# HG changeset patch
# User IBBoard <dev@ibboard.co.uk>
# Date 1702809125 0
# Node ID 79dc2ba41df2c188cffe66ceaa2a4f97cb1d0ee2
# Parent  19481b06146177513b19e0f970a9742a00482c56
Copy a Dijkstra's Algorithm implementation

Gets us the shorted route but doesn't handle the additional
"keep turning" conditions

diff -r 19481b061461 -r 79dc2ba41df2 day17.rb
--- /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]
diff -r 19481b061461 -r 79dc2ba41df2 day17.txt
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/day17.txt	Sun Dec 17 10:32:05 2023 +0000
@@ -0,0 +1,43 @@
+--- Day 17: Clumsy Crucible ---
+
+A route finding puzzle with the following constraints:
+
+* Reduce the sum of values walked (the "cost" of the route)
+* Do not go in a straight line for more than three blocks
+* Don't count the starting square (unless you return to it)
+
+Start at the top-left and move to the bottom-right
+
+Given:
+
+2413432311323
+3215453535623
+3255245654254
+3446585845452
+4546657867536
+1438598798454
+4457876987766
+3637877979653
+4654967986887
+4564679986453
+1224686865563
+2546548887735
+4322674655533
+
+We could go:
+
+2>>34^>>>1323
+32v>>>35v5623
+32552456v>>54
+3446585845v52
+4546657867v>6
+14385987984v4
+44578769877v6
+36378779796v>
+465496798688v
+456467998645v
+12246868655<v
+25465488877v5
+43226746555v>
+
+This path never moves more than three consecutive blocks in the same direction and incurs a heat loss of only 102.
\ No newline at end of file