Satisfy as many people as possible

Question

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.

Answer 1

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!

Answer 2

Python SciPy, 120 bytes

def f(x):[email protected]*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).

Answer 3

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)

Answer 4

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),]
}

Answer 5

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.

Answer 6

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!

Answer 7

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

Answer 8

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)

Answer 9

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

Answer 10

Charcoal, 57 46 bytes

≔Ｅθκη⊞υ⟦⟧Ｆη≔ΣＥυＥ⁻ηκ⁺κ⟦μ⟧υ≔ＥυΣＥι﹪⌕§θμλ⁴ηＩ§υ⌕η⌊η

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

≔Ｅθκη⊞υ⟦⟧Ｆη≔ΣＥυＥ⁻ηκ⁺κ⟦μ⟧υ

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.

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

Calculate the unhappiness of each permutation.

Ｉ§υ⌕η⌊η

Output a permutation with the least unhappiness.

Answer 11

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!

Answer 12

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))
  }
}