Mercurial > repos > other > adventofcode2023

comparison day23.rb @ 33:676461cc3a70

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
32:a1b748f2c416 33:676461cc3a70
1 #! /usr/bin/env ruby 1 #! /usr/bin/env ruby
2
3 require 'set'
2 4
3 if ARGV.length != 1 and ARGV.length != 2 5 if ARGV.length != 1 and ARGV.length != 2
4 abort("Incorrect arguments - needs input file and optional second arg") 6 abort("Incorrect arguments - needs input file and optional second arg")
5 elsif not File.exist? (ARGV[0]) 7 elsif not File.exist? (ARGV[0])
6 abort("File #{ARGV[0]} did not exist") 8 abort("File #{ARGV[0]} did not exist")
15 17
16 $maze_width = 0...maze[0].length 18 $maze_width = 0...maze[0].length
17 $maze_height = 0...maze.length 19 $maze_height = 0...maze.length
18 $can_climb_hills = ARGV.length == 2 20 $can_climb_hills = ARGV.length == 2
19 21
20 open_routes = [[start_pos]] 22 open_segments = [[start_pos]]
21 23 segments = Hash.new
22 distances = Array.new(maze.length) {Array.new(maze[0].length) {Hash.new}}
23 24
24 $moves = [[0,1], [0,-1], [1,0], [-1,0]] 25 $moves = [[0,1], [0,-1], [1,0], [-1,0]]
25 26
26 def valid_move(move, space, maze) 27 def valid_move(move, space, maze)
27 if $maze_width.cover?(space[0]) && $maze_height.cover?(space[1]) 28 if $maze_width.cover?(space[0]) && $maze_height.cover?(space[1])
46 end.filter do |move, new_space| 47 end.filter do |move, new_space|
47 valid_move(move, new_space, maze) && !route.include?(new_space) 48 valid_move(move, new_space, maze) && !route.include?(new_space)
48 end 49 end
49 end 50 end
50 51
51 while open_routes != [] 52 def add_segment(segments, start_step, end_step, route_length)
52 num_routes = open_routes.length 53 current_segments = segments.key?(start_step) ? segments[start_step] : []
53 open_routes = open_routes.flat_map do |route| 54 current_segments << [end_step, route_length]
54 next_steps(route, maze).map do |move, next_step| 55 segments[start_step] = current_segments
55 new_route = route + [next_step]
56 # Simple "distance to this point" doesn't work when if can approach from different
57 # directions, because the other route may be shorter to here but longer to the end
58 # so we use the movement direction to track different directionality
59 current_distances = distances[next_step[1]][next_step[0]]
60 if !current_distances.key?(move) || new_route.length > current_distances[move]
61 distances[next_step[1]][next_step[0]][move] = new_route.length
62 new_route
63 else
64 # We have a longer route to this space in this direction, so prune
65 nil
66 end
67 end.filter {|route| !route.nil?}
68 end
69 # if open_routes.length != num_routes
70 # puts "Now have:"
71 # open_routes.each {|route| puts " * #{route.length} to #{route[-1]}"}
72 # end
73 end 56 end
74 57
75 # Subtract 1 because we don't count the first step 58 while open_segments != []
76 puts "#{distances[end_pos[1]][end_pos[0]].values.max - 1}" 59 open_segments = open_segments.flat_map do |route|
60 candidate_steps = next_steps(route, maze)
61 if candidate_steps.length > 1
62 been_here_before = segments.key?(route[-1])
63 # We got to a fork - record the segment
64 if $can_climb_hills
65 add_segment(segments, route[-1], route[0], route.length)
66 end
67 add_segment(segments, route[0], route[-1], route.length)
68 if ! been_here_before
69 # Start some new segments
70 candidate_steps.map do |move, step|
71 [route[-1], step]
72 end
73 else
74 # Else we've already explored to this fork from another direction, so we can stop
75 []
76 end
77 else
78 # We're following a corridor
79 candidate_steps.filter do |move, step|
80 if step == end_pos
81 # We got to the end - record the segment
82 add_segment(segments, route[0], step, route.length + 1)
83 false
84 else
85 true
86 end
87 end.map do |move, step|
88 route + [step]
89 end
90 end
91 end
92 end
93
94 open_routes = [[[start_pos], 0]]
95 routes = []
96
97 while open_routes.length > 0
98 open_routes = open_routes.flat_map do |route|
99 segments[route[0][-1]].filter do |segment|
100 if segment[0] == end_pos
101 #puts "Add route #{routes.length}: #{route[0] + [segment[0]]} = #{route[1] + segment[1]}"
102 routes << route[1] + segment[1]
103 false
104 else
105 !route[0].include?(segment[0]) && !route[0].include?([segment[0]])
106 end
107 end.map do |segment|
108 # Subtract the overlapping node
109 [route[0] + [segment[0]], route[1] + segment[1] - 1]
110 end
111 end
112 open_routes = Set.new(open_routes)
113 end
114
115 longest_route = routes.max
116 # Subtract the start node
117 puts "#{routes.length} routes - max length #{longest_route - 1}"