The Nineteenth Byte

6:12 PM

C++ Poll: If I do this:

template <typename T>
T foo(int blah);

template <>
bool foo(int blah) {
    ...
}
//Other specializations
//...

Then is it gross to leave the first function without an implementation?

moonheart08

..Not unless you need a general implementation

I'd still put some sort of "Programmer is a dummy" error message the generic outputs

caird coinheringaahing

CMP: What lack of a feature annoys you the most from a given language?

For me, Python not supporting partial application of functions

DJMcMayhem

@cairdcoinheringaahing Vimscript: Sane comparison operators

Recently? C++: yield

Anonymous

@cairdcoinheringaahing from functools import partial

caird coinheringaahing

@Mego Yeah, I know it can be done, it just looks horrible whenever I try it

moonheart08

6:20 PM

...i broke my graphics driver so bad my normal terminal (kitty) segfaults.

.-.

DJMcMayhem

Oh, also Python: Good regex (IMO import re doesn't count)

JS/Ruby/Perl build it in to the language features itself and have dedicated syntax for it. Python doesn't

Anonymous

@cairdcoinheringaahing Also github.com/kachayev/fn.py

moonheart08

either that or kitty broke during some recent update

Anonymous

@DJMcMayhem Python should have the same kind of string suffix stuff that C++ has, so you could do e.g. R"regex here" for a regex

Anonymous

It doesn't, but it should

DJMcMayhem

6:23 PM

Doesn't it have that for unicode strings?

Erik the Outgolfer

yeah, r-strings are pretty much useless for other purposes

moonheart08

@Mego you can't do R"stringyloo" in C++. Only "stringyloo"_R. the _ is manditory

DJMcMayhem

I don't remember exactly how encoding works in python, I just remember that it's a pain

caird coinheringaahing

Although, Python 3 always returning a generator from every iterable builtin is annoying

DJMcMayhem

@cairdcoinheringaahing It's way better than range returning a list

Anonymous

6:24 PM

@moonheart08 Yeah, but I want it to be a prefix for Python, like r"foo" for verbatim strings

DJMcMayhem

That used to annoy me, now I like it a lot

moonheart08

~~thats why i use C++. I mean Rust. I mean D. aaaaa no language has a good mix of functionality reeeee~~

Anonymous

@moonheart08 Haskell is perfection

moonheart08

i can't comprehend haskell :c

DJMcMayhem

@Mego You do C++, right? Do you have much experience with boost?

moonheart08

6:25 PM

((I'd be willing to try it again tho)

Anonymous

@DJMcMayhem A bit. Not a whole lot

DJMcMayhem

To C++ or to boost?

caird coinheringaahing

@Mego Haskell is just confusing. Not Prolog level confusing, but confusing nonetheless

moonheart08

@DJMcMayhem a few words: If you can, don't use boost. It likes to eat at your compiletime, and makes the code-build-debug-code cycle very unfun

Anonymous

@DJMcMayhem Python 3: all strings are unicode. You use s.encode() to encode them, and bs.decode() to decode them

Erik the Outgolfer

6:25 PM

@Mego I would prefer a language where I can code relentlessly

DJMcMayhem

@moonheart08 Oh trust me, I know. We use boost at work a lot, and the project I've been on for a year+ used to take 15 minutes to do a clean build

moonheart08

good lol

DJMcMayhem

Which isn't even that much in the grand scheme of things

moonheart08

boost is poison if you just try and use it for everything

DJMcMayhem

I became intimately acquainted with xkcd.com/303

moonheart08

6:28 PM

lol

I wish there was a C++ like language (Clean, and object oriented without shoving the entire thing in your face) but had a less convoluted template and std lol

but at the same time, not D, because D likes to shove the garbage collector (which you may not want to use) at you

DJMcMayhem

Isn't that what Rust is supposed to be? (disclaimer, I've never used Rust)

moonheart08

Rust isn't object oriented in a traditional sense, which kinda throws me off. (:c)

it's based on applying traits to structs. There is no direct upcasting, either.

or downcasting. whichever. i can't remember the diffrence

yea it's downcasting

you can upcast a struct to a trait it implements all day long

downcasting is useful when you're trying to say "ok, so this is an entity and it's a necromancer. I want to use the necromancer specific functions please" when you have the entity, not the necromancer

RTTI and objects is the only reason i still use C++.

Esolanging Fruit

6:58 PM

@moonheart08 You can (at least partially) do that with the Any trait, I believe. But it's a bit tricky.

Trait objects let you have open (i.e. extendable by the user) union functionality, but you generally can only use functions polymorphic on the trait.

In the case you mentioned, I'd use an enum, which allows type-safe matching but has the disadvantage of not being open

The reason open extension + downcasting isn't usually provided is because I get the feeling it's a bad idea most of the time.

For example, in Python you could write a function that asserts that isinstance(arg, list), and then iterates over it, but it's discouraged because somebody might, for example, put in an iterator.

orlp

@Lembik mathoverflow.net/questions/297155/…

that seems up your alley

on an unrelated note

I'm sad no one posts fastest-code or code-challenges anymore :(

been waiting to try out rust for a while now

but not really getting a chance on PPCG

moonheart08

I'd love to do an entry in a fastest-code, but they've been rather dead

I wonder how a challenge to have your program ""connect"" to IRC would work. IRC is a bit convolted, but such a challenge could be fun

Lembik

7:19 PM

@orlp I have posted one only recently!!

@orlp please see codegolf.stackexchange.com/questions/157049/…

and thanks for the MO link

@moonheart08 don't forget my challenges :)

Poke

10

Q: Make a simple IRC bot.

Task Make a simple IRC bot which does simple task like greeting user. Detail (You may see this RFC document.) Write a complete program that perform these: The program inputs nickname and realname from the user. All nickname and realname which form is [A-Za-z0-9]+ should be allowed, bu...

Lembik

what are the simplest rules for two intervals (x,y) intersecting?

so we have (a,b) and (c,d)

orlp

7:34 PM

@Lembik a >= c && a <= d || b >= c && b <= d

that's one way

Lembik

(6,7) intersects with (0,10)

let me see if that is covered

orlp

it is

Lembik

thanks!

orlp

that's the simplest conceptually

but I don't think it's simplest in actual operators

@Lembik also do edge points matter?

(0, 1) and (1, 2) do those intersect?

Lembik

so d <= a <= c || d>= b >= c

yes they do

orlp

7:37 PM

so you actually mean

[0, 1]

and [1, 2] :)

Lembik

yes.. they were tuples :)

