Van Tuck wrote:
List ->
A client is inquiring about a web-based system that would allow the
user to type in a question, have the algorithm compare the input
character-by-character to a predefined list of answers until all but
one answer had been removed and the correct answer returned.
Basically think of a huge list of answers out on a stage, then as user
types in their question the forming string is compared and the
incorrect answers disappear from the stage until only one remains,
(that is if there is a predefined answer to that question).
This is off the top of my head, but why not use a destructive binary
search? Store all the answers in an array in alphabetical order, then
each time the user types a letter, do a binary search on the developing
string and Array.splice to eliminate all items that do not start with
that string. It would only take a slight variation on binary search to
rapidly destroy all non-matching items in an alphabetically ordered list.
(If you want it to be undoable, restoring options as the user erases his
string, just use variables to rule out items instead of destroying them.)
Pseudocode:
while (alphabetical array still has available options)
figure out the middle index of the array (if array.length == 50, this
would be 25)
compare the item at the middle index with the input string
if the input string is earlier in alphabetical order, rule out all items
AFTER the middle index
OR
if the input string is later in alphabetical order, rule out all items
BEFORE the middle index
eventually you will have ruled out all items which don't begin with that
string
end while
Note that if you use straight comparators (<, >), a string like "a" will
be < "apple". In this case, you want to keep "apple" if the user only
typed "a". So you'll have to do a little bit of string processing once
you get down to that level.
_______________________________________________
Flashcoders@chattyfig.figleaf.com
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com