Prarie Riddler

prarie.py

#!/usr/bin/env python

import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import minimize

'''
Parameterize a solution space so all numbers are valid:
    Solver coordinates are given as arctanh(radius), theta
Then minimize the inverse average distance (to maximize average distance).

Empirically, it only finds results that have average distance to closest neighbor is 1.
'''


def norm(unnorm_r, unnorm_theta):
    ''' Convert from unnormalized coordinates to X, Y coordinates '''
    r = np.tanh(unnorm_r)
    theta = np.mod(unnorm_theta, np.pi * 2)
    return np.array([r * np.cos(theta), r * np.sin(theta)])


def dist(x):
    ''' Calculate average min-neighbor distance given unnormalized polar coordinates '''
    points = [norm(un_r, un_theta) for un_r, un_theta in x.reshape((6, 2))]
    total = 0
    for i, p in enumerate(points):
        min_neighbor = 10
        for j, q in enumerate(points):
            if i == j:
                continue  # skip same point
            neighbor = np.sqrt(np.sum(np.square(p - q)))
            min_neighbor = min(neighbor, min_neighbor)
        total += min_neighbor
    return -total / 6  # (inverse) average min neighbor distance


def plot(x):
    ''' Plot out the results to double-check '''
    points = np.array([norm(un_r, un_theta) for un_r, un_theta in x.reshape((6, 2))])
    circle = np.linspace(0, np.pi * 2, 1000)
    plt.scatter(np.cos(circle), np.sin(circle))
    plt.scatter(points[:, 0], points[:, 1])
    plt.show()


if __name__ == '__main__':
    results = minimize(dist, np.random.randn(6 * 2))
    plot(results.x)
    print('average min-neighbor distance', -dist(results.x))  # 1.000