PWC 382 Replace Question Marks

Task 2: Replace Question Mark

You are given a string that contains only 0, 1 and ? characters.

Write a script to generate all possible combinations when replacing the question marks with a zero or one.

Example 1: Input: $str = "01??0"
Output: ("01000", "01010", "01100", "01110")

Cogitation

The "?" reminds me of shell file name expansion. In bash and similar shells, a question mark acts as a wild card, and there is also the expansion that a group in braces expands to all combinations of the things in braces. For example,

$ echo "a{01}b"
a0b a1b

Perl can do the same trick with the glob function, performing the expansion into a list:

say $_ for glob("a{0,1}b");

So a one-liner solution converts every '?' into the string "{0,1}" and then applies glob.

perl -wE 'say join " ", glob($ARGV[0] =~ s/\?/{0,1}/gr )' "a?c"
a0ca1c

More fun would be to process the substitution. Create a queue of possible strings, starting with the given string. Take the string from the head of the queue and replace it with two new strings that have a "0" and "1" in place of the question mark; put those strings at the end of the queue. If there are no question marks, then that's a final string that's part of the solution.

Implementation

sub task($str)
{
    my @replaced;

    my @queue = ( $str );
    while ( defined(my $s = shift @queue) )
    {
        if ( index($s, '?') >= 0 )
        {
            push @queue, ($s =~ s/\?/0/r), ($s =~ s/\?/1/r);
        }
        else
        {
            push @replaced, $s;
        }
    }

    return \@replaced;
}

Notes:

• I like to use index instead of regular expression match when I can, because it's (probably) more efficient.
• Multiple things can be pushed onto a list in one statement.