yuuki's research

< yuuki

Generation of all strings

Generating all possible strings over a given alphabet is difficult. I don't know what algorithm to use. In Python, you can use itertools.product in a simple case:

from itertools import product

MAX_LENGTH = 6

alphabet = (
    "a", "b", "c", "d", "e", "f", "g",
    "h", "i", "j", "k", "l", "m", "n",
    "o", "p", "q", "r", "s", "t", "u",
    "v", "w", "x", "y", "z",
)

for length in range(1, MAX_LENGTH + 1):
    for chars in product(alphabet, repeat=length):
        print("".join(chars))

# Output:
# a
# b
# ...
# z
# aa
# ab
# ...
# zz
# aaa
# ...
# zzzzzz

Total number of strings

There are 26 strings from "a" to "z", and $26^2$ from "aa" to "zz". The total number of strings of length $n$ or less is

$26 + 26^2 + \cdots + 26^n = \displaystyle \frac{26(26^n - 1)}{25}$.

In general, the sum of the first $n$ terms of a geometric sequence with first term $r$ and common ratio $r$ is $\frac{r(1 - r^n)}{1 - r}$:

$\begin{aligned} r + r^2 + \cdots + r^n &amp;= \frac{(r + r^2 + \cdots + r^n)(1 - r)}{1 - r} \\ &amp;= \frac{\begin{aligned} r &amp;+ r^2 + \cdots + r^n \\ &amp;- r^2 - \cdots - r^n - r^{n + 1} \end{aligned}}{1 - r} \\ &amp;= \frac{r - r^{n + 1}}{1 - r} \\ &amp;= \frac{r(1 - r^n)}{1 - r} \end{aligned}$

The following are 44 of the Japanese alphabet (gojūon) written in rōmaji. Including "n" causes collisions; "na", "ni", "nu", etc. are generated twice.

alphabet = (
    "a", "i", "u", "e", "o",
    "ka", "ki", "ku", "ke", "ko",
    "sa", "shi", "su", "se", "so",
    "ta", "chi", "tsu", "te", "to",
    "na", "ni", "nu", "ne", "no",
    "ha", "hi", "fu", "he", "ho",
    "ma", "mi", "mu", "me", "mo",
    "ya", "yu", "yo",
    "ra", "ri", "ru", "re", "ro",
    "wa",
)

The number of rōmaji strings of length $n$ satisfies the third-order homogeneous linear recurrence relation with constant coefficients

$a_n = 5a_{n - 1} + 36a_{n - 2} + 3a_{n - 3}$,

with initial conditions $a_1 = 5$, $a_2 = 61$, and $a_3 = 488$.

$n$	$a_n$	$26^n$
1	5	26
2	61	676
3	488	17,576
4	4,651	456,976
5	41,006	11,881,376
6	373,930	308,915,776

Planes with perspective

When you are at $(0, 0)$, the bot touches you when it is at $(50, 0)$, a distance of 50.

However, when you are at $(0, 200)$, the bot touches you when it is at $(30, 200)$, a distance of only 30.

What is the formula to find the bot's position $(x', y')$ from your position $(x, y)$ so that the bot follows you?

Answer

When $y = 0$:

$x' = x + 50$

When $y = 200$:

$x' = x + 30$

We see that $x'$ depends on $y$. Let $x' = x + f(y)$. Assume $f(y) = ay + b$. Then:

$\left\{ \begin{alignedat}{3} &amp; f(0) &amp;&amp;= b &amp;&amp;= 50 \\ &amp; f(200) &amp;&amp;= 200a + b &amp;&amp;= 30 \end{alignedat} \right.$

Therefore, $f(y) = -\frac{y}{10} + 50$. The answer is the two-dimensional affine transformation:

$\left\{ \begin{alignedat}{2} &amp; x' &amp;&amp;= x - \frac{y}{10} + 50 \\ &amp; y' &amp;&amp;= y \end{alignedat} \right.$

$\iff \begin{pmatrix} x' \\ y' \end{pmatrix} = \begin{pmatrix} 1 &amp; -\frac{1}{10} \\ 0 &amp; 1 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} + \begin{pmatrix} 50 \\ 0 \end{pmatrix}$