The Nineteenth Byte - 2019-04-22

« first day (3005 days earlier) ← previous day next day → last day (1837 days later) »

1:00 AM

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

1 hour later…

New Sandboxed Posts

2:03 AM

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:...

2:15 AM

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

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

Newly Featured Questions

2:32 AM

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, ...

code-golf math number-theory decision-problem

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

3 hours later…

New Sandboxed Posts

5:21 AM

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...

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

5:47 AM

@Adám Done

@DJMcMayhem Thanks!

7 hours later…

12:54 PM

@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"

1 hour later…

2:09 PM

hi all

2:22 PM

@Anush Hello Anush.

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

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

2:35 PM

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?

@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?

@Adám yes!

@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).

@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?

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

2:41 PM

yes exactly

a list with constant time access :)

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

@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

@Anush Are you sure?

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?

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

2:51 PM

@Adám does the link help?

or en.wikipedia.org/wiki/Maximum_subarray_problem ?

@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.

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

let's index from 1

so at index 2 the max is 5

ok

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?

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

2:58 PM

ok let's do it

for index 1 it is 2

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

ok

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

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

ah, I think I get it now.

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

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

3:02 PM

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

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

@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 :)

@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

isn't that just the largest element?

@Anush divide by length = average, so yes

3:04 PM

@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

@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.

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

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

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

well

3:09 PM

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

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 :)

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

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

whereas I can't find anything on my version

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

isn't that just the largest element again?

3:40 PM

@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 ...

@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

@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

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

@dzaima interesting

3:55 PM

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

@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

1 hour later…

Erik the Outgolfer

5:21 PM

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

wanna practice Jelly?

6:01 PM

@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

Is anyone else unable to access the Perl 6 docs?

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

Been going on for a while

5 hours later…

10:59 PM

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?

11:48 PM

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

« first day (3005 days earlier) ← previous day next day → last day (1837 days later) »

Transcript for

Apr '1922

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