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
|
const std = @import("std");
const test_input =
\\11-22,95-115,998-1012,1188511880-1188511890,222220-222224,1698522-1698528,446443-446449,38593856-38593862,565653-565659,824824821-824824827,2121212118-2121212124
\\
;
test part1 {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const allocator = arena.allocator();
try std.testing.expectEqual(1227775554, try part1(allocator, try parse(allocator, test_input)));
}
test part2 {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const allocator = arena.allocator();
try std.testing.expectEqual(4174379265, try part2(allocator, try parse(allocator, test_input)));
}
const Input = []struct {
from: u64,
to: u64,
};
pub fn parse(allocator: std.mem.Allocator, input: []const u8) !Input {
var spans = std.mem.splitScalar(u8, input, ',');
var parsed = try std.ArrayList(@typeInfo(Input).pointer.child).initCapacity(allocator, 0);
while (spans.next()) |span_| {
var span = if (std.mem.endsWith(u8, span_, "\n")) span_[0 .. span_.len - 1] else span_;
const dash = std.mem.indexOfScalar(u8, span, '-') orelse return error.InvalidInput;
const from = try std.fmt.parseInt(u64, span[0..dash], 10);
const to = try std.fmt.parseInt(u64, span[dash + 1 ..], 10);
try parsed.append(allocator, .{ .from = from, .to = to });
}
return parsed.toOwnedSlice(allocator);
}
pub fn part1(allocator: std.mem.Allocator, input: Input) !usize {
var allocating_writer = std.io.Writer.Allocating.init(allocator);
const writer = &allocating_writer.writer;
var answer: usize = 0;
for (input) |span| {
for (span.from..span.to + 1) |n| {
allocating_writer.clearRetainingCapacity();
try writer.print("{}", .{n});
const written = allocating_writer.written();
if (written.len % 2 == 1) continue;
const len = written.len / 2;
if (!std.mem.eql(u8, written[0..len], written[len..])) continue;
// std.debug.print("{}\n", .{n});
answer += n;
}
}
return answer;
}
pub fn part2(allocator: std.mem.Allocator, input: Input) !usize {
var allocating_writer = std.io.Writer.Allocating.init(allocator);
const writer = &allocating_writer.writer;
var answer: usize = 0;
for (input) |span| {
n: for (span.from..span.to + 1) |n| {
allocating_writer.clearRetainingCapacity();
try writer.print("{}", .{n});
const written = allocating_writer.written();
for (2..written.len + 1) |repetitions| {
if (written.len % repetitions != 0) continue;
const len = written.len / repetitions;
const first = written[0..len];
var windows = std.mem.window(u8, written, len, len);
while (windows.next()) |window| {
if (!std.mem.eql(u8, first, window)) break;
} else { // all were equal
answer += n;
continue :n;
}
}
}
}
return answer;
}
|
