Copyright	(c) Eric Mertens 2017
License	ISC
Maintainer	emertens@gmail.com
Safe Haskell	None
Language	Haskell2010

Main

Description

Day 17 has us repeatedly insert elements into a circular buffer and asks about the elements following some needle.

Part 1 is small enough that we can generate the whole list quickly and search it.

Part 2 is large enough that generating the whole list and searching it uses roughly 5.2 GB of RAM and takes 1 minute 15 seconds on my hardware to run! We instead optimize things by noticing that the 0 element is always at the head of the sequence, so we simply need to find the last element that was written at index 1.

Synopsis

main :: IO ()
elemAfter :: Int -> Seq Int -> Int
makeSequence :: Int -> Int -> Seq Int
cursors :: Int -> [Int]
part2 :: Int -> Int

Documentation

main :: IO () Source #

Print the solutions to the puzzle. Input file can be overridden via command-line arguments.

>>> :main
866
11995607

elemAfter Source #

Arguments

:: Int	needle
-> Seq Int	haystack
-> Int	following element

Compute the element that immediately follows the needle in the haystack. This assumes a circular interpretation for the list, so the first element is considered to follow the last.

makeSequence Source #

Arguments

:: Int	jump size
-> Int	last element
-> Seq Int

Compute the buffer generated by inserting elements up to a given element using a particular jump size.

>>> makeSequence 3 9
fromList [0,9,5,7,2,4,3,8,6,1]

cursors Source #

Arguments

:: Int	jump size
-> [Int]	cursor positions

The infinite list of cursors generated from a particular jump parameter.

>>> take 10 (cursors 3)
[0,1,1,2,2,1,5,2,6,1]

part2 Source #

Arguments

:: Int	jump size
-> Int	number following zero

Special case for when we only need to know what number is going to follow the zero. Because the 0 is always going to be at the zero index, whatever the last element to be written to the 1 index must be the element that directly follows the zero.