Solve the Trolley Problem

Question

Philosophers have long pondered the Trolley problem. Unfortunately, no human has solved this problem yet. Luckily, as programmers we can use computers to solve the problem for us!

Input

Your program will take as input a (finite) directed graph (with at most one edge from x to y, for any x and y), with a designated node, and a nonnegative integer attached to each edge (representing the number of people tied to that track). In addition, every node has at least one exit edge.

The trolley starts at the designated node. Each turn, if the trolley is at node x, the utilitarian selects an edge (x,y). The people on that edge die, and trolley is now at edge y. This process continues forever.

Note that people can only die once, so if the edge (x,y) has n people tied to it, and the trolley runs over them, say, 100 times, it will still only result in n deaths.

Output

The utilitarian makes his choices in such a way as to minimize the number of people that die (which is guaranteed to be finite, since there are only finite people). Your program will output this number.

Input format

You may take the input graph in any reasonable way you like. For example, you could take it as a matrix, and count the designated node as the one labeled 0. Or you could use something like x1,y1,n1;x2,y2,n2;.... For example 0,a,0;a,b,5;a,c,1;b,b,0;c,c,0 to represent the standard trolley problem (with loops at the end).

Testcases

• 0,a,0;a,b,5;a,c,1;b,b,0;c,c,0 -> 1 (Go from 0 to a, a to c (killing one person), and then keep looping the trolley from c to c).
• 0,0,1;0,a,5;a,a,0 -> 1 (Keep going from 0 to 0, running over 1 person for all eternity),
• 0,a,5;0,b,1;a,a,1;b,b,6 -> 6 (0 -> a -> a -> a -> a -> ... (note that the greedy solution of going to b would be incorrect))
• 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 (Note that there are two different options that the utilitarian might take that both kill only one person)

This is code-golf, so the shortest answer wins! Good luck.

Notes: There will be no sick loop de loops and multitrack drifting is banned. Also, although I prefer to think of this problem in terms of Asimov's three laws (/s) Peter Taylor has noted in the sandbox that this problem is mathematically equivalent to that of finding the rho (path the loops back on itself) of lowest weight.

Answer 1

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

Try it online!

Takes input as a dictionary keyed by node id. The entries are a dictionary of neighbors and the number of people on the track between a node and the neighbor. E.g., for the first test case:

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

0 is the start node, 1 is node 'a', 2 is node 'b', etc.

Answer 2

Jelly, 27 23 bytes

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

Try it online! (last test case)

Cruel Version (Mutilate the most people)

Takes input as numbers. For the last example, 1 is a and 2 is b. 0 is the starting node. The first argument is the list of edges (e.g. [0,1],[0,2],[1,1],[2,2]), and the second argument is a list of the edges and the number of people on them (e.g.[[0,1],[0,2],[1,1],[2,2]],[1,1,0,0]).

How it Works

ṗ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.

Answer 3

Perl 6, 90 74 bytes

Thanks to Jo King for -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}

Port of RootTwo's Python solution.

Try it online!