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

はじめに

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で書いて評価関数を工夫する、というアプローチも試したかったのですが、今回は時間切れで断念。気が向いたらやってみます。