expertlead_challenge.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c2d53484-d801-4622-9823-86da6ccfc2b0",
   "metadata": {
    "tags": []
   },
   "source": [
    "# expertlead Coding Challenge\n",
    "\n",
    "```\n",
    "|\n",
    "|\n",
    "|   + (1,4)    + (4,4)\n",
    "|\n",
    "|        + (3,2)\n",
    "|                 + (5,1)\n",
    "|\n",
    "+-------------------------------\n",
    "```\n",
    "\n",
    "Design an application that, given a set of coordinates [(x1, y1), ..., (xn, yn)], determines:\n",
    "- the two closest points between each other\n",
    "- the two most distant points between each other\n",
    "\n",
    "Use your knowledge of **Clean and maintainable code** to create an **appliation with automated tests**.\n",
    "\n",
    "Start with tests or implementation, whatever is better for you."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "e6bd3494-0723-41a4-a1a9-c4dbc4c79cfc",
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import Dict, List, Tuple"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "8ddcba66-b4c6-40fa-bcc7-39128a366f3d",
   "metadata": {},
   "outputs": [],
   "source": [
    "Point = Tuple[int, int]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "acef214a-beef-4976-9c34-f6a22e9fa6e4",
   "metadata": {},
   "source": [
    "## test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "7e729a42-d78a-4ae9-af56-146a19df2d6b",
   "metadata": {},
   "outputs": [
    {
     "ename": "AssertionError",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAssertionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m/var/folders/86/81nphykn4zq2ln3tck4llpzm0000gr/T/ipykernel_19651/954999195.py\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m     10\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m \u001b[0;31m# then\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m \u001b[0;32massert\u001b[0m \u001b[0moutput\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0mexpected_output\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mAssertionError\u001b[0m: "
     ]
    }
   ],
   "source": [
    "# given\n",
    "coordinates: List[Point] = [(1, 4), (4, 4), (3, 2), (5, 1)]\n",
    "expected_output: Dict[str, List[Point]] = {\n",
    "    \"closest\": [(3, 2), (4, 4)],\n",
    "    \"furthest\": [(1, 4), (5, 1)],\n",
    "}\n",
    "\n",
    "# when\n",
    "output = main(coordinates)\n",
    "\n",
    "# then\n",
    "assert output == expected_output  # TODO: be smarter in the assert"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "67d297e3-f4b8-4fb6-aaf6-63629e25ad1d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'closest': ((4, 4), (3, 2)), 'furthest': ((1, 4), (5, 1))}"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "88727b0a-c32c-4cbb-8ee7-541796713c77",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'closest': [(3, 2), (4, 4)], 'furthest': [(1, 4), (5, 1)]}"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "expected_output"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22b0452e-16fe-4604-938e-1bd289b9b30e",
   "metadata": {},
   "source": [
    "## implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "e2abacff-39a9-4812-8dfd-a6fd25d5a7ab",
   "metadata": {},
   "outputs": [],
   "source": [
    "import itertools\n",
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "57f88d1a-3306-44b7-9211-4991182c1b64",
   "metadata": {},
   "outputs": [],
   "source": [
    "def distance(a: Point, b: Point) -> float:\n",
    "    x_a, y_a = a\n",
    "    x_b, y_b = b\n",
    "\n",
    "    # math.dist\n",
    "    euclidian_distance = math.sqrt((x_a - x_b) ** 2 + (y_a - y_b) ** 2)\n",
    "    return euclidian_distance\n",
    "\n",
    "\n",
    "def main(coordinates: List[Point]) -> Dict[str, List[Point]]:\n",
    "    # n**2 4 times\n",
    "    # upper triangle\n",
    "    candidate_pairs: List[Tuple[Point]] = list(\n",
    "        itertools.product(coordinates, coordinates)\n",
    "    )\n",
    "\n",
    "    distances = {}\n",
    "    for candidate_pair in candidate_pairs:\n",
    "        a, b = candidate_pair\n",
    "        if a == b:\n",
    "            continue\n",
    "        d = distance(a, b)\n",
    "        # store only min and max\n",
    "        distances[candidate_pair] = d\n",
    "\n",
    "    closest = min(distances, key=distances.get)\n",
    "    furthest = max(distances, key=distances.get)\n",
    "    return {\n",
    "        \"closest\": closest,\n",
    "        \"furthest\": furthest,\n",
    "    }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "c0a94467-17ce-45a7-97f0-83edc23bbfb2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'closest': ((4, 4), (3, 2)), 'furthest': ((1, 4), (5, 1))}"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "main(coordinates)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6e4d7894-f960-4542-a458-884a5d199cef",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}