Advent of code

◂ 12 décembre 2022 ▸

  Hill Climbing Algorithm : Labyrinthe orienté: ne jamais monter de plus que 1

abccccccccaaaaccccaaacaccccaaa … 

abccccccccaaaaccaaaaaaaacccaaa … 

abcccccccccaacccaaaaaaaaccccaa … 

1. code.py
2. solution.png

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

NB_LIGNES = len(lines)
NB_COLONNES = len(lines[0])


# Initialisation de la grille et des positions S et E
grid = []
startX = startY = None
endX = endY = None

for y in range(NB_LIGNES):
    line = list(lines[y])
    if 'S' in line:
        startY = y
        startX = line.index('S')
        line[startX] = 'a'
    if 'E' in line:
        endY = y
        endX = line.index('E')
        line[endX] = 'z'
    # remplacer les lettres par des niveaux de 0 à 25
    line = list(map(lambda x:ord(x)-ord('a'),line))
    grid.append(line)



# déplacement possible depuis une position (x,y), sur le chemin RETOUR, AU DÉPART DE E: donc en *descendant* au plus de 1 unité
def deplacementsPossibles(grid, x, y):
    prochainsPoints = []
    for (dx,dy) in ((1,0), (-1,0), (0,1), (0,-1)):
        nextX = x + dx
        nextY = y + dy
        if nextX < 0 or nextX >= NB_COLONNES or nextY < 0 or nextY >= NB_LIGNES:
            continue
        # Ne pas trop descendre
        if grid[y][x] - grid[nextY][nextX] <= 1:
            prochainsPoints.append((nextX,nextY))
    return prochainsPoints


# pour algorithme de Dijkstra simplifié (arêtes de longueur 1 tout le temps)
def caculerProchaineDistance(distGrid, aFaire, dejaFaits):
    (x,y) = aFaire.pop(0)
    dejaFaits.append((x,y))
    for (nextX,nextY) in deplacementsPossibles(grid, x, y):
        if (nextX,nextY) not in aFaire and (nextX,nextY) not in dejaFaits:
            distGrid[nextY][nextX] = distGrid[y][x] + 1
            aFaire.append((nextX,nextY))

# algorithme de Dijkstra
def calculerDistancesDepuisE(grid, x, y):
    distGrid = []
    for _ in range(NB_LIGNES):
        distGrid.append(NB_COLONNES * [None])
    distGrid[y][x] = 0

    aFaire = [(x,y)]
    dejaFaits = []
    while len(aFaire) > 0:
        caculerProchaineDistance(distGrid, aFaire, dejaFaits)
    return distGrid


distGrid = calculerDistancesDepuisE(grid, endX, endY)

# Partie 1
longueurE_S = distGrid[startY][startX]
print("Réponse partie 1:", longueurE_S)

# Partie 2
minLongueur = longueurE_S  # autant initialiser avec une valeur connue plutôt que None et devoir tester
for y in range(NB_LIGNES):
    for x in range(NB_COLONNES):
        if grid[y][x] == 0:
            v = distGrid[y][x]    # parfois None si le chemin n'existe pas !
            if v != None:
                minLongueur = min(minLongueur, v)
print("Réponse partie 2:", minLongueur)