[Richard R Richard]

Con los subsistemas subterráneos de su submarino que subsisten de manera subóptima , la única forma de salir de esta cueva pronto es encontrando un camino usted mismo. No solo un camino: la única forma de saber si ha encontrado el mejor camino es encontrarlos todos .

Afortunadamente, los sensores todavía funcionan en su mayor parte, por lo que construye un mapa aproximado de las cuevas restantes (su entrada de rompecabezas). Por ejemplo:

start-A
start-b
A-c
A-b
b-d
A-end
b-end

Esta es una lista de cómo están conectadas todas las cuevas. Empiezas en la cueva nombrada start y tu destino es la cueva nombrada end. Una entrada como b-d significa que la cueva b está conectada a la cueva d, es decir, puede moverse entre ellas.

Entonces, el sistema de cuevas anterior se ve más o menos así:

      start
     /      \
c--A-----b--d
     \      /
      end

Su objetivo es encontrar la cantidad de caminos distintos que comienzan en start, terminan en end y no visitan pequeñas cuevas más de una vez. Hay dos tipos de cuevas: cuevas grandes (escritas en mayúsculas, como A) y cuevas pequeñas (escritas en minúsculas, como b). Sería una pérdida de tiempo visitar una cueva pequeña más de una vez, pero las cuevas grandes son lo suficientemente grandes como para que valga la pena visitarlas varias veces. Por lo tanto, todos los caminos que encuentres deben visitar cuevas pequeñas como máximo una vez , y puedes visitar cuevas grandes tantas veces como quieras .

Dadas estas reglas, hay 10caminos a través de este ejemplo de sistema de cuevas:

start,A,b,A,c,A,end
start,A,b,A,end
start,A,b,end
start,A,c,A,b,A,end
start,A,c,A,b,end
start,A,c,A,end
start,A,end
start,b,A,c,A,end
start,b,A,end
start,b,end

(Cada línea en la lista anterior corresponde a un solo camino; las cuevas visitadas por ese camino se enumeran en el orden en que fueron visitadas y separadas por comas).

Tenga en cuenta que en este sistema de cuevas, la cueva d nunca es visitada por ningún camino: para hacerlo, la cueva b debería ser visitada dos veces (una en el camino a la cueva d y una segunda vez al regresar de la cueva d), y dado que la cueva bes pequeña, esto No se permite.

Aquí hay un ejemplo un poco más grande:

dc-end
HN-start
start-kj
dc-start
dc-HN
LN-dc
HN-end
kj-sa
kj-HN
kj-dc

Los 19 caminos a través de él son los siguientes:

start,HN,dc,HN,end
start,HN,dc,HN,kj,HN,end
start,HN,dc,end
start,HN,dc,kj,HN,end
start,HN,end
start,HN,kj,HN,dc,HN,end
start,HN,kj,HN,dc,end
start,HN,kj,HN,end
start,HN,kj,dc,HN,end
start,HN,kj,dc,end
start,dc,HN,end
start,dc,HN,kj,HN,end
start,dc,end
start,dc,kj,HN,end
start,kj,HN,dc,HN,end
start,kj,HN,dc,end
start,kj,HN,end
start,kj,dc,HN,end
start,kj,dc,end

Finalmente, este ejemplo aún más grande tiene 226caminos a través de él:

fs-end
he-DX
fs-he
start-DX
pj-DX
end-zg
zg-sl
zg-pj
pj-he
RW-he
fs-DX
pj-RW
zg-RW
start-pj
he-WI
zg-he
pj-fs
start-RW

¿Cuántos caminos a través de este sistema de cuevas hay que visitan pequeñas cuevas como máximo una vez?

Que se diviertan !!!

Saludos

[Richard R Richard]

Lo he releido varias veces , no me estan preguntando de que color es el caballo blanco de San Martín.
es decir te dicen en el enunciado que tiene 226 caminos y luego te preguntan cuantos hay... o que me perdí.
 imagino que lo que quieren es que les muestre los caminos separados por comas, eso es?
o bien cual es la porción de todos esos caminos que visitan solo una cueva en minúsculas en todo el recorrido?

Saludos
PD
es claro que dos cuevas en mayúsculas no pueden estar conectadas  o formas loops entre ellas sino hay infinitos caminos.también que si la conexión al árbol de una rama es a través de un nodo en minúsculas esa rama esta prohibida.


Todavia sigo peleandome con geogebra para poder incrustar el archivo en ese formato

[geómetracat]

Te piden el número de caminos. Es decir, que hagas un algoritmo que a partir de la lista de conexiones que te dan te saque el 226.
Esto siempre lo hacen, porque lo que sale ahí es un ejemplo. Si te registras te dan un input (personalizado además, es distinto para cada uno) y tienes que dar el resultado para tu input.

