Znajdź binarray!

24

Definiujemy binarray jako tablicę spełniającą następujące właściwości:

  • nie jest pusty
  • pierwsza wartość to 1
  • ostatnia wartość to 1
  • Wszystkie inne wartości są albo 0albo1

Na przykład tablica [ 1, 1, 0, 1 ]jest prawidłową tablicą binarną .

Zadanie

Biorąc pod uwagę niepustą tablicę A nieujemnych liczb całkowitych i dodatnią liczbę całkowitą N , Twoim zadaniem jest znalezienie tablicy b B o długości N, która pozwala wygenerować A poprzez zsumowanie nieograniczonej liczby kopii B , przesuniętej o nieograniczoną liczbę pozycje.

Przykład

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

Dla tych danych wejściowych binarna tablica B = [ 1, 1, 0, 1 ] byłaby prawidłową odpowiedzią, ponieważ możemy wykonać:

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

Zasady

  • Dane wejściowe można przyjmować w dowolnym rozsądnym formacie.
  • Wyjściem może być natywna tablica (np. [1, 1, 0, 1]) Lub ciąg binarny z separatorem lub bez (np. "1,1,0,1"Lub "1101")
  • Musisz wydrukować lub zwrócić tylko jeden ważny binarray . Alternatywnie możesz wydrukować lub zwrócić je wszystkie, jeśli istnieje kilka rozwiązań.
  • Nie musisz obsługiwać danych wejściowych, które nie prowadzą do żadnego rozwiązania.
  • Suma może zawierać ukryte zer, które nie pokrywają się z jakiejkolwiek kopii B . Drugie zero w powyższej sumie jest takim domniemanym zerem.
  • Możesz założyć, że maksymalny rozmiar A wynosi 100, a maksymalny rozmiar B to 30.
  • To jest golf golfowy, więc wygrywa najkrótsza odpowiedź w bajtach. Standardowe luki są zabronione.

Przypadki testowe

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
źródło
Jaką największą wartość Nnależy w uzasadniony sposób wspierać?
Neil
@ Nee Dodałem limity rozmiaru zarówno dla A, jak i B.
Arnauld
1
@ fənɛtɪk Być może, ale N=4, A = [ 1, 1, 2, 4, 1, 2, 2, 2, 1, 2, 2, 1, 2, 0, 1 ], masz 30459, która jest podzielna zarówno przez 11 i 13 jeszcze tylko jednego [ 1, 1, 0, 1 ]i [ 1, 0, 1, 1 ]jest prawidłowym rozwiązaniem.
Neil
1
@ fəˈnɛtɪk Liczby te nie są zapisane w bazie 2, więc zasady arytmetyki nie mają zastosowania. Na przykład, nie możesz wyraźnie nosić przy dodawaniu.
BallpointBen
2
Dodaj te przypadki testowe, które wydają się łamać prawie wszystkie opublikowane odpowiedzi: 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], wynik = [1, 1, 1].
Anders Kaseorg,

Odpowiedzi:

8

PHP, 105 92 90 86 bajtów

Rozwiązanie Jörga naprawione i golfa:

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

pobiera Nz pierwszego argumentu wiersza poleceń, potem wartości; uruchom go -rlub przetestuj online .
wypisuje liczbę binarną (format 10001); drukuje nieprawidłowe rozwiązanie lub przestaje działać, jeśli nie ma prawidłowego rozwiązania.

pierwsza wersja (obecnie 97 bajtów), która nie drukuje niczego w przypadku nieprawidłowych danych wejściowych: przetestuj online

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

awaria

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
Tytus
źródło
Fajnie, czy nie możesz osiągnąć liczby bajtów poniżej 100?
Jörg Hülsermann
1
@ JörgHülsermann Mogłem.
Tytus
Ciężkie myślenie. Wiem wcześniej, że jesteś lepszy. Mam nadzieję, że potrafisz utrzymać najniższą liczbę bajtów
Jörg Hülsermann
1
Przy N = 3, A = [1, 0, 2, 0, 2, 0, 1], to niepoprawnie zwraca,111 gdy jedynym poprawnym wynikiem jest [1, 0, 1].
Anders Kaseorg,
8

PHP , 219 bajtów

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

Wypróbuj online!

-4 Bajty za pomocą [$g,$z]=$_GETPHP 7.1 zamiastlist($g,$z)=$_GET

Jörg Hülsermann
źródło
Wygląda na to, że wyświetla zarówno poprawną ( [1,0,1,0,1,0,1,0,1]), jak i niepoprawną odpowiedź ( [1,0,0,0,1,0,1,1,1]) dla ostatniego przypadku testowego.
Arnauld
-8 bajtów: while($_GET[0])$s+=2**$i++*array_pop($_GET[0]);. -5 bajtów: range(1|.5*$m=2**$_GET[1],$m,2).
Tytus
@Arnauld Tak Powinienem podać jako Output tylko najwyższy binarray, aby to rozwiązanie było ważne
Jörg Hülsermann
2
@ fəˈnɛtɪk Zgadzam się z twoją matematyką, ale wyzwanie polega na znalezieniu wzoru, który można zsumować dokładnie do A, a nie równoważnego układu. Dostalibyśmy [ 1,0,1,1,1,0,2,2,2,2,2,1 ].
Arnauld
1
-1 bajt z for($g=$_GET[0];$g;).
Tytus
3

Python, 166 bajtów

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

Wypróbuj online!

Jak to działa

Rozważ A i B jako cyfry podstawowych liczb k u i v . Na przykład (użyjemy k = 1000 dla ilustracji):

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

Jak wielu innych Główni odpowiadający zauważył, jeśli B jest prawidłowa odpowiedź, następnie u jest podzielna przez v . W tym przypadku,

u = 1 002 001 002 ⋅ v

Ten iloraz, przetłumaczony z powrotem na tablicę [1, 2, 1, 2], mówi nam dokładnie, ile kopii B potrzebujemy przesuniętych na każdą pozycję.

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

(Dlaczego? Ponieważ dokładnie tak długo działa mnożenie w bazie k .)

To, czego inni autorzy nie zauważyli, to to powyższy warunek nie jest wystarczający . Na przykład:

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

Matematycznie nadal możemy przetłumaczyć ten iloraz z powrotem na tablicę [1, 1, −1, 2], co działa dobrze, jeśli wolno nam używać ujemnych kopii 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]

ale oczywiście wyzwanie nie pozwala na kopiowanie negatywne. Potrzebujemy więc dodatkowej kontroli.

W tym celu wybieramy podstawę k = 10 e, gdzie k > 10 ⋅ suma (A), i sprawdzamy, czy żadna z podstawowych liczb k nie przepełnia się do następnej podstawowej liczby k, gdy mnożymy iloraz przez dziesięć. Oznacza to, że każdy e th cyfra dziesięć podstawa, zaczynając od końca, w reprezentacji baza dziesięć czasów ilorazowe dziesięciu, musi być 0. gwarantuje, że iloraz przekłada powrotem do tablicy z elementami nieujemnych.

Anders Kaseorg
źródło
1
Podoba mi się twoja sztuczka polegająca na użyciu dużej mocy 10 jako podstawy, aby ułatwić konwersję bazy.
Neil
2

PHP, 213 bajtów

W ten sam sposób trochę golfa

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

Wypróbuj online!

PHP, 344 Bytes pierwszy działa

Po mojej pierwszej odpowiedzi zdecydowałem się na dłuższą próbę, która zwróci wszystkie ważne rozwiązania.

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

Wersja online

Awaria

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
źródło
Wydaje się, że działa to dla N ≥ 2, ale zawodzi w przypadku N = 1, takich jak pierwszy przypadek testowy w wyzwaniu.
Anders Kaseorg,
@AndersKaseorg Teraz obsługuje przypadki N = 1, wystarczy tylko ustawić =pierwszą pętlę dla krótszej wersji W większej wersji trzeba usunąć cztery bajty
Jörg Hülsermann
1

Python, 205 bajtów

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

Zwraca ciąg binarny bez separatora. Jak wskazuje @AndersKaseorg, istnieją dane wejściowe, dla których rozwiązanie @ fəˈnɛtɪk nie działa, ponieważ podział reprezentuje ujemny współczynnik, który jest niedozwolony. Aby obejść ten problem, używam bardzo dużej bazy i sprawdzam, czy w dziale nie ma pożyczki.

Neil
źródło
Okej, myślę, że to jest prawdziwy kontrprzykład: f([1, 1, 1, 0, 0, 0, 1, 1, 1], 3)niepoprawnie zwraca 101.
Anders Kaseorg,
@AndersKaseorg Hmm, czy odwrócenie kolejności pętli pomaga, czy algorytm jest nadal zasadniczo uszkodzony?
Neil
Myślę, że jest zasadniczo zepsuty bez dodatkowych kontroli. Odwrotny wariant zawodzi f([1, 0, 2, 0, 2, 0, 1], 3), a oba do przodu i do tyłu zawodzą f([1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0], 5).
Anders Kaseorg,
I nawet jeśli zaznaczysz, że ijest to nieparzyste, zarówno wariant do przodu, jak i do tyłu zawodzą f([1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]*10, 5).
Anders Kaseorg,
1
@AndersKaseorg Ach tak, kiedy gcd (k, n) = 1, (x^kn-1)/(x^k-1)zawsze ma (x^n-1)/(x-1)czynnik, który oszuka rozwiązanie @ fəˈnɛtɪk w dowolnej bazie.
Neil
1

Pyth, 32 bajty

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

Wypróbuj online

Jak to działa

                           ^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

Strategia jest podobna do mojej odpowiedzi w Pythonie , z tym wyjątkiem, że ponieważ Pyth ma wbudowane funkcje do konwersji bazy, możemy użyć bardziej wydajnej bazy k = 2 ⋅ suma (A) i bezpośrednio sprawdzić, czy każda cyfra ilorazu jest co najwyżej sumą (A ).

Anders Kaseorg
źródło
1

Pari / GP , 77 74 96 80 bajtów

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

Zwraca wszystkie rozwiązania.

Najpierw konwertuje tablicę ana wielomian b. Następnie wybiera z dzielników bwielomianów dtak, że współczynniki dsą wszystkie 1i 0, a wszystkie współczynniki b / dsą nieujemne, i d(0) = 1, i deg(d) = n + 1. Na koniec konwertuje je z powrotem na tablice.

Wypróbuj online!

alephalpha
źródło