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.

Examples

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

Example 2
Input: $str = '101'
Output: ('101')

Example 3
Input: $str = '???'
Output: ('000', '001', '010', '011', '100', '101', '110', '111')

Example 4
Input: $str = '1?10'
Output: ('1010', '1110')

Example 5
Input: $str = '1?1?0'
Output: ('10100', '10110', '11100', '11110')

Analysis

My solution first counts the question marks as $marks.

The 1 or 0 replacements for these can be written as all the integers in binary format from 0 up to 2 ** $marks - 1. So if $marks == 3, the 8 replacements are 000, 001, 010, 011, 100, 101, 110 and 111.

I generate these in a simple loop:

for $perm (0 .. 2 ** $marks - 1) {
   $bits = sprintf("%.${marks}b", $perm);
}

which generates each of the binary numbers as the string $bits.

It's then just a case of substituting the characters in $bits for the question marks in the input string:

$input =~ s|\?|substr($bits, $_, 1)|e for 0 .. $marks - 1;

There is a potential criticisms of this solution which is that it will fail if there are more than 63 question marks in the input, because a Perl power of 2 integer (in a 64-bit environment) is limited to 2⁶³.

If there are 64 question marks, there are 2⁶⁴ permutations of 64 characters, which we are to present in quotes and followed by a comma and a space, so that's 68 characters times 2⁶⁴ = 1.2 × 10²¹ bytes of output, or about 1,000,000,000,000 gigabytes of output.

I think my solution is good enough.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge/382/2

use v5.26;    # The Weekly Challenge - 2026-07-13
use utf8;     # Week 382 - task 2 - Replace question mark
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

replace_question_mark('01??0');
replace_question_mark('10101');
replace_question_mark('?0?0?');
replace_question_mark('');
replace_question_mark('???????');

sub replace_question_mark {

    my ($bits, $input, $j, $marks, $perm, $result, $this); 
    
    # initialise
    $input = $_[0];
    say qq[\nInput:  '$input'];
    $result = '';
    
    # count question marks and loop over possible 0/1 combinations
    $marks = $input =~ y|?|?|;
    for $perm (0 .. 2 ** $marks - 1) {
        
        # create binary 0/1 number with $marks digits
        $bits = sprintf("%.${marks}b", $perm);          
        
        # replace each ? with 0 or 1 from bits and save result
        $this = $input;
        $this =~ s|\?|substr($bits, $_, 1)|e for 0 .. $marks - 1;
        $result .= qq['$this', ];           
    }
    
    # report
    say qq[Output: ] . substr($result, 0, -2);
}

12 lines of code

Output from script

Input:  '01??0'
Output: '01000', '01010', '01100', '01110'

Input:  '10101'
Output: '10101'

Input:  '?0?0?'
Output: '00000', '00001', '00100', '00101', '10000', '10001', '10100',
   '10101'

Input:  ''
Output: ''

Input:  '???????'
Output: '0000000', '0000001', '0000010', '0000011', '0000100',
   '0000101', '0000110', '0000111', '0001000', '0001001', '0001010',
   '0001011', '0001100', '0001101', '0001110', '0001111', '0010000',
   '0010001', '0010010', '0010011', '0010100', '0010101', '0010110',
   '0010111', '0011000', '0011001', '0011010', '0011011', '0011100',
   '0011101', '0011110', '0011111', '0100000', '0100001', '0100010',
   '0100011', '0100100', '0100101', '0100110', '0100111', '0101000',
   '0101001', '0101010', '0101011', '0101100', '0101101', '0101110',
   '0101111', '0110000', '0110001', '0110010', '0110011', '0110100',
   '0110101', '0110110', '0110111', '0111000', '0111001', '0111010',
   '0111011', '0111100', '0111101', '0111110', '0111111', '1000000',
   '1000001', '1000010', '1000011', '1000100', '1000101', '1000110',
   '1000111', '1001000', '1001001', '1001010', '1001011', '1001100',
   '1001101', '1001110', '1001111', '1010000', '1010001', '1010010',
   '1010011', '1010100', '1010101', '1010110', '1010111', '1011000',
   '1011001', '1011010', '1011011', '1011100', '1011101', '1011110',
   '1011111', '1100000', '1100001', '1100010', '1100011', '1100100',
   '1100101', '1100110', '1100111', '1101000', '1101001', '1101010',
   '1101011', '1101100', '1101101', '1101110', '1101111', '1110000',
   '1110001', '1110010', '1110011', '1110100', '1110101', '1110110',
   '1110111', '1111000', '1111001', '1111010', '1111011', '1111100',
   '1111101', '1111110', '1111111'