Advent of code

◂ 12 décembre 2024 ▸

  Garden Groups : Trouver des zones et calculer l'aire, le périmètre et le nombre de côtés.

UUUKKKKZZZZ … 

UUKKKKKZZZZ … 

UUKKKKKKKZZ … 

1. code.py
2. code_visualisation.py
3. find_4_colors_coloring.py
4. colorByLetter.png
5. four_colors_plain.png
6. multicolors_borders.png
7. multicolors_plain.png
8. four_colors_terminal_borders.png

from itertools import combinations

with open("input.txt", 'r', encoding='utf-8') as f:
    grid = [line[:-1] for line in f.readlines()]

W = len(grid[0])
H = len(grid)

def find_region_borders(x, y, region_ids, current_region_id) -> (int, int, int):
    region = set()
    borders = set()

    region_letter = grid[y][x]
    to_do = { (x,y), }

    DIRECTIONS = ((1,0), (0,1), (-1,0), (0,-1))

    while to_do:
        x, y = to_do.pop()
        region.add((x,y))
        region_ids[y][x] = current_region_id
        for dx, dy in DIRECTIONS:     
            nx, ny = x+dx, y+dy
            if (nx,ny) not in region:    # not already processed
                if (0 <= nx < W) and (0 <= ny < H) and (grid[ny][nx] == region_letter) :
                    to_do.add((nx,ny))
                else:
                    borders.add( ((x,y), (dx,dy)) )
    return borders
            
     
region_ids = [W*[None] for i in range(H)]
current_region_id = 0
borders = []
for y in range(H):
    for x in range(W):
        if not region_ids[y][x]:   # not already processed
            current_region_id += 1
            borders.append(find_region_borders(x, y, region_ids, current_region_id))

edges = dict( ((i, set())) for i in range(1, len(borders) + 1) )
for region_borders in borders:
    for (x,y),(dx,dy) in region_borders:
        if 0 <= x+dx < W and 0 <= y+dy < H:
            edges[region_ids[y][x]].add(region_ids[y+dy][x+dx])


NB_COLORS = 4


ENLEVES = set()     # id des régions prises en compte qu'à la fin.
edges_copy = dict((k,v.copy()) for k,v in edges.items())
# enlever les noeuds avec peu de voisins, car on pourra toujours les colorer plus tard
id = True
while id:
    id = next((id for id,voisins in edges_copy.items() if len(voisins) < NB_COLORS), None)
    if id is not None:
        ENLEVES.add(id)
        for id_voisin in edges_copy.pop(id):
            edges_copy[id_voisin].remove(id)


COULEURS = set(range(NB_COLORS))
couleur_region = dict()
couls_possibles = dict()
for id in edges:
    couls_possibles[id] = set(COULEURS)

ids_by_degrees = [id for _,id in sorted( ((len(edges[id]), id) for id in edges.keys()), reverse=True)]

def find_clique(ids, edges, clique_size):
    for id in ids:
        if id in ENLEVES:
            continue
        for subset_voisins in combinations(edges[id], clique_size - 1):
            if all(subset_voisins[i2] in edges[subset_voisins[i1]] for i1 in range(len(subset_voisins)-1) for i2 in range(i1+1, len(subset_voisins))):
                return (id,) + subset_voisins
    return None

for clique_size in range(NB_COLORS, 1, -1):
    clique = find_clique(ids_by_degrees, edges_copy, clique_size)
    if clique:
        break
    else:
        print("No clique size", clique_size)

print("Clique:", clique)
for i, id in enumerate(clique):
    couleur_region[id] = i
    couls_possibles.pop(id)
    ids_by_degrees.remove(id)

for id in couls_possibles.keys():
    couls_possibles[id].difference_update( couleur_region[id_clique] for id_clique in edges[id].intersection(clique) )


def get_coloration(couleur_region, couls_possibles, edges):
    id = next( ( id for id, coul_poss in couls_possibles.items() if len(coul_poss) <= 1) , None)
    while id is not None:
        coul_poss = couls_possibles.pop(id)
        if len(coul_poss) == 0:
            return None
        coul = coul_poss.pop()
        couleur_region[id] = coul
        for id2 in edges[id]:
            if id2 in couls_possibles:
                couls_possibles[id2].discard(coul)
        id = next( ( id for id, coul_poss in couls_possibles.items() if len(coul_poss) <= 1) , None)
                                    
    if len(couls_possibles) == 0:
        print("YOUHOUHOU ! 0")
        print(couleur_region)
        print("YOUHOUHOU ! 2")
        exit()

    id,_ = min(couls_possibles.items(), key=lambda t:(t[0] in ENLEVES, len(t[1])))
    couleur_region_copy = dict(couleur_region)
    for coul in couls_possibles.pop(id):
        couleur_region_copy[id] = coul
        couls_poss_copy = dict((k,v.copy()) for k,v in couls_possibles.items())
        for id2 in edges[id]:
            if id2 in couls_poss_copy:
                couls_poss_copy[id2].discard(coul)
        get_coloration(couleur_region_copy, couls_poss_copy, edges)


                    
get_coloration(couleur_region, couls_possibles, edges)