From f0197028478b8fbc529908c44434c4e1cd3c7780 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Sun, 20 Dec 2015 17:23:08 +0000 Subject: [PATCH] Day 20 --- SIGNED.md | 29 +- advent-of-code-20.html | 153 ++++++++++ advent20-slow.ipynb | 672 +++++++++++++++++++++++++++++++++++++++++ advent20.ipynb | 191 ++++++++++++ 4 files changed, 1032 insertions(+), 13 deletions(-) create mode 100644 advent-of-code-20.html create mode 100644 advent20-slow.ipynb create mode 100644 advent20.ipynb diff --git a/SIGNED.md b/SIGNED.md index 62e275e..7c34f19 100644 --- a/SIGNED.md +++ b/SIGNED.md @@ -3,19 +3,19 @@ -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 -iQIcBAABCAAGBQJWdZ4XAAoJEJPB2e07Pgbqkl0P+wX8S9KzBWIBgCoUOx6kts7b -813IQGh5o89fEfBmGLBWlFYKZfhqy2CiruInuAlNSQGpiwp7vXgULnuxhAo3CNla -5fjv38uGY4M4SemJWv6bFxF6hE1MD5OfrTAPGqgHsoURFEC6TaSKQcl98CGKTKZo -l9syicV5+DFXW24n8PZzCInpPYaDiNrZXCDXzjBx3fQwXJC7RPYeTlqzGSs+af2L -J3vs0wDUoSPdERMXwQO/xoRKtSDh/dEZHKT8BobLFsLSUMwstWPQMhOur9+E/G2m -G9uQmZOWDo120PCngFXWu5aTEZbiDdQNlT8Pq1e93ShMQ/CCIiF5p0S2/CzzAwVo -QmiyjW7pifJMsj/ju81DRdbMUcLOqIWJ8MSPLvPzZR0g7j9fv+oA9chcpL/DvpT0 -6nsuE1jZeFYZDgEdgSUm8UHSZYRkP19b7gMZ0G6a59DjD6QoOfDR+tDfTNlVGt7z -SOMLUvBCIT9t91xMXSKjDzyJW/VepJd7y/kM8ZRHMb6ZZsyTtLYOpyT1FbOhz7z8 -SjDczb6KBWOZwLOguSlYvA4x296mG3F8hXikflyG7h+JCsUKSTpNBLgVuUxjno/M -/IOeVssd9iYhSJh/ddtBtMoe7Q+uY8tykstN4sqSZLD3n6Ldv/oqf8QpUSuzFmqs -mq8/g700Yz81x91bIAcG -=nL+C +iQIcBAABCAAGBQJWduQGAAoJEJPB2e07Pgbqz2IQAJ9DTWMKZeYcafZgy0q36wUR +X0hB4ocr0fqOYu0DSnMiw/dTO8iHhqavngTDrO+wcIXsm2zd3ImY6pABY6r111iA +ZCSBMZV5XJ5LtpDQRaTSbHqpNzj3DKxYAhxUH5Hc29oOt3tn900oCupdY6g+BUb9 +xHZQoGTJEhSVB8UuljCtTOBMOufusjjpuTa7d/bEHOkSPDryHysZJheWs3DKMU5W +yxQvVckyVV2Ke5qkpkGysQguyAbZxkyVey+gjEdtZVqnU+A8PNb099eOVMDzm5n8 +R8wc8wT+NuSwOmARrEcZjOYWM9CXDa7H3vYRXQpiiScGYoidB+clwpTq7SjmF5ik +krfGsmEFT95X5t9X3tVwFVuMdhDUGzNzuC4fgq79NJxqzXYQ5uv++I8EWPeTP5gd +r2YLMohJzHBT2odh5Xp6Vefcmrer0qwRz2GTj/mcrz4G9IqmOkzpK6tu0nXMMenM +M0oWAESeAYDJ/5PRJcEOQcQxhhCCfwYbEWklRiAhTZ0AMGoWklmz3Ru6B1bxUOIU +gm8g1RahzlXFfWSOq/+1x8yO1xAiGf0A9XsibDTatKex7DHQAjLySXeVxIof5J1X +9HEsd4dRtK6T4sRBYt90dFNb+HwBL0c3KmE+rmay+l+glVYYvaGOrXdRrDmV7J0o +LzHCVehOsol3p4Dyp3CO +=zX10 -----END PGP SIGNATURE----- ``` @@ -53,6 +53,7 @@ size exec file contents 5613 advent-of-code-17.html dc164050b1accefbbf8f2a8c13428df348bdc22d4293fcf4ef9fc6b74d38a227 7545 advent-of-code-18.html d41f47bada37cd3fb1be795a00a5ef7b6d78a8246f436441e37f94d64d18f677 7580 advent-of-code-19.html 9cd3b0a1a5a1dc658c09b46ba9624312622ac5cf46fffcaccbeea661b11c577e +6387 advent-of-code-20.html 3ec26a7cfb58a168b62781f097ebdb71ae3224cadde49588463370faaa3d33f9 109395 advent-of-code.ipynb 7292eeb9a8019f6931037c70105ab96bf691074dbe963736b6429cb4d4373f51 25607 advent01.ipynb c33ad39a77803a6870dd74998da98e3bb9c2c2db37c34167b330a01d663717e7 7001 advent01.txt 79312922877bdedd09ce0886a42b3d7f7ed092e2218579fb7d6ac1cb38cedebe @@ -89,6 +90,8 @@ size exec file contents 10099 advent18.txt 23d697796dfa397e22b925f850cf5a269802e307753a7a9a26e26ed7350a56a2 9745 advent19.ipynb 858c65e798916dd00403762a01ba6b3a55348f20e8ac927b52e700aa3cd9c073 968 advent19.txt eb333fc1d3ec41e3b9b22096e838fe860fbc6667068129996cae3cd3483dd9e7 +11722 advent20-slow.ipynb 780a5bb1e729e8fdf8b4c75f6fbad5aa53975dcc9a6d12ee699a2d488c7b7dc3 +3377 advent20.ipynb be9db2beee6805ac9db9f2dc145abba3275964e36e21580122bacd8436777a30 ``` #### Ignore diff --git a/advent-of-code-20.html b/advent-of-code-20.html new file mode 100644 index 0000000..dc320d7 --- /dev/null +++ b/advent-of-code-20.html @@ -0,0 +1,153 @@ + + + + +Day 20 - Advent of Code + + + + + + +

Advent of Code

Neil Smith 40*

+ +

+ + + + +

+ +

+

--- Day 20: Infinite Elves and Infinite Houses ---

To keep the Elves busy, Santa has them deliver some presents by hand, door-to-door. He sends them down a street with infinite houses numbered sequentially: 1, 2, 3, 4, 5, and so on.

+

Each Elf is assigned a number, too, and delivers presents to houses based on that number:

+

The first Elf (number 1) delivers presents to every house: 1, 2, 3, 4, 5, ....
The second Elf (number 2) delivers presents to every second house: 2, 4, 6, 8, 10, ....
Elf number 3 delivers presents to every third house: 3, 6, 9, 12, 15, ....

+

There are infinitely many Elves, numbered starting with 1. Each Elf delivers presents equal to ten times his or her number at each house.

+

So, the first nine houses on the street end up like this:

+

House 1 got 10 presents.
+House 2 got 30 presents.
+House 3 got 40 presents.
+House 4 got 70 presents.
+House 5 got 60 presents.
+House 6 got 120 presents.
+House 7 got 80 presents.
+House 8 got 150 presents.
+House 9 got 130 presents.
+

+

The first house gets 10 presents: it is visited only by Elf 1, which delivers 1 * 10 = 10 presents. The fourth house gets 70 presents, because it is visited by Elves 1, 2, and 4, for a total of 10 + 20 + 40 = 70 presents.

+

What is the lowest house number of the house to get at least as many presents as the number in your puzzle input?

+

+

Your puzzle answer was 776160.

--- Part Two ---

The Elves decide they don't want to visit an infinite number of houses. Instead, each Elf will stop after delivering presents to 50 houses. To make up for it, they decide to deliver presents equal to eleven times their number at each house.

+

With these changes, what is the new lowest house number of the house to get at least as many presents as the number in your puzzle input?

+

+

Your puzzle answer was 786240.

Both parts of this puzzle are complete! They provide two gold stars: **

+

At this point, you should return to your advent calendar and try another puzzle.

+

Your puzzle input was 33100000.

+

You can also [Shareon + Twitter + Google+ + Reddit] + this puzzle.

+

+ + + + + + diff --git a/advent20-slow.ipynb b/advent20-slow.ipynb new file mode 100644 index 0000000..53594ae --- /dev/null +++ b/advent20-slow.ipynb @@ -0,0 +1,672 @@ +{ + "cells": [ + { + "cell_type": "code", + "execution_count": 1, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "from functools import lru_cache, reduce\n", + "from itertools import groupby\n", + "import operator\n", + "\n", + "import sys\n", + "sys.setrecursionlimit(1000000)" + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "target = 33100000" + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def sieve(n):\n", + " primes = (2,3,5)\n", + " i = 7\n", + " while i <= n:\n", + " if not any(i % p == 0 for p in primes):\n", + " primes += tuple([i])\n", + " i += 2\n", + " return primes" + ] + }, + { + "cell_type": "code", + "execution_count": 4, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "(2,\n", + " 3,\n", + " 5,\n", + " 7,\n", + " 11,\n", + " 13,\n", + " 17,\n", + " 19,\n", + " 23,\n", + " 29,\n", + " 31,\n", + " 37,\n", + " 41,\n", + " 43,\n", + " 47,\n", + " 53,\n", + " 59,\n", + " 61,\n", + " 67,\n", + " 71,\n", + " 73,\n", + " 79,\n", + " 83,\n", + " 89,\n", + " 97)" + ] + }, + "execution_count": 4, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "sieve(100)" + ] + }, + { + "cell_type": "code", + "execution_count": 5, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "1819.3405398660252" + ] + }, + "execution_count": 5, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "max_prime = (target / 10)**0.5\n", + "max_prime" + ] + }, + { + "cell_type": "code", + "execution_count": 6, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "41538" + ] + }, + "execution_count": 6, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "max_prime = 500000\n", + "primes = sieve(max_prime)\n", + "len(primes)" + ] + }, + { + "cell_type": "code", + "execution_count": 7, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "prime_factors_cache = {}\n", + "# @lru_cache(maxsize=None)\n", + "def prime_factors(n, unused_primes):\n", + " if n in prime_factors_cache:\n", + " return prime_factors_cache[n]\n", + " if n < 2:\n", + " return tuple()\n", + " if n in unused_primes:\n", + " pf = tuple([n])\n", + " elif n % unused_primes[0] == 0:\n", + " pf = tuple([unused_primes[0]]) + prime_factors(n // unused_primes[0], unused_primes)\n", + " else:\n", + " pf = prime_factors(n, unused_primes[1:])\n", + " prime_factors_cache[n] = pf\n", + " return pf" + ] + }, + { + "cell_type": "code", + "execution_count": 8, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "(2, 2, 2, 5)" + ] + }, + "execution_count": 8, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "prime_factors(40, primes)" + ] + }, + { + "cell_type": "code", + "execution_count": 9, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "(17,)" + ] + }, + "execution_count": 9, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "prime_factors(17, primes)" + ] + }, + { + "cell_type": "code", + "execution_count": 10, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "{5: (5,), 10: (2, 5), 17: (17,), 20: (2, 2, 5), 40: (2, 2, 2, 5)}" + ] + }, + "execution_count": 10, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "# prime_factors.cache_info()\n", + "prime_factors_cache" + ] + }, + { + "cell_type": "code", + "execution_count": 11, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[(2, 3), (5, 1)]" + ] + }, + "execution_count": 11, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "[(p, len(list(i))) for p, i in groupby(prime_factors(40, primes))]" + ] + }, + { + "cell_type": "code", + "execution_count": 12, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[1, 2, 4, 8]" + ] + }, + "execution_count": 12, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "[2**p for p in range(3+1)]" + ] + }, + { + "cell_type": "code", + "execution_count": 13, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def prod(iterable):\n", + " return reduce(operator.mul, iterable, 1)" + ] + }, + { + "cell_type": "code", + "execution_count": 14, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def sum_of_factors(n, primes):\n", + " pfs = prime_factors(n, primes)\n", + " grouped_pfs = [(p, len(list(i))) for p, i in groupby(pfs)]\n", + " prime_sums = [sum(p**i for i in range(e+1)) for p, e in grouped_pfs]\n", + " return prod(prime_sums)" + ] + }, + { + "cell_type": "code", + "execution_count": 15, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "7" + ] + }, + "execution_count": 15, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "sum_of_factors(4, primes)" + ] + }, + { + "cell_type": "code", + "execution_count": 16, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "0 10\n", + "1 10\n", + "2 30\n", + "3 40\n", + "4 70\n", + "5 60\n", + "6 120\n", + "7 80\n", + "8 150\n", + "9 130\n" + ] + } + ], + "source": [ + "for i in range(10):\n", + " print(i, sum_of_factors(i, primes) * 10)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": false + }, + "outputs": [], + "source": [ + "i = 7687\n", + "while True:\n", + " try:\n", + " if sum_of_factors(i, primes) * 10 >= target :\n", + " break\n", + " i += 1\n", + " except:\n", + " print(\"failed with i =\", i)\n", + " break\n", + " \n", + "i" + ] + }, + { + "cell_type": "code", + "execution_count": 41, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "7680" + ] + }, + "execution_count": 41, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "max(prime_factors_cache)" + ] + }, + { + "cell_type": "code", + "execution_count": 42, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "499979" + ] + }, + "execution_count": 42, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "primes[-1]" + ] + }, + { + "cell_type": "code", + "execution_count": 43, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "(2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 5)" + ] + }, + "execution_count": 43, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "prime_factors_cache[7680]" + ] + }, + { + "cell_type": "code", + "execution_count": 44, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "7680" + ] + }, + "execution_count": 44, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "prod(prime_factors_cache[7680])" + ] + }, + { + "cell_type": "code", + "execution_count": 57, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "True" + ] + }, + "execution_count": 57, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "7687 in primes" + ] + }, + { + "cell_type": "code", + "execution_count": 58, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "(7687,)" + ] + }, + "execution_count": 58, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "prime_factors(7687, primes)" + ] + }, + { + "cell_type": "code", + "execution_count": 48, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "7682" + ] + }, + "execution_count": 48, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "sum_of_factors(7681, primes)" + ] + }, + { + "cell_type": "code", + "execution_count": 56, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "7688" + ] + }, + "execution_count": 56, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "sum_of_factors(7687, primes)" + ] + }, + { + "cell_type": "code", + "execution_count": 17, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[(2, 5), (3, 2), (5, 1), (7, 2), (11, 1)]" + ] + }, + "execution_count": 17, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "fs = prime_factors(776160, primes)\n", + "[(p, len(list(i))) for p, i in groupby(fs)]" + ] + }, + { + "cell_type": "code", + "execution_count": 18, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "(2, 2, 2, 2, 2, 3, 3, 5, 7, 7, 11)" + ] + }, + "execution_count": 18, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "fs" + ] + }, + { + "cell_type": "code", + "execution_count": 19, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "776160" + ] + }, + "execution_count": 19, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "prod(fs)" + ] + }, + { + "cell_type": "code", + "execution_count": 20, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "3361176" + ] + }, + "execution_count": 20, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "sum_of_factors(776160, primes)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [] + } + ], + "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.4.3" + } + }, + "nbformat": 4, + "nbformat_minor": 0 +} diff --git a/advent20.ipynb b/advent20.ipynb new file mode 100644 index 0000000..9b5dbfb --- /dev/null +++ b/advent20.ipynb @@ -0,0 +1,191 @@ +{ + "cells": [ + { + "cell_type": "code", + "execution_count": 1, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "target = 33100000" + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "import collections" + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defaultdict(, {})" + ] + }, + "execution_count": 3, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "houses = collections.defaultdict(int)\n", + "houses" + ] + }, + { + "cell_type": "code", + "execution_count": 4, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "for elf in range(1, target // 10 + 1):\n", + " for house in range(elf, target // 10 + 1, elf):\n", + " houses[house] += elf * 10" + ] + }, + { + "cell_type": "code", + "execution_count": 5, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[(1, 10),\n", + " (2, 30),\n", + " (3, 40),\n", + " (4, 70),\n", + " (5, 60),\n", + " (6, 120),\n", + " (7, 80),\n", + " (8, 150),\n", + " (9, 130)]" + ] + }, + "execution_count": 5, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "[(h, houses[h]) for h in range(1, 10)]" + ] + }, + { + "cell_type": "code", + "execution_count": 6, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "776160" + ] + }, + "execution_count": 6, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "min(h for h in houses if houses[h] >= target)" + ] + }, + { + "cell_type": "code", + "execution_count": 7, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defaultdict(, {})" + ] + }, + "execution_count": 7, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "houses2 = collections.defaultdict(int)\n", + "houses2" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "for elf in range(1, target // 10 + 1):\n", + " for house in range(1, 51):\n", + " houses2[elf * house] += elf * 11" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": false + }, + "outputs": [], + "source": [ + "min(h for h in houses2 if houses2[h] >= target)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [] + } + ], + "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.4.3" + } + }, + "nbformat": 4, + "nbformat_minor": 0 +} -- 2.34.1