Small Chatbot challenge

The Challenge :

You have a list conversations, in which each element is a conversation that is represented as an array of words. You need to create a chatbot that will complete a conversation that is currently in progress, currentConversation.

To do that, the chatbot must find the conversation from the given list that has the largest number of unique words that match with words from the currentConversation. If there are several conversations that match this condition, the chatbot should use the one that appears first in conversations. If no conversation from the list contains any matching words from currentCoversation, the chatbot should leave currentConversation as it is.

If there is a conversation that can complete currentConversation, the chatbot should find the first word in it that appears after all the matching words. The chatbot should then append this word, along with all the words that follow it in that conversation, to currentConversation.

Return the final state of currentConversation.

Example

For conversations = [ ["where", "are", "you", "live", "i", "live", "in", "new", "york"], ["are", "you", "going", "somewhere", "tonight", "no", "i", "am", "too", "tired", "today"], ["hello", "what", "is", "your", "name", "my", "name", "is", "john"]] and currentConversation = ["hello", "john", "do", "you", "have", "a", "favorite", "city", "to", "live", "in", "yes", "it", "is"], the output should be chatBot(conversations, currentConversation) = ["hello", "john", "do", "you", "have", "a", "favorite", "city", "to", "live", "in", "yes", "it", "is", "new", "york"].

The second conversation has only one matching word, "you". But the other two conversations both have three unique matching words. In the first conversation, the matches are "you", "live", and "in". In the third conversation, the matches are "hello", "john", and "is". Since we have two options that could complete our current conversation, we should choose the one that appears earlier in the list, so we use the first conversation. In that conversation, the last matching word is "in", so we add the last two words, "new" and "york", to currentConversation to complete it.

For conversations = [ ["lets", "have", "some", "fun"], ["i", "never", "get", "it"], ["be", "aware", "of", "this", "house"], ["he", "will", "call", "her"]] and currentConversation = ["can", "you", "please"], the output should be chatBot(conversations, currentConversation) = ["can", "you", "please"].

None of the conversations have any words that match words in currentConversation, so we add nothing to it.

Input/Output

[time limit] 4000ms (py3) [input] array.array.string conversations

An array of conversations, where each conversation is represented as an array of strings. Each string contains only lowercase English letters.

Guaranteed constraints:

• 1 ≤ conversations.length ≤ 104
• 1 ≤ conversations[i].length < 100
• 1 ≤ conversations[i][j].length ≤ 15

[input] array.string currentConversation

The conversation in progress, which needs to be completed by the chatbot. Each string contains only lowercase English letters.

Guaranteed constraints:

• 1 ≤ currentConversation.length ≤ 100
• 1 ≤ currentConversation[i].length ≤ 15

[output] array.string

The completed currentConversation.

MY SOLUTION ok i compiled it, it works but it is not fast enough

def is_unique(word,wlist):
nb = 0
for w in wlist:
if w == word:
nb = nb+1
if nb == 1:
return True
return False

def find_max(conversations_stats):
maxs = conversations_stats[0]
ind_max = 0
for x in range(1,len(conversations_stats)):
if conversations_stats[x] > maxs:
maxs = conversations_stats[x]
ind_max = x
return ind_max, maxs

def chatBot(conversations, currentConversation):
rslt = currentConversation
lc = len(conversations)
conversations_stats = [0 for i in range(lc)]
conversations_li = [0 for i in range(lc)]
#for x in range(lc):
for x, wlist in enumerate(conversations, start=0):   # Python indexes start at zero
#wlist  = conversations[x]
#wl = len(wlist)
conversations_li[x]=0
conversations_stats[x] = 0
#for y in range(wl):
for y, a_word in enumerate(wlist, start=0):
#a_word = wlist[y]
if a_word in currentConversation:
if is_unique(a_word,wlist):
conversations_stats[x] = conversations_stats[x] + 1
conversations_li[x]=y

#print('word c'+str(conversations_li[x])+' cc'+str(x)+' :'+a_word)

# ok the one with max unique matching
ind_max, maxs = find_max(conversations_stats)
#seaching for the last match
#print(maxs)
if maxs == 0:
return rslt
else:
wlist  = conversations[ind_max]
cl=len(wlist)
for k in range(conversations_li[ind_max]+1,cl):
rslt.append(wlist[k])
return rslt
return rslt

• I got a feeling that this question belongs on stackoverflow – MaLiN2223 Nov 4 '17 at 11:39
• Just posted it on StackOverflow stackoverflow.com/questions/47109831/… And a reviewer there said that I should post it here !! – Aness Nov 4 '17 at 11:48
• Fine, if this is the case we will answer it here ;) – MaLiN2223 Nov 4 '17 at 12:01
• @MaLiN2223 Why did you think it would be more appropriate for Stack Overflow? – Mast Nov 4 '17 at 13:59
• @MaLiN2223 Well, we got 4.4k questions in performance, so it should be fine here. Yes, if the question is specifically about the algorithm and not about the rest of the code, it should be more appropriate on Stack Overflow. But it isn't phrased as such, so Stack Overflow rejects it and points to us. It should be just fine here :-) – Mast Nov 4 '17 at 15:43

Assuming wlist is a flat list of words, the is_unique() function could be written as follows:

def is_unique(word, wlist):
return wlist.count(word) == 1


I would write the find_max() function like so:

def find_max(conversations_stats):
ind_max = conversations_stats.index(conversations_stats[-1])
maxs = max(conversations_stats)
return ind_max, maxs

• Thanks for ur reply :), For now I wrote def find_max(array): smax = array[0] ind = 0 for i in range(len(array)): if array[i] > smax: smax = array[i] ind = i return smax, ind Your suggestion looks better, I just tried it and it seems to be missing an import ! for the function max(conversations_stats) on my python server – Aness Nov 4 '17 at 15:58
• @Aness, max() is a built-in function. You don't have to import it. Please try help(max). – Srisaila Nov 4 '17 at 16:25
• Ur right, I used a limited swift based online compiler instead of my usual debian Python, sorry :) – Aness Nov 4 '17 at 16:50

Maybe I'm the one who is confused, but I think you have misunderstood the phrase "unique words from x". It doesn't mean "the set of words in x that appear only once", it means "the set of words in x, with each word presented only once". So, for instance, the unique words in ["where", "are", "you", "live", "i", "live", "in", "new", "york"] are ["where", "are", "you", "live", "i","in", "new", "york"].

My solution:

def chatBot(conversations, currentConversation):
best_conversation = None
best_match_count = 0
current_words = set(currentConversation)
for conversation in conversations:
conversation_words = set(conversation)
match_count = sum([word in conversation_words for word in current_words])
if match_count > best_match_count:
best_match_count = match_count
best_conversation = conversation
if best_conversation is None:
return(currentConversation)
last_match = max([i for i in range(len(best_conversation)) if [best_conversation[i] in currentConversation])
if last_match == len(best_conversation)-1:
return(current_conversation)
return(currentConversation+best_conversation[last_match+1:]