Guest User

Klotski.cs

a guest
Jul 14th, 2020
98
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. }
  23.  
  24. public class KlotskiGridState: IEquatable<KlotskiGridState>
  25. {
  26.   static Dictionary<KlotskiCellState, char[]> DisplayText = new Dictionary<KlotskiCellState, char[]>
  27.   {
  28.     { KlotskiCellState.Empty, "      ".ToCharArray() },
  29.     { KlotskiCellState.Fixed, "######".ToCharArray() },
  30.     { 0, "╔═╗╚═╝".ToCharArray() },
  31.     { KlotskiCellState.ConnectedLeft, "══╗══╝".ToCharArray() },
  32.     { KlotskiCellState.ConnectedRight, "╔══╚══".ToCharArray() },
  33.     { KlotskiCellState.ConnectedUp, "║ ║╚═╝".ToCharArray() },
  34.     { KlotskiCellState.ConnectedDown, "╔═╗║ ║".ToCharArray() },
  35.     { KlotskiCellState.ConnectedLeft|KlotskiCellState.ConnectedRight, "══════".ToCharArray() },
  36.     { KlotskiCellState.ConnectedUp|KlotskiCellState.ConnectedDown, "║ ║║ ║".ToCharArray() },
  37.     { KlotskiCellState.ConnectedUp|KlotskiCellState.ConnectedLeft, "╝ ║══╝".ToCharArray() },
  38.     { KlotskiCellState.ConnectedUp|KlotskiCellState.ConnectedRight, "║ ╚╚══".ToCharArray() },
  39.     // TODO: other possible connections to allow full range of puzzles!
  40.     // down/left, down/right,
  41.     // combinations of 3 connections (4 possibilities),
  42.     // connected all 4 directions.
  43.   };
  44.  
  45.   readonly char[] unknownCell = "<?><?>".ToCharArray();
  46.  
  47.  
  48.   public KlotskiGridState(int columnCount, KlotskiCellState[] cellStates)
  49.   {
  50.     if (cellStates.Length % columnCount != 0)
  51.       throw new ArgumentOutOfRangeException();
  52.     ColumnCount = columnCount;
  53.     CellStates = cellStates;
  54.   }
  55.  
  56.   public int ColumnCount { get; }
  57.   public int RowCount => CellStates.Length / ColumnCount;
  58.  
  59.   public KlotskiCellState[] CellStates { get; }
  60.  
  61.   public HashSet<int> FindConnectedPieceIndexes(int startIndex, Dictionary<KlotskiMoveDirection, int> moveSteps)
  62.   {
  63.     HashSet<int> resultSet = new HashSet<int> { startIndex };
  64.     HashSet<int> searchSet = new HashSet<int> { startIndex };
  65.  
  66.     while(searchSet.Count > 0)
  67.     {
  68.       int index = searchSet.First();
  69.       searchSet.Remove(index);
  70.  
  71.       var cellState = CellStates[index];
  72.       foreach(var step in moveSteps)
  73.       {
  74.         if (((int)cellState & (1 << (int)step.Key)) != 0 && resultSet.Add(index + step.Value))
  75.           searchSet.Add(index + step.Value);
  76.       }
  77.     }
  78.     return resultSet;
  79.   }
  80.  
  81.   public override string ToString()
  82.   {
  83.     int rowLength = ColumnCount * 3 + 1;
  84.     char[] result = new char[rowLength * RowCount * 2];
  85.    
  86.     for (int row = 0; row < RowCount; row++)
  87.     {
  88.       for (int col = 0; col < ColumnCount; col++)
  89.       {
  90.         int cellBaseIndex = row * rowLength * 2 + col * 3;
  91.         if (!DisplayText.TryGetValue(CellStates[row * ColumnCount + col], out var cellText))
  92.           cellText = unknownCell;
  93.         Array.Copy(cellText, 0, result, cellBaseIndex, 3);
  94.         Array.Copy(cellText, 3, result, cellBaseIndex + rowLength, 3);
  95.       }
  96.       result[row * rowLength * 2 + rowLength*2 - 1] = '\n';
  97.       result[row * rowLength * 2 + rowLength - 1] = '\n';
  98.     }
  99.     return new string(result);
  100.   }
  101.  
  102.   public override bool Equals(object obj)
  103.   {
  104.     return base.Equals(obj) || obj is KlotskiGridState other && Equals(other);
  105.   }
  106.  
  107.   public bool Equals(KlotskiGridState other)
  108.   {
  109.     // don't bother checking ColumnCount - it shouldn't be different in cases we're trying to compare!
  110.     // we compare Length only to avoid potential exceptions.
  111.     var otherCellStates = other.CellStates;
  112.     if (otherCellStates.Length != CellStates.Length)
  113.       return false;
  114.     for (int i = 0; i < CellStates.Length; i++)
  115.       if (CellStates[i] != otherCellStates[i])
  116.         return false;
  117.     return true;
  118.   }
  119.  
  120.   public override int GetHashCode()
  121.   {
  122.     int result = 0;
  123.     for (int i = 0; i < CellStates.Length; i++)
  124.       result = (result >> 18) ^ (result * 0x1413 + (int)CellStates[i]);
  125.     return result;
  126.   }
  127. }
  128.  
  129. public struct KlotskiMove
  130. {
  131.   // move parameterised based on the index of the empty cell to cover, and the direction that a piece should be moved to cover it.
  132.   public int EmptyCellToCover { get; set; }
  133.   public KlotskiMoveDirection Direction { get; set; }
  134. }
  135.  
  136. public class KlotskiPuzzleState
  137. {
  138.   private KlotskiPuzzleState(KlotskiGridState gridState)
  139.   {
  140.     GridState = gridState;
  141.   }
  142.  
  143.   public KlotskiGridState GridState { get; }
  144.  
  145.   public KlotskiPuzzleState(params string[] lines)
  146.   {
  147.     int rows = lines.Length;
  148.     if (rows == 0)
  149.       throw new ArgumentOutOfRangeException();
  150.     int cols = lines[0].Length;
  151.     if (lines.Any(line => line.Length != cols))
  152.       throw new ArgumentOutOfRangeException();
  153.  
  154.     EmptyCellIndex = new List<int>();
  155.     // add an extra column and 2 extra rows.
  156.     // this way we don't need to do "if outside grid OR another cell" etc.
  157.     var initialCellStates = new KlotskiCellState[(rows + 2) * (cols + 1)];
  158.     for (int row = -1; row <= rows; row++)
  159.     {
  160.       for (int col = 0; col <= cols; col++)
  161.       {
  162.         int index = (cols + 1) * (row + 1) + col;
  163.         if (row < 0 || row >= rows || col >= cols || lines[row][col] == '#')
  164.           initialCellStates[index] = KlotskiCellState.Fixed;
  165.         else if (lines[row][col] is var c && c == ' ')
  166.         {
  167.           initialCellStates[index] = KlotskiCellState.Empty;
  168.           EmptyCellIndex.Add(index);
  169.         }
  170.         else
  171.         {
  172.           initialCellStates[index] = 0;
  173.           if (row > 0 && lines[row - 1][col] == c)
  174.             initialCellStates[index] |= KlotskiCellState.ConnectedUp;
  175.           if (row < rows - 1 && lines[row + 1][col] == c)
  176.             initialCellStates[index] |= KlotskiCellState.ConnectedDown;
  177.           if (col > 0 && lines[row][col - 1] == c)
  178.             initialCellStates[index] |= KlotskiCellState.ConnectedLeft;
  179.           if (col < cols - 1 && lines[row][col + 1] == c)
  180.             initialCellStates[index] |= KlotskiCellState.ConnectedRight;
  181.         }
  182.       }
  183.     }
  184.     GridState = new KlotskiGridState(cols + 1, initialCellStates);
  185.     MoveStep = new Dictionary<KlotskiMoveDirection, int>
  186.     {
  187.       { KlotskiMoveDirection.Left, -1 },
  188.       { KlotskiMoveDirection.Right, 1 },
  189.       { KlotskiMoveDirection.Up, -(cols+1) },
  190.       { KlotskiMoveDirection.Down, (cols+1) },
  191.     };
  192.     Console.WriteLine(GridState);
  193.   }
  194.  
  195.   List<int> EmptyCellIndex { get; }
  196.  
  197.   public int MoveCount { get; }
  198.  
  199.   public KlotskiPuzzleState Parent { get; }
  200.  
  201.   public KlotskiMove MoveFromParent { get; }
  202.  
  203.   private KlotskiPuzzleState(KlotskiPuzzleState parent, KlotskiMove move, KlotskiGridState gridState, List<int> emptyCells)
  204.     : this(gridState)
  205.   {
  206.     Parent = parent;
  207.     MoveStep = parent.MoveStep;
  208.     MoveCount = parent.MoveCount + 1;
  209.     MoveFromParent = move;
  210.     EmptyCellIndex = emptyCells;
  211.   }
  212.  
  213.   static readonly KlotskiMoveDirection[] AllMoveDirections = new[] { KlotskiMoveDirection.Left, KlotskiMoveDirection.Right, KlotskiMoveDirection.Up, KlotskiMoveDirection.Down };
  214.  
  215.   Dictionary<KlotskiMoveDirection, int> MoveStep { get; }
  216.  
  217.   public IEnumerable<KlotskiPuzzleState> GetStatesAfterValidMoves()
  218.   {
  219.     var originalGrid = GridState.CellStates;
  220.     foreach(int index in EmptyCellIndex)
  221.     {
  222.       foreach(var direction in AllMoveDirections)
  223.       {
  224.         int moveStep = MoveStep[direction];
  225.         int searchStep = -moveStep;
  226.  
  227.         // Identify which piece to attempt to move.
  228.         int pieceIndex = index;
  229.         while (originalGrid[pieceIndex] == KlotskiCellState.Empty)
  230.           pieceIndex += searchStep;
  231.  
  232.         var primaryPieceState = originalGrid[pieceIndex];
  233.  
  234.         if ((primaryPieceState & KlotskiCellState.Fixed) != 0)
  235.           continue; // we can't move a fixed piece (or wall).
  236.  
  237.         // if a piece can be moved, but is wide enough to cover an adjacent empty cell, we'll find the same move from
  238.         // both (or all) empty cells.
  239.         // Avoid this by considering only the lowermost (for a left/right move) or leftmost (for an up/down) move of a continuously connected shape
  240.         // before we bother to find the entire shape.
  241.         // For complex shapes, this optimisation may fail, but we'll generate two moves with the same result grid and ignore one anyway.
  242.  
  243.         if ((direction == KlotskiMoveDirection.Left || direction == KlotskiMoveDirection.Right) &&
  244.             (primaryPieceState & KlotskiCellState.ConnectedDown) != 0)
  245.           continue;
  246.         if ((direction == KlotskiMoveDirection.Up || direction == KlotskiMoveDirection.Down) &&
  247.             (primaryPieceState & KlotskiCellState.ConnectedLeft) != 0)
  248.           continue;
  249.  
  250.         // now identify all connected piece indexes, to see if it is possible to move the selected piece.
  251.  
  252.         HashSet<int> pieceIndexes = GridState.FindConnectedPieceIndexes(pieceIndex, MoveStep);
  253.  
  254.         HashSet<int> movedPieceIndexes = pieceIndexes;
  255.         bool moveIsValid = true;
  256.         int totalMove = 0;
  257.         while(moveIsValid && !movedPieceIndexes.Contains(index))
  258.         {
  259.           totalMove += moveStep;
  260.           movedPieceIndexes = new HashSet<int>(movedPieceIndexes.Select(i => i + moveStep));
  261.           moveIsValid = movedPieceIndexes.All(i => pieceIndexes.Contains(i) || EmptyCellIndex.Contains(i));
  262.         }
  263.         if (!moveIsValid)
  264.           continue;
  265.         KlotskiCellState[] cellStatesAfterMove = new KlotskiCellState[originalGrid.Length];
  266.         Array.Copy(originalGrid, cellStatesAfterMove, cellStatesAfterMove.Length);
  267.  
  268.         // first blank the piece's original location.
  269.         foreach (int i in pieceIndexes)
  270.           cellStatesAfterMove[i] = KlotskiCellState.Empty;
  271.  
  272.         // the copy the piece to its new location
  273.         foreach (int i in pieceIndexes)
  274.           cellStatesAfterMove[i + totalMove] = originalGrid[i];
  275.  
  276.         List<int> emptyCellsAfterMove = new List<int>(EmptyCellIndex.Count);
  277.         foreach (int i in pieceIndexes.Concat(EmptyCellIndex))
  278.           if (!movedPieceIndexes.Contains(i))
  279.             emptyCellsAfterMove.Add(i);
  280.  
  281.         var moveDone = new KlotskiMove { EmptyCellToCover = index, Direction = direction };
  282.         yield return new KlotskiPuzzleState(this, moveDone, new KlotskiGridState(GridState.ColumnCount, cellStatesAfterMove), emptyCellsAfterMove);
  283.       }
  284.     }
  285.   }
  286. }
  287.  
  288.  
  289. public class Problem
  290. {
  291.  
  292.   HashSet<KlotskiGridState> ObservedGridStates { get; }
  293.  
  294.   static KlotskiPuzzleState startingState = new KlotskiPuzzleState(
  295.     "BAAAC",
  296.     "BBDCC",
  297.     "EEDFF",
  298.     "GGHII",
  299.     "JJHKK",
  300.     "L   M");
  301.  
  302.  
  303.   static public void Main()
  304.   {
  305.     var depthDict = new Dictionary<KlotskiGridState, int>() { { startingState.GridState, 0 } };
  306.  
  307.     Queue<KlotskiPuzzleState> statesToConsider = new Queue<KlotskiPuzzleState>();
  308.     statesToConsider.Enqueue(startingState);
  309.  
  310.     int lastDepthSeen = 0;
  311.  
  312.     while (statesToConsider.Count > 0)
  313.     {
  314.       var currentState = statesToConsider.Dequeue();
  315.       if (currentState.MoveCount > lastDepthSeen)
  316.       {
  317.         lastDepthSeen = currentState.MoveCount;
  318.         Console.WriteLine($"Processing move {lastDepthSeen}... {statesToConsider.Count} states in queue, {depthDict.Count} possible states reached");
  319.       }
  320.       foreach (var state in currentState.GetStatesAfterValidMoves())
  321.       {
  322.         if (depthDict.TryGetValue(state.GridState, out int lastDepth))
  323.         {
  324.           // Console.WriteLine($"Duplicate of a state reached in {lastDepth} moves");
  325.         }
  326.         else if(state.GridState.CellStates[6 * state.GridState.ColumnCount + 2] == (KlotskiCellState.ConnectedLeft | KlotskiCellState.ConnectedRight))
  327.         {
  328.           for (var printState = state; printState != null; printState = printState.Parent)
  329.           {
  330.             Console.WriteLine($"After move {printState.MoveCount}: {printState.MoveFromParent.Direction} to {printState.MoveFromParent.EmptyCellToCover}:");
  331.             Console.WriteLine(printState.GridState);
  332.           }
  333.           return;
  334.         }
  335.         else
  336.         {
  337.           depthDict[state.GridState] = state.MoveCount;
  338.           statesToConsider.Enqueue(state);
  339.         }
  340.       }
  341.     }
  342.   }
  343. }
RAW Paste Data Copied