ABC's isn't always the correct order

[William Koch]

Using only letters A B & C, how many different messages of length N can you type? with the constraint that ABC cannot appear anywhere in the string. For example, typing BACBBC would be fine, but typing BCABCB would not. With this constraint, how many different messages of length N can you type? Does anyone know how to solve it using recursion?

N is the length so my solution so far say if it starts with an B or C then there are f(N-1) ways the rest of the string could be arranged. If it starts with an A then there are 4*f(N-3) ways we can arrange it. Therefore:

f(N) = f(N-1) + f(N-1) + 4*f(N-3).... this is incomplete can anyone point me in the right direction?

[Jayesh A Lalwani]

You don't really need recursion

total number of possible messages of Length N using 3 letters = 3^N

total number of messages that have ABC are
ABCXXX....
XABCXX....
XXABCX....
.
.
.
....XXXABC

This is always going to be N-2

So, total number of legal messages = 3^N - N + 2

[William Koch]

Jayesh that will not work. For example if there is a string of length 5 then there are 3^5 ways to arrange those 3 characters (you can resuse them) so 3^5=243 , now we need to look through those 243 and find out which ones have the string ABC in it, count those and subtract that count from 243 to get our answer in this case the correct answer would be 216 ( there are 27 strings where ABC appears). Your approach does not hold for all cases.

[Rob Spoor]

How about XABCXABCX? That's two occurrences of ABC instead of one.

[William Koch]

my point exactly. There is a way to do this where you can use recursion and I started it at the beginning of the thread but it is incomplete does anyone know how to complete this and take into account duplicates, triplets, etc? If my initial part is incorrect please let me know.

[Greg Charles]

Jayesh had the right idea, but didn't get the combinatorics exactly right.

For something like, ABCXX...., you can't count that as 1, because there are multiple values of XX... So, instead of 3^n - (n-2), you have 3^n - (n-2)*3^(n-2). But even that isn't right, because it will twice subtract a string like ABCCCABC.

That may be where the recursion comes in. For each of n-2 positions ABC could hold, you need to multiply 3^m (where m is the number of characters left after the C) by f(k) (where k is the number of characters before the A, and f is the recursive call, ie. the number of ways those k characters could be arranged and not hold "ABC".)

[Paul Clapham]

You're already going in the right direction, William.

If S is a valid production of the grammar then so are BS and CS. That's the first two terms of the equation in your original post. However AS might or might not be valid... basically you now want a count of the number of valid strings of the form BCS so you can subtract that.

[Greg Charles]

Yep, I just coded that up and it worked.

Here's a brute force method I wrote for checking my answer:

	public int countBruteForce(int length) {
		final int max = (int)Math.pow(3,length);
		int count = 0;
		for (int i = 0; i < max; i++) {
			String s = Integer.toString(i, 3);
			for (int pad = s.length(); pad < length; pad++) {
				s = '0' + s;
			}
			if (!s.contains("012")) {
				count++;
			}
		}
		return count;
	}