Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Linq;
- using System.Text;
- using System.Collections.Generic;
- using Dirichlet.Numerics;
- // SquareSwap4.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...
- // compile with command line
- // csc SquareSwap4.cs UInt128.cs /r:System.Numerics.dll
- // you will need UInt128.cs from https://github.com/ricksladkey/dirichlet-numerics
- // see https://stackoverflow.com/questions/227731/int128-in-net
- 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; }
- 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 class PuzzleState
- {
- private 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))
- {
- }
- public PuzzleState(CompressedPuzzleState compressed, GridState gridState)
- : this(gridState, compressed.MovesDone)
- { }
- // 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 < fromColLimit; 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));
- }
- int toNextCol = (fromCol + 1) % GridState.ColumnCount;
- 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();
- // thoretically, we only "need" a 96 bit integer, but code for that seems unlikely to be much of an improvement...
- // limit is based on 16! * 17!
- UInt128 _compressedData;
- 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;
- UInt128 multiplier = 1;
- _compressedData = 0;
- List<int> possiblePositions = Enumerable.Range(0, 16).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)}]");
- _compressedData += multiplier * (uint)posIndex;
- multiplier *= (uint)possiblePositions.Count;
- possiblePositions.RemoveAt(posIndex);
- _compressedData += multiplier * (uint)cellStates[pos].MovesLeft;
- multiplier *= i + 1;
- //Console.WriteLine($"Compression diagnostic: i={i}, pos={pos} index {posIndex}, moves = {cellStates[pos].MovesLeft}, multiplier = {multiplier}, data = {_compressedData}");
- }
- }
- public GridState GetGridState()
- {
- var cellStates = new CellState[16];
- UInt128 multiplier = 1;
- List<int> possiblePositions = Enumerable.Range(0, 16).ToList();
- for (byte i = 1; i <= 16; i++)
- {
- UInt128 nextMultiplier = multiplier * (uint)possiblePositions.Count;
- int posIndex = (int)(_compressedData % nextMultiplier / multiplier);
- int pos = possiblePositions[posIndex];
- possiblePositions.RemoveAt(posIndex);
- multiplier = nextMultiplier;
- nextMultiplier *= (uint)i + 1;
- byte movesLeft = (byte)(_compressedData % nextMultiplier / multiplier);
- multiplier = nextMultiplier;
- 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 base.Equals(obj) || obj is CompressedGridState4 other && Equals(other) || obj is GridState otherExpanded && GetGridState().Equals(otherExpanded);
- }
- public bool Equals(CompressedGridState4 other)
- {
- return _compressedData == other._compressedData;
- }
- public override int GetHashCode()
- {
- return _compressedData.GetHashCode();
- }
- }
- public struct CompressedPuzzleState
- {
- public static implicit operator CompressedPuzzleState(PuzzleState source) => new CompressedPuzzleState(source);
- public CompressedPuzzleState(PuzzleState source)
- {
- MovesDone = source.MovesDone;
- }
- public PuzzleState GetPuzzleState(GridState gridState) => new PuzzleState(this, gridState) { AllowWrapAround = false };
- // currently not (further) compressed. That can be next step if existing changes are insufficient.
- public SwapInfo[] MovesDone { get; }
- }
- 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 Dictionary<CompressedGridState4, CompressedPuzzleState>()).ToArray();
- workingSets[startingState.GridState.TotalMovesLeft].Add(startingState.GridState, startingState);
- 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], pair =>
- {
- GridState gridState = pair.Key; // implicit conversion to decompress
- var puzzleState = pair.Value.GetPuzzleState(gridState);
- // 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().Select(s => $"R{s.rowFrom + 1}C{s.colFrom + 1}<>R{s.rowTo + 1}C{s.colTo + 1}"))}");
- 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???!");
- CompressedGridState4 nextGridStateCompressed = nextState.GridState;
- lock (workingSets[movesLeft])
- {
- if (workingSets[movesLeft].TryGetValue(nextGridStateCompressed, out var firstEquivalentState))
- {
- //Console.WriteLine("Duplicate found!");
- }
- else // implicit conversion to compressed data.
- workingSets[movesLeft].Add(nextGridStateCompressed, nextState);
- }
- }
- });
- // allow dictionaries of compresed state to be reclaimed by garbage collector
- workingSets[i] = null;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement