Il dialer del cavaliere

Question

Immagina di posizionare un pezzo degli scacchi del cavaliere sulla tastiera di un telefono. Questo pezzo degli scacchi si sposta dalle chiavi alle chiavi a forma di "L" maiuscola: due passi orizzontalmente seguiti da uno verticalmente, o un passo orizzontalmente e due verticalmente:

 +-+
 |1|   2    3 
 +-+
    `-------v
     |     +-+
  4  | 5   |6|
     |     +-+
     |
     |+-+
  7  >|8|   9
      +-+


       0

Supponi di comporre i tasti sulla tastiera utilizzando solo i salti che un cavaliere può fare. Ogni volta che il cavaliere atterra su una chiave, componiamo quella chiave e facciamo un altro salto. La posizione iniziale conta come hop 0.

Quanti numeri distinti puoi comporre in N salti da una particolare posizione di partenza?

Esempio

Tasto di avviamento : 6
Numero di salti : 2

Numeri che possono essere formati :

6 0 6
6 0 4
6 1 6
6 1 8
6 7 2
6 7 6

Quindi sei numeri diversi possono essere formati dal tasto 6 e con 2 salti.

Vincoli

Input: riceverai due numeri come input. Puoi combinare questi input e utilizzare qualsiasi formato desideri. La chiave di partenza sarà un numero compreso tra 0 e 9, il numero di salti sarà un numero intero non negativo senza limite superiore.

Output: produrrà un singolo numero in qualsiasi formato desideri.

Casi test

(key,hops)   result

(6,0)         1
(6,1)         3
(6,2)         6
(6,10)        4608
(6,20)        18136064
(5,0)         1
(5,1)         0

Punteggio

Questo è il golf in codice. Per incoraggiare la partecipazione in futuro, nessuna risposta sarà accettata.

Nota

Questo è fortemente ispirato da The Knight's Dialer , un'ex intervista di Google. Ma fai attenzione, non è identico, quindi non basare semplicemente la tua risposta sul codice che vedi lì.

Answer 1

JavaScript (ES6),  62 61  60 byte

Il mio port Python , riportato su 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

Provalo online!

Di seguito è la mia versione originale a 62 byte, che è più facile da capire:

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

Provalo online!

Come?

Ci sono 4 gruppi di chiavi che sono realmente collegati tra loro. Tutte le chiavi all'interno di un gruppo hanno lo stesso identico comportamento.

• Angoli 1, 3, 7, 9(in verde). Caratterizzazione: chiavi dispari che non sono uguali a \$5\$.
• Lati sinistro / destro 4, 6(in blu). Caratterizzazione: anche le chiavi per le quali abbiamo \$k \operatorname{and}4 = 4\$.
• Lati superiore / inferiore 2, 8(in giallo). Caratterizzazione: chiavi pari diverse da zero per le quali abbiamo \$k \operatorname{and}4 = 0\$.
• La 0chiave (in rosso).

La 5chiave è isolata e processata separatamente.

La figura a destra è un grafico orientato ponderato che mostra quali gruppi di destinazione possono essere raggiunti da un dato gruppo di origine e quante chiavi distinte sono obiettivi validi all'interno di ciascun gruppo di destinazione.

Questo algoritmo esegue una chiamata ricorsiva per gruppo target dal gruppo corrente, moltiplica ogni risultato per il peso corrispondente e li somma tutti.

Si aspetta solo la prima iterazione \$k\in[0..9]\$. Per i prossimi, abbiamo solo impostato \$k\$alla chiave iniziale di ogni gruppo ( \$1\$, \$4\$, \$2\$e \$0\$ rispettivamente).

---

JavaScript (ES6),  86 74  72 byte

f=(p,n,k=10)=>n?k--&&(306>>(p*2149^k*2149)%71%35&1&&f(k,n-1))+f(p,n,k):1

Provalo online!

71 byte

Molto, molto più 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

Provalo online!

Trovare una funzione hash

Stiamo cercando una funzione \$h(p,k)\$dire se \$p\$e \$k\$sono collegati da un cavaliere hop. Perché questa funzione è commutativa e perché il risultato è sempre lo stesso quando \$p=k\$, uno XOR bit per bit sembra un buon candidato.

Non possiamo farlo direttamente \$p \operatorname{XOR} k\$perché, ad esempio, \$0 \operatorname{XOR} 4\$e \$3 \operatorname{XOR} 7\$sono entrambi uguali a \$4\$sebbene \$(0,4)\$sono collegati e \$(3,7)\$ non sono.

Dobbiamo ottenere più entropia applicando un moltiplicatore \$M\$tale che \$(M\times p)\operatorname{XOR}\:(M\times k)\$è privo di collisioni. I primi pochi moltiplicatori validi sono \$75\$, \$77\$, \$83\$, ... (Noi potremmo applicare due moltiplicatori distinte \$p\$e \$k\$, ma perderemmo il vantaggio della funzione commutativa. Quindi è improbabile che porti a un'espressione più piccola.)

Per ogni moltiplicatore valido, cerchiamo quindi una catena di moduli per ridurre la dimensione della tabella di ricerca.

Eseguendo una ricerca a forza bruta con \$M<10000\$e due moduli \$1<m_0<m_1<100\$seguito da un modulo \$32\$, si presenta la seguente espressione:

$$h(p,k)=((((p\times 2149)\operatorname{XOR}\:(k\times 2149))\bmod 71)\bmod 35)\bmod 32$$

Abbiamo un hop valido iff \$h(p,k)\in\{1,4,5,8\}\$, che può essere rappresentato come la piccola maschera di bit \$100110010_2=306_{10}\$.

Da qui l'implementazione JS:

306 >> (p * 2149 ^ k * 2149) % 71 % 35 & 1

Nota che il modulo finale \$32\$ è implicitamente fornito dallo spostamento a destra.

Commentato

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

Answer 2

Gelatina ,  29  28 byte

⁵ṗ’;;Ṣe“¡¿Ṅ\ȷḳ€°ị’Ds2¤ʋƝPɗ€S

Un collegamento diadico che accetta il numero di salti a sinistra e il tasto a destra che fornisce il numero di percorsi.

Provalo online!

Come?

Forma tutti hopsi numeri decimali di lunghezza , antepone keya ciascuno e conta quanti hanno tutti i vicini validi mediante ricerca in un elenco compresso. (Nota: quando hopsè zero, il fatto che il prodotto vuoto sia uno significa che Link restituisce 1, come desiderato.)

---

Eccone un altro 28

⁵ṗ’µ;⁴+3!PƝ%⁽W⁶%31fƑ“¤®€×‘)S

Questo usa un po 'di aritmetica funky per decidere se ogni mossa è valida aggiungendo tre a ciascuna delle due cifre, prendendo i loro fattoriali, moltiplicandoli insieme, ottenendo il resto dopo la divisione per \$22885\$, ottenendo il resto dopo la divisione per \$31\$e controllando se il risultato è uno di \$\{3,8,12,17\}\$.

Answer 3

Python 2 , 83 byte

f=lambda s,n:n<1or sum(f(i,n-1)for i in range(10)if`i`+`s`in`0x20cb0e9fd6fe45133e`)

Provalo online!

Una soluzione ricorsiva. Verifica la presenza di coppie di cifre che si allontanano da un cavaliere poiché sono consecutive nella stringa codificata 604927618343816729406, scritta un byte più corta in esadecimale. Questa stringa è un palindromo perché la relazione di adiacenza è simmetrica, ma non ho visto un modo più breve per trarne vantaggio e rimuovere la ridondanza.

83 byte

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)

Provalo online!

85 byte

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]

Provalo online!

Un'idea diversa che fornisce una soluzione rapida e iterativa. Approfittiamo del fatto che il grafico di adiacenza della mossa del cavaliere della tastiera del telefono è simmetrico:

3--8--1
|     |
4--0--6
|     |
9--2--7 

Notare che 0 non interrompe la simmetria alto-basso della tastiera perché si collega solo a 4 e 6 sulla linea centrale. Il numero 5 non è estratto; non si collega a niente.

Usiamo la simmetria per collassare in quattro tipi di posizioni:

a--b--a
|     |
c--d--c
|     |
a--b--a 

a: 1379
b: 28
c: 46
d: 5

Ora abbiamo le transizioni (alcune appaiono più volte):

a -> b, c
b -> a, a
c -> a, a, d
d -> c, c    

Ciò corrisponde all'aggiornamento dei conteggi in ogni fase di a,b,c,d=b+c,2*a,2*a+d,2*c. Questo può essere scritto più breve come a,b=b+c,2*a;c,d=b+d,2*c, come sottolineato da ovs che salva 2 byte.

Quindi, ripetiamo i npassaggi per produrre i valori corrispondenti di a,b,c,d, e ora dobbiamo selezionare quello corrispondente alla cifra iniziale s. Abbiamo bisogno di una mappatura di ogni cifra 0-9alla voce corrispondente a,b,c,d, con 5andando a n<0. Il codice utilizza solo un selettore di matrice diretta: [d,a,b,a,c,n<1,c,a,b,a][s].

Probabilmente c'è un modo più breve per usare la simmetria che se 10-ssono nella stessa categoria, quindi possiamo fare qualcosa come s*s%10comprimerli o anche s*s%10%8per ottenere un'impronta digitale distinta per ogni tipo. Con le ottimizzazioni, questo metodo potrebbe prendere l'iniziativa.

Answer 4

Python 2 , 68 byte

Salvato 1 byte grazie a @Sisyphus
Salvati altri 5 byte grazie a @xnor

Questo si basa sulla logica utilizzata nella mia versione JS a 62 byte , con un'implementazione diversa per rendere più facile il golf in Python. Da allora l'ho riportato su JS, poiché si è rivelato anche più breve.

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)

Provalo online!

Di seguito è riportato un riepilogo dei risultati restituiti da ciascuna espressione, suddivisi per gruppi chiave:

 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

Answer 5

Perl 5 , ( -p) 63 byte

eval's/./(46,68,79,48,390,"",170,26,13,24)[$&]/ge;'x<>;$_=y///c

Provalo online!

Answer 6

Carboncino , 31 byte

ＦＮ≔⭆η§⪪”)‴↘Ｓ‴Ｐeυ!&q]3⁰4”¶ＩκηＩＬη

Provalo online! Il collegamento è alla versione dettagliata del codice. Prende il numero di salti come primo input. Troppo lento per un gran numero di luppoli. Spiegazione:

ＦＮ

Immettere il numero di salti e ripetere più volte.

≔⭆η§⪪”)‴↘Ｓ‴Ｐeυ!&q]3⁰4”¶Ｉκη

Mappa su ogni carattere nella stringa ed elenca i suoi possibili salti successivi. Esempio: 6→ 170→ 682646→ 1701379170390170→ ...

ＩＬη

Contare il numero totale di luppoli trovati.

Versione più veloce a 44 byte:

≔Ｅχ⁼ιＩηηＦＮ≔Ｅ⪪”)∧↑mG@⁰EBü)‽₂≕↖”χΣＥκ×Ｉμ§ηνηΣＩη

Provalo online! Il collegamento è alla versione dettagliata del codice. Spiegazione: funziona moltiplicando ripetutamente una matrice di transizione hop successivo.

Answer 7

Python 3 , 88 byte

f=lambda s,n:n<1or sum(map(f,'46740 021268983 1634    9 7'[int(s)::10].strip(),[n-1]*3))

Provalo online!

-15 byte grazie a ovs

-2 byte grazie a Jonathan Allan

Answer 8

k4 , 60 byte

{#,//y![!10;(4 6;6 8;7 9;4 8;0 3 9;();0 1 7;2 6;1 3;2 4)]/x}

Utilizza un dizionario per mappare le chiavi a mosse valide, che se combinate con /funzioni come una macchina a stati finiti , vengono seminate con x( s) e vengono eseguite per y( n) iterazioni. ,//appiattisce il risultato in una matrice unidimensionale.

Testato con:

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)

Answer 9

05AB1E , 24 22 byte

F•žNjεEÿ¶^²è+%•5¡sèS}g

Quantità di salti come primo input e cifra iniziale come secondo input.

Provalo online o verifica tutti i casi di test (eccetto quello con 20 hop, che scade).

Spiegazione:

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)

Vedi questo mio suggerimento 05AB1E (sezioni Come comprimere numeri interi grandi? ) Per capire perché •žNjεEÿ¶^²è+%•è 46568579548530955107526513524.

Answer 10

Lingua Wolfram , 108 byte

Tr@MatrixPower[AdjacencyMatrix[4~KnightTourGraph~3~VertexDelete~{10,12}],#2,SparseArray[Mod[#,10,1]->1,10]]&

Provalo online!

Sai, probabilmente c'è una soluzione più breve per questo, ma mi piace la matematica di questo. Questo ottiene la matrice di adiacenza per il grafico, la eleva alla potenza del numero di salti e la moltiplica per un vettore che rappresenta da quale chiave parte. Gli elementi del vettore risultante danno il numero di percorsi a ciascuna chiave, quindi il totale fornisce il numero totale di percorsi di una data lunghezza.

Answer 11

T-SQL, 197 byte

Restituisce null per nessuna soluzione

Questo può gestire 25 salti in 10 secondi

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=@

Provalo online

Answer 12

Java 8, 137 129 91 89 byte

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);}

Port of @Arnauld 's JavaScript answer , fornito da @ OlivierGrégoire .
-2 byte grazie a @ceilingcat .

Provalo online.

Vecchi 137 129 byte rispondono:

(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();}

Cifra iniziale come input di stringa, quantità di salti come numero intero.

Provalo online.

Spiegazione:

(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