« LinuxでchrootによるJail環境を構築 | トップページ | LinuxでchrootによるJail環境を構築2 »

2010年4月 3日 (土)

あなたのスキルで飯は食えるか?に挑戦

朝、twitterで西尾泰三氏があなたのスキルで飯は食えるか? 史上最大のコーディングスキル判定という記事を作成したというつぶやきを見かけた。 これは是非挑戦せねば、と挑戦した結果です。 時系列は下記の通り

9:50 開始 3時間後の1時に花見に行く約束なので丁度いい。
9:55 聴牌かどうかを割り出すのではなく、1-9のどれかを足してアガリ
になるかを確認するプログラムにしたらいいととひらめく。
9:57 1牌頭4面子 順序はシュンツ、コウツ、ジャントウの順で確認する
のがいいだろうと思いつく
10:10 シュンツ優先にすると11222333のパターンが駄目に気づく。
10:25 シュンツもコウツもいける用に再帰でチェックがいいのではと思いつき、
コーディング開始
11:10 関数完成
11:30 標準入力から受け取ったり、エラー処理も含めて、一応完成 
11:40 再度問題のページを開いてよく問題文を読むと待ち牌だけでなく、面子の
構成やどういう状態で待ちなのかも表示しないといけないことに気づく。
13:00 アガリを確認するのではなく、やっぱりテンパイを確認しないといけない
のかと思い直し、そうなると再帰は厳しいのかといろいろプログラムを弄りながら
試行錯誤するも、花見の時間なので諦める。
18:00  帰宅。テンパイかどうかは3面子1雀頭、もしくは4面子頭待ちのいづれか
だと気づく。また頭+コウツ+シュンツと並び順を固定すれば、すでに調査した
組み合わせの場合はじけると気づく
18:30 コーディング完了 30分のオーバー。ただなんとなく花見の時も考えてた
から、もっとオーバーかも。

下記がプログラムです。(ruby)
 #アガルために必要な面子数
  NEED_MENTSU=4
  #牌パイに存在する最大数
  MAX_NUM=9
  #同一数の牌パイの最大存在数
  MAX_HAI=4

  $kumiawase = {}
######################################################################
#指定された数字の牌を指定した数字分増減した牌パイのハッシュを作成し返却
######################################################################
def haipai_mod(orig,k,count)
  haipai = orig.clone
  if haipai[k]
    haipai[k] += count
  else
    haipai[k] = count
  end
  #同じ数字の牌が0個以下になることはあり得ないため。
  if haipai[k] < 0
    throw "count < 0"
  end
  #同じ数字の牌が最大数以上になることはあり得ないため。
  if haipai[k] > MAX_HAI
    throw "count > #{MAX_HAI}"
  end
  #定された牌の数が0個になった場合はhashからその数字の牌の存在を削除
  if haipai[k] == 0
    haipai.delete(k)
  end
  return haipai
end
#####################################
#残りの牌を待ちの仕様にあわせた文字列
#####################################
def machi(haipai)
  str = "["
  haipai.keys.sort.each do|k|
    str += k.to_s * haipai[k]
  end
  str += "]"
end
###########################################
#聴牌の場合は、面子と待ちを仕様に沿って表示
###########################################
def disp_tenpai(haipai,idx,mentsu,atama,str)
  #頭待ちの時は必ず聴牌
  if (mentsu == 4 and atama == 0)
    #面子と待ちの牌
    str = str + machi(haipai) + "\n"
    print str
    return
  end
  #1面子足りない場合は残りの牌に1~9までの数字を試す
  if (mentsu == 3 and atama == 1)
    #面子と待ちの牌を予め取得
    str = str + machi(haipai) + "\n"
    #残り牌に1~9の牌を付加
    9.times do |i|
      hai = i+1
      #残り牌今回の牌を付加
      new_haipai = haipai_mod(haipai,hai,1);
      #一番低い数字の牌を取り出す
      k = new_haipai.keys.sort[0]
      #コウツもしくはシュンツか?
      if new_haipai[k] == 3 or
         (new_haipai[k] == 1 and new_haipai[k+1] and new_haipai[k+2])
        #予め取得した面子と待ちの牌を表示
        print str
        return
      end
    end
  end
  (idx .. MAX_NUM).each do |k|
    next unless haipai[k]
    ret = false
    #頭がなく、頭にできる牌が見つかった場合
    if atama == 0 and haipai[k] >= 2
      new_haipai = haipai_mod(haipai,k,-2);
      new_str = "(#{k}#{k})" + str
      #すでに調査した組み合わせ(頭+面子)の場合スキップ
      unless $kumiawase[new_str]
        $kumiawase[new_str] = true
        #頭を除いた残りの牌で再帰
        disp_tenpai(new_haipai,k,mentsu,1,new_str)
      end
    end
    #コウツにできる場合
    if haipai[k] >= 3
      new_haipai = haipai_mod(haipai,k,-3)
      new_str =  "(#{k}#{k}#{k})" + str
      #すでに調査した組み合わせ(頭+面子)の場合スキップ
      unless $kumiawase[new_str]
        $kumiawase[new_str] = true
        #コウツを除いた残りの牌で再帰
        disp_tenpai(new_haipai,k,mentsu+1,atama,new_str )
      end
    end
    #シュンツにできる場合
    if haipai[k+1] and haipai[k+2]
      new_haipai = haipai_mod(haipai,k,-1)
      new_haipai = haipai_mod(new_haipai,k+1,-1)
      new_haipai = haipai_mod(new_haipai,k+2,-1)
      new_str =  str + "(#{k}#{k+1}#{k+2})"
      #すでに調査した組み合わせ(頭+面子)の場合スキップ
      unless $kumiawase[new_str]
        $kumiawase[new_str] = true
        #シュンツを除いた残りの牌で再帰
        disp_tenpai(new_haipai,k,mentsu+1,atama,new_str)
      end
    end
  end
end

hai = ARGV[0]
if hai !~ /^\d{13}$/
  throw "you should put 13 number between 1 and 9."
end
orig_haipai = {}
#各数字をキーにして、キーに対して存在する牌数を値にしたハッシュを作成
hai.split('').each do|h|
  orig_haipai = haipai_mod(orig_haipai,h.to_i,1)
end
#聴牌確認
disp_tenpai(orig_haipai,1,0,0,"")

やっていて一番思ったことは、コーディングしながら考えるのは非常に効率が悪いということ。 どういう処理をするかを頭の中で概念的に整理してからコーディングした方が断然速い。 最初はそうしていたのだが、仕様をよく読んでなかったせいで、後でやり直しになった際に つい作ったプログラムを弄りながら考えてしまったせいで、全然進まなかった。 花見でコーディングから離れているうちに考えが思いつき、後のコーディングはあっと いうまだった。

|

« LinuxでchrootによるJail環境を構築 | トップページ | LinuxでchrootによるJail環境を構築2 »

ruby」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/68673/47987181

この記事へのトラックバック一覧です: あなたのスキルで飯は食えるか?に挑戦:

« LinuxでchrootによるJail環境を構築 | トップページ | LinuxでchrootによるJail環境を構築2 »