Well I decided to solve this and after a while I figured out its some sort of XOR + Rotation based cipher.
I just want to know if brute force is the only way to solve this or is there an actually way to solve it ?
Any tips or links would be highly appreciated. 
Is there anyone who has even solved it ?
Just so you know, sebastien guido, which is the technical recrutor in Nintendo France R&D, told me that their puzzle on codingame is their hardest.
A easiest one can be found here N.E.R.D : Nintendo European Research and Development but itās still hard.
If you manage to finish it, youāll have an opportunity to work with them, so I guess thatās why itās so hard 
You cannot do the 256-bit challenge with brute force because there are 2^256 results to test.
I didnāt solve it yet, but I found a very mathematical way generating and testing only a squared number of results (256*256).
How much of a hint is allowed?
What me helped so far, is to know about bitwise operations on CPUs ā¦
WOW Then its definitely worth a try.
I was thinking like some of these possibilities could be cut off in the starting state itself which would reduce the state tree somehow.And also threads could be used.
But in a way you are right 2^256 is probably more than the no of particles in the universe.
2^256 is 10^86ā¦ āOnlyā 10000 times the (estimated) number of particles in the universe.
But it is definitely doable without any bruteforce.
As for the question in the first post, I remember reading in some other thread that 5 people had solved it (it was back in june I think).
I did. The main difficulty is to identify the problem. Then, known algorithms exist to solve it efficiently.
No bruteforce, itās bitwise logic, your job is to desobfuscate the code to make it simpler.
As Iāve said, the link I provide is the same type of game but easier, and N.E.R.D have told me that itāll definitely help solving the one on Codingame.
By the way I got to know Codingame thanks to my application on N.E.R.D
If you manage to solve this youāll have some other tests given by Sebastien Guido to do with optimization in term of complexity (big O notation) and computation time.
Good luck 
I invented my own ā¦ If Iāve solved it, I will ask you privatly for more details of your solution 
@Plopx : did you use a ready to go algorithm, or rewrote your own ? Iām rewriting, i guess itās my way of doing things. But i did a little search to find out a ready to use one. I gave up after like 5 minutes. Probably more statisfying to rewrite. Still iām curious.
I first tried to write my own algorithm but didnāt manage to get anything useful.
Then I unrolled the encoding function, and as soon as I identified the underlying mathematical problem, I took a ready to go algorithm, using Wikipedia and Knuthās TAOCP as references.
I guess that I cannot give much more details
I identified the mathematical problem very soon but i didnāt know Donald wrote something about.
Thx so far, got something to read now ā¦
I identified the logical structure right away. Then devised an algorithm, that was okay up to ā¦ 1/8 of the smallest test case size.
Then i optimized it, and achieved good perf for up to 1/2 the smallest test case size.
Then i found out about all the litterature on how to solve it. Then i searched a bit for a ready to go in c++, but i have no patience for that sort of thing. And i presumed that it would be more āinterestingā to try to develop an (inneficient ?) own version. Maybe itās just more comfortable for me to redevelopā¦
Did Nintendo contact you plopx, after you solved the thing ?
To be clear, thatās what Iāve done: I took the algorithm description and wrote my own C++ code.
No, since I solved this puzzle for fun only.
[quote][quote]Did Nintendo contact you plopx, after you solved the thing ?
[/quote] No, since I solved this puzzle for fun only.
[/quote]
Is there a pop up that appears so that you can choose to be contacted or not ?
Just like Teads if you have done it, after validating you have a pane where you can choose to send them your code, together with some contact info, CV, etc.
I chose an algorithm at random, and ran into model size trouble. I really should have though about testing the implementation on a real sized one ! >_<
One interesting phrase about all this is this one
The general case is NP complete. (If i understand correctly). Well to be fair, the nintendo one isnāt the general case, thatās for sure. Still i wonder on the ārightā way of solving it.
And thatās wondering whatās the highest size that can be solved within the 5 allocated seconds on the coding game server (well, iām still lacking a way to pass the so called 32 bits sized test cases, but well).
Edit : So the question is thus -> How long does it takes your algorithm to solve the official test cases (letās say at least one of the biggest) on the codin game server (if you use more than one thread, please say so)
Iām pretty not sure that it is not NP-complete, though it is not known to be in P either.
The sentence you quote does not state that your implementation should not be able to break all problem instances, just that other implementations may be more efficient on specific instances.
I can answer your question too, my implementation takes 830ms on the 256 bits test. There is no multi-threading, and more generally my C++ āimplementationā is not optimized in any way. Others who have solved it will definitely have more impressive timings to show.
At last I made it! 100%
Canāt believe Iāve passed this! For performance Iām on 800ms on the last test like @thibaut_verron I did spend some time optimizing but Iām not an expert of C++ at all. My solver is recursive but I think it might fall into the category of ātail-recursiveā Iām not sure.
I took the algorithm from the description as well, pasted it into the editor and tried to run it, see if I get the results from their out.txt file, which I didnāt. Is that the way itās supposed to work? Do they have an overloaded operator in there or something?