I need to implement a Brainfuck language like(?) language
There are 5 commands for the language.
Initially,
int x=1; at start of the execution of the algorithm
Each command does the following in C language.
"+": x+=1;
"-": x-=1;
">": x= x*2;
"<" : x= x/2;
"!" : printf("%c",x);
Input is a sequence of characters that have ASCII codes between 0 to 127.
output should be a sequence of the commands above so that the program prints the same sequence of characters as the input
Note that the length of the output should be minimized.
For example
input: ABC
Output: >>>>>>+!+!+!
explanation: ASCII code for A B C are 65 66 67 receptively
x=1 so x is doubled 6 times to get to 64. Then increment and print 3 times to print all ABC.
This is minimal compared to increasing x 64 times to get to x=65
I need to implement this language.
But I am stuck on thinking up an algorithm that finds the sequence of commands when moving onto the next character in the input.
For instance, when x=8 and needs to move to 12, decrease x twice then multiplying by 2 is faster than adding 4 times. The decision for the algorithm gets very complicated when numbers get large enough.
I am thinking about recursion maybe to find the path? for minimum number of commands.
Any hints or is there a name of this esoteric language that I can refer to?
One way of finding the minimum number of steps to go from one value of x to another is using a modified Dijkstra's algorithm.
It comes down to maintaining a list of to numbers to explore, which will be initialized to your starting number. When you explore a number, you take all possible steps, i.e. +, -, > and <, keeping track of the result (and how you got there), until you reach your destination.
This will find a path from your start number to the destination number, and it will be guaranteed to be the shortest.