Los filósofos han reflexionado durante mucho tiempo sobre el problema del Trolley . Desafortunadamente, ningún humano ha resuelto este problema todavía. ¡Afortunadamente, como programadores podemos usar computadoras para resolver el problema por nosotros!

Entrada

Su programa tomará como entrada un gráfico dirigido (finito) (con como máximo un borde de xay , para cualquier xy y), con un nodo designado, y un entero no negativo unido a cada borde (que representa el número de personas vinculadas a esa pista) . Además, cada nodo tiene al menos un borde de salida.

El carro comienza en el nodo designado. Cada turno, si el carro está en el nodox , el utilitario selecciona un borde (x,y). La gente en ese borde muere, y el carro ahora está al borde y. Este proceso continúa para siempre.

Tenga en cuenta que las personas solo pueden morir una vez, por lo que si el borde (x,y)tienen personas atadas a él, y el carro los atropella, digamos, 100 veces, solo dará como resultado la nmuerte.

Salida

El utilitario toma sus decisiones de tal manera que minimiza el número de personas que mueren (lo que se garantiza que es finito, ya que solo hay personas finitas). Su programa generará este número.

Formato de entrada

Puede tomar el gráfico de entrada de la manera razonable que desee. Por ejemplo, podría tomarlo como una matriz y contar el nodo designado como el etiquetado 0. O podría usar algo como x1,y1,n1;x2,y2,n2;.... Por ejemplo, 0,a,0;a,b,5;a,c,1;b,b,0;c,c,0para representar el problema del carro estándar (con bucles al final).

Casos de prueba

• 0,a,0;a,b,5;a,c,1;b,b,0;c,c,0 -> 1 (Ir de 0 a a, a a c (matar a una persona), y luego seguir girando el carro de c a c).
• 0,0,1;0,a,5;a,a,0 -> 1 (Continúa de 0 a 0, atropellando a 1 persona por toda la eternidad),
• 0,a,5;0,b,1;a,a,1;b,b,6 -> 6 (0 -> a -> a -> a -> a -> ... (tenga en cuenta que la codiciosa solución de ir a b sería incorrecta))
• 0,a,1;0,b,5;a,b,1;b,a,1 -> 3 (0 -> a -> b -> a -> b -> ...)
• 0,a,1;0,b,1;a,a,0;b,b,0 -> 1 (Tenga en cuenta que hay dos opciones diferentes que el utilitario podría tomar y que ambas matan a una sola persona)

Este es el código de golf , por lo que gana la respuesta más corta. Buena suerte.

Notas: No habrá loop de loops enfermos y la deriva multipista está prohibida. Además, aunque prefiero pensar en este problema en términos de las tres leyes (/ s) de Asimov, Peter Taylor ha notado en la caja de arena que este problema es matemáticamente equivalente al de encontrar el rho (camino de vuelta de los bucles en sí mismo) de menor peso .

Jalea , 27 23 bytes

ṗL$µṭ0FIm2ASµÐḟµQ⁴ySµ€Ṃ

Pruébalo en línea! (último caso de prueba)

Versión cruel (Mutilar a la mayoría de la gente)

Toma la entrada como números. Para el último ejemplo, 1es ay 2es b. 0es el nodo inicial El primer argumento es la lista de bordes (p [0,1],[0,2],[1,1],[2,2]. Ej. ), Y el segundo argumento es una lista de los bordes y el número de personas en ellos (p [[0,1],[0,2],[1,1],[2,2]],[1,1,0,0]. Ej .).

Cómo funciona

ṗL$µṭ0FIm2ASµÐḟµQ⁴ySµ€Ṃ
ṗL$                       - on the first argument, get the Cartesian power of it to its length.
                            this gives all paths of the length of the input. Cycles are implicit
   µ        µÐḟ           - get valid paths starting with 0 -- filter by:
    ṭ0                      - prepend 0
      F                     - flatten
       I                    - get the difference between elements
        m2                  - every second difference: 0 for each edge that starts at the node the previous edge ended at, nonzero otherwise.
          AS                - 0 iff all elements are 0
               µ    µ€    - on each path:
                Q           - remove repeat edges.
                 ⁴y         - translate according to the mapping in the second program argument
                   S        - Sum
                      Ṃ   - get the minimum of these.

Python 3 , 80 bytes

y=lambda d,s=0,p=[],f=0:f in p and s or min(y(d,s+d[f][t],p+[f],t)for t in d[f])

Pruébalo en línea!

Toma la entrada como un diccionario con clave por ID de nodo. Las entradas son un diccionario de vecinos y el número de personas en la pista entre un nodo y el vecino. Por ejemplo, para el primer caso de prueba:

{0: {1: 0}, 1: {2: 5, 3: 1}, 2: {2: 0}, 3: {3: 0}}

0 es el nodo de inicio, 1 es el nodo 'a', 2 es el nodo 'b', etc.

Perl 6 , 90 74 bytes

Gracias a Jo King por -16 bytes.

my&g=->\a,\b=0,\c=@,\d=0 {a{d}&&b||min map {g a,b+$^f,(|c,d),$^e},a{d}.kv}

Puerto de la solución Python de RootTwo .

Pruébalo en línea!