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!
Your program will take as input a (finite) directed graph (with at most one edge from
y, for any
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
n people tied to it, and the trolley runs over them, say, 100 times, it will still only result in
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.
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).
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.