{"cells":[{"metadata":{},"cell_type":"markdown","source":"# Conway's Reverse Game of Life 2020","execution_count":null},{"metadata":{},"cell_type":"markdown","source":"![Game of Life](https://i.ytimg.com/vi/4nCTgnbz2fM/maxresdefault.jpg)","execution_count":null},{"metadata":{},"cell_type":"markdown","source":"The Game of Life is, briefly, a two-dimensional cellular automata universe governed by a simple set of birth, death and survival rules. It was invented in 1970 by the Cambridge mathematician John Conway and popularized by a series of articles in \"Scientific American\" by Martin Gardner. Each of the cells in the 2d universe can be in one of two states: alive or dead. Beginning with any given initial pattern of live cells, one can employ Conway's rules in order to determine the behavior of the universe over any number of generations or time steps. Whether a cell survives, dies or comes into being is determined by the number of live neighbors the cell has. Each cell has eight possible neighbors (four on its sides, four on its corners).","execution_count":null},{"metadata":{},"cell_type":"markdown","source":"![life](https://www.researchgate.net/profile/Yan_Liu40/publication/274743186/figure/fig3/AS:667642776006657@1536189850143/Element-of-cellular-automata-CA-top-with-Conways-game-of-life-as-illustration.png)","execution_count":null},{"metadata":{},"cell_type":"markdown","source":"# Rules of the game","execution_count":null},{"metadata":{},"cell_type":"markdown","source":"1. Survival: if a live cell has two or three live neighbors, it survives.\n2. Death: if a live cell has less than two or more than three live neighbors, it dies.\n3. birth: if a dead cell has exactly three live neighbors, it is born.\n\n> When one employs these rules to any given initial pattern of live cells, the results can be startling. Complex behavior consisting of various Life forms, composed of several or more living cells, often occurs.\n\n> This is my first competition. If you find this notebook helpful, please upvote. Thank You.","execution_count":null},{"metadata":{},"cell_type":"markdown","source":"# Importing necessary Libraries","execution_count":null},{"metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","trusted":true},"cell_type":"code","source":"# This Python 3 environment comes with many helpful analytics libraries installed\n# It is defined by the kaggle/python Docker image: https://github.com/kaggle/docker-python\n# For example, here's several helpful packages to load\n\nimport numpy as np # linear algebra\nimport pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)\nimport keras as ks\nfrom keras.models import Sequential\nfrom keras.layers import Dense, Dropout, Conv2D, MaxPool2D, Conv2DTranspose, BatchNormalization\nfrom keras.callbacks import EarlyStopping, ModelCheckpoint\nfrom tqdm import tqdm\nimport matplotlib.pyplot as plt\n%matplotlib inline\n# Input data files are available in the read-only \"../input/\" directory\n# For example, running this (by clicking run or pressing Shift+Enter) will list all files under the input directory\n%load_ext Cython\nimport os\nfor dirname, _, filenames in os.walk('/kaggle/input'):\n    for filename in filenames:\n        print(os.path.join(dirname, filename))\n\n# You can write up to 5GB to the current directory (/kaggle/working/) that gets preserved as output when you create a version using \"Save & Run All\" \n# You can also write temporary files to /kaggle/temp/, but they won't be saved outside of the current session","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"d629ff2d2480ee46fbb7e2d37f6b5fab8052498a","_cell_guid":"79c7e3d0-c299-4dcb-8224-4455121ee9b0","trusted":true},"cell_type":"code","source":"sample = pd.read_csv('/kaggle/input/conways-reverse-game-of-life-2020/sample_submission.csv')\ntest = pd.read_csv('/kaggle/input/conways-reverse-game-of-life-2020/test.csv')\ntrain = pd.read_csv('/kaggle/input/conways-reverse-game-of-life-2020/train.csv')\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Exploring Data","execution_count":null},{"metadata":{"trusted":true},"cell_type":"code","source":"train.shape","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"train.head()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"train.id.nunique()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"train.delta.value_counts()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"train.start_0.value_counts()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"train.stop_0.value_counts()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"sample.head()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"sample.describe()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"train.describe()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"sample_start_1 = train.loc[1, train.columns.str.startswith('start')]\nsample_stop_1 = train.loc[1, train.columns.str.startswith('stop')]","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"sample_start_1 = np.asarray(sample_start_1).reshape(25, 25)\nsample_stop_1 = np.asarray(sample_stop_1).reshape(25, 25)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"fig, ax = plt.subplots(1, 2, figsize=(18, 7), dpi=300)\nax[0] = plt.subplot2grid((1,2), (0,0), colspan=1)\nax[1] = plt.subplot2grid((1,2), (0,1), colspan=1)\nax[0].imshow(sample_start_1)\nax[0].set_title('Start Board 1')\nax[1].imshow(sample_stop_1)\nax[1].set_title(f'Board after 1 time step')\nplt.show()","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Check for imbalance in data","execution_count":null},{"metadata":{"trusted":true},"cell_type":"code","source":"train.sum()[1:].sort_values()","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"There is no such imbalance visible in the dataset. Imbalance could have caused some shake-up in the end.","execution_count":null},{"metadata":{"trusted":true},"cell_type":"code","source":"train[:1]","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"gs=train[:1][[col for col in train.columns if 'start' in col]].values.reshape(-1,1)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"plt.plot(gs)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"train['start_0'].plot(kind='hist')","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"train['stop_0'].plot(kind='hist')","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"train.delta.value_counts().plot(kind='bar')\nplt.title('Delta Distribution')\nplt.grid()\nplt.show()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"test.shape","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"test_sum = test.copy()\ntest_sum = test_sum.drop(['id','delta'], axis=1)\nactive_count = test_sum.sum(axis=1)\nactive_count\nplt.hist(active_count.values,50)\nplt.grid()\nplt.title('Number of active cells')\nplt.show()","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# CNN using Cython and Conv2D  [Reference](https://github.com/ptyshevs)","execution_count":null},{"metadata":{"trusted":true},"cell_type":"code","source":"%%cython\ncimport cython\nimport numpy as np\n\n@cython.cdivision(True)\n@cython.boundscheck(False)\n@cython.nonecheck(False)\n@cython.wraparound(False)\ncdef int calc_neighs(unsigned char[:, :] field, int i, int j, int n, int k):\n    cdef:\n        int neighs = 0;\n        int i_min = i - 1;\n        int i_pl = i + 1;\n        int j_min = j - 1;\n        int j_pl = j + 1;\n    neighs = 0\n    if i_min >= 0:\n        if j_min >= 0:\n            neighs += field[i_min, j_min]\n        neighs += field[i_min, j]\n        if j_pl < k:\n            neighs += field[i_min, j_pl]\n    if j_min >= 0:\n        neighs += field[i, j_min]\n    if j_pl < k:\n        neighs += field[i, j_pl]\n    if i_pl < n:\n        if j_min >= 0:\n            neighs += field[i_pl, j_min]\n        neighs += field[i_pl, j]\n        if j_pl < k:\n            neighs += field[i_pl, j_pl]\n    return neighs\n\n@cython.cdivision(True)\n@cython.boundscheck(False)\n@cython.nonecheck(False)\n@cython.wraparound(False)\ncpdef make_move(unsigned char[:, :] field, int moves):\n    cdef:\n        int _, i, j, neighs;\n        int n, k;\n        int switch = 0;\n        unsigned char[:, :] cur_field;\n        unsigned char[:, :] next_field;\n    cur_field = np.copy(field)\n    next_field = np.zeros_like(field, 'uint8')\n    n = field.shape[0]\n    k = field.shape[1]\n    for _ in range(moves):\n        if switch == 0:\n            for i in range(n):\n                for j in range(k):\n                    neighs = calc_neighs(cur_field, i, j, n, k)\n                    if cur_field[i, j] and neighs == 2:\n                        next_field[i, j] = 1\n                    elif neighs == 3:\n                        next_field[i, j] = 1\n                    else:\n                        next_field[i, j] = 0\n        else:\n            for i in range(n):\n                for j in range(k):\n                    neighs = calc_neighs(next_field, i, j, n, k)\n                    if next_field[i, j] and neighs == 2:\n                        cur_field[i, j] = 1\n                    elif neighs == 3:\n                        cur_field[i, j] = 1\n                    else:\n                        cur_field[i, j] = 0\n        switch = (switch + 1) % 2\n    return np.array(next_field if switch else cur_field)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"NROW, NCOL = 25, 25\n\ndef generate_samples(delta=1, n=32):\n    batch = np.split(np.random.binomial(1, 0.5, (NROW * n, NCOL)).astype('uint8'), n)\n    Yy = [life.make_move(state, 5) for state in batch]\n    Xx = [life.make_move(state, 1) for state in Yy]\n    Y = np.array([y.ravel() for y in Yy])\n    X = np.array([x.ravel() for x in Xx])\n    return X, Y\n    \ndef data_generator(delta=1, batch_size=32, ravel=True):\n    while True:\n        batch = np.split(np.random.binomial(1, 0.5, (NROW * batch_size, NCOL)).astype('uint8'),\n                         batch_size)\n        Yy = [make_move(state, 5) for state in batch]\n        Xx = [make_move(state, delta) for state in Yy]\n\n        if ravel:\n            Y = np.array([y.ravel() for y in Yy])\n            X = np.array([x.ravel() for x in Xx])\n            yield X, Y\n        else:\n            yield np.array(Xx)[:,:, :, np.newaxis], np.array(Yy)[:, :, :, np.newaxis]","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"def create_model(n_hidden_convs=2, n_hidden_filters=128, kernel_size=5):\n    nn = Sequential()\n    nn.add(Conv2D(n_hidden_filters, kernel_size, padding='same', activation='relu',\n                  input_shape=(25, 25, 1)))\n    nn.add(BatchNormalization())\n    for i in range(n_hidden_convs):\n        nn.add(Conv2D(n_hidden_filters, kernel_size, padding='same', activation='relu'))\n        nn.add(BatchNormalization())\n    nn.add(Conv2D(1, kernel_size, padding='same', activation='sigmoid'))\n    nn.compile(optimizer='adam', loss='binary_crossentropy', metrics=['accuracy'])\n    return nn","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"models = []\nfor delta in range(1, 6):\n    model = create_model(n_hidden_convs=6, n_hidden_filters=256)\n    es = EarlyStopping(monitor='loss', patience=9, min_delta=0.001)\n    model.fit_generator(data_generator(delta=delta, ravel=False), \n                        steps_per_epoch=500, epochs=50, verbose=1, callbacks=[es])\n    models.append(model)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"test = pd.read_csv('../input/conways-reverse-game-of-life-2020/test.csv', index_col='id')","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"submit_df = pd.DataFrame(index=test.index, columns=['start_' + str(i) for i in range(625)])","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"for delta in range(1, 6):\n    mod = models[delta-1]\n    delta_df = test[test.delta == delta].iloc[:, 1:].values.reshape(-1, 25, 25, 1)\n    submit_df[test.delta == delta] = mod.predict(delta_df).reshape(-1, 625).round(0).astype('uint8')","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"submit_df.to_csv('submission.csv')","execution_count":null,"outputs":[]}],"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat":4,"nbformat_minor":4}