A counterexample to the exercise

adjacent_numbers.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "e2a76fe3-e7b8-4457-bdd6-37225ca5aef2",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "53c76d50-62cc-42ed-8769-8ff927d0ea8f",
   "metadata": {},
   "source": [
    "### 01 - Getting the Matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "974022a3-f01a-4bca-acac-13269ab8727f",
   "metadata": {},
   "outputs": [],
   "source": [
    "num = (\"\"\"\n",
    "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n",
    "49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n",
    "81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\n",
    "52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\n",
    "22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\n",
    "24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\n",
    "32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\n",
    "67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\n",
    "24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\n",
    "21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\n",
    "78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\n",
    "16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\n",
    "86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\n",
    "19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\n",
    "04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\n",
    "88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\n",
    "04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\n",
    "20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\n",
    "20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\n",
    "01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48\"\"\".replace(\"\\n\", \" \"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "10406a47-6e4e-4a99-a0e9-94094df34d66",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = np.fromstring(num, dtype=np.int64, sep=' ').reshape(20, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "8a488f60-103a-4140-8bcc-d07147bf606e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(20, 20)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0ed5c778-cb44-4b4c-b9d3-452def410ed9",
   "metadata": {},
   "source": [
    "### 02 - Counterexample"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0afe4545-a212-49fd-bb70-7a158033ab81",
   "metadata": {},
   "source": [
    "It seems `48,477,312` is not the max product of 4 adjacent numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "279283a8-1536-49d0-9517-8ed5b3a81d49",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([66, 91, 88, 97])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x[6:10, 15]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "9c676458-da54-4798-8db5-636d8d14c8d0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "51267216"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.prod(x[6:10, 15])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c1f0351a-c2c4-4287-b3e7-2c7bf7c0d200",
   "metadata": {},
   "source": [
    "### 03 - Finding max along rows and columns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "2fd88bd9-f077-4463-b55d-f0880813eacd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sliding_window_view(arr, window_size=4):\n",
    "    \"\"\"\n",
    "    Returns all sequences of 4 adjacent numbers from a given 1-D array.\n",
    "    \"\"\"\n",
    "    shape = (arr.size - window_size + 1, window_size)\n",
    "    strides = (arr.strides[0], arr.strides[0])\n",
    "    return np.lib.stride_tricks.as_strided(arr, shape=shape, strides=strides)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "0eabdab0-fc28-487a-951a-d550f3e8db12",
   "metadata": {},
   "outputs": [],
   "source": [
    "def process_sequence(arr, window_size=4):\n",
    "    \"\"\"\n",
    "    Returns max product of 4 adjacent numbers from a given 1-D array.\n",
    "    \"\"\"\n",
    "    sequence = sliding_window_view(arr, window_size)\n",
    "    return np.max(np.prod(sequence, axis=1))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8dadc25e-5f54-4432-8034-9486251b2d4f",
   "metadata": {},
   "source": [
    "Let's process rows and columns of the given matrix. We may see that 48477312 and 51267216 are max along rows and columns respectively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "bb0102c1-e3cf-40b1-ae4e-96f6cf3f5a10",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 4204200, 13956768, 17696040,  7953400, 21149604, 12501216,\n",
       "       14942340, 27663636, 48477312,  6638874,  3427050, 13193840,\n",
       "       10615920, 12975312, 27896715, 21426363,  6785280, 37529514,\n",
       "       23740128, 22275540])"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.apply_along_axis(process_sequence, axis=1, arr=x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "f73f89c1-9240-4939-bc87-6180a1c2aa67",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "48477312"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# along rows\n",
    "np.max(np.apply_along_axis(process_sequence, axis=1, arr=x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "14f58eaf-8124-4ebc-8289-6ab83dc1e52c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 4540536, 14808780,  6414210, 35845044, 17712864, 25723980,\n",
       "       12837627,  6178914, 15785820, 30618244, 20304768, 10802142,\n",
       "       27832896, 14577860, 13171200, 51267216,  6153840, 13855698,\n",
       "       21710920, 35868960])"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# along colums\n",
    "np.apply_along_axis(process_sequence, axis=0, arr=x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "d8ca51e7-c1d7-4661-aab6-8bb03d0b22ef",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "51267216"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.max(np.apply_along_axis(process_sequence, axis=0, arr=x))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9896e791-dc99-4817-9750-4fc7c6bb45ed",
   "metadata": {},
   "source": [
    "### 04 - Finding the counterexample"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "52edd0e5-9119-44af-9e11-e0edfc231538",
   "metadata": {},
   "source": [
    "First, let's find the column with the max product."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "04d6cf8c-071b-45f2-904f-ebdd16456c47",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.argmax(np.apply_along_axis(process_sequence, axis=0, arr=x))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19398470-b742-4fce-a1b2-797a2fe0689e",
   "metadata": {},
   "source": [
    "Now let's build a sequence of adjacent numbers and find the one with the max product."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "4574cdeb-c55e-471d-821c-0e93dc9f1f4b",
   "metadata": {},
   "outputs": [],
   "source": [
    "sequence = sliding_window_view(x[:, 15])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "c60fccd4-1d89-4760-9fe0-c315d1132899",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[12, 48,  3, 71],\n",
       "       [48,  3, 71, 28],\n",
       "       [ 3, 71, 28, 20],\n",
       "       [71, 28, 20, 66],\n",
       "       [28, 20, 66, 91],\n",
       "       [20, 66, 91, 88],\n",
       "       [66, 91, 88, 97],\n",
       "       [91, 88, 97, 14],\n",
       "       [88, 97, 14, 24],\n",
       "       [97, 14, 24, 58],\n",
       "       [14, 24, 58, 77],\n",
       "       [24, 58, 77, 79],\n",
       "       [58, 77, 79, 32],\n",
       "       [77, 79, 32, 32],\n",
       "       [79, 32, 32, 85],\n",
       "       [32, 32, 85, 16],\n",
       "       [32, 85, 16,  1]])"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sequence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "7d28eb02-ab00-429e-a151-2a5d755bfc86",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.argmax(np.prod(sequence, axis=1))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12ac3a0a-7380-4915-b6e1-02353d46d686",
   "metadata": {},
   "source": [
    "And this is our sequence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "7bbb4131-ec42-458d-93ed-ebdf19486f39",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([66, 91, 88, 97])"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sequence[6]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "47979006-42ab-4934-94e7-ae0ee682838d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "51267216"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.prod(sequence[6])"
   ]
  }
 ],
 "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.11.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}