Project Euler

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

Moderators: phlip, Moderators General, Prelates

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

Re: Project Euler

Postby Xanthir » Sun Jan 31, 2010 3:44 pm UTC

So, doing problem 80 (calculate the sum of the first 100 digits of the square roots of 2-100). Made a nice simple eulers-method iterator, which is plenty fast enough to solve this problem. I then wrote a function that gives me the digit sum. It took 8 seconds to sum the sqrt of 2, since there's a lot of multiplication happening on a very large rational. I let it run for 10 minutes and it couldn't finish the actual problem.

This morning, I look at it and go, "Um, self? Wtf's wrong with multiplying it by 10^99, flooring it, then using your existing routines to break it into digits and sum them?" I replied "I don't know, self, let me try that."

I then headdesk'd as it returned in 60 milliseconds.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Ayren
Posts: 18
Joined: Thu Feb 18, 2010 1:25 pm UTC

Re: Project Euler

Postby Ayren » Thu Feb 18, 2010 1:40 pm UTC

I am having trouble with problem 26. First some (Haskell) code:

Code: Select all

invrem x y = rem y x

recurringcycle n = map (invrem n) $ map (10^) [0..]

hasperiod n orig_n xs = take n (drop orig_n xs) == take n (drop n (drop orig_n xs)) -- the drop orig_n clause is to prevent
                                                                                                                          --starting digits from causing trouble

periodlength n orig_n xs
   | hasperiod n orig_n xs   = n
   | otherwise      = periodlength (n+1) orig_n xs


pl n = periodlength 1 n (recurringcycle n)

prob26 = maximum $ map pl [1..1000]
prob26_2 = maximum [periodlength 1 n $ recurringcycle n|n<-[1..1000]]


prob26 hangs, prob26_2 as well. Doing just "map pl [1..]" shows me that it stops at "pl 7". Manually doing "pl 7" hangs as well, but "periodlength 1 7 (recurringcycle 7)" works just fine. Does anybody know why " pl 7 " won't work?

User avatar
levicc00123
Posts: 165
Joined: Thu Jan 03, 2008 5:33 pm UTC
Location: Sterling, CO
Contact:

Re: Project Euler

Postby levicc00123 » Thu Mar 11, 2010 4:45 am UTC

(Sorry if this is necromancy.)

I'm working on project euler problem 8, and I'm having a bit of trouble. My plan is to load the massive number from a file in the same directory as the python script and split each line into a list of integers before closing the file and moving on, the problem is that when I run

Code: Select all

f = file("pe08.txt", "r")
for line in f:
   fir x in line:
      int(x)
      print(x)

I get
Python 2.6.4 wrote:Traceback (most recent call last):
File "<stdin>", line 4, in <module>
ValueError: invalid literal for int() with base 10: ''


"No problem!" I think, figuring that python was choking on the newlines, so I re-wrote the code to

Code: Select all

f = file("pe08.txt", "r")
for line in f:
   line.rstrip("\n")
   for x in line:
      int(x)
      print(x)


I don't get anything back, what am I doing wrong here? This seems like something that should be easy to pull off here.
Image

User avatar
Pesto
Posts: 737
Joined: Wed Sep 05, 2007 5:33 pm UTC
Location: Berkeley, CA

Re: Project Euler

Postby Pesto » Thu Mar 11, 2010 7:20 am UTC

Bishop wrote:It's funny how simple problem 54 (poker hand problem) is, and yet despite that I still keep getting the wrong answer.

I'd never looked at this one before. It looks like a lot of fun!

User avatar
phlip
Restorer of Worlds
Posts: 7543
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Project Euler

Postby phlip » Thu Mar 11, 2010 11:43 am UTC

levicc00123 wrote:

Code: Select all

   line.rstrip("\n")

Python strings are immutable...

Code: Select all

   line = line.rstrip("\n")

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
levicc00123
Posts: 165
Joined: Thu Jan 03, 2008 5:33 pm UTC
Location: Sterling, CO
Contact:

Re: Project Euler

Postby levicc00123 » Thu Mar 11, 2010 2:52 pm UTC

phlip wrote:
levicc00123 wrote:

Code: Select all

   line.rstrip("\n")

Python strings are immutable...

Code: Select all

   line = line.rstrip("\n")


D'oh! That fixed it, thank you.
Image

User avatar
levicc00123
Posts: 165
Joined: Thu Jan 03, 2008 5:33 pm UTC
Location: Sterling, CO
Contact:

Re: Project Euler

Postby levicc00123 » Thu Mar 18, 2010 4:44 pm UTC

I'm thinking about writing a common lisp library for solving project euler problems, If anyone has any suggestions or requests as to what should go in it, please let me know.
Image

User avatar
Pesto
Posts: 737
Joined: Wed Sep 05, 2007 5:33 pm UTC
Location: Berkeley, CA

Re: Project Euler

Postby Pesto » Thu Mar 18, 2010 7:30 pm UTC

[obvious]Prime number generator[/obvious]

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

Re: Project Euler

Postby Xanthir » Fri Mar 19, 2010 2:49 pm UTC

Plenty of things related to prime number generation, primality testing, and factoring. Efficient implementations of those are necessary for lots of problems. I just tried to attach a utility file I have specifically for dealing with primes, but apparently "lisp" isn't an allowed extension. So, spoiler'd code instead:
Spoiler:

Code: Select all

(defparameter +factors+)
(defparameter +factors-limit+)
(defparameter +last-prime+)
(defun init-factors (&optional (n 1000000))
  (setf +factors+ (make-array (1+ n) :element-type 'fixnum)
        +factors-limit+ n)
  (loop for i from 1 to n do (setf (aref +factors+ i) i))
  (loop for i from 2 to n
        if (= i (aref +factors+ i))
          do (loop for x from i to n by i
                   if (= x (aref +factors+ x))
                     do (setf (aref +factors+ x)
                              (/ (aref +factors+ x) i))))
  (setf +last-prime+ (prev-prime +factors-limit+))
  t)

(defun factor (n)
    "Returns the smallest prime factor of n."
    (/ n (aref +factors+ n)))
(defun factor* (n)
    "Return the largest proper factor of n."
    (aref +factors+ n))

(defun factorize (n)
  "Returns the prime factors of n."
  (unless (primep n) (cons (factor n) (factorize (factor* n)))))

(defun unique-factorize (n)
    "Returns only the unique factors of n."
    (loop for last-factor = 0 then (factor x)
        for x = n then (/ x (factor x))
        if (not (= last-factor (factor x)))
        collect (factor x)
        until (primep x)))

(defun primep (n)
  (cond ((<= n +factors-limit+) (= 1 (factor n)))
        ((<= n (expt +last-prime+ 2)) (primep-2 n))))
(defun primep-2 (n)
  (not (loop for x = 2 then (next-prime x)
             with limit = (floor (sqrt n))
             until (> x limit)
             thereis (zerop (mod n x)))))

(defun next-prime (n)
    "Returns the first prime greater than n."
    (loop for i from (1+ n) to +factors-limit+
        if (primep i)
        do (return i)))

(defun prev-prime (n)
    "Returns the first prime less than n."
    (loop for i from (1- n) downto 1
        if (primep i)
        do (return i)))

(defun prime (n)
    "Returns the nth prime"
    (loop for p = 2 then (next-prime p)
        repeat n
        finally (return p)))

(defun primes (&key limit num)
  "Returns a list of successive primes, limited either by number of primes or maximum prime."
  (loop for x = 2 then (next-prime x)
        for i upfrom 0
        until (and num (= i num))
        until (and limit (> x limit))
        collect x))
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Pesto
Posts: 737
Joined: Wed Sep 05, 2007 5:33 pm UTC
Location: Berkeley, CA

Re: Project Euler

Postby Pesto » Wed Apr 21, 2010 4:48 pm UTC

I'd like to tackle a couple PE problems in befunge. I don't know the language at all, so are there any problems that would lend themselves to that language?

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

Re: Project Euler

Postby Xanthir » Thu Apr 22, 2010 4:12 am UTC

I doubt any problem really lends itself to befunge.

Just start from the beginning, I suppose. Without access to actual data structures there's no way you'll be in under the minute mark past the first few.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Toeofdoom
The (Male) Skeleton Guitarist
Posts: 3446
Joined: Wed Jan 10, 2007 10:06 am UTC
Location: Melbourne, Australia
Contact:

Re: Project Euler

Postby Toeofdoom » Thu Apr 22, 2010 12:06 pm UTC

Well I started this kinda recently, between other things like uni and game development, so far I've solved 38 of them... the most recent 12 just tonight. Not having too much trouble at the moment. I'm working with C++, using ttmath for arbitrarily large numbers.
Hawknc wrote:Gotta love our political choices here - you can pick the unionised socially conservative party, or the free-market even more socially conservative party. Oh who to vote for…I don't know, I think I'll just flip a coin and hope it explodes and kills me.

Website

User avatar
Bipod
Posts: 33
Joined: Fri Dec 04, 2009 8:51 pm UTC

Re: Project Euler

Postby Bipod » Wed May 26, 2010 9:13 pm UTC

halbarad wrote:I'm getting back into these and looking at problem 9 again. I want to come up with a solution which isn't a brute force method but it seems like the quickest and easiest ways I can think of to do it are just brute forcing it.

Is it possible to do it another way or is it better for me to just brute force it and move on?

I definitely didn't do it the way that you were supposed to either, but I managed to significantly lower the choices. On a related note, any help simplifying it further (I got the answer right) would be great, if just for knowledge's sake.

What I did: (in Python)
Spoiler:

Code: Select all

a = aorig = 3
b = borig = 4
c = corig = 5

for x in range( 1000 ):
    if a + b + c == 1000:
        print( a * b * c )
        break
    elif a + b + c < 1000:
        a = a + aorig
        b = b + borig
        c = c + corig
    else:
        break

The code then repeated for each of the other first four triples (5 12 13, 8 15 17, 7 24 25). Luckily, it was one of them. Even though it is a rather unwieldy brute force, I got the correct answer in less than a second, but I know there's a better way that someone on here could explain. ( I couldn't find one that made sense to me on the answer page on the Euler website. )

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

Re: Project Euler

Postby jaap » Wed May 26, 2010 10:59 pm UTC

Bipod wrote:
halbarad wrote:Is it possible to do it another way or is it better for me to just brute force it and move on?

I definitely didn't do it the way that you were supposed to either, but I managed to significantly lower the choices. On a related note, any help simplifying it further (I got the answer right) would be great, if just for knowledge's sake.

What I did: (in Python)
Spoiler:

Code: Select all

a = aorig = 3
b = borig = 4
c = corig = 5

for x in range( 1000 ):
    if a + b + c == 1000:
        print( a * b * c )
        break
    elif a + b + c < 1000:
        a = a + aorig
        b = b + borig
        c = c + corig
    else:
        break

The code then repeated for each of the other first four triples (5 12 13, 8 15 17, 7 24 25). Luckily, it was one of them. Even though it is a rather unwieldy brute force, I got the correct answer in less than a second, but I know there's a better way that someone on here could explain. ( I couldn't find one that made sense to me on the answer page on the Euler website. )


Bipod, since you got that far, you could have deduced the right answer without writing a single line of code:
Spoiler:
3+4+5=12, so any scaled version of this triangle will have a perimeter that is a multiple of 12. But 1000 is not a multiple of 12, so that section of code you wrote will not produce the solution. In the same way you can eliminate two of the other triangles, and verify that the remaining one does work.
You could write a program to generate each primitive pythagorean triplet using Euclid's formula, and check whether its perimeter divides into 1000.
Or you could plug Euclid's formula into a+b+c=1000=2353 and see what the consequences are. It is not terribly hard to deduce what the values of m and n must be (since they are coprime and m>n).

User avatar
Bipod
Posts: 33
Joined: Fri Dec 04, 2009 8:51 pm UTC

Re: Project Euler

Postby Bipod » Fri May 28, 2010 1:20 pm UTC

jaap wrote:Bipod, since you got that far, you could have deduced the right answer without writing a single line of code:
Spoiler:
3+4+5=12, so any scaled version of this triangle will have a perimeter that is a multiple of 12. But 1000 is not a multiple of 12, so that section of code you wrote will not produce the solution. In the same way you can eliminate two of the other triangles, and verify that the remaining one does work.
You could write a program to generate each primitive pythagorean triplet using Euclid's formula, and check whether its perimeter divides into 1000.
Or you could plug Euclid's formula into a+b+c=1000=2353 and see what the consequences are. It is not terribly hard to deduce what the values of m and n must be (since they are coprime and m>n).

:roll: It's always so obvious when you see it written out by someone else. Thanks.

User avatar
kriel
Posts: 922
Joined: Thu Feb 07, 2008 2:58 pm UTC
Location: Somewhere I'm not.
Contact:

Re: Project Euler

Postby kriel » Sat May 29, 2010 12:14 am UTC

Huge fukken spoilers ahead, though only for the first few problems (specifically 1-10, 12, 14, 16, 20)
Spoiler:

Code: Select all

def gcd(a, b):
    while(b != 0):
        a, b = b, a%b
    return a
 
def lcm(a,b):
    return a * b / gcd(a, b)

def natsort( l ):
    """ Sort the given list in the way that humans expect."""
    #http://www.codinghorror.com/blog/archives/001018.html
    convert = lambda text: int(text) if text.isdigit() else text
    from re import split
    alphanum_key = lambda key: [ convert(c) for c in split('([0-9]+)', key) ]
    l.sort( key=alphanum_key )
    return l

#The functions above were stolen, but they were just too awesome to not steal

def _erasthonessieve(n):
    sieve = [False,False]+[True]*(n-2)
    for i in xrange(2,int(n**.5+1)):
        if not sieve[i]:
            continue
        for j in xrange(2*i,n,i):
            sieve[j]=False
    return [i for i,j in enumerate(sieve) if j]

from time import clock
timestart = clock()
primes = _erasthonessieve(2000004) #preseeded with sieve, and memoized
print "primes preseeded in %.3fs\n" % (clock() - timestart)

def _makenextprime():
    global primes
    currcandidate = primes[-1] + 2
    while True:
        goodprime = True
        for i in primes:
            if currcandidate % i == 0:
                goodprime = False
                break
            if i*i > currcandidate:
                break
        if goodprime:
            primes += [currcandidate]
            return
        currcandidate += 2

def getnthprime(n):
    """note that 2 is the "1st" prime"""
    global primes
    while len(primes) < n:
        _makenextprime()
    return primes[n-1]

def getnprimes(n):
    """returns n primes (with indexes 0 to n-1)"""
    global primes
    while len(primes) < n:
        _makenextprime()
    return primes[:n]

def getprimesto(n):
    """returns primes < n"""
    global primes
    while primes[-1] < n:
        _makenextprime()
    a = 0
    while primes[a] < n:
        a += 1
    return primes[:a]

def primefactors(n):
    myprimes = getprimesto(n**.5+1)
    pfacs = []
    for i in myprimes:
        while n % i == 0:
            n /= i
            pfacs += [i]
        if i*i > n:
            if n != 1:
                pfacs += [n]
            break
    return pfacs

def allfactors(n):
    facs = [1] + primefactors(n)
    c = []
    while facs != c:
        c = facs
        facs = list(set([a*b for a in facs for b in facs if (n % (a*b) == 0)]))
        facs.sort()
    return facs

def allfactors2(n):
    facs = []
    for i in xrange(1,int(n**.5+1)):
        if n % i == 0:
            facs += [i,n/i]
    facs = list(set(facs))
    facs.sort()
    return facs

fib = [1,1]
def fibseqto(n):
    """returns a list of the fibonacci sequence up to the value n (exclusive)"""
    global fib
    while fib[-1] < n:
        fib += [fib[-2]+fib[-1]]
    a = 0
    while fib[a] < n:
        a += 1
    return fib[:a]

def prod(n):
    """returns the product of n, similar to sum(n)"""
    from operator import mul
    return reduce(mul, n)

#Now, start the actual problems

def problem1():
    """return the sum of all multiples of 3 and 5 below 1000"""
    return sum([i for i in xrange(1000) if (i%3==0 or i%5==0)])

def problem2():
    """Find the sum of all the even-valued terms in the fibonacci sequence which do not exceed four million."""
    return sum([i for i in fibseqto(4000000) if i%2==0])

def problem3():
    """What is the largest prime factor of the number 600851475143 ?"""
    return max(primefactors(600851475143))

def problem4():
    """Find the largest palindrome made from the product of two 3-digit numbers."""
    #yes, this is a hack. Deal with it.
    universe = [x*y for x in xrange(100,1000) for y in xrange(100,1000) if x <= y]
    universe.sort(reverse=True)
    for i in universe:
        if str(i) == str(i)[::-1]:
            return i

def problem5():
    """What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?"""
    #also stolen.
    return reduce(lcm,xrange(2, 21))

def problem6():
    """Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum."""
    return sum(xrange(101))**2-sum([i**2 for i in xrange(101)])

def problem7():
    """What is the 10001st prime number?"""
    return getnthprime(10001)

def problem8():
    """Find the greatest product of five consecutive digits in the 1000-digit number."""
    number = "73167176531330624919225119674426574742355349194934969835203127745063262395783180169848018694788518438586156078911294"+\
    "94954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121"+\
    "72238311362229893423380308135336276614282806444486645238749303589072962904915604407723907138105158593079608667017242712188399"+\
    "87979087922749219016997208880937766572733300105336788122023542180975125454059475224352584907711670556013604839586446706324415"+\
    "72215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319"+\
    "98900088952434506585412275886668811642717147992444292823086346567481391912316282458617866458359124566529476545682848912883142"+\
    "60769004224219022671055626321111109370544217506941658960408071984038509624554443629812309878799272442849091888458015616609791"+\
    "91338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
    #Oh me yarm Oh big number.
    calcmax = 0;
    for i in xrange(0,len(number)-4):
        calcmax = max(calcmax, prod([int(i) for i in number[i:i+5]]))
    return calcmax

def problem9():
    """There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc."""
    i = -1
    while True:
        i += 1
        a = [(i,j,1000-i-j) for j in xrange(0,i)]
        a += [(j,i,1000-i-j) for j in xrange(0,i+1)]
        for b in a:
            if b[0]*b[0]+b[1]*b[1]==b[2]*b[2]:
                return prod(b)

def problem10():
    """Calculate the sum of all the primes below two million."""
    return sum(getprimesto(2000000))

def problem12():
    """What is the value of the first triangle number to have over five hundred divisors?"""
    b = 0
    d = 0
    while True:
        b += 1
        d += b
        c = {}
        a = primefactors(d)
        for i in a:
            c[i] = a.count(i)+1
        if len(c) > 0 and prod(c.values()) > 500:
            return d

prob14dic = {1:0}
def prob14b(n,c=0):
    global prob14dic
    if prob14dic.has_key(n):
        return prob14dic[n]
    if n % 2 == 0:
        a = prob14b(n/2,c+1)+1
    else:
        a = prob14b(3*n+1,c+1)+1
    prob14dic[n] = a
    return a

