4 "signature": "sha256:2513cb86760ebf975b3dce5f7884ee5e23c13f94e20cc9af8fc245f251455fda"
12 "cell_type": "markdown",
15 "## Project Euler problem 11\n",
16 "Find the largest product of four adjacent numbers in the grid."
20 "cell_type": "markdown",
30 "ROWS = COLUMNS = 20\n",
39 "cell_type": "markdown",
43 "Convert the text of the numbers into a 2d array of integers.\n",
45 "(Alterntive data structures include a 1d list of integers, or a dict with keys of (r, c) pairs.)"
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",
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)]"
92 "output_type": "stream",
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"
121 "cell_type": "markdown",
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",
127 "`directions` stores those directions, and how to move in the direction."
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)}"
137 "language": "python",
143 "cell_type": "markdown",
146 "## Finding the right numbers\n",
147 "Given a starting position and a direction, find the right numbers.\n",
150 "Should we worry if the request goes out of the bounds of the grid?"
157 "def numbers(row, column, direction):\n",
159 " dr, dc = DIRECTIONS[direction]\n",
160 " for _ in range(SECTION_LEN):\n",
161 " nums.append(GRID[row][column])\n",
166 "language": "python",
172 "cell_type": "markdown",
184 "language": "python",
189 "output_type": "pyout",
204 "language": "python",
209 "output_type": "pyout",
222 "numbers(3, 3, 'NW')"
224 "language": "python",
229 "output_type": "pyout",
242 "numbers(3, 3, 'SW')"
244 "language": "python",
249 "output_type": "pyout",
259 "cell_type": "markdown",
262 "## Product of a list"
269 "def product(ns):\n",
275 "language": "python",
284 "product(numbers(0, 3, 'W'))"
286 "language": "python",
291 "output_type": "pyout",
306 "language": "python",
311 "output_type": "pyout",
321 "cell_type": "markdown",
324 "## What directions don't take us out outside of the boundaries?"
331 "def valid_direction_explicit(row, column, direction):\n",
332 " if direction == 'N' and row >= SECTION_LEN -1:\n",
334 " elif direction == 'W' and column >= SECTION_LEN -1:\n",
336 " elif direction == 'NW' and row >= SECTION_LEN -1 and column >= SECTION_LEN -1:\n",
338 " elif direction == 'SW' and row + SECTION_LEN <= ROWS and column >= SECTION_LEN -1:\n",
343 "language": "python",
352 "valid_direction_explicit(0, 0, 'N')"
354 "language": "python",
359 "output_type": "pyout",
372 "valid_direction_explicit(5, 5, 'N')"
374 "language": "python",
379 "output_type": "pyout",
392 "valid_direction_explicit(5, 5, 'NW')"
394 "language": "python",
399 "output_type": "pyout",
412 "valid_direction_explicit(5, 5, 'W')"
414 "language": "python",
419 "output_type": "pyout",
432 "valid_direction_explicit(5, 5, 'SW')"
434 "language": "python",
439 "output_type": "pyout",
452 "valid_direction_explicit(17, 5, 'SW')"
454 "language": "python",
459 "output_type": "pyout",
472 "valid_direction_explicit(16, 5, 'SW')"
474 "language": "python",
479 "output_type": "pyout",
492 "valid_direction_explicit(2, 2, 'NW')"
494 "language": "python",
499 "output_type": "pyout",
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",
521 "language": "python",
530 "valid_direction(0, 0, 'N')"
532 "language": "python",
537 "output_type": "pyout",
550 "valid_direction(3, 3, 'N')"
552 "language": "python",
557 "output_type": "pyout",
570 "valid_direction(3, 3, 'NW')"
572 "language": "python",
577 "output_type": "pyout",
590 "valid_direction(3, 3, 'W')"
592 "language": "python",
597 "output_type": "pyout",
610 "valid_direction(3, 3, 'SW')"
612 "language": "python",
617 "output_type": "pyout",
630 "valid_direction(17, 17, 'N')"
632 "language": "python",
637 "output_type": "pyout",
650 "valid_direction(17, 17, 'NW')"
652 "language": "python",
657 "output_type": "pyout",
670 "valid_direction(17, 17, 'W')"
672 "language": "python",
677 "output_type": "pyout",
690 "valid_direction(17, 17, 'SW')"
692 "language": "python",
697 "output_type": "pyout",
707 "cell_type": "markdown",
710 "## Now to solve the problem"
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",
727 "language": "python",
732 "output_type": "pyout",
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))"
751 "language": "python",
756 "output_type": "pyout",
757 "prompt_number": 101,
766 "cell_type": "markdown",
769 "# All the code in one place"
776 "ROWS = COLUMNS = 20\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",
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",
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",
806 "def numbers(row, column, direction):\n",
808 " dr, dc = DIRECTIONS[direction]\n",
809 " for _ in range(SECTION_LEN):\n",
810 " nums.append(GRID[row][column])\n",
815 "def product(ns):\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",
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)) "
836 "language": "python",
841 "output_type": "pyout",
842 "prompt_number": 102,
854 "language": "python",