Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Color Map by martin_b
# the good thing is this algorithm must work, it is mathematically proven :-)
from collections import defaultdict
def color_map(region):
dim_r, dim_c = len(region), len(region[0])
# create dictionary of countries with its neighbors in a set
countries = defaultdict(set)
for r in range(dim_r):
for c in range(dim_c):
c1 = region[r][c]
if c < dim_c - 1:
c2 = region[r][c + 1]
if c1 != c2:
countries[c1].add(c2)
countries[c2].add(c1)
if r < dim_r - 1:
c2 = region[r + 1][c]
if c1 != c2:
countries[c1].add(c2)
countries[c2].add(c1)
# handle the special case that there is only one country
if not countries:
return [1]
# start with all colors for all countries
colors = {c: set([1, 2, 3, 4]) for c in countries}
for c in countries:
# pick one color for the country
color = colors[c].pop()
colors[c] = color
# remove this color from all country neighbors
for c1 in countries[c]:
if type(colors[c1]) is set:
colors[c1].discard(color)
# extract the colors in the specified format
return [colors[c] for c in sorted(colors.keys())]
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
NEIGHS = ((-1, 0), (1, 0), (0, 1), (0, -1))
COLORS = (1, 2, 3, 4)
ERROR_NOT_FOUND = "Didn't find a color for the country {}"
ERROR_WRONG_COLOR = "I don't know about the color {}"
def checker(func, region):
user_result = func(region)
if not isinstance(user_result, (tuple, list)):
print("The result must be a tuple or a list")
return False
country_set = set()
for i, row in enumerate(region):
for j, cell in enumerate(row):
country_set.add(cell)
neighbours = []
if j < len(row) - 1:
neighbours.append(region[i][j + 1])
if i < len(region) - 1:
neighbours.append(region[i + 1][j])
try:
cell_color = user_result[cell]
except IndexError:
print(ERROR_NOT_FOUND.format(cell))
return False
if cell_color not in COLORS:
print(ERROR_WRONG_COLOR.format(cell_color))
return False
for n in neighbours:
try:
n_color = user_result[n]
except IndexError:
print(ERROR_NOT_FOUND.format(n))
return False
if cell != n and cell_color == n_color:
print("Same color neighbours.")
return False
if len(country_set) != len(user_result):
print("Excess colors in the result")
return False
return True
assert checker(color_map, (
(0, 0, 0),
(0, 1, 1),
(0, 0, 2),
)), "Small"
assert checker(color_map, (
(0, 0, 2, 3),
(0, 1, 2, 3),
(0, 1, 1, 3),
(0, 0, 0, 0),
)), "4X4"
assert checker(color_map, (
(1, 1, 1, 2, 1, 1),
(1, 1, 1, 1, 1, 1),
(1, 1, 0, 1, 1, 1),
(1, 0, 0, 0, 1, 1),
(1, 1, 0, 4, 3, 1),
(1, 1, 1, 3, 3, 3),
(1, 1, 1, 1, 3, 5),
)), "6 pack"
Sept. 9, 2016
Comments:
