Playground: Minimum Knights Moves

Clase 24 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles

Contenido del curso

Introducción

DFS

BFS

Backtrack

Próximos pasos

Tomar examen

Comentarios

Cristian Toro

student•

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

student•

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

student•

My Solution!!

José Ramón García

student•

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

student•

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

student•

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

student•

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

student•

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

Grafos y Árboles: Estructuras de Datos Avanzadas

Estructuras de Datos: Introducción a Árboles y Sus Propiedades

Recursión: Concepto y Aplicaciones Prácticas con Ejemplos

Aplicaciones Prácticas de Grafos en Tecnología e Industria

Representación de Grafos: Matriz y Lista de Adyacencia

DFS

Búsqueda en Profundidad (DFS) en Árboles y Grafos

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

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

Recorridos y Profundidad en Árboles Binarios y Enearios

Suma de Caminos en Árboles Binarios

Suma de Números de Raíz a Hoja en Árboles

Playground: Sum Root to Leaf Numbers

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

Resolución del Problema de Número de Islas con DFS

Conteo de Islas en Matrices con DFS

Playground: Number of Islands

Implementación de "Número de Islas" con Recursión en Python

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

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

BFS

Algoritmo BFS: Recorrido en Anchura de Grafos y Árboles

Implementación de BFS en Árboles usando Python

Movimiento mínimo de caballo en ajedrez infinito

Resolviendo el Problema Mínimo de Movimiento del Caballo en Ajedrez