-
Notifications
You must be signed in to change notification settings - Fork 0
/
day11.cr
169 lines (151 loc) · 4.89 KB
/
day11.cr
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
# The first floor contains a strontium generator, a strontium-compatible
# microchip, a plutonium generator, and a plutonium-compatible
# microchip. The second floor contains a thulium generator, a ruthenium
# generator, a ruthenium-compatible microchip, a curium generator, and a
# curium-compatible microchip. The third floor contains a
# thulium-compatible microchip. The fourth floor contains nothing
# relevant.
# F4
# F3 TM
# F2 TG RG RM CG CM
# F1 SG SM PG PM
# https://en.wikipedia.org/wiki/Breadth-first_search
# 1 procedure BFS(G,start_v):
# 2 let Q be a queue
# 3 label start_v as discovered
# 4 Q.enqueue(start_v)
# 5 while Q is not empty
# 6 v = Q.dequeue()
# 7 if v is the goal:
# 8 return v
# 9 for all edges from v to w in G.adjacentEdges(v) do
# 10 if w is not labeled as discovered:
# 11 label w as discovered
# 12 w.parent = v
# 13 Q.enqueue(w)
# also !any? == none?
# none? &.index("G")
module Solver
@@discovered = Hash(UInt64, Bool).new { |h, k| h[k] = false }
class State
property floors = Hash(Int32, Array(String)).new { |h, k| h[k] = [] of String }
property parent : State?
def initialize
end
def valid
floors.each do |k, v|
if v.any? &.includes?("SM")
return false if !(v.includes?("SG") || v.none? &.index("G"))
end
if v.any? &.includes?("CM")
return false unless v.includes?("CG") || v.none? &.index("G")
end
if v.any? &.includes?("RM")
return false unless v.includes?("RG") || v.none? &.index("G")
end
if v.any? &.includes?("TM")
return false unless v.includes?("TG") || v.none? &.index("G")
end
if v.any? &.includes?("EM")
return false unless v.includes?("EG") || v.none? &.index("G")
end
if v.any? &.includes?("DM")
return false unless v.includes?("DG") || v.none? &.index("G")
end
end
true
end
def height
current = parent
h = 0
until current.nil?
h += 1
current = current.parent
end
h
end
def with_elevator
floors.find { |k, v| v.includes? "E" }.not_nil!.first
end
def edges
options = [] of State
floors[with_elevator].reject("E").each_combination(2) do |c|
if with_elevator > 1
n = State.new
n.floors = self.floors.clone
n.floors[with_elevator].reject!("E").reject! { |i| c.includes? i }
n.floors[with_elevator - 1] += c.to_a
n.floors[with_elevator - 1] << "E"
n.floors[with_elevator - 1].sort!
n.floors[with_elevator].sort!
n.try { |n| options << n if n.valid }
end
if with_elevator < 4
n = State.new
n.floors = self.floors.clone
n.floors[with_elevator].reject!("E").reject! { |i| c.includes? i }
n.floors[with_elevator + 1] += c.to_a
n.floors[with_elevator + 1] << "E"
n.floors[with_elevator + 1].sort!
n.floors[with_elevator].sort!
n.try { |n| options << n if n.valid }
end
end
floors[with_elevator].reject("E").each_combination(1) do |c|
if with_elevator > 1
n = State.new
n.floors = self.floors.clone
n.floors[with_elevator].reject!("E").reject! { |i| c.includes? i }
n.floors[with_elevator - 1] += c.to_a
n.floors[with_elevator - 1] << "E"
n.floors[with_elevator - 1].sort!
n.floors[with_elevator].sort!
n.try { |n| options << n if n.valid }
end
if with_elevator < 4
n = State.new
n.floors = self.floors.clone
n.floors[with_elevator].reject!("E").reject! { |i| c.includes? i }
n.floors[with_elevator + 1] += c.to_a
n.floors[with_elevator + 1] << "E"
n.floors[with_elevator + 1].sort!
n.floors[with_elevator].sort!
n.try { |n| options << n if n.valid }
end
end
options
end
end
def self.solved?(state)
state.floors[4].sort == ["CG", "CM", "E", "PG", "PM", "RG", "RM", "SG", "SM", "TG", "TM", "DG", "DM", "EG", "EM"].sort
end
def self.solve(initial)
q = Deque(State).new
q.push initial
while q.size > 0
n = q.shift
if solved? n
return n
else
n.edges.each do |e|
if !@@discovered[e.floors.hash]
@@discovered[e.floors.hash] = true
e.parent = n
q.push e
end
end
end
end
end
def self.initial
s = State.new
s.floors[1] = ["SG", "SM", "PG", "PM", "DG", "DM", "EG", "EM", "E"].sort
s.floors[2] = ["TG", "RG", "RM", "CG", "CM"].sort
s.floors[3] = ["TM"].sort
s.floors[4] = [] of String
s
end
end
solution = Solver.solve Solver.initial
# pp solution
pp solution.try &.height