The strange life of a beehive

Question

Researchers recently discovered an interesting bee colony that lives in an infinite field of honeycomb:

Each cell can house a bee or not. In fact, the lives of those creatures appear to be a bit ... chaotic. It could be calculated that a colony always starts with the following pattern:

_{(Bee drawn by Emmanuel Boutet on Wikimedia Commons. This honeycomb-and-bees image thus is released under CC-By-SA. grumbles)}

After that the bee's life cycles are divided into so-called generations. Each generation old bees die and new ones hatch and it primarily depends on their cell's neighbors:

• If a bee has less than two neighbors it dies due to loneliness.
• If a bee has more than three neighbors it dies due to overcrowding.
• If a cell has two, three or four living bees in neighboring cells a new bee hatches there in the next generation.

Dying bees don't die until the end of a generation so they still affect surrounding cells that might hatch bees in the next generation.

Now that we know how such a colony works, we can simulate it through any number of generations.

Input

Input is a single number N, given on standard input, terminated by a line break. 0 ≤ N ≤ 150. This is the number of generations to simulate.

Output

Output is a single number, on standard output and optionally followed by a single line break, which represents the number of living bees after N generations.

Additional output on standard error is ignored.

Sample inputs

0
5
42
100

Sample outputs

6
44
1029
5296

Winning condition

Shortest code wins, as is customary in golf. In case of a tie, the earlier solution wins.

Test cases

There are two tests scripts, containing identical test cases:

• bash
• PowerShell

Invocation is in both cases: <test script> <my program> [arguments], e.g. ./test ruby beehive.rb or ./test.ps1 ./beehive.exe.

I know there are only 22 tests instead of 151 (mainly because solutions are often quite slow). Please refrain from embedding the exact test cases instead of solving the task. These scripts are a convenience for you to test whether a change still causes the program to behave correctly; not that you can adapt your code to the specific test cases.

Another note

This task was part of a golf contest held at my university during 2011-W24. The scores and languages of our contestants were as follows:

• 336 – C
• 363 – C
• 387 – C
• 389 – Haskell
• 455 – C

Our own solution was

• 230 – Ruby

Answer 1

Ruby, 181 163 153 146 characters

h=[0]*4e4
[0,-200,201,202,2,3].map{|i|h[i]=1}
gets.to_i.times{h=h.map{[g=1,200,201].map{|x|g+=h[x]+h[-x]};g>5-h.rotate![-1]||g<3?0:1}}
p h.count 1

This implementation follows a standard approach using an array h (dimensions 200 x 200 flattened), where each element is either 0 (no bee) or 1 (bee included). The array [0,-200,201,202,2,3] describes the initial positions of bees (relative to any initial cell).

Input and output as specified above, passes all test cases defined.

Edit 1: changed back to a wrapping solution instead of the "additional space"-version (which was shorter in an intermediate version but now is several characters longer).

Edit 2: removed variable b completely.

Edit 3: warning: this edit made the program horribly slow. I thus reduced the dimensions to 200 each which still is sufficient for up to 150 iterations. Instead of indexing the array by a variable we constantly rotate the array forward. Not really good design, but now we are considerably below the 150.

Answer 2

Python, 152 characters

P=[0,2,3,1j,1+1j,1-1j]
for i in' '*input():Q=[p+d for d in(1,-1,1j,-1j,1j-1,1-1j)for p in P];P=set(p for p in Q if 1<Q.count(p)<5-(p in P))
print len(P)

This solution keeps track of bee locations with a set of complex numbers. It is pretty slow because the inner loop is quadratic in the number of bees. I've tested up to 50 and it works.

Answer 3

Python, 171 169 158 chars

w=300
s=w*w
x=[0]*297
h=[1,1,0]+x+[1,0,1,1]+x+[1]+x*s
exec('h=[1<sum(h[(i+x)%s]for x in[-1,-w-1,-w,1,w+1,w])<5-h[i]for i in range(s)];'*input())
print sum(h)

I model the world as a 300*300=900000 1D array (h is actually bigger, but the end is not used), where a bee is a 1 and empty is 0. Size of 300 is fine because at most the growth would be of 2 in each dimension for each generation, and there is no more than 150 generations.

Here is a slightly ungolfed and commented version:

w=300 # width and height of the world
s=w*w
# create initial grid
l=[1,1]+[0]*298+[1,0,1,1]+[0]*297+[1]+[0]*s

for k in range(input()):
  h=l[:]

  for i in range(s):

    # for each point, compute the number of neighbors
    n=sum(map(lambda x:h[(i+x)%s],[-1,-w-1,-w,1,w+1,w]))

    # if that number verifies the conditions, put 1 here, if not put 0
    l[i]=1<n<5-h[i]

print sum(l)