The Nineteenth Byte

Pavel

11:01 PM

Why does PyCharm think self.ip[0]+=1 is fine but ++self.ip[0] is 'useless'

DJMcMayhem

Because Python doesn't have a ++ operator?

Nathan Merrill

because ++ isn't an operator

:P

Pavel

Isn't it? Increment one?

Nathan Merrill

nope. Self-modifying statements like that don't work

ATaco

I had an idea for the time capsule!

Threead, an Assembly-ish language that runs three simultaneous scripts that can only write to their own memory tapes, and most functions read from the other two.

Lynn

11:09 PM

Wow, that would be a great answer to this old question

a = 0
while a <= 10:
    print(a)
    ++a

FlipTack

@Pavel that's just "unary plus unary plus self.ip[0]" which just computes an unused value

Lynn

Why doesn’t it terminate?! :)

Pavel

@ATaco do you need the form link?

ATaco

(Yes)

Pavel

docs.google.com/forms/d/…

Is there a way to append a list to another list so that it creates a 2d list instead of flattening it?

ATaco

11:13 PM

Which language?

Pavel

Python

Eᴀsᴛᴇʀʟʏ Iʀᴋ

yeah, list(<orig list>) + list(<next list>)

f=lambda x,y:[x]+[y]

Pavel

Oh, thanks!

ATaco

Python, I'm not sure. Lua would require list[#list+1] = list2

Eᴀsᴛᴇʀʟʏ Iʀᴋ

o_O explain?

ATaco

11:14 PM

But Lua doesn't like doing anything nicely.

Eᴀsᴛᴇʀʟʏ Iʀᴋ

yeah

Pavel

Does [<orgi list>]+[<next list>] work?

Lynn

[x]+[y] is just… [x, y].

Pavel

But it works in the lambda

ATaco

Wait, are you trying to make list = [list1, list2] or list = [(contents of list1), list2]?

Pavel

11:16 PM

The first one

orlp

chat mini-challenge: given a uniformly chosen combination of 4 32-bit integers, how many bits do you need to store such a combination?

when I say uniformly chosen I mean that any such combination (e.g. {0, 0, 0, 0} or {100, 30, 13, 25}) has an equal chance of being chosen

the naive solution just uses 4 32-bit integers (128 bits), but you can do better

note: order does not matter

{0, 1, 2, 3} is the same combination as {3, 1, 0, 2}

Lynn

ceil(log2(2^32 choose 4)) surely?

Which is 124

orlp

hrm, you coincidently got the right answer

Lynn

That’s not a coincidence, that’s doing the math!

orlp

{0, 0, 0, 0} is a valid input, but can not be encoded with your n choose k

since we want combinations with replacement

Lynn

11:21 PM

Oh, I see.

ATaco

I'm curious as to what your solution is, Orlp.

orlp

well combinations with replacement is (n+m-1)!/(m!(n-1)!)

you can also write that as ((n+m-1)!/(n-1)!)/m!

if you take m=4 you get

Pavel

I give up on python for today.

orlp

n(n+1)(n+2)(n+3)/24

the log2 of that is how many bits we need

Pavel

I'll just rewrite the interpreter in Java, figure out a way to store mixed data types

orlp

11:23 PM

using log rules we get an exact answer

log2(n)+log2(n+1)+log2(n+2)+log2(n+3)-log2(24)

with n=2^32

which is 123.4150...

ATaco

Storing the data is the easy part, Pavel.

FlipTack

@Pavel can't you use unchecked lists in Java?

Compiler will probably give some warnings but it's fine

Pavel

Maybe just do java.util.ArrayList<java.util.ArrayList<Object>>, and hope no one looks at the code

ATaco

Object is your friend.

Lynn

Ah, I thought orlp had a specific encoding in mind. That would be really neat.

orlp

11:24 PM

well

FlipTack

Otherwise you can make some base class and have your custom types extent that if you wsnt

orlp

that is the follow up

ATaco

Object[] is a valid list construct, just use Integer instead of int

orlp

chat mega challenge

find an encoding that actually does it within 124 bits

ATaco

no

orlp

11:24 PM

@Lynn my mathematical solution is really easy to calculate actually

Lynn

I mean, you probably won’t do much better than “find the lexicographic index of your combination in the list of all combinations, and convert it to a 124-bit binary number”

orlp

f=lambda n,m:sum(log2(n+i) for i in range(m)) - log2(factorial(m))

@Lynn I think it should be possible to make a clever algorithm that does that but in an actual efficient manner

wait a sec, log2(factorial(m)) is inefficient

sum(log2(k+1) for k in range(m)) is the same, no?

so we can golf that to

f=lambda n,m:sum(log2(n+i) - log2(i+1) for i in range(m))

ATaco

Does f=lambda n,m:sum(log2((n+i)*(i+1))for i in range(m)) save a byte?

orlp

@ATaco im not really going for bytes here

ATaco

shrug

orlp

11:29 PM

also that * should be /, since I had a plus mixed up with a minus

@Lynn wolfram alpha has a closed form!

wolframalpha.com/input/…

ATaco

Well I can't edit it now

orlp

oh never mind

pochhammer symbol is that magic stuff

Lynn

Pochhammer isn’t very closed

orlp

yeah

@Lynn but this is what always amazes me

let's say you have a set of 10000 32-bit integers

naively that'd be 320000 bits

you can do it in 201542

ATaco

Okay, that's swell and all.

orlp

11:34 PM

that means you're spending nearly 1/3rd of your data on order!

ATaco

But how do you actually practically store this?

orlp

@ATaco well, that's the chat mega challenge

you can just list all combinations, pick the nth one, then store that number

which works

but isn't practically feasible except for really small collections and sizes

ATaco

I'm sure if it comes to the point in which I need to store an arbitrary order of integers of a non-particular size in as few bits as possible, I'll keep this in mind.

Downgoat

Question to Mac & Linux users: Do you have a gmp.h file? (probably should be in /usr/share/lib/)

orlp

@Downgoat apt-get install libgmp?

Downgoat

11:41 PM

no I mean without

orlp

what do you mean

Downgoat

Like if it comes bundled with OS

I think quartata said it did

orlp

it depends on your OS

I don't think it does though

Downgoat

:( Okay

OS X has :D

orlp

also that should be libgmp-dev

@Downgoat why do you ask

Downgoat

11:43 PM

GMP is dependency for cheddar. I was wondering if I needed to only needed to install it for windows systems

Quartata said to also always use system GMP is possible

I suppose I could use dynamic libs

orlp

@Downgoat windows most definitely does not have libgmp by default

on windows you always ship all your libraries

@Lynn I have an idea

store the first element normally

then store 0 to e where e was the last element

repeat until combination is stored

although this isn't exactly a working solution

since {0,0,0,0} only requires 32 bits to store

but {2^32-1,...} 128

so

'on average' it will be minimum, but doesn't always fit the minimum

George V. Williams

@orlp are you concerned with finding a number which corresponds to each multiset or simply a space-efficient data structure?

orlp

@GeorgeV.Williams those are in essence the same question

ultimately, I'm not concerned about anything

just curious

that being said I'm somewhat interested in an actual efficient encoding algorithm that can encode sets of unordered numbers without loss in the minimum required amount of bits

Combinatorial number system

In mathematics, and in particular in combinatorics, the combinatorial number system of degree k (for some positive integer k), also referred to as combinadics, is a correspondence between natural numbers (taken to include 0) N and k-combinations, represented as strictly decreasing sequences ck > ... > c2 > c1 ≥ 0. Since the latter are strings of numbers, one can view this as a kind of numeral system for representing N, although the main utility is representing a k-combination by N rather than the other way around. Distinct numbers correspond to distinct k-combinations, and produce them in l...

this is kind of interesting

George V. Williams

@orlp interesting problem.

orlp

I mean, there is a trivially correct and optimal algorithm