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

<p>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).</p>

<p>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.</p>

CC BY-SA 3.0
2011-05-03T14:59:17.953Z
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)$.
Fixee
CC BY-SA 3.0
2011-05-03T16:49:22.750Z
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.
bbejot
CC BY-SA 3.0
2011-05-03T22:03:51.450Z
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.)
Jeffε
CC BY-SA 3.0
2011-05-04T01:53:24.410Z
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.
Dave
CC BY-SA 3.0
2011-05-02T04:10:41.667Z
2011-05-02T04:10:41.667Z
bbejot
<p>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.</p>

<p>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.</p>

<p>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)$</p>

CC BY-SA 3.0
2011-05-03T20:19:10.317Z
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.
Dave
CC BY-SA 3.0
2011-05-04T03:32:21.400Z
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.
bbejot
CC BY-SA 3.0
2011-05-04T05:06:34.823Z
@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?
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-05-03T17:43:17.470Z
2011-05-03T18:26:12.313Z
2011-05-03T18:26:12.313Z
Dave
<p>My 8-yr old has gotten bored creating conventional mazes, and has taken to creating variants that look like this:</p>

<p><img src="https://i.sstatic.net/yc37l.jpg" alt="Number Hopper Sample"></p>

<p>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.</p>

<p>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.</p>

<p><strong>Note:</strong> 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.)</p>

CC BY-SA 3.0
2011-05-02T04:12:50.947Z
Props to your child for creating such creative and mathematical puzzles!
bbejot
CC BY-SA 3.0
2011-05-02T04:19:36.793Z
@bbejot You should see some of the stuff he asks me... sometimes I can't answer his questions.  Eg, http://math.stackexchange.com/questions/33094/deleting-any-digit-yields-a-prime-is-there-a-name-for-this
Fixee
CC BY-SA 3.0
2011-05-02T12:09:15.607Z
What is n? ....
Tsuyoshi Ito
CC BY-SA 3.0
2011-05-02T13:05:39.370Z
Pretty impressive for an 8-yr old! (Both, the puzzle and the question about the prime numbers)
George
CC BY-SA 3.0
2011-05-02T13:31:14.840Z
@Tsuyoshi $n$ is the number of integers in the maze.
Fixee
CC BY-SA 3.0
2011-05-02T13:39:13.410Z
Can you include that information in the question so that people do not have to read the comments to understand the meaning of n?
Tsuyoshi Ito
CC BY-SA 3.0
2011-05-02T14:45:08.000Z
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$.
Dave Clarke
CC BY-SA 3.0
2011-05-02T15:00:57.630Z
@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.
Artem Kaznatcheev
CC BY-SA 3.0
2011-05-02T15:16:42.623Z
Indeed. My bad.
Dave Clarke
CC BY-SA 3.0
2011-05-03T22:05:56.643Z
This is an excellent homework problem!
Jeffε
<ds.algorithms><optimization><puzzles>
Solving a Number-Hopper Maze
Fixee
# Solving a Number-Hopper Maze

(Asked by: username_0 on 2011-05-02)

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

![Number Hopper Sample](https://i.sstatic.net/yc37l.jpg)

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.)

**Tags:** ds.algorithms, optimization, puzzles
> **Comments:**
> **username_1**: Props to your child for creating such creative and mathematical puzzles!  
> **username_0**: @bbejot You should see some of the stuff he asks me... sometimes I can't answer his questions.  Eg, http://math.stackexchange.com/questions/33094/deleting-any-digit-yields-a-prime-is-there-a-name-for-this  
> **username_2**: What is n? ....  
> **username_3**: Pretty impressive for an 8-yr old! (Both, the puzzle and the question about the prime numbers)  
> **username_0**: @Tsuyoshi $n$ is the number of integers in the maze.  
> **username_2**: Can you include that information in the question so that people do not have to read the comments to understand the meaning of n?  
> **username_4**: 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$.  
> **username_5**: @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.  
> **username_4**: Indeed. My bad.  
> **username_6**: This is an excellent homework problem!  

---

## 2 answers

### Answer by username_7 on 2011-05-03. Score: 15 | Accepted answer

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)$

> **Comments:**
> **username_7**: 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.  
> **username_1**: 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.  
> **username_8**: @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?  

---

### Answer by username_1 on 2011-05-02. Score: 4

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.

> **Comments:**
> **username_0**: 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)$.  
> **username_1**: 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.  
> **username_6**: 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.)  
> **username_7**: 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.  

---

