Learn to Code
John F. Dumas

Feedback Examples: Three

► PROGRAMMING LANGUAGE:: C++

► ASSIGNMENT: The assignment is to find all numbers below 1,000,000 that are "dual palindromes". Recall that a palindrome is a word that's the same backwards and forwards, like "redder" for example.

A dual palindrome is made up of two back-to-back palindromes of the same length. The sequences "aa" and "abbanoon" would be examples of dual palindromes as would the number "12214774" since it is composed of:

• "1221" (a palindrome of length 4)
• "4774" (another palindrome of length 4)

Your program should output each number that is a dual palindrome along with the broken up version of that number (where the two parts are both palindromes).

As an example, if the number were: 212373 your output should look something like:

[212373] => [212] + [373]

To check your results, note that there are a total of 9,180 dual palindromes less than one million. Additionally, here are the first and last 20 lines of output your program should produce:

[10] => [1] + [0]
[11] => [1] + [1]
[12] => [1] + [2]
[13] => [1] + [3]
[14] => [1] + [4]
[15] => [1] + [5]
[16] => [1] + [6]
[17] => [1] + [7]
[18] => [1] + [8]
[19] => [1] + [9]
[20] => [2] + [0]
[21] => [2] + [1]
[22] => [2] + [2]
[23] => [2] + [3]
[24] => [2] + [4]
[25] => [2] + [5]
[26] => [2] + [6]
[27] => [2] + [7]
[28] => [2] + [8]
[29] => [2] + [9]

...

[999808] => [999] + [808]
[999818] => [999] + [818]
[999828] => [999] + [828]
[999838] => [999] + [838]
[999848] => [999] + [848]
[999858] => [999] + [858]
[999868] => [999] + [868]
[999878] => [999] + [878]
[999888] => [999] + [888]
[999898] => [999] + [898]
[999909] => [999] + [909]
[999919] => [999] + [919]
[999929] => [999] + [929]
[999939] => [999] + [939]
[999949] => [999] + [949]
[999959] => [999] + [959]
[999969] => [999] + [969]
[999979] => [999] + [979]
[999989] => [999] + [989]
[999999] => [999] + [999]

► FEEDBACK: Firstly, your output was exactly correct so while I do have some (hopefully) worthwhile comments to make, the most important part (getting the program to produce the correct results) was right on track.

Let's deal with the low-hanging fruit first. Your way of converting an integer into a string is a perfectly valid way to do it, but, as of 2011 (See: https://en.wikipedia.org/wiki/C%2B%2B11) there's a more direct way to do it:

string s = std::to_string(42);

Additionally, while reversing a string and then comparing it to itself is also a completely reasonable way to decide if a string is a palindrome, we don't actually care about reversing strings in this program (except to determine "palindromeness"). The 'reverse' function is only a stepping stone that gets us part of the way to our goal.

Would it not be better to just have this function?

bool isPalindrome(const string &);

It could even be implemented in terms of 'reverse' (if that's what you'd like to do). but it could also be done another, more direct way. Here's an implementation of 'isPalindrome' that's pretty straightforward:

static bool isPalindrome(const string &s)
{
for(int i = 0, j = s.size() - 1; i < j; i ++, j --)
if(s[i] != s[j])
return(false);

return(true);
}

What this function is doing is essentially comparing the first character in 's' to the last character in 's', the second character in 's' to the second-to-last character in 's' and so on. We'll either find a pair of characters that does not match (in which case we'll return false) or 'i' runs into 'j' without any mismatches (so this is a palindrome).

Reworking this code to apply the two changes above produces:

#include <iostream>
#include <string>

using std::string;

static bool isPalindrome(const string &s)
{
for(int i = 0, j = s.size() - 1; i < j; i ++, j --)
if(s[i] != s[j])
return(false);

return(true);
}

static bool isDualPalindrome(int value)
{
string s = std::to_string(value);

// If the length of 's' is an odd number, we're done as
// there's no way 's' can become two same-sized palindromes

if(s.size() % 2 != 0)
return(false);

// Extract the two halves and see if they are palindromes

string first  = s.substr(0, s.size() / 2);
string second = s.substr(s.size() / 2);

if(!isPalindrome(first))
return(false);

if(!isPalindrome(second))
return(false);

return(true);
}

int main()
{
for(int i = 0; i < 1000000; i ++)
{
if(isDualPalindrome(i))
{
string s = std::to_string(i);

string first  = s.substr(0, s.size() / 2);
string second = s.substr(s.size() / 2);

std::cout <<
"[" << i << "] => [" << first << "] + [" << second << "]\n";
}
}

return(0);
}

The next suggestion is built around the observation that repeated code is often a sign that a function or other code-reuse mechanism might be appropriate. Note that this bit of code:

string first  = s.substr(0, s.size() / 2);
string second = s.substr(s.size() / 2);

shows up both in 'isDualPalindrome' as well as in 'main'. Observe that 'isDualPalindrom' *must* break the string 's' up into its two halves. Since that work is already being done, why not allow the results to be available to main? We can accomplish this easily enough by passing in two strings by reference to 'isDualPalindrome', that way the two parts of our number can easily be displayed in 'main'.

Also (and a much smaller) point, notice that we call 's.size()' three times in 'isDualPalindrome' even though that value (the length of the string 's') does not change. Also, the division by '2' is done more than once. Here's the resulting code with the changes above applied:

#include <iostream>
#include <string>

using std::string;

static bool isPalindrome(const string &s)
{
for(int i = 0, j = s.size() - 1; i < j; i ++, j --)
if(s[i] != s[j])
return(false);

return(true);
}

static bool isDualPalindrome(int value, string &first, string &second)
{
string s = std::to_string(value);
size_t n = s.size();

// If the length of 's' is an odd number, we're done as
// there's no way 's' can become two same-sized palindromes

if(n % 2 != 0)
return(false);

// Extract the two halves and see if they are palindromes

n /= 2;

first  = s.substr(0, n);
second = s.substr(n);

if(!isPalindrome(first))
return(false);

if(!isPalindrome(second))
return(false);

return(true);
}

int main()
{
string first, second;

for(int i = 0; i < 1000000; i ++)
{
if(isDualPalindrome(i, first, second))
{
std::cout <<
"[" << i << "] => [" << first << "] + [" << second << "]\n";
}
}

return(0);
}

One final area where a change might be worthwhile occurs here:

if(!isPalindrome(first))
return(false);

if(!isPalindrome(second))
return(false);

return(true);

There's really no reason we need two separate 'if' statements and three total 'return' statements. Our results are exactly the same if we restructure things this way:

#include <iostream>
#include <string>

using std::string;

static bool isPalindrome(const string &s)
{
for(int i = 0, j = s.size() - 1; i < j; i ++, j --)
if(s[i] != s[j])
return(false);

return(true);
}

static bool isDualPalindrome(int value, string &first, string &second)
{
string s = std::to_string(value);
size_t n = s.size();

// If the length of 's' is an odd number, we're done as
// there's no way 's' can become two same-sized palindromes

if(n % 2 != 0)
return(false);

// Extract the two halves and see if they are palindromes

n /= 2;

first  = s.substr(0, n);
second = s.substr(n);

return(isPalindrome(first) && isPalindrome(second));
}

int main()
{
string first, second;

for(int i = 0; i < 1000000; i ++)
{
if(isDualPalindrome(i, first, second))
{
std::cout <<
"[" << i << "] => [" << first << "] + [" << second << "]\n";
}
}

return(0);
}

© John F. Dumas | johnfdumas@gmail.com | main page | top of page