Something went wrong. Try again.
Code for the Advent of Code event
aoc advent-of-code
Something went wrong. Try again.
5.7 kB · 231 lines
Ruby
at rust
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232#!/usr/bin/env ruby# frozen_string_literal: true
HALLWAY_LEGAL_INDICES = [0, 1, 3, 5, 7, 9, 10].to_set.freeze
AMPHIPOD_MOVE_COSTS = { A: 1, B: 10, C: 100, D: 1000}.freeze
AMPHIPOD_ROOM = { A: 0, B: 1, C: 2, D: 3}.freeze
ROOM_AMPHIPOD = { 0 => :A, 1 => :B, 2 => :C, 3 => :D}.freeze
ROOM_HALLWAY_INDEX = { 0 => 2, 1 => 4, 2 => 6, 3 => 8}.freeze
class Room attr_reader :full_size, :room_index
def initialize(full_size, room_index, amphipods = nil) @full_size = full_size @room_index = room_index @amphipods = amphipods || [] end
def [](i) @amphipods[i] end
def desired_amphipod ROOM_AMPHIPOD[@room_index] end
def hallway_index ROOM_HALLWAY_INDEX[@room_index] end
def solved? @amphipods.size == @full_size && @amphipods.all?(desired_amphipod) end
def shift! @amphipods.shift end
def unshift!(amphipod) @amphipods.unshift amphipod end
def can_enter?(amphipod) amphipod == desired_amphipod && @amphipods.size < @full_size && @amphipods.all?(desired_amphipod) end
def can_exit? @amphipods[0] != desired_amphipod || !@amphipods.all?(desired_amphipod) end
def exit_cost(to = nil) room_distance = @full_size - @amphipods.size + 1 hallway_distance = to.nil? ? 0 : (to - ROOM_HALLWAY_INDEX[@room_index]).abs distance = room_distance + hallway_distance distance * AMPHIPOD_MOVE_COSTS[@amphipods[0]] end
def enter_cost(amphipod, from = nil) hallway_distance = from.nil? ? 0 : (from - ROOM_HALLWAY_INDEX[@room_index]).abs room_distance = @full_size - @amphipods.size distance = hallway_distance + room_distance distance * AMPHIPOD_MOVE_COSTS[amphipod] end
def empty? @amphipods.empty? end
def hash [@full_size, @room_index, @amphipods].hash end
def dup self.class.new(@full_size, @room_index, @amphipods.dup) endend
class State attr_accessor :hallway, :rooms, :cost
def initialize(hallway, rooms, cost) @hallway = hallway @rooms = rooms @cost = cost end
def solved? @rooms.all?(&:solved?) end
def can_reach_room?(hallway_index, room_index) enter_index = ROOM_HALLWAY_INDEX[room_index] return true if (hallway_index - enter_index).abs == 1 if hallway_index < enter_index HALLWAY_LEGAL_INDICES.select { _1 > hallway_index && _1 < enter_index }.each do |i| return false unless @hallway[i].nil? end else HALLWAY_LEGAL_INDICES.select { _1 < hallway_index && _1 > enter_index }.each do |i| return false unless @hallway[i].nil? end end true end
def can_reach_hallway?(room_index, hallway_index) return false unless HALLWAY_LEGAL_INDICES.include? hallway_index exit_index = ROOM_HALLWAY_INDEX[room_index] return @hallway[hallway_index].nil? if (hallway_index - exit_index).abs == 1 if hallway_index < exit_index HALLWAY_LEGAL_INDICES.select { _1 >= hallway_index && _1 < exit_index }.each do |i| return false unless @hallway[i].nil? end else HALLWAY_LEGAL_INDICES.select { _1 <= hallway_index && _1 > exit_index }.each do |i| return false unless @hallway[i].nil? end end true end
def can_amphipod_reach_room?(amphipod, hallway_index) room_index = AMPHIPOD_ROOM[amphipod] can_reach_room? hallway_index, room_index end
def valid_exit_indices(room_index) HALLWAY_LEGAL_INDICES.select { can_reach_hallway? room_index, _1 } end
def gen_states(cache) new_states = []
@hallway.each do |hallway_index, amphipod| next if amphipod.nil? target_room_index = AMPHIPOD_ROOM[amphipod] target_room = @rooms[target_room_index] next unless can_amphipod_reach_room? amphipod, hallway_index next unless target_room.can_enter? amphipod cost = target_room.enter_cost amphipod, hallway_index new_state = dup new_state.cost += cost new_state.hallway.delete hallway_index new_state.rooms[target_room_index].unshift! amphipod cached_cost = cache[new_state.cache_key] next unless cached_cost.nil? || cached_cost > new_state.cost cache[new_state.cache_key] = new_state.cost new_states << new_state end
@rooms.each_with_index do |room, room_index| next if room.empty? next unless room.can_exit? amphipod = room[0] target_hallway_indices = valid_exit_indices room_index next if target_hallway_indices.empty? target_hallway_indices.each do |target_hallway_index| cost = room.exit_cost target_hallway_index new_state = dup new_state.cost += cost new_state.hallway[target_hallway_index] = amphipod new_state.rooms[room_index].shift! cached_cost = cache[new_state.cache_key] next unless cached_cost.nil? || cached_cost > new_state.cost cache[new_state.cache_key] = new_state.cost new_states << new_state end end
new_states end
def dup self.class.new(@hallway.dup, @rooms.map(&:dup), @cost) end
def cache_key [@hallway, @rooms].hash endend
def solve(input) state = State.new({}, input.transpose.map.with_index { Room.new _1.size, _2, _1 }, 0) successful = [] queue = [state] cache = { state.cache_key => state.cost }
while queue.any? current_state = queue.shift if current_state.solved? successful << current_state else new_states = current_state.gen_states cache queue.unshift *new_states end end
successful.map(&:cost).minend
input = ARGF.read.scan(/\w/).map(&:to_sym).each_slice(4).to_a
puts solve(input)
input.insert 1, %i[D C B A], %i[D B A C]
puts solve(input)