Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #45607 > unrolled thread

Challenge: tightest code to find-replace a string

Back to article view | Back to comp.lang.c

Contents

  Challenge: tightest code to find-replace a string DFS <nospam@dfs.com> - 2014-06-06 00:08 -0400
    Re: Challenge: tightest code to find-replace a string DFS <nospam@dfs.com> - 2014-06-06 04:34 -0400
      Re: Challenge: tightest code to find-replace a string Jorgen Grahn <grahn+nntp@snipabacken.se> - 2014-06-06 10:04 +0000
      Re: Challenge: tightest code to find-replace a string Mark Storkamp <mstorkamp@yahoo.com> - 2014-06-06 07:27 -0500
      Re: Challenge: tightest code to find-replace a string Robert Wessel <robertwessel2@yahoo.com> - 2014-06-06 11:55 -0500
        Re: Challenge: tightest code to find-replace a string Johannes Bauer <dfnsonfsduifb@gmx.de> - 2014-06-06 20:47 +0200
    Re: Challenge: tightest code to find-replace a string Ike Naar <ike@iceland.freeshell.org> - 2014-06-06 06:05 +0000
      Re: Challenge: tightest code to find-replace a string Noob <root@127.0.0.1> - 2014-06-06 10:17 +0200
        Re: Challenge: tightest code to find-replace a string Ian Collins <ian-news@hotmail.com> - 2014-06-08 21:20 +1200
    Re: Challenge: tightest code to find-replace a string Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-06-06 14:41 +0100
      Re: Challenge: tightest code to find-replace a string "BartC" <bc@freeuk.com> - 2014-06-06 16:29 +0100
        Re: Challenge: tightest code to find-replace a string Jorgen Grahn <grahn+nntp@snipabacken.se> - 2014-06-06 17:27 +0000
        Re: Challenge: tightest code to find-replace a string Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-06-06 22:16 +0100
          Re: Challenge: tightest code to find-replace a string "BartC" <bc@freeuk.com> - 2014-06-06 23:26 +0100
            Re: Challenge: tightest code to find-replace a string Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-06-06 23:38 +0100
      Re: Challenge: tightest code to find-replace a string Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-06-06 08:31 -0700
        Re: Challenge: tightest code to find-replace a string Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-06-06 22:12 +0100
      Re: Challenge: tightest code to find-replace a string Chad <cdalten@gmail.com> - 2014-06-07 12:19 -0700
        Re: Challenge: tightest code to find-replace a string Chad <cdalten@gmail.com> - 2014-06-07 13:38 -0700
          Re: Challenge: tightest code to find-replace a string raltbos@xs4all.nl (Richard Bos) - 2014-06-08 10:34 +0000
      Re: Challenge: tightest code to find-replace a string DFS <nospam@dfs.com> - 2014-06-07 18:30 -0400
        Re: Challenge: tightest code to find-replace a string Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-06-08 13:09 +0100
          Re: Challenge: tightest code to find-replace a string DFS <nospam@dfs.com> - 2014-06-08 12:42 -0400
            Re: Challenge: tightest code to find-replace a string Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-06-09 01:44 +0100
              Re: Challenge: tightest code to find-replace a string Siri Crews <chine.bleu@yahoo.com> - 2014-06-08 22:15 -0700
                Re: Challenge: tightest code to find-replace a string Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-06-09 12:58 +0100
              Re: Challenge: tightest code to find-replace a string Ike Naar <ike@iceland.freeshell.org> - 2014-06-09 06:40 +0000
                Re: Challenge: tightest code to find-replace a string Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-06-09 13:04 +0100
                  Re: Challenge: tightest code to find-replace a string "BartC" <bc@freeuk.com> - 2014-06-09 15:27 +0100
                    Re: Challenge: tightest code to find-replace a string Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-06-09 16:22 +0100
                      Re: Challenge: tightest code to find-replace a string "BartC" <bc@freeuk.com> - 2014-06-09 18:06 +0100
                      Re: Challenge: tightest code to find-replace a string "BartC" <bc@freeuk.com> - 2014-06-09 22:38 +0100
        Re: Challenge: tightest code to find-replace a string Tim Rentsch <txr@alumni.caltech.edu> - 2014-06-10 00:57 -0700
    Re: Challenge: tightest code to find-replace a string DFS <nospam@dfs.com> - 2014-06-07 17:36 -0400
      Re: Challenge: tightest code to find-replace a string "BartC" <bc@freeuk.com> - 2014-06-08 09:57 +0100
        Re: Challenge: tightest code to find-replace a string DFS <nospam@dfs.com> - 2014-06-08 12:43 -0400
          Re: Challenge: tightest code to find-replace a string Keith Thompson <kst-u@mib.org> - 2014-06-08 15:27 -0700
          Re: Challenge: tightest code to find-replace a string "BartC" <bc@freeuk.com> - 2014-06-09 10:02 +0100
            Re: Challenge: tightest code to find-replace a string Keith Thompson <kst-u@mib.org> - 2014-06-09 08:03 -0700
      Re: Challenge: tightest code to find-replace a string Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-06-08 04:43 -0700
        Re: Challenge: tightest code to find-replace a string DFS <nospam@dfs.com> - 2014-06-08 13:26 -0400
        Re: Challenge: tightest code to find-replace a string Keith Thompson <kst-u@mib.org> - 2014-06-08 15:24 -0700
          Re: Challenge: tightest code to find-replace a string Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-06-09 08:39 -0700
            Re: Challenge: tightest code to find-replace a string Keith Thompson <kst-u@mib.org> - 2014-06-09 08:57 -0700
              Re: Challenge: tightest code to find-replace a string Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-06-09 09:52 -0700
                Re: Challenge: tightest code to find-replace a string Keith Thompson <kst-u@mib.org> - 2014-06-09 11:25 -0700
                  Re: Challenge: tightest code to find-replace a string Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-06-09 13:42 -0700
                    Re: Challenge: tightest code to find-replace a string Keith Thompson <kst-u@mib.org> - 2014-06-09 15:02 -0700
                    Re: Challenge: tightest code to find-replace a string Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-06-09 16:04 -0700
                      Re: Challenge: tightest code to find-replace a string raltbos@xs4all.nl (Richard Bos) - 2014-06-10 10:23 +0000
            Re: Challenge: tightest code to find-replace a string raltbos@xs4all.nl (Richard Bos) - 2014-06-09 16:57 +0000
              Re: Challenge: tightest code to find-replace a string raltbos@xs4all.nl (Richard Bos) - 2014-06-10 10:06 +0000
    Re: Challenge: tightest code to find-replace a string "Chris M. Thomasson" <no@spam.invalid> - 2014-06-09 12:43 -0700
      Re: Challenge: tightest code to find-replace a string "Chris M. Thomasson" <no@spam.invalid> - 2014-06-09 14:32 -0700
        Re: Challenge: tightest code to find-replace a string "Chris M. Thomasson" <no@spam.invalid> - 2014-06-09 16:09 -0700
        Re: Challenge: tightest code to find-replace a string James Kuyper <jameskuyper@verizon.net> - 2014-06-09 21:35 -0400
      Re: Challenge: tightest code to find-replace a string DFS <nospam@dfs.com> - 2014-06-10 09:39 -0400
        Re: Challenge: tightest code to find-replace a string James Kuyper <jameskuyper@verizon.net> - 2014-06-10 11:26 -0400
        Re: Challenge: tightest code to find-replace a string raltbos@xs4all.nl (Richard Bos) - 2014-06-11 16:16 +0000
        Re: Challenge: tightest code to find-replace a string Keith Thompson <kst-u@mib.org> - 2014-06-11 09:25 -0700
          Re: Challenge: tightest code to find-replace a string Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-06-11 13:48 -0700
            Re: Challenge: tightest code to find-replace a string "BartC" <bc@freeuk.com> - 2014-06-11 22:04 +0100
              Re: Challenge: tightest code to find-replace a string Keith Thompson <kst-u@mib.org> - 2014-06-11 14:59 -0700
            Re: Challenge: tightest code to find-replace a string Ike Naar <ike@iceland.freeshell.org> - 2014-06-11 21:35 +0000
            Re: Challenge: tightest code to find-replace a string Keith Thompson <kst-u@mib.org> - 2014-06-11 14:56 -0700
              Re: Challenge: tightest code to find-replace a string Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-06-12 02:24 -0700
                Re: Challenge: tightest code to find-replace a string Keith Thompson <kst-u@mib.org> - 2014-06-12 09:09 -0700
                  Re: Challenge: tightest code to find-replace a string Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-06-13 00:40 -0700
                    Re: Challenge: tightest code to find-replace a string "BartC" <bc@freeuk.com> - 2014-06-13 09:17 +0100
    Re: Challenge: tightest code to find-replace a string "Chris M. Thomasson" <no@spam.invalid> - 2014-06-14 13:12 -0700

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

#45649

On 06/08/2014 07:43 AM, Malcolm McLean wrote:
> On Saturday, June 7, 2014 10:36:03 PM UTC+1, DFS wrote:
>> On 06/06/2014 02:30 PM, Stefan Ram wrote:
>>
>>> DFS <nospam@dfs.com> writes:
>>>> * reads an existing file
>>>> * writes changes to new file
>>>> * counts replacements made by line
>>>> * counts total replacements made
>>>> * no fancy usage of sed!
>>
>>>     I think this is not a sufficient specification of requirements.
>>
>> I think it's fine.
>>
> Depends.
> If you're providing a "search and replace" tool for use on human-readable text, it hardly
> matters how it handles the overlapping cases, because it will rarely be called for such,
> and any reasonable behaviour is likely to be accepted.


A voice of reason?

You may have trouble fitting in on clc.

[toc] | [prev] | [next] | [standalone]

#45652

Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
> On Saturday, June 7, 2014 10:36:03 PM UTC+1, DFS wrote:
>> On 06/06/2014 02:30 PM, Stefan Ram wrote:
>> 
>> > DFS <nospam@dfs.com> writes:
>> >> * reads an existing file
>> >> * writes changes to new file
>> >> * counts replacements made by line
>> >> * counts total replacements made
>> >> * no fancy usage of sed!
>>
>> >    I think this is not a sufficient specification of requirements.
>> 
>> I think it's fine.
>> 
> Depends.
> If you're providing a "search and replace" tool for use on
> human-readable text, it hardly matters how it handles the overlapping
> cases, because it will rarely be called for such, and any reasonable
> behaviour is likely to be accepted.

