Wprowadzenie

Klasy permutacji antsy zdefiniowałem we wcześniejszym wyzwaniu . Przypominamy, że permutacja p liczb od 0 do r-1 jest niespokojna, jeśli dla każdego wpisu p [i] oprócz pierwszego istnieje kilka wcześniejszych wpisów p [ik] takich, że p [i] == p [ ik] ± 1 . Jako zabawny fakt stwierdziłem również, że dla r ≥ 1 istnieją dokładnie 2 permutacje antsy ^r-1 o długości r . Oznacza to, że istnieje zgodność jeden na jeden między permutacjami antsy o długości r i wektorami binarnymi o długości r-1. W tym wyzwaniu Twoim zadaniem jest wdrożenie takiej korespondencji.

Zadanie

Twoim zadaniem jest napisanie programu lub funkcji, która pobiera wektor binarny o długości 1 ≤ n ≤ 99 i generuje anutyczną permutację o długości n + 1 . Permutacja może być oparta na 0 na 1 (ale musi być spójna), a dane wejściowe i wyjściowe mogą mieć dowolny rozsądny format. Co więcej, różne dane wejściowe muszą zawsze dawać różne wyniki; poza tym możesz zwrócić dowolną permutację antsy, którą chcesz.

Wygrywa najniższa liczba bajtów.

Przykład

Permutacje antsy (oparte na 0) o długości 4 są

0 1 2 3
1 0 2 3
1 2 0 3
1 2 3 0
2 1 0 3
2 1 3 0
2 3 1 0
3 2 1 0

a twój program powinien zwrócić jeden z nich dla każdego z ośmiu bitowych wektorów o długości 3:

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

Galaretka , 12 11 10 bajtów

ḟẋLṭ+
0;ç/

Wypróbuj online! lub wygeneruj wszystkie permutacje o długości 4 .

Jak to działa

0;ç/   Main link. Argument: B (bit array)

0;     Prepend a 0 to B.
  ç/   Reduce [0] + B by the helper link.


ḟẋLṭ+  Helper link. Left argument: A (array or 0). Right argument: b (bit)

 ẋ     Repeat A b times, yielding A or [].
ḟ      Filter false; remove the elements of A or [] from A.
  L    Get the length of the resulting array.
       This yield len(A) if b = 0 and 0 if b = 1.
    +  Add b to all elements of A.
   ṭ   Tack; append the result to the left to the result to the right.

Python 2, 62 60 bajtów

x=0,
for n in input():x=[t-n+1for t in x]+[n*len(x)]
print x

Dzięki @xnor za grę w golfa z 2 bajtów!

Przetestuj na Ideone .

Python, 54 bajty

lambda l:[i-i*x+sum(l[i:])for i,x in enumerate([1]+l)]

Stosuje następującą procedurę:

1. Dodaj 1 do listy.
2. Dla każdego 0 wpisu wpisz jego pozycję na liście 0 indeksowanych.
3. Dla każdego wpisu napisz liczbę 1 po jego prawej stronie, nie licząc się.
4. Dodaj wyniki kroków 2 i 3 wpisowo.

Na przykład l=[1,0,1,0]dajef(l) == [2,1,3,0,4]

List with prepended 1         1 1 0 1 0

0-indexed position for 0's        2   4
Number of 1's to right        2 1 1 0 0
Sum of above two              2 1 3 0 4

Podanie 0 również dałoby ten sam wynik. enumerateJest niezgrabne, zobaczymy, czy można to zrobić lepiej rekurencyjnie.

JavaScript (ES6), 48 47 45 bajtów

a=>[h=l=0,...a.map(c=>c?--l:++h)].map(e=>e-l)

Okazało się, że jest podobna do metody @ETHproductions, tyle że zacząłem od bezpośredniego obliczenia pierwszego elementu, a następnie za pomocą wektora binarnego, aby ustalić, czy każda cyfra jest nowym poziomem wysokim, czy nowym poziomem niskim. Edycja: Zapisano 1 bajt dzięki @ETHproductions. Zapisano 2 bajty, zaczynając od zera, a następnie dostosowując. Moja poprzednia metoda okazała się podobna do metody @ Dennisa, ale zajęła 54 bajty:

a=>a.reduce((r,b)=>[...r.map(e=>b+e),r.length*!b],[0])

Perl, 33 bajty

Obejmuje +1 dla -p

Podaj wektor jako ciąg bez spacji na STDIN:

antsy.pl <<< 110

antsy.pl:

#!/usr/bin/perl -p
s%^|.%y/0//+($&?++$a:$b--).$"%eg

JavaScript (ES6), 52 bajty

v=>[...v,l=0].map(x=>x?l++:h--,h=v.length).reverse()

Przetestuj to:

f=v=>[...v,l=0].map(x=>x?l++:h--,h=v.length).reverse()
g=v=>console.log(f((v.match(/[01]/g)||[]).map(x=>+x)))

<input oninput="g(this.value)" value="010">

Wyjaśnienie

Wykorzystuje to fakt, że po odwróceniu permutacji antsy każdy element jest albo o 1 większy niż maksimum poprzednich niskich wpisów, albo o 1 mniej niż minimum poprzednich wysokich wpisów. Oznaczając wyższy element jako a 0i niższy element jako a 1, możemy stworzyć dokładną zgodność jeden na jednego między permutacjami mrówek o długości n i wektorami binarnymi o długości n - 1 .

Najlepsze, co mogłem zrobić z techniką Dennisa, to 57 51 bajtów:

v=>v.reduce((x,n)=>[...x.map(i=>i+n),!n*++j],[j=0])
v=>v.map(n=>x=[...x.map(i=>i+n),!n*++j],x=[j=0])&&x

Rozwiązanie xnor to 56 (zapisano 1 bajt dzięki @Neil):

l=>[1,...l].map((x,i)=>i*!x+eval(l.slice(i).join`+`||0))

Haskell, 40 bajtów

foldl(\r a->map(+0^a)r++[a*length r])[0]

Rozwiązanie Dennisa w Python gra w golfa w Haskell z mapi fold. To krócej niż moje próby przeniesienia mojej bezpośredniej konstrukcji wejściowej:

f l=[i*0^x+sum(drop i l)|(i,x)<-zip[0..]$0:l]
f l=[a+c-b*c|(a,c,b)<-zip3(scanr(+)0l)[0..]$0:l]

Partia, 127 bajtów

@set s=%*
@set/an=h=l=%s: =+%
@for %%b in (%*)do @call:%%b
:0
@echo %n%
@set/an=h+=1
@exit/b
:1
@echo %n%
@set/an=l-=1

Pobiera dane wejściowe jako parametry wiersza polecenia, dane wyjściowe są oddzielone wierszem. (Możliwe jest wprowadzanie jako STDIN w postaci spacji bez dodatkowych kosztów).