KLab若手エンジニアの これなぁに？

こんにちは。takada-atです。

先日開催されたアシアル株式会社、KLab株式会社の合同勉強会で発表しましたので、資料を公開します。

携帯絵文字の文字エンコーディング変換およびキャリア間のマッピングについてKLabでの対応をご紹介させて頂きました。

資料は以下にあります。

■携帯絵文字をutf-8エンコーディングにする話

先週の日曜日、弊社若手社員３人でICPC東京大会を観戦、懇親会にも参加させていただきました。
（ICPCの公式ページはこちら→ACM/ICPC Asia Regional Contest 2009, Tokyo, Japan）
今回は弊社もスポンサーとして、ICPCと学生プログラマーの支援をさせていただきました！

ICPCの会場に入るや否や、さっそく大きな歓声が！！
そう、そこで行われていたのは「Javaチャレンジコンペ」という、各チームが短時間で作成したAI同士の熱い戦いです。

こういったAI同士を競い合わせる競技は熱く盛り上げれますね。次回天下一プログラマー大会の参考にさせていただきます！

本選の優勝者は「HITORI#｣チーム。チームの一人は天下一プログラマーコンテストの優勝者です。他にも天下一プログラマーに参加されていた方々が多数入賞されていました。おめでとうございます！！

表彰の後の懇親会ではinada-nがスピーチをさせていただきました。

今後も、プログラミングコンテストの主催や後援を通して、学生プログラマーを応援していきたいと考えております！
夏に開催された天下一プログラマーコンテストが気になる方はこちらにアクセス！！

ども、amo-kです。

先日(9/7)にsymfony開発者Fabien PotencierさんがKLabにお越し下さりました！
▼ 握手！(あんまり若手エンジニアが写ってないｗ)

▼ ディスカッションの様子

symfonyの使い方から思想まで、色々なことについて話す事ができました。
世界のトップレベルのエンジニアとのディスカッションに、KLab若手エンジニア達も非常に喜んでおりました。
来年のSymfony Conference Japanで何かお役に立てる様にがんばりま〜す。

また、Fabien Potencierさんを連れて来て頂いた秋元さん、月宮さん、大野さんありがとうございました！！
今後ともよろしくお願い致します〜

amo-kです

さて、ひよこエンジニアのtakei-h, kumanaka-aにお題をだします！

我々KLab若手エンジニアは、Webアプリケーション開発に携わることが多いです。
そんな中、HTTPにおける基礎知識が有る／無いでは色々と違ってくるはずです。
例えばPHPなんかでプログラムを書くと、mod_phpがHTTP周りはかなりやってくれますので
HTTPの知識が無くとも大抵の場合は要求仕様を満たしたプログラムを書く事ができます。

しかし、WebアプリケーションからHTTPリクエストを発行するような場合には
HTTPの知識が有るにこした事は有りません。
言語で用意されているcurl的なHTTPクライアントを利用するにしてもしかりです。

ということで、、以下の２つのお題を出します ＞ takei-h, kumanaka-a

これは、２人の先輩である takada-at, honda-hも通ったんですよ。
言わば、超若手エンジニアの登竜門的なお題です。
ではよろしくー

takada-atです。

今朝(8月11日に書きました)地震のせいで早起きしたので、あまった時間を利用して、Haskellに手をだしてみました。
Haskellは関数型言語と呼ばれる言語の中でも、純粋関数型と呼ばれ、遅延評価やパターン
マッチングなどのおもしろい機能があります。
http://ja.wikipedia.org/wiki/Haskell

チュートリアルをひとりで実行するだけではつまらないので、折角なので若手ブログに報告してみます。
(気分と時間が許せばシリーズ化するかも。。)

まずHaskellの処理系としてはコンパイラであるghcを選びました。
他にはhugsというインタープリターが有名ですね。
↓ここからwindows向けのバイナリを持ってきてインストールします。

http://www.haskell.org/ghc/download.html

bin以下にパスを通せば環境構築は終了。

