Sunday Times Teaser 2784 – Three Lives

by Ian Kay

Published: 31 January 2016 (link)

I think of a whole number from 1 to 20 inclusive and Andy has to try to guess the number. He starts with three lives and makes successive guesses: after each guess I tell him whether it is right or too low or too high. If it is too high he loses one of his lives. To win the game he has to guess my number before his lives run out. He has developed the best possible strategy and can always win with a certain number of guesses or fewer. In fact no-one could be sure of winning with fewer guesses than that “certain number”.

What is that “certain number”?

2 Comments Leave one →

Brian Gladman permalink

This requires an adjustment of the well known binary splitting algorithm (which is often used as an exercise in computer science courses because it is very easy to get the details wrong and end up with a version that seems to work but doesn’t). I have implemented this algorithm quite a few times over the years and have frequently fallen foul of its subtleties so I hope I have got it right this time!

It is very similar in structure to Jim’s version below and I have adopted his command line interface so that the performance of the two versions can be compared.


from sys import argv
from functools import lru_cache

# find the maximum number of steps needed to determine
# a number in the range [lo ...[hi starting with lives
# in <lives>
@lru_cache(maxsize=None)
def trial(lo, hi, lives, steps=0, r=0):
  # if we have only one life left we have to try all
  # the remaining numbers from low to high
  if lives == 1 or hi < lo + 2:
    return steps + hi - lo

  # for the minimum neccesary steps from this position
  mx = []
  # now try each number as our next choice
  for pos in range(lo, hi):
    # find the number of steps to solve with this choice
    max_steps = max(
      # (1) if the choice is low
      trial(pos + 1, hi, lives, steps + 1, r + 1),
      # (2) if the choice is high
      trial(lo, pos, lives - 1, steps + 1, r + 1)
    )
    mx.append(max_steps)
  return mx if not r else min(mx)

N = (20 if len(argv) < 2 else int(argv[1]))
L = (3 if len(argv) < 3 else int(argv[2]))
r = trial(1, N + 1, L)
fs = 'At most {} guesses are needed for {} numbers with {} lives.'
print(fs.format(min(r), N, L), r)

from sys import argv

from functools import lru_cache

# find the maximum number of steps needed to determine

# a number in the range [lo ...[hi starting with lives

# in <lives>

@lru_cache(maxsize=None)

def trial(lo, hi, lives, steps=0, r=0):

# if we have only one life left we have to try all

# the remaining numbers from low to high

if lives == 1 or hi < lo + 2:

return steps + hi - lo

# for the minimum neccesary steps from this position

mx = []

# now try each number as our next choice

for pos in range(lo, hi):

# find the number of steps to solve with this choice

max_steps = max(

# (1) if the choice is low

trial(pos + 1, hi, lives, steps + 1, r + 1),

# (2) if the choice is high

trial(lo, pos, lives - 1, steps + 1, r + 1)

)

mx.append(max_steps)

return mx if not r else min(mx)

N = (20 if len(argv) < 2 else int(argv[1]))

L = (3 if len(argv) < 3 else int(argv[2]))

r = trial(1, N + 1, L)

fs = 'At most {} guesses are needed for {} numbers with {} lives.'

print(fs.format(min(r), N, L), r)

Jim Randell permalink

Without the complication of “lives” the maximum amount of numbers that can be distinguished with n guesses is given by:

G(1) = 1
G(n + 1) = 2G(n) + 1

which gives:

G(n) = 2^n – 1

So for 20 numbers the best strategy we can hope for will use 5 guesses in the worst case.

This Python program recursively examines the possibilities (and you can specify a different amount of numbers or lives on the command line):


from enigma import irange, cached, printf

# return the maximum number of guesses required
# ns - numbers remaining
# m - number of lives remaining
# g - number of guesses so far
@cached
def solve(ns, m, g=0, d=0):
  n = len(ns)
  # only one life remaining (or only one number):
  if m == 1 or n == 1:
    # we have to start with the smallest number and work up
    return g + n
  # two or three numbers need up to two guesses (start with the "middle" one)
  # (we don't really need this case, but it speeds things up a bit)
  if n < 4:
    return g + 2
  # more than one life remaining, we can guess any of the numbers
  rs = list()
  for (i, x) in enumerate(ns):
    # if we guess low we don't lose a life
    low = (0 if i == n - 1 else solve(ns[i + 1:], m, g + 1, d + 1))
    # if we guess high we lose a life
    high = (0 if i == 0 else solve(ns[:i], m - 1, g + 1, d + 1))
    # record the worst case
    rs.append(max(low, high))
  if d < 1: printf("{ns} -> {rs}")
  # choose the best worst case
  return min(rs)

from sys import argv
N = (20 if len(argv) < 2 else int(argv[1]))
L = (3 if len(argv) < 3 else int(argv[2]))

r = solve(tuple(irange(1, N)), L)
printf("[{N} numbers, {L} lives] min guesses = {r}")

from enigma import irange, cached, printf

# return the maximum number of guesses required

# ns - numbers remaining

# m - number of lives remaining

# g - number of guesses so far

@cached

def solve(ns, m, g=0, d=0):

n = len(ns)

# only one life remaining (or only one number):

if m == 1 or n == 1:

# we have to start with the smallest number and work up

return g + n

# two or three numbers need up to two guesses (start with the "middle" one)

# (we don't really need this case, but it speeds things up a bit)

if n < 4:

return g + 2

# more than one life remaining, we can guess any of the numbers

rs = list()

for (i, x) in enumerate(ns):

# if we guess low we don't lose a life

low = (0 if i == n - 1 else solve(ns[i + 1:], m, g + 1, d + 1))

# if we guess high we lose a life

high = (0 if i == 0 else solve(ns[:i], m - 1, g + 1, d + 1))

# record the worst case

rs.append(max(low, high))

if d < 1: printf("{ns} -> {rs}")

# choose the best worst case

return min(rs)

from sys import argv

N = (20 if len(argv) < 2 else int(argv[1]))

L = (3 if len(argv) < 3 else int(argv[2]))

r = solve(tuple(irange(1, N)), L)

printf("[{N} numbers, {L} lives] min guesses = {r}")

(It uses the cached() function from the enigma.py library to speed up the execution.

For the problem in the puzzle text the first guess can be any number between 6 and 11.

It turns out that with 3 lives we can distinguish up to 25 numbers using a strategy of up to 5 guesses. In this case the first guess should be 11.

Sunday Times Teaser 2784 – Three Lives

by Ian Kay

Published: 31 January 2016 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta