Mercurial > repos > other > adventofcode2023
annotate day18.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 | 6b58ddfaed38 |
children |
rev | line source |
---|---|
27
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
1 #! /usr/bin/env ruby |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
2 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
3 if ARGV.length < 1 or ARGV.length > 2 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
4 abort("Incorrect arguments - needs input file and optional 'b' for part 2") |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
5 elsif not File.exist? (ARGV[0]) |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
6 abort("File #{ARGV[0]} did not exist") |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
7 end |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
8 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
9 file = ARGV[0] |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
10 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
11 instructions = File.open(file, "r").each_line(chomp: true).map(&:split) |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
12 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
13 Coord = Struct.new(:x,:y, :values) |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
14 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
15 trench = [Coord.new(0,0, [])] |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
16 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
17 if ARGV.length == 1 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
18 def decode(instruction) |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
19 [instruction[0], instruction[1]] |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
20 end |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
21 else |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
22 def decode(instruction) |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
23 # Offset of 2 because of brackets and hash |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
24 dir_char = case instruction[2][7] |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
25 when "0" then "R" |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
26 when "1" then "D" |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
27 when "2" then "L" |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
28 when "3" then "U" |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
29 end |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
30 num_steps = instruction[2][2,5].to_i(16) |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
31 [dir_char, num_steps] |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
32 end |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
33 end |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
34 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
35 instructions.reduce(trench[0]) do |pos, instruction| |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
36 dir_char, num_steps = decode(instruction) |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
37 # Map to cardinal directions so that we can use the day 10 border crossing algorithm |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
38 # for finding "inside" nodes |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
39 case dir_char |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
40 when "R" |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
41 x_change = 1 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
42 y_change = 0 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
43 prev_dir = :east |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
44 next_dir = :west |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
45 when "L" |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
46 x_change = -1 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
47 y_change = 0 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
48 prev_dir = :west |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
49 next_dir = :east |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
50 when "U" |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
51 x_change = 0 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
52 y_change = -1 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
53 prev_dir = :north |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
54 next_dir = :south |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
55 when "D" |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
56 x_change = 0 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
57 y_change = 1 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
58 prev_dir = :south |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
59 next_dir = :north |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
60 end |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
61 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
62 num_steps.to_i.times do |i| |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
63 pos.values << prev_dir |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
64 pos = Coord.new(pos.x + x_change, pos.y + y_change, [next_dir]) |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
65 trench << pos |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
66 end |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
67 pos |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
68 end |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
69 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
70 x_min, x_max = trench.map(&:x).minmax |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
71 y_min, y_max = trench.map(&:y).minmax |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
72 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
73 puts x_min, y_min |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
74 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
75 if ARGV.length > 1 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
76 puts "We can't brute force this. Answers online suggest shoelace formula and Pick's theorem" |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
77 puts "So we'll call it quits and skip this" |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
78 return |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
79 end |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
80 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
81 dig_map = Hash.new |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
82 trench.each do |pos| |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
83 new_x = pos.x - x_min |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
84 new_y = pos.y - y_min |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
85 coords = [new_x, new_y] |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
86 if dig_map.key? (coords) |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
87 dig_map[coords] += pos.values |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
88 else |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
89 dig_map[coords] = pos.values |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
90 end |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
91 dig_map[coords].sort! |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
92 end |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
93 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
94 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
95 State = Struct.new(:crossed_lines, :inside_count, :last_switch) |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
96 in_out_transition = [:north, :south] |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
97 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
98 state = State.new(0,0,nil) |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
99 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
100 cells_inside = (y_max - y_min + 1).times do |y| |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
101 state.last_switch = nil |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
102 (x_max - x_min + 1).times do |x| |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
103 cell = dig_map[[x,y]] |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
104 if cell |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
105 #puts "#{x},#{y} - #{cell}" |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
106 # Same algorithm as Day 10 EXCEPT we count the trench/border as well |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
107 state.inside_count += 1 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
108 if cell == in_out_transition |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
109 state.crossed_lines += 1 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
110 elsif cell != [:east, :west] |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
111 this_switch = (cell & in_out_transition) |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
112 if state.last_switch.nil? |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
113 state.last_switch = this_switch |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
114 else |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
115 if this_switch != state.last_switch |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
116 state.crossed_lines += 1 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
117 end |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
118 state.last_switch = nil |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
119 end |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
120 end |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
121 elsif state.crossed_lines % 2.0 != 0 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
122 #puts "#{x},#{y} - inside" |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
123 state.inside_count += 1 |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
124 else |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
125 #puts "#{x},#{y} - crossed #{state.crossed_lines} lines" |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
126 end |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
127 state |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
128 end |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
129 state |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
130 end |
6b58ddfaed38
Add Day 18 part 1 solution using line crossing
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
131 puts state.inside_count |