Project EulerでF#の勉強をしました（Problem8～10編） #ProjectEuler

はじめに

この記事は以下の記事の続きです。
Project EulerでF#の勉強をしました
（Problem1～3編）
（Problem4～5編）
（Problem6～7編）
（Problem8～10編）
手元でしか動かしていないので、間違いがあったら指摘を頂けると喜びます。

Problem 8

次の1000桁の数字のうち, 隣接する4つの数字の総乗の中で, 最大となる値は, 9 × 9 × 8 × 9 = 5832である.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
略。

この1000桁の数字から13個の連続する数字を取り出して, それらの総乗を計算する. では、それら総乗のうち、最大となる値はいくらか.
EX 6桁の数123789から5個の連続する数字を取り出す場合, 1*2*3*7*8と2*3*7*8*9の二通りとなり, 後者の2*3*7*8*9=3024が最大の総乗となる.

let target =
    "73167176531330624919225119674426574742355349194934\
    96983520312774506326239578318016984801869478851843\
    85861560789112949495459501737958331952853208805511\
    12540698747158523863050715693290963295227443043557\
    66896648950445244523161731856403098711121722383113\
    62229893423380308135336276614282806444486645238749\
    30358907296290491560440772390713810515859307960866\
    70172427121883998797908792274921901699720888093776\
    65727333001053367881220235421809751254540594752243\
    52584907711670556013604839586446706324415722155397\
    53697817977846174064955149290862569321978468622482\
    83972241375657056057490261407972968652414535100474\
    82166370484403199890008895243450658541227588666881\
    16427171479924442928230863465674813919123162824586\
    17866458359124566529476545682848912883142607690042\
    24219022671055626321111109370544217506941658960408\
    07198403850962455444362981230987879927244284909188\
    84580156166097919133875499200524063689912560717606\
    05886116467109405077541002256983155200055935729725\
    71636269561882670428252483600823257530420752963450"

let euler008 = 
    seq { for c in target -> int c - (int '0') }        //①
    |> Seq.windowed 13                                  //②
    |> Seq.map (fun window -> window |> Seq.reduce (*)) //③
    |> Seq.max                                          //④

変な声出た。
1000ケタ・・・？　何・・・？　1000ケタか・・・おう・・・という様子。

正直「これどうすんの・・・」となってしまったので超ググりました。シーケンス式を初めてまともに使いました。
listと比べて定義の仕方と対応した関数の差くらいしか違いを感じていませんが、慣らしていくとします。

中身に関しては、
①seq{}の定義はforeachみたいにcが1文字ずつ抜き出してくれるのでそれを1字ずつintにして、
　(少し呪文があり躓いたのでそれは後述)
②Seq.windowed 関数で13ケタずつ抜き出します。完全にこの問題にドンピシャの関数だなと思って震えました。
　文字列検索あたりに便利な関数ということなんでしょうか。
③そのあと13抜き出しごとにreduce関数で全部をかけ合わせて求めたい値にします。
　(seq{seq{int}}の状態で、外のseqにmap、内のseqにreduce)(このseqの書き方が正しいかは不明です)
④で、max。
といった動きでした。Seqメンバーが魔法ですね・・・。

それから、①で呪文といったくだりですが、ラムダ式内の以下の部分。

  //seq{ for c in target ->
    int c - (int '0')
  // }

int cじゃダメなん・・・？という。
よって色々試しました。

> let tagseq = seq{ for c in target -> c}
- tagseq |> Seq.map (fun d -> int d ) |> printfn "%A"
- tagseq |> Seq.map (fun d -> int d - 0) |> printfn "%A"
- tagseq |> Seq.map (fun d -> int d - (int '0')) |> printfn "%A";;
seq [55; 51; 49; 54; ...]
seq [55; 51; 49; 54; ...]
seq [7; 3; 1; 6; ...]

> 0 = (int '0') |> printfn "%A"
- 0 |> printfn "%A"
- (int '0') |> printfn "%A";;
false
0
48

といったところまでやって納得です。
昔Cでやった覚えがあります。charに"a"入れて"%d"で出力するやつ。
アレと似たようなもんか～～～～～？？？？と思って収めておきました。

Problem 9

ピタゴラス数(ピタゴラスの定理を満たす自然数)とは a < b < c で以下の式を満たす数の組である.
a^2 + b^2 = c^2
例えば, 3^2 + 4^2 = 9 + 16 = 25 = 5^2 である.
a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する.
これらの積 abc を計算しなさい.

let returnDivisorList dividend =
    let rec inReturnDivisorList n dList =
        if n > (dividend|>float|>sqrt|>int) then
            dList
        else
            inReturnDivisorList (n+1) (if dividend%n = 0 then dList@[(n,dividend/n)] else dList)
    inReturnDivisorList 2 [(1,dividend)]

let p2 x = pown x 2

let Problem8 =
    returnDivisorList 500 
    |> List.map (fun (x,y) -> (x,y-x)) 
    |> List.filter (fun (m,n) -> m>n)
    |> List.map (fun (m,n) -> (fun m n -> (p2 m - p2 n,2*m*n,p2 m + p2 n)) m n)
    |> List.find (fun (a,b,c) -> (p2 a + p2 b) = p2 c)
    |> fun (a,b,c) -> a,b,c,a*b*c
//val Problem8 : int * int * int * int = (375, 200, 425, 31875000)

(a, b, c) = (m^2 - n^2, 2mn, m^2 + n^2)

 (m^2 - n^2)^2 + (2mn)^2 = (m^2 + n^2)^2

 m(m+n) = 500

ピタゴラス数の性質 - wikipedia ←このへんを使って式がこうなりました。

という前提を持ちながら、
returnDivisorList関数で500の除数の組を求めて、あとは式変形です。
なんだか全体的にゴチャゴチャしてしまった気がします。
ゴチャゴチャしすぎてpownの省略を定義する始末。（カリー化と言っておきます）（かっこいい）
これまでで一番タプルを重用したように感じていますが、
なんだか式変形をそのまま書いていけたような気がします。よいですね。（ゆえにゴチャる）

あと、解いている最中に|> List.filter (fun (m,n) -> m>n)を挟み込んだわけですが、
数学的にこのへんの処理が絶対必要なのかどうとかが、あまりよくわかっていません。
aがマイナスになる組み合わせが出てきてしまったりしたので挟んだだけという。

Problem 10

10以下の素数の和は 2 + 3 + 5 + 7 = 17 である.
200万以下の全ての素数の和を求めよ.

let Problem10 = SieveOfEratosthenes 2000000L |> List.sum
//val Problem10 : int64 = 142913827499L

最終問題、1行。

いやこれまでの問題で定義した関数を使ったから、という側面はあるわけですが。
とはいえ途端にストレートな設問になりましたね。これだけでは寂しいので、自作エラトステネスの篩を再掲しておきます。
Problem1~3に戻るの面倒ですよね。（謎配慮）

let SieveOfEratosthenes (max:int64) =
    let rtMax = (max|>float|>sqrt|>int64)
    let rec inSieveOfEratosthenes ps ns =
        match ns with
        | [] -> ps
        | head::body when head > rtMax -> ps@body
        | head::body -> inSieveOfEratosthenes (ps@[head]) (List.filter (fun x -> (x % head <> 0L)) body) 
    inSieveOfEratosthenes ([]:int64 list) [2L..max]

脱int64にしたいな・・・などと思いつつ、今回は終えておきます。

おわり

というわけで、宣言していたProblem10までを終えました。
なんだかんだでProblem8(1000桁)あたりも1度やっておくのは良いことかなと思います。

一週間くらいの興行(興行？)になりましたが、
わりと飽きずに平日も記事を起こすことが出来て楽しかったです。
もう全く流行っておらず、好きな人たちも通り過ぎたような気がするF#ですが、
各記事100viewくらいありました。ありがとうございました。「Elixirやれよ」とか聞こえる。聞こえない。

そんなこんなで、今はコンピュテーション式あたりを攻略しようとしています。
とりあえずBindとReturnだけなんとかして俺も「モナドわかった」って言うんや・・・というモチベーション。
ちょっと他も勉強しないといけないことがあったり(Unity C#)して、それに疲れたらF#かな、となりそうですが。

どちらにしても最近は土日が楽しみで仕方がないです。
土日プログラミングに漬かるんや～～とか思いながら平日働いています。
また何かネタがあったら、書きにきます。

では、
ご指導してくださる方がいらっしゃれば、よろしくお願い致します。