5 ms·

So, in terms of acing interviews, increasingly one of the best answers to the question "Write some code that reverses a string" is that in a world of unicode, "

by jerf 5y ago

So, in terms of acing interviews, increasingly one of the best answers to the question "Write some code that reverses a string" is that in a world of unicode, "reversing a string" is no longer possible or meaningful. You'll probably be told "oh, assume US ASCII" or something, but in the meantime, if you can back that up when they dig into it, you'll look really smart.

happytoexplain 5y ago
I would argue that it is possible and meaningful. AFAIK extended grapheme clusters are well defined by the standard, and are very well suited to the default meaning of when somebody says "character", so, given no other information, it's reasonable to reverse a string based on them. I guess the issue is "reverse a string" lacks details, but I think that's different from "not meaningful".
Spivak 5y ago
Reversing a string is still meaningful. Take a step back outside the implementation and imagine handing a Unicode string to a human. They could without any knowledge look at the characters they see and produce the correct string reversal. There is a solution to this which is to compute the list of grapheme clusters, and reverse that. https://unicode.org/reports/tr29/ https://unicode.org/reports/tr29/
- akersten 5y ago
  > imagine handing a Unicode string to a human. They could without any knowledge look at the characters they see and produce the correct string reversal. I really highly doubt it. How do you reverse this?: مرحبًا ، هذه سلسلة. Can you do it without any knowledge about whether what looks like one character is actually a special case joiner between two adjacent codepoints that only happens in one direction? Can you do it without knowing that this string appears wrongly in the HN textbbox due to an apparent RTL issue? It's just not well-defined to reverse a string, and the reason we say it's not meaningful is that no User Story ever starts "as a visitor to this website I want to be able to see this string in opposite order, no not just that all the bytes are reversed, but you know what I mean."
  - adolph 5y ago
    Is a RTL character string already "reversed" from a LTR POV? Is an absolute value signed as positive?
  - Spivak 5y ago
    I mean no but only because I don’t understand the characters. Someone who reads Arabic (I assume based on the shape) would have no trouble. You’re nitpicking cases where for some readers visual characters might be hard to distinguish but it doesn’t change the fact that there exists a correct answer for every piece of text that will be obvious to readers of that text which is the definition of a grapheme cluster.
    - akersten 5y ago
      > the fact that there exists a correct answer for every piece of text that will be obvious to readers of that text which is the definition of a grapheme cluster. No, I insist there is not a single "correct answer," even if a reader has perfect knowledge of the language(s) involved. Now remember, this is already moving the goalposts, since it was claimed that a human needed "no knowledge" to get to this allegedly "correct answer." You already admit that people who don't speak Arabic will have trouble finding the "grapheme clusters," but even two people who speak Arabic may do your clustering or not, depending on some implicit feeling of "the right way to do it" vs taking the question literally and pasting the smallest highlight-able selection of the string in reverse at a time. Anyway, take a string like this: "here is some Arabic text: <RLM> <Arabic codepoints> <LRM> And back to English" Whether you discard the ordering mark[0], keep them, or inverse them is an implementation decision that already produces three completely different strings. Unless we want to write a rulebook for the right way to reverse a string, it remains an impossibility to declare anything the correct answer, and because there is no reason to reverse such a string outside of contrived interview questions and ivory tower debates, it is also meaningless. [0]: https://en.m.wikipedia.org/wiki/Right-to-left_mark https://en.m.wikipedia.org/wiki/Right-to-left_mark https://en.m.wikipedia.org/wiki/Left-to-right_mark https://en.m.wikipedia.org/wiki/Left-to-right_mark
      - 5y ago
- lloeki 5y ago
  Should it reverse a BOM as well or keep it first?
  - Spivak 5y ago
    Keep it first? Like that’s not a gotcha. Your input is a string and the output is that string visually reversed. What it looks like in memory is irrelevant.
  - account42 5y ago
    Remove it since the BOM is a hack to deal with shitty transfer encodings (i.e. UTF-16LE vs. UTF-16BE) and useless for UTF-8.
- chrismorgan 5y ago
  UAX #29 is insufficient: at the very least, you must depend on collation too. In Norwegian, “æ” is a letter, so I believe (as a non-speaker) that they would reverse “blåbærene” to “eneræbålb”; but in English, it’s a ligature representing the diphthong “ae”, and if asked to reverse “æsthetic” I would certainly write “citehtsea” and consider “citehtsæ” to be wrong. (And I enjoy writing the ligature; I fairly consistently write and type æsthetic rather than aesthetic, though I only write encyclopædia instead of encyclopaedia when I’m in a particular sort of mood.) In Dutch, the digraph “ij” is sometimes considered a ligature and sometimes a letter; as a non-speaker, I don’t know whether natives would say that it should be treated as an atom in reversing or not. And not all languages will have the concept of reversing even letters, let alone other things. Face it: in English we have the concept of reversing things, but it just doesn’t work the same way in other languages. Sure, UAX #29 defines something that happens to be a good heuristic for reversing, but it doesn’t define reversing, and in the grand scheme of things reversing grapheme-wise is still Wrong. “Reversing a string” is just not a globally meaningful concept. Another person here has cited Cherokee transliteration, where one extended grapheme cluster turns into multiple English letters. You can apply this to translation in general, but also even keep it inside English and ask: what are we reversing? Letters? Phonemes? Syllables? Words? There are plenty of possibilities which are used in different contexts (and it’s mostly in puzzles, frankly, not general day-to-day life). The concept of grapheme clusters is acknowledged as approximate. Collations are acknowledged as approximate. Reversing would be even more approximate.
  - chrismorgan 5y ago
    Interesting addendum on the matter of reversing “æsthetic”: I asked my parents what they reckoned, and they both went the other way, reckoning that if you wrote æ in the initial word it should stay æ; my dad said he wouldn’t write it that way in the first place, but that if you’ve written it that way you were treating æ as a letter more than just a way of drawing a certain pair of letters. In declaring otherwise, I was using the linguistic approach, which acknowledges æ as a ligature of the ae diphthong from Latin, being purely stylistic and not semantic. And so we see still more how these things are approximations and subjective.
