The Nineteenth Byte

Adám

00:00

@EriktheOutgolfer True, but ⊢(/⍨)⊢≤≢ is a byte shorter.

Pavel

@Adám What is it even supposed to look like?

Erik the Outgolfer

@Adám ...anyway

Adám

@Pavel bugs.chromium.org/p/chromium/issues/detail?id=821173

New Sandboxed Posts

01:21

0

A: Sandbox for Proposed Challenges

A note about this meta post: I just have one example right now, but I will have three in the final. I thought it would be interesting to have a problem about something I know a bit about. Right now it seems a bit mathy, but I wanted to ground the problem on something real. It feels more 'real-...

Pavel

So, in .NET, types are either structs (stack-allocated) or classes (heap-allocated). The latest version added a new construct, the ref struct. Which is a stack-allocated struct that gets passed by reference when used as a parameter. I have no idea what the point is.

Zacharý

So, a struct is normally passed down by VALUE??

Pavel

Yes.

That's the point of a struct.

Zacharý

Whoops, must have been derping for a sec.

Pavel

@Pavel Note that ref structs have to be immutable. So you can't pass it to a function that modifies its arguments.

Zacharý

01:33

@Pavel That is pointless.

Downgoat

twitter.com/martijn_cuppens/status/1015169981368225793?s=21

4

Cat Wizard

02:08

1

A: Sandbox for Proposed Challenges

Existential Golf Math has a lot of symbols. Some might say too many symbols. So lets do some math with pictures. Lets have a paper, which we will draw on. To start the paper is empty, we will say that is equivalent to \$\top\$ or \$\textit{true}\$. If we write other things on the paper they...

Is my explanation of the system clear? I know the challenge is not yet complete.

quartata

02:20

I find it rather odd that changing the listener position causes stuttering but not changing the position of the source

oh well

Jo King

02:52

Apparently my IP has been blacklisted from asciitable.com...

user202729

03:04

Same for me...

There is ascii.cl.

Zacharý

04:24

@JoKing ._o

PhiNotPi

Today I saw a .menu domain in the wild.

Anonymous

05:13

@Pavel I guess to save memory and avoid unwanted side effects of copying a struct a bunch?

Pavel

@Mego I actually have since looked it up and found that there's another restriction on ref structs: They can never appear on the heap, even as a a member of some other object. This forces them to be local variables and allows them to work more safely with stackalloc'd pointers and whatnot.

(stackalloc is like alloca)

Anonymous

Interesting

Neil

08:59

@Downgoat In Firefox it seems to draw the outline as two squares plus four rectangles plus four triangles, however when the offset causes the hole to have negative size then it just keeps moving the squares and they end up where you see them in the diagram. As for the rectangles and triangles... well, try an offset of -80px... no, I don't understand it either.

Erik the Outgolfer

10:12

@JoKing wait why

Jo King

@EriktheOutgolfer ¯\_(ツ)_/¯

Erik the Outgolfer

it works for me

Jo King

Oh, it's back now

Erik the Outgolfer

what error did you get?

Jo King

Something like "Your IP has been blacklisted. If you believe this is in error, please contact your service provider.".

user202729

10:56

@CatWizard Very clear.

user202729

12:33

CMC: code-golf Given an edge-connected region of 1s as a rectangular binary matrix, output number of holes in it. Use O(log n) memory and O(n log n) time, in bit complexity (O(1) mem and O(n) time in word complexity).

Try to come up with an algorithm first. I guarantee that it's possible.

wastl

13:01

