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
"""
    Pour décider si une case vide est à l'intérieur, regarder combien de fois on a
    traversé le circuit pour y arriver (nombre impair = 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 = 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)

reponse1 = len(parcours) // 2


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


def get_pos_interieures(grid):
    pos_interieures = set()    # liste plutôt que décompte, pour dessiner plus tard
    for y,line in enumerate(grid):
        outside = True
        last_corner = None
        for x, lettre in enumerate(line):
            if lettre == '|':
                outside = not outside
            elif lettre == '-':
                pass
            elif lettre in 'LF':
                last_corner = lettre
            elif lettre in 'J7':
                    if (lettre == '7') == (last_corner == 'L'):
                            outside = not outside
            else:
                if not outside:
                    pos_interieures.add((y,x))
    return pos_interieures

pos_interieures = get_pos_interieures(grid)
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}
    return '\033[' + str(CODES[couleur]) + 'm' + s + '\033[0m'

# Trouver le point le plus éloigné du départ, juste pour le dessiner en violet :)
far_away, last_pos = starting_pos, None
for _ in range(len(parcours) // 2):
    last_pos, far_away = far_away, next(far_away, last_pos)

# 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 (y,x) == starting_pos:
            coul = 'rouge'
        elif (y,x) == far_away:
            coul = 'violet'
        elif lettre == '.':
            if (y,x) in pos_interieures:
                coul = 'bleu'
            else:
                coul = 'vert'
                lettre = ' '
        print(colorer(lettre, coul), end='')
    print()
###############################################

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