delta_tester.ipynb

delta_tester.ipynb

{
  "cells": [
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# A Notebook to Demonstrate my Understanding of Delta Testing"
    },
    {
      "metadata": {
        "lines_to_next_cell": 1,
        "trusted": true
      },
      "cell_type": "code",
      "source": "def has_star(s):\n    \"\"\"returns true if test fails\"\"\"\n    ret = \"*\" in s\n    print(\"FAIL\" if ret else \"PASS\",\"\\t\", s)\n    return ret",
      "execution_count": 1,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "def has_gh(s):\n    \"\"\"returns true if test fails\"\"\"\n    ret = \"gh\" in s\n    print(\"FAIL\" if ret else \"PASS\",\"\\t\", s)\n    return ret",
      "execution_count": 2,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "test=has_star",
      "execution_count": 3,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "NOT_FOUND = -1",
      "execution_count": 4,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "def sdiv(s, nparts):\n    plen = len(s)//nparts\n    assert plen*nparts==len(s)\n    divstart = map(lambda x: x * plen, range(nparts))\n    divend   = map(lambda x: (x+1) * plen, range(nparts))\n    deltas = []\n    nablas = []\n    for a,b in zip(divstart, divend):\n        deltas.append(s[a:b])\n        nablas.append(s[0:a] + s[b:])\n    return deltas, nablas",
      "execution_count": 5,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "def dtest(s, test, n=2):\n    \"\"\"\n    finds minimal test input that results in\n    function test returning true\n    (fails)\n    \"\"\"\n    deltas, nablas = sdiv(s, n)\n    for i in range(len(deltas)):\n        if test(deltas[i]):\n            if len(deltas[i]) == 1:\n                return deltas[i]\n            else:\n                further_split = dtest(deltas[i], test)\n                if further_split == NOT_FOUND:\n                    return deltas[i]\n                else:\n                    return further_split\n        elif test(nablas[i]):\n            return dtest(nablas[i], test, n-1)\n    \n    if 2*n > len(s):\n        return NOT_FOUND\n    else:\n        return dtest(s, test, 2*n)",
      "execution_count": 6,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "dtest(\"abcdef*h\", has_star)",
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "text": "PASS \t abcd\nFAIL \t ef*h\nFAIL \t ef*h\nPASS \t ef\nFAIL \t *h\nFAIL \t *h\nFAIL \t *\n",
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "execution_count": 7,
          "data": {
            "text/plain": "'*'"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "dtest(\"abcdefgh\", has_gh)",
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "text": "PASS \t abcd\nFAIL \t efgh\nFAIL \t efgh\nPASS \t ef\nFAIL \t gh\nFAIL \t gh\nPASS \t g\nPASS \t h\nPASS \t h\nPASS \t g\n",
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "execution_count": 8,
          "data": {
            "text/plain": "'gh'"
          },
          "metadata": {}
        }
      ]
    }
  ],
  "metadata": {
    "jupytext": {
      "cell_metadata_filter": "-all",
      "notebook_metadata_filter": "-all",
      "text_representation": {
        "extension": ".py",
        "format_name": "light"
      }
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3",
      "language": "python"
    },
    "language_info": {
      "name": "python",
      "version": "3.7.5",
      "mimetype": "text/x-python",
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "pygments_lexer": "ipython3",
      "nbconvert_exporter": "python",
      "file_extension": ".py"
    },
    "toc": {
      "nav_menu": {},
      "number_sections": true,
      "sideBar": true,
      "skip_h1_title": false,
      "base_numbering": 1,
      "title_cell": "Table of Contents",
      "title_sidebar": "Contents",
      "toc_cell": false,
      "toc_position": {},
      "toc_section_display": true,
      "toc_window_display": false
    },
    "gist": {
      "id": "",
      "data": {
        "description": "delta_tester.ipynb",
        "public": true
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 4
}