euler-11.ipynb

   1 {
   2  "metadata": {
   3   "name": "",
   4   "signature": "sha256:2513cb86760ebf975b3dce5f7884ee5e23c13f94e20cc9af8fc245f251455fda"
   5  },
   6  "nbformat": 3,
   7  "nbformat_minor": 0,
   8  "worksheets": [
   9   {
  10    "cells": [
  11     {
  12      "cell_type": "markdown",
  13      "metadata": {},
  14      "source": [
  15       "## Project Euler problem 11\n",
  16       "Find the largest product of four adjacent numbers in the grid."
  17      ]
  18     },
  19     {
  20      "cell_type": "markdown",
  21      "metadata": {},
  22      "source": [
  23       "## Constants"
  24      ]
  25     },
  26     {
  27      "cell_type": "code",
  28      "collapsed": false,
  29      "input": [
  30       "ROWS = COLUMNS = 20\n",
  31       "SECTION_LEN = 4"
  32      ],
  33      "language": "python",
  34      "metadata": {},
  35      "outputs": [],
  36      "prompt_number": 97
  37     },
  38     {
  39      "cell_type": "markdown",
  40      "metadata": {},
  41      "source": [
  42       "##Data structure\n",
  43       "Convert the text of the numbers into a 2d array of integers.\n",
  44       "\n",
  45       "(Alterntive data structures include a 1d list of integers, or a dict with keys of (r, c) pairs.)"
  46      ]
  47     },
  48     {
  49      "cell_type": "code",
  50      "collapsed": false,
  51      "input": [
  52       "GRID_STRING = \"\"\"08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n",
  53       "49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n",
  54       "81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\n",
  55       "52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\n",
  56       "22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\n",
  57       "24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\n",
  58       "32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\n",
  59       "67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\n",
  60       "24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\n",
  61       "21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\n",
  62       "78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\n",
  63       "16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\n",
  64       "86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\n",
  65       "19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\n",
  66       "04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\n",
  67       "88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\n",
  68       "04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\n",
  69       "20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\n",
  70       "20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\n",
  71       "01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48\"\"\"\n",
  72       "\n",
  73       "GRID_LIST = [int(n) for n in GRID_STRING.split()]\n",
  74       "GRID = [GRID_LIST[i:i+COLUMNS] for i in range(0, ROWS * COLUMNS, COLUMNS)]"
  75      ],
  76      "language": "python",
  77      "metadata": {},
  78      "outputs": [],
  79      "prompt_number": 98
  80     },
  81     {
  82      "cell_type": "code",
  83      "collapsed": false,
  84      "input": [
  85       "for row in GRID:\n",
  86       "    print(row)"
  87      ],
  88      "language": "python",
  89      "metadata": {},
  90      "outputs": [
  91       {
  92        "output_type": "stream",
  93        "stream": "stdout",
  94        "text": [
  95         "[8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8]\n",
  96         "[49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0]\n",
  97         "[81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65]\n",
  98         "[52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 36, 91]\n",
  99         "[22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80]\n",
 100         "[24, 47, 32, 60, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50]\n",
 101         "[32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70]\n",
 102         "[67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21]\n",
 103         "[24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72]\n",
 104         "[21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95]\n",
 105         "[78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92]\n",
 106         "[16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57]\n",
 107         "[86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58]\n",
 108         "[19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40]\n",
 109         "[4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66]\n",
 110         "[88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69]\n",
 111         "[4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36]\n",
 112         "[20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16]\n",
 113         "[20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54]\n",
 114         "[1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48]\n"
 115        ]
 116       }
 117      ],
 118      "prompt_number": 99
 119     },
 120     {
 121      "cell_type": "markdown",
 122      "metadata": {},
 123      "source": [
 124       "#Directions\n",
 125       "What lines do we examine? Each number paricipates in up to 8 \u00d7 4 = 32 lines (fewer near the edges), but we can use the fact that multipication is commutative to only examine four lines that start at a number.\n",
 126       "\n",
 127       "`directions` stores those directions, and how to move in the direction."
 128      ]
 129     },
 130     {
 131      "cell_type": "code",
 132      "collapsed": false,
 133      "input": [
 134       "# Directions, as the pair (difference-in-row, difference-in-column)\n",
 135       "DIRECTIONS = {'N': (-1, 0), 'NW': (-1, -1), 'W': (0, -1), 'SW': (1, -1)}"
 136      ],
 137      "language": "python",
 138      "metadata": {},
 139      "outputs": [],
 140      "prompt_number": 20
 141     },
 142     {
 143      "cell_type": "markdown",
 144      "metadata": {},
 145      "source": [
 146       "## Finding the right numbers\n",
 147       "Given a starting position and a direction, find the right numbers.\n",
 148       "\n",
 149       "### Question:\n",
 150       "Should we worry if the request goes out of the bounds of the grid?"
 151      ]
 152     },
 153     {
 154      "cell_type": "code",
 155      "collapsed": false,
 156      "input": [
 157       "def numbers(row, column, direction):\n",
 158       "    nums = []\n",
 159       "    dr, dc = DIRECTIONS[direction]\n",
 160       "    for _ in range(SECTION_LEN):\n",
 161       "        nums.append(GRID[row][column])\n",
 162       "        row += dr\n",
 163       "        column += dc\n",
 164       "    return nums"
 165      ],
 166      "language": "python",
 167      "metadata": {},
 168      "outputs": [],
 169      "prompt_number": 71
 170     },
 171     {
 172      "cell_type": "markdown",
 173      "metadata": {},
 174      "source": [
 175       "Test it."
 176      ]
 177     },
 178     {
 179      "cell_type": "code",
 180      "collapsed": false,
 181      "input": [
 182       "numbers(0, 3, 'W')"
 183      ],
 184      "language": "python",
 185      "metadata": {},
 186      "outputs": [
 187       {
 188        "metadata": {},
 189        "output_type": "pyout",
 190        "prompt_number": 72,
 191        "text": [
 192         "[97, 22, 2, 8]"
 193        ]
 194       }
 195      ],
 196      "prompt_number": 72
 197     },
 198     {
 199      "cell_type": "code",
 200      "collapsed": false,
 201      "input": [
 202       "numbers(3, 0, 'N')"
 203      ],
 204      "language": "python",
 205      "metadata": {},
 206      "outputs": [
 207       {
 208        "metadata": {},
 209        "output_type": "pyout",
 210        "prompt_number": 73,
 211        "text": [
 212         "[52, 81, 49, 8]"
 213        ]
 214       }
 215      ],
 216      "prompt_number": 73
 217     },
 218     {
 219      "cell_type": "code",
 220      "collapsed": false,
 221      "input": [
 222       "numbers(3, 3, 'NW')"
 223      ],
 224      "language": "python",
 225      "metadata": {},
 226      "outputs": [
 227       {
 228        "metadata": {},
 229        "output_type": "pyout",
 230        "prompt_number": 74,
 231        "text": [
 232         "[23, 31, 49, 8]"
 233        ]
 234       }
 235      ],
 236      "prompt_number": 74
 237     },
 238     {
 239      "cell_type": "code",
 240      "collapsed": false,
 241      "input": [
 242       "numbers(3, 3, 'SW')"
 243      ],
 244      "language": "python",
 245      "metadata": {},
 246      "outputs": [
 247       {
 248        "metadata": {},
 249        "output_type": "pyout",
 250        "prompt_number": 75,
 251        "text": [
 252         "[23, 16, 47, 32]"
 253        ]
 254       }
 255      ],
 256      "prompt_number": 75
 257     },
 258     {
 259      "cell_type": "markdown",
 260      "metadata": {},
 261      "source": [
 262       "## Product of a list"
 263      ]
 264     },
 265     {
 266      "cell_type": "code",
 267      "collapsed": false,
 268      "input": [
 269       "def product(ns):\n",
 270       "    p = 1\n",
 271       "    for n in ns:\n",
 272       "        p *= n\n",
 273       "    return p"
 274      ],
 275      "language": "python",
 276      "metadata": {},
 277      "outputs": [],
 278      "prompt_number": 25
 279     },
 280     {
 281      "cell_type": "code",
 282      "collapsed": false,
 283      "input": [
 284       "product(numbers(0, 3, 'W'))"
 285      ],
 286      "language": "python",
 287      "metadata": {},
 288      "outputs": [
 289       {
 290        "metadata": {},
 291        "output_type": "pyout",
 292        "prompt_number": 26,
 293        "text": [
 294         "34144"
 295        ]
 296       }
 297      ],
 298      "prompt_number": 26
 299     },
 300     {
 301      "cell_type": "code",
 302      "collapsed": false,
 303      "input": [
 304       "97 * 22 * 2 * 8"
 305      ],
 306      "language": "python",
 307      "metadata": {},
 308      "outputs": [
 309       {
 310        "metadata": {},
 311        "output_type": "pyout",
 312        "prompt_number": 27,
 313        "text": [
 314         "34144"
 315        ]
 316       }
 317      ],
 318      "prompt_number": 27
 319     },
 320     {
 321      "cell_type": "markdown",
 322      "metadata": {},
 323      "source": [
 324       "## What directions don't take us out outside of the boundaries?"
 325      ]
 326     },
 327     {
 328      "cell_type": "code",
 329      "collapsed": false,
 330      "input": [
 331       "def valid_direction_explicit(row, column, direction):\n",
 332       "    if direction == 'N' and row >= SECTION_LEN -1:\n",
 333       "        return True\n",
 334       "    elif direction == 'W' and column >= SECTION_LEN -1:\n",
 335       "        return True\n",
 336       "    elif direction == 'NW' and row >= SECTION_LEN -1 and column >= SECTION_LEN -1:\n",
 337       "        return True\n",
 338       "    elif direction == 'SW' and row + SECTION_LEN <= ROWS and column >= SECTION_LEN -1:\n",
 339       "        return True\n",
 340       "    else:\n",
 341       "        return False"
 342      ],
 343      "language": "python",
 344      "metadata": {},
 345      "outputs": [],
 346      "prompt_number": 63
 347     },
 348     {
 349      "cell_type": "code",
 350      "collapsed": false,
 351      "input": [
 352       "valid_direction_explicit(0, 0, 'N')"
 353      ],
 354      "language": "python",
 355      "metadata": {},
 356      "outputs": [
 357       {
 358        "metadata": {},
 359        "output_type": "pyout",
 360        "prompt_number": 33,
 361        "text": [
 362         "False"
 363        ]
 364       }
 365      ],
 366      "prompt_number": 33
 367     },
 368     {
 369      "cell_type": "code",
 370      "collapsed": false,
 371      "input": [
 372       "valid_direction_explicit(5, 5, 'N')"
 373      ],
 374      "language": "python",
 375      "metadata": {},
 376      "outputs": [
 377       {
 378        "metadata": {},
 379        "output_type": "pyout",
 380        "prompt_number": 35,
 381        "text": [
 382         "True"
 383        ]
 384       }
 385      ],
 386      "prompt_number": 35
 387     },
 388     {
 389      "cell_type": "code",
 390      "collapsed": false,
 391      "input": [
 392       "valid_direction_explicit(5, 5, 'NW')"
 393      ],
 394      "language": "python",
 395      "metadata": {},
 396      "outputs": [
 397       {
 398        "metadata": {},
 399        "output_type": "pyout",
 400        "prompt_number": 36,
 401        "text": [
 402         "True"
 403        ]
 404       }
 405      ],
 406      "prompt_number": 36
 407     },
 408     {
 409      "cell_type": "code",
 410      "collapsed": false,
 411      "input": [
 412       "valid_direction_explicit(5, 5, 'W')"
 413      ],
 414      "language": "python",
 415      "metadata": {},
 416      "outputs": [
 417       {
 418        "metadata": {},
 419        "output_type": "pyout",
 420        "prompt_number": 37,
 421        "text": [
 422         "True"
 423        ]
 424       }
 425      ],
 426      "prompt_number": 37
 427     },
 428     {
 429      "cell_type": "code",
 430      "collapsed": false,
 431      "input": [
 432       "valid_direction_explicit(5, 5, 'SW')"
 433      ],
 434      "language": "python",
 435      "metadata": {},
 436      "outputs": [
 437       {
 438        "metadata": {},
 439        "output_type": "pyout",
 440        "prompt_number": 38,
 441        "text": [
 442         "True"
 443        ]
 444       }
 445      ],
 446      "prompt_number": 38
 447     },
 448     {
 449      "cell_type": "code",
 450      "collapsed": false,
 451      "input": [
 452       "valid_direction_explicit(17, 5, 'SW')"
 453      ],
 454      "language": "python",
 455      "metadata": {},
 456      "outputs": [
 457       {
 458        "metadata": {},
 459        "output_type": "pyout",
 460        "prompt_number": 61,
 461        "text": [
 462         "False"
 463        ]
 464       }
 465      ],
 466      "prompt_number": 61
 467     },
 468     {
 469      "cell_type": "code",
 470      "collapsed": false,
 471      "input": [
 472       "valid_direction_explicit(16, 5, 'SW')"
 473      ],
 474      "language": "python",
 475      "metadata": {},
 476      "outputs": [
 477       {
 478        "metadata": {},
 479        "output_type": "pyout",
 480        "prompt_number": 64,
 481        "text": [
 482         "True"
 483        ]
 484       }
 485      ],
 486      "prompt_number": 64
 487     },
 488     {
 489      "cell_type": "code",
 490      "collapsed": false,
 491      "input": [
 492       "valid_direction_explicit(2, 2, 'NW')"
 493      ],
 494      "language": "python",
 495      "metadata": {},
 496      "outputs": [
 497       {
 498        "metadata": {},
 499        "output_type": "pyout",
 500        "prompt_number": 60,
 501        "text": [
 502         "False"
 503        ]
 504       }
 505      ],
 506      "prompt_number": 60
 507     },
 508     {
 509      "cell_type": "code",
 510      "collapsed": false,
 511      "input": [
 512       "def valid_direction(row, column, direction):\n",
 513       "    dr, dc = DIRECTIONS[direction]\n",
 514       "    end_row = row + dr * (SECTION_LEN -1)\n",
 515       "    end_col = column + dc * (SECTION_LEN -1)\n",
 516       "    if end_row >= 0 and end_row < ROWS and end_col >= 0 and end_col < COLUMNS:\n",
 517       "        return True\n",
 518       "    else:\n",
 519       "        return False"
 520      ],
 521      "language": "python",
 522      "metadata": {},
 523      "outputs": [],
 524      "prompt_number": 79
 525     },
 526     {
 527      "cell_type": "code",
 528      "collapsed": false,
 529      "input": [
 530       "valid_direction(0, 0, 'N')"
 531      ],
 532      "language": "python",
 533      "metadata": {},
 534      "outputs": [
 535       {
 536        "metadata": {},
 537        "output_type": "pyout",
 538        "prompt_number": 80,
 539        "text": [
 540         "False"
 541        ]
 542       }
 543      ],
 544      "prompt_number": 80
 545     },
 546     {
 547      "cell_type": "code",
 548      "collapsed": false,
 549      "input": [
 550       "valid_direction(3, 3, 'N')"
 551      ],
 552      "language": "python",
 553      "metadata": {},
 554      "outputs": [
 555       {
 556        "metadata": {},
 557        "output_type": "pyout",
 558        "prompt_number": 81,
 559        "text": [
 560         "True"
 561        ]
 562       }
 563      ],
 564      "prompt_number": 81
 565     },
 566     {
 567      "cell_type": "code",
 568      "collapsed": false,
 569      "input": [
 570       "valid_direction(3, 3, 'NW')"
 571      ],
 572      "language": "python",
 573      "metadata": {},
 574      "outputs": [
 575       {
 576        "metadata": {},
 577        "output_type": "pyout",
 578        "prompt_number": 82,
 579        "text": [
 580         "True"
 581        ]
 582       }
 583      ],
 584      "prompt_number": 82
 585     },
 586     {
 587      "cell_type": "code",
 588      "collapsed": false,
 589      "input": [
 590       "valid_direction(3, 3, 'W')"
 591      ],
 592      "language": "python",
 593      "metadata": {},
 594      "outputs": [
 595       {
 596        "metadata": {},
 597        "output_type": "pyout",
 598        "prompt_number": 83,
 599        "text": [
 600         "True"
 601        ]
 602       }
 603      ],
 604      "prompt_number": 83
 605     },
 606     {
 607      "cell_type": "code",
 608      "collapsed": false,
 609      "input": [
 610       "valid_direction(3, 3, 'SW')"
 611      ],
 612      "language": "python",
 613      "metadata": {},
 614      "outputs": [
 615       {
 616        "metadata": {},
 617        "output_type": "pyout",
 618        "prompt_number": 84,
 619        "text": [
 620         "True"
 621        ]
 622       }
 623      ],
 624      "prompt_number": 84
 625     },
 626     {
 627      "cell_type": "code",
 628      "collapsed": false,
 629      "input": [
 630       "valid_direction(17, 17, 'N')"
 631      ],
 632      "language": "python",
 633      "metadata": {},
 634      "outputs": [
 635       {
 636        "metadata": {},
 637        "output_type": "pyout",
 638        "prompt_number": 85,
 639        "text": [
 640         "True"
 641        ]
 642       }
 643      ],
 644      "prompt_number": 85
 645     },
 646     {
 647      "cell_type": "code",
 648      "collapsed": false,
 649      "input": [
 650       "valid_direction(17, 17, 'NW')"
 651      ],
 652      "language": "python",
 653      "metadata": {},
 654      "outputs": [
 655       {
 656        "metadata": {},
 657        "output_type": "pyout",
 658        "prompt_number": 86,
 659        "text": [
 660         "True"
 661        ]
 662       }
 663      ],
 664      "prompt_number": 86
 665     },
 666     {
 667      "cell_type": "code",
 668      "collapsed": false,
 669      "input": [
 670       "valid_direction(17, 17, 'W')"
 671      ],
 672      "language": "python",
 673      "metadata": {},
 674      "outputs": [
 675       {
 676        "metadata": {},
 677        "output_type": "pyout",
 678        "prompt_number": 87,
 679        "text": [
 680         "True"
 681        ]
 682       }
 683      ],
 684      "prompt_number": 87
 685     },
 686     {
 687      "cell_type": "code",
 688      "collapsed": false,
 689      "input": [
 690       "valid_direction(17, 17, 'SW')"
 691      ],
 692      "language": "python",
 693      "metadata": {},
 694      "outputs": [
 695       {
 696        "metadata": {},
 697        "output_type": "pyout",
 698        "prompt_number": 89,
 699        "text": [
 700         "False"
 701        ]
 702       }
 703      ],
 704      "prompt_number": 89
 705     },
 706     {
 707      "cell_type": "markdown",
 708      "metadata": {},
 709      "source": [
 710       "## Now to solve the problem"
 711      ]
 712     },
 713     {
 714      "cell_type": "code",
 715      "collapsed": false,
 716      "input": [
 717       "best_product = 0\n",
 718       "for row in range(ROWS):\n",
 719       "    for column in range(COLUMNS):\n",
 720       "        for direction in DIRECTIONS:\n",
 721       "            if valid_direction(row, column, direction):\n",
 722       "                this_product = product(numbers(row, column, direction))\n",
 723       "                if this_product > best_product:\n",
 724       "                    best_product = this_product\n",
 725       "best_product"
 726      ],
 727      "language": "python",
 728      "metadata": {},
 729      "outputs": [
 730       {
 731        "metadata": {},
 732        "output_type": "pyout",
 733        "prompt_number": 94,
 734        "text": [
 735         "70600674"
 736        ]
 737       }
 738      ],
 739      "prompt_number": 94
 740     },
 741     {
 742      "cell_type": "code",
 743      "collapsed": false,
 744      "input": [
 745       "max(product(numbers(r, c, d)) \n",
 746       "     for r in range(ROWS) \n",
 747       "     for c in range(COLUMNS) \n",
 748       "     for d in DIRECTIONS \n",
 749       "     if valid_direction(r, c, d))"
 750      ],
 751      "language": "python",
 752      "metadata": {},
 753      "outputs": [
 754       {
 755        "metadata": {},
 756        "output_type": "pyout",
 757        "prompt_number": 101,
 758        "text": [
 759         "70600674"
 760        ]
 761       }
 762      ],
 763      "prompt_number": 101
 764     },
 765     {
 766      "cell_type": "markdown",
 767      "metadata": {},
 768      "source": [
 769       "# All the code in one place"
 770      ]
 771     },
 772     {
 773      "cell_type": "code",
 774      "collapsed": false,
 775      "input": [
 776       "ROWS = COLUMNS = 20\n",
 777       "SECTION_LEN = 4\n",
 778       "\n",
 779       "GRID_STRING = \"\"\"08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n",
 780       "49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n",
 781       "81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\n",
 782       "52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\n",
 783       "22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\n",
 784       "24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\n",
 785       "32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\n",
 786       "67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\n",
 787       "24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\n",
 788       "21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\n",
 789       "78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\n",
 790       "16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\n",
 791       "86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\n",
 792       "19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\n",
 793       "04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\n",
 794       "88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\n",
 795       "04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\n",
 796       "20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\n",
 797       "20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\n",
 798       "01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48\"\"\"\n",
 799       "\n",
 800       "GRID_LIST = [int(n) for n in GRID_STRING.split()]\n",
 801       "GRID = [GRID_LIST[i:i+COLUMNS] for i in range(0, ROWS * COLUMNS, COLUMNS)]\n",
 802       "\n",
 803       "# Directions, as the pair (difference-in-row, difference-in-column)\n",
 804       "DIRECTIONS = {'N': (-1, 0), 'NW': (-1, -1), 'W': (0, -1), 'SW': (1, -1)}\n",
 805       "\n",
 806       "def numbers(row, column, direction):\n",
 807       "    nums = []\n",
 808       "    dr, dc = DIRECTIONS[direction]\n",
 809       "    for _ in range(SECTION_LEN):\n",
 810       "        nums.append(GRID[row][column])\n",
 811       "        row += dr\n",
 812       "        column += dc\n",
 813       "    return nums\n",
 814       "\n",
 815       "def product(ns):\n",
 816       "    p = 1\n",
 817       "    for n in ns:\n",
 818       "        p *= n\n",
 819       "    return p\n",
 820       "\n",
 821       "def valid_direction(row, column, direction):\n",
 822       "    dr, dc = DIRECTIONS[direction]\n",
 823       "    end_row = row + dr * (SECTION_LEN -1)\n",
 824       "    end_col = column + dc * (SECTION_LEN -1)\n",
 825       "    if end_row >= 0 and end_row < ROWS and end_col >= 0 and end_col < COLUMNS:\n",
 826       "        return True\n",
 827       "    else:\n",
 828       "        return False\n",
 829       "\n",
 830       "max(product(numbers(r, c, d)) \n",
 831       "     for r in range(ROWS) \n",
 832       "     for c in range(COLUMNS) \n",
 833       "     for d in DIRECTIONS \n",
 834       "     if valid_direction(r, c, d))    "
 835      ],
 836      "language": "python",
 837      "metadata": {},
 838      "outputs": [
 839       {
 840        "metadata": {},
 841        "output_type": "pyout",
 842        "prompt_number": 102,
 843        "text": [
 844         "70600674"
 845        ]
 846       }
 847      ],
 848      "prompt_number": 102
 849     },
 850     {
 851      "cell_type": "code",
 852      "collapsed": false,
 853      "input": [],
 854      "language": "python",
 855      "metadata": {},
 856      "outputs": []
 857     }
 858    ],
 859    "metadata": {}
 860   }
 861  ]
 862 }