Enigmatic Code

Programming Enigma Puzzles

Enigma 876: Short circuit

From New Scientist #2031, 25th May 1996 [link]

We spent our holiday on the oddly-shaped island of Hexonia. One day, we drove around the coast road which was in the form of a hexagon with each angle 120°. I remember noticing that each straight was a different perfect square whole number of kilometres and that the complete circuit was less than 500 kilometres.

How far did we drive?

[enigma876]

3 responses to “Enigma 876: Short circuit

  1. Jim Randell 20 September 2021 at 8:45 am

    This Python program travels the perimeter of the island, using isometric co-ordinates (where the axes are 60° apart).

    In order to eliminate duplicate solutions we consider the longest side first, and then the second side should be longer than the last side (otherwise we could start at any vertex and travel in either direction, giving 12 times the number of distinct solutions).

    It runs in 274ms.

    Run: [ @replit ]

    from enigma import powers, inf, printf
    
    # directions on an isometric grid, going round the hexagon
    dirs = [ (1, 0), (0, 1), (-1, 1), (-1, 0), (0, -1), (1, -1) ]
    
    # new position after side k of length n
    def pos(n, k, p=(0, 0)):
      (x, y) = p
      (dx, dy) = dirs[k]
      return (x + n * dx, y + n * dy)
    
    # find a hexagonal path
    # sides = available sides
    # ss = sides used so far
    # t = remaining distance budget
    # p = current position
    def solve(sides, ss, t, p):
      k = len(ss)
      # are we done?
      if k == 6:
        # back where we started?
        if p == (0, 0):
          yield ss
      else:
        # choose the next side
        for n in sides:
          if n < t and n not in ss:
            # and solve for the remaining sides
            yield from solve(sides, ss + [n], t - n, pos(n, k, p))
    
    # consider the largest square
    T = 500
    squares = list()
    for n in powers(1, inf, 2):
      if n > T: break
      if len(squares) > 4:
        # solve for largest square n, and 5 more squares
        for ss in solve(squares, [n], T - n, pos(n, 0)):
          if ss[1] > ss[-1]:
            printf("{ss} -> {t}", t=sum(ss))
      squares.append(n)
    

    Solution: The total distance is 420 km.

    The sides of the island have the following lengths (in km): 169, 16, 49, 121, 64, 1.

    Here is a diagram of the island:

  2. Hugh Casement 21 September 2021 at 8:21 am

    I’m not sure we need isometric coordinates. The net distances south and east must both be zero:
    b + c – e – f = 0, 2(a – d) + b – c – e + f = 0.
    If those are six different square numbers with sum less than 500 there is only one sequence, or its cyclic permutations clockwise or anticlockwise. To eliminate most of those duplicate solutions I started with the smallest.

  3. GeoffR 22 September 2021 at 11:02 am

    Using Hugh’s idea of horizontal and vertical distances, I calculated these distances in terms of the sides of the hexagon, using cos(60) for the horizontal distances and sin(60) for the vertical distances.

    Fot the horizontal distances, I got:
    S6/2 + S1 + S2/2 = S3/2 + S4 + S5/2

    and, for the vertical distances:
    S2 * sqrt(3)/2 + S3 * sqrt(3)/2 = S5 * sqrt(3)/2 + S6 * sqrt(3)/2

    These equations translate to the two constraints in the code after the all sides square constraint.

    % A Solution in MiniZinc
    include "globals.mzn";
    
    predicate is_sq(var int: y) =
      exists(z in 1..ceil(sqrt(int2float(ub(y))))) (
            z*z = y );
    
    % six sides of the hexagon
    var 1..200: S1; var 1..200:S2; var 1..200:S3;
    var 1..200: S4; var 1..200:S5; var 1..200:S6;
    
    % make S1 the largest square
    constraint S1 > S2 /\ S1 > S3 /\ S1 > S4 /\ S1 > S5 /\ S1  > S6;
    
    constraint all_different ([S1, S2, S3, S4, S5, S6]);
    
    % all sides of the hexagon are squares
    constraint is_sq(S1) /\ is_sq(S2) /\ is_sq(S3)
    /\  is_sq(S4) /\ is_sq(S5) /\ is_sq(S6);
    
    % all horizontal and vertical distances must balance
    constraint S6 + 2*S1 + S2 == S3 + 2*S4 + S5;
    constraint S2 + S3 == S5 + S6;
    
    constraint all_different([S1, S2, S3, S4, S5, S6]);
    
    constraint S1 + S2 + S3 + S4 + S5 + S6 < 500;
    
    solve satisfy;
    
    output ["Squares (S1 - S6) in km: " ++ show(S1) ++ ",  " 
    ++ show(S2) ++ ",  " ++ show(S3) ++ ",  " ++ show(S4)
     ++ ",  " ++ show(S5) ++ ",  " ++ show(S6) ++ 
    "\nTotal length of sides(km) =  " ++ show(S1 + S2 + S3 + S4 + S5 + S6)];
    
    % Squares (S1 - S6) in km: 169,  16,  49,  121,  64,  1
    % Total length of sides(km) =  420
    % ----------
    % Squares (S1 - S6) in km: 169,  1,  64,  121,  49,  16
    % Total length of sides(km) =  420
    % ----------
    % ==========
    
    
    

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 )

Google photo

You are commenting using your Google 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: