The Nineteenth Byte

1 5 3 2 9
(find longest contiguous sorted segment starting with 0)
[1 5] 3 2 9
(add element)
[1 5 3] 2 9
(starting with 2, shift segments of length N until the segment is sorted)
[[1 5] 3] 2 9
[3 [1 5]] 2 9 (not sorted, try other segment)
[1 [5 3]] 2 9
[[5 3] 1] 2 9 (not sorted, resets & decrement length)
[[1] 5 3] 2 9
[5 [1] 3] 2 9
[5 3 [1]] 2 9 (not sorted, try other segment)
[1 [5] 3] 2 9
[1 3 [5]] 2 9 (sorted! repeat)
1 3 5 2 9
[1 3 5 2] 9
[[1 3 5] 2] 9
[2 [1 3 5]] 9 (not sorted, resets & decrement length

El'endia Starman

mbomb007

7:05 PM

@El'endiaStarman Both pills at once!

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

idk what that is. :( imgur is blocked

mbomb007

Morpheus GIF (from The Matrix), "Show me"

El'endia Starman

@CᴏɴᴏʀO'Bʀɪᴇɴ Morpheus from The Matrix leaning forward and saying "Show me".

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

Oh, XD

mbomb007

Even if it's blocked, you could copy the URL, then search Google for similar images.

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

7:06 PM

Oh, that's smart

TimmyD

> I know ~~Perl~~ kung-fu.

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

Imgur is blocked as being "classified" o_O

El'endia Starman

@CᴏɴᴏʀO'Bʀɪᴇɴ Interesting idea. I wonder what its worst-case complexity is. O(n^3) or something?

mbomb007

@TimmyD I will call you ~~.NET~~ Neo

dangit.

how to strike

El'endia Starman

Three dashes.

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

7:08 PM

---x---

DANGIT

El'endia Starman

Alternatively, make a sword.

flawr

@mbomb007 I'd take the green one. Oh damn colourblindness.

mbomb007

@El'endiaStarman left click

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

@El'endiaStarman Thanks! I was wondering that, too. Worst case would be a reversed list, right?

TimmyD

@mbomb007 Press X

mbomb007

7:08 PM

@TimmyD Ask a girl out. oooooooooooh!!!

El'endia Starman

@CᴏɴᴏʀO'Bʀɪᴇɴ I think so, yeah.

TimmyD

@mbomb007 Band together with your fellow employees and start a picket line.

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

Is it good enough to make a challenge out of?

mbomb007

Bowl. Granny style.

El'endia Starman

Good enough to sandbox at least.

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

7:09 PM

Alright, thanks

TimmyD

Take down a set after the last performance.

mbomb007

@QPaysTaxes Someone already said. Right below that msg.

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

lel

No

mbomb007

@QPaysTaxes That's what DSL stands for.

Dontcha Slow-internet Love?

@QPaysTaxes Time to switch to UDP.

TimmyD

@mbomb007 Dontcha Lo -Int?erSlow net

mbomb007

7:14 PM

Trivia! What does the 'g' in "ping" stand for? :D

TimmyD

Ping is not Gnu?

quartata

Nothing it's not an acronym

mbomb007

@quartata It's a backronym.

So yes it is.

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

g means "Gee, what's the problem with my ping"?

mbomb007

@QPaysTaxes If TCP didn't work, try UDP.

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

7:15 PM

and bai

mbomb007

@quartata It means "GROPER"

Packet INternet Groper.

Think about that next time you want to ping someone.

flawr

@mbomb007 Pizza Is Not Good

El'endia Starman

TIL I grope everyone I ping. :x

mbomb007

@QPaysTaxes Yeah. I know. It was a joke.

@QPaysTaxes Use Wikipedia. Or take a related Computer Science class.

Anonymous

@mbomb007 I have a degree in computer science, including a class on networking, and I have never heard that. I'm calling BS.

flawr

7:19 PM

@Mego Bachelor of Science?

Anonymous

@quartata Did your avatar get hit with radiation that caused it to mutate?

Anonymous

@flawr Yep :P

flawr

@Mego BS = Bachelor of SCience.=)

quartata

@Mego Yeah, I've never heard it either.

Anonymous

@flawr I knopw. It was a fantastic double-joke.

Nathan Merrill

7:20 PM

back

do you still need help @QPaysTaxes?

Anonymous

@quartata How many rooms are you in?

Nathan Merrill

I don't know the difference between type and typename

Anonymous

Are you talking C++?

mbomb007

@Mego So do I. And I learned it in a networking class.

Anonymous

@mbomb007 I think your professor may have been pulling your leg.

Nathan Merrill

7:22 PM

but yes, a class Value with a generic type is what you want

Anonymous

@QPaysTaxes I can help, whatcha need?

mbomb007

@Mego I think it was in the textbook.

Nathan Merrill

that way you can extend it with Int<int>

Anonymous

@mbomb007 citation-needed

quartata

@Mego A few.

Anonymous

7:23 PM

@QPaysTaxes Should be

Anonymous

Though I might be busy beating Piety :P

Anonymous

That's the truth :P

mbomb007

Ping (networking utility)

Ping is a computer network administration software utility used to test the reachability of a host on an Internet Protocol (IP) network. It measures the round-trip time for messages sent from the originating host to a destination computer and echoed back to the source. The name comes from active sonar terminology that sends a pulse of sound and listens for the echo to detect objects under water. It is sometimes interpreted as a backronym as packet Internet groper. Ping operates by sending Internet Control Message Protocol (ICMP) Echo Request packets to the target host and waiting for an ICMP Echo...

El'endia Starman

@Mego 33. Yes, I just counted.

mbomb007

That's a direct link to the citation on Wikipedia.

FryAmTheEggman

7:24 PM

@Mego Find your own way inland, exile! :P

quartata

@mbomb007 huh

mbomb007

The direct article from 1983: tools.ietf.org/html/rfc889#page-1

El'endia Starman

>

Among the various measurement packages is the original PING (Packet InterNet Groper) program used over the last six years for numerous tests and measurements of the Internet system and its client nets.

mbomb007

@QPaysTaxes That's what I said...?

@QPaysTaxes I still use it.

Anonymous

@mbomb007 That's the program ping being called that stupid name, not the actual act of pinging, which I thought you meant. I'm okay with stupid names for programs/languages. If I wasn't, I'd have a lot bigger issue with JavaScript.

Nathan Merrill

7:26 PM

@MartinBüttner I'm not sure what you are talking about with "Busy Beaver"

I've looked it up on wikipedia, but it might help your post to explain it

quartata

@NathanMerrill Do you mean the tag or the function?

mbomb007

@Mego It's the program that runs when the command ping is invoked.

Anonymous

@mbomb007 Congratulations on being the only one on the planet. You get a cookie.

quartata

We have a tag called busy-beaver

That's what he's referring to in the post

mbomb007

@Mego I know plenty of people who agree with me. :P

Anonymous

7:28 PM

@NathanMerrill This is the best example:

mbomb007

Everyone who's never heard of it is just ignorant.

Anonymous

224

Q: Build a Compiler Bomb

Introduction You're probably familiar with zip bombs, XML bombs, etc. Put simply, they are (relatively) small files which produce enormous output when interpreted by naïve software. The challenge here is to abuse a compiler in the same way. Challenge Write some source code which occupies 512 b...

Anonymous

@mbomb007 Yes, and personal anecdotes are the best form of evidence.

flawr

@quartata We need a lazy-cat

Anonymous

linux.die.net/man/8/ping

Anonymous

7:29 PM

Even the man page for ping doesn't mention that ridiculous name

Anonymous

And Linux man pages love mentioning ridiculous names

flawr

@QPaysTaxes Haha, maybe?=)

Anonymous

My cat just sleeps and begs for food all day

flawr

> TolarenUX feminists call their man page woman page.

I know^^

Part of the joke.

Well ToleranUX wasn't very serious at any point I think=)

Anonymous

I always thought it stood for Manuel, like "Manuel, tell me about ping, please."

Anonymous

7:35 PM

(</joke>)

TimmyD

@Mego jeeves ping

Speaking of, whatever happened to Ask Jeeves ... is that still a thing?

Anonymous

@TimmyD Brb making that an alias

Anonymous

@TimmyD ask.com

trichoplax

@mbomb007 @Doorknob we should start using "6 to 8 calendar weeks"

Martin Büttner

@NathanMerrill I thought I did. Is this unclear? "Find a terminating Brainfuck program with N bytes of source code which prints as many characters as possible/runs for as many ticks as possible."

Nathan Merrill

7:48 PM

yeah, I found it after my message

I guess I'm not convinced that fixed N doesn't work

I mean, lets say you set the limit to 20

and somebody finds the optimal program for 20 (with a proof)

that sounds like a great challenge, that's now solved

mbomb007

@Mego Dave Mills gave Mike Muuss the inspiration for creating the ping utility. So his usage of the acronym is not just a personal anecdote.

Martin Büttner

I think with optimisation challenges in general and busy beavers in particular, it's also very interesting to see how optimal solutions vary with problem size.

it would be nice if the challenge could provide a motivation/context/whateveryouwannacallit for exploring that

mbomb007

@Mego Also, Symantec recognizes the acronym

Nathan Merrill

perhaps a "Find the next N" challenge?

mbomb007

@MartinBüttner Maybe you should create such a challenge in Conway's Game of Life.

Geobits

7:52 PM

N <-- right here

mbomb007

@Geobits No, it would've been the "n" in Buttner.

:D

Martin Büttner

@mbomb007 fun fact: the motivation behind the question is a potential busy-beaver challenge in a particular hexagonal life rule

Geobits

That's n, not N. Plus, there's an n in Martin before that one.

Nathan Merrill

actually, a better idea, tell me if you think it would work, and I'll post it

Martin Büttner

we already have a similar (fastest-code) challenge for standard GoL btw

mbomb007

7:54 PM

@Geobits An n is an N

Nathan Merrill

what if you generate a range of N (say 1 through 50)

and people can submit for any particular N

and the person who has the best solution for the most N wins

Geobits

@mbomb007 I dunno...I swear I've seen problems that used both, and not for the same thing ;)

mbomb007

@MartinBüttner I meant find the largest oscillator or something.

I dunno

"I dunno" always sounds weird in my head when I see it.

like "I done-oh"

Geobits

I dunno why :P

TimmyD

PS C:\Tools\Scripts> "n"-eq"N"
True

PS C:\Tools\Scripts> "n"-ceq"N"
False

Martin Büttner

7:57 PM

@NathanMerrill that's sort of the suggestion in my last paragraph, right? my main concern is about that is that it probably has the same problems as the usual (now off-topic) multi-part challenges.

Geobits

@TimmyD "You're both right" is a terrible answer. Choose your side!

Nathan Merrill

you're second to last problem simply mentions combining the scores

Martin Büttner

especially, if you pick the minimum N too low, then the first few N might have quite trivial solutions which the fastest gun in the west can snatch to get some free points

Nathan Merrill

I guess "counting" is a form of combining

TimmyD

@Geobits I don't wanna.

Martin Büttner

7:59 PM

@NathanMerrill how did you mean that?

Nathan Merrill

I find the optimal solution for 1, you have to find the optimal solution with 2.

I scrapped it because you have to prove optimality

Martin Büttner

hm yeah, it's still quite interesting though, I think.

quartata

@TimmyD wuh

Martin Büttner

it means you'd only move on to the next N when you're actually sure that one N has been exhausted, and the person who found the optimal solution for that N gets "a point" or whatever.

(and the person who has the best score on the largest (still unproven) N also gets a point)

proving optimality wouldn't be required to participate, but only to move on to the next N

Nathan Merrill

so you'd have to prove that the other person's submission is optimal?

Martin Büttner

8:03 PM

or your own

I think there'd be incentives for both

TimmyD

@quartata By default, PowerShell is case-insensitive. The -ceq explicitly asks for case-sensitive equality.

Martin Büttner

the main problem it has is the same as answer-chaining, that you somehow need to keep on top of what the current N is

TimmyD

Single-character strings aren't treated as char but as string, so from a case-insensitive perspective, those two strings are equal.

Nathan Merrill

not really. If you know its optimal, but don't want to prove it, then not proving it still gets you a point

and people can't start on the next N

quartata

@TimmyD That's weird.

Nathan Merrill

8:05 PM

@MartinBüttner to an extent. It's actually somewhat easier, because there's only 1 thing you need to keep track of, N

Martin Büttner

@NathanMerrill by proving it you can get another point for the next N as well though. maybe also give out a point for the person who proves optimality (in addition to the person who found that optimal solution)

trichoplax

I think moving on to the next N without proving (or even reaching) optimality would work in some cases. Some problems might have a very hard to improve solution that isn't optimal

Martin Büttner

so if you do both you get two points

@trichoplax right, but when do you move on then?

TimmyD

@quartata PowerShell is case insensitive, except when it isn't.

Martin Büttner

can I just spam obviously suboptimal but valid solutions for 50,000 values of N?

TimmyD

8:07 PM

Like, escape characters (n for newline and whatnot) must be lowercase. And interacting with stuff outside of PowerShell, like Active Directory, can run into case sensitivity issues.

Nathan Merrill

@MartinBüttner I like the idea of giving a point for the proof, but it'd be weird if an answer was simply a proof that another answer was optimal

Martin Büttner

yeah the SE format doesn't lend itself very well to this kind of challenge.

(I'd be happy with solutions not specific to SE as well for the challenge-writing question, but ultimately of course I'd like to find a way to make such a challenge work here)

mbomb007

I really want this challenge reopened, because I just thought of a couple great answers...

Martin Büttner

that seems like a rather poor reason to reopen a bad challenge

although there's a good chance your answers would be valid here: codegolf.stackexchange.com/q/28672/8478

mbomb007

@MartinBüttner Oh, yeah maybe. Sweet

trichoplax

8:11 PM

A couple of my questions just keep N fixed and choose it large enough to make optimal solutions unlikely. That's a bit of a gamble though...

Martin Büttner

yeah and in the case of busy beavers you also don't want to make solutions possible whose runtime/output size has to be expressed with Knuth's arrow notation...

also chat.stackexchange.com/transcript/message/29124903#29124903 (and the next message)

trichoplax

@MartinBüttner I suppose you could weight scores by some function of N, so it isn't obvious which values of N will give the best scores until the answers come in. You estimate what the best weighting function will be, and then let the answerers explore to find out.

Martin Büttner

that's hard to get right in general and impossible for busy beavers specifically:

> The next option would to leave N unconstrained and make it part of the scoring via some function. Even for "normal" challenges getting the balance of combined scores right is incredibly difficult, but in the case of busy beavers it's actually fundamentally impossible, due to the fact that optimal solutions grow faster with N than any computable function.
> That means I can always beat the best existing answer by going to a sufficiently large N where I can easily find a program that runs for so long that I can get a better score without much effort.

trichoplax

Ha ha - that's the paragraph after the one I'm currently reading. I'll read to the end before commenting any further...

Nathan Merrill

well, I answered it twice with both of my ideas

I'll see what the community thinks of them

(this oddly feels like a meta post)

I actually like my "bounds" idea better

Anonymous

8:19 PM

@NathanMerrill That's why I still think questions like those belong on meta :P

Martin Büttner

these guys use bounds and scale each input size independently

Nathan Merrill

@Mego I disagree, because I like expanding the scope of our site

Anonymous

@NathanMerrill This isn't really expanding the scope. This is taking questions that would normally go on Meta and putting them on Main.

Nathan Merrill

@MartinBüttner that problem feels like this challenge: codegolf.stackexchange.com/questions/52496/…

Martin Büttner

@Mego how is that not expanding the scope?

Anonymous

8:22 PM

@NathanMerrill That may be our second-hardest problem on the site. Hardest obviously goes to Tetris in GoL.

Martin Büttner

well, there's the knots challenge...

Anonymous

@MartinBüttner I view scope as scope = (on-topic on Main) + (on-topic on Meta). It's not expanding it; it's shuffling it around.

Anonymous

Oh yeah, that one is pretty tough, too

Nathan Merrill

and all of you guys hated my "award for the hardest challenge"

Anonymous

If I hated on it, I'd remember it :P

Nathan Merrill

8:24 PM

well, it got -3

flawr

with avcad juic pliz

Anonymous

That's not hating on it. That's 3 more people saying "I don't think this is a good idea" than saying "I think this is a good idea"

PhiNotPi

The threshold for "hating" is -5.

Anonymous

I thought it was -10

Nathan Merrill

wait, did I say -3?

its at -4

I have no idea why I said -3

Anonymous

8:25 PM

-1 for -4 being the hate threshold, I hate that suggestion

Nathan Merrill

unless one of you just downvoted it

PhiNotPi

@Mego I was actually just trying to make a joke, by having the threshold 1 below the current score.

Anonymous

What do you people think of a challenge like "Given N, find the shortest way to express N in a subset of Seriously"?

Anonymous

@PhiNotPi That message was also a joke :P

Geobits

-1 threshold not low enough

PhiNotPi

8:27 PM

Depends on the subset?

Hating is anything below +10.

Geobits

Sounds kinda like stickstack, etc.

TimmyD

PS C:\Tools\Scripts> "Seriously".IndexOf("N")
-1

Anonymous

I'm working on compiling a list of commands that would make a good subset

Anonymous

Obviously the digit-pushing commands, +-/*²ⁿ√, probably the n-th prime and n-th fib commands

PhiNotPi

"Finding the shortest way" could be implemented as "brute-force every possible combo"

Anonymous

8:29 PM

Which is why I'd include a decently large set of possible commands and a time limit

Nathan Merrill

is N fixed, or is the input N and the output the program?

Anonymous

Input is N

PhiNotPi

You could make it a code challenge? (similar things have been done before, I don't remember how well it worked out)

flawr

@AlexA. twitter.com/AerLingus/status/722162956319002625/photo/1

Anonymous

@PhiNotPi It would be metagolf

flawr

8:29 PM

Nathan Merrill

how am I supposed to know that my output is the shortest (short of brute-force)?

Anonymous

For example, N = 10 would be 9u or 1╤ for the shortest

Martin Büttner

@NathanMerrill if it's meta-golf, you don't need to

Anonymous

@NathanMerrill It's metagolf, so the score is your output length

Nathan Merrill

ah ok

Martin Büttner

8:30 PM

(in fact, if it's meta-golf it kinda falls under the same category as what I'm asking about on main)

Anonymous

You don't have to have the optimal solution, but you want to for score

Nathan Merrill

yeah :)

TimmyD

@flawr Cody McCodeface

PhiNotPi

I'm going to make a challenge on tropical geometry (maybe not the geometry, but maybe just performing some "simple" tropical math).

Geobits

Do N = 1...10^9 and sum the lengths ;)

Martin Büttner

8:34 PM

@NathanMerrill in the interest of backing up your answers, you could link to azspcs.net for the first one

Nathan Merrill

@MartinBüttner actually, theirs is a bit different. You actually get partial points for a solution that's almost optimal

Martin Büttner

yeah that's true, but I figured the core of the answer was "use several problem sizes and award points for doing well on any of them"

Nathan Merrill

I added it regardless

Martin Büttner

@QPaysTaxes yes

23

Q: Meta regex golf

In the spirit of this xkcd Write a program that plays regex golf with arbitrary pairs of lists. The program should at least attempt to make the regex short, a program that just outputs /^(item1|item2|item3|item4)$/ or similar is not allowed. Scoring is based on the ability to generate the sho...

code-challenge regular-expression

Sherlock9

@flawr My friends are calling this blasphemy :P

Martin and Nathan, what challenge is this N question from?

Nathan Merrill

8:46 PM

9

Q: How can I score challenges with variable problem sizes?

There is fairly strong support on meta for challenge-writing questions to be on topic on main, provided these questions are specific and answerable. However, we don't have any such questions yet, so I figured I'd test the waters. This question is probably entering good subjective, bad subjecti...