Today's Advent of Code problem is a tough one... On the surface it looks very similar to day one and two, but there is a lot more going on. While I was able to solve day one and two fairly quickly in Excel, I had to jump straight to Haskell and JavaScript to find today's solutions.
Part 1
I won't reiterate the problem, because it is pretty complicated. Our input is an array of binary strings:
input = ["00100", "11110", "10110", "10111","10101",
"01111", "00111", "11100", "10000", "11001", "00010", "01010"]
The first order of business is to turn each binary string into a list of integers. I had to split this into two steps because I was fighting with the Haskell type system.
charArrays :: [[[Char]]]
charArrays = map (map (:"")) input
bitArrays :: [[Int]]
bitArrays = map (map (read :: [Char] -> Int)) charArrays
Then we zip together all the bitArrays to get the total number of ones in each bit position. I'm using foldl1 so that the first value of the input list is used as the initial value.
bitCounts :: [Int]
bitCounts = foldl1 (zipWith (+)) bitArrays
Next we check whether one or zero occurs more frequently for each bit by comparing the count to half of the total input length. The least common is simply the bit reversal of the most common.
mostCommon :: [Int]
mostCommon = map (\number ->
if number > (length input `div` 2) then 1 else 0) bitCounts
leastCommon :: [Int]
leastCommon = map (\number ->
if number == 1 then 0 else 1) mostCommon
To convert the bitArrays into decimal numbers, we reverse the list to start from the right side and fold, keeping track of the power and accumulated total. The power is multiplied by two each iteration, and the current bit multiplied by the current power is added to the accumulator. I tried to figure out how to use foldr instead of foldl, but couldn't get it working.
toDecimal :: [Int] -> Int
toDecimal = fst . foldl (\ (acc, power) x -> (acc + (power * x), power * 2)) (0, 1) . reverse
The finally answer is the most and least common numbers multiplied together.
gamma :: Int
gamma = toDecimal mostCommon
epsilon :: Int
epsilon = toDecimal leastCommon
answer = gamma * epsilon
In JavaScript, we can convert the input into bit arrays in one shot pretty easily:
const bitArrays = input.map((binary) =>
binary.split("").map((char) => parseInt(char))
);
We need to define our own zipWith function prior to reducing to find the totals of each bit position. The reduce function in JavaScript automatically uses the first element if no initial value is provided.
const zipWith = (f, a, b) =>
Array(Math.min(a.length, b.length))
.fill()
.map((_, i) => f(a[i], b[i]));
const bitCounts = bitArrays.reduce((acc, x) =>
zipWith((a, b) => a + b, acc, x)
);
The rest of the solution is very similar to the Haskell implementation.
const mostCommon = bitCounts.map((total) => (total > input.length / 2 ? 1 : 0));
const leastCommon = mostCommon.map((total) => (total === 1 ? 0 : 1));
const toDecimal = (bitArray) =>
bitArray
.reverse()
.reduce(([acc, power], x) => [acc + power * x, power * 2], [0, 1])[0];
const gamma = toDecimal(mostCommon);
const epsilon = toDecimal(leastCommon);
const answer = gamma * epsilon;
Part 2
This part looks similar to the first one, but is drastically different. We start off by creating a helper function which will split a list of bitArrays into two lists depending on whether a given bit is zero or one. In general, this is just a filter function which also returns the values that were rejected from the filter criteria. You can tell we are in wacky land when we pull out array indexing using the !! operator...
splitByBit :: Int -> [[Int]] -> ([[Int]], [[Int]])
splitByBit bit = foldl (\ (ones, zeros) x ->
if x!!bit == 1 then (x:ones, zeros) else (ones, x:zeros)) ([], [])
Using this helper function, we need a recursive function to test out each bit position until we get a single result back for the oxygen generator and CO2 scrubber ratings. Technically, there are situations that are not handled by these functions, but they work according to the problem description.
oxygenGenerator :: Int -> [[Int]] -> Int
oxygenGenerator bit bitArrays
| length ones >= length zeros = if length ones == 1
then toDecimal (head ones)
else oxygenGenerator (bit + 1) ones
| otherwise = if length zeros == 1
then toDecimal (head zeros)
else oxygenGenerator (bit + 1) zeros
where (ones, zeros) = splitByBit bit bitArrays
co2Scrubber :: Int -> [[Int]] -> Int
co2Scrubber bit bitArrays
| length zeros <= length ones = if length zeros == 1
then toDecimal (head zeros)
else co2Scrubber (bit + 1) zeros
| otherwise = if length ones == 1
then toDecimal (head ones)
else co2Scrubber (bit + 1) ones
where (ones, zeros) = splitByBit bit bitArrays
And finally we call our recursive functions with initial conditions to get the final results.
oxygenGeneratorRating :: Int
oxygenGeneratorRating = oxygenGenerator 0 bitArrays
co2ScrubberRating :: Int
co2ScrubberRating = co2Scrubber 0 bitArrays
answer = oxygenGeneratorRating * co2ScrubberRating
Again, this translates relatively easily into JavaScript, so here is the whole thing (minus the stuff we already defined in part 1):
const splitByBit = (bit, array) =>
array.reduce(
([ones, zeros], x) =>
x[bit] === 1 ? [[x, ...ones], zeros] : [ones, [x, ...zeros]],
[[], []]
);
const oxygenGenerator = (bit, bitArrays) => {
[ones, zeros] = splitByBit(bit, bitArrays);
if (ones.length >= zeros.length)
return ones.length === 1
? toDecimal(ones[0])
: oxygenGeneratorRating(bit + 1, ones);
return zeros.length === 1
? toDecimal(zeros[0])
: oxygenGeneratorRating(bit + 1, zeros);
};
const co2Scrubber = (bit, bitArrays) => {
[ones, zeros] = splitByBit(bit, bitArrays);
if (zeros.length <= ones.length)
return zeros.length === 1
? toDecimal(zeros[0])
: co2ScrubberRating(bit + 1, zeros);
return ones.length === 1
? toDecimal(ones[0])
: co2ScrubberRating(bit + 1, ones);
};
const oxygenGeneratorRating = oxygenGenerator(0, bitArrays);
const co2ScrubberRating = co2Scrubber(0, bitArrays);
const answer = oxygenGeneratorRating * co2ScrubberRating;
The biggest struggle I had with this problem was messing with the Haskell types and figuring out the deeply nested conditional logic. I think the conditional logic could be further improved in Haskell through some smart pattern matching.
Top comments (2)
Excellent stuff. This is my favourite series on dev right now.
I'm happy I'm not the only one who thought day 3 was a non-trivial step up in difficulty over day 2.
And that part 1 and 2 are not as similar as you'd first think.
I ended up transposing the input in part one which I think made the logic a lot less nefarious.
I have been consistently impressed with how terse the js/ts versions of these are, especially leveraging the power of es6 features.
Keep up the great work.
If you'd like to see my f# attempt. github.com/tkshill/aoc2021/blob/ma...
Thanks so much Kirk! It is great to know that there is someone reading my posts. I really appreciate you sharing your F# solutions as well. Unfortunately, I did not have time today to do problem #4, but hopefully I can catch up soon.