27
\$\begingroup\$

Imagine you place a knight chess piece on a phone dial pad. This chess piece moves from keys to keys in an uppercase "L" shape: two steps horizontally followed by one vertically, or one step horizontally then two vertically:

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


       0

Suppose you dial keys on the keypad using only hops a knight can make. Every time the knight lands on a key, we dial that key and make another hop. The starting position counts as hop 0.

How many distinct numbers can you dial in N hops from a particular starting position?

Example

Starting key: 6
Number of hops: 2

Numbers that can be formed:

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

So six different numbers can be formed from the key 6 and with 2 hops.

Constraints

Input: You will receive two numbers as input. You can mix those input and use any format you wish. The starting key will be a number between 0 and 9, the number of hops will be a nonnegative integer with no upper limit.

Output: You will output a single number in any format you want.

Test cases

(key,hops)   result

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

Scoring

This is code golf. To encourage participation in the future, no answer will be accepted.

Note

This is strongly inspired by The Knight's Dialer, a former Google interview. But be careful, it's not identical, so don't simply base your answer on the code you see there.

\$\endgroup\$
  • \$\begingroup\$ Sandbox \$\endgroup\$ – Olivier Grégoire Oct 18 at 22:12
  • 1
    \$\begingroup\$ "from 0 to positive infinity included" to be clear, you must special case some input symbol for infinity (or use a builtin if your language supports it) and then return it back? \$\endgroup\$ – Jonah Oct 19 at 3:30
  • \$\begingroup\$ @Jonah No, infinity is not an integer, I don't even think it's a number: here it merely means that there are no limits on the number of digits in that number you'll get, even though 20 is already a good challenge for computers if you don't memoize or find an appropriate lengthy algorithm. \$\endgroup\$ – Olivier Grégoire Oct 19 at 8:33
  • \$\begingroup\$ Incorrect Example Solution The Example Answer provided to the Knight's Dialer puzzle is incorrect. There are only 3 solutions, not six: 604, 618 and 672. The other 3 numbers are invalid because they start and end with the same digit, which does not conform to the capital L movement of a knight in chess, which always lands on a different square than from which it moved. \$\endgroup\$ – Robert E Conner Oct 19 at 15:09
  • 4
    \$\begingroup\$ @RobertEConner a knight is allowed to return on its next move, unless there is a particular variant of chess I'm unfamiliar with. \$\endgroup\$ – IanF1 Oct 19 at 17:51

12 Answers 12

20
\$\begingroup\$

JavaScript (ES6),  62 61  60 bytes

My Python port, ported back to 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

Try it online!

Below is my original 62-byte version, which is easier to understand:

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

Try it online!

How?

There are 4 groups of keys which are really connected together. All keys within a group have the exact same behavior.

  • Corners 1, 3, 7, 9 (in green). Characterization: odd keys that are not equal to \$5\$.
  • Left/right sides 4, 6 (in blue). Characterization: even keys for which we have \$k \operatorname{and}4 = 4\$.
  • Top/bottom sides 2, 8 (in yellow). Characterization: non-zero even keys for which we have \$k \operatorname{and}4 = 0\$.
  • The 0 key (in red).

The 5 key is secluded and processed separately.

The figure on the right is a weighted directed graph showing which target groups can be reached from a given source group, and how many distinct keys are valid targets within each target group.

keypad and graph

This algorithm does one recursive call per target group from the current group, multiplies each result by the corresponding weight and sums them all.

Only the first iteration is expecting \$k\in[0..9]\$. For the next ones, we just set \$k\$ to the leading key of each group (\$1\$, \$4\$, \$2\$ and \$0\$ respectively).


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

Try it online!

71 bytes

Much, much slower.

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

Try it online!

Finding a hash function

We are looking for a function \$h(p,k)\$ telling whether \$p\$ and \$k\$ are connected by a knight hop. Because this function is commutative and because the result is always the same when \$p=k\$, a bitwise XOR looks like a good candidate.

We can't directly do \$p \operatorname{XOR} k\$ because, for instance, \$0 \operatorname{XOR} 4\$ and \$3 \operatorname{XOR} 7\$ are both equal to \$4\$ although \$(0,4)\$ are connected and \$(3,7)\$ are not.

We need to get more entropy by applying some multiplier \$M\$ such that \$(M\times p)\operatorname{XOR}\:(M\times k)\$ is collision-free. The first few valid multipliers are \$75\$, \$77\$, \$83\$, ... (We could apply two distinct multipliers to \$p\$ and \$k\$, but we would lose the benefit of the function being commutative. So it's unlikely to lead to a smaller expression.)

For each valid multiplier, we then look for some modulo chain to reduce the size of the lookup table.

By running a brute-force search with \$M<10000\$ and two modulos \$1<m_0<m_1<100\$ followed by a modulo \$32\$, the following expression arises:

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

We have a valid hop iff \$h(p,k)\in\{1,4,5,8\}\$, which can be represented as the small bit-mask \$100110010_2=306_{10}\$.

Hence the JS implementation:

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

Note that the final modulo \$32\$ is implicitly provided by the right-shift.

Commented

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ +1 for detailed explanation of the magic number derivation \$\endgroup\$ – Jonah Oct 19 at 17:09
  • \$\begingroup\$ I don't understand why your 71-byter is "much, much slower" than the 72 one. It looks to me that you are doing the same recursive calls. Btw, I'm very impressed with your work on both solutions... but that doesn't surprise me anymore. Good job +1 \$\endgroup\$ – RGS Oct 22 at 9:03
  • 1
    \$\begingroup\$ @RGS The key difference is that the recursive call in v && f(k,n-1) is processed only if v is truthy, whereas it is always processed if we do v * f(k,n-1), no matter the value of v. \$\endgroup\$ – Arnauld Oct 22 at 9:09
  • \$\begingroup\$ This new implementation seems so simple in regards to what you had previously, and the explnations make it so easy to understand. It's very impressive! \$\endgroup\$ – Olivier Grégoire Oct 22 at 12:27
5
\$\begingroup\$

Jelly,  29  28 bytes

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

A dyadic Link accepting the number of hops on the left and the key on the right which yields the number of paths.

Try it online!

How?

Forms all length hops decimal numbers, prepends key to each and counts how many have all valid neighbours by lookup in a compressed list. (Note: when hops is zero the fact that the empty product is one means the Link yields 1, as desired.)


Here is another 28

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

This one uses some funky arithmetic to decide whether each move is valid by adding three to each of the two digits, taking their factorials, multiplying these together, getting the remainder after division by \$22885\$, getting the remainder after division by \$31\$, and checking if the result is one of \$\{3,8,12,17\}\$.

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

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`)

Try it online!

A recursive solution. Checks for pairs of digits that are a knight's move away by them being consecutive in the hardcoded string 604927618343816729406, written one byte shorter in hex. This string is a palindrome because the adjacency relationship being symmetric, but I didn't see a shorter way to take advantage of that and remove the redundancy.

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)

Try it 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]

Try it online!

A different idea giving a fast, iterative solution. We take advantage of the knight-move adjacency graph of the phone keypad being symmetric:

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

Note that 0 doesn't break the top-bottom symmetry of the keypad because it connects just to 4 and 6 on the centerline. The number 5 is isn't drawn; it doesn't connect to anything.

We use the symmetry to collapse down to four types of locations:

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

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

We now have the transitions (some appearing multiple times):

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

This corresponds to the update of counts at each step of a,b,c,d=b+c,2*a,2*a+d,2*c. This can be written shorter as a,b=b+c,2*a;c,d=b+d,2*c, as pointed out by ovs saving 2 bytes.

So, we iterate n steps to produce the correspond values of a,b,c,d, and now we need to select the one corresponding to the start digit s. We need a mapping of each digit 0-9 to the corresponding entry a,b,c,d, with 5 going to n<0. The code just uses a direct array selector: [d,a,b,a,c,n<1,c,a,b,a][s].

There's probably a shorter way using the symmetry that s and 10-s are in the same category, and so we can do something like s*s%10 to collapse these, or even s*s%10%8 to get a distinct fingerprint for each type. With optimizations, this method might take the lead.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You can save two bytes on the iterative solution with a,b=b+c,2*a;c,d=b+d,2*c;. \$\endgroup\$ – ovs Oct 19 at 21:59
  • \$\begingroup\$ @ovs Thanks, nice find! \$\endgroup\$ – xnor Oct 19 at 22:02
  • \$\begingroup\$ This solution is very neat. [d,a,c,n<1,b][s**6%280%6] is 1 byte shorter than [d,a,b,a,c,n<1,c,a,b,a][s]. I'm sure there's another byte somewhere! \$\endgroup\$ – Sisyphus Oct 20 at 3:06
  • 1
    \$\begingroup\$ @Arnauld Fascinating now that all three (quite distinct) approaches score 83 bytes! \$\endgroup\$ – Sisyphus Oct 21 at 0:50
  • 1
    \$\begingroup\$ It probably would have saved me some time if I had pay more attention to your explanation about the clusters rather than figuring it out by myself. :-/ At any rate, getting this down to 74 bytes (73 thanks to @Sisyphus) was laborious but fun! \$\endgroup\$ – Arnauld Oct 22 at 11:04
5
+300
\$\begingroup\$

Python 2, 68 bytes

Saved 1 byte thanks to @Sisyphus
Saved 5 more bytes thanks to @xnor

This is based on the logic used in my 62-byte JS version, with a different implementation to make it easier to golf in Python. I've since ported this back to JS, as it turned out to be shorter as well.

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)

Try it online!

Below is a summary of the results returned by each expression, split by key groups:

 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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Very elegant solution! You can save a byte by writing (k&5>0)*f(n-1,k%2*4) instead of (k&5and f(n-1,k%2*4)). \$\endgroup\$ – Sisyphus Oct 22 at 10:56
  • \$\begingroup\$ @Sisyphus Ah yes, I missed that one. Thank you! \$\endgroup\$ – Arnauld Oct 22 at 11:01
  • 1
    \$\begingroup\$ Nice solution! I thought something like this would be possible, but didn't expect that it would be by choosing how to recurse via code logic rather than some hardcoded constant. \$\endgroup\$ – xnor Oct 22 at 20:27
  • \$\begingroup\$ I looked at golfing this some more and got it down to 68. I can show you or wait in case you (or @Sisyphus) want to think about it, whichever you prefer. \$\endgroup\$ – xnor Oct 23 at 21:12
  • 1
    \$\begingroup\$ @Arnauld 68 bytes My optimizations are switching 2 and 4 in the 1379 case to regularize the table a bit, changing the 1 digit to a 3 to allow a simpler expression, and mod magic for some expressions. Curious if you have any ideas. I wasn't able to shorten the (2-k%2)* even though it looks long. \$\endgroup\$ – xnor Oct 24 at 10:37
4
\$\begingroup\$

Perl 5, (-p) 63 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

Charcoal, 31 bytes

FN≔⭆η§⪪”)‴↘S‴Peυ!&q]3⁰4”¶IκηILη

Try it online! Link is to verbose version of code. Takes the number of hops as the first input. Too slow for large numbers of hops. Explanation:

FN

Input the number of hops and repeat that many times.

≔⭆η§⪪”)‴↘S‴Peυ!&q]3⁰4”¶Iκη

Map over every character in the string and list its possible next hops. Example: 61706826461701379170390170 → ...

ILη

Count the total number of hops found.

Faster 44-byte version:

≔Eχ⁼ιIηηFN≔E⪪”)∧↑mG@⁰EBü)‽₂≕↖”χΣEκ×Iμ§ηνηΣIη

Try it online! Link is to verbose version of code. Explanation: Works by repeatedly multiplying a next hop transition matrix.

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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

Try it online!

-15 bytes thanks to ovs

-2 bytes thanks to Jonathan Allan

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 96 bytes with a more compact lookup table \$\endgroup\$ – ovs Oct 19 at 10:00
  • \$\begingroup\$ n<1or ... saves two (outputting True for 1 is fine since they behave the same when used as a number). \$\endgroup\$ – Jonathan Allan Oct 19 at 18:39
3
\$\begingroup\$

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}

Uses a dictionary to map keys to valid moves, which when combined with / functions as a finite-state machine, seeded with x (s) and run for y (n) iterations. ,// flattens the result into a one dimensional array.

Tested with:

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)
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 24 22 bytes

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

Amount of hops as first input, and the starting digit as second input.

Try it online or verify all test cases (except for the one with 20 hops, which times out).

Explanation:

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)

See this 05AB1E tip of mine (sections How to compress large integers?) to understand why •žNjεEÿ¶^²è+%• is 46568579548530955107526513524.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language, 108 bytes

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

Try it online!

You know, there's probably a shorter solution for this, but I enjoy the mathematics of this one. This gets the adjacency matrix for the graph, raises it to the power of the number of jumps, and multiplies it by a vector representing which key it starts from. The elements of the resulting vector give the number of paths to each key, so the total gives the total number of paths of a given length.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

T-SQL, 197 bytes

Returns null for no solutions

This can handle 25 hops in 10 seconds

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

Try it online

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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

Port of @Arnauld's JavaScript answer, provided by @OlivierGrégoire.
-2 byte thanks to @ceilingcat.

Try it online.

Old 137 129 bytes answer:

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

Starting digit as a String input, amount of hops as an integer.

Try it online.

Explanation:

(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
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.