using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace OEIS_Prime_Factors
{
    public static class A3242xx
    {
        public static bool IsA324260(long n, long[] distinctFactors)
        {
            // subsequence of A324257 without multiplicity of each distinct factor
            if (!IsA324257(n, distinctFactors))
                return false;

            string nStr = n.ToString();
            bool[] pUsed = new bool[distinctFactors.Length];
            int pCount = 0;
            bool[] digitUsed = new bool[nStr.Length];

            //
            // first pass handle factors with no choice of location to steer the factors with
            // multiple options into the best slot
            for (int i = 0; i < distinctFactors.Length; i++)
            {
                if (pUsed[i])
                    continue;

                long p = distinctFactors[i];
                int nCount = Regex.Matches(nStr, p.ToString()).Count;

                if (nCount == 1)
                {
                    int index = nStr.IndexOf(p.ToString());
                    for (int offset = 0; offset < p.ToString().Length; offset++)
                    {
                        digitUsed[index + offset] = true;
                    }

                    pUsed[i] = true;
                    pCount++;
                }
            }

            // check if we're done
            bool stat = true;
            foreach (bool b in digitUsed)
            {
                if (!b)
                {
                    stat = false;
                    break;
                }
            }

            if (stat == true)
                return true;

            //
            // second pass add remaining factors in reverse order of size to minimize collisions
            //
            // note this could theoretically give false negatives if the factors are overlapping just so.
            // Manual checking of all A324257 terms indicates that this doesn't happen for n < 2.5x10^10.
            // Importantly this will never give a false positive so no erroneous terms can appear in the sequence.

            for (int i = distinctFactors.Length - 1; i >= 0; i--)
            {
                if (pUsed[i])
                    continue;

                long p = distinctFactors[i];

                int index = -1;
                bool stop = false;
                while (!stop && (index = nStr.IndexOf(p.ToString(), index + 1)) != -1)
                {
                    for (int offsetUnused = 0; offsetUnused < p.ToString().Length; offsetUnused++)
                    {
                        if (!digitUsed[index + offsetUnused])
                        {
                            // unused digit at this location place it here
                            for (int offsetPlace = 0; offsetPlace < p.ToString().Length; offsetPlace++)
                            {
                                digitUsed[index + offsetPlace] = true;
                            }

                            pUsed[i] = true;
                            pCount++;
                            stop = true;
                            break;
                        }
                    }
                }
            }

            stat = true;
            foreach (bool b in digitUsed)
            {
                if (!b)
                {
                    stat = false;
                    break;
                }
            }

            return stat;
        }

        public static bool IsA324257(long n, long[] distinctFactors)
        {
            bool stat = true;

            string nStr = n.ToString();
            bool[] digitUsed = new bool[nStr.Length];

            foreach (long p in distinctFactors)
            {
                if (!nStr.Contains(p.ToString()))
                {
                    // n doesn't contain this factor
                    stat = false;
                    break;
                }
                else
                {
                    // all digits in n need to be used
                    int index = -1;
                    while ((index = nStr.IndexOf(p.ToString(), index + 1)) > -1)
                    {
                        for (int offset = 0; offset < p.ToString().Length; offset++)
                        {
                            digitUsed[index + offset] = true;
                        }
                    }

                }
            }

            foreach (bool b in digitUsed)
            {
                if (!b)
                {
                    stat = false;
                    break;
                }
            }

            return stat;
        }

    }
}