Enigmatic Code

Programming Enigma Puzzles

Enigma 285: A dainty dish

From New Scientist #1432, 29th November 1984 [link]

Blackbird pie is popular at the Palace. The King and Queen help themselves to the pie in turn until it is finished. But court etiquette is strict. It is bad form to cut a blackbird in two. It is greedy to cut oneself a slice containing more birds than the previous slice taken. It would be the height of ill-breeding for the King, who has the first go, to take the whole lot straight away. But the King does like finishing the pie.

How many blackbirds should he take in his first slice to be sure of being able to do this?

There are, of course, four-and-twenty blackbirds in a pie.

[enigma285]

Advertisements

5 responses to “Enigma 285: A dainty dish

  1. Jim Randell 2 June 2015 at 7:38 am

    This Python program runs in 42ms.

    from enigma import irange, printf
    
    # what values can the king choose to be sure of being able finish the pie
    # t - total number of birds remaining
    # m - max number of birds that can be taken
    def choose(t, m):
      # is there anything left?
      if t > 0:
        # let the king take a piece
        for k in irange(min(m, t), 1, step=-1):
          # and if the king can get the final piece no matter what the queen takes
          if all(list(choose(t - k - q, q)) for q in irange(min(k, t - k), 1, step=-1)):
            yield k
    
    # the king can take at most 23 birds
    for k in choose(24, 23):
      printf("king chooses {k} birds")
    

    Solution: The King should take 8 blackbirds in his first slice to ensure he gets to finish the pie.

    If the King takes 8 blackbirds, that leaves 16 blackbirds in the pie when the Queen chooses and she can choose at most 8 blackbirds.

    If she chooses to take just 1, that leaves 15, and both the King and Queen are can only take 1 each of the remaining 15 at each turn. As 15 is an odd number the King gets to take the last piece. And in general if the King is presented with an odd number of birds he can take just 1 and will always be left with the last piece of pie (and if he is presented with an even number of birds if he takes only 1 he is forcing the Queen to take the last piece of pie).

    If the Queen takes 2, then that leaves 14 birds. The King takes 2 (as taking 1 would force the Queen to finish the pie), leaving 12. So the Queen is presented with an even number of birds and can choose to take 1 or 2. If she takes 1, then the King is forced to take the last piece of pie. If she takes 2 then the King is again presented with an even number of birds and so will also choose to take 2. And so each takes 2 of the remaining birds, until the King takes the final two. (And in general if the King is presented with an odd number of pairs, he can take 2 and force the Queen to either take 2 until the King is presented with the final pair, or to take 1 and present the King with an odd number of birds, in which case he also eventually takes the final piece).

    If the Queen takes 3, then that leaves 13 birds, so the King can take 1 and force each remaining turn to take 1 so he ends up with the final piece.

    If the Queen takes 4, then that leaves 12 birds. The King also takes 4, leaving 8 birds. If the Queen takes 4 of these, the King takes the remaining 4. If the Queen takes 3 or 1 the King takes 1 of the remaining odd number and ends up with the final piece. If the Queen takes 2, then King is presented with 6 birds, an odd number of pairs, so will end up with the final piece.

    If the Queen takes 5, then that leaves 11 birds. The King can take 1, and so end up taking the final piece. Or he can take 3, leaving 8. So the situation above repeats (but this time the Queen doesn’t have an option of taking 4).

    If the Queen takes 6, then that leaves 10 birds (an odd number of pairs). The King takes 2, and eventually the last pair.

    If the Queen takes 7, then that leaves 9 birds. The King takes 1, and ends up taking the final piece.

    If the Queen takes 8, then the King takes the remaining 8.

    My program can be modified to produce the 21 possible sequences. Each starts with the King choosing 8, and ends after an odd number of “takes” with the King taking the final piece of the pie:

    [8, 8, 8]
    [8, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    [8, 6, 2, 2, 2, 2, 2]
    [8, 6, 2, 2, 2, 1, 1, 1, 1]
    [8, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1]
    [8, 5, 3, 3, 1, 1, 1, 1, 1]
    [8, 5, 3, 2, 2, 2, 2]
    [8, 5, 3, 2, 2, 1, 1, 1, 1]
    [8, 5, 3, 1, 1, 1, 1, 1, 1, 1, 1]
    [8, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    [8, 4, 4, 4, 4]
    [8, 4, 4, 3, 1, 1, 1, 1, 1]
    [8, 4, 4, 2, 2, 2, 2]
    [8, 4, 4, 2, 2, 1, 1, 1, 1]
    [8, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1]
    [8, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    [8, 2, 2, 2, 2, 2, 2, 2, 2]
    [8, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1]
    [8, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1]
    [8, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    [8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    
    • geoffrounce 2 June 2015 at 3:32 pm

      Hi Jim

      Any chance you could give a few more words of explanation on how line 12 of your code works ?- there seems to be a lot going on in this single line!

      Thanks
      Geoff

      • Jim Randell 2 June 2015 at 5:35 pm

        Certainly. Here’s a more detailed explanation of how my code works.

        The choose(t, m) function is a generator that finds what values the King can choose, when presented with a pie containing t birds, and the maximum number of birds that can be taken is m, such that, no matter what number of birds the Queen chooses, the King can always be certain to take the final piece of pie.

        It is written as a Python generator, so when it finds a value, k, it uses the yield operator to pass it back to the calling routine. The calling routine can collect all the values (if there are any) by treating it as an iterator (which is what we do in lines 16 and 17).

        This means we can collect all the values by wrapping the call in a list() constructor. So:

        list(choose(7, 5)) ⇒ [3, 1]
        list(choose(6, 5)) ⇒ []

        When there are no guaranteed choices for the King this returns an empty list. In a boolean context an empty list evaluates to False, whereas a non-empty list evaluates to True.

        In the main part of the routine (at line 10), we consider how many birds the King can take by looking at values of k, starting with the largest number possible, min(t, m), and then working down to taking only 1 bird.

        So we consider what happens when the Queen makes her choice from the remaining t - k birds. She can choose any value q from min(k, t - k) down to 1. And we want to know if whatever value she chooses whether the King can always ensure he takes the final piece of pie.

        For each value q that the Queen chooses we look to see if there are values that the King can choose from the remaining t - (k + q) birds (with a maximum take of q) to guarantee getting the last piece of pie. We do this with a recursive call to choose(t - k - q, q), wrapped in the list() constructor to explore all the values.

        We do this with the all() construct, which returns True if all the values it is passed are True (when evaluated in a boolean context), and False otherwise. (all([]) is True). So this checks if, whatever value the Queen chooses, the King always has a take that will get him the final piece of pie.

        If this is the case, then the original choice for the King k is a value that guarantees he can get the last piece of pie, so we use yield to return it to the calling routine.

        If hope that gives you a better idea of what is going on.

        One of the advantages of using all(), rather than using a Python for loop, is that it will exit early if one of the elements it is testing evaluates to False, so it saves a more complicated loop with an early exit.

        In fact, instead of using list(choose(t, m)) to look for non-empty lists of values for the King to choose, we could use the any() construct. Which returns True when any of the elements it is passed evaluate to True in a boolean context. (any([]) is False).

        Also I now realise that there is no reason to examine k or q in reverse order, so we can simplify the irange() calls.

        So the modified program looks like this:

        from enigma import irange, printf
        
        # what values can the king choose to be sure of being able finish the pie
        # t - total number of birds remaining
        # m - max number of birds that can be taken
        def choose(t, m):
          # is there anything left?
          if t > 0:
            # let the king take a piece
            for k in irange(1, min(m, t)):
              # and if the king can get the final piece no matter what the queen takes
              if all(any(choose(t - k - q, q)) for q in irange(1, min(k, t - k))):
                yield k
        
        # the king can take at most 23 birds
        for k in choose(24, 23):
          printf("king chooses {k} birds")
        
    • Jim Randell 3 June 2015 at 9:13 am

      Also, after the King takes 8 birds, if the Queen wants to maximise the number she gets in total she should take 7 birds. The King then takes 1 bird to guarantee he gets the final piece of pie, and so each following take can only be one. This ends with the King taking a total of 13 birds and the Queen taking a total of 11.

      If the Queen wants to minimise the number of birds she gets in total the best she can do is 8 (and the King gets the other 16). There are many ways this can be achieved. The shortest is for her to take 8 on her first move, the King then takes the remaining 8. The longest is for her to take 1 on her first move, the remaining 15 birds are then taken one at a time.

  2. Brian Gladman 3 June 2015 at 8:51 am
    # pick a number of birds from those 'left'
    # (but not more than 'max_nbr')
    def pick(left, max_nbr):
      # the number of birds chosen 
      for n in range(1, min(left, max_nbr) + 1):
        # if the other person cannot win from
        # here, this number of birds is a win 
        if not any(pick(left - n, n)):
          yield n
    
    # solve for a pie with 'nbr' birds, choosing
    # not more than 'max_nbr' birds
    def solve(nbr, max_nbr, p):
      # if the king can pick all remaining birds
      if nbr <= max_nbr:
        yield p + [nbr]
      else:
        # find a number of birds that allows the king
        # to pick the last portion
        for k in pick(nbr, max_nbr):
          # now check all possible choices for the queen
          for q in range(1, min(nbr - k, k + 1)):
            # and look for a solution for what remains
            yield from solve(nbr - k - q, q, p + [k, q])
    
    for s in solve(24, 23, []):
      print(s)
    

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: