P191_prize_strings.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "P191_prize_strings.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "d5tQOqnybAv2"
      },
      "source": [
        "Doing it through simple brute force would mean checking all possible strings of length 30. There are 3^30 different strings. That would take weeks to solve!\n",
        "\n",
        "However, note that if say the first 2 letters consist of 2 L's, you don't need to test its parents strings (strings that contain this sub-string). Also, if for example, in the first 10 letters there are 3 consecutive A's there is no need to test parent strings.\n",
        "\n",
        "A key insight I had was that we can divide all possible strings into 6 categories, based on the number of L's and the consecutive A's. If we do that we don't even have to worry about the individual strings, as all strings in the category have same properties for the purpose of this problem! Fricking awesome!!\n",
        "\n",
        "The 6 categories are A0, A1, B0, B1, C0, C1. I have a for loop iterating 30 times, and in each loop we are updating the categories.\n",
        "\n",
        "Finally, A0[30] + A1[30] + B0[30] + B1[30] + C0[30] + C1[30] gives us all possible prize strings.\n",
        "\n",
        "Nice, easy and really fast!"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fJ7NDjy7WA2g"
      },
      "source": [
        "def prize_strings(N):\n",
        "  A0 = [0]*(N+1) # Last letter not A & 0 L\n",
        "  A1 = [0]*(N+1) # Last letter not A & 1 L\n",
        "  B0 = [0]*(N+1) # Only last letter is A & 0 L\n",
        "  B1 = [0]*(N+1) # Only last letter is A & 1 L\n",
        "  C0 = [0]*(N+1) # Last 2 letters are A & 0 L\n",
        "  C1 = [0]*(N+1) # Last 2 letters are A & 1 L\n",
        "\n",
        "  A1[1] = 1  # \"L\"\n",
        "  A0[1] = 1  # \"O\"\n",
        "  B0[1] = 1  # \"A\"\n",
        "  \n",
        "  attendance = ['L', 'O', 'A']\n",
        "\n",
        "  for i in range(2, N+1):\n",
        "    for x in attendance:\n",
        "      if x == 'L':\n",
        "        A1[i] += A0[i-1] + B0[i-1] + C0[i-1]\n",
        "      if x == 'A':\n",
        "        B0[i] += A0[i-1]\n",
        "        B1[i] += A1[i-1]\n",
        "        C0[i] += B0[i-1]\n",
        "        C1[i] += B1[i-1]\n",
        "      if x == 'O':\n",
        "        A0[i] += A0[i-1] + B0[i-1] + C0[i-1] \n",
        "        A1[i] += A1[i-1] + B1[i-1] + C1[i-1]\n",
        "\n",
        "  return A0[N] + A1[N] + B0[N] + B1[N] + C0[N] + C1[N]"
      ],
      "execution_count": 20,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wXgmTcBCZtk5",
        "outputId": "a39fcf7b-dbbf-4eca-fe49-f71fa390c0d4",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "source": [
        "%%time\n",
        "prize_strings(30)"
      ],
      "execution_count": 23,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "CPU times: user 48 µs, sys: 0 ns, total: 48 µs\n",
            "Wall time: 51.5 µs\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "1918080160"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 23
        }
      ]
    }
  ]
}