All files index.js

100% Statements 64/64
100% Branches 6/6
100% Functions 11/11
100% Lines 63/63

Press n or j to go to the next uncovered block, b, p or k for the previous block.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168                                          2x 2x                 2x 2x 2x         2x 346278x     2x 2x                   346280x 346280x     346280x 9003280x 9003280x     346280x   346280x 3144174x 3144174x     346280x                 2x 2x   346278x 346278x 346278x     346278x 9003228x 9003228x     9003228x 1315394x   9003228x 9003228x       346278x 313332x   346278x     2x                       1x 1x 1x 1x     1x 26x 26x 26x 26x     26x 40x 40x     40x 50x 44x   50x   40x   26x 26x     1x 1x     1x 5x   5x 8x 8x   5x       18x          
import fs from 'fs'
import path from 'path'
import readline from 'readline'
 
/**
 * A class for generating anagrams of words from comma-separated letters.
 * @example
 * // Create a new instance of WordGenerator
 * const wordGenerator = new WordGenerator();
 * // Generate the anagram tree
 * await wordGenerator.generateTree();
 * // Get the anagrams for a set of letters
 * const lettersArray = ['t', 'e', 's', 't'];
 * const anagrams = wordGenerator.getAnagrams(lettersArray);
 * console.log(anagrams);
 */
class WordGenerator {
  /**
   * Create a new instance of WordGenerator.
   */
  constructor () {
    this.tree = {}
    this.alphabet = 'jqxzwkvfybhgmpudclotnraise'
  }
 
  /**
   * Reads words file and applies a callback on each line
   * @param {function} callback - Function to be called on each line
   * @param {function} finished - Function to be called when file reading is finished
   */
  readWordsFile (callback, finished) {
    const filepath = path.join(__dirname, '../vendor/words.txt')
    const readStream = fs.createReadStream(filepath)
    const rl = readline.createInterface({
      input: readStream,
      crlfDelay: Infinity
    })
 
    rl.on('line', (line) => {
      callback(line)
    })
 
    rl.on('close', () => {
      finished()
    })
  }
 
  /**
   * Creates a histogram from a given word based on the alphabet property
   * @param {string} word - The word to create a histogram from
   * @returns {object} histogram - The created histogram with alphabet characters as keys and their frequency as values
   */
  histogramify (word) {
    const histogram = {}
    let alphabetIndex = 0
 
    // Initialize histogram with alphabet characters and set their frequency to 0
    while (alphabetIndex < this.alphabet.length) {
      histogram[this.alphabet[alphabetIndex]] = 0
      alphabetIndex++
    }
 
    let wordIndex = 0
    // Iterate through the word and update the frequency of each character in the histogram
    while (wordIndex < word.length) {
      histogram[word[wordIndex]]++
      wordIndex++
    }
 
    return histogram
  }
 
  /**
   * Generate a tree of words from given source file.
   * @async
   * @returns {Promise<void>} Promise that resolves when the tree is generated.
   */
  async generateTree () {
    return new Promise((resolve, reject) => {
      this.readWordsFile(
        (word) => {
          const histogram = this.histogramify(word)
          let currentNode = this.tree
          let alphabetIndex = 0
 
          // Iterate through the alphabet and create tree nodes based on character frequencies
          while (alphabetIndex < this.alphabet.length) {
            const letter = this.alphabet[alphabetIndex]
            const frequency = histogram[letter]
 
            // Create a new node for the frequency if it doesn't exist
            if (!currentNode[frequency]) {
              currentNode[frequency] = {}
            }
            currentNode = currentNode[frequency]
            alphabetIndex++
          }
 
          // Add the word to the words array in the current node
          if (!currentNode.words) {
            currentNode.words = []
          }
          currentNode.words.push(word)
        },
        () => {
          resolve()
        }
      )
    })
  }
 
  /**
   * Get all possible anagrams for a given set of letters
   * @param {string[]} lettersArray - Array of letters
   * @returns {string[]} allAnagrams - Sorted array of anagrams in descending order of length
   */
  getAnagrams (lettersArray) {
    const histogram = this.histogramify(lettersArray)
    const rootNode = this.tree
    let frontier = [rootNode]
    let alphabetIndex = 0
 
    // Iterate through the alphabet and traverse the tree based on character frequencies
    while (alphabetIndex < this.alphabet.length) {
      const letter = this.alphabet[alphabetIndex]
      const frequency = histogram[letter]
      const newFrontier = []
      let nodeIndex = 0
 
      // Traverse the frontier nodes to build new frontier nodes
      while (nodeIndex < frontier.length) {
        const currentNode = frontier[nodeIndex]
        let subNodeIndex = 0
 
        // Add nodes from the current frontier to the new frontier based on their frequency
        while (subNodeIndex <= frequency) {
          if (currentNode[subNodeIndex]) {
            newFrontier.push(currentNode[subNodeIndex])
          }
          subNodeIndex++
        }
        nodeIndex++
      }
      frontier = newFrontier
      alphabetIndex++
    }
 
    const allAnagrams = []
    let nodeIndex = 0
 
    // Iterate through the frontier nodes and add their words to the allAnagrams array
    while (nodeIndex < frontier.length) {
      let wordIndex = 0
 
      while (wordIndex < frontier[nodeIndex].words.length) {
        allAnagrams.push(frontier[nodeIndex].words[wordIndex])
        wordIndex++
      }
      nodeIndex++
    }
 
    // Sort the anagrams in descending order of length
    return allAnagrams.sort((a, b) => b.length - a.length)
  }
}
 
export { WordGenerator }