Advent of code

◂ 17 décembre 2023 ▸

  Clumsy Crucible : Parcours le moins coûteux avec contraintes sur la longueur des segments entre les virages
3133311111322 …
   
2231132323114 …
   
2113232122132 …
   
2111331311234 …
   
       ⋮
Essayé avec un Dijkstra puis un A* naïf, mais ça ne marche pas si l'endroit d'où l'on vient peut influencer le droit de prendre une arête ou non.

J'ai tenté un depth-first car un breadth-first me paraissait avoir le même problème, mais depth-first = trop long.

J'ai tenté un breadth-first en prenant en compte l'historique de parcours (et avec le fait que le graphe est pondéré, donc il faut ralentir la progression…).
Beaucoup trop lent aussi, mais avec 15 minutes de moulinage, ça passait et j'ai pu soumettre mes réponses.

Finalement, récrit le code avec Dijkstra, avec sommets = position+porte d'entrée, et en reliant des sommets voisins que si on tourne.
Et du coup, les voisins possibles calculés ne sont pas seulement les voisins immédiats, mais tous les voisins à bonne distance (entre 4 et 10 pour la partie 2).
Le code met moins de 30 secondes pour les deux parties.

Reste à faire :
· rendre plus joli le code Dijkstra ;
· essayer de modifier le Dijkstra en A* ;
· rendre lisible le code avec Breadth-first et le mettre en ligne.
  1. code_avec_dijkstra.py
  2. dijkstra.py
import os, random, random
from collections import defaultdict
from dijkstra import dijkstra

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

H, W = len(lines), len(lines[0])
RANGE_H, RANGE_W = range(H), range(W)
DIRS = (1, 1j, -1, -1j)
print(f"{H=}, {W=}")

grid = defaultdict(lambda:10*H*W, ((r+c*1j, int(lines[r][c])) for r in range(len(lines)) for c in range(len(lines[0]))) )


# J'ai tenté l'utilisation de complexes pour ne pas avoir à gérer les bords. Mauvaise idée.
def toSommet(z, last_dir):
    return (int(z.real), int(z.imag), last_dir.real, last_dir.imag)

def from_sommet(sommet):  
    r,i,last_dir_r, last_dir_i = sommet
    return r + i*1j, last_dir_r + last_dir_i*1j


def get_aretes(pos):
    pos,last_dir = from_sommet(pos)    
    for d in DIRS:
        if last_dir and (d == last_dir or d == -last_dir):
            continue
        dist_segment = 0
        p2 = pos
        for nb in range(1,MIN_L):
            p2 += d
            dist_segment += grid[p2]
            
        for nb in range(MIN_L, MAX_L+1):
            p2 += d
            dist_segment += grid[p2]
            if p2.real in RANGE_H and p2.imag in RANGE_W:
                yield (dist_segment, toSommet(p2,d))
            else:
                break


start = toSommet(0+0j, 0)  # direction = 0, pour ne pas bloquer des départs

def est_fini(sommet):
    return sommet[:2] == (H-1, W-1)

## Plus qu'à appeler l'algo.
## distance1, parcours1 = dijkstra(get_aretes, start, est_fini)


def afficher_parcours(parcours, distance):
    RESET= '\033[0m'
    BOLD = '\033[01m'
    RED  = '\033[31m'

    poss = set((from_sommet(s)[0] for s in parcours))
    passages = set()
    for i in range(1, len(parcours)):
        d = from_sommet(parcours[i])[0] - from_sommet(parcours[i-1])[0]
        nb = int(abs(d))
        d /= nb
        for j in range(nb):
            passages.add(from_sommet(parcours[i-1])[0] + j * d)
    print("===="+str(distance)+": =======")
    for r in range(H):
        for c in range(W):
            ch = str(grid[r+c*1j])
            if r+c*1j in poss:
                print(BOLD+RED + ch + RESET,end='')
            elif r+c*1j in passages:
                print(RED + ch + RESET,end='')
            else:
                print(ch, end='')
        print()
    print("===="+str(distance)+": =======")


MIN_L, MAX_L = 1, 3
distance1, parcours1 = dijkstra(get_aretes, start, est_fini)
afficher_parcours(parcours1, distance1)

MIN_L, MAX_L = 4, 10
distance2, parcours2 = dijkstra(get_aretes, start, est_fini)
afficher_parcours(parcours2, distance2)

print("Réponse partie 1:", distance1)
print("Réponse partie 2:", distance2)



# Pour l'algo A*
#def h(p):
#    return abs(p.real-end.real)+abs(p.imag-end.imag)