{"cells":[{"metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","trusted":true},"cell_type":"code","source":"import numpy as np\nfrom scipy.signal import convolve2d\nimport tensorflow as tf\nimport keras\nfrom keras import layers\nimport matplotlib.pyplot as plt\nimport pandas as pd\nfrom sklearn.model_selection import train_test_split\nfrom random import randint, random\nimport sys\nimport gc","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"def life_step(X):\n    \"\"\"Game of life step using scipy tools\"\"\"\n    X_pad = np.zeros((X.shape[0], X.shape[1]+2, X.shape[2]+2))\n    N = np.zeros((X.shape[0], X.shape[1]+2, X.shape[2]+2))\n    X_pad[:,1:-1,1:-1] += X\n    \n    X_pad[:, 0, 1:-1] = X[:, -1, :]\n    X_pad[:, -1, 1:-1] = X[:, 0, :]\n    \n    X_pad[:, 1:-1, 0] = X[:, :, -1]\n    X_pad[:, 1:-1, -1] = X[:, :, 0]\n    \n    X_pad[:, 0, 0] = X[:, -1, -1]\n    X_pad[:, 0, -1] = X[:, -1, 0]\n    X_pad[:, -1, 0] = X[:, 0, -1]\n    X_pad[:, -1, -1] = X[:, 0, 0]\n    \n    N[:, 1:, 1:] += X_pad[:,:-1,:-1]\n    N[:, 1:, :] += X_pad[:,:-1,:]\n    N[:, 1:, :-1] += X_pad[:,:-1,1:]\n\n    N[:, :, 1:] += X_pad[:,:,:-1]\n    N[:, :, :-1] += X_pad[:,:,1:]\n\n    N[:, :-1, 1:] += X_pad[:,1:,:-1]\n    N[:, :-1, :] += X_pad[:,1:,:]\n    N[:, :-1, :-1] += X_pad[:,1:,1:]\n    \n    N = N[:,1:-1,1:-1]\n\n    return np.logical_or(N == 3, np.logical_and(X, N==2)).astype(np.uint8)\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"train = pd.read_csv(\"../input/conways-reverse-game-of-life-2020/train.csv\", index_col='id').values\ntest = pd.read_csv(\"../input/conways-reverse-game-of-life-2020/test.csv\", index_col='id').values\n\ntrain_delta = train[:,0]\ntest_delta = test[:,0]\n\nX_train = train[:, 1:626].reshape((-1, 25, 25))\ny_train = train[:, 626:].reshape((-1, 25, 25))\nX_test = test[:, 1:626].reshape((-1, 25, 25))\n\nprint(train_delta.shape, X_train.shape, y_train.shape)\nprint(test_delta.shape, X_test.shape)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"current_step = X_train\nstop = []\nstart = []\nfor i in range(5):\n    current_mask = train_delta >= i+1\n    start.append(current_step[current_mask])\n    current_step = life_step(current_step)\n    stop.append(current_step[current_mask])\nX_train = np.concatenate(stop, axis=0)\ny_train = np.concatenate(start, axis=0)\nprint(X_train.shape, y_train.shape, train_delta.sum())","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"X_train, X_val, y_train, y_val = train_test_split(X_train, y_train, test_size=0.33)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"p0 = 0.3058699275697248\ndef iterate_training_batch(batch_size):\n    ids = np.random.permutation(np.arange(len(X_train)))\n    while 1:\n        #y = np.random.randint(0, 2, (batch_size, game_dim, game_dim))\n        #X = life_step(y)\n        \n        #yield (np.expand_dims(X.astype(np.float32), axis=-1), np.expand_dims(y.astype(np.float32), axis=-1))\n        batch_mask = ids[:batch_size]\n        ids = ids[batch_size:]\n        \n        if len(ids) < batch_size:\n            ids = np.random.permutation(np.arange(len(X_train)))\n            \n        X = X_train[batch_mask]\n            \n        X_pad = np.zeros((X.shape[0], X.shape[1]+2, X.shape[2]+2))\n        N = np.zeros((X.shape[0], X.shape[1]+2, X.shape[2]+2))\n        X_pad[:,1:-1,1:-1] += X\n\n        X_pad[:, 0, 1:-1] = X[:, -1, :]\n        X_pad[:, -1, 1:-1] = X[:, 0, :]\n\n        X_pad[:, 1:-1, 0] = X[:, :, -1]\n        X_pad[:, 1:-1, -1] = X[:, :, 0]\n\n        X_pad[:, 0, 0] = X[:, -1, -1]\n        X_pad[:, 0, -1] = X[:, -1, 0]\n        X_pad[:, -1, 0] = X[:, 0, -1]\n        X_pad[:, -1, -1] = X[:, 0, 0]\n\n        N[:, 1:, 1:] += X_pad[:,:-1,:-1]\n        N[:, 1:, :] += X_pad[:,:-1,:]\n        N[:, 1:, :-1] += X_pad[:,:-1,1:]\n\n        N[:, :, 1:] += X_pad[:,:,:-1]\n        N[:, :, :-1] += X_pad[:,:,1:]\n\n        N[:, :-1, 1:] += X_pad[:,1:,:-1]\n        N[:, :-1, :] += X_pad[:,1:,:]\n        N[:, :-1, :-1] += X_pad[:,1:,1:]\n\n        N = N[:,1:-1,1:-1]\n        \n        X_indic = np.ones_like(X) * p0\n        indic_mask = np.logical_and(N==0, X==0)\n        X_indic[indic_mask] = 0\n        prop_clue = np.repeat(np.random.random(batch_size), X.shape[-2] * X.shape[-1]).reshape(X.shape)\n        clues_mask = np.random.random(X.shape) < prop_clue\n        X_indic[clues_mask] = y_train[batch_mask][clues_mask]\n\n        X = np.concatenate((np.expand_dims(X, axis=-1), np.expand_dims(X_indic, axis=-1)), axis=-1)\n\n        yield X.astype(np.float32), np.expand_dims(y_train[batch_mask].astype(np.float32), axis=-1)\n\ndef iterate_val_batch(batch_size):\n    ids = np.random.permutation(np.arange(len(X_val)))\n    while 1:\n        #y = np.random.randint(0, 2, (batch_size, game_dim, game_dim))\n        #X = life_step(y)\n        \n        #yield (np.expand_dims(X.astype(np.float32), axis=-1), np.expand_dims(y.astype(np.float32), axis=-1))\n        batch_mask = ids[:batch_size]\n        ids = ids[batch_size:]\n        \n        if len(ids) < batch_size:\n            ids = np.random.permutation(np.arange(len(X_val)))\n            \n        X = X_val[batch_mask]\n\n        X_pad = np.zeros((X.shape[0], X.shape[1]+2, X.shape[2]+2))\n        N = np.zeros((X.shape[0], X.shape[1]+2, X.shape[2]+2))\n        X_pad[:,1:-1,1:-1] += X\n\n        X_pad[:, 0, 1:-1] = X[:, -1, :]\n        X_pad[:, -1, 1:-1] = X[:, 0, :]\n\n        X_pad[:, 1:-1, 0] = X[:, :, -1]\n        X_pad[:, 1:-1, -1] = X[:, :, 0]\n\n        X_pad[:, 0, 0] = X[:, -1, -1]\n        X_pad[:, 0, -1] = X[:, -1, 0]\n        X_pad[:, -1, 0] = X[:, 0, -1]\n        X_pad[:, -1, -1] = X[:, 0, 0]\n\n        N[:, 1:, 1:] += X_pad[:,:-1,:-1]\n        N[:, 1:, :] += X_pad[:,:-1,:]\n        N[:, 1:, :-1] += X_pad[:,:-1,1:]\n\n        N[:, :, 1:] += X_pad[:,:,:-1]\n        N[:, :, :-1] += X_pad[:,:,1:]\n\n        N[:, :-1, 1:] += X_pad[:,1:,:-1]\n        N[:, :-1, :] += X_pad[:,1:,:]\n        N[:, :-1, :-1] += X_pad[:,1:,1:]\n\n        N = N[:,1:-1,1:-1]\n        \n        X_indic = np.ones_like(X) * p0\n        indic_mask = np.logical_and(N==0, X==0)\n        X_indic[indic_mask] = 0\n        prop_clue = np.repeat(np.random.random(batch_size), X.shape[-2] * X.shape[-1]).reshape(X.shape)\n        clues_mask = np.random.random(X.shape) < prop_clue\n        X_indic[clues_mask] = y_val[batch_mask][clues_mask]\n        \n        X = np.concatenate((np.expand_dims(X, axis=-1), np.expand_dims(X_indic, axis=-1)), axis=-1)\n                        \n        yield X.astype(np.float32), np.expand_dims(y_val[batch_mask].astype(np.float32), axis=-1)\n         ","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"game_dim = 25\nbatch_size = 128\n\nINITIAL_CONV = 64\nRES_LAYERS = 6","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"class ResnetIdentityBlock(keras.Model):\n  def __init__(self, kernel_size, filters):\n    super(ResnetIdentityBlock, self).__init__(name='')\n    filters1, filters2, filters3 = filters\n\ndef get_model(input_shape):\n  t_input = keras.layers.Input(input_shape)\n  x = keras.layers.Conv2D(INITIAL_CONV, 3, padding='same')(t_input)\n  x = keras.layers.BatchNormalization()(x)\n  x = keras.activations.relu(x)\n  for _ in range(RES_LAYERS):\n    x_input = x\n    x = keras.layers.Conv2D(INITIAL_CONV, 3, padding='same')(x)\n    x = keras.layers.BatchNormalization()(x)\n    x = tf.nn.relu(x)\n\n    x = keras.layers.Conv2D(INITIAL_CONV, 3, padding='same')(x)\n    x = keras.layers.BatchNormalization()(x)\n\n    x += x_input\n    x = keras.layers.Conv2D(1, 3, padding='same')(x)\n    x = keras.activations.sigmoid(x)\n\n  return keras.models.Model(inputs=t_input, outputs=x)\n\ndef build_model():\n  return get_model((game_dim, game_dim, 2))","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"class Sampling(layers.Layer):\n    \"\"\"Uses (z_mean, z_log_var) to sample z, the vector encoding a digit.\"\"\"\n\n    def call(self, inputs):\n        z_mean, z_log_var = inputs\n        batch = tf.shape(z_mean)[0]\n        dim = tf.shape(z_mean)[1]\n        epsilon = keras.backend.random_normal(shape=(batch, dim))\n        return z_mean + tf.exp(0.5 * z_log_var) * epsilon\n    \nlatent_dim = 20\n\ndef get_encoder():\n    encoder_inputs = keras.Input(shape=(game_dim, game_dim, 1))\n    x = layers.Conv2D(32, 3, activation=\"relu\", strides=2, padding=\"same\")(encoder_inputs)\n    \n    x = layers.Conv2D(64, 3, activation=\"relu\", strides=2, padding=\"same\")(x)\n    \n    x = layers.Flatten()(x)\n    x = layers.Dense(16, activation=\"relu\")(x)\n    z_mean = layers.Dense(latent_dim, name=\"z_mean\")(x)\n    z_log_var = layers.Dense(latent_dim, name=\"z_log_var\")(x)\n    z = Sampling()([z_mean, z_log_var])\n    encoder = keras.Model(encoder_inputs, [z_mean, z_log_var, z], name=\"encoder\")\n    encoder.summary()\n    return encoder\n\ndef get_decoder():\n    latent_inputs = keras.Input(shape=(latent_dim,))\n    x = layers.Dense(6 * 6 * 64, activation=\"relu\")(latent_inputs)\n    x = layers.Reshape((6, 6, 64))(x)\n    x = layers.Conv2DTranspose(64, 3, activation=\"relu\", strides=2, padding=\"same\")(x)\n    \n    x = layers.Conv2DTranspose(32, 3, activation=\"relu\", strides=2, padding=\"valid\")(x)\n    \n    x = keras.activations.sigmoid(x)\n    decoder_outputs = layers.Conv2DTranspose(1, 3, activation=\"sigmoid\", padding=\"same\")(x)\n    decoder = keras.Model(latent_inputs, decoder_outputs, name=\"decoder\")\n    decoder.summary()\n    return decoder\n\nclass VAE(keras.Model):\n    def __init__(self, encoder, decoder, **kwargs):\n        super(VAE, self).__init__(**kwargs)\n        self.encoder = encoder\n        self.decoder = decoder\n        \n    def call(self, inputs):\n        z_mean, z_log_var, z = self.encoder(inputs)\n        return self.decoder(z)\n\n    def train_step(self, data):\n        if isinstance(data, tuple):\n            data = data[0]\n        with tf.GradientTape() as tape:\n            z_mean, z_log_var, z = self.encoder(data)\n            reconstruction = self.decoder(z)\n            reconstruction_loss = tf.reduce_mean(\n                keras.losses.binary_crossentropy(data, reconstruction)\n            )\n            reconstruction_loss *= 25 * 25\n            kl_loss = 1 + z_log_var - tf.square(z_mean) - tf.exp(z_log_var)\n            kl_loss = tf.reduce_mean(kl_loss)\n            kl_loss *= -0.5\n            total_loss = reconstruction_loss + kl_loss\n        grads = tape.gradient(total_loss, self.trainable_weights)\n        self.optimizer.apply_gradients(zip(grads, self.trainable_weights))\n        return {\n            \"loss\": total_loss,\n            \"reconstruction_loss\": reconstruction_loss,\n            \"kl_loss\": kl_loss,\n        }\n\ndef get_VAE():\n    return VAE(get_encoder(), get_decoder())","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"model = build_model()\n\nmodel.compile(loss=tf.keras.losses.MeanSquaredError(), optimizer=tf.keras.optimizers.Adam(), metrics=['accuracy'])\n\nreduce_lr = tf.keras.callbacks.ReduceLROnPlateau(monitor='val_loss', factor=0.5, patience=2, min_lr=0.00001, verbose=1)\n\nfile_path = 'best_model.hdf5'\n\nmodel_checkpoint = tf.keras.callbacks.ModelCheckpoint(filepath=file_path, monitor='val_loss',\n                                                    save_best_only=True)\n\ncallbacks = [reduce_lr, model_checkpoint]\n#callbacks = [model_checkpoint]\n\nmodel.summary()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"hist = model.fit(\n    iterate_training_batch(batch_size),\n    steps_per_epoch=len(X_train)//batch_size,\n    epochs=30,\n    verbose=1,\n    callbacks=callbacks,\n    validation_data=iterate_val_batch(batch_size),\n    validation_steps=len(X_val)//batch_size,\n    shuffle=True\n)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"del X_train\ndel y_train\ndel X_val\ndel y_val\ndel train\ndel train_delta\ngc.collect()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"model.load_weights('./best_model.hdf5')","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"def get_padded_version_n(X):\n    X_pad = np.zeros((X.shape[0], X.shape[-2] + 2, X.shape[-1] + 2), dtype=X.dtype)\n    X_pad[:, 1:-1,1:-1] += X\n    \n    X_pad[:, 0, 1:-1] = X[:, -1, :]\n    X_pad[:, -1, 1:-1] = X[:, 0, :]\n    \n    X_pad[:, 1:-1, 0] = X[:, :, -1]\n    X_pad[:, 1:-1, -1] = X[:, :, 0]\n    \n    X_pad[:, 0, 0] = X[:, -1, -1]\n    X_pad[:, 0, -1] = X[:, -1, 0]\n    X_pad[:, -1, 0] = X[:, 0, -1]\n    X_pad[:, -1, -1] = X[:, 0, 0]\n    \n    return X_pad\n\ndef solve(F, d):\n    sF = F\n    P = p0 * np.ones_like(F)\n    \n    F_pad = get_padded_version_n(F)\n    \n    N = np.zeros(F_pad.shape)\n    \n    N[:, 1:, 1:] += F_pad[:,:-1,:-1]\n    N[:, 1:, :] += F_pad[:,:-1,:]\n    N[:, 1:, :-1] += F_pad[:,:-1,1:]\n\n    N[:, :, 1:] += F_pad[:,:,:-1]\n    N[:, :, :-1] += F_pad[:,:,1:]\n\n    N[:, :-1, 1:] += F_pad[:,1:,:-1]\n    N[:, :-1, :] += F_pad[:,1:,:]\n    N[:, :-1, :-1] += F_pad[:,1:,1:]\n\n    N = N[:,1:-1,1:-1]\n    \n    P[np.logical_and(N==0, F==0)] = 0\n    print(\"Starting from\", np.logical_and(N==0, F==0).sum(axis=(-1, -2)) / (F.shape[-2] * F.shape[-1]))\n    \n    I = np.zeros_like(F)\n    global_mask = np.ones(F.shape[0]).astype(np.bool_)\n    \n    while len(F):\n        X = np.concatenate((np.expand_dims(F, axis=-1), np.expand_dims(P, axis=-1)), axis=-1)\n        y = model.predict(X)[:, :, :, 0]\n        del X\n        y[P==0.0] = 0\n        y[P==1.0] = 1\n        H = abs(y - 0.5)\n        H_eff = (H * (H<0.5).astype(np.float32))\n        change_mask = H == np.repeat(H_eff.max(axis=(-1, -2)), F.shape[-2] * F.shape[-1]).reshape(H.shape)\n        nP = y\n        p_step = nP[change_mask]\n        nP[change_mask] = np.round(p_step)\n        \n        qsure = ((nP==0.0).sum(axis=(-1, -2)) + (nP==1.0).sum(axis=(-1, -2))) / (F.shape[-2] * F.shape[-1])\n        local_continue_mask = qsure < 1.0\n        local_stop_mask = np.logical_not(local_continue_mask)\n        \n        if local_stop_mask.sum() > 0:\n            eq = (life_step(nP[local_stop_mask]) == F[local_stop_mask])\n            I[np.arange(len(I))[global_mask][local_stop_mask]] = nP[local_stop_mask]\n            d[np.arange(len(d))[global_mask][local_stop_mask]] -= 1\n            F[local_stop_mask] = nP[local_stop_mask]\n            \n            nF = F[local_stop_mask]\n            n_p = p0 * np.ones_like(nF)\n            nF_pad = get_padded_version_n(nF)\n\n            nN = np.zeros_like(nF_pad)\n\n            nN[:, 1:, 1:] += nF_pad[:,:-1,:-1]\n            nN[:, 1:, :] += nF_pad[:,:-1,:]\n            nN[:, 1:, :-1] += nF_pad[:,:-1,1:]\n\n            nN[:, :, 1:] += nF_pad[:,:,:-1]\n            nN[:, :, :-1] += nF_pad[:,:,1:]\n\n            nN[:, :-1, 1:] += nF_pad[:,1:,:-1]\n            nN[:, :-1, :] += nF_pad[:,1:,:]\n            nN[:, :-1, :-1] += nF_pad[:,1:,1:]\n\n            nN = nN[:,1:-1,1:-1]\n            \n            n_p[np.logical_and(nN==0, nF==0)] = 0\n            \n            nP[local_stop_mask] = n_p\n            \n            local_continue_mask[local_stop_mask] = d[global_mask][local_stop_mask] > 0\n            F = F[local_continue_mask]\n            nP = nP[local_continue_mask]\n            \"\"\"\n            print(\"Done for {}, steps {}, continuing with {} items\".format(\n                np.arange(len(I))[global_mask][local_stop_mask],\n                d[global_mask][local_stop_mask],\n                local_continue_mask.sum()\n            ))\n            \"\"\"\n            print(local_continue_mask.sum(), \" items left\")\n            global_mask[global_mask] = local_continue_mask\n            \n            del eq\n            del nN\n            del nF\n            del nF_pad\n        P = nP\n        del y\n        del H\n        del H_eff\n        del change_mask\n        del p_step\n        del qsure\n        del local_continue_mask\n        del local_stop_mask\n        gc.collect()\n    return I","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"def get_optimized_solution_and_score(y, delta, labels):\n    current_step = y\n    res = np.zeros_like(y)\n    for i in range(5):\n        current_mask = delta >= i+1\n        current_step = life_step(current_step)\n        res[delta == i+1] = current_step[delta == i+1]\n    y_scores = (labels == res).mean(axis=(-2, -1))\n    blank_scores = 1 - (labels.mean(axis=(-2, -1)))\n    score_mask = blank_scores > y_scores\n    res[score_mask] = 0\n    score = np.concatenate((blank_scores[score_mask], y_scores[np.logical_not(score_mask)]))\n    return res, 1 - score.mean()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"y = solve(X_test, np.copy(test_delta))","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"y_final, score = get_optimized_solution_and_score(y, test_delta, X_test)\nblank_score = X_test.mean()\nprint(score, blank_score - score)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"submission = pd.read_csv(\"../input/conways-reverse-game-of-life-2020/sample_submission.csv\", index_col='id')\nsubmission_values = y_final.reshape((len(submission), 625))\nfor i, col in enumerate(submission.columns):\n    submission[col].values[:] = submission_values[:, i]\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"submission.to_csv(\"submission.csv\")","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}