Biorąc pod uwagę listę 1S i -1S, określić, czy jest to prawidłowy kod OVSF (przez wyprowadzanie truthy lub wartości falsey).

Kody OVSF są zdefiniowane w następujący sposób:

• [1] to kod OVSF.

• Jeśli Xjest to kod OVSF, to X ++ Xi X ++ -Xoba są kodami OVSF.

  Oto ++konkatenacja listy i -neguje każdy element na liście.

• Żadne inne listy nie są prawidłowymi kodami OVSF.

Możesz założyć, że lista wejściowa zawiera tylko -1i 1, ale musisz poprawnie obsługiwać pustą listę, a także listy, których długość nie jest potęgą 2.

Najkrótszy kod (w bajtach) wygrywa.

Przypadki testowe

[] -> False
[1] -> True
[-1] -> False
[1, 1] -> True
[1, -1] -> True
[1, 1, 1, 1] -> True
[1, 1, 1, 1, 1] -> False
[1, -1, -1, 1, -1, 1, 1, -1] -> True
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1] -> False
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1] -> False
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1] -> True

Galaretka , 18 16 14 11 bajtów

^2/Eam2µḊ¿Ṭ

Wyjścia [1](prawda) dla kodów OVSF, [](fałsz) w przeciwnym razie.

Wypróbuj online!

tło

Jak @ LuisMendo za Mátl odpowiedź i użytkownika @ XNOR Python odpowiedź , ten argument weryfikuje tablicy wejście „od wewnątrz out”.

Każda (nie nakładająca się) para elementów kodu OVSF o długości dwa lub większej jest zasadniczo kopią pierwszej pary, z tymi samymi znakami lub z zamienionymi obydwoma znakami. Podobnie, każda (nie nakładająca się) 4-krotna część elementów kodu OVSF o długości czterech lub większej jest zasadniczo kopią pierwszego 4-krotnego, z tymi samymi znakami lub z zamienionymi obydwoma znakami. To samo dotyczy 8-krotek, 16-krotek itp., Aż do długości kodu OVFS.

Jednym ze sposobów na sprawdzenie tego jest sprawdzenie najpierw wszystkich par dla znaku równości modulo, a następnie usunięcie drugiego elementu z każdej pary (która jest teraz informacją redundantną). Jeśli powtórzymy ten proces jeszcze raz, zasadniczo sprawdzamy wszystkie 4-krotki. W następnej iteracji porównujemy 8 krotek itp.

Wreszcie, jeśli wszystkie wymagane 2 ^k- pary były równe modulo znakowi, a tablica została zredukowana do singletonu, wystarczy sprawdzić, czy pozostały element to 1 .

Jak to działa

^2/Eam2µḊ¿Ṭ  Main link. Argument: A (array of 1's and -1's)

       µḊ¿   While dequeuing A (removing its first element) yields a non-empty
             array, execute the monadic chain to the left, updating A with the
             return value after each iteration.
^2/            Compute the bitwise XOR of each non-overlapping pair of elements of
               A. Note that 1 ^ 1 = 0 = -1 ^ -1 and 1 ^ -1 = -2 = -1 ^ 1.
               For an array of even length that consists of the same pairs modulo
               the sign, this returns either an array of 0's or an array of -2's.
               If the length is odd, it will also contain the last element, which
               is either a 1 or a -1.
   E           Test the elements of the result for equality. This yields 1 if the
               array consists solely of 0's or solely of -2's, 0 otherwise.
    a          Take the logical AND of the previous result and every element of A.
               This returns A if it passed the previous test, but replaces all of
               its elements with 0's otherwise.
     m2        Modulo 2; select every second element of A, starting with the first.
             At this point, the last return value can be:
               • [  ] if the input was empty
               • [ 1] if the input was a valid OVSF code
               • [-1] if the input was the negative of a valid OVSF code.
               • [ 0] in all other cases.
           Ṭ  Untruth; yield an array with 1's at the specified indices.
              Indexing is 1-based in Jelly, so [1] returns [1], the array with a 1
              at index 1. Since the indices -1 and 0 are non-canonical, the arrays
              [-1] and [0] are mapped to []. The empty array remains empty.

Mathematica, 52 47 45 bajtów

Liczba bajtów zakłada kodowanie CP-1252 i jest $CharacterEncodingustawiona na WindowsANSI(ustawienie domyślne w instalacjach Windows).

±___=!(±1=1>0)
a__±b__/;a!==b!||{a}==-{b}:=±a

Definiuje to funkcję wariadyczną PlusMinus, która przyjmuje listę wejściową jako płaską listę argumentów i zwraca wartość logiczną, np . PlusMinus[1, -1, -1, 1]Daje True. To teoretycznie również użyteczny jako operator ±, ale tylko, że operator jest składniowo poprawny w kontekstach jednoargumentowych i binarnych, więc konwencja powołanie dostanie dziwne: ±##&[1,-1,-1,1]. Wyrzuci kilka ostrzeżeń, które można zignorować.

Spowoduje to także wyświetlenie kilku ostrzeżeń, które można zignorować.

Nie może być z dala, aby skrócić nieco irytujące a!==b!||{a}==-{b}część, ale nie jestem znalezienie czegokolwiek teraz. Słowa kluczowe lubią SubsetQi MatrixRanksą po prostu za długie. : /

Wyjaśnienie

Rozwiązanie zasadniczo odkłada wszystkie trudne rzeczy na dopasowywanie wzorców Mathematica, a zatem ma bardzo deklaratywny styl. Oprócz nieco golfa w pierwszej linii, to naprawdę dodaje tylko trzy różne definicje dla operatora ±:

±___=False;
±1=True;
a__±b__/;a!==b!||{a}==-{b}:=±a

Pierwsze dwa wiersze zostały skrócone przez zagnieżdżenie definicji i wyrażenie Truejako 1>0.

Powinniśmy dalej to zdekonstruować, aby pokazać, jak to faktycznie definiuje funkcję variadci, PlusMinusużywając tylko jednoargumentowej i binarnej notacji operatora. Chodzi o to, że wszyscy operatorzy są po prostu cukrem syntaktycznym dla pełnych wyrażeń. W naszym przypadku ±odpowiada PlusMinus. Poniższy kod jest w 100% równoważny:

PlusMinus[___]=False;
PlusMinus[1]=True;
PlusMinus[a__,b__]/;a!==b!||{a}==-{b}:=PlusMinus[a]

Wykorzystując sekwencje (coś w rodzaju spacji w innych językach) jako argumenty do ±możemy objąć dowolną liczbę argumentów PlusMinus, nawet jeśli ±nie można ich użyć z więcej niż dwoma argumentami. Podstawowym powodem jest to, że cukier syntaktyczny jest najpierw rozstrzygany, zanim dowolna z tych sekwencji zostanie rozwinięta.

Do definicji:

Pierwsza definicja jest po prostu rezerwą ( ___pasuje do dowolnej listy argumentów). Daje wszystko, co nie pasuje do bardziej szczegółowych definicji poniżej False.

Druga definicja jest podstawowym przypadkiem OVSF, lista zawiera tylko 1. Określamy to jako True.

Wreszcie trzecia definicja dotyczy tylko list, które można rozłożyć na X ++ Xlub X ++ -Xrekurencyjnie wykorzystuje wynik dla X. Definicja ogranicza się do tych wykazów poprzez zapewnienie mogą być podzielone na podciągów ai bz a__±b__a następnie dołączenie warunku ( /;), które albo {a}=={b}albo {a}==-{b}. Zdefiniowanie PlusMinusw ten dziwny sposób funkcji variadic za pomocą operatora pozwala zaoszczędzić aż 5 bajtów przed zdefiniowaniem jednego operatora ±na listach.

Ale czekaj, jest więcej. Używamy a!==b!zamiast {a}=={b}. Oczywiście robimy to, ponieważ jest on o dwa bajty krótszy, ale interesujące pytanie brzmi, dlaczego to działa. Jak wyjaśniłem powyżej, wszyscy operatorzy to tylko cukier syntaktyczny dla pewnej ekspresji z głową. {a}jest List[a]. Ale ajest to sekwencja (jak powiedziałem, coś w rodzaju innych języków), więc jeśli tak, ato 1,-1,1otrzymamy List[1,-1,1]. Teraz !jest postfiks Factorial. Więc tutaj dostaniemy Factorial[1,-1,1]. Ale Factorialnie wie, co zrobić, gdy ma inną liczbę argumentów niż jeden, więc po prostu pozostaje to bezcenne. ==tak naprawdę nie dba o to, czy po obu stronach są listy, po prostu porównuje wyrażenia, a jeśli są równe, dajeTrue(w tym przypadku nie da się, Falsejeśli tak nie jest, ale wzorce nie pasują, jeśli warunek zwraca coś innego niż True). Oznacza to, że kontrola równości nadal działa, jeśli na liście znajdują się co najmniej dwa elementy. Co jeśli jest tylko jeden? Jeśli ajest, 1to a!jest nadal 1. Jeśli atak -1to a!daje ComplexInfinity. Teraz porównywanie 1do siebie nadal działa dobrze. Ale ComplexInfinity == ComplexInfinitypozostaje nieoceniony i chociaż nie daje prawdy a == -1 == b. Na szczęście to nie ma znaczenia, ponieważ jedyna sytuacja, w PlusMinus[-1, -1]której się pojawia, to i tak nie jest prawidłowy OVSF! (Jeśli warunek powróci True, połączenie rekurencyjne zgłosi sięFalsew końcu, więc nie ma znaczenia, że ​​sprawdzenie się nie powiedzie.) Nie możemy użyć tej samej sztuczki, {a}==-{b}ponieważ -nie chce się przewinąć Factorial, tylko się przewraca List.

Dopasowujący wzór zajmie się resztą i po prostu znajdzie właściwą definicję do zastosowania.

Haskell, 57 bajtów

q=length
f l=l==until((>=q l).q)(\s->s++map(*l!!q s)s)[1]

Biorąc pod uwagę listę danych wejściowych l, rozwija kod OVSF s, zaczynając od [1]i wielokrotnie łącząc jeden slub jeden -s, w zależności od tego, który pierwszy element pasuje do tego l. Następnie sprawdza, czy wynik jest lna końcu. Jest to sprawdzane, gdy sma co najmniej długość l.

Niektóre alternatywne struktury rekurencyjne również dały 57:

(s%i)l|length l<=i=s==l|j<-2*i=(s++map(*l!!i)s)%j$l
[1]%1

q=length
s%l|q s>=q l=s==l|r<-s++map(*l!!q s)s=r%l
([1]%)

q=length
g s l|q s<q l=g(s++map(*l!!q s)s)l|1>0=s==l
g[1]

MATLAB / oktawa , 94 bajty

function a=f(r);n=nnz(r);m=log2(n);a=0;if fix(m)-m==0;for c=hadamard(n);a=a+all(r==c');end;end

Wykorzystuje to nowe podejście: Dozwolone kody długości OVSF Npojawiają się w log2(N)-tej macierzy Walsha , ponieważ są one zasadniczo zdefiniowane przez tę samą rekurencję:

Macierze Walsha są szczególnymi przypadkami macierzy Hadamarda wielkości, N x Njeśli Njest potęgą dwóch. (Istnieją również macierze Hadamarda o innych rozmiarach.) MATLAB i Octave mają wiele wbudowanych funkcji, które generują macierze testowe do testowania właściwości algorytmów numerycznych, między innymi hadamard(). Na szczęście dla mocy dwóch zastosowań MATLABa hadamard()właśnie konstrukcja walijskich matryc.

Ta funkcja najpierw sprawdza, czy długość wejściowa jest potęgą dwóch, a jeśli tak, to sprawdza, czy jest to rząd o odpowiedniej wielkości matrycy walijskiej.

Wypróbuj online!

Python, 64 bajty

f=lambda l:[]<l[1::2]==[x*l[1]for x in l[::2]]*f(l[::2])or[1]==l

Dzieli listę na elementy parzyste i nieparzyste za pomocą plasterków. Sprawdza, czy wektory wynikowe są równe lub ujemne, mnożąc jeden przez znak wymuszony przez jego pierwszy element. Następnie wykonuje tę samą rekurencyjną kontrolę elementów parzysto indeksowanych.

W przypadku podstawowym, jeśli sprawdzenie się nie powiedzie, odrzuca, chyba że lista jest [1]. Pusta lista jest również specjalnie odrzucana, aby uniknąć nieskończonej pętli.

Inna strategia, taka jak moja odpowiedź Haskella, daje 66 bajtów:

f=lambda l,i=1,s=[1]:l[i:]and f(l,i*2,s+[x*l[i]for x in s])or s==l

Haskell , 106 91 87 86 bajtów

g n|n<1=[[1]]|m<-g(n-1)=foldl(\a b->[b++map(0-)b,b++b]++a)[]m++m
f l=elem l$g$length l

Ta funkcja ggeneruje niterację list (stosunkowo nieefektywnie, ponieważ length $ g n == 3^njeśli jednak usuniemy duplikaty, dostaniemy 2^n), fsprawdza, czy nasza lista znajduje się na którejkolwiek z nich. Dzięki @Zgrab za kilka wskazówek!

Wypróbuj online!

JavaScript (ES6), 130 93 87 85 83 bajtów

f=a=>(b=a.slice(0,l=a.length/2),c=a.slice(l)+"",a==1||l&&b==c|b.map(i=>-i)==c&f(b))

Próbny

f=a=>(b=a.slice(0,l=a.length/2),c=a.slice(l)+"",a==1||l&&b==c|b.map(i=>-i)==c&f(b)),[[],[1],[-1],[1,1],[1,-1],[1,1,1,1],[1,1,1,1,1],[1,-1,-1,1,-1,1,1,-1],[1,1,1,1,-1,-1,-1,-1,1,1,1,1],[1,1,1,1,-1,-1,-1,-1,1,1,1,1,1,1,1,1],[1,1,1,1,-1,-1,-1,-1,1,1,1,1,-1,-1,-1,-1]].map(a=>console.log(`[${a}] -> ${!!f(a)}`))

JavaScript (ES6), 85 61 bajtów

a=>(l=a.length)&&!(l&l-1)&a.every((e,i)=>e==a[j=i&-i]*a[i-j])

Poprzednia wersja, która sprawdzała elementy, aby upewnić się, że były 1lub -1:

a=>(l=a.length)&&!(l&l-1)&a.every((e,i)=>i?(j=i&-i)<i?e==a[j]*a[i-j]:e==1|e==-1:e==1)

Wyjaśnienie:

• Długość nie może wynosić zero
• Długość musi być potęgą 2
• Pierwszym elementem musi być 1
• Elementy w pozycjach o sile 2 muszą mieć wartość 1 lub -1
• Elementy w innych pozycjach są iloczynem wszystkich elementów w pozycjach odpowiadających masce bitowej, np a[22] == a[2] * a[4] * a[16]. Ponieważ a[20] == a[4] * a[16]zostało już sprawdzone, a[22] == a[2] * a[20]wystarczy je sprawdzić.
• Powyższa kontrola daje wyniki zdegenerowane za ibrak ustawienia co najmniej dwóch bitów. W przypadku zestawu bitów zerowych sprawdza to a[0] == a[0] * a[0], co jest fałszem a[0] == -1, natomiast w przypadku zestawu bitów sprawdza to a[i] == a[0] * a[i].

MATL , 21 20 bajtów

`2eZ}yy=&=tn1>hh]1X=

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Jak to działa

Kod dzieli tablicę na dwie równe części: pierwsza z nieparzystymi indeksami, druga z nieparzystymi indeksami. Dwa elementy są zmuszone do równej długości, z wypełnieniem zero w drugim w razie potrzeby. Następnie kod to sprawdza

1. Odpowiednie wpisy dwóch elementów są albo równe, albo różne;
2. Brak wpisu w drugim kawałku wynosi zero;
3. Długość elementów przekracza 1.

Jeśli te trzy warunki zostaną spełnione, proces zostanie ponownie zastosowany do pierwszego elementu. Jeśli pętla zostanie zakończona, ponieważ długość wynosiła już 1, wejściem jest kod OFSV. W przeciwnym razie tak nie jest.

Iteracja warunku 1 jest równoważną wersją właściwości definiującej kodów OVSF. Dla tablicy o powiedzmy długości 8 najprostszym podejściem byłoby sprawdzenie, czy wszystkie wpisy 1,2,3,4 są równe lub wszystkie różnią się odpowiednio od wpisów 5,6,7,8 (jest to właściwość definiująca). Ale możemy w równoważny sposób sprawdzić, czy wpisy 1,3,5,7 są równe lub wszystkie różnią się odpowiednio od wpisów 2,4,6,8; i okazuje się, że używa mniej bajtów.

Warunek 2 upewnia się, że długość wejściowa jest potęgą 2: jeśli nie, dopełnienie zerowe zostanie wprowadzone na pewnym etapie.

`        % Do...while loop
  2e     %   Reshape as a two-row matrix, with a padding zero if needed
         %   Row 1 contains the original odd-indexed entries, row 2 the
         %   even-indexed
  Z}     %   Split matrix into two vectors, one corresponding to each row
  yy     %   Duplicate those two vectors
  =      %   Check if corresponding entries are equal or not
  &=     %   Matrix of all pairwise comparisons. This will give a matrix
         %   filled with ones if and only if the previous check gave all
         %   true or all false (condition 1)
  tn1>   %   Duplicate and push true if size exceeds 1, or false otherwise
         %   (condition 3)
  hh     %   Concatenate condition 1, condition 3, and the original copy of
         %   the second piece (condition 2). The resulting vector is truthy
         %   if and only if it doesn't contain any zero
]        % End
1X=      % True if top of the stack is a single 1, false otherwise

Haskell, 66 bajtów

Tak, nieskończone listy!

o=[1]:(o>>= \x->[x++map(0-)x,x++x])
f l=l`elem`take(2*2^length l)o

Alternatywne wersje:

o=[1]:(o<**>map(>>=flip(++))[map(0-),id])
f=Data.List.Ordered.hasBy(comparing length)o

APL, 46 bajtów

{0::0⋄⍵≡,1:1⋄⍬≡⍵:0⋄(∇Z↑⍵)∧(∇Y)∨∇-Y←⍵↓⍨Z←.5×⍴⍵}

Dość bezpośredni:

• Obudowy podstawowe:
  • 0::0: jeśli wystąpi błąd, zwróć 0
  • ⍵≡,1:1: jeśli dane wejściowe są dokładnie [1], zwróć 1
  • ⍬≡⍵:0: jeśli wejście jest pustą listą, zwróć 0
• Przypadek rekurencyjny:
  • Z←.5×⍴⍵: Zto połowa długości wejścia
  • Y←⍵↓⍨Z: Yjest ostatnią połową danych wejściowych (nie powiedzie się, jeśli ⍴⍵jest nierówna, co powoduje uruchomienie procedury obsługi wyjątków)
  • (∇Y)∨∇-Y: ostatnia połowa listy lub negacja ostatniej połowy listy musi być kodem OVSF
  • (∇Z↑⍵)∧: a pierwsza połowa listy musi być kodem OVSF.

Haskell, 69 68 bajtów

g x=any(elem x)$scanr(\_->concat.mapM(\y->[y++y,y++map(0-)y]))[[1]]x

Przykład użycia: g [-1,1]-> False.

Jeszcze bardziej nieefektywna niż odpowiedź @ flawr . Zajmuje zbyt dużo czasu i pamięci dla list 4-elementowych. Aby zobaczyć, że lista kodów OVSF (z dużą liczbą duplikatów) jest rzeczywiście utworzona, spróbuj:

take 10 $ c $ scanr(\_->concat.mapM(\y->[y++y,y++map(0-)y]))[[1]] [1..4]

który zwraca

[[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
 [1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1],
 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
 [1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1],
 [1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1],
 [1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1],
 [1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1],
 [1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1],
 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
 [1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1]]

tzn. lista zaczyna się od wszystkich 16 list elementów (z 4 razy połączonych [1..4]), kontynuuje od wszystkich 8 list elementów i tak dalej, aż do końca [1].

Edycja: @xnor zapisał bajt. Dzięki!

Python 2 , 78 75 bajtów

def f(x):l=len(x)/2;return[n*x[l]*f(x[:l])for n in x[l:]]==x[:l]>[]or[1]==x

Wypróbuj online!

JavaScript (ES6), 80

f=(l,k=[1])=>l+l==k+k||l[k.length]&&f(l,k.concat(k))|f(l,k.concat(k.map(v=>-v)))

Rekurencyjnie buduje i sprawdza każdą listę do długości listy danych wejściowych, zaczynając od [1].

Zwracana jest wartość JS truthy lub falsey, specjalnie 1lub truejeśli ważny, 0lub falselub undefinedjeśli nie ważne.

Test

f=(l,k=[1])=>l+l==k+k||l[k.length]&&f(l,k.concat(k))|f(l,k.concat(k.map(v=>-v)))

test=`[] -> False
[1] -> True
[-1] -> False
[1, 1] -> True
[1, -1] -> True
[1, 1, 1, 1] -> True
[1, 1, 1, 1, 1] -> False
[1, -1, -1, 1, -1, 1, 1, -1] -> True
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1] -> False
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1] -> False
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1] -> True`
.split('\n')

test.forEach(r=>{
  input = r.match(/-?1/g)||[]
  check = r.slice(-4) == 'True'
  result = f(input)
  console.log(result, check, '['+input+']')
})

Clojure, 118 bajtów

(defn f[C](or(=(count C)1)(let[l(/(count C)2)[a b](split-at l C)](and(> l 0)(=(count b)l)(apply =(map * a b))(f a)))))

Dzieli dane wejściowe cna dwie połowy ai bsprawdza, czy wszystkie ich produkty są identyczne. Jeśli tak, sprawdza, czy pierwsza połowa jest prawidłową sekwencją.

Ten ma 142 bajty, ale uważam, że jest bardziej interesujący:

#((set(nth(iterate(fn[I](mapcat(fn[i][(concat i i)(concat i(map - i))])I))[[1][-1]])(loop[l(count %)i 0](if(< l 2)i(recur(/ l 2)(inc i))))))%)

loopoblicza log_2długość wejściową, iterategeneruje sekwencje z wielu iteracji na podstawie definicji. Zwraca argument wejściowy, jeśli jest to poprawna sekwencja i nilinaczej.