Count cyclically self-describing lists

Clash Royale CLAN TAG#URR8PPP

up vote
11
down vote

favorite

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

code-golf array-manipulation counting

share|improve this question

asked 2 hours ago

Zgarb

26k460228

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  An unexpected twist! Halfway through the description I was expecting the less-interesting task of just determining if a list was CSD. Kudos.
  – Sparr
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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
  1 hour ago
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  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
  1 hour ago
  

  
  
  
  

 | 
show 3 more comments

up vote
11
down vote

favorite

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

code-golf array-manipulation counting

share|improve this question

asked 2 hours ago

Zgarb

26k460228

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  An unexpected twist! Halfway through the description I was expecting the less-interesting task of just determining if a list was CSD. Kudos.
  – Sparr
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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
  1 hour ago
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  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
  1 hour ago
  

  
  
  
  

 | 
show 3 more comments

up vote
11
down vote

favorite

up vote
11
down vote

favorite

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

code-golf array-manipulation counting

share|improve this question

asked 2 hours ago

Zgarb

26k460228

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

code-golf array-manipulation counting

code-golf array-manipulation counting

share|improve this question

asked 2 hours ago

Zgarb

26k460228

share|improve this question

asked 2 hours ago

Zgarb

26k460228

share|improve this question

share|improve this question

asked 2 hours ago

Zgarb

26k460228

asked 2 hours ago

Zgarb

26k460228

asked 2 hours ago

Zgarb

26k460228

26k460228

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  An unexpected twist! Halfway through the description I was expecting the less-interesting task of just determining if a list was CSD. Kudos.
  – Sparr
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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
  1 hour ago
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  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
  1 hour ago
  

  
  
  
  

 | 
show 3 more comments

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  An unexpected twist! Halfway through the description I was expecting the less-interesting task of just determining if a list was CSD. Kudos.
  – Sparr
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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
  1 hour ago
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  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
  1 hour ago
  

  
  
  
  

3

3

An unexpected twist! Halfway through the description I was expecting the less-interesting task of just determining if a list was CSD. Kudos.
– Sparr
2 hours ago

An unexpected twist! Halfway through the description I was expecting the less-interesting task of just determining if a list was CSD. Kudos.
– Sparr
2 hours ago

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
2 hours ago

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
2 hours ago

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
1 hour ago

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
1 hour ago

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
1 hour ago

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
1 hour ago

2

2

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
1 hour ago

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
1 hour ago

 | 
show 3 more comments

2 Answers
2

active

oldest

votes

up vote
0
down vote

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.

share|improve this answer

answered 1 hour ago

user202729

13.3k12549

add a comment | 

up vote
0
down vote

Haskell, 118 bytes

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

Try it online!

g s= -- main function
 [ # | n<-[1..s],m<-[1..s]] -- call '#' for all combinations of starting
 -- values, a series of digit 'n' of length 'm'

 d # l a b s -- function f takes
 -- current digit 'd' of length 'l'
 -- first digit 'b' of length 'a'
 -- leftover of the sum 's'
 | =1 -- sequence is valid (i.e. return 1) if
 d==a, -- 'd' equals the initial length 
 d/=b, -- 'd' is not equal to the initial digit
 l*d==s -- digit * length equal the leftover of the sum
 | n<-s-d*l -- else let 'n' be sum less the current run
 =sum -- add the valid sequences of
 [(i#d)a b n -- the recursive call
 |i<-[1..s],d/=i,n>=0] -- for all new possible digits 'i'
 -- that are not equal to 'd'
 -- and where the new run does not exceed the sum

 -- if the sum gets too large, the last check (n>=0)
 -- results in an empty list where function 'sum'
 -- returns 0, i.e. no contribution to the number
 -- of valid sequences 

share|improve this answer

answered 35 mins ago

nimi

30.5k31985

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Tried to factor out the invariants of the recursive call (a and b) but didn't find a shorter solution.
  – nimi
  34 mins ago
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "200"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f175113%2fcount-cyclically-self-describing-lists%23new-answer', 'question_page');

);

Post as a guest

Name Email

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
0
down vote

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.

share|improve this answer

answered 1 hour ago

user202729

13.3k12549

add a comment | 

up vote
0
down vote

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.

share|improve this answer

answered 1 hour ago

user202729

13.3k12549

add a comment | 

up vote
0
down vote

up vote
0
down vote

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.

share|improve this answer

answered 1 hour ago

user202729

13.3k12549

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.

share|improve this answer

answered 1 hour ago

user202729

13.3k12549

share|improve this answer

share|improve this answer

answered 1 hour ago

user202729

13.3k12549

answered 1 hour ago

user202729

13.3k12549

answered 1 hour ago

user202729

13.3k12549

13.3k12549

add a comment | 

add a comment | 

up vote
0
down vote

Haskell, 118 bytes

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

Try it online!

g s= -- main function
 [ # | n<-[1..s],m<-[1..s]] -- call '#' for all combinations of starting
 -- values, a series of digit 'n' of length 'm'

 d # l a b s -- function f takes
 -- current digit 'd' of length 'l'
 -- first digit 'b' of length 'a'
 -- leftover of the sum 's'
 | =1 -- sequence is valid (i.e. return 1) if
 d==a, -- 'd' equals the initial length 
 d/=b, -- 'd' is not equal to the initial digit
 l*d==s -- digit * length equal the leftover of the sum
 | n<-s-d*l -- else let 'n' be sum less the current run
 =sum -- add the valid sequences of
 [(i#d)a b n -- the recursive call
 |i<-[1..s],d/=i,n>=0] -- for all new possible digits 'i'
 -- that are not equal to 'd'
 -- and where the new run does not exceed the sum

 -- if the sum gets too large, the last check (n>=0)
 -- results in an empty list where function 'sum'
 -- returns 0, i.e. no contribution to the number
 -- of valid sequences 

share|improve this answer

answered 35 mins ago

nimi

30.5k31985

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Tried to factor out the invariants of the recursive call (a and b) but didn't find a shorter solution.
  – nimi
  34 mins ago
  

  
  
  
  

add a comment | 

up vote
0
down vote

Haskell, 118 bytes

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

Try it online!

g s= -- main function
 [ # | n<-[1..s],m<-[1..s]] -- call '#' for all combinations of starting
 -- values, a series of digit 'n' of length 'm'

 d # l a b s -- function f takes
 -- current digit 'd' of length 'l'
 -- first digit 'b' of length 'a'
 -- leftover of the sum 's'
 | =1 -- sequence is valid (i.e. return 1) if
 d==a, -- 'd' equals the initial length 
 d/=b, -- 'd' is not equal to the initial digit
 l*d==s -- digit * length equal the leftover of the sum
 | n<-s-d*l -- else let 'n' be sum less the current run
 =sum -- add the valid sequences of
 [(i#d)a b n -- the recursive call
 |i<-[1..s],d/=i,n>=0] -- for all new possible digits 'i'
 -- that are not equal to 'd'
 -- and where the new run does not exceed the sum

 -- if the sum gets too large, the last check (n>=0)
 -- results in an empty list where function 'sum'
 -- returns 0, i.e. no contribution to the number
 -- of valid sequences 

share|improve this answer

answered 35 mins ago

nimi

30.5k31985

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Tried to factor out the invariants of the recursive call (a and b) but didn't find a shorter solution.
  – nimi
  34 mins ago
  

  
  
  
  

add a comment | 

up vote
0
down vote

up vote
0
down vote

Haskell, 118 bytes

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

Try it online!

g s= -- main function
 [ # | n<-[1..s],m<-[1..s]] -- call '#' for all combinations of starting
 -- values, a series of digit 'n' of length 'm'

 d # l a b s -- function f takes
 -- current digit 'd' of length 'l'
 -- first digit 'b' of length 'a'
 -- leftover of the sum 's'
 | =1 -- sequence is valid (i.e. return 1) if
 d==a, -- 'd' equals the initial length 
 d/=b, -- 'd' is not equal to the initial digit
 l*d==s -- digit * length equal the leftover of the sum
 | n<-s-d*l -- else let 'n' be sum less the current run
 =sum -- add the valid sequences of
 [(i#d)a b n -- the recursive call
 |i<-[1..s],d/=i,n>=0] -- for all new possible digits 'i'
 -- that are not equal to 'd'
 -- and where the new run does not exceed the sum

 -- if the sum gets too large, the last check (n>=0)
 -- results in an empty list where function 'sum'
 -- returns 0, i.e. no contribution to the number
 -- of valid sequences 

share|improve this answer

answered 35 mins ago

nimi

30.5k31985

Haskell, 118 bytes

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

Try it online!

g s= -- main function
 [ # | n<-[1..s],m<-[1..s]] -- call '#' for all combinations of starting
 -- values, a series of digit 'n' of length 'm'

 d # l a b s -- function f takes
 -- current digit 'd' of length 'l'
 -- first digit 'b' of length 'a'
 -- leftover of the sum 's'
 | =1 -- sequence is valid (i.e. return 1) if
 d==a, -- 'd' equals the initial length 
 d/=b, -- 'd' is not equal to the initial digit
 l*d==s -- digit * length equal the leftover of the sum
 | n<-s-d*l -- else let 'n' be sum less the current run
 =sum -- add the valid sequences of
 [(i#d)a b n -- the recursive call
 |i<-[1..s],d/=i,n>=0] -- for all new possible digits 'i'
 -- that are not equal to 'd'
 -- and where the new run does not exceed the sum

 -- if the sum gets too large, the last check (n>=0)
 -- results in an empty list where function 'sum'
 -- returns 0, i.e. no contribution to the number
 -- of valid sequences 

share|improve this answer

answered 35 mins ago

nimi

30.5k31985

share|improve this answer

share|improve this answer

answered 35 mins ago

nimi

30.5k31985

answered 35 mins ago

nimi

30.5k31985

answered 35 mins ago

nimi

30.5k31985

30.5k31985

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Tried to factor out the invariants of the recursive call (a and b) but didn't find a shorter solution.
  – nimi
  34 mins ago
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Tried to factor out the invariants of the recursive call (a and b) but didn't find a shorter solution.
  – nimi
  34 mins ago
  

  
  
  
  

Tried to factor out the invariants of the recursive call (a and b) but didn't find a shorter solution.
– nimi
34 mins ago

Tried to factor out the invariants of the recursive call (a and b) but didn't find a shorter solution.
– nimi
34 mins ago

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f175113%2fcount-cyclically-self-describing-lists%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email