Advent of Code 2016 - Day 18

Day 18: Like a Rogue

Useful Links

‹›

• 2016 Main Page
• My solution code

Concepts and Packages Demonstrated

list comprehensions

Problem Intro

We’re in a room with a tiled floor, where some tiles are safe (.) and some are traps (^). The layout of traps in each row is determined by the tiles in the previous row. Specifically, a tile’s type depends on the three tiles above it: the one directly above (center), and the ones to the left and right.

A new tile is a trap if:

• Its left and center tiles are traps, but its right tile is not.
• Its center and right tiles are traps, but its left tile is not.
• Only its left tile is a trap.
• Only its right tile is a trap.

In any other case, the new tile is safe. Tiles outside the bounds of the row are considered safe.

Our input is the first row of tiles, for example: ..^^.

Part 1

Starting with the map in your puzzle input, in a total of 40 rows (including the starting row), how many safe tiles are there?

This is a simulation problem. We need to generate each new row based on the previous one, and count the safe tiles.

My approach is:

1. Create a function is_trap(position, last_row) that determines if a tile at a given position in the new row should be a trap, based on the last_row. This function will implement the four rules described in the problem.
2. Start with the initial row from the input.
3. Iterate to generate the required number of rows. In each iteration, create the new row by applying the is_trap function to each tile position.
4. As each row is generated, count the number of safe tiles and add it to a running total.

Here’s the is_trap function:

def is_trap(position: int, last_row):
    """
    Position is TRAP if:
        - L and C are traps AND R is safe.
        - C and R are traps AND L is safe.
        - L is trap; C and R are safe.
        - R is trap; C and L are safe.
    """
    tile_l = SAFE if position == 0 else last_row[position-1]
    tile_r = SAFE if position == len(last_row) - 1 else last_row[position+1]
    tile_c = last_row[position]
    
    if tile_l == TRAP and tile_c == TRAP and tile_r == SAFE:
        return True
    
    if tile_r == TRAP and tile_c == TRAP and tile_l == SAFE:
        return True
    
    if tile_l == TRAP and tile_c == SAFE and tile_r == SAFE:
        return True
    
    if tile_r == TRAP and tile_c == SAFE and tile_l == SAFE:
        return True
    
    return False

And the main loop to generate rows and count safe tiles:

def main():
    # ... (read input) ...
    
    rows: list[str] = []
    rows.append(data)   # add first row
    
    for row_num in range(1, ROWS):
        last_row = rows[row_num-1]
        row_data = []
        for tile_posn in range(row_width):
            row_data.append(TRAP) if is_trap(tile_posn, last_row) else row_data.append(SAFE)
            
        rows.append("".join(row_data))
        
    safe_count = sum(row.count(SAFE) for row in rows)
    logging.info(f"Safe tiles count: {safe_count}")

I’m using a list comprehension with sum() to get the total count of safe tiles across all rows.

Part 2

How many safe tiles are there in a total of 400,000 rows?

The logic for Part 2 is exactly the same as for Part 1. The only difference is the number of rows to generate. My code is already set up to handle a variable number of rows, so I just need to change the ROWS constant from 40 to 400,000.

Results

Here’s the output from my solution for 40 rows:

Safe tiles count: 1956
Execution time: 0.0010 seconds

And for 400,000 rows:

Safe tiles count: 19995121
Execution time: 2.5 seconds

The solution is efficient enough to handle the large number of rows in a reasonable time.

‹›