euler-081-path-sum-two-ways-20130821.ipynb

{
 "metadata": {
  "name": "euler-081-path-sum-two-ways-20130821"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by **only moving to the right and down**, is indicated in bold red and is equal to 2427.  \n",
      "  \n",
      ">  **131**  673  234  103  18  \n",
      ">  **201  96  342**  965  150  \n",
      ">  630  803  **746  422**  111  \n",
      ">  537  699  497  **121**  956  \n",
      ">  805  732  524  **37  331**  \n",
      "\n",
      "Find the minimal path sum, in [matrix.txt](http://projecteuler.net/project/matrix.txt) (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, from the left column to the right column."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import numpy as np"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def foo(m):\n",
      "    # s = [[2 ** 64 - 1] * len(m[0])] * len(m)  # Slow. \n",
      "    s = [[999999] * len(m[0])] * len(m)\n",
      "    # s = [[2 ** 31 - 1] * len(m[0])] * len(m)  # Not slow.\n",
      "    s = np.array(s)\n",
      "\n",
      "    for column in range(len(m[0]) - 1):\n",
      "        for row in range(len(m)):\n",
      "            if column == 0:\n",
      "                s[row, column] = m[row, column]\n",
      "                if row > 0:\n",
      "                    s[row, column] += s[row - 1, column]\n",
      "            else:\n",
      "                for dir in (1, ):\n",
      "                    r = range(row, 0 if dir < 0 else len(m)-1, dir)\n",
      "                    # print 'd', row, column, dir, r\n",
      "                    for r1 in r:\n",
      "                        r2 = r1 + dir\n",
      "                        if s[r1, column] + m[r2, column] >= s[r2, column]:\n",
      "                            break\n",
      "                        s[r2, column] = s[r1, column] + m[r2, column]\n",
      "        for row in range(len(m)):\n",
      "            s[row, column+1] = s[row, column] + m[row, column+1]\n",
      "    return s[-1, -1]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "n = [[131,673, 234, 103,  18],\n",
      "    [201,  96, 342, 965, 150],\n",
      "    [630, 803, 746, 422, 111],\n",
      "    [537, 699, 497, 121, 956],\n",
      "    [805, 732, 524,  37, 331]]\n",
      "n = np.array(n)\n",
      "print n\n",
      "\n",
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[[131 673 234 103  18]\n",
        " [201  96 342 965 150]\n",
        " [630 803 746 422 111]\n",
        " [537 699 497 121 956]\n",
        " [805 732 524  37 331]]\n",
        "10000 loops, best of 3: 178 us per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 3,
       "text": [
        "2427"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# http://projecteuler.net/project/matrix.txt\n",
      "n = np.array([map(int, line.strip().split(',')) for line in open('matrix.txt').readlines()])\n",
      "# print n\n",
      "\n",
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10 loops, best of 3: 49.1 ms per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "427337"
       ]
      }
     ],
     "prompt_number": 4
    }
   ],
   "metadata": {}
  }
 ]
}