11
1
The period
of a string is the shortest non-zero shift so that the string matches itself, ignoring any parts that overhang. So for example, abcabcab
has period 3
. By convention we say that if there is no such shift then a string has period equal to its length. So the period of abcde
is 5
and the period of a
is 1
.
In more formal terms, the period of a string S
is the minimum i > 0
so that S[1,n-i] == S[i+1,n]
(indexing from 1
).
For a given string S of power of two length, we will compute the period of all its prefixes of power of two length. For example, consider S = abcabcab
. The periods we will compute are:
'a', 1
'ab', 2
'abca', 3
'abcabcab', 3
We will in fact just output the array of periods, that is [1, 2, 3, 3]
.
For a given positive power of two n
, consider all possible binary strings S
. Recall that a binary string is simply a string of 1
s and 0
s so there are exactly 2^n
such strings (that is 2
to the power n
). For each one we can compute this array of periods.
The challenge is to write code that takes
n
(a power of two) as input and computes how many distinct such arrays there are.
The answers for n = 1, 2, 4, 8, 16, 32, 64, 128
are:
1, 2, 6, 32, 320, 6025, 216854, 15128807
The full set of distinct period arrays for n = 4
is:
1, 1, 1
1, 1, 3
1, 1, 4
1, 2, 2
1, 2, 3
1, 2, 4
Score
I will run your code on my computer running Ubuntu for 10 minutes. Your score is the largest n
for which your code terminates in that time. In the case of a tie, the answer that completes the joint largest n
fastest wins. In the case that there is a tie within 1 second on timings, the first answer posted wins.
Languages and libraries
You can use any available language and libraries you like. Please include a full explanation for how to run/compile your code in Linux if at all possible.`
Your code should actually compute the answers and not, for example, just output precomputed values.
Leading entries
- 2 minutes and 21 seconds for n = 128 in C# by Peter Taylor
- 9 seconds for n = 32 in Rust by isaacg
This made my head hurt. – Henry – 2017-08-03T19:46:49.077
1The challenge is interesting, but I still cannot see objective criterium you're using to distinguish between "precomputed" and "actually computed" answers. If you, for example, cannot understand how my code works, but it gives correct answers for huge
n
, would you accept it? It is not well defined where is the border between hardcoding and actual computing. – None – 2017-08-03T19:49:57.287A123903? – H.PWiz – 2017-08-03T20:28:51.953
@H.PWiz I doubt it :) The answer for
n=32
will make that clear I suspect. – None – 2017-08-03T20:29:12.113@Lembik I hope not, as that would undermine your challenge severely – H.PWiz – 2017-08-03T20:29:47.993
1
@ThePirateBay https://codegolf.meta.stackexchange.com/a/1063/9206 . It's a standard rule.
– None – 2017-08-03T20:29:58.407When I saw the title of this challenge, I thought it would be about arrays like this: [".",".","...."] – Gryphon – 2017-08-05T14:02:29.547
@Lembik Huh, it's 6025? Strange – ASCII-only – 2017-08-06T03:02:08.890
https://gist.github.com/somebody1234/fb6494f3a3f350a4ffdc8c8ef213a4c2 – ASCII-only – 2017-08-06T07:14:53.800
I don't understand this challenge quite yet. Could you show how the period of
abcabcab
is 3? – user41805 – 2017-08-06T10:44:34.1902@Cowsquack All but the first three letters of the string is
abcab
. All but the last 3 letters isabcab
. These match, and removing a smaller number of letters does not match. – isaacg – 2017-08-07T03:34:47.130