鍋あり谷あり

テーマを決めずに適当に書いています。

どう書くの問題を作るときに考えること

虎塚さんの記事
http://d.hatena.ne.jp/torazuka/20140512/doukaku
を受けて。

正確なテストデータ / データの数

深く考えずに、40個ぐらいにしていることが多いんだけど、
コーナーケースが多そうなら多めに、コーナーケースが少なそうなら少なめにしてる。
仕様を網羅したいという希望はありつつも、べつに網羅できなくてもいいよね、とも思っている。

正確なテストデータ / データの作成方法

だいたい以下の順序で

  1. 典型的なケース。問題文中に例として挙げます。
  2. 典型的な例外ケース。該当するものがなかったらとかそういうの。
  3. 典型的なケースをいくつか。
  4. コーナーケースを思いつく限り。
  5. 乱数

「乱数」と、さらっと書いたけど、一様乱数でうまくいくわけではない。
たとえば「ポーカーの残り＋」( http://nabetani.sakura.ne.jp/hena/ord10pokarest/ )。
この問題の場合は（あんまりおぼえてないけど）全部の手についてのデータをまあまあ均等に出している。

解き方が複数ある問題にする

この要件が大問題で、ここに注力するとすぐに難易度が上がってしまう。
で。
『「自分では思いつかないけれど、誰かが別の方法で解いてくれるかもしれない」などと勝手に期待』することは結構あって、解き方がひとつしか思いついていない場合でも、いやこれはこの経路以外にありそうだという感触があればそれでよしとする場合もある。
もちろん複数の経路を実装しておきたいとは思うんだけど。

特定のプログラミング言語に配慮する

だいたい ruby に対する嫌がらせをしたいんだけど、いくら考えても他の言語に対する嫌がらせにしかならない。
C と Java、特に C を優遇したいと考えていて、入力データを固定長にしたりしている。

視覚的な演出になる図表を入れる

どちらかというと、できれば図を入れたくないと思ってる。
図を書くコードを書くのが面倒なので。
図が入っているのは、図を入れないと仕様が明確にならないと思ったときだと思う。

過去に出した図で一番気に入ってるのはやっぱり
折って切る( http://nabetani.sakura.ne.jp/hena/ord17foldcut/ )のアニメーション。
問題としてもすごく気に入ってる。
未見の方は是非解くことをおすすめする。

それ以外

どれ以外だと

  • 数学的になりすぎないようにする。
  • 参加者を想像して問題を作る。
  • コンピュータがなくても解ける問題の方が良い。

あたりのことを考えてるって、前にどっかに書いたような。

参加者を想像して問題を作る

これはあんまり具体的にどう問題を作るかという話ではなく。
文字通り、参加者を想像する。
☓☓さんはこの問題を見たらどういう表情をするだろうか。
◯◯さんはこの問題にどう取り組むだろうか。
とか、そういうこと。
CodeIQ と違って、問題を解く人々の集う場があるので（問題だけではなく）その場を面白くしたいと思ってる。
どうしたら面白くなるのか全然わからないんだけど、たぶん面白くするための手段として、想像しながら問題を作っている。

久々に 剰余なしで FizzBuzz

プログラミング

はるか昔に書いた
http://d.hatena.ne.jp/Nabetani/20070510/p1
が、ruby 2.1.0 では動かないようなので、書きなおした。

def f(name,n)
  Fiber.new do
    loop do
      (n-1).times{ Fiber.yield "" }
      Fiber.yield name
    end
  end
end

def fb(sup, *x)
  s=x.map{|name,n| f(name,n)}
  1.upto(sup) do |n|
    yield( (r=s.map{|x|x.resume}.join).empty? ? n : r )
  end
end

fb( 100, [ 'Fizz', 3], [ 'Buzz', 5 ] ) do |s|
  puts s
end

Generator がなくなって Fiber になったらしいので、それに関する対応。
ほかにも多少変更したけど。

記号の読み方

プログラミング

記号の読み方は本を読んでも書いてなかったりするし、会社や文化圏によっても違ったりするので結構困るんだけど、私はこう読んでるよ、という話は書くことができる。

!文脈がなければ「ビックリ」。単項演算子なら「ノット」とか
#「シャープ」か「ハッシュ」
&「アンド」
~「チルダ」
^文脈がなければ「ハット」。二項演算子なら「エックスオア」とか
|文脈がなければ「縦棒」。二項演算子なら「オア」とか
<「右が大きい」あるいは「不等号」。不等号の意味で「>」はほとんど使わないので「不等号」で誤解がないことが多い。
>「左が大きい」または「右が小さい」。template なんかで閉じ括弧に使う時も「右が小さい」と読んだりする。
{ }「波括弧」
[ ]「配列括弧」か「角括弧」
( )「括弧」か「丸括弧」
_「下線」か「アンダースコア」
\「バックスラッシュ」
`「バッククオート」

こんぐらいかな。

正規表現の中にある ^ は、「ハット」と呼んでいる。
「アクサンシルコンフレクス」とか「サーカムフレックス」だと、は â や ê にくっついている場合の「 ̂ 」のことで、単体で意味を成す「^」のことではないような気分。
まあその割に「~」のことを「チルダ」と呼んでるけどね。

筑波の ruby の 23番

プログラミング

「Ruby プログラミング 50題」
http://klis.tsukuba.ac.jp/klib/index.php?plugin=attach&refer=KISL%2Ftop&openfile=ruby.pdf
という素晴らしい資料を筑波大学が公開している。

で。

この 23番。

tango = ["knowledge", "information", "system" , "library", "metadata"]

while true
  print("単語を入力してください\n")
  print("終わる時は . (ピリオド) を入力してください\n")
  a = gets.chomp
  if a == "."
    break
  end

  j=0
  while j < tango.size
    if a == tango[j]
      print(a, "は辞書に登録されています\n")
      break
    end
    j=j+1
  end
  if j == tango.size
    print(a, "を登録します\n")
    tango.push(a)
  end
end
tango.each{|value|
  print(value, "\n")
}

j をループカウンタにした while ループが難しい。

  • 事前条件 : tango.size は 5。a は未登録の単語 "hoge" にしておこう。
  • while文 : j は 0。j<tango.size は true なので ループ内に入る。
  • a==tango[j] は "hoge"=="knowledge" という意味なので、false。
  • break しなかったので、j=j+1 が実行され、j の値が 1になる。
  • 中略
  • break しなかったので、j=j+1 が実行され、j の値が 5なる。
  • while文 : j は 5。j<tango.size は false なのでループ終了
  • if j==tango.size に到達。5==5 ということなので、true。
  • print(a, "を登録します\n") を実行
  • tango.push(a) を実行。tango.size が 6 になる。

ということなんだけど、箇条書きにしただけなので説明できてないような気もする。

while の中で一度も a == tango[j] が true にならなかった場合、j が tango.size と等しくなるまで増えていく。
ので、while を終えた時点で j と tango.size が等しくなる。
逆に。
while の中で a==tango[j] が true になった場合、その時点で終了するので、while ループを抜けた段階での j は tango.size より小さくなる。
表にしようか。

状況 while ループを抜けた段階での jの値
a==tango[j] が true になったので break した 0以上で、tango.size より小さい
a==tango[j] が 一度も true にならなかった tango.size に等しい
起こりえない状況 tango.size より大きい
こんな感じ。 起こりえない状況が条件に混入しても困らないので、 もとのソースで
  if j == tango.size
となっている if 文 の == となっている部分は、== でも >= でも構わないけど、<= だと困る。 ということなんだけど、こんな説明でいい？

蛇足

私は、 chomp も chop も書かないようにしている。どっちが何なのか覚えられないし、状況によって変な動作になるのでちょっとこわい。 strip の方がいいと思う。

南無ドット

プログラミング

CodeIQ のナムドット問題( https://codeiq.jp/ace/yuki_hiroshi/q468 )に取り組んでみた。
規則性の発見に数時間を要したと思う。
規則性がわかれば実装はそんなにかからなかったと思う。
測ってないけど。

で。
私が書いたのはこんな感じ。

maps = (0..( "01234".to_i(5))).map{ |raw_number|
  penta_num=("00000"+raw_number.to_s(5))[-5,5]
  used=penta_num.chars.uniq
  penta_num.chars.map{ |c|
    used.index(c)
  }.join
}.uniq

maps.each_with_index{ |proj,index|
  # printf "%2d : " % (index+1)
  puts 5.times.each_with_object( [""]*5 ){ |ix, o|
    o[proj[ix].to_i]+="#{ix+1}"
  }.select{ |i| ! i.empty? }.join(".")
}

問題を解いてから wikipedia で 52 を調べた( wikipedia:52 )ら、案の定答えがあった。
ベル数( wikipedia:ベル数 )という名前らしい。

言葉で数を表現する遊び( http://d.hatena.ne.jp/Nabetani/20061011/p2 )としては

  • 15 : 合成数であるベル数として最小
  • 52 : 偶数で合成数であるベル数として最小

といったところ。

追記：正解だったらしい。ほ。

Restricted Words の解答の改善

昨日記事を書いたら悔しくなってきたので、もう一回。

#!ruby
include Math
[
E*E*E+E*E*E+E*PI+E+E*E*E,
E+E*PI*E*E+PI*E*PI+E+E+E,
E*PI+PI*E*PI*E+E*PI*E+PI,
PI*E*PI+E+E*PI*PI*E+PI+E,
E*PI*PI+E+E*E*PI*PI+PI*E,
E+E*PI+E+PI+PI+PI+E+PI+E,
PI+PI+E*E+PI*E*E*E+PI*PI,
E*E+E*PI*E+PI*E*PI*E+E*E,
PI*PI*PI*PI+PI+E*E+PI+PI,
E*PI*PI*E+E+PI+E+PI*PI*E,
PI*E*E*E+E*E*E+PI*E+PI*E,
].each{ |v| print v.round.chr }

この方がいいと思うけど、なんか手作り感がないね。

等幅で見たほうが綺麗になる。

Restricted Words の解答

CodeIQ で出題することになったので、私も答えておこうと思い、Restricted Words ( https://codeiq.jp/ace/cielavenir/q431 ) に答えてみた。

問題は、文字列リテラルと数値リテラルを使わずに Hello World を出力するというもの。

ruby の場合、__END__ のあとを取ってくるとか、シンボル使うとか、クラス名取ってくるとか、安い方法がたくさんあって今ひとつ面白くない。

で。

私が書いたのはこんなの。

#!ruby
# tested with ruby 2.0.0p247 (2013-06-27 revision 41674) [x86_64-darwin12.4.0]
[(Math::E**Math::PI*Math::PI).floor,((Math::PI**Math::PI*Math::E
).to_i)+Math::E.to_i,(Math::PI**Math::PI*Math::E).to_i+(Math::PI*
Math::E).round,(Math::PI**Math::PI*Math::E).to_i+(Math::PI*Math::
E).round,(Math::PI**Math::PI*Math::E).to_i+(Math::PI*Math::E).
round+Math::PI.floor,(Math::PI**Math::PI*Math::E).to_i+(Math::PI*
Math::E).round-(Math::E**Math::PI*Math::PI).floor-Math::PI.ceil,
((Math::E**Math::PI)**Math::PI).floor/((Math::PI**Math::PI*Math::
E).to_i+(Math::PI*Math::E).round+Math::PI.floor)/Math::E.floor,(
Math::PI**Math::PI*Math::E).to_i+(Math::PI*Math::E).round+Math::
PI.floor,(Math::PI**Math::PI*Math::PI).floor,(Math::PI**Math::PI*
Math::E).to_i+(Math::PI*Math::E).round,(Math::PI*Math::PI).ceil**
Math::E.floor].map( &:chr ).tap{ |x| puts x.join }

Math::E と Math::PI をごちゃごちゃ組み合わせて文字コードを作り、それを chr して join したら完成。
ちなみに。
文字コードから計算式を自動生成したのではなく、試行錯誤で書いた。
最初のバージョンは中間生成物を変数に受けて、その値を利用することでだいぶ短くなっていたんだけど、むしろごちゃごちゃしたほうが楽しいかなと思って変数に受けずにだらだら書いた。「Math::」を撤去しなかったのも、ゴチャゴチャしたほうがいいかなと思って。

見なおしてみると、to_i, round, floor, ceil が入り乱れていて美しくない感じがする。map と tap があるのも無駄な感じ。

[略].each{ |c| print c.round.chr }

として、配列の中は E と PI と演算子だけにしたほうが良かった。

PI と E がリテラルではない定数で書ける処理系なら概ね移植可能だと思う。