サービスによって処理系の特性の差があるのでまとめておこうと思った。 どれも記事作製時の情報。c言語の規格がどうとか、処理系の話とバイナリの話は別だとか、そういう細かいことはあまり気にせず適当に読んでね。

bf

$ bf -h
bf - a Brainfuck interpreter       version 20041219
(C) 2003, 2004, Stephan Beyer, GPL, s-beyer@gmx.net

Usage information: 
        ./bf [-h] [options] inputfile

Available options:
        -c<num>   specify number of cells [9999]
        -i        show used code input (stderr)
        -n        translate input: 10 (\n) to 0
        -w        disallow decrementing 0 and incrementing 255
        -,<mode>  set input mode: 0-4 [0]

See the bf(1) manpage for more information.
Have fun!
  • c言語製
  • cellは8bit (char)
  • EOFは$-1$
  • wrap-aroundする
    • opiton -wでdisallowできる
  • 負番地の読み書きは不可
  • 規定のcell数が$9999$と少ない
  • cheatは難しい
    • 中で命令を構造体にencodeして保持
    • unmatchedな]は怒られない
      • 先頭付近に跳ぶっぽい変な挙動をする
      • jumpが発生しないなら素通り
    • unmatchedな[は怒られる
      • Error: Out of range! You wanted to '>' beyond the last cell.という、なにか違うこと検出し停止する
      • jumpが発生しないなら素通り
  • 最適化はほぼない
    • 連続する+-や<>はある程度まとめられる

採用サービス

  • AtCoder
    • http://atcoder.jp/
    • 競技プログラミングのサイト
    • 日本語
    • Ubuntu 14.04.4 LTS trusty
    • beginner contestのA問題B問題あたりはbrainfuck向けの問題が多い
    • バイナリはubuntuのrepositoryから入手可能
  • HackerRank
    • https://www.hackerrank.com/
    • 競技プログラミングのサイト
    • Ubuntu 14.04.4 LTS trusty
    • wrap-aroundがoption -wを使って禁止されている
    • バイナリはubuntuのrepositoryから入手可能

BFI

 * Program Name:  BFI
 * Version:       1.1
 * Date:          2003-04-29
 * Description:   Interpreter for the Brainfuck Programming Language

$ bfi [<program file> ...]
  • c言語製
  • cellは32bit (int)
  • EOFは$-1$ (EOF)
  • wrap-aroundする
  • 特に最適化はない
    • 負数に[-]するとTLEなので注意
  • 負番地の読み書きは可能
  • cheat可能
    • codeはchar p[]として無加工で保持
    • unmatchedな]は先頭に跳ぶ (anagol)
      • 例: +++<---]>.>\x03ABC.>.はABCを出力
      • code領域の範囲を越えて[を探しにいく
      • $espより低位な部分に[がひとつだけ置いてあるのが原因
        • 実行環境に強く依存する
        • .によりputcharを呼ぶと壊れて使えなくなる
        • ,のgetcharなら壊れない
      • jumpが発生しないなら素通り
      • yukicoderでは使えないようだ
        • 単独の.や.を踏んだ程度ではだめ
    • unmatchedな[はsegmentation fault
      • jumpが発生しないなら素通り
    • data領域の左側にcode領域がある (anagol, yukicoder)
      • 例: +[<++ABC]:,:,:,はCBAを出力
    • 提出したcodeの右端には$-1$ (code読み込みの際のEOF)
      • 例: +[<+]<.<.<.ABCはCBAを出力
    • 環境が分かっていればropも可能

採用サービス

bff

$ bff --help
bff: moderately-opimizing Brainfuck interpreter, 1.0.6, http://swapped.cc/bff
Usage: bff [<program file> [<input data file]]
  • c言語製
  • cellは32bit (int)
  • EOFは変
    • argv[2]として渡されたファイルを読んでいるなら $0$ (0)
    • 標準入出力から読んでいるなら$-1$ (EOF)
  • wrap-aroundする
  • 負番地も使用可能
  • 最適化はすこし
    • [-]や[+]の特殊化
      • change logには1.0.6からとあるが実際は1.0.5の途中から
    • 連続する+-や<>はある程度まとめられる
    • [>+<-]の最適化はない
      • 負数にやるとTLEなので注意
      • “moderately-opimizing” とは
  • cheatはおそらく不可能
    • unmatchedな[ ]は実行前にちゃんと検出
    • 負番地には対応
    • 中で命令を構造体にencodeして保持

採用サービス

  • ideone
    • http://ideone.com/
    • onlineでコードを実行できるサービス
    • bff-1.0.5
      • [-]や[+]の特殊化あり
    • バイナリは入手できなさそう
  • CodeIQ
    • https://codeiq.jp/

    • 実務スキル評価サービス

    • 日本語
    • bff-1.0.3.1
      • data領域の初期化忘れのbugが残っている
    • 裏側にideoneの企業版を利用
    • バイナリは入手可能

各種サービスにおけるbrainfuck処理系について

  • Sun Mar 27 04:44:02 JST 2016
    • バイナリ取れるあたりのことを追記
  • Mon Apr 4 15:23:20 JST 2016
    • yukicoderにbrainfuckが追加されたので追記
    • ついでにanagolのunmatchedな]をきちんと調べた
  • Mon Dec 5 10:13:11 JST 2016
    • bfのcell数が少ないことを明記