{
 "metadata": {
  "name": "",
  "signature": "sha256:3889b568d4c64c981644c595418fd02cb1cef5f6f0b20c4279a9d722fb0542f7"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "See https://blog.svpino.com/2015/05/07/five-programming-problems-every-software-engineer-should-be-able-to-solve-in-less-than-1-hour"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Problem 1\n",
      "Write three functions that compute the sum of the numbers in a given list using a for-loop, a while-loop, and recursion."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def sum_for(nums):\n",
      "    sum = 0\n",
      "    for n in nums:\n",
      "        sum += n\n",
      "        \n",
      "    return sum\n",
      "\n",
      "def sum_while(nums):\n",
      "    sum = i = 0\n",
      "    while i < len(nums):\n",
      "        sum += nums[i]\n",
      "        i += 1\n",
      "    \n",
      "    return sum\n",
      "\n",
      "def sum_rec(nums):\n",
      "    if len(nums) is 0:\n",
      "        return 0\n",
      "    \n",
      "    return nums[0] + sum_rec(nums[1:])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 16
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "nums = [1, 2, 3]\n",
      "\n",
      "print(sum_for(nums))\n",
      "print(sum_while(nums))\n",
      "print(sum_rec(nums))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "6\n",
        "6\n",
        "6\n"
       ]
      }
     ],
     "prompt_number": 17
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Problem 2\n",
      "Write a function that combines two lists by alternatingly taking elements. For example: given the two lists [a, b, c] and [1, 2, 3], the function should return [a, 1, b, 2, c, 3]."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def combine(l1, l2):\n",
      "    return [item for pair in zip(l1, l2) for item in pair]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 35
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "l1 = [1, 2, 3]\n",
      "l2 = [4, 5, 6]\n",
      "\n",
      "print(combine(l1, l2))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[1, 4, 2, 5, 3, 6]\n"
       ]
      }
     ],
     "prompt_number": 36
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Problem 3\n",
      "Write a function that computes the list of the first 100 Fibonacci numbers. By definition, the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two. As an example, here are the first 10 Fibonnaci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, and 34."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def fibo(n):\n",
      "    f = fibo_gen()\n",
      "    return [next(f) for _ in range(n)]\n",
      "\n",
      "def fibo_gen():\n",
      "    a, b = 0, 1\n",
      "    yield a\n",
      "    yield b\n",
      "    while True:\n",
      "        yield a + b\n",
      "        a, b = b, a + b"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 59
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "fibo(100)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 61,
       "text": [
        "[0,\n",
        " 1,\n",
        " 1,\n",
        " 2,\n",
        " 3,\n",
        " 5,\n",
        " 8,\n",
        " 13,\n",
        " 21,\n",
        " 34,\n",
        " 55,\n",
        " 89,\n",
        " 144,\n",
        " 233,\n",
        " 377,\n",
        " 610,\n",
        " 987,\n",
        " 1597,\n",
        " 2584,\n",
        " 4181,\n",
        " 6765,\n",
        " 10946,\n",
        " 17711,\n",
        " 28657,\n",
        " 46368,\n",
        " 75025,\n",
        " 121393,\n",
        " 196418,\n",
        " 317811,\n",
        " 514229,\n",
        " 832040,\n",
        " 1346269,\n",
        " 2178309,\n",
        " 3524578,\n",
        " 5702887,\n",
        " 9227465,\n",
        " 14930352,\n",
        " 24157817,\n",
        " 39088169,\n",
        " 63245986,\n",
        " 102334155,\n",
        " 165580141,\n",
        " 267914296,\n",
        " 433494437,\n",
        " 701408733,\n",
        " 1134903170,\n",
        " 1836311903,\n",
        " 2971215073,\n",
        " 4807526976,\n",
        " 7778742049,\n",
        " 12586269025,\n",
        " 20365011074,\n",
        " 32951280099,\n",
        " 53316291173,\n",
        " 86267571272,\n",
        " 139583862445,\n",
        " 225851433717,\n",
        " 365435296162,\n",
        " 591286729879,\n",
        " 956722026041,\n",
        " 1548008755920,\n",
        " 2504730781961,\n",
        " 4052739537881,\n",
        " 6557470319842,\n",
        " 10610209857723,\n",
        " 17167680177565,\n",
        " 27777890035288,\n",
        " 44945570212853,\n",
        " 72723460248141,\n",
        " 117669030460994,\n",
        " 190392490709135,\n",
        " 308061521170129,\n",
        " 498454011879264,\n",
        " 806515533049393,\n",
        " 1304969544928657,\n",
        " 2111485077978050,\n",
        " 3416454622906707,\n",
        " 5527939700884757,\n",
        " 8944394323791464,\n",
        " 14472334024676221,\n",
        " 23416728348467685,\n",
        " 37889062373143906,\n",
        " 61305790721611591,\n",
        " 99194853094755497,\n",
        " 160500643816367088,\n",
        " 259695496911122585,\n",
        " 420196140727489673,\n",
        " 679891637638612258,\n",
        " 1100087778366101931,\n",
        " 1779979416004714189,\n",
        " 2880067194370816120,\n",
        " 4660046610375530309,\n",
        " 7540113804746346429,\n",
        " 12200160415121876738,\n",
        " 19740274219868223167,\n",
        " 31940434634990099905,\n",
        " 51680708854858323072,\n",
        " 83621143489848422977,\n",
        " 135301852344706746049,\n",
        " 218922995834555169026]"
       ]
      }
     ],
     "prompt_number": 61
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Problem 4\n",
      "Write a function that given a list of non negative integers, arranges them such that they form the largest possible number. For example, given [50, 2, 1, 9], the largest formed number is 95021."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def largest_from(nums):\n",
      "    from functools import cmp_to_key, reduce\n",
      "    def compare(x, y):\n",
      "        if x == y:\n",
      "            return 0\n",
      "        sx, sy = str(x), str(y)  # string representations for doing stuff\n",
      "        l = min(len(sx), len(sy))       # numer of digits that both numbers have\n",
      "        \n",
      "        # compare the number of digits that are in both numbers\n",
      "        for i in range(l):  \n",
      "            if(sx[i] < sy[i]):\n",
      "                return 1\n",
      "            if(sx[i] > sy[i]):\n",
      "                return -1\n",
      "            \n",
      "        # if all digits match, compare the next digit in the bigger number to the first digit in the smaller number\n",
      "        # TODO: make sure all return values are right\n",
      "        if x > y:\n",
      "            if sx[l] > sy[0]:\n",
      "                return -1\n",
      "            if sx[l] < sy[0]:\n",
      "                return 1\n",
      "        if y > x:\n",
      "            if sy[l] > sx[0]:\n",
      "                return 1\n",
      "            if sy[l] < sx[0]:\n",
      "                return -1\n",
      "        \n",
      "    sorted_nums = sorted(nums, key=cmp_to_key(compare))\n",
      "    return reduce(lambda l, r: l + str(r), sorted_nums, \"\")\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 122
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print(largest_from([50, 2, 1, 9]))\n",
      "print(largest_from([4, 50, 5]))\n",
      "print(largest_from([4, 56, 5]))\n",
      "print(largest_from([4, 40, 5]))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "95021\n",
        "5504\n",
        "5654\n",
        "5440\n"
       ]
      }
     ],
     "prompt_number": 123
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Problem 5\n",
      "Write a program that outputs all possibilities to put + or - or nothing between the numbers 1, 2, ..., 9 (in this order) such that the result is always 100. For example: 1 + 2 + 34 \u2013 5 + 67 \u2013 8 + 9 = 100."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from itertools import product\n",
      "values = list(map(str, range(1, 9)))\n",
      "for p in product(['', ' + ', ' - '], repeat=8):\n",
      "    sumText = reduce(lambda l, r: l + r[0] + r[1], zip(values, p), '') + '9'\n",
      "    if eval(sumText) == 100:\n",
      "        print(sumText)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "123 + 45 - 67 + 8 - 9\n",
        "123 + 4 - 5 + 67 - 89\n",
        "123 - 45 - 67 + 89\n",
        "123 - 4 - 5 - 6 - 7 + 8 - 9\n",
        "12 + 3 + 4 + 5 - 6 - 7 + 89\n",
        "12 + 3 - 4 + 5 + 67 + 8 + 9\n",
        "12 - 3 - 4 + 5 - 6 + 7 + 89"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "1 + 23 - 4 + 56 + 7 + 8 + 9\n",
        "1 + 23 - 4 + 5 + 6 + 78 - 9\n",
        "1 + 2 + 34 - 5 + 67 - 8 + 9\n",
        "1 + 2 + 3 - 4 + 5 + 6 + 78 + 9"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 184
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}