Forked from joshuakfarrar/i-am-not-so-easily-defeated.js
Last active
February 7, 2019 18:34
-
-
Save ltbringer/ef298d66d4d176c64b478aa577da2b8b to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| '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")) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment