There's more than one way to do things PerlMonks

### Re: Challenge: Hidden Message

by Limbic~Region (Chancellor)
 on May 10, 2006 at 14:00 UTC ( #548463=note: print w/replies, xml ) Need Help??

in reply to Challenge: Hidden Message

All,
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.

```#!/usr/bin/perl
use strict;
use warnings;
use constant PATH  => 0;
use constant DEPTH => 1;

my @str = map {chomp; \$_} <DATA>;
print LCS(@str), "\n";

# Longest Common Subsequence in strings
# Change required for duplicate chars
sub LCS{
my @str = @_;

# Map the position of each char in each string

my @pos;
for my \$i (0 .. \$#str) {
my \$line = \$str[\$i];
for (0 .. length(\$line) - 1) {
my \$letter = substr(\$line, \$_, 1);
\$pos[\$i]{\$letter} = \$_;
}
}

# Use 1 line as ref to map pos of same char in all lines
# If lines are variable length, use smallest as ref
# Establish lookup table also

my (%lookup, @order);
for my \$letter (split //, \$str[0]) {
my \$char_map = [ map { \$pos[\$_]{\$letter} } 0 .. \$#pos ];
\$lookup{\$char_map} = \$letter;
push @order, \$char_map;
}

# Predetermine which char mappings are greater than others

my %greater;
for my \$i (0 .. \$#order) {
for my \$j (grep \$_ != \$i, 0 .. \$#order) {
push @{\$greater{\$order[\$i]}}, "\$order[\$j]" if is_greater(@
+order[\$i, \$j]);
}
}

# A max depth watermark and a path representing that depth
my (\$max, \$path) = (0, '');

# Work queue of only char maps with char maps greater then it
my @work = map [\$_, 1], grep @{\$greater{\$_}}, keys %greater;

while (@work) {
my \$item = pop @work;
(\$max, \$path) = (\$item->[DEPTH], \$item->[PATH]) if \$item->[DEP
+TH] > \$max;
my \$last_node = (split /:/, \$item->[PATH])[-1];
next if ! exists \$greater{\$last_node};
my @next_node = @{ \$greater{\$last_node} };
push @work, map ["\$item->[PATH]:\$_", \$item->[DEPTH] + 1], @nex
+t_node;
}

my \$hidden_msg = join '', map \$lookup{\$_}, split /:/, \$path;
return \$hidden_msg;
}

# Are all vals in ref2 greater than corresponding vals in ref1
sub is_greater {
my (\$ref1, \$ref2) = @_;

# Stop at end of smallest ref
my \$end = \$#\$ref1 > \$#\$ref2 ? \$#\$ref2 : \$#\$ref1;

for (0 .. \$end) {
return 0 if \$ref2->[\$_] <= \$ref1->[\$_];
}
return 1;
}

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.

I hope that you enjoyed this challenge.

Cheers - L~R

Create A New User
Node Status?
node history
Node Type: note [id://548463]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (3)
As of 2020-02-20 05:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
What numbers are you going to focus on primarily in 2020?

Results (86 votes). Check out past polls.

Notices?