Programming_class.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    },
    "widgets": {
      "application/vnd.jupyter.widget-state+json": {
        "c35577721d1f4d18b2649dd2a05e611c": {
          "model_module": "@jupyter-widgets/controls",
          "model_name": "HBoxModel",
          "model_module_version": "1.5.0",
          "state": {
            "_dom_classes": [],
            "_model_module": "@jupyter-widgets/controls",
            "_model_module_version": "1.5.0",
            "_model_name": "HBoxModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/controls",
            "_view_module_version": "1.5.0",
            "_view_name": "HBoxView",
            "box_style": "",
            "children": [
              "IPY_MODEL_95f40d772c144dbda149a784762868c6",
              "IPY_MODEL_31a174dbd20a4065b3d7278c4c984b6e",
              "IPY_MODEL_1101c3d678b34cebb4b0b4e665d94a2c"
            ],
            "layout": "IPY_MODEL_f04e6ffc1c944ef5b053845a9950df3d"
          }
        },
        "95f40d772c144dbda149a784762868c6": {
          "model_module": "@jupyter-widgets/controls",
          "model_name": "HTMLModel",
          "model_module_version": "1.5.0",
          "state": {
            "_dom_classes": [],
            "_model_module": "@jupyter-widgets/controls",
            "_model_module_version": "1.5.0",
            "_model_name": "HTMLModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/controls",
            "_view_module_version": "1.5.0",
            "_view_name": "HTMLView",
            "description": "",
            "description_tooltip": null,
            "layout": "IPY_MODEL_c612a5899bd64eb8822e3ec7c8ecbccf",
            "placeholder": "​",
            "style": "IPY_MODEL_7f98e1dfa3eb4dc591774d0da20c40b3",
            "value": "100%"
          }
        },
        "31a174dbd20a4065b3d7278c4c984b6e": {
          "model_module": "@jupyter-widgets/controls",
          "model_name": "FloatProgressModel",
          "model_module_version": "1.5.0",
          "state": {
            "_dom_classes": [],
            "_model_module": "@jupyter-widgets/controls",
            "_model_module_version": "1.5.0",
            "_model_name": "FloatProgressModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/controls",
            "_view_module_version": "1.5.0",
            "_view_name": "ProgressView",
            "bar_style": "success",
            "description": "",
            "description_tooltip": null,
            "layout": "IPY_MODEL_aba59680f3374e8a80256b6596fc59cb",
            "max": 5000,
            "min": 0,
            "orientation": "horizontal",
            "style": "IPY_MODEL_8b8f204056e14a39987f4509c4b0ac42",
            "value": 5000
          }
        },
        "1101c3d678b34cebb4b0b4e665d94a2c": {
          "model_module": "@jupyter-widgets/controls",
          "model_name": "HTMLModel",
          "model_module_version": "1.5.0",
          "state": {
            "_dom_classes": [],
            "_model_module": "@jupyter-widgets/controls",
            "_model_module_version": "1.5.0",
            "_model_name": "HTMLModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/controls",
            "_view_module_version": "1.5.0",
            "_view_name": "HTMLView",
            "description": "",
            "description_tooltip": null,
            "layout": "IPY_MODEL_6937dabe239548fab32cd460720d5ab7",
            "placeholder": "​",
            "style": "IPY_MODEL_2d88733d74414e2da9135e668a0fa0ed",
            "value": " 5000/5000 [01:29&lt;00:00, 56.99it/s]"
          }
        },
        "f04e6ffc1c944ef5b053845a9950df3d": {
          "model_module": "@jupyter-widgets/base",
          "model_name": "LayoutModel",
          "model_module_version": "1.2.0",
          "state": {
            "_model_module": "@jupyter-widgets/base",
            "_model_module_version": "1.2.0",
            "_model_name": "LayoutModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/base",
            "_view_module_version": "1.2.0",
            "_view_name": "LayoutView",
            "align_content": null,
            "align_items": null,
            "align_self": null,
            "border": null,
            "bottom": null,
            "display": null,
            "flex": null,
            "flex_flow": null,
            "grid_area": null,
            "grid_auto_columns": null,
            "grid_auto_flow": null,
            "grid_auto_rows": null,
            "grid_column": null,
            "grid_gap": null,
            "grid_row": null,
            "grid_template_areas": null,
            "grid_template_columns": null,
            "grid_template_rows": null,
            "height": null,
            "justify_content": null,
            "justify_items": null,
            "left": null,
            "margin": null,
            "max_height": null,
            "max_width": null,
            "min_height": null,
            "min_width": null,
            "object_fit": null,
            "object_position": null,
            "order": null,
            "overflow": null,
            "overflow_x": null,
            "overflow_y": null,
            "padding": null,
            "right": null,
            "top": null,
            "visibility": null,
            "width": null
          }
        },
        "c612a5899bd64eb8822e3ec7c8ecbccf": {
          "model_module": "@jupyter-widgets/base",
          "model_name": "LayoutModel",
          "model_module_version": "1.2.0",
          "state": {
            "_model_module": "@jupyter-widgets/base",
            "_model_module_version": "1.2.0",
            "_model_name": "LayoutModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/base",
            "_view_module_version": "1.2.0",
            "_view_name": "LayoutView",
            "align_content": null,
            "align_items": null,
            "align_self": null,
            "border": null,
            "bottom": null,
            "display": null,
            "flex": null,
            "flex_flow": null,
            "grid_area": null,
            "grid_auto_columns": null,
            "grid_auto_flow": null,
            "grid_auto_rows": null,
            "grid_column": null,
            "grid_gap": null,
            "grid_row": null,
            "grid_template_areas": null,
            "grid_template_columns": null,
            "grid_template_rows": null,
            "height": null,
            "justify_content": null,
            "justify_items": null,
            "left": null,
            "margin": null,
            "max_height": null,
            "max_width": null,
            "min_height": null,
            "min_width": null,
            "object_fit": null,
            "object_position": null,
            "order": null,
            "overflow": null,
            "overflow_x": null,
            "overflow_y": null,
            "padding": null,
            "right": null,
            "top": null,
            "visibility": null,
            "width": null
          }
        },
        "7f98e1dfa3eb4dc591774d0da20c40b3": {
          "model_module": "@jupyter-widgets/controls",
          "model_name": "DescriptionStyleModel",
          "model_module_version": "1.5.0",
          "state": {
            "_model_module": "@jupyter-widgets/controls",
            "_model_module_version": "1.5.0",
            "_model_name": "DescriptionStyleModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/base",
            "_view_module_version": "1.2.0",
            "_view_name": "StyleView",
            "description_width": ""
          }
        },
        "aba59680f3374e8a80256b6596fc59cb": {
          "model_module": "@jupyter-widgets/base",
          "model_name": "LayoutModel",
          "model_module_version": "1.2.0",
          "state": {
            "_model_module": "@jupyter-widgets/base",
            "_model_module_version": "1.2.0",
            "_model_name": "LayoutModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/base",
            "_view_module_version": "1.2.0",
            "_view_name": "LayoutView",
            "align_content": null,
            "align_items": null,
            "align_self": null,
            "border": null,
            "bottom": null,
            "display": null,
            "flex": null,
            "flex_flow": null,
            "grid_area": null,
            "grid_auto_columns": null,
            "grid_auto_flow": null,
            "grid_auto_rows": null,
            "grid_column": null,
            "grid_gap": null,
            "grid_row": null,
            "grid_template_areas": null,
            "grid_template_columns": null,
            "grid_template_rows": null,
            "height": null,
            "justify_content": null,
            "justify_items": null,
            "left": null,
            "margin": null,
            "max_height": null,
            "max_width": null,
            "min_height": null,
            "min_width": null,
            "object_fit": null,
            "object_position": null,
            "order": null,
            "overflow": null,
            "overflow_x": null,
            "overflow_y": null,
            "padding": null,
            "right": null,
            "top": null,
            "visibility": null,
            "width": null
          }
        },
        "8b8f204056e14a39987f4509c4b0ac42": {
          "model_module": "@jupyter-widgets/controls",
          "model_name": "ProgressStyleModel",
          "model_module_version": "1.5.0",
          "state": {
            "_model_module": "@jupyter-widgets/controls",
            "_model_module_version": "1.5.0",
            "_model_name": "ProgressStyleModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/base",
            "_view_module_version": "1.2.0",
            "_view_name": "StyleView",
            "bar_color": null,
            "description_width": ""
          }
        },
        "6937dabe239548fab32cd460720d5ab7": {
          "model_module": "@jupyter-widgets/base",
          "model_name": "LayoutModel",
          "model_module_version": "1.2.0",
          "state": {
            "_model_module": "@jupyter-widgets/base",
            "_model_module_version": "1.2.0",
            "_model_name": "LayoutModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/base",
            "_view_module_version": "1.2.0",
            "_view_name": "LayoutView",
            "align_content": null,
            "align_items": null,
            "align_self": null,
            "border": null,
            "bottom": null,
            "display": null,
            "flex": null,
            "flex_flow": null,
            "grid_area": null,
            "grid_auto_columns": null,
            "grid_auto_flow": null,
            "grid_auto_rows": null,
            "grid_column": null,
            "grid_gap": null,
            "grid_row": null,
            "grid_template_areas": null,
            "grid_template_columns": null,
            "grid_template_rows": null,
            "height": null,
            "justify_content": null,
            "justify_items": null,
            "left": null,
            "margin": null,
            "max_height": null,
            "max_width": null,
            "min_height": null,
            "min_width": null,
            "object_fit": null,
            "object_position": null,
            "order": null,
            "overflow": null,
            "overflow_x": null,
            "overflow_y": null,
            "padding": null,
            "right": null,
            "top": null,
            "visibility": null,
            "width": null
          }
        },
        "2d88733d74414e2da9135e668a0fa0ed": {
          "model_module": "@jupyter-widgets/controls",
          "model_name": "DescriptionStyleModel",
          "model_module_version": "1.5.0",
          "state": {
            "_model_module": "@jupyter-widgets/controls",
            "_model_module_version": "1.5.0",
            "_model_name": "DescriptionStyleModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/base",
            "_view_module_version": "1.2.0",
            "_view_name": "StyleView",
            "description_width": ""
          }
        },
        "a69e26c8b3624d18a4025812cf31bead": {
          "model_module": "@jupyter-widgets/controls",
          "model_name": "HBoxModel",
          "model_module_version": "1.5.0",
          "state": {
            "_dom_classes": [],
            "_model_module": "@jupyter-widgets/controls",
            "_model_module_version": "1.5.0",
            "_model_name": "HBoxModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/controls",
            "_view_module_version": "1.5.0",
            "_view_name": "HBoxView",
            "box_style": "",
            "children": [
              "IPY_MODEL_6899ee2061924852b4e7165b6cbed3dc",
              "IPY_MODEL_b0e52890e0ac42b7a8d27d02c6d43e65",
              "IPY_MODEL_be35071209124f1fa94b82cc7f93552e"
            ],
            "layout": "IPY_MODEL_eec59aa18afa4782beefd56524aadf34"
          }
        },
        "6899ee2061924852b4e7165b6cbed3dc": {
          "model_module": "@jupyter-widgets/controls",
          "model_name": "HTMLModel",
          "model_module_version": "1.5.0",
          "state": {
            "_dom_classes": [],
            "_model_module": "@jupyter-widgets/controls",
            "_model_module_version": "1.5.0",
            "_model_name": "HTMLModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/controls",
            "_view_module_version": "1.5.0",
            "_view_name": "HTMLView",
            "description": "",
            "description_tooltip": null,
            "layout": "IPY_MODEL_03d77d1f4ece4889a6a1eca7e2f699d4",
            "placeholder": "​",
            "style": "IPY_MODEL_57f7a2f83c4a4828937f0ae89200700d",
            "value": "100%"
          }
        },
        "b0e52890e0ac42b7a8d27d02c6d43e65": {
          "model_module": "@jupyter-widgets/controls",
          "model_name": "FloatProgressModel",
          "model_module_version": "1.5.0",
          "state": {
            "_dom_classes": [],
            "_model_module": "@jupyter-widgets/controls",
            "_model_module_version": "1.5.0",
            "_model_name": "FloatProgressModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/controls",
            "_view_module_version": "1.5.0",
            "_view_name": "ProgressView",
            "bar_style": "success",
            "description": "",
            "description_tooltip": null,
            "layout": "IPY_MODEL_e06fef203bb44b2fb50df6c949c53202",
            "max": 8423,
            "min": 0,
            "orientation": "horizontal",
            "style": "IPY_MODEL_bc3e5079115143c3a83257b9d7503f1d",
            "value": 8423
          }
        },
        "be35071209124f1fa94b82cc7f93552e": {
          "model_module": "@jupyter-widgets/controls",
          "model_name": "HTMLModel",
          "model_module_version": "1.5.0",
          "state": {
            "_dom_classes": [],
            "_model_module": "@jupyter-widgets/controls",
            "_model_module_version": "1.5.0",
            "_model_name": "HTMLModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/controls",
            "_view_module_version": "1.5.0",
            "_view_name": "HTMLView",
            "description": "",
            "description_tooltip": null,
            "layout": "IPY_MODEL_f5bd635b0a9e4e3caf627264047fabe8",
            "placeholder": "​",
            "style": "IPY_MODEL_f89fff5045544335ac2b1b52c78c8df8",
            "value": " 8423/8423 [00:00&lt;00:00, 233852.88it/s]"
          }
        },
        "eec59aa18afa4782beefd56524aadf34": {
          "model_module": "@jupyter-widgets/base",
          "model_name": "LayoutModel",
          "model_module_version": "1.2.0",
          "state": {
            "_model_module": "@jupyter-widgets/base",
            "_model_module_version": "1.2.0",
            "_model_name": "LayoutModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/base",
            "_view_module_version": "1.2.0",
            "_view_name": "LayoutView",
            "align_content": null,
            "align_items": null,
            "align_self": null,
            "border": null,
            "bottom": null,
            "display": null,
            "flex": null,
            "flex_flow": null,
            "grid_area": null,
            "grid_auto_columns": null,
            "grid_auto_flow": null,
            "grid_auto_rows": null,
            "grid_column": null,
            "grid_gap": null,
            "grid_row": null,
            "grid_template_areas": null,
            "grid_template_columns": null,
            "grid_template_rows": null,
            "height": null,
            "justify_content": null,
            "justify_items": null,
            "left": null,
            "margin": null,
            "max_height": null,
            "max_width": null,
            "min_height": null,
            "min_width": null,
            "object_fit": null,
            "object_position": null,
            "order": null,
            "overflow": null,
            "overflow_x": null,
            "overflow_y": null,
            "padding": null,
            "right": null,
            "top": null,
            "visibility": null,
            "width": null
          }
        },
        "03d77d1f4ece4889a6a1eca7e2f699d4": {
          "model_module": "@jupyter-widgets/base",
          "model_name": "LayoutModel",
          "model_module_version": "1.2.0",
          "state": {
            "_model_module": "@jupyter-widgets/base",
            "_model_module_version": "1.2.0",
            "_model_name": "LayoutModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/base",
            "_view_module_version": "1.2.0",
            "_view_name": "LayoutView",
            "align_content": null,
            "align_items": null,
            "align_self": null,
            "border": null,
            "bottom": null,
            "display": null,
            "flex": null,
            "flex_flow": null,
            "grid_area": null,
            "grid_auto_columns": null,
            "grid_auto_flow": null,
            "grid_auto_rows": null,
            "grid_column": null,
            "grid_gap": null,
            "grid_row": null,
            "grid_template_areas": null,
            "grid_template_columns": null,
            "grid_template_rows": null,
            "height": null,
            "justify_content": null,
            "justify_items": null,
            "left": null,
            "margin": null,
            "max_height": null,
            "max_width": null,
            "min_height": null,
            "min_width": null,
            "object_fit": null,
            "object_position": null,
            "order": null,
            "overflow": null,
            "overflow_x": null,
            "overflow_y": null,
            "padding": null,
            "right": null,
            "top": null,
            "visibility": null,
            "width": null
          }
        },
        "57f7a2f83c4a4828937f0ae89200700d": {
          "model_module": "@jupyter-widgets/controls",
          "model_name": "DescriptionStyleModel",
          "model_module_version": "1.5.0",
          "state": {
            "_model_module": "@jupyter-widgets/controls",
            "_model_module_version": "1.5.0",
            "_model_name": "DescriptionStyleModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/base",
            "_view_module_version": "1.2.0",
            "_view_name": "StyleView",
            "description_width": ""
          }
        },
        "e06fef203bb44b2fb50df6c949c53202": {
          "model_module": "@jupyter-widgets/base",
          "model_name": "LayoutModel",
          "model_module_version": "1.2.0",
          "state": {
            "_model_module": "@jupyter-widgets/base",
            "_model_module_version": "1.2.0",
            "_model_name": "LayoutModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/base",
            "_view_module_version": "1.2.0",
            "_view_name": "LayoutView",
            "align_content": null,
            "align_items": null,
            "align_self": null,
            "border": null,
            "bottom": null,
            "display": null,
            "flex": null,
            "flex_flow": null,
            "grid_area": null,
            "grid_auto_columns": null,
            "grid_auto_flow": null,
            "grid_auto_rows": null,
            "grid_column": null,
            "grid_gap": null,
            "grid_row": null,
            "grid_template_areas": null,
            "grid_template_columns": null,
            "grid_template_rows": null,
            "height": null,
            "justify_content": null,
            "justify_items": null,
            "left": null,
            "margin": null,
            "max_height": null,
            "max_width": null,
            "min_height": null,
            "min_width": null,
            "object_fit": null,
            "object_position": null,
            "order": null,
            "overflow": null,
            "overflow_x": null,
            "overflow_y": null,
            "padding": null,
            "right": null,
            "top": null,
            "visibility": null,
            "width": null
          }
        },
        "bc3e5079115143c3a83257b9d7503f1d": {
          "model_module": "@jupyter-widgets/controls",
          "model_name": "ProgressStyleModel",
          "model_module_version": "1.5.0",
          "state": {
            "_model_module": "@jupyter-widgets/controls",
            "_model_module_version": "1.5.0",
            "_model_name": "ProgressStyleModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/base",
            "_view_module_version": "1.2.0",
            "_view_name": "StyleView",
            "bar_color": null,
            "description_width": ""
          }
        },
        "f5bd635b0a9e4e3caf627264047fabe8": {
          "model_module": "@jupyter-widgets/base",
          "model_name": "LayoutModel",
          "model_module_version": "1.2.0",
          "state": {
            "_model_module": "@jupyter-widgets/base",
            "_model_module_version": "1.2.0",
            "_model_name": "LayoutModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/base",
            "_view_module_version": "1.2.0",
            "_view_name": "LayoutView",
            "align_content": null,
            "align_items": null,
            "align_self": null,
            "border": null,
            "bottom": null,
            "display": null,
            "flex": null,
            "flex_flow": null,
            "grid_area": null,
            "grid_auto_columns": null,
            "grid_auto_flow": null,
            "grid_auto_rows": null,
            "grid_column": null,
            "grid_gap": null,
            "grid_row": null,
            "grid_template_areas": null,
            "grid_template_columns": null,
            "grid_template_rows": null,
            "height": null,
            "justify_content": null,
            "justify_items": null,
            "left": null,
            "margin": null,
            "max_height": null,
            "max_width": null,
            "min_height": null,
            "min_width": null,
            "object_fit": null,
            "object_position": null,
            "order": null,
            "overflow": null,
            "overflow_x": null,
            "overflow_y": null,
            "padding": null,
            "right": null,
            "top": null,
            "visibility": null,
            "width": null
          }
        },
        "f89fff5045544335ac2b1b52c78c8df8": {
          "model_module": "@jupyter-widgets/controls",
          "model_name": "DescriptionStyleModel",
          "model_module_version": "1.5.0",
          "state": {
            "_model_module": "@jupyter-widgets/controls",
            "_model_module_version": "1.5.0",
            "_model_name": "DescriptionStyleModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/base",
            "_view_module_version": "1.2.0",
            "_view_name": "StyleView",
            "description_width": ""
          }
        }
      }
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "Задача:\n",
        "\n",
        "Есть входной текст (строка). Заданы начальный отступ (indent) и ширина выходного текста (width).\n",
        "\n",
        "Нужно написать функцию, которая выдает текст заданной ширины. Если последняя строка короче, чем width, нужно между словами в ней добавить пробелов."
      ],
      "metadata": {
        "id": "uwJCOC4L5t4e"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "Gb_6NvgS5gKK"
      },
      "outputs": [],
      "source": [
        "def wrap_text(text:str, indent:int, width:int):\n",
        "    text = \" \" * indent + text\n",
        "    chunks, chunk_size = len(text), width\n",
        "    split_lines_width = [text[i:i+width] for i in range(0, chunks, chunk_size)]\n",
        "    return split_lines_width"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "input_text = 'Однажды весною, в час небывало жаркого заката, в Москве, на Патриарших прудах, появились два гражданина. Первый из них, одетый в летнюю серенькую пару, был маленького роста, упитан, лыс, свою приличную шляпу пирожком нес в руке, а на хорошо выбритом лице его помещались сверхъестественных размеров очки в черной роговой оправе. Второй – плечистый, рыжеватый, вихрастый молодой человек в заломленной на затылок клетчатой кепке – был в ковбойке, жеваных белых брюках и в черных тапочках.'"
      ],
      "metadata": {
        "id": "sAlmrcGn7y9R"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def wrap_text2(text:str, indent:int, width:int):\n",
        "    wrapped_lines = [[''] * indent, ]\n",
        "    split_spaces = text.split()\n",
        "    for token in split_spaces:\n",
        "        if len(' '.join(wrapped_lines[-1])) + len(token) < width:\n",
        "            wrapped_lines[-1].append(token)\n",
        "        else:\n",
        "            wrapped_lines.append([token, ])\n",
        "\n",
        "    for i in range(len(wrapped_lines)):\n",
        "        wrapped_lines[i] = ' '.join(wrapped_lines[i])\n",
        "        last_space_position = 0\n",
        "        while len(wrapped_lines[i]) < width and ' ' in wrapped_lines[i]:\n",
        "            last_space_position = wrapped_lines[i].find(' ', last_space_position+2) if wrapped_lines[i].find(' ', last_space_position+2)!=-1 else last_space_position\n",
        "            wrapped_lines[i] = wrapped_lines[i][:last_space_position] + ' ' + wrapped_lines[i][last_space_position:]\n",
        "        if len(wrapped_lines[i]) < width and ' ' not in wrapped_lines[i]:\n",
        "            wrapped_lines[i] += ' ' * (width - len(wrapped_lines[i]))\n",
        "    return wrapped_lines"
      ],
      "metadata": {
        "id": "O6ENBkK-DyIz"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "for line in wrap_text2(input_text, indent=5, width=25):\n",
        "    print(len(line), line)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "UwALH9oR5tUG",
        "outputId": "26d5be06-47b4-4d47-991e-6d4e5c678839"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "25         Однажды весною, в\n",
            "25 час  небывало     жаркого\n",
            "25 заката,  в  Москве,    на\n",
            "25 Патриарших        прудах,\n",
            "25 появились два гражданина.\n",
            "25 Первый  из  них, одетый в\n",
            "25 летнюю  серенькую   пару,\n",
            "25 был  маленького    роста,\n",
            "25 упитан,  лыс,        свою\n",
            "25 приличную  шляпу пирожком\n",
            "25 нес  в  руке, а на хорошо\n",
            "25 выбритом  лице        его\n",
            "25 помещались               \n",
            "25 сверхъестественных       \n",
            "25 размеров  очки  в  черной\n",
            "25 роговой  оправе. Второй –\n",
            "25 плечистый,     рыжеватый,\n",
            "25 вихрастый молодой человек\n",
            "25 в заломленной  на затылок\n",
            "25 клетчатой  кепке  – был в\n",
            "25 ковбойке,  жеваных  белых\n",
            "25 брюках  и  в       черных\n",
            "25 тапочках.                \n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "import functools"
      ],
      "metadata": {
        "id": "6fKI28tTPJjP"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "vowels = [ch for ch in 'АЕЁИОУЫЭЮЯаеёиоуыэюя']\n",
        "consonants = [ch for ch in 'БВГДЖЗКЛМНПРСТФХЦЧШЩбвгджзклмнпрстфхцчшщ']\n",
        "BLACK_LIST = {'не', }"
      ],
      "metadata": {
        "id": "bm3ITStAPJf0"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def is_syllabic(seq):\n",
        "    return not set(seq).isdisjoint(vowels)"
      ],
      "metadata": {
        "id": "C2OcfOcUPJdI"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def hyphenate_positions(word):\n",
        "    if word.isupper():\n",
        "        return word\n",
        "    return [i for i in range(1, len(word)-2)\n",
        "            if is_syllabic(word[:i+1]) and\n",
        "            is_syllabic(word[i+1:]) and word[:i+1].lower() not in BLACK_LIST and\n",
        "           not (word[i] in consonants and word[i+1] in vowels) and\n",
        "           word[i+1] not in 'ЫыЙйЪъЬь-' and\n",
        "           not (word[i] in consonants and word[i]==word[i-1]) and\n",
        "           not (word[i+1] in consonants and word[i+2]==word[i+1])]"
      ],
      "metadata": {
        "id": "jmx8dZ0SPJVT"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def hyphenate(word):\n",
        "    result = []\n",
        "    def do_split(prev_pos, pos):\n",
        "        result.append(word[prev_pos:pos+1])\n",
        "        return pos + 1\n",
        "    lastpos = functools.reduce(do_split, hyphenate_positions(word), 0)\n",
        "    result.append(word[lastpos:])\n",
        "    return result"
      ],
      "metadata": {
        "id": "7CTaO0eUPJR3"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def hyphenate_alt(word):\n",
        "    return list(map(lambda pos: (word[0:pos+1], word[pos+1:]), hyphenate_positions(word)))"
      ],
      "metadata": {
        "id": "jGeMFZc6PJPD"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def wrap_text_with_hyphenate(text:str, indent:int, width:int):\n",
        "    wrapped_lines = [[''] * indent, ]\n",
        "    split_spaces = text.split()\n",
        "    token_hypenations_candidates = [hyphenate_alt(token) for token in split_spaces]\n",
        "    h_flag = True\n",
        "    for token, token_hypenations in zip(split_spaces, token_hypenations_candidates):\n",
        "        if len(' '.join(wrapped_lines[-1])) + len(token) < width:\n",
        "            wrapped_lines[-1].append(token)\n",
        "        else:\n",
        "            flag = True\n",
        "            for variant in token_hypenations:\n",
        "                for i in range(len(variant)-1):\n",
        "                    if len(' '.join(wrapped_lines[-1])) + len(variant[i])+1 < width and flag and h_flag:\n",
        "                        wrapped_lines[-1].append(variant[i]+'-')\n",
        "                        wrapped_lines.append([variant[i+1], ])\n",
        "                        flag = False\n",
        "                        h_flag = False\n",
        "            else:\n",
        "                if flag:\n",
        "                    wrapped_lines.append([token, ])\n",
        "                    h_flag = True\n",
        "    for i in range(len(wrapped_lines)):\n",
        "        wrapped_lines[i] = ' '.join(wrapped_lines[i])\n",
        "        last_space_position = 0\n",
        "        while len(wrapped_lines[i]) < width and ' ' in wrapped_lines[i]:\n",
        "            last_space_position = wrapped_lines[i].find(' ', last_space_position+2) if wrapped_lines[i].find(' ', last_space_position+2)!=-1 else last_space_position\n",
        "            wrapped_lines[i] = wrapped_lines[i][:last_space_position] + ' ' + wrapped_lines[i][last_space_position:]\n",
        "        if len(wrapped_lines[i]) < width and ' ' not in wrapped_lines[i]:\n",
        "            wrapped_lines[i] += ' ' * (width - len(wrapped_lines[i]))\n",
        "    return wrapped_lines"
      ],
      "metadata": {
        "id": "hTcBZ4Hx-tP1"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "for line in wrap_text_with_hyphenate(input_text, indent=4, width=30):\n",
        "    print(len(line), line)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "rVM-zAVeVErh",
        "outputId": "25c966d6-5d3a-416b-b53c-c09418cab951"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "30       Однажды  весною,  в  час\n",
            "30 небывало жаркого заката, в Мо-\n",
            "30 скве,  на  Патриарших  прудах,\n",
            "30 появились  два гражданина. Пе-\n",
            "30 рвый  из  них, одетый в летнюю\n",
            "30 серенькую пару, был маленького\n",
            "30 роста,  упитан, лыс, свою при-\n",
            "30 личную  шляпу  пирожком  нес в\n",
            "30 руке, а на хорошо выбритом ли-\n",
            "30 це  его             помещались\n",
            "30 сверхъестественных    размеров\n",
            "30 очки  в черной роговой оправе.\n",
            "30 Второй – плечистый, рыжеватый,\n",
            "30 вихрастый  молодой  человек  в\n",
            "30 заломленной  на  затылок  кле-\n",
            "30 тчатой кепке – был в ковбойке,\n",
            "30 жеваных  белых  брюках и в че-\n",
            "30 рных                 тапочках.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Теперь у нас есть текст, деленный на абзацы, и нам нужно разбить его на страницы.\n",
        "\n",
        "Условия\n",
        "* запрет висящих строк, т.е. первую или последнюю строку нельзя ни оставлять, ни переносить на новую страницу\n",
        "\n",
        "* запрет разрывать абзац по строке, которая заканчивается переносом. Такая строка уходит на новую страницу.\n",
        "\n",
        "** возможно еще какие-то условия (мы забыли)\n"
      ],
      "metadata": {
        "id": "Tmz7hPBUPHZS"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "paragraphs = [\n",
        "    'Однажды весною, в час небывало жаркого заката, в Москве, на Патриарших прудах, появились два гражданина.',\n",
        "    'Первый из них, одетый в летнюю серенькую пару, был маленького роста, упитан, лыс, свою приличную шляпу пирожком нес в руке, а на хорошо выбритом лице его помещались сверхъестественных размеров очки в черной роговой оправе.',\n",
        "    'Второй – плечистый, рыжеватый, вихрастый молодой человек в заломленной на затылок клетчатой кепке – был в ковбойке, жеваных белых брюках и в черных тапочках.']"
      ],
      "metadata": {
        "id": "puRv-CXO-tJr"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def paginate(paragraphs:list, indent:int, line_widthh:int, lines_on_page:int):\n",
        "    pages = [[], ]\n",
        "    paragraphs_to_lines= [wrap_text_with_hyphenate(paragraph, indent=indent, width=line_widthh) for paragraph in paragraphs]\n",
        "    for paragraph_lines in paragraphs_to_lines:\n",
        "        paragraph_lines_len = len(paragraph_lines)\n",
        "        for i in range(paragraph_lines_len):\n",
        "            if lines_on_page - len(pages[-1]) > 1:\n",
        "                pages[-1].append(paragraph_lines[i])\n",
        "            else:\n",
        "                if paragraph_lines[i][-1] == '-':\n",
        "                    pages[-1].append('FILLER')\n",
        "                    pages.append([paragraph_lines[i], ])\n",
        "                else:\n",
        "                    if i == 1:\n",
        "                        pages[-1].append('FILLER')\n",
        "                        pages.append([paragraph_lines[i], ])\n",
        "                    else:\n",
        "                        if paragraph_lines_len - i < 1: # 1?\n",
        "                            pages[-1].append('FILLER')\n",
        "                            pages.append([paragraph_lines[i], ])\n",
        "                        else:\n",
        "                            pages[-1].append(paragraph_lines[i])\n",
        "    return pages"
      ],
      "metadata": {
        "id": "5A1BNglKLfEb"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "paginate(paragraphs, 3,  30, 5)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "59PzW8zaLE8z",
        "outputId": "baf7c43b-9c74-4e37-df9c-0b7d24ceda71"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[['   Однажды весною, в час небы-',\n",
              "  'вало жаркого заката, в Москве,',\n",
              "  'на  Патриарших  прудах,    по-',\n",
              "  'явились  два       гражданина.',\n",
              "  'FILLER'],\n",
              " ['   Первый из них, одетый в ле-',\n",
              "  'тнюю  серенькую  пару,     был',\n",
              "  'маленького роста, упитан, лыс,',\n",
              "  'свою  приличную шляпу пирожком',\n",
              "  'FILLER'],\n",
              " ['нес  в  руке,  а на хорошо вы-',\n",
              "  'бритом  лице  его   помещались',\n",
              "  'сверхъестественных    размеров',\n",
              "  'очки  в черной роговой оправе.',\n",
              "  'FILLER'],\n",
              " ['    Второй  –  плечистый,  ры-',\n",
              "  'жеватый,  вихрастый    молодой',\n",
              "  'человек  в  заломленной на за-',\n",
              "  'тылок  клетчатой кепке – был в',\n",
              "  'ковбойке, жеваных белых брюках',\n",
              "  'и в  черных          тапочках.']]"
            ]
          },
          "metadata": {},
          "execution_count": 41
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Алгоритм Харриса по выделению морфем из текста"
      ],
      "metadata": {
        "id": "bLvmPMknQO9E"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "with open('russian (1).txt', 'r', encoding='windows-1251') as f:\n",
        "    RUSSIAN_WORDS = [l.strip() for l in f.readlines()]"
      ],
      "metadata": {
        "id": "H4UH4dN8-tEG"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "from random import sample\n",
        "from tqdm.notebook import tqdm"
      ],
      "metadata": {
        "id": "KAdRE0N5VrP1"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "RUSSIAN_WORDS_SAMPLE = RUSSIAN_WORDS[:5_000]"
      ],
      "metadata": {
        "id": "3kQYXOKmVuZj"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "RUSSIAN_WORDS_SAMPLE = ['стол', 'стола', 'столы', 'столами', 'столовая', 'столовой', 'столовыми']"
      ],
      "metadata": {
        "id": "hHD5UYUaYEAS"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "PREFIXES_ONE_LETTER = {}\n",
        "for word in tqdm(RUSSIAN_WORDS_SAMPLE):\n",
        "    word += '#'\n",
        "    for i in range(1, len(word)):\n",
        "        prefix = word[:i]\n",
        "        variants_one_letter = set()\n",
        "        for word2 in RUSSIAN_WORDS_SAMPLE:\n",
        "            if word2.startswith(prefix):\n",
        "                variants_one_letter.add(word[len(prefix):len(prefix)+1])\n",
        "        if prefix in PREFIXES_ONE_LETTER:\n",
        "            PREFIXES_ONE_LETTER[prefix] |= variants_one_letter\n",
        "        else:\n",
        "            PREFIXES_ONE_LETTER[prefix] = variants_one_letter"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 49,
          "referenced_widgets": [
            "c35577721d1f4d18b2649dd2a05e611c",
            "95f40d772c144dbda149a784762868c6",
            "31a174dbd20a4065b3d7278c4c984b6e",
            "1101c3d678b34cebb4b0b4e665d94a2c",
            "f04e6ffc1c944ef5b053845a9950df3d",
            "c612a5899bd64eb8822e3ec7c8ecbccf",
            "7f98e1dfa3eb4dc591774d0da20c40b3",
            "aba59680f3374e8a80256b6596fc59cb",
            "8b8f204056e14a39987f4509c4b0ac42",
            "6937dabe239548fab32cd460720d5ab7",
            "2d88733d74414e2da9135e668a0fa0ed"
          ]
        },
        "id": "X-tH-mXQS3s_",
        "outputId": "8df7238b-22ef-423b-d286-d5b9be91f404"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "  0%|          | 0/5000 [00:00<?, ?it/s]"
            ],
            "application/vnd.jupyter.widget-view+json": {
              "version_major": 2,
              "version_minor": 0,
              "model_id": "c35577721d1f4d18b2649dd2a05e611c"
            }
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "PREFIXES_ONE_LETTER_to_int = [(prefix, len(vars)) for prefix, vars in PREFIXES_ONE_LETTER.items()]"
      ],
      "metadata": {
        "id": "8FozaiBMY4uE"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "replace_prefix = ''\n",
        "MORPHEMES = set()\n",
        "for i in tqdm(range(1, len(PREFIXES_ONE_LETTER_to_int))):\n",
        "    previous_prefix, previous_value = PREFIXES_ONE_LETTER_to_int[i-1]\n",
        "    prefix, value = PREFIXES_ONE_LETTER_to_int[i]\n",
        "    if value - previous_value > 1:\n",
        "        if replace_prefix in MORPHEMES:\n",
        "            MORPHEMES.add(prefix.replace(replace_prefix, ''))\n",
        "            replace_prefix = ''\n",
        "        else:\n",
        "            replace_prefix = prefix\n",
        "            MORPHEMES.add(prefix)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 49,
          "referenced_widgets": [
            "a69e26c8b3624d18a4025812cf31bead",
            "6899ee2061924852b4e7165b6cbed3dc",
            "b0e52890e0ac42b7a8d27d02c6d43e65",
            "be35071209124f1fa94b82cc7f93552e",
            "eec59aa18afa4782beefd56524aadf34",
            "03d77d1f4ece4889a6a1eca7e2f699d4",
            "57f7a2f83c4a4828937f0ae89200700d",
            "e06fef203bb44b2fb50df6c949c53202",
            "bc3e5079115143c3a83257b9d7503f1d",
            "f5bd635b0a9e4e3caf627264047fabe8",
            "f89fff5045544335ac2b1b52c78c8df8"
          ]
        },
        "id": "JFEBxoVdiNkA",
        "outputId": "c713c005-6536-4b3f-c607-f09a69004dfe"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "  0%|          | 0/8423 [00:00<?, ?it/s]"
            ],
            "application/vnd.jupyter.widget-view+json": {
              "version_major": 2,
              "version_minor": 0,
              "model_id": "a69e26c8b3624d18a4025812cf31bead"
            }
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "print(MORPHEMES)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "2CMlQmDdocG0",
        "outputId": "3285967c-f2c0-4322-d881-0ff79145cce1"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "{'автоионн', 'абсурдны', 'автомотолотере', 'автодорожн', 'абстрагировал', 'автомодельны', 'автогенщик', 'но', 'авиамодел', 'австри', 'аберрационн', 'автогенны', 'аван', 'автоматизирует', 'абитуриент', 'авиаремонтн', 'аберрационны', 'абдукторны', 'аннотировани', 'автозаводск', 'австро', 'абсолютистск', 'автодинно', 'автоподъемник', 'абсорбиру', 'абсорбируемо', 'абордированн', 'абазинско', 'автоводителя', 'абстракционист', 'авиастроительны', 'авизны', 'Авил', 'Авдеевиче', 'автогон', 'автоматизированны', 'авантюристско', 'автобиографичн', 'авиамодельны', 'автоколонн', 'абонируемы', 'автодоени', 'авиат', 'автом', 'абразионны', 'абсурдистско', 'абсорбированны', 'авиастроитель', 'австралопитек', 'автопилот', 'абиогенн', 'щ', 'австрийско', 'автографическо', 'абаканц', 'авитаминоз', 'абстрагировавши', 'авиаопрыскивани', 'абсолютизирующи', 'авиаци', 'авизиру', 'абдукторн', 'автобиографичны', 'автомобиле', 'абелевы', 'абрам', 'Аверьян', 'авиасалон', 'авт', 'авансирую', 'автогр', 'автомати', 'автопоилк', 'абсолютизируем', 'абортированны', 'авиазавод', 'абсолютизировавш', 'автодо', 'автол', 'автозаводско', 'абдукци', 'абиссинц', 'авдот', 'авансировани', 'автоподстройк', 'авиамоторо', 'абсцисс', 'абордирова', 'айнер', 'атк', 'абсолютн', 'автомобили', 'аварц', 'августинце', 'абдикаци', 'Авиньон', 'авианос', 'авансировавши', 'авианосны', 'абляционн', 'аварийны', 'автоматическ', 'автомобилизаци', 'авансирующ', 'автомобильны', 'абличительн', 'автодиспетчер', 'абиссинк', 'автоблокировочн', 'авто', 'авангардистск', 'автоза', 'абонирует', 'автоматически', 'автопокрышк', 'австрийск', 'абиетиново', 'авангардистско', 'абсолютивн', 'абе', 'авиако', 'абиссальн', 'августовско', 'авиаметеостанци', 'авиатранспорт', 'авиакосмическ', 'автоматчиц', 'заци', 'абстиненци', 'абстрактн', 'авгур', 'авантюрны', 'едприяти', 'абор', 'абиотическ', 'Абе', 'абордируемы', 'аббревиатурн', 'автомагистрал', 'аббатски', 'е', 'абордировал', 'автоионны', 'аброгаци', 'абзац', 'авар', 'т', 'авгит', 'ь', 'абразионн', 'автократ', 'авантюристическ', 'автокорреляционн', 'авансов', 'авиахимическ', 'авантюристическо', 'авитаминозн', 'изм', 'автоколлиматор', 'Абиссини', 'автографично', 'аборигенно', 'абортария', 'аварийщик', 'автомототранспорт', 'абортивны', 'авантюристо', 'авиап', 'ладельц', 'авангардны', 'абстракция', 'автоматизировавши', 'абстинентно', 'авианосно', 'авантюрн', 'авансируемы', 'авантюристичн', 'автопо', 'автокатастроф', 'аварк', 'автоприцеп', 'автоклав', 'автодром', 'автоводител', 'автомеханически', 'ов', 'абрисн', 'австрийц', 'авиаспорт', 'аверс', 'авансиру', 'абсурдистски', 'ави', 'ал', 'автожир', 'абиссально', 'авиаракетостроени', 'автономия', 'абсолютизирующе', 'ьн', 'авансировавше', 'автоблокировочны', 'автомото', 'абсолютно', 'абсентеист', 'абиотическо', 'авиатранспортно', 'автоматчице', 'автопр', 'абортивн', 'аберраци', 'ет', 'автографическ', 'абстрагировавш', 'авантюрно', 'Аверьянович', 'держател', 'абхазск', 'автоматичны', 'автобиографично', 'автокаталитическ', 'автомашин', 'аванпорт', 'абсолютированны', 'авиапо', 'автоклавно', 'автоперевозк', 'авиадесант', 'автомоделизм', 'абсолютизирован', 'аварско', 'автономическо', 'автомобилестроительно', 'авиас', 'абсорбирую', 'абажурчик', 'автоматизировавше', 'автомеханическо', 'автометри', 'автогужев', 'автодел', 'абсолютнейш', 'авантюристск', 'авиационны', 'абонируем', 'абстрагирую', 'аббатис', 'абсолютизм', 'автоп', 'автоматичн', 'абазин', 'автобус', 'к', 'авиадвигателя', 'абстинент', 'абстрагированн', 'аварск', 'аберрация', 'автод', 'автоматическо', 'абрикос', 'абсолютист', 'аванпостн', 'абориген', 'Абинск', 'автомодельн', 'автолюбителя', 'августовски', 'автодрезин', 'автодинны', 'авансированно', 'абхазско', 'аблятив', 'авиамотор', 'абрикосов', 'абсолютиз', 'абстракционисто', 'абиссин', 'абонированны', 'абортирован', 'авангардист', 'авиаракетостроительны', 'абортиру', 'авантюристично', 'авиакосмическо', 'авантажн', 'абвер', 'австрий', 'автоген', 'авк', 'абхаз', 'автоплуг', 'Авдоть', 'автомобильчик', 'автономны', 'автоинкрементн', 'авантюристк', 'абонированн', 'абазино', 'Абхази', 'завод', 'автаркически', 'автоматизирующи', 'автопробег', 'авиакомпани', 'абордирующи', 'Август', 'абордирует', 'абстракт', 'австрально', 'абсорбционны', 'автоматизирую', 'абляционны', 'авиабаз', 'абсолютизиру', 'авиадесантно', 'аболици', 'автоморфизм', 'абсорбировавш', 'авиаракетн', 'абдоминальн', 'автокатализ', 'абстракционистск', 'августинц', 'абхазц', 'аболиционист', 'автограф', 'автокинопередвижк', 'авиапутешестви', 'абажуро', 'ази', 'абстрагиру', 'арк', 'енционист', 'автологи', 'авиамодель', 'автоколебательн', 'абр', 'абитуриентско', 'автопластик', 'автодекрементны', 'абиетиновы', 'авиньонско', 'абиссинско', 'автоко', 'аборигенны', 'автоколебательны', 'авансируемо', 'авестийско', 'абсорбирова', 'автоматик', 'абъюраци', 'авиачаст', 'автономист', 'абзацн', 'авиапредприятия', 'автомашинист', 'авианосц', 'авиапутешествия', 'Аверьяновн', 'ами', 'абстрагирует', 'абсорбировавшем', 'австрияк', 'авиаразведк', 'автоди', 'автомотос', 'автомоторн', 'абсцесс', 'абцуг', 'Ави', 'абрис', 'абсолютизировал', 'абхазк', 'аби', 'абиссальны', 'абстрагирова', 'автобиограф', 'автобронетанковы', 'абонирован', 'ент', 'авоськ', 'авиатрасс', 'абрикосово', 'авиапр', 'авиагоризонт', 'автоматизируемы', 'аболиционистско', 'абонементны', 'абст', 'аварце', 'август', 'авиахимически', 'абаз', 'абиогенно', 'абрикосовы', 'абу', 'абстрагирующи', 'автомеханическ', 'авст', 'абстрагированны', 'абонентско', 'авиаподкормк', 'Аверки', 'автодин', 'автомотрис', 'авиа', 'абстрагирующ', 'автоо', 'абсолют', 'абсорбци', 'авансо', 'аварий', 'абстрагируй', 'абонементно', 'авиабомб', 'абоненто', 'ческ', 'автокружк', 'автоматизиру', 'абордирующе', 'вш', 'абордажны', 'автобензин', 'абонентск', 'автарки', 'австралийско', 'абаканск', 'в', 'автоподъёмник', 'автолюбител', 'абазински', 'грузчик', 'автоматизировани', 'авиньонски', 'ик', 'абортированно', 'Авде', 'автоматизируемо', 'аверки', 'авиабензин', 'автобиографическ', 'автокоррекци', 'абштрих', 'автомоторны', 'авиадиспетчер', 'авансовы', 'авиаторски', 'аббревиатурны', 'абониру', 'абсорбер', 'абд', 'абитуриентск', 'авангардн', 'авиастроител', 'щик', 'автономн', 'авиапочт', 'абсурдн', 'абонировавш', 'абсорбировавши', 'авизировавше', 'автов', 'аврал', 'автобронетанков', 'авизировал', 'августин', 'авиатик', 'авиашкол', 'абрек', 'аватар', 'автобронетанково', 'автокефальн', 'аболиционистски', 'автомобиля', 'авестийск', 'автопарк', 'абелево', 'авантажны', 'абрикосны', 'абс', 'австралийце', 'абажуродержателя', 'абляци', 'абсолютизаци', 'автоматн', 'автономическ', 'строени', 'абиетин', 'австромарксизм', 'абрамк', 'автографичны', 'авантюриновы', 'аванпост', 'автокомбинат', 'аванзал', 'авансированны', 'авиахимическо', 'авансцен', 'АвтоВАЗ', 'автоном', 'авансирова', 'автопод', 'автобиографическо', 'автоколлимаци', 'автографичн', 'Аб', 'абсолютивны', 'аббатско', 'авантюризм', 'абхазо', 'автоматизирован', 'автомобилист', 'аврали', 'абордирую', 'абаканско', 'авометр', 'августинско', 'абля', 'Абрамович', 'австралоидн', 'Абрам', 'абазинск', 'авток', 'абсолюци', 'авиадвигателестроительны', 'августейши', 'авральны', 'австралоидно', 'абсолютизирую', 'абсорбирующ', 'абсорбированно', 'Ав', 'авг', 'абонируй', 'евич', 'авиатор', 'автоблокировк', 'авиаполк', 'автодекрементн', 'автократическ', 'авантюрист', 'б', 'абсорбционн', 'абаканце', 'абстрактны', 'автономно', 'авиастроителя', 'автозаправ', 'австралийск', 'гард', 'абитуриентски', 'авиамоделизм', 'Австри', 'автаркическо', 'абсорбировавшим', 'абитуриенто', 'автокран', 'ав', 'авиетк', 'автоматно', 'абонирова', 'автомотошкол', 'автобиография', 'авизирова', 'автокаталитическо', 'абразивн', 'автогидроподъемник', 'автогужевы', 'абсолютны', 'Авдеевн', 'Аве', 'августинск', 'абсорбциометр', 'австриячк', 'аванс', 'абсолютизируемы', 'абсорб', 'абсорбировал', 'авантюринов', 'абрикотин', 'автопоезд', 'онизм', 'н', 'автомолит', 'автократическо', 'авиастроительств', 'або', 'абажур', 'абсолютизировавши', 'аванлож', 'австральны', 'аврор', 'ем', 'аж', 'аббревиаци', 'аванкамер', 'абортирова', 'австрийце', 'авантитул', 'автовладельце', 'автогенератор', 'автодорог', 'вод', 'авантюрин', 'али', 'абсолютированн', 'Аврам', 'автомобилизм', 'Абиджан', 'авария', 'актировк', 'абстрагирован', 'авиз', 'Абрамовн', 'о', 'Абердин', 'автоклавны', 'авен', 'абордиру', 'авиатехник', 'автокорреляционны', 'автоматизм', 'бил', 'абстракционизм', 'абсолютизирует', 'автономически', 'авиамоделист', 'аббревиатур', 'автоматчик', 'абдомен', 'л', 'автоинкрементны', 'авиастроени', 'и', 'аз', 'абдоминальны', 'аббатск', 'авансирован', 'абстрагируемы', 'абиссинск', 'автомобилестроителя', 'абиогенны', 'Аби', 'авиатранспортны', 'автобусн', 'автозаправщик', 'автомагнитол', 'абл', 'австральн', 'авиакатастроф', 'автомобилестроител', 'авансировал', 'августейш', 'авиньонск', 'автогидроподъёмник', 'автозаправочн', 'онн', 'Австр', 'автокол', 'автомотосекци', 'автономи', 'автоб', 'абсолютизированны', 'автог', 'авиалини', 'авиал', 'абракадабр', 'абонирую', 'автогенез', 'абакан', 'аборальн', 'авиапассажир', 'авральн', 'абак', 'августовск', 'автоматизированно', 'абажурно', 'абсорбирован', 'абажурны', 'авиадвигател', 'аванпостны', 'авант', 'абсолютнейши', 'абонемент', 'автокар', 'абазинц', 'автозагрузк', 'абстрагируем', 'аве', 'австр', 'авер', 'абстракци', 'автодорожны', 'абонентны', 'автомобиль', 'я', 'абсурд', 'абонентн', 'авизировавши', 'автомеханик', 'аборальны', 'абордированны', 'абортивно', 'авантюристичны', 'аво', 'автозаправочны', 'автоионизаци', 'авист', 'автоматны', 'аборт', 'абсолютирован', 'абзацны', 'абдуктор', 'абстинентны', 'абсолютистско', 'авиадвигателестроительн', 'австралий', 'автомобильн', 'авиаремонтны', 'авиад', 'авиадесантны', 'абразивны', 'автомо', 'авизн', 'авансирует', 'абсорбирует', 'автобан', 'абстракционистско', 'авлос', 'автолиз', 'абстракционистк', 'лев', 'абордаж', 'австралийц', 'автоответчик', 'абиссински', 'авиарейс', 'абонировавши', 'авиакосмически', 'авр', 'абсурдист', 'авиабилет', 'автомобилисто', 'абонирующи', 'Авксентьев', 'абрамо', 'авиам', 'авраам', 'дакт', 'Абакан', 'абонировал', 'авиационно', 'автоматизирова', 'авиаторско', 'абули', 'автоклуб', 'абрикосно', 'абсорбирующи', 'авиаконструктор', 'абордирован', 'абразионно', 'ск', 'автоматизированн', 'абсорбционно', 'абонирующ', 'авангардно', 'абонент', 'авантюр', 'ксидаци', 'авось', 'абрисны', 'автоинспекци', 'авитаминозны', 'автопере', 'ари', 'аббат', 'авюр', 'авиаотряд', 'авансирующи', 'автоматизировал', 'автопортрет', 'авиаракетны', 'авангардизм', 'Авест', 'автогенн', 'абсорбируемы', 'автовокзал', 'австралоидны', 'абсолютизированн', 'автокефальны', 'автоматизирующ', 'автолитографи', 'ебания', 'авиаракетостроительн', 'автобусны', 'естроени', 'автомат', 'автомобилестроительны', 'авансированн', 'абордируем', 'а', 'абсентеизм', 'абордажн', 'абхазски', 'автоинспектор', 'абсолютизирова', 'аббатств'}\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "rules = {'a': 'b', 'b': 'c', 'c': 'd', 'e': '1'}"
      ],
      "metadata": {
        "id": "ZIKebFG8ocDR"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "input_str = 'a,b,c,egab'"
      ],
      "metadata": {
        "id": "5VlzjWHsocAf"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def apply_rules_too_simple(input_str:str, rules:dict):\n",
        "    while any(ch in rules for ch in input_str):\n",
        "        for k, v in rules.items():\n",
        "            input_str = input_str.replace(k, v)\n",
        "    return input_str"
      ],
      "metadata": {
        "id": "HkxpwRxDob6_"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def apply_rules(input_str:str, rules:dict):\n",
        "    input_str_len = len(input_str)\n",
        "    input_str += ','\n",
        "    while any(input_str[i] in rules\n",
        "              and (i==0 and input_str[i+1] == ','\n",
        "                   or input_str[i-1] == ',' and input_str[i+1] == ',')\n",
        "              for i in range(1, input_str_len+1)):\n",
        "        for k, v in rules.items():\n",
        "            k_index = input_str.find(k)\n",
        "            if (k_index!=-1 and (input_str[k_index+1]==',' and input_str[k_index-1]==',' or input_str[k_index+1]==',' and k_index==0)):\n",
        "                input_str = input_str.replace(k, v, 1)\n",
        "    return input_str[:-1]"
      ],
      "metadata": {
        "id": "u0cN7dmoQxB3"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "apply_rules_too_simple(input_str, rules)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "id": "d92neew1bAOV",
        "outputId": "11f182fc-d58f-4c31-84f0-604c1ce65292"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'d,d,d,1gdd'"
            ],
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            }
          },
          "metadata": {},
          "execution_count": 94
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "apply_rules(input_str, rules)"
      ],
      "metadata": {
        "id": "m9lr1tp9ob4U",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "outputId": "e1198a8c-967e-460b-c68f-a20222ff98b6"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'d,d,d,egab'"
            ],
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            }
          },
          "metadata": {},
          "execution_count": 95
        }
      ]
    }
  ]
}