DAY 13 - Advent of Code 2020 w/ GoLang

DAY13:

TLDR: Use modulo and look at least common multiple

Again, part one went pretty well. Part two read like it would be a similar difficulty. It was about a similar difficulty level but if not optimized could potentially take hours to run. When I got the solution the first time, it was after passing all test cases and allowing my code to run for about 4 hours. While that was happening, I did some research (Google) and got reminded of least common multiple which after implemented, allowed my program to finish MUCH faster. Essentially it allows you to short circuit and skips forward to the next best potential timestamp without evaluating every single one in between.

package days

import (
    "fmt"
    "strconv"

    inputs "../inputs"
)

// https://adventofcode.com/2020/day/13
// Thirteen : advent of code, day thirteen part1 and 2
func Thirteen() {
    inputSlice := inputs.Day13
    earliestTimeStamp := inputs.Day13EarliestTimestamp
    buses := []int{}

    for bus := range inputSlice {
        if inputSlice[bus] == "x" {
            buses = append(buses, 1)
        } else {
            asInt, _ := strconv.Atoi(inputSlice[bus])
            buses = append(buses, asInt)
        }
    }

    fmt.Print("(Part 1) - Minutes to catch multiplied by the bus ID: ")
    fmt.Println(catchNextPossibleBus(buses, earliestTimeStamp))

    fmt.Print("(Part 2) - Earliest timestamp of subsequent series: ")
    fmt.Println(startStampOfSubsequentSeries(buses, 0))

}

func catchNextPossibleBus(buses []int, earliestTimeStamp int) int {
    busMap := make(map[int]int)

    for bus := range buses {
        if buses[bus] > 1 {
            busMap[buses[bus]] = buses[bus] - (earliestTimeStamp % buses[bus]) + earliestTimeStamp
        }
    }

    nextBusTimeStamp := 0
    nextBus := 0

    for k, v := range busMap {
        if v < nextBusTimeStamp || nextBusTimeStamp == 0 {
            nextBusTimeStamp = v
            nextBus = k
        }
    }

    return nextBus * (nextBusTimeStamp - earliestTimeStamp)
}

func startStampOfSubsequentSeries(buses []int, multiplier int) int {
    start := 0
    properBusSeries := false

    for !properBusSeries {
        skipFactor := 1
        properBusSeries, skipFactor = checkThisSeries(buses, start, skipFactor)
        if !properBusSeries {
            start = start + skipFactor
        }
    }

    return start
}

func checkThisSeries(buses []int, start int, skipFactor int) (bool, int) {
    for bus := 0; bus < len(buses); bus++ {

        if (start+bus)%buses[bus] != 0 {
            return false, skipFactor
        }

        skipFactor = skipFactor * buses[bus]
    }

    return true, skipFactor
}

Link to Github source file