Mercurial > repos > other > adventofcode2023
comparison day18.rb @ 27:6b58ddfaed38
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 |