Oceń wyrażenie operatorów trójskładnikowych

29

Rozważmy gramatykę nad alfabetem { 0, 1, ?, :} określone przez reguły produkcji

s → 010 ?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.
Lynn
źródło
Co powiesz na użycie wbudowanych języków, takich jak eval, które interpretują ciągi znaków jako kod $ my_language po radykalnej zmianie ciągu?
Adám
Co z wbudowanymi, które interpretują ciągi znaków jako kod $ some_other_language ?
Mego
@ Adám To byłoby niedozwolone, przepraszam.
Lynn
@Mego Hmm, tam jest trywialna okazja oszukiwania, więc rozszerzyłem zasadę, aby objąć wszystkie takie wbudowane elementy.
Lynn
1
W świetle przypadków testowych Martina, być może byłoby prościej zdefiniować gramatyki S → T | T ? S : S, T → 0 | 1usuwając potrzebę porozmawiania o skojarzeń?
Peter Taylor

Odpowiedzi:

17

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 ?.

Martin Ender
źródło
Jeśli wyrażenie regularne zaczyna się od prawej, to czy nie powinieneś przetworzyć 1dopasowania st zamiast -1st?
Leaky Nun
@LeakyNun Niestety myślę, że cofam mecze przed zastosowaniem limitu.
Martin Ender
10

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
wada
źródło
8

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.

Mitch Schwartz
źródło
7

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

Mitch Schwartz
źródło
1
Haha, właśnie przeczytałem twoją odpowiedź na b lang i miałem zamiar opublikować prawie identyczną odpowiedź! Oto dodatkowa optymalizacja:3>>int(c)
xsot 15.08.16
Chcesz wyjaśnić, jak to działa? Wygląda naprawdę schludnie
WorldSEnder
@WorldSEnder Myślę, że jest to rozwiązanie, które może być trudne do znalezienia, ale łatwe do zrozumienia, gdy je zobaczysz. Przebiega przez ciąg znaków do tyłu i wielokrotnie przetwarza warunek skrajnie prawy, podobnie jak inne solwery.
Mitch Schwartz
Ta `id`sztuczka…! Dobra robota :)
Lynn,
5

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.

xsot
źródło
5

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.
Zgarb
źródło
5

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).

Laikoni
źródło
1
Niezłe podejście! Czy x>'0'działałby zamiast x=='1'?
Zgarb
Dzięki, nie myślałem o tym podczas zajmowania się znakami.
Laikoni,
1
I pomyśleć można również zastąpić ':'przez _.
Zgarb
Tak, wtedy kod działa nawet dla dowolnych ograniczników zamiast po prostu :. Dzięki jeszcze raz!
Laikoni
1
Miły! Można wymienić if .. then .. elsez last$e s:[a:tail(e s)|x>'0'].
nimi
3

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%.

Neil
źródło
Brakuje twojego kodu na górze f=. Nie sprawdziłem, czy twoja liczba bajtów uwzględnia to, czy nie.
Patrick Roberts,
@PatrickRoberts Robię to na zawsze, ponieważ kopiuję z dziennika, który pokazuje tylko wynik przypisania (co oczywiście wystarcza do nierekurencyjnych funkcji).
Neil
@Neil można kopiować z dziennika wejściowego zamiast wyjściowego
tylko ASCII
@MarsUltor Dane wejściowe dziennika zawierają monit, który muszę następnie pamiętać, aby wykluczyć. Jest to niezręczny dodatkowy krok dla funkcji nierekurencyjnych, dlatego domyślnie kopiuję z danych wyjściowych.
Neil,
3

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.

Dada
źródło
Czy to się -nie liczy do twojego wyniku? Hmm. Ciekawe ... Dobra odpowiedź!
MayorMonty
@MayorMonty W przypadku 1-liniowej linii można ją wywołać w wierszu polecenia, perl -e '<code>'dodając w ten sposób ptylko 1 bajt perl -pe '<code>'.
Neil
@Neil Ahh, to ma sens
MayorMonty
W rzeczywistości nie musisz odwracać łańcucha, możesz po prostu przeczekać, a ?udało mi się zmniejszyć to do 34 bajtów w ten sposób.
Neil
Oto 32 + 1:s/.*\K(1\?(.)..|0\?..)/\2/&&redo
Mitch Schwartz
2

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])
WorldSEnder
źródło
Twoja odpowiedź może być funkcją - możesz usunąć drugą linię.
Lynn
Jest to wyraźnie niesprawdzone, ponieważ nie przechodzi przypadków testowych, a wersja niestosowana daje błąd w czasie wykonywania. Twój podstawowy pomysł jest jednak dobry. Z pewnymi poprawkami dostaję 68 w Pythonie 2 i 69 w Pythonie 3.
Mitch Schwartz
1
Cóż, myślę, że sensowniej jest dać ci odpowiedź niż edytować ją na własną (ponieważ nie myślałem o takim podejściu, zanim zobaczyłem twoją odpowiedź) lub usiąść i czekać, aż twoja odpowiedź jest błędna. Oto 68, o których wspomniałem 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, jest def f(s):z=s.pop;r=z(0);return s and':'<z(0)and(f(s),f(s))[r<'1']or r.
Mitch Schwartz,
Dzięki @MitchSchwartz, prawie parsuj z prawej, zamiast z lewej, gotcha
WorldSEnder
1
Poza tym, w lewo zamiast w prawo, ~~~
WorldSEnder
1

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

:
s,(.*)1\?(.):.,\1\2,
s,(.*)0\?.:,\1,
t
Riley
źródło
Prawdopodobnie możesz to ograniczyć za pomocą sztuczki @ MitchSchwartz w jego komentarzu , chociaż może być konieczne użycie (.*)i dodanie dodatkowego terminu zastępczego.
Neil,
@Neil, możesz mieć rację, ale nie mogę wymyślić, jak to zrobić.
Riley,
Napisałem to na czacie, ponieważ formatowanie komentarza może być mylące: chat.stackexchange.com/transcript/message/31709640#31709640
Mitch Schwartz
@MitchSchwartz Heh, puste etykiety działają? Ale myślę, że miałeś na myśli \3zamiast \2. Możesz także dołączyć do linii, ;aby uzyskać :;s/(.*)(1\?(.):.|0\?.:)/\1\3/;t.
Neil,
@Neil miałem, \3więc oznacza to, że przypadkowo skopiowałem poprzednią wersję. Wiem o średnikach. Ale fuj, dlaczego miałbyś chcieć używać średników.
Mitch Schwartz
0

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 .

Cyfrowa trauma
źródło
Nie musisz przechwytywać pierwszego znaku w 0skrzynce, co oszczędza 5 bajtów.
Neil