The Nineteenth Byte

12:13 AM

@MartinBüttner @El'endiaStarman I just finished creating the first part of my paper on pdqsort, would love some feedback

Alex A.

@orlp I had always known the acronym PDQ to mean Pretty Damn Quick, so I figured pdqsort would be a play on quicksort as Pretty Damn Quicksort.

Doorknob 冰

@orlp What did you use to make that PDF?

orlp

@Doorknob冰 latex

with the tufte-handout document class

and a whole bunch of manual labour

Alex A.

It looks really nice

Doorknob 冰

Ah, okay. It looks very nice ^.^ (although the content is mostly completely over my head)

ninja'd

orlp

12:18 AM

@Doorknob冰 why?

it's not supposed to be difficult

Doorknob 冰

I haven't spent much time (read: any time at all) purposefully learning about algorithms, etc. (although I probably should)

Calvin's Hobbies

12:33 AM

@orlp "Why doesn't some person on the internet instantly understand this random cs topic I threw at them?" - ftfy

Doorknob 冰

I would lean more towards blaming my relative incompetence in these subject areas. :)

New Main Posts

0

Q: Output the Partial Products

In long multiplication, after multiplying the numbers, you are left with the partial products, in this challenge you will output those partial products. Because long multiplication is long, to compensate your code will need to be as short as possible. Examples 34, 53 102, 1700 48, 38 384, 14...

El'endia Starman

@orlp Reading it now.

orlp

@El'endiaStarman you gave me a heart attack

El'endia Starman

The PLUNK sound? :P

orlp

12:42 AM

for some reason the sound notification turned back on on this chat

FULL MAXIMUM OVERVOLUME

El'endia Starman

heh heh whoops :P

Alex A.

@orlp Sounds loud

quartata

Was cruising around for low quality answers when I found this

Maltysen

41 3

?? ok

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

Encode bytes to PGP wordlist format code-golf kolmogorov-complexity The PGP Word List is a set of 512 English words for verbally communicating strings of bytes, such as authentication codes or hashes. It is used in some important applications, such as the DNSSEC Root KSK Ceremonies held four ...

Alex A.

@quartata @Maltysen Uhhhhhhhh

El'endia Starman

12:55 AM

@orlp I'm quite intrigued. Kinda want to make a visualization of it now.

Is the "Dutch national flag problem" well-known in this area? I've never heard of it before.

So I have no idea what it is...

orlp

Dutch national flag problem

The Dutch national flag problem (DNF) is a computer science programming problem proposed by Edsger Dijkstra. The flag of the Netherlands consists of three colours: red, white and blue. Given balls of these three colours arranged randomly in a line (the actual number of balls does not matter), the task is to arrange them such that all balls of the same colour are together and their collective colour groups are in the correct order. The solution to this problem is of interest for designing sorting algorithms. In particular, variants of the quicksort algorithm that must be robust to repeated elements...

I should probably add a reference for it

Alex A.

Of course as a Dutch person you'd pick the Dutch national flag problem :P

#dutchproblems

orlp

@El'endiaStarman My algorithm is significantly faster for sequences not containing many duplicates than previous solutions

El'endia Starman

Funnily enough, the "See Also:" section had a link to...American flag sort.

orlp

and it should be nearly as fast for sequences with very few distinct elements

it depends a bit on whether or not you use a comparison model that gives three-way comparison

El'endia Starman

1:00 AM

huh, okay

orlp

(I don't), but even assuming three-way comparison it saves a CPU branch

El'endia Starman

Is pdqsort entirely your creation?

orlp

define 'entirely'

this portion of quicksort is (to my knowledge) novel, and fully my idea

El'endia Starman

Well, you're the only author, but you use "we" in the paper.

orlp

Yes

El'endia Starman

1:03 AM

I know there's usually a tendency to avoid using "I" in academic papers, but it just seems a little weird to me when there's only one author.

orlp

I'm not decided either way yet

'I' also feels wrong

El'endia Starman

hmm

orlp

and writing everything in the passive voice gets boring

El'endia Starman

haha, yeah

orlp

@El'endiaStarman but does the paper explain the partitioning algorithm well?

El'endia Starman

1:05 AM

I think that if I tried my hand at it, I'd be able to give a definite answer.

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

Golf A Wiki The Challenge Golf a wiki. A wiki, for the purposes of this contest, is defined as a website with: Content editable by all Easy (i.e. non-HTML) linking Your wiki can be a self-contained HTML file, or a cgi-bin script. Scoring Your score is the size of your program in bytes, di...

El'endia Starman

I think I understand the single step portion, where the pivot is the leftmost element and at the end of partitioning, it is followed by all of the lesser elements and then all of the greater elements. I think I don't get the recursive step.

Do you have a due date of any kind for this, @orlp?

orlp

@El'endiaStarman no

El'endia Starman

okay

orlp

@El'endiaStarman I'm in general pretty happy with my exposition

I still have some loose ends to tie up however

b might be smaller than the >= partition of A

because there are partition steps in between

@El'endiaStarman but once these loose ends are tied up my next section will be really elegant

El'endia Starman

1:11 AM

Okay, cool. So this is a paper-in-progress?

orlp

yess

it's only the first section of many

Maltysen

I screwed up my computer and can't even boot :(

El'endia Starman

AH, okay.

orlp

@El'endiaStarman the elegant part is that it will be easy to show that a certain value can only be selected as pivot value twice

once as p, and once as q

this instantly gives me a proof for O(n * k) runtime for k distinct keys

in other words, when k is a small constant, pdqsort runs in linear time

and scales smoothly to linear time

El'endia Starman

Yeah, that bit jumped out at me from the introduction. O(n) in most common cases is amazing.

orlp

1:13 AM

@El'endiaStarman github.com/orlp/pdqsort

more information about the algorithm there

implementation is fully complete

BlockCoder1392

Hey

El'endia Starman

@orlp I like that chart. :)

Impressive that your algorithm does almost as well as Timsort in many cases.

orlp

1:28 AM

@El'endiaStarman which part of the recursive step is unclear?

also, there isn't really a 'recursive' step

I just proved it works for 'Any non-leftmost subsequence'

El'endia Starman

My brain isn't functioning as well as usual at the moment, so new concepts are not "click"ing as well as they normally would. I'm also trying to make myself hunker down and finish Minkolang.

That's why I asked if there was a due date. Since there isn't one, I can get back to this in a few days.

orlp

@El'endiaStarman due date is tomorrow

hurr

El'endia Starman

22 mins ago, by orlp

@El'endiaStarman no

orlp-is-self-contradictory

;)

CSᵠ

1:43 AM

boom, 10 stars remaining...

Hipe99

10 stars on what?

CSᵠ

--------------------------------------------------------------------->>>

Ampora

I was about to say that this room is almost at 10000 chats with stars.

3

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

I just watched The Force Awakens \o/

Ampora

8 Omar

Omar

MOAR

CSᵠ

1:44 AM

^

Ampora

My iPad don't want my continuation of not typing my bad char.

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

Are we star happy, today? :/

Ampora

along with many of you I think :P

2

CSᵠ

star gazing

3

history !!!!!!!!!!!!!!!!!!!!

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

\o/ no mods in the room afaik

quick let's party

2

CSᵠ

1:46 AM

ohh well

Ampora

10000!!!!!!

4

CSᵠ

BOOM

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

@Ampora that's a large number

CSᵠ

/<[^>]+>/

that's beautiful

Ampora

@Cᴏɴᴏʀ It in fact has much big to it

CSᵠ

1:47 AM

@Ampora needs a space

otherwise... factorial factorial factorial...

Ampora

Or it's n(n-2)(n-4)(n-6)... for !!

n=x?

If you want

x = k ?

I bring forth a thing from @Wrong - b/c this room has 10000 chats with stars, all of you who star chats from now on will b BAN'D. Thank you.

3

CSᵠ

1:53 AM

you mean, like that ^ ?

Ampora

BAN

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

@CSᵠ I͒ͬ̋ͧ ̓̐̓̊ͪ͌w̋̑̍͂̔̒iͮ̍̂l̋͗͋l̐͂̓͛̍̍̌ ͦ̎ͦ͂̾u͑̚s̄ͪȇͥ ͑ͭͨȞ̾̽Tͥ̏ͭ̉Ṁ̐ͥ͒͌́L̋̄̅ͥ ͯ̐tͩ͛̇̚ŏͧ̆̎ ̉̔͗̊̍͆pͣ̄̎ͫͧaͫ̈́̽ȑ̇̾̇͛̚s̉ͬ͐̉̋e̒̄̿ͩͭ̇͛ Reg͗̐ͭE͊̈x͆̑͌ͪ̾̈́̐

Alex A.

@Ampora ?

CSᵠ

@CᴏɴᴏʀO'Bʀɪᴇɴ 4eva, so will I m8, KTHNXBYE /\R/

Ampora

Hi Al. @CSᵠ put a star and now this room has 10001 chats with stars. That's an ugly # so ban amiright :P

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

1:55 AM

@CSᵠ *KTHXBAI

Ampora

@Cᴏɴᴏʀ What is this, LOLCOD*?

E

@Ampora ... maybe

or...

CAN I HAZ i

1:56 AM

NO you CANNOT

Hipe99

@CᴏɴᴏʀO'Bʀɪᴇɴ CAN HAZ STDIO

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

@Hipe99 YEA U CANZ

CSᵠ

import ERROR, export NO ERROR

@CᴏɴᴏʀO'Bʀɪᴇɴ hmm, this starting to sound like a nice fork to LC

2

Ampora

I HAS A HAT

Hipe99

@Ampora *HAZ

Ampora

1:58 AM

IPAD IS BAD

I PUT HAZ DAGNABFLIPPINABBIT!

CSᵠ

MEMORY ALLOCATION ERROR, HAT iz BAN

2

Doorknob 冰

hi I am fun police I have come to kill the fun

3

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

@Doorknob冰 NOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

Doorknob 冰

... ehhh too much effort. Enjoy your dirty stars. :P

9

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

Yay!

\\\\o////

Hey, guys, I have a new esoteric programming language: Brainbash

It's brainf*** with two tapes.

And extra mobility

BlockCoder1392

2:16 AM

....

@CᴏɴᴏʀO'Bʀɪᴇɴ That'sjust brian&chuck?

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

@BlockCoder1392 what's that?

BlockCoder1392

uhm'

Adnan

@CᴏɴᴏʀO'Bʀɪᴇɴ esolangs.org/wiki/Brian_%26_Chuck

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

@BlockCoder1392 Ah, no, it isn't. Two tapes, not programs.

Alex A.

@Doorknob冰 Can I chat ban @Ampora until they start using the letter e again?

Doorknob 冰

2:26 AM

@AlexA. Ampora used the letter e once, but is still in denial

Thomas Kwa

@ןnɟuɐɯɹɐןoɯ if you don't explain your ESMin answers, we won't understand them, and we won't vote for them.

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

@ThomasKwa Speak for yourself.

Alex A.

You vote for answers you don't understand?

Granted, I vote for answers that are explained and are proven to work, even if the methodology used is over my head.

Doorknob 冰

2:41 AM

I simply don't vote for answers that use all possible 256 byte values (with a custom charset to be able to access more than the 95 chars of ASCII), out of principle.

Transcript for