Sunday Times Teaser 2775 – Strictly Not

by Angela Newing

Published: 29 November 2015 (link)

Four celebrities entered a dance competition. Five judges each shared out their eight marks among the four dancers, with each getting a non-zero whole number. Each judge split the eight marks in a different way and then allocated them as follows. Amanda’s marks to Lana and Natasha added to the same total as Barry’s marks to Madge and Paula. Barry gave more marks to Madge than to any other dancer, Charles gave more to Paula than to any other, and Doris gave more to Natasha than to any other. Lana scored more from Edna than from Amanda. All dancers had the same total so the head judge’s scores were used, giving a winner and runner-up. Who was the head judge, who was the winner and who was the runner-up?

2 Comments Leave one →

Brian Gladman permalink

I am short of time again today so I will post a solution here when I get more time to look at it. Here it is:


from itertools import permutations

judges = ('Amanda', 'Barry', 'Charles', 'Doris', 'Edna')
dancers = ('Lana', 'Madge', 'Natasha', 'Paula')

# output format
fs = 'The head judge was {}, the winner was {} and the runner-up was {}.'

# partition the integer 'nbr' into 'bits' bits with bits in the
# range min_bit .. max_bit (return bits in non-decreasing order)
def partitions(nbr, bits, min_bit=1, max_bit=0):
  t = max_bit if max_bit else nbr
  if bits == 1:
    if min_bit <= nbr <= t:
      yield [nbr]
  else:
    for i in range(min_bit, min(nbr // bits, t) + 1):
      for p in partitions(nbr - i, bits - 1, i, max_bit):
        yield [i] + p

def distinct_perms(seq):
  s = set()
  for p in permutations(seq):
    if p not in s:
      s.add(p)
  return list(s)

# store the different permutations for each of the possible
# distributions of a judges eight marks among four dancers
perms = tuple(distinct_perms(x) for x in partitions(8, 4, 1))

# a map in which m[J][D] is judge J's mark for dancer D
m = dict()

# permute the five partition permutations among the five judges
for marks in permutations(perms, 5):
  jm = dict(zip(judges, marks))

  # permute Barry's points among the dancers
  for pb in jm['Barry']:
    m['Barry'] = dict(zip(dancers, pb))

    # more of Barry's marks go to Madge than the others
    mx = max(pb)
    if pb.count(mx) > 1 or m['Barry']['Madge'] != mx:
      continue

    # permute Charles's points among the dancers
    for pc in jm['Charles']:
      m['Charles'] = dict(zip(dancers, pc))

      # more of Charles's marks go to Paula than the others
      mx = max(pc)
      if pc.count(mx) > 1 or m['Charles']['Paula'] != mx:
        continue

      # permute Doris's points among the dancers
      for pd in jm['Doris']:
        m['Doris'] = dict(zip(dancers, pd))

        # more of Doris's marks go to Natasha than the others
        mx = max(pd)
        if pd.count(mx) > 1 or m['Doris']['Natasha'] != mx:
          continue

        # permute Amanda's points among the dancers
        for pa in jm['Amanda']:
          m['Amanda'] = dict(zip(dancers, pa))

          # the sum of Amanda's marks for Lana and Natasha is equal
          # to the sum of Barry's marks for Madge and Paula
          if not (m['Amanda']['Lana'] + m['Amanda']['Natasha'] ==
              m['Barry']['Madge'] + m['Barry']['Paula']):
            continue

          # permute Edna's points among the dancers
          for pe in jm['Edna']:
            m['Edna'] = dict(zip(dancers, pe))

            # Lana scored more from Edna than from Amanda
            if not m['Edna']['Lana'] > m['Amanda']['Lana']:
              continue

            # the four dancers scores
            scores = tuple(sum(m[x][y] for x in judges) for y in dancers)
            # the dancers scores are equal at this point
            if len(set(scores)) == 1:

              # consider each possible head judge
              for hj in judges:
                # the points he/she awards to the five dancers
                pts = sorted(m[hj].values(), reverse=True)
                # there must be a winner and a runner-up
                if pts.count(pts[0]) == pts.count(pts[1]) == 1:
                  # output the head judge, the winner and the runner up
                  winner, = (x for x in dancers if m[hj][x] == pts[0])
                  runner_up, = (x for x in dancers if m[hj][x] == pts[1])
                  print(fs.format(hj, winner, runner_up))

100

from itertools import permutations

judges = ('Amanda', 'Barry', 'Charles', 'Doris', 'Edna')

dancers = ('Lana', 'Madge', 'Natasha', 'Paula')

# output format

fs = 'The head judge was {}, the winner was {} and the runner-up was {}.'

# partition the integer 'nbr' into 'bits' bits with bits in the

# range min_bit .. max_bit (return bits in non-decreasing order)

def partitions(nbr, bits, min_bit=1, max_bit=0):

t = max_bit if max_bit else nbr

if bits == 1:

if min_bit <= nbr <= t:

yield [nbr]

else:

for i in range(min_bit, min(nbr // bits, t) + 1):

for p in partitions(nbr - i, bits - 1, i, max_bit):

yield [i] + p

def distinct_perms(seq):

s = set()

for p in permutations(seq):

if p not in s:

s.add(p)

return list(s)

# store the different permutations for each of the possible

# distributions of a judges eight marks among four dancers

perms = tuple(distinct_perms(x) for x in partitions(8, 4, 1))

# a map in which m[J][D] is judge J's mark for dancer D

m = dict()

# permute the five partition permutations among the five judges

for marks in permutations(perms, 5):

jm = dict(zip(judges, marks))

# permute Barry's points among the dancers

for pb in jm['Barry']:

m['Barry'] = dict(zip(dancers, pb))

# more of Barry's marks go to Madge than the others

mx = max(pb)

if pb.count(mx) > 1 or m['Barry']['Madge'] != mx:

continue

# permute Charles's points among the dancers

for pc in jm['Charles']:

m['Charles'] = dict(zip(dancers, pc))

# more of Charles's marks go to Paula than the others

mx = max(pc)

if pc.count(mx) > 1 or m['Charles']['Paula'] != mx:

continue

# permute Doris's points among the dancers

for pd in jm['Doris']:

m['Doris'] = dict(zip(dancers, pd))

# more of Doris's marks go to Natasha than the others

mx = max(pd)

if pd.count(mx) > 1 or m['Doris']['Natasha'] != mx:

continue

# permute Amanda's points among the dancers

for pa in jm['Amanda']:

m['Amanda'] = dict(zip(dancers, pa))

# the sum of Amanda's marks for Lana and Natasha is equal

# to the sum of Barry's marks for Madge and Paula

if not (m['Amanda']['Lana'] + m['Amanda']['Natasha'] ==

m['Barry']['Madge'] + m['Barry']['Paula']):

continue

# permute Edna's points among the dancers

for pe in jm['Edna']:

m['Edna'] = dict(zip(dancers, pe))

# Lana scored more from Edna than from Amanda

if not m['Edna']['Lana'] > m['Amanda']['Lana']:

continue

# the four dancers scores

scores = tuple(sum(m[x][y] for x in judges) for y in dancers)

# the dancers scores are equal at this point

if len(set(scores)) == 1:

# consider each possible head judge

for hj in judges:

# the points he/she awards to the five dancers

pts = sorted(m[hj].values(), reverse=True)

# there must be a winner and a runner-up

if pts.count(pts[0]) == pts.count(pts[1]) == 1:

# output the head judge, the winner and the runner up

winner, = (x for x in dancers if m[hj][x] == pts[0])

runner_up, = (x for x in dancers if m[hj][x] == pts[1])

print(fs.format(hj, winner, runner_up))

Guy permalink


from itertools import permutations, product

def unique_permutations(iterable, r=None):
  previous = tuple()
  for p in permutations(sorted(iterable), r):
    if p > previous:
      previous = p
      yield p

judgenames = ('Amanda', 'Barry', 'Charles', 'Doris', 'Edna')
dancernames = ('Lana', 'Madge', 'Natasha', 'Paula')
fs = 'The head judge was {}, the winner was {} and the runner up was {}.'

# head judge needs to have unique highest and 2nd highest scores
headjudge = [1, 1, 2, 4]

for a, b, c, d, e in permutations(
  [(1, 1, 3, 3), (2, 2, 2, 2), (1, 1, 1, 5), (1, 1, 2, 4), (1, 2, 2, 3)]):
  for judges in product(unique_permutations(a), unique_permutations(b),
                        unique_permutations(c), unique_permutations(d),
                        unique_permutations(e)):
    
    if judges[0][0] + judges[0][2] == judges[1][1] + judges[1][3]:
      # test for Barry, Charles and Doris max scores which are unique
      if all((sorted(judges[1])[3] == judges[1][1], 
              sorted(judges[1])[3] != sorted(judges[1])[2],
              sorted(judges[2])[3] == judges[2][3],
              sorted(judges[2])[3] != sorted(judges[2])[2],
              sorted(judges[3])[3] == judges[3][2],
              sorted(judges[3])[3] != sorted(judges[3])[2])):
        
        if judges[4][0] > judges[0][0]:
          v = [sum(i) for i in zip(*judges)]
          # test for all dancers total scores to be the same
          if v[1:] == v[:-1]:
            for i in range(5):
              if sorted(judges[i]) == headjudge:
                for j in range(4):
                  if judges[i][j] == 4: 
                    winner = dancernames[j]
                  if judges[i][j] == 2:
                    runnerup = dancernames[j]
                print(fs.format(judgenames[i], winner, runnerup))

from itertools import permutations, product

def unique_permutations(iterable, r=None):

previous = tuple()

for p in permutations(sorted(iterable), r):

if p > previous:

previous = p

yield p

judgenames = ('Amanda', 'Barry', 'Charles', 'Doris', 'Edna')

dancernames = ('Lana', 'Madge', 'Natasha', 'Paula')

fs = 'The head judge was {}, the winner was {} and the runner up was {}.'

# head judge needs to have unique highest and 2nd highest scores

headjudge = [1, 1, 2, 4]

for a, b, c, d, e in permutations(

[(1, 1, 3, 3), (2, 2, 2, 2), (1, 1, 1, 5), (1, 1, 2, 4), (1, 2, 2, 3)]):

for judges in product(unique_permutations(a), unique_permutations(b),

unique_permutations(c), unique_permutations(d),

unique_permutations(e)):

if judges[0][0] + judges[0][2] == judges[1][1] + judges[1][3]:

# test for Barry, Charles and Doris max scores which are unique

if all((sorted(judges[1])[3] == judges[1][1],

sorted(judges[1])[3] != sorted(judges[1])[2],

sorted(judges[2])[3] == judges[2][3],

sorted(judges[2])[3] != sorted(judges[2])[2],

sorted(judges[3])[3] == judges[3][2],

sorted(judges[3])[3] != sorted(judges[3])[2])):

if judges[4][0] > judges[0][0]:

v = [sum(i) for i in zip(*judges)]

# test for all dancers total scores to be the same

if v[1:] == v[:-1]:

for i in range(5):

if sorted(judges[i]) == headjudge:

for j in range(4):

if judges[i][j] == 4:

winner = dancernames[j]

if judges[i][j] == 2:

runnerup = dancernames[j]

print(fs.format(judgenames[i], winner, runnerup))

Sunday Times Teaser 2775 – Strictly Not

by Angela Newing

Published: 29 November 2015 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta