Options

Project Euler - Let's do Math/Programming Challenges

2»

Posts

• Options
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
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
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
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
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);