どさにっき（アナログ）～2010年9月中旬～

by やまや

<< = >>

2010年9月11日(土)

■ All Expressions

_ ひさびさにあなごる。最近のではなく、 3年半も前の問題。「指定された数の並びに +,-,* とカッコをてきとーに挿入して得られるすべての組み合わせの式を計算せよ」。たとえば、1, 9, 13 が与えられた場合は、(1+(9+13)), (1-(9+13)), (1*(9+13)), (1+(9-13)), ... を計算する。

_ どうやって解くか考える。まず、カッコがうざい。ので、とっぱらう。ということは、逆ポーランド記法に変換すればよい。つまり、1 + 9 → 1 9 + に変換。RPN で表記しても数字の並びは変わらず、演算子の位置が変わるだけ。しかもカッコは消える。とゆーことで、n 個の数値に対して n-1 個の演算子をてきとーに散りばめた式を作って、あとは外部コマンドに丸投げしてやればよい。

_ という方針は見えるのだが、これがなかなか一筋縄ではいかない。いいかげんなアルゴリズムだとパターンを網羅しきれなかったり、不正なパターンを作ってしまったり、同じパターンを何度も重複して作ってマシンのリソースが枯渇したりする。結局のところ、地道に二分木を構築するハメに。

_ ということで、bash の解。てきとーにインデント+コメント付加してある。それでもなお読みにくいのは golf 向けだから。
read a
set $a
# 以下計算式を作る
# 数値(_)、演算子(:)で抽象化
s=_p				# p は /usr/bin/dc の出力コマンド
for i in `seq $[$#-1]`;{	# _ -> __: -> __:_: ___:: -> ...
    t=
    for j in `seq $i`;{
        p=`sed s/_/__:/$j<<<"$s"`
        t+="$p
"
    }
    s=$t
}
for i in $a;{ s=`sed s/_/$i@/<<<"$s"`;}		# _ を入力された数値に置き換え
s=`sort -u<<<"$s"`				# タイムアウト対策(この行がなくても時間がかかるだけで結果は変わらない)
eval echo ${s//:/{+,-,\*\}}|tr @ \ |dc|sort -un # : を演算子に置き替えて計算
がんばればまだまだ縮みそうな気もするが、とりあえず動くものができた時点で力尽きた。

_ よく似た問題の Expression。 All ...との違いは、演算子の種類がひとつしかないこと。こいつはまったく別のアプローチで解ける。a-(b-c) = a-b+c なので、式の2番目以降の - を {-,+} に変えたパターンを作ることで中間記法のままカッコをはずせる。
eval echo `sed 's/ /-/;s/ /{-,+}/g'`|xargs -n1|bc|sort -un
_ ここのところ週末はずっと山で遊んでばっかりだったけど、久しぶりに遊びに行かずに頭脳遊戯で1日潰したな。

2010年9月12日(日)

■ 無題

_ この前の台風以降だいぶ涼しくなったね。昼間はまだ暑いけどさ、そんなのエアコンの効いた部屋に逃げればいいんだから何とでもなる。朝の7時に暑さで目が覚めるなんてバカげたことがなくなったというのがありがたい。

_ そんなわけで、今週は週末避暑はなし。来週以降も涼しいところに逃避しなくて大丈夫かな。来週は避暑ではないお出かけをするけど。

_ ところで、きのうから冷凍庫がぜんぜん冷えないっつーか、氷が冷凍庫の中で融けはじめちゃってるんだけどどうなってんの。

■ All Expressions

_ きのうのつづき。ここまで縮んだ。183バイト。
set `m4`
s=_p
for i in `seq $[$#-1]`;{
t=
for j in `seq $i`;{ t+=`sed s/_/__:/$j<<<"$s"`"
";}
s=$t
}
for i;{ s=`sed s/_/Ii$i/<<<"$s"|sort -u`;}
eval echo ${s//:/{+,-,\*\}}|dc|sort -un
for ループの内側がなんとかなりそうな気もしないでもないが、2時間にらめっこしてまったく思いつかなかったのであきらめた。むしろ今の路線で進むより、まったく別方向から式を組み立てる方法を考えた方がよさそうな気がする。とはいえ、入力の数値が6個になると列挙すべきパターンは1万を越えるわけで、それを短時間で列挙して計算するなんて問題の別解がそうそう簡単に見つかるとも思えんが。

_ 上のスクリプトで使っている sh の小技。といっても、ほとんど bash 限定。
set ...
引数を空白で区切って $1, $2, ... に代入する。golf じゃなくても、bash じゃなくてもよく使う。引数の先頭がハイフンだったり、あるいは引数がなかったりするとまったく別の挙動になるので、その可能性がある場合は set -- ... としましょう。
$[...]
算術演算。man に載ってないので、よいこは使っちゃいけません(古いバージョンの man には「将来のバージョンではなくす」とあったような記憶があるが、探しても見つからないので勘違いかも)。POSIX sh の $((...)) が bash でも使えるのでそちらを使いましょう。ちなみに $[] も $(()) も整数しか扱えない。
t+=...
文字列付加。たいていの言語では a=12; a+=34 を実行すると a=46 になるが、bash では文字列をくっつけるだけなので、a=1234 になる。誰だこんなクソ構文を考えたアホは。bash 以外では使えないし、bash でも golf 以外では使わなくていい。ふつーに足し算をしたい場合は a=$(($a+34)) とする。
<<<
ヒアストリング。bash の比較的最近のバージョンでしか使えないので、よいこは ...<<<hoge ではなく echo hoge | ... と書きましょう。上の += もそうだけど、これまで困難だったことが bash 拡張によってひじょーに簡単に書けるというのならともかく、これまでもひじょーに簡単に書けていたものなんだから使わずに済ませましょう。
for i;{ ...;}
for i in "$@"; do ... done と同義。bash 以外でもこう書けるけど、わかりづらいのでよいこはふつーに for i in "$@"; do ... done と書きましょう。ちなみに for ではなく while ループでは { ...;} は不可で、do ... done でないとダメ。
${s//x/y}
$s に含まれる文字列 x をすべて y に置換する。${s/x/y} だと置換は最初の1回だけ。bash でしか使えないので、よいこはふつーに sed を使いましょう。
{a,b,c}
a b c に展開する。{a,b}{x,y} なら ax ay bx by に展開される。POSIX sh では使えないのでスクリプト内で使うのはおすすめしないけど、コマンドラインでは便利なので使いたおしてやりましょう。diff -u filename{.bak,} とか、ls {,/usr{,/local},/opt/*}/bin/ とか。

2010年9月13日(月)

■ ある本屋

_ 深夜プラス1廃業とな。以前市ヶ谷に住んでたので近所だったけど、あそこで本を買った記憶はない。ミステリ専門店だと聞いていたのに、いざ行ってみたらミステリ以外もいっぱい置いてあってがっかりしたのが第一印象なぐらいなので、思い入れはない。飯田橋のあのあたりには大きな本屋もいくつかあったし。

_ 狭い店内に早川のポケミスがどどーんと棚いっぱいに収められてたり、ゴルゴ13が全巻揃いで置いてあったり、たしかに品揃えは特徴的だった。でも、そういう珍妙な棚がエアコンの吹き出し口のすぐ下にあって、空気の流れが直接ぶつかるから背表紙の汚れも目立ってた。売れずにずっと棚に残ってるのが丸わかりだったし、そういう汚れやすい陳列のしかたをしてることに反感を覚えた。
よく〈差別化〉といわれるが、それをしてはいけないということが、今回分かった。
特徴的な品揃えではあったけど、「あの規模の書店としては」充実してたというだけで、大規模店と比較しても勝てると感じるほどマニアックな品揃えだとは思わなかった。中途半端な印象しかない。ビレバンとか恵文社とかのレベルまでぶっとんだ差別化をしろとは言わないけど、遠方から電車賃をかけてまで来たくなるような要素がまるでなかった。あれじゃ潰れても当然だと思う。

_ amazon でモノを買っても本は買わず、毎日のように本屋に通っていろいろ物色してる身には、リアル書店が絶滅されるのは困る(神保町勤めバンザイ)。が、本屋に通うのは欲しい本があるからではなく、自分の知らないおもしろそうな本に出会うためなので(買うものがはじめから決まってるのなら amazon でポチればいい)、品揃えの貧弱な店は amazon よりも価値がない。小規模書店の生き残りに差別化は必要だろう。深夜プラス1は不要な差別化をしたのではなく、差別化の方向を誤っただけだと思う。

■ 無題

_ きょうの All Expressions。169バイトになりました。さすがにこれ以上は無理だろう。
set `m4`
s=_p
for i in `seq $[$#-1]`;{
s=$(eval `seq -f'sed s/_/__:/%g<<<"$s";' $i`)
}
for i;{ s=`sed s/_/Ii$i/<<<"$s"|sort -u`;}
eval echo ${s//:/{+,-,\*\}}|dc|sort -un
きのうとの違いは、力技で for ループを seq で置き替えてしまったところ。以前別の問題で使ったことを思いだした。よいこはぜったいにマネしちゃいけません。

2010年9月15日(水)

■ 無題

_ 前の会社の先輩に子供が産まれたとのことでお祝いの飲み会。…のはずが、パパ歴1ヶ月の新米パパから25年のベテランパパまでよってたかってこっちにプレッシャーをかけてきて、あげくのはてに主賓の新米パパが金を出してるのに独身のこっちは支払いを免除される罠。ちくしょーくたばれ親バカども。

2010年9月18日(土)

■ SKK

_ Emacs その他で動く変態的な日本語入力ツール SKK。その名前の由来は Simple Kana to Kanji conversion program だとか SKK = Iだとか言われているが、もうひとつ別の "SKK" がある。

_ これ。

この建物は東北大学電気通信研究所附属21世紀情報通信研究開発センター…らしいけど、たぶん誰もそう呼んでないと思う。みんな SKK 棟と呼んでるはず。わしがここの学生だったときは正式名称は今とは別の名前だったけど、でもやっぱりそれとは無関係に SKK 棟と呼んでいた。この SKK はナニモノかというと、東北大工学部の母体となった仙台高等工業学校略して SKK の旧校舎。古い建物が多く残る片平地区ではそこそこ新しい昭和初期の建築らしい(明治、大正時代の建物もたくさん残ってる)。

_ この SKK 棟と日本語入力の SKK がどう関係するのか。SKK を開発したのは、当時東北大電気通信研究所にいた佐藤雅彦教授(現京大)。ということで、もう1枚写真。

左が SKK 棟、右は通研2号館で、ここの3階に佐藤研究室があった。徒歩10秒。まさに目と鼻の先。そんなわけで、通研の住人にとって SKK といえばレトロな建物を指すし、その住人のひとりだった佐藤先生にとってもそれは例外ではないはず。Simple Kana Kanji だとか SKK=I だとか名前の由来はいくつかあるだろうけど、たぶん間違いなく SKK 棟のことも念頭にあって、それらをひっくるめてこの名前になったんだと思う。

_ SKK の辞書は昔も今もユーザから提供を受けた単語をもとに編集されているけど、開発初期のユーザが少なかった時期は東北大の学内からの提供だけにほとんど限られていたらしい。そのころのことは伝聞で知るだけだけど、学術用語や仙台・東北大ローカルの地名、固有名詞が異様に充実していたことで当時の雰囲気を知ることができた。わしが SKK を使うようになったのも、この偏った辞書の恩恵を最大限に受けられるこの大学に通っていて、日常生活から論文に至るまでひじょーに高い効率で変換できたからでもある。多くの人が使うようになった今では他の単語も増え、またローカルすぎるものは残念ながらかなり削除されたようだ。以前は
そねけんぼうおんしつ /曽根研防音室/
こんなのが実際に辞書に収録されて配布されてたんだけど、曽根研究室の人以外誰も使うはずないわな(関係者だったのでありがたく使ったが)。

■ 無題

_ そんなわけで、仙台に来ました。もう離れる途中だけど。観光客ならば牛タンを食うとこだけど、別に観光客ではないので、すっげーひさしぶりに北京餃子で広東焼きソバを食った。記憶にあるよりもずいぶん店内が明るくきれいになっちゃってるんだけどどういうこと？まあ、たったあの程度きれいになったぐらいでは、おしゃれなファッションビルの中の異次元空間であることにはまったく変わらないんだが。

2010年9月19日(日)

■ 夏休み

_ 夏休みです。もう9月も半ば、お彼岸もすぐそこまで迫ってるけれど、夏休みなのです。夏の間にさんざん遊びまくった気がしなくもないけど、ふつーに土日に遊んでいただけで5月の連休以来はじめてまとまった休みを取るんだから誰が何と言おうと夏休みなのです。

_ そんなわけで、北海道。きのうの夜、仙台港をフェリーで出港して、今朝11時に苫小牧着。朝起きたらいきなり雨まじりの曇り空でいきなりテンションを下げられつつも、午後から晴れるという予報を信じて行動開始。当初は室蘭とか登別とかの方向に行こうかと思ってたんだけど、そっちの方向は雲が厚いので躊躇。遠く北の空にわずかに青い色が見えたのを頼りにいきなり予定を変更して北へ。

_ ちうことで、R36 → R231 → R232 と北上。午後になって晴れてきたよよかったよ。夕日を浴びる日本海すばらしい。やっぱり北海道は走ってて気持ちいいね。何もない。何もないのがいい。どこまでいっても変わりばえのない景色。もうこんなの飽きたと思うぐらいこのまま変わらないでほしい。

_ 今は苫前の港のそば。すぐそばに道の駅があるけど、そっちは車がいっぱいなので、広いのに誰も使ってない駐車場。天売島、焼尻島のそばに太陽を沈むのをぼけーっと眺めてた。明日はまだ遠くにうっすらと見えるだけの利尻富士を目指してさらに北上の予定(利尻島まで渡るつもりはとりあえずないけど)。

2010年9月20日(月) 敬老の日

■ 北の果て

_ オロロンラインと呼ぶらしい R232 → r106 を北上。何もない。カーナビの画面の真ん中をまっすぐ縦に自分の通る道が貫き、その左が海、右が陸。何 km 走っても縮尺を変更しても画面が変化しない。牧草地があったり、風力発電所があったり、人の手が加わってるところもないではないが、ほとんど未開発の原野。当初は人家や港もあるんだろと思ってたが、なかった。「なにもない」があった。

_ 寄り道してサロベツ原野。使い古した表現に「360°の大パノラマ」ってのがあるけど、ふつーはどっかの山のてっぺんからの風景を形容する言葉だよね。まさか標高10mにも満たないところでその言葉が出てくるとは思わなかった。見渡すかぎり、原野。どの方角を向いても、原野。原野の向こうは地平線だったり、利尻富士だったりするけど、原野。

_ ノシャップ岬に、最北端宗谷岬。うん、北にあるというだけで、どこにでもある岬だな:-)。ウニ丼うまかった。ちょうどガソリンがなくなったので、宗谷岬のスタンドで給油して、最北端給油の証明書ゲット:-)。

_ で、宗谷は岬よりもちょっと内陸に入った宗谷丘陵がすごい。こんな風景が日本にあるとは思わなかった。日本語は通じないけど(人がいないので)。氷河期の地形がそのまま残ってるらしい。多くの部分は牧場になって自然のままではなく牧草地だけど、そのぶん、手つかずの谷とのコントラストがはっきりしていて美しい。なのに、宗谷岬にあれだけいた観光客がまったく見当たらない。

_ オホーツク海沿いを走って、枝幸の道の駅まで。ここで車中泊のつもりだったけど、すぐとなりにキャンプ場があるのでそっちに移動。キャンプ場だし、自炊セット持参なので、晩ご飯は海を見ながらジンギスカン。

_ というわけで、おなかいっぱいになったのでもう寝ます。おやすみなさい。

_ r106 オロロンラインと北緯45°モニュメントと利尻島。わしの車が邪魔だ。

サロベツ原野とパンケ沼と利尻富士。

宗谷丘陵。海の向こうに見えてるのは、樺太。

猿払村道エサヌカ線。地平線までまっっっすぐ。

<< = >>