トップ «前の日記(2009-11-07) 最新 次の日記(2009-11-10)» 編集

はじめてのにき

ここの位置付け

2004|11|
2005|03|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|07|08|09|10|11|12|
2010|01|02|03|04|05|06|07|08|09|10|11|12|
2011|01|02|03|04|05|06|07|08|09|10|11|12|
2012|01|02|03|04|05|06|07|08|09|10|11|12|
2013|01|02|03|04|05|06|07|08|09|10|11|12|
2014|01|02|03|04|05|06|07|08|09|10|11|12|
2015|01|02|03|04|05|06|07|08|09|10|11|12|
2016|01|02|03|04|05|06|07|08|09|10|11|12|
2017|01|02|03|04|05|06|07|08|09|10|11|12|
2018|01|02|03|04|05|06|07|08|09|10|11|12|
2019|01|02|03|04|05|06|07|08|09|10|11|12|
2020|01|02|03|04|05|06|07|08|09|10|11|12|
2021|01|02|03|04|05|06|07|08|09|10|11|12|
2022|01|

ToDo:


2009-11-08

_ Cプリプロセッサ

http://d.hatena.ne.jp/qnighy/20091107/1257587259

高校1年でこれかーすごいなぁ。

(10:08)

_ 四色問題

http://twitter.com/alohakun/status/5506693038

これで思い出して前に啓蒙書を貸してもらって読んだけど、証明をさっぱり忘れつつあるので記憶を再構成しておこうと思う。うぃっきぺたんを参考にしつつ俺メモ…

http://en.wikipedia.org/wiki/Four_color_theorem

まず一つの点から4本以上線がのびるような頂点があるグラフは考えなくてもいい。

×

があったら

v
|
^

に変換しちゃえば3本のびるグラフに還元できるから。

2本しかのびてない頂点はつまり、単純に領域数増やしに関わってのは無視できて、孤立した円みたいなヤツも自明に関係なくて、全体を囲むやつとかも外っかわの色のせいで4色じゃ塗れなくなっているとすると、中もどうせ4色で塗れませんよね〜ということで忘れていい。でまぁこのケース忘れることから、隣国が1つしか無い国っていうのもいないとしていい。

次はオイラーの多面体公式

http://ja.wikipedia.org/wiki/%E5%A4%9A%E9%9D%A2%E4%BD%93

頂点の数(V) - 辺の数(E) + 面の数(F) = 2

を使う。なんかしらんけど色をぬる領域が頂点として、隣国との国境が辺、でまぁ地図上の頂点が面として考えている。ややこしいな…

3本線が生えてる頂点しか無いことから、 2E = 3F 。 6V - 6E + 6F = 12 につっこむと、

6V - 2E = 12

頂点から出てる線の数を i とした時に、そういう頂点の数を vi とすると、

6Σvi - Σi*vi = Σ(6-i)*vi = 12

ということは i<6 のものが最低一個無いと左辺が正にならないので、最低一つは隣国の数が5以下の国があるわけだ。そこを攻める。

攻める前に、背理法の準備。ここに4色で塗れない地図があったとして、その中で最小の国数となる地図 G を考える。つまり G から国を 1 つ取り除いたら4色で塗れるようになってしまうようなもの。

さて G は隣国2つしかない国を持てない。その隣国2つの国を取り除いて隣国同士をくっつけた地図も依然として4色で塗ることは不可能で、 G が最小という仮定を壊す。

G は隣国3つしか無い国も持てない。これも隣国3つを取り除いて頂点にしちゃった地図も依然として4色彩色不可能だから。

隣国4つもちょっと賢い理由で無理。隣国4つがそれぞれ全部違う色でかつ自分の色とも違ったとして、赤青黄緑の順でぐるりとまわっているのが隣国で自分が紫とかする。赤の国から出発して、黄→赤→黄→赤→…と交互にたどっていけるパスがあるはず。無いなら黄は赤でいいことになってしまう(はしょりすぎだが)。同じ理由で青と緑を交互にたどるパスもある。さてそれらはどうやって交差してるのでしょうかー無理ー。ということで隣国4つも無理。

5色定理はこの論法で隣国5つのケースも潰せるので、証明できる。ここまではそんなにむつかしくないというか、とても綺麗な論法だったわけだ。

で、5つがむずい。というかその、「隣国5つの国が1つはいるよね〜」という条件だけからではどう考えても矛盾が導けなかったので、「隣国 X の国の回りに隣国 Y の国があるようなパターンか、ほげほげなパターンか、あるいはふがふがなパターンか…のどれかは絶対あるよね〜」とかそんな感じで、パターンをどんどん増やしていって、一個一個潰していく感じでやっていった。でまぁ証明難しげなパターンがあったらそのパターンの中でまたパターン増やして…みたいなことをやって、片っ端からこんぴゅーた様で証明した、っていうような感じだったらしい。

でまぁそいうパターンが証明時で2000近くとかあったんだから、泥臭いことこの上ないという。

最後の部分なんかわかりやすいパターンの例とか本に載ってた気がする。今度立ち読みして再構成しよう…

