Problem 185

axelbrz · Post by **axelbrz** » Sun Jun 07, 2009 10:01 am

Hi,

Can it be solved in less than a minute?

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

Thanks!

ed_r · Post by **ed_r** » Sun Jun 07, 2009 11:00 am

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

LarryC · Post by **LarryC** » Sun Jun 07, 2009 11:58 am

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

axelbrz · Post by **axelbrz** » Sun Jun 07, 2009 8:51 pm

okss! lol

I'll try to solve it!

Thanks!

LarryBlake · Post by **LarryBlake** » Thu Sep 17, 2009 8:21 pm

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?

hk · Post by hk » Thu Sep 17, 2009 8:43 pm

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

quilan · Post by **quilan** » Thu Sep 17, 2009 8:45 pm

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.

LarryBlake · Post by **LarryBlake** » Thu Sep 17, 2009 8:46 pm

Half? You think highly of me.

stijn263 · Post by **stijn263** » Thu Sep 17, 2009 8:48 pm

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

LarryBlake · Post by **LarryBlake** » Thu Sep 17, 2009 8:55 pm

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)?

hk · Post by hk » Thu Sep 17, 2009 8:59 pm

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

LarryBlake · Post by **LarryBlake** » Thu Sep 17, 2009 9:02 pm

Okay.

Are you going to change your signature next year?

hk · Post by hk » Thu Sep 17, 2009 9:03 pm

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

Georges · Post by **Georges** » Fri Oct 02, 2009 7:22 am

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

zwuupeape · Post by **zwuupeape** » Fri Oct 02, 2009 10:11 am

No, this problem is NP-complete.

LarryBlake · Post by **LarryBlake** » Wed Dec 23, 2009 2:14 pm

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

Really nice problem.

Lord_Farin · Post by **Lord_Farin** » Wed Dec 23, 2009 6:36 pm

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.

zwuupeape · Post by **zwuupeape** » Wed Dec 23, 2009 6:53 pm

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.

elr · Post by **elr** » Sun May 22, 2011 2:22 am

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

rayfil · Post by **rayfil** » Sun May 22, 2011 2:45 am

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.

Project Euler Forum

Problem 185

Problem 185

Re: Problem 185

Re: Problem 185

Re: Problem 185

Re: Problem 185

Re: Problem 185

Re: Problem 185

Re: Problem 185

Re: Problem 185

Re: Problem 185

Re: Problem 185

Re: Problem 185

Re: Problem 185

Re: Problem 185

Re: Problem 185

Re: Problem 185

Re: Problem 185

Re: Problem 185

Re: Problem 185

Re: Problem 185