% ghci
で対話型コンソールが起動します。
終了は:q
スクリプト読み込みは :l

haskellの特技は、数値計算や構文解析ということで、project eulerを解いてみることにします。
いろんなチュートリアルを見ながら見よう見真似で。
入出力はHaskellの苦手らしいので、関数定義だけファイルに書いてghci上で読み込んで実行することにします。

-(1)p1.hsを作成
-(2)ghci上で :l p1.hs を実行して読み込み
-(3)定義した関数を実行してみる

* 先回りしてやってみた感想
無限リスト + 内包表記が新鮮！
無限のリストを扱えるというHaskellの特性がとても便利なのですが、
これまでにない頭の使い方を要求される感じでした。

problem1
http://odz.sakura.ne.jp/projecteuler/index.php?Problem%201
「10未満の自然数のうち、3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり、 これらの合計は 23 になる。
同じようにして、1,000 未満の 3 か 5 の倍数になっている数字の合計を求めよ。」

他の言語でも簡単だと思いますが、Haskellだと1ライナーになりました。
どうやらリストの内包表記というのを使うと便利なようです。
以下が関数定義です。
表記は見なれないですが、読み方がわかれば意味はわかりやすいです。


p1 n = sum $ [x | x <- take (n-1) [1,2..], rem x 3 == 0 || rem x 5 == 0]


読み方解説
* p1 n = …
関数定義です。nは仮引数です。

* [x | ...]
これが内包表記です。pythonにも同じ機能があるそうな。
[x | ...] は「…」のようなx を集めたリストという意味。
この部分でリストの条件を指定しています。
[ x|
x <- take (n-1) [1,2..] => 1,2…の最初の n-1個 (つまりn未満)、
, => かつ
rem x 3 == 0 || rem x 5 == 0 => 3の倍数または5の倍数
]

* sum $ [...]
はリストの合計を求める関数です。

p1 10
=> 23
p1
=> 233168

problem2
http://odz.sakura.ne.jp/projecteuler/index.php?Problem%202

フィボナッチ数列がとてもきれいに書けます。
http://www.sampou.org/haskell/tutorial-j/functions.html
↑ここの3.4あたりを参考にしました。


-フィボナッチ数列
fb = 1:2:[x+y|(x,y) <- zip fb (tail fb)]

-問題
p2 n = sum $ takeWhile (\x -> x<=n) [x | x <- fb, even x]


フィボナッチ数列の、偶数の列の内
n以下の範囲をとってきて、合計を求める

細かいことを言うと、
(\x -> x<=n) は無名関数

takeWhile function list
は、listの先頭から順番に要素をとってきて、functionがFalseを返すとやめる。

ほとんど問題文を書き起こしただけで、関数定義になりました。

p2 4000000
=> 4613732

最初はまった点。↓のように書いてしまいました。
sum $ [x | x <- fb, x<=n, even x]

これは無限リストなので、sumの計算は永遠に終わりません。
「フィボナッチ数列はだんだん大きくなるので1度nを超えたら、それより先n以下になることはない」という条件を自明視していたのですが、当然ながらHaskell側は指定されなければそんなことはわからないので、永遠に x<=n を満たす要素を求めて無限リストをたどりつづけてしまいます。
takeWhileを使えば、途中で計算をやめてくれます。

以上でした。
…つづく(かも)

amo-kです。

2009年8月2日(日)に天下一プログラマ大会 2009が終了しました！
KLabとしても初の試みということもあり、運営の不手際がありましたが、
結果として大成功（大盛り上がり）なイベントにできたと感じています。

２１チーム、３１人が本戦に参加しました。

受賞チーム、名前は以下の通り。

受賞した皆さん、おめでとうございました！！

本戦で出題した問題やその解説等、詳細は追って公開しますのでお楽しみに！

こんにちは、天下一プログラマーコンテスト実行委員の inada-n です。

