# 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))
```

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