The Nineteenth Byte

Martin Büttner

19:00

@zyabin101 occasionally. I'm planning to do 9 instalments in total

zyabin101

One, take the hard core idea of length of program is a Mersenne prime and disallow no ops.

Two, take the easier but hard idea of length of program is a prime but still disallow no ops.

The "disallow no ops" is so you can't pad programs.

Nathan Merrill

@zyabin101 considering that primes are more frequent at lower numbers, you would need to make the challenge difficult

Martin Büttner

afaik there is no good way to "disallow no ops" or else, code bowling would work

Nathan Merrill

long var names, comments, whitespace, code that doesn't run, code that runs but does nothing

zyabin101

But this challenge is code golf... Never mind.

Martin Büttner

19:05

@NathanMerrill I think if you were able to tell whether an arbitrary piece of code is an no-op, you'd have solved the halting problem.

flawr

What is a no-op, if I may ask?

Nathan Merrill

@MartinBüttner right, but if you can tell me if an arbitrary piece of code sorts a list, then you've solved the halting problem

Kevin W.

@flawr in this case, code that does nothing

Martin Büttner

a piece of code that doesn't affect any/the relevant state of the program

Nathan Merrill

when determining "what code does", we have always used human judgement

Martin Büttner

19:08

I think the difference is that we normally ask for code that does fulfil a certain property, so it's in the interest of the participants to make it provable that the code has that property. you're trying to impose a restriction where it's in the interest of the participant to make such a prove very difficult.

there's also the thing where you encode the entire program in a unary number to blow up its size.

flawr

So that is just part of a code that you can remove and the whole program still behaves exactly the same?

Martin Büttner

@flawr sort of

flawr

That sounds like it is way more complicated=)

Martin Büttner

I don't know how narrow a definition Nathan and zyabin have in mind.

Nathan Merrill

@MartinBüttner then effectively any "restrictions" we place (as pertains to program properties) is impossible to define

I can't place a restriction of "It can't sort" without human judgement

Martin Büttner

19:12

do we have a good challenge where someone did that?

Nathan Merrill

I don't think so :P

although, we have had challenges that prevent certain operations

Martin Büttner

see...

that's a syntactical restriction though

not a semantic one

Nathan Merrill

I totally agree

Martin Büttner

defining no-ops in 2D languages is also tricky

Nathan Merrill

I'm trying to see if a broad rule of "Restrictions on program functionality are off-topic" works

Martin Büttner

19:14

I think if you phrase it that broadly, all challenges are off topic, because the challenge objective is a form of restriction on program functionality

it's a provable one though.

quintopia

@MartinBüttner no, but it would be faster and hardly be longer to implement than trial division

Martin Büttner

@quintopia why would anyone care about faster in a code golf?

feersum

I care about speed in code golf. I try to make it as slow as possible.

4

Nathan Merrill

lol

quintopia

@MartinBüttner if two solutions are the same length, why not pick the faster one? (no, i haven't proved they would be the same length). in any case, he was asking for suggestions for improvement. one such suggestion would be "code must run in under very small time x"

Cᴏɴᴏʀ O'Bʀɪᴇɴ

19:18

I never got this straight: if you can solve the halting problem for an arbitrary piece of code in language X, then language X is turing-incomplete?

Martin Büttner

yes.

quintopia

@CᴏɴᴏʀO'Bʀɪᴇɴ true

Cᴏɴᴏʀ O'Bʀɪᴇɴ

Oh, cool!

So, removing <> from BF yields a turing-incomplete language?

Nathan Merrill

is it possible to determine the Big-O of a function (without solving the halting problem)?

quintopia

one interesting problem along those lines that lacks a solid answer (or even definition): what's the most comprehensive class of problems that can be solved using a computational model for which halting is solvable?

Martin Büttner

19:20

@CᴏɴᴏʀO'Bʀɪᴇɴ sure because then you only have finite memory

or did you mean []?

Cᴏɴᴏʀ O'Bʀɪᴇɴ

I mean <>

Martin Büttner

then yes, without any form of loop, you can't have a TC language either.

Cᴏɴᴏʀ O'Bʀɪᴇɴ

This stuff is really cool

\o/

quintopia

@CᴏɴᴏʀO'Bʀɪᴇɴ unless you replace it with @ (which swaps between cells 1 and 2) and make those cells unbounded

Cᴏɴᴏʀ O'Bʀɪᴇɴ

@quintopia Oh, yeah, BF minimization.

Martin Büttner

19:21

@NathanMerrill if it's a specific function, yes. you can't do it for an arbitrary function.

Nathan Merrill

@MartinBüttner what do you mean?

quintopia

there is no algorithm which decides for all functions f the asymptotic running time of that function

Nathan Merrill

say I'm an IDE. I have a purely functional function that accepts an array, and returns a number

Martin Büttner

given a specific piece of code, I might be able to solve the halting problem for that piece of code. but you can't solve it automatically for every program.

Nathan Merrill

can the IDE determine Big-O for that function?

Martin Büttner

19:22

@NathanMerrill you can't do it automatically.

Nathan Merrill

:(

quintopia

(unless the language is sub-TC of course)

(and you can sure do very interesting things in sub-TC languages)

Zgarb

@quintopia I think such a class doesn't exist for most reasonable definitions of "computational model", "problem", "solve" and "halt".

Nathan Merrill

@quintopia which is why SQL optimization is a thing

maybe we should simply all use sub-TC languages

quintopia

@Zgarb I have yet to hear of reasonable definitions of those things, so I couldn't say for sure. I'm interested how you came to this conclusion though

Martin Büttner

19:24

@Zgarb I suppose ~~regular expressions~~ regex can do some fun stuff.

@quintopia .NET regular expressions always halt (unless there's a bug in the implementation that I haven't found yet), which is pretty much the only thing stopping them from being TC.

quintopia

@MartinBüttner have there been any problems on ppcg that could not be solved, in theory, by them?

Cᴏɴᴏʀ O'Bʀɪᴇɴ

> Shrewd brainfuckers will have noticed that the aforegiven artistry has seemingly run afoul with recent perl incarnations. Versions 5.20+ exhibit severe indigestion upon encountering this following construct:

perlmonks.org/?node_id=1066494

Martin Büttner

like "shortest infinite loop without producing output"? :P

Zgarb

@quintopia Well, suppose you have a model M for which halting is decidable. It solves some class of problems C, which doesn't contain all computable problems (otherwise M would be Turing complete). Take a computable problem P that's not in C, and make a new model M2 that contains all programs in M, plus a special program that solves P and always halts. Then you have a more powerful model for which halting is also decidable.

Martin Büttner

well many problems as posed on PPCG can't be solved by them directly, because the computational model is a bit restrictive

Zgarb

19:28

I may have misunderstood your question though.

Martin Büttner

e.g. I can't return 0 or 1 conditionally from a regex substitution unless both of those appear in the input string

quintopia

@MartinBüttner and truth-machine. yeah. i suppose that any problem which does not halt is out of the question. and so...there is surely a language that theoretically exists which does more than .NET regex and yet still has decidable halting

Cᴏɴᴏʀ O'Bʀɪᴇɴ

Do we have a challenge for interpreting basic regular expressions?

Martin Büttner

@quintopia I think as soon as you allow .NET regex to backtrack through an empty match arbitrarily often (which would allow infinite loops), it becomes TC

@CᴏɴᴏʀO'Bʀɪᴇɴ I'm pretty sure we do

we definitely have the opposite of "basic": codegolf.stackexchange.com/q/1118/8478

quintopia

@Zgarb this works, but it is not a very interesting answer, since the description of your model grows just as fast as the list of problems it can solve

Martin Büttner

19:31

@CᴏɴᴏʀO'Bʀɪᴇɴ not quite: codegolf.stackexchange.com/questions/7024/compile-regexes

Cᴏɴᴏʀ O'Bʀɪᴇɴ

huh

I tried looking for a regular basic regular expression interpreter here but I couldn't find one

Nathan Merrill

I wanted to do a "generate the shortest regex that matches A, but not B"

until I found that somebody already made a program that does it

quintopia

@NathanMerrill provably shortest?

Nathan Merrill

no, it'd be a code-challenge

quintopia

i'm referring to the program not the challenge

Martin Büttner

19:35

@NathanMerrill codegolf.stackexchange.com/questions/17718/meta-regex-golf

New Meta Posts

0

Q: How do we handle edits that change the code in an answer?

Sorry if this is a duplicate, I haven't seen a post that covers this topic before. I have seen many edits recently that edit the original answers code in an attempt to help golf it. I saw somewhere (sorry, don't remember where) that you shouldn't edit the code in other peoples posts. How are we ...

Nathan Merrill

oh, nevermind

flawr

Love Yourself - Vintage 1920s New Orleans Justin Bieber Cover ft. Sara Niemietz

►

Cᴏɴᴏʀ O'Bʀɪᴇɴ

how often would BF with two tapes and a pointer on each tape outgolf BF?

Martin Büttner

it would never lose to BF

quintopia

19:39

...obviously

but the original question is unanswerable

Martin Büttner

I'm pretty sure it would for any non-trivial problem.

flawr

@CᴏɴᴏʀO'Bʀɪᴇɴ You'd need to assume a distribution on all bf programs.

Cᴏɴᴏʀ O'Bʀɪᴇɴ

I need to... what?

@MartinBüttner That's what I was thinking.

flawr

A probability distribution.

Martin Büttner

depends on what you do to loops though

do they only depend on the first tape?

on a combination of both tapes?

Cᴏɴᴏʀ O'Bʀɪᴇɴ

19:40

conorobrien-foxx.github.io/Brainbash

Martin Büttner

are there two kinds of loops?

Cᴏɴᴏʀ O'Bʀɪᴇɴ

You can switch tapes

Martin Büttner

oh

in that case it might not win as often

Cᴏɴᴏʀ O'Bʀɪᴇɴ

~ to switch tapes and preserve pointers, * to switch tapes and copy the pointer location

Martin Büttner

because switching tapes is as expensive as moving to the next cell

Cᴏɴᴏʀ O'Bʀɪᴇɴ

19:42

yeah

Nathan Merrill

also, BF can be compressed to 3 bits for each symbol

Martin Büttner

it will still win for sufficiently non-trivial problems, but I think the threshold is a bit higher this way

Cᴏɴᴏʀ O'Bʀɪᴇɴ

But who uses compressed BF? :P

Nathan Merrill

but with two tapes (even with separate symbols for each tape), you need at least 4 bits

quintopia

so you could jump to an arbitrary distance on the same tape with ~* (assuming the appropriate setup)

Cᴏɴᴏʀ O'Bʀɪᴇɴ

19:43

Also, } and { move N spots right/left on the tape, based on the current cell's value

quintopia

...Yet Another BrainFuck Derivative

Cᴏɴᴏʀ O'Bʀɪᴇɴ

Yeah, but whatever.

I like it because a range is rather elegant.

quintopia

true

Cᴏɴᴏʀ O'Bʀɪᴇɴ

+++++[[->+~+*]>-~[-*+*]>~>]

quintopia

it would be nice to be able to do array index in general

but adding things to BF pretty much misses the point of it :P

Cᴏɴᴏʀ O'Bʀɪᴇɴ

19:45

Yeah, there's a very fine line

Adding another tape doesn't really make it easier to program in, just more interesting.

IMO, of course

Zgarb

19:56

Argh. I'm manually entering publication data into a university database. After every text box and drop-down menu (and there are dozens), it flashes a "Processing..." animation for over 5 seconds. >:(

El'endia Starman

Man, that sounds annoying. Aggravating, even.

BlockCoder1392

Newmainposts plz

New Main Posts

3

BlockCoder1392

0

Q: Implement a URL shortener

URLs are getting too long. So, you must implement an algorithm to shorten an URL. i. The Structure of an URL An URL has 2 main parts: a domain and a path. A domain is the part of the URL before the first slash. You may assume that the URL does not include a protocol. The path is everything el...

code-golf string

Adnan

ninja'd

BlockCoder1392

19:58

Oh um ninjad

El'endia Starman

.....ninja'd by a bot!! :P

Zgarb

"An error occurred while processing your request! Sorry for the inconvenience."

BlockCoder1392

Hmwut

Zgarb

Well, I saved everything just before that, but still.

BlockCoder1392

S9meone plz answer

@all answer plz

say @a plz answer

Cᴏɴᴏʀ O'Bʀɪᴇɴ

20:00

SHUDDAP AND TAKE MAH UPVOTE

Zgarb

@BlockCoder1392 It's only been 4 minutes.

Adnan

@BlockCoder1392 How do you make math.stackexchange.com to ms.ta?

Cᴏɴᴏʀ O'Bʀɪᴇɴ

^

BlockCoder1392

"M" + "s" +"." + "ta"

M is first letter of math

S is first letter of stackexchange

And ta is 2nd, 3rd

Adnan

Hmmm, okay

Looks like a nice challenge :)

