The Nineteenth Byte

Martin Büttner

12:46 AM

@Doorknob I'm not sure about that. the scoring of fastest-algorithm 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

Martin Büttner

1:19 AM

@Sp3000 got that GoL in there... maybe I can add Wireworld tomorrow ;)

Sp3000

Hah, this popcon really has a snowball effect...

(or maybe it's just Mathematica :P)

Martin Büttner

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.

Sp3000

Somehow I think the short code limitation made things more interesting at first :P

Martin Büttner

definitely

Sp3000

Also Humble Bundle has the Seaside expansion for the online Dominion, not sure if you're interested

Martin Büttner

1:25 AM

thanks, but I don't think I'm really into buying card games online

Sp3000

Ahaha k :)

Martin Büttner

I just played the first round with my own cards though ;)

Sp3000

(I just like online because I don't need to count things myself :P)

Oh? How was it?

Martin Büttner

nice :) ... I really like it. we just used the recommended starter set of kingdom cards and that worked out quite well.

Nathan Merrill

I don't like goku last time I tried it

against real players is fine

but the AIs cheat

Sp3000

1:27 AM

I never play against the AIs, the need to pre-power-up your cards is just silly :/

Nathan Merrill

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

Sp3000

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

Nathan Merrill

there used be an awesome version before goku

totally free, fast paced

Martin Büttner

@Sp3000 I think your Collatz gif stops a bit early

New Sandboxed Posts

1:47 AM

0

A: Sandbox for Proposed Challenges

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

globby

@MartinBüttner, would you mind adding that to the OP of the sandbox?

New Sandboxed Posts

2:38 AM

0

A: Sandbox for Proposed Challenges

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

globby

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

xnor

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

globby

@xnor mmk

xnor

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)

Sp3000

@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

globby

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?

New Sandboxed Posts

3:31 AM

0

A: Sandbox for Proposed Challenges

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

Doorknob

@MartinBüttner Ah, I keep forgetting to do that. :P Sure, go ahead.

@MartinBüttner Without the code, it's entirely untestable.

Nathan Merrill

4:30 AM

Hey does that sandbox post look sufficiently specced?

Nathan Merrill

4:42 AM

hey, is there a Java STDIO controller written somewhere that I can use?

Optimizer

7:36 AM

@MartinBüttner the question was code-challenge too. which means code answers only

@Sp3000 ^

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

Optimizer

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

Sp3000

I agree with you on that one :)

Lembik

8:23 AM

@Sp3000 something like O(m^2 n) but actually worse :) My solution is not particularly clever

Sp3000

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

overactor

Did anyone else see this suggested edit?

Sp3000

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)

overactor

It's baffling in more than one way.

@Sp3000 It would have been a perfectly valid - if mindnumbingly boring - comment.

Sp3000

But at least it'd be more courteous than suggesting it as an edit :)

Lembik

9:42 AM

@Sp3000 I mean my solution has a worse time complexity than O(nm^2)

Sp3000

Ah k

Lembik

@Sp3000 should I saw what it is? I worry about ruining the challenge for people

Sp3000

Hmm nah I think you can keep it yourself for a bit, just in case someone's working on it

Lembik

but O(nm^2) would be amazing :)

if you can get that

Sp3000

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

Lembik

9:49 AM

@Sp3000 either is perfect

@Sp3000 can you ask them why it was deleted? I haven't seen it at all

Sp3000

Lembik

oh someone else deleted it!

that isn't fair

Sp3000

I think Optimizer said something about it being tagged code-challenge, when fastest-algorithm was all that was necessary

Lembik

I specifically asked for an algorithm OR code

Sp3000

@Doorknob ^ ping

Lembik

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

Optimizer

@Lembik remove the code-challenge

Lembik

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?

Optimizer

then the competition is not on the same grounds.

code vs just plain text algorithm

Lembik

@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

Optimizer

I did ask

Lembik

9:55 AM

how long did you give him?

Optimizer

and he could edit and ask for undeletion

Lembik

people get scared off I think

once they have an answer deleted

Optimizer

well, I did not know that Doorknob will directly put a hammer

Lembik

basically we can be nicer in this situation :)

ok

Optimizer

