Skip to content

Instantly share code, notes, and snippets.

@stewSquared
Last active July 12, 2022 10:59
Show Gist options
  • Save stewSquared/4f4fac0d5d754fd0a05ab49eae3d5fe2 to your computer and use it in GitHub Desktop.
Save stewSquared/4f4fac0d5d754fd0a05ab49eae3d5fe2 to your computer and use it in GitHub Desktop.
Advent of Code 2021 Day 22 in Scala 3
val steps =
io.Source.fromResource("2021/day-22-1.txt").getLines.toList.collect {
case s"$step x=${Range(xs)},y=${Range(ys)},z=${Range(zs)}" =>
Step(step == "on", Area(xs, ys, zs))
}
case class Step(on: Boolean, area: Area):
def countLastTouched(future: List[Step]): Long =
val overlaps = future.flatMap(_.area.intersect(area))
val touchedLater = Area.unionSize(overlaps)
area.size - touchedLater
case class Range(min: Int, max: Int):
override def toString = s"$min..$max"
def size = max + 1 - min
def contains(n: Int) = min <= n && n <= max
def superset(r: Range) = min <= r.min && r.max <= max
def intersect(r: Range): Option[Range] =
if superset(r) then Some(r)
else if r.contains(min) then Some(copy(max = max.min(r.max)))
else if r.contains(max) then Some(copy(min = min.max(r.min)))
else None
def diff(r: Range): List[Range] =
intersect(r).fold(List(this)) { o =>
List(
if min < o.min then Some(min to (o.min - 1)) else None,
if o.max < max then Some((o.max + 1) to max) else None
).flatten
}
object Range:
def apply(n1: Int, n2: Int): Range =
new Range(n1 min n2, n1 max n2)
def unapply(s: String) = s match
case s"$n1..$n2" => n1.toIntOption.zip(n2.toIntOption).map(apply)
extension (n1: Int) def to(n2: Int): Range = Range(n1, n2)
case class Area(xs: Range, ys: Range, zs: Range):
def size: Long = xs.size.toLong * ys.size.toLong * zs.size.toLong
def superset(other: Area): Boolean =
(xs superset other.xs) && (ys superset other.ys) && (zs superset other.zs)
def intersect(other: Area): Option[Area] =
for
xo <- xs intersect other.xs
yo <- ys intersect other.ys
zo <- zs intersect other.zs
yield Area(xo, yo, zo)
def diff(other: Area): List[Area] =
intersect(other).fold(List(this)) { o =>
for
xr <- o.xs :: (xs diff other.xs)
yr <- o.ys :: (ys diff other.ys)
zr <- o.zs :: (zs diff other.zs)
a = Area(xr, yr, zr)
if a != o
yield a
}
object Area:
def unionSize(areas: Seq[Area]): Long =
val union = areas.sortBy(_.size).foldLeft[List[Area]](Nil) {
(disjoint, a) => a :: disjoint.flatMap(_ diff a)
}
union.map(_.size).sum
def suffixMap[A](elems: List[A]): Map[A, List[A]] =
val suffixes = elems.scanRight[List[A]](Nil)(_ :: _)
elems.zip(suffixes.tail).toMap
def countLit(steps: List[Step]) =
val onStepToFuture = suffixMap(steps).filter(_._1.on)
onStepToFuture.transform(_ countLastTouched _).values.sum
val initArea = Area(-50 to 50, -50 to 50, -50 to 50)
val initSteps = steps.flatMap(s => s.area.intersect(initArea).map(a => s.copy(area = a)))
val ans1 = countLit(initSteps)
val ans2 = countLit(steps)
// tests
(3 to 7) intersect (1 to 5) // : Option[Range] = Some(3..5)
(3 to 7) intersect (3 to 7) // : Option[Range] = Some(3..7)
(3 to 7) intersect (5 to 9) // : Option[Range] = Some(5..7)
(3 to 7) intersect (1 to 9) // : Option[Range] = Some(3..7)
(3 to 7) intersect (4 to 6) // : Option[Range] = Some(4..6)
(3 to 7) intersect (1 to 2) // : Option[Range] = None
(3 to 7) intersect (8 to 9) // : Option[Range] = None
(3 to 7) diff (1 to 5) // : List[Range] = List(6..7)
(3 to 7) diff (3 to 7) // : List[Range] = List()
(3 to 7) diff (5 to 9) // : List[Range] = List(3..4)
(3 to 7) diff (1 to 9) // : List[Range] = List()
(3 to 7) diff (4 to 6) // : List[Range] = List(3..3, 7..7)
(3 to 7) diff (1 to 2) // : List[Range] = List(3..7)
(3 to 7) diff (8 to 9) // : List[Range] = List(3..7)
def Cube(r: Range) = Area(r, r, r)
def dim(a: Area) =
val dims = List(a.xs, a.ys, a.zs)
dims.map(_.size).sorted.mkString("x")
val cube4 = Cube(1 to 4)
val corner = Cube(3 to 10)
val center = Cube(2 to 3)
cube4 intersect cube4 // : Option[Area] = Some(Area(1..4,1..4,1..4))
cube4 intersect corner // : Option[Area] = Some(Area(3..4,3..4,3..4))
cube4 intersect center // : Option[Area] = Some(Area(2..3,2..3,2..3))
val cornerDiff = cube4 diff corner
val centerDiff = cube4 diff center
cube4 diff cube4 // : List[Area] = List()
cornerDiff map dim // : List[String] = List(2x2x2, 2x2x2, 2x2x2, 2x2x2, 2x2x2, 2x2x2, 2x2x2)
cornerDiff.size // : Int = 7
cornerDiff.map(_.size).sum // : Long = 56
4*4*4 - 2*2*2 // : Int = 56
centerDiff.groupMapReduce(dim)(_ => 1)(_ + _) // : Map[String, Int] = Map(1x1x1 -> 8, 1x2x2 -> 6, 1x1x2 -> 12)
centerDiff.size // : Int = 26
centerDiff.map(_.size).sum // : Long = 56
val areas =
for
xs <- List(1 to 5, 3 to 7, 5 to 9)
ys <- List(1 to 5, 3 to 7, 5 to 9)
zs <- List(1 to 5, 3 to 7, 5 to 9)
yield Area(xs, ys, zs)
Area.unionSize(areas) // : Long = 729
Area(1 to 9, 1 to 9, 1 to 9).size // : Long = 729
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment