Mercurial > repos > other > adventofcode2023
annotate day17.rb @ 25:79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
Gets us the shorted route but doesn't handle the additional
"keep turning" conditions
author | IBBoard <dev@ibboard.co.uk> |
---|---|
date | Sun, 17 Dec 2023 10:32:05 +0000 |
parents | |
children | eb6c3a7d2f72 |
rev | line source |
---|---|
25
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
1 #! /usr/bin/env ruby |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
2 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
3 if ARGV.length != 1 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
4 abort("Incorrect arguments - needs input file") |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
5 elsif not File.exist? (ARGV[0]) |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
6 abort("File #{ARGV[0]} did not exist") |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
7 end |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
8 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
9 file = ARGV[0] |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
10 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
11 Coord = Struct.new(:x, :y) |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
12 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
13 city_map = File.open(file, "r").each_line(chomp: true).map{ |line| line.each_char.map(&:to_i)} |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
14 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
15 distances = Array.new(city_map.length) {Array.new(city_map[0].length) {Float::INFINITY}} |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
16 distances[0][0] = 0 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
17 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
18 visited = Array.new(city_map.length) {Array.new(city_map[0].length)} |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
19 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
20 unvisited = [] |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
21 (0...city_map.length).each {|y| (0...city_map[0].length).each {|x| unvisited << Coord.new(x,y)}} |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
22 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
23 def get_neighbours(city_map, x, y) |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
24 [Coord.new(-1,0), Coord.new(1,0), Coord.new(0,-1), Coord.new(0,1)].map {|coord| Coord.new(coord.x + x, coord.y + y)}.filter {|coord| coord.x >= 0 and coord.y >= 0 and coord.x < city_map[0].length and coord.y < city_map.length} |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
25 end |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
26 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
27 until unvisited.empty? |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
28 min_node = nil |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
29 unvisited.each do |node| |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
30 if min_node.nil? || distances[node.y][node.x] < distances[min_node.y][min_node.x] |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
31 min_node = node unless visited[node.y][node.x] |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
32 end |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
33 end |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
34 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
35 break if distances[min_node.y][min_node.x] == Float::INFINITY |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
36 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
37 cur_distance = distances[min_node.y][min_node.x] |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
38 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
39 get_neighbours(city_map, min_node.x, min_node.y).each do |neighbour| |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
40 value = city_map[neighbour.y][neighbour.x] |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
41 alt = cur_distance + value |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
42 distances[neighbour.y][neighbour.x] = alt if alt < distances[neighbour.y][neighbour.x] |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
43 end |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
44 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
45 visited[min_node.y][min_node.x] = true |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
46 unvisited.delete(min_node) |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
47 distances |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
48 end |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
49 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
50 puts distances[-1][-1] |