Sunday Times Teaser 3235 – Dromedary Lines

by BRG on 22 September 2024

by Mark Valentine

Published Sunday September 22 2024 (link)

Zayed must cross the Setare desert to move to his summer camp, which lies 240 miles east, and a smaller whole number of miles north of his winter camp. Both camps are on a grid of wells every 5 miles north and east across the desert.

His camels can only travel 100 miles before needing to stop for water. Being superstitious, he will only travel a whole number of miles, in a straight line, between wells. Subject to this, he attempts to minimise his journey by travelling to the well, in range, closest to the remaining straight-line route. If more than one well is equally close, he stops at the nearest one.

During his journey he travels a total of 50 miles due east and 5 miles due north and visits 14 wells between his camps (not including the ones at the camps).

List in order the length of each of the first five stages.

From → Uncategorized

One Comment Leave one →

BRG permalink

sqr2rt = {n * n: n for n in range(1, 30)}
def is_sqr(x, y):
  return sqr2rt.get(x * x + y * y, None)
 
# possible diagonal legs plus due east legs for x <= 50 and one due north leg
legs = ({(x, y, z) for x in range(1, 21) for y in range(1, 21) 
       if (z := is_sqr(x, y)) is not None} | 
        {(x, 0, x) for x in range(1, 11)} | {(0, 1, 1)})

# find the next well nearest to the path from (x0, y0) to (x1, y1) 
def find_next_well(x0, y0, x1, y1):
  
  # the east, north and direct distances between the end points
  dx, dy = x1 - x0, y1 - y0
  min_p = dxy = None
  
  # consider possible legs to the next well  
  for lx, ly, lz in legs:
    if (x := x0 + lx) <= x1 and (y := y0 + ly) <= y1:
      # find the relative distance of the well from the straight line path
      p = abs(dx * (y1 - y) - dy * (x1 - x))
      # find the well that is closest to a straight line between (x0, y0) 
      # and (x1, y1) (and nearest to the start if more than one)
      if min_p is None or p < min_p or p == min_p and lz <= dxy[2]:
        # return the position and distance of the next well
        min_p, dxy = p, (lz, x, y)
  return dxy

# use 5 mile units
dx = 240 // 5
# consider the northerly distance between the two camps
for dy in range(1, dx):
  # look for routes between the two camps
  wells, x, y = [(0, 0, 0)], 0, 0
  while x < dx or y < dy:
    dxy = d, x, y = find_next_well(x, y, dx, dy)
    wells.append(dxy)
  
  # 16 wells are visited (including endpoints) 
  if len(wells) == 16:
    # find overall distances travelled due east and due north 
    xd = sum(r - p for (_, p, q), (_, r, s) in zip(wells, wells[1:]) if q == s)
    yd = sum(s - q for (_, p, q), (_, r, s) in zip(wells, wells[1:]) if p == r)    
    if xd == 10 and yd == 1:
      print(f"dy = {5 * dy}, wells @(grid units): "
            f"{' '.join(f'{(x, y)}' for d, x, y in wells)}")
      ds = tuple(5 * w[0] for w in wells) 
      print(f"{ds[1:6]} [...{ds[6:]}]")

sqr2rt = {n * n: n for n in range(1, 30)}

def is_sqr(x, y):

return sqr2rt.get(x * x + y * y, None)

# possible diagonal legs plus due east legs for x <= 50 and one due north leg

legs = ({(x, y, z) for x in range(1, 21) for y in range(1, 21)

if (z := is_sqr(x, y)) is not None} |

{(x, 0, x) for x in range(1, 11)} | {(0, 1, 1)})

# find the next well nearest to the path from (x0, y0) to (x1, y1)

def find_next_well(x0, y0, x1, y1):

# the east, north and direct distances between the end points

dx, dy = x1 - x0, y1 - y0

min_p = dxy = None

# consider possible legs to the next well

for lx, ly, lz in legs:

if (x := x0 + lx) <= x1 and (y := y0 + ly) <= y1:

# find the relative distance of the well from the straight line path

p = abs(dx * (y1 - y) - dy * (x1 - x))

# find the well that is closest to a straight line between (x0, y0)

# and (x1, y1) (and nearest to the start if more than one)

if min_p is None or p < min_p or p == min_p and lz <= dxy[2]:

# return the position and distance of the next well

min_p, dxy = p, (lz, x, y)

return dxy

# use 5 mile units

dx = 240 // 5

# consider the northerly distance between the two camps

for dy in range(1, dx):

# look for routes between the two camps

wells, x, y = [(0, 0, 0)], 0, 0

while x < dx or y < dy:

dxy = d, x, y = find_next_well(x, y, dx, dy)

wells.append(dxy)

# 16 wells are visited (including endpoints)

if len(wells) == 16:

# find overall distances travelled due east and due north

xd = sum(r - p for (_, p, q), (_, r, s) in zip(wells, wells[1:]) if q == s)

yd = sum(s - q for (_, p, q), (_, r, s) in zip(wells, wells[1:]) if p == r)

if xd == 10 and yd == 1:

print(f"dy = {5 * dy}, wells @(grid units): "

f"{' '.join(f'{(x, y)}' for d, x, y in wells)}")

ds = tuple(5 * w[0] for w in wells)

print(f"{ds[1:6]} [...{ds[6:]}]")

This version is much slower but it tests all routes between the two camps:

# find the next well nearest to the path from (x0, y0) to (x1, y1) 
def find_next_well(x0, y0, x1, y1):
  # the east, north distances between the end points
  dx, dy = x1 - x0, y1 - y0
  min_p = {}
  # consider possible legs to the next well  
  for lx, ly, lz in legs:
    if (x := x0 + lx) <= x1 and (y := y0 + ly) <= y1:
      # find the relative distance of the well from the straight line path
      p = abs(dx * (y1 - y) - dy * (x1 - x))
      min_p[p] = min_p.get(p, []) + [(lz, x, y)]
  dxys = sorted(min_p[min(min_p)])
  yield from (dxy for dxy in dxys if dxy[0] == dxys[0][0])

def find_route(xt, yt, x0=0, y0=0, cnt_x=0, cnt_y=0, legs=[]):
  if x0 == xt and y0 == yt:
    yield legs + [(0, x0, y0)]
  else: 
    for d, x, y in find_next_well(x0, y0, xt, yt):
      if x <= xt and y <= yt:
        cnt_x_ = cnt_x + (y == y0 and x - x0 == 1)
        cnt_y_ = cnt_y + (x == x0 and y - y0 == 1)
        if cnt_x_ < 11 and cnt_y_ < 2:
          yield from find_route(xt, yt, x, y, cnt_x_, cnt_y_, legs + [(d, x0, y0)])

# consider the northerly distance between the two camps
dx = 240 // 5
for dy in range(1, dx):
  # look for routes between the two camps
  for wells in find_route(dx, dy):
    # 16 wells are visited (including endpoints) 
    if len(wells) == 16:
      # find overall distances travelled due east and due north 
      xd = sum(r - p for (_, p, q), (_, r, s) in zip(wells, wells[1:]) if q == s)
      yd = sum(s - q for (_, p, q), (_, r, s) in zip(wells, wells[1:]) if p == r)    
      if xd == 10 and yd == 1:
        print(f"dy = {5 * dy}, wells @(grid units): "
              f"{' '.join(f'{(x, y)}' for d, x, y in wells)}")
        ds = tuple(5 * w[0] for w in wells) 
        print(f"{ds[1:6]} [...{ds[6:]}]")

sqr2rt = {n * n: n for n in range(1, 30)}

def is_sqr(x, y):

return sqr2rt.get(x * x + y * y, None)

# possible diagonal legs plus due east legs for x <= 50 and one due north leg

legs = ({(x, y, z) for x in range(1, 21) for y in range(1, 21)

if (z := is_sqr(x, y)) is not None} |

{(x, 0, x) for x in range(1, 11)} | {(0, 1, 1)})

# find the next well nearest to the path from (x0, y0) to (x1, y1)

def find_next_well(x0, y0, x1, y1):

# the east, north distances between the end points

dx, dy = x1 - x0, y1 - y0

min_p = {}

# consider possible legs to the next well

for lx, ly, lz in legs:

if (x := x0 + lx) <= x1 and (y := y0 + ly) <= y1:

# find the relative distance of the well from the straight line path

p = abs(dx * (y1 - y) - dy * (x1 - x))

min_p[p] = min_p.get(p, []) + [(lz, x, y)]

dxys = sorted(min_p[min(min_p)])

yield from (dxy for dxy in dxys if dxy[0] == dxys[0][0])

def find_route(xt, yt, x0=0, y0=0, cnt_x=0, cnt_y=0, legs=[]):

if x0 == xt and y0 == yt:

yield legs + [(0, x0, y0)]

else:

for d, x, y in find_next_well(x0, y0, xt, yt):

if x <= xt and y <= yt:

cnt_x_ = cnt_x + (y == y0 and x - x0 == 1)

cnt_y_ = cnt_y + (x == x0 and y - y0 == 1)

if cnt_x_ < 11 and cnt_y_ < 2:

yield from find_route(xt, yt, x, y, cnt_x_, cnt_y_, legs + [(d, x0, y0)])

# consider the northerly distance between the two camps

dx = 240 // 5

for dy in range(1, dx):

# look for routes between the two camps

for wells in find_route(dx, dy):

# 16 wells are visited (including endpoints)

if len(wells) == 16:

# find overall distances travelled due east and due north

xd = sum(r - p for (_, p, q), (_, r, s) in zip(wells, wells[1:]) if q == s)

yd = sum(s - q for (_, p, q), (_, r, s) in zip(wells, wells[1:]) if p == r)

if xd == 10 and yd == 1:

print(f"dy = {5 * dy}, wells @(grid units): "

f"{' '.join(f'{(x, y)}' for d, x, y in wells)}")

ds = tuple(5 * w[0] for w in wells)

print(f"{ds[1:6]} [...{ds[6:]}]")

Sunday Times Teaser 3235 – Dromedary Lines

by Mark Valentine

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta