24
\$\begingroup\$

We define a binarray as an array satisfying the following properties:

  • it's non-empty
  • the first value is a 1
  • the last value is a 1
  • all other values are either 0 or 1

For instance, the array [ 1, 1, 0, 1 ] is a valid binarray.

The task

Given a non-empty array A of non-negative integers and a positive integer N, your job is to find a binarray B of length N which allows to generate A by summing an unrestricted number of copies of B, shifted by an unrestricted number of positions.

Example

A = [ 1, 1, 2, 4, 1, 2, 2, 1, 0, 1, 0, 1, 1, 0, 1 ]
N = 4

For this input, the binarray B = [ 1, 1, 0, 1 ] would be a valid answer because we can do:

  [ 1, 1, 0, 1 ]
+       [ 1, 1, 0, 1 ]
+       [ 1, 1, 0, 1 ]
+          [ 1, 1, 0, 1 ]
+                   [ 1, 1, 0, 1 ]
+                                  [ 1, 1, 0, 1 ]
  -----------------------------------------------
= [ 1, 1, 2, 4, 1, 2, 2, 1, 0, 1, 0, 1, 1, 0, 1 ]

Rules

  • Input can be taken in any reasonable format.
  • Output can be either a native array (e.g. [1, 1, 0, 1]) or a binary string with or without a separator (e.g. "1,1,0,1" or "1101")
  • You're only required to print or return one valid binarray. Alternatively, you may choose to print or return all of them when several solutions exist.
  • You are not required to support inputs that do not lead to any solution.
  • The sum may include implicit zeros which do not overlap with any copy of B. The second zero in the above sum is such an implicit zero.
  • Your can assume that the maximum size of A is 100 and the maximum size of B is 30.
  • This is code-golf, so the shortest answer in bytes wins. Standard loopholes are forbidden.

Test cases

Input : N = 1 / A = [ 1, 2, 3, 4, 5 ]
Output: [ 1 ]

Input : N = 2 / A = [ 1, 2, 100, 99 ]
Output: [ 1, 1 ]

Input : N = 3 / A = [ 1, 1, 1 ]
Output: [ 1, 1, 1 ]

Input : N = 3 / A = [ 1, 1, 3, 2, 2 ]
Output: [ 1, 1, 1 ]

Input : N = 3 / A = [ 1, 0, 2, 1, 1, 1, 0, 0, 1, 0, 1 ]
Output: [ 1, 0, 1 ]

Input : N = 4 / A = [ 1, 2, 2, 2, 1 ]
Output: [ 1, 1, 1, 1 ]

Input : N = 4 / A = [ 1, 1, 2, 4, 1, 2, 2, 1, 0, 1, 0, 1, 1, 0, 1 ]
Output: [ 1, 1, 0, 1 ]

Input : N = 4 / A = [ 1, 1, 0, 2, 1, 0, 1 ]
Output: [ 1, 0, 0, 1 ] or [ 1, 1, 0, 1 ]

Input : N = 5 / A = [ 1, 3, 6, 9, 8, 6, 3, 4 ]
Output: [ 1, 1, 1, 0, 1 ]

Input : N = 8 / A = [ 2, 1, 0, 2, 3, 3, 1, 2, 1 ]
Output: [ 1, 0, 0, 1, 1, 1, 0, 1 ]

Input : N = 10 / A = [ 1, 2, 1, 2, 2, 1, 3, 3, 3, 2, 3, 0, 2, 1, 1, 0, 1 ]
Output: [ 1, 1, 0, 1, 0, 1, 1, 1, 0, 1 ]

Input : N = 13 / A = [ 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1 ]
Output: [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ]

Input : N = 5 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 1, 1, 1, 1 ]

Input : N = 6 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 0, 0, 0, 0, 1 ]

Input : N = 7 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 1, 0, 0, 0, 1, 1 ]

Input : N = 9 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 0, 1, 0, 1, 0, 1, 0, 1 ]
\$\endgroup\$
  • \$\begingroup\$ What's the largest value of N that should reasonably be supported? \$\endgroup\$ – Neil Mar 30 '17 at 10:50
  • \$\begingroup\$ @Neil I've added size limits on both A and B. \$\endgroup\$ – Arnauld Mar 30 '17 at 11:01
  • 1
    \$\begingroup\$ @fəˈnɛtɪk Maybe, but for N=4, A = [ 1, 1, 2, 4, 1, 2, 2, 2, 1, 2, 2, 1, 2, 0, 1 ], you get 30459 which is divisible by both 11 and 13 yet only one of [ 1, 1, 0, 1 ] and [ 1, 0, 1, 1 ] is a valid answer. \$\endgroup\$ – Neil Mar 30 '17 at 15:28
  • 1
    \$\begingroup\$ @fəˈnɛtɪk These numbers aren't written in base 2 so rules of arithmetic don't apply. For instance, you explicitly cannot carry when adding. \$\endgroup\$ – BallpointBen Mar 30 '17 at 22:46
  • 2
    \$\begingroup\$ Please add these test cases, which seem to break nearly all the posted answers: N = 3, A = [1, 0, 2, 0, 2, 0, 1], output = [1, 0, 1]; N = 3, A = [1, 1, 1, 0, 0, 0, 1, 1, 1], output = [1, 1, 1]. \$\endgroup\$ – Anders Kaseorg Jun 2 '17 at 19:38
8
\$\begingroup\$

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 -ror 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
\$\endgroup\$
  • \$\begingroup\$ Nice could you not reach a byte count under 100? \$\endgroup\$ – Jörg Hülsermann Mar 30 '17 at 16:37
  • 1
    \$\begingroup\$ @JörgHülsermann I could. \$\endgroup\$ – Titus Mar 31 '17 at 0:03
  • \$\begingroup\$ Heavy Thinking. I know before this that you are better. I hope you can hold the lowest byte count \$\endgroup\$ – Jörg Hülsermann Mar 31 '17 at 0:17
  • 1
    \$\begingroup\$ On N = 3, A = [1, 0, 2, 0, 2, 0, 1], this incorrectly returns 111 where the only correct result is [1, 0, 1]. \$\endgroup\$ – Anders Kaseorg Jun 2 '17 at 18:30
8
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ It seems like it outputs both a valid ([1,0,1,0,1,0,1,0,1]) and an invalid answer ([1,0,0,0,1,0,1,1,1]) for the last test case. \$\endgroup\$ – Arnauld Mar 30 '17 at 12:30
  • \$\begingroup\$ -8 bytes: while($_GET[0])$s+=2**$i++*array_pop($_GET[0]);. -5 bytes: range(1|.5*$m=2**$_GET[1],$m,2). \$\endgroup\$ – Titus Mar 30 '17 at 13:22
  • \$\begingroup\$ @Arnauld Yes I should give as Output only the highest binarray too make this solution valid \$\endgroup\$ – Jörg Hülsermann Mar 30 '17 at 13:30
  • 2
    \$\begingroup\$ @fəˈnɛtɪk I do agree with your maths, but the challenge is about finding a pattern that can be summed exactly to A, not an equivalent arrangement. Here, we'd get [ 1,0,1,1,1,0,2,2,2,2,2,1 ]. \$\endgroup\$ – Arnauld Mar 30 '17 at 13:45
  • 1
    \$\begingroup\$ -1 byte with for($g=$_GET[0];$g;). \$\endgroup\$ – Titus Mar 30 '17 at 15:29
3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ I love your trick of using a large power of 10 as the base to make the base conversion easier. \$\endgroup\$ – Neil Jun 4 '17 at 20:38
2
\$\begingroup\$

PHP, 213 Bytes

Same way a little bit golfed

<?for($b=2**~-$l=$_GET[1];$b<2**$l;array_filter($t[$b++])?:$d[]=$o)for($g=count($t[$b]=$_GET[$i=0]);min($t[$b])>-1&$i<=$g-$l;$i++)for($e=$t[$b][$i],$k=0,$o=decbin($b);$k<$l;)$t[$b][$k+$i]-=$o[$k++]*$e;print_r($d);

Try it online!

PHP, 344 Bytes first working

After my first answer I have decide to make a longer try that give back all valid solutions.

<?foreach(range(2**($l=$_GET[1])-1,2**($l-1))as$b){$t[$b]=($g=$_GET[0]);for($i=0;$t[$b]&&$i<=count($g)-$l;$i++){$e=reset($y=array_slice($t[$b],$i,$l));foreach(str_split(decbin($b))as$k=>$v)$t[$b][$k+$i]=$y[$k]-$e*$v;if(min($t[$b])<0)unset($t[$b]);}}foreach($t as$k=>$v)if(max($v)>0)unset($t[$k]);echo join(",",array_map(decbin,array_keys($t)));

Online Version

Breakdown

