Make 10

1から9までの4桁の数字と四則演算で10を作る遊びを知っていますか?
小学生からできる遊びですが、以外に楽しめます。

車のナンバー、時間、切符等、わりと巷には4桁の数字があります。
道を歩いていると暇なので、車を見かける度にやっているのですが、
ちょっとプログラムを作って解いてみました。

この問題のサイズは、高々9^4x4^3 = 419,904 なので、Brute Force で十分です。
実際に遊ぶ場合は数字の並び順は任意なので、重複組合せとなり 495 通りです。
そのうち解を持たない(10にならないの)は、62個なので、62/495=12.5%となります。

解けないことは少ないと感じてたのですが 12.5% とは、以外に解けないなぁと思います。
10台の車をみたとしたら、そのうち1台のナンバーははずれ。

また、1通りしか解を持たないのは 42個で、除算を含むのは 28個あります。
除算は分数の計算をする必要があって 3577のように1を作るもの以外は、
中々、思いつきません。

以下に、解が1個で除算が必要な数字を書いておきます。
頭が固くなっているなと感じたら、試してみてください。
頭が柔らかくなるかもです。

ちなみに、プログラムは C# で書いて、669行になりました(コメントはほとんど無し。)
結果を infix notation にしたり、Ratio arithmetics を実装したり、Enumerator を作ったりと、
余計なことをしているからかもしれません。

Lisp だったら、prefix notation で ratio もあるので、もっと短かったはずですが、
今回は、現在、作成中のVMのサンプルにするために、C#にしました。

Enjoy!

1 1 6 7
1 1 9 9
1 3 3 7
1 4 4 5
1 4 7 9
1 4 8 9
1 5 5 5
1 5 6 6
1 5 9 9
2 2 8 9
2 3 9 9
2 6 6 6
3 4 7 8
3 4 8 8
3 5 7 7
3 5 8 8
4 4 4 8
4 4 6 6
4 8 8 8
5 7 7 7
5 8 8 8
5 8 8 9
5 9 9 9
6 6 7 8
6 7 7 9
6 7 8 8
6 7 9 9
9 9 9 9

P.S.
* C++ STL に next_permuation と言う関数があるのを初めて知った。
* STL は、見慣れない indentation を使っているので、リーフォーマットしないと読み図来。Hard Tab 使っているし。:-<

HDD がぶっ壊れた (ToT)

Seagate の 700GB のHDDが壊れた。

で、Seagate の 1.5GB HDD を2個買ってきた。
(ST31500341AS)

温度は、36℃と35℃

値段は12,500円x2台=25,000円。

HDDも安くなったもんだ。

Haskell体験記

この連休はHaskell Compilerでも作ろうかなと、Haskellで色々遊んで見た。

と言っても、プログラムを組んだわけでは無く Compiler の設計のために Haskell98 Report を深く読んで見た。

前準備として Real World Haskell と Yet Another Haskell Tutorialもね。

Lisp から乗り換えようかなと言うのがそもそもの動機だけど、マイナーからマイナーへと言ったところでしょうか。

Haskell に惹かれたのは、

• Static Typing + Type Inference
• Lazy Evaluation

Static Typing は Lisp が Dynamic Typing だからで、Lazy Evaluation は Lisp が Egaer Evaluation だから。

Static Typing だけならば SML でも良いのだけど、Lisp でも Static Typing はできるのし、SMLはなんとなく Lisp のライバルのような気がして...

Lazy Evaluation も、もちろん Lisp でも可能で、delay macro と force function があります(Scheme では言語仕様になっている)。

Algebraic Data Type は、Haskell の魅力の一つで(SMLにもあり)、これと Pattern Matching を組み合わせると、集合値から簡単に値が取り出せる。

以前に SML を検討にした時に SML を落としたのは、ref の存在で関数型言語と言いつつも、代入可能な変数が必要だったからなのを思い出した。

Haskell の場合は IO Monad で、代入可能な変数や配列などを実現している。

まぁ、関数型言語と言っても実世界とのやりとり(I/O)は、Pure ではいられないので、Monad は I/O をきれいに表現するために導入してされている。

Clean では I/O は、Uniqueness Typing で行われていて、IO Monad より判りやすい。

Haskell の嫌なところは、

1. 記号が多すぎ。<code>(,,,)</code>って…


2. Monad すぎ。なんだかんだ言って、最後は Monad で do-syntax


3. 言語仕様が不安定。HackageDB から幾つかダウンロードしたけど、最新版のGHCでコンパイルできず。


4. Interactive に使い難い = Scripting が難しい


5. lhc (literature Haskell) の仕様が ">" と LaTex 版があって区別するのが困難


6. Standard Library が GHC と NHC 様になっている


7. CPPが多用されている(言語仕様にない。Cleanにはマクロがある)

と言ったところで、言語仕様の安定性は Clean のほうがよさそう。さらに、Cleanだと、Dynamic Typing とか、簡単に Strict Evaluation を記述できるとか、Module System は Clean のほうがしっかりしている(definition/implementaiton)とか…

Lazy ML もはやらないし、Miranda との関係は Gosmacs と GNU Emacs みたいだし…

Haskell は Perl6 のおかげで光があたったと言ったところでしょうか。

Multiple Core だと、関数型が有効ぽくて、遅延評価はさらに並列処理になじみやすい(?) でも Exception がうまく扱えないぽいかなぁ

と言う訳で、Lispから乗り換えるのは無しの方向で。

まぁ、また来年検討しましょう。

iPod vs Gigabeat U408

SIGNEO がわずか1年半で壊れたので、
やっぱり、日本製かなと思い、Gigabeat U408を購入した。

自動リセット機能があるらしく、再生中にメニューを操作すると、
リセットされる。おかげでわずか1時間の間に6回も時刻を設定するはめになった。

音はiPodよりも良いような気がする。

操作性や安心感は iPhone のほうが上かな。

iPhone は、この7ヶ月で、主導リセット3回だし。

現在、聞いているのは、これ

Amazon はメモがわりになるな。(^o^)

Wishlist にもへんなものを入れておっと。

Windows Product Key

25 桁の24進数なので、1秒に1個確認できるとすると、
(expt 24 25) = 32,009,658,644,406,818,986,777,955,348,250,624 秒
掛かります。

(log (expt 24 25) 2) = 114.62406

PidGenX (pidgenx.dll) は、速かったり(0.1秒)、遅かったり(14秒)するので、
もっと掛かる。

SETI@HOME みたいに、Grid Computing すれば解けない問題では無さそうですが、
参加する人はいないだろうなぁ。

Product Id を表示するプログラム
128bit の数値を 24進数表示するだけです。

#define WIN32_LEAN_AND_MEAN
#include <windows.h>

// cl /O1 /Ob2 /Oi /Os /Oy /GT /GL /GF /MT /GS- /Gy /Gr /TP pid.cpp

#pragma comment(lib, "advapi32")
#pragma comment(lib, "kernel32")
#pragma comment(lib, "user32")

typedef unsigned __int32 uint32;
typedef unsigned __int64 uint64;

struct u128
{
uint32 m_d[4];
}; // ui128

uint32 div128_32(u128* pU, uint32 nV)
{
u128 oQ;
uint32 nRem = 0;
for (int i = 3; i >= 0; i -=1)
{
uint64 u64 = nRem;
u64 <<= 32;
u64 |= pU->m_d[i];
oQ.m_d[i] = static_cast<uint32>(u64 / nV);
nRem = static_cast<uint32>(u64 % nV);
} // for i
::CopyMemory(pU, &oQ, sizeof(oQ));
return nRem;
} // div128_32

char* doit()
{
static char s_szResult[100];

LONG lResult;
HKEY hKey;

lResult = ::RegOpenKeyExA(
HKEY_LOCAL_MACHINE,
"SOFTWAREMicrosoftWindows NTCurrentVersion",
0,
KEY_READ | KEY_WOW64_64KEY,
&hKey );
if (ERROR_SUCCESS != lResult)
{
return "Can't open HKLMrn";
}

BYTE rgbData[256];
DWORD cbData = sizeof(rgbData);
lResult = ::RegQueryValueExA(
hKey,
"DigitalProductId",
NULL,
NULL,
rgbData,
&cbData );

::RegCloseKey(hKey);

if (ERROR_SUCCESS != lResult)
{
return "Can't read DigitalProductIdrn";
}

u128 oPid;
::ZeroMemory(&oPid, sizeof(oPid));
::CopyMemory(&oPid, rgbData + 0x34, 15);

char szPid[25+1];
const char k_rgchDigit[25] = "BCDFGHJKMPQRTVWXY2346789";
for (int i = 0; i <25; i++) int nDigit = div128_32(&oPid, 24);
szPid[24 - i] = k_rgchDigit[nDigit];
} // for i
szPid[25] = 0;

char* psz = s_szResult;
for (int i = 0; i <25; i++) if (i > 0 && 0 == (i % 5))
{
*psz++ = '-';
}
*psz++ = szPid[i];
} // for i

*psz++ = 0x0D;
*psz++ = 0x0A;
*psz = 0;

return s_szResult;
} // doit

int showit()
{
char* psz = doit();

::MessageBoxA(NULL, psz, "Product Id", 0);

HANDLE hFile = ::CreateFileA(
"pid.txt",
GENERIC_WRITE,
0,
NULL,
CREATE_ALWAYS,
0,
NULL );

DWORD cbWritten;
::WriteFile(
hFile,
psz,
::lstrlenA(psz),
&cbWritten,
NULL );

::CloseHandle(hFile);
return 0;
} // showit

int WINAPI WinMain(HINSTANCE, HINSTANCE, char*, int)
{
return showit();
} // WinMain

extern "C" void __cdecl WinMainCRTStartup()
{
int iRet = WinMain(::GetModuleHandle(NULL), NULL, NULL, 0);
::ExitProcess(iRet);
} // WinMainCRTStartup

DivX と一緒

いまいちプログラムを組む気が起こらないので、
DivX のエンコードを実験してみた。

エンコードなどめったにしないので、DivX Converter を使っていたが、
1年前の DivX Convert はリサイズしたいなかったが、
6.8 のエンコーダは 740x480 を 652x480 にリサイズしていた。
とは言うもののまったく気が付かなくて、ふとプロパティを見て発覚した。

と言う訳で、色々試してみた。

Source: 相棒3 第4話 4分54秒

Method	Encoding Mode	Data Rate (kbps)	File Size (KB)
2Pass/1,000	fastest	2,118	40,968
1Pass/1,500	balanced	2,864	35,157
1Pass/1,500	fastest	3,081	58,943
2Pass/2,000	balanced	4,439	76,909
1Pass/2,000	balanced	3,716	73,844
2Pass/2,000	better	4,512	76,897
1Pass/2,000	better	3,668	76,772
2Pass/2,000	extream	4,272	76,920
2Pass/2,000	fastest	4,162	76,914
2Pass/2,000	high perforamnce	4,335	76,878
2Pass/3,000	balanced	6,015	112,627
QB/2	balanced	7,519	118,083
QB/3	balanced	4,185	71,529
QB/3/H.263opt	balanced	4,427	75,347
QB/3	fastest	4,834	83,622
QB/3	high performance	4,377	76,405
QB/4	balanced	3,196	51,497
QB/4	fastest	3,849	67,647
QB/4	high performance	3,487	61,667

Certification profile は Unconstrained
Quantization は H.263、
Interlace は De-interlaced

1000, 2000の差はわかるけど、2000と3000 の画質の差はよくわからなかった。

PC に保存して見るだけなので 2Pass を使う意味はないので、
1pass-quality base 4, balanced で行く事に決定。

エンコード時間は、E6600@2.88G で再生時間よりも少し早いぐらい。

17年ぶりの backquote の実装

とある日、2~3時間ほど空きができたので、
TinyCL 用に backquote を C++ を実装することにした。

これまでは頑なに lisp で実装した backquote を使ってきたけど、
backquote を実装するために、多くの関数とマクロを実装しなくてはならないので、TinyCL では genesis を使いたくないからである。

で、evcl の実装をみたら何かよくわからないので、CLtL2を焼きなおすことにした。

が、これが問題で CLtL2 のやつはネストした backquoteを展開してしまうので、
これをそのまま macro expander としては使えないことに、実装が終わってテストしている時に気がついた。orz

う〜ん、それでまったく違う実装していたのね。

まぁ、parse の部分だけを返れば simplifier は使えそうだなと思って parse を書き換えたが、あまり効率の良いコードに展開してくれないので、
simplifier を improve しようとしたけど、基本が append form の単純かなので、list form を処理しなくてはいけないので面倒くさい。

あとは maptree, reverse, every, notany とか lispy なのは、どうにもしっくりこなにので、parse の出力をコードリストに代えた。

これで simplification がやりやすくなって、結果 30KB ほど function object を小さくすることができた。

まぁ、reverse とか maptree とか使っていないので、処理もメモリ効率もよくなり速度も速くなったとおもうけど、これらは未計測。ほとんど測定誤差の範疇になると思うけど。

こんど時間ができたら destructuring-bind でも見直すかな。でもこれは何の効果もなさそうだな。

O(n^2) を甘くみると…

これまで regex-byte-exec のコンパイルに90秒！ほどかかっていて、
まぁ、1100行近くあるからしょうがないかなぁ〜
と、思っていたのは大きな間違いでした。

時間を計ってみるとやはり RA-LS で時間が掛かっている。
ここまでは予測通りだかで、liveness analysis にも時間が掛かっている。

