AoC: Day 05

The Problem

We need to convert a string that encodes the seat row and column to a seat number. In part 2, we have to find the missing seat number in the input data

My Solution

I came to AoC after a bit of a break and just wanted to get it done in time. The approach I took followed the illustration in the problem for the conversion (excuses, excuses, excuses…). So I actually walked through the string, and if the character is an ‘F’ I did this, and if it’s a ‘B’ I did that. Yes, I’m embarrassed (see below). To add to my embarrassment, I implemented two functions for recovering the row and column numbers, instead of just one. My Part 2 was the most idiotic, brute-force, unelegant solution you can imagine!

Implementation

• This is not something I would do, but highlighting out of interest. A few solutions actually created a list of 128 (or 8, in case of columns) populated with the indices, and chopped it up.
• Python string has a replace function and a maketrans function so it’s easy to replace, say, ‘F’ with a ‘0’ and ‘B’ with a ‘1’…. and then interpret this as an integer base 2! Why would you want to do this? see the note below.
• A neat implementation uses recursion and what is essentially a binary search on the indices but keyed on the string

Algorithm

• My ‘doh!’ moment was not recognizing that the string in its entirety was a binary representation of the desired output! Including the combination of rows and columns!!

Part 2 had multiple approaches:

• Put all the values in a set and do a set difference with the entire range
• Add all the numbers up and subtract from the arithmetic sum
• Similar to the above, but use XOR on the full range
• Simulate: Choose a seat and check if it’s occupied. If yes, choose the next seat. The expected number of times to do this is the harmonic series and converges very rapidly.

I really like the last approach, and would not have thought of it. I should have recognized the binary encoding and the summing, so am kicking myself.

Oh well, I live and learn!