20141201_Euler89.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:c2fea237141dda7298d5b591267184a538cd20dfd602a61ee07ab86f8c9a94d7"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def number_to_numeral(n):\n",
      "    \"\"\"\n",
      "    returns minimal numeral\n",
      "    \"\"\"\n",
      "    remainder = n\n",
      "    values = [1000, 500, 100, 50, 10, 5, 1]\n",
      "    substractive_cases = [None, 100, 100, 10, 10, 1, 1]\n",
      "    symbols = dict(zip(values, ['M', 'D', 'C', 'L', 'X', 'V', 'I']))\n",
      "    numeral = ''\n",
      "    for i in range(len(values)):\n",
      "        if remainder >= values[i]:\n",
      "            # first substractive test\n",
      "            if substractive_cases[i] != None and i > 0:\n",
      "                if (remainder + substractive_cases[i]) >= values[i-1]:\n",
      "                    remainder -= (values[i-1] - substractive_cases[i])\n",
      "                    numeral += symbols[substractive_cases[i]] + symbols[values[i-1]]\n",
      "            # then normal test\n",
      "            while remainder >= values[i]:\n",
      "                remainder -= values[i]\n",
      "                numeral += symbols[values[i]]\n",
      "    return numeral"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The problem with this problem is the \"minimal\" form as described [here](https://projecteuler.net/about=roman_numerals). It is important to pay attention to the potential errors arising from substractive combinations:\n",
      "\n",
      ">In addition to the three rules given above, if subtractive combinations are used then the following four rules must be followed.\n",
      "\n",
      ">Only one I, X, and C can be used as the leading numeral in part of a subtractive pair.\n",
      "\n",
      ">I can only be placed before V and X.\n",
      "\n",
      ">X can only be placed before L and C.\n",
      "\n",
      ">C can only be placed before D and M."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The substractive cases to take into account are thus:\n",
      "\n",
      "- 900 + 100 = 1000 (CM)\n",
      "- 400 + 100 = 500 (CD)\n",
      "- 90 + 10 = 100 (XC)\n",
      "- 40 + 10 = 50 (XL)\n",
      "- 9 + 1 = 10 (IX)\n",
      "- 4 + 1 = 5 (IV)\n"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "First test case:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for i in range(1, 21):\n",
      "    print(number_to_numeral(i))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "I\n",
        "II\n",
        "III\n",
        "IV\n",
        "V\n",
        "VI\n",
        "VII\n",
        "VIII\n",
        "IX\n",
        "X\n",
        "XI\n",
        "XII\n",
        "XIII\n",
        "XIV\n",
        "XV\n",
        "XVI\n",
        "XVII\n",
        "XVIII\n",
        "XIX\n",
        "XX\n"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Second test case batch:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "number_to_numeral(9)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 3,
       "text": [
        "'IX'"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "number_to_numeral(19)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "'XIX'"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "number_to_numeral(400)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 5,
       "text": [
        "'CD'"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "number_to_numeral(405)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 6,
       "text": [
        "'CDV'"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "number_to_numeral(900)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 7,
       "text": [
        "'CM'"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "number_to_numeral(1900)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 8,
       "text": [
        "'MCM'"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Now, on to the problem. First, we need to be able to read numerals, then we convert them to minimal form, storing the in-between result."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def numeral_to_number(numeral):\n",
      "    number = 0\n",
      "    values = [1000, 500, 100, 50, 10, 5, 1]\n",
      "    symbols = dict(zip(['M', 'D', 'C', 'L', 'X', 'V', 'I'], values))\n",
      "    for ind, num in enumerate(numeral):\n",
      "        if not ind == len(numeral) - 1:\n",
      "            if symbols[numeral[ind+1]] > symbols[num]:\n",
      "                number -= symbols[num]\n",
      "            else:\n",
      "                number += symbols[num]\n",
      "        else:\n",
      "            number += symbols[num]\n",
      "    return number"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 9
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "numeral_to_number('MMMDLXVIIII')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 10,
       "text": [
        "3569"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "number_to_numeral(3569)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 11,
       "text": [
        "'MMMDLXIX'"
       ]
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The final loop:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import urllib2  # the lib that handles the url stuff\n",
      "data = urllib2.urlopen(\"https://projecteuler.net/project/resources/p089_roman.txt\").readlines() # it's a file like object and works just like a file"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 12
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "initial_lengths = []\n",
      "shortest_lengths = []\n",
      "for line in data: # files are iterable\n",
      "    initial_lengths.append(len(line.strip()))\n",
      "    n = numeral_to_number(line.strip())\n",
      "    shortest_lengths.append(len(number_to_numeral(n)))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 13
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "sum(initial_lengths)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 14,
       "text": [
        "8850"
       ]
      }
     ],
     "prompt_number": 14
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "sum(shortest_lengths)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 15,
       "text": [
        "8107"
       ]
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "And the answer is:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "sum(initial_lengths) - sum(shortest_lengths)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 16,
       "text": [
        "743"
       ]
      }
     ],
     "prompt_number": 16
    }
   ],
   "metadata": {}
  }
 ]
}