15
\$\begingroup\$

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 , so the shortest code, measured in bytes, wins.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Will the input list ever be empty? In this case, must we return an empty list, or can we return something else (in my case, 0)? \$\endgroup\$
    – Lecdi
    Mar 24, 2022 at 21:20
  • 2
    \$\begingroup\$ Can we assume that the list of positive integers is in fact 1..n? \$\endgroup\$ Mar 24, 2022 at 23:27
  • \$\begingroup\$ @Lecdi Empty lists are undefined behavior. \$\endgroup\$
    – ophact
    Mar 25, 2022 at 6:10
  • \$\begingroup\$ @DominicvanEssen Sure. \$\endgroup\$
    – ophact
    Mar 25, 2022 at 6:10
  • \$\begingroup\$ And a test case where the happiest score is obtained by not giving everyone one of their choices, even though this could be done, for instance: [[1,2,3],[2,3,4],[3,4,5],[4,5,1],[1,2,3]] (I thknk). \$\endgroup\$ Mar 25, 2022 at 9:35

12 Answers 12

5
\$\begingroup\$

Wolfram Language (Mathematica), 75 bytes

-2 bytes thanks to @att.

MinimalBy[Permutations[i=0;++i&/@#],tTr[Tr@*Position[0]/@(#-t)/. 0->4]]&

Try it online!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ -2 with Permutations@Range@Length@# -> Permutations[i=0;++i&/@#], and another -7 on top if we can take input reversed. \$\endgroup\$
    – att
    Mar 25, 2022 at 4:44
3
\$\begingroup\$

Python SciPy, 120 bytes

def f(x):a=x@x.T*0+4;a[[*zip(range(len(x)))],x-1]=1,2,3;return linear_sum_assignment(a)[1]+1
from scipy.optimize import*

Attempt This Online!

Not fully builtin but leaves the heavy lifting to scipy.optimize.linear_sum_assignment. We just need to feed it in the right format (essentially one-hotting --- or rather three-hotting --- the input).

\$\endgroup\$
3
\$\begingroup\$

Husk, 12 bytes

◄oṁo%4←z€¹Pŀ

Try it online!

          P   # calculate all permutations of
           ŀ  # the length of the input;
◄             # now output the element that minimizes:
 o            # combination of          
       z€¹    # zip 'get index' function over input (or 0 if not found)
  ṁo%4←       # then subtract 1 & modulo 4 (so not found becomes 3)
\$\endgroup\$
3
\$\begingroup\$

R, 137 133 bytes

Edit: -4 bytes thanks to pajonk and the new-to-me function anyDuplicated()

\(l,n=length(l),q=expand.grid(rep(list(1:n),n)),p=q[!apply(q,1,anyDuplicated),])p[order(apply(p,1,\(x)sum(mapply(match,x,l,4))))[1],]

Attempt This Online!

Ungolfed

assignments=
function(l){
    # get all combinations of n times 1..n, unfortunately with repeats that we don't want
    p=expand.grid(rep(list(seq(l)),length(l)))
    # now get rid of the combinations with duplicates
    p=p[apply(p,1,function(x)sum(unique(x)|1)==length(l)),]
    # calculate the happiness score of each person 
    # as the position of the match of each assigned value in each input list
    # (or 4 if it isn't found)
    e=apply(p,1,function(x)mapply(match,x,l,4))
    # calculate total happiness score for each combination:
    h=colSums(e)
    # return the combination for which happiness score is minimal:
    p[which.min(h),]
}
\$\endgroup\$
4
  • \$\begingroup\$ -4 bytes with anyDuplicated. \$\endgroup\$
    – pajonk
    Mar 25, 2022 at 19:51
  • \$\begingroup\$ @pajonk - Wow - thanks - never heard of that one before! \$\endgroup\$ Mar 25, 2022 at 23:28
  • 2
    \$\begingroup\$ This is the 8th solution containing anyDuplicated! \$\endgroup\$
    – Giuseppe
    Mar 26, 2022 at 0:20
  • \$\begingroup\$ @Giuseppe - Hm. That's embarassing... \$\endgroup\$ Mar 26, 2022 at 6:43
2
\$\begingroup\$

APL(Dyalog Unicode), 34 bytes SBCS

{x⊃⍨⊃⍋(⍵+.⍳⊢)¨x←/⍨∘(≡∘∪⍨¨)⍨,⍳⍴⍨≢⍵}

Try it on APLgolf! (Last cases uses more memory than allowed on TryAPL.)

The cost function for a single arrangement can be computed in a very compact way with +.⍳, taking the preferences on the left and the arrangement on the right. Half of the code is just generating the permutations.

\$\endgroup\$
2
\$\begingroup\$

Python 3, 123 bytes

lambda*a:p({*sum(a,[])},*a)[1:]
p=lambda r,b,*a:min([[*b,i].index(i)+k,i,*j]for i in r for k,*j in[a and p(r-{i},*a)or[0]])

Try it online!

Using builtins only.

As a one-liner:

Python 3, 125 bytes

def f(b,*a,r=0):s=r or{*sum(a,b)};return min([[*b,i].index(i)+k,i,*j]for i in s for k,*j in[a and f(*a,r=s-{i})or[0]])[r==0:]

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ This seems to struggle when there's no combination where everyone gets one of their choices: try it... \$\endgroup\$ Mar 25, 2022 at 9:19
  • \$\begingroup\$ @DominicvanEssen That is true, but the spec states that the output will be a permutation of 1..n and that all integers 1..n are expected to be present in the input. \$\endgroup\$
    – Jitse
    Mar 25, 2022 at 9:22
  • \$\begingroup\$ My example wasn't so good: here is a better one, unless I've messed-up again... \$\endgroup\$ Mar 25, 2022 at 9:38
  • \$\begingroup\$ @DominicvanEssen I see your point, thanks! I fixed it now. \$\endgroup\$
    – Jitse
    Mar 25, 2022 at 10:21
1
\$\begingroup\$

Javascript, 178 bytes

// 178 Bytes
f=a=>(h=(m,i=a.map(_=>0),n=a.length)=>(g=_=>new Set(b=i.map((k,j)=>a[j][k])).size-n?(c=j=>j===!!j||(j<n&&++i[j]&&c(i.reduce((a,b)=>a+b)>m&&j+!(i[j]=0))))(0)&&g():b)()||h(m+1))(0)

// Example
const arr = [
  [1, 2, 3],
  [1, 3, 4],
  [1, 4, 5],
  [1, 5, 6],
  [1, 6, 7],
  [1, 7, 8],
  [2, 3, 8],
  [2, 6, 5],
];
console.log(f(arr));

Explanation

f = a => (
  h = ( // This function tries to find an assignment that happiness <= m
    m,             // Maximum allowed happiness
    i=a.map(_=>0), // Assignments (by rank), i.e. [0,1,2] means P1 gets first choice, P2 gets second, P3 gets third.
    n=a.length    
  ) => (
    g = _ => // This function will iterate through the possibilities of i until it finds a solution (or not)
      new Set(b = i.map((k, j) => a[j][k])).size - n // Checks if assignments are unique
      ? (
          c = j=>  // This function finds the "next" i with maximum happiness m
            j===!!j || (                        // If j is a bool (i.e. not a number, then stop)
              j < n &&                          // If j >= n, then no more combinations
              ++i[j] &&                         // Increment i[j] (otherwise, nop)
              c(
                i.reduce((a, b)=> a + b) > m && // If happiness score exceeds m ...
                j + !(i[j] = 0)                 // Set i[j] to 0 and negate, so we call c(j + 1)
              )
            )
        )(0) &&
        g()
      : b
  )() ||
  h(m+1) // If no assignment was found, try again with a more relaxed contraint
)(0) // Start with m = 0
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 13 12 bytes

āœΣδkÅ\®₄:O}н

-1 byte and corrected my limitations mistake thanks to @DominicVanEssen

Try it online or verify all test cases.

Explanation:

ā           # Push a list in the range [1, (implicit) input-length]
 œ          # Pop and push a list of its permutations
  Σ         # Sort these permutation-lists by:
   δ        #  Apply double-vectorized with the (implicit) input-list of lists
    k       #   Get the first 0-based index of the value in the inner input-list
            #   (or -1 if it's not present)
     Å\     #  Pop the list of lists, and leave its main diagonal
       4%   #  Modulo-4 to replace all -1s with 3s
         O  #  Then sum the list together
  }н        # After the sort-by: pop and leave the first list (with lowest sum)
            # (which is output implicitly as result)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Not sure if I understood the explanation right, but it looks as if you're giving a happiness score of 1000 to anyone that can't get any of their choices... it should be just 4 (which might also be easier to calculate as simply modulo-4 of the index -1...)... \$\endgroup\$ Mar 25, 2022 at 9:30
  • \$\begingroup\$ @DominicvanEssen You're completely right! I was basing the limitations on the wrong list-length. It's indeed limited by 4, since the amount of choices are hard-coded to just 3 options, for which a modulo-4 to correct the -1s indeed suffices. Thanks. :) \$\endgroup\$ Mar 25, 2022 at 9:57
