Sunday Times Teaser 2497 – No Title

by DJT Hogg

Published August 1 2010 (link)

I have two jugs that hold whole numbers of pints, and together they hold two gallons. Using only the two jugs and a tap, discarding water as necessary, I can end up with a total of any whole number of pints from 1 to 16 in the two jugs combined. If I want to end up with exactly one pint in the most economical way possible, I have to draw more water than if I want to end up with exactly four pints.

What are the capacities of the two jugs?

One Comment Leave one →

Brian Gladman permalink


from math import gcd

# find a sequence of steps in filling, emptying and transferring
# water between two jugs of capacity ac and bc to reach a final
# content tgt (af, bf) in the jugs
# 
#  a,  b - the current content of jugs A and B
# ac, bc - the capacities of jugs A and B
# tgt    - the target combined content of the jugs
# w      - water discarded so far
# sv     - the set of contents (a, b) already seen
# js     - the sequence of contents (a, b) to reach the target 

def step(a, b, ac, bc, tgt, w=0, sv=set(), js=[]):
  # if we have reached the target
  if sum((a, b)) == tgt:
    yield w, js
  else:
    # fill A if it is empty
    if not a and (ac, b) not in sv:
      yield from step(ac, b, ac, bc, tgt, w, sv | {(ac, b)}, js + [(ac, b)])
    # fill B if it is empty
    if not b and (a, bc) not in sv:
      yield from step(a, bc, ac, bc, tgt, w, sv | {(a, bc)}, js + [(a, bc)])
      
    # empty A if it is full
    if a == ac and (0, b) not in sv:
      yield from step(0, b, ac, bc, tgt, w + a, sv | {(0, b)}, js + [(0, b)])
    # empty B if it is full
    if b == bc and (a, 0) not in sv:
      yield from step(a, 0, ac, bc, tgt, w + b, sv | {(a, 0)}, js + [(a, 0)])
    
    # if A is not empty and B is not full, fill B from A
    if a and b < bc:
      tx = min(a, bc - b)
      a, b = t = a - tx, b + tx
      if t not in sv:
        # leave remainder in A
        yield from step(a, b, ac, bc, tgt, w, sv | {t}, js + [(a, b)])
      if a and (0, b) not in sv:
        # leave A empty
        yield from step(0, b, ac, bc, tgt, w + a, sv | {t}, js + [(0, b)])
    
    # if B is not empty and A is not full, fill A from B
    if b and a < ac:
      tx = min(b, ac - a)
      a, b = t = a + tx, b - tx
      if t not in sv:
        # leave remainder in B
        yield from step(a, b, ac, bc, tgt, w, sv | {t}, js + [(a, b)])
      if b and (a, 0) not in sv:
        # leave B empty
        yield from step(a, 0, ac, bc, tgt, w + b, sv | {t}, js + [(a, 0)])

# find the most economical way of reaching a target amount 
def find_min(ac, bc, tgt):
  min_w = None
  min_js = None
  # consider all possible solutions
  for w, js in step(0, 0, ac, bc, tgt):
    # store the solution with the minimum of wasted water
    if not min_w or w < min_w:
      min_w = w
      min_js = js[:]
  return min_w, min_js

for ac in range(2, 9):
  bc = 16 - ac
  # to be able to generate all integer amounts of water from 1
  # to 16 litres, the two jugs must have co-prime capacities
  if gcd(ac, bc) == 1:
    # find the most economical ways of reaching one and four litres
    min_1w, min_1s = find_min(ac, bc, 1)
    min_4w, min_4s = find_min(ac, bc, 4)
    # mark solutions where one litre is less economical than four litres
    used_1, used_4 = min_1w + 1, min_4w + 4
    star = ' <== Soluion' if used_1 > used_4 else ''
    # output solutions
    print(f'Jug Capacities {ac} and {bc} (water used: 1:{used_1}, 4:{used_4}) {star}')
    print(f'  {min_1w:2} {min_1s}')
    print(f'  {min_4w:2} {min_4s}')
    print()

from math import gcd

# find a sequence of steps in filling, emptying and transferring

# water between two jugs of capacity ac and bc to reach a final

# content tgt (af, bf) in the jugs

# a, b - the current content of jugs A and B

# ac, bc - the capacities of jugs A and B

# tgt - the target combined content of the jugs

# w - water discarded so far

# sv - the set of contents (a, b) already seen

# js - the sequence of contents (a, b) to reach the target

def step(a, b, ac, bc, tgt, w=0, sv=set(), js=[]):

# if we have reached the target

if sum((a, b)) == tgt:

yield w, js

else:

# fill A if it is empty

if not a and (ac, b) not in sv:

yield from step(ac, b, ac, bc, tgt, w, sv | {(ac, b)}, js + [(ac, b)])

# fill B if it is empty

if not b and (a, bc) not in sv:

yield from step(a, bc, ac, bc, tgt, w, sv | {(a, bc)}, js + [(a, bc)])

# empty A if it is full

if a == ac and (0, b) not in sv:

yield from step(0, b, ac, bc, tgt, w + a, sv | {(0, b)}, js + [(0, b)])

# empty B if it is full

if b == bc and (a, 0) not in sv:

yield from step(a, 0, ac, bc, tgt, w + b, sv | {(a, 0)}, js + [(a, 0)])

# if A is not empty and B is not full, fill B from A

if a and b < bc:

tx = min(a, bc - b)

a, b = t = a - tx, b + tx

if t not in sv:

# leave remainder in A

yield from step(a, b, ac, bc, tgt, w, sv | {t}, js + [(a, b)])

if a and (0, b) not in sv:

# leave A empty

yield from step(0, b, ac, bc, tgt, w + a, sv | {t}, js + [(0, b)])

# if B is not empty and A is not full, fill A from B

if b and a < ac:

tx = min(b, ac - a)

a, b = t = a + tx, b - tx

if t not in sv:

# leave remainder in B

yield from step(a, b, ac, bc, tgt, w, sv | {t}, js + [(a, b)])

if b and (a, 0) not in sv:

# leave B empty

yield from step(a, 0, ac, bc, tgt, w + b, sv | {t}, js + [(a, 0)])

# find the most economical way of reaching a target amount

def find_min(ac, bc, tgt):

min_w = None

min_js = None

# consider all possible solutions

for w, js in step(0, 0, ac, bc, tgt):

# store the solution with the minimum of wasted water

if not min_w or w < min_w:

min_w = w

min_js = js[:]

return min_w, min_js

for ac in range(2, 9):

bc = 16 - ac

# to be able to generate all integer amounts of water from 1

# to 16 litres, the two jugs must have co-prime capacities

if gcd(ac, bc) == 1:

# find the most economical ways of reaching one and four litres

min_1w, min_1s = find_min(ac, bc, 1)

min_4w, min_4s = find_min(ac, bc, 4)

# mark solutions where one litre is less economical than four litres

used_1, used_4 = min_1w + 1, min_4w + 4

star = ' <== Soluion' if used_1 > used_4 else ''

# output solutions

print(f'Jug Capacities {ac} and {bc} (water used: 1:{used_1}, 4:{used_4}) {star}')

print(f' {min_1w:2} {min_1s}')

print(f' {min_4w:2} {min_4s}')

print()

Sunday Times Teaser 2497 – No Title

by DJT Hogg

Published August 1 2010 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta