Daniel Tull: Advent of Code

Day 3: Binary Diagnostic

Advent of Code 2021

My first take at this problem was to use my existing BinaryNumber implementation, mapping each line into a binary number and creating a Count type to hold the counts of zeros and ones.

try input.lines
    .map(BinaryNumber.init)
    .reduce(into: Count()) { $0.count($1) }
    .result

struct Count {

    var zeros: [Int] = []
    var ones: [Int] = []

    mutating func count(_ binary: BinaryNumber) {
        if zeros.count == 0 { zeros = Array(repeating: 0, count: binary.count) }
        if ones.count == 0 { ones = Array(repeating: 0, count: binary.count) }

        self = binary.indexed().reduce(into: self) { (count, argument) in
            let (index, bit) = argument
            switch bit {
            case .one: count.ones[index] += 1
            case .zero: count.zeros[index] += 1
            }
        }
    }

    var result: Int { Int(gamma) * Int(epsilon) }

    var gamma: BinaryNumber {
        BinaryNumber(bits: zip(zeros, ones).map { $0 < $1 ? .zero : .one })
    }

    var epsilon: BinaryNumber { !gamma }
}

Rethinking…

I actually left part 2 until Saturday when I could expend more brain power to think about the problem.

https://github.com/danielctull/Advent-of-Code/commit/2df887b771010b88c26d6cadcfaf461492290811

extension Collection {

    public func transpose<C, E>() -> [[E]] where C == Element, C: Collection, C.Element == E {
        self[startIndex].indices.map { index in
            map { $0[index] }
        }
    }
}

I then added an extension to Sequence to find the element that appears the most. This uses the existing countByElement function which provides a dictionary of elements to their count.

extension Sequence where Element: Hashable {

    public var most: Element? {
        countByElement
            .max(by: { $0.value < $1.value })
            .map(\.key)
    }
}

With these two functions, it was simple to transpose the given lines – an array of strings or a collection of a collection of characters – into an array of columns.

I can then map each column to find the character that occured the most to provide an array of characters, which is then turned into a BinaryNumber type. This allows me to perform a bitwise NOT on it and to calculate the result in decimal.

let most = try input.lines
    .transpose()
    .map { try $0.most.unwrapped() }

let gamma = try BinaryNumber(most)
let epsilon = !gamma
return Int(gamma) * Int(epsilon)

Part 2

I used tuple comparison to get the minimum value in a sequence, specifying two key paths. If the first value is the same, it then compares the value at the second key path.

extension Sequence {

    public func min<V1: Comparable, V2: Comparable>(
        by kp1: KeyPath<Element, V1>,
        _ kp2: KeyPath<Element, V2>
    ) -> Element? {
        self.min(by: {
            ($0[keyPath: kp1], $0[keyPath: kp2]) < ($1[keyPath: kp1], $1[keyPath: kp2])
        })
    }
}

This allowed me to easily update the most function to deal with tied number of bits.

extension Sequence where Element: Hashable, Element: Comparable {

    public var most: Element? {
        countByElement
            .max(by: \.value, \.key)
            .map(\.key)
    }
}