8000 Optimize 2020 day 20 part 2 by not constructing sliding windows · sim642/adventofcode@b743ce2 · GitHub
[go: up one dir, main page]

Skip to content

Commit b743ce2

Browse files
committed
Optimize 2020 day 20 part 2 by not constructing sliding windows
1 parent ba71c96 commit b743ce2

File tree

1 file changed

+20
-27
lines changed

1 file changed

+20
-27
lines changed

src/main/scala/eu/sim642/adventofcode2020/Day20.scala

Lines changed: 20 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@ package eu.sim642.adventofcode2020
22

33
import eu.sim642.adventofcodelib.Grid
44
import eu.sim642.adventofcodelib.GridImplicits._
5+
import eu.sim642.adventofcodelib.box.Box
56
import eu.sim642.adventofcodelib.pos.Pos
67

78
object Day20 {
@@ -157,35 +158,27 @@ object Day20 {
157158
val grid = solved.mapGrid(_.innerGrid).flattenGrid // TODO: try all orientations
158159
//printGrid(grid)
159160

160-
def doOrientation(grid: Grid[Boolean]): Option[Int] = {
161-
val monster = seamonster.linesIterator.map(_.toVector).toVector.mapGrid(_ == '#')
162-
//printGrid(monster)
163-
val monsterPoss =
164-
(for {
165-
(row, y) <- grid.slidingGrid2(monster.size, monster.head.size).zipWithIndex
166-
(window, x) <- row.zipWithIndex
167-
if window.correspondsGrid(monster)({
168-
case (true, true) => true
169-
case (_, false) => true
170-
case (_, _) => false
171-
})
172-
} yield Pos(x, y)).toSet
173-
//println(monsterPoss)
174-
175-
if (monsterPoss.isEmpty)
176-
return None
177-
178-
def grid2PosSet(grid: Grid[Boolean]): Set[Pos] = {
179-
(for {
180-
(row, y) <- grid.view.zipWithIndex
181-
(cell, x) <- row.view.zipWithIndex
182-
if cell
183-
} yield Pos(x, y)).toSet
184-
}
161+
def grid2PosSet(grid: Grid[Boolean]): Set[Pos] = {
162+
(for {
163+
(row, y) <- grid.view.zipWithIndex
164+
(cell, x) <- row.view.zipWithIndex
165+
if cell
166+
} yield Pos(x, y)).toSet
167+
}
168+
169+
val monster = seamonster.linesIterator.map(_.toVector).toVector.mapGrid(_ == '#')
170+
val monsterPosSet = grid2PosSet(monster)
185171

186-
val monsterPosSet = monsterPoss.flatMap(pos => grid2PosSet(monster).map(pos + _))
172+
def doOrientation(grid: Grid[Boolean]): Option[Int] = {
187173
val gridPosSet = grid2PosSet(grid)
188-
Some((gridPosSet -- monsterPosSet).size)
174+
175+
val monsterPosSet2 =
176+
Box(Pos.zero, Pos(grid.head.length - monster.head.length - 1, grid.length - monster.length - 1)).iterator
177+
.map(pos => monsterPosSet.map(pos + _))
178+
.filter(_.subsetOf(gridPosSet))
179+
.reduceOption(_ ++ _)
180+
181+
monsterPosSet2.map(s => (gridPosSet -- s).size)
189182
}
190183

191184
grid.orientations.flatMap(doOrientation).head

0 commit comments

Comments
 (0)
0