# HG changeset patch
# User IBBoard <dev@ibboard.co.uk>
# Date 1727001053 -3600
# Node ID 0e17e4bd97a9e1b0b3847451877ef1858c1a3038
# Parent  8e92cb172e6bd9656a3313d47813d39a05b7cb87
Rewrite as four-dimensional route finding

The grid isn't just a 2D grid. The constraints make it 4D:
* X
* Y
* Last direction
* Number of steps in that direction

By tracking all four dimensions, we can find the shortest route
for _all_ combinations of the constraint. Previously, we were dropping
routes that were currently longer but ended up shorter because
they could take subsequent steps that other routes couldn't.

diff -r 8e92cb172e6b -r 0e17e4bd97a9 day17.rb
--- a/day17.rb	Fri Sep 20 20:30:11 2024 +0100
+++ b/day17.rb	Sun Sep 22 11:30:53 2024 +0100
@@ -11,37 +11,98 @@
 file = ARGV[0]
 
 Coord = Struct.new(:x, :y)
-Route = Struct.new(:steps, :distance)
-Routes = Struct.new(:routes, :min_distance)
-Colour = Struct.new(:r, :g, :b)
+Node = Struct.new(:coords, :direction, :num_prev_steps)
+RouteNode = Struct.new(:node, :cost, :previous_node)
+
+module Directions
+        UP = 0
+        LEFT = 1
+        DOWN = 2
+        RIGHT = 3
+end
+
+$up = Coord.new(0, -1)
+$left = Coord.new(-1, 0)
+$down = Coord.new(0, 1)
+$right = Coord.new(1, 0)
+directions = [$up, $left, $down, $right]
 
 city_map = File.open(file, "r").each_line(chomp: true).map{ |line| line.each_char.map(&:to_i)}
 
-$height = city_map.length
+routes = city_map.map {|row| row.map { (0..3).map { (0..2).map {nil}}}}
+
 $width = city_map[0].length
+$height = city_map.length
 
-start_space = Coord.new(0,0)
+Colour = Struct.new(:r, :g, :b)
+
+start_space = Coord.new(0, 0)
 end_space = Coord.new($width - 1, $height - 1)
 
-visited = {}
-routes = { start_space => Routes.new([Route.new([start_space], 0)], 0)}
+class PQueue
+        def initialize()
+                # Placeholder at the root to simplify calculations
+                @objects = [nil]
+        end
+
+        def push(element)
+                new_idx = @objects.size
+                @objects << element
+                _reorder_insert(new_idx)
+        end
+
+        def _reorder_insert(idx)
+                parent_idx = idx / 2
+                if idx > 1 and @objects[parent_idx].cost > @objects[idx].cost
+                        _swap(idx, parent_idx)
+                        _reorder_insert(parent_idx)
+                end
+        end
+
+        def _swap(idx1, idx2)
+                @objects[idx2], @objects[idx1] = @objects[idx1], @objects[idx2]
+        end
 
-unvisited = Set.new
-unvisited << start_space
-#(0...city_map.length).each {|y| (0...city_map[0].length).each {|x| unvisited << Coord.new(x,y)}}
+        def pop()
+                # Swap for easy popping without moving everything
+                _swap(1, @objects.size - 1)
+                priority_obj = @objects.pop
+                _reorder_remove(1)
+                priority_obj
+        end
+
+        def _reorder_remove(idx)
+                child1_idx = idx * 2
+                child2_idx = child1_idx + 1
+                last_idx = @objects.size - 1
 
-$up = Coord.new(0, -1)
-$down = Coord.new(0, 1)
-$left = Coord.new(-1, 0)
-$right = Coord.new(1, 0)
+                if child1_idx <= last_idx
+                        child1_val = @objects[child1_idx].cost
+                        child2_val = child2_idx <= last_idx ? @objects[child2_idx].cost : Float::INFINITY
+                        child_idx, child_val =  child1_val < child2_val ? [child1_idx, child1_val] : [child2_idx, child2_val]
+
+                        if @objects[idx].cost >= child_val
+                                _swap(idx, child_idx)
+                                _reorder_remove(child_idx)
+                        end
+                end
+        end
+
+        def empty?
+                @objects.size <= 1
+        end
+
+        def to_s
+                @objects.map {|val| "#{val.coords.x},#{val.coords.y}=#{val.cost}" if val }
+        end
+end
 
 # Our route is constrained to "four consecutive spaces". Zig-zag through the middle
-# obeys that rule and would be a worst case score.
+# obeys that rule and it's either the shortest route _or_ we won't explore a longer route
 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
+	angle = (i.to_f / max_score) * 360
 	if angle <= 60
 		r = 0xff
 		g = 0xff * angle / 60
@@ -58,151 +119,121 @@
 		r = 0
 		g = 0xff * (240 - angle) / 60
 		b = 0xff
