Outward Counterclockwise Spiral Matrix Traversal

README.md

Outward Counterclockwise Spiral Matrix Traversal

Programming interview practice of the week (October 25)

Problem

Write a function that accepts four arguments. The first two arguments are the size of the grid (h x w), filled with ascending integers from left to right, top to bottom, starting from 1. The next two arguments are is the starting positions, the row (r) and column (c).

Return an array of integers obtained by spiraling outward anti-clockwise from the r and c, starting upward.

More details here

Note: There is a typo in the question. We should replace the number 194 with 14 in the second test case.

Solution

You can check the algorithm with:

$ pip install pytest
$ py.test

It executes in O(n) where n is the spiral size not the layout h * w. It should be memory efficient (O(h * w)) as it only stores the result representation.

spiral.py

def spiral(h, w, r, c):
    """
    Returns an array of integers obtained by spiralling outward anti-clockwise
    from the r and c, starting upward.

    Args:
        h (int): The layout height.
        w (int): The layout width.
        r (int): The starting row.
        c (int): The starting column.

    Returns:
        list. The spiral representation.

    Raises:
        ValueError

    """

    dirs = [(0, -1), (-1, 0), (0, 1), (1, 0)]
    x, y = c - 1, r - 1
    size = w * h

    if size <= 0:
        raise ValueError('Invalid layout size')

    if x < 0 or x >= w or y < 0 or y >= h:
        raise ValueError('Invalid starting point')

    i, result = 0, [x + y * w + 1]

    while len(result) < size:
        for j in xrange((i % 2) * 2, (i % 2) * 2 + 2):
            dx, dy = dirs[j]
            for _ in xrange(i + 1):
                x, y = x + dx, y + dy
                if 0 <= x < w and 0 <= y < h:
                    result.append(x + y * w + 1)

        i += 1

    return result

spiral_test.py

import pytest
from spiral import spiral

def test_given_layout_size_and_starting_point_should_return_the_spiral():
    assert spiral(1, 1, 1, 1) == [1]
    assert spiral(2, 1, 2, 1) == [2, 1]
    assert spiral(2, 1, 1, 1) == [1, 2]
    assert spiral(2, 2, 2, 2) == [4, 2, 1, 3]
    assert spiral(2, 2, 1, 2) == [2, 1, 3, 4]
    assert spiral(2, 2, 1, 1) == [1, 3, 4, 2]
    assert spiral(2, 4, 1, 2) == [2, 1, 5, 6, 7, 3, 8, 4]
    assert spiral(5, 5, 3, 3) == [
        13, 8, 7, 12, 17,
        18, 19, 14, 9, 4,
        3, 2, 1, 6, 11,
        16, 21, 22, 23, 24,
        25, 20, 15, 10, 5,
    ]


def test_given_invalid_layout_size_should_raise_an_exception():
    with pytest.raises(ValueError):
        spiral(0, 0, 0, 0)


def test_given_invalid_starting_point_should_raise_an_exception():
    with pytest.raises(ValueError):
        spiral(1, 1, 0, 0)

    with pytest.raises(ValueError):
        spiral(1, 1, 2, 1)