Challenge: tightest code to find-replace a string

[Keith Thompson]

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.

If I were given such an instruction in the context of a secretarial
job, that would provide a great deal of information. You gave no
such context. I answered as a software developer, which you already
know is what I am.

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.

Ok, so we seem to be in agreement, now that you've provided some
more context.

But if we're talking about doing search-and-replace within a string
*as a programming problem*, the requirements can and should be
defined unambiguously. If I'm writing an implementation of sed,
for example, I'll be working from a specification that leaves no
doubt what should happen if there's an overlap.

 

[Malcolm McLean]

But if we're talking about doing search-and-replace within a string
*as a programming problem*, the requirements can and should be
defined unambiguously. If I'm writing an implementation of sed,
for example, I'll be working from a specification that leaves no
doubt what should happen if there's an overlap.

Often there's someone who stands between the client and the programmer,
turning business requirements into some sort of formal specification.
You can argue about the wisdom of that paradigm of software development.
But often there isn't.

If you're writing an implementation of sed, you have to be compatible.
Not so for the first sed author.

 

[BartC]

If you're writing an implementation of sed, you have to be compatible.
Not so for the first sed author.

In the case of this thread, the OP is the first author of the challenge, and
everyone else needs to write compatible implementations.

 

[Chris M. Thomasson]

"DFS" wrote in message
FWIW, check out this thread:

https://groups.google.com/forum/#!topic/comp.lang.c/cUeUlQd38-o/overview


Here was my submission:

https://groups.google.com/forum/#!original/comp.lang.c/cUeUlQd38-o/VlU8pTgRk8EJ

http://pastebin.com/f62c80892

This transforms tab characters into spaces.

____________________________________________________
#include <stdio.h>
#include <stdlib.h>
#include <string.h>




#define TAB_MAX 1024U
#define TAB_DEFAULT 1U




typedef char static_assert[
TAB_MAX > 0 && TAB_DEFAULT > 0 ? 1 : -1
];




struct detab {
FILE* in_file;
FILE* out_file;
unsigned long int tabs[TAB_MAX + 1];
};




int
detab_startup(
struct detab* const self,
int argc,
char** argv
) {
if (argc > 1) {
size_t i, size = 0;
char* stop = NULL;
char* cur = argc == 2 ? argv[1] : argv[2];
while (*cur && size < TAB_MAX) {
self->tabs[size] = strtoul(cur, &stop, 10);
if (! self->tabs[size]) self->tabs[size] = TAB_DEFAULT;
++size;
if (! *stop) break;
cur = stop + 1;
}
for (i = size; i < TAB_MAX + 1; ++i) {
self->tabs = TAB_DEFAULT;
}
if (argc > 2) {
self->in_file = fopen(argv[1], "rt");
if (! self->in_file) {
fprintf(stderr, "could not open the [in] file!\n");
return 0;
}
} else {
self->in_file = stdin;
}
self->out_file = stdout;
return 1;
} else {
fprintf(stderr, "invalid argument(s)!\n");
}
return 0;
}


int
detab_shutdown(
struct detab* const self
) {
if (self->in_file != stdin && fclose(self->in_file)) {
fprintf(stderr, "there was an error closing the [in] file!\n");
return 0;
}
return 1;
}


int
detab(
struct detab* const self
) {
int c;
unsigned long int i = 1;
unsigned long int col = 0;
unsigned long int tab = 0;

while((c = getc(self->in_file)) != EOF) {
switch (c) {
case '\t':
do {
if (putc(' ', self->out_file) == EOF) {
goto bail_out;
}
++i;
} while (tab < TAB_MAX && ++col % self->tabs[tab]);
if (tab < TAB_MAX) ++tab;
break;
case '\n':
i = 0;
col = -1;
tab = 0;
default:
++i;
if (tab < TAB_MAX && ! (i % self->tabs[tab])) {
++tab;
}
col = (col + 1) % self->tabs[tab];
if (putc(c, self->out_file) == EOF) {
goto bail_out;
}
}
}
bail_out:;
if (ferror(self->in_file)) {
fprintf(stderr, "there was an error reading from the [in] file!\n");
return 0;
}
if (ferror(self->out_file)) {
fprintf(stderr, "there was an error writing to the [out] file!\n");
return 0;
}
return 1;
}




int main(
int argc,
char** argv
) {
int status = EXIT_FAILURE;
struct detab self = { NULL };
if (detab_startup(&self, argc, argv)) {
status = EXIT_SUCCESS;
if (! detab(&self)) {
status = EXIT_FAILURE;
}
if (! detab_shutdown(&self)) {
status = EXIT_FAILURE;
}
}
return status;
}
____________________________________________________


;^)

 

[Stefan Ram]

@param get a getchar-like function representing the
input to read from.

You might have guessed this, but it should be added here
that this function returns -1 to indicate end-of-input.

 

[Stefan Ram]

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.

See also »string rewriting«, for example:

http://mathworld.wolfram.com/StringRewritingSystem.html