# Nintendo Challenge

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 ?

1 Like

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

1 Like

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.

1 Like

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

2 Likes

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.

2 Likes

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.

1 Like

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?