commit e3c183033e6829f9ee1d3259430cdba48b473b59
parent dd52ea67739b8e0b7b3409f84f6b4583e4f23a02
Author: Decay <decay@todayiwilllaunchmyinfantsonintoorbit.com>
Date: Mon, 12 Dec 2022 16:42:46 -0800
Day 12 in Julia
Slow and inefficient, please do not copy this implementation of Dijkstra's
algorithm or you will be sad.
Diffstat:
| A | 12/12.jl | | | 108 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 108 insertions(+), 0 deletions(-)
diff --git a/12/12.jl b/12/12.jl
@@ -0,0 +1,108 @@
+function popmin!(avail, dist)
+ local min = ()
+ local mindist = length(dist)
+ for v in avail
+ if (dist[v[1], v[2]] < mindist)
+ mindist = dist[v[1], v[2]]
+ min = v
+ end
+ end
+ delete!(avail, min)
+ return min
+end
+
+# Slow and brute force implementation; would be much better using a priority queue implementation
+function dijkstra(map, width, height, startpos, searchbackward::Bool)
+ # Initialize our data structures
+ dist = Array{Int32, 2}(undef, height, width)
+ prev = Array{Tuple, 2}(undef, height, width)
+ avail = Set()
+ for row = 1:height
+ for col = 1:width
+ push!(avail, (row, col))
+ prev[row, col] = ()
+ if (row != startpos[1] || col != startpos[2])
+ dist[row, col] = (height * width) # Greater than max possible distance
+ else
+ dist[row, col] = 0
+ end
+ end
+ end
+
+ while length(avail) > 0
+ next = popmin!(avail, dist)
+
+ # Nothing else is accessible
+ if next == ()
+ return (dist, prev)
+ end
+
+ # Find all neighbors of next still in avail
+ for n in [(next[1] - 1, next[2]), (next[1] + 1, next[2]),
+ (next[1], next[2] - 1), (next[1], next[2] + 1)]
+ row = n[1]
+ col = n[2]
+ if row >= 1 && row <= height && col >= 1 && col <= width && in(n, avail)
+ if searchbackward
+ elevationok = (map[n[1]][n[2]] - map[next[1]][next[2]]) >= -1
+ else
+ elevationok = (map[n[1]][n[2]] - map[next[1]][next[2]]) <= 1
+ end
+ if elevationok
+ # There's a path to n from next
+ alt = dist[next[1], next[2]] + 1
+ if alt < dist[n[1], n[2]]
+ dist[n[1], n[2]] = alt
+ prev[n[1], n[2]] = next
+ end
+ end
+ end
+ end
+ end
+
+ return (dist, prev)
+end
+
+function dijkstra(map, width, height, startpos, endpos::Tuple)
+ (dist, prev) = dijkstra(map, width, height, startpos, false)
+
+ return dist[endpos[1], endpos[2]]
+end
+
+begin
+ map = open("input", "r") do input
+ readlines(input)
+ end
+ mapwidth = length(map[1])
+ mapheight = length(map)
+ local startrow = local startcol = local endrow = local endcol = 0
+ for row = 1:mapheight
+ for col = 1:mapwidth
+ if map[row][col] == 'S'
+ startrow = row
+ startcol = col
+ rowtochange = map[row]
+ map[row] = rowtochange[1:col - 1] * 'a' * rowtochange[col + 1:end]
+ elseif map[row][col] == 'E'
+ endrow = row
+ endcol = col
+ rowtochange = map[row]
+ map[row] = rowtochange[1:col - 1] * 'z' * rowtochange[col + 1:end]
+ end
+ end
+ end
+
+ dist = dijkstra(map, mapwidth, mapheight, (startrow, startcol), (endrow, endcol))
+ println("Shortest distance to E (star 1): ", dist)
+
+ (distmatrix, prev) = dijkstra(map, mapwidth, mapheight, (endrow, endcol), true)
+ local mindist = mapwidth * mapheight
+ for row = 1:mapheight
+ for col = 1:mapwidth
+ if map[row][col] == 'a' && distmatrix[row, col] < mindist
+ mindist = distmatrix[row, col]
+ end
+ end
+ end
+ println("Shortest distance to E from any starting point (star 2):", mindist)
+end
