12
$\begingroup$

I need to travel through the city from my house to school, but the traffic is horrible right now.

I can only move along the city's grid with the following conditions:

• blocks with traffic (marked in red) take three minutes to traverse,
• and blocks without traffic take one minute to traverse.

enter image description here

What is the fastest way that I can get to school?

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ I hate traffic and so do you, And we hate it all together, Come with me and I'll go with you, Let's avoid all the traffic together $\endgroup$
    – RonnieChen
    Commented Apr 30, 2023 at 19:13
  • 2
    $\begingroup$ I wonder if it's possible to create a map with these same dimensions and constraints (1 or 3 minutes per link), but in which the solution cannot be easily solved by eye and intuition ("6 mins is impossible, so the obvious path must be the best)", and instead a methodical A*-like solution is needed? $\endgroup$
    – Dewi Morgan
    Commented May 1, 2023 at 6:27
  • $\begingroup$ This puzzle seems ambiguous to me. A 'block' is really the rectangular area enclosed by streets. So I thought that if a square had any sides that were red, it would take 3 minutes to traverse from one corner to any other corner. And if the block was surrounded by white only, you could traverse from any corner to any other corner in 1 minute. Looking at the accepted answer I guess 'block' means any street segment connecting two intersections. $\endgroup$
    – Jason Goemaat
    Commented May 1, 2023 at 18:49
  • 1
    $\begingroup$ @JasonGoemaat - maybe language usage is a bit different where you are than here, but it is customary to measure length along streets by the "block", as in "it is 3 blocks to the grocery store". This measures from intersection to intersection, not diagonally across the block itself. And since it is clearly the streets, not the blocks themselves that are colored red, and in real life, a block can easily have traffic on one adjoining street and not others, it seems to me that the intended meaning is clear enough. $\endgroup$
    – Paul Sinclair
    Commented May 1, 2023 at 19:18
  • 1
    $\begingroup$ You aren't stuck in traffic - you are traffic. $\endgroup$
    – Stack Exchange Supports Israel
    Commented May 3, 2023 at 0:35

3 Answers 3

Reset to default
19
$\begingroup$

Index the intersections with matrix notation, so $X=(3,3)$ and $Y=(5,7)$. Let $d_{i,j}$ be the shortest time from $(i,j)$ to $Y$. We want to compute $d_{3,3}$. By working backwards from $d_{5,7}=0$, we find the following values:

\begin{matrix}12&11&10&9&8&7&6&7&8\\11&10&9&8&7&8&5&6&7\\10&9&\color{green}{8}&7&6&7&4&5&6\\9&8&7&6&5&4&3&4&5\\8&7&6&5&4&3&\color{magenta}{0}&3&4\\7&6&5&4&3&2&1&2&3\\8&7&6&5&4&3&2&3&4\\\end{matrix}

In particular, the shortest distance from $X$ to $Y$ is

$d_{3,3}=8$.

To recover a shortest path from the table, start at $X$ and repeatedly select an outgoing neighbor $(i,j)$ with the smallest value of $d_{i,j}+\text{time to $(i,j)$}$:

\begin{matrix}.&.&.&.&.&.&.&.&.\\.&.&.&.&.&.&.&.&.\\.&.&\color{green}{8}&.&.&.&.&.&.\\.&.&7&6&.&.&.&.&.\\.&.&6&5&4&.&\color{magenta}{0}&.&.\\.&.&.&4&3&2&1&.&.\\.&.&.&.&.&.&.&.&.\\\end{matrix}

Improve this answer
$\endgroup$
2
  • 5
    $\begingroup$ "repeatedly select an outgoing neighbor with the smallest value of d" is ambiguous and not necessarily gives you the right solution. Following this rule, I may get SSEEEE, which takes 10 minutes. $\endgroup$
    – fuenfundachtzig
    Commented Apr 30, 2023 at 8:02
  • 1
    $\begingroup$ @fuenfundachtzig Thanks, corrected. $\endgroup$
    – RobPratt
    Commented Apr 30, 2023 at 12:25
43
$\begingroup$

Same as other people's answer, but a more visual/intuitive explanation:

Solution - SESESEEN Just looking at the map we can notice two things:

  1. The absolutely fastest time (direct path if there were no traffic jams) would be 6 minutes.
  2. The path marked in blue takes 8 minutes and has no traffic jams on it at all.

In other words, it's the same time as the fastest path, but if one of the fastest path's pieces were replaced with a traffic jam.

Since the fastest path isn't available, and this is the next best possible time, then this must be the solution.

Added:

My conscience isn't letting me go. 😅 I actually haven't provided an explanation why a path of length 7 isn't possible. I'll skip the picture this time, but imagine you color each intersection either red or blue in a checkerboard pattern. Let's say the starting intersection is blue, and then from that the 4 surrounding ones are red, and those are then surrounded by blue, etc. And the idea is to look at the parity of the time spent walking. You'll realize that no matter how you walk, when you end up at a blue intersection, you have spent an even amount of minutes; and at a red intersection - an odd amount of minutes. That's because each path - no matter if it has a traffic jam on it or not - takes an odd amount of minutes to cross. Since the school stands on a blue intersection, you cannot get there in 7 minutes.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ The best reasoning for this specific problem. +1 $\endgroup$
    – justhalf
    Commented Apr 30, 2023 at 16:31
  • 1
    $\begingroup$ Signed up just to commend your solution (both parts of it!). Very elegant. Love it! $\endgroup$
    – TCN
    Commented May 1, 2023 at 9:57
  • $\begingroup$ Technically, all you've shown is that the path is a fastest-time solution. But it is easy to check that any path that doesn't backtrack (travel in one direction, then later travel in the opposite direction) must pass through at least two blocks with traffic, which is enough to show uniqueness. $\endgroup$
    – Paul Sinclair
    Commented May 1, 2023 at 14:52
  • 1
    $\begingroup$ @PaulSinclair There are multiple shortest paths. $\endgroup$
    – RobPratt
    Commented May 1, 2023 at 18:55
  • 1
    $\begingroup$ @RobPratt - True. There are four, depending on which way one travels around two traffic-free blocks. I should have been more careful in my wording. I was caught up in noting that no solutions involved going through traffic. Such a solution would be possible, provided only one block of traffic was encountered. $\endgroup$
    – Paul Sinclair
    Commented May 1, 2023 at 19:02
6
$\begingroup$

You can get to school in 8 minutes

By going one block south of the school, avoiding all the traffic, there are a few different paths available, but one such is S, S, E, E, S, E, E, N

Improve this answer
$\endgroup$

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