Project Euler Task 42 Solution 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, tn = ½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 = t10. 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] &lt;= limit:
        triangles.append(((index ** 2) + index) // 2)
        index += 1
    return sorted(list(set(triangles)))

def binary_search(aList, itemToFind, first, last):
  if last &lt; first:
    #print(itemToFind + "not in list")
    return False
  else:
    midpoint = (first + last)//2
    if aList[midpoint] &gt; itemToFind:
      return binarySearch(aList, itemToFind, first, midpoint - 1)
    else:
      if aList[midpoint] &lt; 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!
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.

    &gt;&gt;&gt; is_triangular(1)
    True
    &gt;&gt;&gt; is_triangular(55)
    True
    &gt;&gt;&gt; is_triangular(56)
    False
    """
    counter = count(1)
    while number &gt; 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.

    &gt;&gt;&gt; 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())))