Project Euler Problem 32

Problem 32

06 December 2002

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

Answer: 45228

Permute and slice

C#

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using System.IO;

namespace Euler {
    class Program {
        static string arrayToString<T>(T[] array) {
            return array.Select(x => Convert.ToString(x)).Aggregate(string.Concat);
        }

        static HashSet<int> results = new HashSet<int>();
        static void permute(int[] n, int level = 0) {
            if (level > n.Length - 1) {
                //Console.Write(count + ": ");
                //foreach (var x in n) Console.Write(x);
                //Console.WriteLine();
                //Console.ReadKey();

                string strN = arrayToString(n);
                for (int i = 1; i <= n.Length - 2; i++) {
                    int a = Convert.ToInt32(strN.Substring(0, i));
                    for (int j = 1; j <= n.Length - i - 1; j++) {
                        int b = Convert.ToInt32(strN.Substring(i, j));
                        int c = Convert.ToInt32(strN.Substring(i + j));
                        if (a * b == c) {
                            Console.WriteLine("{0} {1} {2}", a, b, c);
                            results.Add(c);
                        }
                    }
                }
                return;
            }
            for (int i = 1; i <= 9; i++) {
                bool hasDuplicate = false;
                for (int priorLevel = 0; priorLevel < level; priorLevel++) {
                    if (i == n[priorLevel]) {
                        hasDuplicate = true;
                        break;
                    }
                }
                if (!hasDuplicate) {
                    n[level] = i;
                    permute(n, level + 1);
                }
            }
        }

        static void Main(string[] args) {
            int[] num = new int[9];
            foreach (var x in num) Console.Write(x);
            Console.WriteLine();

            permute(num);
            Console.WriteLine(results.Sum());
        }
    }
}