Mercurial > repos > other > adventofcode2023

annotate day17.rb @ 25:79dc2ba41df2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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]