3_List_Of_Ints.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# find the highest product\n",
    "# list will have at least 3 \n",
    "# should work with negatives\n",
    "\n",
    "test_1 = [-10, -10, 3] # expect 300\n",
    "test_2 = [-10, 6, 6, 9] # expect 324\n",
    "test_3 = [15, 15, -15, 5] # expect 1125\n",
    "test_4 = [5, 6, 8, 4, 3, 1, 0] # expect 240\n",
    "test_5 = [-12, -12, -13, -2, -5, -9] # expect -90\n",
    "\n",
    "tests = [test_1, test_2, test_3, test_4, test_5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from random import randrange\n",
    "\n",
    "# generate random tests to the function, for potentially missed cases. \n",
    "def get_random_tests(num):\n",
    "    tests = []\n",
    "    for i in range(num):\n",
    "        list_length = randrange(16)\n",
    "        while list_length < 3:\n",
    "            list_length = randrange(16)\n",
    "        new_test = []\n",
    "        for j in range(list_length):\n",
    "            new_test.append(randrange(-16, 16))\n",
    "            \n",
    "        tests.append(new_test)\n",
    "    return tests\n",
    "    \n",
    "def run_tests(func, tests):\n",
    "    for test in tests:\n",
    "        try:\n",
    "            func(test)\n",
    "        except IndexError as error:\n",
    "            print(error)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# brutish force approach\n",
    "\n",
    "def max_three_product_brute(numbers):\n",
    "    if len(numbers) < 3:\n",
    "        raise IndexError(\"Index Error: There are {0} items in the list, when a minimum of 3 are expected.\".format(len(numbers)))\n",
    "    max_product = numbers[0] * numbers[1] * numbers[2]\n",
    "    \n",
    "    leng = len(numbers)\n",
    "    for number1 in range(leng):\n",
    "        if(number1 + 2 <= leng):\n",
    "            for number2 in range(number1 + 1, leng):\n",
    "                if(number2 + 1 <= leng):\n",
    "                    for number3 in range(number2 + 1, leng):\n",
    "                        current_product = numbers[number1] * numbers[number2] * numbers[number3]\n",
    "                        if(max_product < current_product):\n",
    "                            max_product = current_product\n",
    "                        \n",
    "                \n",
    "    return max_product         \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "300\n",
      "324\n",
      "1125\n",
      "240\n",
      "-90\n",
      "300\n"
     ]
    }
   ],
   "source": [
    "# passes basic tests\n",
    "for test in tests:\n",
    "    print(max_three_product_brute(test))\n",
    "    \n",
    "print(max_three_product_brute([-10,-10,1,3,2] ))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 205,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "random_tests = get_random_tests(5000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 181,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def max_three_product_optimal(numbers):\n",
    "    if len(numbers) < 3:\n",
    "        raise IndexError(\"Index Error: There are {0} items in the list, when a minimum of 3 are expected.\".format(len(numbers)))\n",
    "    max_product = numbers[0] * numbers[1] * numbers[2]\n",
    "    \n",
    "    highest2 = lowest2 = numbers[0] * numbers[1]\n",
    "    highest = max(numbers[0], numbers[1])\n",
    "    lowest = min(numbers[0], numbers[1])\n",
    "    \n",
    "    leng = len(numbers)\n",
    "    for number in range(2, leng):\n",
    "\n",
    "        current_high_max = numbers[number] * highest2\n",
    "        current_low_max = numbers[number] * lowest2\n",
    "\n",
    "        curr_max = max(current_high_max, current_low_max)\n",
    "        if curr_max > max_product:\n",
    "            max_product = curr_max\n",
    "\n",
    "        current_high_2 = highest * numbers[number]\n",
    "        current_low_2 = lowest * numbers[number]\n",
    "\n",
    "        curr_max_2 = max(current_high_2, current_low_2)\n",
    "        curr_low_2 = min(current_high_2, current_low_2)\n",
    "        \n",
    "        if curr_max_2 > highest2:\n",
    "            highest2 = curr_max_2  \n",
    "        if highest < numbers[number]:\n",
    "            highest = numbers[number]\n",
    "            \n",
    "        if curr_low_2 < lowest2:\n",
    "            lowest2 = curr_low_2\n",
    "        if lowest > numbers[number]:\n",
    "            lowest = numbers[number]\n",
    "            \n",
    "               \n",
    "    return max_product  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "300\n",
      "324\n",
      "1125\n",
      "240\n",
      "-90\n"
     ]
    }
   ],
   "source": [
    "for test in tests:\n",
    "    print(max_three_product_optimal(test))    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 207,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "brutish\n",
      "1 loop, best of 3: 195 ms per loop\n",
      "optomized\n",
      "10 loops, best of 3: 40.4 ms per loop\n"
     ]
    }
   ],
   "source": [
    "print(\"brutish\")\n",
    "%timeit run_tests(max_three_product_brute, random_tests)\n",
    "\n",
    "print(\"optomized\")\n",
    "%timeit run_tests(max_three_product_optimal, random_tests)\n",
    "\n",
    "# optimized considerably faster. \n",
    "# Tested optimized vs. solution, consistently faster, seems to scale better!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}