[1/(ln x)]

Here is the problem:

We are given a string of 2s. We want to replace all possible strings of "222" with "11" and output the number of equivalent "words" or strings.

Example:

The string of 2s is 2222, then the equivalent strings are:

2222
112
211

I know that the replace method will take 2222 and give 112, but how in Java can I get the program to output 211?

I've heard of the replaceAll method, but how do I implement it so that the program outputs both 112 and 211?

[TripleM]

Why are you trying to output those strings? You want to output how many there are, which is a completely different problem which can be solved by DP.

There's really no easy way to use any replace methods to do this, since you may want to say 'replace the 222s at positions 3,7,12, and 21', and leave the others as they are. So in this case, you'd just tell it to replace the 222 at position 1, ie s.substring(0,1)+"11"+s.substring(4). Obviously, thats not really what you were asking, but since it completely depends on which set of 222s you want to replace, theres no other choice.

[SimonM]

Is it possible to log the points which you make the substitutions at.

For example on the string 22222

First sweep

22222 -> 1122 Log 1

Starts at 22222
Gets to the 2nd place
then is
2112

etc

I'll come up with an implementation in a sec if you want

[h_s_potter2002]

If you start out with like, "222222", should your program output "11222" as an equivalent word, even though there's still a "222" in "11222"?

[1/(ln x)]

TripleM wrote:

Why are you trying to output those strings? You want to output how many there are, which is a completely different problem which can be solved by DP.

I actually need the how many there are, but I couldn't think of a way to do it. What is DP?

SimonM wrote:

Is it possible to log the points which you make the substitutions at.

I can't think of one right off the top of my head.

h_s_potter2002 wrote:

If you start out with like, "222222", should your program output "11222" as an equivalent word, even though there's still a "222" in "11222"?

The program should output 11222 and 1111 (by changing the 222 to 11 in 11222) because are equivalent 222222.

[TripleM]

DP is dynamic programming. Quite similar to induction.

Here are some steps to get started with (not a full solution, I'll leave the main part to you):

Define f(n) = the number of strings equivalent to the last n digits of your initial string.
So f(0) = 1, since theres one string (the empty string) equivalent to the empty string.

If the string was 111111222, then f(3) = 2, since there are two strings equivalent to 222 (namely, 222 and 11).

Now, assume you have already calculated f(0), f(1), ... f(n-1).

How can you calculate f(n)? (There are two different cases to consider).

[h_s_potter2002]

I don't think you really need DP if you have to output every possible string.

[TripleM]

h_s_potter2002 wrote:

I don't think you really need DP if you have to output every possible string.

You don't, that was the point.

[1/(ln x)]

TripleM wrote:

DP is dynamic programming. Quite similar to induction.

Here are some steps to get started with (not a full solution, I'll leave the main part to you):

Define f(n) = the number of strings equivalent to the last n digits of your initial string.
So f(0) = 1, since theres one string (the empty string) equivalent to the empty string.

If the string was 111111222, then f(3) = 2, since there are two strings equivalent to 222 (namely, 222 and 11).

Now, assume you have already calculated f(0), f(1), ... f(n-1).

How can you calculate f(n)? (There are two different cases to consider).

OK, so the two cases are

Case 1. The string begins with a 1.
Case 2. The string begins with a 2.

Case 1:

Two subcases:
11_ _ _ _ _....
12_ _ _ _ _.... -> This will give f(n) = f(n-1), because we can't make any substitutions with the 12

Case 2:

Four subcases:
211_ _ _ _ _.... -> This will give f(n) = f(n-1), because we can't do any more substitutions
212_ _ _ _ _.... -> Same as 211 case
221_ _ _ _ _.... -> Same as 211 case
222_ _ _ _ _....

Now I am stuck with the 11_ _ _ _ _.... and 222_ _ _ _ _.... cases. Any ideas?

For example, for the string, 11 221111 which can give 222 221111, but then we have a 2 22 place where we can substitute but was not counted in the f(n-1) equivalent words.

[TripleM]

Oh wait, so you're allowed to replace 11 with 222 as well? (Originally it was just 222->11) OK, thats a different problem altogether, let me think about that..

[TripleM]

So, just to clarify, are you counting 222222 and 12221 equivalent? (222 222 -> 11 11 -> 1 11 1 -> 1 222 1).

[1/(ln x)]

TripleM wrote:

So, just to clarify, are you counting 222222 and 12221 equivalent? (222 222 -> 11 11 -> 1 11 1 -> 1 222 1).

Yeah, 222 can be replaced by 11 and vice versa.

[TripleM]

Hmm.. what are the constraints on the number of 2s you start with?

Out of interest, where did this question come from? It would be nice to see some original wording just so I can make sure I am solving the right problem

[JBL]

If we change all the 1s to 3s, we can think of this as a sort of action on the set of strings composed of 2s and 3s summing to ; then the broadest question is to find the orbits of this action (although actually we're only asked to find the size of the orbit of a given element). Here's a "mathematician's algorithm" (i.e., a process that certainly works but may not be implementable or efficient) for doing this recursively:

For it is easy (there is only one element, and it is its own orbit). I'm going to make up a notation and describe these situations by , and , while for I'd write and for , . Suppose we've calculated these orbits up to . To calculate the orbits for , start by taking the orbits for and prepending a onto each element of every orbit, and taking the orbits for and prepending a onto each element of every orbit. For example, for I begin with . Now, what I have is a refinement of the set of orbits, so I need to check when two of these can actually be joined together. To do this, consider the orbits that came from . For any element that begins with (after we've prepended a ), switch that out for a and join the orbit of what you've started with to the orbit of what you get. In our example with , we have the element that now begins with ; we switch it to a to get and join the two orbits together to get our final result, . Rinse and repeat.

Since the number of elements grows exponentially fast, this probably requires exponential time and huge amounts of storage space. Actually, on second thought, you only need to run the "look for a 33, switch to a 222, join the two orbits" step for a single element of each orbit, and the number of orbits most likely grows much more slowly than the number of elements, so the running time may be less miserable (though you still have to store everything).

[JBL]

Further analysis: let be the number of ways to write a string of s and s whose sum is . Then this sequence satisfies the recursion . The number of these strings beginning with a is , so satisfies the same recursion. The growth rate of this is for some constant , where is the root of largest absolute value of the equation , .

Now, I suggested at the end of my previous post that one need only consider a single element of each orbit and that this might make everything more efficient. Unfortunately, the number of orbits also grows exponentially: let be the number of strings of s and s summing to with no two consecutive s and no three consecutive s such that the string begins with a but not a ; let be the number of such strings beginning with a ; and let be the number of such strings beginning with a . Then
and so (plugging the first and third of these equations into the second) .* Thus for some constant , where is the root of largest absolute value of the equation , . Note that every such string is its own orbit, so we have exponentially many orbits (albeit with a smaller base for the exponential).

* Actually, satisfies the simpler recursion , and .


For the curious, here's some raw data (and the ugly Mathematica code used to generate it -- suggestions for improvements welcome):
Hidden Text

{2}

{3}

{22}

{32}, {23}

{222, 33}

{223}, {232}, {322}

{2222, 332, 233}, {323}

{2232}, {2322}, {333, 2223, 3222}

{2323}, {3223}, {3232}, {2233, 2332, 3322, 22222}

{22322}, {2333, 3323, 22223, 23222}, {3233, 3332, 22232, 32222}

{22323}, {23223}, {23232}, {32232}, {32322}, {3333, 22233, 22332, 23322, 32223, 33222, 222222}

{32323}, {22333, 23323, 33223, 222223, 223222}, {23233, 23332, 33232, 222232, 232222}, {32233, 32332, 33322, 222322, 322222}

{223223}, {223232}, {232232}, {232322}, {322322}, {32333, 33323, 222323, 322223, 323222}, {23333, 33233, 33332, 222233, 222332, 223322, 232223, 233222, 322232, 332222, 2222222}

{232323}, {322323}, {323223}, {323232}, {223233, 223332, 233232, 332232, 2222232, 2232222}, {232233, 232332, 233322, 332322, 2222322, 2322222}, {33333, 222333, 223323, 233223, 322233, 322332, 323322, 332223, 333222, 2222223, 2223222, 3222222}

{2232232}, {2232322}, {2322322}, {232333, 233323, 332323, 2222323, 2322223, 2323222}, {322333, 323323, 333223, 2223223, 3222223, 3223222}, {323233, 323332, 333232, 2223232, 3222232, 3232222}, {223333, 233233, 233332, 332233, 332332, 333322, 2222233, 2222332, 2223322, 2232223, 2233222, 2322232, 2332222, 3222322, 3322222, 22222222}

{2232323}, {2322323}, {2323223}, {2323232}, {3223223}, {3223232}, {3232232}, {3232322}, {2232233, 2232332, 2233322, 2332322, 3322322, 22222322, 22322222}, {233333, 332333, 333323, 2222333, 2223323, 2233223, 2322233, 2322332, 2323322, 2332223, 2333222, 3222323, 3322223, 3323222, 22222223, 22223222, 23222222}, {323333, 333233, 333332, 2223233, 2223332, 2233232, 2332232, 3222233, 3222332, 3223322, 3232223, 3233222, 3322232, 3332222, 22222232, 22232222, 32222222}

{3232323}, {22322322}, {2232333, 2233323, 2332323, 3322323, 22222323, 22322223, 22323222}, {2322333, 2323323, 2333223, 3323223, 22223223, 23222223, 23223222}, {2323233, 2323332, 2333232, 3323232, 22223232, 23222232, 23232222}, {3223233, 3223332, 3233232, 3332232, 22232232, 32222232, 32232222}, {3232233, 3232332, 3233322, 3332322, 22232322, 32222322, 32322222}, {333333, 2223333, 2233233, 2233332, 2332233, 2332332, 2333322, 3222333, 3223323, 3233223, 3322233, 3322332, 3323322, 3332223, 3333222, 22222233, 22222332, 22223322, 22232223, 22233222, 22322232, 22332222, 23222322, 23322222, 32222223, 32223222, 33222222, 222222222}

{22322323}, {22323223}, {22323232}, {23223223}, {23223232}, {23232232}, {23232322}, {32232232}, {32232322}, {32322322}, {3232333, 3233323, 3332323, 22232323, 32222323, 32322223, 32323222}, {2233333, 2332333, 2333323, 3322333, 3323323, 3333223, 22222333, 22223323, 22233223, 22322233, 22322332, 22323322, 22332223, 22333222, 23222323, 23322223, 23323222, 32223223, 33222223, 33223222, 222222223, 222223222, 223222222}, {2323333, 2333233, 2333332, 3323233, 3323332, 3333232, 22223233, 22223332, 22233232, 22332232, 23222233, 23222332, 23223322, 23232223, 23233222, 23322232, 23332222, 32223232, 33222232, 33232222, 222222232, 222232222, 232222222}, {3223333, 3233233, 3233332, 3332233, 3332332, 3333322, 22232233, 22232332, 22233322, 22332322, 23322322, 32222233, 32222332, 32223322, 32232223, 32233222, 32322232, 32332222, 33222322, 33322222, 222222322, 222322222, 322222222}

{23232323}, {32232323}, {32322323}, {32323223}, {32323232}, {22322333, 22323323, 22333223, 23323223, 33223223, 222223223, 223222223, 223223222}, {22323233, 22323332, 22333232, 23323232, 33223232, 222223232, 223222232, 223232222}, {23223233, 23223332, 23233232, 23332232, 33232232, 222232232, 232222232, 232232222}, {23232233, 23232332, 23233322, 23332322, 33232322, 222232322, 232222322, 232322222}, {32232233, 32232332, 32233322, 32332322, 33322322, 222322322, 322222322, 322322222}, {3233333, 3332333, 3333323, 22232333, 22233323, 22332323, 23322323, 32222333, 32223323, 32233223, 32322233, 32322332, 32323322, 32332223, 32333222, 33222323, 33322223, 33323222, 222222323, 222322223, 222323222, 322222223, 322223222, 323222222}, {2333333, 3323333, 3333233, 3333332, 22223333, 22233233, 22233332, 22332233, 22332332, 22333322, 23222333, 23223323, 23233223, 23322233, 23322332, 23323322, 23332223, 23333222, 32223233, 32223332, 32233232, 32332232, 33222233, 33222332, 33223322, 33232223, 33233222, 33322232, 33332222, 222222233, 222222332, 222223322, 222232223, 222233222, 222322232, 222332222, 223222322, 223322222, 232222223, 232223222, 233222222, 322222232, 322232222, 332222222, 2222222222}

Code:

f[2] = {{{2}}};
f[3] = {{{3}}};
f[4] = {{{2, 2}}};

g[n_] := g[n] = Map[Map[Join[{3}, #] &, #] &, f[n - 3]]
h[n_] := h[n] = Map[Map[Join[{2}, #] &, #] &, f[n - 2]]

f[n_] := f[n] =
  Union[Map[Sort,
    Table[If[MemberQ[g[n][[i]], {3, 3, ___}],
      Join[g[n][[i]],
       h[n][[Position[h[n],
            Join[{2, 2, 2},
             Delete[Cases[
                g[n][[i]], {3,
                 3, ___}][[1]], {{1}, {2}}]]][[1]][[1]]]]],
      g[n][[i]]], {i, 1, Length[g[n]]}]],
   Map[Sort,
    Table[If[MemberQ[h[n][[i]], {2, 2, 2, ___}],
      Join[h[n][[i]],
       g[n][[Position[g[n],
            Join[{3, 3},
             Delete[Cases[
                h[n][[i]], {2, 2,
                 2, ___}][[1]], {{1}, {2}, {3}}]]][[1]][[1]]]]],
      h[n][[i]]], {i, 1, Length[h[n]]}]]]

[JBL]

I've placed two relevant sequences in the OEIS, numbers A133925 and A133926.

[spx2]

actually I think using regexes is the most elegant way to solve the problem.
it is the typical spot where you would use regexes.