Miss Minaj says, "I win, I win because I'm a lyricist and I have words in my brain!"
cold > cord > card > ward > warm
What?
Solves Lewis Carroll's word game Doublets (AKA "Word Ladder"):
Given two words X and Y, find a chain ("ladder") of words that take you from X to Y with only one edit a time.
Each intermediate word should be a valid/dictionary word.
My algorithm is biased towards words that appear in Nicki Minaj's lyrics (in pink).
Notes
- Tested on Chrome v70. Performance-wise, it sucks.
- Uses a wordlist that contains the 50K most common words in English. (This demo actually uses just the first 2K words)
- Nicki's words were obtained from an incomplete collection of her lyrics (Check wordli$ter.js: It is the script that created the wordli$t.txt file).
- Uses a breadth-first search algorithm on a "graph of words".
- Uses Hip, my stupid Array-based heap implementation with only three methods: push, pop, and isEmpty.
- The Levenshtein distance can be used to make things interesting, but let's just use the Hamming distance to keep it simple ._.