19
\$\begingroup\$

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 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
\$\endgroup\$
  • 4
    \$\begingroup\$ An unexpected twist! Halfway through the description I was expecting the less-interesting task of just determining if a list was CSD. Kudos. \$\endgroup\$ – Sparr Nov 2 '18 at 15:20
  • \$\begingroup\$ 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. \$\endgroup\$ – Sparr Nov 2 '18 at 15:28
  • \$\begingroup\$ 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. \$\endgroup\$ – user202729 Nov 2 '18 at 15:46
  • \$\begingroup\$ 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. \$\endgroup\$ – user202729 Nov 2 '18 at 15:52
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Nitrodon Nov 2 '18 at 16:31
6
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Factor out with the same trick I showed H.PWiz. \$\endgroup\$ – Ørjan Johansen Nov 3 '18 at 3:42
  • \$\begingroup\$ You missed (i#d)n -> i#d$n \$\endgroup\$ – H.PWiz Nov 3 '18 at 12:09

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.