Suggest a word from a word list, given a string.

Motivation

Imagine typing a word one letter at a time, and seeing a suggested word after each letter is typed. At first the suggested word is simply the first word in the word list that matches, but once a word has been suggested it is assumed that you don’t want that word if you continue typing, so it is excluded from being a candidate for the subsequent suggestions.

Input

• A string and an ordered sequence of distinct strings (the word list).
• You may take these two inputs in any consistent order.
• The word list will contain at least 1 string.
• Each of the strings in both inputs will have length at least 1.
• Each of the strings in both inputs will be composed only of lower case Latin letters:
  abcdefghijklmnopqrstuvwxyz
• No 2 words in the word list will be identical.
• The input string may be identical to one of the words in the word list.

Output

• One of the words from the word list, or the input string.
• There is only 1 correct output for each input, as determined by the algorithm shown below.
• Your code does not need to use this algorithm, provided it gives the correct output.

Algorithm

1. For each prefix of the input string, from length 1 to the full string:
   • If the prefix is one of the words in the word list, remove this found word from the word list
   • Otherwise:
     • Look for the first word in the word list that has this prefix.
     • If a match was found, remove the found word from the word list.
     • Otherwise output the original input string and terminate.
2. Output the latest found word.

Note that the word list will not necessarily be sorted. Here "the first word" means the first word in the order that the word list was received.

Examples

Input string present as a prefix

• Input string: "tre"
• Input word list: "heavy", "table", "test", "treat", "train", "tread"
• Process:
  • The first word with prefix "t" is "table", so "table" is removed from the list.
  • The first word with prefix "tr" is "treat", so "treat" is removed from the list.
  • The first word with prefix "tre" is "tread", so "tread" is removed from the list.
  • The output is "tread", because it was the last word found.

Note that the first word with prefix "tre" in the original word list is "treat", but this is excluded because it is the first word with prefix "tr".

Input string not present as a prefix

• Input string: "tre"
• Input word list: "porridge", "pie", "plum"
• Process:
  • "t" is not a prefix of any word in the word list, so the output is the same as the input string: "tre".

No match due to excluded word

• Input string: "tre"
• Input word list: "heavy", "table", "test", "treat", "train"
• Process:
  • The first word with prefix "t" is "table", so "table" is removed from the list.
  • The first word with prefix "tr" is "treat", so "treat" is removed from the list.
  • There is no word that matches "tre", so the output is the same as the input string: "tre".

Note that the first word with prefix "tre" in the original word list is "treat", but this is excluded because it is the first word with prefix "tr", leaving no remaining words with prefix "tre".

Exact match present and chosen

• Input string: "red"
• Input word list: "redone", "redden", "redo", "red"
• Process
  • The first word with prefix "r" is "redone", so "redone" is removed from the list.
  • The first word with prefix "re" is "redden", so "redden" is removed from the list.
  • There is an exact match for "red", so "red" is removed from the list.
  • The output is "red", because it was the last word found.

Exact match present but excluded

• Input string: "red"
• Input word list: "redone", "red", "redden", "redo"
• Process:
  • The first word with prefix "r" is "redone", so "redone" is removed from the list.
  • The first word with prefix "re" is "red", so "red" is removed from the list.
  • The first word with prefix "red" is "redden", so "redden" is removed from the list.
  • The output is "redden", because it was the last word found.

Test cases

Test cases are in the format:

["string", ["comma", "separated", "words"]] : "output"

["tre", ["heavy", "table", "test", "treat", "train", "tread"]] : "tread"
["tre", ["porridge", "pie", "plum"]] : "tre"
["tre", ["heavy", "table", "test", "treat", "train"]] : "tre"
["red", ["redone", "redden", "redo", "red"]] : "red"
["red", ["redone", "red", "redden", "redo"]] : "redden"
["red", ["red"]] : "red"
["red", ["redo"]] : "red"
["red", ["redo", "red"]] : "red"
["red", ["red", "redo"]] : "red"
["red", ["red", "redo", "redone"]] : "redone"
["red", ["redo", "red", "redone"]] : "redone"
["red", ["redo", "redone", "red"]] : "red"
["red", ["red", "redone", "redo"]] : "redo"
["red", ["redone", "red", "redo"]] : "redo"
["red", ["redone", "redo", "red"]] : "red"
["a", ["a"]] : "a"
["a", ["b"]] : "a"
["a", ["a", "b"]] : "a"
["a", ["b", "a"]] : "a"
["a", ["ah"]] : "ah"
["a", ["a", "ah"]] : "a"
["a", ["ah", "a"]] : "a"
["art", ["a"]] : "art"
["art", ["a", "b"]] : "art"
["art", ["b", "a"]] : "art"
["art", ["a", "antics"]] : "art"
["art", ["antics", "a"]] : "art"
["art", ["a", "art", "antics"]] : "art"
["art", ["art", "a", "antics"]] : "art"
["art", ["art", "antics", "a"]] : "art"
["art", ["a", "antics", "art"]] : "art"
["art", ["antics", "a", "art"]] : "art"
["art", ["antics", "art", "a"]] : "art"
["art", ["a", "art", "article"]] : "article"
["art", ["art", "a", "article"]] : "article"
["art", ["art", "article", "a"]] : "article"
["art", ["a", "article", "art"]] : "art"
["art", ["article", "a", "art"]] : "art"
["art", ["article", "art", "a"]] : "art"
["art", ["artist", "a", "art", "article"]] : "art"
["art", ["artist", "art", "a", "article"]] : "art"
["art", ["artist", "art", "article", "a"]] : "art"
["art", ["artist", "a", "article", "art"]] : "art"
["art", ["artist", "article", "a", "art"]] : "art"
["art", ["artist", "article", "art", "a"]] : "art"
["art", ["a", "artist", "art", "article"]] : "art"
["art", ["art", "artist", "a", "article"]] : "artist"
["art", ["art", "artist", "article", "a"]] : "artist"
["art", ["a", "artist", "article", "art"]] : "art"
["art", ["article", "artist", "a", "art"]] : "art"
["art", ["article", "artist", "art", "a"]] : "art"
["art", ["a", "art", "artist", "article"]] : "artist"
["art", ["art", "a", "artist", "article"]] : "artist"
["art", ["art", "article", "artist", "a"]] : "article"
["art", ["a", "article", "artist", "art"]] : "art"
["art", ["article", "a", "artist", "art"]] : "art"
["art", ["article", "art", "artist", "a"]] : "art"
["art", ["a", "art", "article", "artist"]] : "article"
["art", ["art", "a", "article", "artist"]] : "article"
["art", ["art", "article", "a", "artist"]] : "article"
["art", ["a", "article", "art", "artist"]] : "art"
["art", ["article", "a", "art", "artist"]] : "art"
["art", ["article", "art", "a", "artist"]] : "art"

Scoring

This is a code golf challenge. Your score is the number of bytes in your code.

Explanations are optional, but I'm more likely to upvote answers that have one.

posted about 1 year ago

CC BY-SA 4.0

8mo ago

trichoplax‭

1020 reputation 83 17 129 471