Category Archives: Languages

Project Euler 20: (Iron)Python

In my attempt to learn (Iron)Python out in the open, here’s my solution for Project Euler Problem 20

As always, any feedback is welcome.

# Euler 20
# http://projecteuler.net/index.php?section=problems&id=20
# n! means n x (n - 1) x ... x 3 x 2 x 1
# Find the sum of digits in 100!
import time
start = time.time()

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)
    
print sum([int(i) for i in str(factorial(100))])

print "Elapsed Time:", (time.time() - start) * 1000, "millisecs"
a=raw_input('Press return to continue')

Project Euler 19: (Iron)Python

In my attempt to learn (Iron)Python out in the open, here’s my solution for Project Euler Problem 19

As always, any feedback is welcome.

# Euler 19
# http://projecteuler.net/index.php?section=problems&id=19
# You are given the following information, but you may
# prefer to do some research for yourself.
#
# - 1 Jan 1900 was a Monday.
# - Thirty days has September,
#   April, June and November.
#   All the rest have thirty-one,
#   Saving February alone,
#   Which has twenty-eight, rain or shine.
#   And on leap years, twenty-nine.
# - A leap year occurs on any year evenly divisible by 4,
#   but not on a century unless it is divisible by 400.
#
# How many Sundays fell on the first of the month during
# the twentieth century (1 Jan 1901 to 31 Dec 2000)?
import time
start = time.time()

import datetime
sundays = 0

for y in range(1901,2001):
    for m in range(1,13):
        # monday == 0, sunday == 6
        if datetime.datetime(y,m,1).weekday() == 6:
            sundays += 1
print sundays

print "Elapsed Time:", (time.time() - start) * 1000, "millisecs"
a=raw_input('Press return to continue')

Project Euler 18: (Iron)Python

In my attempt to learn (Iron)Python out in the open, here’s my solution for Project Euler Problem 18

As always, any feedback is welcome.

# Euler 18
# http://projecteuler.net/index.php?section=problems&id=18
# By starting at the top of the triangle below and moving
# to adjacent numbers on the row below, the maximum total
# from top to bottom is 23.
#
# 3
# 7 4
# 2 4 6
# 8 5 9 3
#
# That is, 3 + 7 + 4 + 9 = 23.

# Find the maximum total from top to bottom of the triangle below:

# 75
# 95 64
# 17 47 82
# 18 35 87 10
# 20 04 82 47 65
# 19 01 23 75 03 34
# 88 02 77 73 07 63 67
# 99 65 04 28 06 16 70 92
# 41 41 26 56 83 40 80 70 33
# 41 48 72 33 47 32 37 16 94 29
# 53 71 44 65 25 43 91 52 97 51 14
# 70 11 33 28 77 73 17 78 39 68 17 57
# 91 71 52 38 17 14 91 43 58 50 27 29 48
# 63 66 04 68 89 53 67 30 73 16 69 87 40 31
# 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

# NOTE: As there are only 16384 routes, it is possible to solve
# this problem by trying every route. However, Problem 67, is the
# same challenge with a triangle containing one-hundred rows; it
# cannot be solved by brute force, and requires a clever method! ;o)
import time
start = time.time()

