1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-382/#TASK2
 3 #
 4 # Task 2: Replace Question Mark
 5 # =============================
 6 #
 7 # You are given a string that contains only 0, 1 and ? characters.
 8 #
 9 # Write a script to generate all possible combinations when replacing the
10 # question marks with a zero or one.
11 #
12 ## Example 1
13 ##
14 ## Input: $str = "01??0"
15 ## Output: ("01000", "01010", "01100", "01110")
16 #
17 ## Example 2
18 ##
19 ## Input: $str = "101"
20 ## Output: ("101")
21 #
22 ## Example 3
23 ##
24 ## Input: $str = "???"
25 ## Output: ("000", "001", "010", "011", "100", "101", "110", "111")
26 #
27 ## Example 4
28 ##
29 ## Input: $str = "1?10"
30 ## Output: ("1010", "1110")
31 #
32 ## Example 5
33 ##
34 ## Input: $str = "1?1?0"
35 ## Output: ("10100", "10110", "11100", "11110")
36 #
37 ############################################################
38 ##
39 ## discussion
40 ##
41 ############################################################
42 #
43 # We recursively create all possible outputs: First, we split the
44 # input string into digits, then we recursively
45 # - pick the first character as $first
46 # - create all possible outputs for the remaining digits
47 # - if $first is "?", create "0$str" and "1$str" for all $str in
48 #   the results of the remaining digits. Otherwise, just add
49 #   "$first$str" for each of them
50 # - in the end, sort the result for a consistent result
51 #
52 
53 use v5.36;
54 
55 replace_question_mark("01??0");
56 replace_question_mark("101");
57 replace_question_mark("???");
58 replace_question_mark("1?10");
59 replace_question_mark("1?1?0");
60 
61 sub replace_question_mark($str) {
62     say "Input: \"$str\"";
63     my @digits = split //, $str;
64     my @result = get_replaced(@digits);
65     say "Output: (\"" . join("\", \"", sort @result) . "\")";
66 }
67 
68 sub get_replaced(@digits) {
69     return ("") unless @digits;
70     my $first = shift @digits;
71     my @tmp = get_replaced(@digits);
72     my @result;
73     if($first eq "?") {
74         foreach my $elem (@tmp) {
75             push @result, "0$elem";
76             push @result, "1$elem";
77         }
78     } else {
79         foreach my $elem (@tmp) {
80             push @result, "$first$elem";
81         }
82     }
83     return @result;
84 }