RA-LS の本体はともかく liveness analysis に時間が掛かるのはおかしいので、
よくよくソースを眺めていると、悪者は Function::EnumReg でした。

この子は Instruction を全てスキャンして virtual register を enumerate する。

これを Basic Block 毎に使っているので、O(n^2)　ここで n は bblock の個数。すなわち local liveness の計算に O(n^2) 掛かっていました。global liveness は worlist algorithm を使っているので、nに比例はするものの n^2 はいかない。(リリースビルドでも liveness 情報をダンプしていたのはご愛嬌。でもここでも20秒掛かっていた)

で、Liveness Analysis と RA-LS の Function::EnumReg を register list を作るようにしたら、なんと 2秒でコンパイルが終わりました。(`o')
(m06-loop は 1.5秒)


45倍速くなったわけです。今まで、あまりにもコンパイルが遅いので、regex の際コンパイルを避けるようにしていたのは一体… orz

Lisp のプログラムは関数が小さいので、他のファイルの場合には時間が掛かると感じなかったけど、45倍はは酷すぎる。

O(n^2)は決して無視できないことを、実体験できました。

しかし、45倍とは…

ちなみに、C4 では 0.87秒 (regex-byte-exec), 0.66秒 (m06-loop)。
もう少し見直したほうが良いか？
(かたつむり @jj 犬 g''U )

parse: 391
SSA2CFG: 125
DFA.SolveBackward: 47
BUILD 141
FIXED 16
SCAN 281
ASSIGN 15
RESOLVE 219
CLEAN 16
(RA-LS) 781
ASM 109

Delta Algorithms

* zdelta - http://cis.poly.edu/zdelta/results.shtml
* hsadelta - http://researchweb.watson.ibm.com/journal/rd/501/agarwal.html
* rsync
** Adler-32 then MD4

IME Reconversion

何か眠いので、コンテキストメニューを実装しようかなと、Notepad を見たら、
"Reconvert"とあったので、づっと手を付けていなかった再変換を実装して見ることにした。

MSDNを見たけど呼び出し方がよくわからない。ぐぐったらWZ Editor のTX-C(C言語)で実装した例があったので、それをみて推測して後はデバッガで止めて、値を調べて動くようにした。

他で使いたくなったときのためのメモ。

再変換のステップは、
1　変換したい部分を選択
2 Ctrl+, で Reconvert コマンドを起動。
3 再変換用のバッファの大きさを計算
sizeof(RECONVERTSTRING) + ((lEnd + lStart) + 1) * sizeof(char16)
+1 は NUL 用。MSDNには書かれていないが一応念のため。
たぶん、与える文字列には制限があるだろう。
Newline を含む場合は、Newlineの前までしか再変換の対象にならない。
4 バッファを確保
5 RECONVERTSTRING.dwSize, dwVersion は明確
dwStrOffset = sizeof(RECONVERTINGSTRING)
dwStrLen = lEnd - lStart
dwCompStrOffset = 0 (byte offset)
dwCompStrLen = lEnd - lStart (# chars)
dwTargetStr* は dwCompStr*　と同じ
6 ImmSetCompositionString(hImc, SCS_QUERYRECONVERTSTRING, p, cb, null, 0)
WM_IME_STARTCOMPOSITION が送られてくる。
7 ImmSetCompositionString(hImc, SCS_QUERYRECONVERTSTRING, p, cb, null, 0)
WM_IME_COMPOSITION が送られてくる。

あとは、IME の Composition String のハンドリングで OK。

今のところ、IMR_RECONVERTSTRING ことは無し。本当に必要か？

まぁ、簡単に実装できたけど、使う機会はほとんど無いのが玉に瑕。
日本語書かないからなぁ。

このところテレビで漢字のクイズが良くやっていて、時々読めないのがあるので、
使える方と思ったけど、使えなかった。orz
「ちんじ」で「椿事」にはなったけど、再変換で「ちんじ」には戻らなかった。

Feature list の項目が増えたから良しとしましょう。

私の名前は中野です。

P.S.
全角・半角の相互変換に利用でき事にきがついた。
携帯コンテンツをさわる時には使うかも？

P.S.^2
だれた時の編集用にコンテキストメニューは便利かも。

P.S.^3
Notepad の再変換は、再変換をスタートしたときの表示おかしい。再変換前の文字列が再変換後の文字列より長いと、長い部分が表示されたままになる。まぁ、ここは米人がテストしているだろうから、気づかなかったんだろうな。えと、Vistaね。XPは再変換コマンドは持っていない。