I'm stuck on this problem:
I have a "truth-table" (well, I don't know if it can be called truth table, if there aren't true/false values only):
string | a | b
---------------------
x | 1 | 0
z | 1 | 0
xx | 1 | 1
xz | 1 | 1
zx | 1 | -1
zz | 1 | -1
xxx | 0 | 1
xxz | 0 | 1
xzx | 2 | 1
xzz | 2 | 1
zxx | 2 | -1
zxz | 2 | -1
zzx | 0 | -1
zzz | 0 | -1
... the list goes on for string of any length, e.g. xxzxxzxxzzxzzxx -> a = -4, b = -1.
I can calculate the a and b values from a given string, but the number of steps grows with the length of the string. I am hoping for some kind of better algorithm.
Edit: Here is my original algorithm:
rotation = 0 // 0 -> up, 1 -> right, 2 -> down, 3 -> left
pos_x = 0 // this is the "b"
pos_y = 0 // this is the "a"
function rotate (n):
rotation += n
rotation %= 4 // result is positive integer, e.g. -1 % 4 = 3
function forward (n):
if n == 0: pos_y++
if n == 1: pos_x++
if n == 2: pos_y--
if n == 3: pos_x--
for char in string:
forward()
if char == "x": rotate(1) // to the right
else: rotate(-1) // to the left
I can easily get the final rotation from a string:
function final_rotation (n):
rot = (number of occurences of "x") - (number of occurences of "z")
rot %= 4
return rot
But the pos_x and pos_y (or a and b)? No idea :/
The Karnaugh-maps came to my mind - but I'm unsure how to deal with this, since the values of a and b aren't true/false, but integers.
Also it looks like it's ternary logic, because of the three possible states of string[position] - x, z, none.
As far as I understand this, the last (rightmost) letter of a string doesn't have a say in what the a and b values will be. But what does?
So, my question is - how to find the algorithm for a and b?