# Learning Python with Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python

# Advent of Code 2015 - Day 18

## 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:

## 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:

# 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()

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:
else:
if (len(on_neighbours) == 3):

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 == '#'):

return on_lights
``````

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()
``````

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.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:
else:
if (len(on_neighbours) == 3):

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.

``````    # 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.