i-am-not-so-easily-defeated.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)
 */

String.prototype.fix = function(index, replacement) {
  return `${this.substr(0, index)}${replacement}${this.substr(index + 1)}`
};

String.prototype.flip = function(index) {
  return this.fix(index, (function(i) { if (i == '0') return '1'; else return '0';})(this[index]));
}

function solve(ns, current, fixes, next, ops) {
  if (current == ns.length - 1) {
    if (ns[current] == next) return solve(ns.flip(fixes[fixes.length - 1]), fixes[fixes.length - 1] + 1, fixes.slice(0, fixes.length - 1), '0', ops + 1);
    else if (fixes.length == 0) return ops + 1;
    else return solve(ns.flip(ns.length - 1).flip(fixes[fixes.length - 1]), fixes[fixes.length - 1] + 1, fixes.slice(0, fixes.length - 1), '0', ops + 2);
  } else {
    if (ns[current] == next) {
      return solve(ns, current + 1, fixes, '0', ops);
    } else {
      return solve(ns, current + 1, fixes.concat(current), '1', ops);
    }
  }
}

console.log(solve("1001101", 0, [], '0', 0))

Look ma, no mutable variables! #recursion

(If you're reading this, a hint: I use fixes as a stack to keep track of the most recent bit discovered, by index, that needs to be flipped in order to flip the one in the stack prior to it. Think of it as a stack of dependencies.)