Palindromy Again

chaoticset on 2003-10-10T19:31:08

Still noodling the palindrome problem.

Still haven't gotten any further than trying to make the huge processing task a little smaller with preprocessing the dictionary file. (I figure that taking out all the words that cannot possibly match any other parts of any other words is difficult, but would make it easier to match words later. Just a little.) In the same vein, I assumed that keeping track of whether words contain individual letters would speed up the search too. (Which is to say, searching for the word CASE would only happen in the subset of the wordlist that contains Cs, As, Ss, or Es.) This makes smaller words easier, doesn't help so much with longer words.

Now I just need to turn my little analyzer thingy into a filter (word list goes in, word list minus non-reversible words comes out) and then make sure the filter's working. Then work together whatever data structure I'm going to use (thinking HoA) to store the information about what words contain what letters and put that in place with Storable.

I keep looking at chromatic's project, but I can't seem to throw enough time at it. I had started on the persistence module but someone else actually implemented it when I came back around. NBD.

One thing I've been considering adding as a story is naming a cyberdeck, so that a player could have multiple decks (but not use more than one at a time, of course). Assuming I'm not completely off base here, people might want to daisy chain decks so they've got the extra storage, but still have different decks so that they've got the versatility of choosing what system they want to use to hack.

If, of course, that's an option. If that's not an option, then the decks don't know about each other and don't have to exist at the same time, and the name thing can be handled before the game engine loads (each player is assigned their deck stats and name is included in that). Still, it'd be neat to do that, and further consequences can be imagined (if your head can get hacked, and all your decks are linked to your head, then all your decks can get hacked too...)


a word filter

jmm on 2003-10-10T20:17:24

To filter words that could not be reversed can be expensive. A word, say "abcde" could be reversed in many ways.

(1) "edcba" contained (anywhere) within a word as a (sub-)string

(2} "e" at the end of one word and "dcba" at the beginning of another

(3) "de" at the end and "cba" at the beginning

(4) - (5) the obvious continuations.

To fully test this would require having a hash of leading n-letter strings, trailing n-letter strings, and anywhere n-letter strings. That is going to be a large number of combinations. Filtering out a bunch of irreversible words might make additional words irreversible (since they might have only be able to be reversed using words that have been filtered). So, those hashes should contain a count of how many times that particular sub-string exists, and when a word is found to be unusable, all of its substrings must be subtracted out - if any substring counts went to zero then another round of checking may produce additional words that can be deleted.