GuessGame3.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace GuessGame
{
  public static class Problem
  {
    public interface IValidGuessList : IReadOnlyList<int>
    {
      IValidGuessList GetBefore(int index);
      IValidGuessList GetAfter(int index);
    }

    public class EmptyRange : IValidGuessList
    {
      private EmptyRange() { }
      static public EmptyRange Instance = new EmptyRange();

      public int Count => 0;
      public int this[int index] => throw new IndexOutOfRangeException();
      public IValidGuessList GetBefore(int index) => this;
      public IValidGuessList GetAfter(int index) => this;

      public IEnumerator<int> GetEnumerator() => Enumerable.Empty<int>().GetEnumerator();
      IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
    }

    public class SingleRange : IValidGuessList
    {
      public SingleRange(int start, int end)
      {
        Start = start;
        End = end;
      }

      int Start { get; }
      int End { get; }

      public int Count => 1 + End - Start;

      public int this[int index] => (index >= 0 && index <= End - Start) ? Start + index : throw new IndexOutOfRangeException();

      public IValidGuessList GetBefore(int index)
      {
        if (index <= 0)
          return EmptyRange.Instance;
        if (index >= Count)
          return this;
        return new SingleRange(Start, Start + index - 1);
      }

      public IValidGuessList GetAfter(int index)
      {
        if (index >= End - Start)
          return EmptyRange.Instance;
        if (index < 0)
          return this;
        return new SingleRange(Start + index + 1, End);
      }


      public IEnumerator<int> GetEnumerator() => Enumerable.Range(Start, Count).GetEnumerator();

      IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
    }

    public class JoinedRange : IValidGuessList
    {
      public JoinedRange(IValidGuessList first, IValidGuessList second)
      {
        First = first;
        Second = second;
        Count = first.Count + second.Count;
      }

      IValidGuessList First { get; }
      IValidGuessList Second { get; }

      public int Count { get; }

      public int this[int index] => index < First.Count ? First[index] : Second[index - First.Count];
      public IValidGuessList GetBefore(int index)
      {
        if (index <= First.Count)
          return First.GetBefore(index);
        else if (index >= Count)
          return this;
        return new JoinedRange(First, Second.GetBefore(index - First.Count));
      }

      public IValidGuessList GetAfter(int index)
      {
        if (index >= First.Count - 1)
          return Second.GetAfter(index - First.Count);
        if (index < 0)
          return this;
        return new JoinedRange(First.GetAfter(index), Second);
      }

      public IEnumerator<int> GetEnumerator() => First.Concat(Second).GetEnumerator();
      IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
    }


    public struct WorstCase
    {
      public static WorstCase CombineSubTrees(WorstCase left, WorstCase right)
      {
        return new WorstCase
        {
          MinDepth = Math.Min(left.MinDepth, right.MinDepth) + 1,
          MaxDepth = Math.Max(left.MaxDepth, right.MaxDepth) + 1,
          TreeCount = left.TreeCount + right.TreeCount + 1,
        };
      }
      public WorstCase AddLevel()
      {
        return new WorstCase { MinDepth = MinDepth + 1, MaxDepth = MaxDepth + 1, TreeCount = TreeCount + 1 };
      }
      internal int MinDepth { get; private set; }
      internal int MaxDepth { get; private set; }
      internal Int64 TreeCount { get; private set; }

      internal static WorstCase Leaf1 = new WorstCase() { TreeCount = 1 };
      internal static WorstCase Leaf2 = new WorstCase() { MaxDepth = 1, TreeCount = 2 };

    }


    static Dictionary<int, WorstCase> allTrueResultsDiary = new Dictionary<int, WorstCase>();

    static Dictionary<int, Dictionary<int, WorstCase>> resultsDiary = new Dictionary<int, Dictionary<int, WorstCase>>();


    public static WorstCase CheckState(IValidGuessList lowerList, IValidGuessList higherList, bool saidHigher, int depth)
    {
      int lowerCount = lowerList.Count();
      int higherCount = higherList.Count();

      if (lowerCount + higherCount < 3)

      // deal with leaf cases - no better strategy than to guess each remaining number.
      switch(lowerCount + higherCount)
      {
        case 0: throw new Exception("Alice CHEATED!  (or maybe there's a bug in my program...)");
        case 1: return WorstCase.Leaf1;
//        case 2: return WorstCase.Leaf2;
      }

      // special case "leaf" nodes dealt with...

      var trueList = saidHigher ? higherList : lowerList;
      var falseList = saidHigher ? lowerList : higherList;
      var trueCount = saidHigher ? higherCount : lowerCount;
      var falseCount = saidHigher ? lowerCount : higherCount;

      WorstCase result;

      // although we do the checks based on actual lists of numbers,
      // the result only depends on the counts of these,
      // so we can diarise the result, and avoid another recursive search
      // the next time we're called with equivalent parameters.

      if (resultsDiary.TryGetValue(trueCount, out var resultDict))
      {
        if (resultDict.TryGetValue(falseCount, out result))
          return result;
      }
      else
        resultsDiary.Add(trueCount, resultDict = new Dictionary<int, WorstCase>());


      WorstCase higherResult, lowerResult;

      if (falseCount == 0)
      {
        // nothing can be eliminated this turn.
        // just guess the median value, and process the results for all values except the one guessed.

        int guessIndex = (lowerCount + higherCount) / 2;
        var lowerThanGuess = trueList.GetBefore(guessIndex);
        var higherThanGuess = trueList.GetAfter(guessIndex);

        higherResult = CheckState(lowerThanGuess, higherThanGuess, true, depth + 1);
        lowerResult = CheckState(lowerThanGuess, higherThanGuess, false, depth + 1);

        result = WorstCase.CombineSubTrees(lowerResult, higherResult);
        resultDict.Add(falseCount, result);
        return result;
      }
      else if (falseCount + trueCount == 3 && trueCount > 0)
      {
        // guess the middle number (even if it would be in trueList)
        var lowerThanGuess = lowerList.GetBefore(1);
        var higherThanGuess = higherList.GetAfter(higherList.Count - 2);

        higherResult = CheckState(saidHigher ? EmptyRange.Instance : lowerThanGuess, higherThanGuess, true, depth + 1);
        lowerResult = CheckState(lowerThanGuess, saidHigher ? higherThanGuess : EmptyRange.Instance, false, depth + 1);
      }
      else if (falseCount < trueCount - 1)
        throw new Exception($"I think we've got some dodgy guesswork here! {falseCount}<{trueCount}");
      else
      {
        int doubleFalseCount = (int)(trueCount*0.191 + falseCount*0.5);
        if (doubleFalseCount >= falseCount)
          throw new Exception("I can't guess the number I want!");

        int initialGuess = saidHigher ? doubleFalseCount : (falseCount - doubleFalseCount - 1);
        int nextGuess = initialGuess;
        int guessIndex;

        int prevGuess = -1;
        WorstCase? initialResult = null;
        WorstCase? prevResult = null;

        while (true)
        {
          guessIndex = nextGuess;
          var lowerThanGuess = falseList.GetBefore(guessIndex);
          var higherThanGuess = falseList.GetAfter(guessIndex);

          if (saidHigher)
          {
            // said higher last time, so if said higher again, lowerThanGuess is eliminated as a double-false
            higherResult = CheckState(EmptyRange.Instance, new JoinedRange(higherThanGuess, trueList), true, depth + 1);

            // if said lower, values between the two guesses are eliminated.
            lowerResult = CheckState(lowerThanGuess, trueList, false, depth + 1);
          }
          else
          {
            // if said higher, values between the two guesses are eliminated.
            higherResult = CheckState(trueList, higherThanGuess, true, depth + 1);

            // said lower last time, so if said lower again, lowerThanGuess is eliminated as a double-false
            lowerResult = CheckState(new JoinedRange(trueList, lowerThanGuess), EmptyRange.Instance, false, depth + 1);
          }
          result = WorstCase.CombineSubTrees(lowerResult, higherResult);
          if (lowerResult.MaxDepth == higherResult.MaxDepth)
            break;
          else if (lowerResult.MaxDepth > higherResult.MaxDepth)
          {
            nextGuess = guessIndex - 1;
            if (nextGuess < 1)
              break;
          }
          else
          {
            nextGuess = guessIndex + 1;
            if (nextGuess >= falseCount)
              break;
          }
          if (nextGuess == prevGuess)
          {
            if (prevResult?.MaxDepth <= result.MaxDepth)
            {
              result = prevResult.Value;
              guessIndex = prevGuess;
            }
            break;
          }
          prevGuess = guessIndex;
          prevResult = result;
          if (guessIndex == initialGuess)
            initialResult = result;
          break; // << remove this line to search for better solutions.
        }
        if(initialResult?.MaxDepth <= result.MaxDepth)
        {
          result = initialResult.Value;
        }
        else if ((guessIndex > initialGuess + 1 || guessIndex < initialGuess - 1) && saidHigher)
          Console.WriteLine($"{trueCount},{falseCount} => adjust {initialGuess} to {guessIndex}, improved MaxDepth {initialResult?.MaxDepth} to {result.MaxDepth}");
        resultDict.Add(falseCount, result);
        return result;
      }
      result = WorstCase.CombineSubTrees(lowerResult, higherResult);
      resultDict.Add(falseCount, result);
      return result;
    }


    static public void Main()
    {
      int step = 1;
      // can change loop to search for more values of n (but taking longer to reach higher values of n)
//      for(int i=1;i<= 10000000;i+=step)
      foreach(int i in new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000, 100000, 1000000, 10000000, 100000000, 1000000000 })
      {
        var result = CheckState(new SingleRange(1, i), EmptyRange.Instance, false, 1);
        //        var result = CheckState(Enumerable.Range(1, i), Enumerable.Empty<int>(), false, 1);
        if (i.ToString().ToCharArray().Skip(2).All(c => c == '0'))
        {
          Console.WriteLine($"Result for {i} items: MinDepth:{result.MinDepth}, MaxDepth:{result.MaxDepth}, TreeCount:{result.TreeCount}");
          if (step <= i / 1000)
            step *= 10;
        }
      }
    }
  }
}