Learn to Code by Solving Problems by Daniel Zingaro

Author:Daniel Zingaro [Zingaro, Daniel]
Language: eng
Format: azw3, pdf
ISBN: 9781718501331
Publisher: No Starch Press
Published: 2021-06-28T16:00:00+00:00

The Top Level

To begin our design, we focus on the main tasks that we’ll need to solve.

We’ll certainly have to read the input, so that’s our first task.

Now, assume that we’ve read the input. What should we do to determine whether the boxes can be organized? One important thing to do is check each box on its own to make sure that its action figures have their heights in order. For example, suppose that we had the box [18, 20, 4]. This box, with heights out of order, means that we have no chance of organizing all of the boxes. We can’t even organize this one!

So, that’s our second task: determine whether each box, on its own, has its action figures in order. If any of these boxes has its action figures out of order, then we know that the boxes can’t be organized. If all boxes are OK, then we have more to check.

If each box on its own is OK, the next question is whether we can organize all of the boxes. One important observation we can make here is that the only action figures we care about from now on are the ones at the left and right sides of each box. The action figures between these don’t matter anymore.

Consider this example where we have three boxes:

[[9, 13, 14, 17, 25],

[32, 33, 34, 36],

[1, 6]]

The first box starts with an action figure of height 9 and ends with an action figure of height 25. Action figures placed to the left of this box must all have height 9 or less; for example, we can place the third box to the left of this box. Action figures placed to the right of this box must all have height 25 or more; for example, we can place the second box to the right of this box. The action figures of heights 13, 14, and 17 change nothing; they may as well not be there.

That’s our third task then: ignore all action figures except those on the ends of boxes.

Following that third task, we’ll have a list that looks like this:

[[9, 25],

[32, 36],

[1, 6]]

It’s a lot easier to tell whether we can organize these boxes if we first sort them, like this:

[[1, 6],

[9, 25],

[32, 36]]

Now it’s easy to see what the neighboring boxes of a box must be. (We used a similar approach when solving Village Neighborhood in Chapter 5.) So, our fourth task is to sort the boxes.

Our fifth and final task is to determine whether these sorted boxes are organized. They are organized if the heights of action figures are sorted from left to right. The action figures of heights 1, 6, 9, 25, 32, and 36 are appropriately sorted, so the previous boxes can be organized. But consider this example:

[[1, 6],

[9, 50],

[32, 36]]

These boxes can’t be organized because of that huge action figure in the second box. That second box takes up heights 9 to 50; the third box can’t go on the right of the second box because its heights are too small.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.