eulerbooks/notebooks/problem0093.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "89053792",
   "metadata": {},
   "source": [
    "# [Arithmetic Expressions](https://projecteuler.net/problem=93)\n",
    "\n",
    "We can brute force this answer.\n",
    "\n",
    "There are five ways to place the parentheses in an expression with four numbers (I'm only using addition here, but obviously you could use any operators):\n",
    "* $((a+b)+c)+d$\n",
    "* $(a+(b+c))+d$\n",
    "* $a+((b+c)+d)$\n",
    "* $a+(b+(c+d))$\n",
    "* $(a+b)+(c+d)$\n",
    "\n",
    "(It turns out that the number of ways to place the parentheses around $n$ numbers is $C_{n-1}$, where $C_n$ is the $n$th [Catalan number](https://en.wikipedia.org/wiki/Catalan_number).)\n",
    "\n",
    "If we iterate through every possible permutation of four digits, along with every possible set of three operators, and evaluate using each of the five possible groupings, we can get every number that can be formed from four digits under the problem's rules.\n",
    "\n",
    "Here's a function to find the longest streak of positive integers you can form from four digits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "0d75c8ce",
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import product, permutations, count\n",
    "from operator import add, sub, mul, truediv\n",
    "\n",
    "def streak(digits):\n",
    "    targets = set()\n",
    "    for (a, b, c, d) in permutations(digits):\n",
    "        for (op1, op2, op3) in product((add, sub, mul, truediv), repeat=3):\n",
    "            try:\n",
    "                targets.add(op3(op2(op1(a, b), c), d))\n",
    "            except ZeroDivisionError:\n",
    "                pass\n",
    "            \n",
    "            try:\n",
    "                targets.add(op3(op2(a, op1(b, c)), d))\n",
    "            except ZeroDivisionError:\n",
    "                pass\n",
    "            \n",
    "            try:\n",
    "                targets.add(op3(a, op2(op1(b, c), d)))\n",
    "            except ZeroDivisionError:\n",
    "                pass\n",
    "            \n",
    "            try:\n",
    "                targets.add(op3(a, op2(b, op1(c, d))))\n",
    "            except ZeroDivisionError:\n",
    "                pass\n",
    "            \n",
    "            try:\n",
    "                targets.add(op3(op1(a, b), op2(c, d)))\n",
    "            except ZeroDivisionError:\n",
    "                pass\n",
    "            \n",
    "    for n in count(1):\n",
    "        if n not in targets:\n",
    "            return n - 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7ef3f5d3",
   "metadata": {},
   "source": [
    "Now we just try every combination of four digits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "90d4d5dd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 2, 5, 8)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import combinations\n",
    "\n",
    "max(combinations(range(0, 10), 4), key=streak)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eda00caf",
   "metadata": {},
   "source": [
    "Under the problem's rules, these numbers can form all the positive integers up to 51."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "735dab1c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "51"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "streak((1,2,5,8))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e56a1679",
   "metadata": {},
   "source": [
    "## Relevant sequences\n",
    "* Catalan numbers: [A000108](https://oeis.org/A000108)\n",
    "\n",
    "#### Copyright (C) 2025 filifa\n",
    "\n",
    "This work is licensed under the [Creative Commons Attribution-ShareAlike 4.0 International license](https://creativecommons.org/licenses/by-sa/4.0/) and the [BSD Zero Clause license](https://spdx.org/licenses/0BSD.html)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.5",
   "language": "sage",
   "name": "sagemath"
  },
  "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}