RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved gift allocation and letter pairs. (Note that this ends today.)

Task 1: Secret Santa

Secret Santa is a Christmas tradition in which members of a group are randomly assigned a person to whom they give a gift.

You are given a list of names. Write a script that tries to team persons from different families.

I suspect this is actually best approached as a flow network problem and solved with Ford-Fulkerson (or Edmonds-Karp). But I am lazy. So I take a two pass approach for each donor:

(1) find a member of another family who isn't yet receiving a gift. Give it to them. Failing that:

(2) find a member of your own family who isn't yourself. Give it to them.

This is obviously subject to failure states depending on the input configuration. Rust:

fn secretsanta(name: Vec<&str>) -> bool {

We have full names in name. Build a parallel list of family names in family.

    let mut family = Vec::new();
    for n in &name {
        let surname = n.split(' ').last().unwrap();
        family.push(surname);
    }

Set up a set of recipient indices.

    let mut receivers: HashSet<usize> = HashSet::from_iter(0..name.len());
    let mut gifting: Vec<Vec<String>> = Vec::new();

For each donor:

    for giver in 0..name.len() {
        let mut done = false;
        let mut r = 0;

If we find a recipient who's not in the same family, use that.

        for recipient in &receivers {
            if family[giver] != family[*recipient] {
                r = *recipient;
                done = true;
                break;
            }
        }

Otherwise, if we find a recipient who's not the donor, use that.

        if !done {
            for recipient in &receivers {
                if recipient != &giver {
                    r = *recipient;
                    break;
                }
            }
        }

Remove that recipient and log the gift transfer.

        receivers.remove(&r);
        gifting.push(vec![name[giver].to_string(), name[r].to_string()]);
    }
    for p in gifting {
        println!("{} -> {}", p[0], p[1]);
    }
    println!("");
    true
}

Task 2: Most Frequent Letter Pair

You are given a string S of lower case letters 'a'..'z'.

Write a script that finds the pair of consecutive letters in S that appears most frequently. If there is more than one such pair, chose the one that is the lexicographically first.

This seems to fall very neatly into a set of operations:

• Generate all the letter pairs in the string
• Put them into a counted hash
• Find the highest count
• Filter the hash keys to just the ones with the highest count
• Sort those remaining hash keys and return the first.

Raku:

sub mostfrequentletterpair($s) {
    my %f;

Generate the pairs and hash them:

    for (0 .. chars($s) - 2) -> $i {
        my $pair = substr($s, $i, 2);
        %f{$pair}++;
    }

Find the highest:

    my $m = max(values %f);

Filter the hash keys and sort them.

    my @l = %f.keys.grep({%f{$_} == $m}).sort({$^a cmp $^b});

Return the first.

    return @l[0];
}

Full code on github.