Newsgroups: csh.general
Subject: Re: Programming Contest #1 -- Array Runners
Summary: 
Expires: 
References: <387cca6d@news.csh.rit.edu> <387ce064@news.csh.rit.edu> <387cf52b@news.csh.rit.edu>
Sender: 
Followup-To: 
Distribution: csh
Organization: Computer Science House, Rochester Institute of Technology
Keywords: 
Cc: 

An alumni mailed me to say:
>For a fairly short description.... That seems to be a really neat problem....
>I see you have not made any limits on the sizes which is nice.

    *nod*  Actually, I don't know if you mean on size of
    program or size of array.  But, yep, I fully intend to
    run stuff against several sizes in an attempt to keep
    people from training hard on a particular array size.
    And, limits on the size of the program... well, I don't
    want to have to huck around 300M source code, I figured
    the month time-limit would take care of most of that
    problem.

>The path length penalty is what makes the problem really interesting.

    *nod*  I think the path-length penalty is a bit
    high, but I didn't want to mess with
    floor( path_length/3 ) or anything like that.

>I think you should ask all entrants to supply a test case for all other
>contestants to be run against.

    That's interesting....  I was just planning on generating
    test cases out of Project Gutenberg, but I suppose some
    craftier ones may be of interest.

    [If you want to supply a test case, cool... but I'm not
    requiring it.]

>The judging criteria is also nicely vague.

    Bah... the ``highest score'' is pretty objective as
    long as I don't hand-pick the arrays to my
    algorithm's advantage (hence the Project Gutenberg
    approach).

    [ At the moment, it looks like Boba, Jerry, Scoot?,
    and myself will be doing the ``Slickness'' and
    ``Maintainability'' judging.  Any programs we
    submit to the contest won't get judged under those
    categories. ]

>Are there Alumni Divisions/Current Student Divisions, or just
>one big pot?  If you have enough interest for the contest for that.

    I decided to make a ``Beginner'' class for the
    ``highest score'' prize, but you don't qualify.
    8^)

>I like the fact that
>
>puts("ES");
>
>is a solution (and I could make a case that is the most maintable one
>since it is the simplest. even though it doesn't to a particularly nice
>job of getting a good score....)

    *nod*  I could make that argument, too... but I'd also
    argue that making incremental improvements to that
    code is even worse than if it had been a random walk.

>These test cases came to minde while thinking about the problem...
>
>5 5
>ABCDE
>BCDEF
>CDEFG
>DEFGH
>EFGHI
>
>9 6
>AZAAAZYXW
>AZAZAZYYY
>AAAZAZZZZ
>ZZZZAZAAA
>YYYZAZAZA
>XXYZAAAZA

    *nod*  I had thought about the 9x6-ish version except
    I'd have extended the first bit of the path down further
    or the last bit of the path up further to make it advantagous
    to make a reverse-alphabetic move:

9 6
AZAAAZYXW
AZAZAZYYY
AZAZAZZZZ
AZAZAZAAA
AZAZAZAZA
AAAZAAAZA

    And, I really like your 5x5, but I can't really see it
    separating the chaff from the wheat.... ES and SE tie...
    and all combinations of four E's and four S's tie....

>Can I submit multiple entries for each category.  I.E.
>Is it the programs that compete, or is it the programmers?

    It is the the programs that compete.  Again, I'm hoping
    the month time-line will keep me from getting blitzed.
    I may put an arbitrary upper-bound if people submit
    154 copies of the same basic program with slightly
    different weighting factors.

    And, you don't have to submit code under a category...
    your code will automatically be judged in all three
    categories.

>I will submit something trivial at least, so that there is
>some entry from me.
>
>Too neat of a problem to not do something....

    Cool... that's the way I feel about it, too.... I'm
    obviously not going to plop my program into the
    judging of ``slickest'' or ``most maintainable''
    as I'll be one of the judges, but... I still intend
    to compete for the high score.

>What got you thinking about this problem? (unless that
>would give too much away about solutions)

    I'm working on a different contest altogether.
    But, the other contest requires me to get a server
    up and running before people can write competing
    clients.  So, I needed a problem that wouldn't need
    a ton of apparatus for me to get underway.  My
    first thought was a simple maze-problem.  But,
    mazes are well-understood.  One other thought was
    peg-solitaire.  But, I misread some of HACKMEM to
    imply that peg-solitaire was easily solvable, so I
    avoided that problem.  I also thought that with
    peg-solitaire, there'd be too harsh of a line
    between the best solution and no solution.... there
    wouldn't be a whole continuum of places where one
    could say... ``well, I think that's good enough to
    beat everyone else's programs''.  So, I munged on
    the maze concept a bit until I came to arrays, ran
    it by Jerry, we tweaked some of the scoring a bit
    and the details of the rules (I was thinking of
    disqualifying programs that stepped out of the
    array, but I like the bouncing off of edges
    approach much better (esp.  since it means that
    ``ES'' navigates every array)).

    I have no more in mind for solutions than anyone
    else at this point.  *shrug*

    It just occured to me that the Project Gutenberg
    approach may be biased (unless I advertise it
    quickly) because letters will have the frequency
    they have in written English.  If one knew the data
    set were to be derived from written English, one
    could train that-a-way.

    [ At least one of the input arrays for the judging
    will be derived from English text retrieved from
    Project Gutenberg's 1991 collection. ]

    alter,
    pat