Advent of Code 2017 Day 6 (part 1) in Functional Programming (FP)

Question

I wanted to practice functional programming (FP) without using any library but using vanilla JS only. So I took a problem from Advent of Code (the 1st part of Day 6):

http://adventofcode.com/2017/day/6

A debugger program here is having an issue: it is trying to repair a memory reallocation routine, but it keeps getting stuck in an infinite loop.

In this area, there are sixteen memory banks; each memory bank can hold any number of blocks. The goal of the reallocation routine is to balance the blocks between the memory banks.

The reallocation routine operates in cycles. In each cycle, it finds the memory bank with the most blocks (ties won by the lowest-numbered memory bank) and redistributes those blocks among the banks. To do this, it removes all of the blocks from the selected bank, then moves to the next (by index) memory bank and inserts one of the blocks. It continues doing this until it runs out of blocks; if it reaches the last memory bank, it wraps around to the first one.

The debugger would like to know how many redistributions can be done before a blocks-in-banks configuration is produced that has been seen before.

For example, imagine a scenario with only four memory banks:

• The banks start with 0, 2, 7, and 0 blocks. The third bank has the most blocks, so it is chosen for redistribution.
• Starting with the next bank (the fourth bank) and then continuing to the first bank, the second bank, and so on, the 7 blocks are spread out over the memory banks. The fourth, first, and second banks get two blocks each, and the third bank gets one back. The final result looks like this: 2 4 1 2.
• Next, the second bank is chosen because it contains the most blocks (four). Because there are four memory banks, each gets one block. The result is: 3 1 2 3.
• Now, there is a tie between the first and fourth memory banks, both of which have three blocks. The first bank wins the tie, and its three blocks are distributed evenly over the other three banks, leaving it with none: 0 2 3 4.
• The fourth bank is chosen, and its four blocks are distributed such that each of the four banks receives one: 1 3 4 1.
• The third bank is chosen, and the same thing happens: 2 4 1 2.

At this point, we've reached a state we've seen before: 2 4 1 2 was already seen. The infinite loop is detected after the fifth block redistribution cycle, and so the answer in this example is 5.

Given the initial block counts in your puzzle input, how many redistribution cycles must be completed before a configuration is produced that has been seen before?

Your Input: 2 8 8 5 4 2 3 1 5 5 1 2 15 13 5 14

My solution in FP:

const banks = `2\t8\t8\t5\t4\t2\t3\t1\t5\t5\t1\t2\t15\t13\t5\t14`; const parse = input => input .split('\t') .map(c => parseInt(c)); const copy = input => input.slice(); const isUnique = toCheck => state => toCheck.toString() !== state.toString(); const INPUT = parse(banks); const redistribute = (input, index, toBeDistributed) => { if (!toBeDistributed) return input; const nextIndex = index + 1; const nextInput = input; ++nextInput[nextIndex % input.length]; return redistribute(nextInput, nextIndex, --toBeDistributed); }; const solveDaySix = input => { let banks = copy(input); const states = [input]; let cycle = 0; while (true) { ++cycle; const max = Math.max(...banks); const index = banks.indexOf(max); banks[index] = 0; banks = copy(redistribute(banks, index, max)); const stateIsUnique = isUnique(banks); if (!states.every(stateIsUnique)) break; states.push(copy(banks)); } return cycle; }; console.log("solution ", solveDaySix(INPUT));

Do you think my solution is consistent with the idea of FP (I used loops and mutate variables inside my functions)? Is there a better way to write the solution in FP? Any other improvement suggestions are welcomed.

Answer 1

Explanation

Algorithm

First we have to break down witch steps we have to do:

1. split bank string to an array
2. change all string values to a number
3. reallocate

reallocationRoutine

The algorithm above would look like this in JavaScript:

const reallocationRoutine = pipe ( split (' '), // split number by space map (Number), // cast String to a number reallocation ([]) (0) // reallocate with initial values ) reallocationRoutine ('0 2 7 0') // will return 5 

Pipe is a kind of function composition.

reallocation

I used loops and mutate variables inside my functions

You can avoid muting loops and variables by writing recursive functions. The cool thing about recursive functions is that the logic can be broken down into small steps:

• we need the first index of the biggest number
• we need the biggest number itself
• if our store (memoryBanks) includes the current state (input)
  • we return the current cycleCount
• else we call reallocation again, but there for we need to:
  • update the memoryBanks with the current input
  • increment the cycleCount
  • and redistribute the input

So it can looks like:

const reallocation = memoryBanks => cycleCount => input => { const firstIndexOfMax = input.indexOf(Math.max(...input)) const max = input[firstIndexOfMax] return contains(memoryBanks, input) ? cycleCount : reallocation ( memoryBanks.concat ([input]) ) ( increment (cycleCount) ) ( redistribute (input) (firstIndexOfMax) (max) ) } 

I used the ternary operator for conditions. The reason why is much more than only because it is shorter.
A if should always have an else and the ternary operator forces you to.

redistribute

Instead of putting the entire logic in redistribute, I wrote a function calledloop that traverses an array for a certain number of steps (steps) and a function (fn) on the current index of the passed array (xs) for each step. So we can create a more generic solution - one of the main ideas of FP.

const loop = fn => xs => index => steps => steps <= 0 ? xs : loop ( fn ) ( changeArrayValueOnIndex(index, fn(xs[index]), xs) ) ( getNextIndex(xs, index) ) ( steps - 1 ) 

redistribute is a special form of loop where we increment each index we reaches and modify the passed input xs so, that the start value gets set to 0

const redistribute = xs => index => loop (increment) (changeArrayValueOnIndex(index, 0, xs)) (getNextIndex(xs, index)) 

Working Example

Overall, the code is longer than the imperative solution, but only because I've encapsulated a lot of logic into its own function like increment and loop. However, these are now functions that we could reuse in our next project and, in addition, we can test everything much easier :)

// helper functions const pipe = (...fns) => fns.reduce((f, g) => (...args) => g(f(...args))) const map = fn => arr => arr.map(fn) const split = delimiter => str => str.split(delimiter) const arrayIsEqual = ys => xs => xs.length === ys.length ? xs.every((x, index ) => ys[index] === x) : false const contains = (xss, ys) => xss .map(arrayIsEqual(ys)) .some(bool => bool) const getNextIndex = (arr, index) => arr[index + 1] != undefined ? index + 1 : 0 const increment = x => x + 1 const changeArrayValueOnIndex = (index, value, array) => [].concat(array.slice(0, index), value, array.slice(index + 1)) // functions for businesslogic const loop = fn => xs => index => steps => steps <= 0 ? xs : loop ( fn ) ( changeArrayValueOnIndex(index, fn(xs[index]), xs) ) ( getNextIndex(xs, index) ) ( steps - 1 ) const redistribute = xs => index => loop (increment) (changeArrayValueOnIndex(index, 0, xs)) (getNextIndex(xs, index)) const reallocation = memoryBanks => cycleCount => input => { const firstIndexOfMax = input.indexOf(Math.max(...input)) const max = input[firstIndexOfMax] return contains(memoryBanks, input) ? cycleCount : reallocation ( memoryBanks.concat([input]) ) ( increment(cycleCount) ) ( redistribute (input)(firstIndexOfMax)(max) ) } const reallocationRoutine = pipe( split (' '), map (Number), reallocation ([]) (0) ) console.log('0 2 7 0:', reallocationRoutine('0 2 7 0')) console.log('2 8 8 5 4 2 3 1 5 5 1 2 15 13 5 14:', reallocationRoutine('2 8 8 5 4 2 3 1 5 5 1 2 15 13 5 14'))