CS 594 / CS 690 - Assignment 02

CS 594 / CS 690 - Assignment 02

For this assignment, you must work in groups of one or two students. Each person is responsible to write their own code, but the group will (together) discuss their solution. In this notebook, we provide you with basic functions for completing the assignment. Complete the assignment in this notebook. You will need to modify existing code and write new code to find a solution. Each member of the group must upload their own work (i.e., a notebook file) to GitHub.

Note: Running a cell will not rerun previous cells. If you edit code in previous cells, you must rerun those cells. We recommend using Run All to avoid any errors results from not rerunning previous cells. You can find this in the menu above: Cell -> Run All

Problem 1:
(Adapted from ProjectEuler Problem 1.) If we list the natural numbers below 10 that are multiples of 3 or 5, we get: 3, 5, 6, and 9. The sum of these multiples is 23. Write a function that finds the sum of the multiples of p or q below n. Use your function to find the sum of all multiples of 3 or 5 below 10000.

Note: There are two general approaches to this problem, the naïve (slower) approach and a more mathematical (faster) approach involving the inclusion-exclusion principle.

def lcm(p, q):
    m = 1
    while (m*p)%q != 0:
        m += 1
    return m*p

# Define the function to take three arguments.
def sumOfMultiples(p, q, n):
    sum = 0
    m = 1
    while m*p < n:
        sum += m*p
        m += 1
    m = 1
    while m*q < n:
        sum += m*q
        m += 1
    lcm_pq = lcm(p, q)
    m = 1
    while m*lcm_pq < n:
        sum -= m*p*q
        m += 1
    return sum

# Print the output of your function for p=3, q=5, n=10.
print(sumOfMultiples(3, 5, 10))
# Print the output of your function for p=3, q=5, n=10000.
print(sumOfMultiples(3, 5, 10000))
23
23331668
Expected Output:

23
23331668

Problem 2:
(Adapted from ProjectEuler Problem 22.) The file p022_names.txt contains one line with over 5000 comma-separated names, each in all-capital letters and enclosed in quotes. Import the names and sort them into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 * 53 = 49714.

What is the total of the scores for all the names in the file?

# Rather than manually stripping and slicing the data as we did in the previous assigment, 
# let's use the csv module.
import csv

with open('p022_names.txt') as namefile:
    # Complete the line below by specifying the appropriate arguments. 
    # HINT: ref [1]
    name_reader = csv.reader(namefile)
    names = next(name_reader)

# Sort the list of names.
# HINT: ref [2]
names.sort()

# Compute the alphabetical value for each name, with 'A' -> 1, 'B' -> 2, ..., 'Z' -> 26.
# HINT: ref [3]
values = [sum([ord(char)-64 for char in name]) for name in names]

# Multiply each name value by name's position in the ordered list, where the first name is in position 1.
# HINT: ref [4]
scores = [(i+1)*value for i, value in enumerate(values)]

# Print the sum of all the name scores.
print(sum(scores))
871683246
References:

1: csv.reader
2: sort
Note: we can use the function list.sort() without any added arguments, but the sort function has additional capabilities worth exploring. See HowTo/Sorting for more details.
3: ord
4: enumerate
Expected Output:

871683246

Problem-solving advice
When solving a programming problem such as Problem 3 below, it is generally a bad idea to try and optimize your program in your first attempt. Rather than implementing clever algorithms right away, it is better to write a simple script that you are certain will work and is easier to debug. Once your script runs correctly (possibly with smaller input than the final problem you wish to solve), commit your working solution to your GitHub repository, then you can think about how to improve it.

Problem 3:
(From ProjectEuler Problem 45.) Triangular, Pentagonal, and Hexagonal numbers are generated by the following formulae:

Polygonal    formula for nth term    sequence of terms
Triangular    Tn=
n(n+1)
2
 
1, 3, 6, 10, 15, ...
Pentagonal    Pn=
n(3n−1)
2
 
