MY7LXSE7XMYWCK3BNEFILI4ZRTCPQYXYIP472HFFFJGULNFVWOFAC
const std = @import("std");
const Span = @import("lib/zig-regex/src/regex.zig").Span;
const Regex = @import("lib/zig-regex/src/regex.zig").Regex;
const path = "../data/day18/input.txt";
const RetType = u12;
const SnailType = u6;
const Str = []const u8;
const explode_limit = 5;
pub fn main() !void {
var timer = try std.time.Timer.start();
const ret = try first();
const t = timer.lap() / 1000;
try std.testing.expectEqual(@as(RetType, 3675), ret);
std.debug.print("Day 18a result: {d} \t\ttime: {d}µs\n", .{ ret, t });
}
pub fn first() !RetType {
const input = @embedFile(path);
var in = std.mem.tokenize(u8, input, "\n");
const allocator = std.testing.allocator;
var arena = std.heap.ArenaAllocator.init(allocator);
defer arena.deinit();
var ret: []const u8 = "";
while (in.next()) |line| {
if (ret.len == 0) {
ret = try reduce(arena.allocator(), &line[0..]);
} else {
const next = try std.fmt.allocPrint(arena.allocator(), "[{s},{s}]", .{ ret, line });
ret = try reduce(arena.allocator(), &next[0..]);
}
}
var pos: usize = 0;
return (try magnitude(&ret, &pos));
}
fn magnitude(input: *Str, pos: *usize) anyerror!RetType {
var left: isize = -1;
var right: isize = -1;
var right_side: bool = false;
while (pos.* < input.len) : (pos.* += 1) {
if (input.*[pos.*] == ']') {
break;
}
if (input.*[pos.*] == '[') {
pos.* += 1;
if (right_side) {
right = try magnitude(input, pos);
} else {
left = try magnitude(input, pos);
}
continue;
}
switch (input.*[pos.*]) {
',' => right_side = true,
'0',
'1',
'2',
'3',
'4',
'5',
'6',
'7',
'8',
'9',
=> {
if (right_side) {
right = try std.fmt.parseUnsigned(isize, input.*[pos.* .. pos.* + 1], 10);
} else {
left = try std.fmt.parseUnsigned(isize, input.*[pos.* .. pos.* + 1], 10);
}
},
else => unreachable,
}
}
if (left == -1 or right == -1) {
return @intCast(RetType, left + right + 1);
}
return @intCast(RetType, 3 * left + 2 * right);
}
fn reduce(a: std.mem.Allocator, input: *Str) anyerror!Str {
if (checkExplode(a, input)) {
_ = try reduce(a, input);
} else if (checkSplit(a, input)) {
_ = try reduce(a, input);
}
return input.*;
}
fn checkExplode(a: std.mem.Allocator, input: *Str) bool {
var count: u5 = 0;
for (input.*) |ch, i| {
if (ch == '[') {
count += 1;
if (count == explode_limit) {
explode(a, input, i) catch unreachable;
return true;
}
} else if (ch == ']') {
count -= 1;
}
}
return false;
}
fn checkSplit(a: std.mem.Allocator, input: *Str) bool {
return split(a, input) catch unreachable;
}
fn split(a: std.mem.Allocator, input: *Str) !bool {
// std.debug.print("split: {s}\n", .{input.*});
var two_digit = try Regex.compile(a, "\\d\\d+");
defer two_digit.deinit();
const two = (try two_digit.captures(input.*)) orelse return false;
const split_coords = two.boundsAt(0).?;
var ret = std.ArrayList(u8).init(a);
try ret.appendSlice(input.*[0..split_coords.lower]);
const split_num = try std.fmt.parseUnsigned(SnailType, input.*[split_coords.lower..split_coords.upper], 10);
try ret.append('[');
try ret.appendSlice(try std.fmt.allocPrint(a, "{d}", .{split_num / 2}));
try ret.append(',');
try ret.appendSlice(try std.fmt.allocPrint(a, "{d}", .{std.math.ceil(@intToFloat(f32, split_num) / 2)}));
try ret.append(']');
try ret.appendSlice(input.*[split_coords.upper..]);
input.* = ret.toOwnedSlice();
return true;
}
fn explode(a: std.mem.Allocator, input: *Str, pivot: usize) !void {
// std.debug.print("explode: {s} {d}\n", .{ input.*, pivot });
var number = try Regex.compile(a, "(\\d+)");
defer number.deinit();
var last_number = try Regex.compile(a, "(\\d+)[^\\d+]+$");
defer last_number.deinit();
var exp_number = try Regex.compile(a, "^\\[(\\d+)[^\\d]+(\\d+)");
defer exp_number.deinit();
const exp_nums = (try exp_number.captures(input.*[pivot..])).?;
// Exploding left item
const exp_left = [2]usize{ pivot + exp_nums.boundsAt(1).?.lower, pivot + exp_nums.boundsAt(1).?.upper };
// Exploding right item
const exp_right = [2]usize{ pivot + exp_nums.boundsAt(2).?.lower, pivot + exp_nums.boundsAt(2).?.upper };
// std.debug.print("expLeft: {s} expRight: {s}\n", .{ input.*[exp_left[0]..exp_left[1]], input.*[exp_right[0]..exp_right[1]] });
var new_string = std.ArrayList(u8).init(a);
if (try last_number.captures(input.*[0..pivot])) |lefts| {
if (lefts.boundsAt(1)) |l| {
// std.debug.print("{any} {s}\n", .{ l, input.*[l.lower..l.upper] });
try new_string.appendSlice(input.*[0..l.lower]);
const left_num = try std.fmt.parseUnsigned(SnailType, input.*[l.lower..l.upper], 10);
const exp_left_num = try std.fmt.parseUnsigned(SnailType, input.*[exp_left[0]..exp_left[1]], 10);
try new_string.appendSlice(try std.fmt.allocPrint(a, "{d}", .{left_num + exp_left_num}));
try new_string.appendSlice(input.*[l.upper .. exp_left[0] - 1]);
}
} else {
try new_string.appendSlice(input.*[0 .. exp_left[0] - 1]);
}
try new_string.append('0');
if (try number.captures(input.*[exp_right[1] + 1 ..])) |rights| {
if (rights.boundsAt(0)) |r_raw| {
const r = Span{ .lower = r_raw.lower + exp_right[1] + 1, .upper = r_raw.upper + exp_right[1] + 1 };
// std.debug.print("{any} {s}\n", .{ r, input.*[r.lower..r.upper] });
try new_string.appendSlice(input.*[exp_right[1] + 1 .. r.lower]);
const right_num = try std.fmt.parseUnsigned(SnailType, input.*[r.lower..r.upper], 10);
const exp_left_num = try std.fmt.parseUnsigned(SnailType, input.*[exp_right[0]..exp_right[1]], 10);
try new_string.appendSlice(try std.fmt.allocPrint(a, "{d}", .{right_num + exp_left_num}));
try new_string.appendSlice(input.*[r.upper..]);
}
} else {
try new_string.appendSlice(input.*[exp_right[1] + 1 ..]);
}
input.* = new_string.toOwnedSlice();
}
test "day18a" {
try std.testing.expectEqual(@as(RetType, 3675), try first());
}
[[[3,9],[7,2]],[[8,4],[[5,6],0]]]
[[[1,[4,9]],[[1,8],[1,5]]],[[[2,6],[6,7]],[[4,6],[9,0]]]]
[[[[9,2],1],[[0,7],[9,6]]],[[5,9],[7,[6,9]]]]
[8,9]
[[4,[6,1]],[2,[[6,7],2]]]
[[6,[[4,1],5]],[4,9]]
[[[0,6],[8,[8,5]]],[6,9]]
[[0,[1,0]],[[8,[7,4]],[[1,1],[5,0]]]]
[[[1,[0,1]],6],[1,9]]
[[2,[[9,0],[6,1]]],[[8,4],[5,7]]]
[[[[5,3],[0,9]],[1,[0,7]]],[[9,0],[2,[2,0]]]]
[[2,[2,[6,8]]],[[9,[5,4]],[4,[3,4]]]]
[[[[4,0],[7,0]],[[4,8],[5,8]]],[[[7,2],[2,2]],[[3,3],3]]]
[[5,0],5]
[[8,[[5,0],2]],[6,[5,1]]]
[[[9,[8,8]],[8,7]],[[[4,2],4],[[5,1],[4,8]]]]
[[[[1,1],3],5],9]
[[[[1,7],[6,5]],5],[[0,6],0]]
[[9,6],2]
[[[2,[0,8]],[8,[2,1]]],5]
[[[9,[3,7]],3],[0,[5,9]]]
[[[2,[1,7]],6],[[7,[8,2]],[[8,2],8]]]
[[[[1,2],1],5],2]
[4,[8,[3,9]]]
[[[[8,9],[6,0]],[[1,6],7]],8]
[[2,[8,1]],3]
[[2,2],[[8,[0,2]],[[5,0],5]]]
[9,[2,[[6,1],[8,9]]]]
[[4,[[6,6],4]],[[[9,3],[3,1]],5]]
[[[7,8],1],0]
[[[8,8],[[1,0],7]],[4,6]]
[9,8]
[[[[4,2],9],[[9,9],7]],[7,[9,[5,8]]]]
[[4,[4,[3,3]]],8]
[0,2]
[[4,[5,5]],[9,[[6,9],4]]]
[[[7,3],[[1,2],6]],[[[2,4],[6,7]],[[5,0],9]]]
[[[[2,0],5],[4,5]],[[[6,5],[6,0]],[1,[3,4]]]]
[[3,[6,8]],[[[3,0],0],[[2,8],7]]]
[[[4,[6,2]],[9,[4,1]]],[8,[3,4]]]
[[[6,[6,8]],[7,[2,0]]],[4,[[8,7],[1,6]]]]
[2,[0,[4,0]]]
[[[[0,5],1],8],[[9,[0,3]],3]]
[[[3,[5,2]],[3,[3,2]]],[[[7,3],1],7]]
[1,[[[1,8],[1,7]],0]]
[[8,6],[[0,4],4]]
[[[8,2],[4,6]],3]
[5,[[[7,5],[4,5]],[0,2]]]
[[3,[3,6]],6]
[[[[6,8],[5,7]],[[7,3],5]],[[8,[4,8]],8]]
[[[[5,8],[3,1]],[[3,7],[7,0]]],[[9,7],0]]
[[2,[[5,3],8]],0]
[0,[2,8]]
[[8,9],[[[2,2],[4,7]],[[4,0],1]]]
[[[[3,0],8],[[7,3],[6,1]]],[[3,8],[4,2]]]
[[[[6,7],[4,3]],[[3,9],5]],8]
[[[7,7],[[3,4],7]],[[[0,4],1],9]]
[[[7,5],5],[[2,[9,9]],[0,[3,5]]]]
[[[[3,3],[6,1]],[5,8]],[[4,7],[8,1]]]
[[[0,[7,3]],[6,[7,2]]],[[0,8],7]]
[[[2,7],[9,7]],[8,[3,8]]]
[[[0,2],6],[[9,[6,5]],[[3,9],1]]]
[[7,[[3,4],[2,8]]],[[[4,1],4],7]]
[[3,[[3,4],6]],[[3,9],[[4,5],[3,0]]]]
[[[5,[5,1]],[2,4]],[1,[[1,6],6]]]
[[[5,6],[[1,3],[5,0]]],[[[4,1],8],[5,5]]]
[[[[2,0],7],[[8,9],1]],[[[4,0],[1,6]],1]]
[[[2,0],[[4,2],[9,9]]],[4,9]]
[[[[1,9],6],2],[[5,4],[2,4]]]
[[[[4,1],[4,5]],[[2,3],2]],[3,[[8,8],1]]]
[[[[8,1],0],[2,2]],[[2,[7,1]],1]]
[[[7,4],[[1,3],5]],[[6,8],[[0,0],2]]]
[[[1,2],8],[[[1,7],[4,0]],[[8,2],8]]]
[[[0,8],[3,6]],[[[5,3],7],[9,7]]]
[[4,6],[[[7,9],[7,5]],[[4,6],[8,4]]]]
[[[[7,3],0],[[6,2],[7,2]]],[9,[[8,0],3]]]
[[[3,0],1],[[2,3],1]]
[[[5,[8,6]],[[1,2],2]],[[[1,4],6],[5,[7,1]]]]
[[[[1,5],8],[0,0]],4]
[[[7,[6,8]],3],[[5,1],[[2,8],[4,6]]]]
[3,[[[5,8],[4,5]],[[7,7],8]]]
[[6,[7,[8,2]]],[[9,0],0]]
[[[8,[7,6]],1],[[2,4],6]]
[[[[0,4],2],[0,7]],[6,6]]
[1,[[1,9],[9,3]]]
[[[[5,2],[5,3]],[[9,0],4]],2]
[[[[5,5],3],[7,[1,2]]],[6,[7,2]]]
[[[[2,1],3],8],[[2,[8,2]],[7,4]]]
[[8,[9,[1,8]]],[[[4,4],[0,6]],[6,3]]]
[[[1,6],[1,[2,5]]],0]
[[[[0,1],[7,2]],[[7,2],3]],[2,[[7,8],[0,7]]]]
[[[[1,8],8],[[5,7],[3,4]]],[[[2,5],[7,4]],[[8,4],9]]]
[[[2,2],[5,[1,0]]],[[[6,6],[3,0]],[[8,5],5]]]
[[[[8,2],[4,8]],[9,4]],[[8,[7,9]],0]]
[[3,[5,[2,4]]],[[[8,1],0],[[0,4],[4,5]]]]
[[5,[9,[3,8]]],[4,[1,[5,2]]]]
[[[3,[0,6]],[7,[8,7]]],[[6,8],[[8,7],0]]]
[[[[0,2],5],[4,6]],3]
[[6,7],[[1,[4,6]],9]]
[7,[3,[[8,8],5]]]