Skip to main content
Code Golf

Return to Answer

deleted 4470 characters in body
Source Link
ophact
ophact
  • 3.2k
  • 6
  • 8

any better title?

any other suitable tags?

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 there will be exactly \$n\$ distinct positive integers present in total. For instance, above we had three people, so there were three possible choices. If there are twenty people, then in total there will be twenty positive integers.

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

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]

This is Posted , so the shortest code, measured in bytes, winshere.

Any feedback? Wrong test cases? Clarification needed? Duplicate?

any better title?

any other suitable tags?

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 there will be exactly \$n\$ distinct positive integers present in total. For instance, above we had three people, so there were three possible choices. If there are twenty people, then in total there will be twenty positive integers.

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

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]

This is , so the shortest code, measured in bytes, wins.

Any feedback? Wrong test cases? Clarification needed? Duplicate?

Posted here.

added 22 characters in body
Source Link
ophact
ophact
  • 3.2k
  • 6
  • 8

Choice makerSatisfy as many people as possible

Choice maker

Satisfy as many people as possible

Source Link
ophact
ophact
  • 3.2k
  • 6
  • 8

Choice maker

any better title?

any other suitable tags?

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 there will be exactly \$n\$ distinct positive integers present in total. For instance, above we had three people, so there were three possible choices. If there are twenty people, then in total there will be twenty positive integers.

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

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]

This is , so the shortest code, measured in bytes, wins.

Any feedback? Wrong test cases? Clarification needed? Duplicate?