2016-S5 Circle of Life - Brute Force

# 2016-S5 Circle of Life - Brute Force Solution

## Algorithm

The approach in this implementation is to store the 0s and 1s as bits and create the fastest possible bit shifting algorithm to compute the Circle of Life problem directly.

## Testing Results

Task# Test# Cells Iterations Execution Time
1 1 15 15 0.49 seconds
2 2 200 200 0.39 seconds
2 3 2,000 500,000 0.64 seconds
2 4 4,000 10,000,000 1.189 seconds
2 5 4,000 10,000,000 1.185 seconds
2 6 10 20,000,000 0.079 seconds
2 7 15 100,000,000 0.254 seconds
3 8 15 100,000,000 0.285 seconds
3 9 15 1,000,000,000 2.258 seconds
3 10 15 1,000,000,000,000 36 minutes (estimated)
3 11 15 1,000,000,000,000,000 25 days (estimated)
4 12 10,000 10,000,000,000 20 minutes (estimated)
4 13 10,000 10,000,000 2.993 seconds
4 14 100,000 562,949,953,421,311 49 years (estimated)
4 15 100,000 1,000,000,000,000,000 86 years (estimated)

## Implementation

``````#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#define restrict __restrict__

typedef unsigned long long u64;

u64 bitMask;
long blocks;
long extrabits;
long bitCount;
long long iterationCount;
u64* bitBuffer;
u64* leftBuffer;
u64* rightBuffer;

void init_bits(long bits)
{
blocks = (bits + 63) / 64; // Round to the nearest block
extrabits = bits % 64;    // How many bits are left over

u64 start = 0x8000000000000000;

u64 v = start;
for (int i = 0; i < extrabits - 1; i++)
v = (v >> 1) | start;

bitMask = v;

bitBuffer = new u64[blocks];
leftBuffer = new u64[blocks];
rightBuffer = new u64[blocks];
}

void clean_bits(u64 *buffer)
{
// Cleanup the final word
if (extrabits != 0)
buffer[blocks - 1] = buffer[blocks - 1] & bitMask;
}

void circle_shift_right(u64 const * restrict input, u64 * restrict output)
{
// Get the first previous bit from the end of the array
u64 prevbit;
if (extrabits == 0)
prevbit = input[blocks - 1] << 63;
else
prevbit = (input[blocks - 1] << (extrabits - 1)) & 0x8000000000000000;

// Shift the entire array
for (int b = 0; b < blocks; b++)
{
output[b] = (input[b] >> 1) | prevbit;  // Shift automatically leaves a 0
prevbit = input[b] << 63; // Shift automatically fills with 0s
}

clean_bits(output);
}

void circle_shift_left(u64 const * restrict input, u64 * restrict output)
{
// Get the first previous bit as the first bit in the array
u64 prevbit = (input[0] & 0x8000000000000000) >> (extrabits - 1);

// Shift the entire array
for (int b = blocks - 1; b >= 0; b--)
{
output[b] = (input[b] << 1) | prevbit;  // Shift automatically leaves a 0
prevbit = input[b] >> 63; // Shift automatically fills with 0s
}
}

void xor_bits(u64 const * restrict leftBits, u64 const * restrict rightBits, u64 * restrict output)
{
for (int i = 0; i < blocks; i++)
output[i] = leftBits[i] ^ rightBits[i];
}

void text_to_bits(const char * restrict text, u64 * restrict input, int bits)
{
// Dump the bits in the block

for (int b = 0; b < blocks; b++)
{
u64 curBit = 0x8000000000000000;
u64 curValue = 0;
int maxBits = std::min(bits, 64);

for (int bit = 0; bit < maxBits; bit++)
{
if (*text == '1')
curValue |= curBit;

curBit = curBit >> 1;
text++;
}

bits -= maxBits;
*input = curValue;
input++;
}
}

std::string bits_to_text(u64 const *restrict input, int bits)
{
char* text = new char[bits + 1];
char *c = text;

// Dump the bits in the block
for (int b = 0; b < blocks; b++)
{
int curbits = std::min(bits, 64);
bits -= curbits;

for (int i = 0; i < curbits; i++)
{
if (((input[b] & (0x8000000000000000 >> i)) != 0))
*c = '1';
else
*c = '0';
c++;
}
}

*c = '\0';
return std::string(text);
}

//----------------------------------------------------------------
// INPUT
//----------------------------------------------------------------

void read_input()
{
std::string input;

std::cin >> bitCount >> iterationCount;
std::getline(std::cin, input);

init_bits(bitCount);

std::getline(std::cin, input);

text_to_bits(input.c_str(), bitBuffer, bitCount);
}

void write_output()
{
std::cout << bits_to_text(bitBuffer, bitCount);
}

//----------------------------------------------------------------
// SOLVER
//----------------------------------------------------------------

void compute_iteration()
{
// shift bits both left and right
circle_shift_left(bitBuffer, leftBuffer);
circle_shift_right(bitBuffer, rightBuffer);

// Combine into result using XOR operation
xor_bits(leftBuffer, rightBuffer, bitBuffer);
}

void solve_long_iterations()
{
for (long long iteration = 0; iteration < iterationCount; iteration++)
compute_iteration();
}

void solve_short_iterations()
{
// Get the Values
u64 value = bitBuffer[0];
u64 left, right;

for (long long iteration = 0; iteration < iterationCount; iteration++)
{
left = value << 1;
right = (value >> 1) & bitMask;

left |= (value & 0x8000000000000000) >> (extrabits - 1);
right |= (value << (extrabits - 1)) & 0x8000000000000000;

value = left ^ right;
}

bitBuffer[0] = value;
}

int main()
{
read_input();

if (bitCount > 64)
solve_long_iterations();
else
solve_short_iterations();

write_output();

return 0;
}
``````

© 2020 Emmanuel Mathi-Amorim

This website was created using Hugo with the Book theme. Its content is open sourced on GitHub. Please feel free to send us a pull request if you wish to correct an error or add some content.