第三回Web予選に参加してくださった方、ありがとうございました＆お疲れ様でした。
予選通過者には近日中に連絡が行くはずなので、もうしばらくお待ち下さい。

さて、天下一プログラマーコンテストでは、言語の性能が戦力の決定的な差にならないように、
時間がかかりそうな問題でもC++やJavaを使わずに解いてみて難易度の調整をしています。

ですが、今回の予選の第三問では私の調整ミスで、深さ優先探索+簡単な枝刈りを
使った場合、 C++では数秒〜数分で答えが出るのに PHP/Ruby/Python では数時間
かかってしまう事があり、言語によるハンディキャップが大きくなってしまいました。

投稿されたプログラムに関しては、回答が最善解でないもの、プログラムのみの
回答になっているものを含めて全て目を通しているのですが、もしきちんとプログラムが
出来ていたのに計算が終わる前に時間切れになって投稿できなかった方がおられたら
申し訳ありません。

お詫び(?)に今回の第三問問題文と、私の作った回答プログラムを紹介します。 利用した
言語はPythonで普通に実行した場合20分以下、PsycoというJITコンパイラを利用した場合
5分以下で最適解が見つかります。

問題文

解答プログラム

import csv
import itertools
from collections import defaultdict

try:
    import psyco
    psyco.full()
except:
    pass

_FIELD_SIZE = 30
_INITIAL_FIELD = bytearray("_") * _FIELD_SIZE **2
_MINIMUM_LENGTH = 0

class Field(object):
    __slots__ = "_field _space _deadspace _minimum_line".split()

    def __init__(self, f=_INITIAL_FIELD, space=_FIELD_SIZE**2, deadspace=0, minimum_y=0):
        self._field = f
        self._space = space
        self._deadspace = deadspace
        self._minimum_line = minimum_y

    def put(self, pos, size, chr):
        """try put size to pos.

        Return new Field if can."""
        x,y = pos
        w,h = size
        F = _FIELD_SIZE
        if x + w > F or y + h > F:
            return None

        field = self._field
        t = b'_' * w
        for offs in xrange(F * y + x, F * (y+h), F):
            if field[offs:offs+w] != t:
                return None

        new_field = bytearray(field)
        t = chr * w
        for offs in xrange(F * y + x, F * (y+h), F):
             new_field[offs:offs+w] = t

        ret = Field(new_field, self._space - w*h, self._deadspace, self._minimum_line)
        ret._fill_dead_space()
        ret.calc_minimum_line()
        return ret

    def _fill_dead_space(self):
        F = _FIELD_SIZE
        M = _MINIMUM_LENGTH
        field = self._field
        _s = ord('_')
        _d = ord('#')

        for yoff in xrange(self._minimum_line * F, F*F, F):
            end = yoff + F
            pos = field.find('_', yoff, end)

            while 0 <= pos < end:
                pp = pos+1
                while pp < end and field[pp] == _s:
                    pp += 1
                count = pp - pos
                if count < M:
                    field[pos:pp] = '#' * count
                    self._space -= count
                    self._deadspace += count
                pos = field.find('_', pp, end)

        for x in xrange(F):
            vline = field[x:F*F:F]
            pos = vline.find('_')
            while 0 <= pos < F:
                pp = pos+1
                while pp < F and vline[pp] == _s:
                    pp += 1
                count = pp - pos
                if count < M:
                    field[x + F*pos : x + F*pp : F] = '#' * count
                    self._space -= count
                    self._deadspace += count
                pos = vline.find('_', pp)

    def calc_minimum_line(self):
        pos = self._field.find('_')
        if pos < 0:
            self._minimum_line = _FIELD_SIZE
        else:
            self._minimum_line = pos // _FIELD_SIZE

    def __str__(self):
        return '\n'.join(str(self._field[i:i+_FIELD_SIZE]) for i in xrange(0, _FIELD_SIZE**2, _FIELD_SIZE))

def read_stores():
    reader = csv.reader(open('depart_data.csv'))
    d = {}
    for row in reader:
        c, s, m = [x.strip() for x in row]
        w,h = map(int, s.split('x'))
        m = int(m)
        d[c] = (w, h, m)
    return d

def _solve(field, stores, remains, current, max_dead, dump=0, top=False):
    if dump > 0:
        print dump, remains, current

    b = remains[0]
    w, h, m = stores[b]
    min_wh = min(w,h)

    if dump > 0:
        print dump, "next store:", b, w, h

    next = current+m
    next_remains = remains[1:]

    pos = field._field.find('_')
    while 0 <= pos:
        x, y = pos % _FIELD_SIZE, pos // _FIELD_SIZE
        if top:
            if x > (_FIELD_SIZE - w) / 2:
                x = 0
                y += 1
                pos = y * _FIELD_SIZE
            if y > (_FIELD_SIZE - h) / 2:
                break
        if dump > 1:
            print dump, "x,y = ", x, y
        nf = field.put((x,y), (w,h), b)
        if nf is not None and nf._deadspace <= max_dead:
            if next_remains:
                res = _solve(nf, stores, next_remains, next, max_dead, dump-1)
                if res:
                    return res
            else:
                return nf
        if nf and x == 0 and field._deadspace + h > max_dead:
            pos += _MINIMUM_LENGTH
        else:
            pos += 1
        pos = field._field.find('_', pos)

    pos = field._field.find('_')
    while 0 <= pos:
        x, y = pos % _FIELD_SIZE, pos // _FIELD_SIZE
        if top:
            if x > (_FIELD_SIZE - h) / 2:
                x = 0
                y += 1
                pos = y * _FIELD_SIZE
            if y > (_FIELD_SIZE - w) / 2:
                break
        if dump > 1:
            print dump, "x,y = ", x, y
        nf = field.put((x,y), (h,w), b)
        if nf is not None and nf._deadspace <= max_dead:
            if next_remains:
                res = _solve(nf, stores, next_remains, next, max_dead, dump-1)
                if res:
                    return res
            else:
                return nf
        if x == 0 and field._deadspace + w > max_dead:
            pos += _MINIMUM_LENGTH
        else:
            pos += 1
        pos = field._field.find('_', pos)
    return False

def solve(stores, remains, area):
    remains = sorted(remains, key = lambda x: stores[x][0] * stores[x][1], reverse=True)
    field = Field()

    max_dead = _FIELD_SIZE**2 - area
    print "max_dead", max_dead

    global _MINIMUM_LENGTH
    _MINIMUM_LENGTH = min(min(stores[s][0], stores[s][1]) for s in remains)
    print "_MINIMUM_LENGTH", _MINIMUM_LENGTH

    return _solve(field, stores, remains, 0, max_dead, dump=2, top=True)

def _pre_research(stores):
    store_keys = stores.keys()
    num_store = len(store_keys)
    combis = defaultdict(list)
    while num_store > 0:
        for combi in itertools.combinations(store_keys, num_store):
            earn = 0
            area = 0
            for s in combi:
                st = stores[s]
                area += st[0]*st[1]
                earn += st[2]
            if area > _FIELD_SIZE**2: continue
            if earn < 450: continue
            combis[earn].append((combi, area))
        num_store -= 1

    print "earning, combination, area"
    for k in sorted(combis.keys(), reverse=True)[:5]:
        for v in combis[k]:
            print k,v
    return combis

if __name__ == '__main__':
    stores = read_stores()
    combis = _pre_research(stores)
    for earn in sorted(combis.keys(), reverse=True):
        print "target:", earn
        for comb, area in combis[earn]:
            field = solve(stores, comb, area)
            if field:
                print earn
                print str(field).replace('#', '_')
                break
        else:
            continue
        break

解説

それでは、本戦で皆様にお会いできるのを楽しみにお待ちしております。

こんばんは amo-k です。

Web予選第３回が無事完了しましたが、
御陰さまで天下一プログラマは大盛況となっております！

