Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Commented recursive approach solution in Clear category for Color Map by Ulukai85
def check_neighbors(region, self, cell):
# For a cell in the region, check the neighboring cells for their
# 'land', compare and return all neighbors of the cell.
i, j = cell
neighbors = set()
cell_summands = ((-1, 0), (1, 0), (0, -1), (0, 1))
for x, y in cell_summands:
if (0 <= i + x < len(region)) and (0 <= j + y < len(region[0])):
land = region[i + x][j + y]
if land != self:
neighbors.add(land)
return neighbors
def different_colors(current_land, sequence, map_dict):
# Check the already sequenced neighbors of the current land for their color
# and return True if all already sequenced neighbors have different colors.
area = map_dict[current_land]['neighbors'] & set(range(len(sequence)))
return all(sequence[x] != sequence[-1] for x in area)
def coloring(still_to_paint, sequence, map_dict):
# Try different colors for current_land. If color is different from
# neighbors, continue recursively. If the last land is reached and all
# checks out, return the found color sequence.
current_land, still_to_paint = still_to_paint[0], still_to_paint[1:]
for color in (1, 2, 3, 4):
if different_colors(current_land, sequence + [color], map_dict):
if not still_to_paint:
return sequence + [color]
else:
return coloring(still_to_paint, sequence + [color], map_dict)
def color_map(region):
# Make a dict with the 'lands' as keys and the corresponding cells and the
# neighboring cells as inner dict.
map_dict = {}
for i, row in enumerate(region):
for j, land in enumerate(row):
if land in map_dict:
map_dict[land]['cells'].append((i, j))
else:
map_dict[land] = {'cells' : [(i, j)], 'neighbors' : set()}
map_dict[land]['neighbors'] |= check_neighbors(region, land, (i, j))
# Set the first land's color to one and start with the coloring recursively
if len(map_dict) <= 1:
return [1]
return coloring(sorted(map_dict.keys())[1:], [1], map_dict)
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"
Oct. 19, 2020
Comments: