Skip to content

Instantly share code, notes, and snippets.

@shurane
Last active March 16, 2022 01:05
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save shurane/3d5f0c8f90c270afabfcd69301b4100c to your computer and use it in GitHub Desktop.
Save shurane/3d5f0c8f90c270afabfcd69301b4100c to your computer and use it in GitHub Desktop.
[1,1]
[2,2]
[3,3]
[4,4]
[5,5]
const std = @import("std");
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
const file = try std.fs.cwd().openFile("18.3.input", .{ .read = true });
var buffer: [100]u8 = undefined;
var prev: ?*Pair = null;
while (try file.reader().readUntilDelimiterOrEof(&buffer, '\n')) |value| {
var i: usize = 0;
var p = try parse(allocator, value, &i, null);
if (prev != null) {
prev = try addreduce(allocator, prev.?, p);
std.debug.print("addreduce\n", .{});
printPair(prev.?);
} else {
prev = p;
}
}
}
const PairMember = union(enum) { number: u32, pair: *Pair };
const Pair = struct {
parent: ?*Pair,
left: PairMember,
right: PairMember,
};
// TODO option to use an allocaator and concat strings?
// https://www.reddit.com/r/Zig/comments/bfcsul/concatenating_zig_strings/
fn printPairInternal(p: *Pair) void {
std.debug.print("[", .{});
switch (p.left) {
.number => |number| std.debug.print("{d}", .{number}),
.pair => |pair| printPairInternal(pair),
}
std.debug.print(", ", .{});
switch (p.right) {
.number => |number| std.debug.print("{d}", .{number}),
.pair => |pair| printPairInternal(pair),
}
std.debug.print("]", .{});
}
fn printPair(p: *Pair) void {
printPairInternal(p);
std.debug.print("\n", .{});
}
fn parse(alloc: std.mem.Allocator, s: []const u8, i: *usize, parent: ?*Pair) anyerror!*Pair {
var p = try alloc.create(Pair);
p.parent = parent;
i.* += 1;
if (s[i.*] == '[') {
p.left = .{ .pair = try parse(alloc, s, i, p) };
} else {
p.left = .{ .number = try std.fmt.parseInt(u32, s[i.* .. i.* + 1], 10) };
i.* += 1;
}
// skip over comma
i.* += 1;
if (s[i.*] == '[') {
p.right = .{ .pair = try parse(alloc, s, i, p) };
} else {
p.right = .{ .number = try std.fmt.parseInt(u32, s[i.* .. i.* + 1], 10) };
i.* += 1;
}
// skip over closing bracket
i.* += 1;
return p;
}
const activeTag = std.meta.activeTag;
fn tryExplode(p: *Pair, depth: u8, allocator: std.mem.Allocator) anyerror!bool {
if (depth == 4) {
var current: *Pair = p;
while (current.parent) |parent| {
if (activeTag(parent.left) != .pair) break;
if (parent.left.pair != current) break;
current = parent;
}
if (current.parent) |parent| {
switch (parent.left) {
.pair => {
current = parent.left.pair;
while (activeTag(current.right) == .pair) {
current = current.right.pair;
}
current.right.number += p.left.number;
},
.number => parent.left.number += p.left.number,
}
} else {
// no left sibling
}
current = p;
while (current.parent) |parent| {
if (activeTag(parent.right) != .pair) break;
if (parent.right.pair != current) break;
current = parent;
}
if (current.parent) |parent| {
switch (parent.right) {
.pair => {
current = parent.right.pair;
while (activeTag(current.left) == .pair) {
current = current.left.pair;
}
current.left.number += p.right.number;
},
.number => parent.right.number += p.right.number,
}
} else {
// no right sibling
}
if (activeTag(p.parent.?.left) == .pair and
p == p.parent.?.left.pair)
{
p.parent.?.left = .{ .number = 0 };
} else {
p.parent.?.right = .{ .number = 0 };
}
allocator.destroy(p);
return true;
}
switch (p.left) {
.pair => |pair| _ = if (try tryExplode(pair, depth + 1, allocator)) return true,
.number => {},
}
switch (p.right) {
.pair => |pair| _ = if (try tryExplode(pair, depth + 1, allocator)) return true,
.number => {},
}
return false;
}
fn trySplit(p: *Pair, depth: u8) anyerror!bool {
_ = p;
_ = depth;
return false;
}
fn addreduce(alloc: std.mem.Allocator, p1: *Pair, p2: *Pair) !*Pair {
var top = try alloc.create(Pair);
p1.parent = top;
p2.parent = top;
top.parent = null;
top.left = .{ .pair = p1 };
top.right = .{ .pair = p2 };
printPair(top);
while (true) {
if (try tryExplode(top, 0, alloc)) continue;
if (try trySplit(top, 0)) continue;
break;
}
return top;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment