Secret Dyck
with Raku

by Arne Sommer

Secret Dyck with Raku

[413] Published 30. August 2026.

This is my response to The Weekly Challenge #388.

#388.1 Dyck Words A Dyck Word of order $n is a string of length 2x$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.

Example 1: 
Input: $n = 1
Output: ("UD")
Example 2: 
Input: $n = 2
Output: ("UDUD","UUDD")
Example 3: 
Input: $n = 3
Output: ("UDUDUD", "UDUUDD", "UUDDUD", "UUDUDD", "UUUDDD")
Example 4: 
Input: $n = 0
Output: ("")
Example 5: 
Input: $n = 4
Output: ("UDUDUDUD", "UDUDUUDD", "UDUUDDUD", "UDUUDUDD", "UDUUUDDD",
         "UUDDUDUD", "UUDDUUDD", "UUDUDDUD", "UUDUDUDD", "UUDUUDDD",
         "UUUDDDUD", "UUUDDUDD", "UUUDUDDD", "UUUUDDDD")

I could have used recursion, but have chosen to use a queue (first in, first out) instead as that should be faster - and easier to understand. Note that the result is a sorted list, so we do not have to do anyting besides printing it.

I have assigned the value +1 to Up, and -1 to Down. The initial height is zero, if the think of them as floor numbers. The «initial prefix of the string contains more ‘D’s than ‘U’s» rule then becomes a rule that the height cannot be negative.

File: dyck-words 
#! /usr/bin/env raku

unit sub MAIN (UInt $n, :v(:$verbose));

my @done;
my @todo = ( { word => "", height => 0, D => $n, U => $n }, );

while @todo
{
  my $current = @todo.shift;

  say ": Working on word:'$current<word>', todo D:$current<D> \
    todo U:$current<U> height:$current<height>" if $verbose;

  if $current<D> == $current<U> == 0
  {
    @done.push: $current<word>;
    next;
  }

  if $current<D> && $current<height>
  {
    @todo.push: { word   => $current<word> ~ "D",
                  height => $current<height> -1,
                  D      => $current<D> -1,
                  U      => $current<U>  };
  }

  if $current<U>
  {
    @todo.push: { word   => $current<word> ~ "U",
                  height => $current<height> +1,
                  D      => $current<D>,
                  U      => $current<U> -1 };
  }
}

say "({ @done.join(", ") })";

[3] An unsigned integer, so 0 (the fourth example) is allowed.

[5] The result will end up here.

[6] Unfinished words are kept in this queue. We bootstrap it with the initial state; the word is empty, the height is at ground level (0), and the remaining Ds and Us are both set to $n.

[8] As long as the we have partial words in the queue.

[10] Get the first one.

[15] Do we have a full word (i.e. no Ds and Us left)?

[17] If so, add it to the result,

[18] and continue with the next iteration of the loop.

[21] Any Ds left, and the level is positive (actually non zero)?

[23] If so, append a D to the partial word and add it to the queue.

Note the if on the next one, and not elsif, so that both the Up and Down can be triggered in the same iteration. (I used next in [18] to make the logic simpler.)

[29] Any Us left?

[31] If so, append an U to the partial word and add it to the queue.

[38] Pretty print the result, which is already sorted.

Running it: 

$ ./dyck-words 1
(UD)

$ ./dyck-words 2
(UDUD, UUDD)

$ ./dyck-words 3
(UDUDUD, UDUUDD, UUDDUD, UUDUDD, UUUDDD)

$ ./dyck-words 0
()

$ ./dyck-words 4
(UDUDUDUD, UDUDUUDD, UDUUDDUD, UDUUDUDD, UDUUUDDD, UUDDUDUD, UUDDUUDD, \
 UUDUDDUD, UUDUDUDD, UUDUUDDD, UUUDDDUD, UUUDDUDD, UUUDUDDD, UUUUDDDD)

Looking good.

