Mercurial > repos > other > adventofcode2023
annotate day17.rb @ 31:47dc75915e91
Implement falling/destroying blocks
Implemented part 1 with supports/supported by logic.
Implemented part 2 with cascades and summing counts. Code has
caching so it is quick _but_ it gives an answer that's too low.
author | IBBoard <dev@ibboard.co.uk> |
---|---|
date | Wed, 03 Jan 2024 17:00:56 +0000 |
parents | eb6c3a7d2f72 |
children | 455c825f5080 |
rev | line source |
---|---|
25
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
1 #! /usr/bin/env ruby |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
2 |
26
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
3 require 'set' |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
4 |
25
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
5 if ARGV.length != 1 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
6 abort("Incorrect arguments - needs input file") |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
7 elsif not File.exist? (ARGV[0]) |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
8 abort("File #{ARGV[0]} did not exist") |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
9 end |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
10 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
11 file = ARGV[0] |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
12 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
13 Coord = Struct.new(:x, :y) |
26
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
14 Route = Struct.new(:steps, :distance) |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
15 Routes = Struct.new(:routes, :min_distance) |
25
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
16 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
17 city_map = File.open(file, "r").each_line(chomp: true).map{ |line| line.each_char.map(&:to_i)} |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
18 |
26
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
19 start_space = Coord.new(0,0) |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
20 end_space = Coord.new(city_map[0].length - 1, city_map.length - 1) |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
21 |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
22 visited = {} |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
23 routes = { start_space => Routes.new([Route.new([start_space], 0)], 0)} |
25
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
24 |
26
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
25 unvisited = Set.new |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
26 unvisited << start_space |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
27 #(0...city_map.length).each {|y| (0...city_map[0].length).each {|x| unvisited << Coord.new(x,y)}} |
25
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
28 |
26
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
29 $up = Coord.new(0, -1) |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
30 $down = Coord.new(0, 1) |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
31 $left = Coord.new(-1, 0) |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
32 $right = Coord.new(1, 0) |
25
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
33 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
34 def get_neighbours(city_map, x, y) |
26
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
35 [$up, $down, $left, $right].map {|coord| Coord.new(coord.x + x, coord.y + y)}.filter {|coord| coord.x >= 0 and coord.y >= 0 and coord.x < city_map[0].length and coord.y < city_map.length} |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
36 end |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
37 |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
38 def allowed_routes(city_map, routes, cur_node, next_node) |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
39 next_step_distance = city_map[next_node.y][next_node.x] |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
40 candidate_routes = routes[cur_node].routes.map {|route| Route.new(route.steps + [next_node], route.distance + next_step_distance)} |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
41 valid_routes = candidate_routes.filter do |route| |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
42 looped = route.steps.count(next_node) > 1 |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
43 if route.steps.length < 5 |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
44 ! looped |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
45 else |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
46 step_range = route.steps[-5..-2] |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
47 !(step_range.all?{|step| step.x == next_node.x} or step_range.all?{|step| step.y == next_node.y}) and !looped |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
48 end |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
49 end |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
50 valid_routes = valid_routes + routes[next_node].routes if !routes[next_node].nil? |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
51 Routes.new(valid_routes, valid_routes.map(&:distance).min) |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
52 end |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
53 |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
54 def get_distance(routes, node) |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
55 if routes.key?(node) |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
56 routes[node].min_distance |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
57 else |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
58 Float::INFINITY |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
59 end |
25
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
60 end |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
61 |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
62 until unvisited.empty? |
26
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
63 # puts unvisited |
25
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
64 min_node = nil |
26
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
65 # min_node_direct_distance = Float::INFINITY |
25
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
66 unvisited.each do |node| |
26
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
67 # x_dist = (end_space.x - node.x).abs |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
68 # y_dist = (end_space.y - node.y).abs |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
69 # direct_distance = x_dist * x_dist + y_dist * y_dist |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
70 if min_node.nil? || get_distance(routes, node) < get_distance(routes, min_node)# || direct_distance < min_node_direct_distance |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
71 # puts "#{get_distance(routes, node)} < #{get_distance(routes, min_node)} || #{direct_distance} < #{min_node_direct_distance}" |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
72 min_node = node |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
73 # min_node_direct_distance = direct_distance |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
74 end |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
75 end |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
76 # puts unvisited.length |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
77 puts "Min node: #{min_node}" |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
78 |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
79 break if get_distance(routes, min_node) == Float::INFINITY or min_node == end_space |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
80 |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
81 get_neighbours(city_map, min_node.x, min_node.y).each do |neighbour| |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
82 new_routes = allowed_routes(city_map, routes, min_node, neighbour) |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
83 if new_routes.routes.length > 0 |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
84 routes[neighbour] = new_routes |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
85 unvisited << neighbour if !visited[neighbour] |
25
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
86 end |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
87 end |
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
88 |
26
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
89 visited[min_node] = true |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
90 unvisited = unvisited.delete(min_node) |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
91 # puts "Delete #{min_node}" |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
92 # a = $stdin.gets("\n") |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
93 end |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
94 =begin |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
95 city_map.length.times do |y| |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
96 city_map[0].length.times do |x| |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
97 print routes[Coord.new(x,y)].routes.map(&:distance).min.to_s.rjust(3) + " " + city_map[y][x].to_s + " |" |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
98 end |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
99 puts |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
100 end |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
101 city_map.length.times do |y| |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
102 city_map[0].length.times do |x| |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
103 puts "#{x},#{y} ⇒ #{routes[Coord.new(x,y)].routes.length} - #{routes[Coord.new(x,y)].routes.map(&:distance).minmax}" |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
104 end |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
105 end |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
106 =end |
25
79dc2ba41df2
Copy a Dijkstra's Algorithm implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
107 |
26
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
108 puts routes[end_space].routes.sort {|a, b| a.distance <=> b.distance}[0] |
eb6c3a7d2f72
Constrained and more optimised route finding
IBBoard <dev@ibboard.co.uk>
parents:
25
diff
changeset
|
109 #puts "#{routes[end_space]}" |