Nous définissons un tableau binaire comme un tableau satisfaisant les propriétés suivantes:

• c'est non vide
• la première valeur est un 1
• la dernière valeur est un 1
• toutes les autres valeurs sont soit 0ou1

Par exemple, le tableau [ 1, 1, 0, 1 ]est un tableau de binaires valide .

La tâche

Étant donné un tableau non vide A d'entiers non négatifs et un entier positif N , votre travail consiste à trouver un tableau binaire B de longueur N qui permet de générer A en sommant un nombre illimité de copies de B , décalé d'un nombre illimité de postes.

Exemple

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

Pour cette entrée, le binarray B = [ 1, 1, 0, 1 ] serait une réponse valide car nous pouvons faire:

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

Règles

• L'entrée peut être prise dans n'importe quel format raisonnable.
• La sortie peut être un tableau natif (par exemple [1, 1, 0, 1]) ou une chaîne binaire avec ou sans séparateur (par exemple "1,1,0,1"ou "1101")
• Vous n'êtes tenu d'imprimer ou de retourner qu'un seul binarray valide . Vous pouvez également choisir d'imprimer ou de retourner tous lorsqu'il existe plusieurs solutions.
• Vous n'êtes pas tenu de prendre en charge les entrées qui ne conduisent à aucune solution.
• La somme peut inclure des zéros implicites qui ne se chevauchent pas avec une copie de B . Le deuxième zéro de la somme ci-dessus est un tel zéro implicite.
• Vous pouvez supposer que la taille maximale de A est 100 et la taille maximale de B est 30.
• Il s'agit de code-golf, donc la réponse la plus courte en octets l'emporte. Les failles standard sont interdites.

Cas de test

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 ]

PHP, 105 92 90 86 octets

Solution de Jörg fixe et golfée:

for($b=1+2**$argv[1];;)--$argc>1?$s+=$argv[$argc]*2**$i++:$s%($b-=2)||die(decbin($b));

prend à Npartir du premier argument de ligne de commande, les valeurs après cela; exécutez-le -rou testez-le en ligne .
imprime le nombre binaire (format 10001); imprime une solution non valide ou s'exécute s'il n'y a pas de solution valide.

première version (maintenant 97 octets) qui n'imprime rien pour une entrée invalide: testez-la en ligne

for($b=1+$m=2**$argv[1];$m/2<=$b;)--$argc>1?$s+=$argv[$argc]*2**$i++:$s%($b-=2)||die(decbin($b));

panne

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

PHP , 219 octets

<?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);

Essayez-le en ligne!

-4 octets en utilisant [$g,$z]=$_GETPHP 7.1 au lieu delist($g,$z)=$_GET

Python, 166 octets

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

Essayez-le en ligne!

Comment ça marche

Considérons A et B comme les chiffres des nombres k de base u et v . Par exemple (nous utiliserons k = 1000 pour 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

Comme beaucoup d'autres répondants l'ont remarqué, si B est une réponse valide, alors u est divisible par v . Dans ce cas,

u = 1 002 001 002 ⋅ v

Ce quotient, traduit de nouveau dans le tableau [1, 2, 1, 2], nous dit exactement combien de copies de B nous avons besoin de déplacer à chaque 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]

(Pourquoi? Parce que c'est exactement la durée de la multiplication en base k .)

Ce que les autres répondeurs n'ont pas remarqué, c'est que la condition ci-dessus n'est pas suffisante . Par exemple:

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

Mathématiquement parlant, nous pouvons toujours traduire ce quotient dans le tableau [1, 1, −1, 2], ce qui fonctionne bien si nous sommes autorisés à utiliser des copies négatives de 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]

mais bien sûr, le défi ne permet pas de copies négatives. Nous avons donc besoin d'un contrôle supplémentaire.

À cette fin, on choisit une base k = 10 ^e où k > 10 ⋅ somme (A), et de vérifier qu'aucune de la base k chiffres débordement dans la base suivante k chiffres lorsque l' on multiplie le quotient par dix. C'est, chaque e e dix chiffres de base, à partir de la fin, dans la représentation de dix base du temps de quotient dix, doit être 0. Cela garantit que le quotient reconvertit un tableau avec des éléments non négatifs.

PHP, 213 octets

De la même façon, un peu de golf

<?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);

Essayez-le en ligne!

PHP, 344 octets pour la première fois

Après ma première réponse, j'ai décidé de faire un essai plus long qui rendra toutes les solutions valides.

<?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)));

Version en ligne

Panne

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

Python, 205 octets

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

Renvoie une chaîne binaire sans séparateur. Comme le souligne @AndersKaseorg, il existe des entrées pour lesquelles la solution de @ fəˈnɛtɪk ne fonctionne pas car la division représente un coefficient négatif qui n'est pas autorisé. Pour contourner cela, j'utilise une très grande base et teste qu'il n'y a pas d'emprunt dans la division.

Pyth, 32 octets

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

Essayez-le en ligne

Comment ça marche

                           ^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

La stratégie est similaire à ma réponse Python , sauf que puisque Pyth a des fonctions intégrées pour la conversion de base, nous pouvons utiliser une base k = 2 ⋅ somme (A) plus efficace et vérifier directement que chaque chiffre du quotient est au plus somme (A ).

Pari / GP , 77 74 96 80 octets

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

Renvoie toutes les solutions.

Convertit d'abord le tableau aen polynôme b. Choisit ensuite parmi les diviseurs bles polynômes dtels que les coefficients de dsont tous 1et 0, et les coefficients de b / dsont tous non négatifs, et d(0) = 1, et deg(d) = n + 1. Enfin, les reconvertit en tableaux.

Essayez-le en ligne!