Mercurial > repos > other > adventofcode2023

annotate day16.rb @ 33:676461cc3a70

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Day 23 - track segments, not each space This allows us to explore the branches once then do quicker calculations for valid route lengths. But still requires exploring 1,262,816 routes to find the longest!
author IBBoard <dev@ibboard.co.uk>
date Thu, 04 Jan 2024 14:52:24 +0000
parents ad73a2ff3d06
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
22
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
1 #! /usr/bin/env ruby
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
2
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
3 require "set"
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
4
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
5 if ARGV.length != 1
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
6 abort("Incorrect arguments - needs input file")
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
7 elsif not File.exist? (ARGV[0])
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
8 abort("File #{ARGV[0]} did not exist")
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
9 end
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
10
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
11 file = ARGV[0]
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
12
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
13 Laser = Struct.new(:x, :y, :direction)
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
14
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
15 mirror_map = {
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
16 "." => {
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
17 right: [:right],
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
18 up: [:up],
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
19 left: [:left],
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
20 down: [:down]
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
21 },
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
22 "/" => {
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
23 right: [:up],
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
24 up: [:right],
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
25 down: [:left],
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
26 left: [:down]
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
27 },
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
28 "\\" => {
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
29 right: [:down],
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
30 down: [:right],
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
31 up: [:left],
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
32 left: [:up]
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
33 },
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
34 "-" => {
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
35 right: [:right],
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
36 left: [:left],
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
37 down: [:left, :right],
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
38 up: [:left, :right]
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
39 },
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
40 "|" => {
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
41 right: [:up, :down],
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
42 left: [:up, :down],
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
43 down: [:down],
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
44 up: [:up]
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
45 }
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
46 }
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
47
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
48 def next_positions(puzzle, mirror_map, laser)
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
49 x_prime, y_prime = case laser.direction
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
50 when :right then [laser.x + 1, laser.y]
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
51 when :down then [laser.x, laser.y + 1]
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
52 when :left then [laser.x - 1, laser.y]
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
53 when :up then [laser.x, laser.y - 1]
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
54 end
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
55 if x_prime < 0 or x_prime >= puzzle[0].length or y_prime < 0 or y_prime >= puzzle.length
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
56 []
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
57 else
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
58 new_space = puzzle[y_prime][x_prime]
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
59 # puts "#{laser.direction} to #{x_prime}, #{y_prime} (#{new_space})"
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
60 mirror_map[new_space][laser.direction].map {|dir| Laser.new(x_prime, y_prime, dir)}
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
61 end
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
62 end
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
63
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
64 puzzle = File.open(file, "r").each_line(chomp: true).map {|line| line.each_char.to_a}
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
65 lasers = next_positions(puzzle, mirror_map, Laser.new(-1, 0, :right))
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
66 energised = Array.new(puzzle.length) {Array.new(puzzle[0].length)}
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
67 energised [0][0] = 1
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
68 previous_lasers = Set.new
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
69
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
70 while lasers != []
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
71 # puts "#{lasers}"
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
72 lasers = lasers.flat_map do |laser|
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
73 next_positions(puzzle, mirror_map, laser).filter {|new_laser| !previous_lasers.include? new_laser}.each {|new_laser| energised[new_laser.y][new_laser.x] = 1; previous_lasers << new_laser}
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
74 end
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
75 end
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
76
ad73a2ff3d06 Implement Day 15 part 1 and all of Day 16
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
77 puts energised.flatten.map(&:to_i).reduce(:+)