# HG changeset patch
# User IBBoard <dev@ibboard.co.uk>
# Date 1704379944 0
# Node ID 676461cc3a70b81f7c37cdeec14f1225b30b8578
# Parent  a1b748f2c41635cf9c183c47f97ae8d963b0a1a9
Day 23 - track segments, not each space

This allows us to explore the branches once then do quicker calculations
for valid route lengths. But still requires exploring 1,262,816 routes
to find the longest!

diff -r a1b748f2c416 -r 676461cc3a70 day23.rb
--- a/day23.rb	Thu Jan 04 11:18:56 2024 +0000
+++ b/day23.rb	Thu Jan 04 14:52:24 2024 +0000
@@ -1,5 +1,7 @@
 #! /usr/bin/env ruby
 
+require 'set'
+
 if ARGV.length != 1 and ARGV.length != 2
     abort("Incorrect arguments - needs input file and optional second arg")
 elsif not File.exist? (ARGV[0])
@@ -17,9 +19,8 @@
 $maze_height = 0...maze.length
 $can_climb_hills = ARGV.length == 2
 
-open_routes = [[start_pos]]
-
-distances = Array.new(maze.length) {Array.new(maze[0].length) {Hash.new}}
+open_segments = [[start_pos]]
+segments = Hash.new
 
 $moves = [[0,1], [0,-1], [1,0], [-1,0]]
 
@@ -48,29 +49,69 @@
     end
 end
 
-while open_routes != []
-    num_routes = open_routes.length
-    open_routes = open_routes.flat_map do |route|
-        next_steps(route, maze).map do |move, next_step|
-            new_route = route + [next_step]
-            # Simple "distance to this point" doesn't work when if can approach from different
-            # directions, because the other route may be shorter to here but longer to the end
-            # so we use the movement direction to track different directionality
-            current_distances = distances[next_step[1]][next_step[0]]
-            if !current_distances.key?(move) || new_route.length > current_distances[move]
-                distances[next_step[1]][next_step[0]][move] = new_route.length
-                new_route
-            else
-                # We have a longer route to this space in this direction, so prune
-                nil
-            end
-        end.filter {|route| !route.nil?}
-    end
-    # if open_routes.length != num_routes
-    #     puts "Now have:"
-    #     open_routes.each {|route| puts "  * #{route.length} to #{route[-1]}"}
-    # end
+def add_segment(segments, start_step, end_step, route_length)
+    current_segments = segments.key?(start_step) ? segments[start_step] : []
+    current_segments << [end_step, route_length]
+    segments[start_step] = current_segments
 end
 
-# Subtract 1 because we don't count the first step
-puts "#{distances[end_pos[1]][end_pos[0]].values.max - 1}"
\ No newline at end of file
+while open_segments != []
+    open_segments = open_segments.flat_map do |route|
+        candidate_steps = next_steps(route, maze)
+        if candidate_steps.length > 1
+            been_here_before = segments.key?(route[-1])
+            # We got to a fork - record the segment
+            if $can_climb_hills
+                add_segment(segments, route[-1], route[0], route.length)
+            end
+            add_segment(segments, route[0], route[-1], route.length)
+            if ! been_here_before
+                # Start some new segments
+                candidate_steps.map do |move, step|
+                    [route[-1], step]
+                end
+            else
+                # Else we've already explored to this fork from another direction, so we can stop
+                []
+            end
+        else
+            # We're following a corridor
+            candidate_steps.filter do |move, step|
+                if step == end_pos
+                    # We got to the end - record the segment
+                    add_segment(segments, route[0], step, route.length + 1)
+                    false
+                else
+                    true
+                end
+            end.map do |move, step|
+                route + [step]
+            end
+        end
+    end
+end
+
+open_routes = [[[start_pos], 0]]
+routes = []
+
+while open_routes.length > 0
+    open_routes = open_routes.flat_map do |route|
+        segments[route[0][-1]].filter do |segment|
+            if segment[0] == end_pos
+                #puts "Add route #{routes.length}: #{route[0] + [segment[0]]} = #{route[1] + segment[1]}"
+                routes << route[1] + segment[1]
+                false
+            else
+                !route[0].include?(segment[0]) && !route[0].include?([segment[0]])
+            end
+        end.map do |segment|
+            # Subtract the overlapping node
+            [route[0] + [segment[0]], route[1] + segment[1] - 1]
+        end
+    end
+    open_routes = Set.new(open_routes)
+end
+
+longest_route = routes.max
+# Subtract the start node
+puts "#{routes.length} routes - max length #{longest_route - 1}"
\ No newline at end of file