Project Euler

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

angel.white
Posts: 30
Joined: Thu Sep 11, 2008 2:49 am UTC

Re: Project Euler

Postby angel.white » Fri Oct 31, 2008 7:31 am UTC

Pesto wrote:One problem I seem to be running into a lot is overflow. I'm solving most of the problems using C. Are there any good tricks to avoiding overflow?

If it helps, one problem I ran into trouble with was number 14.
Most programs are small enough to be done with long in Java.

But what I did was picked up basic basic ruby. You can dl and install it in 2 minutes, it's that easy. And with basically my C knowledge changed syntactically, I was able to solve probably 70+ of them with Ruby... I didn't even know what a class was at that time.

http://www.ruby-lang.org/en/downloads/

Dongorath
Posts: 93
Joined: Tue Oct 16, 2007 1:17 pm UTC

Re: Project Euler

Postby Dongorath » Fri Oct 31, 2008 9:10 am UTC

I believe you can declare in C an "unsigned long long" which should be a 64 bits unsigned integer which should range from 0 to 18.446.744.073.709.551.615 (more than 1.8*10^19) if I'm correct which should be enough for most of the problems (but not always...)

HenryGifford
Posts: 152
Joined: Mon Nov 03, 2008 2:01 am UTC

Re: Project Euler

Postby HenryGifford » Tue Nov 04, 2008 2:38 pm UTC

