I’m in the early stages of learning Python – and by early I mean 3 days (about 5 hours total) in. My previous experience with Python was hearing people complain about (or mock) indent based scoping. To learn Python I’ve choose to work through some of the Project Euler problems. This post is specifically about Problem 18 (Find the maximum sum travelling from the top of the triangle to the base. Problem 67 is the same except that it’s dataset is significantly larger so a brute force solution will not work.

Let’s start by looking at our sample graph (this is the sample from the problem website):

tree1

And we want to find the most expensive path from the root (3) to the bottom row (8 5 9 3).

In this example the maximum path has the value 23

tree2

On a small triangle (graph) like this we can just see the answer – but how would we do it with 16 or 100 rows (problems 18 and 67, respectively)?

We could enumerate every path – in the sample above that is 8 potential paths (the number of paths is s^(n-1) where n is the number of rows in the triangle). But in a 100 row triangle that is 2^99 paths – forget about it.

What we can do I is realize that we don’t need to know every path – we only need to the know the most expensive (largest weight) paths. With that in mind we can avoid searching any paths. Let’s talk through this.

We start on the root node, 3. 3 has no parents so it’s overall weight is it’s value: 3.

On to the next row. The first node, 7, has a single parent: 3. So it’s overall weight is (7+3) = 10. The node 4 has an overall weight of (4+3) = 7. Now don’t go thinking “Ok, we can ignore 4!” – you can’t.

Now let’s step back and realize that between every connected pair of nodes there exists one path whose overall weight is greater than all the other paths (maybe there are some that are equal – but we don’t need to worry about that since it doesn’t affect the outcome). The maximal path weight for any given node depends on how many parents it has.

  • No parents – the node’s value is it’s maximal path weight (this is the root node, 3)
  • One parent – the node’s maximal path weight is the maximal weight of it’s parent + it’s value (e.g, 7 + 3)
  • Two parents – the node’s maximal path weight is greater of it’s parent’s maximal weights + it’s value (we’ll see this in a minute)

So far we’ve seen 3 nodes. One of them had no parents (3) and two had one parent (7 and 4). So for those three nodes we know their maximal path weight. Since we know their weight we never to calculate those nodes again. So our tree can now be thought of this like this:

tree3

Moving on to the third row – let’s apply those maximal path rules and see the new values:

tree4

And now we can finish the third row …

tree5

And there you have it – the maximal path value of each node is known.

So what about code?

Well – I could print the code but that would rob you of the opportunity to solve this problem on your own. My solution runs in about 30 milliseconds on the 100 row triangle – not too bad when you consider the brute force approach is estimated to take billions of years (see the explanation at the problem 67 page).

Join the conversation! 10 Comments

  1. sir,i am on a project of AI,and planned to do the Dot and box game in C#.i got your code at
    https://github.com/bubbafat/ but icouldnot understanding its AI algorithm.also i couldnot find its description there.

    i am an undergraduate engineering student and trying ai on dot and box game so please give me some information about the code in brief. I would be very grateful for your help.I only need to understand the AI
    algorithm and how it works. i have made my own interface but couldnot get to how to embedded ai on it.

    please help me……… my email address is [email protected].

  2. laxmi – I never really blogged about it.

    There really isn’t any AI. Look in ComputerPlayer.cs to see the three modes: random, high score (maybe best) and low score (obviously bad) move. High and low score have to do with the output of GameBoard::SpeculateMove – basically it determines the score of a move based on whether it completes a square or leaves the square in a state that the next player can fill it.

    There is nothing complex – it’s just picking moves based on simple heuristics. If you need a “real” AI then this probably isn’t your best example. Please bear in mind it’s been 7 or 8 years since I wrote this and it was a throw-away weekend project.

  3. Thank you so much for your excellent explanation. I was going bottom-up and therefore had to store the whole triangle before I could start processing. With your top-down approach, I can probably have a much smaller memory footprint.

  4. Thanks! I’m glad it was helpful.

  5. sigh. I can’t seem to rescind the memory footprint. Here’s my code:


    import java.util.*;
    import java.nio.file.Paths;
    import java.io.IOException;

    public class Main {
    public static void main(String... vargs) throws IOException {
    String triangleFileName = vargs[0];
    Scanner fileScanner = new Scanner(Paths.get(triangleFileName));
    Scanner lineScanner;
    int[] parentLevel = { Integer.parseInt(fileScanner.nextLine().trim()) };
    int[] childLevel;
    int nChildrenInLevel = 1;
    int childIndex, maxParentWeight, childWeight;
    int heaviestPathWeight = 0;
    while (fileScanner.hasNextLine()) {
    lineScanner = new Scanner(fileScanner.nextLine());
    childLevel = new int[++nChildrenInLevel];
    childIndex = 0;
    while (lineScanner.hasNextInt()) {
    if (childIndex == 0) {
    maxParentWeight = parentLevel[0];
    } else if (childIndex == nChildrenInLevel - 1) {
    maxParentWeight = parentLevel[childIndex - 1];
    } else {
    maxParentWeight = Math.max(parentLevel[childIndex - 1], parentLevel[childIndex]);
    }
    childWeight = lineScanner.nextInt();
    childLevel[childIndex] = maxParentWeight + childWeight;
    heaviestPathWeight = Math.max(heaviestPathWeight, childLevel[childIndex]);
    childIndex++;
    }
    parentLevel = childLevel;
    lineScanner.close();
    System.gc();
    }
    fileScanner.close();
    System.out.println(heaviestPathWeight);
    System.exit(0);
    }
    }

    If anyone has any idea how to increase memory efficiency, please let me know.

  6. get rid of buffering (e.g., no scanners), java collections, wrappers. in their place, use file reader (read char by char), roll your own linked list and use primitives. went from 36 to 6 MB. 🙂

  7. using the strategy described in this post, I was also able to reconstruct the actual maximum weight path by simply constructing linked lists connecting children to their cummulatively heavier parent.

  8. Robert, I don’t quite understand your diagram after “And now we can finish the third row”; shouldn’t that “17” be a “19”. Otherwise, it all makes perfect sense to me.

  9. You are correct, it should be a 19. I don’t always math so good.

  10. Thanks for taking the time to demonstrate this method, it is quite fascinating!

Comments are closed.

Category

Programming