Enigmatic Code

Programming Enigma Puzzles

Enigma 1134: Luck be a lady

From New Scientist #2290, 12th May 2001 [link]

I’ve asked Mystic Mog to advise me on my choice of lottery numbers. She has a way of assigning a measure of luck to each of the numbers from 01 to 49. She has given each of the digits a “luck factor”, with 0’s being less than 1’s, which is less than 2’s, etc. Then to calculate the luckiness of any of the lottery balls she simply adds together the luck factors of the two digits. For example, she regards 27 as luckier than 31 because the digit 2 has a higher luck factor than the 1 and the 7 has a higher luck factor than the 3.

She also tells me that if you consider all the balls excluding number 25, then precisely half of them are luckier than number 25 and half are less lucky than 25. Knowing all these facts, I can decide for most balls whether they are luckier than 25 or not. There are just three balls that I cannot decide about.

Which three?

[enigma1134]

Advertisements

2 responses to “Enigma 1134: Luck be a lady

  1. Jim Randell 2 January 2017 at 8:48 am

    This Python 3 program runs in 66ms

    from collections import defaultdict
    from enigma import irange, compare as _compare, printf
    
    # canonical form of 2 digit number x
    # returns (<lower-digit>, <higher-digit>)
    def canonise(x):
      (a, b) = divmod(x, 10)
      return (a, b) if a < b else (b, a)
    
    # compare two 2 digit numbers
    # returns:
    # -1 if x < y
    # +1 if x > y
    #  0 if x = y
    # None otherwise
    def compare(x, y):
      (a, b) = canonise(x)
      (c, d) = canonise(y)
      p = _compare(a, c)
      q = _compare(b, d)
      if p == q:
        return p
      elif p == 0:
        return q
      elif q == 0:
        return p
      else:
        return None
    
    # order the numbers ns with respect to x
    # returns a dictionary d
    # d[-1] = numbers less than x
    # d[+1] = numbers greater than x
    # d[0]  = numbers equal to x
    # d[None] = numbers incomparable to x
    def order(ns, x):
      d = defaultdict(list)
      for n in ns:
        d[compare(n, x)].append(n)
      return d
    
    # assign the numbers in rest consistently to lower and higher
    # such that there are nlower in lower and nhigher in higher
    def solve(rest, nlower, nhigher, lower=[], higher=[]):
      # are we done?
      if not rest:
        # do we have the same number of lower and higher numbers?
        if len(lower) == nlower and len(higher) == nhigher:
          yield (lower, higher)
      else:
        # otherwise choose a number n and find numbers that are lower and higher than it
        d = order(rest, rest[0])
        # so, if n is in the lower group, so is everything lower than it
        yield from solve(d[None] + d[+1], nlower, nhigher, lower + d[-1] + d[0], higher)
        # and if n is in the higher group, so is everything higher than it
        yield from solve(d[None] + d[-1], nlower, nhigher, lower, higher + d[0] + d[+1])
    
    
    # find numbers that are necessarily lower/higher than 25
    d = order(irange(1, 49), 25)
    
    printf("always lower = {lows}", lows=sorted(d[-1]))
    printf("always higher = {highs}", highs=sorted(d[+1]))
    printf("undecided = {uns}", uns=sorted(d[None]))
    
    # find numbers that are always lower and always higher
    (lows, highs) = (set(d[None]), set(d[None]))
    
    # assign the remaining numbers
    for (lower, higher) in solve(d[None], 24 - len(d[-1]), 24 - len(d[+1])):
      printf("[lower = {lower}, higher = {higher}]")
      lows.intersection_update(lower)
      highs.intersection_update(higher)
    
    printf("always lower = {lows}", lows=sorted(lows))
    printf("always higher = {highs}", highs=sorted(highs))
    
    # so the undecided numbers are:
    uns = set(d[None]).difference(lows, highs)
    
    printf("undecided = {uns}", uns=sorted(uns))
    

    Solution: The three numbers that cannot be decided are: 07, 16, 33.

    We can eliminate numbers that are definitely less lucky than 25 (because one of the digits is less than (or equal to) 2 and one of them less than (or equal to) 5). This gives the following list of 22 numbers:

    01, 02, 03, 04, 05, 10, 11, 12, 13, 14, 15, 20, 21, 22, 23, 24, 30, 31, 32, 40, 41, 42

    Similarly we get the following list of 14 numbers that are definitely more lucky that 25:

    26, 27, 28, 29, 35, 36, 37, 38, 39, 45, 46, 47, 48, 49

    Which leaves us with 12 numbers to decided about:

    06, 07, 08, 09, 16, 17, 18, 19, 33, 34, 43, 44

    We know that in total there are 24 numbers that are less lucky that 25 and 24 numbers that are more lucky than 25, so of these “undecided” numbers exactly two of them must be less lucky than 25 (and the remaining 10 are more lucky than 25).

    There are certain chains of numbers in this list when compared by luck values:

    06 < 07 < 08 < 09
    16 < 17 < 18 < 19
    06 < 16
    07 < 17
    08 < 18
    09 < 19
    33 < 34 = 43 < 44

    So we need to decide which pairs of these numbers can consistently be assigned to be less lucky than 25.

    So, for example, we cannot have 19 less lucky than 25, as then 06, 07, 08, 09, 16, 17, 18 would also be less lucky that 25, and we are only looking for two numbers to be less lucky. So 19 must be more lucky than 25. We can similarly see that 18, 17, 09, 08, 44, 43, 34 must all be more lucky than 25.

    This leaves us with three scenarios where exactly two of our undecided numbers are less lucky than 25:

    A: 06, 07
    B: 06, 16
    C: 06, 33

    In each of these cases 06 is less lucky than 25, but we cannot say whether 07, 16, 33 are less lucky or more lucky than 25. For each number it is less lucky than 25 in one of the cases given above, and more lucky in the other two.

    This table gives example luck values for the digits 0-9, to satisfy the above scenarios:

    enigma-1134-solution

    The luck values of the digits are given in the white cells.
    The luck value of 25 is given in the green cells.
    The remaining cells give the luck values of the 12 “undecided” numbers.
    Numbers that are less lucky than 25 appear in blue cells.
    Numbers that are more lucky than 25 appear in red cells.

  2. Brian Gladman 3 January 2017 at 10:26 pm
    # compare numbers in <seq> with a <target> number and
    # return the sets of numbers that are less lucky,  as
    # lucky, more lucky and those that cannot be decided 
    def partition(target, seq):
      # sets for less, equal, greaater and undecided
      lt, eq, gt, ud = set(), set(), set(), set()
      # the sorted digits of the target
      x, y = divmod(target, 10)
      x, y = (x, y) if x < y else (y, x)
      for n in seq:
        # sort its digits
        a, b = divmod(n, 10)
        a, b = (a, b) if a < b else (b, a)
        if a == x and b == y:
          eq.add(n)
        elif a <= x and b < y or a < x and b <= y:
          lt.add(n)
        elif a >= x and b > y or a > x and b >= y:
          gt.add(n)
        else:
          ud.add(n)
      return lt, eq, gt, ud
    
    # allocate numbers in <rest> to <low> or <high> whilst
    # ensuring that the lucky values of the numbers in the
    # two sets are consistent
    def balance(rest, low, high):
      # are all numbers allocated
      if not rest:
        # and low and high are of equal length
        if len(low) == len(high):
          yield low, high
      else:
        # allocate another number
        for n in rest:
          # find numbers that are less, equal, greater and
          # undecided when compared with it
          ls, eq, gt, ud = partition(n, rest)
          # if we add the number to the lower set, we must also 
          # add those that are less and equally lucky as well
          if len(low | ls | eq) <= 24:
            yield from balance(ud, low | ls | eq, high | gt)
          # otherwise try to add it to higher set with those 
          # that are equally and more lucky
          elif len(high | eq | gt) <= 24:
            yield from balance(ud, low | ls, high | eq | gt)
    
    # split the numbers into sets that are less, equally and more
    # lucky than 25 and those whose value cannot be determined
    ls, eq, gt, ud = partition(25, range(1, 50))
    
    # for accumulating numbers that are always less or more lucky 
    always_less, always_more = set(range(1, 50)), set(range(1, 50))
    
    # find solutions with 24 numbers in the lower and higher sets
    for l, h in balance(ud, ls, gt):
      # accumulate numbers that are always less and always more lucky
      always_less &= l
      always_more &= h
    # find those numbers that are not always less or always more lucky
    und = sorted(set(range(1, 50)) - {25} - always_less - always_more)
    print('Numbers {}, {} and {}.'.format(*und))
    

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: