Practice_12_KM_11_Peshkov_Anton.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FMqboNwO4rVs"
      },
      "source": [
        "# **Курс \"Програмування на мові Python\"**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "A2T6MigL5Z06"
      },
      "source": [
        "## **Практичне зайняття №12**\n",
        "\n",
        "### Тема: \"Рекурсивні структури даних\""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8bFJLl9Y4PYz"
      },
      "source": [
        "### **Завдання 1 (3 бали)**\n",
        "\n",
        "Нехай задано структуру даних, що представляє файли на диску, наступного вигляду:\n",
        "- файли представлені у вигляді рядків зі своїм іменем;\n",
        "- папки представлені у вигляді пари `(name, subnodes)`, де `name` — це ім'я папки, а `subnodes` — список з файлів і/або папок, що містяться у ній.\n",
        "\n",
        "Приклад такої структури наведено нижче у змінній `dirs`.\n",
        "\n",
        "Реалізуйте рекурсивну функцію `search(dirs, filename)` для пошуку усіх файлів із іменем `filename` у структурі `dirs`. Ця функція має повертати список, що містить повні шляхи до файлу у заданій структурі. Наприклад, `search(dirs, 'file2')` для наведеної нижче структури має повертати список `['/folder1/folder2/file2']`.\n",
        "\n",
        "_Зауваження 1_: Ви можете, за необхідності, додати до сигнатури функції додаткові параметри, за умови, що вони матимуть значення за замовчуванням. Однак, я стверджую, що таку функцію завжди можна реалізувати використовуючи лише задану кількість параметрів, незалежно від того, чи будете ви використовувати рекурсію з акумулятором чи без.\n",
        "\n",
        "_Зауваження 2_: Згадайте, що рекурсія буває не тільки безпосередньою, але й опосередкованою, коли послідовність функцій викликає одна одну: `f() -> g() -> ... -> f()`\n",
        "\n",
        "_Зауваження 3_: Пам'ятайте, що Ви завжди можете використовувати функції `map` та `reduce`. Крім того, ви можете захотіти використати інші функції з модулів `functools` та `itertools`, наприклад `itertools.chain()`. Завдання, однак, можна виконати і без них (хоч це і не дуже зручно).\n",
        "\n",
        "_Зауваження 4_: На мій смак, версія з акумулятором є більш елегантною, але дещо складнішою в реалізації. Спробуйте реалізувати обидві версії.\n",
        "\n",
        "![](https://media.giphy.com/media/enCWEo0vG25Ow/giphy.gif) "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {
        "id": "p4JxkFju4W0e"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "['/folder1/file1']\n",
            "['/folder1//folder2/file2']\n",
            "['/folder1//folder2/file3', '/folder1//folder3/file3', '/folder1//folder3//folder4/file3']\n",
            "['/folder1//folder3/file4']\n",
            "['/folder1/file5']\n",
            "[]\n",
            "[]\n",
            "All tests good!\n"
          ]
        }
      ],
      "source": [
        "from functools import reduce \n",
        "dirs = [\n",
        "    ( 'folder1',\n",
        "        [\n",
        "            'file1',\n",
        "            ( 'folder2', \n",
        "                [\n",
        "                    'file2',\n",
        "                    'file3'\n",
        "                ] \n",
        "            ),\n",
        "            ( 'folder3', \n",
        "                [\n",
        "                    'file3', \n",
        "                    'file4',\n",
        "                    ('folder4', ['file3'])\n",
        "                ] \n",
        "            ),\n",
        "            'file5'\n",
        "        ]\n",
        "    )\n",
        "]\n",
        "# def search(folder,filename:str,root_folder=''): return [str(f'{root_folder}/{filename}')] if folder == filename else reduce(lambda result,element: result + search(element,filename,root_folder) if isinstance(folder,list) else result + search(element,filename,root_folder+'//'+folder[0]),folder if isinstance(folder,list) else folder[1],[]) if (isinstance(folder,list) or isinstance(folder,tuple) and len(folder)-1) else []\n",
        "# ВАШ КОД ТУТ\n",
        "def search(folder,filename:str,root_folder=''):\n",
        "    result = []\n",
        "    if folder == filename: result.append(f'{root_folder}/{filename}')\n",
        "    elif isinstance(folder,list) or isinstance(folder,tuple) and len(folder)-1:\n",
        "        if isinstance(folder,list):\n",
        "            root_folder,folder = '',folder\n",
        "        else:\n",
        "            root_folder,folder = root_folder+'//'+folder[0] if root_folder != '' else root_folder+'/'+folder[0], folder[1]\n",
        "        result += reduce(lambda result,element: result + search(element,filename,root_folder),folder,[]) # look how they massacred my boy...\n",
        "    return result\n",
        "\n",
        "# ПЕРЕВІРКА\n",
        "print(search(dirs, 'file1'))\n",
        "print(search(dirs, 'file2'))\n",
        "print(search(dirs, 'file3'))\n",
        "print(search(dirs, 'file4'))\n",
        "print(search(dirs, 'file5'))\n",
        "print(search(dirs, 'file6'))\n",
        "print(search(dirs, 'folder1'))\n",
        "\n",
        "assert search(dirs, 'file1') == ['/folder1/file1'], 'Failed test for file1'\n",
        "assert search(dirs, 'file2') == ['/folder1//folder2/file2'], 'Failed test for file2'\n",
        "assert search(dirs, 'file3') == ['/folder1//folder2/file3', '/folder1//folder3/file3', '/folder1//folder3//folder4/file3'], 'Failed test for file3'\n",
        "assert search(dirs, 'file4') == ['/folder1//folder3/file4'], 'Failed test for file4'\n",
        "assert search(dirs, 'file5') == ['/folder1/file5'], 'Failed test for file5'\n",
        "assert search(dirs, 'file6') == [], 'Failed test for file6'\n",
        "assert search(dirs, 'folder1') == [], 'Failed test for folder1'\n",
        "print('All tests good!')"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [],
      "name": "Practice_12_13_KM_01_.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.10.1"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}