0
matrix_aux_for_circuit = [
    [None,    None,  'd', None,  'c'],
    [None, "start", None,  200,  'b'],
    [None,     'f',  'e', None, None],
]

starting_point_box = (1, 1) #En este caso seria la celda de fila 1 y columna 1

circuit_list = []

el punto de inicio es el de la casilla indicada con la tupla starting_point_box = (1, 1), coloca en circuit_list = [] las coordenadas de este primer punto, en este caso circuit_list = [(1, 1)] sobre ese punto intentar empezar con un movimiento horizontal (es decir sobre esa misma fila) hacia la izquierda hasta encontrarse con un casillero que contenga un elemento que no sea None

Si sobre esa fila hacia la izquierda no encuentra ningún casillero cuyo contenido no es None, entonces debe intentar buscar un casillero cuyo contenido no sea None hacia la derecha, y si lo encuentra guardar las coordenadas de la celda en donde lo encuentra Si sobre esa fila hacia la izquierda encuentra algún casillero cuyo contenido no es None, entonces guarda las coordenadas de esta celda en en circuit_list = [] , en este caso circuit_list = [(1, 1), (1, 4)] Si ni hacia la izquierda y ni hacia la derecha de esa fila, hubiese encontrado alguna celda que tuviese un elemento que no sea None entonces imprimir "no puede formarse un circuito"

En este caso, si encontró hacia la izquierda en la casilla de coordenadas (1, 4), y ahora como el anterior movimiento era horizontal, entonces el siguiente tendrá que ser vertical (se van alternando) por lo que prueba primero hacia arriba, y en este caso encuentra que la celda (0, 4) tiene un elemento que no es None, por lo que debería guardar las coordenadas en circuit_list = [(1, 1), (1, 4), (0, 4)] pero si no hubiese encontrado ninguna celda que tenga un elemento que no sea None hacia arriba entonces tendría que haber probado buscar si hacia abajo en esa misma columna hay alguna casilla que no tenga un elemento que no sea None y guardar sus coordenadas Si ni hacia la arriba y ni hacia la abajo de esa columna, hubiese encontrado alguna celda que tuviese un elemento que no sea None entonces imprimir "no puede formarse un circuito"

En este caso, si encontró hacia arriba en la casilla de coordenadas (0, 4), y ahora como el anterior movimiento era vertical, entonces el siguiente tendrá que ser horizontal (se van alternando) por lo que prueba primero hacia la izquierda de (0, 4) , pero en este caso a su izquierda no hay ningún casillero que no tenga None, por lo que probara hacia la derecha de (0, 4) y de este modo encontraría que la casilla de coordenadas (0, 2) la cual tiene un elemento diferente de None, por lo que guarda sus coordendas en circuit_list = [(1, 1), (1, 4), (0, 4), (0, 2)]

En este caso, si encontro hacia la derecha en la casilla de coordenadas (0, 2), y ahora como el anterior movimiento era horizontal, entonces el siguiente tendrá que ser vertical (se van alternando) por lo que prueba primero hacia arriba de (0, 2) , pero en este caso hacia arriba no hay ningún casillero que no tenga None, por lo que probara hacia abajo de (0, 2) y de este modo encontraría que la casilla de coordenadas (2, 2) la cual tiene un elemento diferente de None, por lo que guarda sus coordenadas en circuit_list = [(1, 1), (1, 4), (0, 4), (0, 2), (2, 2)]

En este caso, si encontró hacia abajo en la casilla de coordenadas (2, 2), y ahora como el anterior movimiento era vertical, entonces el siguiente tendrá que ser horizontal (se van alternando) por lo que prueba primero hacia la izquierda de (2, 2) , pero en este caso hacia su izquierda no hay ningún casillero que no tenga None, por lo que probara hacia la derecha de (2, 2) y de este modo encontraría que la casilla de coordenadas (2, 1) la cual tiene un elemento diferente de None, por lo que guarda sus coordenadas en circuit_list = [(1, 1), (1, 4), (0, 4), (0, 2), (2, 2), (2, 1)]

Y como el movimiento anterior era horizontal este movimiento sera vertical, entonces probara ir hacia arriba de (2, 1) y como logro llegar al punto de inicio (1, 1) entonces debe terminar el circuito e imprimir las coordenadas de cada una de las casillas que conforman los vértices del circuito circuit_list = [(1, 1), (1, 4), (0, 4), (0, 2), (2, 2), (2, 1), (1, 1)] Si no hubiese encontrado a un casillero que no sea None hacia arriba tendría que haber probado buscarlo hacia abajo

Para solucionar este problema, puedes seguir los siguientes pasos:

  • Comience en el punto de partida especificado.
  • Explora horizontal y verticalmente desde cada punto para encontrar el siguiente vértice no visitado (No puede ir 2 veces seguidas en desplazamiento horizontal o 2 veces en desplazamiento vertical, pero debe alternarse).
  • Añade este vértice a la lista de vértices del circuito y continúa explorando desde este nuevo vértice.
  • Repite el proceso hasta que hayas encontrado al menos tres vértices adicionales y hayas regresado al punto de partida.

El tipo de algoritmo que podría resolver este problema es un algoritmo de búsqueda en grafo con restricciones específicas. Este algoritmo exploraría el espacio de posibles movimientos dentro de la matriz, asegurándose de alternar entre movimientos horizontales y verticales, y evitando visitar una celda más de una vez, excepto el punto de partida. En este caso, una posible salida u output correcto es circuit_list = [(1, 1), (1, 4), (0, 4), (0, 2), (2, 2), (2, 1), ( 1, 1)], tenga en cuenta que los circuitos nunca pueden tomar el mismo cuadrado como vértice dos veces excepto el cuadrado inicial.

Este es mi código pero se traba a la mitad del trazado del circuito, quedando así [(1, 1), (2, 1), (2, 2)]:

matrix_aux_for_circuit = [
    [None,    None,  'd', None,  'c'],
    [None, "start", None,  200,  'b'],
    [None,     'f',  'e', None, None],
]

starting_point_box = (1, 1)

circuit_list = []

def find_next_vertex(matrix, current_position, last_move):
    row, col = current_position
    moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # Right, Left, Down, Up

    if last_move == 'horizontal':
        moves = moves[2:]  # Exclude vertical moves
    elif last_move == 'vertical':
        moves = moves[:2]  # Exclude horizontal moves

    for move in moves:
        new_row, new_col = row + move[0], col + move[1]
        if 0 <= new_row < len(matrix) and 0 <= new_col < len(matrix[0]):
            if matrix[new_row][new_col] is not None:
                return (new_row, new_col), move

    return None, None

def traverse_circuit(matrix, start_position):
    current_position = start_position
    last_move = None
    circuit_list.append(start_position)

    while True:
        next_position, move = find_next_vertex(matrix, current_position, last_move)
        if next_position is None:
            print("No se puede formar un circuito")
            return None

        circuit_list.append(next_position)
        last_move = 'vertical' if move[0] != 0 else 'horizontal'
        current_position = next_position

        if next_position == start_position and len(circuit_list) >= 4:
            break

    return circuit_list

traverse_circuit(matrix_aux_for_circuit, starting_point_box)
print(circuit_list)

11
  • Mira Cómo preguntar para que tu pregunta sea mejor recibida. También, aprovecha y haz el recorrido de bienvenida para entender mejor cómo funcionamos y de paso obtener tu primera medalla! Y tu idea es que alguien haga el algoritmo por vos?? que fue lo que intentaste hasta ahora???
    – gbianchi
    Commented el 21 mar. a las 12:21
  • @gbianchi tengo el codigo, pero no se si aporta a la pregunta porque se traba a mitad del trazado del circuito. vale la pena que lo suba? Commented el 21 mar. a las 12:24
  • Mejor resume las reglas del problema. Hay demasiado texto.
    – Candid Moe
    Commented el 21 mar. a las 12:38
  • Si. con el codigo no parece que queres que alguien lo haga por vos, si no encontrar el problema. De paso.. se traba que quiere decir? es un error? o deja de encontrar posiciones o que es lo que pasa?
    – gbianchi
    Commented el 21 mar. a las 12:42
  • @gbianchi Ese codigo traba el circuito en [(1, 1), (2, 1), (2, 2)], es correcto que empiece en (1, 1), luego hace una búsqueda vertical (de columna) y encuentra al (2, 1) abajo, y luego alterna a una busqueda horizontal y encuentra a su derecha el (2,2), hasta ahi va correcto pero el problema es que se detiene, aunque eso esta mal porque si hiciese la busqueda vertical notaria que arriba esta (0, 2) y podria continuar formando el circuito Commented el 21 mar. a las 12:46

1 respuesta 1

0

Aqui tienes una posible solución usando recursión:

matrix_aux_for_circuit = [
    [None,    None,  'd', None,  'c'],
    [None, "start", None,  200,  'b'],
    [None,     'f',  'e', None, None],
]

starting_point_box = (1, 1)

def f(*nodes):
    if nodes[0]==nodes[-1] and len(nodes)>1: return (nodes,)
    y,x = nodes[-1]
    opts = ((y,n) for n in range(len(matrix_aux_for_circuit[y]))) if len(nodes)%2 else ((n,x) for n in range(len(matrix_aux_for_circuit)))
    return (r for i,j in opts if matrix_aux_for_circuit[i][j] is not None and (i,j)!=(y,x) and (i,j) not in nodes[1:] for r in f(*nodes,(i,j)))

try:
    circuit_list = list(next(f(starting_point_box)))
    print(circuit_list)
except StopIteration:
    print("no puede formarse un circuito")

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.