There are times when a large number of people need to choose something. They all want to get the stuff they choose, obviously, but it's impossible to please everyone that way, so a usual compromise is to give people three choices and try to make sure that everyone gets one of their choices.
For instance, consider three people who want to choose their parts in a play. The play has three parts. Imagine that the parts are called Word, PowerPoint and Excel, and imagine that the choices are like this:
Person 1 chooses: (from first choice to third choice)
Word
PowerPoint
Excel
Person 2 chooses: (from first choice to third choice)
PowerPoint
Excel
Word
Person 3 chooses: (from first choice to third choice)
Excel
Word
PowerPoint
Here, it is easy to assign Word to person 1, PowerPoint to person 2 and Excel to person 3 and thus give everyone their first choice. However, it is not so easy if...
Person 1 chooses: (from first choice to third choice)
Word
Excel
PowerPoint
Person 2 chooses: (from first choice to third choice)
Word
PowerPoint
Excel
Person 3 chooses: (from first choice to third choice)
Excel
Word
PowerPoint
Since person 3 is the only person who wants Excel, person 3 automatically gets Excel.
Person 1 and person 2 both want Word, but there is only one Word, so suppose we assign Word to person 1. Then person 2 cannot get Word but his second choice, PowerPoint, has not been taken, so we can assign PowerPoint to person 2.
It gets even more complicated here:
Person 1 chooses: (from first choice to third choice)
Word
PowerPoint
Excel
Person 2 chooses: (from first choice to third choice)
Word
Excel
PowerPoint
Person 3 chooses: (from first choice to third choice)
Excel
Word
PowerPoint
Again, person 3 is the only one who wants Excel, so he gets it.
If we assign Word to person 1, then person 2 cannot get Word. But person 2 cannot get Excel either because person 3 got it! This means that person 2 is stuck with his third choice, PowerPoint. Obviously he is not very happy.
If we assign Word to person 2, on the other hand, person 1 can get his second choice, PowerPoint, and overall everyone is happier.
And that is the aim of this challenge: to make everyone as "happy" as possible.
Challenge
Write a program or function that takes in a list of lists. Each sublist contains three positive integers. If the length of the big list is \$n\$, then the positive integers from 1 to \$n\$ will be present in the list (and no other integers will be there). For instance, above we had three people, so there were three possible choices. If there are twenty people, then in total there will be the integers from 1 to 20 present in the list.
Input may be taken in any reasonable format similar to the one above.
Your output should be a list of \$n\$ distinct positive integers corresponding to the integer assigned to each person. This list is, due to the input format above, a permutation of 1..n
. The output should be such that the people represented in the input are as "happy" as possible.
Output may be in any reasonable format similar to the one above.
Your code may do anything if it receives an empty list.
Quantifying happiness for the purposes of this challenge
The "happiest" arrangement is the one where the following expression is minimal:
$$\sum^{4}_{i=1} ix_i$$
Here, \$x_i\$ is the number of people who got their \$i\$-th choice. \$x_4\$ is the number of people who got none of their choices.
This measure means that if many people get none of their choices, then the population as a whole will be very unhappy. On the other hand, if everyone gets their first choice, then the population will be very happy.
If there are multiple arrangements that have the same "happiness value", then you may output any number of them.
Test cases
[[1,2,3],[2,3,1],[3,1,2]] -> [1,2,3] // first worked example above with 1=Word, 2=PowerPoint, 3=Excel
[[1,3,2],[1,2,3],[3,1,2]] -> [1,2,3] // second worked example
[[1,2,3],[1,3,2],[3,1,2]] -> [2,1,3] // third worked example
[[1,2,3],[1,2,4],[2,3,4],[2,4,3]] -> [1,2,3,4] // happiness measure 7; multiple answers possible
[[1,4,2],[1,4,2],[1,4,2],[2,3,4]] -> [1,2,4,3]
[[1,2,3],[2,3,5],[4,5,1],[5,1,2],[5,4,3]] -> [1,2,4,5,3]
[[1,2,3],[1,3,4],[1,4,5],[1,5,6],[1,6,7],[1,7,8],[2,3,8],[2,6,5]] -> [1, 3, 4, 5, 6, 7, 8, 2]
[[1,2,3],[2,3,4],[3,4,5],[4,5,1],[1,2,3]] -> [1,2,3,4,5]
[[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[4,5,6],[5,6,7]] -> [1, 2, 3, 6, 7, 4, 5]
This is code-golf, so the shortest code, measured in bytes, wins.