work/problem089.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Roman numerals](https://projecteuler.net/problem=89)\n",
    "\n",
    "> For a number written in Roman numerals to be considered valid there are basic rules which must be followed. Even though the rules allow some numbers to be expressed in more than one way there is always a \"best\" way of writing a particular number.\n",
    ">\n",
    "> For example, it would appear that there are at least six ways of writing the number sixteen:\n",
    ">\n",
    "> IIIIIIIIIIIIIIII  \n",
    "> VIIIIIIIIIII  \n",
    "> VVIIIIII  \n",
    "> XIIIIII  \n",
    "> VVVI  \n",
    "> XVI\n",
    ">\n",
    "> However, according to the rules only XIIIIII and XVI are valid, and the last example is considered to be the most efficient, as it uses the least number of numerals.\n",
    ">\n",
    "> The 11K text file, roman.txt (right click and 'Save Link/Target As...'), contains one thousand numbers written in valid, but not necessarily minimal, Roman numerals; see [About... Roman Numerals](https://projecteuler.net/about=roman_numerals) for the definitive rules for this problem.\n",
    ">\n",
    "> Find the number of characters saved by writing each of these in their minimal form.\n",
    ">\n",
    "> Note: You can assume that all the Roman numerals in the file contain no more than four consecutive identical units.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I’ll approach this problem by parsing each Roman numeral string into an integer, converting that integer into a minimal Roman Numeral string, and comparing the sums of the lengths of the strings.\n",
    "\n",
    "For parsing the strings, I'll iterate through the indexes of the characters within the string—not assuming that each character is one byte wide, even though these happen to be—adding or subtracting the value for the current ‘digit’ (depending on its relationship to the character that follows it) from a running total. Observe that the running total can take on a negative value, even though the final total will be positive."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "parseroman (generic function with 1 method)"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function parseroman(s)\n",
    "    R = Dict('M'=>1000, 'D'=>500, 'C'=>100, 'L'=>50, 'X'=>10, 'V'=>5, 'I'=>1)\n",
    "    value = zero(Int)\n",
    "    for i in eachindex(s)\n",
    "        if i < lastindex(s) && R[s[i]] < R[s[nextind(s, i)]]\n",
    "            value -= R[s[i]]\n",
    "        else\n",
    "            value += R[s[i]]\n",
    "        end\n",
    "    end\n",
    "    value\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For turning numbers back into Roman numeral strings, I’ll break it down into the number of 1000s it contains, the number of 500s, etc. I’m pulling out the bigger numbers first, so `D`, the number of 500s, can only be 0 or 1, and so on. I can then build the string up from there, right to left, starting with `M` ‘M’s. Then, the same thing happens for 5s and 1s, at the three powers of 10: 10<sup>2</sup>, 10<sup>1</sup>, and 10<sup>0</sup>. If there are four ones, we subtract one from five or 10, otherwise we proceed directly. Julia strings are immutable, so we store our substrings in an array and join up the pieces at the end."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "toroman (generic function with 1 method)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function toroman(n)\n",
    "    M, n = divrem(n, 1000)\n",
    "    D, n = divrem(n, 500)\n",
    "    C, n = divrem(n, 100)\n",
    "    L, n = divrem(n, 50)\n",
    "    X, n = divrem(n, 10)\n",
    "    V, I = divrem(n, 5)\n",
    "\n",
    "    function f(a, b, c)\n",
    "        d = []\n",
    "        if b == 4\n",
    "            push!(d, string(c[3], c[a == 1 ? 1 : 2]))\n",
    "            a, b = 0, 0\n",
    "        end\n",
    "        push!(d, c[2]^a, c[3]^b)\n",
    "        d\n",
    "    end\n",
    "\n",
    "    digits = [ 'M'^M ]\n",
    "    append!(digits, f(D, C, ['M', 'D', 'C']))\n",
    "    append!(digits, f(L, X, ['C', 'L', 'X']))\n",
    "    append!(digits, f(V, I, ['X', 'V', 'I']))\n",
    "\n",
    "    join(digits)\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To get the answer to this problem, I’ll iterate through the lines of the supplied file, recording the length of each. Julia understands composing functions with the ∘ operator, so I can round-trip each Roman numeral with `(toroman ∘ parseroman)(…)` instead of `toroman(parseroman(…))`. Nice. The answer is the difference between the lengths of the given numerals and the ones I produced."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "numbers expressed with 8850 characters, redone with 8107 characters\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "743"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "given = 0\n",
    "computed = 0\n",
    "for r in eachline(\"p089_roman.txt\")\n",
    "    given += length(r)\n",
    "    computed += length((toroman ∘ parseroman)(r))\n",
    "end\n",
    "println(\"numbers expressed with $given characters, redone with $computed characters\")\n",
    "given - computed"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementing a Custom Type\n",
    "\n",
    "What if we could use the system `parse` and `convert` functions? We can if we write our own implementation of a custom `Roman` type."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "primitive type Roman <: Integer 64 end\n",
    "Roman(x::Int64) = reinterpret(Roman, x)\n",
    "Int64(x::Roman) = reinterpret(Int64, x)\n",
    "Base.convert(::Type{Roman}, x) = Roman(x)\n",
    "Base.convert(::Type{Int64}, x::Roman) = Int64(x)\n",
    "\n",
    "import Base: +\n",
    "+(a::Roman, b::Roman) = Roman(Int64(a) + Int64(b))\n",
    "+(a::Roman, b::Int64) = Roman(Int64(a) + b)\n",
    "+(a::Int64, b::Roman) = Roman(a + Int64(b))\n",
    "\n",
    "import Base: -\n",
    "-(a::Roman, b::Roman) = Roman(Int64(a) - Int64(b))\n",
    "-(a::Roman, b::Int64) = Roman(Int64(a) - b)\n",
    "-(a::Int64, b::Roman) = Roman(a - Int64(b))\n",
    "\n",
    "import Base: <\n",
    "<(a::Roman, b::Roman) = isless(Int64(a), Int64(b))\n",
    "\n",
    "function Base.parse(::Type{Roman}, c::AbstractChar)\n",
    "    R = Dict('M'=>1000, 'D'=>500, 'C'=>100, 'L'=>50, 'X'=>10, 'V'=>5, 'I'=>1)\n",
    "    haskey(R, uppercase(c)) || throw(DomainError(c, \"not a Roman numeral\"))\n",
    "    reinterpret(Roman, R[uppercase(c)])\n",
    "end\n",
    "\n",
    "function Base.parse(::Type{Roman}, s::AbstractString)\n",
    "    value = zero(Int)\n",
    "    for i in eachindex(s)\n",
    "        if i < lastindex(s) && parse(Roman, s[i]) < parse(Roman, s[nextind(s, i)])\n",
    "            value -= parse(Roman, s[i])\n",
    "        else\n",
    "            value += parse(Roman, s[i])\n",
    "        end\n",
    "    end\n",
    "    reinterpret(Roman, value)\n",
    "end\n",
    "\n",
    "function Base.String(x::Roman)\n",
    "    n = Int64(x)\n",
    "    M, n = divrem(n, 1000)\n",
    "    D, n = divrem(n, 500)\n",
    "    C, n = divrem(n, 100)\n",
    "    L, n = divrem(n, 50)\n",
    "    X, n = divrem(n, 10)\n",
    "    V, I = divrem(n, 5)\n",
    "\n",
    "    function f(a, b, c)\n",
    "        d = []\n",
    "        if b == 4\n",
    "            push!(d, string(c[3], c[a == 1 ? 1 : 2]))\n",
    "            a, b = 0, 0\n",
    "        end\n",
    "        push!(d, c[2]^a, c[3]^b)\n",
    "        d\n",
    "    end\n",
    "\n",
    "    digits = [ 'M'^M ]\n",
    "    append!(digits, f(D, C, ['M', 'D', 'C']))\n",
    "    append!(digits, f(L, X, ['C', 'L', 'X']))\n",
    "    append!(digits, f(V, I, ['X', 'V', 'I']))\n",
    "\n",
    "    join(digits)    \n",
    "end\n",
    "\n",
    "Base.length(x::Roman) = length(String(x))\n",
    "Base.show(io::IO, x::Roman) = print(io, String(x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "@assert sum(length, parse(Roman, r) for r in eachline(\"p089_roman.txt\")) == 8107 \"total size of Roman Numerals is wrong\""
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.4.1",
   "language": "julia",
   "name": "julia-1.4"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.4.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}