Восходящая матрица

17

«Восходящая матрица» представляет собой бесконечную матрицу целых чисел (включая 0), в которой любой элемент является наименьшим доступным элементом, который ранее не использовался в соответствующей строке и столбце:

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

Ваша задача - написать программу, которая будет выводить элемент, найденный в строке и столбце, указанных входными данными. (стандартный ввод и вывод)

Тестовые случаи:

5 3 -> 6
2 5 -> 5

Применяются правила Code Golf - выигрывает самый короткий код.

PS Даже если это имеет алгоритмическую природу, код может быть очень, очень кратким.

РЕДАКТИРОВАТЬ: я не ожидал увидеть решение XOR так рано. Я действительно надеялся увидеть 10 постов с алгоритмическим подходом и затем решение XOR. Теперь, имея в виду, что не очень интересно видеть, как писать xor на разных языках, я рекомендую вам также попробовать алгоритмический подход.

Так что, да, я думаю, что сейчас никто не может побить 5-значную отметку - поэтому я поздравляю Илмари Каронен с самым умным и кратчайшим решением. Но впереди стоит новая задача: написать кратчайшее алгоритмическое решение .

adrianton3
источник
5
Xor является алгоритмическим.
Питер Тейлор

Ответы:

10

GolfScript, 5 символов

~(\(^

Действительно, эта задача очень проста, когда вы узнаете шаблон. Единственный неудобный бит - индексация на основе 1 - если бы входные индексы были на основе нуля, этого двухсимвольного решения было бы достаточно:

~^

Чтобы объяснить это читателям, незнакомым с GolfScript, ~команда пропускает ввод, оставляя два числа в стеке. ^затем XOR объединяет два верхних числа в стеке, оставляя результат для вывода. Чтобы справиться с вводом, основанным на 1, необходимы еще две команды: (уменьшает верхнее число в стеке на одну, а также \меняет два верхних элемента в стеке.

Илмари Каронен
источник
1
Не могли бы вы объяснить ^? Я ссылался на встроенную страницу GolfScript и симметричное различие ; использование этой операции с двумя наборами массивов имеет смысл, но я не понимаю, как она работает только для двух отдельных чисел.
Роб
1
@Mike: применительно к числам ^оператор возвращает их побитовое значение XOR .
Илмари Каронен
Это очень крутые отношения :)
beary605
1
Вы были правы в своей оценке моего ответа, который я с тех пор удалил за неправильное прочтение задачи.
DavidC
2

Mathematica 10 44

редактировать

Мой первый ответ был основан на недоразумении относительно характера проблемы, как отметил Илмари. Вот еще одна попытка.

использование

f[n___, 1, n___] := n - 1;
j_~f~k_ := BitXor[j - 1, k - 1]
DavidC
источник
@IlmariKaronen Думаю, на этот раз я все понял правильно. Но это даже не приближается к размеру вашего решения.
DavidC
2

К, 31

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

Украл XOR-логику Илмари Каронена, которую я никогда бы не заметил.

tmartin
источник
2

PHP, 38

Просто простая реализация XOR Илмари Каронена

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

Использование:

... / xor.php? А = 4 & Ь = 7

напечатает 6

scleaver
источник
2

Haskell 174

Думаю, я бы сделал решение, которое не полагалось на XOR. Лень правильно играть в гольф.

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)

Изменить: день спустя я понял, что это просто вычисление XOR. Таким образом, если это считается алгоритмическим решением, то и Ильмари Каронен.

walpen
источник
2
Лень правильно играть в гольф. - пожалуйста, подайте заявку на участие, чтобы стать серьезным соперником.
Джонатан Фрех
2

Python 2, 36

Я понимаю, так как я только начинаю изучать Python, что это было бы идеальным временем для отправки моего первого ответа, используя его (и никто не ответил с помощью Python), и, возможно, я мог бы получить некоторую обратную связь.

Спасибо @IlmariKaronen за очень крутой ярлык.

Спасибо @Gareth за приведенный ниже код.

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

Python 3, 56

Оригинальная программа, которую я написал.

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

IDEONE с 2 и 5

IDEONE с 3 и 3

оборота Майк Дтрик
источник
Я предполагаю, что вы используете Python 2, а не Python 3 - если не игнорировать этот комментарий. inputуже оценивает ввод, поэтому int()не должно быть необходимости. Кроме того, поскольку вы получаете Int непосредственно от input()вас, вы можете сделать -1прямо сейчас. Вы также можете полностью избавиться от промежуточных переменных и перейти прямо к print(input()-1^input()-1). Относительно того, нужен ли импорт - другие пользователи Python на этом сайте не включают его в программы, которые используют input(), но я не программист Python, поэтому я не мог сказать, нужно это или нет.
Гарет
@Gareth На самом деле я использовал Python 3, но мне нравится ваше предложение использовать print(input()-1^input()-1). Спасибо вам за помощь!
Роб
Могу я спросить, почему вы импортируете sys?
Джонатан Фрех
2

MATL , 2 байта

Z~

Попробуйте онлайн!

MATL откладывает задачу на несколько лет, но естественная индексация на основе 1 и побитовая функция xor делают это красиво и аккуратно!

Giuseppe
источник
0

JavaScript 13 байт

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>

Луис Фелипе Де Иисус Муньос
источник