Outward Counterclockwise Spiral Matrix Traversal (in C)

sp.c

/*
 * Outward Spiral, Conrad Meyer 2013.
 * Coding for interviews, Oct 25 2013.
 *
 * This problem is coming up with an ordering of the numbers in the range
 * [1, h*w]. The straightforward implementation of walking in a spiral from the
 * starting coordinates is O(max(h, w) ^ 2). However, given that we only have
 * to order h*w numbers, the best possible bound should be O(h * w). For
 * asymmetric grids, h*w is much less than max(h, w)^2; the worst case would be
 * a single-dimensional array.
 *
 * So, we can skip single-stepping the out-of-bounds traversals and bring our
 * run-time down to O(h*w).
 */

#ifndef DEBUG
#define DEBUG
#endif
#include <assert.h>
#include <inttypes.h>
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

void
f(unsigned h, unsigned w, unsigned r_, unsigned c_, unsigned **arr_out,
    unsigned *arr_len)
{
	assert(h > 0 && w > 0);
	assert(r_ < h && c_ < w);
	assert(r_ <= INT_MAX && c_ <= INT_MAX);

	unsigned tot = h*w;
	*arr_out = malloc(tot * sizeof(unsigned));
	assert(*arr_out);

	*arr_len = tot;

	int r = (int)r_,
	    c = (int)c_;

	enum {
		UP,
		LEFT,
		DOWN,
		RIGHT,
		DIRMAX,
	} dir = UP;

	int step = 0;
	int tr = r, tc = c;
	int dxs = 0, dys = 0;

	for (unsigned i = 0; i < tot;) {
		//printf("At: %d, %d\n", r, c);
		if (r >= 0 && r < (int)h &&
		    c >= 0 && c < (int)w) {
			(*arr_out)[i] = r*w + c + 1;
			i++;
		}

		if (tr == r && tc == c) {
			int dx = 0, dy = 0;

			dxs = 0;
			dys = 0;

			switch (dir) {
			case UP:
				step++;
				dy = -step;
				dys = -1;
				break;
			case LEFT:
				dx = -step;
				dxs = -1;
				break;
			case DOWN:
				step++;
				dy = step;
				dys = 1;
				break;
			case RIGHT:
				dx = step;
				dxs = 1;
				break;
			default:
				assert(false);
			}

			tr = r + dy;
			tc = c + dx;
			dir = (dir + 1) % DIRMAX;

			//printf("XXX tr:%d tc:%d dir:%d\n", tr, tc, dir);
		}

		r += dys;
		c += dxs;

		// Reduce runtime from O(max(h,w) ^ 2) to O(h*w) for non-square
		// grids.
		//
		// skip totally out of bounds walks.
		if ((r < 0 && tr < 0) || (c < 0 && tc < 0) ||
		    (r >= (int)h && tr >= (int)h) || (c >= (int)w && tc >= (int)w)) {
			//printf("Skipping from (%d,%d) -> (%d,%d)\n", r, c, tr, tc);
			r = tr;
			c = tc;
		}

		// Skip directly to in-bound values.
		if (tr > r && r < 0)
			r = 0;
		if (tr < r && r >= (int)h)
			r = (int)h - 1;
		if (tc > c && c < 0)
			c = 0;
		if (tc < c && c >= (int)w)
			c = (int)w - 1;
	}
}

int
main(int argc, char **argv)
{
	int h, w, r, c;

	if (argc != 5) {
		printf("Usage: sp h w r c\n");
		return 1;
	}

	h = atoi(argv[1]);
	w = atoi(argv[2]);
	r = atoi(argv[3]);
	c = atoi(argv[4]);

	unsigned n, *res;
	f(h, w, r-1, c-1, &res, &n);

	printf("[");
	for (unsigned i = 0; i < n; i++) {
		printf(" %u,", res[i]);
		if ((i % 7) == 6 && n > 8)
			printf("\n");
	}
	printf("]\n");

	return 0;
}