FIBD-Mortal_Fibonacci_rabbits.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Mortal Fibonacci rabbits, from [rosalind.info](http://rosalind.info/)\n",
    "\n",
    "(text copied from http://rosalind.info/problems/fibd/)\n",
    "\n",
    "> **Problem**  \n",
    "> Recall the definition of the Fibonacci numbers from “Rabbits and Recurrence Relations”, which followed the recurrence relation Fn=Fn−1+Fn−2\n",
    "> and assumed that each pair of rabbits reaches maturity in one month and produces a single pair of offspring (one male, one female) each subsequent month.\n",
    ">\n",
    "> Our aim is to somehow modify this recurrence relation to achieve a dynamic programming solution in the case that all rabbits die out after a fixed number of months. See Figure 4 for a depiction of a rabbit tree in which rabbits live for three months (meaning that they reproduce only twice before dying).\n",
    ">\n",
    ">   **Given**: Positive integers n≤100 and m≤20\n",
    ">\n",
    ">   **Return**: The total number of pairs of rabbits that will remain after the n-th month if all rabbits live for m months.\n",
    ">\n",
    "> Sample Dataset\n",
    ">\n",
    "> `6 3`\n",
    ">\n",
    "> Sample Output\n",
    ">\n",
    "> `4`\n",
    "\n",
    "[Figure 4: visualisation of the example numbers](http://rosalind.info/media/problems/fibd/mortal_rabbit_tree.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## My interpretation/reasoning\n",
    "\n",
    "1. The _input_ will be a number `n` (number of months the 'experiment' lasts), and a number `m` (number of months after which a rabbit dies).\n",
    "\n",
    "2. You start with one pair of rabbits.\n",
    "\n",
    "3. The rabbits mature after a month, produce offspring, live another month, producing offspring again, and then they die.\n",
    "  - Each rabbit pair can produce two pairs of offspring. \n",
    "  - Rabbits in this model have three (3) life stages: juvenile, adult 1 and adult 2. Both adult stages produce offspring. Adult 2 dies after doing so.\n",
    "  - Note that the number of life stages is equal to `m`!\n",
    "  \n",
    "Let's try a bit of code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "From file data/Example_mortal_Fibonacci_rabbits.txt I have read the following data:\n",
      "n = 6\tm = 3\n",
      "\n",
      "Therefore, rabbits have life stages: [1, 2, 3]\n",
      "and the experiment lasts for 6 months.\n",
      "The starting population is 1 pair(s) of rabbits.\n",
      "---\n",
      "At the start of the experiment, the rabbit dictionary is like:\n",
      "{1: 1, 2: 0, 3: 0}\n",
      "---\n",
      "It is now month: 1\n",
      "0 new rabbit pairs are born\n",
      "0 rabbit pairs die (of age)\n",
      "At the end of the month, we have this age distribution:\n",
      "{2: 1, 3: 0, 1: 0}\n",
      "\n",
      "It is now month: 2\n",
      "1 new rabbit pairs are born\n",
      "0 rabbit pairs die (of age)\n",
      "At the end of the month, we have this age distribution:\n",
      "{2: 0, 3: 1, 1: 1}\n",
      "\n",
      "It is now month: 3\n",
      "1 new rabbit pairs are born\n",
      "1 rabbit pairs die (of age)\n",
      "At the end of the month, we have this age distribution:\n",
      "{2: 1, 3: 0, 1: 1}\n",
      "\n",
      "It is now month: 4\n",
      "1 new rabbit pairs are born\n",
      "0 rabbit pairs die (of age)\n",
      "At the end of the month, we have this age distribution:\n",
      "{2: 1, 3: 1, 1: 1}\n",
      "\n",
      "It is now month: 5\n",
      "2 new rabbit pairs are born\n",
      "1 rabbit pairs die (of age)\n",
      "At the end of the month, we have this age distribution:\n",
      "{2: 1, 3: 1, 1: 2}\n",
      "\n",
      "\n",
      "---\n",
      "Finally, after 6 months, we end up with 4 rabbit pairs\n"
     ]
    }
   ],
   "source": [
    "testing = True #Am I just testing?\n",
    "\n",
    "# Step 1: Load the input data\n",
    "\n",
    "if testing:\n",
    "    #If testing, use my own example file\n",
    "    input_file = \"data/Example_mortal_Fibonacci_rabbits.txt\"\n",
    "else:\n",
    "    #Or else, use the real exercise file\n",
    "    input_file = \"data/Mortal_Fibonacci_rabbits.txt\"\n",
    "\n",
    "with open(input_file, 'r') as infile:\n",
    "    #Read the data from the file\n",
    "    input_data = infile.readline()\n",
    "    \n",
    "#And extract the required parameters\n",
    "n = int(input_data.split()[0]) #number of months to run experiment\n",
    "m = int(input_data.split()[1]) #maximum age of rabbits\n",
    "\n",
    "print(\"From file %s I have read the following data:\" % input_file)\n",
    "print(\"n = %s\\tm = %s\\n\" % (n, m))\n",
    "\n",
    "# Step 2: Specify the model\n",
    "\n",
    "life_stages = range(1,m+1) #for easier reading: use 1-based counting\n",
    "\n",
    "print(\"Therefore, rabbits have life stages: %s\" % list(life_stages))\n",
    "print(\"and the experiment lasts for %i months.\" % n)\n",
    "\n",
    "start_population = 1 #we start with one pair\n",
    "\n",
    "print(\"The starting population is %i pair(s) of rabbits.\\n---\" % start_population)\n",
    "\n",
    "rabbit_dict = {1: start_population} #in life_stage 1 there is now 1 rabbit pair\n",
    "\n",
    "#Fill up the dictionary with 0 for each other stage\n",
    "for stage in life_stages:\n",
    "    if stage != 1:\n",
    "        rabbit_dict[stage] = 0\n",
    "    else:\n",
    "        pass\n",
    "\n",
    "aging_dict = {} #create a copy to move aging rabbits outside the original dictionary\n",
    "\n",
    "print(\"At the start of the experiment, the rabbit dictionary is like:\\n%s\\n---\" % rabbit_dict)\n",
    "\n",
    "for month in range(1, n):\n",
    "    print(\"It is now month: %i\" % month)\n",
    "    #Three things happen each month:\n",
    "    # 1. rabbits in life stages > 1 reproduce\n",
    "    newborns = 0\n",
    "    for stage in rabbit_dict.keys():\n",
    "        if stage > 1:\n",
    "            #past stage 1 are adult, which reproduce:\n",
    "            newborns += rabbit_dict[stage]\n",
    "        else:\n",
    "            #else they are juveniles and don't reproduce\n",
    "            pass\n",
    "        \n",
    "    print(\"%i new rabbit pairs are born\" % newborns)\n",
    "    \n",
    "    # 2. rabbits in the last life stage (m) die\n",
    "    print(\"%i rabbit pairs die (of age)\" % rabbit_dict[m])\n",
    "    rabbit_dict[m] = 0\n",
    "    # 3. all remaining rabbits move to the next stage\n",
    "    for stage in rabbit_dict.keys():\n",
    "        if stage < m:\n",
    "        #Only rabbits of stages before the latest age\n",
    "            aging_dict[stage + 1] = rabbit_dict[stage]\n",
    "        else:\n",
    "        #Others don't exist\n",
    "            pass        \n",
    "    \n",
    "    rabbit_dict = aging_dict.copy()\n",
    "    #Only add newborns to the dictionary after all the \n",
    "    # already existing rabbits have grown to the next stage.\n",
    "    rabbit_dict[1] = newborns\n",
    "    print(\"At the end of the month, we have this age distribution:\\n%s\\n\" % rabbit_dict)\n",
    "    \n",
    "\n",
    "print(\"\\n---\\nFinally, after %i months, we end up with %i rabbit pairs\" % (n, sum(rabbit_dict.values())))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implement as a function\n",
    "\n",
    "The experiment was a success. The loose pieces of code seem to work as intended.\n",
    "\n",
    "Now let's put all of that code into a function that does all the work:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def run_experiment(n, m, start=1, testing=False):\n",
    "    \"\"\"\n",
    "    Run the \"Mortal_Fibonacci_rabbits\" algorithm,\n",
    "    taking as inputs a value for:\n",
    "    n (int; number of months to run for)\n",
    "    m (int; maximum life span of rabbits)\n",
    "    start (int; number of rabbit pairs to start with;\n",
    "            optional, default = 1)\n",
    "    testing (bool; whether or not you are testing:\n",
    "             enables printing at each step, default = False)\n",
    "    \"\"\"\n",
    "    #From the given m, infer all the life stages:\n",
    "    life_stages = range(1,m+1)\n",
    "    \n",
    "    #Set the starting condition in a dictionary:\n",
    "    rabbit_dict = {1: start} #in life_stage 1 there is now 1 rabbit pair\n",
    "    \n",
    "    #Fill up the dictionary with 0 for each other stage\n",
    "    for stage in life_stages:\n",
    "        if stage != 1:\n",
    "            rabbit_dict[stage] = 0\n",
    "        else:\n",
    "            pass\n",
    "\n",
    "    aging_dict = {} #create a copy to move aging rabbits outside the original dictionary\n",
    "    #This prevents errors in changing the dictionary while reading it\n",
    "    \n",
    "    #Now start the calculations for the experiment:\n",
    "    for month in range(1, n):\n",
    "        if testing:\n",
    "            print(\"It is now month: %i\" % month)\n",
    "            \n",
    "        #Three things happen each month:\n",
    "        # 1. rabbits in life stages > 1 reproduce\n",
    "        newborns = 0\n",
    "        for stage in rabbit_dict.keys():\n",
    "            if stage > 1:\n",
    "                #past stage 1 are adult, which reproduce:\n",
    "                newborns += rabbit_dict[stage]\n",
    "            else:\n",
    "                #else they are juveniles and don't reproduce\n",
    "                pass\n",
    "        \n",
    "        if testing:\n",
    "            print(\"%i new rabbit pairs are born\" % newborns)\n",
    "\n",
    "        # 2. rabbits in the last life stage (m) die\n",
    "        if testing:\n",
    "            print(\"%i rabbit pairs die (of age)\" % rabbit_dict[m])\n",
    "            \n",
    "        rabbit_dict[m] = 0\n",
    "        \n",
    "        # 3. all remaining rabbits move to the next stage\n",
    "        for stage in rabbit_dict.keys():\n",
    "            if stage < m:\n",
    "            #Only rabbits of stages before the latest age\n",
    "                aging_dict[stage + 1] = rabbit_dict[stage]\n",
    "            else:\n",
    "            #Others don't exist\n",
    "                pass        \n",
    "\n",
    "        rabbit_dict = aging_dict.copy()\n",
    "        #Only add newborns to the dictionary after all the \n",
    "        # already existing rabbits have grown to the next stage.\n",
    "        rabbit_dict[1] = newborns\n",
    "        \n",
    "        if testing:\n",
    "            print(\"At the end of the month, we have this age distribution:\\n%s\\n\" % rabbit_dict)\n",
    "            print(\"\\n---\\nFinally, after %i months, we end up with %i rabbit pairs\" % (n, sum(rabbit_dict.values())))\n",
    "    \n",
    "    return(sum(rabbit_dict.values()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "It is now month: 1\n",
      "0 new rabbit pairs are born\n",
      "0 rabbit pairs die (of age)\n",
      "At the end of the month, we have this age distribution:\n",
      "{2: 1, 3: 0, 1: 0}\n",
      "\n",
      "\n",
      "---\n",
      "Finally, after 6 months, we end up with 1 rabbit pairs\n",
      "It is now month: 2\n",
      "1 new rabbit pairs are born\n",
      "0 rabbit pairs die (of age)\n",
      "At the end of the month, we have this age distribution:\n",
      "{2: 0, 3: 1, 1: 1}\n",
      "\n",
      "\n",
      "---\n",
      "Finally, after 6 months, we end up with 2 rabbit pairs\n",
      "It is now month: 3\n",
      "1 new rabbit pairs are born\n",
      "1 rabbit pairs die (of age)\n",
      "At the end of the month, we have this age distribution:\n",
      "{2: 1, 3: 0, 1: 1}\n",
      "\n",
      "\n",
      "---\n",
      "Finally, after 6 months, we end up with 2 rabbit pairs\n",
      "It is now month: 4\n",
      "1 new rabbit pairs are born\n",
      "0 rabbit pairs die (of age)\n",
      "At the end of the month, we have this age distribution:\n",
      "{2: 1, 3: 1, 1: 1}\n",
      "\n",
      "\n",
      "---\n",
      "Finally, after 6 months, we end up with 3 rabbit pairs\n",
      "It is now month: 5\n",
      "2 new rabbit pairs are born\n",
      "1 rabbit pairs die (of age)\n",
      "At the end of the month, we have this age distribution:\n",
      "{2: 1, 3: 1, 1: 2}\n",
      "\n",
      "\n",
      "---\n",
      "Finally, after 6 months, we end up with 4 rabbit pairs\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "#Test run the new function:\n",
    "print(run_experiment(6, 3, 1, True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Perform tests with other starting numbers\n",
    "\n",
    "The function seems to work well for the numbers in the example, but how well does it work with other values for n and m?\n",
    "(Remember: the exercise states that n≤100 and m≤20.)\n",
    "\n",
    "Let's generate some random pairs of n and m values and test the function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n = 5, m = 2\n",
      "1\n",
      "n = 17, m = 19\n",
      "1597\n",
      "n = 40, m = 2\n",
      "1\n",
      "n = 44, m = 15\n",
      "694337165\n",
      "n = 24, m = 2\n",
      "1\n",
      "n = 31, m = 5\n",
      "319243\n",
      "n = 56, m = 13\n",
      "217250817514\n",
      "n = 99, m = 3\n",
      "888855064897\n",
      "n = 11, m = 14\n",
      "89\n",
      "n = 65, m = 9\n",
      "11995668815278\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "#Run ten tests:\n",
    "for test in range(10):\n",
    "    n = random.randint(1,101)\n",
    "    m = random.randint(1,21)\n",
    "    print(\"n = %i, m = %i\" % (n, m))\n",
    "    print(run_experiment(n = n, m = m))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that seems to work fine. It looks like both n and m need to be big to produce really big results. If either the experiment runs for few months (n is small), or the rabbits die young (m is small), the final result will not be very big. With high values for both (e.g. n = 56 and m = 13) the population of rabbits will grow in the billions (217,250,817,514).\n",
    "\n",
    "---\n",
    "\n",
    "## Download the dataset and do the actual exercise\n",
    "\n",
    "I will now download the file from Rosalind.info, read the numbers into this notebook and calculate the number of rabbit pairs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "From file data/Mortal_Fibonacci_rabbits.txt I have read the following data:\n",
      "n = 89\tm = 18\n",
      "\n",
      "1769967188277700563\n"
     ]
    }
   ],
   "source": [
    "#First rewrite the data import lines to a function:\n",
    "def read_values_from_file(input_file, debug = True):\n",
    "    \"\"\"\n",
    "    Read n and m values from a text file,\n",
    "    assuming the file only contains two numbers\n",
    "    separated by a space. E.g.:\n",
    "    6 3\n",
    "    \n",
    "    input_file (str; path to and name of the file)\n",
    "    debug (bool; print file name and values?)\n",
    "    \"\"\"\n",
    "    with open(input_file, 'r') as infile:\n",
    "        #Read the data from the file\n",
    "        input_data = infile.readline()\n",
    "\n",
    "    #And extract the required parameters\n",
    "    n = int(input_data.split()[0]) #number of months to run experiment\n",
    "    m = int(input_data.split()[1]) #maximum age of rabbits\n",
    "    \n",
    "    if debug:\n",
    "        print(\"From file %s I have read the following data:\" % input_file)\n",
    "        print(\"n = %s\\tm = %s\\n\" % (n, m))\n",
    "        \n",
    "    return(n, m)\n",
    "\n",
    "#Then load the data by using the function\n",
    "n, m = read_values_from_file(\"data/Mortal_Fibonacci_rabbits.txt\")\n",
    "\n",
    "#And run the experiment\n",
    "print(run_experiment(n, m))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Success!!\n",
    "\n",
    "I uploaded the result and passed the exercise!\n",
    "I also saved this notebook as python script and uploaded it too."
   ]
  }
 ],
 "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.8.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}