2012/08/09

もう一回 数当てゲーム

数当て問題 - Hit & Blow -: ツムジのひとりごとで取り上げていただいたので、自分のコードと比べてみる。

このゲームの肝であるHitとBlowを求める処理のうち、まずはBlowから。
Blowは、「数字として当たっているし、場所(桁)も当たり」ということ。

countBlow :: String->String->Int
countBlow [] _ = 0
countBlow _ [] = 0
countBlow (x:xs) (y:ys)
          | x == y    = 1 + countBlow xs ys
          | otherwise = countBlow xs ys
  • 文字列を2つ受け取って、それぞれの先頭を比較する。一致していたら、戻り値に1を加える。
  • 文字列が終わりでなかったら、比較しなかった残りの文字列それぞれを引数にして、自分を呼び出す。
  • 受け取った文字列のうち、どちらかが空だったら、0を返す
で、それを
  • 文字列を2つ受け取って、それぞれの桁について、同じ数字だったらTrue、違ったらFalseにする→受け取った文字列と同じ長さの、Boolのリストができる
  • そのBoolのリストのうち、Trueの数がBlow
と考える。
そうすると、文字(Char)のリストである文字列を2つ受け取って、それぞれの要素に対して関数を適用する→zipWithの出番
また、BoolのリストでTrueを数えるのは
  • filterでリストのうちTrueのものだけにする
  • それからリストの要素数を数える
とすればよいので、

countTrue :: [Bool] -> Int
countTrue = length . filter (== True)

となる。
結局、Blowは

countBlow :: String -> String -> Int
countBlow target = countTrue . zipWith (==) target

で求められると。


次。Hit。
Hitは、「数字としては当たっているけど、場所(桁)は違う」ということ。
単純に「数字として当たっている」ものを数えてしまうと、Blowもカウントしてしまう。でも、Blowも求めるのだから、「数字として当たりの数」- Blow として求めればよい。
ということで、どうやって「数字として当たりの数」を求めるか?

isUsedNum :: Char->String->Int
isUsedNum _ [] = 0
isUsedNum a (x:xs)
             | a == x    = 1 + isUsedNum a xs
             | otherwise = isUsedNum a xs

countUsedNum :: String->String->Int
countUsedNum [] _ = 0
countUsedNum (x:xs) ys = isUsedNum x ys + countUsedNum xs ys

うーん、回りくどい。2つの文字列を引数として受け取って、1つ目の文字列を1文字ずつ、2つ目の文字列の構成要素か見ている(isUsedNum)。これも、文字列を1文字ずつ比較しているから、遅くなるはず。
こっちも、Blowと同様、「構成要素であればTrue」のリストを作って、最後にTrueの数を数えればいいわけだ。

countHit :: String -> String -> Int
countHit target = countTrue . map (`elem` target)

mapが肝かな?関数とリストを受け取って、リストの1つ1つの要素に対して関数を適用する(関数で処理する)。だから、mapの結果のリストって、与えたリストと同じ長さになる
で、mapにどんな関数を与えるかというと、target の構成要素かどうかを返す関数を与える。あとは、Trueの数を数えればOK。


リストの使い方がうまくない。まぁ、もっといろいろプログラム書いて慣れないとね。


0 件のコメント :

コメントを投稿

Comments on Google+: