Change the subject

Question

Sometimes I feel like the conversation is going down the wrong path and take it upon myself to steer it in another direction. And this conversation is going wrong real fast, so I need to change the subject in as few characters as possible.¹

Task

Given a list of sentences, return the sentences ordered such that each sentence "connects" to the next.

For the purposes of this challenge, a sentence is a string, starting with a capital letter, containing words separated by spaces (there won't be punctuation between words), and ending with a period.

Two sentences "connect" if they share at least two common words. For example, the sentences "Once upon a time giraffes roamed the land freely." and "Another species that roamed freely were elephants." connect because they share the words "roamed" and "freely", while the latter sentence does not connect with "I love eating sandwiches." because they do not share any words. Note that the first and last words of the sentence can be compared with the others as well, and the first word starts with a capital letter while the last word ends with a period.

The input is guaranteed to have a valid output. Both an output and its reverse will be valid, so you may output either or both. The input may have multiple valid orders.

This is code-golf, so shortest answer in bytes wins.

Test cases:

You must output the sorted list, but for the sake of brevity I will write the test cases as returning a list of zero-based indices of the original list.

"Once upon a time giraffes roamed the land freely."
"An awful lot of stories start with the phrase once upon a time."
"Another species that roamed freely were elephants."
-> [1, 0, 2] or [2, 0, 1]

"I hear that he is the worst."
"Did you hear that Mr. Jones is running for president."
"He should not be in charge of making our sandwiches."
"The worst sandwiches in the world."
-> [1, 0, 3, 2] or [2, 3, 0, 1]

Please comment suggested test cases, I suck at this.

---

^{1 This is a totally logical explanation for why this is code-golf. 🙈 🙉}

Answer 1

Vyxal, 11 bytes

Ṗ'ɽ⌈Ǎ¨p‡↔ḢA

Try it Online!

Inputs list of all sentences, outputs all ways the sentences could be joined together as sentences.

Explained

Ṗ'ɽ⌈Ǎ¨p‡↔ḢA
Ṗ'           # Keep permutations of the input where:
  ɽ⌈Ǎ        #   Each lowercased sentence split on spaces with punctuation removed
       ‡     #   With:
        ↔Ḣ   #     Set intersection and head remove (which can be used as a len(x) > 1 check)
     ¨p      #   Applied to all overlapping pairs
          A  #   Is all truthy.

Answer 2

05AB1E, 13 bytes

œʒεl¨#}üåO2@P

Input as a list of sentences. Outputs all possible results as a list of lists of sentences.

Try it online or verify all test cases.

Explanation:

œ         # Get all permutations of the (implicit) input-list of sentences
 ʒ        # Filter it by:
  ε       #  Map over each sentence in the current list:
   l      #   Convert it to lowercase
    ¨     #   Remove the trailing period
     #    #   Split it by spaces to a list of words
  }ü      #  After the map: loop over overlapping pairs of lists of words:
    å     #   Check for each word in the second list if it occurs in the first list
     O    #  Sum each inner list of truthy/falsey results together
      2@  #  Check for each inner sum whether it's >= 2
        P #  Product to check whether it's truthy for every overlapping check
          # (after which the filtered list is output implicitly as result)

Answer 3

JavaScript (V8), 131 bytes

Prints all valid solutions.

f=(a,o,p)=>a.map((s,i)=>s.split` `.map(q=w=>q[v=parseInt(w,36)]=v).filter(v=>p?p[v]:1)[1]&&f(a.filter(_=>i--),[o]+s,q))+a||print(o)

Try it online!

How?

The good thing about parseInt(s, 36) is that the strings "abc", "Abc" and "abc." are seen as three variants of the same base-36 number and therefore evaluate to the same value (13368 in that case).

Commented

f = (                 // f is a recursive function taking:
  a,                  //   a[] = list of sentences
  o,                  //   o = output string
  p                   //   p = lookup object for the words in the previous
) =>                  //       selected sentence
a.map((s, i) =>       // for each sentence s at index i in a[]:
  s.split` `          //   turn s into an array of words
  .map(q =            //   let q be an object
  w =>                //   for each word w:
    q[                //
      v =             //     v = result of ...
      parseInt(w, 36) //         ... base-36 parsing of w
    ] = v             //     save it in q
  )                   //   end of map()
  .filter(v =>        //   filter the result:
    p ?               //     if this is not the first iteration:
      p[v]            //       see if v was defined in the previous sentence
    :                 //     else:
      1               //       keep all entries
  )[1] &&             //   end of filter; if we have at least 2 matches:
    f(                //     do a recursive call:
      a.filter(_ =>   //       pass a copy of a[] where
        i--           //       the i-th entry is removed
      ),              //
      [o] + s,        //       append s to o
      q               //       set p = q
    )                 //     end of recursive call
) + a ||              // end of map(); if a[] was empty:
  print(o)            //   print the output string

Answer 4

Japt -g, 18 bytes

á f_˸mn36Ãäf mÅeÊ

Try it

Answer 5

Python, 181 157 bytes

lambda l:[p for p in permutations(l)if(z:=[s.lower()[:-1].split()for s in p],all(sum(k in i for k in j)>1for i,j in zip(z,z[1:])))[1]]
from itertools import*

Attempt This Online!

Returns all valid orders.

• -14 thanks to Steffan

Python, 165 163 159 bytes

def f(l):
 for p in permutations(l):m=[s.lower()[:-1].split()for s in p];any(sum(k in i for k in j)<2for i,j in zip(m,m[1:]))or print(p)
from itertools import*

Attempt This Online!

Based off Kevin Cruijssen's 05AB1E answer. Prints all valid orders.

• -4 thanks to Steffan

Answer 6

Rust, 375 bytes

|a:Vec<&str>|{let b=a.iter().map(|i|&i[..i.len()-1]).collect::<Vec::<_>>();f(&b.join(" "),b)};fn f(w:&str,p:Vec<&str>)->bool{p.len()<1||match p.iter().find(|k|{w.split(" ").collect::<HashSet<_>>().intersection(&k.split(" ").collect()).count()>1&&f(k,p.clone().into_iter().filter(|d|d!=*k).collect::<Vec<_>>())}){Some(u)=>print!("{u}.
")==(),_=>false}}use std::collections::*;

Attempt This Online!

Answer 7

Factor + math.combinatorics math.unicode, 76 73 bytes

[ [ [ " "split ] map 2 clump [ last2 ∩ { } = ] ∄ ] find-permutation ]

Try it online!

• [ ... ] find-permutation Find the first permutation of the input that...
• [ " "split ] map ...when all sentences are split into words...
• 2 clump ...and grouped into overlapping pairs...
• [ last2 ∩ { } = ] ∄ ...none of the intersections between pairs of sentences are empty.

Answer 8

Pip, 41 bytes

PMgFI{$&((LC(aM H_^s)MP{YbaM_Ny})M1N_>1)}

Very golfable, but I'm happy with it.

Attempt This Online!

Explanation:

PMgFI{$&((LC(aM H_^s)MP{YbaM_Ny})M1N_>1)}
PMgFI{                                  } Filter out permutations of the input by ...
          LC(aM H_^s)                     Remove dot, split by space and lowercase each sentence
                     MP{       }          For consecutive pairs of all sentences, 
                        YbaM_Ny           Does each word of the first pair appear in the second pair?
                                 M1N_>1   Is the count of 1s greater than 1 (>= 2)
      $&                                  Are all elements truthy?