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

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

# Partie 1, plus détecter les cases inatteignables (beaucoup plus rapide avec un dijkstra !)
atteignables = set()
tiles = set([start])
for i in range(int(W * 1.2)):    # devrait suffire pour atteindre tout ce qui est atteignable
    ns = set()
    while len(tiles):
        (tr,tc) = tiles.pop()
        for (dr,dc) in DIR:
            ntr,ntc = tr+dr,tc+dc
            if not(ntr in RANGE_R and  ntc in RANGE_C) or lines[ntr][ntc] == '#':
                continue
            ns.add((ntr,ntc))
    tiles = ns
    atteignables.update(tiles)
    if i == NB_PAS_PARTIE_1 - 1:
        reponse_partie_1 = len(tiles)

def au_centre(r,c):
    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 atteignables:
            if lines[r][c] == '#':
                v = '#'
            else:
                v = BOLD + RED+ '*' + RESET 
            if au_centre(r,c): 
                ints[(r+c)%2] += 1
            elif v == '#':
                    v = BOLD+'#'+RESET
            tots[(r+c)%2] += 1
        else:
            if au_centre(r,c):
                v = ' '
            else:
                v = '.'
        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)