ysnt.cs

using System;
using System.Collections.Generic;
using System.Text;
using System.Threading.Tasks;
using System.Linq;

/// <summary>
/// Program used when writing my answer at
/// https://puzzling.stackexchange.com/questions/130857/you-see-no-three/130869#130869
/// Made available by the author of that answer under the same licensing terms as the answer itself, or under MIT-0 licence as you prefer.
///
/// The program as presented below outputs a "table" of win conditions for each player, as used in the strategy part of the answer,
/// which is truncated due to an OutOfMemoryException.
/// However, modifications to the "Main" function and/or uncommenting some of the Console.WriteLine lines will easily allow other kinds of investigations.
///
/// There are likely many further optimisations that can be done, in particular replacing the class structure with lightweight objects having a better
/// internal representation of the MultiGameState, earlier detection of states that are equivalent to each other, etc.
/// It's also certainly possible to use maths to further simplify the search tree...
/// </summary>

namespace Program
{
  public class YouSeeNoThree
  {
    public enum Players : byte
    {
      Bear,
      Rabbit,
    }

    public enum Colours : byte
    {
      Blue,
      Red,
      Mixed,
    }

    public struct WhiteRun : IEquatable<WhiteRun>
    {
      public int runLength;
      public Colours endColour;

      // IsDegenerate => nobody can ever play there
      public bool IsDegenerate => runLength < 2 || runLength == 2 && endColour == Colours.Mixed;

      public override string ToString() => $"{endColour}{runLength}";

      public override int GetHashCode() => endColour.GetHashCode() + runLength * 3;
      public override bool Equals(object obj) => obj is WhiteRun other && Equals(other);
      public bool Equals(WhiteRun other) => this.runLength == other.runLength && this.endColour == other.endColour;
    }

    public abstract class GameState : IEquatable<GameState>
    {
      protected GameState(Players nextPlayer)
      {
        NextPlayer = nextPlayer;
      }
      public Players NextPlayer { get; }
      public abstract IEnumerable<WhiteRun> Runs { get; }

      public abstract IEnumerable<GameState> EnumerateNextStates();

      public abstract override string ToString();

      public static GameState Create(Players nextPlayer, params WhiteRun[] runs)
      {
        switch (runs.Length)
        {
          case 0: return LostGameState.GetLostState(nextPlayer);
          case 1: return new SimpleGameState(nextPlayer, runs[0]);
          default: return new MultiGameState(nextPlayer, runs);
        }
      }

      public abstract override int GetHashCode();
      public abstract bool Equals(GameState other);
      public override bool Equals(object obj) => obj is GameState other && Equals(other);
    }

    public class LostGameState : GameState
    {
      private LostGameState(Players nextPlayer)
        : base(nextPlayer)
      { }

      private static Dictionary<Players, LostGameState> LostGameStates { get; } = new Dictionary<Players, LostGameState>
      {
        { Players.Bear, new LostGameState(Players.Bear)},
        { Players.Rabbit, new LostGameState(Players.Rabbit)},
      };

      public static LostGameState GetLostState(Players nextPlayer) => LostGameStates[nextPlayer];

      public override IEnumerable<WhiteRun> Runs => Enumerable.Empty<WhiteRun>();

      public override IEnumerable<GameState> EnumerateNextStates() => Enumerable.Empty<GameState>();

      public override string ToString() => $"{NextPlayer} lost the game.";

      public override bool Equals(GameState other) => other is LostGameState && NextPlayer == other.NextPlayer;
      public override int GetHashCode() => NextPlayer.GetHashCode();
    }

    public class SimpleGameState : GameState
    {
      public SimpleGameState(Players nextPlayer, byte runLength, Colours endColour)
        : this(nextPlayer, new WhiteRun { runLength = runLength, endColour = endColour })
      { }
      public SimpleGameState(Players nextPlayer, WhiteRun run)
        : base(nextPlayer)
      {
        singleRun = run;
      }

      public readonly WhiteRun singleRun;
      override public IEnumerable<WhiteRun> Runs => new[] { singleRun };

      public override IEnumerable<GameState> EnumerateNextStates()
      {
        if (singleRun.runLength < 2)
          throw new InvalidOperationException();

        var opponent = GetOpponent(NextPlayer);
        Colours playerColour = GetColour(NextPlayer);
        int minPlayPosition = singleRun.endColour == playerColour ? 1 : 0;
        int maxPlayPosition = singleRun.endColour == Colours.Mixed ? singleRun.runLength - 3 : (singleRun.runLength / 2 - 1);

        Colours beforeColour = singleRun.endColour == playerColour ? playerColour : Colours.Mixed;
        Colours afterColour = singleRun.endColour == Colours.Mixed ? playerColour : beforeColour;

        for (int playPosition = minPlayPosition; playPosition <= maxPlayPosition; playPosition++)
        {
          int runLengthBefore = playPosition;
          int runLengthAfter = singleRun.runLength - 2 - runLengthBefore;

          var runAfter = new WhiteRun { runLength = runLengthAfter, endColour = afterColour };
          var runBefore = new WhiteRun { runLength = runLengthBefore, endColour = beforeColour };

          if (runBefore.IsDegenerate)
          {
            if (runAfter.IsDegenerate)
              yield return GameState.Create(opponent);
            else
              yield return GameState.Create(opponent, runAfter);
          }
          else if (runAfter.IsDegenerate)
            yield return GameState.Create(opponent, runBefore);
          else
          {
            // invariant to have canonical ordering - longest run goes first, with colour as tie-break.
            if (runLengthAfter < runLengthBefore || runLengthAfter == runLengthBefore && afterColour < beforeColour)
              yield return GameState.Create(opponent, runBefore, runAfter);
            else
              yield return GameState.Create(opponent, runAfter, runBefore);
          }
        }
      }

      public override string ToString() => $"{NextPlayer} to play, {singleRun}";

      public override bool Equals(GameState other) => other is SimpleGameState otherSimple && NextPlayer == other.NextPlayer && singleRun.Equals(otherSimple.singleRun);
      public override int GetHashCode() => NextPlayer.GetHashCode() + singleRun.GetHashCode() * 2;
    }

    public class MultiGameState : GameState
    {
      public MultiGameState(Players nextPlayer, params WhiteRun[] runs)
        : base(nextPlayer)
      {
        this.runs = runs;
        if (runs.Length < 2)
          throw new ArgumentOutOfRangeException();
      }
      public readonly WhiteRun[] runs;
      override public IEnumerable<WhiteRun> Runs => runs;

      public override IEnumerable<GameState> EnumerateNextStates()
      {
        // make a valid move on each of the runs in turn...
        for (int runIndex = 0; runIndex < runs.Length; runIndex++)
        {
          // all runs except the one we are making a move on are unaltered...
          List<WhiteRun> runsAfterMove = runs.Where((_, i) => i != runIndex).ToList();
          foreach(var nextStateFromSimple in new SimpleGameState(NextPlayer, runs[runIndex]).EnumerateNextStates())
          {
            // and we then merge the runs list, preserving the invariant ordering.
            var combinedRunsAfterMove = runsAfterMove.Concat(nextStateFromSimple.Runs).Where(r => !r.IsDegenerate).OrderByDescending(r => r.runLength).ThenByDescending(r => r.endColour).ToArray();
            yield return GameState.Create(nextStateFromSimple.NextPlayer, combinedRunsAfterMove);
          }
        }
      }

      public override string ToString() => $"{NextPlayer} to play, {string.Join(", ", runs)}";
      public override bool Equals(GameState other) => other is MultiGameState otherMulti && NextPlayer == other.NextPlayer && runs.SequenceEqual(otherMulti.runs);
      public override int GetHashCode()
      {
        int subtotal = 0;
        for (int i = 0; i < runs.Length; i++)
        {
          subtotal *= 257;
          subtotal += runs[i].GetHashCode();
        }
        return NextPlayer.GetHashCode() + subtotal * 2;
      }
    }


    public static Players GetOpponent(Players player)
    {
      switch (player)
      {
        case Players.Bear: return Players.Rabbit;
        case Players.Rabbit: return Players.Bear;
        default: throw new ArgumentOutOfRangeException();
      }
    }

