2007/12/11

数独ソルバー

数独ソルバーを書いてみました。

http://pa-n.sakura.ne.jp/200712/sudoku/


いきさつ

あーPS3買ったのにやりたいゲームないなー

体験版やるか

GT5 prologue体験版も飽きたなー
てか、prologueの体験版かー
GT5は来年12月って.....

レミング........

ぽちゃぽちゃあひるちゃん.............(買った \840)

.................

カズオ........


他の数独ソルバーのアルゴリズム

http://www.sudoku.name/sudoku-solver/jp

  • 解いている様子が見れるのでおもしろい

http://d.hatena.ne.jp/bellbind/20060712/1152692054

  • 改良版はコードが簡潔
  • 再帰をうまく使っている

http://www.ecclestoad.co.uk/blog/2005/06/02/sudoku_solver_in_three_lines_explained.html

  • コードが簡潔
  • 再帰をうまく使っている

http://echoo.yubitoma.or.jp/weblog/MASA-WA/eid/520627

  • コードは公開されていない?

ところで、これらの(コード公開の)ソルバーには次の共通点があります。

  • どのマスを仮定するかを決める際、候補の少なさを基準にしていない
  • 左上から右下にみていって、空白だったら確定マスに矛盾しないように仮定する

これをちょっと変更して、今回自分が書いたやつみたいに、「候補が少ないところを優先して仮定する」ようにすることで、

空白マスがたくさんある(=仮定がたくさん必要な)問題に対しては目に見えて高速に解けるようになります。

直感的には、次の2つのループ回数

(外側)9×9×9×...×9×8×5×2(内側)

(外側)2×5×8×9×...×9×9×9(内側)

との違いといいますか。(ループ回数はイメージです)

ループの内側にいくにしたがって、仮定したことによる候補の絞りこみで結構すぐに矛盾があらわになりがちだと思うんですね。

なので、最外ループの反復回数が少ないと、わりとすぐに探索木が半分になったりするわけです。

2007/12/10

second life, home

について。

(PS3のhomeはいつ始まるかわからんですが...)


誰か(友達とか)に会うためには、「今」、「自分がいる場所」にその人が居る必要があると思うんですが、

自分が居る場所付近に、過去にいた誰かの痕跡を表示したりする仕組みがあれば、条件が緩くなって誰かに会える可能性が上がって、コミュニケーションが取りやすくなるんじゃないかと思いました。

ニコニコ動画とか、ふつうの掲示板とか、ふつうのメールみたいに。

「今」が重要なんだ、という考えかもしれませんが、今じゃなくていいぜというオプションはあっても困らないような気がします。

2007/12/06

if文と三項演算子

カツマさんのところで、javascriptのif文と三項演算子の速度比較をされたようです。

三項演算子の方が速い場合が多い理由(の予想)

if文は「文」なのに対し、三項演算子は「式」なので、解釈系(インタプリタ)や翻訳系(コンパイラ)が分岐除去の最適化をしやすいんじゃないかと思います。

なぜ式だと分岐除去がしやすいかというと、任意の式が2つ与えられたときに、「それらが同程度の計算で実行できるかどうか」の判断が文2つのときよりも簡単に求まるからかな、と思います。

if文の場合も三項演算子の場合も、then節とelse節とがどちらも十分単純で、異なる部分に分岐の有無の差がなかったりする場合に、分岐を除去して2つを投機的に計算して、後から条件の結果より2つの結果を選択するという最適化ができそうですが、

式の場合、true-exprとfalse-exprが関数呼び出しを含まなければ分岐除去できそうなのに対し、文の場合はthen節とelse節が全く同じ構造を持つ文でないと分岐除去できなさそう、という。

処理系の最適化モジュールを書くのに必要な手間が、式の場合の方が少ないからなんじゃないか、という予想です。

個別の処理系に関しては、処理系の実装次第なのでしょう。

ちなみに、gcc 3.4, -O2 の場合は



int main(int args, char** argv)
{
return (int)(args==5 ? "1022" : "1050");
}


でも



int main(int args, char** argv)
{
if(args==5) return (int)"1022"; else return (int)"1050";
}


でも同様に分岐除去されていないアセンブリが出てきました。



ちなみに!Cell/B.E. の SPU は分岐のペナルティが18cyclesくらいあって結構でかいので、できるだけ三項演算子や spu_sel を使って処理系が分岐を除去しやすくする、または明示的に分岐除去する、という方法がオススメされているようであるッッ......!!!

2007/09/12

HTML/JavaScript コメントアウト支援マクロ

最近、JSONとかWebAPIとかマッシュアップとかそちらの方をかじろうとしておるのですが、

HTMLとJavaScriptのコメント挿入や削除が面倒で

秀丸マクロライブラリィを探してもこれだ!的なのがなかったし

今後もずっと手動でコメント・アンコメントしてくのかと考えるとやる気が下がりそうだったので

マクロを書いてみることにしました。(早くも脱線)


行頭ではなく、行頭の空白の後ろに // を入れるような、Visual Studio みたいな少しインテリゲンツィヤ的なものができたので

しばらく使ってみて不具合が出なかったら公開しようとおもいます。

前々からほしいと思っていたこともあり、これは仕事とかでも生産性アップの予感ッ!!

2007/06/22

キーワード自動録画 第2回 試行錯誤編

前回までのあらすじと今回の内容

前回のキーワード自動録画 調査編では、TV番組のキーワード自動録画のために必要な要素を考え、それぞれどんなソフトを使えばいいのかを調査しました。

今回の「試行錯誤編」では、ユーザーがTVチューナー+ビデオキャプチャボードを買ったと仮定して、(というか自分が買ったんですが、)試行錯誤しながら自動録画システムを完成させていきます。



今回買ったTVチューナーボード

これ! (マウスみたい............)


WinFast PalmTop TV (6,980円 + 送料900円)

USBで繋がるやつです。電源供給もUSB経由でできます。
したがって、接続としては

 TVアンテナ線 ~ PalmTop TV ~ USBケーブル ~ 録画用PC

ということになります。



付属ソフトで「iEPG予約」を試してみる

「iEPG対応」と書いてある付属ソフトなら、Yahoo!テレビなどのテレビ番組表サイトで「iEPG」などというアイコンをクリックすると予約画面になると思います。



今回買ったハコの付属ソフト「WinFast PVR」では、上記のような画面になりました。

OKを押すと、実際に予約されます。



誰がOKを押す?

ここで、1つ問題が発覚しました。
OKを押さないと予約されないので、自動録画をするには何らかの仕組みでOKを押してあげる必要があります。



自動クリックソフトを探す

Auto Clicker というソフトを見つけたので、これを使ってクリックさせることにします。

Auto Clicker の設定ウィンドウにある十字アイコンを、
録画予約確認ウィンドウにある OK ボタンにドラッグ&ドロップします。

監視間隔は 5 秒くらいにしておきました。

あとは Auto Clicker をスタートアップに登録しておけば、自動クリックのからくり完成です。



TVスケジューラの設定

自動取得や検索ワードの設定などは本家を見て頂くとして、
WinPVR と組み合わせる際の注意を1つ。

それは、「テレビ局名をデフォルトの2バイト文字から ASCII 文字コードに変える」という事です。

iEPG ファイルに記載されているテレビ局名と WinPVR 側のチャンネル番号を結びつけるために iEPG 予約時には初回だけ録画チャンネルを選ぶ必要があるのですが、この時 iEPG ファイルのテレビ局名に2バイト文字が含まれていると WinPVR がうまくそのテレビ局名を記録してくれず、再起動すると消えてしまうのです。

iEPG のテレビ局名が ASCII なら大丈夫なようなので、TVスケジューラでそのように設定します。

TVスケジューラには、ウェブ番組表から取ってきた iEPG ファイルに含まれるテレビ局名を設定しておいた対応表に従って書き換えてから録画予約ソフトに渡すという機能があります。

これを使って、例えば「テレビ東京」を「JOTX」や「TOKYO」などに変換するように設定します。iEPG と WinPVR でチャンネルの対応が取れればいいだけなので、名前はなんでもよいです。

設定が終わったら、自動録画する可能性のある全チャンネルで初回予約をして WinPVR に覚えさせておきます。

...この問題には解決するまでに結構時間をかけてしまいました(笑)



まとめ

ここまでで一通りキーワード自動録画システムが動くようになりました。

今回の環境の場合、
用意したものは次の通りです。

1. TVチューナー+キャプチャボードが入ったハコ

2. iEPG対応の録画ソフト(TVチューナーに付属の LeadTek WinPVR)

3. TVスケジューラー

4. Auto Clicker

予約した後の実際の録画もちゃんと動くようなので安心しました。

ひとまずこれでしばらくつけっぱなしにしてみようかと思います。



おまけ(1) - 試行錯誤の結果ボツになったもの

自動クリック関係で最初に試したのは、AutoMouse でした。

このソフトを使うと、予め指定しておいた画像パターンと一致する場所をスクリーン上で探し、そこをクリックすることができます。

指定した画像パターンが出てくるまで待機していてくれるようなので、ウィンドウがずれたりしても大丈夫そうです。

が、このソフトは CPU 時間を食うようで、AutoMouse を起動しながら実際にテレビ録画をするとまったく録画できませんでした。
PC のスペックによるかもしれませんが、残念ながらうちのシステムでは使えないということでボツになりました。



おまけ(2) - iEPGファイルの中身

ちなみに、iEPGアイコンをクリックしたときにダウンロードされるファイルの中身はこんな感じです。

Content-type: application/x-tv-program-info; charset=shift_jis
version: 1
station: NHK総合
year: 2007
month: 06
date: 21
start: 04:30
end: 08:15
program-title: おはよう日本
program-subtitle:
description:[ニュース]▽[天気]▽夏商戦キーワードは“自分を磨く”▽国会会期延長は与野党攻防▽遺族も裁判に参加へ
performer:[出]松尾剛 [出]首藤奈知子

おはよう日本


こんなテキストファイルになっていて、放送日時や番組の詳細情報が書いてあります。

このファイルが、拡張子 "tvpi" に関連付けられたTV録画ソフトに読み込まれ、そのソフト内で録画予約がスケジュールされるというわけです。

2007/06/07

キーワード自動録画 第1回 調査編

PCでテレビ番組を自動録画する仕組みについて調べてみました。

動機、背景

1. 指定しておいたキーワードにマッチするテレビ番組を自動録画したい!

2. 安く済ませたい!2~3万まで!



ということをやりたくなったので

TVチューナー+キャプチャカード+ソフトで録画システムを組む事を考えています。

実は昨年、Perl + VB でスクラッチから書いてみたんですが、肝心のキャプチャカード(玄人志向のやつ)の動作が不安定だったりして安定運用には至らず、1ヶ月くらいでもう使わなくなってしまいました。


ここで改めて自動録画システムを組むことを考えてみようというわけです。




必要な要素

1. ネットからTV番組表を取得する部分

xmltv など。


2. 指定しておいたキーワードとTV番組表を比較して、合致するTV番組データを抽出する部分

TVスケジューラーは 1, 2 までできます。


3. スケジューラ。TV番組データと時刻から、録画開始/終了プログラムorルーチンを起動する部分

TVチューナ+キャプチャボード付属のソフトが iEPG 対応だったりすると、スケジューラもついていると思います。

単体ソフトとしては、NanoPocketがあります。


4. 録画部分

TVチューナ+キャプチャボード付属のソフトや、GraphEdit(マルチメディア系デバイス?の制御がGUIでできるもの)など。


GraphEdit についてはGraphEdit 非公式ガイドが参考になります。


(5. 必要に応じて、1, 2, 3, 4 間の呼び出しやデータ受け渡しをサポートするスクリプト)




ソリューション

基本的に、前述の 1~4 をうまく組み合わせればできるはずです。

組み合わせる場合、エラー制御が意外と肝になるかもしれません。
例えば、録画に失敗したときに GUI のメッセージボックスが出ちゃうと困るとか。

●xmltv(1)+MythTV (2, 3, 4)

linux only

●TVスケジューラー(1, 2)+iEPG対応したTVキャプチャボード付属ソフト(3, 4)

Windows ではこれが楽かな

●TVスケジューラー(1, 2)+NanoPocket(3)+GraphEdit 起動スクリプト+録画できるように設定したGraphEdit(4)

録画が付属ソフトでうまくいかないとか、付属ソフトがなかったとかいうときはこれでしょうか。

録画して出来たファイルをリネームするスクリプトとかもいるでしょう。

●スクリプト(1, 2, 3)+GraphEdit

去年つくったやつはこのパターンです。1,2,3 は perl、GraphEdit 制御部分は VB です。

勉強用と割り切ればいいですが、そうじゃない方には面倒なだけなのでナシですね。

2007/05/21

アクセスカウンタもどき 9821.00.0005

(過去に作ったものを紹介するだけです。最近新しくなったわけではありません)



ソフト概要

起動回数をカウントして、表示するソフトです。
だいたい上のような起動画面になります。

Windowsのスタートアップグループに登録しておくことで、パソコンが起動するごとに何回目の起動かを知ることができます。

…これだけです。「俺のパソコン、アクセスカウンタ付きだよ!」と、お友達に自慢してあげましょう。(^^;



ダウンロード



動作環境

Windows95 以上(たぶん...)

VB4 ランタイムが必要です。(すいません)



動作確認

NEC PC-9821 Cb2/B (i486DX2 66MHz, RAM 8M, HD 420M) (;_;)

(12年前は、メモリ8MBが普通だったんだなぁ。)



懐かしのパソコン通信www

 なお、このソフトはパソコン通信のPC-VANにも登録してあります。

 場所は、SIG WINDOWS(ジャンプコード J WINDOWS )→7.OSL→10.ホビーソフトウェア の、ファイル番号 262番です。


2001 年に廃止された PC-VAN にも登録してあったみたいですwwww

PC-VAN の「テキストWWWサービス」と簡単なスクリプトで、掲示板への自動投稿とかしていたことだなぁ。

2000年 センター試験英語(第5問)

(過去に作ったものを紹介するだけです。最近新しくなったわけではありません)







ダウンロード



ソフト概要

 2000年 センター試験英語(第5問)で出題された、
 コンピュータゲームについての会話文をもとに
 そのゲームを作ってみました。以上。まる。




事の成り行き(当時の文章)



 とある掲示板において、
 1月17日(月)16時35分39秒、"廃人ヒナ"氏に
 
  英語の長文に出てきたゲーム作ってみたら?>岩前、ぱん仔
 
 と言われた"ぱん子"(僕)は、1月17日(月)23時59分33秒に
 
  よし、作る!!<大問5
  今から48時間以内にHPにアップしたら
  ジュースおごって?>廃人ヒナ
 
 という返事を書いた。
 その後48時間以内になんとか完成させ、公開。
 そんなこんなです。(^^;;;まいったまいった。




2日間かかりっきりだったので、私大の願書提出がぎりぎりになってしまって母に叱られたのを覚えています・・・



動作環境

Windows95 以上(たぶん...)

VB4 ランタイムが必要です。(すいません)



操作方法

 [←] … 左に移動
 [→] … 右に移動
 [↑] … 向こうに移動
 [↓] … 手前に移動
 [スペース] … ジャンプ
 [リターン] … 何かをつかむ
 
 ゲームスタートは、メニューから又はスペースキーを押してください。。



パッケージ内容

 readme.txt (このファイル)
 center5.exe (本体)
 goal.wav (効果音)
 jump.wav ( 同 )
 ouch.wav ( 同 )



開発環境

 NEC PC-9821 CanBe2/B メモリ44MBに増設。
  + スキャナ (Canon CanoScan 300)
  + Windows 95
  + Microsoft Visual Basic 4.0 std
  + ペイント
  + アイコンエディタ

2007/05/05

公開中の秀丸マクロ