17
\$\begingroup\$

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

  | 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)

Test cases:

5 3 -> 6
2 5 -> 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.

\$\endgroup\$
  • 5
    \$\begingroup\$ Xor is algorithmic. \$\endgroup\$ – Peter Taylor Oct 1 '12 at 17:06

10 Answers 10

10
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Rob Sep 30 '12 at 19:40
  • 1
    \$\begingroup\$ @Mike: When applied to numbers, the ^ operator returns their bitwise XOR. \$\endgroup\$ – Ilmari Karonen Sep 30 '12 at 22:05
  • \$\begingroup\$ That is a very cool relationship :) \$\endgroup\$ – beary605 Sep 30 '12 at 23:26
  • 1
    \$\begingroup\$ You were correct in your assessment of my response, which I have since removed for being based on a misreading of the challenge. \$\endgroup\$ – DavidC Oct 1 '12 at 0:04
2
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ @IlmariKaronen I think I got it right this time. But it doesn't even come close to the size of your solution. \$\endgroup\$ – DavidC Oct 1 '12 at 0:30
2
\$\begingroup\$

K, 31

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

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

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

Haskell 174

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
 [x,y]<-fmap(map read.words)getLine
 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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Too lazy to golf it properly. -- please golf your submission for it to be a serious contender. \$\endgroup\$ – Jonathan Frech Sep 18 '18 at 21:49
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Gareth Oct 2 '12 at 22:14
  • \$\begingroup\$ @Gareth Actually I was using Python 3, but I like your suggestion to use print(input()-1^input()-1). Thank you for the help! \$\endgroup\$ – Rob Oct 2 '12 at 23:19
  • \$\begingroup\$ May I ask why you import sys? \$\endgroup\$ – Jonathan Frech Sep 18 '18 at 21:48
2
\$\begingroup\$

MATL, 2 bytes

Z~

Try it online!

MATL post-dates the challenge by several years, but, hey, natural 1-based indexing and a bitwise xor function makes this nice and neat!

\$\endgroup\$
0
\$\begingroup\$

Perl 5, 12 bytes

say<>-1^<>-1

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Javascript 13 bytes

a=>b=>--a^--b

f=a=>b=>--a^--b

result = document.getElementById('result')
<input type="text" onkeyup="result.innerHTML = f(this.value.split(',')[0])(this.value.split(',')[1])" >
<p id="result"></p>

\$\endgroup\$
0
\$\begingroup\$

Japt, 5 bytes

UÉ^VÉ

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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