This blog no longer exists.
You will be redirected to something cool.

Monday, December 24, 2012

Secret Code Programming Puzzle

I'm trying to solve a mathy programming problem. (I came up with the problem a couple of years ago, but it's still preying on my mind.)

There is a secret code (which you're allowed unlimited guesses at) => a string 12 characters in length. Each character can be either a number or a letter (a-z, 0-9) and it's not case-sensitive (A == a).

After every hour, a character in the secret code is revealed.

For example:
Hour 1:
_ _ Q _ _ _ _ _ _ _ _ _

Hour 2:
_ _ Q _ _ _ _ _ _ _ 4 _

Hour 3:
_ _ Q _ _ _ _ 7 _ _ 4 _

Hour 12:
1 C Q 8 2 V V 7 J B 4 9

I want to write code that solves the code before a human can. I figure a human can realistically start manually entering combinations at around hour 10. I would like my program to solve it before then.

What should the program do when another hour goes by and another secret character is revealed? I was thinking of starting out with an array of all the possible combinations, but populating and storing the array would take an immense amount of time and resources. I was thinking about storing this array and when a new character is revealed, rejecting ALL strings from the array that don't have the new secret character in the exact position.

At a worse case scenario of making guesses with all 12 characters left unrevealed, we're left with awful time complexity:
36 numbers and letters, 12 mystery characters
36^12 == somewhere considerably longer than I have remaining in my lifetime given however long it takes in a single-threaded program to make a guess. Still too long in a multi-threaded program on the world's best computer.

However, this goes down significantly after each hour. So I have several questions to answer:

Should I start my program at a certain hour? If so, would there be any benefit to at least STARTING to populate an array before said starting hour? Would I even need to populate a massive array?

1 comments:

Why populate an array to iterate over in the first place? The problem space is enumerable and ordered.
Consider looking at a Generator (python) - for example a prime number generator. This is a problem of list permutations (perl List::Permutor) with a narrowing search space as time progresses.