Проверить программу Brainfuck

17

Еще одна проблема разбора Brainfuck, но на этот раз ... другая.

Вы работаете в Infinite Monkeys Incorporated, компании, производящей программы Brainfuck, для решения различных интересных задач (случайно, не менее - в конце концов, компания делает случайные программы). Тем не менее, кажется, что ваши быстрые машины Тьюринга, которые выполняют только Brainfuck, имеют небольшую и дорогую проблему с синтаксическими ошибками - одна проблема, и компьютер взрывается. Вероятно, это недостаток дизайна, но никто не удосужился выяснить, почему это происходит.

Поскольку машины Тьюринга (особенно быстрые) дороги (в конце концов, они имеют бесконечное ОЗУ, которое стоит), было бы лучше убедиться, что в программе нет синтаксических ошибок перед выполнением кода. Ваша компания собирается запустить много кода, поэтому ручная проверка не будет работать. Напишите программу, которая читает STDIN для кода Brainfuck и завершает работу со значением состояния выхода, отличным от 0 (ошибка), если в программе есть какая-либо синтаксическая ошибка (например, ]это синтаксическая ошибка, потому что нет соответствия [). Выход с состоянием выхода, установленным на 0, если программа полностью в порядке.

Убедитесь, что ваша программа правильно замечает ошибки, связанные с []. Вы бы не хотели, чтобы взорвался другой компьютер? Да, и убедитесь, что оно максимально короткое - ваш начальник платит за короткие программы (потому что он считает, что они быстрые или что-то в этом роде). О, и вам не нужно кодировать в Brainfuck (на самом деле, вы не можете, потому что Brainfuck не поддерживает коды выхода) - ваш код будет запускаться на обычном компьютере.

Итак, как вы видите, ваша задача - проверить, является ли программа Brainfuck «действительной» (с парными []символами). Обратите внимание, что в программах Brainfuck могут быть другие символы [], поэтому не отказывайтесь от программы только потому, что в ней есть другие команды. Наименьший код выигрывает, но, вероятно, вам все равно будет важнее голосование против.

Конрад Боровски
источник
1
А как насчет языков, которые не позволяют устанавливать код завершения процесса?
Кендал Фрей
1
@KendallFrey: просто, используйте что-то еще. Или в GolfScript, вставьте код Ruby. Возможно, это блокирует некоторые эзотерические языки программирования, но хорошо ...
Конрад Боровски
1
Можно ли в случае ошибки установить код ошибки, отличный от 1 (если, конечно, он не равен 0)?
Маринус
@marinus: Я не знаю, почему ты этого хочешь, но я думаю, что все в порядке.
Конрад Боровски
@ GlitchMr: потому что тогда я могу использовать GCD(a,b)вместо 0 != a || b.
Маринус

Ответы:

6

GolfScript, 18 символов

