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
|
const std = @import("std");
const aoc = @import("aoc");
const BagCount = struct { id: u64, count: u32 };
const BagRule = struct {
outer: u64,
innerit: std.mem.SplitIterator(u8),
fn from(line: []const u8) BagRule {
var partit = std.mem.split(u8, line, " bags contain ");
const outer = std.hash.CityHash64.hash(partit.next().?);
var innerit = std.mem.split(u8, partit.next().?, ", ");
return BagRule{ .outer = outer, .innerit = innerit };
}
fn nextInner(self: *BagRule) !?BagCount {
if (self.innerit.next()) |bagstr| {
if (std.mem.eql(u8, bagstr[0..2], "no")) return null;
const lastsep = std.mem.lastIndexOfScalar(u8, bagstr, ' ').?;
const firstsep = std.mem.indexOfScalar(u8, bagstr, ' ').?;
const count = try std.fmt.parseInt(u32, bagstr[0..firstsep], 10);
const id = std.hash.CityHash64.hash(bagstr[firstsep + 1 .. lastsep]);
return BagCount{ .id = id, .count = count };
} else {
return null;
}
}
};
fn countBagsTotal(map: *std.AutoHashMap(u64, std.ArrayList(BagCount)), outer: u64) u64 {
var sum: u64 = 0;
if (map.get(outer)) |inner| {
for (inner.items) |bag|
sum += bag.count * (1 + countBagsTotal(map, bag.id));
}
return sum;
}
fn countParentTypes(map: *std.AutoHashMap(u64, std.ArrayList(u64)), inner: u64, seen: *std.ArrayList(u64)) anyerror!u64 {
var sum: u64 = 0;
if (map.get(inner)) |outer| {
for (outer.items) |bagid| {
if (std.mem.indexOfScalar(u64, seen.items, bagid) == null) {
try seen.append(bagid);
sum += 1 + try countParentTypes(map, bagid, seen);
}
}
}
return sum;
}
fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
_ = args;
var lineit = std.mem.tokenize(u8, input, "\n");
var map = std.AutoHashMap(u64, std.ArrayList(u64)).init(allocator);
defer {
var mapit = map.iterator();
while (mapit.next()) |kv| kv.value_ptr.deinit();
map.deinit();
}
while (lineit.next()) |line| {
var rule = BagRule.from(line);
while (try rule.nextInner()) |inner| {
if (map.get(inner.id) == null)
try map.put(inner.id, std.ArrayList(u64).init(allocator));
try map.getEntry(inner.id).?.value_ptr.append(rule.outer);
}
}
const target = std.hash.CityHash64.hash("shiny gold");
var seen = std.ArrayList(u64).init(allocator);
defer seen.deinit();
const answer = try countParentTypes(&map, target, &seen);
return try std.fmt.allocPrint(allocator, "{d}", .{answer});
}
fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
_ = args;
var lineit = std.mem.tokenize(u8, input, "\n");
var map = std.AutoHashMap(u64, std.ArrayList(BagCount)).init(allocator);
defer {
var mapit = map.iterator();
while (mapit.next()) |kv| kv.value_ptr.deinit();
map.deinit();
}
const target = std.hash.CityHash64.hash("shiny gold");
while (lineit.next()) |line| {
var rule = BagRule.from(line);
if (map.get(rule.outer) == null)
try map.put(rule.outer, std.ArrayList(BagCount).init(allocator));
while (try rule.nextInner()) |bag| {
try map.getEntry(rule.outer).?.value_ptr.append(bag);
}
}
const answer = countBagsTotal(&map, target);
return try std.fmt.allocPrint(allocator, "{d}", .{answer});
}
pub const main = aoc.main(part1, part2, .{ "161", "30899" });
|
