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
|
const std = @import("std");
const Input = std.ArrayList(u64);
const test_input =
\\125 17
\\
;
pub fn parse(allocator: std.mem.Allocator, data: []const u8) !Input {
var it = std.mem.splitAny(u8, data, " \n");
var numbers = std.ArrayList(u64).init(allocator);
while (it.next()) |num| {
if (num.len == 0) continue;
const n = try std.fmt.parseInt(u64, num, 10);
try numbers.append(n);
}
return numbers;
}
test "part1" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const output = try part1(arena.allocator(), try parse(arena.allocator(), test_input));
try std.testing.expectEqual(55312, output);
}
fn stoneCount(allocator: std.mem.Allocator, number: u64, rounds: u8) !u64 {
if (rounds == 0) return 1;
if (number == 0) return stoneCount(allocator, 1, rounds - 1);
var num_str = try std.fmt.allocPrint(allocator, "{}", .{number});
if (num_str.len % 2 == 0) {
const a = try std.fmt.parseInt(u64, num_str[0 .. num_str.len / 2], 10);
const b = try std.fmt.parseInt(u64, num_str[num_str.len / 2 ..], 10);
allocator.free(num_str);
return try stoneCount(allocator, a, rounds - 1) +
try stoneCount(allocator, b, rounds - 1);
} else {
allocator.free(num_str);
return stoneCount(allocator, number * 2024, rounds - 1);
}
}
pub fn part1(allocator: std.mem.Allocator, input: Input) !u64 {
var count: u64 = 0;
for (input.items) |stone| {
count += try stoneCount(allocator, stone, 25);
}
return count;
}
fn stoneCoundCachedImpl(
allocator: std.mem.Allocator,
cache: *std.AutoHashMap(u64, [75]u64),
number: u64,
rounds: u8,
) error{ ParseIntError, OutOfMemory, Overflow, InvalidCharacter }!u64 {
if (number == 0) return stoneCountCached(allocator, cache, 1, rounds - 1);
var num_str = try std.fmt.allocPrint(allocator, "{}", .{number});
if (num_str.len % 2 == 0) {
const a = try std.fmt.parseInt(u64, num_str[0 .. num_str.len / 2], 10);
const b = try std.fmt.parseInt(u64, num_str[num_str.len / 2 ..], 10);
allocator.free(num_str);
return try stoneCountCached(allocator, cache, a, rounds - 1) +
try stoneCountCached(allocator, cache, b, rounds - 1);
} else {
allocator.free(num_str);
return stoneCountCached(allocator, cache, number * 2024, rounds - 1);
}
}
fn stoneCountCached(
allocator: std.mem.Allocator,
cache: *std.AutoHashMap(u64, [75]u64),
number: u64,
rounds: u8,
) !u64 {
if (rounds == 0) return 1;
if (cache.get(number)) |val| if (val[rounds - 1] != 0) return val[rounds - 1];
const val = try stoneCoundCachedImpl(allocator, cache, number, rounds);
const res = try cache.getOrPut(number);
if (!res.found_existing) @memset(res.value_ptr, 0);
res.value_ptr[rounds - 1] = val;
return val;
}
pub fn part2(allocator: std.mem.Allocator, input: Input) !u64 {
var cache = std.AutoHashMap(u64, [75]u64).init(allocator);
var count: u64 = 0;
for (input.items) |stone| {
count += try stoneCountCached(allocator, &cache, stone, 75);
}
return count;
}
|