greenyoda 5y ago
> "reversing a string" is no longer possible or meaningful. If you really wanted to, you could write a string reversal algorithm that treated two-character emojis as an indivisible element of the string and preserved its order (just as you'd need to preserve the order of the bytes in a single multi-byte UTF-8 character). You'd just need to carefully specify what you mean by the terms "string", "character" and "reverse" in a way that includes ordered, multi-character sequences like flag emojis.
paxys 5y ago
UTF-8 reverse string has been a thing for a long time in most/all programming languages. It may not work perfectly in 100% of the cases, but that doesn't mean reversing a string is no longer possible.
- jerf 5y ago
  "It may not work perfectly in 100% of the cases, but that doesn't mean reversing a string is no longer possible." It depends on your point of view. From a strict point of view, it does exactly mean it is no longer possible. By contrast, we all 100% knew what reversing an ASCII string meant, with no ambiguity. It also depends on the version of Unicode you are using, and oh by the way, unicode strings do not come annotated with the version they are in. Since it's supposed to be backwards compatible hopefully the latest works, but I'd be unsurprised if someone can name something whose correct reversal depends on the version of Unicode. And, if not now, then in some later not-yet-existing pair of Unicode standards.
  - pwdisswordfish9 5y ago
    > By contrast, we all 100% knew what reversing an ASCII string meant, with no ambiguity. Not if the ASCII string employed the backspace control character to accomplish what is today done with Unicode combining characters. Or, in fact, if it employed any other kind of control sequence.
    - thaumasiotes 5y ago
      I always thought it was interesting that ASCII is transparently just a bunch of control codes for a typewriter (where "strike an 'a'" is a mechanical instruction no different from "reset the carriage position"), but when we wanted to represent symbolic data we copied it and included all of the nonsensical mechanical instructions.
      - adzm 5y ago
        Well the control codes were specifically for TTY rather than typewriters, many of the control codes still make sense from that standpoint.
viktorcode 5y ago
You certainly can. `print(String(flag.reversed()))` in Swift reverses emojis correctly.
- account42 5y ago
  How does it handle the ASCII examples in https://news.ycombinator.com/item?id=30108184 https://news.ycombinator.com/item?id=30108184 And more importantly: What is the use case for a reversed string?
  - Etherlord87 5y ago
    The use case: Make an animation, where the text appears starting from the end - for example if you stylize it as vertical text falling from the top. I think the example shows quite clearly the problem really comes down to dividing the string to logical parts (atoms, grapheme clusters, however you want to call it).
jameshart 5y ago
I'd go further and argue that in general reversing a string isn't possible or meaningful. It's just not a thing people do, so it's just... not very interesting to argue about what the 'correct' way to do it is. Similarly, any argument over whether a string has n characters or n+1 characters in it is almost entirely meaningless and uninteresting for real world string processing problems. Allow me to let you into a secret: there's never really such a thing as a 'character limit' There might be a 'printable character width' limit; or there might be a 'number of bytes of storage' limit. Which means interesting questions about a string include things like 'how wide is it when displayed in this font?' or 'how many bytes does it take to store or transmit it?'... But there's rarely any point where, for a general string, it is really interesting to know 'how many characters does the string contain?' Processing direct user text input is the only situation where you really need a rich notion of 'character', because you need to have a clear sense of what will happen if the user moves a cursor using a left or right arrow, and for exactly what will be deleted when a user hits backspace, or copied/cut and pasted when they operate on a selection. The ĳ ligature might be a single glyph, but is it a single character? When does it matter? Probably not at all unless you're trying to decide whether to let a user put a cursor in the middle of it or not. And next to that, I just feel to argue that there is such a thing as a 'correct' way to reverse "Rĳndæl" according to a strict reading of Unicode glyph composability rules seems like a supremely silly thing to try to do. I'd much rather, when asked to reverse a string, more developers simply said 'that doesn't make sense, you can't arbitrarily chunk up a string and reassemble it in a different order and expect any good to come of it'.
- jerf 5y ago
  Boy, that's implicitly a good question... when's the last time I "reversed" a string, on purpose, for something useful? It took me a bit, but I think I have an answer. It's about 15 years ago. I didn't actually do the original design, but I perpetuated it and didn't remove it. We reversed domain name strings (which, given that they are a subset of ASCII, actually is a well-defined operation) so that the DB we're using, which supported efficient prefix lookups but not suffix lookups, could be used to efficiently query for all subdomains of a given domain, by reversing the domain and using that as the prefix. I mean this as strong support for your point, not a contradictory "gotcha". I'm a big believer in not doing lots of work to save effort or make correct something you do less than once a decade, e.g., http://www.jerf.org/iri/post/2954 http://www.jerf.org/iri/post/2954 . And it's not even a gotcha anyhow, because we aren't reversing a general string; we were reversing a string very tightly constrained to a subset of ASCII where the operation was fully well-defined. I can't think of when I ever reversed a general string.
Someone 5y ago
Even ASCII can be argued to be problematic. What is “3 >= 2", reversed? What is “Rijksmuseum”, reversed? (https://en.wikipedia.org/wiki/IJ_(digraph) https://en.wikipedia.org/wiki/IJ_(digraph); capitalization isn’t simple here, either (https://en.wikipedia.org/wiki/IJ_(digraph)#Capitalisation https://en.wikipedia.org/wiki/IJ_(digraph)#Capitalisation) What is “Schroeder”, reversed? (https://en.wikipedia.org/wiki/Diaeresis_(diacritic)#Printing_conventions_in_German https://en.wikipedia.org/wiki/Diaeresis_(diacritic)#Printing...)
spicybright 5y ago
Sure it is, just render the same string in right to left!

by jerf 5y ago

happytoexplain 5y ago

I would argue that it is possible and meaningful. AFAIK extended grapheme clusters are well defined by the standard, and are very well suited to the default meaning of when somebody says "character", so, given no other information, it's reasonable to reverse a string based on them. I guess the issue is "reverse a string" lacks details, but I think that's different from "not meaningful".

Spivak 5y ago

Reversing a string is still meaningful. Take a step back outside the implementation and imagine handing a Unicode string to a human. They could without any knowledge look at the characters they see and produce the correct string reversal. There is a solution to this which is to compute the list of grapheme clusters, and reverse that. https://unicode.org/reports/tr29/ https://unicode.org/reports/tr29/

akersten 5y ago
> imagine handing a Unicode string to a human. They could without any knowledge look at the characters they see and produce the correct string reversal. I really highly doubt it. How do you reverse this?: مرحبًا ، هذه سلسلة. Can you do it without any knowledge about whether what looks like one character is actually a special case joiner between two adjacent codepoints that only happens in one direction? Can you do it without knowing that this string appears wrongly in the HN textbbox due to an apparent RTL issue? It's just not well-defined to reverse a string, and the reason we say it's not meaningful is that no User Story ever starts "as a visitor to this website I want to be able to see this string in opposite order, no not just that all the bytes are reversed, but you know what I mean."
- adolph 5y ago
  Is a RTL character string already "reversed" from a LTR POV? Is an absolute value signed as positive?
- Spivak 5y ago
  I mean no but only because I don’t understand the characters. Someone who reads Arabic (I assume based on the shape) would have no trouble. You’re nitpicking cases where for some readers visual characters might be hard to distinguish but it doesn’t change the fact that there exists a correct answer for every piece of text that will be obvious to readers of that text which is the definition of a grapheme cluster.
  - akersten 5y ago
    > the fact that there exists a correct answer for every piece of text that will be obvious to readers of that text which is the definition of a grapheme cluster. No, I insist there is not a single "correct answer," even if a reader has perfect knowledge of the language(s) involved. Now remember, this is already moving the goalposts, since it was claimed that a human needed "no knowledge" to get to this allegedly "correct answer." You already admit that people who don't speak Arabic will have trouble finding the "grapheme clusters," but even two people who speak Arabic may do your clustering or not, depending on some implicit feeling of "the right way to do it" vs taking the question literally and pasting the smallest highlight-able selection of the string in reverse at a time. Anyway, take a string like this: "here is some Arabic text: <RLM> <Arabic codepoints> <LRM> And back to English" Whether you discard the ordering mark[0], keep them, or inverse them is an implementation decision that already produces three completely different strings. Unless we want to write a rulebook for the right way to reverse a string, it remains an impossibility to declare anything the correct answer, and because there is no reason to reverse such a string outside of contrived interview questions and ivory tower debates, it is also meaningless. [0]: https://en.m.wikipedia.org/wiki/Right-to-left_mark https://en.m.wikipedia.org/wiki/Right-to-left_mark https://en.m.wikipedia.org/wiki/Left-to-right_mark https://en.m.wikipedia.org/wiki/Left-to-right_mark
    - 5y ago
lloeki 5y ago
Should it reverse a BOM as well or keep it first?
- Spivak 5y ago
  Keep it first? Like that’s not a gotcha. Your input is a string and the output is that string visually reversed. What it looks like in memory is irrelevant.
- account42 5y ago
  Remove it since the BOM is a hack to deal with shitty transfer encodings (i.e. UTF-16LE vs. UTF-16BE) and useless for UTF-8.
chrismorgan 5y ago
UAX #29 is insufficient: at the very least, you must depend on collation too. In Norwegian, “æ” is a letter, so I believe (as a non-speaker) that they would reverse “blåbærene” to “eneræbålb”; but in English, it’s a ligature representing the diphthong “ae”, and if asked to reverse “æsthetic” I would certainly write “citehtsea” and consider “citehtsæ” to be wrong. (And I enjoy writing the ligature; I fairly consistently write and type æsthetic rather than aesthetic, though I only write encyclopædia instead of encyclopaedia when I’m in a particular sort of mood.) In Dutch, the digraph “ij” is sometimes considered a ligature and sometimes a letter; as a non-speaker, I don’t know whether natives would say that it should be treated as an atom in reversing or not. And not all languages will have the concept of reversing even letters, let alone other things. Face it: in English we have the concept of reversing things, but it just doesn’t work the same way in other languages. Sure, UAX #29 defines something that happens to be a good heuristic for reversing, but it doesn’t define reversing, and in the grand scheme of things reversing grapheme-wise is still Wrong. “Reversing a string” is just not a globally meaningful concept. Another person here has cited Cherokee transliteration, where one extended grapheme cluster turns into multiple English letters. You can apply this to translation in general, but also even keep it inside English and ask: what are we reversing? Letters? Phonemes? Syllables? Words? There are plenty of possibilities which are used in different contexts (and it’s mostly in puzzles, frankly, not general day-to-day life). The concept of grapheme clusters is acknowledged as approximate. Collations are acknowledged as approximate. Reversing would be even more approximate.
- chrismorgan 5y ago
  Interesting addendum on the matter of reversing “æsthetic”: I asked my parents what they reckoned, and they both went the other way, reckoning that if you wrote æ in the initial word it should stay æ; my dad said he wouldn’t write it that way in the first place, but that if you’ve written it that way you were treating æ as a letter more than just a way of drawing a certain pair of letters. In declaring otherwise, I was using the linguistic approach, which acknowledges æ as a ligature of the ae diphthong from Latin, being purely stylistic and not semantic. And so we see still more how these things are approximations and subjective.

greenyoda 5y ago

> "reversing a string" is no longer possible or meaningful. If you really wanted to, you could write a string reversal algorithm that treated two-character emojis as an indivisible element of the string and preserved its order (just as you'd need to preserve the order of the bytes in a single multi-byte UTF-8 character). You'd just need to carefully specify what you mean by the terms "string", "character" and "reverse" in a way that includes ordered, multi-character sequences like flag emojis.

paxys 5y ago

UTF-8 reverse string has been a thing for a long time in most/all programming languages. It may not work perfectly in 100% of the cases, but that doesn't mean reversing a string is no longer possible.

jerf 5y ago
"It may not work perfectly in 100% of the cases, but that doesn't mean reversing a string is no longer possible." It depends on your point of view. From a strict point of view, it does exactly mean it is no longer possible. By contrast, we all 100% knew what reversing an ASCII string meant, with no ambiguity. It also depends on the version of Unicode you are using, and oh by the way, unicode strings do not come annotated with the version they are in. Since it's supposed to be backwards compatible hopefully the latest works, but I'd be unsurprised if someone can name something whose correct reversal depends on the version of Unicode. And, if not now, then in some later not-yet-existing pair of Unicode standards.
- pwdisswordfish9 5y ago
  > By contrast, we all 100% knew what reversing an ASCII string meant, with no ambiguity. Not if the ASCII string employed the backspace control character to accomplish what is today done with Unicode combining characters. Or, in fact, if it employed any other kind of control sequence.
  - thaumasiotes 5y ago
    I always thought it was interesting that ASCII is transparently just a bunch of control codes for a typewriter (where "strike an 'a'" is a mechanical instruction no different from "reset the carriage position"), but when we wanted to represent symbolic data we copied it and included all of the nonsensical mechanical instructions.
    - adzm 5y ago
      Well the control codes were specifically for TTY rather than typewriters, many of the control codes still make sense from that standpoint.

viktorcode 5y ago

You certainly can. `print(String(flag.reversed()))` in Swift reverses emojis correctly.

account42 5y ago
How does it handle the ASCII examples in https://news.ycombinator.com/item?id=30108184 https://news.ycombinator.com/item?id=30108184 And more importantly: What is the use case for a reversed string?
- Etherlord87 5y ago
  The use case: Make an animation, where the text appears starting from the end - for example if you stylize it as vertical text falling from the top. I think the example shows quite clearly the problem really comes down to dividing the string to logical parts (atoms, grapheme clusters, however you want to call it).

jameshart 5y ago

I'd go further and argue that in general reversing a string isn't possible or meaningful. It's just not a thing people do, so it's just... not very interesting to argue about what the 'correct' way to do it is. Similarly, any argument over whether a string has n characters or n+1 characters in it is almost entirely meaningless and uninteresting for real world string processing problems. Allow me to let you into a secret: there's never really such a thing as a 'character limit' There might be a 'printable character width' limit; or there might be a 'number of bytes of storage' limit. Which means interesting questions about a string include things like 'how wide is it when displayed in this font?' or 'how many bytes does it take to store or transmit it?'... But there's rarely any point where, for a general string, it is really interesting to know 'how many characters does the string contain?' Processing direct user text input is the only situation where you really need a rich notion of 'character', because you need to have a clear sense of what will happen if the user moves a cursor using a left or right arrow, and for exactly what will be deleted when a user hits backspace, or copied/cut and pasted when they operate on a selection. The ĳ ligature might be a single glyph, but is it a single character? When does it matter? Probably not at all unless you're trying to decide whether to let a user put a cursor in the middle of it or not. And next to that, I just feel to argue that there is such a thing as a 'correct' way to reverse "Rĳndæl" according to a strict reading of Unicode glyph composability rules seems like a supremely silly thing to try to do. I'd much rather, when asked to reverse a string, more developers simply said 'that doesn't make sense, you can't arbitrarily chunk up a string and reassemble it in a different order and expect any good to come of it'.

jerf 5y ago
Boy, that's implicitly a good question... when's the last time I "reversed" a string, on purpose, for something useful? It took me a bit, but I think I have an answer. It's about 15 years ago. I didn't actually do the original design, but I perpetuated it and didn't remove it. We reversed domain name strings (which, given that they are a subset of ASCII, actually is a well-defined operation) so that the DB we're using, which supported efficient prefix lookups but not suffix lookups, could be used to efficiently query for all subdomains of a given domain, by reversing the domain and using that as the prefix. I mean this as strong support for your point, not a contradictory "gotcha". I'm a big believer in not doing lots of work to save effort or make correct something you do less than once a decade, e.g., http://www.jerf.org/iri/post/2954 http://www.jerf.org/iri/post/2954 . And it's not even a gotcha anyhow, because we aren't reversing a general string; we were reversing a string very tightly constrained to a subset of ASCII where the operation was fully well-defined. I can't think of when I ever reversed a general string.

Someone 5y ago

Even ASCII can be argued to be problematic. What is “3 >= 2", reversed? What is “Rijksmuseum”, reversed? (https://en.wikipedia.org/wiki/IJ_(digraph) https://en.wikipedia.org/wiki/IJ_(digraph); capitalization isn’t simple here, either (https://en.wikipedia.org/wiki/IJ_(digraph)#Capitalisation https://en.wikipedia.org/wiki/IJ_(digraph)#Capitalisation) What is “Schroeder”, reversed? (https://en.wikipedia.org/wiki/Diaeresis_(diacritic)#Printing_conventions_in_German https://en.wikipedia.org/wiki/Diaeresis_(diacritic)#Printing...)

spicybright 5y ago

Sure it is, just render the same string in right to left!