J'ai essayé Let's count bye-bye man. C'était la première fois que je jouais au code golf, mais je suis allé au sommet avec 51B (eijit) en Python. C'était amusant de s'égarer par essais et erreurs, alors je vais garder un enregistrement.
S'il est difficile d'imaginer comment augmenter bye-byeman, veuillez également consulter Comment augmenter bye-byeman.
Le tableau ci-dessous montre le nombre et le nombre total de bye byemen de chaque taille pour chaque génération.
| génération | c(1, n) | c(2, n) | c(4, n) | c(8, n) | c(6, n) | s(n) |
|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 2 | 0 | 0 | 1 | 0 | 0 | 1 |
| 3 | 0 | 0 | 0 | 1 | 0 | 1 |
| 4 | 1 | 0 | 0 | 0 | 1 | 2 |
| 5 | 1 | 2 | 0 | 0 | 0 | 3 |
| 6 | 0 | 1 | 2 | 0 | 0 | 3 |
| 7 | 0 | 0 | 1 | 2 | 0 | 3 |
| 8 | 2 | 0 | 0 | 1 | 2 | 5 |
| 9 | 3 | 4 | 0 | 0 | 1 | 8 |
ici
Représente. Alors tu comprendras tout de suite
Et la somme du mouvement de la population de taille plus petite de la génération précédente (s = 6 est considérée comme étant passée à s = 1) et du «report» de la division des tailles de génération précédente 8 et 6 Je peux voir la relation.
Au début, j'ai écrit un code de moins de 400B et l'ai soumis sans remarquer qu'il s'agissait de code golf, mais plus tard j'ai remarqué et essayé de le raccourcir.
c=[1]+[0]*4
for i in range(100):
print sum(c)
c=c[4:]+c[:4]
c[1]+=c[0]
c[0]+=c[4]
C'était 85B. J'ai utilisé un tableau pour stocker les éléments. J'ai conçu
était. En regardant les résultats, j'ai été choqué de ne pas pouvoir supporter mes dents et j'ai commencé à étudier le code golf.
J'ai parcouru les articles sur le Web et j'ai appris ce qui suit.
c=[1]+[0]*4;exec"print sum(c);c=c[4:]+c[:4];c[1]+=c[0];c[0]+=c[4];"*100
Cela a rétréci 14B. Mais ce n'est toujours pas suffisant.
J'ai remarqué que le coût d'accès aux éléments du tableau est élevé, je l'ai donc remplacé par cinq variables telles que a, b, c, d et e.
a=1;b=c=d=e=0;exec"print a+b+c+d+e;f=a+d;a=d+e;c=b;d=c;e=d;b=f"*100
Ce rétrécit davantage 4B. Cependant, il est inutile d'utiliser la variable temporaire f.
Quand j'étudiais le code golf, je me suis souvenu du sujet de l'échange sans utiliser de variables temporaires.
a=1
b=2
a,b=b,a
La syntaxe est comme. Appliquer ceci
a=1;b=c=d=e=0;exec"print a+b+c+d+e;a,b,c,d,e=d+e,a+e,b,c,d;"*100
Il a encore rétréci 3B. J'ai réussi à entrer dans la gamme d'acquisition de badges, mais le sommet est toujours une différence désespérée avec 50B.
En regardant le code ici
print a+b+c+d+e
a=d+e
b=a+e
J'ai remarqué que le calcul est dupliqué. Je me suis demandé si cela pouvait être utilisé
a=1;b=c=d=e=0;exec"a,b,c,d,e=d+e,a+e,b,c,d;print b+c+d+e;"*100
Et encore rétréci de 2B. ici
Je fais ça.
Jusqu'à présent, je pensais que cette politique ne pouvait plus couper le code, alors je suis retourné aux bases et j'ai regardé des exemples concrets pour voir s'il y avait une autre règle.
Puis
s(n) = s(n-1) + c(1, n)
Il semblait y avoir une règle. Compte tenu de la raison, c'était une évidence. Les populations bye-byeman augmentent lorsque les tailles 8 et 6 deviennent les tailles 16 et 12 dans la génération suivante et se divisent en tailles 1, 6 et tailles 1, 2. Les individus qui ont augmenté à ce moment peuvent être considérés comme ceux de taille 1.
Lorsque je l'ai implémenté sur la base du résultat de cette analyse, il a malheureusement augmenté de 1B à cause de la variable de maintien de la somme.
a=1;b=c=d=e=s=0;exec"s+=a;print s;a,b,c,d,e=d+e,a+e,b,c,d;"*100
J'ai confirmé que les résultats sont corrects, je vais donc pousser cette politique un peu plus loin.
J'étais parfaitement conscient qu'il était nécessaire de réduire les variables utilisées, alors je me suis demandé s'il serait possible de calculer commodément le nombre d'individus de taille 1.
(Remplacez les symboles c (1, n) etc. utilisés jusqu'à présent par $ c_ {1, n} $)
Rappelons que 1. $ c_ {1, n} = c_ {6, n-1} + c_ {8, n-1} $ n'est représenté que par le terme de taille 1.
\begin{eqnarray*}
c_{1, n} &= c_{6, n-1} + c_{8, n-1}\\
&=c_{8, n-2} + c_{4, n-2}\\
&=c_{4, n-3} + c_{2, n-3}\\
&=c_{2, n-4} + c_{1, n-4} + c_{6, n-4}\\
&=c_{1, n-5} + c_{6, n-5} + c_{1, n-4} + c_{8, n-5}\\
&=c_{1, n-5} + c_{1, n-4} + c_{6, n-5} + c_{8, n-5}\\
&=c_{1, n-5} + c_{1, n-4} + c_{1, n-4}\\
&=c_{1, n-5} + 2c_{1, n-4}\\
\end{eqnarray*}
Quand
c_{1, n} = c_{1, n-5} + 2c_{1, n-4}
J'ai trouvé que cela pouvait être exprimé par.
Maintenant, résolvons ceci car c'est une équation graduelle entre six termes adjacents. L'équation caractéristique est
x^5 - 2x - 1 = 0
Malheureusement, il n'y a pas de formule de solution pour l'équation du cinquième ordre. Mais comme vous pouvez le voir, $ x = -1 $ est l'une des solutions à cette équation. Par conséquent, si factorisé
x^5 - 2x - 1 = (x + 1)(x^4 - x^3 + x^2 - x -1)
J'ai pu le décomposer en polynômes du premier et du quatrième ordre. La dernière solution du polynôme du quatrième ordre = 0 contient malheureusement des nombres complexes et ne semble pas être de simples nombres rationnels ou des entiers. Il est peu probable que la résolution de cette expression graduelle contribue au raccourcissement du code. Cette fois j'ai abandonné le calcul parce que j'ai perdu la peine, mais il peut être intéressant de résoudre l'équation graduelle et de trouver le terme général.
Depuis que j'ai déraillé, j'ai pris une pause dans la conversation, et la formule graduelle du nombre d'éléments de taille 1
c_{1, n} = c_{1, n-5} + 2c_{1, n-4}
Alors j'ai mis en œuvre ceci docilement
a=e=1;b=c=d=s=0;exec"s+=a;print s;a,b,c,d,e=b,c,d,e,a+2*b;"*100
Malheureusement, c'est la même chose que 63B.
J'ai remarqué lors du calcul de la formule progressive, mais le nombre d'éléments d'autres tailles peut également être exprimé par la même formule progressive.
c_{s, n} = c_{s, n-5} + 2c_{s, n-4}
Tient pour tout $ s = 1, 2, 4, 8, 6 $. Prends la somme de ces
\sum_{s} c_{s, n} = \sum_{s} c_{s, n-5} + \sum_{s} 2c_{s, n-4}
Rappelez-vous que la somme est le nombre total de bye byemen
s_{n} = s_{n-5} + 2s_{n-4}
J'ai pu calculer directement la somme de bye-byeman. Lorsqu'il est mis en œuvre avec le fait que le premier terme pour l'expression progressive du nombre total de bye-by-man est 1, 1, 1, 1, 2.
a=b=c=d=1;e=2;exec"print a;a,b,c,d,e=b,c,d,e,a+2*b;"*100
Il a finalement diminué à 56B.
Nous avons besoin d'une autre torsion, nous utiliserons à nouveau le tableau. De plus, comme il faut au plus 100 générations à calculer, j'ai arrêté la rotation des équipes et ainsi de suite. Ce n'est pas le cas lorsque vous faites semblant de l'être.
a=[1]*4+[2];exec"print a[-5];a+=[a[-5]+2*a[-4]];"*100
Vous avez maintenant atteint 53B. c'est
1, 1, 1, 1, 2, 3, 3, 3, 5, 8, ...
Dans un tableau qui croît indéfiniment en ajoutant le nombre total de la génération suivante en fonction de l'expression graduelle, la position -5 à partir de la fin est sortie comme le nombre total de la génération actuelle.
Le code 53B utilise une valeur négative pour l'index du tableau, perdant seulement un "-". Vous pouvez inverser l'ordre de ce tableau, couper les trois «-» et remplacer + = par = et + a à la place, ce qui correspond à une réduction de 2B.
a=[2]+[1]*4;exec"print a[4];a=[a[4]+2*a[3]]+a;"*100
C'était ma réponse cette fois.
Je me demande si je peux couper un autre octet
J'y ai pensé, mais aucun n'a fonctionné. J'attends avec impatience les réponses python publiées et les réponses dans d'autres langues.
Enfin, nous tenons à remercier Ozy pour avoir fourni un numéro aussi intéressant et CodeIQ pour avoir fourni le lieu.