14
\$\begingroup\$

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

\$\endgroup\$
  • 4
    \$\begingroup\$ Are there any fat men? \$\endgroup\$ – Beta Decay Jul 28 '17 at 20:33
  • 2
    \$\begingroup\$ @BetaDecay yes, but due to upgrades to the trolley, they behave the same as regular people for the purpose of this question. \$\endgroup\$ – PyRulez Jul 28 '17 at 20:34
6
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ @Shaggy Umm, not sure what you mean? Does Jelly hurt your eyes or something? \$\endgroup\$ – Erik the Outgolfer Jul 29 '17 at 15:20
  • 1
    \$\begingroup\$ @EriktheOutgolfer he's referring to the version of the program which tries to mutilate the most people. \$\endgroup\$ – fireflame241 Jul 29 '17 at 16:05
  • \$\begingroup\$ @Shaggy That would be an interesting challenge. \$\endgroup\$ – PyRulez Jul 29 '17 at 17:07
9
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Perl has default parameters too! This can be 74 bytes \$\endgroup\$ – Jo King May 12 at 1:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.