The Nineteenth Byte

user

00:00

There'll be some overhead even though you're doing it in parallel

@rak1507 If you say so. All I know about O notation is that my programs sometimes are expressible in it and it tells me that they're inefficient

3

rak1507

loool

caird coinheringaahing

@RedwolfPrograms Surely everything can be O(1) with enough cores?

Redwolf Programs

No, not really

caird coinheringaahing

Booooo :P

Redwolf Programs

00:01

I'd imagine a lot of crypto stuff is specifically designed to be hard to parallelize

Unrelated String

everything can be constant time if you place bounds on the size of the input

Redwolf Programs

Well...technically yeah :p

user

Is it really constant, though?

@UnrelatedString Oh wait, you mean the input can only be one specific number?

ngn

@RedwolfPrograms KDFs (key derivation functions) are like that

rak1507

schneierfacts.com/facts/98

caird coinheringaahing

00:02

"Calculate the number of permutations of a list with 9 elements in it, in O(1) time"

Unrelated String

@user no, as in the notion of asymptotic complexity doesn't even exist if you have bounds on the size of the input

but yeah the case where an algorithm can be replaced with a lookup table is also there

Redwolf Programs

Then memory/storage complexity would become more important

Which bogosort needs none of

user

@rak1507 Oh yeah? Well, Chuck Norris can do it in O(0). He knows the factors before you give him the integer.

rak1507

lol

user

@RedwolfPrograms Doesn't it have space complexity n?

At least?

Redwolf Programs

00:04

It does?

rak1507

the most time efficient way of storing an algorithm is in a table, but the most memory efficient is storing the code

Unrelated String

oh yeah aren't there also some crypto things which are designed to take strictly constant time to counter side channel attacks

rak1507

yes

user

@RedwolfPrograms It has to hold the new randomly generated array in memory, right?

Redwolf Programs

@UnrelatedString But you can't do that for things that can have an arbitrary number of blocks

user

00:05

Unless you just shuffle the original array, I guess

caird coinheringaahing

Man, it's too easy to get CS nerds to discuss something :P

2

Redwolf Programs

Yeah, I guess O(n) in worst, just since it has to store at least some of the list

Unrelated String

@RedwolfPrograms yeah, it's meant to be constant with respect to single inputs of some sort

ngn

@cairdcoinheringaahing now try to make them do something..

Unrelated String

cannot be done

period

Redwolf Programs

00:07

But you could implement shuffling randomly in a way, if it knew the length beforehand, where the average memory compexity would be closer to O(n/2) I think

caird coinheringaahing

@ngn I'm not that persuasive :P

user

@cairdcoinheringaahing This one probably. All the methods are pretty poorly implemented. However, it's also tied for "fastest answer I've ever written."

Unrelated String

@RedwolfPrograms that's just O(n)

rak1507

@ngn what do you mean, spending large amounts of time in internet chatrooms is definitely a productive use of time

caird coinheringaahing

@ngn The closest I've got is by saying "This is code-golf, so the shortest code in bytes wins"

3

Redwolf Programs

00:08

Actually now I'm wondering, what's the lowest memory complexity to shuffle an array?

If you can recieve the elements one at a time and know the length already

user

@RedwolfPrograms Gotta agree with Unrelated String. Although actually it could be O(1)

@RedwolfPrograms All you need is a temp variable, an index, and the length, I think

Redwolf Programs

But if you store the whole list, it's at least O(n)

Unrelated String

if we're talking memory complexity wouldn't storing the index require logarithmic space

caird coinheringaahing

@Lyxal Would you mind awarding this bounty so that I can start WW's bounty?

user

@RedwolfPrograms I was only counting extra memory aside the pointer to the array, but then yeah, I guess O(n) is the best you can do:(

Redwolf Programs

00:10

Not necessarily, if you can receive the elements one by one

caird coinheringaahing

Bruh, just only accept single element lists. O(1) guaranteed

user

@RedwolfPrograms If you receive the elements one by one, how do you shuffle them?

@cairdcoinheringaahing This is genius!

Unrelated String

if you have to store a list of length n then wouldn't that alone take space proportional to n

Redwolf Programs

Pick a random index, then either wait until you get that item, or if you already have it discard it and output it

Unrelated String

oh so it's like

streams

Redwolf Programs

00:11

That at least lowers the constant

Maybe makes it slightly less than linear

Not sure

caird coinheringaahing

@user People have claimed so, but I'm too humble to let people other than me say I'm a genius :P

user

@cairdcoinheringaahing Done (Lyxal won the bounty on the robbers thread)

> people other than me

caird coinheringaahing

@user ...I read the wrong username :/

user

So you yourself say you're a genius? Yup, that's totally humble :P

caird coinheringaahing

@user I stand by what I said :P

Unrelated String

00:12

quite

exceptionally so

caird coinheringaahing

indeededly

user

Sorry, then. You are the furthest thing from a genius, @cairdcoinheringaahing. There, is that better? :P

Redwolf Programs

I'll give a 50 rep bounty to anyone who can figure out the memory complexity of my method of shuffling an array :p

caird coinheringaahing

@user Perfect :P

user

@RedwolfPrograms Could you explain it a bit more? It's unlikely I'll get the bounty, but I'd still like to try to understand it

By the way, thanks, caird coinheringaahing

Redwolf Programs

00:14

So, you receive the elements like a stream, one at a time

Then, you pick a random index

caird coinheringaahing

2 days ago, by Lyxal

@LuisMendo no, thank you for the high quality answer that won you the award.

s/LuisMendo/user

Redwolf Programs

If you've already got that item in memory, output it

Otherwise, keep inputting into memory until you get that item, then output it

Wait, you'd need to keep track of the used indexes :(

user

@cairdcoinheringaahing Thank you (btw I'm not as humble as you, so feel free to call me a genius :P)

@RedwolfPrograms What happens if you lose a previous element?

Like if the index you get is 10 and you discard the first element. How do you get it back?

Redwolf Programs

It doesn't matter since I just realized my idea wouldn't work

user

Oh ok

How about 50 rep for everyone in this chat then? :P

Lyxal

00:18

@cairdcoinheringaahing I will in a bit

Actually I do it in a few hours

caird coinheringaahing

@Lyxal user beat you to it :P

Lyxal

Wait you did it?

Dang it

caird coinheringaahing

> The current winner is Dennis's Jelly answer at 3 bytes

How am I supposed to compete with that?

@Lyxal I got the usernames mixed up :/

user

Don't. (btw this was a response to "How am I supposed to compete with that?")

Unrelated String

@cairdcoinheringaahing I don't know, but I have a long history of Brachylog answers

caird coinheringaahing

00:20

@user There is a "reply" button :P

rak1507

@cairdcoinheringaahing wait until a new golflang makes it a builtin

caird coinheringaahing

@UnrelatedString I've always wondered about the efficiency of Brachylog answers

user

@cairdcoinheringaahing I didn't think about using it because your message was right above

caird coinheringaahing

Being declarative, they don't seem as though standard O notation would work

Redwolf Programs

Actually, I think I could make my algorithm work in less than O(n) memory complexity, it would just be very biased

Unrelated String

00:21

@cairdcoinheringaahing The evaluation strategy is still performed through classical computation'

user

[Golflang that was totally not created specifically for this], 0 byte
``
Yeah, an empty file just happens to solve this exact problem in my new golflang that I totally did not create just to beat Dennis here.

Explanation
```
Solve this question
```

rak1507

@cairdcoinheringaahing what question btw

Unrelated String

also the constraint propagation only goes so far so even when you're only working with single integers

caird coinheringaahing

@rak1507 The abundant numbers one

Unrelated String

ofc there's no notion of a constraint once you aren't doing math

rak1507

00:23

there's probably some language with a 1 byte divisor sum builtin

or an is abundant builtin

Unrelated String

anything with strings at all is some or another degree of pure brute force

caird coinheringaahing

Ugh, of course score:n means "posts with a score of n or more" in the SE search, rather than "posts with score of n"

Unrelated String

and choicepoints are tried in a deterministic order

Redwolf Programs

I think Ash can get three bytes in that challenge too

user

@cairdcoinheringaahing But you can just do score:n..n, right? Whereas score:n..infinity would be harder

caird coinheringaahing

00:25

score:n.. works for "greater than or equal to n"

user

Oh ok

caird coinheringaahing

Posts one vote away from a gold badge

Posts one vote away from a silver badge

Posts one vote away from a bronze badge

rak1507

time to downvote them all to be evil

5

caird coinheringaahing

Hey, I don't tell y'all what to do with posts, I just provide them :P

Lyxal

@cairdcoinheringaahing when none of those are mine 😢

@rak1507 good luck doing that in one day.

user

00:27

@Lyxal Time to write a bot

caird coinheringaahing

mod flags to ban

Redwolf Programs

That's probably the fastest I've seen a message get that many stars

2

~~not to brag but I was the first to star it~~

caird coinheringaahing

Nov 12 '15 at 22:26, by Doorknob

okay seriously stop abusing stars

2

Unrelated String

@Lyxal the last query should contain three of my highest upvoted answers

caird coinheringaahing

That hit ~50 within an hour

user

00:28

What did Doorknob expect?

The temptation is too much

caird coinheringaahing

@UnrelatedString Don't worry, only 2,733 posts to upvote :P

rak1507

people star messages a lot more in here than the apl orchard it seems

or other rooms

caird coinheringaahing

We have 28144 messages that have been starred

That's a lot

Unrelated String

general chat has no obligations to remain serious

3

user

I sense a pun in here relating to stars but I can't quite find it

Redwolf Programs

00:30

I'm starring to see why, they're all awful

rak1507

these stars are the only ones people here see because they never go outside

user

~~I'm getting starry eyed~~

Actually, scratch that, that's not really relevant here

caird coinheringaahing

Just from a quick search, we might actually have the most stars of any room

@user ---

Unrelated String

@cairdcoinheringaahing honestly makes sense

user

@cairdcoinheringaahing Third time's the charm

rak1507

00:32

this must be one of the most if not the most active room right?

user

I'm star-ting to think it is

Redwolf Programs

I'm sure the SO ones are more active

Unrelated String

considering the other sites on the network are actual q&a affairs

Redwolf Programs

@user I already did a star pun with the word start!

user

Well, I guess SO is the brightest star, if Stack Exchange sites were stars

No wait, that's an analogy

caird coinheringaahing

00:33

It was the most active by far before the Monica incident

Redwolf Programs

What determines the starboard's order?

user

@RedwolfPrograms I'm just not creative.

caird coinheringaahing

Previously, I've seen 30+ users in this room. 14 (rn) isn't a lot

@cairdcoinheringaahing Fun fact:

10

Q: Which post on SE chat has the most stars?

Is there any way to find out which chat post across the entire chat.SE network (all rooms, all users) has the most stars? I solemnly swear that the intention of this question is not so that I can find it and clear the stars on it.

rak1507

It's such a shame I discovered cgcc so late, I was definitely interested in code golf 3 years ago or so but just never came across it somehow

Redwolf Programs

I wish I'd been more active when I first joined

caird coinheringaahing

00:36

@rak1507 Man, I've said the same thing so many times. 2014-2016 looked like the height of this site

Guess we'll have to strive to change that :D

rak1507

yeah

caird coinheringaahing

I tried writing an answer, but couldn't think of the best thing to say, but I do have this: I joined after you 'went dark' and so never really knew you as a mod. However as I read about the history of PPCG more and more (I cannot tell you how many forgotten chat transcripts I've read), I came to realise just how active you were, and I think that you stepping down as a mod is a great shame. I really hope you keep golfing and stay active here (come join us back in TNB when you can!) — caird coinheringaahing Feb 21 '18 at 23:02

rak1507

I think I discovered the tips pages because I'd use them, but I don't know why on earth I didn't look at the main challenges

user

Guess CGCC will have its ups and downs

caird coinheringaahing

I wasn't joking back then. I;ve read basically the entire chat log

rak1507

00:38

I've read a lot of the APL one and some of here

caird coinheringaahing

Oh man, I just realised I have more rep than Alex. That feels weird :/

user

CMQ: When did you join CGCC?

rak1507

The same is true to a lesser extent for the APL orchard, a few people who were active in the past aren't active any more and it's a shame

Redwolf Programs

I joined on my old account about three years ago I think

caird coinheringaahing

@user View your profile, hover your mouse over "Member for" and it'll tell you, to the millisecond, when you joined

rak1507

00:39

@user well my first answer was in September

caird coinheringaahing

@user This account? 12th of March 2017. So, 4 years ago, in 12 days time :P

Check out this. It gives you a full breakdown of your rep gains, day by day, along with rep totals for various intervals at the botton

rak1507

wow if I'm reading this right I visited every day in january

Redwolf Programs

I joined SE in September of 2016 with my old account, but just lurked on CGCC. I don't think I ever even made a CGCC account.

user

57191715: I joined about 8 months ago, and my first answer was sometime in July

caird coinheringaahing

@rak1507 May 14 2020 was the last day I didn't visit PPCG :P

rak1507

00:41

whoa

Redwolf Programs

I've got 198 consecutive days

caird coinheringaahing

Having the mobile app has some advantages :P

user

Looks like you could've gotten multiple Fanatic badges

caird coinheringaahing

> Visited 1171 days, 290 consecutive

rak1507

since september 1st I have 18 missed days

which is exactly 10%

Adám

00:43

@user 2015-08-26T01:59:37Z

user

I've got about 106 consecutive days, and it looks like I didn't come here November 14, 2020

Adám

@cairdcoinheringaahing How do you get milliseconds?

user

^

caird coinheringaahing

@Adám By misreading the timestamp

2

Adám

Cool. Will do.

rak1507

00:44

lol

Redwolf Programs

How many profile views do y'all have?

rak1507

83, you?

Adám

@RedwolfPrograms 7546

Redwolf Programs

4555

rak1507

:(

caird coinheringaahing

00:44

@rak1507 Since Jan 1st 2020, I have 14 missed days

@RedwolfPrograms 6713

rak1507

@cairdcoinheringaahing I think you need golfaholics anonymous

caird coinheringaahing

@rak1507 My record through 2019 was pretty bad

Redwolf Programs

I missed a ton in early 2020

caird coinheringaahing

Maybe 10 days per month

Does my dog look squashed to anyone else here?

Redwolf Programs

Yes

caird coinheringaahing

00:46

ಠ_ಠ

It's normal everywhere else

user

@RedwolfPrograms 992

Wezl

@user just a year ago, but I still have the audacity to use TNB like a mature person

Lyxal

@RedwolfPrograms pathetic

@user just almost 3 years ago

Unrelated String

@user first answer was on a different account but this account was created on feb 6 2019

Lyxal

As in next month my account will turn 3 years old

rak1507

00:50

sorry, I am being an idiot, anyone know why this doesn't work? staxlang.xyz/#c=%22%26F%25

Unrelated String

nice

rak1507

trying to simply get divisors

user

@Lyxal Happy cake day in advance?

Lyxal

@RedwolfPrograms 2403

user

CMC: How many people have you reached? (~)

Lyxal

00:51

@user 230k

Unrelated String

@rak1507 I think the quote is starting a string literal

rak1507

wow

@UnrelatedString quote?

Adám

@user ~1.5m

Unrelated String

@rak1507 i actually ran the code and the quote is definitely starting a string literal

user

I've only reached about ~83k :\

rak1507

00:51

oh, it linked wrong

the code is meant to be :d

Unrelated String

lol

Redwolf Programs

463k

Lyxal

I've seen every day of the last 1.5 years

Adám

I suppose they actually mean M and not m.

rak1507

staxlang.xyz/#c=%3Ad&i=220

Unrelated String

00:52

@user ~150k

user

Somehow I've reached more people on CGCC than on SO, even though I've been a member there longer

Lyxal

@user same.

Unrelated String

@rak1507 I think it's outputting the list of divisors as a string

rak1507

oh

alright

Adám

1 Mperson ("megaperson") = 1×10⁶ people and 1 mperson ("milliperson") = 1×10⁻³ people, I presume.

Unrelated String

00:53

forget how you get around that

Wezl

~~I've never seen a milliperson~~ I guess a milliperson would be too small...

3

user

@Adám I think you're forgetting the quantum is 1 person :P (unless I'm not using "quantum" correctly)

Adám

I'd like to know how they compute the "reached" numbers. They seem exaggerated to me.

user

@Adám I think your answer gets all the views of the question if its score is high enough

Unrelated String

that is a good question

caird coinheringaahing

00:55

@user 373k

Lyxal

@Adám Supposedly theyre underexaggerated

Unrelated String

ooh yeah that makes sense

Redwolf Programs

Who has a ratio of (product(code_points_in_username) - (profile_views * upvotes_cast * downvotes_cast)) / nth_prime(consecutive_days) closest to a square number? The difference for me is 168299831824500

caird coinheringaahing

@RedwolfPrograms Give calculator program psl

user

303

Q: We're working on a new stat to help convey the reach of your posts here

We've got a new statistic on the shiny new Profile Page Prototype. It's not perfect yet. And we did a pretty crap job of explaining what it's all about! Let's talk. What you do here isn't just about solving one person's problem. A while back, a user contacted us about his friend's account. His f...

discussion profile-page feedback people-reached

Lyxal

00:56

CMQ: how many github followers do you have

Adám

Supposedly, the population of Antarctica would be appropriate to measure in millipersons per square kilometre.

rak1507

@Lyxal 14

caird coinheringaahing

@Lyxal 13

Wezl

@Lyxal easy, 0, which is how it should be

Redwolf Programs

6 :(

user

00:56

@Lyxal 2, you and Wezl :(

Lyxal

Wow

Then how do I have 108?

user

Wait not Wezl

Adám

@Lyxal 32

user

Razetime

Wezl

@user yeah I don't follow people (usually)

caird coinheringaahing

00:57

> If anything, the reached indicator is probably more on the conservative side than anything. You can go through 5 or 6 results in the top 10 of searches in way under the amount of time that would actually register

user

What exactly does following someone on GitHub do?

caird coinheringaahing

From here

user

@Wezl Me neither

Unrelated String

@user shows you stuff they do and all that

Lyxal

@RedwolfPrograms imagine having less than 10

Made by 100+ gang

Unrelated String

00:58

followed a friend of mine and the home page shows me when he forks something

rak1507

CMQ: how many linkedin connections do you have

user

Oh ok

Redwolf Programs

Imagine having a job

6

Lyxal

@rak1507 I don't use LinkedIn, boomer

rak1507

don't need a job to have linkedin

caird coinheringaahing

00:59

@rak1507 What is this "linkedin" you speak of?

rak1507

@Lyxal I'm literally younger than you

user

It's useful if you have a job, though

Adám

@rak1507 93, but I intentionally avoid connecting to people I don't know IRL.

Lyxal

@RedwolfPrograms made by me and redwolf gang

user

@rak1507 A boomer in spirit, then.

3

rak1507

00:59

@user harsh!

caird coinheringaahing

@RedwolfPrograms *cries in Gen Z*

Transcript for