stewSquared · July 12, 2022 10:59 · Jul 12, 2022 · Dec 23, 2021 · Dec 23, 2021 · Dec 23, 2021
diff --git a/Day22.worksheet.sc b/Day22.worksheet.sc
@@ -67,7 +67,7 @@ case class Area(xs: Range, ys: Range, zs: Range):
 object Area:
   def unionSize(areas: Seq[Area]): Long =
     val union = areas.sortBy(_.size).foldLeft[List[Area]](Nil) {
-      (disjoin, a) => a :: disjoin.flatMap(_ diff a)
+      (disjoint, a) => a :: disjoint.flatMap(_ diff a)
     }
     union.map(_.size).sum
 

diff --git a/Day22.worksheet.sc b/Day22.worksheet.sc
@@ -82,8 +82,8 @@ def countLit(steps: List[Step]) =
 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
+val ans1 = countLit(initSteps)
+val ans2 = countLit(steps)
 
 // tests
 
@@ -103,21 +103,33 @@ val ans2 = countLit(steps) // : Long = 1346544039176841
 (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)
+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")
 
-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 cube4 = Cube(1 to 4)
+val corner = Cube(3 to 10)
+val center = Cube(2 to 3)
 
-val a2 = Area(6 to 15, 6 to 15, 6 to 15)
+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))
 
-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))
+val cornerDiff = cube4 diff corner
+val centerDiff = cube4 diff center
 
-Area.unionSize(List(a1, a2)) //: Long = 1875
-(a1 intersect a2).map(_.size).sum // : Long = 125
+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

diff --git a/Day22.worksheet.sc b/Day22.worksheet.sc
@@ -1,9 +1,7 @@
 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 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):
@@ -13,6 +11,8 @@ case class Step(on: Boolean, area: Area):
     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
@@ -35,6 +35,9 @@ 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):
@@ -63,9 +66,8 @@ case class Area(xs: Range, ys: Range, zs: Range):
 
 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))
+    val union = areas.sortBy(_.size).foldLeft[List[Area]](Nil) {
+      (disjoin, a) => a :: disjoin.flatMap(_ diff a)
     }
     union.map(_.size).sum
 
@@ -80,5 +82,49 @@ def countLit(steps: List[Step]) =
 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)
+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
diff --git a/Day22.worksheet.sc b/Day22.worksheet.sc
@@ -6,7 +6,11 @@ val steps =
       Step(step == "on", area)
   }
 
-case class Step(on: Boolean, area: 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
@@ -27,12 +31,12 @@ case class Range(min: Int, max: Int):
       ).flatten
     }
 
-extension (n1: Int) def to(n2: Int): Range = Range(n1, n2)
-
 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
 
@@ -65,16 +69,16 @@ object Area:
     }
     union.map(_.size).sum
 
-val onStepsToFuture: Map[Step, List[Step]] =
-  val suffixes = steps.reverse.scanLeft(List.empty[Step])(_ appended _)
-  steps.zip(suffixes.reverse.tail).filter(_._1.on).toMap
+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 countLastTouched: Map[Step, Long] = onStepsToFuture.transform {
-  case (step, futureSteps) =>
-    val overlaps = futureSteps.flatMap(_.area.intersect(step.area))
-    val flippedLater = Area.unionSize(overlaps)
-    val flippedOn = step.area.size
-    flippedOn - flippedLater
-}
+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 ans2 = countLastTouched.values.sum
+val ans1 = countLit(initSteps)
+val ans2 = countLit(steps)
diff --git a/Day22.worksheet.sc b/Day22.worksheet.sc
@@ -1,5 +1,3 @@
-import collection.immutable.BitSet
-
 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" =>
@@ -48,7 +46,7 @@ case class Area(xs: Range, ys: Range, zs: Range):
       zo <- zs intersect other.zs
     yield Area(xo, yo, zo)
 
-  def remainder(other: Area): List[Area] =
+  def diff(other: Area): List[Area] =
     intersect(other).fold(List(this)) { o =>
       for
         xr <- o.xs :: (xs diff other.xs)
@@ -63,7 +61,7 @@ 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(_.remainder(a))
+      a :: acc.flatMap(_.diff(a))
     }
     union.map(_.size).sum
 

diff --git a/Day22.worksheet.sc b/Day22.worksheet.sc
@@ -0,0 +1,82 @@
+import collection.immutable.BitSet
+
+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)
+
+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
+    }
+
+extension (n1: Int) def to(n2: Int): Range = Range(n1, n2)
+
+object Range:
+  def apply(n1: Int, n2: Int): Range =
+    new Range(n1 min n2, n1 max 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 remainder(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(_.remainder(a))
+    }
+    union.map(_.size).sum
+
+val onStepsToFuture: Map[Step, List[Step]] =
+  val suffixes = steps.reverse.scanLeft(List.empty[Step])(_ appended _)
+  steps.zip(suffixes.reverse.tail).filter(_._1.on).toMap
+
+val countLastTouched: Map[Step, Long] = onStepsToFuture.transform {
+  case (step, futureSteps) =>
+    val overlaps = futureSteps.flatMap(_.area.intersect(step.area))
+    val flippedLater = Area.unionSize(overlaps)
+    val flippedOn = step.area.size
+    flippedOn - flippedLater
+}
+
+val ans2 = countLastTouched.values.sum
No results found