From d9d870306c29428bf123c1caa8a82a9a259b58e6 Mon Sep 17 00:00:00 2001 From: Julien Dessaux Date: Tue, 13 Dec 2022 17:41:44 +0100 Subject: 2022-13 in zig --- 2022/13-distress-signal/example | 23 ++ 2022/13-distress-signal/first.zig | 155 +++++++++++++ 2022/13-distress-signal/input | 449 +++++++++++++++++++++++++++++++++++++ 2022/13-distress-signal/second.zig | 213 ++++++++++++++++++ 4 files changed, 840 insertions(+) create mode 100644 2022/13-distress-signal/example create mode 100644 2022/13-distress-signal/first.zig create mode 100644 2022/13-distress-signal/input create mode 100644 2022/13-distress-signal/second.zig (limited to '2022') diff --git a/2022/13-distress-signal/example b/2022/13-distress-signal/example new file mode 100644 index 0000000..af73fbb --- /dev/null +++ b/2022/13-distress-signal/example @@ -0,0 +1,23 @@ +[1,1,3,1,1] +[1,1,5,1,1] + +[[1],[2,3,4]] +[[1],4] + +[9] +[[8,7,6]] + +[[4,4],4,4] +[[4,4],4,4,4] + +[7,7,7,7] +[7,7,7] + +[] +[3] + +[[[]]] +[[]] + +[1,[2,[3,[4,[5,6,7]]]],8,9] +[1,[2,[3,[4,[5,6,0]]]],8,9] diff --git a/2022/13-distress-signal/first.zig b/2022/13-distress-signal/first.zig new file mode 100644 index 0000000..3559e61 --- /dev/null +++ b/2022/13-distress-signal/first.zig @@ -0,0 +1,155 @@ +const std = @import("std"); + +const example = @embedFile("example"); +const input = @embedFile("input"); + +var allocator: std.mem.Allocator = undefined; + +pub fn main() anyerror!void { + var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator); + defer arena.deinit(); + allocator = arena.allocator(); + + try std.testing.expectEqual(try solve(example), 13); + const result = try solve(input); + try std.io.getStdOut().writer().print("{}\n", .{result}); +} + +const ListErrors = error{ + OutOfMemory, +}; + +const List = struct { + data: std.ArrayList(Elt), + fn init(reader: anytype) !*List { + var l = try allocator.create(List); + l.data = std.ArrayList(Elt).init(allocator); + while (true) { + const c = reader.readByte() catch break; + switch (c) { + '[' => { + var e = try l.data.addOne(); + e.* = Elt{ .list = try List.init(reader) }; + }, + ']' => { + return l; + }, + ',' => { // comma after a list ending, ignore + }, + else => { // a digit + var e = try l.data.addOne(); + e.* = Elt{ .int = c - '0' }; + while (true) { + const d = reader.readByte() catch unreachable; + if (d == ']') { + return l; + } else if (d == ',') { + break; + } + e.int = e.int * 10 + d; + } + }, + } + } + return l; + } + fn initSingleton(n: u8) !*List { + var l = try allocator.create(List); + l.data = std.ArrayList(Elt).init(allocator); + var e = try l.data.addOne(); + e.* = Elt{ .int = n }; + return l; + } + fn isLowerThan(l: *List, o: *List) ListErrors!?bool { + var i: usize = 0; + while (true) : (i += 1) { + if (o.len() <= i) { + if (l.len() <= i) { + return null; + } + return false; + } + if (l.len() <= i) { + return true; + } + const t = try l.data.items[i].isLowerThan(&(o.data.items[i])); + if (t != null) { + return t; + } + } + } + inline fn len(l: *List) usize { + return l.data.items.len; + } + fn print(l: *List) void { + for (l.data.items) |e| { + switch (e) { + Elt.int => |i| std.debug.print("{d} ", .{i}), + Elt.list => |o| { + std.debug.print("[", .{}); + o.print(); + std.debug.print("]", .{}); + }, + } + } + } +}; + +const EltType = enum { + int, + list, +}; + +const Elt = union(EltType) { + int: u8, + list: *List, + fn isLowerThan(e: *Elt, f: *Elt) !?bool { + switch (e.*) { + Elt.int => |i| switch (f.*) { + Elt.int => |j| { + if (i == j) { + return null; + } + return i < j; + }, + Elt.list => |o| { + var l = try List.initSingleton(i); + return l.isLowerThan(o); + }, + }, + Elt.list => |l| switch (f.*) { + Elt.int => |j| { + f.* = Elt{ .list = try List.initSingleton(j) }; + return e.isLowerThan(f); + }, + Elt.list => |o| { + return l.isLowerThan(o); + }, + }, + } + } +}; + +fn solve(puzzle: []const u8) !u64 { + var it = std.mem.tokenize(u8, puzzle, "\n"); + var i: usize = 1; + var tot: usize = 0; + while (it.next()) |line| { + var firstLine = std.io.fixedBufferStream(line); + var first = try List.init(firstLine.reader()); + var secondLine = std.io.fixedBufferStream(it.next() orelse unreachable); + var second = try List.init(secondLine.reader()); + const t = try first.isLowerThan(second); + //first.print(); + //std.debug.print("\n", .{}); + //second.print(); + //std.debug.print("\n{d}: {?}\n", .{ i, t }); + if (t) |s| { + if (s) { + tot += i; + } + } + i += 1; + } + return tot; +} diff --git a/2022/13-distress-signal/input b/2022/13-distress-signal/input new file mode 100644 index 0000000..6d78e26 --- /dev/null +++ b/2022/13-distress-signal/input @@ -0,0 +1,449 @@ +[[[1,[1,6,0,10,10],[],5,[]],[3,[5,8],2,[3,6,5,7],8],4,[0,[10]],8],[7,7],[[3,[9,5,10],[3],8,10],2,3,9],[[8,[3,1,4,9,5]]],[[[],0],10,10,3]] +[[],[[[2,1,2,9],[]],[[1,5,10],3]]] + +[[],[[1,[0,4,7,10,10],3,[6,2,0],[9,1,4]],[],[5,[0,8,5],0,10,[3,10,10]],2,2],[],[[[],10,[]],[3,3,[0,0,2,10],[7,8,6,4,6],6],[10,[8,2,4,2,0]]],[[[9,2,10],[5],1,5,[2,7,9]],[4,[6]],[[]],[4,[],[6,5]]]] +[[6,[]],[[[1],[6,4,1,4],3],[4,4]],[[6,[2,2,9],5,[8,9,7,10]],6],[5,[[10,9,0,5,5],[10,6,6]],[[10,9,6],[0,0,3,1],[],5],7]] + +[[[4,[3,0,5,8,4],[5],7]],[[1,[3,9,10,3],6],7,2]] +[[[]],[],[[[5,7,8,8],[3,1,6,3],[6,7],4],10,8,[5,7,[5,0],9,7],6],[7,[4],7,[8,5],5]] + +[[[],4,6],[0,3,2],[[5,[9,0,10,3,7]],[[5,6,7],[6,0]],9,[9]]] +[[[[7,8,9,3,5],6,[2,6],[6,1,4,10,8]],3],[10],[[]]] + +[[2,8,[[8,3,1,5]],[[8,3],[1],[3],[],[5,8,8,9,4]]],[10],[],[6]] +[[0,[[6],8,4],6,4],[[[10,2],[6,4,4,9],8,[]],[0,5,4,[4,2,0]],1],[[[0,3,8]],8,0],[]] + +[[5],[[],[[9,2,3,5,0],[1,2,7,5],5],0,[[4,8,10],[4,1],[9,1],3,10],3],[]] +[[],[2,[8],[],[2,8,7,[]],[[],[9,10,1,10],[],[]]],[6,[1,[],10,[3,1,5,1,7]],[6,[10,1],[0,10,4],4]],[]] + +[[3,[[9,2,7],3,6,[6,9],[3,8,2,5,2]]],[],[[9,[5,8]],6,5,[[10]]]] +[[2,[1,2],[[6]],[6,8,6]],[[],[2,4,[7]],[0,2,[],[0,7,10,7,7],[10,2,8]],10,[[3],[7,4,8],[7,6]]]] + +[[[[2,9],0,9,4],0,[[5,10],[0],5,[6,3]]]] +[[[9,1,[]],[[7,9,9,5]],[[3,6,0,1]]],[1,3,1],[0,1,[],[[3]]]] + +[[6,6,[[5,8,6],[],[0,7],0]],[8]] +[[0,6,[[0,3]]],[9,[0,7,5,5],[[3,8,2,5],1],4,[10,[4,3],2]],[0],[[6],[1],[6,[],[4,8,6,10,0]]],[2,8,[6,[8],[8,4]]]] + +[[7],[[],2,6],[3],[[5,[5,5,5,7],6],[6],1]] +[[1,[3,[8,4,1,0,1]],6,5],[1,[[7],[8,7,5]],8,[[],5],8],[],[[8,[]],5,4],[8]] + +[[8]] +[[],[],[[[7,3],[9,0,0,2]]],[[9,0,[6,3,2,0,1],5],3],[[],[10,9]]] + +[[[2,[10,10,9,6,7]],[5,1,3,7]],[[10],8,[[1,8,10,8,1],8,[1,2,4,7]]],[]] +[[10],[6,[],6,[[10,1],7,[5,1,0]]],[[0,6,[4,5],[9,0],6],[]]] + +[[[],[],[]],[3]] +[[[[]],10],[[[0,9,8,9,4],[4,1,5,4],[7,6],3],10,2,0],[[0,6]],[9,3]] + +[[],[[[9,4,8,1],0,8,[10,9]],[]],[[1,7,[5,9,3],8,5],3,[[8,9,10,2],7,[0,10,7],[8]],[5,[8,7,0,3,5],0],[9]]] +[[3,7,10,[[9,1,8],[4,5,0],8,[2,7]],10]] + +[[[9,[5,10,3,5,1]],7,9]] +[[9]] + +[[[[7,3,4,9,5],6,[4],4],[9,[9,9,3,4,6],5,8],[[1,6,8],[8,9,0,2],10]],[[],[4,[4,7]],3,[7,[],5,7]]] +[[[[0,7,7]],[[4,6,4],[7],4]],[0],[[],[[4,3,1,10,4],[2,0,9]],0],[[[7,1,5,8,9]],5,7,8]] + +[[7,10,[5,[5,6,7],2,7],5,[[10,9],2]],[],[[8,[2,9,10],[10],[],[]],[]],[0,[9,0],[[],[4,2,10,6,5]],10]] +[[[[3,0,10,3]]],[[6],10,[1,3,[],0],4,7],[4,[],9,[[3,5,4,9,10],[0,8,3,4],[3,9,8,9],[1]],1]] + +[[],[6,[7,5]],[6,6,3]] +[[],[[2,3],5,6],[7,[]]] + +[[[],[1,[2]],4,10,[[],[],0,[3,6,10,4]]],[[1]]] +[[7,[5,3,9,[10]]]] + +[[],[]] +[[[10],8,9,[4,10,[9,6],[1,0,6,7,8]]],[2,0,[1,2,2,2,6],[5,[3,0,9]]]] + +[[4,0,4,2,[]],[0],[8,[8,[1,10],4,1],1,[5,6,2],2],[[5,2],0,3,[[8,4,6,9]]],[[[],9,[],9],[],[[2,5],[5,5,8,4],[4]],7,0]] +[[],[10,[4,5,[3,2,10,0,0],[5,3,6]],1,[2]],[[7,[8,7,3,2]],[5,10,10],[4,[10,7,0,6,10]],8]] + +[[[[8]],3,[[2,1],1,4,8,[8]],8],[]] +[[10,9,[[6,3],[9,7,3],[6,8]],2,[[]]],[[[],9,[1,6,3,10]],3,[1,10],0],[[[0,8,5,2],1,2,[7,4]],5,[0,[8,7,1,1],5,2,[6,1,8]],1,[1,[8],[3]]],[[10,[0,7,8],10,8],7,[[]],0,[]],[5,8,1,[[],9,[],[0]],[]]] + +[[[3,6,[7,10,0,2]]]] +[[9,[[4,6,10]],1,6,[5,[8,5],5,10,10]],[[],9,1,[2,[5,3],2,[6]]],[4],[],[[0]]] + +[[[[7,3,5],[1]],2,[],4],[0],[9,[[4,2,5,9,6],2],[],[5,6]],[2]] +[[3,5,6,[[5],10]],[[2,[8,0,2,5,9],[]],5]] + +[[[3],4],[[[2,1],[2,9,6]],[],0,4],[[[7],[7,3],0,8,9],[[10,9,10,6],[2,0,10,1]],9],[10]] +[[[]],[[],8,[[],[5,0],0,2,[3,7,8]]],[3,0,1,2],[],[10,10]] + +[[[1,8,6,[9,5,6,6,3]],5,[[9,3,3,10],[8,0,1,9],9,[2]],8],[[[4,0,5],[4,10,7,4,0],9],4],[2],[3,[9,[],4],3,[[],0,7,6]],[]] +[[[0,[]],4],[[4,[5,7,10,5,1],5],[[10]]]] + +[[[],[[10,8],[],[8,4]],1,0,[]],[[],[[2,0,8],4,9,7],[10,[0,8,4,9,5]],5]] +[[[10,5,[2,7,8],2],[2],7,[]],[6,2],[3,7,7,[[9,3,5,8,4],[3,0,4],[10,9,4,8,8],[2,4,7],7]],[[]],[1,5,[[10,3,4,1,5],6,[],10]]] + +[[],[[[],[3,3,0],[4,0,5],[5]],[10,8,[2],[10,1,10,3],[10,7]],[[1,5,7,0],[8,5],10,8,[10,4,5,10]]],[7,[2,3,9,9]],[[8,[3,9,6]],[[8,8]],0]] +[[8,[9,8,[6]],[[8,7]],[4,6]],[],[],[[0,3,[7,9,6,9,1]],[[],[7,6,2,2,0]]],[[],[[0,2,2,3,7],8,[3,10]],1,[8,0,[6]],6]] + +[[4,[1,9],0],[8,[2,[],[10,9,6,5],9,7],[[6,2,7,8],10,2,2,[0,10,2]],7]] +[[],[0],[2,[],[6,2,[4,4],[10,10,3,2,10]],10],[8,[],[8,8],9,10],[[[4,9],[8],0,10]]] + +[[[[7],5,[4,2,5,6,6],[3,8,10,10,10],[10,10,9,7,9]],[6,9]],[2,[],[[2,2,9,2,10],[10,9],0,[5,7]]],[[7,2],7],[0,[7],[3,[]],6,3]] +[[5]] + +[[[4,10],5]] +[[],[[[],[1,7,10,1,9],2,0,2],2,0],[[],[[8,2,5,4,9],7,8,3,[2,7]],5,0]] + +[[10],[],[4,7,7,[[8],[1,8,8,6,10],[10,6,6],2],[4,[3,3,2,7,4],8,8,3]],[[9,[7,9,8,4],7],[[9,1,5,9,5]]]] +[[[7],6,[3,6,9]],[10,5]] + +[[[2,[],9,6],4,4],[[[8,2,4],8,[8],[8,4,10]],[[7,6,4,10,9],6,6,3],10,[6,[10,2,3,8,7],4],6],[[],[],[3],[10],5]] +[[4],[[],[[10,9],[0,8,3,5]]],[[[],[2,2,1,10,6]],0,[[1,8]],6],[2,[[10],[6,3],7,[1,3,10]]]] + +[[[],[[7,4,7,7]]],[7],[0,[]],[3]] +[[0,[[6,5],[2],0,[],[5]]],[[1]],[]] + +[[[10,[7,7],[8,1,0,4,5],7],2,[[],[2,2,8,2],[5,0,9],5,[]],6,[[0,8,10],9,[5,5,6,8,0],[9]]]] +[[3,[[],[4,9,4],6,[5,2,8]]]] + +[[[[3,2],2],6,[5,1,6,0],[],4],[[7],4,0,0,[[9,1],6,[8]]],[[6],1],[0,[[4,0]],2],[]] +[[[5,9,5,[],3],[2,6,[0,2,4,4]],0,0,[]],[[[],8]]] + +[[[4,0,1,9],5,5]] +[[2,3],[]] + +[[5,2,[[],[4,2,9,3]],[1,0,5],[7]],[[10,[3],[5],4],0,6,8,3],[9,[8,5],[4],3],[6,[],[8,9,5,[1,9,4,3,4],9],[2,10],8],[[[3,3,8,0]],8,4,[6,[1,5],[],[7,7]],5]] +[[],[8,5,[9,[5,5,7]],[[9,0,3,1],5,8]],[[]]] + +[[],[[[6,2,9]],6],[[],[[]],8],[[[5,1],[0,8],10],[[],0,[4,8],[5],7]],[5,3,[9,[0],[],[3,10,3,6]],[7,3,0],[[1,10,8],7,[0]]]] +[[[],[3,6,4,[10,7,1],9],7,[],[0,[9,2,3],[9]]],[0,[4,4,4,9,2],[[8,5,8,3,10],8,7,5],1,[[6,0],6,0,4]]] + +[] +[[],[1,5,8,10,8]] + +[[8,7],[[9,4],10,5,2],[7,[[]],10,0,[10,4,[],[4,6,8],0]],[[[],[1,10,4,3],[1],10,[7,9,3,9]],[6,[9,8,7,0],6,[5,9,3,5,7],[8,3,4,1]],[10,7,9],9],[6,[[9,8],8,[2,6,4,9]]]] +[[[[1],[6,9,6,4,0]],[5,[4]],9]] + +[[[[10,3,2,9,1],[1],7,2,2]]] +[[5,[[],9,[6,0,9,7,2],1],[]],[[1,2,[6,6],[1,7,1]],7],[[7,[2,5,3]],[0],2],[5,9]] + +[[[7],[6],[3,2],[[3,5,2]],1],[[7],[[5,1,0,2],2,[5,7,2,4]],[[10],8]]] +[[[[],[8,2,7,4,4],[10,8]],[3,[3],[4]]],[[0,[10,5,10,4]],[[],[7,8,10,10,3],6],3],[[[10,4],7,[4,0],[7,8,0,10]],[1],[2,2,3,[5,6,8]]],[8,10,[[3,1,8,8],5,9,1,[10,6]],[[4,7],5,[1,9,10,0,4],2]]] + +[[2,[4],9,[],[4,10]],[],[[[9],[0,0],[1,4,9,7],0],0,[[1,0,2],7,1],4,2]] +[[[6,10],[3,2,[1,1,7],[1],7]],[2],[1],[]] + +[[],[4,[10],[[0,5,8,2,10],[],9,[0,3],[9,1]]],[9,1,8,[[1,10,8,3,4],[6,0,5,7,9],[2,10,3],3],6],[0,[10,[],2],5]] +[[[[10,3,9,2,5],2,[],3],10],[[[7,3,8,9,10],5,6,6,[1]],10,3,4,[[1],10,7]],[[[1,8,4,2,10],6,9,0,[]]],[[5,9]]] + +[[[3,10,3,10]],[[6,7,[2,8,9,6,5]],6],[10],[6,[],[7,[8,9,4,2]]]] +[[[[9,7],[2]],[5],[]],[[[4,7,7],7,0],7,[[8,0],[],[4,5,6,2],[]]]] + +[[]] +[[10,[]],[1],[],[[[8]]]] + +[[[[5,0,4,10,0],5,[],[1]],[],[2],[[2,2,7,1,2],7,1,0,4],[10,[],5]],[[6,[5,9,6,3],3,9,[8,4,1,8]],[[3,3,8,3,0]],[6,[],0,[4,2],[]]]] +[[3],[[4,[8,4,10],7],[6,[5,9,9,2,4],[9,1,7,0],[5,9,5,0]],[4,10,[],[8,8,7]],1,10]] + +[[[1,[8],[2,7,1],9],[],[9,1],[2,10,[8,10,7]],5]] +[[3,[]],[[],[9,9],0,8,[[8,8,1,5,6],[3,8,4,5,4]]],[[4,7,10,[7,2,0,0]],[[9]]]] + +[[3],[4,7],[],[[1],[[4,9,10]],[[]],[],4],[[4,1],0,2,2,[2,[],[8,2,10],[9,0,10,4]]]] +[[5,9,[1,[0,9,10]],[1,9],7],[7,6,[[6,9],0],8],[1],[[6,7,3]],[]] + +[[[8,4,[5,2]],0,[],8],[],[9],[[],[6,1,[3,0,7],1],[[9],7,[7],10]],[]] +[[2,[[1,2,8,8],[]],2,4,6],[[7]],[9,[10,[10,1,3,3,3],[3,10,10],5,7],7],[],[]] + +[[10,1],[10,[[9],[9,1,5,9,5],[7,7,9,0],6]]] +[[[4,[10],1,[0,1]]],[[[7],9],6,9,6,6]] + +[[6,[[],6,[7,8,8]]],[[1,3,[4,8,0,6],[1,10,3,9],10],[6,3],[9]],[],[[],[0,[10,3],[5],[7,5,10,5,2],[]],[4,8,3,[],[0]],[[5],[5,9]],[3,[5,2],[1,4,2]]]] +[[[[1,7],3,0,[]]],[1,6,[5,[10,8,8],[]],[[6,10,2,5,7],6,[7,7,9],[6,4,8,8]],1],[5,[[10,10],3],[[],[2,10]],[1,1,[6,5,7],[10,5,2]],0]] + +[[7,[[7],9,[4,1,3,8],0,4],[1,4,[0,7,6,1,1]]],[0,[2,[3,9,7],10,5],[0,[9,4,2,5,3]]],[0,7],[[7,9,9,3,1],10,[],0]] +[[2,[]],[4,0,5,7]] + +[[[8,7],[4,[7,2,2,8],[8,3,9,9],1,0]],[[[7,4,7,3,10],[1,4,1],[0,10],10,[0]]]] +[[],[],[7]] + +[[1,[[5,7,2],[10],0,[8],[10,9,0,10,8]]]] +[[],[2]] + +[[[10,[9,9,6,3],1,9]],[10,[4,[1,9]],[],[8]],[[3,7,[10,2]],[[],[1,3],2]]] +[[8,6],[[5,0,10,[9]],[[1,5,8,4]],[[1,8,4,6],[4,7,6,2,0],[6,0],[6,3],[6,9,9,10]]]] + +[[10],[8,3,2],[2,[1],[],6,[[6,8],[6,7,5],[9,2,9],7,7]]] +[[[3,[],[10,3,9],4,[5,9,10,3,8]],[2],0,[3],[[3,0],3]],[[7]],[4,[],[],[[9,3,5]],[[]]],[[10],[[6],7],[[1,4],1,[1,1,3],[5,0,4,5,6]],[[4],[7,0,4]],3],[[[],3,[]],8,[9],4]] + +[[[7,[1],[8,4,3,7],3]],[[],[[5,5,3,8,7],[7,5,10,1,1]],8,8],[[2,[7,7,9],10],[4,[4,0,4,2],10,[1,10,9,6]],[[0],0,7],[0,8,[5,0,10,2,3],[7,3,6,5,5]]]] +[[9,[[8,5]],3,7,5],[[1,[],0,1]],[[[10,8],10,[1],[9,9,3,4]]],[8,[[5],2,3,[],[4,0,5]],0,5],[[4,[5,5,0,10],6,10],2,7,[],9]] + +[[[[]],6,[[5,1],8,[4,10],4,[10,5,0,6,5]],1],[[4,[4],6],5,7,[[2],[10,1,4,5,4],2,6,[8]],4],[[],7,[[10],[1,5,9,3,9]]],[[1,[],2],[],0,7,[[7],[7]]],[[],[[9,0]],[0]]] +[[1,9,[],6],[[[9,0,4,3],[8,1,4]],0,[]],[1,[3,[2,4],[]],6,1,3]] + +[[4,8,[1,[7,9,5,8,3]]],[[[6,5],[6,1,5,6,0],7,3],[]]] +[[7,0,7,[],[1,[7,1],10,[7,5,8,6]]],[],[[],4,[1,8],[[7],[5,8,0,4],1,[],9],[[],9,1,7]],[[[7],3,[10,2,2],9]]] + +[[7,[[9,7,9,4,3],6,7],9],[1,0,[[1,2,0,7],[9],8,[10],[5,7]],[7]]] +[[[6,4,9],0,[],6]] + +[[1,[[2,0,2,2],8,5],[],[[4,3],[10],[6],10]],[6,[7,1,[0,2,6,1],9,[0,5]],[[1,5,10,10],[7,8,3,10,3],[],2],7,[9,8,9]],[5,6,[[10,3,2,6,3]]]] +[[5],[[[4],[6,0,4,8]]],[[3,2],[10,[4],[1,8],8],5,1],[]] + +[[10,[[],[4,3,6,2,10]],9],[[2,[5],2,[8,8],[8]],1,[5,4,10,0,[6,2,5]]],[[[3,7,9],[7,5,2,4]]],[10,[7],[3],8,8],[]] +[[4,5]] + +[[1,[[6,5,2,7,0],4],[2,1],9],[],[[[4,3,1,0,1],9,1,6]],[[[6,7,0],1,5],5,7],[4,3]] +[[[1,[3],0],[[5],[10],2,[2,1,3,6]],6,[1,[7],1,[],7]],[[],[[10,4,7,7,5],4,[4,5],[3,6,10,9]],[[2,8,5,7],[8,1,0,9]],[[0,6,8],0,7,5,[4,1]],[3]]] + +[[],[9,4,5,[]],[[],5]] +[[[9,0],10],[],[[10,10,[8,2,7],[4,7,3,10,2]],2,1],[[],7],[9,1,[],[[4,7,2],[4,0],0,2,7]]] + +[[[10,[1],[0,3,5,7,9],1,[1,9,5,9]],[2,[10,4,6]],1],[2]] +[[[7,[9,6,6,7],1],6,10],[5,[7,[9,9,9],8]],[7],[9,8,[[0,5,1],[0,3,2,9]],6],[3,3]] + +[[[[4,2]],[[9,10,9]]],[2,[8,[],7,[10],[]],3,2,6],[[0,8,[6,1,6]],1]] +[[[1,[5,9]],9,5],[[[],6,7,[],1],4,[[5,3],[10,2,7,3,10],[6,1,1],4,[]],2],[],[[7,[0,3,5]],[0]]] + +[[3],[4],[[4,[10],7,[2],9],[1,[5,2,10,3],[9,6,1]]]] +[[],[[[6,9,7,10,8],4,6],[[5,5,9,8,3]],8,10],[6,9],[9]] + +[[6,8,[10,9,8]]] +[[[0,3,[],[4,9,5,5],3]],[],[],[9],[[4,[5,3],[3,5,8]],6,[7,9]]] + +[[3,[[]],[[3,4,2,10,0],10],[3],[[],9]],[1,2,4,9]] +[[[9,[0],8],0,3,10],[[4]],[9,7],[1],[[[0,3,0,0,7],1,[0,7],[4,3]]]] + +[[[[8,6],2,6,4,[8,8]],[[]],[[],4,1],[10,[8,4,1,6,6],[4,9,7,6],9]],[6,10,8],[1,9,[]]] +[[10],[5,4,10,[[],3,4,5]],[[],3],[2,[4,[7,2]],6,10]] + +[[6,9,10,[7]],[[3]]] +[[[[7,7,1]],0,1]] + +[[[1,6,8],7,[[4,6],[8,9,5],[7,7,9],10],1,[7,[7,0,5],5,0,[3,7]]]] +[[[[8,1,7],[8,1],0,[0,6,8],[5]]],[5,[4,10],[1,[5,2,8,4,0]],[[7,10,6],3]],[],[8,[5,[5,4],[3]]]] + +[[9],[[],[[5,4,6]],0],[6,6,6],[[[6],[4,6,5,5],1,0,[5,5,3]],4,4,[[6,8,7,5],[10,8,1,8,6]],[6,[10,0,2,8,9],[10,4],2,[10,5]]],[9,[],1,9]] +[[10,[3,[3,0,8],[10],[5,5,8,1]],[[3,0,5],[8],8,7]],[8],[[[],[7,6]],4],[10],[6,[]]] + +[[[[5,0,2,9],5,[8,8,0]],[8,10,[8,9,4],[8,3,10,9],[6]],5],[[0,10,[10,8,3],8,6],6,[[9,9]],[3,[3,7,10],[8,2]],[[],9,3,[9,0,8]]],[[0],4,[7,9],[[2,10,5,7,5],[8,0,1,5],[6]]]] +[[],[10,[[7],8],4],[0],[[10,5,[0,9,9,4]],[]],[5]] + +[[[0],3,7,7,[1,[0,4,8,9,7]]],[[3]],[7,[7],2,[3,[7,7,0],[6,10,4,7,9],[8,10,2,8,2],[9]]]] +[[5],[9,[6,[]]],[[5,2,[],9]],[[]]] + +[[],[[[0,0,6,9],[6,3,2],5],[5,[2]],7],[[[5,2,4],[2,8],[4]],[5,[]]],[],[]] +[[[5,1,[6]],[[3,7],6,[6,6,8,3],[],10]],[],[[],1,[9,[7,2,10,2,9],7]],[6,[1,[0,10,10,1],2,7,[]],[[],1,5],[[7,3,1],[2,8,10,9],[9,5],4]],[[],9]] + +[[[3,6,10],[[10,4,4],[9,0],10,[]],[9,[],[5,4,3,6,6]],6],[],[],[4,3,4,10],[[[10]],0]] +[[[[3,0],[6,2,8]],[[3],5,[],[10,8,7,6]],[9,6]],[]] + +[[[],[6,7,6]],[1,[[],[8,1],[],[6]],9,[[5,0]],[2,9,8,5]],[5,[[10,4,4]],10,8]] +[[[[7,10,8],[8,6],6],2,[7,[2,8],1]],[[7,3,9,9,[6,4,8]]],[[4,1,[0]],4,7,[[10,2]]]] + +[[[9,[10]],5,[[0,9,3,0,6],6,1,[0,10,2],4],4],[4,[[1,5,8,5]],3,6,[6,[8],[6,1,3],[2,2,0]]],[]] +[[],[4,1,[8,2,6],7]] + +[[[9,[5,0,2,9],[5,9,3,7]],4]] +[[],[[3],2,3]] + +[[5,5]] +[[],[7,0,10],[[]],[]] + +[[],[],[[8,9,8,3,[4,5,2]],[[3,3,1],[],[6,9,1]],[4,9,[8,10,10,1],7],0,1],[]] +[[[9,6,5,10,1],8,9,[[7,10,3,9,5],10],2],[4,[],8]] + +[[[[6,0,7,9,5]]],[[[4,4,3]],7],[[[7,0,2,9],[]],[5,[],9],4,[[8,8,9],[],2,[8,4,2,9,0],[4]],1],[8,6,6,[]],[[1,0],[],3,[6,[1,9],[6],[5,6]]]] +[[],[[[10,10],[]]],[]] + +[[[2,[6,4,8],10,[6,6,3,9],4],[0,9,1,[]],[[],[3],9,5]],[[[6,7,8],[4,0],[9,5],[0],[3,10,3]],9],[],[],[[[4]],3,[[1,4,2,8],[5],5,[5,7,7,6],3]]] +[[10,7],[]] + +[[7,2,2],[],[[],1,5,[5,9,[1],1,4]]] +[[4,5,[[9,10,0],6,7],3,6]] + +[[],[5,[[4,10,4,5,2],[3,7,7,1,5],[7,4,1,5]],[[3,3],10,1,10]],[[],[[4,10]],9,10,10]] +[[],[5,[[1,4],[5,4,6,5,0],[10,10],0,[3]],[6,3,3,[0,3,5,0]],[[3,8,10,2],[4,4,2,2],4,[6],8]],[[[6,2],9],7,3],[10],[[],0,1]] + +[[3,10,[],6],[[[]],6],[]] +[[[],6],[[],0],[[8],[[5,5],[],[8,4,7,6],[7]],[],1,[9,5]]] + +[[],[7],[6,[3,2],0],[[[7,1,7],[6,5,1,8,8],[9,3,6,4,2]],[2,4]]] +[[9,[[7],0,[]],[9,[10]]],[10,0,[9,[1,1,5],[6,7]]],[1,9,2,[[5,3,1],9,0,5]]] + +[[4]] +[[[[7,6],[10,7,5,2,0]],8,2,7],[3,[0],[7,0,[2,9],4]],[[3,8,2,4,[]],[[],[8,4,7],[2,9,8]],[[9,2]]],[5,[10],[[],[4,2,3],3,[1,7,5],[1]]]] + +[[[[4,2,6],6,[9,6]]],[9,7,[[4,9,5],[10,1,8,7],6,3,1],[2,[4,6],1,8],1]] +[[[[8,1,1,6,7],[7,6,5],[6,8],[],[1,5,0,2]]]] + +[[[[1,2,5,7],[],[7,2,3],10,8],4,10,4,10],[3,[6,[6,1],[3,7,0,7,0],10],[7],7]] +[[1],[[[1,9,4,8],[0],[10,5,8],[10,8]]],[3,7,5,[[1,2,9,1,7],[7,10,5,8,6],[0,3]],3]] + +[[10,0]] +[[],[0,[1,[]],4],[8]] + +[[],[[[10,3,2]],2,[[10,5,2,1]],[2,[]],[[1,9,4]]]] +[[[[4,9,2]],1,0,9,5],[[[0,5,10,1],[6,7],4,[1,6,4],[3,7]],[[0,10],2,5,9]]] + +[[2,[10],7],[10,[[3,2],[7]],[7,[6,9,9,4],3,[7,1,2]]]] +[[[[9,6,4],8,[6,0,6,10],[7,1,0]]],[],[8,[9,[6,0,4,8],8,3],[],[1,[4,7,2,4]],0],[[[6,1,5],5],5,1],[4]] + +[[[],[[],[]],[8,[5,2,7,7,8],[1,6,4,3,1],[0,10]]],[[[6,7,4]],3,[[],[6],[2,7,4,9]]]] +[[[[7,4,7]]]] + +[[[[3,9,1,3,8],10,[2,6,8,2]],[],1],[1,2],[8,2],[]] +[[0,[6],[[6,9,8],5,4]],[[0],[],6,[6,[6,3,2]],3],[7,[[]]]] + +[[9,10],[1,6],[]] +[[3],[6,1],[[[3,8]],2,[[],[3,9,8,0,2]],[]],[[1,3],4,[6]],[6]] + +[[2,[3,5,1,5,[1,8,2]]],[5,5,[[8,4,8],10,[10,4],6]],[[[10,9],[3,9,8,2,8],[]],8]] +[[[5],6,[2],9],[10]] + +[[2,[0,[6],6,3,[8,4,10]],[[9],7,[3,10,1],[10,5],9],4]] +[[[[9,10,5,6]]],[[2,9],[10,8]]] + +[[3,[[6,1,0,2],[9],2,3],[5,[6,3,0,10],1]],[]] +[[10,9,[],[]],[[6]],[0],[10,[10,6,5,[1]],[[3,10,0,8,1]]]] + +[[7,[[4],2,5],2],[[1,3,[7,4,4,9,5]]],[3,2,[[],1,2,[4],[6,4]],[]]] +[[],[[[]],3,[7,2,[]]]] + +[[1,[[6,9]],5,[[9,5,5,5],9,8,8],[3,2,5,[4,0,4],3]],[4,7],[[[4,2,7,3],[5,1],[10,4]],[[2,9,2],[7,8,1],[10,4,2,3,6],[],5],[10,9,[]]],[9]] +[[[5,10,[6,5,9,3,3],8]],[],[[7,[4],1,0,[9,4,8]],[[10,1],2,3,6],8,3]] + +[[8,4,3,8,[1,0]],[5,[7,[],7]],[10,[[6,2,4],[7,3,7,5],[],[],1],6,2],[[],[[0,9,6],[],8]],[9,[],10]] +[[[[10,8,5,0]],[]],[7],[[1,[2],[8,0,0]],[[2],[],[2,1,1,0,8]],3,[[10,4]],7],[10,[1,[4,5,7],10,5,[8,5,2,10]],1,9]] + +[[1],[0,1,[2,7],[[10],1,[]],[[3,3,4,2,5],4,[],[6,3,1,10],3]],[[3,[9,9,9,1],[8,9,0],0],3,3],[10],[[9,[9,1,6,7],7]]] +[[1,4,[],5],[4,[2,8,6,[3,5,6,4]],3,4,[[],2,[]]],[[[7,1,0,1],[6,10,9,8,3]],[[10,10],6,[]],0],[]] + +[[2,10]] +[[[0],0,[[1,0],[5,5,9]]]] + +[[5,[[3],10,[9,9],[6,4],[]],[5,3,9,[5,0,10,4],9]],[[[0,1,1,8,5]]],[[],[[2,9,7,2],3,1,[6,3]],8,[]],[],[9,9,[[4,0,4],[],3,1]]] +[[],[8,9],[[],9,3,5],[[9,1,[1,4]],[[2],[6,8],[4]],[[],4,[]],8,4]] + +[[0],[4]] +[[[4,7,1,6]],[[10,3,3,3]]] + +[[[[2,9,9,7],1],[1,3,[1,9,8,9,8],10],3,3,5]] +[[[1,6,[3,7,3,0,4],10,[5,2,7]],[[6,5,10,8,6],[8,3,10,5,10],[9,3,5],2,4],10,[7,6]],[1],[[[4,9,3],6,2,[5,4,4,1],2],[[0,3]],9]] + +[[8,[],2]] +[[3,[5,2,[5,1],[8,4,4],10],6,[[1,4],[]],8],[6,10],[[1,4,[5],2,0],4,[[],3],[5,6],2]] + +[[1,9],[]] +[[2,[0,3,8,2]]] + +[[[6,5,7],[2,6]],[10,7,[6,9,6,[3,8,2],[]],1,10],[[[5,2,6,5],4,[]],[6,0,6],1,[]],[5],[[6,3,[7,7,3,2,0]],[[],[7,1,3,5]],[]]] +[[4,[[3,6,9,8,4],0,8,[10,0]],6,0],[3,1,[[7]],[6,8,8,1,4],2],[8,[6,[1],4,0,[8,3,8]],[3]],[[[7,5,3,10]],6,2],[2,[0,[]],5,[4,7]]] + +[[5,0,1,[9,[],[1,10,6,6],[]]],[],[[1],8],[[2,[1,9,1,3]]],[[[],[],7,9,[]]]] +[[],[],[4,2,[[],[3],[3,2,8],0],[[10],[0,7,5,0],[10,8],0,[]],[[],6,2]],[[[5,8,1],[2]],[8],6,[1]]] + +[6,0,1,5,5] +[6,0,1,5] + +[[[4],[],4],[2,[[],[0,5],7,[4,4]],[[9,6],5]],[],[[],2,[],7]] +[[[7,[9,8,8,3]],[],[],6],[9,[[2,0],[7,0],2],5,[[]],[[3,3,6],6,[1,6,1],[10,4]]],[8,[9],4],[[[],[10,0,5],8]]] + +[[[[9,10,2],3,5,[9,8,8,9],4]],[6,[]],[[],[4,10,2,6,[2]],6],[4,6,5,[[],[],3,9,[4,0,2]],5]] +[[5,[[],[1,4,2,4],1]],[2],[7,[8,4,4]]] + +[1,9,4,8] +[1,9,4,8,5] + +[[[[],8,[7,9],4],10,[4,[10,8,4,0]],[3,[10,7],1,[]],[[8,6,8,7,8],2,9]],[]] +[[6,0],[10,10,6,[2,[],[8,1,6,4]]]] + +[[8,6],[[[]]]] +[[5,6]] + +[[],[],[[7],[8],[0,8,0,5],9,2],[1,3,3,[7,8],[4,0,[6,3,9,1],[3,8,4,2,5],[9,5]]],[10,[[0,9,0],[7,9]],9,3]] +[[],[[7,7,[2]],[[6,5,10,7],[8,4,9,0,4],6],[2,9,[4,8],10,5],[2,[7,10,0,1],[3,7]]],[[[5,4,0],[6,5],7,0,[2,6,5]],4,1,[4,10,1,2]],[[3]]] + +[[9,[],3],[10,[4,9,10,0]],[[],5,[[8,0,7,9],6,3],[[10,4],[8,6,0,7],3,2]],[2],[[5]]] +[[[[4],9,[0,7,4,10]],8,[5,8,6,0]],[6],[5,[[],[7,0,5,5],0,[]]],[1,[1,[7,1,10,0,8],2],[2,[9,2,2,8],1,10,[6,9,3]]]] + +[[[],4,[10],[5,[1,0,9],2]],[[6,[4],2,4,10],6,[5],[2,7,[7,6,3,4]]],[[7,1,[5]],10,[1,[0],[],[8,9,9,7],7]],[6,[8],1,3,10],[10,[9]]] +[[1,1,0,0],[1,[[3,10,6,9,10]],[[3,0,6,4,9],0,2]]] + +[[10,[7],5,[],6],[[7,[3,10,9,1],[8],[],[1,0]],[5,8]],[7,[[4,4,0]],10,[3,[9,3,5,2,0],9]]] +[[5,[[4,8]],9,[0,[7,7,8,0,3],4,10],[10,[5,1,7,7,10]]],[],[6,5],[[],7,1,[[],[0,8,1],10],[]],[[],[],[3,10,[2,9,10,4,10],4],10,[10,[10,10,6,8,5],[5],6]]] + +[[[],2,[10,[6,3,10,7],[]],[]],[],[[4,7,[],7,[]],[[1],10,[8,0],10,2],[[8,0,3,3,4],[7,2,3],[3,8,6,9],9],[],[6,8,0,[7]]],[10],[[[8,0,4,6],3,[]],0,6,[[6],5,7,9],[[4,0,7,5]]]] +[[1,[[0],[],[],5],8,6],[0,[2,6,2,[9],6],2],[[[0,4,5,5,4]],[4,5,1,6],3]] + +[[[[5,4,0,9,10],[0,0,7,8,5],[4,6,7],8,5],[[5,2,0,7,3],5,[],[0,0]],[1,3,1,[2],[]],8]] +[[[1,[9,4,4],[8,1,5]],[[5,2],4,10,3,10]],[[[9,6,8]]],[[4,[6,0,2,9,8],[],[10,10,9,2,2],0]],[10,0,[]]] + +[[],[[7,[10,9,10],4],[2,2,[1,0]]],[[2,[3,8,5,9,3]],[[3,2,9],[],5,8],[],[[10,2],0,[]],[[10,6,0],5]],[3,[],[],[2,5,[4,8,1,7],4],[]],[8,1,[[3,4,6,7,1],7]]] +[[1],[[[4,7,9,10],3,[5,9,7,9,10]]]] + +[[1,10,[7,[],[7,6,3],10,9],[[0,10,0]],[4,6,[3]]],[[[6,2,6,3],10,[3,0,7,4]],5,10,6,[[5],6,[],9,[8,2,10,0]]],[],[[[0,8],10],8,[[1,8,1,3,6],2,[6],[7,0]],1]] +[[[3],3,[8,7,[10,8,4,3,6],2],[6,2],5]] + +[[[[1,0,4,3],[9],[1],2]],[[8,9,0],[],10,8,[[5,5,6,5],6]],[[[9],0,10],1,[2,8]],[9]] +[[[2],7,0,1,5],[[[1,6,4,3,4],6,1],[],5,[],[[7,4],[4,1,8,7,0],[],6]],[0,[0,[9],[9]],[10,1,7,[]],2,[[6,5,9,1],[3],5,[5],4]],[8,10,[[10,5,4],0],[5,[10],10,[1]]],[]] + +[[],[2],[1],[9,[[1,2,7]]],[[[1,1],[2],10,[7,1,0]],6]] +[[4,[[9,8]],[[9,3],1,[6]]],[[[4,2,5],[],[],2,6],3],[[[1,0,5,6],[2,6,10,5,9],[1,4,3,0,2],[10,2,9]],[5,2,7,[10,10,9,4,3]],[[3,5,8,9],[10,1,3,10],[],[2,8,1,8]],3,[]],[0,[],[[2,4],[8],[],[5,7,1,1]]],[[[],9,1,7],7]] + +[[4,0,[1,10,[],0,[]],8,0],[],[],[4]] +[[4,[9],2],[9],[3]] + +[[[[6,0,4,2,0],9,[7,8],8]],[],[[2,7],1,4]] +[[],[[]],[],[[[9,7],4,[0],[3,10,10,8,4]],6,5]] + +[[[7]],[],[],[[],[7]],[7,[3,6,3],1]] +[[[8],[7],[3],[[3,2,4,9]],4],[[5,0,[3],[6]]],[[[9,9],[10,1,0,6,3],2]],[0,[2,8,[4,4],2],2]] + +[[],[[[4,3,0,2],[2,4,10,5,3],[]],[[5,9],7,[4,6]],[[6,6],[6,9,2,4],[9,8,9],8]],[[],2,8,8]] +[[[5,9,10],[4,[10]],[[],[9],[]],[4,2,6],2],[[4,[7,3,1,9,3],[3,1,6,5],8]]] + +[[[[4,0],10,3],[[6],[],10],10,6],[8,7]] +[[],[],[10,2,0],[[[3,8,7],[2,0]]],[3,5,5,1]] + +[[[[8,7],4,6,[10,7,9],[1,2]],3,[[5,5,5],4,[0],0]],[6,[[2,0,2,10,2],9],[8,0,[5,5,1,7,6],[2,5,2],[]]],[[[4,5,5],2,5,[4,8]]],[10,4],[[3,[],1,3],[],[3,[9,7,0,1]]]] +[[[[9,9],9,6,8],3,[[],[],[10,8,6,7,6]],2],[[[0,5],4,7,[8,7,10],2],[[9,1],9,[4,9],6],2,5,[4,[7,6,6,4],3,8]],[[],[3,[7,7],1],10]] + +[[9,[0,3,[0,6,9]],[[7,1],[4,4,3,1,9],10],1,3]] +[[8,7,8],[8,4,[]],[[[1],[4,9],[3]],6,8,[4,[6,3],[7],[1,0,10,7],10]],[2,2,0]] + +[[2,10,2],[],[[[2,6,8,7],2],[7,[]]],[7,[[4]],9],[1,[3,[10,2]]]] +[[[],[]],[[3,5],[],10],[]] + +[[2,6,6]] +[[8],[[4],[0,3,[]],[[8,6,0]],[10,10,8,1]],[[0,7],2,[0,10,[7,7,0,7,5],2],7],[[[2,5,7],6,4,10,2],7],[9]] + +[[[9,[7,3],[9,7],1]],[[7,[6,4],1],[0],7,[]],[5,7,[[9,10,10],[10,2]]]] +[[8,[]],[[],[7,10,5,3,[5,8]],[],[[],4,2,8,[2,7,5,7,0]],[1,[9]]],[4,1,2,4,5]] + +[[3,4,[]],[],[3,8,5,[4]]] +[[[5]],[],[],[[[3]],[[3,3,2,9,10],[0,6,5,7],9,2]]] + +[[],[6,[10]],[[5,8,[5,7,4]],5,5],[1,[4,4,[],3,[4,1]],[[5,1,2,7],[10,6],2],[[7],0,0,[7],[1,4]],[8]]] +[[[[6,10,2],[],6,[5,1,1,1,1]],[8,2,[6,7],10,5],3],[6,[5,[9,4,3]]],[[[2,6,10],[0],9,9,[3]],9,5],[9,[9],[[4,4,10],10,6,[],[0,7]],[4,[8,1,9,5],[4]],[[0,3,7,7],[0,9,10,10]]]] + +[[[],5,[3,[],9,[8,10]],2,6],[1,[6,[],6,[10,7,7,6],[3,7]],5],[7,10,[[8],[9,6],[],3,5],[[],4,2,8]],[[8,[]]],[8]] +[[9,4],[10,5],[[6,10,[0,1,1],0],7,4],[2,3,[7,8,1,1],6]] + +[[],[[1,[2,1],5,[],9],6,[9,4,8],[[5,1,7],[10,1,8],0]],[8,1,[[],2,[2,8]]],[[3,[2,3,0],8,6,[]],[8,4,[8],[10,7,2,2,0]],9,1,[1,[0,8,7,1],2]],[[9,5],[[1,2],[],10,7],2]] +[[[10],6,7,4],[],[7,[0,9],[1,10,[0,10]],[[3,10],5,[9,9,8]]]] + +[[[5,[0,8,0]],[[6,3,2,3,5],[8,4]],1],[[[6,6,6,2],1,[2,2],2],9,6,2],[]] +[[[],[],[[4,5],0],[10,6,7]],[[8,[9,8]]],[[[],[],3,7],[],0]] + +[[],[7,4],[[5],5],[[],1,10,[0,[5,0,1,10,6],[8],1,[4]],0],[0]] +[[],[1,0,10],[]] + +[[3,2,[[7,9,4,8,2],2,[1,0,9,6],10,[3,0]]],[[9,6],[[]],1,[[],5,[5,4]],[2]],[],[8,[[6],2]],[[]]] +[[0,[1],[],[[2]]],[[5,[1,0]],[[],2]],[4,[10,2,5],[[6,7,2,10,1],1,0,1]],[]] + +[[0,[],[[5,3,5,3,0],[],[3,8,0,0,1],[2]]],[]] +[[[7,2],6,[8],[],[]]] + +[[[10],0,0,[[0,9]]],[[0,4],[[2,9,1,3]],9],[2,[[]],[7,[0,8],8]],[6,[[6,9],10,[],[4,2],[0]]]] +[[8,[0,9]],[[2,6,8,[5],[8,1,1,9,4]],1,4],[[1,5],2]] + +[[[10,[],9,7,6]],[1],[],[[8],10,[9],[]]] +[[[[9,7,7,7,0],[0,3,9,9,2],5],8,0,0],[],[[3,2,2,[2]],[2,[]],7],[[9,[7,8,9,9,10],[8,10]],6,10,[[]]],[]] diff --git a/2022/13-distress-signal/second.zig b/2022/13-distress-signal/second.zig new file mode 100644 index 0000000..e323138 --- /dev/null +++ b/2022/13-distress-signal/second.zig @@ -0,0 +1,213 @@ +const std = @import("std"); + +const example = @embedFile("example"); +const input = @embedFile("input"); + +var allocator: std.mem.Allocator = undefined; + +pub fn main() anyerror!void { + var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator); + defer arena.deinit(); + allocator = arena.allocator(); + + try std.testing.expectEqual(try solve(example), 140); + const result = try solve(input); + try std.io.getStdOut().writer().print("{}\n", .{result}); +} + +const ListErrors = error{ + OutOfMemory, +}; + +const List = struct { + data: std.ArrayList(Elt), + fn addOne(l: *List) !*Elt { + return try l.data.addOne(); + } + fn init(reader: anytype) !*List { + var l = try allocator.create(List); + l.data = std.ArrayList(Elt).init(allocator); + while (true) { + const c = reader.readByte() catch break; + switch (c) { + '[' => { + var e = try l.data.addOne(); + e.* = Elt{ .list = try List.init(reader) }; + }, + ']' => { + return l; + }, + ',' => { // comma after a list ending, ignore + }, + else => { // a digit + var e = try l.data.addOne(); + e.* = Elt{ .int = c - '0' }; + while (true) { + const d = reader.readByte() catch unreachable; + if (d == ']') { + return l; + } else if (d == ',') { + break; + } + e.int = e.int * 10 + d; + } + }, + } + } + return l; + } + fn initEmpty() !*List { + var l = try allocator.create(List); + l.data = std.ArrayList(Elt).init(allocator); + return l; + } + fn initSingleton(n: u8) !*List { + var l = try allocator.create(List); + l.data = std.ArrayList(Elt).init(allocator); + var e = try l.data.addOne(); + e.* = Elt{ .int = n }; + return l; + } + fn isLowerThan(l: *List, o: *List) ListErrors!?bool { + var i: usize = 0; + while (true) : (i += 1) { + if (o.len() <= i) { + if (l.len() <= i) { + return null; + } + return false; + } + if (l.len() <= i) { + return true; + } + const t = try l.data.items[i].isLowerThan(&(o.data.items[i])); + if (t != null) { + return t; + } + } + } + inline fn len(l: *List) usize { + return l.data.items.len; + } + fn print(l: *List) void { + for (l.data.items) |e| { + switch (e) { + Elt.int => |i| std.debug.print("{d} ", .{i}), + Elt.list => |o| { + std.debug.print("[", .{}); + o.print(); + std.debug.print("]", .{}); + }, + } + } + } +}; + +const EltType = enum { + int, + list, +}; + +const Elt = union(EltType) { + int: u8, + list: *List, + fn isLowerThan(e: *Elt, f: *Elt) !?bool { + switch (e.*) { + Elt.int => |i| switch (f.*) { + Elt.int => |j| { + if (i == j) { + return null; + } + return i < j; + }, + Elt.list => |o| { + var l = try List.initSingleton(i); + return l.isLowerThan(o); + }, + }, + Elt.list => |l| switch (f.*) { + Elt.int => |j| { + var ll = Elt{ .list = try List.initSingleton(j) }; + return e.isLowerThan(&ll); + }, + Elt.list => |o| { + return l.isLowerThan(o); + }, + }, + } + } +}; + +fn lesserThan(context: void, a: *Elt, b: *Elt) bool { + _ = context; + var tt = a.isLowerThan(b) catch unreachable; + if (tt) |t| { + if (t) { + return true; + } + } + return false; +} + +fn solve(puzzle: []const u8) !u64 { + var it = std.mem.tokenize(u8, puzzle, "\n"); + var list = std.ArrayList(*Elt).init(allocator); + var divider2Line = std.io.fixedBufferStream("[[2]]"); + var div2 = try list.addOne(); + div2.* = try allocator.create(Elt); + div2.*.* = Elt{ .list = try List.init(divider2Line.reader()) }; + var divider6Line = std.io.fixedBufferStream("[[6]]"); + var div6 = try list.addOne(); + div6.* = try allocator.create(Elt); + div6.*.* = Elt{ .list = try List.init(divider6Line.reader()) }; + // process input + while (it.next()) |line| { + var bs = std.io.fixedBufferStream(line); + var elt = try list.addOne(); + elt.* = try allocator.create(Elt); + elt.*.* = Elt{ .list = try List.init(bs.reader()) }; + } + // sort the list + std.sort.sort(*Elt, list.items, {}, lesserThan); + //for (list.items) |l| { + // l.list.print(); + // std.debug.print("\n", .{}); + //} + // compute output + var ret: usize = 1; + for (list.items) |l, i| { + switch (l.*) { + Elt.int => {}, + Elt.list => |ll| { + if (ll.len() != 1) { + continue; + } + switch (ll.data.items[0]) { + Elt.int => {}, + Elt.list => |lll| { + if (lll.len() != 1) { + continue; + } + switch (lll.data.items[0]) { + Elt.int => {}, + Elt.list => |llll| { + if (llll.len() != 1) { + continue; + } + switch (llll.data.items[0]) { + Elt.int => |n| { + if (n == 2 or n == 6) { + ret *= (i + 1); + } + }, + Elt.list => {}, + } + }, + } + }, + } + }, + } + } + return ret; +} -- cgit v1.2.3