CODEWITHSUNDEEP
algorithmspiral
Umesh Kacha
Umesh Kacha

Reputation: 13666

Very interesting program of building pyramid

I have came across this very interesting program of printing numbers in pyramid.

If n = 1 then print the following,

1  2
4  3

if n = 2 then print the following,

1  2  3
8  9  4
7  6  5

if n = 3 then print the following,

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

I can print all these using taking quite a few loops and variables but it looks very specific. You might have noticed that all these pyramid filling starts in one direction until it find path filled. As you might have noticed 1,2,3,4,5,6,7,8,9,10,11,12 filed in outer edges till it finds 1 so after it goes in second row after 12 and prints 13,14 and so on. It prints in spiral mode something like snakes game snakes keep on going until it hits itself.

I would like to know is there any algorithms behind this pyramid generation or its just tricky time consuming pyramid generation program.

Thanks in advance. This is a very interesting challenging program so I kindly request no need of pipeline of down vote :)

Upvotes: 2

Views: 1297

Answers (3)

dave
dave

Reputation: 1550

Here is some C code implementing the basic algorithm submitted by @C.Zonnerberg my example uses n=6 for a 6x6 array.

I had to make a few changes to get the output the way I expected it to look. I swapped most the the x's and y's and changed several of the n's to n-1 and changed the comparisons in the for loops from <= to < 

int main(){
  int x,y,n;
  int result[6][6];
  n=6;
  for (x=0; x<n; x++){
    for (y=0; y<n; y++) {
      result[x][y] = Determine(n,x,y);
      if(y==0)
        printf("\n[%d,%d] = %2d, ", x,y, result[x][y]);
      else
        printf("[%d,%d] = %2d, ", x,y, result[x][y]);
    }
  }
return 0;
}

int Determine(int n, int x, int y)
{
  if (x == 0) return y + 1;         // Top
  if (y == n-1) return n + x;     // Right
  if (x == n-1) return 3 * (n-1) - y + 1; // Bottom
  if (y == 0) return 4 * (n-1) - x + 1; // Left
  return 4 * (n-1) + Determine(n - 2, x - 1, y- 1);
}

Output

[0,0] =  1, [0,1] =  2, [0,2] =  3, [0,3] =  4, [0,4] =  5, [0,5] =  6,
[1,0] = 20, [1,1] = 21, [1,2] = 22, [1,3] = 23, [1,4] = 24, [1,5] =  7,
[2,0] = 19, [2,1] = 32, [2,2] = 33, [2,3] = 34, [2,4] = 25, [2,5] =  8,
[3,0] = 18, [3,1] = 31, [3,2] = 36, [3,3] = 35, [3,4] = 26, [3,5] =  9,
[4,0] = 17, [4,1] = 30, [4,2] = 29, [4,3] = 28, [4,4] = 27, [4,5] = 10,
[5,0] = 16, [5,1] = 15, [5,2] = 14, [5,3] = 13, [5,4] = 12, [5,5] = 11,

Upvotes: 1

Chaim Zonnenberg
Chaim Zonnenberg

Reputation: 1823

I made a small recursive algorithm for your problem.

public int Determine(int n, int x, int y)
{
  if (y == 0) return x + 1;         // Top
  if (x == n) return n + y + 1;     // Right
  if (y == n) return 3 * n - x + 1; // Bottom
  if (x == 0) return 4 * n - y + 1; // Left
  return 4 * n + Determine(n - 2, x - 1, y - 1);
}

You can call it by using a double for loop. x and y start at 0:

for (int y=0; y<=n; y++) 
  for (int x=0; x<=n; x++) 
    result[x,y] = Determine(n,x,y);

Upvotes: 3

NoBugs
NoBugs

Reputation: 9496

With an all-zeros array, you could start with [row,col] = [0,0], fill in this space, then add [0,1] to position (one to the right) until it's at the end or runs into a non-zero.

Then go down (add [1,0]), filling in space until it's the end or runs into a non-zero.

Then go left (add [0,-1]), filling in space until it's the end or runs into a non-zero.

Then go up (add [-1,0]), filling in space until it's the end or runs into a non-zero.

and repeat...

Upvotes: 0

Related Questions