The Nineteenth Byte

Alex A.

00:13

@MartinBüttner: PPCG question for you.

Would "tips for creating a challenge leaderboard" be on topic here?

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

Birthday Paradox with Leap Years code-golf probability-theory Background The birthday paradox is a popular problem in probability theory which defies (most people's) mathematical intuition. The problem statement is: Given N people, what is the probability that at least two of them have the...

Martin Büttner

@AlexA. Ummm, I don't think so. What exactly would be asking for?

Alex A.

Tips... on creating a leaderboard.

I don't know how but I'd like to.

They're becoming increasingly common in challenges, so it seems like a reference for folks who'd like to include them in their challenges would be a good resource to have.

Martin Büttner

just copy mine :P

well I could make it a meta post

those are increasingly common.

Alex A.

Haha

I just like to know why it should be done a certain way. Basically I'm a knowledge whore.

Martin Büttner

00:23

I don't know, I just went with the most practical approach

(scrape the data from the SE API, parse the headers with regex, and build a HTML table)

I don't know if there's a reasonable other way

Alex A.

Ah, okay.

I looked at Calvin's leaderboard code once and there was all sorts of JavaScript and I was simultaneously impressed and confused.

orlp

@MartinBüttner I wonder what algorithm would be fastest for these kind of numbers

in the past I've used pollard-brent

although pollard-brent is kinda complicated

randomra

@MartinBüttner A meta for your snippet's usage would be nice.

Alex A.

^ Agree

Martin Büttner

@orlp I couldn't tell, I've never looked into factorisation algorithms.

orlp

00:31

oh

it's pretty cool

I did an optimized implementation once

Martin Büttner

@randomra @AlexA. Yeah, as well as the unminified code I guess. I'll try to get it up on meta tomorrow.

orlp

@MartinBüttner are you familiar with montgomery multiplication?

Martin Büttner

nope

one day I will learn some number theory...

orlp

it's a fast way of doing a*b mod m

if m stays the same a lot

really cool stuff

Alex A.

It was invented in Montgomery, Alabama

Martin Büttner

00:33

well, I need to head off... got a meeting tomorrow morning.

@PhiNotPi btw you never accepted answers for unscramble the source code.

Alex A.

@MartinBüttner Goodnight! Hope your meeting goes well.

orlp

@MartinBüttner a really cool property of my implementation was that it wasn't deterministic

and I abused that by simply not accounting for integer overflow at all

it was faster to just redo trials when something went wrong then to check for it :P

PhiNotPi

00:53

Me: "There's a helicopter outside." Dad: "That's where they belong."

sirpercival

how does .d work in pyth? it's non-intuitive to me

like, .d,1z should create {1:z}, right?

but i get TypeError: cannot convert dictionary update sequence element #0 to a sequence

sirpercival

01:14

nvm, i got it. .d,,1z works

TheNumberOne

01:56

@orlp How to load a constant into a variable?

PhiNotPi

If I were to learn the Chapel programming language, could I turn my laptop into a supercomputer?

^ urgent

PhiNotPi

03:19

Nothing like staying up late at night summing infinite series...

PhiNotPi

04:25

...still awake...

Is anyone on here willing to help with a homework problem?

(I know the answer, but I can't prove it)

For what values of p does the following series converge?

(log(k) should really be ln(k))

The answer is, I think, p>1

I think it's going to be a two-part problem...

3 part, actually

:/

:(

This is awful

PhiNotPi

05:06

Finally, I proved it. It converges when p > 1.

I feel like there should be something called "proof golfing."

New Sandboxed Posts

05:53

0

A: Sandbox for Proposed Challenges

A Golf of Two Cities code-golf kolmogorov-complexity Write a program in as few bytes as possible to output the opening sentence of A Tale of Two Cities: It was the best of times, it was the worst of times, it was the age of wisdom, it was the age of foolishness, it was the epoch of belief, ...

orlp

@TheNumberOne mov a, 42

Whenever a register is used as an operand you can use an immediate value instead.

orlp

06:12

@PhiNotPi that should be >= 1, no?

k*log(k) goes to positive infinity, so 1/(k*log(k)) goes to 0

and then you can write k^p * log(k) as log(k^(k^p)) for the p < 0 < 1 case

and I don't see how that doesn't converge either

so p>0?

aaaaaaaaaaaaaaaaaaand I'm being stupid

scrap all that above

Optimizer

scrap scrap scrap scrap scrap scrap

orlp

you're interested whether the sum converges, not the value

@Optimizer trust Optimizer, always there when I need him

Optimizer

06:28

yay, I am back on my 5 upvotes per answer average :D

33/8 more to go

New Sandboxed Posts

07:28

0

A: Sandbox for Proposed Challenges

Counting in pyramids code-golf numbers You should write a program or function which receives a list of non-repeating integers as input and outputs number of occurrences of each of the input numbers in the following upside-down number pyramid. Starting from the original list in every step we cr...

orlp

07:39

sweet

write_int:
    divu o, m, o, 10
    jz write_int_done, o
    call write_int
write_int_done:
    add m, m, ord("0")
    sw -1, m
    ret

Martin Büttner

08:39

@randomra if you need a reference implementation to generate test results: cjam.aditsu.net/#code=q~%5D__%2C(%7B_2ew%3A%3Ae%3E%7D*%5D(%5Ce_fe%3DS*&inp‌ut=5%202%209%201%206%200

ugh, why didn't I expect that...

goo.gl/az7iim

randomra

@MartinBüttner Thanks, have one but it doesn't hurt to double check :)

I find it a bit easy though

Optimizer

haha ew

randomra

but the O(n*log n) is quite difficult for golfing (in the way I solved it)

Martin Büttner

@Optimizer I believe that's the shortest way to do generalised differencing now

I tried with vectorised operators as well, but that always came out two bytes longer

Optimizer

oh, is that a challenge ? :P

Martin Büttner

08:45

sure, why not. you can start working based on this if you want:

[5 1 2 6]
e#{_@e>\}*;]
e#_1>\W<.e>
e#_,(ew~.e>
e#2ew::e>

Optimizer

@randomra s/non-repeating/unique ?

Martin Büttner

s/unique/distinct/

randomra

what is this syntax?

Optimizer

vim

replace

Martin Büttner

perl replace

anything really

I think it actually works in some chats (Skype. might work in gitter. don't know about IRC)

orlp

08:52

def. not irc without client extensions

Martin Büttner

k

randomra

weird, never saw it before, s as in replaces? :)

I only know the language ///

orlp

s as in substitute

randomra

ahh, I see

aditsu

I've seen an irc bot that parsed substitutions and responded with "X meant to say ..."

also, sed uses that syntax too :)

btw, the choice of "ew" in CJam is meaningful

Martin Büttner

09:04

s/$/ to me/

aditsu

hehe, let me make an image

Martin Büttner

no I think I can see it ;)

Optimizer

@MartinBüttner 24 bytes

Martin Büttner

kk

might try to improve mine later

could you shorten the generalised differencing?

Optimizer

no, I followed a different algorithm

which requires a few new tricks ;)

Martin Büttner

09:10

k

Optimizer

literally

@randomra planning to posting it soon ?

Martin Büttner

@Optimizer dude, it's been in there an hour. we always try to encourage people to leave it there for at least a day, so don't start rushing it, because you're impatient to post your solution. :P

Optimizer

@MartinBüttner dude, I didn't say NAO, I said soon :P

Don't be jelly that I have a shorter solution :P

Martin Büttner

@aditsu What do vectorised operations do for unequal lengths? just append the elements of the longer vector? I would have expected it to either wrap or truncate the shorter one.

but if you just append the original array then you potentially end up with different types where you don't expect them

Optimizer

they work just like z

Martin Büttner

09:16

that's a shame :/ ... if I wanted z, I'd have used z :D

Optimizer

lol

aditsu

Optimizer

What ?

Martin Büttner

@aditsu beautiful

Optimizer

ugh, sans font in chat

Martin Büttner

09:17

that was really not how I pictured it :D

aditsu

@MartinBüttner yeah [1 2 3][1 2].+ -> [2 4 3], since 2+2=4 and 3=3

Martin Büttner

right but that's weird if you do "def""ab".-

randomra

@Optimizer tomorrow probably

Optimizer

@randomra cool

@aditsu but how does the image relate to this ?

Martin Büttner

