Possible binaries sum

Question

This challenge is inspired by the AoC 2020, Day 14 - Part II, created by Eric Wastl and his team, which asks to output the possible binary values from a bitmask.

Let's say we've a bitmask like "10X0X0", then we've to find the possible binary values that can be generated by replacing an X with either 0 or 1. Here I've taken X, but you could take anything except 0 and 1, of course.

So, the possible binaries are ["100000", "100010", "101000", "101010"].
When each of them are converted in decimal, then these are [32, 34, 40, 42] respectively.
And, finally the sum is 148.

Test cases

INPUT: "X"
["0", "1"]
[0, 1]
OUTPUT: 1

INPUT: "0"
OUTPUT: 0

INPUT: "1"
OUTPUT: 1

INPUT: "1X0"
["100", "110"]
[4, 6]
OUTPUT: 10

INPUT: "1X0X1"
["10001", "10011", "11001", "11011"]
[17, 19, 25, 27]
OUTPUT: 88

INPUT: "X0X0X0X"
["0000000", "0000001", "0000100", "0000101", "0010000", "0010001", "0010100", "0010101", 
"1000000", "1000001", "1000100", "1000101", "1010000", "1010001", "1010100", "1010101"]
[0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85]
OUTPUT: 680

INPUT: "1X1X1X1X1X1X1X1X1X1X1"
OUTPUT: 1789569024

INPUT: "1X01X01X01X01X01X01X01X01X01X01X01X0"
OUTPUT: 201053554790400

INPUT: "X000X000X000X000X000X000X000X000X000X000X000X000"
OUTPUT: 307445734561824768

INPUT: "101"
["101"]
[5]
OUTPUT: 5

INPUT: "XXX"
["000", "001", "010", "011", "100", "101", "110", "111"]
[0, 1, 2, 3, 4, 5, 6, 7]
OUTPUT: 28

Rules

• It is guaranteed that \$ 0 \leq \text{count}(X) \leq 12 \$ and \$ 1 \leq \text{length(mask)} \leq 48 \$.
• Input can be either a string, or an array of chars (non-empty).
• I have chosen X in bitmask, however you can replace it with any other character of your choice.
• Output will be the sum of the binaries in decimal.
• This is a code-golf, so fewest bytes will win!

---

Sandbox link.

Answer 1

Python 2, 61 bytes

k=n=0
for c in input():n=n*2+-ord(c)%3;k+=c>"1"
print(n<<k)/2

Try it online!

Implements this algorithm:

1. Convert the input from binary, treating X as \$\frac{1}{2}\$.
2. Double the result for each X in the input.

Why does this work? If X appears \$k\$ times in the input, we're adding up \$2^k\$ near-copies of its binary value. Among these near-copies, each X in any position appears as 0 half the time and 1 half the time for an average of \$\frac{1}{2}\$, so we can treat X as the digit \$\frac{1}{2}\$.

In the code, we actually convert 0,X,1 to doubled values 0,1,2, then halve the result before doubling for X's. And, we use _ for X, since we're allowed to use a different character -- anything with the same ASCII code modulo 3 would work, such as the digit 2.

63 bytes

lambda s:(reduce(lambda n,c:2*n+-ord(c)%3,s,0)<<s.count('_'))/2

Try it online!

Answer 2

Haskell, 56 55 bytes

n!(a:x)|a<'X'=(2*n+read[a])!x|m<-4*n=m!x+1!x
n!x=n
(0!)

Try it online!

Explanation

Start with a simple recursive algorithm to convert binary to an integer:

n!(a:x)=(2*n+read[a])!x
n!x=n
(0!)

From here we add an extra rule if we hit an X which just adds the results for the X being 0 and 1 together:

n!('X':x)=n!('0':x)+n!('1':x)
n!(a:x)=(2*n+read[a])!x
n!x=n
(0!)

We can unroll the applications in that:

n!('X':x)=(2*n)!x+(2*n+1)!x
n!(a:x)=(2*n+read[a])!x
n!x=n
(0!)

We can move a 2*n over to the other side since (!x) is affine

