# Ascending matrix

An "ascending matrix" is an infinite matrix of natural numbers (0 included) in which any element is the smallest available element which has not been previously used on the respective row and column.

An example:

``````  | 1 2 3 4 5 6 ...
--+----------------
1 | 0 1 2 3 4 5 ...
2 | 1 0 3 2 5 4 ...
3 | 2 3 0 1 6 7 ...
4 | 3 2 1 0 7 6 ...
5 | 4 5 6 7 0 1 ...
6 | 5 4 7 6 1 0 ...
. | ...............
``````

Your task is to write a program that will output the element found at the row and column specified by the input. (standard input and output)

EX: for input "5 3" the expected output is "6"; for input "2 5" the expected output is "5".

Code Golf rules apply - the shortest code wins.

P.S. Even if this has an algorithmic nature the code can be very, very concise.

EDIT: I wasn't expecting to see the xor solution so early. I was really hoping to see 10 posts with an algorithmic approach and THEN the xor solution. Now, having in mind that it's not much fun to see how to write xor in different languages I recommend that you also try an algorithmic approach.

So, yes, I think no one can beat the 5 character mark now - therefore I congratulate Ilmari Karonen for the smartest and shortest solution. But there's a new challenge up ahead: write the shortest algorithmic solution.

-
 Xor is algorithmic. – Peter Taylor Oct 1 '12 at 17:06

## GolfScript, 5 chars

``````~(\(^
``````

Indeed, this task is very simple once you recognize the pattern. The only awkward bit is the 1-based indexing — if the input indices were zero-based, this 2-character solution would suffice:

``````~^
``````

To explain this to readers unfamiliar with GolfScript, the `~` command evals the input, leaving the two numbers on the stack. `^` then XORs the two topmost numbers on the stack together, leaving the result for output. To deal with 1-based input, two more commands are needed: `(` decrements the topmost number on the stack by one, while `\` swaps the top two items on the stack.

-
 Could you please explain the `^`? I referred to the GolfScript Built-ins page and Symmetric difference; using this operation with two sets of arrays makes sense, but I don't understand how it works for just two separate numbers. – Mike Dtrick Sep 30 '12 at 19:40 @Mike: When applied to numbers, the `^` operator returns their bitwise XOR. – Ilmari Karonen Sep 30 '12 at 22:05 That is a very cool relationship :) – beary605 Sep 30 '12 at 23:26 You were correct in your assessment of my response, which I have since removed for being based on a misreading of the challenge. – David Carraher Oct 1 '12 at 0:04 +1 Hard to believe you did so much with so little. – David Carraher Oct 1 '12 at 0:30
show 1 more comment

# Mathematica 10 44

Edit

My first response was based on a misunderstanding about the nature of the challenge, as noted by Ilmari. Here's another try.

Usage

``````f[n___, 1, n___] := n - 1;
j_~f~k_ := BitXor[j - 1, k - 1]
``````
-
 @IlmariKaronen I think I got it right this time. But it doesn't even come close to the size of your solution. – David Carraher Oct 1 '12 at 0:30

# K, 31

``````{0b/:{(x|y)&~x~y}. 0b\:'-1+x,y}
``````

Stole Ilmari Karonen's XOR logic, which I would never have spotted myself.

-

# PHP, 38

Just a simple implementation of Ilmari Karonen's XOR

`<?php echo --\$_GET['a']^--\$_GET['b']?>`

Usage:

.../xor.php?a=4&b=7

will print 6

-

Figured I'd make a solution that did not rely on XOR. Too lazy to golf it properly.

``````a 0 0=0
a b c
|m==n=a(b-m)(c-n)
|m>n=m+a(b-m)c
|m<n=n+a b(c-n)
where{g f=until(>f)(*2)1`div`2;m=g b;n=g c;}
main=do
print\$a(x-1)(y-1)
``````

Edit: I realized a day later that this is just calculating XOR. Thus if this counts as an algorithmic solution, so should Ilmari Karonen's.

-

# Python 2, 36

I figure since I'm just starting to learn Python that this would be the perfect time to submit my first answer using it (and no one has answered using Python) and perhaps I could receive some feedback.

Thank you @IlmariKaronen for the very cool shortcut.

Thank you @Gareth for the code below.

``````import sys
print(input()-1^input()-1)
``````

### Python 3, 56

The original program that I had written.

``````import sys
x=int(input())
y=int(input())
x-=1
y-=1
print(x^y)
``````

IDEONE with 2 and 5

IDEONE with 3 and 3

-
 I'm assuming your using Python 2 rather than Python 3 - if not ignore this comment. `input` already evaluates the input so the `int()` shouldn't be necessary. Also since you are getting an int directly from `input()` you could do the `-1` straight away. You can also get rid of the intermediary variables completely and go right for `print(input()-1^input()-1)`. As to whether or not the import is necessary - other Python users on this site don't include it for programs which use `input()`, but I'm not a Python programmer so I couldn't say if it's necessary or not. – Gareth Oct 2 '12 at 22:14 @Gareth Actually I was using Python 3, but I like your suggestion to use `print(input()-1^input()-1)`. Thank you for the help! – Mike Dtrick Oct 2 '12 at 23:19