予想を大幅に上回る投稿数で嬉しい限りなのですが、採点サイドはテンテコ舞いとなっております 汗。

未だWeb予選第２回の解説を公開していないのですが、
実行委員inada-nが、第３回の３問目の解説をまとめたそうですので取り急ぎ実況してもらう事にします。

（順序がとか言わないでね！

追ってその他の問題やWeb予選第２回目の解説も公開しますのでお楽しみに〜

では、inada-n よろしくです！

Web予選第３回の曜日が間違えていましたので更新しました。７月２５日土曜日です。
suztomoさんありがとう！（Fri Jul 24 15:25:54 JST 2009）

こんにちはamo-kです！

天下一プログラマWeb予選２回目が無事完了しました！

なんと２回目も大反響で、４６組が合計１２９の解答を投稿してくれました〜
※ １回目は５４組が１７３解答を投稿
またまた採点が大変だーーー　

１回目の不手際を反省／学習しつつ２回目の開催に挑みましたが、、、改善の余地がまだまだいっぱいありますね　汗
しかし！　前回／今回の経験を活かすと共に、参加してくれた学生達やブログ／twitterなどの声を参考に、より魅力的なコンテストとしていきますのでよろしくです！！

Web予選第３回を７月２５日（土）に開催するので応募してね！
（天下一プログラマ２００９の予選としてはラストチャンスだよ！！

また、概況は追って公開しますのでお楽しみにｗ

問題と解答が無い状態で更新しておりましたので追記しました。（Thu Jul 9 11:39:17 JST 2009）

どうも、天下一プログラマーコンテスト実行委員会の isono です。
告知よりも、少し遅れましたが天下一プログラマーコンテスト Web 予選 第１回の概況をお伝えします。予想をはるかに上回る回答数につき集計システムを改修しながらお送りしています。

まずは問題の開示と機械集計の結果から。

※のべ回答数なので複数回答いただいている分も含んでいます
※回答時間は審査基準ではありませんので参考までに

第２問の回答数が最も多く、第１問と第３問が僅差という興味深い結果となっています。両方ループで解決してしまいそうな問題だからでしょうか？

３問とも回答いただいて、３問とも正解をにたどり着いている方が想定数を大幅に上回っています。コードの査読の結果は未だ全容は出ていませんので、ここでは詳しい結果には触れていませんが、内容を加味して工夫されている方に加点して差をつけるしかありません。

現在審査員が全力で審査を行っています。缶詰審査中に上がったつぶやきの中からいくつか抜粋しておきますので雰囲気だけでも。

第１回の結果はレベルも競争率も想定以上になってしまっています。正解と工夫した点のアピールの掛け算が攻略ポイントとなるでしょう。あえてLLを選択して工夫を最大限アピールしてみる作戦もありかもしれません。

全体として問題は決して簡単すぎることは無いと思うのですが、2回目以降の問題レベルはもう少し引き上げるかもしれません。

第2回は来週 7/15 に開催します。第１回目に参加された方も、されなかった方もふるってご参加ください。新規エントリーは 7/14 18:00 まで受け付けます。

なお、既にエントリー済みの方（第１回目参加者を含む）は改めてエントリーしなくてもそのまま２回目以降参加いただけます。

Web予選は24時間ですが本戦では限られた時間で競っていただきますので結果がどのように変化するのかも注目です。

最後にお詫びとお礼を。
Web予選第１回ではメールの不達などご迷惑をおかけしました。開催時間が１時間程遅れた方考慮して終了時間を１時間延長しました。（延長に関しては特に大きな影響は無かったようですが…）
参加者の熱き闘志に応える為、我々は努力を惜しみません。
今後とも稚拙な部分はあるかと思いますがご了承ください。
本大会はイベント開催になれた人材ではなく運営も採点もKLab技術者が手探りお送りしております。（この方法がプログラマーの気持ちを一番理解できる最善の方法であると信じています）

本戦で皆様にお会いできる事を楽しみにしております。