sharparam.com
Code for the Advent of Code event
aoc
advent-of-code
1#!/usr/bin/env ruby
2# frozen_string_literal: true
3
4HALLWAY_LEGAL_INDICES = [0, 1, 3, 5, 7, 9, 10].to_set.freeze
5
6AMPHIPOD_MOVE_COSTS = {
7 A: 1,
8 B: 10,
9 C: 100,
10 D: 1000
11}.freeze
12
13AMPHIPOD_ROOM = {
14 A: 0,
15 B: 1,
16 C: 2,
17 D: 3
18}.freeze
19
20ROOM_AMPHIPOD = {
21 0 => :A,
22 1 => :B,
23 2 => :C,
24 3 => :D
25}.freeze
26
27ROOM_HALLWAY_INDEX = {
28 0 => 2,
29 1 => 4,
30 2 => 6,
31 3 => 8
32}.freeze
33
34class Room
35 attr_reader :full_size, :room_index
36
37 def initialize(full_size, room_index, amphipods = nil)
38 @full_size = full_size
39 @room_index = room_index
40 @amphipods = amphipods || []
41 end
42
43 def [](i)
44 @amphipods[i]
45 end
46
47 def desired_amphipod
48 ROOM_AMPHIPOD[@room_index]
49 end
50
51 def hallway_index
52 ROOM_HALLWAY_INDEX[@room_index]
53 end
54
55 def solved?
56 @amphipods.size == @full_size && @amphipods.all?(desired_amphipod)
57 end
58
59 def shift!
60 @amphipods.shift
61 end
62
63 def unshift!(amphipod)
64 @amphipods.unshift amphipod
65 end
66
67 def can_enter?(amphipod)
68 amphipod == desired_amphipod && @amphipods.size < @full_size && @amphipods.all?(desired_amphipod)
69 end
70
71 def can_exit?
72 @amphipods[0] != desired_amphipod || !@amphipods.all?(desired_amphipod)
73 end
74
75 def exit_cost(to = nil)
76 room_distance = @full_size - @amphipods.size + 1
77 hallway_distance = to.nil? ? 0 : (to - ROOM_HALLWAY_INDEX[@room_index]).abs
78 distance = room_distance + hallway_distance
79 distance * AMPHIPOD_MOVE_COSTS[@amphipods[0]]
80 end
81
82 def enter_cost(amphipod, from = nil)
83 hallway_distance = from.nil? ? 0 : (from - ROOM_HALLWAY_INDEX[@room_index]).abs
84 room_distance = @full_size - @amphipods.size
85 distance = hallway_distance + room_distance
86 distance * AMPHIPOD_MOVE_COSTS[amphipod]
87 end
88
89 def empty?
90 @amphipods.empty?
91 end
92
93 def hash
94 [@full_size, @room_index, @amphipods].hash
95 end
96
97 def dup
98 self.class.new(@full_size, @room_index, @amphipods.dup)
99 end
100end
101
102class State
103 attr_accessor :hallway, :rooms, :cost
104
105 def initialize(hallway, rooms, cost)
106 @hallway = hallway
107 @rooms = rooms
108 @cost = cost
109 end
110
111 def solved?
112 @rooms.all?(&:solved?)
113 end
114
115 def can_reach_room?(hallway_index, room_index)
116 enter_index = ROOM_HALLWAY_INDEX[room_index]
117 return true if (hallway_index - enter_index).abs == 1
118 if hallway_index < enter_index
119 HALLWAY_LEGAL_INDICES.select { _1 > hallway_index && _1 < enter_index }.each do |i|
120 return false unless @hallway[i].nil?
121 end
122 else
123 HALLWAY_LEGAL_INDICES.select { _1 < hallway_index && _1 > enter_index }.each do |i|
124 return false unless @hallway[i].nil?
125 end
126 end
127 true
128 end
129
130 def can_reach_hallway?(room_index, hallway_index)
131 return false unless HALLWAY_LEGAL_INDICES.include? hallway_index
132 exit_index = ROOM_HALLWAY_INDEX[room_index]
133 return @hallway[hallway_index].nil? if (hallway_index - exit_index).abs == 1
134 if hallway_index < exit_index
135 HALLWAY_LEGAL_INDICES.select { _1 >= hallway_index && _1 < exit_index }.each do |i|
136 return false unless @hallway[i].nil?
137 end
138 else
139 HALLWAY_LEGAL_INDICES.select { _1 <= hallway_index && _1 > exit_index }.each do |i|
140 return false unless @hallway[i].nil?
141 end
142 end
143 true
144 end
145
146 def can_amphipod_reach_room?(amphipod, hallway_index)
147 room_index = AMPHIPOD_ROOM[amphipod]
148 can_reach_room? hallway_index, room_index
149 end
150
151 def valid_exit_indices(room_index)
152 HALLWAY_LEGAL_INDICES.select { can_reach_hallway? room_index, _1 }
153 end
154
155 def gen_states(cache)
156 new_states = []
157
158 @hallway.each do |hallway_index, amphipod|
159 next if amphipod.nil?
160 target_room_index = AMPHIPOD_ROOM[amphipod]
161 target_room = @rooms[target_room_index]
162 next unless can_amphipod_reach_room? amphipod, hallway_index
163 next unless target_room.can_enter? amphipod
164 cost = target_room.enter_cost amphipod, hallway_index
165 new_state = dup
166 new_state.cost += cost
167 new_state.hallway.delete hallway_index
168 new_state.rooms[target_room_index].unshift! amphipod
169 cached_cost = cache[new_state.cache_key]
170 next unless cached_cost.nil? || cached_cost > new_state.cost
171 cache[new_state.cache_key] = new_state.cost
172 new_states << new_state
173 end
174
175 @rooms.each_with_index do |room, room_index|
176 next if room.empty?
177 next unless room.can_exit?
178 amphipod = room[0]
179 target_hallway_indices = valid_exit_indices room_index
180 next if target_hallway_indices.empty?
181 target_hallway_indices.each do |target_hallway_index|
182 cost = room.exit_cost target_hallway_index
183 new_state = dup
184 new_state.cost += cost
185 new_state.hallway[target_hallway_index] = amphipod
186 new_state.rooms[room_index].shift!
187 cached_cost = cache[new_state.cache_key]
188 next unless cached_cost.nil? || cached_cost > new_state.cost
189 cache[new_state.cache_key] = new_state.cost
190 new_states << new_state
191 end
192 end
193
194 new_states
195 end
196
197 def dup
198 self.class.new(@hallway.dup, @rooms.map(&:dup), @cost)
199 end
200
201 def cache_key
202 [@hallway, @rooms].hash
203 end
204end
205
206def solve(input)
207 state = State.new({}, input.transpose.map.with_index { Room.new _1.size, _2, _1 }, 0)
208 successful = []
209 queue = [state]
210 cache = { state.cache_key => state.cost }
211
212 while queue.any?
213 current_state = queue.shift
214 if current_state.solved?
215 successful << current_state
216 else
217 new_states = current_state.gen_states cache
218 queue.unshift *new_states
219 end
220 end
221
222 successful.map(&:cost).min
223end
224
225input = ARGF.read.scan(/\w/).map(&:to_sym).each_slice(4).to_a
226
227puts solve(input)
228
229input.insert 1, %i[D C B A], %i[D B A C]
230
231puts solve(input)