Calculating the Amount of Water to be Trapped on Terrain.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 2,
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "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.7.3"
    },
    "colab": {
      "name": "python-workshop-3(teacher).ipynb",
      "provenance": []
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "## Calculating the Amount of Water to be Trapped on Terrain\r\n",
        "\r\n",
        "\r\n",
        "The purpose of this coding challenge is to write a program that calculates the amount of water that can be contained within the generated holes.\r\n",
        "\r\n",
        "### Learning Outcomes\r\n",
        "\r\n",
        "At the end of this coding challenge, students will be able to;\r\n",
        "\r\n",
        "- analyze a problem, identify, and apply programming knowledge for appropriate solution.\r\n",
        "\r\n",
        "- design, implement `while` loops effectively in Python to solve the given problem.\r\n",
        "\r\n",
        "- control loops effectively by using `if` and `control` statements.\r\n",
        "\r\n",
        "- demonstrate their knowledge of algorithmic design principles by using solving the problem effectively.\r\n",
        "\r\n",
        "### Problem Statement\r\n",
        "\r\n",
        "- Given an array of non-negative integers representing an elevation map as shown below where the width of each bar is 1, compute how much water will be trapped on terrain after raining. To clarify further, the black boxes represents terrain and its height, and the blue boxes represents the water that could be trapped on the terrain.\r\n",
        "\r\n",
        "<center><img src=\"https://raw.githubusercontent.com/andrewfade/myprojects/main/image.png\" /></center>\r\n",
        "\r\n",
        "- User can enter as many numbers as they want to represent elevation of the terrain.\r\n",
        "\r\n",
        "- You can assume all the inputs are valid, thus you don't have to do an input check.\r\n",
        "\r\n",
        "- At the end of the program write a comment that indicates which computational thinking heuristics you have used and how you used them.\r\n",
        "\r\n",
        "- Example of user inputs and respective outputs.\r\n",
        "\r\n",
        "```text\r\n",
        "Inputs\r\n",
        "------------------------------\r\n",
        "Type 'ok' when you are done: 5\r\n",
        "Type 'ok' when you are done: 4\r\n",
        "Type 'ok' when you are done: 5\r\n",
        "Type 'ok' when you are done: ok\r\n",
        "\r\n",
        "Output\r\n",
        "------\r\n",
        "1\r\n",
        "\r\n",
        "Inputs\r\n",
        "------------------------------\r\n",
        "Type 'ok' when you are done: 2\r\n",
        "Type 'ok' when you are done: 1\r\n",
        "Type 'ok' when you are done: 2\r\n",
        "Type 'ok' when you are done: 3\r\n",
        "Type 'ok' when you are done: 2\r\n",
        "Type 'ok' when you are done: 3\r\n",
        "Type 'ok' when you are done: ok\r\n",
        "\r\n",
        "Output\r\n",
        "------\r\n",
        "2\r\n",
        "\r\n",
        "Inputs\r\n",
        "------------------------------\r\n",
        "Type 'ok' when you are done: 6\r\n",
        "Type 'ok' when you are done: 5\r\n",
        "Type 'ok' when you are done: 8\r\n",
        "Type 'ok' when you are done: 9\r\n",
        "Type 'ok' when you are done: 2\r\n",
        "Type 'ok' when you are done: 4\r\n",
        "Type 'ok' when you are done: 3\r\n",
        "Type 'ok' when you are done: 6\r\n",
        "Type 'ok' when you are done: ok\r\n",
        "\r\n",
        "Output\r\n",
        "------\r\n",
        "10\r\n",
        "```"
      ],
      "metadata": {
        "id": "orFavV-SHUE8"
      }
    },
    {
      "cell_type": "markdown",
      "source": [],
      "metadata": {
        "id": "O1-u-UztHZTF"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Solution :"
      ],
      "metadata": {
        "id": "N32-yFxFHUE_"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "source": [
        "# initialize the list of an integer array representing the elevation, and set it to empty\r\n",
        "height = []\r\n",
        "# Unless user types `ok`, get input of numbers from the user\r\n",
        "while True:\r\n",
        "    num = input(\"Type 'ok' when you are done: \")\r\n",
        "    # if the input is not equal to `ok`, add the input number to the height array\r\n",
        "    if num != \"ok\":\r\n",
        "        height.append(int(num))\r\n",
        "    # if the input equals to `ok`, get out of the while loop\r\n",
        "    else:\r\n",
        "        break\r\n",
        "# initialize areas which holds total amount of water to be trapped, and set to 0\r\n",
        "areas = 0\r\n",
        "# initialize maximum left and right, and set to 0\r\n",
        "max_l = max_r = 0\r\n",
        "# initialize left, and set to 0\r\n",
        "l = 0\r\n",
        "# initialize right and set to the last index of the input array\r\n",
        "r = len(height)-1\r\n",
        "# unless the current position of the height on left\r\n",
        "# is not greater than the one on right, run the loop\r\n",
        "while l < r:\r\n",
        "    # if the current position on left is lower than the right,\r\n",
        "    # max level on left determines the amount of water to be trapped.\r\n",
        "    if height[l] < height[r]:\r\n",
        "        # if the current height on left is greater than max height on left\r\n",
        "        # then the water not to be trapped, and set the max height to the new max\r\n",
        "        if height[l] > max_l:\r\n",
        "            max_l = height[l]\r\n",
        "        # otherwise, add the amount of water to be trapped.\r\n",
        "        else:\r\n",
        "            areas += max_l - height[l]\r\n",
        "        # increase current position on left by one\r\n",
        "        l += 1\r\n",
        "    # if the current position on left is higher than the right,\r\n",
        "    # max level on right determines the amount of water to be trapped.\r\n",
        "    else:\r\n",
        "        # if the current height on right is greater than max height on height\r\n",
        "        # then the water not to be trapped, and set the max height to the new max\r\n",
        "        if height[r] > max_r:\r\n",
        "            max_r = height[r]\r\n",
        "        # otherwise, add the amount of water to be trapped.\r\n",
        "        else:\r\n",
        "            areas += max_r - height[r]\r\n",
        "        # decrease current position on right by one\r\n",
        "        r -= 1\r\n",
        "# print the amount of water to be trapped\r\n",
        "print(\"\\nRain-trapped area : \", areas)"
      ],
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Type 'ok' when you are done: 4\n",
            "Type 'ok' when you are done: 3\n",
            "Type 'ok' when you are done: 6\n",
            "Type 'ok' when you are done: 0\n",
            "Type 'ok' when you are done: 1\n",
            "Type 'ok' when you are done: 0\n",
            "Type 'ok' when you are done: 2\n",
            "Type 'ok' when you are done: ok\n",
            "\n",
            "Rain-trapped area :  6\n"
          ]
        }
      ],
      "metadata": {
        "id": "LJKRDS_WHUFC",
        "outputId": "214099ed-4ae1-4992-e1ab-ca2aa5e41e0e"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "source": [],
      "outputs": [],
      "metadata": {
        "id": "SS8rtjG7HUFE"
      }
    }
  ]
}