λx. x K S K ＠はてな

このブログ内に記載された文章およびコードの著作権は，すべて Keisuke Nakano に帰属します．

Pyramid Quine

解答

以下は d:id:KeisukeNakano:20070807:1186422886 の解答です．問題はそちらをご覧ください． なお，この問題はSPOJのCTQUINEというクリスマスツリー型のQuineを求める問題を簡略化したものです． さすがに，1-2時間で解かせる問題としては難しいと思ったのでピラミッド型という単純な形にしました． 興味のある方は元の問題CTQUINEにもチャレンジしてみてください． 但し，この問題ではRubyが使えないなど言語に制限があるため， OCamlより短い答えが（現時点では）提出されていないようです．

実際のコンテストでは時間制限もあったのでちょっとしたヒント（Quineの例）を付けていましたが， ここでの公開では省きました． Quineの作り方については以前解説した通りで， 基本的には同様の構成で作ることができます． 大まかな構成法は以下の通りです．（少し分かりにくいので例を交えて説明しています）

  • 文字列に対応する別のデータ表現を考えます．（たとえば，"barfoo" という文字列に対し，{"b","ar","foo"} という配列を考えることができます）
  1. データ表現 d から文字列を復元するコード C を用意します．（上の例では，文字列を連結するコードを考えます）
  2. データ表現 d から「そのデータ表現を生成するコードの文字列」を出力するコード D を用意します．（上の例では，{"b","ar","foo"} という配列 d から "{\"b\",\"ar\",\"foo\"}" という文字列を生成するようなコードを考えます）
  3. 以下のようなコードを考えればQuineになります．（ただし，α は 2 行目のコード文字列に対応するデータ表現）
d:= α
print("d:=",D,"\n",C)

この形の Quine では，データ表現として空白が無視できるものを選んだり C として空白を無視するコードを記述したりすることでデータ部分を柔軟に整形できるため， ピラミッド型のコードを容易に作ることが可能です． なお，整形させるのは手でもかまいませんが，実際にはそれを自動化するプログラムを書く方が効率的です． 文字列リテラルの中に改行を使えるRubyやOCamlでは，データ表現として文字列を選ぶと D が記述しやすいようです．

まずは，Rubyの10点から．

         '
        PX4
       KIC8v
      OyQ+PDx
     bJyAnKjks
    JCcsCiQnLnV
   ucGFjaygnbScp
  XSoiJyI=KSK='=~
 //;$><<[' '*9,$',
$'.unpack('m')]*"'"
ポイントは，正規表現を使って後ろから束縛している点と unpackが空白を無視してくれる点でしょうか． この問題を公開してすぐに， yamaguchi_keitaさんからevalを使った解答があり， 同様にevalを使ってみたところ，8点が出ました．
       "
      #K#
     $><<[
    ' '*7 ,
   $','=~/'+
  '/;ev']*34.
 chr+'al$'+39.
chr"=~//;eval$'
まだ縮みそうなのですが，どうなんでしょ？ ちなみに，yamaguchi_keitaさん自身も少し違う方法で8点を出しています．

次は，OCamlの17点．

                (
               let
              s,f="
             +o{n}(6
            7hi#NmUu#
           ##)l`fhb#Rw
          }hif)hwd}#+S}
         hiwa)u##s}hiwa-
        $06r_i$0;r_i$08r$
       r_-/-u#-+--odw--r/a
      <_--r:ati#b,9b92=!+u(
     <ntwstw^mxwd#rwgntw+a+a
    #b*0(((r(",(lxor)74in Obj
   .magic String.iter (Printf.
  printf"%17s\n%18s\n%19s%s\","
 "(""let""s,f=\""s;fun c->c>32&(
)=output_byte stdout(f(f c+1)))s)
Obj.magicとか(lxor)74とか&()=とかOCaml Golfのエッセンスがたっぷりです． 一行目にダミーの括弧を入れるというのもポイントですね． 「Obj.magicなんて反則だ」という方のために18点の解答も用意しました．
                 (
                let
               s,f="
              -Dibs/d
             pef!jo!!!
            !!Qsjoug$!!
           !/qsjoug#&29t
          ]o&2:t]o&31t&t]
         ##$!!#)##mfu##t-g
        >]##t<!!Tusjoh/jufs
       $!)gvo!d.?d?(!('pvuqv
      u`czuf!tuepvu)$jg!d>(%(
     uifo!21fmtf!g!d.2*>)*<)**
    t*",Char.code in     Printf
   .printf"%18s\n%19s\n%20s%s\""
  "(""let""s,f=\""s;  String.iter
 (fun c->c>' '&output_byte stdout(
if c='$'then 10else f c-1)=();())s)

お次はCで19点．あまりC言語のゴルフは得意ではないのでまだまだ縮むと思います．

                  ;
                 ;;;
                char*
               s="zxx\
              lr$a3?7.\
             pw!(*7.$6p\
            z{r9|.|Rxxx{\
           ok9aa|.{oe90?*\
          r|.{o`)zlxoglkgl\
         Rxxkglgglz)c|zzwa6\
        -*p$c)ar)a(+$90?*pRx\
       r)qqw^ijvvr)ccijvv(+$)\
      pz||zwwa6-*paRr$a$qqwr$^\
     ijvv(+$90?*pih~pr$~fewqiwa\
    #"  ,*t;main(){printf("%*c\n\
   %15c;;\n%17char*\n%18s", 19,59,
  59,99,"s=\"");for(t=s;*s;putchar(
 *s++)>32&&*s==32&&puts("\\"));for(;
*t;t++)*t>32&&putchar(30^(*t^67)+3);}
コンテスト後にこの解答を見せたら，ANSI Cでは正しくないのではというツッコミが入りましたが， そこは大目に見てやってください．

続いて，Haskellの37点． HaskellやPythonのようにインデントに意味があるような言語では完全なピラミッドを作るのは難しいようで， 一行目でペナルティを受けています．

l                = 
                [""
               ,"  "
              ," ];m"
             ,"ain=ma"
            ,"pM_ putS"
           ,"tr(\"l\":m"
          ,"ap(f\n  repl"
         ,"icate length)("
        ,"\"= \":\"[\\\"\\"
       ,"\"\":\n (map ((\","
      ,"\"++).show).tail)l)+"
     ,"+l  )\nf r g s=r(17-di"
    ,"v(g s)2)' '++s++\"\\n\" "
   ];main=mapM_ putStr("l":map(f
  replicate length)("= ":"[\"\"":
 (map ((","++).show).tail)l)++l  )
f r g s=r(17-div(g s)2)' '++s++"\n"
最初と最後の行の末尾には空白が必要なので注意． どのみちペナルティは受けるので，そのへんの末尾の処理は妥協しています． 私自身はそんなにHaskellに詳しくないので断言はできませんが， Haskellでは完全なピラミッドは作ることはできないのではないでしょうか？ Pythonについても，どなたかチャレンジしてみてください．

最後に，Brainfuckの30点．

                             -
                            >>>
                           >>>>>
                          >+++>+>
                         +++>+>++>
                        +++>+>+>+>+
                       >+++>>+++>+>+
                      ++>+>+++>+>++>+
                     ++>++>>+++>+>>>+>
                    +>>+++>+++>+>>>>>++
                   >+++>++>>+>+>>>+++>+>
                  +++>+>++>+++>+++>+>>+++
                 >+++>+>+++>+>+++>>>>>>>>>
                >>>>>>>>>>>>>+>+>++>+++>++>
               >+++>+>>>>>>>>>>>>>>>>>>>>>>>
              >>>>>>>>>>+>+>>+++>>>+>+>+>+>>>
             ++>+++>+>+>>+++>+>+>+>+>>+++>+>+>
            ++>+++>++>>+>+>>>+++>+>>+++>+>+>++>
           +++>++>>+>+>+++>>+++>+>+++>+>>>+>+>>+
          ++>++>>>+++>+>+>>>>>+++>+>+++>+>++>+++>
         ++>>+>+>+>+>+>+>>>+++>+>>>>>>>+++>+>>>>>>
        >+++>+>>+++>>>>>>>>>>>>>>>>>>>>>+++>+>>>+++
       >+>+++>+>+++>+>>>+++>+>>>+++>+>>>>>>>++>+++>+
      ++>+>>+++>+++>+>+++>+>+++>+>++>+++>>>+>+>+>+>++
     >+++>+>+>>+++>>>>>>>+>+>>>+>+>++>+++>+++>+>>+++>+
    ++>+>+++>+>++>+++>++>>+>+>++>+++>+>+>>+++>>>+++>+>>
   >++>+++>+++>+>>+++>>>+++>+>+++>+>>+++>>+++>>+[[>>+[>]
  +>+[<]<-]>>[>]<+<+++[<]<<+]>>>[>]+++>+>+>>>+>++++++++++
 [>+++>+++>+<<<-]>>++<[-[<+>>.<-]<[>+<-]<[<<[<]+<<+[<+++++
+++++++++++>-]<++++++++++.>>[>]>>+<-]++>[<+>-]>>>.<<]>>++++
これについては以前紹介したものとほぼ同じ解法なので解説は省略します． 最後の>>++++は揃えるためのダミーです．

これだけピラミッドが並ぶとなんだか壮観ですね．まだまだ縮むと思うので興味のある方は是非チャレンジを．