Question

Language: C

Write a function that produces the next generation of cellular automata

Background:

We compactly represent a generation as a 64-bit unsigned long, one bit for each cell. A 1 bit indicates the cell is live, 0 if not. Using this bit-packed representation, the code to read or update a cell is implemented as a bitwise operation Let's trace how one generation advances to the next. A cell and its two neighbors form a "neighborhood". A neighborhood is effectively a 3-bit number, a value from 0 to 7 Consider a live cell with a live left neighbor and an empty right neighbor. The cell's neighborhood in binary is 110, which is the 3-bit number 6. The ruleset dictates whether a cell with neighborhood 6 will be live or empty in the next generation. A ruleset is represented as an 8-bit number, one bit for each of the 8 possible neighborhood configurations. Let's say the ruleset is 93. The number 93 expressed in binary is 01011101. Because the bit at position 6 (note: position 0-> least significant) of the ruleset is 1, this cell will be live in the next generation. Are you getting the sense there will be much binary data to practice your bitwise ops on for this problem?

Function signature:

note that an unsigned long for the next gen is returned as a result.

Function description:

Answer 1

// here is the full code with explanation
// output is attached
?// plz comment if you need further clarification
?// hit a thumbs up if you liked it

?// CODE

#include <stdio.h>

// this function will return 1 if bit in the position pos is 1 in n
// or 0 if the bit in the position pos is 0 in n
// EX: 0101 0010 0011 0101 -> is a 16 bit number be n
// then getBit(n, 2) is 1 because, 2nd bit from lsb(starting from 0) is 1
// getBit(n, 15) is 0 because 15th bit(the msb bit) is 0
int getBit(unsigned long n, int pos) {
    unsigned long n1 = 1;
    n1 = n1 << pos; // this will set n1 as a number in which only pos bit is set and rest are unset
    if(pos < 0 || pos >= 64) return 0;
    //printf(" n: %lu , pos : %d   val : %d   n1 : %lu\n", n, pos, (n & n1) > 0, n1);
    return (n & n1) > 0; // n & n1 is non zero of pos bit is set else it is 0
}

unsigned long nextGen(unsigned long gen, unsigned char ruleset) {
   
    unsigned long nextGeneration = 0; // holds the answer
    for(int i = 0; i < 64; i++) {
        int left = getBit(gen, i-1);
        int cur = getBit(gen, i);
        int right = getBit(gen, i+1);
       
        // we have left, current, and right bits
        // lets create a 3 bit number
        // which will give us the position of the bit in ruleset
        int bitPosition = 4*right + 2*cur + 1*left;
       
        // find the bit at the bitPosition in the given ruleset
        // if it is 1 then ith bit in the nextGeneration will be 1 else 0;
        unsigned long result = getBit(ruleset, bitPosition);
       
        // setting the value of result to the ith bit in the nextGeneration
        nextGeneration = nextGeneration | (result << i);
       
       
    }
    return nextGeneration;
}
int main() {
    //take a number num = 18446744073709551615(in actual code it is -1 but both are same binary number)
    // its binary representation will be 64 1's
    // 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111
    // now take ruleset = 92
    // its binary representaion will be 0101 1100( for this lsb at position 0 and msb at position 7)
    // for this example the answer should be 9223372036854775809 i,e.,
    // 1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001
    // only msb and lsb bits are set
    // for bit 1 in the nextGen number,
    //     left bit : 1
    //     cur bit : 1
    //     right bit: 0 ( as there is no bit right to the lsb)
    // so number will be 110 which equals binary 6.
    // 6th bit in ruleset is 1
    // so bit 1 in nuxtGen is live(means 1).
    // but for others upto 63 bit,
    //     left bit : 1
    //     cur bit : 1
    //     right bit: 1
    //     so number is 7 and the 7th bit in ruleset is 0, so all are zeros
    // for 64th bit
    //     left bit : 0 ( as there is no bit left to msb)
    //     cur bit : 1
    //     right bit: 1
    //     so number is 3, and the 3rd bit in ruleset is 1.
    // so number will have only msb and lsb are set and rest as unset
    unsigned long num = -1; // lets create a number
    unsigned char ruleset = 92;
    unsigned long nextNum = nextGen(num, ruleset);
    printf("Given Number : %lu \nnextGeneration : %lu",num, nextNum);
    return 0;
}

OUTPUT:

Your Output (stdout) Given Number 18446744073709551615 nextGeneration 9223372036854775809