--- a/day17.rb	Sun Dec 17 10:32:05 2023 +0000
+++ b/day17.rb	Sun Dec 17 20:13:03 2023 +0000
@@ -1,5 +1,7 @@
 #! /usr/bin/env ruby
 
+require 'set'
+
 if ARGV.length != 1
         abort("Incorrect arguments - needs input file")
 elsif not File.exist? (ARGV[0])
@@ -9,42 +11,99 @@
 file = ARGV[0]
 
 Coord = Struct.new(:x, :y)
+Route = Struct.new(:steps, :distance)
+Routes = Struct.new(:routes, :min_distance)
 
 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
+start_space = Coord.new(0,0)
+end_space = Coord.new(city_map[0].length - 1, city_map.length - 1)
+
+visited = {}
+routes = { start_space => Routes.new([Route.new([start_space], 0)], 0)}
 
-visited = Array.new(city_map.length) {Array.new(city_map[0].length)}
+unvisited = Set.new
+unvisited << start_space
+#(0...city_map.length).each {|y| (0...city_map[0].length).each {|x| unvisited << Coord.new(x,y)}}
 
-unvisited = []
-(0...city_map.length).each {|y| (0...city_map[0].length).each {|x| unvisited << Coord.new(x,y)}}
+$up = Coord.new(0, -1)
+$down = Coord.new(0, 1)
+$left = Coord.new(-1, 0)
+$right = Coord.new(1, 0)
 
 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}
+	[$up, $down, $left, $right].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
+
+def allowed_routes(city_map, routes, cur_node, next_node)
+	next_step_distance = city_map[next_node.y][next_node.x]
+	candidate_routes = routes[cur_node].routes.map {|route| Route.new(route.steps + [next_node], route.distance + next_step_distance)}
+	valid_routes = candidate_routes.filter do |route|
+		looped = route.steps.count(next_node) > 1
+		if route.steps.length < 5
+			! looped
+		else
+			step_range = route.steps[-5..-2]
+			!(step_range.all?{|step| step.x == next_node.x} or step_range.all?{|step| step.y == next_node.y}) and !looped
+		end
+	end
+	valid_routes = valid_routes + routes[next_node].routes if !routes[next_node].nil?
+	Routes.new(valid_routes, valid_routes.map(&:distance).min)
+end
+
+def get_distance(routes, node)
+	if routes.key?(node)
+		routes[node].min_distance
+	else
+		Float::INFINITY
+	end
 end
 
 until unvisited.empty?
+#	puts unvisited
 	min_node = nil
+#	min_node_direct_distance = Float::INFINITY
 	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]
+#		x_dist = (end_space.x - node.x).abs
+#		y_dist = (end_space.y - node.y).abs
+#		direct_distance = x_dist * x_dist + y_dist * y_dist
+		if min_node.nil? || get_distance(routes, node) < get_distance(routes, min_node)# || direct_distance < min_node_direct_distance
+#			puts "#{get_distance(routes, node)} < #{get_distance(routes, min_node)} || #{direct_distance} < #{min_node_direct_distance}"
+			min_node = node
+#			min_node_direct_distance = direct_distance
+		end
+	end
+#	puts unvisited.length
+	puts "Min node: #{min_node}"
+
+	break if get_distance(routes, min_node) == Float::INFINITY or min_node == end_space
+
+	get_neighbours(city_map, min_node.x, min_node.y).each do |neighbour|
+		new_routes = allowed_routes(city_map, routes, min_node, neighbour)
+		if new_routes.routes.length > 0
+			routes[neighbour] = new_routes
+			unvisited << neighbour if !visited[neighbour]
 		end
 	end
 
-	break if distances[min_node.y][min_node.x] == Float::INFINITY
-
-	cur_distance = distances[min_node.y][min_node.x]
+	visited[min_node] = true
+	unvisited = unvisited.delete(min_node)
+#	puts "Delete #{min_node}"
+#	a = $stdin.gets("\n")
+end
+=begin
+city_map.length.times do |y|
+	city_map[0].length.times do |x|
+		print routes[Coord.new(x,y)].routes.map(&:distance).min.to_s.rjust(3) + " " + city_map[y][x].to_s + " |"
+	end
+	puts
+end
+city_map.length.times do |y|
+	city_map[0].length.times do |x|
+		puts "#{x},#{y} ⇒ #{routes[Coord.new(x,y)].routes.length} - #{routes[Coord.new(x,y)].routes.map(&:distance).minmax}"
+	end
+end
+=end
 
-	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]
+puts routes[end_space].routes.sort {|a, b| a.distance <=> b.distance}[0]
+#puts "#{routes[end_space]}"
\ No newline at end of file