Advent of code

◂ 21 décembre 2023 ▸

  Step Counter : Compter le nombre de positions où l'on peut arriver après un certain nombre de déplacements

................

.##.....#.......

...........#..#.

.....#.#........

.........#...#..

..##.......#.#..

..............##

......##..#.#.##

1. code.py
2. code_sans_dijkstra.py
3. formule_reddit_yellowzorro.png

from typing import Callable
Endroit = tuple[int,int]

f = open("input.txt", 'r', encoding='utf-8')
lines = [line[:-1] for line in f.readlines()]

for r,line in enumerate(lines):
    if 'S' in line:
        start = (r, line.index('S'))

H = len(lines)
W = len(lines[0])
assert H == W
assert H % 2 == 1
MILIEU = H // 2
assert start == (MILIEU, MILIEU)
RANGE_R = range(H)
RANGE_C = range(W)

""" Ne fonctionnera que parce que tout est facilement atteignable et qu'il y a une grosse zone tampon en losange """
""" Et aussi parce que NB_PAS_TOT tombe pile sur bord: NB_PAS_TOT = k * W + W/2 """

NB_PAS_PARTIE_1 = 64
NB_PAS_TOT = 26501365
assert NB_PAS_TOT % W == MILIEU
m = NB_PAS_TOT // W
assert m % 2 == 0   # formule ne marche pas sinon. Aucune idée pourquoi

print(f"{H=}, {W=}, {start=}")

DIR = [(1,0),(-1,0),(0,1),(0,-1)]

def nexts(sommet: Endroit) -> list[ tuple[int,Endroit] ]:
    sr,sc = sommet
    ret = []
    for dr,dc in DIR:
        nr,nc = sr+dr,sc+dc
        if not (nr in RANGE_R and nc in RANGE_C) or lines[nr][nc] == '#':
            continue
        ret.append((1,(nr,nc)))
    return ret

def dijkstra(aretes: Callable[[Endroit],list[tuple[int,Endroit]]], start: Endroit) -> dict[Endroit,int]:
    distances: dict[Endroit,int] = dict()  # distance depuis start et sommet dont on vient
    distances[start] = 0
    heap_a_faire: list[list[int|Endroit]] = [[0,start]]   
    
    while heap_a_faire:
        heap_a_faire.sort(reverse=True)
        dist,sommet = heap_a_faire.pop()
        for poids,arrivee in aretes(sommet):
            dist_arr = distances.get(arrivee)
            if dist_arr is not None:
                if dist_arr > dist + poids:
                    to_heap: list[int|Endroit] = [dist_arr, arrivee]
                    if to_heap in heap_a_faire:
                        heap_a_faire[heap_a_faire.index(to_heap)][0] = dist+poids
                    distances[arrivee] = dist + poids
            else:
                distances[arrivee] = dist + poids
                heap_a_faire.append([dist + poids, arrivee])
    return distances


distances: dict[Endroit, int] = dijkstra(nexts, start)

reponse_partie_1 = sum(1 for r in RANGE_R for c in RANGE_C
                         if  (r+c) % 2 == NB_PAS_PARTIE_1 % 2
                         and distances.get((r,c),NB_PAS_PARTIE_1+1) <= NB_PAS_PARTIE_1    )


def au_centre(r: int, c: int) -> bool:
    return (abs(r-MILIEU) + abs(c-MILIEU)) *2 < W    # assert W == H

# Compter les cases inaccessibles, sur toute la grille et dans le losange intérieur
# en différenciant les cases paires des impaires (noires/blanches d'un échiquier)
tots, ints = [0,0], [0,0] 

RESET = '\033[0m'
BOLD  = '\033[01m'
RED   = '\033[31m'
for r in RANGE_R:
    for c in RANGE_C:
        if lines[r][c] == '#' or (r,c) not in distances:
            if lines[r][c] == '#':
                v = '#'
            else:
                v = BOLD + RED+ 'X' + RESET 
            if au_centre(r,c): 
                ints[(r+c)%2] += 1
            elif v == '#':
                v = BOLD+'#'+RESET
            tots[(r+c)%2] += 1
        else:
            num = distances[(r,c)] - (abs(r-start[0]) + abs(c-start[1]))
            if  num == 0:
                v = '.'
            else:
                v = str(num)
                if num >= 10:
                    v = '*'
                v = RED + v + RESET
        print(v, end='')
    print()

(tot_pair,tot_impair), (int_pair,int_impair) = tots,ints

# Ca inverse pour les carres qui se repetent cote a cote, donc il y a un certain nombre de cases impaires mais qui sont atteignable avec un nombre pair de pas
if m % 2 == 0:
    coeff_murs_impairs = m*(m+1)*tot_impair + (m+1)*int_impair
    coeff_murs_pairs   = m*(m+1)*tot_pair   -  m   *int_pair
else:
    # Ne marche pas ?
    coeff_murs_impairs = m*(m+1)*tot_impair -  m   *int_impair
    coeff_murs_pairs   = m*(m+1)*tot_pair   + (m+1)*int_pair

reponse_partie_2 = NB_PAS_TOT*NB_PAS_TOT+2*NB_PAS_TOT+1 - coeff_murs_pairs - coeff_murs_impairs  


print("Réponse partie 1:", reponse_partie_1)
print("Réponse partie 2:", reponse_partie_2)