## This Week's Contribution to Perl 6 Week 9: Implement Hash.pick for Rakudo

For this week's contribution to Perl 6 we ask you to implement the `Hash.pick` method (which does a weighted random selection) for Rakudo.

## Background

In Perl 6 the `List` class has a method called `pick`, which randomly selects one item from a list. It has a few more options too:

```<a b c>.pick;       # pick one random element
<a b c>.pick(2);    # pick two distinct, random elements
<a b c>.pick(2, :replace); # pick two random elements, it's ok
# if they are the same
<a b c>.pick(*);    # return a random permutation of the elements
<a b c>.pick(*, :replace); # infinite, random stream of elements
```

This is already implemented through several multi methods in Rakudo.

Now the specification describes such a method for hashes too (actually it talks about Bags, but Rakudo doesn't have Bags yet. Pretend it says "Hash" instead). It assumes that each value in the hash is numeric, and that the value is a weight that determines the probability of picking one value. For example

```{a => 1, b => 2}.pick;  # returns 'a' with probability 1/3
# and 'b' with probability 2/3

{a => 1, b => 2}.pick(*);  # <a b b> with probability 1/3
# <b a b> with probability 1/3
# <b b a> with probability 1/3
{a => 1, b => 0.5}.pick(*) # dies, because the weights aren't all integers
{a => 1, b => 0.5}.pick(*, :replace)  # ok
```

## What you can do

Implement Hash.pick. It's ok if your patch doesn't cover all cases. It would be nice if it supported non-integer weights.

Hint: this could be done by storing a list of accumulated weights, and a list of keys.

```{a => 1, b => 2.5, c => 1}

# could translate to
my @keys = ('a', 'b', 'c');
my @accumulated_weights = (1, 3.5, 4.5);

# now pick a random number between 0 and 4.5,
# find the next-highest index in @accumulated_weights
# with a binary search, and then use that to obtain the key.
```

Of course other schemes are fine too.

Second hint: because it takes quite some time to recompile Rakudo, it is probably easier to implement the actual logic in a function in a normal source file first, and only later move it into src/core/Hash.pm.

## Submission

Please submit your source code to the perl6-compiler@perl.org mailing list (and put moritz.lenz@gmail.com on CC, because the mailing list sometimes lack quite a bit).

Update: there's one submission on the perl6-compiler mailing list already, which looks pretty good.

Trackback URL: `/blog-en.trackback`