123456789101112131415161718192021222324252627282930313233343536373839404142 |
- import random
- import string
- from string import ascii_lowercase as alphabet
- def extract(query):
- dataset=set()
- helper('',dataset,query,0)
- return sorted(list(dataset))
-
- def helper(prefix,dataset,query,start_at):
- for i in range(start_at,26):
- results=query(prefix+alphabet[i])
- if prefix+alphabet[i] in results:
- dataset.add(prefix+alphabet[i])
- if len(results)==5:
- dataset.update(results)
- start_at=alphabet.index(results[4][len(prefix)+1])
- helper(prefix+alphabet[i],dataset,query,start_at)
- else:
- dataset.update(results)
- return
- def test(num_words):
- database = []
- for i in range(num_words):
- word = ''.join(random.choice(alphabet) for i in range(random.randint(1,20)))
- database.append(word)
- database = sorted(database)
- query = lambda prefix: [d for d in database if d.startswith(prefix)][:5]
- print (database)
- print (extract(query))
- assert extract(query) == database
- def main():
-
-
- database = ["abracadara", "al", "alice", "alicia", "allen", "alter", "altercation", "bob", "eve", "evening", "event", "eventually", "mallory"]
- query = lambda prefix: [d for d in database if d.startswith(prefix)][:5]
- assert extract(query) == database
-
- main()
- test(25)
|