@aditsu if you truncated, then we could save another byte on generalised differences. (_1>.op instead of 2ew::op)

@Optimizer it doesn't. it's the explanation for why it's ew.

@aditsu btw, this is why I thought it's w:

1  2  3
 \/ \/
 12 23

aditsu

09:21

that's a similar idea

Optimizer

@MartinBüttner ohhh

randomra

(hmm, a new language using only the "topology" of the (individual) code characters...)

Optimizer

in recent times, has CJam ever won over Pyth ? (in competitions where Jakube has participated)

or rather, what are the number...

I can smell a new CHallenge being cooked up

PhiNotPi

10:17

Is it normal to have 6 of the newest 15 questions on hold?

Optimizer

define normal

orlp

!abnormal

PhiNotPi

10:35

With Evolution of OEIS (also known as EOOEUS), I'm thinking scoring could be votes multiplied by a function of its depth on the tree (maybe SQRT()?).

SO then scoring would be votes * sqrt(level)

On the other hand, I feel like there should be a golfing aspect.

randomra

10:55

@PhiNotPi I vote for golf+depth based score. If you write a snippet maybe votes could be added somehow. Idk how that worked out in the past.

FUZxxl

Hello!

@randomra I'm unsure how to get partitions right.

orlp

@Optimizer Pyth > CJam

suck it haters

randomra

@FUZxxl I posted a code for it in the comment. (<@(<;.1)~1,.2#:@i.@^<:@#) 'abc'

PhiNotPi

@orlp Shouldn't it be Pyth < CJam if it's a golfing contest?

orlp

@PhiNotPi > here means 'better than'

FUZxxl

11:01

@randomra Looks like it could work.

Zgarb

@Optimizer Martin's CJam answer beat Jakube's Pyth by 1 byte here

FUZxxl

I'm leaving for lunch now.

orlp

@Zgarb this is unacceptable

@FUZxxl have you written any GOLF yet?

if yes, how's it going so far?

PhiNotPi

I need to create a language called Prl based on Perl like how Pyth is based on Python.

Optimizer

@orlp numbers or it didn't happen

orlp

11:12

@Optimizer 42, 1, 2, 3, Python > CJam, 4, 5, 6

there

plenty of numbers

Optimizer

@orlp proof or it didn't matter

orlp

I don't have a proof, but I can cite an authority on the matter

15 mins ago, by orlp

@Optimizer Pyth > CJam

Optimizer

self referencing is never called citing

I am genuinely trying to find numbers here, so trollers be gone

@aditsu is it possible to make List 0 ew work ?

orlp

11:27

@Optimizer you can look at the stackexchange dump, download PPCG, and programmatically extract the smallest answer, and check if it's Pyth or CJam

Optimizer

@orlp no thanks.

aditsu

11:46

@Optimizer what is that supposed to do?

Optimizer

just kind of a no-op

creates length many empty arrays

because in general, you don't have a way to create an array of 1 to N

so combining ew somehow with , requires an additional step of :)

aditsu

o_O

Optimizer

N,few will never work

where N is a number

FUZxxl

12:14

@orlp I haven't actually! I'm still thinking and I have some calculus homework to do.

And I asked a question in the meanwhile:

11

Q: Is it legal to call memcpy with zero length on a pointer just past the end of an array?

As answered elsewhere, calling functions like memcpy with invalid or NULL pointers is undefined behaviour, even if the length argument is zero. In the context of such a function, especially memcpy and memmove, is a pointer just past the end of the array a valid pointer? I'm asking this question ...

TheNumberOne

12:25

@orlp I'm now getting a struct.error: unpack requires a bytes object of length 8 when I try to read from address -1.

orlp

@TheNumberOne you have to use lw/sw when reading/writing to/from -1

or is this a different error

TheNumberOne

I'm using lw

orlp

give me a sec

post full trace please

actually, what you say should be impossible

are you sure you got the order right?

lw c, -1

TheNumberOne

orlp

@TheNumberOne git pull

you have an outdated version - there is no struct.unpack on line 80

TheNumberOne

12:29

ah. okay

orlp

fixed in new version?

FUZxxl

I think my brain just exploded with respect to the aforementioned question.

TheNumberOne

@orlp Nope, it's not :(

Martin Büttner

any comments for meta.codegolf.stackexchange.com/a/5136/8478 ?

TheNumberOne

@orlp It could just be Windows I/O

orlp

12:41

@TheNumberOne can you post a minimal assembly example that does this?

that doesn't spoil your answer

TheNumberOne

    call read_int
    halt 0


read_int:
    mov x, 0
read_int_loop:
    lw c, -1
    cmp q, c, ord("\n")
    jnz read_int_done, q
    sub c, c, ord("0")
    mulu x, d, x, 10
    add x, x, c
    jmp read_int_loop
read_int_done:
    ret x, c

directly copied from one of your examples.

orlp

you see

I'm confused

open up golf.py

go to line 69

that checks for -1, and it should never get to line 84

@TheNumberOne what command do you use to compile and run?

in particular, did you recompile after git pull?

TheNumberOne

python as.py factor.golf

python golf.py factor.bin

Python is python3 on my system.

@orlp yes i did.

orlp

after line 68

(` def load(self, a, width):`)

insert print(hex(a))

TheNumberOne

weird. it's working now.

orlp

12:52

does it break again when you remove the print(a)? :P

if so we have a succesful heisenbug

TheNumberOne

no, it doesn't... that's very unusual.

orlp

I think you might've not recompiled before running again, or the file was in use, not allowing python to write or something

by the way, I made a better write_int than the one in the examples right now

5 hours ago, by orlp

write_int:
    divu o, m, o, 10
    jz write_int_done, o
    call write_int
write_int_done:
    add m, m, ord("0")
    sw -1, m
    ret

aha, the file being in use is plausible, maybe I can close the files more aggressively

isaacg

Hey everyone, my chrome doesn't seem to like the meta site's certificate

orlp

@isaacg same here

I don't use https on SO though

isaacg

It says it's a cloudfare certificate, not a SE certificate

Main site is working fine though.

orlp

13:00

@ChrisJester-Young ^

Martin Büttner

13:40

0

Q: Pedantic Birthday Paradox

Background The birthday paradox is a popular problem in probability theory which defies (most people's) mathematical intuition. The problem statement is: Given N people, what is the probability that at least two of them have the same birthday (disregarding the year). The problem is usually...

code-golf probability-theory

grc

@MartinBüttner wow you have 40k rep already :O congrats!

you were on about 20k not long ago

Chris Jester-Young

14:00

@orlp Thanks, I'll pass that on to the dev team, though TLS certs were wonky for meta even before our CloudFlare transition anyway, as far as I remember.

Nick Craver

@isaacg correct - meta sites do not support SSL/TLS

(meta.<not stack exchange> are special exceptions with valid certs)

Martin Büttner

@grc thanks :)

I think it's been almost exactly half a year since I hit 20k. I've got a screenshot from 28 October.

Nathan Merrill

@MartinBüttner on your Birthday problem challenge, you post that 99 => 1.0 Is that because of rounding?

Martin Büttner

yes

Nathan Merrill

I thought so, making sure I wasn't missing anything

Martin Büttner

14:15

@NathanMerrill clarified that in the post

PhiNotPi

Rules updates for Evolution of OEIS (EOOEIS) idea: meta.codegolf.stackexchange.com/a/4921/2867

I think I would want 2 stack snippets in the question (is that possible?). One will be a scoreboard, and one will show the tree.

Martin Büttner

yes, that is possible

"at the highest level possible." seems ambiguous (depending on how you picture the tree). do you mean the deepest level?

PhiNotPi

Deepest

Nathan Merrill

greatest

Martin Büttner

