11
\$\begingroup\$

Christmas is fast approaching and along with it, arranging the annual family Secret Santa. I'd like to try and get a head start on this, but making sure couples don't buy for each other keeps causing problems and despite doing this for years there's still the problem that Bob is pretty rubbish at buying gifts for most of the giftees, Erin will likely be disappointed, but he knows that Frank likes Talisker, so he's a good match for him. This makes none of the existing simple solutions acceptable for my needs.

To make my life easier, your task is to write a function (or closest alternative in your language) that when given an array of arrays (or closest alternative in your chosen language), returns (or outputs) a pairing of 'gifters' to 'giftees' in the shortest possible code in bytes, such that the following conditions are met:

  • Each name is paired with another, randomly selected, name from the input data (Note that it may not always be possible to randomise the output based on the provided conditions)
  • Names will be provided with a list of flags that represent an adjacency matrix with the ordering consistent, so that column n refers to the same person as row n.
  • If the conditions cannot be met, return something falsy in your language.
  • If there are multiple solutions, your program must be able to generate them all if run many times.

You can assume you will never be presented with duplicate names as we need to be able to tell which family member is which, but you may be presented with data that includes spaces to differentiate Bob Senior from Bob Junior! It should complete all the supplied test cases within an hour for pretty large families, such as 100 unique names in the source data (please see the example data sets below, you must be able to parse all of these within the allocated time).

Example input:

santa([
    ["Alice", 0, 0, 1, 1, 1, 1, 1],
    ["Bob",   0, 0, 0, 0, 0, 1, 0],
    ["Carla", 1, 1, 0, 0, 0, 1, 1],
    ["Dan",   1, 1, 0, 0, 0, 1, 1],
    ["Erin",  1, 1, 0, 0, 0, 1, 1],
    ["Frank", 1, 1, 1, 1, 1, 0, 1],
    ["Gary",  1, 1, 1, 1, 1, 1, 0]
]);
// might return something like:
[
    ["Alice", "Erin"],
    ["Bob", "Frank"],
    ["Carla", "Alice"],
    ["Dan", "Gary"],
    ["Erin", "Bob"],
    ["Frank", "Dan"],
    ["Gary", "Carla"]
]
santa([
    ["Alice", 0, 1, 1, 1, 0, 1],
    ["Bob",   0, 0, 1, 1, 0, 1],
    ["Carla", 0, 1, 0, 1, 0, 1],
    ["Dan",   0, 1, 1, 0, 0, 0],
    ["Erin",  0, 0, 1, 0, 0, 1],
    ["Frank", 1, 1, 1, 1, 1, 0]
]);
false
santa([
    ["Alice", 0, 1, 1],
    ["Bob",   1, 0, 1],
    ["Carla", 1, 1, 0]
]);
[
    ["Alice", "Bob"],
    ["Bob", "Carla"],
    ["Carla", "Alice"]
]

Depending on language, input can be in other formats, for instance details on STDIN could be provided as:

script <<< 'Alice,0,0,1,1,1,1,1
Bob,0,0,0,0,0,1,0
Carla,1,1,0,0,0,1,1
Dan,1,1,0,0,0,1,1
Erin,1,1,0,0,0,1,1
Frank,1,1,1,1,1,0,1
Gary,1,1,1,1,1,1,0'

Output can also be provided in any sensible format, whichever is easiest for your language. Acceptable formats include an array of arrays (as above) or perhaps a hash/Object/associative array or even just printing the parings to STDOUT:

Alice:Dan
Bob:Erin
Carla:Bob
Dan:Alice
Erin:Frank
Frank:Carla

If in doubt, please ask and provide examples of required input format and expected output format with your answer.

Reference JavaScript implementation.

Larger data sets: 100, 100, 200, 200 - many solutions, 200 - only one solution.

Reference implementation completes all these in <4s on my machine.

Above sets generated with this script.

\$\endgroup\$
  • 1
    \$\begingroup\$ Are we to assume the subarrays' elements are in the same order as the parent array's? And that 1 in the kth subarray's (n+1)th element means that the kth person can give to the nth person? \$\endgroup\$ – msh210 Nov 6 '15 at 9:29
  • \$\begingroup\$ @msh210 Indeed, apologies for not being verbose, I'll update the question to confirm. \$\endgroup\$ – Dom Hastings Nov 6 '15 at 10:07
  • \$\begingroup\$ In the first example, where does it provide a mapping from Bob to Erin? I just see one from Erin to Bob. \$\endgroup\$ – LegionMammal978 Nov 6 '15 at 12:56
  • \$\begingroup\$ @LegionMammal978 Ahhh, that's an excellent question and one that can only be answered by an edit... Apologies! Fixed! \$\endgroup\$ – Dom Hastings Nov 6 '15 at 13:16
  • 1
    \$\begingroup\$ N0! It is way to early for Christmas! This should be secret Turkey who gives out presents. \$\endgroup\$ – Grant Davis Nov 7 '15 at 4:23
4
\$\begingroup\$

Javascript ES6, 191

This solution returns all possible pairings as a list of list of pairs:

f=l=>(h=l=>l.length,n=l.map(i=>i.shift()),o=[],(r=s=>(g=h(s))<h(n)?l[g].map((e,x)=>e&&r([...s,x])):o.push([...s]))([]),o.filter(i=>h([...new Set(i)])==h(n)).map(l=>l.map((t,f)=>[n[f],n[t]])))

Example run:

>> example = f([
    ["Alice", 0, 0, 1, 1, 1, 1, 1],
    ["Bob",   0, 0, 0, 0, 0, 1, 0],
    ["Carla", 1, 1, 0, 0, 0, 1, 1],
    ["Dan",   1, 1, 0, 0, 0, 1, 1],
    ["Erin",  1, 1, 0, 0, 0, 1, 1],
    ["Frank", 1, 1, 1, 1, 1, 0, 1],
    ["Gary",  1, 1, 1, 1, 1, 1, 0]])

<< Array [ Array[7], Array[7], Array[7], Array[7], Array[7], Array[7], Array[7], Array[7], Array[7], Array[7], 26 more… ]

>> example[0]

<< Array [ "Alice:Carla", "Bob:Frank", "Carla:Alice", "Dan:Bob", "Erin:Gary", "Frank:Dan", "Gary:Erin" ]
\$\endgroup\$
  • \$\begingroup\$ I think that based on the larger test cases, this will fail because it generates all the permutations... Are you able to validate it finishes for the larger sets on your machine? Thanks! Apologies that these larger sets weren't there at first. \$\endgroup\$ – Dom Hastings Dec 15 '15 at 13:24

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.