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
|
const AutoHashMap = std.AutoHashMap;
const FixedBufferAllocator = std.heap.FixedBufferAllocator;
const math = std.math;
const print = std.debug.print;
const split = std.mem.split;
const std = @import("std");
const tokenize = std.mem.tokenize;
const Children = packed struct { left: Pair, right: Pair };
const Pair = packed struct { left: u8, right: u8 };
const Rule = packed struct { adj: Pair, _: u32, ins: u8 };
fn KV(comptime M: type, comptime index: usize) type {
const type_info = @typeInfo(@typeInfo(M).Pointer.child.KV);
return type_info.Struct.fields[index].field_type;
}
fn addOrPut(map: anytype, key: KV(@TypeOf(map), 0),
value: KV(@TypeOf(map), 1)) !void {
const result = try map.getOrPut(key);
if (result.found_existing)
result.value_ptr.* += value
else
result.value_ptr.* = value;
}
pub fn main() !void {
var buffer: [0xdecaf]u8 = undefined;
var fba = FixedBufferAllocator.init(buffer[0..]);
var input = split(@embedFile("input"), "\n\n");
var count = AutoHashMap(Pair, usize).init(&fba.allocator);
defer count.deinit();
const template = input.next().?;
for (template[0..template.len-1]) |*c|
try addOrPut(&count, @ptrCast(*const Pair, c).*, 1);
var rules = tokenize(input.next().?, "\n");
var insertions = AutoHashMap(Pair, Children).init(&fba.allocator);
defer insertions.deinit();
while (rules.next()) |rule| {
const unmasked = @ptrCast(*const Rule, rule.ptr);
try insertions.put(unmasked.adj, .{
.left = .{ .left = unmasked.adj.left, .right = unmasked.ins },
.right = .{ .left = unmasked.ins, .right = unmasked.adj.right },
});
}
var result = AutoHashMap(u8, usize).init(&fba.allocator);
for (template) |c|
try addOrPut(&result, c, 1);
var step: u8 = 0;
while (step < 40) : (step += 1) {
var tmp = AutoHashMap(Pair, usize).init(&fba.allocator);
var items = count.iterator();
while (items.next()) |entry| {
const k = insertions.get(entry.key_ptr.*) orelse continue;
const v = entry.value_ptr.*;
try addOrPut(&tmp, k.left, v);
try addOrPut(&tmp, k.right, v);
try addOrPut(&result, k.left.right, v);
}
count.deinit();
count = tmp;
}
var values = result.valueIterator();
var max = values.next().?.*;
var min = max;
while (values.next()) |value| {
max = math.max(value.*, max);
min = math.min(value.*, min);
}
print("{}\n", .{ max - min });
}
|
