月: 2008年4月

練習問題 10.3 fold コマンド

プログラミング in OCaml ~関数型プログラミングの基礎からGUI構築まで~のp.215より。

wc コマンドはなんか難しいのでこっちを先に。

UNIX の fold コマンドは，ファイル名の列を引数として，その内容を，長い行を複数の短い 行（デフォルトでは80文字）に分割しながら表示します。これを OCaml で実装し，実行可能 ファイルを作成しなさい。オプションとしては，行の長さを整数で指定する –width を実装 しなさい。

let version = "0.1"
let filenames = ref []
let width = ref 80
let spec = [("--width",
Arg.Int (fun n -> width := n),
"Set line width");
("--version",
Arg.Unit (fun () -> Printf.printf "fold in OCaml ver.%s\n" version),
"Display version")]
let rec fold_line n str =
let len = String.length str in
if len > n then
( print_endline (String.sub str 0 n);
fold_line n (String.sub str n (len - n)))
else
print_endline str
let rec each_line ic =
fold_line !width (input_line ic);
each_line ic
let fold_file filename =
let infile = open_in filename in
try
each_line infile
with
End_of_file -> close_in infile
let () =
Arg.parse spec
(fun s -> filenames := s :: !filenames)
"Usage: fold [--width width] [--help] [--version] filename ...";
List.iter fold_file (List.rev !filenames)

^o^ >ocamlc -o fold.exe fold.ml
^o^ >fold --width 40 fold.ml
let version = "0.1"
let filenames = ref []
let width = ref 80
let spec = [("--width",
Arg.Int (fun n -> width :=
n),
"Set line width");
("--version",
Arg.Unit (fun () -> Printf
.printf "fold in OCaml ver.%s\n" version
),
"Display version")]
let rec fold_line n str =
let len = String.length str in
if len > n then
( print_endline (String.sub str 0 n)
;
（以下略）

練習問題 10.1

プログラミング in OCaml ~関数型プログラミングの基礎からGUI構築まで~のp.215より。

UNIXの cat コマンドは，ファイル名の列を引数として，その内容を順次表示する（標準出力 に書き込む）ものです。これを OCaml で実装し，実行可能ファイルを作成しなさい。オプシ ョンに関しては少なくとも行番号を表示するための -n オプションを実装すること。

let version = "0.1"
let display_linenum = ref false
let filenames = ref []
let spec = [("-n",
Arg.Set display_linenum,
"Display line number.");
("-version",
Arg.Unit (fun () -> Printf.printf "cat in OCaml ver.%s\n" version),
"Display version.")]
(* print each lines *)
let rec output_file ic =
print_endline (input_line ic);
output_file ic
(* print each lines with line number *)
let rec output_file_n n ic =
Printf.printf "%5d %s\n" n (input_line ic);
output_file_n (n+1) ic
let cat_file filename =
let infile = open_in filename in
try
if !display_linenum then
output_file_n 1 infile
else
output_file infile;
with
End_of_file -> close_in infile
let () =
Arg.parse spec
(fun s -> filenames := s :: !filenames)
"Usage: cat [-n] [-help] [-version] filename ...";
List.iter cat_file (List.rev !filenames)


^o^ >ocamlc -o cat.exe cat.ml
^o^ >cat -n cat.ml
1 let version = "0.1"
2
3 let display_linenum = ref false
4
5 let filenames = ref []
6
7 let spec = [("-n",
8              Arg.Set display_linenum,
9              "Display line number.");
10             ("-version",
11              Arg.Unit (fun () -> Printf.printf "cat in OCaml ver.%s\n" ve
sion),
12              "Display version.")]
13
（以下略）

Problem 31

今日は Problem 31。

 

　cf. Project Euler – Problem 31
　cf. Life Goes On – ３１問目

id:rst76さんのをちょっと改良して1pのコインがない場合にも対応できるようにしてみた。問題の解答には必要ないんだけど。

module Main (main) where

euler031 :: [Int] -> Int -> Int
euler031 (x:[]) m | m `mod` x == 0 = 1
                 | otherwise = 0
euler031 (x:xs) m = sum $ map (\n -> euler031 xs (m - x*n)) [0..(m `div` x)]

main :: IO ()
main = putStrLn $ show $ euler031 [200,100,50,20,10,5,2,1] 200
^o^ >runhaskell euler031.hs
73682

1pのコインがない場合：

*Main> euler031 [200,100,50,20,10,5,2] 200
1784

Problem 14

今日は Problem 14。

　cf. Project Euler – Problem 14

コラッツ問題の数列を求めるのは以前にやったのを流用。あとは力任せに…

module Main (main) where

collatz :: Int -> [Int]
collatz 1 = 1 : []
collatz n | n `mod` 2 == 0 = n : collatz (n `div` 2)
          | otherwise = n : collatz (n * 3 + 1)

euler014 :: Int -> [Int]
euler014 n = snd $ foldl g (0, []) $ map f [1..n]
  where
    f x = ((length.collatz) x, x)
    g (x,zs) (l,z) | x < l = (l, z:[])
                   | x == l = (x, z:zs)
                   | otherwise = (x, zs)

main :: IO ()
main = mapM_ (putStrLn.show) $ euler014 1000000

やったらあえなくスタックオーバーフローに。ありゃ。

^o^ >runhaskell euler014.hs
*** Exception: stack overflow

100,000までだったらうまくいったので間違ってはいないと思う。たぶん数列がすごく長くなる数があるんだろうな。再挑戦はまた今度。

あと，ついでに書いておくと，各数の数列にはおなじ部分列が何度も出現する。これを覚えておけば計算量を少なくできるんだけど，メモ化のやり方がわからない。

Problem 8

今日は Problem 8。

　cf. Project Euler – Problem 8

module Main (main) where

import Data.List
import Data.Char

euler008 :: [Char] -> Int
euler008 n = maximum $ map euler008' $ nums n
  where
    nums = filter (\x -> length x > 4) . map (take 5) . tails
    euler008' = foldl1 (*) . map digitToInt

main :: IO ()
main = do n <- getContents >>= return . concat . lines
          putStrLn $ show $ euler008 n
^o^ >runhaskell euler008.hs < euler008.txt
40824

Problem 13

今日は Problem 13 をやってみた。これは簡単。

　cf. Project Euler – Problem 13

nums :: [Integer]
nums = [37107287533902102798797998220837590246510135740250,
        46376937677490009712648124896970078050417018260538,
        74324986199524741059474233309513058123726617309629,
        ...
        72107838435069186155435662884062257473692284509516,
        20849603980134001723930671666823555245252804609722,
        53503534226472524250874054075591789781264330331690]

euler013 :: String
euler013 = take 10 $ show $ sum nums

main :: IO ()
main = putStrLn euler013
^o^ >runhaskell euler013.hs
5537376230

追記：

数字をファイル（euler013.txt）から読み込むようにしてみた。

euler013 :: [Integer] -> String
euler013 = take 10 . show . sum

main :: IO ()
main = do nums <- getContents >>= return . lines
          putStrLn $ euler013 $ map read nums
^o^ >runhaskell euler013a.hs < euler013.txt
5537376230