見るからに簡単そうなので選択。
実はapkの中にソースが混入しており、Android環境が無くても解けたらしい。えー。

見るからに面白そうなので選択。
前回パックマンをjsで解こうとして痛い目に合ったので、今回は抜かりなく探索が必要なのはCで書くことにした。

先に32回シフトしつつmod5を取ってテーブルを作っておき、後は深さ優先で総当りで探索、見つかり次第それが最短なので探索打ち切り。

正直、gets.split(/ /).eachとか書けないから挫けそうになったけど、動けば100問でも一瞬で溶かすCに惚れ直した。男は黙ってC言語。

1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5typedef unsigned int U;
6
7U _solve(U *q, U n, U rest) {
8  if (rest == 0) return 0;
9
10  U r = 99;
11  if (*q) {
12        r = _solve(q + 1, n, rest & ~*q) + 1;
13        if (r == 1) return r;
14  }
15
16  if (r > 0) {
17        U r0 = _solve(q + 1, n, rest);
18        if (r0 < r) r = r0;
19  }
20
21  return r + 1;
22}
23
24U solve(U *in, U n) {
25  U q[32];
26  for (int j = 0; j < 32; j++) q[j] = 0;
27
28  for (int i = 0; i < n; i++) {
29        for (int j = 0; j < 32; j++) {
30          q[j] |= ((in[i] >> j) % 5) ? 0 : (1 << i);
31        }
32  }
33
34  return _solve(q, n, (1 << n) - 1);
35}
36
37int main() {
38  char buf[256];
39  while (gets(buf)) {
40        int n = atoi(buf);
41        U *in = new U[n];
42
43        int i = 0;
44        gets(buf);
45        char *s = strtok(buf, " ");
46        while (s) {
47          in[i++] = atoi(s);
48          s = strtok(0, " ");
49        }
50
51        printf("%d\n", solve(in, n));
52        delete []in;
53  }
54
55  return 0;
56}

これは大変だった。

基本方針はCでゴリ押し、とした。さっきの一人ゲームと同じ作戦。

まずは単純に深さ優先で枝刈り付けて実装。
これがてんでダメ。テスト用に作った3手で解けるパズルもまともに解けない。なんじゃこりゃと思ったら、同じところでグルグル回って無駄に手数を消耗してた。それじゃ解けるわけがない。

ここでコードを大幅書き直し。評価の高い場面から解いていく幅優先探索にして、同じ場面に当たったら探索を打ち切るようにした。ちなみに評価関数は「深さ＋各板のマンハッタン距離の合計＊４」とした。＊４は適当。倍率が小さいほど深さ重視になり最適解が出やすいけど、答えが出にくくなる、はず。

これで簡単なものは解けるようになったけど、複雑なものだと場面を覚えるメモリが足りずに解けないことが発覚。そもそも重すぎる。そこで、「現在の最高の評価値よりも一定以下の評価値ならその場面の探索を打ち切る」という枝刈りを加えた。これで大分解けそうな感触を掴んだので、仕掛けて就寝。起きたらPCがサスペンドしていて全く進んでいなかったので、休止状態の設定を解除してリトライ。これで72%が解けた。

次は解けなかった問題を、枝刈りを少し甘くして再実行→畑仕事(開墾)→それでも解けなかった問題をさらに枝刈りを甘くして再実行→畑仕事(開墾)→晩御飯を作る→これで84%まで解けた。しかし、これ以上枝狩りを甘くしても時間が無い＆メモリが不足して解けないので投了。

コードは汚いですが勘弁してください。ちなみにgoogleに出したときはもっとdirtyな状態でした…

1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include <set>
5#include <map>
6
7#ifndef CUTBACK_RANGE
8#define CUTBACK_RANGE 24
9#endif
10const int WEIGHT_TD = 4;
11
12typedef unsigned int U;
13
14const char tbl[] = "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0=";
15const int WALL = 36;
16const int ZERO = 35;
17
18inline int abs(int x) { return x > 0 ? x : -x; }
19
20int lim[4], N, w, h;
21int size, qsize;
22int cutback;
23
24class State;
25int stLimit = 20 * 1000 * 1000;
26State *pStateHeap = 0;
27int stPos;
28
29std::set<State*> queue;
30std::multimap<U, State*> collision;
31typedef std::multimap<U, State*>::iterator CollisionIt;
32typedef std::pair<U, State*> CollisionPair;
33
34#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
35class State {
36public:
37  char m[36];
38  char depth;
39  char td; // total (manhattan) distance
40  char x, y; // position of space
41  State* parent;
42  char op; // L, R, U or D
43
44  inline void setMap(const State* st) {
45	for (int i = 0; i < qsize; i++) {
46	  ((int*)m)[i] = ((int*)st->m)[i];
47	}
48  }
49
50  inline bool equal(const State* a) const {
51	for (int i = 0; i < qsize; i++) {
52	  if (((int*)m)[i] != ((int*)a->m)[i])
53		return false;
54	}
55	return true;
56  }
57
58  inline U hash() const {
59	U h = m[0];
60	for (int i = 1; i < size; i++) {
61	  h = ROTATE_LEFT(h, 5) ^ m[i];
62	}
63	return h;
64  }
65
66  inline int diff(int x, int y) const {
67	int c = m[x + y * w];
68	int dx = (c % w) - x;
69	int dy = (c / w) - y;
70	return abs(dx) + abs(dy);
71  }
72
73  inline int eval() const {
74	return depth + td * WEIGHT_TD;
75  }
76
77  void print_answer() const {
78	const State *p = this;
79	char *s = new char[p->depth + 1];
80	int d = p->depth;
81	s[d--] = 0;
82	while (p && p->op) {
83	  s[d--] = p->op;
84	  p = p->parent;
85	}
86	printf("%s\n", s);
87	delete []s;
88  }
89
90  int diff() const {
91	int sum = 0;
92	int k = 0;
93	for (int j = 0; j < h; j++) {
94	  for (int i = 0; i < w; i++, k++) {
95		if (m[k] != WALL && m[k] != ZERO) {
96		  sum += diff(i, j);
97		}
98	  }
99	}
100	return sum;
101  }
102
103  // for priority queue
104  inline bool operator<(const State& a) const {
105	return eval() < a.eval();
106  }	
107};
108
109inline State* alloc() {
110  if (stPos >= stLimit) {
111	return 0;
112  }
113  return &pStateHeap[stPos++];
114}
115
116inline void dealloc() {
117  stPos--;
118}
119
120void prepare(const char *p) {
121  collision.clear();
122  queue.clear();
123
124  cutback = 999999;
125  size = w * h;
126  qsize = (size + 3) / 4;
127
128  stPos = 0;
129  State *st = alloc();
130
131  for (int i = 0; i < size; i++) {
132	st->m[i] =
133	  p[i] == '=' ? WALL :
134	  p[i] == '0' ? ZERO :
135	  p[i] <= '9' ? p[i] - '1' :
136	  p[i] - 'A' + 9;
137	if (st->m[i] == ZERO) {
138	  st->x = i % w;
139	  st->y = i / w;
140	}
141  }
142  for (int i = size; i < sizeof(st->m) / sizeof(*st->m); i++) {
143	st->m[i] = 0xff;
144  }
145
146  st->depth = 0;
147  st->td = st->diff();
148  st->parent = 0;
149  st->op = 0;
150
151  queue.insert(st);
152  collision.insert(CollisionPair(st->hash(),st));
153}
154
155void move(State *st, int dx, int dy) {
156  if (
157	  (st->op == 'R' && dx == -1) ||
158	  (st->op == 'L' && dx ==  1) ||
159	  (st->op == 'D' && dy == -1) ||
160	  (st->op == 'U' && dy ==  1))
161	return;
162
163  int x = st->x;
164  int y = st->y;
165  int rx = x + dx;
166  int ry = y + dy;
167
168  if (rx < 0 || ry < 0 || rx >= w || ry >= h) return;
169
170  int t = st->m[rx + ry * w];
171  if (t == WALL) return;
172
173  State *nst = alloc();
174  if (!nst) return;
175
176  nst->setMap(st);
177
178  nst->m[x + y * w] = t;
179  nst->m[rx + ry * w] = ZERO;
180
181  int d1 = st->diff(rx, ry);
182  int d2 = nst->diff(x, y);
183  int e =  d2 - d1;
184
185  nst->x = rx;
186  nst->y = ry;
187  nst->depth = st->depth + 1;
188  nst->td = st->td + e;
189
190  if (cutback < nst->eval()) return;
191
192  U hs = nst->hash();
193  CollisionIt it = collision.find(hs);
194  bool found = it != collision.end();
195
196  if (found) {
197	found = false;
198	for(; it->first == hs && it != collision.end(); it++) {
199	  if (it->second->equal(nst)) {
200		found = true;
201		break;
202	  }
203	}
204  }
205
206  if ((!found) || (found && ((State*)(it->second))->depth > nst->depth)) {
207	if (found) {
208	  queue.erase(st);
209	  collision.erase(it);
210	}
211	nst->parent = st;
212	nst->op = dx == -1 ? 'L' : dx == 1 ? 'R' : dy == -1 ? 'U' : 'D';
213	queue.insert(nst);
214	collision.insert(CollisionPair(nst->hash(), nst));
215  } else {
216	dealloc();
217  }
218}
219
220void solve() {
221  while (queue.size()) {
222	State *st = *(queue.begin());
223	queue.erase(st);
224
225	if (st->td == 0) {
226	  st->print_answer();
227	  return;
228	}
229
230	int e = st->eval() + CUTBACK_RANGE;
231	if (cutback > e) {
232 	  cutback = e;
233	}
234
235	move(st, -1,  0);
236	move(st,  1,  0);
237	move(st,  0, -1);
238	move(st,  0,  1);
239
240	if (stPos >= stLimit) break;
241  }
242  printf("\n");
243}
244
245int main() {
246  pStateHeap = new State[stLimit];
247
248  scanf("%d %d %d %d", lim + 0, lim + 1, lim + 2, lim + 3);
249  scanf("%d", &N);
250
251  for (int i = 0; i < N; i++) {
252	char m[36];
253	scanf("%d,%d,%s", &w, &h, m);
254	prepare(m);
255	solve();
256	fflush(stdout);
257  }
258
259  return 0;
260}

投了直後の反省点としては

• 既製のset,mapを使うのではなく、内製してメモリ使用量を制御すべきだった
• 要らない場面をgcしてメモリを空ける工夫が必要だった
• なんで俺32bitOS使ってるんだろう…
  • メモリさえあれば解ける問題もあったし、そもそも並列で解けたのに

しかし他の人のコードを見たら様々な事が判明。

• 幅優先ではなく反復深化という手があった！
  • 深さ優先だからキューが要らないし、場面の衝突も気にしない(評価関数で打ち切る)
  • 無駄な計算が多いけど、メモリ爆発しないという点でかなり実用的といえる
• 双方向探索という手も
• 評価関数は上辺や左辺を高めにする
  • 確かに周辺からピースが確定するから、理に適っている
• 評価関数の距離の重み付けに工夫
  • 壁を考慮するとか、距離の1.5乗にするとか

色々勉強になりました。

どうでもいいけど、FPGAで解いたら凄く面白いんではなかろうか。
メモリ帯域を消費しにくい反復深化なら並列化も強烈に効きそうだし。