-
Notifications
You must be signed in to change notification settings - Fork 0
/
solve.rb
105 lines (89 loc) · 2.8 KB
/
solve.rb
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
require 'set'
class Solve
def self.run(start)
start ||= 'shiny gold'
input = File.read('./input')
puts "Part one, possible containers: #{count_containers(clean(start), input)}"
puts "part two, required contents: #{count_contents(clean(start), input)}"
end
def self.count_containers(start, input)
accum_containers(start, graph(input)).count
end
def self.count_contents(start, input)
accum_contents(start, graph(input))
.map { |content| content[:count] }
.reduce(&:+) || 0
end
def self.accum_contents(start, graph, accum = [])
if contents(graph, start)
contents = contents(graph, start)
contents.each { |content| accum << content }
contents.each do |content|
(1..content[:count]).each do
accum_contents(content[:name], graph, accum)
end
end
end
accum
end
def self.accum_containers(start, graph, accum = [].to_set)
if contained_by(graph, start)
nodes = contained_by(graph, start)
nodes.each { |n| accum << n }
nodes.each { |n| accum_containers(n, graph, accum) }
end
accum
end
def self.graph(input)
input.lines
.map { |line| parse_line(line) }
.reduce do |accum, elem|
accum.merge(elem) do |_, val_1, val_2|
merged = {}
join_merge(:contained_by, val_1, val_2, merged)
join_merge(:contains, val_1, val_2, merged)
merged
end
end
end
def self.join_merge(key, val_1, val_2, merging)
merging[key] = val_1.fetch(key, []) + val_2.fetch(key, []) if val_1[key] || val_2[key]
merging
end
def self.parse_line(line)
container_match = /((?:\w|\s)+) bags contain/.match(line)&.captures&.first
contain_matches = line.scan(/(?:(?:(?<count>\d) (?<name>[ a-z]*) bags?))+/)
container = clean(container_match)
contents = contain_matches.map { |count, name| {count: count.to_i, name: clean(name) }}
graph = contents.reduce({}) { |g, content| set_contained_by(g, content[:name], container) }
set_contents(graph, container, contents)
end
def self.contents(graph, key)
graph.fetch(key, nil)&.fetch(:contains, nil)
end
def self.set_contents(graph, container, contents)
if graph[container] && graph[container][:contains]
graph[container][:contains] += contents
else
graph[container] = {contains: contents}
end
graph
end
def self.contained_by(graph, key)
graph.fetch(key, nil)&.fetch(:contained_by, nil)
end
def self.set_contained_by(graph, content, container)
if graph[content] && graph[content][:contained_by]
graph[content][:contained_by] += [container]
else
graph[content] = {contained_by: [container]}
end
graph
end
def self.clean(string)
string.gsub(' ', '_').intern
end
end
if __FILE__ == $0
Solve.run(ARGV[0])
end