Fortnightly challenge of 2015-02-20: Language Design

I also think this is one of those cases where a popcon might actually be better than a code challenge/golf. if we used a non-popcon criterion, it would probably have to be "match these 10 patterns, lowest overall score wins". however, that'll be really prone to hardcoding and people focusing on being able to solve those 10 problems instead of a general purpose language

PhiNotPi

It's a field that is probably underdeveloped as of now.

feersum

1:12 PM

plus, the annoying need to use all 256 bytes

Martin Büttner

@feersum grid-based games, maybe

so as a popcon, I think we should still provide a decent number of problems to be solved. answers should include a design description and a working interpreter, as well as the pattern for the given test cases. and we could provide a number of voting guidelines (conciseness, generality, readability...)

PhiNotPi

We want to prevent the so-called "HQ9+BF" responses, where a few special functions are hard-coded, but the rest is very verbose and not practically useful.

Martin Büttner

exactly

Zgarb

There actually exist 2D regular expressions in CS research.

But they are kind of a small niche.

Martin Büttner

@Zgarb if you could dig up some references, that would be amazing

@PhiNotPi yeah, that's why I think a popcon might be a better option, since we can only provide so many examples

feersum

1:14 PM

probably we will design highly irregular ones

PhiNotPi

As test cases/examples, we could search through PPCG history and find problems where 2D pattern matching would be useful.

Martin Büttner

yeah

what do people think about the general matching process... should the patterns match subregions (and contain a concept of anchors like regex) or should they always match an entire input?

I think I'd prefer the former

Zgarb

Here's the Master's thesis of my colleague on the subject. The second-to-last page has an index.

2

Martin Büttner

it would be interesting to match non-regular subregions

feersum

I think it fails if you doen't http

Zgarb

1:20 PM

@feersum Thanks.

That's very theoretical though, I don't know if it'll be of much help.

Martin Büttner

well, it's definitely interesting

we'd also need to decide if the input is always rectangular

Zgarb

Here's another reference, which may be easier to read.

feersum

we should require a working implementation, right?

Martin Büttner

yes

PhiNotPi

http://codegolf.stackexchange.com/questions/3117/facial-recognition
http://codegolf.stackexchange.com/questions/45488/nether-portal-detection
http://codegolf.stackexchange.com/questions/45720/minecraft-chest-placement
http://codegolf.stackexchange.com/questions/31743/is-this-word-on-the-boggle-board (maybe)
http://codegolf.stackexchange.com/questions/42333/verify-a-minesweeper-board
http://codegolf.stackexchange.com/questions/44485/score-a-game-of-kingdom-builder
^ some possible examples

Zgarb

1:31 PM

I vote that the input may not be rectangular, but it is padded into a rectangle using a new special symbol, which can be matched by escaping (like \# or something).

PhiNotPi

It's like a 2D array of characters, where some characters are the empty string.

Maybe we should leave part of how non-rectangular inputs are handled up to the entrants.

Zgarb

That's also a good option.

Martin Büttner

@Zgarb hm, this raises new questions about connectedness and holes though

any non-rectangular input can always be encoded in a rectangle by padding with an arbitrary unused character

if submissions can still solve those, that's nice, but I think I wouldn't necessarily require it

(as PhiNotPi said)

@PhiNotPi I'd definitely like to include CH's minecraft challenges

some simpler examples could be recognising a checkerboard pattern, or checking if there are exactly N occurrences of some character in the grid

feersum

N occurences of a characters is not much of a 2d problem

Martin Büttner

I'd also leave it up to participants if they return whether a match was found, where it was found, or even the actual match (as a padded subregion of the input)

@feersum doesn't mean, a 2D language shouldn't be capable of handling it though

oh, here is an idea: find isolated gliders in a game of life board

the examples should definitely cover rotation and reflection, and for reflection maybe even cases, where you need to swap out symmetric characters (like parentheses, braces, brackets)

PhiNotPi

1:44 PM

Like "detect a word in any orientation in a word-search puzzle"

Martin Büttner

oh, that's good

PhiNotPi

All-day region band rehearsal is about to begin

Bye! I'll be back in a few hours for lunch break.

Martin Büttner

hf!

Nathan Merrill

2:26 PM

The game of life makes me think

what if the language is self modifying?

in a specific manner

Martin Büttner

ummm... I don't know what you mean by that... it should still be a patter-matching language, right?

I've gotta head off for now, though

Nathan Merrill

not necessarily

just throwing out an idea

Martin Büttner

Oh right, that was meant as an alternative suggestion

I think self-modifying 2D languages are really interesting, but a) it sounds more like a solution than a problem and b) it might lead to people just copying Befunge or ><>

PhiNotPi

6:35 PM

I guess not much has happened since I left.

I'm about to watch the US Navy Band perform.

I think, as a popcon, this fortnightly challenge should be pretty easy to put together (I would hope).

Martin Büttner

7:49 PM

@PhiNotPi agreed

does anyone have suggestions for winning criteria other than popcon?

PhiNotPi

8:40 PM

Not really.

I'm sure that there is some ridiculous mathematical criteria we could use.

But then that wouldn't be very fun.

Martin Büttner

8:53 PM

I mean, there's the obvious "sum the lengths of the patterns that solve the following problems" criterion, but it's really prone to HQ9+ style answers, and we can't just generate new patterns all the time when we suspect an answer to be tailored to the problems

Transcript for

Fortnightly challenge of 2015-02-20: …