4 ms·

I wonder how many of the solutions would still work for arbitrary unicode strings. It looks like the author assumes only ascii exists. Perhaps the interns would

by Thiez 7y ago

I wonder how many of the solutions would still work for arbitrary unicode strings. It looks like the author assumes only ascii exists. Perhaps the interns would be better off if they were taught that "reverse a string" is a fundamentally dangerous (and pointless) operation in almost any real-life context. Strings are way more complex than people give them credit for.

deleted 7y ago
[deleted]
togs 7y ago
It’s not clear to me why reversing a string is dangerous or pointless.
- bastawhiz 7y ago
  An array of characters reversed loses the original meaning of the characters. Other than looking for palindromes, there's almost nothing in the way of practical uses of a reversed string that can't be accomplished by subscripting the string and iterating from the end to the beginning.
  - PeCaN 7y ago
    Iterating from back to front doesn't work either; you probably (depending on what you're doing) still have to segment into grapheme clusters—which is stateful as of unicode 9, so you have to start from the beginning of the string. And then god forbid you get U+202C POP DIRECTIONAL FORMATTING CODE....
  - catlifeonmars 7y ago
    I found this little gem on Software engineering StackExchange: https://softwareengineering.stackexchange.com/questions/24691/what-do-you-use-string-reversal-for https://softwareengineering.stackexchange.com/questions/2469... Suffice it to say, there are many interesting uses for string reversal :)
    - bastawhiz 7y ago
      Interesting, but questionably useful. If you're converting integer bases or obfuscating email addresses, there are much better approaches that don't involve a bad hack
- jodrellblank 7y ago
  "lol :Man facepalming: :medium light skintone:" becomes the skintone applying to nothing (which might crash?) and the wrong coloured man. (e+accent a) making éa becomes (a+accent e) incorrectly making áe - or possibly invalidly making an error combination. Right-to-left markers[1] and left-to-right markers will change which sections of the text are reversed unless you swap them over. Codepoints can combine more than once, to the point where if you're too nitpicky you can't validly substring either, you can only read a string from the first codepoint onwards; they could become invalid sequences if reversed, possibly? [1] https://en.wikipedia.org/wiki/Right-to-left_mark https://en.wikipedia.org/wiki/Right-to-left_mark
  - rlayton2 7y ago
    Agree. I think reversing in non-ascii should always be thought of as "per-token", where English is character-as-token. So the reverse of what you gave would be: ":medium light skintone: :Man facepalming: lol" (with the lol reversed). In this problem, it is a much harder problem than, say in python, mystring[::-1]. Therefore, it is a different problem "reverse a string" than to "reverse an array". Accented characters would be kept as is in my scenario.
    - PeCaN 7y ago
      The "tokens" you're thinking of are "grapheme clusters" in Unicode. Unfortunately just reversing by grapheme clusters doesn't solve the problem because of directional formatting codes; if you have e.g. a right-to-left embedding followed by a pop directional formatting you can't naively reverse them.
      - naniwaduni 7y ago
        Grapheme clusters are a poor approximation of the vaguely-defined linguistic-level concept you're groping for.
        PeCaN 7y ago
        Well, yes, but we gotta stop somewhere or just give up any hope of computers operating on text. Although I think grapheme clusters are a pretty good approximation in that it's usually what you want to backspace in a word processor.
- deleted 7y ago
  [deleted]
- tragomaskhalos 7y ago
  There's actually two levels of jeopardy here: 1/ Treating a string as an array of bytes will give an invalid result if the string unless the string is simple ascii (or an equivalent encoding where each byte has a clearly defined standalone meaning); in particular, just reversing a UTF-8 string in this way will give an invalid answer - ie a string that isn't even valid UTF-8. 2/ The fix for (1) is to convert your string into an array of Unicode code points and reverse that … except that is also broken, because combining characters will now not associate correctly, as per other answers in this thread. Coding your way out of problem (2) in a robust and sensible way is, I suggest, a significant challenge.
  - to11mtm 7y ago
    Of all things, VB.Net actually has a string reverse that handles unicode cases. I'm not quite sure how to view it in referencesource, but it is on Github. [1] The result is less than 100 lines of VB so I don't think it's -that- hard. There's certainly some clever index manipulation going on but nothing that looks too crazy. [1] - https://github.com/microsoft/referencesource/blob/master/Microsoft.VisualBasic/runtime/msvbalib/Strings.vb#L1043-L1134 https://github.com/microsoft/referencesource/blob/master/Mic...
PeCaN 7y ago
Unicode strings are really, really hard. I'm working on a programming language sort of like K or APL. Among other things it has "good" unicode support (I'm fully convinced such a thing is even possible). It introduces a truly frustrating amount of complexity, especially in comparison to how simple ASCII strings are in K or APL (just an array of characters, so you get all the powerful array operations for free as shown in this post). The approach I've more or less settled on is that strings are not arrays at all but it's possible to get arrays of codepoints (composed or decomposed) or grapheme clusters from them. Really this just pushes complexity to the caller, but it means you more control over what exactly you intend to work with. Pretty much all the solutions here could be straightforwardly translated to my programming language, except you would need to choose what definition of "character" you're going with. I basically like this solution but the deeper I get the more I become convinced that manipulating an arbitrary user-provided or even user-facing string in any way is a recipe for disaster; there's often simply no sensible way to handle things like direction formatting control codes (or bidirectional text in general). In other words, I almost think there should be separate types for "computer-facing" strings (like filenames) that one commonly has to manipulate, and "human-facing" strings that one just wants to either display or store somewhere and ideally never touch because you will screw up somewhere.
- macintux 7y ago
  > In other words, I almost think there should be separate types for "computer-facing" strings (like filenames) that one commonly has to manipulate, and "human-facing" strings that one just wants to either display or store somewhere and ideally never touch because you will screw up somewhere. That's a fascinating idea, thanks. I imagine it's impractical due to numerous places where machine and human strings overlap, but I'm going to have to ruminate on it for a while.
  - etaioinshrdlu 7y ago
    It sounds a lot like what Go and perhaps Swift do. Perhaps other languages.
    - 7y ago
vl 7y ago
Especially it's ironical in the contexts of the interview, when the question is something like "write a function to reverse order of all words in the given string". So I'm thinking to myself: "You don't even comprehend how hard it's to actually do, or you know it and checking if I know it?". And then there is a need to ask a lot of probing questions just to learn the the string is ASCII and separator is space.
codeflo 7y ago
I wouldn’t call it dangerous, just meaningless. A lot of the discussion in this thread dives deeply into the technicalities of Unicode. All of that is correct, but a bit besides the point IMO. I think the real issue is that “reversing text” is fundamentally an operation that only makes sense in Western alphabets — the complexities of Unicode just reflect that. This is a bit hard to fathom for people who grew up with such an alphabet (this includes me), where there’s a rich tradition of games based on shuffling letters. It’s not just reversing; my understanding is that you can’t meaningfully define the concept of an anagram in many writing systems.

by Thiez 7y ago

deleted 7y ago

[deleted]

togs 7y ago

It’s not clear to me why reversing a string is dangerous or pointless.

bastawhiz 7y ago
An array of characters reversed loses the original meaning of the characters. Other than looking for palindromes, there's almost nothing in the way of practical uses of a reversed string that can't be accomplished by subscripting the string and iterating from the end to the beginning.
- PeCaN 7y ago
  Iterating from back to front doesn't work either; you probably (depending on what you're doing) still have to segment into grapheme clusters—which is stateful as of unicode 9, so you have to start from the beginning of the string. And then god forbid you get U+202C POP DIRECTIONAL FORMATTING CODE....
- catlifeonmars 7y ago
  I found this little gem on Software engineering StackExchange: https://softwareengineering.stackexchange.com/questions/24691/what-do-you-use-string-reversal-for https://softwareengineering.stackexchange.com/questions/2469... Suffice it to say, there are many interesting uses for string reversal :)
  - bastawhiz 7y ago
    Interesting, but questionably useful. If you're converting integer bases or obfuscating email addresses, there are much better approaches that don't involve a bad hack
jodrellblank 7y ago
"lol :Man facepalming: :medium light skintone:" becomes the skintone applying to nothing (which might crash?) and the wrong coloured man. (e+accent a) making éa becomes (a+accent e) incorrectly making áe - or possibly invalidly making an error combination. Right-to-left markers[1] and left-to-right markers will change which sections of the text are reversed unless you swap them over. Codepoints can combine more than once, to the point where if you're too nitpicky you can't validly substring either, you can only read a string from the first codepoint onwards; they could become invalid sequences if reversed, possibly? [1] https://en.wikipedia.org/wiki/Right-to-left_mark https://en.wikipedia.org/wiki/Right-to-left_mark
- rlayton2 7y ago
  Agree. I think reversing in non-ascii should always be thought of as "per-token", where English is character-as-token. So the reverse of what you gave would be: ":medium light skintone: :Man facepalming: lol" (with the lol reversed). In this problem, it is a much harder problem than, say in python, mystring[::-1]. Therefore, it is a different problem "reverse a string" than to "reverse an array". Accented characters would be kept as is in my scenario.
  - PeCaN 7y ago
    The "tokens" you're thinking of are "grapheme clusters" in Unicode. Unfortunately just reversing by grapheme clusters doesn't solve the problem because of directional formatting codes; if you have e.g. a right-to-left embedding followed by a pop directional formatting you can't naively reverse them.
    - naniwaduni 7y ago
      Grapheme clusters are a poor approximation of the vaguely-defined linguistic-level concept you're groping for.
      - PeCaN 7y ago
        Well, yes, but we gotta stop somewhere or just give up any hope of computers operating on text. Although I think grapheme clusters are a pretty good approximation in that it's usually what you want to backspace in a word processor.
