#coordinates are in region 4 - (0,0) is in the upper left corner, and all positive coords move southeast from there

class Bbox:
    def __init__(self, left, top, right, bottom):
        self.left = left
        self.top = top
        self.right = right
        self.bottom = bottom
    @property
    def width(self):
        return 1 + self.right - self.left
    @property
    def height(self):
        return 1 + self.bottom - self.top

    @property
    def nw(self):
        return self.left, self.top
    @property
    def se(self):
        return self.right, self.bottom

    @property
    def area(self):
        return self.width * self.height

    def quadrisect(self):
        mid_x = (self.left + self.right)/2
        mid_y = (self.top + self.bottom)/2
        x_coords = (self.left, mid_x, self.right)
        y_coords = (self.top, mid_y, self.bottom)
        boxes = []
        for x in ((self.left, mid_x), (mid_x+1, self.right)):
            for y in ((self.top, mid_y), (mid_y+1, self.bottom)):
                box = Bbox(x[0], y[0], x[1], y[1])
                if box:
                    boxes.append(box)
        return boxes

    def contains(self, other):
        if isinstance(other, tuple):
            x,y = other
            return self.left <= x <= self.right and self.top <= y <= self.bottom
        else:
            return all(self.contains(p) for p in other.iter_corners())

    def is_real(self):
        return self.left <= self.right and self.top <= self.bottom

    def intersect(self, other):
        box = Bbox(
            max(self.left, other.left),
            max(self.top, other.top),
            min(self.right, other.right),
            min(self.bottom, other.bottom)
        )
        if not box:
            return None
        return box
    def iter_corners(self):
        for x in (self.left, self.right):
            for y in (self.top, self.bottom):
                yield (x,y)
    def iter_lattice_points(self):
        for i in range(self.left, self.right+1):
            for j in range(self.top, self.bottom+1):
                yield (i,j)
    def tuple(self):
        return (self.left, self.top, self.right, self.bottom)
    def __nonzero__(self):
        #wait, this doesn't work because bboxes always have nonzero area.
        #return self.right-self.left > 0 and self.bottom - self.top > 0
        return self.is_real()
    def __eq__(self, other):
        return self.left == other.left and self.right == other.right and self.top == other.top and self.bottom == other.bottom
    def __repr__(self):
        return "Bbox({}, {}, {}, {})".format(self.left, self.top, self.right, self.bottom)

class QuadRegion:
    def __init__(self, bbox, value=None):
        self.bbox = bbox
        self.value = value
        self.children = None
    def split(self):
        assert self.is_leaf_node()
        self.children = [QuadRegion(bbox, self.value) for bbox in self.bbox.quadrisect()]

    def is_leaf_node(self):
        return self.children is None

    #check if all children have the same value, and if so delete them and become a leaf node with that value.
    #returns True if any changes occurred, False otherwise.
    def maybe_coalesce(self):
        if self.is_leaf_node():
            return False
        for child in self.children:
            child.maybe_coalesce()
            if not child.is_leaf_node():
                return False
        if all(child.value == self.children[0].value for child in self.children):
            self.value = self.children[0].value
            self.children = None

    def apply(self, bbox, func, depth=0):
        assert self.bbox.contains(bbox), "{} does not contain {}".format(self, bbox)
        assert depth < 50, "exceeded maximum depth for {}, {}".format(self, bbox)
        if not self.is_leaf_node():
            for child in self.children:
                child_bbox = child.bbox.intersect(bbox)
                if child_bbox:
                    child.apply(child_bbox, func, depth+1)
        else:
            if self.bbox == bbox:
                self.value = func(self.value)
            else:
                self.split()
                self.apply(bbox, func, depth+1)
        self.maybe_coalesce()

    def iter_leaf_nodes(self):
        if self.is_leaf_node():
            yield self
        else:
            for child in self.children:
                for leaf in child.iter_leaf_nodes():
                    yield leaf

    def __repr__(self):
        if not self.is_leaf_node():
            return "QuadRegion({}, {}, {})".format(self.bbox, self.value, self.children)
        else:
            return "QuadRegion({}, {})".format(self.bbox, self.value)

from PIL import Image, ImageDraw

def fancy_render(region):
    x_offset = region.bbox.left
    y_offset = region.bbox.top
    to_screen_coord = lambda i,j: (1+(i - x_offset)*2, 1+(j - y_offset)*2)
    img = Image.new("RGB", (2*region.bbox.width+1, 2*region.bbox.height+1), "gray")
    draw = ImageDraw.Draw(img)
    pix = img.load()
    def _render(region):
        if region.children:
            for child in region.children:
                _render(child)
        else:
            color = (255,255,255) if region.value else (0,0,0)
            a,b = to_screen_coord(*region.bbox.nw)
            c,d = to_screen_coord(*region.bbox.se)
            draw.rectangle((a-1,b-1,c+1,d+1), outline="red", fill=color)
    _render(region)
    return img

import re
from collections import defaultdict
import time

instructions = []
with open("p6_input.txt") as file:
    for line in file:
        m = re.match(r"(toggle|turn on|turn off) (\d*?),(\d*?) through (\d*?),(\d*?)$", line)
        rule = [m.group(1)] + [int(m.group(x)) for x in range(2, 6)]
        instructions.append(rule)

t = time.time()
r = QuadRegion(Bbox(0,0,999,999), False)
funcs = {"turn on": lambda v: True, "turn off": lambda v: False, "toggle": lambda v: not v}
for idx, (rule, left, top, right, bottom) in enumerate(instructions):
    print "{} / {}\r".format(idx, len(instructions)),
    assert rule in funcs
    r.apply(Bbox(left, top, right, bottom), funcs[rule])

total = 0
for region in r.iter_leaf_nodes():
    if region.value:
        total += region.bbox.area

print "\n", total
print "finished in {} seconds".format(time.time() - t)

fancy_render(r).save("output.png")