# The Matrix Winds In

The Problem: Given an N by M Matrix, Create an Anti-Clockwise Traversal Path that winds in all the way into the Matrix

Example: The Matrix is 9 by 5

Output:

|  1|| 24|| 23|| 22|| 21|
|  2|| 25|| 40|| 39|| 20|
|  3|| 26|| 41|| 38|| 19|
|  4|| 27|| 42|| 37|| 18|
|  5|| 28|| 43|| 36|| 17|
|  6|| 29|| 44|| 35|| 16|
|  7|| 30|| 45|| 34|| 15|
|  8|| 31|| 32|| 33|| 14|
|  9|| 10|| 11|| 12|| 13|


Code:

package com.progint;

import java.io.IOException;
import java.security.SecureRandom; /*For Maximum-Entropy Goodness*/

public class DerLooper {
static final int xMax=20, yMax=20,  xMin=1, yMin=1; /* Maximum and Minimum Matrix Size */
static int xCord, yCord;
static SecureRandom randomGenerator = new SecureRandom();
static int[][] looper;

DerLooper() {
xCord= xMin+randomGenerator.nextInt(xMax-xMin); yCord=yMin+randomGenerator.nextInt(yMax-yMin);
looper = new int[xCord][yCord];
}

/*
*      ________left__________
*     |                     |
*   down                    up
*     |_______right_________|
*
*     right eats higher row
*     up eats higher column
*     left eats lower row
*     down eats lower column
*
*/
static void displayLooper() {
int pathNumber=1;
int currentX=0, currentY=0;
int lowerColumn=0, lowerRow=0;
int higherColumn=yCord, higherRow=xCord;
while(true) {
//Go Down if Possible
/*
*    0
* 0 [1]
* 1 [2]
* 2 [3]
* 3 [4]
*  higherColumn,lowerColumn=0 | lowerRow=0,higherRow=3
*/
while(currentX<higherRow) {
looper[currentX++][currentY] = pathNumber++;
}
if(lowerColumn+1<higherColumn)  {lowerColumn++;} //eats lower column
else if (lowerColumn+1>=higherColumn) {break;}

//Go Right if Possible
/*
*    0  1  2  3  4
* 0 [1]
* 1 [2]
* 2 [3]
* 3 [4][5][6][7][8]
*  higherColumn=4,lowerColumn=1 | lowerRow=0,higherRow=3
*/
currentX--;
currentY++;
while(currentY<higherColumn) {
looper[currentX][currentY++] = pathNumber++;
}
if(higherRow-1>lowerRow)  {higherRow--;} //eats higher row
else if (higherRow-1<=lowerRow) {break;}

//Go Up if Possible
/*
*    0  1  2  3   4
* 0 [1]         [11]
* 1 [2]         [10]
* 2 [3]          [9]
* 3 [4][5][6][7][8]
*  higherColumn=4,lowerColumn=1 | lowerRow=0,higherRow=2
*/
currentX--;
currentY--;
while(currentX>=lowerRow) {
looper[currentX--][currentY] = pathNumber++;
}
if(higherColumn-1>lowerColumn)  {higherColumn--;} //eats higher column
else if (higherColumn-1<=lowerColumn) {break;}

//Go Left if Possible
/*
*    0    1   2   3    4
* 0 [1]  [14][13][12] [11]
* 1 [2]               [10]
* 2 [3]               [9]
* 3 [4]  [5] [6] [7]  [8]
*  higherColumn=3,lowerColumn=1 | lowerRow=0,higherRow=2
*/
currentX++;
currentY--;
while(currentY>=lowerColumn) {
looper[currentX][currentY--] = pathNumber++;
}
if(lowerRow+1<higherRow) {lowerRow++;} //eats lower row
else if (lowerRow+1>=higherRow) {break;}

//Loop through next subMatrix
/*
*    0    1   2   3    4
* 0 [1]  [14][13][12] [11]
* 1 [2]  here         [10]
* 2 [3]               [9]
* 3 [4]  [5] [6] [7]  [8]
*  higherColumn=3,lowerColumn=1 | lowerRow=1,higherRow=2
*/
currentX++;
currentY++;
}

System.out.println("The Matrix is "+xCord+" by "+yCord+"\n");
for (int i=0; i<xCord; i++) {
for (int j=0; j<yCord; j++) {
System.out.printf("|%3d|",looper[i][j]);
}
System.out.println();
}
}

public static void main(String[] args) throws NumberFormatException, IOException {
new DerLooper();
displayLooper();
}
}


We see multiple code stanzas that resemble:

            currentX--;
currentY++;


which seems tedious.

Define a vector of four (delta_x, delta_y) pairs: {(0, -1), (1, 0), (0, 1), (-1, 0)} and iterate through the vector.

• Definitely contracts, but also affects the readability of an already boundary-case cursed algorithm. May 22 at 2:31
• I don't understand your remark. Let's say we can conveniently compute point + delta, for a delta of unit magnitude. And we break out an is_valid_coord(...) predicate. Then it's a matter of asking whether is_valid_coord(point + delta), and keep bumping the delta index while it's invalid. You could combine "valid?" with "visited?" in a single predicate if you like. If you cycle through 4 directions without making any progress, then you have arrived at the omphalos and you're done.
– J_H
May 22 at 2:36