Project Euler の 79 番目 - peanutsjamjam's diary

実は id:tanakaBox さんのダイアリー「ボクノス」で、初めて Project Euler のことを知ったのだけど、「なんだか難しそうだなぁ」と思っていた Problem 79 が、tsort で解けるかも、と思ってやってみたら簡単にいけました。（tsort コマンドを使ったことが無い方はこちらをどうぞ。）

#! /bin/sh

# fetch 'http://projecteuler.net/project/keylog.txt'
# wget 'http://projecteuler.net/project/keylog.txt'

sed 's/\([0-9]\)\([0-9]\)\([0-9]\)/\1 \2 \2 \3/' keylog.txt | tsort | tr -d '\n'
echo ""

sed の部分は、与えられた入力の各行をこんな風に再構成しています。

[ひとつ目の数字] [スペース] [ふたつ目の数字] [スペース] [ふたつ目の数字] [スペース] [みっつ目の数字]

入力 (keylog.txt) :

319
680
...

出力 (tsort に食わせるもの）:

3 1 1 9
6 8 8 0
...

この意味は、

3 の後に 1 が出てくる
1 の後に 9 が出てくる
6 の後に 8 が出てくる
8 の後に 0 が出てくる

です。

これを tsort に食わしてやると、うまいことトポロジカルソートしてくれます。

Project Euler: http://projecteuler.net/
Problem 79 - Project Euler: http://projecteuler.net/index.php?section=problems&id=79
Problem 79 - セキュリティキーを解読せよ - ボクノス: http://d.hatena.ne.jp/tanakaBox/20080427/1209276589
tsort - peanutsjamjamのFreeBSD日記 - freebsdグループ: http://freebsd.g.hatena.ne.jp/peanutsjamjam/20060504/p1
On-line Manual of "tsort" - The FreeBSD Project (Japan): http://www.jp.freebsd.org/cgi/mroff.cgi?subdir=man&lc=1&cmd=&man=tsort&dir=jpman-5.4.0%2Fman§=0