algos-and-data-structs

[elder sand]

Lol I never really asked that but I’ve never seen a tree with more than one component

[brave oak]

I mean

then it's two trees

right

[onyx root]

@elder sand i like the general "think about it" questions.

[elder sand]

Isn’t this a think about it question?

[knotty magnet]

a forest, i think

[onyx root]

but i'd still rather ask about things they have made.

[elder sand]

Or is it too obvious

[onyx root]

yes, that's what i meant.

[brave oak]

it'd be really sad if two trees made a forest

environmentally dystopian future

😔

[elder sand]

Lol, how many grains of rice makes a pile

Just one?

[knotty magnet]

i think a forest is an acyclic undirected graph, so technically two trees would make a forest

[brave oak]

then one tree would be a forest too?

[elder sand]

I’m not sure if more than one component is a graph either

[brave oak]

why wouldn't it be

[elder sand]

Like multiple graphs

Like is a graph/tree defined as being a singular component

[brave oak]

I think they're called subgraphs?

[runic tinsel]

The conversation was about why interviews that consist of standard algorithm implementations should be boycotted

[elder sand]

Noooo

[runic tinsel]

And I don;t understand why would you care

[brave oak]

because it's something you can Google?

[elder sand]

I enjoy those questions lol

[brave oak]

I don't even know

which is preorder traversal

[elder sand]

Those tend to make fun interviews

[brave oak]

like I know it depends on which side you visit first

but I always get preorder/postorder mixed up

[elder sand]

Yeah the terminology there is weird

[brave oak]

I also mix up type I/type II errors

I THINK type I is false negative?

[elder sand]

Wtf is that lol

Oh

[onyx root]

tell us what is fun about them

[brave oak]

data science/statistics

one is false negative and one is false positive

but I'm not sure which

[elder sand]

Uhhhhh, that’s like asking “what’s fun about eating ice cream”. They’re usually challenging

[runic tinsel]

because it takes time to study apparently

[brave oak]

so are trying to use higher-kinded types in Kotlin

😔

[elder sand]

Eating ice cream isn’t challenging lol, originally meant it as “I’m just kinda wired liking them”

[brave oak]

man after trying like 4-5 different languages

I realise

Django is really good

okay off topic sorry

[elder sand]

I don’t care much for Django personally , but we all have our opinions

[lucid pivot]

I thought this was a python server

[knotty magnet]

🤔 maybe, but i guess it's implied that there's more than 1 tree

[brave oak]

it is

[brave oak]

if you want to imply that then "not fully connected" would be necessary?

not sure what the proper terminology is I don't have a math background

[knotty magnet]

or "disjoint union of trees" 🎉

[elder sand]

People get kinda hung up on what is and isn’t good interview questions.
It feels like trying to optimize for the ideal discussion for making friends

[brave oak]

kind of a different case, don't you think

friendship is pretty personal

[knotty magnet]

from wikipedia, lol

As special cases, the order-zero graph (a forest consisting of zero trees), a single tree, and an edgeless graph, are examples of forests.

[elder sand]

The terminology isn’t important either, unless it’s strictly part of the job

[brave oak]

but, at least when we're talking about technical assessments

I think there are clear principles to follow

[elder sand]

Yeah, I just mean you can get a good sense of the person from asking a wide variety of questions

Good distinction to make though

[elder sand]

it sounds like "forest" is similar to the idea of "components"

but anyway, I'm personally kind of bummed when I hear interviewers and interviewees with bad takes about whiteboarding style questions

I don't think they're meant to be some kind of gotcha, and if you're turned down from a place on account of some gotcha, you dodged a bullet lol

I have way way more to say about it, but its probably better not to haha

I would never fault someone for not knowing the name of a specific specialty algorithm or data structure.
But, there are levels that I categorize certain concepts like lists/dicts/sets, big O, etc

in terms of where you are skill-wise

[vague python]

hey
i have a doubt
is there any difference in identity operators while we use it in different enviroment
because it shows diffrent reasult in pycharm and different in jupiter
i am talking about Python

[ivory yacht]

Do you mean in regards to using it with immutable literals? Because you shouldn't do that, it just exposes exactly what optimisations the specific interpreter you're using happens to do.

Depending on how the code is executed, which version, etc you could get different results.

Regular equality will instead give you the correct results.

[vague python]

righnow i am using 3.9 ver

should i send ss of my command

it is showing me true

but it should give me false

[deft locust]

yeah, that's string interning

it's different in REPL and script mode

and it's implementation specific

[vague python]

but its showing their ID same

[jolly mortar]

yes, because its using the same string object for both

its an implementation detail you shouldn't have to worry about

[vague python]

oh thank you

[austere sparrow]

Generally, you should never be using is.

(except when comparing directly to singletons like None, True, False etc.)

[lean dome]

The interpreter sometimes, when it's able to and knows it won't change the behavior of your program, cheats and reuses an existing object instead of creating a new one. It can only do that for immutable objects, because it knows that if two immutable objects are equal, they will always be equal, and nothing can ever happen that would make them become unequal, so everyone can share the same instance of the object without changing the meaning of the program

This is an optimization to save time and memory, but this optimization means that using is on an immutable type like a string or a tuple will sometimes give you weird results that don't match what you would see if you repeated the experiment with a mutable type like a list

[manic oasis]

I would like to soundboard a project if someone has time/opinions.
I want to take a goal input of N elements (ex: ['a', 'b', 'c']) and work backwards with elements to model inheritance (like punnett square style stuff). I'm guessing a tree would make sense?
But I'm not sure if there's a good way to visualize a tree in Jupyter or similar. 🤔

oh anytree looks pretty perfect

[keen hearth]

Probably a better fit for #data-science-and-ml

[analog siren]

with regex what would be the best way of checking if an opening " is the same as the closing and not '?

[keen hearth]

You could use a group and a back-reference.

('|") ... \1

[analog siren]

ah thanks

[main atlas]

Can anyone help with minimax in #help-coconut

[old heron]

What do you guys think about this class I wrote?

from types import SimpleNamespace

class NameDict(SimpleNamespace):
    def __init__(self, **kwargs):
        self.__dict__.update(kwargs)
    
    def __getitem__(self, key):
        return self.__dict__[key]
    
    def __setitem__(self, key, value):
        self.__dict__[key] = value
        
    def __delitem__(self, key):
        del self.__dict__[key]

    def __iter__(self):
        return iter(self.__dict__)

    __len__ = lambda self: len(self.__dict__)

    items = lambda self: self.__dict__.items()
    keys = lambda self: self.__dict__.keys()
    values = lambda self: self.__dict__.values()

It's a SimpleNamespace which can be also accessed/iterated like a dict

Or a dict where you can access values as myDict.key

[old wing]

I am absolutely new to Python and "Algos and Data Structures". Where should I be starting and how?

[old heron]

watch some youtube tutorial for beginners

[carmine cloak]

I have a question that I have more command on dsa with python than C++, Sud I still do dsa with C++ or python for product based company preparation?

[fiery cosmos]

Seems like it'd be easier to just subclass collections.UserDict and override dunder getattr

[old heron]

How would I override getattr to give me direct access to the attributes? @fiery cosmos

[fiery cosmos]

python doesn't have sorted lists/sets, unlike c++. Any idea what can be a workaround?

[austere sparrow]

Is this what you might want? http://www.grantjenks.com/docs/sortedcontainers/

[fiery cosmos]

I know that thing, but nothing out of the box in python.. that makes me sad

I wanted to do competitive programming using python, but now it seems I will not be able to use python for solving all types of problems

[keen hearth]

You mean trees?

[fiery cosmos]

I was referring to something equivalent to c++ set

[keen hearth]

Yeah, I think that's a binary search tree (I'm not a C++ programmer). It's one thing that's strangely absent from the python Python standard library.

[austere sparrow]

Technically the standard library has it (or something like it, I think a b-tree) inside of SQLite

but that would be very silly to use

[keen hearth]

Oh interesting 😄

[knotty magnet]

there is heapq

[fiery cosmos]

heapq is not "sorted" as such

you cannot iterate over elements in a heapq in a sorted fashion after adding some elements in it without sorting it

what I mean is, it doesn't maintain a sorted ordering

one way using heapq would be to heappop items and store them in a auxiliary container, and then add them all back with heappush

but that seems costly, isn't it?

that's at O(NLogN)

as opposed to this, c++ set can do insert and remove in O(logN), no?

[brave oak]

there isn't one in the stdlib

[brave oak]

yes

AFAIK

C++ set generally uses some sort of tree

whereas Python's set is a hash set

[analog siren]

So im using this regex statement to check if ! is in some of quotes, but it doesnt seem to work?
It worked fine on the regex tester.

ah wait nvm

needed to use search instead

[fiery cosmos]

