Sunday Times Teaser 3179 – Sums and Products

by BRG on August 25, 2023

by Andrew Skidmore

Published Sunday August 27 2023 (link)

Mrs Green uses a dice game to improve the maths skills of her pupils. The children sit four to a table and each child throws five dice. Points are awarded according to the sum and product for each child; bonus points are awarded if the five scores contain three or more of the same number.

At Liam’s table all four children had the same sum but all achieved that sum in different ways. Surprisingly, all of the twenty dice scored more than one and no bonus points were awarded. The distribution of scores was: sixes…5; fives…4; fours…2; threes…4; twos…5. Liam had the highest product.

What, in ascending order, were Liam’s five scores?

From → Uncategorized

5 Comments Leave one →

BRG permalink


from itertools import combinations
from collections import Counter
from functools import reduce
  
# throw <n> dice giving no 1's, no more than two of 
# each other value and with an overall sum of <sm>
def play(n, sm, seq=()):
  if n == 0:
    if sm == 0:
      yield seq
  else:  
    for d in range(2 if not seq else seq[-1], 7):
      if seq.count(d) < 2 and n * d <= sm:
        yield from play(n - 1, sm - d, seq + (d,))

# the target numbers of result values in 4 throws of 5 dice
target = Counter({2:5, 3:4, 4:2, 5:4, 6:5})

# find the common sum from the target
common_sum = sum(c * t for c, t in target.items()) // 4

# consider all 5-die throws that have the common sum
for c4 in combinations(play(5, common_sum), 4):
  # have we hit the target for the dice of each value?
  if Counter(d for d5 in c4 for d in d5) == target:
    # find the 5-die throw with the maximum product
    f = lambda c: reduce(lambda x, y: x * y, c, 1)
    print(f"Liam's score: {max(c4, key=f)}")

from itertools import combinations

from collections import Counter

from functools import reduce

# throw <n> dice giving no 1's, no more than two of

# each other value and with an overall sum of <sm>

def play(n, sm, seq=()):

if n == 0:

if sm == 0:

yield seq

else:

for d in range(2 if not seq else seq[-1], 7):

if seq.count(d) < 2 and n * d <= sm:

yield from play(n - 1, sm - d, seq + (d,))

# the target numbers of result values in 4 throws of 5 dice

target = Counter({2:5, 3:4, 4:2, 5:4, 6:5})

# find the common sum from the target

common_sum = sum(c * t for c, t in target.items()) // 4

# consider all 5-die throws that have the common sum

for c4 in combinations(play(5, common_sum), 4):

# have we hit the target for the dice of each value?

if Counter(d for d5 in c4 for d in d5) == target:

# find the 5-die throw with the maximum product

f = lambda c: reduce(lambda x, y: x * y, c, 1)

print(f"Liam's score: {max(c4, key=f)}")

Frits permalink

No recursion this time.


from itertools import product, combinations 

from functools import reduce
from operator import mul

# multiply elemenfive_throws
mult = lambda li: reduce(mul, li, 1)

# frequency: 5 twos, 4 threes, 2 fours, 4 fives and 5 sixes
target = [5, 4, 2, 4, 5]
T = sum([i * target[i - 2] for i in range(2, 7)])
T //= 4 

five_throws = set()
# generate scores of 5 different throws
for p in product(range(2, 7), repeat=4):
  if not 1 < T - (s := sum(p)) < 7: continue
  p += (T - s, )
  # scores didn't contain three or more of the same number
  if any(p.count(i) > 2 for i in range(2, 7)): continue
  five_throws.add(tuple(sorted(p)))

# choose 4 scores and check the frequency of the numbers
for c in combinations(five_throws, 4):
  all_throws = [y for x in c for y in x]
  # check frequencies
  if any(all_throws.count(i) != target[i - 2] for i in range(2, 7)): continue
  
  # Liam had the highest product
  products = [mult(x) for x in c]
  print("answer:", c[products.index(max(products))])

from itertools import product, combinations

from functools import reduce

from operator import mul

# multiply elemenfive_throws

mult = lambda li: reduce(mul, li, 1)

# frequency: 5 twos, 4 threes, 2 fours, 4 fives and 5 sixes

target = [5, 4, 2, 4, 5]

T = sum([i * target[i - 2] for i in range(2, 7)])

T //= 4

five_throws = set()

# generate scores of 5 different throws

for p in product(range(2, 7), repeat=4):

if not 1 < T - (s := sum(p)) < 7: continue

p += (T - s, )

# scores didn't contain three or more of the same number

if any(p.count(i) > 2 for i in range(2, 7)): continue

five_throws.add(tuple(sorted(p)))

# choose 4 scores and check the frequency of the numbers

for c in combinations(five_throws, 4):

all_throws = [y for x in c for y in x]

# check frequencies

if any(all_throws.count(i) != target[i - 2] for i in range(2, 7)): continue

# Liam had the highest product

products = [mult(x) for x in c]

print("answer:", c[products.index(max(products))])

BRG permalink

Hi Frits,

It is quite fast but a lot faster in relative terms with combinations_with_replacement() in place of product().

Brian

Reply

Frits permalink

You are right. As I got a time under 10ms I didn’t really bother about this.
Following is a small benchmark.

combinations_with_replacement() has probably been written in C.


from itertools import combinations_with_replacement as cwr, product
from time import perf_counter

T = 44

def cwr1(seq, k, s=[]):
  if not k:
    yield s
  else:  
    for i, n in enumerate(seq):
      yield from cwr1(seq[i:], k - 1, s + [n])

# https://stackoverflow.com/questions/73512540/is-complexity-of-itertools-combinations-with-replacement-the-same-of-itertools
def cwr2(iterable, r):
  # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
  pool = tuple(iterable)
  n = len(pool)
  if not n and r:
    return
  indices = [0] * r
  yield tuple(pool[i] for i in indices)
  while True:
    for i in reversed(range(r)):
      if indices[i] != n - 1:
        break
    else:
      return
    indices[i:] = [indices[i] + 1] * (r - i)
    yield tuple(pool[i] for i in indices)      

prod = lambda s, k: product(s, repeat=k)
prod.__name__ = "product"

funcs = (cwr, cwr1, cwr2, prod)
for fn in funcs:
  start = perf_counter()
  five_throws = set()
  # generate scores of 5 different throws
  for p in fn(range(2, 7), T // 4 - 1):
    if not 1 < T - (s := sum(p)) < 7: continue
    p += (T - s, )
    # scores didn't contain xx or more of the same number
    if any(p.count(i) > T // 3  for i in range(2, 7)): continue
    five_throws.add(tuple(sorted(p)))   

  print("# length = ", len(five_throws)) 
  print(f"# Time spent in {fn.__name__} is: {perf_counter() - start}\n")

# length =  69
# Time spent in combinations_with_replacement is: 0.0009695999997347826

# length =  69
# Time spent in cwr1 is: 0.004130599999371043

# length =  69
# Time spent in cwr2 is: 0.0047040999997989275

# length =  69
# Time spent in product is: 11.86337949999961

from itertools import combinations_with_replacement as cwr, product

from time import perf_counter

T = 44

def cwr1(seq, k, s=[]):

if not k:

yield s

else:

for i, n in enumerate(seq):

yield from cwr1(seq[i:], k - 1, s + [n])

# https://stackoverflow.com/questions/73512540/is-complexity-of-itertools-combinations-with-replacement-the-same-of-itertools

def cwr2(iterable, r):

# combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC

pool = tuple(iterable)

n = len(pool)

if not n and r:

return

indices = [0] * r

yield tuple(pool[i] for i in indices)

while True:

for i in reversed(range(r)):

if indices[i] != n - 1:

break

else:

return

indices[i:] = [indices[i] + 1] * (r - i)

yield tuple(pool[i] for i in indices)

prod = lambda s, k: product(s, repeat=k)

prod.__name__ = "product"

funcs = (cwr, cwr1, cwr2, prod)

for fn in funcs:

start = perf_counter()

five_throws = set()

# generate scores of 5 different throws

for p in fn(range(2, 7), T // 4 - 1):

if not 1 < T - (s := sum(p)) < 7: continue

p += (T - s, )

# scores didn't contain xx or more of the same number

if any(p.count(i) > T // 3 for i in range(2, 7)): continue

five_throws.add(tuple(sorted(p)))

print("# length = ", len(five_throws))

print(f"# Time spent in {fn.__name__} is: {perf_counter() - start}\n")

# length = 69

# Time spent in combinations_with_replacement is: 0.0009695999997347826

# length = 69

# Time spent in cwr1 is: 0.004130599999371043

# length = 69

# Time spent in cwr2 is: 0.0047040999997989275

# length = 69

# Time spent in product is: 11.86337949999961

BRG permalink

My impression in looking at a lot of code is that “combinations with
replacement” is under appreciated!

Reply

Sunday Times Teaser 3179 – Sums and Products

by Andrew Skidmore

Published Sunday August 27 2023 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta