Advent of Code 2015 - Day 18

Day 18: Like a GIF For Your Yard

Useful Links

‹›

• 2015 Main Page
• My solution code

Concepts and Packages Demonstrated

SetsReusable Point classtuple unpackingNumPy

Page Navigation

• Problem Intro
• Point class solution
  • Part 1
  • Part 2
  • Results
• NumPy solution
  • Part 1
  • Part 2
  • Results
• Results

Problem Intro

A bit like the problem for Day 6, we have a grid of lights to work with. This time, a 100x100 grid. We need to animate this grid of lights, by turning lights on and off according to instructions.

We’re given sample data like this:

.#.#.#
...##.
#....#
..#...
#.#..#
####..

• # means the light is on.
• . means the light is off.

Now we create an animation, by changing which lights are on and off over a number of steps. With each step:

• Each light’s next state (on or off) is dependent on its current state, and the state of the neighbouring eight lights.
• If a light is missing neighbours (because the light is on an edge), then the missing neighbours count as off.
• A light which is on stays on when 2 or 3 neighbors are on, and turns off otherwise.
• A light which is off turns on if exactly 3 neighbors are on, and stays off otherwise.
• All the lights change state at the same time.

Thus, this challenge is very much an implementation of Conway’s Game of Life.

As with Day 6, I’ve sold this using two solutions:

1. Using a Point class
2. Using NumPy

Point Class Solution

Part 1

How many lights are on after 100 steps?

The solution approach here is pretty simple:

• Read in the input grid
• Using the grid dimensions, create a set that contains a Point for all (x,y) coordinates in the grid. We’ll call this all_lights.
• Using the input grid data, create a separate set of Points, containing only lights that are currently on. We call this set: on_lights.
• Now loop through 100 iterations. For each iteration:
  • Loop through every light in the grid.
  • Find the neighbours for each light, and return as a set.
  • Determine how many neighbours are currently turned on, by finding the intersection between the neighbours, and the on_lights.
  • Apply the rules to determine whether the current line should be turned on or off.

Here’s the code that achieves this:

import os
import time
from itertools import product
from common.type_defs import Point

SCRIPT_DIR = os.path.dirname(__file__) 
INPUT_FILE = "input/input.txt"
SAMPLE_INPUT_FILE = "input/sample_input.txt"

ITERATIONS = 100

def main():
    # input_file = os.path.join(SCRIPT_DIR, SAMPLE_INPUT_FILE)
    input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
    with open(input_file, mode="rt") as f:
        data = f.read().splitlines()

    # Get all light coordinates by obtaining cartesian product of all x coords with all y coords
    lights_length = len(data[0])
    lights_height = len(data)
    
    all_lights = {Point(*point) 
                  for point in set(product(range(lights_length), range(lights_height)))}

    on_lights = init_state(data)

    # Part 1
    final_on_lights = process_iterations(all_lights, on_lights.copy(), ITERATIONS)
    print(f"Part 1, after {ITERATIONS} iterations, there are {len(final_on_lights)} turned on.")

def process_iterations(all_lights: set[Point], 
                       on_lights: set[Point], 
                       iterations: int) -> set[Point]:
    """ 
    Carry out Conway-like rules for all lights in the all_lights set.

    Args:
        all_lights (Set[Point]): A set of all coords, in an array of width x and height y
        on_lights (Set[Point]): A set containing only coords of lights that are on
        iterations (int): The number of iterations to process the Conway-like rules

    Returns:
        Set[Point]: The coords of lights that are 'on', following specified iterations
    """

    for _ in range(iterations):
        on_lights_to_remove = set()
        on_lights_to_add = set()
        
        for light in all_lights:
            neighbours = light.neighbours()
            on_neighbours = neighbours.intersection(on_lights)
            
            if (light in on_lights):
                if len(on_neighbours) < 2 or len(on_neighbours) > 3:
                    on_lights_to_remove.add(light)
            else:
                if (len(on_neighbours) == 3):
                    on_lights_to_add.add(light)
        
        on_lights.update(on_lights_to_add)
        on_lights.difference_update(on_lights_to_remove)

    return on_lights
    
def init_state(data: list[str]) -> set[Point]:
    on_lights = set()

    for y, line in enumerate(data):
        for x, char in enumerate(line):
            if (char == '#'):
                on_lights.add(Point(x, y))

    return on_lights

Some notes about this code:

First, I have imported my reusable Point class, which is defined in the module common.type_defs. This Point class already knows how to deterine its neighbours, i.e. the Points that it is adjacent to.

Next, I have used a set comprehension:

    all_lights = {Point(*point) 
                  for point in set(product(range(lights_length), range(lights_height)))}

Imagine our grid was only 3x3. In this case, the two ranges would both be [0, 1, 2]. Applying itertools.product() against these two ranges results in all the possible combinations by taking a value from each range, returned as tuples. I.e.

(0, 0)
(0, 1)
(0, 2)
(1, 0)
(1, 1)
(1, 2)
(2, 0)
(2, 1)
(2, 2)

Thus, we can use this to give us the coordinates of every point in the grid. We then turn each of these tuples into a Point, by creating a Point from each unpacked tuple. This is how we create a Point for every coordinate in the grid.

Next, we determine which lights are currently on by looping through each row (y value) and each column (x value) in the grid, and creating a new set of Point objects, containing only points where the light is on, i.e. where the value in the grid is #.

Now that we have a set of all_lights and a set of on_lights, it is trivial to:

• Get the neighbours of each light, as a set.
• Use set algebra to determine which of these neighbours is on.
• Count the number of on neighbours for each Point.
• Determine if the Point should be on or off accordingly.

Part 2

We’re told that four lights, one in each corner, are stuck on and can’t be turned off.

With the four corners stuck in the on state, how many lights are on after 100 steps?

This requires some fairly trivial changes.

First, we need to identify the four corners:

    # Part 2
    corner_lights = set()
    corner_lights.add(Point(0, 0))
    corner_lights.add(Point(lights_length-1, 0))
    corner_lights.add(Point(0, lights_height-1))
    corner_lights.add(Point(lights_length-1, lights_height-1))

Then, we need to update our process_iterations() function, so that it knows to always keep the corners on. I’ve done this by adding an optional parameter, called fixed_lights. It expects a set of the Points that need to stay on. If we pass the corners to the function using this parameter, then we simply always add these fixed_lights to our set of on_lights. And when we’re processing each light in turn, if the light is one of our fixed_lights, we simply do nothing.

def process_iterations(all_lights: set[Point], 
                       on_lights: set[Point], 
                       iterations: int,
                       fixed_lights: set[Point] = None) -> set[Point]:
    """ 
    Carry out Conway-like rules for all lights in the all_lights set.

    Args:
        all_lights (Set[Point]): A set of all coords, in an array of width x and height y
        on_lights (Set[Point]): A set containing only coords of lights that are on
        iterations (int): The number of iterations to process the Conway-like rules
        fixed_lights (Set[Point], optional): Coords of lights that will always be on. Defaults to empty set().

    Returns:
        Set[Point]: The coords of lights that are 'on', following specified iterations
    """

    if not fixed_lights:
        fixed_lights = set()
        
    for _ in range(iterations):
        on_lights_to_remove = set()
        on_lights_to_add = set()

        on_lights.update(fixed_lights)
        
        for light in all_lights:
            neighbours = light.neighbours()
            on_neighbours = neighbours.intersection(on_lights)
            
            if (light in fixed_lights):
                pass   # do nothing
            elif (light in on_lights):
                if len(on_neighbours) < 2 or len(on_neighbours) > 3:
                    on_lights_to_remove.add(light)
            else:
                if (len(on_neighbours) == 3):
                    on_lights_to_add.add(light)
        
        on_lights.update(on_lights_to_add)
        on_lights.difference_update(on_lights_to_remove)

        # print(f"Iteration {_+1}: {len(on_lights)}")

    return on_lights

Finally, we run Part 2 like this:

    final_on_lights = process_iterations(all_lights, on_lights.copy(), ITERATIONS, corner_lights)
    print(f"Part 2, after {ITERATIONS} iterations, there are {len(final_on_lights)} turned on.")

Results

The output looks like this:

Part 1, after 100 iterations, there are 821 turned on.
Part 2, after 100 iterations, there are 886 turned on.
Execution time: 14.4660 seconds

It works, but it’s not particularly quick!

NumPy Solution

Part 1

How many lights are on after 100 steps?

Since we’re working with a fixed grid of data, and we want to be counting things in that grid, then NumPy is a good library to use. It can save us a lot of coding.

First, let’s read the data:

    # inport text as a numpy grid, setting each field to 1 char wide
    grid = np.genfromtxt(input_file, dtype='U1', comments=None, delimiter=1)
    grid[grid == '#'] = 1
    grid[grid == '.'] = 0
    grid = grid.astype(int)

The code above reads the text file and converts it to a NumPy array. We set the dtype to U1, meaning that the data type for each element will be a single character string. We also set comments=None, because - by default - this method the # character as the beginning of a comment. But here, we want to treat # as legitimate data.

The next two lines convert all # to 1, and all . to 0. This will be useful when we want to sum values later. Then, we convert the dtype of the array to int. This allows us to work with the 0 and 1 as integer values, rather than as string representations.

Now let’s add a function to count the on neighbours of any given element in the grid:

def count_neighbors(grid, x, y):
    """ Count the _on_ neighbours around the light at coords (x, y). """
    min_x, max_x = max(0, x-1), min(grid.shape[0], x+2)
    min_y, max_y = max(0, y-1), min(grid.shape[1], y+2)
    return np.sum(grid[min_x:max_x, min_y:max_y]) - grid[x, y]

The min_x, max_x and min_y, max_y values are used to return a 3x3 grid of elements around each coordinate. In both the x dimension and the y dimension we:

• For min, we get the value that is one less than the current coordinate, or 0, if we go out of the grid.
• For max, we get the value that is two more than the current coordinate, or the length of the dimension, if we go out of the grid. (Here, we want the exclusive max.)

Finally, grid[min_x:max_x, min_y:max_y] uses slice notation to return the 3x3 grid of elements around the current coordinate. We use np.sum() to add up the values of these elements (remember that on elements have a value of 1, whilst off elements have a value of 0). And finally, we need to remove the value of the coordinate at the centre itself, since this coordinate is not itself a neighbour.

Next, add a function that applies the rules to obtain the next state:

def update_grid(grid):
    new_grid = grid.copy()
    for x in range(grid.shape[0]):
        for y in range(grid.shape[1]):
            count = count_neighbors(grid, x, y)
            if grid[x, y] == 1 and count not in [2, 3]:
                new_grid[x, y] = 0
            elif grid[x, y] == 0 and count == 3:
                new_grid[x, y] = 1
                
    return new_grid

Finally we’re ready to perform 100 iterations:

    # Part 1
    p1_grid = grid.copy()
    for _ in range(ITERATIONS):
        p1_grid = update_grid(p1_grid)

    print(f"Part 1: {np.sum(p1_grid)}")

Part 2

With the four corners stuck in the on state, how many lights are on after 100 steps?

Here we only need a couple of trivial changes. First, we need to identify the coordinates of the four corners, set the values of the corners to 1, and pass these coordinates into the update_grid() function:

    # Part 2
    corners = [(0, 0), 
               (0, grid.shape[1]-1), 
               (grid.shape[0]-1, 0), 
               (grid.shape[0]-1, grid.shape[1]-1)]
    for x, y in corners:
        grid[x, y] = 1
        
    for _ in range(ITERATIONS):
        grid = update_grid(grid, corners)

Then we need to modify the update_grid() function so that it optionally takes a list of coordinates that need to stay turned on:

def update_grid(grid, fixed_lights = None):
    new_grid = grid.copy()
    for x in range(grid.shape[0]):
        for y in range(grid.shape[1]):
            if fixed_lights:
                if (x, y) in fixed_lights:
                    continue
            count = count_neighbors(grid, x, y)
            if grid[x, y] == 1 and count not in [2, 3]:
                new_grid[x, y] = 0
            elif grid[x, y] == 0 and count == 3:
                new_grid[x, y] = 1
                
    return new_grid

You’ll see that as we’re looping through all the x, y coordinates, the loop skips to the next iteration of the inner loop, if the coordinate is one of the corners. I.e. if we’re on a corner, then do nothing and move on to the next coordinate.

Results

Part 1: 821
Part 2: 886
Execution time: 5.2444 seconds

You can see that this solution runs considerably faster, is easier to read, and requires a lot less code.

‹›