27
\$\begingroup\$

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:

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:

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]

\$\endgroup\$
22
  • 4
    \$\begingroup\$ Do I understand correctly, that lan glang -> lan glang and lan g lang -> lan g lang, but lan g lan g -> lan g? \$\endgroup\$
    – pajonk
    May 11 at 8:46
  • 8
    \$\begingroup\$ I think this is a really good challenge (seemingly simple, but actually hard), but the hypen rule distracts from the essential puzzle and makes it worse. Since that ship has sailed, you should clarify this sentence: "Any spaces or hyphens that occur between elements of a repeating section must be stripped out, and otherwise retained." It didn't make sense to me, although I understand now what it means by looking at the examples. \$\endgroup\$
    – Jonah
    May 11 at 16:25
  • 7
    \$\begingroup\$ Fun real-world examples: idololatry -> idolatry; cinnamomon -> cinnamon. \$\endgroup\$
    – DLosc
    May 11 at 17:49
  • 4
    \$\begingroup\$ Can you confirm what the correct output would be for "mamapapatatat"? Currently, the Jelly answer outputs "mapatat," the 05AB1E answer outputs "mamapat," and the Python 3.8 answer outputs "mapapat." If I'm understanding the specification correctly, the correct output is "mapapat," because deduplicating "atatat" has the highest priority, followed by "mama." \$\endgroup\$ May 12 at 16:53
  • 6
    \$\begingroup\$ As pointed out there are some edge cases not addressed in the question which existing answers handle differently. Once resolved this is going to take some moderator work to clean up and so I've closed this to prevent additional possibly incorrect answers from coming in. \$\endgroup\$
    – Wheat Wizard
    May 13 at 9:02

5 Answers 5

6
\$\begingroup\$

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.
\$\endgroup\$
5
  • 4
    \$\begingroup\$ I think this handles the string "mamapapatatat" incorrectly. When I do it by hand, I start by selecting the longest repeating sequence ("atatat"). Then it's a tie for longest remaining repeating sequence (between "mama" and "apap"), so I select the leftmost ("mama"). There are no remaining repeating sequences, so finally I deduplicate the sequences I selected, producing a final result of "mapapat." However, your program outputs "mapatat" instead. \$\endgroup\$ May 12 at 15:52
  • \$\begingroup\$ @TannerSwett Good catch! I'm not sure how I didn't read "taking the longest possible sequences first" as literally taking the longest individual sequences, versus longest total region to be processed. \$\endgroup\$ May 12 at 21:38
  • \$\begingroup\$ @TannerSwett I don’t see how “atatat” is a repeated string? “mapatat” is what i would think is correct… \$\endgroup\$
    – Jonah
    May 13 at 14:08
  • \$\begingroup\$ @Jonah "atatat" is a repeating string because it consists of the string "at" repeated three times. \$\endgroup\$ May 13 at 15:30
  • 1
    \$\begingroup\$ @TannerSwett I had interpreted "taking the longest possible sequences first, then working from left to right" as length defined by the length of the repeating thing, in this case at. So here we have ma, pa, and at all tied at 2 chars, and then we work from left to right, so ma and pa get deduped first, giving the final answer mapatat. But it's ambiguous so my interpretation may be wrong. \$\endgroup\$
    – Jonah
    May 13 at 15:46
5
\$\begingroup\$

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

\$\endgroup\$
10
  • 1
    \$\begingroup\$ You might save some bytes with r+=p.group(1) instead of the append call \$\endgroup\$ May 12 at 12:27
  • 1
    \$\begingroup\$ Additionally: * replacing the 2 range calls with one n=range and call to n * similarly replacing calls to len with l=len will save one byte \$\endgroup\$ May 12 at 12:34
  • 1
    \$\begingroup\$ @IvoMerchiers n=range\n + n+n = 10 chars and range + range = 10 chars. Similarly, L=len\n + 3 * L = 9 chars and len * 3 = 9 chars. \$\endgroup\$ May 12 at 13:35
  • 2
    \$\begingroup\$ 196 based on the 209 by @UnrelatedString \$\endgroup\$
    – Jakque
    May 12 at 23:30
  • 1
    \$\begingroup\$ I had to lose (=add) 1 byte because of a bug in atatatat. \$\endgroup\$ May 13 at 7:08
4
\$\begingroup\$

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)
\$\endgroup\$
4
  • 1
    \$\begingroup\$ It looks like there is an issue in the algorithm, as the string "mamapapatatat" should very likely output "mapapat", as discovered by Tanner Swet. Yours answers "mamapat". \$\endgroup\$ May 12 at 20:48
  • 2
    \$\begingroup\$ @OlivierGrégoire Sigh.. This challenge is so dang complex at times. Btw, your Java/Python answers may succeed for mamapapatatat, but they fail for mamapapatatatat (one additional trailing at) -> mapapat, since they both output mapapatat instead. \$\endgroup\$ May 13 at 6:59
  • 2
    \$\begingroup\$ Indeed, I fixed both: the capture group regex was greedy, I made it lazy at the cost of 1 byte for each. A simpler test case was atatatat. Thanks for noticing :) \$\endgroup\$ May 13 at 7:07
  • \$\begingroup\$ Actually and as baffling as it is, mamapapatatatat should indeed return mapapatat as I originally coded, not mapapat as we both thought after you found the issue. \$\endgroup\$ May 15 at 15:40
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 268 (test cases stripped so link could fit) \$\endgroup\$ May 12 at 23:30
3
\$\begingroup\$

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.
\$\endgroup\$
10
  • \$\begingroup\$ Hihi, largely beating Python :D (so far, until my algo is adapted to it) \$\endgroup\$ May 12 at 9:03
  • \$\begingroup\$ Too bad the whakakakakaka test case messes up replacing the Pattern with String.matches/.replaceAll.. :/ Nice answer, though! \$\endgroup\$ May 12 at 13:33
  • 2
    \$\begingroup\$ @KevinCruijssen I cannot remove the replace: no test case uses it, but it would fail on something like this: ababababdsd. \$\endgroup\$ May 12 at 13:45
  • 1
    \$\begingroup\$ Since the input is guaranteed to be lowercase, you can replace the "$" with "$S" and then .replace("$","$s") to .toLowerCase() for -3 bytes. \$\endgroup\$ May 12 at 14:02
  • 1
    \$\begingroup\$ I think the regex suggestion was @Jakque's--I didn't even read the regex lmao \$\endgroup\$ May 13 at 7:44

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.