Enigmatic Code

Programming Enigma Puzzles

Enigma 91: Hidden gifts

From New Scientist #1235, 8th January 1981 [link]

“Beauty? Courage? Generosity? Patience? Wisdom? Which do you wish for the new-born Princess?” asked the Good Fairy.

“Beauty and Wisdom will do nicely, thank you,” replied the King, not wanting to seem greedy.

“Wait! For each gift you name, I shall bestow on her two of the other gifts instead. Each name of a gift triggers a different pair. Each gift is triggered by two of the names. But if you mention both names, they cancel out and she will not get that gift at all.”

“Coo, shiver my sceptre!” exclaimed His Majesty.

“Quite simple! For instance if you ask for Beauty and Courage, she will receive Generosity and Patience. If you ask for Beauty, Generosity and Patience, she will receive those three and Wisdom too. You in fact wished for Beauty and Wisdom. She shall have them, provided you ask for them in the simplest way.”

What gift or gifts should His Majesty ask for?

[enigma91]

One response to “Enigma 91: Hidden gifts

  1. Jim Randell 20 May 2013 at 8:28 am

    If we take it that the result is to end up with only Beauty and Wisdom then there is a unique simplest way to ask for these (if by simplest we mean asking for the fewest number of gifts), and so this is probably what is intended.

    This Python program finds these solutions in 62ms.

    from collections import Counter
    from itertools import combinations
    from enigma import irange, printf
    
    # the gifts
    gifts = 'BCGPW'
    
    # gifts if sequence s is asked for
    def ask(d, s):
      c = Counter()
      for x in s: c.update(d[x])
      return ''.join(sorted(k for (k, v) in c.items() if v % 2 == 1))
    
    # check for a solution
    def check(d):
      # B + C => G + P
      if ask(d, 'BC') != 'GP': return
      # B + G + P => B + G + P + W
      if ask(d, 'BGP') != 'BGPW': return
      # find shortest sequences that give B + W
      print('[' + ', '.join(k + ' => ' + ''.join(sorted(v)) for (k, v) in d.items()) + ']')
      done = False
      for n in irange(1, len(gifts)):
        for s in combinations(gifts, n):
          g = ask(d, s)
          if not('B' in g and 'W' in g): continue
          #if g != 'BW': continue
          print(''.join(s), '=>', g)
          done = True
        if done: break
    
    def update(d, k, v):
      d = d.copy()
      d[k] = v
      return d
    
    def assign(d, g, c):
      # are we done?
      if len(g) == 0:
        check(d)
        return
      # else choose two gifts to assign
      for s in combinations(c, 2):
        if s[0] == s[1] or g[0] in s: continue
        assign(update(d, g[0], s), g[1:], c - Counter(s))
    
    assign(dict(), gifts, Counter(gifts * 2))
    

    Solution: The King should ask for Beauty and Wisdom.

    There are two possible mappings of “asked for” gifts to “bestowed” gifts:

    [1] P → C+G, C → G+W, B → P+W, W → B+P, G → B+C
    [2] P → B+C, C → P+W, B → G+W, W → B+G, G → C+P

    In each of these cases asking for B+W gives (exactly) B+W:

    [1] ask(B+W) = (P+W) + (B+P) = B+W
    [2] ask(B+W) = (G+W) + (B+G) = B+W

    However, by relaxing the constraint that the Beauty and Wisdom should be the only gifts received, there are several other answers, asking for an equally short number of gifts, whereby the Princess could receive Beauty, Wisdom and an additional two gifts. Although in this case there is no unique solution.

    The possible mappings are the same, but we can receive B+W (along with extra gifts) by asking for the following:

    [1] ask(B+G) = (P+W) + (B+C) = B+W+C+P
    [1] ask(C+G) = (G+W) + (B+C) = B+W+C+G
    [1] ask(C+W) = (G+W) + (B+P) = B+W+G+P

    [2] ask(B+P) = (G+W) + (B+C) = B+W+C+G
    [2] ask(C+P) = (P+W) + (B+C) = B+W+C+P
    [2] ask(C+W) = (P+W) + (B+G) = B+W+G+P

    However, in both cases asking for Courage and Wisdom will bestow Beauty and Wisdom along with Generosity and Patience, so this might be a better solution to the puzzle.

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: