day1.ipynb

{
 "metadata": {
  "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.6.10-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "source": [
    "Finding two numbers whose sum is 2020\n",
    "- can inputs be negative?\n",
    "- can inputs be the same?\n",
    "\n",
    "sample:"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "514579\n"
     ]
    }
   ],
   "source": [
    "from functools import reduce\n",
    "import import_ipynb\n",
    "import util\n",
    "\n",
    "sample = [1721, 979, 366, 299, 675, 1456]\n",
    "expected = [1721, 299]\n",
    "expected_output = reduce(lambda x, y: x * y, expected)\n",
    "print(expected_output)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "[299, 1721] [1721, 299]\n"
     ]
    }
   ],
   "source": [
    "def find_2_sum(numbers, target):\n",
    "    seen = set()\n",
    "    for n in numbers:\n",
    "        if target - n in seen:\n",
    "            return [n, target - n]\n",
    "        seen.add(n)\n",
    "    return None\n",
    "print(find_2_sum(sample, 2020), expected)"
   ]
  },
  {
   "source": [
    "This runtime is `N` for seeing each number, `O(1)` to add and check the set. So overall `O(N)`"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "299299"
      ]
     },
     "metadata": {},
     "execution_count": 56
    }
   ],
   "source": [
    "from operator import mul\n",
    "from functools import reduce\n",
    "\n",
    "def solution1():\n",
    "    numbers = map(int, next(util.input_reader('day1.input', -1)))\n",
    "    return reduce(mul, find_2_sum(numbers, 2020))\n",
    "    \n",
    "solution1()\n",
    "            "
   ]
  },
  {
   "source": [
    "Part 2 is a 3 sum problem. We'll just cheese by reusing 2Sum"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "[979, 675, 366] 241861950\n"
     ]
    }
   ],
   "source": [
    "def find_3_sum(numbers, target):\n",
    "    for i, n in enumerate(numbers): \n",
    "        if target - n > 0:\n",
    "            two_sum_solution = find_2_sum(numbers[:i] + numbers[i+1:], target - n)\n",
    "            if two_sum_solution is not None:\n",
    "                return [n] + two_sum_solution\n",
    "    return None\n",
    "print(find_3_sum(sample, 2020), reduce(lambda x, y: x*y, find_3_sum(sample, 2020)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "287730716\n"
     ]
    }
   ],
   "source": [
    "import import_ipynb\n",
    "from util import input_reader\n",
    "def solution2():\n",
    "    def process(numbers):\n",
    "        numbers = list(map(int, numbers))\n",
    "        return find_3_sum(numbers, 2020)\n",
    "    print(reduce(lambda x, y: x * y, process(next(input_reader('day1.input', -1)))))\n",
    "solution2()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}