The Nineteenth Byte

Lembik

17:00

@NathanMerrill I approve of big Oh :)

talking of which .. is there an O(n log n) time sorting challenge?

Dennis

The question asks for an O(n) algorithm. That's rather unrelated to run time...

Lembik

@Dennis right

@Dennis well it's related :)

it tells you how the running time scales with input size

Dennis

O(n) algorithms can have O(n^2) implementations.

Lembik

@Dennis that doesn't quite make sense to me

but can I check.. has anyone actually set a code-golf challenge where the restriction is it must run in O(nlogn) time?

seems surprising if not :)

ven

deadlocks are so fun \o/

Lembik

17:11

hmm.. downvote already :(

ven

wow, downvoted?!

Lembik

-1

Q: A classic sorting code-golf question

This is a code-golf question. Input A space separated list of positive integers Output The same list in sorted order space separated. Restriction Your code must run in O(n log n) time in the worst case. This means that randomized quicksort is out for example. However there are many many ...

is there an obvious reason why?

New Main Posts

-1

Q: A classic sorting code-golf question

This is a code-golf question. Input A space separated list of positive integers Output The same list in sorted order space separated. Restriction Your code must run in O(n log n) time in the worst case. This means that randomized quicksort is out for example. However there are many many ...

code-golf sorting

FryAmTheEggman

Might be the space-separated thing, people don't really like restrictive I/O

Dennis

> O(n log n)

What is n?

ven

17:15

the size of the list.

quartata

He knows, he's just pointing out that it isn't specified.

Lembik

it is now :)

El'endia Starman

Plus, you need test cases.

Lembik

@El'endiaStarman for sorting?!

surely everyone knows what sorting means

El'endia Starman

You don't write good specs by making assumptions.

Lembik

17:16

@Dennis could be the O(n log n ) part... I was hoping that as sorting is so classic there are so many algorithms people wouldn't find it too restrictive

@El'endiaStarman fair enough

Dennis

If it wasn't for the input format, I'd have an O(n) brainfuck sort handy.

Nathan Merrill

do we really not have a standard sorting question?

quartata

We have ones for specific algorithms.

Dennis

Alex was going to write one, but met heavy opposition in the sandbox.

Nathan Merrill

why?

Dennis

17:19

I never understood why.

El'endia Starman

I guess it's because sorting is a common problem with a lot of major common solutions.

ven

I'm not smart enough to figure out how the secretary problem works just by looking at the desc, it seems T_t.

Dennis

I feel kinda weird for copying an answer verbatim from another challenge...

Nathan Merrill

have you read the steps @ven ? I tried to make it clear, but I'm not very good at speaking clearly

A Nerd - I

@Dennis If you want to be a moderator on PPCG, you have to make the judgment call as to if that's allowed or not :P

Nathan Merrill

17:22

I'm much better at speaking dense and tersly

Lembik

@NathanMerrill I was pretty amazed too!

Nathan Merrill

? at what?

Lembik

@Dennis O(n) is O(n log n) :)

ven

@NathanMerrill yeah, it only makes me more confused...

FryAmTheEggman

@Dennis I think there's a meta post about that somewhere...

Nathan Merrill

17:24

you basically need to split your array into 2 parts

Lembik

@El'endiaStarman I think having options is what makes a code-golf question interesting

ven

@NathanMerrill it's not very clear when "applicant" means "in this 'concurrent' process pool" or in general...

Helka Homba

Bad news in Brussels, in case anyone didn't know: Brussels Airport and Subway Attacks Kill at Least 30; ISIS Claims Responsibility

Nathan Merrill

the first slice is the first floor(N/e) ellements

Dennis

@FryAmTheEggman Well, it usually indicates a problem with the question. I just happened to post an O(n) solution to another challenge.

Nathan Merrill

17:25

the second slice is the remaining elements

find the maximum of the first slice

Lembik

@HelkaHomba yes :(

Optimizer

@Dennis ooo, -1 point for mod nom

Lembik

maybe having no government for years was actually a bad thing

Nathan Merrill

then find the first element in the second slice that is larger than the maximum of the first slice

Lembik

it's been minutes and still no answer :)

ven

17:26

@NathanMerrill what's N?

Nathan Merrill

the number of elements in the array

ven

this applies then: (:P)

12 mins ago, by quartata

He knows, he's just pointing out that it isn't specified.

Lembik

"Your code must run in O(n log n) time in the worst case where nis the number of integers in the input. "

ven

(although I did not know)

Lembik

hi @Dennis

sorry to criticize your answer which is very nice

A Nerd - I

17:35

I think it's kind of funny that I'm still in the mindset of "I should apply to be a moderator because it could help the PPCG community but also be something to talk about on college apps" even though 1) I'm a really bad person to ask to be a moderator because I'm so new and don't review a lot and 2) college apps ended months ago

Lembik

what are college apps?

quartata

College applications.

A Nerd - I

@Lembik Applications to get into college

Lembik

oh I see!

would they really care?

A Nerd - I

@Lembik It certainly wouldn't hurt.

quartata

17:38

In the U.S. every scrap of extra activity things you can put on your application helps

Lembik

ok..sounds bonkers :)

quartata

It's pretty competitive, yeah.

Lembik

but everyone has to go somewhere

so this is just to rank people so you go somewhere worse?

A Nerd - I

@Lembik I applied to some of the top schools in the US (Harvard, Yale, Stanford, etc.) and these places have acceptance rates around 5%. So everything helps.

Lembik

ok..I am just surprised. I could imagine they might think "I don't like this application because they regard trivial things as important"

or at least I might think that if I were judging :)

and good luck!

Dennis

17:41

@Lembik This is why I dislike challenges with complexity restrictions. Your post doesn't mention that the involved integers can be arbitrarily high (and, in fact, my answer doesn't support values above 255). Why does that matter for counting sort but not for comparison sorts? You can't compare two bytes and two 8 million bit integers in the same time as well.

A Nerd - I

@Lembik It's absolutely the opposite. I applied based on my interest in biology and chemistry with math and programming as other interests to show that I'm multi-faceted.

@Lembik Thanks, decisions come out within the next 10 days.

El'endia Starman

@ANerd-I I actually toured Harvard and MIT in spring break of my junior year, but didn't apply to either. I heard MIT has a fairly cutthroat culture and for Harvard...I felt like if I applied there, it would only be because it was a prestigious school, not because I would actually like to go there.

Lembik

@Dennis counting sort relies crucially on the size of the range of values in the input where comparison sorts don't

Dennis

But they still rely on it. Where's the line?

Lembik

@Dennis so in radix sort you actually split up the 8 million bit integers explicitly as part of the algorithm

@Dennis for comparison sorts you are right that if we want to be formal we need to state what sized values we can compare in constant time

but no one would say that looping from 1 to 2^64 takes the same time as comparing if 2^53 is bigger than 2^47 (both stored in one word each)

Dennis

17:44

@Lembik But once you do that, counting sort becomes O(n).

A Nerd - I

@El'endiaStarman I didn't go for MIT, but I liked Harvard a lot because of its class system; the opportunities I would have for internships, research, etc.; and the housing system. I also LOVE Boston

Lembik

@Dennis once you do what, sorry?

counting sort is only O(n) time if you say you can loop from 1..2^64 in constant time basically

which is just silly :)

Dennis

But still true.

El'endia Starman

^

Looping from 1 to any constant is a constant-time operation.

Lembik

@Dennis not really. As I say, radix sort deals with this explicitly, A comparison sort would strictly speaking also have to split up large numbers

but I am happy not to make people do that

New Sandboxed Posts

17:46

0

A: Sandbox for Proposed Challenges

Golf Practice: TI-BASIC code-golf blah blah history of TI-BASIC. In this question, you'll be using the dialect of TI-BASIC for the TI-84+ series calculators. Either version 2.55MP (the monochrome 84 version) or 5.1 (the latest color version) are admissible. A list of one-byte tokens is here; al...

Lembik

@Dennis although it might make a nice new sorting challenge!

Maltysen

answered in 1 minute 5 seconds after challenge posted \o/

Dennis

Re: silly assumptions in complexity

9

Q: Check if there is an isomorph substring

This question is an extension of Check if words are isomorphs and copies the first part of it to give the definition of an isomorph. Two words are isomorphs if they have the same pattern of letter repetitions. For example, both ESTATE and DUELED have pattern abcdca ESTATE DUELED abcdca beca...

code-golf

New Main Posts

1

Q: Full Width Text

Full width text is text that has a space after every character, including the last one. For instance, the first sentence of this question becomes: F u l l w i d t h t e x t i s t e x t t h a t h a s a s p a c e a f t e r e v e r y c h a r a c t e r , i n c l u d i n g t...

code-golf

Lembik

@Dennis to be fair.. your criticism with respect to counting sort and comparison sorts is not unreasonable :)

if I were being very strict I would require the comparison sorts to be able to cope with arbitrarily large numbers too.. but then it becomes string sorting

zyabin101

17:53

@NewMainPosts I'd assume it's code golf based on the tag, but the absence of the winning criteria explanation in the text makes me want to do this.

I'm doubted.

<_>

El'endia Starman

That 3-byte Jelly solution hurts.

zyabin101

@El'endiaStarman Which one?

quartata

@AandN How come Iðýð doesn't work?

El'endia Starman

@zyabin101 On the question you're talking about.

Nathan Merrill

C--

C-- (pronounced "see minus minus") is a C-like programming language. Its creators, functional programming researchers Simon Peyton Jones and Norman Ramsey, designed it to be generated mainly by compilers for very high-level languages rather than written by human programmers. Unlike many other intermediate languages, its representation is plain ASCII text, not bytecode or another binary format. == DesignEdit == C-- is a "portable assembly language", designed to ease the task of implementing a compiler which produces high quality machine code. This is done by having the compiler generate C-- code...

A and N

17:59

@quartata You're doing a join operator on a string, so that doesn't work. You need to split it before you do the joining.

Sðýð« works though

Lembik

50 minutes and only one sorting algorithm implemented ! :)

quartata

I figured that it would work because strings can be treated as arrays.

A and N

@quartata So far, only Jelly does that :p

Going to implement that now in osabie

Nathan Merrill

hey, newer meta posts override older meta posts, right?

Anonymous

@NathanMerrill Usually

Maltysen

18:02

@AandN so does pyth

Anonymous

What's the specific one you have in mind?

Nathan Merrill

we have two meta posts which basically ask the same thing, but in different ways

11

Q: Golf Practice questions

This is to discuss Golf Practice: Python and the Golf Practice question type it suggests. Some questions that came up: Is this type of question on-topic for PPCG? Is it OK that many of the individual answers turn out the same? Should/can we trust users to come up with their own answers without ...

discussion questions contest-type

Anonymous

@AandN And Seriously

Nathan Merrill

11

Q: Should multi-part challenges be allowed?

We occasionally have challenges which consist of multiple separate subchallenges, whose individual scores are simply combined at the end. These are often known as "golf courses". While these are often quite popular they do have some problems. Mainly it's not clear how we should deal with people c...

discussion scope

A and N

:(

Nathan Merrill

18:02

but with different resolutions

maybe we close the earlier as a duplicate of the newer?

quartata

Why?

Anonymous

@NathanMerrill That's what I'm thinking

Nathan Merrill

@quartata well, they can't both apply

Anonymous

The first is very specific while the second is general, and the newer policy overrides the older one

quartata

Generally newer meta posts override older posts.

Nathan Merrill

18:05

unless there's a difference between golf practice and multi-part challenges I'm missing

quartata

ninja'd

FryAmTheEggman

I think the golf practice one is more specific than the general one, the point of golf practice is that they won't work as full challenges on their own (and hence won't be dupes of real ones)

Nathan Merrill

as far as I know, we don't have any minimum challenge size

Anonymous

I VTC'd the meta post and the golf practice challenge

quartata

It should probably be historically locked.

Nathan Merrill

18:08

^

A and N

@quartata 4 bytes: Sð«J.

quartata

oops accidentally retracted vote :/ stupid internet

@AandN ohh that's evil

Thanks.

A and N

Hahaha

Anonymous

@quartata I dunno about that. Given that it's the only challenge of that type on the site (unless I'm missing others), I wouldn't consider it to be significant enough to be worthy of a lock.

quartata

@Mego There are several like this.

Anonymous

18:09

Oh

Anonymous

In that case, I could agree with a lock

flawr

@quartata feature-request prehistoric-lock

quartata

@flawr status-what

zyabin101

@quartata status-prehistoric-lock

@zyabin101 status-declined

flawr

status-removed

Easterly Irk

18:23

type.method.ac

I have never been as self-conscious about my handwriting as when I was inking in the caption for this comic.

Fix the kerning!!! type.method.ac

Geobits

If they don't already recognize it when it's that bad, it's likely I already hate them >_>

Easterly Irk

Just try the link.

Geobits

I did

El'endia Starman

I also got 100/100 on holly. :D

And the next one.

Anonymous

@El'endiaStarman Cool kids club:

Anonymous

18:29

Geobits

Yea, the next one was easy. Got 100 on a few others, including quijote. Got bored after that.

El'endia Starman

I was rather far off on quijote. That's where I stopped.

Anonymous

I got 100 on Yvess

Easterly Irk

@Mego I has no screenshot, but I got it also.

I have started a trend.

Anonymous

And Roissy :)

CoolestVeto

18:32

sigh

Easterly Irk

@CoolestVeto try it.

Be part of the hive mind.

CoolestVeto

Nah.

Weird stuff is happening.

Easterly Irk

like what?

CoolestVeto

It's probably inappropriate for public chat.

Easterly Irk

okai

Just weird or bad too?

CoolestVeto

18:37

Bad. Much bad. I'ma go harp on one of my rl friends about it.

bbl

Easterly Irk

bai

Optimizer

ok, so its official.

El'endia Starman

Not really surprising to me. Web is the future, and JavaScript is the only really useful language for web apps.

Optimizer

but not just web.

back-end as well

Anonymous

@El'endiaStarman I for one welcome our new Brython overlords

El'endia Starman

18:46

@Optimizer You didn't post a picture of the back-end tab. Just link to it.

Optimizer

@El'endiaStarman its only you

all of'em're images

Anonymous

@Optimizer He means "You didn't post a picture of the back-end tab. Rather than posting another image, could you just link to it?"

El'endia Starman

^

Optimizer

stackoverflow.com/research/…

epicTCK

do you all think this is ready? meta.codegolf.stackexchange.com/a/8734/47019

Optimizer

18:52

windows 10 is really high despite the age!

El'endia Starman

Eyyyy Python is most-used for Math and Data! :D

Anonymous

8.4% of people use Windows 8

Anonymous

Those poor souls

Dennis

They have no souls.

Anonymous

I use 10 and Linux :P

Optimizer

18:53

why is there no 8.1 ?

Easterly Irk

@El'endiaStarman R and julia should be used for data and math.

El'endia Starman

Oooh, it's also pretty high up among languages used by students. Nearly tied with C++ and JavaScript, with Java in first place there.

Optimizer

and 8.1 is so much better than 7. i feel bad for people with 7 and below

Anonymous

@Optimizer Probably because 8 is assumed to mean 8.1

Anonymous

The UI/UX in 8/8.1 is sooo bad for desktops

Optimizer

18:54

still better than 7

Anonymous

citation-needed

Optimizer

i use 50-50 both and 8.1 is better as per me.

only a couple of apps holding me back to upgrade home one to 10

Anonymous

Internally, at Microsoft: "Ok, we're developing Windows 8. The UI/UX from 7 is solid, and people are used to it, because it's been incremental improvements since 98. Now that we've gotten it good, let's throw it out the window and do something completely different. Users will LOVE that."

Helka Homba

Not running @Opt?

Optimizer

am i even active enough?

(dont give cjy example now)

@Mego that feels more like Apple :P

Helka Homba

18:57

@Optimizer More so than some nominees probably

Anonymous

@Optimizer Doing anything more like Apple is a fatal mistake

Anonymous

OS X is closer to 7/10 than 8, though

Optimizer

marketing like apple is a must though, windows phone declines coz of that

Anonymous

Windows phone has no market share because it was very late to the game

Optimizer

it could still have gained a lot if ms put some effort.

made partnerships

with software companies.

Anonymous

18:58

By the time they had a decent device, Apple and Samsung were on their 3rd iteration

Lembik

I am very impressed by the golfing of haskell

Optimizer

oh, I am not even counting pre windows 7.5

they could have reached 10% market share if they did things like apple after they launched 7.5

Anonymous

But 10% market share is still not enough to make it worth it

Optimizer

the ui was refreshing and it was starting to work out

Anonymous

When you're late to the tech game, you can't win

Optimizer

18:59

@Mego it is to garner more developers spending time for windows apps

Transcript for