ij.py

# Expects i and j to be 1-based row and column indexes, respectively.
def f(i, j):
	return (((i+j-1) * (i+j))/2) - (i if ((i+j-1) & 1 == 0) else j) + 1

# Test: use f() to generate matrix and visually inspect it
# to see that the numbers are correct.
for i in range(10):
	line = ""
	for j in range(10):
		line += "%5d" % (f(i+1, j+1))
	print line

# Problem: Imagine an infinite 2-dimensional matrix containing
# the numbers 1, 2, 3, ... arranged in a diagonally winding
# order as below.  Write an algorithm that returns the matrix
# element at row i and column j.

#  1    3    4   10   11   21   22   36   37   55
#  2    5    9   12   20   23   35   38   54   57
#  6    8   13   19   24   34   39   53   58   76
#  7   14   18   25   33   40   52   59   75   82
# 15   17   26   32   41   51   60   74   83  101
# 16   27   31   42   50   61   73   84  100  111
# 28   30   43   49   62   72   85   99  112  130
# 29   44   48   63   71   86   98  113  129  144
# 45   47   64   70   87   97  114  128  145  163
# 46   65   69   88   96  115  127  146  162  181

# The above solution uses @trueskawka's observation that the
# matrix can be divided into diagonal "slices"
# (1), (2, 3), (4, 5, 6), ..., where the first n slices contain
# the numbers 1 through n(n+1)/2.  The nth slice, where n = i+j-1,
# contains matrix element (i,j), where i and j are 1-based indexes.
# The elements in a slice increase in the northwest direction when
# n is even, and in the southeast direction when n is odd.