I noticed that SBCL does not have an entry for the Alioth Shootout
Meteor Puzzle:
http://shootout.alioth.debian.org/gp4/benchmark.php?test=meteor&lang=all
So, being 1/2-way through PCL, now is the time to start thinking about
contributing it.
The spec of the problem and a series of solutions is given here:
http://www-128.ibm.com/developerworks/java/library/j-javaopt/
But I will start with my first question about their listed solution.
Why is each piece used exactly 5 times? Is an acceptable solution to
this puzzle to use one piece 6 times and another 4? I saw nothing in
the problem description precluding this. In fact, I dont even see a
problem description. They just start offering solutions.
On Dec 10, 5:28 am, "metaperl.com" <········@gmail.com> wrote:
> I noticed that SBCL does not have an entry for the Alioth Shootout
> Meteor Puzzle:http://shootout.alioth.debian.org/gp4/benchmark.php?test=meteor〈=all
>
> So, being 1/2-way through PCL, now is the time to start thinking about
> contributing it.
>
> The spec of the problem and a series of solutions is given here:http://www-128.ibm.com/developerworks/java/library/j-javaopt/
>
> But I will start with my first question about their listed solution.
> Why is each piece used exactly 5 times? Is an acceptable solution to
> this puzzle to use one piece 6 times and another 4? I saw nothing in
> the problem description precluding this. In fact, I dont even see a
> problem description. They just start offering solutions.
The Meteor puzzle uses 10 different pieces. A better description of
the puzzle is here:
http://www.win.tue.nl/~wstomv/publications/puzzle-processor-2up.pdf
I actually coded up a solution to this a few weeks ago as a way of
teaching myself lisp. It was my first lisp program longer than a few
lines (since undergrad at least), so a lot of it looks more like C/
python code written in lisp. Also, I was going for clarity, not
speed, so I used lists of symbols, rather than bitmaps like all of the
other solutions do. Because of this, mine is significantly slower
than even the python solution. However, If its of any interest I'll
post it here. What is the best way to post files? It's about 250
lines.
Den Mon, 10 Dec 2007 02:28:49 -0800 skrev metaperl.com:
> I noticed that SBCL does not have an entry for the Alioth Shootout
> Meteor Puzzle:
> http://shootout.alioth.debian.org/gp4/benchmark.php?test=meteor&lang=all
>
>
> So, being 1/2-way through PCL, now is the time to start thinking about
> contributing it.
>
> The spec of the problem and a series of solutions is given here:
> http://www-128.ibm.com/developerworks/java/library/j-javaopt/
>
> But I will start with my first question about their listed solution. Why
> is each piece used exactly 5 times? Is an acceptable solution to this
> puzzle to use one piece 6 times and another 4? I saw nothing in the
> problem description precluding this. In fact, I dont even see a problem
> description. They just start offering solutions.
Indeed. As far as I am able to tell, given the description on that page,
this is a valid solution, and can can be constructed absolutely trivially:
0 0 0 0 0
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5
6 6 6 6 6
7 7 7 7 7
8 8 8 8 8
9 9 9 9 9
10 10 10 10 10
In fact, constructing any solution is trivial, as long as you never create
partial states that'd cause the unfilled part to be partitioned into more
than one piece.
Cheers,
Maciej
On Dec 10, 6:03 am, Maciej Katafiasz <········@gmail.com> wrote:
> Den Mon, 10 Dec 2007 02:28:49 -0800 skrev metaperl.com:
>
> Indeed. As far as I am able to tell, given the description on that page,
> this is a valid solution, and can can be constructed absolutely trivially:
>
> 0 0 0 0 0
> 1 1 1 1 1
> 2 2 2 2 2
> 3 3 3 3 3
> 4 4 4 4 4
> 5 5 5 5 5
> 6 6 6 6 6
> 7 7 7 7 7
> 8 8 8 8 8
> 9 9 9 9 9
> 10 10 10 10 10
>
You used each color 5 times, would it be Ok to use one color 9 times
and another just once, like this:
0 1 1 1 1
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5
6 6 6 6 6
7 7 7 7 7
8 8 8 8 8
9 9 9 9 9
10 10 10 10 10
On Dec 10, 2:28 am, "metaperl.com" <········@gmail.com> wrote:
> I noticed that SBCL does not have an entry for theAliothShootout
> Meteor Puzzle:http://shootout.alioth.debian.org/gp4/benchmark.php?test=meteor〈=all
>
> So, being 1/2-way through PCL, now is the time to start thinking about
> contributing it.
>
> The spec of the problem and a series of solutions is given here:http://www-128.ibm.com/developerworks/java/library/j-javaopt/
>
> But I will start with my first question about their listed solution.
> Why is each piece used exactly 5 times? Is an acceptable solution to
> this puzzle to use one piece 6 times and another 4? I saw nothing in
> the problem description precluding this. In fact, I dont even see a
> problem description. They just start offering solutions.
Each piece /is not/ used exactly 5 times.
Each piece is made up of five hexagons, each of the different coloured
shapes in "Figure 1. A solution for the Meteor puzzle" is a fixed-
shape puzzle piece.
"metaperl.com" <········@gmail.com> writes:
> I noticed that SBCL does not have an entry for the Alioth Shootout
> Meteor Puzzle:
> http://shootout.alioth.debian.org/gp4/benchmark.php?test=meteor&lang=all
>
>
> So, being 1/2-way through PCL, now is the time to start thinking about
> contributing it.
Hmm, are you sure you are not wasting time? Juho Snellman's observations
in
http://groups.google.com/group/comp.lang.lisp/msg/5489247d2f56a848
match exactly with my shootout experience.
Nicolas
On Dec 10, 12:21 pm, Nicolas Neuss <········@math.uni-karlsruhe.de>
wrote:
> "metaperl.com" <········@gmail.com> writes:
> > I noticed that SBCL does not have an entry for theAliothShootout
> > Meteor Puzzle:
> >http://shootout.alioth.debian.org/gp4/benchmark.php?test=meteor〈=all
>
> > So, being 1/2-way through PCL, now is the time to start thinking about
> > contributing it.
>
> Hmm, are you sure you are not wasting time? Juho Snellman's observations
> in
>
> http://groups.google.com/group/comp.lang.lisp/msg/5489247d2f56a848
>
> match exactly with myshootoutexperience.
>
> Nicolas
I'm profoundly ignorant of Lisp, so I don't really understand why it
would be any harder to modify a Lisp program to meet modified
requirements than it would be to modify a program written in some
other language?
Isaac Gouy <······@yahoo.com> writes:
> On Dec 10, 12:21 pm, Nicolas Neuss <········@math.uni-karlsruhe.de>
> wrote:
>> "metaperl.com" <········@gmail.com> writes:
>> > I noticed that SBCL does not have an entry for theAliothShootout
>> > Meteor Puzzle:
>> >http://shootout.alioth.debian.org/gp4/benchmark.php?test=meteor〈=all
>>
>> > So, being 1/2-way through PCL, now is the time to start thinking about
>> > contributing it.
>>
>> Hmm, are you sure you are not wasting time? Juho Snellman's observations
>> in
>>
>> http://groups.google.com/group/comp.lang.lisp/msg/5489247d2f56a848
>>
>> match exactly with myshootoutexperience.
>>
>> Nicolas
>
> I'm profoundly ignorant of Lisp, so I don't really understand why it
> would be any harder to modify a Lisp program to meet modified
> requirements than it would be to modify a program written in some
> other language?
Sure, if you have the time. I have decided for myself that I have better
things to do than keeping my submissions up to date with whatever comes
into your mind.
Nicolas
On Dec 11, 12:27 am, Nicolas Neuss <········@math.uni-karlsruhe.de>
wrote:
> Isaac Gouy <······@yahoo.com> writes:
> > On Dec 10, 12:21 pm, Nicolas Neuss <········@math.uni-karlsruhe.de>
> > wrote:
> >> "metaperl.com" <········@gmail.com> writes:
> >> > I noticed that SBCL does not have an entry for theAliothShootout
> >> > Meteor Puzzle:
> >> >http://shootout.alioth.debian.org/gp4/benchmark.php?test=meteor〈=all
>
> >> > So, being 1/2-way through PCL, now is the time to start thinking about
> >> > contributing it.
>
> >> Hmm, are you sure you are not wasting time? Juho Snellman's observations
> >> in
>
> >> http://groups.google.com/group/comp.lang.lisp/msg/5489247d2f56a848
>
> >> match exactly with myshootoutexperience.
>
> >> Nicolas
>
> > I'm profoundly ignorant of Lisp, so I don't really understand why it
> > would be any harder to modify a Lisp program to meet modified
> > requirements than it would be to modify a program written in some
> > otherlanguage?
>
> Sure, if you have the time. I have decided for myself that I have better
> things to do than keeping my submissions up to date with whatever comes
> into your mind.
And of course it's perfectly reasonable to advise others based on your
experience with the shootout, but I would ask that you include some
indication of whether that experience is current or from years ago.
Nothing much changed over the last 2 years, until a month ago when I
admitted that the concurrency programs had to be reworked into
something better.
Isaac Gouy <······@yahoo.com> writes:
>> Sure, if you have the time. I have decided for myself that I have better
>> things to do than keeping my submissions up to date with whatever comes
>> into your mind.
>
> And of course it's perfectly reasonable to advise others based on your
> experience with the shootout, but I would ask that you include some
> indication of whether that experience is current or from years ago.
>
> Nothing much changed over the last 2 years, until a month ago when I
> admitted that the concurrency programs had to be reworked into something
> better.
My experience dates back from probably 1-2 years ago. But, sorry, I will
not do a re-evaluation at the moment. I have been too much disappointed by
the rules of the shootout[1], by the selection of the tasks[2], and by the
overall management[3]. I really cannot imagine that your shooutout has
changed enough to be worth the time to look at it again. This view may
change if someone in whose opinion I trust gives me reason to think
differently.
Nicolas
[1] E.g. Lisp programs are usually not executed from inside a Unix shell.
They live inside a Lisp environment, such that parameter passing is
unnecessary for most reasonable uses. The measuring of
stand-alone-executable size as binary size for simple Lisp functions is
also highly dubious, at least it is far from any practical relevance.
[2] The tasks are (at least, they were 1-2 years ago) always things that C
or Perl programs could do relatively easily. Why don't we see interesting
tasks like "write a memoize-function", "read in expressions, compile and
execute them" where many non-Lisp languages simply drop out or are very
slow?
[3] Especially the point that you can never be sure that your work will not
be in vain because the benchmark is removed or its specification has been
changed.
On Dec 11, 12:50 pm, Nicolas Neuss <········@math.uni-karlsruhe.de>
wrote:
> Isaac Gouy <······@yahoo.com> writes:
> >> Sure, if you have the time. I have decided for myself that I have better
> >> things to do than keeping my submissions up to date with whatever comes
> >> into your mind.
>
> > And of course it's perfectly reasonable to advise others based on your
> > experience with theshootout, but I would ask that you include some
> > indication of whether that experience is current or from years ago.
>
> > Nothing much changed over the last 2 years, until a month ago when I
> > admitted that the concurrency programs had to be reworked into something
> > better.
>
> My experience dates back from probably 1-2 years ago. But, sorry, I will
> not do a re-evaluation at the moment.
I don't seek to change your opinion, simply to make it clear that your
experience is from 2005.
> I have been too much disappointed by
> the rules of theshootout[1], by the selection of the tasks[2], and by the
> overall management[3]. I really cannot imagine that your shooutout has
> changed enough to be worth the time to look at it again. This view may
> change if someone in whose opinion I trust gives me reason to think
> differently.
>
> Nicolas
>
> [1] E.g. Lisp programs are usually not executed from inside a Unix shell.
> They live inside a Lisp environment, such that parameter passing is
> unnecessary for most reasonable uses. The measuring of
> stand-alone-executable size as binary size for simple Lisp functions is
> also highly dubious, at least it is far from any practical relevance.
Maybe you're trying to tell me that "parameter passing" is some kind
of problem or huge distortion of timings or ... ?
> [2] The tasks are (at least, they were 1-2 years ago) always things that C
> or Perl programs could do relatively easily. Why don't we see interesting
> tasks like "write a memoize-function", "read in expressions, compile and
> execute them" where many non-Lisp languages simply drop out or are very
> slow?
(I seem to recall being told that it /is/ easy to "write a memoize-
function" in Perl.)
The reason we don't invent problems "where many non-Lisp languages
simply drop out" is that we would like programmers who only know "non-
Lisp languages" to look at Lisp programs (and programs in other - not
C, not Java - languages) and we use the C and Java programs as bait.
> [3] Especially the point that you can never be sure that your work will not
> be in vain because the benchmark is removed or its specification has been
> changed.
I can more or less guarantee that a program /will be removed/ after
someone contributes a faster program (or if the benchmark is removed,
or if the specification is changed and the program shows Error).
Isaac Gouy <······@yahoo.com> writes:
>> [1] E.g. Lisp programs are usually not executed from inside a Unix
>> shell. They live inside a Lisp environment, such that parameter passing
>> is unnecessary for most reasonable uses. The measuring of
>> stand-alone-executable size as binary size for simple Lisp functions is
>> also highly dubious, at least it is far from any practical relevance.
>
> Maybe you're trying to tell me that "parameter passing" is some kind
> of problem or huge distortion of timings or ... ?
Oh yes, maybe...
>> [2] The tasks are (at least, they were 1-2 years ago) always things that
>> C or Perl programs could do relatively easily. Why don't we see
>> interesting tasks like "write a memoize-function", "read in expressions,
>> compile and execute them" where many non-Lisp languages simply drop out
>> or are very slow?
>
> (I seem to recall being told that it /is/ easy to "write a memoize-
> function" in Perl.)
As much as I know only with smaller functionality (no arbitrary parameter
lists, or something like that).
>> [3] Especially the point that you can never be sure that your work will
>> not be in vain because the benchmark is removed or its specification has
>> been changed.
>
> I can more or less guarantee that a program /will be removed/ after
> someone contributes a faster program (or if the benchmark is removed, or
> if the specification is changed and the program shows Error).
Thus we can be sure that only the ugliest CL program with the uttermost
number of (optimize (speed 3) (safety 0)) and type declarations will
survive (at least, as long as it does not break for the next changed
specification). Thanks for making this clear.
Nicolas
On Dec 12, 1:15 am, Nicolas Neuss <········@math.uni-karlsruhe.de>
wrote:
> Isaac Gouy <······@yahoo.com> writes:
> >> [1] E.g. Lisp programs are usually not executed from inside a Unix
> >> shell. They live inside a Lisp environment, such that parameter passing
> >> is unnecessary for most reasonable uses. The measuring of
> >> stand-alone-executable size as binary size for simple Lisp functions is
> >> also highly dubious, at least it is far from any practical relevance.
>
> > Maybe you're trying to tell me that "parameter passing" is some kind
> > of problem or huge distortion of timings or ... ?
>
> Oh yes, maybe...
Apparently it's for you to know and me to guess - I'm done guessing.
-snip-
> >> [3] Especially the point that you can never be sure that your work will
> >> not be in vain because the benchmark is removed or its specification has
> >> been changed.
>
> > I can more or less guarantee that a program /will be removed/ after
> > someone contributes a faster program (or if the benchmark is removed, or
> > if the specification is changed and the program shows Error).
>
> Thus we can be sure that only the ugliest CL program with the uttermost
> number of (optimize (speed 3) (safety 0)) and type declarations will
> survive (at least, as long as it does not break for the next changed
> specification). Thanks for making this clear.
No, I'm afraid I can't guarantee that for you - there's no telling
what good programs might be contributed, and we do sometimes show both
a fast program and a slower program that is interesting in someway
(but before I claim too much credit, it wouldn't be entirely wrong to
assume some of that is laziness in removing programs).
As you seem so concerned about changing specifications, let me try to
give substance to that worry - at the current rate we might predict a
changed specification sometime in early 2010.
On Dec 12, 10:46 am, Isaac Gouy <······@yahoo.com> wrote:
> On Dec 12, 1:15 am, Nicolas Neuss <········@math.uni-karlsruhe.de>
> wrote:
-snip-
> > >> [3] Especially the point that you can never be sure that your work will
> > >> not be in vain because the benchmark is removed or its specification has
> > >> been changed.
>
> > > I can more or less guarantee that a program /will be removed/ after
> > > someone contributes a faster program (or if the benchmark is removed, or
> > > if the specification is changed and the program shows Error).
>
> > Thus we can be sure that only the ugliest CL program with the uttermost
> > number of (optimize (speed 3) (safety 0)) and type declarations will
> > survive (at least, as long as it does not break for the next changed
> > specification). Thanks for making this clear.
>
> No, I'm afraid I can't guarantee that for you - there's no telling
> what good programs might be contributed, and we do sometimes show both
> a fast program and a slower program that is interesting in someway
> (but before I claim too much credit, it wouldn't be entirely wrong to
> assume some of that is laziness in removing programs).
>
> As you seem so concerned about changing specifications, let me try to
> give substance to that worry - at the current rate we might predict a
> changed specification sometime in early 2010.
And coming back to the title of this discussion "meteor puzzle" I
think I'm correct in saying that the meteor-contest currently shows
every program contributed since it began in November 2006.
Isaac Gouy <······@yahoo.com> writes:
> I'm profoundly ignorant of Lisp, so I don't really understand why it
> would be any harder to modify a Lisp program to meet modified
> requirements than it would be to modify a program written in some
> other language?
We've had this discussion before. My objection was not to changing the
spec. Change the specs all you want. It was to erasing all traces of a
fast Lisp implementation of the benchmark having existed. So *That* is
why it would be harder to modify the Lisp program. Instead the
following person to come along would then recode it from scratch,
slowly, rather than modify the existing program to match the new spec.
Isaac Gouy <······@yahoo.com> writes (in another message):
> Incidentally, I was puzzled by this part of "Juho Snellman's
> observations"
>
> > > The old fannkuch program was about 10 times faster than
> > > what is currently up on the shootout site.
>
> So I checked back into CVS and the workload for fannkuch increased
> from N=9 to N=10 (it's now N=11).
I don't see how that is relevant, nor why it would be puzzling. I'm
saying that the program that on the shootout at the time of that
writing (as opposed to "currently" as in a year after that was
written) was 10x slower than the earlier deleted one, mostly
independent of the value of N.
--
Juho Snellman
On 2007-12-11 07:44:10 -0500, Juho Snellman <······@iki.fi> said:
> It was to erasing all traces of a
> fast Lisp implementation of the benchmark having existed. So *That* is
> why it would be harder to modify the Lisp program. Instead the
> following person to come along would then recode it from scratch,
> slowly, rather than modify the existing program to match the new spec.
And the way-back machine is not particularly useful here as many of the
benchmark pages have not been archived.
<http://web.archive.org/web/*/http://shootout.alioth.debian.org>
On Dec 11, 4:44 am, Juho Snellman <······@iki.fi> wrote:
> Isaac Gouy <······@yahoo.com> writes:
> > I'm profoundly ignorant of Lisp, so I don't really understand why it
> > would be any harder to modify a Lisp program to meet modified
> > requirements than it would be to modify a program written in some
> > otherlanguage?
>
> We've had this discussion before. My objection was not to changing the
> spec. Change the specs all you want. It was to erasing all traces of a
> fast Lisp implementation of the benchmark having existed. So *That* is
> why it would be harder to modify the Lisp program. Instead the
> following person to come along would then recode it from scratch,
> slowly, rather than modify the existing program to match the new spec.
And as I noted before, your program is here:
[ #302423 ] Lisp SBCL fannkuch Juho Snellman 2005-10-26
http://alioth.debian.org/tracker/index.php?func=detail&aid=302423&group_id=30402&atid=411646
> Isaac Gouy <······@yahoo.com> writes (in another message):
>
> > Incidentally, I was puzzled by this part of "Juho Snellman's
> > observations"
>
> > > > The old fannkuch program was about 10 times faster than
> > > > what is currently up on theshootoutsite.
>
> > So I checked back into CVS and the workload for fannkuch increased
> > from N=9 to N=10 (it's now N=11).
>
> I don't see how that is relevant, nor why it would be puzzling. I'm
> saying that the program that on theshootoutat the time of that
> writing (as opposed to "currently" as in a year after that was
> written) was 10x slower than the earlier deleted one, mostly
> independent of the value of N.
I think you're close enough ~6x and that situation lasted about 2
weeks, here's a reconstituted timeline:
Mon Nov 21 2005
Notification of changed requirement
Tue Nov 22 19:54:45 2005
fannkuch,sbcl, ,7, 0.104
fannkuch,sbcl, ,8, 0.532
fannkuch,sbcl, ,9, 4.948
fannkuch,sbcl,2,7, 0.100
fannkuch,sbcl,2,8, 0.536
fannkuch,sbcl,2,9, 4.936
fannkuch,sbcl,3,7, 0.052
fannkuch,sbcl,3,8, 0.064
fannkuch,sbcl,3,9, 0.196
Tue Nov 22 23:02:58 2005
All sbcl programs show Error
Wed Dec 21 00:22:53 2005
Error fannkuch programs no longer shown
Fri Sep 15 15:28:31 2006
First new sbcl fannkuch program
fannkuch,sbcl, ,8, 0.164
fannkuch,sbcl, ,9, 1.204
fannkuch,sbcl, ,10, 12.509
Sep 29 2006, 10:26 pm
comp.lang.lisp post
Tue Oct 3 05:09:15 2006
fannkuch,sbcl, ,8, 0.168
fannkuch,sbcl, ,9, 1.200
fannkuch,sbcl, ,10, 12.493
fannkuch,sbcl,2,8, 0.048
fannkuch,sbcl,2,9, 0.100
fannkuch,sbcl,2,10, 0.640
On Dec 10, 12:21 pm, Nicolas Neuss <········@math.uni-karlsruhe.de>
wrote:
-snip-
> Hmm, are you sure you are not wasting time? Juho Snellman's observations
> in
>
> http://groups.google.com/group/comp.lang.lisp/msg/5489247d2f56a848
>
> match exactly with my shootout experience.
Incidentally, I was puzzled by this part of "Juho Snellman's
observations"
> > The old fannkuch program was about 10 times faster than
> > what is currently up on the shootout site.
So I checked back into CVS and the workload for fannkuch increased
from N=9 to N=10 (it's now N=11).