ij.swift

import Foundation

// Expects i and j to be 1-based row and column indexes, respectively.
func f(_ i: Int, _ j: Int) -> Int {
	return ((i+j-1) * (i+j))/2 - (((i+j-1) & 1 == 0) ? i : j) + 1
}

// Test: use f() to generate matrix and visually inspect it
// to see that the numbers are correct.
for i in 1...10 {
	var line: String = ""
	for j in 1...10 {
		line += String(format: "%5d", f(i, j))
	}
	print("\(line)\n")
}


// 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.