Advent of Code: Day 6

2015-12-06

Source

Part 1: Given a 1000 by 1000 grid of lights and a list of instructions of the form (turn on|turn off|toggle) 5,10 through 15,20, determine how many lights are on.

lights = [
    [False for y in range(1000)]
    for x in range(1000)
]

for line in sys.stdin:
    mode, x1, y1, x2, y2 = re.match('(.*) (\d+),(\d+) through (\d+),(\d+)', line.strip()).groups()
    x1, y1, x2, y2 = map(int, (x1, y1, x2, y2))

    for x in range(x1, x2 + 1):
        for y in range(y1, y2 + 1):
            if mode == 'turn on':
                lights[x][y] = True
            elif mode == 'turn off':
                lights[x][y] = False
            else:
                lights[x][y] = not lights[x][y]

print(sum(
    1 if lights[x][y] else 0
    for x in range(1000)
    for y in range(1000)
))

At first, I was going to use pyparsing to parse the input, but then I decided that it was far too heavy weight for what I was doing. All I needed was regular expressions. After that, it’s just a matter of creating a relatively large two dimensional array and running each instruction.

This one I actually did twice. I was curious if CPU would be significantly faster than memory (it is) to the extent that it would be faster to just calculate each light as we went:

filters = []
for line in sys.stdin:
    m = re.match('(.*) (\d+),(\d+) through (\d+),(\d+)', line.strip())
    filters.append([m.group(1)] + list(map(int, m.groups()[1:])))

def is_on(x, y):
    on = False
    for mode, x1, y1, x2, y2 in filters:
        if x1 <= x <= x2 and y1 <= y <= y2:
            if mode == 'turn on':
                on = True
            elif mode == 'turn off':
                on = False
            else:
                on = not on
    return on

print(sum(
    1 if is_on(x, y) else 0
    for x in range(1000)
    for y in range(1000)
))

I works at least, giving the same answer, but it’s roughly an order of magnitude slower. So it goes.

Part 2: This time turn on is +1, turn off is -1, toggle is +2 and you cannot go below zero for any single cell.

The code doesn’t actually change much from the first solution to the first part, we just initialize to 0 instead of False and tweak the updates. The only interesting one is the turn off case:

elif mode == 'turn off':
    if lights[x][y] > 0:
        lights[x][y] -= 1

Since this is the only case that can be negative, it’s the only one we have to special case.