Spiraling Number

Back then in college, we were given a lot of programming practices. These questions usually shows a desired output format, and we were required to write a program to print out the exact thing. Usually it involves printing a matrix of numbers, or symbols etc. For these problems, usually a loop structure or two should solve the problem.

However, a colleague of mine shared another problem this evening over an internal chatroom. Then the whole team got really excited about it. Basically, the question requires this output

 1  2  3  4  5 
16 17 18 19  6 
15 24 25 20  7 
14 23 22 21  8 
13 12 11 10  9

In other words, the number sequence is printed in a clock-wise inward spiraling pattern. It sounded like easy at first, but after a second thought apparently some work is needed. After some tinkering, I recalled my solution to the game of life at 4clojure. So I re-used the concept here (in PHP again, of course).

#!/usr/bin/env php
<?php

function node_is_valid($count_row, $count_column, Array $node_path, $node_next) {
    return FALSE === (node_is_used($node_next, $node_path)
        OR node_exceeds_range($node_next, $count_row, $count_column));
}

function node_is_used($node_next, $node_path) {
    return in_array($node_next, $node_path); 
}

function node_exceeds_range($node_next, $count_row, $count_column) {
    return $node_next[0] >= $count_row
        OR $node_next[0] < 0
        OR $node_next[1] >= $count_column
        OR $node_next[1] < 0;
}

function node_candidates(Array $node_path) {
    $node_last = end(array_values($node_path));
    $node_vector = node_get_vector($node_path, $node_last);

    return array(
        node_go_to($node_last, $node_vector),
        node_go_to($node_last, node_rotate_vector($node_vector)));
}

function node_get_vector($node_path, $node_last) {
    $node_count = count($node_path);

    return $node_count > 1 ?
        array($node_last[0] - $node_path[$node_count - 2][0],
            $node_last[1] - $node_path[$node_count - 2][1])
        : array(0, 1);
}

function node_rotate_vector($node_vector) {
    // maths theorem by @angch
    // http://en.wikipedia.org/wiki/Rotation_matrix#Common_rotations
    return array($node_vector[1], -1 * $node_vector[0]);
}

function node_go_to($node_last, $node_vector) {
    return array($node_last[0] + $node_vector[0],
        $node_last[1] + $node_vector[1]);
}

function node_get_next($row, $column, Array $node_path) {
    return array_shift(array_filter(
        node_candidates($node_path),
        function($node_next) use($row, $column, $node_path) {
            return node_is_valid($row, $column, $node_path, $node_next);
        }));
}

function node_construct_path($row, $column, $node_path=array(array(0, 0))) {
    return count($node_path) == ($row * $column) ?
        $node_path
        : node_construct_path(
            $row,
            $column,
            array_merge(
                $node_path,
                array(node_get_next($row, $column, $node_path))));
}

function print_result($row_count, $column_count, Array $result) {
    $format = sprintf('%%%dd ', strlen($row_count * $column_count));
    $column_range = range(0, $column_count - 1);

    array_walk(range(0, $row_count - 1), function($row) use($column_range, $format, $result) {
        array_walk($column_range, function($column) use($row, $format, $result) {
            printf($format, 1 + array_search(array($row, $column), $result));
        });

        echo PHP_EOL;
    });
}

function spiral($row, $column) {
    return print_result($row, $column, node_construct_path($row, $column));
}

spiral(5,5);

Conceptual-wise, I split the problem into two parts. The first part is to turn this question into some sort of path finding problem. Assuming the grid is of m (row) * n (column) dimension. Starting from the top left corner (coordinate 0,0), there are only 2 possible route, and in this case (0, 1) is the next node we are heading to. Then we continue to (0,2), (0,3) … (0,n) which is the end of the first row. Once we hit that node, the only possible route is down, which is (1,n). The relationship of two consecutive node, would be a case where:

• $row +/- 1, or
• $column +/- 1

With this in place, the list of possible next node for each phase is generated by referring to the above criteria. Besides that, we also need to consider where was the last node heading towards. The prior direction would then be prioritized while generating the list of candidates. Then these candidates will be validated to ensure they do not fall out of the grid, and do not repeat.

After the whole list is generated, then printing it would be an easier problem.

While the solution is never intended to be elegant, but it does the job. However, thinking back, if I am given this as an interview question, I would probably not able to answer on the spot without a computer and the interpreter. Besides that, I suppose if this is written in Javascript/Clojure it would look much better (still not really fond of Python althought it is my main language at work for now).