Borders clear solution for Color Map by DiZ - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

Borders solution in Clear category for Color Map by DiZ

def color_map(colored_map):
    # Construct all regions
    regions = {}
    for i, line in enumerate(colored_map):
        for j, cell in enumerate(line):
            regions.setdefault(cell, set()).add(i + 1j*j)

    # Get neigbours for all regions
    neighbours = {}
    for region, cells in regions.items():
        border = set.union(*({c + 1j ** k for k in range(4)} for c in cells)) - cells
        neighbours[region] = {r for r, c in regions.items() if border & c}

    # Color each region with first available color
    c, colors = 0, [0] * len(regions)
    while c < len(regions):
        variants = set(range(colors[c]+1, 5)) - {colors[n] for n in neighbours[c]}
        colors[c] = len(variants) and min(variants)
        c += 2*bool(variants) - 1
    return colors

Feb. 11, 2015

Comments:

Blastus on July 9, 2016, 2:55 p.m.
Excellent job on your solution to this challenge! You have good documentation, and there are only two (unintentional) PEP8 violations. Check <a href="http://pep8online.com/s/bEPOT0mq">http://pep8online.com/s/bEPOT0mq</a> for what errors your code has in it.

Ardillo95 on Oct. 12, 2016, 4:19 a.m.
.add(i + 1j*j) I don't understand what is this doing :\ <pre class='brush: python'>border = set.union(*({c + 1j ** k for k in range(4)} for c in cells)) - cells </pre> and what about this line?

DiZ on Oct. 12, 2016, 1:57 p.m.
Do you know that Python has <a href="https://en.wikipedia.org/wiki/Complex_numberg">complex number</a> support? They are often you to represent a grid in 2D, so `x + 1j * y` represents a point at coordinates (x, y). There is a trick with the second line: `[1j ** k for k in range(4)] produces [1, 1j, -1, -1j]`, which is equivalent to `[(1,0), (0,1), (-1,0), (0,-1)]`. Does it sound some bells now? That's how I get neighbours for each cell in the set! For each cell in the set, I generate a subset with their neighbours, after what I join all the subsets in a bigger set. This line woul be equivalent to the following if detailed: <pre class='brush: python'>DIRECTIONS = [(1,0), (0,1), (-1,0), (0,-1)] border = set() for x, y in cells: neighbours = {(x + i, y + j) for i, j in DIRECTIONS} border |= neighbours </pre>

Ardillo95 on Jan. 17, 2017, 12:39 a.m.
I am pretty sure this is not a clear solution :/

DiZ on Jan. 17, 2017, 4:55 p.m.
Clearness is a subjective notion ;-) Don't hesitate if you have any question, I would be glad to provide more insight in order to make it understandable.

bkai on Feb. 5, 2017, 8:32 p.m.
How do you ensure that the first available color will work?

DiZ on Feb. 5, 2017, 9:16 p.m.
Look at the lines 14-19. I maintain an array containing colors for each region, with a moving index `c`. When no color is available (`variants` empty), the index is decremented and a new color is tested for previous regions: `range(colors[c]+1, 5)`. It's basically another way to backtrack when a wrong color is selected.

List, list and list again

0 %

PyCharm The Python IDE for Professional Developers. Enjoy productive Python, web and scientific development with PyCharm. Download it now!