Euler 151 - Paper sheets.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Euler Problem 151\n",
    "=================\n",
    "\n",
    "\n",
    "A printing shop runs 16 batches (jobs) every week and each batch requires a sheet of special colour-proofing paper of size A5.\n",
    "\n",
    "Every Monday morning, the foreman opens a new envelope, containing a large sheet of the special paper with size A1.\n",
    "\n",
    "He proceeds to cut it in half, thus getting two sheets of size A2. Then he cuts one of them in half to get two sheets of size A3 and so on until he obtains the A5-size sheet needed for the first batch of the week.\n",
    "\n",
    "All the unused sheets are placed back in the envelope.\n",
    "\n",
    "\n",
    "At the beginning of each subsequent batch, he takes from the envelope one sheet of paper at random. If it is of size A5, he uses it. If it is larger, he repeats the 'cut-in-half' procedure until he has what he needs and any remaining sheets are always placed back in the envelope.\n",
    "\n",
    "Excluding the first and last batch of the week, find the expected number of times (during each week) that the foreman finds a single sheet of paper in the envelope.\n",
    "\n",
    "Give your answer rounded to six decimal places using the format x.xxxxxx ."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.464399\n"
     ]
    }
   ],
   "source": [
    "remember = {}\n",
    "\n",
    "def cut_paper(v = [0,0,0,0,1], n = 16):\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    strv = str(v)\n",
    "    if strv in remember:\n",
    "        return remember[strv]\n",
    "    sv = sum(v)\n",
    "    if sv == 1:\n",
    "        answer = 1\n",
    "    else:\n",
    "        answer = 0\n",
    "    for i in range(len(v)):\n",
    "        if v[i]:\n",
    "            v1 = v[:]\n",
    "            for j in range(i):\n",
    "                v1[j] += 1\n",
    "            v1[i] -= 1\n",
    "            answer += 1.0*v[i]/sv * cut_paper(v1, n-1)\n",
    "    remember[strv] = answer\n",
    "    return answer\n",
    "\n",
    "print (\"%.6f\" % (cut_paper() - 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note:** Old code, should be updated."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}