1313: "Regex Golf"

This forum is for the individual discussion thread that goes with each new comic.

Moderators: Moderators General, Prelates, Magistrates

sudo make me a username
Posts: 20
Joined: Thu Jan 02, 2014 2:03 pm UTC

Re: 1313: "Regex Golf"

Postby sudo make me a username » Tue Jan 07, 2014 11:46 am UTC

orthogon wrote:
Flumble wrote:
MichaelKarnerfors wrote:For those that want to play some Regex Golf...

http://regex.alf.nu/

Wow, it's actually a thing?

I was surprised too; I assumed that Randall had invented it as part of the joke.

I've got as far as "5. Abba", but my current regex is 100% wrong: it matches everything in the right list and nothing in the left, which sounds like it should be easy to fix, but... It does however contain a nice pair of ASCII breasts.


lol, it's basically half the solution. Inverting a regex is not immediately obvious but it's possible and not very hard. Search for "negative lookaheads". A similar solution is used for 7.Prime. BTW 7 is now my favourite regex problem, it has a general solution solution that is pretty short.

Kit.
Posts: 1117
Joined: Thu Jun 16, 2011 5:14 pm UTC

Re: 1313: "Regex Golf"

Postby Kit. » Tue Jan 07, 2014 12:53 pm UTC

Pfhorrest wrote:it was revealed that the producers of the movie are stupid and irrationally hate colons and grammar and that the title of the film is simply "Star Trek Into Darkness" as a unified whole; as in, "Trek" is apparently a verb, "Star" is something like an adverb describing the manner of Trek to be embarked upon,

Isn't "Star" a better choice for the verb here?

Draco18s
Posts: 87
Joined: Fri Oct 03, 2008 7:50 am UTC

Re: 1313: "Regex Golf"

Postby Draco18s » Tue Jan 07, 2014 1:39 pm UTC

sudo make me a username wrote:lol, it's basically half the solution. Inverting a regex is not immediately obvious but it's possible and not very hard. Search for "negative lookaheads". A similar solution is used for 7.Prime. BTW 7 is now my favourite regex problem, it has a general solution solution that is pretty short.


Actually negative lookaheads won't help you.

"cdcdabba" will match on a "not-ABBA-like" because "cdcd" as a string matches that "not-ABBA-like" requirement.

ABBA got me too, I ended up using a half-cheaty solution that matched things using other properties in the words.

Actual solution. Does have a negative lookahead, but not with a backref (which would seem to be the solution)
Spoiler:
^(.(?!(ll|ss|mm|rr|tt|ff|cc|bb)))*$|^n|ef

User avatar
Klear
Posts: 1965
Joined: Sun Jun 13, 2010 8:43 am UTC
Location: Prague

Re: 1313: "Regex Golf"

Postby Klear » Tue Jan 07, 2014 1:52 pm UTC

Pfhorrest wrote:Technically, "Into Darkness" isn't a subtitle. I really hate to be arguing that point because I really wish it wasn't so, but in the Great How-To-Title-The-Wikipedia-Article-For-That-Movie-War of 2013, it was revealed that the producers of the movie are stupid and irrationally hate colons and grammar and that the title of the film is simply "Star Trek Into Darkness" as a unified whole; as in, "Trek" is apparently a verb, "Star" is something like an adverb describing the manner of Trek to be embarked upon, "Into Darkness" is a prepositional phrase indicating where to Trek, and the whole title is an imperative exhorting one to Trek, that is to embark upon a Trek, specifically a Trek of the Star variety, Into the Darkness. Trek, I beseech you! Trek Starly! Go forth, and Star Trek, outward, beyond the light! Star Trek Into Darkness, I command thee!

sigh


Uh... if that were the case, it would be written with lowercase i, no? =)

User avatar
faubiguy
Posts: 15
Joined: Sun Aug 11, 2013 9:20 am UTC

Re: 1313: "Regex Golf"

Postby faubiguy » Tue Jan 07, 2014 2:27 pm UTC

This is the solution I got for abba with backrefrences (for the general case)
Spoiler:

Code: Select all

^((?!(.)(.)\3\2).)*$

I would use a non-capturing group for the first one, but it's 2 extra characters.

protandeous
Posts: 2
Joined: Mon Jan 06, 2014 9:05 pm UTC

Re: 1313: "Regex Golf"

Postby protandeous » Tue Jan 07, 2014 2:38 pm UTC

You are right -- it was a side-effect of using regexpal to test the phrase, a closer working expression is
/|M | [TN]|B|/
because neither the M nor the B were doing anything without the extra pipes

and it works as well on:

Generations
First Contact
Insurrection
Nemesis
Into Darkness

Go Randall!

User avatar
Flumble
Yes Man
Posts: 2248
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: 1313: "Regex Golf"

Postby Flumble » Tue Jan 07, 2014 2:47 pm UTC

faubiguy wrote:This is the solution I got for abba with backrefrences (for the general case)
Spoiler:

Code: Select all

^((?!(.)(.)\3\2).)*$

I would use a non-capturing group for the first one, but it's 2 extra characters.

Hah, what a wonderful solution. I'd never thought of looping through the string that way. :o

I got to only 168 points using simple pattern matching, bringing me to a total of 3752. (I'm not that good with regexes, especially counting with them)

sudo make me a username
Posts: 20
Joined: Thu Jan 02, 2014 2:03 pm UTC

Re: 1313: "Regex Golf"

Postby sudo make me a username » Tue Jan 07, 2014 2:58 pm UTC

faubiguy wrote:This is the solution I got for abba with backrefrences (for the general case)
Spoiler:

Code: Select all

^((?!(.)(.)\3\2).)*$

I would use a non-capturing group for the first one, but it's 2 extra characters.

This is better by 3 points:
Spoiler:
^(?!.*(.)(.)\2\1)

This actually gives a general solution for taking a regex and reversing it, as long as the original regex have no caret or dollar (and you don't care about the match result, as this matches an empty string)):
Spoiler:
^(?!.*original)

Variations in case the original contains a caret or dollar:
Spoiler:
original means original with caret/dollar removed
With caret: ^(?!original)
With dollar: ^(?!.*original$)
With both: ^(?!original$)
I have used the last one for "prime"

User avatar
mathmannix
Posts: 1445
Joined: Fri Jul 06, 2012 2:12 pm UTC
Location: Washington, DC

Re: 1313: "Regex Golf"

Postby mathmannix » Tue Jan 07, 2014 3:14 pm UTC

Klear wrote:
Uh... if that were the case, it would be written with lowercase i, no? =)


Capitalization rules vary, but according to some sources, including the AP Stylebook, all words of four or more letters are to be capitalized in a title, no matter what part of speech they may be. (And this happens to be what I remember being taught in school, FWIW.)
I hear velociraptor tastes like chicken.

User avatar
Carlington
Posts: 1588
Joined: Sun Mar 22, 2009 8:46 am UTC
Location: Sydney, Australia.

Re: 1313: "Regex Golf"

Postby Carlington » Tue Jan 07, 2014 3:41 pm UTC

This is my first time using regexes for anything at all, ever. I'm stopping now, because 2am is not a good time to learn about a new game, but I have a total of 816 [1. 207; 2. 208; 3. 202; 4. 199] on the first four levels and I don't see a way to improve on that. I'll sleep for now, and have a crack at some more in the morning, this is fun.
Kewangji: Posdy zwei tosdy osdy oady. Bork bork bork, hoppity syphilis bork.

Eebster the Great: What specifically is moving faster than light in these examples?
doogly: Hands waving furiously.

Please use he/him/his pronouns when referring to me.

User avatar
Pfhorrest
Posts: 5437
Joined: Fri Oct 30, 2009 6:11 am UTC
Contact:

Re: 1313: "Regex Golf"

Postby Pfhorrest » Tue Jan 07, 2014 6:30 pm UTC

Kit. wrote:
Pfhorrest wrote:it was revealed that the producers of the movie are stupid and irrationally hate colons and grammar and that the title of the film is simply "Star Trek Into Darkness" as a unified whole; as in, "Trek" is apparently a verb, "Star" is something like an adverb describing the manner of Trek to be embarked upon,

Isn't "Star" a better choice for the verb here?

That would require "Trek" to be a proper noun then (or possibly a plural somehow), as there's no article (it's not "Star a Trek" or "Star the Trek"), and the semantics that must be assumed to make sense of that syntax would be even weirder: how exactly does one star something into darkness? The only verb sense of "star" I know of other than a sense that would require a preposition like "in" to make grammatical sense (e.g. Zachary Quinto stars in Trek) is to mark or adorn with stars, so to star something in that sense "into darkness" would be to cover it with stars in such a way as to darken it somehow (either in the sense of preventing light from reaching it, or preventing light from it from reaching others), and that's just getting weirder and weirder. "Adorn Trek with stars until it is [in the] dark"? Makes much less sense than "Trek through the stars (that is, star-trek) into the darkness", as little sense as it makes for a movie title to be an imperative at all.
Forrest Cameranesi, Geek of All Trades
"I am Sam. Sam I am. I do not like trolls, flames, or spam."
The Codex Quaerendae (my philosophy) - The Chronicles of Quelouva (my fiction)

User avatar
ThirdParty
Posts: 347
Joined: Wed Sep 19, 2012 3:53 pm UTC
Location: USA

Re: 1313: "Regex Golf"

Postby ThirdParty » Tue Jan 07, 2014 7:40 pm UTC

MichaelKarnerfors wrote:For those that want to play some Regex Golf...

http://regex.alf.nu/
Awesome! Here are my scores from my first playthru:
  1. 207
  2. 208
  3. 202
  4. 201 (attn: Carlington)
  5. 194 (attn: sudo make me a username)
  6. 176
  7. 286
  8. 199
  9. 199 (using the obvious cheat)
  10. 586 (totally cheating)
  11. 352 (slightly cheating)
  12. 270 (totally cheating)
  13. 60 (non-general solution)
  14. 246 (slightly cheating)
  15. 243 (slightly cheating)
  16. 257 (non-general solution)
total: 3886

Kit.
Posts: 1117
Joined: Thu Jun 16, 2011 5:14 pm UTC

Re: 1313: "Regex Golf"

Postby Kit. » Tue Jan 07, 2014 7:48 pm UTC

Pfhorrest wrote:"Adorn Trek with stars until it is [in the] dark"?

That could work too. Like in: "Give Trek Bicycle Corporation zero-star rating".

Pfhorrest wrote:Makes much less sense than "Trek through the stars (that is, star-trek) into the darkness",

I don't see how missing hyphen is so better than missing colon.

speising
Posts: 2353
Joined: Mon Sep 03, 2012 4:54 pm UTC
Location: wien

Re: 1313: "Regex Golf"

Postby speising » Tue Jan 07, 2014 7:54 pm UTC

what is considered cheating in regex golf?

Kit.
Posts: 1117
Joined: Thu Jun 16, 2011 5:14 pm UTC

Re: 1313: "Regex Golf"

Postby Kit. » Tue Jan 07, 2014 7:59 pm UTC

speising wrote:what is considered cheating in regex golf?

Trying to match the particular cases (sometimes even not matching all of them, but gaining more points due to a shorter regex), and not the general pattern.

Like in the comic.

sudo make me a username
Posts: 20
Joined: Thu Jan 02, 2014 2:03 pm UTC

Re: 1313: "Regex Golf"

Postby sudo make me a username » Tue Jan 07, 2014 8:25 pm UTC

Kit. wrote:
speising wrote:what is considered cheating in regex golf?

Trying to match the particular cases (sometimes even not matching all of them, but gaining more points due to a shorter regex), and not the general pattern.

Like in the comic.


The thing is, in the comic there is no "general case", Megan/Randall just tried to play golf with semi-random lists. In the http://regex.alf.nu/ the list are actually categories that could be extended. So it looks like the "real" riddle is to find a solution for lists of any length, but sometimes just treating the lists as random lists (ignoring the categorization) produces a shorter regex = more score. This feels like cheating.

User avatar
orthogon
Posts: 3075
Joined: Thu May 17, 2012 7:52 am UTC
Location: The Airy 1830 ellipsoid

Re: 1313: "Regex Golf"

Postby orthogon » Tue Jan 07, 2014 10:29 pm UTC

Unless the two studios really are constrained by a bilateral agreement to use titles that match or not some agreed regex. Perhaps that's the real reason for the missing colon...
xtifr wrote:... and orthogon merely sounds undecided.

User avatar
mathmannix
Posts: 1445
Joined: Fri Jul 06, 2012 2:12 pm UTC
Location: Washington, DC

Re: 1313: "Regex Golf"

Postby mathmannix » Thu Jan 09, 2014 2:10 pm UTC

Great, now I have 100 problems.
I hear velociraptor tastes like chicken.


bootmii
Posts: 6
Joined: Fri Mar 11, 2011 11:50 pm UTC

Re: 1313: "Regex Golf"

Postby bootmii » Fri Jan 31, 2014 2:25 am UTC

I found the notebook. But is there code I can download?

Deadcode
Posts: 102
Joined: Mon Mar 08, 2010 6:59 am UTC

Re: 1313: "Regex Golf"

Postby Deadcode » Sat Feb 22, 2014 3:31 pm UTC

MichaelKarnerfors wrote:For those that want to play some Regex Golf...

http://regex.alf.nu/

So I recently became addicted to regex golf, and scored a total of 3912 on Erling's problem set before allowing myself to look at other people's solutions.

Then I made friends with teukon, who created his own problem set on github. (My own nickname on github is Davidebyzero.) I had a lot of fun solving his problems, and also turning golf into tennis, where we'd bounce our solutions back and forth, improving them each time. (If you go to the relevant github pages, be warned: there are lots of spoilers there. You can safely go to teukon's Regex Golf - Unofficial Bonus Levels page, but beware of spoilers on other pages.)

I'd like to start a dedicated Regex Golf thread here on xkcd forums, where people can post their spoiler-tagged solutions and custom problems, but I'm not sure where to put it. Can anyone help me, please? I don't know whether to put it in Logic Puzzles, Computer Science, Coding, or heck, even Mathematics (as many of the ones I've found the most interesting are very mathematical). Where should it go?

User avatar
Darekun
Posts: 38
Joined: Thu Jan 03, 2013 7:57 am UTC

Re: 1313: "Regex Golf"

Postby Darekun » Sat Feb 22, 2014 11:32 pm UTC

Deadcode wrote:I'd like to start a dedicated Regex Golf thread here on xkcd forums, where people can post their spoiler-tagged solutions and custom problems, but I'm not sure where to put it. Can anyone help me, please? I don't know whether to put it in Logic Puzzles, Computer Science, Coding, or heck, even Mathematics (as many of the ones I've found the most interesting are very mathematical). Where should it go?

Perhaps Forum Games?

Deadcode
Posts: 102
Joined: Mon Mar 08, 2010 6:59 am UTC

Re: 1313: "Regex Golf"

Postby Deadcode » Sun Feb 23, 2014 1:52 am UTC

Darekun wrote:Perhaps Forum Games?


Well, although some of the regex golf problems might belong there, this includes things like writing a regular expression that matches only sequences of "x" characters whose length is a prime power. Does that sort of thing really belong in Forum Games?

abeljohnson668
Posts: 1
Joined: Fri May 30, 2014 9:04 am UTC

Re: 1313: "Regex Golf"

Postby abeljohnson668 » Fri May 30, 2014 9:08 am UTC

Nice One! I like it too much. Regax golf may be tough for some people but for those whose can solve easily it is good game.

User avatar
firesoul31
Posts: 93
Joined: Wed Feb 27, 2013 10:30 pm UTC

Re: 1313: "Regex Golf"

Postby firesoul31 » Fri May 30, 2014 1:55 pm UTC

Deadcode wrote:
Darekun wrote:Perhaps Forum Games?


Well, although some of the regex golf problems might belong there, this includes things like writing a regular expression that matches only sequences of "x" characters whose length is a prime power. Does that sort of thing really belong in Forum Games?


Probably, yeah. Logic puzzles would work too, probably.
Pronouns: she/her/hers or they/them please.


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: ronaldkr and 92 guests