ザネリは列車を見送った ブログという名の備忘録

zaneli-eulerのisPrimeを修正。
この変更をしないと今回のProblem 58, 60 には使い物にならなかった。
従来は、まず調べたい値までの素数の全リストをprimes関数を使用して作っていたが、
それでは速度的に厳しかった。
調べ方がザルのような気もしたが、奇数のリストの中に割り切れる値が無いかを調べるほうが格段に速い。

Problem 58. Spiral 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なのは分かっているので固定値でも良かったかも)
その中の素数の数をnに加算していき、素数の割合が10%未満になればその時点での辺の長さを返す。
ここでZaneli.Euler.isPrimeを何度も呼んでいるが、従来の処理では非常に遅かったので修正。

Problem 59. XOR decryption(XOR暗号解読)

おお、Data.Bitsというモジュールを初めて使った。
大した事はしていないけど、
よく使うData.List, Data.Maybe, Data.Char, Data.Ordあたりのモジュール以外が登場すると何だか新鮮な感じだ。

まずcipher.txtから読み取った文字列をリストに変換する。
今回はスペースではなくカンマで区切りたいのでProblem 54で作ったsplitOnを再度利用した。
linesしてconcatMapはcipher.txtには1行しか内容が無いため不要なように思えるが
末尾の改行を考慮してこのようにしている。

次にkeysで暗号化鍵の候補となる3文字の小文字を生成する。
要素数を指定した順列、Data.List.permutationsのように標準で用意されているかと思ったが
多分無い？ので自作してみた。

読み取ったリストと鍵(をcycleした無限リスト)をzipで組にして
暗号化された文字はreadで数値に、鍵となる文字はfromEnumでASCIIコードに変換して
1文字ずつxorで復号していく。

「平文はよく用いられる英単語を含んでいる」から出題の意図に沿うかどうか不明だったが、
単語「the」が含まれるかどうかをcontainsで判定して復号したとみなすことにしてみた。
いくつか解答している人のコードを参考にしてみたが、同じように単語で判定しているか
英文における頻出文字(こちらによるとe, t, a, o, i, nなどの順？)を利用しているかだった。

15秒程度と、ちょっと時間がかかっている印象があるのでもう少し高速化する方法はあるかな…。

その後、教えていただいたこれとこれを元に書き直してみた。
いくつか初めて使う関数が出てきた。
keysの作り方を2パターン教えてもらい前者を採用したが、後者のsequenceは何をやっているのか。

> :t sequence
sequence :: Monad m => [m a] -> m [a]

> sequence [[1,2,3], [4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]

> sequence [[1,2,3], []]
[]

> sequence [Just 1, Just 2, Just 3]
Just [1,2,3]

> sequence [Just 1, Nothing, Just 3]
Nothing

…ふむぅ、なるほど。この辺も理解を深めるのに参考になりそうだ。

breakはBoolを返す関数がTrueになる最初の要素以降をsndとするペアにしてくれるのか。
isInfixOfはリストを2つ渡して1つめのリストが2つめに含まれていればTrue。
これらは知らずに回りくどい書き方をしてしまっていたな。
breakは全ての要素がFalseならペアのfstが元のリストそのまま、sndが空リストになるが、
tailしていたところをdrop 1にして空リストでも例外が飛ばないようにすることで、splitOn'のガードが１つ減って
見通しが良くなったと思う。

さらにこれとこれとこれを元に高速化バージョン。
isPrintとisSpaceでフィルタすることで、8秒ほどかかっていた処理が0.1秒程度と大幅に向上できた。

> isPrint 'a'
True
> isPrint ' '
True
> isPrint '\t'
False
> isPrint '\n'
False

> isSpace 'a'
False
> isSpace ' '
True
> isSpace '\t'
True
> isSpace '\n'
True

せっかくなのでkeysはsequenceを使ったものに書き換えてみた。

Problem 60. Prime pair sets(素数ペア集合)

処理の高速化にだいぶ苦戦した…。
primesで素数を作りながら条件に合うものを探している。
Zaneli.Euler.primesを使えば良かったが、
条件に合うかどうかを判定するsearchが時間のかかる処理で、
かつ第二引数のリストを元に判定しているのでこれが変更(新しく素数が追加)された場合のみ呼びたいため
ガードの順番を入れ替えて別途定義した。
しかし何とか共通化したいものだ。
「第二引数のリストを元に判定」する場合、今回以外でも効率が悪くなりそう。

searchでは、第一引数の素数(primesのガードの順番により、この値は素数)と任意の順で繋げて
素数となるものを第二引数の素数のリストからフィルタし、
そのフィルタした素数のリストの中からお互い同士も同じ条件を満たすものをconcatPrimesで4つ選び出している。
(問は5つの素数の集合の和だが、第一引数との条件を満たす事を判定済みのため)
filterConcatPrimesを2箇所で行っているのが微妙だが、
処理高速化のため試行錯誤の末このようになった。