-----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-----
```
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
10099 advent18.txt 23d697796dfa397e22b925f850cf5a269802e307753a7a9a26e26ed7350a56a2
9745 advent19.ipynb 858c65e798916dd00403762a01ba6b3a55348f20e8ac927b52e700aa3cd9c073
968 advent19.txt eb333fc1d3ec41e3b9b22096e838fe860fbc6667068129996cae3cd3483dd9e7
+11722 advent20-slow.ipynb 780a5bb1e729e8fdf8b4c75f6fbad5aa53975dcc9a6d12ee699a2d488c7b7dc3
+3377 advent20.ipynb be9db2beee6805ac9db9f2dc145abba3275964e36e21580122bacd8436777a30
```
#### Ignore
--- /dev/null
+<!DOCTYPE html>
+<html lang="en-us">
+<head>
+<meta charset="utf-8"/>
+<title>Day 20 - Advent of Code</title>
+<!--[if lt IE 9]><script src="/static/html5.js"></script><![endif]-->
+<link href='//fonts.googleapis.com/css?family=Source+Code+Pro:300&subset=latin,latin-ext' rel='stylesheet' type='text/css'>
+<link rel="stylesheet" type="text/css" href="/static/style.css?3"/>
+<link rel="shortcut icon" href="/favicon.ico?2"/>
+</head><!--
+
+
+
+
+Oh, hello! Funny seeing you here.
+
+I appreciate your enthusiasm, but you aren't going to find much down here.
+There certainly aren't clues to any of the puzzles. You do risk spoiling a few
+surprises for yourself, though. Best to play the normal way and discover
+everything as it was intended, I think. The best surprises don't even appear
+in the source until you unlock them for real.
+
+Please be careful with automated requests; I'm not Google, and I can only take
+so much traffic. Please be considerate so that everyone gets to play.
+
+If you're curious about how Advent of Code works, it's running on some custom
+Perl code. Other than a few integrations (auth, analytics, ads, social media),
+I built the whole thing myself, including the design, animations, prose, and
+all of the puzzles.
+
+The puzzles probably took the longest; the easiest ones were around 45 minutes
+each, but the harder ones took 2-3 hours, some even longer than that. A lot of
+effort went into building this thing - I hope you're enjoying playing it as
+much as I enjoyed making it for you!
+
+If you'd like to hang out, I'm @ericwastl on Twitter.
+
+- Eric Wastl
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+-->
+<body>
+<header><h1><a href="/">Advent of Code</a></h1><div class="user">Neil Smith <span class="star-count">40*</span></div><nav><ul><li><a href="/about">[About]</a></li><li><a href="/stats">[Stats]</a></li><li><a href="/leaderboard">[Leaderboard]</a></li><li><a href="/settings">[Settings]</a></li><li><a href="/auth/logout">[Log out]</a></li></ul></nav></header>
+
+<div id="ad">
+<script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
+<!-- Advent of Code Wide Skyscraper -->
+<ins class="adsbygoogle"
+ style="display:inline-block;width:160px;height:600px"
+ data-ad-client="ca-pub-9420604735624631"
+ data-ad-slot="8014013294"></ins>
+<script>
+(adsbygoogle = window.adsbygoogle || []).push({});
+</script>
+</div><!--/ad-->
+
+<main>
+<article class="day-desc"><h2>--- Day 20: Infinite Elves and Infinite Houses ---</h2><p>To keep the Elves busy, Santa has them deliver some presents <span title="This was before the Elves unionized, apparently.">by hand, door-to-door</span>. He sends them down a street with infinite houses numbered sequentially: <code>1</code>, <code>2</code>, <code>3</code>, <code>4</code>, <code>5</code>, and so on.</p>
+<p>Each Elf is assigned a number, too, and delivers presents to houses based on that number:</p>
+<ul>
+<li>The first Elf (number <code>1</code>) delivers presents to every house: <code>1</code>, <code>2</code>, <code>3</code>, <code>4</code>, <code>5</code>, ....</li>
+<li>The second Elf (number <code>2</code>) delivers presents to every second house: <code>2</code>, <code>4</code>, <code>6</code>, <code>8</code>, <code>10</code>, ....</li>
+<li>Elf number <code>3</code> delivers presents to every third house: <code>3</code>, <code>6</code>, <code>9</code>, <code>12</code>, <code>15</code>, ....</li>
+</ul>
+<p>There are infinitely many Elves, numbered starting with <code>1</code>. Each Elf delivers presents equal to <em>ten times</em> his or her number at each house.</p>
+<p>So, the first nine houses on the street end up like this:</p>
+<pre><code>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.
+</code></pre>
+<p>The first house gets <code>10</code> presents: it is visited only by Elf <code>1</code>, which delivers <code>1 * 10 = 10</code> presents. The fourth house gets <code>70</code> presents, because it is visited by Elves <code>1</code>, <code>2</code>, and <code>4</code>, for a total of <code>10 + 20 + 40 = 70</code> presents.</p>
+<p>What is the <em>lowest house number</em> of the house to get at least as many presents as the number in your puzzle input?</p>
+</article>
+<p>Your puzzle answer was <code>776160</code>.</p><article class="day-desc"><h2>--- Part Two ---</h2><p>The Elves decide they don't want to visit an infinite number of houses. Instead, each Elf will stop after delivering presents to <code>50</code> houses. To make up for it, they decide to deliver presents equal to <em>eleven times</em> their number at each house.</p>
+<p>With these changes, what is the new <em>lowest house number</em> of the house to get at least as many presents as the number in your puzzle input?</p>
+</article>
+<p>Your puzzle answer was <code>786240</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
+<p>At this point, you should <a href="/">return to your advent calendar</a> and try another puzzle.</p>
+<p>Your puzzle input was <code class="puzzle-input">33100000</code>.</p>
+<p>You can also <span class="share">[Share<span class="share-content">on
+ <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Infinite+Elves+and+Infinite+Houses%22+%2D+Day+20+%2D+Advent+of+Code&url=http%3A%2F%2Fadventofcode%2Ecom%2Fday%2F20&related=ericwastl&hashtags=AdventOfCode" target="_blank">Twitter</a>
+ <a href="https://plus.google.com/share?url=http%3A%2F%2Fadventofcode%2Ecom%2Fday%2F20" target="_blank">Google+</a>
+ <a href="http://www.reddit.com/submit?url=http%3A%2F%2Fadventofcode%2Ecom%2Fday%2F20&title=I%27ve+completed+%22Infinite+Elves+and+Infinite+Houses%22+%2D+Day+20+%2D+Advent+of+Code" target="_blank">Reddit</a
+></span>]</span>
+ this puzzle.</p>
+</main>
+
+<!-- ga -->
+<script>
+(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
+(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
+m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
+})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
+ga('create', 'UA-69522494-1', 'auto');
+ga('send', 'pageview');
+</script>
+<!-- /ga -->
+</body>
+</html>
--- /dev/null
+{
+ "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
+}
--- /dev/null
+{
+ "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(<class 'int'>, {})"
+ ]
+ },
+ "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(<class 'int'>, {})"
+ ]
+ },
+ "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
+}
projects / advent-of-code-15.git / commitdiff