I was completing a challenge on codefights, the challenge was:

Quote

Given a string, find the shortest possible string which can be achieved by adding characters to the end of initial string to make it a palindrome.

Example

For st = "abcdc", the output should be
buildPalindrome(st) = "abcdcba".

Below my solution and the top rated solution:

MySolution:

string buildPalindrome(string str) {
	auto BeginIt = str.begin();
	auto EndIt = str.end() - 1;
	bool IsAlreadyPalindrome = true;
	
	for (; BeginIt < EndIt; BeginIt++, EndIt--) {
		if (*BeginIt != *EndIt) {
			EndIt = str.end();
			IsAlreadyPalindrome = false;
		}
	}

	//case midpoint not found
	if (BeginIt != EndIt) {
		//case is a palindrome
		if (IsAlreadyPalindrome) {
			return str;
		}
		//case not a palindrome, no midpoint
		if (str[str.size() - 1] == str[str.size() - 2])
		{
			string HalfStr(str.substr(0, BeginIt - str.begin()));
			return string(HalfStr + string(HalfStr.rbegin(), HalfStr.rend()));
		}
	}
	//case not a palindrome, with midpoint
	auto MidIt = BeginIt != EndIt? str.end() - 1: BeginIt;
	string HalfStr(str.substr(0, MidIt - str.begin()));
	return string(HalfStr + *MidIt + string(HalfStr.rbegin(), HalfStr.rend()));
}

TopRatedSolution:

std::string buildPalindrome(std::string st) {
    
    string ret(st);
    auto it = st.begin();
    while (ret != string(ret.rbegin(), ret.rend())) {
        ret.insert(st.size(), 1, *it++);
    }
    return ret;
}

Now, when I completed the challenge and checked others solution I was a bit discouraged to see that it could be completed in so few lines and took me so many, but then out of curiosity I timed it online against mine with an impossibly long string, while the top rated took 13sec to solve it mine took 0,33sec...

Now I'm pretty sure mine won't ever get a single vote because it looks ugly to see (too many lines).

Now I'm not saying mine is better (now after solving I see 2 things that could be easily improved also), I realize that readability is important and such a function won't ever be used with strings that long, so my performance gain was  pretty much pointless in all real contexts (and also accidental by the way, I was just trying to solve the challenge in the most straightforward way I could see), though I am kind of disappointed by the fact that a site about challenging others and improving, made by hundreds of programmers is "celebrating" something as empty/meaningless as "number of lines used" over readability or performance...

I mean, couldn't that site have users voting on readability and a scoring given by the site based on performances?!

I'm not a fan of that mentality of "watch how hacky I am, can solve it in 0 lines" if then is not readable and the performance are atrocious (not saying is the case with all the short solutions btw), I should probably just start avoiding that place because with that goals/highlights in mind, seems like a good way to train bad programmers in mass to me...

Anyway, just my rant because I'm still disappointed it took me so many lines

What's your opinion on this? Shouldn't sites like that hold to higher standards?

5 hours ago, MarcusAseth said:

I mean, couldn't that site have users voting on readability and a scoring given by the site based on performances?!

The smallest solution is actually quite readable (with regard to the code) and also quite understandable (with regard to the algorithm). If we follow: Make It Work -> Make It Right -> Make It Fast, than the smallest solution would be difficult to beat (i.e. refactor) with regard to "Make It Right". (The performance, however, is bad if considered in isolation, but that would be premature optimization in a larger code base.)

Performance in the sense of hard numbers is not really important. Time and Memory Complexity (though determining performance) are way more important in my opinion. For example: a logarithmic Time Complexity is always preferable to a linear, quadratic, or cubic Time Complexity. One caveat is of course the difference between the input which you intend to use and the input you could use. For example: if you only intend small strings as input, a linear Time complexity can be better than a logarithmic Time Complexity (because both curves will intersect somewhere). Another caveat is the balancing between Time and Memory Complexity which can contradict each other in some problems. So what are you going to favor latency/throughput or memory usage?

The LOC (lines of code) on the other hand is a much easier criterion to check. Though, it seems rather odd, since most languages (including C++) allow you to write all your code on a single line. So you can still beat him on that criterion. A slightly better criterion than LOC would be the number of bytes which is typically used for golfing challenges. But now the problem becomes readability, since you will basically use single character names for variables, parameters and methods.

So the baseline is that it is not easy to come up with some universal criteria for the quality of code snippets.

5 hours ago, MarcusAseth said:

What's your opinion on this? Shouldn't sites like that hold to higher standards?

Who am I to say what that site can or cannot do ? Furthermore, the users are actually casting their vote.

const std::string buildPalindrome(const std::string &st) {
    std::string ret(st);
    auto it = st.begin();
    while (ret != std::string(ret.rbegin(), ret.rend())) {
        ret.insert(st.size(), 1, *it++);
    }
    return ret;
}

Way better with some minor modifications  (but I guess, I was not allowed to modify the signature).

Your solution is not correct, it does not return the shortest possible answer for a string like "abcdccdc".

You need to check things more seriously, think 'what could go wrong' all the time - it happens even with the simplest things.

Quote

You need to check things more seriously, think 'what could go wrong' all the time - it happens even with the simplest things.

Well is not like I wasn't doing that, just a brainfart, I've wrote:

if (str[str.size() - 1] == str[str.size() - 2])

(hard-coding the last 2 character positions) instead of actually using the final position of my iterators, and I was relying too much on codefights tests to catch stuff

Nice catch, fixed

string buildPalindrome(string str) {
	auto BeginIt = str.begin();
	auto EndIt = str.end() - 1;
	bool IsAlreadyPalindrome = true;

	for (; BeginIt < EndIt; BeginIt++, EndIt--) {
		if (*BeginIt != *EndIt) {
			EndIt = str.end();
			IsAlreadyPalindrome = false;
		}
	}

	if (IsAlreadyPalindrome) {
		return str;
	}

	//case not a palindrome, no midpoint
	if (BeginIt != EndIt) {
		if (*BeginIt == *EndIt){
			string HalfStr(str.substr(0, BeginIt - str.begin()));
			return string(HalfStr + string(HalfStr.rbegin(), HalfStr.rend()));
		}
	}
	//case not a palindrome, with midpoint
	auto MidIt = BeginIt != EndIt ? str.end() - 1 : BeginIt;
	string HalfStr(str.substr(0, MidIt - str.begin()));
	return string(HalfStr + *MidIt + string(HalfStr.rbegin(), HalfStr.rend()));
}

Ooops, ok - assuming it works now i'd choose you over the winner, even with the bug. Winning algorithm performance is terrible, your's seem probably ideal to me. We always have to balance dev time / performance, but in this case the difference is just huge.

But: Size may not matter, but it matters if you have balls. Having balls means you give a s**t about such ratings  hehe

Also this is kind of off topic, but I need to know

In my code above, you see that when we enter the if() inside the for() loop we set a bool to false, but that is needed only once and makes no sense to keep setting it to false every time after the first, since is never going to go back to true...

so I fixed it like this:

string buildPalindrome(string str) {
	auto BeginIt = str.begin();
	auto EndIt = str.end() - 1;

	for (; BeginIt < EndIt; BeginIt++, EndIt--) {
		if (*BeginIt != *EndIt) {
			EndIt = str.end();
		}
	}

	if (BeginIt - str.begin() == (str.end()-1) - EndIt) {
		return str;
	}

	//case midpoint not found
	if (BeginIt != EndIt) {
		//case not a palindrome, no midpoint
		if (*BeginIt == *EndIt)
		{
			string HalfStr(str.substr(0, BeginIt - str.begin()));
			return string(HalfStr + string(HalfStr.rbegin(), HalfStr.rend()));
		}
	}
	//case not a palindrome, with midpoint
	auto MidIt = BeginIt != EndIt ? str.end() - 1 : BeginIt;
	string HalfStr(str.substr(0, MidIt - str.begin()));
	return string(HalfStr + *MidIt + string(HalfStr.rbegin(), HalfStr.rend()));
}

The line:

	if (BeginIt - str.begin() == (str.end()-1) - EndIt) {
		return str;
	}

compares the distances of the iterators from both ends of the string, if is equal then is a palindrome because if it wasn't, the for() loop would have took the EndIt back to end(), making is distance smaller than BeginIt.

But I lost in readability because I think it is not immediately obvious what it does.

So I was thinking, there is in the language something similar to a "static assignment"? Basically with the quality of a static declaration which initialize a variable only once, but is an assignment meaning I assign something only once the first time, no matter how many time I loop trough it.

Something like:

bool IsAlreadyPalindrome = true;

for(int i = 0; i < 10; i++)
{
   static_assign IsAlreadyPalindrome = false;
}

meaning it would set the bool only once the first iteration trough the loop, never after. Does C++ have something that allows me toexpress that? :\

Got infected and tried myself:

std::string buildPalindrome (const std::string st) 
{
	int const size = (int)st.size();
	int back = size - 1;
	for (int n=0; n<size; n++)
	{
		if (st[n] == st[back])
			back--; // found one more
		else
			back = size-1; // reset search
	}  
	if (back<0) return st;
	return st + std::string(st.rbegin() + (size-back)-1, st.rend());
};

I think algorithm is same as yours (but i'm unused to iterators, strings, auto, so i have a herd time reading it).

I'm not 100% sure there is no bug

36 minutes ago, MarcusAseth said:

So I was thinking, there is in the language something similar to a "static assignment"? Basically with the quality of a static declaration which initialize a variable only once, but is an assignment meaning I assign something only once the first time, no matter how many time I loop trough it.

Something like:

bool IsAlreadyPalindrome = true;

for(int i = 0; i < 10; i++)
{
   static_assign IsAlreadyPalindrome = false;
}

meaning it would set the bool only once the first iteration trough the loop, never after. Does C++ have something that allows me toexpress that? :\

You can write just  

bool const foo = true;

If you want to make clear this never changes. But there is no way to say variable will be set only once within a loop.

You could factor out the size-1 due to the zero indexing:

const std::string buildPalindrome(const std::string &str) {
    const int end_index = static_cast< int >(str.size()) - 1;
    int back = end_index;
    for (int n = 0; n <= end_index; ++n) {
        if (str[n] == str[back]) { // found one more
            --back;
        }
        else { // reset search
            back = end_index;
        }
    }  

    return (back < 0) ? 
      str : str + std::string(str.rbegin() + end_index-back, str.rend());
};

What I really like about this solution is the explicit str + ... . This makes really clear what the algorithm is doing and actually should do. The former (longer) solution creates two strings which is less clear (and also slower; though strings are optimized to not allocate on the heap if below a certain size), IMO.

let's write a pathtracer with 19 lines.