Guest User

KlotskiWithMerge.cs

a guest
Jul 16th, 2020
82
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. [Flags]
  6. public enum KlotskiCellState : byte
  7. {
  8.   ConnectedLeft = 1 << KlotskiMoveDirection.Left,
  9.   ConnectedRight = 1 << KlotskiMoveDirection.Right,
  10.   ConnectedUp = 1 << KlotskiMoveDirection.Up,
  11.   ConnectedDown = 1 << KlotskiMoveDirection.Down,
  12.   Empty = 16,
  13.   Fixed = 32, // fixed cells cannot be moved (e.g. attached to outside of grid for non-rectangular puzzles?)
  14. }
  15.  
  16. public enum KlotskiMoveDirection
  17. {
  18.   Left,
  19.   Right,
  20.   Up,
  21.   Down,
  22.   MultipleDirections,
  23. }
  24.  
  25. public class KlotskiGridState: IEquatable<KlotskiGridState>
  26. {
  27.   static Dictionary<KlotskiCellState, char[]> DisplayText = new Dictionary<KlotskiCellState, char[]>
  28.   {
  29.     { KlotskiCellState.Empty, "      ".ToCharArray() },
  30.     { KlotskiCellState.Fixed, "######".ToCharArray() },
  31.     { 0, "╔═╗╚═╝".ToCharArray() },
  32.     { KlotskiCellState.ConnectedLeft, "══╗══╝".ToCharArray() },
  33.     { KlotskiCellState.ConnectedRight, "╔══╚══".ToCharArray() },
  34.     { KlotskiCellState.ConnectedUp, "║ ║╚═╝".ToCharArray() },
  35.     { KlotskiCellState.ConnectedDown, "╔═╗║ ║".ToCharArray() },
  36.     { KlotskiCellState.ConnectedLeft|KlotskiCellState.ConnectedRight, "══════".ToCharArray() },
  37.     { KlotskiCellState.ConnectedUp|KlotskiCellState.ConnectedDown, "║ ║║ ║".ToCharArray() },
  38.     { KlotskiCellState.ConnectedUp|KlotskiCellState.ConnectedLeft, "╝ ║══╝".ToCharArray() },
  39.     { KlotskiCellState.ConnectedUp|KlotskiCellState.ConnectedRight, "║ ╚╚══".ToCharArray() },
  40.     // TODO: other possible connections to allow full range of puzzles!
  41.     // down/left, down/right,
  42.     // combinations of 3 connections (4 possibilities),
  43.     // connected all 4 directions.
  44.   };
  45.  
  46.   readonly char[] unknownCell = "<?><?>".ToCharArray();
  47.  
  48.  
  49.   public KlotskiGridState(int columnCount, KlotskiCellState[] cellStates)
  50.   {
  51.     if (cellStates.Length % columnCount != 0)
  52.       throw new ArgumentOutOfRangeException();
  53.     ColumnCount = columnCount;
  54.     CellStates = cellStates;
  55.   }
  56.  
  57.   public int ColumnCount { get; }
  58.   public int RowCount => CellStates.Length / ColumnCount;
  59.  
  60.   public KlotskiCellState[] CellStates { get; }
  61.  
  62.   public HashSet<int> FindConnectedPieceIndexes(int startIndex, Dictionary<KlotskiMoveDirection, int> moveSteps)
  63.   {
  64.     HashSet<int> resultSet = new HashSet<int> { startIndex };
  65.     HashSet<int> searchSet = new HashSet<int> { startIndex };
  66.  
  67.     while(searchSet.Count > 0)
  68.     {
  69.       int index = searchSet.First();
  70.       searchSet.Remove(index);
  71.  
  72.       var cellState = CellStates[index];
  73.       foreach(var step in moveSteps)
  74.       {
  75.         if (((int)cellState & (1 << (int)step.Key)) != 0 && resultSet.Add(index + step.Value))
  76.           searchSet.Add(index + step.Value);
  77.       }
  78.     }
  79.     return resultSet;
  80.   }
  81.  
  82.   public override string ToString()
  83.   {
  84.     int rowLength = ColumnCount * 3 + 1;
  85.     char[] result = new char[rowLength * RowCount * 2];
  86.    
  87.     for (int row = 0; row < RowCount; row++)
  88.     {
  89.       for (int col = 0; col < ColumnCount; col++)
  90.       {
  91.         int cellBaseIndex = row * rowLength * 2 + col * 3;
  92.         if (!DisplayText.TryGetValue(CellStates[row * ColumnCount + col], out var cellText))
  93.           cellText = unknownCell;
  94.         Array.Copy(cellText, 0, result, cellBaseIndex, 3);
  95.         Array.Copy(cellText, 3, result, cellBaseIndex + rowLength, 3);
  96.       }
  97.       result[row * rowLength * 2 + rowLength*2 - 1] = '\n';
  98.       result[row * rowLength * 2 + rowLength - 1] = '\n';
  99.     }
  100.     return new string(result);
  101.   }
  102.  
  103.   public override bool Equals(object obj)
  104.   {
  105.     return base.Equals(obj) || obj is KlotskiGridState other && Equals(other);
  106.   }
  107.  
  108.   public bool Equals(KlotskiGridState other)
  109.   {
  110.     // don't bother checking ColumnCount - it shouldn't be different in cases we're trying to compare!
  111.     // we compare Length only to avoid potential exceptions.
  112.     var otherCellStates = other.CellStates;
  113.     if (otherCellStates.Length != CellStates.Length)
  114.       return false;
  115.     for (int i = 0; i < CellStates.Length; i++)
  116.       if (CellStates[i] != otherCellStates[i])
  117.         return false;
  118.     return true;
  119.   }
  120.  
  121.   public override int GetHashCode()
  122.   {
  123.     int result = 0;
  124.     for (int i = 0; i < CellStates.Length; i++)
  125.       result = (result >> 18) ^ (result * 0x1413 + (int)CellStates[i]);
  126.     return result;
  127.   }
  128. }
  129.  
  130. public class KlotskiMove
  131. {
  132.   // move parameterised based on the index of the empty cell to cover, and the direction that a piece should be moved to cover it.
  133.   // This is enough to fully define a single simple move.
  134.   public int EmptyCellToCover { get; set; }
  135.   public KlotskiMoveDirection Direction { get; set; }
  136.   // to allow for "merged" moves (and more verbose output),
  137.   // also record information about the number of steps moved, and which piece(s) were moved.
  138.   public int StepCount { get; set; }
  139.   public List<int> PiecesMoved { get; set; }
  140. }
  141.  
  142. public class KlotskiPuzzleState
  143. {
  144.   private KlotskiPuzzleState(KlotskiGridState gridState)
  145.   {
  146.     GridState = gridState;
  147.   }
  148.  
  149.   public KlotskiGridState GridState { get; }
  150.  
  151.   public KlotskiPuzzleState(params string[] lines)
  152.   {
  153.     int rows = lines.Length;
  154.     if (rows == 0)
  155.       throw new ArgumentOutOfRangeException();
  156.     int cols = lines[0].Length;
  157.     if (lines.Any(line => line.Length != cols))
  158.       throw new ArgumentOutOfRangeException();
  159.  
  160.     EmptyCellIndex = new List<int>();
  161.     // add an extra column and 2 extra rows.
  162.     // this way we don't need to do "if outside grid OR another cell" etc.
  163.     var initialCellStates = new KlotskiCellState[(rows + 2) * (cols + 1)];
  164.     for (int row = -1; row <= rows; row++)
  165.     {
  166.       for (int col = 0; col <= cols; col++)
  167.       {
  168.         int index = (cols + 1) * (row + 1) + col;
  169.         if (row < 0 || row >= rows || col >= cols || lines[row][col] == '#')
  170.           initialCellStates[index] = KlotskiCellState.Fixed;
  171.         else if (lines[row][col] is var c && c == ' ')
  172.         {
  173.           initialCellStates[index] = KlotskiCellState.Empty;
  174.           EmptyCellIndex.Add(index);
  175.         }
  176.         else
  177.         {
  178.           initialCellStates[index] = 0;
  179.           if (row > 0 && lines[row - 1][col] == c)
  180.             initialCellStates[index] |= KlotskiCellState.ConnectedUp;
  181.           if (row < rows - 1 && lines[row + 1][col] == c)
  182.             initialCellStates[index] |= KlotskiCellState.ConnectedDown;
  183.           if (col > 0 && lines[row][col - 1] == c)
  184.             initialCellStates[index] |= KlotskiCellState.ConnectedLeft;
  185.           if (col < cols - 1 && lines[row][col + 1] == c)
  186.             initialCellStates[index] |= KlotskiCellState.ConnectedRight;
  187.         }
  188.       }
  189.     }
  190.     GridState = new KlotskiGridState(cols + 1, initialCellStates);
  191.     MoveStep = new Dictionary<KlotskiMoveDirection, int>
  192.     {
  193.       { KlotskiMoveDirection.Left, -1 },
  194.       { KlotskiMoveDirection.Right, 1 },
  195.       { KlotskiMoveDirection.Up, -(cols+1) },
  196.       { KlotskiMoveDirection.Down, (cols+1) },
  197.     };
  198.     Console.WriteLine(GridState);
  199.   }
  200.  
  201.   List<int> EmptyCellIndex { get; }
  202.  
  203.   public int MoveCount { get; private set; }
  204.  
  205.   public KlotskiPuzzleState Parent { get; private set; }
  206.  
  207.   public KlotskiMove MoveFromParent { get; }
  208.  
  209.   private KlotskiPuzzleState(KlotskiPuzzleState parent, KlotskiMove move, KlotskiGridState gridState, List<int> emptyCells)
  210.     : this(gridState)
  211.   {
  212.     Parent = parent;
  213.     MoveStep = parent.MoveStep;
  214.     MoveCount = parent.MoveCount + 1;
  215.     MoveFromParent = move;
  216.     EmptyCellIndex = emptyCells;
  217.   }
  218.  
  219.   static readonly KlotskiMoveDirection[] AllMoveDirections = new[] { KlotskiMoveDirection.Left, KlotskiMoveDirection.Right, KlotskiMoveDirection.Up, KlotskiMoveDirection.Down };
  220.  
  221.   Dictionary<KlotskiMoveDirection, int> MoveStep { get; }
  222.  
  223.   public IEnumerable<KlotskiPuzzleState> GetStatesAfterValidMoves()
  224.   {
  225.     var originalGrid = GridState.CellStates;
  226.     foreach(int index in EmptyCellIndex)
  227.     {
  228.       foreach(var direction in AllMoveDirections)
  229.       {
  230.         int moveStep = MoveStep[direction];
  231.         int searchStep = -moveStep;
  232.  
  233.         // Identify which piece to attempt to move.
  234.         int pieceIndex = index;
  235.         while (originalGrid[pieceIndex] == KlotskiCellState.Empty)
  236.           pieceIndex += searchStep;
  237.  
  238.         var primaryPieceState = originalGrid[pieceIndex];
  239.  
  240.         if ((primaryPieceState & KlotskiCellState.Fixed) != 0)
  241.           continue; // we can't move a fixed piece (or wall).
  242.  
  243.         // if a piece can be moved, but is wide enough to cover an adjacent empty cell, we'll find the same move from
  244.         // both (or all) empty cells.
  245.         // Avoid this by considering only the lowermost (for a left/right move) or leftmost (for an up/down) move of a continuously connected shape
  246.         // before we bother to find the entire shape.
  247.         // For complex shapes, this optimisation may fail, but we'll generate two moves with the same result grid and ignore one anyway.
  248.  
  249.         if ((direction == KlotskiMoveDirection.Left || direction == KlotskiMoveDirection.Right) &&
  250.             (primaryPieceState & KlotskiCellState.ConnectedDown) != 0)
  251.           continue;
  252.         if ((direction == KlotskiMoveDirection.Up || direction == KlotskiMoveDirection.Down) &&
  253.             (primaryPieceState & KlotskiCellState.ConnectedLeft) != 0)
  254.           continue;
  255.  
  256.         // now identify all connected piece indexes, to see if it is possible to move the selected piece.
  257.  
  258.         HashSet<int> pieceIndexes = GridState.FindConnectedPieceIndexes(pieceIndex, MoveStep);
  259.  
  260.         HashSet<int> movedPieceIndexes = pieceIndexes;
  261.         bool moveIsValid = true;
  262.         int totalMove = 0;
  263.         while(moveIsValid && !movedPieceIndexes.Contains(index))
  264.         {
  265.           totalMove += moveStep;
  266.           movedPieceIndexes = new HashSet<int>(movedPieceIndexes.Select(i => i + moveStep));
  267.           moveIsValid = movedPieceIndexes.All(i => pieceIndexes.Contains(i) || EmptyCellIndex.Contains(i));
  268.         }
  269.         if (moveIsValid)
  270.         {
  271.           KlotskiCellState[] cellStatesAfterMove = new KlotskiCellState[originalGrid.Length];
  272.           Array.Copy(originalGrid, cellStatesAfterMove, cellStatesAfterMove.Length);
  273.  
  274.           // first blank the piece's original location.
  275.           foreach (int i in pieceIndexes)
  276.             cellStatesAfterMove[i] = KlotskiCellState.Empty;
  277.  
  278.           // the copy the piece to its new location
  279.           foreach (int i in pieceIndexes)
  280.             cellStatesAfterMove[i + totalMove] = originalGrid[i];
  281.  
  282.           List<int> emptyCellsAfterMove = new List<int>(EmptyCellIndex.Count);
  283.           foreach (int i in pieceIndexes.Concat(EmptyCellIndex))
  284.             if (!movedPieceIndexes.Contains(i))
  285.               emptyCellsAfterMove.Add(i);
  286.  
  287.           var moveDone = new KlotskiMove { EmptyCellToCover = index, PiecesMoved = new List<int> { pieceIndex }, Direction = direction, StepCount = totalMove / moveStep };
  288.           yield return new KlotskiPuzzleState(this, moveDone, new KlotskiGridState(GridState.ColumnCount, cellStatesAfterMove), emptyCellsAfterMove);
  289.  
  290.           // detection of multiple moves that can be done "together" done by caller, not here as originally planned.
  291.           // the caller will ignore duplicate states before attempting a merge.
  292.         }
  293.       }
  294.     }
  295.   }
  296.  
  297.   static int AllowableMergeType = 1;
  298.   // merge types:
  299.   // 1: try to move multiple pieces the same amount in the same direction as a single move.
  300.   // 2: try to move the same piece in multiple directions as a single move.
  301.  
  302.   public bool TryMergeWithParent()
  303.   {
  304.     var parentMove = Parent?.MoveFromParent;
  305.  
  306.     if (parentMove == null)
  307.       return false;
  308.     if (AllowableMergeType == 1 && parentMove.Direction == MoveFromParent.Direction && parentMove.StepCount == MoveFromParent.StepCount)
  309.     {
  310.       // the containing condition allows us to "cheat" by moving one piece 2 step and another piece 1 step but calling it a single "move".
  311.       // thus we must also ensure that our (non-merged) move doesn't move one of the pieces that the parent moved.
  312.       var pieceIndexes = Parent.GridState.FindConnectedPieceIndexes(MoveFromParent.PiecesMoved[0], MoveStep);
  313.       var parentMovedPieceIndexes = parentMove.PiecesMoved.Select(i => i + MoveStep[parentMove.Direction] * parentMove.StepCount);
  314.       if (parentMovedPieceIndexes.Any(pieceIndexes.Contains))
  315.         return false;
  316.  
  317.       // TODO: consider whether to allow a merged move only if all the pieces involved would be moved by "pushing" the one furthest from the emty cell being covered.
  318.       // This will be complicated, as a 1 x 2 or larger can push two different 1 x 1 (or oppositely-oriented 2x2, etc.)
  319.       // but, if implemented, the tightened rule set wouldn't allow the two different pieces to be considered to have moved together beforehand.
  320.       // The more complicated merge logic would then potentially generate a "double-merge" where our move count is now lower than that of our former parent,
  321.       // which invalidates all sorts of other assumptions implicit in the overall search method.
  322.  
  323.       MoveFromParent.PiecesMoved.AddRange(parentMove.PiecesMoved);
  324.       MoveFromParent.EmptyCellToCover = parentMove.EmptyCellToCover;
  325.       MoveCount = Parent.MoveCount;
  326.       Parent = Parent.Parent;
  327.       return true;
  328.     }
  329.     else if(AllowableMergeType == 2 && Parent.GridState.FindConnectedPieceIndexes(MoveFromParent.PiecesMoved[0], MoveStep).Contains(parentMove.EmptyCellToCover))
  330.     {
  331.       // TODO: properly reconcile the square identified on the "piece to move" with the cell actually covered.
  332.       // our move may have identified a different square of the same piece as the one moved in the parent move.
  333.       // so the move may end up displayed "wrong".
  334.       MoveFromParent.StepCount += parentMove.StepCount;
  335.       MoveFromParent.PiecesMoved = parentMove.PiecesMoved;
  336.       MoveFromParent.Direction = KlotskiMoveDirection.MultipleDirections;
  337.       MoveCount = Parent.MoveCount;
  338.       Parent = Parent.Parent;
  339.       return true;
  340.     }
  341.     return false;
  342.   }
  343. }
  344.  
  345.  
  346. public class Problem
  347. {
  348.  
  349.   HashSet<KlotskiGridState> ObservedGridStates { get; }
  350.  
  351.   static KlotskiPuzzleState startingState = new KlotskiPuzzleState(
  352.     "BAAAC",
  353.     "BBDCC",
  354.     "EEDFF",
  355.     "GGHII",
  356.     "JJHKK",
  357.     "L   M");
  358.  
  359.  
  360.   static public void Main()
  361.   {
  362.     var depthDict = new Dictionary<KlotskiGridState, int>() { { startingState.GridState, 0 } };
  363.  
  364.     Queue<KlotskiPuzzleState> statesToConsider = new Queue<KlotskiPuzzleState>();
  365.     Queue<KlotskiPuzzleState> mergedMoveStatesToConsider = new Queue<KlotskiPuzzleState>();
  366.     statesToConsider.Enqueue(startingState);
  367.  
  368.     int lastDepthSeen = 0;
  369.  
  370.     while (statesToConsider.Count > 0)
  371.     {
  372.       var currentState = (mergedMoveStatesToConsider.Count > 0 ? mergedMoveStatesToConsider : statesToConsider).Dequeue();
  373.       if (currentState.MoveCount > lastDepthSeen)
  374.       {
  375.         lastDepthSeen = currentState.MoveCount;
  376.         Console.WriteLine($"Processing move {lastDepthSeen}... {statesToConsider.Count} states in queue, {depthDict.Count} possible states reached");
  377.         if (statesToConsider.Count == 11)
  378.         {
  379.           foreach (var printState in statesToConsider)
  380.           {
  381.             var moveInfo = printState.MoveFromParent;
  382.             if (moveInfo == null)
  383.               Console.WriteLine("Starting state:");
  384.             else
  385.               Console.WriteLine($"After move {printState.MoveCount}: piece(s) at {string.Join(",", moveInfo.PiecesMoved)} by {moveInfo.StepCount} {moveInfo.Direction} to cover {moveInfo.EmptyCellToCover}:");
  386.             Console.WriteLine(printState.GridState);
  387.           }
  388.         }
  389.       }
  390.       foreach (var state in currentState.GetStatesAfterValidMoves())
  391.       {
  392.         if (depthDict.TryGetValue(state.GridState, out int lastDepth))
  393.         {
  394.           // Console.WriteLine($"Duplicate of a state reached in {lastDepth} moves");
  395.         }
  396.         else if(state.GridState.CellStates[6 * state.GridState.ColumnCount + 2] == (KlotskiCellState.ConnectedLeft | KlotskiCellState.ConnectedRight))
  397.         {
  398.           for (var printState = state; printState != null; printState = printState.Parent)
  399.           {
  400.             var moveInfo = printState.MoveFromParent;
  401.             if (moveInfo == null)
  402.               Console.WriteLine("Starting state:");
  403.             else
  404.               Console.WriteLine($"After move {printState.MoveCount}: piece(s) at {string.Join(",", moveInfo.PiecesMoved)} by {moveInfo.StepCount} {moveInfo.Direction} to cover {moveInfo.EmptyCellToCover}:");
  405.             Console.WriteLine(printState.GridState);
  406.           }
  407.           return;
  408.         }
  409.         else
  410.         {
  411.           (state.TryMergeWithParent() ? mergedMoveStatesToConsider : statesToConsider).Enqueue(state);
  412.           depthDict[state.GridState] = state.MoveCount;
  413.         }
  414.       }
  415.     }
  416.   }
  417. }
RAW Paste Data Copied