search

phikal / ReGeX

A Regular Expression game for Android
https://f-droid.org/en/packages/com.phikal.regex/
GNU General Public License v3.0
101 stars 10 forks source link

Random language generation needed #34

Closed hackerb9 closed 5 years ago

hackerb9 commented 7 years ago

I am excited for this game as I love solving regular expressions. In the real world, regexes allow you to match not just some finite set of words, but all possible words of a certain type. The puzzle and the fun is in recognizing the pattern that groups the words together so you can craft the perfect regex.

This game has promise, but its random problem generator only creates strings of characters with no rhyme or reason. I just played 66 rounds and got to level 10 and every single solution was "[abc].*" or a minor variant of it. It was boring because the type of problem never changed.

I think it would be much more fun if the set of words was created by randomly created regexes, finite state automata or hidden Markov models.

For example, if the game randomly creates "a+", the first level might look like:

Match: a aaaaaa aaaa Not: b abba baa

As levels progress, instead of the words getting longer, the generating pattern will get more complex, randomly adding regex features like matching groups and alternation.

For example, perhaps the next level would increase the grammar (which letters are allowed) and the problem generated might be "[ab]",

Match: a b Not: c

And then,

Match: aa abab bbbb Not: a bab abba

If you make a list of regex features ordered by difficulty, you can add new ones in the mix after each level. That way the game would constantly feel like a significantly different challenge as new types of patterns appear.

Thanks for making what promises to be a great game.

phikal commented 7 years ago

Definitely sounds interesting, certainly worth building into the game - I'll set it up as a milestone.

But I'd have to revise some language theory, before trying to implement this, since I've never spent too much time with these things. But it will probably take a while, since I'm preoccupied with other stuff for the moment. If anyone reading this would be ready to implement it themselves, I'd gladly assist them.

phikal commented 5 years ago

This should be solved with 9e3317b61870fd6b06b10288ab7f675a0e2966fa. RegularExpression should be able to offer a functioning framework for random-but-challenging games, hopefully solving the issue you brought up.

Now it will just need some more tweaks and improvements, that should come along with testing.

hackerb9 commented 5 years ago

Fabulous! I look forward to play testing this as soon as F-droid updates the apk.

phikal commented 5 years ago

Well, there are still a few other pending issues and general restructuring needed before I can tag a new version, so it might still take a while...