Practical_Recursion_Tutorial_By_Examples.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Practical Recursion Tutorial By Examples.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "authorship_tag": "ABX9TyODl2TqyhFJOTLp98Wyqkmv",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/idhamari/recursion-practical-tutorial/blob/main/Practical_Recursion_Tutorial_By_Examples.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Introduction \n",
        "\n",
        "Recursion is one of the difficult topics for beginners in programming yet it is a very powerful tools that solves many challenging problems in a simple way.\n",
        "\n",
        "I will try to provides simple examples that can be traced easily. I will also refer to nice animations available in youtube as well. \n",
        "\n",
        "The goal is to add many examples to cover different situations. The python code will be simple and well commented so one can transfer it to other languages easily. \n",
        "\n",
        "If you have any comments, questions,or feedback, pleas feel free to add to the discussion page. \n",
        "\n",
        "\n",
        "**How to use:**\n",
        "\n",
        "- Create a google account if you don't have \n",
        "  - You can also download the python code or the notebook and run it locally if you have python or jupeter notebook installed. For this, select Data menu then Downloads.\n",
        "- Open the notebook in google colab\n",
        "- Select  Data menu then save a copy in drive. Then siwtch to the new saved notebook.\n",
        "- Select Run-time menu then Run all\n",
        "- Modify the code to learn more about it and do the tracing (this is important to understand how it works)\n",
        "- Add your feedback to the [discussion](https://github.com/idhamari/recursion-practical-tutorial/discussions/categories/q-a) section in github.\n",
        "- If you have time, contribute by adding more examples or notebooks\n",
        "- I appreciate [forking](https://docs.github.com/en/get-started/quickstart/fork-a-repo) and [starring](https://docs.github.com/en/get-started/exploring-projects-on-github/saving-repositories-with-stars) :)\n",
        "\n",
        "**Impoernat Note:**\n",
        "\n",
        "This is till uncomplete work, I will try to add more stuff when I have more free time!"
      ],
      "metadata": {
        "id": "jmGq5Rmw4Rl9"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Prepare required tools"
      ],
      "metadata": {
        "id": "LLsRLoTN_-yr"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import json"
      ],
      "metadata": {
        "id": "Mk0y7MHU_--F"
      },
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Simple example: \n",
        "\n",
        "Let's start by a simple hellow world problem:print out numbers from n1 to n2 e.g. from 1 to 5\n",
        "\n",
        "I will show how to solve this problem using simple loops and using recursion (I am assuming you know basics of for and while loops) "
      ],
      "metadata": {
        "id": "hH9XXvMD4oMs"
      }
    },
    {
      "cell_type": "code",
      "source": [
        " n1 = 1\n",
        " n2 = 5\n",
        " print(\" ------------ for loop ----------\")\n",
        " for i in range(n1, n2 + 1):\n",
        "     print(i)\n",
        "\n",
        " print(\" ------------ while loop ----------\")\n",
        " i = n1\n",
        " while (i< n2 + 1):\n",
        "     print(i)\n",
        "     i+=1 \n",
        " \n",
        " print(\" ------------ recursion loop ----------\")\n",
        " def myRecursion (n1, n2):\n",
        "     if n1 > n2 :\n",
        "        return\n",
        "     else:\n",
        "       print(n1)\n",
        "       myRecursion (n1 + 1 , n2)   \n",
        "\n",
        "# call the function with initial values\n",
        "myRecursion(n1, n2)\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "DD47kkrw5Blt",
        "outputId": "25e22450-be64-4879-bb69-34baba9b1699"
      },
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            " ------------ for loop ----------\n",
            "1\n",
            "2\n",
            "3\n",
            "4\n",
            "5\n",
            " ------------ while loop ----------\n",
            "1\n",
            "2\n",
            "3\n",
            "4\n",
            "5\n",
            " ------------ recursion loop ----------\n",
            "1\n",
            "2\n",
            "3\n",
            "4\n",
            "5\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "\n",
        "\n",
        "Another example: Modify the about code to print numbers from n2 to n1\n"
      ],
      "metadata": {
        "id": "Kqlql1Am4TOf"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "oNJomVoM4JaB",
        "outputId": "636389fe-e2b1-4005-dccf-89f6e683df80"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            " ------------ for loop ----------\n",
            "5\n",
            "4\n",
            "3\n",
            "2\n",
            "1\n",
            " ------------ while loop ----------\n",
            "5\n",
            "4\n",
            "3\n",
            "2\n",
            "1\n",
            " ------------ recursion loop ----------\n",
            "5\n",
            "4\n",
            "3\n",
            "2\n",
            "1\n"
          ]
        }
      ],
      "source": [
        "n1 = 1\n",
        "n2 = 5\n",
        "print(\" ------------ for loop ----------\")\n",
        "for i in range(n1, n2 +1):\n",
        "     print(n2 + 1  - i)\n",
        "\n",
        "print(\" ------------ while loop ----------\")\n",
        "i = n1\n",
        "while (i< n2 + 1):\n",
        "     print(n2 + 1  - i)\n",
        "     i+=1 \n",
        "\n",
        "print(\" ------------ recursion loop ----------\")\n",
        "def myRecursion (n1, n2):\n",
        "     if n1 > n2 :\n",
        "        return\n",
        "     else:\n",
        "       myRecursion (n1 + 1 , n2)   \n",
        "       print(n1)\n",
        "\n",
        "# call the function with initial values\n",
        "myRecursion(n1, n2)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Recursive Function Concept: \n",
        "\n",
        "In general, recursion function should look like this (there are more complex scenarios but this is the simple one): \n",
        "\n",
        "    function (recursion parameters):\n",
        "    \n",
        "        if (stopping condition)\n",
        "           do somthing one time\n",
        "           return\n",
        "        else: \n",
        "          do somthing1 // before recrsion   \n",
        "          recursion call \n",
        "          do something2 // after recursion \n",
        "\n",
        "Note that: \n",
        "\n",
        "* The recursion call must have parameters that reach the stopping condition or we get an infinit loop\n",
        "* do somthing1 will keeps repeating until we reach the stopping condition, after that do somthing2 will keep repeating the same number of times \n",
        "* The concept is the same in other programming languages\n",
        " \n",
        " Here is an example to show what happens if we print before and after the recursion: "
      ],
      "metadata": {
        "id": "JUR-klIE8ofb"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "print(\" ------------ recursion loop ----------\")\n",
        "def myRecursion (n1, n2):\n",
        "     if n1 > n2 :\n",
        "        print(\"xxx complete xxx\") \n",
        "        return\n",
        "     else:\n",
        "       print(\"before: \" , n1)\n",
        "       myRecursion (n1 + 1 , n2)   \n",
        "       print(\"after : \" , n1)\n",
        "\n",
        "# call the function with initial values\n",
        "myRecursion(n1, n2)\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Ex1q9F8V-YRr",
        "outputId": "53f8bc23-4b9e-4867-85af-c35d02797d18"
      },
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            " ------------ recursion loop ----------\n",
            "before:  1\n",
            "before:  2\n",
            "before:  3\n",
            "before:  4\n",
            "before:  5\n",
            "xxx complete xxx\n",
            "after :  5\n",
            "after :  4\n",
            "after :  3\n",
            "after :  2\n",
            "after :  1\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# How recursion works: \n",
        "\n",
        "The idea is to push and pop values to a memory stack. here is a nice video that explain the idea: \n",
        "\n",
        "Here is an example to convert the above recursion function to a simple loop with a stack:"
      ],
      "metadata": {
        "id": "GbFXguRGAGDk"
      }
    },
    {
      "cell_type": "code",
      "source": [
        " print(\" ------------ recursion loop ----------\")\n",
        "def myRecursion (n1, n2):\n",
        "     if n1 > n2 :\n",
        "        print(\"xxx complete xxx\") \n",
        "        return\n",
        "     else:\n",
        "       print(\"before: \" , n1)\n",
        "       myRecursion (n1 + 1 , n2)   \n",
        "       print(\"after : \" , n1)\n",
        "\n",
        "# call the function with initial values\n",
        "myRecursion(n1, n2)\n",
        "\n",
        "print(\" ------------ using stack  ----------\")\n",
        "\n",
        "def myRecursion (n1, n2):\n",
        "     # create stack with initial parameters \n",
        "     myStack =[[n1,n2]]\n",
        "\n",
        "     # myStack[-1][0] the last element in stack -1, the first element which stores n1 updated value\n",
        "     while (len(myStack) > 0):\n",
        "          if (myStack[-1][0] > n2  ):\n",
        "              if (len(myStack) == myStack[-1][0]):            \n",
        "                 print(\"xxx complete xxx\")\n",
        "              myStack.pop(len(myStack)-1) \n",
        "              if  (len(myStack) > 0):\n",
        "                  print(\"after : \" , myStack[-1][0])   \n",
        "          else: #  (n1 < n2) \n",
        "              print(\"before: \" , myStack[-1][0])\n",
        "              myStack.append( [  myStack[-1][0] + 1 , n2 ] ) \n",
        "\n",
        "            \n",
        "\n",
        "# call the function with initial values\n",
        "# myRecursion(n1, n2)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "TeIyLNzAAdcW",
        "outputId": "9b936199-7a49-41d6-b182-4983133a5c71"
      },
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            " ------------ recursion loop ----------\n",
            "before:  1\n",
            "before:  2\n",
            "before:  3\n",
            "before:  4\n",
            "before:  5\n",
            "xxx complete xxx\n",
            "after :  5\n",
            "after :  4\n",
            "after :  3\n",
            "after :  2\n",
            "after :  1\n",
            " ------------ using stack  ----------\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Fibonacci numbers problem\n",
        "\n",
        "The [Fibonacci](https://en.wikipedia.org/wiki/Fibonacci_number) numbers sequence can be generated by starting with 1,1, then add the previous two numbers to get the next number e.g. the first 7 numbers are: \n",
        "\n",
        "     Fib(7): 1, 1, 2, 3, 5, 8, 13 \n",
        "     2  = 1 + 1 \n",
        "     3  = 1 + 2 \n",
        "     5  = 2 + 3 \n",
        "     8  = 3 + 5 \n",
        "     13 = 5 + 8  \n",
        "\n",
        "Here is a [video animation](https://www.youtube.com/watch?v=BNeOE1qMyRA) to show how it works.\n",
        "\n",
        "Let's write a function that generate these numbers up to n "
      ],
      "metadata": {
        "id": "6QMJh2EKKxut"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "n = 8\n",
        "\n",
        "print(\" ------------ while loop ----------\")\n",
        "fib = [1,1]\n",
        "i= 0 \n",
        "while (i< n - 2):\n",
        "       fib.append( fib[-2] + fib[-1] )\n",
        "       i+=1 \n",
        "print(fib)\n",
        "\n",
        "print(\" ------------ recursion loop ----------\")\n",
        "fib=[]\n",
        "\n",
        "# find the current number e.g. myFib(6) is 8\n",
        "# TODO: try to print inside \n",
        "def myFib (x):\n",
        "\n",
        "    # find current number\n",
        "    def getFib(n):\n",
        "        # stopping condition\n",
        "        if ( (n==1) or (n==2) ):\n",
        "          n = 1 \n",
        "        else:\n",
        "          n = getFib (n-1) + getFib(n-2)\n",
        "        return n    \n",
        "\n",
        "    # to find all numbers\n",
        "    if x< 1:\n",
        "       return  \n",
        "    else:      \n",
        "      myFib(x-1)\n",
        "      fib.append(getFib(x))\n",
        "\n",
        "myFib(n)\n",
        "print(fib)\n",
        " "
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "GH5Nw-dmMSW_",
        "outputId": "ebb6de3d-7884-4db0-82b8-b3487be22e6c"
      },
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            " ------------ while loop ----------\n",
            "[1, 1, 2, 3, 5, 8, 13, 21]\n",
            " ------------ recursion loop ----------\n",
            "[1, 1, 2, 3, 5, 8, 13, 21]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Solving some interested problems using Backtracking\n",
        "\n",
        "[Backtracing](https://en.wikipedia.org/wiki/Backtracking) is a powerful tool to solve challenging problems.\n",
        "\n",
        "Here are some examples:"
      ],
      "metadata": {
        "id": "6r34hiZ_ALto"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Hanoi tower problem:\n",
        "\n",
        "Nice visualisation of the problem can be found [here](https://www.youtube.com/watch?v=rf6uf3jNjbo). A complete tutorial is provided [here](https://www.tutorialspoint.com/data_structures_algorithms/tower_of_hanoi.htm).\n",
        "\n",
        "The problem is to move all discs from the left to the right with three conditions: one disc at a time, move only a disc on top,  and not putting larger disc on top of a smaller one. \n",
        "\n",
        "![](https://www.tutorialspoint.com/data_structures_algorithms/images/tower_of_hanoi.jpg)\n",
        "\n",
        "Here is a soution example for 3 discs:\n",
        "\n",
        "![](https://www.tutorialspoint.com/data_structures_algorithms/images/tower_of_hanoi.gif)\n"
      ],
      "metadata": {
        "id": "mgFgtrL8Sddr"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Recursion"
      ],
      "metadata": {
        "id": "nC_Qzvdmzq4u"
      }
    },
    {
      "cell_type": "code",
      "source": [
        " # Hanoi tower problem:\n",
        "\n",
        "idx = 0\n",
        "def hanoi( n, src, dst, aux):\n",
        "     global idx\n",
        "     if n == 1: \n",
        "        idx=idx+1\n",
        "        print(idx, \" move disc \", n, \" from \", src , \" to \", dst )\n",
        "     else:\n",
        "       hanoi( n - 1 ,src, aux, dst)\n",
        "       idx = idx + 1\n",
        "       print(idx, \" move disc \", n, \" from \", src , \" to \", dst )\n",
        "       hanoi( n - 1, aux, dst, src)\n",
        "\n",
        "number_of_discs = 3\n",
        "hanoi(number_of_discs,\"left\",\"right\",\"middle\")       "
      ],
      "metadata": {
        "id": "iRNn1EijSjOx",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "1c7db9c3-a8c5-459f-a3c7-f37221a89875"
      },
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1  move disc  1  from  left  to  right\n",
            "2  move disc  2  from  left  to  middle\n",
            "3  move disc  1  from  right  to  middle\n",
            "4  move disc  3  from  left  to  right\n",
            "5  move disc  1  from  middle  to  left\n",
            "6  move disc  2  from  middle  to  right\n",
            "7  move disc  1  from  left  to  right\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Without recursion\n",
        "[source](https://stackoverflow.com/questions/70531371/how-solve-iterative-method-for-hanoi-problem)\n",
        "\n",
        "[Another solution in multiple programming languages](https://www.geeksforgeeks.org/iterative-tower-of-hanoi/)"
      ],
      "metadata": {
        "id": "jprsKiEzzwOj"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def hanoi(n, left, right, middle):\n",
        "    idx = 0\n",
        "    # Create a converter for a pile index (0, 1 or 2) to the identifiers \n",
        "    #    that are given as arguments:\n",
        "    map = [\"left\", \"right\",\"middle\"];\n",
        "    # Perform as many iterations as there are moves to perform:\n",
        "    for i in range (1,  1<<n):\n",
        "        # Use bit pattern of i to determine the source peg.\n",
        "        # First remove and count the trailing 0 bits in i:\n",
        "        j = i;\n",
        "        zeroCount = 0;\n",
        "        while (j % 2 == 0):\n",
        "            j >>= 1;\n",
        "            zeroCount += 1;\n",
        "        \n",
        "        # Derive the source pile from that zero-stripped number\n",
        "        source = (j >> 1) % 3;\n",
        "        # Get next pile as destination\n",
        "        target = (source + 1) % 3;\n",
        "        # Depending on parity, the source/target pile should be mirrored\n",
        "        if ((n + zeroCount) % 2 == 0):\n",
        "            source = (3 - source) % 3;\n",
        "            target = (3 - target) % 3;\n",
        "        \n",
        "        #printf(\"Move from %d to %d\\n\", map[source], map[target]);\n",
        "        idx = idx + 1\n",
        "        print(idx, \" move from \", map[source],\" to \",  map[target]);\n",
        "\n",
        "number_of_discs = 3\n",
        "hanoi(number_of_discs, 1, 2, 3);\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "2W8srPxx2bN6",
        "outputId": "cabf3587-63da-4d29-a1d8-3274e26a3075"
      },
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1  move from  left  to  right\n",
            "2  move from  left  to  middle\n",
            "3  move from  right  to  middle\n",
            "4  move from  left  to  right\n",
            "5  move from  middle  to  left\n",
            "6  move from  middle  to  right\n",
            "7  move from  left  to  right\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Set permutation\n",
        "\n",
        "[source](https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/)\n",
        "\n",
        "Print all permutations  of a given set e.g.:\n",
        "\n",
        "Input: A,B,C\n",
        "\n",
        "Output:\n",
        "  \n",
        "  - A,B,C\n",
        "  - A,C,B\n",
        "  - B,A,C\n",
        "  - B,C,A\n",
        "  - C,A,B\n",
        "  - C,B,A\n",
        "\n",
        " Note that the number of permutation is the factorial of the number of elements, in our example factorial(3) = 6\n",
        "\n",
        "Here is how the algorithm works:\n",
        "\n",
        "![](https://media.geeksforgeeks.org/wp-content/cdn-uploads/NewPermutation.gif)"
      ],
      "metadata": {
        "id": "J7wXzy_Ir4Cz"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Python program to print all permutations with \n",
        "# duplicates allowed \n",
        "# This code is contributed by Bhavya Jain \n",
        " \n",
        "# Function to print permutations of string \n",
        "# This function takes three parameters: \n",
        "# 1. String \n",
        "# 2. Starting index of the string \n",
        "# 3. Ending index of the string. \n",
        "def permute(a, l, r): \n",
        "    if l==r: \n",
        "        print (''.join(a))\n",
        "    else: \n",
        "        for i in range(l,r): \n",
        "            a[l], a[i] = a[i], a[l] \n",
        "            permute(a, l+1, r)      # recursion\n",
        "            a[l], a[i] = a[i], a[l] # backtrack \n",
        "  \n",
        "# Driver program to test the above function \n",
        "string = \"ABC\"\n",
        "n = len(string) \n",
        "a = list(string) \n",
        "permute(a, 0, n) "
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "DaqacvrGr4NQ",
        "outputId": "f84c1d4f-b023-4f2f-b7a6-31fe76702e8a"
      },
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "ABC\n",
            "ACB\n",
            "BAC\n",
            "BCA\n",
            "CBA\n",
            "CAB\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Set combination \n",
        "\n",
        "[source](https://www.geeksforgeeks.org/backtracking-to-find-all-subsets/)\n",
        "\n",
        "All subsets of a set (including the empty set). The number of outputs are $2^n$\n",
        "e.g. if 3 we get 8\n",
        "\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "R3Ff-yXdr4W0"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# This code is contributed by SHUBHAMSINGH8410\n",
        "# Python3 program to find all subsets\n",
        "# by backtracking.\n",
        "\n",
        "# In the array A at every step we have two\n",
        "# choices for each element either we can\n",
        "# ignore the element or we can include the\n",
        "# element in our subset\n",
        "def findSubsets(A, subset, index, subsetLength=None):\n",
        "    global idx \n",
        "    if  subsetLength is None:\n",
        "        idx += 1\n",
        "        print(idx,\" : \",  subset)\n",
        "    elif len(subset) == subsetLength:\n",
        "         idx += 1\n",
        "         print(idx,\" : \",  subset)\n",
        " \n",
        "    for i in range(index, len(A)):\n",
        "        \n",
        "        # include the A[i] in subset.\n",
        "        subset.append(A[i])\n",
        "        \n",
        "        # move onto the next element.\n",
        "        findSubsets(A, subset, i + 1, subsetLength)\n",
        "        \n",
        "        # exclude the A[i] from subset and\n",
        "        # triggers backtracking.\n",
        "        subset.pop(-1)\n",
        "\n",
        "# find the subsets of below vector.\n",
        "mySet = \"ABC\"\n",
        "mySet = list(mySet)\n",
        "\n",
        "# res will store all subsets.\n",
        "# O(2 ^ (number of elements inside array))\n",
        "# because at every step we have two choices\n",
        "# either include or ignore.\n",
        "idx = 0\n",
        "findSubsets(mySet, [] , 0)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "CjY2DxJZr4gL",
        "outputId": "f5a8cb4a-0167-4ec8-e865-73abc1fda3ec"
      },
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1  :  []\n",
            "2  :  ['A']\n",
            "3  :  ['A', 'B']\n",
            "4  :  ['A', 'B', 'C']\n",
            "5  :  ['A', 'C']\n",
            "6  :  ['B']\n",
            "7  :  ['B', 'C']\n",
            "8  :  ['C']\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# Find all subsets of specific length\n",
        "mySet = \"ABC\"\n",
        "mySet = list(mySet)\n",
        "idx = 0\n",
        "subsetLength = 2\n",
        "findSubsets(mySet, [] , 0, subsetLength)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "d1E1vkMBw4Gd",
        "outputId": "884594fa-f7d3-44b3-ab39-3b1f27b02692"
      },
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1  :  ['A', 'B']\n",
            "2  :  ['A', 'C']\n",
            "3  :  ['B', 'C']\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Graph Traverse:  [Breadth First Search (BFS)](https://en.wikipedia.org/wiki/Breadth-first_search)\n",
        "\n"
      ],
      "metadata": {
        "id": "8KcC3VTOTkXQ"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Breadth First Search (BFS)"
      ],
      "metadata": {
        "id": "VkZ9WB46Snyc"
      },
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Graph Traverse: [Depth First Search (DFS)](https://en.wikipedia.org/wiki/Depth-first_search)"
      ],
      "metadata": {
        "id": "FsDJe5nSSu31"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Depth First Search (DFS)"
      ],
      "metadata": {
        "id": "z60_H5C9SvAB"
      },
      "execution_count": 13,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## N-queen problem\n",
        "\n",
        "Refs: \n",
        "- https://www.youtube.com/watch?v=jPcBU0Z2Hj8\n",
        "- https://www.geeksforgeeks.org/n-queen-problem-backtracking-3/\n",
        "- https://tutorialspoint.dev/algorithm/backtracking-algorithms/printing-solutions-n-queen-problem\n",
        "\n",
        "The [N-queens]() problem is a chess problem asks to put 8 queens in an empty chess board without any queen attacking another queen. It can be solved for also non standard boards e.g. 4x4 board. Here is a solution for a standard 8x8 board:\n",
        "\n",
        "![](https://rosettacode.org/mw/images/b/bd/N_queens_problem.png)"
      ],
      "metadata": {
        "id": "nFXpkzvJTpk3"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# This code has been contributed \n",
        "# by 29AjayKumar \n",
        "  \n",
        "# This function solves the N Queen problem using  \n",
        "# Backtracking. It mainly uses solveNQUtil() to  \n",
        "# solve the problem. It returns false if queens  \n",
        "# cannot be placed, otherwise return true and  \n",
        "# prints placement of queens in the form of 1s.  \n",
        "# Please note that there may be more than one  \n",
        "# solutions, this function prints one of the  \n",
        "# feasible solutions.\n",
        "\n",
        "def solveNQ(board, col): \n",
        "    global idx \n",
        "    n = len(board)\n",
        "\n",
        "    # base case: If all queens are placedon the board, return true \n",
        "    if (col == n):\n",
        "        idx += 1  \n",
        "        print(\" -------------( sol: \" + str(idx) + \"   )--------------\")\n",
        "        for  i in range(n): \n",
        "            print(board[i]);  \n",
        "        return 1;  \n",
        "  \n",
        "    # Consider this column and try placing  \n",
        "    #this queen in all rows one by one\n",
        "    res = 0;  \n",
        "    for  row in range (n):  \n",
        "        # Check if queen can be placed on board[i][col]  \n",
        "        queenIsSafe = 1\n",
        "        # Check this row on left side\n",
        "        for j in range(col):\n",
        "            if board[row][j] == 1:\n",
        "                queenIsSafe = 0\n",
        "                break  \n",
        "                \n",
        "        # Check upper diagonal on left side\n",
        "        for i, j in zip(range(row, -1, -1), \n",
        "                        range(col, -1, -1)):\n",
        "            if board[i][j] == 1:\n",
        "                queenIsSafe = 0\n",
        "                break\n",
        "    \n",
        "        # Check lower diagonal on left side\n",
        "        for i, j in zip(range(row, n, 1), \n",
        "                        range(col, -1, -1)):\n",
        "            if board[i][j] == 1:\n",
        "               queenIsSafe = 0\n",
        "               break    \n",
        "\n",
        "        if queenIsSafe  :           \n",
        "            # Place this queen in board[i][col]  \n",
        "            board[row][col] = 1;  \n",
        "  \n",
        "            # Make result true if any placement is possible  \n",
        "            res = solveNQ(board, col + 1) or  res;  \n",
        "  \n",
        "            # If placing queen in board[i][col]  \n",
        "            #doesn't lead to a solution, then  \n",
        "            #remove queen from board[i][col] \n",
        "            board[row][col] = 0; # BACKTRACK  \n",
        "         \n",
        "    # If queen can not be place in any row in this column col then return false \n",
        "    return res;  \n",
        "\n",
        "\n",
        "\n",
        "# Note: for 4, there is only 2 solutions\n",
        "# Note: for 8, there is 92 solutions (with rotation and mirroring)\n",
        "idx = 0 # solution counter\n",
        "numberOfQueens = 8 \n",
        "board = [ [ 0 for col in range(numberOfQueens)] for row in range(numberOfQueens)]  \n",
        "\n",
        "solveNQ(board, 0); \n"
      ],
      "metadata": {
        "id": "kCbiN2pgTs80",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "05a289a5-3884-42c0-eeae-c391153db2ec"
      },
      "execution_count": 14,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            " -------------( sol: 1   )--------------\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 2   )--------------\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 3   )--------------\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            " -------------( sol: 4   )--------------\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            " -------------( sol: 5   )--------------\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            " -------------( sol: 6   )--------------\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            " -------------( sol: 7   )--------------\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            " -------------( sol: 8   )--------------\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            " -------------( sol: 9   )--------------\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 10   )--------------\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            " -------------( sol: 11   )--------------\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            " -------------( sol: 12   )--------------\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 13   )--------------\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            " -------------( sol: 14   )--------------\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            " -------------( sol: 15   )--------------\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            " -------------( sol: 16   )--------------\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            " -------------( sol: 17   )--------------\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 18   )--------------\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            " -------------( sol: 19   )--------------\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            " -------------( sol: 20   )--------------\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            " -------------( sol: 21   )--------------\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            " -------------( sol: 22   )--------------\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            " -------------( sol: 23   )--------------\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 24   )--------------\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 25   )--------------\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 26   )--------------\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            " -------------( sol: 27   )--------------\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            " -------------( sol: 28   )--------------\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 29   )--------------\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            " -------------( sol: 30   )--------------\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            " -------------( sol: 31   )--------------\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            " -------------( sol: 32   )--------------\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            " -------------( sol: 33   )--------------\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            " -------------( sol: 34   )--------------\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            " -------------( sol: 35   )--------------\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 36   )--------------\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 37   )--------------\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            " -------------( sol: 38   )--------------\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 39   )--------------\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 40   )--------------\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            " -------------( sol: 41   )--------------\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            " -------------( sol: 42   )--------------\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            " -------------( sol: 43   )--------------\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            " -------------( sol: 44   )--------------\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 45   )--------------\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 46   )--------------\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 47   )--------------\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            " -------------( sol: 48   )--------------\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 49   )--------------\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 50   )--------------\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            " -------------( sol: 51   )--------------\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            " -------------( sol: 52   )--------------\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            " -------------( sol: 53   )--------------\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 54   )--------------\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            " -------------( sol: 55   )--------------\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            " -------------( sol: 56   )--------------\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 57   )--------------\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            " -------------( sol: 58   )--------------\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            " -------------( sol: 59   )--------------\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            " -------------( sol: 60   )--------------\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            " -------------( sol: 61   )--------------\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            " -------------( sol: 62   )--------------\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            " -------------( sol: 63   )--------------\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 64   )--------------\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 65   )--------------\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            " -------------( sol: 66   )--------------\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            " -------------( sol: 67   )--------------\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            " -------------( sol: 68   )--------------\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            " -------------( sol: 69   )--------------\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            " -------------( sol: 70   )--------------\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            " -------------( sol: 71   )--------------\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            " -------------( sol: 72   )--------------\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            " -------------( sol: 73   )--------------\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            " -------------( sol: 74   )--------------\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            " -------------( sol: 75   )--------------\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            " -------------( sol: 76   )--------------\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            " -------------( sol: 77   )--------------\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            " -------------( sol: 78   )--------------\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            " -------------( sol: 79   )--------------\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            " -------------( sol: 80   )--------------\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 81   )--------------\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            " -------------( sol: 82   )--------------\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            " -------------( sol: 83   )--------------\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            " -------------( sol: 84   )--------------\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            " -------------( sol: 85   )--------------\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 86   )--------------\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            " -------------( sol: 87   )--------------\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            " -------------( sol: 88   )--------------\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            " -------------( sol: 89   )--------------\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 90   )--------------\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 91   )--------------\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n",
            " -------------( sol: 92   )--------------\n",
            "[0, 0, 1, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 1, 0, 0]\n",
            "[0, 0, 0, 1, 0, 0, 0, 0]\n",
            "[0, 1, 0, 0, 0, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 0, 1]\n",
            "[0, 0, 0, 0, 1, 0, 0, 0]\n",
            "[0, 0, 0, 0, 0, 0, 1, 0]\n",
            "[1, 0, 0, 0, 0, 0, 0, 0]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Knight tour problem\n",
        "\n",
        "ref: https://www.youtube.com/watch?v=ab_dY3dZFHM"
      ],
      "metadata": {
        "id": "gBNfWbvTW5T_"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "## Knight tour problem"
      ],
      "metadata": {
        "id": "I4XdmjQAW5eg"
      },
      "execution_count": 15,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## [Lattice](https://en.wikipedia.org/wiki/Lattice_(order))\n",
        "\n",
        "Here is a nice [lattice library](https://github.com/prasser/*jhpl*) in java that generates lattice"
      ],
      "metadata": {
        "id": "ZrpQzwhMWAfd"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Lattice"
      ],
      "metadata": {
        "id": "DB_90VgfWA0E"
      },
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Flatten Nested Data e.g. JSON\n",
        "Somtimes we need to convert a heirarichal structure e.g. JSON to a table and vice versa. Here is how we can solve this problem"
      ],
      "metadata": {
        "id": "JDlhsH3zT4pL"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Create sample data"
      ],
      "metadata": {
        "id": "dN_wRN-gzfUC"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Simple nested data sample"
      ],
      "metadata": {
        "id": "bLoiWVHY9FVv"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Create Sample data\n",
        "\n",
        "#example of simple nested data\n",
        "jsonData1 = \"\"\"\n",
        " {\n",
        "    \"USA\": {\n",
        "             \"NJ\"      : {\n",
        "                          \"Newark\"     : [\n",
        "                                          \"Jeremy\",\n",
        "                                          \"Stacey\"  \n",
        "                                         ]\n",
        "                         },\n",
        "             \"New York\": {\n",
        "                          \"Brooklyn\"   : \"David\",\n",
        "                          \"Mannhatten\" : \"Dan\"                       \n",
        "                         }\n",
        "           },\n",
        "    \"CAN\": {\n",
        "             \"MO\"      : \"Sarah\",\n",
        "             \"Toronto\" : {\n",
        "                          \"Yorkville\"  : \"Jessi\",\n",
        "                          \"Lib Vill\"   : \"Sam\"                            \n",
        "                         }\n",
        "           },\n",
        "    \"MEX\": {\n",
        "             \"Tulum\"      : \"Elsi\",\n",
        "             \"Berlin\"     : {\n",
        "                             \"AAA\"  : \"11\",\n",
        "                             \"BBB\"  : \"22\",\n",
        "                             \"CCC\"  : [\n",
        "                                          \"33\",\n",
        "                                          \"44\"  \n",
        "                                         ]                         \n",
        "                            }\n",
        "           }\n",
        "                        \n",
        "  }\n",
        "\"\"\"\n",
        "\n",
        "# Expected output: \n",
        "\n",
        "\"\"\"\n",
        "    USA > NJ > Newark > Jeremy\n",
        "    USA > NJ > Newark > Stacey\n",
        "    USA > New York > Brooklyn > David\n",
        "    USA > New York > Mannhatten > Dan\n",
        "    CAN > MO > Sarah\n",
        "    CAN > Toronto > Yorkville > Jessi\n",
        "    CAN > Toronto > Lib Vill > Sam\n",
        "    MEX > Tulum > Elsi\n",
        "    MEX > Berlin > AAA > 11\n",
        "    MEX > Berlin > BBB > 22\n",
        "    MEX > Berlin > CCC > 33\n",
        "    MEX > Berlin > CCC > 44\n",
        " \"\"\"\n",
        "# example of complicated nested data"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 71
        },
        "id": "R03p0btWzTlX",
        "outputId": "b14b92b4-fa00-4639-b3e0-1801f484526f"
      },
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'\\n    USA > NJ > Newark > Jeremy\\n    USA > NJ > Newark > Stacey\\n    USA > New York > Brooklyn > David\\n    USA > New York > Mannhatten > Dan\\n    CAN > MO > Sarah\\n    CAN > Toronto > Yorkville > Jessi\\n    CAN > Toronto > Lib Vill > Sam\\n    MEX > Tulum > Elsi\\n    MEX > Berlin > AAA > 11\\n    MEX > Berlin > BBB > 22\\n    MEX > Berlin > CCC > 33\\n    MEX > Berlin > CCC > 44\\n '"
            ],
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            }
          },
          "metadata": {},
          "execution_count": 17
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Complicated nested data sample "
      ],
      "metadata": {
        "id": "_vI9N5moy8E6"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "jsonData2 = \"\"\"\n",
        "[\n",
        "    {\n",
        "    \"Class\": \"ClassA\",\n",
        "             \"Persons\": [\n",
        "                           {\n",
        "                            \"ID\": \"11001\",\n",
        "                            \"Age\": \"26\",\n",
        "                            \"Gender\": \"M\",\n",
        "                            \"Info\": [\n",
        "                                        {\n",
        "                                            \"Label\": \"Physical\",\n",
        "                                            \"Info\": [\n",
        "                                                    {\n",
        "                                                    \"Label\": \"Appearance\",\n",
        "                                                    \"Information\": [\n",
        "                                                                    {\n",
        "                                                                    \"Label\": \"eye color\",\n",
        "                                                                    \"Value\": \"blue\"\n",
        "                                                                    },\n",
        "                                                                    {                                                                                        \n",
        "                                                                    \"Label\": \"height\",\n",
        "                                                                    \"unit\": \"cm\",\n",
        "                                                                    \"Value\": \"170\"\n",
        "                                                                    },                                                                                  \n",
        "                                                                    {                                                                                        \n",
        "                                                                    \"Label\": \"has glasses\",\n",
        "                                                                    \"Value\": \"false\"\n",
        "                                                                    },                                                                    \n",
        "                                                                    {                                                                                                                          \n",
        "                                                                    \"Label\": \"Weight\",\n",
        "                                                                    \"Information\": [\n",
        "                                                                                        {                                                                                     \n",
        "                                                                                        \"Date\": \"1.1.2022\",\n",
        "                                                                                        \"center\": \"center1\"\n",
        "                                                                                        },                                                                                  \n",
        "                                                                                        {                                                                                      \n",
        "                                                                                        \"unit\": \"kg\",\n",
        "                                                                                        \"Value\": \"80\"\n",
        "                                                                                        }\n",
        "                                                                                    ]\n",
        "                                                                    }\n",
        "                                                                    ]\n",
        "                                                        }\n",
        "                                                    ]\n",
        "                                        },\n",
        "                                        {\n",
        "                                        \"Label\": \"Others\",\n",
        "                                        \"Info\": [\n",
        "                                                    {\n",
        "                                                    \"Label\": \"Marks\",\n",
        "                                                    \"Information\": [\n",
        "                                                                    {\n",
        "                                                                    \"Label\": \"Swimming\",\n",
        "                                                                    \"Value\": \"10\"\n",
        "                                                                    },\n",
        "                                                                    {                                                                                        \n",
        "                                                                    \"Label\": \"Math\",\n",
        "                                                                    \"Value\": \"7\"\n",
        "                                                                    },                                                                                  \n",
        "                                                                    {                                                                                        \n",
        "                                                                    \"Label\": \"Language\",\n",
        "                                                                    \"Value\": \"5\"\n",
        "                                                                    }\n",
        "                                                                ]\n",
        "                                                        }\n",
        "                                                ]\n",
        "                                        }\n",
        "                                    ]    \n",
        "                        \n",
        "                    \n",
        "                            },\n",
        "                            {\n",
        "                             \"ID\": \"11002\",\n",
        "                             \"Age\": \"20\",\n",
        "                             \"Gender\": \"F\",\n",
        "                             \"Info\": [\n",
        "                                       {\n",
        "                                         \"Label\": \"Physical\",\n",
        "                                         \"Info\": [\n",
        "                                                    {\n",
        "                                                    \"Label\": \"Appearance\",\n",
        "                                                    \"Information\": [\n",
        "                                                                    {\n",
        "                                                                    \"Label\": \"eye color\",\n",
        "                                                                    \"Value\": \"brown\"\n",
        "                                                                    },\n",
        "                                                                    {                                                                                        \n",
        "                                                                    \"Label\": \"height\",\n",
        "                                                                    \"unit\": \"cm\",\n",
        "                                                                    \"Value\": \"160\"\n",
        "                                                                    },                                                                                  \n",
        "                                                                    {                                                                                        \n",
        "                                                                    \"Label\": \"has glasses\",\n",
        "                                                                    \"Value\": \"true\"\n",
        "                                                                    }                                                                  \n",
        "                                                                   ]\n",
        "                                                        }\n",
        "                                                 ]\n",
        "                                       },\n",
        "                                       {\n",
        "                                        \"Label\": \"Others\",\n",
        "                                        \"Info\": [\n",
        "                                                   {\n",
        "                                                   \"Label\": \"Marks\",\n",
        "                                                   \"Information\": [\n",
        "                                                                   {\n",
        "                                                                   \"Label\": \"Swimming\",\n",
        "                                                                   \"Value\": \"7\"\n",
        "                                                                   },\n",
        "                                                                   {                                                                                        \n",
        "                                                                   \"Label\": \"Math\",\n",
        "                                                                   \"Value\": \"10\"\n",
        "                                                                   },                                                                                  \n",
        "                                                                   {                                                                                        \n",
        "                                                                   \"Label\": \"Language\",\n",
        "                                                                   \"Value\": \"9\"\n",
        "                                                                   }\n",
        "                                                                ]\n",
        "                                                       }\n",
        "                                                ]\n",
        "                                      }\n",
        "                                     ]    \n",
        "                            }\n",
        "                        ]\n",
        "    },\n",
        "    {\n",
        "    \"Class\": \"ClassB\",\n",
        "             \"Persons\": [\n",
        "                    {\n",
        "                     \"ID\": \"11003\",\n",
        "                     \"Age\": \"40\",\n",
        "                     \"Gender\": \"F\",\n",
        "                     \"Info\": [\n",
        "                                 {\n",
        "                                     \"Label\": \"Physical\",\n",
        "                                     \"Info\": [\n",
        "                                             {\n",
        "                                             \"Label\": \"Appearance\",\n",
        "                                             \"Information\": [\n",
        "                                                             {\n",
        "                                                             \"Label\": \"eye color\",\n",
        "                                                             \"Value\": \"green\"\n",
        "                                                             },\n",
        "                                                             {                                                                                        \n",
        "                                                             \"Label\": \"height\",\n",
        "                                                             \"unit\": \"cm\",\n",
        "                                                             \"Value\": \"180\"\n",
        "                                                             },                                                                                  \n",
        "                                                             {                                                                                        \n",
        "                                                             \"Label\": \"has glasses\",\n",
        "                                                             \"Value\": \"false\"\n",
        "                                                             },                                                                    \n",
        "                                                             {                                                                                                                          \n",
        "                                                             \"Label\": \"Weight\",\n",
        "                                                             \"Information\": [\n",
        "                                                                                 {                                                                                     \n",
        "                                                                                 \"Date\": \"1.1.2020\",\n",
        "                                                                                 \"center\": \"center1\"\n",
        "                                                                                 },                                                                                  \n",
        "                                                                                 {                                                                                      \n",
        "                                                                                 \"unit\": \"kg\",\n",
        "                                                                                 \"Value\": \"60\"\n",
        "                                                                                 }\n",
        "                                                                             ]\n",
        "                                                             }\n",
        "                                                             ]\n",
        "                                                 }\n",
        "                                             ]\n",
        "                                 },\n",
        "                                 {\n",
        "                                 \"Label\": \"Others\",\n",
        "                                 \"Info\": [\n",
        "                                             {\n",
        "                                             \"Label\": \"Marks\",\n",
        "                                             \"Information\": [\n",
        "                                                             {\n",
        "                                                             \"Label\": \"Swimming\",\n",
        "                                                             \"Value\": \"5\"\n",
        "                                                             },\n",
        "                                                             {                                                                                        \n",
        "                                                             \"Label\": \"Math\",\n",
        "                                                             \"Value\": \"6\"\n",
        "                                                             },                                                                                  \n",
        "                                                             {                                                                                        \n",
        "                                                             \"Label\": \"Language\",\n",
        "                                                             \"Value\": \"10\"\n",
        "                                                             }\n",
        "                                                         ]\n",
        "                                                 }\n",
        "                                         ]\n",
        "                                 }\n",
        "                             ]    \n",
        "                 \n",
        "             \n",
        "                     }\n",
        "                    ]\n",
        "    }   \n",
        "]\n",
        "\"\"\"\n",
        "# Expected output, somthing like: \n",
        "\"\"\"\n",
        "  Class,     ID,     Age, Gender,          Labels,                      date,       location ,   value                                 \n",
        "  ClassA\", \"11001\", \"26\",  \"M\",\"  Physical > Appearance> eye color\",              ,          ,   \"blue\"\n",
        "  ClassA\", \"11001\", \"26\",  \"M\",  \"Physical > Appearance> height\",                 ,          ,   \"170\"\n",
        "  ClassA\", \"11001\", \"26\",  \"M\",  \"Physical > Appearance> has glasses\",            ,          ,   \"false\"\n",
        "  ClassA\", \"11001\", \"26\",  \"M\",  \"Physical > Appearance> Weight\",      \"1.1.2022\", \"center1\" ,   80\n",
        "\n",
        "\"\"\"\n",
        "print(\"data is generated!\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "2QZ7EDNzy8N_",
        "outputId": "7693a20a-bc08-48fb-f073-a803fe004c5b"
      },
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "data is generated!\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Flattening a simple nested data \n",
        "\n",
        "[Youtube source](https://www.youtube.com/watch?v=aUuleLd0lwM&list=PLxyxrvvxl20hNX15DBWbKxCkGFE4RkAcc&index=34)"
      ],
      "metadata": {
        "id": "UsVBnybCsrhs"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "\n",
        "# read json data: \n",
        "\n",
        "def flattenJson(obj):\n",
        "  ret =[]\n",
        "  def flattenX(x, fkey=\"\"):\n",
        "      if type (x) is dict:\n",
        "        for ckey in x:\n",
        "            flattenX(x[ckey], fkey + ckey + ' > ')\n",
        "      elif type (x) is list:        \n",
        "          #i = 0\n",
        "          for elem in x:\n",
        "              flattenX(elem, fkey )\n",
        "      else: \n",
        "          # string, int, ..etc \n",
        "          ret.append(fkey + x)   \n",
        " \n",
        "  flattenX(obj)    \n",
        "  return ret     \n",
        "  \n"
      ],
      "metadata": {
        "id": "GKdw7VsPsrvk"
      },
      "execution_count": 19,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "nestedData1 = json.loads(jsonData1)\n",
        "tbl = flattenJson(nestedData1)\n",
        "for x in tbl: \n",
        "    print(x)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "zvh206pQ5suK",
        "outputId": "a3ec90fd-6a4e-44cf-f4c8-ea64390e430b"
      },
      "execution_count": 20,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "USA > NJ > Newark > Jeremy\n",
            "USA > NJ > Newark > Stacey\n",
            "USA > New York > Brooklyn > David\n",
            "USA > New York > Mannhatten > Dan\n",
            "CAN > MO > Sarah\n",
            "CAN > Toronto > Yorkville > Jessi\n",
            "CAN > Toronto > Lib Vill > Sam\n",
            "MEX > Tulum > Elsi\n",
            "MEX > Berlin > AAA > 11\n",
            "MEX > Berlin > BBB > 22\n",
            "MEX > Berlin > CCC > 33\n",
            "MEX > Berlin > CCC > 44\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "nestedData2 = json.loads(jsonData2)\n",
        "tbl = flattenJson(nestedData2)\n",
        "for x in tbl: \n",
        "    print(x)\n",
        "\n",
        " # TODO: we need a better way to collect person information   "
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Lw9ib8Mv5tjZ",
        "outputId": "82f39dd1-ff93-40b1-a11d-79690ef2eb57"
      },
      "execution_count": 21,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Class > ClassA\n",
            "Persons > ID > 11001\n",
            "Persons > Age > 26\n",
            "Persons > Gender > M\n",
            "Persons > Info > Label > Physical\n",
            "Persons > Info > Info > Label > Appearance\n",
            "Persons > Info > Info > Information > Label > eye color\n",
            "Persons > Info > Info > Information > Value > blue\n",
            "Persons > Info > Info > Information > Label > height\n",
            "Persons > Info > Info > Information > unit > cm\n",
            "Persons > Info > Info > Information > Value > 170\n",
            "Persons > Info > Info > Information > Label > has glasses\n",
            "Persons > Info > Info > Information > Value > false\n",
            "Persons > Info > Info > Information > Label > Weight\n",
            "Persons > Info > Info > Information > Information > Date > 1.1.2022\n",
            "Persons > Info > Info > Information > Information > center > center1\n",
            "Persons > Info > Info > Information > Information > unit > kg\n",
            "Persons > Info > Info > Information > Information > Value > 80\n",
            "Persons > Info > Label > Others\n",
            "Persons > Info > Info > Label > Marks\n",
            "Persons > Info > Info > Information > Label > Swimming\n",
            "Persons > Info > Info > Information > Value > 10\n",
            "Persons > Info > Info > Information > Label > Math\n",
            "Persons > Info > Info > Information > Value > 7\n",
            "Persons > Info > Info > Information > Label > Language\n",
            "Persons > Info > Info > Information > Value > 5\n",
            "Persons > ID > 11002\n",
            "Persons > Age > 20\n",
            "Persons > Gender > F\n",
            "Persons > Info > Label > Physical\n",
            "Persons > Info > Info > Label > Appearance\n",
            "Persons > Info > Info > Information > Label > eye color\n",
            "Persons > Info > Info > Information > Value > brown\n",
            "Persons > Info > Info > Information > Label > height\n",
            "Persons > Info > Info > Information > unit > cm\n",
            "Persons > Info > Info > Information > Value > 160\n",
            "Persons > Info > Info > Information > Label > has glasses\n",
            "Persons > Info > Info > Information > Value > true\n",
            "Persons > Info > Label > Others\n",
            "Persons > Info > Info > Label > Marks\n",
            "Persons > Info > Info > Information > Label > Swimming\n",
            "Persons > Info > Info > Information > Value > 7\n",
            "Persons > Info > Info > Information > Label > Math\n",
            "Persons > Info > Info > Information > Value > 10\n",
            "Persons > Info > Info > Information > Label > Language\n",
            "Persons > Info > Info > Information > Value > 9\n",
            "Class > ClassB\n",
            "Persons > ID > 11003\n",
            "Persons > Age > 40\n",
            "Persons > Gender > F\n",
            "Persons > Info > Label > Physical\n",
            "Persons > Info > Info > Label > Appearance\n",
            "Persons > Info > Info > Information > Label > eye color\n",
            "Persons > Info > Info > Information > Value > green\n",
            "Persons > Info > Info > Information > Label > height\n",
            "Persons > Info > Info > Information > unit > cm\n",
            "Persons > Info > Info > Information > Value > 180\n",
            "Persons > Info > Info > Information > Label > has glasses\n",
            "Persons > Info > Info > Information > Value > false\n",
            "Persons > Info > Info > Information > Label > Weight\n",
            "Persons > Info > Info > Information > Information > Date > 1.1.2020\n",
            "Persons > Info > Info > Information > Information > center > center1\n",
            "Persons > Info > Info > Information > Information > unit > kg\n",
            "Persons > Info > Info > Information > Information > Value > 60\n",
            "Persons > Info > Label > Others\n",
            "Persons > Info > Info > Label > Marks\n",
            "Persons > Info > Info > Information > Label > Swimming\n",
            "Persons > Info > Info > Information > Value > 5\n",
            "Persons > Info > Info > Information > Label > Math\n",
            "Persons > Info > Info > Information > Value > 6\n",
            "Persons > Info > Info > Information > Label > Language\n",
            "Persons > Info > Info > Information > Value > 10\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Reverse flatting nested data\n",
        "\n",
        "How can w ego from flatten aobject to a nested data?"
      ],
      "metadata": {
        "id": "yuBaegcA8b1F"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Try to solve the problem"
      ],
      "metadata": {
        "id": "RHkaZswo8m1N"
      },
      "execution_count": 22,
      "outputs": []
    }
  ]
}