Project Euler

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

Moderators: phlip, Moderators General, Prelates

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

Re: Project Euler

Postby Xanthir » Thu Feb 26, 2009 4:52 pm UTC

You absolutely, positively have to implement some prime/factoring functions. You won't get very far without that. If your language doesn't have decent matrix support, then yeah, go ahead and write some of that as well.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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 Feb 26, 2009 6:20 pm UTC

Functions (and type signature) in my personal hacker library I've had the most use for in PE problems:

primes :: [Integer] (Infinite list of all primes)
isPrime :: Integer -> Bool
factorize :: Integer -> [Integer]
factors :: Integer -> [Integer] (same as factorize, but each appears only once)
fibs :: [Integer] (fibonacci sequence)
permute :: [a] -> [[a]]
isPalindrome :: (Eq a) => [a] -> Bool
powerSet :: [a] -> [[a]]
divisors :: Integer -> [Integer]
contains' :: (Ord a) => a -> [a] -> Bool (True if an element is in a list, assuming the list is sorted. Works on infinite lists)

I haven't had any use for matrixes myself so far, but I don't really know any matrix math so I wouldn't know how to use it properly.
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
mabufo
Posts: 105
Joined: Sun Sep 09, 2007 11:17 pm UTC

Re: Project Euler

Postby mabufo » Thu Feb 26, 2009 10:11 pm UTC

Berengal wrote:Functions (and type signature) in my personal hacker library I've had the most use for in PE problems:

primes :: [Integer] (Infinite list of all primes)
isPrime :: Integer -> Bool
factorize :: Integer -> [Integer]
factors :: Integer -> [Integer] (same as factorize, but each appears only once)
fibs :: [Integer] (fibonacci sequence)
permute :: [a] -> [[a]]
isPalindrome :: (Eq a) => [a] -> Bool
powerSet :: [a] -> [[a]]
divisors :: Integer -> [Integer]
contains' :: (Ord a) => a -> [a] -> Bool (True if an element is in a list, assuming the list is sorted. Works on infinite lists)

I haven't had any use for matrixes myself so far, but I don't really know any matrix math so I wouldn't know how to use it properly.


Thank you for the list. Forgive me for asking though, what is powerset and permute?

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

Re: Project Euler

Postby Xanthir » Thu Feb 26, 2009 10:23 pm UTC

