Mercurial > repos > other > adventofcode2023
view day23.rb @ 36:7197f31970ff
Day 25 part 1 instructions and partial solution
author | IBBoard <dev@ibboard.co.uk> |
---|---|
date | Thu, 18 Apr 2024 19:56:23 +0100 |
parents | 676461cc3a70 |
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}"