"Start with some number of >'s lined up on the left side of a page, followed by a single space and then an equal number of <'s lined up on the right. The goal is to achieve the mirror image (>'s lined up on the right, <'s lined up on the left, with a single space between them). There are two legal moves:
- Either symbol may swap places with the space, if it is adjacent.
- Either symbol may swap places with the space, if it is separated from it by a symbol of the opposite type.
Here's a solution for a single symbol of each type:
| start | > | < | |
| move 1 | > | < | |
| move 2 | < | > | |
| move 3 | < | > |
Is there a general solution for an arbitrary number of >'s and <'s, with a single space in the middle? What is the minimum number of moves required?"
Looks like a standard problem, but fights back well. The problem has two parts:1) find a general solution
2) find the minimum number of moves. (which adds an extra condition to (1)).
I have made some progress towards both requirements. My notes so far are below:
-----
1) Find a general solution:
Now, this is quite difficult; because the number of possible "moves" grows rapidly as the number of symmetrical symbols increases.
It is also not clear what the most efficent way of doing things is; and how to develop a scalable, general solution.
After a lot of experimentation, I found the following:
For ">_<", ">>_<<" and ">>>_<<<" the minimum number of moves (I found) were 3, 8 and 19, respectively. Such numbers do not play well with a natural number formula; flooring/ceiling might be required.
Upon looking at this problem, I immediately suspected that It could be solved in a recursive fashion. For example, the solution to ">>_<<" can be found by first solving for ">_<". Doing this guarentees a solution to any problem of size n for this question; however it is NOT the most efficent way of doing things.
Consider the case k = 2 ">>_<<".
Solving by using the case k=1, the solution is as follows:
0: >>_<<
1: >_><<
2: ><>_<
3: >(<_>)<
4: >_<><
5: _><><
6: <>_><
7: <><>_
8: <><_>
9: <_<>>
10: <<_>>
Compared to not solving the problem recursively; NOT solving for the k-1 case first:
0: >>_<<
1: >_><<
2: ><>_<
3:><><_
4:<>_<>
5:_<><>
6:<_><>
7:<<>_>
8:<<_>>
My next focus was on a particular forms that are ideal for the solution. You may have noticed that many things "come together" for the sort, when the "<><>_" or "_<><>" form is encountered.
Consider a larger case of this form: <><><>_
0: <><><>_
1: <><><_>
2: <><_<>>
3: <_<><>>
4: <<_><>>
5: <<<>_>>
6: <<<_>>>
Beautiful! I call this form the outward paired form; naturally because the symbols are paired, and point outwards. Notice that for moves 2 to 6, only jump swaps were done; no movement of the space was needed at any point; this gives some indication of high efficency (intuitively).
Out of curiosity, I also investigated the inward paired form:
0: ><><(><_)
1: ><(><_)<>
2: ><_<><>
3: _<><><> [just results in outward paired form!]
However, this is because we only traveled in one direction, start at 1 again...
1: ><(><_)<>
2: ><_<><>
3: ><<(_><)>
4: ><<<>_>
5: ><<<_>>
6: ><<_<>>
7: ..... not quite as efficent; we need to travel all the way to the end, and keep flipping.
=> Forget about inward paired form (for now).
Later, I will provide a formula for the general number of moves for k symbols, given that the string is in outward paired form.
Of course, this raises the question: for all the moves you spend to put the string in outward paired form, is there a more efficent way? what if substrings (k-1) were put into outward paired form instead?
2) find the minimum number of moves. (which adds an extra condition to (1)).
As you can see from above, I am still investigating this.
Then, my next research objective is to learn more about outward paired form, and in particular:
-is it better to use outward paired form recursively?
-Or...should the whole expression be put into outward paired form? Which is more efficent?
Such bring us closer to solving a general and efficent method for the problem as a whole.
