Sekwencja liczb całkowitych jest jedną sekwencją, jeśli różnica między dowolnymi dwiema kolejnymi liczbami w tej sekwencji wynosi -1 lub 1, a jej pierwszym elementem jest 0.
Mówiąc dokładniej: a1, a2, ..., an jest jedną sekwencją, jeśli:
For any k (1 ≤ k < n): |a[k] - a[k+1]|=1,
a[1]=0
Wejście
n
- liczba elementów w sekwencjis
- suma elementów w sekwencji
Wynik
- zestaw / lista / tablica / itd. o jednej sekwencji
n
z sumą elementóws
, jeśli to możliwe - pusty zestaw / lista / tablica / etc, jeśli nie jest to możliwe
Przykłady
Dla danych wejściowych 8 4
wyjściem może być [0 1 2 1 0 -1 0 1]
lub [0 -1 0 1 0 1 2 1]
. Mogą istnieć inne możliwości.
W przypadku danych wejściowych dane 3 5
wyjściowe są puste []
, ponieważ nie można tego zrobić.
Zasady
To jest golfowy kod, wygrywa najkrótsza odpowiedź w bajtach. Zgłoszenia powinny być programem lub funkcją. Wejścia / wyjścia można podać na dowolny ze standardowych sposobów .
(l-1)*l/2
i-(l-1)*l/2
które mają taką samą parzystość jak(l-1)*l/2
.Odpowiedzi:
CJam,
56 47 4434 bajtówTutaj jest wiele możliwości ulepszeń, ale oto pierwsza próba:
Podziękowania dla Dennisa za efektywny sposób wykonania
{ ... }%
części.Drukuje reprezentację tablicy, jeśli to możliwe, w przeciwnym razie
""
Wypróbuj online tutaj
źródło
{}%
część twojego kodu nie przypomina mojego (co jest po prostu kodem @ PeterTaylor, zastępując kropki podkreśleniami). Jeśli włożyłem coś do twojego kodu, to jest{}=
operator ..._{_W=)+}%\{_W=(+}%+
który najpierw tworzył dwie kopie, dodawałem 1 do pierwszego, odejmując 1 od drugiego. Twój przykład kazał mi wymyślić, jak to zrobić w jednym{ ... }%
bloku. Jeśli chodzi o to{ ... }=
, już tak bardzo go zmniejszyłem w moich eksperymentach, choć jeszcze nie opublikowałem.3 5
wyjście powinno być,[]
a nie""
[]p
w CJam po prostu wysyła dane do""
. Tak więc język reprezentuje puste tablice.JavaScript (E6) 79
82Nie ma potrzeby brutalnej siły ani liczenia wszystkich krotek.
Zobacz sekwencję długości n jako n -1 kroków, przy czym każdy krok jest przyrostowy lub malejący.
Zauważ, że możesz zamienić przyrost tylko na zmniejszenie, suma zmienia się o 2, więc dla każdej długości suma jest zawsze parzysta lub zawsze nieparzysta.
Mając wszystkie przyrosty, sekwencja wynosi 0, 1, 2, 3, ..., n-1 i wiemy, że suma wynosi (n-1) * n / 2
Zmieniając ostatni krok, suma zmienia się o 2, więc ostatni krok waży 2.
Zmieniając następny na ostatni krok, suma zmienia się o 4, więc ostatni krok waży 4. To dlatego, że kolejny krok opiera się na częściowej sumie.
Zmieniając poprzedni krok, suma zmienia się o 6, więc ostatni krok waży 6 (nie 8, to nie są liczby binarne).
...
Zmiana pierwszego kroku waży (n-1) * 2
Algorytm
Nieskluczony kod
Przetestuj w konsoli Firefox / FireBug
Wynik
źródło
GolfScript (
4139 bajtów)Demo online
Dzięki Dennis za 41-> 39.
źródło
,0=
do?
. Prosty port do CJam byłby o 5 bajtów krótszy:L1,al~:S;({{_W=(+_)))+}%}*{:+S=}=p
{ ... }%
bloku. W moim kodzie miałem dwa, próbowałem zredukować go do 1. Tak jak w prawdziwym algorytmie, myślę, że zarówno Peter, jak i ja opublikowaliśmy ten sam algorytm prawie w tym samym czasie.Mathematica, 73 bajty
Proste rozwiązanie brutalnej siły.
Generuję wszystkie opcje kroków. Następnie przekształcam je w skumulowane listy, aby uzyskać sekwencje jednoelementowe. A potem szukam pierwszego, którego suma jest równa drugiemu parametrowi. Jeśli nie, wartością domyślną jest
{}
.źródło
Haskell, 56 bajtów
Wyjaśnienie:
1,-1
i długością n-1:replicateM n-1[-1,1]
Przykład:
replicateM 2 [-1,1]
==[[-1,-1],[-1,1],[1,-1],[1,1]]
scanl
ma słabą wydajność, ale tutaj robi dobrą robotę.n
gdzie suma jests
źródło
Control.Monad
tylko dla użycia,replicateM
które jest już za długie. jakiej innej funkcji monadycznej możesz użyć do symulacjireplicateM
?head$
do swojego rozwiązania.head
nie wraca[]
po[] :: [[a]]
- i nienawidzę błędów.mapM(\x->[1,-1])[2..n]
zamiastsequence
ireplicate
.Python, 138
źródło
CJam,
655854 bajtówNieco krótszy niż moje rozwiązanie Mathematica, ale to głównie moja wina, że nadal nie używam CJam poprawnie:
Jest to dosłownie ten sam algorytm: pobierz wszystkie
n-1
pary{1, -1}
. Znajdź pierwszy której kumulacja jest taka sama jaks
i przedrostek0
. Wydrukuj pustą tablicę, jeśli nie zostanie znaleziona.źródło
CJam, 40
Inne podejście w CJam.
źródło
Rubin (136)
źródło
J, 47 znaków
Sprawdza każdą sekwencję jak wiele innych odpowiedzi. Spróbuje stworzyć krótsze rozwiązanie O (n).
źródło
APL 38
Przykład:
Ten, jak wiele innych, po prostu przebija siły przez każdą kombinację, aby znaleźć taką, która pasuje, jeśli nie zostanie znaleziona, nic nie zwraca. W rzeczywistości kilkakrotnie próbuje niektórych kombinacji, aby skrócić kod.
źródło