7
\$\begingroup\$

Challenge

The challenge is to write a function that prints the number of repeats a given array of integers has.

What are repeats?

Repeats of a slice (as in a section of an array) [ a1, a2, a3, ..., an] are any other non-overlapping slices of the forms [ a1+an, a2+an, a3+an, ..., an+an], [ a1+2an, a2+2an, a3+2an, ..., an+2an], and so on. Incomplete repeats, e.g. [ a1+3an, a2+3an], are not counted.

Input and output

Inputs should be ordered collections of integers, e.g. arrays, lists, tuples, etc. The integers will be sorted and unique.

Output a single integer that is the number of repeats that covers the whole input. The output should correspond to the greatest possible number of repeats. E.g. certain inputs could be modeled to have 3 repeats of a 4-element slice, or 6 repeats of a 2-element slice; 6 should be the output because it is greater than 3.

Examples

Input -> Output

[ 1,  3,  5,
  6,  8, 10,
 11, 13, 15,
 16, 18, 20]
-> 4

[ 3,  5, 7, 10,
 13, 15]
-> 1

[1,
 2,
 3]
-> 3

[1,2,4]
-> 1

[ 3, 5, 7, 9,
 12,14,16,18]
-> 2

This is a challenge, so the shortest code possible wins

If you have any questions related to the challenge feel free to ask.
I know that my attempts to explain something can be difficult to understand sometimes.

\$\endgroup\$
  • 2
    \$\begingroup\$ As far as I can see the challenge is roughly: "What is the maximum number of equal sized chunks into which an array can be split so that the difference between corresponding elements in any chunk and the next chunk (if any) is a constant. The array is a sorted list of positive (?) numbers (the minumum number of elements is not yet clear) \$\endgroup\$ – Ton Hospel Sep 18 '16 at 11:41
  • 1
    \$\begingroup\$ @Titus: The chunks consist of consecutive elements in the original array and the difference must be a constant over chunks too (otherwise an array of length n can always be split in n). Anyways, I hope this gets clarified and reopened. If my interpretation is correct this is actually a fun little challenge. I have a perl solution just itching to be posted. \$\endgroup\$ – Ton Hospel Sep 18 '16 at 12:19
  • 2
    \$\begingroup\$ @RoiEX just wanna introduce you the sandbox: meta.codegolf.stackexchange.com/questions/2140/… Next time when you come up with a challenge, you can use it to let other users find problems or bugs in your challenge before actually posting it :-) \$\endgroup\$ – busukxuan Sep 18 '16 at 17:29
  • 1
    \$\begingroup\$ Still to be clarified: Can the input array contain 0 ? negative values ? Is a single integer as input allowed. In particular is a single 0 allowed ? If the intention is non-negative integers then 0 is still weird since it can then only appear at the start, so it becomes a1, but then the next repeat must start with a1+an which is an which is therefore a repeat of the previious number which is forbidden. So starting with 0 implies only 1 repeat (simular argument for starting with a negative number). So it seems more logical to only allow positive integers in the input \$\endgroup\$ – Ton Hospel Sep 19 '16 at 9:01
  • 1
    \$\begingroup\$ I just noticed that there is no test case where the gaps within each chunk vary (e.g. [1, 2, 4, 7, 8, 9, 11, 14, 15, 16, 18, 21], which I think should give 3). This should probably be added if I've got it right. \$\endgroup\$ – Martin Ender Sep 19 '16 at 16:45
3
\$\begingroup\$

05AB1E, 21 20 bytes

0)«¥©v®NôÙgi®Nôg}})Z

Explanation

0)«                   # prepend a 0 to the beginning of the list
   ¥©                 # calculate deltas and store in register
     v           }    # for each N in range(0, len(deltas))
      ®Nô             # split deltas into N chunks
         Ù            # uniquify list
          gi    }     # if length == 1
            ®Nôg      # push chunk length
                  )Z  # return max chunk length

Try it online!

Modified test suite

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

Perl, 48 47 bytes

Includes +3 for -p

Give input as a list of numbers on STDIN

repeats.pl <<< "3 5 7 9 12 14 16 18"

repeats.pl:

#!/usr/bin/perl -p
s//0 /;s/\d+/$'-$&/eg;/(.+?)\1*-/;$_=s/$1//g

Does not work if the input is a single 0 (not clear if that is a valid input). Fixing that takes 2 more bytes:

#!/usr/bin/perl -p
$_=s//0 /%s/\d+/$'-$&/eg-/^(.+?)\1*-/||s/$1//g

Explanation

Adds a 0 in front of the sequence and then constructs a list of differences. The example input

3 5 7 9 12 14 16 18

becomes:

3 2 2 2 3 2 2 2 -18

The -18 is because the last difference is calculated relative to the end of the string which in perl will behave like 0. On this transformed list the problem is equivalent to finding the most often repeating substring before the - sign (this is why a single 0 as input does not work because only in that case there is no minus sign)

\$\endgroup\$
3
\$\begingroup\$

Retina, 38 bytes

\d+
$*
(?<=(1*) )\1

(.+?)(| \1)+$
$#2

Input should be space-separated.

Try it online! (The first line enables a linefeed-separated test suite.)

Explanation

\d+
$*

Convert input to unary by replacing each number n with n copies of 1.

(?<=(1*) )\1

Compute consecutive differences, by removing from each number the previous number.

(.+?)(| \1)+$
$#2

Try to match the entire input as a repetition of difference (favouring more repetitions of fewer differences) and replace it with the number of repetitions.

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