Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Re: Challenge: Hidden Message

by Unanimous Monk (Sexton)
on May 11, 2006 at 01:50 UTC ( #548598=note: print w/replies, xml ) Need Help??


in reply to Challenge: Hidden Message

Well, here's my first crack at it.

use strict; use Data::Dumper; my %result; { ### Populate initial tree my @prev; my $temp=<DATA>; chomp $temp; foreach my $char (split '', $temp) { foreach my $pchar (@prev) { $result{$pchar}{$char}{valid} = 1; }; push @prev, $char; }; }; { ### Prune invalid data while (<DATA>) { chomp; my @invalid; foreach my $char (split '') { foreach my $ichar (@invalid) { $result{$char}{$ichar}{valid} = 0; }; push @invalid, $char; }; }; } my $maxdepthchar; { ### Determine depth of each tree my $maxdepth; foreach my $char (keys %result) { getdepth(\%result, $char); if ($result{$char}{depth} > $maxdepth) { $maxdepth = $result{$char +}{depth}; $maxdepthchar = $char }; }; } { ### Output longest string while ($maxdepthchar ne '') { print substr($maxdepthchar,0,1); $maxdepthchar = $result{$maxdepthchar}{maxdepthchar}; }; } sub getdepth{ my ($ref, $char) = @_; my %result = %{$ref}; my $maxdepth; my $maxdepthchar; if ($result{$char}{depth} eq undef) { foreach my $key (keys %{$result{$char}}) { if ($result{$char}{$key}{valid}) { my $depth = getdepth(\%result, $key); if ($depth > $maxdepth) { $maxdepth = $depth; $maxdepthchar = + $key } }; }; $result{$char}{depth} = $maxdepth+1; $result{$char}{maxdepthchar} = $maxdepthchar; return $result{$char}{depth}; } else { return $result{$char}{depth}; }; }; __DATA__ CPD6Z98SB2KQNWV0F7Y1IX4GLRA5MTOJHE3U CXZOL6SUI2WTJ30HF519YPGBRNAK48MQVD7E T8COSQU6I2FJN40DKL157WVGPYXARZ3MBHE9 KNCWVZDSR5420LP91FIQGB7Y3A6J8MOUXTEH XF9C4PSDY62TWJ0QBN17IKG3OH8ALVRM5UEZ D9QCHUSN7TW2YZL0O831FGXIR6JA4P5MVBKE ZC7ISQUPK6N20OLV4T31G9FRXBAWM5YJHED8 Z3C7SJVODL25TRQ01HPWGNKXB4UA68YMI9EF BC9OXDHS2FI5Z6U0TYL1VPGQK7ANR38MEWJ4 K4TCQBHS2ZV7FXU0P8R1YGDON3A6JILM9EW5

and a few modifications to allow for multiple longest strings, and repeated chars (although, the output still only outputs one of the longest string, but the hash contains the info for each longest string).

use strict; use Data::Dumper; my %result; { ### Populate initial tree my @prev; my %charcount; my $temp=<DATA>; chomp $temp; foreach my $char (split '', $temp) { $charcount{$char}++; foreach my $pchar (@prev) { $result{$pchar}{$char.$charcount{$char}}{valid} = 1; }; push @prev, $char.$charcount{$char}; }; }; { ### Prune invalid data while (<DATA>) { chomp; my %charcount; my @invalid; foreach my $char (split '') { $charcount{$char}++; foreach my $ichar (@invalid) { $result{$char.$charcount{$char}}{$ichar}{valid} = 0; }; push @invalid, $char.$charcount{$char}; }; # Prune branches that weren't in the string this time around. foreach my $key1 (keys %result) { foreach my $key2 (keys %{$result{$key1}}) { my $found = 0; foreach my $inv (@invalid) { next if $found; $found = ($inv eq $key2); }; if (!$found) { $result{$key1}{$key2}{valid} = 0 }; }; }; # Prune roots that weren't in the string this time around. foreach my $key1 (keys %result) { my $found = 0; foreach my $inv (@invalid) { next if $found; $found = ($inv eq $key1); }; if (!$found) { foreach my $key2 (%{$result{$key1}}) { $result{$key1}{$key2}{valid} = 0; }; }; }; }; } my $maxdepthchar; { ### Determine depth of each tree my $maxdepth; foreach my $char (keys %result) { getdepth(\%result, $char); if ($result{$char}{depth} > $maxdepth) { $maxdepth = $result{$char +}{depth}; $maxdepthchar = $char }; }; } { ### Output longest string while ($maxdepthchar ne '') { print substr($maxdepthchar,0,1); $maxdepthchar = @{$result{$maxdepthchar}{maxdepthchar}}->[0]; }; } sub getdepth{ my ($ref, $char) = @_; my %result = %{$ref}; my $maxdepth; my @maxdepthchar; if ($result{$char}{depth} eq undef) { foreach my $key (keys %{$result{$char}}) { if ($result{$char}{$key}{valid}) { my $depth = getdepth(\%result, $key); if ($depth > $maxdepth) { $maxdepth = $depth; @maxdepthcha +r = ($key) } elsif ($depth == $maxdepth) { $maxdepth = $depth; push @maxdep +thchar, $key }; }; }; $result{$char}{depth} = $maxdepth+1; $result{$char}{maxdepthchar} = \@maxdepthchar; return $result{$char}{depth}; } else { return $result{$char}{depth}; }; }; __DATA__ HOUSEBOAT COMPUTER DOUBT

It ain't pritty, but it works (I think?).

Update:Oops! Fixed general soultion. Needed to trim roots as well as branches. Thanks LR.

Replies are listed 'Best First'.
Re^2: Challenge: Hidden Message
by Limbic~Region (Chancellor) on May 11, 2006 at 17:43 UTC
    Unanimous Monk,
    I am still working on my general purpose solution, but yours does not appear to work with the following:
    __DATA__ HOUSEBOAT COMPUTER DOUBT

    Cheers - L~R

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://548598]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (3)
As of 2020-10-21 22:43 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My favourite web site is:












    Results (223 votes). Check out past polls.

    Notices?