Trouvez le binarray!

24

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 ]
Arnauld
la source
Quelle est la plus grande valeur de Ncela qui devrait raisonnablement être prise en charge?
Neil
@Neil J'ai ajouté des limites de taille sur A et B.
Arnauld
1
@ fəˈnɛtɪk Peut-être, mais pour N=4, A = [ 1, 1, 2, 4, 1, 2, 2, 2, 1, 2, 2, 1, 2, 0, 1 ], vous obtenez 30459 qui est divisible par 11 et 13 mais un seul [ 1, 1, 0, 1 ]et [ 1, 0, 1, 1 ]est une réponse valide.
Neil
1
@ fəˈnɛtɪk Ces nombres ne sont pas écrits en base 2 donc les règles d'arithmétique ne s'appliquent pas. Par exemple, vous ne pouvez pas porter explicitement lors de l'ajout.
BallpointBen
2
Veuillez ajouter ces cas de test, qui semblent briser presque toutes les réponses publiées: N = 3, A = [1, 0, 2, 0, 2, 0, 1], sortie = [1, 0, 1]; N = 3, A = [1, 1, 1, 0, 0, 0, 1, 1, 1], sortie = [1, 1, 1].
Anders Kaseorg

Réponses:

8

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
Titus
la source
Nice ne pourriez-vous pas atteindre un nombre d'octets inférieur à 100?
Jörg Hülsermann
1
@ JörgHülsermann je pourrais.
Titus
Pensée lourde. Je sais avant cela que tu vas mieux. J'espère que vous pouvez contenir le nombre d'octets le plus bas
Jörg Hülsermann
1
Sur N = 3, A = [1, 0, 2, 0, 2, 0, 1], cela renvoie incorrectement111 où le seul résultat correct est [1, 0, 1].
Anders Kaseorg
8

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

Jörg Hülsermann
la source
Il semble qu'il génère à la fois une [1,0,1,0,1,0,1,0,1]réponse valide ( ) et non valide ( [1,0,0,0,1,0,1,1,1]) pour le dernier cas de test.
Arnauld
-8 octets: while($_GET[0])$s+=2**$i++*array_pop($_GET[0]);. -5 octets: range(1|.5*$m=2**$_GET[1],$m,2).
Titus
@Arnauld Oui, je ne devrais donner en sortie que le binarray le plus élevé pour que cette solution soit valide
Jörg Hülsermann
2
@ fəˈnɛtɪk Je suis d'accord avec vos calculs, mais le défi consiste à trouver un modèle qui peut être résumé exactement à A, pas un arrangement équivalent. Ici, nous aurions [ 1,0,1,1,1,0,2,2,2,2,2,1 ].
Arnauld
1
-1 octet avec for($g=$_GET[0];$g;).
Titus
3

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 ek > 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.

Anders Kaseorg
la source
1
J'adore votre astuce d'utiliser une grande puissance de 10 comme base pour faciliter la conversion de base.
Neil
2

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
Jörg Hülsermann
la source
Cela semble fonctionner pour N ≥ 2, mais échoue sur N = 1 cas, comme le premier cas de test dans le défi.
Anders Kaseorg
@AndersKaseorg Maintenant, il prend en charge les cas N = 1, il suffit de définir un =dans la première boucle pour la version courte Dans la version supérieure, il doit supprimer quatre octets
Jörg Hülsermann
1

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.

Neil
la source
D'accord, je pense que c'est un contre-exemple réel: f([1, 1, 1, 0, 0, 0, 1, 1, 1], 3)renvoie incorrectement 101.
Anders Kaseorg
@AndersKaseorg Hmm, inverser l'ordre de la boucle aide-t-il ou l'algorithme est-il toujours fondamentalement cassé?
Neil
Je pense que c'est fondamentalement cassé sans contrôles supplémentaires. La variante inverse échoue f([1, 0, 2, 0, 2, 0, 1], 3), et les variantes avant et arrière échouent f([1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0], 5).
Anders Kaseorg
Et même si vous vérifiez que ic'est étrange, les variantes avant et arrière échouent f([1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]*10, 5).
Anders Kaseorg
1
@AndersKaseorg Ah oui, quand gcd (k, n) = 1, a (x^kn-1)/(x^k-1)toujours (x^n-1)/(x-1)comme facteur, ce qui trompe la solution de @ fəˈnɛtɪk dans n'importe quelle base.
Neil
1

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 ).

Anders Kaseorg
la source
1

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!

alephalpha
la source