Project Euler Task 42 Solution

Question

I am relatively new to programming and have been recommended to work through the many tasks in order, in order to better my skills. For some reason, problem 42 had me stumped for a while:

The nth term of the sequence of triangle numbers is given by, t_n = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t₁₀. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt, a 16K text file containing nearly two-thousand common English words, how many are triangle words?

The following is my beginner-level code, and I was wondering whether any of you wonderful people would help me improve it and give me some tips for the future. In retrospect, I should have probably reused some code from problem 22 since they involve the same skills.

def calculate_total(word):
    alphabet = {'a':1, 'b':2,'c':3,'d':4,'e':5,'f':6,'g':7,'h':8,'i':9,'j':10,'k':11,'l':12,'m':13,'n':14,'o':15,'p':16,'q':17,'r':18,'s':19,'t':20,'u':21,'v':22,'w':23,'x':24,'y':25,'z':26}
    total = 0
    index = 1
    while word[index] != '"':
        total += alphabet[word[index].lower()]
        index += 1
    return total

def gen_triangles(limit):
    triangles = [0, 1]
    index = 1
    while triangles[index] <= limit:
        triangles.append(((index ** 2) + index) // 2)
        index += 1
    return sorted(list(set(triangles)))

def binary_search(aList, itemToFind, first, last):
  if last < first:
    #print(itemToFind + "not in list")
    return False
  else:
    midpoint = (first + last)//2
    if aList[midpoint] > itemToFind:
      return binarySearch(aList, itemToFind, first, midpoint - 1)
    else:
      if aList[midpoint] < itemToFind:
        return binarySearch(aList, itemToFind, midpoint + 1, last)
      else:
        #print(str(itemToFind) + " Found at position: " + str(midpoint))
        return True


def solution():
    myFile = open('Words.txt', 'r')
    wordsArray = myFile.read().split(',')
    for i in range(0, len(wordsArray)):
        wordsArray[i] = calculate_total(wordsArray[i])

    triangles = gen_triangles(max(wordsArray))

    wordTriangles = []
    lengthTriangles = len(triangles) - 1


    for i in range(0, len(wordsArray)):
        #print('i:', i, 'current index:', wordsArray[i])
        if binarySearch(triangles, wordsArray[i], 0, lengthTriangles) == True:
            wordTriangles.append(wordsArray[i])

    print(len(wordTriangles))

solution()

I have been teaching myself some computing theory and have seen that Python's built-in searching keyword in performs a linear search on the array so I decided to branch out and see if I can make my own binary search, which seemed to have worked :D

What was a surprise to me was that this actually runs really quickly. To all of you guys, though, this is probably a huge mess, but hey, that's why I'm here!

Answer 1

A Python solution can be much more succinct than what you wrote.

• Reading the file: The file is a degenerate CSV file with double-quoted values. You can use the csv module to split on commas and discard the double-quotes.
• Opening the file: You can use the fileinput module to avoid hard-coding the filename. The program will either open the filename given as a command-line argument, or read from stdin.
• Generating triangle numbers: You used the given formula ½n(n+1), but if you want to generate the triangle numbers in sequence, you can just add 1+2+3+…, as per the definition. Calling sorted(list(set(…))) is superfluous, since each appended number should be unique and increasing — if you initialize triangles = [0] instead of triangles = [0, 1].

• Binary search: Using a binary search overcomplicates the solution. A linear search is not necessarily that bad, if the list is short — as it will be in this case. Furthermore, you could have just used a set, whose in operator works in O(1) time, instead of a list. Writing less code means fewer opportunities to introduce bugs.

  Personally, I wouldn't even bother pre-generating the triangular numbers. Testing whether a number is triangular can be done using a simple arithmetic loop — the sort of thing that a CPU is very good at doing. For small numbers, it's likely to be even faster than looking up entries in a data structure, since the CPU doesn't have to access memory to perform arithmetic.

  If I had to test a large number t for triangularity in O(1) time, I'd use the formula in this form:

  $$\lfloor \sqrt{2t} \rfloor \lceil \sqrt{2t} \rceil \stackrel{?}{=} 2t$$

  … verifying that \$\sqrt{2t}\$ is not integer.

• Scoring: Use the built-in sum() function with a generator expression. The words appear to be all uppercase already; no need to .lower(). I would use ord() to convert letters to numbers.
• Counting words that meet the criterion: Again, use the sum() function, which will treat True values as 1, effectively acting as a counter. In my solution below, print(sum(is_triangular(score(w)) for w in words(fileinput.input()))) effectively summarizes the purpose of the entire program in one line.

With those suggestions, the solution can just consist of a few one-liner functions, and a loop. It would be a good idea to write doctests to verify that the behavior is consistent with the examples given in the challenge.

import csv
import fileinput
from itertools import count

def is_triangular(number):
    """
    Test whether number is of the form n(n+1)/2.

    >>> is_triangular(1)
    True
    >>> is_triangular(55)
    True
    >>> is_triangular(56)
    False
    """
    counter = count(1)
    while number > 0:
        number -= next(counter)
    return number == 0

def score(word):
    """
    Calculate the word value by converting 'A'=1, 'B'=2, ..., 'Z'=26, and
    adding.  Characters must all be uppercase letters.

    >>> score('SKY')
    55
    """
    return sum(ord(c) - (ord('A') - 1) for c in word)

def words(fileinput):
    return next(csv.reader(fileinput))

if __name__ == '__main__':
    print(sum(is_triangular(score(w)) for w in words(fileinput.input())))

Answer 2

(I wrote this months ago and forgot to post it, so it may no longer matter, but I'll post it anyway.)

wordsArray is used for two different things. At first it's an array of words, but then it becomes an array of the words' values. This tends to be confusing, so it's better to use a new variable.

The first loop in solution goes through a list and collects an output value for each value in the list. Python has a special kind of loop for this: a list comprehension. It makes calculating wordValues very easy:

wordValues = [calculate_total(w) for w in wordsArray]

open's mode defaults to 'r', so you don't need to specify it.

Apparently calculate_total expects each word to end (and also begin?) with ". Instead of skipping them in the loop, you can just remove them by word[1:-1] or word.strip('"').

alphabet is written out by hand instead of calculated. You could generate it automatically. But there's already a built-in function that does almost what alphabet does: ord returns the Unicode codepoint for a character. Can you find a way to use that to calculate the value of each letter?

Instead of iterating over the indexes of word, you can iterate over its characters directly, without mentioning the indexes:

for c in word:
    total += alphabet[c.lower()]

But there's an even easier way: this loop computes the sum of a sequence of values. There's a built-in function for this: sum.

With ord, sum and a comprehension, it's possible to write calculate_total in one line.