!d object.getattr ```py
In [9]: class Attribute(c.UserDict):
...: def getattr(self, key):
...: try:
...: return self[key]
...: except KeyError:
...: raise AttributeError from None
...:

In [10]: d = Attribute(a=2, b=3)

In [12]: d.a, d['a']
Out[12]: (2, 2)

[halcyon plank]

object.\_\_getattr\_\_

object.__getattr__(self, name)```
Called when the default attribute access fails with an [`AttributeError`](https://docs.python.org/3/library/exceptions.html#AttributeError "AttributeError") (either [`__getattribute__()`](https://docs.python.org/3/reference/datamodel.html#object.__getattribute__ "object.__getattribute__") raises an [`AttributeError`](https://docs.python.org/3/library/exceptions.html#AttributeError "AttributeError") because *name* is not an instance attribute or an attribute in the class tree for `self`; or [`__get__()`](https://docs.python.org/3/reference/datamodel.html#object.__get__ "object.__get__") of a *name* property raises [`AttributeError`](https://docs.python.org/3/library/exceptions.html#AttributeError "AttributeError")). This method should either return the (computed) attribute value or raise an [`AttributeError`](https://docs.python.org/3/library/exceptions.html#AttributeError "AttributeError") exception.

[old rover]

i'm very confused by something

this is how I was taught... that the data in a min heap is stored within an array

and that you have to do a bit of simple math to get the parent, left, and right child

but then

wow i must have been burnt outttt

you get the left child by multiplying the index by 2 and adding 1

i could have sworn I saw this:https://runestone.academy/runestone/books/published/pythonds3/index.html say that you just multiply by 2 to get the left child

must have been tired

[knotty magnet]

it depends if the array is 0-indexed or not

[old rover]

ohhh

[dense forge]

anyone knows the difference between getattr and getattribute ?

[old rover]

ok well then that clears it up

def _perc_up(self, cur_idx):
    while (cur_idx - 1) // 2 >= 0:
        parent_idx = (cur_idx - 1) // 2
        if self._heap[cur_idx] < self._heap[parent_idx]:
            self._heap[cur_idx], self._heap[parent_idx] = (
                self._heap[parent_idx],
                self._heap[cur_idx],
            )
        cur_idx = parent_idx

while (cur_idx -1) //2 = 0

but you get the parent index by subtracting two

and then dividing it by two

oh is it bc of integer division?

it's not bc the array isn't zero indexed... the array on their website starts from zero

what is the reason to overcomplicate this shit?

stick with the formuoli

[jolly mortar]

__getattr__ is only called if normal attribute lookup fails

__getattribute__ is always called

[knotty magnet]

it subtracts 1

and it is because it is 0-indexed

[old rover]

so is gayle's array

0-indexed

it's bc of the integer division they use in the Runestone thing

they subtract by 1 so they intentionally use integer division to get rid of that decimal

[old rover]

def get_min_child(self, parent_idx):
    if 2 * parent_idx + 2 > len(self.heap) - 1:
      return 2 * parent_idx + 1

if the index of the right child

is bigger than the length of the list - 1

return the left child??

how does comparing the index of the right child to the length of the list minus one do anything?

[old rover]

well if the right child's index wasn't bigger than the length of the heap - 1... you wouldn't have a heap?

is that right?

what is that int [] items = new int(capacity) line?

an array of ints?

[knotty magnet]

yes, with length capacity

[old rover]

oh python didn't like it

[old rover]

this is just bc the list is 0-indexed

so you have to subtract 1

smort

i like how it took me maybe 3 hours to realize that

but it's all starting to click now

i need to get a walk in... need some fresh air

[lean junco]

is i have a BST and root node is r

and i do temp = r

the temp usage is limited of using temp, temp.right and temp.left........am i right?

can we do temp.right.right as well? expecting r.right.right?

[rugged swan]

What the growth functions?

Or big o notation

[fiery cosmos]

What do you think? Try multiplying the worst case sizes you might get out of each of the for loops.

[rugged swan]

I need answers

I try but wrong

[fervent saddle]

I guess it’s because j could be anything

So it’s one of those O(n * m) types of complexities

Or maybe they want you to consider j as a constant

[austere sparrow]

if all elements of values2 are bounded by X, then the complexity is O(N^2 * X)

[fervent saddle]

j must always be less than the length of the list, otherwise the 3rd and 4th to last lines wouldn’t work

I wonder why it’s not O(n^3) if j is some random number between 0 and the length of the list

[knotty magnet]

it's java syntax

[austere sparrow]

Why?

oh, right

then it's O(N^3)

[fervent saddle]

He said that’s wrong

Which is weird

[fiery cosmos]

That is weird

[stable pecan]

the third loop isn't dependent on the length of the input, but bounded by the max value in the input

but since values[k] exists

i guess it is bounded by the length of the input

[fiery cosmos]

yeah, k ends up as j like meso said

so it works out to O(N^3)

unless values2 is a dictionary

[stable pecan]

if the numbers in values are bounded (perhaps stated earlier) then the last loop is constant time

[fiery cosmos]

yeah, there might be spec missing about values

[cosmic geode]

I'm having some issues ray tracing quadtrees
Sometimes it just skips nodes and tests positive for objects behind the first one to be intersected, and I have no idea how to troubleshoot it
I haven't been able to find a pattern. sometimes just aiming the ray a few pixels to the other side will make the difference.
I've tried drawing the graph and logging the traversal, but it was a bit like searching for a needle in a haystack

any suggestions? What are some tests I could make, or properties to track that could help narrow down the cause?

[dapper sapphire]

When we are trying to add a value to a set(), does a hash get generated for that value?

[brave oak]

yes

if it can be

otherwise you get an error

[dapper sapphire]

ok makes sense.

thanks!

Does DP always include recursion?

Or can we have DP with iteration(for/while) loop?

[plush owl]

How to visualise a binary tree? I'm aware of the level order traversal and printing. Would prefer a graphical format

[cosmic geode]

I really like networkx/graphviz for that sort of thing

here's a graph for a quadtree from the project I'm currently working on
it's basically the same concept, except you have 4 child nodes on each level

@plush owl

[plush owl]

Thanks, will try it out 🙂

[cosmic geode]

np. feel free to ping me if you run into any issues

[fiery cosmos]

It can be iterative. Recursion uses the call stack but you can use your own stack that you push and pop to.

[cosmic geode]

recently I had to traverse a graph from a shader, and GPUs don't do well with recursion. To avoid the call stack i baked the traversal into the data structure instead.
Basically, just let each node have an "entry" and an "exit" pointer which tells you where the next step in the traversal is

granted, this was a pretty simple algorithm. this approach could be tricky for more complex graphs or traversal patterns

anyway, that's also a way to do iterative traversal

[jolly mortar]

it's often easier to think of a top-down recursive solution first, and then convert that to a bottom-up iterative solution

[normal inlet]

are the append method and insert(-1) both O(1)

or does insert(-1) have a runtime of O(n)

[runic tinsel]

both 1

although they don;t give the same result

still both O(1)

[normal inlet]

oh ok

[normal inlet]

https://media.discordapp.net/attachments/725925581610418236/869078464551063573/Screen_Shot_2021-07-26_at_12.47.10_AM.png

for this one is it a. bubble sort b. selection sort and c. insertion sort?

[fiery cosmos]

can someone pl explain longest path in dag

[keen hearth]

What aspect are you having trouble with?

[rugged swan]

I need answers this

Please

[desert mirage]

Why not listen to your algorithms class and answer it yourself?

[rugged swan]

I order this but i don't know wrong or right

[keen hearth]

This seems like it's a homework exercise. Do you feel you don't understand asymptotic growth well enough to answer it?

[rugged swan]

This my order

Right or no?

[normal inlet]

i think from lowest to highest its
2^10 -> 4n -> 3n + 100logn -> nlogn -> 4nlogn + 2n -> n^2 + 10n -> n^3 -> 2^logn -> 2^n

[old rover]

 def __perc__up(self, cur_idx):
    while (cur_idx - 2)/2 == 0:
      parent_idx = (cur_idx - 2)/2
      if self.heap[cur_idx] < self.heap[parent_idx]:
        self.heap[cur_idx], self.heap[parent_idx] = (self.heap[parent_idx], self.heap[cur_idx])
      cur_idx = parent_idx

is the parent index now the current index... bc they're swapped?

i think so

i'm also slightly confused about something else

def insert(self, item):
    self.heap.append(item)
    self.perc_up(len(self.heap)-1)

here 1 is subtracted from the length of the list

bc it's 0 indexed

 def perc_down(self, cur_idx):
    while (2 * cur_idx + 2) < len(self.heap):
      min_child_idx = self.get_min_child(cur_idx)
      if self.heap[cur_idx] > self.heap[min_child_idx]:
        self.heap[cur_idx], self.heap[min_child_idx] = (self.heap[min_child_idx], self.heap[cur_idx])
      else:
        return 
      cur_idx = min_child_idx #what does this line do?

but here it isn't?

is it bc i'm comparing indexes? so it has to be len(self.heap)?

[old rover]

also about this... while the index of the right child is less than the length of the heap.... would there ever be a scenario where it was greater than the length of the heap?... is it just the heap not existing?

[keen hearth]

Think about 2^10. How does this grow as n grows?

Also, consider the order of 3n + 100 log n relative to n log n.

[old rover]

i'm gonna watch the author's videos

didn't know they existedddddd

[keen hearth]

2 ^ log n is kind of an interesting one. Try simplifying this.

(Does it depend on the base of the logarithm?)

[keen hearth]

Oh, what videos are those?

[old rover]

https://youtu.be/GXq4sV-eo3g

this is the guy who wrote Problem Solving with Algorithms and Data Structures using Python

https://runestone.academy/runestone/books/published/pythonds3/index.html the one I got pinned a long time ago

[austere sparrow]

2^(logn), 4n and 3n + 100logn are on the same order

[old rover]

maybe if i carefully watch his videos I'll understand his code

[austere sparrow]

Actually... it depends on what they mean by log n -- log10, log2 or ln

[old rover]

i find this funny

his book and his video both use different code

at least I finally understand why the heap_list is [0]

nope

nope

now his videos are making me more confused

i don't trust someone whose code is different from the book they wrote

as far as i'm concerned i'm done with heaps

i like how he uses temporary variables like you would in java to switch things around.... and doesn't do that in his book

[old rover]

class Vertex:
    def __init__(self,key):
        self.id = key
        self.connectedTo = {}

i'm confused by this

what is key?

data?

fuck it i am done for today

[dapper sapphire]

Oh actually yeah we can create our own call stack, just keep pushing it to build the stack, and then work backwards and pop element each time.

I never thought about this, until you mentioned it. Thanks!

[austere sparrow]

yeah, that's how "stackless" imlpementation of languages work

[frozen knoll]

i need some help, def sort_array(source_array): splited_array = list(map(int, ''.join([i for i in source_array.split(',')]).split())) # create clear list with integer elemenets odd_array = sorted([i for i in splited_array if i % 2 != 0]) # extract odd numbers for index, item in enumerate(splited_array): #try to insert in splited_array <- problem start here if item in odd_array: splited_array[index] = odd_array.pop[index] <- here its problem in console return splited_array
, problem is 'builtin_function_or_method' object is not subscriptable

[austere sparrow]

It's old_array.pop(), not old_array.pop[]

[frozen knoll]

ahh, thanks, but i have more problems, if i enter 5, 3, 2, 8, 1, 4, he give me 1, 3, 2, 8, 1, 4 but correct is 1, 3, 2, 8, 5, 4

instead of 5 he puts me 1

[little night]

anyone else having an issue with aiohttp ?... it's stopped working for me All data i try and read from my server just returns None.

[austere sparrow]

You shouldn't mutate a list while you're iterating over it
https://docs.python.org/3/reference/compound_stmts.html#the-for-statement

There is a subtlety when the sequence is being modified by the loop (this can only occur for mutable sequences, e.g. lists). An internal counter is used to keep track of which item is used next, and this is incremented on each iteration. When this counter has reached the length of the sequence the loop terminates. This means that if the suite deletes the current (or a previous) item from the sequence, the next item will be skipped (since it gets the index of the current item which has already been treated). Likewise, if the suite inserts an item in the sequence before the current item, the current item will be treated again the next time through the loop. This can lead to nasty bugs that can be avoided by making a temporary copy using a slice of the whole sequence, e.g.,

for x in a[:]:
    if x < 0: a.remove(x)

[normal inlet]

how do i find what the space complexity is of a program

https://images-ext-2.discordapp.net/external/7CLLWsm8ecTZyK5dbv2qkdho0xrujTqllCMdHfmFAFo/https/media.discordapp.net/attachments/725925581610418236/869078464551063573/Screen_Shot_2021-07-26_at_12.47.10_AM.png?width=1210&height=1316

like for example this question

[tender jungle]

I think b

@normal inlet

[normal inlet]

no i meant how do i find the space complexity for each of these programs

the extra space usage

[tender jungle]

Oh kk

I'll do a research

[austere sparrow]

Are you familiar in general what space complexity is?

[normal inlet]

all i know is that it uses the same notation as runtime

and that its basically just extra RAM that a program needs to run (i think)

[shut breach]

yeah your program needs a certain amount of memory

the space complexity class describes how much your memory requirement grows relative to the size of the input to your algorithm

[normal inlet]

i did some research online and it seems space complexity comes down to variable types from what im seeing https://www.youtube.com/watch?v=_F29n4Z69rE

like if theres only ints that u create then its o(1) space but if theres stuff like strings or lists then its o(n) space

[shut breach]

that is not true

it's about how much information you're storing at any one time as a function of the size of the input

[fiery cosmos]

It's true in the sense that ints are bounded (in most languages, not Python technically) - they will always be 64 bits or whatever each. Strings and lists can contain an arbitrary number of chars or items so they are O(N) where N is their length.

But if you know your strings are below a certain length then they become constant memory. So the type isn't exactly important.

[fervent saddle]

There’s also sometimes some unbounded thing that you just ignore in the algorithm. Like if you’re looking at the space complexity of some algorithms that sort an array, you’ll probably ignore the array’s size when trying to find the algorithms’ space complexity

[lean dome]

The question that space complexity analysis for an algorithm answers is "how does the amount of space needed by the algorithm change as the input grows larger?". The size of the input itself isn't counted in that, because that's not part of the space usage of the algorithm.

that is, if someone said that the space complexity of py def find_max(arr): the_max = arr[0] for elem in arr: if elem > the_max: the_max = elem return the_max was O(N) instead of O(1), they would just be wrong. It's not that you sometimes ignore things, it's that you look at the space usage required by the algorithm, not the space usage required by the inputs to the algorithm.

[fervent saddle]

Yeah, that wasn’t the right way to phrase it

[normal inlet]

def method1(lst):
n = len(lst)
total = 0
for i in range(n):
for j in range(1+i):
if i+j in lst:
total += lst[j]
return total

is this runtime O(n) or O(n^2)

[austere sparrow]

@normal inlet What do you think and why?

[normal inlet]

i think its O(n) but someone else is telling me O(n^2)

oh btw thats supposed to be nested lemme fix that

there we go

[austere sparrow]

for i in range(N):
    for j in range(N):
        print("hail satan")

How many times will this print hail satan? @normal inlet

[jovial cairn]

depends on what n is i think

[austere sparrow]

right, so how does it depend on N?

[jovial cairn]

because thats a loop and the range is n as it says in the brackets

[normal inlet]

well thats n^2

o(n^2)*

[austere sparrow]

well, it will print it exactly N^2 times

for i in range(N):
    for j in range(i + 1):
        print("hail satan")
``` And how many times will this print?

[normal inlet]

N?

[austere sparrow]

Or, differently, how many asterisks will this print?

for i in range(N):
    print("*" * (i + 1))

[normal inlet]

uh

[austere sparrow]

certainly not N times, there's a loop inside of it

[normal inlet]

oh wait i think i get it

[fervent saddle]

Won’t that potentially have an index error?
Nvm, no it won’t

[normal inlet]

that i+1 goes to N as i is iterating to N

i think

idk if thats how to explain it

so that acts as a range(N)

[austere sparrow]

You'll know how to find the answer if you find an answer to this

How many asterisks will it print if N is 5, for example?

[normal inlet]

6+ 5 + 4 + 3 + 2 + 1

21?

[austere sparrow]

right

So for any N, the number of asterisks will be 1 + 2 + 3 + ... + N

what's the sum of that series?

[normal inlet]

lemme check

O(N^2)

?

[austere sparrow]

try to figure out on your own 🙂

The sum isn't O(N^2), it's some exact number (depending on N)

[normal inlet]

n(n+1) / 2

?

[austere sparrow]

yes

[fiery cosmos]

ñ

[normal inlet]

o ok

[fiery cosmos]

ñ

ñ

[austere sparrow]

so yes, the complexity of that is O(N^2)

[normal inlet]

ah ok i get it now

thank you

[fervent saddle]

Those are both wrong for that program, it’s O(n^3)

[austere sparrow]

hm?

why?

[fervent saddle]

Outer loop + inner loop + checking inclusion in list

[austere sparrow]

oh, right

@normal inlet When you're doing in on a list, it potentially has to traverse the entire list

(there's no way to find out if there's any given element in the list)

[normal inlet]

oh

[fiery cosmos]

Though you could make it O(N^2) pretty easily by making a set from the list at the top and checking containment in that. x in someset is O(1) on average

[quasi lichen]

Can anyone tell me resources for the ds and algo

[knotty magnet]

📌

[austere sparrow]

well, there's an O(N) solution to the problem 😉

wait, is there?

[knotty magnet]

what is that function even doing

[fiery cosmos]

I wanna say I think so

[jolly mortar]

what's the problem

[raven geode]

what would the time complexity of this be:

def sample(n):
sum = 1
if (n % 2 == 0):
for i in range(n):
sum += 1

else:
    for j in range(n * int(n**0.5)):
        sum *= 2

return sum

y'all i need help, penn is trying to screw me over !

[knotty magnet]

william penn?

@raven geode do you have any guesses?

[fervent saddle]

I think for things like that, it’s just the complexity of the worse possibility

The else block in this case

[austere sparrow]

without any bounds on n (well, assuming it's an int! we're in Python sigh), yes, it's O(n * sqrt(n))

[raven geode]

yeah thats what i was thinking!!!

[jolly mortar]

n*(sqrt(n)..?

[austere sparrow]

yes, sorry

[raven geode]

O (n^(3/2) )

or can we say theta (n^(3/2))

[fervent saddle]

If the else block was entered only a 3rd of the time, would that make it so the average complexity was O(n)? Or is that not how that works?

[fervent saddle]

I think theta isn’t supposed to be used if the best case and worst case aren’t the same

[raven geode]

yeah we always talk about worst case complexity rather than average case because it's hard to calculate it

[fervent saddle]

The best case there is O(n)

[austere sparrow]

Big Theta is what's usually meant by O colloquially, I think

Actually, I don't think there exists a big theta for this, because when divided by n^(3/2), it doesn't have a limit

[raven geode]

interesting so its going to be O(n^(3/2))

[austere sparrow]

if you want to be pedantic, it's O(n * sqrt(n) * n^log2(3)) at least on CPython 😛

because multiplying integers isn't O(1) when they are arbitrarily large

and this will be easy to see if you give the function a 10000-long list

[raven geode]

oh thank you so much !!!

[austere sparrow]

actually, not exactly that, because it's multiplying two numbers of different size

[vocal gorge]

(2^log2(3))
that's just 3

and 3^n is a bit of a scary complexity 😛

[austere sparrow]

oops, I got it backwards

wait, I got it backwards triple

just scratch that expression, I'm a college dropout

multiplying the number N by 2 should be, like, O(log(N))

So the pedantic complexity should be something like O(n * sqrt(n) * log(N))

[vocal gorge]

yeah, that seems about right

[golden tangle]

Hi all, hoping someone can help me with some scipy. I'm trying to curve_fit 2 graphs, one the inverse of the other. So one with (e.g) coords (0,1), (1, 3), (2, 6) and one with (1, 0), (3, 1), (6, 2). The second is working fine, the first is not. The actual code and coords are here https://trinket.io/embed/python3/a5bd54189b and probably explain it better than I have right here

Got it. Needed an x^3 poly for one and an x^2 for the other

[golden tangle]

Wrong assumption above. I was rounding to 4dp, as soon as I got rid of that things started working properly

[urban thistle]

Can anyone help me how to convert string "one" to integer 1

[grizzled schooner]

you’ll probably have to make a dictionary (eg {“one”: 1, “two”: 2}, etc)

[fiery cosmos]

what's the time complexity of string += char

I'm confused, this guide says the time complexity is running string += char in a for loop is O(n^2)

but if you convert the string/list to an array first and do str_list.append(char) in a for loop then it's O(n)

[vocal gorge]

Generally, string += char is O(n), where n is the string's length. That's because strings aren't mutable like lists are, so to "append" to a string, one needs to create a new string with an increased length and copy all the data there.
But, CPython has an optimization that, when possible (which is when there's only one reference to string), makes string += other_string try to resize string in-place, which, if successful, results in this operation being only O(len(other string)).

So string += char is O(1) if everything goes well (there's no other references to the string), but can be O(n) if it doesn't.

as a result, this:

a = "some string of length n"
b = ""
for char in a:
    b += char

is O(n^2) without the optimization, O(n) with.

[knotty magnet]

you shouldn't rely on that behavior though

[analog heron]

Hello!
I've got a list of lists, which contains data of this kind: x,y,z,a,r,g,b for all elements.
Here is a sample of my data:
[(3, 3, 1, 255, 55, 58, 87), (2, 3, 1, 255, 93, 101, 143), (1, 3, 1, 255, 230, 231, 239), (2, 3, 0, 255, 132, 100, 107), (6, 2, 0, 255, 90, 128, 135), (7, 5, 0, 255, 41, 61, 82)]
I need to find a list by its coordinates x y z.

But if a for loop with if statement works for 10-200 elements, when you've got 15 millions of elements (and I'll need to do it for each element), it is not possible :/
I never used Numpy but it seems to be the tool to use for working with a lot of data, do you know any way to do it properly?

[jolly mortar]

yeah numpy should be good

[[  3,   3,   1, 255,  55,  58,  87],
 [  2,   3,   1, 255,  93, 101, 143],
 [  1,   3,   1, 255, 230, 231, 239],
 [  2,   3,   0, 255, 132, 100, 107],
 [  6,   2,   0, 255,  90, 128, 135],
 [  7,   5,   0, 255,  41,  61,  82]]

given say [1, 3, 1], you want [255, 230, 231, 239]?

[analog heron]

yup, exactly!

[jolly mortar]

you could check where the [:, :3] slice equals [1, 3, 1]

(where the first : means "check all rows", and the :3 means check the first 3 columns)

!e
so that gives you a numpy array of booleans indicating which rows satisfy that condition

import numpy as np
a = np.array(
  [[  3,   3,   1, 255,  55,  58,  87],
   [  2,   3,   1, 255,  93, 101, 143],
   [  1,   3,   1, 255, 230, 231, 239],
   [  2,   3,   0, 255, 132, 100, 107],
   [  6,   2,   0, 255,  90, 128, 135],
   [  7,   5,   0, 255,  41,  61,  82]])

print((a[:, :3] == np.array([1, 3, 1])).all(axis=1)) 

(the .all(axis=1) is to make sure that only rows where all the 3 columns match are selected)

[halcyon plank]

@jolly mortar :white_check_mark: Your eval job has completed with return code 0.

[False False  True False False False]

[jolly mortar]

which tells us that the condition is only true for the 3rd row

we can use this array as an index for the original array, to get that row

!e

import numpy as np
a = np.array(
  [[  3,   3,   1, 255,  55,  58,  87],
   [  2,   3,   1, 255,  93, 101, 143],
   [  1,   3,   1, 255, 230, 231, 239],
   [  2,   3,   0, 255, 132, 100, 107],
   [  6,   2,   0, 255,  90, 128, 135],
   [  7,   5,   0, 255,  41,  61,  82]])

mask = (a[:, :3] == np.array([1, 3, 1])).all(axis=1)
print(a[mask]) 

[halcyon plank]

@jolly mortar :white_check_mark: Your eval job has completed with return code 0.

[[  1   3   1 255 230 231 239]]

[jolly mortar]

!e
note that this is also a 2D array, and we want the last 4 items from the first row, so we have:

import numpy as np
a = np.array(
  [[  3,   3,   1, 255,  55,  58,  87],
   [  2,   3,   1, 255,  93, 101, 143],
   [  1,   3,   1, 255, 230, 231, 239],
   [  2,   3,   0, 255, 132, 100, 107],
   [  6,   2,   0, 255,  90, 128, 135],
   [  7,   5,   0, 255,  41,  61,  82]])

mask = (a[:, :3] == np.array([1, 3, 1])).all(axis=1)
row = a[mask][0]
print(row[-4:])

[halcyon plank]

@jolly mortar :white_check_mark: Your eval job has completed with return code 0.

[255 230 231 239]

[analog heron]

I'm trying your solution, but it seems really accurate. Thanks a lot!

[keen hearth]

You could create an index on the columns x, y, z. In a SQL database this would be as simple as create index myindex on mytable (x, y, z);. As you have 15 million rows, it might be worthwhile considering using SQL. In python you could use a dictionary like so: py from collections import defaultdict index = defaultdict(list) for row in rows: x, y, z, *_ = row index[x, y, z].append(row) Then look up all the corresponding rows like so: ```py
index[1, 2, 3] # A list of rows for which x=1, y=2, z=3

The nice thing is that once you've built the index, the time it takes to look up rows is essentially independent of the total number of rows in your data.

But there is a cost to maintaining the index, if your data changes often.

[analog heron]

I've got an issue. The input, that I get by the plyfile librairie, is in a numpy.memmap object ; I've got this error:

    mask = (a[:, :3] == np.array([x, y, z])).all(axis=1)
  File "/usr/lib/python3/dist-packages/numpy/core/memmap.py", line 331, in __getitem__
    res = super(memmap, self).__getitem__(index)
IndexError: too many indices for array: array is 1-dimensional, but 2 were indexed

[jolly mortar]

🤔

the array is supposed to be 2 dimensional

can you print a out before that line

[analog heron]

ofc!

[(55, 126, 201, 255, 107, 88,  98) (55, 124, 202, 255, 126, 96, 109)
 (56, 124, 202, 255, 121, 97, 109) (57, 124, 202, 255, 118, 97, 110)
 (55, 125, 202, 255, 115, 94, 107) (55, 126, 202, 255, 107, 88,  98)]

[stable pecan]

looks like a is of dtype=object, (an array of tuples)

[fiery cosmos]

Hello

[old rover]

i'm looking at depth first search

why does it go from 0 to 1 and not 0 to 4?

i don't think it matters

[cosmic geode]

is there some trick to converting coordinates to z-order? I mean the obvious approach would be to just actually interleave the binary representation, but I feel like there's some pattern I'm overlooking

is that just how you'd normally do it?

[covert totem]

How can I go through a list

[keen hearth]

Just iterate through a list? ```py
for element in mylist:
...

[covert totem]

yes ty

[languid cradle]

can someone help me how to use sympy for solving a linear equation to find value of n

logic is i have to find time complexity

for like

eg

sqroot(n)-10**6=0 // this will be for 1 second

find value of n

n is my time complexity

and n is in millisecond

second part

got it F

my bad

[tribal pendant]

it's not linear equation if there is a square root

[brave light]

i need some help on solving sudokus

umm followed a tutorial, designed (or rather copied) their backtracking algorithm

umm its performance is incredibly inconsistent

i would appreciate is someone would help

heres some context:

    # Solve function using backtracking.
    def solve_grid(self) -> bool:
        for row in range(9):
            for column in range(9):
                if self.grid[row][column] == 0:
                    for num in self.shuffled_range(1, 10):
                        self.grid[row][column] = num
                        if self.check_location_validity(row, column) and self.solve_grid():
                            return True
                        self.grid[row][column] = 0
                    return False
        self.grid_filled = True
        return True

[austere sparrow]

@brave light can you perhaps share the whole code?

[brave light]

uhh prob 2 long

[austere sparrow]

!paste

[halcyon plank]

Pasting large amounts of code

If your code is too long to fit in a codeblock in discord, you can paste your code here:
https://paste.pydis.com/

After pasting your code, save it by clicking the floppy disk icon in the top right, or by typing ctrl + S. After doing that, the URL should change. Copy the URL and post it here so others can see it.

[brave light]

but yeah here it is

https://paste.pythondiscord.com/vebaxoyoqe.sql

heres the problem

[vocal gorge]

This appears to not do any work to prioritize locations with fewer possibilities

so no wonder it gets caught up in bad choices

[austere sparrow]

yeah, that might be a good idea

[brave light]

its brute force after all

[austere sparrow]

also tabs

[brave light]

holy god when did someone set tabs as default indentation method

[austere sparrow]

Sure, but some cells can only possibly have {1, 2}, but other can have {1, 2, 3, 4, 5, 6, 7, 8, 9}, and if you eliminate the 2 from the first one, you basically get a free hint

[brave light]

so uhh can you guys walk me thru the process of implementing such an algorithm?

i'm sick of seeing O(9^(n^2)) everyday

[vocal gorge]

basically:

1. For each empty cell, calculate the number of possible choices.
2. If you find a cell with zero, the board is unsolvable.
3. If you find a cell with one, take that choice immediately.
4. Otherwise, find a cell with the lowest number of choices on the board, and try all the choices for it.

the worst-case complexity is probably still bad (is it even possible to have good worst-case?) but average would be way better.

[brave light]

huge improvement it would be indeed

so this is my take

[austere sparrow]

Another possible issue is that you're generating puzzles which may be unsolvable. So maybe test the algorithm on puzzles you know are solvable

[brave light]

yup (uhh i think that with each grid permutation there is at least 1 possible solution?)

[vocal gorge]

2. If you find a cell with zero, the board is unsolvable.
   actually, that can't happen in the process, unless you have been taking invalid choices, so no need to check

[brave light]

ah thanks

so this is my take

iterate while keeping check of max number of clues

if you encounter max num. of clues find a number for it

actually lemme tell u something

shuffled_range() was the first and only ever optimization i found for this algorithm i wrote

basically it prevents something like testing 1, then 1, 2, then 1, 2, 3, then 1, 2, 3, 4 and such

[vocal gorge]

shuffled_range essentially should make it harder to construct a worst-case for your solver

without it, a sudoku where the first cells are 987 would be a killer for it (it would try literally every other case before that)

[brave light]

-\_("/)_/-

[austere sparrow]

This is what I would do: instead of storing a 2d list of integers, I'd store a 2d list of sets, like

[[{1, 2, 3}, {2, 3}, {4, 5, 6}, ...],
 [...],
 ...
]
```, where the each set stores all possible values that can fit in that cell. If the value is known certainly, the set has only one element. This should simplify some stuff.

Another improvement might be to not deepcopy the board, and instead roll back any changes you've made

[brave light]

i’d prob store it somewhere during solving

i uh still need the numbers to create a ui for users to solve

[austere sparrow]

well, sudoku games usually have a feature to put "pencil marks" to mark possible values for a cell

[brave light]

yup

[austere sparrow]

If you want an example of a more complicated sudoku solving algorithm, there's sgtpuzzles: https://github.com/chrisboyle/sgtpuzzles/blob/main/app/src/main/jni/solo.c#L644. It's in C, but it has lots of comments explaining the algorithm. And it works for larger sizes of boards

[halcyon plank]

app/src/main/jni/solo.c line 644

* Solver.```

[brave light]

imma code it up and prob get back to you later

[austere sparrow]

Also, generating boards is apparently much harder than solving them. Generating a board with 25 5x6 cells takes 52 seconds (!) for me

[brave light]

is randinting out empty coordinates that inefficient?

[brave light]

for my algo, though

[austere sparrow]

if you just put random numbers on random places, you have a high change of making a game that's unsolvable (either has a contradiction or has multiple solutions)

[brave light]

how

i mean uh each permutation has been proven to have exactly 1 solution

removing cells should only open up more choices for the user, amirite?

probably wrong but i have not been researching carefully about sudoku puzzles

[austere sparrow]

For example, the board on the left has a solution, the board on the right doesn't

ah, I see how you generate boards

well, you can still end up with a board that has more than 1 solution

[brave light]

:/ better yet

but how comes adding a 3 there messes the board up?

[austere sparrow]

The board on the left has one solution, and there's a 9 in the place of the 3. So logically, if you place a 3 there, there will be zero solutions

[brave light]

ohhh

in the spirit of puzzles, doesnt that mean that you have to start over?

[austere sparrow]

hm?

[brave light]

so not every combo of possible nums at first produce a solution right?

[austere sparrow]

what do you mean?

[brave light]

both 3 and 9 is valid at first

but filling 3 in deadlocks the grid

[austere sparrow]

yes

[brave light]

so i see how generating a board is harder than expected

alrighty time for me to code your suggestions up

[austere sparrow]

I actually have no idea how to generate a sudoku board, but there's a generator somewhere here as well

[brave light]

hell neither do i know anything besides randomly removing numbers

[fiery cosmos]

Hey, I'm not sure if this is the right place but does anyone know the faintest thing about Contract ABI's for Ethereum? I'm doing some data-logging work but theres 0 good sources.

I only assume this is the right place since ABI's are essentially made of JSON / Dicts with some fairly complex detail

[rugged swan]

Why this code not run

[merry idol]

@flat mortar I wrote yesterday with you and you gave me a "solution" how i could code my programm for my recipes but I wanted that users could chose there recipe with a input and you wrote in your code that I chose which recipe will be chosen.

[keen hearth]

@brave light You might find this useful: https://norvig.com/sudoku.html

[brave light]

@keen hearth thanks a lot

[red garnet]

hello, in the case of dummy-headed circular doubly linked list, do I need to connect the tail with the dummy head or with the actual head?

[knotty magnet]

the tail is only connected to the head in a circular linked list

[old rover]

class Graph:
  def __init__(self):
    self.vert_list = {}
    self.num_vertices = 0

why is it called a list

when it's a dictionary

well i changed it to self.vert_dict = {}

 def add_vertex(self, key):
    self.num_vertices = self.num_vertices + 1
    new_vertex = Vertex(key)
    self.vert_dict[key] = new_vertex
    return new_vertex

also i looked at this and I don't get it... the vertex I just added is now equal to the value in the dictionary as the new vertex?

[keen hearth]

Surprisingly, if you start with random values, then repeatedly choose a conflicted square and change its value to one with fewer conflicts (with a bit of randomness to avoid local-minima), you can find a valid puzzle fairly quickly. Try this out: https://paste.pythondiscord.com/pidepurufa.py @brave light

With this script, it typically takes between 2000 and 4000 iterations.

Although it does still occasionally get stuck in a local minimum.

[old rover]

i don't know what "id" means

class Vertex:
    def __init__(self,key):
        self.id = key
        self.connectedTo = {}

"Each Vertex uses a dictionary to keep track of the vertices to which it is connected, and the weight of each edge. This dictionary is called connectedTo. The listing below shows the code for the Vertex class. The constructor simply initializes the id, which will typically be a string, and the connectedTo dictionary."

[keen hearth]

Hey @old rover 🙂 What are you working on?

[old rover]

graphs 😦

they're ok

from pythonds.graphs import Graph

what

i don't think an interview just lets you use an external library to create a graph

[keen hearth]

Yeah 😄 I would typically represent the nodes of the graph as hashable values, and the edges of the graph with a dictionary mapping each node to all of the nodes it is connected to.

[old rover]

yeah that makes sense

[keen hearth]

I think the 'key' thing is their way of getting around their Vertex class not being hashable.

[old rover]

meh I just needed to figure out how to write code for a graph

I think I have a better understanding now

moving onto DFS and BFS

Pomodoro is working wonders

I no longer spend 5-6 hours staring at my computer

[keen hearth]

Ah yes 😄

Pomodoros are great for staying on-task.

What are you using for learning resources atm?

[old rover]

Cracking The Coding Interview

the Bible basically

I might take another crack at CLRS too

It should be easier for me bc of Pomodoro

[wanton surge]

Any have idea does exist module that allow to keep floats with tailing zeros? I would like to have floats like 0.120 but by default python truncates it to 0.12

[vocal gorge]

0.120 and 0.12 are the same float. If you want to print it as 0.120, format it to 3 decimal digits when printing, i.e. print(f"{x:.3f}").

If you need to do fixed-point arithmetic (common for handling money, say), consider the decimal library. It uses software-implemented fixed-point decimals instead of floats (sacrificing speed to get away from float problems).

[wanton surge]

I now I can print with format, but I also need to know if value was 0.1 or 0.10 cuz it changes error value for measurement reading. I'm currently reading decimal documentation and i thing it could do the job

[vocal gorge]

I also need to know if value was 0.1 or 0.10 cuz it changes error value for measurement reading
Ah, that's what you're doing. Maybe handle the error value separately - like, for each measurement, store the value and the error, and propagate them when doing calculations?

For example, if you have a measurement of 0.317, we assume an absolute error of 0.001 for it. Then if in the process of calculation we need to square that value, the squared result would be 0.100489 +- 0.000634

[wanton surge]

But error is given by percent of measured value + some digit times 0.1 to the power of least significant digit . If i measured 0.120 then I have 0.120 * precent + 0.001 * digit. So it's problematic cuz it's not the same as python treats this 0.120 * precent + 0.01 * digit.

[vocal gorge]

Ah, that's true, I recall that's the right-er way to estimate measurement errors. Still, that only changes how you calculate the initial error value for 0.120 - it'd be 0.120 * a + 0.001, where a depends on the device in question (and maybe even on the measurement value - I've seen manuals that listed different error percentages depending on the value measured)

My point is basically that instead of tracking the digit count, you should explicitly keep track of the absolute error, and propagate it in your calculations.

You start with 0.120 with some error. Then when doing calculations on it, use the error progagation formulas. If you add or subtrack it with some value with an error, add up the absolute errors. If you multiply or divide it with something, the relative errors are added up instead. And so on.

Then at the end, all you'd need is to look at the absolute error you ended up with. No digit-counting needed.

(That's how I was taught to do for my physics laboratory practice - I assume you're doing something like that).

[wanton surge]

I loosely used term error. I've should say uncertainty of measurement 😅

[vocal gorge]

ah, yeah, that seems to be the right term. I'm basically talking about this general formula for uncertainty propagation:
https://en.wikipedia.org/wiki/Propagation_of_uncertainty#Non-linear_combinations

the way I was taught, I'd do all calculations keeping track of the absolute uncertainty, and only on the final step would I round them. For example, I'd get 0.100489 +- 0.000634 as the final result, round the error to 0.0006, round the value correspondingly to 0.1005, and write 0.1005 +- 0.0006 as the final result.

[wanton surge]

I thing that it would work if I was calculating uncertainty of this measurement, but I have it, it's given by hardware manufacturer. I need it's full uncertainty to use it in formula for propagation to calculate uncertainty of other value.

[wanton surge]

I get this part

[vocal gorge]

Hmm, I'm not sure I get it. If it's a measurement (not a calculated value), what other uncertainty is there except the measurement one?

[wanton surge]

None. Just uncertainty of multimeter measurement. But in rest of code i use measured resistance to calculate resistance of other component. I would like to have option to say that measured resistance is 12.120 ohms for example. In calculations i can use 12.12 but to calculate uncertainty automatically I need this .120 part. Otherwise I'm one order of magnitude off. I would like it to be this way cuz measurements are collected automatically and so full analyze. User just enters measured value and brand of multimeter he used and rest is calculated by program.

I hope this clarifies some things

@vocal gorge it took me while to get my thoughts into one piece 😅

[wanton surge]

Unless you asked for uncertainty of calculated value. Then uncertainty of resistance, generator, oscilloscope and fitted function with 5 variables

[teal urchin]

I don't know if this is the right place to ask this, but it looks close enough to my issue, I think

So, I did a project and uploaded the repo to github @ https://github.com/WatermelonSalt/Zdl. So, can anyone figure out why zdl_tst.py is suuuper slow when compared to zdl.py? zdl_tst.py was supposed to be better. Ctrl + B to Activate textbox and Enter to search btw if you want to see whats making one of them basically run at 0.000001 fps.

Please do ping me if you are writing back to me, thanks

[wanton surge]

#❓｜how-to-get-help

[teal urchin]

I've been doing that the entire day, literally

no luck

[vocal gorge]

Sorry for vanishing like that, a thunderstorm burned something of my ISPs out and disabled my internet 😅

None. Just uncertainty of multimeter measurement. But in rest of code i use measured resistance to calculate resistance of other component. I would like to have option to say that measured resistance is 12.120 ohms for example. In calculations i can use 12.12 but to calculate uncertainty automatically I need this .120 part. Otherwise I'm one order of magnitude off. I would like it to be this way cuz measurements are collected automatically and so full analyze. User just enters measured value and brand of multimeter he used and rest is calculated by program.
Essentially, what I'm suggesting is to store the measurement accuracy separately. Measurements 12.120 and 12.12 would both have a value of 12.12, but different uncertainty values.

[wanton surge]

After all I have same conclusion. Decimal can store 0.1200000 but only if you pass it as string 😅 so i thing I will pass unless i make GUI for setting this up

[vocal gorge]

Well, you accept the input as a string, don't you? Don't convert it to float, pass to Decimal directly.

[wanton surge]

I could force user to pass this one value as string to class but i thing it would be nicer to force him to calculate this uncertainty himself and pass measurement value and uncertainty as float. It would be consistence with other parameters

[vocal gorge]

Yeah, for example

You could make a class storing (and automatically propagating) errors

@dataclass
class ErrorFloat:
    value: float
    error: float = 0.0
    def __add__(self, other):
        if not isinstance(other, ErrorFloat):
            other = ErrorFloat(other) # with zero error
        return ErrorFloat(self.value + other.value, self.error + other.error)
    def __sub__(self, other):
        if not isinstance(other, ErrorFloat):
            other = ErrorFloat(other) # with zero error
        return ErrorFloat(self.value - other.value, self.error + other.error)
    # and so on

and make the user create and pass an instance of that class.

[fiery cosmos]

I wrote something like that a long time ago in C# for a Physics class when I got annoyed that sigfigs were considered so important. But I always wondered - couldn't the error change depending on how the calculation is done? Like will the error for (x - y) * (x + y) and x**2 - y**2 come out the same?

I remember coding in all the formulas for various operations like listed here https://www.geol.lsu.edu/jlorenzo/geophysics/uncertainties/Uncertaintiespart2.html, but it seemed so unlikely the algebra worked out when nesting them and so on

[vocal gorge]

Like will the error for (x - y) * (x + y) and x**2 - y**2 come out the same?
Nope, and that's because this formula is a simplification assuming all the variables are independent

x-y and x+y aren't, I believe

so really, the good idea is to derive the final formula and then calculate the error for it, assuming only the independence of original measurements (which is a good assumption)

maybe there's a way to, like

implement pytorch/tensorflow-like calculation graph tracking

[fiery cosmos]

But what is a "final" formula? Who's to say which expression is better there

[vocal gorge]

The final value is the one you'll be writing on your report sheet 😉

Whose to say which expression is better there
(x-y) * (x+y) is bad to calculate the error of because x-y and x+y aren't independent... hold on, aren't they independent actually?...

[fiery cosmos]

idk

But surely a desirable property of error-bars is it doesn't matter how the expression looked algebraically. No?

[vocal gorge]

yes, it's true that propagating the error step-by-step is concerning because it depends on the path taken

like, c = a * b, d = c / b results in d having an error different from a, despite them literally being the same

I'd claim, though, that the right way is to derive the formula for the final results depending only on the original measurements - here, it's d(a) = a - and calculate the error by that formula, as delta_d = delta_a.

[fiery cosmos]

But then, how are they even valid this is why error calcs annoyed me in physics class

Can I construct an equivalent expression that gives me whatever error I want

[vocal gorge]

The derivatives of a function are well-defined, so you can't write a different formula for d(a), equal to a, with a different error

[wanton surge]

Measure it infinity number of times and uncertainty goes to 0 😅

[vocal gorge]

like, even if you write it as d = a * b / b, the error is still delta_d = delta_a * |d/da(a * b / b)| = delta_a * |b/b| = delta_a

[teal urchin]

Guys, this was soo silly. I actually fixed it up!

[scenic hawk]

could someone explain to me detecting negative cycles for Bellman Ford, especially why we run: for every edge (u,v) if distance (v) <= distance (u) + weight (u,v)

i don't really understand the formula

[fiery cosmos]

class Node:
    def __init__(self, name):
        self.children = []
        self.name = name
    def depthFirstSearch(self, array):
        array.append(self.name)
        for child in self.children:
            child.depthFirstSearch(array)
        return array

really noob question, what is child.DFS(array) doing, like why is it child.function() and not self.function(child, array)

[steep turtle]

guys is replit good for coding??

[fiery cosmos]

I see

I tried rewriting that function without using child.function() but I couldn't

like just by using self.function(self, array, child)

    def depthFirstSearch(self, array, child=None):
        array.append(self.name)
        for child in self.children:
            self.depthFirstSearch(array, child)
        return array

I need to use super() ?

ohh

[pseudo igloo]

Does anyone have any source to practice Data Structures and algorithms could be in python with code or just problems

[fiery cosmos]

leetcode.com is the best tool for DS&A practice for interviews

[pseudo igloo]

Is it free?

[fiery cosmos]

mostly

official answers are not free

user answers are free

[pseudo igloo]

ok ty

[fiery cosmos]

algoexpert is pretty good too imo

not free

[pseudo igloo]

Yea checked that If I will need I will subscribe there

I will master it more and than

[fiery cosmos]

algoexpert is actually best for beginners I think

[pseudo igloo]

oh lmao

[fiery cosmos]

since it's basically video lectures

[pseudo igloo]

Is there some free subscription in algoexpert just to get some idea how it works

[fiery cosmos]

yea I believe u can see some of the questions for free

it's basically like leetcode tho

just with video lectures explaining the answers @pseudo igloo

[umbral swallow]

Can I ask a question here?

[brave oak]

well

as long as it's relevant to the channel

go ahead

[tranquil barn]

Can someone take a look at #help-pie its related to algorithm

[umbral swallow]

Creating a command in Python

I want to create a commands like:

"/add 5", "/subtract 5"

So the whole program is a While True Loop, the main variable is " a = 20 ", I want to create these functions so when I type "/add 5" the result will be 25, then it repeats, it waits for me to give the next command, this time if I type "/add 6" the result will be 26, it'll always start with 20 because that's what I want out of this whole thing. (other examples " /subtract 1" will be 19, it repeats and now I can do "/subtract 20 " and it'll give me 0)

But what's hard for is HOW do I split the command in two different things? " /add 5 ", in this example 5 will be " b" and the command add will do a + b. A thought of mine is that I can use the space (" ") between add and 5, but I'm really puzzled.

Can someone help me please? Python is new for me, but I'm good in C++

[vocal gorge]

But what's hard for is HOW do I split the command in two different things? " /add 5 ", in this example 5 will be " b" and the command add will do a + b. A thought of mine is that I can use the space (" ") between add and 5, but I'm really puzzled.
Precisely. Just use split.

!docs str.split

[halcyon plank]

str.split

str.split(sep=None, maxsplit=-1)```
Return a list of the words in the string, using *sep* as the delimiter string. If *maxsplit* is given, at most *maxsplit* splits are done (thus, the list will have at most `maxsplit+1` elements). If *maxsplit* is not specified or `-1`, then there is no limit on the number of splits (all possible splits are made).

If *sep* is given, consecutive delimiters are not grouped together and are deemed to delimit empty strings (for example, `'1,,2'.split(',')` returns `['1', '', '2']`). The *sep* argument may consist of multiple characters (for example, `'1<>2<>3'.split('<>')` returns `['1', '2', '3']`). Splitting an empty string with a specified separator returns `['']`.

For example:

[vocal gorge]

!e

print("\\add 5".split(" "))

[halcyon plank]

@vocal gorge :white_check_mark: Your eval job has completed with return code 0.

['\\add', '5']

[umbral swallow]

Split and the blank space (" ")

And how do i tell the program that 5 = b

That the second value is b

[vocal gorge]

You can unpack a list into variables like a, b = lst

in this case, you'd want something like command, value = inp.split(" ")

[umbral swallow]

Thanks so much guys

[vocal gorge]

this will crash if inp.split(" ") isn't two elements, which is handy.

[umbral swallow]

I ll try this

[cyan ice]

I have a datastructures query open in #help-cookie if someone can please look?

[last fulcrum]

Does anyone want to solve DS & A questions together?

[dapper sapphire]

Is below pretty much one of the ways to increment a character?:

!e

alpha = 'a'

print(alpha)
print(chr(ord(alpha) + 1))

[halcyon plank]

@dapper sapphire :white_check_mark: Your eval job has completed with return code 0.

001 | a
002 | b

[dapper sapphire]

I remember in c we can do something like:

#include <stdio.h>

int main(void)
{
    char string[] = "abcd";

    string[0] = string[0] + 1;

    printf("%s", string);
}

[austere sparrow]

😄

the bot only runs Python

[austere sparrow]

yeah

there isn't really a character type in Python

[dapper sapphire]

lol I was like hey doesnt hurt to give it a try.

[dapper sapphire]

Like we dont have a char data type in python?

[austere sparrow]

yes

well, it wouldn't be a char from C, it would be a unicode codepoint

but still

[dapper sapphire]

ok that makes sense.

[austere sparrow]

so chr just returns a string of length 1

[dapper sapphire]

so chr converts an ascii numerical value to a character

I guess maybe because I dont increment characters in my day to day routine lol, so chr(ord(foo)) doesnt stick right away.

[fervent saddle]

Unicode value

[dapper sapphire]

Unicode value?

[fervent saddle]

Unicode value

Not ascii value

That’s only from 0 to 127

[dapper sapphire]

oh ok thanks!

[old rover]

ok so here's the psuedocode reducible wrote

def dfs(self, v):
    marked = [False] * self.vert_dict.size()
    if v in self.vert_dict:
      marked[v] = True
      for nodes in self.vert_dict[v]:
        if not marked[nodes]:
          self.dfs(self.vert_dict, v)

here is what I wrote

am I on the right path?

[knotty magnet]

almost, yeah

the, issue is that marked will be created every time you recurse, so you aren't actually tracking which you've reached already

[old rover]

so it should be after the if statement

[knotty magnet]

also, that looks very much like python in that pseudocode, lol

no, it should be outside the function itself

[old rover]

yep

  marked = [False] * self.vert_dict.size()

this throws me an error

bc i use self

should I create the marked variable where I define what self.vert_dict is?

no that doesn't work

bc then it only exists in the scope

[strong cairn]

i am a python beginner, can someone tell me where to start?

[old rover]

now it works.... when I define it in both places???

nvm that's not what i want

yeah I'm stuck

nope i don't get what to do

it doesn't like that i'm using self

marked = [False] * self.vert_dict.size()

  def dfs(self, v):
    if v in self.vert_dict:
      marked[v] = True
      for nodes in self.vert_dict[v]:
        if not marked[nodes]:
          self.dfs(self.vert_dict, v)

this is currently my issue

[knotty magnet]

what's self, your graph object?

[old rover]

class Graph:
  def __init__(self):
    self.vert_dict = {}
    self.num_vertices = 0

yeah

i tried creating marked in the graph class

[knotty magnet]

you can pass it as an optional parameter in dfs

[old rover]

marked = [False] * self.vert_dict.size()

  def dfs(self, v, marked):
    if v in self.vert_dict:
      marked[v] = True
      for nodes in self.vert_dict[v]:
        if not marked[nodes]:
          self.dfs(self.vert_dict, v)

something like this?

it still doesn't work

if i take out the self, then it's "undefined name vert_dict"

[knotty magnet]

no, you would create it inside dfs, then pass it to subsequent calls as an optional parameter

[old rover]

def dfs(self, v):
    marked = [False] * self.vert_dict.size()
    if v in self.vert_dict:
      marked[v] = True
      for nodes in self.vert_dict[v]:
        if not marked[nodes]:
          self.dfs(self.vert_dict, v, marked)

something like that?

[knotty magnet]

almost

have you tried running it

[old rover]

no not yet

[knotty magnet]

are you using an ide

[old rover]

repl.it

def add_vertex(self, key): #adds a vertex to the graph
    self.num_vertices = self.num_vertices + 1
    new_vertex = Vertex(key)
    self.vert_dict[key] = new_vertex
    return new_vertex

don't you just call this with add_vertex(5)?

nope

[knotty magnet]

are you able to download thigns? or is replit all you can use

[old rover]

i can download things

i think i might know the problem

[knotty magnet]

i would recommend downloading an ide, replit is absolute shit

you call methods on an instance of the class, so

graph = Graph() # or however you instantiate it
graph.add_vertex(5)

[old rover]

how did i forget that

def get_vertices(self):
    return self.vert_dict.keys() #gets the vertices of the graph 
  
  def __iter__(self):
    return iter(self.vert_dict.values()) #returns a list of vertices

when I call these two methods... it shows the position of the vertices in memory

oh it does... that's what it's supposed to do

[knotty magnet]

i'm guessing you have a Vertex object?

[old rover]

yes

oh i know now

meh i'll do it tomorrow i'm feeling tired

[dapper sapphire]

Why does string method __contains__ have dunder?

!e

str1 = "abcd"
str2 = "abcde"

print(str2.__contains__(str1))

[halcyon plank]

@dapper sapphire :white_check_mark: Your eval job has completed with return code 0.

True

[austere sparrow]

__contains__ is the dunder method for in

!e

class Foo:
    def __contains__(self, other):
        print("aye")
        return True

print(1 in Foo())

[halcyon plank]

@austere sparrow :white_check_mark: Your eval job has completed with return code 0.

001 | aye
002 | True

[dapper sapphire]

wait what you did 1 in Foo() and it returned True. Is it because 1 is True and 0 is False?

!e

str1 = "abcd"
str2 = "abcde"

print(str1 in str2)
print(str2 in str1)

[halcyon plank]

@dapper sapphire :white_check_mark: Your eval job has completed with return code 0.

001 | True
002 | False

[dapper sapphire]

!e

class Foo:
    def __contains__(self, other):
        return True

print(1 in Foo())
print(2 in Foo())
print(0 in Foo())
print(-1 in Foo())

[halcyon plank]

@dapper sapphire :white_check_mark: Your eval job has completed with return code 0.

001 | True
002 | True
003 | True
004 | True

[fervent saddle]

He wrote the method to always return True

So that’s all it does

[fiery cosmos]

print("ThingThatIsDefinitelyNotInFoo" in Foo())

[austere sparrow]

as I said, __contains__ is the method that overloads the in operator

[dapper sapphire]

Oh oh I see what's happening lol!!

You redefined __contains__ so in always returns True now.

I had a dumb moment! 🤦‍♂️

Thanks!!

[heady saddle]

Hi! I'm trying to make a rain prediction model using already existing data but get errors left and right. Pls help me in #help-mango

[tribal lotus]

Anyone here experienced with Numpy array manipulation?

I got an array from the DirectX buffer based on the screen:

shape: tuple(3) (500, 1920, 3)
size: 2,888,000
each pixel: [40, 42, 54]

From my understanding, that's RGB values.

I want to convert it into something like:

shape: tuple(3) (500, 1920, 4)
size: 3,840,000
each pixel: [54, 42, 40, 255]

Which is basically the R and B values exchanged and 255 (I think it's the alpha value) appended to the end of each pixel. Anyone have a fast way to do this through Numpy since it's Numpy arrays.

Please ping me if you have an answer that's performance wise super fast.

[jolly mortar]

to exchange the R and B you could do arr[..., [0, 2]] = arr[..., [2, 0]]
to add a 255 at the end you could make a np.full array with the same number of rows and columns as arr, and fill_value as 255 and concatenate this array with arr

In [65]: %%timeit a = np.arange(2880000).reshape((500, 1920, 3))
    ...: a[..., [0, 2]] = a[..., [2, 0]]
    ...: a = np.concatenate((a, np.full(a.shape[:2] + (1,), 255)), axis=2)
    ...:
    ...:
53.7 ms ± 6.58 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

it won't be too fast in any case, because the dimensions of a numpy array aren't supposed to change

[tribal lotus]

@jolly mortar what were the times you achieved?

[jolly mortar]

53.7 ms ± 6.58 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

[tribal lotus]

so at minimum 46ms and max 59ms.

That's too slow.

Way too slow.

In #help-cake somebody help me figure out a way to do it in under 3ms given I resize the image a little prior.

[tribal lotus]

For those wondering or check later, this is the fastest way we were able to found.

It's exponentially faster the smaller the image, so do resizing faster.

Essentially, it's conversion from RGB to BGRA.

[jolly mortar]

In [101]: %%timeit old = np.zeros((500, 1920, 3))
     ...: n = np.zeros((500, 1920, 4))
     ...: n[:, :, 0] = old[:, :, 2]
     ...: n[:, :, 1] = old[:, :, 1]
     ...: n[:, :, 2] = old[:, :, 0]
     ...: n[:, :, 3] = 255
     ...:
     ...:
37.3 ms ± 3.72 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [102]: %%timeit a = np.zeros((500, 1920, 3))
     ...: b = np.append(a, np.full((500, 1920, 1), 255), axis=2)
     ...:
     ...:
26.7 ms ± 3.66 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

np.append was slightly faster for me

[tribal lotus]

oh interesting. might try that. @jolly mortar

[manic hatch]

hi, i'm looking at the voss function in https://github.com/AllenDowney/ThinkDSP/blob/master/code/voss.ipynb, any idea how to speed it up?

def voss(nrows, ncols=16):
    """Generates pink noise using the Voss-McCartney algorithm.
    
    nrows: number of values to generate
    rcols: number of random sources to add
    
    returns: NumPy array
    """
    array = np.full((nrows, ncols), np.nan)
    array[0, :] = np.random.random(ncols)
    array[:, 0] = np.random.random(nrows)
    
    # the total number of changes is nrows
    n = nrows
    cols = np.random.geometric(0.5, n)
    cols[cols >= ncols] = 0
    rows = np.random.randint(nrows, size=n)
    array[rows, cols] = np.random.random(n)

    df = pd.DataFrame(array)
    df.fillna(method='ffill', axis=0, inplace=True)
    total = df.sum(axis=1)

    return total.values

i want to apply pink noise over an array with shape (6, 100_000)

with each row independent from the other, so i guess that makes 6 times (100_000, 1)

[stable pecan]

cv2 has a RGB to BGR conversion, which may more or less do the exact same thing (it stores image data in numpy arrays as well)

this would just be cv2.cvtColor(my_image, cv2.COLOR_RGB2BGRA)

[stable pecan]

you didn't swap the B and R channels did you?

[jolly mortar]

oh

f

[stable pecan]

you can copy the whole array flipped though on the right rectangular section, you don't need three copies

though it's the same amount of work anyway

In [36]: old = np.random.randint(0, 255, (500, 1920, 3), dtype=np.uint8)
    ...: n = np.full((500, 1920, 4), 255, dtype=np.uint8)
    ...: n[..., 2::-1] = old
    ...: 

In [37]: (n[..., 0] == old[..., 2]).all()
Out[37]: True

In [38]: (n[..., 2] == old[..., 0]).all()
Out[38]: True

this is how you do just one copy

err, well, one slice

[coral pumice]

Hello friends please am really I need of your help in solving this am working on my final test to work as an intern please help me solve this if you can plse I beg of u all.
Exercice 1

Sorted Search

Implement function count_numbers that accepts a sorted list of unique integers and, efficiently with respect to time used, counts the number of list elements that are less than the parameter less_than.

For example, count_numbers([1, 3, 5, 7], 4) should return 2 because there are two list elements less than 4.

def count_numbers(sorted_list, less_than): pass if name == "main": sorted_list = [1, 3, 5, 7] print(count_numbers(sorted_list, 4)) # should print 2

[knotty magnet]

what have you tried so far

[manic hatch]

that's a strange toy test for an intern..

[tribal lotus]

@stable pecan cv2's conversion is slow at best.

it changes the memory directly

[last fulcrum]

I need help with binary trees. How do I return values from a binary tree. On a platform, I was given this question.

In a binary tree, a node is considered "visible" if no node on the root-to-itself path has a greater value. The root is always "visible" since there are no other nodes between the root and itself. Given a binary tree, count the number of "visible" nodes.

My analysis is a node is visible if it is a child node and is greater than it's parent. This is the code I wrote.

Clearly I'm not doing something right.

    def dfs(node, parent_value, current_sum):
        if not node:
            return 0
        if parent_value < node.val:
            parent_value = node.val
            current_sum += 1
        
        dfs(node.left, parent_value, current_sum)
        dfs(node.right, parent_value, current_sum)
      
        return current_sum
    
    return dfs(root, float('-inf'), 0)

[stable pecan]

cv2 is usually extremely optimized -- did you actually test it and find it slow?

i'm pretty sure it just does these same numpy manipulations but with less python <-> c interfacing

[tribal lotus]

@stable pecan I didn't try it but I found out through Google research and Stackoverflow that it's much slower compared to if you would use Numpy.

The numy operation takes approx. 1-3ms.

Which was sufficient enough for my case.

[stable pecan]

well, should check the dates on it --- cv2 is specialized for this sort of thing, in any case:

In [36]: old = np.random.randint(0, 255, (500, 1920, 3), dtype=np.uint8)
    ...: n = np.full((500, 1920, 4), 255, dtype=np.uint8)
    ...: n[..., 2::-1] = old

that's how you do it with a single slice

[tribal lotus]

Right. I prefer it separated as it's easier for me to understand what's happening.

(Being someone who's fairly new to the Numpy manipulation syntax)

One thing I'm getting some issues with is The Windows Desktop Duplication API. https://github.com/SerpentAI/D3DShot Leveraging D3dshot, I should be getting high frames / second given it's the fastest way to get screen pixel information.

[stable pecan]

i think possibly faster version with the append and a flipped view

[tribal lotus]

However, what's annoying me is the fact that it's incredibly slow if the pixels are changing.

[stable pecan]

I've never tried it, are you doing any other computation?

just grabbing screen info?

[tribal lotus]

Grabbing screen information and then doing the RGB -> BGRA changes.

[last fulcrum]

Sorry to say but isn't this crowding out those who are seeking algorithm help?

Maybe it's DS & A. But doesn't look like that to me

[stable pecan]

it's array manipulation essentially

which is a data structure

[tribal lotus]

Oh sorry. I didn't see much of a conversation going here prior to discussing this, and thought maybe it's an issue with the way the data is being handled.

[last fulcrum]

Ok ok

Sorry then

@tribal lotus please go on

[tribal lotus]

the claims are that it's the fastest way to capture screen with Python on Windows 8.1+

[stable pecan]

i can try to help with the binary tree thing, but i was thinking about this -- it may be the fastest, but you might still be limited by python speed

[tribal lotus]

But going all the way upto 16ms when pixels change is kind of odd.

I understand python isn't (ahem) the fastest language there is.

[stable pecan]

there's numba you can try to speed up numpy operations (it will use gpu)

[tribal lotus]

But clearly it can't be that slow.

Numba?

[stable pecan]

i think that's the package

https://numba.pydata.org/

[tribal lotus]

ah JIT

[stable pecan]

oh that's not the one that uses gpu -- nevermind it is the one that uses gpu

[tribal lotus]

Yeah JIT does speed up repetitive operations.

@stable pecan they have both CPU & GPU

if you want to write GPU algorithms, it'll use JIT for that

and if it's CPU algorithms, it'll use JIT for that

[stable pecan]

yeah, there's another package as well, but i'm not too familiar with them

[tribal lotus]

JIT basically is like a cache.

Which will just help repetitive processes.

(which is good for my case I suppose so)

since I'm looping.

But I truly wonder how much I can parallelize.

but it still doesn't really explain why the WDDAPI is so slow with Python.

These were the benchmarks available on D3dshot. @stable pecan

Now, fair enough I'm not running an Intel UHD Graphics 630, but am running this on an Intel HD Graphics 620, it should still be faster than 20 FPS

I'm using Numpy output.

d3dshot.capture() runs the capturing on another thread— is it possibly an issue with the fact that I'm running stuff on the main thread while capturing is being done on another thread?

Sine afaik, 2 threads can't run simultaneously in python.

[stable pecan]

oh yes, because of the GIL threads can actually slow down your program -- the requests to grab the global lock have a fair amount of overhead

[tribal lotus]

Ah right. Any way to combat this or do we just start a new process altogether?

[stable pecan]

you can use multiprocessing to run on a different core, or use cooperative multitasking (async)

[tribal lotus]

Well, I should move this to #async-and-concurrency

[stable pecan]

is your last return meant to be indented?

[stable pecan]

    def dfs(node, parent_value, current_sum):
        if not node:
            return 0
        if parent_value < node.val:
            parent_value = node.val
            current_sum += 1
        
        dfs(node.left, parent_value, current_sum)
        dfs(node.right, parent_value, current_sum)
      
        return current_sum
    
    return dfs(root, float('-inf'), 0)

Are you trying to return the total number of visible nodes?

the issue is this:

        dfs(node.left, parent_value, current_sum)
        dfs(node.right, parent_value, current_sum)

You're not saving the result of these function calls anywhere!

(They do not modify the local variable current_sum)

[last fulcrum]

Oh they don't modify because I don't save the results right?

[stable pecan]

the recursion is messed up for the base case as well

there's a simpler way to recurse without the current_sum value needing to be passed at all

[last fulcrum]

What's that?

[stable pecan]

consider that the number of visible nodes from the root is 1 + visible nodes from root.left + visible nodes from root.right

you can just return 1 + dfs(root.left) + dfs(root.right) --- just generalize this

[untold falcon]

hi all. Is this where I'd ask a question related to JSON schema? I've been googling around and haven't had much success with a question.

not sure if that falls under "data struct"

[last fulcrum]

I'll look into it. It's just like the height of a tree

[stable pecan]

height would be 1 + max(dfs(left), dfs(right))

[last fulcrum]

Yea I might the formula is almost the same.

[untold falcon]

my question is fairly simple-- if I have a JSON path, is there an easy way to find the associated JSON object from a given schema?

So lets say i have something like building/room/lighting/power. Is there some way to pull up the Lighting object reference from a given JSON schema?

[old rover]

>>> g = Graph()
>>> for i in range(6):
...    g.addVertex(i)
>>> g.vertList
{0: <adjGraph.Vertex instance at 0x41e18>,
 1: <adjGraph.Vertex instance at 0x7f2b0>,
 2: <adjGraph.Vertex instance at 0x7f288>,
 3: <adjGraph.Vertex instance at 0x7f350>,
 4: <adjGraph.Vertex instance at 0x7f328>,
 5: <adjGraph.Vertex instance at 0x7f300>}
>>> g.addEdge(0,1,5)
>>> g.addEdge(0,5,2)
>>> g.addEdge(1,2,4)
>>> g.addEdge(2,3,9)
>>> g.addEdge(3,4,7)
>>> g.addEdge(3,5,3)
>>> g.addEdge(4,0,1)
>>> g.addEdge(5,4,8)
>>> g.addEdge(5,2,1)
>>> for v in g:
...    for w in v.getConnections():
...        print("( %s , %s )" % (v.getId(), w.getId()))
...

i'm a bit confused by this

the fact that it doesn't even use any of the methods from the vertex class

[last fulcrum]

@stable pecan I'll like to dm you. I have something to say to you

[old rover]

other than get_connections

so dfs is basically going through a graph until you hit a dead end

and then you retrace steps before you hit that dead end

to visit an undiscovered node

is it "naturally recursive" bc you're calling dfs on each neighboring node?

https://youtu.be/PMMc4VsIacU?t=402

talking about this video here

i think i'm finally starting to get it guys

finalllyyyyyyyy

[grand tapir]

@alpine pilot I haven't quite figured it out but what will work is something with swapaxes. myarr.T.swapaxes(1,3) gets you pretty close

Not sure if this is the right channel either, but saw that your help channel got closed

Actually see if that is the answer, I don't have the full dataset so it's hard to tell

[old rover]

def dfs(self, v):
    marked = [False] * len(self.vert_dict)
    # a bunch of False values in a list
    if v in self.vert_dict.values():
      # if a vertices is in the values of the dictionary
      marked[v] = True
      #then turn it into true
      for nodes in self.vert_dict[v]:
        #for vertices in the values that store the vertex
        if not marked[nodes]:
          #if these neighbors aren't marked as true... then run DFS on them
          self.dfs(self.vert_dict, v, marked)
          # do I have to pass in the vertices... I think so bc marked is based on those vertices

am I on the right track here

marked is a list of False values

if a vertex is in the neighbors of any vertices mark it as true

and then the second part is if there are no nodes/vertices in the neighbors of a vertex... if marked has a False... then run depth first search on them again?

[knotty magnet]

sure, you could call it that

[knotty magnet]

almost, have you tried running it

do you have a sample graph that you can use to test on?

[old rover]

yes it seems like it works

[knotty magnet]

it seems? did you test it?

[old rover]

yeah

graph = Graph()

for v in range(6):
  graph.add_vertex(v)

#print(graph.vert_dict)

graph.add_edge(0,1,5)
graph.add_edge(0,5,2)
graph.add_edge(1,2,4)
graph.add_edge(2,3,9)
graph.add_edge(3,4,7)
graph.add_edge(3,5,3)
graph.add_edge(4,0,1)
graph.add_edge(5,4,8)
graph.add_edge(5,2,1)


#print(graph.vert_dict)

graph.dfs(3)

maybe i should print v

well nothing happens bc I'm not returning anything

[knotty magnet]

can you show the add_edge function

[old rover]

  def add_edge(self, f, t, weight = 0): #adds an edge in the graph... adds the new node value and the weight in the dictionary
    if f not in self.vert_dict:
      nv = self.add_vertex(f)
    if t not in self.vert_dict:
      nv = self.add_vertex(t)
    self.vert_dict[f].add_neighbor(self.vert_dict[t], weight)

def add_neighbor(self, nbr, weight = 0):
    self.connected_to[nbr] = weight #nbr is vertex it's connected to and the weight is whatever the cost is for the connection

[knotty magnet]

is self.connected_to a dictionary?

[old rover]

yes

the key is the vertex obj. and the value is the cost

[knotty magnet]

i see

actually can you just send everything in a pastebin instead of me just questioning you

[old rover]

yeah i'll do that rn

!pastebni

[halcyon plank]

Pasting large amounts of code

If your code is too long to fit in a codeblock in discord, you can paste your code here:
https://paste.pydis.com/

After pasting your code, save it by clicking the floppy disk icon in the top right, or by typing ctrl + S. After doing that, the URL should change. Copy the URL and post it here so others can see it.

[knotty magnet]

your dfs function shouldn't work, you're passing too many arguments in the recursive call

[old rover]

https://paste.pythondiscord.com/leneluyomu.rb

i'm gonna take a break for today i think i'm too tired

yeah I pass more arguments than I initially wrote the function to recieve

[fiery cosmos]

!rule 4

[halcyon plank]

Rules

4. Use English to the best of your ability. Be polite if someone speaks English imperfectly.

[last fulcrum]

I need help with this. How do I return current_sum? I'm still struggling with recursion so please explain it to me.
Q) In a binary tree, a node is considered "visible" if no node on the root-to-itself path has a greater value. The root is always "visible" since there are no other nodes between the root and itself. Given a binary tree, count the number of "visible" nodes.

My code.

def dfs(node, parent = float('-inf')):
        if not node:
            return 0

        current_sum = 0
        if node.val > parent:
            current_sum += 1
          
        left = dfs(node.left, node.val)
        right = dfs(node.right, node.val)
        
        
    return dfs(root)

[proven depot]

how are the hashlibs so fast in python? I created my own sha256 program in c and it is pretty fast. Not as fast as the sha256 from hashlibs, more than 6 times fast than mine. And in that situation I was hashing a bunch of different things, and one of them being a txt file of the entire Bible.

oh wait

even when I compile with -O2 or -O3, python's sha256 is 5.5 times faster than my c version

[knotty magnet]

i'm pretty hashlib is written in C

[proven depot]

dang, its still super fast

i probably can't see the implementation right?

maybe ill check out github

yeah i found it on github

[split sigil]

!warn 617982273186430987 Please keep your messages on topic and in English. Posting a huge block of text of a Bulgarian song is neither.

[halcyon plank]

:incoming_envelope: :ok_hand: applied warning to @fringe otter.

[wispy hare]

I think that at the end of the function there should be something like return current_sum + left + right
And I also think that your implementation is not right, because you're comparing with the parent only

I think that the right thing to do is that instead of a parameter parent, you use a parameter max_from_top that starts at float('-inf')

And you update it when calling again, so the call would be like dfs(node.left, max(max_from_top, node.val))

[brisk junco]

I'm currently working on creating an rsi. I got the rsi to 'work' but the results are different from the rsi on platforms such as trading view. I've tried multiple different ways to create the rsi with all ways yielding a similar result. If anyone is willing to help it would be greatly appreciated

[tribal lotus]

@stable pecan I believe it was you who recommended me Numba. Issue is, Numba only works if everything in the function is either Numpy or just general loops or arithmetic.

If you for say call a function that uses an object Numba doesn't know, it'll only compile in object mode and not nopython mode.

[raven kraken]

Can anyone explain to me what this question wants? To be specific I didn't understand the 2nd condition about the integer.

[tribal lotus]

I think optimizations and stuff of algorithms and data-structure is best fitted here. @stable pecan & @vocal gorge I did a profile of the program.

[halcyon plank]

Hey @tribal lotus!

It looks like you tried to attach file type(s) that we do not allow (.pstat). We currently allow the following file types: .gif, .jpg, .jpeg, .mov, .mp4, .mpg, .png, .mp3, .wav, .ogg, .webm, .webp, .flac, .m4a.

Feel free to ask in #community-meta if you think this is a mistake.

[tribal lotus]

https://1drv.ms/u/s!AoIOF_tDXwqCm3xtydrxEfgTezDL — you may download the profile from the OneDrive link.

Generated via Pycharm Professional 2021.1.2

^ The above profile is generated while using mss() to capture screen.

https://1drv.ms/u/s!AoIOF_tDXwqCm31d3t8RiS0bz5sI

This one is generated while using d3dshot (directx) to capture screen.

[wraith ocean]

the int is the number representation of the week day

[raven kraken]

Can you tell me the logic to calculate it?

[wraith ocean]

D = 2020-01-01 evaluates to a mean value of based on the previous day

[wraith ocean]

8 numbers (9 including the sum) for 1st date: 2+0+2+0+0+1+0+1 = 6 mean val is 1.5? 8 numbers (9 including the sum) for 2nd date 2+0+2+0+0+1+0+4=9 mean val is 2

a bunch more i dont really have time to mess with but just think critically and youll figure it out

[raven kraken]

Thanks for your time

[wraith ocean]

if you dont figure it out and have time to write down so its a little easier to read i could help again

[raven kraken]

Yeah I think I can solve it from here

[old rover]

 def dfs(self, v):
    marked = [False] * len(self.vert_dict)
    # a bunch of False values in a list
    if v in self.vert_dict.values():
      print(v)
      # if a vertices is in the values of the dictionary
      marked[v] = True
      #then turn it into true
      for nodes in self.vert_dict[v]:
        #for vertices in the values that store the vertex
        if not marked[nodes]:
          #if these neighbors aren't marked as true... then run DFS on them
          self.dfs(self, v)
          # do I have to pass in the vertices... I think so bc marked is based on those vertices
      
        #O(V + E) time where V is the number of vertices and E is the number of edges

well this still doesn't work

def dfs(self, v,marked):
    marked = [False] * len(self.vert_dict)
    # a bunch of False values in a list
    if v in self.vert_dict.values():
      print(v)
      # if a vertices is in the values of the dictionary
      marked[v] = True
      #then turn it into true
      for nodes in self.vert_dict[v]:
        #for vertices in the values that store the vertex
        if not marked[nodes]:
          #if these neighbors aren't marked as true... then run DFS on them
          self.dfs(self, v,marked)
          # do I have to pass in the vertices... I think so bc marked is based on those vertices
      
        #O(V + E) time where V is the number of vertices and E is the number of edges

i made this change here

graph.dfs(3, [])