Mercurial > repos > other > adventofcode2023
annotate day23.rb @ 38:8e92cb172e6b
Output final distance
Also minor code cleanup
author | IBBoard <dev@ibboard.co.uk> |
---|---|
date | Fri, 20 Sep 2024 20:30:11 +0100 |
parents | 676461cc3a70 |
children |
rev | line source |
---|---|
32
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
1 #! /usr/bin/env ruby |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
2 |
33
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
3 require 'set' |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
4 |
32
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
5 if ARGV.length != 1 and ARGV.length != 2 |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
6 abort("Incorrect arguments - needs input file and optional second arg") |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
7 elsif not File.exist? (ARGV[0]) |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
8 abort("File #{ARGV[0]} did not exist") |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
9 end |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
10 |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
11 file = ARGV[0] |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
12 |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
13 lines = File.open(file, "r").each_line(chomp: true).to_a |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
14 start_pos = [lines[0].index("."), 0] |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
15 end_pos = [lines[-1].index("."), lines.length - 1] |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
16 maze = lines.map {|line| line.each_char.to_a} |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
17 |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
18 $maze_width = 0...maze[0].length |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
19 $maze_height = 0...maze.length |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
20 $can_climb_hills = ARGV.length == 2 |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
21 |
33
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
22 open_segments = [[start_pos]] |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
23 segments = Hash.new |
32
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
24 |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
25 $moves = [[0,1], [0,-1], [1,0], [-1,0]] |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
26 |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
27 def valid_move(move, space, maze) |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
28 if $maze_width.cover?(space[0]) && $maze_height.cover?(space[1]) |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
29 case maze[space[1]][space[0]] |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
30 when "#" then false |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
31 when "." then true |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
32 when "^" then $can_climb_hills || move == [0,-1] |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
33 when "v" then $can_climb_hills || move == [0, 1] |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
34 when ">" then $can_climb_hills || move == [1, 0] |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
35 when "<" then $can_climb_hills || move == [-1,0] |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
36 end |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
37 else |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
38 false |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
39 end |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
40 end |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
41 |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
42 def next_steps(route, maze) |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
43 last_space = route[-1] |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
44 $moves.map do |move| |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
45 new_space = [move[0] + last_space[0], move[1] + last_space[1]] |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
46 [move, new_space] |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
47 end.filter do |move, new_space| |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
48 valid_move(move, new_space, maze) && !route.include?(new_space) |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
49 end |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
50 end |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
51 |
33
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
52 def add_segment(segments, start_step, end_step, route_length) |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
53 current_segments = segments.key?(start_step) ? segments[start_step] : [] |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
54 current_segments << [end_step, route_length] |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
55 segments[start_step] = current_segments |
32
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
56 end |
a1b748f2c416
Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
57 |
33
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
58 while open_segments != [] |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
59 open_segments = open_segments.flat_map do |route| |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
60 candidate_steps = next_steps(route, maze) |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
61 if candidate_steps.length > 1 |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
62 been_here_before = segments.key?(route[-1]) |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
63 # We got to a fork - record the segment |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
64 if $can_climb_hills |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
65 add_segment(segments, route[-1], route[0], route.length) |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
66 end |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
67 add_segment(segments, route[0], route[-1], route.length) |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
68 if ! been_here_before |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
69 # Start some new segments |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
70 candidate_steps.map do |move, step| |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
71 [route[-1], step] |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
72 end |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
73 else |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
74 # Else we've already explored to this fork from another direction, so we can stop |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
75 [] |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
76 end |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
77 else |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
78 # We're following a corridor |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
79 candidate_steps.filter do |move, step| |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
80 if step == end_pos |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
81 # We got to the end - record the segment |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
82 add_segment(segments, route[0], step, route.length + 1) |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
83 false |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
84 else |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
85 true |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
86 end |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
87 end.map do |move, step| |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
88 route + [step] |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
89 end |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
90 end |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
91 end |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
92 end |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
93 |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
94 open_routes = [[[start_pos], 0]] |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
95 routes = [] |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
96 |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
97 while open_routes.length > 0 |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
98 open_routes = open_routes.flat_map do |route| |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
99 segments[route[0][-1]].filter do |segment| |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
100 if segment[0] == end_pos |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
101 #puts "Add route #{routes.length}: #{route[0] + [segment[0]]} = #{route[1] + segment[1]}" |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
102 routes << route[1] + segment[1] |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
103 false |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
104 else |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
105 !route[0].include?(segment[0]) && !route[0].include?([segment[0]]) |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
106 end |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
107 end.map do |segment| |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
108 # Subtract the overlapping node |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
109 [route[0] + [segment[0]], route[1] + segment[1] - 1] |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
110 end |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
111 end |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
112 open_routes = Set.new(open_routes) |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
113 end |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
114 |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
115 longest_route = routes.max |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
116 # Subtract the start node |
676461cc3a70
Day 23 - track segments, not each space
IBBoard <dev@ibboard.co.uk>
parents:
32
diff
changeset
|
117 puts "#{routes.length} routes - max length #{longest_route - 1}" |