The Nineteenth Byte

@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?

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

define in-place

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

O(1), I believe

that's really really restrictive

for example quicksort is considered in-place

but is O(log(n))

3:02 PM

then what is "in-place"?

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

oh, the call stack

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

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

-.-

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)

3:04 PM

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

yes, but the call stack is another data structure

that's fine

so you've already eliminated non-tail recursive functions

so, define :P

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

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

3:06 PM

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

I would just say O(log n)

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

@NathanMerrill singly linked or doubly linked?

doubly

@NathanMerrill I don't think it's possible

it can be done in O(n log n)

how?

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

3:16 PM

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

then we can combine these lists by repeatedly tossing a coin

oh, you merge

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

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

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

@NathanMerrill I'm fairly positive

Kingspray Graffiti Simulator VR

3:19 PM

►

TimmyD

@orlp Looks like PowerShell thinks you're positive

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

@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

yeah I do

@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

3:25 PM

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

random access is O(n) though

3:40 PM

@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

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

ArtOfCode

@quartata I don't think so?

@orlp nondeterministic maximum?

here's the algorithm

@ArtOfCode OK.

3:49 PM

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

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

@NathanMerrill I'm not

I'm referring to a, b

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

right

3:54 PM

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

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

@NathanMerrill not randomized quicksort :)

but if the quicksort is not randomized, then yes

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

@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

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

4:03 PM

@NathanMerrill sorry

I meant this

> unlike a sorting algorithm that can reliably demonstrated

oh, I understand

I just found that comment, and thought it was interesting

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

ah

I didn't know about that optimization to quicksort

it's not needed

@orlp does your middle name start with L ?

4:06 PM

@NathanMerrill one of mine does

I have multiple middle names

it's the L in orlp :)

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

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...

bah, I hate being in multiple rooms

4:33 PM

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

that's singly linked

lol I wasn't actually expecting anybody to build it

but doubly linked is equally easy

but awesome

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

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... ♫

4:37 PM

@mınxomaτ oh boy

repeated squarings

n^(2*k)

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

or does it only say who the top candidate is?

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

@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)

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

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)

4:50 PM

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.)

@mIllIbyte what do you mean with output format?

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.

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

@mIllIbyte writing out to an argument is valid

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

4:55 PM

@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

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

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

Oh, I see what you meant.

Magnets and Marbles !

►

3

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

15

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

5:12 PM

Seriously?

Wow it was taken seriously too...

El'endia Starman

@Quill I like this one:

O-O

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

> You are now known as guest862c49ce47c55bcb61

I did something right

for what?

5:19 PM

the qpixel nickserv

ah

anyone here know css?

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

It is a good smiley though

@epicTCK a little bit

what's the question

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

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

5:33 PM

^ that could work

or use jquery

NO

@Adnan actual best solution

jayqueuerey

DON'T BE DECEIVED

5:34 PM

hahaha

@quartata no

Not working....

They really should just build jQuery into V8 and Spidermonkey

Geobits

Great. Somehow lenny is even creepier than usual:

@quartata NO

5:35 PM

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

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

Is that a html tag?

@quartata sighs

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

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

@quartata no.

5:35 PM

Thats legal in HTML right.... ?

or am I thinking SGML

Yes, but not suggested.

IE won't like you.

But eh

dang all the 'ML's

hahaha

So any more ideas?

jquery has that built in I think

But I'm not a jquery expert

5:38 PM

What are you trying to do?

A: show hide div on mouseover and mouseout

9

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

5:49 PM

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...

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

Mouseover: autoexec code posted by verified twitter users

6:06 PM

GIF to XLS is the best one

i.imgur.com/eZly154.mp4

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

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

> Predictive Touchpad

haha

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

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

@NathanMerrill What do you mean by sort on preference?

A: Sandbox for Proposed Challenges

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

2

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...

6:23 PM

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.

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

@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+ ?

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

@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.

6:38 PM

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 ^

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

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

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

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

> recursive stuff here

ok.

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

6:46 PM

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

LOL

Eᴀsᴛᴇʀʟʏ Iʀᴋ

Hai

On mobile.

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

Eᴀsᴛᴇʀʟʏ Iʀᴋ

Mam?

@NathanMerrill cool

6:53 PM

Maximized affirmed majorities

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

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

(or ranking)

@Quill hello to you.

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

@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ʀᴋ

6:57 PM

Goodbyes to you, @QPaysTaxes.

@Quill eh. Not really good day.

that sucks

@QPaysTaxes bai

7:10 PM

@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