2016-S5 Circle of Life - Solution

# 2016-S5 Circle of Life - Solution

## Declare Variables

``````int *oldGeneration;
int *newGeneration;
int n;
long long t;
``````

## Read Inputs and Write Output

``````void readInput()
{
std::cin >> n >> t;
oldGeneration = new int[n];
newGeneration = new int[n];
std::string input;
std::getline(std::cin, input);
std::getline(std::cin, input);
for (int i = 0; i < n; i++)
{
if (input.c_str()[i] == '0')
oldGeneration[i] = 0;
else
oldGeneration[i] = 1;
}
}

void writeOutput()
{
for (int i = 0; i < n; i++)
{
std::cout << oldGeneration[i];
}
delete oldGeneration;
delete newGeneration;
}
``````

## Get Cyclic Pointer

The list of cells wraps around. We need a function that given a cyclic index returns the real index of the cell.

``````int getCyclicPointer(long long cyclicIndex)
{
long long nonCyclicIndex = cyclicIndex % n;
if (nonCyclicIndex < 0)
return n + nonCyclicIndex;
else
return nonCyclicIndex;
}
``````

## Simulate Generations

``````void simulateGenerations(long long numberOfGenerations)  //Number of generation must be a power of two
{
for (int i = 0; i < n; i++)
{
newGeneration[i] = oldGeneration[getCyclicPointer(i - numberOfGenerations)] ^ oldGeneration[getCyclicPointer(i + numberOfGenerations)];
}
}
``````

## Swap Generation Pointers

``````void swapGenerationPointers()
{
int* intermediate = oldGeneration;
oldGeneration = newGeneration;
newGeneration = intermediate;
}
``````

## Get Largest Power of Two

``````long long getLargestPowerOfTwo(long long max)
{
unsigned long long powerOfTwo = 1;
for (int i = 0; i < 64; i++)
{
powerOfTwo <<= 1;
if (powerOfTwo > max)
{
powerOfTwo >>= 1;
return (long long)powerOfTwo;
}
}
return 0;
}
``````

## Main Method

``````int main()
{
long long generationsLeft = t;
while (generationsLeft > 0)
{
long long largestPowerOfTwo = getLargestPowerOfTwo(generationsLeft);
generationsLeft -= largestPowerOfTwo;
simulateGenerations(largestPowerOfTwo);
swapGenerationPointers();
}
writeOutput();
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.