Advent of Code 2023 - Day 23

README.md

Advent of Code

Day 23 - A Long Walk

Part 1

The first part of this puzzle is a simple DFS solve for longest possible hike with strict rules regarding the path.

The map includes simple tokens indicating paths (.), forest (#), and steep slopes (^, >, v, and <).

The example:

#.##################### #.......#########...### #######.#########.#.### ###.....#.>.>.###.#.### ###v#####.#v#.###.#.### ###.>...#.#.#.....#...# ###v###.#.#.#########.# ###...#.#.#.......#...# #####.#.#.#######.#.### #.....#.#.#.......#...# #.#####.#.#.#########v# #.#...#...#...###...>.# #.#.#v#######v###.###v# #...#.>.#...>.>.#.###.# #####v#.#.###v#.#.###.# #.....#...#...#.#.#...# #.#########.###.#.#.### #...###...#...#...#.### ###.###.#.###v#####v### #...#...#.#.>.>.#.>.### #.###.###.#.###.#.#v### #.....###...###...#...# #####################.#

The goal is to find the longest path without stepping on the same tile twice and you cannot traverse "up" a slope due to fear of "icy conditions".

Part 2

Part Two modifies the rules by treating all slopes as normal paths, allowing free movement in any direction. The challenge remains to find the longest path without stepping onto the same tile twice.

Part 2 Solution

For part two I transformed the grid into a graph. This graph abstracts the grid into nodes representing intersections and edges representing paths between these intersections. Then used a graph traversal algorithm to find the longest path from the start to the end node.

1. The grid is converted into a list of lists for easy manipulation.
2. A graph is created where nodes are the intersections, and edges are paths with their lengths.
3. A traversal algorithm (mixing a bit BFS with DFS here) is applied to the graph to find the longest path.
4. The maximum steps taken to reach the final node are calculated and returned.

example_map.txt

#.#####################
#.......#########...###
#######.#########.#.###
###.....#.>.>.###.#.###
###v#####.#v#.###.#.###
###.>...#.#.#.....#...#
###v###.#.#.#########.#
###...#.#.#.......#...#
#####.#.#.#######.#.###
#.....#.#.#.......#...#
#.#####.#.#.#########v#
#.#...#...#...###...>.#
#.#.#v#######v###.###v#
#...#.>.#...>.>.#.###.#
#####v#.#.###v#.#.###.#
#.....#...#...#.#.#...#
#.#########.###.#.#.###
#...###...#...#...#.###
###.###.#.###v#####v###
#...#...#.#.>.>.#.>.###
#.###.###.#.###.#.#v###
#.....###...###...#...#
#####################.#

main_part_1.py

import sys

sys.setrecursionlimit(10000) # womp womp

def longest_hike(grid):
    rows, cols = len(grid), len(grid[0])
    directions = {'^': (-1, 0), '>': (0, 1), 'v': (1, 0), '<': (0, -1)}

    def is_valid(x, y, visited):
        return 0 <= x < rows and 0 <= y < cols and grid[x][y] != '#' and (x, y) not in visited

    def dfs(x, y, visited):
        if not is_valid(x, y, visited):
            return 0

        visited.add((x, y))
        max_length = 0
        next_steps = []

        if grid[x][y] in directions:
            dx, dy = directions[grid[x][y]]
            next_steps.append((x + dx, y + dy))
        else:
            next_steps = [(x + dx, y + dy) for dx, dy in directions.values()]

        for nx, ny in next_steps:
            if is_valid(nx, ny, visited):
                length = dfs(nx, ny, visited)
                max_length = max(max_length, length)

        visited.remove((x, y))
        return 1 + max_length

    # Find the starting position (S)
    start_x, start_y = next((i, row.index('.')) for i, row in enumerate(grid) if '.' in row)

    # Perform DFS from the starting position
    return dfs(start_x, start_y, set()) - 1  # Subtract 1 to not count the starting position

def main(file_path):
    with open(file_path, 'r') as file:
        grid = [line.strip() for line in file.readlines()]

    longest_hike_length = longest_hike(grid)
    print(f"Longest hike length: {longest_hike_length}")

if __name__ == "__main__":
    import sys
    if len(sys.argv) != 2:
        print("Usage: python script.py <file_path>")
    else:
        main(sys.argv[1])

main_part_2.py

from collections import defaultdict

def create_graph_and_find_longest_path(grid):
    start = (1, 1)  # starting at second tile
    target = (len(grid) - 1, len(grid[0]) - 2)
    graph = defaultdict(list)

    # Create graph where the nodes are the intersections of the grid
    queue = [(start, start, {start, (0, 1)})]
    while queue:
        curr_xy, prev_node, visited = queue.pop()
        if curr_xy == target:
            final_node = prev_node
            final_steps = len(visited) - 1
            continue

        x, y = curr_xy
        neighbors = []
        for i, j in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
            if (i, j) not in visited and grid[i][j] != '#':
                neighbors.append((i, j))

        if len(neighbors) == 1:
            nxt_xy = neighbors.pop()
            queue.append((nxt_xy, prev_node, visited | {nxt_xy}))
        elif len(neighbors) > 1:
            steps = len(visited) - 1
            if (curr_xy, steps) in graph[prev_node]:
                continue
            graph[prev_node].append((curr_xy, steps))
            graph[curr_xy].append((prev_node, steps))
            for nxt_xy in neighbors:
                queue.append((nxt_xy, curr_xy, {curr_xy, nxt_xy}))

    # Traverse graph to find the longest path
    max_steps = 0
    queue = [(start, 0, {start})]
    while queue:
        curr, steps, visited = queue.pop()
        if curr == final_node:
            max_steps = max(steps, max_steps)
            continue
        for nxt, distance in graph[curr]:
            if nxt not in visited:
                queue.append((nxt, steps + distance, visited | {nxt}))

    return max_steps + final_steps

def main(file_path):
    with open(file_path, 'r') as file:
        grid = [list(line.strip()) for line in file.readlines()]

    max_steps = create_graph_and_find_longest_path(grid)
    print(f"Longest hike length: {max_steps}")

if __name__ == "__main__":
    import sys
    if len(sys.argv) != 2:
        print("Usage: python script.py <file_path>")
    else:
        main(sys.argv[1])

map.txt

#.###########################################################################################################################################
#.#.....###.......#...#.....#.......#.........###...#...###...#.........#.....#...#.......#.........#...#...###.......#...#.................#
#.#.###.###.#####.#.#.#.###.#.#####.#.#######.###.#.#.#.###.#.#.#######.#.###.#.#.#.#####.#.#######.#.#.#.#.###.#####.#.#.#.###############.#
#...#...#...#.....#.#.#.#...#...#...#...#.....#...#.#.#...#.#.#...#...#.#.#...#.#.#...#...#.....#...#.#.#.#...#.....#.#.#.#...#.......#.....#
#####.###.###.#####.#.#.#.#####.#.#####.#.#####.###.#.###.#.#.###.#.#.#.#.#.###.#.###.#.#######.#.###.#.#.###.#####.#.#.#.###.#.#####.#.#####
#.....###...#...#...#.#.#.#####.#.###...#...###...#.#...#.#.#...#...#.#.#.#.#...#.#...#...###...#.###.#.#.#...###...#.#.#.#...#.....#.#.....#
#.#########.###.#.###.#.#.#####.#.###.#####.#####.#.###.#.#.###.#####.#.#.#.#.###.#.#####.###.###.###.#.#.#.#####.###.#.#.#.#######.#.#####.#
#.........#.#...#...#.#.#.#.>.>.#.###.#.....#...#.#.#...#...#...###...#...#.#...#.#.....#...#...#.#...#...#...#...###...#...#.......#.......#
#########.#.#.#####.#.#.#.#.#v###.###.#.#####.#.#.#.#.#######.#####.#######.###.#.#####.###.###.#.#.#########.#.#############.###############
#.........#.#...#...#...#.#.#.###...#.#.#...#.#.#.#.#.....#...#...#.......#.#...#.#...#...#...#.#.#.#.......#.#.#.......#...#.........#.....#
#.#########.###.#.#######.#.#.#####.#.#.#.#.#.#.#.#.#####.#.###.#.#######.#.#.###.#.#.###.###.#.#.#.#.#####.#.#.#.#####.#.#.#########.#.###.#
#.#...#...#.###.#.......#.#.#.#.....#.#.#.#.#.#.#.#.#...#.#.###.#.#...#...#.#.#...#.#.###.#...#.#.#...#.....#...#.....#...#...........#...#.#
#.#.#.#.#.#.###v#######.#.#.#.#.#####.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.#.###.#.#.###.#.###.#.###.#.#####.#############.###################.#.#
#.#.#.#.#...###.>.......#...#.#...#...#.#.#.#.#.#.#.#.#...#.>.>.#...#.#.#...#.#.#...#...#.#...#.#.>.>.#.#.......#.....#.....#...#.....###.#.#
#.#.#.#.#######v#############.###.#.###.#.#.#.#.#.#.#.#######v#######.#.#.###.#.#.#####.#.###.#.###v#.#.#.#####.#.#####.###.#.#.#.###.###.#.#
#.#.#.#.#...#...#...#.........###.#.###.#.#.#.#.#.#...#.......#.....#.#.#.>.>.#.#.#...#.#.###.#.###.#...#...#...#.....#.#...#.#.#.#...#...#.#
#.#.#.#.#.#.#.###.#.#.###########.#.###.#.#.#.#.#.#####.#######.###.#.#.###v###.#.#.#.#.#.###.#.###.#######.#.#######.#.#.###.#.#.#.###.###.#
#.#.#.#.#.#.#.....#.#...........#.#...#...#.#.#.#.....#.......#.#...#.#.###...#...#.#.#.#...#.#...#.#...#...#.....###...#.....#...#.....#...#
#.#.#.#.#.#.#######.###########.#.###.#####.#.#.#####.#######.#.#.###.#.#####.#####.#.#.###.#.###.#.#.#.#.#######.#######################.###
#.#.#.#.#.#...###...#...........#.....#.....#.#...#...#...###...#...#...#####...###.#.#.#...#.#...#.#.#...###...#.#...#...#...#.....#.....###
#.#.#.#.#.###.###.###.#################.#####.###.#.###.#.#########.###########.###.#.#.#.###.#.###.#.#######.#.#.#.#.#.#.#.#.#.###.#.#######
#...#.#.#...#.....###.................#.....#...#.#.#...#...#...###.........###...#.#.#.#.#...#...#.#.#.....#.#...#.#...#...#.#...#.#.......#
#####.#.###.#########################.#####.###.#.#.#.#####.#.#.###########.#####.#.#.#.#.#.#####.#.#.#.###.#.#####.#########.###.#.#######.#
#.....#.###...#...###.................#...#.#...#...#.....#.#.#.###...#...#.#.....#.#.#...#.....#.#...#...#.#...###.........#.#...#.......#.#
#.#####.#####.#.#.###.#################.#.#.#.###########.#.#.#.###.#.#.#.#.#.#####.#.#########.#.#######.#.###.###########.#.#.#########.#.#
#.#.....#...#...#...#.........#...#...#.#.#...#...........#...#.....#...#...#.......#...###...#...###.....#.....#...........#...#.....#...#.#
#.#.#####.#.#######.#########.#.#.#.#.#.#.#####.#######################################.###.#.#######.###########.###############.###.#.###.#
#...#...#.#.........#...#####...#...#...#...###.......#.....#...#...###...#...#.........#...#...#...#.........###.................#...#...#.#
#####.#.#.###########.#.###################.#########.#.###.#.#.#.#.###.#.#.#.#.#########.#####.#.#.#########.#####################.#####.#.#
#.....#...#...#...#...#...#...........#.....#...#...#...###...#...#...#.#.#.#.#...#...###.#.....#.#.....#####.....#...........#...#.#####...#
#.#########.#.#.#.#.#####.#.#########.#.#####.#.#.#.#################.#.#.#.#.###v#.#.###.#.#####.#####.#########.#.#########.#.#.#.#########
#.#...#.....#.#.#.#...#...#.........#...#...#.#...#.#...#...###.......#.#...#...>.>.#.#...#.....#.....#.#.........#.........#...#.#...#.....#
#.#.#.#.#####.#.#v###.#.###########.#####.#.#.#####.#.#.#.#.###.#######.#########v###.#.#######.#####.#.#.#################.#####.###.#.###.#
#...#...###...#.#.>.#.#...#.......#.#...#.#.#.....#...#.#.#.#...#...###.....#.....###...#.......#...#.#.#.........#...#...#.....#.....#.#...#
###########.###.#v#.#.###.#.#####.#.#.#.#.#.#####.#####.#.#.#.###.#.#######.#.###########.#######.#.#.#.#########.#.#.#.#.#####.#######.#.###
###...#...#.....#.#.#.#...#...###...#.#.#.#.#...#.....#.#.#.#.#...#.#.......#.....#.....#...#.....#.#.#.#.........#.#.#.#.#.....###...#.#.###
###.#.#.#.#######.#.#.#.#####v#######.#.#.#.#.#.#####.#.#.#.#.#.###.#.###########.#.###.###.#.#####.#.#.#.#########.#.#.#.#v#######.#.#.#.###
#...#...#.........#.#.#.....>.>.#...#.#.#.#.#.#.#...#.#.#.#.#...###.#.........#...#.#...#...#.....#.#.#.#.....#...#.#.#.#.>.#...#...#...#...#
#.#################.#.#######v#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#######v#########.#.###.#.###.#######.#.#.#.#####v#.#.#.#.#.###v#.#.#.#########.#
#...#.............#.#.....#...#...#.#.#.#.#.#.#.#.#.#.#.#.#.#.....>.>.#.....#.#...#.#...#.......#.#...#.....>.>.#.#.#.#.#...#.#.#...#.......#
###.#.###########.#.#####.#.#######.#.#.#.#.#.#.#.#.#.#.#.#.#.#####v#.#.###.#.###.#.###.#######.#.###########v###.#.#.#.#.###.#.###.#.#######
#...#.#.....#.....#...#...#.......#.#.#...#.#.#.#.#...#.#.#...#...#.#.#.###...###.#.###.......#.#.#.........#...#.#.#.#.#...#.#.....#.....###
#.###.#.###.#.#######.#.#########.#.#.#####.#.#.#.#####.#.#####.#.#.#.#.#########.#.#########.#.#.#.#######.###.#.#.#.#.###.#.###########.###
#...#.#...#.#.......#.#.#.........#.#...#...#.#.#.....#...#...#.#...#...#...#####...#.....#...#...#.......#.#...#.#.#...#...#.#.....#...#...#
###.#.###.#.#######.#.#.#.#########.###.#.###.#.#####.#####.#.#.#########.#.#########.###.#.#############.#.#.###.#.#####.###.#.###.#.#.###.#
#...#.#...#.#.......#...#.........#...#.#.#...#...#...#.....#.#.......#...#...###...#...#.#.....#...#.....#.#.###...#...#.....#...#...#.....#
#.###.#.###.#.###################.###.#.#.#.#####.#.###.#####.#######.#.#####.###.#.###.#.#####.#.#.#.#####.#.#######.#.#########.###########
#.....#...#.#...#...###...........###.#.#...#...#...###.....#...#.....#.....#.....#.....#...#...#.#.#.....#.#.......#.#...........#...#...###
#########.#.###.#.#.###.#############.#.#####.#.###########.###.#.#########.###############.#.###.#.#####.#.#######.#.#############.#.#.#.###
#...#.....#.....#.#...#...#.........#...#...#.#...#...#...#.###...#.....#...#.....#.....###...#...#.......#.........#.#...#.......#.#.#.#...#
#.#.#.###########.###.###.#.#######.#####.#.#.###.#.#.#.#.#.#######.###.#.###.###.#.###.#######.#####################.#.#.#.#####.#.#.#.###.#
#.#...#.....#...#.#...###...#...#...#...#.#.#.#...#.#.#.#.#.......#.#...#.#...###...###...#.....#.........#...#...#...#.#.#...#...#.#.#.#...#
#.#####.###.#.#.#.#.#########.#.#.###.#.#.#.#.#.###.#.#.#.#######.#.#.###.#.#############.#.#####.#######.#.#.#.#.#.###.#.###.#.###.#.#.#.###
#.......###...#...#...#.......#...###.#.#.#...#...#.#.#.#.#.......#.#...#.#...#...........#.....#.#.....#.#.#.#.#.#.....#.....#...#.#...#...#
#####################.#.#############.#.#.#######.#.#.#.#.#v#######.###.#.###.#.###############.#.#.###.#.#.#.#.#.###############.#.#######.#
#...........###.......#...........#...#.#.......#.#.#...#.>.>.#.....#...#.....#...............#.#.#...#...#.#.#.#.#...#...#.......#.#.......#
#.#########.###.#################.#.###.#######.#.#.#######v#.#.#####.#######################.#.#.###.#####.#.#.#.#.#.#.#.#.#######.#.#######
#.#...#...#...#.......#...#.......#...#.......#.#.#.#.....#.#.#...#...###...###...#...#.......#...###...#...#...#.#.#.#.#.#.......#.#.......#
#.#.#.#.#.###.#######.#.#.#.#########.#######.#.#.#.#.###.#.#.###.#.#####.#.###.#.#.#.#v###############.#.#######.#.#.#.#.#######.#.#######.#
#...#...#...#.........#.#.#...###...#.......#.#.#.#.#...#.#.#...#.#...#...#.#...#.#.#.>.>.#...#...###...#...#.....#.#.#.#.#.....#...###.....#
###########.###########.#.###.###.#.#######.#.#.#.#.###.#.#.###.#.###.#.###.#.###.#.###v#.#.#.#.#.###.#####.#.#####.#.#.#.#.###.#######.#####
#.........#.....#.....#.#.#...#...#.#...#...#...#...#...#...###...#...#...#.#.#...#.#...#.#.#.#.#...#.#.....#.......#.#.#.#.#...###...#.....#
#.#######.#####.#.###.#.#.#.###.###.#.#.#.###########.#############.#####.#.#.#.###.#.###.#.#.#.###.#.#.#############.#.#.#.#.#####.#.#####.#
#.......#.......#.#...#.#.#...#...#.#.#...#####...###.............#.....#.#.#.#.#...#.###.#.#.#.#...#.#...#...........#.#...#.#...#.#.#.....#
#######.#########.#v###.#.###v###.#.#.#########.#.###############.#####.#.#.#.#.#.###.###.#.#.#.#.###v###.#.###########.#####.#.#.#.#.#.#####
#.......#.......#.#.>.#.#...>.>.#.#.#.###.......#.......#.........#.....#.#.#.#...###...#.#.#...#...>.>.#.#.###...#...#...#...#.#.#.#.#...###
#.#######.#####.#.#v#.#.#####v#.#.#.#.###.#############.#.#########.#####.#.#.#########.#.#.#########v#.#.#.###.#.#.#.###.#.###.#.#.#.###v###
#.....#...#...#...#.#.#...#...#...#.#...#.#...#...#...#...#.......#...#...#...#...#...#.#.#.#.........#...#...#.#.#.#.#...#.#...#.#.#.#.>.###
#####.#.###.#.#####.#.###.#.#######.###.#.#.#.#.#.#.#.#####.#####.###.#.#######.#.#.#.#.#.#.#.###############.#.#.#.#.#.###.#.###.#.#.#.#v###
#...#...###.#.......#.....#.......#.....#...#...#...#.......#...#.###...###.....#...#...#...#.#...#...###.....#.#.#.#...###...#...#.#...#...#
#.#.#######.#####################.###########################.#.#.#########.#################.#.#.#.#.###.#####.#.#.###########.###.#######.#
#.#.###...#...............#...#...#.........#.................#...#...#...#.................#.#.#...#...#.......#...#...#.....#.....#.....#.#
#.#.###.#.###############.#.#.#.###.#######.#.#####################.#.#.#.#################.#.#.#######.#############.#.#.###.#######.###.#.#
#.#.#...#...#...#.........#.#.#.###.#.......#...............#.......#.#.#.........#.........#...#...###.....#.....###.#.#.#...#...#...#...#.#
#.#.#.#####.#.#.#v#########.#.#v###.#.#####################.#.#######.#.#########.#.#############.#.#######.#.###.###.#.#.#.###.#.#v###.###.#
#.#.#.#...#...#.#.>...#...#.#.>.>...#.###...#.....#.........#.....#...#.........#...#.........#...#.........#...#...#.#...#.#...#.>.###...#.#
#.#.#.#.#.#####.#v###.#.#.#.###v#####.###.#.#.###.#.#############.#.###########.#####.#######.#.###############.###.#.#####.#.#####v#####.#.#
#.#.#...#...#...#...#.#.#.#.###.....#...#.#.#.#...#.....#...###...#.#...#.....#.....#.#.......#.#.........#####...#.#...###...#...#...#...#.#
#.#.#######.#.#####.#.#.#.#.#######.###.#.#.#.#.#######.#.#.###.###.#.#.#.###.#####.#.#.#######.#.#######.#######.#.###.#######.#.###.#.###.#
#.#.#...#...#.......#...#...#.......###.#.#.#.#...#.....#.#...#.#...#.#.#.#...#...#.#.#.......#.#...#.....#.....#.#.#...#.......#...#.#...#.#
#.#.#.#.#.###################.#########.#.#.#.###.#.#####.###.#.#.###.#.#.#.###.#.#v#.#######.#.###.#.#####.###.#.#.#.###.#########.#.###.#.#
#.#...#.#...#.....#...#...#...#...#...#...#.#.#...#.....#.#...#.#.###.#.#.#.#...#.>.>.#.......#.....#.....#...#...#.#.#...#.......#...#...#.#
#.#####.###.#.###.#.#.#.#.#.###.#.#.#.#####.#.#.#######.#.#.###.#.###.#.#.#.#.#####v###.#################.###.#####.#.#.###.#####.#####.###.#
#.#...#.###...###...#...#.#.....#...#...#...#.#.#...#...#.#.....#...#.#.#.#.#.#####.#...###.....#...#####...#.....#.#.#.#...#.....#...#...#.#
#.#.#.#.#################.#############.#.###.#.#.#.#.###.#########.#.#.#.#.#.#####.#.#####.###.#.#.#######.#####.#.#.#.#.###.#####.#.###.#.#
#...#.#...................#.............#...#.#...#.#.###.###...#...#.#.#.#.#.#.....#.....#.#...#.#.###...#.###...#...#.#.#...#...#.#.###...#
#####.#####################.###############.#.#####.#.###.###.#.#.###.#.#.#.#.#.#########.#.#.###.#.###.#.#v###.#######.#.#.###.#.#.#.#######
#...#.............#...#...#.........#...###...###...#.#...#...#...#...#...#...#.......#...#.#...#.#.....#.>.>.#.......#...#.....#...#.......#
#.#.#############.#.#.#.#.#########.#.#.#########.###v#.###.#######.#################.#.###.###.#.#########v#.#######.#####################.#
#.#.....#...#...#...#...#...###.....#.#.......#...#.>.>.###...#...#.....#.............#...#.#...#...#.......#...#...#...#...................#
#.#####.#.#.#.#.###########.###.#####.#######.#.###.#v#######.#.#.#####.#.###############.#.#.#####.#.#########.#.#.###.#.###################
#.#...#...#...#.....#.....#...#.#.....#.......#.....#...#...#...#.#...#.#.......#...#...#.#.#.#...#.#.#...#...#...#.#...#.........#.........#
#.#.#.#############.#.###.###.#.#.#####.###############.#.#.#####.#.#.#.#######.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#####.#.###########.#.#######.#
#.#.#.....#.......#...###.#...#...#...#...........#...#...#.....#...#...###.....#.#...#.#.#.#.#.#.#.#.#.#...#.....#.#...#.......#...#.......#
#.#.#####.#.#####.#######.#.#######.#.###########.#.#.#########.###########.#####.#####.#.#.#.#.#.#.#.#.#########.#.###.#.#####.#####.#######
#.#.#.....#.#.....###...#...#...#...#.............#.#...........###...#...#.......#.....#.#.#.#.#...#...#.....#...#.....#.....#.....#.....###
#.#.#.#####.#.#######.#.#####.#.#.#################.###############.#.#.#.#########.#####.#.#.#.#########.###.#.#############.#####.#####.###
#...#.......#.........#.....#.#.#...#...#.........#.#.........#...#.#.#.#.#...#...#.#...#...#.#...#.......###...#.......#####.....#.#...#...#
###########################.#.#.###.#.#.#.#######.#.#.#######.#.#.#.#.#.#.#.#.#.#.#.#.#.#####.###.#.#############.#####.#########.#.#.#.###.#
###...................#.....#.#...#...#...#...#...#...#.......#.#.#.#.#.#.#.#.#.#.#.#.#.#...#.....#...........###.....#...#.......#...#.....#
###.#################.#.#####.###.#########.#.#.#######.#######.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#################.#######.###.#.#################
#...#.....#.........#.#.#...#.#...#...#.....#...###.....#.....#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...#####...#...#.....###...#.#...#.............#
#.###.###.#.#######.#.#.#.#.#.#.###.#.#.###########.#####.###.#.#.#.#.#.#.#.#.#.#.#v#.#.#.#.#.#.#####.#.#.#.#####.#####.#.###.#.###########.#
#.....###...###.....#...#.#.#.#...#.#.#...........#.......#...#.#.#.#.#.#.#.#.#.#.>.>.#...#...#...#...#...#.......#.....#...#...#...........#
###############.#########.#.#.###.#.#.###########.#########.###.#.#.#.#.#.#.#.#.###v#############.#.###############.#######.#####.###########
#...............#.....###.#.#...#...#.#...........#...#.....#...#.#.#...#.#.#.#.###.....#.........#...#.......#...#...#...#.......#...###...#
#.###############.###.###.#.###.#####.#.###########.#.#.#####.###.#.#####.#.#.#.#######.#.###########.#.#####.#.#.###.#.#.#########.#.###.#.#
#.#.............#...#...#.#.#...#.....#.......#...#.#.#.#...#...#.#.#.....#.#.#.....#...#.........###...#.....#.#.#...#.#.#...#...#.#.....#.#
#.#.###########v###.###.#.#.#.###.###########.#.#.#.#.#v#.#.###.#.#.#.#####.#.#####.#.###########.#######.#####.#.#.###.#.#.#.#.#.#.#######.#
#.#.#.........#.>.#.#...#.#.#...#.#.......#...#.#.#.#.>.>.#...#.#.#.#.....#.#.......#...#.........#...#...#...#.#.#.....#...#...#...#.......#
#.#.#.#######.#v#.#.#.###.#.###.#.#.#####.#.###.#.#.###v#####.#.#.#.#####.#.###########.#.#########.#.#.###.#.#.#.###################.#######
#.#.#.......#...#...#...#.#.###.#.#.#.....#.###.#...#...#...#...#...#.....#.###...#...#.#...###...#.#.#...#.#.#.#.#...#...###...#...#.......#
#.#.#######.###########.#.#.###.#.#.#.#####v###.#####.###.#.#########.#####.###.#.#.#.#.###.###.#.#.#.###v#.#.#.#.#.#.#.#.###v#.#.#.#######.#
#...###...#.#.........#.#.#.#...#.#.#.#...>.>.#.#...#.....#.......###.......#...#...#...###.....#.#.#.#.>.>.#.#.#.#.#.#.#...>.#.#.#.#...#...#
#######.#.#.#.#######.#.#.#.#.###.#.#.#.###v#.#.#.#.#############.###########.###################.#.#.#.#v###.#.#.#.#.#.#####v#.#.#.#.#.#.###
#.......#.#...#...#...#.#.#.#.###...#...#...#.#.#.#...............#...#...###.......#.........#...#.#...#...#.#.#.#.#.#...#...#...#...#...###
#.#######.#####.#.#.###.#.#.#.###########.###.#.#.#################.#.#.#.#########.#.#######.#.###.#######.#.#.#.#.#.###.#.#################
#.......#.......#...###...#.#.#...........###...#.................#.#.#.#.#...#...#.#.#.......#...#.....#...#...#...#...#.#.......#.....#...#
#######.###################.#.#.#################################.#.#.#.#.#.#.#.#.#.#.#.#########.#####.#.#############.#.#######.#.###.#.#.#
#...###.....#...........###...#.........#...#.....#...............#.#.#.#...#...#.#...#.........#.......#.............#...#...#...#.#...#.#.#
#.#.#######.#.#########.###############.#.#.#.###.#.###############.#.#.#########.#############.#####################.#####.#.#.###.#.###.#.#
#.#.......#.#.#.........#...#...#.....#...#...#...#.........#.......#.#...#.......###...........###.....#.............###...#.#.....#.....#.#
#.#######.#.#.#.#########.#.#.#.#.###.#########.###########.#.#######.###.#.#########.#############.###.#.###############.###.#############.#
#.......#...#.#.....###...#...#.#...#.#.........#...........#.......#.###.#.#...#...#...###...#...#.#...#...........#...#...#.#.............#
#######.#####.#####.###.#######.###.#.#v#########.#################.#.###.#.#.#.#.#.###v###.#.#.#.#.#.#############.#.#.###.#.#.#############
#.......#.....#...#...#.#.....#.....#.>.>...#...#.......#...#...#...#.#...#.#.#.#.#.#.>.>.#.#.#.#.#.#...#...#.......#.#.#...#.#.....#...#...#
#.#######.#####.#.###.#.#.###.#############.#.#.#######.#.#.#.#.#.###.#.###.#.#.#.#.#.###.#.#.#.#.#.###.#.#.#.#######.#.#.###.#####.#.#.#.#.#
#.#...#...#.....#.....#...###...........###.#.#.###...#.#.#.#.#.#.#...#.#...#.#.#.#.#...#.#.#.#.#.#.#...#.#.#...#...#.#.#...#...#...#.#.#.#.#
#.#.#.#.###.###########################.###.#.#.###.#.#v#.#.#.#.#.#.###.#.###.#.#.#.###.#.#.#.#.#.#.#.###.#.###v#.#.#.#.###.###.#.###.#.#.#.#
#.#.#.#.#...#...#.....###...#...#...#...#...#.#...#.#.>.>.#.#.#.#.#.#...#...#.#...#.#...#.#.#...#.#.#.#...#.#.>.>.#.#.#.###.#...#.....#.#.#.#
#.#.#.#.#.###.#.#.###.###.#.#.#.#.#.#.###.###.###.#.#######.#.#.#.#.#.#####.#.#####.#.###.#.#####.#.#.#.###.#.#####.#.#.###.#.#########v#.#.#
#.#.#...#.....#...#...#...#.#.#.#.#...###...#.###.#.#####...#.#...#.#...#...#...#...#...#.#.###...#.#.#.#...#...###.#.#.#...#...#...#.>.#.#.#
#.#.###############.###.###.#.#.#.#########.#.###.#.#####.###.#####.###.#.#####.#.#####.#.#.###.###.#.#.#.#####.###.#.#.#.#####.#.#.#.#v#.#.#
#.#.#...............#...#...#.#.#.....#.....#.#...#.....#...#...###...#.#.#...#.#...#...#...#...#...#...#...#...#...#.#.#.....#...#...#...#.#
#.#.#.###############.###.###.#.#####.#.#####.#.#######.###.###.#####.#.#.#.#.#.###.#.#######.###.#########.#.###.###.#.#####.#############.#
#...#.......#...#...#.###.#...#.#.....#.#...#.#...#.....###.#...#.....#.#.#.#...#...#.....#...#...#.........#...#...#.#.#...#.....#.........#
###########.#.#.#.#.#.###.#.###.#.#####.#.#.#.###.#.#######.#.###.#####.#.#.#####.#######.#.###.###.###########.###.#.#.#.#.#####.#.#########
#...........#.#.#.#.#...#.#.###.#...#...#.#.#.#...#.......#.#.#...#...#.#.#.#.....#...#...#...#...#.#.....#.....#...#.#.#.#.#...#.#...#.....#
#.###########.#.#.#.###.#.#.###.###.#.###.#.#.#.#########.#.#.#.###.#.#.#.#.#.#####.#.#.#####.###.#.#.###.#.#####.###.#.#.#.#.#.#.###.#.###.#
#.............#...#.....#...###.....#.....#...#...........#...#.....#...#...#.......#...#####.....#...###...#####.....#...#...#...###...###.#
###########################################################################################################################################.#