Mercurial > repos > other > adventofcode2023
diff 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 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/day17.rb Sun Dec 17 10:32:05 2023 +0000 @@ -0,0 +1,50 @@ +#! /usr/bin/env ruby + +if ARGV.length != 1 + abort("Incorrect arguments - needs input file") +elsif not File.exist? (ARGV[0]) + abort("File #{ARGV[0]} did not exist") +end + +file = ARGV[0] + +Coord = Struct.new(:x, :y) + +city_map = File.open(file, "r").each_line(chomp: true).map{ |line| line.each_char.map(&:to_i)} + +distances = Array.new(city_map.length) {Array.new(city_map[0].length) {Float::INFINITY}} +distances[0][0] = 0 + +visited = Array.new(city_map.length) {Array.new(city_map[0].length)} + +unvisited = [] +(0...city_map.length).each {|y| (0...city_map[0].length).each {|x| unvisited << Coord.new(x,y)}} + +def get_neighbours(city_map, x, y) + [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} +end + +until unvisited.empty? + min_node = nil + unvisited.each do |node| + if min_node.nil? || distances[node.y][node.x] < distances[min_node.y][min_node.x] + min_node = node unless visited[node.y][node.x] + end + end + + break if distances[min_node.y][min_node.x] == Float::INFINITY + + cur_distance = distances[min_node.y][min_node.x] + + get_neighbours(city_map, min_node.x, min_node.y).each do |neighbour| + value = city_map[neighbour.y][neighbour.x] + alt = cur_distance + value + distances[neighbour.y][neighbour.x] = alt if alt < distances[neighbour.y][neighbour.x] + end + + visited[min_node.y][min_node.x] = true + unvisited.delete(min_node) + distances +end + +puts distances[-1][-1]