in reply to Challenge: Hidden Message

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) CS201GA
+M
    # 402 wallclock secs (393.05 usr +  0.05 sys = 393.10 CPU) CS201GA
+ME
    # 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) CS201GA
+M
    # ... 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/;    
}

[download]

⠤⠤ ⠙⠊⠕⠞⠁⠇⠑⠧⠊

Replies are listed 'Best First'.
Re^2: Challenge: Hidden Message
by Limbic~Region (Chancellor) on May 11, 2006 at 20:31 UTC
    diotalevi,
    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

[reply]

      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?

      ⠤⠤ ⠙⠊⠕⠞⠁⠇⠑⠧⠊

[reply]
[d/l]
        diotalevi,
        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

[reply]
      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 :-(

      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 :)

[reply]

In Section Meditations