Clase 24 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles
Contenido del curso
Cristian Toro
Cristian Toro
John Eduard Meneses González
José Ramón García
Michael Martinez
Carlos Hernandez
Jose Miguel Murillo Cediel
Jose Miguel Murillo Cediel
Ivan Scaglioni
Esta es mi solución. Inicialmente, había implementado un enfoque diferente, pero ajusté el código para cumplir con los requisitos del desafío y asegurar que pasara todas las pruebas.
def minKnightMoves(origenX, origenY, objetivoX, objetivoY): origen = (origenX , origenY) objetivo = (objetivoX , objetivoY) if origen == objetivo: return [] movimientos = [] cola = [origen] lugares = [] niveles = 1 direcciones = [(-1 ,2), (1 ,2), (-1, -2), (1, -2), (2, -1), (2, 1), (-2, -1), (-2, 1)] while cola: for _ in range(len(cola)): posicionActual = cola.pop(0) if posicionActual == objetivo: movimientos.append(posicionActual) return niveles lugares.append(posicionActual) for xd , yd in direcciones: nextPosicion = posicionActual[0] + xd , posicionActual[1] + yd if nextPosicion in lugares: continue if nextPosicion == objetivo: movimientos.append(nextPosicion) return niveles cola.append(nextPosicion) niveles += 1 if niveles > 8: print("no se encontro objetivo en 8 pasos") return [] return niveles
Me tomó un poco más de tiempo desarrollar el código, ya que pensé que debía devolver las coordenadas de todos los pasos que realizaba el caballo para alcanzar el objetivo.
My Solution!!
Les comparto mi solución en Python:
from collections import defaultdict def minKnightMoves(origenX,origenY,objectiveX,objectiveY): if (origenX,origenY) == (objectiveX,objectiveY): return 0 level = 1 queue = [(origenX,origenY)] visited = defaultdict(int) while queue: for _ in range(len(queue)): x, y = queue.pop(0) for move in [(-2,-1),(-2,1),(-1,-2),(-1,2),(1,-2),(1,2),(2,-1),(2,1)]: i,j = move if visited[(x+i,y+j)] == 0: if (x+i,y+j) == (objectiveX,objectiveY): return level else: queue.append((x+i,y+j)) level += 1
function minKnightMoves(origenX, origenY, objetivoX, objetivoY) { // Paso 1: Normalizar las coordenadas porque el tablero es simétrico objetivoX = Math.abs(objetivoX); objetivoY = Math.abs(objetivoY); // Paso 2: Definir las posibles direcciones del movimiento del caballo const directions = [ [2, 1], [1, 2], [-1, 2], [-2, 1], [-2, -1], [-1, -2], [1, -2], [2, -1] ]; // Paso 3: Crear una cola para la BFS y un conjunto para rastrear las posiciones visitadas const queue = [[origenX, origenY, 0]]; // [x, y, steps] const visited = new Set(); visited.add(`${origenX},${origenY}`); // Paso 4: Realizar la BFS while (queue.length > 0) { const [currentX, currentY, steps] = queue.shift(); // Si alcanzamos el objetivo, devolvemos el número de pasos if (currentX === objetivoX && currentY === objetivoY) { return steps; } // Explorar los movimientos posibles for (const [dx, dy] of directions) { const nextX = currentX + dx; const nextY = currentY + dy; // Normalizar las coordenadas para la simetría del tablero y evitar visitar repetidamente la misma posición if (!visited.has(`${nextX},${nextY}`)) { visited.add(`${nextX},${nextY}`); queue.push([nextX, nextY, steps + 1]); } } } // El problema garantiza que siempre hay una solución, así que no alcanzaremos aquí. return -1; } // Ejemplo de uso: const response = minKnightMoves(0, 0, 5, 5); console.log(response); // Output: 4 ```function minKnightMoves(origenX, origenY, objetivoX, objetivoY) {   // Paso 1: Normalizar las coordenadas porque el tablero es simétrico   objetivoX = Math.abs(objetivoX);   objetivoY = Math.abs(objetivoY);       // Paso 2: Definir las posibles direcciones del movimiento del caballo   const directions = \[   \[2, 1], \[1, 2], \[-1, 2], \[-2, 1],   \[-2, -1], \[-1, -2], \[1, -2], \[2, -1]   ];   // Paso 3: Crear una cola para la BFS y un conjunto para rastrear las posiciones visitadas   const queue = \[\[origenX, origenY, 0]]; // \[x, y, steps]   const visited = new Set();   visited.add(`${origenX},${origenY}`);   // Paso 4: Realizar la BFS   while (queue.length > 0) {   const \[currentX, currentY, steps] = queue.shift();   // Si alcanzamos el objetivo, devolvemos el número de pasos   if (currentX === objetivoX && currentY === objetivoY) {   return steps;   }   // Explorar los movimientos posibles   for (const \[dx, dy] of directions) {   const nextX = currentX + dx;   const nextY = currentY + dy;   // Normalizar las coordenadas para la simetría del tablero y evitar visitar repetidamente la misma posición   if (!visited.has(`${nextX},${nextY}`)) {   visited.add(`${nextX},${nextY}`);   queue.push(\[nextX, nextY, steps + 1]);   }   }   }   // El problema garantiza que siempre hay una solución, así que no alcanzaremos aquí.   return -1; } // Ejemplo de uso: const response = minKnightMoves(0, 0, 5, 5); console.log(response); // Output: 4
Mi solución:
def generate_possible_moves(x, y): # Generate clockwise positions return [(x+1, y+2), (x+2, y+1), (x+2, y-1), (x+1, y-2), (x-1, y-2), (x-2, y-1), (x-2, y+1), (x-1, y+2)] def minKnightMoves(originX, originY, targetX, targetY): current_postion = (originX, originY) if current_postion == (targetX, targetY): return 0 queue = [current_postion] moves = 0 while queue: for _ in range(len(queue)): current_postion = queue.pop(0) x, y = current_postion possible_moves = generate_possible_moves(x, y) for move in possible_moves: queue.append(move) moves += 1 if (targetX, targetY) in queue: break return moves print(minKnightMoves(0, 0, 5, 5)) print(minKnightMoves(0, 0, 1, 2)) print(minKnightMoves(0, 0, 0, 0)) print(minKnightMoves(0, 0, 3, 3)) print(minKnightMoves(0, 0, 2, 2))
from collections import deque def minKnightMoves(origenX, origenY, objetivoX, objetivoY): # Posibles movimientos del caballo en el tablero movimientos = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)] # BFS cola = deque([(origenX, origenY, 0)]) visitado = set() while cola: x, y, pasos = cola.popleft() if x == objetivoX and y == objetivoY: return pasos for dx, dy in movimientos: nuevo_x, nuevo_y = x + dx, y + dy if (nuevo_x, nuevo_y) not in visitado: visitado.add((nuevo_x, nuevo_y)) cola.append((nuevo_x, nuevo_y, pasos + 1)) return -1
Para probar con este
from collections import dequedef minKnightMoves(origenX, origenY, objetivoX, objetivoY): # Posibles movimientos del caballo en el tablero movimientos = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)] # BFS cola = deque([(origenX, origenY, 0)]) visitado = set() while cola: x, y, pasos = cola.popleft() if x == objetivoX and y == objetivoY: return pasos for dx, dy in movimientos: nuevo_x, nuevo_y = x + dx, y + dy if (nuevo_x, nuevo_y) not in visitado: visitado.add((nuevo_x, nuevo_y)) cola.append((nuevo_x, nuevo_y, pasos + 1)) return -1
Mi solución no pasa el segundo test, pero a mí me funciona bien.
Este código filtra algunos movimientos, lo que lo hace más eficiente.
PD: Vengo desde la próxima clase y me faltó poner una forma de verificar si ya había visitado un lugar en el tablero.
def minKnightMoves(origenX, origenY, objetivoX, objetivoY): # Tu código aquí 👇 saltos = 0 movimientos = [(origenX,origenY)] while movimientos: for _ in range(len(movimientos)): mov = movimientos.pop(0) x = mov[0] y = mov[1] current_modulo = int(((x - objetivoX )**2 + (y - objetivoY)**2)**(1/2)) print(current_modulo) if x == objetivoX and y == objetivoY: print("-------------------") print(x,y) print("-------------------") return saltos for next_mov in [(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,1),(-2,-1)]: """mi pequeño aporte para mejorar un poco el rendimineto""" new_modulo = int((((x + next_mov[0] )- objetivoX )**2 + ((y + next_mov[1]) - objetivoY)**2)**(1/2)) if current_modulo-1 > new_modulo or new_modulo <= 2: movimientos.append((x + next_mov[0] , y + next_mov[1] )) saltos += 1 return saltos```
