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

Mocking HttpCookieCollection in HttpRequestBase

When unit testing ASP.NET MVC2 projects the issue of injecting HttpContext is quickly encountered.  There seem to be many different ways / recommendations for mocking HttpContextBase to improve the testability of controllers and their actions.  My investigations into that will probably be a separate blog post in the near future but for now I want to cover something that had me stuck for longer than it probably should have.  That is how to mock non abstract/interfaced classes within HttpRequestBase and HttpResponseBase – namely the HttpCookieCollection class.   The code sample below illustrates how it can be used within a mocked instance of HttpRequestBase.  Cookies can be added / modified within the unit test code prior to being passed into the code being tested.   After it’s been called, using a combination of MOQ’s Verify and NUnit’s Assert it is possible to check how many times the collection is accessed (but you have to include the set up calls) and that the relevant cookies have …

Injecting HttpContextBase into an MVC Controller

It is a shame that when the ASP.NET MVC framework was released they did not think to build IoC support into the infrastructure. All the major components of the MVC engine appear to magically inherit instances of HttpContext and it’s related objects – which can cause no end of problems if you are trying to utilise Unit Testing and IoC. Reading around various articles on the subject just to get around this one problem requires the implementation of several different concepts and you are still left with a work around. The code below, along with the other links referenced in this article is my stab at resolving the issue. There’s probably nothing new here, but it does attempt to relate all the information needed to do this for Castle Windsor. The overview is that all controllers will need to inherit from a base controller, which takes an instance of HttpContext into it’s constructor. It then overrides the property HttpContext in the main controller class, supplying it’s own version…

Problem installing AWS CLI

It never feels like a good start when you're trying to start out with something and the install fails with an obscure error! I was just trying to install the Amazon CLI following the instructions at https://aws.amazon.com/cli/ and ran into the following error when running 'pip install awscli': Collecting awscli Could not find a version that satisfies the requirement awscli (from versions: ) No matching distribution found for awscli I appeared to have a correct version of Python installed (v2.7) and checking "PIP -v" indicated that 9.0.1 was installed. That all seemed to tick the required boxes but digging around a little more I did see that some people had had issues with various versions of PIP so I found / ran the following to upgrade to the latest vesion: curl https://bootstrap.pypa.io/get-pip.py -o get-pip.py python get-pip.py This installed v9.0.3 of PIP which burst into life when I re-ran 'pip install awscli' and everything seems to be ok. Like…