# 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],,[3,3],[1,1,1],]\$$.

• The first run is a run of $$\1\$$s, and the length of the next run, $$\\$$, 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, $$\\$$, 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\$$.

# The Task

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
• 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
• This does not currently have an oeis entry. Consider submitting it? – Draco18s no longer trusts SE Nov 2 '18 at 20:52

# Haskell, 75 bytes

Thanks Ørjan for saving one byte!

# 05AB1E, 25 bytes

Åœεœʒ¬sθÊ}ÙεγĆü‚εgå}P]˜O


Try it online or verify the first 9 test cases (times out for $$\n\geq10\$$).

Explanation:

Åœ              # Get all lists of positive integers that sum to the (implicit) input
ε             # Map over each inner list:
œ            #  Get all its permutations
ʒ           #  Filter this list of permutation-lists by:
¬          #   Get the first element (without popping the list itself)
sθ        #   Swap to get the list, and pop and push its last element
Ê       #   Check that they are NOT equal
}Ù          #  After the inner filter: uniquify all remaining permutations
ε         #  Map each permutation to:
γ        #   Split the list into groups of equal adjacent elements
Ć       #   Enclose it: add the first group as trailing item
ü‚     #   Create overlapping pairs of groups
ε    #   Map over each pair:
#    Pop and push both lists separated to the stack
g  #    Pop and get the length of the second list
å #    And check that it's in the first list
}P   #   After this inner-most map: verify all pairs were truthy (product)
]             # Close the two still open nested maps
˜            # Flatten the list of lists
O           # And take the sum
# (after which this is output implicitly as result)


Try it online with a step-by-step output.

# Husk, 27 bytes

#§=oṙ1mLm←fo¬εumgfo=¹ΣṖṁḣ´R


Try it online!

A direct bruteforce. Struggles for n above 4.