« first day (1453 days earlier)      last day (3385 days later) » 

12:46 AM
@Doorknob I'm not sure about that. the scoring of is not affected by the code at all. I think algorithm-only submissions should be totally valid for that, provided they contain a rigorous proof for correctness (I didn't bother reading the deleted answer to see how rigorous it actually was). cc @Optimizer
 
1:19 AM
@Sp3000 got that GoL in there... maybe I can add Wireworld tomorrow ;)
 
Hah, this popcon really has a snowball effect...
(or maybe it's just Mathematica :P)
 
it's getting really hard to come up with interesting stuff though... mostly because by now there's so much I could possibly do.
the limitation of the short code is pretty much gone.
 
Somehow I think the short code limitation made things more interesting at first :P
 
definitely
 
Also Humble Bundle has the Seaside expansion for the online Dominion, not sure if you're interested
 
1:25 AM
thanks, but I don't think I'm really into buying card games online
 
Ahaha k :)
 
I just played the first round with my own cards though ;)
 
(I just like online because I don't need to count things myself :P)
Oh? How was it?
 
nice :) ... I really like it. we just used the recommended starter set of kingdom cards and that worked out quite well.
 
I don't like goku last time I tried it
against real players is fine
but the AIs cheat
 
1:27 AM
I never play against the AIs, the need to pre-power-up your cards is just silly :/
 
the AI will start out with significantly better cards than you at later levels
like, a silver + 7 bronze + duchy + estate
while, you start out with 6 bronze + 4 estates
 
More annoying when you have to nerf the province they start with...
But yeah I just play with my friend every so often. Would get real cards but we're the only two I know who are really interested...
 
there used be an awesome version before goku
totally free, fast paced
 
@Sp3000 I think your Collatz gif stops a bit early
 
1:47 AM
0
A: Sandbox for Proposed Challenges

globbyRise and Shine code-golf The challenge is to create a program which takes a date - as per ISO8601 format - and prints the sunrise on that day. The program must work for any valid date between January 1, 0000, and December 31, 9999. In-built functions are disallowed, so the sunrise must be calcul...

 
@MartinBüttner, would you mind adding that to the OP of the sandbox?
 
2:38 AM
0
A: Sandbox for Proposed Challenges

xnorImplement the Henkin quantifier code-golf logic Your goal is to implement the Henkin quantifier Q_H, a generalized quantifier on four variables x1,x2,y1,y2 and a Boolean function f. It expresses the idea that for every choice of the x's, there's a choice of the y's that satisfies f, so that ea...

 
Also, would anyone mind taking a look at this? meta.codegolf.stackexchange.com/a/4646/15822 I finally got around to doing up the specs
 
it's kind-of hard to see the length and angle labels
the ideal thing would be just to label each one with the measure, possible with an arrow to avoid clutter
so there's no need to match up letters or colors
 
@xnor mmk
 
also, the dark purple / light purple look like light purple/ gray to me
is there any restriction on where the text can go?
(other than not touching the spikes)
 
@MartinBüttner The Fibonacci one does too - if I did all iterations the GIF would get long :P
Changed the description to say the GIF isn't the complete trace
 
3:01 AM
@xnor It has to be on the line between the center and the end of the spike but other than that, no
I guess I'll say that it has to be 5 units away
2-3
Also, are the specs easier to read now?
 
3:31 AM
0
A: Sandbox for Proposed Challenges

Nathan MerrillThe Genetic Game of Life In this game, you play as cells (as in cellular automata). Your goal is to reproduce and kill off other cells on the board. At the beginning of the game, two randomly chosen configurations will be chosen, one for reproduction, one for killing. The configurations will ...

 
@MartinBüttner Ah, I keep forgetting to do that. :P Sure, go ahead.
@MartinBüttner Without the code, it's entirely untestable.
 
4:30 AM
Hey does that sandbox post look sufficiently specced?
 
4:42 AM
hey, is there a Java STDIO controller written somewhere that I can use?
 
 
3 hours later…
7:36 AM
@MartinBüttner the question was code-challenge too. which means code answers only
@Sp3000 ^
 
"A code challenge is a competition for creative ways to solve a programming puzzle with an objective winning criterion not covered by other scoring tags" - tag wiki
I just thought it was something you use when it's not code-golf/popcon/etc., but I've probably got the wrong idea
 
we should really remove the "code" from it if it does not require actual code
or in other words, the question could have added just the fastest algorithm tag
 
I agree with you on that one :)
 
8:23 AM
@Sp3000 something like O(m^2 n) but actually worse :) My solution is not particularly clever
 
9:04 AM
@Lembik "but actually worse"?
I think what I had was basically R.T.'s solution... but that's been deleted right now...
 
Did anyone else see this suggested edit?
 
Ahaha wow, I don't think they get the idea of the challenge
(although, posting it as a comment would have been fine - just might not be well received)
 
It's baffling in more than one way.
@Sp3000 It would have been a perfectly valid - if mindnumbingly boring - comment.
 
But at least it'd be more courteous than suggesting it as an edit :)
 
9:42 AM
@Sp3000 I mean my solution has a worse time complexity than O(nm^2)
 
Ah k
 
@Sp3000 should I saw what it is? I worry about ruining the challenge for people
 
Hmm nah I think you can keep it yourself for a bit, just in case someone's working on it
 
but O(nm^2) would be amazing :)
if you can get that
 
Well the idea was just DP over tasks and machines
Out of curiosity though, did you intend for actual code or was an algorithm okay?
Because I'm not sure what should be done about the currently deleted answer...
 
9:49 AM
@Sp3000 either is perfect
@Sp3000 can you ask them why it was deleted? I haven't seen it at all
 
oh someone else deleted it!
that isn't fair
 
I think Optimizer said something about it being tagged code-challenge, when fastest-algorithm was all that was necessary
 
I specifically asked for an algorithm OR code
 
@Doorknob ^ ping
 
9:52 AM
it shouldn't have been deleted. The person could have been asked to give pseudocode or code but it should not have been deleted in my view
 
@Lembik remove the code-challenge
 
it's rather unlike codegolf.se to delete something without giving the opportunity to improve it as well
@Optimizer well I don't mind if they give code
@Optimizer should I delete it anyway?
 
then the competition is not on the same grounds.
code vs just plain text algorithm
 
@Optimizer what do you mean? I don't distinguish between code and pseudocode when describing an algorithm
I mean an algorithm description is ok as long as it is clear
and it can be clear in Java and Haskell or pseudocode
I agree R.T. should give code or pseudocode.. but he should have been asked to do so
 
I did ask
 
9:55 AM
how long did you give him?
 
and he could edit and ask for undeletion
 
people get scared off I think
once they have an answer deleted
 
well, I did not know that Doorknob will directly put a hammer
 
basically we can be nicer in this situation :)
ok
 
otherwise 3 people are required for deletion, not 2
 
9:56 AM
ah ok
I am trying to work out if the answer is right!
 
also, remove the code-challenge tag
since all you need is fastest algo
 
it is done
@Sp3000 do you think the answer is right?
It's not clear to me
 
a sandbox would have made these things more clear from the beginning :)
 
@Optimizer maybe :)
I am generally pro sandbox
one of the things that might help puzzling.se
 
something can help puzzling ? :O
 
10:00 AM
@Optimizer :) They have a problem with their users too
I posted a challenge and people got furiously angry because they couldn't solve it immediately
and said it should be closed as a result :)
luckily someone came along a few hours later with a good solution
so not all their users are terrible :)
 
lol
 
puzzling.stackexchange.com/questions/7976/… but then weirdly the best answer gets nowhere near the most votes
 
VTC coz over 9000!
 
so I am really not sure about their users after all :)
 
I think so? It sounds like what I had in mind, which was to have an m by n grid where each row is a machine and each column is a task, cell (a, b) being the cost of finishing up to the b'th task, ending on the a'th machine. The extra factor of m comes from the fact that to calculate the cost for a cell you need to consider all cells in the previous column
Having said that, I haven't coded it to check yet
 
