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

Geobits
Geobits
12:00 AM
Well damn. Instead of getting sweet solar eclipse pictures this evening, I find out my camera's busted.
 
Martin Büttner
Martin Büttner
there's a solar eclipse?
 
Geobits
Geobits
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.
 
Martin Büttner
Martin Büttner
yeah it's been dark for about 6 hours now
 
Geobits
Geobits
I assume it was dark there :P
 
Martin Büttner
Martin Büttner
how eclipsed was it?
 
Geobits
Geobits
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.
 
Martin Büttner
Martin Büttner
lol
0
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...

code-golf sorting array-manipulation
 
Geobits
Geobits
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 ><
 
Martin Büttner
Martin Büttner
try the soldering iron
 
Geobits
Geobits
I don't usually solder plastic, but maybe....
 
Martin Büttner
Martin Büttner
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.
 
Geobits
Geobits
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.
 
Martin Büttner
Martin Büttner
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
 
Geobits
Geobits
Aww...
 
Martin Büttner
Martin Büttner
well, I've got to head off and pick up the girlfriend from the airport transfer... see you
 
Calvin's Hobbies
Calvin's Hobbies
12:32 AM
Is there a meta post that lists all the valid types of challenges or am I imagining things?
 
Geobits
Geobits
@Calvin Is this post the one you mean?
 
Calvin's Hobbies
Calvin's Hobbies
@Geobits Thank you!
 
Geobits
Geobits
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…
New Meta Posts
New Meta Posts
2:40 AM
1
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...

discussion sandbox
 
 
4 hours later…
New Sandboxed Posts
New Sandboxed Posts
6:46 AM
0
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 ...

 
Sp3000
Sp3000
7:03 AM
Huzzah I wrote a Stack Snippet to write a Stack Snippet [/meta]
 
Peter Taylor
Peter Taylor
@Geobits Plastic clips.
 
grc
grc
7:30 AM
Can someone look at my proof for the book stack sort? I don't really know what I'm doing.
 
xnor
xnor
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
 
Sp3000
Sp3000
Something like [(5, 5), (4, 6), (3, 3), (2, 6)]?
 
xnor
xnor
say you have books [(4,2),(3,4),(2,1),(1,3)]
yup, your example is just like mine
 
Sp3000
Sp3000
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
 
xnor
xnor
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"?
 
Sp3000
Sp3000
7:44 AM
Oh, nvm - every new pile has greater book height, so first pile is equivalent to smallest height :P
 
xnor
xnor
book height = height of top book?
 
Sp3000
Sp3000
Yeah, that. Sorry, didn't make that clear
 
xnor
xnor
@grc ping, we're discussing your proof
 
grc
grc
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
 
xnor
xnor
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
 
grc
grc
7:53 AM
would it be enough to assume that each book has been placed on the smallest pile (by height) possible?
 
xnor
xnor
to be clear, smallest pile by height means the pile whose top book has the smallest height?
of all top books
 
grc
grc
yes
 
xnor
xnor
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
*ascending
 
grc
grc
thanks, I'll try to fix my proof
 
New Sandboxed Posts
New Sandboxed Posts
8:06 AM
0
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...

 
xnor
xnor
8:25 AM
@grc I'm still not sold on your proof unfortunately
 
grc
grc
@xnor yeah it doesn't feel right to me either
 
xnor
xnor
let me take a step back and say what the gap is
 
grc
grc
do you reckon it would help to split case 1 up and elaborate on when we have a choice of piles?
 
xnor
xnor
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?
 
grc
grc
yes, but I think you've slightly misunderstood case 3
*case 2
 
xnor
xnor
8:39 AM
oh, yes?
 
grc
grc
do you agree that the width is strictly lower and height strictly greater than all other books in the piles?
 
xnor
xnor
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
 
Sp3000
Sp3000
But the piles are descending in both height and width as you go up the pile?
 
xnor
xnor
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
 
grc
grc
my bad - I think I messed the height thing up
 
xnor
xnor
8:42 AM
yes, it's the change from smallest to greatest that makes it no longer work
 
grc
grc
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
 
Sp3000
Sp3000
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?>
 
xnor
xnor
i see, that proof would work if you can contradict subcase 2
 
Sp3000
Sp3000
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))
 
xnor
xnor
9:01 AM
i think i have a proof but it's fairly involved
 
Sp3000
Sp3000
Oh?
 
xnor
xnor
give me a few minutes to check it
ok, i think it's good
let me try to give it
@grc
i'd like you guys to stop me if anything is unclear lest I go off into something ambiguous or incorrect
 
Sp3000
Sp3000
kk :)
 
grc
grc
okay
 
xnor
xnor
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?
 
grc
grc
9:08 AM
yes
 
xnor
xnor
ok
not that any book in an antipile overhangs over any other book in an antipile
*note
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?
 
Sp3000
Sp3000
Yep, makes sense
 
xnor
xnor
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
 
grc
grc
it would have to be the top book I think
 
xnor
xnor
and therefore, no construction can have fewer piles
what would have to be the top book?
 
Sp3000
Sp3000
9:13 AM
Yeah the top books work, don't they
 
grc
grc
wait - did you mean taking any book from each pile?
or just one specific book
 
Sp3000
Sp3000
They decrease in width because you're processing them in decreasing width, but they increase in height as well
 
xnor
xnor
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
 
Sp3000
Sp3000
With grc's algorithm that'd become [(3,2), (1,1)] [(2, 3)] though
 
xnor
xnor
oh, my mistake
but the claim is still true
(1,1) and (2,3) are not an antipile
 
Sp3000
Sp3000
9:15 AM
Oh... point
 
xnor
xnor
this is the hard part of the proof, finding a way to take one book from each pile to make an antipile
 
Sp3000
Sp3000
k yep, continue?
 
xnor
xnor
ok, you're convinced that if this can be done, grc's algorithm is optimal?
 
grc
grc
yes
 
xnor
xnor
cool
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)
 
Sp3000
Sp3000
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?
 
xnor
xnor
yes, but the hard part is that that book must also be less tall
that's the part I'll try to prove next
 
Sp3000
Sp3000
k, will be interested to see how this goes :)
 
xnor
xnor
grc, are you with me?
 
grc
grc
I think the top books form an antipile at the time you create a new pile
maybe
 
xnor
xnor
hmm, if that's true, it would certainly simplify the proof
 
grc
grc
9:23 AM
wait nvm
 
Sp3000
Sp3000
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"
 
grc
grc
go on
 
xnor
xnor
oh, nope, take [(3,2), (1,1)] [(2, 3)], [(0,0)]
 
Sp3000
Sp3000
There's no guarantee the other books do too
 
xnor
xnor
ok, cool
 
Sp3000
Sp3000
9:23 AM
s/the top book for/the new book forms
 
xnor
xnor
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)
 
Sp3000
Sp3000
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...
 
xnor
xnor
yes, that's exactly what I wanted to show next
 
Sp3000
Sp3000
And since we're increasing in width and decreasing in height, it also antipiles with all other red books so far?
 
xnor
xnor
yes
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
 
Sp3000
Sp3000
9:30 AM
*cannot also be less tall
 
xnor
xnor
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
 
Sp3000
Sp3000
I'm pretty convinced that works :)
 
xnor
xnor
yay!
grc, how are you with this?
 
grc
grc
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
 
xnor
xnor
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
 
Sp3000
Sp3000
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 :)
 
grc
grc
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
 
xnor
xnor
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?
 
Sp3000
Sp3000
B doesn't necessarily end up on the first pile...
 
xnor
xnor
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
 
grc
grc
sorry I don't mean i, I mean the pile number that B is on
 
xnor
xnor
rather, once all the books are added and all the piles are made, we can find a maximal-size antipile in retrospect
 
grc
grc
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
 
xnor
xnor
10:09 AM
hmm, here's a counterexample
[(3,2), (1,1)] [(2, 3)]
(1,1) is not part of any size-2 antipile
 
grc
grc
(1, 1) is in pile 1, and therefore you can construct an antipile of length 1 from it
 
xnor
xnor
oh, i see
 
Sp3000
Sp3000
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)
 
xnor
xnor
ok, grc, i think that works and is much simpler than what I was doing
 
grc
grc
@Sp3000 yeah that makes good sense
 
Sp3000
Sp3000
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)
 
xnor
xnor
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?
 
Sp3000
Sp3000
No, I just mean what I wrote isn't a full proof :P
 
xnor
xnor
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
 
Sp3000
Sp3000
This is getting neater by the minute - gimme a few minutes, wanna do something :D
 
xnor
xnor
(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
 
Sp3000
Sp3000
10:18 AM
@MartinBüttner Excellent timing - xnor's just proven grc's book stack algorithm :D
 
xnor
xnor
and "just" means "explaining it over the last hour" :-P
 
Martin Büttner
Martin Büttner
lol
 
xnor
xnor
though it's becoming simpler
 
Martin Büttner
Martin Büttner
and you were successful?
 
xnor
xnor
we think so
 
grc
grc
10:19 AM
yeah I think we're all on the same page now :)
 
Martin Büttner
Martin Büttner
cool
 
Sp3000
Sp3000
I'm trying to draw up a diagram, just to make things super clear
 
Martin Büttner
Martin Büttner
I'll read the transcript later
 
xnor
xnor
@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
 
Martin Büttner
Martin Büttner
interesting
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.
 
xnor
xnor
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"
 
Sp3000
Sp3000
user image
2
Following any red path from right to left forms an antipile!
 
Martin Büttner
Martin Büttner
@xnor well that one got you a populist badge ;)
 
Sp3000
Sp3000
(think this would be better as an animated gif but I'm lazy)
 
grc
grc
@MartinBüttner I don't know anything about Pyth, but looking at the translated code it wouldn't work
 
xnor
xnor
wow, nice diagram
 
grc
grc
10:29 AM
so he hasn't tested it at all
 
xnor
xnor
how did you make it that fast?
 
Sp3000
Sp3000
Flash :P
 
Martin Büttner
Martin Büttner
@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
 
xnor
xnor
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
 
Martin Büttner
Martin Büttner
sure
 
Sp3000
Sp3000
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.
 
xnor
xnor
(piles are left to right)
(and contain books that are stacked on top of each other without overhangs)
 
Martin Büttner
Martin Büttner
I see, thanks. I'll read through the transcript later so I can really follow.
 
xnor
xnor
(err, each pile is bottom to top)
 
Sp3000
Sp3000
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
 
grc
grc
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?
 
Martin Büttner
Martin Büttner
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
 
justhalf
justhalf
Woah, nice concept of antipile
 
xnor
xnor
@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
Antichain
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...
 
Martin Büttner
Martin Büttner
understandable
 
xnor
xnor
also, isaacg's pyth translation is correct
it's just the conversion to python that's buggy
 
Sp3000
Sp3000
I have to say, @MartinBüttner, great way of introducing posets into a problem. It made is a lot more interesting
 
xnor
xnor
10:45 AM
eval(input()) should be input() for python 2
 
justhalf
justhalf
@Sp3000 So this is the final piece of truth that put all the proof in place?
 
xnor
xnor
sum needs a second arg of []
(the pyth sum handles lists, automatically, i believe)
and the initialization Y=[] needs to be included
 
Martin Büttner
Martin Büttner
@Sp3000 that's totally what I had in mind when I first thought of the challenge ;)
 
Sp3000
Sp3000
eval(input()) looks more like Python 3 to me
 
grc
grc
@xnor ah okay
 
xnor
xnor
10:46 AM
@Sp3000 oh, that makes sense
 
Sp3000
Sp3000
@justhalf What's the final piece of truth?
 
xnor
xnor
i was also inspired by the reduction to max flow that I originally thought of
the antichain is the min cut
*antipile
that limits the size of the "max flow" (number of piles)
 
Martin Büttner
Martin Büttner
@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)
 
justhalf
justhalf
@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
 
Sp3000
Sp3000
Oh, I didn't know you could do that. Or edit messages either. :P [/new to chat]
 
justhalf
justhalf
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
 
Sp3000
Sp3000
@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
 
xnor
xnor
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
 
Sp3000
Sp3000
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
 
xnor
xnor
i think it's exactly what we just proved
but for general posets
 
grc
grc
@xnor wow
 
xnor
xnor
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
 
Sp3000
Sp3000
So what you mean is, minimum number of chains is just the number of piles in our problem, right?
 
grc
grc
@xnor you should definitely add your name to the wikipedia page
 
xnor
xnor
64 years too late unfortunately
yes, chain = pile, antichain = antipile
anyway, i should sleep, good night
it's been fun
 
grc
grc
good night and thanks again :)
 
Sp3000
Sp3000
Fun extension question: Does the algorithm still work if we allow rotations
:P
(ie sort by max(width, height) first, then tiebreak by min(width, height))
 
Martin Büttner
Martin Büttner
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 ;)
 
grc
grc
@MartinBüttner wow, congrats in advance on 20k rep (and almost all of it this year!)
 
Martin Büttner
Martin Büttner
thanks ;) ... I get addicted to things... SO went even quicker
 
Sp3000
Sp3000
Talk about it, I'm supposed to be doing assignments and here I am discussing book stacking
 
grc
grc
yeah, I've got exams soon as well...
but maybe there will be a question on book stacking?
 
Martin Büttner
Martin Büttner
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...
 
grc
grc
11:37 AM
@Sp3000 do you mind if I use your diagram in my answer?
 
Sp3000
Sp3000
@grc Go for it - that's what I made it for :P
 
grc
grc
12:00 PM
@Sp3000 thanks
I've updated my post (hopefully it makes sense)
 
Sp3000
Sp3000
@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 :)
 
grc
grc
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
 
Sp3000
Sp3000
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
 
grc
grc
12:17 PM
@Sp3000 thanks - I still find time complexity a bit confusing and arbitrary
 
Sp3000
Sp3000
Hm? How so?
 
grc
grc
choosing which operation to count for any non-trivial algorithm is what I don't really get
 
Sp3000
Sp3000
Oh, I see
 
Geobits
Geobits
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.
 
Rainbolt
Rainbolt
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":
            break;
        default:
            return false;
        }
    }
    return true;
}
Ugh I butchered that way too much after renaming all of the variables
 
Sp3000
Sp3000
Somehow I feel terrible for not seeing anything wrong with that - is it just me?
 
Geobits
Geobits
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 ;)
 
Rainbolt
Rainbolt
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.
 
Geobits
Geobits
It's probably not how I'd have written it, but it doesn't seem terrible.
 
Rainbolt
Rainbolt
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
SearchOneDirectory(
                  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 (3462 days later) »