Mercurial > repos > other > adventofcode2023

annotate 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
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
25
79dc2ba41df2 Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
1 #! /usr/bin/env ruby
79dc2ba41df2 Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
2
26
eb6c3a7d2f72 Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents: 25
diff changeset
3 require 'set'
eb6c3a7d2f72 Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents: 25
diff changeset
4
25
79dc2ba41df2 Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
5 if ARGV.length != 1
79dc2ba41df2 Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
6 abort("Incorrect arguments - needs input file")
79dc2ba41df2 Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
7 elsif not File.exist? (ARGV[0])
79dc2ba41df2 Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
8 abort("File #{ARGV[0]} did not exist")
79dc2ba41df2 Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
9 end
79dc2ba41df2 Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
10
79dc2ba41df2 Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
11 file = ARGV[0]
79dc2ba41df2 Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
12
79dc2ba41df2 Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
13 Coord = Struct.new(:x, :y)
39
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
14 Node = Struct.new(:coords, :direction, :num_prev_steps)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
15 RouteNode = Struct.new(:node, :cost, :previous_node)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
16
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
17 module Directions
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
18 UP = 0
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
19 LEFT = 1
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
20 DOWN = 2
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
21 RIGHT = 3
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
22 end
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
23
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
24 $up = Coord.new(0, -1)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
25 $left = Coord.new(-1, 0)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
26 $down = Coord.new(0, 1)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
27 $right = Coord.new(1, 0)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
28 directions = [$up, $left, $down, $right]
25
79dc2ba41df2 Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
29
79dc2ba41df2 Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
30 city_map = File.open(file, "r").each_line(chomp: true).map{ |line| line.each_char.map(&:to_i)}
79dc2ba41df2 Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
31
39
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
32 routes = city_map.map {|row| row.map { (0..3).map { (0..2).map {nil}}}}
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
33
37
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
34 $width = city_map[0].length
39
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
35 $height = city_map.length
37
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
36
39
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
37 Colour = Struct.new(:r, :g, :b)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
38
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
39 start_space = Coord.new(0, 0)
37
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
40 end_space = Coord.new($width - 1, $height - 1)
26
eb6c3a7d2f72 Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents: 25
diff changeset
41
39
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
42 class PQueue
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
43 def initialize()
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
44 # Placeholder at the root to simplify calculations
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
45 @objects = [nil]
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
46 end
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
47
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
48 def push(element)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
49 new_idx = @objects.size
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
50 @objects << element
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
51 _reorder_insert(new_idx)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
52 end
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
53
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
54 def _reorder_insert(idx)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
55 parent_idx = idx / 2
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
56 if idx > 1 and @objects[parent_idx].cost > @objects[idx].cost
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
57 _swap(idx, parent_idx)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
58 _reorder_insert(parent_idx)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
59 end
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
60 end
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
61
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
62 def _swap(idx1, idx2)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
63 @objects[idx2], @objects[idx1] = @objects[idx1], @objects[idx2]
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
64 end
25
79dc2ba41df2 Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
65
39
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
66 def pop()
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
67 # Swap for easy popping without moving everything
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
68 _swap(1, @objects.size - 1)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
69 priority_obj = @objects.pop
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
70 _reorder_remove(1)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
71 priority_obj
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
72 end
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
73
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
74 def _reorder_remove(idx)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
75 child1_idx = idx * 2
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
76 child2_idx = child1_idx + 1
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
77 last_idx = @objects.size - 1
25
79dc2ba41df2 Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
78
39
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
79 if child1_idx <= last_idx
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
80 child1_val = @objects[child1_idx].cost
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
81 child2_val = child2_idx <= last_idx ? @objects[child2_idx].cost : Float::INFINITY
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
82 child_idx, child_val = child1_val < child2_val ? [child1_idx, child1_val] : [child2_idx, child2_val]
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
83
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
84 if @objects[idx].cost >= child_val
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
85 _swap(idx, child_idx)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
86 _reorder_remove(child_idx)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
87 end
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
88 end
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
89 end
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
90
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
91 def empty?
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
92 @objects.size <= 1
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
93 end
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
94
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
95 def to_s
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
96 @objects.map {|val| "#{val.coords.x},#{val.coords.y}=#{val.cost}" if val }
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
97 end
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
98 end
25
79dc2ba41df2 Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
99
37
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
100 # Our route is constrained to "four consecutive spaces". Zig-zag through the middle
39
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
101 # obeys that rule and it's either the shortest route _or_ we won't explore a longer route
37
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
102 max_score = city_map.each_with_index.map {|row, i| i < row.length - 1 ? [row[i], row[i+1]] : [row[i]]}.flatten.reduce(:+)
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
103
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
104 $colours = (0..max_score).map do |i|
39
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
105 angle = (i.to_f / max_score) * 360
37
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
106 if angle <= 60
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
107 r = 0xff
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
108 g = 0xff * angle / 60
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
109 b = 0
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
110 elsif angle <= 120
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
111 r = 0xff * (120 - angle) / 60
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
112 g = 0xff
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
113 b = 0
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
114 elsif angle <= 180
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
115 r = 0
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
116 g = 0xff
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
117 b = 0xff * (angle - 120) / 60
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
118 elsif angle <= 240
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
119 r = 0
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
120 g = 0xff * (240 - angle) / 60
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
121 b = 0xff
39
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
122 elsif angle <= 300
37
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
123 r = 0xff * (240 - angle) / 60
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
124 g = 0
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
125 b = 0xff
39
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
126 else
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
127 r = 0xff
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
128 g = 0
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
129 b = 0xff * (360 - angle) / 60
37
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
130 end
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
131 Colour.new(r.to_i, g.to_i, b.to_i)
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
132 end
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
133
39
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
134 def update_map(new_node, map)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
135 up = $height - new_node.node.coords.y
38
8e92cb172e6b Output final distance
IBBoard <dev@ibboard.co.uk>
parents: 37
diff changeset
136 # We printed a new line after the map, so we're already in column 0 and go X forward (right)
39
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
137 forward = new_node.node.coords.x
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
138 colour = $colours[new_node.cost]
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
139 cell = map[new_node.node.coords.y][new_node.node.coords.x]
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
140 #puts [cell, new_node, $height, $width, up, forward, colour]
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
141 print "\e[s"
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
142 if forward > 0
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
143 print "\e[#{forward}C"
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
144 end
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
145 if up > 0
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
146 print "\e[#{up}A"
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
147 end
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
148 print "\e[48;2;#{colour.r};#{colour.g};#{colour.b}m#{cell}\e[0m\e[u"
37
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
149 end
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
150
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
151 puts "#{city_map.map {|row| row.join("")}.join("\n")}"
38
8e92cb172e6b Output final distance
IBBoard <dev@ibboard.co.uk>
parents: 37
diff changeset
152 # sleep(5) # For screen recording
37
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
153
39
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
154 unvisited = PQueue.new
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
155 # Fake two starting steps from outside so that we use the "turn" logic to get
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
156 # routes with zero previous steps
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
157 start_node_1 = RouteNode.new(Node.new(start_space, Directions::RIGHT, 0), 0, nil)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
158 start_node_2 = RouteNode.new(Node.new(start_space, Directions::DOWN, 0), 0, nil)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
159 unvisited.push(start_node_1)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
160 unvisited.push(start_node_2)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
161 visited = Set.new
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
162 candidate_node = nil
26
eb6c3a7d2f72 Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents: 25
diff changeset
163
39
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
164 def is_shorter?(cur_shortest, new_node)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
165 not cur_shortest or cur_shortest.cost > new_node.cost
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
166 end
26
eb6c3a7d2f72 Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents: 25
diff changeset
167
39
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
168 def is_valid?(x, y)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
169 0 <= x and x < $width and 0 <= y and y < $height
26
eb6c3a7d2f72 Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents: 25
diff changeset
170 end
37
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
171
39
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
172 while not unvisited.empty?
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
173 candidate_node = unvisited.pop
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
174 candidate_node_node = candidate_node.node
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
175
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
176 if visited.include?(candidate_node_node)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
177 # Longer route to an already visited node
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
178 next
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
179 end
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
180 visited.add(candidate_node_node)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
181
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
182 candidate_coords = candidate_node_node.coords
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
183 update_map(candidate_node, city_map)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
184
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
185
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
186 if candidate_coords == end_space
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
187 break
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
188 end
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
189
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
190 current_direction = candidate_node_node.direction
37
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
191
39
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
192 # We can always turn
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
193 anticlockwise = (current_direction + 1) % 4
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
194 clockwise = (anticlockwise + 2) % 4
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
195
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
196 next_steps = [
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
197 [anticlockwise, 0],
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
198 [clockwise, 0]
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
199 ]
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
200 next_steps.append([current_direction, candidate_node_node.num_prev_steps + 1]) if candidate_node_node.num_prev_steps < 4
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
201
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
202 next_steps.each do |direction, num_prev_steps|
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
203 dir = directions[direction]
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
204 new_x = candidate_coords.x + dir.x
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
205 new_y = candidate_coords.y + dir.y
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
206 if is_valid?(new_x, new_y)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
207 next_num_prev_steps = num_prev_steps + 1
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
208 cur_shortest = routes[new_y][new_x][direction][next_num_prev_steps]
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
209 if is_shorter?(cur_shortest, candidate_node)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
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)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
211 routes[new_y][new_x][direction][next_num_prev_steps] = new_shortest
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
212 unvisited.push(new_shortest)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
213 end
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
214 end
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
215 end
26
eb6c3a7d2f72 Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents: 25
diff changeset
216 end
37
455c825f5080 Add plotting of map in ANSI as we go
IBBoard <dev@ibboard.co.uk>
parents: 26
diff changeset
217
39
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
218 if candidate_node
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
219 route_node = candidate_node
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
220 coords = []
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
221 while route_node
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
222 coords.append(route_node.node.coords)
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
223 route_node = route_node.previous_node
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
224 end
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
225 coords.each do |step|
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
226 cell = city_map[step.y][step.x]
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
227 up = $height - step.y
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
228 forward = step.x
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
229 print "\e[s"
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
230 if forward > 0
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
231 print "\e[#{forward}C"
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
232 end
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
233 if up > 0
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
234 print "\e[#{up}A"
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
235 end
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
236 print "\e[1;30m\e[1;47m#{cell}\e[0m\e[u"
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
237 end
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
238 puts candidate_node.cost
0e17e4bd97a9 Rewrite as four-dimensional route finding
IBBoard <dev@ibboard.co.uk>
parents: 38
diff changeset
239 end