Dave Long writes:
> So I tried allowing myself the luxury of (very small) base-10
> integers and a more mature (though more primitive) rewrite system:
>
> > echo "31240056" | time ./qsort.sed
> 00123456
> 0.01user 0.00system 0:00.02elapsed 35%CPU (0avgtext+0avgdata 0maxresident)k
> 0inputs+0outputs (87major+15minor)pagefaults 0swaps
Very impressive; I finally had a spare morning here in Paris to
understand it. A couple of notes:
- the final s/{}// should probably be s/ {}//
- it bothers me to need two base cases, one for zero-element lists and one for
one-element lists; one can unify them with a little regexp magic, of course:
# zero or one element list is trivially sorted
#-------------------------------------
s/[ ]*{\(.\?\)} \([^ ]*\)/\1 {\2}/
t sort
But that still has both cases, just merged into one regexp. I feel
sure some real simplification must lurk nearby...
> Expansion to arbitrary-length integers is left as an exercise for
> the reader.
I hope to have the time, perhaps on our return flight.
--
<[EMAIL PROTECTED]> Kragen Sitaker <http://www.pobox.com/~kragen/>
Edsger Wybe Dijkstra died in August of 2002. The world has lost a great
man. See http://advogato.org/person/raph/diary.html?start=252 and
http://www.kode-fu.com/geek/2002_08_04_archive.shtml for details.
