HaskellでProject Euler(Problem 58～60) | ザネリは列車を見送った
zaneli-eulerのisPrimeを修正。 この変更をしないと今回のProblem 58, 60 には使い物にならなかった。 従来は、まず調べたい値までの素数の全リストをprimes関数を使用して作っていたが、 それでは速度的に厳しかった。 調べ方がザルのような気もしたが、奇数のリストの中に割り切れる値が無いかを調べるほうが格段に速い。 まずspiralDiagonalsで渦巻きの対角線上の数値と、その時点での辺の長さを持つ無限リストを作っている。 > take 3 spiralDiagonals [(3,[3,5,7,9]),(5,[13,17,21,25]),(7,[31,37,43,49])] その無限リストに対してsearchで条件に合うものを探す。 対角線上の値をdに加算していき、(length nsとしているが全て4なのは分かっているので固定値でも良かったかも) その中の
99 Haskell Problems より、[31] でもその前に - Qiita
追記 Qiita の記事の中にすでにもっと早くてエレガントなコードを書いていらっしゃる記事を見つけました。 Haskell で「素数列」をつくる。 なお、さらに元ネタはこちらだそうです。 エラトステネスの小型高速遠心分離機 コメントにも有りましたが、これらの実装も実はエラトステネスのふるいではなく（Haskell の遅延評価のせい？）いわゆる試し割りということになるそうですが、コードゴルフにも採用されてる位短くてかつ早いとなると、、、 一見したところ何をしているか分からなかったのでちょっと紐解いてみます、以下本質的にはHaskell で「素数列」をつくる。からのコピペです、ちょっと型とか二乗とか改変していますが（手元の環境では違いが出ませんでしたが、もしかしたら高次の影響があるかも分かりません、掛け算の方が安価なのかも） Fast primes from http://qiita.com/
![99 Haskell Problems より、[31] でもその前に - Qiita](https://cdn-ak-scissors.b.st-hatena.com/image/square/74874ac1b650d6c3416e332809810cc19f2aab62/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fqiita-user-contents.imgix.net%252Fhttps%25253A%25252F%25252Fcdn.qiita.com%25252Fassets%25252Fpublic%25252Farticle-ogp-background-afbab5eb44e0b055cce1258705637a91.png%253Fixlib%253Drb-4.0.0%2526w%253D1200%2526blend64%253DaHR0cHM6Ly9xaWl0YS11c2VyLXByb2ZpbGUtaW1hZ2VzLmltZ2l4Lm5ldC9odHRwcyUzQSUyRiUyRnFpaXRhLWltYWdlLXN0b3JlLnMzLmFtYXpvbmF3cy5jb20lMkYwJTJGODQwNzQlMkZwcm9maWxlLWltYWdlcyUyRjE0NzM3MDI5ODA_aXhsaWI9cmItNC4wLjAmYXI9MSUzQTEmZml0PWNyb3AmbWFzaz1lbGxpcHNlJmZtPXBuZzMyJnM9MjQ3MTJhNjBiMDYyYjcyOTVhMGZhOWZiZDY0NDRjZDA%2526blend-x%253D120%2526blend-y%253D467%2526blend-w%253D82%2526blend-h%253D82%2526blend-mode%253Dnormal%2526s%253D075908c02c17ec0b5d54406ff4d367d4%3Fixlib%3Drb-4.0.0%26w%3D1200%26fm%3Djpg%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTk2MCZoPTMyNCZ0eHQ9OTklMjBIYXNrZWxsJTIwUHJvYmxlbXMlMjAlRTMlODIlODglRTMlODIlOEElRTMlODAlODElNUIzMSU1RCUyMCVFMyU4MSVBNyVFMyU4MiU4MiVFMyU4MSU5RCVFMyU4MSVBRSVFNSU4OSU4RCVFMyU4MSVBQiZ0eHQtYWxpZ249bGVmdCUyQ3RvcCZ0eHQtY29sb3I9JTIzMUUyMTIxJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTU2JnR4dC1wYWQ9MCZzPWYxZmQzY2E1YmEwMTdlOWE0ZWI2NTg3YmZmNGUzMjZk%26mark-x%3D120%26mark-y%3D112%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTgzOCZoPTU4JnR4dD0lNDBicmFfY2F0X2tldCZ0eHQtY29sb3I9JTIzMUUyMTIxJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTM2JnR4dC1wYWQ9MCZzPWVmYTYzMzQxYzUyYjYxMGYzYjg3NDlmMzgxZWYxZWRh%26blend-x%3D242%26blend-y%3D480%26blend-w%3D838%26blend-h%3D46%26blend-fit%3Dcrop%26blend-crop%3Dleft%252Cbottom%26blend-mode%3Dnormal%26s%3D5765ae18ffd4ed4106c9071a23b23c9a)
Haskellで無限個の無限リストをソートされた形で結合する - プログラムモグモグ
CodeforcesやProject Eulerの問題には、無限リストをうまく使うと綺麗に解くことができる問題がたくさんあります。 数列の性質から探索範囲の上界を決めて解を探索することが多いのですが、きちんとした根拠を持って上界を決めることができることは少なく、余裕を持って十分に広い範囲で計算して解を求める解法がよく取られます。 Haskellの特徴である遅延評価とその洗練された糖衣構文を用いると、無限リストを簡単に扱うことができます。 上界を適当に定める解法よりも、より宣言的で美しく、時に効率的なコードで同じ解を得ることができます。 しかし、無限リストをきちんと、それも無限個の無限リストをきちんと扱うとなると、意外と苦労します。 この記事では、無限個の無限リストをソートされた形で結合する方法について説明します。 一般的な無限リストではなく、条件はかなり絞っていてます (そうでないと原理的
HaskellでProject Euler(Problem 52～54 補足) | ザネリは列車を見送った
Data.Function.onという、バシッと決まれば格好良さそうなやつを教わったので バシッと決まる使いどころを探そう。 そうか、splitOnを自作せずとも、スペース区切りの場合ならwordsがあった。 fromEnum (Rank 1) = fromEnum (Rank 13) + 1とすることでエースを13より大きい値として扱えるようにした。 こういう場合、toEnumはどうするのが良いのだろう？何となく対称性を持たせてはみたが。 また、sameRanks関数などを使ってワンペア・ツーペア・スリーカード・フルハウスなどを判定していたが、 あらかじめ同じ数字ごとにグループ化して要素数でソートしておき、パターンマッチで役を判定できるようにしてみた。 Data.Ord.comparingを使って compare = comparing fromEnum、sortBy (flip $ c
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Optimizing longest Collatz chain in Haskell
