I have hidden a message in the text below:
CPD6Z98SB2KQNWV0F7Y1IX4GLRA5MTOJHE3U CXZOL6SUI2WTJ30HF519YPGBRNAK48MQVD7E T8COSQU6I2FJN40DKL157WVGPYXARZ3MBHE9 KNCWVZDSR5420LP91FIQGB7Y3A6J8MOUXTEH XF9C4PSDY62TWJ0QBN17IKG3OH8ALVRM5UEZ D9QCHUSN7TW2YZL0O831FGXIR6JA4P5MVBKE ZC7ISQUPK6N20OLV4T31G9FRXBAWM5YJHED8 Z3C7SJVODL25TRQ01HPWGNKXB4UA68YMI9EF BC9OXDHS2FI5Z6U0TYL1VPGQK7ANR38MEWJ4 K4TCQBHS2ZV7FXU0P8R1YGDON3A6JILM9EW5
Your mission, should you choose to accept it, is to find the hidden message and report back on the algorithm you used. I have provided 3 clues of increasing insight to help you on your journey. They should be used only as a last resort.
Clue #1:
Clue #2:
Clue #3:
my @str = map {chomp; $_} ;
print LCS(@str), "\n";
sub LCS{
my ($d,$s,%l,%t)=(0,'');
my @p=map{my $i=$_;({map{substr($_[$i],$_,1),$_}0..length($_[$i])-1})}0..$#_;
my @o=map{my $l=$_;my $r=[map $p[$_]{$l},0..$#p];$l{$r}=[$r,$l];$r}split//,$_[0];
for my $i(0..$#o){$t{$o[$i]}=[map{g($o[$i],$o[$_])?"$o[$_]":()}grep$_!=$i,0..$#o]}
my @w=map[$_,1],grep@{$t{$_}},keys%t;
while(@w){my $i=pop@w;($s,$d)=@$i if$i->[1]>$d;
my @n=@{$t{(split/:/,$i->[0])[-1]}}or next;push@w,map["$i->[0]:$_",$i->[1]+1],@n}
join'',map$l{$_}[1],split/:/,$s;
}
sub g{$_[1]->[$_]<=$_[0]->[$_]&&return 0 for 0..(@{$_[0]}>@{$_[1]}?$#{$_[1]}:$#{$_[0]});1}
Cheers - [Limbic~Region|L~R]
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 [id://547199|longest increasing subsequence] and found the [wp://Longest_common_subsequence|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; $_} ;
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->[DEPTH] > $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], @next_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.
Cheers - [Limbic~Region|L~R]
It probably wouldnt be too hard to make it possible to selectively display different spoilers. We already have logic along those lines for handling download links so there is at least a starting point.
Update: And I was right, it wasn't hard. Case closed. :-)
$world=~s/war/peace/g
Your css doesnt highlight links eh? Heh.
I completely overlooked that "Reveal" was a link; how about making it "Reveal this spoiler or spoilers on this page."?
My main objection to this is it doesnt work that nicely when you have "reveal this spoiler or all spoilers in this node or all spoilers on this page"... Although "objection" is definately too strong a word... The truth was the patch was a quickie and doing it the way I did required the least finagling the markup. :-)
$world=~s/war/peace/g
[...|this]--. [...|this spoiler] would be better, but it still obfuscates what the link does ([...|Reveal spoilers] would be even better, but doesn't address the possible desire to have a link that reveals just one spoiler). After noting that there was a patch, I expected to see three links when a node had multiple spoilers (not that I'm convinced that such would or wouldn't be a good idea). I don't have a suggestion, I just wanted to strongly discourage making links labeled "this", which is only slightly better than links labeled "click here".
- tye
I expected to see three links when a node had multiple spoilers
You will see three links, but only in a reply displayed when viewing another node. In that case youll see
The in this node part disappears when the node being rendered is also the focus of the page. For instance if you make Challenge: Hidden Message the focus you'll see that the reply by Unanimous Monk has the links above. But when you make it the focus one link disappears.
BTW, you can also make links that expose multiple specific spoilers at once.
As a side note, ive been thinking that the 'in this node' link really belongs in the "per node links" that are normally on the right, and the "on this page" link should go at the bottom. Then the only link that would remain would be the single mode, so then we could say "Reveal this spoiler" all the time. Which I guess means using HTMLVARS, sigh.
$world=~s/war/peace/g
Yeah, I'd never figure out what that first link does just based on the wording. And why do you assume I'd never want to reveal all of the spoilers in a root node but not in any of the replies? Ah, I see we've got a design conflict between the old design and the new design.
The old "in this node" really means "in this node and all replies to it (and no longer showing the rest of the thread that is currently displayed)", which is why it doesn't apply to the top-most node currently being displayed.
So, if we are going to reveal spoilers individually, I'd abandon much of the old design and make "in this node" really mean "in this node" and not have it change which part of the thread you are viewing. So "in this node" would add that node's ID to the list in ?showspoiler= and the "reveal this spoiler" would add "ID-N" instead and with each click you could reveal another spoiler or another node's-worth of spoilers, or just reveal all spoilers. Something like:
Reveal this spoiler or all spoilers in this thread.
Reveal only this spoiler or all spoilers in this node or in this thread.
All links would use the top-most ID in ?node_id=. "only this spoiler" would have the current ?showspoiler= with ",ID-N" appended. "Reveal this spoiler" and "in this node" would have the current ?showspoiler= with ",ID" appended (and perhaps any "ID-N" for that same node removed). "in this thread" would drop ?showspoiler= and add ?spoil=1.
Make sense?
- tye
Ah, I see we've got a design conflict between the old design and the new design.
Yep, thats it in a nutshell. :-)
Make sense?
I think so. To recap the essence: make showspoiler additive in some situations, make showspoiler handle ID as well as ID-N, with the former meaning 'for all N'. Introduce new links and reorganize.
Oh, I like it by the way. Except maybe the last two links, i wonder if they should only show up once per node, probably on the first spoiler.
$world=~s/war/peace/g
Yes, extra links only on the first spoiler would probably be good.
- tye
Is it about right now? And i assume we are trying to minimize calls to linkNode()? Thats why we are doing the tricks with s///? (I have a weird feeling I should be asking myself that :-)
$world=~s/war/peace/g
No, you've got 5 links showing not 3(max) and the wording doesn't make sense to me, offering to "reveal ... only this node".
I showed two lines, one for nodes with multiple spoilers, one for nodes with a single spoiler. I'm not sure what all of the extra links are for but I don't have time to look further at this time.
- tye
Unfortunately, the author is unable to actually see their own spoiler tags so I didn't know they were all being revealed at once. I am glad this is supposed to be fixed now (demerphq++) but I had to ask someone in the CB just to verify the spoiler tags even worked.
Cheers - L~R
Unfortunately, the author is unable to actually see their own spoiler tags
I don't know how you jumped to that conclusion, but that doesn't match my own experience nor my impression of the implementing code, so I'm pretty certain you are wrong. You can't do much with spoiler tags during preview, of course.
- tye
I wonder if some people are getting confused because there are multiple spoiler modes that can be chosen from Display Settings. The stuff I added would affect only users with 'link' spoiler mode selected.
$world=~s/war/peace/g
I jumped to that conclusion because I assumed my spoiler settings hadn't mysteriously changed without my knowledge. Now that it is once again at "link", I can see I drew the wrong conclusion. I am still at a loss as to how my setting was changed though. Thanks for the friendly reminder to always check assumptions.
Cheers - L~R
use strict;
use Data::Dumper;
my %result;
{ ### Populate initial tree
my @prev;
my $temp=;
chomp $temp;
foreach my $char (split '', $temp) {
foreach my $pchar (@prev) {
$result{$pchar}{$char}{valid} = 1;
};
push @prev, $char;
};
};
{ ### Prune invalid data
while () {
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=;
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 () {
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; @maxdepthchar = ($key) }
elsif ($depth == $maxdepth) { $maxdepth = $depth; push @maxdepthchar, $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.
I am still working on my general purpose solution, but yours does not appear to work with the following:
__DATA__ HOUSEBOAT COMPUTER DOUBT
Cheers - [Limbic~Region|L~R]
I don't see how a person was supposed to solve this without doing some crypto analysis. Could you explain that please? I read your spoiler and thought it'd be trivial to write a regex to extract the solution. Here it is. It's really slow. It'd be faster if I could use backreferences in negated character classes. I could have written this using a regex that generates another regex to incorporate the negated backreference but that seemed like a whole lot of work and I guessed it wouldn't be . It's pretty as-is.
[Updated: Added an expensive and less wasteful version. I'll be adding timing info when my computer has finished running these. They succeed within a few minutes but take a lot longer to finish failing.]
$| = 1;
for ( my $len = 1; ; ++ $len ) {
my $rx = rx1( $len );
my @found = /$rx/ or last;
print "$len: " . join( '', @found ) . "\n";
}
sub rx1 {
# Cheap but wasteful.
# 0 wallclock secs ( 0.00 usr + 0.00 sys = 0.00 CPU) C
# 0 wallclock secs ( 0.00 usr + 0.00 sys = 0.00 CPU) CP
# 0 wallclock secs ( 0.00 usr + 0.00 sys = 0.00 CPU) CPM
# 0 wallclock secs ( 0.01 usr + 0.00 sys = 0.01 CPU) CPME
# 1 wallclock secs ( 0.61 usr + 0.00 sys = 0.61 CPU) CS201
# 4 wallclock secs ( 4.24 usr + 0.00 sys = 4.24 CPU) CS201G
# 24 wallclock secs (23.48 usr + 0.01 sys = 23.49 CPU) CS201GA
# 108 wallclock secs (105.62 usr + 0.02 sys = 105.64 CPU) CS201GAM
# 402 wallclock secs (393.05 usr + 0.05 sys = 393.10 CPU) CS201GAME
# 3917 wallclock secs (3827.03 usr + 0.50 sys = 3827.53 CPU)
#
# real 74m16.003s
# user 72m34.080s
# sys 0m0.588s
my $len = shift @_;
my $pat = "\\A[^\n]*?" . ( "(?:(\\S)[^\n]*?)" x $len ) . "\n"
. "(?:[^\n]*?" . join( '', map "\\$_\[^\n]*?", 1 .. $len ) . "\n)+\\z";
return qr/$pat/;
}
sub rx2 {
# Expensive but less wasteful.
# 0 wallclock secs ( 0.00 usr + 0.00 sys = 0.00 CPU) C
# 0 wallclock secs ( 0.00 usr + 0.00 sys = 0.00 CPU) CP
# 0 wallclock secs ( 0.00 usr + 0.00 sys = 0.00 CPU) CPM
# 0 wallclock secs ( 0.03 usr + 0.00 sys = 0.03 CPU) CPME
# 2 wallclock secs ( 1.66 usr + 0.00 sys = 1.66 CPU) CS201
# 13 wallclock secs (13.27 usr + 0.00 sys = 13.27 CPU) CS201G
# 83 wallclock secs (80.97 usr + 0.00 sys = 80.97 CPU) CS201GA
# 413 wallclock secs (403.82 usr + 0.04 sys = 403.86 CPU) CS201GAM
# ... to be continued (it's still working)
# ... nope. It's 4x slower than the prior. I'll not bother.
my $len = shift @_;
my $pat = "\\A[^\n]*?" . ( "(?:(\\w)[^\n]*?)" x $len ) . "\n"
. "(??{ qq<(?:" . join('', map { "[^\n>.\$$_.qq<]*>.\$$_.qq<" } 1 .. $len) . "[^\n]*\n)+>})\\z";
use re 'eval';
return qr/$pat/;
}⠤⠤ ⠙⠊⠕⠞⠁⠇⠑⠧⠊
You're probably right about people in general not having a clue as to the right approach without reading the spoilers. I am an avid puzzle and riddle aficionado. One kind of puzzle I see is identifying someone's ATM PIN using a constrained version of this. I incorrectly assumed people who enjoyed my challenges to have the same kind of exposure and recognize it as being similar :-(
The more interesting problem to me is the general case which I am hoping someone provides a better solution then my own.
Thanks for your regex solution. I am not sure I understand it but it gives me something new to work at learning.
Cheers - L~R
It's just making a regex like \A[^\n]*(\w)[^\n]*\n(?:[^\n]*\1[^\n]*\n)+\z which just says, I captured $1 and it has to exist on every line. Higher # versions just capture more and assert the new digits, in order. It's really very simple. rx() could be improved if you pegged certain captures with specified characters. I'm searching the entire space so I'm slower.
What's this have to do with ATM PINs?
⠤⠤ ⠙⠊⠕⠞⠁⠇⠑⠧⠊
The riddle setup is along the lines that when the website asking for your PIN does so, it will ask for it by creating a larger PIN and place the true values in positions W, X, Y, and Z (which change each time). You are then free to fill all the remaining positions with random numbers. The riddle itself is to determine the PIN after capturing a certain number of succesful logins. Forget I said ATM as this was web banking.
Cheers - L~R
Personally, I enjoyed the challenge of trying to figure out what the message was as well as coming up with a general solution (which has now been fixed). I worked out that C,S,0,1,M,E were statistically significant, but I couldn't make heads or tails of what that could possibly mean so I did eventually have to look at the spoilers to work it out.
I just wish I had more time to spend on things like this instead of doing actual work :)