An autonomous wheeled delivery robot is being tested in a city district. It must navigate along the streets from a central warehouse (marked \(A\)) to a customer’s house (marked \(B\)), as shown.
Due to a glitch in its guidance sensors, the robot is currently unable to process continuous, straight-line travel through intersections. At every intersection it reaches, the robot’s programming forces it to make either a \(90\degree\) left turn or a \(90\degree\) right turn; it can never continue straight through an intersection. Furthermore, to prevent the robot from getting stuck in an infinite loop, its safety protocols dictate that it can never travel along the same street segment more than once.
If moving from one intersection to the next one counts as one travel segment, what is the minimum number of segments needed for the robot to successfully reach the house?
This problem was inspired by a past Beaver Computing Challenge (BCC) problem.
To get from the central warehouse (\(A\)) to the customer’s house (\(B\)), the robot must pass through at least one of the four numbered segments shown.
We will find the length of the shortest route through each of these four numbered segments, and then determine the shortest route overall. The length of this route will then be equal to the minimum number of segments needed for the robot to successfully reach the house.
For each route, we start by noting that since the robot cannot travel straight through any intersection, it must turn both before and after the numbered segment. We then cross out the vertical segments directly below and above the numbered segment, because the robot cannot travel on these segments. From there, we determine the shortest route between \(A\) and the numbered segment, and then between the numbered segment and \(B\). Some details, for the sake of brevity, will be omitted from the solution and left for the solver to consider further.
For some of the routes shown, at some point along the route alternate choices can be made that lead to invalid solutions, lengthen the route, and/or have the same length as the route shown. The solver may wish to confirm this.
Shortest Route Through Segment 1:
In the part of the route between \(A\) and segment \(1\), the shortest route has length \(4\). In the part of the route between segment \(1\) and \(B\), the shortest route has length \(10\). Thus, the shortest route through segment \(1\) has length \(4+1+10=15\).
Shortest Route Through Segment 2:
In the part of the route between \(A\) and segment \(2\), the shortest route has length \(9\). In the part of the route between segment \(2\) and \(B\), the shortest route has length \(3\). Thus, the shortest route through segment \(2\) has length \(9+1+3=13\).
Shortest Route Through Segment 3:
In the part of the route between \(A\) and segment \(3\), the shortest route has length \(13\). In the part of the route between segment \(3\) and \(B\), the shortest route has length \(3\). Thus, the shortest route through segment \(3\) has length \(13+1+3=17\).
Shortest Route Through Segment \(\bf 4\):
In the part of the route between \(A\) and segment \(4\), the shortest route has length \(12\). In the part of the route between segment \(4\) and \(B\), the shortest route has length \(2\). Thus, the shortest route through segment \(4\) has length \(12+1+2=15\).
After examining the shortest route through each of the four numbered segments, the shortest route overall has a length of \(13\) and passes through segment \(2\). Thus, the minimum number of segments needed for the robot to successfully reach the house is \(13\).