Project Euler Forum

Hi,

Can it be solved in less than a minute?

And do I have to use random function to solve it?

Thanks!

You've been around long enough, axelbrz, to know not to expect an answer to that sort of question!

It can be solved in less than a minute as almost every problem can. But that's a given.

okss! lol I'll try to solve it!

Thanks!

In the example for the 5 digit problem, the guesses hit all 5 of the digits. Can we assume the same for the 16 digit problem?

When you assume something, you risk being wrong half the time.
So, try and find out.

LarryBlake wrote:In the example for the 5 digit problem, the guesses hit all 5 of the digits. Can we assume the same for the 16 digit problem?

I don't recall exactly, been a while, but I do remember it was deterministic... i.e. only one answer.

Half? You think highly of me.

quilan wrote:I don't recall exactly, been a while, but I do remember it was deterministic... i.e. only one answer.

Problem 185 (View Problem) reads:

Find the unique 16-digit secret sequence

Thanks. I understood that there was only one right answer. My question was, are all 16 of the digits mentioned in the guesses, or do I need to consider every digit as a possibility in each position (except where I can logically exclude them)?

I understood your question perfectly.
That's what you have to find out.

Okay.

Are you going to change your signature next year?

Yes, into 7×7×(7×7-7-7/7)+⁷log(7)

is there a fast algorithm for this problem ? (polynomial time)

No, this problem is NP-complete.

Wow, this was hard. After many different attempts, I finally got it, and not under 1 minute either.

Really nice problem.

zwuupeape wrote:No, this problem is NP-complete.

If I read the definition of NP-complete correctly, a problem belonging there does not mean there is no polynomial time solution... It just means that if there is one, there is a P solution for every problem in NP. The proof or disproof that NP-complete problems have no P-time solutions, however, is still unknown to man.

The way I understand, he asks if such an algorithm is known, not if it could exist in theory. No algorithm that solves any NP-complete problem in polynomial time is known to exist. The more interesting question is, of course, if the problem belongs to that class. The answer is yes, because - at least as I read on the forum and confirmed online - the game of Mastermind is NP-complete and this one is the same except you have less information.

does leading zeros allowed at the "secret sequence of digits" ?

Find the unique 16-digit secret sequence

A sequence of digits is requested. Since 0's are allowed as digits, they could appear anywhere in the sequence. Consider the digits as different colors.