Northcott's Game of Soldiers

I wrote a small applet that you can use to play Northcott's Game of Soldiers.

The game works as follows:

1. There are 4 planks, each with 5,7,11 or 13 spaces.
2. Each turn, a player can move one of his soldiers to any free space on the same plank, which is not located behind the enemy soldier. A soldier cannot remain on the same square.
3. The first player who does not have a valid move loses. (So the soldiers are pinned against the back of the plank with the other soldier right before it.)

You can play against the AI by clicking on the plank were you want the soldier to move, and the AI will do the same.

Attributions: Soldier SVG Vector by svgrepo under the CC0 license. / recolored and rescaled.

Submarine hunting

You know that a submarine is travelling in an infinite ocean, at a constant speed, in a constant direction. Each second you can bomb a point of choice, and each submarine within a distance ϵ of that point will be destroyed. Is it possible to device a bombing strategy that will certainly destroy the submarine at a finite point in time.

Source

One dimensional case

First will will solve a simpler version, where the submarines can move in a line, not on a plane.

Our submarine has 2 free variables, it's position at time 0 x₀ and it's velocity v. Its position at time t will be x₀ + vt. If we bomb the ocean at position x, the submarine will be destroyed if
x − ϵ < x₀ + vt < x + ϵ
.

Instead of looking at this like bombing a one-dimensional area at different times with moving submarines, we can look at this as bombing a two dimensional area (x, v) where the submarine is at a fixed point (x, v) and not moving. Each bomb we launch covers the area described by the above equation. So we can rewrite our question as follows:

Find a function f : ℤ⁺ → ℝ such that:
{(x,v)∈ℝ²|−ϵ<x₀+vt−f(t)<ϵ}
covers the plain.

If we can find a subset of this set that covers the plane, then the original set also covers the plane.

This figure describes different "areas" that would be bombed if we bomb at time t at position f(t). Each submarine with starting position x and speed v will be destroyed by a specific bombing if the point on the graph is coloured in that respective colour.

Take a look at this equation
−ϵ/2 < x₀ − f₁(t)<ϵ/2 ∩ −ϵ/2 < vt − f₂(t)<ϵ/2

It is easy to see that if f(x)=f₁(x)+f₂(x), this equations implies the above equation (just sum the two equations). It is also easy to see that the bottom equation descibes rectangles with sizes ϵ x ϵ/t where we can choose the position freely.

This figure you can see in blue our original area, and in yellow our new area. You can easily see that orange is a subset of blue, so if our orange tiles can tile the plane, blue can cover it.

Therefore, if we can cover a plane with rectangles with sizes ϵ x ϵ/t, we can destroy the submarine.

To tile our rectangles, we will decide to tile them as follows:

Each lane, marked in red, contains stacked rectangles of different sizes. Each line is also numbered in red, and each rectangle is stacked as follows:

1. The first rectangle is stacked in the respective lane. if l is the lane number, v will be ( − 1)^⌊l/2⌋⌊l/4⌋ϵ.
2. For odd numbered lanes, the following values of x will have added a negative sign.
3. The first rectangle added to the lane will be put at x = u₀/2
4. The second rectangle added to the lane will be stacked on top. x = u₀ + u₁/2
5. Each additional rectangle will be stacked at $x=\sum^{n-1}_{i=0} u_i + u_n/2$

Where u_i is the i-th value assigned to the respective lane.

To tile the full plane, all we have to do is assign each rectancle at the correct lane, such that the sum of every lane will be infinite.

We can do it like this: if at t the prime decomposition has two unique primes, assign it to the lane of the lowest prime. If it isn't do whatever (or skip, or bomb (0,0), nobody cares).

The total sum assigned to a lane will be
$$\frac{1}{p_l} \sum_{i=l}^{\infty} \frac{1}{p_i}$$
And due to this property this will diverge.

Putting this all together, we arrive at the following strategy.

1. Calculate prime decomposition of t
2. If t does not have two primes, bomb 0
3. Otherwise, call l and k the two indexes of the primes
4. calculate v = ( − 1)^⌊l/2⌋⌊l/4⌋ϵ
5. calculate $x=\frac{1}{p_l} \sum_{i=l}^{k-1} \frac{1}{p_i} + \frac{1}{2p_lp_k}$
6. bomb ( − 1)^lx + v/t

Two dimensional case

We use the same technique as for the two dimensional case. This time our submarine has 4 free variables, its position at time 0 (x₀, y₀) and it's velocity (v_x, v_y) The position of a submarine at time t will be
(x₀ + v_xt, y₀ + v_yt)
If we bomb the ocean at position (x, y), the submarine will be destroyed if
(x₀ + v_xt − x)² + (y₀ + v_yt − y)² < ϵ²

Analogious to the previous case, our problem can be restated as follows:

Find a function f : ℤ⁺ → ℝ² such that
{(x,y,v,w)∈ℝ⁴|(x+vt−x(t))²+(y+wt−y(t))²<ϵ²}
is a cover. (where f(t)=(x(t),y(t)))

For this to be a cover, it has to be a cover for every subset. Take the subset (0, 0, v, w). The intersection of our original set with the subset is
{(0,0,v,w)∈ℝ⁴|(vt−x(t))²+(wt−y(t))²<ϵ²}
This can be simplified to
$$\left\{(0,0,v,w) \in \mathbb{R}^4 \middle|\left(v-\frac{x(t)}{t}\right)^2 + \left(w-\frac{y(t)}{t}\right)^2 < \frac{\epsilon^2}{t^2}\right\}$$

This expression is never a cover for the full plane, as this is a set of circles with a surface area of $\frac{\epsilon^2\pi}{t^2}$ The total measure of this cover is $\frac{\epsilon^2\pi^3}{6}$ (source), so this measure can never cover the full plane as it have finite area.

digit problem

Find all natural numbers, for which, if you knock off the first digit, the remaining number is a divisor of the original number.
You can find these numbers here: https://oeis.org/A292683

First of, let us write our number as
$y*10^n + x$ with the extra conditions $y<10$ and $x< 10^n$.
$x$ is obviously the number with the first digit removed, so we have to find all $x$, $y$ and $n$ such that there exists a natural number $z$ such that:
$zx = y*10^n+x$

$(z-1)x = y*10^n$

As the left and right side of the equation have the same prime decomposition, we can find 4 new numbers, $a,b,c$ and $d$ such that:
$\begin{aligned} ab&=x\\cd&=z-1\\ac&=y\\bd&=10^n \end{aligned}$

The last one: $bd=10^n$ can for the same reason be simplified to $b=2^k5^l$ and $d=2^{n-k}5^{n-l}$, simplifing everying to:
$\begin{aligned} x&=a2^k5^l\\z&=c2^{n-k}5^{n-l}+1\\y&=ac \end{aligned}$
We are uninterested in the value of z, so this mean that our original value is:
$ac10^n+a2^k5^l$
with the extra conditions of $ac < 10$ and $n > \log_{10}(a2^k5^l)$
The second condition can be smoothed by replacing $n$ by $m+\lceil{\log_{10}(a2^k5^l)}\rceil$
As all numbers are natural numbers anyway. This reduces the expression to

