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
|
const std = @import("std");
const aoc = @import("aoc");
fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
_ = args;
var target: u32 = 0;
var intlist = std.ArrayList(u32).init(allocator);
defer intlist.deinit();
var lineit = std.mem.tokenize(u8, input, "\n");
while (lineit.next()) |line| {
var val = try std.fmt.parseInt(u32, line, 10);
if (val > target) {
target = val;
}
try intlist.append(val);
}
target += 3;
try intlist.append(target);
if (intlist.items.len == 0) return null;
std.sort.sort(u32, intlist.items, {}, comptime std.sort.asc(u32));
var diffs = [_]u32{ 0, 0, 0, 0 };
var last: u32 = 0;
for (intlist.items) |ov| {
if (ov - last > 3 or ov == last) {
aoc.debugfmt("Unable to find a suitable adapter for {} output jolts (next: {} jolts)\n", .{ last, ov });
return aoc.Error.InvalidInput;
}
diffs[ov - last] += 1;
last = ov;
}
return try std.fmt.allocPrint(allocator, "{d}", .{diffs[1] * diffs[3]});
}
fn countArrangements(arrangement: []u32, adapters: []const u32, adaptermask: []u1, target: u32, fillcount: u32, searchstart: u32, count: *u32) void {
var last: u32 = 0;
if (fillcount > 0) {
last = arrangement[fillcount - 1];
}
if (last == target) {
count.* += 1;
return;
}
for (adapters[searchstart..]) |adap, i| {
if (adaptermask[searchstart + i] == 1) continue;
if (adap > last + 3) break;
adaptermask[searchstart + i] = 1;
arrangement[fillcount] = adap;
countArrangements(arrangement, adapters, adaptermask, target, fillcount + 1, searchstart + @intCast(u32, i) + 1, count);
adaptermask[searchstart + i] = 0;
}
}
fn groupPermutations(adapters: []const u32) u64 {
if (adapters.len == 1) return 1;
var count: u64 = 0;
for (adapters) |_, i| {
if (i == 0) continue;
if (adapters[i] <= adapters[0] + 3) {
count += groupPermutations(adapters[i..]);
}
}
return count;
}
fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
_ = args;
var target: u32 = 0;
var intlist = std.ArrayList(u32).init(allocator);
defer intlist.deinit();
try intlist.append(0);
var lineit = std.mem.tokenize(u8, input, "\n");
while (lineit.next()) |line| {
var val = try std.fmt.parseInt(u32, line, 10);
if (val > target) {
target = val;
}
try intlist.append(val);
}
target += 3;
try intlist.append(target);
if (intlist.items.len == 0) return aoc.Error.InvalidInput;
std.sort.sort(u32, intlist.items, {}, comptime std.sort.asc(u32));
var gapstart: u32 = 0;
var multiplier: u128 = 1;
var i: u32 = 0;
while (i < intlist.items.len - 1) : (i += 1) {
// whenever we encounter a 3 jolt gap, we can calc permutations of group before
if (i + 1 < intlist.items.len and intlist.items[i + 1] == intlist.items[i] + 3) {
multiplier *= groupPermutations(intlist.items[gapstart .. i + 1]);
aoc.debugfmt("gap from {} to {} => {}\n", .{ intlist.items[i], intlist.items[i + 1], multiplier });
aoc.debugfmt("group size: {}\n", .{i + 1 - gapstart});
gapstart = i + 1;
}
}
return try std.fmt.allocPrint(allocator, "{d}", .{multiplier});
}
pub const main = aoc.main(part1, part2, .{ "1998", "347250213298688" });
|
