もっとエレガントな書き方ありそうだなあ…と思いつつゴリ押しで解くオイラー。
Problem 61. Cyclical figurate numbers(巡回図形数)
うーん…長い(のは仕方ないかもしれないけど)し、再帰の呼び出し方がイマイチで無駄に複雑になってしまった気がする。triangles
など三角数のリストを作る関数を用意し、digitRange
で無限リストから4桁の要素(1000~9999の範囲の要素)のみ取り出すようにした。あとは、八角数のリストから始めて、候補となる
candidates
の中から巡回数(前後半2桁が重なる数値)を探し出している。candidates
は三角数~七角数までの全リストから作り、タプルの2要素目でn角数か分かるようにしておき、同じn角数から一度巡回数を取り出せば候補からn角数の要素を全て取り除いて処理を続けるようにしている。
一応解けたが
appendCyclics
, appendCyclic
が何だかまどろっこしい形になってしまったように思う。少し考えて別バージョンも書いてみた。
candidates
を作るところまでは同じで、n角数のリストの中から巡回数を探し出すところをリスト内包表記で書いてみた。
手続きっぽい書き方になった。
どちらが良いとも言えないが、まぁこんな書き方もあるという事で。
多角数を求める関数を
polygonal
にまとめることで全体的に短くしたものがこちら。Problem 62. Cubic permutations(立方数置換)
最初にこんな感じで書いてみた。import Data.List (find, permutations) import Data.Maybe (mapMaybe) import Data.Set (fromDistinctAscList, fromList, intersection, size) main = print $ head search search :: [Integer] search = mapMaybe (\(n, m) -> search' n m cubes) $ iterate (\(n, m) -> (n*10, m*10)) (1, 10) where search' n m = permuted 3 . dropWhile (何をやっているかというと、同じ桁の立方数のリストごとに、一要素ずつInt -> [a] -> Maybe a permuted cnt cubes = find (\m -> cnt == (size $ intersection cubes' $ perms m)) cubes where cubes' = fromDistinctAscList cubes perms = fromList . map read . permutations . show
perms
で置換した数のリストを作り、候補となる立方数の中に重複する要素がcnt個あればそれを解としている。
が、これは遅い…終わらない…。
permuted 3
の場合、何とか20秒台で完了するが、permuted 4
でもう駄目。ちなみに一旦Setにせず
Data.List.intersect
で重複要素を取ると2倍ほど時間がかかる…。よくよく考えると、各要素に対していちいち
permutations
してからcubes
との重複を一つ一つ調べるなんていう事はしなくてもcubes
の中だけで調べることができる事に気づいたので、このように書いてみた。各桁の数値が同じものを
groupBy
して、要素数が5であればそれが解になる。grouping
とsorting
でほぼ同じ事をやっているのが気になるが、これは仕方ないかな…。これを参考に書き換えたのがこちら。
groupBy
に使うための文字列と、元の数値をどちらも保持しておくというやり方。こういう手法をシュワルツ変換というらしい。
また一つ勉強になった。
Problem 63. Powerful digit counts(べき乗の桁の個数)
問題そのまんまHaskellのコードに落とし込んだらこんな感じになった。n乗した桁数がnである要素数を数えている。
特にヒネりも無いが、こんなんで良かったかな…。
書いていて気づいたけど、最初に自然数の無限リストを対象に
map
してtakeWhile (>0)
で打ち切る、つまりn乗した桁数がnと一致する要素が無い場合それ以降調べないようにしているがこれで良かったのだろうか?
正解にはなったけれど、nには条件を満たす要素が無く、n+1以降には条件を満たす要素があればこれでは成り立たないな…うーむ。
…と思っていたが、こちらのコメントの通り問題はないという事だった。
m < 10ということは、
length $ filter (==n) $ takeWhile (<= n) $ map powerLength [1..]
のところは、length $ filter (==n) $ map powerLength [1..9]
でも良さそうだ。実際書き換えてみたら同じ結果となった。