other/adventofcode2023: day23.rb annotate

annotate day23.rb @ 37:455c825f5080

Add plotting of map in ANSI as we go

author	IBBoard <dev@ibboard.co.uk>
date	Fri, 20 Sep 2024 20:06:21 +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}"

Mercurial > repos > other > adventofcode2023

annotate day23.rb @ 37:455c825f5080