Make 10

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

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

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

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

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

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

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

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

Enjoy!

解をもたないもの:
1111
1112
1113
1122
1159
1169
1177
1178
1179
1188
1399
1444
1499
1666
1667
1677
1699
1777
2257
3444
3669
3779
3999
4444
4459
4477
4558
4899
4999
5668
5788
5799
5899
6666
6667
6677
6777
6778
6888
6899
6999
7777
7788
7789
7799
7888
7999
8899

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は再変換コマンドは持っていない。