Challenge #3

Part One:
A Cut Above the Rest

The news of your remarkable intelligence spreads quickly through the village, carried by the excited chatter of the mathematicians. Before long, you are approached by the town's flintknapper, Wuru, and brought to his shop. His shop is filled with hand-crafted obsidian spearheads; a collection that is both visually stunning and impressively vast. Even from a distance, you can sense how perfectly sharp they are. Wuru proudly exclaims that they can slice through anything without even touching it, so long as you hold them just a few centimeters away.

You casually remark that such weapons must be incredibly effective in hunting mastodons and saber-tooth cats. Wuru's face flushes and he scowls. You're puzzled by the sudden offense, until you notice movement in the room behind him. To your surprise, two saber-tooth cats are happily tumbling over each other in play.

Realizing your confusion, Wuru softens. He introduces you to his beloved pets, Chia and Lola. As it turns out, this village is vegetarian and the spears that Wuru makes are not for hunting beasts, but instead are used to harpoon fruit from the tops of the tallest trees.

As the big cats romp about, one of them bumps a table and the carefully stacked spearheads scatter into a chaotic jumble. Fortunately, none fall to the floor. With lightning-fast reflexes, Wuru sweeps them into an unordered pile to prevent injury. His skilled hands seem entirely unbothered by the spearhead's razor-sharp edges.

Turning to you, he apologizes for his pets' unruly behavior and starts to guide Chia and Lola into their outdoor enclosure for everyone's safety. In the meantime, he asks if you could help re-stack the spearheads in their correct order. He hands you a list of instructions: complex steps that even he admits he struggles with. Last time, he says, it took months to get them all properly sorted.

Before stepping away, he gives you a special spearhead-flipper, a tool designed to grab and invert an entire stack of spearheads safely, like flipping a stack of pancakes, but far more dangerous.

The instructions read:

  1. Look at the incomplete section of the stack.

    At the start, the incomplete section is taken to be the entire stack. It will reduce in size as you progress.

  2. Find the largest spearhead in the incomplete section.

  3. If the largest spearhead is already at the bottom of the incomplete section, it is already in its final position. Reduce the incomplete section by exactly one and return to Step 1.

  4. Otherwise, if the largest spearhead is not already on top, flip the stack from the top down to that spearhead (inclusive) so the largest spearhead becomes the topmost one.

    This counts as one flip.

  5. Next, flip the entire incomplete section. This moves the largest spearhead from the top to the bottom of the incomplete section, placing it in its final sorted position.

    This is another flip.

  6. The incomplete section is now smaller by exactly one. Repeat this process until the size of the incomplete section reaches zero. At this point, the entire stack is properly ordered.

To further help you along, Wuru grabs a scrap of parchment and, after carefully looking at the pile exactly as it lies, writes down the sizes of the spearheads in their current order. This sequence becomes your puzzle input. The parchment is old and stained with stray markings, but the numbers remain legible, so you can disregard the markings.

For example:

If your parchment shows the following stack: -3 -
 - -
2 -
--4
  -
1  -

3
2
4
1
3
2
4
1
3
2
4
1
4
2
3
1
4
2
3
1
1
3
2
4
  • Find the largest number: 4
  • Flip from the top down to 4.
  • flips: 1
  • Flip the entire incomplete section.
  • flips: 2
  • 4 is now in its correct position.
1
3
2
4
1
3
2
4
1
3
2
4
3
1
2
4
3
1
2
4
2
1
3
4
  • Find the largest number: 3
  • Flip from the top down to 3.
  • flips: 3
  • Flip the entire incomplete section.
  • flips: 4
  • 3 and 4 are now in their correct positions.
2
1
3
4
2
1
3
4
→
2
1
3
4
1
2
3
4
1
2
3
4
  • Find the largest number: 2
  • 2 is already on top, so no flip is necessary.
  • flips: still 4
  • Flip the entire incomplete section.
  • flips: 5
  • 2, 3, and 4 are now in their correct positions.
  • 1 spearhead remains at the top so the sorting is complete.

The total number of flips to correctly stack these spearheads is 5.

Here is your unordered stack of spearheads:

[ click to get input ]