Skip to content

Instantly share code, notes, and snippets.

@vladris vladris/kami.py
Created Apr 15, 2018

Embed
What would you like to do?
Python solution for Kami 2 puzzle
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)
@vladris

This comment has been minimized.

Copy link
Owner Author

vladris commented Apr 15, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.