Solve the Trolley Problem
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.
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.