Rozważmy gramatykę nad alfabetem { 0
, 1
, ?
, :
} określone przez reguły produkcji
s →
0
┃1
┃0
?
s:
s ┃1
?
s:
s
Biorąc pod uwagę ciąg wygenerowany ze s , przeanalizuj go jako wyrażenie, w którym ?:
jest asocjacyjnie prawostronny (na przykład a?B?X:Y:c?d:e?f:g
oznacza a?(B?X:Y):(c?d:(e?f:g))
) i oceń go za pomocą następującej semantyki:
eval(0) = 0
eval(1) = 1
eval(0?a:b) = eval(b)
eval(1?a:b) = eval(a)
Jeśli wynikiem jest 0 , wypisz pewną stałą wartość; jeśli wyjście wynosi 1 , wypisz inną stałą wartość. Podaj w odpowiedzi wybrane wartości wyjściowe (np. 0
/ 1
Lub False
/ True
).
Przypadki testowe
0 -> 0
1 -> 1
0?0:1 -> 1
0?1:0 -> 0
1?0:1 -> 0
1?1:0 -> 1
0?1?0:1:1 -> 1
1?0?1:1:1 -> 1
1?0:1?0:1?1:1 -> 0
1?1?1:0?1?0:0:0:0 -> 1
1?0:1?0?1:1?1:0:1?1?1:1:1?0:1 -> 0
1?1?1:0?0?1:1:0?1:0:1?1?0?0:0:1?1:0:0?1?0:1:1?0:1 -> 1
0?0?1?0?0:1:0?0:0:0?0?1:1:1?0:1:0?0?0?1:0:0?1:1:1?1?0:1:1 -> 0
Zasady
- Nie możesz używać wbudowanych języków, które interpretują ciągi znaków jako kod w niektórych językach programowania i uruchamiają je (np. JavaScript / Perl / Ruby / Python
eval
). - To powiedziawszy, twój kod w rzeczywistości nie musi analizować, a następnie oceniać łańcuch wejściowy. Możesz zastosować dowolne podejście, które osiąga równoważne wyniki i nie narusza poprzedniej zasady.
- Twój program zostanie porównany z
perl -le 'print eval<>'
. - Najkrótszy kod (w bajtach) wygrywa.
S → T | T ? S : S
,T → 0 | 1
usuwając potrzebę porozmawiania o skojarzeń?Odpowiedzi:
GolfScript, 21 bajtów
Wyjściowe
0
lub1
. Zakłada się, że wejście ma jedną końcową nową linię. Użycie~
(które ocenia łańcuchy) pozwoliłoby zaoszczędzić bajt:Jest to oparte na http://golf.shinh.org/reveal.rb?The+B+Programming+Language/tails_1462638030&gs .
źródło
Siatkówka , 23 bajty
Wypróbuj online! (Pierwszy wiersz włącza pakiet testowy oddzielony od linii).
Wyjaśnienie
W rzeczywistości jest to dość proste. Dane wejściowe są redukowane do wyniku przez wielokrotne (
+
) ocenianie trójek, które zawierają tylko literały. Aby upewnić się, że jest to wykonane w sposób asocjatywny, szukamy dopasowań od prawej do lewej (r
) i zastępujemy tylko ostatnie znalezione dopasowanie (-1=
).Wyrażenie regularne albo dopasowuje
0\?.:
i usuwa je (pozostawiając tylko rzeczy po:
) lub1\?.:.
zastępuje je wartością po?
.źródło
1
dopasowania st zamiast-1
st?Haskell,
106 101 100 9083 bajtówW dużej mierze zależy to od możliwości dopasowania wzoru przez Haskell. Przede wszystkim odwracamy ciąg tak, że możemy po prostu wyszukać po raz pierwszy
b:a?x
(co normalnie brzmiałoby jakox?a:b
) i zastąpić go jego wartością. To automatycznie zapewnia właściwe połączenie . Tutaj wykorzystujemyx:xs
wzór. Tak właśnie działa funkcjaf
. Następnie zasadniczo stosujemyf
dane wyjściowe w kółko, dopóki nie zostanie nam jedna liczba (0 lub 1).Dzięki @Lynn za 12 bajtów!
źródło
Brainfuck,
826463 bajtyDane wyjściowe są
\xff
dla0
i\x00
dla1
. Implementacja „brainfuck” musi pozwolić na przejście na lewo od komórki początkowej.Zasadniczo ten wykorzystuje takie samo podejście jak xsot za Pythona odpowiedź , ale rozgałęzienie jest chyba trudniejsze do naśladowania w porównaniu z moim początkowym składania 82-bajtowy:
(W tym rozwiązaniu dane wyjściowe są
\xfe
dla0
i\xff
dla1
, a szersza kompatybilność jest osiągana, gdy dane wejściowe kończą się nową linią.)Jeśli nie możesz niepokoić się analizą rozwiązania xsot, pomysł jest następujący: Przejdź od lewej do prawej. Jeśli widzisz,
1?
łapczywie go odrzuć. Jeśli widzisz,0?
odrzuć wszystko między tym a odpowiednim:
. Gdy?
nie pojawia się jako drugi znak, przestań zapętlać i wydrukuj pierwszy znak pozostałego ciągu.Tak więc 82-bajtowe rozwiązanie faktycznie bardzo dokładnie odzwierciedla ten schemat. Wewnętrzna pętla obsługuje się
0?
, podobnie jak wewnętrzna pętla xsot. Należy zachować ostrożność, aby wejść do głównej pętli bez sprawdzania znaków wejściowych; tzn. chcemy sprawdzić, czy drugi znak znajduje się?
tylko raz na końcu głównej pętli, a nie także na początku przed wejściem do głównej pętli.63-bajtowe rozwiązanie zasadniczo łączy wewnętrzną i zewnętrzną pętlę w jedną, co, jak podejrzewałem, było możliwe, biorąc pod uwagę podobieństwo między tymi pętlami. Układ pamięci w głównej pętli można opisać jako:
gdzie
[x]
oznacza bieżącą komórkę -s
zaczyna się jako fałszywa niezerowa wartość, która po prostu wskazuje, że nadal zapętlamy, i jest natychmiast zastępowana znakiem wejściowym (albo0
lub1
).d
Komórka posiada głębokość (ujemny) w przypadku jesteśmy w środku0?
, inaczej0
.c
Będzie albo?
albo:
albo nowej linii lub EOF.Po aktualizacji
s
ic
obsługujemy0?
sprawę, odpowiednio aktualizującd
i dostosowując wskaźnik, w przeciwnym razie używamy bieżącej wartościc
jako wartościd
w następnej iteracji lub zatrzymujemy się, jeśli skończymy.źródło
Python 2,
76747372 bajtyZ danymi wejściowymi jako literał ciągów, aby uniknąć
raw_
.Wyjście jest
0
lub1
następuje<built-in function id>
.źródło
3>>int(c)
`id`
sztuczka…! Dobra robota :)Python 2, 89 bajtów
Dane wejściowe są traktowane jako literał łańcuchowy.
źródło
Grime ,
3431 bajtówDrukuje
1
dla prawdziwych danych wejściowych i0
dla fałszywych. Wypróbuj online! W ostatnim przypadku testowym zabrakło pamięci w TIO.Wyjaśnienie
Prawo-asocjatywność zasadniczo oznacza, że
a?b:c
,a
jest zawsze albo0
albo1
, nigdy dłuższe wypowiedzi. Po prostu rekurencyjnie zdefiniuję wzór, który pasuje do takiego prawdziwego wyrażenia, i sprawdzę dane wejściowe w stosunku do niego. Nie jest również konieczne sprawdzanie, czy każdy:
jest naprawdę a:
, jeśli wszystkie?
s są sprawdzane: na wejściu znajduje się równa liczba?
si:
si, a jeśli niektóre?
są niepoprawnie sklasyfikowane jako:
, odpowiadające im elementy:
nie pasują, a dopasowanie Grime'a silnik cofnie się.źródło
Haskell,
79 71 70 62 6056 bajtówEdycja: Dzięki @Zgarb za 3 bajty i @nimi za 4 bajty!
Jest to podejście rekurencyjne,
które w pewnym stopniu narusza regułę wyjścia „jakaś stała wartość”. Edycja: Pozbycie się krotek nie tylko oszczędza 8 bajtów, ale także daje ładniejszy wynik:"0"
lub"1"
.Wersja bez golfa:
Jak to działa? Funkcja przemierza niejawny drzewo wyrażeń
eval
i zwraca krotkę formularza
(result, rest)
.Pierwszy wzór
(x:'?':r1)
pasujex
do'1'
ir1
do"0?0:1:0?1:0"
. Rekurencyjnie stosuje sięeval
dor1
oceny podwyrażenia0?0:1
i zwraca(0,":0?1:0")
. Dopasowanie tego do wzoru(a,':':r2)
dajea=0
ir2=0?1:0
. Ta podformuła jest również poddawana rekurencyjnej ocenie, abyb='0'
ir3=""
. Sprawdź, czyx
jest'1'
czy'0'
i powrót albo(a, r3)
albo(b, r3)
.źródło
x>'0'
działałby zamiastx=='1'
?':'
przez_
.:
. Dzięki jeszcze raz!if .. then .. else
zlast$e s:[a:tail(e s)|x>'0']
.JavaScript (ES6), 53 bajty
Zwraca
0
lub1
dla poprawnych danych wejściowych; zawiesza się z powodu nieprawidłowego wejścia. Objaśnienie: ponieważ w JavaScript JavaScript odwracanie łańcucha jest niewygodne, moja pierwsza 71-bajtowa próba?
polegała na użyciu negatywnego spojrzenia w przód, które w przeciwnym razie zakłóciłoby asocjatywność:Ponieważ było to trochę za długo, zastanawiałem się, czy mogę poprawić sprawy, włączając proces decyzyjny do wyrażenia regularnego. Jak się okazało, nie był to natychmiastowy sukces, ponieważ zajął również 71 bajtów:
Wtedy przyszło mi to do głowy
0?0:
i0?1:
są zawsze nie-OPS, bez troski o skojarzeń. To zaoszczędziło mi prawie 25%.źródło
f=
. Nie sprawdziłem, czy twoja liczba bajtów uwzględnia to, czy nie.Perl, 32 + 1 (
-p
flaga) = 33 bajtyPełny kredyt @Mitch Swartch , ponieważ jego rozwiązanie było o 14 bajtów krótsze niż moje!
Dziękujemy również @Neil, który zaproponował rozwiązanie o 1 bajt dłużej niż Mitch.
Potrzebuje
-p
flagi, a także-M5.010
lub-E
uruchomić. Na przykład :Objaśnienia : Zasadniczo redukuje bloki
a?b:c
(zaczynając od końca, aby upewnić się, że nie?
następuje) dob
lub wc
zależności od prawdziwościa
, w kółko, aż łańcuch zawiera tylko1
lub0
.źródło
-
nie liczy do twojego wyniku? Hmm. Ciekawe ... Dobra odpowiedź!perl -e '<code>'
dodając w ten sposóbp
tylko 1 bajtperl -pe '<code>'
.?
udało mi się zmniejszyć to do 34 bajtów w ten sposób.s/.*\K(1\?(.)..|0\?..)/\2/&&redo
Python 3,
9369 bajtówWejście jest ciąg jako listę znaków, wyjście jest albo
"0"
albo"1"
Wersja bez golfa:
Kolejna próba, ale ze znacznie większą liczbą bajtów:
źródło
def f(s):x=s.pop(0);return[]<s<s.pop(0)>'>'and(f(s),f(s))[x<'1']or x
, a dla Pythona 3 z małą odległością edytowania do twojej, jestdef f(s):z=s.pop;r=z(0);return s and':'<z(0)and(f(s),f(s))[r<'1']or r
.SED,
75 74 68(40 + 1 dla -r) 41źródło
(.*)
i dodanie dodatkowego terminu zastępczego.\3
zamiast\2
. Możesz także dołączyć do linii,;
aby uzyskać:;s/(.*)(1\?(.):.|0\?.:)/\1\3/;t
.\3
więc oznacza to, że przypadkowo skopiowałem poprzednią wersję. Wiem o średnikach. Ale fuj, dlaczego miałbyś chcieć używać średników.Narzędzia Bash + GNU, 42
Podobny pomysł do większości innych odpowiedzi pasujących do wzorca.
Ideone .
źródło
0
skrzynce, co oszczędza 5 bajtów.