[Cs5500] HSR Counting Tournament Result for avatars that scale well

Karl Lieberherr lieber at ccs.neu.edu
Fri Dec 2 10:51:38 EST 2011 

Hi Nimrod:

thank you for the results. It is great to have those results.

The reason why Ravi did not want to run the 100 000 rung challenge was that
the
testing team found problems in some history files.

To the class:

The avatars

usb     30.0 / Lukasz and Max
team2   30.0 / Nimrod and Ryan
wkn32   27.0 / Matthew Pelland
iGalaxy 27.0 /  James Antonius
TheGreatGonzo   18.0 / Dennis

get an A for the extra credit (the tall ladder challenge). Congratulations.

We are going to retire our avatars today. If you claim that your avatar
was also prepared to handle 100 000 rungs, but somehow you could not
participate in the tournament explain in your submission:

1. The features of your algorithm that make it scale well.
2. The test inputs HSR(n,k) on which you tested it and it worked correctly.

You will get full extra credit for the 100 000 rung challenge if your
algorithm
and your reasoning are correct.

-- Karl


On Thu, Dec 1, 2011 at 11:53 PM, Nimrod E. Drizlikh <nimdriz at ccs.neu.edu>wrote:

> Here are the tournament results for the 100,000 rung tournament:
>
> usb     30.0 / ??
> team2   30.0 / Nimrod and Ryan
> wkn32   27.0 / Matthew Pelland
> iGalaxy 27.0 /  James Antonius
> TheGreatGonzo   18.0 / Dennis
> baby    6.0 / The Baby Avatar
>
> The other two avatars that participated didn't actually send any responses.
>
> I also ran into the same issue as David. I am guessing that the only thing
> that is slowing down the server is the implementation of the valid
> function. There seems to be no issues for avatars to run a high amount of
> rungs.
>
> Nimrod Drizlikh
>
> ----- Original Message -----
> From: "David Richards" <dirich at ccs.neu.edu>
> To: "Karl Lieberherr" <lieber at ccs.neu.edu>
> Cc: "Ravishankar Rajagopal" <rajagopal.r at husky.neu.edu>, "CS4800 Mailing
> List" <cs4800 at lists.ccs.neu.edu>
> Sent: Thursday, December 1, 2011 10:56:09 PM GMT -05:00 US/Canada Eastern
> Subject: Re: [Cs4800] Reg: HSR Counting Tournament
>
> One quick problem I noticed with running a 100,000 rung tournament is that
> the valid function for the HSR playground
> slows down pretty drastically.  While it was taking me a fraction of a
> second to produce a 100,000 rung solution, it was
> taking multiple seconds to compute its validity.  When I ran a 1,000,000
> rung solution, it took about 5 minutes after which
> I gave up and terminated the program.
>
> The problem behind this seems to be in the use of ArrayLists.  One of the
> things valid does is produce an ArrayList of
> Integers from 0 to n-1.  It then iterates through the solution tree and
> removes the question of each node from the ArrayList.
> At the end, it checks to make sure that the list is empty.  The problem
> with this approach is that removing an item from an
> ArrayList is actually a potentially long running operation since it needs
> to shift every element in the list after the element
> that was removed.  I did some refactoring and implemented essentially the
> same solution using a stack, which is possible
> as long as we're careful to traverse the solution in the correct order
> (left, current node, right).  Since stacks are designed
> to quickly pop the top element, the runtime was reduced to essentially
> linear in respect to the size of the solution.
>
> -David
>
>
> On Dec 1, 2011, at 10:18 PM, Karl Lieberherr wrote:
>
> > Hi Nimrod:
> >
> > thank you for running the tournament. I have not been told yet what went
> wrong with the 100 000 tournament.
> > There is a danger of a stack overflow happening. A larger stack size for
> the admin and avatars might do the trick.
> >
> > I am at a loss why this was not done before. I double checked this
> morning with the graduate class and a testing team was working on it.
> >
> > -- Karl
> >
> > On Thu, Dec 1, 2011 at 10:10 PM, Nimrod E. Drizlikh <nimdriz at ccs.neu.edu>
> wrote:
> > I spent a decent chunk of time testing for 100,000 and making sure it
> would work. If anyone else is in the same boat and wants to test their
> avatar in a 100,000 rung competition I am running one on tank.ccs.neu.edu.
> It starts at 10:37pm. The tournament id is 34. I can't promise this but I
> should also have the babyavatar running in the tournament for comparison.
> >
> > Thanks,
> > Nimrod Drizlikh
> > ----- Original Message -----
> > From: "Ravishankar Rajagopal" <rajagopal.r at husky.neu.edu>
> > To: "Dennis Zografos" <dzog at ccs.neu.edu>
> > Cc: cs4800 at lists.ccs.neu.edu
> > Sent: Thursday, December 1, 2011 9:59:44 PM GMT -05:00 US/Canada Eastern
> > Subject: Re: [Cs4800] Reg: HSR Counting Tournament
> >
> >
> > No unfortunately at this point, n = 100000 setting has not been tested
> enough and therefore this will be a maxN: 1000 tournament.
> >
> > Also i request all of you to signup again at tvtennis for the MMG.
> Thanks.
> >
> > Regards,
> > Ravi Rajagopal
> >
> >
> > On Thu, Dec 1, 2011 at 9:46 PM, Dennis Zografos < dzog at ccs.neu.edu >
> wrote:
> >
> >
> > the config file for that tournament has
> >
> > hsr_config[maxN: 1000 ]
> >
> > isn't this supposed to be an n=100000 tournament?
> >
> >
> > ----- "Ravishankar Rajagopal" < rajagopal.r at husky.neu.edu > wrote:
> >
> > > Hi All,
> > >
> > > The HSR Counting tournament has been scheduled at 10.30 PM tonight at
> > > seawolf.ccs.neu.edu . I will approve signups every 5 minutes. You can
> >
> > > use the same version of the code - 76 - as you have used for MMG.
> > >
> > > Regards,
> > > Ravi Rajagopal
> > >
> >
> >
> >
> > > _______________________________________________
> > > Cs4800 mailing list
> > > Cs4800 at lists.ccs.neu.edu
> > > https://lists.ccs.neu.edu/bin/listinfo/cs4800
> >
> >
> > _______________________________________________
> > Cs4800 mailing list
> > Cs4800 at lists.ccs.neu.edu
> > https://lists.ccs.neu.edu/bin/listinfo/cs4800
> >
> > _______________________________________________
> > Cs4800 mailing list
> > Cs4800 at lists.ccs.neu.edu
> > https://lists.ccs.neu.edu/bin/listinfo/cs4800
> >
> > _______________________________________________
> > Cs4800 mailing list
> > Cs4800 at lists.ccs.neu.edu
> > https://lists.ccs.neu.edu/bin/listinfo/cs4800
>
>
> _______________________________________________
> Cs4800 mailing list
> Cs4800 at lists.ccs.neu.edu
> https://lists.ccs.neu.edu/bin/listinfo/cs4800
>
-------------- next part --------------
HTML attachment scrubbed and removed

More information about the Cs5500 mailing list