I'm attempting to do Project Euler in Python but I'm not quite a master of the language. (I'm good, but not amazing.) Any tips to start out?

User avatar
Baxter
Posts: 46
Joined: Sun Oct 12, 2008 3:30 am UTC

Re: Project Euler

Postby Baxter » Tue Nov 04, 2008 3:04 pm UTC

Try to strip all of the problems down to the bare minimum required, can you isolate any cases that you're sure you don't need to test?

Try to define tight upper and lower bounds to all of the problems

If you're searching thought a list of numbers and one of the conditions is that the result must be a multiple of 20, you then have a dramatically reduced search space as you can generate multiples of 20 and test them for the rest of the conditions.

For the following conditions you should test in order of decreasing rarity for example if you also have to check if the numbers are a prime and if the numbers are odd you'd want to filter with your prime test first as it will lead to fewer numbers being pass to the function that tests if they're odd or not.

User avatar
zed0
Posts: 179
Joined: Sun Dec 17, 2006 11:00 pm UTC

Re: Project Euler

Postby zed0 » Wed Nov 26, 2008 1:25 am UTC

Any suggestions on a more elegant way to solve problem 16 in C++, apart from getting some bigNum library (I wanted to try it manually the first few times at least)?

(please don't look at this unless you've solved it yourself)

Spoiler:

Code: Select all

#include <iostream>
#include <vector>
using namespace std;

void longMult(int, vector<int> &);

int main()
{
   int power = 1000;
   int baseNum = 2;
   int total;
   vector<int> bigNum(1,1);

   for(int i=1; i<=power; ++i)
   {
      total = 0;
      cout << i << ": length = " << bigNum.size()+1 << " ";
      longMult(baseNum, bigNum);
      for(int j=bigNum.size()-1; j>=0; --j)
      {
         cout << bigNum.at(j);
         total += bigNum.at(j);
      }
      cout << ", total = " << total << endl;
   }
}

void longMult(int smallNum, vector<int> &bigNum)
{
   int carry = 0;
   for(int i=0; i<bigNum.size(); ++i)
   {
      bigNum.at(i)=(bigNum.at(i)*smallNum)+carry;
      carry = 0;
      if(bigNum.at(i)>=10)
      {
         if(i >= bigNum.size()-1)
         {
            bigNum.push_back(0);
         }
         carry = (bigNum.at(i)-(bigNum.at(i)%10))/10;
         bigNum.at(i) = bigNum.at(i)%10;
      }
   }
}

notallama
Posts: 236
Joined: Fri Jun 01, 2007 4:28 pm UTC

Re: Project Euler

Postby notallama » Wed Nov 26, 2008 6:23 am UTC

my solution for 10: (i was feeling crafty, so i used a lazy sieve)
Spoiler:

Code: Select all

(defn natural [] (iterate #(+ % 1) 1))
(def primes
     ;;takes a sorted set of counters and a seq of numbers to filter
     ((fn sieve [in-counters checked]
   ;;first part of the cons is the first in said seq. hurray!
     (lazy-cons (first checked)
           ;;this bit takes the set of counters, and the unchecked seq
           (loop [counts in-counters
             unchecked (rest checked)]
             (let [count (first counts)
              [c p] count
              u (first unchecked)]
          ;;if first in seq = a counter, composite -> try next in seq
          (cond (= c u) (recur counts
                     (rest unchecked))
                ;;if the counter is smaller, increment it and try again
                (< c u) (recur (conj (disj counts
                       count)
                      [(+ c p) p])
                     unchecked)
                ;;if the counter is bigger, first in seq is prime
                (> c u) (sieve (conj counts
                      [u u])
                     unchecked))))))
      ;;feed it a set with 2's counter and a seq from 2
      (sorted-set [2 2])
      (rest (natural))))

;;the bit that actually gives the answer
(reduce + (take-while #(> 2000000 %) primes))


it's rather slow, since it has none of the optimizations you'd normally use on this type of thing.
i couldn't square the counters, because the comparator was throwing a fit if i gave it a long integer.
(it gets up to 40000 or so with the squaring before it breaks, and it's considerably faster. what this means is that i need to build a better priority queue.)

User avatar
RoadieRich
The Black Hand
Posts: 1037
Joined: Tue Feb 12, 2008 11:40 am UTC
Location: Behind you

Re: Project Euler

Postby RoadieRich » Fri Nov 28, 2008 6:00 pm UTC

HenryGifford wrote:I'm attempting to do Project Euler in Python but I'm not quite a master of the language. (I'm good, but not amazing.) Any tips to start out?


1. Master generator expressions (f(x) for x in l if condition(x))
2. Master generator functions (see below)
3. Build a library of useful functions. I have a module called primes, which has a sieve, an iteerative prime number generator, and various derivative functions.

Example generator:

Code: Select all

def count2(start_at=0):
    """yield every other number, starting with start_at"""
    while True:
        yield start_at
        start_at += 2

For a long while, that generator was an integral part of my prime number generator.

(I then realized it was faster (and more efficient) to use a version of 6n+/-1, but that's an exercise for the reader.) w
73, de KE8BSL loc EN26.

HenryGifford
Posts: 152
Joined: Mon Nov 03, 2008 2:01 am UTC

Re: Project Euler

Postby HenryGifford » Fri Nov 28, 2008 6:56 pm UTC

RoadieRich wrote:
HenryGifford wrote:I'm attempting to do Project Euler in Python but I'm not quite a master of the language. (I'm good, but not amazing.) Any tips to start out?


1. Master generator expressions (f(x) for x in l if condition(x))
2. Master generator functions (see below)
3. Build a library of useful functions. I have a module called primes, which has a sieve, an iteerative prime number generator, and various derivative functions.

Example generator:

Code: Select all

def count2(start_at=0):
    """yield every other number, starting with start_at"""
    while True:
        yield start_at
        start_at += 2

For a long while, that generator was an integral part of my prime number generator.

(I then realized it was faster (and more efficient) to use a version of 6n+/-1, but that's an exercise for the reader.) w

:shock:
...I'll work on that...

grom
Posts: 11
Joined: Thu Aug 07, 2008 12:28 pm UTC

Re: Project Euler

Postby grom » Thu Dec 04, 2008 8:39 am UTC

Here is my haskell solution.
Spoiler:

Code: Select all

primes :: [Integer]
primes = 2:3:primes'
  where
    -- Every prime number other than 2 and 3 must be of the form 6k + 1 or
    -- 6k + 5. Note we exclude 1 from the candidates and mark the next one as
    -- prime (6*0+5 == 5) to start the recursion.
    1:p:candidates = [6*k+r | k <- [0..], r <- [1,5]]
    primes'        = p : filter isPrime candidates
    isPrime n      = all (not . divides n) $ takeWhile (\p -> p*p <= n) primes'
    divides n p    = n `mod` p == 0

main = print . sum . takeWhile (< 2000000) $ primes


$ ghc --make -O2 prob10.hs
$ time ./prob10
Spoiler:
142913828922


real 0m2.528s
user 0m2.512s
sys 0m0.016s

luke77
Posts: 47
Joined: Fri Oct 03, 2008 4:54 pm UTC

Re: Project Euler

Postby luke77 » Fri Dec 19, 2008 5:56 pm UTC

Has anyone done 34? I've written what seems to be a solid algorithm to solve it, but the only number I'm coming up with is the one they give, 145. At least in tests up to 5000000. Is there a special way to solve this?

User avatar
Xanthir
My HERO!!!
Posts: 5423
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Project Euler

Postby Xanthir » Fri Dec 19, 2008 6:23 pm UTC

luke77 wrote:Has anyone done 34? I've written what seems to be a solid algorithm to solve it, but the only number I'm coming up with is the one they give, 145. At least in tests up to 5000000. Is there a special way to solve this?

No, it should be extremely straightforward. My algorithm is a 3-liner, and that's with no tricks - it's simply the way anyone would first think of solving it.

Do you have a function for breaking a number into its constituent digits? That should make this trivial.

Hint, if you need it:
Spoiler:
Obviously, there's no way you'll need to loop is below 10M. However, the answer is actually quite substantially less than this - it's below 100k.


Algorithm that will solve it correctly in Lisp (again, only if you need it):
Spoiler:

Code: Select all

(loop for i from 10 to 100000
    if (= i (apply '+ (mapcar 'factorial (number->digits i))))
    collect i)

factorial and number->digits aren't built in, but they're trivial to write.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

luke77
Posts: 47
Joined: Fri Oct 03, 2008 4:54 pm UTC

Re: Project Euler

Postby luke77 » Fri Dec 19, 2008 8:01 pm UTC

I think that's basically what I did, or tried to, although not as concisely. Here's my code in Python:

Spoiler:
def makeFact(bound):
#Return list of factorials, 0 through bound
facts=list()
facts.append(0)
for i in range(1,bound+1):
facts.append(fact(i))

return facts

def testInclude(upperbound):
#tests for curious numbers below upperbound

# first make a list of factorials 0 through 9, to prevent repeated function calls
facts=makeFact(9)

#We want to begin our search at 3 since 1 and 2 are excluded
testlist=[i for i in range(3,upperbound+1)]
answerlist=list()

for num in testlist:
thesum=0
for digit in str(num):
thesum=thesum+facts[int(digit)]
if thesum==num:
answerlist.append(num)
return answerlist



The only answer this returns is 145, and that's it...

User avatar
Xanthir
My HERO!!!
Posts: 5423
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Project Euler

Postby Xanthir » Fri Dec 19, 2008 9:20 pm UTC

The factorial of 0 is 1. That's your problem.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

luke77
Posts: 47
Joined: Fri Oct 03, 2008 4:54 pm UTC

Re: Project Euler

Postby luke77 » Sat Dec 20, 2008 1:38 am UTC

Ahhh...thanks. Time to retake ninth grade math...

luke77
Posts: 47
Joined: Fri Oct 03, 2008 4:54 pm UTC

Re: Project Euler

Postby luke77 » Sun Dec 21, 2008 8:41 pm UTC

Any hints on number 50? I keep getting 886591, using the following code:

Spoiler:
def findContig(primes):
first=0
last=0
lenfinal=0
answer=0
thesum=0
primesclone=primes[:]
sequencelength=len(primes)

while first<=sequencelength:
last=first+1
while thesum<=1000000:
shortenedseq=primes[first:last]
thesum=sum(shortenedseq)
if thesum in primesclone:
newlen=last-first
if newlen>=lenfinal:
lenfinal=newlen
answer=thesum
last+=1
first+=1
return answer



The list of primes I'm passing in helped me solve an earlier problem correctly, so I think it's correct. Here is the code I used:

Spoiler:
def erat(lim):
array =range(lim+1)


firstprime=2
multiplier=2
while firstprime<=(lim**.5+1):




while firstprime*multiplier<=(lim):

array[firstprime*multiplier]=0
multiplier+=1
firstprime=getNextPrime(array,firstprime)
multiplier=2
answers=[]
for i in array:
if not i==0:
answers.append (i)

return answers

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Project Euler

Postby jaap » Mon Dec 22, 2008 12:40 am UTC

luke77 wrote:Any hints on number 50? I keep getting 886591, using the following code:


Please use the code tags for your code - that's what they're for. It is impossible to read python when the indentation is stripped.
That said, I don't immediately see a problem in your programs.

To help you find your problem, here are some facts you might want to try to verify.
- The sum of the first 60 primes, 2 up to 281, is the prime 7699.
- The only way to get a sum of some consecutive primes to be 886591 is by using the 31 primes from 28477 to 28711.

luke77
Posts: 47
Joined: Fri Oct 03, 2008 4:54 pm UTC

Re: Project Euler

Postby luke77 » Mon Dec 22, 2008 7:15 am UTC

Hmm...I'm getting the same result as you for the first sixty primes. There must be something wrong with my function. I'll try rewriting tomorrow.

EDIT: Is the length of the entire list of primes to 1000000 78500?

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Mon Dec 22, 2008 5:37 pm UTC

I'm getting 78498 for my prime below 1000000, with the highest being 999983. I'm pretty sure it's correct (using the list in my sig).
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
RoadieRich
The Black Hand
Posts: 1037
Joined: Tue Feb 12, 2008 11:40 am UTC
Location: Behind you

Re: Project Euler

Postby RoadieRich » Mon Dec 22, 2008 7:01 pm UTC

Berengal wrote:I'm getting 78498 for my prime below 1000000, with the highest being 999983. I'm pretty sure it's correct (using the list in my sig).

I got exactly the same using my generator, so confirmation of correctness.
73, de KE8BSL loc EN26.

User avatar
Kag
Posts: 1214
Joined: Thu Aug 23, 2007 1:56 am UTC

Re: Project Euler

Postby Kag » Mon Dec 22, 2008 7:26 pm UTC

I've been working on 222, and I'm sort of stuck.

I know how to calculate the minimum length of the pipe given a certain configuration of the balls, but I don't know which configuration would be the most efficient. Obviously brute forcing it isn't an option, since there are 21! possible orders. Any ideas?
The Great Hippo wrote:I am starting to regret having used 'goat-fucker' in this context.

luke77
Posts: 47
Joined: Fri Oct 03, 2008 4:54 pm UTC

Re: Project Euler

Postby luke77 » Mon Dec 22, 2008 11:39 pm UTC

That's right, I was accidentally adding an extra 2 in there. So my list is correct, but I don't see where my code is in error. Does anyone see the problem in this function?

Code: Select all

def findContig(primes):
   first=0
   last=0
   lenfinal=0
   answer=0
   thesum=0
   primesclone=primes[1:]
   sequencelength=len(primes)
   
   while first<=sequencelength:
   
      last=first+20
      while thesum<=1000000:
         shortenedseq=primes[first:last]
         thesum=sum(shortenedseq)
         if isPrime(thesum) :
            newlen=last-first
            if newlen>=lenfinal:
               lenfinal=newlen
               answer=thesum
         last+=1
      first+=1
   return answer

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Project Euler

Postby jaap » Mon Dec 22, 2008 11:53 pm UTC

luke77 wrote:That's right, I was accidentally adding an extra 2 in there. So my list is correct, but I don't see where my code is in error. Does anyone see the problem in this function?

When thesum exceeds 100000 and it exits the inner loop, when will it enter the inner loop again?

Kag wrote:Obviously brute forcing it isn't an option, since there are 21! possible orders. Any ideas?

Try a smaller number of circles. Explore the problem and its answers. Extend that to original problem.

luke77
Posts: 47
Joined: Fri Oct 03, 2008 4:54 pm UTC

Re: Project Euler

Postby luke77 » Tue Dec 23, 2008 12:11 am UTC

jaap wrote:
luke77 wrote:That's right, I was accidentally adding an extra 2 in there. So my list is correct, but I don't see where my code is in error. Does anyone see the problem in this function?

When thesum exceeds 100000 and it exits the inner loop, when will it enter the inner loop again?

When it exceeds 1000000 and exits the inner loop, 1 is added to "first" and then it reenters the inner loop as long as first is less than or equal to the length of the original sequence. So, in effect, it tests primes[1:21], then primes[1:22], primes[1:23],etc.until the sum is greater than 1000000, then tests primes[2:22], primes[2:23], ...

I start with sequences of length 20 simply because I know that the answer will have a sequence length greater than 20.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Project Euler

Postby jaap » Tue Dec 23, 2008 7:21 am UTC

luke77 wrote:...until the sum is greater than 1000000, then tests primes[2:22], primes[2:23], ...


I know that is what you intended, but that is not what will happen. Think about the (sum<=100000) condition of the inner loop. What is the value of thesum when it reaches the start of that inner while loop the second time?

User avatar
AttackAttack
Posts: 27
Joined: Fri Dec 12, 2008 1:31 am UTC

Re: Project Euler

Postby AttackAttack » Tue Dec 23, 2008 8:15 pm UTC

Haha, I love Project Euler, even though I haven't attempted any problems yet. I'm going to use Ruby to do it, but that means I have to learn Ruby, which is incredibly fun. Learning Ruby for that kind of thing is a lot easier than learning Python for it. To me, at least...

User avatar
Qoppa
Posts: 694
Joined: Sat Nov 24, 2007 9:32 pm UTC
Location: Yes.

Re: Project Euler

Postby Qoppa » Wed Dec 24, 2008 8:43 pm UTC

I just got number 39 using Haskell! Hooray! My solution's rather verbose (15 lines), but it gets me the answer in ~0.4 seconds.

Code: Select all

_=0,w=-1,(*t)(int,int);a()??<char*p="[gd\
~/d~/\\b\x7F\177l*~/~djal{x}h!\005h";(++w
<033)?(putchar((*t)(w??(p:>,w?_:0XD)),a()
):0;%>O(x,l)??<_='['/7;{return!(x%(_-11))
?x??'l:x^(1+ ++l);}??>main(){t=&O;w=a();}

HenryGifford
Posts: 152
Joined: Mon Nov 03, 2008 2:01 am UTC

Re: Project Euler

Postby HenryGifford » Tue Dec 30, 2008 11:47 pm UTC

My problems are endless.
My code for problem 34

Code: Select all

from Module import factorial
g,l=0,0
for d in range(1,6000): #I don't know why I'm using 6000... But the problem doesn't say how far to go up to, so I'm gonna assume that there aren't any above a specific number..
    for i in range(0,len(str(d))):
        g+=factorial(int(str(d)[i]))
    if g==d: l+=d
print l
It just comes up with 1. When I try it as simply:

Code: Select all

g,l=0,0
for i in range(0,len(str(145))):
    g+=factorial(int(str(145)[i]))
if g==145: l+=145
print l

It prints 145. What's the deal??

User avatar
spdqbr
Posts: 171
Joined: Sat Mar 08, 2008 1:41 am UTC
Location: A shaker of salt

Re: Project Euler

Postby spdqbr » Wed Dec 31, 2008 1:37 am UTC

@HenryGifford:
The problem is that the value of g is not behaving like you think it is. Walk through by hand for d in range(1,4) and you should get it (or just print g and l for every iteration and it should become clear).

Also,
HenryGifford wrote:I don't know why I'm using 6000... But the problem doesn't say how far to go up to, so I'm gonna assume that there aren't any above a specific number..

You are correct, but you can figure out which number.
Spoiler:
What's the most you can add to the sum of the factorial of the digits of a number by adding a digit?
In questions of science, the authority of a thousand is not worth the humble reasoning of a single individual.

Galileo

HenryGifford
Posts: 152
Joined: Mon Nov 03, 2008 2:01 am UTC

Re: Project Euler

Postby HenryGifford » Wed Dec 31, 2008 1:44 am UTC

spdqbr wrote:@HenryGifford:
The problem is that the value of g is not behaving like you think it is. Walk through by hand for d in range(1,4) and you should get it (or just print g and l for every iteration and it should become clear).

Also,
HenryGifford wrote:I don't know why I'm using 6000... But the problem doesn't say how far to go up to, so I'm gonna assume that there aren't any above a specific number..

You are correct, but you can figure out which number.
Spoiler:
What's the most you can add to the sum of the factorial of the digits of a number by adding a digit?

Aha! Thanks, I've had that problem before, should have realized.

User avatar
katkov
Posts: 31
Joined: Fri Sep 28, 2007 9:11 pm UTC

Re: Project Euler

Postby katkov » Sun Jan 11, 2009 3:32 am UTC

I tried to do a Sieve of Eratosthenes for Problem 10 and ended up with this

Code: Select all

public class Prob10
{
    public static void main(String args[])
    {
        final int NUM=2000000;
        int list[]= new int[NUM+1];
        for(int i=0;i<=NUM;i++)
        {
            list[i]=i;
        }
        list[1]=0;
        for(int j=2;j<=NUM;j++)
        {
            if (list[j] != 0)
            {
                for(int k=j*2;k<=NUM; k+=j)
                {
                    list[k]=0;
                }
            }
        }
        int total=0;
        for(int l=0; l<=NUM; l++)
        {
            total+=(int)list[l];
        }
       System.out.println(total);
    }
}

And it gives me 1179908154, and I tried it with 1 million instead of two and it gave me a negative number.
I can't figure what I did wrong

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Sun Jan 11, 2009 3:52 am UTC

From a very brief glimpse at your code, I'd suggest changing total to a long.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
katkov
Posts: 31
Joined: Fri Sep 28, 2007 9:11 pm UTC

Re: Project Euler

Postby katkov » Sun Jan 11, 2009 5:10 am UTC

Berengal wrote:From a very brief glimpse at your code, I'd suggest changing total to a long.

And that was the problem ok thanks

User avatar
spdqbr
Posts: 171
Joined: Sat Mar 08, 2008 1:41 am UTC
Location: A shaker of salt

Re: Project Euler

Postby spdqbr » Fri Jan 16, 2009 2:44 am UTC

Problems 103, 105, and 106 have been kicking my ass for a loooooong time now. They deal with special sum sets, and my brute force solution just doesn't cut it.

Can anyone give a hint or point me in the right direction?
In questions of science, the authority of a thousand is not worth the humble reasoning of a single individual.

Galileo

DarkRat
Posts: 19
Joined: Mon Mar 31, 2008 3:19 pm UTC

Re: Project Euler

Postby DarkRat » Sat Jan 17, 2009 1:29 pm UTC

Problem 34:

Code: Select all

class Integer
  def factorial
    result = self
    (self-1).downto(1) { |n|
      result *= n
    }
    return result
  end
end
result_array = []
start = Time.now
3.upto 1_000_000 do |n|
  result = 0
  n.to_s.split(//).each{ |d| #split the number and factor the digits
    result += d.to_i.factorial
    break if result > n
  }
  if result == n
    result_array << n
    puts n
  end
  #puts "Progress: " + n.to_s  if n%50_000 == 0
end
puts "------"
puts Time.now - start
puts "------"
result_array.each do |i|
  puts i
end


some dirty hacks inside, but I just can't figure out a result. 145 ist the only number I get as result

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Project Euler

Postby jaap » Sat Jan 17, 2009 1:38 pm UTC

DarkRat wrote:Problem 34:


0! = 1

DarkRat
Posts: 19
Joined: Mon Mar 31, 2008 3:19 pm UTC

Re: Project Euler

Postby DarkRat » Sat Jan 17, 2009 1:57 pm UTC

jaap wrote:
DarkRat wrote:Problem 34:


0! = 1

meh, thanks :D

User avatar
Kag
Posts: 1214
Joined: Thu Aug 23, 2007 1:56 am UTC

Re: Project Euler

Postby Kag » Sat Jan 17, 2009 4:47 pm UTC

jaap wrote:Try a smaller number of circles. Explore the problem and its answers. Extend that to original problem.
Got it. Took me a while to write something to brute-force scaled down versions, but the problem is hilariously easy after that. I'd still like to write a solution that can solve this on its own, though.
The Great Hippo wrote:I am starting to regret having used 'goat-fucker' in this context.

User avatar
spdqbr
Posts: 171
Joined: Sat Mar 08, 2008 1:41 am UTC
Location: A shaker of salt

Re: Project Euler

Postby spdqbr » Thu Jan 29, 2009 4:22 am UTC

Re my previous post, I've finally nailed down 106 (combinitorically, didn't even need code), and 105. 103 can't be far now!
(sorry, I'm stoked 8) )
In questions of science, the authority of a thousand is not worth the humble reasoning of a single individual.

Galileo

stone915
Posts: 42
Joined: Wed Jan 07, 2009 4:31 am UTC

Re: Project Euler

Postby stone915 » Thu Jan 29, 2009 6:33 am UTC

Just found this and I'm working on problem 3. Here's my code:

Spoiler:

Code: Select all

getLargestPrime :: Integer -> Integer
getLargestPrime n = getPrime (reverse (getFactors n [2..n]))

getPrime :: [Integer] -> Integer
getPrime (p1:ps) | (length $ getFactors p1 ps) == 0 = p1
                 | otherwise = getPrime ps

getFactors :: Integer -> [Integer] -> [Integer]
getFactors x [] = []
getFactors x (p1:ps) | (mod x p1) == 0 = p1 : (getFactors x ps)
                     | otherwise = getFactors x ps


Anybody want to tell me what the runtime of it is? Because I think it's at least O(n^3), which is horrifying, especially for the number they gave us.

And it's had one of my processor cores maxed out for the past 10-15 minutes.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Thu Jan 29, 2009 9:24 am UTC

Actually, you might want to start by defining all prime numbers and then start factorizing from there. The coolest prime definition I've seen is 'primes = nubBy (((>1) .) . gcd) [2..]' but it's not as efficient as the one I use (which is still a one-liner, if a little longer).

Keep a file containing various definitions, such as the list of primes, factorization, all divisors, power set etc. It'll be handy. E.g. when I got to problem 10 on my haskell run my answer was simply 'sum . takeWhile (<2*10^6) $ primes'
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 8 guests