Problem Solving: Part II

Last time, I played around with methods to efficently sort a string of angle brackets, into a particular form. I discovered Inward Paired Form (IPF) and Outward Paired Form (OPF), as logical steps to getting a solution to the problem mentioned in the last post.

I believe at this point, I have found the (one of) the most efficent ways to sort the angle bracket strings accordingly. It turns out that the previously rejected IPF is infact useful in the solution to this problem.

Before I go into detail about all of this, let me present a table with my findings:

	“>_<”	“>>_<<”	">>>_<<<”	“>>>>_<<<<”
Start String -> IPF	><_	>_><< ><>_< ><><_	>>_><<< >><>_<< >><><_< >><_<>< >_<><>< _><><><	>>>_><<<< >>><>_<<< >>><><_<< >>><_<><< >>_<><><< >_><><><< ><>_><><< ><><>_><< ><><><>_< ><><><><_
IPF -> OPF	<>_	><_<> _<><>	<>_><>< <><>_<> <><><>_	><><><_<> ><><_<><> ><_<><><> _<><><><>
OPF -> Solution	<_>	<_><> <<>_> <<_>>	<><><_> <><_<>> <_<><>> <<_><>> <<<>_>> <<<_>>>	<_><><><> <<>_><><> <<><>_><> <<><><>_> <<><><_>> <<><_<>>> <<_<><>>> <<<_><>>> <<<<>_>>> <<<<_>>>>

This chart shows the most efficent ways (I could find) of arriving at the solution, for 4 pairs of strings that (increment by one set of <> brackets). The solution I use has the following process:

Start String -> Inward Paired Form -> Outward Paired Form -> Solution

Immediately, the problem of insufficient cleverness arises. How do I know this is the most efficent way to obtain a solution? To be honest, I don't. I there are other cases I could have checked (although, I checked many). I found this method to be fairly straightforward; furthermore: to make the solutions even more efficient after this point became fairly difficult. Because (unlike other, random methods), the one above is easy to conceptualize, in addition to appearing highly efficent, I choose it for my final solution.

Because I am letting the above method be my final solution; I can answer the second part of the question to this problem: What is the minimum number of moves needed for an n bracket string?

Because of the conceptualization of this problem, steps can be fairly easily counted. Let every move be one step. Then, the total number of moves for an arbitrary string of angle brackets is:

| Start String -> IPF| + | IPF -> OPF| + |OPF -> Solution|

Where "||" indicates the number of moves for each process. Let us consider each process in turn:

1) | IPF -> OPF|:

From the table, it can easily be seen that for n sets of brackets, n moves are needed for this step in the solution. Then simply, f(n) = n here.

2) |Start String -> IPF| AND |OPF -> Solution|

A glance at the table shows that both processes have the same number of steps. If f is a function that represents the number of steps for each sub-process, then:

f(0) = 0
f(1) = 1
f(2)= 3
f(3) = 6
f(4) = 10

which results in the following recursive formula:

{ n n = 0, 1 |
f(n) = { |
{ f(n-1) n >= 2 |

We can unwind the formula accordingly....

f(n) = f(n-1) + n
= [f(n-2) + (n-1)] + n
= [f(n-3) + (n-2)] + (n-1) + n
.......
= [0 ] + 1 + 2 .....n

Simply, the sum from 1 to n. So then f(n) = n(n+1)/2 .
-------


Then, our final formula for | Start String -> IPF| + | IPF -> OPF| + |OPF -> Solution| is:

f(n) = 2(n(n+1)/2 ) + n
= n(n+1) + n
= n^2 + 2n


If I have time, I will give some proofs of my findings. That is all, for now.

Problem Solving Post: Part 1

A requirement for the course SLOG is to solve (or at least attempt) to solve a fairly advanced problem, from a list of problems. Its time to complete this requirement. From the list, I chose the following problem to pursue:

"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:

1. Either symbol may swap places with the space, if it is adjacent.
2. 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.