Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
If you know exactly how a string can be used to get the a and b values, you should provide that. Otherwise, you are basically asking people to guess. –  Aryabhata Dec 24 '10 at 19:35
    
@Moron: Added. I'd say it's basically walking on x-y coords, or complex plane, if you want to. –  Martin Janiczek Dec 24 '10 at 19:49
    
So you want an algorithm which ignores part of the string? I suppose that won't be possible. –  Aryabhata Dec 24 '10 at 20:28
    
No, I want an algorithm that doesn't "walk" the string (because in some cases it's just too long). Maybe the algorithm should would work with some kind of patterns of substrings, e.g. "xxxx" -> ""... –  Martin Janiczek Dec 24 '10 at 20:40
1  
@Martin: Don't you need to "walk" the string to detect the patterns? –  Aryabhata Dec 24 '10 at 21:10
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.