Project Euler: Inaugural meeting
4 June 2012, by Jamie Humphries
Last Wednesday, Softwire had our first Project Euler evening. After a day’s work writing code, we got together to socialise… and write some more code! But the evening shifted our focus from real-world programming problems to the abstract world of mathematics.
Like many others at Softwire, my background is in mathematics (the queen of all subjects). Until about a year ago I had never even considered a job in computer programming, but then I came across ProjectEuler.net.
Project Euler is a fantastic website that provides hundreds of puzzles and problems that require a blend of mathematics and computing to solve. After I tried a few of the problems I was hooked on programming, eventually leading me to apply to Softwire.
Since I owed my career choice to the website, I thought it was worth asking around the office to see if anyone else was interested in getting together to tackle a few problems. This led to the first meeting of the Softwire Eulerians society on Wednesday night.
We focused our efforts on five problems centred around finding the maximum or minimum paths through different grids of numbers. If you want to give them a go for yourself they were problems 18, 67, 81, 82 and 83.
The first of these could be solved by ‘brute-force’, simply crunching through every path and choosing the one which gave the maximum result. However using the same tactic on the next problem yielded a program that would have taken twenty billion years to run, so we sought a more elegant solution!
Having discussed possible approaches as a group we then broke off to code out the problem alone or in pairs. In the end the best solutions were written in five or six lines of code and took only a few milliseconds to run – much better! You can see one such solution at the end of this blog.
A key draw to the event was the opportunity for personal development, which played a central role in the evening. Many of us took the opportunity to try out different programming languages including Ruby, Python and Scala. Programming in pairs and comparing code also gave us a perfect opportunity to learn from others’ expertise.
Overall it was a very successful evening and we plan to make it a regular event on the Softwire calendar. If you like the sound of it, why not try Project Euler for yourself? I’m certainly glad that I did! You can register for a Project Euler account here.
As we continue with these events, more blogs will follow to examine interesting bits of code that emerge. For now I leave you with a small taster in the form of a solution for problem 67 written in Python (if you want to try the problems for yourself, look away now!).
# Read triangle.txt file into local string. triangleText = open("triangle.txt").read().strip() # Now model the triangle as an array of arrays ('triangle'). # Each array represents a row of numbers from the problem triangle. triangle = [[int(x) for x in row.strip().split(' ')] for row in triangleText.split('n')] # Start from the second row from bottom and work upwards (this is the key idea!). # Overwrite each value with the maximum possible path value to that point. for row in range(len(triangle) - 2, -1, -1): for i in range(0, len(triangle[row])): triangle[row][i] += max(triangle[row + 1][i], triangle[row + 1][i + 1]) # The first entry will now be the maximum path value from the bottom row to the top. print(triangle) # Answer for problem 67 = 7273