[Cs4800] Reg: HSR Counting Tournament

[David Richards]

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