Advent of Code #3 (in JavaScript & Haskell)
Tags: functional, programming, javascript, haskell
Published: 2021-12-04 05:45:15

---
series: Advent of Code 2021 (in JavaScript & Haskell)
---

Today's [Advent of Code](https://adventofcode.com/2021/day/3) 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:
```haskell
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.
```haskell
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.
```haskell
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.
```haskell
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.
```haskell
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.
```haskell
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:
```js
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.
```js
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.
```js
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...
```haskell
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.
```haskell
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.
```haskell
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):
```js
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.