The Nineteenth Byte

xnor

12:00 AM

so there's two parameters the complexity depends on

the number of books

and the maximize size (assuming whole numbers)

i think you need to specify how these relate or which takes prioeity

Martin Büttner

would the maximum size really affect complexity?

xnor

i'd suggest simply bounding the maximum dimension by the number of books

yes

if the max size is at most K

you can only have k*k different types of books

and you always want to stack every book of the same type in a single stack

Martin Büttner

@xnor An alternative: I revert to the simpler stack metric - minimise the number of overlaps. That should be a simpler problem, because it asks for the shortest Hamiltonian path of a graph with edge weights 0 or 1. And then I could turn the full problem with areas (and possibly rotation) into a code challenge with strict time limit ("sort as well as you can").

xnor

hmm

i think i find the original more interesting

Martin Büttner

@xnor well yes, the parameter would be the number of distinct books

xnor

12:02 AM

with no bound on size?

i think you need some bound to at least ensure the sizes are representable

within your runtime

Martin Büttner

yeah, you can usually assume that

but if I put a bound on the size, I also put a bound on the relevant input parameter. which shouldn't really matter for fastest-algorithm.

xnor

i feel like with the change, all anyone can do is construct the binary graph (easy), and then it's a generic ham path challenge

though to be fair i guess you can think of the original version as a tsp challenge

what do you mean by "put a bound on the size?"

Martin Büttner

@xnor the same as you did ;)

xnor

ah, ok

then i don't understand what you mean by "I also put a bound on the relevant input parameter"

Martin Büttner

if I say books won't be larger than 100x100 then that means the graph won't have more than 10k vertices

xnor

12:08 AM

isn't it O(1) then?

Martin Büttner

technically yes. which is why I said I don't think limiting the input size makes sense for a fastest-algorithm challenge.

xnor

maybe i wasn't clear then about limiting the input size

Martin Büttner

for fastest algorithm I'll probably specify that there won't be duplicate books. they don't make the algorithm more interesting.

xnor

i meant guarantee that book-dim <= num-books

and have num-books be the parameter

Martin Büttner

would the book size even matter if I ruled out duplicates?

xnor

12:13 AM

i think only in the pedantic sense of a book size being a very long binary string

and so needing time to read and compare

Martin Büttner

well I'll say that the implementation can assume that it fits in a 32-bit integer so you can assume constant-time arithmetic.

xnor

i think that's OK, though again more pedantic people might ask if the same can be guaranteed for the sum of two book sizes

or the product in the area version

Martin Büttner

16 bit then ^^

xnor

sure, that should do

Martin Büttner

I'm off to bed... if nothing else comes up, I'll probably post this in about 12 to 16 hours.

xnor

12:27 AM

ok, good night!

is there really no way to make a private chat or send a private message?

xnor

1:02 AM

@MartinBüttner A friend and I believe we have a polynomial-time solution to the book problem (minimizing number of overhangs) by a reduction to max-flow

Soham Chowdhury

5:45 AM

Hey, what about a code-golf to generate a random gif similar to i.imgur.com/wPr421f.gif

?

xnor

6:35 AM

you'd need to specify precisely what you want in such a gif

Martin Büttner

7:50 AM

@xnor hm, interesting

is max flow polynomial for graphs that aren't acyclic?

Martin Büttner

8:15 AM

actually, it probably is

but how do you do the reduction such that you ensure every book is used?

New Sandboxed Posts

8:32 AM

0

A: Sandbox for Proposed Challenges

ASCII Calendar code-golf calendar (ascii-art?) Needs another title Given a date, generate a monthly calendar sheet using ASCII. For 23/10/2014 it would be: Mo Tu We Th Fr Sa Su 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ==== 20 21 22...

Martin Büttner

10:45 AM

@PeterTaylor I should just stop trying to come up with calendar-based challenges :D

Peter Taylor

10:57 AM

@MartinBüttner I think that avoiding duplication of the previous one is the reason that Calvin's Hobbies went with the weird effect.

Martin Büttner

@PeterTaylor yeah, very likely

or just because he really likes ASCII art challenges ^^

Peter Taylor

The easy calendar stuff has been done, so a new calendar question has to be quite unusual.

I enjoyed the Easter calculation one, though.

Martin Büttner

yeah, quite unusual, because most problems can be solved with lookup tables

I had another idea, but that might fall victim to the same thing. you know some watches have a small hand for the day of the month? and how people never remember to correct that if the month has less than 31 days? I was thinking about the following: given the current day of month and the shown day of month, calculate the most likely month (or a histogram of how likely each month is)

Peter Taylor

I've never seen a watch like that, but I get your drift. Still sounds like a lookup table.

Martin Büttner

well it's not attached to the centre with the other hands... it's one of those smaller ones in the "background".

Peter Taylor

11:04 AM

I saw the question idea about complications too :P

Martin Büttner

lol yeah, what happened to that

is main down again?

Peter Taylor

Looks like it

And meta

Unihedron

and Stack Overflow and Stack Exchange

Martin Büttner

I love how the chat always survives :D

Geobits

12:49 PM

I like carving pumpkins for Halloween. I normally do 5-6 each year, and am not too bad at it (ifisaysomyself). My problem is that I need some templates/stencils to work from. (cont...)

So, I was thinking a challenge to take an image file and make a stencil-type image for me to use on a pumpkin.

Martin Büttner

what kind of image?

Geobits

Basically, it would have to be done monochrome black/white, and make sure there are no floating pumpkin "islands".

Nothing too complicated. No Mona Lisa, more like game sprites or clipart style.

Martin Büttner

would that be a lot more interesting than flooding filling from the corners?

Geobits

I'm just having a hard time coming up with an exact spec for the output.

Well, flood filling from the corners would work, I guess, but it wouldn't be very popular, I'd imagine. It would be hard to do things like lit eyes or gaps with that.

Martin Büttner

hm yeah possibly

I want to finish the tetris controller... I'm missing timing and process communication... portable high-res timers in C... ugh....

I also still haven't decided about sending updates all the time vs submissions requesting them

real time koths are hard...

3

Geobits

12:58 PM

Yea, I can imagine. Discrete time steps make everything much easier ;)

Martin Büttner

1:09 PM

I really can't decide on the communication there are 2x2 ways to do it

decision one: should the controller send out a state update for every gravity tick or should it only send the current state upon request.
decision two: should the controller only send THAT a tick occurred or should it send the full state (in the case of a request, it would send the number of ticks since the last request). the latter means less parsing and less data through the pipeline, but it requires people to reproduce half the gameplay in their code.

Geobits

1) Each tick 2) give players an option? tell entries to send a flag on startup that chooses between full state and "ping" types or something like that

Though I suppose that works equally well for 1.

Martin Büttner

okay, I think I found a portable timer

are you on Unix?

Geobits

1:24 PM

Not at the moment.

Martin Büttner

k

Martin Büttner

1:38 PM

okay, the timer is working on Windows... if someone would be so kind to test it on a Unix system that would be amazing

Unihedron

1:49 PM

Hello!

Martin Büttner

:)

would you mind cloning this repo github.com/mbuettner/ppcg-tetris-tournament, doing gcc controller.c -o controller and then run ./controller and check that the program spits out one Tick. every second?

Unihedron

How to do that?

I need git first, right?

Martin Büttner

oh yes, that's right, sorry

if you've got git, it's just git clone https://github.com/mbuettner/ppcg-tetris-tournament.git

Unihedron

Sorry for making you say sorry. :) I'll try to get it!

downloads git

Peter Taylor

@Unihedron No, github has a "Download zip" option

Unihedron

1:57 PM

@PeterTaylor Oh, ok. Thanks!

Martin Büttner

@PeterTaylor oh right, I thought you'd needed to explicitly tag a release for that

Peter Taylor

(Ok, technically it won't be cloning it as Martin requested, but to test that it works you don't need the ability to pull changes)

Martin Büttner

yes, that's absolutely fine

Unihedron

I ran wget and got the file.

Martin Büttner

yeah that's even simpler

Unihedron

2:00 PM

I need a compiler?

Martin Büttner

gcc

don't worry if you don't have it

I'll find another way to test it on Unix

Unihedron

lol, I should compile it on my workstation first, then send it through ftp

user23013

2:40 PM

The tick works. Ubuntu 64bit

Martin Büttner

4:49 PM

@user23013 great, thank you!

Martin Büttner

6:54 PM

A wild @Rainbolt appeared!

5

how's things?

Rainbolt

Good mate! 'Ow bout you?

Martin Büttner

not too bad

Rainbolt

I'm here to discuss Tips questions.

Geobits

Uh oh ;)

Martin Büttner

@Rainbolt added timing to the tetris controller today... but now I'm left with the most annoying part... portably implementing persistent pipes in C...

Rainbolt

6:56 PM

You guys are making my comment lonely.

It's so bad that no other comment wants to live nearby.

Martin Büttner

wants to? they all died from sadness.

to be fair, you said the same thing yesterday and didn't even give me time to respond before deleting it again :D

Geobits

@Rainbolt At least the chat transcript is (barely) under a week now, right?

Rainbolt

It's my new catch phrase. "I'm here to discuss <insert topic that was beaten to death last month but Rainbolt just won't let it go>."

I figure if I joke about it on entry, people won't know when I'm being serious.

Geobits

You should chat with COTO about code trolling :P

Rainbolt

Heh. Yesterday, even after he said "I get it now" I sent three more messages explaining what happened.

Geobits

7:02 PM

Best answer on Skeptics ever. I'm expecting it to be deleted soon.

That is one jaded person.

Martin Büttner

oh wow :D

Optimizer

7:33 PM

How is this possible : i.snag.gy/ZMFzw.jpg ?

the 11th up vote only gave 2 reps

Martin Büttner

rep cap?

you can't get more than 200 rep from upvotes in a day

Optimizer

oh!

:(

Martin Büttner

don't make a sad face, there's badges for reaching it! :D

Optimizer

I am sad that at times like these, I have to limit my awesomeness

:P

does that include question up votes too ?

/me searches

Martin Büttner

yes

the only way to get beyond 200 is accepting questions, getting questions accepted and earning bounties

Optimizer

7:36 PM

what is associations ?

accepted edits ?

ah, cross site account.

Geobits

I feel your pain. Rep cap is good and bad at the same time :(

Martin Büttner

yay, I cracked one of the tetris codes

Geobits

Good, it's not COTO's C code :) I've been working on that one in my spare time. I think I've got 8-9 blocks right, but the others are giving me problems.

Martin Büttner

I'll have a look at that JS one now

Geobits

I'm thinking of setting a "bounty" on mine in the comments, to be started/awarded when cracked.

Martin Büttner

7:48 PM

well, offer the bounty on the rebuilder's challenge

of course you can't avoid it being auto-awared if no one cracks it

Geobits

Right, that's why I don't want to actually start it.

But if I comment on my code saying I'll offer X rep, I don't have to worry about that.

Martin Büttner

ah I see

yeah

you just have to worry about people noticing it :P

Geobits

Exactly

Martin Büttner

maybe rather edit and mention it at the bottom in a fat headline font

Geobits

Yea, that might be better.

Optimizer

7:50 PM

can you link to your submission ?

Geobits

The issue then is that Calvin wants answers posted after 72 hours. I wonder if he'd make an exception if I emailed him the solution so he knows there is one?

@Optimizer codegolf.stackexchange.com/a/40180/14215

Optimizer

Thanks

Martin Büttner

@Geobits I read that sentence the way I intended it in my own challenge: there's no obligation to post the solution after 72 hours, but as long as you don't do it, your submission can still be cracked.

Optimizer

btw, if I cannot get any more points, how will the notifications system tell me about an upvote ?

+0 ?

Martin Büttner

no it won't

Optimizer

7:52 PM

:(

Martin Büttner

but if you look at your rep tab on the profile, new upvotes will be highlighted

Optimizer

that's so messed up

Geobits

"A Jumbler must do this to win, since otherwise it will be unclear if there even was a solution." So I guess it just won't "win" if I don't post it. Not that it will win at 360 bytes anyway, unless basically all the others get cracked.

Martin Büttner

(new == since last visiting that tab)

@Geobits you want it to be cracked, so why would you care about being able to win? ;)

Geobits

Right, I was just pointing it out :P

@Optimizer That's my issue with meta. Since it doesn't give rep, you don't get vote notifications :(

Optimizer

7:58 PM

Bah, that tetris one is too time consuming

Martin Büttner

the JS one is haaaard

hosch250

Y'all should read this essay by Edsger W. Dijkstra: delivery.acm.org/10.1145/1290000/1283927/…

Geobits

The 80 or 420? I've only looked at the 80, but didn't get very far with it.

Martin Büttner

the 80

the JSFuck one is too crazy

Geobits

I only looked at it for a few minutes, long enough to throw the eval and window together, but got stuck and went back to the C one :)

Martin Büttner

8:10 PM

I didn't even come up with window yet :D

Geobits

I'm not sure why he's using window, but it seems likely from the pieces there. The presence of slashes has me thinking there are commented out line(s) to throw off the trail.

Martin Büttner

there has to be a comment

the block with three slashes can't be rotated to avoid two consecutive slashes

unless it's in a string of course

Geobits

Yea, but if the // is at the end of a line it doesn't mean much.

Martin Büttner

yeah sure

and what's with the var... there's no = in the code

Geobits

I was thinking more like "there's a line of complete bullshit that isn't valid code" to keep it from being put together

Martin Büttner

8:13 PM

you can also build "Tetris" but it might be a red herring

Geobits

Yea, I looked at that long enough to think it was fake. There's also building blocks for x/54 and another letter (can't remember which).

Martin Büttner

e and ,

Geobits

Good luck with it :P I'm out.

Martin Büttner

lol I think I'm giving up too

just found this: cnet.com/news/… looks neat

New Sandboxed Posts

8:31 PM

0

A: Sandbox for Proposed Challenges

Determine the Base that a Given Equation is Possible Given 3 integers, determine a possible base for the first two integers to multiply into the third. If you think of the Answer to Life, the World, and Everything, 6 * 9 == 42 is true in Base 13. You can assume that the first two values are sma...

Martin Büttner

9:15 PM

this sounds pretty cool: youtube.com/watch?v=q8g3v5ApGuI

(audio based puzzle game, for those who don't click random links :D)

xnor

10:32 PM

@MartinBüttner You can think of the book problem as Minimum Path Cover on a directed acyclic graph

Martin Büttner

but it's not acyclic, is it?

xnor

is it not?

the edge relation is that a book is strictly smaller than another book

l1<=l2 and w1<=w2

which is a partial order

Martin Büttner

oh, we're talking about the number of overlaps, not total area, right

xnor

yes

think of not as minimizing overhangs

but maximizing the number of non-overhangs

which is equivalent

Martin Büttner

yeah okay that makes sense

xnor

10:34 PM

and Minimum Path Cover reduces to max flow

also to Max Matching

(a small caveat is that this problem requires the paths to be vertex-disjoint but that can be fudged by taking any two overlapping paths, and cutting the overlapping part out of one)

Maximum flow problem

In optimization theory, maximum flow problems involve finding a feasible flow through a single-source, single-sink flow network that is maximum. The maximum flow problem can be seen as a special case of more complex network flow problems, such as the circulation problem. The maximum value of an s-t flow (i.e., flow from source s to sink t) is equal to the minimum capacity of an s-t cut (i.e., cut severing s from t) in the network, as stated in the max-flow min-cut theorem. == History == The maximum flow problem was first formulated in 1954 by T. E. Harris and F. S. Ross as a simplified model of...

err, that was supposed to link to the section "Minimum path cover in directed acyclic graph" but the autowikify ate it

Martin Büttner

hm okay, but that just means minimising numbers could be a nice golf if I require polynomial time complexity

because this doesn't apply to the minimum area one

which is definitely cyclic

xnor

do you think there is a poly-time algorithm for the minimizing numbers one?

Martin Büttner

wait I thought max flow was polynomial

xnor

oh, i misunderstood minimizing numbers = minimizing overhangs, not minimizing area

Optimizer

missed on 50 points :( When will the new day start as per SE ?

xnor

10:43 PM

yes

a polynomial cutoff + golf might be the better approach

then complexity tiebroken by golf

since there's some quite difficult standard algorithms to shave time on max flow

(possibly also maximum matching, I don't know if that's optimally done via max flow)

and it would be bad if it turned into a contest off "implement the latest max flow algorithm"

Martin Büttner

@Optimizer UTC

in 75 minutes

xnor

an empirical question: if you expect your post to be crazy upvoted, when is the strategically optimal time to post it in light of the rep cap?

Martin Büttner

@Optimizer also that's not too bad... I've missed over 200 before ;) ... I think there is a query on data.SE that tells you how much rep you'd have if there was no rep cap... try running it for Jon Skeet on SO :D

@xnor I wouldn't plan for the rep cap from a single post... it's really rare to hit that

xnor

the rep cap is 200, right?

Martin Büttner

yes

xnor

10:47 PM

it's happened

with the power of HNQ

Peter Taylor

@hosch250 What's the citation? The direct link just gives an error.

Martin Büttner

@xnor I know ^^... I was lucky with that a couple of times... but it is fairly unlikely... I'd rather try to maximise the possibility of getting noticed and into the HNQ ;)

xnor

@MartinBüttner I think it's more a function of the question

i do find an ironic anticorrelation with how easy the question is to answer and how many upvotes you get for answering it

about max flow and max matching, it looks like the best algorithms are from 2013 and would be quite hard to implement :-)

