Clojureで日付の計算をする
引き続き「プログラマ脳を鍛える数学パズル」の問題を解いて遊んでいる。 第7問は日付を扱う。 問題自体は簡単なのだが、Clojureでの日付の扱い方がよく分からなくて、調べるのに時間がかかった。
clj-timeというライブラリがあるようだが、わざわざな・・・。
結局javaライブラリを生でたたくのが一番で、しかしまあオブジェクト指向のAPIは何かするのにいちいち面倒いこと。 もう一度面倒くさいことをしなくて済むようにメモを残しておこう。
動くコードを残しておくのが一番手っ取り早い。
処理
"19991225" から10日分の年月日を出力する
コード
(ns prog-math-puzzle.test-date (import (java.util Calendar) (java.text SimpleDateFormat))) (def date-format (SimpleDateFormat. "yyyyMMdd")) (defn date [dstr] (let [cal (Calendar/getInstance)] (.setTime cal (.parse date-format dstr)) cal)) (defn to-str [cal] (.format date-format (.getTime cal))) (defn next-day [cal] (let [nc (.clone cal)] (.add nc Calendar/DATE 1) nc)) (defn date-seq [cal] (lazy-seq (cons cal (date-seq (next-day cal))))) (println (map to-str (take 10 (date-seq (date "19991225")))))
出力
(19991225 19991226 19991227 19991228 19991229 19991230 19991231 20000101 20000102 20000103)
メモ
必要なライブラリ
java.util.Calendar、java.text SimpleDateFormat
日付のフォーマット
(def date-format (SimpleDateFormat. "yyyyMMdd"))
の部分で、"yyyy-mm-dd"とかでもOK。
日付オブジェクトの生成
java.util.Calendarオブジェクトを作る。
(defn date [dstr] (let [cal (Calendar/getInstance)] (.setTime cal (.parse date-format dstr)) cal))
.setTimeはjavaのメソッド呼び出しなので、返り値にデータを返す訳ではなくて、calを書き換えちゃうんだな。
なので、最後にcalを返している。
また、javaのメソッドで日付データを変える場合は、データをコピーしてから、やらないといけない。 元のデータが書き換わっちゃうから。
next-day関数ではCalendarインスタンスをcloneしてから、日にちを１つ足している。
(defn next-day [cal] (let [nc (.clone cal)] (.add nc Calendar/DATE 1) nc))
以上。
Haskell/Clojureでrepeated_combinationを実装してみる
前回やった Haskell/Clojureで数学パズル：コインの両替 - Programmer's Note の問題5は、書籍の解答例のひとつに、Rubyのrepeated_combination()を使った解があった。
こいつは任意の回数、配列の要素の組み合わせを出してくれる関数で、 探せばClojure/Haskellにもあるだろうけど、ちょうどいい感じの題材なので実装してみる。
任意の大きさのリスト[a,b,c,d,...]を任意の回数n、各要素の組み合わせを出す。
使い方
repeat_combination [1 2 3] 2 ; -> ((1 1) (1 2) (1 3) (2 1) (2 2) (2 3) (3 1) (3 2) (3 3)) repeat_combination [1 2 3] 3 ; -> ((1 1 1) (1 1 2) (1 1 3) (1 2 1) (1 2 2) (1 2 3) (1 3 1) (1 3 2) (1 3 3) (2 1 1) (2 1 2) (2 1 3) (2 2 1) (2 2 2) (2 2 3) (2 3 1) (2 3 2) (2 3 3) (3 1 1) (3 1 2) (3 1 3) (3 2 1) (3 2 2) (3 2 3) (3 3 1) (3 3 2) (3 3 3))
アルゴリズムは２通りあって、深さ優先か幅優先か。
いろいろやってみたけれど、下記の実装が一番シンプルでわかりやすいな。 幅優先で処理するやり方。
Haskellの実装：
comb :: [[Int]] -> [[Int]] -> [[Int]] comb xs ys = [ x ++ y | x <- xs, y <- ys] comb_n_times :: [[Int]] -> Int -> [[Int]] comb_n_times xs 1 = xs comb_n_times xs n = comb xs (comb_n_times xs (n-1)) repeat_combination :: [Int] -> Int -> [[Int]] repeat_combination xs 1 = [xs] repeat_combination xs n = let ys = [[x] | x <- xs] in comb_n_times ys n
やっていることは以下のような感じ。
入力データを変換してから [a,b,c] => [[a],[b],[c]] １回目 [[a],[b],[c]] x [[a],[b],[c]] => [a,a][a,b][a,c][b,a][b,b][b,c][c,a][c,b][c,c] ２回目は１回目の結果にたいして、 [[a],[b],[c]] x [[a,a][a,b][a,c][b,a][b,b][b,c][c,a][c,b][c,c]] => [a,a,a][a,a,b][a,a,c] .... 以上を繰り返す
コードとしては分かりやすいが、SICPでいうrecusive processになっているので、末尾最適化できない。 nが大きいとStack Overflowを起こす。 とはいえ、この幅優先な方法は、iterative processな実装も可能ではある。
深さ優先
一方、深さ優先で組み合わせを作っていくやりかたもある。 プロセスはこんな感じ。
[a,b,c] x [a,b,c] x [a,b,c]
a -> a -> a => [a,a,a]
-> b => [a,a,b]
-> c => [a,a,c]
-> b -> a => [a,b,a]
-> b => [a,b,b]
-> c => [a,b,c]
...
こっちの方はClojureの実装を載せる。
(defn repeat-combination [xs n] (letfn [(comb-depth [cnt res] (if (zero? cnt) [res] (apply concat (for [x xs] (comb-depth (dec cnt) (conj res x)))))) ] (if (= n 1) [xs] (comb-depth n []))))
こっちの方法はあまりメリットはないかな・・・。 iterative processな実装にすることができない（たぶん）。
Haskell/Clojureで数学パズル：コインの両替
いやあ「プログラマ脳を鍛える数学パズル」楽しいですわ。 まだ5問しかやっていないけど、Clojure/Haskell両方で解いているので、一粒で二度美味しい。 しかも、解説は違う視点の解法を示してくれるので、３度も４度も美味しい感じだ。
5問目は、お金の両替問題で、これシンプルだけど奥が深い。 1000円を10円、50円、100円、500円に両替する。同じコインは何枚使ってもいいが、最大コイン数は15枚。 この時の両替パターン数を求める。
名著SICPにも内容が少し違う両替問題が出ていて、再帰の威力を見せつけられたな。
さて、この問題、まず最初にぱっと思いつく方法は、ベタに組み合わせと条件判定。
Haskellの回答例は、
change_coin :: Int -> Int -> Int change_coin money max_coins = sum [1 | m10 <- [0..max_coins], m50 <- [0..max_coins], m100 <- [0..max_coins], m500 <- [0..max_coins], m10 + m50 + m100 + m500 <= max_coins, money == (10*m10 + 50*m50 + 100*m100 + 500*m500)] main :: IO () main = do print $ change_coin 1000 15
リスト内包表記、便利で簡潔で美しいですわ。
似た簡潔さでClojureも書ける。for文を使う。
(defn change_coin [money max_coins] (reduce + (for [m10 (range 0 (inc max_coins)) m50 (range 0 (inc max_coins)) m100 (range 0 (inc max_coins)) m500 (range 0 (inc max_coins)) :when (and (<= (+ m10 m50 m100 m500) max_coins) (= money (+ (* 10 m10) (* 50 m50) (* 100 m100) (* 500 m500)))) ] 1))) (println (change_coin 1000 15))
少しだけ考えて、再帰を使って汎用的な関数を作ってみる。
Haskell版：
change_coin :: Int -> [Int] -> Int -> Int change_coin 0 _ _ = 1 change_coin _ _ 0 = 0 change_coin _ [] _ = 0 change_coin money (x:xs) max_coins = sum [ change_coin (money - x * use) xs (max_coins - use) | use <- [0..max_coins]] main :: IO () main = do print $ change_coin 1000 [10,50,100,500] 15
考え方としては、使うコインのリスト[10,50,100,500]を与えて、前からコインを取り出して、
(この場合だとまずは10円）
- コインを0枚使う → 1000-0 に対して残ったコインで両替する
- コインを1枚使う → 1000-10 に対して残ったコインで両替する
- ・・・
- コインを15枚使う → 1000-10*15 に対して残ったコインで両替する
というのを再帰でやる。（まあ15枚使ったら、もう終わりだけどね） 最後に残金が０なら、うまく換金できたので１を返し、 それ以外でコインのリストが空になったり、最大コイン数使ったら０を返す。
Clojureも同じように組める。
(defn change_coin_patterns [money coins max-coins] (cond (zero? money) 1 (empty? coins) 0 (zero? max-coins) 0 :else (reduce + (for [uses (range 0 (inc max-coins))] (change_coin_patterns (- money (* uses (first coins))) (rest coins) (- max-coins uses)))))) (println (change_coin_patterns 1000 [10 50 100 500] 15))
Haskellだとパターンマッチングを使った記述がビューティフル。
Haskell／Clojureで数値をN進数表記に変換
去年からHacker Rankが面白くてハマっている。 今年に入ってからHaskellを始めたので、ますます関数型プログラミングでアルゴリズムをやりたい気分が上がっている。
アルゴリズム勉強したいなと思い、 有名なKnuth先生の「The Art of Computer Programming」を買って、 ちょっと読んでみたら、これアセンブラなんですね。興味を削がれたのでそっと積んで置く・・・。
一方、Hacker Rankに飽き足らず、コードパズル系の本も気になっていて、 「プログラマ脳を鍛える数学パズル」も買ってみた。書籍だと解説もあるので楽しみである。
早速、しょっぱなの２問をやってみた。問題自体はいいのだが、 回答がプログラミング言語の機能をばんばん使う前提にしているんだな。 (rubyのevalレベルまで使っていいとは）
制限時間が設定されていて、とにかく速く問題を解くことに目が置かれているので、 そうしているんだな。
別にいいんだけど、 しかしまあ、美味しい部分は、その端折ったところにあったりする。
1問目は、同じ整数を表す10進・8進・2進表記が回文になっている数を求める問題なのだが、 N進数に変換する部分はプログラミング言語のライブラリを使っていい前提だ。
・・・このN進数表記に変換する部分が美味しい部分ですやん。
実際、Clojure, Haskellで書いてて面白く楽しかった部分だ。 やっていること自体は難しくないが、最大公約数を求めるユークリッドの相除法みたく、 数学に近い部分の本質的な面白さがある。
これは、関数型言語で書くと短くて鑑賞のしがいのあるコードが書ける。 （最近はコードを書いて悦悦と眺めるのが目的みたいな感じになっている。 そのために良問を探している感がある。）
さて、ある数をN進表記に変換する関数を、まずはHaskellで書いてみる。
どんな関数かというと、整数10を2進表記に変換する場合に、
Prelude > n_ary_str 10 2 "1010"
という風に使う関数だ。
import Data.Char n_ary :: Int -> Int -> [Int] n_ary 0 _ = [] n_ary num base = n_ary quotient base ++ [remainder] where quotient = num `quot` base remainder = num `mod` base n_ary_str :: Int -> Int -> String n_ary_str num base = map intToDigit (n_ary num base)
やっていることは、 まずN進の数字のリストを求めて、それを文字列にしている。
n_ary 10 2 は [1, 0, 1, 0] というリストが返る。
これを使ってn_ary_str関数で、順に文字に置換しているだけだ。
Haskellの文字列は文字の配列なので、置換したら終わり。
10進以上は対応していないが、対応するのは簡単だ。
たとえばn_ary 199 16は[12, 7]になるが、これを['C', '7']に変換するだけだ。
つまり、10以上の数字を'A'からのアルファベットに置き換えるだけ。
Haskellは習い始めだが、whereというシンタックスはえらく感動する。
これを使うとコードの本質的な部分を先に書けて意図を強調できる。
上記コードは、別に使わなくてもいいのに、わざわざwhereを使っているが、
結局N進数って何？という問いに対して、ソースコードで、
「Nで割った余りを求める。自分の上の桁に対して商を与えそれを繰り返す」です、と表現できる。
（Nに相当する部分がソースではbase）
Haskellは本当にそのまま定義を書ける感じだ。大学の授業とかで使って欲しい言語No.1だな。
Clojureも同じように書ける。（n_ary関数だけ）
(defn n_ary [number base] (if (zero? number) [] (let [quotient (quot number base) remainder (mod number base)] (conj (n_ary quotient base) remainder))))
たぶんLISPerはこんな冗長なコードは書かない(笑。
自分のいつものClojureのコードだと下記のようになる。（文字列変換も込みで）
(defn n_ary [number base] (loop [n number, res []] (if (zero? n) res (recur (quot n base) (cons (mod n base) res))))) (defn n_ary_str [number base] (apply str (n_ary number base)))
Clojureのloopマクロは本当に便利で多用している。 すごく便利なのだが、実は初見だとコードがわかりづらいかもしれないね。
Haskellの勉強をはじめる
今年に入ってからHaskellを勉強し始めた。これが結構楽しい。教科書は「Programming in Haskell」。(この本は名著だ)
読み進めてコードを書いてみるにつれ、最初の想像と違って、かなりLISPに近い印象を受ける。ラムダ計算がベースなので、そっくりなのは当たり前かもしれない。
この言語の文法は可能な限り簡略化されてて、関数の定義にdefもカッコも必要なく、引数を与えるのにカンマもいらない。
手書きでアルゴリズム考えるのにLISPより使いやすい。カッコ不要で中置記法、条件文も明瞭で無駄がなく、コードが読みやすい。教育用としてとても使いやすい言語だと思う。(そのために設計されたのかもしれないが)
LISPのS式とは違った美しさがある。
かなり好きになりそう。
この先、興味があるのは、型がプログラミング上どれくらい本質的な重要性を持つかというところ。そもそもHaskellを勉強してみたくなったのは、Rich Hickeyが静的型とパターンマッチングをdisってたのが気になったからだしな。
最近はClojureでHacker Rankの問題を解いてて、すっかり考え方(解き方)がマンネリ化してきていると感じている。再帰は手軽な(loop...)ばかり使ってしまう。まあ得意技を持つのは悪いことではないが、引き出しの数が増えない。
Haskellの勉強はかなり良い意味で視点の転換、拡張をさせてくれている。
例えばリスト内包表記はClojureの(for...)と実質同等なのだが、処理対象をデータグループとして捉えるか、forループの結果として捉えるかで、問題の解き方が大きく違ってくるんだなと気付かされた。(本の中でこの違いを言及している訳じゃなくて、自分が後者の視点ばかり持っていたから、前者の視点での解法にinsightを与えられた)
文法の違いが実は思考の展開の違いを生んでいる。
「達人プログラマ」がいう年に一個新しい言語を学べというのは、侮れないアドバイスなり。と。
Clojure: cond-> の使い所
久々のブログ更新だ。
いやはやClojureが楽しくてしょうがない。 特に何か作っているわけではないが、 ここ３、４ヶ月はHackerRank (https://www.hackerrank.com/) にハマって、パズル解く感覚でClojureを使って問題を解いて遊んでいた。
LISP言語はアルゴリズム＆データ構造を試行錯誤するのに最適だな、と。 加え、Clojureは標準で扱えるデータ形式が豊富で、いろいろなマクロがあって シンタックスのバリエーションも多いから、書いてて楽しい。
さて、HackerRankの中で、シンプルでイージーだけど、 プログラムの表現方法を色々試せて楽しめた問題があった。
問題
https://www.hackerrank.com/challenges/mars-exploration/problem
[超概略]
火星探査機が故障したので地球にSOS信号を出しているが、宇宙線の影響でノイズが入ってしまう。
SOSSOSSOSSOS
と出したところ、
SOSSPSSQSSOR
と届いてしまう。このノイズの数を数えなさい。
回答例(C言語)
こういう系統の処理はC言語が得意なんだとなと思う。
#include <stdio.h> int main() { char string[256], *s = string; scanf("%s", string); int cnt = 0; while(*s) { if (*s++ != 'S') cnt++; if (*s++ != 'O') cnt++; if (*s++ != 'S') cnt++; } printf("%d\n", cnt); }
文字列を読むとこは置いといて、実処理while文以下はポインタを使うとかなりすっきり書けて、自分はC言語のこういうところが好きである。
ポインターと変数を使うことで簡潔に書ける例だと思う。
じゃあ、Clojureだとどうなるのか？というと…
解答例(Clojure)
自分の中では、やり方は３つくらいはあって、その中で一番すっきり書けたのはpartitionを使うもの。
処理の内容をダイレクトに読み取れてC言語に負けないくらい簡潔。
(->> (read-line) (partition 3) (reduce (fn [cnt [c1 c2 c3]] (+ cnt (if (not= c1 \S) 1 0) (if (not= c2 \O) 1 0) (if (not= c3 \S) 1 0))) 0) println)
さて、上のコードはこれはこれで好きなのだが、最近cond->なるものを知って、
これを使えばより短く、処理の意図もダイレクトに表現できることがわかった。
以下がcond->を使った場合。
(->> (read-line) (partition 3) (reduce (fn [cnt [c1 c2 c3]] (cond-> cnt (not= c1 \S) inc (not= c2 \O) inc (not= c3 \S) inc)) 0) println)
”カウントする”という処理の意図がincを使うことで、よりダイレクトな表現になっている。
しかしまあ、Clojureはcoreライブラリだけでも、本当にいろいろマクロがあるなあ。と。
余談：解答例(Clojureその２)
遠回りで効率も良くないけど、以下のやり方もある。
(let [string (read-line)] (->> (repeat "SOS") (take (/ (count string) 3)) (apply str) (map #(not= %1 %2) string) (filter true?) count println))
この前の解答例は、与えられた文字列を前から順になめっていって文字を比較しているのだが、 このプログラムでは正解の文字列を作って、与えられた文字列と比較している。 （実はこれが最初に思いついた解なのだが^^;)
いやあ、 いろんなやり方をさくっと試せてしまうところが、Clojureの一番の強みで楽しいとこだな！と。
Vimにneosnippetを導入
SICPのexerciseをやっていると、例えば(ns …)の宣言など定型的な部分は、snippetがあると便利だなーと思う。
探してみたらvimのpluginで定番のneosnippetがあった。
GitHub - Shougo/neosnippet.vim: neo-snippet plugin
この動作にはneocompleteが必要だったの一緒に導入した。
上記サイトにはneocompleteの代わりにneocomplcacheも使えると書いてあるが、自分の環境(Mac OS X 10.9, vim 7.4)ではうまく動作しなかった。 (インストールはうまく行ったがまったくcompleteしてくる様子がなかった）
導入方法
NeoBundleのリストに追加する。
call neobundle#begin(expand('~/.vim/bundle/')) ... NeoBundle 'Shougo/neocomplete' NeoBundle 'Shougo/neosnippet' NeoBundle 'Shougo/neosnippet-snippets' call neobundle#end()
あとは、もろもろの設定を.vimrcに追加する
"" -------------------------------------------- "" neocomplete "" -------------------------------------------- " Disable AutoComplPop. let g:acp_enableAtStartup = 0 " Use neocomplete. let g:neocomplete#enable_at_startup = 1 " Use smartcase. let g:neocomplete#enable_smart_case = 1 " Set minimum syntax keyword length. let g:neocomplete#sources#syntax#min_keyword_length = 3 " Define dictionary. let g:neocomplete#sources#dictionary#dictionaries = { \ 'default' : '', \ 'vimshell' : $HOME.'/.vimshell_hist', \ 'scheme' : $HOME.'/.gosh_completions' \ } " Define keyword. if !exists('g:neocomplete#keyword_patterns') let g:neocomplete#keyword_patterns = {} endif let g:neocomplete#keyword_patterns['default'] = '\h\w*' " Plugin key-mappings. inoremap <expr><C-g> neocomplete#undo_completion() inoremap <expr><C-l> neocomplete#complete_common_string() " Recommended key-mappings. " <CR>: close popup and save indent. inoremap <silent> <CR> <C-r>=<SID>my_cr_function()<CR> function! s:my_cr_function() return (pumvisible() ? "\<C-y>" : "" ) . "\<CR>" " For no inserting <CR> key. "return pumvisible() ? "\<C-y>" : "\<CR>" endfunction " <TAB>: completion. inoremap <expr><TAB> pumvisible() ? "\<C-n>" : "\<TAB>" " <C-h>, <BS>: close popup and delete backword char. inoremap <expr><C-h> neocomplete#smart_close_popup()."\<C-h>" inoremap <expr><BS> neocomplete#smart_close_popup()."\<C-h>" " Close popup by <Space>. "inoremap <expr><Space> pumvisible() ? "\<C-y>" : "\<Space>" " AutoComplPop like behavior. "let g:neocomplete#enable_auto_select = 1 " Shell like behavior(not recommended). "set completeopt+=longest "let g:neocomplete#enable_auto_select = 1 "let g:neocomplete#disable_auto_complete = 1 "inoremap <expr><TAB> pumvisible() ? "\<Down>" : "\<C-x>\<C-u>" " Enable omni completion. "autocmd FileType css setlocal omnifunc=csscomplete#CompleteCSS "autocmd FileType html,markdown setlocal omnifunc=htmlcomplete#CompleteTags "autocmd FileType javascript setlocal omnifunc=javascriptcomplete#CompleteJS "autocmd FileType python setlocal omnifunc=pythoncomplete#Complete "autocmd FileType xml setlocal omnifunc=xmlcomplete#CompleteTags " Enable heavy omni completion. if !exists('g:neocomplete#sources#omni#input_patterns') let g:neocomplete#sources#omni#input_patterns = {} endif "let g:neocomplete#sources#omni#input_patterns.php = '[^. \t]->\h\w*\|\h\w*::' "let g:neocomplete#sources#omni#input_patterns.c = '[^.[:digit:] *\t]\%(\.\|->\)' "let g:neocomplete#sources#omni#input_patterns.cpp = '[^.[:digit:] *\t]\%(\.\|->\)\|\h\w*::' " For perlomni.vim setting. " https://github.com/c9s/perlomni.vim let g:neocomplete#sources#omni#input_patterns.perl = '\h\w*->\h\w*\|\h\w*::' "" -------------------------------------------- "" neo-snippet "" -------------------------------------------- " Plugin key-mappings. " Note: It must be "imap" and "smap". It uses <Plug> mappings. imap <C-k> <Plug>(neosnippet_expand_or_jump) smap <C-k> <Plug>(neosnippet_expand_or_jump) xmap <C-k> <Plug>(neosnippet_expand_target) " SuperTab like snippets behavior. " Note: It must be "imap" and "smap". It uses <Plug> mappings. imap <C-k> <Plug>(neosnippet_expand_or_jump) "imap <expr><TAB> " \ pumvisible() ? "\<C-n>" : " \ neosnippet#expandable_or_jumpable() ? " \ "\<Plug>(neosnippet_expand_or_jump)" : "\<TAB>" smap <expr><TAB> neosnippet#expandable_or_jumpable() ? \ "\<Plug>(neosnippet_expand_or_jump)" : "\<TAB>" " For conceal markers. if has('conceal') set conceallevel=2 concealcursor=niv endif
動作確認
試しにnsのsnippetを使ってみる。
vimを起動して適当に:e /tmp/test.cljとかでファイルを編集する。
インサーションモードに入り、nsを入力してC-kを押すと、一瞬で下記のようなコードに展開してくれる。
(ns .tmp.test (:require <`2:`>))
この状態でカーソルはtmp.testにあたっており、編集できる状態になっていて、
さらにC-kを押すと、カーソルは<`2:`>に飛ぶ。
素晴らしい。
snippetファイルは自分で作成できる。標準のclojureのsnippetは
~/.vim/bundle/neosnippet-snippets/neosnippets/clojure.snip
に入っているので、これを参考にして色々追加してみるかな。
以上。
