sklave

去年の暮れにほってんとりになってた採用問題が公開されたのでやってみた。

というのも、当初問題文を読み違えていて(格子マップじゃなくて、連続的なマップだと思ってた)、「各経路点を取って最短経路問題ですかねぇ」とか「僕だったら、答えをASCIIにプロットするのに25分かかるなぁ」とか頓珍漢な事を言っていたのが恥ずかしかったからです。 問題文を読んでないので応募以前の問題ですね。ここらへんを参照

んで、最適解法を知った上でコード書いたのに40分かかりました…

さて、僕自身も経営者の端っこなので、いろいろ思う点がありました。

まず、こういうアルゴリズム系の問題を出すことでGoogleの使い方を知らない奴を簡単に落とせるのがわかったのは参考になりました。 というのも、問題解決について求められるのはその時点での知識ではなく、最終的に許される時間の中で解決できるかという点だからです。 また、実務をこなす上でのほとんどの細かい問題に関しては、それまで世界の誰もそんな問題に直面したことが無い！なんて事は殆どないはずなので、そういうった問題を確実に解けるのか？というのは重要なポイントだと思います。

また、話には聞いていましたが、それぐらいの人材が我々のような（勝手に一緒にしちゃいましたが）零細IT企業にふらっと応募することは少ないのだなというのも参考になります。そういう点で、公募する場合には根気よく採用を続ける必要がありそうなので、あんまり応募者をディスると今後の応募に影響してしまいそうな点は気になります。

このエントリに応えると、小さな企業が人を取った場合、新人の戦力が30で今の戦力と足して130だ！、というよりも、新人がしちめんどくせーことやってくれるお陰で俺らが強まって足して150だ！みたいな気概でいるのがいいんじゃないのかなーと思います。

イメージとしてはこんな感じ

以下がコード。Pythonです。:

#!/usr/bin/env python
# -*- coding:utf-8 -*-

import sys

CELLMAX = 9999

def main(input):
    m, start, goal = load_map(input)
    solve(m, start, goal)

    print_result(m, goal)

def load_map(input):
    start, goal = [], None

    d = {
        '*': -1,
        ' ': CELLMAX,
        'S': 0
    }
    m = []
    for l in input:
        m.append([d.get(ch, ch) for ch in l.rstrip()])

    for y in range(len(m)):
        for x in range(len(m[y])):
            if m[y][x] == 0:
                start.append((x, y))
            elif m[y][x] == 'G':
                goal = (x, y)

    return m, start, goal

def solve(m, start, goal):
    cur = 0
    while start:
        next = []

        for c in start:
            m[c[1]][c[0]] = cur

            for d in [(-1, 0), (0, -1), ( 1,  0), ( 0, 1)]:
                if m[c[1]+d[1]][c[0]+d[0]] > cur:
                   next.append((c[0]+d[0], c[1]+d[1]))
        start = next
        cur += 1
        if goal in start:
            m[goal[1]][goal[0]] = cur # syoboi
            return

    if goal not in start:
        raise RuntimeError, u'とけないよ'

def fill(m, c, x):
    filled = []
    for d in [(-1, 0), (0, -1), ( 1,  0), ( 0, 1)]:
        if m[c[1]+d[1]][c[0]+d[0]] > x:
           m[c[1]+d[1]][c[0]+d[0]] = x
           filled.append((c[0]+d[0], c[1]+d[1]))
    return filled

def print_result(m, goal):
    c = goal
    while True:
        check = m[c[1]][c[0]] - 1
        if check == -1:
            break

        m[c[1]][c[0]] = '$'
        for d in [(-1, 0), (0, -1), ( 1,  0), ( 0, 1)]:
            if m[c[1]+d[1]][c[0]+d[0]] == check:
               c = (c[0]+d[0], c[1]+d[1])
               break
        else:
            raise RuntimeError
    m[goal[1]][goal[0]] = 'G' # syoboi
    d = {
       -1: '*',
        0: 'S',
       '$': '$',
       'G': 'G',
    }
    for l in m:
       print ''.join(d.get(ch, ' ') for ch in l)    

if __name__=='__main__':
    main(sys.stdin)

「最短性のチェック」というのは、(コードの外で)アルゴリズムの証明をせよ、という意味だろうか？基本的にダイクストラ法を格子マップでやっているので、最短性はダイクストラ法の証明となると思うのだけど。

って岡嶋さんてスウィフトの関係者なのか！

あとはっちゅう君バジョナップ期待しています！