The Nineteenth Byte - 2014-09-11 (page 1 of 2)

« first day (1321 days earlier) ← previous day next day → last day (3520 days later) »

New Sandboxed Posts

1:19 AM

0

A: Sandbox for Proposed Challenges

Comment Java Code Little Billy is in an AP computer science class and his teacher requires him to comment his code (in Java) even though Little Billy thinks it is redundant. Little Billy is a lazy person and so he wants a program to comment for him. The Challenge: Make a program in any languag...

1:50 AM

@PeterTaylor I figured out how you could do dynamic 4-path in a very similar manner to @justhalf's dynamic 2-path. basically the exact same algorithm, but you'd produce two parallel paths as each path was extended.

2 hours later…

New Sandboxed Posts

3:41 AM

0

A: Sandbox for Proposed Challenges

Chad king-of-the-hill chess Chad is a variant of chess. It is played on an uncheckered board measuring twelve by twelve squares. Squares are denoted using standard chess notation, so a12 is the top left corner and l1 is the bottom right corner. The opening position of Chad looks like this: Ab...

2 hours later…

6:04 AM

I spend way too much time on these contests. Beating APL took the better part of a day...

New Sandboxed Posts

6:21 AM

0

A: Sandbox for Proposed Challenges

The Best Way to Rake Leaves code-challenge optimization [This is just a little problem I thought up while doing yard work today. It is not fully specified and I may not finish it if some simple optimal solution is found.] Suppose some 2D grid represents the area of a lawn. A number of leaves ...

1 hour later…

Martin Büttner

7:51 AM

@Rainbolt Sure they can. It's just another thing they "waste" cycles on. And another thing to optimise: how often do I check in order to be able to go as close to 10 min as possible without spending too much time on checking the time?

@PeterTaylor Fractional colouring sounds quite interesting, but I agree that it might be a bit over the top for PPCG.

I'll throw together a draft during my lunch break.

the sandbox went wild last night :D

We also had 13 questions in the last 48 hours, though 4 of those have a negative score.

Martin Büttner

8:07 AM

that's not too bad

I've seen that with 12 of 13 closed

@MartinBüttner more importantly, we're over 6/day

do closed questions count?

If you multiply the recommended amount of questions per day (15) with the recommended amount of answers per question (2.5), you get 37.5 answers per day

If you do the same calculation for CG, you get 44.62

I'd argue that number is more important than the two individual ones

Especially considering that creatinga large body of canonical answers to questions can never be the purpose of PPCG.

Martin Büttner

8:23 AM

just stop worrying about graduation :P

I'm not worrying, I'm pondering.

9:09 AM

hi

would anyone like to look at chat.stackexchange.com/rooms/240/the-nineteenth-byte and tell me what is wrong with it/how to fix it please?

I think it's a perfectly fine chatroom.

oops!

4

Q: Sandbox for Proposed Challenges

How does the sandbox work, and how do I use it? The sandbox works best if you sort the posts by "active". See the sandbox FAQ for more information on how to use this sandbox. Submission Directory This is a community-maintained list of the most active submissions in the Sandbox. If you add a ...

discussion featured sandbox

1

A: Sandbox for Proposed Challenges

Restricted memory optimization code-challenge The edit distance between two strings is the minimal number of single character insertions, deletions and substitutions needed to transform one string into the other. If the two strings have length n each, it is well known that this can be done in O...

The only downside being that it caused an infinite loop.

:)

what should I do with built in functions?

I'll give it a read

9:16 AM

@overactor thanks

Hmm, it's a difficult restriction to define.

yes!

I know what I mean :)

which is what theorists call "working memory"

or "working space"

I know what you mean too

but you can't expect people to figure out exactly how much working space each function they use uses

right

so what to do?

I mean in C it all seems fine

the problem is library functions and higher level languages

I think

I don't really care how much memory the function really uses

You could allow programs black box functions

9:21 AM

just how much it should use in theory if implemented in C

which functions?

with a fixed amount of memory usage

you let them use a function that performs a certain task with a defined memory usage

what I really need is to know which functions people will want to use

or I could just say they can use any function that is the equivalent of something in glibc I suppose

whether the actual implementation of that function uses more or less memory in that language doesn't matter

I can't guess what functions people will want to use

@user2179021 You could try?

@user2179021 You could take that approach

9:24 AM

the glibc approach?

yeah

that seems like the best option to me

but you shopudl ask around a bit

I am trying to get a list of what glibc has in it!

New Sandboxed Posts

10:05 AM

0

A: Sandbox for Proposed Challenges

Electron Configurations [WIP] code-golf kolmogorov-complexity chemistry Your mission is to accept an element* as input, and output its electron configuration (e.g. 2,8,8,2 for calcium). * Sandbox note - Depending on how much of a kolmogorov-complexity question you want this to be, accept an ato...

@user2179021 You need to ban recursion in order to not have to worry about the size of a stack frame.

@PeterTaylor good point!

@PeterTaylor but I am much more worried by the built in function

I really don't know how to deal with whatever functions you might get from the standard libraries of some high level languag

take Mathematica for example

Theorists talking about working space are assuming a stated model.

right and normally the only operations are if, while and assignment :)

@PeterTaylor can you see a way to do this by restricting to what C has in some way?

There you go.

10:10 AM

but where is malloc in all that?

???

If you allocate a 1000-element array on the stack, you don't need malloc.

ok

they need to be able to read in the data

which will presumably require some function to make it easy

No, require them to implement a function rather than a program.

I would like them to read in the data to test it

Or apply the memory restriction only to the function and not to the main method which tests it.

10:12 AM

this should be harmless

ok

does this make sense in non-C languages is what I am wondering

i am not an expert in C in any case.. are #include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <iostream> all part of glibc?

or is there some other term for the standard libraries?

I mean you need to include something just to print things out I think

in C

I suppose so

@PeterTaylor I was thinking of allowing anything that is functionally equivalent to something in glibc

@PeterTaylor is that reasonable?

If for the actual core task you say: "you may access array elements and characters in the string (which may be assumed to be pstrings or cstrings) and may use basic arithmetic operators on 32-bit ints and loops with no hidden state" then it doesn't matter what is in glibc or what libraries you need to print.

I don't know much about C either. I use it as little as possible because I hate its type system.

what does pstrings or cstrings mean?

Martin Büttner

@PeterTaylor do you have any idea what the maximum graph size is for which you can figure out the chromatic number in a reasonable time with brute force?

pstrings: Pascal-style, where you have essentially a character array of known length. cstrings: C-style, pointer to memory with null termination.

@MartinBüttner, no.

Martin Büttner

@PeterTaylor hm, for a graph with 8 vertices, testing all combinations of 7 colours is about 5 million combinations. that sounds doable.

for testing 8 colours for 9 vertices is 100 million. so I think I'll cap it at 8 vertices

10:22 AM

Sounds overkill even for brute force.

n-1 colours is achievable if you don't have K_n.

Martin Büttner

yes, but it's going to be code golf, right? so just testing all combinations might be the shorter code.

ok could you look at the latest version please? meta.codegolf.stackexchange.com/questions/2140/…

But you can pick your test cases such that n-1 is tested for 7 vertices and something less dense for more vertices.

You don't have to be able to test the entire range of permitted input in a reasonable time, especially not if you can predict how solutions will tackle it.

Martin Büttner

sure, but I'd rather just say "your program must handle all graphs up to N vertices" rather than "your program must handle these 5 test cases", because I doubt I'll come up with much more than that.

i am tempted to post it now

unless anyone complains

10:31 AM

8

Q: Cleaning lady may have taken fruit from my work desk

Yesterday in my office was weekly fruit day. As always, I took a few, and did not eat them all. I left two on my work table. The fruit were in perfectly good condition, and I have done this more than a few times. Today I came to work and realised that the fruit was missing. I left work late and ...

work-environment employees

oh wow

@MartinBüttner Sure, but make n=16 and include test cases which cover n=8, chi=7 and n=16, chi=3 or something.

Martin Büttner

@overactor that must have a lot of downvotes

@overactor I saw that in the hi-vis queue yesterday.

@MartinBüttner I wish I could see

Martin Büttner

@PeterTaylor Okay, but if I make n=16, then I'm basically disallowing brute force solutions, right?

10:33 AM

the accepted answer has 98 upvotes

Seeing it again, I'm reminded of the security officers at Los Alamos during Project Manhattan who reported someone for leaving an orange on their desk.

Because it might be a secret message to someone about the shape of the bomb.

@MartinBüttner, not at all, unless you also say that it must complete for any input up to that size within a certain time.

codegolf.stackexchange.com/questions/37620/… posted

Martin Büttner

It seems pointless to put a limit on it at all unless for the purpose of saying that results must be completed in a reasonable amount of time for those sizes. Or is there any other benefit to it?

Memory allocation for people using C

Martin Büttner

I see

@PeterTaylor any idea for a simple n=16 graph with chi=3, which isn't just the generalisation of this one? en.wikipedia.org/wiki/Graph_coloring#mediaviewer/…

I could make a triangular lattice

that would be n=15

10:44 AM

@MartinBüttner Doesn't Mathematica have a library function to enumerable k-colourable graphs over n vertices?

Martin Büttner

let me see

it has reference.wolfram.com/language/Combinatorica/ref/…

so I least I can double-check

I wonder if I should disallow using that. I'm usually a fan of built-in functions. and mathematica submissions would need a lot of bytes just to turn the string into a graph to feed to that function. then again, in this case it does kinda ruin the fun

Martin Büttner

10:59 AM

okay, posted in the sandbox

onebox should be coming up in a minute

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

Find the Chromatic Number code-golf Given an undirected graph, we can give each vertex a colour such that no two adjacent vertices share the same colour. The smallest number χ of distinct colours necessary to achieve this is called the chromatic number of the graph. For example, the following...

Martin Büttner

11:22 AM

opinions?

0

Q: Tips for Golfing in JavaScript - ES6 edition

This is similar to other "Tips for golfing in <...>" but specifically targeting the EcmaScript 6 features in JavaScript. JavaScript inherently is a very verbose language, function(){}, .forEach(), converting string to array, array-like object to array, etc, etc are super bloats and not healthy f...

tips javascript

@MartinBüttner voted

Martin Büttner

@PeterTaylor oops, that should have been chi = 8. or am I actually missing any edges?

I didn't check

I just assumed it was the test case we were discussing earlier

Martin Büttner

I just did, it should be a complete graph

the chi=5 one should serve as an example of an almost complete graph

did you spot any other problems with the challenge?

I suppose an example would be nice where the chromatic number is larger than the clique number, but I'm not sure how to construct one

ah wait... a ring of vertices, with an odd number, should serve

okay, got that too

1 hour later…

Martin Büttner

12:50 PM

okay, any last objections before I post the chromatic number challenge?

(meta.codegolf.stackexchange.com/a/2173/8478)

What's with all the haste lately? Surely the sandbox only really fulfils its purpose if posts are left for 48 hours (longer at weekends) to allow more than one person to give feedback?

2

Martin Büttner

hm fair enough... spec-wise this one seems simple enough not to need days of review, but okay. especially with so many other proposals having been posted the last couple of days, I'd rather get the simple ones through the sandbox fast, so people can pay more attention to the ones that need it (like koths and code challenges).

1:19 PM

@MartinBüttner Voted to close as Too Broad

Martin Büttner

@Rainbolt too broad? o.O

how is it any broader than any other tips question?

in fact I think it's narrower than all the others

@MartinBüttner It's not any broader than the others. I was under the impression that they held some sort of special historical value.

Martin Büttner

Yes but that doesn't mean we don't add new ones for new languages.

By all means, use broad questions as an excuse for more broad questions. I'll continue casting my close vote if I see questions that I think are too broad. That's why it's a vote.

Martin Büttner

well, we have a community consensus that tips-list questions are on topic

meta.codegolf.stackexchange.com/a/1725/8478 (that's +24/-1)

1:27 PM

I disagree with your census, and I think you are using it to steal my vote away.

Martin Büttner

no I want you to keep your vote, because I want the question closed

I just don't think it's the right close-vote reason :D

(also if that downvote is yours, my point is even stronger ^^)

It's not

I've never seen that before

Just look at this propaganda: "We shouldn't blindly accept the dogma that list-like questions are bad"

Martin Büttner

should we?

That wasn't my point...

If I accept that list questions are bad, am I blind?

Is it indeed a dogma?

Martin Büttner

well, I don't know. but if the only argument is "it's bad because it's a list", I don't think that's a valid argument

1:33 PM

Is it true because Stack Exchange said so, or could it be true because every other community agreed with it?

Martin Büttner

so how do you complete "it's bad because it's a list and that's bad because..."?

I didn't say it's bad because it's a list. I voted to close because it's too broad.

Martin Büttner

in that case my argument against the argument that it's a list is completely irrelevant

You actually try to argue that it's good because it's a tips question and the community has your back.

So you brought that up

So if your intent was to derail me and then call me pointless again, that didn't work out

I don't see how the question could be viewed as anything but Too Broad. The question literally does not allow for a complete answer.

Martin Büttner

I just told you that there's a community consensus for those to be on-topic. You can do with your close vote whatever you want. But I personally would accept a community consensus even if I disagree (or at least take my disagreement to meta instead). But whether you do that or not is up to you.

1:37 PM

So if some community decided that one of the standard close vote reasons does not apply to this site, and I had a problem with that, then you think I should go to meta?

Oh I see. You are in a bind. You need Too Broad because it applies to challenges

So you can claim helplessness here

I probably don't want to get involved with this at all, but what question are you guys even talking about?

Martin Büttner

I don't care what you want to call it, or how many things are wrong with it in the big picture of the general stack exchange model, but if the community decides "Tips for golfing in [language]" questions are cool, then they're cool. And if you think that's not the case, then I'm pretty sure meta is the right place to discuss that.

But feel free to go through this list and put a close vote on them all (they are only 51, shouldn't take too long). Maybe you can find 4 people in the review queue who agree.

@Geobits tips questions in general

The default is "If there is a close reason in the list, it IS valid." I don't have to bring this up on meta because I am on the default side.

If you want to go to meta and have that reason removed, then that's your thing.

Martin Büttner

(I just said that this one would be duplicate but Rainbolt turned that into another "tips questions should be closed argument" codegolf.stackexchange.com/questions/37624/…)

Can you please qualify that: new tips questions

As I said before, the old ones have historical significance

Martin Büttner

1:42 PM

@Rainbolt Wait why are old tips questions better than new ones?

They could still be closed.

They don't lose historical significance by being closed.

I thought this was all pretty well settled by now?

Martin Büttner

so did I

It was settled, but then Martin challenged my close vote. I am merely defending myself.

And why does this have to be about tips questions?

I voted to close as TOO BROAD. I would appreciate if you would use that to refer to the type of question we are discussing.

You are trying to turn this into an anti tips question war on my side.

I clearly said multiple times why I closed the question.

Ok, well, sorry I asked. Continue on. I'll just lurk on the side after grabbing some popcorn right quick.

Martin Büttner

@Rainbolt it's about tips because it looks like the community decided to make an exception and declare tips questions as neither too broad nor off topic.

1:46 PM

I don't see anything about tips questions not being too broad.

Martin Büttner

-.-

I'm saying it doesn't matter whether they're too broad or not if there's a consensus that they're okay to be posted

Oh, so the community made a specific type of question basically immune to my own opinions?

If I am not allowed my own opinion, then what are we talking for?

Martin Büttner

but it doesn't really matter. I know I'm not going to convince you, and I don't even care enough about it myself. I'm really just going with those 23 votes. what you do with your votes is your thing.

You aren't even trying to convince me that my opinion is wrong. You are trying to convince me that my opinion doesn't matter. It's so typical of this site.

Martin Büttner

you're entitled to your opinion, but if you're trying to close those questions based on it, you'll have to take it to meta or your opinion really doesn't matter, because you won't get the other 4 necessary close votes.

1:50 PM

And there's the crux of the situation. I won't get those other votes. Why won't I get them? Because you crusade against them at the mere mention of a Too Broad close vote.

Keep telling people that their opinions don't matter, and they won't bother to vote. Good plan.

Martin Büttner

I just pointed you towards evidence that you won't find many people agreeing with you if you don't try to present arguments to them

I presented my argument. The question is Too Broad.

It stopped there. You never retorted.

You defaulted to "Your argument is irrelevant."

How do I argue with someone who tells me my argument is irrelevant?

Martin Büttner

I replied with "the community agreed on making an exception"

You forgot the "and so therefore the question is.... ???"

Martin Büttner

still too broad but worth to be kept open?

1:53 PM

So you agree that they are too broad?

Martin Büttner

sure, I've never been saying they aren't. I'm pretty sure I explicitly said somewhere that we agreed that they should be kept open despite default close vote reasons applying.

So my close vote is entirely valid then?

23 people said they are Too Broad but should be kept open

Martin Büttner

ugh

yes

1 person said they are Too Broad but should NOT be kept open (me)

Martin Büttner

now go ahead and cast the other 50 close votes please

1:54 PM

Why can't I just peacefully have my 1 vote?

Martin Büttner

because that's being inconsistent

You basically spent 10 minutes telling me that my vote is invalid because I don't have 50 votes.

Martin Büttner

why is that one worse than the other 50?

Huh?

Martin Büttner

there are 51 tips questions

if you think they're all too broad, and that you should be able to express your opinion by close voting regardless of community consensus, why not close vote all of them?

I don't get it.

1:56 PM

13 mins ago, by Rainbolt

As I said before, the old ones have historical significance

Martin Büttner

unless your point is "you can't tell what the f*ck I do"

That's actually now "As I said before before"

Martin Büttner

13 mins ago, by Martin Büttner

They don't lose historical significance by being closed.

Feel free to ask me a fourth time.

Martin Büttner

I think most "historical significance" posts on SO are closed

in fact, most of them are locked. that's worse than closed. that's almost deleted.

1:58 PM

I am willing to make an exception for them because they have historical significance

Martin Büttner

That seems more random to me than making an exception because the community agrees they are useful.

But as I said: whatever, they are your votes.

You keep excluding me from the community

Martin Büttner

You didn't even downvote that post to disagree

If 23 people think they are exceptional, are you saying that it somehow invalidates my vote?

Because the ratio makes it pointless

Martin Büttner

ummm, what?

2:00 PM

23 to 1

Martin Büttner

yeah I don't get it. I'm just saying do with your votes whatever.

why do I have to vote on that post in order to have a valid opinion?

Martin Büttner

because your only point seems to be "I want to have an opinion"

But your only point seems to be "Your opinion is invalid because 23 people disagree."

Martin Büttner

no, your opinion is totally valid. but if you keep it to yourself I'm not sure what you're trying to accomplish with it.

other than being able to say "haha, but I disagree"

2:02 PM

I hadn't heard of that meta post until you brought it up mid argument

@Rainbolt, you're free to try and convince people of your opinion on meta though

For what it's worth, I think I agree with you

Martin Büttner

@Rainbolt he doesn't want to though

@overactor Too Broad is a default close reason. If you want to invalidate it, you have to remove it.

The default is "If it's on the list of close reasons, and I think it applies, I can use it."

You are trying to buck the system by gathering a consensus and then using that as an argument for invalidating the voting system

You could argue that a community concensus overrules default rules though

@overactor that's exactly what is happening

If you want to override the default, the way to do it is to get the list of close reasons changed.

Make it apparent to new users that Too Broad is not a valid reason

2:05 PM

Ideally, yes

Spitting meta posts at everyone who uses common sense is not the way to handle it.

I saw a Too Broad question, so I closed it as Too Broad. After the fact, Martin said 23 people disagree with me. Should I now retract my close vote just because 23 people disagree with it?

@Rainbolt Can you actually show me where anyone says "You can't vote that way"? Nobody here is telling you you're not allowed to, they're just disagreeing with your reasoning. That's just as allowed as voting, so what the fuck is the actual problem?

Expecting people to search the meta when things aren't as expected is perfectly reasonable though.

So it's expected that Too Broad may be an invalid reason?

@Geobits How about you look at the first thing I said: "I voted to close as Too Broad". Does that indicate that I have a problem to you?

yeah, it's a perfectly reasonable assumption to make

2:08 PM

No, but you're acting like you're being persecuted, claiming that he's trying to "steal your votes", etc.

And in my opinion, no one can blame you for voting to close as too broad

And if you then notice no one agrees with you, you can take it to meta and ask: "What gives?"

@Geobits Martin questioned my vote, so I responded. The argument blew up shortly after that, and you are now taking the problem out of context

Martin Büttner

In other news, I rewrote the timing part of the integer lattice challenge:

3

A: Sandbox for Proposed Challenges

False Positives on an Integer Lattice fastest-code arithmetic floating-point Background When working on a 2-D grid of integer coordinates, you sometimes want to know whether two vectors (with integer components) have the same magnitude. Of course, in Euclidean geometry the magnitude of a vecto...

If that's looking good, I think it's ready to post. I've got code to kill a process after a fixed timeout from older challenges, so I know that's going to work.

@Rainbolt funnily, the post that sparked it all has been deleted in the meantime

@MartinBüttner It was a bad post

goes to create an 5 alternate accounts. One to ask a tips questions, and 4 who will always vote the way he does.

2:16 PM

@Rainbolt I that allowed?

Martin Büttner

@PeterTaylor thanks!

@overactor sock puppeting in general is allowed I think (Jon Skeet has at least on sock puppet account, and no one seems to bother, afaik)... colluding with your accounts probably isn't

@overactor Not working for me

I can't edit my messages anymore, virtually all of my messages contain typos, I'm doomed!!

Is the up arrow working for anyone else to edit messages?

Martin Büttner

yes

@MartinBüttner Pretty much. You're allowed to have multiple accounts as long as you don't use that to do something you couldn't do with just one of them (e.g. vote on something twice).

Martin Büttner

2:18 PM

you've only got 2 minutes to edit

Reloaded the page, now it works again, weird.

@MartinBüttner It didn't even work within 2 seconds.

Martin Büttner

oh okay

hi @algorithmshark ... how is Learn J in Y minutes coming along? ;)

Someone should make Learn Marbelous in Y minutes.

4

Q: Why doesn't water enter my body through my anus or genitals when swimming?

So when we swim, we can make water not enter through our nose and mouth, simply by holding our breath. However, the mouth and the nose aren't the only cavities. What about the anus and the genitals? They obviously can't "hold breath", so how do they stop water from entering? I thought the reason...

Martin Büttner

0

Q: False Positives on an Integer Lattice

Background When working on a 2-D grid of integer coordinates, you sometimes want to know whether two vectors (with integer components) have the same magnitude. Of course, in Euclidean geometry the magnitude of a vector (x,y) is given by √(x² + y²) So a naive implementation might compute this ...

fastest-code arithmetic floating-point

2:23 PM

Read the revisions to see the original title

Martin Büttner

@Rainbolt :D

I think what I need right now

If you're happy and you know it, syntax error!

Martin Büttner

happy was not expected at this time

oh damn, the memory limit

@Geobits would a 4GB as opposed to a 1GB limit help you significantly?

if so, I can probably test submissions if I close my browser :D

4GB is fine, sure, but if your intent is to not allow that much upfront computation, 1GB would be better for the challenge.

Martin Büttner

my intent is to be able to run the submissions without locking up my PC :D

2:30 PM

At this point I rather wish I hadn't asked, then I could post in ignorance since no limit was in the question :D

You may want to run a test to see if you can allocate whatever your limit is first, though.

Martin Büttner

why wouldn't I be able to do that on a 64-bit system?

@MartinBüttner I started it and then couldn't decide if I wanted to make a REPL call-and-response or just a program with comments.

Martin Büttner

@algorithmshark I think their standard is program with comments, no?

But J is a very output heavy language, since you're dropping arrays left and right and upside-down all the time.

@MartinBüttner I don't know how much memory your computer has total/free at any give time. I assume that either you do or you could run an allocation test with not much running, that's all.

Martin Büttner

2:35 PM

I've got 12 GB... I can usually free up 2 to 3 of those without closing my browser which is hogging at least that much again. I'm sure I'll find 4 GB spare somewhere

note to self: never edit close vote reasons into the auto-generated "possible duplicate of" comment

@MartinBüttner No, delete the auto-generated comment and post a new one.

Martin Büttner

why do votes on questions bother me more than votes on answers? :/

Because they have a bigger influence on the amount of answers the question attracts?

Martin Büttner

probably

but even on questions that are already "done"

BTW I think the 4GB limit is hilarious. I'm intending to stay within 4kB and L1 cache.

Martin Büttner

2:48 PM

@PeterTaylor that's why I didn't add one in the first place, but Geobits wanted to use over 6 and I don't think I can provide that

It was just an idea I had. I'm not sure if that's the final method I'd use, but I was trying to test something :o

Martin Büttner

sure, but if it's an idea you had, there's a chance someone else will have the same/a similar idea/a different idea which also uses tons of precomputation

I have a [code-golf] almost ready to post. How do I say "you need to do something other than this naive O(ridiculous) method because it needs an answer for large input in some feasible amount of time"?

Because the naive one is probably the shortest, golf-wise.

Martin Büttner

either restrict the time complexity like Optimizer did, or provide a test input that can't be solved in a reasonable amount of time with the naive solution

(I was referring to this question codegolf.stackexchange.com/questions/37556/…)

I thought about a large test input, but once anyone posts the correct output, anyone could copy/paste it and say they got it. So that really means only one person needs to do it smartly.

Martin Büttner

2:52 PM

well you could always test how long solutions take ^^

Ok, so if I restrict time complexty, the naive way is something like O(n^m). What is reasonable? I know one smarter way to do it, but there may be others. Should I just say "less than that"?

Martin Büttner

do you know the complexity of your smart way to do it?

Roughly, but I don't want to make that the only way to do it.

Martin Büttner

also, since you've got two variables... what's smaller than n^m? m^n? m^m? n^n?

well what is it? maybe there's a simple choice somewhere in between?

Give me a minute. Stupid math. The simple answer is O(fast) :D

I think I'd rather go with time, but that is hard to test in some languages (specifically those with online-only interpreters).

2:58 PM

@MartinBüttner Don't restrict the time complexity like Optimizer did. If you want to restrict the time complexity, please do it better than that.

Martin Büttner

@PeterTaylor well... I meant... in general...

I wish it worked like O(naive) and O(fast).

@algorithmshark Then there's omega(naive)

Martin Büttner

@PeterTaylor but I doubt Geobits problem will have an n^m complexity to read the input, so Optimizer's problem doesn't apply here at all

(or was there something else wrong with it?)

Well. Optimizer's question is still self-contradictory.

It asks for a linear time solution and also asks for a O(n+m) time solution, which is sublinear.

Martin Büttner

3:00 PM

ummm... how is m+n not linear in m and n?

It is linear in m and n, but a linear time solution should be linear in the size of the input, which is m*n.

Martin Büttner

ah okay

Ok, the faster method (that I know) is (I believe) linear in n.

Martin Büttner

in that case I wouldn't say it's contradictory, but he just failed to mention what variables it should be linear in.

So it's quite faster than n^m.

Martin Büttner

3:02 PM

@Geobits ask for a polynomial solution then?

or at least "complexity should be independent of m"?

I'm not entirely confident of my analysis o.o

Martin Büttner

then again n^n might be larger than n^m... I don't know what your n and m are

well if you don't share your problem and/or algorithm it's hard to tell :P

Either n or m can be the larger of the two, really.

And yes, I realize that :P

	long f(int min, int max, int count, int length){
		if(count==1)
			return 1;
		long num = 0;
		for(int i=min;i<=max;i++){
			int goal = length - i;
			if(goal <= max*(count-1) && goal >= min*(count-1)){
				num += f(min,max,count-1,goal);
			}
		}
		return num;
	}

That's the basic naive method. n=max-min+1, m=count.

length doesn't matter much. (well it does, but not for worst-case)

Yea, that, inclusive.

Martin Büttner

yes that looks like n^m, unless the if condition hits only in certain special cases

The if is hit mainly dependent on length. So it matters, but only to say that it decides if it's worst-,best-, or between-case.

Martin Büttner

3:10 PM

okay

So I want it more efficient than that monstrosity, but don't want to box out non-perfect solutions. I think poly-time works, just need to figure out how to phrase it.

Martin Büttner

I still really want to try and work out a regex-based golf course. but I'm afraid that won't work as well as I'd like it to. simpler regex problems are likely to be solved optimally fairly quickly. so I'd need to focus on obscure features/non-regular languages/maths. But then I'm afraid that there's only a handful of people who have the regex skills to even ponder participating.

I know just enough regex to not know enough to be dangerous.

Martin Büttner

(and just while I typed that my top-voted SO (regex) answer got another upvote :D)

@MartinBüttner There's no need to focus on specific obscure features, just choose a large enough pool of accepts/rejects that the trivial approach would be boring.

The trivial approach being |ing a bunch of substrings together.

Martin Büttner

3:20 PM

@algorithmshark I'm not thinking about the standard regex golf, which is just "match all of these but none of those". I'd rather actually pose computational problems to be solved with regex

(something like this codegolf.stackexchange.com/a/36532/8478)

(or this stackoverflow.com/q/12941362/1633117)

but if you choose simpler things like "Test a unary number for primality", there's a rather short optimal (and also well-known) solution.

Oh, that's neat. I never even thought of that.

3:41 PM

Hmm, how about something like this:

> To be considered valid for this challenge, you should be able to compute input 1 10 100 700 in under one hour on my i7. Given a more efficient algorithm than the one above, this should not be a problem. I will test any entries I believe may come close to the limit.

Martin Büttner

sounds good

go ahead and steal my views :P

Oh, I like yours. I'm going to start coming up with something here in a bit.

Just need to get this half-asked question tab off my browser first.

Martin Büttner

(I was kidding)

(I figured that)

Martin Büttner

I also realised that I should probably add my reference solution in Julia

but I've got that on my machine at home

so I'll do that tonight

Martin Büttner

3:55 PM

first sentence: avaialable

It never fails.

Martin Büttner

what's your stance on built-ins? :D I'm not gonna win anyway (because function names) but there's a very simple solution in mathematica

standard loophole, depending on what function it is I guess

« first day (1321 days earlier) ← previous day next day → last day (3520 days later) »

Transcript for

Sep '1411

The Nineteenth Byte

The Nineteenth Byte: General discussion for codegolf.stackexc...

join this room
about this room

00:00

06:00

12:00

18:00

all times are UTC

site design / logo © 2024 Stack Exchange Inc; legal

mobile