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
""" Façon très mathématique de calculer le nombre de points intérieur
    avec le Théorème de Pick qui relie l'aire au nombre de points
    et avec un calcul d'aire des polygones avec la formule des lacets (déterminants) """

def get_nb_pos_interieures(grid):
    pos, last_pos = starting_pos, None
    nb = 0
    sum_det = 0
    for _ in range(len(parcours)):
        last_pos, pos = pos, next(pos, last_pos)

        # https://en.wikipedia.org/wiki/Shoelace_formula :
        sum_det += last_pos[0]*pos[1] - last_pos[1]*pos[0]
        nb += 1
    area = abs(sum_det) / 2.0

    # https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Pick :
    return  area - nb//2 + 1