Meaningless Drivel is fun!*
The moose likes Java in General and the fly likes ABC's isn't always the correct order Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "ABC Watch "ABC New topic
Author

ABC's isn't always the correct order

William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76
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
Bartender

Joined: Jan 17, 2008
Posts: 2320
    
  28

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
Ranch Hand

Joined: Sep 26, 2012
Posts: 76
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
Sheriff

Joined: Oct 27, 2005
Posts: 19670
    
  18

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


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76
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
Sheriff

Joined: Oct 01, 2001
Posts: 2848
    
  11

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
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

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
Sheriff

Joined: Oct 01, 2001
Posts: 2848
    
  11

Yep, I just coded that up and it worked.

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

 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: ABC's isn't always the correct order