As soon as I saw the title of this week's challenge, I had to run to Google. As a person with a German surname that is sometimes mispronounced for sophomoric humor, I did not want to fall into that trap. Sure enough, that name is pronounced "deek", so let's restrain ourselves, shall we?
On the other hand, as a person with the emotional maturity of a fourteen-year-old, I am well aware of the Letterkenny Dycks. So, take a moment and I'll meet you back here.
Now that we have that out of our system, let's begin.
Task 1:: Dyck Words
A Dyck Word of order n is a string of length 2n 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 2n, sorted in lexicographical (alphabetical) order.
-
Example 1: _Input:
$n = 1-
Output:
("UD")
-
Output:
-
Example 2: Input:
$n = 2-
Output:
("UDUD","UUDD")
-
Output:
-
Example 3: Input:
$n = 3-
Output:
("UDUDUD", "UDUUDD", "UUDDUD", "UUDUDD", "UUUDDD")
-
Output:
-
Example 4: Input:
$n = 0-
Output:
("")
-
Output:
-
Example 5: Input:
$n = 4-
Output:
("UDUDUDUD", "UDUDUUDD", "UDUUDDUD", "UDUUDUDD", "UDUUUDDD", "UUDDUDUD", "UUDDUUDD", "UUDUDDUD", "UUDUDUDD", "UUDUUDDD","UUUDDDUD", "UUUDDUDD", "UUUDUDDD", "UUUUDDDD")
-
Output:
Discussion
This pattern can be visualized as walking along a grid, starting at (0,0), staying entirely inside the wedge between 0° and 45°, and ending back on the x axis. If you replace 'U' and 'D' with '(' and ')', it represents strings with balanced parentheses.
Generating these strings is going to be some kind of recursive algorithm. While checking on the pronunciation of "Dyck", I stumbled on a CPAN module, Math::DyckWords, that implements these strings. Peeking at the source code, sure enough there's a recursive algorithm. Just like AI, I'm going to train myself by scanning a public web site, regurgitating something similar, taking credit for it, and skimming over the ethical implications.
Implementation
Working top-down, I'm going to assume that there's a function that can return a list of appropriate strings. I'll handle the special case of 0, and turn the list into the sorted set that the problem specifies. Because of the way the recursion works, and because we've chosen to use the letters U and D, it turns out that the list comes back in reverse alphabetical order, so we can avoid sorting.
sub task($n)
{
my $result = $n ? generateDyck($n) : [""];
return [ reverse $result->@* ];
}
On to the meat of the problem. My recursive function will have a signature that reflects how deep into the string we've come.
sub generateDyck($n, $dyck=[], $word='U', $nU=1, $nD=0, $depth=1)
{
[ . . . ]
}
I'm making generous use of default values for parameters. The first call from task() is just generateDyck($n), so all the rest of the parameters will get their values from the signature. The list of words will accumulate in the $dyck array. The word we're currently working on is in $word. Our first character is always a 'U', and the counts reflect that. The $depth parameter is the depth of the recursion; it's not really necessary but helps in debugging.
To build the string, we add a letter at a time, preferring 'U' first. The number of D's can never get ahead of the number of U's. Eventually we return the reference to the list of words; the return value is only really used at the top-level call.
# We have space to add both a U and a D
if ( $nU < $n && $nD < $n && $nU > $nD )
{
# U goes before D
generateDyck( $n, $dyck, $word . 'U', $nU + 1, $nD , $depth++ );
generateDyck( $n, $dyck, $word . 'D', $nU, $nD + 1 , $depth++ );
}
# We have space, but a U must be next
if ( ( $nU < $n && $nD < $n && $nU == $nD ) ||
( $nU < $n && $nD == $n ) )
{
generateDyck( $n, $dyck, $word . 'U', $nU + 1, $nD , $depth++ );
}
if ( $nU == $n )
{
# We have all the Us, must add enough D to balance.
if ( $nD < $n )
{
my $need = $n - $nD;
generateDyck( $n, $dyck, $word . ('D' x $need), $nU, $nD + $need , $depth++ );
}
else # $nD == $n
{
# We have n of each, so save a complete word.
push @$dyck, $word;
}
}
return $dyck;