It matters very much if the handling of overlapping cases can trigger an
infinite loop.

And even for use on human-readable text, I fail to see how a precise and
unambiguous definition of the behavior is unimportant.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#45682

On Sunday, June 8, 2014 11:24:54 PM UTC+1, Keith Thompson wrote:
> Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
> 
> > Depends.
> 
> > If you're providing a "search and replace" tool for use on
> > human-readable text, it hardly matters how it handles the overlapping
> > cases, because it will rarely be called for such, and any reasonable
> > behaviour is likely to be accepted.
> 
> It matters very much if the handling of overlapping cases can trigger an
> infinite loop.
>
it mustn't crash or fail to return on any input. But it probably doesn't matter
if replace 'abcabc' 'x' called on abcabcabc returns xabc xx or even abcabcabc. 
>
> And even for use on human-readable text, I fail to see how a precise and
> unambiguous definition of the behavior is unimportant.
> 
The requirement for a function can be something like "makes the space invader
crash realistically". That's not reducible to a pure mathematical specification.

[toc] | [prev] | [next] | [standalone]

#45683

Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
> On Sunday, June 8, 2014 11:24:54 PM UTC+1, Keith Thompson wrote:
>> Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
>> > Depends.
>> 
>> > If you're providing a "search and replace" tool for use on
>> > human-readable text, it hardly matters how it handles the overlapping
>> > cases, because it will rarely be called for such, and any reasonable
>> > behaviour is likely to be accepted.
>> 
>> It matters very much if the handling of overlapping cases can trigger an
>> infinite loop.
>>
> it mustn't crash or fail to return on any input. But it probably
> doesn't matter if replace 'abcabc' 'x' called on abcabcabc returns
> xabc xx or even abcabcabc.

Nonsense.

>> And even for use on human-readable text, I fail to see how a precise and
>> unambiguous definition of the behavior is unimportant.
>> 
> The requirement for a function can be something like "makes the space
> invader crash realistically". That's not reducible to a pure
> mathematical specification.

Yes, the requirement for *some* functions can be that vague.

But a string replacement function *can* be specified precisely,
and there's no excuse for not doing so.  And if it doesn't behave
consistently, I'm not interested in using it; I'll just use a
different function that's properly defined.

Are you perhaps assuming that it doesn't matter because
search-and-replace is performed interactively, and therefore the
user can immediately see the results?  Are you familiar with sed?

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#45685

On Monday, June 9, 2014 4:57:23 PM UTC+1, Keith Thompson wrote:
>
> Are you perhaps assuming that it doesn't matter because 
> search-and-replace is performed interactively, and therefore the
> user can immediately see the results?  Are you familiar with sed?
> 
I'm familiar with the name but I've never used it.
If you're implementing see presumably you have to implement the quirks
as well, to avoid breaking existing scripts.
But if "search and replace" is called on overlapping input, then almost 
always it indicates that the caller didn't expect the pattern to be applied
to that situation. There's no ideal behaviour with a "pattern / replacement"
interface. Probably you should pass an extra parameter in to indicate whether 
to be greedy, non-greedy, or flag up an error. 
 

[toc] | [prev] | [next] | [standalone]

#45695

Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
> On Monday, June 9, 2014 4:57:23 PM UTC+1, Keith Thompson wrote:
>> Are you perhaps assuming that it doesn't matter because 
>> search-and-replace is performed interactively, and therefore the
>> user can immediately see the results?  Are you familiar with sed?
>> 
> I'm familiar with the name but I've never used it.

It's a non-interactive tool, common (in fact, nearly universal) on
UNIX-like systems.  The name is derived from the phrase "stream editor".
It's commonly used in scripts (i.e., programs written in the language
implemented by a shell).

> If you're implementing see presumably you have to implement the quirks
> as well, to avoid breaking existing scripts.
> But if "search and replace" is called on overlapping input, then
> almost always it indicates that the caller didn't expect the pattern
> to be applied to that situation. There's no ideal behaviour with a
> "pattern / replacement" interface. Probably you should pass an extra
> parameter in to indicate whether to be greedy, non-greedy, or flag up
> an error.

I've been using sed for decades.  As far as I know, it has no flag to
indicate different semantics for overlapping input, and I've never
encountered a need for such a flag.

The POSIX specification is here:
http://pubs.opengroup.org/onlinepubs/9699919799/utilities/sed.html

The relevant command in this context would be:

    sed 's/foo/bar/g'

In the documentation, a BRE is a "Basic Regular Expression"; in this
case, we're considering a simple string.  The 'g' suffix causes it to
replace all non-overlapping instances of "foo"; by default it only
replaces the first on each line.

An example:

    $ echo banana | sed 's/ana/Anana/g'
    bAnanana

As far as I can tell, no other output would be consistent with the
specification (there are two occurrences of "ana", but they overlap so
only the first is replaced) -- and I would consider any other output
unacceptable.

Though I can't think of a concrete example, it's likely I've used sed on
text with overlapping occurrences of a substitution pattern and relied
on the way it behaves.

The problem you perceive with overlapping input is not a problem
in practice.  There is no real ambiguity in the behavior, and
therefore no need for extra flags to resolve it.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#45709

On Monday, June 9, 2014 7:25:05 PM UTC+1, Keith Thompson wrote:
> Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
> 
> As far as I can tell, no other output would be consistent with the
> specification (there are two occurrences of "ana", but they overlap so
> only the first is replaced) -- and I would consider any other output
> unacceptable.
> 
It's slightly easier to write a greedy matcher. So probably that's what
they did, and wrote the specifications afterwards.
>
> The problem you perceive with overlapping input is not a problem
> in practice.  There is no real ambiguity in the behavior, and
> therefore no need for extra flags to resolve it.
> 
No it's not. If you call a pattern on an input with overlapping 
sequences, almost certainly you haven't thought through the output 
you actually want. The fix is usually to extend the pattern.  

[toc] | [prev] | [next] | [standalone]

#45719

Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
> On Monday, June 9, 2014 7:25:05 PM UTC+1, Keith Thompson wrote:
>> Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
>> As far as I can tell, no other output would be consistent with the
>> specification (there are two occurrences of "ana", but they overlap so
>> only the first is replaced) -- and I would consider any other output
>> unacceptable.
>> 
> It's slightly easier to write a greedy matcher. So probably that's what
> they did, and wrote the specifications afterwards.

Right, they couldn't possibly have thought about the design before they
implemented it.  (That was sarcasm.)

>> The problem you perceive with overlapping input is not a problem
>> in practice.  There is no real ambiguity in the behavior, and
>> therefore no need for extra flags to resolve it.
>> 
> No it's not. If you call a pattern on an input with overlapping 
> sequences, almost certainly you haven't thought through the output 
> you actually want. The fix is usually to extend the pattern.  

Perhaps you could try not making assumptions about what others have or
haven't thought through.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#45724

On Monday, June 9, 2014 10:02:23 PM UTC+1, Stefan Ram wrote:
> Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
> 
>   Dennis Ritchie, Donald E. Knuth, were or are they not all
>   masters of the English language, too?
> 
>       I've found that some of the best [Software ]developers
>       of all are English majors. They'll often graduate with
>       no programming experience at all, and certainly without
>       a clue about the difference between DRAM and EPROM.
> 
>       But they can write. That's the art of conveying
>       information concisely and clearly. Software development
>       and writing are both the art of knowing what you're going
>       to do, and then lucidly expressing your ideas.
>
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.

  

[toc] | [prev] | [next] | [standalone]

#45747

ram@zedat.fu-berlin.de (Stefan Ram) wrote:

> Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
> >humans can't easily communicate mathematical expressions. 
> 
>   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.)
> 
> http://en.wikipedia.org/wiki/Alex_(parrot)

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

Richard

[toc] | [prev] | [next] | [standalone]

#45687

Malcolm McLean <malcolm.mclean5@btinternet.com> wrote:

> On Sunday, June 8, 2014 11:24:54 PM UTC+1, Keith Thompson wrote:
> > Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
> > 
> > > If you're providing a "search and replace" tool for use on
> > > human-readable text, it hardly matters how it handles the overlapping
> > > cases, because it will rarely be called for such, and any reasonable
> > > behaviour is likely to be accepted.
> > 
> > It matters very much if the handling of overlapping cases can trigger an
> > infinite loop.
> >
> it mustn't crash or fail to return on any input. But it probably doesn't matter
> if replace 'abcabc' 'x' called on abcabcabc returns xabc xx or even abcabcabc. 

On the contrary. If my word processor gave me anything but "xabc" under
those circumstances, I'd start using another.

Richard

[toc] | [prev] | [next] | [standalone]

#45744

ram@zedat.fu-berlin.de (Stefan Ram) wrote:

> raltbos@xs4all.nl (Richard Bos) writes:
> >Malcolm McLean <malcolm.mclean5@btinternet.com> wrote:
> >>it mustn't crash or fail to return on any input. But it probably doesn't matter
> >>if replace 'abcabc' 'x' called on abcabcabc returns xabc xx or even abcabcabc. 
> >On the contrary. If my word processor gave me anything but "xabc" under
> >those circumstances, I'd start using another.
> 
>   You are responding to:
> 
> |... called on abcabcabc returns xabc or even abcabcabc.

No, what I'm responding to is still up there in the quoted post.

>   Malcolm wrote:
> 
> |... called on abcabcabc returns xabc xx or even abcabcabc.

Quite.

>   Malcolm failed to clearly indicate the boundaries of the string.
>   Still, taking » xx« to be a part of the string, is the only way
>   to parse the English sentence, as long as there is no comma after
>   the »xabc«.

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

[toc] | [prev] | [next] | [standalone]

#45700

> "DFS"  wrote in message news:lmrer6$4l3$1@dont-email.me... 
> * reads an existing file
> * writes changes to new file
> * counts replacements made by line
> * counts total replacements made
> * no fancy usage of sed!

Can I get the most recent requirements as a summary?

AFAICT, you want a one-to-many transformation.

A simple example:

s = "abcdefgabcdefghijklmnop"


A possible transformation could be:

"abcdefg" => "aaaAAaa"



So:

s_t = "aaaAAaaaaaAAaahijklmnop"


Right?



FWIW, this can be easily rendered into a case-sensitive function.

[toc] | [prev] | [next] | [standalone]

#45715

"Chris M. Thomasson"  wrote in message 
news:ln52p6$ri6$1@speranza.aioe.org...
> > "DFS"  wrote in message news:lmrer6$4l3$1@dont-email.me... [...]
> Can I get the most recent requirements as a summary?
> AFAICT, you want a one-to-many transformation.
> A simple example:
> s = "abcdefgabcdefghijklmnop"
> A possible transformation could be:
> "abcdefg" => "aaaAAaa"
> So:
> s_t = "aaaAAaaaaaAAaahijklmnop"
> Right?


WRT "infinitely" overlapping search string in the to be transformed string:

s = "01"

Transform:

"01" => "0101"

s[0] = "01"
s[1] = "0101"
s[2] = "01010101"
s[3] = "0101010101010101"
[...]


