5
\$\begingroup\$

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
\$\endgroup\$
6
  • \$\begingroup\$ I got a feeling that this question belongs on stackoverflow \$\endgroup\$ Commented Nov 4, 2017 at 11:39
  • \$\begingroup\$ Just posted it on StackOverflow stackoverflow.com/questions/47109831/… And a reviewer there said that I should post it here !! \$\endgroup\$ Commented Nov 4, 2017 at 11:48
  • \$\begingroup\$ Fine, if this is the case we will answer it here ;) \$\endgroup\$ Commented Nov 4, 2017 at 12:01
  • \$\begingroup\$ @MaLiN2223 Why did you think it would be more appropriate for Stack Overflow? \$\endgroup\$ Commented Nov 4, 2017 at 13:59
  • 3
    \$\begingroup\$ @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 :-) \$\endgroup\$ Commented Nov 4, 2017 at 15:43

2 Answers 2

Reset to default
2
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ 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 \$\endgroup\$ Commented Nov 4, 2017 at 15:58
  • \$\begingroup\$ @Aness, max() is a built-in function. You don't have to import it. Please try help(max). \$\endgroup\$ Commented Nov 4, 2017 at 16:25
  • \$\begingroup\$ Ur right, I used a limited swift based online compiler instead of my usual debian Python, sorry :) \$\endgroup\$ Commented Nov 4, 2017 at 16:50
1
\$\begingroup\$

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:]
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.