Options

Project Euler - Let's do Math/Programming Challenges

2»

Posts

  • Options
    JaninJanin Registered User regular
    edited January 2008
    The Python solution is instant on my computer. Some variety of Core2, but mere processor speed shouldn't make such a large difference.

    Janin on
    [SIGPIC][/SIGPIC]
  • Options
    jackaljackal Fuck Yes. That is an orderly anal warehouse. Registered User regular
    edited January 2008
    Janin wrote: »
    The Python solution is instant on my computer. Some variety of Core2, but mere processor speed shouldn't make such a large difference.

    Damn... back to the drawing board.

    Edit: Got it. I missed a step. Now it is instant. It takes between 20 and 60 milliseconds. The bad version was checking every single number. Yours technique runs 3x faster than mine. :oops:
    I forgot to multiply each item in the range by the increment variable.
    
            public static void Problem5Janin2()
            {
                var toCheck = Enumerable.Range(10, 10);
                int[] factors = { 2, 3, 5, 7, 11, 13, 17, 19 };
                Func<int, bool> divisible = x => toCheck.All(y => x % y == 0);
                var increment = factors.Aggregate((x, y) => x * y);
                var incrementMultiples = Enumerable.Range(1, int.MaxValue).Select(x => x * increment);
                Console.WriteLine(incrementMultiples.First(x => divisible(x)));
            }
    

    Here it is in LINQ. While I am digging the LINQ library, I am not digging the syntax. I might like it more if my brain was more poisoned by SQL.
            public static void Problem5JaninLinq()
            {
                var toCheck = Enumerable.Range(10, 10);
                int[] factors = { 2, 3, 5, 7, 11, 13, 17, 19 };
                Func<int, bool> divisible = x => toCheck.All(y => x % y == 0);
                var increment = factors.Aggregate((x, y) => x * y);
                Console.WriteLine((from incrementedNaturals in 
                                        from naturals in Enumerable.Range(1, int.MaxValue)
                                        select naturals * increment
                                        where divisible(incrementedNaturals)
                                            select incrementedNaturals).First());
            }
    

    jackal on
  • Options
    jackaljackal Fuck Yes. That is an orderly anal warehouse. Registered User regular
    edited January 2008
    Problem 27 is a doozie. Solved it in 8 lines, but it took about an hour to write. Execution takes around 35 seconds on my computer. Technically it is 11 lines total, but one of the functions is reused from earlier solutions.
    I tried caching the IsPrime function, but it only saved about 5 seconds, so I dumped it to save 2 lines (plus the 9 lines of the memoization function.
            public static void Problem27()
            {
                Func<int, int, int, long> evaluateFormula = (n, a, b) =>(long) n * n + a * n + b;
                var range = Enumerable.Range(-999, 1999);
                var wholeNumbers = Enumerable.Range(0, int.MaxValue - 1);
                var duples = range.SelectMany(x => range.Select(y => new { a = x, b = y }));
                var formulaAnswers = duples.Select(x =>  new { x.a, x.b, answers = wholeNumbers.Select(y => evaluateFormula(y, x.a, x.b) )});
                var formulasWithPrimeCounts = formulaAnswers.Select(x => new { x.a, x.b, primeCount = x.answers.TakeWhile(y => y.IsPrime()).Count() });
                var mostPrimes = formulasWithPrimeCounts.OrderByDescending(x => x.primeCount).First();
                Console.WriteLine(mostPrimes.a * mostPrimes.b);
            }
    
    
            public static bool IsPrime(this long value)
            {
                if (value <= 1) return false;
                int square = Convert.ToInt32((Math.Sqrt(value)));
                return !Enumerable.Range(2, square - 1).Any(x => value % x == 0);
            }
    

    After applying a couple optimizations from it is down to less than a second. I had to add two lines, and make a small change to a third.
            public static void Problem27b()
            {
                Func<int, int, int, long> evaluateFormula = (n, a, b) => (long)n * n + a * n + b;
                var range = Enumerable.Range(-999, 1999);
                var aRange = range.Where(x => (x & 1) == 1);
                var bRange = range.Where(x => ((long)x).IsPrime());
                var wholeNumbers = Enumerable.Range(0, int.MaxValue - 1);
                var duples = aRange.SelectMany(x => bRange.Select(y => new { a = x, b = y }));
                var formulaAnswers = duples.Select(x => new { x.a, x.b, answers = wholeNumbers.Select(y => evaluateFormula(y, x.a, x.b)) });
                var formulasWithPrimeCounts = formulaAnswers.Select(x => new { x.a, x.b, primeCount = x.answers.TakeWhile(y => y.IsPrime()).Count() });
                var mostPrimes = formulasWithPrimeCounts.OrderByDescending(x => x.primeCount).First();
                Console.WriteLine(mostPrimes.a * mostPrimes.b);
            }
    

    jackal on
  • Options
    andi75andi75 Registered User new member
    edited January 2008
    Some of these problems, e.g. 1 & 15, can be done by pure math, without resorting to code.
    1: 5 * (199*200)/2 + 3 * (333*334)/2 - 15 * (66*67)/2

    15: 40! / (20! 20!)

    andi75 on
  • Options
    jackaljackal Fuck Yes. That is an orderly anal warehouse. Registered User regular
    edited January 2008
    Problem 35. This one didn't take long at all to write. It runs in about 7 seconds.
    I really need to implement a prime sieve. It would save quite a bit of execution time. The memoize function saved about 2 seconds.
    
            public static void Problem35()
            {
                Func<int, bool> IsPrimeFunc = x => x.IsPrime();
                Func<int, bool> IsPrimeMemo = IsPrimeFunc.Memoize();
                var Range = Enumerable.Range(1, 1000000);
                Range = Range.Where(x => IsPrimeMemo(x));
                Range = Range.Where(x => NumberSequences.Rotations(x).All(y => IsPrimeMemo(y)));
                Console.WriteLine(Range.Count());
            }
    

    I went the imperative route on this one. I will probably try to reimplement it. The Digits function is with Problem 30.
            public static IEnumerable<int> Rotations(int value)
            {
                var valueDigits = Digits(value).Reverse().ToList();
                for (int counterX = 0; counterX < valueDigits.Count; counterX++)
                {
                    int current = 0;
                    for (int counterY = 0; counterY < valueDigits.Count; counterY++)
                    {
                        current = current * 10 + valueDigits[(counterX + counterY) &#37; valueDigits.Count];
                    }
                    yield return current;
                }
            }
    

    I didn't write this, but it is pretty trivial.
            public static Func<A, R> Memoize<A, R>(this Func<A, R> f)
            {
                var map = new Dictionary<A, R>();
                return a =>
                {
                    R value;
                    if (map.TryGetValue(a, out value))
                        return value;
                    value = f(a);
                    map.Add(a, value);
                    return value;
                };
            }
    

    jackal on
Sign In or Register to comment.