Problem 32 - Pandigital products

Problem: 

Please find the problem here.

Solution:

My current solution is kind of slow - it runs through all permutations and all possible splits to check for the product formula, and when it does accumulate the results, it is that simple.

It would be great if we could speed this up using some more constraints, but for now, this is good enough to produce and answer.

It would be an interesting detour to discuss the permutation generating algorithm. In some sense it is simple, pick the head, recursively compute the permutation of remaining elements, and concat with the head. Note that we could have been faster if we optimize the permutation method to reuse the same buffer instead of creating new list for each recursive result!

Code:

namespace Euler
{
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Numerics;

    internal static partial class Program
    {
        public static IEnumerable<IEnumerable<T>> Permutations<T>(IEnumerable<T> available)
        {
            List<T> availableList = available.ToList();
            return Permutations(availableList.Select(t => Pair<bool, T>.Create(true, t)).ToArray(), availableList.Count);
        }

        private static IEnumerable<IEnumerable<T>> Permutations<T>(Pair<bool, T>[] available, int count)
        {
            if (count == 0)
            {
                yield return new List<T> { };
            }

            for (int i = 0; i < available.Length; i++)
            {
                if (available[i].Item1)
                {
                    available[i].Item1 = false;
                    foreach (IEnumerable<T> recursiveResult in Permutations(available, count - 1))
                    {
                        yield return new List<T> { available[i].Item2 }.Concat(recursiveResult);
                    }

                    available[i].Item1 = true;
                }
            }
        }

        private class Pair<T, U>
        {
            public static Pair<T, U> Create(T item1, U item2)
            {
                return new Pair<T, U>(item1, item2);
            }

            private Pair(T item1, U item2)
            {
                this.Item1 = item1;
                this.Item2 = item2;
            }

            public T Item1 { get; set; }

            public U Item2 { get; set; }

        }

        public static void Problem032()
        {
            HashSet<int> results = new HashSet<int>();
            foreach (var permutation in Permutations(Enumerable.Range(1, 9).ToArray()))
            {
                // Break down the permutation into list of different partitions and check product formula
                for (int firstPart = 1; firstPart < 9; firstPart++)
                {
                    for (int secondPart = 1; secondPart < 9; secondPart++)
                    {
                        int thirdPart = 9 - firstPart - secondPart;
                        if (thirdPart > 0)
                        {
                            string permutationString = permutation.Aggregate("", (s, x) => s + x);
                            int firstPartValue = int.Parse(permutationString.Substring(0, firstPart));
                            int secondPartValue = int.Parse(permutationString.Substring(firstPart, secondPart));
                            int thirdPartValue = int.Parse(permutationString.Substring(9 - thirdPart));
                            if (firstPartValue == secondPartValue * thirdPartValue)
                            {
                                results.Add(firstPartValue);
                                //Console.WriteLine("{0} = {1} x {2}", firstPartValue, secondPartValue, thirdPartValue);
                            }
                        }
                    }
                }
            }
            Console.WriteLine(results.Aggregate((x, y) => x + y));
        }
    }
}

Problem 31 - Coin Sum

Problem:

Please find the problem here.

Solution:

It is easier to think when the number is smaller.

The number of ways to represent 15 using any number of coin is:

number of ways to represent 15 using coins (1, 2, 5) [by choosing using 0 10 coin]
+
number of ways to represent 5 using coins (1, 2, 5) [by choosing using 1 10 coin]

Similarly, the number of ways to represent 15 using coin (1, 2, 5) is:

number of ways to represent 15 using coins (1, 2, 5) [by choosing using 0 5 coin]
+
number of ways to represent 10 using coins (1, 2) [by choosing using 1 5 coin]
+
number of ways to represent 5 using coins (1, 2) [by choosing using 2 5 coin]
+
number of ways to represent 0 using coins (1, 2) [by choosing using 3 5 coin]

Of course the last term is 1, and now you get the idea how to use recursion to find the number of ways. The code do exactly that.

Code:

namespace Euler
{
    using System;
    using System.Linq;
    using System.Numerics;

    internal static partial class Program
    {
        public static void Problem031()
        {
            // Count the number of using different coins
            int[] coinValues = new int[] { 1, 2, 5, 10, 20, 50, 100, 200 };
            Console.WriteLine(Way(200, coinValues, coinValues.Length - 1));
        }

        private static int Way(int value, int[] coinValues, int maxIndex)
        {
            // This is special because we know it is 1, the value is can always be represented as sum of 1 in only 1 way.
            if (maxIndex == 0)
            {
                return 1;
            }
            int maxValue = coinValues[maxIndex];
            return Enumerable.Range(0, value / maxValue + 1).Select(t => Way(value - maxValue * t, coinValues, maxIndex - 1)).Aggregate((x, y) => x + y);
        }
    }
}