With verbose mode: 

$ ./dyck-words -v 1
: Working on word:'', todo D:1 todo U:1 height:0
: Working on word:'U', todo D:1 todo U:0 height:1
: Working on word:'UD', todo D:0 todo U:0 height:0
(UD)

$ ./dyck-words -v 2
: Working on word:'', todo D:2 todo U:2 height:0
: Working on word:'U', todo D:2 todo U:1 height:1
: Working on word:'UD', todo D:1 todo U:1 height:0
: Working on word:'UU', todo D:2 todo U:0 height:2
: Working on word:'UDU', todo D:1 todo U:0 height:1
: Working on word:'UUD', todo D:1 todo U:0 height:1
: Working on word:'UDUD', todo D:0 todo U:0 height:0
: Working on word:'UUDD', todo D:0 todo U:0 height:0
(UDUD, UUDD)

$ ./dyck-words -v 3
: Working on word:'', todo D:3 todo U:3 height:0
: Working on word:'U', todo D:3 todo U:2 height:1
: Working on word:'UD', todo D:2 todo U:2 height:0
: Working on word:'UU', todo D:3 todo U:1 height:2
: Working on word:'UDU', todo D:2 todo U:1 height:1
: Working on word:'UUD', todo D:2 todo U:1 height:1
: Working on word:'UUU', todo D:3 todo U:0 height:3
: Working on word:'UDUD', todo D:1 todo U:1 height:0
: Working on word:'UDUU', todo D:2 todo U:0 height:2
: Working on word:'UUDD', todo D:1 todo U:1 height:0
: Working on word:'UUDU', todo D:2 todo U:0 height:2
: Working on word:'UUUD', todo D:2 todo U:0 height:2
: Working on word:'UDUDU', todo D:1 todo U:0 height:1
: Working on word:'UDUUD', todo D:1 todo U:0 height:1
: Working on word:'UUDDU', todo D:1 todo U:0 height:1
: Working on word:'UUDUD', todo D:1 todo U:0 height:1
: Working on word:'UUUDD', todo D:1 todo U:0 height:1
: Working on word:'UDUDUD', todo D:0 todo U:0 height:0
: Working on word:'UDUUDD', todo D:0 todo U:0 height:0
: Working on word:'UUDDUD', todo D:0 todo U:0 height:0
: Working on word:'UUDUDD', todo D:0 todo U:0 height:0
: Working on word:'UUUDDD', todo D:0 todo U:0 height:0
(UDUDUD, UDUUDD, UUDDUD, UUDUDD, UUUDDD)

$ ./dyck-words -v 0
: Working on word:'', todo D:0 todo U:0 height:0
()

$ ./dyck-words -v 4
: Working on word:'', todo D:4 todo U:4 height:0
: Working on word:'U', todo D:4 todo U:3 height:1
: Working on word:'UD', todo D:3 todo U:3 height:0
: Working on word:'UU', todo D:4 todo U:2 height:2
: Working on word:'UDU', todo D:3 todo U:2 height:1
: Working on word:'UUD', todo D:3 todo U:2 height:1
: Working on word:'UUU', todo D:4 todo U:1 height:3
: Working on word:'UDUD', todo D:2 todo U:2 height:0
: Working on word:'UDUU', todo D:3 todo U:1 height:2
: Working on word:'UUDD', todo D:2 todo U:2 height:0
: Working on word:'UUDU', todo D:3 todo U:1 height:2
: Working on word:'UUUD', todo D:3 todo U:1 height:2
: Working on word:'UUUU', todo D:4 todo U:0 height:4
: Working on word:'UDUDU', todo D:2 todo U:1 height:1
: Working on word:'UDUUD', todo D:2 todo U:1 height:1
: Working on word:'UDUUU', todo D:3 todo U:0 height:3
: Working on word:'UUDDU', todo D:2 todo U:1 height:1
: Working on word:'UUDUD', todo D:2 todo U:1 height:1
: Working on word:'UUDUU', todo D:3 todo U:0 height:3
: Working on word:'UUUDD', todo D:2 todo U:1 height:1
: Working on word:'UUUDU', todo D:3 todo U:0 height:3
: Working on word:'UUUUD', todo D:3 todo U:0 height:3
: Working on word:'UDUDUD', todo D:1 todo U:1 height:0
: Working on word:'UDUDUU', todo D:2 todo U:0 height:2
: Working on word:'UDUUDD', todo D:1 todo U:1 height:0
: Working on word:'UDUUDU', todo D:2 todo U:0 height:2
: Working on word:'UDUUUD', todo D:2 todo U:0 height:2
: Working on word:'UUDDUD', todo D:1 todo U:1 height:0
: Working on word:'UUDDUU', todo D:2 todo U:0 height:2
: Working on word:'UUDUDD', todo D:1 todo U:1 height:0
: Working on word:'UUDUDU', todo D:2 todo U:0 height:2
: Working on word:'UUDUUD', todo D:2 todo U:0 height:2
: Working on word:'UUUDDD', todo D:1 todo U:1 height:0
: Working on word:'UUUDDU', todo D:2 todo U:0 height:2
: Working on word:'UUUDUD', todo D:2 todo U:0 height:2
: Working on word:'UUUUDD', todo D:2 todo U:0 height:2
: Working on word:'UDUDUDU', todo D:1 todo U:0 height:1
: Working on word:'UDUDUUD', todo D:1 todo U:0 height:1
: Working on word:'UDUUDDU', todo D:1 todo U:0 height:1
: Working on word:'UDUUDUD', todo D:1 todo U:0 height:1
: Working on word:'UDUUUDD', todo D:1 todo U:0 height:1
: Working on word:'UUDDUDU', todo D:1 todo U:0 height:1
: Working on word:'UUDDUUD', todo D:1 todo U:0 height:1
: Working on word:'UUDUDDU', todo D:1 todo U:0 height:1
: Working on word:'UUDUDUD', todo D:1 todo U:0 height:1
: Working on word:'UUDUUDD', todo D:1 todo U:0 height:1
: Working on word:'UUUDDDU', todo D:1 todo U:0 height:1
: Working on word:'UUUDDUD', todo D:1 todo U:0 height:1
: Working on word:'UUUDUDD', todo D:1 todo U:0 height:1
: Working on word:'UUUUDDD', todo D:1 todo U:0 height:1
: Working on word:'UDUDUDUD', todo D:0 todo U:0 height:0
: Working on word:'UDUDUUDD', todo D:0 todo U:0 height:0
: Working on word:'UDUUDDUD', todo D:0 todo U:0 height:0
: Working on word:'UDUUDUDD', todo D:0 todo U:0 height:0
: Working on word:'UDUUUDDD', todo D:0 todo U:0 height:0
: Working on word:'UUDDUDUD', todo D:0 todo U:0 height:0
: Working on word:'UUDDUUDD', todo D:0 todo U:0 height:0
: Working on word:'UUDUDDUD', todo D:0 todo U:0 height:0
: Working on word:'UUDUDUDD', todo D:0 todo U:0 height:0
: Working on word:'UUDUUDDD', todo D:0 todo U:0 height:0
: Working on word:'UUUDDDUD', todo D:0 todo U:0 height:0
: Working on word:'UUUDDUDD', todo D:0 todo U:0 height:0
: Working on word:'UUUDUDDD', todo D:0 todo U:0 height:0
: Working on word:'UUUUDDDD', todo D:0 todo U:0 height:0
(UDUDUDUD, UDUDUUDD, UDUUDDUD, UDUUDUDD, UDUUUDDD, UUDDUDUD, UUDDUUDD, \
 UUDUDDUD, UUDUDUDD, UUDUUDDD, UUUDDDUD, UUUDDUDD, UUUDUDDD, UUUUDDDD)