$ac10^{m+\lceil{\log_{10}(a2^k5^l)}\rceil}+a2^k5^l$
$m,k$ and $l$ can assume any natural number, $a$ and $c$ can assume the following pairs:
(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(4,1),(4,2),(5,1),(6,1),(7,1),(8,1) or (9,1).

Each combination generates a unique number, and each number is generated by this formula.

hexagonal grid of resistors

On this infinite hexagonal grid of ideal one-ohm resistors, what’s the equivalent resistance between the two marked nodes?

This is a variation of the following xkcd:

Of which the solution can be found here: https://www.mathpages.com/home/kmath668/kmath668.htm

As this is already a really difficult problem, one might assume that a hexagonal grid makes this problem even harder. And in general, this obviously does, but these two marked points are close enough together that we can use the symmetries of the system to calculate the resistance.

First, let’s use the same method and assumptions of the system in the provided solution. We apply a current of 1 Amp to one of the nodes, and a current of -1 Amp to the other node, and calculate the potential difference between them. Due to the linearity of the system, one can use the Superposition principle to only apply a single current at one of the nodes, and use the symmetry to state that applying the other one will cause the same difference in potential. So we only have to solve the potential difference between our two nodes, given that there is an external current of 1 Amp in one marked node, and one of zero everywhere. Our solution will then be twice this potential difference.

If we apply a current of 1 Amp to a node, the current will flow out as follows:

The currents marked in blue are all equal, so are the currents marked in green, due to the symmetry of the system. ## Kirchhoff’s current law tells us that the current over in the blue arrows is $1/3A$ and that the current over the green arrows is $1/6A$. This also equals the voltage over this resistor, as all resistances are $1\Omega$. Thus our effective resistance between the two nodes is
$2 \left(\frac{1}{3}+\frac{1}{6}\right)$
Which is equal to 1. So our effective resistance is $1\Omega$

Regex (Advent of Code)

This blog describes the solution to this puzzle https://adventofcode.com/2020/day/2, that came out the same day as this blog is written. Although it is very easy to solve this puzzle with python or even with a google spreadsheet, in this blog, I will solve it in the esoteric language Retina. For those of you who never heard of this language, the linked page gives the following explanation:

Retina is a regex-based recreational programming language. Every program works by reading a (finite) string from standard input, transforming it via a series of regex operations (e.g. counting matches, filtering lines, and most of all substituting). Retina was built on top of .NET’s regex engine, but provides its own, more powerful substitution syntax.

As retina does not allow reading or writing files, the input from the puzzle will be provided via stdin.

The two solutions in runnable form can be found here: Part 1 and Part 2.

Part 1

For part one we have to count the lines of the form 1-3 a: abcde wherein the password (string at the end), the number of times the letter (before the colon) appear between “minimum” and “maximum” times (the indicated numbers).
The code does the following:

%(`

Do for every line

(\d+)\-(\d+) (.): (.+)

Select the minimum, maximum, letter and password. They are stored in $1 $2 $3 and $4
So, for example, if our input was 1-3 b: abbc the variables would respectively be 1, 3, “b” and “abbc”

K`$1,$2:$4¶$3¶_

Build for the given variables the following string

K`<mimimum>,<maximum>:<password>
<letter>
_

So for our previous example, this string becomes

K`1,3:abbc
b
_

This is in itself a retina program, that takes the password, and replaces each occurrence of <letter> in the password with an underscore. <mimimum>,<maximum>: is prepended, but as they do not contain any letters, this piece is unaffected by the replace statement.

~`$-
_

Executes the code given by the struct. $- means the result of the last expression (so the code described above). As the code does not take any input, the underscore is ignored. The result is something of the form 1,3: a__c.

[a-z]*
<whitespace>

Delete all lowercase letters. The result is something of the form 1,3:__. It has the minimum and maximum, and contains a list of underscores with its length equal to the number of occurrences of <letter>

:(_*)$

This matches the underscores after the colon.

:$.($1)

Replaces the previous match with the length of the string, which is the number of underscores. The result will be something like 1,3:2

^(\d+),(\d+):(\d+)$
$1;$3;$2

Extract the 3 numbers, and puts them in in a comma seperated list, with the mesured lenght in the middle.
In our example, this will be 1,2,3.
Note that if our measured length is between minimum and maximum, this list will be sorted.

N`\d+

Sort the list.

^
$-1x

Append the previous expression (the unsorted list) to the current expression. In our example, the value will now be 1,2,3x1,2,3

^(.*)x\1$
ok

This replaces the full string with ok if the expression before the ‘x’ is the same as the expression after the ‘x’. This only happens when our list was already sorted before the sort operation.

)*`

End the Per-line mode and concatenate all lines.
Now we only have to count all occurrences of ok, and we have our list. We do that by just typing ok

If you try it with your own puzzle input, make sure to not add a trailing enter, as the procedure above replaces an empty string by ok, so it will count empty lines.

part 2

For part one we have to count the lines of the form 1-3 a: abcde where either the first or third element of our password is the correct letter. Note that this is one indexed, contrary to the superior and more practical zero indexing. This we will have to keep in mind later.

%(`

Again we start with “for every line”

(\d+)\-(\d+) (.): (.+)

Same as above. Extract the variables.

K`a$4¶^(.){$1}(.).$*$$¶$$2¶K`a$4¶^(.){$2}(.).$*$$¶$$-1$3$$2

Build the following string

K`a<password>
^(.){<first index>}(.).*$
$2
K`a<password>
^(.){$2}(.).*$
$-1<letter>$2

This is in itself a retina program, that works as following:

K`a<password>

Create a string with the password. We prepend an “a” to make our indices work. As the following code assumes the password is zero-indexed, but it is one indexed, we can apply an extra character to the front of our password to shift all indices by one.

^(.){<first index>}(.).*$

Select the letter at the index of <first index>. The first part of the regex ^(.){<first index>} matches <first index> characters, so $2 will be matched with the first character after it, which is the <first index>-th character. .*$ matches the rest of the string, to make sure the full string is replaced.

$2

Replace the full string with $2, which was the needed character.
The next three lines of code do the same thing, except for the second number. And at the end instead of only selecting the needed character, you also add the previous one and the original letter.
Executing this code leaves us with three letters, and we have to check if one of the side letters matches the middle letter, but not both. This can be done by first deleting all triples, which is done by this piece of code:

m`(.)\1\1

And then count all doubles, stated by this piece:

m`(.)\1

This will give the correct results in every case.

Velociraptor pursuit

Today, we are going to solve the second question of this xkcd: https://xkcd.com/135/

You’re at the centre of a 20m equilateral triangle with a raptor at each corner. The top raptor has a wounded leg and is limited to a top speed of 10 m/s.
The raptors will run toward you. At what angle should you run to maximize the time you stay alive?
(It is assumed that you have a speed of 6m/s and the unwounded velociraptor has a top speed of 25 m/s, from the first question). We are also removing the fact that the velociraptors and you have to speed up, and assume they are going at full speed at the start.

Pursuit curve

First, we are going to take a look at the following problem:

Assume a velociraptor starts running in your direction with a speed of $k$ times you speed, while you start at point $(A_x, A_y)$ running in the $y$ direction, what is the distance you can run?
According to wikipedia, the $y$ coordinate of the capture point is $\lim _{x\to A_{x}}y(x)={\frac {1}{2}}\left({\frac {A_{y}+{\sqrt {A_{x}^{2}+A_{y}^{2}}}}{1-{\frac {V_{t}}{V_{d}}}}}+{\frac {A_{y}-{\sqrt {A_{x}^{2}+A_{y}^{2}}}}{1+{\frac {V_{t}}{V_{d}}}}}\right)$
Thus the distance ran is
$d = {\frac {1}{2}}\left({\frac {A_{y}+{\sqrt {A_{x}^{2}+A_{y}^{2}}}}{1-{\frac {V_{t}}{V_{d}}}}}+{\frac {A_{y}-{\sqrt {A_{x}^{2}+A_{y}^{2}}}}{1+{\frac {V_{t}}{V_{d}}}}}\right) - A_y$
If we swap $\frac {V_{t}}{V_{d}}$ by $k$ and $A_x$ by $R\cos(\alpha)$ and $A_y$ by $R\sin(\alpha)$ we get:

$\begin{aligned}d &= {\frac {1}{2}}\left({\frac {R\sin(\alpha)+R}{1-k}}+{\frac {R\sin(\alpha)-R}{1+k}}\right) - R\sin(\alpha)\\ &= {\frac {1}{2}}{\frac {(R\sin(\alpha)+R)(1+k)+(R\sin(\alpha)-R)(1-k)}{1-k^2}} - R\sin(\alpha)\\ &= {\frac {R\sin(\alpha)+R+R\sin(\alpha)k+Rk+R\sin(\alpha)-R-R\sin(\alpha)k+Rk}{2-2k^2}} - R\sin(\alpha)\\ &= {\frac {R\sin(\alpha)+Rk}{1-k^2}} - R\sin(\alpha)\\ &= R\left({\frac {\sin(\alpha)+k- \sin(\alpha)+k^2\sin(\alpha)}{1-k^2}} \right)\\ &= Rk\left({\frac {1+k\sin(\alpha)}{1-k^2}} \right)\\\end{aligned}$

The time you can stay alive is relative to the distance you can run, as you can run at constant speed. If the angle you run at is $\theta$, the time you stay alive in total is the minimal time you stay alive considering each individual raptor.
So the minimal of these three expressions:
$Rk\left({\frac {1-k\cos(\alpha+2\pi/3)}{1-k^2}} \right)$
$Rk\left({\frac {1-k\cos(\alpha+4\pi/3)}{1-k^2}} \right)$
$R\kappa\left({\frac {1-\kappa\cos(\alpha)}{1-\kappa^2}} \right)$

Where $\kappa$ is your speed over the speed of the wounded velociraptor $6/10$ and $k$ is the speed of a healthy velociraptor over your speed $6/25$. Plotting the survival time for each velociraptor gives us the following figure.

We get a rather surprising result. The bottom velociraptors can catch up with us before the top one, independent of the angle, so we can ignore it. This also means that the optimal strategy is running towards the wounded velociraptor.