I counted bye bye man

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.

Simple algorithm

Analyze the problem 1

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.

[85B] First code

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.

[71B] First one liner

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.

[67B] Stop the array

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.

[64B] Swap without using temporary variables

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.

[62B] Summarize common calculations

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.

Optimal (not) algorithm

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.

Analyze the problem 2

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.

[63B] Strategic retreat

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.

Recurrence formula between adjacent six terms

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} $)

  1. c_{1, n} = c_{6, n-1} + c_{8, n-1}
  2. c_{2, n} = c_{1, n-1} + c_{6, n-1}
  3. c_{4, n} = c_{2, n-1}
  4. c_{8, n} = c_{4, n-1}
  5. c_{6, n} = c_{8, n-1}

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.

[63B] Stagnation

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.

[56B] Finally move forward

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.

[53B] Array again

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.

[51B] Last idea

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.

Finally

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.

Recommended Posts

I counted bye bye man
I counted the grains