Advent of code

◂ 10 décembre 2023 ▸

  Pipe Maze : Suivre parcours circulaire et compter l'intérieur
7.FF7777.|77.-L-77.|F-7-.L77|7F|7-|-JF77 …
   
J7L-||LL7L|7-J.|.|7LL-|.F7|FJ7----J-7-|L …
   
.77L|7-|L-L7J.L7FJ.||F|F|-F-JJ.|..|LL-L. …
   
                        ⋮
Quatre façons de résoudre la partie 2:
  1. code_part1_part2.py :
    Compter le nombre de fois où l'on traverse la boucle pour savoir si on est dedans ou non.
  2. code_part2_compterInterieur_maths.py :
    Utiliser la formule du laçage pour calculer l'aire et utiliser le théorème de Pick, qui relie aire, périmètre et nombre de points intérieurs.
  3. code_part2_broaden_floodfill.py :
    Agrandir la grille pour que toutes les parties extérieures soient connexes et faire un flood-fill.
  4. code_part2_floodFillLeftSide.py :
    Marquer les endroits touchant la boucle de façon différente si c'est à gauche ou à droite en avançant, et faire un flood-fill sur chaque zone connexe.
    (Variante sensCourbe : on fait le flood-fill uniquement sur la même ligne)
  1. code_part1_part2.py
  2. code_part2_diag.py
  3. code_part2_compterInterieur_replace.py
  4. map.png
  5. map_animation
  6. mapColor.png
  7. mapFilledWithGimp.png
  8. code_part2_compterInterieur_maths.py
  9. code_part2_broaden_floodfill.py
  10. mapBroadenAndFill.png
  11. map_animation_flood_fill
  12. code_part2_floodFillLeftSide.py
  13. left_right.png
  14. code_part2_sensCourbe.py
"""
    Agrandir la grille, de sorte que toutes les cases extérieures soient connexes.
    Plus qu'à faire un flood-fill depuis l'extérieur et compter ce qui reste.
"""
f = open("input.txt", 'r', encoding='utf-8')

DRAWING_MODE = 3   # 1: carré, 2: arrondi léger, 3: virages à la corde

HAUT, BAS, GAUCHE, DROITE = 1, 8, 2, 4
MOVES = {HAUT:(-1,0), BAS:(1,0), GAUCHE:(0,-1), DROITE:(0,1)}
LETTRES_TO_DIRS = { '|' : HAUT + BAS,
                    '-' : GAUCHE + DROITE,
                    'F' : BAS + DROITE,
                    '7' : BAS + GAUCHE,
                    'L' : HAUT + DROITE,
                    'J' : HAUT + GAUCHE
                  }

def has_direction(lettre, dir):
    return dir & LETTRES_TO_DIRS.get(lettre, 0)

def find_junction_type(y, x):
    """ Regarde autour de la position pour déterminer les sorties et donc la lettre censée être là (utile pour 'S') """
    dirs_start = 0
    for bit_value, (dy, dx) in MOVES.items():
        if has_direction( grid[y+dy][x+dx], 8//bit_value ):   #  8//bit : change HAUT<->BAS et GAUCHE<->DROITE
            dirs_start += bit_value
    return {v: k for k, v in LETTRES_TO_DIRS.items()}[dirs_start]

def get_moves(lettre):
    return tuple( MOVES[dir]  for dir in MOVES.keys()  if  has_direction(lettre, dir))

def next(pos, coming_from=None):
    new_positions = [(pos[0]+d0, pos[1]+d1) for d0, d1 in get_moves(grid[pos[0]][pos[1]])]
    if new_positions[0] == coming_from:
        return new_positions[1]
    else:
        return new_positions[0]

grid = [list(line[:-1]) for line in f.readlines()]
starting_pos = None

# Trouver le départ
for y,line in enumerate(grid):
    if 'S' in line:
        x = line.index('S')
        starting_pos = (y,x)
        grid[y][x] = find_junction_type(*starting_pos)
        break


parcours = set()
pos, last_pos = starting_pos, None
while (not last_pos) or pos != starting_pos:
    parcours.add(pos)
    last_pos, pos = pos, next(pos, last_pos)

# Effacer les lettres hors du vrai circuit
grid = [ [ lettre  if (y,x) in parcours else  '.'   for x,lettre in enumerate(line)]   for y,line in enumerate(grid)]
new_grid = [ (3*len(grid[0]))*[' ']for _ in range(len(grid)*3) ]

for y,line in enumerate(grid):
    y = 3*y + 1
    for x, lettre in enumerate(line):
        dirs = LETTRES_TO_DIRS.get(lettre, 0)
        if dirs != 0:
            x = 3*x + 1
            if DRAWING_MODE == 1 or dirs in (HAUT+BAS, GAUCHE+DROITE):   # Pas quand ça tourne, pour arrondir les coins :)
                new_grid[y][x] = '#'                # Dessiner le centre
            tdy, tdx = 0, 0
            for bit_value, (dy, dx) in MOVES.items():
                if has_direction(lettre, bit_value):
                    new_grid[y+dy][x+dx] = '#'
                    tdy += dy
                    tdx += dx
            if DRAWING_MODE == 3:
                new_grid[y+tdy][x+tdx] = '#'


FLOOD = 'o'
new_grid[0][0] = FLOOD
to_spread = set([(0,0)])
while len(to_spread) > 0:
    pos = to_spread.pop()
    new_grid[pos[0]][pos[1]] = FLOOD
    for d0, d1 in MOVES.values():
        if (pos[0]+d0 in range(len(new_grid))) and (pos[1]+d1 in range(len(new_grid[0]))):
            if new_grid[pos[0]+d0][pos[1]+d1] == ' ':
                to_spread.add((pos[0]+d0, pos[1]+d1))


pos_interieures = set()
for y in range(1, len(new_grid), 3):
    for x in range(1, len(new_grid[0]), 3):
        if all(new_grid[yy][xx] == ' ' for (yy,xx) in ((y,x), (y-1,x), (y,x-1), (y+1,x), (y,x+1))):
            pos_interieures.add((y,x))
    
reponse2 = len(pos_interieures)



####### Dessiner la grille ####################
def colorer(s, couleur):
    if couleur is None:
        return s
    CODES = {'rouge':41, 'violet':45, 'bleu':44, 'vert':42, 'orange':43, 'gris':47}
    return '\033[' + str(CODES[couleur]) + 'm' + s + '\033[0m'

# go dessin
subs = str.maketrans('#', '█')  
for y, line in enumerate(new_grid):
    for x, lettre in enumerate(line):
        lettre = lettre.translate(subs)
        coul = None
        if lettre in '. ':
            #if (y,x) in pos_interieures:
            if any((yy,xx) in pos_interieures for (yy,xx) in ((y,x),(y+1,x),(y-1,x),(y,x+1),(y+1,x+1),(y-1,x+1),(y,x-1),(y+1,x-1),(y-1,x-1))):
                coul = 'bleu'
                lettre = ' '
            else:
                coul = 'gris'
                lettre = ' '
        elif lettre == FLOOD:
            coul = 'vert'
        
        print(2*colorer(lettre, coul), end='')
    print()
###############################################

print("Réponse partie 2:", reponse2)