Номеронабиратель рыцаря
Представьте, что вы кладете фигурку коня на клавиатуру телефона. Эта шахматная фигура перемещается от клавиш к клавишам в форме буквы "L" в верхнем регистре: два шага по горизонтали, за которыми следует один по вертикали, или один шаг по горизонтали, затем два по вертикали:
+-+
|1| 2 3
+-+
`-------v
| +-+
4 | 5 |6|
| +-+
|
|+-+
7 >|8| 9
+-+
0
Предположим, вы набираете клавиши на клавиатуре, используя только прыжки, которые может сделать рыцарь. Каждый раз, когда рыцарь приземляется на ключ, мы набираем его и делаем еще один прыжок. Начальная позиция считается переходом 0.
Сколько различных номеров вы можете набрать за N прыжков из определенной начальной позиции?
пример
Стартовый ключ : 6
Количество прыжков : 2
Числа, которые можно образовать :
6 0 6
6 0 4
6 1 6
6 1 8
6 7 2
6 7 6
Таким образом, шесть разных чисел могут быть сформированы из ключа 6 и с двумя переходами.
Ограничения
Ввод: на входе вы получите два числа. Вы можете смешивать эти входные данные и использовать любой желаемый формат. Стартовый ключ будет числом от 0 до 9, количество переходов будет неотрицательным целым числом без верхнего предела.
Вывод: вы выведите одно число в любом желаемом формате.
Тестовые примеры
(key,hops) result
(6,0) 1
(6,1) 3
(6,2) 6
(6,10) 4608
(6,20) 18136064
(5,0) 1
(5,1) 0
Подсчет очков
Это код гольфа. Чтобы стимулировать участие в будущем, ответ не принимается.
Запись
Это во многом навеяно The Knight's Dialer , бывшим интервью Google. Но будьте осторожны, он не идентичен, поэтому не основывайте свой ответ просто на коде, который вы там видите.
Ответы
JavaScript (ES6), 62 61 60 байт
Мой порт Python , перенесенный обратно на JS. :-п
f=(n,k,o=k%2)=>n--?k-5&&(2-o)*f(n,!k*3-~o)+(k&5&&f(n,o*4)):1
Попробуйте онлайн!
Ниже представлена моя оригинальная 62-байтовая версия, которую легче понять:
f=(n,k)=>n--?k&1?k-5&&f(n,2)+f(n,4):2*f(n,k?1:4)+(k&4&&f(n)):1
Попробуйте онлайн!
Как?
Есть 4 группы ключей, которые действительно связаны между собой. Все клавиши в группе ведут себя одинаково.
- Уголки 1, 3, 7, 9(зеленый цвет). Характеристика: нечетные ключи, не равные \$5\$.
- Левая / правая стороны 4, 6(в синем). Характеристика: даже ключи, для которых у нас есть \$k \operatorname{and}4 = 4\$.
- Верх / низ сторона 2, 8(в желтом цвете). Характеристика: ненулевые четные ключи, для которых есть \$k \operatorname{and}4 = 0\$.
- 0Ключ (в красном цвете).
5Ключ уединенный и обрабатывается отдельно.
Рисунок справа - это взвешенный ориентированный график, показывающий, какие целевые группы могут быть достигнуты из данной исходной группы, и сколько отдельных ключей являются действительными целями в каждой целевой группе.
Этот алгоритм выполняет один рекурсивный вызов для каждой целевой группы из текущей группы, умножает каждый результат на соответствующий вес и суммирует их все.
Ожидается только первая итерация \$k\in[0..9]\$. Для следующих мы просто устанавливаем \$k\$к ведущему ключу каждой группы ( \$1\$, \$4\$, \$2\$и \$0\$ соответственно).
JavaScript (ES6), 86 74 72 байта
f=(p,n,k=10)=>n?k--&&(306>>(p*2149^k*2149)%71%35&1&&f(k,n-1))+f(p,n,k):1
Попробуйте онлайн!
71 байт
Намного, намного медленнее.
f=(p,n,k=10)=>n?k--&&(306>>(p*2149^k*2149)%71%35&1)*f(k,n-1)+f(p,n,k):1
Попробуйте онлайн!
Поиск хеш-функции
Ищем функцию \$h(p,k)\$говорит ли \$p\$и \$k\$связаны рыцарским прыжком. Поскольку эта функция коммутативна и результат всегда один и тот же, когда \$p=k\$, побитовый XOR выглядит хорошим кандидатом.
Мы не можем делать напрямую \$p \operatorname{XOR} k\$потому что, например, \$0 \operatorname{XOR} 4\$и \$3 \operatorname{XOR} 7\$оба равны \$4\$хотя \$(0,4)\$связаны и \$(3,7)\$ не.
Нам нужно получить больше энтропии, применив некоторый множитель \$M\$такой, что \$(M\times p)\operatorname{XOR}\:(M\times k)\$без столкновений. Первые несколько действительных множителей : \$75\$, \$77\$, \$83\$, ... (Мы могли бы применить два разных множителя к \$p\$и \$k\$, но мы потеряем преимущество коммутативности функции. Так что вряд ли это приведет к меньшему выражению лица.)
Затем для каждого действительного множителя мы ищем некоторую цепочку по модулю, чтобы уменьшить размер таблицы поиска.
Выполнив поиск методом перебора с \$M<10000\$и два модуля \$1<m_0<m_1<100\$с последующим модулем \$32\$, возникает следующее выражение:
$$h(p,k)=((((p\times 2149)\operatorname{XOR}\:(k\times 2149))\bmod 71)\bmod 35)\bmod 32$$
У нас есть допустимый переход, если \$h(p,k)\in\{1,4,5,8\}\$, который можно представить как маленькую битовую маску \$100110010_2=306_{10}\$.
Отсюда реализация JS:
306 >> (p * 2149 ^ k * 2149) % 71 % 35 & 1
Обратите внимание, что последний по модулю \$32\$ неявно обеспечивается сдвигом вправо.
Прокомментировал
f = ( // f is a recursive function taking:
p, // p = current position
n, // n = number of remaining hops
k = 10 // k = key counter
) => //
n ? // if n is not equal to 0:
k-- && ( // decrement k; if it was not 0:
306 >> // right-shifted lookup bit-mask
(p * 2149 ^ k * 2149) // apply the XOR
% 71 % 35 // apply the modulo chain
& 1 && // if the least significant bit is set:
f(k, n - 1) // do a recursive call with p = k and n - 1
) + //
f(p, n, k) // add the result of a recursive call
// with the updated k
: // else:
1 // stop the recursion
// and increment the final result
Желе , 29 28 байт
⁵ṗ’;;Ṣe“¡¿Ṅ\ȷḳ€°ị’Ds2¤ʋƝPɗ€S
Двоичная ссылка, принимающая количество переходов слева и ключ справа, который дает количество путей.
Попробуйте онлайн!
Как?
Формирует hopsдесятичные числа всей длины , добавляется keyк каждому и подсчитывает количество всех допустимых соседей при поиске в сжатом списке. (Примечание: когда hopsравно нулю, то факт, что пустой продукт равен единице, означает, что ссылка дает 1, как и нужно.)
Вот еще 28
⁵ṗ’µ;⁴+3!PƝ%⁽W⁶%31fƑ“¤®€×‘)S
Здесь используется некоторая забавная арифметика, чтобы решить, является ли каждый ход действительным, добавив по три к каждой из двух цифр, взяв их факториалы, умножив их вместе, получив остаток после деления на \$22885\$, получая остаток от деления на \$31\$, и проверка того, является ли результат одним из \$\{3,8,12,17\}\$.
Python 2 , 83 байта
f=lambda s,n:n<1or sum(f(i,n-1)for i in range(10)if`i`+`s`in`0x20cb0e9fd6fe45133e`)
Попробуйте онлайн!
Рекурсивное решение. Проверяет наличие пар цифр, которые являются ходом коня, поскольку они идут подряд в жестко запрограммированной строке 604927618343816729406, записанной на один байт короче в шестнадцатеричном формате. Эта строка является палиндромом, потому что отношения смежности симметричны, но я не видел более короткого способа воспользоваться этим и удалить избыточность.
83 байта
f=lambda s,n:n<1or sum(f(i,n-1)for i in range(10)if 6030408>>(s*353^i*353)%62%29&1)
Попробуйте онлайн!
85 байт
def f(s,n):a=b=c=d=1;exec"a,b=b+c,2*a;c,d=b+d,2*c;"*n;print[d,a,b,a,c,n<1,c,a,b,a][s]
Попробуйте онлайн!
Другая идея - быстрое итеративное решение. Воспользуемся преимуществом симметричного графа смежности клавиатуры телефона:
3--8--1
| |
4--0--6
| |
9--2--7
Обратите внимание, что 0 не нарушает симметрию верхней и нижней части клавиатуры, потому что он соединяется только с 4 и 6 на центральной линии. Число 5 не выпадает; он ни к чему не подключен.
Мы используем симметрию, чтобы объединить четыре типа локаций:
a--b--a
| |
c--d--c
| |
a--b--a
a: 1379
b: 28
c: 46
d: 5
Теперь у нас есть переходы (некоторые появляются несколько раз):
a -> b, c
b -> a, a
c -> a, a, d
d -> c, c
Это соответствует обновлению счетчиков на каждом шаге a,b,c,d=b+c,2*a,2*a+d,2*c. Это можно записать короче a,b=b+c,2*a;c,d=b+d,2*c, как указано в ovs, сохраняющем 2 байта.
Итак, мы повторяем nшаги, чтобы получить соответствующие значения a,b,c,d, и теперь нам нужно выбрать то, которое соответствует начальной цифре s. Нам нужно сопоставить каждую цифру 0-9с соответствующей записью a,b,c,dс 5переходом к n<0. Код просто использует прямой селектор массива: [d,a,b,a,c,n<1,c,a,b,a][s].
Там, наверное, более короткий путь , используя симметрию , что sи 10-sнаходятся в одной и той же категории, и поэтому мы можем сделать что - то вроде s*s%10разрушаться их, или даже s*s%10%8получить четкий отпечаток пальца для каждого типа. С оптимизацией этот метод может стать лидером.
Python 2 , 68 байт
Сохранено 1 байт благодаря @Sisyphus
Сохранено еще 5 байтов благодаря @xnor
Это основано на логике, использованной в моей 62-байтовой JS-версии , с другой реализацией, чтобы упростить игру в гольф на Python. С тех пор я перенес это обратно на JS, так как он тоже оказался короче.
f=lambda n,k:n<1or k-5and(2-k%2)*f(n-1,4-k%-9%2)+9%~k%2*f(n-1,k%2*2)
Попробуйте онлайн!
Ниже приводится сводка результатов, возвращаемых каждым выражением, с разбивкой по ключевым группам:
expression | 1 3 7 9 | 2 8 | 4 6 | 0 | description
------------+---------+-----+-----+---+---------------------------------------
2-k%2 | 1 1 1 1 | 2 2 | 2 2 | 2 | weight for the 1st recursive call
4-k%-9%2 | 4 4 4 4 | 3 3 | 3 3 | 4 | target key for the 1st recursive call
9%~k%2 | 1 1 1 1 | 1 1 | 0 0 | 0 | weight for the 2nd recursive call
k%2*2 | 2 2 2 2 | 0 0 | - - | - | target key for the 2nd recursive call
Perl 5 , ( -p) 63 байта
eval's/./(46,68,79,48,390,"",170,26,13,24)[$&]/ge;'x<>;$_=y///c
Попробуйте онлайн!
Уголь , 31 байт
ＦＮ≔⭆η§⪪”)‴↘Ｓ‴Ｐeυ!&q]3⁰4”¶ＩκηＩＬη
Попробуйте онлайн! Ссылка на подробную версию кода. Принимает количество прыжков в качестве первого ввода. Слишком медленно для большого количества хмеля. Пояснение:
ＦＮ
Введите количество прыжков и повторите это много раз.
≔⭆η§⪪”)‴↘Ｓ‴Ｐeυ!&q]3⁰4”¶Ｉκη
Сопоставьте каждый символ в строке и перечислите его возможные следующие переходы. Пример: 6→ 170→ 682646→ 1701379170390170→ ...
ＩＬη
Подсчитайте общее количество найденных прыжков.
Более быстрая 44-байтовая версия:
≔Ｅχ⁼ιＩηηＦＮ≔Ｅ⪪”)∧↑mG@⁰EBü)‽₂≕↖”χΣＥκ×Ｉμ§ηνηΣＩη
Попробуйте онлайн! Ссылка на подробную версию кода. Объяснение: Работает путем многократного умножения матрицы перехода следующего шага.
Python 3 , 88 байт
f=lambda s,n:n<1or sum(map(f,'46740 021268983 1634 9 7'[int(s)::10].strip(),[n-1]*3))
Попробуйте онлайн!
-15 байт благодаря ovs
-2 байта благодаря Джонатану Аллану
k4 , 60 байт
{#,//y![!10;(4 6;6 8;7 9;4 8;0 3 9;();0 1 7;2 6;1 3;2 4)]/x}
Использует словарь для сопоставления ключей с действительными ходами, которые в сочетании с /функциями в качестве конечного автомата , заполняются с помощью x( s) и выполняются для итераций y( n). ,//сводит результат в одномерный массив.
Протестировано с:
1 3 6 4608 18136064 1 0~{#,//y![!10;(4 6;6 8;7 9;4 8;0 3 9;();0 1 7;2 6;1 3;2 4)]/x}.'(6 0;6 1;6 2;6 10;6 20;5 0;5 1)
05AB1E , 24 22 байта
F•žNjεEÿ¶^²è+%•5¡sèS}g
Количество прыжков в качестве первого ввода и начальная цифра в качестве второго ввода.
Попробуйте онлайн или проверьте все тестовые примеры (кроме одного с 20 прыжками, время ожидания которого истекло).
Пояснение:
F # Loop the first (implicit) input amount of times:
•žNjεEÿ¶^²è+%• # Push compressed integer 46568579548530955107526513524
5¡ # Split it on 5: [46,68,79,48,309,"",107,26,13,24]
s # Swap to take the current list of digits,
# or the second (implicit) input in the first iteration
è # (0-based) index those into this list
S # Convert it to a flattened list of digits
# ("" becomes an empty list [])
}g # After the loop: pop the list of digits, and take its length
# (after which the result is output implicitly)
Посмотрите этот мой совет 05AB1E (разделы Как сжимать большие целые числа? ), Чтобы понять, почему •žNjεEÿ¶^²è+%•это так 46568579548530955107526513524.
Язык Wolfram Language , 108 байт
Tr@MatrixPower[AdjacencyMatrix[4~KnightTourGraph~3~VertexDelete~{10,12}],#2,SparseArray[Mod[#,10,1]->1,10]]&
Попробуйте онлайн!
Вы знаете, возможно, есть более короткое решение для этого, но мне нравится математика этого. Он получает матрицу смежности для графа, возводит ее в степень числа переходов и умножает ее на вектор, представляющий, с какого ключа он начинается. Элементы результирующего вектора дают количество путей к каждому ключу, поэтому сумма дает общее количество путей данной длины.
T-SQL, 197 байт
Если нет решений, возвращает null
Это может обработать 25 прыжков за 10 секунд.
WITH C as(SELECT 0i,1*translate(@n,'37986','11124')x,1q
UNION ALL
SELECT-~i,y,q*(2+1/~(y*~-a))FROM(values(1,4),(1,2),(4,0),(2,1),(4,1),(0,4))x(a,y),c
WHERE a=x AND i<@)
SELECT
sum(q)FROM C
WHERE i=@
Попробуйте онлайн
Java 8, 137 129 91 89 байт
int f(int n,int k){return--n<0?1:k%2>0?k==5?0:f(n,2)+f(n,4):2*f(n,k>0?1:4)+k/4%2*f(n,0);}
Порт ответа JavaScript @Arnauld , предоставленный @ OlivierGrégoire .
-2 байта благодаря @ceilingcat .
Попробуйте онлайн.
Старые 137 129 байт ответа:
(s,h)->{for(;h-->0;){var t="";for(var c:s.getBytes())t+="46,68,79,48,309,,107,26,13,24".split(",")[c-48];s=t;}return s.length();}
Начальная цифра как строковый ввод, количество переходов как целое число.
Попробуйте онлайн.
Пояснение:
(s,h)->{ // Method with String & integer parameter & integer return
for(;h-->0;){ // Loop the integer amount of times:
var t=""; // Temp-String, starting empty
for(var c:s.getBytes()) // Inner loop over the digit-codepoint of the String:
t+= // Append to the temp-String:
"46,68,79,48,309,,107,26,13,24".split(",")[c-48]);
// The keys the current digit can knight-jump to
s=t;} // After the inner loop, replace `s` with the temp-String
return s.length();} // Return the length of the String as result