n!('X':x)=(4*n)!x+1!x
n!(a:x)=(2*n+read[a])!x
n!x=n
(0!)

From here we combine the pattern matches to save bytes.

Answer 3

JavaScript (ES6), 55 bytes

f=(s,g=d=>f(s.replace('X',d)))=>1/s?+('0b'+s):g(0)+g(1)

Try it online!

Commented

f = (                   // f is a recursive function
  s,                    // taking the input string s
  g = d =>              // g is a helper function taking a digit d
    f(                  // and doing a recursive call to f
      s.replace('X', d) // with the first 'X' in s replaced with d
    )                   //
) =>                    //
  1 / s ?               // if s looks like a number (i.e. does not contain any 'X'):
    +('0b' + s)         //   convert it from binary to decimal
  :                     // else:
    g(0) +              //   invoke g a 1st time to replace the first 'X' with '0'
    g(1)                //   invoke g a 2nd time to replace the first 'X' with '1'

Answer 4

Bash, 38

echo $[`eval echo +2\#${1//X/{0,1\}}`]

Try it online!

Answer 5

J, 47 bytes

1#.#.@(]`(_ I.@E.[)`[}"#.[:#:@i.@(**2&^)1#._&=)

Try it online!

Not super happy with this one...

Answer 6

R, 156 142 78 61 56 52 51 50 bytes

In the entry of the bitmask, 2 replaces X.

Thanks to Giuseppe, came a reduction in unnecessary brackets in an earlier version recreating the binary duplications.

However, a more condensed version can be found by realising that the sum is the sum of the inverse of the non-zero digits, times 2 to the power of the number of 2's, ie

                                        

which actually happens to be the solution earlier worked out by xnor. With improvements from Dominic achieving the same score as this earlier solution and more from Giuseppe!

function(x)2^sum(a<-x>1)*rev(x/4^a)%*%2^(seq(x)-1)

Try it online!

Answer 7

05AB1E, 14 12 bytes

Y1ÝI2¢ãδ.;CO

Uses 2 instead of X.

Try it online.

Explanation:

 1Ý           # Push the list [0,1]
   I2¢        # Count the amount of 2s in the input-string
      ã       # Take the cartesian product of [0,1] with this count
       δ      # Map over each inner list of 0s and 1s:
Y       .;    #  Replace every 2 in the (implicit) input-string one by one with the 0s
              #  and 1s in the current list
          C   # Convert each binary string to a base-10 integer
           O  # Sum the list together
              # (after which the result is output implicitly)

---

Fun alternative that's unfortunately a byte longer (13 bytes):

TIgãʒøþ€ËP}CO

Uses X.

Try it online.

Explanation:

T           # Push 10
 Ig         # Push the length of the input-string
   ã        # Take the cartesian product of "10" with this count
    ʒ       # Filter this list of binary strings by:
     ø      #  Zip/transpose it with the (implicit) input, creating pairs
      þ     #  Remove all "X" from each pair by only leaving digits
       €Ë   #  Check for each if all digits are the same
            #  (this checks if the 1s and 0s are at the same positions between the 
            #   current binary string and input; and since we've removed all "X" those
            #   single digits are truthy by default)
         P  #  Check if this is truthy for all of them with the product
    }C      # After the filter: convert any remaining binary string to a base-10 integer
      O     # Sum the list together
            # (after which the result is output implicitly)

Answer 8

Haskell, 53 bytes

sum.foldl(%)[0]
l%c=[2*a+1-read[b]|a<-l,b<-"01",b/=c]

Try it online!

Implements the spec somewhat directly, using a modified from-binary conversion that works on lists of digits to produce lists of possible outcomes. Any character can be used for X except of course for 0 and 1.

Answer 9

Husk, 11 bytes

*ΠfI¹ḋm?I\ε

Try it online!

Port of xnor's approach. Input is list of binary digits (0 or 1), with 2 to represent the bitmask.
13 bytes to accept input as an integer instead of a list.

*               # multiply
 Π              # product of 
  fI¹           # non-zero elements of input
     ḋ          # by binary number with digits given by
      m         # mapping over all digits of input
       ?  ε     # if digit is equal to at most 1
        I       # leave it alone
         \      # otherwise take reciprocal

Answer 10

Perl 5 -p, 35 bytes

s/X/{0,1}/g;map$\+=oct"0b$_",glob}{

Try it online!

Answer 11

MATLAB, 55 46 bytes

@(x)2.^(nnz(x):-1:1)*mod(x'*2,3)/4*2^nnz(x>49)

Inspired by the Python solution of xnor. But here we don't use a loop, we work with array operators.

Thanks to Luis Mendo for replacing the sum of element-wise products by the dot product (-5 bytes).

Instead of X, it expects _ as input:

ans('1_0_1')
ans =
    88

etc.

Answer 12

Wolfram Language (Mathematica), 67 bytes

Distribute@StringReplace[#,"X"->"0"+"1"]/.s_String:>s~FromDigits~2&

Try it online!

-1,2,...50...61 bytes from @att

Answer 13

K (oK), 37 bytes

{(*/(+/t)#2)*{y+2*x}/x-48+1.5*t:x=50}

Try it online!

Inspired by xnor's Python solution.

Answer 14

Jelly, (9?) 12 bytes

^{9 if we may accept a list of integers (e.g. "0X1X0" as [0,2,1,2,0]) - remove the leading V€µ.}

V€µẹ2ŒPṬạḂḄS

A monadic Link accepting a list of characters from "012" ('2' representing an unknown bit) which yields the sum.

Try it online!

How?

V€µẹ2ŒPṬạḂḄS - Link: list of characters, S    e.g. "022001"
V€           - convert (S) to a list of integers   [0,2,2,0,0,1]
  µ          - start a new monadic chain, f(A=that)
   ẹ2        - indices of 2                        [2,3]
     ŒP      - power-set                           [[],[2],[3],[2,3]]
       Ṭ     - un-truth                            [[],[0,1],[0,0,1],[0,1,1]]
         Ḃ   - mod-2 (A)                           [0,0,0,0,0,1]
        ạ    - absolute difference                 [[0,0,0,0,0,1],[0,1,0,0,0,1],[0,0,1,0,0,1],[0,1,1,0,0,1]]
          Ḅ  - convert from binary                 [1,17,9,25]
           S - sum                                 52

Answer 15

C (gcc), 71 bytes

c,s;f(char*m){for(c=1,s=0;*m;88-*m++||(s++,c*=2))s+=s+=*m==49;c=c*s/2;}

Try it online!

• Saved 2 bytes thanks to @Ceilingcat
• Works only for small numbers (int) added unsigned long in header to test 1X1X1X1X1X1X1X1X1X1X1

We iterate a char array: s is sum
c is number of masks, initially 1

s+=*m==49  - we add 1 if we have '1'
s*=2       - then we multiply by 2
88-*m++||  - if we have a 'X'
(s++,c*=2) - we add 1 and we double number of possible masks. 

c=c*s/2    - finally we multiply sum by c and divide by 2 because we multiplied sum one time more than needed.

Answer 16

K (ngn/k), 27 20 bytes

{_2/0.5^x,&+/^x:.'x}

Try it online!

Modeled after @Galen Ivanov's oK answer. Uses " " in place of "X" in the input.

• x:.'x convert input string to a list of integer digits, updating variable x (spaces in the input become (::)s, i.e. null functions)
• &+/^ generate n 0's, where n is the number of blanks in the input
• x, append these 0's to the end of the digit-ified input
• 0.5^ fill nulls with 0.5's
• _2/ convert from base-2 and take the floor

Answer 17

Stax, 20 bytes

år╢T>∩E%>►ΣD"╬@☼≡ ╫^

Run and debug it

Shortened from 32 by borrowing the idea from Kevin Cruijssen's answer.

Answer 18

Octave, 66 59 bytes

@(x)(t=0:2^nnz(x)-1)*all(abs(dec2bin(t)*2-mod(2*x,99))<2,2)

Uses character b instead of X. Runs out of memory for the two longest test cases.

Try it online!

Answer 19

Wolfram Language (Mathematica), 43 bytes

d[c=0;d/@#/. 2:>++c^0/2,2]2^c&
d=FromDigits

Try it online!

Input a list of characters. Uses 2 instead of X.

Answer 20

Retina 0.8.2, 41 29 bytes

+%1`X
0$'¶$`1
1
01
+`10
011
1

Try it online! Link includes smaller test cases (code uses unary arithmetic so large numbers won't work on TIO). Explanation:

+%1`X
0$'¶$`1

Repeatedly replace each line containing an X with two copies of that line, one with a 0 and one with a 1 in place of the first X.

1
01
+`10
011

Convert each line from binary to unary.

1

Take the sum and convert to decimal.

Answer 21

Charcoal, 18 bytes

Ｉ÷×↨Ｅθ⌕0X1ι²Ｘ²№θX²

Try it online! Link is to verbose version of code. Explanation: Based on @xnor's algorithm.

     θ              Input string
    Ｅ               Map over characters
      ⌕             Find index of
          ι         Current character
       0X1          In literal string `0X1`
   ↨       ²        Convert from "binary"
  ×                 Multiply by
             ²      Literal `2`
            Ｘ       Raised to power
              №     Count of
                X   Literal string `X`
               θ    In input string
 ÷                  Integer divide by
                 ²  Literal `2`
Ｉ                   Cast to string
                    Implicitly print

Answer 22

Scala, 61 bytes

_./:(Set(0)){(a,c)=>for(s<-a;d<-Set(c%2,c%3))yield s*2+d}.sum

Try it online!

Turns out X's value of 88 is perfect for this algorithm.

A simple binary-to-decimal conversion would look like this in Scala. /: is the fold operator. Starting with 0, you multiply 0 by 2 and add the first digit. Then you multiply that by 2 again and add the next digit, and so on.

(0 /: listOfInts)((a, c) => 2 * a + c)

This is very similar, except now we're folding with multiple integers, and we're taking the sum at the end. In the lambda used for folding, a is all the accumulated sums, and c is the next character. For every sum s in a (for(s<-a), for every possible digit d that c could represent d<-Set(c%2,c%3), we do the same thing as above - double the accumulator and add the next digit (d) to it, doubling the size of our set of accumulators each time.

Set(c%2,c%3) works because '0'%2 and '0'%3 both return 0 and '1'%2 and '1'%3 both return 1. Even though there's two of them, since we're using a Set, the duplicate is automatically removed. If, however, c is 'X' (88), then 'X'%2 is 0 and 'X'%3 is 1, giving us two different possible values, which is pretty nice.

Answer 23

Icon, 85 77 bytes

procedure f(s)
b:=n:=0
c:=!s&{c=2&{c:=.5;n+:=1};b:=2*b+c}&\z
return b*2^n
end

Try it online!

Uses 2 instead of X.

Inspired by xnor's Python solution.

Answer 24

Factor, 46 bytes

[ [ 48 - >bin ] map [ bin> ] product-map sum ]

Try it online!

Takes an array of charcodes (the character 2 is used for X) and returns the sum. Uses the built-in that generates the Cartesian product of multiple sequences. (I think it's already done in many answers.)

[
  [ 48 - >bin ] map     ! map '0', '1', '2' to "0", "1", "10" respectively
  [ bin> ] product-map  ! compute cartesian product of all strings,
                        ! and convert from binary to integer
  sum                   ! sum
]

Answer 25

J, 21 bytes

1#.2#.[:>@,@{#:@".&.>

Try it online!

Exact same algorithm as my Factor answer. Takes a string, with 2 in the place of X. If a plain integer vector is allowed, remove @". to get 18 bytes.

1#.2#.[:>@,@{#:@".&.>
                  &.>  NB. Apply to each character and enclose...
             #:@".     NB. Eval and convert to binary (0 -> 0, 1 -> 1, 2 -> 1 0)
           @{  NB. Take cartesian product of all boxed vectors
         @,    NB. Remove unnecessary outer array shape
      [:>      NB. Unbox the result vectors
   2#.         NB. Convert from binary to integer for each row
1#.            NB. Sum