//The sollution to Project Euler Problem 4
//By Sam
#include <iostream>
#include <math.h>
int reverse(int);
int digitCount(int);
bool palindrome(int);
int main(){
/* Lazy block comments ;)
int test;
while(true){
std::cout << "Test if palindromic: ";
std::cin >> test;
if(palindrome(test))
std::cout << "This is a palindrome.";
else
std::cout << "This is not a palindrome.";
std::cout << std::endl;
}
//*/
int result=0;
int second=0;
int highest=0;
//Loop through all possible numbers that we can times together
for(int first = 999;first > 100;first--){
for(second = first;second > 100; second--){
//Find the result
result = first * second;
//Record the highest one we get
if(palindrome(result) && result > highest)
highest = result;
}
}
std::cout << "The largest palindrome made from the product of two 3-digit numbers is " << highest;
return 0;
}
bool palindrome(int number){
//if the number = the reverse number
return (number == reverse(number));
}
int reverse(int number){
int currentUnit = 0;
int oppositeUnit = 0;
int newPosition=0;
int progressive = 0;
int finalNumber=0;
int previous=0;
//For the program, the number of digits start from an index of 0 hence -1
int digits = digitCount(number) - 1;
//Loop through the number backwards
for(int i = digits;i >= 0;i--){
//Where the target digit is units wise, and where it should be
currentUnit = pow(10,i);
oppositeUnit = pow(10,digits - i);
//Take crap out from the right
progressive = floor(number / currentUnit);
//Take crap out from the left
newPosition = progressive - (previous * 10);
//Calculate what we will be taking out next iteration
previous = progressive;
//Put isolated number in correct units and add to final number
finalNumber += newPosition * oppositeUnit;
}
return finalNumber;
}
int digitCount(int number){
//Start the variables, size needs to be larger than 10
int digits=0;
float size=10.1;
//See if dividing by 1, 10, 100.. etc reduces the units of the number
while(size > 10){
//If the size is under 10, we know we have hit the end of the number.
size = number / pow(10,digits);
digits++;
}
return digits;
}
(defun find-palindrome-in-range (x y)
(loop for i from x downto y do
(loop for j from x downto y
do (let ((a (* i j)))
(when (palindromep a)
(return-from find-palindrome-in-range a))))))
CL-USER> (time (find-palindrome-in-range 999 100))
Evaluation took:
0.016 seconds of real time
0.015625 seconds of total run time (0.015625 user, 0.000000 system)
100.00% CPU
27,368,892 processor cycles
1,897,600 bytes consed
(defun find-palindrome-in-range (x y)
(iter (for i from y downto x)
(maximizing
(iter (for j from i downto x)
(finding (* i j) such-that #'palindromep on-failure 0)))))
And profiling/timing information:
CL-USER> (time (find-palindrome-in-range 100 999))
Evaluation took:
0.454 seconds of real time
0.453125 seconds of total run time (0.453125 user, 0.000000 system)
[ Run times consist of 0.048 seconds GC time, and 0.406 seconds non-GC time. ]
99.78% CPU
1,081,934,397 processor cycles
137,371,272 bytes consed
(define (find-palindromes from to)
(letrec ((rec
(lambda (x y lst)
(cond ((= x to)
(reverse lst))
((= y to)
(rec (+ x 1) from lst))
((palindrome? (* x y))
(rec x (+ y 1) (cons (* x y) lst)))
(else
(rec x (+ y 1) lst))))))
(rec from from '())))
(time (apply max (find-palindromes 111 999)))
=>cpu time: 1227 real time: 1252 gc time: 74
906609
Name:
Anonymous2010-05-18 12:24
>>19
Writing a primitive recursion is unnecessary and only turns people off scheme. (import (srfi :13) (srfi :42)) (define (palindrome? number)
(let ((numstring (number->string number)))
(string=? numstring (string-reverse numstring)))) (define (find-palindromes to from)
(list-ec (:range i to from)
(:range j to from)
(:let n (* i j))
(if (palindrome? n))
n)) (time (apply max (find-palindromes 100 1000)))
running stats for (apply max (find-palindromes 100 1000)):
67 collections
936 ms elapsed cpu time, including 89 ms collecting
986 ms elapsed real time, including 98 ms collecting
278422240 bytes allocated
906609
Name:
Anonymous2010-05-18 12:41
Why do you use strings? what dumbasses.
(defun reverse-integer (integer)
"Reverse a non-zero positive integer"
(do ((i (floor (log integer 10)) (1- i))
(sum 0 (+ sum (* (rem integer 10)
(expt 10 i))))
(integer integer (floor (/ integer 10))))
((zerop i) (+ sum integer))))
(defun palindrome-p (x)
(= x (reverse-integer x)))
>>21
Your integer version is actually slower than the string version:
;;; Integer version from >>21
CL-USER> (time (find-palindrome-in-range 100 999))
Evaluation took:
0.610 seconds of real time
0.609375 seconds of total run time (0.609375 user, 0.000000 system)
99.84% CPU
1,461,927,303 processor cycles
94,789,536 bytes consed
STYLE-WARNING: redefining PALINDROMEP in DEFUN
906609
;;; String version from >>17
CL-USER> (time (find-palindrome-in-range 100 999))
Evaluation took:
0.484 seconds of real time
0.484375 seconds of total run time (0.484375 user, 0.000000 system)
[ Run times consist of 0.031 seconds GC time, and 0.454 seconds non-GC time. ]
100.00% CPU
1,150,893,090 processor cycles
137,372,928 bytes consed
906609
I actually expected the integer version to be faster, but it doesn't seem to be. I think the reason why your version is slower is that you use floor/log, while using truncate or mod would likely be better choices, and maybe some declarations too.
Name:
Anonymous2010-05-18 13:00
>>22 What's the point?
Legibility. The string library is a bit generous, since I only used string-reverse.There is a time and a place for writing out your recursions by hand, but a comprehension isn't one of them. It's a pattern you are going to use over and over and over and over and over and over and over and over and over and over and over and over and over and over and over and over and over and over and over and over and over and over. If you are not using the abstraction facilities that Scheme gives you, then why bother using Scheme at all? If you want to be a caveman, code in Assembly.
While I'm moaning, If you write out a recursion by hand where map, filter, fold[lr], for-each or unfold could be used, you are a fucking retard and should get the fuck out of here
>>24
He's using CL, not Scheme, but the point does apply. He should aim for elegant code and only optimize when needed. After he profiles his code and sees that something is the bottleneck, only then he can write more butchered code for the sake of speed. (To be fair, palindromep function is the bottleneck, and he was right to try writing a more efficient version, but too bad his version is actually SLOWER than the string one because he used too costly function calls).
>>23
You're a fucking idiot. The real reason my version is slower than your version is because you're comparing an implementation-quality function with the plain algorithm. fucking dumbass CL programmers came out of a university with no real experience and they don't get shit, talk shit and code shit. eat a fucking dick
spawn_processes(N, Nmax, Receiver_PID) ->
if
N + 1 =< Nmax ->
spawn(tut, is_palindrome, [N div 1000, N rem 1000, Receiver_PID]),
spawn_processes(N+1, Nmax, Receiver_PID);
N + 1 >= Nmax ->
{completed, Nmax}
end
.
>>27
That was indeed the case.
I still enjoy me a (letrec ...) and a (lambda ...) or two.
Readability is paramount if you ever intend your code to be used elsewhere and understood by somebody else, I agree. And abstraction is very useful, but I feel for this particular case, the extra libraries are overkill.
>>30
You don't get it do you fucking idiot? I was right you don't get it. FORMAT is optimized you fucking moron. REVERSE is optimized you fucking dumford. Fucking stupid dumb piece of shit. God damn fucking atheist sonscumbitchassnigfaggot
>>33
And the functions you used aren't optimized? If your function was written for efficiency, it would have been fast. And format isn't always optimized (sometimes it may be, using a compiler transform). If I wanted zomgspeed, I would have used formatter wrapped around the function in a closure, and declared the arguments' type. Your code benefited from the same optimizations as my code. Your code was slow because of the choice of functions.
Name:
172010-05-18 16:04
Hah, obtaining good performance is easy even if you cons up a list, much better than strings at that:
(defun integer-to-list (x &optional (base 10))
(labels ((rec (i res)
(if (zerop i) res
(multiple-value-bind (div mod)
(truncate i base)
(rec div (cons mod res))))))
(rec x nil)))
And the benchmark:
CL-USER> (time (find-palindrome-in-range 100 999))
Evaluation took:
0.062 seconds of real time
0.062500 seconds of total run time (0.062500 user, 0.000000 system)
100.00% CPU
177,844,266 processor cycles
27,449,040 bytes consed
>>28,33,38 'thinks he's a hotshot for making an elementary algorithm which reverses the order of digits of a base 10 number. 'thinks said poster didn't know the complexity classes of the algos involved, including his current CL implementation's
I can smell the butthurt and delicious tears from miles away...
Sorry, I couldn't abstain, but this has been keeping me laughing for a while.
/me returns back to /b/ for making a /b/-quality post
int Projects::EulerProject4() {
/*
A palindromic number reads the same both ways.
The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
*/
int palindrome = 0;
const int LOOP_MAX = 999;
for (int loopiter1 = 100; loopiter1 < LOOP_MAX; loopiter1++) {
for (int loopiter2 = 100; loopiter2 < LOOP_MAX; loopiter2++) {
int result = loopiter1 * loopiter2;
int grumblyface = result;
char len = (result > 99999) ? 6 : 5;
bool flag = true;
int* grumblyarray = new int[len];
for (char b = 0; b < len; b++) {
int digit = grumblyface % 10;
grumblyface /= 10;
grumblyarray[b] = digit;
}
for (int i = 0; i < (len / 2); i++) {
if (grumblyarray[i] != grumblyarray[(len - 1) - i]) {
flag = false;
break;
}
}
if (flag) {
palindrome = result;
}
delete grumblyarray;
}
}
return palindrome;
}