今回の三問はリスト内包表記を多用して解いたような印象。
Problem 31. Coin sums(硬貨の和)
2ポンドを作る組み合わせということは、単位をペンスに合わせると合計200ペンスとなる全ての組み合わせを出せばいい。最初、こんな感じで各硬貨のリストを作り、リスト内包表記で合計200となるもののみ抽出しようとした。
main = print $ length $ coinSums 200 pound1 = [0,1..200] pound2 = [0,2..200] pound5 = [0,5..200] pound10 = [0,10..200] pound20 = [0,20..200] pound50 = [0,50..200] pence1 = [0,100,200] pence2 = [0,200] coinSums :: Integer -> [(Integer, Integer, Integer, Integer, Integer, Integer, Integer, Integer)] coinSums n = [ (po1, po2, po5, po10, po20, po50, pe1, pe2) | po1 <- pound1, po2 <- pound2, po5 <- pound5, po10 <- pound10, po20 <- pound20, po50 <- pound50, pe1 <- pence1, pe2 <- pence2, po1 + po2 + po5 + po10 + po20 + po50 + pe1 + pe2 == n]一見うまくいきそうだったが…実行してみるといつまで経っても終わらない。
組み合わせのパターンが多過ぎるようだ。
そこで、このように修正してみた。
リスト内包表記で全ての組み合わせの中から合計200となるもののみ抽出する、という処理自体は変わっていないが、
合計200を超えることが分かっている組み合わせまで調べる必要はないので、
200からその前の組み合わせのパターンの合計値を引いた値までをリストの終端とした。
Problem 32. Pandigital products(パンデジタル積)
2つの数値の組み合わせで、isPandigital
関数が真となるもののみ抽出している。条件としては
[1..limit] == (sort $ map digitToInt $ numStr)
だけ調べれな十分なはずだが、それでは実行に時間がかなりかかり、掛ける前の数を
isUnique
関数で重複がないか調べたり、length numStr /= limit
で全ての値を連結した文字列の長さが9か調べたりと事前に条件に合致しないものを除外するようにしてみたところ、少し処理時間に改善が見られた。
数値の組み合わせをどこまで調べるかというのを
let limit = 9876
とかなり適当に定めてしまったが、これも数学的にここまで調べれば十分、という値を算出できるんだろうか…。
Problem 33. Digit canceling fractions(桁消去分数)
まずfractions
関数で、全ての2桁の数値の組み合わせから同じ数値を持つ組み合わせを抽出し、元の分数とその同じ値を消去した分数とが約分して同じ値になるものを
dcFractions
関数で抽出している。(書いていて気づいたが、別に
fractions
とdcFractions
を分けなくても一度に条件判断して抽出できそうだ。)分数の計算には
Data.Ratio
モジュールの%
演算子を使用した。> 2 % 3 == 6 % 9 True > product [1 % 2, 1 % 3] 1 % 6 > denominator $ 6 % 9 -- 分母を取る 3※追記:ブログを書いている途中で思いついた、
一度のリスト内包表記で桁消去分数と元の分数が等しいもののみ抽出する方法に書き換えてみた。
あまり良くない書き方だと思っていた
isJust
も行う必要が無く、スッキリしたように思う。