Concatenate the Cats

Question

There is a sentence with many cats:

there is a cat house where many cats live. in the cat house, there is a cat called alice and a cat called bob. in this house where all cats live, a cat can be concatenated into a string of cats. The cat called alice likes to purr and the cat called bob likes to drink milk.

The Task

Concatenate (_) all pairs of neighbouring words in the sentence and place each in between the any such pair if that pair occurs more than once in the sentence. Note that overlapping counts, so blah blah occurs twice in blah blah blah.

For example, if the cat occurs more then once, add the concatenated words in between them like this: the the_cat cat

Example Output

there there_is is is_a a a_cat cat cat_house house where many cats live. in the the_cat cat cat_house house,
there there_is is is_a a a_cat cat cat_called called called_alice alice and a a_cat cat cat_called called called_bob bob.
the the_cat cat cat_called called called_alice alice likes likes_to to purr and the the_cat cat cat_called called called_bob bob likes likes_to to drink milk.

Some more examples:

milk milk milk       milk milk_milk milk milk_milk milk
a bun and a bunny    a bun and a bunny
milk milk milk.      milk milk milk.
bun bun bun bun.     bun bun_bun bun bun_bun bun bun.

Notes

• All utf-8 characters are allowed. Meaning that punctuations are part of the input.
• Punctuation becomes part of the word (e.g., with in the house, is a cat the word house, includes the comma)

Answer 1

Python 2, 99 107 103 102 bytes

def f(s):S=s.split();T=zip(S,S[1:]+[s]);return' '.join(x+(' '+x+'_'+y)*(T.count((x,y))>1)for x,y in T)

Try it online!

Fixed the milk milk milk style edge cases.

Answer 2

Jelly,  23 22 21  18 bytes

Ḳµżj”_$ƝḢKċ@Ị¥?€`K

A full program which prints the output.

Try it online! Or see a test-suite.

How?

Ḳµżj”_$ƝḢKċ@Ị¥?€`K - Main Link: list of characters T
Ḳ                  - split (T) at spaces (call this W)
 µ                 - start a new monadic chain (i.e. f(W))
       Ɲ           - for neighbouring pairs:
      $            -   last two links as a monad:
   j               -     join with...
    ”_             -     ...underscore character
  ż                - zip (with W) (making pairs of ["left", "left_right"]
                   -               plus a trailing ["rightmost"])
                `  - use this as both left and right arguments of:
               €   -   for each:
              ?    -     if...
             ¥     -     ...condition: last two links as a dyad:
           @       -       with swapped arguments:
          ċ        -         count occurrences of right in left
            Ị      -       is insignificant? (abs(x) <= 1)
        Ḣ          -     ...then: head (   ["left", "left_right"] -> "left"
                   -                    or ["rightmost"] -> "rightmost")
         K         -     ...else: join with space (["same", "same_same"] -> "same same_same")
                 K - join with space characters
                   - implicit print

Answer 3

Zsh, 103 bytes

t=($=1)
for b a (${${t:1}:^t})s+=(${a}_$b)
for w ($s)((++i,${#s:#$w}-$#s+1))||s[i]=
echo ${t:^s} $t[-1]

Try it online!

The key constructs used here are:

• ${=1}: splits the first parameter into words (because there are no other flags, the {braces} are optional)
• ${a:^b}: substitutes array $a zipped with array $b
• ${a:#b}: substitutes array $a with all instances of b removed.
• ${# }: the length of the contained expansion.
• echo: <<< leaves extra spaces

If the input is already split into words, 99 bytes.

Answer 4

Jelly, 32 27 bytes

;⁶Ḳṡ2W€jj”_W$Ɗ€ĠL’$ƇẎƊ¦Ṗ€ẎK

Try it online!

Shorter and more correct! Thanks to @JonathanAllan for highlighting an issue with "milk milk milk"!

A monadic link that takes a Jelly string as its argument and returns a processed Jelly string.

Explanation

;⁶                          | Append a space
  Ḳ                         | Split at spaces
   ṡ2                       | Sliced of length 2
                     Ɗ¦     | At the indices indicated by the following:
               Ġ            | - Group indices of equal values
                   Ƈ        | - Keep only those where the following is non-zero:
                L           |   - Length
                 ’          |   - Decrease by 1
                    Ẏ       | - Tighten (join outermost lists together)
             Ɗ€             | Do the following as a monad:
     W€                     | - Wrap each word in a list
       j    $               | - Join with the following:
        j”_                 |   - The two words joined with "_"
           W                |   - Wrapped in a list
                       Ṗ€   | Remove last member of each list
                         Ẏ  | Tighten (join outermost lists)
                          K | Join with spaces

Answer 5

JavaScript (ES6), 94 bytes

s=>s.split` `.map((w,i,a)=>a.some((W,j)=>j!=i&W==w&a[j+1]==(p=a[i+1]))?w+` ${w}_`+p:w).join` `

Try it online!

Answer 6

J, 69 bytes

;:inv@(a:-.~],@,.a:,~(2(,'_'&,)&.>/\])#&.>~1<1#.[:=/~2<\])' '<;._1@,]

Try it online!

J, 56 bytes (but breaks on commas)

(a:-.~],@,.a:,~(2(,'_'&,)&.>/\])#&.>~1<1#.[:=/~2<\])&.;:

Try it online!

explanation for both

A bit verbose but the underlying idea is nice, so I'll explain that with pictures:

Let's start with this input:

low in xx xx low in bun bun bun bun.

First we turn it into words:

┌───┬──┬──┬──┬───┬──┬───┬───┬───┬────┐
│low│in│xx│xx│low│in│bun│bun│bun│bun.│
└───┴──┴──┴──┴───┴──┴───┴───┴───┴────┘

And then create the underscore concatenation of every pair, plus a blank item at the end:

┌──────┬─────┬─────┬──────┬──────┬──────┬───────┬───────┬────────┬┐
│low_in│in_xx│xx_xx│xx_low│low_in│in_bun│bun_bun│bun_bun│bun_bun.││
└──────┴─────┴─────┴──────┴──────┴──────┴───────┴───────┴────────┴┘

Let's zip these together and see where we're at:

┌────┬────────┐
│low │low_in  │
├────┼────────┤
│in  │in_xx   │
├────┼────────┤
│xx  │xx_xx   │
├────┼────────┤
│xx  │xx_low  │
├────┼────────┤
│low │low_in  │
├────┼────────┤
│in  │in_bun  │
├────┼────────┤
│bun │bun_bun │
├────┼────────┤
│bun │bun_bun │
├────┼────────┤
│bun │bun_bun.│
├────┼────────┤
│bun.│        │
└────┴────────┘

We notice that if we could keep just the items we want in the right column, we could flatten the whole thing, unbox, and we'd be done.

So we want a filter for the right column. Let's start by treating the consecutive pairs of input words as single units (again, with a blank at the end):

┌────────┬───────┬───────┬────────┬────────┬────────┬─────────┬─────────┬──────────┬┐
│┌───┬──┐│┌──┬──┐│┌──┬──┐│┌──┬───┐│┌───┬──┐│┌──┬───┐│┌───┬───┐│┌───┬───┐│┌───┬────┐││
││low│in│││in│xx│││xx│xx│││xx│low│││low│in│││in│bun│││bun│bun│││bun│bun│││bun│bun.│││
│└───┴──┘│└──┴──┘│└──┴──┘│└──┴───┘│└───┴──┘│└──┴───┘│└───┴───┘│└───┴───┘│└───┴────┘││
└────────┴───────┴───────┴────────┴────────┴────────┴─────────┴─────────┴──────────┴┘

The filter we seek is simply any element that occurs more than once. To find this we'll create a function table of equality:

1 0 0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
1 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1

And sum it rowise or colwise (the direction doesn't matter, since it's symmetric):

2 1 1 1 2 1 2 2 1 1

And find all entries greater than 1:

1 0 0 0 1 0 1 1 0 0

This filter is all we need to carry out our plan from above and arrive at the answer.