« first day (1364 days earlier)      last day (3521 days later) » 
00:00 - 14:0014:00 - 21:00

12:00 AM
Well damn. Instead of getting sweet solar eclipse pictures this evening, I find out my camera's busted.
there's a solar eclipse?
Was, but I'm not sure if it was visible where you're at. It barely was here just before sunset.
About 2 hours ago.
yeah it's been dark for about 6 hours now
I assume it was dark there :P
how eclipsed was it?
12:02 AM
Here, maybe 15-20%, not much. Further north it was moreso, but I don't think it was more than 75% anywhere.
It just looked like someone nibbled the sun's right side a bit.
Q: Book Stack Sort

Martin BüttnerWhen stacking books you usually want to put the largest ones at the bottom and the smallest ones at the top. However, my latent OCD makes me feel very uneasy if I've got two books where one is shorter (in height) but wider than the other. No matter which order I place them in, the top book will e...

I hate electronics sometimes. I've had every visible screw on this casing removed for about 15 minutes now and I have no idea why it won't open ><
try the soldering iron
I don't usually solder plastic, but maybe....
I hate Ryanair... the planes back from Germany go so ridiculously late... usually you're back just in time to catch the last tube through the city to get home... but today, for some reason, the plane is even later, and my girlfriend won't arrive in central London before 2am... and then there's still the night bus home after that... that's just ridiculous.
12:16 AM
I think I've only flown them once, but not that route. Don't remember it much, so mine must not have been that bad.
they are the cheapest of the cheap airlines over here... and not "cheap" as in "inexpensive"... just cheap :D
did you guys see Wumpus's revealed solution to the regex cops'n'robbers challenge? it's pretty awesome... such a shame no one figured that out. codegolf.stackexchange.com/a/40033/8478
@Geobits that answer on skeptics did get deleted
a shame I don't have enough rep to see it and the other comments it certainly got
well, I've got to head off and pick up the girlfriend from the airport transfer... see you
12:32 AM
Is there a meta post that lists all the valid types of challenges or am I imagining things?
@Calvin Is this post the one you mean?
@Geobits Thank you!
1:02 AM
@MartinBüttner So my new camera will be here Saturday. Hopefully you have better luck with your plans for tonight :)
2 hours later…
2:40 AM
Q: We Have a Messy Sandbox

Calvin's HobbiesIt may be just me, but it seems kind of bothersome that we have 500-odd undeleted answers in the Sandbox. Many of them have already been posted for real but not edited to reflect that. More (I think it's more) have been abandoned and are unlikely to ever be revived. (I've almost never seen an aba...

4 hours later…
6:46 AM
A: Sandbox for Proposed Challenges

Beta DecayPowers of Ten code-golfmath Challenge Every real number can be represented as a power of ten. For example, 100 can be represented as 102 and 20 can be represented as 101.30102999566. Your challenge is to write a program which calculates the power of ten representation of a number supplied by ...

7:03 AM
Huzzah I wrote a Stack Snippet to write a Stack Snippet [/meta]
@Geobits Plastic clips.
7:30 AM
Can someone look at my proof for the book stack sort? I don't really know what I'm doing.
i'm reading through it now
i believe your method is optimal
there is a part of the proof that i'm sketchy about though: that if the new book can't fit on any pile, then an additional pile is required
of course, it's required with the current collection of piles, but something stronger is needed. maybe there was another way to split the books up to now into piles that would allow this one to be tacked on
there's a crucial aspect in your algorithm that you're not using in your proof
that each book that can be added to a pile is not just added to any pile that works
but to the earliest-started pile that works
here's an example
Something like [(5, 5), (4, 6), (3, 3), (2, 6)]?
say you have books [(4,2),(3,4),(2,1),(1,3)]
yup, your example is just like mine
So with both these examples we want to put new books on the pile of smallest height - will that always be the case?
If so then that's just a small modification
not on the pile of smallest height, but the first pile to be created
as your algorithm already does
the first one listed in P
or, wait, what do you mean by "height"?
7:44 AM
Oh, nvm - every new pile has greater book height, so first pile is equivalent to smallest height :P
book height = height of top book?
Yeah, that. Sorry, didn't make that clear
@grc ping, we're discussing your proof
Hm... That makes sense, I think. So we need to place it on the pile with smallest height, in case subsequent books have a greater height?
and thanks for your help
yes, though your algorithm already achieves this by placing it on the earliest-listed pile in P
your proof needs to somehow use this crucial fact though
7:53 AM
would it be enough to assume that each book has been placed on the smallest pile (by height) possible?
to be clear, smallest pile by height means the pile whose top book has the smallest height?
of all top books
yes, and it's always the case the piles in order of creation are the same as the piles in descending order of top-book height
thanks, I'll try to fix my proof
8:06 AM
A: Sandbox for Proposed Challenges

maf-soft Calculate the Delacorte Number of a square (code-golf, math) Read and unterstand how a Delacorte Number is calculated, then implement it in any language. Shortest code wins. You can choose how to handle input and output and you don't have to count the necessary framework of your language, li...

8:25 AM
@grc I'm still not sold on your proof unfortunately
@xnor yeah it doesn't feel right to me either
let me take a step back and say what the gap is
do you reckon it would help to split case 1 up and elaborate on when we have a choice of piles?
i don't yet know how to fix the proof, so I don't know
you're showing that if the solution is optimal for the first k books, then it's optimal for the first k+1 books
let's say the first k books are in p piles
if the (k+1)-st book can be added on top of these piles, the new solution is still optimal since adding books can only hurt
the hard part is to show that if it can't, then p+1 piles are required
note that it doesn't suffice to say that it can't be added to any of the p existing piles since there might have been another p-pile solution for the first k books that would have allowed it
makes sense?
yes, but I think you've slightly misunderstood case 3
*case 2
8:39 AM
oh, yes?
do you agree that the width is strictly lower and height strictly greater than all other books in the piles?
i agree that the width of the new book is lower that the width of any book in any other pile
since we're going through the books by decreasing width
i don't agree though that its height is greater than all previously encountered books
only that it's greater than any previously encountered book that's currently on top of a pile
*height is greater than
But the piles are descending in both height and width as you go up the pile?
yes, but that's exactly bad
the current book's height is greater than that of any book on a top of a pile
but tops of piles have small height
my bad - I think I messed the height thing up
8:42 AM
yes, it's the change from smallest to greatest that makes it no longer work
here's an example where the proof fails: (3, 5), (2, 2), (1, 4)
but there's something about sorting the books first which makes it impossible (?) to find a case that breaks the implementation
Assume we have a book we can't fit on any pile. If we can rearrange the books so that we can fit the new book in without introducing a new pile, we have two cases:
1) all top books of each pile are in different piles after rearranging - impossible since we're assuming we can't fit the new book in
2) two of the top books are in the same pile after rearranging - <why is this impossible?>
i see, that proof would work if you can contradict subcase 2
I'm thinking it's something to do with the fact that we pick the pile with the smallest top-book height, because that maximises (I think?) the top-book areas
I guess that could be part of the induction - assume we have k books in minimal number of piles AND maximal top-book areas
You'd need to show there's a unique meaning of "maximal" though, because the books themselves can't be ordered totally (e.g. (3,2), (2,3))
9:01 AM
i think i have a proof but it's fairly involved
give me a few minutes to check it
ok, i think it's good
let me try to give it
i'd like you guys to stop me if anything is unclear lest I go off into something ambiguous or incorrect
kk :)
ok, cool
first, let me define the notion of an antipile
an antipile is a sequence of books of decreasing height, but increasing width
so, each successive book is strictly taller but strictly less wide
makes sense?
9:08 AM
not that any book in an antipile overhangs over any other book in an antipile
so, no two books within an antipile can be in the same pile
as a consequence, if you can find an antipile of x books, then those books must be in different piles
is it clear why?
Yep, makes sense
so, the size of the largest antipile is a lower bound on the number of piles
so, if you can find an antipile of 5, any solution must use at least 5 piles
and therefore, if you find a 5-pile solution, you know it's optimal
so what I'm going to try to prove is that in grc's construction, one can make an antipile by taking one book from each pile
it would have to be the top book I think
and therefore, no construction can have fewer piles
what would have to be the top book?
9:13 AM
Yeah the top books work, don't they
wait - did you mean taking any book from each pile?
or just one specific book
They decrease in width because you're processing them in decreasing width, but they increase in height as well
the top books of every pile don't necessarily form an antipile
consider piles [(2,3), (1,1)] and [3,2]
the bottom books of each pile also don't necessarily form an antipile
With grc's algorithm that'd become [(3,2), (1,1)] [(2, 3)] though
oh, my mistake
but the claim is still true
(1,1) and (2,3) are not an antipile
9:15 AM
Oh... point
this is the hard part of the proof, finding a way to take one book from each pile to make an antipile
k yep, continue?
ok, you're convinced that if this can be done, grc's algorithm is optimal?
let's paint red the books we want to be in our antipile
so one from each pile
when i say "first pile", i mean the first one to be started
so paint red the top book from the last pile
we're going to go down the piles in reverse order of creation
in each one, we're going to need to find a book that's less tall and more wide than the last book we painted red, and paint that book red
i claim that we can't fail to do this even if we pick arbitrarily
just paint any book that works
what i need to prove though is that there's always one that works
(pause for questions)
9:20 AM
Well I guess if you're looking for a book that's more wide in an earlier-formed pile, that'd be books near the bottom of the pile added before the last one you painted red?
yes, but the hard part is that that book must also be less tall
that's the part I'll try to prove next
k, will be interested to see how this goes :)
grc, are you with me?
I think the top books form an antipile at the time you create a new pile
hmm, if that's true, it would certainly simplify the proof
9:23 AM
wait nvm
I think it's more like "the top book for a 2-book antipile individually with each top book at the time you create a new pile"
go on
oh, nope, take [(3,2), (1,1)] [(2, 3)], [(0,0)]
There's no guarantee the other books do too
ok, cool
9:23 AM
s/the top book for/the new book forms
so say we've painted books red in pile p,p-1, p-2, up to pile i
and we want to paint red a book in pile i-1
that book must be both wider and less tall than the previous book
now, note that the base of pile i-1 is wider than the previous book
because it is wider than the base of pile i
and the base of pile i is wider than any book in pile i
suppose for contradiction that every book in pile i-1 is either taller or less wide that the last red-painted book
let's look at the state of the world at the time the last red-painted book was added
(more pause)
The last red book B would form a 2-book antipile with the book that was on top of pile i-1 at the time B was added...
yes, that's exactly what I wanted to show next
And since we're increasing in width and decreasing in height, it also antipiles with all other red books so far?
to spell it out
since we add books in order of decreasing width, book B must be less wide than that book
and since it was not chosen to go on top of that book, but rather on a different pile, it cannot also be less wide
thank-you, that way of putting it is cleaner than the contradiction i was going for
it also gives a construction
form the antichain by starting with the last book to be added
and repeatedly adding new books to the antichain as follows
9:30 AM
*cannot also be less tall
take the previous book in the antichain, go back in time when it was added, and take book that was at the top of the pile before it
I'm pretty convinced that works :)
grc, how are you with this?
so the requirement that we put the book on the earliest pile possible is used for the last step?
slowly trying to get my head around it, but it looks good
yes, lemme think exactly where
ah, yes
let B be a red-painted book in pile i, and we're trying to find a book to paint red in pile i-1
we go back time to when book B was added
at which point B is the least wide book we've encountered up to then
when we say that the top book of the pile before B must be less tall than B
it's because if it were more tall, book B could go on top of it
and would have due to the "earliest pile rule"
the fact that it didn't is how we know it must be less tall
and hence can be painted red and extend the antipile
9:46 AM
To give an explicit example, if we go back to [(5, 5), (4, 6), (3, 3), (2, 6)] and stack it without "earliest pile" like this: [(5, 5)] [(4, 6), (3, 3)] [(2, 6)] then we'd paint (3, 3) and (2, 6) red, but from (3, 3) we can't paint (5, 5) red. Note that the difference between this and the proof is that in the proof, since we did earliest pile, we "couldn't" put B on any previous pile, but here we're "choosing not to" put (3, 3) on (5, 5).
I'm trying to associate the proof with each part of the algorithm :)
is this a correct summary?
we have i piles
we add a book B to the first pile it can fit or create a new one
B is either in the first pile or it forms an antipile with the last book P on the previous pile because:
-B is smaller in width than P (since books are sorted in descending order)
-B is greater in height than P (or we would have placed B on P)
this chains with P's antipile to form an antipile of length i
we therefore have an optimal number of piles
10:02 AM
i'm not sure that works
it shows that B and P form an antipile of size 2
but how down you know that P was already in an antipile of size i?
B doesn't necessarily end up on the first pile...
we know from induction that there is some antipile of size i in the first i piles, but not (as far as i see) that it contains P
and an arbitrary book B you add might not be included in any maximal-size antipile
sorry I don't mean i, I mean the pile number that B is on
rather, once all the books are added and all the piles are made, we can find a maximal-size antipile in retrospect
any arbitrary book B in pile x is in an antipile of length x, since it can be chained with P in the previous pile, which has an antipile length of x-1
10:09 AM
hmm, here's a counterexample
[(3,2), (1,1)] [(2, 3)]
(1,1) is not part of any size-2 antipile
(1, 1) is in pile 1, and therefore you can construct an antipile of length 1 from it
oh, i see
Why sort by decreasing width?
If B is red in pile i then we know that the book B' which was on top of pile i-1 when B was placed is at least as wide as B.

Why earliest pile?
So we know that when we added B to pile i, it could not be placed on top of the book B' which was on top of pile i-1 at the time (otherwise we might have the case that B could have been put on B', but we chose not to). Note that since B' is at least as wide as B by above, so B' must also be strictly less tall as otherwise B could be placed on B'.
^^ I think? (I was trying to make clear what happens if you have books of the same height/width)
ok, grc, i think that works and is much simpler than what I was doing
@Sp3000 yeah that makes good sense
10:12 AM
@xnor It is what you are doing :P You still need to explain why we want strictly wider and strictly less tall (i.e. antipiles)
we can think of each book as pointing to the one that, when it was being placed, was on top of the pile before the one it was placed it
wait, was the movitation for antipiles not clear?
No, I just mean what I wrote isn't a full proof :P
let me finish say out loud the cleaner replacement for "painting red"
whenever you place a book on top of a pile, make a permanent pointer from it to the book on top of the pile right before it
(except for books in the first pile)
each book points to a book that is wider that in and less tall than it
and is in the previous pile
so once we're done, taken any book in the last pile, follow the pointers, and we get an antipile containing as many books as there are piles
and so there can be no solution with fewer piles, since it would have to have a pile with two books from the old antipile, a contradiction
This is getting neater by the minute - gimme a few minutes, wanna do something :D
(this is the same argument, but made cleaner by grc's inductive claim)
@MartinBüttner we've had a long party of proving grc's algorithm
10:18 AM
@MartinBüttner Excellent timing - xnor's just proven grc's book stack algorithm :D
and "just" means "explaining it over the last hour" :-P
though it's becoming simpler
and you were successful?
we think so
10:19 AM
yeah I think we're all on the same page now :)
I'm trying to draw up a diagram, just to make things super clear
I'll read the transcript later
@MartinBüttner i think the key claim is this
say you have k books, any two of which overhang each other
so, sorting them by height is the same as sorting them by reverse width
then, you must have at least k-1 overhangs
because between any two such books must be an overhang
but the interesting thing is that as long as you can find only k such books, you can achieve exactly k-1 overhangs
and grc's algorithm does this
I'm not sure what to say to isaacg's submission... usually taking another user's approach and golfing it in another language isn't too much frowned upon... but in a challenge where coming up with the algorithm is decidedly nontrivial, that's kinda rude.
10:24 AM
i think it's fine
the same thing happened in codegolf.stackexchange.com/a/37863/20260
and was accepted
many accepted answers are "the best algorithm/code converted to golfscript/cjam/pyth"
user image
Following any red path from right to left forms an antipile!
@xnor well that one got you a populist badge ;)
(think this would be better as an animated gif but I'm lazy)
@MartinBüttner I don't know anything about Pyth, but looking at the translated code it wouldn't work
wow, nice diagram
10:29 AM
so he hasn't tested it at all
how did you make it that fast?
Flash :P
@grc you might want to comment on that then, because I don't feel like downloading pyth right now... might do that over the weekend if he claims it's correct
you don't have to download pyth, there's a link to run it somewhere
i.e. a link with the python code for pyth in an online editor where you paste the pyth code into STDIN and it outputs the result
in any case, i think it's clear isaacg can fix his Pyth code to be a shorter version of grc's
10:35 AM
@MartinBüttner Diagram explanation: Each red line joins a book to the book which was on top of the previous pile when it was added. By grc's algorithm, this previous-pile book must be strictly wider and strictly less tall.
(piles are left to right)
(and contain books that are stacked on top of each other without overhangs)
I see, thanks. I'll read through the transcript later so I can really follow.
(err, each pile is bottom to top)
Pick a book on the last pile and following a path from right to left gives a subset of books where no two can be in the same pile
Man, I'm almost of the opinion that xnor should post something as well just so I have something to upvote :P
yeah I might try to write up the proof in my answer now, but I think @xnor and @Sp3000 deserve rep
so if either of you want to post a proof or something?
10:42 AM
well xnor had his own algorithm ;) ... while it won't beat yours at golfing it would be nice to see it an answer for more diversity of approaches
Woah, nice concept of antipile
@grc thanks, but you're welcome to write it up as well
i'm not sure i'll have more time this weekend
@MartinBüttner writing the reduction to max flow sounds painful. it's much easier to cite the result from wikipedia than to code it. so sorry, i probably won't be answering, especially now that grc has posted a much better algorithm
@justhalf it's the antichain from the theory of posets
In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two elements in the subset are incomparable. (Some authors use the term "antichain" to mean strong antichain, a subset such that there is no element of the poset smaller than two distinct elements of the antichain.) Let S be a partially ordered set. We say two elements a and b of a partially ordered set are comparable if a ≤ b or b ≤ a. If two elements are not comparable, we say they are incomparable; that is, x and y are incomparable if neither x ≤ y nor y ≤ x. A chain in S is a subset...
also, isaacg's pyth translation is correct
it's just the conversion to python that's buggy
I have to say, @MartinBüttner, great way of introducing posets into a problem. It made is a lot more interesting
10:45 AM
eval(input()) should be input() for python 2
@Sp3000 So this is the final piece of truth that put all the proof in place?
sum needs a second arg of []
(the pyth sum handles lists, automatically, i believe)
and the initialization Y=[] needs to be included
@Sp3000 that's totally what I had in mind when I first thought of the challenge ;)
eval(input()) looks more like Python 3 to me
@xnor ah okay
10:46 AM
@Sp3000 oh, that makes sense
@justhalf What's the final piece of truth?
i was also inspired by the reduction to max flow that I originally thought of
the antichain is the min cut
that limits the size of the "max flow" (number of piles)
@Sp3000 posts with a little arrow on the left are in response to specific messages. you can see said message by clicking on that arrow ;)
(unless you're on mobile I guess)
@Sp3000: It seems that that comment of yours finalize the proof?
@MartinBüttner: Oh, I didn't consider that possibility that he misunderstood my comment, haha
Oh, I didn't know you could do that. Or edit messages either. :P [/new to chat]
10:51 AM
@Sp3000: I'm also new to chat! I've never got the chance to see people online like now!
Too bad I need to go now
@justhalf Oh well... maybe? I thought it'd be better for my brain if I tried to explicitly figure out why each step of grc's algorithm was important by linking it to xnor's proof, and that was the result
Hence the diagram too, thought it'd make more sense if I had a concrete example
the idea i find helpful is to link each book to its "predecessor" as soon as it's placed
rather than waiting for all of them to be placed, then going back in time
Yeah, that's certainly easier to explain :P It's like doing a delta-epsilon proof, and then changing all your epsilons to epsilon/3 after you're done because you realise that you ended up with 3*epsilon at the end
i think it's exactly what we just proved
but for general posets
@xnor wow
10:55 AM
yup, it's exactly the result
and moreover, dilworth's theorem is stated to be equivalent to Konig's Theorem, which is the basis of the reduction i had given Martin Büttner
So what you mean is, minimum number of chains is just the number of piles in our problem, right?
@xnor you should definitely add your name to the wikipedia page
64 years too late unfortunately
yes, chain = pile, antichain = antipile
anyway, i should sleep, good night
it's been fun
good night and thanks again :)
Fun extension question: Does the algorithm still work if we allow rotations
(ie sort by max(width, height) first, then tiebreak by min(width, height))
11:03 AM
@grc if your algorithm remains the only valid one used in the challenge, and everyone just golfs that, I'll give you a bounty after I've hit 20k ;)
@MartinBüttner wow, congrats in advance on 20k rep (and almost all of it this year!)
thanks ;) ... I get addicted to things... SO went even quicker
Talk about it, I'm supposed to be doing assignments and here I am discussing book stacking
yeah, I've got exams soon as well...
but maybe there will be a question on book stacking?
damn... when I bought my PS3 I got the cheap one with the 12GB hard drive, because I thought "yeah I only need one game installed on it at a time, so that's enough"... now they released a game today that needs 11.3GB of memory.... even if I throw out all the games, I won't get more than 9 available...
11:37 AM
@Sp3000 do you mind if I use your diagram in my answer?
@grc Go for it - that's what I made it for :P
12:00 PM
@Sp3000 thanks
I've updated my post (hopefully it makes sense)
@grc Did you simplify your algorithm's explanation? You might want to expand that "descending order" means "by width, tiebroken by height", for example
You mention it in your proof but not in your algorithm
Also, a bit of a nitpick, but you don't have to isolate putting B on the first pile as a separate case - you can just say earliest pile (as you have in point 2) to simplify the explanation a bit :)
I've updated the algorithm explanation
I'm not sure step 3/4 would make sense if I removed step 1
I suppose I could add the first pile case as an alternative in step 3
Oh I see what you mean, nevermind :)
But yeah time complexity sounds like O(n^2) to me - O(n log n) sort + O(n) book placements * O(n) to place each book in the worst case :) nicely done
12:17 PM
@Sp3000 thanks - I still find time complexity a bit confusing and arbitrary
Hm? How so?
choosing which operation to count for any non-trivial algorithm is what I don't really get
Oh, I see
12:52 PM
@PeterTaylor Yea, there were a few clips I got to, but there was still something I couldn't see/manipulate in the hot shoe area that wouldn't budge.
1:45 PM
I just found the most curious way to validate input I've ever seen in my company's code:
private bool isValid(string[] parameters)
    foreach (string parameter in parameters)
        switch (parameter)
        case "Foo":
        case "Bar":
        case "Baz":
            return false;
    return true;
Ugh I butchered that way too much after renaming all of the variables
Somehow I feel terrible for not seeing anything wrong with that - is it just me?
I suppose it might be quicker than keeping a list/set of valid params and checking contains() or equivalent each time.
Surely that's an actual bottleneck based on testing ;)
Oh I know Linq is probably not meant for high performance use cases, but we're checking a list of parameters in a URL here
return parameters.Concat(validParams).Except(parameters.Intersect(validParams)).Count == 0;
Ok that's not prettier than how they did it. Ignore me.
I guess it just looked weird at first, but it's not actually that weird.
It's probably not how I'd have written it, but it doesn't seem terrible.
HAHAHA! I started looking for a weird code construct I found years ago and instead I found this beautiful thing:

This was found in the 2004 leaked Windows sources
__inline BOOL
                  IN  LPSTR Directory,
                  IN  LPSTR FileToFind,
                  IN  LPSTR SourceFullName,
                  IN  LPSTR SourceFilePart,
                  OUT PBOOL FoundInTree
    // This was way too slow. Just say we didn't find the file.
00:00 - 14:0014:00 - 21:00

« first day (1364 days earlier)      last day (3521 days later) »