# Holiday Gift Exchange

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

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

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

## 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

• I don't know [J], but would this work if the names had with different lengths? Commented Nov 11, 2016 at 14:53
• No. The code exploits the fact that all names are 4 characters long. It'll work for different lengths with very few changes. Commented Nov 11, 2016 at 20:36
• 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.
– Adám
Commented Mar 5, 2019 at 11:23

# 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 :)

• @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/…
– dana
Commented Mar 4, 2019 at 3:16
• 43?
– dana
Commented Mar 4, 2019 at 3:32
• Ah, you're right. I think this would work for 42 Commented Mar 4, 2019 at 3:44
• 41 bytes Commented Mar 4, 2019 at 3:56
• Wait what does the "q" in the .ö("q") do Commented Mar 4, 2019 at 4:59

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


## 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 +. # 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. • I tried this ad-hoc, I'm not shure whether it works: paste.ubuntuusers.de/399798 Commented Feb 11, 2011 at 19:00 • @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. Commented Feb 11, 2011 at 20:29
• And for your special purpose: r=tail.cycle. and than inline it. Commented Feb 11, 2011 at 20:33
• Got it down to 202 chars. Have a look: paste.ubuntuusers.de/399799 Commented Feb 11, 2011 at 20:49
• And for 189 chars, replace the third line in my example with: main=randomRIO(0,719)>>=mapM_ putStrLn.f Commented Feb 11, 2011 at 20:54

## 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* • "AndyBarbCarlDidiEarlFran"4/ Commented Feb 11, 2011 at 14:01 • ah ha, thank you @gnibbler, cool, going to update it. – YOU Commented Feb 11, 2011 at 14:03 • Not sure why you're using 6rand* -- 0=rand or maybe ;9rand is preferable. For the loop, {.n+\' buys for '}%( is shorter.. – Nabb Commented Feb 13, 2011 at 18:31 • 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) – YOU Commented Feb 14, 2011 at 1:08 ## 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]  R - 85 characters paste(n<-sample(c('Andy','Barb','Carl','Didi','Earl','Fran')),'buys for',n[c(6,1:5)])  ## 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  • Apologies, my Python is severely lacking...is the while loop there basically looping until it finds a solution that avoids "X buys for X"? Commented Feb 11, 2011 at 1:16 • @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. Commented Feb 11, 2011 at 1:21 • @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 Commented Feb 11, 2011 at 1:22 • 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. Commented Feb 11, 2011 at 1:24 # 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]); }  ## 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)  # 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)))  ## 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. • That's the interpretation I was intending (and basically the solution we landed on as well). Commented Feb 11, 2011 at 1:18 • Should be 210. are you counting the newline at the end of the file? Commented Feb 11, 2011 at 4:01 • @gnibbler: I probably was. I just catted the file into wc, I'm not really going to count that by hand. Commented Feb 11, 2011 at 4:03 • 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. – Joey Commented Feb 12, 2011 at 12:11 • @Joey: Tweaked it as per your suggestions, thanks. Commented Feb 13, 2011 at 20:00 # 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  • You can use map instead of each. Commented Feb 11, 2011 at 20:43 • 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 Commented Nov 26, 2012 at 21:59 # 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
`