4
$\begingroup$

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?

  • 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.2010-12-24
  • 0
    @Moron: Added. I'd say it's basically walking on x-y coords, or complex plane, if you want to.2010-12-24
  • 0
    So you want an algorithm which ignores part of the string? I suppose that won't be possible.2010-12-24
  • 0
    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" -> ""...2010-12-24
  • 1
    @Martin: Don't you need to "walk" the string to detect the patterns?2010-12-24
  • 0
    Hmm, that's probably true. Still, I was hoping for some formula similar to the final_rotation(). I guess this is a dead-end. Fortunately I have some other approaches left to try...2010-12-24
  • 0
    To compute `final_rotation`, you need to count the number of occurrences of *x* and *z* in the string, so you still have to traverse the whole string. Linear time is the best you can do in either case. If your code is too slow, you may be able to optimize it, but that's a programming question that would belong on StackOverflow.2010-12-25

1 Answers 1

1

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.