2010年を振り返る

人生

おおざっぱに言うと、4〜5月に仕事が詰め詰めになって、そのあおりで中期的目論見がいろいろ崩壊してしまったという1年だった。ううむ駄目だ…。
最近ようやく立て直せてきた感があるので、自分がやりたいと思っている方面へ能力を伸ばしていく活動を進めていきましょう。

月別に

  • 1月
  • 2月
    • 社員食堂の夜営業が無くなって食生活悪化
    • 海部川風流マラソンに参加。4回目のフルマラソン。へろへろ。また爪が剥がれてこれ以来走ってない
  • 3月
    • プロジェクトに自動テストフレームワークが導入される。それまでは無かったので既存コードにテスト可能な設計の部分が少なくて後悔。最初からやっておくべきだったと全力で思う
    • あまりにも○○が××だったので△△する（自主規制）
  • 4月
    • フレックスタイムが無くなって毎日9時に出勤しないといけなくなる
    • セキュリティスペシャリスト試験を受けた→合格
    • 体調が変になる→病院で検査したが異常なし→6月くらいに仕事が落ち着いてきたら治まった
    • 新聞を取るのをやめた
  • 5月
  • 6月
    • 5月の反動で大量に休みを取る
    • Google Code Jamで敗北
    • ICFPC。とても面白かった。有給休暇使うべきだった
  • 7月
    • PRML読書会とUTPCで東京に行く
    • レッドコーダーになれた
    • ○○について考えるなど（自主規制）
  • 8月
    • TopCoder Openでちょっと惜しいところまで行く
    • 北陸方面へ鈍行旅行
  • 9月
    • お昼休みを知らせるチャイムを製作
    • コンテスト系で使う言語をJavaからC++に切り替え（SRMだけはまだJavaのまま）
  • 10月
  • 11月
    • F#を覚え始める
    • NetAgent Security Contest 2010に参加
    • jubeatをやり始める
  • 12月
    • 初めて仕事で出張

そのほか

  • Emacsをちょっとずつ覚えていっている
  • 技術書以外の本をほとんど読まなかった。あまり良くない
  • 飲み会のとき以外でも飲酒する習慣ができた
  • 休日に自宅以外で読書や作業するときタリーズをよく使うようになった
  • 白髪がめっちゃ増えた

Twitterから印象に残ったものを

「顧客がほしいのはきれいなコードではない」というのは大事な考え方なんだけど、「いいコード書くためにいろいろ勉強するのとか面倒くさ」と思ってるだけの人が免罪符にすることもあるので気をつけないといけない、かもしれない

http://twitter.com/#!/tomerun/status/9773602433

過去の自分の言葉に励まされる日々。BlogやTwitterがあって良かったと思う。そして将来の自分のために今日も思考を書き残す

http://twitter.com/#!/tomerun/status/10380043304

まともな場所かどうかは「いい仕事をしよう」と思う方が幸せかそんなこと思わない方が幸せかで簡単に判別できるのではないか

http://twitter.com/#!/tomerun/status/10731313778

仕事ちうのは単にパソコンの前に座ってプログラムを打ったりバグレポートの返事を書いたりすることではなくて、その作業がどんな意義を生み出していくかのストーリー、で、関わっている人らがそれをどれだけ語れるかというのは重要とても重要

http://twitter.com/#!/tomerun/status/12890036200

どうもあれができないこれができないと不安に思ってしまいがちで良くない。どこまでいってもできないことというのは無くならないのだから何ができるかを広げていくように意識を向けるべし

http://twitter.com/#!/tomerun/status/16237332424

意義や意図が不明な規則は守られなくてそこが割れ窓となって関係ないところまで破滅していくのでそんな規則最初から無い方がいい

http://twitter.com/#!/tomerun/status/19250166414

なんというか「マジメに仕事すること」自体が目的になってはいかんよなあ、などと

http://twitter.com/#!/tomerun/status/19253186532

職場でしか新しい人と知り合いになることがないというのはあまりよろしくない状況だと思うけども、地方在住であまりアクティブでもない自分がなんとかそうならないでいられてるのはTwitterのおかげであって大変ありがたいことだ

http://twitter.com/#!/tomerun/status/27045286784

F#学習用リソースいろいろ

F#

この記事は F# Advent Calendar jp 2010に参加しています。

最近ちょうどF#を覚え始めたところでして、同じような方も多いと思いますので、F#の学習に使えるいろいろを紹介します。

プログラミングF#

プログラミングF#

プログラミングF#

定番でしょうか。ぼちぼち読み進めています。
書籍で学習しようと思ったら、とりあえずこれを選んでおけば間違いはなさそうです。

F# Survival Guide

http://www.ctocorner.com/fsharp/book/default.aspx
本を買うのにお金かけたくないという方はこちらで（全編英語ですが）。

Sphere Online Judge(SPOJ)

https://www.spoj.pl/
プログラミングの問題が多数置かれています。
対応言語40種超というのはこの手のサイトでは一番多いのではないでしょうか。F#のほかにBrainf*ckやWhitespaceなどにも対応。
文法を覚えてきて何かコード書きたいけど手頃なのがない、というときの題材になります。
一番簡単な問題をF#で解いた人たち一覧：https://www.spoj.pl/ranks/TEST/lang=FS

Codeforces

http://codeforces.com/
週1回くらいの頻度でプログラミングコンテストを開催しているサイトです。
解答をF#で提出できるというのはなかなか珍しい。
素早く書く力を鍛えようと思ったらこれにF#で参加してみると良さそうです。

ideone

http://www.ideone.com/
コード共有&コンパイル&実行サービス。最近よく見かけますね。
いろいろな言語が使え、F#にも対応しています。
例：http://www.ideone.com/fyq5M

F# snippets

http://fssnip.net/
F#に特化したコード共有サービス。参考になるコードがいろいろと置かれています。
次のような特徴があります。

  • Visual Studioと同様のツールチップが出る
  • 投稿したコードごとにタイトルやタグを指定できる
  • 参考になったコードに投票できる
  • 折りたたみを指定できる
    • コードの一部だけを表示する
      • 「// [snippet:%TITLE%]」と「// [/snippet]」でコードの一部を挟むと、その部分だけが表示されます。
      • 複数使うとコードが複数個の部分に分けて表示されます（詳しくは下の例を）。
      • %TITLE%のところに書いた文字列が、その部分のキャプションになります。
      • 囲まなかった部分は表示されないので、先頭に書くopenの列挙などコード中の面白くない部分を省略するのにも使えます。
    • コードの一部を省略する
      • 「(*[omit:%COMMENT%]*)」と「(*[/omit]*)」でコードの一部を挟むと、その部分が省略されます。
      • 重要ではない実装の詳細を隠してコードの骨格を明確にするなどの目的に使えます。
      • %COMMENT%の所に書いた文字列が、省略された部分に表示されます。

折りたたみの例：次のコードが（はてな記法でF#のシンタクスハイライト未対応なんですね…）

// meaningless opens
open System
open System.Collections.Generic

// [snippet:FizzBuzz sample]
let fizzbuzz x =
    if x % 3 = 0 && x % 5 = 0 then
        (*[omit:print "fizz" ans "buzz"]*)printfn "fizzbuzz"(*[/omit]*)
    elif x % 3 = 0 then
        (*[omit:print "fizz"]*)printfn "fizz"(*[/omit]*)
    elif x % 5 = 0 then
        (*[omit:print "buzz"]*)printfn "buzz"(*[/omit]*)
    else
        (*[omit:print number]*)printfn "%d" x(*[/omit]*)

let fizzbuzz_loop n =
    List.iter fizzbuzz [1 .. n]
// [/snippet]

// [snippet:main]
fizzbuzz_loop 100;;
// [/snippet]

こうなります→http://fssnip.net/1h

NetAgent Security Contest 2010

event security

http://www.netagent-blog.jp/archives/51504789.html
参加していました。この手のイベントは初めてでバイナリ解析なぞやったことないという程度の経験なのですが、まあ楽しみつつ学びつつ。
8問あるうちの前半4問が解けました。このあたりだったらまだそこまで事前知識が無くてもその場で調べて何とかなるようなくらいで、初心者にも優しい設計でした。
ただ仕事でWindows開発やってる身としては6問目のようなのはできるようになっておきたい…。解説が来たら復習しよう。
取り組んでいたのは約15時間ですが、それだけの時間のこととは思えないくらいものすごく勉強になりました。これは学習効果高いです。

1. Activation

マシンの日付を変えるだけでOK。
拍子抜けしたけどLevel1だからこんなものか…

2. Hidden file

とりあえずZIPでWeb検索するとWikipediaにフォーマットの概略があるのを発見。
先頭4バイトが固有のシグネチャだそうなのでそれでデータファイル内を検索すると探したいZIPファイルの先頭位置が見つかった。
末尾の位置も、ZIPフォーマットの最後に付くCentralDirectoryのシグネチャで検索して見つかった。あとはそのCentralDirectory中のフィールドを見ていくと長さがわかる。
最初見たときはもっと苦労するかと思っていたのだけど、ZIPのフォーマットが意外と簡潔だったのでそこまで時間かからなかった。

3. Crypto

暗号化で整数でnとeといったらRSAでしょー。
そのままではブロックサイズがわからないので数バイトの小さなファイルで暗号化を試してみると、1バイト→4バイトで暗号化されているようだと把握。
あとは画像に示されているn、eの値から鍵を探索して（値は大きくないので全探索で大丈夫）RSAの手順通りにデコードすると答えが出てきた。


問題文にはexeやdllを解析して…と書いてあるけどそんなのいらなかったですハイ。


コード

#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

int n,e,p,q,d;

int main(){
  cin >> n >> e;
  for(int i = 3; i <= n; i+=2){
    if(n % i == 0) {
      p = i;
      q = n / i;
      break;
    }
  }
  int m = (p-1)*(q-1);
  for(d = 2; d < m; ++d) {
    if(d *e % m == 1) {
      break;
    }
  }
  fstream input;
  input.open("password", ios_base::binary|ios_base::in);
  fstream output;
  output.open("output", ios_base::binary|ios_base::out);
  while(!input.eof()){
    long long v = 0;
    for(int i = 0; i < 4; ++i){
      v += (input.get() << (i*8));
    }
    long long res = 1;
    for(int i = 0; i < d; ++i){
      res *= v;
      res %= n;
    }
    output.put(res);
  }
}

4. Character codes

メールのヘッダに "charset=utf-7" と書いてあるのでまあUTF-7なんでしょう。


デコーダを自分で書くのは面倒すぎる…。検索してみたらJavaのライブラリが出てきたので使わせてもらう。→ jutf7
で、デコードしてみようとしたら失敗してしまう。何故だ。
問題のバイト列をちゃんとUTF-7の仕様に則って検討してみると、+-の対応がおかしいし、8bit目が立っているバイトもたくさんある。
そういえば、UTF-7ではアプリケーションが8bit目を独自の情報を載っけるのに使う場合がある、というのをどこかで聞いたことがあるような…。
そこで8bit目を全部クリアしてデコードしてやるとうまくいった。


しかしまだ化けている。
デコード結果のcharの値を見てみると、Shift_JISのひらがなの領域に相当する値が多いよう。
そこで今度はShift_JISとしてデコードしてやると、見事Javaの文字列になって日本語の文章として表示できました。


コード

import java.nio.ByteBuffer;
import java.nio.CharBuffer;
import java.nio.charset.Charset;

public class Main {

  static String data = "+〓...中略...N-";

  public static void main(String[] args) throws Exception {
    Charset utf7 = Charset.forName("UTF-7");
    ByteBuffer buf = ByteBuffer.allocate(data.length());
    for (int i = 0; i < data.length(); ++i) {
      buf.put(i, (byte) (data.charAt(i) & 127));
    }
    int[] ai = new int[data.length()];
    byte[] bi = buf.array();
    for (int i = 0; i < ai.length; ++i) {
      ai[i] = (bi[i] & 255);
    }
    CharBuffer str = utf7.decode(buf);

    Charset sjis = Charset.forName("Shift_JIS");
    ByteBuffer buf2 = ByteBuffer.allocate(str.length() * 2);
    for (int i = 0; i < str.length(); ++i) {
      char c = str.get(i);
      buf2.put(i * 2, (byte) (c));
      buf2.put(i * 2 + 1, (byte) (c >> 8));
    }
    str = sjis.decode(buf2);
    System.out.println(str);
  }
}

5. Crack ZIP files

問題文にあるヒントで検索すると、Known-Plaintext Attackという脆弱性があるのを知る。
zipファイルを古い形式で暗号化している場合、中に入っているファイルのバイト列が一部わかっている場合はパスワードが破れる、と。なるほど。
http://www.woodmann.com/fravia/mike_zipattacks.htm


しかしxyz.zipの中にあるファイルの情報がわからないのでこれがわかってもどうにも…。
houkoku.zipはzipファイルなのだからシグネチャ部分の先頭4バイトはわかるけどそれだけでは無理だろうし。


一応適当にツール拾ってきてブルートフォースもかけてみたけど、さすがにそんなのでは見つからないですね。

6. UnPack EXE

.kdファイルがアセンブラ風のスクリプトになっていて、exeから読み込まれて実行されているみたい。
その中に「グローバル変数に状態を保存」というところがあるので、その書き込み先アドレスをいじってみて変なことが起きないかやってみたけどどうにもならない。


やっぱりこのレベルになるとちゃんと解析しないといけないんだなあと思いつつも、ツールや手法はよく知らないのでとりあえず手元にあるVC2010でアタッチして逆アセンブル結果を見る。
アセンブリコードからリテラルの10000を検索してみたり、ステップ実行させながら勝利数が入っていそうなメモリを探したりしたけど成果無し。挫折

7. JavaScript

ひとまずセミコロンで改行を入れて地道ーに読んでいく。
しばらく読んで触ってしていると、最初のあたりで変数$をいろいろ弄っているところは、そのあとで$のプロパティを全部出力させてやるとどういう結果になるか簡単にわかることに気づいた。
（JavaScriptは素人なのでここまでで1時間ほど…）


その結果を使って、次に何か関数を実行しているところを復号すると、変数 __ にとある文字列が入っていることと、変数 _$ にRegExpを返す関数が入っていることがわかる。
んでその正規表現を使って長ーーーーい文字列を置換して、一番最後の部分はcreateCRMFRequestという関数にその文字列を渡してある。


CRMFというのが何なのかよくわからないのだけど、実はその関数の中身はあまり関係なくて、結局パラメタに渡した長い文字列がevalされているだけみたい？
実際、そのcreateCRMFRequestを呼ばずに、自分で文字列をevalしても同じダイアログが出てくる。
ならばその長い文字列を解析すればゴールか…と思ったが長すぎて（200万文字くらいだったか）手作業ではだいぶ無理がある。
一応後ろに ";alert(Answer);" とかくっつけてevalさせてみるのもやったけどもちろんundefined。どこかの関数内のスコープで定義されてるんでしょうね。


デバッガをうまく使ったら見えるのかなぁ…といったあたりで時間終了になりました。

8. x86_64

手つかず。

Collection#contains() の引数はObject型

Java

次のようなコード

HashSet<Long> set = new HashSet<Long>();
set.add(1L);

set.contains(1); // => ?

これはfalseになる。リテラルの1はboxingがかかってもInteger型にしかならず、Long型の1とは一致しない。しかもコンパイルエラーにもならない。あやうく嵌りそうになった。
あと、add() のほうは引数にEを取るので、set.add(1) はコンパイルエラーになる。


Map#containsKey() などでも同じ。

ICFP Programming Contest 2010

contest

http://icfpcontest.org/2010/
年に一度のお祭り、今年も参加しました。1人チームです。

score: 102.991
others' cars solved: 178
cars submitted: 0

で70位くらい？　1台くらいは車を出荷したかったなぁ。次から次に現れてくる謎を解くのに夢中であっという間の週末でした。プログラミングはあまりやらなかったけれども、論理パズル好きとしてはこういう展開は面白い。
1人チームに不利な条件で、月曜に休み取ってなくてラスト20時間なにもできなかったという割には頑張った。去年は下から数えた方が早かったくらいだし。


以下時系列に

  • 18日21:00 問題を読み始める、短くていい感じ
  • 18日22:00 やることは把握したので回路の文法を推測すべく適当な文字列をサーバーに投げる
  • 18日23:00 回路の文法はけっこう単純だった。gateのtypeは常に0なのは後の拡張のため空けておかれてるのだろうか。引き続きgateの仕様を探るべく単純な回路を投げる
  • 19日01:00 gateの出力は入力のみから決まるものと仮定して推測していたら矛盾が出てきてしまった。これは内部で状態を持っているのか…！　と早くも絶望しかける
  • 19日02:00 問題文にあった"backward"なwireが何をさすのかを勘違いしてますねこれ。直接自分に戻すwireのことだけを指していると思っていたのだけど、それでは大きな回路でつじつまが合わなくなってしまう。gate番号が小さいやつに向かうwire全部のことか
  • 19日03:00 gateの真理値表が完成。サンプル回路を実行してkey prefixを得るべく回路のパーサとシミュレータを書き始める
  • 19日05:00 回路シミュレータができてkey prefix判明。きりが良くなったので寝る
  • 19日16:00 活動開始。うっかり11時間睡眠
  • 19日16:30 オウム返し回路を作ってサーバー入力の先頭17bitを得る
  • 19日18:00 とりあえず回路を組み上げるための部品を揃えようと、0を入力され続けると常に0を返す（1,2を返すバージョンも）回路とか、何を入力されても0を返す回路とか、1と2を反転させる回路とか、そんなのを作ってた
  • 19日19:30 任意の出力を生成する回路の方針が立つ。backwardなwireでは1サイクルの遅延がかかることを活かして、オウム返し回路をbackwardにN-1個つなげることで「はじめ0を出力してNサイクル目以降はiを出力する回路(i=0,1,2)」が作れる。そしてそれらをN=0〜M-1までAdder（のようなもの）で連結することでM文字の出力が作れる、という感じ。gate数が文字数の2乗オーダーになってしまうが、それを縮めるためにかけられる時間はないし、スコア的にも最小と最大ではせいぜい2倍しか違わないし、早く先に進みたいしということで、回路の小型化はしないことにした
  • 19日24:00 望みのビット列を与えたら、それを出力する回路をはき出す回路ジェネレータができた。しかし動かしてみたらバグっている…。この辺でTopCoder Openの予選のため小休止
  • 20日03:30 バグはたいしたものではなくてすぐ取れた。というわけで最初の車に対して燃料を供給できた！ 60番目くらい
  • 20日05:00 スコアボードで得点が入ったのを確認して就寝
  • 20日13:00 起床。最終的な目標を「carやfuelの仕様をそれなりに解読し、いくつかの車に対してfuelを供給する」というあたりに置く
  • 20日14:00 とりあえず、提出されているcarのビット列を見て規則を推測しようとする。似たようなcarをサイズ順に並べてみたら、明らかにビット列がインクリメントされていっている様子が見えるものの正確なフォーマットがなかなかわからない…。あと平行してサーバーの17ビット目以降の入力を推測する作業も。どうやら"2"は偶数個連続してないと怒られるみたいなので（※後でわかったことだが必ずしもそうではない）、それを手がかりに1ビットずつ
  • 20日15:30 テキトーに投げてたら2台目の車に対して「1111」というfuelが通った。どうやらtank1個の車は同じfuelでいけるみたいというのも把握。そして大量の車を前にして、上位の人たちが「提出状況管理をどうするか」みたいな話をしていた意味を知る…、まあそこにかけられる手間もないのでベタにテキストファイルに書いていた。提出するのも、ちまちまURL直打ちで。この日いったい何百回「/solve/form」をアドレスバーに入力したことだろうか。プログラマ失格ですね
  • 20日21:00 ternary streamのシンタクスは依然わからないままだが、何となく100くらいまでの数値は調べられたので、さしあたってはこれで問題なさそう。リストのサイズを表しているところとそれ以外とでフォーマットが違うみたい？
  • 20日23:30 車のフォーマットが完全に見えた。「Auxiliaryなchamberでは、上のpipeと下のpipeの間に挟まっているのは0ではなく10」というのが最後の1ピースだった
  • 20日24:00 簡単そうな車を片っ端から給油していく。手作業で。これはつらい…
  • 21日01:00 複数のingredientを使うfuelのフォーマットを見つけたかったが、"dimension mismatch"地獄にはまってしまって進展せず
  • 21日02:00 まだまだクソゲーな感じの大衆車が湧いてきていたので、解けるやつに適当に給油しておしまい
  • 21日21:00 提出状況の詳細が出ていたので見てみる。おい僕の回路でかすぎだろこれ…。最初の車を提出している220チームくらいのうちワースト8番目だった。ははは


あとはfuelのフォーマットを完全に解析して、carのパーサとfuelのフォーマッタ書いて、とまでやったら後は数学の問題で、ここでやっと本当のスタートにたどり着いた…、という感じでしょうか。月曜も丸1日使えてたらその辺まではいけたかな。
回路は、ちょっと考えれば少なくとも文字数にリニアなgate数にはなりそうですね。
順位を狙うのならば、小さい回路の設計を最初にもっと頑張っておくとか、提出を自動化するとかやるべきなのでしょうけれど、この大会にあまりそういう動機はないので好きにやりました。
ほかのチームの人たちの参加記を見ると、複数人でわいわい参加するのすごく楽しそうだ。特に今年の問題は役割を分担して進められるものでしたし。来年は周囲の人を誘ってみよう。


結局書いたコードの量は、回路のパーサ・シミュレータ150行 + 回路ジェネレータ550行（全部Java）というくらいでした。回路ジェネレータは無駄に大きいに違いない。
しかし去年より倍以上の時間取り組んだのにコード量は少なくなっている。入り口のところでかなり論理パズル的おもむきが強い問題でした。


期間中の3日間で体重が2kg落ちました。楽しかったけれども体には悪いと思います。

2010年2月振り返り

人生

ここに書くことで、日々これらの目標を意識して過ごすようになっていることを実感中

PA[-5%]
一歩進んで一歩下がる感じ。難しいことは最初からわかっているのだから、まあ地道にやっていきますよ
PB[3%]
当初の目標ではちょっと無理そうなので下方修正した
42:03+09:00">PC[0%]:PTに吸収合併
PD[10%]
優先度高めだったのがそうでもなくなってしまった。どうしよう
PL[12%]
継続中
PM[0%]
ひとつ目のマイルストーン。なんとかかんとか最低限の目標は達成
PP[5%]
早く進めたいが4月まではがまん
PR[0%]
進展なし
PS[15%]
そろそろ本気出す
42:03+09:00">PT[0%]:手が回らなさそうなので廃止
PT[0%]
新設（まぎらわしい）。不確定要素も多いがとにかくやってみよう

2010年1月振り返り

人生

MarathonMatchやってると他のことができなくなるのでTopCoder Openまでは封印すべき

PA[-10%]
むしろ後退してしまった。厳しい…。大きいイベントの日程が決まりつつある
PB[0%]
未だ0%というのは予想外だったがまだまだこれから
PC[0%]
4月以降に優先
PD[10%]
優先度高め
PL[4%]
早くも挫折気味だったが2月になってから復活
PM[0%]
数字上の進捗は無いがまずまず順調、数字は年末に出てればよいのです。4月までは優先
PP[5%]
4月以降に優先
PR[0%]
優先度低め
PS[1%]
申し込み済、4月までは優先
PT[0%]
優先度低め