Lily's_Homework.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Lily's Homework.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyNWpS7rsJrfuFnKTNXp9m+x",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/Syntax-code/Codes/blob/master/Lily's_Homework.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5l6kbb4bAj0R",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def homework(arr):\n",
        "    arr1 = arr.copy()\n",
        "    count1, count2, x = 0, 0, 0\n",
        "    a = sorted(arr)\n",
        "    b = sorted(arr, reverse = True)\n",
        "    while(arr != a):\n",
        "       i = arr.index(min(arr[x:]))\n",
        "       if i == x:\n",
        "         x += 1\n",
        "         continue\n",
        "       arr[x],arr[i] = arr[i], arr[x]\n",
        "       count1 += 1\n",
        "       x += 1\n",
        "       print(arr)\n",
        "    arr = arr1.copy()\n",
        "    print(\"reverse\")\n",
        "    print(arr)\n",
        "    x = 0\n",
        "    while(arr != b):\n",
        "       i = arr.index(max(arr[x:]))\n",
        "       if i == x:\n",
        "         x += 1\n",
        "         continue\n",
        "       arr[x],arr[i] = arr[i], arr[x]\n",
        "       count2 += 1\n",
        "       x += 1\n",
        "       print(arr)\n",
        "    return  print('count2: '+ str(count2)) if(count1>count2) else print('count1: '+ str(count1))"
      ],
      "execution_count": 40,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9O4ywED_BJ78",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 185
        },
        "outputId": "e3c3efb7-b370-4580-9e81-12082e09b259"
      },
      "source": [
        "arr = [3, 4, 2, 5, 1]\n",
        "print(homework(arr))"
      ],
      "execution_count": 41,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[1, 4, 2, 5, 3]\n",
            "[1, 2, 4, 5, 3]\n",
            "[1, 2, 3, 5, 4]\n",
            "[1, 2, 3, 4, 5]\n",
            "reverse\n",
            "[3, 4, 2, 5, 1]\n",
            "[5, 4, 2, 3, 1]\n",
            "[5, 4, 3, 2, 1]\n",
            "count2: 2\n",
            "None\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jhV0BDLuXPv4",
        "colab_type": "text"
      },
      "source": [
        "#Time complexity O(nlog(n))"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CO93-SzEShF3",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def homework(arr, sol):\n",
        "  dic = {}\n",
        "  count = 0\n",
        "  for index, val in enumerate(arr):\n",
        "    dic[val] = index\n",
        "  for x in range(len(arr)):\n",
        "    if arr[x] != sol[x]:\n",
        "      # dic[arr[x]], dic[sol[x]] = dic[sol[x]], dic[arr[x]]\n",
        "      # arr[x], arr[arr.index(sol[x])] = arr[arr.index(sol[x])], arr[x]\n",
        "      # count += 1\n",
        "      count +=1\n",
        "            \n",
        "      ind_to_swap = dic[ sol[x] ]\n",
        "      dic[ arr[x] ] = dic[ sol[x]]\n",
        "      arr[x],arr[ind_to_swap] = sol[x],arr[x]\n",
        "  return count "
      ],
      "execution_count": 56,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "JTdIdiYFSlDt",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "8107a158-eab6-4657-ef7e-1efd4c5eb859"
      },
      "source": [
        "# arr = [3, 4, 2, 5, 1]\n",
        "arr = [2,5,3,1]\n",
        "asc = homework(arr, sorted(arr))\n",
        "des = homework(arr, sorted(arr, reverse = True))\n",
        "print(min(asc, des))"
      ],
      "execution_count": 58,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "2\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}