other/adventofcode2023: day17.rb annotate

annotate day17.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	455c825f5080
children	0e17e4bd97a9

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)
37 455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	16 Colour = Struct.new(:r, :g, :b)
25 79dc2ba41df2 Copy a Dijkstra's Algorithm implementation IBBoard <dev@ibboard.co.uk> parents: diff changeset	17
79dc2ba41df2 Copy a Dijkstra's Algorithm implementation IBBoard <dev@ibboard.co.uk> parents: diff changeset	18 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	19
37 455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	20 $height = city_map.length
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	21 $width = city_map[0].length
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	22
26 eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	23 start_space = Coord.new(0,0)
37 455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	24 end_space = Coord.new($width - 1, $height - 1)
26 eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	25
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	26 visited = {}
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	27 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	28
26 eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	29 unvisited = Set.new
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	30 unvisited << start_space
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	31 #(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	32
26 eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	33 $up = Coord.new(0, -1)
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	34 $down = Coord.new(0, 1)
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	35 $left = Coord.new(-1, 0)
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	36 $right = Coord.new(1, 0)
25 79dc2ba41df2 Copy a Dijkstra's Algorithm implementation IBBoard <dev@ibboard.co.uk> parents: diff changeset	37
37 455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	38 # Our route is constrained to "four consecutive spaces". Zig-zag through the middle
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	39 # obeys that rule and would be a worst case score.
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	40 max_score = city_map.each_with_index.map {\|row, i\| i < row.length - 1 ? [row[i], row[i+1]] : [row[i]]}.flatten.reduce(:+)
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	41
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	42 $colours = (0..max_score).map do \|i\|
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	43 # Use 300° because we don't want to be confused and loop back to red
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	44 angle = (i.to_f / max_score) * 300
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	45 if angle <= 60
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	46 r = 0xff
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	47 g = 0xff * angle / 60
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	48 b = 0
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	49 elsif angle <= 120
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	50 r = 0xff * (120 - angle) / 60
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	51 g = 0xff
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	52 b = 0
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	53 elsif angle <= 180
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	54 r = 0
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	55 g = 0xff
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	56 b = 0xff * (angle - 120) / 60
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	57 elsif angle <= 240
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	58 r = 0
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	59 g = 0xff * (240 - angle) / 60
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	60 b = 0xff
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	61 else
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	62 r = 0xff * (240 - angle) / 60
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	63 g = 0
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	64 b = 0xff
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	65 end
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	66 Colour.new(r.to_i, g.to_i, b.to_i)
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	67 end
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	68
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	69
25 79dc2ba41df2 Copy a Dijkstra's Algorithm implementation IBBoard <dev@ibboard.co.uk> parents: diff changeset	70 def get_neighbours(city_map, x, y)
26 eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	71 [$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	72 end
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	73
37 455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	74 def steps_since_turn(route)
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	75 if route.steps.length < 2
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	76 return 1
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	77 end
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	78 # puts "#{route}"
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	79 x_steps = 0
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	80 y_steps = 0
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	81 x_turned = false
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	82 y_turned = false
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	83 step_range = ..([6, route.length].max)
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	84 route.steps.reverse[step_range].each_cons(2) do \|step_n, step_m\|
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	85 x_diff = (step_n.x - step_m.x).abs
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	86 y_diff = (step_n.y - step_m.y).abs
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	87 if x_diff > 0 and ! x_turned
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	88 x_steps += 1
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	89 else
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	90 x_turned = true
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	91 end
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	92 if y_diff > 0 and ! y_turned
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	93 y_steps += 1
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	94 else
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	95 y_turned = true
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	96 end
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	97 end
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	98 (y_steps * 10) + x_steps
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	99 end
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	100
26 eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	101 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	102 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	103 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	104 valid_routes = candidate_routes.filter do \|route\|
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	105 looped = route.steps.count(next_node) > 1
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	106 if route.steps.length < 5
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	107 ! looped
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	108 else
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	109 step_range = route.steps[-5..-2]
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	110 !(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	111 end
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	112 end
37 455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	113 valid_routes = valid_routes + routes[next_node].routes unless routes[next_node].nil?
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	114 valid_routes = valid_routes.group_by {\|route\| steps_since_turn(route)}.values.map {\|routes\| routes.sort {\|a,b\| a.distance <=> b.distance}[0]}
26 eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	115 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	116 end
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	117
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	118 def get_distance(routes, node)
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	119 if routes.key?(node)
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	120 routes[node].min_distance
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	121 else
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	122 Float::INFINITY
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	123 end
25 79dc2ba41df2 Copy a Dijkstra's Algorithm implementation IBBoard <dev@ibboard.co.uk> parents: diff changeset	124 end
79dc2ba41df2 Copy a Dijkstra's Algorithm implementation IBBoard <dev@ibboard.co.uk> parents: diff changeset	125
37 455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	126 def update_map(new_node, map, routes)
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	127 routes_to_cell = routes[new_node]
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	128 up = $height - new_node.y
38 8e92cb172e6b Output final distance IBBoard <dev@ibboard.co.uk> parents: 37 diff changeset	129 # We printed a new line after the map, so we're already in column 0 and go X forward (right)
37 455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	130 forward = new_node.x
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	131 if routes_to_cell
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	132 colour = $colours[routes_to_cell.min_distance]
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	133 cell = map[new_node.y][new_node.x]
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	134 #puts [cell, new_node, $height, $width, up, forward, colour]
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	135 print "\e[s"
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	136 if forward > 0
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	137 print "\e[#{forward}C"
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	138 end
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	139 if up > 0
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	140 print "\e[#{up}A"
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	141 end
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	142 print "\e[48;2;#{colour.r};#{colour.g};#{colour.b}m#{cell}\e[0m\e[u"
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	143 end
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	144 end
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	145
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	146 puts "#{city_map.map {\|row\| row.join("")}.join("\n")}"
38 8e92cb172e6b Output final distance IBBoard <dev@ibboard.co.uk> parents: 37 diff changeset	147 # sleep(5) # For screen recording
37 455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	148
25 79dc2ba41df2 Copy a Dijkstra's Algorithm implementation IBBoard <dev@ibboard.co.uk> parents: diff changeset	149 until unvisited.empty?
37 455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	150 #puts "Start loop: #{unvisited}"
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	151 #puts routes
25 79dc2ba41df2 Copy a Dijkstra's Algorithm implementation IBBoard <dev@ibboard.co.uk> parents: diff changeset	152 min_node = nil
37 455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	153 min_node_direct_distance = Float::INFINITY
25 79dc2ba41df2 Copy a Dijkstra's Algorithm implementation IBBoard <dev@ibboard.co.uk> parents: diff changeset	154 unvisited.each do \|node\|
38 8e92cb172e6b Output final distance IBBoard <dev@ibboard.co.uk> parents: 37 diff changeset	155 x_dist = end_space.x - node.x
8e92cb172e6b Output final distance IBBoard <dev@ibboard.co.uk> parents: 37 diff changeset	156 y_dist = end_space.y - node.y
37 455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	157 direct_distance = x_dist + y_dist
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	158 node_route_distance = get_distance(routes, node) + direct_distance
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	159 min_node_route_distance = get_distance(routes, min_node) + min_node_direct_distance
38 8e92cb172e6b Output final distance IBBoard <dev@ibboard.co.uk> parents: 37 diff changeset	160 #puts "Node? #{min_node} - #{node_route_distance} < #{min_node_route_distance} \|\| #{direct_distance} < #{min_node_direct_distance}"
8e92cb172e6b Output final distance IBBoard <dev@ibboard.co.uk> parents: 37 diff changeset	161 #sleep(1)
37 455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	162 if min_node.nil? \|\| node_route_distance < min_node_route_distance #\|\| (node_route_distance == min_node_route_distance && direct_distance < min_node_direct_distance)
26 eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	163 min_node = node
37 455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	164 min_node_direct_distance = direct_distance
26 eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	165 end
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	166 end
37 455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	167 #puts "Unvisited: #{unvisited.length}"
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	168 #puts "Min node: #{min_node} from #{unvisited.length}"
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	169 update_map(min_node, city_map, routes)
26 eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	170
38 8e92cb172e6b Output final distance IBBoard <dev@ibboard.co.uk> parents: 37 diff changeset	171 break if not routes.has_key?(min_node) or min_node == end_space
26 eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	172
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	173 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	174 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	175 if new_routes.routes.length > 0
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	176 routes[neighbour] = new_routes
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	177 unvisited << neighbour if !visited[neighbour]
25 79dc2ba41df2 Copy a Dijkstra's Algorithm implementation IBBoard <dev@ibboard.co.uk> parents: diff changeset	178 end
79dc2ba41df2 Copy a Dijkstra's Algorithm implementation IBBoard <dev@ibboard.co.uk> parents: diff changeset	179 end
79dc2ba41df2 Copy a Dijkstra's Algorithm implementation IBBoard <dev@ibboard.co.uk> parents: diff changeset	180
26 eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	181 visited[min_node] = true
eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	182 unvisited = unvisited.delete(min_node)
37 455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	183 #puts "Delete #{min_node}"
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	184 #a = $stdin.gets("\n")
26 eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	185 end
37 455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	186
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	187 best_route = routes[end_space].routes.sort {\|a, b\| a.distance <=> b.distance}[0]
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	188
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	189 best_route.steps.each do \|step\|
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	190 cell = city_map[step.y][step.x]
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	191 up = $height - step.y
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	192 forward = step.x
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	193 print "\e[s"
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	194 if forward > 0
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	195 print "\e[#{forward}C"
26 eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	196 end
37 455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	197 if up > 0
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	198 print "\e[#{up}A"
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	199 end
455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	200 print "\e[1;30m\e[1;47m#{cell}\e[0m\e[u"
26 eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	201 end
37 455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	202
38 8e92cb172e6b Output final distance IBBoard <dev@ibboard.co.uk> parents: 37 diff changeset	203 puts best_route.distance
8e92cb172e6b Output final distance IBBoard <dev@ibboard.co.uk> parents: 37 diff changeset	204
37 455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	205 #puts "#{city_map.map {\|row\| row.join("")}.join("\n")}"
25 79dc2ba41df2 Copy a Dijkstra's Algorithm implementation IBBoard <dev@ibboard.co.uk> parents: diff changeset	206
37 455c825f5080 Add plotting of map in ANSI as we go IBBoard <dev@ibboard.co.uk> parents: 26 diff changeset	207
26 eb6c3a7d2f72 Constrained and more optimised route finding IBBoard <dev@ibboard.co.uk> parents: 25 diff changeset	208 #puts "#{routes[end_space]}"

Mercurial > repos > other > adventofcode2023

annotate day17.rb @ 38:8e92cb172e6b