rotate string with authors note
Back to General discussions forum
I don't get the idea of rotating twice with 2 centers, can someone explain ? My solution is in-place O(n) using modular arithmetic (https://www.codeabbey.com/index/task_solution?task=rotate-string&user=simyager&lang=LISP).
Hi! Honestly I'm doubt that there are many people who can read your solution :)
of rotating twice with 2 centers
it is rather about reverting twice
Regard your username as an example. Let's first reverse it around its "main" centre, and then reverse again around
the centre shifted by 1 position left.
S I M Y A G E R
|
R E G A Y M I S
|
M Y A G E R S I
On the second revert operation we'll need to "wrap around" two letters "falling out" into negative positions.
Anyway, you see, the string is rotated. The approach doesn't pretend to be the fastest, but of course is O(n) also.
Now I kinda understand it, I'll try implementing it. I don't think I could come up with this myself, doesn't seem intuitive.
I'm doubt that there are many people who can read your solution :)
Is it because of lisp or the algorithm ?
I think the code is readable but you have to know setf, aref, rotatef
and so on do, these usually have their own syntax in other languages like = and arr[i].
When it comes to the algorithm, I tried a couple examples in my mind and it seemed to hold up, but I haven't mathematically proved it.