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?