code/12. Integer to Roman.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem\n",
    "\n",
    "Roman numerals are represented by seven different symbols: `I`, `V`, `X`, `L`, `C`, `D` and `M`.\n",
    "\n",
    "```\n",
    "Symbol       Value\n",
    "I             1\n",
    "V             5\n",
    "X             10\n",
    "L             50\n",
    "C             100\n",
    "D             500\n",
    "M             1000\n",
    "```\n",
    "For example, `2` is written as `II` in Roman numeral, just two one's added together. `12` is written as `XII`, which is simply `X + II`. The number `27` is written as `XXVII`, which is `XX + V + II`.\n",
    "\n",
    "Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not `IIII`. Instead, the number four is written as `IV`. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as `IX`. There are six instances where subtraction is used:\n",
    "\n",
    "`I` can be placed before `V` (5) and `X` (10) to make 4 and 9.  \n",
    "`X` can be placed before `L` (50) and `C` (100) to make 40 and 90.  \n",
    "`C` can be placed before `D` (500) and `M` (1000) to make 400 and 900.  \n",
    "\n",
    "Given an integer, convert it to a roman numeral."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Summary\n",
    "\n",
    "+ have considered `0` situation at first, but forget then.\n",
    "+ `range()` does not accept the `float` type.\n",
    "+ the elements with same index in two `list` construct a pair -> convinent for loop compared with `dict`\n",
    "\n",
    "But more, how to construct the rules?\n",
    "1. exhausted all the results, and follow them\n",
    "2. find the general rule, and add the others (special) rules, then iterate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Review\n",
    "\n",
    "## 28/03/22\n",
    "\n",
    "Rule-based method is the only way to solve this problem. The question raises that how to generate the Roman by rules.\n",
    "\n",
    "My methods is pretty simple, given a dictionary that stores the representation of zero to nine at each carry. Another method construct the Roman by implementing subtraction from the largest case to the least case. The key difference between the two is the first computes Roman from the left and the second computes from the right."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Method\n",
    "\n",
    "1. rule-based.\n",
    "\n",
    "1.1 Decompose the int by digit, and can find the Roman number along with, then concatenate the Roman string. But this method is too lengthy.$O(n)$  \n",
    "1.2 Decompose the int by subtraction thousands, hundreds, tens, and ones.\n",
    "+ subtraction result > 0, keep going\n",
    "+ subtraction result < 0, find how many times they do subtraction. If t = 1, next degree; 1 < t <= 3, just concatenate `I` like Roman; if 4 <= t <= 8, `V` like Roman; if 9 <= t, `X` like Roman."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Method 1.1 Decompose by Int\n",
    "\n",
    "|Number|Ones|Tens|Hundreds|Thousands|\n",
    "|:--|:--|:--|:--|:--|\n",
    "|1|`I`|`X`|`C`|`M`|\n",
    "|2|`II`|`XX`|`CC`|`MM`|\n",
    "|3|`III`|`XXX`|`CCC`|`MMM`|\n",
    "|4|`IV`|`XL`|`CD`||\n",
    "|5|`V`|`L`|`D`||\n",
    "|6|`VI`|`LX`|`DC`||\n",
    "|7|`VII`|`LXX`|`DCC`||\n",
    "|8|`VII`|`LXX`|`DCCC`||\n",
    "|9|`IX`|`XC`|`CM`||\n",
    "|0|`''`|`''`|`''`|`''`|"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''\n",
    "Runtime: 56 ms\n",
    "Memory Usage: 14.2 MB\n",
    "'''\n",
    "\n",
    "def intToRoman(num: int) -> str:\n",
    "    \n",
    "    assert 1 <= num <= 3999, 'the input is out of range of [1, 3999].'\n",
    "    \n",
    "    # rules \n",
    "#     ones = {1:'I', 2:'II', 3:'III', 4:'IV', 5:'V', 6:'VI', 7:'VII', 8:'VIII', 9:'IX'}\n",
    "#     tens = {1:'X', 2:'XX', 3:'XXX', 4:'XL', 5:'L', 6:'LX', 7:'LXX', 8:'LXXX', 9:'XC'}\n",
    "#     hundreds = {1:'C', 2:'CC', 3:'CCC', 4:'CD', 5:'D', 6:'DC', 7:'DCC', 8:'DCCC', 9:'CM'}\n",
    "#     thousands = {1:'M', 2:'MM', 3:'MMM'}\n",
    "    rules = {\n",
    "        1: {0:'', 1:'I', 2:'II', 3:'III', 4:'IV', 5:'V', 6:'VI', 7:'VII', 8:'VIII', 9:'IX'},\n",
    "        2: {0:'', 1:'X', 2:'XX', 3:'XXX', 4:'XL', 5:'L', 6:'LX', 7:'LXX', 8:'LXXX', 9:'XC'},\n",
    "        3: {0:'', 1:'C', 2:'CC', 3:'CCC', 4:'CD', 5:'D', 6:'DC', 7:'DCC', 8:'DCCC', 9:'CM'},\n",
    "        4: {0:'', 1:'M', 2:'MM', 3:'MMM'}\n",
    "    }\n",
    "    \n",
    "    roman = ''\n",
    "    times = 0\n",
    "    while num >= 1:\n",
    "        times += 1\n",
    "        mod = num % 10\n",
    "        # num = int(num/10)\n",
    "        num = num // 10\n",
    "        \n",
    "        roman = rules[times][mod] + roman\n",
    "    \n",
    "    return roman"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Standard Method\n",
    "\n",
    "Standard method is similar to my ans, but more elegant. Since it decompes the int from the largest to the smallest, and need less rules. $O(n)$\n",
    "\n",
    "REF: https://www.rapidtables.com/convert/number/how-number-to-roman-numerals.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''\n",
    "Runtime: 60 ms\n",
    "Memory Usage: 14.4 MB\n",
    "'''\n",
    "\n",
    "def intToRoman(num: int) -> str:\n",
    "    values = [1000, 900, 500, 400,\n",
    "              100, 90, 50, 40,\n",
    "              10, 9, 5, 4, 1]\n",
    "    symbols = [\"M\", \"CM\", \"D\", \"CD\",\n",
    "               \"C\", \"XC\", \"L\", \"XL\",\n",
    "               \"X\", \"IX\", \"V\", \"IV\",\n",
    "               \"I\"]\n",
    "    roman = ''\n",
    "    i = 0\n",
    "    while num > 0:\n",
    "        # k = num / values[i]\n",
    "        k = num // values[i]\n",
    "        # for j in range(int(k)):\n",
    "        for j in range(k):\n",
    "            roman += symbols[i]\n",
    "            num -= values[i]\n",
    "        i += 1\n",
    "    return roman"
   ]
  }
 ],
 "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.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}