two-bucket.js

/*
Given two buckets of different size, demonstrate how to measure an exact number of liters by strategically transferring liters of fluid between the buckets.

Since this mathematical problem is fairly subject to interpretation / individual approach, the tests have been written specifically to expect one overarching solution.

To help, the tests provide you with which bucket to fill first. That means, when starting with the larger bucket full, you are NOT allowed at any point to have the smaller bucket full and the larger bucket empty (aka, the opposite starting point); that would defeat the purpose of comparing both approaches!

Your program will take as input:

    the size of bucket one, passed as a numeric value
    the size of bucket two, passed as a numeric value
    the desired number of liters to reach, passed as a numeric value
    which bucket to fill first, passed as a String (either 'one' or 'two')

Your program should determine:

    the total number of "moves" it should take to reach the desired number of liters, including the first fill - expects a numeric value
    which bucket should end up with the desired number of liters (let's say this is bucket A) - expects a String (either 'one' or 'two')
    how many liters are left in the other bucket (bucket B) - expects a numeric value

Note: any time a change is made to either or both buckets counts as one (1) move.

Example: Bucket one can hold up to 7 liters, and bucket two can hold up to 11 liters. Let's say bucket one, at a given step, is holding 7 liters, and bucket two is holding 8 liters (7,8). If you empty bucket one and make no change to bucket two, leaving you with 0 liters and 8 liters respectively (0,8), that counts as one "move". Instead, if you had poured from bucket one into bucket two until bucket two was full, leaving you with 4 liters in bucket one and 11 liters in bucket two (4,11), that would count as only one "move" as well.

To conclude, the only valid moves are:

    pouring from one bucket to another
    emptying one bucket and doing nothing to the other
    filling one bucket and doing nothing to the other
*/

function twoBucket (bucketOne, bucketTwo, goal, starterBucket) {
  let opts = {
    aMax: bucketOne,
    bMax: bucketTwo,
    goal: goal,
    parent: null
  }
  // Record attempted combinations. If a combination has been tried
  // then further identical combinations can be ignored, it's a dead end.
  // Prepopulated with [0,0] and [aMax, bMax]; these are also dead ends:
  const nodeIDs = new Set([nodeID(0,0), nodeID(bucketOne, bucketTwo)])
  const nodes = []
  // Initialize. One bucket always starts filled:
  let a = (starterBucket === 'one') ? bucketOne : 0
  let b = (starterBucket === 'two') ? bucketTwo : 0
  // The buckets should not end up in the opposite state to the start,
  // eg if there is a start of [aMax, 0], should not go to [0, bMax]:
  const disallowed = (starterBucket === 'one') ? nodeID(0, bucketTwo)
                                               : nodeID(bucketOne, 0)
  nodeIDs.add(disallowed)
  // Build the tree via a traversal of possible values.
  // NOTE side effect; this fills the Set of IDs and the Map of nodes.
  traverse(a, b, nodeIDs, nodes, opts)
  // Going from the last node in the tree (the goal),
  // find a path by checking the parent.
  const happyPath = nodes.reverse()
                         .reduce((acc, curr, i) => {
                           let {id, parent} = curr
                           if(i === 0) {
                             acc.push(curr)
                           } else if(id === acc[acc.length - 1].parent) {
                             acc.push(curr)
                           }
                           return acc
                         }, [])

  // The first value in the happyPath array is always the goal:
  // extract the [a,b] from the string `a,b`:
  const [goalA, goalB] = happyPath[0].id.split(',').map(v => Number(v))
  // Then get the required info:
  const goalBucket = (goalA === goal) ? `one` : `two`
  const otherBucket = (goalA === goal) ? goalB : goalA

  return Object.freeze({
    moves() { return happyPath.length },
    goalBucket,
    otherBucket
  })
}

// Start with only the root node in the queue.
// Pop an item from the front of the queue
// Explore it add all of the nodes found during exploration to the back of the queue
// Check if there are any nodes in the queue if there are go back to step 2
// Your done
function traverse(a, b, nodeIDs, nodes, opts) {
  let { aMax, bMax, goal, parent } = opts
  const queue = []
  // Add the root node:
  addNode(a, b, nodeIDs, nodes, parent)
  // Set the root node as the parent:
  parent = nodeID(a,b)
  // Check for possible children:
  let children = possChildren(a, b, nodeIDs, opts)
  // Add each of those children to the Set of node IDs
  // & the nodes Map, and push them into the queue:
  for(let [a,b] of children) {
    addNode(a, b, nodeIDs, nodes, parent)
    // Exit if goal reached:
    if(a === goal || b === goal) return
    queue.push([a,b])
  }
  // Do the above again for every member of the queue, breadth-first,
  // shifting out the checked values until the queue is empty:
  while (queue.length > 0) {
    for(let [a,b] of queue) {
      // Exit if goal reached:
      if(a === goal || b === goal) return
      parent = nodeID(a,b)
      let children = possChildren(a, b, nodeIDs, opts)
      for(let [a,b] of children) {
        addNode(a, b, nodeIDs, nodes, parent)
        // Aaaaand exit if goal reached:
        if(a === goal || b === goal) return
        queue.push([a,b])
      }
    }
    queue.shift()
  }
}

function addNode(a, b, nodeIDs, nodes, parent) {
  nodeIDs.add(nodeID(a,b))
  nodes.push({ id: nodeID(a,b), parent: parent })
}

function possChildren(a, b, nodeIDs, opts) {
  const { aMax, bMax } = opts
  const x = min(aMax - a, b)
  const y = min(a, bMax - b)
  return [[a,0], [0,b], [aMax,b], [a,bMax], [a + x, b - x], [a - y, b + y]].filter(([a, b]) => !nodeIDs.has(nodeID(a, b)))
}

// The Nodes ideally would be a tuple of the form [a,b],
// but JS does not have tuples, so stringify to compare:
function nodeID(a,b) { return `${a},${b}`}
// Minimum of two values, used when swapping bucket quantities:
function min(a,b) { return (a < b) ? a : b }