Last active
December 8, 2023 19:08
-
-
Save thanhbv/7df2f403d2f7e2c21d8b16ab30dd95fa to your computer and use it in GitHub Desktop.
Advent of Code 2023 day 8 bug
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Guide to run: | |
// + Install scala-cli: https://scala-cli.virtuslab.org/install | |
// + Run: scala-cli test d8bug.scala | |
// Guide to dev: https://scala-cli.virtuslab.org/docs/cookbooks/ide/vscode | |
//> using scala 3.3.1 | |
//> using dep org.scalameta::munit::1.0.0-M10 | |
// With input like bellow, we can NOT use LCM to solve part2 | |
val input = """LLR | |
AAA = (BBA, AAA) | |
BBA = (BBB, DDD) | |
BBB = (BBA, CCC) | |
CCC = (AAZ, CCC) | |
AAZ = (BBB, AAZ) | |
DDD = (DDD, ZZZ) | |
ZZZ = (AAZ, ZZZ)""" | |
type Node = String | |
type Direction = Char // 'L' or 'R' | |
case class Choices(left: Node, right: Node) | |
val (instructions: LazyList[Direction], net: Map[Node, Choices]) = | |
val lines = input.linesIterator | |
val firstLinne = lines.next() | |
val net = lines.drop(1).map { line => | |
val s"$from = ($left, $right)" = line: @unchecked | |
from -> Choices(left, right) | |
}.toMap | |
val instructions = LazyList.from(0).map(i => firstLinne.charAt(i % firstLinne.length)) | |
instructions -> net | |
def moves(start: Node => Boolean) = | |
instructions.scanLeft(net.keys.filter(start).toList) { | |
case (nodes, 'L') => nodes.map(net(_).left) | |
case (nodes, _) => nodes.map(net(_).right) | |
} | |
// brute force | |
def part2() = moves(_.endsWith("A")).indexWhere(_.forall(_.endsWith("Z"))) | |
class MyTests extends munit.FunSuite: | |
val stop = (n: Node) => n.endsWith("Z") | |
val moves1 = moves(_ == "AAA").flatten | |
val moves2 = moves(_ == "BBA").flatten | |
test("AAA escape after 4 + 3x steps"): | |
moves1.zipWithIndex.take(20).foreach: (n, i) => | |
assertEquals(stop(n), i >= 3 && i % 3 == 1) | |
test("BBA escape after 6 or 7 + 3x steps"): | |
moves2.zipWithIndex.take(20).foreach: (n, i) => | |
assertEquals(stop(n), i == 6 || i >= 7 && i % 3 == 1) | |
test("Using LCM to solve part2 is NOT correct"): // fail!!! | |
val l1 = moves1.indexWhere(stop) | |
val l2 = moves2.indexWhere(stop) | |
assertEquals(l1, 4) | |
assertEquals(l2, 6) | |
val lcm = 12 | |
val at12 = moves1(lcm) | |
assert(stop(at12), s"\nat12 == $at12") | |
test("Correct answer for part2 is 7"): | |
val n = part2() | |
assertEquals(n, 7) | |
assert(stop(moves1(7))) | |
assert(stop(moves2(7))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
network visualize for the input