and as much as i'd find it hilarious

pure complexity optimization is probably not the way to go

and simply asking for a polynomial time algorithm with golf would be best

Martin Büttner

k

going by area (and then allowing rotation) could still make an interesting optimisation challenge

xnor

as in one where your score is a combination of code length and performance on a data set?

Martin Büttner

10:55 PM

no restriction on code length. just large data sets, a strict time limit, and the score is how low you can get the overlap

xnor

i see

and is the time limit just strict enough to rule out brute force solutions?

or does it also limit potential poly-time solutions if someone can find one?

Martin Büttner

I guess that's hard to figure out in advance, because even a polynomial solution could have huge exponents, but if the data set and time limit are large enough a heuristic based on an exact polynomial solution should still perform much better than others

xnor

i think that's fine. the only risk is that if someone quickly finds an optimal polynomial solution, that's it

well, i guess you could have golf as a tiebreak

Martin Büttner

or actual runtime to completion

xnor

ah, right

Martin Büttner

11:14 PM

rewritten it once more:

2

A: Sandbox for Proposed Challenges

Book Stack Sort code-golfarray-manipulationsorting When 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 but wider than the other. No matter which o...

@xnor if you could have another look, I'll probably post it then

xnor

11:40 PM

it says to minimize the number of overhangs, but also talks about the area of overhangs which is superfluous

i think you should also keep to note about book sizes fitting within 16 bits just in case it matters for complexity

Martin Büttner

@xnor fixed

@xnor done

xnor

and also the note that fixed max size doesn't make your algorithm O(1)

i.e. that it's a simplification for language data types

Martin Büttner

right, done

xnor

can you actually confirm also that what I said about poly time is right?

the challenge relies on this and it would be bad if I were mistaken

hosch250

@PeterTaylor This is specifically what I wanted you all to read:

In the case of a well-known conversational programming language I have been told from various sides that as soon as a programming community is equipped with a terminal for it, a specific phenomenon occurs that even has a well-established name: it is called “the one-liners”.

From this observation we must conclude that this language as a tool is an open invitation for clever tricks; and while exactly this may be the explanation for some of its appeal, viz. to those who like to show how clever they are, I am sorry, but I must regard this as one of the most damning things that can be said about a programming language.

xnor

11:46 PM

@MartinBüttner other than that, i'm done nitpicking!

hosch250

This is another link that may work:

cs.utexas.edu/~EWD/transcriptions/EWD03xx/EWD340.html

Martin Büttner

actually

xnor

i think it's good to go

Martin Büttner

in the graph