triangle = [
 [75],
 [95, 64],
 [17, 47, 82],
 [18, 35, 87, 10],
 [20, 04, 82, 47, 65],
 [19, 01, 23, 75, 03, 34],
 [88, 02, 77, 73, 07, 63, 67],
 [99, 65, 04, 28, 06, 16, 70, 92],
 [41, 41, 26, 56, 83, 40, 80, 70, 33],
 [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
 [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
 [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
 [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
 [63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
 [04, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 04, 23]]
 
# Loop through each row of the triangle starting at the base.
for a in range(len(triangle) - 1, -1, -1):
    for b in range(0, a):  
        # Get the maximum value for adjacent cells in current row.
        # Update the cell which would be one step prior in the path
        # with the new total. For example, compare the first two
        # elements in row 15. Add the max of 04 and 62 to the first
        # position of row 14.This provides the max total from row 14
        # to 15 starting at the first position. Continue to work up
        # the triangle until the maximum total emerges at the
        # triangle's apex.
        triangle [a-1][b] += max(triangle [a][b], triangle [a][b+1])
 
  
print triangle [0][0]
print "Elapsed Time:", (time.time() - start) * 1000, "millisecs"
a=raw_input('Press return to continue')

Project Euler 17: (Iron)Python

In my attempt to learn (Iron)Python out in the open, here’s my solution for Project Euler Problem 17

As always, any feedback is welcome.

# Euler 17
# http://projecteuler.net/index.php?section=problems&id=17
# If the numbers 1 to 5 are written out in words:
# one, two, three, four, five, then there are
# 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
# If all the numbers from 1 to 1000 (one thousand)
# inclusive were written out in words, how many letters
# would be used?
#
# NOTE: Do not count spaces or hyphens. For example, 342
# (three hundred and forty-two) contains 23 letters and
# 115 (one hundred and fifteen) contains 20 letters. The
# use of "and" when writing out numbers is in compliance
# with British usage.
import time
start = time.time()

def to_word(n):
    h = { 1 : "one", 2 : "two", 3 : "three",
        4 : "four", 5 : "five", 6 : "six",
        7 : "seven", 8 : "eight", 9 : "nine",
        10 : "ten", 11 : "eleven", 12 : "twelve",
        13 : "thirteen", 14 : "fourteen", 15 : "fifteen",
        16 : "sixteen", 17 : "seventeen", 18 : "eighteen",
        19 : "nineteen", 20 : "twenty", 30 : "thirty",
        40 : "forty", 50 : "fifty", 60 : "sixty",
        70 : "seventy", 80 : "eighty", 90 : "ninety",
        100 : "hundred", 1000 : "thousand" }

    word = ""

    # Reverse the numbers so position (ones, tens,
    # hundreds,...) can be easily determined        
    a = [int(x) for x in str(n)[::-1]]
    
    # Thousands position
    if (len(a) == 4 and a[3] != 0):
        # This can only be one thousand based
        # on the problem/method constraints
        word = h[a[3]] + " thousand "
    

    # Hundreds position
    if (len(a) >= 3 and a[2] != 0):
        word += h[a[2]] + " hundred"

        # Add "and" string if the tens or ones
        # position is occupied with a non-zero value.
        # Note: routine is broken up this way for [my] clarity.
        if (len(a) >= 2 and a[1] != 0):
            # catch 10 - 99
            word += " and"
        elif len(a) >= 1 and a[0] != 0:
            # catch 1 - 9
            word += " and"

    # Tens and ones position
    tens_position_value = 99
    if (len(a) >= 2 and a[1] != 0):
        # Calculate the tens position value per the
        # first and second element in array
        # e.g. (8 * 10) + 1 = 81
        tens_position_value = int(a[1]) * 10 + a[0]

        if tens_position_value <= 20:
            # If the tens position value is 20 or less
            # there's an entry in the hash. Use it and there's
            # no need to consider the ones position
            word += " " + h[tens_position_value]
        else:
            # Determine the tens position word by
            # dividing by 10 first. E.g. 8 * 10 = h[80]
            # We will pick up the ones position word later in
            # the next part of the routine
            word += " " + h[(a[1] * 10)]
        
    if (len(a) >= 1 and a[0] != 0 and tens_position_value > 20):
        # Deal with ones position where tens position is
        # greater than 20 or we have a single digit number
        word += " " + h[a[0]]
    
    # Trim the empty spaces off both ends of the string
    return word.replace(" ","")    


def to_word_length(n):    
    return len(to_word(n))    

print sum([to_word_length(i) for i in xrange(1,1001)])

print "Elapsed Time:", (time.time() - start) * 1000, "millisecs"
a=raw_input('Press return to continue')

Project Euler 16: (Iron)Python

In my attempt to learn (Iron)Python out in the open, here’s my solution for Project Euler Problem 16

As always, any feedback is welcome.

# Euler 16
# http://projecteuler.net/index.php?section=problems&id=16
# 2^15 = 32768 and the sum of its digits is
# 3 + 2 + 7 + 6 + 8 = 26.
# What is the sum of the digits of the number 2^1000?
import time
start = time.time()

print sum([int(i) for i in str(2**1000)])

print "Elapsed Time:", (time.time() - start) * 1000, "millisecs"
a=raw_input('Press return to continue')

Project Euler 15: (Iron)Python

In my attempt to learn (Iron)Python out in the open, here’s my solution for Project Euler Problem 15

As always, any feedback is welcome.

# Euler 15
# http://projecteuler.net/index.php?section=problems&id=15
# Starting in the top left corner of a 2x2 grid, there
# are 6 routes (without backtracking) to the bottom right
# corner. How many routes are their in a 20x20 grid?
import time
start = time.time()

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)
    
rows, cols = 20, 20
print factorial(rows+cols) / (factorial(rows) * factorial(cols))

print "Elapsed Time:", (time.time() - start) * 1000, "millisecs"
a=raw_input('Press return to continue')

Project Euler 14: (Iron)Python

In my attempt to learn (Iron)Python out in the open, here’s my solution for Project Euler Problem 14

As always, any feedback is welcome.

# Euler 14
# http://projecteuler.net/index.php?section=problems&id=14
# The following iterative sequence is defined for the set
# of positive integers:
# n ->  n/2 (n is even)
# n ->  3n + 1 (n is odd)
# Using the rule above and starting with 13, we generate
# the following sequence:
# 13  40  20  10  5  16  8  4  2  1
# It can be seen that this sequence (starting at 13 and
# finishing at 1) contains 10 terms. Although it has not
# been proved yet (Collatz Problem), it is thought that all
# starting numbers finish at 1. Which starting number,
# under one million, produces the longest chain?
# NOTE: Once the chain starts the terms are allowed to go
# above one million.
import time
start = time.time()

def collatz_length(n):
    # 0 and 1 return self as length
    if n <= 1: return n

    length = 1
    while (n != 1):
      if (n % 2 == 0):
        n /= 2
      else:
        n = 3*n + 1
      
      length += 1
    
    return length
    
starting_number, longest_chain = 1, 0

for x in xrange(1, 1000001):
    l = collatz_length(x)
    if l > longest_chain: starting_number, longest_chain = x, l 
        
print starting_number
print longest_chain

# Slow 31 seconds
print "Elapsed Time:", (time.time() - start) * 1000, "millisecs"
a=raw_input('Press return to continue')

Project Euler 13: (Iron)Python

In my attempt to learn (Iron)Python out in the open, here’s my solution for Project Euler Problem 13

As always, any feedback is welcome.

# Euler 13
# http://projecteuler.net/index.php?section=problems&id=13
# Work out the first ten digits of the sum of the
# following one-hundred 50-digit numbers.
import time
start = time.time()

number_string = '\
37107287533902102798797998220837590246510135740250\
46376937677490009712648124896970078050417018260538\
74324986199524741059474233309513058123726617309629\
91942213363574161572522430563301811072406154908250\
23067588207539346171171980310421047513778063246676\
89261670696623633820136378418383684178734361726757\
28112879812849979408065481931592621691275889832738\
44274228917432520321923589422876796487670272189318\
47451445736001306439091167216856844588711603153276\
70386486105843025439939619828917593665686757934951\
62176457141856560629502157223196586755079324193331\
64906352462741904929101432445813822663347944758178\
92575867718337217661963751590579239728245598838407\
58203565325359399008402633568948830189458628227828\
80181199384826282014278194139940567587151170094390\
35398664372827112653829987240784473053190104293586\
86515506006295864861532075273371959191420517255829\
71693888707715466499115593487603532921714970056938\
54370070576826684624621495650076471787294438377604\
53282654108756828443191190634694037855217779295145\
36123272525000296071075082563815656710885258350721\
45876576172410976447339110607218265236877223636045\
17423706905851860660448207621209813287860733969412\
81142660418086830619328460811191061556940512689692\
51934325451728388641918047049293215058642563049483\
62467221648435076201727918039944693004732956340691\
15732444386908125794514089057706229429197107928209\
55037687525678773091862540744969844508330393682126\
18336384825330154686196124348767681297534375946515\
80386287592878490201521685554828717201219257766954\
78182833757993103614740356856449095527097864797581\
16726320100436897842553539920931837441497806860984\
48403098129077791799088218795327364475675590848030\
87086987551392711854517078544161852424320693150332\
59959406895756536782107074926966537676326235447210\
69793950679652694742597709739166693763042633987085\
41052684708299085211399427365734116182760315001271\
65378607361501080857009149939512557028198746004375\
35829035317434717326932123578154982629742552737307\
94953759765105305946966067683156574377167401875275\
88902802571733229619176668713819931811048770190271\
25267680276078003013678680992525463401061632866526\
36270218540497705585629946580636237993140746255962\
24074486908231174977792365466257246923322810917141\
91430288197103288597806669760892938638285025333403\
34413065578016127815921815005561868836468420090470\
23053081172816430487623791969842487255036638784583\
11487696932154902810424020138335124462181441773470\
63783299490636259666498587618221225225512486764533\
67720186971698544312419572409913959008952310058822\
95548255300263520781532296796249481641953868218774\
76085327132285723110424803456124867697064507995236\
37774242535411291684276865538926205024910326572967\
23701913275725675285653248258265463092207058596522\
29798860272258331913126375147341994889534765745501\
18495701454879288984856827726077713721403798879715\
38298203783031473527721580348144513491373226651381\
34829543829199918180278916522431027392251122869539\
40957953066405232632538044100059654939159879593635\
29746152185502371307642255121183693803580388584903\
41698116222072977186158236678424689157993532961922\
62467957194401269043877107275048102390895523597457\
23189706772547915061505504953922979530901129967519\
86188088225875314529584099251203829009407770775672\
11306739708304724483816533873502340845647058077308\
82959174767140363198008187129011875491310547126581\
97623331044818386269515456334926366572897563400500\
42846280183517070527831839425882145521227251250327\
55121603546981200581762165212827652751691296897789\
32238195734329339946437501907836945765883352399886\
75506164965184775180738168837861091527357929701337\
62177842752192623401942399639168044983993173312731\
32924185707147349566916674687634660915035914677504\
99518671430235219628894890102423325116913619626622\
73267460800591547471830798392868535206946944540724\
76841822524674417161514036427982273348055556214818\
97142617910342598647204516893989422179826088076852\
87783646182799346313767754307809363333018982642090\
10848802521674670883215120185883543223812876952786\
71329612474782464538636993009049310363619763878039\
62184073572399794223406235393808339651327408011116\
66627891981488087797941876876144230030984490851411\
60661826293682836764744779239180335110989069790714\
85786944089552990653640447425576083659976645795096\
66024396409905389607120198219976047599490197230297\
64913982680032973156037120041377903785566085089252\
16730939319872750275468906903707539413042652315011\
94809377245048795150954100921645863754710598436791\
78639167021187492431995700641917969777599028300699\
15368713711936614952811305876380278410754449733078\
40789923115535562561142322423255033685442488917353\
44889911501440648020369068063960672322193204149535\
41503128880339536053299340368006977710650566631954\
81234880673210146739058568557934581403627822703280\
82616570773948327592232845941706525094512325230608\
22918802058777319719839450180888072429661980811197\
77158542502016545090413245809786882778948721859617\
72107838435069186155435662884062257473692284509516\
20849603980134001723930671666823555245252804609722\
53503534226472524250874054075591789781264330331690'

total = 0

for i in xrange(0, 100 * 50 - 1, 50):       
    total += int(number_string[i:i+49])         
        
print str(total)[:10]

print "Elapsed Time:", (time.time() - start) * 1000, "millisecs"
a=raw_input('Press return to continue')