AoC 2020 Day 13

day13.swift

import Foundation

final class Day1320: Day {
    override func perform() {
        let components = String.input(forDay: 13, year: 2020).split(separator: "\n")
        let estimate = Int(String(components[0]))!
        let buses = components[1]
            .split(separator: ",")
            .map(String.init)
            .map(Int.init)

        stageOneOutput = "\(part1(estimate: estimate, buses: buses))"
        stageTwoOutput = "\(part2(buses: buses))"
    }

    func part1(estimate: Int, buses: [Int?]) -> Int {
        let (bus, time) =  buses
            .compactMap { $0 }
            .map { ($0, $0 - (estimate % $0)) }
            .min(by:  { lhs, rhs in lhs.1 < rhs.1 })!

        return bus * time
    }

    func part2(buses: [Int?]) -> Int {
        // We're trying to find time t where the first bus takes off
        // The keys are bus IDs (mods), and the values are t % ID
        let moduloAndRemainder = buses
            .enumerated()
            .compactMap { bus in bus.element.flatMap { ($0, bus.offset) } }
            .reduce(into: [:]) { (offsetsByBus, next) in
                // offsets are latencies, we convert them to remainder of t % ID
                // for instance, t + offset % x = 0 => t + 4 % x = 0 => t % x = x - 4 =
                offsetsByBus[next.0] = next.0 - next.1
            }
            .sorted(by: { (lhs, rhs) -> Bool in lhs.key < rhs.key} )

        // follow the calculations for Chinese Remainder Theorem https://youtu.be/zIFehsBHB8o
        let bi = sortedBusAndTimes.map { $0.value }
        let modi = sortedBusAndTimes.map { $0.key }
        let N = modi.reduce(1, *)
        let ni = modi.map { N/$0 }
        let xi = zip(ni, modi).map { modInverse(of: $0.0, mod: $0.1 ) }

        let binixi = (0..<bi.count).map { bi[$0] * ni[$0] * xi[$0] }
        return binixi.reduce(0, +) % N
    }

    // Adapted from https://github.com/simon-andrews/rust-modinverse/blob/master/src/lib.rs
    func modInverse(of a: Int, mod m: Int) -> Int {
        let (g, x, _) = egcd(a, m)
        guard g == 1 else { fatalError() }
        return (x % m + m) % m
    }

    // Adapted from https://github.com/simon-andrews/rust-modinverse/blob/master/src/lib.rs
    func egcd(_ a: Int, _ b: Int) -> (Int, Int, Int) {
        if a == 0 {
            return (b, 0, 1)
        } else {
            let (g, x, y) = egcd(b % a, a)
            return (g, y - (b / a) * x, x)
        }
    }
}