Matrice ascendante

17

La "matrice ascendante" est une matrice infinie de nombres entiers (0 inclus) dans laquelle tout élément est le plus petit élément disponible qui n'a pas été précédemment utilisé sur la ligne et la colonne respectives:

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

Votre tâche consiste à écrire un programme qui affichera l'élément trouvé à la ligne et à la colonne spécifiées par l'entrée. (entrée et sortie standard)

Cas de test:

5 3 -> 6
2 5 -> 5

Les règles du Code Golf s'appliquent: le code le plus court l'emporte.

PS Même si cela a un caractère algorithmique, le code peut être très, très concis.

EDIT: Je ne m'attendais pas à voir la solution xor si tôt. J'espérais vraiment voir 10 messages avec une approche algorithmique et ALORS la solution xor. Maintenant, sachant que ce n'est pas très amusant de voir comment écrire xor dans différentes langues, je vous recommande également d'essayer une approche algorithmique.

Donc, oui, je pense que personne ne peut battre la barre des 5 caractères maintenant - donc je félicite Ilmari Karonen pour la solution la plus intelligente et la plus courte. Mais il y a un nouveau défi à venir: écrire la solution algorithmique la plus courte .

adrianton3
la source
5
Xor est algorithmique.
Peter Taylor

Réponses:

10

GolfScript, 5 caractères

~(\(^

En effet, cette tâche est très simple une fois que vous reconnaissez le motif. Le seul bit gênant est l'indexation basée sur 1 - si les indices d'entrée étaient basés sur zéro, cette solution à 2 caractères suffirait:

~^

Pour expliquer cela aux lecteurs peu familiers avec GolfScript, la ~commande évalue l'entrée, laissant les deux nombres sur la pile. ^puis XORs les deux nombres supérieurs de la pile ensemble, laissant le résultat pour la sortie. Pour gérer une entrée basée sur 1, deux commandes supplémentaires sont nécessaires: (décrémente le numéro le plus haut de la pile d'une \unité , tandis que permute les deux éléments supérieurs de la pile.

Ilmari Karonen
la source
1
Pourriez-vous expliquer cela ^? J'ai fait référence à la page intégrée GolfScript et à la différence symétrique ; utiliser cette opération avec deux ensembles de tableaux est logique, mais je ne comprends pas comment cela fonctionne pour seulement deux nombres distincts.
Rob
1
@Mike: lorsqu'il est appliqué à des nombres, l' ^opérateur renvoie leur XOR au niveau du bit .
Ilmari Karonen
C'est une relation très cool :)
beary605
1
Vous aviez raison dans votre évaluation de ma réponse, que j'ai depuis supprimée car elle était fondée sur une lecture erronée du défi.
DavidC
2

Mathematica 10 44

Éditer

Ma première réponse était basée sur un malentendu sur la nature du défi, comme l'a noté Ilmari. Voici un autre essai.

Usage

f[n___, 1, n___] := n - 1;
j_~f~k_ := BitXor[j - 1, k - 1]
DavidC
la source
@IlmariKaronen Je pense que j'ai bien compris cette fois. Mais cela ne correspond même pas à la taille de votre solution.
DavidC
2

K, 31

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

J'ai volé la logique XOR d'Ilmari Karonen, que je n'aurais jamais repérée moi-même.

tmartin
la source
2

PHP, 38

Juste une simple implémentation du XOR d'Ilmari Karonen

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

Usage:

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

imprimera 6

scleaver
la source
2

Haskell 174

Je pensais que je ferais une solution qui ne reposait pas sur XOR. Trop paresseux pour jouer au golf correctement.

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: J'ai réalisé un jour plus tard que ce n'est que du calcul XOR. Ainsi, si cela compte comme une solution algorithmique, il devrait en être de même pour Ilmari Karonen.

walpen
la source
2
Trop paresseux pour jouer au golf correctement. - veuillez jouer votre soumission pour qu'elle soit un concurrent sérieux.
Jonathan Frech
2

Python 2, 36

Je suppose que depuis que je commence à peine à apprendre Python que ce serait le moment idéal pour soumettre ma première réponse en l'utilisant (et personne n'a répondu en utilisant Python) et peut-être que je pourrais recevoir des commentaires.

Merci @IlmariKaronen pour le raccourci très cool.

Merci @Gareth pour le code ci-dessous.

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

Python 3, 56

Le programme original que j'avais écrit.

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

IDEONE avec 2 et 5

IDEONE avec 3 et 3

Mike Dtrick
la source
Je suppose que vous utilisez Python 2 plutôt que Python 3 - sinon ignorez ce commentaire. inputévalue déjà l'entrée de sorte qu'elle int()ne devrait pas être nécessaire. De plus, puisque vous obtenez un int directement de input()vous, vous pouvez le faire -1immédiatement. Vous pouvez également vous débarrasser complètement des variables intermédiaires et aller à droite pour print(input()-1^input()-1). Quant à savoir si l'importation est nécessaire ou non - les autres utilisateurs de Python sur ce site ne l'incluent pas pour les programmes qui utilisent input(), mais je ne suis pas un programmeur Python, donc je ne pouvais pas dire si c'était nécessaire ou non.
Gareth
@Gareth En fait, j'utilisais Python 3, mais j'aime votre suggestion print(input()-1^input()-1). Merci pour l'aide!
Rob
Puis-je vous demander pourquoi vous importez sys?
Jonathan Frech
2

MATL , 2 octets

Z~

Essayez-le en ligne!

MATL retarde le défi de plusieurs années, mais bon, l'indexation naturelle basée sur 1 et une fonction xor au niveau du bit rendent cela agréable et soigné!

Giuseppe
la source
0

Javascript 13 octets

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>

Luis felipe De jesus Munoz
la source