#!/usr/bin/python
"""Use hill-climbing to solve a simple problem.

I was trying to use the Law of Cosines to solve a simple problem: if
shaft center B is 11 mm from shaft center A and 11 mm from shaft center
C, and A and C are 13 mm apart, how far is B from the line AC?

I got snarled up in confusing sines with cosines, so I thought to try
the following brute-force approach: just use hill-climbing to solve the
problem.  We know what the solution looks like and how to quantify how
far we are from it, so let's just hill-climb with random restarts.

It works far better than it has any right to, but then I saw how to
solve the problem in closed form without trigonometric functions.  At
first I had a bug due to using a step function p() that was always
positive, and that made it not work very well.

It still takes several seconds to run on my netbook; some kind of
gradient descent would probably be better.

"""

import numpy

def search(f, p, restarts=30, steps=30):
    "Simple hill-climbing in a continuous space with random restarts."
    best = None
    for start in range(restarts):
        current = p()
        current_badness = f(current)
        for size in range(20):
            for i in range(steps):
                # Start with steps of size 256*p and end with steps of
                # size p/4294967296.
                new = current + p() * 4**(4-size)
                new_badness = f(new)
                if new_badness < current_badness:
                    current, current_badness = new, new_badness
        #print current, current_badness
        if best is None or best[1] > current_badness:
            best = current, current_badness

    return best

def distance(p1, p2):
    return ((p1 - p2)**2).sum()**0.5

def badness(guess):
    return ((distance(guess, (0, 0)) - 11)**2 +
            (distance(guess, (13, 0)) - 11)**2)

if __name__ == '__main__':
    print(search(badness, lambda: numpy.random.rand(2) - 0.5))