GDD2011 Devquiz

event

Google Developer Day 2011（http://www.google.com/events/developerday/2011/tokyo/) のDevquizで書いたコードです。

1人ゲーム

与えられる整数は最大で100万（< 2^20）なので、20回連続半分にしたら全て0になって最悪でも21手で終わる。
というわけで2^21通り全部調べれば良い。
実際は2回連続で5の倍数を取り除く操作をすることはないので状態数はもっと少ない。

// g++4.6 -std=c++0x
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <iterator>

using namespace std;

vector<int> input;

template<class T>
void output(const vector<T>& vec){
  for (const T& v : vec) {
    cout << v << " ";
  }
  cout << endl;
}

int solve(){
  set<vector<int>> sts;
  sts.insert(input);
  for (int i = 1; ; ++i) {
    set<vector<int>> next;
    for (const vector<int>& st : sts) {
      vector<int> removed;
      copy_if(st.begin(), st.end(), back_inserter(removed), [](int v){ return v%5 != 0;});
      if (removed.empty()) return i;
      if (removed.size() != st.size()) {
	next.insert(removed);
      }
      vector<int> halved;
      transform(st.begin(), st.end(), back_inserter(halved), [](int v){ return v/2;});
      next.insert(halved);
    }
    swap(sts, next);
  }
}

int main(){
  int T;
  cin >> T;
  for (int i = 0; i < T; ++i) {
    int N;
    cin >> N;
    input.clear();
    for (int j = 0; j < N; ++j) {
      int v;
      cin >> v;
      input.push_back(v);
    }
    cout << solve() << endl;
  }
}

Go!

Go書くのは初めてだったのでリファレンスを見つつ。
次のあたりに引っかかった。

  • 未使用変数があるだけでコンパイルエラー
  • 関数の戻り値を無視するには '_' を使う
  • 整数の拡大変換であっても暗黙には型変換は起きない
  • importしたimage/pngの関数の呼び出し方
  • mapは言語組み込み
import (
	"fmt"
	"io"
	"strings"
	"image"
	ipng "image/png"
)

func ColorToUInt(col image.Color) uint64 {
	r,g,b,_ := col.RGBA()
	return (uint64(r) << 32) + (uint64(g) << 16) + uint64(b)
}

func CountColor(png io.Reader) int {
	img, err := ipng.Decode(png)
	if err != nil {
		return -1
	}
	rect := img.Bounds()
	m := make(map[uint64]int)
	for i := rect.Min.X; i < rect.Max.X; i++ {
		for j := rect.Min.Y; j < rect.Max.Y; j++ {
			m[ColorToUInt(img.At(i,j))] = 1
		}
	}
	return len(m)
}

スライドパズル

方針はこんな感じ。

  • とりあえず簡単な盤面は枝刈りなしの両側探索でやっつける
  • これではちょっと大きい盤面だと全然メモリ足りないので評価関数を入れて枝を刈る
    • 各パネルについて、本来あるべき位置から何マス離れているか * そのパネルの本来あるべき位置が右下のゴールから何マス離れているか を足し合わせる
      • ざっくり言ってゴールより遠い位置から順に埋めていって行ったほうが良いよね、と思って後者の要素を入れた
    • まずゴール側から20数手分を全探索して状態を覚えておいて（部分的な両側探索）、
    • スタート側からは、1手進めるごとに評価関数の良い方から数えて一定個数の状態が含まれるあたりを評価関数の足切り値とする
  • これで4950問くらい。
  • 残ったのを見てみると、壁が通路みたいになっていて何周も回って調整しないといけないようなのが多い
    • 確かにそういうケースは、このアルゴリズムでは通路内の一部だけが正しくはまった状態の局所解に陥ってしまいそう
  • ひとつながりの通路になっている部分は、全部が正しくそろっていないと評価関数がプラスにならないようにした。すると追加で10問ちょっと解けた
  • 残った34問は半手動で。がっかりな感じだが残り1日しかなかったので安全策をとった
  • というわけでなんとか全問正解


その他雑感

  • 5000問もあってパフォーマンスきつそうだなーと思ったので最初からC++で。C++0x使ってみたかったというのもあり。
    • ラムダ式とか拡張forとかサイズが決まっている整数型とかautoとか、良いなぁ
  • 盤面サイズをテンプレートパラメータ化したら1.5倍くらい速くなって驚いた。そんな違うの
  • GUIソルバはC#でさくっと作ったけどやっぱり動いているところを見ると満足度高い。全部テキストベースでやろうとしなくて本当に良かった


GUIソルバの様子


ソースコード（500行強）

// g++4.6 -std=c++0x
#include <array>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <unordered_set>
#include <functional>
#include <cstring>
#include <boost/functional/hash.hpp>
#include <boost/timer.hpp>

using namespace std;

const double TIMER = 250.0;

const int8_t DR[] = {-1, 0, 1, 0};
const int8_t DC[] = {0, 1, 0, -1};
const int8_t WALL = 0x7F;

typedef uint8_t Dir;
const Dir UP = 0;
const Dir RIGHT = 1;
const Dir DOWN = 2;
const Dir LEFT = 3;

int pena[37][6][6];

char dir2char(Dir d) {
  switch(d) {
  case UP:
    return 'U';
  case RIGHT:
    return 'R';
  case DOWN:
    return 'D';
  case LEFT:
    return 'L';
  }
  return 'X';
}

ostream& outputPath(ostream& stm, const std::vector<uint8_t>& path, int turn) {
  for (int i = 0; i < turn; ++i) {
    Dir d = (path[i / 4] >> ((i % 4) * 2)) & 3;
    stm << dir2char(d);
  }
  return stm;
}

ostream& outputPath(ostream& stm, const std::vector<Dir>& path) {
  for (Dir d : path) {
    stm << dir2char(d);
  }
  return stm;
}

template<int HL, int WL>
struct Board{

  Board() {}
  Board(const Board<HL,WL>& o) { memcpy(row, o.row, sizeof(row)); }
  Board<HL,WL>& operator=(const Board<HL,WL>& o) { 
    memcpy(row, o.row, sizeof(row));
    return *this;
  }

  int8_t get(int8_t r, int8_t c) const {
    return row[r][c];
  }
  
  void swap(int8_t r1, int8_t c1, int8_t r2, int8_t c2) {
    std::swap(row[r1][c1], row[r2][c2]);
  }

  size_t hash() const {
    size_t ret = 0;
    for (int i = 0; i < HL; ++i) {
      for (int j = 0; j < WL; ++j) {
	ret *= 17;
	ret ^= (row[i][j] << 3) + row[i][j];
      }
    }
    return ret;
  }

  int8_t row[HL][WL];
};

template<int HL, int WL>
bool operator==(const Board<HL,WL>& l, const Board<HL,WL>& r) { 
  for (int i = 0; i < HL; ++i) {
    for (int j = 0; j < WL; ++j) {
      if (l.row[i][j] != r.row[i][j]) return false;
    }
  }
  return true;
}

template<int HL, int WL>
ostream& operator<<(ostream& stm, const Board<HL,WL>& b) {
  for (int i = 0; i < HL; ++i) {
    for (int j = 0; j < WL; ++j) {
      int v = b.row[i][j];
      if (v == 0x7F) {
	stm << '=';
      } else if (v < 10) {
	stm << static_cast<char>(v + '0');
      } else {
	stm << static_cast<char>(v - 10 + 'A');
      }
    }
    stm << endl;
  }
  return stm;
}

template<int HL, int WL>
struct State{

  State(const string& data) : penalty(0) {
    for (int8_t i = 0; i < HL; ++i) {
      for (int8_t j = 0; j < WL; ++j) {
	int8_t v = char2int(data[i*WL + j]);
	b.row[i][j] = v;
	if (v == 0) {
	  cr = i;
	  cc = j;
	}
	if (v != WALL) {
	  penalty += pena[v][i][j];
	}
      }
    }
  }
  
  State<HL,WL> move(Dir d, int turn) const {
    State<HL,WL> ret(*this);
    ret.cr += DR[d];
    ret.cc += DC[d];
    ret.b.swap(cr, cc, ret.cr, ret.cc);
    if (turn % 4 == 0) {
      ret.path.push_back(d);
    } else {
      ret.path.back() += (d << ((turn % 4) * 2));
    }
    int8_t val = b.get(ret.cr, ret.cc);
    ret.penalty += pena[val][cr][cc] - pena[val][ret.cr][ret.cc];
    return ret;
  }

  Dir getDir(int turn) const {
    return (path[turn / 4]  >> ((turn % 4)) * 2) & 3;
  }

  int getPenalty(const vector<vector<pair<int,int>>>& roads) const {
      int ret = penalty;
      // 通路部分は全部合致していないとだめ
      for (auto road : roads) {
	bool match = true;
	for (auto pos : road) {
	  if (b.get(pos.first, pos.second) != pos.first * WL + pos.second + 1) {
	    match = false;
	    break;
	  }
	}
	if (!match) {
	  ret += road.size() * 40;
	}
      }
      return ret;
    }

  static int8_t char2int(char c){
    if (c == '=') return WALL;
    if ('0' <= c  && c <= '9') return c - '0';
    return c - 'A' + 10;
  }

  ostream& output(ostream& stm, int turn) const {
    stm << "pos: (" << (int)cr << "," << (int)cc << ")" << endl;
    stm << "penalty:" << dec << getPenalty() << endl;
    stm << "board:" << endl << b;
    stm << "path:<";
    outputPath(stm, path, turn);
    stm << ">" << endl;
    return stm;
  }

  Board<HL,WL> b;
  int8_t cr;
  int8_t cc;
  int penalty;
  vector<uint8_t> path; // 1手を2bitに押し込む
};

template<int HL, int WL>
bool operator==(const State<HL,WL>& l, const State<HL,WL>& r) { return l.b == r.b; }

template<int HL, int WL>
class Solver{
  typedef State<HL,WL> MyState;

  struct StateHash : std::unary_function<MyState, size_t> {
    size_t operator()(const MyState& st) const { return boost::hash_value(st.b.row); }
  };

  typedef unordered_set<MyState, StateHash> MySet;

public:
  Solver(const string& data) : prob(data) { calcPenalty(); }

  vector<Dir> solve(){
    boost::timer timer;
    //printPenalty();
    const size_t LIMIT_COUNT = 200000; // メモリと時間のバランスを見て変えつつ試す
    const vector<Dir> giveup;
    vector<MyState> statesS;
    statesS.push_back(MyState(prob));
    array<MySet, 10000> usedS;
    usedS[statesS[0].getPenalty(roads)].insert(statesS[0]);
    vector<MyState> statesG;
    statesG.push_back(createGoal());
    MySet usedG;
    int gTurn = 0;
    for (; gTurn < 50; ++gTurn) {
      vector<MyState> nextG;
      for (const MyState& st : statesG) {
	for (int d = 0; d < 4; ++d) {
	  if (!canMove(st, d, gTurn)) continue;
	  MyState ns = st.move(d, gTurn);
	  nextG.push_back(ns);
	}
      }
      if (nextG.size() > LIMIT_COUNT*4) {
	usedG.insert(nextG.begin(), nextG.end());
	break;
      }
      swap(statesG, nextG);
    }
    if (usedG.empty()){
      --gTurn;
      usedG.insert(statesG.begin(), statesG.end());
    }
    statesG.clear();

    int turn = 0;
    int cutoff = 10000;
    while(turn < 300) {
      cout << "turn:" << turn << " " << timer.elapsed() << endl;
//       int counter = 0;
      int maxPenalty = 0;
      vector<MyState> nextS;
      for (const MyState& st : statesS) {
	for (int d = 0; d < 4; ++d) {
	  if (!canMove(st, d, turn)) continue;
	  MyState ns = st.move(d, turn);
	  const int penalty = ns.getPenalty(roads);
	  if (penalty >= cutoff) continue;
	  if (usedS[penalty].count(ns) != 0) continue;
	  if (usedG.count(ns) != 0) {
	    vector<Dir> ret;
	    for (int i = 0; i <= turn; ++i) {
	      ret.push_back(ns.getDir(i));
	    }
	    auto gside = usedG.find(ns);
	    for (int i = gTurn; i >= 0; --i) {
	      ret.push_back((gside->getDir(i) + 2) % 4);
	    }
	    return ret;
	  }
	  nextS.push_back(ns);
	  usedS[penalty].insert(ns);
	  maxPenalty = max(maxPenalty, penalty);
	}
// 	++counter;
// 	if ((counter & 0x1FFF) == 0) {
// 	  size_t sum = 0;
// 	  for (int j = 0; j <= maxPenalty; ++j) {
// 	    sum += usedS[j].size();
// 	  }
// 	  if (sum > LIMIT_COUNT * 2) {
// 	    break;
// 	  }
// 	}
      }
      if(turn > 10) {
	size_t sum = 0;
	for (int i = 0; i <= maxPenalty; ++i) {
	  sum += usedS[i].size();
	  if (sum > LIMIT_COUNT){
	    for (int j = i+1; j <= maxPenalty; ++j) {
	      usedS[j].clear();
	    }
	    cutoff = i + 5;
	    break;
	  }
	}
      }
      swap(statesS, nextS);
      if (statesS.empty() || timer.elapsed() > TIMER) {
	return giveup;
      }
      //sort(statesS.begin(), statesS.end(), [](const MyState& l, const MyState& r){return l.penalty < r.penalty;});
      ++turn;

      /*
      if (turn == 1) {
	for (int i = 0; i < 100; ++i) {
	  printf("%5d ", i);
	}
	printf("\n");
      }
      printf("cutoff:%3d", cutoff);
      for (int i = 0; i <= maxPenalty; ++i) {
	printf("%5d ", static_cast<int>(usedS[i].size()));
      }
      printf("\n");
      */
    }
    return giveup;
  }

  private:
  const string prob;
  vector<vector<pair<int,int>>> roads;

  bool canMove(const MyState& st, Dir d, int turn) {
    if (turn != 0 && abs(st.getDir(turn - 1) - d) == 2) return false; 
    int8_t nr = st.cr + DR[d];
    int8_t nc = st.cc + DC[d];
    if (nr == -1 || nr == HL || nc == -1 || nc == WL) return false;
    if (st.b.get(nr, nc) == WALL) return false;
    return true;
  }

  MyState createGoal(){
    MyState state(prob);
    int8_t lr = 0;
    int8_t lc = 0;
    for (int8_t i = 0; i < HL; ++i) {
      for (int8_t j = 0; j < WL; ++j) {
	int v = prob[i*WL + j];
	if (v != '=') {
	  lr = i;
	  lc = j;
	  state.b.row[i][j] = i * WL + j + 1;
	}else {
	  state.b.row[i][j] = WALL;
	}
      }
    }
    state.b.row[lr][lc] = 0;
    state.cr = lr;
    state.cc = lc;
    state.penalty = 0;
    return state;
  }

  void printPenalty(){
    for (int i = 0; i < HL * WL; ++i) {
      for (int j = 0; j < HL; ++j) {
	for (int k = 0; k < WL; ++k) {
	  cout << pena[i+1][j][k] << ' ';
	}
	cout << endl;
      }
    }
  }

  void calcPenalty(){
    memset(pena, 0, sizeof(pena));
    int lastPos = 0;
    for (int i = 1; i <= HL * WL; ++i) {
      if (prob[i - 1] == '=') continue;
      int r = (i-1) / WL;
      int c = (i-1) % WL;
      lastPos = i;
      vector<pair<int,int>> pos;
      pos.push_back(make_pair(r,c));
      bool visited[6][6] = {};
      visited[r][c] = true;
      int turn = 1;
      while(!pos.empty()) {
	vector<pair<int,int>> next;
	for (const pair<int,int>& p: pos) {
	  for (int j = 0; j < 4; ++j) {
	    int nr = p.first + DR[j];
	    int nc = p.second + DC[j];
	    if (nr == -1 || nr == HL || nc == -1 || nc == WL
		|| visited[nr][nc] || prob[nr*WL+nc] == '=') continue;
	    visited[nr][nc] = true;
	    pena[i][nr][nc] = turn;
	    next.push_back(make_pair(nr, nc));
	  }
	}
	++turn;
	swap(pos, next);
      }
    }
    for (int i = 1; i < lastPos; ++i) {
      if (prob[i - 1] == '=') continue;
      int r = (i-1) / WL;
      int c = (i-1) % WL;
      double prod = pow(pena[lastPos][r][c], 1);
      for (int j = 0; j < HL; ++j) {
	for (int k = 0; k < WL; ++k) {
	  pena[i][j][k] = (int)(pena[i][j][k] * prod);
	}
      }
    }

    // 通路になっている部分は別扱い
    bool visited[HL][WL] = {};
    for (int i = 0; i < HL; ++i) {
      for (int j = 0; j < WL; ++j) {
	if (!visited[i][j] && isRoad(i,j)) {
	  visited[i][j] = true;
	  vector<pair<int,int>> list;
	  vector<pair<int,int>> pos;
	  pos.push_back(make_pair(i,j));
	  list.push_back(pos[0]);
	  while(!pos.empty()) {
	    vector<pair<int,int>> nextPos;
	    for (auto p : pos) {
	      for (int k = 0; k < 4; ++k) {
		int nr = p.first + DR[k];
		int nc = p.second + DC[k];
		if (nr == -1 || nr == HL || nc == -1 || nc == WL || prob[nr*WL + nc] == '=') continue;
		if (visited[nr][nc]) continue;
		visited[nr][nc] = true;
		if(isTwoWall(nr,nc)) {
		  nextPos.push_back(make_pair(nr, nc));
		  list.push_back(make_pair(nr, nc));
		}
	      }
	    }
	    swap(pos, nextPos);
	  }
	  roads.push_back(list);
	  for (auto p : list) {
	    for (int r = 0; r < HL; ++r) {
	      for (int c = 0; c < WL; ++c) {
		pena[p.first * WL + p.second + 1][r][c] = 0;
	      }
	    }
	  }
	}
      }
    }
  }
  
  bool isRoad(int r, int c) const {
    bool tWall = r == 0 || prob[(r-1)*WL+c] == '=';
    bool bWall = r == HL-1 || prob[(r+1)*WL+c] == '=';
    bool lWall = c == 0 || prob[r*WL+c-1] == '=';
    bool rWall = c == WL-1 || prob[r*WL+c+1] == '=';
    return (tWall && bWall) || (lWall && rWall);
  }

  bool isTwoWall(int r, int c) const {
    int count = 0;
    for (int i = 0; i < 4; ++i) {
      int nr = r + DR[i];
      int nc = c + DC[i];
      if (nr == -1 || nr == HL || nc == -1 || nc == WL || prob[nr*WL + nc] == '=') ++count;
    }
    return count == 2;
  }

};

template<int HL, int WL>
vector<Dir> solve(const string& data) {
  return Solver<HL,WL>(data).solve();
}

int main(){
  cout.setf(ios::uppercase);
  int LX,RX,UX,DX,N;
  cin >> LX >> RX >> UX >> DX >> N;
  vector<string> result(N);
  {
    // 解答済みの問題をスキップするため
    ifstream result_file("result.txt");
    char buf[512] = {};
    for (int i = 0; i < N; ++i) {
      result_file.getline(buf, sizeof(buf));
      result[i] = string(buf);
    }
  }
  string bufs;
  for (int i = 0; i < N; ++i) {
    cin >> bufs;
    if (result[i].empty()) {
      boost::timer timer;
      int w = bufs[0] - '0';
      int h = bufs[2] - '0';
      string data(bufs.begin() + 4, bufs.end());
      vector<Dir> answer;
      if (h == 3) {
	if (w == 3) answer = solve<3,3>(data);
	else if (w == 4) answer = solve<3,4>(data);
	else if (w == 5) answer = solve<3,5>(data);
	else if (w == 6) answer = solve<3,6>(data);
      } else if(h == 4){
	if (w == 3) answer = solve<4,3>(data);
	else if (w == 4) answer = solve<4,4>(data);
	else if (w == 5) answer = solve<4,5>(data);
	else if (w == 6) answer = solve<4,6>(data);
      } else if(h == 5){
	if (w == 3) answer = solve<5,3>(data);
	else if (w == 4) answer = solve<5,4>(data);
	else if (w == 5) answer = solve<5,5>(data);
	else if (w == 6) answer = solve<5,6>(data);
      } else if(h == 6){
	if (w == 3) answer = solve<6,3>(data);
	else if (w == 4) answer = solve<6,4>(data);
	else if (w == 5) answer = solve<6,5>(data);
	else if (w == 6) answer = solve<6,6>(data);
      }
      cout << i << ":" << timer.elapsed() << endl;
      outputPath(cout, answer) << endl;
    } else {
//       cout << i << ":skip" << endl;
//       cout << result[i] << endl;
    }
  }

}