Created
June 2, 2015 20:10
-
-
Save adusak/3ac462e248be09aa7117 to your computer and use it in GitHub Desktop.
Color maze solver
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
| import copy | |
| import numpy as np | |
| from python.common.line import Line | |
| from python.common.svg import Svg | |
| def load_color_maze(name) -> ({}, str, str, [[str]]): | |
| file = open("labs/" + name, 'r') | |
| text = file.read() | |
| lines = text.split("\n") | |
| rows = [] | |
| for line in lines: | |
| column = [] | |
| for col in line.split(" "): | |
| column.append(col) | |
| rows.append(column) | |
| table = np.array(rows) | |
| coor_str = lambda x, y: str(x) + "," + str(y) | |
| gr = {} | |
| for i in range(len(table)): | |
| for j in range(len(table[i])): | |
| color = table[i, j] | |
| name = coor_str(i, j) | |
| gr[name] = {"color": color, "neighbors": set()} | |
| neighbors = gr[name]["neighbors"] | |
| if i - 1 >= 0: | |
| neighbors.add(coor_str(i - 1, j)) | |
| if i + 1 < len(table): | |
| neighbors.add(coor_str(i + 1, j)) | |
| if j - 1 >= 0: | |
| neighbors.add(coor_str(i, j - 1)) | |
| if j + 1 < len(table[i]): | |
| neighbors.add(coor_str(i, j + 1)) | |
| return gr, coor_str(3, 0), coor_str(0, 3), table | |
| def solve_color_maze(graph, start, end) -> [[str]]: | |
| found_paths = find_paths(graph, start, end) | |
| colors = {} | |
| color_set = set() | |
| for _set in graph.values(): | |
| color_set.add(_set['color']) | |
| for color in color_set: | |
| if color not in ['F', 'n', 'S']: | |
| colors[color] = 0 | |
| result_paths = [] | |
| for found_path in found_paths: | |
| local_colors = copy.deepcopy(colors) | |
| for index in found_path: | |
| node = graph[index] | |
| if node['color'] in local_colors.keys(): | |
| local_colors[node['color']] += 1 | |
| count = None | |
| equal = True | |
| for c_count in local_colors.values(): | |
| if count is None: | |
| count = c_count | |
| if c_count != count: | |
| equal = False | |
| break | |
| if equal: | |
| result_paths.append(found_path) | |
| return result_paths | |
| def draw_graph_svg(table, name="graph", size=500, path=None): | |
| svg = Svg() | |
| one = (size / len(table)) + (len(table)) | |
| current_y = 0 | |
| def color_from_letter(letter): | |
| if letter == 'r': | |
| return 'red' | |
| if letter == 'g': | |
| return 'green' | |
| if letter == 'y': | |
| return 'yellow' | |
| if letter == 'b': | |
| return 'blue' | |
| if letter == 'S': | |
| return 'black' | |
| if letter == 'n': | |
| return 'white' | |
| if letter == 'F': | |
| return 'gold' | |
| for row in table: | |
| y = current_y + one | |
| current_x = 0 | |
| for field in row: | |
| x = current_x + one | |
| svg.add_square((current_x, x), (current_y, y), color_from_letter(field)) | |
| current_x = x | |
| current_y = y | |
| if path is not None: | |
| one_center = one / 2 | |
| start = path[0] | |
| for next in path[1:]: | |
| y1, x1 = tuple(start.split(",")) | |
| x1 = (int(x1) + 1) * one - one_center | |
| y1 = (int(y1) + 1) * one - one_center | |
| y2, x2 = tuple(next.split(",")) | |
| x2 = (int(x2) + 1) * one - one_center | |
| y2 = (int(y2) + 1) * one - one_center | |
| start = next | |
| svg.add_line(Line(x1, y1, x2, y2), (255, 0, 0), 2) | |
| svg.save(name) | |
| def find_paths(graph, start, end, current_path=None) -> [[str]]: | |
| if not current_path: | |
| current_path = [] | |
| current_path = current_path + [start] | |
| if start == end: | |
| return [current_path] | |
| if start not in graph.keys(): | |
| return [] | |
| paths = [] | |
| for node in graph[start]["neighbors"] - set(current_path): | |
| new_paths = find_paths(graph, node, end, current_path) | |
| for new_path in new_paths: | |
| paths.append(new_path) | |
| return paths | |
| g, s, e, t = load_color_maze("color_1.txt") | |
| paths = solve_color_maze(g, s, e) | |
| for path in paths: | |
| draw_graph_svg(t, path=path, name="graph_" + str(paths.index(path))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment