The Nineteenth Byte

New Main Posts

02:41

0

It turns out that my toaster is a tad broken. It lost WiFi (You know, it's one of those newfangled smart toasters), and its been going bonkers! Since it no longer works, I've been having to hack into my breakfast's source code and run Plate.bread.toastAs(3); every morning. Will you help? My toas...

Nathan Merrill

02:56

It's commonly known that sorting takes O(nlog(n)) comparisons

but what if N is super expensive, and you are allowed to cache all comparisons? Can you do better than O(nlog(n))?

Anonymous

@NathanMerrill It's impossible unless the transitive property applies to the comparison function. If so, then maybe, but I need to ponder more.

Nathan Merrill

actually, its guaranteed that no two elements are equal

The scenario I was thinking was this: Let's assume that we're organizing a tournament bracket (for football or whatever)

the actual games are super expensive: on the order of days

Anonymous

Distinctness is not enough. You need to have a comparison function that imposes a well-ordering on the elements

Nathan Merrill

but let's assume that if Team A beats Team B and Team B beats Team C then Team A would beat Team C

Eric Tressler

I think essentially you just want to be in a situation like sorting integers in [0,k] so you have bucket sort.

Nathan Merrill

03:02

@Mego if I understand well-ordered, I think that is true

it basically means I can rank all of them with no ties/loops/etc, right?

Eric Tressler

yes, but I think Mego meant a total ordering (which is weaker, but equivalent for finite sets)?

Anonymous

@EricTressler Yes, that one, thanks

Eric Tressler

but yes, that's what it means; every pair of elements is comparable

Comparison sort

A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator obey two of the properties of a total order: if a ≤ b and b ≤ c then a ≤ c (transitivity) for all a and b, either a ≤ b or b ≤ a (totalness or trichotomy).It is possible that both a ≤ b and b ≤ a; in this case either may come first in the sorted list. In a stable sort, the input...

I link that because it states "A comparison sort must have an average-case lower bound of Ω(n log n) comparison operations" and "Non-comparison sorts (such as the examples discussed below) can achieve O(n) performance by using operations other than comparisons"

with references and lots of details

Nathan Merrill

My question is if that is still the case if you allow caching of comparisons

Eric Tressler

Yes

and a skeletal proof is in the link; basically, there are n! different possible orderings, and you can reduce that number by a factor of 2 with each comparison

so to pin down the 1 ordering out of the n! potential ones, you need log_2(n!) comparisons, which is O(n log n)

Nathan Merrill

03:10

ah, that's a clever proof.

Eric Tressler

It's just a small step from the much more obvious proof that you need log n queries to search. Anyway, I'd totally forgotten that proof, so thank you for reminding me.

Nathan Merrill

Yeah I was thinking about the binary search method, but with that method, it feels less obvious to me that caching won't help

Anyways, so that means with 64 teams tournament, they would have to play 384 games, which is just a bit more than the 128 games they already are playing :P

Eric Tressler

After you let them know what their schedule is, some of them will drop out, and then you'll have a manageable number of games again. Problem solved.

Nathan Merrill

lol

it's not 384 games per team. It'll still average out to around 6 games per team

...actually. That's crazy interesting. The average team plays twice in a single-elimination tournament, no matter the size

I mean, the math works out, but I had never thought about that

Eric Tressler

I hope you used linearity of expectation and not something ugly to get that

Nathan Merrill

03:23

er...no. The number of games in a single elimination is N + n/2 + n/4 + ... which is equal to 2N. Since there are N teams, it means the average number of games is 2N/N

Eric Tressler

or, that you know exactly n-1 games are played if there are n teams, because after each game you lose 1 team, and you stop when there is 1

and each game gets counted twice, once for each team that plays

Nathan Merrill

each game counting twice actually evens out

because with N players, the first round has N/2 games

so, my terminology above is wrong, but the math is still correct

Eric Tressler

I think you need to account for the last term being missing

Nathan Merrill

true, it's 2N -1 games.

but that makes the math really messy and the average number of games a decimal number :)

so I ignore it :)

we can just assume there's a consolation game for 3rd place :)

actually, that makes it 2N+1 games

bah, that's lame

Eric Tressler

With n teams, there are n-1 games, or 2n-2 games if we count each side. So each team plays an average of 2-2/n games.

Anonymous

03:32

Now do the math for double-elimination :P

Eric Tressler

All you need is an infinite league, and then it's 2 :-o

