14
\$\begingroup\$

The challenge is to write a simple chatbot which can complete the curr_conv (current-conversation) with the help of a collection of conversations, all_conv. Both curr_conv and all_conv are array of downcased English words.

Procedure

To complete the curr_conv, the bot should find a conversation from all_conv that has the largest number of unique words that match with words in curr_conv

  • In case of multiple matches, the bot should take the first one that appears in all_conv
  • If none of them matches, then leave curr_conv as it is

If there is a suitable conversation, then the bot should find the first word, that appears after all the matching words. The chatbot should then append all the following words starting with this word, to curr_conv

Finally, return the curr_conv

Examples

  • For,
all_conv = [
    ["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"]
]
curr_conv = ["hello", "john", "do", "you", "have", "a", "favorite", "city", "to", "live", "in", "yes", "it", "is"]

Output would be,

["hello", "john", "do", "you", "have", "a", "favorite", "city", "to", "live", "in", "yes", "it", "is", "new", "york"]

As we can see, the first and third conversation in all_conv have three, unique matching words, therefore the first one is required to complete the curr_conv


  • For,
all_conv = [
    ["lets", "have", "some", "fun"],
    ["i", "never", "get", "it"],
    ["be", "aware", "of", "this", "house"],
    ["he", "will", "call", "her"]
]
curr_conv = ["can", "you", "please"]

Output would be,

["can", "you", "please"]

As, none of the conversations in all_conv matches any word with curr_conv


  • For,
all_conv = [
    ["foo", "bar"],
    ["foo", "foo"],
    ["bar", "foo"]
]
curr_conv = ["foo", "foo"]

Output would be,

["foo", "foo", "bar"]

As, all of them have 1 unique word, i.e., "foo" in common, hence the first conversation will complete curr_conv

Test cases

# in
all_conv = [
    ["it","is","my","favorite","movie"], 
    ["really","i","did","not","know"]
]
curr_conv = ["what", "you", "think", "about", "this", "movie"]

# out
["what", "you", "think", "about", "this", "movie"]
# in
all_conv = [
    ["tonight","i","need","dollar","bills"], 
    ["i","dont","keep","fun"], 
    ["cheap","thrills","long","to","feel","money"], 
    ["the","bills","dont","need","the","dancing","baby"], 
    ["fun","dollar","dancing","thrills","the","baby","i","need"], 
    ["dont","have","fun"], 
    ["no","no","dont","have","dancing","fun","tonight"]
]
curr_conv = ["beat", "the", "can", "as", "i", "dont", "feel", "thrills"]

# out
["beat", "the", "can", "as", "i", "dont", "feel", "thrills", "need"]
# in
all_conv = [
    ["where", "are", "in", "live", "i", "live", "you", "new", "york"],
    ["are", "you", "going", "somewhere", "tonight", "no", "i", "am", "too", "tired", "today"],
    ["hello", "what", "is", "your", "name", "my", "name", "is", "john"]
]
curr_conv = ["hello", "john", "do", "you", "have", "a", "favorite", "city", "to", "live", "in", "yes", "it", "is"]

# out
["hello", "john", "do", "you", "have", "a", "favorite", "city", "to", "live", "in", "yes", "it", "is", "new", "york"]
# in
all_conv = [
    ["fame","is","you","like","what","in","the","limo"], 
    ["fame","what","you","get","is","no","tomorrow"], 
    ["fame","what","you","need","you","have","to","borrow","fame"], 
    ["fame","its","mine","its","mine","its","just","his","line"], 
    ["to","bind","your","time","it","drives","you","to","crime"]
]
curr_conv = ["what", "is"]

# out
["what", "is", "in", "the", "limo"]

This is a , so fewest bytes will win!

\$\endgroup\$
  • \$\begingroup\$ How did you come up with the example conversations? \$\endgroup\$ – xigoi Nov 16 at 11:49
  • \$\begingroup\$ @xigoi - this was from an old book GrownUps puzzle which I found yst \$\endgroup\$ – vrintle Nov 16 at 12:34
  • \$\begingroup\$ If all_conv=[["foo","bar"]] and curr_conv=["foo","foo"], does it count as one or two matching words? In other words, do we 1) count the number of unique matching words in all_conv for each word in curr_conv independently, or 2) look for the size of the intersection? Or 3) are the words in curr_conv guaranteed to be unique? \$\endgroup\$ – Arnauld Nov 16 at 13:42
  • 1
    \$\begingroup\$ @vrintle So if all_conv=[["foo","foo"]] and curr_conv=["foo","foo"], is that one or two matches? It would be helpful to provide testcases with all kinds of duplicates. \$\endgroup\$ – xigoi Nov 16 at 13:56
  • 1
    \$\begingroup\$ Except for the “golfing” part, this sounds a lot like the “travesty” programs of several decades ago. wg20.criticalcodestudies.com/index.php?p=/discussion/92/… \$\endgroup\$ – WGroleau Nov 18 at 3:39

11 Answers 11

11
\$\begingroup\$

JavaScript (ES6), 109 bytes

Expects (all_conv)(curr_conv).

a=>c=>a.map(b=>[...b].map(w=>(l+=c[I='includes'](b.shift())&!b[I](w))>m&&(m=l,o=[...c,...b]),l=0),m=0,o=c)&&o

Try it online!

Commented

a => c =>                 // a[] = all_conv, c[] = curr_conv
a.map(b =>                // for each list of words b[] in a[]:
  [...b].map(w =>         //   for each word w in a copy of b[]:
    (                     //
      n +=                //     increment n if:
        c[I = 'includes'] //       c[] includes ...
        (b.shift()) &     //       ... the next entry extracted from b[] (which is w)
        !b[I](w)          //       and this is the last instance of w in b[]
    ) > m && (            //     if n is greater than m:
      m = n,              //       set m to n
      o = [...c, ...b]    //       set the output to c[] followed by b[]
    ),                    //
    n = 0                 //     start with n = 0
  ),                      //   end of inner map()
  m = 0,                  //   start with m = 0
  o = c                   //   and o[] = c[]
) && o                    // end of outer map(); return o[]
| improve this answer | |
\$\endgroup\$
8
\$\begingroup\$

05AB1E, 19 bytes

δåOZDĀikèõª¹¡θ¹ìáë¹

First input is curr_conv, second input is all_conv.

Try it online or verify all test cases.

Explanation:

δ                 # Apply double-vectorized on the two (implicit) inputs
 å                #  Check if the list contains the current word

This results in a list of lists of truthy/falsey values, where each truthy/falsey value represents whether the word of curr_conv is present in the inner list of the all_conv.

Try just this first part online.

  O               # Sum each inner list to get the amount of matched words
   Z              # Get the maximum of this (without popping the list itself)
    D             # Duplicate this maximum
     Āi           # If it's NOT 0:
       k          #  Get the (first) index of this maximum in the list of sums
        è         #  And use that to index into the (implicit) second input all_conv

Now we have the (first) inner list of all_conv that contains the most unique words of curr_conv.

Try just the first two parts online.

         õª       #  Append an empty string to this list
           ¹¡     #  Then split it by each word of the first input curr_conv

Try just the first three parts online.

             θ    #  Pop it, and only leave the last inner list
              ¹ì  #  Prepend the curr_conv in front of it
                á #  And only leave letters to remove the empty trailing string
      ë           # Else (none of the words of curr_conv are in all_conv):
       ¹          #  Simply push the first input
                  # (after which the top of the stack is output implicitly as result)

NOTE: The õª and á are a work-around for when the list of all_conv with the most unique words contains one of the words as trailing item (like the test case with output ["what", "you", "think", "about", "this", "movie"]), because the ¡ won't have a trailing empty item in that case: Try it online vs Try it online without the õª...á.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Maybe add that ending note in the osabie tips thread. \$\endgroup\$ – Razetime Nov 16 at 16:05
7
\$\begingroup\$

Jelly, 17 bytes

ṚfQLɗÞṪṫẹⱮFṀɗ¥Ḋ⁹;

A dyadic Link accepting all_conv (a list of lists of lists of characters) on the left and curr_conv (a list of lists of characters) on the right which yields the altered curr_conv (a list of lists of characters).

Try it online! Or see the test-suite.

How?

ṚfQLɗÞṪṫẹⱮFṀɗ¥Ḋ⁹; - Link: all, curr
Ṛ                 - reverse (all)
     Þ            - sort by:
    ɗ             -   last three links as a dyad:
 f                -     filter keep
  Q               -     de-duplicate
   L              -     length
      Ṫ           - tail
             ¥    - last two links as a dyad:
            ɗ     -   last three links as a dyad:
         Ɱ        -     map with:
        ẹ         -       indices of
          F       -     flatten
           Ṁ      -     maximum (0 if empty)
       ṫ          - tail from (there) (final word only if 0)
              Ḋ   - dequeue
               ⁹  - chain's right argument, curr
                ; - concatenate
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

Python 3, 96 bytes

lambda a,c:c+max([[*{*s}&{*c},s[max([-1,*map(s.index,{*s}&{*c})]):][1:]]for s in a],key=len)[-1]

Try it online!

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

Stax, 19 bytes

æ;í²'^8τ}gAαögQl╝ε╟

Run and debug it(all test cases)

query first, sentences last, separated by a comma.

Explanation

;{x|&u%}EhcJsx|&H/HxJs+
;                       Push the sentences
 {     }E               max by the following:
  x|&                   Intersection with query string
     u%                 length of all unique words
         h              take the first one of those
          cJ            duplicate, and join tdup with spaces
            s           swap with the list
             x|&        take intersection with query string
                H       Take last element
                 /      and split the copy on that
                  H     take the second part of that
                   xJ   push the input, joined with spaces
                     s+ concatenate the two         
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

Perl 5, 140 bytes

sub{($C,$A,$a,@e)=@_;$$a[0]<($x=--$n+9e9*grep$_~~@$C&&!$s{$n,$_}++,@$_)and$a=[$x,@$_]for@$A;unshift@e,pop@$a until!@$a||$$a[-1]~~@$C;@$C,@e}

Try it online!

ungolfed:

sub{
  ($C,$A,$a,@e)=@_;
  $$a[0] < ($x = --$n + 9e9*grep$_~~@$C&&!$s{$n,$_}++,@$_)
    and $a = [$x,@$_]
    for @$A;
  unshift @e, pop@$a until !@$a || $$a[-1]~~@$C;
  @$C,@e
}
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Jelly, 25 23 bytes

;ɓ³œ&QLƲÐṀḢṫẹⱮF©Ṁ‘ʋ¥¹®ȧ

Try it online!

Dyadic link that takes the current conversation as the left argument and the list of conversations as the right argument.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ @vrintle I think I fixed it. \$\endgroup\$ – xigoi Nov 16 at 15:03
2
\$\begingroup\$

Ruby 2.7, 72 bytes

->(a,c,f=a.max_by{(_1&c).size}){c+f[f.rindex{(c&f).any?_1}+1..]rescue c}

Try it online!

TIO uses an older version of Ruby, so _1 is used in place of |i|i, saving 2 bytes, twice. Further, endless range i.. is used instead of i..-1, saving 2 more bytes.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

R, 106 105 95 bytes

Edit: -10 bytes thanks to Giuseppe

function(c,a,s=sapply,b=a[[which.max(colSums(s(a,'%in%',x=c)))]])c(c,b[0:-max(s(c,match,b,0))])

Try it online!

How?

chat=
function(c,a,                       # c=curr_conv, a=all_conv
 s=sapply,                          # alias to sapply() function
 d<-colSums(sapply(a,`%in%`,x=c))   # d=number of matching words in each conversation
 b=a[[which.max(d)]]                # b=conversation with most matching words
                                    #   (first of ties; so first one if none match)
)
c(c,                                # output concatenation of curr_conv with
 b[                                 # the elements of b 
  0:-                               # excluding (negative indices) all up to
  max(sapply(c,match,b,0))          # highest index of a matching word (or zero if no match)
 ])
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ function(c,a,s=sapply,b=a[[which.max(d<-colSums(s(a,'%in%',x=c)))]])c(c,b[0:-max(s(c,match,b,0))]) is 98 (too long to post a TIO link in the comments) \$\endgroup\$ – Giuseppe Nov 18 at 22:27
  • 1
    \$\begingroup\$ @Giuseppe - Thanks! and now it doesn't need d any more, either, so down to 95! \$\endgroup\$ – Dominic van Essen Nov 18 at 22:35
1
\$\begingroup\$

Charcoal, 45 bytes

Fθ⊞υΣEη∧№ικ⁼λ⌕ηκ≔§θ⌕υ⌈υθF✂θ∨⌈ΦEη⌈⊕⌕AθιιLθ⊞ηιη

Try it online! Link is to verbose version of code. Feels far to long, but that's edge cases for you. Explanation:

Fθ⊞υΣEη∧№ικ⁼λ⌕ηκ

For each conversation, count the number of unique words that also appear in the current conversation.

≔§θ⌕υ⌈υθ

Get the best match conversation.

F✂θ∨⌈ΦEη⌈⊕⌕AθιιLθ⊞ηι

Find the last word that matched the current conversation, and push the subsequent words, if any.

η

Output the resulting conversation using the default output format of one word per line.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Scala, 190 bytes

type S=Seq[String];def f(c:S,a:Seq[S])={val s=a.map(s=>(s,(s.toSet&c.toSet).size)).fold((Seq[String](),0)){(m,s)=>if(s._2>m._2)s else m}._1;c++s.slice(s.lastIndexWhere(c.toSet(_))+1,s.size)}

Try it online!

Same, just a little more readable:

def f( c:Seq[String], a:Seq[Seq[String]] ) = {
  val s=a.map(s=>(s,(s.toSet&c.toSet).size))
         .fold((Seq[String](),0)){ (m,s) => if(s._2>m._2) s else m}
         ._1
  c ++ s.slice( s.lastIndexWhere(c.toSet(_))+1, s.size )
}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.