Skip to main content

Euler 0018

The Problem:

IfMoving youthrough werea triangle of number (every number chosen yields 2 more numbers to writechoose), outwhat a number as a word, you could then countis the lettershighest andsum generatepath a new number.  
For example: 1 becomes one which becomes 3.  
We use british convention which adds an 'and' betweenin the hundreds and tens place. For example one hundred and forty-four.
How many letters are used in total to write out all of the numbers from 1 to 1000? We can exclude hyphens. triangle?

Considerations and Approach:

ThereWe arewill populate a lottree data structure with the data from the triangle, and then work from the bottom up to find the best path.

Starting at the bottom of uniquesthe wetree needtake the value of the nodes themself, then when moving up the tree, take the best value from the left and right children and add it to keepthe track of, but then we can convert numbers off of a set of rules.  sum.

1This -results onein -the 3top
2node -having twothe -best 3  
3 - three - 5  
4 - four - 4  
5 - five - 4  
6 - six - 3  
7 - seven - 5  
8 - eight - 5  
9 - nine - 4  
10 - ten - 3  
11 - eleven - 6  
12 - twelve - 6  
13 - thirteen - 8  
14 - fourteen - 8  
15 - fifteen - 7  
16 - sixteen - 7  
17 - seventeen - 9  
18 - eighteen - 8  
19 - nineteen - 8  
20 - twenty - 6  
30 - thirty - 6  
40 - forty - 5  
50 - fifty - 5  
60 - sixty - 5  
70 - seventy - 7  
80 - eighty - 6  
90 - ninety - 6  
and - 3  
thousand - 8  
hundred - 7  


1 through twenty have distinct numbers so we will need to keep that into account.


sum.

The Code:

number_dicttriangle_file = {1:3,2:3,3:5,4:4,5:4,6:3,7:5,8:5,9:4,10:3,11:6,12:6,13:8,14:8,15:7,16:7,17:9,18:8,19:8,20:6,30:6,40:5,50:5,60:5,70:7,80:6,90:6}open("triangle", number_end"r")

class Node:
    def __init__(self, value):
        self.l_node = 1000None
        total_sumself.r_node = 0None

        self.value = value
        self.l_sum = -1
        self.r_sum = -1
        self.best = -1

#not necessarily the prettiest way to construct a tree... but oh well.
#there is a lot by reference here.
top_triangle = int(triangle_file.readline())
triangle_tree = Node(top_triangle)
past_line = [triangle_tree]
for line in triangle_file:
    current_line = [Node(int(x)) for x in line.split()]
    for i in range(1,number_endlen(past_line)):
        past_line[i].l_node = current_line[i]
        past_line[i].r_node = current_line[i+1]
    past_line = current_line

#make a function to populate the sums
def pop_sums(node : Node):
    if node.l_node is None:
        node.l_sum = node.value
        node.r_sum = node.value
        node.best = node.value
    else:
        #make sure both below are populated
        if node.l_node.best == -1:
            pop_sums(node.l_node)
        if node.r_node.best == -1:
            pop_sums(node.r_node)
        
        node.l_sum = node.l_node.best + 1):node.value
        constructionnode.r_sum = ""node.r_node.best hundred+ node.value
        node.best = Falsenode.l_sum if int(i / 1000)node.l_sum > 0:node.r_sum total_sumelse +=node.r_sum

number_dict[int(i / 1000)] #thousands place number
        #print(i,int(i / 1000))
        total_sum += 8 #the word thousand
    if int((i % 1000) / 100) > 0:
        #print(i,int((i % 1000) / 100))
        total_sum += number_dict[int((i % 1000) / 100)] #hundreds place number
        total_sum += 7 #the word hundred
        hundred = True
        construction += str(int((i % 1000) / 100)) + "hundred"
    if int((i % 100)) > 0:
        tens = int((i % 100)/10)*10
        ones = int((i % 100))
        ones_true = int(i%10)
        if hundred:
            construction += " and "
            total_sum += 3 #the word and
        if tens >= 20: #numbers greater than 20
            construction += str(tens)
            total_sum += number_dict[tens]
        if ones > 9 and tens < 20: #10 through 19
            construction += str(ones)
            total_sum += number_dict[ones]
        if ones_true > 0 and (ones < 10 or ones > 19): #ten through 19 are weird
            construction += str(ones_true)
            total_sum += number_dict[ones_true]
    #print(construction)pop_sums(triangle_tree)

print(total_sum)triangle_tree.best)
Back to top