The Nineteenth Byte

caird coinheringaahing

20:06

CMP: Should I add implicit casting to my golfing language?

dzaima

@cairdcoinheringaahing depends on whether or not there are overloads

IMO overloads for functions are more useful than implicit casting

caird coinheringaahing

No overloads, but maybe casting string versions of numbers into the integer versions ("123"+5 => 128)

dzaima

@cairdcoinheringaahing I think that "123"+5 => "1235" would be more useful

caird coinheringaahing

That's "123";5 => "1235" (concatenation)

dzaima

ah

though you could make both be +. That case of joining a number to a number to result to a string (IMO) is rare enough to have an extra casting byte wasted

Adám

20:11

@dzaima I think "123"+5 → [54,55,56] or "678".

caird coinheringaahing

I could, but then what would [1, 2, 3]+5 be?

dzaima

@cairdcoinheringaahing in SOGL that'd result to [1,2,3,5]

@Adám it's a matter of figuring out which of the options would be the most useful to be a one byte command. If that's useful enough, why not?

caird coinheringaahing

@dzaima Yeah, I've got vectorising commands in Levant, so I didn't think overloading + would be a good idea

New Main Posts

3

Q: Reduce a number by its largest digit

Task: Given an integer number in decimal number system, reduce it to a single decimal digit as follows: Convert the number to a list of decimal digits. Find the largest digit, D Remove D from the list. If there is more than one occurrence of D, choose the first from the left (at the most signi...

code-golf

dzaima

@cairdcoinheringaahing of course that could also result to [6,7,8] and overload only on numbers/strings

if you think that implicit casting is gonna be more useful than a couple more 1 byte commands, go ahead

Riker

20:54

@ASCII-only mind joining the ppcg game discord for d&d discussion?

New Sandboxed Posts

21:31

0

A: Sandbox for Proposed Challenges

Draw the ☣ (Biohazard Symbol) kolmogorov-complexitycode-golfgraphical-output Draw the Biohazard symbol in an arbitrary colour on a distinctly coloured background. Details As output writing to a file (raster and vector formats are permitted) or displaying on the screen. The symbol itself shoul...

New Meta Posts

22:35

1

Q: Should we reopen the "Tips for golfing in Befunge 93" question?

I'm referring to this question: Tips for golfing in Befunge 93 It's currently closed as a duplicate of "Tips for golfing in Befunge 98", but they're really not the same language - they're probably about as similar as C and C++. While there's obviously a fair amount of overlap, more than half of ...

discussion closed-questions reopening tips

Leaky Nun

22:46

@EriktheOutgolfer we use Greek alphabet in maths; what do Greeks use?

I think this tradition of using Greek alphabet began with Euclid?

he used Greek letters in the Elements

orlp

23:10

@LeakyNun hey how's it going

Leaky Nun

good

orlp

nice to hear

I implemented something cool over the past couple days (spent an hour here or there)

Leaky Nun

what is it?

orlp

@LeakyNun do you know what the hadamard product of generating functions is?

Leaky Nun

not yet

orlp

23:11

say I have two series a(n), b(n)

and their generating functions A(x), B(x)

then calculating the g.f. for a(n) + b(n) is simple, just A(x) + B(x) because the coefficients add up

Leaky Nun

now I do

orlp

but a(n)*b(n) isn't just A(x)*B(x), you need to multiply the coefficients of x

that's the Hadamard product

@LeakyNun gist.github.com/orlp/097da717e04a7cc2d6e23bd2ce58dfb4

I wrote some code that given two rational generating functions computes their hadamard product

Leaky Nun

nice

orlp

1

Q: Algorithm for computing Hadamard product of two rational generating functions

If I have two generating functions $A(x) = \sum_na_nx^n$ and $B(x) = \sum_n b_nx^n$ then the Hadamard product is $(A \star B)(x) = \sum_{n} a_nb_nx^n$. Now when $A$ and $B$ are both rational functions ($P(x)/Q(x)$ with polynomials $P, Q$) I've seen non-constructive proofs that $A \star B$ is a...

generating-functions hadamard-product

had to ask for some help though :P

Leaky Nun

interesting

but can you find the generating function for partial sums?

orlp

23:17

@LeakyNun partial sums of what?

Leaky Nun

of the coefficients of another generating function

orlp

can you be a bit more explicit?

like

a(0), a(0) + a(1), a(0) + a(1) + a(2), ...?

Leaky Nun

yes

orlp

@LeakyNun that's stupidly simple actually :)

A(x)/(1-x)

Leaky Nun

oh god

nice

orlp

23:20

so no hadamard product needed for that :)

I love that identity though

somewhat blew my mind when I first saw it

Leaky Nun

thanks

can you prove $\displaystyle \sum_{n=0}^\infty a_n b_n z^n = \frac 1 {2\pi} \int_0^{2\pi} F(\sqrt z e^{it}) G(\sqrt z e^{-it}) \ \mathrm dt$?

orlp

I can't

I'm aware of that integral form though

that was my first attempt but it got absolutely nowhere

it lead to stuff like this @LeakyNun

that's exactly 65/252

Leaky Nun

what led to it?

I was talking about proving that identity

orlp

I know, I'm saying that my first attempts of implementing the hadamard product using that identity led to stuff like that

Leaky Nun

on which sequences?

orlp

23:28

3

A: Bitwise XOR of rational numbers

Python 3, 193 164 bytes def x(a,b,z=0): l=[] while(a,b)not in l:l+=[(a,b)];z=2*z|(a<.5)^(b<.5);a=a*2%1;b=b*2%1 p=l.index((a,b));P=len(l)-p return((z>>P)+z%2**P*a**0/~-2**(P or 1))/2**p Takes input as Python 3's fractions.Fraction type, and outputs it as well. Fun fact (you can easily show...

if you write a rational number as the generating function of its binary digits

then A(x) + B(x) - 2*HadamardProduct(A(x),B(x)) is the generating function of the binary xor of those digits

Leaky Nun

I sense a root of unity filter

(referring to that formula I want to prove)

orlp

$$\int_{0}^{2\pi} A(r e^{it}) B(r e^{-it}) \, dt = \int_0^{2\pi} \sum_{m,n} a_n b_m r^{n+m} e^{i(n-m)t} \, dt = 2\pi \sum_{n \ge 0} a_n b_n r^{2n}$$

from math.stackexchange.com/a/66134/5558

Leaky Nun

thanks, it's dank

thanks a lot

orlp

in that post he also links to a cool blog post: qchu.wordpress.com/2009/10/07/extracting-the-diagonal

Leaky Nun

I need to do something like this tomorrow, and if you weren't here, I would have skipped this part

it's hard to explain what I'm doing though

orlp

23:34

well

now you have to :P

Leaky Nun

sort of an informal lecture to an informal group

thanks a million lol

orlp

what are the odds?

Leaky Nun

somehow you popped up at the right time

orlp

it's weird how I can show something like this to you when you're much better at this stuff than I am :P

I'm more of an engineer than a mathematician

Leaky Nun

I didn't know this stuff

hadamard product

orlp

23:35

but now I need to know what your informal lecture is about

and how it relates to this

Leaky Nun

generating functions :)

orlp

@LeakyNun what this implies though is pretty cool

given any two series that can be expressed as a linear recurrence

the product of their terms can as well

Leaky Nun

right

proof via power form

orlp

well in my case via rational generating functions

e.g. $a(n) = 2^n F_n^2$ has a recurrence

and its generating function is (hold on one second)

$\dfrac{2x(1-2x)}{(2x + 1)(4x^2 - 6x + 1)}$

Leaky Nun

thanks

orlp

23:41

doing that by hand is a nightmare :D

Leaky Nun

nice

can you tell me more lol

I may discover something useful

for tomorrow's lecture

orlp

often there's stuff about integer partitions in generating functions texts, right?

but only today I saw the full generic form

Leaky Nun

what do you mean?

orlp

so there's the number of partitions of n, right?

but you can also say the number of partitions of n, with k parts

or the number of partitions of n, with each part <= k

or we might want that the partition be distinct

so 1 + 1 + 1 = 3 isn't valid

from the book generatingfunctionology

with this you can derive all other formulae

Leaky Nun

hmm

orlp

23:46

math.upenn.edu/~wilf/gfology2.pdf

page 101

@LeakyNun I used that to solve this problem: math.stackexchange.com/questions/2525536/…

(or well, a generalization)

Leaky Nun

is it hard to derive?

It's just convolution isn't it

you have $(1+x+...+x^8)$ for each variable

and take its fourth power

and find the coefficient of $x^{18}$

orlp

I mean isn't that what generating functions are often effectively used for?

as a convenient way to notate convolution

Leaky Nun

hmm

orlp

there's two sides to generating functions

one is the analytical side, with the infinite sums with closed forms

and the other is the combinatorical side

which basically abuses polynomial multiplication to get convolution

but since they're both using the same notation you can jump from one side to the other and use the power of both, making it very powerful :)

Leaky Nun

how hard is it to prove the formula?

orlp

23:51

I don't know I haven't tried

Leaky Nun

I mean, the idea of using $y$ to further generalize it in order to solve it is very dank

generalize it, trivialize it, and then specialize it

orlp

I'm not too familiar with the combinatorical side of gfs at the moment

honestly you should just read generatingfunctionology :)

great book

Leaky Nun

you see, $\sum p(n,4,8)x^n = (1+x+\cdots+x^8)^4$

so $\sum p(n,k,R) x^n = (1+x+\cdots+x^R)^k = \dfrac{(1-x^{R+1})^k}{(1-x)^k}$

orlp

@LeakyNun some more material

go to page 52 of math.upenn.edu/~wilf/gfology2.pdf

Leaky Nun

now, $\sum \sum p(n,k,R) x^n y^k = (1+x+\cdots+x^R)^k = \sum \left( \dfrac{y(1-x^{R+1})}{1-x} \right)^k = \dfrac 1 {1 - \left( \frac{y(1-x^{R+1})}{1-x} \right)} = \dfrac {1-x} {1 - x - y + yx^{R+1}}$

$1-x-y+yx^{R+1} = (1-y)-x(1-yx^R)$

hmm, this leads me nowhere

orlp

23:59

I'm sorry, can't be of much help here atm

Leaky Nun

ok

Transcript for