The Nineteenth Byte

Riker

01:00

@aspaghetto what inspired this revolutionary shift in ideals, from fencing to feeding?

New Sandboxed Posts

02:03

0

A: Sandbox for Proposed Challenges

🎲🎲Upgrade Your Dice (KotH, WIP)🎲🎲 You have recently taken a job at Lucky & Co, as a professional dice roller, and need to make as much money as you can! (of course). You will be paid exactly what you roll, $1 for a 1, $2 for a 2 etc. Where's the fun in that? Well, these aren't ordinary dice:...

Adám

02:15

@LeakyNun YEN-sₔn as in the Japanese currency and chosen

MilkyWay90

@Adám Yeah I print(int(input(),16))ed 05AB1E and got the same thing

Newly Featured Questions

02:32

25

Q: Is this a Smith number?

Challenge description A Smith number is a composite number whose sum of digits is equal to the sum of sums of digits of its prime factors. Given an integer N, determine if it's a Smith number or not. The first few Smith numbers are 4, 22, 27, 58, 85, 94, 121, 166, 202, 265, 274, 319, 346, 355, ...

MilkyWay90

print("".join(chr(int(x.replace("'","0").replace('"',"1"), 2))for x in['\'"\'\'"\'\'"', '\'\'"\'\'\'\'\'', '\'"""\'"""', '\'""\'"\'\'"', '\'""\'""\'\'', '\'""\'""\'\'', '\'\'"\'\'\'\'\'', '\'""\'""""', '\'""\'"""\'', '\'""\'""\'\'', '\'""""\'\'"', '\'\'"\'\'\'\'\'', '\'"""\'"\'\'', '\'""\'\'\'\'"', '\'""\'""\'\'', '\'""\'"\'""', '\'\'"\'\'\'\'\'', '\'""\'"\'\'"', '\'""\'"""\'', '\'\'"\'\'\'\'\'', '\'"\'"\'\'\'\'', '\'""""\'\'"', '\'"""\'"\'\'', '\'""\'"\'\'\'', '\'""\'""""', '\'""\'"""\'', '\'\'"\'\'\'\'"']))

New Sandboxed Posts

05:21

0

A: Sandbox for Proposed Challenges

Output the date in the Mel calendar The Mel calendar is used in the fictional world of Kaldia. Your goal is to convert dates into the Mel calendar. This calendar has 13 months of 28 days each, plus 1 or 2 extra days. A year that is divisible by 4 but not by 100, or divisible by 400 has 366 days...

Adám

@DJMcMayhem Can you give chat.stackexchange.com/users/406444/user517906 explicit write access to chat.stackexchange.com/rooms/52405/the-apl-orchard?_=228938491?

DJMcMayhem

05:47

@Adám Done

Adám

@DJMcMayhem Thanks!

Quintec

12:54

@EriktheOutgolfer yeah, I know... :p but we have at least 6-8 more weeks!

Erik the Outgolfer

not so sure, Catija did say "a week or two"

Anush

14:09

hi all

Adám

14:22

@Anush Hello Anush.

Anush

I am still wondering about my algo puzzle... :)

if anyone has any ideas it would be great to hear them

Anush

14:35

in my puzzle, you are given an array of numbers (can be positive or negative) and you have to output the maximum subarray sum divided by the sqrt of the length of that subarray

the question is, can you do any better than naively looking at every subarry?

Adám

@Anush Do better performance-wise, you mean, right?

@Anush Does the subarray have to be square? If not, what does length of that subarray mean?

Anush

@Adám yes!

Adám

@Anush Why is it divided by the sqrt of the length of that subarray, rather than the square of the length of that subarray (which would then be the subarray with highest average).

Anush

@Adám say the array is (3,-2,5,-1,2) then the subarray (-2,5,-1) has length 3

@Adám divided by the length of the subarray would be the average. Where does the square come from?

Adám

@Anush Oh, so the array is just a list?

Anush

14:41

yes exactly

a list with constant time access :)

Adám

@Anush You wrote divided by the sqrt of the length!

Anush

@Adám yes.. that turns out to be interesting for ML people apparently

but really divided by any function of the length is interesting

we can start with divided by the length, I don't mind

@Adám if you don't divide by anything there is a very simple linear time algorithm

Adám

@Anush Are you sure?

Anush

yes :)

I can explain it

let's maintain the max subarray sum for a subarray that finishes at index i

now look at index i+1

the subarray with max subarray sum that finishes at i+1 is either the subarray with max subarray sum that finishes at i plus the element at i+1 or it's the element i+1 on its own

that's the whole algorithm

afshinm.name/2018/06/24/why-kadane-algorithm-works

is that clear?

Adám

@Anush Not at all, but surely just due to me being dumb.

Anush

14:51

@Adám does the link help?

or en.wikipedia.org/wiki/Maximum_subarray_problem ?

Adám

@Anush I read through it, but I don't understand what would happen with [2,3,-1,3]. Once we reach -1 we conclude that that isn't helping, so we stop there and start over, but if we had continued, we'd see the 3 next so the max is 7.

Anush

@Adám ok so let's take that example

let's index from 1

so at index 2 the max is 5

Adám

ok

Anush

we then read in -1

the max that terminates at index 3 is either 5-1 or -1

so it is 4

we are computing for every index the max that ends at that index

the max overall will be the max of all those values

does that make sense?

Adám

So what about [2,3,-1,-1]?

Anush

14:58

ok let's do it

for index 1 it is 2

for index 2 it is max(2+3, 3) = 5

Adám

ok

Anush

for index 3 is max(5-1, -1) = 4

for index 4 it is max(4-1,-1) = 3

Adám

ah, I think I get it now.

Anush

it's super elegant

the problem is that if we divide the subarray by its length, it all seems more difficult

I can't see how to do anything non-naive at all

Adám

@Anush And you're only interested in theoretical complexity, not actual performance, right?

Anush

15:02

@Adám well.. I am interested in how the performance scales

dzaima

@Anush I'd guess there isn't a general algorithm for any function, but for specific functions it's probably possible

Anush

@dzaima let's take two function. One where we divide by the length of the subarray and one where we divide by sqrt(length subarray)

can we do anything for either?

oh.. dividing by the length might not make sense :)

dzaima

@Adám if one finds a theoretical algorithm, it can probably be adapted somewhat efficiently. O(n^2) is almost always gonna be slower than O(n) for a 1000000000 item array

Anush

isn't that just the largest element?

dzaima

@Anush divide by length = average, so yes

Anush

15:04

@dzaima yes.. it's only the other version that makes sense. dividing by the sqrt of the length of the subarray

serves me right for trying to simplify a problem :)

that's the version the ML people told me in any case

Adám

@Anush Some measure of brute force may be able to use the processor's vector instructions or even parallelise the computations while the O(n) approach needs a loop that the branch predictor will have little chance to deal with.

Anush

@Adám true... but I think if n = 100000, an O(n^2) algorithm is always going to lose

dzaima

@Adám again, a billion items and O(n) is probably better than O(n^2). O(nlogn) would be debatable though

Anush

@dzaima I think even with 100,000 items, unless the constant is crazy in your linear time algorithm

dzaima

well

Adám

15:09

Right, I'm just saying, and we never stated the order of magnitude of the list's length.

Anush

but we don't have any non-naive algorithm at all currently!

@Adám Let's assume it's around 1,000,000 items long if we don't want to talk big Oh

@dzaima yes that has silly constants :)

Adám

@Anush Another fun one would be to find the largest subarray sum in N dimensions.

Anush

@Adám yes but those problems seem to be known

whereas I can't find anything on my version

Adám

CMC: given an N-dimensional array, find the largest subarray sum when divided by the product of the subarray's side lengths.

Anush

isn't that just the largest element again?

Anush

15:40

@dzaima do you think there is a subquadratic time solution to my problem?

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

I'm trying out a personal leaderboard widget. This is my test to see how it looks embedded. <iframe src="https://ppcg-leaderboard-test--xmikee.repl.co/?id=183544" style="width: 100%;">Oops, your browser is too old to view this content! Please upgrade to a newer version of your browser that ...

dzaima

@Anush no idea. it probably can be optimized a lot for specific datasets (straight up random numbers often end up resulting in the whole array), but otherwise i don't see much pattern in the outputs

actually a smarter observation would be that for a list of positive numbers the best subset isn't guaranteed to be the whole list

Anush

@dzaima you mean it might even be quadratric time for positive only arrays?

@dzaima imagine the numbers of random N(0,1), it's not clear what length the subarrays would be to me

dzaima

@Anush it'd probably be near the whole array is what I'm saying, and maybe there's some way to quickly check that

Anush

@dzaima interesting

dzaima

15:55

haven't put much thought in how to do that though

Anush

@dzaima the key question is how to find the max subarray that includes some index i

then you could you divide and conquer

but it's not obvious how to do that to me

Erik the Outgolfer

17:21

@Zylviij looks like you requested access to JHT :-)

wanna practice Jelly?

Zylviij

18:01

@EriktheOutgolfer I'm very new to Jelly, but I'm trying to figure out the chain/link system by doing some older challenges.

Currently I'm looking at codegolf.stackexchange.com/questions/62314/…

Erik the Outgolfer

you're interested, you're in :P

bb94

Is anyone else unable to access the Perl 6 docs?

Zylviij

@bb94 Just got the ERR_CONNECTION_TIMED_OUT on docs.perl6.org

bb94

Been going on for a while

MilkyWay90

22:59

Okay, who chatted "gode colf" and "ppcg" as the user "dddd" on my website, randomstuffonline.com/chat.html?

Can a mod give meta.stackexchange.com/users/468751/dysfunctional write access to chat.stackexchange.com/rooms/88563/cicada?

New Main Posts

23:48

0

Q: Generate a Pronounceable Nonsense Word \$n\$ syllables long

Your task is to generate a nonsense word that is reasonably pronounceable with the specified number of 'syllables'. Each time the program is run possibly results in a different nonsense word. Pronounceability A pronounceable word is made up of syllables, which are in turn made up of a vowel gro...

code-golf string random

Transcript for