I’m aware of the issue.
This happens when you solve too many levels in a single run, as the SDK assumes 50ms for each line you print. I can partially solve this issue by reading multiple lines at once, but not solve it completely.
Replace the “first_level” by the last password from the game output to start at higher levels.
At some point you won’t be able to solve a map within 1s anyways, so you are supposed to solve it offline and submit the password along with your hardcoded solution in order to get the next level.
Hi everybody, funny how long it can take to solve a puzzle for such a little grid! The first levels were quite immediate then it took me hours for level 19. I was wondering if my program would ever give a solution or had just died.
I surely need to optimize, but apart from ordering the possible moves (I try minus moves toward big numbers first and plus moves towards big numbers last) I dont’t see. Any clue? Early detection of position with no solution?
I suppose it is because if php script does not start with <?php , then the php interpreter simply echoes the source to output. The legacy of being designed as a server-side dynamic HTML page-generation language.
Some people had succes doing GA with mutation, or some other approaches that I don’t know (Westicles for example).
Others divided the problem on smaller ones, and treated it as an Exact Cover problem.
Premises:
-A number can only be used once.
-You know that a solution is when all numbers are removed. That is equal to a set of numbers that ends in a zero (you subtract a number X to another X, reaching a zero).
With these two premises you can infer that a solution probably are N sets of numbers, each set reaching a zero. The problem then changed from getting an precise move list for all numbers to find enough zero-sum sets that can be combined to cover all numbers once and only once (exact cover problem).
This approach is good in most levels below 200. Except a few hard levels most of them are solved in minutes, not hours. Above 200 the size increases a lot and the exact cover problem begins to be intractable.
Oh I see (or pretend to). If for example I find a set that ends with zero, I now have to solve a smaller equivalent problem. The first simple approach is to privilege moves that end with zero. Let’s see…
1-Do a lot of random moves, until you can’t move anymore. If you ever find a zero-sum set save it if you don’t already have it. Zero-sum set must be the precise list of moves to reach a 0, not all moves you did. You need to track where do you “send” each number.
2- Restart the map to the original state and repeat a lot of times the first step. Well, the basic MonteCarlo.
3-Once you have enough sets, try to find a solution. With all the zero-sum set you have, use some algorithm that solves de exact cover set problem (cover all numbers once, and only once). If you fail to find a solution, return to 1.
Some advices:
It isn’t a simple game at all, to reach higher levels it requires a lot of pieces and some patience. I ended with MonteCarlo, mutators, DLX Solver, load/save states to file, hashing, unordered sets, threads and a miriad of trials and errors. I think that I have more code that in some multiplayer games.
It’s better to hash the sets with only the numbers used, it dosen’t matter the order or the move itself, that speed up the search of a possible solution.
Some maps are noticeably hard, more than others, like 61, 100 or 138.
It’s hard to tell how many sets you need to solve a map, sometimes a couple of seconds of MC is enough to find a solution, other harder maps can take hours between MC and exact cover search.
Dumb question - but how do I progress in this?
Using ‘submit’ gets me to level 11, but I see no output or guidance as to what I succeeded or failed at, and I have never done offline submissions (but would be happy to try if it can be automated)
There’s a ‘next step’ button, but that doesn’t do anything useful
Not dumb, this mechanics is rather special. If your solutions are correct, at some point you just fail from running out of time. If you look at the console output when you play a test, you should see a “Code for next level: xxxx”. If you copy paste xxxx and print it in your code (instead of “first_level”), you will play from that next level on.
To automate this or to go to levels where you need more than 1 second, there is the submit.py script in the linked github repository.
I’ve successfully completed up to about level 23 using the offline tool - but the leaderboard still says level 11 - like it’s being overridden by the value from the tests on the site
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).
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.
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.
