Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Recursive optimizted brute-force solution solution in Clear category for Color Map by brubru777
def build_graph(region):
'''Builds and returns the graph of country adjacences.
'''
def add_connexion(graph, country1, country2):
'''Adds a connexion between the two countries.
'''
if country1 != country2:
if country1 not in graph:
graph[country1] = set()
if country2 not in graph:
graph[country2] = set()
graph[country1].add(country2)
graph[country2].add(country1)
height = len(region)
width = len(region[0])
graph = {0: set()}
for i in range(height):
for j in range(width - 1):
add_connexion(graph, region[i][j], region[i][j + 1])
for i in range(height - 1):
for j in range(width):
add_connexion(graph, region[i][j], region[i + 1][j])
return graph
def fill_colors(graph, colors, index):
'''Recursively fills the colors while respecting the constraints and returns
True if a solution is found or False if a constraint can't be satisfied.
'''
if index == len(colors):
return True
neighbor_colors = set(colors[neighbor] for neighbor in graph[index])
available_colors = set((1, 2, 3, 4)) - neighbor_colors
for color in available_colors:
colors[index] = color
if fill_colors(graph, colors, index + 1):
return True
return False
def color_map(region):
'''Returns a color mapping such that no adjacent countries have the same
color.
'''
graph = build_graph(region)
colors = [0 for _ in range(len(graph))]
fill_colors(graph, colors, 0)
return colors
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"
Dec. 17, 2016
Comments:
