Somewhat suspicious of 2 easy days we end up at Day 8. A simple map to follow again, from one key follow the instructions until we hit ZZZ. Part 2 had us do it for several keys at once, with the goal to find the spot where they all converge. This can take forever, erhm, a long time.

So there has to be a math type solution to this problem. It turns out to be a Least Common Multiple problem. It is the smallest positive integer that is divisible by two or more numbers without leaving a remainder. To find the LCM of two or more numbers, you can use a method called prime factorization or a simpler approach involving multiples. We can also use the Greatest Common Divisor (GCD) to find the LCM.

LCM(a, b) = (a * b) / GCD(a, b)

Example: Find the LCM of 12 and 18 using their GCD.

Step 1: Find the GCD of 12 and 18.

  • You can use methods like prime factorization or the Euclidean algorithm to find the GCD.
  • GCD(12, 18) = 6

Step 2: Use the formula to find the LCM.

LCM(12, 18) = (12 * 18) / 6 = 216 / 6 = 36

So, the LCM of 12 and 18 is 36.

package main

import (
	"fmt"
	"strings"
	"time"

	"arjenwiersma.nl/aoc/internal/aoc"
)

func LCM(numbers []int) int {
	result := numbers[0]
	for i := 1; i < len(numbers); i++ {
		result = (result * numbers[i]) / GCD(result, numbers[i])
	}
	return result
}

func GCD(a, b int) int {
	if b == 0 {
		return a
	}
	return GCD(b, a%b)
}

func solve(s string, instr string, m map[string][]string, p2 bool) int {
	steps := 0
	for {
		d := 0
		if string(instr[steps%len(instr)]) == "R" {
			d = 1
		}

		if !p2 && s == "ZZZ" {
			break
		}
		if p2 && s[2] == 'Z' {
			break
		}

		s = m[s][d]

		steps += 1
	}
	return steps
}
func main() {
	content := aoc.AsLines("2023/Day08/input.txt")

	instr := content[0]
	m := make(map[string][]string)

	for _, v := range content[2:] {
		n := strings.Split(v, " = ")
		lr := strings.Split(n[1], ",")

		m[n[0]] = []string{strings.TrimSpace(lr[0][1:]), strings.TrimSpace(lr[1][:len(lr[1])-1])}
	}

	startTime := time.Now()

	steps := solve("AAA", instr, m, false)

	endTime := time.Now()
	elapsed := endTime.Sub(startTime)
	fmt.Printf("Part 1: %d (%v)\n", steps, elapsed)

	startTime = time.Now()

	var solves []int
	for k := range m {
		if k[2] == 'A' {
			solves = append(solves, solve(k, instr, m, true))
		}
	}

	// do stuff
	endTime = time.Now()
	elapsed = endTime.Sub(startTime)
	fmt.Printf("Part 2: %d (%v)\n", LCM(solves), elapsed)
}