Just finished this little script that turned out to be an interesting enough project that I figured some members here might want to see.

For those unaware, Fallout 3, New Vegas, and 4 all features a mini-game/puzzle for "hacking" into computers whose password you haven't yet found or cannot be found. The puzzle is pretty simple, you've been given a set of possible words all with the same length, and must make guesses as to which is the correct password. You get 4 attempts at the correct password, and the game will tell you after each attempt how many characters in your guess matched the characters in the correct password. In this sense, it's similar to the game Mastermind except get the "correct letters with correct placement" number without the "correct letter with incorrect placement" number. If you make 4 incorrect guesses you're locked out of the machine.

You have as much time as you want to solve the puzzle, so generally the way most people solve it is by making a random choice, seeing how many letters match, then finding and trying all remaining passwords that have the same number of matching letters. I grew tired of manually going through each password and counting letters, and disliked how random and unguided this process was so I started making a script that would attempt to find the password for me with as few guesses as possible.

When looking at this problem, my first insight (from experience) was noting that not all passwords given were equal. The game at times seems to use words with certain prefixes and suffixes. 're-', 'un-', 'de-', etc. are frequent prefixes above a certain length, along with '-ing', '-tion', '-ed', etc. for word endings and suffixes. I have also noticed that at times it will choose a lot of words that share the same prefix and suffix. Generally speaking choosing one of these words as your first bit of information tends to be not very helpful as most of the time the actual password is one of these words, so it's going to have 3-6 letters in common with about half of your given words. While reducing the possibilities by 50% can be pretty good, because we're dealing with 0-13 letter matches here, I'd like to aim for a better reduction than 50%. While we can technically gain more information with each guess at a password, I think some of the choices are usually going to be much better than others, which begs the questions of "which choices are better than others?" and "how can that be determined?"

To attempt to figure this out, I started looking at a practical example. Below is a list of the words I had available as options in a Hard rated computer. You'll note that although they don't share many prefixes, several of them share the same suffixes and endings due to many of them being verbs that share the same tense.

Code:

The only information I can gleam from the game about any of these choices is how many letters any of them have in common with the actual password, which could be any of them. Due to this, my first thought is to try to try matching each word with one another and see if there's anything I can try with the resulting data. Below is a chart with how many letters match between each word. The Y axis is labeled with each word being used, the X axis uses the same words in the same order going from left to right as the Y axis uses going from top to bottom.

Code:
The code I used to present this data:
Code:

One thing I wanted to see when looking at this data was whether there was a significant difference in the potential information provided by each choice, which as the data currently stands is difficult to see, so I tried sorting each row by values to see some rows had a noticeably more even distribution of data than others. Admittedly this destroys some of the data, as it's now impossible to tell which value relates to which word, however as we're just looking at the metadata and we're just presenting it in a different way, I'm not super concerned with keeping that intact. This is also done purely so I can better interpret the data and isn't used in the resulting code at any point.

Code:
The code used for this is the last line of the previous code segment slightly altered to sort the numbers before joining them together with commas.
Code:

One thing I noticed immediately is that there are several lines here that have more than 10 matches with only 1 letter in common. It seems while I was largely concerned with getting several words with 3-6 letters in common, the bigger issue (in this example, at least) is with words that are too unique from one another to get much information. Now this information is a bit easier to read, but I'm still (personally) struggling to get a better idea of which has the better distribution of values. In order to get a better idea of this, I decided to count the number of each value. Here's the resulting grid:

Code:
And the code used to present this information:
Code:

Side note: You may notice that despite the fact that each word is 11 characters in length, 11 is missing from this grid. Unless there are 2 words entered that are exactly the same, there will always be exactly 1 word in the list that is the same as a given word: itself. Therefore this last column can be safely omitted without losing any useful information.

The information here seems a lot easier to quantify than before. Around this time, I started thinking about ways to find which row had the best distribution of values, when I realized that the biggest issue with any of the rows is whichever number of shared letters is most common in a given row. Minimizing this number should be the best way to guarantee that no matter what the actual password is, the information received will narrow down where the actual password is the most consistently. As such, the resulting code looks like this:
Code:

After this, we can attempt to reiterate the same process for the second most common values for any rows that share the minimum of the maximum of each row, but in practice one iteration of this process is more than enough to solve most any situation presented by the hacking mini-game in Fallout 3, New Vegas, or 4.

After this, all we need to do is get the result for the word the algorithm believes is the best option, choose that in-game, enter however many letters the game says that chosen word shares with the actual password, remove all the words that don't share that many letters as the chosen one, then reiterate until the actual password is discovered.

In practice I've found that this process tends to narrow the results by 80% each iteration, depending on the length of the words, generally requiring 2-3 attempts to find the actual password. I've yet to run into a situation where it has required a 4th attempt, but I still need to do some more testing to see how effective it is at different lengths and with different numbers of given passwords, and am looking to see if I can find the way the game sets this puzzle up in more precise details so I can simulate it much faster than manually typing words when I find new computers to hack into in-game.

Last but not least, the full source code for my resulting script:
Code:


Let me know how you'd approach this problem, how you liked my approach, or if you can find any specific details on how Fallout generates these puzzles so I can quickly test more situations and see how well this works in most scenarios.