| 28 August 2026 | Challenge 388 |
Secret Words
Task 1: Dyck Words
Submitted by: Roger Bell_West
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")
Solution
Looking at the prefixes of a Dyck Word:
A Dyck Prefix of length \(k\) is a string of length \(k\) consisting of ‘U’ (Up) and ‘D’ (Down) characters such that no initial prefix of the string contains more ‘D’s than ‘U’s.
Every prefix of a Dyck Prefix is a Dyck Prefix itself.
OTOH, appending an ‘U’ to a Dyck Prefix results in a valid prefix. If - additionally - a Dyck Prefix contains more ‘Up’s than ‘Downs’, then appending a ‘D’ results in a valid prefix, too.
Taking the empty string as the Dyck Prefix of length zero, with the above two rules all Dyck Prefixes of length \(k > 0\) can constructed from the Dyck Prefixes of length \(k - 1\).
When the two rules are applied in reversed order to each of the shorter prefixes, the resulting list is in lexicographical order.
The Dyck Words of order \(n\) then can be found from the Dyck Prefixes of length \(2n\) that have an equal number of ‘Up’s and ‘Downs’.
Certainly there are more efficient ways to solve this task - in time and space.
[Update]
Inspired by spying at other solutions, I modified the process:
Considering Dyck Prefixes of length \(k\) of a Dyck Word of order \(c\).
- Appending a ‘D’ if there are more ‘U’s than ‘D’s.
- Appending a ‘U’ if the number of ‘U’s is less than \(c\).
This avoids the generation of unneeded prefixes.
Perl
[Original version]
Recursively build the list of Dyck Prefixes (memoizing intermediate results) and select the Dyck Words thereof.
use strict;
use warnings;
use List::Gather;
use Memoize;
use experimental 'signatures';
sub dyck_words {
state sub eq_ud :prototype(_) {
return tr/U// == tr/D// for shift;
}
state $dp;
$dp //= memoize sub ($k) {
return '' unless $k;
gather {
take +($_.'D') x !eq_ud, $_.'U' for $dp->($k - 1);
};
};
grep eq_ud, $dp->(2 * shift);
}
See the full solution to task 1.
[Updated version]
This is the implementation of the modified process.
I dropped memoization because intermediate results now depend on the target order and are no longer universally usable.
use strict;
use warnings;
use List::Gather;
use experimental 'signatures';
sub dyck_words ($n, $k=2*$n) {
return '' unless $k;
gather {
for (__SUB__->($n, $k - 1)) {
my $up = tr/U//;
take $_.'D' if 2 * $up >= $k;
take $_.'U' if $up < $n;
}
};
}
See the full solution.
Comparing both versions:
$ /usr/bin/time perl/ch-1.pl 13 | wc -w
11.51user 1.17system 0:12.76elapsed 99%CPU (0avgtext+0avgdata 2927804maxresident)k
0inputs+0outputs (0major+723006minor)pagefaults 0swaps
742900
$ /usr/bin/time perl/ch-1a.pl 13 | wc -w
1.30user 0.09system 0:01.44elapsed 96%CPU (0avgtext+0avgdata 230912maxresident)k
344inputs+0outputs (6major+49299minor)pagefaults 0swaps
742900
J
My J implementation was faulty. Results for \(n \ge 7\) were erroneous.
Removed it.
Task 2: Secret Santa
Submitted by: Roger Bell_West
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.
Solution
This task asks for the number \(!n\) of permutations that are fixed point free, a.k.a. derangements.
An explicit formula to calculate \(!n\) is:
\[!n = n! \sum_{i=0}^n\frac{(-1)^i}{i!}\]As the ratio \(\frac{n!}{!n}\) rapidly converges towards \(e\), the approximation \(!n \approx \frac{n!}{e}\) can actually be used to calculate the exact number of derangements very easily from the factorial. One of several formulas is:
\[!n = \bigg\lfloor \frac{n! + 1}{e} \bigg\rfloor \text{ for } n > 0\]See Wikipedia.
Perl
Using Math::Prime::Util::factorial
to calculate the factorial.
use strict;
use warnings;
use Math::Prime::Util 'factorial';
sub derangements {
int((factorial(shift) + 1) / exp(1));
}
See the full solution to task 2.
[Update]
Looking at Choroba’s solution I realized that a new function
subfactorial providing the number of derangements was added quite recently to Math::Prime::Util.
My solution looks a bit silly now.
J
J has a built-in primitive to calculate the factorial.
derangements =: <. @ (%&(^1)) @ >: @ !
(] ,. derangements) >: i.6
1 0
2 1
3 2
4 9
5 44
6 265
See the full solution .