word games - permutate/temperature game

permutate.js

const fs = require('fs')
const readline = require('readline')

async function readDict(dictFile, wordLength) {

    const words = {}

    return new Promise((resolve) => {

        const lineReader = readline.createInterface({
            input: fs.createReadStream(dictFile)
        })
        
        lineReader.on('line', line => {
            if (line.length === wordLength) {
                const word = line.toLowerCase().trim()
                words[word] = word
            }
        })
        
        lineReader.on('close', () => {
            resolve(words)
        })
    })
}

// doesn't have to result in valid words
function *letterReplacements(word, alphabet) {
    for (let i = 0; i < word.length; i++) {
        for (let c = 0; c < alphabet.length; c++) {
            yield [
                word.slice(0, i) + alphabet[c] + word.slice(i + 1),
                alphabet.slice(0, c) + alphabet.slice(c + 1)
            ]
        }
    }
}

// has to be 1 step closer to target word
function *successors(words, state) {

    const [word, togo] = state
    const replacements = letterReplacements(word, togo)

    for (let [replacement, nextTogo] of replacements) {
        if (words[replacement] && replacement !== word) {
            yield [replacement, nextTogo]
        }
        for (let permutation of permute(replacement)) {
            if (words[permutation] && permutation !== word) {
                yield [permutation, nextTogo]
            }
        }
    }
}

function *permute(str) {

    const permutation = str.split('')
    const length = permutation.length
    const c = new Array(length).fill(0)
    let i = 1
    let k
    let p
  
    while (i < length) {
        if (c[i] < i) {
            k = i % 2 && c[i]
            p = permutation[i]
            permutation[i] = permutation[k]
            permutation[k] = p
            ++c[i]
            i = 1
            yield permutation.join('')
        } else {
            c[i] = 0
            ++i
        }
    }
}

function *depthFirstTreeSearch(problem) {

    const startNode = {
        state: problem.initialState,
        parent: null
    }
    const frontier = [startNode]
    const seen = new Set()

    while (frontier[0]) {

        const node = frontier.pop()
        if (problem.isGoal(node.state)) {
            yield node

        } else {
            const hash = problem.hash(node.state)
            seen.add(hash)

            for (nextNode of problem.expand(node)) {
                if (!seen.has(problem.hash(nextNode.state))) {
                    frontier.push(nextNode)
                }
            }
        }
    }

    return false
}

function flatten(node) {

    const result = []

    while (node.parent) {
        result.unshift(node.state)
        node = node.parent
    }

    return result
}

function *solve(words, start, target) {

    const permuteProblem = {

        hash(state) {
            return state[0]
        },

        initialState: [start, target],

        isGoal(state) {
            return state[0] === target
        },
        
        *expand(node) {
            const nextStates = successors(words, node.state)
            for (let state of nextStates) {
                yield { state, parent: node }
            }
        }
    }

    for (let solution of depthFirstTreeSearch(permuteProblem)) {
        yield flatten(solution)
    }
}

const start = process.argv[2]
const finish = process.argv[3]

if (!start || !finish || start.length !== finish.length) {
    process.stdout.write(
        `usage: node permute.js startWord targetWord\n`
    )

} else {
    readDict('./dictionary.txt', start.length).then(words => {
        for (let solution of solve(words, start, finish)) {
            process.stdout.write(
                solution.map(s => s[0]).join(' -> ') + '\n'
            )
        }
    })
}