Aoc2021-day12.scala

package lascala.aoc2021.day11_20.day12

opaque type Cave = String
extension (c: Cave) def isLarge: Boolean = c.forall(_.isUpper)
object Cave:
  val Start = "start"
  val End   = "end"

opaque type CaveSystem = Map[Cave, Set[Cave]]

extension (cs: CaveSystem)
  def paths(cond: (Cave, List[Cave]) => Boolean): Set[List[Cave]] =
    def dfs(current: Cave, visited: List[Cave]): Set[List[Cave]] =
      val nextVisited = current :: visited
      if current == Cave.End then Set(nextVisited)
      else
        for
          next  <- cs(current) if cond(next, nextVisited)
          paths <- dfs(next, nextVisited)
        yield paths
    dfs(Cave.Start, Nil)
end extension

object CaveSystem:
  def parse(s: String): CaveSystem = s
    .split("\n")
    .flatMap { line =>
      val Array(c0, c1) = line.split("-")
      Array(c0 -> c1, c1 -> c0)
    }
    .groupMapReduce(_._1)((_, v) => Set(v))(_ ++ _)

  def firstCondition(next: Cave, visited: List[Cave]): Boolean =
    next.isLarge || !visited.contains(next)

  def secondCondition(next: Cave, visited: List[Cave]): Boolean =
    val isLarge = next.isLarge
    val isStart = next == Cave.Start
    val isAlreadyVisitedSmallCaveTwice =
      val smalls = visited.filterNot(_.isLarge)
      smalls.size != smalls.toSet.size
    val isAlreadyVisited = visited.contains(next)
    isLarge || !(isStart || (isAlreadyVisitedSmallCaveTwice && isAlreadyVisited))

end CaveSystem

def solve1(s: String): BigInt =
  val caveSystem = CaveSystem.parse(s)
  caveSystem.paths(CaveSystem.firstCondition).size
end solve1

def solve2(s: String): BigInt =
  val caveSystem = CaveSystem.parse(s)
  caveSystem.paths(CaveSystem.secondCondition).size
end solve2

@main def part1: Unit =
  val ans = solve1(input)
  println(ans)

@main def part2: Unit =
  val ans = solve2(input)
  println(ans)

//val input = """start-YY

Aoc2021-day12Test.scala

package lascala.aoc2021.day11_20.day12

import minitest.SimpleTestSuite
import hedgehog.minitest.HedgehogSupport
import hedgehog.*

object Day12Test extends SimpleTestSuite with HedgehogSupport:

  val testInput1 = """start-A
start-b
A-c
A-b
b-d
A-end
b-end"""

  val testInput2 = """dc-end
HN-start
start-kj
dc-start
dc-HN
LN-dc
HN-end
kj-sa
kj-HN
kj-dc"""

  val testInput3 = """fs-end
he-DX
fs-he
start-DX
pj-DX
end-zg
zg-sl
zg-pj
pj-he
RW-he
fs-DX
pj-RW
zg-RW
start-pj
he-WI
zg-he
pj-fs
start-RW"""

  example("day12 - solve 1 with test input #1") {
    solve1(testInput1) ==== 10
  }

  example("day12 - solve 1 with test input #2") {
    solve1(testInput2) ==== 19
  }
  
  example("day12 - solve 1 with test input #3") {
    solve1(testInput3) ==== 226
  }

  example("day12 - solve 2 with test input #1") {
    solve2(testInput1) ==== 36
  }

  example("day12 - solve 2 with test input #2") {
    solve2(testInput2) ==== 103
  }
  
  example("day12 - solve 2 with test input #3") {
    solve2(testInput3) ==== 3509
  }
end Day12Test