17
\$\begingroup\$

(This challenge is related to the challenge "Generate the Abacaba sequence.")

Zimin words (also called "sesquipowers") are an important idea in the subject of "combinatorics on words". This is because every Zimin word is "unavoidable", meaning that every sufficiently long word over a finite alphabet has a substring that is an "instance" (defined below) of the Zimin word. Remarkably, every binary word of length 29 has a substring that is an instance of the pattern \$ABACABA\$.

Definitions

Zimin words are recursively defined:

  • \$Z_1 = A\$
  • \$Z_2 = ABA\$
  • \$Z_3 = ABACABA\$
  • \$Z_4 = ABACABADABACABA\$
  • \$\vdots\$
  • \$Z_{n+1} = Z_n X Z_n\$

It's a little tricky to formally define what it means to be an "instance" for a word without talking about free monoids and homomorphisms, but it's easy enough to see from some examples. At a hand-wave-y level, a word \$w\$ is said to be an "instance" of a pattern if there's a way to assign a (non-empty) string to each letter of the pattern and recover \$w\$.

Examples

Consider the word "11211212211221" on two letters.

  • It has \$105\$ substrings that are instances of the Zimin word \$Z_1 = A\$ because every substring is an instance of \$A\$.
  • It has \$54\$ substrings that are instances of the Zimin word \$Z_2 = ABA\$—for example, the substring "212211221": $$ 11211\underbrace{21}_A\underbrace{22112}_B\underbrace{21}_A. $$
  • It has \$1\$ substring that is an instance of the Zimin word \$Z_3 = ABACABA\$: $$ 11 \underbrace{2}_A \underbrace{11}_B \underbrace{2}_A \underbrace{12}_C \underbrace{2}_A \underbrace{11}_B \underbrace{2}_A 21. $$
  • It has \$0\$ substrings that are instances of the Zimin word \$Z_4 = ABACABADABACABA\$.

Thus if you are given "11211212211221", you should return [105, 54, 1].

Challenge

This challenge will give you a word as an an input, and asks you to output a list of the number of substrings that are instances \$Z_1, Z_2, \cdots, Z_n\$ until there are not any substrings that are instances. That is, your program should never output 0.

You can take the word in any reasonable way: as a string, as a list of strings, as a list of appropriately coded integers, as a pair of integers \$(b,i)\$ where \$i\$ is base-\$b\$ encoded integer, etc.

Test Data

word                           | zimin_counts(word)
-------------------------------+-------------------
""                             | []
"P"                            | [1]
"MOM"                          | [6,1]
"alfalfa"                      | [28, 8]
"aha aha!"                     | [36, 9, 1]
"xxOOOxxxxxOOOxxx"             | [136, 64, 9]
"3123213332331112232"          | [190, 55, 1]
"2122222111111121221"          | [190, 80, 3]
"13121311213121311212"         | [210, 114, 25, 2]
"344112222321431121114"        | [231, 48]
"141324331112324224341"        | [231, 49]
"344342224124222122433"        | [231, 61, 1]
"331123321122132312321"        | [231, 74]
"11221112211212122222122"      | [276, 149, 4]
"2222222112211121112212121"    | [325, 166, 6]
"AAAaaAAAAAAAaAaAAaAaAAAAA"    | [325, 198, 30]
"1100000010010011011011111100" | [406, 204]
"1111221211122111111221211121" | [406, 261, 56, 2]
\$\endgroup\$
4
  • \$\begingroup\$ _ABACABA_ could be a Z₂ with A = ABA, B = C, or it could be a Z₂ with A = A, B = BACAB. Does this count once or twice? \$\endgroup\$ – Neil Mar 14 at 22:48
  • 3
    \$\begingroup\$ ABACABA indeed matches \$Z_2\$ in two different ways, but here we're counting the number of substrings not the number of matches, so it would only be counted once. \$\endgroup\$ – Peter Kagey Mar 14 at 23:05
  • \$\begingroup\$ Not every substring of the example is \$Z_1\$, notably the empty string is not. 105 is still right since there are 120 substrings, of which 15 are empty, but it is a little confusing. \$\endgroup\$ – Wheat Wizard Mar 17 at 12:02
  • \$\begingroup\$ We are also not really "counting substrings" in any of your examples since strings like 1 are counter more than once. I'm not sure what a good way to phrase this is but we are really counting sections of the string, which yield strings. I think it would be good to make this clear because without trying to solve the examples on your own and comparing with the presented results it is not possible to tell that you want the same string counted once for each time it appears. \$\endgroup\$ – Wheat Wizard Mar 17 at 12:07
6
\$\begingroup\$

Brachylog, 30 bytes

{s{h∧1|~cṪ↺₁hʰb=h↰ᶠ⌉+₁}ᵘ}ᶠcọtᵐ

Try it online!

  • {s … }ᶠ for every substring:
  • {h∧1| …} on every non-empty string, return 1. Also try …
  • ~c input split into groups, so that …
  • Ṫ↺₁…b= it unifies with [A,B,A] (this works, too, but is sadly longer).
  • B is non-empty
  • h↰ᶠ take A and call the predicate recursively, finding all results
  • ⌉+₁ get the highest number and add 1
  • Find all unique values. So for aha aha we get [1,2,3] from [aha aha, aha, a].
  • cọtᵐ join the results from all the substrings, count the occurrences of each number, and return them
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Your recent answers just might get me to finally learn some brachylog... \$\endgroup\$ – Jonah Mar 15 at 16:54
  • 1
    \$\begingroup\$ @Jonah Sadly Brachylogonah doesn't really roll off the tongue. :-) \$\endgroup\$ – xash Mar 15 at 19:04
  • \$\begingroup\$ With J, I can use my name unmodified. \$\endgroup\$ – Jonah Mar 15 at 19:50
10
\$\begingroup\$

J, 63 58 53 52 51 47 bytes

_1}.1#.a:~:[:([#~[e.&,(],,)&.>/)^:a:~@;<@(<\)\.

Try it online!

-2 bytes thanks to Bubbler

-3 bytes thanks to FrownyFrog for golfier way to create all substrings of a string.

how

We'll use MOM as our example:

  • [:...;<@(<\)\. All substrings of the input, boxed.

    ┌─┬─┬─┬──┬──┬───┐
    │M│O│M│MO│OM│MOM│
    └─┴─┴─┴──┴──┴───┘
    
  • (...)^:a:~ Using the substrings as both the left and right args ~, apply the verb in parens until a fixed point, keeping track of each iteration's results ^:a:.

  • (...(],,)&.>/) To create the next "level" of candidates, create all possible combinations that look like <level_n><orig substring><level_n> where level_n is any element from the current level, and <orig substring> is one of the original input substrings (level 0). Then the 1st level looks like:

    ┌─────┬─────┬─────┬───────┬───────┬─────────┐
    │MMM  │OMO  │MMM  │MOMMO  │OMMOM  │MOMMMOM  │
    ├─────┼─────┼─────┼───────┼───────┼─────────┤
    │MOM  │OOO  │MOM  │MOOMO  │OMOOM  │MOMOMOM  │
    ├─────┼─────┼─────┼───────┼───────┼─────────┤
    │MMM  │OMO  │MMM  │MOMMO  │OMMOM  │MOMMMOM  │
    ├─────┼─────┼─────┼───────┼───────┼─────────┤
    │MMOM │OMOO │MMOM │MOMOMO │OMMOOM │MOMMOMOM │
    ├─────┼─────┼─────┼───────┼───────┼─────────┤
    │MOMM │OOMO │MOMM │MOOMMO │OMOMOM │MOMOMMOM │
    ├─────┼─────┼─────┼───────┼───────┼─────────┤
    │MMOMM│OMOMO│MMOMM│MOMOMMO│OMMOMOM│MOMMOMMOM│
    └─────┴─────┴─────┴───────┴───────┴─────────┘
    
  • [#~[e.&,... Check if each original substring is an element of this candidate list [e.&,, and use that to filter the original substrings [#~. In the above example, only MOM passes.

  • After the above process iterates to its fixed point (no more matches), the result is:

    ┌───┬─┬─┬──┬──┬───┐
    │M  │O│M│MO│OM│MOM│
    ├───┼─┼─┼──┼──┼───┤
    │MOM│ │ │  │  │   │
    ├───┼─┼─┼──┼──┼───┤
    │   │ │ │  │  │   │
    └───┴─┴─┴──┴──┴───┘
    
  • a:~: Since we don't want to count empty boxes, we perform an elementwise test for "not equal to the empty box a:", giving us a 0-1 matrix:

    1 1 1 1 1 1
    1 0 0 0 0 0
    0 0 0 0 0 0
    
  • 1#. Sum rows:

    6 1 0
    
  • _1}. And kill the last element:

    6 1
    
\$\endgroup\$
4
  • 2
    \$\begingroup\$ [,,~ -> ,,[ to save a byte. \$\endgroup\$ – Bubbler Mar 15 at 3:28
  • 2
    \$\begingroup\$ Another -1: ([(e.&,#[)(],,)&.>/) -> ([#~[e.&,(],,)&.>/) \$\endgroup\$ – Bubbler Mar 15 at 6:01
  • 1
    \$\begingroup\$ _1}.1#.a:~:[:([#~[e.&,(],,)&.>/)^:a:~@;<@(<\)\. \$\endgroup\$ – FrownyFrog Mar 15 at 12:10
  • 1
    \$\begingroup\$ @FrownyFrog It's funny, I actually woke up this morning thinking... "I bet I could have done something with \\. to save some bytes", and then saw your post :) \$\endgroup\$ – Jonah Mar 15 at 13:14
8
\$\begingroup\$

JavaScript (ES6),  148 142  141 bytes

Saved 6 bytes thanks to @user81655

Expects an array of characters.

f=(a,o=[],s='')=>a.map(c=>{for(s+=c,i=p='';s.match(`^${p+='(.+)'+p.replace(/\(.../g,_=>"\\"+n++)}$`);n=1)o[+i]=-~o[i++]})+a?f(a.slice(1),o):o

Try it online!

How?

For each substring in the input string, we apply the following patterns while they match:

P₀  ^(.+)$
P₁  ^(.+)(.+)\1$
P₂  ^(.+)(.+)\1(.+)\1\2\1$
P₃  ^(.+)(.+)\1(.+)\1\2\1(.+)\1\2\1\3\1\2\1$
    ...

Apart from the delimiters ^ and $ which are ignored below, these patterns are built recursively as follows:

  • \$P_0\$ is (.+)

  • \$P_{k+1}\$ is \$P_{k}\$, followed by (.+), followed by \$P_k\$ with each \$n\$-th group (.+) replaced with the back reference \{n} (1-indexed)

    e.g. for \$P_2 \rightarrow P_3\$:

    (.+)(.+)\1(.+)\1\2\1 -> (.+)(.+)\1(.+)\1\2\1 (.+) (.+)(.+)\1(.+)\1\2\1
                                                       \1  \2    \3

It's worth noting that:

  • if a substring matches some \$P_i\$, it also matches all \$P_j,\:j<i\$
  • if a substring doesn't match some \$P_i\$, it also won't match any \$P_j,\:j>i\$

We keep track of the results in the array o[], which is eventually returned. Whenever \$P_i\$ matches a substring, we increment o[i].

\$\endgroup\$
4
  • \$\begingroup\$ 142 bytes \$\endgroup\$ – user81655 Mar 17 at 7:15
  • \$\begingroup\$ @user81655 Nice! I tend to use more for loops in my recent answers but didn't attempt to do it here. \$\endgroup\$ – Arnauld Mar 17 at 8:30
  • \$\begingroup\$ Will it fail if Z[10] exists? \$\endgroup\$ – l4m2 Mar 17 at 8:33
  • \$\begingroup\$ @l4m2 The regex will eventually overflow on very large strings, but \10 is legal in JS. \$\endgroup\$ – Arnauld Mar 17 at 8:38
2
\$\begingroup\$

Retina, 77 bytes

K`(.+)
/\(/{G`
%"$+"~`^
w`
"¶0"(Am`^0
K`

$+2
(.*?\))+(.*)$
$&¶$&(.+)$2\$#1$2

Try it online! No test suite because of the advanced use of result history. Explanation:

K`(.+)

Start by considering matches of Z₁.

/\(/{`

Repeat while the working area contains a (.

G`

Do nothing. This is here solely to record the value at the start of each pass of the loop in the stage history, so that it can be referred to later on.

%"$+"~`^
w`

Processing each line of regex separately, evaluate it as an overlapped count command on the original input, thereby returning a list of counts.

"¶0"(`

If the list contains a 0 (strictly speaking this can only happen on the second pass, as I use a newline to check that it's a leading 0)...

Am`^0

... then delete all 0 values (including the first if the input string was empty), otherwise:

K`

$+2

Retrieve the value saved in step 2. (Because Retina numbers stages in post-order traversal, this is the G command.) Unfortunately $ doesn't work directly in a K command, so the easiest way to do this is to delete the result and then substitute the empty string with the saved value.

(.*?\))+(.*)$
$&¶$&(.+)$2\$#1$2

Append an additional regex that matches the next Zimin word.

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

05AB1E, 31 bytes

āεo<VŒε.œYùεĆ4ô€¨yªεÂQ}P}1å]O0Ü

Try it online or verify some more test cases (pretty slow, so the larger test cases are omitted in the test suite).

Explanation:

Step 1: Loop over the possible sizes \$n\$ of the \$Z_n\$ based on the input-length.

We can calculate the valid \$n\$ to check with the following formula: \$m = \left\lceil\log_2(L)\right\rceil\$, where \$L\$ is the input-length, and the result \$m\$ indicates the range \$[1,m]\$ to check for Zimin 'words': \$Z_{n=1}^m\$.

In 05AB1E code, this would have resulted in g.²îLεo<VŒε.œYùεĆ4ô€¨yªεÂQ}P}1å]O0Ü (35 bytes): try it online.

Since we have to strip trailing 0s at the end in case no \$Z\$ were found for them anyway, we simply don't calculate this maximum. Instead, we'll just check in the range \$[1,L]\$ for Zimin words. Less efficient in terms of performance, but 4 bytes shorter, which is all we care about with . :)

We can also calculate the amount of parts in the resulting Zimin 'word' (\$Z_n\$), which is the oeis sequence A000225: \$2^n-1\$.

ā              # Push a list in the range [1, (implicit) input-length]
 ε             # Map over each of these integers:
  o            #  Take 2 to the power this integer
   <           #  Decrease it by 1
    V          #  Pop and store this in variable `Y`

Step 2: For each of these amount of parts \$Y\$, we check how many substrings of the input are valid Zimin 'words' (\$Z_Y\$).

Step 2a: We do this by first generating all substrings of the input, and mapping over them:

  Π           #  Get all substrings of the (implicit) input-list
   ε           #  Inner map over each substring:

Step 2b: Then we'll get all partitions of the current substring of exactly \$Y\$ amount of parts:

    .œ         #   Get all partitions of this subtring
      Yù       #   Only leave the partitions of `Y` amount of parts

Step 2c: We then check for each of these (correctly sized) partitions of this substring if it's a valid Zimin 'word'.
We do this by checking two things:

  1. Is the current list of parts in this partition a palindrome?
  2. Is every \$ABA\$ part within the current partition a palindrome?

As for step 2c2, we do so by first adding a dummy trailing item to the partition; then splitting the partition-list into sublists of size 4; then we remove the trailing item from each of these sublists; after which we can check for each \$[A,B,A]\$ sublist whether it's a palindrome.

        ε      #   Inner map over each remaining partition:
         Ć     #    Enclose the partition; append its own first part at the end
          4ô   #    Split the partition into parts of size 4
            ۬ #    Remove the final part of each quartet
         yª    #    Append the full partition to this list of triplets as well
           ε   #    Inner map over this list of lists:
               #     Check if the current list is a palindrome by:
            Â  #      Bifurcating: short for Duplicate & Reverse copy
             Q #      Check if the list and reversed copied list are the same
           }   #    After this inner-most map:
            P  #    Check if all were truthy by taking the product

Alternatively for step 2c2, Ć4ô€¨ could have been 4ô3δ∍ instead: Split the partition-list into sublists of size 4 (with 3 in the trailing sublist); shorten each sublist to size 3 by removing trailing item(s); same as above. Try it online.

Step 2d: And we then check if there is at least one valid Zimin 'word' (\$Z_Y\$) among the mapped partitions for this substring:

       }       #   After the map over the partitions of the current substring:
        1å     #   Check if any were truthy by checking if it contains a 1
               #   (NOTE: we can't use the max builtin `à` here like we usually do when
               #    we want to mimic an `any` builtin, because lists could be empty here,
               #    resulting in an empty string)

Step 3: Now we sum the amount of truthy results per size \$Y\$:

]              # Close all remaining nested maps
 O             # Sum the inner-most lists together

Step 4: And finally we clean-up all trailing 0s (both the \$\geq m\$ sizes we've checked in our golfed approach, as well as any trailing \$Z\$ within the \$[1,m]\$ range that simply resulted in \$0\$), before outputting the result:

  0Ü           # Remove any trailing 0s from this list
               # (after which the resulting list is output implicitly)
\$\endgroup\$
1
\$\begingroup\$

Python 3, 205 bytes

def f(w):
 R=range(len(w));s=[w[i:j+1]for i in R for j in R[i:]];v=[*s];n=len(s);r=[]
 while n:r+=[n];s={i+j+i for i in s for j in v if i+j+i in w};n=sum(len({w.find(a,b)for b in R})-1for a in s)
 return r

Try it online!

Quite verbose.
Inputs a string and returns a list of the number of substrings that are instances \$Z_1, Z_2, \dots, Z_n\$.

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