using System;

using System.Collections.Generic;

using System.Linq;

public static class Program

{

    static IEnumerable<IEnumerable<T>> GetKCombsWithRept<T>(IEnumerable<T> list, int length) where T : IComparable

    {

        if (length == 1) return list.Select(t => new T[] { t });

        return GetKCombsWithRept(list, length - 1)

            .SelectMany(t => list.Where(o => o.CompareTo(t.Last()) >= 0), 

                (t1, t2) => t1.Concat(new T[] { t2 }));

    }

    public static void Main()

    {

        Console.WriteLine("Hello World");

        //ReverseHash(362899, 3);

        //ReverseHash(680131659347, 7);

        //ReverseHash(930846109532517, 9);

        int length = 3;

        double lookingFor = 362899;

        bool gotit = false;

        _options = new List<string>();

        int[] lettersArray =  new int[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};

        //printCombination(lettersArray, 15, length);

        var values1 = new[] { 1, 2, 3, 4, 5 };

​

        foreach (var permutation in GetPermutations(values1))

        {

        //  Console.WriteLine(string.Join(", ", permutation));

        }

        var combos = GetKCombsWithRept<int>(lettersArray, length);

        foreach(var combo in combos){

            string option = FormatStringFromLetterPositions(combo.ToArray());

            //Console.WriteLine("option to be permutated " + option);

            _permutations = new List<string>();

            char[] charArray = option.ToCharArray();

            foreach (var permutation in GetPermutations(combo))

            {

                double sum = 0;

                string word = String.Empty;

                for(int i = 0; i < permutation.Count(); i++){

                    word +=Char.ToString(_letters[permutation.ElementAt(i)]);

                    sum += GetHashOfLettAtPostion(word, i, length);

                }

                Console.WriteLine(string.Join(", ", permutation) + " " + word + " sum " + sum);

                if(sum == lookingFor){

                    Console.WriteLine("Got it: " + permutation + " " + sum);

                    gotit = true;

                    break;

                }

            }

            foreach(string permutation in _permutations)

            {

            }

            if(gotit)

                break;

        }

        return;

        foreach(var option in _options){

            Console.WriteLine("option to be permutated " + option);

            _permutations = new List<string>();

            char[] charArry = option.ToCharArray();

            permute(charArry, 0, 2);

            foreach(string permutation in _permutations)

            {

                double sum = 0;

                for(int i = 0; i < permutation.Length; i++){

                    sum += GetHashOfLettAtPostion(permutation.Substring(i, 1), i, length);

                }

                Console.WriteLine("perm " + permutation + " sum " + sum);

                if(sum == lookingFor){

                    Console.WriteLine("Got it: " + permutation + " " + sum);

                    gotit = true;

                    break;

                }

            }

            if(gotit)

                break;

        }

        return;

        // Pick a number:

        int num = 5;

        Console.WriteLine("Number is: " + num);

        // Add the number to itself 3 times

        int result = 5 * 3;

        Console.WriteLine("Add number to itself 3 times: " + result);

        // Multiple result by 37

        int resultTimes37 = result * 37;

        Console.WriteLine("Result mutiplied by 37: " + resultTimes37);

        Console.WriteLine("Woah! The answer is original number repeated 3 times");

        Console.WriteLine(" 5 + 5 + 5 multiplied by 37 = 555");

        Console.WriteLine("Hello World");

        _positions = new int[3];

        _values = new double[3];

        ReverseHash(362899, 3);

        _positions = new int[7];

        _values = new double[7];

        //ReverseHash(680131659347, 7);

        _positions = new int[9];

        _values = new double[9];

        //ReverseHash(930846109532517, 9);

    }

    static List<string> _permutations;

    static void permute(char[] arry, int i, int n)

    {

        int j;

        if (i==n)

        {

            string str = new string(arry);

            //Console.WriteLine("perm " + str);

            _permutations.Add(str);

        }

        else

        {

            for(j = i; j <=n; j++)

            {

                swap(ref arry[i],ref arry[j]);

                permute(arry,i+1,n);

                swap(ref arry[i], ref arry[j]); //backtrack

            }

        }

    }

    static void swap(ref char a, ref char b)

    {

        char tmp;

        tmp = a;

        a=b;

        b = tmp;

    }

    const string _letters = "acdegilmnoprstuw";

    public static int[] _positions = new int[3];

    public static double[] _values = new double[3];

    public static Something Y1(Func<Something, Something> f){

        return (a, b) => f(Y1(f)) (a, b);

    }

    public static void ReverseHash(double answer, int length)

    {

        Y1(Answer)(answer, 0);

        //Something f = ReverseHash;

        //f(answer, arrayIndexes, values, 0);

    }

    // Answer

    public static Something Answer(Something f)

    {

        Something del = delegate(double hashedString, int counter)

        {

            int lenOfWord = _positions.Length;

            for (_positions[counter] = 0; _positions[counter] < _letters.Length; _positions[counter]++)

            {

                _values[counter] = _positions[counter] * Math.Pow(37, lenOfWord - 1 - counter);

                // Console.WriteLine("counter " + counter);

                // Console.WriteLine("letter position " + positions[counter]);

                if (counter == 0)

                {

                    _values[counter] += (7 * Math.Pow(37, lenOfWord));

                }

                double sumOfValues = 0;

                foreach (var val in _values)

                {

                    sumOfValues += val;

                }

                if (sumOfValues == hashedString)

                {

                    string unhashedString = FormatStringFromLetterPositions(_positions);

                    Console.WriteLine("Answer is " + unhashedString);

                    break;

                }

                else if (counter < lenOfWord - 1)

                {

                    f(hashedString, counter + 1);

                }

            }

        }

​

        ;

        return del;

    }

​

    public delegate void Something(double hashResult, int counter);

    public static string FormatStringFromLetterPositions(int[] positions)

    {

        string resultStr = "";

        foreach (int i in positions)

        {

            resultStr += Char.ToString(_letters[i]);

        }

​

        return resultStr;

    }

    /* NOTHING WORKS, TRY SOMETHING ELSE */

    public class DTO{

        public int letter;

        public double hashedLetterAtPosition;

        public DTO (){

        }

    }

    private static double GetHashOfLettAtPostion(string letter, int position, int length){

        double hashedLetterAtPosition = _letters.IndexOf(letter) * Math.Pow(37, length - 1 - position);

                // Console.WriteLine("counter " + counter);

                // Console.WriteLine("letter position " + positions[counter]);

                if (position == 0)

                {

                    hashedLetterAtPosition += (7 * Math.Pow(37, length));

                }

        return hashedLetterAtPosition;

    }

    public static void TryAgain(double answer, int length){

        Dictionary<int, List<DTO>> positions = new Dictionary<int, List<DTO>>();

        for(int i = 0; i< length; i++)

        {

            for (int letter = 0; letter < _letters.Length; letter++)

            {

                double hashedLetterAtPosition = letter * Math.Pow(37, length - 1 - i);

                // Console.WriteLine("counter " + counter);

                // Console.WriteLine("letter position " + positions[counter]);

                if (i == 0)

                {

                    hashedLetterAtPosition += (7 * Math.Pow(37, length));

                }

                var dto = new DTO{

                    letter = letter,

                    hashedLetterAtPosition = hashedLetterAtPosition

                };

                if(!positions.ContainsKey(i)){

                    positions[i] = new List<DTO>();

                }

                List<DTO> list = positions[i];

                list.Add(dto);

                positions[i] = list;

            }   

        }

    }

                    // The main function that prints all combinations of size r

    // in arr[] of size n. This function mainly uses combinationUtil()

    static void printCombination(int[] arr, int n, int r)

    {

        // A temporary array to store all combination one by one

        int[] data=new int[r];

        // Print all combination using temprary array 'data[]'

        combinationUtil(arr, n, r, 0, data, 0);

    }

    public static List<string> _options;

     /* arr[]  ---> Input Array

    data[] ---> Temporary array to store current combination

    start & end ---> Staring and Ending indexes in arr[]

    index  ---> Current index in data[]

    r ---> Size of a combination to be printed */

    static void combinationUtil(int[] arr, int n, int r, int index,

                                int[] data, int i)

    {

        // Current combination is ready to be printed, print it

        if (index == r)

        {

            string sum = "";

            for (int j=0; j<r; j++) 

            {  

                //Console.WriteLine(data[j] + " " + _letters[data[j]]);

                sum += _letters[data[j]];

            }

            //Console.WriteLine("sum: " + sum);

            _options.Add(sum);

            //Console.WriteLine();

            return;

        }

        // When no more elements are there to put in data[]

        if (i >= n)

        return;

        // current is included, put next at next location

        data[index] = arr[i];

        combinationUtil(arr, n, r, index+1, data, i+1);

        // current is excluded, replace it with next (Note that

        // i+1 is passed, but index is not changed)

        combinationUtil(arr, n, r, index, data, i+1);

    }

    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> enumerable)

    {

        var array = enumerable as T[] ?? enumerable.ToArray();

​

        var factorials = Enumerable.Range(0, array.Length + 1)

            .Select(Factorial)

            .ToArray();

​

        for (var i = 0L; i < factorials[array.Length]; i++)

        {

            var sequence = GenerateSequence(i, array.Length - 1, factorials);

​

            yield return GeneratePermutation(array, sequence);

        }

    }

​

    private static IEnumerable<T> GeneratePermutation<T>(T[] array, IReadOnlyList<int> sequence)

    {

        var clone = (T[]) array.Clone();

​

        for (int i = 0; i < clone.Length - 1; i++)

        {

            Swap(ref clone[i], ref clone[i + sequence[i]]);

        }

​

        return clone;

    }

​

    private static int[] GenerateSequence(long number, int size, IReadOnlyList<long> factorials)

    {

        var sequence = new int[size];

​

        for (var j = 0; j < sequence.Length; j++)

        {

            var facto = factorials[sequence.Length - j];

​

            sequence[j] = (int)(number / facto);

            number = (int)(number % facto);

        }

​

        return sequence;

    }

​

    static void Swap<T>(ref T a, ref T b)

    {

        T temp = a;

        a = b;

        b = temp;

    }

​

    private static long Factorial(int n)

    {

        long result = n;

​

        for (int i = 1; i < n; i++)

        {

            result = result * i;

        }

​

        return result;

    }

}