81
10
Warm up: Regex, Paper, Scissors
This is the challenge I originally wanted to post, before realising that some very short solution exist. Nevertheless, it can be an interesting problem to think about in preparation for the actual challenge below.
Write three regexes R, P and S such that they match each other in a cyclic Rock, Paper, Scissors fashion. In particular, R matches S, S matches P and P matches R, but R doesn't match P, S doesn't match R and P doesn't match S. Here's a handy table:
Regex Matches Doesn't match
R S P
P R S
S P R
It doesn't matter what R, P and S do on any other inputs, including themselves.
Here, match just means that some (possibly empty) substring of the input is matched. The match does not need to cover the entire input.
The challenge: Regex, Paper, Scissors, Lizard, Spock
For this challenge, you'll solve a tougher version of the above problem, based on the RPS variant Rock, Paper, Scissors, Lizard, Spock (as popularised by The Big Bang Theory). In RPSLV, there are five different symbols, that beat each other in two cycles:
- Rock → Scissors → Lizard → Paper → Spock → Rock
- Rock → Lizard → Spock → Scissors → Paper → Rock
You should write five regexes R, P, S, L and V which mimic this structure when given to each other as input. Here is the corresponding table:
Regex Matches Doesn't match
R L, S V, P
L V, P S, R
V S, R P, L
S P, L R, V
P R, V L, S
Just to be clear, you should not match the string R
, P
, etc, but the other regexes. E.g. if your regex R is ^\w$
for example, then P and V have to match the string ^\w$
, whereas S and L shouldn't.
Again, match just means that at least one (possibly empty) substring of the input is matched. The match does not need to cover the entire input. For example \b
(word boundary) matches hello
(at the beginning and at the end), but it doesn't match (^,^)
.
You may use any regex flavour, but please state the choice in your answer and, if possible, provide a link to an online tester for the chosen flavour. You may not use any regex features that let you invoke code in the flavour's host language (like the Perl flavour's e
modifier).
Delimiters (like /regex/
) are not included in the regex when given as input to another, and you cannot use modifiers that are outside of the regex. Some flavours still let you use modifiers with inline syntax like (?s)
.
Your score is the sum of the lengths of the five regexes in bytes. Lower is better.
It turns out to be a lot simpler to find a working solution to this problem than it may seem at first, but I hope that finding an optimal solution is quite tricky.
Does, say, R have to match the entire regex of S or a substring of S, provided it does not match any substrings of P or V? – Okx – 2017-07-05T13:00:38.583
@Okx "match just means that at least one (possibly empty) substring of the input is matched. The match does not need to cover the entire input. For example
\b
(word boundary) matcheshello
(at the beginning and at the end), but it doesn't match(^,^)
." – Martin Ender – 2017-07-05T13:01:05.3901Presumably it doesn't matter if a regex matches itself? – Brilliand – 2017-07-05T18:57:40.460
@Brilliand Correct. – Martin Ender – 2017-07-05T19:07:08.520
For making this more general, could one just write a set of programs which accept (or reject) each other? – Paŭlo Ebermann – 2017-07-06T19:39:34.380
@MartinEnder I didn't want to generalize the graph, but to generalize from regular expressions to any kind of programs which implement a string → boolean function, in order to allow more "programming languages". – Paŭlo Ebermann – 2017-07-06T21:32:41.227
1
Great puzzle. I've created an interactive version here, if anyone is interested: https://shark.fish/rock-paper-scissors/
– shark.dp – 2017-07-30T11:22:47.347@shark.dp Wow that's really cool, nice work! – Martin Ender – 2017-07-30T12:40:03.483