◂ 22 décembre 2022 ▸
Monkey Map : Se déplacer sur une carte 2D d'un tore, puis sur un cube
… ..................#.. …
… #......#........##..# …
⋮
36R27L7R50R50L10L1R4R47L15 …
- codeToutFaitALaMain.py
- codeMeilleurMaisPasTop.py
- codeAutomatique.py
### CODE général pour tout dépliage du dé !
### Pas eu le temps de récrire les noms de variables et de fonctions au propre...
import re
DROITE, BAS, GAUCHE, HAUT = list(range(4))
DIRS = [(1,0), (0,1), (-1,0), (0,-1)]
SYMBOLE = ['>', 'v', '<', '^']
def lireInput():
with open("input.txt", 'r', encoding='utf-8') as f:
lignes = [ligne[:-1] for ligne in f.readlines()]
instructions = tuple(map(lambda x:x in 'RL' and x or int(x), re.findall('[0-9]+|[RL]', lignes[-1])))
lignes = lignes[:-2]
hauteur = len(lignes)
largeur = 0
nbPointsVisitables = 0
for ligne in lignes:
if len(ligne) > largeur:
largeur = len(ligne)
nbPointsVisitables += len(ligne) - ligne.count(' ')
longueurCote = (nbPointsVisitables / 6.)**0.5
assert longueurCote == int(longueurCote)
longueurCote = int(longueurCote)
### Ajouter de la marge pour pouvoir aller dans n'importe quelle direction depuis un endroit du cube
lignes = [largeur*" "] + lignes + [largeur*" "]
for i in range(len(lignes)):
lignes[i] = " " + lignes[i] + (largeur+1)*" "
largeur += 2
hauteur += 2
return lignes, instructions, largeur, hauteur, longueurCote
lignes, INSTRUCTIONS, LARGEUR, HAUTEUR, LONGUEUR_COTE = lireInput()
DEPART_Y = 1
DEPART_X = lignes[DEPART_Y].index('.')
# Partie 1: fonction calculant le prochain endroit, None si obstacle
def prochainPoint_partie1(lignes, indiceDir, x, y):
move = True
while move:
x = (x + DIRS[indiceDir][0]) % LARGEUR
y = (y + DIRS[indiceDir][1]) % HAUTEUR
if lignes[y][x] == '#':
return None
move = (lignes[y][x] == ' ')
return (x, y, indiceDir)
# Pour partie 2
def rotationCube(coins, direction):
if direction == BAS:
matrice = [[ 0,0,1],
[ 0,1,0],
[-1,0,0]]
elif direction == GAUCHE:
matrice = [[ 0,1,0],
[-1,0,0],
[ 0,0,1]]
elif direction == HAUT:
matrice = [[0,0,-1],
[0,1, 0],
[1,0, 0]]
else: # DROITE
matrice = [[0,-1,0],
[1, 0,0],
[0, 0,1]]
return tuple(tuple(sum(ligne[i]*pt[i] for i in range(3)) for ligne in matrice) for pt in coins)
def rotationsCubeMultiples(directions):
coins = FACE_BASE
for direction in directions:
coins = rotationCube(coins, direction)
return coins
# Chaque face orientée est décrite par les coints HAUT-GAUCHE et HAUT-DROITE
coordonnesSelonFace = {} # liste des coordonnées de chaque face orientée
faceSelonCoordonnees = {} # liste des faces pour chaque coordonnées, orientation est celle de la carte
rotationsSelonCoordonnees = {} # liste des rotations pour obtenir la face depuis FACE_BASE
# calcule et enregistre dans les dictionnaires décits ci-dessus
def sauverCoordonnesFacesEtRotations(col, row, rotations=None):
if rotations is None:
rotations = []
face = rotationsCubeMultiples(rotations)
for orientation in range(4):
faceOrientee = tuple((face[orientation:] + face[:orientation])[:2]) # Coing HAUT-GAUCHE et HAUT-DROITE
coordonnesSelonFace[faceOrientee] = (col, row, orientation%4)
rotationsSelonCoordonnees[(col,row)] = rotations
faceSelonCoordonnees[(col,row)] = face
FACE_BASE = ((1,1,1),(1,1,-1),(1,-1,-1),(1,-1,1))
sauverCoordonnesFacesEtRotations((DEPART_X - 1) // LONGUEUR_COTE, (DEPART_Y - 1) // LONGUEUR_COTE)
# Algo Breadth-first pour trouver où sont les faces sur la carte
aTraiter = [coordonnesSelonFace[FACE_BASE[:2]][0:2]]
while len(aTraiter) > 0:
col , row = aTraiter.pop()
for indiceDir in range(4):
prochCol = col + DIRS[indiceDir][0]
prochLigne = row + DIRS[indiceDir][1]
if prochCol < 0 or prochLigne < 0 or prochCol >= (LARGEUR - 2) // LONGUEUR_COTE or prochLigne >= (HAUTEUR - 2) // LONGUEUR_COTE: # en dehors de l'input
continue
xAuMilieu, yAuMilieu = prochCol * LONGUEUR_COTE + LONGUEUR_COTE // 2, prochLigne * LONGUEUR_COTE + LONGUEUR_COTE // 2
if lignes[yAuMilieu][xAuMilieu] == ' ':
continue
if (prochCol, prochLigne) in aTraiter or (prochCol, prochLigne) in faceSelonCoordonnees: # déjà calculé
continue
aTraiter.append((prochCol, prochLigne))
rotations = [indiceDir] + rotationsSelonCoordonnees[(col,row)]
sauverCoordonnesFacesEtRotations(prochCol, prochLigne, rotations)
CORRESPONDANCES = {} # tunnel entre un côté et un autre qu'on lui colle dessus
# point de départ du segment à coller
def departSegment(col, row, indiceDir, segmentQuOnColle=True):
indiceDirCollage = (indiceDir + 1) % len(DIRS) # tourner à droite
if segmentQuOnColle:
directionDecalee = indiceDirCollage
else:
directionDecalee = (indiceDirCollage - 1) % 4
ajout = { DROITE:(1, 1), BAS:(LONGUEUR_COTE, 1), GAUCHE:(LONGUEUR_COTE, LONGUEUR_COTE), HAUT:(1, LONGUEUR_COTE)}[directionDecalee]
x,y = LONGUEUR_COTE*col + ajout[0], LONGUEUR_COTE*row + ajout[1]
return (x, y, indiceDirCollage)
def collerBords(col1, row1, indiceDir1, col2, row2, indiceDir2):
global CORRESPONDANCES
x1,y1,d1 = departSegment(col1, row1, indiceDir1, segmentQuOnColle=True)
x2,y2,d2 = departSegment(col2, row2, indiceDir2, segmentQuOnColle=False) # segment sur lequel on colle
# coller chaque point d'un côté sur l'autre côté
for i in range(LONGUEUR_COTE):
nx1, ny1 = x1 + i * DIRS[d1][0], y1 + i * DIRS[d1][1]
nx2, ny2 = x2 + i * DIRS[d2][0], y2 + i * DIRS[d2][1]
CORRESPONDANCES[(nx1 + DIRS[indiceDir1][0], ny1 + DIRS[indiceDir1][1], indiceDir1)] = (nx2, ny2, indiceDir2)
### Collons les côtés et remplissons CORRESPONDANCES
for col,row in faceSelonCoordonnees:
face = faceSelonCoordonnees[(col, row)]
for indiceDirCote in range(4): # coller chaque côté de chaque face, même si c'est inutile car déjà connecté
faceOrientee = (face+face)[indiceDirCote:indiceDirCote+2] # répéter face pour éviter un calcul compliqué de modulos
faceOpposee = tuple(reversed(faceOrientee))
col2, row2, indexDir2 = coordonnesSelonFace[faceOpposee]
collerBords(col, row, indiceDirCote, col2, row2, (indexDir2 + 2) % 4)
### Et maintenant c'est encore plus simple que pour la partie 1
def prochainPoint_partie2(lignes, indiceDir, x, y):
x = (x + DIRS[indiceDir][0])
y = (y + DIRS[indiceDir][1])
if lignes[y][x] == ' ':
x,y,indiceDir = CORRESPONDANCES[(x,y,indiceDir)]
if lignes[y][x] == '#':
return None
else:
return (x,y, indiceDir)
def avancer(lignes, indiceDir, distance, x, y):
for _ in range(distance):
prochainPt = prochainPoint(lignes, indiceDir, x, y)
if prochainPt is None:
break
x,y,indiceDir = prochainPt
# lignes[y] = lignes[y][:x] + SYMBOLE[indiceDir] + lignes[y][x+1:] # pour visualiser, ne change pas les obstacles '#'
return (x, y, indiceDir)
### C'est parti pour la balade sur le cube
for partie in [1, 2]:
x = DEPART_X
y = DEPART_Y
indiceDir = DROITE
# Choisisson pour chaque partie la bonne fonction à appeler
if partie == 1:
prochainPoint = prochainPoint_partie1
else:
prochainPoint = prochainPoint_partie2
# Suivre les instructions
for instr in INSTRUCTIONS:
if instr in {'R', 'L'}:
if instr == 'R':
indiceDir = (indiceDir + 1) % len(DIRS)
elif instr == 'L':
indiceDir = (indiceDir - 1) % len(DIRS)
else:
x, y, indiceDir = avancer(lignes, indiceDir, instr, x, y)
print("Réponse partie " + str(partie) + ":", 1000*y + 4*x + indiceDir)