Regular Expresso 2

[choroba]

As you might have noticed, I like programming puzzles and brain teasers. But I hadn't participated in a real public contest... until today. I registered to Regular Expresso 2 on HackerRank. The participants had 24 hours to solve 8 tasks, Perl was among the supported languages. The contest was regular expression-centered, your code had to always end the same:

$Test_String = <STDIN> ;
if($Test_String =~ /$Regex_Pattern/){
    print "true";
} else {
    print "false";
}

The top 10 contestants (most points + shortest time) won a T-shirt. Once I realised there were more then 10 people with the full score, I knew I wasn't getting one, but I still wanted to get the full score.

But I had no idea how to solve one of the tasks: the input was a long string of zeroes and ones. Your regex had to recognise whether the string encoded two binary numbers in the following way: when you reversed the string and extracted the odd digits, you got a number three times greater than the one built from the remaining digits. For example,

1110110001 => 00111, 10101
                  7     21
              3 * 7  =  21, accept!

I wrote a short script to generate some examples, but I wasn't able to find the pattern. Moreover, the regex couldn't have more than 40 characters!

Then I remembered Perl has a way to run code in a regex: the (?{...}) pattern. I read the relevant perlre section several times and tried something like the following:

use bigint;

sub check {
    my ($bin, $three) = ('0b') x 2;
    my $s = $_;
    while ($s) {
        $three .= chop $s;
        $bin   .= chop $s;
    }
    return oct $three == 3 * oct $bin
}

$Regex_Pattern = qr/(?{ check() })/;

The problem here is that (?{...}) always matches. Fortunately, you can use the code pattern as the condition in

(?(condition)yes-pattern|no-pattern)

As the yes-pattern, I used ^ which always matches, and (*FAIL) for the no-pattern:

$Regex_Pattern = qr/^(?(?{ check() }) ^ | (*FAIL) )/x;

The qr adds some characters, so to be sure I don't overflow, I renamed the subroutine to c and golfed the solution to

'^(?(?{c()})^|(*F))'

I got the full score! Would you call such a solution cheating? On one hand, I see that's not what the organisers wanted me to do, on the other hand, that's what Perl regular expressions give you. In fact, with the "start or fail" pattern, I can solve almost any problem with a regular expression!

[oiskuu]

Multiplying by three is the same as shift + add. Essentially you have a binary adder with carry, or rather two carries: the input bit is also a carry. So you have an FSM with three states for the three possible carry values 0, 1, 2.

    00111
 +   00111
  --------
     10101

Let's start with a recursive regex with groups for each of the states.

    qr/ (?(DEFINE)
          ( 00 (?1) | 11 (?2) | )               # group 1:  carry = 0
          ( 01 (?1) | 10 (?3) )                 # group 2:  carry = 1
          ( 00 (?2) | 11 (?3) )                 # group 3:  carry = 2
        )

        \A(?1)\Z /x;

From here, we can inline the group 2 in g1 and g3:

    qr/ (?(DEFINE)
          ( 00 (?1) | 11 01 (?1) | 11 10 (?3) | )
          ( )
          ( 00 01 (?1) | 00 10 (?3) | 11 (?3) )
        )

        \A(?1)\Z /x;

Now it should be obvious that the group 3 i.e. carry=2 state is entered with a 11 10 and left with 00 01. Rewriting the regex with repeats instead of recursion:

my $Regex_Pattern =

    qr/ \A ( 00 | 11 01 | 11 10 ( 00 10 | 11 )* 00 01 )* \Z /x;

ps. I'm assuming that the input string must have 2*n digits.

[morgon]

Would you call such a solution cheating?

In a competition where people use other languages I actually would call it sort of cheating.

A perl regex is much more expressive (especially because of the features that you have used) than your CS-course regular expression and so you have a lot more fire-power than someone that is restricted to less powerful implementations.

[Your Mother]

actually would call it sort of cheating.

Nonsense. How else will anyone know that Perl is considerably better than other languages at some things? Playing down to their level would be self-handicapping and would be a silly exercise in false humility. Hubris is what Perl demands. Display it, lazily!