199 lines
4.5 KiB
Plaintext
199 lines
4.5 KiB
Plaintext
{
|
|
"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
|
|
}
|