Project Euler Q4 - LO Man Hei

Download notebook

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c2470291-6ce0-4d26-b123-40807c58efc3",
   "metadata": {},
   "source": [
    "### Q4\n",
    "Find the largest palindrome made from the product of two 3-digit numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "de3c691e-e79d-4885-baf5-c15e7c36c09a",
   "metadata": {},
   "outputs": [],
   "source": [
    "#Very simple but stupid. It needs to loop through all combinations\n",
    "def largest_palindrome_0(max_range):\n",
    "    step_count = 0\n",
    "    result = 0\n",
    "    for x in range(max_range,-1,-1):\n",
    "        for y in range(max_range,-1,-1):\n",
    "            product_str = str(x*y)\n",
    "            step_count += 1\n",
    "            if product_str == product_str[::-1]:\n",
    "                if int(product_str) > result:\n",
    "                    result = int(product_str)\n",
    "    print(f\"step_count={step_count}\")\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "acf10b9e-4497-495e-b09d-436cd9029de8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "step_count=1000000\n",
      "CPU times: user 163 ms, sys: 327 µs, total: 163 ms\n",
      "Wall time: 161 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "906609"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "largest_palindrome_0(999)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "11f95458-b634-4f2f-809e-c1651a98a5fe",
   "metadata": {},
   "outputs": [],
   "source": [
    "#Slightly smarter. Counting down for each digit, i.e. step_10: x,y = 999,990, step_11: x,y = 998,999\n",
    "#It needs hard coding for the num of digits, and is less flexible.\n",
    "def largest_palindrome_1():\n",
    "    step_count = 0\n",
    "    record_y = 0\n",
    "    result = 0\n",
    "    for x_i in range(9,-1,-1):\n",
    "        for y_i in range(9,-1,-1):\n",
    "            for x_j in range(9,-1,-1):\n",
    "                for y_j in range(9,-1,-1):\n",
    "                    for x_k in range(9,-1,-1):\n",
    "                        for y_k in range(9,-1,-1):\n",
    "                            x = 100*x_i+10*x_j+x_k\n",
    "                            y = 100*y_i+10*y_j+y_k\n",
    "                            product_str = str(x*y)\n",
    "                            step_count += 1\n",
    "                            if product_str == product_str[::-1] and int(product_str) > result:\n",
    "                                result = int(product_str)\n",
    "                                record_y = y\n",
    "                            #when x < record_y, we can guarantee the max palindrome already in our record    \n",
    "                            if x < record_y:\n",
    "                                print(f\"step_count={step_count}\")\n",
    "                                return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "2cc69575-74fd-4c85-8542-ef1abff70562",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "step_count=8071\n",
      "CPU times: user 1.83 ms, sys: 312 µs, total: 2.14 ms\n",
      "Wall time: 2.14 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "906609"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "largest_palindrome_1()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "c82f3932-07f4-4446-8968-b02ef58d0afa",
   "metadata": {},
   "outputs": [],
   "source": [
    "#The even smarter way. \n",
    "def split_combinations(n):\n",
    "    return [[i,n-i] for i in range(n) if 2*i<=n ] if n > 0 else [[0,0]]\n",
    "\n",
    "def largest_palindrome(max_range):\n",
    "    step_count = 0\n",
    "    result = 0\n",
    "    while step_count < 2*max_range:\n",
    "        step_split_combinations = split_combinations(step_count)[::-1]\n",
    "        if (max_range-step_split_combinations[0][0])*(max_range-step_split_combinations[0][1]) < result:\n",
    "            #we can guarantee the max palindrome already in our record  \n",
    "            print(f\"step_count={step_count}\")\n",
    "            return result\n",
    "        for dx,dy in step_split_combinations: \n",
    "            x = max_range - dx\n",
    "            y = max_range - dy\n",
    "            product_str = str(x*y)\n",
    "            if product_str == product_str[::-1] and int(product_str) > result:\n",
    "                result = int(product_str)   \n",
    "        step_count += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "d36e0e2e-0bd2-4067-a4ef-423e11cc6a91",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "step_count=94\n",
      "CPU times: user 610 µs, sys: 119 µs, total: 729 µs\n",
      "Wall time: 731 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "906609"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "largest_palindrome(999)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "90ef5991-a41d-4197-9e7f-1dd02d98a8c7",
   "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