or1ko's diary

日々を書きます

Project Euler - Problem 24

Problem 24 は結構、手間取った。総当たり戦で解こうと頑張ったのが敗因。だいたいの計算量を考えながらプログラム作らないといけないとつくづく感じた。

r とか t とか変な関数名をつけてしまった。でも、こういう自分が適当に作った関数の名前の付け方って難しい。ちなみに r は再帰関数だから r (笑)。t は transform(変換) の t。tも再帰関数ですけどね...。

whereの箇所はletの方が適切っぽい*1のですが、私的にwhereの方が使いやすくて見た目も好きなのでwhereにしてます。

import Data.Char (intToDigit)

p24 :: String
p24 = map intToDigit t'
	where
		rank = 1000000 - 1
		m = 10 - 1
		r' = r rank m
		t' = t r' [0..m]

t :: [Int] -> [Int] -> [Int]
t [] ms = ms
t (n:ns) ms = [n'] ++ (t ns (filter (n' /=) ms))
	where
		n' = ms !! n

r :: Int -> Int -> [Int]
r n 0 = []
r n m = [d] ++ (r o (m-1))
	where
		(d,o) = divMod n $ frac m

frac :: Int -> Int
frac n = foldr (*) 1 [2..n]

main :: IO ()
main = print p24

*1:式を定義するときはwhereで、変数の定義だけならletでしょうか