[Community Puzzle] Number Shifting


#21

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).


#22

so confusing :slight_smile:
Do I need to do that after every puzzle, or just the last one that I get to?


#23

Just the last one.


#24

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.


#25

Hi, after submit the first level, the “next step” button send me out to profile page… :roll_eyes:
I found the code : it is in the console :smiley:


#26

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.


#27

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.


#28

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).


#29

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.


#30

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.


#31

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.


#32

Yeah, I think it was vector[ v ] and not I, but the same idea.
Each loop:

v = I mod Lfa;
++I;

#33

yes, thanks.


#34

Hello, could someone clarify, is it supposed that each level up to 500 can be solved under 800 ms?
As I see from posts above some people have spent minutes/hours to find level solution, or these results doesn’t affect leaderboard?
Thanks!
@eulerscheZahl


#35

The idea is to solve the levels offline and play your solution on the CodinGame website to get the next level.

Let’s play the following PHP code (in PHP you don’t need any print-command, that’s why so many players on the leaderboard use it):
image
Now have a look at the output below the viewer:
image
There you have the next level, ready to copy-paste to your local environment.
Run your offline solver on it, paste the solution back to CodinGame and get the next level again.

There is a script to help you automate that copy-pasting to get the next level.
Depending on your python knowledge I would recommend to copy-paste levels by hand at first to see how fast runtime explodes. You won’t get far without a sophisticated solver anyways :wink:


#36

Ah, so it’s ok to hardcode solutions on CodinGame website for each level when submitting code for leaderboard, even all of them actually solved locally?


#37

Yes, you are supposed to hardcode here.
This game is quite different to other optim games on CodinGame.


#38

This is the way.

It sounds so simple. I’ll give a couple more hints (no spoilers) below.

I have struggled to follow it, trying to be sophisticated with hashes and what not (in Python and C++).

After all, this is all about randomly exploring the move space, with some hints like they come from annealing (although I’m not so sure about the theory of this – pruning moves does not exactly result in a “neighbour”).

My advice: CPUs are fast, RAM is slow. Write something that fits in the CPU cache – sophisticated hashing schemes etc. won’t. You can only control this with natively compiled languages like C/C++/Rust and so on.

I only feel confident about this because my small-scale C solution cracked level 61 (particularly hard one) in a reasonable time. I don’t think this was just luck, but let’s see…

Anyway, I thought this might be helpful w/o spoiling things.