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 = `2t8t8t5t4t2t3t1t5t5t1t2t15t13t5t14`;

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.

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'))