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), 93);
    const result = try solve(input);
    try std.io.getStdOut().writer().print("{}\n", .{result});
}

const Line = struct {
    data: std.ArrayList(u8),
    x: u64,
    fn get(l: *Line, x: u64) u8 {
        if (x >= l.x and x < l.x + @intCast(u64, l.len())) return l.data.items[@intCast(usize, x - @intCast(u64, l.x))];
        return ' ';
    }
    fn init() !*Line {
        var l = try allocator.create(Line);
        l.data = std.ArrayList(u8).init(allocator);
        return l;
    }
    inline fn len(l: Line) usize {
        return l.data.items.len;
    }
    fn set(l: *Line, x: u64, v: u8) !void {
        if (l.len() == 0) { // this is en empty line
            l.x = x;
            try l.data.append(v);
            return;
        }
        const lx = @intCast(u64, l.len());
        if (x >= l.x) {
            if (x < l.x + lx) { // just set the value
                l.data.items[@intCast(usize, x - l.x)] = v;
            } else { // we need to add trailing spaces
                var i: usize = l.len();
                while (i < x - l.x) : (i += 1) {
                    try l.data.append(' ');
                }
                try l.data.append(v);
            }
        } 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(u8, l.data.items[@intCast(usize, l.x - x)..], l.data.items[0..oldLen]);
            l.data.items[0] = v;
            var i: usize = 1;
            while (i < @intCast(usize, l.x - x)) : (i += 1) {
                l.data.items[i] = ' ';
            }
            l.x = x;
        }
    }
};

pub const Field = struct {
    x: u64 = 0,
    y: u64 = 0,
    lines: std.ArrayList(*Line),
    lx: usize = 0,
    pub fn get(f: *Field, x: u64, y: u64) u8 {
        if (y >= f.y and y < f.y + @intCast(u64, f.lines.items.len)) return f.lines.items[@intCast(usize, y - @intCast(u64, f.y))].get(x);
        return ' ';
    }
    fn init() !*Field {
        var f = try allocator.create(Field);
        f.x = undefined;
        f.y = 0;
        f.lines = std.ArrayList(*Line).init(allocator);
        var l = try f.lines.addOne();
        l.* = try Line.init();
        f.lx = 0;
        return f;
    }
    inline fn isIn(f: *Field, x: u64, y: u64) bool {
        return x >= f.x and y >= f.y and x < f.x + @intCast(u64, f.lx) and y < f.y + @intCast(u64, f.lines.items.len);
    }
    inline fn len(f: Field) usize {
        return f.lines.items.len;
    }
    pub fn set(f: *Field, x: u64, y: u64, v: u8) !void {
        if (y >= f.y) {
            if (y < f.y + @intCast(u64, f.lines.items.len)) { // the line exists
                try f.lines.items[@intCast(usize, y - f.y)].set(x, v);
            } else { // append lines
                var i: usize = f.lines.items.len;
                while (i < y - f.y) : (i += 1) {
                    try f.lines.append(try Line.init());
                }
                var l = try Line.init();
                try l.set(x, v);
                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();
            try l.set(x, v);
            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.y = y;
        }
        if (x < f.x or x >= f.x + @intCast(u64, f.lx)) { // recalculate boundaries
            f.x = std.math.maxInt(u64);
            var x2: u64 = std.math.minInt(u64);
            for (f.lines.items) |line| {
                if (line.len() == 0) continue;
                if (f.x > line.x) f.x = line.x;
                if (x2 < line.x + @intCast(u64, line.len())) x2 = line.x + @intCast(u64, line.len());
            }
            f.lx = @intCast(usize, x2 - f.x);
        }
        return;
    }
};

fn solve(puzzle: []const u8) !u64 {
    var it = std.mem.tokenize(u8, puzzle, "\n");
    var field = try Field.init();
    // process input
    while (it.next()) |line| {
        var coords = std.mem.tokenize(u8, line, " ->,");
        var x = try std.fmt.parseInt(u64, coords.next() orelse continue, 10);
        var y = try std.fmt.parseInt(u64, coords.next() orelse unreachable, 10);
        try field.set(x, y, '#');
        while (true) {
            var a = try std.fmt.parseInt(u64, coords.next() orelse break, 10);
            var b = try std.fmt.parseInt(u64, coords.next() orelse unreachable, 10);

            while (x != a or y != b) {
                if (x < a) {
                    x += 1;
                } else if (x > a) {
                    x -= 1;
                }
                if (y < b) {
                    y += 1;
                } else if (y > b) {
                    y -= 1;
                }
                try field.set(x, y, '#');
            }
        }
    }
    // run simulation
    const maxY = field.y + field.len();
    var i: usize = 0;
    while (true) : (i += 1) { // add sand forever
        var x: u64 = 500;
        var y: u64 = field.y;
        while (true) { // let the sand fall
            if (y == maxY) {
                try field.set(x - 1, y + 1, '#');
                try field.set(x, y + 1, '#');
                try field.set(x + 1, y + 1, '#');
            }
            switch (field.get(x, y + 1)) {
                ' ' => y += 1, // we can fall straight down
                else => {
                    switch (field.get(x - 1, y + 1)) {
                        ' ' => { // we can fall down to the left
                            x -= 1;
                            y += 1;
                        },
                        else => {
                            switch (field.get(x + 1, y + 1)) {
                                ' ' => { // we can fall down to the right
                                    x += 1;
                                    y += 1;
                                },
                                else => { // we stop falling
                                    try field.set(x, y, 'o');
                                    break;
                                },
                            }
                        },
                    }
                },
            }
        }
        if (x == 500 and y == 0) {
            break;
        }
    }
    return i + 1;
}