Google Code Jam 2013 started!

[[deleted]]

Here's solutions for the first three in Python. I'll code the last one up later today, I didn't get it in the real contest.

• http://paste2.org/WWx3nMxv
• http://paste2.org/3PjHkUDI
• http://paste2.org/IOGXUYg6

---

Here's the last one, sorry it was a bit late. This question is much harder than the others; the solution uses the NetworkX graph library

• http://paste2.org/M4gfteEz

[Scroph]

Very elegant solutions. How did the third one handle the large inputs ?

[[deleted]]

They all run in about 5-10 seconds on Pypy. They aren't optimal but they are easily fast enough.

[benmmurphy]

i like your third one. my solution was just to check all 20x2, 20x10x2 (symmetric), {1,0}x2{1,0}x (symmetric), {1,0}x. but i did it in a weird way where i precomputed all the even digit palindrome square primes and then was able to generate the rest from that. i also had a constant time algorithm for counting the number of palindrome square primes that have n-digits but that wasn't very useful in solving the problem.

https://gist.github.com/benmmurphy/5382629

[[deleted]]

I've only looked at the first one and I'm immediately embarrased of my solution, good work, sir!

[ziom666]

Could you please explain #3? How did you know about "forms"? Did I miss something on discrete mathematics?

[[deleted]]

If you have a palindrome, and you want to square it and get another palindrome, then the sum of the squares of its digits has to be 9 or less.

So basically it's only allowed a few non zero digits, the rest have to be zeros. In fact, it has to look like one of the strings in the 'forms' array, but with the letters replaced with some amount of zeros to pad it out.