Mercurial > repos > other > adventofcode2023

annotate day17.rb @ 36:7197f31970ff

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Day 25 part 1 instructions and partial solution
author IBBoard <dev@ibboard.co.uk>
date Thu, 18 Apr 2024 19:56:23 +0100
parents eb6c3a7d2f72
children 455c825f5080
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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]}"