10:06 AM
I have flagged for undeletion of that answer
 
@Lembik Just tried it by hand I think it's not as easy as O(m^2 n)
Forgot to consider cost/time balance, i.e. you can't tell if it's good to take higher cost, lower time now or lower cost, higher time
 
10:27 AM
@Sp3000 thanks... I didn't think it could work. Isn't the problem np-hard?
@Sp3000 not that I have proved that so maybe ignore that comment
@Optimizer thanks
@Optimizer maybe he will be able to fix it once sp3000 tells him what is wrong with it
him/her
@MartinBüttner in the tree problem you described, can you just alternate rows?
 
10:42 AM
@Lembik no
      X
  ____|____
  |       |
  X       X
  |     __|__
  |     |||||
  X     XXXXX
__|__
|||||
XXXXX
the Xs are nodes.
 
@Lembik I read your post...the obvious approach in O(m^2 n d)
or if cost was bounded and discretized instead of time, you could swap c for d
 
@Optimizer a) that was just mistagged. b) I don't think "code-challenge" really implies anything at all except "I'm using my own winning criterion"
 
what is tree problem?
maybe there should be a tag for ones that involve code length as well as other things; those are common
 
10:59 AM
I don't know... "as well as other things" is pretty broad to catch everything in one tag
@Sp3000 I'll never be able to decide between learning Befunge and ><> :D
 
Is there any reason to use anything besides 1 or 2?
 
I find the Python interpreter easy to use, and mirrors are cool :P
I don't know, I tried downloading and interpreter for Befunge-98 once and never got it to work
 
With the tree problem, either way, should be simple to make a polynomial solution
can calculate the optimum subtree for each value from 1 to N
trees make everything easy
 
@feersum see the tree a few messages back
@feersum yeah I was thinking a greedy solution should do it, but I'm not sure how to find the largest admissible subset of nodes efficiently
 
huh?
 
11:07 AM
@Sp3000 in terms of complexity ><> seems to be somewhere in between Befunge 93 and 98, right?
 
I start by picking any old node as the root
 
Yeah, like it's got a-f for 10-15 which 98 does but 93 doesn't
 
@feersum and then?
 
(I should have picked a smaller input for making this GIF. Better yet, someone should have made an interpreter for my bounty D: )
 
on each subtree, find best possible solution for its root being 1...N
pick best number for root based on those
I would like to write some interpreters...but don't want to Javascript :(
 
11:10 AM
@feersum that sounds pretty exponential to me
 
There there, I feel your Javascript pain :)
 
JavaScript isn't all that bad if you use it right
 
there's no integers!
 
that's true
 
Or maps ... well not maps/dicts in the way I'm used to
I can't get over the fact that I can do obj[0] and later do obj.0 or whatever it was
 
11:16 AM
huh
certains looks icky
barfulous
 
"The Map object is a simple key/value map." -> "This is an experimental technology, part of the Harmony (ECMAScript 6) proposal."
Huzzah?
 
omg so high tech
 
@Sp3000 no, obj.x only works if x is a valid identifier and then equivalent to obj["x"]. what's weird is that you can do things like obj[{}] which is then stored at obj["object ()"] or something like that
 
@MartinBüttner on the trees is the goal to be polynomial in N, number of nodes or both?
 
@feersum they are the same N
 
11:19 AM
ok
 
Oh true, just tried and obj.0 didn't work
 
I thought JS was bad but little did I know how much until this conversation!
 
@Sp3000 I believe you can store something at obj[""]
 