You would have to set an iteration threshold to help the
program avoid an infinite loop, and an ever expanding
buffer.


It expands like a L-system fractal. 

[toc] | [prev] | [next] | [standalone]

#45725

> From: Stefan Ram
> Sent: Monday, June 09, 2014 2:40 PM
> Newsgroups: comp.lang.c Subject:
> Re: Challenge: tightest code to find-replace a string

> > "Chris M. Thomasson" <no@spam.invalid> writes:
> > You would have to set an iteration threshold to help the
> > program avoid an infinite loop, and an ever expanding
> > buffer.

>   In C, one can write: »while(1);«.

>  Not having an iteration threshold in C means that the
>  language is simple and fast, albeit not without risks.

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
replacements:

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?

[toc] | [prev] | [next] | [standalone]

#45731

On 06/09/2014 05:32 PM, Chris M. Thomasson wrote:
> "Chris M. Thomasson"  wrote in message 
> news:ln52p6$ri6$1@speranza.aioe.org...
...
>> Can I get the most recent requirements as a summary?
>> AFAICT, you want a one-to-many transformation.
>> A simple example:
>> s = "abcdefgabcdefghijklmnop"
>> A possible transformation could be:
>> "abcdefg" => "aaaAAaa"
>> So:
>> s_t = "aaaAAaaaaaAAaahijklmnop"
>> Right?
> 
> 
> WRT "infinitely" overlapping search string in the to be transformed string:
> 
> s = "01"
> 
> Transform:
> 
> "01" => "0101"
> 
> s[0] = "01"
> s[1] = "0101"
> s[2] = "01010101"
> s[3] = "0101010101010101"
> [...]
> 
> 
> You would have to set an iteration threshold to help the
> program avoid an infinite loop, and an ever expanding
> buffer.
> 
> 
> It expands like a L-system fractal. 

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

[toc] | [prev] | [next] | [standalone]

#45752

On 6/9/2014 3:43 PM, Chris M. Thomasson wrote:
>> "DFS"  wrote in message news:lmrer6$4l3$1@dont-email.me...
>> * reads an existing file
>> * writes changes to new file
>> * counts replacements made by line
>> * counts total replacements made
>> * no fancy usage of sed!
>
> Can I get the most recent requirements as a summary?

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.




> AFAICT, you want a one-to-many transformation.
>
> A simple example:
>
> s = "abcdefgabcdefghijklmnop"
>
> A possible transformation could be:
>
> "abcdefg" => "aaaAAaa"
>
> So:
>
> s_t = "aaaAAaaaaaAAaahijklmnop"
>
> Right?


Yep!




> FWIW, this can be easily rendered into a case-sensitive function.

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.

[toc] | [prev] | [next] | [standalone]

#45758

On 06/10/2014 09:39 AM, DFS wrote:
> On 6/9/2014 3:43 PM, Chris M. Thomasson wrote:
>>> "DFS"  wrote in message news:lmrer6$4l3$1@dont-email.me...
>>> * reads an existing file
>>> * writes changes to new file
>>> * counts replacements made by line
>>> * counts total replacements made
>>> * no fancy usage of sed!
>>
>> Can I get the most recent requirements as a summary?
> 
> 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.

"Common sense" is just a fiction invented for the sake of justifying the
assumption that everyone else will think the same way you do.

[toc] | [prev] | [next] | [standalone]

#45794

DFS <nospam@dfs.com> wrote:

> On 6/9/2014 3:43 PM, Chris M. Thomasson wrote:
> >> "DFS"  wrote in message news:lmrer6$4l3$1@dont-email.me...
> >> * reads an existing file
> >> * writes changes to new file
> >> * counts replacements made by line
> >> * counts total replacements made
> >> * no fancy usage of sed!
> >
> > Can I get the most recent requirements as a summary?
> 
> 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.

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

Richard

[toc] | [prev] | [next] | [standalone]

#45797

DFS <nospam@dfs.com> writes:
> On 6/9/2014 3:43 PM, Chris M. Thomasson wrote:
>>> "DFS"  wrote in message news:lmrer6$4l3$1@dont-email.me...
>>> * reads an existing file
>>> * writes changes to new file
>>> * counts replacements made by line
>>> * counts total replacements made
>>> * no fancy usage of sed!
>>
>> Can I get the most recent requirements as a summary?
>
> 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.
[...]

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 (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

Back to top | Article view | comp.lang.c

csiph-web