Advent of code

◂ 23 décembre 2023 ▸

  A Long Walk : Trouver parcours le plus long sans repasser par le même chemin

#.################## … 

#.#...#...#......... … 

#.#.#.#.#.#.#######. … 

#.#.#...#.#.......#. … 

#.#.#####.#######.#. … 

#.#.#.....#...#...#. … 

#.#.#.#####.#.#.###. … 

#.#.#...#...#.#...#. … 

#.#.###.#.###v###.## … 

#...###.#.###.>.#... … 

#######.#.###v#.###. … 

#.......#.#...#...#. … 

1. code.py
2. code1_lent.py
3. soluceGraphe1.png
4. soluceGraphe2.png
5. grapheurCodePourri.py

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

H = len(lines)
W = len(lines[0])
RANGE_H = range(H)
RANGE_W = range(W)

sys.setrecursionlimit(W * H)

start = (0,1)
end = (H-1,W-2)

DIR = ( (1,0), (-1,0), (0,1), (0,-1) )
OKS = ['.v', '.^', '.>', '.<']
def chemins(pos, faits):
    if pos == end:
        return [[]]
    ret = []
    for i,(d0,d1) in enumerate(DIR):
        np = (np0,np1) = (pos[0]+d0, pos[1]+d1)
        if np0 in RANGE_H and np1 in RANGE_W and lines[np0][np1] in OKS[i] and  np not in faits:
            ret.extend( [ [pos] + nc   for nc in chemins(np, faits+[np]) ])
    return ret


chemin_partie1 = max(chemins(start, [start] ), key=len )
reponse_partie1 = len(chemin_partie1)


RESET = '\033[0m'
BOLD  = '\033[01m'
RED   = '\033[31m'
for y in RANGE_W:
    for x in RANGE_H:
        if (y,x) in chemin_partie1:
            print(RED + BOLD + 'O' + RESET, end='')
        else:
            print(lines[y][x], end='')
    print()

print("Réponse partie 1:", reponse_partie1)