Asymptotically (ignoring the inability for 1 team to play alone), the first situation is "how many times do you expect to flip a coin if you stop after you see tails", and double elimination is "... see tails twice"

but again by linearity of expectation, it's just twice the amount of flips you expect to have until you see tails once, so it's 4 games - {junk}

Anonymous

DE is interesting because the number of games is not constant - you may have 1 more in certain situations (if the loser bracket winner beats the winner bracket winner)

Eric Tressler

Expectation smooths over all kinds of things

Nathan Merrill

Actually, that's a clever way to think of it: You have 64 dice, all showing "3". A game consists of turning one of them to the next lower number, and keeping another one the same.

So yes, it's possible that the last remaining die has "3" on it or "2" on it

which would affect the number of games, but it's easy to calculate

Eric Tressler

New goal: devise tournament rules that result in an average of 3 games per team

quartata

03:43

a different angle to consider: whatever sort you pick, it should be something reatively easy to digest/visualize so people get why which teams are playing. i think merge sort is a good pick in that regard (and is also stable if you do have ties)

Eric Tressler

I guess you'd just modify double elimination to make a team flip a coin after they lose their first game to see whether they lose 1 or 2 games that game

Nathan Merrill

What if you had a 3-team game?

could that give you 3 games per team?

Actually, can that be a challenge? Write an efficient comparison sort using a tri-comparison function

Eric Tressler

Is there some standard tri-comparison function? I'm drawing a blank

Nathan Merrill

no. But there are two possibilities I can think of, and both are interesting

The first is if it gives you the full ordering (A < B < C) of the elements, the second is if it only gives you the best element of the three (A < B and A < C)

quartata

the former would be a simpler sort

Anonymous

03:48

@NathanMerrill So the first one would be from X^3 -> X^2, and the latter would be max (X^3 -> X, could be generalized to X^n -> X)

Anonymous

The latter would be a simpler extension of a normal comparison op

Anonymous

Though it would be trivial to reduce it to a regular 2-element comparison: always use a fixed element for the 3rd element.

Nathan Merrill

Both of them can be easily reduced to 2-element comparison

The key is to use the extra information efficiently

quartata

well. its only really a straight reduction if that fixed element is the infimum. which doesnt make much sense for teams. the worst possible team always getting to play a game as part of each comparison

Pavel

I spent four hours performing every optimzation humanly possible on my code before realizing the reason it was taking several minutes to run was that my cache, meant to expire every day, was never being marked as not expired.

quartata

03:55

browser cache?

Pavel

No this runs locally

I have my own cache system

It's supposed to fetch a gigabyte-sized JSON from an API and parse it

And I cache the list I parse out

Anonymous

05:18

That reminds me - does anyone know of a tool that can render a ridiculously large HTML file (~13 GB) into a PDF? I'm not concerned about speed - it just needs to successfully convert the file, without reading the entire file into memory.

New Main Posts

06:12

0

Q: Generate some rough numbers

Background A number n can be described as B-rough if all of the prime factors of n strictly exceed B. The Challenge Given two positive integers B and k, output the first k B-rough numbers. Examples Let f(B, k) be a function which returns the set containing the first k B-rough numbers. > f(1...

code-golf number-theory primes factoring

Downgoat

07:09

@Mego no idea but curious where you get such a large HTML from O.o

New Main Posts

0

Q: Is there any mistakes in this code?

The photo is from the book the c programming language by Brian Kernighan and Dennis Ritchie 2nd edition I am compiling it using mobile c and decoder and it is showing error.

programming-puzzle

flawr

09:03

@Mr.Xcoder I see, well good luck with everything!

Mr. Xcoder

@flawr Thank you very much!

Anush

09:14

Is this possible for ppcg? github.com/scikit-learn/scikit-learn/issues/12512

A copy button, in short

Erik the Outgolfer

@flawr looks like somebody likes Christmas... :P

Laikoni

11:34

@Anush Feature request on meta: meta.stackexchange.com/questions/32625/…

New Main Posts

11:55

0

Q: Count the corners, edges and faces of a cut cube

Coming from this sandbox post This is inspired from an 8th graders math test Intro We have a cube with following corners A(0, 0, 0) B(1, 0, 0) C(1, 1, 0) D(0, 1, 0) E(0, 0, 1) F(1, 0, 1) G(1, 1, 1) H(0, 1, 1) This cube clearly has 8 corners, 12 edges and 6 faces. If we now cut off corner ...

code-golf

Sherlock9

14:05

Hello everyone

It's a good thing I still remember to check if my challenge ideas have been posted before

Was about to post this one

Largest squarefree number that divides the input

Oh wait no

My idea was to divide out the squares, and then print the resulting integer, which is slightly different

144 after diving out the squares is 1, but the largest squarefree number that divides 144 is 6

Hmm

Erik the Outgolfer

Feedback requests: 1, 2

caird coinheringaahing

@EriktheOutgolfer For the second one, the rules sort of blend together, I'd recommend separating them (bullet points etc.)

Erik the Outgolfer

done

caird coinheringaahing

14:21

In the final bullet point (right at the end), what do n_5 and n_1 denote?

Erik the Outgolfer

whoops, should be x_5 and x_1

those are the requirements that must be met so that the ordering is valid

New Main Posts

15:38

1

Q: number of circles in a rectangle

calculate number of the maximum numbers of circles of radius r that can fit in a rectangle , the rectangle has height of x and width y.the circles touch each other in triangular shape, Write a function that take r , x and y as input and return the number of circles that fit in the rectangle.

code-golf math geometry

Erik the Outgolfer

@NewMainPosts so... not very good formatting and grammar, but surprisingly good challenge from a newcomer

New Sandboxed Posts

18:05

0

A: Sandbox for Proposed Challenges

Remove all squares! code-golfmath Given an integer n, divide out n's largest square divisor, and return the result. Test cases 1 1 60 15 96 6 125 5 1001 1001 Related challenge Note: Just typing this challenge idea up quickly. Will edit it to look nicer when I have ti...

Adám

18:18

@Mego @DJMcMayhem Can you give chat.stackexchange.com/users/379312/kaijaeger explicit write access to chat.stackexchange.com/rooms/52405/the-apl-orchard?

Zacharý

Another one from that conference?

DJMcMayhem

@Adám Done

Adám

@DJMcMayhem Thank you.

@Zacharý I advertised the Orchard on the last day. Kai is Mr. APLWiki

Zacharý

O_O

Is it getting close to that time o' year?

flawr

18:35

@EriktheOutgolfer Since halloween isn't really a thing here (or at lest has not been, it is getting more popular each time) some stores already have their christmas decorations out for about 4 weeks:)

Erik the Outgolfer

@flawr Jumbo stores in Greece always have Christmas products up way before Ohi Day (that is, 10/28) :P

I remember going to the one in my area this year (obviously, not for toys) and seeing, in this order, 1) Christmas products, starting from the top floor 2) Halloween products, starting from the first point of the bottom floor (of Jumbo, not the whole building), and then some more Christmas products 3) Ohi Day (October 28th) products, then more Christmas products...you can see the marketing here, as well as the focus on Christmas ;-)

Zacharý

"Oxi" means"no" right?

flawr

hehe, well I do have the impression that they are starting earlier every year

Erik the Outgolfer

yeah, it's "ochi" (όχι), actually, but Ohi Day isn't Ochi Day

flawr

I'm surprized they do not sell any chocolate easter bunnies yet.

Erik the Outgolfer

18:44

nope, they don't, that would be a giant overkill :P

flawr

what is Ohi day?

Erik the Outgolfer

and... easter?!

Zacharý

Wait ... what's the difference?

Erik the Outgolfer

@flawr October 28th, 1944, the day we want to think Ioannis Metaxas said a huge ΟΧΙ to Benito Mussolini and his Italian forces which tried to "peacefully occupy a few strategic locations in Greece"

flawr

Ah thanks. Are there any special traditions for celebrating that?

Erik the Outgolfer

18:48

@Zacharý the chocolate is in the shape of Santa Claus during Christmas

yeah, there are parades

it's one of the most important national anniversaries

also, many people put up Greek flags... some roads too :P

@EriktheOutgolfer 1940, duh

why do I always confuse that with October 12th, 1944...

flawr

I'm very bad when it comes to specific dates in history.

Erik the Outgolfer

well... it might be that the latter is when peace came, i.e. good, while the former is when war came ;-P

Zacharý

O_O

New Main Posts

19:07

-2

Q: Find the nth root

Introduction The n-th root of a number, \$x\$, often expressed as \$\sqrt[n]{x}\$ can be multiplied by itself \$n\$ times to equal \$x\$. In other words: $$(\sqrt[n]{x})^n = x$$ Challenge Given \$n > 1\$ and \$x > 0\$, your challenge is to calculate \$\sqrt[n]{x}\$, or the n-th root of \$x\$...

code-golf math code-challenge

flawr

19:17

@Mr.Xcoder recently suggested me (in a specific challenge proposal) to make a CW answer for all trivial answers. Is this something we already did frequently, or do we have some sort of relevant meta post?

Erik the Outgolfer

the relevant meta post is what we call "xnor's proposal"

25

A: Should we combine answers where the same code works in many different languages?

Combine equivalent trivial answers I think the idea is right, but needs to specifically target the problem case of built-in-does-it answers. Trivial challenges invite many trivial answers that are just a built-in. There is an overwhelming temptation to get loads of rep and attention with an ans...

flawr

@EriktheOutgolfer thanks a lot!

New Main Posts

19:37

0

Q: Ryley's Theorem

S. Ryley proved following theorem in 1825: Every rational number can be expressed as a sum of three rational cubes. Challenge Given some rational number \$r \in \mathbb Q \$ find three rational numbers \$a,b,c \in \mathbb Q\$ such that $$r= a^3+b^3+c^3.$$ Details Your submission should ...

code-golf math number-theory rational-numbers polynomials

Riker

@flawr nice hat

snek hats are good

flawr

@Riker thanks!

@Riker you should subscribe to snake discovery

(the videos include captions of the snakes thoughts, but is otherwise quite educational)

damn spelling

@Riker you know the most influential author among the reptiles? It's William Snakespeare

2

(Among his works there is a famous series about Harry the Lizard.)

Adám

I just walked outside. A neighbour has a lit image of Mr. Claus in their window.

New Main Posts

19:52

-1

Q: Rosencrantz and Guildenstern are Code

In the absurdist play Rosencrantz and Guildenstern are Dead, the two main characters Rosencrantz and Guildenstern(or are they?) are always mixing up which of them is who—or sometimes which of their own body parts is which—because of a perceived lack of individual identity. Wouldn't it be absurd i...

code-golf code-challenge

Zacharý

O_O

Riker

20:20

@flawr LOL

subscribed

request: snake hissing asmr

flawr

hehe:)

caird coinheringaahing

20:43

@NewMainPosts @flawr Was that in the Sandbox for a long time? I feel like I've seen that same post, by flawr

flawr

yep it has been there for a while

Erik the Outgolfer

@flawr the only flaw I can find in that challenge is that we're required to support every possible input beyond the language's limits

otherwise, nice challenge (even though I will most likely brute-force it >:D)

flawr

@EriktheOutgolfer I decided to do that because for rather simple input, the outputs can be exploding (or maybe have exploding intermediate values)

Erik the Outgolfer

regarding "exploding intermediate values": if you use a suitable ordering of \mathbb Z (e.g. [0, 1, -1, 2, -2, ...]), and a "little" bit of brute force, that shouldn't be a problem :P

flawr

@EriktheOutgolfer I know at least one proof that more or less directly constructs the solutions. I'm trying to implement that right now, and I think it might be competitive with bruteforcing solutions.

I think I have a 70 byte Haskell solution.

Erik the Outgolfer

20:52

I know what language I'm trying first... :P

flawr

I'm curious to see if anyone actually finds this proof and uses it in their golf.

Erik the Outgolfer

I assume we can't use Google to find that, right?

flawr

haven't tried so far:)

you can find at least one

Erik the Outgolfer

except that I'm not going to read 5 pages of proof, thanks

flawr

actually it is just a little more than 2 pages that are actually relevant

and more than 90% of those pages is actually white, so there cannot possibly be that much to read

Erik the Outgolfer

21:04

definitely not referring to this, eh?

flawr

that is the one I linked

Erik the Outgolfer

ah, didn't notice the edit

flawr

sorry!

Erik the Outgolfer

hah, Delfad0r posted a brute-force solution in Haskell... in 95 bytes

if we assume that to be optimal for brute-force... goodbye brute-force, then :P

flawr

I'm not quite sure if I have to include imports in my solution

if I do, it will be 88 bytes :)

Erik the Outgolfer

21:12

ah

I suspect you do

still, 7 bytes ahead :P

flawr

this is kind of a special case: you can define the function without using any imports

but you need the import to generate a rational number

I know that we can expect the input to our answers be of the correct type.

But I'm not sure how this particular case should be handled.

Erik the Outgolfer

but... can the function make the output without the imports?

flawr

it will only return rational numbers if you input a rational numbers

otherwise it uses floating poitn numbers

Dennis

12

Q: Byte count for imports (or other things) not needed for definition, but for execution

When we define a function that needs an import, we have to add it to the byte count. So far, so good. What about cases where the definition itself doesn't need the import, but when you want to call/execute the function you need it, for example to construct parameters? Examples can be found here ...

discussion code-golf scoring

flawr

but the challenge says that the input consist of a rationl number

Erik the Outgolfer

21:17

the challenge spec is to be translated per-language, and, if that means imports, imports it is

flawr

@Dennis thanks!

Erik the Outgolfer

also, if you're using operators that act differently on an imported type, it's pretty likely that the import is what defines the behavior of the operators in this case (especially since that's very easy to do in Haskell, methinks)

flawr

as I understand it, @Mego's answer to that meta would say in this case I do not have to count the import

Erik the Outgolfer

reads below top answer

yeah, looks like you've got a pretty 70 bytes over there

(if it works)

New Main Posts

0

Q: Tips for Big-O notation beginners

A beginner's guide to Big O notation by Rob Bell explains Big-O notation for beginners. Explain Big-O notation to beginners reading and writing algorithms, code, questions and answers for the fastest-algorithm tag at Programming Puzzles & Code Golf.

tips fastest-algorithm

-1

Q: Fastest algorithm to output array containing all integers in range excluding duplicate digits

Given input a single minimum integer 12 and a maximum integer 123456789 (9!), output a single array containing the input integer and all integers between input and input digits in reverse order (21; 987654321) including minimum and maximum in ascending or descending numeric values, where each dig...

math number combinatorics fastest-algorithm

flawr

21:21

too bad they didn't explicitly answer the Haskell case

@EriktheOutgolfer it seems those two answers contradict?

Erik the Outgolfer

Mego's is the winner there

that was a reference to sorting answers Dennis-style (i.e. by "active")

flawr

is there any other number I should add as an example?

Riker

@flawr I just watched that channel's bullsnake thingy

from not-yet-laid to incubating to opening to babby reveal

beautiful

10/10

flawr

I just learned so much about snakes even though I've hardly ever seen one in person :)

caird coinheringaahing

@flawr Last time in was in Switzerland (summer mountain hiking), a grass snake scared my dog and fascinated my dad :P

Riker

21:34

caird where do you live agian?

caird coinheringaahing

UK

flawr

@cairdcoinheringaahing how cool! (just had to look up "grass snake", they have a completely different name in german)

caird coinheringaahing

@flawr My dad loved catching snakes as a kid, and was disappointed that he couldn't bring the snake back to where we were staying :/

flawr

@cairdcoinheringaahing what kind of dog do you have?:)

caird coinheringaahing

@flawr Lab/springer spaniel cross (he was my last profile picture)

This

flawr

21:41

oh what a cute little guy :D

Zacharý

D'awwww

flawr

you should take it back as profile pic!!!

Erik the Outgolfer

IIRC caird had some GCSEs to do before putting it back as a profile pic or something

caird coinheringaahing

@EriktheOutgolfer Yeah, then I left for a while and sort of forgot about my PP

How's that?

Erik the Outgolfer

~~wait, do you have a lizard?~~ looks like people are impatient for Christmas...

caird coinheringaahing

21:51

@EriktheOutgolfer We have no other holiday between now and Christmas here (no Thanksgiving, for example) and I've always liked Christmas :P

flawr

22:07

@cairdcoinheringaahing yay:)

H.PWiz

@flawr Using the MSE post linked earlier, a 52 byte answer is possible. Better answers are likely though

flawr

@H.PWiz feel free to post!!

I'm curious to see that.

Erik the Outgolfer

yeah, if you have spent effort, it shouldn't go wasted

H.PWiz

Well, it was already 58 without introducing new variables, and with n=1

New Main Posts

22:36

0

Q: Captcha Capture

Captchas aren't meant to be machine-readable, and that's terrible. It is time to end this obvious bout of unfounded hatred for machines just trying to let you know about great deals on ṗḧ@ṛḿ4ćëüẗ1ċäḷṡ ƻđȺɏ. Note: All captchas were made by using a library that has been modified so that it mostly ...

parsing image-processing test-battery

flawr

@H.PWiz Are you gonna post it?

H.PWiz

Maybe later, once I've though more

Delfad0r

23:23

@H.PWiz I got my solution down to 69, but I'd be very interested to see yours. Please consider posting it :)

flawr

@Delfad0r I based mine on a construction I found in a popular number theory book.

Transcript for