태그 보관물: decision-problem

decision-problem

Brainfuck 프로그램 확인 결함 일지

그러나 또 다른 Brainfuck 파싱 문제이지만 이번에는 … 다릅니다.

당신은 Brainfuck 프로그램을 만드는 회사 인 Infinite Monkeys Incorporated에서 다양한 흥미로운 문제를 해결하기 위해 노력하고 있습니다 (사고로, 회사는 무작위로 프로그램을 만듭니다). 그러나 Brainfuck 만 실행하는 빠른 Turing 컴퓨터는 구문 오류와 관련하여 작고 값 비싼 문제가 있습니다-컴퓨터를 만들고 컴퓨터가 폭발합니다. 아마도 디자인 결함 일지 모르지만 아무도 왜 그런지 고민하지 않았습니다.

튜링 머신 (특히 빠른 머신)은 비싸기 때문에 (결국 무한 RAM이 필요) 코드를 실행하기 전에 프로그램에 구문 오류가 없는지 확인하는 것이 좋습니다. 회사에서 많은 코드를 실행하므로 수동 확인이 작동하지 않습니다. Brainfuck 코드 용 STDIN을 읽고 프로그램에 구문 오류가있는 경우 종료 상태가 0 (오류) 이외의 값으로 설정된 상태로 종료하는 프로그램을 작성하십시오 (예 :] 일치하지 않기 때문에 구문 오류 [임). 프로그램이 완전히 정상이면 종료 상태가 0으로 설정된 상태에서 종료하십시오.

프로그램이 관련된 실수를 올바르게 인식하는지 확인하십시오 []. 다른 컴퓨터가 폭발하기를 원하지 않습니까? 아, 그리고 가능한 한 짧은 지 확인하십시오-상사는 짧은 프로그램에 대해 비용을 지불합니다 (그가 빠르거나 다른 것으로 생각하기 때문에). 아, 그리고 당신은 Brainfuck에서 코딩 할 필요가 없습니다 (실제로 Brainfuck은 종료 코드를 지원하지 않기 때문에 할 수 없습니다)-코드는 일반 컴퓨터에서 실행됩니다.

보시다시피, Brainfuck 프로그램이 “유효한”(페어링 된 []기호 가 있는지) 여부를 확인해야합니다 . Brainfuck 프로그램은 이외의 다른 문자를 가질 수 []있으므로 다른 명령이 있기 때문에 프로그램을 거부하지 마십시오. 가장 작은 코드가 승리하지만 어쨌든 상향 투표에 더 관심이있을 것입니다.



답변

GolfScript, 18 자

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

입력의 대괄호가 균형을 이루면이 코드는 종료 코드 0으로 성공적으로 실행되고 일부 쓰레기는 표준 출력으로 인쇄합니다. 그렇지 않은 경우 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) 의 첫 번째 항목을 찾으려고 시도합니다. 변수는 배열이었습니다. 그렇다면 0으로 나누면 원하는 충돌이 발생합니다.

추신. 다른 두 가지 18 문자 솔루션은 다음과 같습니다.

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

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

아아, 아직 “빈 배열 문제”를 해결하는 더 짧은 방법을 찾지 못했습니다.


답변

Brainfuck 76 바이트

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

대괄호가 불균형하면 bf 인터프리터 / 컴파일러가 런타임에 실패하고 일부는 종료 코드가 있음을 나타 내기 위해 본드가 사라집니다.

eof = 0, 랩핑 값 및 finit 수의 셀 필요

우분투에서는 통역사를 사용할 수 있습니다 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

답변

비 펀지 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

답변

J ( 38 35)

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

설명:

  • 1!:1[3: stdin 읽기
  • '[]'=/: 첫 번째 행이 [입력 에서 s 의 비트 마스크 인 행렬을 작성 하고 두 번째 행은] s 인 .
  • 1 _1*: 첫 번째 행에 1을 곱하고 두 번째 행에 -1을 곱하십시오.
  • +/: 행렬의 열을 합하여 문자 당 델타 들여 쓰기
  • +/\: 각 문자에 들여 쓰기 수준을 부여하여 누적 합계를 만듭니다.
  • ({:+.<./): 최종 요소의 GCD를 반환합니다 ({: )와 가장 작은 요소 ( <./) . 모든 괄호가 일치하면,이 두 가지가 있어야한다 0이 반환됩니다 있도록 0. 중괄호가 일치하지 않으면 0이 아닌 값을 반환합니다.
  • exit: 종료 값을 설정하고 종료하십시오.

답변

루비 (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의 배수 일 때 거짓 부정 (!!!)을 나타 내기 때문에 단독으로 사용할 수 없습니다


답변

펄, 30 자

구조에 대한 기본 Perl 재귀 정규식 :

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

여기에 사용 된 명령 줄 인수에 익숙하지 않은 사용자 -0는 파일 입력을 위해 줄 끝 문자를 설정할 수 있습니다. -0인수없이 사용 하면 줄 끝 문자를 EOF로 설정합니다. -n입력 (이 경우 전체 파일)을 자동으로 읽습니다.$_사전에 .

정규식이 일치하면 종료 코드에 대해 0으로 무시되는 true 값을 리턴합니다. 그렇지 않으면 false 리턴 값은 종료 코드 1을 생성합니다.


답변

배쉬 (tr + sed)-42

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

당신이 오류 메시지를 꺼리지 않는 경우에 당신은 사이 마지막 공간을 제거 할 수 `]길이 (41)를 얻을 수 있습니다.