changeset 33:676461cc3a70

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!
author IBBoard <dev@ibboard.co.uk>
date Thu, 04 Jan 2024 14:52:24 +0000
parents a1b748f2c416
children 59620bbc4084
files day23.rb
diffstat 1 files changed, 68 insertions(+), 27 deletions(-) [+]
line wrap: on
line diff
--- 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