{"cells":[{"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)\n\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\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\n\nimport numpy as np\nimport matplotlib.pyplot as plt\nfrom IPython.core.pylabtools import figsize\nimport seaborn as sns\nimport pandas as pd\nfrom tqdm import tqdm","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"d629ff2d2480ee46fbb7e2d37f6b5fab8052498a","_cell_guid":"79c7e3d0-c299-4dcb-8224-4455121ee9b0","trusted":true},"cell_type":"code","source":"TRAIN_PATH = '/kaggle/input/conways-reverse-game-of-life-2020/train.csv'\nONE_STEP_START_PATH = '/kaggle/working/onestepstart.npy'\nONE_STEP_STOP_PATH = '/kaggle/working/onestepstop.npy'\ntrainset = pd.read_csv(TRAIN_PATH)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"1. Generation process.\n\nTo evolve, neighbor status and live count shall be calculated for all cells."},{"metadata":{"trusted":true},"cell_type":"code","source":"def gen_grid(N = 20, live_pct = 0.3):\n    '''Generate a grid with size N * N and dencity = live_pct'''\n    return (np.random.random((N,N)) > (1 - live_pct)).astype(int)\n\n\ndef n_lives(g):\n    '''part of grid g * fileter f element size, sum to get number of live neighbors\n     for each cell\n    '''\n    f = np.array([\n          [1., 1., 1.],\n          [1., 0., 1.], \n          [1., 1., 1.]])\n    return (g * f).sum()\n\n\ndef pad_grid(grid):\n    # padd with zeros around grid\n    padded_grid = np.pad(grid,((1,1),(1,1)))\n\n    # for each edge, pad edge of opposite side\n    padded_grid[0,1:-1] = padded_grid[-2,1:-1]\n    padded_grid[-1,1:-1] = padded_grid[1,1:-1]\n    padded_grid[1:-1,0] = padded_grid[1:-1,-2]\n    padded_grid[1:-1,-1] = padded_grid[1:-1,1]\n\n    # for each coner, pad with opposite corner\n    padded_grid[0,0] = grid[-1,-1]\n    padded_grid[-1,-1] = grid[0,0]\n    padded_grid[0,-1] = grid[-1,0]\n    padded_grid[-1,0] = grid[0,-1]\n    return padded_grid\n\n\ndef neighbor_count_grid(N):\n    '''count number of neighbors for each cell'''\n    neighbor_count = 8 * np.ones((N,N))\n    neighbor_count[[0, N-1],:] = 5\n    neighbor_count[:,[0, N-1]] = 5\n    neighbor_count[0,0] = neighbor_count[0,N-1] = 3\n    neighbor_count[N-1,0] = neighbor_count[N-1,N-1] = 3\n    return neighbor_count\n\n\ndef board_lives(grid):\n    '''for all cell in grid, count live neighbors'''\n    n = grid.shape[0]\n    padded_grid = pad_grid(grid)\n    lives = np.zeros((n,n))\n    for i in range(1, n + 1):\n        for j in range(1, n + 1):\n            lives[i-1,j-1] = n_lives(padded_grid[i-1: i+2, j-1:j+2])\n    return lives\n\n\ndef board_dies(lives, neighbors):\n    '''for all cells count died neigbors'''\n    return neighbors - lives\n\n\ndef evolve(grid, lives):\n\n    '''evolve base'''\n    new_grid = grid.copy()\n\n    # criterion\n    over_population = np.where(grid * lives > 3)\n    stasis = np.where(np.logical_or(grid * lives == 2, grid * lives == 3))\n    under_population = np.where(grid * lives < 2)\n    reproduction = np.where(np.logical_not(grid).astype(int) * lives == 3)\n\n    # apply criterion\n    new_grid[over_population] = 0\n    new_grid[stasis] = 1\n    new_grid[under_population] = 0\n    new_grid[reproduction] = 1\n    return new_grid\n\ndef one_step_evolve(grid):\n    '''evolve one step, including live counts and rule apply'''\n    lives = board_lives(grid)\n    evolved_grid = evolve(grid, lives)\n    return evolved_grid\n\ndef n_step_evolve(grid, steps):\n    '''evolve many steps, 55-70 iterations per second'''\n    for step in range(steps):\n        grid = one_step_evolve(grid)\n    return grid\n\n\ndef show_all(grid, padded_grid, lives, dies):\n    '''generate visualizations'''\n    figsize(15,12)\n    plt.subplot(2,2,1)\n    sns.heatmap(grid, linewidth = 1)\n    plt.title('Grid State')\n    plt.subplot(2,2,2)\n    sns.heatmap(padded_grid, linewidth = 1)\n    plt.title('Padded State')\n    plt.subplot(2,2,3)\n    sns.heatmap(lives, annot = True, linewidth = 1)\n    plt.title('Live State')\n    plt.subplot(2,2,4)\n    sns.heatmap(dies, annot = True, linewidth = 1)\n    plt.title('Die State')\n    plt.show()","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"A view of generated boards"},{"metadata":{"trusted":true},"cell_type":"code","source":"N = 20\nlive_pct = 0.3\ngrid = gen_grid(N, live_pct)\npadded_grid = pad_grid(grid)\nneighbor_count=  neighbor_count_grid(N)\nlives = board_lives(grid)\ndies = board_dies(lives, neighbor_count)\nshow_all(grid, padded_grid, lives, dies)\nevolved_grid = evolve(grid, lives)\n\n\nfigsize(15,5)\nplt.subplot(1,2,1)\nsns.heatmap(grid, linewidth = 1)\nplt.subplot(1,2,2)\nsns.heatmap(evolved_grid,linewidth = 1)\nplt.show()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"grids = trainset.copy()","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Test generation process"},{"metadata":{"trusted":true},"cell_type":"code","source":"start_grids = grids[[col for col in grids.columns if col.startswith('start')]]\nstop_grids = grids[[col for col in grids.columns if col.startswith('stop')]]\ngrid_steps = grids.delta.values\n\nN = 25\n\naccs = []\nfor idx in tqdm(range(len(start_grids))[:1000]):\n    start = start_grids.iloc[idx].values.reshape(25,25)\n    stop = stop_grids.iloc[idx].values.reshape(25,25)\n    steps = grid_steps[idx]\n    gen_stop = n_step_evolve(start, steps)\n    accuracy = (stop == gen_stop).mean()\n    accs.append(accuracy)\n\n'Correct Code' if np.mean(accs) == 1 else 'Bugs exists'","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Visualizations of generated board"},{"metadata":{"trusted":true},"cell_type":"code","source":"N = 25\nidx =  np.random.choice(np.arange(len(start_grids)))\nstart = start_grids.iloc[idx].values.reshape(25,25)\nstop = stop_grids.iloc[idx].values.reshape(25,25)\nsteps = grid_steps[idx]\ngen_stop = n_step_evolve(start, steps)\naccuracy = (stop == gen_stop).mean()\nprint('Generation accuracy: {}'.format(accuracy))\n\n\nfigsize(28,6)\nplt.subplot(1,4,1)\nsns.heatmap(start,  linewidth = 1)\nplt.title('Start')\n\nplt.subplot(1,4,2)\nsns.heatmap(stop, linewidth = 1)\nplt.title('Result')\n\n\nplt.subplot(1,4,3)\nsns.heatmap(gen_stop, linewidth = 1)\nplt.title('Generate')\n\nplt.subplot(1,4,4)\nsns.heatmap(gen_stop == stop, linewidth = 1)\nplt.title('Error location')\nplt.show()","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Generate one step sampels, devolve one step at a time"},{"metadata":{"trusted":true},"cell_type":"code","source":"# def generate_onestep_samples(start_grids, grid_steps):\n#     '''Use given start grids, grid steps to generate one step samles\n#      Use implemented algorithm to generate next step\n#      Each start grid generate a sequence of start and stop samples (all onestep)\n#     '''\n\n#     start_samples_onestep = []\n#     stop_samples_onestep = []\n\n#     for idx in tqdm(range(len(start_grids))):\n#         sta = start_grids.iloc[idx].values.reshape(25,25)\n#         for st in range(grid_steps[idx]):\n#             sto = n_step_evolve(sta,1)\n#             start_samples_onestep.append(sta.reshape(625))\n#             stop_samples_onestep.append(sto.reshape(625))\n#             sta = sto\n        \n#     np.save(ONE_STEP_START_PATH, np.array(start_samples_onestep))\n#     np.save(ONE_STEP_STOP_PATH, np.array(stop_samples_onestep))\n#     return np.array(start_samples_onestep),np.array(stop_samples_onestep)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# start_samples_onestep, stop_samples_onestep = generate_onestep_samples(start_grids, grid_steps)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# figsize(16,6)\n# plt.subplot(1,2,1)\n\n# idx = np.random.randint(0, len(start_samples_onestep))\n# sns.heatmap(start_samples_onestep[idx].reshape(25,25), linewidth = 1)\n# plt.title('Start Sample')\n# plt.subplot(1,2,2)\n# sns.heatmap(stop_samples_onestep[idx].reshape(25,25), linewidth = 1)\n# plt.title('Stop Sample')\n\n\n# (start_samples_onestep[idx].reshape(25,25) == stop_samples_onestep[idx].reshape(25,25)).mean()","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"For sparse boards evoving 1 step, it is almost the same as start board, complexity increase as density increase"},{"metadata":{"trusted":true},"cell_type":"code","source":"# results = [[start_samples_onestep[i].mean(), (start_samples_onestep[i] == stop_samples_onestep[i]).mean()] for i in range(len(start_samples_onestep))]\n# figsize(8,6)\n# results = np.array(results)\n# plt.scatter(results[:,0], results[:,1], alpha = 0.1)\n# plt.xlabel('Board density')\n# plt.ylabel('Percent stop equal start')\n# plt.show()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# plt.hist(start_samples_onestep.mean(axis = 1))\n# plt.show()","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Creating a NN model tends to predict the same thing as start board...."},{"metadata":{"trusted":true},"cell_type":"code","source":"from tensorflow.keras.layers import Conv2D, MaxPooling2D, Dense, Input, Flatten,GlobalMaxPooling2D, GlobalAveragePooling2D, Concatenate, BatchNormalization\nfrom tensorflow.keras.layers import Embedding, Reshape, Dot, Multiply\nfrom tensorflow.keras.layers import Activation\nfrom tensorflow.keras.models import Model, Sequential\nfrom tensorflow.keras.utils import plot_model\nfrom tensorflow.keras.optimizers import Adam, SGD, RMSprop\nimport tensorflow as tf","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"start_grids = grids[[col for col in grids.columns if col.startswith('start')]]\nstop_grids = grids[[col for col in grids.columns if col.startswith('stop')]]\ngrid_steps = grids.delta.values\n\ntargets = start_grids.values.reshape(-1,25,25,1)\nfeatures = stop_grids.values.reshape(-1,25,25,1)\ngrid_steps.shape, targets.shape, features.shape","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"inputs = Input((25,25,1))\n\nstep_in = Input(1,)\nstep_out = Embedding(input_dim = 6, output_dim = 625, input_length = 1)(step_in)\nstep_out = Reshape((25,25,1))(step_out)\n\nx1 = Conv2D(128,3,activation = None,padding = 'same', name = 'conv_size_3')(inputs)\nbn1 = BatchNormalization()(x1)\nbn1 = Activation('elu')(bn1)\nx2 = Conv2D(32,4,activation = None,padding = 'same',name = 'conv_size_4')(inputs)\nbn2 = BatchNormalization()(x2)\nbn2 = Activation('elu')(bn2)\nx3 = Conv2D(10,5,activation = None,padding = 'same',name = 'conv_size_5')(inputs)\nbn3 = BatchNormalization()(x3)\nbn3 = Activation('elu')(bn3)\nx4 = Conv2D(10,7,activation = None,padding = 'same',name = 'conv_size_7')(inputs)\nbn4 = BatchNormalization()(x4)\nbn4 = Activation('elu')(bn4)\nx5 = Conv2D(10,9,activation = None,padding = 'same',name = 'conv_size_9')(inputs)\nbn5 = BatchNormalization()(x5)\nbn5 = Activation('elu')(bn5)\n\n\nx = Concatenate(axis = -1)([bn1, bn2, bn3, bn4, bn5])\n\nx = Conv2D(32,3, activation = 'elu', padding = 'same', name = 'conv1_out_1')(x)\nx = Multiply()([step_out, x])\nx = Conv2D(32,3, activation = 'elu', padding = 'same', name = 'conv1_out_2')(x)\nx = Multiply()([step_out, x])\nx = Conv2D(32,3, activation = 'elu', padding = 'same', name = 'conv1_out_3')(x)\nx = Multiply()([step_out, x])\nx = Conv2D(32,3, activation = 'elu', padding = 'same', name = 'conv1_out_4')(x)\nx = Multiply()([step_out, x])\nx = Conv2D(32,3, activation = 'elu', padding = 'same', name = 'conv1_out_5')(x)\nx = Multiply()([step_out, x])\n\nx = Conv2D(1,3, activation = 'sigmoid', padding = 'same', name = 'conv1_out_final')(x)\nmodel = Model([inputs,step_in], x)\nmodel.summary()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"model.compile(loss = 'binary_crossentropy',optimizer = Adam(lr = 0.001),metrics = ['accuracy'])\nmodel.fit(x = [features, grid_steps],y = targets, epochs = 140, validation_split = 0.05, batch_size = 128)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"test_grids = pd.read_csv('/kaggle/input/conways-reverse-game-of-life-2020/test.csv')\nstop_grids_test = test_grids[[col for col in grids.columns if col.startswith('stop')]]\ngrid_steps_test = test_grids.delta.values\nfeatures_test = stop_grids_test.values.reshape(-1,25,25,1)\ntest_predictions = model.predict(x = [features_test, grid_steps_test])","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"submissions = pd.DataFrame((test_predictions.reshape(-1,625) > 0.5).astype(int), columns = [f'start_{i}'for i in np.arange(625)])\nsubmissions['id'] = test_grids.id.values","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"submissions.to_csv(\"submission.csv\", index=False)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"submissions.head()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"","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}