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? <\/p>\n
Five minutes with one or two tries? 30 seconds and nail it on the first try?<\/p>\n
What if I say that this is 2013 and your software can’t just fail because a user inputs non-ASCII data?<\/p>\n
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?<\/p>\n
No, you will in fact need several hours and hundreds of lines of code. Reversing a string is much harder than one would think. <\/p>\n
The following are cases that a string reversal algorithm could reasonably be expected to handle, but which your initial, naive implementation most likely fails:<\/p>\n
Wikipedia says that “The byte order mark<\/a> (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.” <\/p>\n 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? <\/p>\n Environment based around 16-bit character types, like Java and C#’s If two chars form a single code point (see e.g. Java’s Trashing characters in the string is not a property of correct string reversers. Please fix.<\/p>\n While there is a separate character for “\u00f1”, 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.<\/p>\n In this way, you can encode “pin~a colada”, and it will render as “pi\u00f1a colada”. If the string is trivially reversed, it becomes “adaloc a~nip” which will render as “adaloc \u00e3nip”. The tilde is now on the wrong character.<\/p>\n Please don’t shuffle diacritical marks in the input string. Just reverse it.<\/p>\n 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<\/i> composing characters go between<\/i> the characters they compose. <\/p>\n To put a ‘double macron below’ under the characters “ea” in “mean”, you’d encode “me_an” which renders as “mea<\/u>n”. If you try to reverse it while keeping the macron after the “e”, you end up with “nae_m” (“naem<\/u>“) rather than the original, correct “na_em” (“nae<\/u>m”).<\/p>\n What’s “hello world” backwards? It’s “hello world” if your implementation is to be believed. <\/p>\n It happens to be encoded with left-to-right and right-to-left overrides as “U+202D U+202E dlrow olleh”. <\/p>\n 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.<\/p>\n Your string reverser doesn’t actually reverse strings. Would you kindly sort that out?<\/p>\n Obviously, it also has to handle explicit directional embedding, U+202A and U+202B, which are similar but not identical to directional overrides.<\/p>\n Reversal issues occur naturally in bidirectional text. A mix such as “hello \u05e2\u05d5\u05dc\u05dd” will render “hello” LTR and “\u05e2\u05d5\u05dc\u05dd” RTL (the “\u05dd” 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.<\/p>\n If we trivially reverse this string, we get “olleh \u05dd\u05dc\u05d5\u05e2” 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. <\/p>\n Obviously, “hello \u05e2\u05d5\u05dc\u05dd” backwards is “\u05dd\u05dc\u05d5\u05e2 olleh”. Please add this to your list. <\/p>\n 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.<\/p>\n “(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.<\/p>\n Didn’t we already file two bugs about this? <\/p>\n 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!<\/p>\n 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. <\/p>\n Here’s the ten thousand word specification<\/a> of the Unicode directionality algorithm. Have fun.<\/p>\n 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<\/a>, alongside the text. <\/p>\n If your browser supports it, here’s an example: \u6f22Surrogate pairs<\/h5>\n
char<\/code> and some C\/++ compilers’ wchar_t<\/code>, 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<\/code>, and will be encoded as a surrogate pair – two char<\/code>s next to each other.<\/p>\nString.codePointAt(int)<\/code><\/a>), reversing them produces an invalid character. <\/p>\nComposing characters<\/h5>\n
Directional overrides<\/h5>\n
RTL scripts<\/h5>\n
Left-to-right and right-to-left markers<\/h5>\n
Pop directional formatting<\/h5>\n
Interlinear annotations<\/h5>\n