current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote 0 down vote favorite
1

There is a secret code, 12 characters in length. Each character can be either a number or a letter. Every two hours, a random character in the secret code is revealed.

For example:

Hour 2:

_ _ Q _ _ _ _ _ _ _ _ _

Hour 4:

_ _ Q _ _ _ _ _ _ _ 4 _

Hour 6:

_ _ Q _ _ _ _ 7 _ _ 4 _

Hour 12:

1 C Q 8 2 V V 7 J B 4 9

You (your program) is allowed unlimited guesses. Write a program to solve a secret code like this.

What does your program do when another hour goes by and another secret character is revealed?

[Let me know if you have questions. I've never written a puzzle before. :S]

share|improve this question
4  
My understanding is that we're supposed to assume that we have a single-threaded computer which runs at an unspecified but fixed number of operations per second and that we can work out precisely how many operations our code will compile into, that there are no memory caching issues to take into account, and that we need to calculate the cutoff at which we can guarantee that the exhaustive search will complete in a fixed time. Is that correct? Because if so there are a lot of details missing about the precise architecture model. –  Peter Taylor Sep 16 '11 at 10:56
1  
Tentative rewording to see if I've got it right. We are to write a program that writes 36^12 strings of alphanums to standard output, waits for the end of the hour, writes the 36^11 remaining strings, waits for the end of the hour... after twelve hours it just displays the only remaining string. I don't quite see where the time complexity and earliest hour come into play. –  J B Sep 16 '11 at 11:07
1  
@Peter Taylor: reading the whole thing again, your rewording seems like a better fit. –  J B Sep 16 '11 at 11:35
    
Yes, @Peter Taylor. :P –  Melanie Sep 17 '11 at 2:18
    
every two hours vs. when another hour goes by and another secret character is revealed? - 1 or 2 hours? The list suggests 1 hour too. –  user unknown Sep 17 '11 at 3:17
show 3 more comments

1 Answer

up vote 3 down vote

Assuming it takes a millisecond per guess and we're using only uppercase letters and numbers, guessing the correct code with 11 absent digits is in the worst case scenario 36^11 milliseconds or 4173696.8 years.

Generalizing a bit, the problem becomes how many slots we'd need filled so that you could be able to solve the code using brute force in under an hour. So when is the following true solving for x (g represents guesses per second, which I'll assume is 1000):

36^x < 3600 * g

Though it's slightly more complicated than that, since after each hour, you're told the value of another digit. If you started over from scratch, you'd have this formula as best case scenario, though I think you can eliminate a fraction of the solution scope given that you've might have explored some of the solutions including that digit. Though worst case scenario is that you didn't and so the above would be the solution.

share|improve this answer
    
I don't understand why this is upvoted, and not a comment. But can you tell me, how do you know that you solved something? Solved what? –  user unknown Sep 21 '11 at 2:46
1  
@user: I think you're assuming this is a traditional code golf problem where you have to write code for your solution. This is more like a math problem in nature, so the solution then becomes mathematical in nature. –  Neil Sep 22 '11 at 12:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.