18
$\begingroup$

My 8-yr old has gotten bored creating conventional mazes, and has taken to creating variants that look like this:

Number Hopper Sample

The idea is to start from x and reach o via the normal rules. Additionally, you can "hop" from any integer $a$ to any other integer $b$, but you must pay $|a-b|$ dollars for the privilege. The goal is to solve the maze for the least cost. In the example above, we could go from x to o via x-14-18-27-28-o at cost 5, but it's cheaper to go x-13-11-9-8-29-28-o for only 4.

So here is my question: what is the best solution (in terms of asymptotic running time) you can think of for solving this? You may make any reasonable assumptions about the input format.

Note: I am using the "puzzles" tag here because I have an $O(n^2)$ answer in mind, but I'm not sure it's optimal and would like to see if someone else can improve my solution. (Here $n$ is the number of integers in the maze.)

Improve this question
$\endgroup$
10
  • 7
    $\begingroup$ Props to your child for creating such creative and mathematical puzzles! $\endgroup$
    – bbejot
    May 2, 2011 at 4:12
  • 2
    $\begingroup$ @bbejot You should see some of the stuff he asks me... sometimes I can't answer his questions. Eg, math.stackexchange.com/questions/33094/… $\endgroup$
    – Fixee
    May 2, 2011 at 4:19
  • 1
    $\begingroup$ I'm not sure that your cost calculations are correct. x-14-18-27-28-o should cost $4 + 9 + 1 = 14$ and x-13-11-9-8-29-28-o should cost $2 + 2 + 1 + 21 + 1 = 27$. $\endgroup$
    – Dave Clarke
    May 2, 2011 at 14:45
  • 1
    $\begingroup$ @Dave not all of the transitions are jumps. We could write 'a-b' for jumps (which have a cost of $|a - b|$) and 'a->b' for walking in the graph from a to b (which has a cost of $0$), which is allowed only if they are reachable without breaking a wall in the maze. In this notation we have x->14-18->27-28->o and a cost of 5 and x->13-11->9-8->29-28->o. I thin Fixee did not introduce this notation on account of it being redundant: there is no reason to hop twice and thus hops and walks in the maze will alternate. $\endgroup$
    – Artem Kaznatcheev ♦
    May 2, 2011 at 15:00
  • 2
    $\begingroup$ This is an excellent homework problem! $\endgroup$
    – Jeffε
    May 3, 2011 at 22:05

2 Answers 2

Reset to default
15
$\begingroup$

You can solve this in $O(n\log n)$ time using a variation of Dijkstra's algorithm. We can get away with not performing all distance updates when we visit a new node. If we visit a node $y$, we need only to update the distances of everything walkable from $y$ to 0, and to update the distances to the two nodes $y_-$ and $y_+$ with the closest values to $y$ less and greater than $y$ which have not been picked yet.

These updates are sufficient to keep the heap returning the minimum element because any closest node you jump to must have been numerically just above or just below an already visited node.

Each node gets updated to 0 at most once (if we pop out all zero distance nodes from the queue to avoid quadratic behavior), and each time we add a node, we only do O(1) other updates. Finding the values $y_-$ and $y_+$ can be done in linear time if we also keep an ordered doubly-linked list of all the nodes, sorted by their integer values. Building this doubly-linked list takes $O(n \log n)$ time, and finally the $O(n)$ updates to and pops from the heap take $O(n \log n)$ time, for a total runtime of $O(n \log n)$

Improve this answer
$\endgroup$
3
  • $\begingroup$ This can probably be improved a little using sorting and priority queues which are specialized for integers, but you can't do better than integer sorting, as can be seen by the following reduction: if we have a list of integer values $x_1,\ldots,x_n$, set $x$ to be twice the minimum of these and $o$ to be twice the maximum. Create a region with values $2x_i$ and $2x_i+1$ for each other $x_i$. The best solution goes through each region in sorted order by $x_i$, and thus produces a sorting of the $x_i$ values. $\endgroup$
    – Dave
    May 3, 2011 at 20:19
  • $\begingroup$ Dave is right, this can be reduced to $O(n lg n)$ by only updating $y_+$ and $y_-$. Also, instead of connecting every node in a region to every other node in the region, they only need to be connected to 1 or 2 other nodes in the region (making a path). Thus, each node has only up to 4 edges. Then Dijkstra's algorithm (with a min priority queue) maybe applied granting $O(n lg n)$ time. $\endgroup$
    – bbejot
    May 4, 2011 at 3:32
  • $\begingroup$ @bbejot: But if so, doesn't the integral priority queue by Thorup improve the running time to $O(n \log\log n)$, or even to $O(n)$ with some additional bucketing technique under the undirected situation? $\endgroup$
    – Hsien-Chih Chang 張顯之
    May 4, 2011 at 5:06
4
$\begingroup$

I feel like $O(n^2)$ might be the best you can get.

It seems natural to convert this into the shortest path problem with a special starting node (x) and ending node (0). There would also be one other node for each of the numbers. Both x and 0 have edges of weight 0 to all number nodes which are reachable in the maze. All number nodes are connected with either weight 0 (if the numbers are maze reachable) or with the difference between the numbers (if not maze reachable).

Shortest path in this graph cannot be solved in less than $O(n^2)$ because the graph has roughly $n^2$ edges and, in the worst case, one would have to view every case once. As such, Dijkstra'a algorithm for shortest path takes $O(n^2)$ time and is worst-case optimal.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This is the answer I had in mind; of course, you have to use the proper data structure with Dijkstra's algorithm to get $O(n^2)$ running time. Using the typical binary heap would yield $O(n^2 \lg n)$. $\endgroup$
    – Fixee
    May 3, 2011 at 14:59
  • 1
    $\begingroup$ I was thinking about this problem this morning and it can be sped up a little. Instead of using one node for each number in the maze, use one node for each region of the maze. The cost between nodes is then the least cost from jumping from one region to the next. The starting node is the region with x and the ending node is the region with 0. If there are $r$ regions, this can then be solved in $O(r^2)$ time by the methods we've been discussing. $\endgroup$
    – bbejot
    May 3, 2011 at 16:49
  • $\begingroup$ You also need $O(n\log n)$ time to create the graph, so the total running time should be $O(r^2 + n\log n)$. Even if there are only two regions, you need to find the closest pair between the two sets of numbers, and there is an $\Omega(n\log n)$ lower bound for that problem in the algebraic computation tree model. (Bit tricks can probably reduce or eliminate the log factor.) $\endgroup$
    – Jeffε
    May 3, 2011 at 22:03
  • $\begingroup$ The $\Omega(n^2)$ lower bound based on the number of edges doesn't apply because the edges aren't part of the input - they're implied. You don't need to look at all of them because you can compute the relevant ones. $\endgroup$
    – Dave
    May 4, 2011 at 1:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.