foreach(
    range(2**($l=$_GET[1])-1
    ,2**($l-1)
    ) # make decimal range of a binarray with given length
    as$b){
$t[$b]=($g=$_GET[0]); # make a copy for each possible solution pattern
    for($i=0;$t[$b]&&$i<=count($g)-$l;$i++){ # Loop till solution is valid or reach last digit
        $e=reset($y=array_slice($t[$b],$i,$l)); # take first value of a sequence with the length
        foreach(str_split(decbin($b))as$k=>$v)
            $t[$b][$k+$i]=$y[$k]-$e*$v; # replace values in copy
        if(min($t[$b])<0)unset($t[$b]); # kill solution if a minimum <0 exists
    }
}
foreach($t as$k=>$v)if(max($v)>0)unset($t[$k]); # drop all solutions where the sum is not zero 


echo join(",",array_map(decbin,array_keys($t))); #Output all solutions
\$\endgroup\$
  • \$\begingroup\$ This seems to work for N ≥ 2, but fails on N = 1 cases, such as the first test case in the challenge. \$\endgroup\$ – Anders Kaseorg Jun 4 '17 at 2:35
  • \$\begingroup\$ @AndersKaseorg Now it supports the N = 1 Cases it needs only to set a = in the first loop for the shorter version In the greater version it needs to delete four Bytes \$\endgroup\$ – Jörg Hülsermann Jun 4 '17 at 11:00
1
\$\begingroup\$

Python, 205 bytes

def f(a,l):
 b=lambda s:b(s[:-1])*sum(a)*8+int(s[-1])if s else 0
 c=lambda n:n and(n/sum(a)/4%2 or c(n/sum(a)/8))
 for i in range(2**~-l,2**l):
  j=bin(i)[2:]
  if b(a)%b(j)<1 and not c(b(a)/b(j)):return j

Returns a binary string without separator. As @AndersKaseorg points out, there are inputs for which @fəˈnɛtɪk's solution doesn't work because the division represents a negative coefficient which is disallowed. To work around this, I use a very large base and test that there is no borrow in the division.

\$\endgroup\$
  • \$\begingroup\$ Okay, I think this is an actual counterexample: f([1, 1, 1, 0, 0, 0, 1, 1, 1], 3) incorrectly returns 101. \$\endgroup\$ – Anders Kaseorg Jun 2 '17 at 19:26
  • \$\begingroup\$ @AndersKaseorg Hmm, does reversing the order of the loop help, or is the algorithm still fundamentally broken? \$\endgroup\$ – Neil Jun 2 '17 at 19:44
  • \$\begingroup\$ I think it’s fundamentally broken without additional checks. The reverse variant fails on f([1, 0, 2, 0, 2, 0, 1], 3), and both the forward and reverse variants fail on f([1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0], 5). \$\endgroup\$ – Anders Kaseorg Jun 2 '17 at 20:36
  • \$\begingroup\$ And even if you check that i is odd, both the forward and reverse variants fail on f([1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]*10, 5). \$\endgroup\$ – Anders Kaseorg Jun 2 '17 at 20:44
  • 1
    \$\begingroup\$ @AndersKaseorg Ah yes, when gcd(k,n)=1, (x^kn-1)/(x^k-1) always has (x^n-1)/(x-1) as a factor, which fools @fəˈnɛtɪk's solution in any base. \$\endgroup\$ – Neil Jun 3 '17 at 15:44
1
\$\begingroup\$

Pyth, 32 bytes

f!|%FKiRJysQ,QT>#sQj/FKJ+L1^U2tE

Try it online

How it works

                           ^U2tE   Cartesian power [0, 1]^(N - 1)
                        +L1        prepend 1 to every list
f                                  filter for lists T such that:
          sQ                         sum(A)
         y                           double
        J                            assign to J
      iR    ,QT                      convert [A, T] from base J
     K                               assign to K
   %F                                fold modulo
  |                                  logical OR with
                    /FK                fold integer division over K
                   j   J               convert to base J
               >#sQ                    filter for digits greater than sum(A)
 !                                   logical NOT

The strategy is similar to my Python answer, except that since Pyth has builtins for base conversion, we can use a more efficient base k = 2 ⋅ sum(A), and check directly that every digit of the quotient is at most sum(A).

\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 77 74 96 80 bytes

n->a->[v|d<-divisors(b=Pol(a)),(v=Vec(d))%2==v&&vecmin(Vec(b/d))>=0&&d%x&&#d==n]

Returns all solutions.

First converts the array a to a polynomial b. Then chooses from the divisors b the polynomials d such that the coefficients of d are all 1 and 0, and the coefficients of b / d are all nonnegative, and d(0) = 1, and deg(d) = n + 1. Finally, converts them back to arrays.

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.