コグノスケ

テンパズルその2

前回（2015年8月10日の日記参照）に引き続き、テンパズルを総当たりで解いてしまおう、という話です。

前回、テンパズルの総当たりで答えが見つからなかった、
1158, 1199, 1337, 3478
の4つですが、Facebookでコメントいただいた通り、自然数ではなく有理数を使ったら解けました。Wikipediaに載っていた解の個数とも一致してスッキリです。

上記の4つの解き方はこんな感じでした。

• 1158: (8 / (1 - (1 / 5)))
• 1199: (((1 / 9) + 1) * 9)
• 1199: ((1 + (1 / 9)) * 9)
• 1199: (9 * ((1 / 9) + 1))
• 1199: (9 * (1 + (1 / 9)))
• 1337: (((7 / 3) + 1) * 3)
• 1337: ((1 + (7 / 3)) * 3)
• 1337: (3 * ((7 / 3) + 1))
• 1337: (3 * (1 + (7 / 3)))
• 3478: ((3 - (7 / 4)) * 8)
• 3478: (8 * (3 - (7 / 4)))

いずれも難しいです。特に3478は8 * 7 / 4 = 14を思いつける気がしません…。

ちなみに総当たり回数というか問題空間は3200000通りで、解が36384通り（演算子の適用順序、数字の順序の重複全て含む）でした。

他の桁数も見てみたところ、

• 2桁、加減乗除: 400通り、解11通り
• 3桁、加減乗除: 32000通り、解534通り
• 4桁、加減乗除: 3200000通り、解36384通り
• 5桁、加減乗除: 358400000通り、解2851411通り

問題空間は100^Nくらいで増えるようなので、6桁以降は何かの枝狩りを入れないと、総当たりでは解けないと思います。

あまり効率の良くないプログラムなので参考程度の情報ですが、5桁の総当たりに106分かかりました（CPUはIntel Atom D2700/2.13GHzを使用）。

メモ: 技術系の話はFacebookから転記しておくことにした。

netcat traditional版とnetcat OpenBSD版

ネットワークを経由した送受信を実現するのに便利なnetcatというツールがあります。わざわざソケットプログラムなどを書かなくても、単純な送受信が実現できる優れものです。

利用イメージは、Aというマシンで、produce_something | ncとしてnetcatでネットワークに送信し、Bというマシンでnc | consume_somethingとしてnetcatでネットワークから受信します。まるでネットワーク越しにパイプを繋ぐかのような感覚で利用できます（ncはnetcatのコマンド名）。

さてこのnetcatですがDebian Jessieで利用可能なnetcatは下記の2種類があります。

netcat traditional版（パッケージ名netcat-traditional）

Hobbitさんが書いたオリジナルのnetcatです。コマンド名はnc.traditionalです。

netcat OpenBSD版（パッケージ名netcat-openbsd）

OpenBSDのナイスガイ達が書き直して、機能追加したnetcatです。コマンド名はnc.openbsdです。

結論を先に書くと、特に理由が無ければnetcat OpenBSD版をオススメします。こちらの方が新しくて、多機能です。変な動きもしません。

netcat traditionalの変な動き

何が「変な動き」かというと、下記のようなごく普通の使い方でもnetcat traditionalは必ず終端でハングアップしてしまいます。

----- 送信側host1
nc.traditional host2 55555
（Ctrl+Dを押してEOFを送る）
（終了しない。。。）

----- 受信側host2
nc.traditional -l -p 5555
（終了しない。。。）

どうも入力に来たEOFの扱いが上手くない？ようで、EOFを受けるとCtrl+Cなどでkillしない限り、ずっと止まったままになってしまいます。この挙動を防ぐには -qというオプションでEOFが来たときの挙動を指定する必要があります。

----- 送信側host1
nc.traditional -q 0 host2 55555
（Ctrl+Dを押してEOFを送る）
（終了する）

----- 受信側host2
nc.traditional -q 0 -l -p 5555
（送信側が終了したタイミングで終了する）

これで万事解決に見えますが、残念なことにnetcat tradtionalは標準入力から入力待ちするため、受信側をバックグラウンドに送ると入力待ちで停まってしまいます。

----- 送信側host1
while : ; do \
	cat /lib/x86_64-linux-gnu/libc-2.19.so | \
		nc.traditional -q 0 host2 5555 ; \
	sleep 1 ; \
done


----- 受信側host2
（準備）
rm pipe recv_file
mkfifo pipe
cat pipe > recv_file

cat > recv.sh << EOS
#!/bin/sh

while : ; do \
	nc.traditional -q 0 -l -p 5555 > pipe ; \
	sleep 1 ; \
done
EOS
chmod 755 recv.sh

（端末その1）
./recv.sh &
（Enterキーを押し続けると…）
[1]+  停止                  ./recv.sh★★★★止まってしまう★★★★

（端末その2）
while : ; do \
	cat pipe > recv_file ; \
	sleep 1 ; \
done

私の知る限りnetcat traditionalでこの問題を解決する方法はありません（たぶん）。代わりにnetcat OpenBSDを使って解決します。

なんとnetcat OpenBSDには -dオプションという標準入力を開かないように指定するそのものズバリのオプションがあるのです。

----- 送信側host1
さっきと同じなので省略

----- 受信側host2
（準備）
cat > recv.sh << EOS
#!/bin/sh

while : ; do \
	nc.openbsd -d -l -p 5555 > pipe ; \ ★★★★nc.traditionalをnc.openbsdに変え、-dオプション追加★★★★
	sleep 1 ; \
done
EOS
chmod 755 recv.sh

（端末その1）
./recv.sh &
（Enterキーを押し続けても止まらない）

（端末その2）
さっきと同じなので省略

これでバックグラウンドに送ったnetcatが突然停止することはないはずです。

まとめ

以上の話をまとめると、

• netcat traditionalを使うときは -qオプションを使ってEOFで止まらないようにしよう
• netcat traditionalはバックグラウンドでの利用に適していないと思われる
• バックグラウンドでnetcatを使うときは、netcat OpenBSDと -dオプションを使おう

結論をもう一度書いておくと「特に理由がないならnetcat.openbsdがオススメだよ！」ってことです。