Reputation: 31

Help with spiral matrix

I need to write a program for Pascal that makes array in spiral form like this:

(7) (8) (9) (10)
(6) (1) (2) (11)
(5) (4) (3) (12)
(16)(15)(14)(13)

Start from 1 and continue to 36 but this is not so important.

After 3 days thinking I have no idea how to realize this.

Problem is not in language syntax or arrays, it is just in the algorithm.

Can you help me with any ideas, links, pseudo-code or program code in any programming language?

Upvotes: 3

Answers (10)

Paul Ramirez

Reputation: 11

Here's a snippet from a Java program to perform a spiral matrix visit. It tracks changes in directions to sense how many more visits to make while traveling in any given direction. The pattern that simplifies this problem is that while traveling in any given direction, the next time you visit that direction the number of visits to make is reduced by one. More simply put, if the first time you travel in the horizontal direction you will be making 6 visits the next time you travel in the horizontal direction you will make 5 visits. It should also be noted that the horizontal and vertical visits are tracked separately. A single equation below has been used to calculate the number of visits for a given direction after a change in direction is needed. This equation selects vertical or horizontal by deriving it from the total number of direction changes and using mod as a selector. Finally, thinking of the visits as a snake moving along the matrix I represented the step as the change in row/column as velocity (dy and dx). As another person pointed out there is a pattern that can be used and is expressed in the formula for dy and dx.

int[][] matrix = { {  1,  2,  3,  4,  5,  6,  7,  8 }, 
                   { 24, 25, 26, 27, 28, 29, 30,  9 },
                   { 23, 40, 41, 42, 43, 44, 31, 10 }, 
                   { 22, 39, 48, 47, 46, 45, 32, 11 },
                   { 21, 38, 37, 36, 35, 34, 33, 12 }, 
                   { 20, 19, 18, 17, 16, 15, 14, 13 } };

int n = matrix.length;
int m = matrix[0].length;
int row = 0;
int col = 0;
int dx = 1;
int dy = 0;
int dirChanges = 0;
int visits = m;

for (int i = 0; i < n * m; i++) {
  System.out.print(matrix[row][col] + " ");
  visits--;
  if (visits == 0) {
    visits = m * (dirChanges %2) + n * ((dirChanges + 1) %2) - (dirChanges/2 - 1);
    int temp = dx;
    dx = -dy;
    dy = temp;
    dirChanges++;
  }

  col += dx;
  row += dy;
}

The output of this program is:

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

Upvotes: 1

Arnab Datta

Reputation: 1

import java.util.Scanner; 
class CircularMatrixFromInnerClockwise
{
Scanner sc= new Scanner(System.in);
 void main()
 {
     System.out.println("Enter size.");
     int n=sc.nextInt();
     int a[][]= new int [n][n];
     int r1,c1,r2,c2;
     if(n%2==0)
     {
      r1=n/2-1;
      c1=n/2-1;
      r2=n/2-1;
      c2=n/2-1;
    }
    else
    {
      r1=(n+1)/2-1;
      c1=(n+1)/2-1;
      r2=(n+1)/2-1;
      c2=(n+1)/2-1;
    }
     int k=1;
     do
     {   
         if(c2<n-1&&r2<n-1)
        {
         r2++;
         c2++;
        }
        for(int i=c1;i<=c2;i++)
         a[r1][i]=k++;  
          if(k>=n*n)
         break;
        for(int i=r1+1;i<=r2;i++)
         a[i][c2]=k++; 
         if(k>=n*n)
         break;
        if(c1>0&&r1>0)
        {
             c1--;
             r1--;
        }
         for(int i=c2-1;i>=c1;i--)
         a[r2][i]=k++;
         if(k>=n*n)
         break;

         for(int i=r2-1;i>=r1+1;i--)
         a[i][c1]=k++;
         if(k>=n*n)
         break;
     }while(k<=n*n);
     System.out.println("Circular matrix");
     for(int i=0;i<n;i++)
     {
         for(int j=0;j<n;j++)
         {
             System.out.print( a[i][j]+"\t");
         }
         System.out.println();
     }
 }
}

You're going from left to right, then down. left , up and all over again. Hope it helps. :)

Upvotes: 0

sayuan

Reputation: 41

How about just apply the right-hand rule (like solving a maze).

Consider each cell after you walked become the wall.

Upvotes: 1

paulmurray

Reputation: 3413

Do you mean that it has to print out the numbers from left-to-right, top to bottom? It helps to know that to make square numbers, you add consecutive odd numbers together - 1 + 3 + 5 + 7 + 9 + 11 = 36.

In this spiral, the left-hand edge is simple ... except for the bottom row. So one way to go is to write your algorithm as if the spiral was one loop bigger, but don't print out the first row and first and last column.

Upvotes: 0

Alin P.

Reputation: 44346

Here's a recursive solution written in PHP.

<?php
header('Content-type: text/plain');

function fill($x, $y, $dir, $leftInDir, $index, $stepSize, $stop){
    global $out;

    // set the value for the current item //
    $out[$y][$x] = $index;

    // everything that comes after this point is computing for the parameters of the next call //

    // activate this for debugging //
    //echo $x, ',', $y, ',', $dir, ',', $leftInDir, ',', $index, ',', $stepSize, ',', $stop, "\n";

    // decrease the number of steps left to take in the current direction //
    $leftInDir--;

    // check if this is the last item //
    if($index == $stop)
        return;

    // we're going up for the next item //
    if($dir == 'U')
        $y--;

    // we're going right for the next item //
    if($dir == 'R')
        $x++;

    // we're going down for the next item //
    if($dir == 'D')
        $y++;

    // we're going left for the next item //
    if($dir == 'L')
        $x--;

    // if this was the last step in this direction we need to change the direction //
    if($leftInDir == 0){

        // after two direction changes we need to increase the numbers of steps to take //
        if($dir == 'D' || $dir == 'U'){
            $stepSize++;
        }

        // update the direction clockwise //
        if($dir == 'U')
            $dir = 'R';
        else if($dir == 'R')
            $dir = 'D';
        else if($dir == 'D')
            $dir = 'L';
        else if($dir == 'L')
            $dir = 'U';

        // set the number of steps left as the step size //
        $leftInDir = $stepSize;
    }

    // increase the number to put in the cell //
    $index++;

    // call for the next item //
    fill($x,$y,$dir,$leftInDir,$index,$stepSize,$stop);
}

// set the size //
$size = 100;

// start the process from the center of the matrix //
fill((int)$size/2, (int)$size/2, 'R', 1, 1, 1, $size*$size);

// just output //
ksort($out);
foreach($out as $row){
    ksort($row);
    foreach($row as $item){
        echo str_pad($item, 7);
    }
    echo "\n";
}
?>

The principle is quite straight forward (well, not straight, but in a spiral, forward :) ). You start from where 1 should be and start walking. 1 RIGHT, 1 DOWN, 2 LEFT, 2 UP, 3 RIGHT, etc. until you reach n*n.

I wrote it as a recursive function, but it can easily be converted to a loop.

Upvotes: 0

Mohammad Mazaz

Reputation: 316

CurValue = n * n;

End point is the most down left point.

We'll visit from the end point to the first point ( we assign values with visiting )

Every cell has zero value at the beginning.

x = n-1;

y = 0;

arr[x][y] = CurValue;


while ( CurValue greater than zero )
{


keep going right until you face a cell that has non-zero value or until you reach the most right cell

keep going top until you face a cell that has non-zero value or until you reach the most top cell

keep going left until you face a cell that has non-zero value or until you reach the most left cell

keep going down until you face a cell that has non-zero value or until you reach the most down cell

}

note: with each cell you visit then do the following :
    CurValue --;
    Assign CurValue to the current visited cell;

I hope the algorithm above is clear to understand.

Upvotes: 0

Egon

Reputation: 1705

The easiest idea is to start from the end of the spiral and work your way back.

Have four variables (left, top, right, bottom) that tell you how much you have filled appropriately from each side.

Make a matrix of appropriate size.

Initialize left = top = 0 and right and bottom to the last column and row index.

Fill the bottom row from left -> right. Decrease bottom by one.
Fill right from bottom -> top. Decrease right by one.
Fill top from right -> left. Increase top by one.
Fill left from top -> bottom. Increase left by one.
Iterate until you filled the whole matrix.

Upvotes: 1

Dialecticus

Reputation: 16761

There is one sweet idea you can use to change direction while iterating over the matrix. Look at the following table. Input (dX, dY) are the previous direction in increment values, and output (cwdx, cwdy) are the next clock-wise direction, and output (ccwdx, ccwdy) are the next counter-clockwise direction (coordinate (0,0) is in upper-left corner):

dx dy | cwdx cwdy | ccwdx ccwdy
-------------------------------
 1  0 |   0    1  |    0    -1
 0  1 |  -1    0  |    1     0
-1  0 |   0   -1  |    0     1
 0 -1 |   1    0  |   -1     0

So, given direction (dx,dy) to turn clockwise you need direction (-dy,dx), and to turn counter-clockwise you need direction (dx,-dy). This means that you don't need a switch in your code to turn direction, you just do it by three lines of code:

temp = dx; // this is for clockwise turn
dx = -dy;
dy = temp;

And there is one more little trick. To fill the matrix you can actually start from the end and largest number, and make your way to center and number 1. If you start from edge and go to the center then you can fill the numbers in a line until you can (until you reach the edge of matrix or another number). If you can't fill in current direction anymore because (x+dx, y+dy) is not "fillable" then change direction.

Upvotes: 1

Rockstar

Reputation: 31

To #1

I wrote the program but the result looks like this:

I don't know maybe I have not understood your algorythm or any other problem happened. Here is code:

  n:=16;
  x:=1;
  For i:=1 to (n div 2) do
  begin
    For p:=i to n-i+1 do
    begin
      a[n-i+1,p]:=x;
    end;

    For q:=n-i to i do
    begin
      a[q,n-i+1]:=x;
    end;

    For o:=n-i to i do
    begin
      a[i,o]:=x;
    end;

    For u:=i+1 to n-i do
    begin
      a[u,i]:=x;
    end;
  end;

So I tried to write #2 program from php to pascal and it works. Now I will fix it to write numbers clockwise and start from center of array.

Big thank you all.

Upvotes: 0

Gabi Purcaru

Reputation: 31524

Think of splitting the nxn matrix into concentric submatrixes of 2x2, 4x4, .. nxn. In your case we would have the outer sub-matrix (elements 5 to 16) and the inner one (elements 1 to 4).

Now, for each level you should iterate over the four edges, and fill them with the needed elements. You can go inside-out or outside-in. I will go outside-in. We keep a counter which is initially n*n (16 in our example).

For i going from 1 to n/2:

First take the bottom edge (elements 16-13 for outer level). We go from x[n-i+1][i] to x[n-i+1][n-i+1] and fill (this would be 16, 15, 14, 13 for the first level and 4,3 for the second level)

Then we take the right edge (elements 12-10 for outer level). We go from x[n-i][n-i+1] to x[i][n-i+1] (elements 12, 11, 10 for outer level).

Then we take the top edge (elements 9-7 for outer level). We go from x[i][n-i] to x[i][i] (elements 9, 8, 7 for outer level)

At last we take the left edge (elements 6-5 for outer level). We go from x[i+1][i] to x[n-i][i] and fill that side (this would be 6, 5 for outer level).

And at last you have the middle element if n is odd. Then all you have to do is to assign x[n/2+1][n/2+1] = 1

I hope I made the the idea clear; if there is something you don't understand, ask.

Also I didn't implement the solution because I assume that the problem you have is only the idea, not the implementation

Upvotes: 1

Help with spiral matrix

Answers (10)

Related Questions