I tried Let's count bye-byeman. It was my first time to play code golf, but I went to the top with 51B (eijit) in Python. It was fun to stray through trial and error, so I will keep a record.
If it is difficult to imagine how to increase bye-byeman, please also see How to increase bye-byeman.
The table below shows the number and total number of bye-byemen of each size for each generation.
| generation | 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 |
here
Represents. Then you will understand immediately
And the sum of the movement from the one smaller size population of the previous generation (s = 6 is considered to have moved to s = 1) and the "carry" from the division of the previous generation sizes 8 and 6 I can see the relationship.
At first, I wrote a code of less than 400B and submitted it without noticing that it was code golf, but later I noticed and tried to shorten it.
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]
This was 85B. I used an array to store the elements. I devised
was. Looking at the results, I was shocked that I couldn't stand my teeth and started studying code golf.
I went around the articles on the web and learned the following.
c=[1]+[0]*4;exec"print sum(c);c=c[4:]+c[:4];c[1]+=c[0];c[0]+=c[4];"*100
This has shrunk 14B. But it's still not enough.
I noticed that the cost of accessing the elements of the array is high, so I replaced it with five variables such as a, b, c, d, and 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
This further shrunk 4B. However, it is useless to use the temporary variable f.
When I was studying code golf, I remembered the topic of swapping without using temporary variables.
a=1
b=2
a,b=b,a
The syntax is like. Apply this
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
It shrank 3B further. I managed to get into the badge acquisition range, but the top is still a desperate difference with 50B.
Looking at the code here
print a+b+c+d+e
a=d+e
b=a+e
I noticed that the calculation is duplicated. I wondered if this could be used
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
And further shrunk by 2B. here
I am doing that.
Up to this point, I thought that this policy couldn't cut the code any more, so I went back to the basics and looked at concrete examples to see if there was another rule.
Then
s(n) = s(n-1) + c(1, n)
There seemed to be a rule. Considering the reason, it was a matter of course. Bye-byeman populations increase when sizes 8 and 6 become sizes 16 and 12 in the next generation and split into sizes 1, 6 and sizes 1, 2. The individuals that have increased at that time can be regarded as those of size 1.
When I implemented it based on the result of this analysis, unfortunately it increased by 1B because of the variable for holding the sum.
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
I've confirmed that the results are correct, so I'll take this policy a little further.
I was keenly aware that it was necessary to reduce the variables used, so I wondered if it would be possible to conveniently calculate the number of size 1 individuals.
(Replace the symbols c (1, n) etc. used so far with $ c_ {1, n} $)
Recall that we consider that $ c_ {1, n} = c_ {6, n-1} + c_ {8, n-1} $ in 1. is represented only by the term of size 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*}
When
c_{1, n} = c_{1, n-5} + 2c_{1, n-4}
I found that it can be expressed by.
Now, let's solve this because it is a recurrence formula between adjacent six terms. The characteristic equation is
x^5 - 2x - 1 = 0
Unfortunately, there is no solution formula for the quintic equation. But as you can see, $ x = -1 $ is one of the solutions to this equation. So if you factor it
x^5 - 2x - 1 = (x + 1)(x^4 - x^3 + x^2 - x -1)
I was able to decompose it into first-order and fourth-order polynomials. The latter solution of the fourth-order polynomial = 0 unfortunately contains complex numbers and does not seem to be simple rational or integers. Perhaps solving this recurrence formula is unlikely to contribute to code shortening. This time, I lost the trouble and gave up the calculation, but it may be interesting to solve the recurrence formula and find the general term.
Since I derailed, I took a break from talking, and the recurrence formula for the number of elements of size 1 is
c_{1, n} = c_{1, n-5} + 2c_{1, n-4}
Because it was, I implemented this obediently
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
Unfortunately, it is the same as 63B.
I noticed when calculating the recurrence formula, but the number of elements of other sizes can also be expressed by the same recurrence formula.
c_{s, n} = c_{s, n-5} + 2c_{s, n-4}
Holds for all $ s = 1, 2, 4, 8, 6 $. Take the sum of these
\sum_{s} c_{s, n} = \sum_{s} c_{s, n-5} + \sum_{s} 2c_{s, n-4}
Recalling that the sum is the total number of bye-byemen
s_{n} = s_{n-5} + 2s_{n-4}
I was able to calculate the sum of bye-byeman directly. When implemented together with the fact that the first term for the recurrence formula of the total number of by-by-man is 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
It has finally shrunk to 56B.
We need another twist, so we'll use the array again. Furthermore, since it is at most 100 generations to calculate, I stopped rotating shift and so on. This is not the case when you are pretending to be.
a=[1]*4+[2];exec"print a[-5];a+=[a[-5]+2*a[-4]];"*100
You have now reached 53B. this is
1, 1, 1, 1, 2, 3, 3, 3, 5, 8, ...
In an array that grows indefinitely by adding the total number of the next generation according to the recurrence formula, the position -5 from the end is output as the total number of the current generation.
The code in 53B uses a negative value for the array index, which is a loss of'-'. You can reverse the order of this array, trim the'-'three, and replace + = with = and + a instead, which is a reduction of 2B.
a=[2]+[1]*4;exec"print a[4];a=[a[4]+2*a[3]]+a;"*100
This was my answer this time.
I wondered if I could cut another byte
I thought about it, but none of them worked. I'm looking forward to the published python answers and answers in other languages.
Finally, we would like to thank Ozy for providing such an interesting issue and CodeIQ for providing the venue.