I just thought I had invented a great algorithm for bitshifts by a rational and started writing a sandbox post until I noticed that a << b would equal floor(a * (2**b) and it would be too trivial.

feersum

13:12

@user202729 What are you expecting the size of a word to be? The size of the whole matrix? Of one row?

user202729

@feersum Of n.

feersum

What's n?

user202729

Oh, I forgot that. n is the number of 0/1 in the matrix.

feersum

Number of entries or of each dimension?

user202729

thinking

O(n) time (bit complexity) is possible.

feersum

13:14

Not sure how a hole is defined either.

user202729

Number of connected component of 0 inside the outer bound of the 1s.

Example input: (█ for 1, space for 0)

█████
█ █ █
█████

-> 2

Ouch, line spacing...

██ ██
█   █
█████
-> 0

feersum

I'm afraid I am not really following this definition as that one seems to not be contained by 1s.

user202729

@feersum Better now?

feersum

The connected component does not count iff if it connects to an edge of the matrix?

user202729

Assume the matrix is surrounded by 0s.

feersum

13:22

Also the memory complexities don't match.

user202729

@feersum Why?

feersum

O(1) words of memory is O(n) bits of memory.

user202729

@feersum O(1) words of memory is O(log n) bits of memory.

10 mins ago, by user202729

@feersum Of n.

feersum

I interpreted as "the size of a word is n"

Anyway I see that it is supposed to log n.

So far I can do it in O(log(n)) bits of memory, but only at the cost of being slow.

user202729

13:44

██
█ █
███
-> 1

Leaky Nun

not 2?

user202729

23 mins ago, by user202729

Assume the matrix is surrounded by 0s.

Leaky Nun

ok

user202729

Refined statement:

Leaky Nun

so what is a word?

user202729

13:48

CMC: code-golf Given an edge-connected region of 1s as a rectangular binary matrix consisting of n numbers, output number of holes in it. Assume the matrix is surrounded by zeroes, and a hole is a edge-connected region of 0s inside the 1 block. Use O(log n) memory and O(n log n) time, in bit complexity (O(1) mem and O(n) time in word complexity, assume a word is O(log n) bits).

thinking again ...

I have not yet rigorously proven it. I have to find some way to make the spec so it's possible.

feersum

I'm not believing it can be done in O(log n) memory without at least O(n^1.5) time.

user202729

I think it can be done.

Looks good.

Should I give a hint?

Cat Wizard

14:11

I'd like to give it a whirl first

ok go ahead

user202729

Almost spoiler. (I hope I don't make any mistakes anyway)

feersum

14:53

@user202729 Please explain your solution?

user202729

Assume that the piece of 1 is a 3D shape (similar to a dihedron). Then compute the number of vertices, edges, faces. Then use that to compute the genus. That's the answer.

feersum

How do you know the number of faces?

Oh, I didn't read the constraint that the 1s are a single connected component.

That's why it didn't make sense to me.

user202729

Just two times number of 1.

Anush

15:18

hi.. I have an algo question. If I want to calculate the pearson correlation coefficient between two vectors of the same length it is nice and simple wikimedia.org/api/rest_v1/media/math/render/svg/…

but what if I have a short vector of length m and a long vector and I want to compute the correlation coefficient between the short vector and every subvector of the long one of length m?

Zacharý

15:35

@LeakyNun: do you know what would model would model chained ?'s in befunge?

Never mind: I think it's a Markov chain, right?

user202729

@Anush fastest-algorithm?

FrownyFrog

15:54

why doesn't this work? codegolf.stackexchange.com/a/97803/74681

did xkcd change the format?

Anonymous

18:45

@FrownyFrog Slightly - the image permalink is https now, so the regex doesn't work.

Pavel

That challenge is so poorly written. It only got upvotes because xkcd.

dylnan

19:08

@user202729 Would that count as a different language? Jelly UTF-8 v. Jelly SBCS

This is a plea for @CatWizard to keep up the good work with the avatars.

2

Zacharý

20:01

Does anyone know of a C++ compiler that doesn't complain about shebangs?

Anonymous

@Zacharý No, because then it wouldn't be C++

Pavel

Why would you put a #! in C++

Zacharý

Polyglot...

Pavel

But why would that need a #!

Anonymous

Probably because there's already a #! in it

Pavel

20:09

Oh, the polyglot challenge

That one

Zacharý

No, most likely not for that challenge.

https://tio.run/##bVJdT9swFH2uf8XBrVBD12TlsV9TVxAgIYY2pm0CNFzHTbwlduQ40G7jt3e3KdkY2kMSO@eec32Pz0KU6WbTxiyOIaASUSVGnMNb2hU2WyeZ9fCq9EiFM6ossVjjQqujH@rbd7tgbcxtlomiVOBzGysOYWLwmUuqXBlfcpRKem1NiaV1WCjvlYNaFcppZaRiTAqPKSRxmbeVTFE4TUTG2Pns4uTj7OT469nF0fHnyYC9/XJ1/GHCO90Hib4cbzkBZ8vK1B2QCZNUIlHd4CdrKZla8DY6/6qE6AxeoVMr0Sg0GW9q31fGaJNQAcd0/5C1FuQN9QHvHPKprXxReda6vqb9G469CV7j9hb7@6jpl84mTuSQjlgqDsMn2b6h@gH/5dT9dDu29CpuOr783zcZa@kl9iDzAruOaMBtp/8CxBrBp8qw1k73k7M0xq4qxKlaxVVeDAldrWI0cyw1a70wmIztvrCrNwiCPwb1cXPX6W7vaycS3NxBm51f0@baHhllIvW@KIdRlGifVotQ2jy6cusz/85k2qjIu7X2tlkrFeWipFhED04UFIySFJq7BN@Gj4P…

Trying to fit Befunge in there, but I don't know how...

Pavel

\
# pragma once

That works with C++ and Python, but I don't know D.

dzaima

@Pavel D is the biggest problem there

Zacharý

D is the big problem: the only # allowed is #line...

Pavel

Sure, #line works in C++ too

Zacharý

20:22

The problem there: we can't figure out how to get Befunge to redirect, not to mention Befunge-98 will just bounce between l and i forever (I think)

dzaima

@Pavel also Error: character '\' is not a valid token :/

Pavel

What does " do in Befunge?

Zacharý

Toggle string mode... that means anything inside of " ... " will be a string (so redirects won't work)

We can't put three quotation marks or escape them with ", because D breaks.

New Main Posts

23:32

0

Q: Double a number's continued fraction

Your task is, given x, output 2*x. Easy right!? But there's a catch: x will be given as a (possibly infinite) continued fraction, and the output must be a continued fraction. The input is guaranteed to be a real algebraic number whose degree is at most 2. Input: The continued fraction of x. This...

Erik the Outgolfer

> If the repeating part is empty, that indicates a rational number.

not so sure about that...

Leaky Nun

@EriktheOutgolfer why not?

Erik the Outgolfer

@LeakyNun because 1 ÷ 3

Pavel

@NewMainPosts I'm more than confident Mathematica's builtin multiplication would work, but I don't remember properly how continued fractions work to test

Leaky Nun

1/3 = [0;3]

Pavel

23:46

I suppose ContinuedFraction[2*FromContinuedFraction@#]& would work

Cat Wizard

@Pavel How does mathematica represent numbers?

Pavel

@CatWizard Depends?

Cat Wizard

What does FromContinuedFraction return?

Pavel

@CatWizard Try it online!

FreezePhoenix

@quartata since when did Closure Compiler recognize copyright comments?

Cat Wizard

23:49

@Pavel That doesn't help. What type does that function return?

quartata

@FreezePhoenix no idea

Pavel

@CatWizard List

Cat Wizard

No FromContinuedFraction.

Of course ContinuedFraction returns a list

Pavel

@CatWizard Oh, it returns a normal number

FreezePhoenix

@quartata I thought you made closure-compiler...

quartata

23:51

...what?

Cat Wizard

@Pavel What are normal numbers!?

FreezePhoenix

Wait did you just mean you had to fix your code for closure compiler, so it wouldn't throw a fit?

quartata

no I had to fix someone else's code for it

Pavel

@CatWizard The type depends on the value. Sqrt[2] has type Power, and is a complex type represented by 2 and 1/2.

If you print it, you get Sqrt[2].

It has infinite precision.

Cat Wizard

I don't know then. Mathematica is too dumb for me to want to spend any more time thinking about this.

Pavel

23:54

@CatWizard What do you mean?

Cat Wizard

> The type depends on the value.

Pavel

That's the same as in, say python, where a small value is an int and a really big one is called a long

Cat Wizard

Yeah, and that's bad.

Pavel

It's treated the same as any other number.

@CatWizard I'm not seeing the problem. It's just a number. The low-level representation doesn't matter.

Cat Wizard

Dynamic typing is fine. But you have to put thought into your type system, instead of just pretending types don't exist.

Pavel

23:58

@CatWizard But why does it matter?

Not needing to care about types is kinda the point.

Transcript for