Рассмотрим грамматику над алфавитом { 0, 1, ?, :} определяется правилом производства

s → 0┃ 1┃ 0 ?s :s ┃ 1 ?s :s

Получив строку, сгенерированную из s , проанализируйте ее как выражение, где ?:ассоциативно справа (например, a?B?X:Y:c?d:e?f:gозначает a?(B?X:Y):(c?d:(e?f:g))), и оцените ее с помощью следующей семантики:

eval(0) = 0
eval(1) = 1
eval(0?a:b) = eval(b)
eval(1?a:b) = eval(a)

Если результат равен 0 , выведите некоторое фиксированное значение; если вывод равен 1 , выведите другое фиксированное значение. Укажите выбранные выходные значения (например, 0/ 1или False/ True) в своем ответе.

Контрольные примеры

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

правила

• Вы не можете использовать встроенные языковые модули, которые интерпретируют строки как код в каком-либо языке программирования и запускают его (например, JavaScript / Perl / Ruby / Python eval).
• Тем не менее, ваш код на самом деле не должен анализировать и затем оценивать входную строку. Вы можете использовать любой подход, чтобы получить эквивалентные результаты и не нарушать предыдущее правило.
• Ваша программа будет проверена perl -le 'print eval<>'.
• Самый короткий код (в байтах) выигрывает.

GolfScript, 21 байт

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

Это выводы 0или 1. Предполагается, что вход имеет одну завершающую новую строку. Использование ~(которое оценивает строки) позволит сохранить байт:

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

Это основано на http://golf.shinh.org/reveal.rb?The+B+Programming+Language/tails_1462638030&gs .

Сетчатка , 23 байта

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

Попробуйте онлайн! (Первая строка включает набор тестов, разделенных переводом строки.)

объяснение

Это довольно просто на самом деле. Ввод сводится к результату путем многократного ( +) вычисления троичных символов, содержащих только литералы. Чтобы убедиться, что это сделано справа ассоциативно, мы ищем совпадения справа налево ( r) и заменяем только последнее найденное совпадение ( -1=).

Само регулярное выражение либо сопоставляет 0\?.:и удаляет его (оставляя только материал после :), либо 1\?.:.заменяет его значением после ?.

Haskell, 106 101 100 90 83 байта

Это в значительной степени зависит от возможностей сопоставления с образцом в Haskell. Прежде всего, мы переворачиваем строку так, что мы можем просто выполнить поиск для первого вхождения b:a?x(который обычно читается как x?a:b) и заменить ее значением. Это автоматически обеспечивает правильную ассоциативность . Здесь мы используем x:xsшаблон. Это то, что fделает функция . Затем мы в основном применяем fк его выводу снова и снова, пока у нас не останется ни одного числа (0 или 1).

Спасибо @Lynn за 12 байтов!

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 байта

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

Выход \xffдля 0и \x00для 1. Реализация мозгового перста должна позволять идти налево от стартовой ячейки.

Это существенно использует тот же подход , как Python xsot в ответ , но ветвление, вероятно , труднее следовать по сравнению с моим первоначальным представлением 82 байт:

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

(Для этого решения выходные данные предназначены \xfeдля 0и \xffдля 1, и более широкая совместимость достигается, когда ввод заканчивается новой строкой.)

Если вам не мешает проанализировать решение xsot, идея заключается в следующем: действуйте слева направо. Если вы видите, 1?то жадно откажитесь от него. Если вы видите, 0?тогда отбросьте все между этим и соответствующим :. Если ?второй символ не отображается, прекратите цикл и напечатайте первый символ оставшейся строки.

Таким образом, 82-байтовое решение фактически очень близко отражает эту схему. Внутренний цикл обрабатывает 0?, как внутренний цикл xsot. Некоторое внимание уделяется тому, чтобы войти в основной цикл без проверки любых вводимых символов; т.е. мы хотим проверить, находится ли второй символ ?только один раз в конце основного цикла, а не также в начале перед входом в основной цикл.

63-байтовое решение по существу объединяет внутренние и внешние циклы в один, что, как я подозревал, было возможно, учитывая сходство между этими циклами. Схема памяти в основном цикле может быть описана как:

[s] d c

где [x]означает текущую ячейку - sначинается как фиктивное ненулевое значение, которое просто указывает, что мы все еще выполняем цикл, и немедленно перезаписывается вводимым символом (или, 0или 1). dКлетка удерживает (отрицательную) глубину в случае , если мы находимся в середине 0?, в противном случае 0. Это cбудет либо ?либо, :либо перевод строки или EOF.

После обновления sи cмы обрабатываем 0?регистр, соответственно обновляя dи корректируя указатель, в противном случае мы используем текущее значение в cкачестве значения dна следующей итерации или остановим, если мы закончили.

Python 2, 76 74 73 72 байта

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

С вводом в виде строкового литерала, чтобы избежать raw_.

Вывод 0или 1после <built-in function id>.

Python 2, 89 байт

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

Ввод принимается как строковый литерал.

Грязь , 34 31 байт

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

Отпечатки 1для правдивых входов и 0ложных. Попробуйте онлайн! К сожалению, в последнем тесте на TIO не хватает памяти.

объяснение

Право-ассоциативность по сути означает, что в a?b:c, aвсегда либо, 0либо 1никогда более длинное выражение. Я просто рекурсивно определю шаблон, который соответствует истинному выражению, подобному этому, и проверю входные данные по нему. Также нет необходимости проверять, что каждое :действительно является a :, если все ?s проверены: во входных данных есть равное количество ?s и :s, и если некоторые из ?них неправильно классифицированы как a :, соответствующее :не будет соответствовать, и соответствие Грайма двигатель будет возвращаться назад.

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 байт

Редактировать: Спасибо @Zgarb за 3 байта и @nimi за 4 байта!

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

Это рекурсивный подход, который несколько нарушает правило вывода с некоторым фиксированным значением . Редактирование: избавление от кортежей не только экономит 8 байтов, но также дает более хороший результат: "0"или "1".

Безголовая версия:

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)

Как это работает? Функция пересекает неявное дерево выражений
eval

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

и возвращает кортеж формы (result, rest).
Первый шаблон (x:'?':r1)совпадает xс '1'и r1с "0?0:1:0?1:0". Рекурсивное применение evalк r1вычисляет подвыражение 0?0:1и возвращает (0,":0?1:0"). Соответствие этому образцу (a,':':r2)дает a=0и r2=0?1:0. Эта под формула также рекурсивно оценивается так, что b='0'и r3="". Проверьте, если xесть '1'или '0'и верните либо (a, r3)или (b, r3).

JavaScript (ES6), 53 байта

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

Возвращает 0или 1для правильного ввода; зависает для неверного ввода. Объяснение: поскольку в JavaScript изменение строки неудобно, моя первая попытка в 71 байт сработала с использованием отрицательного предвкушения для a, ?которое в противном случае нарушило бы ассоциативность:

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

Поскольку это было довольно долго, я задавался вопросом, могу ли я улучшить положение дел, включив принятие решений в регулярное выражение. Как оказалось, это не был немедленный успех, так как он также занимал 71 байт:

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

Тогда мне пришло в голову, что 0?0:и 0?1:всегда бездельники, не заботясь об ассоциативности. Это спасло меня почти на 25%.

Perl, 32 + 1 ( -pфлаг) = 33 байта

Полная заслуга @Mitch Swartch , поскольку его решение было на 14 байт короче моего!
Спасибо также @Neil, который предложил решение на 1 байт длиннее, чем Митч.

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

Необходимо -pпометить, как -M5.010или -Eзапустить. Например :

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"

Пояснения : Это в основном уменьшает блоки a?b:c(начиная с конца, чтобы убедиться, что не ?следует) в bили в cзависимости от истинности a, снова и снова, пока строка не содержит только 1или 0.

Python 3, 93 69 байт

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

Ввод является строка в виде списка символов, выход либо "0"или"1"

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

Безголовая версия:

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

Еще одна попытка, но со значительно большим количеством байтов:

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

САС, 75 74 68 (40 + 1 для -r) 41

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

Утилиты Bash + GNU, 42

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

Подобная идея для большинства других совпавших по шаблону ответов.

Ideone .