Skip to content

Instantly share code, notes, and snippets.

@almendar
Created December 14, 2021 19:07
Show Gist options
  • Save almendar/c5b6a41bbbd3ab1246a3e9ada9f8b18c to your computer and use it in GitHub Desktop.
Save almendar/c5b6a41bbbd3ab1246a3e9ada9f8b18c to your computer and use it in GitHub Desktop.
import java.nio.file.Files
import java.nio.file.Paths
import scala.collection.mutable
import scala.collection.mutable.ArrayBuffer
import scala.util.chaining._
opaque type Cave = String
type Path = Vector[Cave]
extension (c: Cave)
def isStart: Boolean = c == "start"
def isEnd: Boolean = c == "end"
def allLowerCase: Boolean = c.forall(_.isLower)
object Cave:
def apply(s: String): Cave = s
final case class Territory(map: Map[Cave, Vector[Cave]])
def readInput(s: String) =
val map = Files
.readString(Paths.get(s))
.split("\n")
.foldLeft(Map.empty[Cave, Vector[Cave]])((map, line) =>
val Array(c1, c2) = line.split("-")
val addFunc = (from: String, to: String, map: Map[Cave, Vector[Cave]]) =>
if !from.isEnd && !to.isStart then
map.updatedWith(from) {
case Some(x) => Some(x :+ to)
case None => Some(Vector(to))
}
else map
end addFunc
map.pipe(addFunc(c1, c2, _)).pipe(addFunc(c2, c1, _))
)
Territory(map)
def visitOnlyOnceIfLowercase(item: Cave, path: Path): Boolean =
// println(s"Checking $item in path: $path")
if item.allLowerCase && path.contains(item) then false
else true
def lowerCaseMaxTwice(item: Cave, path: Path): Boolean =
val counts = mutable.Map[Cave, Int]()
var wasTwice = false
for v <- path do
if v.allLowerCase then
counts
.updateWith(v) {
case None => Some(1)
case Some(x) => Some(x + 1)
}
.foreach(x => if x == 2 then wasTwice = true)
if wasTwice then !counts.contains(item)
else
counts.get(item) match
case Some(x) => x < 2
case None => true
def lowerCaseMaxTwice1(item: Cave, path: Path): Boolean =
val counts = path.view.filter(_.allLowerCase).groupMapReduce(x => x)(x => 1)(_ + _).toMap
val wasTwice = counts.exists((_, v) => v == 2)
if wasTwice then !counts.contains(item)
else
counts.get(item) match
case Some(x) => x < 2
case None => true
def step(t: Territory, node: Cave, path: Path, validMove: (Cave, Path) => Boolean): Int = (for
v <- t.map(node)
if validMove(v, path)
yield
if v.isEnd then 1
else step(t, v, path :+ Cave(v), validMove)).sum
def task1(input: String): Int =
val r = readInput(input)
val count = step(r, Cave("start"), Vector(Cave("Start")), visitOnlyOnceIfLowercase)
println(s"Day 12 task1 $input - $count")
count
def task2(input: String): Int =
val r = readInput(input)
val count = step(r, Cave("start"), Vector(Cave("Start")), lowerCaseMaxTwice)
println(s"Day 12 task2 $input - $count")
count
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment