Solving wordcrack

wordcrack.js

'use strict'
const fs = require('fs')

// util function modified from github.com/bucaran/sget
function readLineSync(message) {
  message = message || ''
  const win32 = () => 'win32' === process.platform
  const readSync = function(buffer) {
    var fd = win32() ? process.stdin.fd : fs.openSync('/dev/stdin', 'rs')
    var bytes = fs.readSync(fd, buffer, 0, buffer.length)
    if (!win32()) fs.closeSync(fd)
    return bytes
  }
  return (function(buffer) {
    try {
      process.stdout.write(message + ' ')
      return buffer.toString(null, 0, readSync(buffer))
    } catch (e) {
      throw e
    }
  }(new Buffer(256)))
}

// const corpus = fs.readFileSync('words2.txt', 'utf-8').split('\n').map(word => word.toLowerCase())
const corpus = fs.readFileSync('/usr/share/dict/words', 'utf-8').split('\n').map(word => word.toLowerCase())
const board = {
  length: 4,
  height: 4,
}
// // NOTE: For notation, axes are swapped. eg., 0, 2 is first row second letter
// const inp = ['ogwc', 'ntca', 'aiap', 'lces']
const inp = []
console.log(`Enter the ${board.length}x${board.height} matrix`)
inp[0] = readLineSync()
inp[1] = readLineSync()
inp[2] = readLineSync()
inp[3] = readLineSync()

const matrix = inp.map(str => str.split(''))
const emptyMatrix = Array(board.height + 1).join('-').split('').map(i => Array(board.length + 1).join('-').split('').map(j => 0))

const ALPHABETS = 'abcdefghijklmnopqrstuvwxyz'.split('')

function place(obj, word) {
  let localObj = obj
  const letters = word.split('')
  for (let i = 0; i < letters.length; i++) {
    const letter = letters[i]
    if (!localObj[letter]) {
      localObj[letter] = {}
    }
    if (i === letters.length - 1) {
      localObj[letter]._word = true
    }
    localObj = localObj[letter]
  }
  return obj
}

function structureCorpus(words) {
  let structured = {}
  // Using for loops instead of forEach for efficiency
  for (let i = 0; i < words.length; i++) {
    const word = words[i]
    if (!word) {
      continue
    }
    structured = place(structured, word)
    // break
  }
  return structured
}

// - fn:(matrix, pos, flagMatrix, localStruc)
//   - If flagged, return []
//   - create a flagMatrixCopy
//   - Flag value
//   - if in localStruc
//     - if _word, also send ["<letter>"]
//     - for every position around it
//       - get fn(matrix, newPos, flagMatrix, localStruc[letter])
//       - return with <letter> prepended to each value
//   - else return []
// - For every value in matrix
//   - fn(matrix, value, flagMatrix, structured)

function traverse(matrix, pos, flagMatrix, localObj, lvl) {
  if (flagMatrix[pos.i][pos.j])
    return []

  const letter = matrix[pos.i][pos.j]
  if (!localObj[letter]) {
    return []
  }

  const flagMatrixCopy = flagMatrix.map(row => row.slice())
  flagMatrixCopy[pos.i][pos.j] = 1
  let allWords = []
  if (localObj[letter]._word) {
    allWords.push(letter)
  }
  for (let i = -1; i <= 1; i++) {
    const newI = pos.i + i
    if (newI < 0 || newI >= board.length) {
      continue
    }
    for (let j = -1; j <= 1; j++) {
      const newJ = pos.j + j
      if (newJ >= 0 && newJ < board.height) {
        const newPos = { i: newI, j: newJ }
        const others = traverse(matrix, newPos, flagMatrixCopy, localObj[letter], lvl + 1).map(word => letter + word)
        allWords = allWords.concat(others)
      }
    }
  }

  return allWords
}

const structuredCorpus = structureCorpus(corpus)
// const structuredCorpus = structureCorpus(['a', 'abs', 'absolute', 'allah', 'almighty', 'spec', 'ties', 'cap', 'taps', 'laces', 'alias'])

let allWords = []
for (let i = 0; i < board.length; i++) {
  for (let j = 0; j < board.height; j++) {
    allWords = allWords.concat(traverse(matrix, { i, j }, emptyMatrix, structuredCorpus, 0))
  }
}
// Finding unique
allWords = allWords.filter((item, pos) => allWords.indexOf(item) == pos)
allWords.sort((a, b) => a.length >= b.length)

console.log(allWords.length, 'words')
console.log('')
console.log(allWords)