--- /dev/null
+-- Writeup at https://work.njae.me.uk/2022/12/21/advent-of-code-2022-day-21/
+
+import AoC
+import Data.Text (Text)
+import qualified Data.Text.IO as TIO
+import Data.Attoparsec.Text hiding (take, D)
+import Control.Applicative
+import qualified Data.Map.Strict as M
+import Data.Map.Strict ((!))
+import Control.Lens
+
+data Shout = Literal Int | Operation Operator String String
+ deriving (Show, Eq, Ord)
+
+data Operator = Plus | Minus | Times | Divide
+ deriving (Show, Eq, Ord)
+
+type Monkeys = M.Map String Shout
+
+fromLiteral :: Shout -> Int
+fromLiteral (Literal n) = n
+fromLiteral _ = error "fromLiteral"
+
+main :: IO ()
+main =
+ do dataFileName <- getDataFileName
+ text <- TIO.readFile dataFileName
+ let monkeys = successfulParse text
+ print $ part1 monkeys
+ print $ part2 monkeys
+
+part1, part2 :: Monkeys -> Int
+part1 monkeys = fromLiteral $ findRoot values operations
+ where (values, operations) = splitMonkeys monkeys
+
+-- hardcoded assumption: small values of humn give large values of result, so find larger values to give negative output
+part2 monkeys = binarySearch values operations l u
+ where (Operation _ rootL rootR) = monkeys ! "root"
+ monkeys' = monkeys & at "root" ?~ (Operation Minus rootL rootR)
+ (values, operations) = splitMonkeys monkeys'
+ (l, u) = findRange values operations 1
+
+findRange :: Monkeys -> Monkeys -> Int -> (Int, Int)
+findRange values operations prev
+ | res > 0 = findRange values operations (prev * 2)
+ | otherwise = (prev, prev * 2)
+ where res = fromLiteral $ trial values operations (prev * 2)
+
+binarySearch :: Monkeys -> Monkeys -> Int -> Int -> Int
+binarySearch values operations lower upper
+ | lower > upper = error "Failed search"
+ | result == 0 = probe
+ | result > 0 = binarySearch values operations (probe + 1) upper
+ | result < 0 = binarySearch values operations lower probe
+ where probe = ((upper - lower) `div` 2) + lower
+ result = fromLiteral $ trial values operations probe
+
+trial :: Monkeys -> Monkeys -> Int -> Shout
+trial values operations humn = findRoot (values & at "humn" ?~ (Literal humn)) operations
+
+splitMonkeys :: Monkeys -> (Monkeys, Monkeys)
+splitMonkeys = M.partition f
+ where f (Literal _) = True
+ f (Operation _ _ _) = False
+
+findRoot :: Monkeys -> Monkeys -> Shout
+findRoot values operations
+ | "root" `M.member` values = values ! "root"
+ | otherwise = findRoot values' operations'
+ where (values', operations') = evaluateMonkeys values operations
+
+evaluateMonkeys :: Monkeys -> Monkeys -> (Monkeys, Monkeys)
+evaluateMonkeys values operations = M.foldlWithKey' f ((values, M.empty)) operations
+ where f (valMs, opMs) name op =
+ case (evalShout valMs op) of
+ Nothing -> (valMs, opMs & at name ?~ op)
+ Just v -> (valMs & at name ?~ v, sans name opMs)
+
+evalShout :: Monkeys -> Shout -> Maybe Shout
+evalShout _ (Literal n) = Just $ Literal n
+evalShout values (Operation op l r) = apply <$> (Just op) <*> lval <*> rval
+ where lval = M.lookup l values
+ rval = M.lookup r values
+
+apply :: Operator -> Shout -> Shout -> Shout
+apply Plus (Literal l) (Literal r) = Literal (l + r)
+apply Minus (Literal l) (Literal r) = Literal (l - r)
+apply Times (Literal l) (Literal r) = Literal (l * r)
+apply Divide (Literal l) (Literal r) = Literal (l `div` r)
+apply _ _ _ = error "Illegal apply"
+
+
+-- Parse the input file
+
+monkeysP :: Parser Monkeys
+monkeyP :: Parser (String, Shout)
+shoutP, numberP, operationP :: Parser Shout
+nameP :: Parser String
+operatorP, plusP, minusP, timesP, divideP :: Parser Operator
+
+monkeysP = M.fromList <$> monkeyP `sepBy` endOfLine
+monkeyP = (,) <$> (nameP <* ": ") <*> shoutP
+shoutP = numberP <|> operationP
+numberP = Literal <$> decimal
+operationP = opify <$> nameP <*> operatorP <*> nameP
+ where opify l o r = Operation o l r
+nameP = many1 letter
+operatorP = plusP <|> minusP <|> timesP <|> divideP
+plusP = Plus <$ " + "
+minusP = Minus <$ " - "
+timesP = Times <$ " * "
+divideP = Divide <$ " / "
+
+successfulParse :: Text -> Monkeys
+successfulParse input =
+ case parseOnly monkeysP input of
+ Left _err -> M.empty -- TIO.putStr $ T.pack $ parseErrorPretty err
+ Right monkeys -> monkeys
--- /dev/null
+<!DOCTYPE html>
+<html lang="en-us">
+<head>
+<meta charset="utf-8"/>
+<title>Day 21 - Advent of Code 2022</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?30"/>
+<link rel="stylesheet alternate" type="text/css" href="/static/highcontrast.css?0" title="High Contrast"/>
+<link rel="shortcut icon" href="/favicon.png"/>
+<script>window.addEventListener('click', function(e,s,r){if(e.target.nodeName==='CODE'&&e.detail===3){s=window.getSelection();s.removeAllRanges();r=document.createRange();r.selectNodeContents(e.target);s.addRange(r);}});</script>
+</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 a massive company, 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, social media), I
+built the whole thing myself, including the design, animations, prose, and all
+of the puzzles.
+
+The puzzles are most of the work; preparing a new calendar and a new set of
+puzzles each year takes all of my free time for 4-5 months. 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="/2022/about">[About]</a></li><li><a href="/2022/events">[Events]</a></li><li><a href="https://teespring.com/stores/advent-of-code" target="_blank">[Shop]</a></li><li><a href="/2022/settings">[Settings]</a></li><li><a href="/2022/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <a href="/2022/support" class="supporter-badge" title="Advent of Code Supporter">(AoC++)</a> <span class="star-count">42*</span></div></div><div><h1 class="title-event"> <span class="title-event-wrap">int y=</span><a href="/2022">2022</a><span class="title-event-wrap">;</span></h1><nav><ul><li><a href="/2022">[Calendar]</a></li><li><a href="/2022/support">[AoC++]</a></li><li><a href="/2022/sponsors">[Sponsors]</a></li><li><a href="/2022/leaderboard">[Leaderboard]</a></li><li><a href="/2022/stats">[Stats]</a></li></ul></nav></div></header>
+
+<div id="sidebar">
+<div id="sponsor"><div class="quiet">Our <a href="/2022/sponsors">sponsors</a> help make Advent of Code possible:</div><div class="sponsor"><a href="https://www.assured.se/careers" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">Assured</a> - Från chip till skepp, bitar till bilar. Vi testar din säkerhet, vi säkrar din kod. Your career Assured.</div></div>
+</div><!--/sidebar-->
+
+<main>
+<article class="day-desc"><h2>--- Day 21: Monkey Math ---</h2><p>The <a href="11">monkeys</a> are back! You're worried they're going to try to steal your stuff again, but it seems like they're just holding their ground and making various monkey noises at you.</p>
+<p>Eventually, one of the elephants realizes you don't speak monkey and comes over to interpret. As it turns out, they overheard you talking about trying to find the grove; they can show you a shortcut if you answer their <em>riddle</em>.</p>
+<p>Each monkey is given a <em>job</em>: either to <em>yell a specific number</em> or to <em>yell the result of a math operation</em>. All of the number-yelling monkeys know their number from the start; however, the math operation monkeys need to wait for two other monkeys to yell a number, and those two other monkeys might <em>also</em> be waiting on other monkeys.</p>
+<p>Your job is to <em>work out the number the monkey named <code>root</code> will yell</em> before the monkeys figure it out themselves.</p>
+<p>For example:</p>
+<pre><code>root: pppw + sjmn
+dbpl: 5
+cczh: sllz + lgvd
+zczc: 2
+ptdq: humn - dvpt
+dvpt: 3
+lfqf: 4
+humn: 5
+ljgn: 2
+sjmn: drzm * dbpl
+sllz: 4
+pppw: cczh / lfqf
+lgvd: ljgn * ptdq
+drzm: hmdt - zczc
+hmdt: 32
+</code></pre>
+<p>Each line contains the name of a monkey, a colon, and then the job of that monkey:</p>
+<ul>
+<li>A lone number means the monkey's job is simply to yell that number.</li>
+<li>A job like <code>aaaa + bbbb</code> means the monkey waits for monkeys <code>aaaa</code> and <code>bbbb</code> to yell each of their numbers; the monkey then yells the sum of those two numbers.</li>
+<li><code>aaaa - bbbb</code> means the monkey yells <code>aaaa</code>'s number minus <code>bbbb</code>'s number.</li>
+<li>Job <code>aaaa * bbbb</code> will yell <code>aaaa</code>'s number multiplied by <code>bbbb</code>'s number.</li>
+<li>Job <code>aaaa / bbbb</code> will yell <code>aaaa</code>'s number divided by <code>bbbb</code>'s number.</li>
+</ul>
+<p>So, in the above example, monkey <code>drzm</code> has to wait for monkeys <code>hmdt</code> and <code>zczc</code> to yell their numbers. Fortunately, both <code>hmdt</code> and <code>zczc</code> have jobs that involve simply yelling a single number, so they do this immediately: <code>32</code> and <code>2</code>. Monkey <code>drzm</code> can then yell its number by finding <code>32</code> minus <code>2</code>: <code><em>30</em></code>.</p>
+<p>Then, monkey <code>sjmn</code> has one of its numbers (<code>30</code>, from monkey <code>drzm</code>), and already has its other number, <code>5</code>, from <code>dbpl</code>. This allows it to yell its own number by finding <code>30</code> multiplied by <code>5</code>: <code><em>150</em></code>.</p>
+<p>This process continues until <code>root</code> yells a number: <code><em>152</em></code>.</p>
+<p>However, your actual situation involves <span title="Advent of Code 2022: Now With Considerably More Monkeys">considerably more monkeys</span>. <em>What number will the monkey named <code>root</code> yell?</em></p>
+</article>
+<p>Your puzzle answer was <code>21120928600114</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>Due to some kind of monkey-elephant-human mistranslation, you seem to have misunderstood a few key details about the riddle.</p>
+<p>First, you got the wrong job for the monkey named <code>root</code>; specifically, you got the wrong math operation. The correct operation for monkey <code>root</code> should be <code>=</code>, which means that it still listens for two numbers (from the same two monkeys as before), but now checks that the two numbers <em>match</em>.</p>
+<p>Second, you got the wrong monkey for the job starting with <code>humn:</code>. It isn't a monkey - it's <em>you</em>. Actually, you got the job wrong, too: you need to figure out <em>what number you need to yell</em> so that <code>root</code>'s equality check passes. (The number that appears after <code>humn:</code> in your input is now irrelevant.)</p>
+<p>In the above example, the number you need to yell to pass <code>root</code>'s equality test is <code><em>301</em></code>. (This causes <code>root</code> to get the same number, <code>150</code>, from both of its monkeys.)</p>
+<p><em>What number do you yell to pass <code>root</code>'s equality test?</em></p>
+</article>
+<p>Your puzzle answer was <code>3453748220116</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="/2022">return to your Advent calendar</a> and try another puzzle.</p>
+<p>If you still want to see it, you can <a href="21/input" target="_blank">get your puzzle input</a>.</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+%22Monkey+Math%22+%2D+Day+21+%2D+Advent+of+Code+2022&url=https%3A%2F%2Fadventofcode%2Ecom%2F2022%2Fday%2F21&related=ericwastl&hashtags=AdventOfCode" target="_blank">Twitter</a>
+ <a href="javascript:void(0);" onclick="var mastodon_instance=prompt('Mastodon Instance / Server Name?'); if(typeof mastodon_instance==='string' && mastodon_instance.length){this.href='https://'+mastodon_instance+'/share?text=I%27ve+completed+%22Monkey+Math%22+%2D+Day+21+%2D+Advent+of+Code+2022+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2022%2Fday%2F21'}else{return false;}" target="_blank">Mastodon</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('set', 'anonymizeIp', true);
+ga('send', 'pageview');
+</script>
+<!-- /ga -->
+</body>
+</html>
\ No newline at end of file
projects / advent-of-code-22.git / commitdiff