not mathematical intervals

so I have a coding problem that is making my head hurt

I want do the following...

(warning...flood)

test_data = [(0, 10), (1, 100), (5, 21), (6, 6), (101, 150)]

def intersect(A, B):
if ((A[0] <= B[0] <= A[1]) or (B[0] <= A[0] <= B[1])):
return True
else:
return False

list = []
for pair in test_data:
row = []
for pair_compared in test_data:
if intersect(pair, pair_compared):
row.append(pair_compared)
list.append(row)

print list

the indentation has gone, sorry

orlp

c <= b && a <= d

that's simpler

Lembik

is that enough??

orlp

world.std.com/~swmcd/steven/tech/interval.html

Lembik

nice :)

let me try it

orlp

7:40 PM

also we have a < b and c < d always, right?

Lembik

yes

that's a nice improvement

but it's not the part hurting my head :)

my code is very inefficient as it compares pairs that could never intersect

how can I change it so it never does that?

test_data will eventually be very long

ngn

@Lembik why do so many people write "if x: return True; else return False" instead of just "return x" ...

orlp

@Lembik so if I understand correct

you have some large collection of intervals

and want to find all possible combinations that intersect?

Anonymous

@ngn More accurately, it should be return bool(x)

Lembik

@ngn I find it helpful to be explicit

@orlp basically yes.. I want a list of lists where each list contains all the pairs that intersect with a particular pair

orlp

7:47 PM

@Lembik please use interval

as a term

because pair is ambiguous here

Lembik

ok

maybe it should be a coding challenge :) ?

it does involve a little thought to get right I think

orlp

I mean you still didn't specify exactly what you want

Lembik

@orlp oh sorry what isn't clear still?

orlp

@Lembik describe what you want

using the term interval

instead of pair

you have a list of intervals

what do you want with them

ngn

@Lembik if you sort them first, you won't have to do so many comparisons

Lembik

7:54 PM

@ngn they are sorted already

@ngn [(0, 10), (1, 100), (5, 21), (6, 6), (101, 150)]

The problem with my code is, for example, that it checks if (101,150) intersects with (0,5) but by the time we get to looking at pair = (101,150) we already know that the pair before it in the sorted list is (6,6) so there was no need to make that comparison or any of the comparison to the pairs before (6,6) in the list.

this problem happens a lot making it much slower than it should be

ngn

@Lembik oh, ok, so why don't you break the second loop the moment they no longer intersect then?

Lembik

@ngn you have to start it in the right place too

ngn

@Lembik right

Lembik

@ngn so you need to start at the right place and break it at the right place

getting the right is making my head hurt :)

orlp

but please describe what you want first

precisely

Lembik

7:57 PM

@orlp I want exactly the output my code above gives

just faster

ngn

@Lembik something like for i in range(len(test_data)): for j in range(i, range(len(test_data)): if intersect(test_data[i], test_data[j]): do something; else break

Lembik

that could work.. what is the do something?

orlp

@Lembik pypi.python.org/pypi/intervaltree

don't reinvent the wheel :)

ngn

@Lembik whatever you have in the inner loop body: row.append(...); list.append(...)

Lembik

@orlp :) I am not sure we need a tree for this.. something like ngn's code should work

orlp

8:00 PM

@Lembik this is the simplest way to get good performance

you put all your intervals in the tree

and then query per interval what other intervals overlap with it

Lembik

thanks but how could it be faster than ngn's idea?

orlp

@Lembik because he compares every interval with every other interval

putting it in a tree you don't

Lembik

@orlp no I hope he doesn't

orlp

in the worst case (where everything intersects) you still have to

Lembik

hmm

let me try the interval tree

but I would like to get ngn's code to work too :)

@orlp hmm.. how do you actually add the pairs?
t = IntervalTree()
for pair in test_data:
t.add(pair)

that code doesn't work

if interval.is_null():
AttributeError: 'tuple' object has no attribute 'is_null'

Pavel

8:09 PM

CMC: find a use case for > /dev/stdin in a shell script

orlp

@Lembik read the documentation...

it's right where I linked you

pypi.python.org/pypi/intervaltree

ctrl+f examples

Lembik

I know but I don't understand how to add an interval!

it says tree.add(interval)

which is what I am doing

but then later it says Adding intervals - any object works!

>>> t[1:2] = "1-2"

orlp

>>> tree = intervaltree.IntervalTree()
>>> interval = intervaltree.Interval(2, 10)
>>> tree.add(interval)

@Lembik works just fine

Lembik

which I don't understand

oh you have to convert it to an interval first

let me see

orlp

@Lembik keep in mind that these intervals are half-open integers

so [6, 6) is empty

Lembik

8:15 PM

argh

ngn

@Pavel here's a use case: to win a CMC :)

orlp

you can add one to the end of each interval though

if all your intervals have integer boundaries

Lembik

the code is driving me crazy currently

ok something is working

now trying to work out how to find all the overlapping pairs

orlp

>>> from intervaltree import IntervalTree, Interval
>>> test_data = [(0, 10), (1, 100), (5, 21), (6, 6), (101, 150)]
>>> intervals = [Interval(start, stop + 1) for start, stop in test_data]
>>> for iv in intervals: tree.add(iv)
>>> for iv in intervals: print(iv, "overlaps with", tree[iv])
Interval(0, 11) overlaps with {Interval(6, 7), Interval(1, 100), Interval(1, 101), Interval(0, 11), Interval(0, 10), Interval(5, 21), Interval(5, 22)}
Interval(1, 101) overlaps with {Interval(6, 7), Interval(1, 100), Interval(1, 101), Interval(0, 11), Interval(0, 10), Interval(5, 21), Interval(5, 22)}

it's not that complicated

ngn

@Pavel if stdout is redirected or closed, /dev/stdin can act as a replacement for the original stdout?

orlp

8:19 PM

@Lembik do you see how easy this is with an interval tree already implemented for you :)

Pavel

@ngn For that you would use /dev/tty

Lembik

@orlp Thanks! Now I just need to make a sparse matrix out of the output :)

orlp

@Lembik but that's a different problem :(

that's why I asked what you needed

how big is N here?

Lembik

@orlp about 100,000

orlp

do you have a special sparse matrix data structure?

Lembik

8:27 PM

from scipy.sparse import coo_matrix ?

orlp

or will you simply set a 100,000x100,000 matrix to zeroes

Lembik

coo_matrix looks good for this

orlp

alright then you do have a sparse matrix data structure

Lembik

where each entry is the index of an interval in the original sorted list

orlp

I'm kinda curious

Lembik

8:28 PM

I want a sparse adjacency matrix in the end really

orlp

adjacency of what?

Lembik

each row is an element of the original list

orlp

also let me know how big the total number of overlaps are

Lembik

I suspect that it will have about 10 million non-zero entries in the end

orlp

@Lembik oh you mean just a boolean matrix

Lembik

8:29 PM

yes but sparse

orlp

where a_ij = overlaps(intervals[i], intervals[j])

Lembik

right

orlp

sparse is an implementation detail :)

Lembik

exactly that :)

orlp

eh I can recommend one little tip in that case

Lembik

8:30 PM

go on...

orlp

since you want to know the index of the interval in the original array

>>> test_data = [(0, 10), (1, 100), (5, 21), (6, 6), (101, 150)]
>>> tree = IntervalTree()
>>> for i, (start, stop) in enumerate(test_data): tree[start:stop+1] = i
>>> for i, (start, stop) in enumerate(test_data): print(tree[start:stop+1])
{Interval(1, 101, 1), Interval(0, 11, 0), Interval(6, 7, 3), Interval(5, 22, 2)}
{Interval(1, 101, 1), Interval(0, 11, 0), Interval(6, 7, 3), Interval(5, 22, 2)}
{Interval(1, 101, 1), Interval(0, 11, 0), Interval(6, 7, 3), Interval(5, 22, 2)}
{Interval(6, 7, 3), Interval(1, 101, 1), Interval(0, 11, 0), Interval(5, 22, 2)}

you can store extra data with the interval

in your case it's very useful to store the original index i

H.PWiz

@Lynn I don't think Haskell has been updated on anagolf

Lembik

@orlp interesting

so it should be pretty simple now I think with that trick @orlp

orlp

@Lembik once you have the Interval from the query

just iv.data gives you back the original index

Lembik

so this looks good now

orlp

8:36 PM

>>> test_data = [(0, 10), (1, 100), (5, 21), (6, 6), (101, 150)]
>>> M = [[0 for _ in test_data] for _ in test_data] # matrix
>>> tree = IntervalTree()
>>> for i, (start, stop) in enumerate(test_data): tree[start:stop+1] = i
>>> for i, (start, stop) in enumerate(test_data):
...     for iv in tree[start:stop+1]:
...         j = iv.data
...         M[i][j] = 1
>>> M
[[1, 1, 1, 1, 0], [1, 1, 1, 1, 0], [1, 1, 1, 1, 0], [1, 1, 1, 1, 0], [0, 0, 0, 0, 1]]

@Lembik obviously you'd replace M with your sparse matrix

Lembik

very nice!

I am intrigued to see how fast the IntervalTree is in reality

orlp

then try it :)

it very much depends on how many 1s are in your output

Lembik

I will! I don't have the real data here

thanks so much.. this has been a lot of fun

orlp

@Lembik why do you want this matrix anyway?

Lembik

@orlp it's so that I can process a large data set more efficiently

the rows help me cut down a search space

orlp

8:39 PM

doing what exactly?

because that's the beauty of an interval tree

once you've built it

queries are quick

yes!

I have a hunch

go on? :)

that instead of that adjacency matrix you can use the interval tree directly

Lembik

(I have to go in a moment)

oh! that might work

thanks for all this.. bye for now

New Sandboxed Posts

8:55 PM

0

A: Sandbox for Proposed Challenges

