Mam sterowaną korbą pozytywkę, która może odtwarzać serię czterech dźwięków. Kiedy obracam korbą, wyrywa ona jeden z czterech strun, w zależności od położenia korby i kierunku obrotu. Kiedy korba jest skierowana na północ, skrzynia (z jej łańcuchami ponumerowanymi od 1 do 4) wygląda następująco:
1 | 2
|
O
4 3
Stamtąd mogę obrócić korbą w kierunku zgodnym z ruchem wskazówek zegara, aby zerwać sznur nr 2 i skierować korbę na wschód:
1 2
O---
4 3
Alternatywnie, mógłbym również obrócić korbą w kierunku przeciwnym do ruchu wskazówek zegara z północy, aby zagrać na strunie nr 1 i zakończyć korbą skierowaną na zachód:
1 2
---O
4 3
Zatem w danym momencie skrzynka może odtwarzać jedną z dwóch nut: następną nutę dostępną w kierunku zgodnym z ruchem wskazówek zegara lub następną nutę w kierunku przeciwnym do ruchu wskazówek zegara.
Wyzwanie
Twoim wyzwaniem jest, aby napisać program lub funkcję, która akceptuje niepusty ciąg wartości Note (tj cyframi 1
pośrednictwem 4
) i określić, czy jest to możliwe, aby zagrać tę sekwencję nut na polu muzycznym. Podaj wynik zgodny z prawdą lub fałszem, aby wskazać grywalność lub brak możliwości gry na danych wejściowych.
Niektóre uwagi:
Dane wejściowe nie zakładają początkowej pozycji początkowej. Dane wejściowe
214
(rozpoczynające się na wschód i poruszające się ściśle przeciwnie do ruchu wskazówek zegara) i234
(rozpoczynające się na północ i poruszające się ściśle zgodnie z ruchem wskazówek zegara) i oba są ważne.Korba może się swobodnie poruszać w dowolnym kierunku po każdej nucie. Seria tej samej nuty jest możliwa (np.
33333
) Poprzez przesuwanie się w przód i w tył po jednym strunie. Serię1221441
można doskonale grać (zaczynając na zachód, przesuwając dwa kroki zgodnie z ruchem wskazówek zegara, następnie trzy kroki przeciwnie do ruchu wskazówek zegara, a następnie dwa kroki zgodnie z ruchem wskazówek zegara).
Próbki
Niektóre true
przypadki:
1
1234
1221
3333
143332
22234
2234
22214
1221441
41233
Niektóre false
przypadki:
13 (note 3 is never available after note 1)
1224 (after `122`, the crank must be north, so 4 is not playable)
121 (after `12` the crank is east; 1 is not playable)
12221 (as above, after `1222` the crank is east)
43221
źródło
Odpowiedzi:
Pyth,
3027 bajtówOto pomysł:
Korba jest zawsze w pozycji połowy liczby całkowitej
c
. Na każdym kroku odzwierciedlamy ją nad nutą pozycji całkowitejn
przez ustawieniec = 2*n-c
. Jeślin
jest poprawny,c
zmienia się o ± 1 mod 8. Jeślin
jest nieważny,c
zmienia się o ± 3 mod 8. Łącznie zmniejszamy wartość wejściową, aby zebrać wszystkie wartościc
, a następnie sprawdzić, czy wszystkie nuty są prawidłowe. Robimy to dla każdej wartości początkowejc
, ponieważ jest krótsza niż sprawdzenie tylko tych sąsiadujących z pierwszą nutą.Sformatowany:
Zestaw testowy .
źródło
CJam,
3431 bajtówZrobiłem to na moim telefonie, więc będę musiał wyjaśnić później.Dane wyjściowe są niepuste, jeśli są zgodne z prawdą.Wypróbuj online | Zestaw testowy
Wyjaśnienie
Nowy kod nieco zmienia układ:
Liczby parzyste odpowiadają pozycjom strun, a liczby nieparzyste odpowiadają pozycjom korby.
Oto co się dzieje:
Stos jest następnie automatycznie drukowany na końcu. Wszelkie możliwe pozycje końcowe będą na wyjściu, np. Dla wejścia
1
jest wyjście31
, co oznacza, że korba może kończyć się skierowaną w lewo lub w górę.Gdyby tylko CJam miał filtr z dodatkowym parametrem ...
Edycja: Tymczasowo się wycofuję, a ja przekonuję się, że ten 29-bajtowy działa:
źródło
Haskell,
93 8887 bajtówTo ocenia na anonimową funkcję, która pobiera ciąg znaków i zwraca wartość logiczną. Zestaw testowy tutaj.
Wyjaśnienie
Chodzi o to, że lambda po prawej mapuje liczbę
a
do[[a,a+1],[a+1,a]]
, dwóch możliwych „ruchów”, które odbywają korbą nad tym numerem, zgodnie z następującym schematem:W głównej funkcji anonimowej najpierw robimy
mapM((...).read.pure)
, która konwertuje każdy znak na liczbę całkowitą, stosuje do niego powyższą lambdę i wybiera jeden z dwóch ruchów, zwracając listę wszystkich wynikowych sekwencji ruchów. Następnie sprawdzamy, czy którakolwiek z tych sekwencji ma właściwość, że druga liczba każdego ruchu jest równa pierwszej liczbie następnego modułu 4, co oznacza, że jest to fizycznie możliwa sekwencja. Aby to zrobić,zip
każdy z nich przesuwa sekwencję razem z niątail
, sprawdzamy warunek dlaall
par i sprawdzamy, czyany
sekwencja się sprawdzaTrue
.źródło
Siatkówka, 50 bajtów
Myślę, że to działa?
Wypróbuj tutaj.
źródło
Siatkówka ,
127109 bajtówTo drukuje
0
lub1
odpowiednio.Wypróbuj online! (Jest to nieco zmodyfikowana wersja, która oznacza wszystkie dopasowania na wejściu zamiast drukowania
0
lub1
.)Próbowałem wymyślić elegancki algorytm, ale moich pierwszych kilku próbom nie udało się ominąć cofania się ... a implementacja powrotu jest denerwująca ... więc użyłem języka, który wykonuje dla mnie cofanie, w którym muszę tylko zakodować prawidłowe rozwiązanie. Niestety kodowanie jest dość pełne i dość zbędne ... Jestem pewien, że można to skrócić.
Podczas gdy próbuję wymyślić coś bardziej zgrabnego, jeśli ktoś chce dowiedzieć się, jak to działa, oto nieco bardziej czytelna wersja:
A oto wskazówka:
źródło
MATL ,
5755 bajtówUżywa bieżącej wersji (10.2.1) , która jest wcześniejsza niż to wyzwanie.
EDIT (17 stycznia 2017): ze względu na zmiany w języku,
v
musi być zastąpiona&v
, atL3$)
przezY)
(dodatkowo kilka innych usprawnień mogły być wykonane). Poniższy link zawiera te dwie modyfikacjeWypróbuj online!
Wyjaśnienie
Jest to oparte na dwóch moich ulubionych narzędziach do gry w golfa kodowego: brutalnej sile i konwolucji .
Kod określa ścieżkę , po której następuje korby pod względem współrzędnych
0.5
,1.5
itd Każdy numer mówi położenia wału korbowego pomiędzy nutami. Kod najpierw tworzy tablicę ścieżek ze wszystkimi możliwymi ścieżkami, które zaczynają się od pierwszej nuty ciągu wejściowego. Każda ścieżka jest kolumną w tej tablicy. To składnik siły brutalnej .Z tej tablicy ścieżek uzyskuje się tablicę nut , gdzie każda kolumna jest możliwą do wykonania sekwencją granych nut. Na przykład ruch z pozycji
0.5
do1.5
produkowania nuty1
. Polega to na przyjęciu średniej między pozycjami, a następnie zastosowaniu operacji modulo 4. Średnia bieżąca wzdłuż każdej kolumny jest wykonywana za pomocą splotu 2D .Na koniec program sprawdza, czy jakakolwiek kolumna tablicy nut pokrywa się z danymi wejściowymi.
źródło
Pyth, 43
Pakiet testowy
Jest to prawdopodobnie bardzo gra w golfa, a także nie jest to optymalny algorytm do gry w golfa (spodziewam się, że wyliczenie wszystkich ścieżek będzie krótsze?) ... W każdym razie, jeśli znajdziesz jakiś błąd w algorytmie, daj mi znać, myślę, że powinien działać, ale ja wcześniej się myliłem!
Wyjaśnię mój algorytm, używając przykładowego wejścia
1221
. Program ten pierwszy odwzorowuje cyfry przed ich następców, tak:[[1,2],[2,2],[2,1]]
. Potem robi się ich różnic mod4
(Pyth dostaje wynik odpowiadający znak prawego argumentu%
, więc jest zawsze dodatnia)[3,0,1]
. Następnie wyniki są podzielone na0
i nie2
odejmuje się od każdego z nich[[1],[-1]]
.Teraz, gdy konfiguracja jest zakończona, tworzymy listę
[-1,1,-1...]
i jej negację[1,-1,...]
, obie o tej samej długości co tablica wynikowa z wcześniej. Następnie dla każdej z tych list wykonaj odejmowanie zgodnie z ustaleniami między elementami listy i listą wygenerowaną we wcześniejszym kroku. Następnie, jeśli którykolwiek z wyników zawiera tylko puste listy, generujemy true.źródło
1221221
a1221441
?1221221
jest fałszem i1221441
ogólnie daje prawdę, ale jeśli rozumiem, że chcesz uzyskać wynik po tym kroku w algorytmie? W takim przypadku daje to: od[3, 0, 1, 3, 0, 1]
do[[3], [1, 3], [1]]
i[3, 0, 1, 1, 0, 3]
do[[3], [1, 1], [3]]
. Daj mi znać, jeśli chcesz wyjaśnić coś innego :)[[1], [-1, 1], [-1]]
i[[1], [-1, -1], [1]]
stąd widać, że pierwsza nie ma list, które zmieniają się na przemian-1
i1
podczas gdy druga lista, co daje końcowy wynik. Algorytm jest nieco tępy, ale zasadniczo odwzorowuje zmiany kierunku0
i kierunek+/-1
, a następnie sprawdza, czy nie są wykonywane żadne skoki i czy kierunki mają sens.Matlab,
279180 bajtówCałkiem leniwe rozwiązanie, ale najkrótsze, jakie udało mi się wymyślić. Stworzyłem specjalną matrycę: kiedy kodujesz stan skubaka i ostatni ciąg, który ma być skubany, zwraca wektor, który koduje nową pozycję skubaka i czy poprzedni skubanie było w ogóle możliwe. Teraz po prostu zapętlamy wszystkie nuty z dwóch możliwych pozycji początkowych i sprawdzamy, czy jedna z nich daje odtwarzalną melodię. Prawdopodobnie można grać w golfa o wiele więcej.
Rozszerzone i wyjaśnione źródło:
źródło
ES6,
104100 bajtówEdycja: Zapisano 4 bajty dzięki @DigitalTrauma.
To jest kompletne przepisanie, ponieważ moje poprzednie podejście było wadliwe.
Zaczynam od zredukowania wszystkich serii cyfr do 1 lub 2 w zależności od tego, czy w serii była liczba nieparzysta czy parzysta. Następnie szukam wszystkich nielegalnych kombinacji:
13|24|31|42
(przeciwne strony)3[24]{2}1
jak3221
i3441
są nielegalne4xx2
,1xx3
i2xx4
gdziex
jest albo brakujących cyfr(.).\1
ponieważ rzeczy takie121
są nielegalne (111
zostały zredukowane do1
wcześniejszych)Jeśli nie ma nielegalnych par lub „potrójnych”, to cały ciąg jest legalny (dowód przez indukcję pozostawia się jako ćwiczenie, ponieważ tutaj jest późna noc).
Starałem się uprościć,
3[24]{2}1|1[24]{2}3
stosując negatywne stwierdzenie z wyprzedzeniem, ale okazało się, że tak jest dłużej.źródło
f("1122") => true
@DigitalTraumaf("1221221")
wychodzi zła odpowiedź, więc będę musiał przemyśleć.[24][24]
na(2|4)\1
ale nie przetestowane odpowiednio. Przepraszam za to.[24][24]
w golfa[24]{2}
?JavaScript (ES6), 80 bajtów
Wyjaśnienie
i%4
jest bieżącą pozycją korby:Wcięte i komentowane
Test
źródło
|
działa w tym przypadku?(x.map(...),v)
. Działa, ponieważ tablica, do którejmap
zwracane są dane rzutowane na0
i0|v == v
.Lua ,
146 142 108 162 159 149 144 135 132 118113 113 bajtówZwraca wartość true lub false, biorąc pod uwagę ciąg liczb od 1 do 4. (Nie obsługuje danych ani numerów spoza zakresu.
Po prostu śledzi, jaki był ostatni ruch i sprawdza, czy ruch ten jest odwrotnością ostatniego ruchu (IE, 121 lub 12221), czy też odległość ruchu jest większa niż to możliwe.
EDYCJA 1 :
Zapisano 6 bajtów. Zapomniałem, że
if (int) then
zwraca true, jeśli int jest niezerowe.A zatem:
zmiany w:
Oszczędzono także kilka bajtów poprzez restrukturyzację.
EDYCJA 2 :
Powoli to rozgryzam. Przeczytałem tutaj dokumentację: http://www.lua.org/pil/ A jedną z bardziej przydatnych stron do gry w golfa jest http://www.lua.org/pil/3.3.html
Jest to szczególnie pomocne:
Dla mnie oznacza to, że mogę iść dalej i usunąć moją deklarację dla q ( która początkowo była ustawiona na 0 ), ponieważ będzie ona uważana za „fałszywą”, dopóki nie zostanie ustawiona. Dzięki temu oszczędzam jeszcze kilka bajtów.
Inną rzeczą, o której warto wspomnieć, chociaż jej nie używam, jest to, że jeśli chcesz zamienić wartości w Lua, możesz po prostu zrezygnować
a,b=b,a
z potrzeby tymczasowej zmiennej.EDYCJA 3
Tak więc, dzięki sprytnej rekonstrukcji, a także nowej funkcji, odliczam bajt o 9 więcej.
Najlepszy tryb do odbierania danych wejściowych
Jeśli chcesz czytać listę numerów i wykonywać na nich operacje pojedynczo, możesz użyć:
W porównaniu do alternatywy wykorzystującej string: sub, możesz zobaczyć wartość golfa (lub ogólnego zastosowania):
Restrukturyzacja funkcji lub ciągów
Po drugie, jeśli masz wiele deklaracji w jednym wierszu, a jedna z wartości jest funkcją lub masz warunek, w którym porównujesz liczbę z wynikiem funkcji takiej jak te:
przekształcając go tak, aby nawias zamykający był ostatnim znakiem warunku lub deklaracji, możesz wyciąć znak taki:
Zwracane warunki, które odpowiadają prawdzie lub fałszowi zamiast „prawdy” lub „fałszu”
Znalazłem na poły zabawny sposób, aby jeszcze bardziej zmniejszyć liczbę moich bajtów. Jeśli musisz zwrócić wartość prawda lub fałsz, możesz zwrócić instrukcję, która jest równa prawdzie lub fałszowi, która ma mniej znaków niż same „prawda” lub „fałsz”.
Na przykład porównaj:
Do:
źródło
121
powinien wypisać wartość false.MATL, 49 bajtów (niekonkurencyjny 1 )
1. Odpowiedź (ab) wykorzystuje mniej ścisłe indeksowanie nowszych wersji MATL i nie działałaby w chwili opublikowania tego wyzwania.
Wypróbuj online! .
Widziałem to wyzwanie podczas Best of PPCG 2016 i pomyślałem, że może to wykorzystać mój ulubiony operator :
Lub
diff
w MATLAB / Octave (swobodnie będę używać terminologii MATLAB / Octave w moim objaśnieniu, ponieważ dla ludzi jest łatwiejszy do odczytania). To polecenie oblicza różnicę elementarną w wektorze lub, w tym przypadku, w tablicy znaków.W przypadku tego problemu różnice wykazują ciekawy wzór. Zauważ, że
Dla wzorca różnicy (na razie ignorując
1-4
przejście) oznacza to, żeZaimplementowałem to, znajdując pierwsze zero dla każdej tablicy. Wycinam zero i mnożę wszystkie elementy po nim
-1
. Dla wyniku końcowego oznacza to, że wszystkie elementy muszą mieć ten sam znak. Oczywiście istnieje niewielka kwestia-3
wyrównywania+1
i2
ogólnie bycia niedozwolonym. Rozwiązałem to, biorąc zestaw sumy wyniku[1 -3]
i sprawdzając, czy ma ona rozmiar 2 (tj. Żadne niedozwolone elementy nie „weszły” do zestawu przez łączenie). Powtórz dla[-1 3]
i sprawdź, czy którykolwiek (lub oba, w przypadku danych wejściowych o długości 1) jest prawdziwy.źródło
M
, kiedy ostatnio próbowałem, zadziałało inaczej niż oczekiwano, więc na razie zignorowałem to. Czy słusznie jest powiedzieć, że tak musi być,3M
ponieważ wtedy dostaję wejście nie)
, nie:
aleq
(pomijanie,w
ponieważ nie jest to normalna funkcja)?w
jest pomijany, ponieważ nie jest to normalna funkcja. Normalne funkcje, które nie wymagają wprowadzania danych, również zostałyby pominiętePython (3.5)
160151150 bajtówRozwiązanie rekurencyjne
Bez golfa bez lambda
Obracam wszystkie pudła zamiast korby. Pozycja korby znajduje się między pierwszym a drugim znakiem łańcucha c. Muszę przetestować całą początkową pozycję korby.
Sztuczka służy do obracania sznurka
Zwykły sposób obracania łańcucha w python (
s[i:]+s[:i]
) również wymaga powtórzenia zarówno indeksu, jak i łańcucha. W takim przypadku powielam ciąg i kadruję pierwsze znaki.Przypadki testowe
źródło
3"[i:]) for
.Python 2 , 65 bajtów
Wypróbuj online!
źródło
JavaScript (ES2015),
1109515 bajtów zapisanych przez Neila! Oryginalna wersja bez golfa:
Testy: https://jsbin.com/cuqicajuko/1/edit?js,console
źródło
(s,d)=>(h=s[0],t=s.slice(1),g=t[0],!g||(d?g==h?p(t,-d):g%4==(h-d)%4&&p(t,d):p(s,1)||p(s,-1)))
Kod maszynowy Turinga, 395 bajtów
Wypróbuj online!
Jest to w zasadzie podejście państwowe:
a
,b
,c
, Id
są „stany niezdecydowanych”, które występują tylko na początkuN
,E
,S
, IW
są "postanowił członkowskimi", oczywiście stojąc naN
Północy,E
ast,S
OUtH iW
est.źródło
Czw. 203 bajty
Nie mogę wymyślić, jak grać w golfa dalej.
Jeśli sekwencja nut jest możliwa, wyświetli kierunek zakończenia, w przeciwnym razie wyjście będzie puste.
źródło
Prolog (SWI) , 117 bajtów
Definiuje predykat,
p
który odnosi sukces na wejściach możliwych do gry (podanych jako lista liczb całkowitych), a na wejściach niemożliwych do odtworzenia. Wypróbuj online!Wyjaśnienie
a
określa relację sąsiedztwa między nutąN
a położeniem korbyP
. Definiujemy pozycję p, która będzie pomiędzy nutami p i p + 1 . Zatem pozycja sąsiaduje z nutąN
iffN
(P=N
); lubN=1,P=4
); lub!
), a pozycja równa sięN-1
(P is N-1
).m
bierze listę nut i próbuje wygenerować listę pozycji, które będą odtwarzać te nuty.A
to właśnie zagrana nuta,B
to nuta, która ma zostać odtworzona;X
to bieżąca pozycja korby,Y
to następna pozycja korby. Ruch jest ważny iffa(A,X)
);a(B,X)
);a(B,Y)
); iX\=Y
).Jeśli wszystkie z nich się utrzymują, powtórz. Jeśli uda nam się przejść do jednej nuty (
m([_],_)
), sekwencję nut można zagrać.W przypadku tego pytania zależy nam tylko na tym, czy istnieje sekwencja ruchów, dlatego definiujemy,
p
aby wywoływaćm
i odrzucać wygenerowaną listę pozycji korby.Zobaczyć ungolfed wersji i zweryfikować wszystkie przypadki testowe tutaj .
źródło