## Project Euler

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

Moderators: phlip, Moderators General, Prelates

Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Project Euler

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

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

Code: Select all

`invrem x y = rem y xrecurringcycle 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 troubleperiodlength n orig_n xs    | hasperiod n orig_n xs   = n   | otherwise      = periodlength (n+1) orig_n xspl 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?

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

### Re: Project Euler

(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.

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

### Re: Project Euler

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!

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

### Re: Project Euler

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]

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

### Re: Project Euler

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.

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

### Re: Project Euler

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.

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

### Re: Project Euler

[obvious]Prime number generator[/obvious]

Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Project Euler

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

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

### Re: Project Euler

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?

Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Project Euler

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

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

### Re: Project Euler

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

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

### Re: Project Euler

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 = 3b = borig = 4c = corig = 5for 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. )

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

### Re: Project Euler

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 = 3b = borig = 4c = corig = 5for 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).

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

### Re: Project Euler

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). It's always so obvious when you see it written out by someone else. Thanks.

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

### Re: Project Euler

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 stealdef _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 clocktimestart = clock()primes = _erasthonessieve(2000004) #preseeded with sieve, and memoizedprint "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 += 2def 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 pfacsdef allfactors(n):    facs =  + 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 facsdef 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 facsfib = [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 problemsdef 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 idef 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 calcmaxdef 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*b+b*b==b*b:                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 dprob14dic = {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 adef problem14():    """Which starting number, under one million, produces the longest chain?"""    a =     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

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?

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

### Re: Project Euler

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 3x = range(0,1000,3)#Multiples of 5y = range(0,1000,5)#Changing each into a set to perform functionsthree = set(x)five = set(y)#Changing to include numbers in 3 or 5 but not both so that I don't have duplicatesanswer = five.symmetric_difference(three)#Find sum of all elements that are multiples of 3 and 5print 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

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

### Re: Project Euler

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.

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

### Re: Project Euler

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

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. kriel
Posts: 923
Joined: Thu Feb 07, 2008 2:58 pm UTC
Location: Somewhere I'm not.
Contact:

### Re: Project Euler

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

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'.

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

### Re: Project Euler

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.

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

### Re: Project Euler

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

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.

MarkGyver
Posts: 41
Joined: Sun Nov 09, 2008 6:56 am UTC

### Re: Project Euler

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.

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

### Re: Project Euler

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

An easier way of solving problem 31?

Spoiler:

Code: Select all

`Make an array with indexes 0..200Set the value at 0 to 1For 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 sReturn the value at 200`

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

### Re: Project Euler

That's so easy it would give you the wrong answer. a 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

Tirian wrote:That's so easy it would give you the wrong answer. a 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.

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

### Re: Project Euler

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[j]);    }[...]`
But that clearly won't (and doesn't) work, since namesarray[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

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] (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.

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

### Re: Project Euler

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[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] or namesarray[y] work, although using namesarray[y] produces:

Code: Select all

`9,4Loaded arrayMPLBAAIARTNRYRDBAAIARTNRYRDBRTNRYRDBYRDB`
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.

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

### Re: Project Euler

Macbi,

A two-dimensional array, for example char a;, is arranged in memory in the following order.
a, a, a, a, a, a, a, a, a, a, a, a

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 is can be used as a char pointer, pointing to the first string, a 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

`MPLBAAIARTNRYRDBAAIARTNRYRDBRTNRYRDBYRDB`

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.

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

### Re: Project Euler

jaap wrote:Macbi,

A two-dimensional array, for example char a;, is arranged in memory in the following order.
a, a, a, a, a, a, a, a, a, a, a, a
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

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.

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

### Re: Project Euler

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.

Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Project Euler

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

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

### Re: Project Euler

@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.