Matryca wstępująca

17

„Macierz wstępująca” jest nieskończoną macierzą liczb całkowitych (włącznie z 0), w której dowolny element jest najmniejszym dostępnym elementem, który nie był wcześniej używany w odpowiednim wierszu i kolumnie:

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

Twoim zadaniem jest napisanie programu, który wyświetli element znaleziony w wierszu i kolumnie określonej przez dane wejściowe. (standardowe wejście i wyjście)

Przypadki testowe:

5 3 -> 6
2 5 -> 5

Obowiązują zasady Code Golf - wygrywa najkrótszy kod.

PS Nawet jeśli ma to charakter algorytmiczny, kod może być bardzo, bardzo zwięzły.

EDYCJA: Nie spodziewałem się, że zobaczę rozwiązanie Xor tak wcześnie. Naprawdę miałem nadzieję zobaczyć 10 postów z podejściem algorytmicznym i NASTĘPNIE rozwiązanie xor. Teraz, mając na uwadze, że pisanie xora w różnych językach nie jest zbyt zabawne, zalecam również podejście algorytmiczne.

Więc tak, myślę, że nikt nie może teraz pokonać znaku 5 znaków - dlatego gratuluję Ilmari Karonen za najmądrzejsze i najkrótsze rozwiązanie. Przed nami jednak nowe wyzwanie: napisz najkrótsze rozwiązanie algorytmiczne .

adrianton3
źródło
5
Xor jest algorytmiczny.
Peter Taylor

Odpowiedzi:

10

GolfScript, 5 znaków

~(\(^

Rzeczywiście, zadanie to jest bardzo proste po rozpoznaniu wzoru. Jedynym niezręcznym bitem jest indeksowanie oparte na 1 - jeśli indeksy wejściowe byłyby oparte na zerach, to 2-znakowe rozwiązanie wystarczyłoby:

~^

Aby wyjaśnić to czytelnikom niezaznajomionym z językiem GolfScript, ~polecenie sprawdza dane wejściowe, pozostawiając dwie liczby na stosie. ^następnie XOR łączy dwie najwyższe liczby na stosie, pozostawiając wynik dla wyniku. Aby poradzić sobie z (danymi wejściowymi opartymi na 1, potrzebne są jeszcze dwa polecenia: zmniejsza najwyższą liczbę na stosie o jeden, a \zamienia dwa górne elementy na stosie.

Ilmari Karonen
źródło
1
Czy mógłbyś wyjaśnić ^? Odniosłem się do strony z wbudowanymi elementami GolfScript i różnicą symetryczną ; użycie tej operacji z dwoma zestawami tablic ma sens, ale nie rozumiem, jak to działa tylko dla dwóch oddzielnych liczb.
Rob
1
@ Mike: Po zastosowaniu do liczb ^operator zwraca swój bitowy XOR .
Ilmari Karonen
To bardzo fajny związek :)
beary605 30.09.12
1
Miałeś rację, oceniając moją odpowiedź, którą usunąłem, ponieważ opierałem się na błędnej interpretacji wyzwania.
DavidC
2

Mathematica 10 44

Edytować

Moja pierwsza odpowiedź była oparta na nieporozumieniu dotyczącym charakteru wyzwania, jak zauważył Ilmari. Oto kolejna próba.

Stosowanie

f[n___, 1, n___] := n - 1;
j_~f~k_ := BitXor[j - 1, k - 1]
DavidC
źródło
@IlmariKaronen Myślę, że tym razem mam rację. Ale to nawet nie zbliża się do rozmiaru twojego rozwiązania.
DavidC
2

K, 31

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

Logika XOR Stole Ilmari Karonena, której nigdy bym nie zauważył.

tartin
źródło
2

PHP, 38

Po prostu prosta implementacja XOR Ilmari Karonena

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

Stosowanie:

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

wydrukuje 6

scleaver
źródło
2

Haskell 174

Pomyślałem, że stworzę rozwiązanie, które nie będzie oparte na XOR. Zbyt leniwy, aby poprawnie grać w golfa.

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)

Edycja: Dzień później zdałem sobie sprawę, że to tylko obliczenie XOR. Tak więc, jeśli liczy się to jako rozwiązanie algorytmiczne, to również Ilmari Karonen.

walpen
źródło
2
Zbyt leniwy, aby poprawnie grać w golfa. - prosimy o przesłanie golfa, aby był poważnym kandydatem.
Jonathan Frech,
2

Python 2, 36

Wydaje mi się, że odkąd dopiero zaczynam się uczyć Pythona, to byłby idealny czas na przesłanie mojej pierwszej odpowiedzi przy użyciu go (i nikt nie odpowiedział przy użyciu Pythona) i być może mógłbym otrzymać jakieś opinie.

Dziękuję @IlmariKaronen za bardzo fajny skrót.

Dziękuję @Gareth za poniższy kod.

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

Python 3, 56

Oryginalny program, który napisałem.

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

IDEONE z 2 i 5

IDEONE z 3 i 3

Mike Dtrick
źródło
Zakładam, że używasz Python 2 zamiast Python 3 - jeśli nie, zignoruj ​​ten komentarz. inputjuż ocenia dane wejściowe, więc int()nie powinno być to konieczne. Również ponieważ otrzymujesz int bezpośrednio zinput() ciebie, możesz zrobić to -1od razu. Możesz także całkowicie pozbyć się zmiennych pośrednich i przejść od razu print(input()-1^input()-1). Jeśli chodzi o to, czy import jest konieczny - inni użytkownicy Pythona na tej stronie nie uwzględniają go w programach, które go używają input(), ale nie jestem programistą Python, więc nie mogłem powiedzieć, czy jest to konieczne, czy nie.
Gareth
@Gareth Właściwie korzystałem z Pythona 3, ale podoba mi się twoja sugestia print(input()-1^input()-1). Dziękuję za pomoc!
Rob
Czy mogę zapytać, dlaczego importujesz sys?
Jonathan Frech,
2

MATL , 2 bajty

Z~

Wypróbuj online!

MATL wypowiada wyzwanie po kilku latach, ale hej, naturalne indeksowanie 1 i bitowa funkcja xor sprawia, że ​​jest to miłe i schludne!

Giuseppe
źródło
0

Javascript 13 bajtów

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
źródło