Possible periods of input

Question

Background:

Take this input as an example:

1 1 2 1 1 2 1 3 1 3

If you look only at the first few digits, between 1 1 2 and 1 1 2 1 1 2 1, this input appears to consist of the pattern 1 1 2 repeating indefinitely. This would make its period 3, as there are 3 numbers in the pattern.

Given only the first number, the period appears to be 1, as only the number 1 is in the input. Given the first two numbers, it still appears to be the number 1 repeating, so the period does not change.

Task:

Given an array of numbers (or strings, or similar), determine the period of each prefix of the array, and return the unique ones. For example, the above input would have periods of:

1 1 3 3 3 3 3 8 8 10

Thus, the output would be:

1 3 8 10

I/O:

Input should be an array of any set of a large number of different values. For example, numbers, strings, natural numbers, or pairs of integers. Booleans wouldn't be allowed, but chars/bytes would.

Output can be any reasonable representation of the numbers, such as an array/list, or a string with the numbers joined by newlines.

Test cases:

1                     ->  1
1 2 1 1 2 1           ->  1 2 3
1 1 2 1 1 2 1         ->  1 3
1 2 1 2 1 2 1 2 4     ->  1 2 9
1 2 3 4 1 2 3 1 2 1   ->  1 2 3 4 7 9
4 4 4 4 4 4 4 4 4 4   ->  1

Answer 1

J, 23 bytes

1+[:~.(i.~]{~#\|/i.@#)\

Try it online!

We do the heavy lifting of creating the periods using integers, and then use those to index into our input. Specifically...

• (...)\ For each prefix:

  • #\|/i.@# Create a table of indexes to represent the possible periods. An example should make this clear:

      (#\|/i.@#) 1 1 2 3 1 1 2 3
    0 0 0 0 0 0 0 0
    0 1 0 1 0 1 0 1
    0 1 2 0 1 2 0 1
    0 1 2 3 0 1 2 3
    0 1 2 3 4 0 1 2
    0 1 2 3 4 5 0 1
    0 1 2 3 4 5 6 0
    0 1 2 3 4 5 6 7
    

  • ]{~ Pull these indexes from the input:

    1 1 1 1 1 1 1 1
    1 1 1 1 1 1 1 1
    1 1 2 1 1 2 1 1
    1 1 2 3 1 1 2 3   <-- Input matches here, index 3.
    1 1 2 3 1 1 1 2
    1 1 2 3 1 1 1 1
    1 1 2 3 1 1 2 1
    1 1 2 3 1 1 2 3
    

  • i.~ And find the index of the original input within this list. In this case, that index is 3.

• [:~. De-dup.

• 1+ And add one.

original approach, 24 bytes

[:~.1+i.&1@(-:"1#$&><\)\

Try it online!

Answer 2

Jelly, 6 bytes

ṁƤi$ƤQ

A monadic Link accepting a list that yields a list of the unique period lengths.

Try it online! Or see the test-suite.

How?

ṁƤi$ƤQ - Link: list, A
    Ƥ  - for each prefix (p in A):
   $   -   last two links as a monad - f(p):
 Ƥ     -     for each prefix (x in p):
ṁ      -       mould like (p)
             -> Z = list of copies of x each "extended" to the length of p
  i    -     first 1-indexed index (of p in Z)
     Q - de-duplicate

Answer 3

R, 88 82 81 bytes

unique(Map(function(i)Find(function(j)all(a[1:i]==a[1:j]),1:i),seq(a=a<-scan())))

Try it online!

Thanks to Giuseppe for fixing a mistake and -6 bytes.

Answer 4

Jelly, 10 bytes

¹Ƥṁ€ẹƊṂ$ƤQ

Try it online!

Explanation

¹Ƥṁ€ẹƊṂ$ƤQ  Main Link
[....].$    Group these two into one monad so Ƥ runs the whole link
            to its left

[][].Ɗ      Group these three into one monad so it accepts the link
            left argument as the right argument to ẹ instead of
            grouping ẹṂ into a dyad-monad monadic link

        Ƥ   For each prefix of the list: let it be the "sublist":
¹Ƥ          Map identity over prefixes; get all prefixes of the
            sublist
  ṁ€        Mold each prefix to the shape of the sublist; repeat
            elements until the two lists are the same length
    ẹ       Find all indices of the original sublist in the list
            of looped prefixes; essentially, find all prefixes
            that work for the period
      Ṃ     Take the minimum of these; this returns the period
         Q  Deduplicate; find only unique potential periods

Answer 5

JavaScript (Node.js), 69 bytes

a=>a.flatMap(x=>(j=1/a.some(v=>v-a[++j],j=i++)+j)>p?(p=j,i):[],i=p=0)

Try it online!

a=>a.flatMap(x=>                   // for i := 1 to a.length do
(j=1/a.some(v=>v-a[++j],j=i++)+j)  //   j := prefix size of repeating first i elements;
>p?(p=j,i):[]                      //   if j > p then p := j; add `i` to answer; endif;
,i=p=0)                            // endfor

Answer 6

05AB1E, 13 bytes

ηε¼ηÅΔ¾∍Å?]>Ù

Try it online!

Commented:

η              # push all prefixes of the input
 ε        ]    # iterate over all prefixes:
  ¼            #   increment the counter variable
   ηÅΔ    ]    #   find the index of the first prefix of the prefix which satisifies:
      ¾∍       #     if extended to the length of the outer prefix (value of the counter variable)
        Å?     #     this is a prefix of the (implicit) input
               #     (and therefore equal to the outer prefix)
           >   # increment the 0-based indices
            Ù  # only keep unique ones

Answer 7

JavaScript (ES6), 73 bytes

Returns a set.

a=>new Set(a.map((_,i)=>(g=m=>a.some((v,j)=>j<=i&&v^a[j%m])?g(-~m):m)``))

Try it online!

Commented

a =>                   // a[] = input array
new Set(               // build a set from the following array:
  a.map((_, i) =>      //   for each value at position i in a[]:
    ( g = m =>         //     g is a recursive function taking a modulo value m
      a.some((v, j) => //       check if there's some element in a[]:
        j <= i &&      //         that it is not located beyond the position i
        v ^ a[j % m]   //         and is not equal to the element at j modulo m
      ) ?              //       end of some(); if truthy:
        g(-~m)         //         recursive call with m + 1
      :                //       else:
        m              //         return m
    )``                //     initial call to g with m zero'ish
  )                    //   end of map()
)                      // end of Set()

Answer 8

Stax, 15 bytes

┼↓Φ:'ñ╪⌐ñ∟M╕LbN

Run and debug it

Output is as a string representing the codepoints of each period. Pretty printed with spaces for verification.

Explanation

|[{c|[{n%:mn=}j%mu
|[                 prefixes of input
  {             m  map to
   c|[             dup and take prefixes
      {      }j    first element which satisfies:
       n%:m        when extended to current iteration length
           n=      equals the current iteration?
               %   take the length
                 u uniquify

Answer 9

Brachylog, 18 14 bytes

{a₀{ġz₁=ᵐ!}l}ᵘ

Try it online!

-4 because I remembered which zip I was using

{           }ᵘ    Find every unique output from:
 a₀               for some prefix of the input,
    ġ             split it into groups of the same length except the last can be shorter
   {     !}       with that length being the smallest possible for which
     z₁           the non-cycling zip of the groups
       =ᵐ         contains only elements all elements of which are equal;
           l      output the length.

Answer 10

APL (Dyalog Unicode), 50 bytes

{∪{1⍳⍨⍵[⍴⍵]≡¨⍵}¨{L←⍴,⊃⌽⍵⋄L⍴¨⍵}¨{⍺,⍵}\¨{⍺,⍵}\⊂∘⍕¨⍵}

I'm fairly certain there's room for improvement, but it's just out of my reach, for the moment.

∪ ⍝ list unique values
 1⍳⍨ ⍝ get the index value of the first occurrence of 1 in the bit mask
   ⍵[⍴⍵]≡¨⍵ ⍝ create a bit mask by checking which padded strings match the last string in the expansion
     ¨ ⍝ for each list of padded strings
       L←⍴,⊃⌽⍵ ⍝ assign length of last string in expansion to L
          ⋄ ⍝ statement separator
            L⍴¨⍵ ⍝ for each string, reshape to length of longest string
               ¨ ⍝ for each list of strings
                 {⍺,⍵}\¨{⍺,⍵}\ ⍝ expand twice. (A, B, C) -> (A, AB, ABC) -> ((A), (A, AB), (A, AB, ABC))
                    ⊂∘⍕¨⍵ ⍝ for each element, encode as string and enclose

Try it online!

Answer 11

Haskell, 77 bytes

nub.map(\x->[p|p<-[1..],and.zipWith(==)x$drop p x]!!0).inits
import Data.List

Try it online!

Implicit function, taking a list of integers as input and returning a list of integers as output.

Not really satisfied with this answer, but I can't seem to avoid importing Data.List.

How?

nub.                                -- remove duplicates from
map(\x->                            -- the list obtained replacing each x with
        [p|p<-[1..],                --     the integer p>=1
        and.zipWith(==)x$drop p x]  --     such that x is periodic of period p
    !!0).                           --   take the smallest such p
inits                               -- where x ranges over the prefixes of the input list

Answer 12

Python 2, 92 bytes

def f(l):r=[];p=i=1;exec"while l[p:i]!=l[:i-p]:p+=1\ni+=1;r+=[p][p in r:]\n"*len(l);return r

Try it online!

This uses the fact that the periods of prefices are non-decreasing.

Ungolfed a bit:

def f(l):
 r=[];p=i=1
 for _ in l:                       # for each prefix of l (tracked by i)
  while l[p:i]!=l[:i-p]:p+=1       # find the next p s.t. removing a length p prefix or a length p suffix result in equal lists
  i+=1;r+=[p][p in r:]             # then add p to the return value if its not already there
 return r

Answer 13

K (ngn/k), 19 17 21 bytes

1+?{((#x)#',\x)?x}',\

Try it online!

Modeled after @Jonah's J answer.

• {...}',\ for each prefix of the (implicit) input...
• ((#x)#',\x) expand each prefix (of the current passed-in prefix) to the full length of that prefix (e.g., transform 1 1 2 from (1;1 1;1 1 2) into (1 1 1;1 1 1;1 1 2))
• (...)?x get the index of the first transformed prefix that matches the prefix itself
• 1+?{...} add one to the distinct indices

Answer 14

Scala 3, 119 bytes

_.inits.toSeq.reverse.tail.map{a=>1.to(a.size).find(Seq.fill(a.size)(_)flatMap a.take zip a forall(_==_)).get}.distinct

Try it in Scastie!

This is annoyingly long.

_                 //The input
  .inits          //Iterator of all prefixes (biggest to smallest)
  .toSeq          //Conver to Seq so we can do stuff to it
  .reverse        //Reverse so the smallest prefixes are first
  .tail           //Drop the first prefix, which is empty
  .map { a =>     //Map each prefix a to its possible period
    1.to(a.size)         //Range of possible possible periods
      .find(             //Find an i such that
        Seq.fill(a.size)(_)  //when you make a.size copies
          flatMap a.take     //of the first i elements of a
          zip a              //and zip those with a, dropping extra elements
          forall(_ == _)     //they all equal the corresponding elements in a
      ).get             //Unwrap the Option to get the possible period
  }.distinct      //Remove duplicates

Answer 15

Haskell, 110 133 bytes

Sorry, got longer, fixed bug.

h v=l<$>(l v#v)
1#v=[1!v]
n#v=(n-1)#v++[[i!v|i<-[2..n],n!v==r n(i!v)]!!0|notElem(n!v)$r n<$>(n-1)#v]
r n=(n!).cycle
(!)=take
l=length

Try it online!

Answer 16

Charcoal, 27 bytes

Ｗ⁻⊕Ｅθ⌕Ｅ⊕λ……θ⊕μ⊕λ…θ⊕λυ⊞υ⌊ιＩυ

Try it online! Link is to verbose version of code. Takes input by default as a character array, but it's also possible to feed it integer or string arrays by using JSON format. Explanation:

⊕Ｅθ⌕Ｅ⊕λ……θ⊕μ⊕λ…θ⊕λ

Loop over all prefixes of prefixes, extending them to the original prefix and finding indices of the first prefix where this results in the original prefix, then adjusting to give the periods.

Ｗ⁻...υ

While the list of periods contains a value not in the deduplicated list...

⊞υ⌊ι

... push the smallest missing value to the deduplicated list.

Ｉυ

Output the deduplicated list.

Answer 17

Haskell, 96 95 92 bytes

import Data.List
r=tail.inits
f=nub.map(\p->[length x|x<-r p,and$zipWith(==)p$cycle x]!!0).r

Try it online!

• saved 1 thanks to @Unrelated String

r=tail.inits

• all prefixes(excludes empty)

f=nub.map(\p-> ... ).r

• we map every prefix(.rlist) by doing the job below and we return unique elements.

[length x|x<-r p, .. ]!!0

• list of prefixes of the current prefix being tested (x<-r p), which satisfy condition below. We take the length and we return first element (shorter)

and$zipWith(==)p$cycle x

• True if difference of each elements of prefix and possible period is 0

Answer 18

Ruby, 79 75 bytes

->x{(1..x.size).map{|i|(1..i).find{|j|i.times.all?{|k|x[k]==x[k%j]}}}.uniq}

Accepts an array (e.g. of strings or integers) and returns an array of ints.

Previous code:

->x{(1..x.size).map{|i|(1..i).find{|j|x[0...j].cycle.first(i)==x[0...i]}}.uniq}

Try it online!

Answer 19

Java, 105 bytes

a->{var s=new java.util.TreeSet();int p=1,i=0;for(int c:a)s.add(p=a[i++%p]==c?p:a[0]==c?i-1:i);return s;}

Try it online!