もっとエレガントな書き方ありそうだなあ…と思いつつゴリ押しで解くオイラー。
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であればそれが解になる。
groupingsortingでほぼ同じ事をやっているのが気になるが、これは仕方ないかな…。

これを参考に書き換えたのがこちら。
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]でも良さそうだ。
実際書き換えてみたら同じ結果となった。

Copyright© 2011-2021 Shunsuke Otani All Right Reserved .