Project Euler: Determining the number of paths in a grid

Filed Under hisabati, project euler by | Comments Off on Project Euler: Determining the number of paths in a grid

For problem 15 from Project Euler, we are asked to find the number of paths leading from the top left corner of a grid to the bottom right corner that do not involve backtracking.

Starting in the top left corner of a 2 by 2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20 by 20 grid?

Given the way the problem is set up, for any one node there are at most two nodes that can lead directly to the node. If we assign coordinates to the grid with (0,0) being the top-left corner, the only nodes that have direct outgoing paths to (1,1) are (0,1) and (1,0). Trivially, each of the nodes in row 0 (the top row) has only one node that can lead into it (the node immediately to its left). Similarly, nodes in column 0 (the left-most column) each have one node leading into them (the node immediately above them). We can use this information to calculate the number of paths ending at any one node in the grid.

To do this, consider nodes A, B and C that form the lower right triangle of an arbitrary square in the grid. We label the nodes such that A is the lower left corner of the square, B is the lower right corner while C is the upper right corner of the square. As shown before, the only way to get a path ending at B is to take a path ending at either A or C and add one step to it. We also know that a path ending at A cannot pass through C (since we don’t allow backtracking) and similarly a path ending at C cannot pass through A. Therefore, the number of paths ending at B = number of paths ending at A + number of paths ending at C.

This leads to the following rather short algorithm:

  1: def num_paths_to_grid_bottom(numRowCells, numColumnCells):
  2:     currRow = [1 for x in range(numColumnCells + 1)]
  3:     # the number of nodes to consider = numRowCells + 1
  4:     for numRow in range(1, numRowCells + 1):
  5:         for numColumn in range(1, numColumnCells + 1):
  6:             currRow[numColumn] += currRow[numColumn - 1]
  7:     return currRow[numColumnCells]

Project Euler: finding maximal sum of path in a graph

Filed Under hisabati, project euler by | Comments Off on Project Euler: finding maximal sum of path in a graph

Problem 18 in Project Euler reminded me of shortest path algorithms in graph theory. The goal is to determine the maximal sum you can compute when traveling from the top to the bottom of a triangle.

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 5
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

If this were a shortest path problem, we would be computing the minimum sum when traveling down the triangle (and we would also have a fixed destination, rather than a set of them – details, details). As phrased, the problem does not actually require us to give the path that yields the maximal sum and that eases the requirements on our algorithm.

The first step of our solution is to read lists of integers from the input triangle string.

  1: def get_triangle_lists(triangleString):
  2:     listOfRowsString = triangleString.split('n')
  3:     listOfRows = []
  4:     for row in listOfRowsString:
  5:         currRow = [int(x) for x in row.split()]
  6:         listOfRows.append(currRow)
  7:     return listOfRows

Next, we compute the max sum.

  1: def max_sum_in_triangle(triangleString):
  2:     listOfLists = get_triangle_lists(triangleString)
  3:     numRows = len(listOfLists)
  4:     for index in range(0, numRows):
  5:         if(index == 0):
  6:             continue
  7:         currRow = listOfLists[index]
  8:         previousRow = listOfLists[index - 1]
  9:         for column in range(0, index+1):
 10:             if (column == 0):
 11:                 currRow[column] += previousRow[column]
 12:             elif(column == index):
 13:                 currRow[column] += previousRow[column - 1]
 14:             else:
 15:                 currRow[column] += max(previousRow[column - 1], previousRow[column])
 16:     return max(listOfLists[numRows - 1])

The motivation is simple. We go through the triangle, from top to bottom one row at a time (breadth-first). For each node, we set its value to the maximal sum that can be achieved by a valid path ending in that node. For the top node, the maximal sum is trivially the value of the node. For subsequent rows, each node can be reached from exactly one or two nodes from the previous row.  The outer nodes in a row are only reachable from the outer nodes from the previous row. This means that for these nodes, we always add the current node value to the previous outer node’s value ( Lines 10 to 13 of the code above). Nodes that are not outer nodes in the row are reachable from two nodes in the previous row (the node to the upper left and one to the upper right in the graphical representation).The maximal sum at the current node is therefore given by the value of the current node plus the higher value between those presented in the two nodes in the previous row (Line 15 of the code above).

When the algorithm finishes iterating through the rows, the maximal value can be read directly from the bottom row of the triangle (line 16 in the code above).

Problem 11 from Project Euler is a fun one:

In the 20 by 20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is  26 \times 63 \times 78 \times 14 = 1788696.

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20 by 20 grid?

I came up with two solutions: a naive exhaustive search (which still runs remarkably fast in python) and a slightly more efficient one in the spirit of my solution to problem 8. The naive version proceeds as follows:

  1: def max_prod_in_grid_basic(gridString, windowSize):
  2:     gridNums = [int(x) for x in gridString.split()]
  3:     gridLen = int(sqrt(len(gridNums)))
  4:     maxProduct = 0
  5:     # get horizontal products
  6:     lastColumn = gridLen - windowSize + 1
  7:     for rootRow in range(0, gridLen):
  8:         for rootColumn  in range(0, lastColumn):
  9:             startIndex = (rootRow * gridLen) + rootColumn
 10:             endIndex = startIndex + windowSize
 11:             windowItems = gridNums[startIndex:endIndex]
 12:             currProduct = prod(windowItems)
 13:             if(currProduct > maxProduct):
 14:                 maxProduct = currProduct
 15:     # get vertical products
 16:     lastRow = gridLen - windowSize + 1
 17:     for rootColumn  in range(0, gridLen):
 18:         for rootRow in range(0, lastRow):
 19:             startIndex = (rootRow * gridLen) + rootColumn
 20:             endIndex = startIndex + (gridLen * windowSize)
 21:             windowItems = gridNums[startIndex: endIndex: gridLen]
 22:             currProduct = prod(windowItems)
 23:             if(currProduct > maxProduct):
 24:                 maxProduct = currProduct
 25:     # get down-diagonal products
 26:     lastRow = gridLen - windowSize + 1
 27:     lastColumn = gridLen - windowSize + 1
 28:     for rootRow in range(0, lastRow):
 29:         for rootColumn  in range(0, lastColumn):
 30:             startIndex = (rootRow * gridLen) + rootColumn
 31:             endIndex = startIndex + (gridLen * windowSize) + windowSize
 32:             windowItems = gridNums[startIndex: endIndex: gridLen+1]
 33:             currProduct = prod(windowItems)
 34:             if(currProduct > maxProduct):
 35:                 maxProduct = currProduct
 36:     # get up-diagonal products
 37:     lastRow = gridLen - windowSize + 1
 38:     lastColumn = gridLen
 39:     firstColumn = windowSize - 1
 40:     for rootRow in range(0, lastRow):
 41:         for rootColumn  in range(firstColumn, lastColumn):
 42:             startIndex = (rootRow * gridLen) + rootColumn
 43:             endIndex = startIndex + (gridLen * windowSize) - windowSize
 44:             windowItems = gridNums[startIndex: endIndex: gridLen-1]
 45:             currProduct = prod(windowItems)
 46:             if(currProduct > maxProduct):
 47:                 maxProduct = currProduct
 48:     return maxProduct

The primary weakness with this approach is that it does not take advantage of the fact that there is a simple relationship between the products of two adjacent sets of consecutive numbers. From the solution to problem 8:

We achieve some performance gain by taking advantage of the overlap between adjacent windows. If the window has length 5, then adjacent windows have 3 elements in common. The overlap elements contribute the same value to the product computed for the two adjacent windows. Therefore, the difference between the product computed for a window starting at index i and one starting at i+1 is due to elements at the end of the windows. Specifically, the product of the window rooted at i+1 is given by the dividing the value of the product of the window rooted at i by the value of the ith element (undoing the effect of the element we’re removing) multiplied by the value of the element at position i+(windowSize – 1) (adding the effect of the new element)

The second algorithm takes advantage of this information. The solution is in two functions. First, we extract the list of valid sequences (all the rows, columns and up and down diagonals), taking the maximum length of each sequence.

  1: def get_sequences_in_grid(gridString, minLength):
  2:     gridNums = [int(x) for x in gridString.split()]
  3:     gridLen = int(sqrt(len(gridNums)))
  4:     digitSequences = []
  5:     # get horizontal sequences
  6:     rootColumn = 0
  7:     for rootRow in range(0, gridLen):
  8:         startIndex = (rootRow * gridLen) + rootColumn
  9:         endIndex = startIndex + gridLen
 10:         listItems = gridNums[startIndex:endIndex]
 11:         digitSequences.append(listItems)
 12:     # get vertical sequences
 13:     rootRow = 0
 14:     for rootColumn  in range(0, gridLen):
 15:         startIndex = (rootRow * gridLen) + rootColumn
 16:         endIndex = int(len(gridNums))
 17:         listItems = gridNums[startIndex: endIndex: gridLen]
 18:         digitSequences.append(listItems)
 19:     # get down-diagonal sequences
 20:     # upper triangle
 21:     lastRow = gridLen - minLength + 1
 22:     lastColumn = gridLen - minLength + 1
 23:     rootRow = 0
 24:     for rootColumn  in range(0, lastColumn):
 25:         startIndex = (rootRow * gridLen) + rootColumn
 26:         endIndex = (rootRow + 1 +(gridLen - (rootColumn + 1))) * gridLen
 27:         listItems = gridNums[startIndex: endIndex: gridLen+1]
 28:         digitSequences.append(listItems)
 29:     # lower triangle
 30:     rootColumn = 0
 31:     for rootRow in range(1, lastRow):
 32:         startIndex = (rootRow * gridLen) + rootColumn
 33:         endIndex = (rootRow + 1 + (gridLen - (rootRow + 1))) * gridLen
 34:         listItems = gridNums[startIndex: endIndex: gridLen+1]
 35:         digitSequences.append(listItems)
 36:     # get up-diagonal sequences
 37:     # upper triangle
 38:     rootRow = 0
 39:     firstColumn = minLength - 1
 40:     for rootColumn  in range(firstColumn, gridLen):
 41:         startIndex = (rootRow * gridLen) + rootColumn
 42:         endIndex = startIndex + (rootColumn * gridLen)
 43:         listItems = gridNums[startIndex: endIndex: gridLen - 1]
 44:         digitSequences.append(listItems)
 45:     # lower triangle
 46:     rootColumn = gridLen - 1
 47:     for rootRow in range(1, lastRow):
 48:         startIndex = (rootRow * gridLen) + rootColumn
 49:         endIndex = (rootRow + 1 + (gridLen - (rootRow + 1))) * gridLen
 50:         listItems = gridNums[startIndex: endIndex: gridLen - 1]
 51:         digitSequences.append(listItems)
 52:     return digitSequences
 53: 

The second step takes the list of sequences and iterates through them, computing the max product for each list using a modified version of the “slice product” function from problem 8.

  1: def max_prod_in_grid(gridString, minLength):
  2:     sequences = get_sequences_in_grid(gridString, minLength)
  3:     max_product = 0
  4:     for currList in sequences:
  5:         listLength = len(currList)
  6:         if(listLength < minLength):
  7:             continue
  8:         curr_product = prod(currList[:minLength])
  9:         if(curr_product > max_product):
 10:             max_product = curr_product
 11:         for i in range(1, listLength - minLength + 1):
 12:             stopPosition = i + (minLength - 1)
 13:             outItem = currList[i - 1]
 14:             inItem = currList[stopPosition]
 15:             if(outItem == 0):
 16:                 curr_product = prod(currList[i:stopPosition + 1])
 17:             else:
 18:                 curr_product = (curr_product / outItem) * inItem
 19:             if(curr_product > max_product):
 20:                 max_product = curr_product
 21:     return max_product

For Problem 8 in Project Euler, you are required to find the largest product of 5 consecutive digits in a 1000 digit integer.

7316717653133062491922511967442657474235534919493496983520
3127745063262395783180169848018694788518438586156078911294
9495459501737958331952853208805511125406987471585238630507
1569329096329522744304355766896648950445244523161731856403
0987111217223831136222989342338030813533627661428280644448
6645238749303589072962904915604407723907138105158593079608
6670172427121883998797908792274921901699720888093776657273
3300105336788122023542180975125454059475224352584907711670
5560136048395864467063244157221553975369781797784617406495
5149290862569321978468622482839722413756570560574902614079
7296865241453510047482166370484403199890008895243450658541
2275886668811642717147992444292823086346567481391912316282
4586178664583591245665294765456828489128831426076900422421
9022671055626321111109370544217506941658960408071984038509
6245544436298123098787992724428490918884580156166097919133
8754992005240636899125607176060588611646710940507754100225
6983155200055935729725716362695618826704282524836008232575
30420752963450

My implementation for this proceeds as follows:

  1: def window_slice_product(num,windowSize):
  2:     digits = [int(x) for x in str(num)]
  3:     sequencewindowSize = len(digits)
  4:     if(sequencewindowSize <= windowSize):
  5:         return prod(digits)
  6:
  7:     products =[]
  8:     curr_product = prod(digits[:windowSize])
  9:     max_product = curr_product
 10:     for i in range(1, sequencewindowSize - windowSize + 1):
 11:         stopPosition = i + (windowSize - 1)
 12:         outItem = digits[i - 1]
 13:         inItem = digits[stopPosition]
 14:         if(outItem == 0):
 15:             curr_product = prod(digits[i:stopPosition + 1])
 16:         else:
 17:             curr_product = (curr_product / outItem) * inItem
 18:         if(curr_product > max_product):
 19:             max_product = curr_product
 20:     return max_product

Given the digits in the input number, we create a list with all the integers in sequence. To calculate the required product, we create a sliding window of length 5, which serves as a snapshot of the list. In each iteration of the loop starting on line 10, we ‘slide’ the window down the list (we start with the window’s first element at index 0 and consider 5 consecutive items; move the window to have first item at index 1 and consider 5 items etc until we get to the point where the window’s starting element is at index 995). We take the product of each window and check if it’s higher than the maximal product seen so far. At the end, we report the max product.

We achieve some performance gain by taking advantage of the overlap between adjacent windows. If the window has length 5, then adjacent windows have 3 elements in common. The overlap elements contribute the same value to the product computed for the two adjacent windows. Therefore, the difference between the product computed for a window starting at index i and one starting at i+1 is due to elements at the end of the windows. Specifically, the product of the window rooted at i+1 is given by the dividing the value of the product of the window rooted at i by the value of the ith element (undoing the effect of the element we’re removing) multiplied by the value of the element at position i+(windowSize – 1) (adding the effect of the new element). This is achieved in lines 11 to 17 of the algorithm posted.

In the cases where we remove a zero, its necessary to compute the product for the new window by multiplying all items in the window – otherwise we would end up dividing by zero.

For problem 20, the goal is to sum all the digits in a large number:

n! = n\times (n-1) \times \ldots \times 3 \times 2 \times 1

Find the sum of the digits in the number 100!

The algorithm proceeds as follows:

  1: def factorial(n):
  2:     if(n == 0):
  3:         return 1
  4:     else:
  5:         return (n * factorial(n-1))
  6:
  7: def sum_factorial(n):
  8:     fact = factorial(n)
  9:     digits = [int(x) for x in str(fact)]
 10:     return sum(digits)

The factorial() function is defined in a pretty straightforward recursive algorithm. The interesting line stuff happens in the sum_factorial() function (specifically on line 9). We use a list comprehension to unpack the digits in the factorial number into a list object. When the comprehension is evaluated, the call to str() converts the factorial number to a string (which is iterable). We take each character in the string and call int() on it to convert it to an integer. The collection of integers is then collected into a list. the call to sum() on line 10 takes a list of integers and returns a single number which is the sum.

This is the  second of a series of problems form Project Euler that I’ve worked on as part of my “Learn Python” project. In Problem 5, the question is:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

In mathematical terms, this is asking for the Least Common Multiple of the numbers in the range from 1 to 20. The algorithm here is an implementation of the “LCM by table” method described in the linked Wikipedia article.

  1: def find_lcm_of_range(n):
  2:     assert (0 < n)
  3:     residues = range(1, n+1)
  4:     divisor = 2
  5:     lcm_factors = []
  6:     found_factor = False
  7:     while True:
  8:         #print residues
  9:         found_factor = False
 10:         highest_power = 0
 11:         for index, item in enumerate(residues):
 12:             if(item < 2):
 13:                 continue
 14:             elif((item % divisor) == 0):
 15:                 found_factor = True
 16:                 # extract all powers of the divisor
 17:                 curr_power = 0
 18:                 while ((residues[index] % divisor) == 0):
 19:                     residues[index] = residues[index] / divisor
 20:                     curr_power += 1
 21:                 if(curr_power > highest_power):
 22:                     highest_power = curr_power
 23:         if(found_factor):
 24:             highest_value = pow(divisor, highest_power)
 25:             lcm_factors.append(highest_value)
 26:             # remove 1s from the list
 27:             residues[:] = [x for x in residues if (x != 1)]
 28:         if(divisor < n):
 29:             if(divisor == 2):
 30:                 divisor += 1
 31:             else:
 32:                 divisor += 2
 33:         else:
 34:             break
 35:     print "LCM factors: ", lcm_factors
 36:     # multiply out all factors
 37:     lcm = 1
 38:     for f in lcm_factors:
 39:         lcm *= f
 40:
 41:     return lcm

The algorithm finds the lcm of the numbers in range (1,n) by accumulating factors in a list. This is similar to the Prime Factors code from a previous post – we try all numbers starting at 2 and check if we have a factor for any number in the list. Once we find a factor, we figure out the highest exponent of the divisor that divides a number on the list (lines 18 – 21). The value of the divisor to its maximal power is taken as a factor and added to our list. We also reduce the values of numbers in the range as we find factors, keeping computation costs low. At the end of an iteration involving a particular divisor, we remove all numbers in the residues list whose values are now 1 (i.e. we’ve found all their factors so they no longer need to be considered in future iterations) [line 27]. At the end, when we have the list of factors, we multiply them out to give the lcm.

To get a better idea of how this works, you can uncomment line 8 and observe the list of residues at each iteration. The algorithm is exponential but runs surprisingly fast – the lcm for numbers between 1 and 20 is determined in 1 millisecond whereas the lcm for the range 1-10,000 is found in 2.749 seconds. The latter number is pretty big:

5793339670287642968692270879166240098634860297998518825393
1383511489793001457731823088325981761829221665744176794023
4070565594914024678915773283267630212994668431184746378526
5683193852154947234797107306816167930170547268523692646338
7338495220571064420250677315000599457941340849496227227628
9264937710182648218422303703496401025734928814243173061895
6946710149583460199127003991878092450649540579792376220536
0790652073159333382795670426041033566699342449050309786673
6816704833691556895675542398988790397441473339719882580610
4209097047672929348451307244361479576687872632579585485539
4491290821167148355514749149683707585283381546153703014210
4424703181805119066911083251464942193434988993829180182465
8660982766747032916601211087498110480041574152758628002673
7848182673635645872230905234515169611121042867043956727839
3141987286262740666554678461833435991947615903686084725783
9816974011148592404698687071488389428584139496462740809416
1019230662749101230783008668676907211199488107523306410531
7720454528539577068732384668299886498221575571035032835633
9828177546491190478915951590098740157467888594249390760474
0891878907698622679570965569483682456042918236444719794534
4111719076063360905340293493513002761418925297954487518263
9439915321618327038573779574877050861209637476533357823797
3395907265484337502903901947799663388329849198045756207969
5900556866076781952063672736006329094170242247547504287112
3691791366341921592583094403553984874916317848961422754665
6090790164108195741048033614368495827231281392190063051315
2480701922634008013150956085121395107314697323113138989957
4604056343312142777607148265590434653828101066847673113241
5829844984600414136781404774213539507859790229205890271721
6003091699268061218717500081637387739116100095086091496653
3257963276739707887799692658133741935183475437041100868613
6818501030862345505385357198060894463821342298717851567836
5629843448064696137680247649673729796551790660743981982468
0510457613447482301648884281807704166167609839937880971389
4284994865370648616800689225595431967181072865363430005250
8407678909121645307057049368379155848566069606873473723913
3925443211908593217554139295434368471669516262927122978928
9404752104218596977036941910521266321726821940533986384237
9944037806183013790993479752601227241944542750888255870444
8820896569037370690405692650932469630881097433179011945643
8147168585552011926921912167450509941646104076818762060881
9039696164316463849858959442312185056205470938742411697592
0545014547874611279689862671196632096505721221995856733885
1356631739947125096250452942497473309299907612330435197454
3927886373592531163086850070142496054926595244291345133441
3751710187227942820228595165285635482723076593150280534169
6470148698002737700823078904634554776750169178259216255903
9688655887498277898889501724524554482488337123098356575613
6923315797740557936529367194313141203410990194489281924500
1657496671822581274180596255340507054499934060282320458240
7224542099335697359400328591099346868782741108643949244635
7385201533842888196184329208356603466981461961260663828361
5766521897504566616272305253931938372830446073384019299355
3208643427340195176336623467904229159519548226451370914941
2610039010451098737336632861536305604213744080822597360080
9566845718073791616927784260557845021823094999326904373592
3194075166608967643880922625103691821535592854460749909418
6351624722653265314219855184006363198942877679953328621546
4660644129411503287306838551341184739976807097763115368031
7486460437805490551434282972306780537384530102349490082537
6935520720816799920335315752466601702980367961213182474079
4652592875662818479980117505768541194835524231818203552256
4267527304551157522808370997632376063481928679364579939708
6644626401581281917999413864229510887238170918193709229039
2544335464025324661284746003660247161196698209062164637264
1149307664444734710834082003296620590642018967211650156874
8772830085450178081015584483748979814430994299909177446640
6270065305461848242329380636274754660519867343112275861821
2935011121014348682253780418138368087454176062891599042941
6594140869292225060112780497196234280792774339003039504826
3275616935165347620718001157478088456439083590834464409622
7816937908832895970240439825842200692241702358634587453443
6568408211443036286744619360107556980365077301802670000381
2298460527976219100308016537538008597751565631582745643139
434508332515569645426771932483266712323523039014220800000L

The best way to learn a programming language is to use it in a project. Having a book is nice as a starting point (and as a reference guide) but I find that you have to step out of the world of tutorials and samples to see new sides of a language and encounter its frustrations. I’ve been meaning to try out python for a while now but I didn’t have a project that I would use it on. Recently, I came across a perfect candidate: Project Euler.

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

This is the perfect tool for learning a language that has a functional bent to it.

For my first bit of Python, I tried out problem 3.

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

def unique_prime_factors(n):
   assert (0 < n)
   if (n == 1):
      return [n]

   factors = []
   residue = n
   divisor = 2
   while True:
      if residue == 1:
         break

      while ((residue % divisor) != 0):
         divisor += 1
      factors.append(divisor)

      while ((residue % divisor) == 0):
        residue /= divisor
   return factors

The idea behind the algorithm is pretty straight-forward. Given a number n, check for divisors from 2 to a max number (initially n). Each time we find a divisor, we reduce the max number and use the residue as our new max number. This implicitly caps the size of divisor considered at \sqrt{n} .Also, when we find a factor, we divide the residue for a long as the factor is a divisor thus extracting all the powers of the factor in the residue.

Reducing the residue to the smallest number we need speeds up our algorithm and proves to be a great boost in performance if we the number we’re factoring has small factors (i.e. is B-smooth for a small B).

The American Presidential campaign was filled with mudslinging and hate. The republican propaganda machine painted the picture of Obama as an un-American outsider, a terrorist, a socialist; they stopped short of calling him the anti-Christ. It reminded me of the Kenyan election. Thankfully, in the American case, the losing candidate conceded defeat graciously and the winner accepted the concession magnanimously.

The propaganda machine did not go away on polling day. Talk radio is still active spreading fear and hate. Last week, a Republican Congressman, Paul Broun, made the allegation that Obama would establish a Gestapo force in America (on talk radio, no less). A news report from AP has the details.