Intron Adder Quine code-golf quine In the context of quines, an intron is a part of a quine that serves no purpose in producing output, but is still included in the data section. For example: function quine() { const data = "function quine() {\n const data=\"@\";\n // Arr! This be ...

Pheo

@totallyhuman how is your language going? Also, I recommend basing it off of another language, such as downloading the source code for python 3.6 and modifying some stuff.

mbomb007

9:10 PM

Welcome to WorldDestroying.SE

39

Q: How to completely burn down a city, without leaving clues for humanity 4,000 years later?

Background I want to burn down a city completely. Nothing must remain, ashes to ashes, dust to dust. Even though I'm a supernatural being, I want this to happen in a natural way. I also want the destruction to not leave any traces that can be used by humanity 4,000 years later to identify what e...

reality-check cities weapon-mass-destruction ancient-history natural-disasters

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

Date Multiplying Challenge (Inspired by this week's riddler on FiveThirtyEight.com) Given a year between 2001 and 2099, calculate and return the number of days during that calendar year where dd * mm = yy (where yy is the 2-digit year). 2018, for example, has 5 days: 1/18/18, 2/9/18, 3/6/18, ...

DevelopingDeveloper

9:24 PM

Woohoo!! @DJMcMayhem codegolf.stackexchange.com/help/badges/81/steward

DJMcMayhem

:D

Neil

@DJMcMayhem Why do you even need the first function?

DJMcMayhem

I thought it was necessary. I guess I could be wrong though

@Neil msdn.microsoft.com/en-us/library/k568kf16.aspx

orlp

9:40 PM

@user56656 do you have a bunch of test cases for what you call intersection? (I'm calling it schema deduction atm :P)

caird coinheringaahing

@mbomb007 I totally disagree with the premise of that question. Half the fun of destroying a city is people knowing that it was you :D

user56656

@orlp Sorry I don't.

I should make some though

Zacharý

11:20 PM

I found the weirdest probability distribution ever ...

Neil

@DJMcMayhem for the last example on that page, if you really want an overload with a const char* argument, then just overload it: CF(const char* p) {}. No template <> necessary.

Zacharý

1/x^2 on [1,infty).

Pavel

What's odd about it

Zacharý

Unless I'm mistaken: the mean, standard deviation, skewness, and kurtosis are all infinite.

Pavel

I'm pretty sure the mean is indeterminate

Zacharý

11:27 PM

I'm pretty sure it's infinity, as the integral diverges towards infinity.

Pavel

Since the entire distribution falls between 1 and 0, it certaintly can't be infinite.

Zacharý

wut

Pavel

> [1,infty)

Zacharý

The pdf of the distribution being 1/x^2

That being the probability density.

I meant to say x on [1,infty)

Pavel

I'm starting to suspect that AP Statistics didn't actually teach me anything

Zacharý

11:30 PM

I'm just looking into it on my own time

Pavel

Oh nevermind I just misunderstood

Zacharý

"Algebra-based X" is equivalent to saying "Watered down X. in fact so watered down X: it's basically water"

DJMcMayhem

@Neil I get errors in my code if I remove the standard template

I could post a snippet of it later if you're interested

Pavel

Templates work in mysterious ways

Neil

minimal test case, yes?

Zacharý

11:36 PM

Would the standard deviation of 1/x^2 be undefined?

Or would it be infinite?

Leaky Nun

@Zacharý if the mean is infinite, whence standard deviation (from the mean)?

Zacharý

@LeakyNun So, it would be infinite?

Leaky Nun

i would rather leave it undefined

Zacharý

I like it. It's so bizarre of a probability distribution.

I learned about infinite parameters when examining t-distribution w/ degrees of freedom being 2 or 1.

ngn

@Zacharý how can one pick a (uniformly distributed?) random number from an infinite interval?

Zacharý

11:45 PM

@ngn The probability density function is p(x)=1/x^2, for all x>=1, and 0 for all x<1.

ngn

@Zacharý that way it makes sense

DJMcMayhem

@Neil Try it online!

Zacharý

I didn't know how to describe it, okay?

DJMcMayhem

I'm doing it in Visual C++, I don't know if the compiler makes a difference

Pavel

Well, Visual C++ is dumb

Neil

11:48 PM

@DJMcMayhem afaik there's no reason to make it a template function, just drop the template <> like I said earlier

ngn

@Zacharý my fault, I didn't realise 1/x^2 is density

Zacharý

mu=sigma=skewness=kappa=infinity... man that's weird

DJMcMayhem

@Neil Well, it does need to be a template because Try it online! is ambiguous

But Try it online! is not

Neil

@DJMcMayhem ah, well personally I'd think that's an odd way of choosing which function you want

DJMcMayhem

How would you do it? I do need them to have the same name/arguments

Leaky Nun

11:54 PM

@Zacharý is it the inverse of the uniform distribution on (0,1]?

by inverse i mean reciprocal

Zacharý

Yes, actually, I think it is/

Leaky Nun

then it's weird

21

A: What is the new probability density function by generating a random number by taking the reciprocal of a uniformly random number between 0 and 1?

Let the old probability density function be $f_1(x)$, and the new one be $f_2(x)$. We have:$$ \int_1^af_2(x)\mathrm dx=\int_\frac1a^1f_1(x)\mathrm dx $$where $a>1$. We also know that $f_1(x)$ is uniform, and spans from $0$ to $1$. Therefore, $f_1(x)=1$ in that interval. Therefore:$$ \int_1^af_...