Created
April 15, 2018 16:09
-
-
Save vladris/c283de5d8a3289303c7aca258e9cbdb1 to your computer and use it in GitHub Desktop.
Python solution for Kami 2 puzzle
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
class Graph: | |
def __init__(self, nodes=dict(), edges=[]): | |
self.nodes = nodes | |
self.edges = edges | |
self.colors = len(set(nodes.values())) | |
def connected(self, node): | |
for edge in self.edges: | |
if edge[0] == node: | |
yield edge[1] | |
elif edge[1] == node: | |
yield edge[0] | |
def color(self, node, color): | |
to_merge = [node] | |
to_merge += [n for n in self.connected(node) if self.nodes[n] == color] | |
new_n = min(to_merge) | |
new_nodes = { new_n: color } | |
for node in self.nodes: | |
if node not in to_merge: | |
new_nodes[node] = self.nodes[node] | |
new_edges = set() | |
for edge in self.edges: | |
if edge[0] in to_merge and edge[1] in to_merge: | |
continue | |
elif edge[0] in to_merge: | |
new_edges.add(tuple(sorted((new_n, edge[1])))) | |
elif edge[1] in to_merge: | |
new_edges.add(tuple(sorted((edge[0], new_n)))) | |
else: | |
new_edges.add(edge) | |
return Graph(new_nodes, new_edges) | |
def solve(graph, steps, n): | |
if len(graph.nodes) == 1: | |
print(steps) | |
exit() | |
if n == 0: | |
return | |
if graph.colors > n + 1: | |
return | |
for node in graph.nodes: | |
colors = list(set([graph.nodes[n] for n in graph.connected(node)])) | |
for color in colors: | |
g = graph.color(node, color) | |
solve(g, steps + [(node, color)], n - 1) | |
g = Graph( | |
nodes = { | |
1: "Purple", | |
2: "Yellow", | |
3: "Red", | |
4: "Yellow", | |
5: "White", | |
6: "Purple", | |
7: "Yellow", | |
8: "Purple", | |
9: "Yellow", | |
10: "Red", | |
11: "Purple", | |
12: "White", | |
13: "Purple", | |
14: "Purple", | |
15: "White", | |
16: "Yellow", | |
17: "Red", | |
18: "Purple", | |
}, | |
edges = [ | |
(1, 2), | |
(1, 4), | |
(2, 3), | |
(2, 5), | |
(2, 6), | |
(3, 6), | |
(3, 7), | |
(4, 5), | |
(4, 8), | |
(5, 6), | |
(5, 8), | |
(6, 7), | |
(6, 9), | |
(7, 9), | |
(7, 12), | |
(8, 9), | |
(8, 10), | |
(9, 11), | |
(9, 12), | |
(10, 11), | |
(10, 13), | |
(10, 15), | |
(12, 13), | |
(12, 14), | |
(12, 16), | |
(13, 15), | |
(13, 16), | |
(13, 18), | |
(15, 18), | |
(16, 17), | |
(16, 18), | |
(17, 18), | |
]) | |
solve(g, [], 5) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
http://vladris.com/blog/2018/04/15/kami-2.html