λx. x K S K @はてな

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

Pyramid Quine

恒例の研究室合宿でのプログラミングコンテストで出題した問題を(一部編集して)公開. 解答は一週間後にここで発表します.

その出力がそのプログラム自身と一致するようなプログラムのことをQuineと呼ぶ. ここでは, Quineの名の元となった哲学者Willard Van Orman Quineに敬意を表し, そのプログラム自身を読み込むものや 関数呼び出しを含まないPHPコードのようなものや 空プログラムなどはQuineとは呼ばないことにする.

さて,今回の使命はピラミッド型の(あるいはそれに近い)Quineプログラムを書くことである. ピラミッド型のプログラムとは, 空白でない文字がピラミッドのような三角形をなしているプログラムで, 具体的には,ある n>0 に対し以下の条件を満たしているものである:

  • プログラムで使われる文字は,改行(0x0a)か空白(0x20)か非空白文字(0x21..0x7e)のみである.
  • 最後に現れる非空白文字は n 行目に現れる.
  • 全ての k=1,...,n に対し,k 行目の最初に現れる非空白文字は n-k+1 文字目である.
  • 全ての k=1,...,n に対し,k 行目の最後に現れる非空白文字は n+k-1 文字目である.
たとえば,下の図
において,(a)(b)はピラミッド型であるが,(c)(d)(e)(f)はピラミッド型ではない.

採点は,Quineプログラムになっているもののみを対象とし, 基準となるピラミッド型にどのくらい近いかによって判定する. 基準となるピラミッド型は上記の条件の n によって決定される. 具体的には「基準となるピラミッド型と異なる文字の数の自乗とn×2 の和」によって採点し, この値が小さいものほど上位とする. 同じピラミッド型でも,(a)のように 最後の行が n 行目でかつ各行の最後の文字が空白でないようなプログラムは, 特別ボーナスとして n だけ減算される. また,(f)のようなパターンは, 上記の条件からn=5のピラミッド型を基準として差分を計算されるため, 点数が大きくなってしまうことがあるので注意すること. なお,参考までにRubyによる採点プログラムを以下に示すが,Quineになっているかどうかはdiffなどを用いて各自で確認されたい.

input=$<.read
code=input.rstrip
puts " Height = %3d : %4d"%[height=code.map.size,height*2]
penalty=0
bonus=(input.map.size==height)?-height:0

code.each_with_index do |line,idx|
  line.chomp!
  bonus=0 if line.rstrip!
  penalty+=1 if height+idx>line.length
  line.unpack('C*').each_with_index do |byte,i|
    penalty+=1 if (i<height-idx-1||i>height+idx-1) && byte!=32
    penalty+=1 if (i==height-idx-1||i==height+idx-1) && byte==32
  end
end
bonus=0 if penalty>0
puts "Penalty = %3d : %4d"%[penalty,penalty**2]
puts "  Bonus = %3d : %4d"%[bonus,bonus]
puts "---------------------"
puts "  Total score : %4d"%(height*2+penalty**2+bonus)

どんな言語で解いてもかまいません*1. 参考までに,こちらであらかじめ用意していた解答例は Ruby (10点), OCaml (17点), C (19点), Brainfuck (30点), Haskell (37点) の5つです.

[追記(8/7)] yamaguchi_keitaさんの解答を元に書き直したところ,Rubyで8点まで出ました.

[追記(8/7)] yamaguchi_keitaさんも8点が出たようです.こちらの解答とは少し異なりますが.

*1:HQ9+などは除く