Find the binarray!
PHP, 219 bytes
<?for(list($g,$z)=$_GET,$d=~-$l=2**$z;$d>=$l/2;max(array_diff_assoc($r,$g)?:[0])?:$o[]=$b,$d-=2)for($r=[],$b=decbin($d),$k=0;$k<count($g);$k++)for($u=$g[$k]-$r[$k],$i=0;$i<$z;$i++)$u<1?:$r[$k+$i]+=$u*$b[$i];print_r($o);
Try it online!
-4 Bytes using [$g,$z]=$_GET
PHP 7.1 instead of list($g,$z)=$_GET
PHP, 105 92 90 86 bytes
Jörg´s solution fixed and golfed:
for($b=1+2**$argv[1];;)--$argc>1?$s+=$argv[$argc]*2**$i++:$s%($b-=2)||die(decbin($b));
takes N
from first command line argument, values after that;
run with -r
or test it online.
prints binary number (format 10001
);
prints invalid solution or runs dead if there is no valid solution.
first version (now 97 bytes) that prints nothing for invalid input: test it online
for($b=1+$m=2**$argv[1];$m/2<=$b;)--$argc>1?$s+=$argv[$argc]*2**$i++:$s%($b-=2)||die(decbin($b));
breakdown
for($b=1+$m=2**$argv[1];$m/2<=$b;) # second loop: loop $b from 2^N-1 by -2 to 2^(N-1)
--$argc>1 # first loop: decrease $argc ...
?$s+=$argv[$argc]*2**$i++ # while $argc>1: binary sum from last to 2nd argument
:$s%($b-=2)||die(decbin($b)); # later: if $b divides $s, print in binary and exit
Python, 166 bytes
def f(a,n):
for i in range(1<<n-1,1<<n):
b=bin(i)[2:];u,v=(int(('0{:0>%d}'%sum(a)*len(s)).format(*s))for s in[a,b])
if u%v<1>int(str(u//v*10)[::~sum(a)]):yield b
Try it online!
How it works
Consider A and B as the digits of base k numbers u and v. For example (we’ll use k = 1000 for illustration):
A = [1, 2, 1, 3, 2, 1, 2]
B = [1, 0, 0, 1]
u = 1 002 001 003 002 001 002
v = 1 000 000 001
As many of the other answerers noticed, if B is a valid answer, then u is divisible by v. In this case,
u = 1 002 001 002 ⋅ v
This quotient, translated back to the array [1, 2, 1, 2], tells us exactly how many copies of B we need shifted to each position.
[1, 0, 0, 1]
+ [1, 0, 0, 1]
+ [1, 0, 0, 1]
+ [1, 0, 0, 1]
+ [1, 0, 0, 1]
+ [1, 0, 0, 1]
-----------------------
[1, 2, 1, 3, 2, 1, 2]
(Why? Because that is exactly how long multiplication works in base k.)
What the other answerers failed to notice is that the above condition is not sufficient. For example:
A = [1, 2, 1, 3, 2, 1, 2]
B = [1, 1, 1, 1]
u = 1 002 001 003 002 001 002
v = 1 001 001 001
u = 1 000 999 002 ⋅ v
Mathematically speaking, we can still translate that quotient back to the array [1, 1, −1, 2], which works fine if we’re allowed to use negative copies of B:
[1, 1, 1, 1]
+ [1, 1, 1, 1]
− [1, 1, 1, 1]
+ [1, 1, 1, 1]
+ [1, 1, 1, 1]
-----------------------
[1, 2, 1, 3, 2, 1, 2]
but of course the challenge does not permit negative copies. So we need an additional check.
Toward that end, we select a base k = 10e where k > 10 ⋅ sum(A), and check that none of the base k digits overflow into the next base k digit when we multiply the quotient by ten. That is, every eth base ten digit, starting at the end, in the base ten representation of the quotient times ten, must be 0. This guarantees that the quotient translates back to an array with nonnegative elements.