{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "49450d64-7237-43ac-af2f-39f04d005881",
   "metadata": {},
   "source": [
    "[Discussions](https://discu.eu/q/https://youtu.be/ea7ljkehyta) about Conway's video."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "rubber-painting",
   "metadata": {},
   "source": [
    "Memory allocation is the slowest part. We estimate the upper bound of the length of the nth sequence and preallocate two lists with the needed space and compute the new sequence populating each time the other list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "productive-narrative",
   "metadata": {},
   "outputs": [],
   "source": [
    "def look_and_say(current, new):\n",
    "    prev_d = current[0]\n",
    "    run_len = 0\n",
    "    new_i = 0\n",
    "    for d in current:\n",
    "        if d != prev_d:\n",
    "            new[new_i] = run_len\n",
    "            new[new_i+1] = prev_d\n",
    "            new_i += 2\n",
    "            run_len = 0\n",
    "            prev_d = d\n",
    "            if d == 0:\n",
    "                break\n",
    "\n",
    "        run_len += 1\n",
    "\n",
    "def estimate_length(times):\n",
    "    λ = 1.30357726903429639125709911215255189073070250465940487575486139062855088785246155712681576686442522555\n",
    "    return λ**times"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "b931cc74-2d63-4bd5-8717-073dd02934e5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5103798"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "times = 50\n",
    "upper_bound = int(10 * estimate_length(times))\n",
    "\n",
    "sequence = [0]*upper_bound\n",
    "sequence[0:10] = [1,1,1,3,1,2,2,1,1,3]\n",
    "tmp = [0]*upper_bound\n",
    "\n",
    "for _ in range(times): \n",
    "    look_and_say(sequence, tmp)\n",
    "    sequence, tmp = tmp, sequence\n",
    "\n",
    "# remove trailing 0s\n",
    "sequence = sequence[:sequence.index(0)]\n",
    "\n",
    "len(sequence)"
   ]
  }
 ],
 "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.11.4"
  },
  "title": "Elves Look, Elves Say"
 },
 "nbformat": 4,
 "nbformat_minor": 5
}