wtf, how is Telescopic Parentheses still on the HNQ

Nathan Merrill

14:28

I didn't even find it that interesting

Martin Büttner

@NathanMerrill I didn't expect you to :P

Nathan Merrill

not sure if that was an insult or not :P

PhiNotPi

It's also a total ripoff of Explanation Formatter. (It's actually completely different, I just don't like being the "inspiration for a more popular question")

Martin Büttner

@NathanMerrill it wasn't. I just don't remember you being particularly interested in golfing.

Nathan Merrill

well, some golfing problems are interesting

I just didn't think that one was

randomra

14:34

@PhiNotPi if you want to sum the scores for a submitter's multiple submits you should use the reciprocal so higher score will be better and addable

Martin Büttner

@NathanMerrill "not sure if that was an insult or not :P"

Nathan Merrill

?

I understood you were replying that statement

Martin Büttner

yeah, no I'm saying it back at you :D

Nathan Merrill

oh lol

I didn't even realize you wrote it

Martin Büttner

no problem ;)

how do I search OEIS for sequences starting with a given subsequence?

PhiNotPi

14:38

^ I couldn't figure that out either. :(

Martin Büttner

@Peter do you know if that's possible? ^

PhiNotPi

It should be a really simple thing to do.

Is there some obscure language where an empty program always outputs 0?

Martin Büttner

there's probably some esolang which automatically prints the value of some register or stack at the end of the program

randomra

@MartinBüttner I spent a lot of time trying to find it out but couldn't. :(

Martin Büttner

I don't know one off the top of my head though

Zgarb

14:47

@MartinBüttner Partial solution: seq:1,2,3,6,11,23 -seq:_,1,2,3,6,11,23 finds those sequences where 1 2 3 6 11 23 occurs in the beginning and nowhere else.

randomra

@PhiNotPi or outputs the input number

PhiNotPi

The sequence 1 2 3.... could show up as deep as level 3. (Preceded by 1,1,1, and 1,2,4,8,)

randomra

@Zgarb Thanks, great! (given the possibilities)

@PhiNotPi it could show up at almost any level

just like 0 0 0 0

Martin Büttner

@PhiNotPi actually, I can probably make a 0-byte retina solution

the default operation mode is counting matches. so this will give no. of decimal digits + 1

randomra

lol at probably :D

Martin Büttner

14:52

well it depends if that's an OEIS sequence

PhiNotPi

It really can show up at any level as long as there's a sequence that matches the first however many terms. There's probably a lot of sequences that start with 1,2,3,4

0 0 0 is a sequence. I checked.

randomra

It does sound funny. " I can probably make a 0-byte solution if I write it well enough."

Do you think deeper level scores could compete with 1-2 char solutions at starting levels?

Martin Büttner

hm yeah, the zero sequence is definitely possible with a single character in many languages.

(and possibly with zero characters)

or the natural numbers

randomra

I would do a scoring like level/(length+10) (I know I already said it before)

Martin Büttner

I think an empty fractran program would output the input

PhiNotPi

14:57

Maybe change the requirement to "print the first N terms"?

But that might exclude some stuff.

Martin Büttner

I should quickly add decimal to unary conversion to Retina ;)

randomra

going to bed, bye all!

Peter Taylor

@MartinBüttner Download the database. It's a text file, a bit under 50MB, which contains just the names of the sequences and the first few terms.

Martin Büttner

Oh, neat. Thanks :)

@PhiNotPi You might want to add that as a suggestion to the post.

it's not entirely obvious where to find it. it appears to be the stripped.gz link on this page

PhiNotPi

15:17

Here's an idea as to how to score stuff:

Each user will have a score created by combining the scores of their answers.

Each answer's score will be calculated with something like (length/depth + 1).

And their combined score is like resisters in parallel: inverse is sum of inverses.

I can probably simplify this.

Answer Score = depth / (length + depth)

User Score is sum of answer scores.

Geobits

15:35

This guy is really getting on my nerves lately.

Optimizer

ugh, CJam hate

Geobits

That's not the first time you've said that. Is there any evidence that it's CJam hate and not just a normal downvote? I've had answers downvoted, despite not using CJam.

Optimizer

Well, I don't see a reason for a down vote considering it a normal answer

and I can point to several questions where someone mass downvotes just golfing language based submissions

Geobits

Well the question itself has 6 DVs. I'm pretty sure I've seen people say they DV answers to "bad" questions, too. It could be any number of things.

Optimizer

since this question has no other answers, yeah there is a doubt that this is not cjam hate..

Geobits

15:46

Either way, I'd be happy with +31/-1 :P

Optimizer

+32/0 is still better :P

Martin Büttner

@AlexA. @randomra meta post for the leaderboard snippet is up.

New Meta Posts

0

Q: Leaderboard Snippet

I've been using a stack snippet for a while to generate leaderboards for my simpler or more popular code golf challenges. I want to share the code for this snippet here so others can use it more easily as well. Feel free to put feature requests and bug reports in answers, or let me know in chat....

discussion stack-snippets scoring

ProgramFOX

var answer = 574b6d73-42db-4091-b2de-8e05fd1d2eaf(answer)

@MartinBüttner ^ What does that line mean?

Martin Büttner

ugh...

I forgot that meta still has mathjax activated

ProgramFOX

15:55

ah

orlp

s/\$/jQuery/

Martin Büttner

yeah

Optimizer

@MartinBüttner so the adjusted_for_leap_year probability when N = 23 is 1 - 366!/(366^23 * 343!) right ?

Martin Büttner

fixed

@Optimizer no, that gives 0.506323

(instead of 0.506876)

Optimizer

yeah, that is what i was wondering ..

so do we have to calculate the formula ourselves ?

Martin Büttner

16:01

well yeah, it's not quite as simple as the problem without leap years :P

Optimizer

and any year range ?

Martin Büttner

yes, just assume it's equally distributed over the 400 year cycle

Optimizer

ok

orlp

16:16

There's 97 leap years every 400 years, right?

Optimizer

so its just a challenge of finding out the formula first :P

Martin Büttner

@orlp yes

@Optimizer yes, that's part of the challenge, and there might be multiple ways to calculate it.

orlp

@MartinBüttner might?

this is math we're talking about

Martin Büttner

well yeah of course there is an infinite number of ways, but I don't know if there are multiple substantially different approaches which are feasible to golf and still meet the time limit.

everyone might end up using the same approach.

TheNumberOne

@orlp Does the golf-cpu flush after every output?

orlp

16:24

@TheNumberOne open the source code :)

but yes

Optimizer

I've got the formula, trying to golf it computationally

hmm, i was pretty sure my formula was correct, still I get 0.507061151502729 for 23

orlp

@MartinBüttner may you use a builtin for the gamma function?

Martin Büttner

@orlp sure

Optimizer

@MartinBüttner so simply replacing the probability to have birthday on a day (1/365) to the actual value (over 400 years) is not the answer ?

because its not giving the right values

Martin Büttner

16:40

@Optimizer no that doesn't work, because you get different probabilities depending on whether someone actually has their birthday on 29 Feb or not.

Geobits

This challenge isn't pedantic enough to be called pedantic. The fact that birthdays are far from uniformly distributed surely matters more ;)

Optimizer

I've got a very simple formula which gives the first 5 decimal correct for all inputs and the sixth one correct for 40 numbers :D

Martin Büttner

@Geobits Feel free to come up with a better title ;)

@Optimizer could that be due to different rounding, or is that sixth one way off for some of them?

Geobits

(Somewhat) Pedantic Birthday Paradox

Optimizer

@MartinBüttner off by 1

Martin Büttner

16:50

how do you round then?

Optimizer

oh, I haven't rounded at all

Martin Büttner

just truncated?

Optimizer

CJam gives me 10 decimals

yeah, truncated

let me round

orlp

aww

gamma not enough range :(

Martin Büttner

@Geobits I actually went with that.

Geobits

16:55

:D

I just now noticed Peter ninja'd my chat message in the comments an hour ago :(

Martin Büttner

yep

Transcript for