(powerset '(1 2 3)) => (nil (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3))

(permute '(1 2 3)) => ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
headprogrammingczar
Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: Project Euler

Postby headprogrammingczar » Fri Feb 27, 2009 12:18 am UTC

Xanthir wrote:(powerset '(1 2 3)) => (nil (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3))

(permute '(1 2 3)) => ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))

Those would be useful even outside PE problems.
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you

User avatar
JBJ
Posts: 1263
Joined: Fri Dec 12, 2008 6:20 pm UTC
Location: a point or extent in space

Re: Project Euler

Postby JBJ » Fri Feb 27, 2009 1:31 pm UTC

Xanthir wrote:You absolutely, positively have to implement some prime/factoring functions. You won't get very far without that. If your language doesn't have decent matrix support, then waffle, go ahead and write some of that as well.

I heartily agree with getting/creating some standard functions for PE.
I only learned of PE about a week ago (Thanks XKCD!) and so far have finished 15 of the easy ones.

I'm doing them in VBScript, which admittedly doesn't have the greatest math ability. All the more challenging, eh?
But the loose data types allowed me to create some functions for adding and multiplying very large numbers ( > 1.7 E308) by converting them to strings and running them through basic multiplying and adding algorithms. This came in pretty useful for some of the questions for adding the sum of digit questions, or like Q25, the first Fibonacci to have 1000 digits. Got the answer in less than 15 seconds.

I've also got a basic prime generator and prime test which worked fine for the first few problems, although I should probably look into finding a more streamlined one. Q10 for finding the sum of all primes below 2 million slightly exceeded the 1-minute guideline. Okay, it took two minutes. I didn't revamp that one since I still got the answer in what I considered a reasonable amount of time, but I know I'll have to going forward.
So, you sacked the cocky khaki Kicky Sack sock plucker?
The second cocky khaki Kicky Sack sock plucker I've sacked since the sixth sitting sheet slitter got sick.

Gumbitha
Posts: 10
Joined: Tue Feb 24, 2009 6:49 am UTC

Re: Project Euler

Postby Gumbitha » Sat Feb 28, 2009 11:45 pm UTC

I'm stuck on number 10. Both methods of prime number generation I have seem to give the same exact answer,
Spoiler:
1179908154

Which is regarded as wrong.

My "solution":
Spoiler:

Code: Select all

/*The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.*/

#include <iostream>
#include <cmath>

using namespace std;


int main(void) {
   int root = 1;
   int n = 3;
   int p = 1;
   int prime = 1;
   int c = 0;
   int sum = 2;
   static int PRIMELIST[1000000] = {2};
   


   for (int i = 3; i < 2000000; i+=2) {
      root = sqrt((double)i) + 1;

       for(c = 0; PRIMELIST[c] < root && PRIMELIST[c] != '\0'; c++) {
      if (i % PRIMELIST[c] == 0) {
         prime = 0;      
         //cout << i << " is not prime " << PRIMELIST[c] << " is a factor \n";
         break;
         }
      }
      if (prime == 1) {   
         cout << i << " is prime " << p + 1 << "\n" ;
         PRIMELIST[p] = i;
         p++;
         sum += i;
      }      
         prime = 1;
      
   }
   
cout << "Sum is " << sum << "\n";
return 0;   
}

/*
int main(void) {
   int root = 1;
   int n = 3;
   int p = 1;
   int prime = 1;
   int sum = 2;
   for (int i = 3; i < 2000000; i+=2) {
      root = sqrt((double)i) + 1;
      for (n = 3; n <= root; n += 2){
         if (i % n == 0) {
            prime = 0;      
            //cout << i << " is not prime " << n << " is a factor \n";
            break;
         }
      }
      if (prime == 1) {
         p++;
         cout << i << " is prime " << p + 1 << "\n" ;
         sum += i;
      }      
         prime = 1;
   }
   cout << "Sum is " << sum << "\n";
return 0;   
}
*/

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 Mar 01, 2009 12:21 am UTC

Spoiler:
unsigned 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.

Gumbitha
Posts: 10
Joined: Tue Feb 24, 2009 6:49 am UTC

Re: Project Euler

Postby Gumbitha » Sun Mar 01, 2009 1:08 am UTC

Oh, stupid me. I was going to change that and forgot. Many thanks :)

User avatar
Guff
Posts: 165
Joined: Thu Jan 03, 2008 11:56 pm UTC

Re: Project Euler

Postby Guff » Sun Mar 01, 2009 4:31 am UTC

I just made it to Level 2. :)

I also just looked at 234, and have a solution that should work but is currently far too slow. Based on my estimates, I think it would take at least a few hours to run. Thing is, that's after I implemented some memoization-type functionality that dramatically sped it up (based on the idea that
Spoiler:
non-squares of primes will have the same lps and ups as others when floor(sqrt(n)) is the same).

Not sure what else I can do in terms of optimization. I think I'm going to have to use maths.
Aw, shucks. :(

codebliss
Posts: 12
Joined: Wed Mar 04, 2009 3:30 am UTC

Re: Project Euler

Postby codebliss » Wed Mar 04, 2009 3:56 am UTC

Anybody else here love F#? I'll post a bunch of solutions tomorrow and some library code.

It's incredibly fun =D

akashra
Posts: 503
Joined: Tue Jan 01, 2008 6:54 am UTC
Location: Melbourne, AU
Contact:

Re: Project Euler

Postby akashra » Thu Mar 05, 2009 12:49 am UTC

I've been playing around with CUDA lately, so I'll be taking a crack at a few of the Euler problems making use of a GPU. Some problems it's appropriate, others it's not worthwhile or suitable (it's *great* for bruteforcing problems like 7 and 11, but the dataset is a bit small for it to really be worthwhile :)
( find / -name \*base\* -exec chown us : us { } \ ; )

rustyocean
Posts: 1
Joined: Fri Mar 13, 2009 5:10 pm UTC

Re: Project Euler

Postby rustyocean » Fri Mar 13, 2009 5:16 pm UTC

I have been working on project euler 234, have come up with this so far, but I do know this code will take foreever to run, any ideas ?

Spoiler:

Code: Select all

def isSemiDivisible(n,lpsNum,upsNum):
    isTrue = (n%lpsNum == 0)
    isTrueAsWell = (n%upsNum == 0)

    if isTrue == True and isTrueAsWell == True:
        return False

    if isTrue == False and isTrueAsWell == False:
        return False

    return True

def lpsAlt(x,primes):
    y = 0

    while ( y < len(primes) ):
        if primes[y] >= x:
            if primes[y] == x:
                return x
            else:
                return primes[y-1]
        y += 1

def upsAlt(x,primes):
    for prime in primes:
        if prime >= x:
            return prime




while x < 999966663334:
    sqrtX = math.sqrt(x)
    #print sqrtX
   
    lpsNum = lpsAlt(sqrtX, primes)

    #print lpsNum
    upsNum = upsAlt(sqrtX, primes)

    #print upsNum

    if isSemiDivisible(x,lpsNum,upsNum):
        print x,
        print " " +str(lpsNum),
        print " " + str(upsNum)
       
        count += x
    x += 1
print count

halbarad
Posts: 394
Joined: Mon Dec 08, 2008 11:49 am UTC

Re: Project Euler

Postby halbarad » Tue Mar 24, 2009 2:57 pm UTC

I'm kind of stuck on problem 20, I have the solution (or what I think is the solution) but the text box to input it is too small. The code I wrote in java is:

Spoiler:

Code: Select all


import java.math.*;

public class Main {

    public static void main(String[] args) {
       
        BigInteger total = new BigInteger("1");
        BigInteger countBig;
       
        int count = 2;
        int lineCount = 0;

        while (count != 101) {
            countBig = convertBig(count);
            System.out.println("Sum of: " + countBig + " X " + total + " = ");
            total = total.multiply(countBig);
            count++;
            lineCount++;
           
        }

        System.out.println(total);
        System.out.println(lineCount);
    }
   
    private static BigInteger convertBig(int n) {
     
        int bigConv = n;
        String bigInt = Integer.toString(bigConv);
        BigInteger returnInt = new BigInteger(bigInt);

        return returnInt;
    }
}


I added the line count so I could see how many calculations had been performed.


I have ran this both from 1 to 100 and from 100 to 1 and the result I get is alway:

Spoiler:
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000


Any help?

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 » Tue Mar 24, 2009 3:01 pm UTC

I'd advise you to go re-read the problem.
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
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Project Euler

Postby jaap » Tue Mar 24, 2009 3:01 pm UTC

halbarad wrote:I'm kind of stuck on problem 20, I have the solution (or what I think is the solution) but the text box to input it is too small. Any help?


Read the question again:
Project Euler wrote:Find the sum of the digits in the number 100!

douglasm
Posts: 630
Joined: Mon Apr 21, 2008 4:53 am UTC

Re: Project Euler

Postby douglasm » Tue Mar 24, 2009 3:04 pm UTC

Your code appears to compute total = 100! correctly, I think. Now add up the digits.

halbarad
Posts: 394
Joined: Mon Dec 08, 2008 11:49 am UTC

Re: Project Euler

Postby halbarad » Tue Mar 24, 2009 3:23 pm UTC

douglasm wrote:Your code appears to compute total = 100! correctly, I think. Now add up the digits.


Turns out that I fail at basic reading skills.

Thanks.

Cecil
Posts: 23
Joined: Tue Jan 16, 2007 3:05 am UTC

Re: Project Euler

Postby Cecil » Wed Mar 25, 2009 5:14 pm UTC

Hint for the couple people stuck on 234 (also a good tip for PE in general):

Write a quick-and-dirty brute force and use it to print out the first few n along with their corresponding lps() and ups(). See if you notice a pattern that you can use to simplify the problem.
More xkcd than your mom.

edanite
Posts: 56
Joined: Sat Jun 23, 2007 8:32 pm UTC

Re: Project Euler

Postby edanite » Wed Apr 22, 2009 11:01 pm UTC

I'm having problems with #80. My code appears to take square roots and add up the digits after the decimal, but the final answer is wrong. Can someone tell me if these pairs of n:decimal sum of sqrt(n) are correct to see if my code is working?
Spoiler:

Code: Select all

2:475
3:441
5:472
6:470
7:397
8:463
10:456
11:482
12:403
13:416
14:483
15:498

I can post these pairs all the way up to 99:438 if someone really wants to check every one.

User avatar
Dropzone
Posts: 405
Joined: Sun Dec 30, 2007 10:12 pm UTC
Location: North Lincs., UK

Re: Project Euler

Postby Dropzone » Thu Apr 23, 2009 12:16 am UTC

It looks like your sums are coming out slightly wrong; the ones you should be getting are:
Spoiler:

Code: Select all

2:475
3:441
5:473
6:471
7:398
8:465
10:459
11:484
12:406
13:418
14:485
15:500

User avatar
headprogrammingczar
Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: Project Euler

Postby headprogrammingczar » Thu Apr 23, 2009 12:29 am UTC

Rounding error is what I see. It goes from correct to off-by-one to off-by-two, and it happens without any pattern I can see.
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you

edanite
Posts: 56
Joined: Sat Jun 23, 2007 8:32 pm UTC

Re: Project Euler

Postby edanite » Thu Apr 23, 2009 1:15 am UTC

headprogrammingczar wrote:Rounding error is what I see. It goes from correct to off-by-one to off-by-two, and it happens without any pattern I can see.


That was my thought too. I tried all the rounding schemes I could think of (up, down, half up, half down, half even, truncate), got several different answers, but none of them were right. I'm going to look deeper.

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

Re: Project Euler

Postby levicc00123 » Sun May 24, 2009 4:44 pm UTC

Code: Select all

#!/usr/bin/env python
import sys
def ReverseNumber(n, partial=0):
    if n == 0:
        return partial
    return ReverseNumber(n / 10, partial * 10 + n % 10)

results = []

for x in xrange(100, 1000):
    for y in xrange(100, 1000):
        r = x*y
        ip = ReverseNumber(r)
        if ip == r:
            results.append(r)
        else:
            pass
results.sort()
ss = str(results)
print ss
sys.exit(0)


I just got done with PE#4 and I got the right answer, but I've noticed I've been getting each number twice in the results list.

Spoiler:

Code: Select all

[10201, 11211, 11211, 12221, 12221, 12321, 13231, 13231, 13431, 13431, 14241, 14241, 14541, 14541, 14641, 15151, 15151, 15251, 15251, 15351, 15351, 15651, 15651, 15851, 15851, 16261, 16261, 16761, 16761, 17271, 17271, 17871, 17871, 18081, 18081, 18281, 18281, 18981, 18981, 19291, 19291, 19591, 19591, 20002, 20002, 20202, 20202, 20402, 20402, 20502, 20502, 20502, 20502, 21012, 21012, 21012, 21012, 21112, 21112, 21112, 21112, 21312, 21312, 21312, 21312, 21412, 21412, 21412, 21412, 21712, 21712, 21812, 21812, 21912, 21912, 22022, 22022, 22022, 22022, 22422, 22422, 22422, 22422, 22922, 22922, 23232, 23232, 23232, 23232, 23432, 23432, 23432, 23432, 23532, 23532, 23532, 23532, 23532, 23532, 23632, 23632, 23932, 23932, 24442, 24442, 24442, 24442, 24642, 24642, 24742, 24742, 25152, 25152, 25252, 25252, 25252, 25252, 25452, 25452, 25452, 25452, 25652, 25652, 25652, 25652, 25752, 25752, 25752, 25752, 25752, 25752, 26062, 26062, 26162, 26162, 26162, 26162, 26462, 26462, 26462, 26462, 26562, 26562, 26862, 26862, 26862, 26862, 26962, 26962, 27072, 27072, 27072, 27072, 27472, 27472, 27472, 27472, 27572, 27572, 27572, 27572, 27772, 27772, 27772, 27772, 27872, 27872, 27872, 27872, 27972, 27972, 27972, 27972, 27972, 27972, 27972, 27972, 28182, 28182, 28182, 28182, 28282, 28282, 28482, 28482, 28482, 28482, 28782, 28782, 28782, 28782, 29192, 29192, 29392, 29392, 29492, 29492, 29492, 29492, 29592, 29592, 29592, 29592, 29792, 29792, 29792, 29792, 29792, 29792, 29892, 29892, 29892, 29892, 29892, 29892, 29992, 29992, 30003, 30003, 30303, 30303, 30303, 30303, 30603, 30603, 31313, 31313, 31413, 31413, 31613, 31613, 32523, 32523, 32623, 32623, 33033, 33033, 33033, 33033, 33233, 33233, 33333, 33333, 33633, 33633, 33633, 33633, 34243, 34243, 34443, 34443, 34643, 34643, 34743, 34743, 35453, 35453, 35653, 35653, 35853, 35853, 35953, 35953, 36663, 36663, 36663, 36663, 36863, 36863, 36963, 36963, 37073, 37073, 37373, 37373, 37673, 37673, 37873, 37873, 37973, 37973, 38383, 38383, 38683, 38683, 39093, 39093, 39593, 39593, 39693, 39693, 39693, 39693, 39893, 39893, 40004, 40004, 40004, 40004, 40304, 40304, 40404, 40404, 40404, 40404, 40404, 40404, 40404, 40404, 40504, 40504, 40504, 40504, 40704, 40704, 40704, 40704, 40704, 40704, 40704, 40704, 40804, 40804, 40804, 41114, 41114, 41314, 41314, 41514, 41514, 41514, 41514, 41514, 41514, 41814, 41814, 41814, 41814, 41814, 41814, 42024, 42024, 42024, 42024, 42024, 42024, 42024, 42024, 42224, 42224, 42224, 42224, 42224, 42224, 42224, 42224, 42224, 42224, 42624, 42624, 42624, 42624, 42624, 42624, 42624, 42624, 42624, 42624, 42824, 42824, 42824, 42824, 42824, 42824, 42924, 42924, 42924, 42924, 42924, 42924, 43134, 43134, 43134, 43134, 43434, 43434, 43434, 43434, 43434, 43434, 43734, 43734, 43734, 43734, 43834, 43834, 43834, 43834, 44044, 44044, 44044, 44044, 44044, 44044, 44044, 44044, 44144, 44144, 44144, 44144, 44344, 44344, 44444, 44444, 44544, 44544, 44544, 44544, 44544, 44544, 44544, 44544, 44744, 44744, 44744, 44744, 44744, 44744, 44844, 44844, 44844, 44844, 44844, 44844, 44844, 44844, 44944, 44944, 44944, 45154, 45154, 45154, 45154, 45254, 45254, 45254, 45254, 45854, 45854, 45854, 45854, 45954, 45954, 45954, 45954, 45954, 45954, 46364, 46364, 46364, 46364, 46464, 46464, 46464, 46464, 46464, 46464, 46464, 46464, 46464, 46464, 46664, 46664, 46764, 46764, 46864, 46864, 46864, 46864, 46864, 46864, 46964, 46964, 46964, 46964, 47174, 47174, 47174, 47174, 47674, 47674, 47674, 47674, 47874, 47874, 47874, 47874, 47874, 47874, 47974, 47974, 48184, 48184, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48484, 48484, 48884, 48884, 48884, 48884, 48884, 48884, 48984, 48984, 48984, 48984, 48984, 48984, 49494, 49494, 49494, 49494, 49494, 49494, 49594, 49594, 49594, 49594, 49794, 49794, 49794, 49794, 49894, 49894, 49894, 49894, 50005, 50005, 50505, 50505, 50505, 50505, 50505, 50505, 50505, 50505, 50605, 50605, 51015, 51015, 51315, 51315, 51415, 51415, 51615, 51615, 51615, 51615, 51615, 51615, 51815, 51815, 52125, 52125, 52125, 52125, 52325, 52325, 52325, 52325, 52325, 52325, 52425, 52425, 52525, 52525, 52625, 52625, 52725, 52725, 52725, 52725, 52925, 52925, 53235, 53235, 53235, 53235, 53235, 53235, 53235, 53235, 53535, 53535, 53535, 53535, 53835, 53835, 53835, 53835, 53935, 53935, 53935, 53935, 54145, 54145, 54145, 54145, 54945, 54945, 54945, 54945, 54945, 54945, 54945, 54945, 55055, 55055, 55055, 55055, 55255, 55255, 55555, 55555, 55755, 55755, 55755, 55755, 55755, 55755, 55755, 55755, 55955, 55955, 56165, 56165, 56265, 56265, 56265, 56265, 56265, 56265, 56465, 56465, 56565, 56565, 56865, 56865, 57275, 57275, 57375, 57375, 57375, 57375, 57375, 57375, 57375, 57375, 57475, 57475, 57475, 57475, 57575, 57575, 57575, 57575, 57875, 57875, 58185, 58185, 58485, 58485, 58685, 58685, 58985, 58985, 59095, 59095, 59295, 59295, 59295, 59295, 59495, 59495, 59595, 59595, 59595, 59595, 59895, 59895, 59895, 59895, 59995, 59995, 60006, 60006, 60006, 60006, 60006, 60006, 60306, 60306, 60306, 60306, 60606, 60606, 60606, 60606, 60606, 60606, 60606, 60606, 60606, 60606, 60606, 60606, 60706, 60706, 60706, 60706, 61016, 61016, 61016, 61016, 61116, 61116, 61516, 61516, 61516, 61516, 61716, 61716, 61716, 61716, 61716, 61716, 61716, 61716, 62426, 62426, 62526, 62526, 62626, 62626, 62626, 62626, 62726, 62726, 62826, 62826, 62826, 62826, 62926, 62926, 63036, 63036, 63036, 63036, 63036, 63036, 63036, 63036, 63036, 63036, 63336, 63336, 63336, 63336, 63336, 63336, 63336, 63336, 63336, 63336, 63336, 63336, 63336, 63336, 63336, 63336, 63536, 63536, 63536, 63536, 63536, 63536, 63736, 63736, 63736, 63736, 63936, 63936, 63936, 63936, 63936, 63936, 63936, 63936, 63936, 63936, 63936, 63936, 63936, 63936, 64246, 64246, 64446, 64446, 64546, 64546, 64746, 64746, 64746, 64746, 64746, 64746, 65056, 65056, 65056, 65056, 65056, 65056, 65156, 65156, 65156, 65156, 65556, 65556, 65656, 65656, 65656, 65656, 65856, 65856, 65856, 65856, 65856, 65856, 65856, 65856, 65856, 65856, 65856, 65856, 66066, 66066, 66066, 66066, 66066, 66066, 66066, 66066, 66066, 66066, 66066, 66066, 66466, 66466, 66466, 66466, 66566, 66566, 66666, 66666, 66666, 66666, 66766, 66766, 66766, 66766, 66866, 66866, 67076, 67076, 67176, 67176, 67176, 67176, 67276, 67276, 67276, 67276, 67276, 67276, 67776, 67776, 67876, 67876, 67876, 67876, 67976, 67976, 67976, 67976, 68086, 68086, 68186, 68186, 68186, 68186, 68286, 68286, 68486, 68486, 68486, 68486, 68586, 68586, 68586, 68586, 68586, 68586, 68586, 68586, 68686, 68686, 68786, 68786, 68786, 68786, 68886, 68886, 68886, 68886, 68886, 68886, 69296, 69296, 69296, 69296, 69296, 69296, 69496, 69496, 69496, 69496, 69496, 69496, 69496, 69496, 69596, 69596, 69596, 69596, 69596, 69596, 69696, 69696, 69696, 69696, 69696, 69696, 69696, 69696, 69696, 69696, 69696, 69696, 69696, 69696, 69696, 69996, 69996, 69996, 69996, 70007, 70007, 70307, 70307, 70707, 70707, 70707, 70707, 70707, 70707, 70807, 70807, 71117, 71117, 71217, 71217, 71217, 71217, 71817, 71817, 72027, 72027, 72027, 72027, 72627, 72627, 72927, 72927, 72927, 72927, 73337, 73337, 73437, 73437, 73537, 73537, 73937, 73937, 74347, 74347, 74347, 74347, 74447, 74447, 74547, 74547, 74847, 74847, 74947, 74947, 75057, 75057, 75057, 75057, 76167, 76167, 76167, 76167, 76167, 76167, 76167, 76167, 76467, 76467, 76867, 76867, 77077, 77077, 77077, 77077, 77677, 77677, 77777, 77777, 77877, 77877, 78287, 78287, 78387, 78387, 78987, 78987, 78987, 78987, 79097, 79097, 79297, 79297, 79497, 79497, 79497, 79497, 79597, 79597, 79797, 79797, 79897, 79897, 80008, 80008, 80008, 80008, 80008, 80008, 80208, 80208, 80408, 80408, 80408, 80408, 80608, 80608, 80608, 80608, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80908, 80908, 80908, 80908, 80908, 80908, 81018, 81018, 81618, 81618, 81618, 81618, 81618, 81618, 81718, 81718, 81918, 81918, 81918, 81918, 81918, 81918, 81918, 81918, 82128, 82128, 82128, 82128, 82128, 82128, 82128, 82128, 82128, 82128, 82128, 82128, 82228, 82228, 82228, 82228, 82328, 82328, 82328, 82328, 82628, 82628, 82628, 82628, 82728, 82728, 82728, 82728, 82928, 82928, 82928, 82928, 82928, 82928, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83638, 83638, 83738, 83738, 83738, 83738, 83838, 83838, 83838, 83838, 83838, 83838, 84048, 84048, 84048, 84048, 84048, 84048, 84048, 84048, 84048, 84048, 84048, 84048, 84148, 84148, 84148, 84148, 84148, 84148, 84348, 84348, 84348, 84348, 84348, 84348, 84348, 84348, 84348, 84348, 84348, 84348, 84448, 84448, 84448, 84448, 84448, 84448, 84448, 84448, 84448, 84448, 84448, 84448, 84448, 84448, 84448, 84448, 85058, 85058, 85158, 85158, 85158, 85158, 85158, 85158, 85158, 85158, 85358, 85358, 85358, 85358, 86268, 86268, 86268, 86268, 86268, 86268, 86268, 86268, 86268, 86268, 86668, 86668, 86768, 86768, 86768, 86768, 86768, 86768, 86768, 86768, 86768, 86768, 86768, 86768, 86868, 86868, 86868, 86868, 86868, 86868, 86868, 86868, 86868, 86868, 87078, 87078, 87178, 87178, 87278, 87278, 87278, 87278, 87478, 87478, 87478, 87478, 87978, 87978, 87978, 87978, 87978, 87978, 88088, 88088, 88088, 88088, 88088, 88088, 88088, 88088, 88088, 88088, 88088, 88088, 88088, 88088, 88288, 88288, 88288, 88288, 88288, 88288, 88688, 88688, 88688, 88688, 88788, 88788, 88788, 88788, 88788, 88788, 88788, 88788, 88888, 88888, 88888, 88888, 89198, 89198, 89198, 89198, 89298, 89298, 89298, 89298, 89298, 89298, 89298, 89298, 89298, 89298, 89498, 89498, 89598, 89598, 89598, 89598, 89598, 89598, 89598, 89598, 89698, 89698, 89698, 89698, 89798, 89798, 90009, 90009, 90009, 90009, 90109, 90109, 90209, 90209, 90909, 90909, 90909, 90909, 90909, 90909, 90909, 90909, 90909, 90909, 91719, 91719, 91719, 91719, 92129, 92129, 92229, 92229, 92329, 92329, 92529, 92529, 92529, 92529, 92629, 92629, 92829, 92829, 93639, 93639, 93639, 93639, 93839, 93839, 93939, 93939, 93939, 93939, 94149, 94149, 94249, 95259, 95259, 95259, 95259, 95559, 95559, 95659, 95659, 96369, 96369, 96669, 96669, 96869, 96869, 97079, 97079, 98189, 98189, 98289, 98289, 98289, 98289, 98489, 98489, 98589, 98589, 98789, 98789, 98889, 98889, 98889, 98889, 99099, 99099, 99099, 99099, 99099, 99099, 99099, 99099, 99099, 99099, 99199, 99199, 99299, 99299, 99599, 99599, 99699, 99699, 99699, 99699, 99799, 99799, 99899, 99899, 99999, 99999, 99999, 99999, 101101, 101101, 102201, 102201, 102201, 102201, 105501, 105501, 105501, 105501, 106601, 106601, 108801, 108801, 108801, 108801, 110011, 110011, 111111, 111111, 111111, 111111, 111111, 111111, 111111, 111111, 117711, 117711, 117711, 117711, 117711, 117711, 119911, 119911, 121121, 121121, 122221, 122221, 123321, 123321, 127721, 127721, 128821, 128821, 129921, 129921, 131131, 131131, 133331, 133331, 133331, 133331, 133331, 133331, 135531, 135531, 137731, 137731, 138831, 138831, 140041, 140041, 141141, 141141, 141141, 141141, 141141, 141141, 141141, 141141, 142241, 142241, 143341, 143341, 147741, 147741, 149941, 149941, 154451, 154451, 155551, 155551, 156651, 156651, 159951, 159951, 161161, 161161, 161161, 161161, 162261, 162261, 165561, 165561, 165561, 165561, 168861, 168861, 168861, 168861, 168861, 168861, 168861, 168861, 171171, 171171, 171171, 171171, 171171, 171171, 171171, 171171, 171171, 171171, 174471, 174471, 174471, 174471, 178871, 178871, 180081, 180081, 180081, 180081, 182281, 182281, 184481, 184481, 187781, 187781, 188881, 188881, 189981, 189981, 189981, 189981, 198891, 198891, 198891, 198891, 198891, 198891, 198891, 198891, 201102, 201102, 201102, 201102, 201102, 201102, 202202, 202202, 204402, 204402, 204402, 204402, 204402, 204402, 209902, 209902, 209902, 209902, 209902, 209902, 210012, 210012, 210012, 210012, 210012, 210012, 210012, 210012, 212212, 212212, 212212, 212212, 212212, 212212, 212212, 212212, 213312, 213312, 213312, 213312, 213312, 213312, 213312, 213312, 214412, 214412, 214412, 214412, 215512, 215512, 215512, 215512, 215512, 215512, 216612, 216612, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 220022, 220022, 221122, 221122, 221122, 221122, 221122, 221122, 222222, 222222, 222222, 222222, 222222, 222222, 222222, 222222, 222222, 222222, 222222, 222222, 222222, 222222, 225522, 225522, 225522, 225522, 225522, 225522, 227722, 227722, 231132, 231132, 231132, 231132, 231132, 231132, 232232, 232232, 232232, 232232, 232232, 232232, 232232, 232232, 232232, 232232, 232232, 232232, 234432, 234432, 234432, 234432, 234432, 234432, 234432, 234432, 234432, 234432, 234432, 234432, 234432, 234432, 234432, 234432, 235532, 235532, 238832, 238832, 238832, 238832, 238832, 238832, 239932, 239932, 239932, 239932, 239932, 239932, 239932, 239932, 239932, 239932, 242242, 242242, 244442, 244442, 244442, 244442, 246642, 246642, 246642, 246642, 249942, 249942, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 255552, 255552, 255552, 255552, 255552, 255552, 255552, 255552, 256652, 256652, 256652, 256652, 257752, 257752, 257752, 257752, 258852, 258852, 258852, 258852, 258852, 258852, 259952, 259952, 259952, 259952, 262262, 262262, 266662, 266662, 266662, 266662, 266662, 266662, 266662, 266662, 270072, 270072, 270072, 270072, 270072, 270072, 270072, 270072, 270072, 270072, 270072, 270072, 272272, 272272, 272272, 272272, 272272, 272272, 272272, 272272, 272272, 272272, 272272, 272272, 273372, 273372, 273372, 273372, 273372, 273372, 276672, 276672, 276672, 276672, 276672, 276672, 277772, 277772, 279972, 279972, 279972, 279972, 279972, 279972, 279972, 279972, 279972, 279972, 280082, 280082, 280082, 280082, 282282, 282282, 282282, 282282, 282282, 282282, 282282, 282282, 282282, 282282, 284482, 284482, 286682, 286682, 289982, 289982, 290092, 290092, 290092, 290092, 292292, 292292, 292292, 292292, 292292, 292292, 294492, 294492, 294492, 294492, 296692, 296692, 297792, 297792, 297792, 297792, 297792, 297792, 297792, 297792, 297792, 297792, 297792, 297792, 299992, 299992, 299992, 299992, 301103, 301103, 302203, 302203, 303303, 303303, 306603, 306603, 308803, 308803, 320023, 320023, 321123, 321123, 324423, 324423, 329923, 329923, 330033, 330033, 333333, 333333, 333333, 333333, 333333, 333333, 335533, 335533, 343343, 343343, 345543, 345543, 348843, 348843, 354453, 354453, 357753, 357753, 359953, 359953, 363363, 363363, 366663, 366663, 367763, 367763, 369963, 369963, 371173, 371173, 372273, 372273, 374473, 374473, 375573, 375573, 377773, 377773, 378873, 378873, 378873, 378873, 384483, 384483, 391193, 391193, 393393, 393393, 397793, 397793, 399993, 399993, 399993, 399993, 401104, 401104, 401104, 401104, 401104, 401104, 402204, 402204, 402204, 402204, 404404, 404404, 405504, 405504, 405504, 405504, 405504, 405504, 407704, 407704, 407704, 407704, 408804, 408804, 408804, 408804, 408804, 408804, 409904, 409904, 412214, 412214, 412214, 412214, 414414, 414414, 414414, 414414, 414414, 414414, 414414, 414414, 414414, 414414, 414414, 414414, 416614, 416614, 420024, 420024, 420024, 420024, 420024, 420024, 421124, 421124, 424424, 424424, 424424, 424424, 424424, 424424, 425524, 425524, 426624, 426624, 426624, 426624, 428824, 428824, 428824, 428824, 432234, 432234, 432234, 432234, 434434, 434434, 434434, 434434, 436634, 436634, 438834, 438834, 440044, 440044, 441144, 441144, 442244, 442244, 442244, 442244, 443344, 443344, 443344, 443344, 444444, 444444, 444444, 444444, 444444, 444444, 444444, 444444, 444444, 444444, 445544, 445544, 445544, 445544, 447744, 447744, 447744, 447744, 447744, 447744, 452254, 452254, 456654, 456654, 456654, 456654, 459954, 459954, 459954, 459954, 461164, 461164, 462264, 462264, 462264, 462264, 464464, 464464, 464464, 464464, 464464, 464464, 468864, 468864, 468864, 468864, 468864, 468864, 468864, 468864, 469964, 469964, 470074, 470074, 471174, 471174, 474474, 474474, 474474, 474474, 476674, 476674, 477774, 477774, 484484, 484484, 485584, 485584, 485584, 485584, 487784, 487784, 488884, 488884, 489984, 489984, 489984, 489984, 489984, 489984, 489984, 489984, 491194, 491194, 493394, 493394, 505505, 505505, 506605, 506605, 507705, 507705, 507705, 507705, 508805, 508805, 509905, 509905, 510015, 510015, 512215, 512215, 513315, 513315, 513315, 513315, 513315, 513315, 514415, 514415, 515515, 515515, 519915, 519915, 520025, 520025, 522225, 522225, 523325, 523325, 525525, 525525, 525525, 525525, 525525, 525525, 528825, 528825, 531135, 531135, 534435, 534435, 535535, 535535, 536635, 536635, 543345, 543345, 545545, 545545, 548845, 548845, 549945, 549945, 550055, 550055, 551155, 551155, 554455, 554455, 555555, 555555, 560065, 560065, 561165, 561165, 564465, 564465, 565565, 565565, 570075, 570075, 571175, 571175, 573375, 573375, 575575, 575575, 576675, 576675, 577775, 577775, 579975, 579975, 579975, 579975, 580085, 580085, 585585, 585585, 585585, 585585, 588885, 588885, 589985, 589985, 592295, 592295, 595595, 595595, 595595, 595595, 601106, 601106, 602206, 602206, 603306, 603306, 604406, 604406, 606606, 606606, 611116, 611116, 611116, 611116, 611116, 611116, 612216, 612216, 616616, 616616, 616616, 616616, 618816, 618816, 619916, 619916, 623326, 623326, 630036, 630036, 630036, 630036, 631136, 631136, 636636, 636636, 636636, 636636, 639936, 639936, 639936, 639936, 642246, 642246, 648846, 648846, 649946, 649946, 650056, 650056, 650056, 650056, 652256, 652256, 653356, 653356, 654456, 654456, 654456, 654456, 656656, 656656, 657756, 657756, 660066, 660066, 661166, 661166, 663366, 663366, 666666, 666666, 666666, 666666, 666666, 666666, 672276, 672276, 675576, 675576, 678876, 678876, 689986, 689986, 693396, 693396, 696696, 696696, 696696, 696696, 696696, 696696, 698896, 698896, 698896, 723327, 723327, 729927, 729927, 737737, 737737, 747747, 747747, 749947, 749947, 770077, 770077, 780087, 780087, 793397, 793397, 801108, 801108, 802208, 802208, 804408, 804408, 807708, 807708, 809908, 809908, 819918, 819918, 821128, 821128, 824428, 824428, 828828, 828828, 828828, 828828, 840048, 840048, 853358, 853358, 855558, 855558, 861168, 861168, 886688, 886688, 888888, 888888, 906609, 906609]


I think it's the two for loops that's causing this strange result, but I'm not sure. Where am I going wrong?
Image

User avatar
Cleverbeans
Posts: 1378
Joined: Wed Mar 26, 2008 1:16 pm UTC

Re: Project Euler

Postby Cleverbeans » Sun May 24, 2009 6:39 pm UTC

levicc00123 wrote:I think it's the two for loops that's causing this strange result, but I'm not sure. Where am I going wrong?


You're taking every possible x*y combination, and since x*y = y*x you're getting redundant entries. You can solve this in a couple ways.

Firstly, instead of using a list as your result collector, you could use a set, which will automatically gobble up the redundant entries, then after you're done with your loop turn the set into a list and sort it.

Alternately, rather then collecting all the palindromes, sorting, and returning the largest, you can check for the biggest as you go and just store the largest one in a variable. It takes up less space, and you don't have to sort the list. Here is the solution I found, notice I still double multiply.

Spoiler:

Code: Select all

def paliTest(word):
    word = list(str(word))
    drow = word[:]
    drow.reverse()
    for x in range(len(word)):
        if word[x] != drow[x]:
            return False
    return True

def p4():
    biggest = 0
    for a in range(100,1000):
        for b in range(100,1000):
            if paltest(a*b) == True and a*b > biggest:
                biggest = a*b
    return biggest
"Labor is prior to, and independent of, capital. Capital is only the fruit of labor, and could never have existed if labor had not first existed. Labor is the superior of capital, and deserves much the higher consideration." - Abraham Lincoln

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

Re: Project Euler

Postby levicc00123 » Sun May 24, 2009 7:22 pm UTC

Cleverbeans wrote:
levicc00123 wrote:I think it's the two for loops that's causing this strange result, but I'm not sure. Where am I going wrong?


You're taking every possible x*y combination, and since x*y = y*x you're getting redundant entries. You can solve this in a couple ways.

Firstly, instead of using a list as your result collector, you could use a set, which will automatically gobble up the redundant entries, then after you're done with your loop turn the set into a list and sort it.

Alternately, rather then collecting all the palindromes, sorting, and returning the largest, you can check for the biggest as you go and just store the largest one in a variable. It takes up less space, and you don't have to sort the list. Here is the solution I found, notice I still double multiply.

Spoiler:

Code: Select all

def paliTest(word):
    word = list(str(word))
    drow = word[:]
    drow.reverse()
    for x in range(len(word)):
        if word[x] != drow[x]:
            return False
    return True

def p4():
    biggest = 0
    for a in range(100,1000):
        for b in range(100,1000):
            if paltest(a*b) == True and a*b > biggest:
                biggest = a*b
    return biggest


Ah, thank you.
Image

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

Re: Project Euler

Postby phlip » Wed Jun 03, 2009 11:52 am UTC

So I'm going through Project Euler again from the top, but this time in Haskell, since you've all convinced me to try learning that language.

I got up to number 17 ("How many letters would be needed to write all the numbers in words from 1 to 1000?")... and I get it wrong. I'd already solved it in Python, along with many other PE puzzles, so the answer was on the screen for me to compare with.

So I run my original Python version, to compare the calculations... see where my new one's going wrong... and get the same wrong result. Somehow I'd managed to get the wrong result, and then typo it when entering it in the answer field (it was out by exactly 100, so it's only one digit), and get the right answer.

(Incidentally, the bug was that in both the Python and Haskell versions, I'd said that 40 is spelled with 6 letters... thinking "fourty" instead of "forty". Since there are 100 numbers that include "forty" in the name, the result was 100 too high.)

Code: Select all

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

User avatar
MHD
Posts: 630
Joined: Fri Mar 20, 2009 8:21 pm UTC
Location: Denmark

Re: Project Euler

Postby MHD » Wed Jun 03, 2009 2:13 pm UTC

On the one liner solution topic:

Primes test function:

Code: Select all

def Prime_test(number):
    assert number.__class__ is int
    assert number > 0
    if number == 2:
        return True
    if number % 2 == 0 or number == 1:
        return False
    from math import sqrt
    for i in iter(range(3,int(sqrt(number)) + 1,2)):
        if not number % i:
            return False
    return True


Determining sums:

Code: Select all

sum(Prime_test(i) for i in range(2000000))
EvanED wrote:be aware that when most people say "regular expression" they really mean "something that is almost, but not quite, entirely unlike a regular expression"

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

Re: Project Euler

Postby qbg » Wed Jun 03, 2009 8:35 pm UTC

MHD wrote:On the one liner solution topic:

Primes test function:

Code: Select all

def Prime_test(number):
    assert number.__class__ is int
    assert number > 0
    if number == 2:
        return True
    if number % 2 == 0 or number == 1:
        return False
    from math import sqrt
    for i in iter(range(3,int(sqrt(number)) + 1,2)):
        if not number % i:
            return False
    return True


Determining sums:

Code: Select all

sum(Prime_test(i) for i in range(2000000))

That looks slow...

I have to like this solution (in Factor):

Code: Select all

USING: math.primes sequences ;
: euler010 ( -- answer )
    2000000 primes-upto sum ;

Runs in about .3 seconds on my machine.

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 » Wed Jun 03, 2009 9:11 pm UTC

Since we're on the subject...

Code: Select all

import Data.Numbers.Primes
main = print $ length (takeWhile (<2000000) 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.

User avatar
Guff
Posts: 165
Joined: Thu Jan 03, 2008 11:56 pm UTC

Re: Project Euler

Postby Guff » Thu Jun 04, 2009 1:50 am UTC

That's way too many keystrokes, guys.

For [imath]\pi(n)[/imath]:

Code: Select all

(p:^:_1)2e6


For problem 10:

Code: Select all

x:+/i.&.(p:^:_1)2e6


I should really try actually learning J some day.

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

Re: Project Euler

Postby zed0 » Thu Jun 04, 2009 10:30 am UTC

problem 3:

Code: Select all

javascript: n=317584931803;for(i=2;n>1;n%i?i++:(n/=i,document.write(i+' ')));

(you can put this direct into firefox)
I know this is a horribly inefficient way to do things, but it was amusing to write.

HalfThere
Posts: 33
Joined: Fri May 01, 2009 1:27 am UTC

Re: Project Euler

Postby HalfThere » Sun Jun 07, 2009 6:51 am UTC

I did a few Project Euler things, but the fact that so much of it is number theory is kind of annoying -that's not a huge interest of mine. Couldn't they be a BIT more diverse?

Agent_Irons
Posts: 213
Joined: Wed Sep 10, 2008 3:54 am UTC

Re: Project Euler

Postby Agent_Irons » Sun Jun 07, 2009 7:02 am UTC

HalfThere wrote:I did a few Project Euler things, but the fact that so much of it is number theory is kind of annoying -that's not a huge interest of mine. Couldn't they be a BIT more diverse?

You, sir, are a scholar and a gentleman.

You did do that on purpose, right?

User avatar
xulaus
Posts: 136
Joined: Thu Jul 03, 2008 11:09 am UTC

Re: Project Euler

Postby xulaus » Sun Jun 07, 2009 8:35 pm UTC

I just solved 59, I am quite smug. I have been stuck on it for ages.
Meaux_Pas wrote:I don't even know who the fuck this guy is

Dr. Willpower
Posts: 197
Joined: Wed May 28, 2008 3:55 pm UTC

Re: Project Euler

Postby Dr. Willpower » Tue Jun 16, 2009 1:01 am UTC

phlip wrote:(Incidentally, the bug was that in both the Python and Haskell versions, I'd said that 40 is spelled with 6 letters... thinking "fourty" instead of "forty". Since there are 100 numbers that include "forty" in the name, the result was 100 too high.)


I made the same error. I'd come into this thread planning to post my code and hope for some help finding the reason my code wasn't working. I'm lucky I spotted your post.
Image
Hat me, bro

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

Re: Project Euler

Postby keeperofdakeys » Mon Jun 22, 2009 10:48 am UTC

i'm stuck on problem 89

the program involves reading roman numerals, which are not in minimal form, and converting them into minimal form; then submitting the difference of characters

I got the answer wrong, so I checked my algorithms but could not find anything wrong.
I link to a different file than the problem which I made a list, it is the correct numerals.

code:
Spoiler:

Code: Select all

def reverse_(string):
   '''returns the reverse of string'''
   asd = list(string)
   asd.reverse()
   return ''.join(asd)

def roman_read(numeral):
   numerals = ['I',1,'V',5,'X',10,'L',50,'C',100,'D',500,'M',1000]
   if len(numeral) == 1: return numerals[numerals.index(numeral) + 1]
   numeral = reverse_(numeral) # reverses the roman numeral for easier processing
   num = 0 # final value of roman numeral
   index = 0 # stores progress in transversing the string
   length = len(numeral) - 1 # length of string for use with index
   while index <= length:
      try: # try and except catch index errors
         if index + 1 > length: # detects end of numeral
            num += numerals[numerals.index(numeral[index]) + 1]
            index += 1
         if numerals.index(numeral[index + 1]) >= numerals.index(numeral[index]): # activates when next digit needs to be added
            num += numerals[numerals.index(numeral[index]) + 1]
            index += 1
         else: # activates when a subtraction is needed
            index_ = index + 1
            num += numerals[numerals.index(numeral[index]) + 1]
            num -= numerals[numerals.index(numeral[index_]) + 1] # starts subtraction
            if index_ + 1 > length:
               return num
            while numerals.index(numeral[index_ + 1]) == numerals.index(numeral[index_]): # continues subtraction until needed
               num -= numerals[numerals.index(numeral[index_ + 1]) + 1]
               if index_ + 1 >= length: return num
               else: index_ += 1
            index = index_ + 1
      except IndexError:
         index += 1 # if except is tripped, this will move it along
   return num

def roman_write(num):
   numerals = ['I',1,'V',5,'X',10,'L',50,'C',100,'D',500,'M',1000]
   for x in xrange(1,14,2): # captures easy numerals
      if num == numerals[x]: return numerals[x-1]
   numeral = ''
   level = 1 # indicates which digit is used, counts up in twos
   while level <= 7 and num != 0:
      num_ = num % 10
      numeral_ = '' # temporary numeral for subtraction pairs
      if level == 7: # counts numerals beyond 1000s
         numeral_1 = 'M'
         numeral = ''.join([numeral_,numeral_1 * (num),numeral])
         break
      else: (numeral_1,numeral_2,numeral_3) = (numerals[(level-1)*2],numerals[level*2],numerals[(level+1)*2]) # assigns numerals equivilent to 1, 5 and 10 of digit placing ex. 10, 50 and 100 for 10s
      if num_ > 7:
         numeral_ = ''.join([numeral_,numeral_1 * (10 - num_),numeral_3])
         num_ = 0
      elif num_ > 5:
         numeral_ = ''.join([numeral_,numeral_2,numeral_1 * (num_ - 5)])
         num_ = 0
      elif num_ == 5:
         numeral_ = ''.join([numeral_,numeral_2])
         num_ = 0
      elif num_ > 3:
         numeral_ = ''.join([numeral_,numeral_1 * (5 - num_),numeral_2])
         num_ = 0
      else:
         numeral_ = ''.join([numeral_,numeral_1 * (num_)])
         num_ = 0
      numeral = ''.join([numeral_,numeral])
      num //= 10
      level += 2
   return numeral

import urllib2

numerals = eval(urllib2.urlopen('http://keeperofdakeys.x10hosting.com/temp/Problem_89_res.txt').read())
numerals_ = []
numbers = []
total_char_1 = 0
total_char_2 = 0

for x in numerals:
   total_char_1 += len(x)
   num = roman_read(x)
   numbers.append(num)

for x in numbers:
   numeral = roman_write(x)
   numerals_.append(numeral)
   total_char_2 += len(numeral)

print total_char_1 - total_char_2


I hope its commented enough

thanks for your help

andy11235
Posts: 38
Joined: Thu Oct 16, 2008 6:21 am UTC

Re: Project Euler

Postby andy11235 » Tue Jun 23, 2009 9:44 am UTC

Problem 89:

You are not supposed to do things like IIX for 8, you should instead use the (longer) VIII. Your code shortens 8 to IIX.

The "correct" way of writing numerals is to only use subtractive pairs if writing it out otherwise would require 4 of the same symbol in a row. You should not prefix a numeral by multiple smaller numerals, in addition to the other rules. This could have been better explained.

The numerals in "minimal form" should go

I II III IV V VI VII VIII IX X ...

User avatar
PM 2Ring
Posts: 3715
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Project Euler

Postby PM 2Ring » Tue Jun 23, 2009 12:51 pm UTC

You may wish to look at my Python Roman-Decimal, Decimal-Roman conversion program I posted here 3 months ago in the Hacks & Snippets thread.

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

Re: Project Euler

Postby keeperofdakeys » Wed Jun 24, 2009 7:12 am UTC

thanks for that, I changed the 7 to an 8 and it works perfectly
it appears my internal definition of a roman numeral was stuffedal up and the fact that it says subtractive PAIR still didn't ert me to the fact


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 10 guests