1
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Why not house house_where where, since house where appears twice? (Actually, I think the example output does not match the example input.) \$\endgroup\$ – Arnauld Sep 1 at 19:38
  • 3
    \$\begingroup\$ @BobvanLuijt So that clarifies what characters are allowed, but I'm still not clear how punctuation or other characters affect what's considered a separate word. \$\endgroup\$ – xnor Sep 1 at 20:18
  • 2
    \$\begingroup\$ So basically a word is a sequence of non-whitespace characters? \$\endgroup\$ – Arnauld Sep 1 at 20:28
  • 2
    \$\begingroup\$ Is the count overlapping or not? i.e does milk milk occur twice or once in milk milk milk? (I'd guess twice so "yes" but I don't know) \$\endgroup\$ – Jonathan Allan Sep 1 at 20:36
  • 1
    \$\begingroup\$ Perfect; thanks \$\endgroup\$ – Bob van Luijt Sep 1 at 20:59
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ ...but milk milk milk - count is non-overlapping; is that OK? \$\endgroup\$ – Jonathan Allan Sep 1 at 20:33
  • \$\begingroup\$ @Jonathan Allan: Hmm... OP has yet to weigh in, but I don't like that milk milk milk doesn't work with this code... thinking... \$\endgroup\$ – Chas Brown Sep 1 at 20:48
  • \$\begingroup\$ Also be incorrect with compound words, like a bun and a bunny though. \$\endgroup\$ – Jonathan Allan Sep 1 at 20:51
  • \$\begingroup\$ Okay, fixed now at a cost of 8 bytes... \$\endgroup\$ – Chas Brown Sep 1 at 20:52
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Thanks @Arnauld, would you mind explaining a bit more in-depth about how it works? \$\endgroup\$ – Bob van Luijt Sep 1 at 20:23
  • \$\begingroup\$ ...also milk milk milk... I've asked under the question for clarification. \$\endgroup\$ – Jonathan Allan Sep 1 at 20:39
  • \$\begingroup\$ @JonathanAllan Thanks for pointing this out. Now fixed. \$\endgroup\$ – Arnauld Sep 2 at 20:21
1
\$\begingroup\$

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.

\$\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.