Task Information for Hotter Colder

Task Author: Gordon Cormack (CAN)

This problem is an interesting variant of the well-known guessing game Higher-Lower, also featured in the demonstration task Guess.

Higher-Lower is efficiently solved by the, also well-known, Binary Search algorithm. Binary Search maintains an interval of still possible numbers (candidates). Initially, this interval includes all numbers in the range. By comparing to the middle candidate, the interval can be halved by a single guess. Thus, the secret number can be determined in a logarithmic (to base 2) number of guesses. Or, to put it differently, if the range of allowed numbers is doubled, than the secret number can be determined with one additional guess.

Subtask 1

Doing a Linear Search, that is, successively calling Guess(i) for i from 1 to N, yields a solution requiring N calls to Guess, in the worst case. This solves Subtask 1. See below for a Pascal program.

Analysis

To get a better understanding of the Hotter-Colder problem, it helps to formalize the rules of this game.

Let J be Jill's number, and let P be the most recent guess, that is, Guess(P) was called last. In that situation, Guess(G) will return

    HOTTER if abs(G - J) < abs(P - J)
    COLDER if abs(G - J) > abs(P - J)
    SAME   if abs(G - J) = abs(P - J)
Or in a single formula: sign(abs(P - J) - abs(G - J)). Letting M = (P + G)/2, this can be rephrased as
  if P <= G then
    HOTTER if J > M
    COLDER if J < M
    SAME   if J = M
  else
    HOTTER if J < M
    COLDER if J > M
    SAME   if J = M
Or in a single formula: sign(G - P) * sign(J - M).

Thus, we see that each Guess(G) effectively provides a high-low comparison to the midpoint M. In fact, sign(G - P) * Guess(G) = sign(J - M) offers a genuine high-low comparison.

Unfortunately, due to the range restriction on G, we cannot make the midpoint M go wherever we want. So, a straightforward Binary Search is not going to work.

Subtask 2

Ignoring the results of all odd calls to Guess, we can extract one bit of information out of every successive pair of odd-numbered and next even-numbered call to Guess. This yields a solution that calls Guess at most W times, where W is the largest integer such that 2W/2≤N. That is, it makes at most log2 N2 (rounded up) calls to Guess. For N=500 (almost 29), this boils down to making at most 18 calls.

Subtask 3

By exploiting the fact that we actually do a high/low/equal comparison instead of a pure high/low (binary) comparison, we can gain almost one extra bit of information (taken over all guesses). Explanation: a complete binary tree with 2k leaves has 2k-1 internal nodes. So, the same number of high/low/equal guesses can reach twice the number of nodes minus one (compared to using just binary high/low guesses).

A Pascal program is given below.

Subtask 4

The preceding approaches obviously throw away (ignore) valuable information. However, using this information requires careful tuning of the guesses. It helps to do some small cases by hand.

In general, it turns out to be possible to determine Jill's number in no more than log2 3*N = log2 3 + log2 N calls of Guess.

We explain one such algorithm. Because of the nature of the guess (being a comparison), at any moment you have an interval of remaining candidate numbers. You can distinghuish two cases for the location of this interval with respect to the initial interval:

  1. either this interval of candidates contains 1 or N (is "against a wall");

  2. or it contains neither 1 nor N (is "in the middle").
Furthermore, you know what the previous guess was, say P.

If the interval of candidates is "in the middle", then you are home free (provided you are a bit careful), because now each guess can be made to reduce the interval sufficiently. In K more guesses, you can find Jill's number among 2K+1-1 candidates. [Details suppressed (for the time being)]

If the interval of candidates is "against a wall", then you can always arrange it so that the interval is 1 through P (or symmetrically on the other side). With two extra steps you can grow a solution that solves for P in K more guesses to one that solves for P+2K+2 in K+2 more guesses.

The base cases are P=3, K=1 and P=7, K=2.

The construction works like this. Consider the interval

aaaabbbbbbdddddddddd
where

Your next guess is G = P-2:

aaaabbbbbbdddddddddd
1G P      M        R
This guess compares to M = (G+R)/2 = (P-2 + P+2K+2)/2 = P + 2K+1-2 + 1, that is, the first element of the d-labeled subinterval. Do a case distinction on the result of this guess:

A C program solving Subtask 4 can be found here.

const
  Colder = -1;
  Same = 0;
  Hotter = +1;

type
  TResult = Colder .. Hotter;

function HC(N: Longint): Longint;
  { returns secret number of Jill }

  var
    r: TResult;  { result of Guess }
    G: Longint; { argument for Guess }
  
  begin
    if N = 1 then begin
      HC := N
    ; Exit
    end { if }
    { N >= 2 }
  ; G := 1
  ; r := Guess(G) { ignored }

  ; repeat
      { numbers >= G are remaining candidates; G < N }
      G := G + 1
    ; r := Guess(G) { compares to G - 0.5; r <> Same }
    until (r = Colder) or (G = N)

  ; case r of
      Colder: HC := G - 1;
      Hotter: HC := G;
    end { case r }
  end;
const
  Colder = -1;
  Same = 0;
  Hotter = +1;

type
  TResult = Colder .. Hotter;

function HC(N: Longint): Longint;
  { returns secret number of Jill }

  var
    r: TResult;  { result of Guess }
    a, b: Longint; { [a .. b] is interval of remaining candidates }
  
  begin
    if N = 1 then begin
      HC := N
    ; Exit
    end { if }
    { N >= 2 }
    
  ; a := 1
  ; b := N

    { invariant: 1 <= a <= b <= N }
  ; while a <> b do begin
      r := Guess(a) { ignored }
    ; r := Guess(b) { compares to (a+b)/2 }
    ; case r of
        Colder: b := (a + b - 1) div 2; { largest integer < (a+b)/2 }
        Same: begin a := (a + b) div 2 ; b := a end;
        Hotter: a := (a + b + 1) div 2; { smallest integer > (a+b)/2 }
      end { case r }
    end { while }
    { a = b }

  ; HC := a
  end;