Zählen Sie zyklisch selbstbeschreibende Listen

19

Zyklisch selbstbeschreibende Listen

Eine Liste positiver Ganzzahlen ist zyklisch selbstbeschreibend , wenn die folgenden Bedingungen erfüllt sind.L

  1. L ist nicht leer.
  2. Das erste und das letzte Element von sind unterschiedlich.L
  3. Wenn Sie in Läufe mit gleichen Elementen aufteilen , entspricht das Element jedes Laufs der Länge des nächsten Laufs und das Element des letzten Laufs der Länge des ersten Laufs.L

Betrachten Sie zum Beispiel . Es ist nicht leer und das erste und das letzte Element sind unterschiedlich. Wenn wir es in Läufe , erhalten wir .L=[1,1,1,2,3,3,1,1,1,3][[1,1,1],[2],[3,3],[1,1,1],[3]]

  • Der erste Lauf ist ein Lauf von s und die Länge des nächsten Laufs ist .1[2]1
  • Der zweite Lauf ist ein Lauf von s und die Länge des nächsten Laufs ist .2[3,3]2
  • Der dritte Lauf ist ein Lauf von s und die Länge des nächsten Laufs ist .3[1,1,1]3
  • Der vierte Lauf ist ein Lauf von s und die Länge des nächsten Laufs ist .1[3]1
  • Schließlich ist der letzte Lauf ein Lauf von s und die Länge des ersten Laufs ist .3[1,1,1]3

Dies bedeutet, dass eine sich zyklisch selbst beschreibende Liste ist.L

Für ein Nicht-Beispiel ist die Liste nicht zyklisch selbstbeschreibend, da auf einen Lauf von s ein Lauf der Länge folgt . Die Liste ist auch nicht zyklisch selbstbeschreibend, da der letzte Lauf s dauert, der erste jedoch die Länge .[3,2,2,2,1,4,1,1,1]21[2,2,4,4,3,3,3,3]32

Die Aufgabe

In dieser Herausforderung ist Ihre Eingabe eine Ganzzahl . Ihre Ausgabe soll die Anzahl der sich zyklisch selbst beschreibenden Listen sein, deren Summe gleich . Zum Beispiel sollte zu , da die zyklisch selbstbeschreibenden Listen, deren Summe ist, ,n1nn=848[1,1,1,1,4][1,1,2,1,1,2] , [2,1,1,2,1,1] und [4,1,1,1,1]. Die niedrigste Byteanzahl gewinnt, und es gelten andere Standardregeln für .

Hier sind die korrekten Ausgabewerte für Eingaben von 1 bis 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
Zgarb
quelle
4
Eine unerwartete Wendung! In der Mitte der Beschreibung erwartete ich die weniger interessante Aufgabe, nur festzustellen, ob eine Liste CSD war. Ein dickes Lob.
Sparr
Ich bin ein wenig traurig, dass die Definition keine Listen enthält, in denen das erste und das letzte Element identisch sind, und als dieselbe Gruppe gelten, als ob die Liste tatsächlich ein Zyklus ohne eindeutigen Anfang / Ende wäre.
Sparr
Dies ist Codegolf, daher finde ich es interessanter, festzustellen, ob eine Liste zyklisch selbstbeschreibend ist (Lösungen sind schneller auszuführen) - wenn es keinen anderen Weg gibt, als alle Listen und Zähler zu generieren.
User202729
Es gibt einen polynomiellen Zeitalgorithmus, aber es ist ziemlich schwierig zu programmieren und definitiv nicht so effektiv wie eine Lösung, die alle möglichen Listen generiert und überprüft.
User202729
2
Jede gerade Zahl mit Ausnahme von 2 kann als erhalten werden n,1,...,1, und jede ungerade Zahl größer als 13 kann durch Verketten 3,2,2,2,1,1mit einer geraden Zahl erhalten werden. Der Beweis, dass 13 unmöglich ist, wird dem Leser als Übung überlassen.
Nitrodon

Antworten:

6

Haskell , 75 Bytes

Vielen Dank Ørjan für das Speichern eines Bytes!

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]]

Probieren Sie es online!

Das Problem ist äquivalent zu:

ni=0kaiai+1aiN,aiai+1,a0=ak

H.PWiz
quelle
1
76
Ørjan Johansen
1

Jelly , 18 Bytes

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

Probieren Sie es online!

Idee: Jede zyklisch selbstbeschreibende Liste kann als Werteliste für jeden Block beschrieben werden, und wir können die Längen aus den Werten ableiten. Beachten Sie, dass zwei benachbarte Werte unterschiedlich sein müssen. Natürlich kann es höchstens nBlöcke geben und die Länge jedes Blocks ist höchstens n.

user202729
quelle
1

Haskell, 118 105 103 Bytes

Edit: -13 Bytes dank @ Ørjan Johansen, -2 Bytes dank @ 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]]

Probieren Sie es online!

nimi
quelle
Ziehe es mit dem gleichen Trick heraus, den ich H.PWiz gezeigt habe.
Ørjan Johansen
Sie haben verpasst (i#d)n->i#d$n
H.PWiz