http://projecteuler.net/index.php?section=problems&id=204 普通の解法。 import Number ham xs = h where h = 1:foldr1 merge [map (x*) h|x<-xs ] main = print.length.takeWhile(<=10^9) . ham .takeWhile(<100) $ primes

http://projecteuler.net/index.php?section=problems&id=92 ナイーブな解法でも解けたが、少し遅かったので、ちょっと改良。 import Data.Char (digitToInt) import Data.List (group) next :: Int -> Int next = sum.map (^2).map digitToInt.show choose …

単純な全探索、遅すぎる。 import Number import Data.List divsSum x = (flip(-)x).product.map f.group.factors$x where f ps@(p:_) = let n = genericLength ps + 1 in (p^n-1)`div` (p-1) chain m = chain' [] . iterate divsSum where chain' xs (y:ys)…

http://projecteuler.net/index.php?section=problems&id=89 はじめは、入力として、 IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII みたいなものもあるのかと思っていた。 import Data.List import Data.Maybe roman [] xs = xs roman ((r,s):rs) xs | i…

ghc-6.10.1を入れたので、 {-# OPTIONS_GHC -fglasgow-exts #-} main = 素数 `を` 10 `個` 見せる where 素数 = 篩 [2..] 篩 (素数:残り) = 素数 : 篩 [数|数<-残り,数 `割り切れない` 素数] 割り切れない 被除数 除数 = mod 被除数 除数 /= 0 を xs n = ret…

インストール（コンパイル）はできた。しかし、hmatrixをつかったコードがコンパイルできない。例えば import Numeric.LinearAlgebra.Tests main = runTests 20 をコンパイルすると、以下のエラー C:\unix\ghc\ghc-6.8.2\hmatrix-0.5.0.1\ghc-6.8.2/libHShma…

http://projecteuler.net/index.php?section=problems&id=91 三角形だと思ったら、直角三角形だった。 import Data.Array import Data.List p091 m = length [(a,b)|a<-area,b<-takeWhile(

http://projecteuler.net/index.php?section=problems&id=90 組み合わせを数えるときも、6と9を区別しないのかと思っていたり、同じ数字が二度以上出てくると思っていたり。 まったく、これだから英語の問題は squ = [[(0,1)],[(0,4)],[(0,9),(0,6)],[(1,6),…

http://projecteuler.net/index.php?section=problems&id=87 ナイーブな方法で解けた。遅いけど。 import Number import Data.List import Data.Array.IArray import System primesS = map (^2) primes primesC = map (^3) primes primesF = map (^4) primes…

http://projecteuler.net/index.php?section=problems&id=86 英語難しいです。 最短を忘れていたり、組ではなく並びかと思ったりと。 import Data.List cuboid m = sum[div2 n m |n<-[2..2*m-1],isIntSqrt$n*n+m*m] div2 n m | n > m = div (2*m-n+2) 2 | n …

http://projecteuler.net/index.php?section=problems&id=85 効率の良い解法ではないが、コードは短いし、単純。 main =print.minimum$[(abs$8*10^6-a*(a+1)*b*(b+1),a*b)|a<-[1..ceiling.sqrt$8*10^6],b<-[1..a]]

http://projecteuler.net/index.php?section=problems&id=88 調べる範囲が2~12000なので、product-sumの値は高々20000だとした。実際そうだった。 あまり速くない。やはり、Arrayはあまり速くないのか？ import Data.List import qualified Data.Set as S im…

http://projecteuler.net/index.php?section=problems&id=84 モノポリーのどのマスに止まりやすいか、という問題。 マルコフ連鎖だとおもう。ただ、状態数が120ぐらいある。 遷移行列を求めるのが面倒だ、というか面倒そう。 import Data.List import Data.A…

目標：HackageDBからパッケージをインストール HackageDB:http://hackage.haskell.org/packages/hackage.html まず、どんなパッケージが利用できるのかを調べる方法。 ghc-pkg listこのページを参考にした。http://www.hmatrix.googlepages.com/installation…

Dijkstraで解く。 前と全く同じ。 むしろ、補助頂点の数が少ないので楽とも。 import Dijkstra import Data.Graph import Data.Array.IArray w = 80 xi (i,j) = w*i+j mkGraph = buildG (0,w*w).((w*w,0):).concatMap e$range b where b = ((0,0),(w-1,w-1))…

Dijkstraで解く。 先と同様。 import Dijkstra import Data.Graph import Data.Array.IArray w = 80 xi (i,j) = w*i+j mkGraph = buildG (0,w*w+1).(s++).(t++).concatMap e$range b where b = ((0,0),(w-1,w-1)) e (i,j) = [(xi (i,j),xi x)|x<-[(i-1,j),(i…

Dijkstraで解く。 import Dijkstra import Data.Graph import Data.Array.IArray w = 80 xi (i,j) = w*i+j mkGraph = buildG (0,w*w).((w*w,0):).concatMap e$range b where b = ((0,0),(w-1,w-1)) e (i,j) = [(xi (i,j),xi x)|x<-[(i+1,j),(i,j+1)],inRange…

http://projecteuler.net/index.php?section=problems&id=81 ものすごくそのままなDP import Data.Array.IArray import Control.Monad root ::Array (Int,Int) Integer->Array (Int,Int) Integer root cost = r where r = listArray b [c ix | ix <- range b…

http://projecteuler.net/index.php?section=problems&id=80 どっかで調べた開平法を実装。 探索範囲が狭いから楽。 import Data.List root m =root' m 0 root' n a = b : root' n' a' where b = head [c|c<-[9,8..],(a+c)*c < n] n' = (n-(a+b)*b)*100 a' =…

http://projecteuler.net/index.php?section=problems&id=79 とりあえず、最短なので、各数字は高々一回しか現れないと勝手に解釈。 あとはそのまま。 import Data.Char import Data.List import Control.Monad import Data.Graph p079 xs =flip intersect u…

Dijkstra まだ一度も走らせていない。 たぶんバグあり。 module Dijkstra where import Data.List import Data.Graph import Data.Array.IArray import Debug.Trace import qualified Data.Set as Set type Weight = Array Edge Int -- g=graph, w=weight, d…

http://projecteuler.net/index.php?section=problems&id=77 Problem 76とまったく同じ方針で解ける。 まず再帰。 count x = count' x primes count' x (p:ps) | x > p = count' (x-p) (p:ps) + count' x ps | x ==p = 1 | x < p = 0 そして、DPに書き換える…

http://projecteuler.net/index.php?section=problems&id=76 まず再帰で書き下す。計算時間は指数時間。 count (x+1) = count' (x+1) x count' 0 _ = 1 count' _ 1 = 1 count' x m | x > 0 = count' (x-m) m + count' x (m-1) | x < 0 = 0 この再帰をDPで書…

http://projecteuler.net/index.php?section=problems&id=75 普通に数える。 import Data.List pythagoras l = [2*m*(m+n)|m<-[1..floor.sqrt.fromInteger.div l$2], n<-[1..min m$div l (2*m) - m],gcd m n ==1,even m || even n] p075 l = length.concat.f…

http://projecteuler.net/index.php?section=problems&id=78 今までと同じ方法はかなり時間がかかる。 まぁ、そこで、google先生ですよ。 結果できたのが下。 import Data.List import Data.Array.IArray import Data.Maybe import Control.Monad ini = arra…

分割統治を使ってO(N*log N)になるそうな。 分割統治と聞いたら、反射的に平面を二分して〜 とここまでは誰も思う。と思う。 しかし、この後のマージの処理が説明を読んでも意味不明でした。

http://projecteuler.net/index.php?section=problems&id=70 ナイーブな方法。brute force 答えは出るが、遅い。これはよろしくない。 import Number import Data.List import Control.Arrow phi = product.map f.group.factors where f ps@(p:_) = let n = …

http://projecteuler.net/index.php?section=problems&id=69 n/Φ(n)をnの素因数で表現すれば、どれが最大かは自明。 つまり、nの素因数をとするとき import Number main = print.last.takeWhile(<1000000).scanl1(*)$primes

なかなか面白そうだ。 不確定状況下での意思決定とかに応用しようと思えばできそうではある。きれいに解けるかはまったく分からないが。

http://projecteuler.net/index.php?section=problems&id=74 いわゆる、すなおなアルゴリズム。 よって、遅い。 import Data.List import Data.Char next = toInteger.sum.map (f.digitToInt).(show::Integer->String) where f n = product [1..n] link = le…