#StackBounty: #c# #performance #algorithm #recursion #combinatorics Best way to performance permutations

Bounty: 50

enter image description here

This has been my white whale for a while, the idea is convert all the symbols to the goal symbol using all the pieces.

I did an algorithm like 5 years ago (now is lost) and reach lvl 48 but got stuck here and drop. After I watch The Imitation Game and see how Turin solve enigma using a Heil Hitler to reduce the space search I decide give it a second try.

I try solve row by row. First you have to see how many flips each row need and then found a set of pieces with enough squares to flip all symbols or a multiple of the symbol cycle (in this case 3)

In the orginal version when I found a set I try to place the pieces on each column to see if can solve the row if that happen then can go to the next row. Now I dont try to solve it but directly try to go to the next row with less pieces. Not sure what is the best aproach.

With those 18 pieces you 6.5E25 combinations to place them on the board (consider engima machine has 15E18). But if you try to solve only the flips on the first row you have 2^18 = 262k set combinations, of those only 84k has the correct amount of flips. That is the biggest prunning I could found.

My hope is there is some algorithm to allow me reduce even more the search space or some optimization I can use to improve the search speed.

Shape

[Serializable()]
public class Shape : ICloneable
{
    public int Height { get; set; }
    public int Width { get; set; } // I will use Width to test by column later
    public int[] Changes { get; set; } // How many flips 
    public long Id { get; set; }
    public int RowPosition { get; set; } // In what Row Im using the piece
    public int MaxRow { get; set; } // What is the last row where can fit 

    public Shape(double id, int[] piece, int height)
    {
        Changes = piece;
        Height = height;
        Id = (long)id;
        RowPosition = -1;
        MaxRow = 8 - height;
    }

    public object Clone()
    {
        return this.MemberwiseClone();
    }
}

Solution

[Serializable()]
public class Solution : ICloneable
{
    private readonly int[] Game = new int[8] { 3, 8, 6, 7, 7, 8, 9, 7 };
    public List<Shape> Pieces { get; set; }
    public long Id { get; set; }

    public Solution()
    {
        Pieces = new List<Shape>();
    }

    // Return a deep clone of an object of type T.
    public object DeepClone()
    {
        using (MemoryStream memory_stream = new MemoryStream())
        {
            // Serialize the object into the memory stream.
            BinaryFormatter formatter = new BinaryFormatter();
            formatter.Serialize(memory_stream, this);

            // Rewind the stream and use it to create a new object.
            memory_stream.Position = 0;
            return (Solution)formatter.Deserialize(memory_stream);
        }
    }

    public bool TestRowFlips(int row)
    {
        int[] Changes = new int[8] { 0, 0, 0, 0, 0, 0, 0, 0 };

        foreach (Shape p in Pieces)
        {
            for (int i = 0; i < p.Height; i++)
            {
                Changes[ i + p.RowPosition ] += p.Changes[i];
            }
        }

        if ((Changes[row] - Game[row]) % 3 == 0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    public bool ExistPiece(long id)
    {
        return Pieces.Any(x => x.Id == id);
    }
}

Recursive

class Recursive
{
    private List<Shape> Pieces { get; set; }

    public void Setup()
    {
        Pieces = new List<Shape>
        {
            new Shape(Math.Pow( 2, 0 ), new int[5] { 2, 1, 2, 0, 0 }, 3),
            new Shape(Math.Pow( 2, 1 ), new int[5] { 2, 1, 0, 0, 0 }, 2),
            new Shape(Math.Pow( 2, 2 ), new int[5] { 2, 2, 2, 0, 0 }, 3),

            new Shape(Math.Pow( 2, 3 ), new int[5] { 3, 1, 3, 0, 0 }, 3),
            new Shape(Math.Pow( 2, 4 ), new int[5] { 4, 3, 3, 3, 0 }, 4),
            new Shape(Math.Pow( 2, 5 ), new int[5] { 3, 0, 0, 0, 0 }, 1),

            new Shape(Math.Pow( 2, 6 ), new int[5] { 3, 1, 3, 0, 0 }, 3),
            new Shape(Math.Pow( 2, 7 ), new int[5] { 3, 4, 1, 2, 2 }, 5),
            new Shape(Math.Pow( 2, 8 ), new int[5] { 1, 0, 0, 0, 0 }, 1),

            new Shape(Math.Pow( 2, 9 ), new int[5] { 2, 2, 2, 0, 0 }, 3),
            new Shape(Math.Pow( 2, 10 ), new int[5] { 2, 3, 4, 0, 0 }, 3),
            new Shape(Math.Pow( 2, 11 ), new int[5] { 1, 3, 1, 3, 2 }, 5),

            new Shape(Math.Pow( 2, 12 ), new int[5] { 1, 2, 2, 0, 0 }, 3),
            new Shape(Math.Pow( 2, 13 ), new int[5] { 2, 4, 1, 1, 0 }, 4),
            new Shape(Math.Pow( 2, 14 ), new int[5] { 1, 2, 1, 0, 0 }, 3),

            new Shape(Math.Pow( 2, 15 ), new int[5] { 1, 1, 3, 0, 0 }, 3),
            new Shape(Math.Pow( 2, 16 ), new int[5] { 3, 2, 3, 1, 0 }, 4),
            new Shape(Math.Pow( 2, 17 ), new int[5] { 1, 3, 2, 2, 0 }, 4)
        };
        // try to solve first row
        for (long PieceSet = 0; PieceSet < Math.Pow(2, 18); PieceSet++)
        {
            Solution solution = new Solution();
            foreach (Shape piece in Pieces)
            {
                if ((piece.Id & PieceSet) > 0)
                {
                    Shape p = (Shape)piece.Clone();
                    p.RowPosition = 0;
                    solution.Pieces.Add(p);
                }
            }

            if (solution.TestRowFlips(0))
            {
                solution.Id = PieceSet;
                Solve_Row(solution, 1);
            }
        }
    }

    public bool Solve_Row(Solution solution, int rowToSolve)
    {
        // Check the unused pieces to see if are too big to be used on any other row.
        if (Pieces.Any(x => (x.Id & solution.Id) == 0 && x.MaxRow < rowToSolve))
        {
            return false;
        }

        for (long pieceSet = 0; pieceSet < Math.Pow(2, 18); pieceSet++)
        {          
            if ((pieceSet & solution.Id) == 0)
            {
                Solution newSolution = (Solution)solution.DeepClone();

                foreach (Shape piece in Pieces.Where(x => (x.Id & pieceSet) > 0)
                                              .ToList())
                {
                    Shape p = (Shape)piece.Clone();
                    p.RowPosition = rowToSolve;
                    newSolution.Pieces.Add(p);
                }

                newSolution.Id = newSolution.Id | pieceSet;

                if (newSolution.Id == Pieces.Sum(x => x.Id))
                {
                    Debug.Print("Found a Solution");
                    return true;
                }

                if (newSolution.TestRowFlips(rowToSolve))
                {
                    Solve_Row(newSolution, rowToSolve + 1);
                }
            }
        }
        return false;
    }


}


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.