# Cyclically self-describing lists

A list $$\L\$$ of positive integers is cyclically self-describing, if the following conditions hold.

1. $$\L\$$ is nonempty.
2. The first and last elements of $$\L\$$ are different.
3. If you split $$\L\$$ into runs of equal elements, the element of each run equals the length of the next run, and the element of the last run equals the length of the first run.

For example, consider $$\L = [1,1,1,2,3,3,1,1,1,3]\$$. It is nonempty, and the first and last elements are different. When we break it into runs, we get $$\[[1,1,1],[2],[3,3],[1,1,1],[3]]\$$.

• The first run is a run of $$\1\$$s, and the length of the next run, $$\[2]\$$, is $$\1\$$.
• The second run is a run of $$\2\$$s, and the length of the next run, $$\[3,3]\$$, is $$\2\$$.
• The third run is a run of $$\3\$$s, and the length of the next run, $$\[1,1,1]\$$, is $$\3\$$.
• The fourth run is a run of $$\1\$$s, and the length of the next run, $$\[3]\$$, is $$\1\$$.
• Finally, the last run is a run of $$\3\$$s, and the length of the first run, $$\[1,1,1]\$$, is $$\3\$$.

This means that $$\L\$$ is a cyclically self-describing list.

For a non-example, the list $$\[3,2,2,2,1,4,1,1,1]\$$ is not cyclically self-describing, since a run of $$\2\$$s is followed by a run of length $$\1\$$. The list $$\[2,2,4,4,3,3,3,3]\$$ is also not cyclically self-describing, since the last run is a run of $$\3\$$s, but the first run has length $$\2\$$.

In this challenge, your input is an integer $$\n \geq 1\$$. Your output shall be the number of cyclically self-describing lists whose sum equals $$\n\$$. For example, $$\n = 8\$$ should result in $$\4\$$, since the cyclically self-describing lists whose sum is $$\8\$$ are $$\[1,1,1,1,4]\$$, $$\[1,1,2,1,1,2]\$$, $$\[2,1,1,2,1,1]\$$ and $$\[4,1,1,1,1]\$$. The lowest byte count wins, and other standard rules apply.

Here are the correct output values for inputs from $$\1\$$ to $$\50\$$:

1 -> 0
2 -> 0
3 -> 0
4 -> 2
5 -> 0
6 -> 2
7 -> 0
8 -> 4
9 -> 0
10 -> 6
11 -> 6
12 -> 12
13 -> 0
14 -> 22
15 -> 10
16 -> 32
17 -> 16
18 -> 56
19 -> 30
20 -> 96
21 -> 56
22 -> 158
23 -> 112
24 -> 282
25 -> 198
26 -> 464
27 -> 364
28 -> 814
29 -> 644
30 -> 1382
31 -> 1192
32 -> 2368
33 -> 2080
34 -> 4078
35 -> 3844
36 -> 7036
37 -> 6694
38 -> 12136
39 -> 12070
40 -> 20940
41 -> 21362
42 -> 36278
43 -> 37892
44 -> 62634
45 -> 67154
46 -> 108678
47 -> 118866
48 -> 188280
49 -> 209784
50 -> 326878
• An unexpected twist! Halfway through the description I was expecting the less-interesting task of just determining if a list was CSD. Kudos. – Sparr Nov 2 '18 at 15:20
• I am a little sad that the definition doesn't include lists where the first and last element are the same, and count as the same group, as they would if the list were actually a cycle without a distinct start/end. – Sparr Nov 2 '18 at 15:28
• This is code-golf, so I think determining if a list is cyclically self-describing is more interesting (solutions faster to execute) -- if there is no short way other than generating all lists and count. – user202729 Nov 2 '18 at 15:46
• There is a polynomial time algorithm, but it is quite difficult to program and definitely not as golfy as a solution that generates and verifies all possible lists. – user202729 Nov 2 '18 at 15:52
• Every even number except 2 can be obtained as n,1,...,1, and every odd number greater than 13 can be obtained by concatenating 3,2,2,2,1,1 to an even number. The proof that 13 is impossible is left as an exercise for the reader. – Nitrodon Nov 2 '18 at 16:31