数独ソルバー続々

昨日も数独ソルバー野続を作業していましたが、もう無理だ!プログラムにバグがあって必ずフリーズしてしまう!と頭がパンクして、昨日は京王のダイヤDBを作って眺める作業に逃避してしまいました。

疲れたので答え見てやる!とweb検索すると引っかかったのが次のサイトでした。

nihemak.hatenablog.com

例えば空のマス目の数が30、そこに入る候補の数の平均が4になるとすれば探索範囲数は下記のようにしぼられます。(これでも処理時間は相当かかります。)
 42391158275216203514294433201(9の3乗)→1152921504606846976(4の30乗) 

ああ、これは時間がかかるのも当たり前ですね。9*9のマスしかないならブラウザ上でも処理時間は全然かからないでしょ、と思っていたのが甘かった。天文学的数字になるんじゃしょうがないです。

私がとった方法は「候補が複数あればそれに応じて分岐を作成、数字を入れていって矛盾があればその分岐は無効、最後まで残った分岐を採用」というやり方ですが、これは分岐が天文学的数字になってメモリも処理時間もバカみたいに食います。で、ブラウザに「反応が無いですよ」と言われてしまってアウトとなりました。

この記事を読んで、数独ソルバーというのはルールの実装は実に単純なので「いかにして処理の無駄をなくし正解を素早く見つけるか」が勝負になるということがわかりました。

来週もチャレンジしてみよう。

 

10行で解くおそろしいコードもあるらしいです。すごい

 

ブラウザ上で実用になる程度のjavascriptのコードが書けたら自分としては満足です。

 

(追記)K, Perl, Rubyなら2行なんてバカみたいなコードもあります。世界広すぎ

ShortestSudokuSolver


京王ダイヤ改正とか

TrainNavi2

更新しました。2015/09/25に行われた京王線系列のダイヤ改正に対応しました。

f:id:happyholiday:20151011150842p:plain

なぜこんなものを作るかと言うとダイヤを目で見て愛でるためです。時刻表は昔から好きです。おそらく時刻表は数字で表現されているからでしょう。何駅から何駅までは何分とか調べてるとうひょーってなります。このPHPアプリケーションを作ったのはプログラミングの修行のためもありますが動機のほとんどは趣味です。グラフィカルに列車っぽいものを走らせてみたら面白くていつまでも見ていられそうです。いまのところ実物の列車には興味はありません。

脱線しました。9/25改正の目玉は準特急の停車駅の増加です。笹塚と千歳烏山に止まるようになりました。でも速度は落ちていません不思議。ひそかに区間急行が仙川に止まるようになりました。快速が八幡山で待避するようになり全然快速じゃなくなりました。しかも京王新宿ではなく新線新宿から発車するようになりました。快速停車駅の住人はあの大深度ホームまで降りるのはたいへん。

私はいま京王線沿線には住んでいませんが以前に相模原線沿線の多摩ニュータウンの西の果ての駅からさらに山を18分のぼった所に住んでいました。当時は橋本直通特急などなく新宿から八王子と高尾行の準特急が10分おきに出ていて、それに乗ると調布でダッシュ乗り換えを強いられる不便なダイヤでした。9/25改正で橋本発の準特急が笹塚に止まり、しかも笹塚では都営線行の急行が待ち構えているという超便利なダイヤになっていて何だよチクショウという感じです。

当時は朝7時発くらいの最ラッシュ時間帯の急行で通勤していました。京王線は複々線化されていないため、この時間の急行は急行とは名ばかりで調布を出るころには本線から合流した電車と合わせて超過密ダイヤとなっており通常の半分の速度で運転します。15.5kmを35分かけて走ります。のろすぎ

で、京王は首都圏の列車混雑度の上位にはランクインしていませんがあれは各駅停車の混雑度平均ですから嘘の値です。急行はJR首都圏路線にほぼ匹敵する混雑率300%で身動きが取れず、橋本の時点ですでに満席の列車では座席の前に立たざるを得ずしかも後ろから押されるため電車が傾くと壁ドンならぬ窓ドンは必至です。荷物から手を放すとあれよあれよとどこかに行ってしまうおそれがあります。過密はしょうがないですがノロいのが致命的でとてもげんなりする朝ラッシュでした。

そんな列車に乗っていたら南平で人身事故なる放送が入り調布を目前にして電車が止まったことがありました。まだ調布が地上駅だった時代ですので平面交差に入れない電車は動けなくなり、そのまま2時間ほど閉じ込められました。その後もダイヤ乱れにより新宿についたのは3時間後。体調が悪くなり搬送された乗客もいたそうです。そんな思い出のある京王のダイヤを視覚化して眺めるのは至福です。8時前後の超過密ダイヤをJRや小田急と並べてみると京王のノロさが際立ち、キャッキャウフフ


数独ソルバー

最近webプログラムを全く作成しておらず腕がなまって仕方ないので、新聞で見たシルバーウィーク数独特集!みたいな記事に触発されて数独ソルバーを作ってみました。時間もないので即興で2時間半しかかけてません。ですので予想が必要な難しい問題は一切できず一意に決まるごく簡単な問題しか解けません。

 

f:id:happyholiday:20150920111201p:plain

 

プログラム倉庫に置きました。

 

今日はここまでだけれど、あとは再帰処理を使って予想→矛盾発見→候補から外す→予想しなおし→の繰り返しで一つずつ潰していけるはず。計算処理よりもインターフェースなどの準備段階の方が時間がかかったので問題を解く処理の強化自体は案外すぐできてしまうかも?


「LoaderLockが検出されました。」がうっとおしい

C++アプリケーションと.NETアプリケーション(C#, VB.NET)を混在して成り立っているプロジェクトで頻繁に出現するこのウインドウ。

f:id:happyholiday:20150904091901p:plain

長い長い時間をかけてデバッグしてきたのにこのメッセージのせいで処理が先に進まなくなると絶望的な気持ちになります。デバッグ中に.NET様の機嫌を損ねるマネージコードがあることが原因らしいですが、そんなこと言ったってそのようなコードは現実に実行されているし変更もできないので、どうしようもありません。

しかしこのメッセージをすっ飛ばす機能がありました。。!

「LoaderLock が検出されました。」の対処方法 | Managed DirectX プログラミング解説

あああなたが神か。

対処方法

LoaderLock例外の発生時に、処理を停止しないようにします。

メニューの【デバッグ → 例外】から、Managed Debugging AssistantsLoaderLockの項目の[スローされるとき]のチェックを外します。

http://so-zou.jp/software/tech/library/managed-directx/troubleshooting/images/exception.jpg

見事デバッグできました。ありがたいありがたい。


jQuery: showとhideの正体

 

1
2
3
4
5
// Instantaneously hide all paragraphs
$( "p" ).hide();
 
// Instantaneously show all divs that have the hidden style class
$( "div.hidden" ).show();

When jQuery hides an element, it sets its CSS display property to none. This means the content will have zero width and height; it does not mean that the content will simply become transparent and leave an empty area on the page.

まじかよ!

hide()⇔widthとheightが0

なんだってさ。知らんかった。ドキュメントって面白いねぇ。


自分用単語記憶ソフトを開発して1年、6000語以上学習できた

私の趣味の一つに外国語学習があります。かれこれ4年くらいになります。

震災後からスタート

きっかけは東日本大震災でした。地震後からさまざまな情報が氾濫し、毎日ニュースにくぎ付けになっていました。近隣のスーパーから水が無くなったり、住んでいる地域に放射性物質が降ったりと身の回りもえらいことになっていました。

ところが日本のメディアはパニック抑止のため情報統制がきつく、一番情報が早いのはなんと英BBCでした。

大学入試以来の錆び付いた英語力でざざっと読んでいましたが限界があり、文章の大意がつかめていたかどうかも怪しかったものです。この時から外国語を学び直してみよう、という考えが湧いてきました。

多言語理解を目指す

英語だけではなく、大学でかじった程度のフランス語や、近隣の中国語韓国語にも興味がありました。また、いずれ哲学書を原文で読むことを目指してドイツ語も学習を始めました。オペラを聴いて歌詞の意味が知りたいな!と思ってイタリア語も少しずつ学習を始めました。いまは時間が無くなってイタリア語は中止、韓国語も縮小運転中です。各国語についてはいずれ別の機会に記事にする予定です。

単語力が重要

外国語学習については様々なメソッドがあり正解はありません。4年間で色々なことを試しました。そこここに転がっている外国語吹き替えの日本製アニメを見る(いままでに10タイトルくらい見ました)とか、ドラマを見るとか、ラジオ番組を聴くとか、洋書にトライしてみるとか。しかしなかなか効率は上がりません。今考えると、自分のレベルを超越しているものばかり選んでいました。東芝のようにチャレンジしても見せかけの利益にしかなりませんでした。

色々な言語をかじるにつれて一つだけ確信したことがあります。語学は「単語力が最も重要」であるということです。単語を知らなければ読めません、聞けません。もちろん書けないし話せません。この思想をもって、単語力を伸ばすためにPHPの勉強を兼ねて自分で学習用ソフトを開発することにしました。

復習が基本、モチベーションも重要

語学は復習が基本です。100を適当に流すより、1を繰り返して確実に覚えた方がよいです。なぜなら語学は覚えることが多すぎて、一度流すと2回目に同じ表現が現れることはまれで、人間の宿命である「忘却」という厄介な敵によって記憶が持ち去られてしまうからです。

また、単語は単語帳を使って単独で覚えることをおすすめしません。これは個人的な好みの問題です。単語が全て日本語と1対1にくっついたただの代替物になってしまうのが嫌です。あと、単純に覚えるのが退屈です。文脈を使って文章の中で実際に使用されている原語の「生」の状態で覚えるのが最も効率が良いし、その「文脈」も自分で読みたいな!と思った文章であれば「絶対に理解してやる!」というモチベーションが働くので更に相乗効果を生む、と考えます。

以上のことから「文脈」「復習」に重点を置いたソフトを開発しました。忘却曲線の論理を借り、一度出題した問題を1日後・1週間後・2週間後・1か月後にそれぞれ復習するという仕様で、完成したのが1年前です。

毎日の学習を強制されるシステム

システムは単純で、「単語」「例文」「解答」を1組にしたDBを作り、1日後・1週間後・2週間後・1か月後に復習させるだけです。ただし、記憶の度合いによっていずれのステージに属するかをユーザーが選択できるようにします。次のような感じです。

f:id:happyholiday:20150809103631p:plain

「覚えていた!」なら1日後→1週間後に格上げ。「なんとなく覚えていた」なら1日後に残留。「忘れた。。」なら格下げです。それほど難しくなく、カスタマイズも楽勝でプログラムの勉強にちょうど良い規模のアプリケーションでした。まだwebデザインを勉強していない頃だったので、UIは淡泊でつまんねぇです。

このシステムを動作させてみるといくつかの利点に気が付きました。まず、復習が前提ですので1日サボると効果が無くなります。しかも1日に解く問題の量を枯渇させないため、毎日一定量の問題を登録しなくてはいけません。要するに毎日の学習を強制されます。これは受動的でネガティブに聞こえますが、1年続けていくための大きな原動力となりました。いまは1日に新規で16単語学習+問題登録しているのですが、復習で16単語*4=64問学習しなければいけないので、だいたい1日1時間かかります。

さらに、1か月後に復習するとかなりの頻度で忘れているということもわかりました。長期記憶というのは難しいです。1か月後の復習が終わった単語について、再復習するための処理も作ったのですが時間が足りずあまり動作させていません。。

検索機能も大事です。問題作成時に、実はすでに登録済みの単語だったということも多いのです。単語検索機能もつけたので、登録済みであることが分かるとついでに復習もできて「あ~この文章で使われていた単語だったのか」とちょっとうれしくなる上に、記憶が定着します。

1年で6000語以上の学習に成功

自己満足のために学習した単語数をグラフにする機能も付けました。flotr2というライブラリを使っています。おすすめです。

1年間使ってみた結果は次のようになりました。

f:id:happyholiday:20150809105134p:plain

登録単語数は約6200語。問題作成時に一度学習していることを考えると、1年で6200語を学習したことになります。1か月後の復習、つまり最低6回学習した単語だけで5000語あります。うち英語は1900語程度。

効果は?

こうかはばつぐんです。まず英語については、1年前苦戦していた洋書を読む速度が体感で倍速になりました。特にコンピューター書については平易な言語で書かれていることが多いので、楽勝で読めます。単純に単語だけを学習するのではなく、文章全体で分からなかった単語を調べるついでに復習するという形式にしたため、結果的に読む文章量が多くなりました。しかも楽しい。次は通常のスピードの3倍を目指して赤くなりたいです。分からない単語に会う確率は今後も減っていきますが、読むスピードが上がるので学習に割く時間は一定しています。

weblioに単語力診断があります。

これを1年前に診断したときの推定語彙数は7001~8000でした。今日試しに再テストしてみました。

確実に上がっています。でも2000語上がらなかったのは残念です。学習した1900語のうち、半分はまだ記憶が怪しいということなのかもしれません。来年もテストしてみます。

フランス語も、1年前に歯が立たなかったネイティブ向け新聞記事が、単語を調べればすんなり読めるようになってきました。NHK WORLD – French ここのものなら平易なのでそれなりの速度で読めるようになりました。いまだに分からない単語は1記事に1つくらいありますが。中国語、ドイツ語についても1日あたりの学習時間は10分に満たないのですが、確実に読めるようになってきています。

韓国語は私にとって非常に難易度が高く、しかも時間の都合上学習量を1日1語に限定したためなかなか進みません。いまは、紆余曲折を経て某ラノベの韓国語訳を教材にしていますが、開始から4か月経っても未だに冒頭のキョンのモノローグすら終わっていません。1つの文に3つも4つも知らない単語があるためです。いつになったらブーストするのやら。気長に10年くらい続けようと思っています。

Ankiがおすすめ

これから単語を学習したい人は、Ankiというソフトをお勧めします。基本思想は私が作ったシステムと同じです(Ankiは後で知りました)が、こちらの方が何段階も洗練されています。スマホでも使えるしweb上でも使え、しかもローカルとの同期も取れます。

Anki – powerful, intelligent flashcards

スクリーンショット 2015-07-08 15.22.22

【忘却曲線に基づいた暗記!?】暗記用アプリ「Anki」 | OUlife

私は先ほど述べたように、1対1の単語帳として使うのではなく、なるべく例文を「自分の読んだ文章から」持ってくることをお勧めします。そうすれば絶対楽しいですから。もちろん問題集は人の作ったものでなく自分で作ることが前提です。自分で作らないとこの手のソフトには意味がないと思います。

私は昔「速読英単語」で大学入試に備えましたが、これ、文章がつまんねぇっていう最大の欠点があるんですよね。時間も選択肢もない高校生にはこれしかないかもしれませんが、大人がこれを使うのはおすすめしません。自分の好みで選んだ文章で、自分だけの単語帳を作って学習するって本当にいいものですよ!


jQuery: イベントバブルをストップ

恥ずかしながらイベントバブルについて知らなかったので次の記事で学習しました。

 

イベントバブルとは

あるイベント(クリックしたとか)が発生すると、そのイベントはすべての親要素に通知されます。これがイベントバブルです。

<body onclick="alert('BODYがクリックされました')">
<div onclick="alert('DIVがクリックされました')">
<p onclick="alert('Pがクリックされました')">例:
<span onclick="alert('SPANがクリックされました')">
<button id="btn1" onclick="alert('BUTTONがクリックされました')">
ここをクリックしてください
</button></span></p></div>

上のコードを実行すると、ボタンを押したときBUTTON→SPAN→P→DIV→BODYの順ですべてのメッセージボックスが出ます。

バブルを止める

イベントバブルがうっとおしいので、jQueryを使って

event.stopPropagation();

を入れることで、バブルを止めることができます。

$( "#btn1" ).on( "click", function( event ) {
 // Prevent event from bubbling up DOM tree, prohibiting delegation
event.stopPropagation();
});

これだけです。楽勝ですね。

 

なお、超簡便な記法として、

$( "#btn1" ).on( "click", function( event ) {

return false;

});

でもよいです。でもこれだとわけが分かりにくいので、推奨されていません。おまけに、event.preventDefault() も一緒に実行した場合と同じ動作になります。preventDefaultというのは、既定のイベント、例えばボタンにsubmit属性が付いてたらページ遷移しちゃうとか、チェックボックスのチェックが変わるとか、そのようなオブジェクトの既定の動作のことです。

ですのでfalseを返すのはあまり好ましくありません。


jQuery: イベントにnamespace!?

 

jQueryはイベントにネームスペースを導入し、利便性の向上を図っています。

Namespacing Events

For complex applications and for plugins you share with others, it can be useful to namespace your events so you don’t unintentionally disconnect events that you didn’t or couldn’t know about.

1
2
3
4
// Namespacing events
$( "p" ).on( "click.myNamespace", function() { /* ... */ } );
$( "p" ).off( "click.myNamespace" );
$( "p" ).off( ".myNamespace" ); // Unbind all events in the namespace

 

click.myNamespace

のようにピリオドに続けてネームスペースを記述することで、複数のイベントをグループ化したり、逆にあるイベントの一部分だけをon/offしたりできる、という仕組みです。

ふつうnamespaceといえばもっと上位のカテゴリを表すものですが、jQueryでは何故かnamespaceと呼んでいます。クラスみたいなものですけれど、クラスとは違うものなので名前を変えたのでしょうね。

$(“p”).off(“click”);

だとすべてのp要素のclickイベントが無効になってしまうので、

$(“p”).off(“click.header”);

のようにheaderのネームスペースをつけた要素だけ無効にしたい、なんてときに便利になるでしょう。

やはり設計思想の問題か

でもこれ、p要素にクラスを付けておいて

$(“p.header”).off(“click”);

でセレクトするんじゃだめなの!?という疑問が消えません。その方が構造がスタティックで、分かりやすい気がします。

一つ解釈が考えられます。クラスを付けるためにはHTMLで文章自体に要素を付加することを意味します。イベントはプログラム側の都合なんだから、画面表示と直接関係のないクラスをHTML/CSSに持ち込むんじゃねぇ!という思想が働いているのではないかと思いました。

ですので、プログラムの都合はプログラム内で完結してやるようにしましょう。


Windows8.1(64bit)+PHP環境でLZHファイルを解凍したい

あるwebサービスを作ろうとして、LZHファイルの自動展開が必要になったので方法を調べて試行錯誤していましたが、難しかったのでメモします。

PHPからはexecコマンドを使って、コマンドプロンプトと同じ仕様でwindowsプログラムを走らせることができます。

まず、本家本元lha.exeを使用しようと思って、こちらのlha255.exeをダウンロードしました。

ところがスクリプトを走らせてもうんともすんとも言いません。

エクスプローラー上からlha255.exeをダブルクリックしてみました。

f:id:happyholiday:20150726100303p:plain

がっくし。64ビットマシンでは使えなくなったようです。

次に、既にPCにインストールして毎日使っているwinrarが使えるか試してみました。あまり知られていませんがwinrarはコマンドラインからも実行が可能です。右クリックメニューだけではないのです。

W150724.lzhというファイルを解凍したいです。getcwdなる関数がカレントディレクトリをゲットするスペルであることが分かりましたので、次の呪文を唱えてみました。

$cd = getcwd();
$cmd = “C:\\Program Files\\WinRAR\\winrar.exe x {$cd}\\W150724.lzh {$cd}”; 

 

exec($cmd);

何もおこりません。コマンドプロンプトから実行するとうまくいくのに、PHPからは効果がありません。マホトーンでもかかってるのかしら。

しょうがないので次は単独のexeでかつコマンドライン上で使えるソフトを探しました。すると次のサイトで「lhact」というプログラムを発見しました。

Allergy Design Office プログラミング、無線LANからイタリアンまで

これを使い、スクリプトと同一フォルダにlhact.exeを置いて、呪文を唱えてみました。

$cmd = “lhact x W150724.lzh”;
exec($cmd);

今度は上手くいきました。ファイルが解凍されていることを確認できました。解凍してファイルが出来上がるなんてスーパーマリオ3のワールド6でファイアボールを使ってコインをゲットしてるみたいですよね。

というわけで、Windows8.1(64bit)環境でPHPを使いLZHファイルを解凍したいというとてもマイナーな人には、lhactを使うことをお勧めします。


PHP: パフォーマンス改善のためにすべきこと

• Avoid  printf() when  echo is all you need.

• Avoid recomputing values inside a loop, as PHP’s parser does not remove loop invariants. For example, don’t do this if the size of  $array doesn’t change:
for ($i = 0; $i < count($array); $i++) { /* do something */ }

Instead, do this:
$num = count($array);
for ($i = 0; $i < $num; $i++) { /* do something */ }

• Include only files that you need. Split included files to include only functions that you are sure will be used together. Although the code may be a bit more difficult to maintain, parsing code you don’t use is expensive.

• If you are using a database, use persistent database connections—setting up and tearing down database connections can be slow.

• Don’t use a regular expression when a simple string-manipulation function will do the job. For example, to turn one character into another in a string, use str_replace() , not  preg_replace() . 

 

———Programming PHP 3rd edition 325P

 まとめると

・printfよりもechoを使え

・for文の条件に関数を入れるな

・includeするファイルは分割して最小限にしろ

・データベースを開いたらコネクションを使いまわせ

・簡単な文字列操作に正規表現を使うな

となります。ふつうですね。普通すぎます。いつも仕事でやってることと変わりません。パフォーマンスの低下の原因って、どのプログラミング言語でも似たようなもんなんですね。安心しました。