deleted 7y ago
[deleted]
tragomaskhalos 7y ago
There's actually two levels of jeopardy here: 1/ Treating a string as an array of bytes will give an invalid result if the string unless the string is simple ascii (or an equivalent encoding where each byte has a clearly defined standalone meaning); in particular, just reversing a UTF-8 string in this way will give an invalid answer - ie a string that isn't even valid UTF-8. 2/ The fix for (1) is to convert your string into an array of Unicode code points and reverse that … except that is also broken, because combining characters will now not associate correctly, as per other answers in this thread. Coding your way out of problem (2) in a robust and sensible way is, I suggest, a significant challenge.
- to11mtm 7y ago
  Of all things, VB.Net actually has a string reverse that handles unicode cases. I'm not quite sure how to view it in referencesource, but it is on Github. [1] The result is less than 100 lines of VB so I don't think it's -that- hard. There's certainly some clever index manipulation going on but nothing that looks too crazy. [1] - https://github.com/microsoft/referencesource/blob/master/Microsoft.VisualBasic/runtime/msvbalib/Strings.vb#L1043-L1134 https://github.com/microsoft/referencesource/blob/master/Mic...

PeCaN 7y ago

Unicode strings are really, really hard. I'm working on a programming language sort of like K or APL. Among other things it has "good" unicode support (I'm fully convinced such a thing is even possible). It introduces a truly frustrating amount of complexity, especially in comparison to how simple ASCII strings are in K or APL (just an array of characters, so you get all the powerful array operations for free as shown in this post). The approach I've more or less settled on is that strings are not arrays at all but it's possible to get arrays of codepoints (composed or decomposed) or grapheme clusters from them. Really this just pushes complexity to the caller, but it means you more control over what exactly you intend to work with. Pretty much all the solutions here could be straightforwardly translated to my programming language, except you would need to choose what definition of "character" you're going with. I basically like this solution but the deeper I get the more I become convinced that manipulating an arbitrary user-provided or even user-facing string in any way is a recipe for disaster; there's often simply no sensible way to handle things like direction formatting control codes (or bidirectional text in general). In other words, I almost think there should be separate types for "computer-facing" strings (like filenames) that one commonly has to manipulate, and "human-facing" strings that one just wants to either display or store somewhere and ideally never touch because you will screw up somewhere.

macintux 7y ago
> In other words, I almost think there should be separate types for "computer-facing" strings (like filenames) that one commonly has to manipulate, and "human-facing" strings that one just wants to either display or store somewhere and ideally never touch because you will screw up somewhere. That's a fascinating idea, thanks. I imagine it's impractical due to numerous places where machine and human strings overlap, but I'm going to have to ruminate on it for a while.
- etaioinshrdlu 7y ago
  It sounds a lot like what Go and perhaps Swift do. Perhaps other languages.
  - 7y ago

vl 7y ago

Especially it's ironical in the contexts of the interview, when the question is something like "write a function to reverse order of all words in the given string". So I'm thinking to myself: "You don't even comprehend how hard it's to actually do, or you know it and checking if I know it?". And then there is a need to ask a lot of probing questions just to learn the the string is ASCII and separator is space.

codeflo 7y ago

I wouldn’t call it dangerous, just meaningless. A lot of the discussion in this thread dives deeply into the technicalities of Unicode. All of that is correct, but a bit besides the point IMO. I think the real issue is that “reversing text” is fundamentally an operation that only makes sense in Western alphabets — the complexities of Unicode just reflect that. This is a bit hard to fathom for people who grew up with such an alphabet (this includes me), where there’s a rich tradition of games based on shuffling letters. It’s not just reversing; my understanding is that you can’t meaningfully define the concept of an anagram in many writing systems.