8000 Solve 2024 day 16 part 2 · sim642/adventofcode@fea3aa0 · GitHub
[go: up one dir, main page]
Skip to content
10000

Commit fea3aa0

Browse files
sim642sim642
committed
Solve 2024 day 16 part 2
1 parent 8983af7 commit fea3aa0

File tree

2 files changed

+145
-1
lines changed

2 files changed

+145
-1
lines changed

‎src/main/scala/eu/sim642/adventofcode2024/Day16.scala

Lines changed: 136 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,13 @@
11
package eu.sim642.adventofcode2024
22

33
import eu.sim642.adventofcodelib.Grid
4-
import eu.sim642.adventofcodelib.graph.{Dijkstra, GraphSearch, TargetNode}
4+
import eu.sim642.adventofcodelib.graph.{Dijkstra, GraphSearch, GraphTraversal, TargetNode}
55
import eu.sim642.adventofcodelib.pos.Pos
66
import eu.sim642.adventofcodelib.GridImplicits.*
77
import eu.sim642.adventofcode2018.Day13.DirectionPos
88

9+
import scala.collection.mutable
10+
911
object Day16 {
1012

1113
case class Reindeer(pos: Pos, direction: Pos = Pos(1, 0))
@@ -32,11 +34,144 @@ object Day16 {
3234
Dijkstra.search(graphSearch).target.get._2
3335
}
3436

37+
/*def bestPathTiles(grid: Grid[Char]): Int = {
38+
val targetScore = lowestScore(grid)
39+
40+
val graphTraversal = new GraphTraversal[(List[Reindeer], Int)] {
41+
override val startNode: (List[Reindeer], Int) = (List(Reindeer(grid.posOf('S'))), 0)
42+
43+
override def neighbors(reindeers: (List[Reindeer], Int)): IterableOnce[((List[Reindeer], Int), Int)] = {
44+
val reindeer = reindeers._1.head
45+
println(reindeers._2)
46+
Seq(
47+
reindeer.copy(pos = reindeer.pos + reindeer.direction) -> 1,
48+
reindeer.copy(direction = reindeer.direction.left) -> 1000,
49+
reindeer.copy(direction = reindeer.direction.right) -> 1000,
50+
)
51+
.filter(reindeer => grid(reindeer._1.pos) != '#')
52+
.filter(p => reindeers._2 + p._2 <= targetScore)
53+
.map(p => (p._1 :: reindeers._1, reindeers._2 + p._2) -> p._2)
54+
}
55+
56+
}
57+
58+
val targetPos: Pos = grid.posOf('E')
59+
60+
Dijkstra.traverse(graphTraversal).nodes.filter(_._1.head.pos == targetPos).filter(_._2 == targetScore)
61+
.tapEach(println)
62+
.flatMap(_._1.map(_.pos)).toSet.size
63+
}*/
64+
65+
/*def bestPathTiles(grid: Grid[Char]): Int = {
66+
val targetScore = lowestScore(grid)
67+
68+
val graphSearch = new GraphSearch[Reindeer] {
69+
override val startNode: Reindeer = Reindeer(grid.posOf('S'))
70+
71+
override def neighbors(reindeer: Reindeer): IterableOnce[(Reindeer, Int)] = {
72+
Seq(
73+
reindeer.copy(pos = reindeer.pos + reindeer.direction) -> 1,
74+
reindeer.copy(direction = reindeer.direction.left) -> 1000,
75+
reindeer.copy(direction = reindeer.direction.right) -> 1000,
76+
)
77+
.filter(reindeer => grid(reindeer._1.pos) != '#')
78+
}
79+
80+
private val targetPos: Pos = grid.posOf('E')
81+
82+
override def isTargetNode(reindeer: Reindeer, dist: Int): Boolean = reindeer.pos == targetPos
83+
}
84+
val targetPos: Pos = grid.posOf('E')
85+
86+
val memo = mutable.Map.empty[(Reindeer, Set[Reindeer], Int), Set[Pos]]
87+
88+
def helper(reindeer: Reindeer, visited: Set[Reindeer], distance: Int): Set[Pos] = {
89+
memo.getOrElseUpdate((reindeer, visited, distance), {
90+
if (distance == targetScore && reindeer.pos == targetPos)
91+
visited.map(_.pos)
92+
else if (distance >= targetScore)
93+
Set.empty
94+
else {
95+
assert(distance < targetScore)
96+
(for {
97+
(newReindeer, step) <- graphSearch.neighbors(reindeer)
98+
if !visited(newReindeer)
99+
newDistance = distance + step
100+
if newDistance <= targetScore
101+
} yield helper(newReindeer, visited + newReindeer, newDistance)).foldLeft(Set.empty)(_ ++ _)
102+
}
103+
})
104+
}
105+
106+
val s = helper(graphSearch.startNode, Set.empty, 0)
107+
println(s)
108+
109+
for ((row, y) <- grid.zipWithIndex) {
110+
for ((cell, x) <- row.zipWithIndex) {
111+
if (s(Pos(x, y)))
112+
print('O')
113+
else
114+
print(cell)
115+
}
116+
println()
117+
}
118+
119+
s.size
120+
}*/
121+
122+
def bestPathTiles(grid: Grid[Char] 57AE ): Int = {
123+
val graphSearch = new GraphSearch[Reindeer] {
124+
override val startNode: Reindeer = Reindeer(grid.posOf('S'))
125+
126+
override def neighbors(reindeer: Reindeer): IterableOnce[(Reindeer, Int)] = {
127+
Seq(
128+
reindeer.copy(pos = reindeer.pos + reindeer.direction) -> 1,
129+
reindeer.copy(direction = reindeer.direction.left) -> 1000,
130+
reindeer.copy(direction = reindeer.direction.right) -> 1000,
131+
)
132+
.filter(reindeer => grid(reindeer._1.pos) != '#')
133+
}
134+
135+
private val targetPos: Pos = grid.posOf('E')
136+
137+
override def isTargetNode(reindeer: Reindeer, dist: Int): Boolean = reindeer.pos == targetPos
138+
}
139+
140+
def backNeighbors(reindeer: Reindeer): IterableOnce[(Reindeer, Int)] = {
141+
Seq(
142+
reindeer.copy(pos = reindeer.pos - reindeer.direction) -> 1,
143+
reindeer.copy(direction = reindeer.direction.left) -> 1000,
144+
reindeer.copy(direction = reindeer.direction.right) -> 1000,
145+
)
146+
.filter(reindeer => grid(reindeer._1.pos) != '#')
147+
}
148+
149+
val graphResult = Dijkstra.search(graphSearch)
150+
151+
def helper(reindeer: Reindeer): Set[Pos] = {
152+
if (reindeer == graphSearch.startNode)
153+
Set(reindeer.pos)
154+
else {
155+
val distance = graphResult.distances(reindeer)
156+
val x = for {
157+
(oldReindeer, step) <- backNeighbors(reindeer)
158+
oldDistance <- graphResult.distances.get(oldReindeer)
159+
if oldDistance + step == distance
160+
} yield helper(oldReindeer) + reindeer.pos
161+
162+
x.foldLeft(Set.empty)(_ ++ _)
163+
}
164+
}
165+
166+
helper(graphResult.target.get._1).size
167+
}
168+
35169
def parseGrid(input: String): Grid[Char] = input.linesIterator.map(_.toVector).toVector
36170

37171
lazy val input: String = scala.io.Source.fromInputStream(getClass.getResourceAsStream("day16.txt")).mkString.trim
38172

39173
def main(args: Array[String]): Unit = {
40174
println(lowestScore(parseGrid(input)))
175+
println(bestPathTiles(parseGrid(input)))
41176
}
42177
}

‎src/test/scala/eu/sim642/adventofcode2024/Day16Test.scala

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -49,4 +49,13 @@ class Day16Test extends AnyFunSuite {
4949
test("Part 1 input answer") {
5050
assert(lowestScore(parseGrid(input)) == 73404)
5151
}
52+
53+
test("Part 2 examples") {
54+
assert(bestPathTiles(parseGrid(exampleInput)) == 45)
55+
assert(bestPathTiles(parseGrid(exampleInput2)) == 64)
56+
}
57+
58+
test("Part 2 input answer") {
59+
assert(bestPathTiles(parseGrid(input)) == 449)
60+
}
5261
}

0 commit comments

Comments
 (0)
0