Instantly share code, notes, and snippets.

Last active February 2, 2024 23:06
Show Gist options
• Save BradonZhang/c93fa7e35f10eda0407c95ac5dbaa78e to your computer and use it in GitHub Desktop.
Can You Race Across the Chess Board?

# Can You Race Across the Chess Board?

## This Week's Fiddler

We can draw a line across the diagonal of the board (top left to bottom right); due to symmetry of the board, the optimal time from the bottom left to the top right is twice the optimal time from the bottom left to said diagonal. Additionally, due to symmetry along the other diagonal, it does not matter if we travel through the top-left white square or the bottom-right white square.

Arbitrarily, let's say we travel through the bottom-right white square. We can say there's a point at $(1, x)$ (in cm) where this happens, where $0\le x\le 1$. The distance travelled in the first black square is $\sqrt{1+x^2}$ with a speed of $0.9$, making a time of $\frac{\sqrt{1+x^2}}{0.9}=\frac{10}{9}\sqrt{1+x^2}$. After crossing, we can beeline to the diagonal (with a slope of 1); the total distance travelled in the white square is $(1-x)\sqrt{2}$. Then the last black square travel is symmetric to the first, making it also $\frac{10}{9}\sqrt{1+x^2}$. This makes the final time:

$2(\frac{10}{9}\sqrt{1+x^2})+(1-x)\sqrt{2}$

Minimum is at $x=\frac{9}{\sqrt{119}}$, making the time needed $\sqrt{2}+\frac{\sqrt{238}}{9}$, or about 3.1284 minutes.

## Extra Credit

We can extend this idea to finding the point of intersection for the 8 by 8 board, except this time we would need 7 variables.

Because it is difficult to solve for the minimum of a 7-variable multivariate function, I used SciPy to find an optimal estimate:

import math

from scipy.optimize import minimize

def alice(X):
ans = (1 - X[-1]) * math.sqrt(2)
for i, (a, b) in enumerate(zip([0, *X[:-1]], X)):
mult = (10 / 9) if (i % 2 == 0) else 1
ans += 2 * mult * math.sqrt((1 - a) ** 2 + b**2)
return ans

print(minimize(alice, (0.5,) * 7, method="Nelder-Mead", tol=0.00001))

Output:

       message: Optimization terminated successfully.
success: True
status: 0
fun: 11.799178130784053
x: [ 5.280e-01  7.501e-01  1.852e-01  1.000e+00  2.090e-09
9.999e-01  6.510e-05]
nit: 872
nfev: 1335
final_simplex: (array([[ 5.280e-01,  7.501e-01, ...,  9.999e-01,
6.510e-05],
[ 5.280e-01,  7.501e-01, ...,  9.999e-01,
6.511e-05],
...,
[ 5.280e-01,  7.501e-01, ...,  9.999e-01,
6.511e-05],
[ 5.280e-01,  7.501e-01, ...,  9.999e-01,
6.513e-05]]), array([ 1.180e+01,  1.180e+01,  1.180e+01,  1.180e+01,
1.180e+01,  1.180e+01,  1.180e+01,  1.180e+01]))


So we have an estimate of about 11.799 minutes.

Just to verify, we can confirm that this function also works for part 1:

print(minimize(alice, (0.5,), method="Nelder-Mead", tol=0.00001))
       message: Optimization terminated successfully.
success: True
status: 0
fun: 3.128352297990603
x: [ 8.250e-01]
nit: 19
nfev: 38
final_simplex: (array([[ 8.250e-01],
[ 8.250e-01]]), array([ 3.128e+00,  3.128e+00]))


3.1284 - nice 😎