The Nineteenth Byte

Sp3000

00:05

@Optimizer Easily meets it, in the same way the Python one does too

It's basically O(n^2)

Rainbolt

00:18

@xnor @Optimizer Posted. Won't onebox it because the bot will have it soon, but here is the link.

New Meta Posts

0

Q: Is a broken question automatically dead unless the original poster fixes it?

A challenge was recently posted without a winning criterion. I added one. The revision was then rolled back and I was told that only the OP could make functional changes to a challenge. I disagree with this reaction. If the OP is a newbie and demonstrates a complete lack of knowledge about how t...

discussion

Rainbolt

Pfffft ninjad.

Optimizer

You forgot to mention that the quesiton was put on hold

as unclear

I think its crutial in this case.

@Rainbolt ^

vzn

01:49

hi all. any Boy Scouts around?

heard of at least 2 in here awhile back.

wondering if anyone has any experience with the programming/ robotics/ video games/ controller badges etc.

fyi decided to finally write this up. list of CS-related badges & links to details.

in Computer Science, 6 hours ago, by vzn

also plz feel free to contact me if anyone is interested in a prj using genetic algorithms for scientific research. thx!

Nathan Merrill

what do you guys think of google's project ara (the modular smartphone)?

I personally wouldn't get one unless its popular, because it is only useful if it still used 5+ years down the line when I can install new modules

However, if everybody has that attitude, then it won't ever get popular

feersum

02:04

Sounds like a good idea to me. I can refrain from buying a camera module, thereby thwarting the NSA from seeing me. bwahaha!

Optimizer

or you can simply turn off data connection

feersum

why would I want a smartphone without internet connection ??

Optimizer

same goes for camera

Nathan Merrill

I think a good use would be batteries

If they make it possible to have multiple batteries installed

I know for sure they have an internal battery that will allow you to swap batteries in and out without killing the power

Nathan Merrill

03:15

something is wrong about my approach, but I don't know what:

I'm calculating the number of 0s at the end of n!

isn't it just int(n/5)?

because the only way a 0 gets added is by multiplying by 10, and multiples of 2 is plentiful, so 5 is the restricting factor

oooh, 25 is my exceptional case

thanks, chat, for allowing me a place to debug my problems

2

Geobits

The best rubber duck ever. Sometimes it even talks back :D

Nathan Merrill

03:36

I'm curious, as I don't really participate in code golf:

what makes good code-golf problems?

aka, there's always the standard tricks to save a few bytes here or there

but beyond those tricks, what makes a given program funner to code golf?

or is it simply the enjoyment of programming a particular program, and code golfing is an excuse to program it?

feersum

it's not really hard to make a decent code golf question. It can be anything as long it is specified clearly and objectively, and is not excessively trivial or difficult

Nathan Merrill

I'm not talking "good" as in "acceptable to our community guidelines"

I'm talking "good" as in "enjoyable"

Geobits

I like 1) Something interesting to me (obv very subjective) and 2) something that can be done with more than one or two "obvious" approaches

But I'm not the golfiest golfer around.

And I mostly use Java for it, so lose most golf cred I do have ;)

feersum

if an exact algorithm is proscribed, that does make it a bit dull

Nathan Merrill

ah, I can see how the multiple approaches would be appealing for golfing

I'm starting to not enjoy this code chef site...as it gives me out of time errors with good solutions

simply because I'm using python

feersum

03:41

no offense but that's funny!

Sp3000

It's definitely multiple approaches for me - what works well in one language might not work as well in another and it really emphasises a language's features

Geobits

You should probably be using Chef on a code chef site :P

Nathan Merrill

lol

Sp3000

Also 25's not the only exceptional case, it's basically anything that can be divided by 5 more than once

feersum

I like python, but I never use it if there's any questiin of runtime efficiency

Nathan Merrill

03:42

bah, they don't support Chef

I know @Sp3000

feersum

finding number of factors of x in y = every 3rd project Euler

Nathan Merrill

this is a little bit different as I don't want to factor out 1000000000!

but yeah :P

but seriously, they are expecting me to process 100K lines of output in 8 seconds

feersum

on another site I've even had problems with Java's I/O taking more time than the entire allotment

Sp3000

Why 100k lines?

Nathan Merrill

04:00

that's what they test on

they said in the problem description that they would pass around 100K lines

globby

04:49

@Sp3000 your answer to my question is invalid

It isn't implementing a heap, it is simply operating on a list

Sp3000

Python heaps are lists though

Did you mean a class or something?

feersum

@globby I don't see any reason why even a sorted flat array couldn't be used to satisfy the spec

globby

That's not implementing, that's using a built in type that functions as a heap (more or less)

I guess I didn't clearly specify what I wanted

feersum

or rather, a linked list instead of a flat array

globby

a linked list would be more or less acceptable if actually implemented

well even then

feersum

04:52

discard old linked list, bubblesort, and create new linked list after each operation, lol

Sp3000

Well I thought the array implementation was pretty common, so that was the first thing that came to mind...

globby

Yeah but note that those are pointers to the child elements

I did clearly say implement the Heap data type

Granted

I do see how that could meet the spec, I should re-word things

If implemented with actual pointers

feersum

ooh, even better idea

make it an (N-1)ary heap

Sp3000

I don't think those are actual pointers though

feersum

have the max element, and then a list of all the other ones

Sp3000

04:55

You don't need pointers because you can always calculate the children/parent from the current index

globby

@Sp3000 touche. Would the updated question make it more clear?

(Under clarifications)

From what I can see, the haskell solution meets what I wanted

Sp3000

Well the Haskell one is a data type, but it basically operates by converting to a list and back again from what I can tell

globby

It has a custom heap type which is linking everything together and creating a tree

Sp3000

Oh, ok

globby

data Heap=Heap Heap Int Heap|Empty

I assume that the first two heaps are children, the int is the value, and the other heap is the parent

The list conversion is all legal because he defined:

`toList Empty=[]`
`toList(Heap a x b)=x:toList a++toList b`

and used that throughout

Sp3000

05:03

So if we have a heap structure and methods to convert to/from a list, that's okay?

globby

Yes, because you are still implementing the correct heap structure. As long as the methods somehow restructure it as a heap and return it, then I think that using list conversion is actually a cool way to solve the problem

Martin Büttner

07:44

@Optimizer you keep the saying that powers of 2 question was closed as being unclear and that that's very relevant. afaict it's been closed as missing a winning criterion. what am I missing here?

Peter Taylor

07:59

@feersum I have a base class for my Java Project Euler solutions which includes various number theory methods and a lookup table for primes.

@globby An array which is carefully maintained is the standard implementation of a binary heap. No-one implements it with pointers in the real world.

2

@globby To be honest, given that one of the articles you links to talks about the word "heap" being in general use for any priority queue, I think you should specify that you want a particular type of heap. And if you want binary heaps, you really need to state that: at present you have no argument that someone implementing an n-ary heap fails to meet spec, so it's only necessary to identify the least element.

Lembik

10:29

hi all

another challenge idea involving binary strings... :)

TheBestOne

13:16

I just found this. Looks useful. :D

Nathan Merrill

14:14

cool how it tracks keystrokes

definitely possible to abuse, but pretty awesome

Nathan Merrill

15:37

hey, I have an idea for code bowling

the biggest problem is all of the things you can do to make a problem longer

however, if you make it cops and robbers style

where the cops try to reduce the program (with a max levenstein distance of 7)

and variable names have a max length of 3

would that work?

for being mid-workday, its surprisingly quiet in here

Nathan Merrill

16:38

ah, I just did a search, looks like its already been done

hmm....I still think it hasn't been done justice

Nathan Merrill

17:01

the latest what if is quite epic what-if.xkcd.com

3

Geobits

Yea... I've been waiting for a good opportunity to use the phrase "I'd rather be swimming on the moon" since I saw it, but it hasn't come up yet :(

Lembik

hi all

I have another fiendish binary string challenge if anyone wants to hear it :)

Rainbolt

"and swimmers would be able to jump out of the water like dolphins." that was my first thought verbatim. Is it even correct to use the word verbatim when talking about thoughts?

runs to ELU

Lembik

@Rainbolt "precisely" would do

unless you thought was actually in textual form

Geobits

I think so, as long as you accept that you think in words. A common definition for verbatim is "in exactly the same words as were used originally".

Rainbolt

17:16

Ok cool. I wanted to communicate that not only did I think the same thing, but my thoughts used the exact same words as they floated through my head, so I guess that works.

Lembik

yes!

Rainbolt

With permission of you guys I use this phrase from now on.

Lembik

@NathanMerrill thank you for the comic!

Nathan Merrill

yep!

Geobits

Well at least you sought our permission first this time. Please continue to follow this procedure in the future ;)

Lembik

17:21

so... about my new puzzle.. I would prefer to have live chat about it before putting it in the sandbox

if possible

but if no one is interested.. sob...

Geobits

Drown your tears in spec. Until you say something more about it, nobody knows if they're interested.

Lembik

ah ok.. so here goes :)

consider two binary strings A and B

A has length 2n-1 and B has length n

now consider the binary output array that just tells you if B matches A[i,...,i + n-1] for each i

make sense so far?

for a given string B, there are a number of different possible output arrays

Geobits

Depending on where you start in A I assume.

Lembik

you could find them all by iterating over all possible strings A of length 2n-1

@Geobits the output array has n binary values. A 1 at position i means B matches A[i,...,i + n-1]

you get a 0 at position i otherwise

Geobits

Gotcha.

Lembik

17:25

cool.. so...

given input n, your task is to find a B which maximises the number of possible output arrays . You should also output how many that is

say n = 2

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

Robbers' Thread In this challenge, your goal is to write a function that accepts a integer N, and that function will return the first N primes. However, you must do this in the most characters possible. However, after posting your answer, the cops will have the opportunity to crack your code b...

Lembik

then B = 00 will give 4 possible output arrays

you can get 00, 01, 10, 11

but try n = 3

it is already more interesting

can you find a B which gives 2^3 = 8 different output arrays?

Geobits

That feels like there should be a closed form solution (with a pattern dictating the actual B), but I don't know offhand if that's true (or what it would be).

Lembik

@Geobits well.. that would be nice too :)

Geobits

It would be nice to find, sure, but it wouldn't make a great golf if it's found to be "do this explicit formula".

Lembik

17:29

@Geobits if there is an explicit formula. I mean I don't know that there is

I certainly haven't found it

Geobits

Right, that's why I said I wasn't sure. I'm not the most mathy one here by any means. I mentioned it as something to look out for if you hadn't considered it yet.

Lembik

ah ok.. I did consider that but haven't found it

I suppose I could ask on math.se first.. but I would rather not

Nathan Merrill

Heh. I can star my own sandboxed posts

Lembik

@Geobits I was going to make it a code challenge

I don't like pure code-golf ... :(

Geobits

What's the win criteria? Highest n?

Lembik

17:34

@Geobits yes

whcih clearly doesn't work if there is a closed form solution!

Geobits

If that's the case, you probably should ask on math.se to make sure.

Or just accept that someone might break your challenge :P

Lembik

I don't mind breaking as that person would win :)

I have another variant where the output array is the edit distance :)

but that seems a lot harder

i mean the output array is an array of edit distances

Nathan Merrill

Hey @MartinBüttner what do you think of this: meta.codegolf.stackexchange.com/a/4665/20198

Optimizer

@NathanMerrill I think similar challenges have been done in the past. Also, the need to print first n prime numbers, has not been done as is, but this has that along with something else

Martin Büttner

@NathanMerrill
a) It *is* pretty similar to the previous one, although the restrictions make it a lot harder.
b) You've swapped the meanings of Cops and Robbers compared to older challenges. I agree that both interpretations make sense, depending on your point of view, but to minimise confusion I think we should probably be consistent throughout the tag.
c) I think a week works better than 72 hours.
d) It's interesting that there's not guaranteed to be a possible crack.
e) This might be too easy for the robbers (cops in old challenges).

Lembik

17:46

I do like this cops and robbers model

Optimizer

@MartinBüttner did you try the APL code with the last two test cases ?

Martin Büttner

@Optimizer just now. finishes immediately

why wouldn't it? looks O(N^2) to me.

Optimizer

I did not bother understanding the algorithm :)

too busy training my cars

Martin Büttner

lol

Optimizer

hang ten is really something

Nathan Merrill

18:13

Thanks for the feedback @Optimizer and @MartinBüttner

@MartinBüttner I switched cops/robbers. I'm curious why you think it'll be harder for the (now) cops. All the robbers have to do is find 1 small tweak that'll make it shorter, which happens all the times in current code golf to completely remove the submission from the running.

Martin Büttner

@NathanMerrill I think it will be easier for the cops.

But I think that's what you meant to say.

I think the Levenshtein distance ≤ 10 makes it harder for the robbers. I'm sure there are ways to ensure that any shortening needs more than 10 changes.

Nathan Merrill

the only way I could think of was really long variable names

but now that I think about it, that doesn't really matter

only the number of times you use a variable

well, I'll post it and see

Optimizer

18:31

@NathanMerrill There is no point in posting to sandbox if you are going to take it off in 30 minutes

6

Nathan Merrill

@Optimizer yes there is. To have people read it

which happened :P

Optimizer

is it a joke to you ?

Nathan Merrill

no?

Optimizer

why post it to sandbox then ? post it directly to main site, many people will read it .

Nathan Merrill

sure, but I'd rather see its feasibility and get feedback to improve it before posting it

the length of time doesn't matter to me

the feedback does

Optimizer

18:33

the feedback you are talking about was just 2 people's personal POV

Nathan Merrill

sure

Optimizer

this is not going anywhere.

Martin Büttner

@NathanMerrill naming the cops' thread with "Robbers" and vice versa is a bit confusing

Nathan Merrill

Bah, I hoped that that was made obvious with the H1 at the top of the thread

Martin Büttner

there was no h1 in the robbers' thread which I clicked on first because I took it to be the cops' thread ;)

Geobits

18:44

^ Makes me a sad panda

4

Instead of a header, maybe just put (cops) or (robbers) in the title itself. There's no way to differentiate them now without clicking in.

Nathan Merrill

Ok

Lembik

19:43

hi @MartinBüttner

Martin Büttner

hi

Lembik

@MartinBüttner just posted a new binary string challenge to the sandbox :)

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

An input with many outputs Consider two binary strings A and B of length x and 2x-1, respectively. Now consider a binary output array Z of length x where Z[i] is 1 if B = A[i,...,i+x-1] and 0 otherwise. For a given fixed B, there are a number of different possible output arrays Z. You can find...

Martin Büttner

20:01

@Lembik sounds fine to me

Lembik

@MartinBüttner great!

Rainbolt

20:18

It bugs me that the English language has no contraction for "it is not". You have to choose between "It isn't [...]" or "It's not [...]"

Haha of course there is a post for that: english.stackexchange.com/q/15001/72792

Lembik

the answer is quite right

at least not in British English

journals.cambridge.org/action/… :)

it's all about class :)

Rainbolt

Go kick some ELU ass @Lembik.

Lembik

:)

Optimizer

No. It's all about the bass.

Lembik

the fish?

Geobits

20:26

@Rainbolt t'isn't something that's ever bothered me :P

Rainbolt

The one contraction I miss from high school: Ur

Optimizer

@Rainbolt no

Rainbolt

It avoids the major problem of "Your" vs "You're"

"Ur ur own worst enemy."

Martin Büttner

that should be "u r ur own worst enemy."

:P

Geobits

It's only a major problem if you're illiterate ;)

Rainbolt

20:33

Martin why are you room owner? I keep thinking I'm in the wrong room.

Geobits

He was dubbed Sir Martin of The Nineteenth Byte.

(or room owner, if you must)

Yay for edits that make my replies look pointless!

Rainbolt

I like turtles.

Geobits

I'm not entirely sure why, but it was around the time the room for the weekly challenge was opened, so I think that had something to do with it.

He's also epic enough to own this place.

Turtles, you say? Fair enough. Turtles are epic as well.

Martin Büttner

@Rainbolt Because Doorknob added me to the room owners I guess.

(and if you wanna know why he did that it was because I wanted a post unpinned and another one pinned and he was on mobile)

Jan 9 at 18:58, by Doorknob

@MartinBüttner Thanks! I'm busy at the moment, but since you're obviously not going to abuse power or anything...

Geobits

I'd rather think it's because you told him to. Stop proving my pet theories wrong.

Martin Büttner

20:47

@Geobits I'm more subtle than that. ;)

Rainbolt

I tried to reply with @SirMartin but it didn't work. Geobits lied.

Geobits

Not my fault you didn't use his full title when I even spelled it out for you.

Optimizer

codegolf.stackexchange.com/a/44571/31414 - is this entry correct ? If yes, what is there to that cops and robbers apart from 2 individual questions (duplicate of each other) asking for a program for printing n prime numbers ..

(with some source restriction)

Geobits

Seems valid to me. I feel the first few will be like this. It will take something very creative (or simply very golfed) to stop minor changes from shortening it.

Optimizer

but the question asks for as non golfed as possible

Geobits

21:01

Ironically, the best/easiest approach might just be to golf it well in a language that's really bad at golf.

Optimizer

I just want to confirm, so the robbers have to simply change at max 10 characters from the cops entry and still leaving the program as is ?

Geobits

And I believe the new entry must be shorter by at least one character, but yes.

So you could bump your distance up to 10 by removing another character from the function name to lower your score.

Optimizer

@Geobits I don't see why more answers will make the robber's task difficult.

Geobits

Not necessarily more, just later ones tend to be more difficult. The originals see what worked and what didn't and get more creative later, from what I've seen.

Optimizer

I see.

still, I don't understand the point of having most non golfed code. Since that is in turn making robber's task easier

Sigh, all these points should have been discussed in the sandbox post. Only if

Geobits

21:07

I agree. Like I said, a golfed entry in a verbose language would probably do well.

Optimizer

I guess it might get loads of answers as it gives a sense of accomplishment to the robbers.

Geobits

Meh. The only reason a robber should bother to even crack a long entry is if they also posted a (shorter) cop that's still uncracked. They can't (reasonably) win the robber thread by cracking long ones, due to the scoring method.

Off-topic: New parents are funny... "My baby doesn't go to sleep right away"

Optimizer

lets see if any of the bigger fishes participate

on a sadder note, the lego movie was not nominated in oscars in animated movie category ..

Geobits

I just saw that last week. It was much better than I expected it to be :D

Rainbolt

@Geobits Such arrogance "Most babies here (in Belgium) sleep full night from the age of like 3 months without using any technique [...]" Bartdude 11 hours ago

Optimizer

21:16

yeah, they added in big hero and a few others in that category and left this one out :/

@Geobits oh, aren't you like a kid ? :P

Rainbolt

I shed a few tears during Big Hero 6

Geobits

@Rainbolt Yea, I really only visit that site for the strange responses people give :P

Optimizer

@Rainbolt I asked a friend how it was and he said HTTYD2 was way better, so I did nto watch it yet

Geobits

@Optimizer Like a kid? Sure, I'll accept that gladly :)

Optimizer

it would be wrong to call a 14 yr old a kid, :P

Rainbolt

