Enigmatic Code

Programming Enigma Puzzles

Enigma 862: Distances

From New Scientist #2017, 17th February 1996 [link] [link]

The mileage chart shows the distances between various secret government establishments, each of which is designated by a three-digit code. The distance between two locations can be calculated by adding the differences between the three pairs of corresponding digits, ignoring the signs of the differences. Thus the distance between 689 and 773 is (7 − 6) + (8 − 7) + (9 − 3) = 8.

For reasons of security the government wants these locations to be as far apart as possible, and is concerned that two of them are only four miles apart. Locations 000 and 999 must be retained, but the other four can be moved to locations represented by any three-digit codes, to make the closest pair as far apart as possible.

What is the greatest possible distance between the closest pair?

[enigma862]

One response to “Enigma 862: Distances

  1. Jim Randell 23 May 2022 at 10:32 am

    This Python program considers decreasing bounds on the allowable minimum distance, until a viable set of location codes is found.

    It runs in 83ms. (Internal run time is 19ms).

    Run: [ @replit ]

    from enigma import (ordered, subsets, irange, peek, printf)
    
    # distance between 2 locations
    dist = lambda xs, ys: sum(abs(x - y) for (x, y) in zip(xs, ys))
    
    # add <n> more keys to <ks>, distances <ds>
    # subject to minimum allowable distance <m>
    def solve(n, ks, ds, m):
      # are we done?
      if n == 0:
        yield (ks, ds)
      else:
        # choose a new key
        for k in subsets(irange(0, 9), size=3, select="M"):
          ds_ = dict(ds)
          for k_ in ks:
            ds_[ordered(k, k_)] = dist(k, k_)
          if min(ds_.values()) < m: continue
          yield from solve(n - 1, ks.union([k]), ds_, m)
    
    # consider decreasing lower bounds on the distance
    for m in irange(20, 5, step=-1):
      printf("[considering min distance {m} ...]")
      # initial keys
      A = (0, 0, 0)
      B = (9, 9, 9)
      # can we add add 4 more
      rs = peek(solve(4, {A, B}, { ordered(A, B): dist(A, B) }, m), default=None)
      if rs:
        # output solution: keys and distances
        (ks, ds) = rs
        printf("{ks} -> {ds}", ks=sorted(ks), ds=sorted(ds.values()))
        break
    

    Solution: The greatest possible distance between the closest pair is 13 miles.

    There are many ways of achieving this value.

    Here is one:

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: