幅が 3 マスから 6 マスで、高さが 3 マスから 6 マスのボードが与えられます。 各マスは、パネルが置かれているか、壁があるか、空白であるかのいずれかです。 パネルには 1 から 9 あるいは A から Z のいずれかの文字が書かれており、同じ文字の書かれたパネルは存在しません。 壁は 0 個以上存在し、空白のマスはただ 1 つだけ存在します。 例えば、次のようなボードが与えられます。ここで、壁は = で、空白は 0 で表されています。このパズル、5000問あるのです。そして一問が0.01点。100問といてやっと1点。手で解くことをある程度防ぐ設問ですね。 15パズルでの評価関数は各駒のゴールに対するマンハッタン距離合計を使うのがポピュラーな模様。その方向で、A*探索をRubyで試しに実装してみてあまりの遅さに音をあげてすぐにJavaにうつりました。 まずはメモリをじゃぶじゃぶつかって試みてみました。この時点で一晩で1000問程度回答。かなり厳しいです。 次はゴール状態から初期状態に向かってのA*探索を同時に走らせる双方向A*探索してみました。これでもくろみ通り、探索空間が小さくなってかなり成績があがり、3300問程度。その後はパラメータを少し調整し、メモリを増やすなどして、4300問まで頑張りました。 メモリ使いすぎで探索中にMacBook使えないのが辛くて、こんどはメモリをあんまり使わない反復深化深さ優先探索(IDDFS)を実装してみました。が、新たな解はほとんどみつけてくれません。 このあたりで飽きたのでgoでIDDFSを実装しなおして遊んでいたら「探索したノード数が一定数を超えたらその時点で評価値最良のノードひとつだけ残してそこから再度探索する」という乱暴な枝狩りをおもいつきました。これがそれなりに効果的で、最終的には4818問で終了しました。 この問題、30人近くが5000問すべてを解いています。そのひとたちは、そもそもメモリの使い方を最初からすごくしぼっていて、私の無駄遣い富豪プログラミングとは一線を画している様です。評価関数もいろいろ工夫されています。コード公開しているひと多数なので、後でじっくりみてみようと思ってます。 ]]>
40=
215
=86
空白は、上下左右のマスのパネルと入れ替えることができます。上のマスのパネルと入れ替えることを U とよび、同様に、下左右のマスのパネルと入れ替えることをそれぞれ D, L, R とよぶものとします。壁を空白やパネルと入れ替えることはできません。
パズルを解くというのは、与えられたボードの各マスを操作して、ゴール状態に持っていくことです。
ゴール状態とは、上の行から各行順番に、左から右に 1, 2, 3, 4, ..., 9, A, ..., Z という順にパネルが並び、最も右下のマスに空白が配置された状態のことです。壁のあるマスに対応するパネルは存在しません。例えば、左上のマスが壁であれば、ボード上に 1 のパネルは存在しません。
(中略)
いま、使うことができる L, R, U, D それぞれの総数があたえられます。 この総数は全パズルで共有されています。 例えばあるパズルを解くために L を使い切ってしまった場合、 他のパズルでは L を使うことはできません。 この総数を超えないようにしながら、なるべくたくさんのパズルを解いてください。
シンプルな神経衰弱ゲームです。カードはクリックすることでめくることができます。全 64 セットを解くことで問題クリアとなります。色が違うだけのカードが、最大1024枚出てくる神経衰弱。これを手でやろうなんていうプログラマはほとんどいないでしょう。 親切なことに、「ヒント」としてGoogle Chromeの機能拡張の例が出ています。これをベースに使えばとても簡単。JavaScriptでDOMさわってクリックして色チェックして覚えて、というだけOKです。 manifestを含むコードはここに置いています。 https://gist.github.com/1213056
Go 言語で、PNG 画像を入力として受け取り、その画像が何色使っているかを返す関数func CountColor(png io.Reader) intを実装してください。PNG 画像は io.Reader 型で与えられます。なお、入力の画像は R G B の各色の値が 0 から 255 までの 256 段階のいずれかであり、不透明（アルファチャンネルの値が常に 255）であることが保証されています。これも、goのimage/pngライブラリを使えば実に簡単です。
数がいくつか与えられます。なるべく少ない手数で数を全て取り除いてください。あなたは 1 手で、簡単簡単、とおもったらちょっとだけひっかかりました。 「5で割りきれてかつ2で割りきれない数が残っている」ときに、その数を含めて5の倍数を取り除くのが良い場合と、良くない場合があるのです。 結局、こんなコード書きました。幅優先探索。
- 全ての数を半分にする（端数は切り捨て）
- 5 の倍数 (0 を含む) を全て取り除く
のどちらかの操作をすることができます。
[[ -s "$HOME/.rvm/scripts/rvm" ]] && source "$HOME/.rvm/scripts/rvm"
rvm install ruby-1.9.2 --with-readline-dir=/usr/local
rvm use 1.9.2 gem install rails]]>
EPUB生成のライブラリをrubyで作ってみました。ブツはこちら。http://github.com/skoji/gepub
などなどいろいろ決め打ちにしています。
利用例はこんなです。
require 'rubygems'
require 'gepub'
require 'fileutils'
epubdir = "testepub" # epubのコンテンツを置くディレクトリ
title = "samplepub" # epubのファイル名
FileUtils.rm_rf(epubdir)
FileUtils.mkdir(epubdir)
# epub メタデータ作成
epub = GEPUB::Generator.new(title)
epub.author="the author"
epub.publisher="the publisher"
epub.date = "2010-05-03"
epub.identifier = "http://www.skoji.jp/testepub/2010-05-03" # identifierはURLのみ
# サンプルのコンテンツ生成。通常は、別途作成しているはず。
[ 'coverpage', 'chapter1', 'chapter2' ].each {
|name|
File.open(epubdir + "/#{name}.html", 'w') {
|file|
file << <<EOF
<?xml version="1.0" encoding="UTF-8"?>
<html xmlns="http://www.w3.org/1999/xhtml" lang="ja" xml:lang="ja">
<head>
<title>sample #{name} </title>
</head>
<body>
<h1>#{name}</h1>
<p>here comes the contents for #{name}</p>
</body>
</html>
EOF
}
}
# "coverpage"は表紙を想定。従って目次のデータには入れない。
# spineに入れた順にリーダでは表示される。
epub.addManifest('cover', "coverpage.html", 'application/xhtml+xml')
epub.spine.push('cover')
epub.addManifest('chap1', "chapter1.html", 'application/xhtml+xml')
epub.spine.push('chap1')
epub.addNav('chap1', 'Chapter 1', "chapter1.html")
epub.addManifest('chap2', "chapter2.html", 'application/xhtml+xml')
epub.spine.push('chap2')
epub.addNav('chap1', 'Chapter 2', "chapter2.html")
# この他にcssとかイメージがあれば、それもManifestへ追加する。
# cssやイメージはspineやaddNavへの追加は不要。
# container.xml/contents.opf/toc.ncxなどのファイルを生成
epub.create(epubdir)
# 生成したディレクトリから、epubファイル作成
epub.create_epub(epubdir, ".")
サンプル書いて気付きましたが、EPUB::Creatorというクラスの役割がぶれてるなあ。
]]>zip -0X testbook.epub mimetype zip -9rXD testbook.epub -x mimetypemimetypeは非圧縮(-0)で先頭に。他のコンテンツは圧縮してよし(-9)。属性は不要なので-X。ディレクトリは保存しなくてよいので-D。など。 ]]>
この本は、ユニットテストの基本的な考え方と基本的な書き方から始まります(Part 1)。
そして、ユニットテストで必須のテクニックである依存性の取り除きかたについて語られます(Part 2)。
その上で、ユニットテストをどう配置し走らせるか、どうやってリファクタするか、どんなふうに自動ビルドで運用するか、など実際に運用するときの考え方や方法論を解説します。そしてユニットテストのコードで陥りがちな罠(ひとつのテストにAssertion多すぎ、テストの名前が分からん、Setupに詰め込みすぎ、実行順序に依存、などなど)とその回避基準も明示します(Part 3)。
さらに、組織へのユニットテストを導入するにはどうするか(新しいことには抵抗がつきものです)を説明し、「タフ」な質問( 「これはどのくらい時間をとるの?」「これでほんとに効果がでるの?」など)にどう応えるか、回答例のカタログとともに説明します。最後の章では所謂"レガシーコード"に、どのようにユニットテストを適用していくのか、という話題に切り込みます(Part 4)。
上記で要約したとおり、「ユニットテスト」の話題に関する1から10までをカバーしてる本です。これだけ盛りだくさんで、厚さは300ページ程度と薄いのもよいです。でも内容は決して薄くないですよ。これからユニットテストを学ぶひとが最初から通読するのにはとても向いていますし、ある程度実践してるけど、いろいろうまくいっていない人(それは私)にも読み応えあります。
テスト駆動開発ベースの本や、JUnitの使い方の本はいままでもいろいろありましたが、ユニットテストの話題を網羅した、適切なサイズの本はこれまでなかったのではないかと思います。
"xUnit Test Patterns: Refactoring Test Code (Addison-Wesley Signature Series)"や、"レガシーコード改善ガイド (Object Oriented SELECTION)"を読む前に読むのもよいのではないかと推測します(推測なのは、どっちも未だ読んでいないので...)
翻訳されていないのが惜しいです。もし誰も版権とっていないのならば、翻訳したいなー、と本気で思っています。アンオフィシャルに蠢き中ですが、既に翻訳はじまってるよ、などの情報ご存じの方いらっしゃったら教えてください。
そして、ひろってくださる出版社募集中。
]]>
俺たちは有用性が証明されたかどうかでなく、流行や気持ちよさ、直観、「のみ」で技術や方法論を追いかけている(ことが多い)
今週になってからtwitterでの議論の中で、こんな発言がありました:
if your only learning comes from asking other people what *they* think - how can you claim to personally know anything?(このひとは、The Art of Unit Testing: With Examples in .net
の著者です。良書なので近々紹介します)
これは開発関連のツールに関連した議論の中で出てきた発言です。意図は、先のJim Coplienの発言と同じだと、私は理解しました。
肝に銘じます。
]]>
USING: io.directories io.pathnames kernel sequences io ;
IN: filelist
<PRIVATE
: filter-quot ( str -- quot ) [ file-extension ] swap [ equal? ] curry compose ; inline
PRIVATE>
: filelist ( path ext -- seq )
dupd [ directory-files ] dip filter-quot filter
[ dupd "/" swap 3append ] map nip ;
最初は、filer-quotのinline指定なしで書いてみました。そうすると、filelistのコンパイルに失敗します。曰く、
Got a computed value where a literal quotation was expected
filter-quotで生成したquotationを、filterに渡しているところでこのエラーが発生しているようです。filterはliteralのquotationじゃないと受け付けないと。それじゃ全然quotation使えないじゃん!
と悩むこと30分。inline指定しておけばよいことがわかりましたが...これは「optimizing compiler」でのみ効くとのこと。つまり、optimizing compilerを使わなければinline指定しなくても動くはずとのこと。
まだよくわからないので、続きます。
]]>今日はwordを定義する方法について調べます。普通のword定義はこういうふうにします。
: myword ( x y -- z ) dup * + ;
ほぼ意味のないwordですが、x + y * 2を計算します。mywordは名称。( x y -- z )はstack effectの宣言。: からはじまって、;で終わるまでがwordの定義です。これは、ソースコードのパース時に読み込まれ、定義が実行されます。
ランタイムでwordを定義することもできるそうで、それがdefine。
( scratchpad ) DEFER: foo ( scratchpad ) \ foo [ dup * + ] define Attempting to define foo outside of a compilation unit Type :help for debugging help. ( scratchpad ) [ \ foo [ dup * + ] define ] with-compilation-unit :errors - show 1 compiler errors ( scratchpad ) :errors ==== <Listener input> <Listener input> Asset: foo Missing stack effect declaration word foo :errors - show 1 compiler errors ( scratchpad ) [ \ foo [ dup * + ] (( x y -- z )) define-declared ] with-compilation-unit ( scratchpad ) 3 4 foo . 19
defineだとstack effect declarationがない、って怒られてしまいました。用途としては、既に定義されているwordの中身を置き換えるもの、のように見えます。いきなり定義するにはdefine-declaredを使う必要があるようです。いずれにせよ、wordとして用意しておかなくてはならないので、DEFER:を使わなくてはなりません。DEFER:はランタイムじゃなくてパースタイムだよな。ランタイムにwordを作る方法はやっぱりよく分かりません。
あと、with-compilation-unitが必要とのことですが、compilation-unitの詳細もよく分かっていません。要調査。
]]>Git Internalsは$9のPDF本。大変安い。Internalsというだけあって、仕組みを解き明かす本のようです。
Pragmatic Version Control using Gitは、名前から推測つくように、The Pragmatic Bookshelfから出ている本。電子版$22, 書籍版$34.95 + 送料, 電子+書籍$43.75。
まずはPragmatic Version Control using Gitの電子版を買って、読み始めています。iPhoneでも読めるので通勤の友です。前回疑問に思ったレポジトリをworkingの関係はすぐにすっきりしました。
Gitには3種類のエリアがあります: working tree (ここで実ファイルを編集), repository(コミットされたファイルの各バージョンが入っているデータベース), index(or staging area)(これからコミットされるファイルが一時的に入っている場所)。このindexの存在意義がいまのところ私には分かっていませんが、indexとかstating areaとかcachedとかいわれるものが、レポジトリとworkの間にはさまっていることを理解しておくのがGitをちゃんと理解してつかう第一歩なように思います。
その他にもGitはいろいろ特徴的なようです。本質的に「内容の」変更がtrackされること(ファイルではなく!)、branchが本質的でその処理も非常に軽いこと(だからbranchを使いまくる、従来のVCSからみると「過激な」使い方も気楽にできる)、VCSというよりは履歴つきファイルシステムのようなものであること、等々。
]]>