Finde das Binarray!

24

Wir definieren ein Binarray als ein Array, das die folgenden Eigenschaften erfüllt:

  • es ist nicht leer
  • Der erste Wert ist a 1
  • Der letzte Wert ist a 1
  • Alle anderen Werte sind entweder 0oder1

Zum Beispiel das Array [ 1, 1, 0, 1 ] ein gültiges Binarray .

Die Aufgabe

Bei einem nicht leeren Array A mit nicht negativen Ganzzahlen und einer positiven Ganzzahl N müssen Sie ein Binarray B mit der Länge N finden , mit dem Sie A durch Summieren einer uneingeschränkten Anzahl von Kopien von B generieren können , die um eine uneingeschränkte Anzahl von verschoben sind Positionen.

Beispiel

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

Für diese Eingabe wäre das Binarray B = [ 1, 1, 0, 1 ] eine gültige Antwort, da wir Folgendes tun können:

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

Regeln

  • Die Eingabe kann in jedem vernünftigen Format erfolgen.
  • Die Ausgabe kann entweder ein natives Array (z. B. [1, 1, 0, 1]) oder eine Binärzeichenfolge mit oder ohne Trennzeichen (z. B. "1,1,0,1"oder "1101") sein.
  • Sie müssen nur ein gültiges Binarray ausdrucken oder zurücksenden . Alternativ können Sie alle drucken oder zurückgeben , wenn mehrere Lösungen vorhanden sind.
  • Sie müssen keine Eingaben unterstützen, die zu keiner Lösung führen.
  • Die Summe kann implizite Nullen enthalten, die sich mit keiner Kopie von B überschneiden . Die zweite Null in der obigen Summe ist eine solche implizite Null.
  • Sie können davon ausgehen, dass die maximale Größe von A 100 und die maximale Größe von B 30 beträgt.
  • Das ist Code-Golf, also gewinnt die kürzeste Antwort in Bytes. Standardlücken sind verboten.

Testfälle

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
quelle
Was ist der größte Wert, der Nvernünftigerweise unterstützt werden sollte?
Neil
@Neil Ich habe Größenbeschränkungen für A und B hinzugefügt.
Arnauld
1
@ fəˈnəˈtɛk Vielleicht, aber dafür N=4, A = [ 1, 1, 2, 4, 1, 2, 2, 2, 1, 2, 2, 1, 2, 0, 1 ]bekommst du 30459, das sowohl durch 11 als auch durch 13 teilbar ist und doch nur eine von [ 1, 1, 0, 1 ]und [ 1, 0, 1, 1 ]eine gültige Antwort ist.
Neil
1
@ fəˈnəˈtɪk Diese Zahlen sind nicht in Basis 2 geschrieben, daher gelten keine arithmetischen Regeln. Zum Beispiel können Sie nicht explizit beim Hinzufügen tragen.
BallpointBen
2
Bitte fügen Sie diese Testfälle hinzu, die fast alle geposteten Antworten zu brechen scheinen: N = 3, A = [1, 0, 2, 0, 0, 1], output = [1, 0, 1]; N = 3, A = [1, 1, 1, 0, 0, 1, 1, 1], Ausgabe = [1, 1, 1].
Anders Kaseorg

Antworten:

8

PHP, 105 92 90 86 Bytes

Jörgs Lösung fixiert und golfen:

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

Nimmt Nvom ersten Kommandozeilenargument Werte danach; Laufen Sie mit -roder testen Sie es online .
druckt Binärzahl (Format 10001); Gibt eine ungültige Lösung aus oder wird beendet, wenn keine gültige Lösung vorhanden ist.

Erste Version (jetzt 97 Byte), die nichts für ungültige Eingaben ausgibt: Testen Sie sie online

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

Nervenzusammenbruch

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
quelle
Nizza konnten Sie nicht eine Byteanzahl unter 100 erreichen?
Jörg Hülsermann 30.
1
@ JörgHülsermann Ich könnte.
Titus
Schweres Denken. Ich weiß vorher, dass es dir besser geht. Ich hoffe, Sie können die niedrigste Byteanzahl halten
Jörg Hülsermann
1
Bei N = 3, A = [1, 0, 2, 0, 2, 0, 1] wird fälschlicherweise zurückgegeben,111 wenn das einzig richtige Ergebnis [1, 0, 1] ist.
Anders Kaseorg
8

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

Probieren Sie es online!

-4 Bytes mit [$g,$z]=$_GETPHP 7.1 stattlist($g,$z)=$_GET

Jörg Hülsermann
quelle
Es scheint, als würde sowohl eine gültige ( [1,0,1,0,1,0,1,0,1]) als auch eine ungültige Antwort ( [1,0,0,0,1,0,1,1,1]) für den letzten Testfall ausgegeben.
Arnauld
-8 Bytes while($_GET[0])$s+=2**$i++*array_pop($_GET[0]);. -5 Bytes range(1|.5*$m=2**$_GET[1],$m,2).
Titus
@Arnauld Ja ich sollte als Ausgabe nur das höchste Binarray angeben um diese Lösung gültig zu machen
Jörg
2
@ fəˈnəˈtɪk Ich stimme Ihrer Mathematik zu, aber die Herausforderung besteht darin, ein Muster zu finden, das genau zu A summiert werden kann, nicht zu einer äquivalenten Anordnung. Hier würden wir bekommen [ 1,0,1,1,1,0,2,2,2,2,2,1 ].
Arnauld
1
-1 Byte mit for($g=$_GET[0];$g;).
Titus
3

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

