aboutsummaryrefslogtreecommitdiff
path: root/2022
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--2022/09-rope-bridge/example8
-rw-r--r--2022/09-rope-bridge/example28
-rw-r--r--2022/09-rope-bridge/first.zig222
-rw-r--r--2022/09-rope-bridge/input2000
-rw-r--r--2022/09-rope-bridge/second.zig247
5 files changed, 2485 insertions, 0 deletions
diff --git a/2022/09-rope-bridge/example b/2022/09-rope-bridge/example
new file mode 100644
index 0000000..9874df2
--- /dev/null
+++ b/2022/09-rope-bridge/example
@@ -0,0 +1,8 @@
+R 4
+U 4
+L 3
+D 1
+R 4
+D 1
+L 5
+R 2
diff --git a/2022/09-rope-bridge/example2 b/2022/09-rope-bridge/example2
new file mode 100644
index 0000000..60bd43b
--- /dev/null
+++ b/2022/09-rope-bridge/example2
@@ -0,0 +1,8 @@
+R 5
+U 8
+L 8
+D 3
+R 17
+D 10
+L 25
+U 20
diff --git a/2022/09-rope-bridge/first.zig b/2022/09-rope-bridge/first.zig
new file mode 100644
index 0000000..9229f5d
--- /dev/null
+++ b/2022/09-rope-bridge/first.zig
@@ -0,0 +1,222 @@
+const std = @import("std");
+
+const example = @embedFile("example");
+const input = @embedFile("input");
+
+pub fn main() anyerror!void {
+ var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
+ defer arena.deinit();
+ const allocator = arena.allocator();
+
+ try std.testing.expectEqual(try solve(example, allocator), 13);
+ const result = try solve(input, allocator);
+ try std.io.getStdOut().writer().print("{}\n", .{result});
+}
+
+const Line = struct {
+ data: std.ArrayList(bool),
+ x: i64,
+ fn init(allocator: std.mem.Allocator) !*Line {
+ var l = try allocator.create(Line);
+ l.data = std.ArrayList(bool).init(allocator);
+ return l;
+ }
+ inline fn len(l: Line) usize {
+ return l.data.items.len;
+ }
+ fn set(l: *Line, x: i64) !void {
+ if (l.len() == 0) { // this is en empty line
+ l.x = x;
+ try l.data.append(true);
+ return;
+ }
+ const lx = @intCast(i64, l.len());
+ if (x >= l.x) {
+ if (x < l.x + lx) { // just set the value
+ l.data.items[@intCast(usize, x - l.x)] = true;
+ } else { // we need to add trailing spaces
+ var i: usize = l.len();
+ while (i < x - l.x) : (i += 1) {
+ try l.data.append(false);
+ }
+ try l.data.append(true);
+ }
+ } else { // we need to shift right and add leading spaces
+ const oldLen = l.len();
+ l.data.items.len += @intCast(usize, l.x - x);
+ try l.data.ensureUnusedCapacity(l.len());
+ std.mem.copyBackwards(bool, l.data.items[@intCast(usize, l.x - x)..], l.data.items[0..oldLen]);
+ l.data.items[0] = true;
+ var i: usize = 1;
+ while (i < @intCast(usize, l.x - x)) : (i += 1) {
+ l.data.items[i] = false;
+ }
+ l.x = x;
+ }
+ }
+ pub fn visited(l: Line) u64 {
+ var tot: u64 = 0;
+ var i: usize = 0;
+ while (i < l.len()) : (i += 1) {
+ if (l.data.items[i]) {
+ tot += 1;
+ }
+ }
+ return tot;
+ }
+};
+
+pub const Field = struct {
+ allocator: std.mem.Allocator,
+ x: i64 = 0,
+ y: i64 = 0,
+ lines: std.ArrayList(*Line),
+ lx: usize = 0,
+ fn init(allocator: std.mem.Allocator) !*Field {
+ var f = try allocator.create(Field);
+ f.allocator = allocator;
+ f.x = undefined;
+ f.y = 0;
+ f.lines = std.ArrayList(*Line).init(allocator);
+ var l = try f.lines.addOne();
+ l.* = try Line.init(allocator);
+ f.lx = 0;
+ return f;
+ }
+ inline fn len(f: Field) usize {
+ return f.lines.items.len;
+ }
+ pub fn set(f: *Field, x: i64, y: i64) !void {
+ if (y >= f.y) {
+ if (y < f.y + @intCast(i64, f.lines.items.len)) { // the line exists
+ try f.lines.items[@intCast(usize, y - f.y)].set(x);
+ } else { // append lines
+ var i: usize = f.lines.items.len;
+ while (i < y - f.y) : (i += 1) {
+ try f.lines.append(try Line.init(f.allocator));
+ }
+ var l = try Line.init(f.allocator);
+ try l.set(x);
+ try f.lines.append(l);
+ }
+ } else { // preprend lines
+ const oldLen = f.lines.items.len;
+ f.lines.items.len += @intCast(usize, f.y - y);
+ try f.lines.ensureUnusedCapacity(f.lines.items.len);
+ std.mem.copyBackwards(*Line, f.lines.items[@intCast(usize, f.y - y)..], f.lines.items[0..oldLen]);
+ var l = try Line.init(f.allocator);
+ try l.set(x);
+ f.lines.items[0] = l;
+ var i: usize = 1;
+ while (i < @intCast(usize, f.y - y)) : (i += 1) {
+ f.lines.items[i] = try Line.init(f.allocator);
+ }
+ f.y = y;
+ }
+ if (x < f.x or x >= f.x + @intCast(i64, f.lx)) { // recalculate boundaries
+ f.x = std.math.maxInt(i64);
+ var x2: i64 = std.math.minInt(i64);
+ for (f.lines.items) |line| {
+ if (line.len() == 0) continue;
+ if (f.x > line.x) f.x = line.x;
+ if (x2 < line.x + @intCast(i64, line.len())) x2 = line.x + @intCast(i64, line.len());
+ }
+ f.lx = @intCast(usize, x2 - f.x);
+ }
+ return;
+ }
+ pub fn visited(f: Field) u64 {
+ var tot: u64 = 0;
+ var i: usize = 0;
+ while (i < f.len()) : (i += 1) {
+ tot += f.lines.items[i].visited();
+ }
+ return tot;
+ }
+};
+
+const Rope = struct {
+ hx: i64 = 0,
+ hy: i64 = 0,
+ tx: i64 = 0,
+ ty: i64 = 0,
+ fn step(r: *Rope, direction: u8) void {
+ switch (direction) {
+ 'D' => {
+ r.hy += 1;
+ },
+ 'L' => {
+ r.hx -= 1;
+ },
+ 'R' => {
+ r.hx += 1;
+ },
+ 'U' => {
+ r.hy -= 1;
+ },
+ else => unreachable,
+ }
+ if (r.tx == r.hx) { // same line
+ if (r.ty + 2 == r.hy) { // to the left
+ r.ty += 1;
+ } else if (r.ty - 2 == r.hy) { // to the right
+ r.ty -= 1;
+ }
+ } else if (r.ty == r.hy) {
+ if (r.tx + 2 == r.hx) { // to the top
+ r.tx += 1;
+ } else if (r.tx - 2 == r.hx) { // to the bottom
+ r.tx -= 1;
+ }
+ } else if (r.tx + 1 == r.hx) { // on the left by one
+ if (r.ty + 2 == r.hy) { // above by two
+ r.tx += 1;
+ r.ty += 1;
+ } else if (r.ty - 2 == r.hy) { // bellow by two
+ r.tx += 1;
+ r.ty -= 1;
+ }
+ } else if (r.tx - 1 == r.hx) { // on the right by one
+ if (r.ty + 2 == r.hy) { // above by two
+ r.tx -= 1;
+ r.ty += 1;
+ } else if (r.ty - 2 == r.hy) { // bellow by two
+ r.tx -= 1;
+ r.ty -= 1;
+ }
+ } else if (r.ty + 1 == r.hy) { // above by one
+ if (r.tx + 2 == r.hx) { // two to the left
+ r.tx += 1;
+ r.ty += 1;
+ } else if (r.tx - 2 == r.hx) { // two to the right
+ r.tx -= 1;
+ r.ty += 1;
+ }
+ } else if (r.ty - 1 == r.hy) { // bellow by one
+ if (r.tx + 2 == r.hx) { // two to the left
+ r.tx += 1;
+ r.ty -= 1;
+ } else if (r.tx - 2 == r.hx) { // two to the right
+ r.tx -= 1;
+ r.ty -= 1;
+ }
+ }
+ }
+};
+
+fn solve(puzzle: []const u8, allocator: std.mem.Allocator) !u64 {
+ var it = std.mem.tokenize(u8, puzzle, "\n");
+ var rope = Rope{};
+ var field = try Field.init(allocator);
+ // process input
+ while (it.next()) |line| {
+ var elts = std.mem.split(u8, line, " ");
+ _ = elts.next() orelse unreachable; // the move word
+ var n = try std.fmt.parseInt(u8, elts.next() orelse unreachable, 10);
+ while (n > 0) : (n -= 1) {
+ rope.step(line[0]);
+ try field.set(rope.tx, rope.ty);
+ }
+ }
+ return field.visited();
+}
diff --git a/2022/09-rope-bridge/input b/2022/09-rope-bridge/input
new file mode 100644
index 0000000..757d633
--- /dev/null
+++ b/2022/09-rope-bridge/input
@@ -0,0 +1,2000 @@
+R 1
+D 1
+L 1
+D 1
+R 2
+L 1
+U 2
+D 1
+U 2
+L 1
+U 1
+L 2
+D 1
+U 2
+L 1
+R 1
+D 1
+L 2
+D 2
+L 2
+R 1
+L 2
+U 2
+R 2
+L 2
+U 2
+L 1
+D 1
+L 2
+U 1
+R 1
+D 2
+L 2
+U 1
+R 1
+D 1
+U 2
+L 1
+D 2
+U 1
+D 1
+R 2
+D 1
+L 2
+D 1
+L 1
+R 1
+D 2
+L 1
+R 2
+D 2
+U 2
+R 2
+D 2
+R 2
+L 2
+D 2
+L 2
+D 1
+U 2
+R 1
+D 2
+L 2
+R 2
+L 1
+D 1
+U 2
+D 1
+R 2
+U 2
+R 2
+D 1
+L 1
+U 2
+D 1
+U 1
+D 2
+U 1
+R 1
+U 2
+D 1
+L 2
+U 1
+L 2
+D 2
+R 1
+U 2
+L 1
+D 2
+R 1
+U 1
+D 1
+L 2
+U 1
+R 1
+D 2
+U 2
+L 1
+U 2
+D 2
+R 1
+U 2
+R 1
+U 2
+R 1
+D 2
+U 1
+D 2
+L 2
+D 2
+L 2
+D 2
+R 1
+U 1
+D 3
+U 1
+R 2
+U 3
+D 1
+U 2
+D 2
+U 2
+D 1
+U 2
+R 2
+L 2
+U 1
+L 3
+D 1
+R 3
+D 3
+R 2
+L 1
+U 3
+D 1
+U 2
+R 2
+D 1
+R 3
+D 2
+R 3
+D 1
+U 3
+L 3
+R 2
+U 3
+L 3
+U 2
+L 3
+D 1
+R 3
+U 3
+R 2
+D 1
+U 3
+R 3
+D 1
+L 2
+D 2
+L 2
+D 3
+R 2
+U 3
+L 3
+D 2
+U 3
+L 2
+U 3
+D 1
+L 1
+D 3
+R 1
+D 3
+U 1
+L 3
+U 1
+D 2
+U 1
+D 1
+U 2
+D 3
+L 1
+U 1
+R 1
+U 3
+D 3
+R 1
+L 2
+R 3
+L 3
+U 1
+D 2
+R 2
+U 2
+D 3
+U 2
+D 3
+L 1
+R 3
+D 3
+R 2
+U 3
+D 3
+L 2
+R 3
+D 3
+R 2
+L 1
+R 3
+D 2
+R 1
+D 3
+L 1
+U 1
+D 2
+R 1
+D 1
+L 1
+R 2
+L 1
+U 1
+L 2
+D 2
+L 2
+D 1
+L 2
+U 3
+D 1
+R 3
+L 2
+R 1
+L 2
+R 3
+U 2
+L 4
+R 3
+L 1
+R 2
+D 2
+L 4
+U 3
+L 1
+D 1
+L 3
+U 2
+L 3
+U 2
+L 1
+R 2
+L 3
+U 1
+D 2
+R 1
+L 4
+R 4
+L 4
+U 2
+D 2
+R 2
+L 2
+U 2
+R 1
+D 3
+L 4
+R 2
+U 1
+L 4
+R 1
+L 1
+D 4
+R 3
+D 1
+R 2
+L 2
+R 3
+L 1
+U 1
+D 3
+U 2
+R 1
+L 1
+D 3
+R 2
+U 2
+R 3
+U 2
+D 1
+R 4
+U 4
+D 3
+U 3
+R 2
+U 1
+L 1
+U 4
+D 1
+R 4
+D 4
+L 3
+U 4
+R 4
+L 1
+R 1
+U 2
+R 4
+D 2
+R 1
+U 2
+L 1
+D 1
+L 3
+R 3
+L 3
+D 3
+L 4
+D 2
+U 2
+D 3
+R 1
+U 1
+D 3
+U 1
+R 3
+D 2
+L 3
+R 2
+D 1
+L 3
+D 3
+U 3
+D 4
+L 2
+U 3
+D 5
+L 2
+D 2
+R 2
+L 3
+D 5
+U 4
+R 1
+D 5
+R 1
+D 1
+L 2
+R 4
+U 2
+D 3
+R 5
+L 2
+R 2
+D 1
+R 2
+U 5
+L 4
+U 5
+D 1
+L 2
+U 2
+R 2
+D 4
+U 3
+L 2
+D 1
+U 4
+L 4
+D 3
+L 3
+D 3
+R 1
+U 1
+R 1
+U 1
+R 2
+D 3
+R 5
+U 1
+D 2
+L 5
+U 5
+L 4
+D 4
+U 4
+L 1
+R 5
+U 2
+L 3
+U 2
+D 3
+L 5
+D 5
+L 2
+U 2
+D 4
+U 3
+D 3
+L 1
+D 2
+R 2
+D 1
+R 4
+L 3
+D 1
+U 4
+L 1
+R 2
+L 4
+D 5
+R 3
+D 1
+L 5
+D 5
+U 3
+R 2
+D 4
+L 2
+R 2
+D 3
+R 3
+U 2
+R 5
+U 4
+R 3
+L 1
+D 2
+U 1
+L 1
+R 2
+U 4
+D 4
+L 1
+R 1
+U 4
+L 3
+U 5
+R 3
+L 4
+D 3
+U 1
+R 4
+U 1
+L 1
+U 3
+R 4
+L 5
+D 1
+U 4
+R 5
+L 1
+R 4
+D 2
+L 6
+D 5
+U 5
+L 5
+R 6
+D 1
+U 2
+R 1
+U 4
+D 6
+L 6
+D 6
+U 6
+D 4
+U 4
+D 1
+U 3
+L 5
+D 6
+R 1
+L 1
+D 2
+L 4
+D 4
+L 4
+R 4
+U 2
+L 3
+D 4
+R 3
+D 4
+U 5
+R 4
+U 1
+R 6
+L 3
+R 2
+U 1
+L 1
+R 2
+D 3
+R 6
+D 6
+U 1
+D 3
+U 4
+D 5
+L 5
+U 3
+D 6
+L 5
+R 5
+U 1
+R 4
+D 2
+L 2
+R 4
+L 5
+R 4
+L 3
+D 5
+R 6
+L 6
+U 1
+R 5
+U 6
+D 2
+R 2
+D 1
+L 6
+U 4
+L 1
+R 5
+L 1
+R 2
+D 1
+L 4
+U 4
+L 1
+R 3
+U 5
+L 2
+D 6
+U 5
+R 6
+D 6
+U 3
+L 3
+U 3
+L 4
+D 5
+U 2
+D 4
+U 5
+R 6
+U 5
+D 2
+U 6
+D 3
+L 3
+D 6
+L 5
+R 2
+D 6
+R 7
+D 3
+L 7
+D 3
+U 2
+R 7
+U 2
+L 6
+R 7
+D 3
+R 7
+U 5
+R 7
+L 5
+R 7
+L 7
+U 4
+D 4
+U 1
+D 3
+U 1
+D 5
+R 3
+U 1
+D 2
+U 1
+L 4
+U 2
+L 6
+D 7
+U 1
+D 4
+U 6
+L 4
+R 4
+D 4
+R 6
+D 7
+R 1
+D 7
+L 4
+R 4
+L 1
+U 1
+R 6
+L 7
+D 7
+L 5
+U 7
+D 3
+L 6
+D 6
+U 4
+R 1
+L 2
+D 4
+R 3
+L 1
+R 7
+D 1
+L 2
+U 1
+D 2
+R 1
+U 3
+D 4
+L 3
+U 6
+L 4
+R 2
+L 1
+U 6
+D 1
+R 5
+U 2
+D 2
+L 7
+U 2
+R 5
+D 2
+R 4
+D 4
+R 3
+L 2
+R 3
+U 7
+L 5
+R 7
+U 2
+L 7
+D 3
+U 6
+D 4
+U 4
+D 6
+U 3
+L 6
+R 4
+D 2
+R 4
+D 2
+R 3
+L 5
+D 1
+U 7
+D 4
+L 4
+U 2
+D 2
+U 7
+L 5
+R 6
+U 8
+L 7
+D 2
+U 1
+R 6
+D 4
+L 4
+R 7
+D 1
+L 6
+D 7
+R 7
+U 3
+L 6
+U 1
+L 8
+D 6
+U 8
+L 7
+U 5
+D 8
+L 2
+D 3
+L 8
+U 1
+D 5
+L 4
+R 6
+D 8
+L 6
+U 5
+R 3
+U 7
+R 6
+U 3
+L 3
+D 4
+R 4
+L 2
+R 6
+D 3
+R 3
+L 8
+U 2
+D 6
+U 3
+D 8
+U 6
+D 4
+U 8
+R 7
+D 2
+U 6
+D 6
+R 1
+U 3
+D 3
+R 1
+U 3
+R 1
+D 7
+L 8
+R 8
+U 7
+R 3
+L 8
+U 2
+L 8
+D 4
+U 4
+R 1
+D 3
+R 4
+U 3
+L 7
+U 2
+R 7
+D 2
+U 4
+D 3
+L 8
+D 5
+L 3
+U 4
+D 6
+L 5
+D 2
+U 1
+R 6
+L 4
+R 6
+U 5
+R 8
+U 8
+D 7
+L 5
+D 2
+L 8
+U 2
+D 1
+R 1
+L 7
+U 4
+R 2
+U 7
+D 6
+R 6
+L 5
+U 8
+D 7
+R 8
+L 8
+D 6
+U 6
+R 1
+D 5
+L 7
+R 8
+L 4
+D 3
+L 2
+U 5
+R 9
+L 8
+D 8
+L 2
+R 4
+L 7
+R 5
+L 1
+R 8
+D 8
+L 4
+U 2
+D 7
+L 7
+D 6
+R 8
+L 3
+D 7
+U 1
+R 6
+D 6
+U 6
+L 9
+D 1
+R 7
+L 5
+R 5
+U 5
+D 4
+L 8
+U 4
+D 8
+R 4
+D 6
+U 3
+D 7
+L 5
+D 6
+R 9
+U 4
+R 6
+L 3
+U 4
+D 9
+L 7
+R 5
+D 9
+L 6
+U 7
+L 7
+R 4
+D 5
+R 7
+L 5
+R 3
+U 8
+L 6
+U 5
+L 9
+R 8
+U 4
+D 2
+L 4
+D 7
+R 7
+D 4
+L 4
+U 2
+L 3
+R 1
+D 3
+U 6
+R 1
+U 8
+R 2
+L 4
+D 3
+L 5
+U 4
+R 7
+L 2
+R 7
+L 9
+D 9
+U 5
+L 4
+U 1
+D 1
+U 6
+D 1
+L 6
+D 7
+U 5
+D 9
+R 9
+D 5
+U 9
+L 3
+R 5
+D 10
+R 1
+U 7
+D 6
+L 3
+U 5
+R 1
+D 5
+R 8
+U 3
+L 1
+D 2
+R 1
+L 6
+R 8
+D 9
+U 9
+D 4
+R 1
+U 8
+L 5
+U 4
+D 7
+L 1
+R 4
+L 6
+D 4
+R 5
+D 1
+R 10
+D 5
+R 7
+U 6
+R 5
+U 2
+L 8
+R 1
+U 3
+L 5
+U 4
+L 3
+D 3
+U 6
+D 10
+L 3
+D 7
+L 5
+D 4
+U 6
+R 9
+U 5
+D 5
+R 2
+L 7
+U 8
+D 5
+R 9
+L 6
+R 8
+U 9
+L 4
+R 10
+D 10
+L 9
+R 8
+L 4
+R 5
+L 9
+D 1
+L 3
+R 9
+U 2
+L 5
+R 2
+U 1
+R 4
+D 10
+U 3
+D 8
+L 9
+D 8
+L 5
+D 4
+U 2
+L 8
+R 5
+U 4
+D 1
+L 4
+U 7
+D 9
+R 3
+D 7
+R 9
+L 6
+R 6
+U 8
+L 10
+U 5
+D 4
+R 5
+L 6
+D 7
+L 10
+R 1
+L 9
+U 6
+D 9
+R 7
+L 7
+D 6
+U 6
+R 1
+D 7
+L 1
+R 9
+D 9
+R 3
+L 5
+D 4
+R 3
+L 5
+D 11
+U 1
+R 6
+D 8
+R 4
+D 3
+R 9
+U 3
+D 8
+U 7
+R 2
+U 10
+R 4
+L 4
+D 10
+R 8
+U 11
+R 7
+D 7
+R 9
+D 11
+U 6
+R 7
+D 10
+L 4
+D 5
+L 7
+D 3
+L 4
+D 4
+U 4
+R 3
+L 9
+D 4
+L 8
+U 5
+R 7
+L 2
+D 4
+R 11
+U 10
+D 3
+R 8
+D 3
+R 10
+L 8
+U 6
+R 4
+D 10
+R 7
+D 3
+R 2
+U 1
+D 5
+L 8
+U 2
+R 1
+U 8
+R 11
+L 3
+U 10
+L 5
+D 3
+L 6
+U 10
+L 11
+D 4
+L 5
+D 1
+L 4
+D 1
+L 3
+R 7
+U 7
+R 4
+L 1
+U 10
+D 11
+L 1
+R 1
+U 9
+D 6
+L 9
+D 1
+L 4
+D 11
+L 5
+U 2
+L 5
+D 8
+U 10
+D 5
+U 10
+L 8
+R 11
+D 10
+U 11
+R 4
+U 6
+D 11
+R 1
+L 4
+U 12
+L 8
+U 12
+D 4
+L 7
+U 7
+L 8
+D 3
+U 1
+L 12
+D 5
+U 3
+D 6
+R 7
+U 1
+D 12
+R 6
+U 3
+D 3
+R 12
+U 5
+R 3
+U 8
+L 6
+R 6
+U 3
+L 4
+D 8
+L 5
+D 12
+U 1
+L 9
+R 4
+L 1
+D 6
+U 9
+L 5
+R 3
+L 9
+D 8
+R 6
+D 3
+U 6
+L 1
+D 7
+U 5
+D 1
+L 11
+R 7
+D 11
+L 3
+U 6
+R 9
+D 12
+R 11
+L 5
+R 8
+L 2
+U 10
+R 6
+U 10
+L 9
+U 1
+L 1
+R 8
+L 7
+R 3
+U 4
+L 3
+R 8
+L 9
+R 11
+L 9
+D 11
+U 1
+L 12
+R 6
+L 3
+R 3
+D 12
+U 9
+L 9
+D 8
+R 4
+L 7
+R 1
+U 2
+R 4
+U 4
+R 11
+U 7
+D 11
+U 3
+D 6
+U 7
+L 2
+D 4
+U 9
+R 3
+L 8
+R 9
+L 4
+R 5
+L 7
+D 3
+R 8
+L 6
+U 10
+R 3
+L 6
+D 8
+U 3
+D 9
+L 1
+U 13
+R 12
+L 13
+R 2
+U 8
+R 1
+D 11
+R 5
+L 4
+U 5
+L 3
+D 13
+U 2
+D 1
+U 2
+L 9
+D 3
+R 6
+U 13
+L 3
+U 5
+R 2
+D 2
+L 5
+U 4
+R 6
+D 1
+U 9
+L 7
+R 11
+U 10
+D 12
+R 10
+U 7
+R 5
+L 2
+R 13
+L 13
+D 3
+R 7
+U 1
+L 1
+D 2
+L 9
+U 12
+D 7
+U 13
+L 12
+U 13
+D 7
+U 7
+D 8
+L 2
+U 6
+D 2
+U 6
+L 8
+U 4
+D 11
+U 11
+L 11
+R 10
+L 10
+R 6
+D 13
+U 2
+L 7
+U 8
+D 1
+R 6
+L 7
+R 9
+L 8
+R 9
+L 6
+R 7
+D 12
+R 11
+L 8
+R 1
+D 5
+R 5
+L 10
+U 6
+L 8
+D 9
+L 5
+U 4
+D 12
+U 8
+L 13
+U 6
+D 10
+R 5
+L 13
+D 7
+L 13
+R 5
+L 10
+D 13
+L 9
+R 3
+D 8
+U 9
+D 10
+U 10
+D 7
+L 5
+R 5
+D 9
+L 7
+R 10
+D 13
+R 1
+U 2
+R 6
+U 14
+R 10
+D 6
+U 13
+D 14
+U 5
+D 1
+U 8
+R 4
+U 9
+R 13
+L 4
+D 2
+R 8
+U 2
+D 12
+U 3
+R 6
+U 6
+D 11
+R 7
+L 12
+R 9
+U 7
+D 1
+R 14
+L 11
+U 4
+D 13
+U 5
+L 7
+R 14
+L 1
+U 6
+D 3
+L 1
+U 13
+D 8
+U 14
+D 5
+U 14
+L 1
+R 1
+D 5
+U 7
+L 8
+R 6
+U 1
+D 2
+R 14
+U 13
+L 10
+U 8
+D 13
+U 6
+R 2
+D 4
+R 6
+U 7
+D 10
+L 6
+U 5
+L 3
+D 9
+U 13
+D 8
+U 3
+R 3
+L 12
+D 5
+R 8
+U 7
+R 11
+U 6
+D 7
+R 13
+U 1
+D 9
+U 10
+D 3
+L 5
+R 12
+L 4
+D 13
+R 7
+D 12
+R 11
+D 9
+R 5
+U 13
+R 3
+D 4
+U 10
+R 3
+U 6
+L 4
+R 1
+U 4
+L 9
+D 11
+U 5
+D 3
+U 13
+D 1
+L 1
+D 13
+L 2
+R 9
+L 4
+R 2
+U 9
+D 9
+U 12
+L 14
+R 2
+L 9
+R 5
+U 2
+D 3
+R 13
+U 5
+D 1
+U 15
+R 6
+D 14
+R 8
+L 9
+D 14
+L 6
+R 8
+U 14
+R 11
+L 3
+D 15
+U 5
+R 1
+L 7
+R 12
+D 1
+R 4
+D 13
+U 9
+D 2
+L 3
+U 10
+R 10
+D 2
+R 6
+U 13
+D 7
+R 5
+U 5
+L 12
+U 6
+R 1
+L 7
+U 9
+D 15
+L 8
+U 9
+L 5
+R 3
+L 9
+U 6
+L 11
+D 8
+L 11
+D 13
+U 3
+R 6
+D 2
+L 10
+R 15
+U 2
+D 8
+R 6
+D 6
+L 8
+D 7
+U 2
+D 14
+U 4
+R 6
+D 15
+L 12
+R 4
+D 3
+U 7
+D 10
+L 8
+U 7
+R 10
+U 11
+D 2
+R 10
+D 10
+U 13
+R 8
+L 2
+U 12
+R 9
+U 12
+R 5
+U 10
+L 6
+R 3
+D 10
+L 10
+U 6
+L 4
+R 3
+D 9
+R 15
+D 14
+L 11
+R 5
+U 2
+R 14
+L 15
+R 3
+D 3
+L 4
+U 10
+D 14
+L 9
+D 5
+L 16
+U 12
+L 4
+D 15
+L 10
+R 14
+D 4
+R 12
+L 7
+U 5
+R 3
+L 6
+U 16
+L 5
+U 8
+D 8
+L 6
+D 3
+U 14
+R 1
+L 13
+U 4
+D 11
+R 5
+L 11
+D 7
+R 1
+L 14
+U 10
+L 5
+D 15
+U 14
+L 4
+D 7
+U 3
+R 1
+U 2
+R 3
+D 16
+U 7
+R 7
+D 13
+R 7
+D 5
+U 7
+R 16
+U 4
+L 3
+R 9
+U 1
+D 2
+R 5
+D 3
+U 8
+R 5
+L 13
+U 13
+L 2
+R 9
+L 14
+D 10
+R 1
+U 1
+R 14
+U 14
+R 2
+L 1
+R 12
+L 1
+D 6
+R 2
+D 7
+R 11
+L 5
+D 8
+R 15
+D 12
+R 12
+L 8
+D 10
+R 2
+D 12
+U 15
+L 9
+D 4
+U 3
+L 8
+D 3
+U 9
+D 16
+L 2
+U 14
+R 15
+D 14
+U 12
+D 6
+U 14
+R 11
+D 12
+R 2
+U 13
+L 2
+R 1
+D 6
+U 13
+D 15
+U 1
+R 14
+L 16
+D 8
+R 13
+L 14
+R 3
+D 8
+L 6
+R 16
+D 6
+L 13
+R 2
+L 11
+D 2
+U 1
+R 15
+L 9
+U 1
+R 12
+L 9
+D 7
+L 8
+U 2
+L 14
+R 7
+U 8
+D 15
+R 8
+D 13
+L 15
+R 11
+D 17
+U 2
+R 14
+L 9
+U 11
+D 6
+U 4
+D 8
+U 16
+D 5
+L 3
+D 11
+L 7
+U 11
+L 4
+D 5
+L 5
+D 2
+U 8
+R 17
+D 17
+U 12
+R 4
+L 13
+R 15
+L 10
+U 2
+L 10
+R 6
+D 1
+U 6
+L 3
+D 8
+R 4
+D 1
+L 4
+D 13
+R 1
+U 3
+L 1
+U 9
+D 13
+U 2
+D 13
+R 6
+D 8
+R 6
+D 13
+R 4
+D 10
+L 10
+U 8
+D 1
+R 6
+U 14
+R 3
+L 10
+U 15
+L 11
+U 13
+L 4
+U 5
+L 16
+R 16
+U 11
+R 14
+D 7
+U 5
+R 9
+L 5
+U 12
+R 16
+U 10
+D 5
+R 17
+L 3
+D 5
+U 13
+R 3
+U 3
+L 14
+U 1
+L 8
+R 2
+D 3
+U 9
+D 7
+L 1
+D 5
+R 16
+D 12
+R 1
+U 2
+L 16
+U 3
+R 18
+D 11
+R 3
+L 17
+R 7
+L 6
+D 13
+L 5
+R 12
+D 3
+U 1
+L 1
+U 5
+L 8
+R 11
+L 13
+D 14
+R 17
+D 17
+L 2
+U 7
+D 18
+R 3
+D 2
+U 6
+D 9
+R 3
+U 3
+R 5
+D 16
+R 9
+D 13
+U 8
+D 17
+R 4
+L 6
+R 7
+D 2
+R 15
+U 10
+R 15
+D 6
+L 8
+R 17
+D 5
+L 9
+U 18
+D 10
+U 3
+L 6
+U 10
+D 10
+U 16
+R 6
+D 18
+U 10
+D 8
+U 14
+R 3
+U 14
+L 16
+R 3
+D 5
+L 2
+R 4
+D 9
+L 13
+R 17
+L 8
+D 2
+R 16
+D 18
+L 11
+D 15
+U 5
+D 7
+U 14
+D 13
+U 7
+L 13
+D 13
+R 1
+D 15
+R 11
+L 1
+U 6
+D 14
+L 6
+U 8
+D 15
+R 8
+L 12
+D 17
+R 8
+L 17
+D 16
+R 9
+D 19
+U 4
+R 9
+U 10
+L 3
+U 3
+D 5
+R 2
+U 6
+L 16
+D 8
+R 4
+L 16
+R 15
+U 6
+L 8
+D 6
+L 6
+R 1
+L 8
+D 13
+L 1
+U 7
+R 16
+L 16
+U 1
+L 18
+D 16
+L 8
+U 2
+D 1
+R 2
+D 10
+U 8
+D 2
+R 18
+U 14
+D 15
+R 15
+U 3
+D 1
+U 17
+L 17
+D 15
+L 14
+R 6
+L 18
+U 19
+L 6
+U 17
+L 1
+D 2
+U 17
+R 11
+L 3
+R 3
+L 12
+U 1
+L 9
+U 13
+D 15
+U 12
+R 1
+L 5
+D 17
+L 14
+D 13
+L 2
+D 10
+U 5
+R 13
+L 19
+D 1
+R 12
+U 17
+R 15
+D 19
+U 12
+D 16
+R 2
+U 3
+R 15
+L 13
+U 11
+D 19
+R 10
+D 19
+L 2
+U 12
+R 5
+L 13
+U 13
+R 1
+D 11
+R 17
+D 7
+U 4
+D 14
+L 13
+R 8
+L 8
+D 8
diff --git a/2022/09-rope-bridge/second.zig b/2022/09-rope-bridge/second.zig
new file mode 100644
index 0000000..f866b75
--- /dev/null
+++ b/2022/09-rope-bridge/second.zig
@@ -0,0 +1,247 @@
+const std = @import("std");
+
+const example = @embedFile("example");
+const example2 = @embedFile("example2");
+const input = @embedFile("input");
+
+pub fn main() anyerror!void {
+ var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
+ defer arena.deinit();
+ const allocator = arena.allocator();
+
+ try std.testing.expectEqual(try solve(example, allocator), 1);
+ try std.testing.expectEqual(try solve(example2, allocator), 36);
+ const result = try solve(input, allocator);
+ try std.io.getStdOut().writer().print("{}\n", .{result});
+}
+
+const Line = struct {
+ data: std.ArrayList(bool),
+ x: i64,
+ fn init(allocator: std.mem.Allocator) !*Line {
+ var l = try allocator.create(Line);
+ l.data = std.ArrayList(bool).init(allocator);
+ return l;
+ }
+ inline fn len(l: Line) usize {
+ return l.data.items.len;
+ }
+ fn set(l: *Line, x: i64) !void {
+ if (l.len() == 0) { // this is en empty line
+ l.x = x;
+ try l.data.append(true);
+ return;
+ }
+ const lx = @intCast(i64, l.len());
+ if (x >= l.x) {
+ if (x < l.x + lx) { // just set the value
+ l.data.items[@intCast(usize, x - l.x)] = true;
+ } else { // we need to add trailing spaces
+ var i: usize = l.len();
+ while (i < x - l.x) : (i += 1) {
+ try l.data.append(false);
+ }
+ try l.data.append(true);
+ }
+ } else { // we need to shift right and add leading spaces
+ const oldLen = l.len();
+ l.data.items.len += @intCast(usize, l.x - x);
+ try l.data.ensureUnusedCapacity(l.len());
+ std.mem.copyBackwards(bool, l.data.items[@intCast(usize, l.x - x)..], l.data.items[0..oldLen]);
+ l.data.items[0] = true;
+ var i: usize = 1;
+ while (i < @intCast(usize, l.x - x)) : (i += 1) {
+ l.data.items[i] = false;
+ }
+ l.x = x;
+ }
+ }
+ pub fn visited(l: Line) u64 {
+ var tot: u64 = 0;
+ var i: usize = 0;
+ while (i < l.len()) : (i += 1) {
+ if (l.data.items[i]) {
+ tot += 1;
+ }
+ }
+ return tot;
+ }
+};
+
+pub const Field = struct {
+ allocator: std.mem.Allocator,
+ x: i64 = 0,
+ y: i64 = 0,
+ lines: std.ArrayList(*Line),
+ lx: usize = 0,
+ fn init(allocator: std.mem.Allocator) !*Field {
+ var f = try allocator.create(Field);
+ f.allocator = allocator;
+ f.x = undefined;
+ f.y = 0;
+ f.lines = std.ArrayList(*Line).init(allocator);
+ var l = try f.lines.addOne();
+ l.* = try Line.init(allocator);
+ f.lx = 0;
+ return f;
+ }
+ inline fn len(f: Field) usize {
+ return f.lines.items.len;
+ }
+ pub fn set(f: *Field, x: i64, y: i64) !void {
+ if (y >= f.y) {
+ if (y < f.y + @intCast(i64, f.lines.items.len)) { // the line exists
+ try f.lines.items[@intCast(usize, y - f.y)].set(x);
+ } else { // append lines
+ var i: usize = f.lines.items.len;
+ while (i < y - f.y) : (i += 1) {
+ try f.lines.append(try Line.init(f.allocator));
+ }
+ var l = try Line.init(f.allocator);
+ try l.set(x);
+ try f.lines.append(l);
+ }
+ } else { // preprend lines
+ const oldLen = f.lines.items.len;
+ f.lines.items.len += @intCast(usize, f.y - y);
+ try f.lines.ensureUnusedCapacity(f.lines.items.len);
+ std.mem.copyBackwards(*Line, f.lines.items[@intCast(usize, f.y - y)..], f.lines.items[0..oldLen]);
+ var l = try Line.init(f.allocator);
+ try l.set(x);
+ f.lines.items[0] = l;
+ var i: usize = 1;
+ while (i < @intCast(usize, f.y - y)) : (i += 1) {
+ f.lines.items[i] = try Line.init(f.allocator);
+ }
+ f.y = y;
+ }
+ if (x < f.x or x >= f.x + @intCast(i64, f.lx)) { // recalculate boundaries
+ f.x = std.math.maxInt(i64);
+ var x2: i64 = std.math.minInt(i64);
+ for (f.lines.items) |line| {
+ if (line.len() == 0) continue;
+ if (f.x > line.x) f.x = line.x;
+ if (x2 < line.x + @intCast(i64, line.len())) x2 = line.x + @intCast(i64, line.len());
+ }
+ f.lx = @intCast(usize, x2 - f.x);
+ }
+ return;
+ }
+ pub fn visited(f: Field) u64 {
+ var tot: u64 = 0;
+ var i: usize = 0;
+ while (i < f.len()) : (i += 1) {
+ tot += f.lines.items[i].visited();
+ }
+ return tot;
+ }
+};
+
+const Rope = struct {
+ hx: i64 = 0,
+ hy: i64 = 0,
+ tx: i64 = 0,
+ ty: i64 = 0,
+ fn stepH(r: *Rope, direction: u8) void {
+ switch (direction) {
+ 'D' => {
+ r.hy += 1;
+ },
+ 'L' => {
+ r.hx -= 1;
+ },
+ 'R' => {
+ r.hx += 1;
+ },
+ 'U' => {
+ r.hy -= 1;
+ },
+ else => unreachable,
+ }
+ }
+ fn stepT(r: *Rope) void {
+ if (r.tx == r.hx) { // same line
+ if (r.ty + 2 == r.hy) { // to the left
+ r.ty += 1;
+ } else if (r.ty - 2 == r.hy) { // to the right
+ r.ty -= 1;
+ }
+ } else if (r.ty == r.hy) { // same column
+ if (r.tx + 2 == r.hx) { // to the top
+ r.tx += 1;
+ } else if (r.tx - 2 == r.hx) { // to the bottom
+ r.tx -= 1;
+ }
+ } else if (r.tx + 1 == r.hx) { // on the left by one
+ if (r.ty + 2 == r.hy) { // above by two
+ r.tx += 1;
+ r.ty += 1;
+ } else if (r.ty - 2 == r.hy) { // bellow by two
+ r.tx += 1;
+ r.ty -= 1;
+ }
+ } else if (r.tx - 1 == r.hx) { // on the right by one
+ if (r.ty + 2 == r.hy) { // above by two
+ r.tx -= 1;
+ r.ty += 1;
+ } else if (r.ty - 2 == r.hy) { // bellow by two
+ r.tx -= 1;
+ r.ty -= 1;
+ }
+ } else if (r.ty + 1 == r.hy) { // above by one
+ if (r.tx + 2 == r.hx) { // two to the left
+ r.tx += 1;
+ r.ty += 1;
+ } else if (r.tx - 2 == r.hx) { // two to the right
+ r.tx -= 1;
+ r.ty += 1;
+ }
+ } else if (r.ty - 1 == r.hy) { // bellow by one
+ if (r.tx + 2 == r.hx) { // two to the left
+ r.tx += 1;
+ r.ty -= 1;
+ } else if (r.tx - 2 == r.hx) { // two to the right
+ r.tx -= 1;
+ r.ty -= 1;
+ }
+ } else {
+ if (r.tx + 2 == r.hx) { // far left
+ r.tx += 1;
+ } else if (r.tx - 2 == r.hx) { // far right
+ r.tx -= 1;
+ }
+ if (r.ty + 2 == r.hy) { // far above
+ r.ty += 1;
+ } else if (r.ty - 2 == r.hy) { // far bellow
+ r.ty -= 1;
+ }
+ }
+ }
+};
+
+fn solve(puzzle: []const u8, allocator: std.mem.Allocator) !u64 {
+ var it = std.mem.tokenize(u8, puzzle, "\n");
+ var rope: [9]Rope = undefined;
+ for (rope) |*r| {
+ r.* = Rope{};
+ }
+ var field = try Field.init(allocator);
+ // process input
+ while (it.next()) |line| {
+ var elts = std.mem.split(u8, line, " ");
+ _ = elts.next() orelse unreachable; // the move word
+ var n = try std.fmt.parseInt(u8, elts.next() orelse unreachable, 10);
+ while (n > 0) : (n -= 1) {
+ rope[0].stepH(line[0]);
+ rope[0].stepT();
+ var i: usize = 1;
+ while (i < rope.len) : (i += 1) {
+ rope[i].hx = rope[i - 1].tx;
+ rope[i].hy = rope[i - 1].ty;
+ rope[i].stepT();
+ }
+ try field.set(rope[rope.len - 1].tx, rope[rope.len - 1].ty);
+ }
+ }
+ return field.visited();
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-23 03:02:29 +0000