Google Developer Day 2010 Japan DevQuiz

なんだかいろいろなところでGoogle Developer Day 2010 Japanで出題されたDevQuizのソースコード公開が流行っているようなのでとりあえず晒しておく。Super Hackers枠の問題を選択問題を含めて全部解いた。使用言語はPython。

Google Maps API

Google Maps APIの問題は巡回セールスマン問題だけどたかだか10カ所を廻るだけなので簡単だった。一応行きと帰りは所用時間が変わることもあるから有方向グラフ問題なのかな。

import sys, urllib
import simplejson

url = "http://maps.google.com/maps/api/directions/json?origin=%s&destination=%s&sensor=false&key=MAPS_API_KEY"

class Node:
    def __init__(self, data):
        self.place = data[0]
        self.latlng = "%s,%s" % tuple(data[1:])

def get_duration(start, end):
    json = urllib.urlopen(url % (start, end)).read()
    data = simplejson.loads(json)
    return data["routes"][0]["legs"][0]["duration"]["value"]

def find_route(current_node, nodes):
    global duration, min_duration, current_duration, route, min_route, start_node

    if len(nodes) == 0:
        if current_duration + duration[(current_node, start_node)] < min_duration:
            min_duration = current_duration + duration[(current_node, start_node)]
            min_route = route[:]
            min_route.append(current_node)
            min_route.append(start_node)
        return

    route.append(current_node)
    for node in nodes:
        if current_duration + duration[(current_node, node)] > min_duration:
            continue
        current_duration += duration[(current_node, node)]
        new_nodes = nodes[:]
        new_nodes.remove(node)
        find_route(node, new_nodes)
        current_duration -= duration[(current_node, node)]
    route.pop()

def main(args):
    global duration, min_duration, current_duration, route, min_route, start_node

    data = [l.strip().split() for l in file(args[1])]
    nodes = []
    for d in data:
        nodes.append(Node(d))
    start_node = nodes[0]

    duration = {}
    for node1 in nodes:
        for node2 in nodes:
            if node1 == node2: continue
            duration[(node1, node2)] = get_duration(node1.latlng, node2.latlng)

    min_duration = 0
    for i in range(len(nodes) - 1):
        min_duration += duration[(nodes[i], nodes[i+1])]
    min_duration += duration[(nodes[-1], start_node)]
    min_route = [node for node in nodes]
    min_route.append(start_node)

    current_duration = 0
    route = []
    find_route(start_node, nodes[1:])
    print min_duration
    print " ".join([node.place for node in min_route])

if __name__ == "__main__": main(sys.argv)

2-legged OAuth

OAuthは何回か利用したことがあるから余裕だろうと思ったら、くだらないミスをしていて何回かリトライしてしまった。Pythonで書いたけどコード自体は短い。

import urllib, urllib2, oauth

consumer_key = "CONSUMER_KEY"
secret_key   = "SECRET_KEY"
realm        = "devquiz"
url          = "http://gdd-2010-quiz-japan.appspot.com/oauth/CONSUMER_KEY"
params       = { "hello": "world" }

consumer = oauth.OAuthConsumer(consumer_key, secret_key)
request = oauth.OAuthRequest.from_consumer_and_token(consumer, None, http_method="POST", http_url=url, parameters=params)
request.sign_request(oauth.OAuthSignatureMethod_HMAC_SHA1(), consumer, None)
req = urllib2.Request(url=url, data=request.to_postdata(), headers=request.to_header(realm))
print urllib2.urlopen(req).read()

Shiritori

しりとりはコード書いたけど補助として使っただけ。Nodeクラス作ってグラフ問題として扱った。でも人力でも解けそうな感じだった。どうせなら全自動で綺麗なコードが書きたかったな。

PAC-MAN

パックマンはまずシミュレータを書いた。これはゲームクラス、敵クラス、状態クラスを作っておいて、ゲームクラスで敵クラスと状態クラスのリストを保持しておく。ゲームクラスにnextメソッドを実装し、そのメソッドの引数としてパックマンの動作を渡し、メソッド内で敵クラスのmoveメソッドを呼び出す。ついでに敵の次に動く位置を表示したり、undo/redoや再開なども追加。因みにシミュレータだけなら状態クラスはいらない。

そして試しに手動で動かしたら簡単に解けてしまったので(しかも楽しい)、ソルバ実装のやる気がみるみる下がってしまうことに(得点は41,247,523)。でも全く手をつけないのもどうかと思ったので、簡単なソルバだけ実装。レベル1は瞬時に(多分)最適解を出力。レベル2は解くだけなら瞬時だけどスコアは良くない。レベル3は短時間では解けない感じ。枝刈りとかアルゴリズムの改良とかは、もともと時間がなかったことに加えてやる気が下がってしまったので結局やらなかった。

import sys, copy

class State:
    def __init__(self, pacman, prev_pacman, path, dots, enemies):
        self.pacman = pacman
        self.prev_pacman = prev_pacman
        self.path = path[:]
        self.dots = dots[:]
        self.enemies = copy.deepcopy(enemies)

class Enemy:
    def __init__(self, char, pos, W, WH, types):
        self.char = char
        self.pos = pos
        self.prev_pos = -1
        self.W = W
        self.WH = WH
        self.types = types
        self.ncross = 0

    def move(self, pacman):
        dirs = [self.W, -1, -self.W, 1]  # 下、左、上、右.
        if self.prev_pos == -1:
            for d in dirs:  
                x = self.pos + d
                if x < 0 or x >= self.WH or self.types[x] == '#':
                    continue
                self.pos, self.prev_pos = x, self.pos
                break
        else:
            if self.types[self.pos] == 'W':
                for d in dirs:
                    x = self.pos + d
                    if self.prev_pos == x or x < 0 or x >= self.WH or self.types[x] == '#':
                        continue
                    self.pos, self.prev_pos = x, self.pos
                    break
            elif self.types[self.pos] == 'E':
                self.pos, self.prev_pos = self.prev_pos, self.pos
            elif self.char in ('V', 'H'):
                dx = pacman % self.W - self.pos % self.W
                dy = pacman // self.W - self.pos // self.W
                f, df, s, ds = (dy, self.W, dx, 1) if self.char == 'V' else (dx, 1, dy, self.W)
                self.prev_pos = self.pos
                if f < 0 and self.types[self.pos-df] != '#':
                    self.pos -= df
                elif f > 0 and self.types[self.pos+df] != '#':
                    self.pos += df
                elif s < 0 and self.types[self.pos-ds] != '#':
                    self.pos -= ds
                elif s > 0 and self.types[self.pos+ds] != '#':
                    self.pos += ds
                else:
                    for d in dirs:
                        x = self.pos + d
                        if x < 0 or x >= self.WH or self.types[x] == '#':
                            continue
                        self.pos = x
                        break
            elif self.char in ('L', 'R', 'J'):
                if self.char == 'R':
                    dirs.reverse()
                elif self.char == 'J':
                    if self.ncross % 2 == 1: dirs.reverse()
                    self.ncross += 1
                idx = (dirs.index(self.prev_pos - self.pos) + 1) % 4
                dirs = dirs[idx:] + dirs[:idx]
                for d in dirs:
                    x = self.pos + d
                    if self.prev_pos == x or x < 0 or x >= self.WH or self.types[x] == '#':
                        continue
                    self.pos, self.prev_pos = x, self.pos
                    break

class Game:
    def __init__(self, T, W, H, data):
        self.T = T
        self.W = W
        self.H = H
        self.WH = W * H
        self.data = data
        self.types = []
        self.dots = []
        self.enemies = []
        self.path = []
        self.is_quit = False
        self.t = 0
        self.prev_pacman = -1
        for i in range(self.WH):
            if self.data[i] == '#':
                self.types.append('#')
            else:
                if self.data[i] == '.':
                    self.dots.append(i)
                elif self.data[i] == '@':
                    self.pacman = i
                cnt = 0
                for d in (-1, 1, -self.W, self.W):
                    x = i + d
                    if x < 0 or x >= self.WH or self.data[x] == '#':
                        continue
                    cnt += 1
                if cnt == 1:
                    self.types.append('E')  # dead end
                elif cnt == 2:
                    self.types.append('W')  # way
                else:
                    self.types.append('C')  # crossing
        self.ndots = len(self.dots)
        for i in range(self.WH):
            if self.data[i] in ('V', 'H', 'L', 'R', 'J'):
                self.enemies.append(Enemy(self.data[i], i, self.W, self.WH, self.types))
        for i in range(self.WH):
            if self.data[i] != '#':
                self.data[i] = ' '
        self.states = []

    def next(self, D='.'):
        if D == 'q':
            self.is_quit = True
            print len(self.path), "".join(self.path)
            return True
        dirs = { 'h': -1, 'j': self.W, 'k': -self.W, 'l': 1, '.': 0 }
        self.states.append(State(self.pacman, self.prev_pacman, self.path, self.dots, self.enemies))
        for d in D:
            if d in ('h', 'j', 'k', 'l'):
                if self.data[self.pacman + dirs[d]] == '#':
                    return False
            elif d != '.':
                return False
            self.pacman, self.prev_pacman = self.pacman + dirs[d], self.pacman
            self.path.append(d)
            for e in self.enemies:
                e.move(self.prev_pacman)
            if self.conflict() or len(self.path) > self.T:
                print "Game Over!"
                self.show_data()
                print len(self.path), "".join(self.path)
                self.is_quit = True
                return True
            if self.pacman in self.dots:
                self.dots.remove(self.pacman)
            if len(self.dots) == 0:
                print "Game Clear!"
                self.show_data()
                print len(self.path), "".join(self.path)
                self.is_quit = True
                return True
        return True

    def prev(self):
        state = self.states.pop()
        self.pacman = state.pacman
        self.prev_pacman = state.prev_pacman
        self.path = state.path[:]
        self.dots = state.dots[:]
        self.enemies = copy.deepcopy(state.enemies)

    def conflict(self):
        for e in self.enemies:
            if e.pos == self.pacman or (e.pos == self.prev_pacman and e.prev_pos == self.pacman):
                return True
        return False

    def show_data(self):
        data = self.data[:]
        for d in self.dots:
            data[d] = '.'
        for e in self.enemies:
            data[e.pos] = e.char.lower() if e.pos in self.dots else e.char
        enemies = copy.deepcopy(self.enemies)
        for e in enemies: e.move(self.pacman)
        for e in enemies:
            if e.pos in self.dots:
                data[e.pos] = '*'
            else:
                data[e.pos] = '+'
        data[self.pacman] = '@'
        if len(self.path) > 0:
            print "Num of dots (rate): %d (%f)" % (len(self.dots), (self.ndots - len(self.dots)) / float(len(self.path)))
        for i in range(0, self.WH, self.W):
            print "".join(data[i:i+self.W])
        print

def main(args):
    f = file(args[1])
    T = int(f.readline().strip())
    W, H = map(int, f.readline().strip().split())
    data = list("".join([l.strip() for l in f]))
    game = Game(T, W, H, data[:])

    game.show_data()
    path = []
    while True:
        d = raw_input("Move (h,j,k,l,.%s): " % (",number" if path and len(game.path) == 0 else "")).strip()
        if d == 'x': break
        if path and len(game.path) == 0 and (d.isdigit() or (len(d) > 1 and d[0] == '-' and d[1:].isdigit())):
            print len(path[:int(d)]), "".join(path[:int(d)])
            d = path[:int(d)]
        if not game.next(d):
            game.prev()
            continue
        if game.is_quit:
            path = game.path[:]
            print "*" * 50
            game = Game(T, W, H, data[:])
            game.show_data()
            continue
        print len(game.path)
        game.show_data()

if __name__ == "__main__": main(sys.argv)