-	else
+	elsif angle <= 300
 		r = 0xff * (240 - angle) / 60
 		g = 0
 		b = 0xff
+	else
+		r = 0xff
+		g = 0
+		b = 0xff * (360 - angle) / 60
 	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)}
-	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 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
-
-def get_distance(routes, node)
-	if routes.key?(node)
-		routes[node].min_distance
-	else
-		Float::INFINITY
-	end
-end
-
-def update_map(new_node, map, routes)
-	routes_to_cell = routes[new_node]
-	up = $height - new_node.y
+def update_map(new_node, map)
+	up = $height - new_node.node.coords.y
 	# We printed a new line after the map, so we're already in column 0 and go X forward (right)
-	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
+	forward = new_node.node.coords.x
+        colour = $colours[new_node.cost]
+        cell = map[new_node.node.coords.y][new_node.node.coords.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
 
 puts "#{city_map.map {|row| row.join("")}.join("\n")}"
 # sleep(5)  # For screen recording
 
-until unvisited.empty?
-	#puts "Start loop: #{unvisited}"
-	#puts routes
-	min_node = nil
-	min_node_direct_distance = Float::INFINITY
-	unvisited.each do |node|
-		x_dist = end_space.x - node.x
-		y_dist = end_space.y - node.y
-		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} - #{node_route_distance} < #{min_node_route_distance} || #{direct_distance} < #{min_node_direct_distance}"
-		#sleep(1)
-		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
-		end
-	end
-	#puts "Unvisited: #{unvisited.length}"
-	#puts "Min node: #{min_node} from #{unvisited.length}"
-	update_map(min_node, city_map, routes)
+unvisited = PQueue.new
+# Fake two starting steps from outside so that we use the "turn" logic to get
+# routes with zero previous steps
+start_node_1 = RouteNode.new(Node.new(start_space, Directions::RIGHT, 0), 0, nil)
+start_node_2 = RouteNode.new(Node.new(start_space, Directions::DOWN, 0), 0, nil)
+unvisited.push(start_node_1)
+unvisited.push(start_node_2)
+visited = Set.new
+candidate_node = nil
 
-	break if not routes.has_key?(min_node) or min_node == end_space
+def is_shorter?(cur_shortest, new_node)
+        not cur_shortest or cur_shortest.cost > new_node.cost
+end
 
-	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
-
-	visited[min_node] = true
-	unvisited = unvisited.delete(min_node)
-	#puts "Delete #{min_node}"
-	#a = $stdin.gets("\n")
+def is_valid?(x, y)
+        0 <= x and x  < $width and 0 <= y and y < $height
 end
 
-best_route = routes[end_space].routes.sort {|a, b| a.distance <=> b.distance}[0]
+while not unvisited.empty?
+        candidate_node = unvisited.pop
+        candidate_node_node = candidate_node.node
+
+        if visited.include?(candidate_node_node)
+                # Longer route to an already visited node
+                next
+        end
+        visited.add(candidate_node_node)
+
+        candidate_coords = candidate_node_node.coords
+        update_map(candidate_node, city_map)
+
+
+        if candidate_coords == end_space
+                break
+        end
+
+        current_direction = candidate_node_node.direction
 
-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"
+        # We can always turn
+        anticlockwise = (current_direction + 1) % 4
+        clockwise = (anticlockwise + 2) % 4
+
+        next_steps = [
+                [anticlockwise, 0],
+                [clockwise, 0]
+        ]
+        next_steps.append([current_direction, candidate_node_node.num_prev_steps + 1]) if candidate_node_node.num_prev_steps < 4
+
+        next_steps.each do |direction, num_prev_steps|
+                dir = directions[direction]
+                new_x = candidate_coords.x + dir.x
+                new_y = candidate_coords.y + dir.y
+                if is_valid?(new_x, new_y)
+                        next_num_prev_steps = num_prev_steps + 1
+                        cur_shortest = routes[new_y][new_x][direction][next_num_prev_steps]
+                        if is_shorter?(cur_shortest, candidate_node)
+                                new_shortest = RouteNode.new(Node.new(Coord.new(new_x, new_y), direction, next_num_prev_steps), candidate_node.cost + city_map[new_y][new_x], candidate_node)
+                                routes[new_y][new_x][direction][next_num_prev_steps] = new_shortest
+                                unvisited.push(new_shortest)
+                        end
+                end
+        end
 end
 
-puts best_route.distance
-
-#puts "#{city_map.map {|row| row.join("")}.join("\n")}"
-
-
-#puts "#{routes[end_space]}"
\ No newline at end of file
+if candidate_node
+        route_node = candidate_node
+        coords = []
+        while route_node
+                coords.append(route_node.node.coords)
+                route_node = route_node.previous_node
+        end
+        coords.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
+        puts candidate_node.cost
+end
\ No newline at end of file