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:goznacza 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/ 1Lub 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.

GolfScript, 21 bajtów

2/-1%{)2%{0`=@@if}*}/

Wyjściowe 0lub 1. Zakłada się, że wejście ma jedną końcową nową linię. Użycie ~(które ocenia łańcuchy) pozwoliłoby zaoszczędzić bajt:

2/-1%{)2%{~!@@if}*}/

Jest to oparte na http://golf.shinh.org/reveal.rb?The+B+Programming+Language/tails_1462638030&gs .

Siatkówka , 23 bajty

r-1=+`0\?.:|1\?(.):.
$1

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 :) lub 1\?.:.zastępuje je wartością po ?.

Haskell, 106 101 100 90 83 bajtów

W 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 jako x?a:b) i zastąpić go jego wartością. To automatycznie zapewnia właściwe połączenie . Tutaj wykorzystujemy x:xswzór. Tak właśnie działa funkcja f. Następnie zasadniczo stosujemy fdane wyjściowe w kółko, dopóki nie zostanie nam jedna liczba (0 lub 1).

Dzięki @Lynn za 12 bajtów!

f(b:':':a:'?':x:l)|x>'0'=a:l|1>0=b:l
f(x:l)=x:f l
f x=x
until((<2).length)f.reverse

Brainfuck, 82 64 63 bajty

+
[
  ,>>,>
  +++++++[<---<<-[------>>]<-]
  <<
  [
    ->[<++>[+]]
  ]
  +>[>>]
  <<<-
]
<.

Dane wyjściowe są \xffdla 0i \x00dla 1. 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ą \xfedla 0i \xffdla 1, 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:

[s] d c

gdzie [x]oznacza bieżącą komórkę - szaczyna się jako fałszywa niezerowa wartość, która po prostu wskazuje, że nadal zapętlamy, i jest natychmiast zastępowana znakiem wejściowym (albo 0lub 1). dKomórka posiada głębokość (ujemny) w przypadku jesteśmy w środku 0?, inaczej 0. cBędzie albo ?albo :albo nowej linii lub EOF.

Po aktualizacji si cobsługujemy 0?sprawę, odpowiednio aktualizując di dostosowując wskaźnik, w przeciwnym razie używamy bieżącej wartości cjako wartości dw następnej iteracji lub zatrzymujemy się, jeśli skończymy.

Python 2, 76 74 73 72 bajty

a=`id`
for c in input()[::-1]:a=(c+a,a[ord(c)*7%9]+a[4:])[a>'?']
print a

Z danymi wejściowymi jako literał ciągów, aby uniknąć raw_.

Wyjście jest 0lub 1następuje <built-in function id>.

Python 2, 89 bajtów

s=input()
while'?'<=s[1:]:
 n=s<'1'
 while n:s=s[2:];n+=-(s[1]<'?')|1
 s=s[2:]
print s[0]

Dane wejściowe są traktowane jako literał łańcuchowy.

Grime , 34 31 bajtów

E=d|d\?E.E
e`\1|\1\?_.E|\0\?E._

Drukuje 1dla prawdziwych danych wejściowych i 0dla 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, ajest zawsze albo 0albo 1, 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ę.

E=d|d\?E.E
E=                      Define nonterminal E (for "expression") as
  d|                     a digit, OR
    d                    a digit,
     \?                  a literal ?,
       E                 a match of E,
        .                any character (will match a :), and
         E               another match of E.
e`\1|\1\?_.E|\0\?E._
e`                      Match entire input against this pattern (truthy expression):
  \1|                    a literal 1, OR
     \1\?                a literal 1?,
         _               a recursive match of truthy expression,
          .              any character (will match a :), and
           E|            any expression, OR
             \0\?E._     the same, but with 0 in front, and _ and E swapped.

Haskell, 79 71 70 62 60 56 bajtów

Edycja: Dzięki @Zgarb za 3 bajty i @nimi za 4 bajty!

e(x:'?':r)|a:_:s<-e r=last$e s:[a:tail(e s)|x>'0']
e x=x

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:

eval (x:'?':r1) = if x=='1' then (a, r3) else (b, r3)
    where (a,':':r2) = eval r1
          (b, r3)    = eval r2
eval (x:r) = (x,r)

Jak to działa? Funkcja przemierza niejawny drzewo wyrażeń
eval

eval 1?0?0:1:0?1:0 -> eval 1?          :
                             eval 0?0:1 eval 0?1:0

i zwraca krotkę formularza (result, rest).
Pierwszy wzór (x:'?':r1)pasuje xdo '1'i r1do "0?0:1:0?1:0". Rekurencyjnie stosuje się evaldo r1oceny podwyrażenia 0?0:1i zwraca (0,":0?1:0"). Dopasowanie tego do wzoru (a,':':r2)daje a=0i r2=0?1:0. Ta podformuła jest również poddawana rekurencyjnej ocenie, aby b='0'i r3="". Sprawdź, czy xjest '1'czy '0'i powrót albo (a, r3)albo (b, r3).

JavaScript (ES6), 53 bajty

f=s=>s[1]?f(s.replace(/0\?.:|1\?(.):.(?!\?)/,"$1")):s

Zwraca 0lub 1dla 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ść:

f=s=>s[1]?f(s.replace(/(.)\?(.):(.)(?!\?)/,(_,a,b,c)=>+a?b:c)):s

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:

f=s=>s[1]?f(s.replace(/0\?.:(.)(?!\?)|1\?(.):.(?!\?)/,"$1$2")):s

Wtedy przyszło mi to do głowy 0?0: i 0?1:są zawsze nie-OPS, bez troski o skojarzeń. To zaoszczędziło mi prawie 25%.

Perl, 32 + 1 ( -pflaga) = 33 bajty

Peł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.

s/.*\K(0\?..|1\?(.)..)/\2/&&redo

Potrzebuje -pflagi, a także -M5.010lub -Euruchomić. Na przykład :

perl -pE 's/.*\K(0\?..|1\?(.)..)/\2/&&redo' <<< "0
0?0:1
0?1?0:1:1
1?0:1?0?1:1?1:0:1?1?1:1:1?0: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"

Objaśnienia : Zasadniczo redukuje bloki a?b:c(zaczynając od końca, aby upewnić się, że nie ?następuje) do blub w czależności od prawdziwości a, w kółko, aż łańcuch zawiera tylko 1lub 0.

Python 3, 93 69 bajtów

def f(s):z=s.pop;r=z(0);return s and':'<z(0)and(f(s),f(s))[r<'1']or r

Wejście jest ciąg jako listę znaków, wyjście jest albo "0"albo"1"

>>>f(list("0?0:1"))
<<<"1"

Wersja bez golfa:

def parse(s):
    predicate = s.pop(0)
    if s and s.pop(0) == '?':
        left, right = parse(s), parse(s)
        if predicate == '0':
            return right
        return left
    return predicate

Kolejna próba, ale ze znacznie większą liczbą bajtów:

i=input()[::-1]
a=[i[0]]
for o,z in zip(i[1::2],i[2::2]):a+=[z]if o<'?' else[[a.pop(),a.pop()][z>'0']]
print(a[0])

SED, 75 74 68 (40 + 1 dla -r) 41

:
s,(.*)1\?(.):.,\1\2,
s,(.*)0\?.:,\1,
t

Narzędzia Bash + GNU, 42

rev|sed -r ':
s/(.):.\?0|.:(.)\?1/\1\2/
t'

Podobny pomysł do większości innych odpowiedzi pasujących do wzorca.

Ideone .