1
\$\begingroup\$

Vyxal, 18 bytes

żṖµ£⁰ƛ¥$vḟ;Þ/4%∑;h

Try it Online! or Verify (almost) all test cases (the larger ones time out)

Port of 05AB1E. Probably a way to shorten £⁰ƛ¥$vḟ;, but idk.

How?

żṖµ£⁰ƛ¥$vḟ;Þ/4%∑;h
ż                  # Inclusive length range [1, length]
 Ṗ                 # All permutations
  µ             ;  # Sorting lambda
   £               # Store this item in the register
    ⁰ƛ    ;        # Mapping lambda over the input
      ¥$vḟ         # Get the index of the current character in this list
           Þ/      # Get the main diagonal of this list
             4%    # Modulo each by four to convert -1 to 3
               ∑   # Sum these
                 h # Get the first item of the sorted list
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 57 46 bytes

≔Eθκη⊞υ⟦⟧Fη≔ΣEυE⁻ηκ⁺κ⟦μ⟧υ≔EυΣEι﹪⌕§θμλ⁴ηI§υ⌕η⌊η

Attempt This Online! Link is to verbose version of code. 0-indexed. Explanation:

≔Eθκη⊞υ⟦⟧Fη≔ΣEυE⁻ηκ⁺κ⟦μ⟧υ

Generate all the permutations of [0..n). This is based on my answer to 1 to N column and row sums but tweaked to use the length of the input as n.

≔EυΣEι﹪⌕§θμλ⁴η

Calculate the unhappiness of each permutation.

I§υ⌕η⌊η

Output a permutation with the least unhappiness.

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

Python 3.8+, 172 171 165 bytes

-6 bytes thanks to @jezza_99

Golfed code

from itertools import*
def f(m):
 L=len(m);H=s=5*L
 for p in permutations(range(1,L+1)):
  if(h:=sum((m[i]+[p[i]]).index(p[i])for i in range(L)))<H:H,s=h,p
 return s

Try it online!

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

Scala, 378 bytes

378 bytes, it can be golfed more.


Golfed version. Try it online!

type Q[A]=List[A]
def f(m: Q[Q[Int]])={val L=m.length;var(s,minH)=(List.fill(L)(0),5*L);def permute(input:Q[Int]):Q[Q[Int]]=input match{case Nil=>List(Nil);case _=>for{i<-input.indices.toList;rest=input.patch(i,Nil,1);other<-permute(rest)}yield input(i)::other};for(p<-permute((1 to L).toList)){val h=(0 until L).map(i=>(m(i):+p(i)).indexOf(p(i))).sum;if(h<minH){minH=h;s=p}};s}

Ungolfed version. Try it online!


import scala.util.control.Breaks._
import scala.collection.mutable.ArrayBuffer

object Main {
  def f(m: List[List[Int]]): List[Int] = {
    val L = m.length
    val H = 5 * L
    var s = List.fill(L)(0)
    var minH = H

    def permute(input: List[Int]): List[List[Int]] = {
      input match {
        case Nil => List(Nil)
        case _ => for {
          i <- input.indices.toList
          rest = input.patch(i, Nil, 1)
          other <- permute(rest)
        } yield input(i) :: other
      }
    }

    for (p <- permute((1 to L).toList)) {
      val h = (0 until L).map(i => (m(i) :+ p(i)).indexOf(p(i))).sum
      if (h < minH) {
        minH = h
        s = p
      }
    }
    s
  }

  def main(args: Array[String]): Unit = {
    println(f(List(
      List(1, 2, 3),
      List(1, 3, 4),
      List(1, 4, 5),
      List(1, 5, 6),
      List(1, 6, 7),
      List(1, 7, 8),
      List(2, 3, 8),
      List(2, 6, 5)
    )) == List(1, 3, 4, 5, 6, 7, 8, 2))
  }
}

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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