Advent of Code - Day 22

You will perhaps notice we’ve skipped over Day 21 straight to Day 22. Was it Penn State winning their first ever playoff game? Was it the Tennessee Volunteers not belonging in the playoffs? Sadly, neither of those were the answer. The straight up answer is…I have not even solved Problem 1 yet. So after a day of struggling, and watching football, and wrenching on the Miata, we move on to Day 22. Will today have the same heartache in store for me? Well, I’ll give you a hint, I’ve written an article…

Problem 1

We’ve been transported into the jungle, and before anyone realizes it, a monkey steals the device that gets us around from place to place. Guess who gets to go looking for the device while the historians continue their search?

Our scofflaw monkey will trade for the device, but for an EXTREMELY high number of bananas, seeing as we don’t currently have any, we’re going to have to go buy some so we can eventually make it back to the North Pole. Apparently, jungle hiding spots are the hot thing on the market today, and just your luck, you know where plenty are. If we sell enough hiding spots, we should be able to get enough bananas and get our device back. While the prices buyers offer seem random, a more careful examination reveals they are only pseudorandom, so if we can figure out the secret to how they pick prices, we can sell at just the right time. One of the historians lets us know that, the buyers produce a sequence of secret numbers wherein, each secret is derived from the previous secret, evolving into the next sequence as follows;

• Calculate the result of multiplying the secret number by 64. Then, mix this result into the secret number. Finally, prune the secret number.
• Calculate the result of dividing the secret number by 32. Round the result down to the nearest integer. Then, mix this result into the secret number.
• Finally, prune the secret number.
• Calculate the result of multiplying the secret number by 2048. Then, mix this result into the secret number. Finally, prune the secret number.

Breaking down our problem statement for the challenge today, we can identify the following;

• Input: list of the initial secret number for each buyer in the market
• Output: the sum of the 2,000th secret generated by each buyer
• Constraint: we must perform specific operations to generate each new secret number and all calculations should be done using integer arithmetic

With these considerations in mind, we can develop the following approach in our attempt to solve this problem;

1. Read our input file and parse the initial secret numbers
2. Build functions that perform the mix, prune and generate next secret operations
3. Generate 2,000 new secret’s for each buyer
4. Sum the 2,000th secret for all buyers

The biggest issue I had was using the wrong input file, which happened to have hex code in it, or rather, the interpreter believed it did because of the ‘A’ in each value in the input. Perhaps, amateurishly, it took me a bit to realize that my code was calling the wrong file, despite some of the hair I ripped out of my head searching the file for hex code that wasn’t in there. Once I was able to move on from that however, it really was just a matter of iterating on my functions that performed the number generation, for this I used bitwise operations. Given how Day 21 went, it was nice to solve a problem again, even if I did have to work for it.

Problem 2

We realize something as we watch the bidding. The secret numbers aren’t the prices a buyer is offering, they are just offering the ones digit of each of their secret numbers. For example, if a buyer starts with a secret number of ‘123’, the price they would offer would be ‘3’. At the present moment though, we cannot speak directly with buyers, and have asked a monkey to speak on our behalf, but the monkey only knows how to decide to sell by looking at changes in price. They are specifically for a sequence of four consecutive changes in price, then sell when they see it.

We need to instruct our interpreter to make sure they sell at the highest point of the sequence of numbers in an effort to maximize our profits. With each buyer only wanting one hiding spot, we need to be careful about how we do this. Once again, we have 2,000 price changes within which a sequence can occur. What is the best sequence to tell the monkey to sell at to get us the most bananas possible. What is the most bananas we can get?

Breaking down our problem statement for the challenge today, we can identify the following;

• Input: the same list of the initial secret number for each buyer in the market from Problem 1
• Output: the maximum number of bananas we can get
• Constraints: we are only interested in the last digit of each number, as with Problem 1, we need to generate 2,000 secret numbers for each buyer, we can only give one sequence of four price changes

With these considerations in mind, we can develop the following approach in our attempt to solve this problem;

1. Read our input file and parse the initial secret numbers just as in problem 1
2. Reuse our function from Problem 1 to generate the secret numbers
3. Calculate price changes
4. Generate possible sequences of four price changes, calculating how many bananas we would earn
5. Identify the sequence that gives us the maximum number of bananas and return that number

Problem 2 allowed us to start with a lot of what we used on Problem 1, and adapt it to fit here. While I still don’t fully understand the why, I struggled to get the right answer for about two hours. I was solving just a bit low, in fact I was only eight off the correct answer. With some Google-foo, and a bit of experimentation I was finally able to solve it, my solution using defaultdict to count the bananas, a set to track our price changes per buyer and list comprehension to calculate our price change sequences.

Ultimately, Day 22 proved a bit easier than Day 21, which like Bruno we may not talk about for awhile. Today’s challenge involved starting with an initial value and generating a series of numbers based on that. In today’s challenge we used strategies like bitwise operators to generate our secret numbers, which offer speed and efficiency over standard mathematic operations. While both problems had us thinking about efficiently handling the data we created, in Problem 2 we had to be even more careful as we were dealing with more data, and being efficient with how we stored and processed it helped us overall in solving it quicker. Now, for those wondering if Day 21 will just be lost to time? No, it won’t. Much like Problem 2 on Day 15, I’ll come back after this year’s Advent of Code is wrapped up for another attempt at solving those. Until tomorrow friends!