Advent of Code 2023-8.scala

import java.io.FileInputStream
import scala.annotation.tailrec
import scala.io.StdIn

case class Network(left: String, right: String)
case class Desert(networks: Map[String, Network])

case class LoopInfo(start: Int, step: Int)

object Desert {
  def apply(inputs: Vector[String]): Desert =
    val networks = inputs.map { line =>
      val words = line.split(" ")
      words(0) -> Network(words(2).tail.init, words(3).init)
    }.toMap
    Desert(networks)
}

@tailrec
def step(instructions: String, desert: Desert, isEnd: String => Boolean, current: String, index: Int, acc: Int): Int =
  if isEnd(current) then acc
  else
    val network = desert.networks(current)
    val next = instructions(index) match
      case 'L' => network.left
      case 'R' => network.right
    step(instructions, desert, isEnd, next, (index + 1) % instructions.length, acc + 1)

def solve8_1(instructions: String, desert: Desert): Int =
  step(instructions, desert, s => s == "ZZZ", "AAA", 0, 0)

@tailrec
def findLoopInfo(instructions: String, desert: Desert, isEnd: String => Boolean, current: String, index: Int, acc: Vector[(String, Int)]): Vector[LoopInfo] =
  val currentIndex = acc.indexOf((current, index))
  if -1 != currentIndex then
    val endSet = acc.zipWithIndex.filter((s, i) => i >= currentIndex && isEnd(s._1))
    endSet.map {
      case (s, i) => LoopInfo(i, acc.length - currentIndex) // 3 6
    }
  else
    val network = desert.networks(current)
    val next = instructions(index) match
      case 'L' => network.left
      case 'R' => network.right
    findLoopInfo(instructions, desert, isEnd, next, (index + 1) % instructions.length, acc :+ (current, index))

def solve8_2(instructions: String, desert: Desert): BigInt =
  val starts = desert.networks.keys.toVector.filter(s => s.endsWith("A"))
  val loopInfos = starts.map(start => findLoopInfo(instructions, desert, s => s.endsWith("Z"), start, 0, Vector()))
  val smallOnes = loopInfos.map(x => x.minBy(_.step))
  val base = smallOnes.maxBy(_.step)

  @tailrec
  def _solve(current: BigInt): BigInt =
    if loopInfos.forall(_.exists(x => 0 == (current - x.start) % x.step)) then
      current
    else
      _solve(current + base.step)

  _solve(base.start)

@main def solve8(): Unit =
  val in = new FileInputStream("example8-2.in")
  System.setIn(in)
  val inputs = Iterator.continually(StdIn.readLine())
    .takeWhile(line => null != line)
    .toVector

  println(solve8_1(inputs.head, Desert(inputs.drop(2))))
  println(solve8_2(inputs.head, Desert(inputs.drop(2))))