I am solving a problem about T9 Keyboard and knight movement:
We have found a device which have a classic keyboard like below.
|1|2|3|
|4|5|6|
|7|8|9|
|*|0|#|
This device is protected by a secret password. We don't know what the password is,
but after several hours of reversing we know that the password was generated by
following the rules:
1, The password has length of n, and contains characters as shown on the keyboard.
2, The password must end with either *, 8 or #.
3, After one character, the character which is on the knight move pattern (as the
knight in chess) can be the next character. For example, if the current character
is 3, then the next character can be either 4 or 8.
We really want to know how many passwords can be generated given length n, so that
we can know whether to give up brute-force or not. Ah, because that number may be
very large so you just need to give us the answer modulo 1e39.
These are something I calculated:
We can create password from the last character, which are *, # and 8. nAsterisk(x), nSharp(x), nEight(x) will be the number of possible x-length passwords I used brute-force to calculate several cases and receive a table like this:
| x | fAsterisk | fSharp | fEight |
|---|---|---|---|
| 0 | 1 | 1 | 1 |
| 1 | 2 | 2 | 2 |
| 2 | 5 | 5 | 4 |
| 3 | 11 | 11 | 10 |
| 4 | 28 | 28 | 22 |
| 5 | 65 | 65 | 56 |
| 6 | 163 | 163 | 130 |
| 7 | 388 | 388 | 326 |
| 8 | 961 | 961 | 776 |
| 9 | 2315 | 2315 | 1922 |
I saw several patterns:
fAsterisk = fSharp for every x, and also
fEight(x) = fAsterisk(x-1)*2
The thing I am very struggle is the last pattern I found:
fAsterisk(x) = fAsterisk(x-1)*2+numberOfChildNodeThatHaveThreeAdjacentButton
For example:
*
/ \
5 9
/ \ / | \
* # 2 4 7
fAsterisk(2) here is 5, and it equals fAsterisk(1)*2 + 1 because we only have 9 as a node that have 3 adjacents. After calculate, I have a serie for this number:
0,1,1,6,9,33,62,185,393,1062,...
I am wonder that if there is a way to calculate the number of nodes have 3 adjacents or not. Or is there any better way or pattern to solve this problems. I tried brute-force way but the number is too big that I can't calculated for x = 88.
For a character set $S$, let $f_S(n)$ be the number of passwords of length $n$ ending in character $x$ when $x\in S$. Let $A=\{1,3,*,\#\}$, $B=\{2,0\}$, $C=\{4,6,7,9\}$, $D=\{5,8\}$. We are looking for $g(n):=2f_A(n)+f_D(n)$.
By inspection, we find recurrence relations such as $$ f_A(n)=f_C(n-1)+f_D(n-1)$$ and $$ f_C(n)=f_A(n-1)+f_B(n-1)+f_C(n-1)$$ and similar equations for $f_B(n)$ and $f_D(n)$. Then solve these linear recurrences (noting that $f_S(0)=1$ for all $S$).
To elaborate, with $\mathbf f(n)=(f_A(n),f_B(n),f_C(n),f_D(n))^T$, we find $$ \mathbf f(n)=M\cdot\mathbf f(n-1)$$ with the matrix $$ M=\begin{pmatrix}0&0&1&1\\ 0&0&2&0\\ 1&1&1&0\\ 2&0&0&0 \end{pmatrix}.$$ Note that this in particular contains your observation that $f_D(n)=2f_A(n-1)$.
Now one way to solve the original problem is to compute $M^n\bmod 10 ^{39}$ by the well-known square-and-multiply method in $O(\log n)$ time (and using non-negative integers $<10^{78}$ as intermediate results) and multiplying it with $\mathbf f(0)=(1,1,1,1)^T$.
Given that one only wants to find one value instead of four, one may alternatively want to get rid of the additional three variables. But at best, this will take you to a four-term linear recursion. Of course, we may readily find a good approximation $g(n)\approx c\lambda_\max^n$ where $c$ is some constant and $\lambda_\max$ the greatest eigenvalue of $M$ (for the record, $\lambda_\max\approx 2.438283239$). However, this won't help for the original problem of finding $g(n)$ exactly modulo some integer.