--- 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