Oh, string reversal! The bread and butter of Programming 101 exams. If I ask you to prove your hacker worth by implementing it in your favorite language, how long would it take you and how many tries will you need to get it right?
Five minutes with one or two tries? 30 seconds and nail it on the first try?
What if I say that this is 2013 and your software can’t just fail because a user inputs non-ASCII data?
Well… Java, C#, Python, Haskell and all other modern languages have native Unicode string types, so at most you’ll just need another minute to verify that it does indeed work, right?
No, you will in fact need several hours and hundreds of lines of code. Reversing a string is much harder than one would think.
The following are cases that a string reversal algorithm could reasonably be expected to handle, but which your initial, naive implementation most likely fails:
Byte order marks
Wikipedia says that “The byte order mark (BOM) is a Unicode character used to signal the endianness (byte order) of a text file or stream. It is encoded at U+FEFF byte order mark (BOM). BOM use is optional, and, if used, should appear at the start of the text stream.”
It’s obviously a bug if the BOM ends up at the end of the string when it’s reversed. At least that’s a simple fix, right?
Surrogate pairs
Environment based around 16-bit character types, like Java and C#’s char and some C/++ compilers’ wchar_t, had an awkward time when Unicode 2.0 came along, which expanded the number of characters from 65536 to 1114112. Characters in so-called supplementary planes will not fit in a 16-bit char, and will be encoded as a surrogate pair – two chars next to each other.
If two chars form a single code point (see e.g. Java’s String.codePointAt(int)), reversing them produces an invalid character.
Trashing characters in the string is not a property of correct string reversers. Please fix.
Composing characters
While there is a separate character for “ñ”, n with tilde, it can also be written as two characters: regular “n” (U+006E) plus composing tilde (U+0303), which I’ll write as a regular tilde for illustration.
In this way, you can encode “pin~a colada”, and it will render as “piña colada”. If the string is trivially reversed, it becomes “adaloc a~nip” which will render as “adaloc ãnip”. The tilde is now on the wrong character.
Please don’t shuffle diacritical marks in the input string. Just reverse it.
By the way, if you try to fix this by ensuring that composing characters stay behind their preceding character, you’ll introduce a regression. Double composing characters go between the characters they compose.
To put a ‘double macron below’ under the characters “ea” in “mean”, you’d encode “me_an” which renders as “mean”. If you try to reverse it while keeping the macron after the “e”, you end up with “nae_m” (“naem“) rather than the original, correct “na_em” (“naem”).
Directional overrides
What’s “hello world” backwards? It’s “hello world” if your implementation is to be believed.
It happens to be encoded with left-to-right and right-to-left overrides as “U+202D U+202E dlrow olleh”.
In this direction, everything from the second character onward is shown right-to-left as “hello world”. With trivial reversion, it becomes “hello world” followed by a RLO immediately cancelled by a LRO.
Your string reverser doesn’t actually reverse strings. Would you kindly sort that out?
Obviously, it also has to handle explicit directional embedding, U+202A and U+202B, which are similar but not identical to directional overrides.
RTL scripts
Reversal issues occur naturally in bidirectional text. A mix such as “hello עולם” will render “hello” LTR and “עולם” RTL (the “ם” is encoded last, but displays leftmost in that word). When the latin script is first, the string starts from the left margin, with the first encoded character to the left.
If we trivially reverse this string, we get “olleh םלוע” as it starts rendering from the right margin. The first encoded character appears rightmost in the right word, while the last encoded displays rightmost of the leftmost word, i.e. in the middle.
Obviously, “hello עולם” backwards is “םלוע olleh”. Please add this to your list.
Left-to-right and right-to-left markers
Similarly to the two above cases, the LRM (U+200E) and RLM (U+200F) codes allows changing the direction neutral characters (such as punctuation) are rendered.
“(RLM)O:” will be rendered as “:O” in the right margin. With trivial string reversal, it will still render as “:O”, starting at the left margin.
Didn’t we already file two bugs about this?
Pop directional formatting
Once your kludged and fragile directional string reversal support appears to work reasonably ok, along comes the U+202C Pop Directional Format character. It never ends!
This character undoes the previous explicit directional override, whatever it happened to be. You can no longer try to be clever by splitting the string up into linear sections based on directional markers; you have to go full stack parsing.
Here’s the ten thousand word specification of the Unicode directionality algorithm. Have fun.
Interlinear annotations
Even if you give up and add a TODO to handle directionality, you still have some cases to go. In logographic languages like Chinese and Japanese, you can have pronunciation guides, so called ruby characters, alongside the text.
If your browser supports it, here’s an example: 漢字.
To support this in plain text, Unicode has U+FFF9 through U+FFFB, the Interlinear Annotation Anchor, Separator and Terminator characters respectively. The above could be encoded as “U+FFFF9 漢字 U+FFFA kan U+FFFA ji U+FFFB”.
Reversing the anchor and terminating characters is obviously a bug.
Your string reverser produces garbled output instead of a reversed string… Is it going to be much longer?
Note that reversing just the contents is still wrong. Instead of correctly annotating “字漢” with “ij nak”, you’d be annotating “ij” with “nak 字漢”.
Once you’ve correctly handled this case, try it again when you have an excess of separators at the end of the ruby text. Normally, these would just be ignored, but if you reversed them and put them in front, they’ll push all ruby characters away from where they were supposed to be.
For “U+FFFF9 漢字 U+FFFA kan U+FFFA ji U+FFFA U+FFFB”, instead of 字漢 you’d get 字漢.
(Update: Commenter Jim convincingly argues that you’d want to reverse the ruby logograph groups but not the characters themselves, resulting in 字漢 )
Like with the composing characters, your string reversal shuffles ruby characters around. Please… oh, why bother.
Conclusion
Your implementation most likely had half a dozen bugs. Maybe string reversal is beyond your abilities? Join the club!
Hopefully you had fun anyways.