DEV Community

Cover image for DAY 13 - Advent of Code 2020 w/ GoLang
Edvin
Edvin

Posted on

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
}

Enter fullscreen mode Exit fullscreen mode

Link to Github source file

AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay