Biorąc pod uwagę ciąg N długości mniejszy niż i większy niż znaki ( <
, >
), wstaw liczby całkowite od 0 do N na początku i na końcu oraz pomiędzy każdą parą znaków, aby wszystkie nierówności zostały spełnione. Wyprowadza wynikowy ciąg. Jeśli istnieje wiele prawidłowych wyników, wypisz dowolne (i tylko jedno) z nich.
Na przykład
<<><><<
ma 7 znaków, więc należy wstawić wszystkie cyfry od 0 do 7 włącznie. Prawidłowe wyjście to
2<3<4>1<5>0<6<7
ponieważ wszystkie nierówności były podejmowane pojedynczo
2<3
3<4
4>1
1<5
5>0
0<6
6<7
są prawdziwe.
W razie potrzeby na wyjściu mogą znajdować się spacje otaczające znaki, np 2 < 3 < 4 > 1 < 5 > 0 < 6 < 7
.
Najkrótszy kod w bajtach wygrywa.
Przypadki testowe
Pierwszy wiersz po pustym wierszu jest wejściem, a następne wiersze są prawidłowymi przykładami danych wyjściowych.
[empty string]
0
<
0<1
>
1>0
<<
0<1<2
<>
1<2>0
><
1>0<2
2>0<1
>>
2>1>0
<<<
0<1<2<3
><>
1>0<3>2
>><
3>2>0<1
3>1>0<2
2>1>0<3
>>>
3>2>1>0
>>><<<
3>2>1>0<4<5<6
6>3>1>0<2<4<5
4>2>1>0<3<5<6
4>3>1>0<2<5<6
<<><><<
2<3<4>1<5>0<6<7
>><><>>
7>6>0<5>1<4>3>2
<<<<<<<<<<<<<<
0<1<2<3<4<5<6<7<8<9<10<11<12<13<14
>><<<<><>><><<
6>5>4<7<8<9<10>3<11>2>1<12>0<13<14
14>5>4<7<8<9<10>3<11>2>1<12>0<13<6
code-golf
math
arithmetic
permutations
integer
Hobby Calvina
źródło
źródło
Odpowiedzi:
Siatkówka , 20 bajtów
Liczba bajtów zakłada kodowanie ISO 8859-1.
Wypróbuj online! (Pierwszy wiersz włącza pakiet testowy oddzielony od linii).
Wyjaśnienie
Prostym sposobem na znalezienie prawidłowej permutacji jest rozpoczęcie od wstawienia liczb od
0
doN
w kolejności, a następnie odwrócenie liczb otaczających każdy podciąg>
s. Weź<><<>>><<
jako przykład:Oba te zadania są dość proste w Retinie, mimo że wszystko, z czym naprawdę możemy pracować, to łańcuchy. Możemy zaoszczędzić dodatkowy bajt, wstawiając liczby od
N
dołu do0
i odwracając otaczające sekcje<
, ale zasada jest taka sama.Etap 1: Zmiana
Zaczynamy od wstawienia długości
$'
(sufiksu, czyli wszystkiego po dopasowaniu) w każdej możliwej pozycji na wejściu. To wstawia liczby odN
do0
.Etap 2: Podział
Podzieliliśmy dane wejściowe
>
na osobne linie, więc każda linia jest albo indywidualną liczbą, albo listą liczb połączonych<
.Etap 3: Sortuj
W obrębie każdej linii (
%
) sortujemy (O
) liczby (\d#
) według ich wartości liczbowej (#
). Ponieważ wstawiliśmy liczbę w odwrotnej kolejności numerycznej, powoduje to ich odwrócenie.Etap 4: Zmiana
Zamieniamy
>
ponownie źródła linii, aby połączyć wszystko z powrotem w jedną linię. Otóż to.Na marginesie chciałem dodać sposób zastosowania
%
do innych ograniczników niż linie. Gdybym to zrobił, przesłanie to miałoby 14 bajtów, ponieważ wówczas trzy ostatnie etapy zostałyby zredukowane do jednego:źródło
> <> ,
464335 + 4 dla-s=
= 39 bajtówJest to implementacja algorytmu xnor w> <>.
Pobiera ciąg wejściowy na stosie (
-s
flaga ze standardowym interpreterem).Możesz to wypróbować na tłumaczu online .
źródło
> <> , 26 + 4 = 30 bajtów
Wypróbuj online! +4 bajty dla
-s=
flagi - jeśli tylko-s
jest w porządku (oznaczałoby to, że flaga musiałaby zostać całkowicie usunięta z powodu pustych danych wejściowych), to zamiast tego byłoby +3.Zakłada, że wejście STDIN jest puste, więc
i
daje -1 (co robi na EOF). Program popełnił błąd podczas próby wydrukowania tego -1 jako znaku.Wykorzystuje podejście max-of-nums-dotychczas-dotychczas-for-
>
, min-of-nums-dotychczas-dotychczas-for-<
.Program, który kończy się czysto i nie przyjmuje założenia o STDIN, ma 4 dodatkowe bajty:
źródło
CJam , 16 bajtów
Wypróbuj online!
Port mojej odpowiedzi Retina .
Wyjaśnienie
źródło
Perl, 29 bajtów
Obejmuje +2 za
-lp
Uruchom z wejściem na STDIN, np
Wynik:
order.pl
:Wyjaśnienie
Posiadaj dwa liczniki, maks. Zaczynając od długości łańcucha, min zaczynając od 0. Następnie na każdej granicy (w tym na początku i na końcu łańcucha), jeśli jest tuż przed
<
wstawieniem minimum tam i zwiększ o 1, w przeciwnym razie umieść tam maksimum i zmniejsz o 1 (na końcu ciągu nie ma znaczenia, który licznik bierzesz, ponieważ oba są takie same)źródło
s{}{/\G/...}
Nigdy wcześniej tego nie widziałem, jest genialny.Python 2, 67 bajtów
Funkcja rekurencyjna. Spełnia każdy operator kolejno oddanie najmniejszą niewykorzystaną wartość
x
dlax<
a największe dlax>
. Najmniejsza nieużywana wartość jest przechowywanai
i aktualizowana, a największa nieużywana wartość jest wywnioskowana nai
podstawie pozostałej długości.źródło
(s>'=')
zamiast(s>='>')
zaoszczędzić bajt?<
i>
nie są to kolejne punkty kodowe.=
między<
a>
.Python 2,
163137 bajtówTasuje liczby, aż oświadczenie przejdzie do
True
.Spróbuj.
źródło
APL, 33 bajty
⍋⍋
jest niezwykle przydatny.Wyjaśnienie
źródło
⍋⍋
)?⍋
to ocena w górę, która zwraca wskaźniki w posortowanej kolejności. Robiąc to dwa razy, dostajesz,1
gdzie była najmniejsza liczba,2
gdzie była następna najmniejsza liczba, itd.JavaScript (ES6),
7456 bajtówZaczyna się od zestawu liczb
0...N
. Na każdym etapie po prostu bierze największą (l
) lub najmniejszą (j
) z pozostałych liczb; następny numer musi być z definicji mniejszy lub większy niż ten. Edycja: Zaoszczędź 18 bajtów dzięki @Arnauld.źródło
replace
? Możes=>s.replace(/./g,c=>(c<'>'?j++:l--)+c,j=0,l=s.length)+j
replace
) do 74 bajtów ...Pyth - 19 bajtów
Brawo dla łączenia łańcuchów!
Nie działa online, ponieważ istnieje absolutne bezpieczeństwo.
źródło
2sable , 20 bajtów
Wyjaśnienie
Wypróbuj online!
Dla N <10 może to być 14 bajtów:
źródło
C #,
10299 bajtówNie golfowany:
źródło
r = r +
części na złożone zadanie , gdyby nie kilka bajtów?r+
część po prawej stronie informuje kompilator, że cała rzecz jest ciągiem, dlategoc
używana jest reprezentacja ciągu . Gdybym użyłr+=
,?:
część byłaby oceniana naint
,c
dodawana byłaby do niej wartość porządkowa , i tylko wtedy byłaby konwertowana na reprezentację ciągu.Java 8,
126125 bajtówNie sądzę, że to nawet działa hehe
Nie testowany program testowy
źródło
.replaceAll
, aby.replace
i usuń nawiasy wokół(c+"")
zaoszczędzić 5 bajtów.Galaretka ,
27 1412 bajtówPort rozwiązania @Martin Enders CJam
-2 bajty dzięki @Dennis
Przetestuj w TryItOnline
W jaki sposób?
Poprzednia metoda była interesująca matematycznie, ale nie tak golfowa ...
Wykorzystuje on system bazowy silni do znalezienia indeksu permutacji [0, N], który spełni równanie.
źródło
U
wektoryzuje, więc nie potrzebujesz€
.żJ0;
zapisuje kolejny bajt.Clojure,
152132126 bajtówZaoszczędził sporo bajtów, eliminując tyle spacji, ile mogłem. Uświadomiłem sobie, że białe znaki nie są konieczne do oddzielenia nawiasu od innej postaci.
Zasadniczo port Clojure odpowiedzi @ Scepheo. Działa identycznie.
Te
recur
połączenia są zabójcze!Podejrzewam, że mógłbym użyć atomów do oczyszczenia go.Doswap!
połączenia wymagane do korzystania atomów dodany do hrabiego: /Dzięki @amalloy za uratowanie mi kilku bajtów.
Nie golfowany:
źródło
loop
powiązaniu, przeds
i poa
. Można również golić trochę zastępującif
drzewa zcase
:(case c \< (recur ...) nil (str ...) (recur ...))
. I oczywiściecr
może to być krótsza nazwa.Haskell, 162 bajty
To jest cholernie długie.
źródło
Perl (107 + 1 dla -p) 108
Algorytm skradzione Martin Ender ♦ 's odpowiedź
źródło
Rubin, 135 bajtów
Uwaga: złożoność czasu jest duża (O (n!)).
źródło
Python 2,
176172 bajtówNie jest bardzo krótki w porównaniu do innych, ale cieszę się, że rozwiązałem go tak szybko.
Wypróbuj online
Nie golfowany:
Wypróbuj online
źródło
zip
pop
), ale są nieco krótsze. GdybymN<10
mógł skrócić sznurowanie.PHP, 190 bajtów
losowe odtwarzanie losowe do momentu znalezienia prawidłowego rozwiązania
381 bajtów dostaje wszystkie rozwiązania i wybiera jedno
źródło