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=${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) { | |
| (disjoin, a) => a :: disjoin.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) // : Long = 546724 | |
| val ans2 = countLit(steps) // : Long = 1346544039176841 | |
| // 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) | |
| val a1 = Area(1 to 10, 1 to 10, 1 to 10) | |
| a1 superset a1 // : Boolean = true | |
| a1 intersect a1 // : Option[Area] = Some(Area(1..10,1..10,1..10)) | |
| a1 diff a1 // : List[Area] = List() | |
| a1.xs intersect a1.xs // : Option[Range] = Some(1..10) | |
| a1.xs diff a1.xs // : List[Range] = List() | |
| val a2 = Area(6 to 15, 6 to 15, 6 to 15) | |
| a1 intersect a2 // : Option[Area] = Some(Area(6..10,6..10,6..10)) | |
| a1 diff a2 // : List[Area] = List(Area(6..10,6..10,1..5), Area(6..10,1..5,6..10), Area(6..10,1..5,1..5), Area(1..5,6..10,6..10), Area(1..5,6..10,1..5), Area(1..5,1..5,6..10), Area(1..5,1..5,1..5)) | |
| Area.unionSize(List(a1, a2)) //: Long = 1875 | |
| (a1 intersect a2).map(_.size).sum // : Long = 125 | |
| 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