--/--/--

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

2008/10/31

ubuntu 8.10

そういや今日リリースか。とりあえず 8.04 のサポート期限が過ぎるか、なにか不自由を感じるまで upgrade はやめとくかな。

2008/10/30

Project Euler: Problem 23

Problem 23

相当苦戦した。色々試すも、全て計算が終わらない。結局scheme による解答を見た。なるほど set をこのように使うのだな。

リンク先では sorted list による set を用いているが、本プログラムでは IntSet なるモジュールを使ってみた。ドキュメントの英語の意味が分からないのだけど、union や intersection に強いということなので。

実行結果

$ time ./23
4179871

real 0m35.947s
user 0m35.870s
sys 0m0.060s

プログラム

 1 import Data.IntSet (fromList,toList,union,insert,empty,fold)
 2
 3 divisors x = filter ((== 0. (mod x)) [1..(x `div` 2)]
 4
 5 abundants x = fromList $ filter isAbundant [1..x]
 6
 7 isAbundant x = x < (sum $ divisors x)
 8
 9 sumOfTwoAbundants n =
10   let abus = abundants n
11     in fold (\x acc -> union acc (f abus x)) empty abus
12   where f abus x = fold (\y acc' -> if x + y <= n
13                                       then insert (x+y) acc'
14                                       else acc')
15                         empty
16                         abus
17
18 fn = (sum [1..n]) - (sum' $ sumOfTwoAbundants n)
19   where n = 28123
20         sum' = fold (+0
21
22 main = print $ fn

2008/10/30

vim スクリプトの <SID> の意味

:help script-local に書いてあった。s: と関数名に付け、<SID> を付けて呼び出すと、同じスクリプトファイル内で関数名が一致する関数を呼び出す仕組みとのこと。複数のスクリプトを読み込んだとき、関数名が重複して曖昧になってしまうのを避けるため?らしい。名前空間用意しろと。

2008/10/29

vim から GHCi に現在のバッファをロードする

:!ghci % とやるのが面倒になったので、そういう map を作った。バッファをロードせず、ただ GHCi を起動する map も合わせて作った。ちょっと型のチェックをしたいときや、関数の単体動作確認したい時なんか便利。

vim スクリプトで定義する関数の前に付けるプレフィックスの意味は、未だに分からない。

使用する際には、filetype plugin on を vimrc に書いておかなければならない。

$HOME/.vim/ftplugin/haskell.vim

 1 nmap ,l :call <SID>LoadGHCi()<CR>
 2
 3 function s:LoadGHCi()
 4   w
 5   !ghci %
 6 endfunction
 7
 8
 9 nmap ,nl :call <SID>GHCi()<CR>
10
11 function s:GHCi()
12   !ghci
13 endfunction

,l で現在のバッファを GHCi にロードする。,nl でバッファのロードは行なわず、GHCi を起動する。

2008/10/29

Project Euler: Problem 22

Problem 22

アルファベット文字列から数値への変換を容易にするため、アルファベットの Enum なデータ型を用意した。Enum#toInt とがそのまま使えるので、変換処理が簡潔になる。また、文字からシンボルへの変換は、ord と fromInt を組み合わせることで、これまた簡潔になる。こんな感じで、問題の本題については、かなり簡潔に書けたと思う。(2つ目のハイフンより上まで)

面倒だったのはファイルからのリスト構築。" とゴミで入った \n を消去し、"," で split する。こういう関数ってないのかな。いや絶対あるだろう。

実行結果

$ runhaskell 22.hs
871198282

プログラム

 1 import Data.Char (ord)
 2 import Data.List (sort)
 3 import IO (readFile)
 4
 5 data Alpha = A | B | C | D | E
 6            | F | G | H | I | J
 7            | K | L | M | N | O
 8            | P | Q | R | S | T
 9            | U | V | W | X | Y
10            | Z deriving (Enum,Eq,Show)
11
12 toInt :: Alpha -> Int
13 toInt = (+1. fromEnum
14
15 fromChar :: Char -> Alpha
16 fromChar = toEnum . subtract (ord 'A'. ord
17 ----------------------------------------
18
19 score :: Int -> String -> Int
20 score n s = n * (sum $ map (toInt . fromChar) s)
21
22 scores :: [String] -> Int
23 scores = sum . map (uncurry score) . zip [1..]
24
25 sortNames :: [String] -> [String]
26 sortNames = sort
27 ----------------------------------------
28
29 member :: (Eq a) => a -> [a] -> Bool
30 member _ [] = False
31 member x (y:ys) = x == y || member x ys
32
33 deleteAll :: (Eq a) => [a] -> [a] -> [a]
34 deleteAll _ [] = []
35 deleteAll xs (y:ys) | member y xs = deleteAll xs ys
36                     | otherwise   = y : deleteAll xs ys
37
38 splitWith :: (Eq a) => a -> [a] -> [[a]]
39 splitWith _ [] = []
40 splitWith x ys = split' x ys []
41   where split' _ [] r = [reverse r]
42         split' x (y:ys) r
43            | x == y    = (reverse r) : splitWith x ys
44            | otherwise = split' x ys (y:r)
45
46 makeInput :: IO String
47 makeInput = readFile "names.txt"
48 ----------------------------------------
49
50 fn = makeInput >>=
51      return . scores . sortNames . splitWith ',' . deleteAll "\"\n"
52
53 main = fn >>= print

2008/10/29

Project Euler: Problem 21

Problem 21

力技で。友愛数の組を求める必要はないので、単純に数列に対してフィルタをかけている。

実行結果

$ time runhaskell 21.hs
40285

real 0m14.595s
user 0m14.510s
sys 0m0.050s

プログラム

1 divisors x = filter ((== 0. (mod x)) [1..(x `div` 2 + 1)]
2 = sum . divisors
3
4 hasAmicableNum n = n == (d (d n))
5
6 fn = sum $ filter hasAmicableNum [1..10000-1]
7
8 main = print $ fn

2008/10/29

Project Euler: Problem 20

Problem 20

文字列化したら負けかなと思ってる。

実行結果

$ runhaskell 20.hs
648

プログラム

 1 fact 0 = 1
 2 fact x = x * fact (x-1)
 3
 4 figureSum 0 = 0
 5 figureSum n = d + figureSum n'
 6   where (n',d) = divMod n 10
 7
 8 fn = figureSum $ fact 100
 9
10 main = print $ fn

2008/10/29

Project Euler: Problem 19

Problem 19

zeller の公式 - wikipediaとやらを使った。そのままだとうまくいかなかったので、ここを参考に、少し改変している。

実行結果

$ runhaskell 19.hs
171

プログラム

 1 zeller y m d = let w = k + (floor $ (double k)/4+
 2                        (floor $ (double j)/4- 2*+
 3                        (floor $ (13*(m'+1))/5+ d
 4                  in w `mod` 7
 5   where (y',m') = if m == 1 || m == 2
 6                     then (y-1,m+12)
 7                     else (y,m)
 8         (j,k)   = divMod y' 100
 9         double :: (Integral a) => a -> Double
10         double  = fromIntegral
11
12 fn = sum $ map year [1901..2000]
13   where year y = length $
14                  filter ((== 1. (\-> zeller y m 1))
15                         [1..12]
16
17 main = print $ fn

2008/10/21

Learn You a Haskell for Great Good

Learn You a Haskell for Great Good

Haskell の入門サイト。はてブ経由。7 Modules がちょうど知りたいなと思っていたところ。

2008/10/21

Project Euler: Problem 18

Problem 18

総当たりはやめとけと注意書きがあるにも関わらず、総当たりで。

実行結果

$ runhaskell 18.hs
1482

プログラム

 1 input = [[75],
 2          [95,64],
 3          [17,47,82],
 4          [18,35,87,10],
 5          [20,04,82,47,65],
 6          [19,01,23,75,03,34],
 7          [88,02,77,73,07,63,67],
 8          [99,65,04,28,06,16,70,92],
 9          [41,41,26,56,83,40,80,70,33],
10          [41,48,72,33,47,32,37,16,94,29],
11          [53,71,44,65,25,43,91,52,97,51,14],
12          [70,11,33,28,77,73,17,78,39,68,17,57],
13          [91,71,52,38,17,14,91,43,58,50,27,29,48],
14          [63,66,04,68,89,53,67,30,73,16,69,87,40,31],
15          [04,62,98,27,23,09,70,98,73,93,38,53,60,04,23]]
16
17 downPyramid :: [[a]] -> [[a]]
18 downPyramid (top:low) = down' top low
19   where down' [] _ = []
20         down' top [] = map (:[]) top
21         down' (t:ts) ((l1:l2:ls):low') =
22             map (t:$ down' [l1,l2] low' ++
23             down' ts ((l2:ls):low')
24
25 maxDownPyramid = maximum . map sum . downPyramid
26
27 stupid = maxDownPyramid input
28
29 main = print $ stupid

2008/10/20

Project Euler: Problem 17

Problem 17

どうにもこういった感じの処理を記述するのが苦手だ。実装も大変ダサい。つづりに間違いがなければあってるはず。

実行結果

$ runhaskell 17.hs
18548

プログラム

 1 toAlphabet 0 = ""
 2 toAlphabet 1 = "one"
 3 toAlphabet 2 = "two"
 4 toAlphabet 3 = "three"
 5 toAlphabet 4 = "four"
 6 toAlphabet 5 = "five"
 7 toAlphabet 6 = "six"
 8 toAlphabet 7 = "seven"
 9 toAlphabet 8 = "eight"
10 toAlphabet 9 = "nine"
11 toAlphabet 10 = "ten"
12 toAlphabet 11 = "eleven"
13 toAlphabet 12 = "twelve"
14 toAlphabet 13 = "thirteen"
15 toAlphabet 14 = "fourteen"
16 toAlphabet 15 = "fifteen"
17 toAlphabet 16 = "sixteen"
18 toAlphabet 17 = "seventeen"
19 toAlphabet 18 = "eighteen"
20 toAlphabet 19 = "nineteen"
21 toAlphabet 20 = "twenty"
22 toAlphabet 30 = "thirty"
23 toAlphabet 40 = "fourty"
24 toAlphabet 50 = "fifty"
25 toAlphabet 60 = "sixty"
26 toAlphabet 70 = "seventy"
27 toAlphabet 80 = "eighty"
28 toAlphabet 90 = "ninety"
29 toAlphabet 100 = "hundred"
30 toAlphabet 1000 = "one thousand"
31 toAlphabet n | n > 100 = (toAlphabet $ n `div` 100++ " hundred " ++
32                          (toAlphabet $ n `mod` 100)
33              | otherwise = (toAlphabet $ n - n `mod` 10++ " " ++
34                            (toAlphabet $ n `mod` 10)
35
36 deleteAll :: (Eq a) => a -> [a] -> [a]
37 deleteAll n [] = []
38 deleteAll n (x:xs) | n == x = deleteAll n xs
39                    | otherwise = x : deleteAll n xs
40
41 fn = sum $ map (length . deleteAll ' ' . toAlphabet) [1..1000]
42
43 main = print $ fn

2008/10/18

Java で動的にプロパティの指定を行う

Java にはプロパティというものが言語仕様上には存在しない(たぶん)。しかし一般的には、public な setter/getter を持つ属性がプロパティとして扱われている。最も、属性の名前をプロパティ名としたり、メソッドの prefix を取った名前をプロパティとしたり、その辺は色々と流儀がありそうだけど。

前述の通り、Java にはプロパティというものが言語仕様上にない。ゆえに動的にプロパティの指定を行うには、少し工夫が必要になる。

その1つの解が、文字列でプロパティ名を渡し、指定する方法である。これは最もお手軽な方法とも言える。しかし、これを使用すればするほどタイプミスによる誤りを生む可能性を増幅させてしまう。

そこで、どうにかシンボルで指定できないものかと考えた。そして行き着いた方法は、プロパティを enum で指定する方法である。各 Bean クラスの基底クラスとして、次の AbstractBean クラスを定義する。

AbstractBean

 1 public abstract class AbstractBean<P extends Enum<P>> {
 2
 3     private final Object[] values;
 4
 5     protected AbstractBean() {
 6         Class<P> propertyType = properties();
 7         values = new Object[propertyType.getEnumConstants().length];
 8     }
 9
10     protected <V> void set(P property, V value) {
11         values[property.ordinal()] = value;
12     }
13
14     protected Object get(P property) {
15         return values[property.ordinal()];
16     }
17
18     protected <V> V get(P property, Class<V> valueType) {
19         return valueType.cast(values[property.ordinal()]);
20     }
21
22     protected abstract Class<P> properties();
23
24 }

型引数として、enum クラスを受け取るようになっている。この enum クラスが、プロパティの列挙となる。properties() という abstract メソッドがある。AbstractBean クラスのサブクラスは、継承時に自身のプロパティ列挙クラスを指定し、properties メソッドでその列挙クラスを返すよう定義する。AbstractBean クラスのサブクラスの例が、次の Book クラスである。

Book

 1 public class Book extends AbstractBean<Book.Property> {
 2
 3     public enum Property { Name, Author, Price }
 4
 5     public Book() {
 6         super();
 7         setPrice(0);
 8     }
 9
10     @Override
11     protected Class<Property> properties() {
12         return Property.class;
13     }
14
15     public String getName() {
16         return get(Property.Name, String.class);
17     }
18     public void setName(String name) {
19         set(Property.Name, name);
20     }
21
22     public String getAuthor() {
23         return get(Property.Author, String.class);
24     }
25     public void setAuthor(String author) {
26         set(Property.Author, author);
27     }
28
29     public int getPrice() {
30         return get(Property.Price, Integer.class).intValue();
31     }
32     public void setPrice(int price) {
33         set(Property.Price, price);
34     }
35
36 }

さて、問題はこういった機構をいかに使い、シンボルを用いた動的なプロパティの指定を行うかである。そのサンプルとして、次のような Generator クラスを定義した。

Generator

 1 import java.util.HashMap;
 2 import java.util.Map;
 3
 4 public class Generator<T extends AbstractBean<P>, P extends Enum<P>> {
 5
 6     public static <T extends AbstractBean<P>, P extends Enum<P>>
 7         Generator<T, P> type(Class<T> type) {
 8         return new Generator<T, P>(type);
 9     }
10
11     private static <T> T newInstance(Class<T> type) {
12         try {
13             return type.newInstance();
14         } catch (Exception e) {
15             throw new Error(e);
16         }
17     }
18
19     private Class<T> type;
20     private Map<P, Object> buffer = new HashMap<P, Object>();
21
22     private Generator(Class<T> type) {
23         this.type = type;
24     }
25
26     public Generator<T, P> value(P property, Object value) {
27         buffer.put(property, value);
28         return this;
29     }
30
31     public T generate() {
32         T instance = newInstance(type);
33         for (Map.Entry<P, Object> prop : buffer.entrySet()) {
34             instance.set(prop.getKey(), prop.getValue());
35         }
36         buffer.clear();
37         return instance;
38     }
39
40 }

繰り返すが、実用性を求めるものでなく、あくまでも動的なプロパティの指定のサンプルとして作ったクラスである。どのクラスのインスタンスを生成するかを指定し、どのプロパティにどんな値を設定するという処理を行い、最後に generate を呼び出すとオブジェクトを生成する、というクラスである。例外処理は適当。

次はこのクラスを使ったテストケース。

GeneratorTest

 1 import org.junit.Before;
 2 import org.junit.Test;
 3 import static org.junit.Assert.*;
 4
 5 public class GeneratorTest {
 6
 7     @Test
 8     public void generate() {
 9         Book book =
10             Generator.type(Book.class)
11                      .value(Book.Property.Name, "うしおととら")
12                      .value(Book.Property.Author, "藤田和日郎")
13                      .value(Book.Property.Price, 250)
14                      .generate();
15
16         assertEquals("うしおととら", book.getName());
17         assertEquals("藤田和日郎", book.getAuthor());
18         assertEquals(250, book.getPrice());
19     }
20
21 }

このテストケースは成功する。動的なプロパティの指定をシンボルで行うことに成功している。ちなみにうしおととらは絶賛愛読中。

以上、どうにかして動的なプロパティの指定を、文字列から脱却できないものかと考えた結果でした。

2008/10/17

Project Euler: Problem 16

Problem 16

2^1000 を計算して答えを文字列化する。各文字を数値化することで、数値のリストを作る。あとはその数値のリストの合計を求めるだけ。ひねりなし。

Haskell の (^) が想像以上に速い。

実行結果

$ runhaskell 16.hs
1366

プログラム

1 import Char (ord)
2
3 main = print $ sum $ map toNum $ show $ 2^1000
4   where toNum c = ord c - ord '0'

2008/10/15

Project Euler: Problem 15

Problem 15

f(0,y) = 1
f(x,0) = 1
f(x,y) = f(x-1,y) + f(x,y-1)

という性質を使っている。ただし計算量がバカみたいに増えるので、メモ化して高速化している。State モナドでも使ってみりゃよかったかな。

実行結果

$ time runhaskell 15.hs
407575348

real 0m0.312s
user 0m0.280s
sys 0m0.040s

プログラム

 1 type Table = [((Int,Int), Int)]
 2
 3 lookupTable :: (Int,Int) -> Table -> [Int]
 4 lookupTable _ []     = []
 5 lookupTable x ((k,v):rs) | x == k    = [v]
 6                          | otherwise = lookupTable x rs
 7
 8 insertTable :: (Int,Int) -> Int -> Table -> Table
 9 insertTable k v tbl = (k,v) : tbl
10
11 memoRouteCount :: (Int,Int) -> Table -> (Int, Table)
12 memoRouteCount (0,_) tbl = (1,tbl)
13 memoRouteCount (_,0) tbl = (1,tbl)
14 memoRouteCount (x,y) tbl =
15   case lookupTable (x,y) tbl of
16     (v:_) -> (v,tbl)
17     []    -> let x'        = x - 1
18                  y'        = y - 1
19                  (v1,tbl1) = memoRouteCount (x',y) tbl
20                  (v2,tbl2) = memoRouteCount (x,y') tbl1
21                  v         = v1 + v2
22                  tbl3      = insertTable (x,y) v tbl2
23                in (v,tbl3)
24
25 routeCount :: (Int,Int) -> Int
26 routeCount = fst . flip memoRouteCount []
27
28 fn = routeCount (20,20)
29
30 main = print $ fn

2008/10/13

Project Euler: Problem 14

Problem 14

タプルの一方を比較し、戻り値はタプル全体としたいという処理を綺麗に書けなかった。なので Ord クラスのインスタンスとなる型を作った。

他は素朴な実装。1 から 99999 まで問題の処理を行い、それぞれ 1 になるまでカウントする。最後にカウントが最大のものを答えとして出力する。

実行結果

$ time ./14
Result 77031 351

real 0m17.152s
user 0m16.790s
sys 0m0.110s

プログラム

 1 data Result = Result Int Int deriving (Show, Eq)
 2
 3 instance Ord Result where
 4   (Result _ x) <= (Result _ y) = x <= y
 5
 6 next n | even n    = n `div` 2
 7        | otherwise = 3 * n + 1
 8
 9 clatzResult n = count 1 n
10   where count c x | x == 1    = Result n c
11                   | otherwise = count (c+1) (next x)
12
13 = maximum $ map clatzResult [1..99999]
14
15 main = print $ f

2008/10/13

Ordクラス

Ord クラスのインスタンスを作る際には、<=compare をオーバーライドするといい。これが最小限の実装となる。

2008/10/15: 不等号が逆になっていたので修正。

2008/10/12

IIDX

今作中の9段獲得は無理と確信しつつある。moon_child(A)とかなんだよあれひどすぎるだろ。

2008/10/12

ghc 拡張の使い方

コマンドオプションで指定する方法と、ソースコード内に記述する方法の2種類がある。

手元の環境では、拡張機能が必要ないのに拡張使用を指定すると、妙なメッセージを吐き出して死んでしまう。必要な時だけ使用すること。

コマンドオプション

ghc コマンドや ghci コマンドに、-X拡張名 というコマンドオプションを付ける。

ghc -XRankNTypes Hello.hs

ソースコード内指定

ソースコードの先頭行で、使用する拡張を指定する。個人的にはこちらが好き。何を要求するのか一目で分かるし、コンパイル時はghc とだけ打てば済むので。

 1 {-# LANGUAGE RankNTypes #-}
 2
 3 data Hello a = Hello a
 4              | GoodMorning a
 5
 6 extract :: Hello a -> a
 7 extract (Hello a) = a
 8 extract (GoodMorning a) = a
 9
10 showHellos :: forall a. (Show a) => [Hello a] -> [String]
11 showHellos = map (show . extract)

参考リンク

2008/10/12

Project Euler: Problem 13

Problem 13

上位N桁を求めたい数値の桁を計り、10 の (数値の桁数 - N) 乗 で数値を割ると答えが出る。これまでのプログラムよりは、ちょっと一般化している。まぁ、上位N桁の数値が知りたいという要求が、どれほど出るかは疑問であるが。そもそも文字列処理でいいじゃない、というのもあるし。

実行結果

$ runhaskell 13.hs
5537376230

プログラム

  1 input = [37107287533902102798797998220837590246510135740250,
  2          46376937677490009712648124896970078050417018260538,
  3          74324986199524741059474233309513058123726617309629,
  4          91942213363574161572522430563301811072406154908250,
  5          23067588207539346171171980310421047513778063246676,
  6          89261670696623633820136378418383684178734361726757,
  7          28112879812849979408065481931592621691275889832738,
  8          44274228917432520321923589422876796487670272189318,
  9          47451445736001306439091167216856844588711603153276,
 10          70386486105843025439939619828917593665686757934951,
 11          62176457141856560629502157223196586755079324193331,
 12          64906352462741904929101432445813822663347944758178,
 13          92575867718337217661963751590579239728245598838407,
 14          58203565325359399008402633568948830189458628227828,
 15          80181199384826282014278194139940567587151170094390,
 16          35398664372827112653829987240784473053190104293586,
 17          86515506006295864861532075273371959191420517255829,
 18          71693888707715466499115593487603532921714970056938,
 19          54370070576826684624621495650076471787294438377604,
 20          53282654108756828443191190634694037855217779295145,
 21          36123272525000296071075082563815656710885258350721,
 22          45876576172410976447339110607218265236877223636045,
 23          17423706905851860660448207621209813287860733969412,
 24          81142660418086830619328460811191061556940512689692,
 25          51934325451728388641918047049293215058642563049483,
 26          62467221648435076201727918039944693004732956340691,
 27          15732444386908125794514089057706229429197107928209,
 28          55037687525678773091862540744969844508330393682126,
 29          18336384825330154686196124348767681297534375946515,
 30          80386287592878490201521685554828717201219257766954,
 31          78182833757993103614740356856449095527097864797581,
 32          16726320100436897842553539920931837441497806860984,
 33          48403098129077791799088218795327364475675590848030,
 34          87086987551392711854517078544161852424320693150332,
 35          59959406895756536782107074926966537676326235447210,
 36          69793950679652694742597709739166693763042633987085,
 37          41052684708299085211399427365734116182760315001271,
 38          65378607361501080857009149939512557028198746004375,
 39          35829035317434717326932123578154982629742552737307,
 40          94953759765105305946966067683156574377167401875275,
 41          88902802571733229619176668713819931811048770190271,
 42          25267680276078003013678680992525463401061632866526,
 43          36270218540497705585629946580636237993140746255962,
 44          24074486908231174977792365466257246923322810917141,
 45          91430288197103288597806669760892938638285025333403,
 46          34413065578016127815921815005561868836468420090470,
 47          23053081172816430487623791969842487255036638784583,
 48          11487696932154902810424020138335124462181441773470,
 49          63783299490636259666498587618221225225512486764533,
 50          67720186971698544312419572409913959008952310058822,
 51          95548255300263520781532296796249481641953868218774,
 52          76085327132285723110424803456124867697064507995236,
 53          37774242535411291684276865538926205024910326572967,
 54          23701913275725675285653248258265463092207058596522,
 55          29798860272258331913126375147341994889534765745501,
 56          18495701454879288984856827726077713721403798879715,
 57          38298203783031473527721580348144513491373226651381,
 58          34829543829199918180278916522431027392251122869539,
 59          40957953066405232632538044100059654939159879593635,
 60          29746152185502371307642255121183693803580388584903,
 61          41698116222072977186158236678424689157993532961922,
 62          62467957194401269043877107275048102390895523597457,
 63          23189706772547915061505504953922979530901129967519,
 64          86188088225875314529584099251203829009407770775672,
 65          11306739708304724483816533873502340845647058077308,
 66          82959174767140363198008187129011875491310547126581,
 67          97623331044818386269515456334926366572897563400500,
 68          42846280183517070527831839425882145521227251250327,
 69          55121603546981200581762165212827652751691296897789,
 70          32238195734329339946437501907836945765883352399886,
 71          75506164965184775180738168837861091527357929701337,
 72          62177842752192623401942399639168044983993173312731,
 73          32924185707147349566916674687634660915035914677504,
 74          99518671430235219628894890102423325116913619626622,
 75          73267460800591547471830798392868535206946944540724,
 76          76841822524674417161514036427982273348055556214818,
 77          97142617910342598647204516893989422179826088076852,
 78          87783646182799346313767754307809363333018982642090,
 79          10848802521674670883215120185883543223812876952786,
 80          71329612474782464538636993009049310363619763878039,
 81          62184073572399794223406235393808339651327408011116,
 82          66627891981488087797941876876144230030984490851411,
 83          60661826293682836764744779239180335110989069790714,
 84          85786944089552990653640447425576083659976645795096,
 85          66024396409905389607120198219976047599490197230297,
 86          64913982680032973156037120041377903785566085089252,
 87          16730939319872750275468906903707539413042652315011,
 88          94809377245048795150954100921645863754710598436791,
 89          78639167021187492431995700641917969777599028300699,
 90          15368713711936614952811305876380278410754449733078,
 91          40789923115535562561142322423255033685442488917353,
 92          44889911501440648020369068063960672322193204149535,
 93          41503128880339536053299340368006977710650566631954,
 94          81234880673210146739058568557934581403627822703280,
 95          82616570773948327592232845941706525094512325230608,
 96          22918802058777319719839450180888072429661980811197,
 97          77158542502016545090413245809786882778948721859617,
 98          72107838435069186155435662884062257473692284509516,
 99          20849603980134001723930671666823555245252804609722,
100          53503534226472524250874054075591789781264330331690]
101
102 topFigure x n = x `div` (10 ^ (figure - n))
103   where figure = figure' 1
104         figure' f | x < (10 ^ f) = f
105                   | otherwise    = figure' (f+1)
106
107 fn = flip topFigure 10 $ sum input
108
109 main = print $ fn

2008/10/12

Project Euler: Problem 12

Problem 12

約数の個数を簡単に求める公式なんてものがあるらしい。知らなかった。はじめはアドホックに約数の個数を求めていたのだけど、なんかありそうだよなーと思って調べてみたらあった。速度的にも結構改善された。数分かかってたのが10数秒くらいになるとか。

参考リンク:

実行結果

$ time runhaskell 12.hs
76576500

real 0m24.888s
user 0m24.830s
sys 0m0.020s

プログラム

 1 triNum n = sum $ take n [1..]
 2
 3 ------------------------------------------------------------
 4 primes = sieve [2..]
 5   where sieve (p:ps) = p : sieve [x | x <- ps, x `mod` p /= 0]
 6
 7 primeDivs n = f' n primes [] 0
 8   where f' n pps@(p:ps) r c
 9            | n < p          = (p,c):r
10            | n `mod` p == 0 = f' (n `div` p)  pps r (c+1)
11            | otherwise      = if c == 0
12                                 then f' n ps r 0
13                                 else f' n ps ((p,c):r) 0
14
15 divsCount = product . map ((+1. snd) . primeDivs
16
17 ------------------------------------------------------------
18 = (fst . head) $
19     dropWhile ((< 501. snd) $
20     map (\-> let t = triNum n in (t,divsCount t)) [1..]
21
22 main = print $ f

2008/10/10

Project Euler: Problem 11 修正

Project Euler: Problem 11 - たろうbぉg が間違っていた。縦は下方向、横は右方向、斜めは右下方向だけ調べていたのだが、左下方向を調べていなかった。ので修正した。結果も変わったようである。

また、修正するにあたり、高階関数を使うようにプログラムを変えた。余計見にくくなった感も否めない。

実行結果

$ runhaskell 11.hs
70600674

プログラム

 1 input = [08,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,08,
 2          49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00,
 3          81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65,
 4          52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91,
 5          22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80,
 6          24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50,
 7          32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70,
 8          67,26,20,68,02,62,12,20,95,63,94,39,63,08,40,91,66,49,94,21,
 9          24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72,
10          21,36,23,09,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95,
11          78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,09,53,56,92,
12          16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57,
13          86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58,
14          19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40,
15          04,52,08,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66,
16          88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69,
17          04,42,16,73,38,25,39,11,24,94,72,18,08,46,29,32,40,62,76,36,
18          20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16,
19          20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54,
20          01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48]
21
22 tateMax values = fn values
23                     (\p len -> (p+60>= len)
24                     (\_     -> False)
25                     (+0)
26                     20
27
28 yokoMax values = fn values
29                     (\p len -> (p+3> len)
30                     (\p     -> (p+3`mod` 20 == 0)
31                     (+3)
32                     1
33
34 migiNanameMax values = fn values
35                        (\p len -> (p+63> len)
36                        (\p     -> (p+3`mod` 20 == 0)
37                        (+3)
38                        21
39
40 hidariNanameMax values = fn values
41                             (\p len -> (p+60>= len)
42                             (\p     -> p `mod` 20 == 0)
43                             (+3)
44                             19
45
46 fn values finish skip skipNext step = f 0 0 (length values)
47     where f r p len | finish p len  = r
48                     | skip p        = f r (skipNext p) len
49                     | otherwise     = let n = product' p step values
50                                           in if n > r
51                                                 then f n (p+1) len
52                                                 else f r (p+1) len
53
54 product' p i values = (values !! p) *
55                       (values !! (p+i)) *
56                       (values !! (p+(i*2))) *
57                       (values !! (p+(i*3)))
58
59 main = print $ maximum $ map (\-> f $ input)
60                              [tateMax, yokoMax,
61                               migiNanameMax, hidariNanameMax]

2008/10/09

Project Euler: Problem 11

Problem 11

急に難しくなった気がする。しかしこの問題は気合いで解く方針でも速度的には問題なく解ける模様。縦、横、斜めの3方向について、連続する4つの数字の積の最大値を求める。その3つの数の最大値を答えとしている。

縦を上下両方向やる必要はない。同様に横も斜めも全方向網羅する必要はない。理由は単純で、掛け算に方向は関係ないから。1 * 2 = 2 * 1みたいな。それを念頭に置けば、速度はなんとかなった。

ただ、プログラムはめちゃくちゃダサくなってしまった。自分で言うのもなんだが、いかにもメンテナンスしたくないって感じ。近いうちに修正したい。

実行結果

$ runhaskell 11.hs
51267216

プログラム

 1 input = [08,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,08,
 2          49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00,
 3          81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65,
 4          52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91,
 5          22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80,
 6          24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50,
 7          32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70,
 8          67,26,20,68,02,62,12,20,95,63,94,39,63,08,40,91,66,49,94,21,
 9          24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72,
10          21,36,23,09,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95,
11          78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,09,53,56,92,
12          16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57,
13          86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58,
14          19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40,
15          04,52,08,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66,
16          88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69,
17          04,42,16,73,38,25,39,11,24,94,72,18,08,46,29,32,40,62,76,36,
18          20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16,
19          20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54,
20          01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48]
21
22 tateMax values = f 0 0 (length values)
23     where f r p len | (p+60>= len = r
24                     | otherwise     =
25                         let n = product' p 20 values
26                             large = n > r
27                           in if large then f n (p+1) len
28                                       else f r (p+1) len
29
30 yokoMax values = f 0 0 (length values)
31     where f r p len | (p+3> len         = r
32                     | (p+3`mod` 20 == 0 = f r (p+3) len
33                     | otherwise           =
34                         let n = product' p 1 values
35                             large = n > r
36                           in if large then f n (p+1) len
37                                       else f r (p+1) len
38
39 nanameMax values = f 0 0 (length values)
40     where f r p len | (p+63> len        = r
41                     | (p+3`mod` 20 == 0 = f r (p+3) len
42                     | otherwise           =
43                         let n = product' p 21 values
44                             large = n > r
45                           in if large then f n (p+1) len
46                                       else f r (p+1) len
47
48 product' p i values = (values !! p) *
49                       (values !! (p+i)) *
50                       (values !! (p+(i*2))) *
51                       (values !! (p+(i*3)))
52
53 main = print $ maximum $ map (\-> f $ input)
54                              [tateMax, yokoMax, nanameMax]

2008/10/07

pandoc

一連のテストは pandoc の動作確認のため。日本語が 数字文字参照になってしまう現象は pandoc の仕様な のか、どうにも回避できそうにない。とりあえず web にちゃんと表示されるのであればいいかなと、まずは その実験を行った。結果、web ページ上ではちゃんと 表示される模様。

次に、様々な markdown の変換を試した。リスト周り がどうも思ったようにいかない。あとは大丈夫そう。 俺自身、markdown をそんなに使ったこともないので、 俺が間違っている可能性も大いにあるのだけど。

とりあえずこのエントリは markdown で書いてみた。 ちゃんとそれらしく出力されているだろうか。

テストはあとで消す。

参考URL:

このエントリの markdown コード

一連のテストは pandoc の動作確認のため。日本語が
数字文字参照になってしまう現象は pandoc の仕様な
のか、どうにも回避できそうにない。とりあえず web
にちゃんと表示されるのであればいいかなと、まずは
その実験を行った。結果、web ページ上ではちゃんと
表示される模様。

次に、様々な markdown の変換を試した。リスト周り
がどうも思ったようにいかない。あとは大丈夫そう。
俺自身、markdown をそんなに使ったこともないので、
俺が間違っている可能性も大いにあるのだけど。

とりあえずこのエントリは markdown で書いてみた。
ちゃんとそれらしく出力されているだろうか。

テストはあとで消す。

参考URL:

- [Pandoc][pandoc]
- [pandocの出力結果から数値文字参照を無くしたいのだけど - mieki256's diary][blog]
- [Markdwon 文法の全訳][markdown]
[pandoc]: http://johnmacfarlane.net/pandoc/
[blog]: http://blawat2015.no-ip.com/~mieki256/diary/200803311.html
[markdown]: http://blog.2310.net/contents/individual/000022.php

この記事、思い通りに変換されず(主に pre の改行関係で) 5,6回投稿しなおした。

2008/10/07

Project Euler: Problem 10

Problem 10

純粋にやると遅延評価のやりすぎによる stack over flow となった。seq を用いて遅延評価を回避している。

しかしこういう答えだと、純粋に和を求めなくともうまい方法があるのではと思ってしまう。いやたぶんあるんだろう。確信はないけど。

参考: sum の stack overflow - haskell のある暮らし

実行結果

$ runhaskell 10.hs
1000000000001

プログラム

1 primes = sieve [2..]
2     where sieve (p:ps) = p : [x | x <- ps, x `mod` p /= 0]
3
4 = strictSum 0 $ takeWhile (<= 2000000$ primes
5     where strictSum r []     = r
6           strictSum r (x:xs) = let r' = r+x
7                                 in r' `seq` strictSum r' xs
8
9 main = print $ f

2008/10/07

Project Euler: Problem 9

Problem 9

入れ子のリスト内包表記の使いかたを覚えた。filtermap を駆使しても可能なんだろうけども。こういったことは、リスト内包表記が圧倒的に簡潔だなぁ。

実行結果

$ runhaskell 9.hs
31875000

プログラム

1 = head $ [a*b*(1000-a-b) | a <- [1..(floor $ 1000/3)],
2                              b <- [a..1000],
3                              a^2 + b^2 == (1000-a-b)^2]
4
5 main = print $ f

2008/10/05

Project Euler: Problem 8

Problem 8

パターンマッチで文字を5個ずつ取り出し、数値化して計算する。4個しかない場合は終了。最後に計算結果のリストの最大値を求める。

実行結果

$ runhaskell 8.hs
40824

プログラム

 1 import Data.Char
 2
 3 input =
 4     "73167176531330624919225119674426574742355349194934" ++
 5     "96983520312774506326239578318016984801869478851843" ++
 6     "85861560789112949495459501737958331952853208805511" ++
 7     "12540698747158523863050715693290963295227443043557" ++
 8     "66896648950445244523161731856403098711121722383113" ++
 9     "62229893423380308135336276614282806444486645238749" ++
10     "30358907296290491560440772390713810515859307960866" ++
11     "70172427121883998797908792274921901699720888093776" ++
12     "65727333001053367881220235421809751254540594752243" ++
13     "52584907711670556013604839586446706324415722155397" ++
14     "53697817977846174064955149290862569321978468622482" ++
15     "83972241375657056057490261407972968652414535100474" ++
16     "82166370484403199890008895243450658541227588666881" ++
17     "16427171479924442928230863465674813919123162824586" ++
18     "17866458359124566529476545682848912883142607690042" ++
19     "24219022671055626321111109370544217506941658960408" ++
20     "07198403850962455444362981230987879927244284909188" ++
21     "84580156166097919133875499200524063689912560717606" ++
22     "05886116467109405077541002256983155200055935729725" ++
23     "71636269561882670428252483600823257530420752963450"
24
25 calc (_:_:_:_:[]) = []
26 calc (a:rest@(b:c:d:e:_)) = n : calc rest
27     where n       = product $ map toNum $ a:b:c:d:e:[]
28           toNum c = ord c - ord '0'
29
30 = maximum $ calc $ input
31
32 main = print $ f

2008/10/05

Project Euler: Problem 7

Problem 7

問題文そのまま。素数を列挙し、10001番目をとりだす。

実行結果

$ runhaskell 7.hs
20003

プログラム

1 primes = sieve [2..]
2     where sieve (p:ps) = p : [x | x <- ps, x `mod` p /= 0]
3
4 main = print $ primes !! 10001

2008/10/04

焼き肉

1ヶ月前ぐらいは焼き肉に久しくいってなくて、焼き肉に行きたいと懇願していた。しかし最近は逆に焼き肉が多い。9月から昨日にかけて、3回いっている。

まぁ好きだからいいのだけど。

2008/10/04

Project Euler: Problem 6

Problem 6

昨日は酔っぱらってあげるの忘れていた。

この問題を解く際、はじめは因数分解から導ける式を元に解こうとしていた。(x+y)^2 = x^2 + y^2 + 2xy だから、x と y の和の二乗と、二乗の和の差は 2xy であるというもの。しかしこれを 1 から 100 までやると、xy の組合せを構築するのに時間がかかり、結果として率直に解いたほうが速かった。

実行結果

$ runhaskell 6.hs
25164150

プログラム

1 = (sum [1..100])^2 - (sum $ map (^2) [1..100])
2
3 main = print $ f

2008/10/03

Haskell でスクリーンのサイズを得る

Haskell では、Graphics.X11 あたりのモジュールを使えば可能となっている。以下サンプル。

import qualified Graphics.X11.Xlib.Display as X

defaultScreenWidth =
    do disp <- X.openDisplay ""
       return $ X.displayWidth disp (X.defaultScreen disp)

以下余談。

なぜこんなことをしたくなったかと言うと、xmonad に関係している。

現在、ステータスバーとして dzen2 を2つ用いている。1つはWM系の情報、もう1つは雑多な情報を表示するのに用いている。WM系の情報を表示するため、dzen2 は xmonad.hs から起動している。

この時、2つのバーが重ならないよう、適切にサイズや位置を指定してやる必要がある。以前は固定で問題なかった。しかし最近はデュアルディスプレイの時やシングルディスプレイの時、ディスプレイサイズが違うなど、固定値ではまずい状況となっていた。

意図した通りの場所にバーを出現させるには、dzen2 に指定するサイズや位置を動的に変える必要がある。そこでスクリーンのサイズを得て、そこから色々と切り替えるように設定を変えた。まだお粗末ではあるが、期待した通りに動いている。

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。