Something went wrong. Try again.
Code for the Advent of Code event
aoc advent-of-code
Something went wrong. Try again.
7.2 kB · 287 lines
Ruby
at rust
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288#!/usr/bin/env ruby# frozen_string_literal: true
require 'colorize'require 'matrix'
DEBUG = ENV.fetch('DEBUG', nil)
PATH = ARGV.first || 'input'
INPUT_MAP = { '#' => :wall, ' ' => :empty, '.' => :open}.freeze
OUTPUT_MAP = { wall: '██'.white, open: ' '.black, empty: ' '.black, dead: '██'.red, current: '██'.green}.freeze
TRANSFORMS = { north: Vector[0, -1], south: Vector[0, 1], west: Vector[-1, 0], east: Vector[1, 0]}.freeze
class Vector def x; self[0]; end def y; self[1]; endend
module Enumerable def tally Hash.new(0).tap { |h| each { |v| h[v] += 1 } } endend
def term_clear print "\e[H"end
def deep_copy(o) Marshal.load(Marshal.dump(o))end
class Maze attr_reader :grid, :teleporters
def initialize(grid) @grid = grid xs = @grid.keys.map(&:x) ys = @grid.keys.map(&:y) @min_x = xs.min @max_x = xs.max @min_y = ys.min @max_y = ys.max process! end
def self.from_file(path) letters = {} grid = Hash.new :empty File.readlines(path).each_with_index do |line, y| line.chars.each_with_index do |char, x| pos = Vector[x, y] case char when ' ' grid[pos] = :empty when '#' grid[pos] = :wall when '.' grid[pos] = :open else letters[pos] = char end end end
letters.each do |(pos, letter)| if grid[pos + TRANSFORMS[:north]] == :open other = letters[pos + TRANSFORMS[:south]] label = letter + other grid[pos] = label elsif grid[pos + TRANSFORMS[:south]] == :open other = letters[pos + TRANSFORMS[:north]] label = other + letter grid[pos] = label elsif grid[pos + TRANSFORMS[:west]] == :open other = letters[pos + TRANSFORMS[:east]] label = letter + other grid[pos] = label elsif grid[pos + TRANSFORMS[:east]] == :open other = letters[pos + TRANSFORMS[:west]] label = other + letter grid[pos] = label end end
Maze.new grid end
def process! @teleporters = {} @outer_teleport_positions = Set.new @inner_teleport_positions = Set.new
@grid.each do |(pos, tile)| if deadend? pos fill_deadends! pos elsif tile == 'AA' others = surroundings pos @start_pos = others.find { |(_, t)| t == :open }.first elsif tile == 'ZZ' others = surroundings pos @finish_pos = others.find { |(_, t)| t == :open }.first elsif tile =~ /\A[A-Z]{2}\z/ @teleporters[tile] ||= [] points = @teleporters[tile] unless points.include? pos others_here = surroundings pos open_pos, = others_here.find { |(_, tile)| tile == :open } points << open_pos
is_outer_x = open_pos.x <= (@min_x + 2) || open_pos.x >= (@max_x - 2) is_outer_y = open_pos.y <= (@min_y + 2) || open_pos.y >= (@max_y - 2) if is_outer_x || is_outer_y @outer_teleport_positions.add open_pos else @inner_teleport_positions.add open_pos end end end end
@grid.keys.each do |pos| @grid[pos] = :wall if @grid[pos] == :dead end end
def draw(current_pos = nil) buffer = '' (@min_y..@max_y).each do |y| (@min_x..@max_x).each do |x| pos = Vector[x, y] tile = @grid[pos] sprite = OUTPUT_MAP[tile] || tile if pos == current_pos # rubocop:disable Style/ConditionalAssignment buffer += OUTPUT_MAP[:current] elsif tile == 'AA' buffer += sprite.black.on_blue elsif tile == 'ZZ' buffer += sprite.black.on_green else buffer += sprite end end buffer += "\n" end term_clear puts buffer end
def shortest_path(pos = nil, previous_pos = nil, steps = 0, ports = Set.new) pos ||= @start_pos return steps if pos == @finish_pos
others = surroundings(pos).reject { |_, t| t == :wall }.reject do |p, t| p == previous_pos || ports.include?(t) || t == 'AA' || t == 'ZZ' end
return nil if others.empty?
costs = others.map do |target_pos, target_tile| if target_tile == :open shortest_path(target_pos, pos, steps + 1, ports.dup) else # It's a teleporter tp_pos = @teleporters[target_tile].reject { |p| p == pos }[0] ports.add target_tile shortest_path(tp_pos, pos, steps + 1, ports.dup) end end
costs.compact.min end
def shortest_recursive_path_bfs(start_pos = nil, finished = nil) start_pos ||= @start_pos finished ||= Set.new q = Queue.new q.enq [start_pos, 0, 0, Set.new, nil]
until q.empty? pos, depth, steps, visited, previous_pos = q.deq draw pos if DEBUG puts "Solutions: #{finished}" if DEBUG _tile = @grid[pos]
if finished.empty? || steps < finished.min if pos == @finish_pos && depth == 0 finished.add steps elsif depth < 30 others = surroundings(pos).reject { |_, t| t == :wall }.reject do |p, t| p == previous_pos || visited.include?([pos, p]) || visited.include?(t) || t == 'AA' || t == 'ZZ' end others.each do |target_pos, target_tile| dir = [pos, target_pos] visited.add dir target_visited = visited.dup if target_tile == :open q.enq [target_pos, depth, steps + 1, target_visited, pos] else # Teleporter is_inner_tp = inner_teleport?(pos) is_outer_tp = outer_teleport?(pos) unless depth == 0 && is_outer_tp tp_pos = @teleporters[target_tile].reject { |p| p == pos }[0] tp_depth = depth + (is_inner_tp ? 1 : -1) q.enq [tp_pos, tp_depth, steps + 1, Set.new([target_tile]), nil] end end end end end end
finished.min end
private
def fill_deadends!(pos) return unless @grid[pos] == :open @grid[pos] = :dead others = surroundings pos
others.each_key do |other_pos| fill_deadends! other_pos if deadend?(other_pos) && @grid[other_pos] != :dead end end
def deadend?(pos) tile = @grid[pos] return false if tile == :wall return true if tile == :dead return false unless tile == :open others = surroundings pos counts = others.values.tally (counts[:wall] + counts[:dead]) >= 3 end
def surroundings(pos) other_pos = [ pos + TRANSFORMS[:north], pos + TRANSFORMS[:south], pos + TRANSFORMS[:west], pos + TRANSFORMS[:east] ]
other_pos.to_h { |p| [p, @grid[p]] } end
def teleport?(pos) inner_teleport?(pos) || outer_teleport?(pos) end
def inner_teleport?(pos) @inner_teleport_positions.include? pos end
def outer_teleport?(pos) @outer_teleport_positions.include? pos endend
maze = Maze.from_file PATH
maze.draw if DEBUG
part1 = maze.shortest_pathputs "Part 1: #{part1 || 'N/A'}"
part2 = maze.shortest_recursive_path_bfsputs "Part 2: #{part2 || 'N/A'}"