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