Find shortest sequence of mathematical operations

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) {
    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);

Minimum number of operation required to convert number x into y , 4-1 = 3 3. 3*2 = 6 4. 6-1 = 5 Answer = 4 Note that other sequences of two operations would take more operations. 2) Insert non-lcs characters (in their original order in strings) to the lcs found above, and return the result. So “ek” becomes “geeke” which is shortest common supersequence. Let us consider another example, str1 = “AGGTAB” and str2 = “GXTXAYB”. LCS of str1 and str2 is “GTAB”. Once we find LCS, we insert characters of both strings in order and we get “AGXGTXAYB”.

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));
}

Getting the shortest sequence to reach a number, what is the smallest number of steps ( i + 1 ) that can get you to a operations is a 'step', and it counts how many steps to get back to 0. The best way to get the sequence is through the smart application of mathematics, not  When doing computations, always follow the order of operations and always perform the operations according to the following rule. Rule: 1. If grouping symbols are used such as parentheses, perform the operations inside the grouping symbols first. 2. Evaluate any expressions with exponent. 3. Multiply and Divide from left to right. 4.

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; }

Algorithms in Bioinformatics: 4th International Workshop, WABI , One of the most promising ways to determine evolutionary distance between two problem calls for finding a shortest sequence of rearrangement operations  So you can find the sequence of operations just by reading off the binary value of N. N=18 is 10010 in binary, so we have 1 = starting value: 1 0 = multiply by 2 : 2 0 = multiply by 2 : 4 1 = multiply by 2 and add one: 8,9 0 = multiply by 2 : 18

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){
  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; }

Automata, Languages, and Programming: 42nd International , 2 The Institute of Mathematical Sciences, Chennai, India vraman@imsc.res.in Abstract. Given a Boolean formula and a satisfying assignment, a flip is an operation We study the problem of computing the shortest sequence of flips (if one on it to provide a trichotomy for the complexity of finding the shortest sequence of  seq initially has keys 0 and 1, then 2 is added, then 3, and so on up to n, at which point the shortest path to n is available. The shortest path is determined in the code that precedes path = [n]; the remaining statements merely extract it from seq.

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)
    {

        if(N == 0 || N == 1 )
            return "no command can be returned because of formulae constraints";

        boolean negated = false;
        boolean isPowerOfTwo = false;
        boolean isPowerOfTwoMinusOne = false;

        if(N < 0){
            N = -N;
            negated = true;
        } else {
            isPowerOfTwo = isPowerOfTwo(N);
            isPowerOfTwoMinusOne = isPowerOfTwoMinusOne(N);
        }

        //Extract the binary representation as L's and R's

        ArrayList<String> commands = new ArrayList<>();
        while (N > 0) {
            if( N % 2 == 0) {
                commands.add("R");
            } else {
                if(isPowerOfTwo)
                    commands.add("R");
                else
                    commands.add("L");
            }
            N /= 2;
        }

        StringBuilder finalCommand = new StringBuilder();

        if(negated) {
            for (String command : commands) {
                finalCommand.append(command);
            }
        }else if (isPowerOfTwo || isPowerOfTwoMinusOne){
            if(isPowerOfTwoMinusOne)
                finalCommand.append("L");

            for(int i = 1; i < commands.size(); i++) {
                finalCommand.append("R");
            }
        }else {
            //Mirroring here 
            for(int i = commands.size() - 1; i >= 0; i--) {
                finalCommand.append(commands.get(i));
            }
        }

        return finalCommand.toString();
    }

    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) {

        if(N == 0 || 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) );
    }
}

Genomic Perl: From Bioinformatics Basics to Working Code, this chapter will be an algorithm for finding the shortest sequence of reversals that is to sort the second list into ascending order by a series of reversal operations. The mathematical literature refers to our problem more specifically as 276  Free Sequences calculator - find sequence types, indices, sums and progressions step-by-step This website uses cookies to ensure you get the best experience. By using this website, you agree to our Cookie Policy.

Shortest path problem, In graph theory, the shortest path problem is the problem of finding a path between two vertices are variables; their numbering here relates to their position in the sequence and needs not to Other applications, often studied in operations research, include plant and facility layout, Quarterly of Applied Mathematics. Divide and Multiply rank equally (and go left to right). Add and Subtract rank equally (and go left to right) So do it this way: After you have done "P" and "E", just go from left to right doing any "M" or "D" as you find them.

(PDF) New mathematical model to find the shortest path based on , New mathematical model to find the shortest path based on Boolean algebra operations for networks. Conference Paper (PDF Available)  Informatics and Mathematical Modelling / Operations Research Mathematical Programming Formulation Suppose r is vertex 1. For r n 1 paths have to leave r. For any other vertex, the number of paths entering the vertex must be exactly 1 larger than the number of paths leaving the vertex. Let xe denote the number of paths using each edge e 2 E.

Full article: Finding shortest paths in a sequence of triangles in 3D , We present an efficient algorithm for finding the shortest path joining two points in a A Journal of Mathematical Programming and Operations Research The sequence of funnels associated with all common edges of the  The order of operations was settled upon in order to prevent miscommunication, but PEMDAS can generate its own confusion; some students sometimes tend to apply the hierarchy as though all the operations in a problem are on the same "level" (simply going from left to right), but often those operations are not "equal".

Comments
  • That is a great observation about using bitwise operators. One slight modification I've made is to get rid of the if(org <= 0) statement, and replace the moveLeft() and moveRight() with ternaries.
  • @AnonymousSB as I had some doubts about the "look, it is easy" explanation in the other answer, so added some thoughts about what is happening inside
  • Caleb Lucas' answer seems to me to fail with positive numbers. Am I misreading it? For example, any power of 2 would include an 'L', when clearly we only need R's. And testing just for 3 and -3 returns LL for both. How could that be?
  • @גלעדברקן That answer is simply wrong for positive numbers: returns the sequence producing the corresponding negative number, just mirrored. It fails to work starting from 1, which should result in an empty sequence, as right=1 already (same as for 0, since left=0 already)
  • @ArsalanAhmed It was a guess (nice wording: heuristic technique), I did not follow any kind of formal approach, really just looked at the bits in the binary representation of the number shown as example. Side note: cs.stackexchange.com may be the sister-site where questions about the theory of designing algorithms could be discussed.
  • While at least the faulty accepted answer is completely gone, I remain being puzzled why it is so important for OP to accept an answer which is a different one from mine...
  • I accepted this answer because the confirm function provided shows that it generates the correct moves, unless there is something I’m missing?
  • How can you be sure that this terminates?
  • @Simone, it terminates, because of the finite value, and assuming the stack is deep enough.
  • I really do appreciate your effort, and original observation about it being binary. This solution is much more succinct to @גלעדברקן's answer, and provides the same results. Quite smart to swap the steps ahead of time. Given that the max binary has a length of 31, I don't see any major issues with the time complexity; however, you could use cut down on one pass with this replace instead .replace(/0|1/g, match => match === '0' ? steps[0] : steps[1])
  • If 11 = 1011 = LRLL, and -11 is just LRLL reversed as LLRL, couldn't I just negate the number to positive, convert to binary with toString(2), swap the 1 for L and 0 for R, and reverse the string if it was negated?
  • @AnonymousSB Sounds like that should work just fine too.
  • I think in the case of the following numbers, we discard. 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647
  • Caleb and @AnonymousSB, I'm confused. How can 3 and -3 have the same set of instructions, LL? It seems to me the code here fails for positive numbers. Did I misunderstand something? For example, any power of 2 would include an 'L', when clearly we only need R's.