The Nineteenth Byte

Jo King

00:47

@Rick Probably into 32 bits

Rick

01:01

@JoKing compress this => EBJ71A

compress it so I can sort it quickly

imagine millions more just like this

Jo King

I don't really have any context from which to start "compressing" that. I assume interpret as a base 36 number?

And what does compressing have to do with sorting?

Rick

makes the numbers smaller

so I can pipe it through my Radix

interpret it however you want

I've already solved this, but maybe there is something I missed

Jo King

Well, EBJ71A isn't a number, so you have to interpret it somehow.

Rick

it's a string but you can turn it into a number

you want me to tell you how?

Jo King

Base 36? Without knowing the context of the string, I'm not able to turn it into a number

It looks like it's just composed of numbers and letters, but maybe it's could be base64 encoded string, or can contain any byte etc.

Rick

01:16

I was not given a context just a million other strings just like it. I had to deduce it

Jo King

Yes, a million other strings is context

Rick

I said a million earlier

Also they are all the same length

if that helps

and they follow the same format

LLLNNL (L:letter,N:number)

All letters are uppercase

I said there is 1 million but there are 2 million to be exact (but I don't think that's going to help)

@JoKing if it's too difficult let me know and I will just tell you

Jo King

Well, you can interpret as a 26*26*26*10*10*26 size number

Which is only 26 bits

Rick

yep you got it

@JoKing can you do better and if not why?

Jo King

01:32

I mean no? Not unless there's some other formatting restriction that you aren't telling me about

Rick

There are no other restrictions

Jo King

Then you can't compress it further without being lossy or inspecting the actual data

Rick

you are more or less correct. but even if you inspected it wouldn't help given the other restrictions i mentioned

what sorting algorithm is best for sorting 2 million of these ints? and why?

and is there a class of sorting algorithms that best fit this use case ?

Jo King

idk, merge sort?

Rick

cough cough... umm no!

Jo King

01:45

quick sort? If you're just sorting numbers, I can't really think of a certain sort that would be better

lirtosiast

this discussion doesn't make sense

Jo King

if you're still in that format though, radix sort would be better right?

@lirtosiast correct

lirtosiast

The fact that the numbers are being converted from the form AAA00A has no bearing whatsoever on their distribution

Other than that they're less than 26^4*100

Rick

@lirtosiast you don't know their distribution

if you did you wouldn't need to sort

lirtosiast

Even if they did have a special distribution 2 million integers can be sorted in minutes using quicksort, radix sort, or whatever algorithm

Rick

01:49

this is not a flame war. The whole point of this is about optimization. Sorting gives us insights into how to solve much harder problems

Jo King

Radix would be O(6n)?

Rick

if I just wanted to sort something anyone can brute force it

@JoKing how many passes would merge sort make on a data set this large?

Jo King

log2 right?

Rick

can you give me an exact number

Jo King

2e6.log(2) ~=~ 21

New Main Posts

03:17

0

Q: Implement Division with Error-Detection

Implement division. Input 2 numbers: a and b. Output the result of a divided by b. Note that 0-division returns 0. (A simple error-detection) This program should support division with big integers (i.e. supports more digits that the built-in long long type in C) Support for negative numbers is ...

code-golf

New Main Posts

04:21

0

Q: Implement the EnScript CHS command

JonoCode9374 had almost completely implemented my language EnScript except for the CHS command. I was impatient of waiting them to implement this command, so I chose to put this question here. This is the CHS instruction reference copied from the website: CHS means to chase all of the numbers in...

code-golf

New Main Posts

05:01

-2

Q: Tips for golfing in Keg

Keg is a minimalistic golfing language created by JonoCode9374. Post tips that specifically apply to Keg.

tips

New Main Posts

05:21

0

Q: Proving that a Russian cryptographic standard is too structured

The aim of this challenge is to find an impossibly short implementation of the following function p, in the langage of your choosing. Here is C code implementing it (see this TIO link that also prints its outputs) and a wikipedia page containing it. unsigned char pi[] = { 252,238,221,17,207...

code-golf math kolmogorov-complexity cryptography

0

Q: Finding Maximum of minimum from K segments in an array

I am working on a programming problem , but I am not able to prove one of the case from the solution mathematically. The problem statement is- Given an array of n integers, divide it into k segments and find the maximum of the minimums of k segments. Output the maximum integer that can be obtaine...

math array

Adám

@Catija @Mego Why is Cast your vote for “Best of PPCG 2018”! featured?

New Sandboxed Posts

07:23

0

A: Sandbox for Proposed Challenges

Who can escape the Nonary Game? Rules of the game There are 9 participants, numbered 1 to 9. There are any number of doors, each one with a 1 to 9 number. There may be duplicate or missing door numbers. Only groups of 3 to 5 persons can go through a door. A group can only go through a door if ...

New Sandboxed Posts

12:02

0

A: Sandbox for Proposed Challenges

Make Gimbap cutter Gimbap(김밥) is Korean food, somewhat looks like sushi roll. Here is Korean emoticon represent Gimbap : @)))))))))) Your quest is make ASCII Gimbap cutter. Rule Input is string made with @ and ). Output cuts input string with ), and then add (space)@ between them. If there...

Veskah

12:57

This OneNote we're using for a project has a typo in the name. It bugs the hell out of me but there's probably enough links that changing it will break things

AdmBorkBork

13:15

@someone Now that you've posted your Graeco-Latin square challenge, make sure to delete the post in the Sandbox to help save space and keep the Sandbox tidy. Thanks!

Adám

13:30

@Mego @Dennis Can you make chat.stackexchange.com/users/382943/richard-park a room owner of chat.stackexchange.com/rooms/52405/the-apl-orchard?

@Catija ^ not to ignore you — I just don't know if it is appropriate to ask such of CM.

dzaima

@Adám i'd expect that to be a thing you could do

Dennis

in The APL Orchard, 21 secs ago, by Feeds

Dennis has added Richard Park to the list of this room's owners.

Catija

13:43

@Adám no worries... but I think you could have done it without even a mod. ;)

someone

Deleted. I think a mod has done this to a posted proposal of mine in the past. My original plan was to delete it after a certain duration after the question is posted, so that people without the reputation to see deleted answers could see the proposal after following the sandbox link in the comments, but I ended up forgetting.

Adám

14:16

@Catija @dzaima Target has rep=1

Catija

Why is a one-rep user being given access to that room?

@Adám I mean, access is less of a thing but made a RO is confusing to me.

dzaima

@Catija Adám's giving RO to a coworker from his workplace who doesn't use SE

Poke

he has a duck collection

seems okay in my book

Catija

14:39

Well, clearly y'all know what's what. ;)

Oh, and don't worry about not pinging me about stuff... I have a lot of tabs open and I forget to close them. :/ So it looks like I'm around more than I am. Mostly I'm here so that if y'all have questions about the design, I'm pingable.

Anonymous

@Adám Because the featured list is weird and likes to not update, even when stuff hasn't been featured for weeks.

Anonymous

It's a known issue for all of SE

Catija

15:25

@Mego ... It's because it was locked before it was unfeatured.

Anonymous

That's a thing?

Catija

Yes.

9

Q: Old featured meta question intermittently appearing in "Featured on Meta" box

For some reason, a Meta question on IPS has recently erroneously appeared in the sidebar "Featured on Meta" box. Not only is this question not currently featured, it's locked. The featured tag was removed February 2nd, and this is not a caching issue because it was not in the box earlier this eve...

bug sidebar featured-question

Anonymous

That's some whacky behavior

AdmBorkBork

At least it's intermittent, so that's good for troubleshooting.

2

Veskah

16:16

Hmm, it'd be neat to see what challenge had the most bytes golfed off.

DJMcMayhem

@Veskah e576 bytes golfed off

Veskah

@DJMcMayhem Well alright then

DJMcMayhem

17:14

@Veskah I take it back:

Removed 39 × 2^(18 × 97!) ≈ 10^(5.2 × 10^152) characters (from 10^(5.2 × 10^152) to 2.8 × 10^101) — jimmy23013 Sep 14 '14 at 21:59

Neil

Someone helped my golf down one of my Lenguage answers quite a bit

AdmBorkBork

(With help) I've golfed 167 bytes off of a PowerShell answer. Does that count? Mathematically, they're practically indistinguishable.

167 and 10^(5.2 * 10^152), that is.

DJMcMayhem

Not to brag or anything, but one time Dennis commented on one of my Jelly answers and golfed 2-3 bytes off.

AdmBorkBork

So, it went from 100 to 98? :p

DJMcMayhem

Oh snap

Anonymous

17:28

@AdmBorkBork I'd get bored before I managed to count to either, so yeah they're the same number

AdmBorkBork

Perfect.

Rick

19:39

Given an array of 2N integers (-10^9 < X < 10^9), you can take any subarray of size N and multiply each element by (-1), what's the maximum array sum you can get doing this operation as many times as you want. (0 < N < 10^5)

Transcript for