Skip to content

Instantly share code, notes, and snippets.

@teukon teukon/gist:16b6de379907bb2a3aa4 Secret
Last active Dec 3, 2018

Embed
What would you like to do?
Regex Golf - Unofficial Bonus Levels

Regex Golf - Unofficial Bonus Levels

  1. Subtraction Quantify with care.
  2. Typist With apologies to Dr. Dvorak.
  3. Addition Beauty in symmetry.
  4. Anyway Old MacDonald had a farm...
  5. Tic-tac-toe Don't forget the horizontals.
  6. Modulus Lookahead smithwork.
  7. Matryoshka Pay attention to detail.
  8. Euclid Greed is good.
  9. Latin squares No mathematics; just logic and reasoning.
  10. Dominoes Caution! Rabbit holes.

Each problem has a robust solution (can be done "without cheating"), unlike "A man, a plan", "Glob", and "Balance" from the original set. In each case, the pattern should be unambiguous. A solution to a problem is considered robust if it conforms to this pattern for any string matching the problem's domain regex:

Level Domain regex
Subtraction ^x+ - x+ = x+$
Typist ^[a-z]+$
Addition ^x+ \+ x+ = x+ \+ x+$
Anyway ^[a-z]+$
Tic-tac-toe ^[\.OX]{3} [\.OX]{3} [\.OX]{3}$
Modulus ^x+ % x+ = x+$
Matryoshka ^([a-z]+ )*[a-z]+$
Euclid ^gcd\(x+, x+\) = x+$
Latin squares ^[a-z]{4} [a-z]{4} [a-z]{4} [a-z]{4}$
Dominoes ^([0-6]{2} )*[0-6]{2}$

Please refrain from posting solutions here until the thread is well underway (20+ posts). Questions, total scores, and gentle hints are ok.


A warm thank you to Davidebyzero for helping me refine each of these problems, and for coming up with some brilliant solutions. Our testing and development notes can be found here and here (caution: spoilers).

@Davidebyzero

This comment has been minimized.

Copy link

commented Feb 22, 2014

I've made a meta-post on xkcd forums, asking what subforum my actual post should go in.

Note to people coming over to play this problem set: Please avoid posting your solutions here (maybe even avoid posting your scores) and instead, post them somewhere else with a link to them here, or post the md5sums of the solutions here. At least until the thread here has become long enough that even people with really large monitors won't be able to see the spoilers without scrolling down.

@teukon

This comment has been minimized.

Copy link
Owner Author

commented Feb 22, 2014

I've made a meta-post on xkcd forums, asking what subforum my actual post should go in.

Great!

Also, it'd be awesome if you could avoid posting your solutions here (maybe even avoid posting your scores) and instead, post them somewhere else with a link to them here, or post the md5sums of the solutions here.

Yes. I will delete very early comments that give solutions. If you are one of the first here, please post your total score or the md5sums of your solutions, and refrain from posting the solutions themselves until this thread is well underway. Holding back on posting individual scores would be greatly appreciated.

I hope to see 20 comments of cloak-and-dagger chat before solution lists break out.

@tabatkins

This comment has been minimized.

Copy link

commented Feb 25, 2014

I've been messing around with Matroyshka, and I can't come up with a definition of it that doesn't include several of the items on the "bad" list. All I can gather from the "good" list is that each successive word includes all the letters of the previous word, plus at least one more. But the "on", "sad", and "tea" bad lines also match that criteria, so I'm obviously wrong.

@teukon

This comment has been minimized.

Copy link
Owner Author

commented Feb 25, 2014

Welcome! :)

Yes, the difficulty in this one is more to do with pinning down the precise pattern than in building the regex or in compressing it. Focus on the "on" and "sad" lines in particular.

Good luck!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.