Skip to content

Instantly share code, notes, and snippets.

@obiwanus
Created December 19, 2013 08:42
Show Gist options
  • Save obiwanus/8036251 to your computer and use it in GitHub Desktop.
Save obiwanus/8036251 to your computer and use it in GitHub Desktop.
One of the possible solutions to the task in https://neil.fraser.name/news/2013/03/16/
# coding: utf-8
import copy
maze = []
# Read the maze into an array
with open('maze1.txt') as f:
for line in f.readlines():
maze.append([int(i) for i in line.strip()])
# A list of seen points
seen = copy.deepcopy(maze)
MAZE_HEIGHT = len(maze)
MAZE_LENGTH = len(maze[0])
def all_points(array):
for x, row in enumerate(array):
for y, point in enumerate(row):
yield x, y
def get_entry_point():
""" Searches a first unseen point in the maze """
for x, y in all_points(maze):
if not seen[x][y]:
return x, y
return None
# Obtain a list of linked components
components = []
entry_point = get_entry_point()
while entry_point:
component = [entry_point]
queue = [entry_point]
while len(queue):
x, y = queue.pop()
seen[x][y] = 1
possible_neighbors = [(x, y - 1), (x, y + 1), (x - 1, y), (x + 1, y)]
# Exclude all neighbors with coordinates out of range
neighbors = [(x, y) for x, y in possible_neighbors if 0 <= x < MAZE_HEIGHT and 0 <= y < MAZE_LENGTH]
for point in neighbors:
x, y = point
if point not in component and maze[x][y] == 0:
component.append(point)
queue.append(point)
components.append(component)
entry_point = get_entry_point()
def does_not_contact_perimeter(area):
""" Checks if an area touches the borders if the maze """
for x, y in area:
if x == 0 or y == 0 or x == MAZE_HEIGHT - 1 or y == MAZE_LENGTH - 1:
return False
return True
# Exclude all areas that contact the perimeter
# and get the list of enclosed areas accordingly
enclosed_areas = list(filter(does_not_contact_perimeter, components))
print("The amount of enclosed areas: %d" % len(enclosed_areas))
# Figure out the area of the largest one
if len(enclosed_areas):
largest_area = max(enclosed_areas, key=lambda area: len(area))
# Find the key points of the area
def is_point_key(point):
x, y = point
return (x - 2) % 4 == 0 and y % 4 == 0
key_points = list(filter(is_point_key, largest_area))
print("The area of the largest one: %d" % len(key_points))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment