Algorithm for Hacking Fallout Terminals

The post-apocalyptic video game Fallout features computer terminals that can be "hacked" to unlock special areas and items. Hacking consists of a word puzzle. The game gives you a series of words, only one of which is the password, and you have 3 chances to guess it.

Strategy for Hacking

The first choice is always a guess. If you guess incorrectly, the terminal tells you how well your guess matches the password. It compares the letters and the positions of the letters. For instance, let's say the password is tap. You choose pot and then hat:

  • pot (0/3 correct)
  • hat (1/3 correct)

pot is completely incorrect because none of its letters match up with tap. The second choice, hat, is partially correct because it shares an a with tap. Solving the puzzles isn't hard, but it gets tedious for some of the higher-difficulty terminals because they include lengthy words.

Goal: Create an algorithm to discover terminal passwords in fewer guesses.

More specifically, we want to tell the user if a remaining word could be the password, considering what we have learned from previous guesses.

Predicting 'Likeness'

First let's construct an object array to store information about each incorrect guess. We'll need to record the likeness between each guess word and the password as it is reported by the terminal.

 var guessedWords = [
    {word: 'cat', likeness: 0},
    {word: 'dog', likeness: 1}
 ];

Now we'll define a method for comparing the likeness between words.

function getLikeness(wordA, wordB) {  
    return wordA.split('').reduce(function(likeness, letter, i) {
      return likeness + ((letter === wordB[i]) ? 1 : 0);
    }, 0);
}

console.assert(getLikeness('cat','hat') === 2); // true  
console.assert(getLikeness('zoo', 'fish') === 0); // true  
console.assert(getLikeness('bar', 'bar') === 3); // true  

Weeding Out Non-Passwords

To determine if a remaining word could be the password, we'll use both getLikeness() and the information in guessedWords. This part is a little complicated, but it's the meat of the algorithm.

Main idea: An untried word may be the password if, for each incorrectly guessed word, getLikeness(untriedWord, incorrectWord) equals getLikeness(incorrectWord, password).

function isViableWord(guessedWords, word) {  
   var i = 0, guess; 
   while (guess = guessedWords[i++]) {
     if (getLikeness(guess.word, word) !== guess.likeness) {
        return false; 
     }
   }
   return true;
}

A few assertions to illustrate:

var guessedWords = [  
  {word: 'cat', likeness: 0},
  {word: 'dog', likeness: 1}
];

console.assert(isViableWord(guessedWords, 'bat') === false);  
console.assert(isViableWord(guessedWords, 'keg') === true);  

Analyzing Words In Bulk

You can call isViableWord for every prospective word, but that's tedious. It's a lot easier to add a method that checks the viability of words in bulk:

function getViableWords(allWords, guessedWords) {  
  var viableCheck = isViableWord.bind(undefined, guessedWords); 
  return allWords.filter(viableCheck); 
}

As usual, a few tests:

var allWords = ['fame','hoop', 'time','mime']; 

var guessedWords = [  
  {word: 'time', likeness: 2}, 
  {word: 'mime', likeness: 2}
];

var viableWords = getViableWords(allWords, guessedWords);  
console.assert(viableWords.length === 1);  
console.assert(viableWords[0] === 'fame'); // true  

The Terminal Hacking Module

Here are the terminal-hacking methods bundled into a module:

/**
* @module Terminal
* @desc Methods to expedite terminal hacking in Fallout 4
*/
(function(exports) {
  'use strict';

  var Terminal = exports.Terminal = {
    getLikeness: function(wordA, wordB) {
      return wordA.split('').reduce(function(likeness, letter, i) {
        return likeness + ((letter === wordB[i]) ? 1 : 0);
      }, 0);
    },
    isViableWord: function(guessedWords, word) {
      var i = 0, guess; 
      while (guess = guessedWords[i++]) {
        if (this.getLikeness(guess.word, word) !== guess.likeness) {
          return false; 
        }
      }
      return true;
    },
    getViableWords: function(allWords, guessedWords) {
      var viableCheck = this.isViableWord.bind(this, guessedWords); 
      return allWords.filter(viableCheck); 
    }
  };
})(window);

Example Usage:

var allWords = ['fish','dish','rags',...],  
    guessedWords = [{word: 'fish', likeness: 2}, ...];

Terminal.getViableWords(allWords, guessedWords);  

Conclusion

There's a lot of room for optimization. I didn't prioritize performance because the input size is always going to be small (fewer than 20 words), but I welcome your suggestions for boosting performance or reducing complexity.

Also, I realize that few people are going to fire up a JavaScript console when they're playing Fallout. This module would be a lot more useful if came with a friendly UI. If anyone wants to take on that task, you have my full permission to use and modify the code above.