From fef438e522205404e0e765414e412ccacc34bfaa Mon Sep 17 00:00:00 2001 From: Neil Smith <neil.git@njae.me.uk> Date: Mon, 5 Dec 2016 12:28:57 +0000 Subject: [PATCH] Day 5 --- README.html | 3 ++ README.md | 6 +++ advent05.hs | 44 +++++++++++++++ day05.html | 152 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 205 insertions(+) create mode 100644 advent05.hs create mode 100644 day05.html diff --git a/README.html b/README.html index 68668e7..754e9be 100644 --- a/README.html +++ b/README.html @@ -17,6 +17,9 @@ <p>I'm using the basic Haskell Platform installation (install with</p> <pre><code>$ sudo aptitude install haskell-platform</code></pre> <p>).</p> +<p>I'm also using the <code>MissingH</code> library (install with</p> +<pre><code>$ cabal install MissingH</code></pre> +<p>)</p> <p>Compile the code with</p> <pre><code>ghc --make advent01.hs</code></pre> <p>then run it as</p> diff --git a/README.md b/README.md index d95ac12..5c7f379 100644 --- a/README.md +++ b/README.md @@ -13,6 +13,12 @@ $ sudo aptitude install haskell-platform ``` ). +I'm also using the `MissingH` library (install with +``` +$ cabal install MissingH +``` +) + Compile the code with ``` ghc --make advent01.hs diff --git a/advent05.hs b/advent05.hs new file mode 100644 index 0000000..d86bd5a --- /dev/null +++ b/advent05.hs @@ -0,0 +1,44 @@ +module Main(main) where + +import Data.Hash.MD5 (md5s, Str(..)) +import Data.List (isPrefixOf) +import qualified Data.Map.Lazy as Map + +type Password = Map.Map Integer Char + +input = "cxdnnyjw" + +main :: IO () +main = do + part1 + part2 + + +part1 :: IO () +part1 = do + print $ take 8 [h!!5 | h <- filter (interesting) $ md5sequence input 0] + +part2 :: IO () +part2 = do + print $ Map.foldr (:) [] password + where interestingHashes = + [(read [h!!5], h!!6) | + h <- filter (interesting) (md5sequence input 0), + h!!5 `elem` "01234567"] + password = findPassword Map.empty interestingHashes + + +md5sequence :: String -> Integer -> [String] +md5sequence key i = (md5s (Str (key ++ show i))) : (md5sequence key (i+1)) + +interesting :: String -> Bool +interesting hash = "00000" `isPrefixOf` hash + +dontReplace :: (Integer, Char) -> Password -> Password +dontReplace (k, v) = Map.insertWith (\_ v -> v) k v + +findPassword :: Password -> [(Integer, Char)] -> Password +findPassword p (candidate:candidates) + | Map.size p == 8 = p + | otherwise = findPassword p' candidates + where p' = dontReplace candidate p diff --git a/day05.html b/day05.html new file mode 100644 index 0000000..f8af5e5 --- /dev/null +++ b/day05.html @@ -0,0 +1,152 @@ +<!DOCTYPE html> +<html lang="en-us"> +<head> +<meta charset="utf-8"/> +<title>Day 5 - Advent of Code 2016</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?7"/> +<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. 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, and a few 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><div><h1 class="title-global"><a href="/">Advent of Code</a></h1><nav><ul><li><a href="/2016/about">[About]</a></li><li><a href="/2016/support">[AoC++]</a></li><li><a href="/2016/events">[Events]</a></li><li><a href="/2016/settings">[Settings]</a></li><li><a href="/2016/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <span class="supporter">(AoC++)</span> <span class="star-count">10*</span></div></div><div><h1 class="title-event"> <span class="title-event-wrap">y(</span><a href="/2016">2016</a><span class="title-event-wrap">)</span></h1><nav><ul><li><a href="/2016">[Calendar]</a></li><li><a href="/2016/leaderboard">[Leaderboard]</a></li><li><a href="/2016/stats">[Stats]</a></li><li><a href="/2016/sponsors">[Sponsors]</a></li></ul></nav></div></header> + +<div id="sidebar"> +<div id="sponsor"><div class="quiet">Our <a href="/2016/sponsors">sponsors</a> help make AoC possible:</div><p><a href="http://www.novetta.com/careers/#opportunities" target="_blank" onclick="if(ga)ga('send','event','sponsor','click',this.href);">Novetta</a> - Unleash your imagination. Innovate at Novetta.</p></div> +<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--> +</div><!--/sidebar--> + +<main> +<article class="day-desc"><h2>--- Day 5: How About a Nice Game of Chess? ---</h2><p>You are faced with a security door designed by Easter Bunny engineers that seem to have acquired most of their security knowledge by watching <a href="https://en.wikipedia.org/wiki/Hackers_(film)">hacking</a> <a href="https://en.wikipedia.org/wiki/WarGames">movies</a>.</p> +<p>The <em>eight-character password</em> for the door is generated one character at a time by finding the <a href="https://en.wikipedia.org/wiki/MD5">MD5</a> hash of some Door ID (your puzzle input) and an increasing integer index (starting with <code>0</code>).</p> +<p>A hash indicates the <em>next character</em> in the password if its <a href="https://en.wikipedia.org/wiki/Hexadecimal">hexadecimal</a> representation starts with <em>five zeroes</em>. If it does, the sixth character in the hash is the next character of the password.</p> +<p>For example, if the Door ID is <code>abc</code>:</p> +<ul> +<li>The first index which produces a hash that starts with five zeroes is <code>3231929</code>, which we find by hashing <code>abc3231929</code>; the sixth character of the hash, and thus the first character of the password, is <code>1</code>.</li> +<li><code>5017308</code> produces the next interesting hash, which starts with <code>000008f82...</code>, so the second character of the password is <code>8</code>.</li> +<li>The third time a hash starts with five zeroes is for <code>abc5278568</code>, discovering the character <code>f</code>.</li> +</ul> +<p>In this example, after continuing this search a total of eight times, the password is <code>18f47a30</code>.</p> +<p>Given the actual Door ID, <em>what is the password</em>?</p> +</article> +<p>Your puzzle answer was <code>f77a0e6e</code>.</p><article class="day-desc"><h2>--- Part Two ---</h2><p>As the door slides open, you are presented with a second door that uses a slightly more <span title="This one says 'WOPR' in block letters.">inspired</span> security mechanism. Clearly unimpressed by the last version (in what movie is the password decrypted <em>in order</em>?!), the Easter Bunny engineers have worked out <a href="https://www.youtube.com/watch?v=NHWjlCaIrQo&t=25">a better solution</a>.</p> +<p>Instead of simply filling in the password from left to right, the hash now also indicates the <em>position</em> within the password to fill. You still look for hashes that begin with five zeroes; however, now, the <em>sixth</em> character represents the <em>position</em> (<code>0</code>-<code>7</code>), and the <em>seventh</em> character is the character to put in that position.</p> +<p>A hash result of <code>000001f</code> means that <code>f</code> is the <em>second</em> character in the password. Use only the <em>first result</em> for each position, and ignore invalid positions.</p> +<p>For example, if the Door ID is <code>abc</code>:</p> +<ul> +<li>The first interesting hash is from <code>abc3231929</code>, which produces <code>0000015...</code>; so, <code>5</code> goes in position <code>1</code>: <code>_5______</code>.</li> +<li>In the previous method, <code>5017308</code> produced an interesting hash; however, it is ignored, because it specifies an invalid position (<code>8</code>).</li> +<li>The second interesting hash is at index <code>5357525</code>, which produces <code>000004e...</code>; so, <code>e</code> goes in position <code>4</code>: <code>_5__e___</code>.</li> +</ul> +<p>You almost choke on your popcorn as the final character falls into place, producing the password <code>05ace8e3</code>.</p> +<p>Given the actual Door ID and this new method, <em>what is the password</em>? Be extra proud of your solution if it uses a cinematic "decrypting" animation.</p> +</article> +<p>Your puzzle answer was <code>999828ec</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="/2016">return to your advent calendar</a> and try another puzzle.</p> +<p>Your puzzle input was <code class="puzzle-input">cxdnnyjw</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+%22How+About+a+Nice+Game+of+Chess%3F%22+%2D+Day+5+%2D+Advent+of+Code+2016&url=http%3A%2F%2Fadventofcode%2Ecom%2F2016%2Fday%2F5&related=ericwastl&hashtags=AdventOfCode" target="_blank">Twitter</a> + <a href="https://plus.google.com/share?url=http%3A%2F%2Fadventofcode%2Ecom%2F2016%2Fday%2F5" target="_blank">Google+</a> + <a href="http://www.reddit.com/submit?url=http%3A%2F%2Fadventofcode%2Ecom%2F2016%2Fday%2F5&title=I%27ve+completed+%22How+About+a+Nice+Game+of+Chess%3F%22+%2D+Day+5+%2D+Advent+of+Code+2016" 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> \ No newline at end of file -- 2.43.0