Hacker News new | ask | show | jobs
by losvedir 5365 days ago
Ha, well that was a lot easier than I made it.

I ended up with the right answer by finding the minimum of the equation

    f(x,y) = 2(sqrt(1+x^2) + sqrt((6-x)^2 + y^2) + sqrt((15-y)^2 + 36))
which is the length of the path taken if the ant goes up to the ceiling at a point x to the East of straight up, and from there goes to the side wall at a point y to the south, and then goes from there to the center of that wall. (And then it's mirrored).

I should have thought to unravel the room! Errr.
2 comments
tzs 5365 days ago
To make the "minimize the equation" approach complete, other paths should be considered, such as instead of going up to the ceiling, going to the side and taking a side wall.

Some limits can be placed on the number of possible paths by considering some general properties of an optimal solution:

1. Assuming the start point is A, and the path leaves the start side at point B, the optimal path will take a straight line from A to B. Proof: if it were not straight, it could be replaced by a straight line which would shorten the path, contradicting the assumption the path was optimum.

2. Once the optimal path leaves a side, it will not return to that side. Proof. Suppose the path leaves the side at point B, then later enters at C, and then leaves again at D. The route from B to C could be replaced with a straight line from C to D, which would shorten the path, again contradicting the assumption that the path was optimum.

This cuts down the number of possible path templates greatly, since a given surface can only appear once in the optimal path, and only contain a single straight line segment.

I expect that a little more reasoning can deduce some more limits on possible optimal paths, to get it down to just two or three possible equations to maximize.

link
d0mine 5365 days ago
for the unraveled room:

  sqrt(1+x^2) + sqrt((6-x)^2+y^2)+sqrt(12^2+z^2)+
  sqrt((30-z-y)^2+u^2)+sqrt((6-u)^2+1)

  40 at {x -> 0.75, y -> 7, z -> 16, u -> 5.25}
http://www.wolframalpha.com/input/?i=minimize%5B%7Bsqrt%281%...

your equation: http://www.wolframalpha.com/input/?i=minimize+2%28sqrt%281%2...

link