はすけるとぱいそん

Project Euler 35

Haskell, Project Euler

問題はこちら。
この問題はネットを少々徘徊した限りでは、僕のコードが一番速かったです。
ちょっとうれしい。えへへ。すごいね！おにいちゃん！！！
（とりあえずうｐ。コメント、メモはあとでまた書こ）

import Data.List
import Data.Char


f :: [Int] -> Integer
f xs = read (map intToDigit xs) :: Integer

a :: [Integer]
a = 2:5:(map f $ concat $ map (nub.permutations) $ concat [ comb [1,3,7,9] x | x <- [1..6] ])

g:: Integer -> Integer
g n = read (map (intToDigit) (tail ns ++ [head ns]))::Integer
	  where ns = map (digitToInt) (show n)

h' :: Integer -> Int -> Bool
h' n c 
	| (c == length (show n)) = True
	| isPrime n = h' (g n) (c+1)
	| otherwise = False

h :: Integer -> Bool
h n = h' n 0

main = print $ length $ filter h a



--重複組み合わせ。
comb :: [a] -> Int -> [[a]]
comb _ 0 = [[]]
comb [] _ = []
comb (x:xs) n = map (x:) (comb (x:xs) (n-1)) ++ comb xs n


--素数の無限リスト。
primesList :: [Integer]
primesList = map fromIntegral primesList'
    where
      primesList' = [2, 3, 5] ++ f 5 7 (drop 2 primesList')
      f m s (p : ps) = [n | n <- ns, gcd m n == 1] ++ f (m * p) (p * p) ps
          where ns = [x + y | x <- [s, s + 6 .. p * p - 2], y <- [0, 4]]


--素数判定。
isPrime :: Integer -> Bool
isPrime n = (n > 1) && isPrime' primesList
    where
      isPrime' (x : xs)
          | x * x > n    = True
          | rem n x == 0 = False
          | otherwise    = isPrime' xs

ツイートする

Permalink | コメント(0) | トラックバック(0) | 15:29

Project Euler 34

Haskell, Project Euler

問題はこちら。
上限は7桁です。それ以上になるとだめです。
算数できないので最初何故だかよく解らなかったのですが（え、
実際計算してみたらそうでした。

import Data.List
import Data.Char


-- 階乗を求める。
-- f 5 で 120を返す。
f :: Int -> Int
f 0 = 1
f n = product [1..n]


-- 重複組み合わせ。リストの数字から重複を許してn個選ぶ。昇順になる。
-- comb [1,2,3] 2 で [[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]] を返す。
comb :: [a] -> Int -> [[a]]
comb _ 0 = [[]]
comb [] _ = []
comb (x:xs) n = map (x:) (comb (x:xs) (n-1)) ++ comb xs n


-- 2ケタ以上の数字を、桁のリストで表す。123は[1,2,3]となる。
-- [[0,0],[0,1],・・・[1,2,3],・・・[1,2,3,4]・・・]
a :: [[Int]]
a = concat [ comb [0..9] x | x <- [2..7] ]


-- 問題の条件に合うならTrue。bはそれに合うものをfilterしたリスト。
-- って言っても結局[[1,4,5],[0,4,5,5,8]]なんだけど。
g :: [Int] -> Bool
g xs = (sort $ show $ sum $ map f xs) == (sort $ map intToDigit xs)

b :: [[Int]]
b = filter g a


--ふぇぇ〜。つかれたあ〜。でもあともうちょっとだよ！おにいちゃん！
main = print $ sum $ concat $ map (map f) b

ネットを徘徊した限り、幾人かのスゴイ方のコードより若干遅いしメモリ喰ってますが、
まあ合格の範囲内かと。ってか、自分のPC遅すぎorz
「0.1secで出ました」ってコードを走らせると、自分のPCだと20secくらいかかりますｗ
ちなみにこのコードは0.3secくらいです。うん、合格だね！おにいちゃん！　
　

ツイートする

Permalink | コメント(0) | トラックバック(0) | 15:20

Haskell短期強化週間ひとまず終了！

Haskell, プログラミング日記

HaskellでEulerを55題クリアし、なんとか目標達成。つかれたあ。

今後ちょいちょい復習をしたり、時々新しい問題を解いたりするけれど、
とりあえず僕の頭の悪さではここまでが限界なようです。

次はHaskellで何やろうかな。何か作りたいけどなんだか無理そうorz
　
　

ツイートする

Permalink | コメント(0) | トラックバック(0) | 12:45