jigsaw algorithm - June 20, 2018

jigsawAlgorithm.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace JigSawProblem
{
    class Program
    {
        class Edge
        {
            // it should be defined as two points connecting to each other
        }

        class Piece
        {
            public int Index { get; set; }
            public Edge[] Edges;

            public static bool Match(Edge edge1, Edge edge2)
            {
                // the api will return if two edges are matched or not. 
                return true;
            }
        }

        /// <summary>
        /// Design the api to solve the pieces, so the output should be
        /// the list of edge id. 
        /// </summary>
        /// <param name="pieces"></param>
        /// <param name="topLeft"></param>
        public static IList<int> Solve(HashSet<Piece> pieces, Piece topLeft)
        {
            var preprocessed = preprocessingAllPieces_AtMostFourNeighbors(pieces);
            var lookup = buildPieces(pieces);

            var sorted = new List<int>(); 
            
            // process the first row 
            var current = topLeft;
            while (current != null)
            {
                var neighbors = preprocessed[current.Index];
                sorted.Add(current.Index);
                current = lookup[neighbors[1]]; // 0, 1, 2, 3, check right neighbor, left, top, right, bottom clockwise 
            }
            // continue to second row ...

            return sorted; 
        }

        private static Dictionary<int, Piece> buildPieces(HashSet<Piece> pieces)
        {
            var lookup = new Dictionary<int, Piece>(); 

            foreach (var item in pieces)
            {
                lookup.Add(item.Index, item); 
            }

            return lookup; 
        }

        /// <summary>
        /// IDictionary<string, int[]>
        /// key - index1 + ":" + index2, assuming that index1 < index2
        /// total complexity is O(n * n) , n is total pieces in the hashset<Edge>
        /// int[]
        /// overlap - how many of them, same index -> no check
        /// different index, and then figure out position
        /// 0 - no overlap
        /// 1 - 
        /// 2 - 
        /// 3 - 
        /// 4 - 
        /// </summary>
        private static IDictionary<string, int[]> preprocessingAllPieces(HashSet<Piece> pieces)
        {
            var pair = new Dictionary<string, int[]>();

            var toArray = pieces.ToArray();
            var length = toArray.Length;

            for (int index = 0; index < toArray.Length; index++)
            {
                for (int index2 = index + 1; index2 < length; index2++)
                {
                    var piece1 = toArray[index];
                    var piece2 = toArray[index2];

                    var key = "";
                    if (piece1.Index < piece2.Index)
                        key = piece1.Index + ":" + piece2.Index;

                    // insert into dictionary ...
                }
            }

            return pair; 
        }

        /// <summary>
        /// preprocess all pieces, for each piece, there is an entry in dictionary by looking up 
        /// piece ID, and the value entry is a dictionary, for each piece, there is value to explain
        /// how two pieces are matched. The position can be next to each other, one is left or right, top, bottom 
        /// or no overlap
        /// Time complexity: 
        /// n - hashset size
        /// algorithm time complexity will be O(n^2) for preprocessing 
        /// </summary>
        /// <param name="pieces"></param>
        /// <returns></returns>
        public static IDictionary<int, IDictionary<int, int>> preprocessingAllPieces_QuickFind(HashSet<Piece> pieces)
        {
            var pair = new Dictionary<int, IDictionary<int, int>>();

            //...
            return pair; 
        }

        /// <summary>
        /// preprocess all pieces, for each piece, there is at most 4 pieces which are next to each other. 
        /// We only need to save those four pieces.
        /// 0, 1, 2, 3
        /// 0 - left
        /// 1 - right
        /// 2 - top
        /// 3 - down
        /// piece id is saved in the array
        /// 
        /// Time complexity: 
        /// n - hashset size
        /// algorithm time complexity will be O(n^2) for preprocessing 
        /// </summary>
        /// <param name="pieces"></param>
        /// <returns></returns>
        public static IDictionary<int, int[]> preprocessingAllPieces_AtMostFourNeighbors(HashSet<Piece> pieces)
        {
            var pair = new Dictionary<int, int[]>();

            // the code please refer to the function
            // preprocessingAllPieces()

            return pair;
        }

        /// <summary>
        /// time complexity: 
        /// At most 16 calls to Piece.Match function
        /// </summary>
        /// <param name="piece1"></param>
        /// <param name="piece2"></param>
        /// <returns></returns>
        private static int checkTwoPieces(Piece piece1, Piece piece2)
        {
            int count = 0; 
            foreach (var edge in piece1.Edges)
            {
                foreach (var edge2 in piece2.Edges)
                {
                    if(Piece.Match(edge, edge2))
                        count++; 
                }
            }

            return count; 
        }

        static void Main(string[] args)
        {
        }
    }
}