# Hitcon Quals 2016 - RegExpert### Misc - 200 pts
    Do you remember "hard to say" last year?    I think this one is harder to say... "Simple" challenge in appearance, we need to give a regex to match a fixed pattern. We have 5 regex to find.The three main things to take care of are :- Ruby language is used. Therefore Regex are sometimes different in their syntax compared to what I was used to- We don't have access to options, so no "insensitive" option possible- Asked Regex are not usual
### 1st Regex :```================= [SQL] =================Please match string that contains "select" as a case insensitive subsequence.```
Here we need to find every subsequence. Meaning SXeLEcT should match.
First try :`[sS].*[eE].*[lL].*[eE].*[cC].*[tT]` should be ok. And yes it works until the last test :`Almost there...But the length limit is 21`...So here the workaround is a `(?i)` for the insensitive case.
And the solution is `(?i)s.*e.*l.*e.*c.*t`
### 2nd Regex :```=============== [a^nb^n] ================Yes, we know it is a classical example of context free grammer.````The "Contenxt free grammer" helps us in our research. Here the goal is to create a pattern aXb where X is the same pattern in recursion and optionnal. This is possible in Ruby with the syntax `\g<1>?` which creates recursion on the 1 capturing group.So we try the regex `^(a\g<1>?b)$` and it works !
2nd Solution : `^(a\g<1>?b)$`
### 3rd Regex :
```================= [x^p] =================A prime is a natural number greater than 1 that has no positive divisors other than 1 and itself.```Here I don't have much to say.To force all elements to be `x` and avoid empty regex we put `^xx+$` at the end.`(xx+)\1+` matches non-prime length strings. So we invert it and get the 3rd solution
3rd Solution : `(?!(xx+)\1+$)^xx+$`
### 4th Regex :
```============= [Palindrome] ==============Both "QQ" and "TAT" are palindromes, but "PPAP" is not.```
Here we need to first match a single character, or create a recursive pattern matching the pattern `aXa` where `a` is a random character and `X` the recursion being on the whole pattern. (Because we need the recursion to have a stopping condition which here will be the single character)
So first we match a single character with this `^(\w)$`Then we add to **OR** pattern with the recursion and it works !
4th Solution : `^(\w?|(\w)\g<1>\k<2>)$`
### 5th Regex :
```============== [a^nb^nc^n] ==============Is CFG too easy for you? How about some context SENSITIVE grammer?```
Here `context SENSITIVE grammer` helps us to find informations on Google.
We first found this Regex : `/\A(?<AB>a\g<AB>b|){0}(?=\g<AB>c)a*(?<BC>b\g<BC>c|){1}\Z/` which we reduced to `^(a\g<1>b|)(?=\g<1>c)a*(b\g<2>c|)$`
This regex works but the length limit is 29. After testings, we didn't find a way to reduce this regex. So we searched for another method. We found the regex `^(?=(a(?-1)?b)c)a+(b(?-1)?c)$` and after a little adaptation to Ruby Language we have the solution
5th Solution : `^(?=(a\g<1>?b)c)a+(b\g<2>?c)$`
**Here we are !**With all this, we get the well deserved flag : `hitcon{The pumping lemma is a lie, just like the cake}`