4
\$\begingroup\$

The challenge is to create one program that will accept as arguments (arrays of arrays) or on standard input (line-by-line, separated by commas) a collection of families and names, like so:

John,Anna
Mark,James
Elizabeth,Daniel,Isabelle
Ryan,Ruth

As well as two other arguments (two more arrays of pairs, as arrays) or on standard input (a blank line after the preceding input, followed by two comma-separated lists on two lines with an = separating pairings; see example) that represent the two previous years' Christmas lists:

John=Mark,James=Anna,Elizabeth=Ryan,...
John=Isabelle,Ryan=Elizabeth,Daniel=Mark,...

The function/program must return/output (in any format) a way that each person is assigned somebody to give a present to, following these rules:

  1. A person cannot give a present to him or herself.
  2. A person cannot give a present to anybody in his or her own family.
  3. A person cannot be assigned the same person he or she was assigned in any of the two previous years.

If such a matching is impossible for every person, output/return null or nothing or something appropriate.

This is a code golf, so shortest code wins, but I'll also give a bounty to the code that runs fastest (on my computer, at least, though results shouldn't vary much).

Improve this question
\$\endgroup\$
8
  • 1
    \$\begingroup\$ Are the gift assignments symmetric? The text doesn't say so, but using = to represent the assignments suggests it... \$\endgroup\$
    – Keith Randall
    Jul 7, 2012 at 6:05
  • 1
    \$\begingroup\$ Shouldn't the number of people be guaranteed to be even? \$\endgroup\$
    – Peter Taylor
    Jul 7, 2012 at 6:13
  • \$\begingroup\$ @KeithRandall: No, they aren't symmetric. \$\endgroup\$
    – Ry-
    Jul 7, 2012 at 13:35
  • \$\begingroup\$ @PeterTaylor: No, because they aren't symmetric. (Dan=Marge,Marge=Carolyn,Carolyn=Don,Don=Bob,Bob=Dan) \$\endgroup\$
    – Ry-
    Jul 7, 2012 at 13:37
  • 2
    \$\begingroup\$ @userunknown What, we can't prepare early for christmas? I like to buy my christmas cards in January in the sales. :-) Seriously though, I think -1 for being unseasonal is a little harsh. \$\endgroup\$
    – Gareth
    Jul 7, 2012 at 16:31

1 Answer 1

Reset to default
2
\$\begingroup\$

GolfScript, 90 characters

+:q;:f[]*:^[]:r\{.,{(^3${1=}%-f{2$\?)},~-q{(3$={-.}*;}/{.[[2$\]]4$|3$c;}%;;;}{;:r}if;}:c~r

The program does a simple recursive search on the names. It actually calculates all possible lists but saves them to a variable for output, so only the last one is returned.

The input/output is on the interpreter stack (first families then two previous years` assignments), e.g.

#PREPARE INPUT
;
[["John" "Anna"]["Mark" "James"]["Elizabeth" "Daniel" "Isabelle"]["Ryan" "Ruth"]]
[["Ruth" "John"] ["Ryan" "Daniel"] ["Isabelle" "Mark"] ["Daniel" "Anna"] ["Elizabeth" "James"] ["James" "Elizabeth"] ["Mark" "Ryan"] ["Anna" "Isabelle"] ["John" "Ruth"]]
[["Ruth" "Anna"] ["Ryan" "Elizabeth"] ["Isabelle" "John"] ["Daniel" "James"] ["Elizabeth" "Mark"] ["James" "Daniel"] ["Mark" "Isabelle"] ["Anna" "Ruth"] ["John" "Ryan"]]

#PROGRAM
+:q;:f[]*:^[]:r\{.,{(^3${1=}%-f {2$\?)},~-q{(3$={-.}*;}/{.[[2$\]]4$|3$c;}%;;;}{;:r}if;}:c~r

#SHOW OUTPUT
p

prints the output

[["Ruth" "Elizabeth"] ["Ryan" "John"] ["Isabelle" "James"] ["Daniel" "Mark"] ["Elizabeth" "Anna"] ["James" "Ruth"] ["Mark" "Daniel"] ["Anna" "Ryan"] ["John" "Isabelle"]]
Improve this answer
\$\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.