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.)
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
or1
) in the current bit position, and only keep the numbers with that bit in that position. If0
and1
are equally common, keep values with a1
in the position being considered.  To find CO2 scrubber rating, determine the least common value
(
0
or1
) in the current bit position, and only keep the numbers with that bit in that position. If0
and1
are equally common, keep values with a0
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 `Wunusedtopbinds` [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/usingwarnings.html?highlight=unusedtopbinds#ghcflagWunusedtopbinds
 [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/deepseq1.4.6.1/docs/ControlDeepSeq.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 bleast 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/base4.16.0.0/docs/DataBits.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 viceversa 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 ith 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
.
findRating :: BitFrequencySummarizer > Int > [Bits] > Bits
 We don't need to match `findRating _ _ []` because we always have
 a nonempty `[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/base4.16.0.0/docs/GHCList.html#v:3333
 [2]: https://hackage.haskell.org/package/vector0.12.3.1/docs/DataVector.html#v:3363
$ 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]
.
 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).

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 theIO
orST
monads; prepending requires copying over elements. .
Data.Vector
exposes boxed vectors and unboxed vectors. Say we have a
vector of Int
s. 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 malloc
ed 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.
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 mostsignificantbitfirst 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 MSBfirst
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\).
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 PackedMemory Data Representations. www.fpcomplete.com . Accessed Feb 26, 2022.
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.