bitflip.js

'use strict';

/*
 * given a string of bits such as 100100, calculate the number of steps required to convert
 * the string to 000000 using the following rules:
 * a bit may be flipped only if it is following immediately by a one, followed only by zeroes
 * the far-right bit may be toggled freely
 * 
 * examples: 111 -> 110 -> 010 -> 011 -> 001 -> 000 (score 5)
 *           1101 -> 1100 -> 0100 -> 0101 -> 0111 -> 0100 -> 0010 -> 0011 -> 0001 -> 0000 (score 9)
 */

/**
* Problems:
* 1) Search from the left-most bit and find a bit which is followed by 1 which is further followed only by zeros, 
*      defaults to right-most bit(which can be flipped freely).
* 2) Flip the bits (1 -> 0) or (0 -> 1).
* 3) Keep a track of iterations needed to reach from any input to having all bits as 0.
*/

const flip = bit => (bit === '1') ? '0' : '1'

/** returns a function with idx frozen */
const flipAtIdx = (idx) => (bit, i) => (i === idx) ? flip(bit) : bit

/** Flip the bit at a given index idx */
const getFlippedBitString = (bitString, idx) => bitString.split('').map(flipAtIdx(idx)).join('')

/** 
* acc stores the idx of '1' which is followed by 0s or nothing,
* acc updates if the current value is '1' and acc has a value > current index
*/
const findBitToFlip = (acc, bit, idx) => (bit === '1' && idx < acc) ? idx : acc

/**
* 1. Reverse the bitString so that it is easy to find the bit 
* 2. get the index of the bit to flip
* 3. if the index of bit to flip is same as the last time, shift the 
* extreme right bit instead.
* 4. else return the index saved in step 2.
*/
const searchFlipBitIdx = (bitString, bitShiftIndexStore) => {
  const bitArray = bitString.split('').reverse();
  const defaultArrIdx = bitArray.length - 1;
  const bitToFlip = bitArray.reduce(findBitToFlip, defaultArrIdx);
  // To reverse the effects of reverse()
  const tentativeIdx = (bitToFlip === 0) ? defaultArrIdx - 1: defaultArrIdx - bitToFlip - 1;
  if (bitShiftIndexStore[bitShiftIndexStore.length - 1] === tentativeIdx)
    return defaultArrIdx;
  return tentativeIdx
}

/**
 * Runs for limited number of attempts
 */
function solve(bitString, maxAttempts=120, debug=false) {
    const attemptsArr = new Array(maxAttempts).fill(1);
    const solution = attemptsArr.reduce((acc, _) => {
      if (acc.success) return acc
      // Get the index of the bit to flip
      const bitIdx = searchFlipBitIdx(acc.flippedString, acc.bitIdxStore);
      // store the index for excluding same results on next search
      acc.bitIdxStore = [ ...acc.bitIdxStore, bitIdx ];
      // store the flipped bitString
      acc.flippedString = getFlippedBitString(acc.flippedString, bitIdx);      
      // check if all bits are set to '0'
      if (acc.flippedString.indexOf('1') > -1 && acc.success === false) {
        acc.attempts += 1
      } else {
        acc.success = true
      }
      if (debug) { console.log(acc.flippedString); }
      return acc
    }, {flippedString: bitString, attempts: 0, success: false, bitIdxStore: []})
    return (solution.success) ? `Solved in ${solution.attempts} attempts.` : `Stopped at ${solution.attempts}.`
}

console.log(solve("1001101"))