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 2^W/2≤N. That is, it makes at most log₂ N² (rounded up) calls to Guess. For N=500 (almost 2⁹), 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 2^k leaves has 2^k-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.

• N=3 can obviously be done in 2 guesses, by straddling the middle, for example, Guess(1) followed by Guess(3) does a high/low/equal comparison to 2.

• N=5 can be done in 3, but this already needs some care, because it does not work to set this up so that the first two guesses compare to the middle number 3. When, after Guess(1) Guess(5), or Guess(2) Guess(4), the result of the second guess is colder, you won't be able to solve the remaining problem in a single guess.

  You need to start with Guess(1) Guess(3) (or symmetrically Guess(5) Guess(3)). If the result of the second guess is same, Jill's number is 2; if the result is colder, only candidate 1 remains and this must be Jill's number. If the result is hotter, candidates 3, 4, and 5 remain. Since 3 was the most recent guess, doing Guess(5) will compare to 4, and we are done.

In general, it turns out to be possible to determine Jill's number in no more than log₂ 3*N = log₂ 3 + log₂ 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 2^K+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+2^K+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

• aaaa is the interval 1 through P (and we assume that if the most recent guess was at P, then an additional K guesses can determine Jill's number in this interval);
• bbbbbb is of length 2^K+1-2;
• dddddddddd is of length 2^K+1+2;
• the most recent guess was R = P+2^K+2.

Your next guess is G = P-2:

aaaabbbbbbdddddddddd
1G P      M        R

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

• Same: Jill's number is M; done.
• Colder: the interval is reduced to M+1 through R; continue with a "middle game" on ddddddddd of length 2^K+1+1;
• Hotter: the interval is reduced to 1 through M-1:

  aaaabbbbbb
  1G P      M
  

  Next, guess P, which boils down to comparing to (G+P)/2 = P-1. Do a case distinction on the result:
  • Colder: "wall game" on interval 1 through P (aaaa), which we assumed can be solved in K more guesses;
  • Hotter: "middle game" on abbbbbb of length 2^K+1-1.

A C program solving Subtask 4 can be found here.

Pascal program for Linear Search solving Subtask 1

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;

Pascal program for wasteful Binary Search solving Subtask 3

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;