Skip to main content

Project Euler – Problems 18 & 67

The challenge set by problem 18 was

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.

A 15 row triangle was then supplied for which the program must determine the corresponding maximum value taking a similar path through the data.  A foot note to the problem highlighted that due to the “limited” number of paths for this puzzle it could be solved using brute force determining the total for each path through the triangle and selecting the maximum total returned.  However a link to problem 67 was provided which exactly the same problem, but this time the data was for a hundred row triangle. For that problem a brute force attack could not be used as the number of possible routes meant that:

If you could check one trillion routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

In researching possible approaches I came across an Excel solution by Tushar Metha.  This really simplified the approach, turning the data upside down and starting on the last row, taking two adjacent cells (“c1” and “c2”) and their corresponding cell on the row below “c3” (remember triangle has been turned upside down).  The two routes for that subset were determined and the maximum value was placed in cell “c3”.  In the example, 5 is “c1”, 9 is “c2” and 4 is “c3”.  So “c1 + c3” = 9 whilst “c2 +c3” = 13, so the contents of c3 is replaced with 13.  This process is repeated for the entire row. 

5   9

  4

Once the entire row has processed you “move” down a row and repeat the process.  For problem 67, instead of taking 20 billion years it takes less than a second - so quite a nice time saving over the brute force approach.

Source code: VS2010 C# Solution

Problem Stats:

  • 23 out of 299 problems solved (2 more until first level!)
  • No Ranking (based on problems 275 to 299)
del.icio.us Tags: ,

Comments

Popular posts from this blog

Why do my Android Notification only appear in the status bar?

I'm definitely getting back into Android development, I'm remembering that feeling of 'Surely this should be easier than this!'. All I wanted to do was to schedule a local notification which behaved similar to a push notification pop-up. That is, as well as showing the small icon in the status bar I wanted it to pop up on screen to notify the end user. All seems fairly easily, I found this code for how to schedule a notification. That all worked perfectly, apart from the notification would only appear in the status bar. Searching around I found loads of different answers / solutions, mostly all saying the same thing:It only worked if you used 'NotificationCompat.Builder' in place of 'Notification.Builder', orYou had to set the priority to 'NotificationCompat.PRIORITY_HIGH'As usually happens, none of these solutions worked for me until I added in the missing piece of the jigsaw:- '.setDefaults(Notification.DEFAULT_ALL)'. For me this…

Do "Task Hours" add anything in Scrum (Agile)?

What do task hours add to the overall process in scrum?This was a question that has arisen from all team members in both instances that I've helped teams switch over to scrum. The benefits of artifacts like the comparative story point estimation, the 2 week sprints, stand-ups and the end of sprint demo have been self evident to the team, but as one I think every team member has expressed dismay when it comes to task planning and estimating each task in hours. Left unchecked there is a natural tendency for people to actually begin to dread the start of each sprint purely due to the task planning session.In my current role we've been lucky to investigate this further as a team.The team sat down to discuss the problems it was experiencing with estimating tasks in hours and the following common themes appeared:It is hard: Maybe it shouldn't be, but time estimation is hard! Story points are comparative and abstracted making them easier to determine, but time estimate is gen…

IPhone hangs when running from XCode

I've had this happen a couple of times now and the first time was a little worrying that I'd bricked my iPhone. Basically I was running an application on my phone via XCode and when rebuilding an updated version it failed with a "busy" error message. Stopping XCode and unconnecting my phone had no effect, the phone was stuck displaying the loading screen of the application and wouldn't respond to any key commands. To fix you have to hard reboot, holding the power and home button until the phone reboots - doesn't lose any of the data you have on your phone (a concern the first time I did it).