Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:
    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|cite|improve this question
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
@Martin: Don't you need to "walk" the string to detect the patterns? – Aryabhata Dec 24 '10 at 21:10

Assuming that you can represent the string as a number you could build a piece wise function. Piece wise functions can also then be built from the floor function.

$SJF(x) = \lfloor \frac x{(x^2 + 1)^{\frac 12}} \rfloor$ + 1

The above function adds a jump of one at point x = 0.

g(x) + f(x)*SJF(x-h) - f(x)SJF(x-k)

This translates f(x) so that it is only added to g(x) on the range [h, k) if h > k. Or subtracted on [k, h] is k < h.

You can play around with these and see of you can obtain the piece wise function you desire. Then it will be a simple matter of reducing whatever items are combinable.

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.