yuuki's research

< yuuki

String generation

Generating all possible strings over a given alphabet is difficult. In Python, you can use itertools.product in a simple case:

from itertools import product

MAX_LENGTH = 5

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
# ...
# zzzzz

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 $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 elements of the Japanese alphabet (gojūon) written in rōmaji. Including "n" causes collisions; "na", "ni", 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}$

Function identification

Data

	0JAuF0
0	iWNbkU
1	bgRFgs
2	Ctipm0
3	Z+DHC8
4	3riK4c
5	oFkyFk
6	oKzaX4
7	YPqcak
8	eV2DBw
9	Jdp+Zg
A	1BhV5w
B	0BaqIs
C	DkAeOU
D	1DApu8
E	4vaQls
F	Et6Q4I
G	G8r490
H	F5QhQg
I	MmBPMc
J	Hsv4X4
K	I0X3SM
L	vmdUCU
M	ty4XUA
N	ok/sl0
O	6TfUFg
P	XiCA+Y
Q	G7H7BM
R	kw4pCM
S	fNQT7Q
T	DLxTeE
U	jo/eyI
V	m3TMqI
W	it09hU
X	9weMNA
Y	wSuV1M
Z	gLCCzE
a	orob88
b	ltOY6g
c	CWxa58
d	nAq7ds
e	36Bzk4
f	u7DOkc
g	2R4/2c
h	aZfOac
i	pP5fYU
j	9Ytf2k
k	7YNrD0
l	mff9qY
m	fJG1ig
n	17OC+M
o	pSupHk
p	Q7IqQM
q	bHewwY
r	m0eWdg
s	RRCH0c
t	cc7Mp0
u	PEumbo
v	VnpGDI
w	vYjjlw
x	e4GRUM
y	zwjpgY
z	93pV5M