Enigmatic Code

Programming Enigma Puzzles

Enigma 432: Holiday on the islands

From New Scientist #1582, 15th October 1987 [link]

Alan and Susan recently spent eight days among the six Oa-Oa islands, which are shown on the map as Os.

Enigma 432

Only two of the islands, Moa-Moa and Noa-Noa, have names and hotels. The lines indicate the routes of the four arlines: Airways, Byair, Smoothflight and Transocean.

Alan and Susan started their holiday on the morning of the first day on Moa-Moa or Noa-Noa. On each of the eight days they would fly out to an unnamed island in the morning and then on to a named island in the afternoon and spend the night on that island. They each had eight airline tickets and each ticket was a single one-island-to-the next journey for two passengers. Alan had two Airways and six Byair tickets, while Susan had three Smoothflight and five Transocean tickets. They noticed that whatever island they were on, only one of them would have tickets for the flights out and so they agreed that, each time, that person should choose which airline to use.

Now Alan preferred that they should spend the nights on Moa-Moa, while Susan preferred Noa-Noa. However, they are an inseparable couple. So they each worked out the best strategy for the use of their tickets in order to spend the maximum number of nights on their favourite island.

How many nights did they spend on each island?

[enigma432]

Advertisements

10 responses to “Enigma 432: Holiday on the islands

  1. Jim Randell 19 January 2018 at 8:56 am

    The puzzle has been carefully constructed so that at each island only one person holds possible onward tickets. So, (numbering the unnamed islands 1, 2, 3, 4 from left to right) Alan makes the choice at islands M, 2, 3, and Susan makes the choice at N, 1, 4.

    This Python program computes example itineraries where both players are seeking to maximise their respective goals. It runs in 237 ms.

    Run: [ @repl.it ]

    from enigma import find, unpack, Accumulator, printf
    
    # <s> -> <d> -> <tickets>
    graph = {
      'M': { '1': 'A', '4': 'B' },
      'N': { '2': 'S', '3': 'T' },
      '1': { 'M': 'ST' },
      '2': { 'M': 'A', 'N': 'B' },
      '3': { 'M': 'AB' },
      '4': { 'M': 'T', 'N': 'S' },
    }
    
    # the metric for an itinerary = (<number of nights at M>, <number of nights at N>)
    def metric(vs, es):
      s = vs[2::2]
      return (s.count('M'), s.count('N'))
    
    # Alan's goal is to maximise M
    A = unpack(lambda M, N: M)
    
    # Susan's goal is to maximise N
    B = unpack(lambda M, N: N)
    
    # find an itinerary, return (<islands visited>, <tickets used>)
    # s - start island
    # ts - remaining tickets
    # vs - islands visited
    # es - tickets used
    def solve(s, ts, vs='', es=''):
      # all tickets exhausted
      if not ts:
        return (vs, es)
      else:
        # use the appropriate goal
        goal = (A if s in 'M23' else B)
        # consider possible onward destinations
        rs = Accumulator(fn=max)
        for (d, tt) in graph[s].items():
          for t in tt:
            i = find(ts, t)
            if i != -1:
              # solve for the remaining tickets
              r = solve(d, ts[:i] + ts[i + 1:], vs + d, es + t)
              rs.accumulate_data(goal(metric(*r)), r)
        # return a maximal choice
        return rs.data
    
    
    # available tickets
    tickets = 'AABBBBBBSSSTTTTT'
    
    # start on M or N
    for s in 'MN':
      (vs, es) = solve(s, tickets, s)
      (M, N) = metric(vs, es)
      printf("start={s}, M={M} N={N} [{vs}, {es}]")
    

    Solution: They spent 5 nights on Moa-Moa and 3 nights on Noa-Noa.

    A possible itinerary starting on M is:

    1: M (A) 1 (T) M
    2: M (A) 1 (T) M
    3: M (B) 4 (T) M
    4: M (B) 4 (T) M
    5: M (B) 4 (T) M
    6: M (B) 4 (S) N
    7: N (S) 2 (B) N
    8: N (S) 2 (B) N

    And starting on N:

    1: N (T) 3 (A) M
    2: M (A) 1 (T) M
    3: M (B) 4 (T) M
    4: M (B) 4 (T) M
    5: M (B) 4 (T) M
    6: M (B) 4 (S) N
    7: N (S) 2 (B) N
    8: N (S) 2 (B) N

    They only differ on day 1, but both itineraries end up on M at the end of day 1.

    • Jim Randell 19 January 2018 at 2:00 pm

      I augmented my program to find all possible maximal itineraries, and I found there are 246 starting on M and 136 starting on N (giving 382 in total). But they all involve spending 5 nights on Moa-Moa and 3 nights on Noa-Noa.

      There are only two which have 2 day visits to each of the unnamed islands, they both start from N:

      1: N (T) 3 (B) M
      2: M (A) 1 (T) M
      3: M (A) 1 (T) M
      4: M (B) 4 (T) M
      5: M (B) 4 (S) N
      6: N (S) 2 (B) N
      7: N (S) 2 (B) N
      8: N (T) 3 (B) M

      1: N (T) 3 (B) M
      2: M (A) 1 (T) M
      3: M (A) 1 (T) M
      4: M (B) 4 (S) N
      5: N (S) 2 (B) N
      6: N (S) 2 (B) N
      7: N (T) 3 (B) M
      8: M (B) 4 (T) M

      • Brian Gladman 21 January 2018 at 12:00 am

        @Jim I am getting different answers here but I could be misunderstanding how you define ‘maximal itineraries’. This could mean that all islands are visited at least once or that all twelve airline routes are used at least once (or both). Or something else maybe?

        • Jim Randell 21 January 2018 at 4:36 pm

          @Brian: I’m talking about the number of different itineraries that could be outcomes of the situation described in the puzzle (where each person is seeking to maximise the number of nights spent of their preferred island, by making the appropriate ticket choice). I found 382 different itineraries (destination islands and ticket orders).

          • Brian Gladman 22 January 2018 at 10:14 am

            There may be a bug in this code that is giving erroneous itineraries but I found 36 paths covering all islands at least twice with (M, N) = (5, 3):

            from itertools import zip_longest as zipl
            
            # map the airlines and destinations from each island
            paths = {'1':('MS', 'MT'), '4':('NS', 'MT'), '3':('MA', 'MB'), 
                     '2':('MA', 'NB'), 'M':('1A', '4B'), 'N':('2S', '3T')}
            
            # find solutions for the sequence of islands visited
            # where iseq is the sequence of islands visited and
            # aseq is the sequence of airlines used
            def solve(tkts, iseq, aseq):
              # have we finsihed?
              if not tkts:
                yield iseq, aseq
              else:
                # try all outward flights from the last island visited
                for ds, al in paths[iseq[-1]]:
                  if al in tkts:
                    yield from solve(tkts.replace(al, '', 1), iseq + ds, aseq + al)
             
            # Alan's and Susan's tickets
            tkts = 'AABBBBBBSSSTTTTT'
            
            # consider both Moa-Moa and Noa-Noa as the start island
            for first in 'MN':
              sol = set()
              for s, t in solve(tkts, first, ''):
                # count the nights on each island
                cts = list(s[1:].count(x) for x in 'MN1234')
                if all(c >= 2 for c in cts) and {3, 5} < set(cts):
                  it = ''.join(a + (b if b else '') for a, b in zipl(s, t))
                  st = ''
                  for i, c in enumerate(it):
                    if c in 'STAB':
                      st += ' (' + c + ') '
                    elif i != 0 and i != len(it) - 1 and c in 'MN':
                      st += c + '\n' + c
                    else:
                      st += c
                  st += '\n'
                  sol.add(st)
              for i, s in enumerate(sol, 1):
                print(i)
                print(s)
            
            • Jim Randell 22 January 2018 at 12:27 pm

              @Brian: But would all these show up as itineraries in a game where each player is playing optimally?

              For instance, your code outputs itineraries that start “1: N (S) 2 (B) N”, but my tests indicate that if we started on island N and Susan choose to fly to island 2 (via S), then Alan would choose to fly to island M (via A), and in the end they would have stayed 6 nights on M and only 2 nights on N. But if Susan chooses to fly to island 3 (via T), then they would end up staying 5 nights on M and 3 nights on N, which is what Susan would prefer, and as she’s making the choice at N this is what would happen.

              It looks like Susan is better off not using S to fly to island 2 until Alan has used up both his A tickets, and then he is forced to fly them back to N on a B ticket.

              It feels like I really ought to know more about Game Theory to get a proper understanding of this kind of puzzle.

              • Hugh Casement 22 January 2018 at 12:48 pm

                There’s a book that I first encountered at school some 55 years ago:
                The Compleat Strategyst, being a primer on the theory of games of strategy
                by J.D. Williams (McGraw-Hill, 1954).
                I picked up a copy in the 1980s when the library at the IBM labs near Stuttgart was having a clear-out. It’s quite entertaining to read, but I can’t promise it would help with this puzzle.

              • Brian Gladman 22 January 2018 at 2:56 pm

                I am not sure that Game Theory will help here since the difference is caused by two different approaches in applying the strategy.

                If, as you suggest, they each apply an non co-operative strategy during the holiday, they will then only find two tours that visit all the islands (I get the same results as you do here). And, of course, they would be very unlikely to visit all the islands twice unless they planned for this in advance.

                But if they plan a co-operative optimal route planning strategy in advance, they will then find 36 ‘all islands’ routes.

  2. Brian Gladman 19 January 2018 at 9:32 am
    from itertools import zip_longest as zipl
    
    #                     -------<-------
    #            Moa-Moa /       T       \
    #   W O------<------O-------->--------O X
    #      \     A     /|\       B        |
    #       ----->----- |A,B              v S
    #           S,T     |   --<--O--<--   |
    #                 A ^        Y      T |
    #                   |        S       \|
    #                 Z O--------<--------O Noa-Noa
    #                    \       B       /
    #                     ------->-------          
    
    # labels for the islands
    M, N, W, X, Y, Z = islands = range(6)
    # labels for the airlines
    A, B, S, T = airlines = range(4)
    
    # map the airlines and destinations from each island
    paths = {W:((S, M), (T, M)), X:((S, N), (T, M)), Y:((A, M), (B, M)), 
             Z:((A, M), (B, N)), M:((A, W), (B, X)), N:((S, Z), (T, Y))}
    
    # find solutions for the sequence of islands visited
    # where iseq is the sequence of islands visited and
    # aseq is the sequence of airlines used
    def solve(at, st, iseq, aseq):
      # have we finsihed?
      if len(iseq) == 17:
        yield iseq, aseq
      else:
        # for collecting soltions 
        sols = []
        # try all outward flights from the last island visited
        for al, ds in paths[iseq[-1]]:
          # if we use one of Alan's tickets
          if at[al]:
            op = M
            atn, stn = tuple(x - 1 if i == al else x for i, x in enumerate(at)), st
          # otherwise we use one of Susan's
          elif st[al]:
            op = N
            atn, stn = at, tuple(x - 1 if i == al else x for i, x in enumerate(st))
          else:
            continue
          sols.append(list(solve(atn, stn, iseq + (ds,), aseq + (al,))))
        # if there is only one possible outward flight, use it
        if len(sols) == 1:
          yield from sols[0]
        else:
          # otherwise use the outward flight that is better for the
          # person whose tickets are being used - find which choice
          # gives them more nights on their favourite island
          mx = [0, 0]
          for i, ss in enumerate(sols):
            for s, t in ss:
              m = s.count(op)
              if m > mx[i]:
                mx[i] = m
          # ... and consider only solutions that are optimum for them
          for s, t in sols[0 if mx[0] >= mx[1] else 1]:
            if s.count(op) == max(mx):
              yield s, t
    
    # Alan's and Susan's numbers of tickets (in order A, B, S, T)
    at, st = (2, 6, 0, 0), (0, 0, 3, 5)
    
    # consider both Moa-Moa and Noa-Noa as the start island
    for first in (M, N):
      for s, t in solve(at, st, (first,), ()):
        # count the night on Moa-Moa and Noa-Noa
        mc, nc = s[1:].count(M), s[1:].count(N)
        j = ''.join('MNWXYZ'[s] + 
                    ('' if a is None else 'ABST'[a]) + '>' for s, a in zipl(s, t))
        print(f'{mc} nights on Moa-Moa, {nc} nights on Noa-Noa:', j[:-1])
    

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 )

w

Connecting to %s

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

%d bloggers like this: