Haplololololololology!

Question

Haplology

Haplology is a linguistic term:

the omission of one occurrence of a sound or syllable that is repeated within a word, for example probly for probably.

For this challenge, it means specifically, replacing any sequences of two or more letters that are repeated two or more times with just one copy.

For example:

• haplology -> haplogy
• boobook -> book
• couscous -> cous
• ngorongoro -> ngoro
• hehehe -> he
• whakakakakaka -> whaka
• lerderderg -> lerderg

If there are multiple, non-overlapping repeating sequences, they all get replaced:

• cancangogo -> cango
• yadayadablahblah -> yadablah

Only a single round of replacements is performed, taking the longest possible sequences first, then working from left to right:

• mississippi -> missippi
• mymememymemebooboo -> mymemeboo
• aaaabaaaab -> aaaab

This means the returned result can contain repeating sequences:

• babambambadingding -> babambading

It cans also mean the end result is longer that it would be if replacement happened strictly left to right:

• bababababababadoobababababababadoo -> bababababababadoo (not badoobadoo)

Any spaces or hyphens that occur between elements of a repeating section must be stripped out, and otherwise retained:

• lang lang -> lang
• cha-cha-cha -> cha
• hi-di-hi-di-hi-di-ho -> hi-di-ho
• tut-tutting -> tutting
• lady gaga -> lady ga
• banana-cocoa agar agar -> bana-coa agar
• who put the bop in the bop shoo bop shoo bop who put the dip in the dip da dip da dip -> who put the bop in the bop shoo bop who put the dip in the dip da dip
• hare krishna hare krishna krishna krishna hare hare hare rama hare rama rama rama hare hare -> hare krishna krishna hare hare rama rama hare

Challenge

Write a function/program/etc which applies haplology, as defined above, to a single input string.

Inputs and outputs

Each input will match this regex: ^[a-z]([a-z -]?[a-z])*$

Your output is a lowercase string containing the haplologised input. No extraneous characters.

Standard rules for taking input and output.

Scoring

Code golf. Standard rules and exclusions apply.

Updates

Additional test cases and clarification

The algorithm (ignoring punctuation) is:

• find the longest chunk of letters that is repeated at least twice, giving precedence to the left-most chunk
• replace those repeated chunks with one chunk
• repeat, until none left
• never allow any any letter to be processed as part of different chunks

• mamapapatatat -> mapatat (there is no duplicated sequence longer than 2 characters, so work left to right: mama, papa, tata)
• babababa -> baba ([baba] x2)
• ratratatat -> ratat ([rat] x2, [at] x2)

Questions

Why does babambambadingding give babambading instead of bambading (from [baba][mbamba][dingding])?

In order of priority, the chunks are [ding], [bam]. The chunk [mba] is the same length as [bam], but [bam] occurs to its left.

Why doesn't the "hare krishna" test case greedily take the third consecutive hare?

Because the longer [hare rama] takes precedence over the shorter [hare]

Answer 1

Jelly, 45 38 bytes

ḷⱮjⱮƤ““ “-”ẎʋƤṖe@€i1ḣ@ȯ
ŒṖÇƑÐḟẈṢṚƲÞṪÇ€

Try it online!

Should be correct for real this time thanks to Tanner Swett.

Should be correct for real this time.

It's even less performant now! Now designed from the ground up to handle spaces and hyphens, but there's got to be a shorter way to do ““ “-”...

ḷⱮjⱮƤ““ “-”ẎʋƤṖe@€i1ḣ@ȯ    Monadic helper link: de-n-plicate an entire string
            ʋƤ             For each prefix of the argument:
 Ɱ                         create a list of, for each element of the argument
              Ṗ            but one,
ḷ                          a copy of the prefix;
    Ƥ                      for each prefix of that list,
  j                        join the copies on
   Ɱ ““ “-”                each of the empty string, a space, and a hyphen;
           Ẏ               flatten the results.
               e@€         Check if the argument is in each of those,
                  i1       get the first index of 1,
                    ḣ@     and return the argument truncated to that length
                      ȯ    or unchanged if it's 1 long and got clobbered.

ŒṖÇƑÐḟẈṢṚƲÞṪÇ€    Main link
ŒṖ                All ways to partition the input.
         ƲÞ       Sort them by
      Ẉ           the lengths
       ṢṚ         sorted descending of
    Ðḟ            the slices which are not
   Ƒ              unchanged by
  Ç               the helper link,
          Ṫ       take the last,
           ǀ     and map the helper over its slices.

Answer 2

05AB1E, 45 bytes

.œεDü2εËyε„ -SNiÛëÜ}}Ë~y€g≠P*}Zi_1šÏJë¯]˜éIªн

Very slow, but should work for all test cases including those in the comments.

Try it online or verify some of the smaller test cases. (Some of the test cases are slightly modified in the test suite.)

Explanation:

.œ             # Get all partitions of the (implicit) input-string
  ε            # Map over each partition-list:
   D           #  Duplicate the partition-list
    ü2         #  Get the overlapping pairs of the strings
      ε        #  Map over each pair:
       Ë       #   Check if both strings in the pair are the same
       y       #   Push the pair again
        ε      #   Map over it:
         „ -S  #    Push pair ["-"," "]
         Ni    #    If the inner map-index is 1 (thus the right item):
           Û   #     Strip the leading "-"/" "
          ë    #    Else (it's 0, thus the left item):
           Ü   #     Strip the trailing "-"/" "
          }    #    Close the if-else statement
        }Ë     #   After the inner-most map: check if both values are the same
             ~ #   Check if either of the two checks is truthy
       y       #   Push the pair yet again
        €g     #   Get the length of each part
          ≠    #   Check for each length that it's NOT 1
           P   #   Take the product to check whether it's truthy for both
            *  #   Check if both checks are truthy
      }        #  Close the inner map
       Z       #  Push the maximum (without popping the list)
        i      #  Pop, and if this is truthy:
         _     #   Invert all booleans in the list
          1š   #   Prepend an additional leading 1
            Ï  #   Only leave the string-parts at the truthy indices
             J #   And join them together to a string
        ë      #  Else:
         ¯     #   Push an empty list instead
  ]            # Close the if-else statement and outer map
   ˜           # Flatten to remove all empty lists
    é          # Sort the strings by length
     Iª        # Append the input in case it's empty
       н       # Pop and leave the first/shortest one
               # (which is output implicitly as result)

Answer 3

Python 3.8 (pre-release), 196 bytes

import re
def f(s,*r):
 for l in range(-len(s),-2):
  for i in range(len(s)-~l):
   if p:=re.match("(\w[\w -]*\w)(-? ?\\1)+$",x:=s[i:i-l]):s=re.sub(x,"{%s}"%len(r),s);r+=p[1],
 return s.format(*r)

Try it online!

Credits

• Port of my Java answer.
• -8 bytes, thanks to Blue
• -5 bytes, thanks to Ivo Merchiers
• -25 bytes, thanks to Unrelated String
• -2 bytes, thanks to Jakque

Answer 4

Java (JDK), 308 bytes

s->{var r=new java.util.Stack();for(int l=s.length(),i;l>1;l--)for(i=0;i<=s.length()-l;){var x=s.substring(i,l+i++);var p=java.util.regex.Pattern.compile("(\\w[\\w -]*\\w)(-? ?\\1)+").matcher(x);s=p.matches()&&r.add(p.group(1))?s.replace(x,"%"+r.size()+"$S"):s;}return"".format(s.toLowerCase(),r.toArray());}

Try it online!

Explanation

This algorithm takes all substrings that exist, from longest, to smallest and checks if that one is a repetition with spaces or dashes. If it is, it takes the repeated value and stores it in a list (the Stack in the code) and replaces that long substring to something with special characters (%1$S with 1 being any number, actually) so that it's not matched anymore later on.

After all repetitions are found, the string, taken as lowercase, is actually a formattable that can be properly formatted to wrap up the replacements with String.format.

Credits

• -3 bytes thanks to Kevin Cruijssen.
• -3 bytes by backporting Jakque's regex suggestion from my Python answer.

Answer 5

Python3, 283 bytes:

R,L=range,len
def f(s):
 m=[]
 for x in R(L(s)):
  for y in R(x+2,L(s)):
   S=s;T=s[x:y];K=0;X=x
   while S[(F:=(X+(X<L(S)and S[X]in[' ','-']))):][:L(T)]==T:K+=1;X=F+L(T)
   if K>1:m+=[[s[:x],T,len(T*K),s[X:]]]
 return s if[]==m else f((M:=max(m,key=lambda x:x[2]))[0])+M[1]+f(M[-1])

Try it online!

A no-import solution in Python.