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. :blush:

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 :slight_smile:

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 :slight_smile:

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 :wink:

I invented my own ā€¦ If Iā€™ve solved it, I will ask you privatly for more details of your solution :smiley:

@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 :wink:

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 ā€¦ :wink:

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?