otherwise 3 people are required for deletion, not 2

Lembik

9:56 AM

ah ok

I am trying to work out if the answer is right!

Optimizer

also, remove the code-challenge tag

since all you need is fastest algo

Lembik

it is done

@Sp3000 do you think the answer is right?

It's not clear to me

Optimizer

a sandbox would have made these things more clear from the beginning :)

Lembik

@Optimizer maybe :)

I am generally pro sandbox

one of the things that might help puzzling.se

Optimizer

something can help puzzling ? :O

Lembik

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

Optimizer

lol

Lembik

puzzling.stackexchange.com/questions/7976/… but then weirdly the best answer gets nowhere near the most votes

Optimizer

VTC coz over 9000!

Lembik

so I am really not sure about their users after all :)

Sp3000

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

Optimizer

10:06 AM

I have flagged for undeletion of that answer

Sp3000

@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

Lembik

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?

Martin Büttner

10:42 AM

@Lembik no

      X
  ____|____
  |       |
  X       X
  |     __|__
  |     |||||
  X     XXXXX
__|__
|||||
XXXXX

the Xs are nodes.

feersum

@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

Martin Büttner

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

feersum

what is tree problem?

maybe there should be a tag for ones that involve code length as well as other things; those are common

Martin Büttner

10:59 AM

I don't know... "as well as other things" is pretty broad to catch everything in one tag

@feersum this chat.stackexchange.com/transcript/message/19636688#19636688

@Sp3000 I'll never be able to decide between learning Befunge and ><> :D

feersum

Is there any reason to use anything besides 1 or 2?

Sp3000

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

feersum

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

Martin Büttner

@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

feersum

huh?

Martin Büttner

11:07 AM

@Sp3000 in terms of complexity ><> seems to be somewhere in between Befunge 93 and 98, right?

feersum

I start by picking any old node as the root

Sp3000

Yeah, like it's got a-f for 10-15 which 98 does but 93 doesn't

Martin Büttner

@feersum and then?

Sp3000

(I should have picked a smaller input for making this GIF. Better yet, someone should have made an interpreter for my bounty D: )

feersum

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 :(

Martin Büttner

11:10 AM

@feersum that sounds pretty exponential to me

Sp3000

There there, I feel your Javascript pain :)

Martin Büttner

JavaScript isn't all that bad if you use it right

feersum

there's no integers!

Martin Büttner

that's true

Sp3000

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

feersum

11:16 AM

huh

certains looks icky

barfulous

Sp3000

"The Map object is a simple key/value map." -> "This is an experimental technology, part of the Harmony (ECMAScript 6) proposal."

Huzzah?

feersum

omg so high tech

Martin Büttner

@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

feersum

@MartinBüttner on the trees is the goal to be polynomial in N, number of nodes or both?

Martin Büttner

@feersum they are the same N

feersum

11:19 AM

ok

Sp3000

Oh true, just tried and obj.0 didn't work

feersum

I thought JS was bad but little did I know how much until this conversation!

Martin Büttner

@Sp3000 I believe you can store something at obj[""]

Sp3000

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)

Martin Büttner

well, it's definitely inaccessible with . :D

Sp3000

11:22 AM

Oh I know something I thought was weird

x="5"
y=4

Then x*y and x+y

Martin Büttner

yeah

as I said, JavaScript is fine if you know how to use it right

feersum

is multiplication non-commutative?

Martin Büttner

just steer away from all thoe odd quirks

@feersum addition is, between different types

x+y would be "54" but y+x is 9

feersum

addition ???

Sp3000

Maybe I shouldn't be writing all these stack snippets then :P

feersum

11:24 AM

I could see string multiplication being noncommutative kind of, but not +

Sp3000

My console seems to give "54" and "45", actually

But 20 for *

Martin Büttner

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

Sp3000

Ah, no string multiplication?

Martin Büttner

yeah, I keep forgetting these things, because I usually don't encounter them

@Sp3000 nope

Sp3000

I don't think I'll get used to this auto-convert-from-string-to-number-as-necessary feature

feersum

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

Lembik

@feersum well your solution would be the winning answer!

feersum

It's not really insightful though

too boring to be worth writing

Lembik

@MartinBüttner what's wrong with alternating rows?

@feersum :(

Martin Büttner

@Lembik have you seen the example tree?

only using 1 and 2 is not optimal

Lembik

@MartinBüttner no sorry.. I only know what you said to me

@MartinBüttner that is very interesting

feersum

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

Lembik

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

Martin Büttner

sure, any tree is

Lembik

@MartinBüttner ok thanks.. that does make things more difficult. I somehow always remove nodes with only one child

I mean mentally

feersum

1-child nodes aren't needed to have 3s, 4s etc

Lembik

oh

@feersum do you think my problem is np-hard?

feersum

11:46 AM

like this

     X
   // \\\
  X   XXXX
 //\\
XXXXX

maybe if you had real numbers for the time amounts

and costs

Lembik

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

feersum

@Lembik yes, optimal is 14, yours is 16

Lembik

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

feersum

I mean times, not cost

Lembik

@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

feersum

11:50 AM

what?

times are not integers?

Lembik

@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

feersum

ok I see, you're saying d is exponential in log d

Lembik

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"

feersum

Seems likely, I mean it's a sort of traveling salesman-ish thing

Lembik

@feersum I'll add a bounty in a bit to at least get one answer :)

Optimizer

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)

Martin Büttner

@Optimizer it seems pointless to add a algorithms-challenge tag for "challenges not involving code with a custom winning criterion"

Optimizer

@MartinBüttner I think for this use case, fastest-algorithm covers all

Martin Büttner

you could have "algorithm with least space complexity"... or a mixture of the two... or best numerical accuracy... or probably something else.

Optimizer

is PPCG really for "just" algorithm challenges ?

Martin Büttner

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.

Optimizer

12:12 PM

I am not against anything

Optimizer

12:33 PM

@MartinBüttner BTW congrats on your (future) 9th gold badge ..

Lembik

@Optimizer to be fair I specify that an answer entirely in code is OK

Doorknob

@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

Martin Büttner

@Optimizer I'm still pretty far away

Optimizer

@MartinBüttner its still 1st on HNQ LTIC

@Doorknob so many negatives. Hard to figure out what are you saying actually.

Doorknob

@Optimizer Heh, I'll reword that: "All the answers I've seen have contained code of some sort"

Optimizer

12:35 PM

That is what I also thought.

Martin Büttner

@Doorknob I'm not entirely sure about that. But that doesn't automatically imply we disallow algorithm-only answers.

Optimizer

is there a consensus anywhere whether non code based challenges are on-topic ?

Lembik

are we talking about the answer to my question?

feersum

The deleted answer is a perfect example of the fact that not requiring code allows one to write something that makes no sense

Martin Büttner

@Optimizer I have just posted a meta question

Lembik

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?

feersum

pseudocode can't be tested so a non-functional answer is likely

I'm against pseudocode-only answers

Martin Büttner

@feersum testing actual code is no proof of correctness either

Lembik

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

Martin Büttner

if you want to be 100% sure you need a rigorous proof either way

Lembik

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

feersum

12:38 PM

um, what sort of code snippet are you thinking?

Lembik

@feersum a function for example

feersum

I think the code should be runnable

Lembik

@feersum but you can't just compile a function and run it

feersum

of course, a function is runnable, it is a standard answer form for any question

Lembik

@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

feersum

12:40 PM

You mean if a Java function did not have class X { } around it?

New Meta Posts

0

Q: Do all challenges have to be answered with code?

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

feersum

really who cares

Lembik

@feersum well it might not actually do anything.. for example print its output or read in input

feersum

Function answers are normal for code golf, etc. answers. I don't know why you would make a big deal out of that.

Lembik

@feersum well all I am saying is that if code doesn't actually have to be runnable, that is a slightly different story

feersum

12:43 PM

this is a ridiculously trivial discussion

Lembik

@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

Martin Büttner

@Doorknob while you're here... what about changing the weekly challenge schedule?

Doorknob

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

Martin Büttner

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

Doorknob

Hmm, that does make sense.

0

A: Do all challenges have to be answered with code?

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

Martin Büttner

12:57 PM

promotion:

0

A: How do weekly topic challenges work?

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

feersum

who says it is?

Transcript for