def problem14():
    """Which starting number, under one million, produces the longest chain?"""
    a = [0]
    for i in xrange(1,1000001):
        a += [prob14b(i)]
    #resetting the dic to save memory, maybe
    global prob14dic
    prob14dic = {1:0}
    return a.index(max(a))

def problem16():
    """What is the sum of the digits of the number 2**1000?"""
    return sum([int(i) for i in str(2**1000)])

def problem20():
    """Find the sum of digits in 100!"""
    return sum([int(i) for i in str(prod(xrange(2,long(101))))])

#And some cosmetic stuffs to make stuff nice.

def do_main(n):
    from time import clock
    from sys import argv
    global primes, timestart
    for a in (natsort([i for i in n if i[:7] == "problem"]) if len(argv[1:])==0 else ["problem" + argv[-1]]):
        print a+": ",
        s = clock()
        exec "print "+a+"(),"
        print " in %.3fs" % (clock() - s)
    print "\nall done in %.3fs" % (clock() - timestart)
    print "\nbiggest prime found: %d" % primes[-1]

if __name__ == "__main__":
    do_main(dir())

Divinas
Posts: 57
Joined: Wed Aug 26, 2009 7:04 am UTC

Re: Project Euler

Postby Divinas » Mon May 31, 2010 12:30 pm UTC

Is it only me that tries to get the best possible solution from the first try, instead of mocking up a working, but bad version first? Also, is it only me that often finds himself calculating the answer by hand (or arrives just a few steps before the answer), and then realizes that this was the program's job?

User avatar
Jubi
Posts: 37
Joined: Tue Feb 16, 2010 3:03 pm UTC

Re: Project Euler

Postby Jubi » Sun Jun 06, 2010 2:54 pm UTC

I just started programming and working on project euler. I'm having trouble with problem 1 and I'm trying not to cheat and look up the answer but here is what I have so far.

Code: Select all


#Multiples of 3
x = range(0,1000,3)
#Multiples of 5
y = range(0,1000,5)

#Changing each into a set to perform functions
three = set(x)
five = set(y)

#Changing to include numbers in 3 or 5 but not both so that I don't have duplicates
answer = five.symmetric_difference(three)

#Find sum of all elements that are multiples of 3 and 5
print sum(answer)



I can't find where I made the mistake, it works for 10 but not 1000
Ég vild...Ég vildi að einhver myndi bara skipta mér burt og...festa mig

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

Re: Project Euler

Postby jaap » Sun Jun 06, 2010 3:01 pm UTC

Jubi wrote:I just started programming and working on project euler. I'm having trouble with problem 1

You're using symmetric_difference, so you're excluding multiples of 15 instead of including them just once. Use union instead.

User avatar
Jubi
Posts: 37
Joined: Tue Feb 16, 2010 3:03 pm UTC

Re: Project Euler

Postby Jubi » Sun Jun 06, 2010 3:51 pm UTC

jaap wrote:
Jubi wrote:I just started programming and working on project euler. I'm having trouble with problem 1

You're using symmetric_difference, so you're excluding multiples of 15 instead of including them just once. Use union instead.



Thank you so much! I feel like much less of a failure at life now.

Time for problem 2.....eep...

After working on this one for a while it seems much more difficult than the first one
Ég vild...Ég vildi að einhver myndi bara skipta mér burt og...festa mig

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: Project Euler

Postby Tirian » Sun Jun 06, 2010 11:15 pm UTC

One of the problems/features of Project Euler is that it is so strongly fixed on math problems. More often than not in my experience, the difference between a program taking a week to run and one running in less than a minute is sitting down with a piece of paper until you understand the mathematical secret that obscures the problem (or that you do that for weeks before learning that the secret was published in a mathematical journal that only the submitters read). That's neither good nor bad, but it isn't necessarily the best way to learn to program if you're not coming in as a math geek.

If you find that PE isn't necessarily what you're looking for or are looking for a supplement, the Sphere Online Judge is something that I've liked a lot. There are some problems that are harsh on Python because they use the same time limits for all problems and some are designed to be challenging for C/C++ users, but there is still quite a lot there to offer. In addition, their forums actually welcome people earnestly asking for help about how to solve the problems. :wink:

User avatar
kriel
Posts: 922
Joined: Thu Feb 07, 2008 2:58 pm UTC
Location: Somewhere I'm not.
Contact:

Re: Project Euler

Postby kriel » Mon Jun 07, 2010 4:31 am UTC

Tirian wrote:More often than not in my experience, the difference between a program taking a week to run and one running in less than a minute is sitting down with a piece of paper until you understand the mathematical secret that obscures the problem
ftfy.

But for serious, simply understanding the problem can make things so much easier. Running max() on a query of 7M rows, when you know the maxes are at the bottom of the table, than just pulling the last 1K or so and maxing that.

There was a perfect example earlier up in the thread. a + b + c = 1000, a^2 + b^2 = c^2, solve for a, b, and c. This is not really a problem that should be brute forced, it can be solved algebraically.

