11
\$\begingroup\$

Another problem from our internal golfing...this one around the holidays last year.

PROBLEM

Andy, Barb, Carl, Didi, Earl, and Fran are buying gifts for each other. Draw names for a gift exchange.

  1. Each person buys one gift and receives one gift.
  2. Nobody buys their own gift.
  3. Running the solution multiple times should produce different results (giver-receiver pair should not be predictable or identical from run to run).

INPUT

None.

OUTPUT

Formatted as in this example:

Andy buys for Barb
Barb buys for Carl
Carl buys for Didi
Didi buys for Earl
Earl buys for Fran
Fran buys for Andy

\$\endgroup\$
  • \$\begingroup\$ Should the output be sorted by name? \$\endgroup\$ – Eelvex Feb 11 '11 at 15:52
  • \$\begingroup\$ @Eelvex Nope, not necessary. \$\endgroup\$ – Steve Feb 12 '11 at 0:11
  • 1
    \$\begingroup\$ This was duplicated by a question today and the keyword I searched for didn't turn it up, so for future searches: derangement. \$\endgroup\$ – Peter Taylor Nov 26 '12 at 22:23

15 Answers 15

4
\$\begingroup\$

J, 57

(,.' buys for ',"1|.)(?~6){6 4$'AndyBarbCarlDidiEarlFran'

eg

   (,.' buys for ',"1|.)(?~6){6 4$'AndyBarbCarlDidiEarlFran'
Carl buys for Earl
Andy buys for Barb
Fran buys for Didi
Didi buys for Fran
Barb buys for Andy
Earl buys for Carl
\$\endgroup\$
  • \$\begingroup\$ I don't know [J], but would this work if the names had with different lengths? \$\endgroup\$ – zx8754 Nov 11 '16 at 14:53
  • \$\begingroup\$ No. The code exploits the fact that all names are 4 characters long. It'll work for different lengths with very few changes. \$\endgroup\$ – Eelvex Nov 11 '16 at 20:36
  • \$\begingroup\$ This also exploits that there is an even number of people. Note that if X gives to Y, Y will always give to X too. \$\endgroup\$ – Adám Mar 5 at 11:23
3
\$\begingroup\$

c99 -- 252 characters

#include <stdio.h>
#define G for(i=0;i<6;i++)
char*n="Andy\0Barb\0Carl\0Didi\0Earl\0Fran",*p[7];int i,j;int main()
{FILE*r=fopen("/dev/random","r");G p[i]=n+5*i;G{j=fgetc(r)%6;p[7]=p[j]
;p[j]=p[i];p[i]=p[7];}G printf("%s buys for %s\n",p[i],p[(i+1)%6]);}

Slight improvement by taking advantage of the circular nature of the permutation. This version always builds a loop-like buying strategy, so it is less random than the previous (271 character) version, but I believe it still meets the spec.

Requires a platform that has a working /dev/random. I ought to be able to knock about 8 off by omitting the \0s in the big string, but my libc doesn't seem to be dealing with %4s print specifiers the way the man page says.

The shuffle is bad, but doing it that way prevents me from having to check on "Foo buys for Foo" conditions.

Readable:

#include <stdio.h>

char *n="Andy\0Barb\0Carl\0Didi\0Earl\0Fran",
  *p[7]; /* 7th cell for temp */
int i,j;

int main(){
  FILE*r=fopen("/dev/random","r");
  for(i=0;i<6;i++)
    p[i]=n+5*i;   /* Initialize the pointers */
  for(i=0;i<6;i++){
    j=fgetc(r)%6; /* Poor numeric properties. Cest le Code Golf */
    p[7]=p[j];
    p[j]=p[i];
    p[i]=p[7];
  }
  for(i=0;i<6;i++)
    printf("%s buys for %s\n",p[i],p[(i+1)%6]);
}
\$\endgroup\$
3
\$\begingroup\$

Windows PowerShell, 83

$i=random 5
($n=-split'Andy Barb Carl Didi Earl Fran')|%{"$_ buys for "+$n[++$i%6]}

History:

  • 2011-02-11 22:01 (136) – First attempt.
  • 2011-02-11 22:05 (130) – Inlined a few things. Shuffling the names now, not the indexes.
  • 2011-02-13 16:13 (128) – I don't need the modulus as $i will be recreated every time.
  • 2011-02-13 16:20   (87) – Borrowed the idea from Anon.'s C# solution. Just generate a random offset and then just let them gift in circles.
  • 2011-02-13 16:26   (83) – Changed random number generation and indexing. Pulled $_ into the string to save the +.
\$\endgroup\$
3
\$\begingroup\$

Haskell, 241 189 characters

import Data.List
import Random
main=randomRIO(0,719)>>=mapM_ putStrLn.f
f n=map(\(x,y)->x++" buys for "++y).zip(l n).tail$cycle$l n
l=(permutations(words"Andy Barb Carl Didi Earl Fran")!!)

Fully random output (that still satisfies the spec).

This generates all permutations of the list of the names, picks one at random (I think this is the shortest way in Haskell to shuffle a list - if anyone has anything smaller, I'd appreciate it), and then each person then buys a present for the next person in the list.

\$\endgroup\$
  • \$\begingroup\$ I tried this ad-hoc, I'm not shure whether it works: paste.ubuntuusers.de/399798 \$\endgroup\$ – FUZxxl Feb 11 '11 at 19:00
  • \$\begingroup\$ @Anon: permutations$words"Andy Barb Carl Didi Earl Fran" and some other tricks I tried in my improved version. I forgot, that permutations isn't included in the 98 List, so you have to use the long name either. Have a look at it. \$\endgroup\$ – FUZxxl Feb 11 '11 at 20:29
  • \$\begingroup\$ And for your special purpose: r=tail.cycle. and than inline it. \$\endgroup\$ – FUZxxl Feb 11 '11 at 20:33
  • \$\begingroup\$ Got it down to 202 chars. Have a look: paste.ubuntuusers.de/399799 \$\endgroup\$ – FUZxxl Feb 11 '11 at 20:49
  • 1
    \$\begingroup\$ And for 189 chars, replace the third line in my example with: main=randomRIO(0,719)>>=mapM_ putStrLn.f \$\endgroup\$ – FUZxxl Feb 11 '11 at 20:54
3
\$\begingroup\$

Golfscript: 72 64 57 chars

"AndyBarbCarlDidiEarlFran"4/{;9rand}${.n+\' buys for '}%(

Tests

$ golfscript codegolf-838.gs 
Fran buys for Carl
Carl buys for Andy
Andy buys for Barb
Barb buys for Didi
Didi buys for Earl
Earl buys for Fran

$ golfscript codegolf-838.gs 
Didi buys for Earl
Earl buys for Andy
Andy buys for Barb
Barb buys for Carl
Carl buys for Fran
Fran buys for Didi
  • Thanks gnibbler for "AndyBarbCarlDidiEarlFran"4/, updated and got 7 chars less
  • 57 chars solution is basically by Nabb :D, and also noticed that ;9rand is more random than my 6rand*
\$\endgroup\$
  • 1
    \$\begingroup\$ "AndyBarbCarlDidiEarlFran"4/ \$\endgroup\$ – gnibbler Feb 11 '11 at 14:01
  • \$\begingroup\$ ah ha, thank you @gnibbler, cool, going to update it. \$\endgroup\$ – YOU Feb 11 '11 at 14:03
  • \$\begingroup\$ Not sure why you're using 6rand* -- 0=rand or maybe ;9rand is preferable. For the loop, {.n+\' buys for '}%( is shorter.. \$\endgroup\$ – Nabb Feb 13 '11 at 18:31
  • \$\begingroup\$ heh; became same chars count with J now :D and thank you @Nabb, I used 6rand* because I thought It will equally randomize the 6 items array (I think I was wrong, since ;9rand looks really random than mine) \$\endgroup\$ – YOU Feb 14 '11 at 1:08
3
+200
\$\begingroup\$

Japt -R, 41 bytes

`AÌ)B¼C¤E¤FÎÂDi¹`qe ö¬ê1 ò mq` ¿ys f 

-2 bytes thanks to @Oliver!

Try it!

This is the approach I took at a high level:

  • uncompress a string containing participants names
  • split string into an array
  • shuffle it
  • assign each person to the person with the next highest index
  • the last person in the array gets assigned to the first

I have a little history with this problem as I created a "secret santa" program for my work years ago. We ended up asking a few job applicants to work through it as well :)

\$\endgroup\$
  • \$\begingroup\$ @Oliver - thanks for the tips! It looks like the ã is not returning a pair that links the first to the last element. I'm working on a way to get this to work, but thought I'd let you know. Thanks again though! ethproductions.github.io/japt/… \$\endgroup\$ – dana Mar 4 at 3:16
  • \$\begingroup\$ 43? \$\endgroup\$ – dana Mar 4 at 3:32
  • 1
    \$\begingroup\$ Ah, you're right. I think this would work for 42 \$\endgroup\$ – Oliver Mar 4 at 3:44
  • 1
    \$\begingroup\$ 41 bytes \$\endgroup\$ – Oliver Mar 4 at 3:56
  • \$\begingroup\$ Wait what does the "q" in the .ö("q") do \$\endgroup\$ – ASCII-only Mar 4 at 4:59
2
\$\begingroup\$

Python - 118 chars

from random import*;L="Andy Barb Carl Didi Earl Fran".split()
for i in sample(range(6),6):print L[i-1],"buys for",L[i]

Python - 120 chars

import random as R;L="Andy Barb Carl Didi Earl Fran".split();R.shuffle(L)
for i in range(6):print L[i-1],"buys for",L[i]
\$\endgroup\$
2
\$\begingroup\$

R - 85 characters

paste(n<-sample(c('Andy','Barb','Carl','Didi','Earl','Fran')),'buys for',n[c(6,1:5)])
\$\endgroup\$
1
\$\begingroup\$

Python - 154 chars

import random as R;L="Andy Barb Carl Didi Earl Fran".split();M=L[:]
while any(map(str.__eq__,L,M)):R.shuffle(M) 
for i in zip(L,M):print"%s buys for %s"%i
\$\endgroup\$
  • \$\begingroup\$ Apologies, my Python is severely lacking...is the while loop there basically looping until it finds a solution that avoids "X buys for X"? \$\endgroup\$ – Steve Feb 11 '11 at 1:16
  • \$\begingroup\$ @Steve: That's pretty much what it does. map calls str.__eq__ on each pair of corresponding values in L and M, and the loop keeps going until none of them are true. \$\endgroup\$ – Anon. Feb 11 '11 at 1:21
  • \$\begingroup\$ @Steve, yes. although it is probably shorter to jsut shift the records by a random amount from 1 to 5, I think that's not in the spirit of the question \$\endgroup\$ – gnibbler Feb 11 '11 at 1:22
  • \$\begingroup\$ When I first posed the question at work, you're exactly right. My coworkers quickly pointed out it wasn't ruled out by my definitions...so I left it as is when posting here. \$\endgroup\$ – Steve Feb 11 '11 at 1:24
1
\$\begingroup\$

D: 233 Characters

import std.random,std.stdio;void main(){auto p=["Andy","Barb","Carl","Didi","Earl","Fran"];auto q=p.dup;o:while(1){for(int i;i<6;++i)if(p[i]==q[i]){randomShuffle(q);continue o;}break;}foreach(i,a;p)writefln("%s buys for %s",a,q[i]);}

More Legibly:

import std.random, std.stdio;

void main()
{
    auto p = ["Andy", "Barb", "Carl", "Didi", "Earl", "Fran"];
    auto q = p.dup;

    o:while(1)
    {
        for(int i; i < 6; ++i)
            if(p[i] == q[i])
            {
                randomShuffle(q);
                continue o;
            }

        break;
    }

    foreach(i, a; p)
        writefln("%s buys for %s", a, q[i]);
}
\$\endgroup\$
1
\$\begingroup\$

Python (175)

import random as r
n=['Andy','Barb','Carl','Didi','Earl','Fran']
m=n[:]
r.shuffle(m)
b=' buys for '
for i in n:
 h=m.pop()
 while h==i:
  m.append(h)
  h=m.pop()
 print(i+b+h)
\$\endgroup\$
1
\$\begingroup\$

Scheme, 173

Gives one of two solutions.

(define(m lst)
    (printf"~v buys for ~v~n"(car lst)(cadr lst))
    (if(eq?(cadr lst)'Andy)0(m(cdr lst)))
)
(m((if(odd?(random 2))reverse values)'(Andy Barb Carl Didi Earl Fran Andy)))
\$\endgroup\$
1
\$\begingroup\$

C#, 210 183 characters

using System;class a{static void Main(){var n="Andy Barb Carl Didi Earl Fran".Split();var c=0,i=new Random().Next(1,6);for(;c<6;c++)Console.WriteLine(n[c]+" buys for "+n[(c+i)%6]);}}

Heaps of boilerplate :(

This solution isn't totally random - there are always one or more "loops" of people e.g. A->C->E->A, and the offsets are always the same in the loops. However, it is not possible to predict the output of a particular run unless you have part of that output.

\$\endgroup\$
  • \$\begingroup\$ That's the interpretation I was intending (and basically the solution we landed on as well). \$\endgroup\$ – Steve Feb 11 '11 at 1:18
  • \$\begingroup\$ Should be 210. are you counting the newline at the end of the file? \$\endgroup\$ – gnibbler Feb 11 '11 at 4:01
  • \$\begingroup\$ @gnibbler: I probably was. I just catted the file into wc, I'm not really going to count that by hand. \$\endgroup\$ – Anon. Feb 11 '11 at 4:03
  • 1
    \$\begingroup\$ What about var n="Andy Barb Carl Didi Earl Fran".Split()? Saves 16 bytes. You can leave out the argument to Main(), which saves another 9 bytes. And you can combine the declaration of c and i: int c,i=...;for(c=0;... which saves another two. \$\endgroup\$ – Joey Feb 12 '11 at 12:11
  • \$\begingroup\$ @Joey: Tweaked it as per your suggestions, thanks. \$\endgroup\$ – Anon. Feb 13 '11 at 20:00
0
\$\begingroup\$

Ruby - 89 chars

(a=%w(Andy Barb Carl Didi Earl Fran).shuffle).zip(a.reverse).each{|e|puts e*' buys for '}

Output:

Andy buys for Didi
Barb buys for Earl
Fran buys for Carl
Carl buys for Fran
Earl buys for Barb
Didi buys for Andy
\$\endgroup\$
  • 1
    \$\begingroup\$ You can use map instead of each. \$\endgroup\$ – Dogbert Feb 11 '11 at 20:43
  • 1
    \$\begingroup\$ the problem with this solution is that if you have an odd number of people the middle person will gift themselves Earl buys for Mark Fran buys for Andy Barb buys for Carl Didi buys for Didi Carl buys for Barb Andy buys for Fran Mark buys for Earl \$\endgroup\$ – StudleyJr Nov 26 '12 at 21:59
0
\$\begingroup\$

MathGolf, 41 bytes

"δ%è╘+µ√♂JÇ"2/$╦╕ää▐δáw_╪" buys for "+m+n

Try it online!

Explanation

This is not guaranteed to produce each case with equal probability, but it does produce different results each run. One byte could be removed if I had a shuffle operator, but that's for another day.

"δ%è╘+µ√♂JÇ"                                push the string "δ%è╘+µ√♂JÇ"
            2/                              split into segments of two characters
              $                             transform to ordinals using base 256
               ╦                            fetch dictionary words (['Andy', 'barb', 'Carl', 'Earl', 'Fran'])
                ╕ää                         Push "didi"
                   ▐                        append to end of list
                    δ                       capitalize all strings in list
                     áw                     sort by random character in each string (shuffle)
                       _                    duplicate TOS
                        ╪                   right-rotate bits in int, list, str
                         " buys for "       push the string " buys for "
                                     +      Add to all strings in list
                                      m+    zip add the two arrays
                                        n   join array with newline
\$\endgroup\$

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.