|There's more than one way to do things|
Re: Challenge: Hidden Messageby Limbic~Region (Chancellor)
|on May 10, 2006 at 14:00 UTC||Need Help??|
The following is an in-depth explanation of the entire challenge. For those of you who have given up or are only interested in the answer, read on. For anyone else still working on it - you have been warned.
I was looking at problems related to the longest increasing subsequence and found the longest common subsequence . The intriguing thing about the problem was that the subsequence doesn't not need to be contiguous. Additionally, I couldn't find an actual implementation that handled more than 2 strings at a time. I was originally hoping to create a matrix mapping of characters and positions. Using that, I thought I could collapse each row of the matrix into a single numerical value so that I could use the patience sorting to find the longest common substring.
My first pitfall was that the matrix is only 2 dimensional if no chars are duplicated within a single row. This was easy to overcome as I could just impose this restriction on the challenge. The second pitfall was in collapsing the rows into a single numerical value. In a nutshell, one row is consider greater than another row if and only if all the values in the first row are greater than the corresponding values in the second row. There really isn't a way to do partial ordering.
I realized I could still create separate piles of rows that are greater than other rows. The largest pile would represent the solution. To expedite the process, I precalculated some information which requires N^2 - N passes where N is the length of the shortest line (36). Building the piles only required an additional 597 iterations for this particular puzzle. Not bad. It could be better by adding cacheing such that piles are abandoned as soon as it is known that they can not exceed the current largest pile.
This solution is challenge specific. Work would need to be done to allow for duplicate chars within a line. Very minor tweaking would also be necessary to allow for variable length lines. All in all, it was a very fun diversion.
The answer 'CS 201 GAME' was meant to imply a second year computer science student should have fun with it. Generating the hidden message was easy. I just presized a string of 36 spaces and allocated 4 positions (36/9) for each char in my solution. I placed those chars first and then just filled any remaining space with a random remaining character.
Cheers - L~R