Puzzle Time - The out-of-shape postman
-
You can do better than systematic guessing.
-
Hint under the spoiler.
(extraneous extra line otherwise you can read what it says under the spoiler from the thread list view)
||The distances between the houses are irrelevant.||
-
In any order? Ay particular starting and stopping point?
Here's another hint.
||Calculate the maximum number of times you could traverse each path segment. Can you find a path that achieves the maximum?||
-
Starting point?
-
@Klaus said in Puzzle Time - The out-of-shape postman:
The next point is always the one that is the farthest from the current.
Is this required?
-
You choose the starting point. Yeah I get that in real life circumstances would dictate one.
-
Here's the answer, I'm not bothering with a spoiler.
A previous hint suggested figuring out the maximum number of times you could traverse any segment of road between two addresses.
Let me label the path segments between the addresses with letters as follow:
2-a-3-b-5-c-7-d-11-e-13-f-17-g-19
It's clear that you could traverse a and g a maximum of twice. Once arriving to the end point and once leaving it. In order to traverse them the maximum number of times you can't start or end on either end point, if that condition is met it guarantees you'll traverse a and g the maximum number of times.
b (and f) you can traverse a maximum of 4 times. In the case of b, you could traverse it once going to 3, once leaving 3, once going to 2, and once leaving 2. (of course you could do it less but that's the max). What condition must be met to traverse b the maximum number of times? You can't start or finish on either the end point 2 or the next point 3. You also can't go from 2 to 3 or vice versa. Same with f since they are mirror images of each other.
Similarly c and e can be traversed 6 times. Also the constraints are similar. You can't start or end on either 2,3,5 (or 19,17,13). And you can't travel directly between the three end points. IOW, each trip to or from the three end points needs to cross segment c (e).
Segment d can be traversed as much as 7 times. What condition must be met in order to traverse it the maximum number of times? Well, there are only 8 addresses, so 7 'trips' between them. Each trip must cross segment d.
If you take all of that together, it means we must start at one of the two middle points (7 or 11), we must end at the other one, and we must cross the middle segment each time we move from one address to another. So we zig zag back and forth.
You can do what Klaus suggested and always go to the furthest on the other side. But a little reflection will show you it doesn't actually matter the order you take them in, as long as you cross the middle each time and start and end in the right spot.
A little math will show there are actually 2x3x3x2x2 = 72 ways to hit that maximum distance, which is 82.
Note also that the distances between the houses don't matter at all.
-
@jon-nyc said in Puzzle Time - The out-of-shape postman:
Note also that the distances between the houses don't matter at all.
The ‘official’ solution came out today. When discussing a generalized version of the problem, it pointed out that for odd numbers of houses the distance between them matters, but only a little.
In the case an odd number of houses you start and end at the center house and the one closest to it. Otherwise the solution is identical and scales to any number of houses.