Lösen Sie das Wagenproblem

14

Philosophen haben lange über das Trolley-Problem nachgedacht . Leider hat noch kein Mensch dieses Problem gelöst. Zum Glück können wir als Programmierer Computer verwenden, um das Problem für uns zu lösen!

Eingang

Ihr Programm verwendet als Eingabe einen (endlichen) gerichteten Graphen (mit höchstens einer Kante von xbis yfür ein beliebiges xund y) mit einem festgelegten Knoten und einer nichtnegativen Ganzzahl, die an jede Kante angehängt ist (die Anzahl der Personen, die an diese Spur gebunden sind). . Zusätzlich hat jeder Knoten mindestens eine Austrittskante.

Der Wagen startet am angegebenen Knoten. Befindet sich der Wagen in jeder Runde am Knoten x, wählt der Bediener eine Kante aus (x,y). Die Leute an diesem Rand sterben, und der Wagen ist jetzt am Rand y. Dieser Prozess dauert für immer an.

Beachten Sie, dass Menschen nur einmal sterben können. Wenn (x,y)also nPersonen an die Kante gebunden sind und der Wagen beispielsweise 100 Mal über sie fährt, führt dies nur zu nTodesfällen.

Ausgabe

Der Utilitarist trifft seine Entscheidungen so, dass die Anzahl der Sterbenden so gering wie möglich gehalten wird (was garantiert endlich ist, da es nur endliche Menschen gibt). Ihr Programm gibt diese Nummer aus.

Eingabeformat

Sie können das Eingabediagramm nach Belieben anpassen. Zum Beispiel könnten Sie es als Matrix nehmen und den angegebenen Knoten als den mit 0 bezeichneten Knoten zählen. Oder Sie könnten so etwas verwenden x1,y1,n1;x2,y2,n2;.... Zum Beispiel 0,a,0;a,b,5;a,c,1;b,b,0;c,c,0, um das Standard-Trolley-Problem darzustellen (mit Schleifen am Ende).

Testfälle

  • 0,a,0;a,b,5;a,c,1;b,b,0;c,c,0 -> 1 (Gehe von 0 nach a, a nach c (töte eine Person) und schleife dann den Wagen weiter von c nach c).
  • 0,0,1;0,a,5;a,a,0 -> 1 (Gehen Sie von 0 auf 0 und überflügeln Sie 1 Person für alle Ewigkeit),
  • 0,a,5;0,b,1;a,a,1;b,b,6 -> 6 (0 -> a -> a -> a -> a -> ... (beachte, dass die gierige Lösung, nach b zu gehen, falsch wäre))
  • 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 (Beachten Sie, dass es zwei verschiedene Möglichkeiten gibt, die der Utilitarist ergreifen könnte, wenn beide nur eine Person töten)

Das ist Code-Golf , also gewinnt die kürzeste Antwort! Viel Glück.

Hinweise: Es wird keine Sick-Loop-De-Loops geben und das Driften auf mehreren Spuren ist verboten. Auch, obwohl ich dieses Problem lieber in Bezug auf Asimovs drei Gesetze (n) sehe, hat Peter Taylor in der Sandbox festgestellt, dass dieses Problem mathematisch äquivalent zu dem Problem ist, den Rho (Pfad, auf dem die Schleifen zurückführen) mit dem geringsten Gewicht zu finden .

code-golf graph-theory optimization PyRulez
quelle
4
Gibt es dicke Männer ?
Beta Decay
2
@BetaDecay ja, aber aufgrund von Upgrades des Wagens verhalten sie sich im Sinne dieser Frage genauso wie normale Leute.
PyRulez

Antworten:

6

Jelly , 27 23 Bytes

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

Probieren Sie es online! (letzter Testfall)

Grausame Version (Verstümmle die meisten Leute)

Nimmt Eingaben als Zahlen entgegen. Für das letzte Beispiel 1ist aund 2ist b. 0ist der Startknoten. Das erste Argument ist die Liste der Kanten (z. B. [0,1],[0,2],[1,1],[2,2]), und das zweite Argument ist eine Liste der Kanten und der Anzahl der Personen darauf (z [[0,1],[0,2],[1,1],[2,2]],[1,1,0,0]. B. ).

Wie es funktioniert

ṗ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.
fireflame241
quelle
@ Shaggy Umm, weißt du nicht, was du meinst? Tut Jelly deinen Augen weh oder so?
Erik der Outgolfer
1
@EriktheOutgolfer bezieht sich auf die Version des Programms, die versucht, die meisten Menschen zu verstümmeln .
Fireflame241
@ Shaggy Das wäre eine interessante Herausforderung.
PyRulez
9

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])

Probieren Sie es online!

Übernimmt die Eingabe als Wörterbuch mit der Node-ID. Die Einträge sind ein Wörterbuch der Nachbarn und die Anzahl der Personen auf der Strecke zwischen einem Knoten und dem Nachbarn. ZB für den ersten Testfall:

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

0 ist der Startknoten, 1 ist der Knoten 'a', 2 ist der Knoten 'b' usw.

RootTwo
quelle