<html><head></head><body><div class="ydpc2a184a4yahoo-style-wrap" style="font-family: Helvetica Neue, Helvetica, Arial, sans-serif; font-size: 13px;"><div></div>
<div dir="ltr" data-setdir="false">I have an update on my post. I implemented the same solution in Python 3 using a dictionary and it ran pretty quickly. I couldn't understand why my similar Haskell solution using an IntMap dictionary wasn't running similarly quickly.</div><div dir="ltr" data-setdir="false"><br></div><div dir="ltr" data-setdir="false">I have been running Haskell code in GHCI. I decided to break the code for this puzzle out into a separate file. Upon compiling and running, this code produced the correct output relatively quickly, on par with the Python 3 version. I am very surprised the code runs so much faster after compiling with GHC. I'm sure this is obvious to experienced Haskellers but it was new to me that performance could be so drastically different upon compilation, so I'm sharing in case anyone else has run into something similar. Here is my Haskell code:</div><div dir="ltr" data-setdir="false"><br></div><div dir="ltr" data-setdir="false">---</div><div dir="ltr" data-setdir="false"> <div><div>import Data.IntMap.Strict (IntMap)</div><div>import qualified Data.IntMap.Strict as IntMap</div><div><br></div><div>main = do</div><div> let iterate' f x = x `seq` x : iterate' f (f x)</div><div> print $ snd $ (iterate' nextNum (IntMap.fromList [(9,1),(3,2),(1,3),(0,4),(8,5)],(4,6)))!!29999994</div><div><br></div><div>-- Uses Data.IntMap.Strict to keep track of each number that has appeared in the list and its last position in an IntMap dictionary</div><div>nextNum :: (IntMap Int, (Int, Int)) -> (IntMap Int, (Int, Int))</div><div>nextNum (mp, (k, v)) = case IntMap.lookup k mp of</div><div> Nothing -> (IntMap.insert k v mp, (0, v+1))</div><div> Just pos -> (IntMap.insert k v mp, (v-pos, v+1))</div></div><br></div><div><br></div>
</div><div id="ydp85723606yahoo_quoted_1480582277" class="ydp85723606yahoo_quoted">
<div style="font-family:'Helvetica Neue', Helvetica, Arial, sans-serif;font-size:13px;color:#26282a;">
<div>
On Saturday, January 16, 2021, 04:20:29 PM PST, Julian Ong <julian_ong@yahoo.com> wrote:
</div>
<div><br></div>
<div><br></div>
<div><div id="ydp85723606yiv6069595109"><div><div class="ydp85723606yiv6069595109ydpd2cc4c4cyahoo-style-wrap" style="font-family:Helvetica Neue, Helvetica, Arial, sans-serif;font-size:13px;"><div></div>
<div dir="ltr">Sorry, corrected some typos below in the number of apostrophes.</div><div><br clear="none"></div>
</div><div class="ydp85723606yiv6069595109ydp48a48e4dyahoo_quoted" id="ydp85723606yiv6069595109ydp48a48e4dyahoo_quoted_1580992452">
<div style="font-family:'Helvetica Neue', Helvetica, Arial, sans-serif;font-size:13px;color:#26282a;">
<div class="ydp85723606yiv6069595109yqt5411645286" id="ydp85723606yiv6069595109yqtfd69223"><div>
On Saturday, January 16, 2021, 04:14:47 PM PST, Julian Ong <julian_ong@yahoo.com> wrote:
</div>
<div><br clear="none"></div>
<div><br clear="none"></div>
<div><div dir="ltr">Hi Haskellers - I'm learning Haskell and attempting to solve the Advent of Code 2020 puzzles using Haskell. I'm stuck on part 2 of Day 15 and have been for a while now, so I'm reaching out.</div><div dir="ltr"><br clear="none"></div><div dir="ltr">The puzzle asks you to find the nth element in a list of integers. Here's how the list is constructed:</div><div dir="ltr"><br clear="none"></div><div dir="ltr"><div><div dir="ltr">Start with a seed list of integers, like [0,3,6]. Then, referring to the last element (6), the next element is given by these rules:</div><div><br clear="none"></div><div><ul><li>If the last element was the first time the element has appeared in the list, then the next element is 0.</li><li>Otherwise, the next element is the age, or distance in the number of index positions, between the last element and when it last appeared before that.</li></ul></div></div><div><br clear="none"></div><div dir="ltr">For example, starting with [0,3,6], the next elements are 0, 3, 3, 1, 0, 4, 0, etc.</div><div dir="ltr"><br clear="none"></div><div dir="ltr">Part 1 of the puzzle asks you to find the 2020th element in the list.</div><div dir="ltr"><br clear="none"></div><div dir="ltr">You can do this by constructing increasingly longer lists like this (using Data.List):</div></div><div dir="ltr"><br clear="none"></div><div dir="ltr"><div><div><b>nextNum :: [Int] -> [Int]</b></div><div><b>nextNum l@(x:xs) = if not (x `elem` xs) then 0 : l else age l : l</b></div><div><b> where</b></div><div><b> age (x:xs) = let Just i = elemIndex x xs</b></div><div><b> in i+1</b></div></div><div dir="ltr"><br clear="none"></div>Then:</div><div dir="ltr"><br clear="none"></div><div dir="ltr"> <span><b>head $ (iterate nextNum [6,3,0]) !! 2017</b></span></div><div dir="ltr"><span><br clear="none"></span></div><div dir="ltr"><span>will give you the 2020th element of 436.</span></div><div dir="ltr"><span><br clear="none"></span></div><div dir="ltr">Note that you provide the starting list in reverse order and iterate so that it will keep adding new elements to the head of the list, which is more efficient than adding to the end.</div><div dir="ltr"><br clear="none"></div><div dir="ltr">You can also use unfoldr to generate the list element by element like this:</div><div dir="ltr"><br clear="none"></div><div dir="ltr"> <div><div><b>nextNum' :: [Int] -> Int</b></div><div><b>nextNum' (x:xs) = if not (x `elem` xs) then 0 else age x xs</b></div><div><b> where</b></div><div><b> age x xs = let Just i = elemIndex x xs</b></div><div><b> in i+1</b></div></div><br clear="none"></div><div dir="ltr">Then:</div><div dir="ltr"><br clear="none"></div><div dir="ltr"><span><b>(unfoldr (\l -> Just (nextNum' l, nextNum' l : l)) slist) !! 2016</b></span><br clear="none"></div><div dir="ltr"><span><br clear="none"></span></div><div dir="ltr"><span>will give you the 2020th element of 436.</span></div><div dir="ltr"><span><br clear="none"></span></div><div dir="ltr">---</div><div dir="ltr"><br clear="none"></div><div dir="ltr">Part 2 of the puzzle asks you to find the <b>30000000th</b> element given starting list [9,3,1,0,8,4].</div><div dir="ltr"><br clear="none"></div><div dir="ltr">I cannot find a way to do this without stack overflow and performance issues (I've run my attempts overnight with no answer generated). I've tried using Data.Map and Data.Sequence because my Stack Overflow searching suggested these might be more efficient data structures for this sort of task. Here are my attempts:</div><div dir="ltr"><br clear="none"></div><div dir="ltr">-- Uses Data.Map to avoid duplicate numbers thereby shortening the list. The dictionary entry (k, v) gives the element and the last position of that element.</div><div dir="ltr"><br clear="none"></div><div dir="ltr"> <div><div><b>nextNum'' :: (IntMap Int, (Int, Int)) -> (IntMap Int, (Int, Int))</b></div><div><b>nextNum'' (mp, (k, v)) = case IntMap.lookup k mp of</b></div><div><b> Nothing -> (IntMap.insert k v mp, (0, v+1))</b></div><div><b> Just pos -> (IntMap.insert k v mp, (v-pos, v+1))</b></div></div><br clear="none"></div><div dir="ltr"><br clear="none"></div><div dir="ltr">Then:</div><div dir="ltr"><br clear="none"></div><div dir="ltr"><span><b>snd $ (iterate nextNum'' (IntMap.fromList [(0,1),(3,2)],(6,3))) !! 2017</b></span><br clear="none"></div><div dir="ltr"><span><br clear="none"></span></div><div dir="ltr"><span>provides the answer for the 2020th element but either stack overflows or runs for hours (if I use a strict version of iterate) trying to figure out the 30000000th element.</span></div><div dir="ltr"><span><br clear="none"></span></div><div dir="ltr">Similarly, using Data.Sequence, I tried:</div><div dir="ltr"><br clear="none"></div><div dir="ltr"> <div><div><b>nextNum''' :: Seq Int -> Int</b></div><div><b>nextNum''' (xs :|> x) = if not (x `elem` xs) then 0 else age x xs</b></div><div><b> where</b></div><div><b> age x xs = let Just i = Seq.elemIndexR x xs</b></div><div><b> in Seq.length xs - i</b></div></div></div><div dir="ltr"><b><br clear="none"></b></div><div dir="ltr"> <div><div><b>aoc15b' :: Seq Int -> Int -> Int</b></div><div><b>aoc15b' slist tnum = (\(xs :> x) -> x) $ Seq.viewr (Seq.unfoldr (\l -> if Seq.length l == tnum then Nothing else let nnum = force (nextNum''' l) in Just (nnum, force (l |> nnum))) slist)</b></div></div><br clear="none"></div><div dir="ltr">I found that I needed to fix stack overflow problems by using "force" from Control.DeepSeq. Despite seemingly fixing stack overflow issues though, the calculation just takes too long, and in fact, I have never been able to actually output a solution.</div><div dir="ltr"><br clear="none"></div><div dir="ltr">I thought that using Data.Map or Data.Sequence would speed things up based on my Stack Overflow searching, but I'm unable to come up with a Haskell solution that runs in reasonable time.</div><div dir="ltr"><br clear="none"></div><div dir="ltr">I'm at a loss for different strategies at this point and would appreciate any ideas from the community.</div><div dir="ltr"><br clear="none"></div><div dir="ltr">Thanks, Julian</div><div dir="ltr"><br clear="none"></div><div dir="ltr"><br clear="none"></div><div dir="ltr"><br clear="none"></div><div dir="ltr"><span><br clear="none"></span></div><div dir="ltr"><span><br clear="none"></span></div><div dir="ltr"><span><br clear="none"></span></div><div dir="ltr"><span><br clear="none"></span></div><div dir="ltr"><span><br clear="none"></span></div><div dir="ltr"><span><br clear="none"></span></div><div dir="ltr"></div></div>
</div></div><div class="ydp85723606yiv6069595109yqt5411645286" id="ydp85723606yiv6069595109yqtfd27981">
</div></div></div></div></div>
</div>
</div></body></html>