Project Euler

(C#) Project Euler Utility Functions

steloflute 2012. 5. 27. 23:59


namespace etc {
    static class Etc {
        static BigInteger combination(int n, int r) {
            return (factorial(n) / factorial(r) / factorial(n - r));
        }

        static Dictionary<BigInteger, int> f5Cache = new Dictionary<BigInteger, int>();
        static int f5(BigInteger n) {
            if (f5Cache.ContainsKey(n)) return f5Cache[n];
            int r = 0;
            for (int x = (int)Double.Parse(BigInteger.Log(n, 5).ToString()); x > 0; x--) {
                if (n % BigInteger.Pow(5, x) == 0) { r = x; break; }
            }
            f5Cache.Add(n, r);
            return r;
        }

        static Dictionary<BigInteger, BigInteger> fCache = new Dictionary<BigInteger, BigInteger>();
        static BigInteger factorial(this BigInteger n) {
            if (fCache.ContainsKey(n)) return fCache[n];
            BigInteger f = 1;
            for (BigInteger i = 2; i <= n; i++) {
                f *= i;
                if (!fCache.ContainsKey(i)) {
                    fCache[i] = f;
                }
            }
            return f;
        }

        static int t5(BigInteger n) {
            int count = 0;
            for (BigInteger i = 1; i <= n; i++) {
                if (f5((2 * i - 1).factorial()) < 2 * f5(i.factorial())) count++;
                //Console.WriteLine(i);
            }
            return count;
        }

        static void problem383() {
            Console.WriteLine(f5(625000));
            Console.WriteLine(t5(1000));
            Console.WriteLine(t5(1000000000));
        }

        static HashSet<int> primeFactors(int num) {
            var r = new HashSet<int>();
            var n = num;
            for (var pf = 2; pf * pf <= num; pf++) {
                if (n % pf == 0) {
                    r.Add(pf);
                    n /= pf;
                    while (n % pf == 0) n /= pf;
                }
            }
            if (n > 1) r.Add(n);
            return r;
        }

        static bool isTriangle(long value) {
            var index = (-1 + Math.Sqrt(1 + 8 * value)) / 2;
            return index == Math.Floor(index);
        }

        static bool isPentagonal(long value) {
            var index = (Math.Sqrt(24 * value + 1) + 1) / 6;
            return index == Math.Floor(index);
        }

        static int wordValue(string s) {
            return s.Select(x => x - 'A' + 1).Sum();
        }

        static string tryMakePandigital(int n) {
            string r = "";
            for (int i = 1; ; i++) {
                r += (n * i).ToString();
                if (i > 1 && r.Length >= 9) break;
            }
            return r;
        }

        static bool isPandigital(string s) {
            var hs = new HashSet<char>(s);
            if (hs.Contains('0')) return false;
            return hs.Count == s.Length;
        }

        static int pandigital(int n) {
            string s = tryMakePandigital(n);
            if (isPandigital(s)) {
                return Convert.ToInt32(s);
            } else
                return 0;
        }

        static bool isPalindrome<T>(T value) {
            var str = value.ToString();
            var to = str.Length / 2;
            for (var i = 0; i <= to; i++) {
                if (str[i] != str[str.Length - 1 - i]) return false;
            }
            return true;
        }

        static bool isPrime(int value) {
            if (value <= 1) return false;
            for (int i = 2; i * i <= value; i++) {
                if (value % i == 0) return false;
            }
            return true;
        }

        /// <summary>
        /// Returns primes under limit using sieve.
        /// </summary>
        /// <param name="limit">An integer to limit.</param>
        /// <returns>Primes under limit.</returns>
        static HashSet<int> primesUnder(int limit) {
            var p = new bool[limit];
            if (limit >= 3) p[2] = true;
            for (int i = 3; i < limit; i += 2) p[i] = true;
            for (int i = 3; i * i < limit; i += 2) {
                if (!p[i]) continue;
                for (int j = i + i; j < limit; j += i)
                    p[j] = false;
            }
            var r = new HashSet<int>();
            for (int i = 2; i < limit; i++)
                if (p[i]) r.Add(i);
            return r;
        }

        static string rotateLeft(string value) {
            if (value.Length <= 1) return value;
            return value.Substring(1) + value[0];
        }

        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);
                }
            }
        }
    }
}

 

'Project Euler' 카테고리의 다른 글

Project Euler Problem 55  (0) 2012.05.28
Project Euler Problem 53  (0) 2012.05.28
Project Euler Problem 3  (0) 2012.05.27
Project Euler Problem 2  (0) 2012.05.27
Project Euler Problem 1  (0) 2012.05.27