11
\$\begingroup\$

Stuttering is a problem which many of us might have experienced or at least seen it. Although most of famous speech recognition softwares have serious issues with stuttered speaking, let's imagine a software which understands stuttering, but cannot fix them and only writes them as is.

An example written text by such a software can be like this: "please be ca ca careful". In this example "careful" is the original word and "ca ca" are the stuttered words.

Challenge

Write a program or function that fixes stuttered words by removing them from the input while keeping the original words. For example fixed version of "please be ca ca careful" would be "please be careful".

This is , shortest answer in every language wins!

What are stuttered words?

Stuttering has many different variations. But for simplicity of this challenge, we are going to limit it to the following rules:

  • Stuttered words can be an uncompleted part or whole of the original word. By "uncompleted part" I mean that the original word should start exactly with the stuttered word. For example "ope" and "open" both can be a stuttered word for "open", but "pen" cannot be one since "open" doesn't start with "pen".
  • Stuttered words must contain at least one of the "aeiou" vowels. For example "star" can be a stuttered word for "start" as it contains "a", but "st" cannot be a stuttered word as it doesn't contain any of the mentioned vowels.
  • Stuttered words can only appear before the original word and should be repeated at least two times to be valid (the original word doesn't count in the repeats). For example "o o open" has stuttered words but "o open o" doesn't, because the "o" after the original word doesn't count and "o" before the original word is not repeated at least two times. "go go go go go go" has five repeats of stuttered words before the original word and is valid.
  • A single set of repeated stuttered words cannot contain mixed forms and the words should be exactly like each other. For example "op o op open" doesn't count as stuttered words. On the other hand "o op op open" has stuttered words because the first "o" is seen as a whole different word here and the two "op"s are counted as stuttered words of "open".
  • In case of multiple valid sets of repeated stuttered words right after each other, only the last original word stays. For example, in "o o o op op op open", the "o o o" part is seen as stuttered words of the first "op", so they should be removed and then "op op op" is seen as stuttered words of "open" and they should be removed too, so only the "open" will be left after removal of stuttered words. You can assume that multiple valid sets of repeated stuttered words only happen from left to right, so fixing "op op o o o open" would result in "op op open" (a.k.a. we do not fix again after fixing once).

Input

  • Input is a single line string containing only ASCII English letters (a-z), digits (0-9) and space characters. Letter casing is not important and you can decide to accept lowercase or uppercase or both of them, but the casing should stay the same and you cannot change it in the output.
  • You can use a list of letters (like ["l","i","s","t"," ","o","f"," ","l","e","t","t","e","r","s"]) instead of the string, but you cannot use a list of words. If your language has a different input structure, use it. The point is that input shouldn't be separated by words, so cost of separating words in some languages might actually trigger other creative solutions.
  • The input might contain none, one or multiple stuttered words in it.
  • Words and or numbers are separated by a single space and input will not contain double spaces right next to each other.

Output

  • A string or a list of letters or the appropriate structure in your language with all stuttered words removed from the input.
  • Output words should be separated by exactly one space (same as input).
  • Single leading and trailing newline or space are allowed.

Standard loopholes are forbidden.

Test cases

No stuttered words:

"hello world" => "hello world"

A single instance of repeated stuttered words:

"ope ope ope ope open the window" => "open the window"

Multiple instances of repeated stuttered words:

"there is is is is something un un under the the the table" => "there is something under the table"

No stuttered words, not repeated enough:

"give me the the book" => "give me the the book"

No stuttered words, don't have any of the mentioned vowels:

"h h help m m m me" => "h h help m m m me"

Numbers aren't stuttered words, they don't have any of the mentioned vowels:

"my nu nu number is 9 9 9 9876" => "my number is 9 9 9 9876"

But a word with both vowels and numbers can have stuttered words:

"my wi wi windows10 is slow" => "my windows10 is slow"

Different forms of stuttered words in same repeat group aren't counted:

"this is an ant antarctica does not have" => "this is an ant antarctica does not have"

For multiple continuous sets of stuttered words right after each other, only keep the last original word:

"what a be be be beauti beauti beautiful flower" => "what a beautiful flower"

This isn't a case of multiple continuous sets of stuttered words right after each other:

"drink wat wat wa wa water" => "drink wat wat water"

Empty input:

"" => ""

More cases from comments:

"a ab abc" => "a ab abc"
"a ab ab abc" => "a abc"
"ab ab abc abcd" => "abc abcd"
"a a ab a able" => "ab a able"
"i have ave ave average" => "i have average"
"my wi wi windows 10 is cra cra crap" => "my windows 10 is crap"

An easy to copy list of the above test cases:

"hello world",
"ope ope ope ope open the window",
"there is is is is something un un under the the the table",
"give me the the book",
"h h help m m m me",
"my nu nu number is 9 9 9 9876",
"my wi wi windows10 is slow",
"this is an ant antarctica does not have",
"what a be be be beauti beauti beautiful flower",
"drink wat wat wa wa water",
"",
"a ab abc",
"a ab ab abc",
"ab ab abc abcd",
"a a ab a able",
"i have ave ave average",
"my wi wi windows 10 is cra cra crap"
\$\endgroup\$
  • 2
    \$\begingroup\$ "drink wat wat wa wa water" => "drink wat wat water" it really seems like the rule should apply recursively so that this becomes "drink water" \$\endgroup\$ – Jonah Sep 19 at 15:59
  • 2
    \$\begingroup\$ @Jonah if you read the last item under What are stuttered words? I have explained this matter. "wat wat" are not stuttered words for "wa" and we only fix once, so once we get "drink wat wat water", we don't fix again to remove newly formed stuttered words. But in a reverse case like "wa wa wat wat water" result will be "water" because "wa wa" are stuttered words for the first "wat" and "wat wat" are also stuttered words of "water". \$\endgroup\$ – Night2 Sep 19 at 16:02
  • \$\begingroup\$ Ok fair enough, I was just saying it would make sense to keep fixing until you couldn't any more, but I can see the argument for focusing on a single iteration as well. \$\endgroup\$ – Jonah Sep 19 at 16:04
6
\$\begingroup\$

C (gcc), 183 180 178 bytes

f(s,t,u,T,e,r)char*s,*t,*u,*r;{for(;s=index(u=s,32);T>1&strpbrk(u,"aeiou")-1<s&&memmove(s=u,t-e,r-t-~e))for(e=++s-u,r=u+strlen(t=u),T=0;(t+=e)<r&!memcmp(u,t,e-1)&t[-1]==32;++T);}

Try it online!

Well, C certainly can't compete with the brevity of regex...

This one's particularly tough to read because I ended up collapsing the entire function into a single nested pair of for loops (with no body!). That makes the evaluation order all wonky -- the code near the beginning actually executes last.

My favorite trick here is strpbrk(u,"aeiou")-1<s. This is used to check whether the repeated word contains vowels. u points to the start of the repeated word, and s points to the second repetition of the word; for example:

"my nu nu number is 9 9 9 9876"
    ^  ^
    u  s

strpbrk then finds the first character in "aeiou" that appears after u. (In this case, it is the 'u' immediately after.) Then we can check that this comes before s to verify the word contains a vowel. But there's a slight issue - strpbrk returns NULL (i.e. 0) if there's no vowel in the entire string. To fix this, I simply subtract 1, which turns 0 into 0xffffffffffffffff (on my machine) due to overflow. Being the maximum value of a pointer, this is decidedly greater than s, causing the check to fail.

Here's a slightly older version (before the transformation that muddled up control flow) with comments:

f(s,t,u,c,n,e)char*s,*t,*u,*e;{
    // set s to the position of the *next* check; u is the old position
    for(;s=index(u=s,32);) {
        // count the length of this word (incl. space); also fix s
        n=++s-u;
        // find the end of the string; assign temp pointer to start
        e=u+strlen(t=u);
        // count repetitions of the word
        for(c=0;                // number of repetitions
            (t+=n)              // advance temp pointer by length of word
            <e&&                // check that we haven't hit the end...
            !strncmp(u,t,n-1)&& // ...and the word matches...
            t[-1]==32;          // ...and the previous character was space
            ++c);               // if so, increment count
        // decide whether to remove stuttering
        c>1&&                    // count must be at least 2
        strpbrk(u,"aeiou")-1<s&& // word must contain a vowel
        // if so, move everything after the last occurrence back to the
        // beginning, and also reset s to u to start scanning from here again
        memmove(s=u,t-n,e-t+n+1);
    }
}

Thanks to @user1475369 for 3 bytes and @ceilingcat for 2 bytes.

\$\endgroup\$
  • \$\begingroup\$ -3 bytes by replacing T>1&&strpbrk with T>1&strpbrk, r&&!strncmp with r&!strncmp, and &&t[-1] with &t[-1]. \$\endgroup\$ – girobuz Sep 21 at 3:31
  • \$\begingroup\$ tio.run/##bVHbjpswEH3PV0yRGtnBSEtW6kWs@xV5a/… \$\endgroup\$ – girobuz Sep 21 at 3:32
  • \$\begingroup\$ @ceilingcat Your link fails some of the test cases, but 2 of those 3 optimizations work; thanks! \$\endgroup\$ – Doorknob Sep 21 at 15:30
  • \$\begingroup\$ Suggest bcmp() instead of memcmp() \$\endgroup\$ – ceilingcat Sep 30 at 4:56
4
\$\begingroup\$

Perl 5 (-p), 34 bytes

Based on Arnauld's deleted answer.

s/(\b(\w*[aeiou]\w*) )\1+(?=\2)//g

Try it online!

\$\endgroup\$
  • \$\begingroup\$ This produces "zab" for "za a ab". I don't think there should be a stutter detected in that input. \$\endgroup\$ – recursive Sep 19 at 17:39
  • \$\begingroup\$ @recursive thanks, fixed. \$\endgroup\$ – Grimmy Sep 19 at 17:50
  • 2
    \$\begingroup\$ I looked at the test cases and devised a regex, only to find it already here. Naturally this means that the trivial Retina port is 30 bytes. \$\endgroup\$ – Neil Sep 19 at 20:14
3
\$\begingroup\$

05AB1E, 30 29 28 bytes

-1 byte thanks to Kevin Cruijssen

#Rγε®y¬©žMÃĀiнkĀDygαΘ+∍]R˜ðý

Try it online!

05AB1E, having no regexes, definitely doesn't look like the best tool for this task. Still, it somehow manages to just barely beat Retina.

#                     # split on spaces
 R                    # reverse the list of words
  γ                   # group consecutive identical words together

ε                   ] # for each group of words y:
 ®                    #  push the previous word on the stack (initially -1)
  y                   #  push another copy of y
   ¬                  #  push the first element without popping
    ©                 #  save the current word for the next loop
     žM               #  built-in constant aeiou
       ÃĀi          ] #  if the length of the intersection is non-zero:
           н          #   take the first element of y
            kĀ        #   0 if the previous word starts with this word, 1 otherwise
              D       #   duplicate
               yg     #   length of y (the number of consecutive identical words)
                 α    #   subtract the result of the startsWith check
                  Θ   #   05AB1E truthify (1 -> 1, anything else -> 0)
                   +  #   add the result of the startsWith check
                    ∍ #   set the length of y to that value
                      #  otherwise leave y unchanged

˜                     # flatten the modified list of groups of words
 R                    # reverse the list of words
  ðý                  # join with spaces
\$\endgroup\$
  • 1
    \$\begingroup\$ You can remove the g before the Ā. Python-style truthify will already result in 0 for empty strings and 1 for non-empty strings. \$\endgroup\$ – Kevin Cruijssen Sep 23 at 8:19
  • \$\begingroup\$ @KevinCruijssen nice find! \$\endgroup\$ – Grimmy Sep 23 at 8:37
1
\$\begingroup\$

Perl 6, 45 bytes

{S:g/<|w>(\S*<[aeiou]>\S*)\s$0+%%\s{}<?$0>//}

Try it online!

A simple regex answer that substitutes all matches of stutters with the empty string.

\$\endgroup\$
1
\$\begingroup\$

Stax, 26 bytes

å╬↓<▀.₧▀"╦n▐∞↨vß%ù:Qa3@=↔_

Run and debug it

Direct port from @Grimy's perl answer. Stax is able to shrink the regex pattern literal, and it has a vowels constant which is able to shrink [aeiou].

\$\endgroup\$
1
\$\begingroup\$

Clean, 184 bytes

import StdEnv,Data.List,Text
$s=join[' '](f(group(split[' ']s)))
f[[a]:t]=[a:f t]
f[h=:[a:_]:t=:[[b:_]:_]]|intersect['aeiou']a==[]=h++f t|isPrefixOf a b=f t=if(h>[a,a])[a]h++f t
f[]=[]

Try it online!

Defines $ :: [Char] -> [Char], which splits the input string on spaces and groups identical elements which are then collapsed by the helper f :: [[[Char]]] -> [[Char]], joining before returning.

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