1, 5, 12, 22, 35, ...
Hexagonal    Hn=n(2n−1)    1, 6, 15, 28, 45, ...
The number 1 is triangular, pentagonal, and hexagonal (TPH). Less obviously, 40755=T285=P165=H143 is also TPH. In fact, 40755 is the smallest TPH number bigger than 1.

Write a function to find the smallest TPH number bigger than n. Use your function to find the smallest TPH bigger than 40755.

Note: You can simplify this problem using a relationship between two of the three given sequences.

# The function numpy.argmin may come in handy (ref [1]), but is not necessary.
# from numpy import argmin
import numpy as np

# You will probably want to define functions that compute the n-th polygonal number
# for various polygons. For example...
def getHex(n):
    return n * (2*n - 1)

def getPent(n):
    return n*(3*n-1)/2

# My note: Every hexagonal number is triangular.
# Thus we can ignore the triangular sequence for this problem.

# (The following is necessary for an efficient solution, but not for a brute-force solution.)
# The quadratic formula is useful for computing a least polygonal number greater than n.
# For example, to find the least Hexagonal number greater than 30, solve the equation 
# 30 = x(2x-1), which in general form is 0 = 2x^2 - x - 30. If we write the function below 
# to compute the larger of the two solutions to 0=ax^2 + bx + c, then solve_quad(2, -1, -30) 
# will return 4.1310435... so the next Hexagonal number is getHex(5) = 45.
# HINT: ref [2]
def solve_quad(a, b, c):
    return (-b+np.sqrt(b**2-4*a*c))/(2*a)
    
# Now write a function that returns the least TPH number greater than n. 
def nextTPH(n):
    p = n+1
    h = 0
    while p != h:
        i = np.ceil(solve_quad(2, -1, -p))
        h = getHex(i)
        i = np.ceil(solve_quad(3/2, -1/2, -h))
        p = getPent(i)
    return int(p)

# Print the output of your function for n=1 and again for n=40754.
print(nextTPH(1))
print(nextTPH(40754))

# Print the output of your function for n=40755.
print(nextTPH(40755))
40755
40755
1533776805
References:

1: argmin
2: Wikipedia: quadratic formula
Expected Output:

40755
40755
1533776805

Assignment Questions:
Answer the following questions, in a couple sentences each, in the cells provided below

List the key tasks you accomplished during this assignment?
Describe the challenges you faced in addressing these tasks and how you overcame these challenges?
Did you work with other students on this assignment? If yes, how did you help them? How did they help you? Be as specific as possible.
List the key tasks you accomplished during this assignment?
a. I wrote a function that computes the sum of all multiples of p and q that are below n.

b. I used the csv python module to load a list of names. I computed the "alphabetical value" each name and then its "score". I then computed the sum of all scores.

c. I wrote a function that returns the smallest number above n that is simultaneously triangular, pentagonal, and hexagonal. I realized that every hexagonal number is triangular, and hence I was able to drop the triangular condition. I then wrote the function to bounce between computing the smallest pentagonal number above a given integer and the smallest hexagonal number. When the two numbers are equal, we have our answer.

Describe the challenges you faced in addressing these tasks and how you overcame these challenges?
The main challenge was to write solutions that were efficient. For example, the naive solution for Problem 3 is to keep iterating through numbers above n while checking the TPH condition for each. I suspected through intuition that every hexagonal number is triangular, and then I proved it. I tried to find a similar relationship between pentagonal and hexagonal numbers but could not. I settled on an algorithm that first computes the smallest pentagonal number of n and then computes the smallest hexagonal number above or equal to the pentagonal number; the algorithm bounces between pentagonal and hexagonal in this way. It took a few loops of debugging before I obtained the correct answers. I was satisfied with the efficiency.

Did you work with other students on this assignment? If yes, how did you help them? How did they help you? Be as specific as possibl
I received no help on the assignment. But I did describe the intuition of my algorithm for Problem 3 to a student.