.{[]`?)},~](`91?./

Этот код успешно выполняется с кодом выхода 0 (и выводит часть мусора в стандартный вывод), если квадратные скобки во входных данных сбалансированы. Если это не так, происходит сбой с ненулевым кодом выхода и выводится сообщение об ошибке в stderr, например:

(eval):2:in `/': divided by 0 (ZeroDivisionError)

или

(eval):1:in `initialize': undefined method `ginspect' for nil:NilClass (NoMethodError)

Поскольку в запросе ничего не сказано о выводе в stdout / stderr, я полагаю, что это подходит. В любом случае вы всегда можете перенаправить их на /dev/null.

Объяснение:

Код {[]`?)},удаляет из входных данных все, кроме квадратных скобок, и результат ~оценивается как код GolfScript. Сложность в том, что несбалансированные скобки совершенно законны в GolfScript (и, действительно, мой код содержит одну!), Поэтому нам нужен какой-то другой способ вызвать сбой кода.

Хитрость, которую я использую, заключается в том, чтобы оставить копию ввода в нижней части стека, собрать весь стек в массив (используя несбалансированный ]) и сдвинуть первый элемент. На этом этапе могут произойти три вещи:

  • Если ввод заканчивается незакрытым [, попытка сдвинуть элемент с пустого массива приведет к сбою интерпретатора (что, в данном случае, именно то, что мы хотим!)
  • Если скобки на входе были сбалансированы, смещенный элемент будет исходной строкой ввода.
  • В противном случае (если вход был закрыт ]или закрыт [), это будет массив.

Моя первоначальная запись из 14 символов сравнивала смещенное значение со строкой, которая вылетала бы, если бы это был вложенный массив. К сожалению, оказывается, что сравнение плоского (или, в частности, пустого) массива со строкой также допустимо в GolfScript, поэтому мне пришлось переключиться на такт.

Вместо этого в моем текущем представлении используется метод очень грубой силы, чтобы отличить массивы от строк: он выявляет их и пытается найти первое вхождение [(код ASCII 91), которое будет равно нулю тогда и только тогда, когда не уклонено переменная была массивом. Если это так, разделение нуля на себя вызывает желаемый сбой.

Ps. Два других 18-символьных решения:

.{[]`?)},{.}%~](n<

и

.{[]`?)},~]([n]+n<

Увы, я еще не нашел более короткий способ решить «проблему пустых массивов».

Илмари Каронен
источник
это сбалансировано ?: ][(т.е. это терпит неудачу в вашей программе?)
Джастин
@Quincunx: не получается, как следует.
Ильмари Каронен
Тем не менее, это оказалось принять [[]; Я исправил это сейчас, по цене 4 символов, и теперь он проходит все мои тесты.
Илмари Каронен
Если я вас правильно понимаю, у вас было решение из 14 символов, которое не может различить строку и массив только в том случае, если массив пуст. 1+превратит пустой массив в непустой массив, непустой массив в непустой массив, а строку в строку.
Питер Тейлор
@PeterTaylor: Да, это было .{[]`?)},~](n<. Я попробовал ваш 1+, но кажется, что массив должен содержать что-то отличное от числа (предположительно, чтобы интерпретатор зависал при попытке рекурсивного сравнения символа с массивом / строкой). Использование n+также не работает, так как он приводит массив в строку; [n]+ делает работу, но по- прежнему ставит меня в 18 символов.
Илмари Каронен
17

Brainfuck 76 байт

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

Это выходит из-под контроля, если квадратные скобки не сбалансированы, что приводит к сбою интерпретатора / компилятора bf, и некоторые из них имеют коды выхода, чтобы отразить это.

требует eof = 0, значений переноса и конечного числа ячеек

В Ubuntu вы можете использовать интерпретатор bf( sudo apt-get install bf)

% echo '[[[]' | bf -n bf_matching.bf
Error: Out of range! Youwanted to '<' below the first cell.
To solve, add some '>'s at the beginning, for example.
an error occured
% echo $? 
5
% bf -n bf_matching.bf < bf_matching.bf
% echo $?
0
Сильвестер
источник
5
Мне нравится, как ты использовал Brainfuck, хотя вопрос сказал, что это невозможно.
Riking
Ух ты. Я честно удивлен. Я предполагал, что это невозможно, но это не так.
Конрад Боровски
1
@xfix: Brainfuck полностью тьюринг, поэтому он может делать все что угодно (учитывая ограничения ввода / вывода).
marinus
2
@marinus Тьюринг-полнота означает лишь то, что она может выполнять все вычисления. BrainfuckТьюринг завершен без ввода-вывода, так как вы можете запустить программу, которая вычисляет любые вычисления и посмотреть результат, проверив его память после запуска. BF без ввода / вывода сделает людей менее заинтересованными, так как будет сложно сделать утилиты. Например, я никогда не смог бы сделать мой переводчик LISP .
Сильвестр
14

Befunge 98 - 26 31 20 19 символов

~:']-!\'[-!-+:0`j#q

Избавился от некоторых массивных условных выражений. Теперь программа работает следующим образом:

~:   read an input char and duplicate it

']-! push a 1 if the char is the ] char, 0 otherwise

\    swap the comparison value for the duplicated input char

'[-! push a 1 if the char is the [ char, 0 otherwise

-    subtract the two comparison values. If the second one is 1, the first is 0, 
     so the result is -1. Else if the second one is 0, the first is 1 and the result is
     1. Else, the first and the second are both 0 and the result is 0

+    Add the number to the counter (which is 0 if there is none already)

:0`  test if the counter is positive (that'd mean an invalid program). Pushes a 1 if 
     positive, 0 otherwise.

j#q  if the counter is positive, then this jumps to the q. Otherwise, it skips the q 
     and continues to the ~ at the beginning of the line. If there are no more chars in
     the input, then the IP will be sent back to the q. 

qвыходит из программы и выводит верхнее значение в качестве значения ошибки. Значение ошибки будет -1 1, если их слишком много] , 0, если они сбалансированы, и положительно отрицательным, если их слишком много [. Если число положительно отрицательно, то для балансировки программы необходимо столько абсолютных значений этого числа ].

Редактировать: переключаемое увеличение и уменьшение. [используется для увеличения счетчика и ]для его уменьшения. Переключая его, я сохраняю 1 символ, потому что для условия выхода мне нужно только проверить, является ли счетчик положительным, а не отрицательным.


Старая версия

~:'[-!j;\1+\#;']-!j;1-#;:0\`j#q

Этот код работает следующим образом:

~    read one char of input
:    duplicate it
'[-! push 1 if the character is [, 0 otherwise
j    jump that number of characters
;    skip until next ;
\1+\ increment counter

similarily for ].

#q when end of input is reached, ~ reflects the IP back. q ends the program with the error value on the stack.

Изменить: понял, что это принятые входные данные, как ][, теперь он заканчивается всякий раз, когда счет становится отрицательным, используя

:0\`j
Джастин
источник
1
18 байт
Джо Кинг,
@ JoKing это довольно мило, используя расстояние между [и ]сделать сравнение с обоими.
Джастин
6

J ( 38 35)

exit({:+.<./)+/\+/1 _1*'[]'=/1!:1[3

Объяснение:

  • 1!:1[3: читать стандартный
  • '[]'=/: создать матрицу, в которой первая строка является битовой маской [s во входных данных, а вторая строка -] s.
  • 1 _1*: умножить первый ряд на 1, а второй на -1.
  • +/: суммировать столбцы матрицы вместе, давая дельта-отступ на символ
  • +/\: создайте их общее количество, давая уровень отступа для каждого символа
  • ({:+.<./): вернуть GCD последнего элемента ( {:) и самого маленького элемента ( <./). Если все скобки совпадают, оба из них должны быть, 0так что это вернет0 . Если фигурные скобки не совпадают, возвращается ненулевое значение.
  • exit: установите значение выхода на это и выйдите.
Мэринус
источник
Хороший срыв ...
Крис Кэшвелл
6

рубин (64)

exit $<.read.tr('^[]','').tap{|x|0while x.gsub!('[]','')}.empty?

ранее (68) это было:

exit ARGF.read.tr('^[]','').tap{|x| 0 while x.gsub!('[]','')}.empty?

Другое эквивалентное решение использует

exit $<.read.tr('^[]','').tap{|x|0while x.gsub!('[]','')}.size>0

не может использовать sizeодин, потому что это даст ложные отрицания (!!!), когда общее количество несбалансированных скобок кратно 256

переписан
источник
Это кодегольф. Я уверен, что вы можете удалить некоторые пробелы здесь. Ruby несколько чувствителен к пробелам, но во многих случаях игнорирует его. Для начала вам не нужно пробелов рядом с =оператором.
Конрад Боровски
лучшая версия (несколько вдохновленная решением sed + tr). Я не уверен, что смогу стать намного лучше, чем это. По крайней мере, он имеет всего 4 пробела!
переписано
1
И все же я могу удалить два из них.
Конрад Боровски
2
Я думаю, что места вокруг 0могут пойти.
Маринус
потрясающий космический трюк, спасибо!
переписано
5

Perl, 30 символов

Ваш основной Perl рекурсивный регулярное выражение на помощь:

perl -0ne 'exit!/^(([^][]|\[(?1)\])*)$/'

Для тех, кто не знаком с аргументами командной строки, используемыми здесь: -0позволяет установить символ конца строки для целей ввода файла; использование -0без аргумента устанавливает символ конца строки в EOF. -nавтоматически считывает ввод (в данном случае весь файл) в $_заранее.

Если регулярное выражение совпадает, оно возвращает истинное значение, которое сводится к 0 для кода выхода. В противном случае ложное возвращаемое значение дает код выхода 1.

Хлебница
источник
Думаю, мне придется лучше отыграть свой ответ, чтобы обойти это решение с 30 символами.
Джастин
Там. Мое решение теперь намного короче, чем было раньше. Хорошее решение. +1
Джастин
4

Баш (tr + sed) - 42

[ -z `tr -Cd []|sed ":a;s/\[\]//g;t a"` ]

Если вы не возражаете против сообщений об ошибках, вы можете удалить последний пробел между `и ]получить длину 41.

shiona
источник
Если я ничего не пропущу, вы бесполезно используете catи $()(также "[]"можно записать как[] ). Я принял этот ответ, но пока я не увижу улучшения в длине, я не собираюсь повышать это, так как пока короткий, это может быть намного короче для bash.
Конрад Боровски
Ну, на самом деле я не очень хорошо знаю сценарии оболочки. Я не могу сделать большинство из этих работ. Я заменил $()галочкой и сделал "[]"-> []вы предложили.
Шион
Существует все еще бесполезное использование кошки .
Конрад Боровски
1
Я мог бы меч, я пытался и потерпел неудачу, но я был не прав.
Шион
3

Perl (56 символов)

$/=0;$r=qr/[^][]*(\[(??{$r})\])*[^][]*/;<>=~m/^$r$/||die

Очевидное решение Perl: рекурсивное регулярное выражение. К сожалению, это довольно многословная конструкция.

Питер Тейлор
источник
3

Хаскелл (143)

import System.Exit
f=exitFailure
v c []|c==0=exitSuccess|True=f
v c (s:t)|c<0=f|s=='['=v(c+1)t|s==']'=v(c-1)t|True=v c t
main=getContents>>=v 0

to jgon: использование 2-х охранников кажется более плотным, чем если-то-еще. Кроме того, я не думаю, что ваш проверяет, что скобки в правильном порядке ("] [" проходит)

user13350
источник
Ого, только видел этот комментарий, когда он был отмечен сегодня. Исправил мой код, но да, приятно, охранники кажутся более плотными (+1).
августа
3

C 73 64 символа

Благодаря предложениям из хлебного ящика (хотя это, вероятно, требует порядка с прямым порядком байтов):

i;main(c){while(read(0,&c,1)*(i+1))i+=(c==91)-(c==93);return i;}

Как это устроено:

  • неявный int global iполучает значение 0
  • cстановится неявным int, который получает argc(инициализируется 1, но нам все равно, только если старшие биты не установлены)
  • read(0,&c,1)считывает один символ в младший байт c (на архитектурах с прямым порядком байтов) и возвращает 0 в EOF; i+1 != 0если кавычка в сбалансированной скобке не равна -1; умножение их вместе работает как (безопасное) логическое И, которое занимает на один символ меньше, чем&&
  • c==91оценивает до 1 для '['и c==93оценивает до 1 для']' . (Там может быть какой-то трюк с мелочами, который будет меньше, но я ничего не могу придумать.)
  • return iвыходит с кодом состояния 0, если он сбалансирован, и ненулевым, если это не так. Возвращение -1 технически нарушает POSIX, но на самом деле это никого не волнует.

Предыдущая версия:

main(i){char c;i=0;while(read(0,&c,1)*(i+1))i+=(c==91)-(c==93);return i;}
пушистый
источник
Использование getchar()вместо чтения сократит код и позволит вам использовать (неявно) intвместо charсвоей переменной. Также помните, что глобальные переменные автоматически обнуляются.
хлебница
Спасибо, я забыл про getchar (). Не уверен, как глобальный init помогает, хотя - определение глобального int занимает больше символов, чем использование неявного аргумента argc.
пушистый
1
Глобалы также могут быть неявными. Вне функции c;определяет глобальный int.
хлебница
Между тем, getchar (c) в конечном итоге не делает его короче, по крайней мере, с использованием этого подхода, потому что его нужно каким-то образом протестировать на> = 0, и неявный int для c, переданный в read (), не гарантирует работа из-за байтов
пушистый
Как насчет ][? Я уверен, что это не сбалансировано. Разве вы не должны следить за тем, не станет ли он отрицательным хотя бы один раз?
vsz
2

Луа, 56

os.exit(("["..io.read"*a".."]"):match"^%b[]$"and 0 or 1)
МНИИП
источник
"^%b[]$"что это? Вы можете объяснить? Конечно, это не регулярное выражение?
Cruncher
@Cruncher: Это не так. Это шаблон Lua, а не регулярное выражение (шаблоны Lua похожи на регулярные выражения, но это не так). В этом случае он соответствует началу string ( ^), сбалансированному набору [и ]чему угодно inbetween ( %b[]) и концу string ( $).
Конрад Боровски
1

GTB , 55

0→O:0→X[`I@I="[":X+1→X@I="]":X-1→X@X<0:1→O@!!Ig;e]l;e~O

Пропускает []

Используйте, 0чтобы остановить.

Timtech
источник
1

МАТЕМАТИКА, 88 символов

s = "[ [ my crazy code ] [ don't explode please! [] [ :)Ahh) ]  [] []]]";

r=StringReplace;
StringLength@FixedPoint[r[#,"[]"-> ""]&,r[s,Except@Characters["[]"]-> ""]]
Мурта
источник
С функцией s name like RegularExpression` и StringLengthя никогда не смогу выиграть контекст гольф-кода с Mathematica! :)
Мурта
Я знаю, что вы имеете в виду :) ToCharacterCodeгораздо дольше, чем ordтакже ... PS: А как насчет установки кода выхода?
Аяся
Length[StringCases[s,"["|"]"]//.{x___,"[","]",y___}:>{x,y}]
alephalpha
1

Рубин, 59 58

Сканирует на открывающую и закрывающую скобки, считая [как 1 и ]как -1, и выходит, если количество падает ниже 0.

b=0
$<.read.scan(/\]|\[/){exit 1if(b+=92-$&.ord)<0}
exit b
daniero
источник
1
Подтверждено и сокращено на один символ (я удалил пробел после того, как exit 1вы спросите).
Конрад Боровски
1

Калий , 104 байта

func main(){l=0;r=0;b=input();foreach (c in b){if(c=="[")l++;if(c=="]")r++;}if(!(r==l))exit(1);exit(0);}

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

Яков Мисирян
источник
1

Код машины Тьюринга, 286 276 байт

Опять же, я использую синтаксис таблицы правил, определенный здесь.

0 * * l 1
1 _ ! r Q
5 _ _ r 5
5 * * * W
W [ ! l E
W ] ! l T
W _ _ l I
W * ! r *
E ! ! l *
E * * * R
R _ [ r O
R * * l *
T ! ! l *
T * * * Y
Y _ _ r U
Y * * l *
U [ _ r O
U ! ! * halt-err
I ! ! l *
I _ _ r halt
I * * l halt-err
O ! ! r Q
O _ _ l I
O * * r *
Q ! ! r *
Q * * * W

Завершается в состоянии haltпринять ввод и halt-errотклонить его.

SuperJedi224
источник
halt-errможет быть короче, как halt*например.
Эрик Outgolfer
1

Хаскелл ( 167 , 159)

Делал это в основном для развлечения, если у кого-нибудь есть какие-либо предложения, как сделать его короче, я был бы рад услышать их, хотя :)

import System.Exit
p x y b|b=x|True=y
main=getContents>>=(return.all (>=0).scanl (\v->p (v-1) (v+1).(==']')) 0.filter (`elem`"[]"))>>=p exitSuccess exitFailure

Изменить: Исправлена ​​проблема, указанная мне в комментариях (добавлено 11 байт).

Редактировать 2: Создана вспомогательная функция для тестирования предикатов с использованием сторожей, созданных на основе user13350, с удалением 8 байтов.

jgon
источник
@ user202729 Это отличный момент, это было супер небрежно. Уверен, это сейчас исправлено.
августа
1

Stax , 14 11 персонажей

╬Äτ↔EªÉs «Ü

Запустите и отладьте его

Кредит @recursive для -3 байта.

ASCII эквивалент:

.[]Y|&{yz|egp!

Удалите все символы, кроме [], затем удалите, []пока строка больше не изменится. Вернуть, 1если последняя строка пуста.

Вейцзюнь Чжоу
источник
1
Ницца. Вы можете использовать .[]|&для фильтрации символов, а затем повторно использовать литерал для 11
рекурсивный