Yeah exactly. I'm sure there are faster algorithms and slower
algorithms, but the fact that I was only reqiured to find the
"mediocre" algorithm and not the fast one is an advantage :).
I thought about using 2 threads, too, but much too late. My code has
inter-testcases optimizations, too (if the result for bases "2 3 4" is
x, for "2 3 4 8", there is no need to start from anything less than
x).
2 threads would probably have made it faster overall.
My solution was in C++, and I did do the premutations optimization.
My algorithm in pseudo-code:
bool is_happy(number, base) {
if (number == 1) return true;
int64 new_number = 0;
vector<int> digits; /* for those not familiar with C++, a vector
is a dynamic array, like ArrayList in Java */
while (number != 0) {
int digit = number % base;
number /= base;
add the element digit to digits
new_number += digit * digit;
}
sort the digits vector
calculate a hash of the sorted vector using precomputed zobrist
keys (http://en.wikipedia.org/wiki/Zobrist_hashing)
/* basically for every element of the vector, xor zobrist
[position][digits[position]] into the hash, where zobrist is a 2D
array of precomputed randomly generated numbers (I used Mersenne
Twister) */
try to find the hash in a set of numbers already seen.
if found, return false;
else
add hash to the set;
return is_happy(new_number, base);
}
---------------------
I'm sure there are ways to make it faster by moving things around...
but I think the general algorithm I have here SHOULD be fast enough,
and having a fast CPU allowed me to not have to spend time optimizing
it.
BTW, my CPU is a C2D 1.86ghz overclocked to 3.3 :). Gotta love early
C2D's.
Ah, adding parallelization to template would be a very good idea. I'll
consider doing that, too. Maybe even adding a little server and client
that would allow you to build a cluster in short order (the server can
dispatch tasks, and clients will just receive and process them, and
send the result back to the server. They can all run the same code,
with a different command line switch or something). If I add all the
computers in the house together, I have 8 cores! (1 P4, 1 Core 2 Solo,
2 Core 2 Duo's, 1 Core 2 based dual core Celeron).
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to google-code@googlegroups.com
To unsubscribe from this group, send email to
google-code+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en
-~----------~----~----~----~------~----~------~--~---