... it's late, so this post may or may not be sensical.

greg1313
Posts: 1
Joined: Sat Jun 26, 2010 12:48 pm UTC

Re: Project Euler

Postby greg1313 » Sat Jun 26, 2010 12:51 pm UTC

themuffinking wrote:I want to kill problem #14 with fire. It's about finding the maximum cycle length in the collatz conjecture scenario with a starting point under a million.



Every single time, I get 910107 with 475 cycles as the maximum. Every time. I checked it, that's how many cycles there are. In fact, I checked a random sample of 45 different numbers, all of which are correct in their cycle lengths. Why? Why does it mock me?


I had the same problem until I changed 'int' to 'unsigned long int'.

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 » Sat Jul 17, 2010 2:07 am UTC

Ok, I'm completely stumped on problem 31.

Can anyone give me some advice on how I should be looking at it? All I can think is that I need some sort of backtracking approach, but I can't for the life of me figure out how to implement it. I'm almost certainly missing something.
73, de KE8BSL loc EN26.

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

Re: Project Euler

Postby jaap » Sat Jul 17, 2010 3:58 am UTC

RoadieRich wrote:Ok, I'm completely stumped on problem 31.

Can anyone give me some advice on how I should be looking at it? All I can think is that I need some sort of backtracking approach, but I can't for the life of me figure out how to implement it. I'm almost certainly missing something.

Use recursion.
Spoiler:
Implement a recursive function
int countWays(int remainingMonetaryValue, int numCoinTypes )
which returns the number of ways to make remainingMonetaryValue using only the smallest numCoinTypes types of coins.
The problem asks for countWays(200, 7 ).
Spoiler:
This countWays function can call itself with a reduced numCoinTypes argument. So what it has to do is select how many coins to use of the largest type, call itself to count how many ways there are to complete it. For each choice of number of largest coin used you get a result, and the function returns the sum of those results.

qbg
Posts: 586
Joined: Tue Dec 18, 2007 3:37 pm UTC

Re: Project Euler

Postby qbg » Sat Jul 17, 2010 4:48 am UTC

RoadieRich wrote:Ok, I'm completely stumped on problem 31.

Can anyone give me some advice on how I should be looking at it? All I can think is that I need some sort of backtracking approach, but I can't for the life of me figure out how to implement it. I'm almost certainly missing something.

You can use some awesome generating function magic from combinatorics to solve this.

All you need to do is extract the coefficient on x^200 term from the OGF 1/((1-x)(1-x^2)(1-x^5)(1-x^10)(1-x^20)(1-x^50)(1-x^100)(1-x^200)). I actually just recently wrote code that would do just that.

User avatar
MarkGyver
Posts: 29
Joined: Sun Nov 09, 2008 6:56 am UTC

Re: Project Euler

Postby MarkGyver » Sat Jul 17, 2010 6:36 am UTC

hobojoe3001 wrote:On 910107:
After the uncouth but helpful answer leak, I checked my length function against that number.
themuffinking, I'm guessing you used Java.
When the leaked number is used as the start of that sequence, eventually the terms of the sequence exceed Java's maximum integer value, and so roll over to large negative numbers.
It also happens when using longs.
In short, I lawl'd.

My Java code gave the correct answer using longs, though I cannot guarantee that it didn't do anything wrong to get the right result.

Code: Select all

public class Problem_014 {
   public static void main(String[] args) {
      int longest = 0, start = 0;
      for (int i = 1; i < 1000000; i += 2) {
         int n = i;
         while (n < 1000000) {
            n *= 2;
         }
         int count = collatzLength(n);
         if (count > longest) {
            longest = count;
            start = i;
         }
      }

      System.out.println(start);
   }

   private static int collatzLength(long n) {
      int count = 0;
      while (n != 1) {
         if (n % 2 == 0) {
            n /= 2;
            count++;
         } else {
            n = (3 * n + 1) / 2;
            count += 2;
         }
      }
      return count;
   }
}
Generation 0: The first time you see this, copy it into your signature and change it so that it looks like you inspired this signature. Social experiment.

User avatar
phlip
Restorer of Worlds
Posts: 7543
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Project Euler

Postby phlip » Sat Jul 17, 2010 7:22 am UTC

I think I solved 31 with dynamic programming...
Spoiler:
let f(n,m) = number of ways of making n pence with only the first m coins, find f(200,8)
Spoiler:
f(0,m) = 1
f(n,0) = 0 [for n>0]
f(n,m) = f(n,m-1) [for n < coinm]
f(n,m) = f(n,m-1) + f(n - coinm, m) [for n ≥ coinm]
where coin1 = 1, coin2 = 2, ..., coin8 = 200

The second parameter is needed to avoid double-counting combinations

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

qbg
Posts: 586
Joined: Tue Dec 18, 2007 3:37 pm UTC

Re: Project Euler

Postby qbg » Sat Jul 17, 2010 4:49 pm UTC

An easier way of solving problem 31?

Spoiler:

Code: Select all

Make an array with indexes 0..200
Set the value at 0 to 1
For each i in [1..200]:
  Let s be the sum of the values at i-j (or 0 if out of range) for j in {1, 2, 5, 10, 20, 50, 100, 200}
  Set the value at i to s
Return the value at 200

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: Project Euler

Postby Tirian » Sat Jul 17, 2010 5:38 pm UTC

That's so easy it would give you the wrong answer. a[3] would be 3 using your algorithm, but there are only 2 ways of making change for 3 pence. Your problem is that you are counting 1+2 and 2+1 as separate.

qbg
Posts: 586
Joined: Tue Dec 18, 2007 3:37 pm UTC

Re: Project Euler

Postby qbg » Sat Jul 17, 2010 7:13 pm UTC

Tirian wrote:That's so easy it would give you the wrong answer. a[3] would be 3 using your algorithm, but there are only 2 ways of making change for 3 pence. Your problem is that you are counting 1+2 and 2+1 as separate.

Ah, true.

Well, my previous method give me the right answer in about 50 msec using my Clojure implementation.

User avatar
Macbi
Posts: 941
Joined: Mon Apr 09, 2007 8:32 am UTC
Location: UKvia

Re: Project Euler

Postby Macbi » Thu Jul 22, 2010 4:32 pm UTC

I'm stuck on 22 (the one where you have to sort a list of names). I'm working in C, I've done it before in python. At the moment my program finds the number of names in the list, and the length of the longest name, and then creates an array of the appropriate size, initialises all its entries to \0's and then fills it up with the names from the file. I haven't written any sorting stuff yet. What I'm trying to do at the moment is print the first few names just to make sure they're going into the array okay. I've tried:

Code: Select all

#include <stdio.h>
[...]//Make array and put names in it.
    for(j=0;j<100;++j){
            printf("%s\n",namesarray[0][j]);
    }
[...]
But that clearly won't (and doesn't) work, since namesarray[0][j] is a char and not a string. I've read a couple of tutorials on pointers, but there's clearly something I'm not grokking. I can't just continue on with the problem, because I'm bound to need to do the same thing when handling strings in quicksort.
    Indigo is a lie.
    Which idiot decided that websites can't go within 4cm of the edge of the screen?
    There should be a null word, for the question "Is anybody there?" and to see if microphones are on.

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: Project Euler

Postby Tirian » Thu Jul 22, 2010 5:01 pm UTC

My C is very rusty, but you do print a string by pointing to a char. You've got a "%s" instead of a "%c" in the printf, so the program knows that it should print all of the characters until it reaches a \0.

My simple guess is that namesarray[j][0] (or, better yet, namesarray[j] since an array pointer already points to the first element of the array) is worth checking to see if that isn't your problem. But I wonder if things aren't working because your array loading really isn't working the way it should.

User avatar
Macbi
Posts: 941
Joined: Mon Apr 09, 2007 8:32 am UTC
Location: UKvia

Re: Project Euler

Postby Macbi » Thu Jul 22, 2010 5:38 pm UTC

My array loading's fine since I can check it char by char and everything comes out perfectly.
Here's the full code if anyone wants to look at it:

Code: Select all

#include <stdio.h>

int main(void){
    FILE *namesfile;
    namesfile=fopen("Euler22Text.txt","r");
    int c=0,number=1,length=0,current=1;
    while(1){ //finds the number of names and max length
        c=getc(namesfile);
        if (c<0) break; //end of file
        if (c==44) ++number; //comma
        if (c==34) {length=(current>length)?current:length; current=1;}//quotes
        if (c>=65) ++current;//capital letter
    }
    rewind(namesfile);
    printf("%d,%d\n",length,number);
    char namesarray[length][number];
    int x=0,y=0;
    for(y=0;y<number;++y){//initialise array to \0
        for(x=0;x<length;++x){
            namesarray[x][y]=0;
        }
    }
    x=0; y=0;
    while(1){//load array
        c=getc(namesfile);
        if (c<34) break;
        if (c==44) ++y;
        if (c==34) {x=0;}
        if (c>=65) {namesarray[x++][y]=c;}
    }
    printf("Loaded array\n");
//    for(y=0;y<number;++y){ //prints array character by character
//        for(x=0;x<length;++x){
//            printf("%c",namesarray[x][y]);
//        }
//    printf("|\n");
//    }
    for(y=0;y<number;++y){
        printf("%s\n",namesarray[0][y]);
    }
    return 0;
}

With Euler22Text.txt being a longer version of this:

Code: Select all

"MARY","PATRICIA","LINDA","BARBARA"

(No end-of-file newline)

Neither namesarray[y][0] or namesarray[y] work, although using namesarray[y] produces:

Code: Select all

