--- a/day17.rb	Thu Apr 18 19:56:23 2024 +0100
+++ b/day17.rb	Fri Sep 20 20:06:21 2024 +0100
@@ -13,11 +13,15 @@
 Coord = Struct.new(:x, :y)
 Route = Struct.new(:steps, :distance)
 Routes = Struct.new(:routes, :min_distance)
+Colour = Struct.new(:r, :g, :b)
 
 city_map = File.open(file, "r").each_line(chomp: true).map{ |line| line.each_char.map(&:to_i)}
 
+$height = city_map.length
+$width = city_map[0].length
+
 start_space = Coord.new(0,0)
-end_space = Coord.new(city_map[0].length - 1, city_map.length - 1)
+end_space = Coord.new($width - 1, $height - 1)
 
 visited = {}
 routes = { start_space => Routes.new([Route.new([start_space], 0)], 0)}
@@ -31,10 +35,69 @@
 $left = Coord.new(-1, 0)
 $right = Coord.new(1, 0)
 
+# Our route is constrained to "four consecutive spaces". Zig-zag through the middle
+# obeys that rule and would be a worst case score.
+max_score = city_map.each_with_index.map {|row, i| i < row.length - 1 ? [row[i], row[i+1]] : [row[i]]}.flatten.reduce(:+)
+
+$colours = (0..max_score).map do |i|
+	# Use 300° because we don't want to be confused and loop back to red
+	angle = (i.to_f / max_score) * 300
+	if angle <= 60
+		r = 0xff
+		g = 0xff * angle / 60
+		b = 0
+	elsif angle <= 120
+		r = 0xff * (120 - angle) / 60
+		g = 0xff
+		b = 0
+	elsif angle <= 180
+		r = 0
+		g = 0xff
+		b = 0xff * (angle - 120) / 60
+	elsif angle <= 240
+		r = 0
+		g = 0xff * (240 - angle) / 60
+		b = 0xff
+	else
+		r = 0xff * (240 - angle) / 60
+		g = 0
+		b = 0xff
+	end
+	Colour.new(r.to_i, g.to_i, b.to_i)
+end
+
+
 def get_neighbours(city_map, x, y)
 	[$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 steps_since_turn(route)
+	if route.steps.length < 2
+		return 1
+	end
+#	puts "#{route}"
+	x_steps = 0
+	y_steps = 0
+	x_turned = false
+	y_turned = false
+	step_range = ..([6, route.length].max)
+	route.steps.reverse[step_range].each_cons(2) do |step_n, step_m|
+		x_diff = (step_n.x - step_m.x).abs
+		y_diff = (step_n.y - step_m.y).abs
+		if x_diff > 0 and ! x_turned
+			x_steps += 1
+		else
+			x_turned = true
+		end
+		if y_diff > 0 and ! y_turned
+			y_steps += 1
+		else
+			y_turned = true
+		end
+	end
+	(y_steps * 10) + x_steps
+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)}
@@ -47,7 +110,8 @@
 			!(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?
+	valid_routes = valid_routes + routes[next_node].routes unless routes[next_node].nil?
+	valid_routes = valid_routes.group_by {|route| steps_since_turn(route)}.values.map {|routes| routes.sort {|a,b| a.distance <=> b.distance}[0]}
 	Routes.new(valid_routes, valid_routes.map(&:distance).min)
 end
 
@@ -59,22 +123,49 @@
 	end
 end
 
+def update_map(new_node, map, routes)
+	routes_to_cell = routes[new_node]
+	up = $height - new_node.y
+	# We printed a new line, so we're already in column 0
+	forward = new_node.x
+	if routes_to_cell
+		colour = $colours[routes_to_cell.min_distance]
+		cell = map[new_node.y][new_node.x]
+		#puts [cell, new_node, $height, $width, up, forward, colour]
+		print "\e[s"
+		if forward > 0
+			print "\e[#{forward}C"
+		end
+		if up > 0
+			print "\e[#{up}A"
+		end
+		print "\e[48;2;#{colour.r};#{colour.g};#{colour.b}m#{cell}\e[0m\e[u"
+	end
+end
+
+puts "#{city_map.map {|row| row.join("")}.join("\n")}"
+sleep(5)
+
 until unvisited.empty?
-#	puts unvisited
+	#puts "Start loop: #{unvisited}"
+	#puts routes
 	min_node = nil
-#	min_node_direct_distance = Float::INFINITY
+	min_node_direct_distance = Float::INFINITY
 	unvisited.each do |node|
-#		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}"
+		x_dist = (end_space.x - node.x).abs
+		y_dist = (end_space.y - node.y).abs
+		direct_distance = x_dist + y_dist
+		node_route_distance = get_distance(routes, node) + direct_distance
+		min_node_route_distance = get_distance(routes, min_node) + min_node_direct_distance
+		#puts "Node? #{min_node} - #{get_distance(routes, node)} < #{get_distance(routes, min_node)} || #{direct_distance} < #{min_node_direct_distance}"
+		if min_node.nil? || node_route_distance < min_node_route_distance #|| (node_route_distance == min_node_route_distance && direct_distance < min_node_direct_distance)
 			min_node = node
-#			min_node_direct_distance = direct_distance
+			min_node_direct_distance = direct_distance
 		end
 	end
-#	puts unvisited.length
-	puts "Min node: #{min_node}"
+	#puts "Unvisited: #{unvisited.length}"
+	#puts "Min node: #{min_node} from #{unvisited.length}"
+	update_map(min_node, city_map, routes)
 
 	break if get_distance(routes, min_node) == Float::INFINITY or min_node == end_space
 
@@ -88,22 +179,27 @@
 
 	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
+	#puts "Delete #{min_node}"
+	#a = $stdin.gets("\n")
 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}"
+
+best_route = routes[end_space].routes.sort {|a, b| a.distance <=> b.distance}[0]
+
+best_route.steps.each do |step|
+	cell = city_map[step.y][step.x]
+	up = $height - step.y
+	forward = step.x
+	print "\e[s"
+	if forward > 0
+		print "\e[#{forward}C"
 	end
+	if up > 0
+		print "\e[#{up}A"
+	end
+	print "\e[1;30m\e[1;47m#{cell}\e[0m\e[u"
 end
-=end
+
+#puts "#{city_map.map {|row| row.join("")}.join("\n")}"
 
-puts routes[end_space].routes.sort {|a, b| a.distance <=> b.distance}[0]
+
 #puts "#{routes[end_space]}"
\ No newline at end of file