#388.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).

Example 1: 
Input: $n = 1
Output: 0

Only 1 participant exists. They would have to receive their own gift,
which is invalid.
Example 2: 
Input: $n = 2
Output: 1

Participants 1 and 2 must swap gifts ([2, 1]).
Example 3: 
Input: $n = 3
Output: 2

The 2 valid gift arrays where array[i] is who person i+1 receives from:
[2, 3, 1]
[3, 1, 2]
Example 4: 
Input: $n = 4
Output: 9

The 9 valid arrays are:
[2, 1, 4, 3], [2, 3, 4, 1], [2, 4, 1, 3],
[3, 1, 4, 2], [3, 4, 1, 2], [3, 4, 2, 1],
[4, 1, 2, 3], [4, 3, 1, 2], [4, 3, 2, 1],
Example 5: 
Input: $n = 5
Output: 44

There are 44 valid permutations out of 5! = 120 total possible
arrangements.

I have chosen to assign employee numbers from 0 to $n -1, instead of starting at 1 as the examples do, as that makes the programming logic easier. Now @perm[$x] gives us the source for the gift to employee $x.

File: secret-santa 
#! /usr/bin/env raku

unit sub MAIN (UInt $n where $n > 0, :v(:$verbose));

my $count = 0;

PERM: for (^$n).permutations -> @perm
{
  for ^$n -> $i
  {
    if @perm[$i] == $i
    {
      say ": [{ @perm.join(", ") }] -- (illegal)" if $verbose;
      next PERM;
    }
  }

  say ": [{ @perm.join(", ") }] ++ (legal)" if $verbose;

  $count++;
}

say $count;

[3] Ensure a positive integer.

[5] The result (the number of legal permutations) will end up here.

[7] Iterate over all the possible permutations.

See docs.raku.org/routine/permutations for more information about permutations.

[9] Iterate over the indices (or employee numbers, zero based).

[11] Do this employee receive their own gift?

[14] That is illegal, so skip this permutation.

[20] If the loop in [9] was not short circuited by [14}, then we have a valid permutation. Count it.

[23] Print the result.

Running it: 

$ ./secret-santa 1
0

$ ./secret-santa 2
1

$ ./secret-santa 3
2

$ ./secret-santa 4
9

$ ./secret-santa 5
44

Looking good.

With verbose mode: 

$ ./secret-santa -v 1
: [0] -- (illegal)
0

$ ./secret-santa -v 2
: [0, 1] -- (illegal)
: [1, 0] ++ (legal)
1

$ ./secret-santa -v 3
: [0, 1, 2] -- (illegal)
: [0, 2, 1] -- (illegal)
: [1, 0, 2] -- (illegal)
: [1, 2, 0] ++ (legal)
: [2, 0, 1] ++ (legal)
: [2, 1, 0] -- (illegal)
2

$ ./secret-santa -v 4
: [0, 1, 2, 3] -- (illegal)
: [0, 1, 3, 2] -- (illegal)
: [0, 2, 1, 3] -- (illegal)
: [0, 2, 3, 1] -- (illegal)
: [0, 3, 1, 2] -- (illegal)
: [0, 3, 2, 1] -- (illegal)
: [1, 0, 2, 3] -- (illegal)
: [1, 0, 3, 2] ++ (legal)
: [1, 2, 0, 3] -- (illegal)
: [1, 2, 3, 0] ++ (legal)
: [1, 3, 0, 2] ++ (legal)
: [1, 3, 2, 0] -- (illegal)
: [2, 0, 1, 3] -- (illegal)
: [2, 0, 3, 1] ++ (legal)
: [2, 1, 0, 3] -- (illegal)
: [2, 1, 3, 0] -- (illegal)
: [2, 3, 0, 1] ++ (legal)
: [2, 3, 1, 0] ++ (legal)
: [3, 0, 1, 2] ++ (legal)
: [3, 0, 2, 1] -- (illegal)
: [3, 1, 0, 2] -- (illegal)
: [3, 1, 2, 0] -- (illegal)
: [3, 2, 0, 1] ++ (legal)
: [3, 2, 1, 0] ++ (legal)
9