9,4
Loaded array
MPLBAAIARTNRYRDB
AAIARTNRYRDB
RTNRYRDB
YRDB
    Indigo is a lie.
    Which idiot decided that websites can't go within 4cm of the edge of the screen?
    There should be a null word, for the question "Is anybody there?" and to see if microphones are on.

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

Re: Project Euler

Postby jaap » Thu Jul 22, 2010 6:17 pm UTC

Macbi,

A two-dimensional array, for example char a[3][4];, is arranged in memory in the following order.
a[0][0], a[0][1], a[0][2], a[0][3], a[1][0], a[1][1], a[1][2], a[1][3], a[2][0], a[2][1], a[2][2], a[2][3]

Characters must be consecutive in memory to represent a string so if you are storing strings in a two-dimensional array then the first index indicates the string, the second indicates the character within that string. Then a[0] is can be used as a char pointer, pointing to the first string, a[1] points to the second, etc. In this example they are of length at most 3, which needs 4 chars including the terminating zero.

Macbi wrote:

Code: Select all

MPLBAAIARTNRYRDB
AAIARTNRYRDB
RTNRYRDB
YRDB


You can see that you used the indices the wrong way around, as the names appear vertical - the first column reads MARY, etc.

By the way, there are better ways to read a string than doing it one character at a time, for example scanf, or fgets.
Macbi wrote:

Code: Select all

    char namesarray[length][number];
This is a construct that only works in C99. Keep in mind that the 1999 C standard is not as commonly in use as the C89 standard in which this doesn't work.

User avatar
Macbi
Posts: 941
Joined: Mon Apr 09, 2007 8:32 am UTC
Location: UKvia

Re: Project Euler

Postby Macbi » Thu Jul 22, 2010 6:24 pm UTC

jaap wrote:Macbi,

A two-dimensional array, for example char a[3][4];, is arranged in memory in the following order.
a[0][0], a[0][1], a[0][2], a[0][3], a[1][0], a[1][1], a[1][2], a[1][3], a[2][0], a[2][1], a[2][2], a[2][3]
Ah, thank you. That explains a lot of confusion I had with pointers as well.
Macbi wrote:

Code: Select all

    char namesarray[length][number];
This is a construct that only works in C99. Keep in mind that the 1999 C standard is not as commonly in use as the C89 standard in which this doesn't work.
[/quote] How would this be done in C89? With malloc?

EDIT: It all works as expected now, thank you again.
    Indigo is a lie.
    Which idiot decided that websites can't go within 4cm of the edge of the screen?
    There should be a null word, for the question "Is anybody there?" and to see if microphones are on.

keeperofdakeys
Posts: 658
Joined: Wed Oct 01, 2008 6:04 am UTC

Re: Project Euler

Postby keeperofdakeys » Mon Nov 01, 2010 9:20 am UTC

So, problem 83.
I have solved problem 81 and 82, but I have no idea how to go for 83.
Spoiler for possible give-aways of earlier problems:
Spoiler:
So I thought about a method of adding the minimum paths, like 81. The problem with this is that being able to move in any direction means that this will not work. The method I used for 82, which finds the minimum path for each cell in each column won't work, as I can't make the problem smaller (like columns in 82). The only other possibility I can think of is an optimised brute-force, that has the problems of cycles and maybe not meeting the end-point. It also doesn't help that I wish to implement this in a functional programming language, when I am still learning to think functionally.

Any kind of pointers people could give me towards thinking of an algorithm would be appreciated.

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

Re: Project Euler

Postby jaap » Mon Nov 01, 2010 10:57 am UTC

keeperofdakeys wrote:So, problem 83.

Spoiler:
In 81, when you came to a new cell, you could immediately work out what the minimum value was to get to that cell, because you had perfect knowledge from the adjacent cells. In 82 this was no longer the case. There you first have a provisional best value from knowledge from one or two directions, which then gets updated as knowledge is gained from the other directions. For 83 a similar thing holds. You may be able to update a cell's provisional best value using the provisional value from the adjacent cells. That value may still not be the perfect correct answer, but it is better than before. Now think about what it would mean if no more such updates could be made.

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

Re: Project Euler

Postby Xanthir » Thu Nov 04, 2010 1:58 pm UTC

Or, if you want the simple algorithm answer to 83:

Spoiler:
Use the A* pathfinding algorithm. You can use almost the exact same thing for 81, 82, and 83.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Bubbles McCoy
Posts: 1106
Joined: Wed Jul 09, 2008 12:49 am UTC
Location: California

Re: Project Euler

Postby Bubbles McCoy » Fri Nov 05, 2010 11:54 am UTC

@Xanthir -
Spoiler:
Did you manage to come up with a good forward-looking estimation for use in A*? I more or less just used Dijkstras, I guess you could probably just measure the minimum number of steps to reach the destination and multiply by a reasonable average step cost, but I'm having a hard time visualizing how you'd avoid cases where the estimation overshoots.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 7 guests