Mercurial > repos > other > adventofcode2023
annotate day17.rb @ 39:0e17e4bd97a9 default tip
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 |
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 | 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 | 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 |