challenges

solutions.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def braces(values):\n",
    "    def solve(brace_string):\n",
    "        closing_pairs = {\n",
    "            '(': ')', '{': '}', '[': ']',\n",
    "            ')': '(', '}': '{', ']': '['\n",
    "        }\n",
    "        \n",
    "        def _solve(brace_inp, stack):\n",
    "            if len(brace_inp) == 0 and len(stack) == 0:\n",
    "                return 'YES'\n",
    "            \n",
    "            if len(brace_inp) > 0:\n",
    "                first, rest = brace_inp[0], brace_inp[1:]\n",
    "                \n",
    "                if first in '{[(':\n",
    "                    stack.append(first)\n",
    "                    return _solve(rest, stack)\n",
    "                \n",
    "                if first in '}])':\n",
    "                    if len(stack) == 0:\n",
    "                        return 'NO'\n",
    "                    if stack[-1] == closing_pairs[first]:\n",
    "                        stack.pop()\n",
    "                        return _solve(rest, stack)\n",
    "                    else:\n",
    "                        return 'NO'\n",
    "            return 'NO'\n",
    "        return _solve(brace_string, [])\n",
    "        \n",
    "    return [solve(r) for r in values]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "}][}}(}][))] []\n",
      "[](){()} []\n",
      "](){()} ['[']\n",
      "(){()} []\n",
      "){()} ['(']\n",
      "{()} []\n",
      "()} ['{']\n",
      ")} ['{', '(']\n",
      "} ['{']\n",
      " []\n",
      "() []\n",
      ") ['(']\n",
      " []\n",
      "({}([][]))[]() []\n",
      "{}([][]))[]() ['(']\n",
      "}([][]))[]() ['(', '{']\n",
      "([][]))[]() ['(']\n",
      "[][]))[]() ['(', '(']\n",
      "][]))[]() ['(', '(', '[']\n",
      "[]))[]() ['(', '(']\n",
      "]))[]() ['(', '(', '[']\n",
      "))[]() ['(', '(']\n",
      ")[]() ['(']\n",
      "[]() []\n",
      "]() ['[']\n",
      "() []\n",
      ") ['(']\n",
      " []\n",
      "{)[](}]}]}))}(())( []\n",
      ")[](}]}]}))}(())( ['{']\n",
      "! ) [](}]}]}))}(())( ['{']\n",
      "([[) []\n",
      "[[) ['(']\n",
      "[) ['(', '[']\n",
      ") ['(', '[', '[']\n",
      "! )  ['(', '[', '[']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['NO', 'YES', 'YES', 'YES', 'NO', 'NO']"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val = [\n",
    "    '}][}}(}][))]',\n",
    "    '[](){()}',\n",
    "    '()',\n",
    "    '({}([][]))[]()',\n",
    "    '{)[](}]}]}))}(())(',\n",
    "    '([[)'\n",
    "]\n",
    "\n",
    "braces(val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxDifference(a):\n",
    "    if not a or len(a) == 1:\n",
    "        return -1\n",
    "    curr_min, curr_diff = a[0], a[1] - a[0]\n",
    "    for i in a[1:]:\n",
    "        curr_diff = max(i - curr_min, curr_diff)\n",
    "        curr_min = min(curr_min, i)\n",
    "    return curr_diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-1, -1)"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t1 = [2, 3, 10, 2, 4, 8, 1]\n",
    "t2 = [7,9,5,6,3,2]\n",
    "t = [10,8,7,6,5]\n",
    "maxDiff(t, len(t)), maxDifference(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['d104.aa.net',\n",
       " '[01/Jul/1995:00:00:15 -0400] \"GET /images/NASA-logosmall.gif HTTP/1.0\" 200 786']"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'d104.aa.net - - [01/Jul/1995:00:00:15 -0400] \"GET /images/NASA-logosmall.gif HTTP/1.0\" 200 786'.split(' - - ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['', '00']"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"hosts_access_log_00.txt\".replace('.txt', '').split('hosts_access_log_')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{0, 2, 3, 4}, {1}]"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "adjm = [\n",
    "    [0, 0, 1, 0, 0],\n",
    "    [0, 0, 0, 0, 0],\n",
    "    [1, 0, 0, 1, 0],\n",
    "    [0, 0, 1, 0, 1],\n",
    "    [0, 0, 0, 1, 0]\n",
    "] # {0, 2, 3, 4} {1}\n",
    "\n",
    "def connected_components(matr):\n",
    "    connections = {}\n",
    "    def adjacent(line):\n",
    "        return [i for i, v in enumerate(line) if v]\n",
    "    for i, line in enumerate(matr):\n",
    "        connections[i] = set(adjacent(line))\n",
    "\n",
    "    components = []\n",
    "    def component(v):\n",
    "        queue = [v]\n",
    "        comps = set()\n",
    "        while queue:\n",
    "            n = queue.pop(0)\n",
    "            comps.add(n)\n",
    "            queue.extend(connections[n] - comps)\n",
    "        return comps\n",
    "\n",
    "    for v, e in connections.items():\n",
    "        c = component(v)\n",
    "        if c not in components:\n",
    "            components.append(component(v))\n",
    "    return components\n",
    "        \n",
    "\n",
    "connected_components(adjm)"
   ]
  }
 ],
 "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}