Advertisement
Guest User

SquareSwap3.cs

a guest
Oct 1st, 2021
57
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Linq;
  3. using System.Text;
  4. using System.Collections.Generic;
  5.  
  6. // SquareSwap3.cs
  7. // used for a breadth-first exhaustive search for supplementary answer at
  8. // https://puzzling.stackexchange.com/questions/111900/remove-the-magic-from-a-3x3-magic-square
  9. // including some further optimisations intended to help towards the follow-on puzzle,
  10. // and still "a work in progress" so not very tidied up...
  11.  
  12.  
  13. public struct CellState : IEquatable<CellState>
  14. {
  15.   public byte Value { get; set; }
  16.   public byte MovesLeft { get; set; }
  17.  
  18.   public override bool Equals(object obj)
  19.   {
  20.     return obj is CellState other && Equals(other);
  21.   }
  22.  
  23.   public bool Equals(CellState other)
  24.   {
  25.     return Value == other.Value && MovesLeft == other.MovesLeft;
  26.   }
  27.  
  28.   public override int GetHashCode()
  29.   {
  30.     return Value * 256 + MovesLeft;
  31.   }
  32.  
  33.   public bool IsSwapValid(CellState other)
  34.   {
  35.     if (Value > other.Value)
  36.       return MovesLeft >= other.Value && other.MovesLeft > 0;
  37.     else
  38.       return other.MovesLeft >= Value && MovesLeft > 0;
  39.   }
  40. }
  41.  
  42.  
  43.  
  44.  
  45.  
  46. public class GridState : IEquatable<GridState>
  47. {
  48.   private static CellState[] MakeCellStates(params string[] initialRows)
  49.   {
  50.     int columnCount = initialRows[0].Length;
  51.     var result = new CellState[initialRows.Length * columnCount];
  52.     for (int row = 0; row < initialRows.Length; row++)
  53.     {
  54.       if (initialRows[row].Length != columnCount)
  55.         throw new ArgumentException("All rows must be the same length", nameof(initialRows));
  56.       for (int col = 0; col < columnCount; col++)
  57.       {
  58.         int value = _mainNumbers.IndexOf(initialRows[row][col]);
  59.         if (value < 0)
  60.           throw new ArgumentException("Row contained invalid character: " + initialRows[row]);
  61.  
  62.         result[row * columnCount + col] = new CellState { Value = (byte)value, MovesLeft = (byte)value };
  63.       }
  64.     }
  65.     return result;
  66.   }
  67.  
  68.   public GridState(params string[] initialRows)
  69.     : this(initialRows[0].Length, MakeCellStates(initialRows))
  70.   { }
  71.  
  72.   public GridState(int columnCount, CellState[] cellStates)
  73.   {
  74.     if (cellStates.Length % columnCount != 0)
  75.       throw new ArgumentOutOfRangeException();
  76.     ColumnCount = columnCount;
  77.     CellStates = cellStates;
  78.   }
  79.  
  80.   public int ColumnCount { get; }
  81.   public int RowCount => CellStates.Length / ColumnCount;
  82.  
  83.   public CellState[] CellStates { get; }
  84.  
  85.   public CellState this[int row, int col]
  86.   {
  87.     get
  88.     {
  89.       if (row < 0 || row > RowCount)
  90.         throw new ArgumentOutOfRangeException(nameof(row));
  91.       if (col < 0 || col > ColumnCount)
  92.         throw new ArgumentOutOfRangeException(nameof(col));
  93.       return CellStates[row * ColumnCount + col];
  94.     }
  95.   }
  96.  
  97.   private static readonly string _mainNumbers      = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ#";
  98.   private static readonly string _subscriptNumbers = "₀₁₂₃₄₅₆₇₈₉₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊";
  99.  
  100.   public override string ToString()
  101.   {
  102.     int rowLength = ColumnCount * 5;
  103.  
  104.     StringBuilder result = new StringBuilder(rowLength * RowCount * 2);
  105.  
  106.     for (int row = 0; row < RowCount; row++)
  107.     {
  108.       for (int col = 0; col < ColumnCount; col++)
  109.       {
  110.         var state = CellStates[row * ColumnCount + col];
  111.         result.Append(new[] { ' ', _mainNumbers[state.Value], _subscriptNumbers[state.MovesLeft], ' ', col < ColumnCount - 1 ? '|' : '\n' });
  112.       }
  113.       if (row < RowCount - 1)
  114.       {
  115.         result.Append(string.Join("+", Enumerable.Repeat("----", ColumnCount)));
  116.         result.Append("\n");
  117.       }
  118.     }
  119.     return result.ToString();
  120.   }
  121.  
  122.   public override bool Equals(object obj)
  123.   {
  124.     return base.Equals(obj) || obj is GridState other && Equals(other);
  125.   }
  126.  
  127.   public bool Equals(GridState other)
  128.   {
  129.     var otherCellStates = other.CellStates;
  130.     if (otherCellStates.Length != CellStates.Length)
  131.       return false;
  132.     for (int i = 0; i < CellStates.Length; i++)
  133.       if (!CellStates[i].Equals(otherCellStates[i]))
  134.         return false;
  135.     return true;
  136.   }
  137.  
  138.   public bool EqualValues(GridState other)
  139.   {
  140.     var otherCellStates = other.CellStates;
  141.     if (otherCellStates.Length != CellStates.Length)
  142.       return false;
  143.     for (int i = 0; i < CellStates.Length; i++)
  144.       if (!CellStates[i].Value.Equals(otherCellStates[i].Value))
  145.         return false;
  146.     return true;
  147.   }
  148.  
  149.   public override int GetHashCode()
  150.   {
  151.     int result = 0;
  152.     for (int i = 0; i < CellStates.Length; i++)
  153.       result = (result >> 18) ^ (result * 0x1413 + CellStates[i].GetHashCode());
  154.     return result;
  155.   }
  156.  
  157.   public int TotalMovesLeft => CellStates.Sum(c => c.MovesLeft);
  158.  
  159.   public GridState GetStateAfterSwap(SwapInfo swapInfo)
  160.   {
  161.     CellState stateFrom = this[swapInfo.rowFrom, swapInfo.colFrom];
  162.     CellState stateTo = this[swapInfo.rowTo, swapInfo.colTo];
  163.  
  164.     if (!stateFrom.IsSwapValid(stateTo))
  165.       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()}");
  166.  
  167.     var cellStatesAfter = CellStates.ToArray();
  168.  
  169.     CellState stateFromAfter = new CellState { Value = (byte)stateTo.Value, MovesLeft = (byte)(stateTo.MovesLeft - (stateTo.Value > stateFrom.Value ? stateFrom.Value : 1)) };
  170.     CellState stateToAfter = new CellState { Value = (byte)stateFrom.Value, MovesLeft = (byte)(stateFrom.MovesLeft - (stateFrom.Value > stateTo.Value ? stateTo.Value : 1)) };
  171.  
  172.     cellStatesAfter[swapInfo.rowFrom * ColumnCount + swapInfo.colFrom] = stateFromAfter;
  173.     cellStatesAfter[swapInfo.rowTo * ColumnCount + swapInfo.colTo] = stateToAfter;
  174.  
  175.     return new GridState(ColumnCount, cellStatesAfter);
  176.   }
  177.  
  178.   public bool IsSwapValid(SwapInfo info) => this[info.rowFrom, info.colFrom].IsSwapValid(this[info.rowTo, info.colTo]);
  179.  
  180.   public bool IsOrdered()
  181.   {
  182.     for (int i = 0; i < CellStates.Length - 1; i++)
  183.       if (CellStates[i].Value > CellStates[i + 1].Value)
  184.         return false;
  185.     return true;
  186.   }
  187.  
  188.   public bool IsMagic()
  189.   {
  190.     if (RowCount != ColumnCount)
  191.       return false;
  192.     int count = RowCount;
  193.     int firstDiagTotal = Enumerable.Range(0, count).Sum<int>(i => this[i, i].Value);
  194.     int secondDiagTotal = Enumerable.Range(0, count).Sum<int>(i => this[count - 1 - i, i].Value);
  195.     if (firstDiagTotal != secondDiagTotal)
  196.       return false;
  197.     return Enumerable.Range(0, count).All(i => Enumerable.Range(0, count).Sum<int>(col => this[i, col].Value) == firstDiagTotal &&
  198.                                                Enumerable.Range(0, count).Sum<int>(row => this[row, i].Value) == firstDiagTotal);
  199.   }
  200. }
  201.  
  202.  
  203. public struct SwapInfo : IEquatable<SwapInfo>
  204. {
  205.   public byte rowFrom { get; set; }
  206.   public byte colFrom { get; set; }
  207.   public byte rowTo { get; set; }
  208.   public byte colTo { get; set; }
  209.  
  210.   public override bool Equals(object obj)
  211.   {
  212.     return obj is SwapInfo other && Equals(other);
  213.   }
  214.  
  215.   public bool Equals(SwapInfo other)
  216.   {
  217.     return rowFrom == other.rowFrom && colFrom == other.colFrom && rowTo == other.rowTo && colTo == other.colTo ||
  218.            rowFrom == other.rowTo && colFrom == other.colTo && rowTo == other.rowFrom && colTo == other.colFrom;
  219.   }
  220.  
  221.   public override int GetHashCode()
  222.   {
  223.     return Math.Min(rowFrom, rowTo) + Math.Max(rowFrom, rowTo) * 64 + Math.Min(colFrom, colTo) * 4096 + Math.Max(colFrom, colTo) * 262144;
  224.   }
  225. }
  226.  
  227.  
  228. public class PuzzleState
  229. {
  230.   private PuzzleState(GridState gridState)
  231.   {
  232.     GridState = gridState;
  233.   }
  234.  
  235.   public void ClearGridState() => GridState = null;
  236.  
  237.   public GridState GridState { get; private set; }
  238.  
  239.   public PuzzleState(params string[] lines)
  240.     : this(new GridState(lines))
  241.   { }
  242.  
  243.   public int MoveCount { get; }
  244.  
  245.   public PuzzleState Parent { get; }
  246.  
  247.   public SwapInfo MoveFromParent { get; }
  248.  
  249.   private PuzzleState(PuzzleState parent, SwapInfo move, GridState gridState)
  250.     : this(gridState)
  251.   {
  252.     Parent = parent;
  253.     MoveCount = parent.MoveCount + 1;
  254.     MoveFromParent = move;
  255.   }
  256.  
  257.   public bool IsSwapValid(SwapInfo info) => GridState.IsSwapValid(info);
  258.  
  259.   public bool AllowWrapAround { get; set; } = true;
  260.  
  261.   public IEnumerable<PuzzleState> GetStatesAfterValidMoves()
  262.   {
  263.     int fromRowLimit = AllowWrapAround ? GridState.RowCount : (GridState.RowCount - 1);
  264.     int fromColLimit = AllowWrapAround ? GridState.ColumnCount : (GridState.ColumnCount - 1);
  265.     for (int fromRow = 0; fromRow < fromRowLimit; fromRow++)
  266.     {
  267.       int toNextRow = (fromRow + 1) % GridState.RowCount;
  268.       for (int fromCol = 0; fromCol < fromColLimit; fromCol++)
  269.       {
  270.         CellState fromState = GridState[fromRow, fromCol];
  271.         if (fromState.MovesLeft < 1)
  272.           continue;
  273.  
  274.         CellState toState = GridState[toNextRow, fromCol];
  275.         if (fromState.IsSwapValid(toState))
  276.         {
  277.           var swapInfo = new SwapInfo { colFrom = (byte)fromCol, rowFrom = (byte)fromRow, colTo = (byte)fromCol, rowTo = (byte)toNextRow };
  278.           yield return new PuzzleState(this, swapInfo, GridState.GetStateAfterSwap(swapInfo));
  279.         }
  280.  
  281.         int toNextCol = (fromCol + 1) % GridState.ColumnCount;
  282.         toState = GridState[fromRow, toNextCol];
  283.         if (fromState.IsSwapValid(toState))
  284.         {
  285.           var swapInfo = new SwapInfo { colFrom = (byte)fromCol, rowFrom = (byte)fromRow, colTo = (byte)toNextCol, rowTo = (byte)fromRow };
  286.           yield return new PuzzleState(this, swapInfo, GridState.GetStateAfterSwap(swapInfo));
  287.         }
  288.       }
  289.     }
  290.   }
  291.  
  292.   static GridState targetState = new GridState("123", "456", "789");
  293.  
  294.   public bool IsTargetState => GridState.EqualValues(targetState); // GridState.IsMagic();
  295.  
  296.   // this is horrendous code using a recursive enumerator...
  297.   // but rarely called (only when a solution is found)
  298.   // just as well the values of N will be relatively small!
  299.   public IEnumerable<SwapInfo> GetSwaps()
  300.   {
  301.     return Parent?.GetSwaps().Concat(Enumerable.Repeat(MoveFromParent, 1)) ?? Enumerable.Empty<SwapInfo>();
  302.   }
  303. }
  304.  
  305.  
  306. public class SquareSwap
  307. {
  308.   static public void Main()
  309.   {
  310.     Console.OutputEncoding = System.Text.Encoding.UTF8;
  311.  
  312.     var startingState = new PuzzleState("816", "357", "492") { AllowWrapAround = true };
  313.  
  314.     Console.WriteLine($"Starting state [total moves left: {startingState.GridState.TotalMovesLeft}]:");
  315.     Console.WriteLine(startingState.GridState);
  316.  
  317.     var workingSets = Enumerable.Range(0, startingState.GridState.TotalMovesLeft + 1).Select(i => new Dictionary<GridState, PuzzleState>()).ToArray();
  318.  
  319.     workingSets[startingState.GridState.TotalMovesLeft].Add(startingState.GridState, startingState);
  320.  
  321.     bool found = false;
  322.  
  323.     for (int i = workingSets.Length-1; i > 0 /*&& !found*/; i--)
  324.     {
  325.       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]");
  326.  
  327.       System.Threading.Tasks.Parallel.ForEach(workingSets[i].Values, puzzleState =>
  328.       {
  329.         if (puzzleState.IsTargetState)
  330.         {
  331.           found = true;
  332.           lock (workingSets[i])
  333.           {
  334.             Console.WriteLine("Found solution!");
  335.             Console.WriteLine($"... after swaps: {string.Join(", ", puzzleState.GetSwaps().Select(s => $"R{s.rowFrom + 1}C{s.colFrom + 1}<>R{s.rowTo + 1}C{s.colTo + 1}"))}");
  336.             Console.WriteLine(puzzleState.GridState);
  337.           }
  338.         }
  339.         else
  340.           foreach (var nextState in puzzleState.GetStatesAfterValidMoves())
  341.           {
  342.             var swapInfo = nextState.MoveFromParent;
  343.             int movesLeft = nextState.GridState.TotalMovesLeft;
  344.             //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}]:");
  345.             //Console.WriteLine(nextState.GridState);
  346.  
  347.             if (movesLeft >= i)
  348.               throw new InvalidOperationException("Total moves left didn't decrease???!");
  349.  
  350.             lock (workingSets[movesLeft])
  351.             {
  352.               if (workingSets[movesLeft].TryGetValue(nextState.GridState, out var firstEquivalentState))
  353.               {
  354.                 //Console.WriteLine("Duplicate found!");
  355.               }
  356.               else
  357.                 workingSets[movesLeft].Add(nextState.GridState, nextState);
  358.             }
  359.           }
  360.         // we don't use the gridstate again (can be regenerated from move if needed for a "path to solution" report)
  361.         // so can allow the garbage collector to reclaim it.
  362.         puzzleState.ClearGridState();
  363.       });
  364.       // allow "duplicate paths" that lead to no unique states to be reclaimed by garbage collector
  365.       // (this was first attempt at memory management, but probably less effective than ClearGridState above, at least in early phases of search)
  366.       workingSets[i] = null;
  367.     }
  368.   }
  369. }
  370.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement