Setup
I import the standard library and also initiate an allocator. There isn’t much noteworthy stuff here except for the defered for loop to deinit every nested ArrayList.
const std = @import("std");
const mem = std.mem;
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
const ArrayList = std.ArrayList;
pub fn main() void {
const input = switch (true) {
true => @embedFile("input.txt"),
false =>
\\7 6 4 2 1
\\1 2 7 8 9
\\9 7 6 2 1
\\1 3 2 4 5
\\8 6 4 4 1
\\1 3 6 7 9
,
};
const parsed = parseInput(input);
defer {
for (parsed.items) |report| {
report.deinit();
}
parsed.deinit();
}
std.debug.print("Part 1: {d}\n", .{part1(parsed)});
std.debug.print("Part 2: {d}\n", .{part2(parsed)});
}Parsing
The input is in the form of several lines, with each line having a list of whitespace-separated numbers. This is relatively simple to parse by iterating over lines and then iterating over the number in each line.
const inputType = ArrayList(ArrayList(i13));
fn parseInput(input: []const u8) inputType {
const splitScalar = std.mem.splitScalar;
const trim = std.mem.trim;
const tokenizeScalar = std.mem.tokenizeScalar;
var lines_it = splitScalar(u8, trim(u8, input, "\n"), '\n');
var reports = ArrayList(ArrayList(i13)).init(allocator);
while (lines_it.next()) |line| {
var nums_it = tokenizeScalar(u8, line, ' ');
var list = ArrayList(i13).init(allocator);
while (nums_it.next()) |num_s| {
const num = parseInt(i13, num_s);
list.append(num) catch unreachable;
}
reports.append(list) catch unreachable;
}
return reports;
}
fn parseInt(comptime T: type, s: []const u8) T {
return std.fmt.parseInt(T, s, 10) catch unreachable;
}For convenience, I defined inputType. Since the numbers in my input weren’t very large, I used i13 as my number type. Zig lets you use integer types of any width (in the range [1, 65536)).
Part One
The lines of numbers are called reports and each number within is called a level. We need to count the number of “safe” reports. Safe reports are reports where the levels are either all increasing or all decreasing and the difference between any two adjacent levels is >= 1 and <= 3.
fn part1(input: inputType) u32 {
var count: u32 = 0;
for (input.items) |report| {
var safe = true;
const firstDiffSign = (report.items[1] - report.items[0]) > 0;
for (1..report.items.len) |i| {
const diff = report.items[i] - report.items[i - 1];
if (((diff > 0) != firstDiffSign) or (@abs(diff) < 1 or @abs(diff) > 3)) {
safe = false;
break;
}
}
if (safe) {
count += 1;
}
}
return count;
}Part Two
It turns out we need to be more lenient in counting reports. We now can skip over a single bad level in each report, that is, if removing a single level from an unsafe report would make it safe, that report is now considered safe.
My solution tries skipping each number in the report and seeing if that makes the report safe. Note that I include the length of the report in the i_skip loop to cover the original case where no levels are skipped. There is probably a way to solve this in O(n) time instead of the current O(n²) time but I didn’t spend much time figuring that out and it doesn’t really matter anyway since our n is pretty small.
fn part2(input: inputType) u32 {
var count: u32 = 0;
for (input.items) |report| {
var safe_all = false;
for (0..(report.items.len + 1)) |i_skip| {
var safe = true;
var old_value: ?i13 = null;
var firstDiffSign: ?bool = null;
for (0..report.items.len) |i| {
if (i == i_skip) {
continue;
}
if (old_value == null) {
old_value = report.items[i];
firstDiffSign = (report.items[i + 1] - report.items[i]) > 0;
continue;
}
const diff = report.items[i] - old_value.?;
if (((diff > 0) != firstDiffSign.?) or (@abs(diff) < 1 or @abs(diff) > 3)) {
safe = false;
break;
}
old_value = report.items[i];
}
safe_all = safe_all or safe;
}
if (safe_all) {
count += 1;
}
}
return count;
}