I wonder if you could come up with a decent 2D pattern description language (like regex, but 2D)... on PPCG it could be really useful for challenges like CH's Nether challenge, where you'd have to do some annoying floodfill... but I think even in normal programming tasks it could be really useful when dealing with data on grids.

A 2D regex....

well it doesn't have to be based on regex

it could be a grammar or something else

Something like that could solve challenges like this very easily: codegolf.stackexchange.com/questions/3117/facial-recognition

yep

actually, CH's challenge sounds like a job for regex though

You can describe the location of the different parts in terms of relative coordinates, in that case. If the left eye is (0,0), the nose is (n,n) and the right eye is (2n,0). Then, there would have be a way to describe the location of the mouth from (0,2n) to (2n,2n).

With the Nether challenge, for some numbers x,y (and some origin location), there are obsidian block from (0,0) to (x,0) to (x,y) to (0,y) to (0,0).

The answers are only a few suggestions, nothing really major.

nice find though!

One suggestion is to do it in a row-by-row format, like this: timepedia.blogspot.com/2007/09/…

Actually, that can probably be expanded beyond a row-by-row format.

The example that blog post uses is a really bad one, since it can be solved with regular regexes.

In the "find the cross" problem in the SO question, so could write a 2D regex like a/a/a/(a+a+a+b+a+a+a)/a/a/a

A column of three a's above a row of aaabaaa above a column of three more a's.

The one problem I see is that it does not yet describe how the column must line up with the row.

I did it:

Seems good.

Hey

Hmm I can't seem to run this answer codegolf.stackexchange.com/a/45485/7162

Ah, the tryapl site doesn't support the ⎕ operator

Trying and can't seem to get it working either, but I don't know any APL...

I do

Well it relies on a dyalog-specific ⎕rl variable

and in the linked snippet he uses a lambda with ⍺ and ⍵ instead of input

Oh, it works if I copy and paste the f←{(.5*⍨¯2×⍟?z)×1○○2×?z←⍵⍴0⊣⎕rl←⍺} part from the link and do 5 f 10

I can't figure out how did I forget to rename the _ENV variable when designing golflua :P

Also that solution is invalid as pointed out by marinus

Indeed it seems to be - doing the same input twice yields the same thing but the numbers are completely different when using the same seed but different N

also a sum of bytecounts across multiple puzzles is a bad idea

also dang this place has changed since I've been here last time

Will probably be biased towards one of the harder challenges, yes. ^^ @MartinBüttner

How so?

So many people over 10k

Someone should make a programming language based on haskell

You mean a golfing language? Or...?

er

yeah

A golfing language based on haskell. The IO would be a nuisanse though

Would be interested to see how that would work...

well maybe if you allow unicode operators, and then suffix unary operator

then make unsafePerformIO and seq cost 1 character each

haskell has some really nice list processing stuff

The problem with unicode operators I guess would be challenges which require printable ASCII only

> filterM (const [False,True]) "hello"
["","o","l","lo","l","lo","ll","llo","e","eo","el","elo","el","elo","ell","ello","h","ho","hl","hlo","hl","hlo","hll","hllo","he","heo","hel","helo","hel","helo","hell","hello"]

> sequence $ replicate 3 [3,5,7]
[[3,3,3],[3,3,5],[3,3,7],[3,5,3],[3,5,5],[3,5,7],[3,7,3],[3,7,5],[3,7,7],[5,3,3],[5,3,5],[5,3,7],[5,5,3],[5,5,5],[5,5,7],[5,7,3],[5,7,5],[5,7,7],[7,3,3],[7,3,5],[7,3,7],[7,5,3],[7,5,5],[7,5,7],[7,7,3],[7,7,5],[7,7,7]]

(read: list monad is magic)

:P

@mniip yes, there will be a bias towards harder challenges, but I'm not sure that's a bad thing. I hope I'll manage to choose the challenges such that there won't be one challenge completely dominating the rest. but if there are like 3 harder ones that make for longer programs, I don't really see a problem.

man, I think I'll just write a command-line tool in C# that reads a regex from a source file and the target from STDIN and comes with a few flags to either print out truthy/falsy, number of matches, the matches themselves or a regex substitution, so I can claim that there's an existing regex interpreter...

XD

@MartinBüttner That's called grep

or sed

for .NET regex...

grep.NET

@feersum oh?

egrep?

@feersum or is that a suggestion for a name? :P

^ That

ah right

I like that

Apparently there's this

(just doing a quick search)

@feersum although I don't think I want to turn this into a full-blown grep

what's the difference between .NET regex and regular regex

hunts down Martin's epic explanation...

@mniip it has a number of funky features... most prominently variable-length lookbehinds and balancing groups

@Sp3000 I still had it open from yesterday ;)

nvm Martin's a ninja

Balancing like lua's %b?

better than that, but for the same purpose

oh, and (related to balancing groups), you can access all captures of any group (not just the last one), because captures are essentially stacks

(which allows funky things like arithmetic)

let the golfing commence...

What where

where what?

the golfing?

I was talking about my regex submission to the Nether challenge

Hey Martin, what's the [^!]+ early on for?

@Sp3000 I want to store the lines of the portal (i.e. a string of n underscores) in a group, which I can then just match with a backreference (instead of having to shift around n matches on every line)

the [^!] matches any character, including newlines

. doesn't work?

(well, for the given input, anyway :D)

Oh newlines, right

@mniip doesn't match newlines

(by default)

there's an option to make . include newlines, but I also use . in other places where it relies on only matching _ and X

You can probably do something silly like \D instead, I think

For 2 bytes

oh, nice

@Sp3000 btw, while I was golfing this yesterday, I noticed that the winning submission to the regex CnR could have been shortened a lot: codegolf.stackexchange.com/a/40077/8478

(by using the (?<x-y>) syntax)

Ahaha probably :P

I'm thinking at that point people had probably solved too many NP-complete problems to have much energy left

:D

Also I promise to get data structures done by tonight...

nice

Sigh I should start being productive

It would be amusing if you could just do a backreference that just matches the number of chars

@Sp3000 yeah, it would be somewhere between a backreference and Perl's recursion feature

Like a(.*)b({}\1)c({}\1)d to match aXXXXXbXXXXXcXXXXXd or something

(inventing own funny syntax)

:P yeah - actually can you do it with just recursion?

(hmm might be a bit tricky)

well with recursion you can re-apply the same pattern (which allows for different characters), but then there's no restriction to use the same number of repetitions between applications.

so you can use unnamed balancing groups... neat :)

.NET gets weirder

:D

actually, I think during solving this challenge, I may have discovered a way to work around the bug that prevented me from solving Doorknob's challenge last year (codegolf.stackexchange.com/questions/26057/…)

this close to two digits...

(and halving my initial score)

you cannot beat 81 anyways

@Optimizer I don't intend to

since when do we stop golfing when we're beaten?

but there definitely is a way to be shorter using regex, if that is your point

(especially by another language)

@MartinBüttner we don't but we do keep the intentions of beating the other language in mind..

@Optimizer CH doesn't accept it as a competitive submission anyway... so...

@Sp3000 nice profile picture btw ;)

@MartinBüttner not when you have a full program there too

;) you should do another one. That was easily my most productive week of last year.

@Optimizer I do, but that's not beating anyone...

@Sp3000 it took me forever to come up with that one (to be interesting and not a duplicate of the existing image processing challenges)

okay, my goal for this regex is to ditch the horizontal scrollbar... 5 characters to go...

Ahaha k, well if I ever get time I'll fix up my submission...

lol, I'm down to 98 now, but I don't need the scrollbar any more anyway, because I've got linebreaks in there now :D

Two linebreaks!

okay, I think that's pretty much it

not quite half my initial score but at least I hit my goal of 98 :)

Since I have the Morra controller working for Java, do you think it will be okay to post the challenge and wait for a wrapper to be added later?

Also, it turns out this would be the first KOTH I've ever hosted.

Are there reasonably similar wrappers for previous KotHs to save you having to write them from scratch?

Somebody said that they could probably write a wrapper for a few languages which included the compilers as well.

Would a generic wrapper that uses STDIN/STDOUT to communicate with any language be possible?

It's a pretty simple IO scheme. There are six strings passed as arguments, and two numbers are returned.

But, I might actually need to keep the programs alive and pass input via STDIN.

In the Java version, the competitors are objects which are kept alive for the whole tournament. This would allow them to store information between matches.

@PhiNotPi sure. but be aware that you lose HNQ time if the challenge doesn't really take off until the wrapper is added

I don't really expect HNQ time.

@MartinBüttner I lied about being done today :/ damnit

Anyone know the (old) game gamedesign.jp/flash/chatnoir/chatnoir.html ? I have some ideas for challenges based on the idea of this game.

anyone wanna discuss?

sure

@flawr What are you ideas?

(I just played the game)

Well I had a few ideas: One idea was kind of a cop-robber-king-of-the-hill mix:

Given a field of a certain size, the competitors can program 'cats' and 'players' which will all compete against each other.

then we can find the best cats (those who evaded the most) and the best players (those who caught the most cats)

what do you think of that?

I am not sure whether there exists ideal strategies that always let you win /lose, but I think this is difficult to find out

Well, the main concern would be that there is a way to brute force the solution.

hm, can you think of a way of bruteforcing all solutions? I thought the number of possible moves is too big, but perhpas you can simplify it

How about brute-forcing from the cat's perspective?

hi all

hi@trichoplax

There are 6 moves each turn ^ number of moves.

@trichoplax i.sstatic.net/dJDCG.png seems to be the shortest unreacable shape yet

As far as I can tell, the strategy of "being two steps ahead of the cat" seems pretty good, but that might be taking advantage of the suboptimal AI

It's probably a suboptimal AI. A better AI would recognize that it couldn't catch up to you like that, and make a break for the opposite side of the board.

Well I thought as a cat you can always find the shortest way out, and then weigh your chances on how many ways in which direction, but I am not sure whether it is optimal

Of course you have 6 moves eacht turn, but you do not know in advance where the player will place walls

wich generates much more possibilities.

And yes I assume the given flash game has a pretty simple AI

can anyone compile kuroi neko's solution codegolf.stackexchange.com/a/45481/9206 in linux?

I get bpaste.net/show/77b03516372a

A large board will probably prevent brute-forcing. We should just set a short time limit to prevent extensive computation.

Well but then we need all submissions in the same language in order to be fair

seems to be a problem with timer

any C++ people in?

Well, it doesn't have to be that short.

@Lembik Cool. I was just on my way to tell you I'd found a length 32 solution - but that's even better

@trichoplax assuming it is correct :)

It wasn't me that found it

^ What challenge is that for?

@Lembik I checked it was correct using neighbours()

the complication is that it turns out the shortest unreachable shape might not be one where there is no legal move

@trichoplax great!

@PhiNotPi codegolf.stackexchange.com/questions/45059/…

still open:)

@Lembik Yes there may be an isolated network of interchangeable shapes not connected to the straight snake

@trichoplax exactly! Although I doubt it :)

I'm just editing to include the ability to display a snake. If I include the length 30 one as an example, who can I give credit to?

@trichoplax to be honest.. I am surprised that all shapes are reachable for so many snake lengths

@trichoplax a visualisation would be great.. nudge.. :)

@PhiNotPi I fear that if the field is too big or too small, then only tha cats or only the players will win with a high probability

At least up to n=16. We could probably rule out a few more as I expect your machine has enough memory to solve 17 or higher

@trichoplax it is length 31 I think... credit to "David K"

@Lembik Editing it in as we speak...

@trichoplax great!

@Lembik Oh yes of course - 30 joints is length 31

@flawr Will the grid have random spots already filled in? I think it might be impossible to win otherwise.

@trichoplax why does your code fail in python 2 even with from future import division?

@PhiNotPi you mean for the players?

For the players (it would be a win for the cat)

i think if the field is big enough you could always win as player

As the field grows, the player can start building the wall further away from the cat, but has to cover a larger perimeter.

lets say the field has a radius of r

then the player has to be able to place every second dot on the perimeter

before the cat comes to that point

but the player sees in which way the cat is moving, so he can conecntrate on that area

because to fill the whole perimeter, you need about 2*pi*r dots

because you only have to fill every second dot it is about 3*r dots you have to place

that means you can already close a third of the perimeter with every second dot before the cat reaches that point

which is imho more than enough for winning

if r is big enough

@Lembik I only wrote it for python 3. It's not intended to be back-compatible. Since pypy works with 3 I didn't have a reason to think of python 2. There are a few things it could be. Does it give an error message as a clue?

@Lembik this David K?

@trichoplax I believe it is

@trichoplax bpaste.net/show/a26c6b967656

@trichoplax oh no.. my mistake.. this one math.stackexchange.com/users/139123/david-k

@Lembik I'll include the correct credit in my answer :)

@trichoplax cool

@trichoplax so I wanted to ask two follow up questions and I would be interested in your opinion now

although I am also interested if Jakube is going to post a corrected answer

@Lembik That isn't an error that would stop the program running - it just failed a doctest. You can still proceed, because in this case the doctest only failed because python 2 uses set() instead of {}

@trichoplax aha! Thanks

@Lembik I was wondering what your follow up questions were going to be - you hinted before that you had some ideas

@trichoplax the problem is that they reply on people understanding a working solution to the existing solution :) OK ... so follow up a) Given a 2d shape, find the shortest set of rotations that makes the shape. Smallest number wins

b) the same set up as we have now but in 3d. Find the shortest unreachable snake

for a) I will have to come up with one or more good and fun shapes :)

for which I might need help

what do you think?

of course b) would hugely benefit from some beautiful visualisation

but again I would need a volunteer who knew how to do that

s/reply/rely :)

b) would need extra specification (I think). Would you allow only rotations that cause a bend, or also rotations that twist? I think this would affect the possible shapes

@trichoplax what is the difference between a bend and a twist here?

For each joint there are 4 directions in which to bend, and 2 directions in which to twist

oh.. I only meant bends

For a straight snake, a twist makes no difference

no twists allowed!

For other snakes, a twist allows getting round awkward situations

twists sound very interesting but I think it is hard enough already :)

I wonder if there is a simple way to translate directly to a POVray input file

Indeed! I just meant that you'd need to specify. Otherwise some people would think "bend" includes twist, and get different answers

or maybe that could be a PCCG too

@trichoplax yes.. you are right

@Lembik Do that one first then ;)

@trichoplax it might have to be pop-con which people hate

can you think of a way of specifying it otherwise?

The biggest problem that occurs to me about (b) is that it may have even more steps before diverging from a simple self-avoiding path like the OEIS sequence than the 2d variant does

I'm guessing it's easier in 3d to get around obstacles

@trichoplax true but I think it will be easy to come up with a very long one by hand

so people can just work on finding something shorter

I don't expect a provably optimal solution!

I should say I think that the current question is likely to have a more efficient solution than the current one

@Lembik if you specify the requirements strictly then you can make it code-golf or fastest-code or whatever you like.

@Lembik I can't quite process that sentence

@trichoplax How can you tightly specify it? I don't know how to specify something that ultimately has a graphical output

unless I actually tell them exactly what the output will be.. in which case the challenge seems pointless

@trichoplax that's because it didn't make any sense :) I just edited it

@Lembik I can read it now :) You mean my answer is unlikely to be the most efficient way of calculating how many shapes can be reached? Yes I agree! It was only meant to be an example to encourage others. Although I can't think of another algorithm I'm hoping someone else will.

