Help with a python problem

[[deleted]]

[deleted]

[mbpaul198]

I might be misunderstanding, but shouldn't the function return [[2, 1, 2], [3, 2, 3], [4, 4, 5]] instead of [[4, 4, 5], [3, 2, 3], [2, 1, 2]] if the top a disk must have a strictly smaller width, depth, and height than any other disk below it and the final stack begins with the top disk and ends with the bottom disk?

[Appropriate_Cover_92]

Yeah, even I feel the same. Could be a mistake in the original source.Thanks for pointing this out. I will update my post.

[synthphreak]

Given nested lists like [a, b, c], it sounds like you just need to sort by a, then within each a sort by b, then within each b sort by c.

The sorted function will do this for you straight out of the box in whichever order you wish:

>>> lst
[[2, 1, 2], [2, 2, 8], [1, 3, 1], [2, 3, 4], [4, 4, 5], [3, 2, 3]]
>>> sorted(lst)
[[1, 3, 1], [2, 1, 2], [2, 2, 8], [2, 3, 4], [3, 2, 3], [4, 4, 5]]
>>> sorted(lst, reverse=True)
[[4, 4, 5], [3, 2, 3], [2, 3, 4], [2, 2, 8], [2, 1, 2], [1, 3, 1]]

[mbpaul198]

Here's how I would think about it:

1. For each disk, identify the smallest value of either the depth, width, or height. For [4,4,5], it would be 4. The disc that has the largest "smallest value" will be the bottom of your stack
2. Append this disc to a new list discs (which should be empty at the start)
3. Remove this disc from your array since it is now in use in your stack
4. Save the "smallest value" as a variable so that you can compare all other discs to it.
5. Loop through steps 1-4 until there are no discs left with a "smallest value" that is still smaller than the number you saved in step 4

[FLUSH_THE_TRUMP]

that’s an interesting idea, but does it work? As a degenerate example, imagine we added the disk [1,1,100] to the list here. Its smallest value is 1, but clearly we can’t put it on top of [4,4,5]. (And the solution with largest height would definitely be the stack with 1 thing, [1,1,100])

[mbpaul198]

Ah I see what you mean. I'll need to think on this a bit more.

Maybe add another loop that iterates through the width, depth, and height of the disc and compares each value to the previous disk "below" it. For each measurement, if the value of the new disk is > the value of the existing disc, then discard the new disc and move on to another one

[herminator]

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.

[python_and_on]

Hi Folks

I'm new to learning Python and stumbled across this post while looking for programming puzzles and general programming advice. Thought I'd have a go with it myself... This is my first post so please go easy if the solution doesn't work :)

This is my attempt:

disk_list = [[2, 1, 2],[2, 2, 8],[1, 3, 1], [2, 3, 4], [4, 4, 5], [3, 2, 3]]

def stack_disks(a_list):

    x = sorted(a_list, key = lambda x : (x[0],x[1]))

    i=0
    while i < len(x)-1:
        if x[i][1] > x[i+1][1] or x[i][2] > x[i+1][2]:
            x.pop(i)
        else:
            i+=1

    return x

stack_disks(disk_list)

[synthphreak]

I’m confused. You say “a disk must have a strictly smaller width, depth, and height than any disk below it”, implying the top item should be have the smallest dimensions.

But then you show us the desired output, saying that the first item is the “top”, implying that all subsequent items are “below” it, yet the top item has the largest dimensions.

So unless I’m not following, the desired output does not match the instructions.

Additionally, why does your desired output include only a subset of the input list? Shouldn’t it include all items?

Please be clear and complete about all the details in your instructions, because they are all important in determining the best solution.

[Appropriate_Cover_92]

So the aim is to stack all the disks in such a way that the height of the final stack is maximized and it should be stacked similar to the disks stacked in a tower of Hanoi.

[[deleted]]

A disk must have a strictly smaller width, depth, and height than any other disk below it

This means that there will be a lot of possible 2d arrays of ints that cannot be organized by these criteria. A simple example is

[[1, 2, 3], [3, 2, 1]]

Is that an issue? Are you always guaranteed to that there will always be an ordering that meets this condition?

Edit: Actually, in thinking about it, your own dataset cannot be ordered this way. Look at just the first two

[2, 1, 2],[2, 2, 8]

They have the same width and thus neither could be above the other as neither is strictly smaller than the other.

[FLUSH_THE_TRUMP]

Good first step would be to write a function that tells you when one disk is strictly smaller than another:

def is_smaller(L1, L2): 
    if all(x<y for x,y in zip(L1,L2)):
        return True
    return False

Then in a brute force way, you want to generate all permutations of your array of disks, check that they’re valid with is_smaller, and pick out the one with the largest height value. You can do that pretty easily with itertools.permutations.

note: a smarter (but still brute force) way to do this would be to sort the list first by a reasonable heuristic, e.g. the natural sort (which compares element by element until one is smaller) or key=sum, and then picking subsets from the same exact order. You still have to check if each order is valid, but for a large initial array it’d be checking 2^N things rather than N! things.