Probieren Sie es online!

Wie es funktioniert

Betrachten Sie A und B als die Ziffern der Basis- k- Zahlen u und v . Zum Beispiel ( zur Veranschaulichung verwenden wir k = 1000):

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

Wie viele der anderen Antwortenden bemerkt haben, ist u durch v teilbar , wenn B eine gültige Antwort ist . In diesem Fall,

u = 1 002 001 002 ⋅ v

Dieser Quotient, der in das Array [1, 2, 1, 2] zurückübersetzt wird, gibt genau an, wie viele Kopien von B an jede Position verschoben werden müssen.

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

(Warum? Denn genau so lange funktioniert die Multiplikation in der Basis k .)

Was die anderen Antwortenden nicht bemerkten, ist, dass die obige Bedingung nicht ausreicht . Beispielsweise:

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

Mathematisch gesehen können wir diesen Quotienten immer noch zurück in das Array [1, 1, −1, 2] übersetzen, was gut funktioniert, wenn wir negative Kopien von B verwenden dürfen:

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

Aber natürlich erlaubt die Herausforderung keine negativen Kopien. Wir brauchen also einen zusätzlichen Scheck.

Mit diesem Ziel, wählen wir eine Basis k = 10 e , wo k > 10 ⋅ Summe (A), und sicherstellen , dass keine von der Basis k Ziffern Überlauf in die nächsten Basis k digit wenn multiplizieren wir die Quotienten von zehn. Das heißt, jeder e ten Basiszehnstellige, am Ende ausgehend, in der Basis - Zehn - Darstellung des Quotienten mal zehn muss 0. Dies garantiert sein , dass der Quotient mit nicht - negativen Elementen auf ein Array zurück übersetzt.

Anders Kaseorg
quelle
1
Ich mag Ihren Trick, eine große Potenz von 10 als Basis zu verwenden, um die Konvertierung der Basis zu vereinfachen.
Neil
2

PHP, 213 Bytes

Genauso ein bisschen golfen

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

Probieren Sie es online!

PHP, 344 Bytes zuerst funktioniert

Nach meiner ersten Antwort habe ich beschlossen, einen längeren Versuch zu machen, der alle gültigen Lösungen zurückgibt.

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

Nervenzusammenbruch

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
quelle
Dies scheint für N ≥ 2 zu funktionieren, schlägt jedoch in N = 1 Fällen fehl, z. B. im ersten Testfall der Challenge.
Anders Kaseorg
@AndersKaseorg Jetzt werden die N = 1 Fälle unterstützt, die nur =in der ersten Schleife für die kürzere Version gesetzt werden müssen. In der größeren Version müssen vier Bytes gelöscht werden
Jörg Hülsermann,
1

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

Gibt eine Binärzeichenfolge ohne Trennzeichen zurück. Wie @AndersKaseorg ausführt, gibt es Eingaben, für die die @ fəˈnəˈtɪk-Lösung nicht funktioniert, weil die Division einen negativen Koeffizienten darstellt, der nicht zulässig ist. Um das zu umgehen, benutze ich eine sehr große Basis und teste, dass es in der Abteilung kein Darlehen gibt.

Neil
quelle
Okay, ich denke das ist ein echtes Gegenbeispiel: f([1, 1, 1, 0, 0, 0, 1, 1, 1], 3)Gibt fälschlicherweise zurück 101.
Anders Kaseorg
@AndersKaseorg Hmm, hilft es, die Reihenfolge der Schleife umzukehren, oder ist der Algorithmus immer noch grundlegend defekt?
Neil
Ich denke, es ist im Grunde ohne zusätzliche Kontrollen gebrochen. Die umgekehrte Variante schlägt fehl f([1, 0, 2, 0, 2, 0, 1], 3), und sowohl die Vorwärts- als auch die Rückwärtsvariante schlagen fehl f([1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0], 5).
Anders Kaseorg
Und selbst wenn Sie dies ials ungerade markieren, schlagen sowohl die Vorwärts- als auch die Rückwärtsvariante fehl f([1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]*10, 5).
Anders Kaseorg
1
@AndersKaseorg Ah ja, wenn gcd (k, n) = 1 ist, hat das (x^kn-1)/(x^k-1)immer (x^n-1)/(x-1)einen Faktor, der die Lösung von @ fɛnɪtɛk in einer beliebigen Basis zum Narren hält.
Neil
1

Pyth, 32 Bytes

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

Probieren Sie es online aus

Wie es funktioniert

                           ^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

Die Strategie ist meiner Python-Antwort ähnlich , außer dass wir, da Pyth über integrierte Funktionen für die Basiskonvertierung verfügt, eine effizientere Basis k = 2 ⋅ sum (A) verwenden und direkt überprüfen können, ob jede Ziffer des Quotienten höchstens sum (A) ist ).

Anders Kaseorg
quelle
1

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]

Gibt alle Lösungen zurück.

Zuerst konvertiert das Array ain ein Polynom b. Dann wählt man aus den Teilern bdie Polynome dso, dass die Koeffizienten von dalle 1und 0und die Koeffizienten von b / dalle nichtnegativ sind und d(0) = 1und deg(d) = n + 1. Konvertiert sie schließlich wieder in Arrays.

Probieren Sie es online!

Alephalpha
quelle