Created
November 6, 2015 19:20
-
-
Save codyhanson/ec1c7f662b4e32bec6af to your computer and use it in GitHub Desktop.
longest chain
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var _ = require('underscore'); | |
var sprintf = require('sprintf-js').sprintf; | |
var words = _.chain(require('fs').readFileSync('wordsEn.txt').toString().split("\r\n")).compact().sortBy('length').value(); | |
var chains = []; | |
function contains(smaller, bigger) { | |
if (smaller.length >= bigger.length) return false; | |
for (var i = 0; i < smaller.length; i++) if (_.indexOf(bigger, smaller[i]) == -1) return false; | |
return true; | |
} | |
for (var i = 0; i < words.length; i++) { | |
var word = words[i]; | |
var foundExistingChain = false; | |
var spliceList = []; | |
for (var j = 0; j < chains.length; j++){ | |
var endOfChain = chains[j][chains[j].length -1]; | |
if (contains(endOfChain, word)){ | |
foundExistingChain = true; | |
chains[j].push(word); | |
} else if (word.length > endOfChain.length + 1 && chains[j].length < 3) spliceList.push(j); | |
} | |
_.each(spliceList, function(k) { chains.splice(k,1);}); | |
if (!foundExistingChain && word.length < 4) chains.push([word]); | |
} | |
var longestGroups = _.chain(chains).groupBy('length').value(); | |
var longests = longestGroups[_.chain(longestGroups).keys().map(parseInt).max().value()]; | |
console.log(sprintf("longest length: %s \n %s", longests[0].length, longests.join('\n'))); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
clh@striker ~/workspace/longestchain (master) $ archey | |
### User: clh | |
#### Hostname: striker | |
### Distro: OS X 10.10.5 | |
####### ####### Kernel: Darwin | |
###################### Uptime: 28 days | |
##################### Shell: /bin/bash | |
#################### Terminal: xterm-256color | |
#################### Packages: 108 | |
##################### CPU: Intel Core i7-4850HQ CPU @ 2.30GHz | |
###################### Memory: 16 GB | |
#################### Disk: 48% | |
################ Battery: 100.00% | |
#### ##### IP Address: [REDACTED] |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
clh@striker ~/workspace/longestchain (master) $ time nvm run 0.10.40 attempt2.js | |
Running node v0.10.40 (npm v1.4.28) | |
longest length: 14 | |
ai,aid,acid,acids,caddis,addicts,acridest,accredits,acridities,ascertained,candidatures,circumstanced,discouragement,discouragements | |
an,ana,acne,acned,ascend,ascends,acidness,accidents,anecdotist,anecdotists,condensation,commendations,appendectomies,complicatedness | |
id,aid,acid,acids,caddis,addicts,acridest,accredits,acridities,ascertained,candidatures,circumstanced,discouragement,discouragements | |
ii,aid,acid,acids,caddis,addicts,acridest,accredits,acridities,ascertained,candidatures,circumstanced,discouragement,discouragements | |
is,dis,aids,acids,caddis,addicts,acridest,accredits,acridities,ascertained,candidatures,circumstanced,discouragement,discouragements | |
mo,com,coma,cameo,cameos,calomels,camisoles,normalcies,ceremonials,reclamations,ceremonialist,ceremonialists,chemosterilants,trichloromethanes | |
na,ana,acne,acned,ascend,ascends,acidness,accidents,anecdotist,anecdotists,condensation,commendations,appendectomies,complicatedness | |
sd,ads,adds,acids,caddis,addicts,acridest,accredits,acridities,ascertained,candidatures,circumstanced,discouragement,discouragements | |
si,dis,aids,acids,caddis,addicts,acridest,accredits,acridities,ascertained,candidatures,circumstanced,discouragement,discouragements | |
real 0m5.020s | |
user 0m4.784s | |
sys 0m0.252s |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
clh@striker ~/workspace/longestchain (master) $ time nvm run 4.2.1 attempt2.js | |
Running node v4.2.1 (npm v1.4.28) | |
longest length: 14 | |
ai,aid,acid,acids,caddis,addicts,acridest,accredits,acridities,ascertained,candidatures,circumstanced,discouragement,discouragements | |
an,ana,acne,acned,ascend,ascends,acidness,accidents,anecdotist,anecdotists,condensation,commendations,appendectomies,complicatedness | |
id,aid,acid,acids,caddis,addicts,acridest,accredits,acridities,ascertained,candidatures,circumstanced,discouragement,discouragements | |
ii,aid,acid,acids,caddis,addicts,acridest,accredits,acridities,ascertained,candidatures,circumstanced,discouragement,discouragements | |
is,dis,aids,acids,caddis,addicts,acridest,accredits,acridities,ascertained,candidatures,circumstanced,discouragement,discouragements | |
mo,com,coma,cameo,cameos,calomels,camisoles,normalcies,ceremonials,reclamations,ceremonialist,ceremonialists,chemosterilants,trichloromethanes | |
na,ana,acne,acned,ascend,ascends,acidness,accidents,anecdotist,anecdotists,condensation,commendations,appendectomies,complicatedness | |
sd,ads,adds,acids,caddis,addicts,acridest,accredits,acridities,ascertained,candidatures,circumstanced,discouragement,discouragements | |
si,dis,aids,acids,caddis,addicts,acridest,accredits,acridities,ascertained,candidatures,circumstanced,discouragement,discouragements | |
real 0m8.629s | |
user 0m8.081s | |
sys 0m0.346s |
Still 14
[mcoffin@mcoffin-arch-mbair wordchain]$ time dist/build/wordchain/wordchain words.txt
Longest path found: 14
["presuppositions\r"]
["presupposition\r"]
["superposition\r"]
["prepositions\r"]
["preposition\r"]
["reposition\r"]
["portiones\r"]
["spoonier\r","snoopier\r","poisoner\r"]
["erosion\r"]
["senior\r","nosier\r","noires\r","irones\r"]
["noire\r"]
["rein\r","erin\r"]
["ire\r"]
["ie\r"]
real 0m1.024s
user 0m0.987s
sys 0m0.037s
oh yeah, i should be able to push the 'a' on the front and get to 15.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
So we're getting different chains. Btw it looks to me like you're just not checking the 1-length words. ezpz fix?