8000 Clean up 2020 day 20 · sim642/adventofcode@5f3b5fb · GitHub
[go: up one dir, main page]
Skip to content

Commit 5f3b5fb

Browse files
sim642sim642
committed
Clean up 2020 day 20
1 parent b743ce2 commit 5f3b5fb

File tree

1 file changed

+36
-58
lines changed

1 file changed

+36
-58
lines changed

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

Lines changed: 36 additions & 58 deletions
Original file line numberDiff line numberDiff line change
@@ -31,19 +31,7 @@ object Day20 {
3131
def borderLeft: Border = grid.map(_.head)
3232
def borderRight: Border = grid.map(_.last)
3333

34-
def rotate: Tile = copy(grid = grid.transpose.reverse)
35-
def flip: Tile = copy(grid = grid.reverse)
36-
37-
def orientations: Seq[Tile] = Seq(
38-
this,
39-
rotate,
40-
rotate.rotate,
41-
rotate.rotate.rotate,
42-
flip,
43-
flip.rotate,
44-
flip.rotate.rotate,
45-
flip.rotate.rotate.rotate,
46-
)
34+
def orientations: Seq[Tile] = grid.orientations.map(grid => copy(grid = grid))
4735

4836
def innerGrid: Grid[Boolean] = grid.drop(1).dropRight(1).map(_.drop(1).dropRight(1))
4937

@@ -77,20 +65,14 @@ object Day20 {
7765
case (border, Seq(tile)) => border -> tile
7866
})
7967

80-
edgeBorderTiles
81-
.groupMapReduce(_._2)(p => Set(p._1))(_ ++ _)
68+
edgeBorderTiles.groupMapReduce(_._2)(p => Set(p._1))(_ ++ _)
8269
}
8370

8471
def findCorners(borderTiles: Map[Border, Seq[Tile]]): Seq[Tile] = {
85-
val tileEdgeBorders = getTileEdgeBorders(borderTiles)
86-
87-
/*for ((a, b) <- edgeBorderTiles)
88-
println(s"$a: $b")
89-
90-
for ((a, b) <- tileEdgeBorders)
91-
println(s"${a.id}: ${b.size}")*/
92-
93-
tileEdgeBorders.filter(_._2.size == 4).keys.toSeq
72+
getTileEdgeBorders(borderTiles)
73+
.filter(_._2.size == 4)
74+
.keys
75+
.toSeq
9476
}
9577

