diff options
author | Franklin Wei <git@fwei.tk> | 2017-04-29 18:21:56 -0400 |
---|---|---|
committer | Franklin Wei <git@fwei.tk> | 2017-04-29 18:24:42 -0400 |
commit | 881746789a489fad85aae8317555f73dbe261556 (patch) | |
tree | cec2946362c4698c8db3c10f3242ef546c2c22dd /apps/plugins/puzzles/src/divvy.c | |
parent | 03dd4b92be7dcd5c8ab06da3810887060e06abd5 (diff) | |
download | rockbox-881746789a489fad85aae8317555f73dbe261556.tar.gz rockbox-881746789a489fad85aae8317555f73dbe261556.zip |
puzzles: refactor and resync with upstream
This brings puzzles up-to-date with upstream revision
2d333750272c3967cfd5cd3677572cddeaad5932, though certain changes made
by me, including cursor-only Untangle and some compilation fixes
remain. Upstream code has been moved to its separate subdirectory and
future syncs can be done by simply copying over the new sources.
Change-Id: Ia6506ca5f78c3627165ea6791d38db414ace0804
Diffstat (limited to 'apps/plugins/puzzles/src/divvy.c')
-rw-r--r-- | apps/plugins/puzzles/src/divvy.c | 781 |
1 files changed, 781 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/divvy.c b/apps/plugins/puzzles/src/divvy.c new file mode 100644 index 0000000000..517e3ddbb0 --- /dev/null +++ b/apps/plugins/puzzles/src/divvy.c | |||
@@ -0,0 +1,781 @@ | |||
1 | /* | ||
2 | * Library code to divide up a rectangle into a number of equally | ||
3 | * sized ominoes, in a random fashion. | ||
4 | * | ||
5 | * Could use this for generating solved grids of | ||
6 | * http://www.nikoli.co.jp/ja/puzzles/block_puzzle/ | ||
7 | * or for generating the playfield for Jigsaw Sudoku. | ||
8 | */ | ||
9 | |||
10 | /* | ||
11 | * This code is restricted to simply connected solutions: that is, | ||
12 | * no single polyomino may completely surround another (not even | ||
13 | * with a corner visible to the outside world, in the sense that a | ||
14 | * 7-omino can `surround' a single square). | ||
15 | * | ||
16 | * It's tempting to think that this is a natural consequence of | ||
17 | * all the ominoes being the same size - after all, a division of | ||
18 | * anything into 7-ominoes must necessarily have all of them | ||
19 | * simply connected, because if one was not then the 1-square | ||
20 | * space in the middle could not be part of any 7-omino - but in | ||
21 | * fact, for sufficiently large k, it is perfectly possible for a | ||
22 | * k-omino to completely surround another k-omino. A simple | ||
23 | * example is this one with two 25-ominoes: | ||
24 | * | ||
25 | * +--+--+--+--+--+--+--+ | ||
26 | * | | | ||
27 | * + +--+--+--+--+--+ + | ||
28 | * | | | | | ||
29 | * + + + + | ||
30 | * | | | | | ||
31 | * + + + +--+ | ||
32 | * | | | | | ||
33 | * + + + +--+ | ||
34 | * | | | | | ||
35 | * + + + + | ||
36 | * | | | | | ||
37 | * + +--+--+--+--+--+ + | ||
38 | * | | | ||
39 | * +--+--+--+--+--+--+--+ | ||
40 | * | ||
41 | * I claim the smallest k which can manage this is 23. More | ||
42 | * formally: | ||
43 | * | ||
44 | * If a k-omino P is completely surrounded by another k-omino Q, | ||
45 | * such that every edge of P borders on Q, then k >= 23. | ||
46 | * | ||
47 | * Proof: | ||
48 | * | ||
49 | * It's relatively simple to find the largest _rectangle_ a | ||
50 | * k-omino can enclose. So I'll construct my proof in two parts: | ||
51 | * firstly, show that no 22-omino or smaller can enclose a | ||
52 | * rectangle as large as itself, and secondly, show that no | ||
53 | * polyomino can enclose a larger non-rectangle than a rectangle. | ||
54 | * | ||
55 | * The first of those claims: | ||
56 | * | ||
57 | * To surround an m x n rectangle, a polyomino must have 2m | ||
58 | * squares along the two m-sides of the rectangle, 2n squares | ||
59 | * along the two n-sides, and must fill in at least three of the | ||
60 | * corners in order to be connected. Thus, 2(m+n)+3 <= k. We wish | ||
61 | * to find the largest value of mn subject to that constraint, and | ||
62 | * it's clear that this is achieved when m and n are as close to | ||
63 | * equal as possible. (If they aren't, WLOG suppose m < n; then | ||
64 | * (m+1)(n-1) = mn + n - m - 1 >= mn, with equality only when | ||
65 | * m=n-1.) | ||
66 | * | ||
67 | * So the area of the largest rectangle which can be enclosed by a | ||
68 | * k-omino is given by floor(k'/2) * ceil(k'/2), where k' = | ||
69 | * (k-3)/2. This is a monotonic function in k, so there will be a | ||
70 | * unique point at which it goes from being smaller than k to | ||
71 | * being larger than k. That point is between 22 (maximum area 20) | ||
72 | * and 23 (maximum area 25). | ||
73 | * | ||
74 | * The second claim: | ||
75 | * | ||
76 | * Suppose we have an inner polyomino P surrounded by an outer | ||
77 | * polyomino Q. I seek to show that if P is non-rectangular, then | ||
78 | * P is also non-maximal, in the sense that we can transform P and | ||
79 | * Q into a new pair of polyominoes in which P is larger and Q is | ||
80 | * at most the same size. | ||
81 | * | ||
82 | * Consider walking along the boundary of P in a clockwise | ||
83 | * direction. (We may assume, of course, that there is only _one_ | ||
84 | * boundary of P, i.e. P has no hole in the middle. If it does | ||
85 | * have a hole in the middle, it's _trivially_ non-maximal because | ||
86 | * we can just fill the hole in!) Our walk will take us along many | ||
87 | * edges between squares; sometimes we might turn left, and | ||
88 | * certainly sometimes we will turn right. Always there will be a | ||
89 | * square of P on our right, and a square of Q on our left. | ||
90 | * | ||
91 | * The net angle through which we turn during the entire walk must | ||
92 | * add up to 360 degrees rightwards. So if there are no left | ||
93 | * turns, then we must turn right exactly four times, meaning we | ||
94 | * have described a rectangle. Hence, if P is _not_ rectangular, | ||
95 | * then there must have been a left turn at some point. A left | ||
96 | * turn must mean we walk along two edges of the same square of Q. | ||
97 | * | ||
98 | * Thus, there is some square X in Q which is adjacent to two | ||
99 | * diagonally separated squares in P. Let us call those two | ||
100 | * squares N and E; let us refer to the other two neighbours of X | ||
101 | * as S and W; let us refer to the other mutual neighbour of S and | ||
102 | * W as D; and let us refer to the other mutual neighbour of S and | ||
103 | * E as Y. In other words, we have named seven squares, arranged | ||
104 | * thus: | ||
105 | * | ||
106 | * N | ||
107 | * W X E | ||
108 | * D S Y | ||
109 | * | ||
110 | * where N and E are in P, and X is in Q. | ||
111 | * | ||
112 | * Clearly at least one of W and S must be in Q (because otherwise | ||
113 | * X would not be connected to any other square in Q, and would | ||
114 | * hence have to be the whole of Q; and evidently if Q were a | ||
115 | * 1-omino it could not enclose _anything_). So we divide into | ||
116 | * cases: | ||
117 | * | ||
118 | * If both W and S are in Q, then we take X out of Q and put it in | ||
119 | * P, which does not expose any edge of P. If this disconnects Q, | ||
120 | * then we can reconnect it by adding D to Q. | ||
121 | * | ||
122 | * If only one of W and S is in Q, then wlog let it be W. If S is | ||
123 | * in _P_, then we have a particularly easy case: we can simply | ||
124 | * take X out of Q and add it to P, and this cannot disconnect X | ||
125 | * since X was a leaf square of Q. | ||
126 | * | ||
127 | * Our remaining case is that W is in Q and S is in neither P nor | ||
128 | * Q. Again we take X out of Q and put it in P; we also add S to | ||
129 | * Q. This ensures we do not expose an edge of P, but we must now | ||
130 | * prove that S is adjacent to some other existing square of Q so | ||
131 | * that we haven't disconnected Q by adding it. | ||
132 | * | ||
133 | * To do this, we recall that we walked along the edge XE, and | ||
134 | * then turned left to walk along XN. So just before doing all | ||
135 | * that, we must have reached the corner XSE, and we must have | ||
136 | * done it by walking along one of the three edges meeting at that | ||
137 | * corner which are _not_ XE. It can't have been SY, since S would | ||
138 | * then have been on our left and it isn't in Q; and it can't have | ||
139 | * been XS, since S would then have been on our right and it isn't | ||
140 | * in P. So it must have been YE, in which case Y was on our left, | ||
141 | * and hence is in Q. | ||
142 | * | ||
143 | * So in all cases we have shown that we can take X out of Q and | ||
144 | * add it to P, and add at most one square to Q to restore the | ||
145 | * containment and connectedness properties. Hence, we can keep | ||
146 | * doing this until we run out of left turns and P becomes | ||
147 | * rectangular. [] | ||
148 | * | ||
149 | * ------------ | ||
150 | * | ||
151 | * Anyway, that entire proof was a bit of a sidetrack. The point | ||
152 | * is, although constructions of this type are possible for | ||
153 | * sufficiently large k, divvy_rectangle() will never generate | ||
154 | * them. This could be considered a weakness for some purposes, in | ||
155 | * the sense that we can't generate all possible divisions. | ||
156 | * However, there are many divisions which we are highly unlikely | ||
157 | * to generate anyway, so in practice it probably isn't _too_ bad. | ||
158 | * | ||
159 | * If I wanted to fix this issue, I would have to make the rules | ||
160 | * more complicated for determining when a square can safely be | ||
161 | * _removed_ from a polyomino. Adding one becomes easier (a square | ||
162 | * may be added to a polyomino iff it is 4-adjacent to any square | ||
163 | * currently part of the polyomino, and the current test for loop | ||
164 | * formation may be dispensed with), but to determine which | ||
165 | * squares may be removed we must now resort to analysis of the | ||
166 | * overall structure of the polyomino rather than the simple local | ||
167 | * properties we can currently get away with measuring. | ||
168 | */ | ||
169 | |||
170 | /* | ||
171 | * Possible improvements which might cut the fail rate: | ||
172 | * | ||
173 | * - instead of picking one omino to extend in an iteration, try | ||
174 | * them all in succession (in a randomised order) | ||
175 | * | ||
176 | * - (for real rigour) instead of bfsing over ominoes, bfs over | ||
177 | * the space of possible _removed squares_. That way we aren't | ||
178 | * limited to randomly choosing a single square to remove from | ||
179 | * an omino and failing if that particular square doesn't | ||
180 | * happen to work. | ||
181 | * | ||
182 | * However, I don't currently think it's necessary to do either of | ||
183 | * these, because the failure rate is already low enough to be | ||
184 | * easily tolerable, under all circumstances I've been able to | ||
185 | * think of. | ||
186 | */ | ||
187 | |||
188 | #include <assert.h> | ||
189 | #include <stdio.h> | ||
190 | #include <stdlib.h> | ||
191 | #include <stddef.h> | ||
192 | |||
193 | #include "puzzles.h" | ||
194 | |||
195 | /* | ||
196 | * Subroutine which implements a function used in computing both | ||
197 | * whether a square can safely be added to an omino, and whether | ||
198 | * it can safely be removed. | ||
199 | * | ||
200 | * We enumerate the eight squares 8-adjacent to this one, in | ||
201 | * cyclic order. We go round that loop and count the number of | ||
202 | * times we find a square owned by the target omino next to one | ||
203 | * not owned by it. We then return success iff that count is 2. | ||
204 | * | ||
205 | * When adding a square to an omino, this is precisely the | ||
206 | * criterion which tells us that adding the square won't leave a | ||
207 | * hole in the middle of the omino. (If it did, then things get | ||
208 | * more complicated; see above.) | ||
209 | * | ||
210 | * When removing a square from an omino, the _same_ criterion | ||
211 | * tells us that removing the square won't disconnect the omino. | ||
212 | * (This only works _because_ we've ensured the omino is simply | ||
213 | * connected.) | ||
214 | */ | ||
215 | static int addremcommon(int w, int h, int x, int y, int *own, int val) | ||
216 | { | ||
217 | int neighbours[8]; | ||
218 | int dir, count; | ||
219 | |||
220 | for (dir = 0; dir < 8; dir++) { | ||
221 | int dx = ((dir & 3) == 2 ? 0 : dir > 2 && dir < 6 ? +1 : -1); | ||
222 | int dy = ((dir & 3) == 0 ? 0 : dir < 4 ? -1 : +1); | ||
223 | int sx = x+dx, sy = y+dy; | ||
224 | |||
225 | if (sx < 0 || sx >= w || sy < 0 || sy >= h) | ||
226 | neighbours[dir] = -1; /* outside the grid */ | ||
227 | else | ||
228 | neighbours[dir] = own[sy*w+sx]; | ||
229 | } | ||
230 | |||
231 | /* | ||
232 | * To begin with, check 4-adjacency. | ||
233 | */ | ||
234 | if (neighbours[0] != val && neighbours[2] != val && | ||
235 | neighbours[4] != val && neighbours[6] != val) | ||
236 | return FALSE; | ||
237 | |||
238 | count = 0; | ||
239 | |||
240 | for (dir = 0; dir < 8; dir++) { | ||
241 | int next = (dir + 1) & 7; | ||
242 | int gotthis = (neighbours[dir] == val); | ||
243 | int gotnext = (neighbours[next] == val); | ||
244 | |||
245 | if (gotthis != gotnext) | ||
246 | count++; | ||
247 | } | ||
248 | |||
249 | return (count == 2); | ||
250 | } | ||
251 | |||
252 | /* | ||
253 | * w and h are the dimensions of the rectangle. | ||
254 | * | ||
255 | * k is the size of the required ominoes. (So k must divide w*h, | ||
256 | * of course.) | ||
257 | * | ||
258 | * The returned result is a w*h-sized dsf. | ||
259 | * | ||
260 | * In both of the above suggested use cases, the user would | ||
261 | * probably want w==h==k, but that isn't a requirement. | ||
262 | */ | ||
263 | static int *divvy_internal(int w, int h, int k, random_state *rs) | ||
264 | { | ||
265 | int *order, *queue, *tmp, *own, *sizes, *addable, *removable, *retdsf; | ||
266 | int wh = w*h; | ||
267 | int i, j, n, x, y, qhead, qtail; | ||
268 | |||
269 | n = wh / k; | ||
270 | assert(wh == k*n); | ||
271 | |||
272 | order = snewn(wh, int); | ||
273 | tmp = snewn(wh, int); | ||
274 | own = snewn(wh, int); | ||
275 | sizes = snewn(n, int); | ||
276 | queue = snewn(n, int); | ||
277 | addable = snewn(wh*4, int); | ||
278 | removable = snewn(wh, int); | ||
279 | |||
280 | /* | ||
281 | * Permute the grid squares into a random order, which will be | ||
282 | * used for iterating over the grid whenever we need to search | ||
283 | * for something. This prevents directional bias and arranges | ||
284 | * for the answer to be non-deterministic. | ||
285 | */ | ||
286 | for (i = 0; i < wh; i++) | ||
287 | order[i] = i; | ||
288 | shuffle(order, wh, sizeof(*order), rs); | ||
289 | |||
290 | /* | ||
291 | * Begin by choosing a starting square at random for each | ||
292 | * omino. | ||
293 | */ | ||
294 | for (i = 0; i < wh; i++) { | ||
295 | own[i] = -1; | ||
296 | } | ||
297 | for (i = 0; i < n; i++) { | ||
298 | own[order[i]] = i; | ||
299 | sizes[i] = 1; | ||
300 | } | ||
301 | |||
302 | /* | ||
303 | * Now repeatedly pick a random omino which isn't already at | ||
304 | * the target size, and find a way to expand it by one. This | ||
305 | * may involve stealing a square from another omino, in which | ||
306 | * case we then re-expand that omino, forming a chain of | ||
307 | * square-stealing which terminates in an as yet unclaimed | ||
308 | * square. Hence every successful iteration around this loop | ||
309 | * causes the number of unclaimed squares to drop by one, and | ||
310 | * so the process is bounded in duration. | ||
311 | */ | ||
312 | while (1) { | ||
313 | |||
314 | #ifdef DIVVY_DIAGNOSTICS | ||
315 | { | ||
316 | int x, y; | ||
317 | printf("Top of loop. Current grid:\n"); | ||
318 | for (y = 0; y < h; y++) { | ||
319 | for (x = 0; x < w; x++) | ||
320 | printf("%3d", own[y*w+x]); | ||
321 | printf("\n"); | ||
322 | } | ||
323 | } | ||
324 | #endif | ||
325 | |||
326 | /* | ||
327 | * Go over the grid and figure out which squares can | ||
328 | * safely be added to, or removed from, each omino. We | ||
329 | * don't take account of other ominoes in this process, so | ||
330 | * we will often end up knowing that a square can be | ||
331 | * poached from one omino by another. | ||
332 | * | ||
333 | * For each square, there may be up to four ominoes to | ||
334 | * which it can be added (those to which it is | ||
335 | * 4-adjacent). | ||
336 | */ | ||
337 | for (y = 0; y < h; y++) { | ||
338 | for (x = 0; x < w; x++) { | ||
339 | int yx = y*w+x; | ||
340 | int curr = own[yx]; | ||
341 | int dir; | ||
342 | |||
343 | if (curr < 0) { | ||
344 | removable[yx] = FALSE; /* can't remove if not owned! */ | ||
345 | } else if (sizes[curr] == 1) { | ||
346 | removable[yx] = TRUE; /* can always remove a singleton */ | ||
347 | } else { | ||
348 | /* | ||
349 | * See if this square can be removed from its | ||
350 | * omino without disconnecting it. | ||
351 | */ | ||
352 | removable[yx] = addremcommon(w, h, x, y, own, curr); | ||
353 | } | ||
354 | |||
355 | for (dir = 0; dir < 4; dir++) { | ||
356 | int dx = (dir == 0 ? -1 : dir == 1 ? +1 : 0); | ||
357 | int dy = (dir == 2 ? -1 : dir == 3 ? +1 : 0); | ||
358 | int sx = x + dx, sy = y + dy; | ||
359 | int syx = sy*w+sx; | ||
360 | |||
361 | addable[yx*4+dir] = -1; | ||
362 | |||
363 | if (sx < 0 || sx >= w || sy < 0 || sy >= h) | ||
364 | continue; /* no omino here! */ | ||
365 | if (own[syx] < 0) | ||
366 | continue; /* also no omino here */ | ||
367 | if (own[syx] == own[yx]) | ||
368 | continue; /* we already got one */ | ||
369 | if (!addremcommon(w, h, x, y, own, own[syx])) | ||
370 | continue; /* would non-simply connect the omino */ | ||
371 | |||
372 | addable[yx*4+dir] = own[syx]; | ||
373 | } | ||
374 | } | ||
375 | } | ||
376 | |||
377 | for (i = j = 0; i < n; i++) | ||
378 | if (sizes[i] < k) | ||
379 | tmp[j++] = i; | ||
380 | if (j == 0) | ||
381 | break; /* all ominoes are complete! */ | ||
382 | j = tmp[random_upto(rs, j)]; | ||
383 | #ifdef DIVVY_DIAGNOSTICS | ||
384 | printf("Trying to extend %d\n", j); | ||
385 | #endif | ||
386 | |||
387 | /* | ||
388 | * So we're trying to expand omino j. We breadth-first | ||
389 | * search out from j across the space of ominoes. | ||
390 | * | ||
391 | * For bfs purposes, we use two elements of tmp per omino: | ||
392 | * tmp[2*i+0] tells us which omino we got to i from, and | ||
393 | * tmp[2*i+1] numbers the grid square that omino stole | ||
394 | * from us. | ||
395 | * | ||
396 | * This requires that wh (the size of tmp) is at least 2n, | ||
397 | * i.e. k is at least 2. There would have been nothing to | ||
398 | * stop a user calling this function with k=1, but if they | ||
399 | * did then we wouldn't have got to _here_ in the code - | ||
400 | * we would have noticed above that all ominoes were | ||
401 | * already at their target sizes, and terminated :-) | ||
402 | */ | ||
403 | assert(wh >= 2*n); | ||
404 | for (i = 0; i < n; i++) | ||
405 | tmp[2*i] = tmp[2*i+1] = -1; | ||
406 | qhead = qtail = 0; | ||
407 | queue[qtail++] = j; | ||
408 | tmp[2*j] = tmp[2*j+1] = -2; /* special value: `starting point' */ | ||
409 | |||
410 | while (qhead < qtail) { | ||
411 | int tmpsq; | ||
412 | |||
413 | j = queue[qhead]; | ||
414 | |||
415 | /* | ||
416 | * We wish to expand omino j. However, we might have | ||
417 | * got here by omino j having a square stolen from it, | ||
418 | * so first of all we must temporarily mark that | ||
419 | * square as not belonging to j, so that our adjacency | ||
420 | * calculations don't assume j _does_ belong to us. | ||
421 | */ | ||
422 | tmpsq = tmp[2*j+1]; | ||
423 | if (tmpsq >= 0) { | ||
424 | assert(own[tmpsq] == j); | ||
425 | own[tmpsq] = -3; | ||
426 | } | ||
427 | |||
428 | /* | ||
429 | * OK. Now begin by seeing if we can find any | ||
430 | * unclaimed square into which we can expand omino j. | ||
431 | * If we find one, the entire bfs terminates. | ||
432 | */ | ||
433 | for (i = 0; i < wh; i++) { | ||
434 | int dir; | ||
435 | |||
436 | if (own[order[i]] != -1) | ||
437 | continue; /* this square is claimed */ | ||
438 | |||
439 | /* | ||
440 | * Special case: if our current omino was size 1 | ||
441 | * and then had a square stolen from it, it's now | ||
442 | * size zero, which means it's valid to `expand' | ||
443 | * it into _any_ unclaimed square. | ||
444 | */ | ||
445 | if (sizes[j] == 1 && tmpsq >= 0) | ||
446 | break; /* got one */ | ||
447 | |||
448 | /* | ||
449 | * Failing that, we must do the full test for | ||
450 | * addability. | ||
451 | */ | ||
452 | for (dir = 0; dir < 4; dir++) | ||
453 | if (addable[order[i]*4+dir] == j) { | ||
454 | /* | ||
455 | * We know this square is addable to this | ||
456 | * omino with the grid in the state it had | ||
457 | * at the top of the loop. However, we | ||
458 | * must now check that it's _still_ | ||
459 | * addable to this omino when the omino is | ||
460 | * missing a square. To do this it's only | ||
461 | * necessary to re-check addremcommon. | ||
462 | */ | ||
463 | if (!addremcommon(w, h, order[i]%w, order[i]/w, | ||
464 | own, j)) | ||
465 | continue; | ||
466 | break; | ||
467 | } | ||
468 | if (dir == 4) | ||
469 | continue; /* we can't add this square to j */ | ||
470 | |||
471 | break; /* got one! */ | ||
472 | } | ||
473 | if (i < wh) { | ||
474 | i = order[i]; | ||
475 | |||
476 | /* | ||
477 | * Restore the temporarily removed square _before_ | ||
478 | * we start shifting ownerships about. | ||
479 | */ | ||
480 | if (tmpsq >= 0) | ||
481 | own[tmpsq] = j; | ||
482 | |||
483 | /* | ||
484 | * We are done. We can add square i to omino j, | ||
485 | * and then backtrack along the trail in tmp | ||
486 | * moving squares between ominoes, ending up | ||
487 | * expanding our starting omino by one. | ||
488 | */ | ||
489 | #ifdef DIVVY_DIAGNOSTICS | ||
490 | printf("(%d,%d)", i%w, i/w); | ||
491 | #endif | ||
492 | while (1) { | ||
493 | own[i] = j; | ||
494 | #ifdef DIVVY_DIAGNOSTICS | ||
495 | printf(" -> %d", j); | ||
496 | #endif | ||
497 | if (tmp[2*j] == -2) | ||
498 | break; | ||
499 | i = tmp[2*j+1]; | ||
500 | j = tmp[2*j]; | ||
501 | #ifdef DIVVY_DIAGNOSTICS | ||
502 | printf("; (%d,%d)", i%w, i/w); | ||
503 | #endif | ||
504 | } | ||
505 | #ifdef DIVVY_DIAGNOSTICS | ||
506 | printf("\n"); | ||
507 | #endif | ||
508 | |||
509 | /* | ||
510 | * Increment the size of the starting omino. | ||
511 | */ | ||
512 | sizes[j]++; | ||
513 | |||
514 | /* | ||
515 | * Terminate the bfs loop. | ||
516 | */ | ||
517 | break; | ||
518 | } | ||
519 | |||
520 | /* | ||
521 | * If we get here, we haven't been able to expand | ||
522 | * omino j into an unclaimed square. So now we begin | ||
523 | * to investigate expanding it into squares which are | ||
524 | * claimed by ominoes the bfs has not yet visited. | ||
525 | */ | ||
526 | for (i = 0; i < wh; i++) { | ||
527 | int dir, nj; | ||
528 | |||
529 | nj = own[order[i]]; | ||
530 | if (nj < 0 || tmp[2*nj] != -1) | ||
531 | continue; /* unclaimed, or owned by wrong omino */ | ||
532 | if (!removable[order[i]]) | ||
533 | continue; /* its omino won't let it go */ | ||
534 | |||
535 | for (dir = 0; dir < 4; dir++) | ||
536 | if (addable[order[i]*4+dir] == j) { | ||
537 | /* | ||
538 | * As above, re-check addremcommon. | ||
539 | */ | ||
540 | if (!addremcommon(w, h, order[i]%w, order[i]/w, | ||
541 | own, j)) | ||
542 | continue; | ||
543 | |||
544 | /* | ||
545 | * We have found a square we can use to | ||
546 | * expand omino j, at the expense of the | ||
547 | * as-yet unvisited omino nj. So add this | ||
548 | * to the bfs queue. | ||
549 | */ | ||
550 | assert(qtail < n); | ||
551 | queue[qtail++] = nj; | ||
552 | tmp[2*nj] = j; | ||
553 | tmp[2*nj+1] = order[i]; | ||
554 | |||
555 | /* | ||
556 | * Now terminate the loop over dir, to | ||
557 | * ensure we don't accidentally add the | ||
558 | * same omino twice to the queue. | ||
559 | */ | ||
560 | break; | ||
561 | } | ||
562 | } | ||
563 | |||
564 | /* | ||
565 | * Restore the temporarily removed square. | ||
566 | */ | ||
567 | if (tmpsq >= 0) | ||
568 | own[tmpsq] = j; | ||
569 | |||
570 | /* | ||
571 | * Advance the queue head. | ||
572 | */ | ||
573 | qhead++; | ||
574 | } | ||
575 | |||
576 | if (qhead == qtail) { | ||
577 | /* | ||
578 | * We have finished the bfs and not found any way to | ||
579 | * expand omino j. Panic, and return failure. | ||
580 | * | ||
581 | * FIXME: or should we loop over all ominoes before we | ||
582 | * give up? | ||
583 | */ | ||
584 | #ifdef DIVVY_DIAGNOSTICS | ||
585 | printf("FAIL!\n"); | ||
586 | #endif | ||
587 | retdsf = NULL; | ||
588 | goto cleanup; | ||
589 | } | ||
590 | } | ||
591 | |||
592 | #ifdef DIVVY_DIAGNOSTICS | ||
593 | { | ||
594 | int x, y; | ||
595 | printf("SUCCESS! Final grid:\n"); | ||
596 | for (y = 0; y < h; y++) { | ||
597 | for (x = 0; x < w; x++) | ||
598 | printf("%3d", own[y*w+x]); | ||
599 | printf("\n"); | ||
600 | } | ||
601 | } | ||
602 | #endif | ||
603 | |||
604 | /* | ||
605 | * Construct the output dsf. | ||
606 | */ | ||
607 | for (i = 0; i < wh; i++) { | ||
608 | assert(own[i] >= 0 && own[i] < n); | ||
609 | tmp[own[i]] = i; | ||
610 | } | ||
611 | retdsf = snew_dsf(wh); | ||
612 | for (i = 0; i < wh; i++) { | ||
613 | dsf_merge(retdsf, i, tmp[own[i]]); | ||
614 | } | ||
615 | |||
616 | /* | ||
617 | * Construct the output dsf a different way, to verify that | ||
618 | * the ominoes really are k-ominoes and we haven't | ||
619 | * accidentally split one into two disconnected pieces. | ||
620 | */ | ||
621 | dsf_init(tmp, wh); | ||
622 | for (y = 0; y < h; y++) | ||
623 | for (x = 0; x+1 < w; x++) | ||
624 | if (own[y*w+x] == own[y*w+(x+1)]) | ||
625 | dsf_merge(tmp, y*w+x, y*w+(x+1)); | ||
626 | for (x = 0; x < w; x++) | ||
627 | for (y = 0; y+1 < h; y++) | ||
628 | if (own[y*w+x] == own[(y+1)*w+x]) | ||
629 | dsf_merge(tmp, y*w+x, (y+1)*w+x); | ||
630 | for (i = 0; i < wh; i++) { | ||
631 | j = dsf_canonify(retdsf, i); | ||
632 | assert(dsf_canonify(tmp, j) == dsf_canonify(tmp, i)); | ||
633 | } | ||
634 | |||
635 | cleanup: | ||
636 | |||
637 | /* | ||
638 | * Free our temporary working space. | ||
639 | */ | ||
640 | sfree(order); | ||
641 | sfree(tmp); | ||
642 | sfree(own); | ||
643 | sfree(sizes); | ||
644 | sfree(queue); | ||
645 | sfree(addable); | ||
646 | sfree(removable); | ||
647 | |||
648 | /* | ||
649 | * And we're done. | ||
650 | */ | ||
651 | return retdsf; | ||
652 | } | ||
653 | |||
654 | #ifdef TESTMODE | ||
655 | static int fail_counter = 0; | ||
656 | #endif | ||
657 | |||
658 | int *divvy_rectangle(int w, int h, int k, random_state *rs) | ||
659 | { | ||
660 | int *ret; | ||
661 | |||
662 | do { | ||
663 | ret = divvy_internal(w, h, k, rs); | ||
664 | |||
665 | #ifdef TESTMODE | ||
666 | if (!ret) | ||
667 | fail_counter++; | ||
668 | #endif | ||
669 | |||
670 | } while (!ret); | ||
671 | |||
672 | return ret; | ||
673 | } | ||
674 | |||
675 | #ifdef TESTMODE | ||
676 | |||
677 | /* | ||
678 | * gcc -g -O0 -DTESTMODE -I.. -o divvy divvy.c ../random.c ../malloc.c ../dsf.c ../misc.c ../nullfe.c | ||
679 | * | ||
680 | * or to debug | ||
681 | * | ||
682 | * gcc -g -O0 -DDIVVY_DIAGNOSTICS -DTESTMODE -I.. -o divvy divvy.c ../random.c ../malloc.c ../dsf.c ../misc.c ../nullfe.c | ||
683 | */ | ||
684 | |||
685 | int main(int argc, char **argv) | ||
686 | { | ||
687 | int *dsf; | ||
688 | int i; | ||
689 | int w = 9, h = 4, k = 6, tries = 100; | ||
690 | random_state *rs; | ||
691 | |||
692 | rs = random_new("123456", 6); | ||
693 | |||
694 | if (argc > 1) | ||
695 | w = atoi(argv[1]); | ||
696 | if (argc > 2) | ||
697 | h = atoi(argv[2]); | ||
698 | if (argc > 3) | ||
699 | k = atoi(argv[3]); | ||
700 | if (argc > 4) | ||
701 | tries = atoi(argv[4]); | ||
702 | |||
703 | for (i = 0; i < tries; i++) { | ||
704 | int x, y; | ||
705 | |||
706 | dsf = divvy_rectangle(w, h, k, rs); | ||
707 | assert(dsf); | ||
708 | |||
709 | for (y = 0; y <= 2*h; y++) { | ||
710 | for (x = 0; x <= 2*w; x++) { | ||
711 | int miny = y/2 - 1, maxy = y/2; | ||
712 | int minx = x/2 - 1, maxx = x/2; | ||
713 | int classes[4], tx, ty; | ||
714 | for (ty = 0; ty < 2; ty++) | ||
715 | for (tx = 0; tx < 2; tx++) { | ||
716 | int cx = minx+tx, cy = miny+ty; | ||
717 | if (cx < 0 || cx >= w || cy < 0 || cy >= h) | ||
718 | classes[ty*2+tx] = -1; | ||
719 | else | ||
720 | classes[ty*2+tx] = dsf_canonify(dsf, cy*w+cx); | ||
721 | } | ||
722 | switch (y%2 * 2 + x%2) { | ||
723 | case 0: /* corner */ | ||
724 | /* | ||
725 | * Cases for the corner: | ||
726 | * | ||
727 | * - if all four surrounding squares belong | ||
728 | * to the same omino, we print a space. | ||
729 | * | ||
730 | * - if the top two are the same and the | ||
731 | * bottom two are the same, we print a | ||
732 | * horizontal line. | ||
733 | * | ||
734 | * - if the left two are the same and the | ||
735 | * right two are the same, we print a | ||
736 | * vertical line. | ||
737 | * | ||
738 | * - otherwise, we print a cross. | ||
739 | */ | ||
740 | if (classes[0] == classes[1] && | ||
741 | classes[1] == classes[2] && | ||
742 | classes[2] == classes[3]) | ||
743 | printf(" "); | ||
744 | else if (classes[0] == classes[1] && | ||
745 | classes[2] == classes[3]) | ||
746 | printf("-"); | ||
747 | else if (classes[0] == classes[2] && | ||
748 | classes[1] == classes[3]) | ||
749 | printf("|"); | ||
750 | else | ||
751 | printf("+"); | ||
752 | break; | ||
753 | case 1: /* horiz edge */ | ||
754 | if (classes[1] == classes[3]) | ||
755 | printf(" "); | ||
756 | else | ||
757 | printf("--"); | ||
758 | break; | ||
759 | case 2: /* vert edge */ | ||
760 | if (classes[2] == classes[3]) | ||
761 | printf(" "); | ||
762 | else | ||
763 | printf("|"); | ||
764 | break; | ||
765 | case 3: /* square centre */ | ||
766 | printf(" "); | ||
767 | break; | ||
768 | } | ||
769 | } | ||
770 | printf("\n"); | ||
771 | } | ||
772 | printf("\n"); | ||
773 | sfree(dsf); | ||
774 | } | ||
775 | |||
776 | printf("%d retries needed for %d successes\n", fail_counter, tries); | ||
777 | |||
778 | return 0; | ||
779 | } | ||
780 | |||
781 | #endif | ||