Seems like you can, but is that weird in some way?
(although, I'm having trouble figuring out what's supposed to be weird and what's not right now)
 
well, it's definitely inaccessible with . :D
 
11:22 AM
Oh I know something I thought was weird
x="5"
y=4
Then x*y and x+y
 
yeah
as I said, JavaScript is fine if you know how to use it right
 
is multiplication non-commutative?
 
just steer away from all thoe odd quirks
@feersum addition is, between different types
x+y would be "54" but y+x is 9
 
addition ???
 
Maybe I shouldn't be writing all these stack snippets then :P
 
11:24 AM
I could see string multiplication being noncommutative kind of, but not +
 
My console seems to give "54" and "45", actually
But 20 for *
 
well operands are coerced into the left-hand type if possible
@Sp3000 huh okay
@Sp3000 ah yeah right, it's that + coerces to string because it can, but * coerces to Number because it can't coerce to string
 
Ah, no string multiplication?
 
yeah, I keep forgetting these things, because I usually don't encounter them
@Sp3000 nope
 
I don't think I'll get used to this auto-convert-from-string-to-number-as-necessary feature
 
11:26 AM
I still think the tree should be polynomial time, but it's too hard to prove
because when counting from 1 to N, at a certain point there will be nothing above the current number
and then the rest of them are constant time
 
@feersum well your solution would be the winning answer!
 
It's not really insightful though
too boring to be worth writing
 
@MartinBüttner what's wrong with alternating rows?
@feersum :(
 
@Lembik have you seen the example tree?
only using 1 and 2 is not optimal
 
@MartinBüttner no sorry.. I only know what you said to me
@MartinBüttner that is very interesting
 
11:33 AM
by using clumps of 1s you can definitely require arbitrarily high numbers, continuing same strategy
but it will require exponentially more amounts of 1's to do so
well, maybe
 
@feersum it's possible your solution is optimal of course.. so if everyone finds it too boring there will be no answer
'@feersum but it is the same complexity I got
@MartinBüttner oh sorry I didn't see the nice picture you drew
@MartinBüttner so nodes with only one child are allowed?
 
sure, any tree is
 
@MartinBüttner ok thanks.. that does make things more difficult. I somehow always remove nodes with only one child
I mean mentally
 
1-child nodes aren't needed to have 3s, 4s etc
 
oh
@feersum do you think my problem is np-hard?
 
11:46 AM
like this
     X
   // \\\
  X   XXXX
 //\\
XXXXX
maybe if you had real numbers for the time amounts
and costs
 
so if you assign 1 to 1st and 3rd layer
adn 2 to the second, this is non-optimal?
in your tree example I mean
 
@Lembik yes, optimal is 14, yours is 16
 
ok.. that's very interesting
@feersum your comment about real numbers for the time amounts and costs is also interesting although I don't understand it yet
 
I mean times, not cost
 
@feersum right but d is a value so your and my solutions are exponential time
@feersum exponential time in the number of bits needed to represent the input
 
11:50 AM
what?
times are not integers?
 
@feersum d is the largest deadline. This means that in the input there is a number d with log d bits
@feersum if the algorithms takes d time that is exponential in the input size. In the same sense that naive trial and error factoring is exponential time
 
ok I see, you're saying d is exponential in log d
 
yes
so O(nm^2 d) is an exponential time solution
in the size of the input
and hence compatible with the problem being np-hard
some would call it "pseudo polynomial time"
 
Seems likely, I mean it's a sort of traveling salesman-ish thing
 
@feersum I'll add a bounty in a bit to at least get one answer :)
 
12:03 PM
@MartinBüttner I really think that the code in code-challenge refers to "hey, you have to write a code and the winning criteria is this : "
and Doorknob also thought so (AFAICS)
 
@Optimizer it seems pointless to add a tag for "challenges not involving code with a custom winning criterion"
 
@MartinBüttner I think for this use case, fastest-algorithm covers all
 
you could have "algorithm with least space complexity"... or a mixture of the two... or best numerical accuracy... or probably something else.
 
is PPCG really for "just" algorithm challenges ?
 
why not? designing algorithms is definitely part of programming. but there's no point discussing it with me. bring it up on meta if you disagree.
 
12:12 PM
I am not against anything
 
12:33 PM
@MartinBüttner BTW congrats on your (future) 9th gold badge ..
 
@Optimizer to be fair I specify that an answer entirely in code is OK
 
@Sp3000 Hang on, this is Programming Puzzles and Code Golf, correct? I haven't seen any answers that do not contain code being allowed.
3
 
@Optimizer I'm still pretty far away
 
@MartinBüttner its still 1st on HNQ LTIC
@Doorknob so many negatives. Hard to figure out what are you saying actually.
 
@Optimizer Heh, I'll reword that: "All the answers I've seen have contained code of some sort"
 
12:35 PM
That is what I also thought.
 
@Doorknob I'm not entirely sure about that. But that doesn't automatically imply we disallow algorithm-only answers.
 
is there a consensus anywhere whether non code based challenges are on-topic ?
 
are we talking about the answer to my question?
 
The deleted answer is a perfect example of the fact that not requiring code allows one to write something that makes no sense
 
@Optimizer I have just posted a meta question
 
12:36 PM
because if so, I think all that was needed was a commentn asking for clear pseudocode to be added, no?
@feersum didn't it just need a comment asking for some code or pseudocode?
 
pseudocode can't be tested so a non-functional answer is likely
I'm against pseudocode-only answers
 
@feersum testing actual code is no proof of correctness either
 
@feersum ok so this is a good point.. we could insist on actually runnable code in all answers.. I am not sure we should but we could :)
 
if you want to be 100% sure you need a rigorous proof either way
 
@MartinBüttner a very good point!!
@feersum do you want a complete runnable piece of code in every answer or would code snippets ever be alllowed?
 
12:38 PM
um, what sort of code snippet are you thinking?
 
@feersum a function for example
 
I think the code should be runnable
 
@feersum but you can't just compile a function and run it
 
of course, a function is runnable, it is a standard answer form for any question
 
@feersum well you can't typically just copy it into a file and compile it
@feersum it might need some setup
on tex.se you have to give full LaTeX that you could just copy into a file without editing and it would compile
 
12:40 PM
You mean if a Java function did not have class X { } around it?
 
0
Q: Do all challenges have to be answered with code?

Martin BüttnerWe have a tag fastest-algorithm and we've had it for a while now. Submissions are scored based on the time complexity of the algorithm. This means that the actual implementation has no effect on the score whatsoever (except if, say, actual runtime is used as a tiebreaker). In particular, we had ...

 
really who cares
 
@feersum well it might not actually do anything.. for example print its output or read in input
 
Function answers are normal for code golf, etc. answers. I don't know why you would make a big deal out of that.
 
@feersum well all I am saying is that if code doesn't actually have to be runnable, that is a slightly different story
 
12:43 PM
this is a ridiculously trivial discussion
 
@feersum and given that we can't tell if code is correct without a separate argument, i am not sure what is wrong with pseudocode for a small subset of the questions
 
@Doorknob while you're here... what about changing the weekly challenge schedule?
 
@MartinBüttner Oh yeah, about that, maybe it could just be a weekly-ish challenge? Translation only took a week, and if it was biweekly we'd just have been sitting around doing nothing for the second week.
 
@Doorknob translation could have used a few more days, imo.
and having a couple of days break between the challenges is also not a bad thing for people who want to be involved in most of them
I think a less strict deadline that we can always meet is probably better than a strict deadline that have to extend every other week.
 
Hmm, that does make sense.
0
A: Do all challenges have to be answered with code?

DoorknobYes, all answers should contain code. Without working code, there is no way to test the answer to verify that it works, to determine its score, etc. If we allow algorithm-describing answers, then we'd also have to allow, say, answers that describe how you would write the code (without actually ...

 
12:57 PM
promotion:
0
A: How do weekly topic challenges work?

Martin BüttnerProgramming Puzzles & Code Golf beta has started a topic challenge. (Weekly challenge ideas) We also started with our weekly challenges, although we decided to change the format a little. Since writing good questions/challenges on PPCG is quite hard, we're going for one high-quality challenge pe...

@Doorknob thanks. but regarding your first point, I still maintain that code is no proof of correctness either.
 
who says it is?
 

« first day (1453 days earlier)      last day (3385 days later) »