The Nineteenth Byte

Doorknob

9:07 PM

@MartinBüttner How is this "Looks OK"? codegolf.stackexchange.com/review/low-quality-posts/14641

Martin Büttner

@Doorknob seemed like a reasonable number of bytes for a brainfuck submission

Rainbolt

@Doorknob Are you taking a stab at the "Unreasonably non-competitive, so should be closed as not an answer." thing that was discussed last week?

If I was on the fence before, seeing an 83 thousand character code-golf submission knocked me off of it. That should definitely be downvoted.

Doorknob

@MartinBüttner Yes, but answers on Stack Exchange should be self-contained, not outsourced somewhere else. Right? (I came across this "disputed review" in the flag queue, and I'm wondering what you were thinking about it)

@Rainbolt No, the problem is that if pastebin goes down, the answer's worthless. (And people don't like clicking more unnecessary links just to see the code.)

Rainbolt

Oh I see.

I thought there was a problem with the competitiveness of the answer

Martin Büttner

@Doorknob so what if your language doesn't allow you to golf it below 30k bytes?

@Rainbolt there indirectly is

Rainbolt

9:11 PM

@MartinBüttner Ignore me

Martin Büttner

huh what? I don't follow any more

user2179021

hi

FireFly

Heya @user2179021

Doorknob

@MartinBüttner Well now that I look at it, I'm fairly certain that was autogenerated and that he didn't type out 83000 characters by hand. If he actually put some effort into it (at least writing his own autogeneration code or something), then yes, it probably could get that low

@user2179021 Hello!

user2179021

I was wondering whether anyone is interested in mathematical optimization challenges? That is I give a function to optimize and the best answer within x seconds wins

the problem I suppose is how to define the time limit

Martin Büttner

9:13 PM

well whatever, gonna delete vote next time

githubphagocyte

I saw another answer come up for deletion with a very low byte count (lower than others on the same question) but flagged for length or content, with no explanation and nothing apparently wrong with it.

Doorknob

Ok, I'll leave a comment and delete

Martin Büttner

@user2179021 you'll have to measure it on your own machine

user2179021

maybe just the best answer wins with no time limit

@MartinBüttner I am happy to do that

Martin Büttner

@githubphagocyte that happens automatically

user2179021

9:14 PM

I just don't know what people's appetite is for math :)

githubphagocyte

@MartinBüttner you mean no one needs to flag it for a short post to show up in the queue?

Eric Tressler

I like math

Martin Büttner

most of the entries in the Low Quality queue are because it's common here to just post title + code block (and usually a short code block) which triggers SE's automatic flagging system

user2179021

@EricTressler Good!

Eric Tressler

But people have different computational resources

Rainbolt

9:14 PM

@user2179021 The best way to gauge interest is to post your challenge in the Sandbox. We have a bot that automatically scours it for new posts and notifies the users in this channel, so it will get some attention. I would encourage you to post it before 5:00 Central Standard Time to get the best response, because after that time, the chatroom starts to shrink.

Eric Tressler

You really can't leave people to their own devices if you want to have a fair challenge

user2179021

@Rainbolt what time is it now?

Rainbolt

4:15

user2179021

aha :)

Eric Tressler

You could run an evolutionary algorithm on a cluster, or pay some money to run it on the cloud, and it will discourage anyone else with a single machine from attempting it

Rainbolt

9:15 PM

@user2179021 You could also post it, come back tomorrow and ask for opinions on it.

Eric Tressler

That's why code-golf is nice; it's very egalitarian

user2179021

thanks

@EricTressler I know but I like things with some mathematical or scientific meat :)

I think there area really clever people on the Internet and it's great to see them using their brains :)

Eric Tressler

So do I, but it's difficult to make them into good challenges here

user2179021

right

Eric Tressler

Runtime is perhaps the worst metric we have

user2179021

9:17 PM

@EricTressler right.. it is a bit annoying

Martin Büttner

@EricTressler I don't think it's a bad metric. It's just a difficult one to enforce.

githubphagocyte

we have a metric for metrics?

Eric Tressler

So if you can come up with an alternative, in terms of algorithmic complexity, code size, etc., it's virtually always better than limiting runtime. Unless you're willing to run the code yourself, which mitigates all of that

user2179021

@githubphagocyte :)

@EricTressler I don't mind running the code at all

Martin Büttner

@EricTressler the problem with algorithmic complexity is that it almost always leads to ties

user2179021

9:17 PM

@EricTressler but people like to post their own scores

Rainbolt

If someone writes a scheduler that can reserve and assign entire cores (or pi machines) to a particular process, our problem will be solved.

Martin Büttner

(waiting for phagocyte to mention the pi rack)

user2179021

are there really algorithmic complexity challenges here?

githubphagocyte

@MartinBüttner wow you're quick

Eric Tressler

Yeah, but as @MartinBüttner said, it's not a good metric either. It's too coarse

user2179021

9:19 PM

unless it is for 3-sat :)

Martin Büttner

@user2179021 we recently created a separate tag for them: fastest-algorithm

user2179021

cool!

Eric Tressler

3-SAT doesn't need us, they have their own contest :-p

user2179021

so I have some questions that might be interesting ther

@EricTressler :) they keep on reducing the exponent by tiny amounts

Eric Tressler

At my last job, I spent some time turning some problems into SAT, and one day I spent some hours turning the SAT problems into graphs and putting them in Gephi (a graph analysis program). I got some really cool pictures out of that

user2179021

9:22 PM

nice!

Peter Taylor

Penrose tiling, eat your heart out. p196.

Eric Tressler

We were trying to identify some common characteristics of SAT problems that made heuristic solvers fail. But we didn't find anything unexpected

Martin Büttner

@PeterTaylor O.O

Eric Tressler

@PeterTaylor do you generate that via subdivision?

Martin Büttner

@EricTressler projection apparently

or can't you generate via projection?

Eric Tressler

9:23 PM

Wow; I know just a little about that method

No, that's apparently the best method, but I only know that anecdotally

It's more complicated, but researchers use it

I believe it's a projection from R^5 into R^2?

But there are extra constraints that are required, or else the projection will violate the matching rules of the penrose tiling

Martin Büttner

for penrose, yes

Peter Taylor

@EricTressler Still beats popularity.

@EricTressler In this case, from R^7

Martin Büttner

Does that have 3 prototiles?

Peter Taylor

And it's actually less complicated than subdivision. Just more algebraically involved.

githubphagocyte

@PeterTaylor that tiling is incredibly rich. I'm half expecting you to find spaceships with glider guns mounted on the sides.

Peter Taylor

9:26 PM

Yes, it has rhombs of 1::6, 2::5, and 3::4 angle ratios.

Martin Büttner

:D

ah that makes sense

Eric Tressler

@PeterTaylor Now implement Hashlife for it

I'm kidding, it's very impressive. I'm looking through your code

Martin Büttner

@PeterTaylor I'm wondering whether I'll manage to get my first submission for that ready before you post your tenth :D

Eric Tressler

@PeterTaylor Am I misunderstanding something? It looks like you're using subdivision with iterations stopping at depth 7, not the projection method

Peter Taylor

I've only posted 6 so far. (Ok, I have 5 which I haven't posted, but that's because they're not interesting).

@EricTressler Yes, you're misunderstanding everything. There is no subdivision at all.

Martin Büttner

9:29 PM

@PeterTaylor yeah I know, but 6 isn't too far from 10 and I don't have any code yet :D ... you just need to come up with a new interesting tiling ^^

Eric Tressler

@PeterTaylor I was looking at Sparr's code :(

Martin Büttner

lol

Peter Taylor

He uses subdivision.

Eric Tressler

# break one triangle up into 2-3 smaller triangles
def subdivide(self):

Clearly. Sorry for the confusion

Peter Taylor

The number 7 was an unfortunate coincidence.

githubphagocyte

9:30 PM

I'm not going to attempt to look at the code since I'm expecting it to be a projection from R^7 into ASCII

Eric Tressler

Yeah, my fault. I think when the images loaded on the page, it scrolled me directly from your post to his

and I didn't know the difference. To be honest, I don't understand the projection method very well. Also, can you guarantee that yours is aperiodic?

Peter Taylor

When following an answer link I generally wait for things to settle down, put the focus in the address bar, and hit enter. No need to reload the page, and finds the anchor correctly.

Eric Tressler

I'll remember that

Peter Taylor

I can. There is a point of global rotational symmetry by a prime order which isn't 3. That's sufficient.

Eric Tressler

the variety in neighbor relationships lends itself to having a lot of oscillators, but many may only be possible in specific regions/configurations

Martin Büttner

9:34 PM

@EricTressler I believe that works for any pair of dimensions as long as the hyperplane projected on is totally irrational

(I'm currently reading up on this stuff :D)

Peter Taylor

(I think that "by an order which isn't 3, 4, or 6" is sufficient, but I'd have to review the proof)

@EricTressler But every finite region should occur infinitely many times at different densities, so that's not really a problem.

Eric Tressler

True, but it makes the situation much more complicated for certain purposes. For instance, I don't think you could construct a turing machine here

So it would be a real feat to prove that it's universal

Peter Taylor

That's why there's a 40-point bonus for aperiodic tilings.

In retrospect it seems high, given how few gliders have been found.

Martin Büttner

We still don't have a tiling with two really distinct gliders.

We just have two (similar) grids where the glider can support two additional live cells

Eric Tressler

It may have been a better problem, or a separate but potentially more interesting one, if people were allowed to specify their own life rules for their tilings

githubphagocyte

9:40 PM

@EricTressler that may have been judged too broad

Martin Büttner

That is one amazing ASCII pirate ship: codegolf.stackexchange.com/a/36470/8478

Eric Tressler

There's clearly a happy medium. @githubphagocyte yeah, that's why I was wishy-washy saying that

githubphagocyte

@EricTressler I'd like to see that somewhere, just not sure if it would be accepted here. I'm imagining a combination of a lot of support and a lot of objection...

Martin Büttner

I suppose for the common regular tilings they have all been examined thoroughly somewhere?

Eric Tressler

Fine-tuned Universe

The fine-tuned Universe is the proposition that the conditions that allow life in the Universe can only occur when certain universal fundamental physical constants lie within a very narrow range, so that if any of several fundamental constants were only slightly different, the Universe would be unlikely to be conducive to the establishment and development of matter, astronomical structures, elemental diversity, or life as it is understood. The proposition is discussed among philosophers, scientists, theologians, and proponents and detractors of creationism. Physicist Paul Davies has asserted that...

Martin Büttner

9:43 PM

@EricTressler Accepting an infinite number of universes, that is quite obvious, to be honest

It's like saying "wow, what a coincidence that OUR planet is the only one around that supports life"

Eric Tressler

I know the anthropic principle :-p

I think you just almost quoted Dawkins

Martin Büttner

never read anything by him, and I wasn't aware that that's called the anthropic principle :D

Eric Tressler

My point was that if you change the tiling (i.e. the situation of the game), you might get more interesting results if you can adjust the rules as well

Martin Büttner

yeah, that's very likely

I wonder if there's another Turing-complete CA rule on the square grid (also using only Moore neighbourhood and two states)

I mean, there probably is, but how different would it be?

(I think there would be too many for Conway to luckily stumble upon the best one)

githubphagocyte

I think Conway was deliberately searching for a rule with balance between rapid decay and excess growth leading to meaningless chaos.

Eric Tressler

9:49 PM

He was

Also, I don't know if there is, @MartinBüttner

githubphagocyte

There still might be plenty more though

Eric Tressler

It's been a few years since I looked into it, but most rules are seriously degenerate

githubphagocyte

It might be interesting to extend the rule search beyond the 8 cell neighbourhood

Eric Tressler

and there aren't so many that only consider the 1-neighborhood

^

There are plenty of people who have generalized on Conway's Life

githubphagocyte

@EricTressler you mean there are already examples out there for me to view?

Eric Tressler

9:50 PM

Yes

githubphagocyte

oh dear this will take up time :)

Eric Tressler

But it's been years since I studied it, so I'm no longer a useful source of information

You'll have to google it

githubphagocyte

I'm going to avoid googling it until I get a few things finished...

Eric Tressler

well, when you do, there is a world of research

a lot of it is crap

some of it is okay

githubphagocyte

I want to get my KotH going, and contribute to a KotH controller with the option to freeze bots, and also write an answer to the single line drawing question

Eric Tressler

9:52 PM

Mostly, it's undergraduates and master's students looking for an easy thesis topic, but there are legitimate papers out there

githubphagocyte

I'm looking forward to the day that computer architecture is less divided between memory and processor, and cellular automata can run natively

Martin Büttner

@EricTressler Well there's at least B145678/S1245678 :D

Eric Tressler

Martin Büttner

(that's flipping live and dead cells if I'm not mistaken)

Peter Taylor

@EricTressler And actually they're often the best papers to read, because they explain things at a level which the author can understand.

Eric Tressler

9:55 PM

Perhaps I can sell you this Tressler Mark VI processor

githubphagocyte

@EricTressler can I override the rule on it??

Eric Tressler

No, but you can cook and eat anything you find inside

githubphagocyte

edible processor substrate...

Eric Tressler

Note: Eating the contents may compromise the integrity of the processor

Martin Büttner

so I think there should be 2^15 CAs with considering the 1-neighbourhood. I wonder how many you can rule out immediately, but I could imagine a few thousand distinct and potentially interesting ones remain.

Eric Tressler

10:04 PM

Most of the interpretations of the CA rules don't allow you to distinguish directions

So you really have 9 states, and 2^9 total CAs

Martin Büttner

hm?

if I write the rule as above

B12356/S358

I have 16 digits for which I can decide to include or exclude them

that's 2^16

but there's at least one symmetry by flipping live and dead cells

which is how I got to 2^15

Eric Tressler

wait, hang on.

Martin Büttner

basically you get 9 living and 9 dead states

Eric Tressler

you're right

Martin Büttner

actually 0 is a valid choice

so 2^17

Eric Tressler

10:08 PM

you have your own state and 8 neighbors, so 2^18; how are you getting symmetry?

Martin Büttner

there's an equivalent rule where living and dead cells are switched

Eric Tressler

oh, right; for the purposes of counting gliders and things, yes

githubphagocyte

This is for CAs where 3 neighbours has different results depending on which neighbours they are?

Martin Büttner

no

githubphagocyte

Oh no - I see now

Martin Büttner

10:13 PM

B12356/S358 says a dead cell comes alive if 1,2,3,5 or 6 neighbours live and a living cell stays alive if 3,5 or 8 neighbours live

lol that new challenge's title

githubphagocyte

Is your symmetry by expressing those as a death and survival rule to get the same numbers twice?

FireFly

Lol, cute

githubphagocyte

Too cute for words

Martin Büttner

@githubphagocyte well as a death and stay dead rule :D

githubphagocyte

@MartinBüttner oh yeah...

Martin Büttner

10:18 PM

@Doorknob "Thats"?

githubphagocyte

@FireFly just accidentally exited the chatroom by pressing backspace - now I can see your new avatar. I like it

Martin Büttner

Did you hit Enter instead of Backspace ;)

