Round2.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "de700845-12ab-49a9-a61d-1d5984fda6bb",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import itertools\n",
    "import math"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c8dd7fe3-fd4e-4b61-b8f0-d8207c8c0a79",
   "metadata": {},
   "source": [
    "# Problem statement\n",
    "\n",
    "<p float=\"left\">\n",
    "  <img src=\"https://i.imgur.com/pNIA5Ua.png\" width=\"500\" />\n",
    "  <img src=\"https://i.imgur.com/DfE8CQW.png\" width=\"800\" /> \n",
    "</p>\n",
    "\n",
    "\n",
    "# Solution\n",
    "\n",
    "The state space has size $1+4+4^2+4^3+4^4 = 341$. It is small enough that optimal solutions can be found via bruteforce."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "3a72ed5c-a489-4cd1-a062-88abe753100a",
   "metadata": {},
   "outputs": [],
   "source": [
    "rates = np.array([[1, 1.41, 0.61, 2.08],\n",
    "                  [0.71, 1, 0.48, 1.52],\n",
    "                  [1.56, 2.05, 1, 3.26],\n",
    "                  [0.46, 0.64, 0.3, 1]\n",
    "                 ])\n",
    "products = {0:'Shell', 1:'Pizza', 2:'Wasabi', 3:'Snowball'}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "3060b277-e921-4134-9cec-be773514b49d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def amount(seq):\n",
    "    \"\"\"Compute the final amount after a sequence of trades, starting with 1 SeaShell.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    seq : list of int\n",
    "        List of intermediate products traded.\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    float\n",
    "        Payoff.\n",
    "    \"\"\"\n",
    "    if not seq:\n",
    "        return 1\n",
    "    prod = rates[0, seq[0]] * rates[seq[-1], 0]\n",
    "    L = len(seq)\n",
    "    for i in range(L-1):\n",
    "        prod *= rates[seq[i], seq[i+1]]\n",
    "    return prod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "7c21aad1-e572-4fcd-842c-085501c4a789",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maximize(L):\n",
    "    \"\"\"Among sequences of L intermediate products, compute the ones with greatest final amount.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    L : int\n",
    "        Number of intermediate products.\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    argmax : list of tuple\n",
    "        Optimal sequences of intermediate trades.\n",
    "    max_val : float\n",
    "        Maximal final amount for L intermediate products.\n",
    "    \"\"\"\n",
    "    seqs = itertools.product(*[range(0, 4) for _ in range(L)])\n",
    "    max_val = float('-inf')\n",
    "    argmax = []\n",
    "    for seq in seqs:\n",
    "        p = amount(seq)\n",
    "        if math.isclose(p, max_val):\n",
    "            argmax.append(seq)\n",
    "        elif p > max_val:\n",
    "            max_val = p\n",
    "            argmax = [seq]\n",
    "    return (argmax, max_val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "4816295f-42e2-4083-b51f-7ec65cd36194",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "([()], 1)\n",
      "([(1,)], 1.0010999999999999)\n",
      "([(1, 2)], 1.0558079999999999)\n",
      "([(0, 1, 2), (1, 1, 2), (1, 2, 0), (1, 2, 2)], 1.0558079999999999)\n",
      "([(1, 0, 1, 2), (1, 2, 0, 1)], 1.0569693887999996)\n"
     ]
    }
   ],
   "source": [
    "for L in range(0,5):\n",
    "    print(maximize(L))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eed21687-2770-41ed-8eb0-3eade8f0968e",
   "metadata": {},
   "source": [
    "It is therefore optimal to proceed with 4 intermediate products (5 trades in total).  \n",
    "Since the initial capital was $1$ SeaShell, `max_val - 1` is the rate of return. Thus the maximal return is $\\approx 5.7\\%$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "46a68e91-f1e7-4a47-83f9-e96a0e14a594",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimal sequences of trades:\n",
      "Shell -> Pizza -> Shell -> Pizza -> Wasabi -> Shell\n",
      "Shell -> Pizza -> Wasabi -> Shell -> Pizza -> Shell\n"
     ]
    }
   ],
   "source": [
    "argmax, _ = maximize(4)\n",
    "print(\"Optimal sequences of trades:\")\n",
    "for seq in argmax:\n",
    "    res = ' -> '.join([products[0]] + [products[i] for i in seq] + [products[0]])\n",
    "    print(res)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b0d4673b-bc7c-4abf-bab8-c93630e50f5d",
   "metadata": {},
   "source": [
    "# Results \n",
    "\n",
    "The outcome of this round was fully predictable, hence no surprise on the online judge.\n",
    "\n",
    "<img src=\"https://i.imgur.com/MMbtqjI.png\" width=\"900\" />\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7c7745db-c0fe-40f5-b58b-d7b44eb48b7a",
   "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.12.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}