Mercurial > repos > other > adventofcode2023

comparison day17.rb @ 39:0e17e4bd97a9 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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.
author IBBoard <dev@ibboard.co.uk>
date Sun, 22 Sep 2024 11:30:53 +0100
parents 8e92cb172e6b
children
comparison
equal deleted inserted replaced
38:8e92cb172e6b 39:0e17e4bd97a9
9 end 9 end
10 10
11 file = ARGV[0] 11 file = ARGV[0]
12 12
13 Coord = Struct.new(:x, :y) 13 Coord = Struct.new(:x, :y)
14 Route = Struct.new(:steps, :distance) 14 Node = Struct.new(:coords, :direction, :num_prev_steps)
15 Routes = Struct.new(:routes, :min_distance) 15 RouteNode = Struct.new(:node, :cost, :previous_node)
16
17 module Directions
18 UP = 0
19 LEFT = 1
20 DOWN = 2
21 RIGHT = 3
22 end
23
24 $up = Coord.new(0, -1)
25 $left = Coord.new(-1, 0)
26 $down = Coord.new(0, 1)
27 $right = Coord.new(1, 0)
28 directions = [$up, $left, $down, $right]
29
30 city_map = File.open(file, "r").each_line(chomp: true).map{ |line| line.each_char.map(&:to_i)}
31
32 routes = city_map.map {|row| row.map { (0..3).map { (0..2).map {nil}}}}
33
34 $width = city_map[0].length
35 $height = city_map.length
36
16 Colour = Struct.new(:r, :g, :b) 37 Colour = Struct.new(:r, :g, :b)
17 38
18 city_map = File.open(file, "r").each_line(chomp: true).map{ |line| line.each_char.map(&:to_i)} 39 start_space = Coord.new(0, 0)
19
20 $height = city_map.length
21 $width = city_map[0].length
22
23 start_space = Coord.new(0,0)
24 end_space = Coord.new($width - 1, $height - 1) 40 end_space = Coord.new($width - 1, $height - 1)
25 41
26 visited = {} 42 class PQueue
27 routes = { start_space => Routes.new([Route.new([start_space], 0)], 0)} 43 def initialize()
28 44 # Placeholder at the root to simplify calculations
29 unvisited = Set.new 45 @objects = [nil]
30 unvisited << start_space 46 end
31 #(0...city_map.length).each {|y| (0...city_map[0].length).each {|x| unvisited << Coord.new(x,y)}} 47
32 48 def push(element)
33 $up = Coord.new(0, -1) 49 new_idx = @objects.size
34 $down = Coord.new(0, 1) 50 @objects << element
35 $left = Coord.new(-1, 0) 51 _reorder_insert(new_idx)
36 $right = Coord.new(1, 0) 52 end
53
54 def _reorder_insert(idx)
55 parent_idx = idx / 2
56 if idx > 1 and @objects[parent_idx].cost > @objects[idx].cost
57 _swap(idx, parent_idx)
58 _reorder_insert(parent_idx)
59 end
60 end
61
62 def _swap(idx1, idx2)
63 @objects[idx2], @objects[idx1] = @objects[idx1], @objects[idx2]
64 end
65
66 def pop()
67 # Swap for easy popping without moving everything
68 _swap(1, @objects.size - 1)
69 priority_obj = @objects.pop
70 _reorder_remove(1)
71 priority_obj
72 end
73
74 def _reorder_remove(idx)
75 child1_idx = idx * 2
76 child2_idx = child1_idx + 1
77 last_idx = @objects.size - 1
78
79 if child1_idx <= last_idx
80 child1_val = @objects[child1_idx].cost
81 child2_val = child2_idx <= last_idx ? @objects[child2_idx].cost : Float::INFINITY
82 child_idx, child_val = child1_val < child2_val ? [child1_idx, child1_val] : [child2_idx, child2_val]
83
84 if @objects[idx].cost >= child_val
85 _swap(idx, child_idx)
86 _reorder_remove(child_idx)
87 end
88 end
89 end
90
91 def empty?
92 @objects.size <= 1
93 end
94
95 def to_s
96 @objects.map {|val| "#{val.coords.x},#{val.coords.y}=#{val.cost}" if val }
97 end
98 end
37 99
38 # Our route is constrained to "four consecutive spaces". Zig-zag through the middle 100 # Our route is constrained to "four consecutive spaces". Zig-zag through the middle
39 # obeys that rule and would be a worst case score. 101 # obeys that rule and it's either the shortest route _or_ we won't explore a longer route
40 max_score = city_map.each_with_index.map {|row, i| i < row.length - 1 ? [row[i], row[i+1]] : [row[i]]}.flatten.reduce(:+) 102 max_score = city_map.each_with_index.map {|row, i| i < row.length - 1 ? [row[i], row[i+1]] : [row[i]]}.flatten.reduce(:+)
41 103
42 $colours = (0..max_score).map do |i| 104 $colours = (0..max_score).map do |i|
43 # Use 300° because we don't want to be confused and loop back to red 105 angle = (i.to_f / max_score) * 360
44 angle = (i.to_f / max_score) * 300
45 if angle <= 60 106 if angle <= 60
46 r = 0xff 107 r = 0xff
47 g = 0xff * angle / 60 108 g = 0xff * angle / 60
48 b = 0 109 b = 0
49 elsif angle <= 120 110 elsif angle <= 120
56 b = 0xff * (angle - 120) / 60 117 b = 0xff * (angle - 120) / 60
57 elsif angle <= 240 118 elsif angle <= 240
58 r = 0 119 r = 0
59 g = 0xff * (240 - angle) / 60 120 g = 0xff * (240 - angle) / 60
60 b = 0xff 121 b = 0xff
61 else 122 elsif angle <= 300
62 r = 0xff * (240 - angle) / 60 123 r = 0xff * (240 - angle) / 60
63 g = 0 124 g = 0
64 b = 0xff 125 b = 0xff
126 else
127 r = 0xff
128 g = 0
129 b = 0xff * (360 - angle) / 60
65 end 130 end
66 Colour.new(r.to_i, g.to_i, b.to_i) 131 Colour.new(r.to_i, g.to_i, b.to_i)
67 end 132 end
68 133
69 134 def update_map(new_node, map)
70 def get_neighbours(city_map, x, y) 135 up = $height - new_node.node.coords.y
71 [$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}
72 end
73
74 def steps_since_turn(route)
75 if route.steps.length < 2
76 return 1
77 end
78 # puts "#{route}"
79 x_steps = 0
80 y_steps = 0
81 x_turned = false
82 y_turned = false
83 step_range = ..([6, route.length].max)
84 route.steps.reverse[step_range].each_cons(2) do |step_n, step_m|
85 x_diff = (step_n.x - step_m.x).abs
86 y_diff = (step_n.y - step_m.y).abs
87 if x_diff > 0 and ! x_turned
88 x_steps += 1
89 else
90 x_turned = true
91 end
92 if y_diff > 0 and ! y_turned
93 y_steps += 1
94 else
95 y_turned = true
96 end
97 end
98 (y_steps * 10) + x_steps
99 end
100
101 def allowed_routes(city_map, routes, cur_node, next_node)
102 next_step_distance = city_map[next_node.y][next_node.x]
103 candidate_routes = routes[cur_node].routes.map {|route| Route.new(route.steps + [next_node], route.distance + next_step_distance)}
104 valid_routes = candidate_routes.filter do |route|
105 looped = route.steps.count(next_node) > 1
106 if route.steps.length < 5
107 ! looped
108 else
109 step_range = route.steps[-5..-2]
110 !(step_range.all?{|step| step.x == next_node.x} or step_range.all?{|step| step.y == next_node.y}) and !looped
111 end
112 end
113 valid_routes = valid_routes + routes[next_node].routes unless routes[next_node].nil?
114 valid_routes = valid_routes.group_by {|route| steps_since_turn(route)}.values.map {|routes| routes.sort {|a,b| a.distance <=> b.distance}[0]}
115 Routes.new(valid_routes, valid_routes.map(&:distance).min)
116 end
117
118 def get_distance(routes, node)
119 if routes.key?(node)
120 routes[node].min_distance
121 else
122 Float::INFINITY
123 end
124 end
125
126 def update_map(new_node, map, routes)
127 routes_to_cell = routes[new_node]
128 up = $height - new_node.y
129 # We printed a new line after the map, so we're already in column 0 and go X forward (right) 136 # We printed a new line after the map, so we're already in column 0 and go X forward (right)
130 forward = new_node.x 137 forward = new_node.node.coords.x
131 if routes_to_cell 138 colour = $colours[new_node.cost]
132 colour = $colours[routes_to_cell.min_distance] 139 cell = map[new_node.node.coords.y][new_node.node.coords.x]
133 cell = map[new_node.y][new_node.x] 140 #puts [cell, new_node, $height, $width, up, forward, colour]
134 #puts [cell, new_node, $height, $width, up, forward, colour] 141 print "\e[s"
135 print "\e[s" 142 if forward > 0
136 if forward > 0 143 print "\e[#{forward}C"
137 print "\e[#{forward}C" 144 end
138 end 145 if up > 0
139 if up > 0 146 print "\e[#{up}A"
140 print "\e[#{up}A" 147 end
141 end 148 print "\e[48;2;#{colour.r};#{colour.g};#{colour.b}m#{cell}\e[0m\e[u"
142 print "\e[48;2;#{colour.r};#{colour.g};#{colour.b}m#{cell}\e[0m\e[u"
143 end
144 end 149 end
145 150
146 puts "#{city_map.map {|row| row.join("")}.join("\n")}" 151 puts "#{city_map.map {|row| row.join("")}.join("\n")}"
147 # sleep(5) # For screen recording 152 # sleep(5) # For screen recording
148 153
149 until unvisited.empty? 154 unvisited = PQueue.new
150 #puts "Start loop: #{unvisited}" 155 # Fake two starting steps from outside so that we use the "turn" logic to get
151 #puts routes 156 # routes with zero previous steps
152 min_node = nil 157 start_node_1 = RouteNode.new(Node.new(start_space, Directions::RIGHT, 0), 0, nil)
153 min_node_direct_distance = Float::INFINITY 158 start_node_2 = RouteNode.new(Node.new(start_space, Directions::DOWN, 0), 0, nil)
154 unvisited.each do |node| 159 unvisited.push(start_node_1)
155 x_dist = end_space.x - node.x 160 unvisited.push(start_node_2)
156 y_dist = end_space.y - node.y 161 visited = Set.new
157 direct_distance = x_dist + y_dist 162 candidate_node = nil
158 node_route_distance = get_distance(routes, node) + direct_distance 163
159 min_node_route_distance = get_distance(routes, min_node) + min_node_direct_distance 164 def is_shorter?(cur_shortest, new_node)
160 #puts "Node? #{min_node} - #{node_route_distance} < #{min_node_route_distance} || #{direct_distance} < #{min_node_direct_distance}" 165 not cur_shortest or cur_shortest.cost > new_node.cost
161 #sleep(1) 166 end
162 if min_node.nil? || node_route_distance < min_node_route_distance #|| (node_route_distance == min_node_route_distance && direct_distance < min_node_direct_distance) 167
163 min_node = node 168 def is_valid?(x, y)
164 min_node_direct_distance = direct_distance 169 0 <= x and x < $width and 0 <= y and y < $height
165 end 170 end
166 end 171
167 #puts "Unvisited: #{unvisited.length}" 172 while not unvisited.empty?
168 #puts "Min node: #{min_node} from #{unvisited.length}" 173 candidate_node = unvisited.pop
169 update_map(min_node, city_map, routes) 174 candidate_node_node = candidate_node.node
170 175
171 break if not routes.has_key?(min_node) or min_node == end_space 176 if visited.include?(candidate_node_node)
172 177 # Longer route to an already visited node
173 get_neighbours(city_map, min_node.x, min_node.y).each do |neighbour| 178 next
174 new_routes = allowed_routes(city_map, routes, min_node, neighbour) 179 end
175 if new_routes.routes.length > 0 180 visited.add(candidate_node_node)
176 routes[neighbour] = new_routes 181
177 unvisited << neighbour if !visited[neighbour] 182 candidate_coords = candidate_node_node.coords
178 end 183 update_map(candidate_node, city_map)
179 end 184
180 185
181 visited[min_node] = true 186 if candidate_coords == end_space
182 unvisited = unvisited.delete(min_node) 187 break
183 #puts "Delete #{min_node}" 188 end
184 #a = $stdin.gets("\n") 189
185 end 190 current_direction = candidate_node_node.direction
186 191
187 best_route = routes[end_space].routes.sort {|a, b| a.distance <=> b.distance}[0] 192 # We can always turn
188 193 anticlockwise = (current_direction + 1) % 4
189 best_route.steps.each do |step| 194 clockwise = (anticlockwise + 2) % 4
190 cell = city_map[step.y][step.x] 195
191 up = $height - step.y 196 next_steps = [
192 forward = step.x 197 [anticlockwise, 0],
193 print "\e[s" 198 [clockwise, 0]
194 if forward > 0 199 ]
195 print "\e[#{forward}C" 200 next_steps.append([current_direction, candidate_node_node.num_prev_steps + 1]) if candidate_node_node.num_prev_steps < 4
196 end 201
197 if up > 0 202 next_steps.each do |direction, num_prev_steps|
198 print "\e[#{up}A" 203 dir = directions[direction]
199 end 204 new_x = candidate_coords.x + dir.x
200 print "\e[1;30m\e[1;47m#{cell}\e[0m\e[u" 205 new_y = candidate_coords.y + dir.y
201 end 206 if is_valid?(new_x, new_y)
202 207 next_num_prev_steps = num_prev_steps + 1
203 puts best_route.distance 208 cur_shortest = routes[new_y][new_x][direction][next_num_prev_steps]
204 209 if is_shorter?(cur_shortest, candidate_node)
205 #puts "#{city_map.map {|row| row.join("")}.join("\n")}" 210 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)
206 211 routes[new_y][new_x][direction][next_num_prev_steps] = new_shortest
207 212 unvisited.push(new_shortest)
208 #puts "#{routes[end_space]}" 213 end
214 end
215 end
216 end
217
218 if candidate_node
219 route_node = candidate_node
220 coords = []
221 while route_node
222 coords.append(route_node.node.coords)
223 route_node = route_node.previous_node
224 end
225 coords.each do |step|
226 cell = city_map[step.y][step.x]
227 up = $height - step.y
228 forward = step.x
229 print "\e[s"
230 if forward > 0
231 print "\e[#{forward}C"
232 end
233 if up > 0
234 print "\e[#{up}A"
235 end
236 print "\e[1;30m\e[1;47m#{cell}\e[0m\e[u"
237 end
238 puts candidate_node.cost
239 end