for the current snake challenge, did you consider divide and conquer. That is, place the snake on the x axis with the middle at 0. Now look at the number of shapes that the right half can make without move any part to the left of the line x = 0 and then the number of shapes that the left half can make without move any part to the right of x =0. Then add the shapes that can be made which do overlap. The first part is recursive

I'm not sure that will help

the first two numbers are the same of course

Some of the shapes possible with one half are not possible if the tail is extended by even one unit

so you don't need to compute them twice

it seems to allow you to avoid recomputing parts of the total number. If I am right, you actually have to visit every single shape you count currenly, right?

If it was an accurate method, then doubling the length of the snake should square the number of possibilities, which doesn't seem to be the case

@trichoplax that's because of the overlaps which are important. I am not suggesting this is suddenly poly time. Just maybe a small exponential

Yes currently I try every bend at every joint for every snake I have so far, to see if there are more to add. Very far from efficient :)

My idea is vague but do you see that it seems sometimes you can more than 1 to your current count without actually having to visit every shape

ok cool :)

Ah I see. So not expecting it to give all the answers, but just narrowing it down a bit?

exactly!

I do see a problem with my initial divide and conquer idea though :)

but I think you can at least get some advantage

You could possibly do this from the other direction too - eliminating any string that contains an illegal substring. For example, a loop of 000 or 222

an interesting idea!

One thing that seems tantalising is that although the OEIS sequence grows above 2.6 each step, your sequence should suddenly start growing much slower once it reaches the diverging n (which we know is 31 or lower). So if we can get enough efficiency to reach whatever n that happens to be, getting further will suddenly get easier

@trichoplax possibly :) I am not sure it will grow so much slower

Out of interest, does the display function work in python 2?

will there ever be a point where most shapes are unreachable?

You mean more than half of the non-intersecting paths cannot be folded from straight?

exactly

I couldn't guess

me neither :)

The number of unreachable shapes will go up fast once it starts, but it might still grow slower than the reachable shapes. I can't think of a way of reasoning about it

maybe a good question for math.se :)

It's always interesting when ppcg overlaps with math.se

TIL you can go back and edit an edit

TIL?

@Lembik "Today I Learned"

Thanks!

That was 100% new to me :)

no problem

ten irritating lions

I find it hard to imagine lions which are exactly irritating

If it was simple then it wouldn't deserve an acronym :D

:)

Twerking Is Lame ?

meh I wanted to regex the Privileged Substrings challenge, but it doesn't seem possible. I think I'd need anchors for the end of a recursive call, and I don't think that's possible.

your regex obsession is going wild

challenges that are solvable with regex are rare... so I jump on every opportunity :P

I think to solve it, I'd need variable-length lookbehinds and recursion...

(and even then I'm not sure it would work)

Maybe you need a new language called REWTLEIN (Reg Ex With Those Little Extras I Need)

lol

well they exist

just not in the same flavour :D

So you'd have to combine all the flavours into one?

two of them would be enough :P

basically, if .NET supported recursion it would be the only flavour I'd ever need

for .NET to support recursion, .NET has to support recursion first.

@Sp3000 interesting... the capture doesn't get popped by a (?<-x>...) until the group is completed. so you can match palindromes with ^(.)*.?(?<-1>\1)*$.

I like the regex that matches 2 adjacent characters and captures each one

@aditsu what do you mean?

(.)(.)

lol right

do you like it because it looks like that ? :P

@aditsu I think I had that in a PPCG answer of mine, but I can't find it any more... I guess I had to golf it out :(

haha

ah! codegolf.stackexchange.com/a/37907/8478

@aditsu In Haskell, that's "compose the second input of binary function with a unary function"

@MartinBüttner <butthead>uh, huh-huh-huh</butthead>

@Zgarb it's time to declare "I should learn Haskell" and promptly forget about it again

so... ummm... with the stacks... I wonder if that makes .NET regex Turing complete (by encoding a 2-stack PDA)... I'm sure you can encode state transitions with balancing groups (and the stacks, too), but I think that you might need to be given the stack alphabet at the end of the input string (because you can't conjure up arbitrary characters).

@lembik hi there. About this ###!?! compiler error on k-mer counting... I can see no reason why your compiler chokes on it. I upgraded to g++4.8 and still no errors. I copy-pasted the code from my actual post, so it's the same stuff that compiles on my computer and doesn't on yours.

I checked g++ options. Nothing fancy, just -O2 for optimization. Should compile and link like a charm.

@kuroineko For me, it fails on g++ 4.7, 4.8, 4.9 and on Clang 3.5. (on Ubuntu 14.10)

will now test on Windows

What the ### is going on there? Could you try to rename timer_t into xxxtimer_t or something? maybe the name is already used by some linux include?

sure, will try

as for exit() being undefined, that should be fixed by including <cstdlib>

when doing that, I get the same error as when compiling on Windows:

/tmp/ccMBs4qG.o: In function `main':
kmers.cpp:(.text+0x42d): undefined reference to `divsufsort'
collect2: error: ld returned 1 exit status

Even when I have that file added.

But the timer errors are gone, so that looks like something Linux-specific.

that linker error is normal, you must also compile divsufsort.c (there is a link to the source in my post)

ah

and thanks for the timer_t thing. Serves me right for trying to use cool type names.

@kuroineko After copying all divsufsort files and running make, I still get the same error when compling your C++ file. Do I have to do something to refer to the compiled binary?

No. Simply linking main.o and divsufsort.o should do the trick

maybe it's a c/c++ linkage issue

Yep, that worked.

at laaaast....

So after compiling divsufsort, this was the command I used:

g++ main.cpp -o main divsufsort.o

I use Qt IDE for g++ compiling, and the command was:

g++ -Wl,-s -Wl,-subsystem,console -mthreads -o release\l_kmers.exe release/main.o release/divsufsort.o

...which is a slightly more convoluted way of doing the same thing

I'll update my post and include the command line, just to be on the safe side. Thanks again.

That command line doesn't seem to work for me.

sure, it's in windows. I'll post your command line, not mine :)

ah, I see

@kuroineko I've looked at the commands in your edit -- the first one does only work if you append a -c argument, which is not there in your answer.

dang... I should have gone for a walk instead of getting myself into that Linux mess :) Thanks for the third time

You're welcome!

I have an Ubuntu in a VM, but I never could bring myself to setup a comfy environment to share directories and work on the same sources as in Windows, so I only use it when I can't avoid it.

I'm currently taking AP CompSci. Every once in a while, I get an assignment that seems really... easy.

Instructions: Write a program to calculate prime numbers.
The design and implementation details of this program are completely up to you. The program should allow the user to enter an upper limit (e.g., 100, 1,000, etc.) and the program should calculate and display all of the prime numbers from 1 to the upper limit.

I almost want to submit a program that uses the Perrin sequence to "calculate" primes. It's accurate up to 271441.

implement it in something stupid like SK-calculus or iota-calculus

I was thinking of using the AKS primality test, which has polynomial time complexity but is still super-overkill.

I'm famous-search-engine-ing your suggestions right now.

What language is that assignment in

Java

You can write a FRACTRAN interpreter and run Conway's program :P might be a bit slow though

hey

it's me again=)

anyone here?

Everyone is dead.

NOOOOOOOOOOOOOOOOOO

do you know this game: gamedesign.jp/flash/chatnoir/chatnoir.html

small addictive flash game, try to catch the cat.

as i said erlier, i want to make a challenge based on this idea

and id like to ask for someones opinion on my idea=)

Is that game even solvable

protip: start placing the dots at the boarder

outside

and only place every second one until the cats comes too close=)

@Sp3000 I've got a .NET regex challenge for you: find a way to make the interpreter try out an arbitrary number of zero-length matches in a loop. ;)

It all makes sense now

(I don't have a solution yet, but if you can find one, I think I can prove Turing-completeness)

mniip, could you solve it?