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
""" Il est plus facile de savoir si on coupe la boucle ou non
    si on trace des diagonales (y = x + h) au lieu des horizontales """

def get_pos_interieures(grid):

    pos_interieures = set()
    for h in range(1 - len(grid[0]), len(grid)):
        outside = True
        for x in range(max(0,-h), min(len(grid[0]), len(grid) - h)):
            y = x + h
            lettre = grid[y][x]
            if lettre in '-|FJ':      # un seul critère pour savoir si on traverse la boucle
                outside = not outside
            elif lettre in '.':
                if not outside:
                    pos_interieures.add((y,x))
    return pos_interieures