Playground: Shortest Bridge Between Islands

Curso de Algoritmos Avanzados: Grafos y Árboles

Contenido del curso

Introducción

DFS

BFS

Backtrack

Próximos pasos

Tomar examen

Playground: Shortest Bridge Between Islands

import math

def check_spot(islands, i, j):
    for index, islands_spots in islands.items():
        if (i - 1, j) in islands_spots or (i, j-1) in islands_spots or (i + 1, j) in islands_spots or (i, j + 1) in islands_spots:
            return index
    return -1

def get_islands(input_map):
    islands = {}

    for i, row in enumerate(input_map):
        for j, column in enumerate(row):
            if column == "0":
                continue
            else:
                # Check contiguous spots
                found_index = check_spot(islands, i, j)
                # Clock-wise order starting from left
                if found_index == -1:
                    next_index = len(islands.items())
                    islands[next_index] = [(i, j)]
                else:
                    islands[found_index].append((i, j))
    return islands

def generate_next_steps(islands, i, j, destination):
    next_steps = []

    if (i - 1) >= 0 and islands[i-1][j] == "0" or (i-1,j) == destination:
        next_steps.append((i-1, j))
    if (j + 1) < len(islands[i]) and islands[i][j+1] == "0" or (i,j+1) == destination:
        next_steps.append((i, j+1))
    if (i + 1) < len(islands) and islands[i+1][j] == "0" or (i+1,j) == destination:
        next_steps.append((i+1, j))
    if (j - 1) >= 0 and islands[i][j-1] == "0" or (i,j-1) == destination:
        next_steps.append((i, j-1))
    
    return next_steps


def get_shortest_bridge_between_islands(input_map):
    islands = get_islands(input_map)
    
    shortest_path_data = {
        "spot_1" : None,
        "spot_2" : None,
        "distance": 1000000
    }

    for i1, j1 in islands[0]:
        for i2, j2 in islands[1]:
            spots_distance = math.dist([i1, j1], [i2, j2])
            if spots_distance < shortest_path_data["distance"]:
                shortest_path_data['spot_1'] = (i1, j1)
                shortest_path_data['spot_2'] = (i2, j2)
                shortest_path_data['distance'] = spots_distance
    
    origin, destination = shortest_path_data["spot_1"], shortest_path_data["spot_2"]
    print(origin, destination)

    bridge_amount = -1
    steps = [origin]


    while steps:
        if destination in steps: 
            break
        for _ in range(len(steps)):
            current_step = steps.pop(0)
            i, j = current_step
            next_steps = generate_next_steps(input_map, i, j, destination)
            for next_step in next_steps:
                if not next_step in steps:
                    steps.append(next_step)
        bridge_amount += 1
        print(steps)
        
    return bridge_amount
    


input_map = [
    ["1","1","1","1","1"],
    ["1","0","0","0","1"],
    ["1","0","1","0","1"],
    ["1","0","0","0","1"],
    ["1","1","1","1","1"],
]
response = get_shortest_bridge_between_islands(input_map)
print(response)

from typing import List

from collections import deque

class Solution:

&#x20;   def shortestBridge(self, grid: List\[List\[int]]) -> int:

&#x20;       \# Step 1: Find the first island and mark it, adding boundary cells to the queue

&#x20;       found = False

&#x20;       queue = deque()  # Boundary of the first island for expansion

&#x20;       for i in range(len(grid)):

&#x20;           for j in range(len(grid\[i])):

&#x20;               if grid\[i]\[j] == 1:

&#x20;                   self.mark\_first\_island(grid, i, j, queue)  # Mark first island and add boundaries to queue

&#x20;                   found = True

&#x20;                   break

&#x20;           if found:

&#x20;               break

&#x20;       \# Step 2: Expand BFS from the first island to reach the second island

&#x20;       return self.expand(grid, queue)

&#x20;   def mark\_first\_island(self, grid: List\[List\[int]], x: int, y: int, queue: deque):

&#x20;       directions = \[(1, 0), (-1, 0), (0, 1), (0, -1)]

&#x20;       grid\[x]\[y] = 2  # Mark the island as visited

&#x20;       queue\_for\_marking = deque(\[(x, y)])

&#x20;       while queue\_for\_marking:

&#x20;           x, y = queue\_for\_marking.popleft()

&#x20;           for direction in directions:

&#x20;               new\_x, new\_y = x + direction\[0], y + direction\[1]

&#x20;               if 0 <= new\_x < len(grid) and 0 <= new\_y < len(grid\[0]):

&#x20;                   if grid\[new\_x]\[new\_y] == 1:

&#x20;                       grid\[new\_x]\[new\_y] = 2  # Mark connected land

&#x20;                       queue\_for\_marking.append((new\_x, new\_y))

&#x20;                   elif grid\[new\_x]\[new\_y] == 0:

&#x20;                       \# Add boundary water cells to queue for BFS expansion

&#x20;                       queue.append((x, y))

&#x20;   def expand(self, grid: List\[List\[int]], queue: deque) -> int:

&#x20;       directions = \[(1, 0), (-1, 0), (0, 1), (0, -1)]

&#x20;       steps = 0

&#x20;       \# Start BFS to expand towards the second island

&#x20;       while queue:

&#x20;           for \_ in range(len(queue)):

&#x20;               x, y = queue.popleft()

&#x20;               for direction in directions:

&#x20;                   new\_x, new\_y = x + direction\[0], y + direction\[1]

&#x20;                   if 0 <= new\_x < len(grid) and 0 <= new\_y < len(grid\[0]):

&#x20;                       if grid\[new\_x]\[new\_y] == 1:  # Found the second island

&#x20;                           return steps

&#x20;                       if grid\[new\_x]\[new\_y] == 0:  # Expand to water, turn it into land

&#x20;                           grid\[new\_x]\[new\_y] = 2

&#x20;                           queue.append((new\_x, new\_y))

&#x20;           steps += 1  # Increase the step count as we expand one layer outwards

&#x20;       return -1  # Should never reach here if there are two islands

import math

def check_spot(islands, i, j):
    for index, islands_spots in islands.items():
        if (i - 1, j) in islands_spots or (i, j-1) in islands_spots or (i + 1, j) in islands_spots or (i, j + 1) in islands_spots:
            return index
    return -1

def get_islands(input_map):
    islands = {}

    for i, row in enumerate(input_map):
        for j, column in enumerate(row):
            if column == "0":
                continue
            else:
                # Check contiguous spots
                found_index = check_spot(islands, i, j)
                # Clock-wise order starting from left
                if found_index == -1:
                    next_index = len(islands.items())
                    islands[next_index] = [(i, j)]
                else:
                    islands[found_index].append((i, j))
    return islands

def generate_next_steps(islands, i, j, destination):
    next_steps = []

    if (i - 1) >= 0 and islands[i-1][j] == "0" or (i-1,j) == destination:
        next_steps.append((i-1, j))
    if (j + 1) < len(islands[i]) and islands[i][j+1] == "0" or (i,j+1) == destination:
        next_steps.append((i, j+1))
    if (i + 1) < len(islands) and islands[i+1][j] == "0" or (i+1,j) == destination:
        next_steps.append((i+1, j))
    if (j - 1) >= 0 and islands[i][j-1] == "0" or (i,j-1) == destination:
        next_steps.append((i, j-1))
    
    return next_steps


def get_shortest_bridge_between_islands(input_map):
    islands = get_islands(input_map)
    
    shortest_path_data = {
        "spot_1" : None,
        "spot_2" : None,
        "distance": 1000000
    }

    for i1, j1 in islands[0]:
        for i2, j2 in islands[1]:
            spots_distance = math.dist([i1, j1], [i2, j2])
            if spots_distance < shortest_path_data["distance"]:
                shortest_path_data['spot_1'] = (i1, j1)
                shortest_path_data['spot_2'] = (i2, j2)
                shortest_path_data['distance'] = spots_distance
    
    origin, destination = shortest_path_data["spot_1"], shortest_path_data["spot_2"]
    print(origin, destination)

    bridge_amount = -1
    steps = [origin]


    while steps:
        if destination in steps: 
            break
        for _ in range(len(steps)):
            current_step = steps.pop(0)
            i, j = current_step
            next_steps = generate_next_steps(input_map, i, j, destination)
            for next_step in next_steps:
                if not next_step in steps:
                    steps.append(next_step)
        bridge_amount += 1
        print(steps)
        
    return bridge_amount
    


input_map = [
    ["1","1","1","1","1"],
    ["1","0","0","0","1"],
    ["1","0","1","0","1"],
    ["1","0","0","0","1"],
    ["1","1","1","1","1"],
]
response = get_shortest_bridge_between_islands(input_map)
print(response)

from typing import List

from collections import deque

class Solution:

