Fiddler on the Proof: Fiddler (09/27/2024)

fiddler_20240927.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6479454d-d434-4808-a73d-01255eed4844",
   "metadata": {},
   "source": [
    "# Fiddler on the Proof\n",
    "\n",
    "Ravi Dayabhai & Conrad Warren 🦎 2024-09-27"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "52b23e3c-c3d9-4a10-87b0-8f3910e19419",
   "metadata": {},
   "source": [
    "## Problem\n",
    "\n",
    "From Jake Conway comes a question regarding a variant of a well-known game:\n",
    "\n",
    "In a game of “Rock, Paper, Scissors,” each element you can throw ties itself, beats one of the other elements, and loses to the remaining element. In particular, Rock beats Scissors beats Paper beats Rock.\n",
    "\n",
    "“Rock, Paper, Scissors, Lizard, Spock” (popularized via The Big Bang Theory) is similar, but has five elements you can throw instead of the typical three. Each element ties itself, beats another two, and loses to the remaining two. More specifically, Scissors beats Paper beats Rock beats Lizard beats Spock beats Scissors beats Lizard beats Paper beats Spock beats Rock beats Scissors.\n",
    "\n",
    "Three players are playing “Rock, Paper, Scissors, Lizard, Spock.” At the same time, they all put out their hands, revealing one of the five elements. If they each chose their element randomly and independently, what is the probability that one player is immediately victorious, having defeated the other two?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eaa13279-6073-4c6d-8fa7-e57145e55b49",
   "metadata": {},
   "source": [
    "## Solution\n",
    "\n",
    "\n",
    "The probability one player is immediately victorious is $\\frac{60}{125} = \\frac{12}{25}$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75277d57-d547-41e9-9813-88d90e03dc12",
   "metadata": {},
   "source": [
    "### Rationale\n",
    "\n",
    "Let the three players be $A$, $B$, and $C$. Without loss of generality, let $A$ be the immediate victor. For a given choice that $A$ makes, there are $2$ choices that $B$ or $C$ can make that would result in both losing to $A$. Therefore, there are $4$ outcomes (each with the same probability $\\frac{1}{25}$) given the choice $A$ made; hence, the probability that $A$ is the immediate victor given its choice is $\\frac{4}{25}$.\n",
    "\n",
    "Since $A$ can make any of $5$ choices uniformly, the probability that $A$ is the immediate victor is $\\frac{1}{5} \\cdot \\frac{4}{25} = \\frac{20}{125}$.\n",
    "\n",
    "By symmetry, the probability _single_ player is immediately victorious is $3 \\cdot \\frac{20}{125} = \\frac{60}{125} = \\frac{12}{25}$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2881ca6f-8752-4fa0-9a16-390ff41e14aa",
   "metadata": {},
   "source": [
    "## Extra Credit\n",
    "\n",
    "The rules for “Rock, Paper, Scissors” can concisely be written in one of the following three ways:\n",
    "\n",
    "- Rock beats Scissors beats Paper beats Rock\n",
    "- Scissors beats Paper beats Rock beats Scissors\n",
    "- Paper beats Rock beats Scissors beats Paper\n",
    "\n",
    "Each description of the rules includes four mentions of elements and three “beats.”\n",
    "\n",
    "Meanwhile, as previously mentioned, a similarly concise version of the rules for “Rock, Paper, Scissors, Lizard, Spock” (and adapted from the original site) is:\n",
    "\n",
    "> Scissors beats Paper beats Rock beats Lizard beats Spock beats Scissors beats Lizard beats Paper beats Spock beats Rock beats Scissors\n",
    "\n",
    "In this case, there are 11 mentions of elements and 10 “beats.” Including the one above, how many such ways are there to concisely describe the rules for “Rock, Paper, Scissors, Lizard, Spock?”"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a2bb6083-8e32-44b8-822a-014bf4b7fb5f",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "The number of ways to concisely describe the rules for “Rock, Paper, Scissors, Lizard, Spock?” is $110$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1842df6a-4ffb-4f5c-9b96-865bff3fbd99",
   "metadata": {},
   "source": [
    "### Rationale\n",
    "\n",
    "This problem reduces to counting the number of Eulerian cycles on the tournament graph where the vertices are the choices a player can make and the edges represent the \"beats\" relations among the vertices. Below, we leverage Hierholzer's algorithm on our tournament graph to count the valid permutations of our edge set.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "4ee477f7-0155-469a-98db-b968b81da767",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "110"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "# Represent our tournament graph\n",
    "V = [\"rock\", \"paper\", \"lizard\", \"scissors\", \"spock\"]\n",
    "E = [\n",
    "    (\"scissors\", \"paper\"), (\"scissors\", \"lizard\"), \n",
    "    (\"rock\", \"scissors\"), (\"rock\", \"lizard\"), \n",
    "    (\"paper\", \"rock\"), (\"paper\", \"spock\"),\n",
    "    (\"lizard\", \"spock\"), (\"lizard\", \"paper\"),\n",
    "    (\"spock\", \"scissors\"), (\"spock\", \"rock\")\n",
    "]\n",
    "\n",
    "\n",
    "def count_edge_permutations(vertices: list[str], edges: list[tuple[str, str]]) -> int:\n",
    "\n",
    "    G = defaultdict(set)\n",
    "    for winner, loser in E:\n",
    "        G[winner].add(loser)\n",
    "\n",
    "    traversed = set()\n",
    "    total = 0\n",
    "\n",
    "    # Implement Hierholzer's algorithm\n",
    "    def hierholzer(u: str) -> None:\n",
    "        nonlocal total\n",
    "        if len(traversed) == len(E):\n",
    "            total += 1\n",
    "            return\n",
    "        for v in G[u]:\n",
    "            if (u, v) not in traversed:\n",
    "                traversed.add((u, v))\n",
    "                hierholzer(v)\n",
    "                traversed.remove((u, v))\n",
    "\n",
    "    for u in vertices:\n",
    "        hierholzer(u)\n",
    "\n",
    "    return total\n",
    "\n",
    "\n",
    "count_edge_permutations(V, E)"
   ]
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}