Codegolf — Подсчет Циклических Самоописывающих Списков

Циклически самоописывающиеся списки

Список \$L\$ натуральных чисел — это циклически самоописывающийся, если выполняются следующие условия.

1. \$L\$ непусто.
2. Первый и последний элементы \$L\$ различны.
3. Если вы разделите \$L\$ на серии равных элементов, элемент каждой серии будет равен длине следующей серии, а элемент последней серии будет равен длине первой серии.

Например, рассмотрим \$L = [1,1,1,2,3,3,1,1,1,3]\$.

• Он непустой, а первый и последний элементы различны.
• Когда мы разобьем его на серии, мы получим \$[[1,1,1],[2],[3,3],[1,1,1],[3]]\$.
• Первый запуск равен \$1\$s, а длина следующего запуска \$[2]\$ равна \$1\$.
• Второй прогон — это прогон \$2\$s, а длина следующего прогона \$[3,3]\$ равна \$2\$.
• Третий прогон — это прогон \$3\$s, а длина следующего прогона \$[1,1,1]\$ равна \$3\$.

Четвертый прогон — это прогон \$1\$с, а длина следующего прогона \$[3]\$ равна \$1\$.

Наконец, последний прогон — это прогон \$3\$s, а длина первого прогона \$[1,1,1]\$ равна \$3\$.

Это означает, что \$L\$ — циклически самоописывающийся список.

В качестве примера, список \$[3,2,2,2,1,4,1,1,1]\$ не является циклически самоописывающим, поскольку за серией \$2\$s следует серия длиной \$1\$.

Список \$[2,2,4,4,3,3,3,3]\$ также не является циклически самоописываемым, поскольку последний запуск представляет собой серию из \$3\$s, но первый запуск имеет длина \$2\$.

 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
 

Задача

Хаскелл, 75 байт

Спасибо Орджану за сохранение одного байта!

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

Попробуйте онлайн!

Проблема эквивалентна:

Сколькими способами \$n\$ можно записать как \$\sum_{i=0}^ka_ia_{i+1}\$ с \$a_i\in\mathbb N,a_i\neq a_{i+1}, a_0=a_k\$

Желе, 18 байт

Попробуйте онлайн!

Идея: каждый циклически самоописывающийся список можно описать как список значений для каждого блока, и мы можем вывести длину из значений. Обратите внимание, что два соседних значения должны быть разными. Конечно, их может быть максимум Åœεœʒ¬sθÊ}ÙεγĆü‚ε`gå}P]˜O blocks and the length of each block is at most 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]] .

Хаскель, 118 105 103 байта

Изменить: -13 байт благодаря @Ørjan Johansen, -2 байта благодаря @H.PWiz

Попробуйте онлайн!

05AB1E, 25 байты

Попробуйте онлайн или проверить первые 9 тестовых случаев (время ожидания \$n\geq10\$).

Объяснение:

Попробуйте онлайн с пошаговым выводом.

Шелуха, 27 байт

Попробуйте онлайн!

Прямой перебор. Борется за n выше 4.