RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved sequence generation and derangement. (Note that this ends today.)

Task 1: Dyck Words

A Dyck Word of order $n is a string of length 2×$n consisting of $n 'U' (Up) characters and $n 'D' (Down) characters such that no initial prefix of the string contains more 'D's than 'U's.

Write a script to return a list of all valid Dyck words of length 2x$n, sorted in lexicographical (alphabetical) order.

The simplest approach would be to generate all strings of the right length and then filter the prefixes. I get very slightly more sophisticated by using a breadth-first search pattern, and not generating any prefixes with more D than U. (I do not attempt to even out the number of elements of each type; that's done with a filter when the string has reached its target length.)

In Raku:

sub dyckwords($order) {

Set up the output list and the initial queue containing an empty string.

    my @out;
    my @queue = ("",);

Take the first fragment off the queue.

    while (@queue.elems > 0) {
        my $st = @queue.shift;

Count the Ds in it.

        my $dcount = $st.comb.grep(/D/).elems;

If it's the right length to be a possible answer,

        if ($st.chars == $order * 2) {

and it has the right number of Ds,

            if ($dcount == $order) {

append it to the list of answers.

                @out.push($st);
            }

If it's not long enough,

        } else {

If it can take an additional D, append one to make a new candidate.

            if ($dcount * 2 < $st.chars) {
                @queue.push($st ~ 'D');
            }

And in any case, append a U to make a new candidate. (The strings with too many Us will be caught by the final filter.)

            @queue.push($st ~ 'U');
        }
    }
    @out;
}

Task 2: Secret Santa

A company with $n employees is running a Secret Santa exchange. Each employee buys one gift and receives one gift.

Write a script to return the total number of valid gift assignments where no employee receives the gift they originally bought (i.e., employee $i must not be assigned gift $i).

I don't often do recursion but it seems like the right tool for the job here; this is OEIS A000166, the number of derangements of an n-element set, and the easiest way to build it is recursively.

Typst:

#let secretsanta(n) = {
  if n == 0 {
    1
  } else if n == 1 {
    0
  } else {
    (n - 1) * (secretsanta(n - 1) + secretsanta(n - 2))
  }
}

Or in Scala, which has a match-case type structure:

  def secretsanta(n: Int): Int = {
    n match {
      case 0 => 1
      case 1 => 0
      case _ => (n - 1) * (secretsanta(n - 1) + secretsanta(n - 2));
    }
  }

Full code in all tagged languages is on codeberg.