Broun was specifically referring to a July speech by Obama, where the then-Democratic presidential nominee said he supports a civilian force helping the military when it comes to national security.

Responding to those comments, Broun told the AP Monday: “That’s exactly what Hitler did in Nazi Germany and it’s exactly what the Soviet Union did. When he’s proposing to have a national security force that’s answering to him, that is as strong as the U.S. military, he’s showing me signs of being Marxist.”

“We can’t be lulled into complacency,” Broun added. “You have to remember that Adolf Hitler was elected in a democratic Germany.”

The statement is absolutely untenable and irrational. It is amazing to see this happen in America. Politics has moved from the realm of reasoned debate and policy discussions to appealing to people’s fears and latent prejudices. The target audience is divided into groups totally unrelated to the policies – in America, Palin preached about a “real” America and an “elitist” or “unpatriotic” fake America. If this were in Kenya, the proxy for policy discourse would would be tribal affiliation. Accusations would be “my opponent is a Muslim; he will only help his tribesmen” et cetera. Those are not quite as bad as “my opponent is Hitler” (though the republican machinery did use these earlier on). The experience makes me rethink my perceptions of tribalism. The line of division doesn’t matter – the tendency to fiery irrational hate and even violence is the same.

Obama’s victory has been hailed as a victory for America. It is an affirmation that the country lives by the ideals that it was founded on. The vibrant movement that Obama mobilized shows that the government really is of the people. His unlikely ascendancy shows that it is still a land of opportunity – where a middle-class multi-racial kid from a single parent upbringing can rise to the highest office in the land.

For a nation that started out treating black people as sub-human and just 30 years ago criminalized interracial marriages, the transformation is amazing. As an African living in America, I share the euphoria of the black community. Obama is Joshua to Martin Luther King’s Moses. Dr. King led his people through the great struggle. He inspired many and spoke of a future in which the value of a man would be determined by the quality of his character – regardless of race. This is that time and this is the land of his dreams.

In the last speech he gave on the day before he was assassinated, King talked about the promised land:

Well, I don’t know what will happen now. We’ve got some difficult days ahead. But it really doesn’t matter with me now, because I’ve been to the mountaintop. And I don’t mind. Like anybody, I would like to live a long life. Longevity has its place. But I’m not concerned about that now. I just want to do God’s will. And He’s allowed me to go up to the mountain. And I’ve looked over. And I’ve seen the Promised Land. I may not get there with you. But I want you to know tonight, that we, as a people, will get to the promised land! And so I’m happy, tonight. I’m not worried about anything. I’m not fearing any man! Mine eyes have seen the glory of the coming of the Lord!!

It is noteworthy that Obama is not the traditional black revolutionary. He is the “new black man”. Reading his life story, you get the impression that he looks beyond race. Being black is only part of who he is. Franz Fanon spoke of this new man in his advice to the 3rd world revolutionaries:

For Europe, for ourselves and for humanity, comrades, we must make a new start, develop a new way of thinking, and endeavor to create a new man.

As an African, I see a different promise in Obama. I don’t think his administration will especially prioritize Africa or give us extra development aid. He already has quite a job cut out for him fixing America. What I do hope is that he will show the next generation of African leaders the value of the New Man. There are many parallels between the black struggle in America and the African struggle. The Americans have overcome by evolving a new man. We need to borrow a leaf from them and move past the fixation with colonialism and neocolonialism, blaming our present on the crimes of past generations. We need to formulate a plan of the future of our continent that does not involve retribution or righting past wrongs. We need our own messenger of Hope.

Here’s a gem from the Ars mathamatica blog.I don’t think I could put it better if I tried.

You know, mathematical terminology cannot be parodied. Mathematicians have invented groups, semigroups, quasigroups, pseudogroups, and two mostly-unrelated concepts both known as groupoids. They have invented both formal groups and quantum groups, neither of which are kinds of groups. And while the study of groups is a branch of algebra, most groups are not, in fact, algebraic.

Check out the comments for the post

← Previous PageNext Page →