 |
Cheat Engine
The Official Site of Cheat Engine
|
| View previous topic :: View next topic |
| Author |
Message |
Symbol
I'm a spammer
![]() Reputation: 0
Joined: 18 Apr 2007
Posts: 5094
Location: Israel.
|
 Posted: Sat Oct 18, 2008 9:32 am Post subject: [Project Euler]Programming Exercises and Problems |
 |
|
Here's a nice site I've found with a lot of programming problems, to check your answers, register and you'll have an "Check" button for each question.
Problems page: http://projecteuler.net/index.php?section=problems
About Project Euler: http://projecteuler.net/index.php?section=about
The questions are sorted by difficulty level.
| Quote: | Can anyone solve the problems?
The problems range in difficulty and for many the experience is inductive chain learning. That is, by solving one problem it will expose you to a new concept that allows you to undertake a previously inaccessible problem. So the determined participant will slowly but surely work his/her way through every problem.
I've written my program but should it take days to get to the answer?
Absolutely not! Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.
I solved it by using a search engine, does that matter?
Making use of the internet to research a problem is to be encouraged as there could be hidden treasures of mathematics to be discovered beneath the surface of many of these problems. However, there is a fine line between researching ideas and using the answer you found on another website. If you photocopy a crossword solution then what have you achieved? |
Efficiency is the most important thing in here:
| Quote: | Does it matter if it takes more than one minute to solve?
Of course not, but that should provide the impetus to return to the problem and see how you can improve your approach. But remember that once you've solved a particular problem you will be able to access a thread relating to that problem and it is here that you may be able to pick some tips from others that have solved it. |
You can discuss about problems here if you want.
|
|
| Back to top |
|
 |
nog_lorp
Grandmaster Cheater
 Reputation: 0
Joined: 26 Feb 2006
Posts: 743
|
| Posted: Sat Oct 18, 2008 11:25 pm Post subject: |
|
|
Interesting thought about #2. It is easy to complete by testing for the evenness number; however: every 3rd Fibonacci number is even, wonder what the performance difference would be to add every 3rd number rather than performing n modulos?
_________________
Mutilated lips give a kiss on the wrist of the worm-like tips of tentacles expanding in my mind
I'm fine accepting only fresh brine you can get another drop of this yeah you wish |
|
| Back to top |
|
|
Overload
Master Cheater
 Reputation: 0
Joined: 08 Feb 2008
Posts: 293
|
| Posted: Sun Oct 19, 2008 2:34 am Post subject: |
|
|
Damn!
I was just in development of a website similar to this. Anyways, maybe I'll show you guys when its done.
But I'm already done lots of them 
Number two was easy.
_________________
Blog
| Quote: | Rhys says:
you can be my maid
Rhys says:
ill buy you a french maid outfit
Tyler says:
Sounds good
Rhys says:
ill hold you to that |
|
|
| Back to top |
|
|
Zand
Master Cheater
![]() Reputation: 0
Joined: 21 Jul 2006
Posts: 424
|
| Posted: Sun Oct 19, 2008 3:41 am Post subject: |
|
|
| Overload wrote: |
Number two was easy. |
That's not the point.
|
|
| Back to top |
|
|
nog_lorp
Grandmaster Cheater
Reputation: 0
Joined: 26 Feb 2006
Posts: 743
|
| Posted: Sun Oct 19, 2008 7:44 am Post subject: |
|
|
Similar idea for 1:
rather than
| Code: |
for(i=1; i<1000; i++) { ... } //this runs 1000 times
|
do this:
| Code: |
for(i=0; i*3<1000; i++) { ... } //runs 333 times
for(i=0; i*5<1000; i++) { ... } //runs 200 times
//total number of loops = 533
|
_________________
Mutilated lips give a kiss on the wrist of the worm-like tips of tentacles expanding in my mind
I'm fine accepting only fresh brine you can get another drop of this yeah you wish |
|
| Back to top |
|
|
Symbol
I'm a spammer
![]() Reputation: 0
Joined: 18 Apr 2007
Posts: 5094
Location: Israel.
|
| Posted: Sun Oct 19, 2008 8:06 am Post subject: |
|
|
I'm kinda stuck at 36, I'm pretty sure my answer is correct... you need to sum all the numbers up to one milion that are palindrome in both bases 10 (decimal) and 2 (binary).
Does 1-digit numbers count as palindromes?
Here's the output of my program:
Decimal:Binary
| Quote: | 0:0
1:1
3:11
5:101
7:111
9:1001
33:100001
99:1100011
313:100111001
585:1001001001
717:1011001101
7447:1110100010111
9009:10001100110001
15351:11101111110111
32223:111110111011111
39993:1001110000111001
53235:1100111111110011
53835:1101001001001011
73737:10010000000001001
Sum: 286602 |
| Code: | int Problem36()
{
int sum = 0;
for (int i = 0; i < 1000000; ++i)
{
if (isPalindromic(i))
{
if (isPalindromic(DecToBin(i)))
{
printf("%u:%llu\n", i, DecToBin(i));
sum += i;
}
}
}
return sum;
} |
I'm not sure if I should start from 0, maybe 2-digit numbers?
By the way, is there a faster, more efficient way t odo this?
| nog_lorp wrote: | Similar idea for 1:
rather than
| Code: |
for(i=1; i<1000; i++) { ... } //this runs 1000 times
|
do this:
| Code: |
for(i=0; i*3<1000; i++) { ... } //runs 333 times
for(i=0; i*5<1000; i++) { ... } //runs 200 times
//total number of loops = 533
|
|
That's a pretty good idea, might not make a big diffrance with small numbers but with bigger numbers...
Edit:
I'm not sure I understood problem 213, they said:
| Quote: | | What is the expected number of unoccupied squares after 50 rings of the bell? Give your answer rounded to six decimal places. |
Rounded to 6 decimal places? does that mean the number is bigger than 100,000? how come, if there are only 30x30 (900) squares?
Or I misunderstood that part?
|
|
| Back to top |
|
|
nog_lorp
Grandmaster Cheater
Reputation: 0
Joined: 26 Feb 2006
Posts: 743
|
| Posted: Sun Oct 19, 2008 8:49 am Post subject: |
|
|
With 213 it is a statistical problem, so the answer will probably be a non-integer representing the most likely/mean outcome. I'm guessing (hoping) this is meant as a simulation problem.
For 36, are you sure you are doing up to 1,000,000 and not 100,000? Because your last palindromic number is less than 100,000 which would imply there are no numbers between 1,000,000 and 100,000 that fit the rules.
Edit: I would make a binIsPalindrome function - converting to a huge int so you can use your int function will hurt efficiency alot. I would use bit masks and bitwise logic.
Also, I'd like to see your isPalindrome function for comparison 
| Code: | inline int isPalindromic(unsigned int x)
{
unsigned int n,i;
for(n=0; x > pow(10,n); n++);
for(i=1; i <= n/2; i++)
if(x/(int)pow(10,n-i) % 10 != x/(int)pow(10,i-1) % 10)
return 0;
return 1;
} |
With a cursory look through the thread for the problem I see noone actually using math to test the palindromic property, instead they write to a string buffer or use some higher level function (excluding the people who factored it out into a polynomial).
_________________
Mutilated lips give a kiss on the wrist of the worm-like tips of tentacles expanding in my mind
I'm fine accepting only fresh brine you can get another drop of this yeah you wish |
|
| Back to top |
|
|
HalfPrime
Grandmaster Cheater
![]() Reputation: 0
Joined: 12 Mar 2008
Posts: 532
Location: Right there...On your monitor
|
| Posted: Sun Oct 19, 2008 4:27 pm Post subject: |
|
|
It would be a good idea to check for binary palindromacy first as that should be the quickest to check.
20 bits for 1048575
| Code: | isBinPal(int x){
bitArray ba = &x;
int c;
//ba[20] should be for 524288
if(ba[20] == 1)
c=20;
else if(ba[19] == 1)
c=19;
...
else if(ba[2] == 1)
c=2;
else
return 1;
int max=c/2;
for(int a=0;a<max;a++)
if(ba[a] != ba[c-a])
return 0;
return 1;} |
That's the fastest way I can think of to check barring some kind of bit trickery.
I think it would actually be faster to split up each group of numbers in the main loop rather than have all those ifs to take off the leading 0's and have isBinPal16to31, etc.
for checking decimal palindromes, the fastes way to me would be to do something like an array of numbers (bytes or half-bytes) representing each digit. basically like a string, but not messing withoutside function calls or chars.
Then, for each digit it would only take the conversion and the compare to do it. I think the conversion would be faster than "x/(int)pow(10,(n or i)-1) % 10", but I haven't tried it or anything.
I'm currently working on problem 110. These are all pretty fun.
_________________
|
|
| Back to top |
|
|
Symbol
I'm a spammer
![]() Reputation: 0
Joined: 18 Apr 2007
Posts: 5094
Location: Israel.
|
| Posted: Sun Oct 19, 2008 4:35 pm Post subject: |
|
|
| nog_lorp wrote: | With 213 it is a statistical problem, so the answer will probably be a non-integer representing the most likely/mean outcome. I'm guessing (hoping) this is meant as a simulation problem.
For 36, are you sure you are doing up to 1,000,000 and not 100,000? Because your last palindromic number is less than 100,000 which would imply there are no numbers between 1,000,000 and 100,000 that fit the rules.
Edit: I would make a binIsPalindrome function - converting to a huge int so you can use your int function will hurt efficiency alot. I would use bit masks and bitwise logic.
Also, I'd like to see your isPalindrome function for comparison
| Code: | inline int isPalindromic(unsigned int x)
{
unsigned int n,i;
for(n=0; x > pow(10,n); n++);
for(i=1; i <= n/2; i++)
if(x/(int)pow(10,n-i) % 10 != x/(int)pow(10,i-1) % 10)
return 0;
return 1;
} |
With a cursory look through the thread for the problem I see noone actually using math to test the palindromic property, instead they write to a string buffer or use some higher level function (excluding the people who factored it out into a polynomial). |
Nah, I didn't used any strings:
| Code: | bool isPalindromic(unsigned __int64 n)
{
unsigned __int64 num = 0, x = n;
do
{
num = (num * 10) + (x % 10);
} while (x /= 10);
return (num == n);
} |
And yes, I did check up to 1,000,000:
| Quote: | | for (int i = 0; i < 1000000; ++i) |
I'll take a look at the question again, I might misread something.
| HalfPrime wrote: | It would be a good idea to check for binary palindromacy first as that should be the quickest to check.
20 bits for 1048575
| Code: | isBinPal(int x){
bitArray ba = &x;
int c;
//ba[20] should be for 524288
if(ba[20] == 1)
c=20;
else if(ba[19] == 1)
c=19;
...
else if(ba[2] == 1)
c=2;
else
return 1;
int max=c/2;
for(int a=0;a<max;a++)
if(ba[a] != ba[c-a])
return 0;
return 1;} |
That's the fastest way I can think of to check barring some kind of bit trickery.
I think it would actually be faster to split up each group of numbers in the main loop rather than have all those ifs to take off the leading 0's and have isBinPal16to31, etc.
for checking decimal palindromes, the fastes way to me would be to do something like an array of numbers (bytes or half-bytes) representing each digit. basically like a string, but not messing withoutside function calls or chars.
Then, for each digit it would only take the conversion and the compare to do it. I think the conversion would be faster than "x/(int)pow(10,(n or i)-1) % 10", but I haven't tried it or anything.
I'm currently working on problem 110. These are all pretty fun. |
I didn't use any strings, I was too tired to code a normal function and other functions for binary-pilandrome, so I just used int64 and when I converted from decimal to binary I used '1' and '2' instead of '0' and '1', then decrased by one, so it won't remove the right-side zeros when reversing. (I converted to binary in a way which the number is returned reversed)
| Code: | unsigned __int64 DecToBin(unsigned __int64 d)
{
unsigned __int64 bin = 0, len = 0, x = d;
do
{
bin = (bin * 10) + (x % 2 == 0 ? 1 : 2); //1 and 2 to keep the leading zero's, which are now 1, and 1 is now 2.
} while (x /= 2);
x = 0;
do
{
x = (x * 10) + ((bin % 10) - 1); //decrase 1 to fix the number
} while (bin /= 10);
return x;
} |
It's kinda ugly, but I was too lazy.
|
|
| Back to top |
|
|
nog_lorp
Grandmaster Cheater
Reputation: 0
Joined: 26 Feb 2006
Posts: 743
|
| Posted: Sun Oct 19, 2008 7:06 pm Post subject: |
|
|
I only did the early (#6?) palindrome problem, let me give 36 a go and see if I get a different answer.
_________________
Mutilated lips give a kiss on the wrist of the worm-like tips of tentacles expanding in my mind
I'm fine accepting only fresh brine you can get another drop of this yeah you wish |
|
| Back to top |
|
|
Overload
Master Cheater
Reputation: 0
Joined: 08 Feb 2008
Posts: 293
|
| Posted: Sun Oct 19, 2008 7:14 pm Post subject: |
|
|
| Zand wrote: | | Overload wrote: |
Number two was easy. |
That's not the point. |
The point is to solve them. Thats what I did. I just thought it was easy 
_________________
Blog
| Quote: | Rhys says:
you can be my maid
Rhys says:
ill buy you a french maid outfit
Tyler says:
Sounds good
Rhys says:
ill hold you to that |
|
|
| Back to top |
|
|
nog_lorp
Grandmaster Cheater
Reputation: 0
Joined: 26 Feb 2006
Posts: 743
|
|
| Back to top |
|
|
HalfPrime
Grandmaster Cheater
![]() Reputation: 0
Joined: 12 Mar 2008
Posts: 532
Location: Right there...On your monitor
|
| Posted: Sun Oct 19, 2008 8:13 pm Post subject: |
|
|
Good point.
If you can do X many binary checks per 1 decimal check
and there's Y decimal fails per binary fails
It would depend on which was greater. But I don't think you can get Y without going through the entire thing. =\
Gut feeling says binary check first, but I can't say for sure.
Just did 108 while I was trying 110. I can do 108 fast enough, but 110 takes a minute per checking just 500 numbers. Guess I don't have a clever enough implementation.There were some strange numbers I noticed 2^16-1 and 2^32-1 which had half as many solutions as their value.
Currently working on 213
_________________
|
|
| Back to top |
|
|
nog_lorp
Grandmaster Cheater
Reputation: 0
Joined: 26 Feb 2006
Posts: 743
|
|
| Back to top |
|
|
DoomsDay
Grandmaster Cheater
 Reputation: 0
Joined: 06 Jan 2007
Posts: 768
Location: %HomePath%
|
| Posted: Mon Oct 20, 2008 3:58 am Post subject: |
|
|
If you want to see my implementation of a brute-force solution for #36, quote my post (should include the original formatting)).
isDecP proc num
pushad
mov eax,num
xor ebx,ebx
mov ecx,10
.repeat ;push all the remainders of the number divided by 10 to the stack
xor edx,edx
inc ebx
div ecx
push edx
.until (!eax)
lea edx,[ebx*4] ;edx is the stack offset
xor ecx,ecx
.repeat
mov eax,[esp+ecx*4]
.if (eax != [esp+ebx*4-4])
add esp,edx
popad
xor eax,eax
jmp @F
.endif
inc ecx ;offsetS to the remainders
dec ebx
.until zero? ;could be optimized
add esp,edx ;restore the stack
popad ;restore the registers
xor eax,eax ;return TRUE
inc eax
@@:
ret
isDecP endp
isBinP proc num
push ecx ;preserve ECX
mov eax,num
mov ecx,eax
.if (eax)
;push the bits
.repeat
add eax,eax ;faster than SHL eax,1
.until carry?
;compare to the revesed order, use the carry flag for branching
shr ecx,1
.if carry?
.repeat
shr ecx,1
.if carry? ;branching instead of boollean compares
add eax,eax
.if !carry?
xor eax,eax
jmp @F
.endif
.else
add eax,eax
.if carry?
xor eax,eax
jmp @F
.endif
.endif
.until zero? ;corresponds to eax
.else
xor eax,eax
jmp @F
.endif
xor eax,eax
.endif
inc eax
@@:
pop ecx
ret
isBinP endp
problem_36 proc
xor ecx,ecx
xor edx,edx
.repeat
invoke isBinP,ecx
.if (eax)
invoke isDecP,ecx
.if (eax)
add edx,ecx
.endif
.endif
inc ecx
.until (ecx == 1000000) ;ofcourse, could be optimized =]
print str$(edx),13,10
ret
problem_36 endp
Last edited by DoomsDay on Mon Oct 20, 2008 7:01 am; edited 1 time in total |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
