/day06.ipynb Secret
Created
December 6, 2021 12:41
Revisions
-
TheShallowOne created this gist
Dec 6, 2021 .There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,292 @@ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Advent of Code - Day 6 - Lanternfish\n", "\n", "- Fishes are initialized with an internal counter.\n", "- Every day this counter decreases by `1`.\n", "- When it reaches `-1`, it gets reset to `6`. Additionally, a new fish is created with counter `8`." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Basics\n", "- Every calculation for fish with counter `x` and `d` days can be reduced to a fish with counter `0` and `d - x` days\n", "- This means a fish will create a new generation at the first day.\n", "\n", "### Example\n", "\n", "- Day -1: `0`\n", "- Day 0: `6 8`\n", "- Day 1: `5 7`\n", "- ...\n", "- Day 6: `0 2`\n", "- Day 7: `6 1 8`\n", "- Day 8: `5 0 7`\n", "- Day 9: `4 6 6 8`\n", "- ...\n", "- Day 13: `0 2 2 4`\n", "- Day 14: `6 1 1 3 8`\n", "- ...\n", "- Day 16: `4 6 6 1 6 8 8`\n", "\n", "## Theory" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Generation 0\n", "\n", "- This will generate the first child at day **0**, and then `1` every **7th** day.\n", "\n", "=> Count $\\left \\lfloor{\\frac{d}{7}}\\right \\rfloor + 1$\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Generation 1\n", "\n", "- The first of this is spawned at day **0**\n", "- The next ones are spawned on day **7**, **14** and so on\n", "- On day **9**, this will create `1` child\n", "- On day **16 = 9+7**, this will create `2` children (`3` total)\n", "- On day **23 = 9+14**, this will create `3` children (`6` total)\n", "\n", "=> Number of steps $n = \\left \\lfloor{\\frac{d - 9}{7}}\\right \\rfloor + 1$\n", "\n", "=> Count $1 + (1+1) + (1+1*2) + ... = \\frac{1}{2} n (n+1)$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Generation 2\n", "\n", "- The first of this is spawned at day **9**;\n", "- On day **16**, `2` more are added\n", "- On day **23**, `3` more are added and so on\n", "- On day **18 = 9+9**, this will create `1` child\n", "- On day **25 = 18+7**, this will create `3` children (`4` total)\n", "- On day **32 = 18+14**, this will create `5` children (`9` total)\n", "\n", "=> Number of steps $n = \\left \\lfloor{\\frac{d - 18}{7}}\\right \\rfloor + 1$\n", "\n", "=> Count $1 + (1+2) + (1+2*2) + ... = \\frac{1}{6} n (n+1)(n+2)$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Summary\n", "\n", "- Days `d`\n", "- Generation `n`\n", "\n", "Number of steps in generation: $s_n = \\left \\lfloor{\\frac{d - 9*n}{7}}\\right \\rfloor + 1$\n", "\n", "Total members: $c_n = \\prod_{i=0}^{n}{\\frac{1}{1+i}(s_n+i)}$" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Days 10\n", " Gen: 0 - Count: 2\n", " Gen: 1 - Count: 1\n", "Days 50\n", " Gen: 0 - Count: 8\n", " Gen: 1 - Count: 21\n", " Gen: 2 - Count: 35\n", " Gen: 3 - Count: 35\n", " Gen: 4 - Count: 21\n", " Gen: 5 - Count: 1\n", "Days 100\n", " Gen: 0 - Count: 15\n", " Gen: 1 - Count: 105\n", " Gen: 2 - Count: 364\n", " Gen: 3 - Count: 1001\n", " Gen: 4 - Count: 2002\n", " Gen: 5 - Count: 1716\n", " Gen: 6 - Count: 1716\n", " Gen: 7 - Count: 1287\n", " Gen: 8 - Count: 715\n", " Gen: 9 - Count: 66\n", " Gen: 10 - Count: 12\n", " Gen: 11 - Count: 1\n" ] } ], "source": [ "def number_in_generation(generation, days):\n", " if days < 9 * generation:\n", " return 0\n", "\n", " steps = (days - 9 * generation) // 7 + 1\n", " count = 1\n", " for i in range(0, generation + 1):\n", " count = count * (steps + i) // (1 + i)\n", " \n", " return count\n", "\n", "for days in (10, 50, 100):\n", " print(\"Days\", days)\n", " for gen in range(days):\n", " num = number_in_generation(gen, days)\n", " if num == 0:\n", " break\n", " print(\" Gen:\", gen, \"- Count:\", num)\n" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0 - 107\n", "1 - 106\n", "2 - 86\n", "3 - 86\n", "4 - 71\n", "5 - 70\n", "6 - 64\n" ] } ], "source": [ "def calculate_total(days):\n", " count = 1\n", " for gen in range(days):\n", " num = number_in_generation(gen, days)\n", " if num == 0:\n", " break\n", " count += num\n", " return count\n", "\n", "def calculate_with_offset(startvalue, days):\n", " days -= startvalue\n", " if days <= 0:\n", " return 1\n", " else:\n", " return calculate_total(days-1)\n", "\n", "for i in range(0, 7):\n", " print(i, \" - \", calculate_with_offset(i, 50))\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Part 1\n", "\n", "- Test-Input: `3,4,3,1,2`\n", "- Days: `80`" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1154, 1034, 1154, 1401, 1191]\n", "Result 5934\n" ] } ], "source": [ "input = [3, 4, 3, 1, 2]\n", "days = 80\n", "\n", "counts = [calculate_with_offset(x, days) for x in input]\n", "print(counts)\n", "\n", "print(\"Result\", sum(counts))\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Part 2\n", "\n", "- Same Test-Input: `3,4,3,1,2`\n", "- Days: `256`" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[5217223242, 4726100874, 5217223242, 6206821033, 5617089148]\n", "Result 26984457539\n" ] } ], "source": [ "input = [3, 4, 3, 1, 2]\n", "days = 256\n", "\n", "counts = [calculate_with_offset(x, days) for x in input]\n", "print(counts)\n", "\n", "print(\"Result\", sum(counts))\n" ] } ], "metadata": { "interpreter": { "hash": "13d53c8face9a08fdb2882093b07b2652a2425aacf7a83c418b6a6c0253419ee" }, "kernelspec": { "display_name": "Python 3.10.0 64-bit", "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.10.0" }, "orig_nbformat": 4 }, "nbformat": 4, "nbformat_minor": 2 } This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,38 @@ input = [3, 4, 3, 1, 2] def number_in_generation(generation, days): if days < 9 * generation: return 0 steps = (days - 9 * generation) // 7 + 1 count = 1 for i in range(0, generation + 1): count = count * (steps + i) // (1 + i) return count def calculate_total(days): count = 1 for gen in range(days): num = number_in_generation(gen, days) if num == 0: break count += num return count def calculate_with_offset(startvalue, days): days -= startvalue if days <= 0: return 1 else: return calculate_total(days-1) def calculate(input, days): counts = [calculate_with_offset(x, days) for x in input] return sum(counts) part1 = calculate(input, 80) part2 = calculate(input, 256) print("Part 1:", part1) print("Part 2:", part2)