Unlock Android.ipynb

unlock-android.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Unlock Android.ipynb",
      "version": "0.3.2",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/gist/NTT123/b6fa438634c932494b3759bb22e2d4c2/unlock-android.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "metadata": {
        "id": "V6Yscj1NVL_V",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "<img src=\"https://docs.google.com/drawings/d/e/2PACX-1vR2SM_Nz9Yes6pBUjn3KnX1T77Hm0p2dd7eXBExhbZoye-u165KTb61pg9kTJi6VoI7HDRUWZWNZ4oL/pub?w=245&amp;h=200\">"
      ]
    },
    {
      "metadata": {
        "id": "9PZTrpYDVu71",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "# Cannot visit v from u, unless the middle node is visitted\n",
        "def middle_node(u, v):\n",
        "    dic = { (1, 3): 2, (4, 6): 5, (7, 9): 8, (1, 7): 4, (2, 8): 5, (3, 9): 6, (1,9): 5, (3, 7): 5}\n",
        "    \n",
        "    if u > v:\n",
        "        u,v = v, u\n",
        "\n",
        "    if u == 0:\n",
        "        return 0\n",
        "        \n",
        "    if (u, v) in dic:\n",
        "        return dic[(u, v)]\n",
        "    else:\n",
        "        return 0"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "MmQ354YeYDA-",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "def count():\n",
        "    total_count = [-1] # do not count 0\n",
        "    \n",
        "    visitted = [0 for _ in range(10)]\n",
        "    visitted[0] = 1\n",
        "    \n",
        "    def visit(u, visitted, total_count):\n",
        "       \n",
        "        visitted[u] = 1\n",
        "        \n",
        "        total_count[0] += 1\n",
        "        \n",
        "        for v in range(10):\n",
        "            if visitted[v] == 0:\n",
        "                if visitted[middle_node(u, v)] == 1:\n",
        "                    visit(v, visitted, total_count)\n",
        "        visitted[u] = 0\n",
        "        \n",
        "    visit(0, visitted, total_count)\n",
        "        \n",
        "    return total_count[0]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "qIdsqwDZZLGl",
        "colab_type": "code",
        "outputId": "eaf15768-e490-4bf3-e8fa-f9f129263c39",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "cell_type": "code",
      "source": [
        "count()"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "389497"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 30
        }
      ]
    }
  ]
}