Possible binaries sum

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"]

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 , so fewest bytes will win!

• Can we substitute another character for X? Dec 15 '20 at 12:37
• @Shaggy - yeah sure! Dec 15 '20 at 12:37
• Can I substitute .5 for X?! Dec 17 '20 at 20:49

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!

• Hm, there is an error when the bitmask doesn't contain X, maybe because k+=c>"1" isn't incrementing k and n<<k-1 causes error.. Dec 15 '20 at 13:01
• @vrintle Good catch, I missed that inputs like that were possible, let me try to fix it.
– xnor
Dec 15 '20 at 13:03

n!x=n
(0!)

Try it online!

Explanation

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

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!x=n
(0!)

We can unroll the applications in that:

n!('X':x)=(2*n)!x+(2*n+1)!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!x=n
(0!)

From here we combine the pattern matches to save bytes.

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'

J, 47 bytes

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

Try it online!

Not super happy with this one...

Bash, 38

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

Try it online!

R, 1561427861565251 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!

• 142 bytes Dec 17 '20 at 17:11
• 61 bytes, I think... Dec 17 '20 at 19:56
• @DominicvanEssen Once we consider the input as a vector, one could as well set the 2's to .5's and remove the first command x[x>1]=.5;, no? Dec 17 '20 at 20:26
• That might be stretching the input format a bit, but you could ask vrintle for clarification, I suppose. You can also swap %in% with ==, and I think you can replace a sum(A*B) with A%*%B, which would be 56 bytes. Dec 17 '20 at 20:33
• 52 bytes -- I stumbled upon 55 bytes and just kept going; if the input can be taken in reverse (little-endian), then it can be 49 bytes. Dec 17 '20 at 22:05

05AB1E, 14 12 bytes

Y1ÝI2¢ãδ.;CO

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)

sum.foldl(%)

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.

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

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.

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

• 78 bytes letting Distribute do the heavy lifting.
– att
Dec 15 '20 at 19:12
• Another -11 distributing over Plus instead
– att
Dec 16 '20 at 0:34
• Further -18 taking a list of characters and using a digit instead of X
– att
Dec 17 '20 at 22:04

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]]
Ṭ     - 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
• I have already allowed array of chars, so allowing array of ints is assumed, so 9 bytes ;-) Dec 16 '20 at 14:27
• @vrintle many answers are spending bytes on string processing, I think it's worth updating the specification if allowed. Dec 16 '20 at 20:04
• Oops! I'm sorry. I thought that it's array of char int like ['0','2','1'...] Dec 17 '20 at 4:04

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.
• Suggest s+=s+=*m==49;c*=s/2;} instead of s+=*m==49,s*=2;c=c*s/2;} Dec 19 '20 at 7:43

K (ngn/k), 27 bytes

{_2/(d-1.5*t),&+/t:2=d:.'x}

Try it online!

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

• d:.'x convert input string to a list of integer digits, storing in d
• t:2=d store bitmask of where 2's are present in t
• &+/t generate n 0's, where n is the number of 2's in the input
• (d-1.5*t) convert 2's to 0.5's
• (...),... concat the 0's at the end
• 2/ convert from base-2 (equivalent to {y+2*x}/)
• _ take the floor

Stax, 20 bytes

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

Run and debug it

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

Perl 5-p, 35 bytes

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

Try it online!

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!

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.

Retina 0.8.2, 41 29 bytes

+%1X
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:

+%1X
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.

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

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.

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.

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!

Inspired by xnor's Python solution.

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
]

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