Task 1: Dyck Word
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 contains more 'D's than 'U's. Write a script to return a list of all valid Dyck words of length 2*$n, sorted in lexicographical order.
Example Output
Input: $n = 2
Output: ("UDUD", "UUDD")
Input: $n = 3
Output: ("UDUDUD", "UDUUDD", "UUDDUD", "UUDUDD", "UUUDDD")
Logic
Use recursive backtracking to generate valid sequences. At each step, if the count of 'D's is less than 'U's, we can branch by appending 'D'. If the count of 'U's is less than n, we can branch by appending 'U'. Because 'D' comes before 'U' alphabetically, trying 'D' before 'U' at each decision point naturally produces the results in lexicographical order.
Perl Solution
ch-1.pl
sub dyck_words ($n) {
return [''] if $n == 0;
my @result;
my $generate;
$generate = sub ( $current, $u_count, $d_count ) {
if ( $u_count == $n && $d_count == $n ) {
push @result, $current;
return;
}
if ( $d_count < $u_count ) {
$generate->( $current . 'D', $u_count, $d_count + 1 );
}
if ( $u_count < $n ) {
$generate->( $current . 'U', $u_count + 1, $d_count );
}
};
$generate->( '', 0, 0 );
return \@result;
}
Python Solution
ch-1.py
def dyck_words(n: int) -> list[str]:
"""Return all valid Dyck words of length 2*n in lexicographical order."""
if n == 0:
return [""]
result: list[str] = []
def generate(current: str, u_count: int, d_count: int) -> None:
if u_count == n and d_count == n:
result.append(current)
return
if d_count < u_count:
generate(current + "D", u_count, d_count + 1)
if u_count < n:
generate(current + "U", u_count + 1, d_count)
generate("", 0, 0)
return result
Task 2: Secret Santa
A company with $n employees is running a Secret Santa exchange. Write a script to return the total number of valid gift assignments where no employee receives the gift they originally bought (derangements of $n elements).
Example Output
Input: $n = 3
Output: 2
Input: $n = 4
Output: 9
Input: $n = 5
Output: 44
Logic
This problem asks for the number of derangements (subfactorial !n). We can compute this iteratively using the standard recurrence relation:
D(1) = 0, D(2) = 1, and for i >= 3, D(i) = (i - 1) * (D(i - 1) + D(i - 2)) in O(n) time and O(1) space.
Perl Solution
ch-2.pl
sub secret_santa ($n) {
return 0 if $n <= 1;
return 1 if $n == 2;
my $prev2 = 0; # D(1)
my $prev1 = 1; # D(2)
my $curr = 1;
for my $i ( 3 .. $n ) {
$curr = ( $i - 1 ) * ( $prev1 + $prev2 );
$prev2 = $prev1;
$prev1 = $curr;
}
return $curr;
}
Python Solution
ch-2.py
def secret_santa(n: int) -> int:
"""Return the number of derangements for n items."""
if n <= 1:
return 0
if n == 2:
return 1
prev2 = 0 # D(1)
prev1 = 1 # D(2)
curr = 1
for i in range(3, n + 1):
curr = (i - 1) * (prev1 + prev2)
prev2 = prev1
prev1 = curr
return curr