On Wed, 2004-06-09 at 07:37, Steve Wampler wrote:
> Here's another little puzzle that's fun do in Icon/Unicon.
> (In this case, the solution I have is Icon-compliant):
>
> Write a program that reads strings from standard input
> and outputs those strings with the letters rearranged in
> alphabetical order.
>
> So for example, given the input "aardvarks are ant eaters",
> the output would be " aaaaaadeeeknrrrrssttv" (note the
> 3 spaces at the start).
There have been a number of very nice solutions provided.
(The above problem description turned out to be vague,
though most solutions interpreted it the same way I did.
Solutions that took it another way aren't included here, but
are no less interesting.)
Since most of the solutions were posted to the groups already
I won't reproduce them here. Here are my solutions. The
first is the one I prefer, the 2nd is an attempt to write
a small "one-liner" and suffers from that attempt by being
too information dense to be easily understood. Both solutions
are interesting in that are written with no 'loops' and instead
rely entirely on goal-directed evaluation - including the reading
of the input lines. The first solution also readily maps (there's
a pun there, sorry) to a solution to the 'dictionary-order'
second challange. That solution also shown below.
Solution 1:
procedure main(args)
every write(ssort(!&input))
end
procedure ssort(s)
s ? every (ns:="") ||:= (tab(upto(!cset(s))),move(1))
return ns
end
Solution 2: (long line was wrapped for the mailer)
procedure main(args)
every !&input ?
(tab(upto(!cset(&subject))),writes(move(1)))|write()
end
Solution 3: (dictionary order - uses same main program as Solution 1)
procedure ssort(s)
map(s) ? every (ns:="") ||:=
2(tab(upto(!cset(map(s)))),s[&pos],move(1))
return ns
end
Kazimir Majoric submitted a particularly clever solution that I
adapted to handle more than one input line. I also produced
a variant of his solution aiming to be slightly more efficient:
procedure main()
while x := read() do {
every writes(!cset(x) == !x)
write()
}
end
Michael Borek provided a solution that spends a little more time up
front in order to take advantage of Icon's sort() function later on.
His solution is particularly efficient on input with long lines,
since the sorting algorithm begins to dominate at some point. (He
also provided a nice solution to the dictionary-order challenge.)
Frank Lhota whipped out an efficient solution quite quickly, his
approach is also quite readable.
Now, performance wasn't a requirement (nor was brevity or clarity
or any other measure, for that matter!) but it's interesting to look at.
Pure combinatorial solutions suffer in the performance
area - which shouldn't be a surprise - and is not particularly important
on short input (naturally, performance tests use large input sets
and so exaggerate this penalty).
Most of the other solutions are really just adding heuristics
to reduce that combinatorial cost. A less obvious cost is that
writing the characters out individually (such as solution 2, above)
adds greatly to the system overhead. In looking at the times below
you might compare both the user-time (cpu-time spent on user code)
and system-time (cpu-time spent on system calls).
Here are the performance results:
# Case 1 - 1.6MB input file, reasonable line lengths
#
weaver% RunTests
------------------ Kazimir Majorinc -----------------------
138.18s user 7.01s system 98% cpu 2:27.98 total
------------------ Kazimir Majorinc(2) -----------------------
14.39s user 6.37s system 98% cpu 20.990 total
------------------ Steve Wampler(2) -----------------------
3.81s user 6.33s system 99% cpu 10.205 total
------------------ Frank Lhota -----------------------
2.81s user 0.23s system 100% cpu 3.039 total
------------------ Michael Borek -----------------------
2.76s user 0.28s system 94% cpu 3.217 total
------------------ Steve Wampler -----------------------
2.21s user 0.26s system 99% cpu 2.472 total
# Case 2 - 2.2MB input file, absurdly long input lines with few letters
#
weaver% RunTests --infile=input2.txt --valid=valid3.txt
------------------ Kazimir Majorinc -----------------------
188.70s user 8.65s system 98% cpu 3:19.67 total
------------------ Kazimir Majorinc(2) -----------------------
103.86s user 8.24s system 98% cpu 1:54.29 total
------------------ Steve Wampler(2) -----------------------
7.00s user 8.95s system 99% cpu 15.953 total
------------------ Frank Lhota -----------------------
5.52s user 0.08s system 99% cpu 5.615 total
------------------ Steve Wampler -----------------------
4.97s user 0.13s system 99% cpu 5.108 total
------------------ Michael Borek -----------------------
4.16s user 0.18s system 99% cpu 4.346 total
My thanks to everyone who posted a solution - I found them all
interesting!
--
Steve Wampler -- [EMAIL PROTECTED]
The gods that smiled on your birth are now laughing out loud.
-------------------------------------------------------
This SF.Net email is sponsored by the new InstallShield X.
>From Windows to Linux, servers to mobile, InstallShield X is the
one installation-authoring solution that does it all. Learn more and
evaluate today! http://www.installshield.com/Dev2Dev/0504
_______________________________________________
Unicon-group mailing list
[EMAIL PROTECTED]
https://lists.sourceforge.net/lists/listinfo/unicon-group
