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: */