Mercurial > repos > other > adventofcode2023

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