{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "dbdd8508",
   "metadata": {},
   "source": [
    "# [Roman Numerals](https://projecteuler.net/problem=89)\n",
    "\n",
    "First, we have to read in all the [Roman numerals](https://en.wikipedia.org/wiki/Roman_numerals) we're working with."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "e2925aba",
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"txt/0089_roman.txt\") as f:\n",
    "    numerals = [s.strip() for s in f.readlines()]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b57710ca",
   "metadata": {},
   "source": [
    "To assist us, we'll make a map from denominations to Roman numerals."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "5b4b8abd",
   "metadata": {},
   "outputs": [],
   "source": [
    "denominations = {\n",
    "    1: \"I\",\n",
    "    2: \"II\",\n",
    "    3: \"III\",\n",
    "    4: \"IV\",\n",
    "    5: \"V\",\n",
    "    6: \"VI\",\n",
    "    7: \"VII\",\n",
    "    8: \"VIII\",\n",
    "    9: \"IX\",\n",
    "    10: \"X\",\n",
    "    20: \"XX\",\n",
    "    30: \"XXX\",\n",
    "    40: \"XL\",\n",
    "    50: \"L\",\n",
    "    60: \"LX\",\n",
    "    70: \"LXX\",\n",
    "    80: \"LXXX\",\n",
    "    90: \"XC\",\n",
    "    100: \"C\",\n",
    "    200: \"CC\",\n",
    "    300: \"CCC\",\n",
    "    400: \"CD\",\n",
    "    500: \"D\",\n",
    "    600: \"DC\",\n",
    "    700: \"DCC\",\n",
    "    800: \"DCCC\",\n",
    "    900: \"CM\",\n",
    "    1000: \"M\",\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "339bbd69",
   "metadata": {},
   "source": [
    "We can make a simple greedy parser to convert the given Roman numerals to ints."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "01623002",
   "metadata": {},
   "outputs": [],
   "source": [
    "def to_int(s):\n",
    "    rev_denominations = {v: k for (k, v) in denominations.items()}\n",
    "    prefixes = sorted(rev_denominations.keys(), key=len, reverse=True)\n",
    "    \n",
    "    n = 0\n",
    "    while s != \"\":\n",
    "        for prefix in prefixes:\n",
    "            if s.startswith(prefix):\n",
    "                n += rev_denominations[prefix]\n",
    "                s = s.removeprefix(prefix)\n",
    "                break\n",
    "                \n",
    "    return n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "594d35b8",
   "metadata": {},
   "source": [
    "It's arguably easier to convert an int to the minimal Roman numeral."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "fc3ce748",
   "metadata": {},
   "outputs": [],
   "source": [
    "def to_roman(n):\n",
    "    s = [\"\", \"\", \"\", \"\"]\n",
    "    \n",
    "    for i in range(1, 4):\n",
    "        d = n % 10^i\n",
    "        if d in denominations:\n",
    "            s[-i] = denominations[d]\n",
    "    \n",
    "        n -= d\n",
    "        \n",
    "    s[0] = \"M\" * (n // 1000)\n",
    "    \n",
    "    return \"\".join(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e1f6d92d",
   "metadata": {},
   "source": [
    "To solve, convert each Roman numeral to an int, then convert that int to the minimal Roman numeral, and count the characters saved."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "b88ee547",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "743"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "total = 0\n",
    "for numeral in numerals:\n",
    "    value = to_int(numeral)\n",
    "    minimal = to_roman(value)\n",
    "    total += len(numeral) - len(minimal)\n",
    "\n",
    "total"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "109ecfb2",
   "metadata": {},
   "source": [
    "#### Copyright (C) 2025 filifa\n",
    "\n",
    "This work is licensed under the [Creative Commons Attribution-ShareAlike 4.0 International license](https://creativecommons.org/licenses/by-sa/4.0/) and the [BSD Zero Clause license](https://spdx.org/licenses/0BSD.html)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.5",
   "language": "sage",
   "name": "sagemath"
  },
  "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.11.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}