SquareSwap4NoPath96.cs

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

// SquareSwap4NoPath96.cs
// used for a breadth-first exhaustive search for an answer at
// https://puzzling.stackexchange.com/questions/111932/can-you-reactivate-a-4x4-magic-square
// still "a work in progress" so not very tidied up...


using IntCode = System.UInt64;

public struct CellState : IEquatable<CellState>
{
  public byte Value { get; set; }
  public byte MovesLeft { get; set; }

  public override bool Equals(object obj)
  {
    return obj is CellState other && Equals(other);
  }

  public bool Equals(CellState other)
  {
    return Value == other.Value && MovesLeft == other.MovesLeft;
  }

  public override int GetHashCode()
  {
    return Value * 256 + MovesLeft;
  }

  public bool IsSwapValid(CellState other)
  {
    if (Value > other.Value)
      return MovesLeft >= other.Value && other.MovesLeft > 0;
    else
      return other.MovesLeft >= Value && MovesLeft > 0;
  }
}





public class GridState : IEquatable<GridState>
{
  private static CellState[] MakeCellStates(params string[] initialRows)
  {
    int columnCount = initialRows[0].Length;
    var result = new CellState[initialRows.Length * columnCount];
    for (int row = 0; row < initialRows.Length; row++)
    {
      if (initialRows[row].Length != columnCount)
        throw new ArgumentException("All rows must be the same length", nameof(initialRows));
      for (int col = 0; col < columnCount; col++)
      {
        int value = _mainNumbers.IndexOf(initialRows[row][col]);
        if (value < 0)
          throw new ArgumentException("Row contained invalid character: " + initialRows[row]);

        result[row * columnCount + col] = new CellState { Value = (byte)value, MovesLeft = (byte)value };
      }
    }
    return result;
  }

  public GridState(params string[] initialRows)
    : this(initialRows[0].Length, MakeCellStates(initialRows))
  { }

  public GridState(int columnCount, CellState[] cellStates)
  {
    if (cellStates.Length % columnCount != 0)
      throw new ArgumentOutOfRangeException();
    ColumnCount = columnCount;
    CellStates = cellStates;
  }

  public int SetMagicConstant()
  {
    MagicConstant = 0;
    if (RowCount == ColumnCount)
    {
      int totalValues = CellStates.Sum(c => (int)c.Value);
      if (totalValues % ColumnCount == 0)
        MagicConstant = totalValues / ColumnCount;
    }
    return MagicConstant;
  }

  public int ColumnCount { get; }
  public int RowCount => CellStates.Length / ColumnCount;

  private static int MagicConstant { get; set; }

  public CellState[] CellStates { get; }

  public CellState this[int row, int col]
  {
    get
    {
      if (row < 0 || row > RowCount)
        throw new ArgumentOutOfRangeException(nameof(row));
      if (col < 0 || col > ColumnCount)
        throw new ArgumentOutOfRangeException(nameof(col));
      return CellStates[row * ColumnCount + col];
    }
  }

  private static readonly string _mainNumbers = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ#";
  private static readonly string _subscriptNumbers = "₀₁₂₃₄₅₆₇₈₉₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊";

  public override string ToString()
  {
    int rowLength = ColumnCount * 5;

    StringBuilder result = new StringBuilder(rowLength * RowCount * 2);

    for (int row = 0; row < RowCount; row++)
    {
      for (int col = 0; col < ColumnCount; col++)
      {
        var state = CellStates[row * ColumnCount + col];
        result.Append(new[] { ' ', _mainNumbers[state.Value], _subscriptNumbers[state.MovesLeft], ' ', col < ColumnCount - 1 ? '|' : '\n' });
      }
      if (row < RowCount - 1)
      {
        result.Append(string.Join("+", Enumerable.Repeat("----", ColumnCount)));
        result.Append("\n");
      }
    }
    return result.ToString();
  }

  public override bool Equals(object obj)
  {
    return base.Equals(obj) || obj is GridState other && Equals(other);
  }

  public bool Equals(GridState other)
  {
    var otherCellStates = other.CellStates;
    if (otherCellStates.Length != CellStates.Length)
      return false;
    for (int i = 0; i < CellStates.Length; i++)
      if (!CellStates[i].Equals(otherCellStates[i]))
        return false;
    return true;
  }

  public bool EqualValues(GridState other)
  {
    var otherCellStates = other.CellStates;
    if (otherCellStates.Length != CellStates.Length)
      return false;
    for (int i = 0; i < CellStates.Length; i++)
      if (!CellStates[i].Value.Equals(otherCellStates[i].Value))
        return false;
    return true;
  }

  public override int GetHashCode()
  {
    int result = 0;
    for (int i = 0; i < CellStates.Length; i++)
      result = (result >> 18) ^ (result * 0x1413 + CellStates[i].GetHashCode());
    return result;
  }

  public int TotalMovesLeft => CellStates.Sum(c => c.MovesLeft);

  public GridState GetStateAfterSwap(SwapInfo swapInfo)
  {
    CellState stateFrom = this[swapInfo.rowFrom, swapInfo.colFrom];
    CellState stateTo = this[swapInfo.rowTo, swapInfo.colTo];

    if (!stateFrom.IsSwapValid(stateTo))
      throw new ArgumentOutOfRangeException(nameof(swapInfo), $"Invalid swap R{swapInfo.rowFrom + 1}C{swapInfo.colFrom + 1} with R{swapInfo.rowTo + 1}C{swapInfo.colTo + 1} for grid:\n{this.ToString()}");

    var cellStatesAfter = CellStates.ToArray();

    CellState stateFromAfter = new CellState { Value = (byte)stateTo.Value, MovesLeft = (byte)(stateTo.MovesLeft - (stateTo.Value > stateFrom.Value ? stateFrom.Value : 1)) };
    CellState stateToAfter = new CellState { Value = (byte)stateFrom.Value, MovesLeft = (byte)(stateFrom.MovesLeft - (stateFrom.Value > stateTo.Value ? stateTo.Value : 1)) };

    cellStatesAfter[swapInfo.rowFrom * ColumnCount + swapInfo.colFrom] = stateFromAfter;
    cellStatesAfter[swapInfo.rowTo * ColumnCount + swapInfo.colTo] = stateToAfter;

    return new GridState(ColumnCount, cellStatesAfter);
  }

  public bool IsSwapValid(SwapInfo info) => this[info.rowFrom, info.colFrom].IsSwapValid(this[info.rowTo, info.colTo]);

  public bool IsOrdered()
  {
    for (int i = 0; i < CellStates.Length - 1; i++)
      if (CellStates[i].Value > CellStates[i + 1].Value)
        return false;
    return true;
  }

  public bool IsMagic()
  {
    if (MagicConstant == 0)
      throw new InvalidOperationException("Cannot be magic - wrong dimensions or total...");
    int count = ColumnCount;
    return Enumerable.Range(0, count).Sum(i => (int)this[i, i].Value) == MagicConstant &&
           Enumerable.Range(0, count).Sum(i => (int)this[count - 1 - i, i].Value) == MagicConstant &&
           Enumerable.Range(0, count).All(i => Enumerable.Range(0, count).Sum(col => (int)this[i, col].Value) == MagicConstant &&
                                               Enumerable.Range(0, count).Sum(row => (int)this[row, i].Value) == MagicConstant);
  }
}


public struct SwapInfo : IEquatable<SwapInfo>
{
  public byte rowFrom { get; set; }
  public byte colFrom { get; set; }
  public byte rowTo { get; set; }
  public byte colTo { get; set; }

  static Dictionary<SwapInfo, byte> _toByteDict = new Dictionary<SwapInfo, byte>(256);
  static List<SwapInfo> _knownValidSwaps = new List<SwapInfo>(256); // only because dict isn't indexable...
  static System.Threading.ReaderWriterLockSlim _byteDictLock = new System.Threading.ReaderWriterLockSlim();

  public byte CompressToByte()
  {
    if (!_toByteDict.TryGetValue(this, out byte result))
    {
      // Attention - this is a potential major bug if the same pattern used anywhere else... Dictionary is not thread safe.
      // However, we avoid hash bucket re-organisation by pre-allocating 256 entries (enough for anything which can be converted to/from byte)
      // and in this specific case, the lock isn't even needed because we're really doing all writing from the single thread that
      // handles finding swaps from the starting position, but kept lock because
      // later tweaks to the program might potentially make the lock necessary...
      // the alternatives of concurrentdictionary or readerwriterlockslim would add more overhead for many millions of calls.
      lock (_toByteDict)
        if (!_toByteDict.TryGetValue(this, out result))
        {
          if (_toByteDict.Count > 255)
            throw new InvalidOperationException("_toByteDict is full. refactoring required!");
          result = (byte)_toByteDict.Count;
          Console.WriteLine($"Allocated byte {result} to swap {this}");
          _toByteDict.Add(this, result);
          _knownValidSwaps.Add(this);
        }
    }
    return result;
  }

  public static SwapInfo ExpandFromByte(byte compressed)
  {
    return _knownValidSwaps[compressed];
  }


  public override bool Equals(object obj)
  {
    return obj is SwapInfo other && Equals(other);
  }

  public bool Equals(SwapInfo other)
  {
    return rowFrom == other.rowFrom && colFrom == other.colFrom && rowTo == other.rowTo && colTo == other.colTo ||
           rowFrom == other.rowTo && colFrom == other.colTo && rowTo == other.rowFrom && colTo == other.colFrom;
  }

  public override int GetHashCode()
  {
    return Math.Min(rowFrom, rowTo) + Math.Max(rowFrom, rowTo) * 64 + Math.Min(colFrom, colTo) * 4096 + Math.Max(colFrom, colTo) * 262144;
  }

  public override string ToString()
  {
    return $"R{rowFrom + 1}C{colFrom + 1}<>R{rowTo + 1}C{colTo + 1}";
  }
}


public class PuzzleState
{
  public PuzzleState(GridState gridState, params SwapInfo[] movesDone)
  {
    GridState = gridState;
    MovesDone = movesDone;
  }

  public GridState GridState { get; private set; }

  public PuzzleState(params string[] lines)
    : this(new GridState(lines))
  {
  }

  // parent and move count were never used, so removed these.

  public SwapInfo[] MovesDone { get; }

  private static SwapInfo[] ConcatSwapInfo(PuzzleState parent, SwapInfo move)
  {
    int parentLength = parent.MovesDone.Length;
    var result = new SwapInfo[parentLength + 1];
    Array.Copy(parent.MovesDone, result, parentLength);
    result[parentLength] = move;
    return result;
  }

  private PuzzleState(PuzzleState parent, SwapInfo move, GridState gridState)
    : this(gridState, ConcatSwapInfo(parent, move))
  {
    // bug in previous version before major refactoring left out this (now redundant!) line
    AllowWrapAround = parent.AllowWrapAround;
  }

  public bool IsSwapValid(SwapInfo info) => GridState.IsSwapValid(info);

  public bool AllowWrapAround { get; set; } = true;

  public IEnumerable<PuzzleState> GetStatesAfterValidMoves()
  {
    int fromRowLimit = AllowWrapAround ? GridState.RowCount : (GridState.RowCount - 1);
    int fromColLimit = AllowWrapAround ? GridState.ColumnCount : (GridState.ColumnCount - 1);
    for (int fromRow = 0; fromRow < fromRowLimit; fromRow++)
    {
      int toNextRow = (fromRow + 1) % GridState.RowCount;
      for (int fromCol = 0; fromCol < GridState.ColumnCount; fromCol++)
      {
        CellState fromState = GridState[fromRow, fromCol];
        if (fromState.MovesLeft < 1)
          continue;

        CellState toState = GridState[toNextRow, fromCol];
        if (fromState.IsSwapValid(toState))
        {
          var swapInfo = new SwapInfo { colFrom = (byte)fromCol, rowFrom = (byte)fromRow, colTo = (byte)fromCol, rowTo = (byte)toNextRow };
          yield return new PuzzleState(this, swapInfo, GridState.GetStateAfterSwap(swapInfo));
        }
      }
    }
    for (int fromCol = 0; fromCol < fromColLimit; fromCol++)
    {
      int toNextCol = (fromCol + 1) % GridState.ColumnCount;
      for (int fromRow = 0; fromRow < GridState.RowCount; fromRow++)
      {
        CellState fromState = GridState[fromRow, fromCol];
        if (fromState.MovesLeft < 1)
          continue;

        CellState toState = GridState[fromRow, toNextCol];
        if (fromState.IsSwapValid(toState))
        {
          var swapInfo = new SwapInfo { colFrom = (byte)fromCol, rowFrom = (byte)fromRow, colTo = (byte)toNextCol, rowTo = (byte)fromRow };
          yield return new PuzzleState(this, swapInfo, GridState.GetStateAfterSwap(swapInfo));
        }
      }
    }
  }

  //  static GridState targetState = new GridState("123", "456", "789");

  public bool IsTargetState => GridState.IsMagic();

  public IEnumerable<SwapInfo> GetSwaps()
  {
    return MovesDone;
  }
}

public struct CompressedGridState4 : IEquatable<CompressedGridState4>
{
  public static implicit operator CompressedGridState4(GridState source) => new CompressedGridState4(source);
  public static implicit operator GridState(CompressedGridState4 source) => source.GetGridState();

  // now further compressed to 96 bits (was 128) to allow more space before reaching memory limit for hash tables.
  UInt32 _compressedData1low;
  UInt32 _compressedData2low;
  UInt32 _compressedDataHigh;

  static int[] _possiblePositionsInit = Enumerable.Range(0, 16).ToArray();

  public CompressedGridState4(GridState source)
  {
    if (source.ColumnCount != 4 || source.CellStates.Length != 16)
      throw new InvalidOperationException("This compression function assumes a 4 x 4 grid containing precisely the numbers 1-16");

    var cellStates = source.CellStates;
    UInt64 multiplier1 = 1;
    UInt64 multiplier2 = 1;
    UInt64 _compressedData1 = 0;
    UInt64 _compressedData2 = 0;

    List<int> possiblePositions = _possiblePositionsInit.ToList();

    for (uint i = 1; i <= 16; i++)
    {
      // find index of value i
      int pos = 0;
      while (cellStates[pos].Value != i)
      {
        if (pos >= cellStates.Length - 1)
          throw new InvalidOperationException($"Value {i} not found in grid state");
        else
          pos++;
      }
      int posIndex = possiblePositions.IndexOf(pos);
      if (posIndex == -1)
        throw new InvalidOperationException($"Value {i} found at position {pos} which isn't possible! Possible: [{string.Join(",", possiblePositions)}]");

      _compressedData1 += multiplier1 * (uint)posIndex;
      multiplier1 *= (uint)possiblePositions.Count;

      possiblePositions.RemoveAt(posIndex);

      _compressedData2 += multiplier2 * (uint)cellStates[pos].MovesLeft;
      multiplier2 *= i + 1;

      //Console.WriteLine($"Compression diagnostic: i={i}, pos={pos} index {posIndex}, moves = {cellStates[pos].MovesLeft}, multiplier = {multiplier}, data = {_compressedData}");
    }
    // result was stored in 2 x 64 bits (128 bits total), but fits within 96 bits...
    _compressedData1low = (uint)_compressedData1;
    _compressedData2low = (uint)_compressedData2;
    _compressedDataHigh = ((uint)(_compressedData1 >> 32)) | (8192 * (uint)(_compressedData2 >> 32));
  }

  public GridState GetGridState()
  {
    var cellStates = new CellState[16];
    UInt64 multiplier1 = 1;
    UInt64 multiplier2 = 1;
    // first expand back to 2 x 64 bits for further computations...
    UInt64 _compressedData1 = _compressedData1low | ((UInt64)(_compressedDataHigh % 8192)) << 32;
    UInt64 _compressedData2 = _compressedData2low | ((UInt64)(_compressedDataHigh / 8192)) << 32;


    List<int> possiblePositions = Enumerable.Range(0, 16).ToList();

    for (byte i = 1; i <= 16; i++)
    {
      UInt64 nextMultiplier1 = multiplier1 * (uint)possiblePositions.Count;
      int posIndex = (int)(_compressedData1 % nextMultiplier1 / multiplier1);
      int pos = possiblePositions[posIndex];
      possiblePositions.RemoveAt(posIndex);

      multiplier1 = nextMultiplier1;

      UInt64 nextMultiplier2 = multiplier2 * ((uint)i + 1);
      byte movesLeft = (byte)(_compressedData2 % nextMultiplier2 / multiplier2);
      multiplier2 = nextMultiplier2;

      cellStates[pos] = new CellState { Value = i, MovesLeft = movesLeft };

      //Console.WriteLine($"Decompression diagnostic: i={i}, pos={pos} index {posIndex}, moves = {cellStates[pos].MovesLeft}, multiplier = {multiplier}, data = {_compressedData}");
    }

    return new GridState(4, cellStates);
  }

  public override bool Equals(object obj)
  {
    return obj is CompressedGridState4 other && Equals(other) || obj is GridState otherExpanded && GetGridState().Equals(otherExpanded);
  }

  public bool Equals(CompressedGridState4 other)
  {
    return _compressedDataHigh == other._compressedDataHigh && _compressedData2low == other._compressedData2low && _compressedData1low == other._compressedData1low;
  }

  public override int GetHashCode()
  {
    return _compressedData1low.GetHashCode() + _compressedData2low.GetHashCode() + _compressedDataHigh.GetHashCode();
  }

}


public class SquareSwap
{
  static public void Main()
  {
    Console.OutputEncoding = System.Text.Encoding.UTF8;

    var startingState = new PuzzleState("867G", "143A", "9D2E", "BC5F") { AllowWrapAround = false };

    //    var startingState = new PuzzleState("1FE4", "BA58", "G69C", "732D") { AllowWrapAround = false }; // test starting state similar to "given" magic square

    //    var startingState = new PuzzleState("1FE4", "AB85", "769C", "G32D") { AllowWrapAround = false }; // test starting state similar to "given" magic square


    var magicConstant = startingState.GridState.SetMagicConstant();

    Console.WriteLine($"Starting state [total moves left: {startingState.GridState.TotalMovesLeft}, magic constant = {magicConstant}]:");
    Console.WriteLine(startingState.GridState);

    // test case for compression and decompression functions.
    CompressedGridState4 comp = startingState.GridState;
    Console.WriteLine($"Equality check: {comp.Equals((object)startingState.GridState)}");

    var workingSets = Enumerable.Range(0, startingState.GridState.TotalMovesLeft + 1).Select(i => new HashSet<CompressedGridState4>()).ToArray();

    workingSets[startingState.GridState.TotalMovesLeft].Add(startingState.GridState);

    bool found = false;

    for (int i = workingSets.Length - 1; i > 0 /*&& !found*/; i--)
    {
      Console.WriteLine($"Starting on working set #{i}, which has {workingSets[i].Count} members... [{Enumerable.Range(0, i).Sum(x => workingSets[x].Count)} already in later working sets]");

      System.Threading.Tasks.Parallel.ForEach(workingSets[i], key =>
      {
        GridState gridState = key; // implicit conversion to decompress
        var puzzleState = new PuzzleState(gridState) { AllowWrapAround = false };
        // non-compressed puzzle state is now only scoped to this block.

        if (puzzleState.IsTargetState)
        {
          found = true;
          lock (workingSets[i])
          {
            Console.WriteLine("Found solution!");
            Console.WriteLine($"... after swaps: {string.Join(", ", puzzleState.GetSwaps())}");
            Console.WriteLine(puzzleState.GridState);
          }
        }
        else
          foreach (var nextState in puzzleState.GetStatesAfterValidMoves())
          {
            int movesLeft = nextState.GridState.TotalMovesLeft;
            //var swapInfo = nextState.MovesDone.Last();
            //Console.WriteLine($"Possible next state after swapping R{swapInfo.rowFrom + 1}C{swapInfo.colFrom + 1} with R{swapInfo.rowTo + 1}C{swapInfo.colTo + 1} [total moves left: {movesLeft}]:");
            //Console.WriteLine(nextState.GridState);

            if (movesLeft >= i)
              throw new InvalidOperationException("Total moves left didn't decrease???!");

            // implicit conversion to compressed data.
            CompressedGridState4 nextGridStateCompressed = nextState.GridState;

            lock (workingSets[movesLeft])
            {
              if (workingSets[movesLeft].TryGetValue(nextGridStateCompressed, out var firstEquivalentState))
              {
                // Console.WriteLine("Duplicate found!");
              }
              else
              {
                workingSets[movesLeft].Add(nextGridStateCompressed);
//                if (movesLeft == 131)
  //                Console.WriteLine("131 moves left:\n" + nextState.GridState);
              }
            }
          }
      });
      // allow dictionaries of compresed state to be reclaimed by garbage collector
      workingSets[i] = null;
    }
  }
}