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
"""
    Parcourir le circuit et marquer différemment les vides à gauche et à droite.
    https://en.wikipedia.org/wiki/Nonzero-rule
    Faire un flood-fill sur chaque marque.
    Déterminer si l'intérieur et à gauche ou à droite et compter.
"""
f = open("input.txt", 'r', encoding='utf-8')

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)]

CARAC_FLOOD_GAUCHE = '.'
CARAC_FLOOD_DROITE = 'o'
def add_gauche_droite(pos, vecteur_vitesse, flood_gauche, flood_droite, grid):
    pos_gauche = pos[0] - vecteur_vitesse[1], pos[1] + vecteur_vitesse[0]
    pos_droite = pos[0] + vecteur_vitesse[1], pos[1] - vecteur_vitesse[0]
    if grid[pos_gauche[0]][pos_gauche[1]] == ' ':
        flood_gauche.add(pos_gauche)
        grid[pos_gauche[0]][pos_gauche[1]] == CARAC_FLOOD_GAUCHE
    if grid[pos_droite[0]][pos_droite[1]] == ' ':
        flood_droite.add(pos_droite)
        grid[pos_droite[0]][pos_droite[1]] == CARAC_FLOOD_DROITE
    
flood_gauche = set()
flood_droite = set()
pos, last_pos = starting_pos, None
while (not last_pos) or pos != starting_pos:
    last_pos, pos = pos, next(pos, last_pos)
    vecteur_vitesse = (pos[0]-last_pos[0], pos[1]-last_pos[1])
    add_gauche_droite(last_pos, vecteur_vitesse, flood_gauche, flood_droite, grid)
    add_gauche_droite(pos, vecteur_vitesse, flood_gauche, flood_droite, grid)


def flood(grid, positions, caractere):
    while len(positions) > 0:
        pos = positions.pop()
        grid[pos[0]][pos[1]] = caractere
        for d0, d1 in MOVES.values():
            if pos[0]+d0 in range(0,len(grid)) and pos[1]+d1 in range(0,len(grid[0])):
                if grid[pos[0]+d0][pos[1]+d1] == ' ':
                    positions.add((pos[0]+d0, pos[1]+d1))
flood(grid, flood_gauche, CARAC_FLOOD_GAUCHE)
flood(grid, flood_droite, CARAC_FLOOD_DROITE)

nb_carac_gauche = sum(1 for line in grid for c in line if c == CARAC_FLOOD_GAUCHE)
nb_carac_droite = sum(1 for line in grid for c in line if c == CARAC_FLOOD_DROITE)
if grid[0][0] == CARAC_FLOOD_DROITE:
    reponse2 = nb_carac_gauche
elif grid[0][0] == CARAC_FLOOD_GAUCHE:
    reponse2 = nb_carac_droite
else:
    print("Ahem.")
    # Refaire le parcours, regarder si on tourne plus souvent à gauche qu'à droite ou le contraire.
    # L'intérieur est du côté où on a le plus tourné.
    reponse2 = None


####### 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('FJL7-|', '┏┛┗┓━┃')   #  █ non utilisé finalement
for y, line in enumerate(grid):
    for x, lettre in enumerate(line):
        lettre = lettre.translate(subs)
        coul = None
        if lettre == CARAC_FLOOD_GAUCHE:
            coul = 'bleu'
        elif lettre == CARAC_FLOOD_DROITE:
            coul = 'vert'
        
        print(colorer(lettre, coul), end='')
    print()
###############################################

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