Project Euler Q11 - LO Man Hei

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
}

Loading