Mercurial > repos > other > adventofcode2023
view day23.rb @ 33:676461cc3a70
Day 23 - track segments, not each space
This allows us to explore the branches once then do quicker calculations
for valid route lengths. But still requires exploring 1,262,816 routes
to find the longest!
author | IBBoard <dev@ibboard.co.uk> |
---|---|
date | Thu, 04 Jan 2024 14:52:24 +0000 |
parents | a1b748f2c416 |
children |
line wrap: on
line source
#! /usr/bin/env ruby require 'set' if ARGV.length != 1 and ARGV.length != 2 abort("Incorrect arguments - needs input file and optional second arg") elsif not File.exist? (ARGV[0]) abort("File #{ARGV[0]} did not exist") end file = ARGV[0] lines = File.open(file, "r").each_line(chomp: true).to_a start_pos = [lines[0].index("."), 0] end_pos = [lines[-1].index("."), lines.length - 1] maze = lines.map {|line| line.each_char.to_a} $maze_width = 0...maze[0].length $maze_height = 0...maze.length $can_climb_hills = ARGV.length == 2 open_segments = [[start_pos]] segments = Hash.new $moves = [[0,1], [0,-1], [1,0], [-1,0]] def valid_move(move, space, maze) if $maze_width.cover?(space[0]) && $maze_height.cover?(space[1]) case maze[space[1]][space[0]] when "#" then false when "." then true when "^" then $can_climb_hills || move == [0,-1] when "v" then $can_climb_hills || move == [0, 1] when ">" then $can_climb_hills || move == [1, 0] when "<" then $can_climb_hills || move == [-1,0] end else false end end def next_steps(route, maze) last_space = route[-1] $moves.map do |move| new_space = [move[0] + last_space[0], move[1] + last_space[1]] [move, new_space] end.filter do |move, new_space| valid_move(move, new_space, maze) && !route.include?(new_space) end end def add_segment(segments, start_step, end_step, route_length) current_segments = segments.key?(start_step) ? segments[start_step] : [] current_segments << [end_step, route_length] segments[start_step] = current_segments end while open_segments != [] open_segments = open_segments.flat_map do |route| candidate_steps = next_steps(route, maze) if candidate_steps.length > 1 been_here_before = segments.key?(route[-1]) # We got to a fork - record the segment if $can_climb_hills add_segment(segments, route[-1], route[0], route.length) end add_segment(segments, route[0], route[-1], route.length) if ! been_here_before # Start some new segments candidate_steps.map do |move, step| [route[-1], step] end else # Else we've already explored to this fork from another direction, so we can stop [] end else # We're following a corridor candidate_steps.filter do |move, step| if step == end_pos # We got to the end - record the segment add_segment(segments, route[0], step, route.length + 1) false else true end end.map do |move, step| route + [step] end end end end open_routes = [[[start_pos], 0]] routes = [] while open_routes.length > 0 open_routes = open_routes.flat_map do |route| segments[route[0][-1]].filter do |segment| if segment[0] == end_pos #puts "Add route #{routes.length}: #{route[0] + [segment[0]]} = #{route[1] + segment[1]}" routes << route[1] + segment[1] false else !route[0].include?(segment[0]) && !route[0].include?([segment[0]]) end end.map do |segment| # Subtract the overlapping node [route[0] + [segment[0]], route[1] + segment[1] - 1] end end open_routes = Set.new(open_routes) end longest_route = routes.max # Subtract the start node puts "#{routes.length} routes - max length #{longest_route - 1}"