16
1
Background
I have a collection of "weekday socks", which are seven pairs of socks labeled by the days of the week. When I wash my socks, they end up in a pile, and I must arrange them into the correct pairs before putting them into the closet. My strategy is to pull one random sock from the pile at a time and put it on a drawer. Whenever there's a matching pair of socks on the drawer, I tie them together and put them in the closet. Your task is to simulate this random process and return the number of draws required to find the first matching pair.
Input
Your input is an integer N ≥ 1. It represents the "number of days in a week": there are N pairs of socks in the pile, and each pair has a distinct label. If necessary, you may also take a PRNG seed as input.
Output
Your output is the number of socks I have to draw before the first matching pair is found.
For example, if the first two socks already form a matching pair, the output is 2
.
Of course, the output is random, and depends on the drawing order. We assume that all drawing orders are equally likely, so that each time a sock is drawn, the choice is uniform and independent from all other choices.
Example
Let N = 3, so that we have 6 socks in total, labeled A A B B C C. One possible run of the "sock-drawing protocol" is as follows:
| Pile | Drawer | Pairs
Begin | AABBCC | - | -
Draw B | AABCC | B | -
Draw C | AABC | BC | -
Draw B | AAC | C | BB
Draw A | AC | AC | BB
Draw A | C | C | AA BB
Draw C | - | - | AA BB CC
The first matching pair was found after drawing the second B, which was the third sock to be drawn, so the correct output is 3
.
Rules and scoring
You can write a full program or a function.
The lowest byte count wins, and standard loopholes are disallowed.
Input and output can be in any reasonable format, including unary (string of 1
s).
You may assume that your language's built-in RNG is perfect. You don't have to actually simulate the sock-drawing protocol, as long as your outputs have the correct probability distribution.
"Test cases"
Here are the approximate probabilities of all outputs for the input N = 7:
Output 2 3 4 5 6 7 8
Probability 0.077 0.154 0.210 0.224 0.186 0.112 0.037
To test your solution, you can run it for, say, 40 000 times and see whether the output distribution is reasonably close to this.
25Real Life, 42 bytes --
Draw all socks. End up with an odd number.
– AdmBorkBork – 2016-08-02T15:11:29.6472
See How to pair socks from a pile efficiently?
– Dada – 2016-08-02T15:52:29.417So n=8 is not equal to 1->7 and then 1 again? i.e. 4 socks labeled 1 – Viktor Mellgren – 2016-08-03T09:10:48.010
@ViktorMellgren No, you would have 8 distinct labels. – Zgarb – 2016-08-03T09:43:32.510
I have a drawer full of identical socks, so there is no need to sort through them. – JDługosz – 2016-08-03T16:43:14.683
In which universe "all drawing orders are equally likely" for socks? Not in ours, that's for sure! – hyde – 2016-08-03T20:20:17.730