Created
December 19, 2013 08:42
-
-
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/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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