コードを短く書く人のブログ

コードゴルフを稀に取り上げるブログ

AOJ watch toolsの話

AOJ watch toolsの話

この記事はICT Advent Calendarの15日目として書かれました。

前置き

どうもこんばんわ、@orisanoです。Advent Calendarで何を書こうと悩んでいましたが、
今年作ったものがあるじゃないかと気づいたのでそれを記事することにしました。
僕は今年の1月くらいからAOJ watch toolsというものを開発しつつ公開してました。
使ったこと、見たことがあるという人もいるかもしれません。
以下の3つをまとめてAOJ watch toolsと呼んでいます。

今回は僕とAOJ watch toolsの1年間を書いていきたいと思います。

きっかけ

きっかけはraimei10130くんだったと記憶しています。
当時、AOJで何問解いたかを後輩に聞くのが趣味だった僕は
皆のアイドルraimei10130くんと

僕「何問ときましたか?」
raimei10130「(◞‸◟)」
僕「何問ときましたか?」
raimei10130「0問です。」
僕「1日1問解きましょう!!!!!!」
raimei10130「わかりましたよ!!!!!!!!!!!!!!!!!!!」
僕「AOJ監視しとくから」

というやりとりをしました。これがAOJ watch toolsを作るきっかけになったわけです。
といってもこのやりとりのあと2週間ほどは普通にAOJを監視していました。
2週間たって監視も面倒くさくなってきてましたが、当時の他の1年生や2年生にも
同じようなやりとりをしていて引くに引けない状態(自業自得)だったので
ツールをつくろうと決意しました。

(この時点でのraimei10130のSolve数:0)

開発(初期)

ローカルで動く監視ツールでも良かったのですがその時の僕が
何を考えたのかはわかりませんがHTMLでやろう、JS(CoffeeScript)でやろう
という気分になっていました。おそらくその背景にはサーバ借りたくない
気持ちが強かったのだと思います。結果的にそれがいい方向に転がったと思います。
HTML+JS(Coffee)でやってdropboxのpublicフォルダでホスティングしようと
考えていましたが、ちょうどその時期にGithub Pagesの存在を知ったので
そちらでやることにしました。
いろいろやることが決まったのでもりもり開発を始めました。
当時あまりJS(Coffee)を書いたことがなかった僕はコールバック地獄にはまりながらも
ajaxAPIにアクセスしてSolve数を取得できるようになりました。
aoj_watch(ソースコードめちゃくちゃ)はかなり初期に作られています。

(この時点でのraimei10130のSolve数:0)

開発(中期)

いろいろできることが見えてきたので部内だけのsubmit一覧とか作れると
面白いかなと思い作ることを決意します。この時期くらいまでリファクタリングなど
完全に無視して突っ走っています。完璧にやばいです。
そんな完璧にやばい状況でもaoj_submit_watchは完成します。
複数ユーザの情報取得なんていうAPIは存在しなくて一人ずつ情報を取得して
クライアント側でマージするという処理を行っているのでAPIアクセスが多く
非常に重いページに仕上がっています。
この頃はユーザの追加がかなりだるかったのを覚えています。

(この時点でのraimei10130のSolve数:0)

開発(今まで)

中期を超えたあたりからAOJのdiffを取るツールがほしいと
後輩から言われていたし自分も欲しかったので 次作るのはdiffツールだと決めていました。
AOJのdiffを取るツールがあるのは知っていましたが、
学内からだとブロックされたり、レスポンスタイムアウトしたりなど
まともに使えた記憶がありませんでした。
3つ目のツールを作るときにさすがにリファクタリングをしようということで
勉強してコールバック地獄から抜けだしたり、クラス化を行ったりしました。
このリファクタリングしている時に、seka先輩にaoj_submit_watchの高速化を
やってもらい、その際にgruntでいろんな作業を自動化してもらいました。
本当に感謝しています。ありがとうございました!!!!!!!!!!!!
リファクタリングに結構時間がかかりましたが最後のaoj_compareが出来上がりました。
ぶっちゃけどのAOJ watch toolsより反響が大きく、びっくりしました。
これ以降は細かい機能追加などを今日まで行って来た次第です。
これまでorisano.github.ioにpullreqをくれた、
たいちゃん@imishinistとくまさん@higumachan725、seka先輩
本当にありがとうございました。これからもpullreqくださいお願いします。

(この時点でのraimei10130のSolve数:9)

作って思ったこと

AOJ watch toolsを作って公開してみて思ったことがあります。
それは可視化が重要ということです。これは僕自身の話なのですが
aoj_watchを作って自分のsolve数を見るようになって、
m_kyoujyuやli_saku先輩を越してやろうという具体的な目標を持つようになりました。
具体的な目標を持つことで開発当時100問解いていたかすら
怪しかった僕が376問までになり、ICT委員会の中で2位まで上り詰めました。
可視化、具体的な目標、それを効率的に達成するためツールがあると
切磋琢磨しやすくなると僕は考えています。AOJ watch toolsで
ICT委員会の競技勢の実力が上がると非常に嬉しいです。

(この時点でのraimei10130のSolve数:9)

最後に

全国のICT委員会でもこんなシステムを導入してみるといいかもしれません。
僕のGithub Pagesをcloneして、users.jsonを書き換えると
どこの組織でも使えると思います。役に立てると幸いです。
最後に言いたいのは

raimei10130が1日1問解いてたら360問くらいなはずなので頑張って問題解いてください!

明日はみずきちさんの記事だと思います。

宿題 0b1 #kagapra0715

AOJ 0569

21:31~22:24

外側からラベリングして建物のセルに到達した回数を求めれば良い。
後は6近傍の時の移動が出来ればラベリングするだけ。
外側に番兵を置く実装をすると非常に楽。
僕は6近傍の時の移動ができなかったので時間がかかりました。
53分
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1020674

AOJ 0033

22:26~22:33

取りうる状態が2^10個くらいなので全探索で余裕。
Aに入れるか、Bに入れるかをDFSする。
7分
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1020685

AOJ 0118

22:35~22:42

このようなラベリング問はUnionFindで常勝(と思っているので)
必要な部分だけUnionFind書いて終了。
4近傍で同じ文字があればmergeして、最後にgroupの数を出力するだけで良い。
実際dfsとかのほうが短く早く書けそうですが、こういう問題を見ると思考停止してしまう。
7分
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1020692

AOJ 0558

22:44~23:18

読んで「ダルそう」となった問題。
S -> 1 -> 2 -> 3 -> ... -> N
の最短経路長の和を求める問題だということにすぐに気がついた。
そこからは思考停止してグラフを作って、ダイクストラっぽいもので最短経路長を求めた。
34分
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1020743

AOJ 0121

23:19~23:35

7パズルを解く問題。
最初の時点で完成版盤面から解くことの出来る
全ての盤面の最短の解をBFSで求めて保持しておく。
盤面が7!程度しかないので問題はない。
BFSを書き慣れていなかったり、いろいろ躓いた。
16分
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1020767

AOJ 0529

0:37~0:45

半分全列挙を行う問題。
kagamiz先生が講義で言っていたことを素直に実装した。
0点を追加することで必ず4本ダーツを投げるようにして
N^2で2回投げるパターンを列挙しその中から一つ選び,
M-今のパターンの点数 以下の最大を2分探索で求めることで解くことが出来る。
8分
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1020833

とりあえずこれからも宿題で解いたものをブログに上げると思います。

毎年恒例の年明けたから書いたコード

あけましておめでとうございます。@orisanoです。

毎年恒例(1年ぶり2回目)の年明けたから書いたコードを適当に晒しておきます。

去年とちょっとネタがかぶってるので来年から本気出します。
説明はしません。見たらわかると思います。

http://ideone.com/0ty1OW

puts();main(){qsort((int[]){2*2*2*3*479*164093,11273*150769,79*1453*14813,7*47*89},2,2*2,puts);}

適当に今年の目標。

ブレない目標を持つこと
が今年の目標です。

今年がより良い年であることを願います。

僕がコードゴルフを始めたキッカケ

こんばんわ。@orisanoです。

この記事はICT Advent Calenderの20日目の記事です。

毎度毎度のことですが、
今日は僕が比較的時間を費やしている趣味である。
コードゴルフについて語りたいと思います。

始めたきっかけ

始めたきっかけはえむきょうじゅでした。
2年の頃?だったので今からちょうど2年前になります。
夏休みの合宿中、プロコンの開発の息抜きでえむきょうじゅにそそのかされたのが
すべての始まり(終わり)でした。

誰もが通るAOJ0000

某くま先輩と某えむきょうじゅが当時聞いたこともないコードゴルフという
趣深い競技をしていたので、開発に疲れた僕は息抜きとしてやってみることにしました。
初めてのコードゴルフAOJ0000でした。

#include <stdio.h>
int main(void)
{
    int i, j;

    for (i = 1; i <= 9; i++){
        for (j = 1; j <= 9; j++){
            printf("%dx%d=%d\n", i, j, i * j);
        }
    }

    return (0);
}

当時の僕はこんな感じのコードを

#include<stdio.h>
int main(void){
    int i,j;
    for(i=1;i<=9;i++){
        for(j=1;j<=9;j++){
            printf("%dx%d=%d\n",i,j,i*j);
        }
    }
    return 0;
}

こうすることをコードゴルフと呼ぶ非常に素直な好青年だったに違いありません!!
しかし、最終的に

j;main(i){for(;i%10;(j=++j%10)?printf("%dx%d=%d\n",i,j,i*j):i++);}

こういったコードを書く青年になってしまったようです。

そして

プロコンの開発(2時間)は停滞し、息抜き(5時間弱)が行われて、
おりさのという青年は変わってしまいました。

ここで伝えたかったことは趣味に打ち込むのもいいけど、
「実際のコーディングに影響を出しちゃダメだぞ★」ということです。
あとプロジェクトに火をつけちゃダメ、ゼッタイ

むしろ僕はコードゴルフを始めたから人一倍
コードの綺麗さ、読みやすさを意識するようになりました。
コードゴルフをやることでトリッキーなことをしているコードを読めるようになったり
環境について詳しくなったり、1byteに命をかけるようになったり
といろいろ良いことがありました。

最後に

僕がコードゴルフを始めたキッカケについて語る記事が
長くなってしまって申し訳ありませんでした。
明日はプロラボ現会長の@Pelkiraくんが書いてくれます。
(Accepted 2822byte)

アドレスから添字を求めるのがめんどくさい

どうも、@orisanoです。

今日は、bsearchという関数を使ってて思ったのですが、
ポインタから添字を求めるのってちょっとだけめんどくさいなって思いました。
ので、ソースコードを書いて、忘備録的にあげようかなと思った次第です。
以下コード

typedef unsigned long long ulong;
ulong ptr2index(void *head, void *cur, size_t size)
{
	ulong ha = (ulong)head;
	ulong ca = (ulong)cur;

	if (ca < ha) ha ^= ca ^= ha ^= ca;
	return ((ca - ha) / size);
}

追記: どの処理系でもできるか保証できないですが

int ary[1024];
int *p = ary;
int *q = ary + 54;
int d;

d = q - p;

という感じでやっても添字は求まるっぽいです。(詳しくは調べてないです

処理系によってアドレスが64bitだったりするので、最初からlong longにしておけば32bitの処理系でも大丈夫なんじゃないかっていう甘えです。

渦巻き生成ってめんどくさい

どうも、72日ぶりの更新の@orisanoです。

渦巻き生成っていざコードに落とそうと思うとめんどくさいって思いました。
(ICPCのD問題を見た感想)

なので、てきとーに関数を作っておけばいいと思ったので作りました(てきとー

可読性もひったくれも無いコード。

int make_spiral(int *m, int s, int n, int hour, int is_cw)
{
	int x, y;
	int c, l, v, i;
	int t[] = {0, -1, 0, 1, 0, -1, 0, 1};
	int *d = t + (hour / 3 % 4 + 4 & 3);

	n & 1 || n++;
	x = y = n / 2;
	c = l = v = 0;
	n *= n;

	for (m[y * s + x] = ++c; c < n; v &= 3){
		for (i = 0; i < l; i++){
			x += d[v + 1];
			y += d[v] * (is_cw ? 1 : -1);
			m[y * s + x] = ++c;
		}
		if (++v & 1) l++;
	}
	return (0);
}

試しに使ってみたのがこれです。http://ideone.com/zDWAgk

コメントはめんどくさかったので書きませんでした。察してください。
あと回転が始まる方向は時計の針の方向を採用しました。
3時、6時、9時、12時の方向が選べるはず、それが引数のhourですね。

久々の更新が適当ですいません。

Erlangでフィボナッチ数列求めるやつを書いてみた。

1週間ぶりくらいの更新になります。

Orisanoです。最近Erlangと戦っています。
Sortを書いてみたの方はちょっと時間かかっちゃって更新できないので、
何気なく書いたフィボナッチ数列を求める記事で間を持たせたいと思います。

fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N - 1) + fib(N - 2).

とまあ最初こういう実装をしたらfib(100)ですらまともに帰ってこない。。。。(悲しみ
ま、当然ですよね。O(2^n)くらいになるのかな・・・自信ない。


追記:
ついでに、末尾最適化したコードも書きました

tailfib(0) -> 0;
tailfib(1) -> 1;
tailfib(N) -> tailfib(N, 0, 1).
tailfib(2, P2, P1) -> P2 + P1;
tailfib(N, P2, P1) -> tailfib(N - 1, P1, P2 + P1).

追記終了


なんかこのままじゃ悔しかったので
いろんなサイトを参考にしつつ、

logfib(0) -> 0;
logfib(1) -> 1;
logfib(2) -> 1;
logfib(N) when N rem 2 =:= 0 ->
	Res1 = logfib(N div 2 + 1),
	Res2 = logfib(N div 2),

	Res2 * (Res1 * 2 - Res2);

logfib(N) ->
	Res1 = logfib(N div 2 + 1),
	Res2 = logfib(N div 2),

	Res1 * Res1 + Res2 * Res2.

O(log n)で求めるコードを書いてfib(1000000)まではストレスなく
表示までしてくれるコードになりました。
10000000でも求めてはくれるのだが、表示にものすごい時間がかかる。

一応Erlangのプロセス辞書というものを使ってメモ化的なこともやってみました。

logfib(0) -> 0;
logfib(1) -> 1;
logfib(2) -> 1;
logfib(N) ->
	Memo = get(N),
	if 
		Memo =:= undefined ->
			Res1 = logfib(N div 2 + 1),
			Res2 = logfib(N div 2),
	
			if
				N rem 2 =:= 0 ->
					Res = Res2 * (Res1 * 2 - Res2);
				true ->
					Res = Res1 * Res1 + Res2 * Res2
			end,
			put(N, Res);
		true ->
			Res = Memo
	end,
	Res.

今書いてるのが、プロセスを作って並列化するコードなのですが、
Erlangの強みを生かしたコードが書けるといいなって感じです。

今回はここまでにしたいと思います。
ではでは