The weekly challenge 388 - Task 1: Dyck Words

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-388/#TASK1
 3 #
 4 # Task 1: Dyck Words
 5 # ==================
 6 #
 7 # A Dyck Word of order $n is a string of length 2x$n consisting of $n ‘U’ (Up)
 8 # characters and $n ‘D’ (Down) characters such that no initial prefix of the
 9 # string contains more ‘D’s than ‘U’s.
10 #
11 # Write a script to return a list of all valid Dyck words of length 2x$n,
12 # sorted in lexicographical (alphabetical) order.
13 #
14 ## Example 1
15 ##
16 ## Input: $n = 1
17 ## Output: ("UD")
18 #
19 ## Example 2
20 ##
21 ## Input: $n = 2
22 ## Output: ("UDUD","UUDD")
23 #
24 ## Example 3
25 ##
26 ## Input: $n = 3
27 ## Output: ("UDUDUD", "UDUUDD", "UUDDUD", "UUDUDD", "UUUDDD")
28 #
29 ## Example 4
30 ##
31 ## Input: $n = 0
32 ## Output: ("")
33 #
34 ## Example 5
35 ##
36 ## Input: $n = 4
37 ## Output: ("UDUDUDUD", "UDUDUUDD", "UDUUDDUD", "UDUUDUDD", "UDUUUDDD",
38 ##          "UUDDUDUD", "UUDDUUDD", "UUDUDDUD", "UUDUDUDD", "UUDUUDDD",
39 ##          "UUUDDDUD", "UUUDDUDD", "UUUDUDDD", "UUUUDDDD")
40 #
41 ############################################################
42 ##
43 ## discussion
44 ##
45 ############################################################
46 #
47 # We just calculate all options recursively:
48 # - We start with an empty string
49 # - As long as we still have U's or D's available:
50 #   - recursively create all options starting at the current string:
51 #     - if there are more U's, create all new results from the current
52 #       results by adding a "U" and recursively go further with one less U
53 #     - if there are more D's than U's, create all new results from the current
54 #       results by adding a "D" and recursively go further with one less D
55 # When there are no more U's and D's left, return the result.
56 
57 use v5.36;
58 
59 sub dyck_words($n) {
60     say "Input: $n";
61     my @result = find_dyck_words($n, $n, (""));
62     say "Output: (" . join(", ", map { "\"$_\"" } @result) . ")";
63 }
64 
65 sub find_dyck_words($n1, $n2, @current_result) {
66     my @result = ();
67     return @current_result if $n1 == 0 and $n2 == 0;
68     if($n1 > 0) {
69         foreach my $elem (@current_result) {
70             push @result, find_dyck_words($n1-1, $n2, ("${elem}U"));
71         }
72     }
73     if($n2 > $n1) {
74         foreach my $elem (@current_result) {
75             push @result, find_dyck_words($n1, $n2-1, ("${elem}D"));
76         }
77     }
78     return @result;
79 }
80 
81 dyck_words(1);
82 dyck_words(2);
83 dyck_words(3);
84 dyck_words(0);
85 dyck_words(4);