razimantv/covfefe.ipynb

## covfefe.ipynb
{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solving the covfefe problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Define $f_i$ to be the expected number of further keypresses required if you have already managed a prefix of length $i$.\n",
    "\n",
    "First, define the variables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[f_{0}, f_{1}, f_{2}, f_{3}, f_{4}, f_{5}, f_{6}, f_{7}\\right]</script></html>"
      ],
      "text/plain": [
       "[f0, f1, f2, f3, f4, f5, f6, f7]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%display latex\n",
    "f=list(var('f%d' % i) for i in (0..7));\n",
    "f"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What we want to find is $f_0$. We will do so by figuring out the relationships between the variables\n",
    "\n",
    "If we do not have a valid prefix, the probability is $\\frac{1}{26}$ that we hit C and obtain a valid prefix, and $\\frac{25}{26}$ that we do not."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}f_{0} = \\frac{25}{26} \\, f_{0} + \\frac{1}{26} \\, f_{1} + 1</script></html>"
      ],
      "text/plain": [
       "f0 == 25/26*f0 + 1/26*f1 + 1"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eq1 = [f[0] == 1+(f[1] + 25 * f[0])/26]\n",
    "eq1[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we have a prefix of length $l (0 < l < 7)$, the probability is $\\frac{1}{26}$ that we extend it successfully, $\\frac{1}{26}$ that we hit C and revert to a prefix of length 1, and $\\frac{24}{26}$ that we get an invalid prefix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}f_{1} = \\frac{12}{13} \\, f_{0} + \\frac{1}{26} \\, f_{1} + \\frac{1}{26} \\, f_{2} + 1 \\: \\cdots \\: f_{6} = \\frac{12}{13} \\, f_{0} + \\frac{1}{26} \\, f_{1} + \\frac{1}{26} \\, f_{7} + 1</script></html>"
      ],
      "text/plain": [
       "f_{1} = \\frac{12}{13} \\, f_{0} + \\frac{1}{26} \\, f_{1} + \\frac{1}{26} \\, f_{2} + 1 \\: \\cdots \\: f_{6} = \\frac{12}{13} \\, f_{0} + \\frac{1}{26} \\, f_{1} + \\frac{1}{26} \\, f_{7} + 1"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "eq2=[f[i] == 1 + (f[i+1] + f[1] + 24 * f[0])/26 for i in range(1,7)]\n",
    "show(latex(eq2[0])+ '\\: \\cdots \\:' + latex (eq2[5]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, $f_7$ is 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}f_{7} = 0</script></html>"
      ],
      "text/plain": [
       "f7 == 0"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eq3 = [f[7] == 0]\n",
    "eq3[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now solve the equation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}f_{0} = 8031810176</script></html>"
      ],
      "text/plain": [
       "f0 == 8031810176"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = solve(eq1 + eq2 + eq3, f)\n",
    "s[0][0]"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 8.1",
   "language": "",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
	{
	"cells": [
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"# Solving the covfefe problem"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"Define $f_i$ to be the expected number of further keypresses required if you have already managed a prefix of length $i$.\n",
	"\n",
	"First, define the variables"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 1,
	"metadata": {},
	"outputs": [
	{
	"data": {
	"text/html": [
	"<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[f_{0}, f_{1}, f_{2}, f_{3}, f_{4}, f_{5}, f_{6}, f_{7}\\right]</script></html>"
	],
	"text/plain": [
	"[f0, f1, f2, f3, f4, f5, f6, f7]"
	]
	},
	"execution_count": 1,
	"metadata": {},
	"output_type": "execute_result"
	}
	],
	"source": [
	"%display latex\n",
	"f=list(var('f%d' % i) for i in (0..7));\n",
	"f"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"What we want to find is $f_0$. We will do so by figuring out the relationships between the variables\n",
	"\n",
	"If we do not have a valid prefix, the probability is $\\frac{1}{26}$ that we hit C and obtain a valid prefix, and $\\frac{25}{26}$ that we do not."
	]
	},
	{
	"cell_type": "code",
	"execution_count": 2,
	"metadata": {},
	"outputs": [
	{
	"data": {
	"text/html": [
	"<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}f_{0} = \\frac{25}{26} \\, f_{0} + \\frac{1}{26} \\, f_{1} + 1</script></html>"
	],
	"text/plain": [
	"f0 == 25/26f0 + 1/26f1 + 1"
	]
	},
	"execution_count": 2,
	"metadata": {},
	"output_type": "execute_result"
	}
	],
	"source": [
	"eq1 = [f[0] == 1+(f[1] + 25 * f[0])/26]\n",
	"eq1[0]"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"If we have a prefix of length $l (0 < l < 7)$, the probability is $\\frac{1}{26}$ that we extend it successfully, $\\frac{1}{26}$ that we hit C and revert to a prefix of length 1, and $\\frac{24}{26}$ that we get an invalid prefix."
	]
	},
	{
	"cell_type": "code",
	"execution_count": 3,
	"metadata": {},
	"outputs": [
	{
	"data": {
	"text/html": [
	"<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}f_{1} = \\frac{12}{13} \\, f_{0} + \\frac{1}{26} \\, f_{1} + \\frac{1}{26} \\, f_{2} + 1 \\: \\cdots \\: f_{6} = \\frac{12}{13} \\, f_{0} + \\frac{1}{26} \\, f_{1} + \\frac{1}{26} \\, f_{7} + 1</script></html>"
	],
	"text/plain": [
	"f_{1} = \\frac{12}{13} \\, f_{0} + \\frac{1}{26} \\, f_{1} + \\frac{1}{26} \\, f_{2} + 1 \\: \\cdots \\: f_{6} = \\frac{12}{13} \\, f_{0} + \\frac{1}{26} \\, f_{1} + \\frac{1}{26} \\, f_{7} + 1"
	]
	},
	"metadata": {},
	"output_type": "display_data"
	}
	],
	"source": [
	"eq2=[f[i] == 1 + (f[i+1] + f[1] + 24 * f[0])/26 for i in range(1,7)]\n",
	"show(latex(eq2[0])+ '\\: \\cdots \\:' + latex (eq2[5]))"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"Finally, $f_7$ is 0."
	]
	},
	{
	"cell_type": "code",
	"execution_count": 4,
	"metadata": {},
	"outputs": [
	{
	"data": {
	"text/html": [
	"<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}f_{7} = 0</script></html>"
	],
	"text/plain": [
	"f7 == 0"
	]
	},
	"execution_count": 4,
	"metadata": {},
	"output_type": "execute_result"
	}
	],
	"source": [
	"eq3 = [f[7] == 0]\n",
	"eq3[0]"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"Now solve the equation"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 5,
	"metadata": {},
	"outputs": [
	{
	"data": {
	"text/html": [
	"<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}f_{0} = 8031810176</script></html>"
	],
	"text/plain": [
	"f0 == 8031810176"
	]
	},
	"execution_count": 5,
	"metadata": {},
	"output_type": "execute_result"
	}
	],
	"source": [
	"s = solve(eq1 + eq2 + eq3, f)\n",
	"s[0][0]"
	]
	}
	],
	"metadata": {
	"kernelspec": {
	"display_name": "SageMath 8.1",
	"language": "",
	"name": "sagemath"
	},
	"language_info": {
	"codemirror_mode": {
	"name": "ipython",
	"version": 2
	},
	"file_extension": ".py",
	"mimetype": "text/x-python",
	"name": "python",
	"nbconvert_exporter": "python",
	"pygments_lexer": "ipython2",
	"version": "2.7.14"
	}
	},
	"nbformat": 4,
	"nbformat_minor": 2
	}