9678
def findCorners(tiles: Seq[Tile]): Seq[Tile] = findCorners(getBorderTiles(tiles))
@@ -99,11 +81,6 @@ object Day20 {
9981

10082
def solvePuzzle(tiles: Seq[Tile]): Grid[Tile] = {
10183
val borderTiles = getBorderTiles(tiles)
102-
val corners = findCorners(borderTiles)
103-
val cornerTopLeft = corners.head
104-
val cornerTopLeftBorders = getTileEdgeBorders(borderTiles)(cornerTopLeft) // TODO: don't repeat with findCorners
105-
val cornerTopLeftOriented = cornerTopLeft.orientations.find(tile => cornerTopLeftBorders.contains(tile.borderTop) && cornerTopLeftBorders.contains(tile.borderLeft)).get
106-
println(cornerTopLeftOriented)
10784

10885
def solveRow(tileLeft: Tile): Vector[Tile] = {
10986
val border = tileLeft.borderRight
@@ -112,76 +89,77 @@ object Day20 {
11289
if (newTiles.size == 1) {
11390
val newTile = newTiles.head
11491
val newTileOriented = newTile.orientations.find(_.borderLeft == border).get
115-
newTileOriented +: solveRow(newTileOriented)
92+
solveRow1(newTileOriented)
11693
}
11794
else if (newTiles.isEmpty) {
11895
Vector.empty
11996
}
12097
else
121-
throw new IllegalArgumentException("duplicate new tiles")
98+
throw new IllegalArgumentException("ambiguous new tile")
12299
}
123100

101+
def solveRow1(tileLeft: Tile): Vector[Tile] = tileLeft +: solveRow(tileLeft)
102+
124103
def solve(tileTop: Tile): Grid[Tile] = {
125104
val border = tileTop.borderBottom
126105
//val newTiles = borderTiles(border).toSet - tileLeft
127106
val newTiles = borderTiles(border).toSet.filterNot(_.id == tileTop.id)
128107
if (newTiles.size == 1) {
129108
val newTile = newTiles.head
130109
val newTileOriented = newTile.orientations.find(_.borderTop == border).get
131-
(newTileOriented +: solveRow(newTileOriented)) +: solve(newTileOriented)
110+
solve1(newTileOriented)
132111
}
133112
else if (newTiles.isEmpty) {
134113
Vector.empty
135114
}
136115
else
137-
throw new IllegalArgumentException("duplicate new tiles")
116+
throw new IllegalArgumentException("ambiguous new tile")
138117
}
139118

140-
(cornerTopLeftOriented +: solveRow(cornerTopLeftOriented)) +: solve(cornerTopLeftOriented)
141-
}
119+
def solve1(tileTop: Tile): Grid[Tile] = solveRow1(tileTop) +: solve(tileTop)
142120

143-
def printGrid(grid: Grid[Boolean]): Unit = {
144-
for (row <- grid) {
145-
for (cell <- row)
146-
print(if (cell) '#' else '.')
147-
println()
148-
}
121+
val corners = findCorners(borderTiles)
122+
val cornerTopLeft = corners.head
123+
val cornerTopLeftBorders = getTileEdgeBorders(borderTiles)(cornerTopLeft) // TODO: don't repeat with findCorners
124+
val cornerTopLeftOriented = cornerTopLeft.orientations.find(tile => cornerTopLeftBorders.contains(tile.borderTop) && cornerTopLeftBorders.contains(tile.borderLeft)).get
125+
126+
solve1(cornerTopLeftOriented)
149127
}
150128

151-
private val seamonster =
152-
""" #.
129+
private val seaMonster =
130+
""" #
153131
|# ## ## ###
154132
| # # # # # # """.stripMargin
155133

156134
def checkSeaMonsters(tiles: Seq[Tile]): Int = {
157135
val solved = solvePuzzle(tiles)
158-
val grid = solved.mapGrid(_.innerGrid).flattenGrid // TODO: try all orientations
159-
//printGrid(grid)
136+
val grid = solved.mapGrid(_.innerGrid).flattenGrid
160137

161-
def grid2PosSet(grid: Grid[Boolean]): Set[Pos] = {
138+
// TODO: move this to library?
139+
def booleanGrid2Poss(grid: Grid[Boolean]): Set[Pos] = {
162140
(for {
163141
(row, y) <- grid.view.zipWithIndex
164142
(cell, x) <- row.view.zipWithIndex
165143
if cell
166144
} yield Pos(x, y)).toSet
167145
}
168146

169-
val monster = seamonster.linesIterator.map(_.toVector).toVector.mapGrid(_ == '#')
170-
val monsterPosSet = grid2PosSet(monster)
171-
172-
def doOrientation(grid: Grid[Boolean]): Option[Int] = {
173-
val gridPosSet = grid2PosSet(grid)
147+
val seaMonsterGrid = seaMonster.linesIterator.map(_.toVector).toVector.mapGrid(_ == '#')
148+
val seaMonsterPoss = booleanGrid2Poss(seaMonsterGrid)
149+
val seaMonsterSize = Pos(seaMonsterGrid.head.length, seaMonsterGrid.length)
174150

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(_ ++ _)
151+
def checkSeaMonstersGrid(grid: Grid[Boolean]): Option[Int] = {
152+
val gridPoss = booleanGrid2Poss(grid)
153+
val gridSize = Pos(grid.head.length, grid.length)
180154

181-
monsterPosSet2.map(s => (gridPosSet -- s).size)
155+
Box(Pos.zero, gridSize - seaMonsterSize - Pos(1, 1)).iterator
156+
.map(pos => seaMonsterPoss.map(pos + _))
157+
.filter(_.subsetOf(gridPoss))
158+
.reduceOption(_ ++ _)
159+
.map(seaMonsterPoss => (gridPoss -- seaMonsterPoss).size)
182160
}
183161

184-
grid.orientations.flatMap(doOrientation).head
162+
grid.orientations.flatMap(checkSeaMonstersGrid).head
185163
}
186164

187165
private val tileIdRegex = """Tile (\d+):""".r

0 commit comments

Comments
 (0)
0