Advent of Code #3 (in JavaScript & Haskell)

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.

Blog

Advent of Code #3 (in JavaScript & Haskell)

Caleb Weeks

Part 1

Part 2

Join Our Newsletter. No Spam, Only the good stuff.

Related