DEV Community


Posted on

Advent of code - day 6

This challenge is to create a state machine and find the end state after n iterations.

This seems like a perfect opportunity to dig deeper with the State Monad which i have been struggling with for a while. First, the interface which is

// newtype State s a = State { runState :: s -> (a, s) }
interface State<S, A> {
  (s: S): [A, S]
Enter fullscreen mode Exit fullscreen mode

A more accurate name for this would be State processor. The type S represents the state whereas the A represents some sort of interesting output from the State processor.

First, I create my nextFishState function which has the signature:
nextFishState :: number -> [number]. Now in my nextState function which has the singature: nextState: S.State<number[], number>, I use chain to apply the nextFishState function to every element in my number[].

Finally, i replicate the nextState function 80 times so that i can pass it to sequeunce so that it'll fit the shape required by S.execute.

S.execute(initial)(A.sequence(S.Applicative)(A.replicate(80, nextState)))

This was okay with the small dataset however I suspect due to the eager evaluation of JS and the nature of A.sequence, my browser tab crashed on the input dataset. So, instead I'm going to use reduce instead:

pipe(A.replicate(80, nextState), A.reduce(initial, (state, f) => S.execute(state)(f))
Enter fullscreen mode Exit fullscreen mode

Edit: I don't think the problem was due to using sequence or changing it to reduce. It may be something to do with console logging an array several hundred thousand long as the answer shows up before the tab crashes. Changing it to only print out the length of the array seems to work okay

Part 2:
Now we are assessing the number of fish after 256 days instead of 80, so only a simple change from 80 -> 256.

Edit 2: So it appears its not that simple as the brute force method is too slow and memory intensive. Instead, I am going to remodel my state to be an array where the index is the number of days left and the value is the number of fish with that index. The beauty of using the State monad pattern is that even though i have changed the representation of the State as well as the nextState transformation, the passing of one state to the next remained the same.

Top comments (0)