FireFly

Hehe, was thinking I'd join in on the avatar-from-tweetable-art-contest thing

Doorknob

@MartinBüttner Yes. :P

Martin Büttner

Ah I knew I had seen that title before somewhere.

I think this is the first code golf I wanna do in C#

but not tonight

Doorknob

10:21 PM

I think I'm going to try it. I'm bored. :P

Martin Büttner

in?

Doorknob

Ruby, probably

githubphagocyte

I love the original question it links back to...

Martin Büttner

@Doorknob thought so :D

I guess you can just do it by iterating through the string and maintaining a stack of bracket types and their positions

Doorknob

yeah that was my idea

Martin Büttner

10:25 PM

but I'd like to try a pure regex-replace-until-nothing-is-found-anymore approach :D

Doorknob

llama@llama:~$ cd Code/ruby/
llama@llama:~/Code/ruby$ mkdir ReplacesSpacesBracesBlahBlahGolf
llama@llama:~/Code/ruby$ vim SomethingSomethingIDontKnow.rb

Martin Büttner

not very golfy

Eric Tressler

I found a regex to check for prime numbers earlier, but I couldn't figure out how to adapt it to look for smooth numbers

Martin Büttner

hehe

Eric Tressler

I also wrote some python code that was strikingly similar to the existing python entry, which I discovered when I went to post, so I abandoned

Martin Büttner

10:30 PM

how would one regex look for smooth numbers though?

Eric Tressler

I don't know if it can

Martin Büttner

do you mean you'd replace a unary number by its largest prime factor (again unary)?

Eric Tressler

it can't select a member from a range, that I know of

it returns a binary result on a string, right? or even that might be wrong

Martin Büttner

well you can return a match

Eric Tressler

I read enough to understand the prime-checking algorithm, and then I was stuck

Martin Büttner

10:31 PM

which can be any substring

and with capturing you can get multiple substrings

well the standard regex for prime checking gives you any divisor

Eric Tressler

there's a standard one?

Martin Büttner

well there is that well-known one on SO

you'd need to make sure that that divisor is prime... greediness should then give you the largest prime factor by default

Eric Tressler

I was looking at /^1?$|^(11+?)\1+$/

which only matches primes

Martin Büttner

no it only matches composites

Peter Taylor

@EricTressler ^(.{1,X})\1+$ and you increment X in a loop

Martin Büttner

10:34 PM

but that's the one

@PeterTaylor that's cheating :P

Peter Taylor

Wait, that's no good.

It only checks for divisibility by small numbers, not lack of divisibility by large numbers. I think I should go to bed.

Eric Tressler

@MartinBüttner It matches primes with "false", sorry for the misunderstanding you are wrong

Martin Büttner

what now? :D

Eric Tressler

Heh. Anyway, I spent a little while trying to adapt it to look for smooth numbers

but I couldn't

People who use grep for things it was never intended for amaze me

Martin Büttner

I think it's possible

let me give it a try

Eric Tressler

10:37 PM

I mean, I can use it to strip junk out of a log, but not for elaborate things

okay

Martin Büttner

damn, I thought I had it :D

it worked for n = 12, but it fails for 15

debugging now

Eric Tressler

You should post if it you can do it

Martin Büttner

oh wait

it does work

just not for prime numbers

^(11+)(?=.*(?=\1$)(?!(11+?)\2+$))\1+$

I'll try to get the prime numbers to work

for a unary encoded number this gives you the unary encoded largest prime factor

Eric Tressler

there's that, but also the challenge of handling the range

Martin Büttner

how would you even represent the range?

githubphagocyte

10:46 PM

Seeing something being used for other than its original intention reminds me of reading that someone had written a ray tracer using template definitions in C++, so that all the calculation was done by the compiler up front and the run time was near zero

Eric Tressler

I don't know

you could stick it in Perl

Martin Büttner

I guess you could give it comma-separated list of numbers and try to return the smoothest

ugh, making it work for primes is annoying

here is the simplest attempt to make it work for primes as well, by checking them separately

^(?:(11+)(?=.*(?=\1$)(?!(11+?)\2+$))\1+|(?!(11+)\3+$).*)$

the appropriate way would be to move that long lookahead to the front, but then you need some dark magic to trick PCRE into backtracking into a lookahead

I figured out how that works once, but it's not necessarily shorter

Eric Tressler

Witch!

FireFly

burn ~~her~~ him!

Eric Tressler

I need to read it carefully, but I actually have to go for a bit

bbl

Martin Büttner

10:55 PM

I'll probably sleep soon, but ping me if you have any questions, I'll reply tomorrow

Actually that regex was still inconsistent. This one always gives you the result in the same capturing group:

^(?|()(11+)(?=.*(?=\2$)(?!(11+?)\3+$))\2+|(?!(11+)\1+$)(.*)())$

There might be a simpler way... I'm not entirely sure that the problems I encountered with simpler version weren't due to a bug in the tester instead of a problem with the PCRE spec.

I'll think about optimising this and maybe even selecting the smoothest number from several tomorrow

Doorknob

^ Terminator is pretty awesome for golfing.

I can have my code, the output of my code, and irb all in one window!

VisualMelon

Fun fact: you can seg-fault Terminator by creating and moving frames around

New Sandboxed Posts

11:42 PM

0

A: Proposed Question Sandbox - Mark XIV

Voice recognition: "Yes" or "No"? (Previous sandbox submission: http://meta.codegolf.stackexchange.com/a/1793/7773) Task Implement a program in minimum bytes of source or binary code that does voice recognition of a voice sample (me saying "yes", "yeah" or "no" in voice or in whisper, plainly ...

Doorknob

11:54 PM

Wow. I just realized our homepage activity rivals even some of the most active graduated sites, such as Server Fault (!). :D

PhiNotPi

@Doorknob What are those statistics?

Doorknob

@PhiNotPi Well, for example, we only have stuff from ~1h ago on the first screenful of our home page, while a site like Webmasters has stuff from 2-3 hours ago

githubphagocyte

It would be interesting to do that kind of comparison at different times of day and see if time zone makes a difference to how we rank

Transcript for