Wednesday, May 25, 2011
Palindrome Puzzle
I heard this puzzle on car talk. It's about finding odometer reading which is a palindrome. The twist is that a 6 digit odometer read's palindrome in the morning when Tommy left to work and the odometer read palindrome again when Tommy came back home!
The complete detail is on Tommy's Drive to Work
To solve this problem
1. Find all 6 digit palindrome heuristically.
2. Sort all the palindrome in ascending order.
3. Compare adjacent palindromes, if they are less than 100(miles) print the palindrome.
Here is my c++ solution
#include <iostream> #include <vector> #include <algorithm> #include <iomanip> // 5/25/2011 5:39 PM // Car talk Puzzle 6 digit palindrome// Shankar Chakkere // http://www.cartalk.com/content/puzzler/transcripts/201121/index.html std::vector <unsigned int > palindrome;bool sortVector (unsigned int i,unsigned int j) { return (i < j);} int main() { // for 6 digit (654321) palindrome // digits 1 and 6 are same, 2 & 5 are same, 3 & 4 are same // e.g 175571 // Generate all possible palindrome heuristically for(int x = 0; x <= 9; x++) { for(int y =0; y <= 9; y++) { for(int z =0; z <= 9; z++) { // Have not tried to optimize for sake of clarity unsigned int pal = x*100000 + y*10000 + z*1000 + z*100 + y*10 + x; palindrome.push_back(pal); } } } // // Sort them in ascending order std::sort(palindrome.begin(), palindrome.end(), sortVector); std::vector<unsigned int>::iterator it = palindrome.begin(); unsigned int previous = *it++; while(it != palindrome.end()) { unsigned int current = *it++; // if the diffence of adjacent odometer reading is less than 100 miles // assuming he does not drives more than 100 miles if( (current - previous) < 100) { std::cout << std::setw(6) << std::setfill('0') << previous << " " << current << " miles driven= " << current - previous << std::endl; } previous = current; } return 0; }The Output
099990 100001 miles driven= 11
199991 200002 miles driven= 11
299992 300003 miles driven= 11
399993 400004 miles driven= 11
499994 500005 miles driven= 11
599995 600006 miles driven= 11
699996 700007 miles driven= 11
799997 800008 miles driven= 11
899998 900009 miles driven= 11Labels: Puzzles
