[sgt/puzzles] / laydomino.c

/*
 * laydomino.c: code for performing a domino (2x1 tile) layout of
 * a given area of code.
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "puzzles.h"

/*
 * This function returns an array size w x h representing a grid:
 * each grid[i] = j, where j is the other end of a 2x1 domino.
 * If w*h is odd, one square will remain referring to itself.
 */

int *domino_layout(int w, int h, random_state *rs)
{
    int *grid, *grid2, *list;
    int wh = w*h;

    /*
     * Allocate space in which to lay the grid out.
     */
    grid = snewn(wh, int);
    grid2 = snewn(wh, int);
    list = snewn(2*wh, int);

    domino_layout_prealloc(w, h, rs, grid, grid2, list);

    sfree(grid2);
    sfree(list);

    return grid;
}

/*
 * As for domino_layout, but with preallocated buffers.
 * grid and grid2 should be size w*h, and list size 2*w*h.
 */
void domino_layout_prealloc(int w, int h, random_state *rs,
                            int *grid, int *grid2, int *list)
{
    int i, j, k, m, wh = w*h, todo, done;

    /*
     * To begin with, set grid[i] = i for all i to indicate
     * that all squares are currently singletons. Later we'll
     * set grid[i] to be the index of the other end of the
     * domino on i.
     */
    for (i = 0; i < wh; i++)
        grid[i] = i;

    /*
     * Now prepare a list of the possible domino locations. There
     * are w*(h-1) possible vertical locations, and (w-1)*h
     * horizontal ones, for a total of 2*wh - h - w.
     *
     * I'm going to denote the vertical domino placement with
     * its top in square i as 2*i, and the horizontal one with
     * its left half in square i as 2*i+1.
     */
    k = 0;
    for (j = 0; j < h-1; j++)
        for (i = 0; i < w; i++)
            list[k++] = 2 * (j*w+i);   /* vertical positions */
    for (j = 0; j < h; j++)
        for (i = 0; i < w-1; i++)
            list[k++] = 2 * (j*w+i) + 1;   /* horizontal positions */
    assert(k == 2*wh - h - w);

    /*
     * Shuffle the list.
     */
    shuffle(list, k, sizeof(*list), rs);

    /*
     * Work down the shuffled list, placing a domino everywhere
     * we can.
     */
    for (i = 0; i < k; i++) {
        int horiz, xy, xy2;

        horiz = list[i] % 2;
        xy = list[i] / 2;
        xy2 = xy + (horiz ? 1 : w);

        if (grid[xy] == xy && grid[xy2] == xy2) {
            /*
             * We can place this domino. Do so.
             */
            grid[xy] = xy2;
            grid[xy2] = xy;
        }
    }

#ifdef GENERATION_DIAGNOSTICS
    printf("generated initial layout\n");
#endif

    /*
     * Now we've placed as many dominoes as we can immediately
     * manage. There will be squares remaining, but they'll be
     * singletons. So loop round and deal with the singletons
     * two by two.
     */
    while (1) {
#ifdef GENERATION_DIAGNOSTICS
        for (j = 0; j < h; j++) {
            for (i = 0; i < w; i++) {
                int xy = j*w+i;
                int v = grid[xy];
                int c = (v == xy+1 ? '[' : v == xy-1 ? ']' :
                         v == xy+w ? 'n' : v == xy-w ? 'U' : '.');
                putchar(c);
            }
            putchar('\n');
        }
        putchar('\n');
#endif

        /*
         * Our strategy is:
         *
         * First find a singleton square.
         *
         * Then breadth-first search out from the starting
         * square. From that square (and any others we reach on
         * the way), examine all four neighbours of the square.
         * If one is an end of a domino, we move to the _other_
         * end of that domino before looking at neighbours
         * again. When we encounter another singleton on this
         * search, stop.
         *
         * This will give us a path of adjacent squares such
         * that all but the two ends are covered in dominoes.
         * So we can now shuffle every domino on the path up by
         * one.
         *
         * (Chessboard colours are mathematically important
         * here: we always end up pairing each singleton with a
         * singleton of the other colour. However, we never
         * have to track this manually, since it's
         * automatically taken care of by the fact that we
         * always make an even number of orthogonal moves.)
         */
        k = 0;
        for (j = 0; j < wh; j++) {
            if (grid[j] == j) {
                k++;
                i = j;          /* start BFS here. */
            }
        }
        if (k == (wh % 2))
            break;              /* if area is even, we have no more singletons;
                                   if area is odd, we have one singleton.
                                   either way, we're done. */

#ifdef GENERATION_DIAGNOSTICS
        printf("starting b.f.s. at singleton %d\n", i);
#endif
        /*
         * Set grid2 to -1 everywhere. It will hold our
         * distance-from-start values, and also our
         * backtracking data, during the b.f.s.
         */
        for (j = 0; j < wh; j++)
            grid2[j] = -1;
        grid2[i] = 0;              /* starting square has distance zero */

        /*
         * Start our to-do list of squares. It'll live in
         * `list'; since the b.f.s can cover every square at
         * most once there is no need for it to be circular.
         * We'll just have two counters tracking the end of the
         * list and the squares we've already dealt with.
         */
        done = 0;
        todo = 1;
        list[0] = i;

        /*
         * Now begin the b.f.s. loop.
         */
        while (done < todo) {
            int d[4], nd, x, y;

            i = list[done++];

#ifdef GENERATION_DIAGNOSTICS
            printf("b.f.s. iteration from %d\n", i);
#endif
            x = i % w;
            y = i / w;
            nd = 0;
            if (x > 0)
                d[nd++] = i - 1;
            if (x+1 < w)
                d[nd++] = i + 1;
            if (y > 0)
                d[nd++] = i - w;
            if (y+1 < h)
                d[nd++] = i + w;
            /*
             * To avoid directional bias, process the
             * neighbours of this square in a random order.
             */
            shuffle(d, nd, sizeof(*d), rs);

            for (j = 0; j < nd; j++) {
                k = d[j];
                if (grid[k] == k) {
#ifdef GENERATION_DIAGNOSTICS
                    printf("found neighbouring singleton %d\n", k);
#endif
                    grid2[k] = i;
                    break;         /* found a target singleton! */
                }

                /*
                 * We're moving through a domino here, so we
                 * have two entries in grid2 to fill with
                 * useful data. In grid[k] - the square
                 * adjacent to where we came from - I'm going
                 * to put the address _of_ the square we came
                 * from. In the other end of the domino - the
                 * square from which we will continue the
                 * search - I'm going to put the distance.
                 */
                m = grid[k];

                if (grid2[m] < 0 || grid2[m] > grid2[i]+1) {
#ifdef GENERATION_DIAGNOSTICS
                    printf("found neighbouring domino %d/%d\n", k, m);
#endif
                    grid2[m] = grid2[i]+1;
                    grid2[k] = i;
                    /*
                     * And since we've now visited a new
                     * domino, add m to the to-do list.
                     */
                    assert(todo < wh);
                    list[todo++] = m;
                }
            }

            if (j < nd) {
                i = k;
#ifdef GENERATION_DIAGNOSTICS
                printf("terminating b.f.s. loop, i = %d\n", i);
#endif
                break;
            }

            i = -1;                /* just in case the loop terminates */
        }

        /*
         * We expect this b.f.s. to have found us a target
         * square.
         */
        assert(i >= 0);

        /*
         * Now we can follow the trail back to our starting
         * singleton, re-laying dominoes as we go.
         */
        while (1) {
            j = grid2[i];
            assert(j >= 0 && j < wh);
            k = grid[j];

            grid[i] = j;
            grid[j] = i;
#ifdef GENERATION_DIAGNOSTICS
            printf("filling in domino %d/%d (next %d)\n", i, j, k);
#endif
            if (j == k)
                break;             /* we've reached the other singleton */
            i = k;
        }
#ifdef GENERATION_DIAGNOSTICS
        printf("fixup path completed\n");
#endif
    }
}

/* vim: set shiftwidth=4 :set textwidth=80: */
Commit	Line	Data
4700b849	1	/*
	2	* laydomino.c: code for performing a domino (2x1 tile) layout of
	3	* a given area of code.
	4	*/
	5
	6	#include <stdio.h>
	7	#include <stdlib.h>
	8	#include <assert.h>
	9
	10	#include "puzzles.h"
	11
	12	/*
	13	* This function returns an array size w x h representing a grid:
	14	* each grid[i] = j, where j is the other end of a 2x1 domino.
	15	* If w*h is odd, one square will remain referring to itself.
	16	*/
	17
	18	int domino_layout(int w, int h, random_state rs)
	19	{
	20	int grid, grid2, *list;
	21	int wh = w*h;
	22
	23	/*
	24	* Allocate space in which to lay the grid out.
	25	*/
	26	grid = snewn(wh, int);
	27	grid2 = snewn(wh, int);
	28	list = snewn(2*wh, int);
	29
	30	domino_layout_prealloc(w, h, rs, grid, grid2, list);
	31
	32	sfree(grid2);
	33	sfree(list);
	34
	35	return grid;
	36	}
	37
	38	/*
	39	* As for domino_layout, but with preallocated buffers.
	40	* grid and grid2 should be size wh, and list size 2w*h.
	41	*/
	42	void domino_layout_prealloc(int w, int h, random_state *rs,
	43	int grid, int grid2, int *list)
	44	{
	45	int i, j, k, m, wh = w*h, todo, done;
	46
	47	/*
	48	* To begin with, set grid[i] = i for all i to indicate
	49	* that all squares are currently singletons. Later we'll
	50	* set grid[i] to be the index of the other end of the
	51	* domino on i.
	52	*/
	53	for (i = 0; i < wh; i++)
	54	grid[i] = i;
	55
	56	/*
	57	* Now prepare a list of the possible domino locations. There
	58	* are w(h-1) possible vertical locations, and (w-1)h
	59	* horizontal ones, for a total of 2*wh - h - w.
	60	*
	61	* I'm going to denote the vertical domino placement with
	62	* its top in square i as 2*i, and the horizontal one with
	63	* its left half in square i as 2*i+1.
	64	*/
65	k = 0;
66	for (j = 0; j < h-1; j++)
67	for (i = 0; i < w; i++)
68	list[k++] = 2 * (jw+i); / vertical positions */
69	for (j = 0; j < h; j++)
70	for (i = 0; i < w-1; i++)
71	list[k++] = 2 * (jw+i) + 1; / horizontal positions */
72	assert(k == 2*wh - h - w);
73
74	/*
75	* Shuffle the list.
76	*/
77	shuffle(list, k, sizeof(*list), rs);
78
79	/*
80	* Work down the shuffled list, placing a domino everywhere
81	* we can.
82	*/
83	for (i = 0; i < k; i++) {
84	int horiz, xy, xy2;
85
86	horiz = list[i] % 2;
87	xy = list[i] / 2;
88	xy2 = xy + (horiz ? 1 : w);
89
90	if (grid[xy] == xy && grid[xy2] == xy2) {
91	/*
92	* We can place this domino. Do so.
93	*/
94	grid[xy] = xy2;
95	grid[xy2] = xy;
96	}
97	}
98
99	#ifdef GENERATION_DIAGNOSTICS
100	printf("generated initial layout\n");
101	#endif
102
103	/*
104	* Now we've placed as many dominoes as we can immediately
105	* manage. There will be squares remaining, but they'll be
106	* singletons. So loop round and deal with the singletons
107	* two by two.
108	*/
109	while (1) {
110	#ifdef GENERATION_DIAGNOSTICS
111	for (j = 0; j < h; j++) {
112	for (i = 0; i < w; i++) {
113	int xy = j*w+i;
114	int v = grid[xy];
115	int c = (v == xy+1 ? '[' : v == xy-1 ? ']' :
116	v == xy+w ? 'n' : v == xy-w ? 'U' : '.');
117	putchar(c);
118	}
119	putchar('\n');
120	}
121	putchar('\n');
122	#endif
123
124	/*
125	* Our strategy is:
126	*
127	* First find a singleton square.
128	*
129	* Then breadth-first search out from the starting
130	* square. From that square (and any others we reach on
131	* the way), examine all four neighbours of the square.
132	* If one is an end of a domino, we move to the _other_
133	* end of that domino before looking at neighbours
134	* again. When we encounter another singleton on this
135	* search, stop.
136	*
137	* This will give us a path of adjacent squares such
138	* that all but the two ends are covered in dominoes.
139	* So we can now shuffle every domino on the path up by
140	* one.
141	*
142	* (Chessboard colours are mathematically important
143	* here: we always end up pairing each singleton with a
144	* singleton of the other colour. However, we never
145	* have to track this manually, since it's
146	* automatically taken care of by the fact that we
147	* always make an even number of orthogonal moves.)
148	*/
149	k = 0;
150	for (j = 0; j < wh; j++) {
151	if (grid[j] == j) {
152	k++;
153	i = j; /* start BFS here. */
154	}
155	}
156	if (k == (wh % 2))
157	break; /* if area is even, we have no more singletons;
158	if area is odd, we have one singleton.
159	either way, we're done. */
160
161	#ifdef GENERATION_DIAGNOSTICS
162	printf("starting b.f.s. at singleton %d\n", i);
163	#endif
164	/*
165	* Set grid2 to -1 everywhere. It will hold our
166	* distance-from-start values, and also our
167	* backtracking data, during the b.f.s.
168	*/
169	for (j = 0; j < wh; j++)
170	grid2[j] = -1;
171	grid2[i] = 0; /* starting square has distance zero */
172
173	/*
174	* Start our to-do list of squares. It'll live in
175	* `list'; since the b.f.s can cover every square at
176	* most once there is no need for it to be circular.
177	* We'll just have two counters tracking the end of the
178	* list and the squares we've already dealt with.
179	*/
180	done = 0;
181	todo = 1;
182	list[0] = i;
183
184	/*
185	* Now begin the b.f.s. loop.
186	*/
187	while (done < todo) {
188	int d[4], nd, x, y;
189
190	i = list[done++];
191
192	#ifdef GENERATION_DIAGNOSTICS
193	printf("b.f.s. iteration from %d\n", i);
194	#endif
195	x = i % w;
196	y = i / w;
197	nd = 0;
198	if (x > 0)
199	d[nd++] = i - 1;
200	if (x+1 < w)
201	d[nd++] = i + 1;
202	if (y > 0)
203	d[nd++] = i - w;
204	if (y+1 < h)
205	d[nd++] = i + w;
206	/*
207	* To avoid directional bias, process the
208	* neighbours of this square in a random order.
209	*/
210	shuffle(d, nd, sizeof(*d), rs);
211
212	for (j = 0; j < nd; j++) {
213	k = d[j];
214	if (grid[k] == k) {
215	#ifdef GENERATION_DIAGNOSTICS
216	printf("found neighbouring singleton %d\n", k);
217	#endif
218	grid2[k] = i;
219	break; /* found a target singleton! */
220	}
221
222	/*
223	* We're moving through a domino here, so we
224	* have two entries in grid2 to fill with
225	* useful data. In grid[k] - the square
226	* adjacent to where we came from - I'm going
227	* to put the address _of_ the square we came
228	* from. In the other end of the domino - the
229	* square from which we will continue the
230	* search - I'm going to put the distance.
231	*/
232	m = grid[k];
233
234	if (grid2[m] < 0 \|\| grid2[m] > grid2[i]+1) {
235	#ifdef GENERATION_DIAGNOSTICS
236	printf("found neighbouring domino %d/%d\n", k, m);
237	#endif
238	grid2[m] = grid2[i]+1;
239	grid2[k] = i;
240	/*
241	* And since we've now visited a new
242	* domino, add m to the to-do list.
243	*/
244	assert(todo < wh);
245	list[todo++] = m;
246	}
247	}
248
249	if (j < nd) {
250	i = k;
251	#ifdef GENERATION_DIAGNOSTICS
252	printf("terminating b.f.s. loop, i = %d\n", i);
253	#endif
254	break;
255	}
256
257	i = -1; /* just in case the loop terminates */
258	}
259
260	/*
261	* We expect this b.f.s. to have found us a target
262	* square.
263	*/
264	assert(i >= 0);
265
266	/*
267	* Now we can follow the trail back to our starting
268	* singleton, re-laying dominoes as we go.
269	*/
270	while (1) {
271	j = grid2[i];
272	assert(j >= 0 && j < wh);
273	k = grid[j];
274
275	grid[i] = j;
276	grid[j] = i;
277	#ifdef GENERATION_DIAGNOSTICS
278	printf("filling in domino %d/%d (next %d)\n", i, j, k);
279	#endif
280	if (j == k)
281	break; /* we've reached the other singleton */
282	i = k;
283	}
284	#ifdef GENERATION_DIAGNOSTICS
285	printf("fixup path completed\n");
286	#endif
287	}
288	}
289
290	/* vim: set shiftwidth=4 :set textwidth=80: */
291