(10:09)

_ スタック巻戻し…

TODO

  • ゴルフ場の続き
  • Snow leopard で sevil/w3mimg
  • Snow leopard で SDL
  • るびま
  • メガデモ
  • chrome linux の omnibox のコピー(よくわからんがめんどくさそうだ…)
  • GCC とたわむれる
  • syard とたわむれる
  • syard の script.js をちょっと書き直す
  • blokus (オワタ)
  • テトリス
  • TCC は -run をあと少しリファクタリングして push
  • TCC x86-64 asm が出たら見てみる
  • w3m であそぶ
  • chrome key でコピーができると良い
  • chrome key は chrome 側の変更が必要 http://shinh.skr.jp/m/?date=20090823#p01
  • kevil がなんかおかしい件
  • 定額給付金をくれと電話する
  • ベッドについて思いをはせる
  • bfx は忘れてた
  • ada は忘れてた
  • grub コード整理

(16:38)

_ chrome key でコピー

をやろうとしたけどうまくいかんな…

とりあえず background.html にフラッシュ置いたら SEGV した :( まぁ置けないのはいいのかもしれんが SEGV はどうなんだと思ったので 報告するか今度眺めておこうと思う。

次に content script 側でページにフラッシュを つっこむ実装にしてみようとやってみた。 でもどうもうまくいかない。 なんでだろ。

(16:42)

_ Shibuya.lisp

おもしろかった。

  • 行ったら UtiLisp の話をしていた
  • hcons ってなんか聞いたことあったけどそいうものだったんだなあ
  • 24bit address space 楽しそうだなぁ
  • 現行の機械だけにあわせてなんか作るとか楽しそうだなぁ
  • でも発表者は今はポータブルにした方がいいよねと言ってたそうですね…
  • 当然タグポインタ
    • 80 binary cell, atom
    • 90-F0 unused
    • --- signedness ---
    • 00 ret etc.
    • 10 24bit integer
    • 18 floating
    • 20 1 dim array
    • 30 elem array
    • 40 string
    • 50 io stream
    • 60 native function
    • 70 atom
  • 大型命令って今ではむしろ…
  • optional parameter の実現が面白い。引数の数に応じて call するアドレスを変えることによって引数が少ない時のチェックは消すらしい
  • どんな関数でも引数6つぶんくらいのエントリポイントを作って引数がそれ以上だった時のエントリポイントも用意すれば最大チェックも消せるかなぁ、でも引数個数が少ない関数でのオーバヘッドとか大きいかなぁとか妄想した
  • あとキーワード引数で似たようなことやれそうだなぁとか妄想した
  • Mosh は JIT で速くなりましたかーとか聞いた。 30% とかそのへんの数字らしい。やっぱそんなもんかー。
  • 次は竹内先生の昔話
  • くだらないシャレになってる命名はいいなぁ。 LIPQ とか USO 800 とか
  • プロシンで見たカレンダーがパワーアップしてた
  • なんかメモしてなかったからあんまり印象に残ってることがないな…
  • あと LT
  • github.com/mokehehe/bulletsml
  • メル尺度

BulletSML を聞いていて、 何か jsdmkun 作ってる時にコンパイルするアプローチだと アレが難しいよなーと思っていた、アレは何だっただろう… とひたすら思い出していたけど思い出せなかった。 その後一瞬で思い出したんだが単に継続だ。 BulletSML では普通に継続使ってるから問題ないのであった。

(17:20)

_ chromiumExtensionDevCon

んで Shibuya.lisp 終わってから行ったら遅れてた。

というかそもそも今思い出したけど Shibuya.lisp 自体存在をきっちり忘れていて、 というか登録した記憶がきっちり無くて、 masa_edw さんの twitter を見て 「あー今日 Shibuya.lisp かー俺も行きたかったなぁ」 と思ってサイト見たら何か登録されていて 焦って飛んでいったとかいうそんなこんな。

で chrome の方はまぁなんかみんなよく知ってるなぁとかそんなこんな。 extension はやっぱこうまだ API 全然足りないよなぁ。

(17:29)

_ w3mcooksrv

はまぁ悪くはなかったんだけど、 コードが無闇に長いしもう毎回クッキー読み書きする実装でいいんじゃね? と当たり前のことを思ったのでそいう実装を作ってみた。

http://github.com/shinh/w3m/commit/abcedbb2d7222f97157221cf52b00b3b600c6431

これでしばらく使ってみて良さげなら w3mcooksrv はもう捨てよう。

(20:03)

_ こぴー

なんだ JS だけでできるんじゃないか… Linux でもすごくよく動いてるので、 もう chrome linux の omnibox とか忘れていい。

TODO がちまちまと消えていってうれしい

(22:25)

お名前:
E-mail:
コメント:
人生、宇宙、すべての答え
本日のリンク元

2009年
11月
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30
1.shinh(2014-05-24 02:05) 2.shinh(2014-05-24 02:05) 3.かめぞう(2014-05-24 02:05)
search / home / index

全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。

shinichiro.hamaji _at_ gmail.com / shinichiro.h