$ ./secret-santa -v 5
: [0, 1, 2, 3, 4] -- (illegal)
: [0, 1, 2, 4, 3] -- (illegal)
: [0, 1, 3, 2, 4] -- (illegal)
: [0, 1, 3, 4, 2] -- (illegal)
: [0, 1, 4, 2, 3] -- (illegal)
: [0, 1, 4, 3, 2] -- (illegal)
: [0, 2, 1, 3, 4] -- (illegal)
: [0, 2, 1, 4, 3] -- (illegal)
: [0, 2, 3, 1, 4] -- (illegal)
: [0, 2, 3, 4, 1] -- (illegal)
: [0, 2, 4, 1, 3] -- (illegal)
: [0, 2, 4, 3, 1] -- (illegal)
: [0, 3, 1, 2, 4] -- (illegal)
: [0, 3, 1, 4, 2] -- (illegal)
: [0, 3, 2, 1, 4] -- (illegal)
: [0, 3, 2, 4, 1] -- (illegal)
: [0, 3, 4, 1, 2] -- (illegal)
: [0, 3, 4, 2, 1] -- (illegal)
: [0, 4, 1, 2, 3] -- (illegal)
: [0, 4, 1, 3, 2] -- (illegal)
: [0, 4, 2, 1, 3] -- (illegal)
: [0, 4, 2, 3, 1] -- (illegal)
: [0, 4, 3, 1, 2] -- (illegal)
: [0, 4, 3, 2, 1] -- (illegal)
: [1, 0, 2, 3, 4] -- (illegal)
: [1, 0, 2, 4, 3] -- (illegal)
: [1, 0, 3, 2, 4] -- (illegal)
: [1, 0, 3, 4, 2] ++ (legal)
: [1, 0, 4, 2, 3] ++ (legal)
: [1, 0, 4, 3, 2] -- (illegal)
: [1, 2, 0, 3, 4] -- (illegal)
: [1, 2, 0, 4, 3] ++ (legal)
: [1, 2, 3, 0, 4] -- (illegal)
: [1, 2, 3, 4, 0] ++ (legal)
: [1, 2, 4, 0, 3] ++ (legal)
: [1, 2, 4, 3, 0] -- (illegal)
: [1, 3, 0, 2, 4] -- (illegal)
: [1, 3, 0, 4, 2] ++ (legal)
: [1, 3, 2, 0, 4] -- (illegal)
: [1, 3, 2, 4, 0] -- (illegal)
: [1, 3, 4, 0, 2] ++ (legal)
: [1, 3, 4, 2, 0] ++ (legal)
: [1, 4, 0, 2, 3] ++ (legal)
: [1, 4, 0, 3, 2] -- (illegal)
: [1, 4, 2, 0, 3] -- (illegal)
: [1, 4, 2, 3, 0] -- (illegal)
: [1, 4, 3, 0, 2] ++ (legal)
: [1, 4, 3, 2, 0] ++ (legal)
: [2, 0, 1, 3, 4] -- (illegal)
: [2, 0, 1, 4, 3] ++ (legal)
: [2, 0, 3, 1, 4] -- (illegal)
: [2, 0, 3, 4, 1] ++ (legal)
: [2, 0, 4, 1, 3] ++ (legal)
: [2, 0, 4, 3, 1] -- (illegal)
: [2, 1, 0, 3, 4] -- (illegal)
: [2, 1, 0, 4, 3] -- (illegal)
: [2, 1, 3, 0, 4] -- (illegal)
: [2, 1, 3, 4, 0] -- (illegal)
: [2, 1, 4, 0, 3] -- (illegal)
: [2, 1, 4, 3, 0] -- (illegal)
: [2, 3, 0, 1, 4] -- (illegal)
: [2, 3, 0, 4, 1] ++ (legal)
: [2, 3, 1, 0, 4] -- (illegal)
: [2, 3, 1, 4, 0] ++ (legal)
: [2, 3, 4, 0, 1] ++ (legal)
: [2, 3, 4, 1, 0] ++ (legal)
: [2, 4, 0, 1, 3] ++ (legal)
: [2, 4, 0, 3, 1] -- (illegal)
: [2, 4, 1, 0, 3] ++ (legal)
: [2, 4, 1, 3, 0] -- (illegal)
: [2, 4, 3, 0, 1] ++ (legal)
: [2, 4, 3, 1, 0] ++ (legal)
: [3, 0, 1, 2, 4] -- (illegal)
: [3, 0, 1, 4, 2] ++ (legal)
: [3, 0, 2, 1, 4] -- (illegal)
: [3, 0, 2, 4, 1] -- (illegal)
: [3, 0, 4, 1, 2] ++ (legal)
: [3, 0, 4, 2, 1] ++ (legal)
: [3, 1, 0, 2, 4] -- (illegal)
: [3, 1, 0, 4, 2] -- (illegal)
: [3, 1, 2, 0, 4] -- (illegal)
: [3, 1, 2, 4, 0] -- (illegal)
: [3, 1, 4, 0, 2] -- (illegal)
: [3, 1, 4, 2, 0] -- (illegal)
: [3, 2, 0, 1, 4] -- (illegal)
: [3, 2, 0, 4, 1] ++ (legal)
: [3, 2, 1, 0, 4] -- (illegal)
: [3, 2, 1, 4, 0] ++ (legal)
: [3, 2, 4, 0, 1] ++ (legal)
: [3, 2, 4, 1, 0] ++ (legal)
: [3, 4, 0, 1, 2] ++ (legal)
: [3, 4, 0, 2, 1] ++ (legal)
: [3, 4, 1, 0, 2] ++ (legal)
: [3, 4, 1, 2, 0] ++ (legal)
: [3, 4, 2, 0, 1] -- (illegal)
: [3, 4, 2, 1, 0] -- (illegal)
: [4, 0, 1, 2, 3] ++ (legal)
: [4, 0, 1, 3, 2] -- (illegal)
: [4, 0, 2, 1, 3] -- (illegal)
: [4, 0, 2, 3, 1] -- (illegal)
: [4, 0, 3, 1, 2] ++ (legal)
: [4, 0, 3, 2, 1] ++ (legal)
: [4, 1, 0, 2, 3] -- (illegal)
: [4, 1, 0, 3, 2] -- (illegal)
: [4, 1, 2, 0, 3] -- (illegal)
: [4, 1, 2, 3, 0] -- (illegal)
: [4, 1, 3, 0, 2] -- (illegal)
: [4, 1, 3, 2, 0] -- (illegal)
: [4, 2, 0, 1, 3] ++ (legal)
: [4, 2, 0, 3, 1] -- (illegal)
: [4, 2, 1, 0, 3] ++ (legal)
: [4, 2, 1, 3, 0] -- (illegal)
: [4, 2, 3, 0, 1] ++ (legal)
: [4, 2, 3, 1, 0] ++ (legal)
: [4, 3, 0, 1, 2] ++ (legal)
: [4, 3, 0, 2, 1] ++ (legal)
: [4, 3, 1, 0, 2] ++ (legal)
: [4, 3, 1, 2, 0] ++ (legal)
: [4, 3, 2, 0, 1] -- (illegal)
: [4, 3, 2, 1, 0] -- (illegal)
44

And that's it.

Links
 About me
 Keyword Index
 Beginning Raku (book)
 RSS Feed
 Code (zip)
Reddit Comments