&#x20;   def shortestBridge(self, grid: List\[List\[int]]) -> int:

&#x20;       \# Step 1: Find the first island and mark it, adding boundary cells to the queue

&#x20;       found = False

&#x20;       queue = deque()  # Boundary of the first island for expansion

&#x20;       for i in range(len(grid)):

&#x20;           for j in range(len(grid\[i])):

&#x20;               if grid\[i]\[j] == 1:

&#x20;                   self.mark\_first\_island(grid, i, j, queue)  # Mark first island and add boundaries to queue

&#x20;                   found = True

&#x20;                   break

&#x20;           if found:

&#x20;               break

&#x20;       \# Step 2: Expand BFS from the first island to reach the second island

&#x20;       return self.expand(grid, queue)

&#x20;   def mark\_first\_island(self, grid: List\[List\[int]], x: int, y: int, queue: deque):

&#x20;       directions = \[(1, 0), (-1, 0), (0, 1), (0, -1)]

&#x20;       grid\[x]\[y] = 2  # Mark the island as visited

&#x20;       queue\_for\_marking = deque(\[(x, y)])

&#x20;       while queue\_for\_marking:

&#x20;           x, y = queue\_for\_marking.popleft()

&#x20;           for direction in directions:

&#x20;               new\_x, new\_y = x + direction\[0], y + direction\[1]

&#x20;               if 0 <= new\_x < len(grid) and 0 <= new\_y < len(grid\[0]):

&#x20;                   if grid\[new\_x]\[new\_y] == 1:

&#x20;                       grid\[new\_x]\[new\_y] = 2  # Mark connected land

&#x20;                       queue\_for\_marking.append((new\_x, new\_y))

&#x20;                   elif grid\[new\_x]\[new\_y] == 0:

&#x20;                       \# Add boundary water cells to queue for BFS expansion

&#x20;                       queue.append((x, y))

&#x20;   def expand(self, grid: List\[List\[int]], queue: deque) -> int:

&#x20;       directions = \[(1, 0), (-1, 0), (0, 1), (0, -1)]

&#x20;       steps = 0

&#x20;       \# Start BFS to expand towards the second island

&#x20;       while queue:

&#x20;           for \_ in range(len(queue)):

&#x20;               x, y = queue.popleft()

&#x20;               for direction in directions:

&#x20;                   new\_x, new\_y = x + direction\[0], y + direction\[1]

&#x20;                   if 0 <= new\_x < len(grid) and 0 <= new\_y < len(grid\[0]):

&#x20;                       if grid\[new\_x]\[new\_y] == 1:  # Found the second island

&#x20;                           return steps

&#x20;                       if grid\[new\_x]\[new\_y] == 0:  # Expand to water, turn it into land

&#x20;                           grid\[new\_x]\[new\_y] = 2

&#x20;                           queue.append((new\_x, new\_y))

&#x20;           steps += 1  # Increase the step count as we expand one layer outwards

&#x20;       return -1  # Should never reach here if there are two islands

Playground: Shortest Bridge Between Islands

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

Playground: Minimum Knights Moves

Resolución de Problemas de Caballos de Ajedrez con BFS en Python

Propagación BFS en Rotting Oranges

Resolución de Rotting Oranges usando BFS

Playground: Rotting Oranges

Implementación de BFS para naranjas podridas

Puente más corto entre islas con BFS

Shortest Bridge: combina DFS y BFS

Playground: Shortest Bridge Between Islands

Shortest Bridge con DFS y BFS en Python

Búsqueda en anchura: Ejercicios prácticos y aplicaciones

Ejercicios avanzados de búsqueda en anchura (BFS) en programación

Backtrack

Backtracking para encontrar soluciones válidas

Combinaciones de letras en teclado telefónico

Combinaciones de teclado con backtracking

Generación de combinaciones de letras con teclados numéricos en C++

Playground: Letter Combinations of a Phone Number

Generación de Direcciones IP Válidas a partir de Cadenas Numéricas

Backtracking para generar IPs válidas

Playground: Restore IP Addresses

Búsqueda de Palabras en Matrices: Solución y Complejidad

Word Search con DFS y backtracking

Playgrund: Word Search

Búsqueda de palabras en matrices con DFS

Resolución del problema de las n reinas en ajedrez

Ejercicios de Backtracking: Combinaciones y Permutaciones

Combinaciones y Permutaciones con Backtracking

Próximos pasos

Dijkstra y topological sort en grafos

Qué sigue después de aprender grafos