Challenge: tightest code to find-replace a string

Discussion in 'C Programming' started by DFS, Jun 6, 2014.

  1. Right, they couldn't possibly have thought about the design before they
    implemented it. (That was sarcasm.)
    Perhaps you could try not making assumptions about what others have or
    haven't thought through.
    Keith Thompson, Jun 9, 2014
    1. Advertisements

  2. I am what Americans would call an English major. My first degree
    was English Language and Literature at Oxford.
    But I don't apply a mathematical mindset to natural language.
    Computers can't talk. There's currently a claim that a program
    has passed the Turing test (successfully deceive judges into
    thinking it is human), but it's bound to be flawed. Similarly
    humans can't easily communicate mathematical expressions. But
    that doesn't make a natural language specification meaningless.
    Malcolm McLean, Jun 10, 2014
    1. Advertisements

  3. From: Stefan Ram
    I was thinking more along the lines of:
    unsigned i;

    for (i = 0; i < n; i += 1)


    So, wrt "01" and a transformation of "01" =>
    "0101", then this would be 2^n number of

    01 = seed
    0101 = 2^0 transformations
    01010101 = 2^1 transformations
    0101010101010101 = 2^2 transformations
    .... = 2^n transformations


    Think of iterating an L-system. You generally
    want to stop at some point?
    Chris M. Thomasson, Jun 10, 2014
  4. DFS

    Stefan Ram Guest

    The other animals are even worse at it! (Except maybe Alex,
    who invented the number 0 by himself, while human culture
    needed a long time for this.)
    Stefan Ram, Jun 10, 2014
  5. DFS

    Stefan Ram Guest

    The client should have a way to terminate a loop,
    but should be free to choose not to terminate it,
    too. Just as in C.
    Stefan Ram, Jun 10, 2014
  6. DFS

    James Kuyper Guest

    In general, I don't like arbitrary limits like that . I think that for
    the kind of utility program being discussed here, the most appropriate
    way to deal with that issue is to define the transformations that it's
    capable of implementing in such a way that the loop cannot be infinite.

    I think that the simplest way to arrange this is to exclude the
    replacement text from previous find-replace operations from all
    following "find" steps.

    Alternatively, one relatively minimal way to it is to require than each
    found pattern must include at least one character that was not the
    result of a previous replace. That would ensure that your loop would
    never have more iterations than the number of characters in the input.
    James Kuyper, Jun 10, 2014
  7. DFS

    Tim Rentsch Guest

    copy_file_replacing( FILE *in, FILE *out, char *this, char *that, int end ){
    char *t = this;
    int matches = 0;
    int c;

    while( c = fgetc( in ), c != end && c != EOF ){
    if( t > this && *t != c ){
    char *p = this, *u = t;
    do {
    fputc( *p, out ), p++, t--;
    } while( p < u && (*t != c || strncmp( this, p, u-p )) );

    if( c == *t ){
    if( * ++t == 0 ) fputs( that, out ), matches++, t = this;
    } else {
    fputc( c, out );

    if( c != EOF && c == 0[t] && 1[t] == 0 ){
    fputs( that, out );
    return matches + 1;

    fprintf( out, "%.*s", (int){t-this}, this );
    if( c != EOF ) fputc( c, out );
    return matches;
    Tim Rentsch, Jun 10, 2014
  8. DFS

    Richard Bos Guest

    No, what I'm responding to is still up there in the quoted post.
    I presumed that Malcolm was merely being sloppy, and had omitted a comma
    he intended to be there. I often disagree with him, but I don't think
    he's daft enough to believe that "replace 'abcabc' 'x'" on "abcabcabc"
    could result in "xabc xx". Even by his standards, that would be an
    unacceptably excentric bug.

    Richard Bos, Jun 10, 2014
  9. DFS

    Richard Bos Guest

    Well. So Pepperberg claims. Her claims are highly suspect, though.

    Richard Bos, Jun 10, 2014
  10. DFS

    DFS Guest

    No changes on my side, though others have jumped on them as insufficient.

    I would like for common sense to be a requirement of the developer.

    That would be nice. Most find-replace apps have the 'match case' option.

    I'll try and add it to my own code as well.
    DFS, Jun 10, 2014
  11. DFS

    James Kuyper Guest

    "Common sense" is just a fiction invented for the sake of justifying the
    assumption that everyone else will think the same way you do.
    James Kuyper, Jun 10, 2014
  12. DFS

    Richard Bos Guest

    I'm all for it, but common sense in the client would be even more

    Richard Bos, Jun 11, 2014
  13. [...]

    My common sense as a developer tells me that I need an unambiguous
    specification. If I can't get one, I'll probably write one myself
    and verify that it's consistent with what's actually needed.
    Keith Thompson, Jun 11, 2014
  14. If someone instructed you to go through a text, and replace every
    instance of "her" with "him", how would you respond?
    Malcolm McLean, Jun 11, 2014
  15. DFS

    Stefan Ram Guest

    Well, the obvious call backs would be: »also in "inheritance"?«,
    »also "Her"? (by "Him" or by "him"?)«, »also, when the glyph "h"
    is encoded using Unicode code point 1211 (decimal)«?
    Stefan Ram, Jun 11, 2014
  16. DFS

    BartC Guest

    I would probably change "I told her so" to "I told him so".

    I wouldn't change "There are several herds" to "Thime are several himds".

    I would have to think a little about changing "Here was her coat" to "Here
    was him coat" (but would not be tempted to write "Hime was him coat".

    (I would probably also change whole words of "her", "Her" and "HER" to
    "him", "Him" and "HIM" respectively.)

    So yes, when presenting a challenge, you do have to spell these things out.
    (And also why when I re-stated this problem, I talked about byte-sequences
    rather than text.)
    BartC, Jun 11, 2014
  17. DFS

    Ike Naar Guest

    "Whime you crazy?"
    Ike Naar, Jun 11, 2014
  18. I'd ask whethim thime are any bothimsome or othimwise incohiment special
    cases to consider.

    Possibly the context of the request would clarify whether
    occurrences of "her" within a word (and what exactly is a
    "word"?) should or shouldn't be replaced, and whether "Her" and
    "HER" should be replaced by "Him" and "HIM", respectively. If the
    intent is to replace feminine pronouns by masculine, I'd have to do
    more analysis to determine whether "her" is possesive (and should
    be replaced by "his") or not (and should be replaced by "him").
    Given the complexity of English grammar, I woudln't be surprised
    if there are cases that are inherently ambiguous.

    Your point?
    Keith Thompson, Jun 11, 2014
  19. And if the actual intent is to implement C code that performs the
    equivalent of

    sed 's/him/her/g'

    then most of these assumptions would be wrong. This is why we need
    context. Even with perfectly precise requirements, knowing the actual
    goal can help both in understanding the requirements and in judging
    whether they're written correctly.
    Keith Thompson, Jun 11, 2014
  20. You can't do that and keep a secretarial job. Well actually you maybe can,
    it's such an unusual response that a secretary who said that would probably
    be treated as a company treasure. But usually, a businessman expects a
    reasonable instruction like that to be executed.
    You need to read the text. It's entirely possible that a blind search/replace
    of the sequence "her" by "him" will produce an output everyone would
    agree is the one desired. It's quite likely that a word replacement will
    be right.
    But it's also likely that no simple program can do the job, but any human
    can, for example, "himself" and "herself", or "her" and "his". It's also
    likely that there are other gendered words, there comes a point where
    you've got to query if, say, "Freda" should be replaced by "Fred". That's
    pretty clearly going beyond the instruction. It's hard to say where that
    point is.

    User requirements are often inherently ambiguous in computer terms.
    There is no algorithm that can fulfil the businessman's request.
    Malcolm McLean, Jun 12, 2014
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.