Home
About
Resume
Projects
Links
Blog
Download notebook
{ "cells": [ { "cell_type": "markdown", "id": "31537bc2-3760-45aa-82e1-7e1764ae19c6", "metadata": {}, "source": [ "### Q11\n", "What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the \\(20 \\times 20\\) grid?" ] }, { "cell_type": "code", "execution_count": 1, "id": "3ed57f7f-dc11-4c66-a8ab-309f611acf56", "metadata": {}, "outputs": [], "source": [ "num_string = \"08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48\"" ] }, { "cell_type": "code", "execution_count": 2, "id": "3a02d67d-4dab-408a-ab69-e7dcee6ef62d", "metadata": {}, "outputs": [], "source": [ "def prod(x_vector):\n", " result = 1\n", " for i in x_vector:\n", " result *= i\n", " return result\n", "\n", "def diag_eles(idx):\n", " return [[i,idx-i] for i in range(idx+1) ] if idx > 0 else [[0,0]]\n", "\n", "def rotate_matrix(m):\n", " return [[m[j][i] for j in range(len(m))] for i in range(len(m[0])-1,-1,-1)]\n", "\n", "def adjacent_product(num_list, len_adjacent):\n", " base_prod = prod([int(c) for c in num_list[:len_adjacent]])\n", " result = [base_prod]\n", " for i in range(1,len(num_list)-len_adjacent+1):\n", " result.append(result[i-1]*int(num_list[i+len_adjacent-1])//int(num_list[i-1]))\n", " return result\n", "\n", "def string_to_grid(num_string,dims):\n", " result = []\n", " splited_string = num_string.split(\" \") \n", " for i in range(dims[0]):\n", " row = []\n", " for j in range(dims[1]):\n", " idx = i*dims[1] + j\n", " row.append(int(splited_string[idx])) \n", " result.append(row)\n", " return result\n", "\n", "def get_collinear_ele(num_grid, direction):\n", " if direction == 0:\n", " return num_grid\n", " if direction == 1:\n", " nrow = len(num_grid)\n", " ncol = len(num_grid[0])\n", " return [[num_grid[j][i] for j in range(ncol)] for i in range(nrow)]\n", " if direction == 2:\n", " nrow = len(num_grid)\n", " ncol = len(num_grid[0])\n", " result = []\n", " for idx in range(nrow+ncol-1):\n", " result.append([num_grid[i][j] for i,j in diag_eles(idx) if i < nrow and j < ncol])\n", " return result\n", " if direction == 3:\n", " rotated_grid = rotate_matrix(num_grid)\n", " nrow = len(rotated_grid)\n", " ncol = len(rotated_grid[0])\n", " result = []\n", " for idx in range(nrow+ncol-1):\n", " result.append([rotated_grid[i][j] for i,j in diag_eles(idx) if i < nrow and j < ncol])\n", " return result\n", " \n", "def filtering_lines(lines,min_len):\n", " result = lines.copy()\n", " line_idx = len(result)-1\n", " while line_idx >= 0:\n", " if len(result[line_idx]) < min_len:\n", " result.pop(line_idx)\n", " line_idx -= 1\n", " continue\n", " if 0 in result[line_idx]:\n", " zero_loc = result[line_idx].index(0)\n", " current_line = result[line_idx].copy()\n", " splited_line = [current_line[:zero_loc],current_line[zero_loc+1:]]\n", " if len(splited_line[0]) >= min_len:\n", " result.insert(line_idx+1,splited_line[0])\n", " result[line_idx] = splited_line[1]\n", " continue\n", " line_idx -= 1\n", " return result\n", " \n", "def max_adjacent_prod_in_grid(num_string,dims,len_adjacent):\n", " num_grid = string_to_grid(num_string,dims)\n", " lines = []\n", " for i in range(4):\n", " lines += filtering_lines(get_collinear_ele(num_grid,i),len_adjacent)\n", " return max([max(adjacent_product(line,len_adjacent)) for line in lines]) " ] }, { "cell_type": "code", "execution_count": 3, "id": "f536a14b-8509-4161-bc2e-61247971f3d3", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 482 µs, sys: 134 µs, total: 616 µs\n", "Wall time: 617 µs\n" ] }, { "data": { "text/plain": [ "70600674" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%%time\n", "max_adjacent_prod_in_grid(num_string,[20,20],4)" ] }, { "cell_type": "code", "execution_count": null, "id": "c27b9ac2-69ec-49db-a2d7-b6932b213a69", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.10" } }, "nbformat": 4, "nbformat_minor": 5 }
Previous Notebook:
Project Euler Q10
Next Notebook:
Project Euler Q12
Loading