Enigmatic Code

Programming Enigma Puzzles

Enigma 381: Island airlines

From New Scientist #1530, 16th October 1986 [link]

Come with us now to those 10 Pacific islands with the quaint native names A, B, C, D, E, F, G, H, I, J. These are served by Lamour and Sarong airlines. Each morning one plane from each airline leaves each island bound for another of the islands. No two planes from the same airline are going to the same island and the two planes leaving any island go to different destinations.

The planes all carry out the return journeys overnight and everything is repeated the next day and so on.

Each island has a beautiful queen. One morning, each queen left her island on the Lamour plane, staying overnight on the island she reached, and left the next morning on the Sarong plane. At the end of their two-day journey the queens of A, B, C, D, E, F, G, H, I, J found themselves on the islands of C, F, B, H, J, D, E, I, G, A, respectively.

Some time later, the queens made similar journeys, again starting from their home islands, but this time taking the Sarong planes on the first day and the Lamour planes on the second day. This time the Queens of A, B, C, D, E, F, G, H, I, J ended up on the islands of J, A, B, I, F, H, E, C, G, D respectively.

As the sun slowly sits in the west we say a fond farewell to a £10 book token, which will be sent to the first person to tell as the details of the 10 Lamour routes.

[enigma381]

Advertisements

6 responses to “Enigma 381: Island airlines

  1. Jim Randell 27 January 2017 at 8:26 am

    This Python program runs in 43ms.

    from enigma import irange, join, concat, printf
    
    # labels for the islands
    islands = (A, B, C, D, E, F, G, H, I, J) = irange(0, 9)
    
    # map the labels back to strings
    label = 'ABCDEFGHIJ'
    
    # L first, then S (i.e. S[L[i]])
    SL = [ C, F, B, H, J, D, E, I, G, A ]
    
    # S first, then L (i.e. L[S[i]])
    LS = [ J, A, B, I, F, H, E, C, G, D ]
    
    # assign i -> j in the map A, and infer remaining assignments
    # A = map to assign
    # B = other map
    # BA = result of A first then B
    # AB = result of B first then A
    def assign(i, j, A, B, BA, AB):
      while A[i] is None:
        # each map is a derangement, and maps don't share pairs
        assert not(i == j or B[i] == j or j in A)
        A[i] = j
        # switch maps
        (i, j, A, B, BA, AB) = (j, BA[i], B, A, AB, BA)
      # if the map is already filled out, check the value
      assert A[i] == j
      # we're done
      return (A, B)
      
    # consider destinations for L, from A
    for d in islands:
      try:
        (L, S) = assign(A, d, [None] * 10, [None] * 10, SL, LS)
      except AssertionError:
        continue
    
      fmt = lambda x: join((concat(label[i], '->', label[x[i]]) for i in islands), sep=" ")
      printf("L: {L}", L=fmt(L))
      printf("S: {S}", S=fmt(S))
      printf()
    

    Solution: The routes from Lamour are: A → F; B → C; C → H; D → A; E → G; F → B; G → I; H → J; I → D; J → E.

    The program works by choosing a destination for airline L flying from A, and then infers the remaining destinations for both airlines. If it some point it finds a departure/destination pair that are the same, or a route that is duplicated between the airlines it stops looking.

    So, for example, if we suppose that L flies from A to B (we write L[A] = B), then we see that the Queen of A, flying on L and then S arrives at C. So S[L[A]] = C, hence S[B] = C. We now have a value for S[B], and we see that the Queen of B, flying on S then L arrives at A. So L[S[B]] = A, hence L[C] = A. And we repeat the process. The Queen of C flying on L then S arrives at B, so S[L[C]] = B, hence S[A] = B. But we already have L[A] = B and the airlines fly to different destinations from the same island, so this is not a valid solution.

    We can similarly try the other possibilities for L[A] manually, and we find there is only one valid solution:

    L[A] = A. not allowed – L must be a derangement.

    L[A] = B, S[B] = C, L[C] = A, S[A] = B. not allowed – L[A] and S[A] cannot both be B.

    L[A] = C, S[C] = C. not allowed – S must be a derangement.

    L[A] = D, S[D] = C, L[C] = I, S[I] = B, L[B] = G, S[G] = F, L[F] = E, S[E] = D, L[D] = F, S[F] = H, L[H] = H. not allowed – L must be a derangement.

    L[A] = E, S[E] = C, L[C] = F, S[F] = B, L[B] = H, S[H] = F, L[F] = C, S[C] = D, L[D] = B, S[B] = H – L[B] and S[B] cannot both be H.

    L[A] = F, S[F] = C, L[C] = H, S[H] = B, L[B] = C, S[C] = F, L[F] = B, S[B] = D, L[D] = A, S[A] = H, L[H] = J, S[J] = I, L[I] = D, S[D] = G, L[G] = I, S[I] = E, L[E] = G, S[G] = J, L[J] = E, S[E] = A, L[A] = F – valid solution.

    L[A] = G, S[G] = C, L[C] = E, S[E] = B, L[B] = F, S[F] = F. not allowed – S must be a derangement.

    L[A] = H, S[H] = C, L[C] = C. not allowed – L must be a derangement.

    L[A] = I, S[I] = C, L[C] = G, S[G] = B, L[B] = E, S[E] = F, L[F] = F. not allowed – L must be a derangement.

    L[A] = J, S[J] = C, L[C] = D, S[D] = B, L[B] = I, S[I] = F, L[F] = G, S[G] = D, L[D] = E, S[E] = H, L[H] = F, S[F] = I, L[I] = H, S[H] = G, L[G] = C, S[C] = E, L[E] = B, S[B] = J, L[J] = A, S[A] = A – not allowed, S must be a derangement.

    So the solution is found when L[A] = F.

    • Jim Randell 27 January 2017 at 8:34 am

      We can also express the problem as a set of constraints in MiniZinc as follows:

      (This program uses my minizinc.py wrapper library to let me do the formatting of the results in Python).

      from enigma import irange, concat, join, sprintf as f
      from minizinc import MiniZinc
      
      # labels for the islands
      islands = (A, B, C, D, E, F, G, H, I, J) = irange(0, 9)
      
      # map the labels back to strings
      label = 'ABCDEFGHIJ'
      
      # L first, then S (i.e. S[L[i]])
      SL = [ C, F, B, H, J, D, E, I, G, A ]
      
      # S first, then L (i.e. L[S[i]])
      LS = [ J, A, B, I, F, H, E, C, G, D ]
      
      # the MiniZinc model
      model = f("""
      
      include "globals.mzn";
      
      % destinations for L and S
      array[0..9] of var 0..9: L;
      array[0..9] of var 0..9: S;
      
      % each is a permutation of 0..9
      constraint all_different(L);
      constraint all_different(S);
      
      % each is a derangement
      constraint forall (i in 0..9) (L[i] != i);
      constraint forall (i in 0..9) (S[i] != i);
      
      % no routes are duplicated
      constraint forall (i in 0..9) (L[i] != S[i]);
      
      % L first, then S
      constraint [ S[L[i]] | i in 0..9 ] == {SL};
      
      % S first, then L
      constraint [ L[S[i]] | i in 0..9 ] == {LS};
      
      solve satisfy;
      
      """)
      
      # run the model
      for (L, S) in MiniZinc(model).solve(result="L S", solver="mzn-gecode -a"):
        # format the output
        fmt = lambda x: join((concat(label[i], '->', label[x[i]]) for i in islands), sep=" ")
        print(f("L: {L}", L=fmt(L)))
        print(f("S: {S}", S=fmt(S)))
        print()
      

      This finds the solution in 162ms (using the mzn-gecode -a solver).

    • Jim Randell 28 January 2017 at 3:33 pm

      Here’s a slightly improved Python 3 version of the code. It doesn’t use exceptions when invalid solutions are detected, instead assign() returns a boolean value. And the code to try the possibilities is now placed in a solve() function, which should make it work in the more general case. (Of course in this case it still only needs to consider possible values for L[A]).

      from enigma import irange, find, join, concat, printf
      
      # labels for the islands
      islands = (A, B, C, D, E, F, G, H, I, J) = irange(0, 9)
      
      # map the labels back to strings
      label = 'ABCDEFGHIJ'
      
      # L first, then S (i.e. S[L[i]])
      LS = [ C, F, B, H, J, D, E, I, G, A ]
      
      # S first, then L (i.e. L[S[i]])
      SL = [ J, A, B, I, F, H, E, C, G, D ]
      
      # assign i -> j in the map A, and infer remaining assignments
      # A = map to assign
      # B = other map
      # BA = result of A first then B
      # AB = result of B first then A
      def assign(i, j, A, B, BA, AB):
        while A[i] is None:
          # each map is a derangement, and maps don't share pairs
          if i == j or B[i] == j or j in A: return False
          A[i] = j
          # switch maps
          (i, j, A, B, BA, AB) = (j, BA[i], B, A, AB, BA)
        # if the map is already filled out, check the value
        return (A[i] == j)
      
      # find possible completions of maps A and B
      # A, B = maps to assign
      # BA = result of A first then B
      # AB = result of B first then A
      def solve(A, B, BA, AB):
        # find an unassigned value in A
        i = find(A, None)
        # are we done?
        if i == -1:
          yield (A, B)
        else:
          # choose an unused destination
          for j in islands:
            if j not in A:
              # does this assignment work?
              (A1, B1) = (list(A), list(B))
              if assign(i, j, A1, B1, BA, AB):
                # complete the remaining blanks
                yield from solve(A1, B1, BA, AB)
      
      # solve the puzzle, starting with empty maps for L and S
      for (L, S) in solve([None] * 10, [None] * 10, SL, LS):
        fmt = lambda x: join((concat(label[i], '->', label[x[i]]) for i in islands), sep=" ")
        printf("L: {L}", L=fmt(L))
        printf("S: {S}", S=fmt(S))
        printf()
      
  2. Hugh Casement 27 January 2017 at 8:41 am

    Not sure whether it follows automatically, but in my solution the other airline flies routes
    A – H, B – D, C – F, D – G, E – A, F – C, G – J, H – B, I – E, J – I.

    • Jim Randell 27 January 2017 at 8:54 am

      Yes, that’s right. These are the only solutions for L and S.

      I should probably have mentioned the routes for S explicitly in my comment (although there are given in my explanation of the manual solution).

      L is a single cycle: (A F B C H J E G I D).
      S has two cycles: (A H B D G J I E) (C F).

  3. Brian Gladman 27 January 2017 at 5:47 pm
    # the islands and the results of sequential island to island flights
    isles = 'ABCDEFGHIJ'
    sl = dict(zip(isles, 'CFBHJDEIGA'))   # Lamour then Sarong
    ls = dict(zip(isles, 'JABIFHECGD'))   # Sarong then Lamour
    
    # solve for Lamour flights from <frm> islands to those in <dst> while
    # compiling the flight details for Lamour and Sarong in <lf> and <sf>
    def solve(frm, dst, lf=dict(), sf=dict()):
      # return the Lamour and Sarong flight details if we are finished
      if not frm:
        yield lf, sf
      else:
        # select the Lamour flight destination for the next island 
        fr = frm[0]
        for ds in dst:
          
          # which must be a different island and not the same
          # destination as the Sarong flight (if this is known)
          if ds == fr or fr in sf and sf[fr] == ds:
            continue
          
          # copy the flight details and add this flight
          lf2, sf2 = lf.copy(), sf.copy()
          lf2[fr] = ds
          
          # if we know the onward flight from the destination, check
          # that the combined flights give the correct final destination
          if ds in sf2 and sf2[ds] != sl[fr]:
            continue
          
          # otherwise we can set the Sarong flight from the destination
          # as that given by the known combined flight destination
          sf2[ds] = sl[fr]
          
          # but we need to check that it is to a different island and not 
          # the same as any Lamour flight from this island
          if ds == sl[fr] or ds in lf2 and lf2[ds] == sl[fr]:
            continue
          
          # now check that all known 'reverse' combined flights are correct
          if all(lf2[sf2[k]] == ls[k] for k in sf2 if sf2[k] in lf2):
            yield from solve(frm[1:], [x for x in dst if x != ds], lf2, sf2)
    
    for l, s in solve(isles, isles):
      print('Lamour Flights: ', ', '.join(c + '->' + l[c] for c in isles))
      print('Sarong Flights: ', ', '.join(c + '->' + s[c] for c in isles))
    

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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: