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.
Who are you talking to? Was there some sort of contest?
Before you go too far with mocking these theoretical solutions, you should be more clear about what the problem was. If someone told me \reverse a string\, I’d ask \what do you mean?\ Here, you seem to have meant: \Given a sequence of Unicode code points, return a new sequence of Unicode code points such that, when rendered as individual glyphs, the ordering of glyphs in the result is left-right mirror image of their ordering in the rendering of the original sequence\. But even then, you’d need to be more clear. For example, byte order marks have to do with the encoding, not the code points themselves, so that point is irrelevant. Second, what do you consider a glyph? Why do you consider the result of a double composing character to be two separate glyphs that should be reversed independently, and why should the interlinear annotation for a glyph be reversed (certainly the description of that glyph hasn’t changed).
Conclusion: String reversal is poorly defined. String is poorly defined. The proper response to this programming challenge is \Tell me what actual goal you’re hoping to accomplish, and I will do it.\. I hope you had fun anyways!
@Jim
I love your argument about interlinear annotations! I can imagine that when used for pronunciation as in Asian languages, the ruby should be as you describe, while for translation as used in western contexts (well, bibles), you’d want it reversed.
Do you know of any cases in which a double composing characters would be treated as one? I haven’t seen any cases where something with e.g. double combining macron like “mean” should be “neam” in reverse, but it would be really interesting to find some.
You are, of course, right about the proper response. Reversing a string is in itself a very pointless and artificial thing to do, despite the popularity of this question. In any case, the topic is much broader than many people think!
Also, I’ve turned down the mocking by 10% :P
So where can I download the source code of your final string reverser? Hehe… xD
Some regex engines like Perl have
\Xwhich matches extended grapheme clusters (and in some others engines matches legacy grapheme clusters). Grapheme clusters are user-perceived characters and include composing character sequences as well as other code point sequences.Leveraging
\Xmakes reversing strings without reversing code points within a grapheme cluster very simple:use utf8;my $str = "g̈ 각 กำ நி षि \r\n";
my $rev = join('', reverse($str =~ /\X/g));
# \r\n षि நி กำ 각 g̈
\Xcan also be used for counting characters as grapheme clusters. In general, I recommend using it in regular expressions instead of.when matching a single character.