reverse-the-words C program contest
James Irl Waldby
the letters of words of its input, leaving other characters alone:
#!/usr/bin/perl
for (<>) {
for $i (split /(\W)/) {
print join('', reverse(split //, $i)), $1;
}
}
For example, if file p2 says: "\W Match a non-word character"
then rev < p2 produces: "\W hctaM a non-drow retcarahc".
Of course, rev could also be written with less whitespace as:
#!/usr/bin/perl
for(<>){for$i(split/(\W)/){print join('',reverse(split//,$i)),$1;}}
or could be used on the command line as:
perl -ne "for$i(split/(\W)/){print join('',reverse(split//,$i)),$1;}" < p2
Now for the contest!
(1) Write a short C program to act the same way, ie, if a.out is the
name of the executable, then a.out is a filter that reverses "letters" *
of words in its stdin output while copying non-letters and writes the
results to stdout.
(2) You can assume some reasonable limit such as 65536 characters on
lengths of input lines, but no limit on number of lines.
(3) I offer a $4.40 prize (check, US$) to author of shortest working
program that compiles ok with gcc 2.7.0 and is posted here before 5
pm CDT on 13 Sept 95. Posted programs remain intellectual property
of posters, as far as I'm concerned; the prize money is just to
double (?) the fun.
* "letters" = [a-zA-Z0-9_], as in following example ...
JW> ls -l j* r*
lrwxrwxrwx 1 j-waldby users 19 Apr 30 10:23 jd.h -> /usr/8c/pc/jd.h
-rw-r--r-- 1 j-waldby users 1000 Apr 30 10:29 run_time.o
JW> ls -l j* r*|perl -ne "for$i(split/(\W)/){print join('',reverse(split//,$i)),$1;}"
xwrxwrxwrl 1 j-ybdlaw sresu 91 rpA 03 01:32 dj.h -> /rsu/c8/cp/dj.h
-wr-r--r-- 1 j-ybdlaw sresu 0001 rpA 03 01:92 emit_nur.o
-- James Waldby j-wa...@uiuc.edu
Matt Cross
James Irl Waldby <j-wa...@glhpx11.cen.uiuc.edu> wrote:
>mcr...@bonehead.sw.stratus.com (Matt Cross) writes:
>
>>Anyways, this is a good start:
>
>>#include <stdio.h>
>>#define x _=getchar();if(isalnum(_)||_=='_')main(-1)
>>main(_){if(_>=0){a:x;if(_!=-1){putchar(_);goto a;}}
>>else{x,putchar(_);else ungetc(_,stdin);}}
>
> Neat program! and it works ok on several test sets I tried.
Thanks! It gets better, though:
r(l,c,d){a:c=getchar();if(isalnum(c)||c=='_'){d=r(1);putchar(c);if(l)return
d;else c=d;}if(l)return c;if(c!=-1){putchar(c);goto a;}}main(){r(0);}
Got it down to 146 characters. (145 if you don't count the newline at
the end of the file, the newline in the middle is necessary, and if it
wasn't there a space would be needed).
The only assumption I added is that if you call a function with less
arguments than it takes, it will fill in the first argument correctly.
Not sure if this is in the standard or not.
-Matt
Matt Cross
>
> (2) You can assume some reasonable limit such as 65536 characters on
>lengths of input lines, but no limit on number of lines.
Do we get extra points for not assuming this?
> (3) I offer a $4.40 prize (check, US$) to author of shortest working
>program that compiles ok with gcc 2.7.0 and is posted here before 5
>pm CDT on 13 Sept 95. Posted programs remain intellectual property
>of posters, as far as I'm concerned; the prize money is just to
>double (?) the fun.
How do you measure shortest?
Anyways, this is a good start:
#include <stdio.h>
#define x _=getchar();if(isalnum(_)||_=='_')main(-1)
main(_){if(_>=0){a:x;if(_!=-1){putchar(_);goto a;}}
else{x,putchar(_);else ungetc(_,stdin);}}
166 characters according to 'wc -c'. I had to include stdio.h to get
the definition for stdin for the ungetc call, which I couldn't think
of a way to work around. As long as you don't overflow your stack, an
input line or word size will work.
-Matt
James Irl Waldby
>In article <42ifbm$2...@vixen.cso.uiuc.edu>,
>James Irl Waldby <j-wa...@glhpx11.cen.uiuc.edu> wrote:
>>Now for the contest!
>>
>> (2) You can assume some reasonable limit such as 65536 characters on
>>lengths of input lines, but no limit on number of lines.
>Do we get extra points for not assuming this?
No; of course it is much better for the program to not
have arbitrary limits, but scoring rules could get
complicated. Also, instead of "lines" I should have said
"words" since that is the limiting factor in some approaches.
...
>How do you measure shortest?
wc -c like you used (that is, total characters) but if there's
an author-title comment line would use
tail +2 programname | wc -c
to only count characters after the comment line.
Oh, re shortness - the perl program doesn't need the 'join',
it was left over by mistake from an earlier version ... so:
perl -ne "for$i(split/(\W)/){print reverse(split//,$i),$1;}"
>Anyways, this is a good start:
>#include <stdio.h>
>#define x _=getchar();if(isalnum(_)||_=='_')main(-1)
>main(_){if(_>=0){a:x;if(_!=-1){putchar(_);goto a;}}
>else{x,putchar(_);else ungetc(_,stdin);}}
Neat program! and it works ok on several test sets I tried.
>166 characters according to 'wc -c'. I had to include stdio.h to get
>the definition for stdin for the ungetc call, which I couldn't think
>of a way to work around. As long as you don't overflow your stack, an
>input line or word size will work.
> -Matt
It ran ok here on a 'word' of 150000 characters.
p-rev = perl program, c-rev = yours; and t is not
a palindrome :-) , as follows:
jw> time p-rev < t > y
7.64user 1.79system 0:10.39elapsed 90%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+0minor)pagefaults 0swaps
jw> time c-rev < t > x
0.47user 0.20system 0:00.81elapsed 82%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+0minor)pagefaults 0swaps
jw> diff x y
jw> diff t x | wc
6 20 100070
jw> wc t
0 1 150000 t
and another example, with English language text :
jw> time p-rev < ~/po/ps > y
42.14user 0.44system 0:42.74elapsed 99%CPU ...
jw> time c-rev < ~/po/ps > x
0.72user 0.29system 0:01.01elapsed 100%CPU ...
jw> diff x y
jw> wc x y
12121 76492 401076 x
12121 76492 401076 y
24242 152984 802152 total
Labeeb Ismail
Matt Cross <mcr...@bonehead.sw.stratus.com> wrote:
>In article <42ifbm$2...@vixen.cso.uiuc.edu>,
>James Irl Waldby <j-wa...@glhpx11.cen.uiuc.edu> wrote:
>>Now for the contest!
>>
>> (2) You can assume some reasonable limit such as 65536 characters on
>>lengths of input lines, but no limit on number of lines.
>
>Do we get extra points for not assuming this?
>
>>program that compiles ok with gcc 2.7.0 and is posted here before 5
>>pm CDT on 13 Sept 95. Posted programs remain intellectual property
>>of posters, as far as I'm concerned; the prize money is just to
>>double (?) the fun.
>
Here is my entry contains 144 chars
s[65536];h;c;main(){while((c=getch())!=4)if((c>47)&&(c<58)||
((c&~32)>64)&&((c&~32)<91)||(c==95))s[h++]=c;else{for(;h;
putch(s[--h]));putch(c);}}
################################################################################
# Labeeb K I #
# Senior Software Engineer Ph: (Res) 503-640-1014 #
# Wipro Infotech Ltd. (Off) 503-696-3276 #
# 1221, NE 51st AVE, #203, #
# HILLSBORO, ORE- 97124 #
# U S A. #
# #
# Feeling Disillusioned, I have some great new Illusions #
################################################################################
Labeeb Ismail
Labeeb Ismail <lab...@ornews.intel.com> wrote:
>In article <42k656$o...@transfer.stratus.com>,
>Matt Cross <mcr...@bonehead.sw.stratus.com> wrote:
>>In article <42ifbm$2...@vixen.cso.uiuc.edu>,
>>James Irl Waldby <j-wa...@glhpx11.cen.uiuc.edu> wrote:
>>>Now for the contest!
>>>
>>> (2) You can assume some reasonable limit such as 65536 characters on
>>>lengths of input lines, but no limit on number of lines.
>>
>>Do we get extra points for not assuming this?
>>
>>> (3) I offer a $4.40 prize (check, US$) to author of shortest working
>>>program that compiles ok with gcc 2.7.0 and is posted here before 5
>>>pm CDT on 13 Sept 95. Posted programs remain intellectual property
>>>of posters, as far as I'm concerned; the prize money is just to
>>>double (?) the fun.
>>
>
>Here is my entry contains 144 chars
>
>s[65536];h;c;main(){while((c=getch())!=4)if((c>47)&&(c<58)||
>((c&~32)>64)&&((c&~32)<91)||(c==95))s[h++]=c;else{for(;h;
>putch(s[--h]));putch(c);}}
OOps! the above one works only with my watcom compiler.
Now try this one. Works on my unix machine.140 chars
#include <stdio.h>
s[65536];h;c;main(){while((c=getchar())!=EOF)if(isalnum(c)||
(c==95))s[h++]=c;else{for(;h;putchar(s[--h]));putchar(c);}}
Paul Gentieu
Here's my solution:
O[99999],*l=O;main(_){for(;_=getchar()+1;)if(!isalnum(
*++l=--_)&&_^'_'){for(;*--l;putchar(*l));putchar(_);}}
108 characters. The maximum line length is 99999, but
this can easily be extended by increasing the size of
O[]. The program assumes EOF == -1, but other than that
it should be portable.
This was a fun problem. Some of my earlier solutions
were truly grotesque...
-Paul
Zefram
Hmm...
main(){execlp("perl","","-ne","for$i(split/(\\W)/){print reverse(split//,$i),$1;}",0);}
88 characters, including the newline.
(Yes, I know it's a cop-out.)
-zefram
Labeeb Ismail
l;p(c){putchar(c);}main(a){int c;while((c=getchar())+1)if(isalnum(c)|(c==95)){main(0);p(c);if(!a)break;p(l);}else{if(!a){l=c;break;}p(c);}}
W. Scott Cranston
>
> Thanks! It gets better, though:
>
> r(l,c,d){a:c=getchar();if(isalnum(c)||c=='_'){d=r(1);putchar(c);if(l)return
> d;else c=d;}if(l)return c;if(c!=-1){putchar(c);goto a;}}main(){r(0);}
>
> Got it down to 146 characters. (145 if you don't count the newline at
> the end of the file, the newline in the middle is necessary, and if it
> wasn't there a space would be needed).
>
> The only assumption I added is that if you call a function with less
> arguments than it takes, it will fill in the first argument correctly.
> Not sure if this is in the standard or not.
>
> -Matt
1) You can replace the logical or "||" with the bitwise or "|" and get
the same results with one fewer character.
2) Since you already using -1 for EOF, which is not totally portable,
you might as well say "<0" and save 2 characters.
--
-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 2.3
mQCNAi17g20AAAEEANt1ejh9nWvnRPhb9LYXyQsD/VKZuJb+A1wV7Ph+Dc/QztlU
GyVWtBCx7QiuWy4jch32z+yzkpgvm7W1aWBSUmUh2sVDI2KizqwStZSbppHP/vz1
XN+5bkdsXVOxqpnnUnMhmgerNyTdsY6fnNlKm8d9HorgLdeQzQqlAZcPtC+9AAUR
tClXbS4gU2NvdHQgQ3JhbnN0b24gPGNyYW5zdG9uQGNhZGVuY2UuY29tPg==
=w8Le
-----END PGP PUBLIC KEY BLOCK-----
James Bonfield
> (1) Write a short C program to act the same way, ie, if a.out is the
>name of the executable, then a.out is a filter that reverses "letters" *
>of words in its stdin output while copying non-letters and writes the
>results to stdout.
I've got 93 characters so far. It's not particularly ANSI conforming, but it
does compile correctly with all the compilers I've tried, including gcc 2.7.0
as requested.
y;x(c){isalnum(c=getchar())||c =='_'?x()|putchar(c):(y=c);}main(c){for(;x(),y+1;putchar(y));}
I'm trying to work out a method of doing it entirely within a recursive
main(), but I can't see how yet.
James
Matt Cross
>
>I've got 93 characters so far. It's not particularly ANSI conforming, but it
>does compile correctly with all the compilers I've tried, including gcc 2.7.0
>as requested.
>
>y;x(c){isalnum(c=getchar())||c =='_'?x()|putchar(c):(y=c);}main(c)
>{for(;x(),y+1;putchar(y));}
>
>I'm trying to work out a method of doing it entirely within a recursive
>main(), but I can't see how yet.
I've got mine all in a recursive main() (I assume the second arg to
main (argv) will not be zero on the initial call, and use that as a
flag to control what it does), but I've only got it down to 128
characters:
main(l,c,d){l=!c;a:c=getchar();if(isalnum(c)||c==95){d=main(1,0,0);
putchar(c);c=d;}if(l)return c;if(c!=-1){putchar(c);goto a;}}
(Note: to get 128 characters, you have to combine this onto one line;
I left it as two in this post to keep newsreaders happy)
Taking your idea of using a global variable instead of return, and
your for loop structure (and a couple other minor things), I can get
mine down to 100 characters:
d;main(l,c){for(l=c;isalnum(c=getchar())||c==95?main(1,0),putchar(c),c=d:
(d=c),l&&c+1;putchar(c));}
-Matt
BTW, I tried yours out, and it works if I compile with gcc, but if I
compile with the cc on my Sparcstation, it just prints things out in
the normal order...
James Irl Waldby
>In article <42l36d$l...@ornews.intel.com>,
>Labeeb Ismail <lab...@ornews.intel.com> wrote:
>>In article <42k656$o...@transfer.stratus.com>,
>>Matt Cross <mcr...@bonehead.sw.stratus.com> wrote:
>>>In article <42ifbm$2...@vixen.cso.uiuc.edu>,
>>>James Irl Waldby <j-wa...@glhpx11.cen.uiuc.edu> wrote:
>>>>Now for the contest!
Part (1) was:
(1) Write a short C program to act the same way, ie, if a.out is the
name of the executable, then a.out is a filter that reverses "letters" *
of words in its stdin output while copying non-letters and writes the
results to stdout.
["The same way" refers to the filter,
perl -ne "for$i(split/(\W)/){print reverse(split//,$i),$1;}"
Also, "lines" in (2) should be "words" if it makes a difference.
Also, "letters" is [a-zA-Z0-9_], that is, alpha, _, and numeric.
-- jiw ]
>>>> (2) You can assume some reasonable limit such as 65536 characters on
>>>>lengths of input lines, but no limit on number of lines.
>>>
>>>Do we get extra points for not assuming this?
[ The answer to this was no, too hard to score. -- jiw ]
>>>
>>>> (3) I offer a $4.40 prize (check, US$) to author of shortest working
>>>>program that compiles ok with gcc 2.7.0 and is posted here before 5
>>>>pm CDT on 13 Sept 95. Posted programs remain intellectual property
>>>>of posters, as far as I'm concerned; the prize money is just to
>>>>double (?) the fun.
>>>
>>Here is my entry contains 144 chars
>>s[65536];h;c;main(){while((c=getch())!=4)if((c>47)&&(c<58)||
>>((c&~32)>64)&&((c&~32)<91)||(c==95))s[h++]=c;else{for(;h;
>>putch(s[--h]));putch(c);}}
>Hmm. This didn't compile for me, but here is a derivative
>that gets it down to 114 characters.
>s[65536];h;main(c){while((c=getchar())>=0)
>if(isalnum(c)||c==95)s[h++]=c;else{for(;h;putchar(s[--h]));putchar(c);}}
>I note that this solution assumes that the last character of the file is
>a newline (or other non reversing character) or else the last word isn't
>printed. Is this OK by the rules of the contest?
Two or three of my test files are all-alpha_numeric, produced eg by:
man yes |perl -ne "s/\W//g; print" > testF
man ls | perl -ne "s/\W//g; print" > testG
I have run entries from bonfield, cross, gentieu, labeeb, labeeb,
and zefram thru test suite and saw symptoms of this problem with
most entries but unfortunately have been looking for c library bugs
instead of figuring it out like you did. :) --jiw
>Also it is system dependent on '_' and EOF values.
True -- maybe this enhances programmer but not program portability :)
--jiw (James Waldby j-wa...@uiuc.edu)
>John Ellson >AT&T Bell Labs >-- >John....@att.com
James Bonfield
> Two or three of my test files are all-alpha_numeric, produced eg by:
> man yes |perl -ne "s/\W//g; print" > testF
> man ls | perl -ne "s/\W//g; print" > testG
>
> I have run entries from bonfield, cross, gentieu, labeeb, labeeb,
> and zefram thru test suite and saw symptoms of this problem with
> most entries but unfortunately have been looking for c library bugs
> instead of figuring it out like you did. :) --jiw
Actually, my shortest one I posted earlier didn't work full stop it seems.
Anyway, my earlier one did, and I've now shrunk it again to 90 characters. It
passes the tests you've listed above fine.
y;x(c){isalnum(c=getchar())|c==95?x(),putchar(c):(y=c);}
main(c){for(;x(),y+1;putchar(y));}
James
--
James Bonfield (j...@mrc-lmb.cam.ac.uk) Tel: 01223 402499 Fax: 01223 412282
Medical Research Council - Laboratory of Molecular Biology,
Hills Road, Cambridge, CB2 2QH, England.
James Bonfield
>y;x(c){isalnum(c=getchar())|c==95?x(),putchar(c):(y=c);}
>main(c){for(;x(),y+1;putchar(y));}
Same length again (90), but recursing entirely in main. This is even more
obscure than the other one!
y,z;main(c){isalnum(c=getchar())|c==95?main(++z),putchar(c),z--||putchar(y),main():(y=c);}
Seems like 90 characters is dogging me a bit at the moment. Someone else is on
90 too I believe :-)
Can anyone see any simple optimisations to shrink either of these two (or the
other 90 character solution) to get an 89er?
Justin Legakis
>Anyway, my earlier one did, and I've now shrunk it again to 90 characters. It
>passes the tests you've listed above fine.
>
>main(c){for(;x(),y+1;putchar(y));}
>
The for loop can be rearranged to give an 89 character solution:
y;x(c){isalnum(c=getchar())|c==95?x(),putchar(c):(y=c);}
main(c){for(;y+1;putchar(y))x();}
-Justin
Ed Hanway
: Seems like 90 characters is dogging me a bit at the moment. Someone else is on
: 90 too I believe :-)
:
: Can anyone see any simple optimisations to shrink either of these two (or the
: other 90 character solution) to get an 89er?
This one's 88, ignoring newlines. It's basically the same as one of your
solutions, but derived independently, believe it or not.
q;x(c){isalnum(c=q=getchar())||c==95?x(),putchar(c):0;}
main(){while(x(),1+q)putchar(q);}
--
Ed Hanway <han...@ekfido.kodak.com>
Ed Hanway
: Aha! Got it down to 87 characters:
:
: y;x(c){isalnum(y=c=getchar())|c==95?x(),putchar(c):0;}
^
This won't work if the right side of the | is evaluated before the left.
Replacing with || (at cost of one character, alas), works.
--
Ed Hanway <han...@ekfido.kodak.com>
James Irl Waldby
>>Aha! Got it down to 87 characters:
>>
>>y;x(c){isalnum(y=c=getchar())|c==95?x(),putchar(c):0;}
>>main(){while(x(),y+1)putchar(y);}
>>
>>Neat-o.
>> -Matt
>>(Yes, I _know_ this is stupid. But it's a challenge and it's fun.)
>Here you go, down to 85 characters:
>y;x(c){isalnum(y=c=getchar())|c==95&&x()+putchar(c);}
>main(){for(;y+1;putchar(y))x();}
>-Justin
Well, that's a relief! (to see some C solutions under 88 characters...
wouldn't want Zefram's entry to win ... :) (he wrote, on one line:
main(){execlp("perl","","-ne","for$i(split/(\\W)/)
{print reverse(split//,$i),$1;}",0);}
which is an 88 character "cop-out" as he referred to it.)
-- James
Staffan Ulfberg
this is my contribution to the contest:
d;main(w,r){for(;1+(d=isalnum(r=getchar())||r==95?main(0),putchar(r),d:r)&&w;
putchar(d));}
The program is 92 characters including 2 newlines.
Staffan
--
/D{def}def /d{.00017 add D}D /C{2 copy dup mul exch dup mul}D /g 150 string
D /y .29 D 150 150 8[.4 0 0 .4 -45 -90]{/x -1.2 D 0 1 149{x y /n 300 D{/n n
5 sub D C exch sub x add 3 1 roll 2 mul mul y add C add 4 gt n 5 eq or{exit
}if}loop pop pop g exch n put /x x d}for /y y d g}image showpage
James Bonfield
I know it's bad form to keep replying to your own news, but I've got down to
89 characters, albeit at the expense of not working too well in the case
where we don't end in a non word character.
Anyway, even though it doesn't strictly meet the requirements in that case,
here it is:
y,z;main(c){isalnum(c=getchar())|c==95?main(++z),putchar(c),--z||main(putchar(y)):(y=c);}
James Bonfield
>y;x(c){isalnum(c=getchar())||c =='_'?x()|putchar(c):(y=c);}
>main(c){for(;x(),y+1;putchar(y));}
I noticed a rogue space in there which I've removed. I've also taken a hint
from others and decided that if I'm assuming EOF==-1 then I can also assume
ascii and use 95 instead of '_'.
Finally, I think I'm a bit unportable with 'x()|putchar(c)' which won't
necessarily do the putchar after calling x. Use of '||' solves this (and I
don't lose space because I realised the other || can be made to a |) :-)
So, we now have 91 characters (ignoring the newlines for formatting purposes):
y;x(c){isalnum(c=getchar())|c==95?x()||putchar(c):(y=c);}
main(c){for(;x(),y+1;putchar(y));}
There's still redundancy to remove in there - two putchar calls for starters!
James
PS. I think it's a bit dubious claiming an overall winner, as anyone could
take my program and optimise it a bit more, and I could take other peoples
ideas to optimise mine more. With everyone posting answers it's hard to see
who's taken ideas from whom. Therefore I suggest that the winning money be
donated to FSF; certainly do so should I win anyway.
John Ellson
Labeeb Ismail <lab...@ornews.intel.com> wrote:
>In article <42k656$o...@transfer.stratus.com>,
>Matt Cross <mcr...@bonehead.sw.stratus.com> wrote:
>>In article <42ifbm$2...@vixen.cso.uiuc.edu>,
>>James Irl Waldby <j-wa...@glhpx11.cen.uiuc.edu> wrote:
>>>Now for the contest!
>>>
>>>lengths of input lines, but no limit on number of lines.
>>
>>Do we get extra points for not assuming this?
>>
>>>program that compiles ok with gcc 2.7.0 and is posted here before 5
>>>pm CDT on 13 Sept 95. Posted programs remain intellectual property
>>>of posters, as far as I'm concerned; the prize money is just to
>>>double (?) the fun.
>>
>
>Here is my entry contains 144 chars
>
>s[65536];h;c;main(){while((c=getch())!=4)if((c>47)&&(c<58)||
>((c&~32)>64)&&((c&~32)<91)||(c==95))s[h++]=c;else{for(;h;
>putch(s[--h]));putch(c);}}
Hmm. This didn't compile for me, but here is a derivitive
that gets it down to 114 characters.
s[65536];h;main(c){while((c=getchar())>=0)
if(isalnum(c)||c==95)s[h++]=c;else{for(;h;putchar(s[--h]));putchar(c);}}
I note that this solution assumes that the last character of the file is
a newline (or other non reversing character) or else the last word isn't
printed. Is this OK by the rules of the contest?
Also it is system dependent on '_' and EOF values.
John Ellson
Matt Cross
James Bonfield <j...@mrc-lmb.cam.ac.uk> wrote:
>In article <42prsd$5...@lyra.csx.cam.ac.uk> j...@mrc-lmb.cam.ac.uk (James Bonfield) writes:
>>main(c){for(;x(),y+1;putchar(y));}
>
>Same length again (90), but recursing entirely in main. This is even more
>obscure than the other one!
>
>y,z;main(c){isalnum(c=getchar())|c==95?main(++z),putchar(c),z--||putchar(y),main():(y=c);}
This second one doesn't seem to work at all for me... But that first
one looks real good. You can get rid of the c in main(c), since you
don't use it in main (oops). I tried changing the 'for' to a 'while',
but you end up with the same # of characters, though it does look
nicer:
y;x(c){isalnum(c=getchar())|c==95?x(),putchar(c):(y=c);}
main(){while(x(),y+1)putchar(y);}
Will
: In article <42ifbm$2...@vixen.cso.uiuc.edu>,
: James Irl Waldby <j-wa...@glhpx11.cen.uiuc.edu> wrote:
: > (2) You can assume some reasonable limit such as 65536 characters on
: >lengths of input lines, but no limit on number of lines.
: Do we get extra points for not assuming this?
any stackbased approach does have a linit only in stacksize, and it does
limit only the length of words, not lines or text.
: How do you measure shortest?
I would have expected to measure it in cleverness of algorithm, using
less operations is more clever than using a shorter sourcecode?
: #include <stdio.h>
: #define x _=getchar();if(isalnum(_)||_=='_')main(-1)
: main(_){if(_>=0){a:x;if(_!=-1){putchar(_);goto a;}}
: else{x,putchar(_);else ungetc(_,stdin);}}
jeesuz :-)
Well, I used the nonrecursive approach, where I push all the characters
I read if they are not whitespaces, and if I read a whitespace, I simply
pop all the characters again and write them out - so they are reversed.
/* revertwords.c *****************************************************/
#include <stdio.h>
#include <ctype.h>
#include "charstack.h"
extern long int stackpos;
void WriteOutWordReversed() {
char c;
/* all except the terminating NULL does get putchared */
while (c = pop())
putchar(c);
}
/* this is a general errorfunction to be called by the libs like the
stack when it is underflowed or something. */
void error(char *msg) {
printf("error: %s\n", msg);
exit(1);
}
main() {
char c;
initstack();
while (!feof(stdin)) {
c = getchar();
if (isspace(c)) {
WriteOutWordReversed();
putchar(c);
} else
push(c);
}
}
the charstack is just a single stack where I can push chars <> 0 on,
and pop them - if I get a 0 back from pop, it means the stack is empty.
Is there a shorter (means better performing - less operations) algorithm
for the task?
Cheers, Michael Will
PS:
I will add the stack-source here for completion, but it is not part of the
reversionalgorithm, is it?
/* charstack.c **********************************/
#define MAX_STACK 600
char stack[MAX_STACK];
long int stackpos;
void initstack() {
stackpos = MAX_STACK;
}
char pop() {
if (stackpos < MAX_STACK)
return(stack[stackpos++]);
else return(0);
}
void push(char c) {
if (stackpos>0) stack[--stackpos] = c; else error("stack: overflow");
}
long int printstackused() {
printf("%d char in stack.\n", MAX_STACK - stackpos);
}
/* charstack.h ********************************/
#ifndef CHAR_STACK_H
#define CHAR_STACK_H
#define MAX_STACK 600
extern void initstack();
extern char pop();
extern void push(char c);
extern long int printstackused();
#endif
#/* Makefile ***************************/
all: revertwords
revertwords: revertwords.o charstack.o
Justin Legakis
>
>y;x(c){isalnum(y=c=getchar())|c==95?x(),putchar(c):0;}
>main(){while(x(),y+1)putchar(y);}
>
>Neat-o.
>
> -Matt
>
>(Yes, I _know_ this is stupid. But it's a challenge and it's fun.)
Labeeb Ismail
James Bonfield <j...@mrc-lmb.cam.ac.uk> wrote:
>
>y,z;main(c){isalnum(c=getchar())|c==95?main(++z),putchar(c),--z||main(putchar(y)):(y=c);}
>
> James
>James Bonfield (j...@mrc-lmb.cam.ac.uk) Tel: 01223 402499 Fax: 01223 412282
>Medical Research Council - Laboratory of Molecular Biology,
>Hills Road, Cambridge, CB2 2QH, England.
I thought that the initial requirement was that the program continues to reverse
words till the eof. (ie. the number of input lines can be infinite).
The above program when run with ls -l| proagam_name inversed only the first line
Labeeb.
Paul Gentieu
[snip 1st optimization of James Bonfield's original]
>Here you go, down to 85 characters:
>
>y;x(c){isalnum(y=c=getchar())|c==95&&x()+putchar(c);}
>main(){for(;y+1;putchar(y))x();}
>
>-Justin
>
And now down to 84:
y;x(c){isalnum(y=c=getchar())|c==95&&x()+putchar(c);}
main(){for(;~y;putchar(y))x();}
Here's my latest, with 87.
_[99999],l;main(){for(;~(!l|isalnum(*_)|*_==
95?*_=_[++l]=getchar():putchar(_[--l])););}
-Paul
Staffan Ulfberg
>Here you go, down to 85 characters:
>y;x(c){isalnum(y=c=getchar())|c==95&&x()+putchar(c);}
>main(){for(;y+1;putchar(y))x();}
Two questions: (It's monday moring, so maybe these are supid:-)
How come you can use | instead of ||? I mean, you want to read c
before comparing it to 95, right?
This program will output the EOF character, won't it?
Staffan
--
----------------------------------------------------------------------
Staffan Ulfberg phone: int+46 920 87353
Email: sta...@ludd.luth.se
PGP key: finger sta...@mother.ludd.luth.se
Phil Knaack
j-wa...@glhpx11.cen.uiuc.edu (James Irl Waldby) writes:
> (1) Write a short C program to act the same way, ie, if a.out is the
>name of the executable, then a.out is a filter that reverses "letters" *
>of words in its stdin output while copying non-letters and writes the
>results to stdout.
I failed to notice the shortest one that had been posted, but a
friend of mine (I can't claim credit, I'm not nearly this good :) managed
to get it down to 79 characters. This is a later modification of one that
someone else posted here a while ago (I failed to notice who).
y;x(c){isalnum(y=c=getchar())&&x()|putchar(c);}main(){for(;x(),~y;putchar(y));}
Cheers,
Phil
--
Phillip F Knaack
fl...@iastate.edu
Larry Wall
:
: >>Aha! Got it down to 87 characters:
: >>
: >>y;x(c){isalnum(y=c=getchar())|c==95?x(),putchar(c):0;}
: >>main(){while(x(),y+1)putchar(y);}
: >>
: >>Neat-o.
: >> -Matt
: >>(Yes, I _know_ this is stupid. But it's a challenge and it's fun.)
: >Here you go, down to 85 characters:
:
: >y;x(c){isalnum(y=c=getchar())|c==95&&x()+putchar(c);}
: >main(){for(;y+1;putchar(y))x();}
: >-Justin
:
: Well, that's a relief! (to see some C solutions under 88 characters...
: wouldn't want Zefram's entry to win ... :) (he wrote, on one line:
: main(){execlp("perl","","-ne","for$i(split/(\\W)/)
: {print reverse(split//,$i),$1;}",0);}
: which is an 88 character "cop-out" as he referred to it.)
Well, if that's your goal, you're gonna have to work a little harder.
I sent this out last week, but it never made it off my machine. It's
50 characters, counting the final newline.
main(){system("perl -pe 's/\\w+/reverse$&/eg'");}
It's almost readable, too.
Larry Wall
lw...@sems.com
James Bonfield
> I failed to notice the shortest one that had been posted, but a
>friend of mine (I can't claim credit, I'm not nearly this good :) managed
>to get it down to 79 characters. This is a later modification of one that
>someone else posted here a while ago (I failed to notice who).
>
>y;x(c){isalnum(y=c=getchar())&&x()|putchar(c);}main(){for(;x(),~y;putchar(y));}
This doesn't work as it assumes isalnum() will accept underscore as an
alphanumeric, which is doesn't. That's where all the extra space comes from.
Besides which, there are also a number of flaws with programs, including this
one, that people have been making:
1. x()|putchar(c) is NOT the same as x()||putchar(c). It may happen to
work the same on your compiler, but that's luck. The order of
evaluation is not guaranteed with |, but is with ||. This can be seen
in the isalnum(y=c=getchar())|c==95 expression which many people use -
that's also wrong as it may check c against 95 before assigning it.
2. for(;~y;putchar(y))x(); will output one extra character when we don't
(eg) end in a newline.
Given these constraints for a program that only assumes things about C, not
the system, we get:
y;x(c){isalnum(y=c=getchar())||c==95?x(),putchar(c):0;}
main(){for(;x(),~y;putchar(y));}
which is 87 characters. I tried fiddling with using && and removing the ?:
operator, but this requires extra brackets (I think) to be system independant
again and so ends up worse (or the same, I forget which).
No doubt you'll all point out the bits I've missed :-)
Staffan Ulfberg
And now down to 84:
y;x(c){isalnum(y=c=getchar())|c==95&&x()+putchar(c);}
main(){for(;~y;putchar(y))x();}
I've tried this one now, and it does indeed output an EOF charater at
the end.
Here's my latest, with 87.
_[99999],l;main(){for(;~(!l|isalnum(*_)|*_==
95?*_=_[++l]=getchar():putchar(_[--l])););}
Here's my latest using 86 characters:
d;main(w,r){while(w*~(isalnum(d=r=getchar())||r==95?main(0),putchar(r):r))
putchar(d);}
Staffan Ulfberg
man yes |perl -ne "s/\W//g; print" > testF
man ls | perl -ne "s/\W//g; print" > testG
I have run entries from bonfield, cross, gentieu, labeeb, labeeb,
and zefram thru test suite and saw symptoms of this problem with
most entries but unfortunately have been looking for c library bugs
instead of figuring it out like you did. :) --jiw
Too bad, I noticed that my entry didn't make it all the way either,
but this 86 character piece of code will hopefully work:
d;main(w,r){while(isalnum(d=r=getchar())||r==95?main(0),putchar(r):7,~d*w)
Staffan Ulfberg
>Here you go, down to 85 characters:
>y;x(c){isalnum(y=c=getchar())|c==95&&x()+putchar(c);}
>main(){for(;y+1;putchar(y))x();}
Hmmm... the x()+putchar(c) won't guarantee execution order, I think.
Using the same techniques as above, I can get from:
d;main(w,r){while(isalnum(d=r=getchar())||r==95?main(0),putchar(r):7,~d*w)putchar(d);}
to:
d;main(w,r){while(isalnum(d=r=getchar())|r==95&&main(0)+putchar(r),~d*w)putchar(d);}
which sums up to 84 characters. So, any opinions on what rules to
use? I'd vote for allowing EOF=-1 and '_'=95, but disallowing
dependece of order of execution. Comments?
James Bonfield
>
>[snip 1st optimization of James Bonfield's original]
>
>main(){for(;~y;putchar(y))x();}
Goodness - doesn't anyone go home at the weekends!!!
I think the optimisation of moving x() isn't correct. It always outputs an
extra (undefined probably) character for me. Putting that back how it was we
get the 100% working (as far as I can tell) program:
y;x(c){isalnum(y=c=getchar())|c==95&&x()+putchar(c);}
main(){for(;x(),~y;putchar(y));}
This is 85 characters, which is still 5 less than I had originally. As I
mentioned in an ealier post, I half expected this would happen - that the
contest would soon spiral into an interative approach which many 'authors'.
Thus I think the person to whom the prize should go to is somewhat unclear. If
the prize is still available, I reckon it should go to some worthy cause.
(Unless of course some smart alec has privately sent some email to the author
containing a 10 character solution ;-).
>Here's my latest, with 87.
>
>_[99999],l;main(){for(;~(!l|isalnum(*_)|*_==
>95?*_=_[++l]=getchar():putchar(_[--l])););}
Oh YUK! You're really going for obfuscation as well as shortness.
A slight problem though - it (like some of my earlier attempts) doesn't work
when ran on the following:
$ echo -n 'foo bar' | ./a.out
oof $
It appears to only work when the last character is a non word symbol.
James
PS. Can anyone shrink this integer square root program? Algorithm (and
original code) supplied by Steve Sykes; shrinkage by me. 116 characters.
x,y,l,c,k=16;main(char**v){x=atoi(*++v);for(;k--;l=l*4|x>>
30&3,x*=4,y=(c+=c)*2,l>y&&(c++,l-=y+1));printf("%d\n",c);}
James Irl Waldby
>In <42ifbm$2...@vixen.cso.uiuc.edu>
> j-wa...@glhpx11.cen.uiuc.edu (James Irl Waldby) writes:
>> (1) Write a short C program to act the same way, ie, if a.out is the
>>name of the executable, then a.out is a filter that reverses "letters" *
>>of words in its stdin output while copying non-letters and writes the
>>results to stdout.
> I failed to notice the shortest one that had been posted, but a
>friend of mine (I can't claim credit, I'm not nearly this good :) managed
>to get it down to 79 characters. This is a later modification of one that
>someone else posted here a while ago (I failed to notice who).
>y;x(c){isalnum(y=c=getchar())&&x()|putchar(c);}main(){for(;x(),~y;putchar(y));}
>Cheers, >Phil >-- >Phillip F Knaack >fl...@iastate.edu
On my machine with test file E created via
man ls | perl -ne "s/\W//g; print" > tinE
and H, a gunzip'd copy of G, this fails to work:
j-waldby ~/src/rev > run-test knaack
80 characters in program rev-knaack.c
/* From: fl...@iastate.edu (Phil Knaack) Date: 11 Sep 95 16:18:36 GMT */
y;x(c){isalnum(y=c=getchar())&&x()|putchar(c);}main(){for(;x(),~y;putchar(y));}
ok A ok B ok C ok D fail E ok F ok G fail H
j-waldby ~/src/rev > wc tin*
1 5 31 tinA
12 42 312 tinB
0 1 50000 tinC
0 1 150000 tinD
0 1 7012 tinE
1 1 150001 tinF
12121 76492 401076 tinG
617 3766 165129 tinH
12752 80309 923561 total
j-waldby ~/src/rev > run-test me
115 characters in program rev-me.c
/* James Waldby - a simple recursive solution - 9/7/95 */
d;r(c){if(isalnum(c=getchar())||c==95){d=r(0);putchar(c);return
d;};return c;}main(){while(d=r(0)+1)putchar(d-1);}
ok A ok B ok C ok D ok E ok F ok G ok H
j-waldby ~/src/rev > run-test b3-c
88 characters in program rev-b3-c.c
/* From: j...@mrc-lmb.cam.ac.uk (James Bonfield) 8 Sep 1995 16:43:57 GMT */
/* From: mcr...@bonehead.sw.stratus.com (Matt Cross) 8 Sep 1995 19:06:41 GMT */
y;x(c){isalnum(y=c=getchar())|c==95?x(),putchar(c):0;}main(){while(x(),y+1)putchar(y);}
ok A ok B ok C ok D ok E ok F ok G ok H
James Irl Waldby
>In article <42qq6o$q...@gap.cco.caltech.edu> pgen...@alumni.caltech.edu (Paul Gentieu) writes:
>>Justin Legakis <legakis> wrote:
>>
>>[snip 1st optimization of James Bonfield's original]
>>And now down to 84:
>>
>>y;x(c){isalnum(y=c=getchar())|c==95&&x()+putchar(c);}
>>main(){for(;~y;putchar(y))x();}
>Goodness - doesn't anyone go home at the weekends!!!
>I think the optimisation of moving x() isn't correct. It always outputs an
>extra (undefined probably) character for me. Putting that back how it was we
>get the 100% working (as far as I can tell) program:
>y;x(c){isalnum(y=c=getchar())|c==95&&x()+putchar(c);}
>main(){for(;x(),~y;putchar(y));}
It works ok on tests I ran, too --
jw> run-test b3-c-l-g-b
86 characters in program rev-b3-c-l-g-b.c
/* j...@mrc-lmb.cam.ac.uk (James Bonfield) writes: */
y;x(c){isalnum(y=c=getchar())|c==95&&x()+putchar(c);}main(){for(;x(),~y;putchar(y));}
ok A ok B ok C ok D ok E ok F ok G ok H
which is a contrast to test for the former version --
jw> run-test b3-c-l-g
85 characters in program rev-b3-c-l-g.c
/* From: j...@mrc-lmb.cam.ac.uk (James Bonfield) 8 Sep 1995 16:43:57 GMT */
/* From: mcr...@bonehead.sw.stratus.com (Matt Cross) 8 Sep 1995 19:06:41 GMT */
/* From: Justin Legakis <legakis> 8 Sep 1995 20:29:35 GMT */
/* From: pgen...@alumni.caltech.edu (Paul Gentieu) 9 Sep 1995 01:21:28 GMT */
y;x(c){isalnum(y=c=getchar())|c==95&&x()+putchar(c);}main(){for(;~y;putchar(y))x();}
fail A fail B fail C fail D fail E fail F fail G fail H
>This is 85 characters, which is still 5 less than I had originally. As I
>mentioned in an ealier post, I half expected this would happen - that the
>contest would soon spiral into an interative approach which many 'authors'.
>Thus I think the person to whom the prize should go to is somewhat unclear. If
>the prize is still available, I reckon it should go to some worthy cause.
>(Unless of course some smart alec has privately sent some email to the author
>containing a 10 character solution ;-).
The rules provide that all entries must be posted to newsgroup.
I was all set to post a summary of results, thinking there would
be no more entries, but will need to re-run the summary and
post it late today.
You are right about the "spiraling interactive approach", although
at least three separate threads of development are still visible -
iterative C, recursive C, system call to perl ...
>>Here's my latest, with 87.
>>
>>_[99999],l;main(){for(;~(!l|isalnum(*_)|*_==
>>95?*_=_[++l]=getchar():putchar(_[--l])););}
I think this failed test D, an out-of-specs 150000-character word.
The easy fix is substitute 1<<18 for 99999.
Justin Legakis
>In article <flipk.8...@soclab.soc.iastate.edu> fl...@iastate.edu (Phil Knaack) writes:
>Besides which, there are also a number of flaws with programs, including this
>one, that people have been making:
>
>1. x()|putchar(c) is NOT the same as x()||putchar(c). It may happen to
> work the same on your compiler, but that's luck. The order of
> evaluation is not guaranteed with |, but is with ||. This can be seen
> in the isalnum(y=c=getchar())|c==95 expression which many people use -
> that's also wrong as it may check c against 95 before assigning it.
>
>2. for(;~y;putchar(y))x(); will output one extra character when we don't
> (eg) end in a newline.
>
>Given these constraints for a program that only assumes things about C, not
>the system, we get:
>
>y;x(c){isalnum(y=c=getchar())||c==95?x(),putchar(c):0;}
>main(){for(;x(),~y;putchar(y));}
>
>which is 87 characters. I tried fiddling with using && and removing the ?:
>operator, but this requires extra brackets (I think) to be system independant
>again and so ends up worse (or the same, I forget which).
OK, how about this one? 81 characters:
y;x(c){isalnum(y=getchar())||y==95?x(y):0;putchar(c?c:y);}
main(){for(;x(0),~y;);}
-Justin
James Irl Waldby
>In article <42qcpp$a...@vixen.cso.uiuc.edu>,
>James Irl Waldby <j-wa...@glhpx11.cen.uiuc.edu> wrote:
...
>: Well, that's a relief! (to see some C solutions under 88 characters...
>: wouldn't want Zefram's entry to win ... :) (he wrote, on one line:
>: main(){execlp("perl","","-ne","for$i(split/(\\W)/)
>: {print reverse(split//,$i),$1;}",0);}
>: which is an 88 character "cop-out" as he referred to it.)
>Well, if that's your goal, you're gonna have to work a little harder.
>I sent this out last week, but it never made it off my machine. It's
>50 characters, counting the final newline.
> main(){system("perl -pe 's/\\w+/reverse$&/eg'");}
>It's almost readable, too. >Larry Wall >lw...@sems.com
This works fine. Disregard that now-cancelled post I made saying
otherwise. I had two errors in testing: (1) trying
perl -pe 's/\\w+/reverse$&/eg' at the shell prompt, I should have
left out a \. (2) in test script, should have said ./$i < ...
instead of $i < ... since /usr/bin/wall's behavior doesn't
conform to contest specs. Will post test script late today
with a summary of test results for several programs.
Anyway, as the above program makes obvious, in
for$i(split/(\\W)/){print reverse(split//,$i),$1;}
the split// is totally unnecessary since reverse of a scalar
is a string reverse; the () to get $1 isn't needed since
$& has match results; the -p makes perl print as well as loop;
and the e (evaluate replacement as expression) modifier makes
a separate reverse call unnecessary. How'd you know all
that stuff, Larry? :-)
- James Waldby
John Ellson
Larry Wall <lw...@netlabs.com> wrote:
>In article <42qcpp$a...@vixen.cso.uiuc.edu>,
>James Irl Waldby <j-wa...@glhpx11.cen.uiuc.edu> wrote:
>:
>: >>Aha! Got it down to 87 characters:
>
>I sent this out last week, but it never made it off my machine. It's
>50 characters, counting the final newline.
>
> main(){system("perl -pe 's/\\w+/reverse$&/eg'");}
>
>It's almost readable, too.
>
>Larry Wall
>lw...@sems.com
Well, if we're allowed to write our own interpreters then yours is
easy to beat!
main(){system("a");}
20 characters! (Not counting the final newline.)
You haven't heard of my interpreter "a"? Well it just so happens
that, without any command line arguments, it filters stdin to stdout
in a manner that is identical to any of the valid entries to this
competition, like your entry above for example. :-)
John Ellson
I'm so glad that you found a way to get rid of the second putchar().
Unfortunately this code puts out an extra character at the end (the EOF).
It can be fixed with 4 characters, so now at 85:
y;x(c){isalnum(y=getchar())||y==95?x(y):0;~y&&putchar(c?c:y);}
main(){for(;x(0),~y;);}
John Ellson
James Bonfield
>86 characters in program rev-b3-c-l-g-b.c
>/* j...@mrc-lmb.cam.ac.uk (James Bonfield) writes: */
>y;x(c){isalnum(y=c=getchar())|c==95&&x()+putchar(c);}main(){for(;x(),~y;putchar(y));}
> ok A ok B ok C ok D ok E ok F ok G ok H
>
It may work, but I'm still suspicious about that | symbol. It's not guaranteed
that the isalnum(y=c=getchar()) will be tested for before the c==95 check.
Also, unless I've misaligned your comments, I have a feeling this is
attributed wrongly (although I couldn't say for sure as we all seem to have
posted so many!).
James
Paul Gentieu
>
>OK, how about this one? 81 characters:
>
>y;x(c){isalnum(y=getchar())||y==95?x(y):0;putchar(c?c:y);}
>main(){for(;x(0),~y;);}
>
>-Justin
That's an amazing piece of code...
I was able to save a character by inverting the condition.
y;x(c){!isalnum(y=getchar())&&y^95||x(y);putchar(c?c:y);}
main(){for(;x(0),~y;);}
-Paul
James Bonfield
>OK, how about this one? 81 characters:
>
>y;x(c){isalnum(y=getchar())||y==95?x(y):0;putchar(c?c:y);}
>main(){for(;x(0),~y;);}
Brilliant (especially removing that double putchar), but it still outputs an
extra character on certain conditions.
I can fix this, but that gives 86 characters.
y;x(c){isalnum(y=getchar())||y==95?x(y):0;~y|c&&putchar(c?c:y);}
main(){for(;~y;)x(0);}
Paul Gentieu
>>
>>y;x(c){isalnum(y=getchar())||y==95?x(y):0;putchar(c?c:y);}
>>main(){for(;x(0),~y;);}
>I was able to save a character by inverting the condition.
>
>main(){for(;x(0),~y;);}
I just noticed that these print character 255 at the end.
Oh well. Anyway here's another 1 character savings:
y;x(c){!isalnum(y=getchar())&&y^95||x(y);putchar(c?c:y);}
main(){for(;~y;x(0));}
-Paul
John Ellson
John Ellson <ell...@hotair.att.com> wrote:
>In article <43224i$c...@fido.asd.sgi.com>, Justin Legakis <legakis> wrote:
>>>In article <flipk.8...@soclab.soc.iastate.edu> fl...@iastate.edu (Phil Knaack) writes:
>>
>>
>>y;x(c){isalnum(y=getchar())||y==95?x(y):0;putchar(c?c:y);}
>>main(){for(;x(0),~y;);}
>>
>
>I'm so glad that you found a way to get rid of the second putchar().
>Unfortunately this code puts out an extra character at the end (the EOF).
>It can be fixed with 4 characters, so now at 85:
>
>main(){for(;x(0),~y;);}
>
>John Ellson
No, after sleeping on it I realised that it won't print the last word
if the file doesn't end in a non-word character, and it won't print NUL
characters.
So now I have an ugly 90 characters, but still only one putchar():
y;x(c){isalnum(y=getchar())||y==95?x(y):0;~c|~y&&putchar(~c?c:y);}
main(){for(;x(~0),~y;);}
Larry Wall
John Ellson <ell...@hotair.att.com> wrote:
: In article <1995Sep11....@netlabs.com>,
Well, hey, I said you'd have to work a *little* harder, not a lot harder. :-)
Larry
James Irl Waldby
reverse-the-words C program contest (ends 13 Sep 95) in
comp.programming.contests.
Two of the programs are listed here; all of them are listed, along
with a summary of contest rules and the 'run-tests' and 'run-test'
scripts, in the file
http://biobio.cs.uiuc.edu/~j-waldby/results.rev
which I will update if there are more entries.
In case of errors or omissions -- sorry, let me know.
- James Waldby j-wa...@uiuc.edu 12 Sep 95
The shortest C program that worked ok on my system was:
/* From: lw...@netlabs.com (Larry Wall) Date: Mon, 11 Sep 1995 16:23:27 GMT */
main(){system("perl -pe 's/\\w+/reverse$&/eg'");}
which had result:
wall 50 ok ok ok ok ok ok ok ok ok
The shortest C-library-based program that worked ok on my system was:
/* From: j...@mrc-lmb.cam.ac.uk (James Bonfield) 8 Sep 1995 16:43:57 GMT */
/* From: mcr...@bonehead.sw.stratus.com (Matt Cross) 8 Sep 1995 19:06:41 GMT */
/* From: Justin Legakis <legakis> 8 Sep 1995 20:29:35 GMT */
/* From: sta...@ludd.luth.se (Staffan Ulfberg) 11 Sep 1995 16:59:31 +0200 */
d;main(w,r){while(isalnum(d=r=getchar())|r==95&&main(0)+putchar(r),~d*w)putchar(d);}
which had result:
b-c-l-u2 85 ok ok ok ok ok ok ok ok ok
The columns of chart are: 1, key to names of author(s).
2, length of program exclusive of comments; sometimes a little
different from length mentioned in newsgroup.
3-11, results of test with data sets a ... i generated by run-test.
Per wc, dataset sizes (lines, ws-delimited-words, characters) are:
1 6 39 tia
0 6 38 tib
1 1 50001 tic
0 1 50000 tid
0 1 150000 tie
451 2644 113028 tif
0 1 580 tig
0 1 7012 tih
2047 9069 100000 tii
Tests were done on my i486dx2-66, linux 1.2.8, gcc 2.7.0-elf system.
'ok' means that the program under test correctly reversed the 'words'
of its input (where words have letters, _, or digits) and then
reversed that output back ok. 'fail' means that on my system for
that input dataset the program didn't work -- perhaps due to program
portability problem, maybe an error in testing procedure, maybe an
array or stack overflow, or, or -- who knows, maybe even due to error
in program under test. :)
---------------chart-----------------
Start at Tue Sep 12 09:43:54 CDT 1995
bonfield 94 fail fail fail fail fail fail fail fail fail
bonfield2 92 fail fail fail fail fail fail fail fail fail
bonfield3 91 ok ok ok ok ok ok ok ok ok
bonfield4 91 fail fail fail ok ok fail ok ok fail
cross 166 ok ok ok ok ok ok ok ok ok
cross2 146 fail fail fail fail fail fail fail fail fail
cross3 100 ok ok ok ok ok ok ok ok ok
me 115 ok ok ok ok ok ok ok ok ok
ellson 115 ok ok ok fail fail ok fail fail fail
gentieu 110 ok ok ok fail fail ok fail fail fail
gentieu2 100 ok ok ok fail fail ok fail fail fail
gentieu3 88 ok ok ok fail fail ok fail fail fail
hanway 89 fail fail fail fail fail fail fail fail fail
knaack 80 ok ok fail fail fail fail fail fail fail
labeeb 140 ok ok ok fail fail ok fail fail fail
labeeb2 141 ok ok ok fail fail ok fail fail fail
labeeb3 96 fail fail fail fail fail fail fail fail fail
legakis 86 fail fail fail fail fail fail fail fail fail
ulfberg 91 fail fail fail fail fail fail fail fail fail
ulfberg2 87 fail fail fail fail fail fail fail fail fail
ulfberg3 87 fail fail fail fail fail fail fail fail fail
wall 50 ok ok ok ok ok ok ok ok ok
zefram 88 ok ok ok ok ok ok ok ok ok
b-c 88 ok ok ok ok ok ok ok ok ok
b-c-h 89 fail fail fail fail fail fail fail fail fail
b-c-l 86 fail fail fail fail fail fail fail fail fail
b-c-l-b 86 fail fail fail fail fail fail fail fail fail
b-c-l-g 85 fail fail fail fail fail fail fail fail fail
b-c-l-g-b 86 ok ok ok ok ok ok ok ok ok
b-c-l-g-b-l 82 fail fail fail fail fail fail fail fail fail
b-c-l-u 86 fail fail fail fail fail fail fail fail fail
b-c-l-u2 85 ok ok ok ok ok ok ok ok ok
--------end---
wes_k...@wiltel.com
Recursive but about 124 bytes
#include<stdio.h>
g(c){return (c=getchar())==EOF?0:(isalnum(c)|c==95)?g()|c^putchar(c):c;}
main(c){while(c=g())putchar(c);}
--
Wes Kaefer WorldCom Inc. Tel: (918) 588-5461
One Williams Center, Mail Drop D-4 Fax: (918) 588-3719
Tulsa, Oklahoma 74121 Net: wes_k...@wiltel.com
Staffan Ulfberg
In article <43224i$c...@fido.asd.sgi.com> Justin Legakis <legakis> writes:
>y;x(c){isalnum(y=getchar())||y==95?x(y):0;putchar(c?c:y);}
>main(){for(;x(0),~y;);}
Brilliant (especially removing that double putchar), but it still outputs an
extra character on certain conditions.
I can fix this, but that gives 86 characters.
y;x(c){isalnum(y=getchar())||y==95?x(y):0;~y|c&&putchar(c?c:y);}
main(){for(;~y;)x(0);}
This one's also fixed (no extra character in output) - down to 84 charcters:-)
y;main(c){for(c--;!isalnum(y=getchar())&&y-95||main(y),c|~y&&
putchar(c?c+1:y)*!c;);}
Irmgard
Well, what about this one :-)
We need 90 characters, whithout counting the
#includes as most of the contestants did.
In our shortest version we considered '_' not
being an alphanumerical character.
See the version with 2 lines
If we care about '_' we need 8 more characters
because of ||c=='_' makes 98 characters.
See the long version which is a bit more readable !
By the way : how did you get the idea for the contest ?
*/
#include <ctype.h>
#include <stdio.h>
/* Short version not caring about '_'
1 2 3 4
01234567890123456789012345678901234567890123456789012
#define s(i) {r(getchar());putchar(i);}
a;r(c){if(isalnum(a=c))s(c)}main(){while(a!=EOF)s(a)}
*/
/* Short version caring about '_'
1 2 3 4
0123456789012345678901234567890123456789012345678901234567890
#define s(i) {r(getchar());putchar(i);}
a;r(c){if(isalnum(a=c)||c=='_')s(c)}main(){while(a!=EOF)s(a)}
*/
/* long version */
#define s(i) {r(getchar());putchar(i);}
a;
r(c)
{
if(isalnum(a=c)||c=='_')s(c)
}
main()
{
while(a!=EOF)s(a)
}
/*
Written by Irmgard Wasinger
e892...@stud1.tuwien.ac.at
and
Ramin Nourbakhch
e892...@stud1.tuwien.ac.at
*/
James Irl Waldby
>/*
> Well, what about this one :-)
>
> We need 90 characters, whithout counting the
> #includes as most of the contestants did.
#includes count as part of length, and _ must be considered.
I included your version that treats _ as well as alpha-num.
(see http://biobio.cs.uiuc.edu/~j-waldby/results.rev file.)
The 'i-w' program listed after yours is slightly modified
version.
...
> By the way : how did you get the idea for the contest ?
Well, there was this post in rec.arts.poems ...
From: jmi...@forest.drew.edu
And Now a Word From Milton's Satan
################################################
evah uoy reve dehsurc
eht rettib seirreb fo ruoy sniahc
dessot ruoy enam
knurd ni eht dniw fo liah
eht segdeh nrohs-
gnihcterts munipitalp sbmil
ni erab yrolg fo detlem eldirb
neht
dnuof eht seniv ylneerg gnihcnelc
ruoy nedlog selkna
wena?
-ennej
which I had no trouble reading except for munipitalp
so I wrote a program, but the punctuation looked wrong,
so then ...
- James
James Irl Waldby
comp.programming.contests.
Two of the programs are listed here; all of them are listed (for the
next week or two) along with a summary of contest rules and the
'run-tests' and 'run-test' scripts, in the file
http://biobio.cs.uiuc.edu/~j-waldby/results.rev
This list includes 10 more programs than the list posted 2 days ago.
Previous test had no gcc optimization selected. For this test I used
gcc -O6 and seven of the programs worked better than before. See
separate post about this, or http://biobio.cs.uiuc.edu/~j-waldby/result-opt,
a copy of that post. Thanks to Ed Hanley for his analysis re opt.!
And thanks to everyone who entered or commented on the reverse-
the-words contest: Labeeb Ismail, Matt Cross, James Bonfield, Zefram,
Paul Gentieu, W S Cranston, John Ellson, Michael Will, Staffan
Ulfberg, Justin Legakis, Ed Hanway, Phil Knaack, Larry Wall, Wes
Waefer, Irmgard Wasinger and Ramin Nourbakhch.
In case of errors or omissions -- sorry, let me know.
- James Waldby j-wa...@uiuc.edu 13 Sep 95
The shortest C program that worked ok on my system was:
/* From: lw...@netlabs.com (Larry Wall) Date: Mon, 11 Sep 1995 16:23:27 GMT */
main(){system("perl -pe 's/\\w+/reverse$&/eg'");}
which had result:
wall 50 ok ok ok ok ok ok ok ok ok
It looks like all entries are in now and Larry Wall won the contest!
And the prize, a $4.40 check.
The shortest not-Perl-based program that worked ok on my system was:
---------------chart-----------------
Start at Wed Sep 13 20:34:33 CDT 1995
bonfield 94 ok ok ok ok ok ok ok ok ok
bonfield2 92 fail fail fail fail fail fail fail fail fail
bonfield3 91 ok ok ok ok ok ok ok ok ok
bonfield4 91 fail fail fail ok ok fail ok ok fail
cross 166 ok ok ok ok ok ok ok ok ok
cross2 146 ok ok ok ok ok ok ok ok ok
cross3 100 ok ok ok ok ok ok ok ok ok
me 115 ok ok ok ok ok ok ok ok ok
ellson 115 ok ok ok fail fail ok fail fail fail
gentieu 110 ok ok ok fail fail ok fail fail fail
gentieu2 100 ok ok ok fail fail ok fail fail fail
gentieu3 88 ok ok ok fail fail ok fail fail fail
hanway 89 ok ok ok ok ok ok ok ok ok
knaack 80 ok ok fail fail fail fail fail fail fail
labeeb 140 ok ok ok fail fail ok fail fail fail
labeeb2 141 ok ok ok fail fail ok fail fail fail
labeeb3 96 fail fail fail fail fail fail fail fail fail
legakis 86 fail fail fail fail fail fail fail fail fail
ulfberg 91 ok ok ok ok ok ok ok ok ok
ulfberg2 87 ok ok ok fail fail ok fail fail fail
ulfberg3 87 ok ok ok ok ok ok ok ok ok
wall 50 ok ok ok ok ok ok ok ok ok
zefram 88 ok ok ok ok ok ok ok ok ok
b-c 88 ok ok ok ok ok ok ok ok ok
b-c-h 89 ok ok ok ok ok ok ok ok ok
b-c-l 86 fail fail fail fail fail fail fail fail fail
b-c-l-b 86 fail fail fail fail fail fail fail fail fail
b-c-l-g 85 fail fail fail fail fail fail fail fail fail
b-c-l-g-b 86 ok ok ok ok ok ok ok ok ok
b-c-l-g-b-l 82 fail fail fail fail fail fail fail fail fail
b-c-l-u 86 fail fail fail fail fail fail fail fail fail
b-c-l-u2 85 ok ok ok ok ok ok ok ok ok
k-l-b-u 85 ok ok ok ok ok fail ok ok ok
k-b-l-e-e 91 ok ok ok ok ok ok ok ok ok
l-g 80 fail fail fail fail fail fail fail fail fail
l-b 87 ok ok ok ok ok ok ok ok ok
k-b-l-g 82 fail fail fail fail fail fail fail fail fail
k-b-l-e 86 ok ok ok fail fail ok fail fail fail
irmgard 133 fail fail fail fail fail fail fail fail fail
i-w 107 ok ok ok ok ok ok ok ok ok
kaefer 123 ok ok ok ok ok fail ok ok ok
k-w 100 ok ok ok ok ok fail ok ok ok
Finish at Wed Sep 13 20:43:15 CDT 1995
--------end---
James Irl Waldby
and found that optimization level can affect whether some of
the program versions work ok. I don't have his explanation in
front of me, but the idea is that parameters are register-
allocated (for optimized code) and not stack-allocated. An
invalid stack store would fault but a store to register doesn't.
Anyway, here is a list of 7 programs that work a lot better on my
Linux system when compiled with gcc -O6 (">" lines) instead of no
optimization ("<" lines). All of these programs leave off a
parameter to a function call, to save a character or two. (Moral of
story, "compile with optimization." :-) See code, following table.
This file == http://biobio.cs.uiuc.edu/~j-waldby/result-opt
See also: http://biobio.cs.uiuc.edu/~j-waldby/results.rev
for full listings.
< Start at Tue Sep 12 09:43:54 CDT 1995
> Start at Wed Sep 13 20:34:33 CDT 1995
< bonfield 94 fail fail fail fail fail fail fail fail fail
> bonfield 94 ok ok ok ok ok ok ok ok ok
< cross2 146 fail fail fail fail fail fail fail fail fail
> cross2 146 ok ok ok ok ok ok ok ok ok
< hanway 89 fail fail fail fail fail fail fail fail fail
> hanway 89 ok ok ok ok ok ok ok ok ok
< ulfberg 91 fail fail fail fail fail fail fail fail fail
> ulfberg 91 ok ok ok ok ok ok ok ok ok
< ulfberg2 87 fail fail fail fail fail fail fail fail fail
> ulfberg2 87 ok ok ok fail fail ok fail fail fail
< ulfberg3 87 fail fail fail fail fail fail fail fail fail
> ulfberg3 87 ok ok ok ok ok ok ok ok ok
< b-c-h 89 fail fail fail fail fail fail fail fail fail
> b-c-h 89 ok ok ok ok ok ok ok ok ok
bonfield :
/* James Bonfield <jkb> 7 Sep 1995 13:43:33 GMT <42msu5$r...@lyra.csx.cam.ac.uk> */
y;x(c){isalnum(c=getchar())||c =='_'?x()|putchar(c):(y=c);}main(c){for(;x(),y+1;putchar(y));}
cross2 :
/*From: mcr...@bonehead.sw.stratus.com (Matt Cross) 6 Sep 1995 19:17:21 GMT */
r(l,c,d){a:c=getchar();if(isalnum(c)||c=='_'){d=r(1);putchar(c);if(l)return
d;else c=d;}if(l)return c;if(c!=-1){putchar(c);goto a;}}main(){r(0);}
hanway :
/* From: han...@ekfido.kodak.com (Ed Hanway) 8 Sep 1995 20:15:42 GMT */
q;x(c){isalnum(c=q=getchar())||c==95?x(),putchar(c):0;}main(){while(x(),1+q)putchar(q);}
ulfberg :
/* From: staf...@tcs07.nada.kth.se (Staffan Ulfberg) 08 Sep 1995 14:49:41 GMT */
d;main(w,r){for(;1+(d=isalnum(r=getchar())||r==95?main(0),putchar(r),d:r)&&w;putchar(d));}
ulfberg2 :
/* From: staf...@tcs07.nada.kth.se (Staffan Ulfberg) 11 Sep 1995 12:44:22 GMT */
d;main(w,r){while(w*~(isalnum(d=r=getchar())||r==95?main(0),putchar(r):r))putchar(d);}
ulfberg3 :
/* From: staf...@tcs07.nada.kth.se (Staffan Ulfberg) 11 Sep 1995 14:43:12 GMT */
d;main(w,r){while(isalnum(d=r=getchar())||r==95?main(0),putchar(r):7,~d*w)putchar(d);}
b-c-h :
/* From: j...@mrc-lmb.cam.ac.uk (James Bonfield) 8 Sep 1995 16:43:57 GMT */
/* From: mcr...@bonehead.sw.stratus.com (Matt Cross) 8 Sep 1995 19:06:41 GMT */
/* From: han...@ekfido.kodak.com (Ed Hanway) 8 Sep 1995 20:18:57 GMT */
y;x(c){isalnum(y=c=getchar())||c==95?x(),putchar(c):0;}main(){while(x(),y+1)putchar(y);}
--------------------------end---------------