Lock Hack Problem

Velocirapture

United States983 Posts

September 17 2015 18:50 GMT

Recently during an interview process I was given a series of question and asked to give the best answers I could. I am allowed to consult anybody I wish and thought it might be fun to post it here. The questions are supposed to be hard and draw on a wide variety of specialties. This is the one that I don't know how to start.

You are given a lock with 4 letters (A,B,C,D) as input options and a 3 letter code. Order is important and repetition is allowed so obviously this means you have 64 permutations as seen below.

{a,a,a} {a,a,b} {a,a,c} {a,a,d} {a,b,a} {a,b,b} {a,b,c} {a,b,d} {a,c,a} {a,c,b} {a,c,c} {a,c,d} {a,d,a} {a,d,b} {a,d,c} {a,d,d} {b,a,a} {b,a,b} {b,a,c} {b,a,d} {b,b,a} {b,b,b} {b,b,c} {b,b,d} {b,c,a} {b,c,b} {b,c,c} {b,c,d} {b,d,a} {b,d,b} {b,d,c} {b,d,d} {c,a,a} {c,a,b} {c,a,c} {c,a,d} {c,b,a} {c,b,b} {c,b,c} {c,b,d} {c,c,a} {c,c,b} {c,c,c} {c,c,d} {c,d,a} {c,d,b} {c,d,c} {c,d,d} {d,a,a} {d,a,b} {d,a,c} {d,a,d} {d,b,a} {d,b,b} {d,b,c} {d,b,d} {d,c,a} {d,c,b} {d,c,c} {d,c,d} {d,d,a} {d,d,b} {d,d,c} {d,d,d}

Now here is the challenge. The lock does not track a registry so an input of AAAB counts as both AAA and AAB. Given this information I need to find the shortest possible string of inputs that includes all 64 permutations.

I am not a programmer so I would love to know if there is a conventional logic to finding the solution rather than brute forcing it computationally.

Sn0_Man

Tebellong44238 Posts

September 17 2015 19:30 GMT

Rules for maximum efficiency:
1)Each attempt should borrow the last 2 letters of the preceeding permutation
2)Each pairing can only occur 4 times (after using *BC, we can only repeat BC three more times)

if we can find a string that follows those rules, we achieve a 66 letter string that will open the lock. I'm assumign the rules are possible but I'm not certain. While there *must* be options (since swapping A and B in all instances produces a different string with the same result) I'm not sure that there are meaningfully different ones (aka truly different orders).

an attempt where we start with AAA and choose the next letter in the sequence (A, B, C, D) to make a new triplet that also isn't the 4th repetition of any pairing:

aaabbbcccdddaaccaaddbbddccbbabcdabdacdbcabacacbcbdbdcdcadadbadcbaa

which i'm fairly sure works
which would indicate that there are a lot of results that work but w/e

thats my process

note how you have to end on the same pairing as you begin so in this case AA is the only pairing that appears 5 times (counting AAA as 2 appearances of AA) since it represents the necessary inefficiency for 64 triplets to take 66 letters. In that way, this is cyclical so you could start at any arbitrary point in the sequence above, after first removing the AA from the end and instead duplicating your start pairing at the end.

DarkPlasmaBall

United States44608 Posts

September 18 2015 01:28 GMT

I like Sn0's response and I'm really tired, so I apologize but I'm going to ask a related question (just not to the actual problem):

You had a take-home interview quiz? That seems kind of odd, considering you could just Google the answer/ ask your friends/ ask TLers. How is that supposed to assess you in any way as a future employee, if they don't even know if your solutions are really your own? You don't have to even be able to be creative or a good problem solver... you just need to find someone else who is!

Nemesis

Canada2568 Posts

September 18 2015 03:16 GMT

A simple way to think about is you have three _ in which you can put 4 different letters.
_ _ _

Since order and repetition does not matter, each _ can take 4 different letters. So in total you have 4x4x4 or 4^3 possible combinations.

Edit: Oops, didn't fully read the OP, you were asking about something else. In that case Sn0_Man's solution seems to be best for now. I'll think of my own solution later if I can find another one.

Velocirapture

United States983 Posts

September 18 2015 05:18 GMT

To answer dark, this is one of may questions spanning mathematics, chemistry, physics, biology and more. The idea is that you have to be able to work with subjects outside your comfort zone and take the necessary step to come to a solution. Follow up questions are asked to ensure you gained some understanding of the material rather than simply outsourcing.

To get back to the question, I don't feel I really have a true understanding of the logic of how an answer is derived. Both of the rules you set out by sn0 were obvious to me and I was spending hours trying to find the pattern between different clusters of permutations following "last two" or "first two" groupings. After a lot of time I stumbled upon the following 66 letter solution.

BAAABBACADAACBABCAADBADCABDACCCACDADDDBDBCBCDDCCDCBBBCCBDCDBBDDABA

I am 100% certain this solution works as I have checked it a couple times. I guess I understand that this question does not have many permutations and the solutions will be short enough that it can be managed by hand but what if it was much harder. I would want a process that clearly manages the variables and prescribes an order. Maybe I am just missing it because I am tired.

Sn0_Man

Tebellong44238 Posts

September 18 2015 14:32 GMT

I guess what you need is a logical proof that any method of generation that follows those two rules will complete?
If we follow the generation method, we understand then that our termination point would be a point where the current end pairing has no unused future letter, and as such any letter we add to the end will break us out of "optimal" status by repeating a triplet. yes?
For that to happen, the current pairing must have already occurred 4 times previously PLUS this time since otherwise there will certainly be an allowable letter (one of the 4). In that case, we have already broken our rule of "only use a pairing 4 times". Hence, for a rule to be impossible to follow before the end pairing of the string generation, we must have already broken one of our rules. So simply following the pair of rules above guarantees generation of a winning string assuming you write in the necessary exception for the start/end case (a 5-use pairing) in your method.

Which means that even selecting a random next letter works assuming you check to confirm that it follows the original rules every time before actually adding it to the string.

Computationally, this gets decently expensive as you are required to check every triplet and pair against previously used triplets and pairs however in a low-permutation system like this one it's not a big deal. I'm suspicious that in a system like "10 possible letters, 5 letter passwords" not only would those calculations be expensive but also you may have to track more than just quintuplets and quadruplets although I'd have to think about it. Obviously that case wouldn't be answerable outside a computer-generated answer anyway unless you like typing out pages of letters.

E: I'm not actually convinced that the way I stated my "proof" is even close to concrete but I don't think I'm wrong.

joshie0808

Canada1024 Posts

September 18 2015 15:53 GMT

You could probably perhaps repost this in the programming thread and someone might derive an algorithm that could solve for such an answer given x spaces and y variables?

broodwarhd2

8 Posts

September 18 2015 19:03 GMT

as a programmer i would write a brute force script that would generate all the possible combinations and rank them frrom shortest to longest, then visually analyse the shortest one and try to figure out what mkes it unique

Velocirapture

United States983 Posts

September 18 2015 20:54 GMT

On September 19 2015 04:03 broodwarhd2 wrote:
as a programmer i would write a brute force script that would generate all the possible combinations and rank them frrom shortest to longest, then visually analyse the shortest one and try to figure out what mkes it unique

When I first saw the question this is the first solution that came to mind. Programming simply isn't a skill I have acquired and so I was hoping there was some discrete mathematics I simply didn't know that I could apply. I have my own answer that I came to through my own process so I guess I have to be satisfied.

I would like to thank sn0 for all of his help. I was getting discouraged with my process and your answer really kept me going.

Nemesis

Canada2568 Posts

September 19 2015 01:41 GMT

#10

The solution is not unique. As mentioned before, the minimum solution has to be 66 characters.

A way you could do it via programming is put all the possible keys to the lock in an array or list. Take a single key, and save that in a string variable as the final solution key. Kick that key attempt out of the array.

Next step is to take the last two letters in the solution key and compare it with the first two letters of whatever you have left in the array, then just pick one of the key with the same first two letters and add the last letter to your final solution key string. Kick the key that you just used up once again.

Repeat that until you have no more keys left. And you should come up with a 66 character solution eventually.

Essentially you just do it inductively. That's how I would do it anyways.

Ziggareto

United Kingdom9 Posts

September 20 2015 17:40 GMT

#11

I just brute forced it with programming and got:
AAABAACAADABBABCABDACBACCACDADBADCADDBBBCBBDBCCBCDBDCBDDCCCDCDDDA

You can see for yourself that it is fairly straightforward to get just by hand if you only have A, B, and C at your disposal and you only need a two letter string. You first right out all the possible keys:
AA
AB
AC
BA
BB
BC
CA
CB
CC

then you start your string with AA, then add a letter to make the next highest ordered alphabetically two letter combination not already in your string. In the end you get:
AABACBBCCA
the only thing here is that after AABAC, if you were to add an A then you couldn't complete it, so instead you add a B then it is smooth going.
When you move up to 3 letter code with ABC it just takes longer by hand and there are two of these stepping backwards where the nearest move by the alphabet would leave you in a rut. Adding D doesn't make much difference.

Please or register to reply.

Lock Hack Problem

Completed

Ongoing

Upcoming