I'm mathematically trying to determine the shortest sequence of moves to reach a desired numerical result. I have two functions, both of which multiply a number by 2, and minus the value of the other number.

I've included my code so far, which has me manually calling the two functions to obtain the desired result; however, I would like help figuring out the logic to do this automatically with a loop.

function findShortestSequence(number) {
    let left = 0;
    let right = 1;
    let moves = [];

    const moveLeft = () => {
        moves.push('L');
        left = 2 * left - right;
    }

    const moveRight = () => {
        moves.push('R');
        right = 2 * right - left;
    }

    moveLeft();
    moveLeft();
    moveRight();
    moveLeft();

    console.log(left, right, moves);
}

findShortestSequence(-11)

I'm mathematically trying to determine the shortest sequence of moves to reach a desired numerical result. I have two functions, both of which multiply a number by 2, and minus the value of the other number.

I've included my code so far, which has me manually calling the two functions to obtain the desired result; however, I would like help figuring out the logic to do this automatically with a loop.

function findShortestSequence(number) {
    let left = 0;
    let right = 1;
    let moves = [];

    const moveLeft = () => {
        moves.push('L');
        left = 2 * left - right;
    }

    const moveRight = () => {
        moves.push('R');
        right = 2 * right - left;
    }

    moveLeft();
    moveLeft();
    moveRight();
    moveLeft();

    console.log(left, right, moves);
}

findShortestSequence(-11)

• javascript
• algorithm

4 Answers 4

I was just looking at -11, and considering 11 being 1011 in binary, which resembles your manual solution of LLRL, just backwards. Tests suggest that this may be the key for negative numbers: get their absolute value, and start shifting towards the right until it bees zero. When you shift out an 1, move to the left, when you shift out a 0, move to the right. The last step will be a left-move, and the result goes into left.
Then I just checked what about positive numbers, simply swapping the moves (because leaving them in place would provide the negative result) and it appeared to generate one number above the goal. So I just subtracted one from the original and it started to work. Of course this time the last step is going to be a right-move, and result goes into right:

function findShortestSequence(number) {
    let org = number;
    if(number<=0)number=-number; // work with absolute values when input is not positive
    else number--;               // work with one less, if input is positive
    let left = 0;
    let right = 1;
    let moves = [];

    const moveLeft = () => {
        moves.push('L');
        left = 2 * left - right;
    }

    const moveRight = () => {
        moves.push('R');
        right = 2 * right - left;
    }

    if(org<=0)
        while(number!=0){
          if(number&1)moveLeft();
          else moveRight();
          number>>=1;
        }
    else
        while(number!=0){
          if(number&1)moveRight();
          else moveLeft();
          number>>=1;
        }

    console.log(org, left, right, moves.join(''), (org==left)||(org==right));
}

for(var i=-20;i<=20;i++)
    findShortestSequence(i);

While I do not chase to provide a full explanation, I can provide some pieces which one may find useful:

• the "subtract 1 if positive" part feels like creating anti-two's plement number (in two's plement, in case of positive number you do not do anything, and in case of negative number you get its positive pair, invert its bits, and add 1 to the result)
• from a distance the "multiply by 2 and do a fix" is not that extreme:
  if one somehow ends up with 10001001 (137) and 1001 is the fixer, then multiply by 2 shifts everything to the left (100010010, 274), and if you want to keep that 0001001 part in its original place, subtracting the fixer "locally divides" that part back to its original place (100010010-1001=100001001), this is more or less what moveRight does to positive numbers
• updating the fixer is more convoluted, though some parts of it do resemble the previous idea: 2*1001 bees 10010, and subtracting 10001001 fixes back 1001 on the lower places, and also introduces that 1 from the beginning at high places. The nasty part is that 10001001 is clearly larger than 10010, so the result is a negative number, and in fact the fixer (left in case of a positive target number) has never been 1001, because at its very first update ever, it bees "2*0-something" (where "something" is a positive number, as right starts from 1). Indeed, looking at the example loop, left always seems to end up being non-positive, and right seems to be non-negative
• the anti-two's plement thing also uglifies the picture, it may be cleaner to think about negative target numbers first, as there the fixer (right) is non-negative, and positive*2-negative also stays positive:
  ...11110001001 (left) and 1001 (right), ...11110001001*2 is ...111100010010, and ...111100010010-1001=...111100001001, first part of the mission is acplished (keeping the 1001 pattern in place)
  and if the goal is to have ...1110010001001 later (after 2 moveLeft-s), then moveRight really does 1001*2=10010, 10010-...11110001001(-119)=10001001, which is exactly what is needed to extend the 1001 pattern into 10001001 for the 8 lowest places)
• about being "shortest": the fastest growing part is moveRight, if left remains 0 all the time, right jumps to the next power of two each step, so ceil(log2(number)) steps are needed to reach or surpass the given number, which equals to the number of significant binary digits required represent the number, which equals the steps taken by the loop.

I think I came to the same conclusion as tevemadar. Here it is in code:

function confirm(str, n){
  let l = 0;
  let r = 1;
  let i = 0;
  
  while(str[i]){
    if (str[i++] == 'L')
      l = 2*l - r;
    else
      r = 2*r - l;
  }
  
  if ([l, r].includes(n))
    return true;
    
  return false;
}

function f(n){
  if ([0, 1].includes(n))
    return '';
  else if (n > 1)
    return (n - 1)
      .toString(2)
      .split('')
      .map(x => x & 1 ? 'R' : 'L')
      .reverse()
      .join('');
  else
    return (-n)
      .toString(2)
      .split('')
      .map(x => x & 1 ? 'L' : 'R')
      .reverse()
      .join('');
}

for (let i=-11; i<=11; i++){
  fi = f(i);
  console.log(i + ': ' + fi + ', ' + confirm(fi, i));
}

You could take an iterative approach with a stack for the next state for checking the result.

This approach tests the smallest amount of changes first and then takes a growing count of possibilities.

function findShortestSequence(number) {
    const
        moveLeft = (left, right, moves) => [left * 2 - right, right, [...moves, 'L']],
        moveRight = (left, right, moves) => [left, right * 2 - left, [...moves, 'R']],
        functions = [moveLeft, moveRight];

    var stack = [[0, 1, []]],
        left, right, moves;

    while ([left, right, moves] = stack.shift()) {
        if (left === number) return moves;
        functions.forEach(fn => stack.push(fn(left, right, moves)));
    }
}

console.log(findShortestSequence(-11));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Yes, I also pletely agree with myself, and find my hint useful (ok, that answer is gone).
If verification is not needed, generating the steps is this simple:

function getSequence(n){
  if(n==0 || n==1)return "";
  var steps=n<0?["R","L"]:["L","R"];
  return (n<0?-n:n-1).toString(2)                        // get binary number
         .replace(/0/g,steps[0]).replace(/1/g,steps[1])  // replace digits with L/R
         .split('').reverse().join('');                  // reverse order
}

for(var i=-20;i<=20;i++)
  console.log(i,getSequence(i));

.as-console-wrapper { max-height: 100% !important; top: 0; }