AoC 2021 Day 03: Binary Diagnostic

Day 3 - Advent of Code 2021. adventofcode.com . Accessed Feb 23, 2022.

Problem Description

Part One

The submarine has been making some odd creaking noises, so you ask it to produce a diagnostic report just in case.

The diagnostic report (your puzzle input) consists of a list of binary numbers which, when decoded properly, can tell you many useful things about the conditions of the submarine. The first parameter to check is the power consumption.

You need to use the binary numbers in the diagnostic report to generate two new binary numbers (called the gamma rate and the epsilon rate). The power consumption can then be found by multiplying the gamma rate by the epsilon rate.

Each bit in the gamma rate can be determined by finding the most common bit in the corresponding position of all numbers in the diagnostic report.

The epsilon rate is calculated in a similar way; rather than use the most common bit, the least common bit from each position is used.

Use the binary numbers in your diagnostic report to calculate the gamma rate and epsilon rate, then multiply them together. What is the power consumption of the submarine? (Be sure to represent your answer in decimal, not binary.)

I don’t see a fault in part 1. I anticipate that part II will involve more bit manipulation in the name of getting more measurements beyond power consumption. Update: That guess was correct.

Part Two

Next, you should verify the life support rating, which can determined by multiplying the oxygen generator rating by the CO2 scrubber rating.

Both the oxygen generator rating and the CO2 scrubber rating are values that can be found on your diagnostic report - finding them is the tricky part. Both values are located using a similar process that involves filtering out values until one remains. Before searching for either rating value, start with the full list of binary numbers from your diagnostic report and consider just the first bit of those numbers. Then:

Keep only numbers selected by the bit criteria for the type of rating value for which you are searching. Discard numbers which do not match the bit criteria.
If you only have one number left, stop; this is the rating value for which you are searching.
Otherwise, repeat the process, considering the next bit to the right.

The bit criteria depends on which type of rating value you want to find:

To find oxygen generator rating, determine the most common value (0 or 1) in the current bit position, and only keep the numbers with that bit in that position. If 0 and 1 are equally common, keep values with a 1 in the position being considered.
To find CO2 scrubber rating, determine the least common value (0 or 1) in the current bit position, and only keep the numbers with that bit in that position. If 0 and 1 are equally common, keep values with a 0 in the position being considered.

Use the binary numbers in your diagnostic report to calculate the oxygen generator rating and CO2 scrubber rating, then multiply then together. What is the life support rating of the submarine? (Be sure to represent your answer in decimal, not binary.)

My Solution

{-# LANGUAGE RecordWildCards #-}
{-# OPTIONS_GHC -Wall #-}

module BinaryDiagnostic.BinaryDiagnostic
  ( BinaryDiagnostics (..),
    powerConsumption,
    lifeSupportRating,
  )
where

import Control.DeepSeq (NFData, rnf)
import Data.Bits (Bits (testBit))

-- Without the underscore prefix, I need to add `diagWidth` and `diagNums` to the
-- export list to avoid `Wunused-top-binds` [1]. The field names share the top
-- level namespace with ordinary variables and classes. [2] That's kinda
-- inconvenient.
--
-- [1]: https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/using-warnings.html?highlight=unused-top-binds#ghc-flag--Wunused-top-binds
-- [2]: https://www.haskell.org/tutorial/moretypes.html#sect6.2
data BinaryDiagnostics = BinaryDiagnostics {diagWidth :: Int, diagNums :: [Int]}

-- For the `($!!)` operator to work on `BinaryDiagnostics`, we need to be an
-- instance of `NFData`. [1] ([2] for syntax)
--
-- [1]: https://hackage.haskell.org/package/deepseq-1.4.6.1/docs/Control-DeepSeq.html#t:NFData
-- [2]: https://stackoverflow.com/a/31478918/7812406
instance NFData BinaryDiagnostics where
  rnf BinaryDiagnostics {..} = rnf diagWidth `seq` rnf diagNums

-- | `toBitList n b` returns a `[Int]` representing the b-least significant
-- | bits of `n`, e.g. `toBitList 22 5 == [1, 0, 1, 1, 0]`.
toBitList :: Int -> Int -> [Int]
toBitList n numBits =
  map (\i -> if testBit n i then 1 else 0) [(numBits -1), (numBits -2) .. 0]

-- | `fromBitList ds` returns the `Int` formed when `ds` is treated like a bit
-- | representation of an integer, e.g. `fromBitList [1, 0, 1, 1, 0] == 22`.
fromBitList :: [Int] -> Int
fromBitList ds = fst $ foldr f (0, 1) ds
  where
    f d (s, powerOf2) = (s + powerOf2 * d, powerOf2 * 2)

-- | Flips any `0` to `1` and anything else to `0`. Assumes the input `[Int]` is
-- | just zeros and ones.
flipZerosAndOnes :: [Int] -> [Int]
flipZerosAndOnes = map (\num -> if num == 0 then 1 else 0)

-- | `bitFrequencies numBits nums` returns an `[Int]` of size `numBits` where
-- | the i'th element encodes the relative frequency of the bit at position
-- | `numBits - i`.
bitFrequencies :: Int -> [Int] -> [Int]
bitFrequencies numBits = foldr updateCumulativeFrequencies (replicate numBits 0)
  where
    zerosToNegativeOnes :: Int -> Int
    zerosToNegativeOnes i = if i == 0 then -1 else i

    updateCumulativeFrequencies :: Int -> [Int] -> [Int]
    updateCumulativeFrequencies num cumulativeBitFrequencies =
      zipWith
        (+)
        cumulativeBitFrequencies
        ( map
            zerosToNegativeOnes
            ( toBitList num numBits
            )
        )

-- | Convert frequency values to either 0 or 1 depending on whether the value
-- | is negative or positive. In case the value is zero, `tieValue` is used.
frequenciesToZeroOne :: Int -> [Int] -> [Int]
frequenciesToZeroOne tieValue = map f
  where
    f :: Int -> Int
    f freq
      | freq < 0 = 0
      | freq > 0 = 1
      | otherwise = tieValue

type BitFrequencySummarizer = Int -> [Int] -> [Int]

-- | `majorityBits numBits tieValue nums` returns an `[Int]` where the element
-- at index `i` is the most common bit at position `i`. In case of a tie,
-- `tieBreaker` is placed into `i`.
majorityBits :: BitFrequencySummarizer
majorityBits numBits nums =
  frequenciesToZeroOne 1 (bitFrequencies numBits nums)

-- | `majorityBits numBits tieValue nums` returns an `[Int]` where the element
-- at index `i` is the least common bit at position `i`. In case of a tie,
-- `tieBreaker` is placed into `i`.
minorityBits :: BitFrequencySummarizer
minorityBits numBits nums =
  frequenciesToZeroOne 0 (map (* (-1)) (bitFrequencies numBits nums))

-- The BinaryLiterals language extension adds syntactic sugar for `0b11001001`
-- [1]. But I didn't end up using binary representation. `Data.Bits` provides
-- utilities for working with `Int`, so why not? [2]
--
-- [1]: https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/binary_literals.html
-- [2]: https://hackage.haskell.org/package/base-4.16.0.0/docs/Data-Bits.html

-- | Solution for Advent of Code Day 3: Part I.
powerConsumption :: BinaryDiagnostics -> Int
powerConsumption BinaryDiagnostics {..} =
  let majorities = majorityBits diagWidth diagNums
      gammaRate = fromBitList majorities
      epsilonRate = fromBitList (flipZerosAndOnes majorities)
   in gammaRate * epsilonRate

-- | `lastNumStanding nums width f positionToCheck` recursively finds an `Int`
-- | that matches the rules of AoC Day 3: Part II.
lastNumStanding :: [Int] -> Int -> BitFrequencySummarizer -> Int -> Int
lastNumStanding [] _ _ _ = 0
lastNumStanding [x] _ _ _ = x
lastNumStanding nums width f positionToCheck =
  let expectedValues = f width nums
      shouldBeSet = (expectedValues !! positionToCheck) == 1 -- (*/_＼)
      bitIndex = length expectedValues - positionToCheck - 1
      matchingNums = filter (\n -> testBit n bitIndex == shouldBeSet) nums
   in if null matchingNums
        then last nums
        else lastNumStanding matchingNums width f (positionToCheck + 1)

-- | Solution for Advent of Code Day 3: Part II.
lifeSupportRating :: BinaryDiagnostics -> Int
lifeSupportRating BinaryDiagnostics {..} =
  -- Partial application allows us to pass less than the full number of args to
  -- a function that takes multiple arguments.
  --
  -- [1]: https://wiki.haskell.org/Partial_application
  let f = lastNumStanding diagNums diagWidth
   in f majorityBits 0 * f minorityBits 0

Learning from Others' Solutions

Potpourri

Although I didn’t find a way to declare a type for a [Int] whose size if fixed after reading an input file, it would have still been more readable to have something like type Bits = [Int], as shown in ’s code.

Computing Most Common and Least Common Bits

My majorityBits and minorityBits (should have been more aptly named mostCommonBits and leastCommonBits) have a lot going in them.

has a more elegant implementation which shows a deeper understanding of math:

-- The type of `(1 -)` is `Num a => a -> a`. Huh! I can rationalize it
-- as applying eta reduction to `f x = 1 - x`.

invertBinary :: Bits -> Bits
invertBinary = map (1 -)

-- `foldl1 (zipWith (+)) bits` sums up all the bits at a given position.
--
-- If the sum at position `i` is greater than N/2, then we can infer
-- that 1 is more common than 0 at position `i`, and vice-versa if less
-- than N/2. There is a tie if the sum is exactly N/2.
--
-- `(`div` N) . (* 2)` multiplies a number by 2 and then does integer
-- division by N. That is a nifty way of avoiding the N/2 which may not
-- be an integer.

mostCommonBits :: [Bits] -> Bits
mostCommonBits bits = map ((`div` length bits) . (* 2))
                    $ foldl1 (zipWith (+)) bits

leastCommonBits :: [Bits] -> Bits
leastCommonBits = invertBinary . mostCommon

… The functions used by did not occur to me at all. Upon reading the problem description, I had an idea of how I’d go about it, and the only unknowns were translating my plan into valid Haskell. I should spend more time thinking through my approach before I rush into coding it.

Several folks in use when calculating mostCommonBits. This is quite convenient as the data for the i-th bit position is all in the same array!

Structure of the Solution to Part II

The recursive nature gave me problems. I wonder how others did it. My approach was:

lastNumStanding :: [Int] -> Int -> BitFrequencySummarizer -> Int -> Int
lastNumStanding [] _ _ _ = 0
lastNumStanding [x] _ _ _ = x
lastNumStanding nums width f positionToCheck =
  let expectedValues = f width nums
      shouldBeSet = (expectedValues !! positionToCheck) == 1
      bitIndex = length expectedValues - positionToCheck - 1
      matchingNums = filter (\n -> testBit n bitIndex == shouldBeSet) nums
   in if null matchingNums
        then last nums
        else lastNumStanding matchingNums width f (positionToCheck + 1)

… and I’m not proud about it. For instance, I keep passing a width parameter that never changes. This parameter was necessitated by the fact that I represent the bits as an Int, and use testBit to extract information. A better abstraction would have been to represent 10111 as [1, 0, 1, 1, 1], instead of as 23.

Naming-wise, ’s findRating is better than lastNumStanding. Even better is rating as get* and find* are not idiomatic.

had a solution of the form:

findRating :: BitFrequencySummarizer -> Int -> [Bits] -> Bits
-- We don't need to match `findRating _ _ []` because we always have
-- a non-empty `[Bits]` and our base case is the single item `[Bits]`.
findRating _ _ [b] = b
findRating f idx bits =
  -- I don't think that unconditionally calling `findRating` with
  -- the filtered list is safe. What if the filtered list is empty? We'd
  -- go into an infinite loop!
  findRating f (idx + 1)
  -- `(!!)` crashes if the index is out of bounds. However, if we have a
  -- `Data.Vector`, then `(!?)` is safe, and returns `Maybe Int` [2].
  -- Another point in the bag for `Data.Vector`.
  --
  -- [1]: https://hackage.haskell.org/package/base-4.16.0.0/docs/GHC-List.html#v:-33--33-
  -- [2]: https://hackage.haskell.org/package/vector-0.12.3.1/docs/Data-Vector.html#v:-33--63-
  $ filter (\b -> b !? idx == mc !? idx) bits
  where mc = f bits

Efficiency of Collections Types

To represent the bit sequence, decided to use Vector Int from the vector package , while I used [Int].

discusses tradeoffs:

Lists give $O(1)$ cons and pattern matching, and are purely functional and lazy. However, indexing takes $O(k)$ time, they have poor data locality, and poor space efficiency (pointer overhead per item).

A [Foo] is a singly-linked list of pointers to either a thunk (can take up more space than a Foo) that produces a Foo when evaluated, or an actual Foo.

Data.Sequence are purely functional, have amortized $O(1)$ to access the beginning and end, and have $O(log\ n)$ access to the middle. However, poor data locality, and only work for finite collections.
Arrays provide $O(1)$ access, and have good data locality, but they do not fit very well with the lazy pure functional world, and are a pain to use.
Data.Vector provides all of the array goodness in a higher level and cleaner APIs, with caveats like: mutable arrays need live in the IO or ST monads; prepending requires copying over elements. .

mentions [Char] as a notable example of lists screwing up performance, and therefore a recommendation to use Data.Text or the very fast Data.ByteString. has sample perf numbers.

Data.Vector exposes boxed vectors and unboxed vectors. Say we have a vector of Ints. If it is boxed, then we have a pointer to an Int, or a thunk that produces an Int if evaluated. If unboxed, then we have the Int itself, no thunks. Boxed vectors said to be value lazy, while unboxed vectors are said to be value strict. Boxed vectors are instances of Functor and can therefore be fmap’d on .

Data.Vector uses stream fusion to optimize memory usage. For example,

import qualified Data.Vector.Unboxed as V

main :: IO ()
main = print V.sum $ V.enumFromTo 1 (10^9 :: Int)

… allocates a total of 52kb with -O2 optimization (instead of the expected 10^9 * sizeof int) because GHC determines that creating a vector is unnecessary and instead create an tight inner loop.

Data.Vector also exposes Storable vectors which hold Storable types. These types are stored in malloced memory that isn’t moved around by the garbage collector. Although this can lead to memory fragmentation, such types can be shared with programs in other languages through the Foreign Function Interface (FFI) .

I’m not currently interested in Storable types though.

The general guideline is:

Use unboxed vectors if you don’t need to pass values to a C FFI, and you have a Prim instance .
Use a storable vector is you have a Storable instance.
Otherwise, use a boxed vector.

Maybe #1 can be, if you need to fmap, use a boxed vector?

Converting Binary Representation to Decimal

My solution was:

fromBitList :: [Int] -> Int
fromBitList ds = fst $ foldr f (0, 1) ds
  where
    f d (s, powerOf2) = (s + powerOf2 * d, powerOf2 * 2)

… I don’t like that I’m carrying over two pieces of information in the fold.

had a solution of the form:

binaryToDecimal :: [Int] -> Int
binaryToDecimal = go 0
  where go n (b:bs) = go (2*n + b) bs
        go n []     = n

-- The recursive `go` is tricky. Tracing a sample call (with fully
-- evaluated parameters for clarity)
--
--                                = go  0 [1, 0, 1, 1, 1]
--  = go ( 2*0 + 1)  [0, 1, 1, 1] = go  1    [0, 1, 1, 1]
--  = go ( 2*1 + 0)     [1, 1, 1] = go  2       [1, 1, 1]
--  = go ( 2*2 + 1)        [1, 1] = go  5          [1, 1]
--  = go ( 2*5 + 1)           [1] = go 11             [1]
--  = go (2*11 + 1)           [0] = go 23              []
--  = 23

Even after tracing through ’s recursive fromBinary, I’m not sure how one could come up with it. Building up the solution from the least significant bit is more intuitive to me, not so for the most-significant-bit-first approach. Maybe algebraic manipulation might help?

$$ 10111_2 = (2^4 \cdot 1) + (2^3 \cdot 0) + (2^2 \cdot 1) + (2^1 \cdot 1) + (2^0 \cdot 1) $$

The algebraic form didn’t help. Maybe the intuition for the MSB-first approach is that whenever we see a new digit b, we need to multiply whatever we have by 2 and then add b. That is the best answer we can give at that moment. The various values for n in the go n calls are $0_2, 1_2, 10_2, 101_2, 1011_2, 10111_2$.

uses a left-fold:

binaryToDecimal :: [Int] -> Int
binaryToDecimal = foldl (\acc x -> acc * 2 + x) 0

… which is basically what did, but using the standard library. That said, if using a left fold, the strict foldl' is a better choice to avoid stack overflow of pending thunks.

References

Advent of Code 2021: Day 3: Binary Diagnostic. jhidding.github.io . Accessed Feb 25, 2022.
Haskell: Lists, Arrays, Vectors, Sequences - Stack Overflow. stackoverflow.com . Accessed Feb 25, 2022.
Performance/Strings - HaskellWiki. wiki.haskell.org . Accessed Feb 25, 2022.
performance - Advent of Code 2021, Day 3 in Haskell - Code Review Stack Exchange. codereview.stackexchange.com . Accessed Feb 25, 2022.
Data.List > foldl'. hackage.haskell.org . Accessed Feb 25, 2022.
Advent of Code 2021 day 3 : haskell. www.reddit.com . Accessed Feb 25, 2022.
Data.List.transpose. hackage.haskell.org . Accessed Feb 25, 2022.
vector: Efficient Packed-Memory Data Representations. www.fpcomplete.com . Accessed Feb 26, 2022.