I have the feeling that this problem can not be solved with less then 9*k+7 rows in the control table(my solution has exactly 9*k+7 rows) but I have not proven it. Has anybody a shorter solution?

Edited by author 06.04.2008 23:24

It can be solved using O(log(n) + log(k)) rows.

Do it like that:

1) put AA right before # to the left. This is 00 written base 26.

2) go right until you encounter -. Put + there and then go left until you hit #. Increase that number (it will become AB). Then go right again.

3) if you encounter # while walking right, go left and compute coordinate of last - mathematically using cells to the left as memory with base-26 2-digit arithmetics. For arbitrary k and n it will be more than 2 of course, that's why it's O(log(k)+log(n)), but not a constant.

4) like in case of 2 run right/left by putting - instead of + until result becomes zero (decrease it with every - set).

5) Find rightmost - and paint everything to the left with +

6) Find - and stop there

Though, I heard in this forum that the checker is wrong as it stops when there are n-1 pluses, but not when invalid state/character pair is met. So, actually you will have to use O(n) states to calculate 'n' and then bring back this value to calculation area inside read/write head :)

My solution for each k output 604 lines.

How did you do this? My solution uses 1003 lines for each k, and I don't know how to optimize it :(

I also came up with 604 lines solution. Just go to the right incrementing the state (200 instructions), then output "X # something_related_to_josephus # <" for X in range [2, 201]. You've spent 400 states. Now your state number should have the information how many steps left you should make outputting '+' -- you will need 199 instructions for this. After that you'll have to add 5 more instructions

JOSEPHUS_POINT - LEFT_MODE - <
LEFT_MODE - LEFT_MODE + <
LEFT_MODE # RIGHT_MODE # >
RIGHT_MODE + RIGHT_MODE + >
RIGHT_MODE - FINISH - =