O Discador do Cavaleiro
Imagine que você coloca uma peça de xadrez de um cavaleiro em um teclado de discagem de telefone. Esta peça de xadrez se move de chave em chave em forma de "L" maiúsculo: duas etapas horizontalmente seguidas por uma verticalmente, ou uma etapa horizontalmente e depois duas verticalmente:
+-+
|1| 2 3
+-+
`-------v
| +-+
4 | 5 |6|
| +-+
|
|+-+
7 >|8| 9
+-+
0
Suponha que você disque as teclas no teclado usando apenas os saltos que um cavaleiro pode fazer. Cada vez que o cavaleiro pousa em uma tecla, nós a discamos e damos outro salto. A posição inicial conta como salto 0.
Quantos números distintos você pode discar em N saltos a partir de uma determinada posição inicial?
Exemplo
Chave inicial : 6
Número de saltos : 2
Números que podem ser formados :
6 0 6
6 0 4
6 1 6
6 1 8
6 7 2
6 7 6
Portanto, seis números diferentes podem ser formados a partir da chave 6 e com 2 saltos.
Restrições
Entrada: Você receberá dois números como entrada. Você pode misturar essas entradas e usar qualquer formato que desejar. A chave inicial será um número entre 0 e 9, o número de saltos será um número inteiro não negativo sem limite superior.
Saída: você produzirá um único número em qualquer formato que desejar.
Casos de teste
(key,hops) result
(6,0) 1
(6,1) 3
(6,2) 6
(6,10) 4608
(6,20) 18136064
(5,0) 1
(5,1) 0
Pontuação
Este é o código de golfe. Para incentivar a participação no futuro, nenhuma resposta será aceita.
Nota
Isso é fortemente inspirado pelo Dialer do Knight , uma antiga entrevista do Google. Mas tome cuidado, não é idêntico, então não baseie simplesmente sua resposta no código que você vê lá.
Respostas
JavaScript (ES6), 62 61 60 bytes
Minha porta Python , portada de volta para JS. :-p
f=(n,k,o=k%2)=>n--?k-5&&(2-o)*f(n,!k*3-~o)+(k&5&&f(n,o*4)):1
Experimente online!
Abaixo está minha versão original de 62 bytes, que é mais fácil de entender:
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
Experimente online!
Quão?
Existem 4 grupos de teclas que estão realmente conectadas. Todas as chaves em um grupo têm exatamente o mesmo comportamento.
- Corners 1, 3, 7, 9(em verde). Caracterização: chaves ímpares que não são iguais a \$5\$.
- Esquerda / lados direito 4, 6(em azul). Caracterização: até mesmo chaves para as quais temos \$k \operatorname{and}4 = 4\$.
- Principais / lados do fundo 2, 8(em amarelo). Caracterização: chaves pares diferentes de zero para as quais temos \$k \operatorname{and}4 = 0\$.
- A 0chave (em vermelho).
A 5chave é isolada e processada separadamente.
A figura à direita é um gráfico direcionado ponderado que mostra quais grupos de destino podem ser alcançados a partir de um determinado grupo de origem e quantas chaves distintas são destinos válidos em cada grupo de destino.
Este algoritmo faz uma chamada recursiva por grupo alvo do grupo atual, multiplica cada resultado pelo peso correspondente e soma todos eles.
Apenas a primeira iteração está esperando \$k\in[0..9]\$. Para os próximos, apenas definimos \$k\$para a chave principal de cada grupo ( \$1\$, \$4\$, \$2\$e \$0\$ respectivamente).
JavaScript (ES6), 86 74 72 bytes
f=(p,n,k=10)=>n?k--&&(306>>(p*2149^k*2149)%71%35&1&&f(k,n-1))+f(p,n,k):1
Experimente online!
71 bytes
Muito, muito mais lento.
f=(p,n,k=10)=>n?k--&&(306>>(p*2149^k*2149)%71%35&1)*f(k,n-1)+f(p,n,k):1
Experimente online!
Encontrar uma função hash
Estamos procurando uma função \$h(p,k)\$dizendo se \$p\$e \$k\$são conectados por um salto de cavaleiro. Porque esta função é comutativa e porque o resultado é sempre o mesmo quando \$p=k\$, um XOR bit a bit parece um bom candidato.
Não podemos fazer diretamente \$p \operatorname{XOR} k\$porque, por exemplo, \$0 \operatorname{XOR} 4\$e \$3 \operatorname{XOR} 7\$são ambos iguais a \$4\$embora \$(0,4)\$estão conectados e \$(3,7)\$ não são.
Precisamos obter mais entropia aplicando algum multiplicador \$M\$tal que \$(M\times p)\operatorname{XOR}\:(M\times k)\$está livre de colisões. Os primeiros multiplicadores válidos são \$75\$, \$77\$, \$83\$, ... ( Poderíamos aplicar dois multiplicadores distintos para \$p\$e \$k\$, mas perderíamos o benefício da função ser comutativa. Portanto, é improvável que leve a uma expressão menor.)
Para cada multiplicador válido, procuramos alguma cadeia de módulo para reduzir o tamanho da tabela de pesquisa.
Executando uma pesquisa de força bruta com \$M<10000\$e dois modulos \$1<m_0<m_1<100\$seguido por um módulo \$32\$, surge a seguinte expressão:
$$h(p,k)=((((p\times 2149)\operatorname{XOR}\:(k\times 2149))\bmod 71)\bmod 35)\bmod 32$$
Temos um salto válido iff \$h(p,k)\in\{1,4,5,8\}\$, que pode ser representado como a pequena máscara de bits \$100110010_2=306_{10}\$.
Daí a implementação JS:
306 >> (p * 2149 ^ k * 2149) % 71 % 35 & 1
Observe que o módulo final \$32\$ é fornecido implicitamente pelo deslocamento para a direita.
Comentou
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
Jelly , 29 28 bytes
⁵ṗ’;;Ṣe“¡¿Ṅ\ȷḳ€°ị’Ds2¤ʋƝPɗ€S
Um Link diádico que aceita o número de saltos à esquerda e a chave à direita que fornece o número de caminhos.
Experimente online!
Quão?
Forma todos os hopsnúmeros decimais de comprimento , adiciona keycada um e conta quantos têm todos os vizinhos válidos por pesquisa em uma lista compactada. (Observação: quando hopsé zero, o fato de o produto vazio ser um significa que o Link produz 1, conforme desejado.)
Aqui estão outros 28
⁵ṗ’µ;⁴+3!PƝ%⁽W⁶%31fƑ“¤®€×‘)S
Este usa um pouco de aritmética funky para decidir se cada movimento é válido adicionando três a cada um dos dois dígitos, tomando seus fatoriais, multiplicando-os juntos, obtendo o resto após a divisão por \$22885\$, obtendo o resto após a divisão por \$31\$, e verificando se o resultado é um dos \$\{3,8,12,17\}\$.
Python 2 , 83 bytes
f=lambda s,n:n<1or sum(f(i,n-1)for i in range(10)if`i`+`s`in`0x20cb0e9fd6fe45133e`)
Experimente online!
Uma solução recursiva. Verifica os pares de dígitos que são afastados por um cavalo por serem consecutivos na string codificada 604927618343816729406, escrita um byte a menos em hexadecimal. Essa string é um palíndromo porque a relação de adjacência é simétrica, mas não vi uma maneira mais curta de tirar vantagem disso e remover a redundância.
83 bytes
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)
Experimente online!
85 bytes
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]
Experimente online!
Uma ideia diferente com uma solução rápida e iterativa. Aproveitamos a vantagem do gráfico de adjacência do movimento cavaleiro do teclado do telefone ser simétrico:
3--8--1
| |
4--0--6
| |
9--2--7
Observe que 0 não quebra a simetria de cima para baixo do teclado porque ele se conecta apenas a 4 e 6 na linha central. O número 5 não está desenhado; não se conecta a nada.
Usamos a simetria para reduzir a quatro tipos de locais:
a--b--a
| |
c--d--c
| |
a--b--a
a: 1379
b: 28
c: 46
d: 5
Agora temos as transições (algumas aparecendo várias vezes):
a -> b, c
b -> a, a
c -> a, a, d
d -> c, c
Isso corresponde à atualização das contagens em cada etapa de a,b,c,d=b+c,2*a,2*a+d,2*c. Isso pode ser escrito de forma mais curta como a,b=b+c,2*a;c,d=b+d,2*c, conforme apontado por ovs salvando 2 bytes.
Assim, iteramos netapas para produzir os valores correspondentes de a,b,c,d, e agora precisamos selecionar aquele que corresponde ao dígito inicial s. Precisamos de um mapeamento de cada dígito 0-9para a entrada correspondente a,b,c,d, 5indo para n<0. O código usa apenas um selector de cortina direta: [d,a,b,a,c,n<1,c,a,b,a][s].
Provavelmente existe uma maneira mais curta de usar a simetria em que se 10-sestão na mesma categoria e, portanto, podemos fazer algo como s*s%10colapsá-los ou até mesmo s*s%10%8obter uma impressão digital distinta para cada tipo. Com otimizações, esse método pode assumir a liderança.
Python 2 , 68 bytes
Salvo 1 byte graças a @Sisyphus
Salvo mais 5 bytes graças a @xnor
Isso é baseado na lógica usada em minha versão JS de 62 bytes , com uma implementação diferente para tornar mais fácil jogar golfe em Python. Desde então, portei de volta para JS, pois acabou sendo mais curto também.
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)
Experimente online!
Abaixo está um resumo dos resultados retornados por cada expressão, divididos por grupos principais:
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 bytes
eval's/./(46,68,79,48,390,"",170,26,13,24)[$&]/ge;'x<>;$_=y///c
Experimente online!
Carvão , 31 bytes
ＦＮ≔⭆η§⪪”)‴↘Ｓ‴Ｐeυ!&q]3⁰4”¶ＩκηＩＬη
Experimente online! O link é para a versão detalhada do código. Aceita o número de saltos como a primeira entrada. Muito lento para um grande número de saltos. Explicação:
ＦＮ
Insira o número de saltos e repita isso muitas vezes.
≔⭆η§⪪”)‴↘Ｓ‴Ｐeυ!&q]3⁰4”¶Ｉκη
Mapeie cada caractere na string e liste seus próximos saltos possíveis. Exemplo: 6→ 170→ 682646→ 1701379170390170→ ...
ＩＬη
Conte o número total de saltos encontrados.
Versão mais rápida de 44 bytes:
≔Ｅχ⁼ιＩηηＦＮ≔Ｅ⪪”)∧↑mG@⁰EBü)‽₂≕↖”χΣＥκ×Ｉμ§ηνηΣＩη
Experimente online! O link é para a versão detalhada do código. Explicação: Funciona multiplicando repetidamente uma matriz de transição do próximo salto.
Python 3 , 88 bytes
f=lambda s,n:n<1or sum(map(f,'46740 021268983 1634 9 7'[int(s)::10].strip(),[n-1]*3))
Experimente online!
-15 bytes graças ao ovs
-2 bytes graças a Jonathan Allan
k4 , 60 bytes
{#,//y![!10;(4 6;6 8;7 9;4 8;0 3 9;();0 1 7;2 6;1 3;2 4)]/x}
Usa um dicionário para mapear chaves para movimentos válidos, que quando combinados com /funções como uma máquina de estado finito , propagados com x( s) e executados para iterações y( n). ,//nivela o resultado em uma matriz unidimensional.
Testado com:
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 bytes
F•žNjεEÿ¶^²è+%•5¡sèS}g
Quantidade de saltos como primeira entrada e o dígito inicial como segunda entrada.
Experimente online ou verifique todos os casos de teste (exceto aquele com 20 saltos, que atinge o tempo limite).
Explicação:
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)
Veja este 05AB1E ponta do meu (seções Como comprimir grandes inteiros? ) Para entender por que •žNjεEÿ¶^²è+%•é 46568579548530955107526513524.
Linguagem Wolfram , 108 bytes
Tr@MatrixPower[AdjacencyMatrix[4~KnightTourGraph~3~VertexDelete~{10,12}],#2,SparseArray[Mod[#,10,1]->1,10]]&
Experimente online!
Você sabe, provavelmente há uma solução mais curta para isso, mas eu gosto da matemática desta. Isso obtém a matriz de adjacência para o grafo, eleva-a à potência do número de saltos e a multiplica por um vetor que representa de qual chave ele começa. Os elementos do vetor resultante fornecem o número de caminhos para cada chave, portanto, o total fornece o número total de caminhos de um determinado comprimento.
T-SQL, 197 bytes
Retorna nulo para nenhuma solução
Isso pode lidar com 25 saltos em 10 segundos
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=@
Experimente online
Java 8, 137 129 91 89 bytes
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);}
Porta da resposta JavaScript de @Arnauld , fornecida por @ OlivierGrégoire .
-2 byte graças a @ceilingcat .
Experimente online.
Resposta antiga de 137 129 bytes:
(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();}
Dígito inicial como uma entrada String, quantidade de saltos como um inteiro.
Experimente online.
Explicação:
(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