BlockCoder1392

20:03

Btw I saw the URL compression challenge but this is different

Ttoibt tjid on ohone w left Hand

mınxomaτ

I received a Intel-C/++ compiler license. Let's see if it has the mystical powers everyone claims it has.

BlockCoder1392

Use vs

mınxomaτ

what?

BlockCoder1392

visul studio

mınxomaτ

That's not a compiler.

BlockCoder1392

20:09

What I use for c++ thoug/

mınxomaτ

You mean the MSVC compiler. I already use that. But IC++ is way more optimized. (Although GCC (TDM flavor) already beats MSVC speedwise for most of my applications).

ICC gains you anywhere from 20ish% to 200% performance improvement on numerical heavy code over gcc -Os. (BTW: -Os will be faster or equal to -O2 and will be faster than -O3 in 99% of use cases unless you run on a server architecture with huge L-caches on the CPUs to fit the enormous unrolled loops -O3 generates. Consumer machines don't like that.).

quartata

@RikerW "<pet> moves, but only reluctantly"

Dennis

20:35

@NewMainPosts Enough with the taunting, please.

TimmyD

Are you looking for a challenge?!

(Internet cookie to anyone who gets the reference)

Rainbolt

Stinkoman?

mınxomaτ

Hover image, it says stinkoman, ???, profit.

Rainbolt

Exactly what I did, but since I didn't spend extra time putting my conclusion into meme form, I got it faster.

Of course, he did say that anyone who gets the reference gets a cookie, not just the first one, so we both get a cookie.

mınxomaτ

I'll give you mine. I don't like cookies.

Rainbolt

20:46

Thanks, but I'm on a diet. I'll give both of these cookies to @Neil, since he has been afk in the room longer than anyone.

RikerW

@quartata Okay.

Rainbolt

I've lost 9 lbs since January 1st XD

I also noticed that my heart rate increases more when I talk to specific people at work.

randomra

@MartinBüttner What do you think of a "group slicing" operator for Retina which would parenthesize the pattern: `a#b*c#d == (a)(b*c)(d)`
I think it could often save bytes and you have some extra chars now that you are in the ISO charset.

It saves a char even if you need to capture only 1 group at the start or the end of the pattern. Although that could be solved with implicit opening/closing of the parens.

Cᴏɴᴏʀ O'Bʀɪᴇɴ

29

Q: The Rien Number

The Champernowne constant is a number that is constructed by concatenating the first n numbers, with n tending to infinity. It looks something like this: 0.123456789101112131415161718192021222324252627282930... Now, I will describe to you the Rien number. It can be thought of as a minimization...

code-golf math number sequence sorting

Almost at 30 o_O

randomra

This could be done as a preprocessing of the pattern.

TimmyD

21:00

@Rainbolt @mınxomaτ It's from a Strongbad Email cartoon from Homestar Runner. The character is indeed "Stinkoman," so you're kinda correct.

mınxomaτ

Wait, wasn't stinkoman a scrolling shooter?

randomra

@CᴏɴᴏʀO'Bʀɪᴇɴ now I have a sudden urge to downvote :D

Cᴏɴᴏʀ O'Bʀɪᴇɴ

@randomra ಠ_ಠ

XD

I don't care about the rep, just the number :P

mınxomaτ

rep is a number whistles

TimmyD

@mınxomaτ homestarrunner.com/stinkogame/v7/stinkogame.html ?

Cᴏɴᴏʀ O'Bʀɪᴇɴ

21:03

My rep number sucks :P 6104

mınxomaτ

@TimmyD Yeah

I'm confusing different things, but I knew there was some kind of game.

TimmyD

Yeah. The Brothers Chaps, along with Sluggy Freelance, really paved the way for independent, Internet-only media

RikerW

@quartata this will happen to you if you keep being a tourist:

NetHack (DOS) (Fastest death) in 00:01.15 by ais523

►

:P

Neil

21:28

bah, I've been overcounting my bytes

mınxomaτ

@RikerW That beep. I had my vol at 90 percent >.<

Neil

`${f}`.length is actually a byte longer than I expected

RikerW

@mınxomaτ lol

@Neil overcounting then? You mean undercounting?

Neil

@RikerW No, I mean that if I write (say) f=x=>x then `${f}`.length is 5

RikerW

Oaky.

Zgarb

21:37

oaky

Adjective: oaky ‎(comparative oakier, superlative oakiest)

Describing the taste of wine that has been aged in oak and acquired tannins from the wood.

RikerW

Yeah, I know.

Grandma looves wine.

flawr

fuck

Verb: fuck ‎(third-person singular simple present fucks, present participle fucking, simple past and past participle fucked)

(vulgar, colloquial, often obscene) To have sexual intercourse, to copulate.
(vulgar, colloquial, often obscene) To insert one’s penis, a dildo or other phallic object, into a specified orifice or cleft.
(vulgar, colloquial) To put in an extremely difficult or impossible situation.
(vulgar, colloquial, usually followed by “up”) To break; to destroy.
(vulgar, colloquial) To defraud or otherwise treat badly.

(3 more not shown…)

Noun: fuck ‎(plural fucks)

(vulgar, colloquial) An act of sexual intercourse.
2001, Thomas Kelly, The Rackets, MysteriousPress.com (2012), ISBN 9781453247341, unnumbered page:
2012, Heather Rutman, The Girl's Guide to Depravity: How to Get Laid Without Getting Screwed, Running Press (2012), ISBN 9780762445356, unnumbered page:
(vulgar, colloquial) A sexual partner, especially a casual one.
2005, Jaid Black, Strictly Taboo, Berkley Sensations (2005), ISBN 9780425202456, unnumbered page:

(5 more not shown…)

Interjection: fuck

(vulgar, colloquial) Expressing dismay or discontent.

Adverb: fuck ‎(not comparable)

Used as an intensifier for the words "yes" and "no".
Do you say it out loud and proud?

RikerW

WTF?

@flawr Why?

flawr

Why not?

Oneboxes can get quite big=)

RikerW

Maybe un-onebox pls?

flawr

21:44

Never=)

I like teasing americans that have such an issue with swear words=)

RikerW

I hate you.

No, just annoying.

Martin Büttner

@randomra I don't wanna use the ISO set more than necessary, because it's a pain to type.

RikerW

I actually mainly dislike oneboxes.

Hey, more messages means more scroll down?

Yeah, it does.

Sorry @flawr.

:P

Martin Büttner

@randomra I do want to make leading and trailing parentheses optional though

so you could do a)(b*c)(d at least.

RikerW

@flawr Where are you from? UK, AU, Mars...

flawr

21:46

Mars, yeah. No for real: Yurop.

Martin Büttner

but any of those changes will require tokenising the regex, which I want to put off for a bit longer, because it's gonna be a pain.

RikerW

@flawr Okay.

English-speaking or newtonian-speaking?

flawr

newtonian??

RikerW

flawr

Einsteinian would be most accurate I think.

RikerW

21:48

Newt.

flawr

It's a blind worm

slow worm

whatever

RikerW

This?

Anguis fragilis

flawr

Yes.

RikerW

So you are german?

mınxomaτ

Aaaaaaaah, I leave for two minutes and then get back to snakes and wormes?!

RikerW

21:51

@mınxomaτ Trust me, the above was worse.

flawr

@RikerW Nope.

mınxomaτ

@flawr My bet is Swiss.

Martin Büttner

@RikerW newts are not reptiles.

RikerW

@mınxomaτ chat.stackexchange.com/messages/27010999/history

@MartinBüttner IDK whether that was a reptile though.

Martin Büttner

it has scales. it's a reptile.

2

(unless it's a fish, which it isn't.)

RikerW

21:53

@MartinBüttner Or a bird...

Go chicken legs!!

Martin Büttner

what bird has scales?

RikerW

> Pangolins have large, protective keratin scales covering their skin; they are the only known mammals with this adaptation.

Aaaand mammals. :P

flawr

Pangolins are birds?

RikerW

No, mammals.

@MartinBüttner Bird_anatomy#Scales

Martin Büttner

oh, cool.

@RikerW and yeah, mammals try to get a foot in the door everywhere for some reason...

flawr

21:56

Well it is obviously not a mammal and not a bird=)

Cᴏɴᴏʀ O'Bʀɪᴇɴ

No, I'm pretty sure it's a bird.

RikerW

> A caecilian's skin has a large number of transverse folds and in some species contains tiny embedded dermal scales.

Beat that.

Martin Büttner

I just read about those, but read that caecilian's scales are different from fish/reptile scales, plus their underneath actual skin.

I guess those are the "tiny embedded dermal scales"

RikerW

I knew that, I was hoping you didn't....

:(

@CᴏɴᴏʀO'Bʀɪᴇɴ BTW opinion on evolution?

Transcript for