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.
    Au lieu d'un flood-fill ensuite (code_part2_floodFillLeftSide.py), marquer les vides
    contigus sur la même ligne .
    https://en.wikipedia.org/wiki/Nonzero-rule
    Histoire de varier, on utilise aussi le fait de savoir si on tourne à gauche ou à droite pour
    déterminer l'intérieur
"""
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 = {}
pos, last_pos = starting_pos, None
virages = []
while (not last_pos) or pos != starting_pos:
    last_pos, pos = pos, next(pos, last_pos)
    c = grid[last_pos[0]][last_pos[1]]
    if c == '|':
        v = BAS if last_pos[0] < pos[0] else HAUT
    elif c == '-':
        v = DROITE if last_pos[1] < pos[1] else GAUCHE
    elif c == 'F':
        v = DROITE+HAUT if last_pos[1] < pos[1] else GAUCHE+BAS
        virages.append(v)
    elif c == 'L':
        v = DROITE+BAS if last_pos[1] < pos[1] else GAUCHE+HAUT
        #virages.append(8//(v&(GAUCHE+DROITE)))
        virages.append(DROITE if v&GAUCHE else GAUCHE)
    elif c == 'J':
        v = GAUCHE+BAS if last_pos[1] > pos[1] else DROITE+HAUT
        virages.append(DROITE if v&GAUCHE else GAUCHE)
    else:
        assert c == '7'
        v = GAUCHE+HAUT if last_pos[1] > pos[1] else DROITE+BAS
        virages.append(v)
    parcours[last_pos] = v    # enregistrer deplacement plutôt que accès


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

    
interieur_a_gauche: bool = sum(1 for v in virages if v&GAUCHE) > sum(1 for v in virages if v&DROITE)
interieur = set()
pos, last_pos = starting_pos, None
while (not last_pos) or pos != starting_pos:
    last_pos, pos = pos, next(pos, last_pos)
    if parcours[last_pos] & (HAUT if interieur_a_gauche else BAS):
        for x in range(last_pos[1]-1, -1, -1):
            if grid[last_pos[0]][x] == ' ':
                interieur.add((last_pos[0],x))
            else:
                break
    else:
        for x in range(last_pos[1]+1, len(grid[0])):
            if grid[last_pos[0]][x] == ' ':
                interieur.add((last_pos[0],x))
            else:
                break

reponse2 = len(interieur)


####### Dessiner la grille ####################
CARAC_INTERIEUR = '.'
CARAC_EXTERIEUR = 'o'
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 == ' ':
            if ((y,x) in interieur):
                lettre = CARAC_INTERIEUR
                coul = 'bleu'
            else:
                lettre = CARAC_EXTERIEUR
                coul = 'vert'
        
        print(colorer(lettre, coul), end='')
    print()
###############################################

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