Google Developer Day 2011のDevQuizをやってみました

Programming

はじめに

Google Developer Day 2011のDevQuizをやってみたので、回答を晒してみます。

Web Game

問題

シンプルな神経衰弱ゲームです。カードはクリックすることでめくることができます。全 64 セットを解くことで問題クリアとなります。


解き方
1枚目のカードを開いてその色を取得するChrome Extensionのサンプルが公開されていましたが、Chrome Extensionは作成せずにJavaScriptコンソール上でJavaScriptを直接実行する、という方法で対応しました。

// -*- coding: utf-8 -*-
/**
   Google Developer Day 2011 DevQuiz - Web Game
   http://gdd-2011-quiz-japan.appspot.com/problems?problem=webgame

   solve_webgame.js

   1. ChromeでWeb Game(http://gdd-2011-quiz-japan.appspot.com/webgame/problem)を開く
   2. Chromeの設定→ツール→JavaScriptコンソール を開く
   3. JavaScriptコンソール の Console を選択し、コンソールウィンドウに下記をコピペして Enter を押す
*/
(function () {
    function getColor(i) {
	var element = document.getElementById('card' + i);
	if (element == null) {
	    return null;
	}
	else {
	    var myevent = document.createEvent('MouseEvents');
	    myevent.initEvent('click', false, true);
	    element.dispatchEvent(myevent);
	    return element.style.backgroundColor;
	}
    }

    function solve(colors) {
	var i, j;
	var size = colors.length;
	var answer = [];
	for (i = 0; i < size; i++) {
	    for (j = 0; j < size; j++) {
		if (i == j)
		    continue;
		if (colors[i] == colors[j]) {
		    answer[i] = j;
		    answer[j] = i;
		    break;
		}
	    }
	}
	return answer;
    }

    function main() {
	var i = 0;
	var color;
	var colors = [];
	while ((color = getColor(i)) != null) {
	    colors[i] = color;
	    i++;
	}
	var answer = solve(colors);
	$("#answer").val(answer.join(","));
	$("#solve").submit();
    }
    
    main();
})();

一人ゲーム

問題

数がいくつか与えられます。なるべく少ない手数で数を全て取り除いてください。
あなたは 1 手で、

  • 全ての数を半分にする（端数は切り捨て）
  • 5 の倍数 (0 を含む) を全て取り除く

のどちらかの操作をすることができます。


解き方
単純な幅優先探索です。

  • 全部5の倍数だったら、「全ての数を半分にする」をしない
  • 5の倍数が1つも無ければ、「5の倍数を全て取り除く」をしない

という枝刈りを入れています。

#!/usr/bin/env ruby
# -*- mode: ruby; coding: utf-8-unix -*- 

# Google Developer Day 2011 DevQuiz - Algorithm
# http://gdd-2011-quiz-japan.appspot.com/problems?problem=algorithm
#
# solve_hitorigame.rb
#
class Problem
  attr_reader :count
  
  def initialize(numbers, count = 0)
    @numbers = numbers
    @count = count
    @num_factor5 = numbers.count { |n| n % 5 == 0 }
  end

  def half
    Problem.new(@numbers.map { |n| n >> 1 }, @count + 1)
  end

  def remove5
    Problem.new(@numbers.delete_if { |n| n % 5 == 0 }, @count + 1)
  end

  def finished?
    @numbers.size == 0
  end

  def all_x5?
    @num_factor5 == @numbers.size
  end

  def has_x5?
    @num_factor5 > 0
  end
end

def parse_question(filename)
  questions = []
  open(filename, 'r') { |f| f.read.lines }.map { |line| line.chomp }.each_with_index { |line, i|
    questions << line.split(/\s/).map { |n| n.to_i }.to_a if i > 0 and i.even?
  }
  questions
end

def breadth_first_search(numbers)
  queue = [Problem.new(numbers)]
  
  while queue.size > 0
    a = queue.shift
    return a.count if a.finished?
    queue << a.half unless a.all_x5?
    queue << a.remove5 if a.has_x5?
  end
  
  raise 'solve: should not reach here'
end

if ARGV.size == 0
  puts "Usage: ruby #{__FILE__} problem_file"
  exit
end

parse_question(ARGV[0]).each { |numbers|
  puts breadth_first_search(numbers)
}

スライドパズル

問題
3×3〜6×6まで、壁ありのスライドパズルを5000問解く、という問題です。

回答
反復深化深さ優先探索をCでゴリゴリ書き*1、マシンパワーに任せて解きました。
タイムアウト時間を60秒に設定し、Core i5 M520 2.40GHz、メモリ4GBのマシンで5プロセス同時に実行して、全体の75%(37.42点)まで回答できました。こんなのでも、たしか数時間で終わったはず。

/* -*- mode: c; coding: utf-8-unix -*- */
/**
   Google Developer Day 2011 DevQuiz - Sliding Puzzle
   http://gdd-2011-quiz-japan.appspot.com/problems?problem=slidingpuzzle

   iterative_deeping_solver.c
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LIMIT 100
#define ANSWER_POSITIONS_SIZE ('Z' - '0')
#define CHAR2IDX(c) (c - '0')
#define ABS(n) ((n < 0) ? -n : n)

const char* ALNUM = "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0";
const int ALNUM_SIZE = 36;

const char DIRECTIONS[] = {'L', 'R', 'U', 'D'};

int glimit = 0;
char groute[LIMIT];
char* gboard_original = NULL;
char* gboard = NULL;
int gwidth = 0;
int gheight = 0;

char* ganswer;
char ganswer_positions_x[ANSWER_POSITIONS_SIZE];
char ganswer_positions_y[ANSWER_POSITIONS_SIZE];

void init_answer(int width, int height, const char* board)
{
  int board_size = width * height;
  ganswer = (char*)malloc(sizeof(char) * (board_size + 1));
  int i;
  for (i = 0; i < board_size; i++) {
    ganswer[i] = (board[i] == '=') ? '=' : ALNUM[i];
  }
  ganswer[board_size - 1] = '0';
  ganswer[board_size] = '\0';

  for (i = 0; i < board_size; i++) {
    int y = (int)(i / width);
    int idx = CHAR2IDX(ALNUM[i]);
    ganswer_positions_y[idx] = y;
    ganswer_positions_x[idx] = i - width * y;
  }
  int idx = CHAR2IDX('0');
  ganswer_positions_y[idx] = height - 1;
  ganswer_positions_x[idx] = width - 1;
}

void release_all()
{
  if (ganswer != NULL) {
    free(ganswer);
  }
  if (gboard != NULL) {
    free(gboard);
  }
}

int distance(char c, int x, int y)
{
  int idx = CHAR2IDX(c);
  x -= ganswer_positions_x[idx];
  y -= ganswer_positions_y[idx];
  return ABS(x) + ABS(y);
}

int total_distance(int width, int height, const char* board)
{
  int dist = 0;
  int i, j;
  for (j = 0; j < height; j++) {
    int jw = j * width;
    for (i = 0; i < width; i++) {
      char c = gboard_original[jw + i];
      if (c != '=') {
	dist += distance(c, i, j);
      }
    }
  }
  return dist;
}

int solve(int count, int x0, int y0, int lower_limit, char prev_dir)
{
  if (count > glimit) {
    return 0;
  }
  if (strcmp(gboard, ganswer) == 0) {
    return 1;
  }

  int i;
  int x1, y1;
  for (i = 0; i < 4; i++) {
    switch (DIRECTIONS[i]) {
    case 'L':
      if (prev_dir == 'R') {
	continue;
      }
      x1 = x0 - 1;
      y1 = y0;
      break;
    case 'R':
      if (prev_dir == 'L') {
	continue;
      }
      x1 = x0 + 1;
      y1 = y0;
      break;
    case 'U':
      if (prev_dir == 'D') {
	continue;
      }
      x1 = x0;
      y1 = y0 - 1;
      break;
    case 'D':
      if (prev_dir == 'U') {
	continue;
      }
      x1 = x0;
      y1 = y0 + 1;
      break;
    default:
      puts("error");
      exit(-1);
      break;
    }

    int pos0 = y0 * gwidth + x0;
    int pos1 = y1 * gwidth + x1;
    if (x1 < 0 || x1 >= gwidth || y1 < 0 || y1 >= gheight || gboard[pos1] == '=') {
      continue;
    }

    groute[count] = DIRECTIONS[i];
    char tmp = gboard[pos1];
    gboard[pos0] = gboard[pos1];
    gboard[pos1] = '0';

    int next_lower = lower_limit - distance(tmp, x1, y1) + distance(tmp, x0, y0);
    if (next_lower + count <= glimit) {
      if (solve(count + 1, x1, y1, next_lower, DIRECTIONS[i])) {
	return 1;
      }
    }

    groute[count] = '\0';
    gboard[pos0] = '0';
    gboard[pos1] = tmp;
  }
  
  return 0;
}

void parse_line(const char* line)
{
  gwidth = line[0] - '0';
  gheight = line[2] - '0';
  gboard_original = (char*)(line + 4);
  gboard = (char*)malloc(sizeof(char) * (gwidth * gheight + 1));
}

int main(int argc, char *argv[])
{
  if (argc != 2) {
    exit(-1);
  }
  parse_line(argv[1]);
  init_answer(gwidth, gheight, gboard_original);

  int x0, y0;
  int i, j;
  for (j = 0; j < gheight; j++) {
    int jw = j * gwidth;
    for (i = 0; i < gwidth; i++) {
      if (gboard_original[jw + i] == '0') {
	x0 = i;
	y0 = j;
	j = gheight;
	break;
      }
    }
  }

  int board_size = gwidth * gheight;
  int lower_limit = total_distance(gwidth, gheight, gboard_original);

  for (i = 0; i < LIMIT; i++) {
    glimit = i;
    memset(groute, 0, LIMIT);
    strcpy(gboard, gboard_original);
    if (solve(0, x0, y0, lower_limit, '0')) {
      puts(groute);
      break;
    }
  }

  release_all();
  
  return 0;
}


実行する際はこんな感じのスクリプトを使用し、プロセスを監視して制限時間を超えたらkillするようにしています。

#!/usr/bin/env ruby
# -*- mode: ruby; coding: utf-8-unix -*- 
# solve_slidingpuzzle.rb

if ARGV.size < 2
  puts "Usage: ruby #{__FILE__} problems.txt output-filename"
  exit
end

result = {}
LIMIT_TIME = 60
CMD = './solver/iterative_deeping_solver'

begin
  lines = nil
  open(ARGV[0], 'r') { |f|
    lines = f.read.lines.map { |m| m.chomp }
    lines.reject! { |line| line !~ /^(\d),(\d),[\d\w=]+$/ }
  }
  
  lines.each { |line|
    begin
      pid = nil
      result[line] = 'Timeout'
      th = Thread.new {
        IO.popen("#{CMD} #{line}") { |io|
          pid = io.pid
          ret = io.gets
          result[line] = ret.chomp unless ret.nil?
        }
      }
      Process.kill('SIGHUP', pid) if th.join(LIMIT_TIME).nil?
      Thread::kill(th)
    rescue => e
      result[line] = e.message
      Thread::list.each { |t| Thread::kill(t) if t != Thread::current }
      GC.start
    end
  }
ensure
  begin
    open(ARGV[1], 'w') { |f|
      lines.each { |line|
        f.puts "#{line}\t#{result[line]}"
      }
    }
  rescue
    lines.each { |line|
      puts "#{line}\t#{result[line]}"
    }
  end
end

スライドパズルはしばらくRubyで単純な幅優先探索→A*アルゴリズム→双方向A*→反復深化深さ優先探索という順に試していたのですが、思ったような速度が出なかったため、Cに切り替えました。するとどうでしょう、いままで全く歯が立たなかった4×4がいとも簡単に解けていく…。やっぱC速いですね。書くのは超めんどくさいですが。
双方向A*版をCで書いて評価関数を工夫する、というアプローチも試したかったのですが、今回は時間切れで断念。気が向いたらやってみます。

結果

合計137.4点でした。最終的なボーダーラインの目安が101点前後らしいので、たぶん大丈夫なはず。

ウォームアップクイズ 40.0点
Web Game 30.0点
一人ゲーム 30.0点
スライドパズル 37.4点
合計 137.4点

まとめ

Google Developer Day 2011のDevQuizを解いてみました。こういうのに挑戦すると、普段使わないようなアルゴリズムを使うことができて楽しいですねー。10月にGoogle Code Jam Japan 2011も開催されるようなので、こちらも挑戦してみようかと思います。

*1:もちろん-O4で最適化