21:19

"Are you satisfied with my care?" :*-(

Geobits

Wait, I think you have me confused with Doorknob. I'm not close to 14.

Optimizer

oh wait, the other one was cfojure not you..

my bad.

Rainbolt

@Optimizer I thought HTTYD1 was better than Big Hero, but I thought HTTYD2 was worse (just barely worse).

Geobits

My kid is closer to 14 than I am :(

Optimizer

@Rainbolt oh, I personally liked the trailer of Big Hero, just did not go to theater to watch it due to the friend's response. I'll have to watch it by other means now

Rainbolt

21:22

@Optimizer rainiertamayo.com/movie/big-hero-6-2014.html

Unfortunately not in 720p. Some of his movies are, but not that one.

Optimizer

780 ?

Geobits

Why have I never heard of this site before now?

Rainbolt

I've been using since Isohunt shut down a few years ago

Optimizer

Also, I think my other means are better and equally illegal ;)

full movie on youtube. DMRC hammer on its way .

Rainbolt

I cannot vouch for the accuracy of this quote "Rainiertamayo, falls within a grey area within the internet media rules. This website is ran by a single man who is actually buying the rights to very popular Hollywood movies and TV shows. Due to the fact that the man literally owns some rights to the multimedia, it's legal for him to post them online, free for anyone to stream the content. He asks for no donations, or compensation in anyway, he's just a true believer in free entertainment. "

Taken from here

I mean, it really seems false given that some of the movies he posts are still in theaters.

Optimizer

21:26

"buying the rights to very... " as in buying the movie ticket or DVD ?

Rainbolt

No idea. I don't know why I even quoted it. It seems wildly inaccurate now that I think about it.

Nathan Merrill

@Optimizer I don't understand why its a huge problem that the question was only on the sandbox for 30 minutes. Many questions never even appear there

Optimizer

And that is there call.

but if you post it to sandbox, you are requesting for feedback.

Nathan Merrill

true

Optimizer

all the comments coming in in the actual post would have been sorted out initially itself.

I will now demonstrate an example.

Nathan Merrill

21:40

only the first two

and technically, yours

Rainbolt

@NathanMerrill You can sandbox challenges for thirty days, thirty minutes, or choose not to use it entirely. It's just a (very useful) tool that exists for those who want to use it. Who told you otherwise?

Nathan Merrill

Optimizer thinks I should have kept it there longer

I know there's no required minimal time :P

Optimizer

@Rainbolt but he actually wanted to use it.

and for that matter, I think 30 minutes was very less of a time to get a useful outcome for any post on sandbox.

Nathan Merrill

Optimizer, I will give you this. I should have kept it longer due to the scoring on the robbers

Rainbolt

@NathanMerrill Oh. It sounded like there was a "huge problem"

Nathan Merrill

21:46

however, I'm still ok with the status of the cops post

nah :P

Sp3000

It's good to keep it in the sandbox for a day or so even if nobody looks at it, because you might realise something's wrong yourself after you posted it

Just gives you more time to double check :)

Rainbolt

I'm studying the comments on the recently posted challenges, and it looks like quite a few good points were made after the post was 24 hours old.

Sp3000

Also Nathan you have a typo with distacne, just wanted to point out

Nathan Merrill

@Optimizer I can't get the "try it online" to work. I just copy/paste the code and input, and press submit, right?

Optimizer

You have to call the function

its just a function

I have given an example of how to call it

Sp3000

22:15

Hmm total max Lev dist makes it seem like if I have an answer with a distance of 2, I'd want to randomly change 8 more chars somewhere just to maximise the score...

Optimizer

obv

why would you even have an answer with distance 2 to begin with ? :P

Sp3000

Maybe someone had a bad cop :P

Optimizer

then it clearly means that you cannot randomly change 8 more chars :P

Sp3000

But my point is that seems like it just encourages meaningless edits, like //2 becomes >>1

Optimizer

oh

yeah

Transcript for