Clase 23 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles
Contenido del curso
Daniel Ortiz
JOHANBERT MOSQUERA
Diego Portillo
Mario Alberto Hernández Pintor
Miguel Angel Reyes Moreno
Yojan Antonio Pardo Zabala
No es el mas efectivo pero es trabajo honesto :V
import math MOVEMENTS = [ (2, 1), (1, 2), (-2, 1), (-1, 2), (2, -1), (1, -2), (-2, -1), (-1, -2) ] def distance_between_points(x1, y1, x2, y2): return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2) def move_point(x: int, y: int, search_point: tuple, previous_point, previous_distance=0): list_possible_moves = [] for movement_index in range(0, len(MOVEMENTS)): next_x = x + MOVEMENTS[movement_index][0] next_y = y + MOVEMENTS[movement_index][1] distance = distance_between_points(next_x, next_y, search_point[0], search_point[1]) if distance == 0: return None if (next_x >= search_point[0] and next_y >= search_point[1]) \ or (distance > distance_between_points(0, 0, search_point[0], search_point[1])): continue list_possible_moves.append([next_x, next_y, previous_distance + distance, previous_point + [(next_x, next_y)]]) list_possible_moves.sort(key=lambda x: x[2]) return list_possible_moves def horse_steps(x, y): initial = [[0, 0]] jumps = 1 while jumps < 1000: jumps = jumps + 1 next_step = [] for step in initial: response = move_point(x=step[0], y=step[1], search_point=(x, y), previous_point=[(step[0], step[1])]) if response is None: return jumps next_step = next_step + response if next_step is None: print('No more steps') break initial = next_step if __name__ == '__main__': assert horse_steps(2, 1) == 2 assert horse_steps(5, 5) == 5 assert horse_steps(5, 0) == 4
jajajaja trabajo honesto dice jajajaj
Solution:
def minimum_knight_moves(x_start, y_start, x_end, y_end): moves = 0 options = [ (1,2), (2,1), (-1,2), (-2,1), (1,-2), (2,-1), (-1,-2), (-2,-1) ] queue = [(x_start, y_start)] while queue: if (x_end, y_end) in queue: break for coordinates in range(len(queue)): # important: here we use FIFO to follow the order in which elements are added x, y = queue.pop(0) print(x, y) for option in options: x_add, y_add = option queue.append((x+x_add, y+y_add)) moves += 1 return moves print(minimum_knight_moves(0,0,5,5) == 4)
Review comparing with teacher's code (mine has a bug):
Comparison
Correctness — the most important difference
The first solution has a critical bug: it checks (x_end, y_end) in queue to verify if the destination was reached, but this searches the entire queue including future positions that haven't actually been "reached" yet at that level. On top of that, it has no visited set, so the queue grows infinitely — on a board without boundaries, it would never finish or take extremely long.
The second solution is correct: it checks the destination when dequeuing each position, and uses visited to avoid revisiting nodes.
queue.pop(0) vs deque.popleft() complexity
python
# Solution 1 — Python list queue.pop(0) # O(n) — shifts all elements # Solution 2 — deque queue.popleft() # O(1) — designed for this
Using a list as a queue is a classic performance mistake. For BFS you should always use deque.
BFS structure
The first attempts level-by-level BFS with an inner loop, which is a valid way to track steps, but it's poorly implemented because it mixes the destination check outside the main loop. The second carries the step counter directly in the queue as (position, steps), which is cleaner and less error-prone.
Visited set
Without visited, the first solution revisits positions infinitely. This is its most serious flaw — in practice the program never terminates for large inputs.
Verdict
Solution 1Solution 2
Correct BFS
❌
✅
Visited set
❌
✅
Efficient queue
❌ O(n) pop
✅ O(1) pop
Always terminates
❌
✅
The second solution is clearly superior in every aspect. The first has the right intuition but fails in execution.
En javascript:
código en Python:
from queue import Queue
from typing import List
class Solution:
def minimum_knight_moves(self, target: List[int]) -> int:
# The knight moves in 8 possible directions
directions = [
(2, 1), (2, -1), (-2, 1), (-2, -1),
(1, 2), (1, -2), (-1, 2), (-1, -2)
]
queue = Queue()
queue.put((0, 0, 0)) # (current_x, current_y, step_count)
visited_positions = set()
visited_positions.add((0, 0))
target_x, target_y = abs(target[0]), abs(target[1])
# BFS algorithm
while not queue.empty():
# Dequeue the next position and step count to be processed
current_x, current_y, current_steps = queue.get()
# Check if we've reached the target position
if current_x == target_x and current_y == target_y:
return current_steps
# Explore all possible knight moves
for dx, dy in directions:
new_x = current_x + dx
new_y = current_y + dy
new_position = (abs(new_x), abs(new_y))
# Check if the new position has been visited
if new_position not in visited_positions:
visited_positions.add(new_position)
queue.put((new_x, new_y, current_steps + 1))
# Example usage:
solution = Solution()
print(solution.minimum_knight_moves([2, 1])) # Output: 1
print(solution.minimum_knight_moves([5, 5])) # Output: 4
Esta es mi solución en java, no estoy seguro de si es la mas eficiente (ya que para cada nivel calcula todas las nuevas posiciones posibles posibles) pero funciona, ¿alguna recomendación?
public class MinimumKnightsMoves { public static void main(String[] args) { System.out.println("Welcome to Minimum knights moves!"); System.out.println("in here you can calculate the minimum moves a chess knight needs to move from x,y point to another coordinates in an infinite chess board."); System.out.print("please insert the x coordinate for the initial position: "); final int startX = scanner.nextInt(); System.out.print("please insert the y coordinate for the initial position: "); final int startY = scanner.nextInt(); System.out.println("now you need to insert the destination coordinates..."); System.out.print("insert the x destination coordinate: "); final int destinationX = scanner.nextInt(); System.out.print("insert the y destination coordinate: "); final int destinationY = scanner.nextInt(); System.out.printf("the minimum moves to move from [%d,%d] to [%d,%d] are: [%d]", startX, startY, destinationX, destinationY, calculateMoves(startX, startY, destinationX, destinationY)); } private static int calculateMoves(int startX, int startY, int destinationX, int destinationY) { int moves = 0; if(startX == destinationX && startY == destinationY){ return moves; } Queue<int[]> movements = getPossibleMovementsForKnight(startX, startY); while(!movements.isEmpty()){ moves++; Queue<int[]> newMovements = new LinkedList<>(); while(!movements.isEmpty()) { int[] actualMove = movements.poll(); if (actualMove[0] == destinationX && actualMove[1] == destinationY) { return moves; } newMovements.addAll(getPossibleMovementsForKnight(actualMove[0], actualMove[1])); } movements.addAll(newMovements); } return moves; } private static Queue<int[]> getPossibleMovementsForKnight(int startX, int startY) { System.out.printf("Possible movements for knight at [%d,%d] are: \n", startX, startY); Queue<int[]> moves = new LinkedList<>(); moves.add(new int[] {startX + 2, startY + 1}); System.out.printf("\t [%d,%d]\n", startX + 2, startY + 1); moves.add(new int[] {startX + 1, startY + 2}); System.out.printf("\t [%d,%d]\n", startX + 1, startY + 2); moves.add(new int[] {startX - 2, startY + 1}); System.out.printf("\t [%d,%d]\n", startX - 2, startY + 1); moves.add(new int[] {startX - 1, startY + 2}); System.out.printf("\t [%d,%d]\n", startX - 1, startY + 2); moves.add(new int[] {startX + 2, startY - 1}); System.out.printf("\t [%d,%d]\n", startX + 2, startY - 1); moves.add(new int[] {startX + 1, startY - 2}); System.out.printf("\t [%d,%d]\n", startX + 1, startY - 2); moves.add(new int[] {startX - 2, startY - 1}); System.out.printf("\t [%d,%d]\n", startX - 2, startY - 1); moves.add(new int[] {startX - 1, startY - 2}); System.out.printf("\t [%d,%d]\n", startX - 1, startY - 2); return moves; } }
