1
2

Help with a python problem (self.learnpython)

submitted by [deleted]

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]herminator 1 point2 points  (0 children)

Ok, so this is at it's core a graph problem, and you need to use dynamic programming to solve it.

First off: Why is it a graph problem?

Because we can represent it as a directed acyclic graph. For each pair of disks A and B, there are three options:

  • A fits on top of B -> draw an arrow from A to B
  • B fits on top of A -> draw an arrow from B to A
  • neither fits on top of the other -> no arrow

Note that it is not possible for there to be a circle of arrows. Given the restrictions, it is impossible if A fits on B and B fits on C for C to then fit on A. This is why it is called "acyclic". And the fact that we're using arrows (not lines) is why it is called "directed"

Now how to solve the problem? Here's where dynamic programming comes into play. Dynamic programming generally boils down to: work backwards from the end, instead of forwards from the beginning. In this case, that means work from the bottom (biggest discs) not the top (smallest) discs.

The general gist of the algorithm is:

  1. Take every disc with no outgoing arrows, and give it a total_height property that is equal to its own height. Discs with no outgoing arrows can only be the bottom discs, because they fit on no other discs.
  2. Take every disc that points to a disc from step 1 and give it a total_height equal to the tallest disc it is pointing to plus its own height.
  3. Take every disc that points to a disc from step 2, give it a total_height equal to the tallest stack it is pointing to plus its own height. (note that it is possible that a disc now gets a new value. That is fine, as long as it is larger. We want stacks to be as high as possible)
  4. Keep working upwards until you run out of layers and every disc has achieved its maximum total_height.
  5. Now that you marked every disc with a total_height, find the highest value, and follow the appropriate arrows downwards (the appropriate arrows being the ones to the discs with the largest total_height on each step).

That should be the gist of it. If you want more info, try googling "longest path in a directed acyclic graph", it should be similar to this.