23
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ Does the output have to be ordered? \$\endgroup\$ – user Apr 5 at 19:12
  • 1
    \$\begingroup\$ @OriginalOriginalOriginalVI Yes, although you can just sort it to get the correct output \$\endgroup\$ – Redwolf Programs Apr 5 at 19:13
  • 2
    \$\begingroup\$ Suggested test case: 1 2 1 1 2 1 as an example where the first prefix with period n isn't just the nth prefix, as it always is in all current test cases (in this case, the 3rd prefix has period only 2 but period 3 is still possible). \$\endgroup\$ – kops Apr 5 at 20:43
  • \$\begingroup\$ @kops Adding, thanks! \$\endgroup\$ – Redwolf Programs Apr 5 at 21:32

19 Answers 19

9
\$\begingroup\$

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!

\$\endgroup\$
9
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ this will error on length-one input that's different from c(1); You can fix it by using seq(a=a<-scan()) instead. Try it \$\endgroup\$ – Giuseppe Apr 5 at 15:58
  • \$\begingroup\$ Ah, I keep forgetting about that length 1 scenario, thanks! \$\endgroup\$ – Kirill L. Apr 5 at 16:01
  • 1
    \$\begingroup\$ You can get down to 82 bytes though! \$\endgroup\$ – Giuseppe Apr 5 at 16:05
8
\$\begingroup\$

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
\$\endgroup\$
7
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Well that was fast :p \$\endgroup\$ – Redwolf Programs Apr 5 at 15:07
  • 8
    \$\begingroup\$ @RedwolfPrograms i am speed \$\endgroup\$ – hyper-neutrino Apr 5 at 15:07
6
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Can't reach Jelly's score because k (index of) doesn't work for finding lists in lists of lists (because implicit vectorization) and 0-indexing. \$\endgroup\$ – ovs Apr 5 at 16:55
  • \$\begingroup\$ "prefix which satisifies..." So does 05AB1E have some prolog-like logic programming features? \$\endgroup\$ – Jonah Apr 5 at 18:06
  • 1
    \$\begingroup\$ @Jonah Not really. η generates a list of prefixes and ÅΔ is a loop with iterates over a given list and returns the first index for which the code returns 1. I think this is much more direct than the Prolog variant. \$\endgroup\$ – ovs Apr 5 at 20:25
5
\$\begingroup\$

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()
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

K (ngn/k), 19 bytes

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

Try it online!

Modeled after @Jonah's J answer.

  • {...}',\ for each prefix of the (implicit) input...
  • (++,\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
\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
5
  • \$\begingroup\$ -4 bytes (maybe) \$\endgroup\$ – Delfad0r Apr 5 at 20:29
  • \$\begingroup\$ -3 more bytes if you take as input the length of v as well. I think this is usually allowed, but I can't seem to find anything on Meta. Maybe wait for the OP's opinion. \$\endgroup\$ – Delfad0r Apr 5 at 20:36
  • 1
    \$\begingroup\$ This fails for the list [1,2,1,1,2,1] (returns [1,2], should return [1,2,3]). \$\endgroup\$ – kops Apr 5 at 20:48
  • 1
    \$\begingroup\$ In commiseration, I spent quite a while on this 88 byte solution with the same bug and I think it's not at all fixable with my approach (not sure about yours). \$\endgroup\$ – kops Apr 5 at 20:49
  • \$\begingroup\$ I have fixed the bug by a different approach, but it got longer :-( . \$\endgroup\$ – Donat Apr 5 at 23:15
2
\$\begingroup\$

Charcoal, 27 bytes

W⁻⊕Eθ⌕E⊕λ……θ⊕μ⊕λ…θ⊕λυ⊞υ⌊ιIυ

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:

⊕Eθ⌕E⊕λ……θ⊕μ⊕λ…θ⊕λ

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.

W⁻...υ

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

⊞υ⌊ι

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

Iυ

Output the deduplicated list.

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

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
\$\endgroup\$
1
2
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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!

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