aoc-2021/22.py

from util import get_input
from more_itertools import flatten
from itertools import product

def parse(line):
    action, stuff = line.split()
    coords = [s[2:].split("..") for s in stuff.split(",")]
    coords = [(int(a), int(b) + 1) for [a, b] in coords]
    return (action == 'on', tuple(coords))

input = get_input("22.input", fn=parse)

def part1():
    area = set()

    for (on, coords) in input:
        for x in range(max(coords[0][0], -50), min(coords[0][1], 50)):
            for y in range(max(coords[1][0], -50), min(coords[1][1], 50)):
                for z in range(max(coords[2][0], -50), min(coords[2][1], 50)):
                    if on:
                        area.add((x, y, z))
                    else:
                        area.discard((x, y, z))

    print("Part 1:", len(area))

def split_by_plane(blk, coord, val):
    res = list()
    nblk = list(blk)
    if val > blk[coord][0]:
        nblk[coord] = (blk[coord][0], min(val, blk[coord][1]))
        res.append(tuple(nblk))
    if val < blk[coord][1]:
        nblk[coord] = (max(val, blk[coord][0]), blk[coord][1])
        res.append(tuple(nblk))
    return res

def split_by(a, b):
    res = {a}
    for coord in range(3):
        for idx in range(2):
            res = set(flatten([split_by_plane(block, coord, b[coord][idx]) for block in res]))
    return res

def intersects_coord(a, b):
    r = range(b[0] + 1, b[1])
    return a[0] in r or a[1] in r or (a[0] == b[0] and a[1] == b[1])

def intersects(a, b):
    for coord in range(3):
        if not (intersects_coord(a[coord], b[coord]) or intersects_coord(b[coord], a[coord])):
            return False
    return True

def contains(b, a):
    for coord in range(3):
        if range(a[coord][0], a[coord][1]) not in range(b[coord][0], b[coord][1]):
            return False
    return True

def check_intersection(aa, bb):
    for a in aa:
        for b in bb:
            if a != b:
                if intersects(a, b):
                    raise ValueError("Intersection", a, b)

def block_size(a):
    return (a[0][1] - a[0][0]) * (a[1][1] - a[1][0]) * (a[2][1] - a[2][0])

def test_split():
    orig = ((-10, 10), (-10, 10), (-10, 10))
    rem = ((-5, 5), (-5, 5), (-5, 5))
    split = set(split_by(orig, rem))
    print(block_size(orig))
    print(block_size(rem))
    print(sum(block_size(a) for a in split))
    res = split.difference({rem})
    print(sum(block_size(a) for a in res))
    check_intersection(split, split)


area = set()

for i, (on, nblock) in enumerate(input):
    print(i, "/", len(input))
    if not on:
        for eblock in list(area):
            if not intersects(eblock, nblock):
                continue
            if eblock == nblock:
                continue
            if contains(nblock, eblock):
                area.remove(eblock)
                continue
            area.remove(eblock)
            newarea = set(split_by(eblock, nblock))
            area = area.union(newarea)
        area = {b for b in area if not intersects(b, nblock)}
    else:
        nblocks = {nblock}
        possible_issues = [a for a in area if intersects(a, nblock)]
        for eblock in possible_issues:
            for nblock in list(nblocks):
                if eblock == nblock:
                    continue
                if not intersects(eblock, nblock):
                    continue
                nblocks.remove(nblock)
                new = set(split_by(nblock, eblock))
                new = {b for b in new if not intersects(b, eblock)}
                nblocks = nblocks.union(new)
        area = area.union(nblocks)

part1()
print("Part 2:", sum(block_size(b) for b in area))