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?

  • 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 $w$hole string. Linear time is the best you can do in either case. If your code is too slo$w$, 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.