Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Color Map by Moff
from collections import defaultdict
class Graph(object):
COLORS = (1, 2, 3, 4)
def __init__(self):
self.vertices = set()
self.adjacent = defaultdict(set)
def add_edge(self, v1, v2):
self.adjacent[v1].add(v2)
self.adjacent[v2].add(v1)
def adj(self, v):
return self.adjacent[v]
@classmethod
def from_region(cls, m):
graph = cls()
for r, row in enumerate(m):
for c, v in enumerate(row):
graph.vertices.add(v)
for w in cls.neighbours(m, r, c):
if w != v:
graph.add_edge(v, w)
return graph
@staticmethod
def neighbours(m, i, j):
delta = [(0, 1), (0, -1), (1, 0), (-1, 0)]
return [m[ci][cj] for ci, cj in ((i + di, j + dj) for di, dj in delta)
if 0 <= ci < len(m) and 0 <= cj < len(m[0])]
def colorize(self, colors_map, unused):
if not unused:
return colors_map
v = unused[0]
valid_colors = set(self.COLORS)
for w in self.adj(v):
c = colors_map.get(w)
if c is not None:
valid_colors.discard(c)
for c in valid_colors:
d = {v: c}
d.update(colors_map)
res = self.colorize(d, unused[1:])
if res is not None:
return res
def color_map(m):
graph = Graph.from_region(m)
res = graph.colorize(dict(), sorted(graph.vertices))
return [v for k, v in sorted(res.items())]
Sept. 15, 2015
