Creating outward spiral

Question

I've been thinking about this and I just can't think of a way to fill in a matrix with an outward spiral, so that I can do the following:

Turn this: 1 2 3 4 5 ... n

To

21 22 23 24 25 26
20 07 08 09 10 27
19 06 01 02 11 28
18 05 04 03 12 29
17 16 15 14 13 30
           ...n

My problem is the algorithm itself, but if instead of pseudocode you can help with C++, that'd be better.

This is some code I wrote to test things out, but I really don't know how I can go about to do this.

#include <stdio.h>
#include <string>

using namespace std;

int main() {
  //int n = 5;
  int spiral[5][6];

  for (int i = 0; i < 5; i++)
    for (int u = 0; u < 6; u++)
      spiral[i][u] = 0;

  spiral[2][2] = 1;
  string direction = "right";
  for (int i = 2; i < 5; i++) {
    for (int u = 2; u < 6; u++) {
      if (direction == "right") {
        spiral[i][u + 1] = spiral[i][u] + 1;
        direction = "down";
      }
    }
  }

  for (int i = 0; i < 5; i++) {
    for (int u = 0; u < 6; u++) {
      printf("%02d ", spiral[i][u]);
    }
    printf("\n");
  }

  return 0;
}

Thank you!

Answer 1

You can make the observation that there are similar squares with the lowest value in the bottom-left position then going upwards, right, down and left.

You can use this to create such a function:

template <typename Array>
void spiral_square(Array& a, int x, int y, int side, int& value)
{
  int mx = x+side-1, my=y+side-1;
  for (int i = 1; i <= side-1; ++i) a[my-i][x] = value++;
  for (int i = 1; i <= side-1; ++i) a[y][x+i] = value++;
  for (int i = 1; i <= side-1; ++i) a[y+i][mx] = value++;
  for (int i = 1; i <= side-1; ++i) a[my][mx-i] = value++;
}

See it in action: http://ideone.com/9iL1F

Answer 2

Start at the last number, and go inwards from a corner. Move in one direction, and when you hit a wall, turn left 90-degrees.

Answer 3

I think ipc's solution is based on the assumption you always want to fill out an entire matrix. What if you want to do n = 28 (ie having some incomplete row or column)?

For a generic n solution, I found it easiest to start from the starting point and increment outwards knowing the pattern of travel. Notice that you go:

1 right, 1 down, 2 left, 2 up, 3 right, 3 down, 4 left, 4 up, etc

So basically the pattern is you travel right, down, left, up for a number of steps that increments every two direction changes.

Unfortunately, I have not programmed in c++ in a while, so I did it in Ruby.

def output_spiral(n)
  #For formatting, determine the length of the largest number
  max_number_length = n.to_s.length

  #Determine matrix size
  max_x = Math.sqrt(n).floor
  max_y = Math.sqrt(n).floor
  if max_x * max_y < n
    max_x += 1
    if max_x * max_y < n
      max_y += 1
    end
  end

  #The a matrix of the required size.
  #Note that for simplicity in printing spiral is an array of row arrays.
  spiral = Array.new
  row = Array.new(max_x){ |i| '  ' }
  max_y.times{ spiral << row.clone }

  #Determine the starting point index (ie where to insert 1)
  x = ((max_x-1)/2).floor
  y = ((max_y-1)/2).floor

  #Input the start point value, formatted to the right size
  spiral[y][x] = "%0#{max_number_length}d" % 1

  #Setup counters required to iterate through the spiral
  steps_in_direction = 1        #This defines how many steps to take in a direction
  steps_count = 0               #This defines how many steps have been taken in the direction
  direction = 'right'           #This defines the direction currently travelling
  steps_in_direction_count = 0  #This define how many times we have used the same steps_in_direction value

  #Iterate through all the numbers up to n
  2.upto(n) do |i|
    #Change index based on the direction we are travelling
    case direction
      when 'right' then x += 1
      when 'down' then y += 1
      when 'left' then x -= 1
      when 'up' then y -= 1
    end

    #Input the value, formatted to the right size
    spiral[y][x] = "%0#{max_number_length}d" % i

    #Increment counters
    steps_count += 1
    if steps_count == steps_in_direction
      steps_count = 0
      steps_in_direction_count += 1

      if steps_in_direction_count == 2
        steps_in_direction += 1
        steps_in_direction_count = 0
      end

      case direction
        when 'right' then direction = 'down'
        when 'down' then direction = 'left'
        when 'left' then direction = 'up'
        when 'up' then direction = 'right'
      end
    end

  end

  #Output spiral
  spiral.each do |x|
    puts x.join(' ')
  end
end

output_spiral(95)

See http://ideone.com/d1N2c, which does a spiral of n=95.

Answer 4

I'm going to assume this is for project euler #28 (I just did this problem the other day). The secret isn't in creating the matrix, but in realizing the pattern. Realize the pattern and you can just count the two diagonals out without creating the matrix.

1, 3, 5, 7, 9, 13, 17, 21, 25, ... , n

Skipping anything?

As far as recreating the spiral matrix, I think the best way would be to work backwards after figuring out the pattern. Start from n and work your way down to 1. It would be a lot easier to place 'n' than 1 in the matrix.

Edited:

It isn't too difficult to create the matrix after determining the diagonals (problem 28). I placed those values into the matrix and then "walked" the matrix filling in all of the other values based on the main diagonal values that I had previously filled into the matrix. However, I waste a small amount of time determining the two main diagonals. I like IPC's solution better. However, just as another method, here is the code to compute the matrix after I have determined the two main diagonals. Let n refer to the size of the grid, for example, 5.

int[,] t = new int[n, n];
int sizeOf = n - 1;

//Note that nums is the array of the two diagonals, which are already in sorted order based on my solution to problem 28.

//fill in diagonals
for (int diagNum = numsCount, i = sizeOf, j = 0; ; i--, j++)
{
    if (diagNum < 3)
    {
        t[i, j] = 1;
        break;
    }

    t[i, i] = nums[diagNum--];
    t[i, j] = nums[diagNum--];

    t[j, j] = nums[diagNum--];
    t[j, i] = nums[diagNum--];
}

//finish filling in matrix
for (int i = sizeOf, c = 0; i > 1; i--, c++)
{
    for (int j = i - 1; j > sizeOf - i; j--)
        t[i, j] = t[i, i] - i + j;

    for (int j = c + 1; j < sizeOf - c; j++)
        t[c, j] = t[c, c] - j + c;

    for (int j = c + 1; j < i; j++)
        t[j, i] = t[c, i] - j + c;

    for (int j = i - 1; j > c; j--)
        t[j, c] = t[i, c] - i + j;
}

Answer 5

#include<stdio.h>

main()
{

long int i,j,k,a,b,c,d,sum1=0,sum2=0,sum3=0,sum4=0;

       for(i=1;i<=500;i++)
      {
        a=(2*i+1)*(2*i+1);
        sum1=sum1+a;
        b=a-2*i;
        sum2=sum2+b;
      c=b-2*i;
      sum3=sum3+c;
      d=c-2*i;
      sum4=sum4+d;
      }`

    printf("%ld",sum1+sum2+sum3+sum4+1);``
}