Enigmatic Code

Programming Enigma Puzzles

Enigma 46: Rising prices

From New Scientist #1189, 10th January 1980 [link]

George recently hit upon a plan to get his three daughters up earlier in the mornings. He promised each one penny on each day she was down before him. He further offered one extra penny for a second consecutive day, two extra for a third consecutive day and so on. Thus five consecutive days would be worth 1 + 2 + 3 + 4 + 5 = 15 pence. But the days had to be consecutive.

The scheme ran for eight days, Monday to Monday inclusive. George managed to be first down on one day and third on two others. Otherwise he was always triumphantly last. Alice made more money than Brenda, who was last down on Sunday, and the whole scheme, as it turned out, could not have cost George less than it did for a tally of one first and two third places.

On which day or days was George down before Cynthia?



One response to “Enigma 46: Rising prices

  1. Jim Randell 15 January 2013 at 9:54 am

    In order to arrive at the published solution, I found it necessary to interpret the phrase “the whole scheme could not have cost George less that it did for a tally of one first and two third places” to mean that overall George must have one first place, no second places, two third places and five last places.

    This Python program tries all possible combinations where G is up 1st once, 3rd twice and last the rest of the time in order to find the minimum payout, and also records possible solutions (where A earns more than B, and B is up last on Sunday). Then finally outputs the minimal solutions. It runs in 49ms.

    from itertools import combinations, product
    from enigma import irange, printf
    # label the days
    DAY = [ 'Mon1', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat', 'Sun', 'Mon2' ]
    # indices of A, B, C
    (A, B, C) = (0, 1, 2)
    # the possible situations for A, B, C getting up before G are:
    g4 = (1, 1, 1) # G up 4th
    g1 = (0, 0, 0) # G up 1st
    g3s = [(1, 1, 0), (1, 0, 1), (0, 1, 1)] # G up 3rd
    # possible days
    ds = set(irange(0, 7))
    # how much do A, B and C earn from this sequence of days?
    def check(ds):
      t = [0, 0, 0]
      for x in (A, B, C):
        r = 1
        for d in ds:
          if d[x]:
            t[x] += r
            r += 1
            r = 1
      return t
    r = dict()
    # G is 1st up on 1 day
    for dg1 in ds:
      # and 4th up on 5 days (but not Sunday = day 6)
      for dg4 in combinations(ds.difference((dg1, 6)), 5):
        # and the other 2 days G is up 3rd
        days = [dg1] + list(dg4) + list(ds.difference(dg4 + (dg1,)))
        # make a corresponding list of when payment is due
        for (g3a, g3b) in product(g3s, repeat=2):
          pays = [g1] + [g4] * 5 + [g3a, g3b]
          # order the days chronologically
          d = list(pays[x[1]] for x in sorted(zip(days, range(8))))
          # and compute the overall amounts
          (a, b, c) = check(d)
          s = a + b + c
          if not s in r: r[s] = []
          # record possible solutions, when A earns more than B, and B doesn't get paid on Sunday
          if a > b and d[6][B] == 0: r[s].append(d)
    # find the minimum possible pay out
    m = min(r.keys())
    for d in r[m]:
      # who got up before G on each day?
      printf('[{s}]', s=', '.join(DAY[i] + ': ' + ''.join(x[1] for x in zip(p, 'ABC') if x[0]) for (i, p) in enumerate(d)))
      # who earned what?
      (a, b, c) = check(d)
      printf("[A={a} B={b} C={c} sum={s}]", s=a + b + c)
      # and the solution: on what days is G down before C?
      printf('G < C: {s}', s=', '.join(DAY[i] for (i, p) in enumerate(d) if p[C] == 0))

    Solution: George was down before Cynthia on Thursday and Saturday.

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: