159 Hard Life confirmation
Back to Problem Solutions forum
Hey,
I need a bit of information on the #159. I'm doing it in Java, however I believe that I'm just making a stupid mistake somewhere in the algorhitm. The problem is that I get correct results when trying out the example input, but every time I try passing the results of the actual task, I get the 'incorrect number of generations' message. I tried using a 2000x2000 grid and 3000x3000 grid to see if that's the reason, but the results are always the same.
MoffSerge, Guy Gervais, Rodion - any chane you could verify if a grid of 2000x2000 is enough for the task, when the input numbers are e.g.~ -100, 100? The 0,0 of the Acorn is placed in the middle of the grid (so, x1000, y1000).
Some of my lesser input data (e.g.~ -40, 30) stabilized in about ~400 generations. So, assuming that the X and Y colony values move closer to 0 and MAX values of the grid with a tempo of 1 per generation, it should not reach 0 or MAX in only 400 generations.
Is there a diffrent message if the values are correct, but the time is over 1 min? My code checks the 2000x2000 in about 1:30 min, however the answer is usualy found in ~40s.
Maybe there could be a different example, like -50, 50, which would not show up in the input data? Rodion, are there any more starting points you could provide as an additional example verification?
From what I understand, the answer should be the number or the first generation, when the stabilizing really occured, not when it has been spotted, and the counter starts at 1, not at 0.
I'm not marking this as private, since there is nothing to spoil here, as I haven't solved it yet.
Cheers!
> any chane you could verify if a grid of 2000x2000 is enough for the task
Hi! Thanks for your question!
I think you can try to analyze whether the game reaches the edge of such matrix - i.e. whether the "edge-effects" may cause the mistakes. I have no ready answer since I did not perform such an analysis - however most of cases require more than 3000 generations so the edge may be easily reached, I suppose...
However the idea of this task was to make you switching to algorithm which will not use the matrix and so will not have limits :)
Thanks for the reply. It really convinced me, that my lazy approach would not be enough for such a high task number. Got it now!
@Admin : did you choose the title "Hard Life" on purpose ? is it a hint for a particular complex very difficult algorithm I think for ?
> did you choose the title "Hard Life" on purpose
Yes it should suggest that probably the basic "on-matrix" approach used in the "Life is Simple" would not work there (because processing too many empty cells is ineffective). It is hard to judge whether supposed approach is "very difficult". Probably for you it would be easy enough... :)
BTW, if you really want to hang "certificate" on the wall, feel free to e-mail me so I can send you hi-res copy :D
Well, I tried a script which process only living cells and neighboors, but it takes 80 seconds for 1000 generations. May be I'll try to learn C++ to do the same more rapidly. Otherwise I was thinking about the Hashlife, which I find very hard !
> Well, I tried a script which process only living cells and neighboors, but it takes 80 seconds for 1000 generations.
Probably this depends on what storage type you have chosen for these living cells. Do you store them as tuples in the set (or dictionary keys)?
The main trouble here is to find neighbors of the given empty cell fast - either hashing or sorting by one of coordinates should help...
Good day! My solution does not contain arrays, runs within 10 seconds and gives the correct answer in the case (-5 5). However, on the test I get a stable answer "Number of generations is incorrect!". Tell me in which direction to look for an error.