Yo lo he hecho esta mañana en un rato que he tenido, pero no he quedado demasiado satisfecho con mi solución. Por la noche intentaré optimizarlo un poco y lo pondré aquí.

Como siempre, dejo la segunda parte para quien no quiera registrarse o hacer la primera.

--- Part Two ---

After reviewing the available paths, you realize you might have time to visit a single small cave twice. Specifically, big caves can be visited any number of times, a single small cave can be visited at most twice, and the remaining small caves can be visited at most once. However, the caves named start and end can only be visited exactly once each: once you leave the start cave, you may not return to it, and once you reach the end cave, the path must end immediately.

Now, the 36 possible paths through the first example above are:

start,A,b,A,b,A,c,A,end start,A,b,A,b,A,end start,A,b,A,b,end start,A,b,A,c,A,b,A,end start,A,b,A,c,A,b,end start,A,b,A,c,A,c,A,end start,A,b,A,c,A,end start,A,b,A,end start,A,b,d,b,A,c,A,end start,A,b,d,b,A,end start,A,b,d,b,end start,A,b,end start,A,c,A,b,A,b,A,end start,A,c,A,b,A,b,end start,A,c,A,b,A,c,A,end start,A,c,A,b,A,end start,A,c,A,b,d,b,A,end start,A,c,A,b,d,b,end start,A,c,A,b,end start,A,c,A,c,A,b,A,end start,A,c,A,c,A,b,end start,A,c,A,c,A,end start,A,c,A,end start,A,end start,b,A,b,A,c,A,end start,b,A,b,A,end start,b,A,b,end start,b,A,c,A,b,A,end start,b,A,c,A,b,end start,b,A,c,A,c,A,end start,b,A,c,A,end start,b,A,end start,b,d,b,A,c,A,end start,b,d,b,A,end start,b,d,b,end start,b,end

The slightly larger example above now has 103 paths through it, and the even larger example now has 3509 paths through it.

Given these new rules, how many paths through this cave system are there?

[Richard R Richard]

Me estoy  dando por vencido, (que a fuerza bruta no sirve, hay que programar) tengo una estrategia si la longitud de la cadena tiene una longitud constante, pero la longitud puede variar y se me vuelan los patitos alineados, me lo seguiré pensando.
Una estrategia sería crear una matriz con las relaciones posibles al inicio de cada recorrido, crear para cada recorrido una copia,  e ir eliminado las relaciones que no se pueden usar dos veces, en el momento que se transita el punto alguna vez,se explora si en algún momento las opciones son nulas el trayecto no se cuenta,  si se alcanza el final , se cuenta, si restan opciones se exploran, pero esto no es facilito de programar en 5 minutitos.

Y otra igualmente posible se me hace que  se maneja bien con Stacks, donde guardas el ultimo lugar donde pasaste, exploras de una en una escogiendo la primera las opciones que tienes y si hay una viable, la guardas al stack y sigues, si no hay opciones retrocedes en el stack y quitas la opción de la lista de posibles(pero la vuelves a dejar disponible para acceder desde otro nodo), quitas todas las ya exploradas y escoges la siguiente del nodo que este disponible,, y bla bla bla.

[geómetracat]

Mi solución para ambas partes, usando funciones recursivas. Creo que es bastante mejorable, sobre todo la segunda parte que tarda alrededor de 1.25s en obtener la solución.

Código: [Seleccionar]

with open("input12.txt") as f:
    inp = [x[:-1] for x in f.readlines()]
   
def list_to_graph(l):
    """Represents the graph as a dictionary vertex:set of vertices connected to it"""
    graph = dict()
    for x in l:
        x = x.split('-')
        if x[0] not in graph.keys():
            graph[x[0]] = [x[1]]
        else:
            graph[x[0]].append(x[1])
        if x[1] not in graph.keys():
            graph[x[1]] = [x[0]]
        else:
            graph[x[1]].append(x[0])
    return graph

#Part 1

def find_paths(graph, path_list, count):
    if path_list == []:
        return count
    new_paths = []
    for path in path_list:
        if path[-1] == 'end':
            count += 1
        else:
            for x in graph[path[-1]]:
                if x not in path or x.isupper():
                    new_paths.append(path + [x])
    return find_paths(graph, new_paths, count)

graph = list_to_graph(inp)
print(find_paths(graph, [['start']], 0))

#Part 2

def find_paths2(graph, path_list, count):
    if path_list == []:
        return count
    new_paths = []
    for path in path_list:
        if path[-1] == 'end':
            count += 1
        else:
            small_visited = [x for x in path if x.islower()]
            twice = [x for x in small_visited if small_visited.count(x)>1]
            for x in graph[path[-1]]:
                if twice:
                    if x not in path or x.isupper():
                        new_paths.append(path + [x])                       
                elif x != 'start':
                    new_paths.append(path + [x])
    return find_paths2(graph, new_paths, count)

print(find_paths2(graph, [['start']], 0))