El hilo de Ariadna

Enunciado

Antes de que Teseo entre al laberinto de Creta, Ariadna le da un ovillo de hilo para que sepa volver. Ella quiere saber cuántos caminos distintos llevan de la entrada hasta el Minotauro sin pasar dos veces por la misma sala: donde ya pasó el hilo, Teseo no vuelve a entrar.

Escribe una función que reciba puertas, una lista de listas de enteros.

Las salas se numeran desde 0, y puertas[i] son las salas a las que se puede pasar desde la sala i. Las puertas se cruzan en los dos sentidos: si la 2 está en puertas[0], la 0 está en puertas[2]. No hay puertas repetidas ni puertas de una sala a sí misma. La entrada es la sala 0 y el Minotauro está en la última. Hay al menos una sala y a lo más 8. Regresa un entero: cuántos caminos empiezan en la entrada, terminan en la sala del Minotauro y no repiten ninguna sala. Dos caminos son distintos si no recorren las mismas salas en el mismo orden.

Con [[1, 2], [0, 2, 3], [0, 1, 3], [1, 2]] hay 4: 0-1-3, 0-2-3, 0-1-2-3 y 0-2-1-3. Con [[1], [0], []] la sala 2 no tiene puertas, así que no hay ninguno: 0. Si la entrada es la sala del Minotauro, el único camino es quedarse ahí: 1.

Ejemplos

• El ejemplo

  [[1, 2], [0, 2, 3], [0, 1, 3], [1, 2]] → 4

• La sala del Minotauro no tiene puertas

  [[1], [0], []] → 0

• Un pasillo

  [[1], [0, 2], [1]] → 1

Además de estas, el reto tiene pruebas ocultas que se revelan al enviar tu solución.

Empiezas con esto

def caminos(puertas):
    pass

function caminos(puertas) {
}