Mercurial > repos > other > adventofcode2023

annotate day18.rb @ 27:6b58ddfaed38

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add Day 18 part 1 solution using line crossing
author IBBoard <dev@ibboard.co.uk>
date Tue, 02 Jan 2024 16:04:33 +0000
parents
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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