Count cyclically self-describing lists

Question

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

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 code-golf 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

Answer 1

Haskell, 75 bytes

Thanks Ørjan for saving one byte!

g n=sum[x#n|x<-[1..n],let a#n=sum$[b#(n-a*b)|b<-[1..n],a/=b]++[0^n^2|a==x]]

Try it online!

The problem is equivalent to:

How many ways can \$n\$ be written as \$\sum_{i=0}^ka_ia_{i+1}\$ with \$a_i\in\mathbb N,a_i\neq a_{i+1},a_0=a_k\$

Answer 2

Jelly, 18 bytes

ṗⱮ¹Ẏ;ḷ/$€IẠ$Ƈ×Ɲ€§ċ

Try it online!

Idea: Each cyclically self-describing list can be described as a list of values for each block, and we can deduce the lengths from the values. Note that two adjacent values must be different. Of course there can be at most n blocks and the length of each block is at most n.

Answer 3

Haskell, 118 105 103 bytes

Edit: -13 bytes thanks to @Ørjan Johansen, -2 bytes thanks to @H.PWiz

g s=sum[b#a$s|b<-[1..s],a<-[1..s],let(d#l)s|d==a,d/=b,l*d==s=1|n<-s-d*l=sum[i#d$n|i<-[1..s],d/=i,n>=0]]

Try it online!

Answer 4

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.

Answer 5

Husk, 27 bytes

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

Try it online!

A direct bruteforce. Struggles for n above 4.