tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
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 */
215static bool 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 bool gotthis = (neighbours[dir] == val);
243 bool 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 */
263DSF *divvy_rectangle_attempt(int w, int h, int k, random_state *rs)
264{
265 int *order, *queue, *tmp, *own, *sizes, *addable;
266 DSF *retdsf, *tmpdsf;
267 bool *removable;
268 int wh = w*h;
269 int i, j, n, x, y, qhead, qtail;
270
271 n = wh / k;
272 assert(wh == k*n);
273
274 order = snewn(wh, int);
275 tmp = snewn(wh, int);
276 own = snewn(wh, int);
277 sizes = snewn(n, int);
278 queue = snewn(n, int);
279 addable = snewn(wh*4, int);
280 removable = snewn(wh, bool);
281 retdsf = tmpdsf = NULL;
282
283 /*
284 * Permute the grid squares into a random order, which will be
285 * used for iterating over the grid whenever we need to search
286 * for something. This prevents directional bias and arranges
287 * for the answer to be non-deterministic.
288 */
289 for (i = 0; i < wh; i++)
290 order[i] = i;
291 shuffle(order, wh, sizeof(*order), rs);
292
293 /*
294 * Begin by choosing a starting square at random for each
295 * omino.
296 */
297 for (i = 0; i < wh; i++) {
298 own[i] = -1;
299 }
300 for (i = 0; i < n; i++) {
301 own[order[i]] = i;
302 sizes[i] = 1;
303 }
304
305 /*
306 * Now repeatedly pick a random omino which isn't already at
307 * the target size, and find a way to expand it by one. This
308 * may involve stealing a square from another omino, in which
309 * case we then re-expand that omino, forming a chain of
310 * square-stealing which terminates in an as yet unclaimed
311 * square. Hence every successful iteration around this loop
312 * causes the number of unclaimed squares to drop by one, and
313 * so the process is bounded in duration.
314 */
315 while (1) {
316
317#ifdef DIVVY_DIAGNOSTICS
318 {
319 int x, y;
320 printf("Top of loop. Current grid:\n");
321 for (y = 0; y < h; y++) {
322 for (x = 0; x < w; x++)
323 printf("%3d", own[y*w+x]);
324 printf("\n");
325 }
326 }
327#endif
328
329 /*
330 * Go over the grid and figure out which squares can
331 * safely be added to, or removed from, each omino. We
332 * don't take account of other ominoes in this process, so
333 * we will often end up knowing that a square can be
334 * poached from one omino by another.
335 *
336 * For each square, there may be up to four ominoes to
337 * which it can be added (those to which it is
338 * 4-adjacent).
339 */
340 for (y = 0; y < h; y++) {
341 for (x = 0; x < w; x++) {
342 int yx = y*w+x;
343 int curr = own[yx];
344 int dir;
345
346 if (curr < 0) {
347 removable[yx] = false; /* can't remove if not owned! */
348 } else if (sizes[curr] == 1) {
349 removable[yx] = true; /* can always remove a singleton */
350 } else {
351 /*
352 * See if this square can be removed from its
353 * omino without disconnecting it.
354 */
355 removable[yx] = addremcommon(w, h, x, y, own, curr);
356 }
357
358 for (dir = 0; dir < 4; dir++) {
359 int dx = (dir == 0 ? -1 : dir == 1 ? +1 : 0);
360 int dy = (dir == 2 ? -1 : dir == 3 ? +1 : 0);
361 int sx = x + dx, sy = y + dy;
362 int syx = sy*w+sx;
363
364 addable[yx*4+dir] = -1;
365
366 if (sx < 0 || sx >= w || sy < 0 || sy >= h)
367 continue; /* no omino here! */
368 if (own[syx] < 0)
369 continue; /* also no omino here */
370 if (own[syx] == own[yx])
371 continue; /* we already got one */
372 if (!addremcommon(w, h, x, y, own, own[syx]))
373 continue; /* would non-simply connect the omino */
374
375 addable[yx*4+dir] = own[syx];
376 }
377 }
378 }
379
380 for (i = j = 0; i < n; i++)
381 if (sizes[i] < k)
382 tmp[j++] = i;
383 if (j == 0)
384 break; /* all ominoes are complete! */
385 j = tmp[random_upto(rs, j)];
386#ifdef DIVVY_DIAGNOSTICS
387 printf("Trying to extend %d\n", j);
388#endif
389
390 /*
391 * So we're trying to expand omino j. We breadth-first
392 * search out from j across the space of ominoes.
393 *
394 * For bfs purposes, we use two elements of tmp per omino:
395 * tmp[2*i+0] tells us which omino we got to i from, and
396 * tmp[2*i+1] numbers the grid square that omino stole
397 * from us.
398 *
399 * This requires that wh (the size of tmp) is at least 2n,
400 * i.e. k is at least 2. There would have been nothing to
401 * stop a user calling this function with k=1, but if they
402 * did then we wouldn't have got to _here_ in the code -
403 * we would have noticed above that all ominoes were
404 * already at their target sizes, and terminated :-)
405 */
406 assert(wh >= 2*n);
407 for (i = 0; i < n; i++)
408 tmp[2*i] = tmp[2*i+1] = -1;
409 qhead = qtail = 0;
410 queue[qtail++] = j;
411 tmp[2*j] = tmp[2*j+1] = -2; /* special value: `starting point' */
412
413 while (qhead < qtail) {
414 int tmpsq;
415
416 j = queue[qhead];
417
418 /*
419 * We wish to expand omino j. However, we might have
420 * got here by omino j having a square stolen from it,
421 * so first of all we must temporarily mark that
422 * square as not belonging to j, so that our adjacency
423 * calculations don't assume j _does_ belong to us.
424 */
425 tmpsq = tmp[2*j+1];
426 if (tmpsq >= 0) {
427 assert(own[tmpsq] == j);
428 own[tmpsq] = -3;
429 }
430
431 /*
432 * OK. Now begin by seeing if we can find any
433 * unclaimed square into which we can expand omino j.
434 * If we find one, the entire bfs terminates.
435 */
436 for (i = 0; i < wh; i++) {
437 int dir;
438
439 if (own[order[i]] != -1)
440 continue; /* this square is claimed */
441
442 /*
443 * Special case: if our current omino was size 1
444 * and then had a square stolen from it, it's now
445 * size zero, which means it's valid to `expand'
446 * it into _any_ unclaimed square.
447 */
448 if (sizes[j] == 1 && tmpsq >= 0)
449 break; /* got one */
450
451 /*
452 * Failing that, we must do the full test for
453 * addability.
454 */
455 for (dir = 0; dir < 4; dir++)
456 if (addable[order[i]*4+dir] == j) {
457 /*
458 * We know this square is addable to this
459 * omino with the grid in the state it had
460 * at the top of the loop. However, we
461 * must now check that it's _still_
462 * addable to this omino when the omino is
463 * missing a square. To do this it's only
464 * necessary to re-check addremcommon.
465 */
466 if (!addremcommon(w, h, order[i]%w, order[i]/w,
467 own, j))
468 continue;
469 break;
470 }
471 if (dir == 4)
472 continue; /* we can't add this square to j */
473
474 break; /* got one! */
475 }
476 if (i < wh) {
477 i = order[i];
478
479 /*
480 * Restore the temporarily removed square _before_
481 * we start shifting ownerships about.
482 */
483 if (tmpsq >= 0)
484 own[tmpsq] = j;
485
486 /*
487 * We are done. We can add square i to omino j,
488 * and then backtrack along the trail in tmp
489 * moving squares between ominoes, ending up
490 * expanding our starting omino by one.
491 */
492#ifdef DIVVY_DIAGNOSTICS
493 printf("(%d,%d)", i%w, i/w);
494#endif
495 while (1) {
496 own[i] = j;
497#ifdef DIVVY_DIAGNOSTICS
498 printf(" -> %d", j);
499#endif
500 if (tmp[2*j] == -2)
501 break;
502 i = tmp[2*j+1];
503 j = tmp[2*j];
504#ifdef DIVVY_DIAGNOSTICS
505 printf("; (%d,%d)", i%w, i/w);
506#endif
507 }
508#ifdef DIVVY_DIAGNOSTICS
509 printf("\n");
510#endif
511
512 /*
513 * Increment the size of the starting omino.
514 */
515 sizes[j]++;
516
517 /*
518 * Terminate the bfs loop.
519 */
520 break;
521 }
522
523 /*
524 * If we get here, we haven't been able to expand
525 * omino j into an unclaimed square. So now we begin
526 * to investigate expanding it into squares which are
527 * claimed by ominoes the bfs has not yet visited.
528 */
529 for (i = 0; i < wh; i++) {
530 int dir, nj;
531
532 nj = own[order[i]];
533 if (nj < 0 || tmp[2*nj] != -1)
534 continue; /* unclaimed, or owned by wrong omino */
535 if (!removable[order[i]])
536 continue; /* its omino won't let it go */
537
538 for (dir = 0; dir < 4; dir++)
539 if (addable[order[i]*4+dir] == j) {
540 /*
541 * As above, re-check addremcommon.
542 */
543 if (!addremcommon(w, h, order[i]%w, order[i]/w,
544 own, j))
545 continue;
546
547 /*
548 * We have found a square we can use to
549 * expand omino j, at the expense of the
550 * as-yet unvisited omino nj. So add this
551 * to the bfs queue.
552 */
553 assert(qtail < n);
554 queue[qtail++] = nj;
555 tmp[2*nj] = j;
556 tmp[2*nj+1] = order[i];
557
558 /*
559 * Now terminate the loop over dir, to
560 * ensure we don't accidentally add the
561 * same omino twice to the queue.
562 */
563 break;
564 }
565 }
566
567 /*
568 * Restore the temporarily removed square.
569 */
570 if (tmpsq >= 0)
571 own[tmpsq] = j;
572
573 /*
574 * Advance the queue head.
575 */
576 qhead++;
577 }
578
579 if (qhead == qtail) {
580 /*
581 * We have finished the bfs and not found any way to
582 * expand omino j. Panic, and return failure.
583 *
584 * FIXME: or should we loop over all ominoes before we
585 * give up?
586 */
587#ifdef DIVVY_DIAGNOSTICS
588 printf("FAIL!\n");
589#endif
590 retdsf = NULL;
591 goto cleanup;
592 }
593 }
594
595#ifdef DIVVY_DIAGNOSTICS
596 {
597 int x, y;
598 printf("SUCCESS! Final grid:\n");
599 for (y = 0; y < h; y++) {
600 for (x = 0; x < w; x++)
601 printf("%3d", own[y*w+x]);
602 printf("\n");
603 }
604 }
605#endif
606
607 /*
608 * Construct the output dsf.
609 */
610 for (i = 0; i < wh; i++) {
611 assert(own[i] >= 0 && own[i] < n);
612 tmp[own[i]] = i;
613 }
614 retdsf = dsf_new(wh);
615 for (i = 0; i < wh; i++) {
616 dsf_merge(retdsf, i, tmp[own[i]]);
617 }
618
619 /*
620 * Construct the output dsf a different way, to verify that
621 * the ominoes really are k-ominoes and we haven't
622 * accidentally split one into two disconnected pieces.
623 */
624 tmpdsf = dsf_new(wh);
625 for (y = 0; y < h; y++)
626 for (x = 0; x+1 < w; x++)
627 if (own[y*w+x] == own[y*w+(x+1)])
628 dsf_merge(tmpdsf, y*w+x, y*w+(x+1));
629 for (x = 0; x < w; x++)
630 for (y = 0; y+1 < h; y++)
631 if (own[y*w+x] == own[(y+1)*w+x])
632 dsf_merge(tmpdsf, y*w+x, (y+1)*w+x);
633 for (i = 0; i < wh; i++) {
634 j = dsf_canonify(retdsf, i);
635 assert(dsf_equivalent(tmpdsf, j, i));
636 }
637
638 cleanup:
639
640 /*
641 * Free our temporary working space.
642 */
643 sfree(order);
644 sfree(tmp);
645 dsf_free(tmpdsf);
646 sfree(own);
647 sfree(sizes);
648 sfree(queue);
649 sfree(addable);
650 sfree(removable);
651
652 /*
653 * And we're done.
654 */
655 return retdsf;
656}
657
658DSF *divvy_rectangle(int w, int h, int k, random_state *rs)
659{
660 DSF *ret;
661
662 do {
663 ret = divvy_rectangle_attempt(w, h, k, rs);
664 } while (!ret);
665
666 return ret;
667}