I’m trying to write a normal Markov algorithm in an emulator to swap two ternary numbers separated by the symbol “^”. For example, for input “120^210”, the result should be “210^120”.
I have tried these rules:
<code>^0 -> 0@^
^1 -> 1@^
^2 -> 2@^
@^0 -> 0@^
@^1 -> 1@^
@^2 -> 2@^
@^ -> ^
^->@
@0 -> ^0
@1 -> ^1
@2 -> ^2
@ -> ^
</code>
<code>^0 -> 0@^
^1 -> 1@^
^2 -> 2@^
@^0 -> 0@^
@^1 -> 1@^
@^2 -> 2@^
@^ -> ^
^->@
@0 -> ^0
@1 -> ^1
@2 -> ^2
@ -> ^
</code>
^0 -> 0@^
^1 -> 1@^
^2 -> 2@^
@^0 -> 0@^
@^1 -> 1@^
@^2 -> 2@^
@^ -> ^
^->@
@0 -> ^0
@1 -> ^1
@2 -> ^2
@ -> ^
But it didn’t work correctly; I just get “120210^”.
1
When the ^ symbol has moved to the far right, and it is replaced with @, then there are no more rules that apply. For instance, @0, @1, @2 will never occur, so the corresponding rules never activate, and so that @ is replaced back to ^ without having accomplished anything.
I would suggest to split the task in these phases:
- Turn all right side digits to letters (a, b and c)
- Move all letters to the left of all (remaining) digits
- Turn the letters back to digits
You could use a distinct marker for each phase to know “where you are”.
Here is a possible implementation in JavaScript of the Markov algorithm, given a set of rules that will apply the above phases:
<code>// Every rule consists of 3 parts: find, replace, is-terminating-rule
const rules = [
// Map the right-side digits to letters
["^0", "a^", false],
["^1", "b^", false],
["^2", "c^", false],
["^", "@", false], // Mapping completed, go to next phase:
// Move letters left of all digits
["0a", "a0", false],
["0b", "b0", false],
["0c", "c0", false],
["0@", "@0", false],
["1a", "a1", false],
["1b", "b1", false],
["1c", "c1", false],
["1@", "@1", false],
["2a", "a2", false],
["2b", "b2", false],
["2c", "c2", false],
["2@", "@2", false],
["@", "<|", false], // Move completed, go to next phase:
// Change letters back to digits
["a<", "<0", false],
["b<", "<1", false],
["c<", "<2", false],
["<", "", false], // Change back completed, go to last phase:
// Terminating rule
["|", "^", true],
];
const result = applyRules("210^120", rules);
console.log("final:", result);
// Used Markov algorithm
function applyRules(str, rules) {
for (let i = 0; i < 5000; i++) { // Avoid infinite loop
const rule = rules.find(([find]) => str.includes(find));
if (!rule) return str;
const [find, replace, terminating] = rule;
str = str.replace(find, replace);
console.log(`apply rule "${find}"=>"${replace}", result="${str}"`);
if (terminating) return str;
}
}</code>
<code>// Every rule consists of 3 parts: find, replace, is-terminating-rule
const rules = [
// Map the right-side digits to letters
["^0", "a^", false],
["^1", "b^", false],
["^2", "c^", false],
["^", "@", false], // Mapping completed, go to next phase:
// Move letters left of all digits
["0a", "a0", false],
["0b", "b0", false],
["0c", "c0", false],
["0@", "@0", false],
["1a", "a1", false],
["1b", "b1", false],
["1c", "c1", false],
["1@", "@1", false],
["2a", "a2", false],
["2b", "b2", false],
["2c", "c2", false],
["2@", "@2", false],
["@", "<|", false], // Move completed, go to next phase:
// Change letters back to digits
["a<", "<0", false],
["b<", "<1", false],
["c<", "<2", false],
["<", "", false], // Change back completed, go to last phase:
// Terminating rule
["|", "^", true],
];
const result = applyRules("210^120", rules);
console.log("final:", result);
// Used Markov algorithm
function applyRules(str, rules) {
for (let i = 0; i < 5000; i++) { // Avoid infinite loop
const rule = rules.find(([find]) => str.includes(find));
if (!rule) return str;
const [find, replace, terminating] = rule;
str = str.replace(find, replace);
console.log(`apply rule "${find}"=>"${replace}", result="${str}"`);
if (terminating) return str;
}
}</code>
// Every rule consists of 3 parts: find, replace, is-terminating-rule
const rules = [
// Map the right-side digits to letters
["^0", "a^", false],
["^1", "b^", false],
["^2", "c^", false],
["^", "@", false], // Mapping completed, go to next phase:
// Move letters left of all digits
["0a", "a0", false],
["0b", "b0", false],
["0c", "c0", false],
["0@", "@0", false],
["1a", "a1", false],
["1b", "b1", false],
["1c", "c1", false],
["1@", "@1", false],
["2a", "a2", false],
["2b", "b2", false],
["2c", "c2", false],
["2@", "@2", false],
["@", "<|", false], // Move completed, go to next phase:
// Change letters back to digits
["a<", "<0", false],
["b<", "<1", false],
["c<", "<2", false],
["<", "", false], // Change back completed, go to last phase:
// Terminating rule
["|", "^", true],
];
const result = applyRules("210^120", rules);
console.log("final:", result);
// Used Markov algorithm
function applyRules(str, rules) {
for (let i = 0; i < 5000; i++) { // Avoid infinite loop
const rule = rules.find(([find]) => str.includes(find));
if (!rule) return str;
const [find, replace, terminating] = rule;
str = str.replace(find, replace);
console.log(`apply rule "${find}"=>"${replace}", result="${str}"`);
if (terminating) return str;
}
}