Mercurial > repos > other > adventofcode2023

annotate day23.rb @ 32:a1b748f2c416

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Implement day 23 "longest route finding" Allows for "downhill only" and "can climb" approaches. But climbing still brute-forces the map and takes too long on the final input.
author IBBoard <dev@ibboard.co.uk>
date Thu, 04 Jan 2024 11:18:56 +0000
parents
children 676461cc3a70
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
3 if ARGV.length != 1 and ARGV.length != 2
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
4 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
5 elsif not File.exist? (ARGV[0])
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
6 abort("File #{ARGV[0]} did not exist")
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
7 end
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
8
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
9 file = ARGV[0]
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 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
12 start_pos = [lines[0].index("."), 0]
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
13 end_pos = [lines[-1].index("."), lines.length - 1]
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
14 maze = lines.map {|line| line.each_char.to_a}
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
15
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
16 $maze_width = 0...maze[0].length
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
17 $maze_height = 0...maze.length
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
18 $can_climb_hills = ARGV.length == 2
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
19
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
20 open_routes = [[start_pos]]
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
21
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
22 distances = Array.new(maze.length) {Array.new(maze[0].length) {Hash.new}}
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
23
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
24 $moves = [[0,1], [0,-1], [1,0], [-1,0]]
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
25
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
26 def valid_move(move, space, maze)
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
27 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
28 case maze[space[1]][space[0]]
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
29 when "#" then false
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
30 when "." then true
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
31 when "^" then $can_climb_hills || move == [0,-1]
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
32 when "v" then $can_climb_hills || move == [0, 1]
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
33 when ">" then $can_climb_hills || move == [1, 0]
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 end
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
36 else
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
37 false
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
38 end
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
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
41 def next_steps(route, maze)
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
42 last_space = route[-1]
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
43 $moves.map do |move|
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
44 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
45 [move, new_space]
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
46 end.filter do |move, new_space|
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
47 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
48 end
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
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
51 while open_routes != []
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
52 num_routes = open_routes.length
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
53 open_routes = open_routes.flat_map do |route|
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
54 next_steps(route, maze).map do |move, next_step|
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
55 new_route = route + [next_step]
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
56 # Simple "distance to this point" doesn't work when if can approach from different
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
57 # directions, because the other route may be shorter to here but longer to the end
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
58 # so we use the movement direction to track different directionality
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
59 current_distances = distances[next_step[1]][next_step[0]]
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
60 if !current_distances.key?(move) || new_route.length > current_distances[move]
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
61 distances[next_step[1]][next_step[0]][move] = new_route.length
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
62 new_route
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
63 else
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
64 # We have a longer route to this space in this direction, so prune
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
65 nil
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
66 end
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
67 end.filter {|route| !route.nil?}
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
68 end
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
69 # if open_routes.length != num_routes
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
70 # puts "Now have:"
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
71 # open_routes.each {|route| puts " * #{route.length} to #{route[-1]}"}
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
72 # end
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
73 end
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
74
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
75 # Subtract 1 because we don't count the first step
a1b748f2c416 Implement day 23 "longest route finding"
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
76 puts "#{distances[end_pos[1]][end_pos[0]].values.max - 1}"