2
\$\begingroup\$

There is a table (the matrix one, not the one in your kitchen) called the "mex table". It has a left-top cell, at coordinates (0,0), but extends to infinity rightwards and downwards. The x-coordinate increases to the right and the y-coordinate increases downwards.

Every cell has a value >=0, and the cell at (0,0) has the value 0. The value of any other cell is defined as the lowest integer, >=0, which does not occur directly above it or directly to the left of it.

The start of the mex table looks like this:

+---+---+---+---+---+-
| 0 | 1 | 2 | 3 | 4 | ..
+---+---+---+---+---+-
| 1 | 0 | 3 | 2 | 5 | ..
+---+---+---+---+---+-
| 2 | 3 | 0 | 1 | ..
+---+---+---+---+-
| 3 | 2 | 1 | ..
+---+---+---+-
| 4 | 5 | ..
+---+---+-
| : | : | \

So, for example, the cell at (2,1) is 3 because 0 occurs left of it, 1 occurs left of it and 2 occurs above the cell. The cell at (3,1) is 2, however, because in the part of the row directly to the left of (3,1) and the part of the column directly above (3,1), 0, 1 and 3 occur, but 2 doesn't.

Objective: Print, to standard output, the number in the cell at (x,y) given two integers, both >=0, on standard input, space-separated and newline-terminated.

Thunderbirds are GO!

(This is derived from a question from the national finals of the Dutch Informatics Olympiad of some time ago.)

\$\endgroup\$
  • \$\begingroup\$ This too easy if you know the trick. Two characters in golfscript. \$\endgroup\$ – John Dvorak Apr 9 '14 at 15:42
  • \$\begingroup\$ Let them figure out... Took me some time too. \$\endgroup\$ – tomsmeding Apr 9 '14 at 15:47
  • \$\begingroup\$ I don't understand directly as used. It just seems like "doesn't occur to the left, doesn't occur above". \$\endgroup\$ – Bill Woodger Apr 9 '14 at 15:50
  • \$\begingroup\$ @BillWoodger correct, the "directly" is to stress that we only count that very same row and column, not any cells in between. Whatever, you get the point. \$\endgroup\$ – tomsmeding Apr 9 '14 at 15:52
  • \$\begingroup\$ Is there some other name for this table? \$\endgroup\$ – Justin Apr 9 '14 at 16:13
2
\$\begingroup\$

GolfScript (2 chars)

~^

This is familiar to anyone who knows anything at all about combinatorial game theory.

\$\endgroup\$
  • \$\begingroup\$ Hmm. Not much change of beating that since I have to convert to and from binary too. :-( \$\endgroup\$ – Gareth Apr 9 '14 at 16:19
  • 1
    \$\begingroup\$ technically, I have posted this very same answer 30 minutes ago ;-) \$\endgroup\$ – John Dvorak Apr 9 '14 at 16:24
  • 2
    \$\begingroup\$ @JanDvorak, Ilmari beat us both to it by 18 months. \$\endgroup\$ – Peter Taylor Apr 9 '14 at 16:26
1
\$\begingroup\$

J, 7 characters

#.~:/#:

Usage:

   #.~:/#:3 5
6
   #.~:/#:2 3
1
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.