Last active
July 12, 2022 10:59
-
-
Save stewSquared/4f4fac0d5d754fd0a05ab49eae3d5fe2 to your computer and use it in GitHub Desktop.
Advent of Code 2021 Day 22 in Scala 3
This file contains hidden or 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
| val steps = | |
| io.Source.fromResource("2021/day-22-1.txt").getLines.toList.collect { | |
| case s"$step x=$x1..$x2,y=$y1..$y2,z=$z1..$z2" => | |
| val area = | |
| Area(x1.toInt to x2.toInt, y1.toInt to y2.toInt, z1.toInt to z2.toInt) | |
| Step(step == "on", area) | |
| } | |
| 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): | |
| 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) | |
| 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 largest = areas.sortBy(_.size).reverse | |
| val union = largest.foldLeft[List[Area]](Nil) { (acc, a) => | |
| a :: acc.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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment