• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 08:26
CEST 14:26
KST 21:26
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
Maestros of the Game: Week 1/Play-in Preview12[ASL20] Ro24 Preview Pt2: Take-Off7[ASL20] Ro24 Preview Pt1: Runway132v2 & SC: Evo Complete: Weekend Double Feature4Team Liquid Map Contest #21 - Presented by Monster Energy15
Community News
LiuLi Cup - September 2025 Tournaments2Weekly Cups (August 25-31): Clem's Last Straw?39Weekly Cups (Aug 18-24): herO dethrones MaxPax6Maestros of The Game—$20k event w/ live finals in Paris54Weekly Cups (Aug 11-17): MaxPax triples again!15
StarCraft 2
General
Team Liquid Map Contest #21 - Presented by Monster Energy #1: Maru - Greatest Players of All Time Production Quality - Maestros of the Game Vs RSL 2 Geoff 'iNcontroL' Robinson has passed away Heaven's Balance Suggestions (roast me)
Tourneys
Maestros of The Game—$20k event w/ live finals in Paris RSL: Revival, a new crowdfunded tournament series Chzzk MurlocKing SC1 vs SC2 Cup Sea Duckling Open (Global, Bronze-Diamond) LiuLi Cup - September 2025 Tournaments
Strategy
Custom Maps
External Content
Mutation # 489 Bannable Offense Mutation # 488 What Goes Around Mutation # 487 Think Fast Mutation # 486 Watch the Skies
Brood War
General
The Korean Terminology Thread BGH Auto Balance -> http://bghmmr.eu/ Pros React To: herO's Baffling Game ASL20 General Discussion BW General Discussion
Tourneys
[Megathread] Daily Proleagues [IPSL] ISPL Season 1 Winter Qualis and Info! Is there English video for group selection for ASL Small VOD Thread 2.0
Strategy
Simple Questions, Simple Answers Muta micro map competition Fighting Spirit mining rates [G] Mineral Boosting
Other Games
General Games
General RTS Discussion Thread Stormgate/Frost Giant Megathread Nintendo Switch Thread Path of Exile Warcraft III: The Frozen Throne
Dota 2
Official 'what is Dota anymore' discussion
League of Legends
Heroes of the Storm
Simple Questions, Simple Answers Heroes of the Storm 2.0
Hearthstone
Heroes of StarCraft mini-set
TL Mafia
TL Mafia Community Thread Vanilla Mini Mafia
Community
General
US Politics Mega-thread The Games Industry And ATVI Things Aren’t Peaceful in Palestine Russo-Ukrainian War Thread Canadian Politics Mega-thread
Fan Clubs
The Happy Fan Club!
Media & Entertainment
[Manga] One Piece Anime Discussion Thread Movie Discussion! [\m/] Heavy Metal Thread
Sports
MLB/Baseball 2023 2024 - 2026 Football Thread Formula 1 Discussion TeamLiquid Health and Fitness Initiative For 2023
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread High temperatures on bridge(s)
TL Community
The Automated Ban List TeamLiquid Team Shirt On Sale
Blogs
Collective Intelligence: Tea…
TrAiDoS
A very expensive lesson on ma…
Garnet
hello world
radishsoup
Lemme tell you a thing o…
JoinTheRain
RTS Design in Hypercoven
a11
Evil Gacha Games and the…
ffswowsucks
INDEPENDIENTE LA CTM
XenOsky
Customize Sidebar...

Website Feedback

Closed Threads



Active: 1338 users

Lock Hack Problem

Blogs > Velocirapture
Post a Reply
Velocirapture
Profile Blog Joined December 2010
United States983 Posts
September 17 2015 18:50 GMT
#1
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
Profile Blog Joined October 2012
Tebellong44238 Posts
Last Edited: 2015-09-17 19:41:42
September 17 2015 19:30 GMT
#2
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.
LiquidDota StaffSCIENTISTS BAFFLED | 3275929302
DarkPlasmaBall
Profile Blog Joined March 2010
United States44465 Posts
September 18 2015 01:28 GMT
#3
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!
"There is nothing more satisfying than looking at a crowd of people and helping them get what I love." ~Day[9] Daily #100
Nemesis
Profile Blog Joined May 2009
Canada2568 Posts
Last Edited: 2015-09-18 03:19:39
September 18 2015 03:16 GMT
#4
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.
Lee Young Ho fighting! KT P are just CHINTOSSTIC.
Velocirapture
Profile Blog Joined December 2010
United States983 Posts
September 18 2015 05:18 GMT
#5
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
Profile Blog Joined October 2012
Tebellong44238 Posts
Last Edited: 2015-09-18 14:52:26
September 18 2015 14:32 GMT
#6
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.
LiquidDota StaffSCIENTISTS BAFFLED | 3275929302
joshie0808
Profile Blog Joined March 2011
Canada1024 Posts
September 18 2015 15:53 GMT
#7
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
Profile Joined February 2015
8 Posts
September 18 2015 19:03 GMT
#8
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
Profile Blog Joined December 2010
United States983 Posts
September 18 2015 20:54 GMT
#9
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
Profile Blog Joined May 2009
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.
Lee Young Ho fighting! KT P are just CHINTOSSTIC.
Ziggareto
Profile Joined March 2014
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 log in or register to reply.
Live Events Refresh
RSL Revival
10:00
Season 2: Group A
Bunny vs ZounLIVE!
Creator vs TBD
Crank 1308
Tasteless1079
IndyStarCraft 239
Rex163
3DClanTV 65
LiquipediaDiscussion
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
Crank 1308
Tasteless 1079
IndyStarCraft 239
Rex 163
Codebar 23
Railgan 10
ProTech1
StarCraft: Brood War
Shuttle 1549
firebathero 596
sSak 508
Larva 479
ggaemo 293
Pusan 254
Last 251
Light 234
Zeus 219
JulyZerg 213
[ Show more ]
Hyuk 198
ToSsGirL 181
Hyun 89
TY 82
Aegong 68
scan(afreeca) 33
JYJ32
Free 28
Icarus 18
Movie 17
Noble 15
Terrorterran 8
Shine 7
Hm[arnc] 4
Britney 0
Dota 2
The International74872
Gorgc14212
Fuzer 348
XcaliburYe195
Counter-Strike
x6flipin677
zeus205
byalli117
Super Smash Bros
Mew2King63
Heroes of the Storm
Khaldor199
Liquid`Hasu178
Other Games
singsing1472
B2W.Neo1140
DeMusliM359
JimRising 352
Hui .180
Sick97
MindelVK29
Organizations
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 14 non-featured ]
StarCraft 2
• Adnapsc2 12
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• Noizen33
League of Legends
• Jankos1048
Other Games
• WagamamaTV310
Upcoming Events
Maestros of the Game
4h 34m
Maru vs Lambo
herO vs ShoWTimE
BSL Team Wars
6h 34m
Team Hawk vs Team Sziky
Sparkling Tuna Cup
21h 34m
Monday Night Weeklies
1d 3h
The PondCast
3 days
RSL Revival
3 days
RSL Revival
4 days
Online Event
4 days
BSL Team Wars
5 days
Team Bonyth vs Team Dewalt
BSL Team Wars
5 days
[ Show More ]
RSL Revival
5 days
Maestros of the Game
6 days
Cosmonarchy
6 days
Bonyth vs Dewalt
[BSL 2025] Weekly
6 days
RSL Revival
6 days
Liquipedia Results

Completed

Proleague 2025-09-02
SEL Season 2 Championship
HCC Europe

Ongoing

Copa Latinoamericana 4
BSL 20 Team Wars
KCM Race Survival 2025 Season 3
BSL 21: BSL Points
ASL Season 20
CSL 2025 AUTUMN (S18)
LASL Season 20
RSL Revival: Season 2
Maestros of the Game
Chzzk MurlocKing SC1 vs SC2 Cup #2
BLAST Open Fall 2025
BLAST Open Fall Qual
Esports World Cup 2025
BLAST Bounty Fall 2025
BLAST Bounty Fall Qual
IEM Cologne 2025
FISSURE Playground #1

Upcoming

2025 Chongqing Offline CUP
BSL Polish World Championship 2025
BSL Season 21
BSL 21 Team A
EC S1
BLAST Rivals Fall 2025
IEM Chengdu 2025
PGL Masters Bucharest 2025
Thunderpick World Champ.
MESA Nomadic Masters Fall
CS Asia Championships 2025
ESL Pro League S22
StarSeries Fall 2025
FISSURE Playground #2
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2025 TLnet. All Rights Reserved.