[Community Puzzle] Number Shifting

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.

The second level code doesn’t work :frowning: Is there anyway to fix it?

Works fine for me.

As I wrote above, solving the first level will give you a password to enter the second one:

So that’s how level 2 looks like:
image
And some code that solves the level:

pmkhklcgypoivqgfzyyuvmtsywegacwu
4 2 D -
4 4 L -
0 4 R -

The first line is the level code to tell the system which level you want to play and to confirm that you’ve solved the previous ones. The following lines are the actions to solve the level.
Running this solution on CodinGame will then give you the 3rd level.

If your program is fast enough, you can solve multiple levels at once, just reading the next level from input and solving it online.

1 Like

I tried printing the second level code but it doesn’t work :cry: :cry: :cry:

Did you try printing exactly these four lines and nothing else? It works for me.

Yes and it doesn’t work

Strange. It works here.

Thanks for this optimization problem! I find it very fun to try to solve it: simple rules, a lot of progression (1000 levels), large search space, and a nice helper script to get started. Since it’s designed to be run offline, it’s easier to explore and develop optimization techniques: I can simply run the program in a debugger to understand what’s going on, where the search is stucked and why.

As suggested Marchete, I tried a LAHC algorithm, but simpler to what is proposed in Marchete’s github. I was quite surprised that a basic version of LAHC + multithreading could lead me to level 95. Looking at the leaderboard, I understand that I still have a lot of things to learn ^^.

5 Likes

Hmm, I’m stuck at level 6, getting a timeout error.
I test my solutions directly on the CodinGame website and the timeout occurs while reading the input for the level.

This puzzle is a bit different, the idea is that you solve it offline on your own IDE, then go to CG and paste your solution.
You can automate the process if don’t want to manually paste everything.
But the allocated time on CG’s IDE is very short on purpose so you won’t go far if you stay on CG.

Yup, solving it offline works, although it remains strange that the allocated time isn’t enough to just read the input.
And boy does this puzzle get out of control fast :smile:

I don’t know which language you use to get the input but for example with Python you can just do that:

print("your access key here")

_, h = map(int, input().split())
M = []
for _ in range(h):
    M.append(list(map(int, input().split())))

print(*M, sep=",")

Then you can just copy/paste the input in [ ] and you get a nice matrix to work with.

For anyone wondering, this is the last level (1000):

I’ve solved it and all I got was this lousy error:
Broken
So it’s unsolvable and the max score is 999. It’s a Pac Man-like ending, it’s OK.

Someday I’ll write a PM, it was a truly journey reaching it.

10 Likes

Information about my approach:

It gives a lot of information and source code. Code is not directly compilable, it needs some code fixes, someone with C++ experience can fix it easily. The idea is learn from it, not simply C&P.

Key points are:
-Use Merge a lot. This reduces a number without breaking anything.
-Use exhaustive permutation of ending moves on good candidates. Try to reach a 0 by itself or be able to merge on another intermediate value on a neighbour. The problem is that permutations are really expensive.
-Priorize performance on random move generation. Minimize smart moves at that point, add them on the Mutation part, choosing more prospectable Moves to mutate. Performance per thread matters, a CPU running 200% faster than other 4xCPUs solved 90% of the 900+ levels.
-A physical corei7 with 6 cores can do 10threads without bloating the whole PC (you can do normal work while running the solver), vCPUs on the cloud are usually worse. With 6 threads you can even play 3D games at 144hz without noticeable slowdown.
-Use good mutators. Not only randoms, but ending points, incompletes numbers, etc… One mutator I have that is based on ending moves affecting incomplete Strategies achieved 50% of good candidates.
-Keep a pool of good approximations (=low remaining numbers), no matter the score, allow worse candidates as long as remaining numbers are below a threshold. LAHC failed a lot on endgame, it lost many near solutions because my Mutators were unable to exit a local minimum, and LAHC hasn’t any further protection against that, you can only reset the whole search.
-In that pool, ensure that candidates are unique. Don’t accept repeated candidates with the same remaining numbers, replace equals if the new candidate has a better score. Check/remove supersets (a candidate with the same remaining numbers than an existing candidate but additional remainings).

7 Likes

I’m kind of curious why you would publish something that can reach 999 with 10 minutes of easy code fixes. Seems a shame to spoil such a nice problem.

2 Likes

I understand your point of view, but I also shared a previous version of a LAHC solver a year ago, the main difference between both is that the previous one only reached lvl 330. I haven’t seen a massive amount of people reaching levels 200+, only hardcore/crazy codingamers went to higher levels.

It’s not a simple C&P from github to CG IDE. This puzzle needs a lot to setup, configure and run, and the naive copypaster won’t do all that. Besides that level 932 can’t be exported due to stderr limits, you need more tweaks to extract it.

My postmortem will be interesting to 6-7 people, at most. I usually find that most papers about a subject are too broad, and give results without a real support of their statements. I prefer seeing code and see how it’s done

5 Likes

Could you please check if solver still works?
What is 01234… in
session.cookies.set('rememberMe', '01234567-0123-0123-0123-0123456789ab', domain='codingame.com')

userId = 1500515
As on profile address it’s much longer and in hex format.

r = session.post('https://www.codingame.com/services/Puzzle/generateSessionFromPuzzlePrettyId', json=[userId, "number-shifting", False])

handle = r.json()['handle']

I cannot get handle, and session.post() throws 422 error.

Let’s have a look at the full line of code including comments:
session.cookies.set('rememberMe', '01234567-0123-0123-0123-0123456789ab', domain='codingame.com') # change the cookie value, see https://github.com/s-vivien/CGBenchmark#how-to-grab-your-accounts-rememberme

You have to extract your session cookie as Neumann described in detail.

Your userId is 3657937 and will always be for this account.

I just did lvl 19, my program explored 821,782,575 nodes before dropping an answer. Took about 100 minutes. I was like wth.

What about my userID? How can I get it? Is your script working at present?
Thanks for this optimisation problem.