Project Euler
Moderators: phlip, Moderators General, Prelates
 Xanthir
 My HERO!!!
 Posts: 5336
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Project Euler
So, doing problem 80 (calculate the sum of the first 100 digits of the square roots of 2100). Made a nice simple eulersmethod 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.
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)))
Re: Project Euler
I am having trouble with problem 26. First some (Haskell) code:
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?
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 nn<[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
I get
"No problem!" I think, figuring that python was choking on the newlines, so I rewrote the code to
I don't get anything back, what am I doing wrong here? This seems like something that should be easy to pull off here.
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 rewrote 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.
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: 7557
 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)⚠);}
 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.
 Xanthir
 My HERO!!!
 Posts: 5336
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 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:
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))
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: 5336
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 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.
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 freemarket 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
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:
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:
Bipod, since you got that far, you could have deduced the right answer without writing a single line of code:
Spoiler:
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:
It's always so obvious when you see it written out by someone else. Thanks.
Re: Project Euler
Huge fukken spoilers ahead, though only for the first few problems (specifically 110, 12, 14, 16, 20)
Spoiler:
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?
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.
I can't find where I made the mistake, it works for 10 but not 1000
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
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.
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
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.
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.
Re: Project Euler
ftfy.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 downwith a piece of paperuntil you understand themathematicalsecret that obscures the problem
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.
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'.
 RoadieRich
 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.
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.
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:
Spoiler:
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/((1x)(1x^2)(1x^5)(1x^10)(1x^20)(1x^50)(1x^100)(1x^200)). I actually just recently wrote code that would do just that.
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: 7557
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: Project Euler
I think I solved 31 with dynamic programming...
Spoiler:
Spoiler:
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Re: Project Euler
An easier way of solving problem 31?
Spoiler:
Re: Project Euler
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.
Re: Project Euler
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.
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:
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.
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]);
}
[...]
 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.
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][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.
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.
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:
With Euler22Text.txt being a longer version of this:
(No endoffile newline)
Neither namesarray[y][0] or namesarray[y] work, although using namesarray[y] produces:
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 endoffile 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.
Re: Project Euler
Macbi,
A twodimensional 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 twodimensional 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.
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.
A twodimensional 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 twodimensional 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.
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 wrote:Code: Select all
char namesarray[length][number];
Re: Project Euler
Ah, thank you. That explains a lot of confusion I had with pointers as well.jaap wrote:Macbi,
A twodimensional 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]
[/quote] How would this be done in C89? With malloc?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 wrote:Code: Select all
char namesarray[length][number];
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.

 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 giveaways of earlier problems:
Any kind of pointers people could give me towards thinking of an algorithm would be appreciated.
I have solved problem 81 and 82, but I have no idea how to go for 83.
Spoiler for possible giveaways of earlier problems:
Spoiler:
Any kind of pointers people could give me towards thinking of an algorithm would be appreciated.
Re: Project Euler
keeperofdakeys wrote:So, problem 83.
Spoiler:
 Xanthir
 My HERO!!!
 Posts: 5336
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Project Euler
Or, if you want the simple algorithm answer to 83:
Spoiler:
(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:
Who is online
Users browsing this forum: No registered users and 11 guests