How to derive a formula?

Question

I have two 5x5 diamond grids,

Grid1: Y values are,

    0
   1 1
  2 2 2
 3 3 3 3
4 4 4 4 4
 5 5 5 5
  6 6 6
   7 7
    8

Grid2: X values are,

    0
   0 1
  0 1 2
 0 1 2 3
0 1 2 3 4
 0 1 2 3
  0 1 2
   0 1
    0 

I need to derive a formula to get Grid3 values related to X, Y, and gridSize. expecting the below values in Grid3 (index values),

        00
      01  02
    03  04  05
  06  07  08  09
10  11  12  13  14
  15  16  17  18 
    19  20  21
     22   23
        24

What could be the formula which can be used to get Grid3 values?

Answer 1

To create a function getindex(x,y,size) returning the index, the first thing to notice is that because the index values increase from left to right first, the following identity always holds: getindex(x+1,y,size) = getindex(x,y,size)+1.

So we have

getindex(x,y,size): return x+[something involving only y and size]

Let's look at the index values for x=0. They start off as 0,1,3,6,10... for y=0,1,2.... These are the triangular numbers 0, 1, 1+2, 1+2+3, 1+2+3+4... and there's a closed-form solution y*(y+1)/2.

So our function, for the top half of the grid, looks like:

getindex(x,y,size): return x+y*(y+1)/2

When are we in the bottom half? When y>size. What do we do then? Count triangular numbers backwards from the bottom line. There are a total of (size*2-1) lines, so to flip the y coordinate we can replace y by (size*2-1)-y. Note that when y equals size we're in both the top and bottom half as far as this calculation is concerned.

Our function so far:

getindex(x,y,size): return x+((y<size) ? y*(y+1)/2 : size*size-(size*2-1-y)*(size*2-1-y+1)/2)

We should probably check for values that aren't actually in the grid. When are values not in the grid? When x or y is less than zero (off the top or left), or x>y (off the right in the top half), or x>=(size*2-1)-y (off the right in the bottom half) or y>size*2-1 (off the bottom).

So here we go:

function getindex(x,y,size):
     if (x<0) return "off to the left"
     if (y<0) return "off to the top"
     if (x>y) return "off to the right (top half)"
     if (x>=(size*2-1-y)) return "off to the right (bottom half)"
     if (y>size*2-1) return "off the bottom"
     
     return x+((y<size) ? y*(y+1)/2 : size*size-(size*2-1-y)*(size*2-1-y+1)/2)

Test it:

size = 5
counts = []
for (y in 0..10):
  for (x in 0..10):
     index = getindex (x, y, size)
     print x, y, index
     if index is OK:
       counts[index]++

Now check that each grid value was produced precisely once:

assert (keys(counts) == size*size)
for i in (0..size*size-1):
   assert (counts[i] == 1)

Writing a function to go in the reverse direction is left as an exercise :)