Playground: Minimum Knights Moves

Curso de Algoritmos Avanzados: Grafos y Árboles

Contenido del curso

Introducción

DFS

BFS

Backtrack

Próximos pasos

Tomar examen

Playground: Minimum Knights Moves

Comentarios8

Cristian Toro

Estudiante

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

Cristian Toro

Estudiante

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.

John Eduard Meneses González

Estudiante

My Solution!!

José Ramón García

Estudiante

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

Michael Martinez

Company_admin

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) {

&#x20;   // Paso 1: Normalizar las coordenadas porque el tablero es simétrico

&#x20;   objetivoX = Math.abs(objetivoX);

&#x20;   objetivoY = Math.abs(objetivoY);

&#x20;  &#x20;

&#x20;   // Paso 2: Definir las posibles direcciones del movimiento del caballo

&#x20;   const directions = \[

&#x20;       \[2, 1], \[1, 2], \[-1, 2], \[-2, 1],

&#x20;       \[-2, -1], \[-1, -2], \[1, -2], \[2, -1]

&#x20;   ];



&#x20;   // Paso 3: Crear una cola para la BFS y un conjunto para rastrear las posiciones visitadas

&#x20;   const queue = \[\[origenX, origenY, 0]]; // \[x, y, steps]

&#x20;   const visited = new Set();

&#x20;   visited.add(`${origenX},${origenY}`);



&#x20;   // Paso 4: Realizar la BFS

&#x20;   while (queue.length > 0) {

&#x20;       const \[currentX, currentY, steps] = queue.shift();



&#x20;       // Si alcanzamos el objetivo, devolvemos el número de pasos

&#x20;       if (currentX === objetivoX && currentY === objetivoY) {

&#x20;           return steps;

&#x20;       }



&#x20;       // Explorar los movimientos posibles

&#x20;       for (const \[dx, dy] of directions) {

&#x20;           const nextX = currentX + dx;

&#x20;           const nextY = currentY + dy;



&#x20;           // Normalizar las coordenadas para la simetría del tablero y evitar visitar repetidamente la misma posición

&#x20;           if (!visited.has(`${nextX},${nextY}`)) {

&#x20;               visited.add(`${nextX},${nextY}`);

&#x20;               queue.push(\[nextX, nextY, steps + 1]);

&#x20;           }

&#x20;       }

&#x20;   }



&#x20;   // El problema garantiza que siempre hay una solución, así que no alcanzaremos aquí.

&#x20;   return -1;

}



// Ejemplo de uso:

const response = minKnightMoves(0, 0, 5, 5);

console.log(response); // Output: 4

Carlos Hernandez

Estudiante

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))

Jose Miguel Murillo Cediel

Estudiante

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

Jose Miguel Murillo Cediel

Estudiante

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

Ivan Scaglioni

Estudiante

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```

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

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) {

&#x20;   // Paso 1: Normalizar las coordenadas porque el tablero es simétrico

&#x20;   objetivoX = Math.abs(objetivoX);

&#x20;   objetivoY = Math.abs(objetivoY);

&#x20;  &#x20;

&#x20;   // Paso 2: Definir las posibles direcciones del movimiento del caballo

&#x20;   const directions = \[

&#x20;       \[2, 1], \[1, 2], \[-1, 2], \[-2, 1],

&#x20;       \[-2, -1], \[-1, -2], \[1, -2], \[2, -1]

&#x20;   ];

&#x20;   // Paso 3: Crear una cola para la BFS y un conjunto para rastrear las posiciones visitadas

&#x20;   const queue = \[\[origenX, origenY, 0]]; // \[x, y, steps]

&#x20;   const visited = new Set();

&#x20;   visited.add(`${origenX},${origenY}`);

&#x20;   // Paso 4: Realizar la BFS

&#x20;   while (queue.length > 0) {

&#x20;       const \[currentX, currentY, steps] = queue.shift();

&#x20;       // Si alcanzamos el objetivo, devolvemos el número de pasos

&#x20;       if (currentX === objetivoX && currentY === objetivoY) {

&#x20;           return steps;

&#x20;       }

&#x20;       // Explorar los movimientos posibles

&#x20;       for (const \[dx, dy] of directions) {

&#x20;           const nextX = currentX + dx;

&#x20;           const nextY = currentY + dy;

&#x20;           // Normalizar las coordenadas para la simetría del tablero y evitar visitar repetidamente la misma posición

&#x20;           if (!visited.has(`${nextX},${nextY}`)) {

&#x20;               visited.add(`${nextX},${nextY}`);

&#x20;               queue.push(\[nextX, nextY, steps + 1]);

&#x20;           }

&#x20;       }

&#x20;   }

&#x20;   // El problema garantiza que siempre hay una solución, así que no alcanzaremos aquí.

&#x20;   return -1;

}

// Ejemplo de uso:

const response = minKnightMoves(0, 0, 5, 5);

console.log(response); // Output: 4

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

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```

Playground: Minimum Knights Moves

Introducción

Qué son los grafos y cómo modelan el mundo

Qué es un árbol en estructuras de datos

Qué es la recursión en programación

Grafos en el mundo real que ya conoces

Representación de Grafos: Matriz y Lista de Adyacencia

DFS

Cómo recorre nodos el algoritmo DFS

Implementación de DFS recursivo para búsqueda en árboles

Búsqueda en Profundidad (DFS) para Grafos: Enfoque Iterativo y Recursivo

Inorder, Preorder y Postorder en árboles

Suma de caminos raíz a hoja en árboles

Suma de caminos raíz a hoja con DFS

Playground: Sum Root to Leaf Numbers

Implementación de Algoritmo DFS en Árboles Binarios con Golang

Número de islas con DFS en matrices

Problema de islas resuelto con DFS

Playground: Number of Islands

Número de islas con DFS recursivo en Python

Ejercicios Prácticos de Búsqueda en Profundidad (DFS)

Algoritmos de Búsqueda en Profundidad (DFS) en Problemas Comunes

BFS

Cómo BFS recorre grafos por niveles

Implementación de BFS con colas en Python

Mínimos movimientos del caballo en ajedrez

Minimum Knight's Move con BFS