The Nineteenth Byte

Martin Büttner

15:00

uniformly, I take it?

orlp

@NathanMerrill yes, but you didn't specify memory requirements

"can I do X in O(n) with linked lists" is always answerable by yes if you allow O(n) memory

so, what are the memory requirements?

Nathan Merrill

like I said, it needs to be an in-place sort

orlp

define in-place

O(sqrt(n))? O(log(n))? O(1)?

Nathan Merrill

O(1), I believe

orlp

that's really really restrictive

for example quicksort is considered in-place

but is O(log(n))

Nathan Merrill

15:02

then what is "in-place"?

orlp

(you need a call stack of at least 64 elements when sorting 2^64 elements)

Nathan Merrill

oh, the call stack

orlp

In-place algorithm

In computer science, an in-place algorithm is an algorithm which transforms input using no auxiliary data structure. However a small amount of extra storage space is allowed for auxiliary variables. The input is usually overwritten by the output as the algorithm executes. In-place algorithm updates input sequence only through replace or swapping of elements. An algorithm which is not in-place is sometimes called not-in-place or out-of-place. In-place can have slightly different meanings. In its strictest form, the algorithm can only have a constant amount of extra space, counting everything including...

second paragraph

Nathan Merrill

no memory requirements, but as wikipedia says: In-place requires no additional data structure

-.-

orlp

yes, but the definition varies

some people consider o(n) (everything strictly smaller than Theta(n)) to be in-place

some only O(log n)

Nathan Merrill

15:04

I don't care about memory restrictions, but you can't create another data structure

orlp

yes, but the call stack is another data structure

Nathan Merrill

that's fine

orlp

so you've already eliminated non-tail recursive functions

so, define :P

Nathan Merrill

like I said, I'm ok with the call stack being used

orlp

@NathanMerrill that's not enough info, you can store arbitrary information in the call stack

Nathan Merrill

15:06

as long as its not a data structure, you're ok

orlp

I would just say O(log n)

although O(sqrt(n)) often leads to interesting results

@NathanMerrill singly linked or doubly linked?

Nathan Merrill

doubly

orlp

@NathanMerrill I don't think it's possible

it can be done in O(n log n)

Nathan Merrill

how?

orlp

let's first see how we shuffle lists of size n = 2^k

shuffling a list of size 1 is the base case

now we can shuffle a list of size 2*k by splitting it up into two recursive calls to shuffle the first k elements, and the last k elements

Nathan Merrill

15:16

oooh, so you split the list in half, and randomly put a half in the front or back?

orlp

then we can combine these lists by repeatedly tossing a coin

Nathan Merrill

oh, you merge

orlp

if it's heads we grab an element from the first list

if it's tails we grab an element from the second

until one of the lists runs out, the rest just gets appended

I believe that should be entirely bias-free

Nathan Merrill

I'm not positive that appending the remaining list is bias-free

but I'm not positive that it isn't either

orlp

@NathanMerrill I'm fairly positive

Quill

15:19

Kingspray Graffiti Simulator VR

►

TimmyD

@orlp Looks like PowerShell thinks you're positive

PS C:\Tools\Scripts> 'orlp'-gt0
True

orlp

@NathanMerrill now, when the list isn't of size 2^k

you only need to handle one extra case

where you need to merge two lists where one list is one element larger than the other

and I think you can fix that by using a biased coin

if you understand what I mean

Nathan Merrill

yeah I do

orlp

@NathanMerrill I have another interesting algorithm

it would be O(n^2), but it has an interesting property

Sp3000

@orlp If I've understood this correctly, I don't think so. Suppose we have [1,2,3,4] and [5,6,7,8]. Then getting [1,2,3,4,5,6,7,8] is probability (1/2)^4 since after that you must take from the other list, but [1,2,3,5,6,7,8,4] is (1/2)^3 * (1/2)^4

orlp

15:25

you can find out directly the final position of a single element

@Sp3000 hrm

actually yeah, it'd be biased

I'm sure that can be fixed though

ah, I think I figured it out

that should also solve the uneven length lists

to fairly choose one element from two lists a and b

you simply grab (a + b)[random.randint(0, len(a) + len(b)]

in Python notation

so you concatenate the lists, and grab a random element from the concatenated list

how you can simulate doing that is simply by generating a random number between 0 and 1

and if it's <= than len(a)/(len(a) + len(b)) you remove an element from a, else from b

Nathan Merrill

random access is O(n) though

orlp

15:40

@NathanMerrill no, that was just an explanation

afterwards I show how you do it with lists

e.g. in Python

def shuffle(li):
    l = len(li)
    if l == 1: return li
    a = shuffle(li[:l//2])
    b = shuffle(li[l//2:])
    r = []
    while a or b:
        if random.random() <= len(a) / (len(a) + len(b)):
            r.append(a.pop())
        else:
            r.append(b.pop())
    return r

getting the length of a doubly linked list and splitting it up in two is O(n), but is only done once, not in a loop

@NathanMerrill what about nondeterministic runtimes?

there is a very elegant algorithm

quartata

@ArtOfCode Is there any limit on how long a name can be on QPixel?

ArtOfCode

@quartata I don't think so?

Nathan Merrill

@orlp nondeterministic maximum?

orlp

here's the algorithm

quartata

@ArtOfCode OK.

orlp

15:49

if the length of the list you're shuffling is 0 or 1 you're done

otherwise for every element you flip a fair coin, and put it in either list a or b

finally you shuffle list a and b recursively, and concatenate them

def shuf(l):
    if len(l) <= 1: return l
    a, b = [], []
    for e in l: random.choice([a, b]).append(e)
    return shuf(a) + shuf(b)

expected time is O(n log n), but worst case is O(n^2)

just like randomized quicksort

Nathan Merrill

you're using additional structures there

and I'm not sure you can simplify it to a single one

actually, yeah, you can. You just need two more pointers

orlp

@NathanMerrill I'm not

Nathan Merrill

I'm referring to a, b

orlp

a and b are just two pointers each to a tail/head of a list

Nathan Merrill

right

orlp

15:54

not an additional structure

think this algorithm should be even faster on average than the previous one

and the worst case is really, really unlikely

Nathan Merrill

and the worst case is a probabilistic unlikely, unlike a sorting algorithm that can reliably demonstrated to have a worse big-O

orlp

@NathanMerrill not randomized quicksort :)

but if the quicksort is not randomized, then yes

Nathan Merrill

I'm guessing randomized quicksort is just shuffle, then quicksort?

orlp

@NathanMerrill nope

randomized quicksort chooses a random pivot element at every recursive call

llvm.org/bugs/show_bug.cgi?id=20837

^ I still have an important open bug for clang's standard library for that btw

Nathan Merrill

Quicksort may take only $\Theta(n\log n)$ time in worst case if one employs a linear-time algorithm to find the median as the pivot. Of course, randomized quicksort has a better practical performance usually. — Bangye Jan 6 '15 at 19:04

orlp

16:03

@NathanMerrill sorry

I meant this

> unlike a sorting algorithm that can reliably demonstrated

Nathan Merrill

oh, I understand

I just found that comment, and thought it was interesting

orlp

you can't reliably demonstrate the worst case of randomized quicksort

ah

Nathan Merrill

I didn't know about that optimization to quicksort

orlp

it's not needed

Nathan Merrill

@orlp does your middle name start with L ?

orlp

16:06

@NathanMerrill one of mine does

I have multiple middle names

it's the L in orlp :)

Nathan Merrill

I know. I saw your name on the llvm link

and I guessed where OR and P came from, but I'm guessing now that I guessed wrong on the R

PhiNotPi

I made a room so that I don't have to worry about spamming everyone with lots of code/text.

Phi's Crafting Game

A room to discuss a new game involving resource-gathering/craf...

Nathan Merrill

bah, I hate being in multiple rooms

orlp

16:33

@NathanMerrill coliru.stacked-crooked.com/a/10a8ab71eee44c39

that's singly linked

Nathan Merrill

lol I wasn't actually expecting anybody to build it

orlp

but doubly linked is equally easy

Nathan Merrill

but awesome

yeah, I just said doubly linked because it makes some things easier

orlp

actually

@NathanMerrill I just thought of an O(n) algorithm with O(1) space if the element you're storing fits in a pointer

actually nvm

I thought of doing something smart

but it's still not random access memory

(I thought about storing extra information in the doubly linked pointer slot, and then restoring double links after the algorithm is done :P)

mınxomaτ

♪ ...fix n bugs, compile it again, n^2 bugs in the code... ♫

orlp

16:37

@mınxomaτ oh boy

repeated squarings

n^(2*k)

Nathan Merrill

@PhiNotPi is it possible to rank the candidates using Maximized Affirmed Majorities?

or does it only say who the top candidate is?

PhiNotPi

@NathanMerrill Yes, it's possible (it determines the top candidate by looking who's ranked first).

orlp

@NathanMerrill but what do you think of this algorithm?

I don't have a proof, but I really don't think it can be done in O(n)

Nathan Merrill

neither do I. I do like the two-pointer approach though

orlp

although you might want to post it to cs.stackexchange.com to maybe see if someone can prove that for you (but be prepared to be very specific about your memory limits, computation model and linked list, or it's impossible to answer)

mIllIbyte

16:50

Hi. I have answered a challenge, in C, using this as output format: f(a,b,c)int*b;{...} where f is called using only two arguments. I have copied this trick off someone else's answer to some different challenge. My question is: has anyone seen this used a lot in C answers - is it old hat? (Otherwise, I am going to search for that specific answer where I have seen it, to give credit to the author.)

orlp

@mIllIbyte what do you mean with output format?

mIllIbyte

I mean, instead of a return statement, you pass a pointer as the second argument when you call the function. That will contain the result after the function call is completed.

orlp

you sure you didn't mean f(a,b,c)int*c;{...}?

Nathan Merrill

@mIllIbyte writing out to an argument is valid

mIllIbyte

Yes, sure. You call f with only two arguments, and just use c as a local variable.

orlp

16:55

@mIllIbyte don't think that's really shorter though

f(a,b,c)int*c;{*c=...;}
f(a,b){return...;}

not without context at least

I can see some cases (like recursive functions or multiple return points) where it might be shorter

mIllIbyte

You save bytes because you don't have to declare c.

f(a,b,c)int*c;{*c=...;}

Oh, I see what you meant.

orlp

Magnets and Marbles !

►

3

Quill

15

Q: How to include a Lenny face in a LaTeX document? e.g. ( ͡° ͜ʖ ͡°)

How would one include a "classic" Lenny face in a LaTeX document? A paper is due tomorrow and I am curious. e.g. ( ͡° ͜ʖ ͡°) I have attempted to use the verbatim environment but it has proved fruitless.

trichoplax

17:12

Seriously?

Wow it was taken seriously too...

El'endia Starman

@Quill I like this one:

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

O-O

Quill

Chrome's Omnibox messes up the formatting like I haven't seen before

quartata

> You are now known as guest862c49ce47c55bcb61

I did something right

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

for what?

quartata

17:19

the qpixel nickserv

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

ah

epicTCK

anyone here know css?

@El'endiaStarman That does not look remotely like a lenny

It is a good smiley though

Adnan

@epicTCK a little bit

what's the question

epicTCK

Trying to show hide on mouseover, not working pastebin.com/sWdJzLxP

Adnan

maybe something like sho:hover { ... }?

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

17:33

^ that could work

Adnan

or use jquery

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

NO

quartata

@Adnan actual best solution

Adnan

jayqueuerey

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

DON'T BE DECEIVED

Adnan

17:34

hahaha

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

@quartata no

epicTCK

Not working....

quartata

They really should just build jQuery into V8 and Spidermonkey

Geobits

Great. Somehow lenny is even creepier than usual:

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

@quartata NO

quartata

17:35

@CᴏɴᴏʀO'Bʀɪᴇɴ it's not like they can make JS any worse

Adnan

@epicTCK What is <sho>Projects></sho>?

Is that a html tag?

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

@quartata sighs

quartata

@CᴏɴᴏʀO'Bʀɪᴇɴ well it's true

epicTCK

@Adnan No, custom tag b/c divs mess up the formatting

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

@quartata no.

epicTCK

17:35

Thats legal in HTML right.... ?

or am I thinking SGML

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

Yes, but not suggested.

IE won't like you.

But eh

epicTCK

dang all the 'ML's

Adnan

hahaha

epicTCK

So any more ideas?

Adnan

jquery has that built in I think

But I'm not a jquery expert

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

17:38

What are you trying to do?

quartata

9

A: show hide div on mouseover and mouseout

If you can wrap them in a common parent it is as simple with just CSS, no JavaScript is needed. CSS: #sidebar { display: none; } .cart:hover #sidebar { display:block; } HTML: <div class="cart"> <img src="images/cart.jpg" width="80px" height="30px" /> <div id="sidebar">some t...

New Main Posts

1

Q: Is the electric garage door open?

My electric garage door works like this: There is just one push button to control the door If the door is fully closed and I hit the button, the door starts to open. It takes 10 seconds to open fully If the door is fully open and I hit the button, the door starts to close. It takes 10 seconds...

code-golf

New Sandboxed Posts

17:49

0

A: Sandbox for Proposed Challenges

Shortest paths in a divisor graph code-golf number-theory graphs Introduction In this challenge, we will be dealing with a certain infinite undirected graph, which I call the high divisor graph. Its nodes are the integers starting from 2. There is an edge between two nodes a < b if a divides...

epicTCK

thought you all might get a kick out of this: splasho.com/upgoer5

zyabin101

Guys, today's new xkcd is interesting.

autoexec code posted by verified twitter users

epicTCK

Mouseover: autoexec code posted by verified twitter users

Nathan Merrill

18:06

GIF to XLS is the best one

epicTCK

i.imgur.com/eZly154.mp4

~~videos don't onebox... and I can't get a direct link...~~

Quill

in Tavern on the Meta on Meta Stack Exchange Chat, 2 hours ago, by Quill

> Predictive Touchpad

haha

Nathan Merrill

@PhiNotPi what's the purpose of the affirm function?

Aka, why can't I just sort based on preferences, then select the top user?

PhiNotPi

@NathanMerrill What do you mean by sort on preference?

Nathan Merrill

on your sandboxed post: why can't I stop at step 3?

2

A: Sandbox for Proposed Challenges

Implement the Maximize Affirmed Majorities voting system code-golf There are many different voting systems in existence. Different voting systems have different mathematical properties, which serve to describe the "positive features" of that system. Here is an informative list of these proper...

PhiNotPi

18:23

Let's say we have bots A, B, and C. If B always beats C, then B>C goes at the top of that list.

But, if A usually beats B, and also usually beats C, then A should the the winner.

B>C is affirmed first, then A>B, then A>C, giving a final order of A>B>C

Just because a given bot always beats some other bot, doesn't make that bot the best out of everyone.

Nathan Merrill

ok. So if I want to turn a "top candidate" algorithm into a "sorted candidates" algorithm, after I've run my affirm function, I need to find the top candidate(s), remove them, find the next candidate(s), and so on?

So, in the above example, I'd remove A

then find that B > C

PhiNotPi

@NathanMerrill Actually, I don't even think you need to do that. After affirming everything, you end up with a complete list of candidates.

Agawa001

C+ ?

Nathan Merrill

@PhiNotPi not from the algorithm AFAIK. The affirm() function basically returns a set of affirmed candidates, not in any particular order

PhiNotPi

@NathanMerrill Oh, I think I might have limited my sandbox post to the case of determinng the winner.

@NathanMerrill After running the affirm method, you should end up with a F(x,y) that indicates if candidate X finished strictly above candidate Y.

From that, you can deduce the entire ordering of candidates, including groups of candidates that tied.

The F() function is modified by affirm.

Nathan Merrill

18:38

right, so after the affirm function, I have a set of affirmations (pairs of <T, U> where T is affirmed over U)

so I just sort the candidates based on that set

what happens if when I compare(T, U), the set contains neither Pair<T,U> or Pair<U,T> exist?

or does that never happen?

@PhiNotPi ^

PhiNotPi

In that case, the candidates are tied, and you can use a tiebreaker.

Nathan Merrill

@PhiNotPi lets say that a<b and b<c. Are you also saying that the set will always contain a<c as well?

PhiNotPi

@NathanMerrill I think that is covered in this part of the affirm function:

> For each candidate A where X != A != Y

> recursive stuff here

Nathan Merrill

ok.

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

recursive course AN: teaches recursion. pre-reqs: recursive course AN+1

Nathan Merrill

18:46

^ why you always start your recursive functions with the base case

Quill

LOL

Eᴀsᴛᴇʀʟʏ Iʀᴋ

Hai

On mobile.

Nathan Merrill

@PhiNotPi thanks for your help. I think I got the new and improved MamTournament finished

Eᴀsᴛᴇʀʟʏ Iʀᴋ

Mam?

PhiNotPi

@NathanMerrill cool

Nathan Merrill

18:53

Maximized affirmed majorities

I changed it so that tournaments have to return a score for every player

Quill

@EᴀsᴛᴇʀʟʏIʀᴋ hello

Nathan Merrill

(or ranking)

Eᴀsᴛᴇʀʟʏ Iʀᴋ

@Quill hello to you.

Nathan Merrill

now, I've only got 1 left to update: Elimination Tournament

maybe I'll just remove it

its easily the most complicated and least useful

Quill

@EᴀsᴛᴇʀʟʏIʀᴋ hows goes the life of the cat with a scarf and hat

@QPaysTaxes did you just do like s/about/aboot/?

see you later

Eᴀsᴛᴇʀʟʏ Iʀᴋ

18:57

Goodbyes to you, @QPaysTaxes.

@Quill eh. Not really good day.

Quill

that sucks

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

@QPaysTaxes bai

quartata

19:10

@ArtOfCode Basically finished the IRC side of things

ArtOfCode

@quartata awesome, anything I need to do to deploy it? Or on the Rails side?

:D

shoot

@QPaysTaxes absolutely zero, I'm afraid

quartata

@ArtOfCode Yeah, there'll be some Rails side things. That's what I'm looking into now

ArtOfCode

cool

@QPaysTaxes WEBrick? It's actually not that bad. It used to be terrible, but it's not too bad any more.

true, but... eh

later

I can always put it on puma when I need to

Anonymous

@QPaysTaxes I'm half-decent at C++

New Sandboxed Posts

19:31

0

A: Sandbox for Proposed Challenges

Functional Programming in Your Language A lot of modern programming languages allow some form of functional programming, but I don't often see them used. I'm curious to see how different languages tackle problems that are naturally solved with some form of functional programming. The winning ent...

Anonymous

@QPaysTaxes Sure thing

Anonymous

Just invite me to a room when you're ready

trichoplax

20:20

I don't have a suggestion, but since the name clashes somewhat with the help tour, perhaps someone else could think of something catchy and meaningful? — trichoplax 2 mins ago

TimmyD

The PPCG Tour

trichoplax

Um, thanks :P

ArtOfCode

Community Picks

trichoplax

Ooh - that has promise

Ideally comment on the post so people can comment vote...

TimmyD

@trichoplax But if I do that, I'm subject to the judgment of my peers. Whereas here, all people can do is star.

3

Anonymous

20:25

Diamonds in the Rough

TimmyD

Most Significant Bits

trichoplax

@TimmyD Relax - comments only have upvotes... :)

@TimmyD Now that I like - I'd upvote it as a comment...

TimmyD

A Byte-size Jaunt

Eᴀsᴛᴇʀʟʏ Iʀᴋ

@Quill :D It got better.

@TimmyD stars are democracy incarnate

Eᴀsᴛᴇʀʟʏ Iʀᴋ

20:48

@TimmyD Mosibits, Minibits v2.0

Nathan Merrill

All of this naming is going to be useless if nobody posts any challenges for the Tour

Phi's Crafting Game

Transcript for