From de640d46282134bb95db645a2bd8de687f3251b1 Mon Sep 17 00:00:00 2001
From: Neil Smith <neil.git@njae.me.uk>
Date: Thu, 24 Dec 2020 10:55:25 +0000
Subject: [PATCH] Now with use of monad loops
---
advent15/package.yaml | 9 +-
advent15/src/advent15.hs | 26 +++---
advent15/src/advent15loop.hs | 75 ++++++++++++++++
advent15/src/advent15slow.hs | 1 -
problems/day15.html | 165 +++++++++++++++++++++++++++++++++++
5 files changed, 262 insertions(+), 14 deletions(-)
create mode 100644 advent15/src/advent15loop.hs
create mode 100644 problems/day15.html
diff --git a/advent15/package.yaml b/advent15/package.yaml
index cd2c591..ddc9415 100644
--- a/advent15/package.yaml
+++ b/advent15/package.yaml
@@ -56,7 +56,6 @@ executables:
source-dirs: src
dependencies:
- base >= 2 && < 6
- - text
- vector
advent15slow:
@@ -64,6 +63,12 @@ executables:
source-dirs: src
dependencies:
- base >= 2 && < 6
- - text
- containers
+ advent15loop:
+ main: advent15loop.hs
+ source-dirs: src
+ dependencies:
+ - base >= 2 && < 6
+ - vector
+ - monad-loops
diff --git a/advent15/src/advent15.hs b/advent15/src/advent15.hs
index 87cbf3d..ac0f2b4 100644
--- a/advent15/src/advent15.hs
+++ b/advent15/src/advent15.hs
@@ -7,6 +7,9 @@ import Data.STRef
import qualified Data.Vector.Unboxed.Mutable as V
+type STInt s = STRef s Int
+type VInt s = V.MVector s Int
+
main :: IO ()
main =
do let seed = [20, 0, 1, 11, 6, 3]
@@ -18,24 +21,25 @@ main =
part1 seed = runGame seed 2020
part2 seed = runGame seed 30000000
-zeroInt :: Int
-zeroInt = 0
+runGame :: [Int] -> Int -> Int
+runGame seed roundsNeeded =
+ runST $
+ do (round, word, history) <- seedGame seed roundsNeeded
+ gameSteps roundsNeeded round word history
+ readSTRef word
+seedGame :: [Int] -> Int -> ST s (STInt s, STInt s, VInt s)
seedGame seed historySize =
do round <- newSTRef $ length seed
word <- newSTRef $ last seed
- history <- V.replicate historySize zeroInt
+ history <- V.replicate historySize 0
forM_ (zip (init seed) [1..]) $ \(t, s) -> V.write history t s
return (round, word, history)
-runGame seed roundsNeeded =
- runST $
- do (round, word, history) <- seedGame seed roundsNeeded
- gameStep roundsNeeded round word history
- readSTRef word
-gameStep :: Int -> STRef s Int -> STRef s Int -> V.MVector s Int -> ST s ()
-gameStep targetRound round word history =
+-- gameSteps :: Int -> STRef s Int -> STRef s Int -> V.MVector s Int -> ST s ()
+gameSteps :: Int -> STInt s -> STInt s -> VInt s -> ST s ()
+gameSteps targetRound round word history =
do roundVal <- readSTRef round
if roundVal == targetRound
then return ()
@@ -46,7 +50,7 @@ gameStep targetRound round word history =
V.write history wordVal roundVal
modifySTRef round (+1)
writeSTRef word word'
- gameStep targetRound round word history
+ gameSteps targetRound round word history
speakWord :: Int -> Int -> Int
diff --git a/advent15/src/advent15loop.hs b/advent15/src/advent15loop.hs
new file mode 100644
index 0000000..7d2d258
--- /dev/null
+++ b/advent15/src/advent15loop.hs
@@ -0,0 +1,75 @@
+-- import Debug.Trace
+
+import Prelude hiding (round)
+import Control.Monad
+import Control.Monad.ST
+import Control.Monad.Loops
+import Data.STRef
+import qualified Data.Vector.Unboxed.Mutable as V
+
+
+main :: IO ()
+main =
+ do let seed = [20, 0, 1, 11, 6, 3]
+ -- print seed
+ print $ part1 seed
+ print $ part2 seed
+
+
+part1 seed = runGame seed 2020
+part2 seed = runGame seed 30000000
+
+runGame seed roundsNeeded =
+ runST $
+ do (round, word, history) <- seedGame seed roundsNeeded
+ gameLoop roundsNeeded round word history
+ readSTRef word
+
+-- gameLoop targetRound round word history =
+-- do ( gameStep round word history
+-- `untilM_` (do r <- readSTRef round
+-- return $ r == targetRound)
+-- )
+-- return ()
+
+-- gameLoop targetRound round word history =
+-- do untilM_ (gameStep round word history )
+-- (do r <- readSTRef round
+-- return $ r == targetRound )
+-- return ()
+
+-- gameLoop targetRound round word history =
+-- do whileM_ (do r <- readSTRef round
+-- return $ r /= targetRound )
+-- (gameStep round word history )
+-- return ()
+
+gameLoop targetRound round word history =
+ do whileM_ (do r <- readSTRef round
+ return $ r /= targetRound )
+ $ gameStep round word history
+ return ()
+
+seedGame seed historySize =
+ do round <- newSTRef $ length seed
+ word <- newSTRef $ last seed
+ history <- V.replicate historySize 0
+ forM_ (zip (init seed) [1..]) $ \(t, s) -> V.write history t s
+ return (round, word, history)
+
+gameStep :: STRef s Int -> STRef s Int -> V.MVector s Int -> ST s ()
+gameStep round word history =
+ do roundVal <- readSTRef round
+ wordVal <- readSTRef word
+ wordH <- V.read history wordVal
+ let word' = speakWord wordH roundVal
+ V.write history wordVal roundVal
+ modifySTRef round (+1)
+ writeSTRef word word'
+ return ()
+
+speakWord :: Int -> Int -> Int
+speakWord 0 _ = 0
+speakWord prev now = now - prev
+
+
diff --git a/advent15/src/advent15slow.hs b/advent15/src/advent15slow.hs
index 508fedd..4c6ff07 100644
--- a/advent15/src/advent15slow.hs
+++ b/advent15/src/advent15slow.hs
@@ -3,7 +3,6 @@
import Prelude hiding (round)
import qualified Data.IntMap.Strict as M
-
data Game = Game { round :: Int
, word :: Int
, history :: M.IntMap Int
diff --git a/problems/day15.html b/problems/day15.html
new file mode 100644
index 0000000..cc9a773
--- /dev/null
+++ b/problems/day15.html
@@ -0,0 +1,165 @@
+<!DOCTYPE html>
+<html lang="en-us">
+<head>
+<meta charset="utf-8"/>
+<title>Day 15 - Advent of Code 2020</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?25"/>
+<link rel="stylesheet alternate" type="text/css" href="/static/highcontrast.css?0" title="High Contrast"/>
+<link rel="shortcut icon" href="/favicon.png"/>
+</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="/2020/about">[About]</a></li><li><a href="/2020/events">[Events]</a></li><li><a href="https://teespring.com/stores/advent-of-code" target="_blank">[Shop]</a></li><li><a href="/2020/settings">[Settings]</a></li><li><a href="/2020/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <a href="/2020/support" class="supporter-badge" title="Advent of Code Supporter">(AoC++)</a> <span class="star-count">30*</span></div></div><div><h1 class="title-event"> <span class="title-event-wrap">int y=</span><a href="/2020">2020</a><span class="title-event-wrap">;</span></h1><nav><ul><li><a href="/2020">[Calendar]</a></li><li><a href="/2020/support">[AoC++]</a></li><li><a href="/2020/sponsors">[Sponsors]</a></li><li><a href="/2020/leaderboard">[Leaderboard]</a></li><li><a href="/2020/stats">[Stats]</a></li></ul></nav></div></header>
+
+<div id="sidebar">
+<div id="sponsor"><div class="quiet">Our <a href="/2020/sponsors">sponsors</a> help make Advent of Code possible:</div><div class="sponsor"><a href="https://careers.bolt.eu/positions?team=engineering&utm_source=adventofcode&utm_medium=banner&utm_campaign=adventofcode_traffic" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">Bolt</a> - Fastest growing mobility startup in Europe: distributed systems, microservices, ML, complex algorithms for demand prediction, and much more!</div></div>
+</div><!--/sidebar-->
+
+<main>
+<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>
+<article class="day-desc"><h2>--- Day 15: Rambunctious Recitation ---</h2><p>You catch the airport shuttle and try to book a new flight to your vacation island. Due to the storm, all direct flights have been cancelled, but a route is available to get around the storm. You take it.</p>
+<p>While you wait for your flight, you decide to check in with the Elves back at the North Pole. They're playing a <em>memory game</em> and are <span title="Of course they are.">ever so excited</span> to explain the rules!</p>
+<p>In this game, the players take turns saying <em>numbers</em>. They begin by taking turns reading from a list of <em>starting numbers</em> (your puzzle input). Then, each turn consists of considering the <em>most recently spoken number</em>:</p>
+<ul>
+<li>If that was the <em>first</em> time the number has been spoken, the current player says <em><code>0</code></em>.</li>
+<li>Otherwise, the number had been spoken before; the current player announces <em>how many turns apart</em> the number is from when it was previously spoken.</li>
+</ul>
+<p>So, after the starting numbers, each turn results in that player speaking aloud either <em><code>0</code></em> (if the last number is new) or an <em>age</em> (if the last number is a repeat).</p>
+<p>For example, suppose the starting numbers are <code>0,3,6</code>:</p>
+<ul>
+<li><em>Turn 1</em>: The <code>1</code>st number spoken is a starting number, <em><code>0</code></em>.</li>
+<li><em>Turn 2</em>: The <code>2</code>nd number spoken is a starting number, <em><code>3</code></em>.</li>
+<li><em>Turn 3</em>: The <code>3</code>rd number spoken is a starting number, <em><code>6</code></em>.</li>
+<li><em>Turn 4</em>: Now, consider the last number spoken, <code>6</code>. Since that was the first time the number had been spoken, the <code>4</code>th number spoken is <em><code>0</code></em>.</li>
+<li><em>Turn 5</em>: Next, again consider the last number spoken, <code>0</code>. Since it <em>had</em> been spoken before, the next number to speak is the difference between the turn number when it was last spoken (the previous turn, <code>4</code>) and the turn number of the time it was most recently spoken before then (turn <code>1</code>). Thus, the <code>5</code>th number spoken is <code>4 - 1</code>, <em><code>3</code></em>.</li>
+<li><em>Turn 6</em>: The last number spoken, <code>3</code> had also been spoken before, most recently on turns <code>5</code> and <code>2</code>. So, the <code>6</code>th number spoken is <code>5 - 2</code>, <em><code>3</code></em>.</li>
+<li><em>Turn 7</em>: Since <code>3</code> was just spoken twice in a row, and the last two turns are <code>1</code> turn apart, the <code>7</code>th number spoken is <em><code>1</code></em>.</li>
+<li><em>Turn 8</em>: Since <code>1</code> is new, the <code>8</code>th number spoken is <em><code>0</code></em>.</li>
+<li><em>Turn 9</em>: <code>0</code> was last spoken on turns <code>8</code> and <code>4</code>, so the <code>9</code>th number spoken is the difference between them, <em><code>4</code></em>.</li>
+<li><em>Turn 10</em>: <code>4</code> is new, so the <code>10</code>th number spoken is <em><code>0</code></em>.</li>
+</ul>
+<p>(The game ends when the Elves get sick of playing or dinner is ready, whichever comes first.)</p>
+<p>Their question for you is: what will be the <em><code>2020</code>th</em> number spoken? In the example above, the <code>2020</code>th number spoken will be <code>436</code>.</p>
+<p>Here are a few more examples:</p>
+<ul>
+<li>Given the starting numbers <code>1,3,2</code>, the <code>2020</code>th number spoken is <code>1</code>.</li>
+<li>Given the starting numbers <code>2,1,3</code>, the <code>2020</code>th number spoken is <code>10</code>.</li>
+<li>Given the starting numbers <code>1,2,3</code>, the <code>2020</code>th number spoken is <code>27</code>.</li>
+<li>Given the starting numbers <code>2,3,1</code>, the <code>2020</code>th number spoken is <code>78</code>.</li>
+<li>Given the starting numbers <code>3,2,1</code>, the <code>2020</code>th number spoken is <code>438</code>.</li>
+<li>Given the starting numbers <code>3,1,2</code>, the <code>2020</code>th number spoken is <code>1836</code>.</li>
+</ul>
+<p>Given your starting numbers, <em>what will be the <code>2020</code>th number spoken?</em></p>
+</article>
+<p>Your puzzle answer was <code>421</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>Impressed, the Elves issue you a challenge: determine the <code>30000000</code>th number spoken. For example, given the same starting numbers as above:</p>
+<ul>
+<li>Given <code>0,3,6</code>, the <code>30000000</code>th number spoken is <code>175594</code>.</li>
+<li>Given <code>1,3,2</code>, the <code>30000000</code>th number spoken is <code>2578</code>.</li>
+<li>Given <code>2,1,3</code>, the <code>30000000</code>th number spoken is <code>3544142</code>.</li>
+<li>Given <code>1,2,3</code>, the <code>30000000</code>th number spoken is <code>261214</code>.</li>
+<li>Given <code>2,3,1</code>, the <code>30000000</code>th number spoken is <code>6895259</code>.</li>
+<li>Given <code>3,2,1</code>, the <code>30000000</code>th number spoken is <code>18</code>.</li>
+<li>Given <code>3,1,2</code>, the <code>30000000</code>th number spoken is <code>362</code>.</li>
+</ul>
+<p>Given your starting numbers, <em>what will be the <code>30000000</code>th number spoken?</em></p>
+</article>
+<p>Your puzzle answer was <code>436</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="/2020">return to your Advent calendar</a> and try another puzzle.</p>
+<p>Your puzzle input was <code class="puzzle-input">20,0,1,11,6,3</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+%22Rambunctious+Recitation%22+%2D+Day+15+%2D+Advent+of+Code+2020&url=https%3A%2F%2Fadventofcode%2Ecom%2F2020%2Fday%2F15&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+%22Rambunctious+Recitation%22+%2D+Day+15+%2D+Advent+of+Code+2020+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2020%2Fday%2F15'}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
--
2.43.0