The Nineteenth Byte

MilkyWay90

00:02

I am going to make a constant output golfer in Python for Turing Machine But Way Worse

MilkyWay90

02:08

Actually nevermind

Anonymous

03:16

Things that grind my gears: when a website for a JS library doesn't have the library loaded so that I can test it out in the console

Anush

08:07

hi all

New Main Posts

08:26

-1

Q: Maximizing by swapping

Input An integer n in the range 100 to 10^18 and an integer k in the range 1 to 18, inclusive. The swap operation A swap chooses two digits at different positions and exchanges their positions, as long as the swap does not result in a leading zero. For example if we start with the integer 1234...

dzaima

12:43

@Anush another guess for why people don't like your restricted-time challenges - by making the challenges generally just hard to do, the code-golf aspect becomes just pointless as for a complicated program there isn't much golfing leeway. they also kind of seem like homework/do-this-for-me questions as you don't show that you even know it's possible (do you?)

what you like are "find a good complicated algorithm" challenges, but the problem is that once there's already an answer, copying the whole algorithm to golf a bit in another language feels pointless, and making a new algorithm is bound to be very hard

@NewMainPosts (okay that challenge might not be that hard, but for it restricted-complexity and no explicit input size limit fits pretty well)

also brb making a language that takes 60s to start up so it literally can't compete :p

AdmBorkBork

13:20

That's a new one for me

Erik the Outgolfer

pretty old on SO, actually

AdmBorkBork

Oh, I don't doubt that it's a standard message, just the first time I've seen it

Adám

@AdmBorkBork Your challenge doesn't have an objective winning criteria? ;-)

Erik the Outgolfer

@Adám that's SO...

New Main Posts

13:37

0

Q: I'm in your subnets, golfing your code

Given an IPv4 address in dotted-quad notation, and an IPv4 subnet in CIDR notation, determine if the address is in the subnet. Output a distinct and consistent value if it is in the subnet, and a separate distinct and consistent value if it is not in the subnet. The output values do not necessari...

code-golf decision-problem networking

Erik the Outgolfer

whoops, notice had a point! :P

Anush

13:55

@dzaima interesting, thanks

orlp

@flawr if you want I can discuss my results so far regarding the dithering with gamma correction

it's a bit of a mess >.<

Anush

16:15

removed restricted-time under severe peer pressure

New Sandboxed Posts

16:54

0

A: Sandbox for Proposed Challenges

Calculate Trinary Complexity We have a lot of binary questions on this site, but not many trinary questions. The Trinary Complexity of a decimal integer is the number of iterations of f(n) required to reach a result < 3, where f(n) is the sum of the digits of the trinary representation of n. E...

Skidsdev

17:30

ah man I was so close to a decent answer for the digit swapping challenge until i tested 510 and realised my code is doing it in k or fewer swaps, not exactly k swaps

Curse you @Anush

flawr

@Riker Space X was so yesterday ^

@orlp I do now understand the problem but I don't know enough to provide anything meaningful:) I have the impression that it is a hard problem and I have a hunch that it is impossible to solve for arbitrary t. Maybe one could find a solution if you restrict it to a certain class of t's but I already failed for t(x) = x^k with n(s,r) = n(r) (independent of s)

Skidsdev

17:51

@flawr Does that mean that when the russians finally snap we'll have Space Z?

New Main Posts

1

Q: Shantae Dance Matching

In the original Shantae game, there are transformation dances that you have to input in time using the D-Pad, A, and B. If you complete a predefined sequence while dancing, you will transform into the corresponding form (or teleport or heal). Your task is to output the corresponding effect when g...

code-golf sequence classification

flawr

@Skidsdev I hope we don't :)

Skidsdev

18:08

@flawr Likewise

orlp

18:34

@flawr I find that the problem really simplifies if you look at it from the perspective of the quantized values

e.g. instead of studying where quantize(s + n(s, r)) ends up you start with a certain quantized value, e.g. 4 and ask what the chance is that s ends up being 4

flawr

I think this is the formulation you used on mathunderflow?

I'll have to look at that again, because I didn't really have an intuition for the quantization process.

orlp

yes it is

Skidsdev

19:00

is there a shorter NodeJS way to check if an array is empty than arr.length?

flawr

arr==[] maybe?

nope

Skidsdev

nah arrays are ref types in js

flawr

same length: a==false

Skidsdev

oh wait

an empty array is falsey

flawr

or a==1<0?

Skidsdev

19:04

so I can do if(a)

DJMcMayhem

@Skidsdev sigh

Oh javascript

flawr

I wouldn't be surprized if an empty array is falsey from the left side but truthy from the right.

Skidsdev

nevermind, an empty array isn't falsey, and I just crashed a browser tab trying to test it

I did a=[1,2,3]while(a)a.pop() in the browser console, now that tab has frozen

Veskah

RIP in peace

Skidsdev

@flawr that seems to work

but 1<0 can be shortened to !1

New Main Posts

19:09

0

Q: Make some Prime Squares!

What is a Prime Square? A Prime Square is a square where all four edges are different prime numbers. But which ones? And how do we construct them? Here is an example of a 4x4 Prime Square 1009 0 0 3 0 1021 First we start from the upper left corner. We are working c...

code-golf ascii-art

flawr

or you could do a!=0

Skidsdev

yes I can

that's a shame I was looking forward to doing a!=!1

because !=! is just so comical to me

@flawr well that's 8 bytes golfed, thanks!

or would it be !thanks? :P

orlp

@flawr so for a certain value c (I've been using c in my code instead of s*(m-1) for the signal)

there are three possible outcomes after quantization

Round[c], Round[c] - 1, Round[c] + 1, make sense?

flawr

@Skidsdev np I'm always happy to abuse JS:)

@orlp 1 moment, I'll have to get the cookies out of the oven

orlp

the cookies come first, entirely understandable

Skidsdev

19:17

well on the topic of abusing JS, is there a golfier way to include a variable in a regex than this: RegExp("^D"+z)

flawr

@orlp let me first take one step back: the problem is that you want to dither before you do the transformation, such that it is correct after the transformation?

H.PWiz

It can be shorter to:
eval(`/^D`+z)

orlp

@flawr there is no before/after

H.PWiz

according to this tip

orlp

the dither takes in sRGB values (in float 0-1) and outputs sRGB values (in integer [0, m))

it just happens to be that the sum of two sRGB values as we perceive it isn't a + b

it's ti(t(a) + t(b)) where ti = inverse t

and t converts sRGB to a linear space

now the idea behind dithering is that we introduce variance such that the average color is correct

but in an average we sum - meaning we have to take into account t or our dither will be incorrect

Skidsdev

19:26

@H.PWiz I believe it would still need the closing delimiter, which would make it eval(`/^D${z}/')

which is 2 bytes longer than RegExp("^D"+z)

H.PWiz

That's what I meant

Skidsdev

I think that tip only works when the variable is within the regex, rather than at the end of it

H.PWiz

Well, they also had new in the emaple

Skidsdev

I mean, you save 2 bytes by going from RegExp to eval, but lose 2 bytes by adding the /, so I'm not actually sure it saves any bytes overall

yeah, that's either outdated or a slip-up on their part, JS constructors don't need the new keyword

flawr

@orlp ah now I see the point, thanks for this excellent explanation!

orlp

19:31

(click for full-size to defeat moiree)

flawr

This property of the triangle distribution is somehow incredible

orlp

@flawr as an example the above is 50% white 50% black on the left and on the right (0.5, 0.5, 0.5) sRGB

notice how the 50% white / 50% black is way too bright?

@flawr this part I can reproduce now!

that is, I can already re-invent the triangular distribution

flawr

@orlp yeah I see that

orlp

>>> (0.5*0 + 0.5*1**(2.4))**(1/2.4)
0.7491535384383408

but to come back

@flawr so for a certain value c (I've been using c in my code instead of s*(m-1) for the signal)
there are three possible outcomes after quantization
Round[c] - 1, Round[c], Round[c] + 1, make sense?

and depending on the distance of c to Round[c] you get different chances for each of those 3 outcomes

flawr

yep, the gray closest to c, and one step above and below, right?

yes

orlp

19:39

you are familiar with mathematica, right?

flawr

not terribly, but I think I'll be able to read the most basic things

orlp

FullSimplify[Solve[{
    x*(Round[c] + 1) + y*(Round[c]) + z*(Round[c] - 1) == c,
    x + y + z == 1,
    x*(c -(Round[c]+1))^2 + y*(c - Round[c])^2 + z*(c - (Round[c]-1))^2 == 1/4
    }, {x, y, z}
]]

this is what I did

we want to know x, y, z which are respectively the chances of quantizing c to Round[c] - 1, Round[c], Round[c] + 1

the first equation states that the average must be c

flawr

go on

orlp

the second that the probabilities must sum to 1

the last is that the variance must be 1/4

flawr

why do we want 1/4?

for Std = 1/2?

Neil

19:41

@Skidsdev depends on the array's contents e.g. if it contains integers then you can use 1/arr[0] or arr+arr but this doesn't work if the array contains only the empty array.

orlp

@flawr I'd expect the error on average to be 1/2

Skidsdev

@Neil it's an array of only strings, I went with a!=0 which is 4 bytes shorter than the a.length I was using before

orlp

thus I'd expect the variance to be half that

I'm not explaining this well

Neil

well note that ["0"]==0

orlp

1/4 is just the lowest possible constant variance over the domain

ah now I remember the explanation

(1/2)^2 = 1/4

c - Round[c] is a maximum of 1/2

at least that's how I backsplained it in my head

@flawr I'm cheating here because I found out the 1/4th from measurement of the original triangular distribution

regardless, that solves to:

{{x -> 1/8 (1 + 2 c - 2 Round[c])^2,
  y -> 3/4 - c^2 + 2 c Round[c] - Round[c]^2,
  z -> 1/8 (1 - 2 c + 2 Round[c])^2}}

Skidsdev

19:47

@Neil good to know, but in this particular case the strings will only ever be /[UDLRAB]+/

Neil

in that case 1/a should work, I think

orlp

@flawr and this is what we want

in the linear case that is... without t

Adám

@orlp What is that?

orlp

@Adám a long story about dithering, quantization, the triangular distribution and gamma correction

Adám

@orlp No, I meant which application/language.

orlp

19:51

@Adám wolfram language

@flawr this resulting piecewise function is the same function you'd get by convolving the triangular distribution PDF with the unit box

flawr

so a second degree spline basis function it seems?

orlp

I'm not familiar with that

AdmBorkBork

I recognize some of those words. ;-)

orlp

flawr

I'll gladly talk about that another time, but I think it is probably not relevant right now (but it might be:)

orlp

19:58

why convolve with the unit box?

Skidsdev

@Neil oh wait, I factored out one of the arrays, and the other is actually a string (consisting only of /^[UDLRAB.]+$/), 1/a doesn't seem to work for a string

orlp

well the unit box centered around x is the domain that gets rounded to x in a sense

I don't know I'm terrible at explaining this stuff

it made sense at some point in my head and it is correct so \o/

flawr

hehe we all know that feeling:)

orlp

but to get to the point

we now know how to construct our function

so let's try to do it with the transform in mind

flawr

@orlp I'm still trying to wwrap my head around what I see here. Can you explain again, what is p?

orlp

20:01

@flawr p[c, k] is the probability that c quantizes to k

(where k is an integer in the neighbourhood of c)

in the example above we have x = p[c, Round[c] - 1]

y = p[c, Round[c]]

z = p[c, Round[c] + 1]

@flawr for example the purple curve centered around 3

you can see that it's zero at 5

so c = 5 has zero chance of quantizing to 3

same for c = 4.5

but c = 4 has a small chance of quantizing to 3

and c = 3 has the highest chance of quantizing to 3

flawr

Ok yes I understand!

This is beautiful:)

orlp

this way simplifies the problem immensely

because instead of having to solve integration

we just have 3 functions in the neighbourhood of any c

it really is quite magic that these curves perfectly add up to the y = x curve :D

and their variances to the y = 1/4 curve

Skidsdev

alright last JS golf question: Is there a golfier way to remove the first char of a string than d=d.substr(1)?

if it was an array I could use d.shift(), but string doesn't have shift

oh I can use d=d.slice(1), that's a little better

DJMcMayhem

I was just about to say that

But it would be better if you can avoid the assignment entirely.

orlp

@flawr i.imgur.com/D6IRQiy.png

that was the next logical step

Skidsdev

20:13

@DJMcMayhem exactly, array.shift() modifies in place, I don't think there's an equivalent for strings

DJMcMayhem

I meant something along the lines of using console.log(d.slice(1)) instead of d=d.slice(1);console.log(d)

Skidsdev

oh yeah not sure that's possible here

each "slice" of d is referenced multiple times

so I can't slice it at reference time

also re: earlier discussion on checking array length. Now that I've factored out the actual array and just have the string left, the string on its own is a condition, because empty strings are falsey

orlp

@flawr unfortunately the result is a total mess

it's not correct

yes, the probabilities sum to 1

the variance is 1/4

and the average does come to c

but the probabilities aren't in [0, 1]

since the solution is unique (3 variables, 3 equations) and it doesn't work we know that we can't have constant 1/4 variance

and I've tried various (hehe) constant variances but they all are broken

so we need non-constant variance but I have no idea what/how

Skidsdev

I should make a language called ES6 just to add confusion to the world

flawr

@orlp WHAT HAVE YOU DONE IT IS ALL BROKEN!!!

So you've tried transforming these basis functions too but that didn't seem to work out (or only almost)

orlp

20:22

I don't know what a basis function is

my best result so far

has been to solve the above system of equations under-determined

leaving out the constant variance

giving me y, z in terms of x

meaning I only have to find x

flawr

maybe it is worth taking a small detour into b-splines:)

are you familiar with the term basis from linear algebra?

orlp

imgur.com/a/TZMXxv3

this is what I got from manually fitting a curve

it's definitely workable

but no mathematical justification

it has a small kink

and I have no idea if it's even close to optimal

@flawr I am sort of, a linear combination of basis vectors can make any other vector

Neil

@Skidsdev well if you want to know whether a string is empty just use !s

oh you already said that later, nm

flawr

@orlp yeah a basis is a bunch of things (linearly independend blablabla) that span the whole space of things

so splines are (roughly) some piecewise polynomial functions (of a certain degree)

and if you take a fixed degree and fixed nodes these form a vector space

and b-splines are just that. you express a spline as a linear combination of basis splines

the piecewise constant splines can be expressed using a basis of box functions (lets call them B)

the piecewise linear splines can be expressed using a basis of triangle functions (that are basically B convolved with B, let us denote this B*B)

the piecewise quadratic splines can be expressed using a basis of B*B*B

... cubic ... B*B*B*B

... quartic ... B*B*B*B*B

I hope the pattern is not too difficult to spot :D

@orlp these bumps seem to be a basis of quadratic splines

orlp

the bumps are only a visualization though

they're probabilities

flawr

20:41

well they all sum to this linear function right?

orlp

no

to make it easy to debug I wrap the entire sum in a ti

they all sum to t[x] which is not linear (but if we wrap the sum in ti it will obviously sum to x)

flawr

are you talking about the sRGB case now?

orlp

yes

note the ti on the last line

flawr

(I was talking about the first case where everything worked out fine.)

orlp

ohh

alright yeah, then continue

flawr

20:50

I was now just trying to find out whether we can modify those basis vectors/functions/distributions/bumps/whateveryouwannacallit to exactly represent t[x]

(instead of x)

I mean I think this is exactly what you're trying to do, but I think I was just trying to look at it form a perspective I'm more familiar with:)

orlp

wait maybe I can differentiate the variance with respect to c

then set it equal to 0 and solve

Riker

22:15

@flawr yeah, I'm not certain why they didn't clue into this earlier

everybody knows space is straight up

space X is just gonna hit china or europe depending on which way they go

MilkyWay90

23:36

I am getting bored

Transcript for