wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> smallest string with nondistinct consecutive chars
        
(Message started by: inexorable on Sep 21^st, 2012, 12:17pm)

Title: smallest string with nondistinct consecutive chars
Post by inexorable on Sep 21^st, 2012, 12:17pm

Given a string consisting of a, b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'.

What is the smallest string which can result by applying this operation repeatedly?

Title: Re: smallest string with nondistinct consecutive c
Post by Aryabhatta on Sep 22^nd, 2012, 8:37pm

Haven't thought through completely, but seems like the smallest string is of length either 1 or 2 (of the same character).

Basically if n_a, n_b, n_c are the number of a's, b's and c's in the string.

Then either all three (n_a,n_b,n_c) are of the same parity, in which case, the answer is 2 and that can be made to be either the first or last character of the string.

Or there is one of a different parity, say n_a, in which case, we can end up with a single a.

A proof by induction seems to work, but since you have posted this in the cs forum...

The observation used is that the parity of n_a+n_b, n_b+n_c, n_a + n_c are invariant.

Title: Re: smallest string with nondistinct consecutive c
Post by towr on Sep 23^rd, 2012, 2:15am

on 09/22/12 at 20:37:06, Aryabhatta wrote:

Haven't thought through completely, but seems like the smallest string is of length either 1 or 2 (of the same character).

Definitely not so if you start with a string that contains only the same character (more than two time). You can't reduce, say, aaaaaaaaaaa to anything smaller.

Title: Re: smallest string with nondistinct consecutive c
Post by Aryabhatta on Sep 23^rd, 2012, 7:58am

on 09/23/12 at 02:15:23, towr wrote:

Definitely not so if you start with a string that contains only the same character (more than two time). You can't reduce, say, aaaaaaaaaaa to anything smaller.

Yes, those are the special cases I forgot to mention and I suppose you agree that they are the uninteresting cases :)

Title: Re: smallest string with nondistinct consecutive c
Post by towr on Sep 23^rd, 2012, 12:43pm

Well, seeing as this is a CS puzzle, I'm guessing we need to find an algorithm that will lead us to the shortest string. In which case it's important not to get trapped in those special cases, since that's quite easy.
Say you have abccc, and approach it greedily from left to right, then abccc => cccc, and you're stuck. Whereas a winning route is e.g. abccc => aacc => abc => cc.

Title: Re: smallest string with nondistinct consecutive c
Post by Aryabhatta on Sep 23^rd, 2012, 9:10pm

The proof by induction actually gives an algorithm.

Let n_a, n_b, n_c be the numbers of a's, b's and c's.

At least two of n_a, n_b, n_c have the same parity (even or odd basically): say n_b and n_c.

Property P: Also keep the observation in mind that an operation keeps the parity of n_a+n_b, n_b + n_c and n_c+n_a invariant.

Case I)

First consider the case when n_a is of different parity than n_b and n_c. Since we will always end up with a string formed by a single character(possibly repeated), by property P above, we end up with an odd number of a's. By induction on the length of the string, this will be shown to be a single a.

Given a string satisfying Case I), we simply make one transformation which involves an a (or any random transform if there aren't any a's). This reduces the length, while maintaining the property of n_a being different from n_b and n_c (parity wise), and not making the whole string comprise solely of 3 or more a's (or b's or c's). By induction, we can now claim that we will end up with a single a.

This give an algorithm: Picking any transform which does not make all the characters equal (and there will always be one, as we greedily pick the one with mismatched parity, if it exists).

Case II)

Now consider the second case, when all have the same parity.

Consider one of the characters at the end, say c.

Now consider the string without that c. In this string, n_c has different parity from the others, and by the above Case I, that string can be transformed to c.

Thus the whole string can be transformed to cc.

cc is the best we can do, since parity of n_a + n_c is invariant, and thus the number of c's at the end has to be even.

This gives an algorithm for the all same parity case: fix an end, and then apply the transformations as in Case I).

For instance in the example you give:
abccc: Fix the last c and consider abcc -> aac->ab->c

Thus we get to cc.

If we chose to fix a, we can get to aa.