Odtnhj

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 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 becomes 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) (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 complement number (in two's complement, 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 becomes 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 becomes "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 complement 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 accomplished (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 completely 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)

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

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

EDIT: Since we have a correct and proper solution to this question, the pattern of mirroring as applied in CommandBuilder for positive integers is a misconception and should have never been used: it generates duplicate command strings for some integers. Please see CommandBuilderTwo for a more appropriate solution.

Given the fact that L = 0 and R = 1, we can convert the desired decimal number, P, into binary and store each digit inversely as 1 for L and 0 for R when negative

Let us also take these factors into consideration. For any given number P:

1. P could be a positive number that is the result of (2 ^ N); where 0 < N <= 32


2. P could be a positive number that is the result of (2 ^ N) - 1; where 0 < N <= 32


3. P could be any other positive number


4. P could be any negative number

We can efficiently determine the commands required to build the inputted desired number using the following solution:

public class CommandBuilder 

 private static String getCommand(long N)
 

 private static boolean isPowerOfTwo(long val) 
 return (int) Math.ceil( Math.log(val) / Math.log(2))
 == (int) Math.floor(Math.log(val) / Math.log(2));
 

 private static boolean isPowerOfTwoMinusOne(long val) 
 int root = (int) Math.ceil(Math.log(val) / Math.log(2));
 return Math.pow(2, root) - 1 == val;
 

 //Driver method
 public static void main(String args) 

 for(int i = 0; i <= 25; i++)
 System.out.println("The command required to produce " + i + ": " + getCommand(i) );
 System.out.println("The command required to produce -" + i + ": " + getCommand(-i) );
 

 int edge = Integer.MAX_VALUE;
 System.out.println("The command required to produce " + edge + ": " + getCommand(edge) );
 System.out.println("The command required to produce -" + edge + ": " + getCommand(-edge) );

 

This is a solution equivalent to @tevemadar's description of his solution, albeit in java.

public class CommandBuilderTwo 

 private static String buildCommand(int N) N == 1)
 return "no command can be built";

 boolean negated = false;

 if(N < 0) 
 N = -N;
 negated = true;
 else 
 --N;
 

 String bin = Integer.toBinaryString(N).split("");

 StringBuilder res = new StringBuilder();

 if(negated) 
 for (String c: bin) 
 if((Integer.valueOf(c) & 1) == 1)
 res.append('L');
 else
 res.append('R');
 
 else
 for (String c: bin) 
 if((Integer.valueOf(c) & 1) == 1)
 res.append('R');
 else
 res.append('L');
 
 

 //Reverse string built
 String command = res.toString();
 res = new StringBuilder();
 for(int i = command.length() - 1; i >= 0; i--) 
 res.append(command.charAt(i));
 

 return res.toString();
 

 //Driver method
 public static void main (String args) 
 for(int i = 0; i <= 25; i++)
 System.out.println("The command required to produce " + i + ": " + buildCommand(i) );
 System.out.println("The command required to produce -" + i + ": " + buildCommand(-i) );
 

 int edge = Integer.MAX_VALUE;
 System.out.println("The command required to produce " + edge + ": " + buildCommand(edge) );
 System.out.println("The command required to produce -" + edge + ": " + buildCommand(-edge) );