Nice. Despite its name, submit.py does not send your result to the leaderboard. You need to go to the codingame IDE, and hit the Submit button. The solution found offline should already be there, in “PHP” (just the text of the solution).
Do I need to do that after every puzzle, or just the last one that I get to?
Just the last one.
As an explanation why it is the way it is:
there is a submit limit, after 4 submits in a short time you have to solve captchas first. There are limits for testing in the IDE too, but these are much less strict. On top of that you can watch an IDE replay in your browser, while submit replays are hidden.
Hi, after submit the first level, the “next step” button send me out to profile page…
I found the code : it is in the console
I changed to something similar to Westicles. I used Late Acceptance Hill Climbing instead of Simulated Annealing, but the idea is just the same.
1- Create a candidate solution, based on a previous accepted solution, changing little things (removing some Moves, truncating list of numbers, etc) 2- Score it, based on some objective. I picked reducing both numbers in the grid and total sum of these numbers 3- Based on the LAHC algorithm, accept it as a new accepted solution or discard it. 4- Goto 1, Rinse and repeat until you have a real solution with 0 points and no numbers in the grid. I reset the attempt after N seconds.
Dancing Links limit is around 230-250. LAHC limit for me is around 330.
So if you need to pick an option, SA or LAHC is best, simpler and gets you a bit higher.
Thanks for sharing. I also switched to SA and my current implementation can take up to two hours to find a solution around level 220 which is too much. Theoretically I can leave it run all the time but I think at the current rate it is more of a waste of energy. What time does your LAHC take around level 330?
How does LAHC work? Can you sketch it if you have time? I presume it is simple enough but it is explained in a more complicated way in the article.
That’s some sketch, with some omitted parts. Some levels can be solved in minutes, others in hours.
Some levels around 100-200 can be solved with that sample code in less than 1 minute.
At 335 I just stopped trying, it was well beyond 4 hours without finding a solution.
LAHC is like SA, random search after all, it depends on the luck + degrees of freedom of the map itself. If there are little solutions, you’ll have a hard time.
EDIT: In level 225 with Dancing Links I needed 6318secs, with 4 cores. I have used LAHC on it again and it took 490secs. Both solutions were valid but very different (18 groups of numbers vs 10 groups)
I have launched LAHC with the command “./NumberShift_LAHC 15 4 < level.txt”, resetting the search each 15 seconds because it converges fast to little numbers (there is no point on wasting too much time once you have like 2-4 numbers left).
Thanks for the reply. I found the paper on LAHC and from what I get from it LAHC compares the cost of the candidate solution not to the current best as HC does, but to recorded solutions from previous iterations, thus from time to time accepting worse solutions similarly to SA.
Is the parameter of the model the number of iterations back that you compare to?
If I got this right I might give it a try.
Yes, you have a vector of Scores, with size “Lfa”.
Then you accept a candidate
if (candidate.Score >= lastAccepted.Score || candidate.Score >= vector[ I ].Score)
And then you always update vector[ I ].Score = lastAccepted.Score;
so you can accept worse solutions, but over time it converges.
The only parameter is the vector size (Lfa), it defines how fast it converges. Lfa=300 means a fast convergence, with worse results due to local maxima. What I do is to use a small Lfa and when I’m reaching some % of numbers completed I increase it. I don’t see much interest on accepting worse results early, there is too much room to mutate.
I see. How do you determine the value of I - the score of I iterations in the past?
ps: I got it - it depends on the iteration number and the size of the scores array.
Yeah, I think it was vector[ v ] and not I, but the same idea.
v = I mod Lfa; ++I;