Puzzle 3 — Presents go Pop!

< APUG Nov 2024

Part 1

Finally, Santa and the chip-filled elves reach the Aberdeen Python User Group “Ho, ho, ho! Merry Christmas!” laughs Santa taking the presents out of his jolly Christmas present sack.

“Now we took a few more presents than we need.” Santa says, “Let's pick the eight highest values presents.”

Santa's elves lay out the gifts in a row. “Here you go Santa, I laid them out in a row just like they're wired up!” said one of the elves.

“Wired up?” Santa asked confused, looking at the gifts, he notices wires between each adjacent gift, “Ho ho no! That's not right at all!”

Santa's Chief Technology Elf (CTE) explains, “It seems the Aberdeen R programmers have been messing with the Python programmers' presents again,” he says, examining the wires, “yup, seems each adjacent pair of presents is wired up to a small bomb!”

“A bomb?” Santa gasps!

The CTE fiddles around with the wires, “I think we can safely open any present, but, not if they are adjacent to one another.” he explains

Santa and the elves think for a while.

“Okay, let's simply start by opening the most valuable present...” Santa begins, “then the next most valuable present, assuming it's safe, and so on.”

We need to open the most valuable present available, then the two next to it become unavailable (they are still there, but we won't touch them), and repeat until we have 8 presents. If at any time the next most valuable present is unavailable, we skip over it. What is the total value of the 8 presents we get with this strategy?

Example Input File

Let's look at a small example list:

Santa needs 8 presents from the real input file, but for the example, we will open only four presents, because it's a small example!

First, we open the most valuable present (100), this means the present next to it becomes unavailable.

The next most valuable present is 70, let's open that. This means the two presents next to it become unavailable.

The next most valuable presents are 60 and 50, but don't touch them! They'll go boom!

The next most valuable present is 25, let's open that. This means the two presents next to it become unavailable. Well, actually, one of them (60) is already marked as unavailable, no need to mark it twice. So we're just marking one new present (50) unavailable this time.

Using our strategy the next present is 20.

Since this is a small example, we are only taking four presents, not eight.

Our total is... 100 + 70 + 25 + 20 = 215

So using our strategy to open 4 presents from the small example, we get 215.

Real Input File

To see the real list of presents, download input3.txt

Using the same strategy given above, but remember to open eight presents, not four, what is the total present value?

Part 2

It seems the Python programmers aren't happy and don't want to open the presents. We're not sure why. Maybe they don't want a sub-optimal set of presents.

“Hmm, maybe there is a better strategy we can figure out.” Santa says thinking, “How can we get the maximum total value of eight presents?” shaking his head again.

Example Input File

Our total is... 20 + 60 + 50 + 100 = 230

Which is higher than our earlier strategy which gave us 215. In fact, this is the best possible total we can get! There is no higher total we can get by opening 4 presents without opening two adjacent presents and blowing up!

“That's wonderful!” Santa laughs, “What strategy did you use?” he asked.

The Chief Technology Elf looks proud, “Really easy, Santa, I just...”

At that moment a seagull swoops in through the window and carries off the CTE!

“Well, that's indeed less wonderful. I need to assign a new CTE again next year.” Santa sighs, “Without the CTE, how will we figure out the optimum set of presents?”

Real Input File

Sadly, the CTE isn't around to tell us the strategy for solving Part 2.

What is the maximum possible total we can get for eight presents laid out according to our real input file without blowing up?

The real list of presents is the same file we used for Part 1: input3.txt