    public static Colours GetColour(Players player)
    {
      switch (player)
      {
        case Players.Bear: return Colours.Blue;
        case Players.Rabbit: return Colours.Red;
        default: throw new ArgumentOutOfRangeException();
      }
    }

    static Dictionary<GameState, LostGameState> knownOutcomes = new Dictionary<GameState, LostGameState>();

    static LostGameState GetOutcomeFromState(GameState state, string indent = "")
    {
//      Console.WriteLine($"{indent}Checking outcome from: {state}");
      if (knownOutcomes.TryGetValue(state, out var result))
      {
  //      Console.WriteLine($"{indent}Cached result: {result}");
        return result;
      }

      if (state is LostGameState lostState)
        result = lostState;
      else if (state is SimpleGameState simpleState && simpleState.singleRun.runLength < 5)
      {
        switch (simpleState.singleRun.runLength)
        {
          case 0:
          case 1:
            // degenerate game states where there is no possible move
            result = LostGameState.GetLostState(state.NextPlayer);
            break;
          case 2:
            // with 2 white beads, at most one player can play in this state, if they have non-matching colour for both ends.
            switch (simpleState.singleRun.endColour)
            {
              case Colours.Blue: result = LostGameState.GetLostState(Players.Bear); break;
              case Colours.Red: result = LostGameState.GetLostState(Players.Rabbit); break;
              case Colours.Mixed: result = LostGameState.GetLostState(state.NextPlayer); break;
              default: throw new InvalidOperationException();
            }
            break;
          case 3:
            // with 3 white beads, at least one player can play in this state, if they have non-matching colour for one end.
            switch (simpleState.singleRun.endColour)
            {
              case Colours.Blue: result = LostGameState.GetLostState(Players.Bear); break;
              case Colours.Red: result = LostGameState.GetLostState(Players.Rabbit); break;
              case Colours.Mixed: result = LostGameState.GetLostState(GetOpponent(state.NextPlayer)); break;
              default: throw new InvalidOperationException();
            }
            break;
          case 4:
            // with 4 white beads, a valid "losing" move may exist, but we don't play that.
            // opponent loses, as nextPlayer makes the obvious winning move.
            result = LostGameState.GetLostState(GetOpponent(state.NextPlayer));
            break;

          default:
            throw new InvalidOperationException();
        }
      }
      else
        result = GenerateUnknownOutcome(state, indent + " ");

     // Console.WriteLine($"{indent}Storing outcome: {result}");
      knownOutcomes.Add(state, result);
      return result;
    }

    static LostGameState GenerateUnknownOutcome(GameState state, string indent = "")
    {
      // unless we have at least one winning move, the state is lost.
      var result = LostGameState.GetLostState(state.NextPlayer);

      foreach(var nextState in state.EnumerateNextStates())
      {
//        Console.WriteLine($"{indent}Investigating state: {nextState}");
        var nextResult = GetOutcomeFromState(nextState, indent);
        if (nextResult != result)
        {
  //        Console.WriteLine($"{indent}Winning move found!");
          return nextResult;
        }
      }
      return result;
    }

    public static int Main()
    {
      var availableColours = new[] { Colours.Blue, Colours.Red, Colours.Mixed };
      var availablePlayers = new[] { Players.Rabbit, Players.Bear };
      int testIndex = 0;
      Console.Write("RunLength");
      foreach (var player in availablePlayers)
        foreach (var endColour in availableColours)
          Console.Write($"\t{player}:{endColour}");
      Console.WriteLine();
      for (byte count = 0; count <= 99; count++)
      {
        var winners = new List<Players>();
        foreach (var player in availablePlayers)
        {
          foreach (var endColour in availableColours)
          {
            var startState = GameState.Create(player, new WhiteRun { runLength = count, endColour = endColour });
            var result = GetOutcomeFromState(startState, $"[test{testIndex++}] ");
            //Console.WriteLine($"Result from [{startState}]: {result}");
            winners.Add(GetOpponent(result.NextPlayer));
          }
        }
        Console.WriteLine($"{count}\t{string.Join("\t", winners)}");
      }

      return 0;
    }
  }
}