algos-and-data-structs

[jolly mortar]

f(n) belongs to O(g(n)) iff its possible to pick two positive constants c and k such that the graph of f(n) is always below (or at most touching) the graph of c g(n) for all n > k

2n belongs to O(n) because you can pick, say, c = 3 and k = 0, and the graph of 2n is always bounded by the graph of 3n for all n > 0

[fiery cosmos]

🤔

[jolly mortar]

how about... no matter what c you pick, 2^2n will always eventually overshoot c 2^n, so 2^n cannot be an upper bound for 2^2n

[agile sundial]

2^2n is the same as 2^n * 2^n, which is obviously 2^n times larger than 2^n, so 2^2n is obviously not in O(2^n)

[haughty mountain]

People sometimes use big O and related notations in exponents for this kind of reason

for a and b constants, O(2^(a*n)) and O(2^(b*n)) are not the same unless a == b

as others stated, if 2^(2n) = O(2^n) then there is some constant C such that

2^(2n) < C*2^n
``` we can solve for `C`

2^n < C
```and clearly this C is not a constant, this means that 2^(2n) is not in O(2^n)

[fiery cosmos]

Does that mean, we ignore constants in big o notation except when they are in superscript?

[haughty mountain]

it's not quite that simple, the notation has a strict mathematical definition which you should probably get familiar with,
f(x) is in O(g(x)) if there exist some constant C such that f(x) < C*g(x)

this implies that stuff like multiplying by a constant doesn't matter, but that's only one of the consequences

what matters in the end is the definition

there are tons of other consequences that doesn't fit what you said, e.g.

log(n^2) = O(log(n))

because log(n^2) = 2*log(n) so if we let the constant C in the definition be larger than 2 the inequality log(n^2) < C log(n) holds

[waxen jackal]

I have to put a string that already contains ' and " as content. How can I declare it also? Is there like in JS a ` ?

[fiery cosmos]

You could escape the character

[dark aurora]

thanks I like list comprehensions much more

What is the time complexity of [1,2]+[2,3,5]

is it O(n+m)?

[haughty mountain]

you could use a triple quoted string

"""string with "double" and 'single' quotes"""

[haughty mountain]

you need to copy elements to a new list, so the complexity is just the number of elements that ends up in the final list

[dark aurora]

thanks

[haughty mountain]

if n and m are the lengths of the lists then yes that's the complexity

in general you have to specify what the variables in your expressions are

[austere sparrow]

2^(2n) is actually 4^n

The only rule that applies to "scaling" is O(f(x) * C) = O(f(x)).

[haughty mountain]

exponentials in general don't plat that well with big O notation if used like that

if you want to compare exponentials you could put stuff in the exponent

e.g. 4^n is in 2^O(n)

at least I think that's how you would write that

[shut breach]

would 2^O(n) be {2^f(X) | f ∈ O(n)}?

[haughty mountain]

the regular rules would apply, there exist some constant C such that the inequality holds

@shut breach
e.g. 4^n = 2^(2*n) < 2^(C*n)where C > 2

[haughty mountain]

so I guess this is true?

[fiery cosmos]

hey all, i'm struggling to understand how to do runtime complexity computation. the methods in the book are very very mathy which i don't understand when one could simply look at an algorithm and get a rough estimate O(n) when everything takes constant time, O(n^2) when you have a nested loop. what about when you have a single while loop? furthermore, when would something take log(n) time or n*log(n) time?

[agile sundial]

the book is mathy because that's what it takes to do more than just a rough estimate

also, if everything is constant time, then the function is constant time

[jolly mortar]

logs often turn up in divide and conquer algorithms

[agile sundial]

in the while loop case, you need to compute how many times the loop runs, the you just multiply that by the time complexity of the stuff inside the loop

[haughty mountain]

yes, nested loops doesn't mean that things are e.g. quadratic

and a single loop isn't necessarily linear, e.g.

def f(n):
  m = n
  while m > 0:
    # some O(1) work
    m //= 2
```this would be `O(log n)`

[fiery cosmos]

How would you approach the question below:
you have a keyword
you also have a list of words
if a combination of the letters in the keyword exist in the list of words, you return true
everything is lowercase

keyword: 'python'
words: ['test','xxx','abcd','ytphno','discord']
my approach was, sum all the ascii values of words in the words list and if the keywords total ascii values is equal to the word in the words list and if the lengths are the same too then they are equal

[haughty mountain]

your approach doesn't work in general

e.g. ad has the same sum and length as bc

there are a few sensible options, you could sort all the strings and then just compare them, or better compute the count of each character in the words and then compare the letter counts

the latter is nicer because you don't have the extra log factor from sorting everything, though in practice they are probably pretty comparable

[fiery cosmos]

how or why is this O(logn)?

[haughty mountain]

think through what happens to m in the loop

how many times will the loop contents run?

[fiery cosmos]

ahh i see it now

[fiery cosmos]

what would be the time complexity of your solution?

[haughty mountain]

the bulk of the time is just computing the counts, and it looks at every character once

writing the exact complexity is a bit awkward, it's O(sum of all the string lengths)

[haughty mountain]

where is this problem from?

oh, nvm it's a simpler version of an interview question I've seen

[fiery cosmos]

https://youtu.be/TKzLFB7Peaw?t=3549

[agile sundial]

you can probably come up with the brute force solution pretty quickly, but if it's not going to be fast enough based on the constraints then why even try it

[haughty mountain]

In practice I would think a bit about the problem.
Usually a brute force solution is obvious, if it's also trivial to implement and the constraints are small then just go for that.

Else consider better approaches, oftentime they might even be simpler/easier to code than a brute force solution

If constraints matter, also consider better approaches

[fervent saddle]

If you have a hash table with separate chaining, does that mean avalanching doesn’t matter? For example if you have the strings “test1”, “test2”, “test3”, and they hash to positions 5, 6, and 7, does that matter if it’s using separate chaining?

[agile sundial]

what's separate chaining

[fervent saddle]

The hash table solves collision by using singly linked lists, or something else to store values, at each position

[agile sundial]

huh, isn't that the normal chaining way?

[fervent saddle]

Is there “normal chaining”?

[haughty mountain]

separate chaining is the way hashmaps are typically taught I think

hence "normal"

I guess the avalanching problem appears when you do a flat hash map?

[fiery cosmos]

What is the hashset equivalent of C++ in python? I use dictionary for checking whether a value was seen or not but don't really need the value part of the dictionary. only the key part. I guess i could use set but set doesn't have constant lookup like dict do. What do you suggest?

[half lotus]

Wouldn't that just be a set in Python?

A set does use hashing in Python

x in some_set is a constant time operation

Oh sorry I replied to the wrong message

Meant to reply to @fiery cosmos

[fiery cosmos]

Are you sure it is constant. I asked this question before actually and ended up referring to the documentation which states the worst case is O(n) which is what I will be asked during the interview. Am I right? I want to make sure that I grasp it before the interview

[onyx root]

the worst case is O(n), but that is the pathological case. Typical is O(1)

you only get O(n) with specially crafted data

[fiery cosmos]

Thank you for the answer. When I am evaluating the time complexity of my solution though during my interview, should I say it is O(n) or O(1)?

[onyx root]

you should say it is "expected O(1)"

[vocal gorge]

example of specially crafted data:

class A:
    def __init__(self, val):
        self.val = val
    def __eq__(self, other):
        # behaves fine:
        return self.val == other.val
    def __hash__(self):
        return 0 #whoops, all collisions!

Set = {A(i) for i in range(10**4)} # This set of only 10k elements takes 2.83s to be created, because every insertion takes O(n) time 

if you don't get to construct your own classes, generating collisions is harder. Python actually has a protection against it - string hashes have a random component per process, so it's not trivial to just find a few thousand/million strings with equal hashes. (If it was, that could be used as a DOS attack - submit them all to some dict/set, and watch it struggle to insert them all)

[fiery cosmos]

thank you. That helps. it is going to be O(n) for list lookup though right?

if n in [1,4,11,2,34]:

[dapper oriole]

Hello, I would like to know how to generate a sudoku. is there an algorithm for this?

[lean walrus]

is there any articles about implementing good __hash__ to prevent collisions?

class Point:
    x: float
    y: float
    def __init__(self, x: float = 0.0, y: float = 0.0) -> None:
        self.x = x
        self.y = y

    def __eq__(self, obj: object) -> bool:
        if isinstance(obj, Point):
            return self.x == obj.x and self.y == obj.y
        return NotImplemented
    
    def __hash__(self) -> int:
        # which implementation is better?
        return hash(self.x) ^ hash(self.y)
        return hash((self.x, self.y))
        ...

[fiery cosmos]

Is there a way of disabling bracket matching on leetcode? It is super annoying

[halcyon plank]

@mystic basin :white_check_mark: Your eval job has completed with return code 0.

001 | 1
002 | 1

[lean walrus]

yes, i know

another alternative```py
return hash((type(self), self.x, self.y))

[tropic falcon]

@next cedar

[fiery cosmos]

Below is my solution to the leetcode minimuum remove to make valid parantesis question. I calculated the time and space complexity as below. Do you think it is accurate?

Time: O(n)
Space: O(n)

class Solution:
  def minRemoveToMakeValid(self, s: str) -> str:
    openings=[]
    closings=[]
    string=list(s)
    
    # determine invalids
    for i in range(len(s)):
      if s[i]=='(':
        openings.append(i)
      elif s[i]==')' and len(openings)>0:
        openings.pop()
      elif s[i]==')':
        closings.append(i)
    
    # remove invalids
    for i in openings+closings:
      string[i]=''
      
    return ''.join(string)

[haughty mountain]

sadly that protection is not there for integers, where hash(x) == x (except for x == -1)

[shut breach]

is there no upper limit for that?

[fervent saddle]

Too bad python doesn’t have bst

[haughty mountain]

kinda, but the hashes are still predictable, the hashes are modulo a prime

In [1]: p = 2305843009213693951

In [2]: hash(p)
Out[2]: 0

In [3]: hash(p-1)
Out[3]: 2305843009213693950

In [4]: hash(p+1)
Out[4]: 1

!e print(hash(-1)) oh yeah, this is the silliest thing

[halcyon plank]

@haughty mountain :white_check_mark: Your eval job has completed with return code 0.

-2

[rapid crater]

-2

[fringe zodiac]

class Database:

    # Empty database to store all the records in a list
    def __init__(self):
        self.__records = []

    # Add record
    def add_record(self, pname, cname, no_of_pax, p_cost_per_pax):
        self.__records.append(Record(pname, cname, no_of_pax, p_cost_per_pax))

    # Return count of records
    def __len__(self):
        return len(self.__records)

    # Helper method to replace records with indexes idx and idy
    def __replace(self, idx, idy):
        self.__records[idx], self.__records[idy] = self.__records[idy], self.__records[idx]

    def shell_sort(self):
        gap = len(self) / 2

        while gap > 0:
            for i in range(gap, len(self)):
                temp = self.__records[i].get_p_cost_per_pax()

                j = i
                while j >= gap and self.__records[j - gap].get_p_cost_per_pax() > temp:
                    self.__records[j] = self.__records[j - gap].get_p_cost_per_pax()
                    j -= gap

                self.__replace(j, i)
            gap /= 2

hi, how do i fix this error? I tried defining gap as an integer but it gives a TypeError stating that 'float' object cannot be interpreted as an integer

[haughty mountain]

!e have a fun example for ints

import time

def anti_hash_hack(n):
    pow2 = 2**(n.bit_length() + 2)

    A = [pow2]
    i = 1
    while len(A) < n//2:
        A.append(i)
        i = (5 * i + 1) % pow2

    while len(A) < n:
        A.append(0)

    return A

def measure(A):
    start = time.perf_counter()
    D = {}
    for a in A:
        D[a] = 1
    end = time.perf_counter()
    print(end - start, 'seconds')

n=5*10**4

ok_data = list(range(n))
bad_data = anti_hash_hack(n)

measure(ok_data)
measure(bad_data)

[halcyon plank]

@haughty mountain :white_check_mark: Your eval job has completed with return code 0.

001 | 0.008298241533339024 seconds
002 | 3.486910255625844 seconds

[silent mortar]

hello, I am a little confused on this question of deleting a node, this is the code:
i dont really understand how thise code works

so
d is a node which carries a string --> "dummy"
d.next --> head of the linkedlist (where the linkedlist starts)

we set p to the dummy variable and c to the head so the linked list looks something like this:

p --> c

then in the while loop, we check if c's value = the value we are trying to delete and idrk whats happening after that

class Node(object):
    def __init__(self, v):
        self.val = v
        self.next = None
    
def delete_node(head, val):
    d = Node("dummy") # 1
    d.next = head
    p = d
    c = head
    while c:
        if c.val == val:
            p.next = c.next # 2
            return d.next   # 3
        p = c
        c = c.next
    return d.next # 4 

[polar wing]

hey guys, can someone help me with a good resource to learn (and then practice) algos and data structures in python? Thanks in advance

[haughty mountain]

you're making it into a float with the / division

[fringe zodiac]

i tried the // floor division but it still gave the TypeError

[haughty mountain]

// in both places?

[fringe zodiac]

what do you mean both places?

[haughty mountain]

        gap = len(self) / 2   # 1

        while gap > 0:
            ...
            gap /= 2          # 2

[fringe zodiac]

now it gives this type of error

[haughty mountain]

because of this line

self.__records[j] = self.__records[j - gap].get_p_cost_per_pax()

you seem to be replacing your record with an int here

[fringe zodiac]

oh i just followed the normal code of shell sort in geeksforgeeks.org for arr[j] = arr[j-gap]

[haughty mountain]

you still seem to assign something weird to your record list, in this case a float?

[fringe zodiac]

rc = Database()
rc.add_record("Suite", "Levi", 3, 300.00)
rc.add_record("Deluxe", "Zenitsu", 3, 110.60)
rc.add_record("Euphoria", "Kaguya", 4, 120.50)
rc.add_record("Serendipity", "Anya", 3, 130.30)
rc.add_record("Epiphany", "Kirito", 2, 140.40)
rc.add_record("Gold", "Violet", 1, 150.10)
rc.add_record("Business", "Kazuma", 4, 160.20)
rc.add_record("Base", "Takagi", 2, 170.70)
rc.add_record("Casual", "Emilia", 2, 180.80)
rc.add_record("Luxury", "Miku", 5, 200.00)


def menu():
    display_menu = ("\n1. Display all records\n" +
                    "2. Sort record by Customer Name\n" +
                    "3. Sort record by Package Name\n" +
                    "4. Sort record by Package Cost\n" +
                    "5. Search record by Customer Name and update record\n" +
                    "6. Search record by Package Name and update record\n" +
                    "7. List records range from $X to $Y. e.g $100-$200\n" +
                    "7. Sort record by Package Cost (Shell Sort)\n" +
                    "0. Exit Application\n")

    while True:
        print(display_menu)
        choice = input("Enter choice: ")
        choice = choice.strip()

        if choice == "1":
            print("\nProceeding to display all records...")
            rc.show_all()

        elif choice == "2":
            print("\nProceeding to sort record by Customer Name...")
            rc.bubble_sort_by_name()
            rc.show_all()

        elif choice == "3":
            print("\nProceeding to sort record by Package Name...")
            rc.select_sort_by_package()
            rc.show_all()

        elif choice == "4":
            print("\nProceeding to sort record by Package Cost...")
            rc.insert_sort_by_cost()
            rc.show_all()

        elif choice == "5":
            rc.linear_search_by_cname()

        elif choice == "6":
            rc.binary_search_by_pname()

        elif choice == "7":
            rc.list_range()

        elif choice == "8":
            rc.shell_sort()
            rc.show_all()

        elif choice == "0":
            print("Exited Program")
            break

        else:
            print("Invalid input. Please select from 1 - 7 or 0 to exit.")


menu()

as you can see, yeah there is a float in the object

[haughty mountain]

a float in the object isn't the issue

you replace your record type with a float at some point

hence the error when you try to access a method on it

[fringe zodiac]

is it fine if i send you my whole file so you can take a look?

[haughty mountain]

you assign to your list in only two places, this one is not an issue

    def __replace(self, idx, idy):
        self.__records[idx], self.__records[idy] = self.__records[idy], self.__records[idx]
```so it must be the other one, the one that was
```py
self.__records[j] = self.__records[j - gap].get_p_cost_per_pax()

[haughty mountain]

except you don't do arr[j] = arr[j-gap]

you do something like arr[j] = arr[j-gap].something

so arr[j] is not a Record anymore

[fringe zodiac]

so that "something" is my get method from the class?

[haughty mountain]

yes, presumably it returns a float

[fringe zodiac]

class Record:
    count = 1

    def __init__(self, pname, cname, no_of_pax, p_cost_per_pax):
        self.__pname = pname
        self.__cname = cname
        self.__no_of_pax = no_of_pax
        self.__p_cost_per_pax = p_cost_per_pax
        self.__count_number = Record.count
        Record.count += 1

    def get_pname(self):
        return self.__pname

    def get_cname(self):
        return self.__cname

    def get_no_of_pax(self):
        return self.__no_of_pax

    def get_p_cost_per_pax(self):
        return self.__p_cost_per_pax

    def set_pname(self, pname):
        self.__pname = pname

    def set_cname(self, cname):
        self.__cname = cname

    def set_no_of_pax(self, no_of_pax):
        self.__no_of_pax = no_of_pax

    def set_p_cost_per_pax(self, p_cost_per_pax):
        self.__p_cost_per_pax = p_cost_per_pax

    def __str__(self):
        return f"Record {self.__count_number:<3d}: {self.__pname}, {self.__cname}, {self.__no_of_pax}, ${self.__p_cost_per_pax:.2f}"

is it because of the .2f?

[haughty mountain]

what? the issue isn't with the get method

the issue is that you essentially do

b = Record(...)
a = b.get_thing()
```and you're then surprised that `a` is not a `Record`

[fringe zodiac]

oh i see

[vocal gorge]

Looks accurate to me

[fiery cosmos]

When I sort a multi-dimentional array like this

lis = [[1, 9], [3, 7], [2, 8], [4, 6]].sort()

it sorts based on the first element:
[[1, 9], [2, 8], [3, 7], [4, 6]]
what do I do to sort it based on the second element?

[vocal gorge]

You'd need to provide a custom key-function like lambda row: row[1]

[fiery cosmos]

Do the lines below have the same time complexity and what is their time complexity?

unsortedlist.sort()

unsortedlist=sorted(unsortedlist)

[vocal gorge]

python's sorting algorithm is O(n log n) for both inplace and out-of-place. Inplace sorting also O(1) space complexity

[agile sundial]

actually, i wonder if it's specified that it should be n log n, or just stable

[vocal gorge]

🤷, but if this page has authority:
https://wiki.python.org/moin/TimeComplexity

This page documents the time-complexity (aka "Big O" or "Big Oh") of various operations in current CPython. Other Python implementations (or older or still-under development versions of CPython) may have slightly different performance characteristics. **However, it is generally safe to assume that they are not slower by more than a factor of O(log n). **

[agile sundial]

also, timsort requires a temp array of up to N // 2 pointers

[fiery cosmos]

It turns out .sort() notation uses Timsort which is nlogn.
I am not sure what the other one uses but according to the documentation .sort() is slightly more efficient than sorted()

[vocal gorge]

sort is just timsort but inplace

[agile sundial]

https://github.com/python/cpython/blob/main/Objects/listsort.txt#L17

[halcyon plank]

Objects/listsort.txt line 17

+ timsort can require a temp array containing as many as N//2 pointers,```

[vocal gorge]

https://github.com/python/cpython/blob/main/Objects/listsort.txt
ah, true, I misremembered it being only for out-of-place

[fiery cosmos]

How can I sor a multidimentional array first by the first element then by the second element?
[[2,3], [1,4]] -> [[1,3], [2,4]]

[agile sundial]

that's the default way lists compare, so you don't need a key

[fiery cosmos]

lis.sort() returns [[1, 4], [2, 3]] not [[1,3], [2,4]]

[agile sundial]

oh, that's what you mean

[haughty mountain]

I could spit out some incantation for doing this, but that would probably defeat the learning process of it all

zip to transpose, map sorted, zip to transpose back

[agile sundial]

with python lists, you probably waant to- ^ yeah that

[fiery cosmos]

If I were to apply that incantation, what would be the time complexity?

[agile sundial]

uhh, nm log m? where m is how many rows you have, n is how many columns

it'd be much faster and easier in numpy though, you'd just np.sort(arr, axis=0)

[fiery cosmos]

what is the difference between sorting an ordinary dictionary after populating it and using a ordereddict?

[shut breach]

the only order in a dict is the insertion order

you can't sort it

[fiery cosmos]

I see. what is the cost of using the ordereddict?

[onyx umbra]

for calling in unordered in O(1) but for ordered it is O(log(n))

same for insertion too

[fervent saddle]

OrderedDict isn’t O(log(n)), it’s O(1) too

It doesn’t use a BST, it uses a hash table plus a linked list with the keys at each node

Also it also is only insertion ordered. The difference is that it’s able to efficiently move values to either end, and it’s able to do it without ever needing to resize the hash table

And accessing the key from either end is more efficient. In a normal dict, it can be O(n). Like if you filled the dict, then delete every key except the last one you’ve placed, then access it using next(iter(the_dict)), that’s O(n) if the dict hasn’t resized itself

[fiery cosmos]

How do I do overloading in python?
I have two functions as below:
print_nums(num:int)
print_nums(numlist:[int])

print_nums(4) will print 1 2 3 4
print_nums([1,4,5,2,7]) will print 1 4 5 2 7

[fervent saddle]

You can’t, you just have to use isinstance for it to decide what to do

Python doesn’t have overloading

[fiery cosmos]

oh

[slender sandal]

Except you can implement method overloading using a meta-class

But there's nothing for regular functions as far as I am aware

[agile sundial]

functools singledispatch

[haughty mountain]

I guess OrderedDict is mostly superfluous after dict changed to guarantee insertion order?

[fervent saddle]

If you want to be able to put values at the start efficiently, you kind of need it

[agile sundial]

no, since with ordered dict you can manipulate the order, which you can't with normal dict

[fervent saddle]

And other than that, it’s just faster at accessing values at the ends or moving them to the ends

[agile sundial]

is it really faster at the ends? tbh I've never actually looked at the impl

[fervent saddle]

It should be more optimized since it’s just checking the start/end nodes

[agile sundial]

right but you still have to hash the key right?

[fervent saddle]

And in a regular dict, if you’ve been removing values, it can be O(n) to access from either end

[agile sundial]

oh I see

[fervent saddle]

I don’t think so to access

You would need to do that in order to move one to the end

[agile sundial]

is there a get first or something

[fervent saddle]

Yeah

[agile sundial]

that makes sense

[fervent saddle]

You don’t have to hash the key in a regular dict either, like if you do next(iter(d)) or next(reversed(d)). But it reaches the key by internally going through the insertion ordered array, and if you’ve been deleting keys then it will need to look over all the spaces marked as deleted until it finds the first/last occupied space. So it can be O(n) in that case.

[agile sundial]

right, yeah

[calm shale]

which data structure is best where link is the only unique data?

submissions[link] = {"id": id, "prompt_type": prompt_type, "future_time": future_time, "likes": [likes_list]}

OR

submissions[prompt_type] = {id: {link: [likes_list], "future_time": future_time}}```
prompt_type can only be one of four strings so it'll repeat a lot, id would repeat more on the first one as well. Is the first one quicker to search, does the nested dictionary on the second take up a lot of space?

[haughty mountain]

I would probably bundle your data into a class rather than using a dict

also that, prompt_type should probably be an enum

wrt searching, we would probably need to know a bit more about what data you actually want to store, and what data you want to be able to search by

[calm shale]

a class is probably a better idea i just hate making classes for some reason

[fiery cosmos]

the heapq is a minheap by default right? How do I make it a max heap?

[austere sparrow]

negate the numbers 🙂

-3 < -1, but 3 > 1

Raymond Hettinger once said that he dislikes the procedural interface and just makes a class wrapper for heapq, sounds like a good idea.

[haughty mountain]

yeah, I do the same

example here

[fiery cosmos]

What does procedural interface mean here

[austere sparrow]

as in "procedural programming", not "object-oriented-programming"

[fiery cosmos]

Ah, so the idea is the https://docs.python.org/3/library/heapq.html implementation of a heap is more precedural vs wrapping it in a class like algmyr showed is OO?

[fiery cosmos]

Or maybe I don't get it (I always get confused by the word "procedural" since most code, even OO, is procedural - i.e. it executes line by line or call by call - the exception is maybe like Prolog)

[austere sparrow]

yep

[fiery cosmos]

can someone walk me through this math? can't follow whats going on. its supposed to be pretty simple

[austere sparrow]

to me, 'procedural' vs 'object-oriented' vs 'functional' is not about the way of execution, but about how the concepts are structured

[fiery cosmos]

what do they mean by "we start by assuming that this bound holds for all positive m < n, in marticular for m = |_ n/2 _|

[opal oriole]

If you pick some number other than n, named m, that is less than n, and use that instead, the bounds still holds (assumption). And a possible m that is less than n could be m = floor(n / 2). That value is chosen because it is particularly interesting when used.

[fiery cosmos]

where are they substituting it in ?

[haughty mountain]

tl;dr: assume that the statement is true for m < n, show that it's also true for m == n

[opal oriole]

Right after.

*Also there are some other details I did not include in my breakdown, small, but important, like that m is positive.

[haughty mountain]

the last batch of equation is 4.19 with the thing substituted in

[fiery cosmos]

a redditor i see

[haughty mountain]

why?

[fiery cosmos]

tl:dr

[haughty mountain]

tl;dr is common in general, no?

[fiery cosmos]

oh i picked it up from reddit, nvm

i'm just not following this line by line

[haughty mountain]

what part?

[fiery cosmos]

if you compare the expression just after "yielding", to 4.19, more than one thing has changed

[opal oriole]

Previous sentence.

[fiery cosmos]

instead of subbing it in they have also replaced the T on the right hand side of the equation and a c has appeared

[haughty mountain]

this thing is 4.19

combined with

i.e. take this and substitute for T(floor(n/2))

[opal oriole]

T(n) <= c*n*lg(n) From previous sentence.

Before "We start by...".

It's split along 2 lines.

Plugging in m is plugging in floor(n/2).

[haughty mountain]

now, you would need to prove some base case to actually make the proof work, but that should be easy enough

err, I guess the last expression should be T(m) = O(m lg m) like the first expression

[fiery cosmos]

boy i am really not good at math

idk what is going on

[haughty mountain]

like, what part in particular?

[fiery cosmos]

there are too many new previously unmentioned symbols. i understand that big O, upper bounding of a function f(x) can be said to be g(x) if and only if there exists some constant c that makes g(x) greater than f(x) for all n greater than some n_0 value

[haughty mountain]

the first display equation in my image is just from the definition for big O

[fiery cosmos]

and that for this problem, we are trying to determine an upper bound using this "substitution method" on the recurrence T(n) = 2T(|n/2|) + n

so essentially T(n) can be thought of as f(x) from the definition

we're trying to upper bound the T(n) (the runtime for some given input n)

and we first guess that O = nlogn

i just don't understand how you "know" to plug in the |n/2| term for n in the right hand side while also adding in c

does this stuff actually make sense to you guys? cause i'm considering saving myself a lot of stress and money and walking away

[haughty mountain]

yes, it makes sense

do you know the idea behind inductive proofs in general?

[fiery cosmos]

yes

i even understand a lot of the nuanced distinctions they make but not the core math

[haughty mountain]

cool, so we assume that the statement is true for m<n

in particular, let's look at m = floor(n/2) because that's what is in our recurrence

[fiery cosmos]

wait slow down 1 sec. what i know about inductive proofs is you prove a base case and then prove that it holds true for some other condition, typically n+1, is that it?

[haughty mountain]

from the definition of big O, this holds

[haughty mountain]

in this case we assume stuff about floor(n/2) to prove n, but same idea

[opal oriole]

On knowing why to try that: we are guessing that it involves lg, so it makes sense to keep halving something (so n / 2 specifically chosen).

[haughty mountain]

well, it's more that it shows up in the recurrence

we want to get rid of the T(floor(n/2)) on the right hand side

[fiery cosmos]

is that how you read the partial brackets, as floor?

[opal oriole]

Yea, both. The lg came from recurrence. So it's the original source of the n/2 thought (the recurrence).

[haughty mountain]

yes

ceiling would be with the line at the top

[opal oriole]

"round down" and "round up" (actual terms are floor and ceil).

[fiery cosmos]

the book defines it as the greatest integer less than or equal to

is that the same

[opal oriole]

Yes.

[haughty mountain]

this is then substituted into the original recurrence and we can simplify and bound until we have something on the form relevant for big O

that's it

[opal oriole]

>>> import math
>>> math.floor(2.3)
2
>>> 
``` 2 is the greatest integer less than (or equal to) 2.3.

[fiery cosmos]

tbh i was just ignoring the floor stuff and trying to understand the substitution

[haughty mountain]

did you follow what I said in #algos-and-data-structs message and below?

[fiery cosmos]

no. could you point out which n in the term following "yielding" they have substituted in the m = |n/2| term? is it for every n in T(n) = O(nlogn)?

[haughty mountain]

this

for m = floor(n)

means

[fiery cosmos]

ok i'm following that far

[haughty mountain]

ok, substitute this into the original recurrence

and simplify a bunch until you have shown that T(n) < c n lg n i.e. T(n) <= O(n lg n)

[fiery cosmos]

sorry, i'm not seeing how one could substitute it into the original formula at 4.19

ph

oh

wait no i don't see a substitution i see them multiplying both sides by 2

[haughty mountain]

T(n) = 2 T(floor(n/2)) + n
is the recurrence we are looking at, we replace
T(floor(n/2)) with something larger

crucially this substitution gets rid of the T on the right side, so the expression is not recurrent anymore and we can easily simplify a bit

[opal oriole]

Notice how it goes from = to <=.

[fiery cosmos]

ok so we plug the right hand side of the equation just after "yielding" in for T(floor(n/2)), leaving the constant 2 out front and appending the +n at the end

[haughty mountain]

no, the 2 and +n was already there in the original recurrence

we just replaced part of the expression

[fiery cosmos]

right

why do you not replace the entire expression after the equals in 4.19, why do you not replace only T and instead include the floor expression

this is the point i get to in math where i don't know why it shouldnt be some other way

[haughty mountain]

wdym replace only T?

T is a function

T(floor(n/2)) is a value of the function, which we have an inequality for

[fiery cosmos]

i guess its because we didn't develop an expression for T, we developed one for T(floor(n/2))

ok ok

ok, i think im beginning to get it!

any way to make this more intuitive??

[haughty mountain]

what part is not intuitive atm?

the intuitive idea is just to use the assumption in our induction to bound T(n)

what stops us from just analyzing T directly? it's that it's recursively defined

[fiery cosmos]

hmm

[haughty mountain]

however, with the assumption in the induction we can bound the term with the T on the right hand side

using this we now have an inequality for T(n) that has no T on the right hand side, no recursion

this is an expression we can more easily work with

we make some additional simplifications and we arrive at exactly what we wanted to show, that T(n) = O(n lg n)

[fiery cosmos]

ok. i am very happy for the handholding. i'm not sure that i'd be able to intuit this stuff on my own but maybe next time

[haughty mountain]

(assuming T(m) = O(m lg m) for m < n)

there is still need for some base case, but I guess that's covered somewhere

it's a bit weird to think of a base case for this since the O notation only makes sense as a limit, but whatever

[fiery cosmos]

i thought we only did the base case, and the inductive step would come later

[haughty mountain]

the pattern of "what's on the other side of this equation is annoying, maybe I can bound it and get something I can actually work with" is quite common

[haughty mountain]

no, this is the inductive step

[fiery cosmos]

because its m<n?

and m = floor(n/2)?

[haughty mountain]

assuming things hold for m<n we show it also holds for m=n

[fiery cosmos]

where is that part?

[haughty mountain]

the whole thing? we assume T(m) = O(m lg m) is true for m<n, a particular value that is useful for us is m=floor(n/2)

it gives us a bound that we can use to show that our statement is true for T(n), i.e. that T(n) = O(n lg n)

that is the inductive step

[fiery cosmos]

i get that we showed something for some random variable m < n but what about the m = n bit?

how can you do an inductive step before a base case? btw i have office hrs in 13m so i have to go really soon

@haughty mountain ty for all your help

[haughty mountain]

the inductive step is independent from showing the base cases

you need both for the thing to be correct

but in what order you show them is irrelevant

[fiery cosmos]

oh ok

how are you so good with this stuff are you a software engineer?

[haughty mountain]

like, there are statements where you can show the inductive step, but where there is no base case that makes the thing work

[fiery cosmos]

hm

[haughty mountain]

I wouldn't say I'm good at this because I'm a software engineer. I did a bunch of math and physics in university, so this kind of thing is quite familiar with me

I ended up as a software engineer because I had programming and problem solving as a big hobby

[fiery cosmos]

i did too but nothing like this. i wasn't engineering major

or CS, or any math kind

at least i guessed it correctly!

i'm trying to get a MS in bioinformatics, thats why i'm unfamiliar with all this stuff but being thrown into the deep end so to speak

[haughty mountain]

I did engineering physics, so a bunch of pretty advanced math and physics, theoretical and applied

[fiery cosmos]

yeah i can tell 😵‍💫

[haughty mountain]

I think what you're looking at now is not too advanced, mostly just something you need to get used to

[fiery cosmos]

fair enough. the book gets a lot harder from here though

[haughty mountain]

What you have here should be quite familiar to techniques you would use for inductive proofs in general. Bound the annoying thing (in this case the T on the right hand side) and hope the bound is good enough to prove the thing you want to prove

[fiery cosmos]

I am working on a binary tree implementation as below:

class TreeNode:
  def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
        
  # 1,2,3,4,5,6,7
  def in_order(self, root=self):
    ptr = root
    if ptr == None:
        return
    in_order(ptr.left)
    print(ptr.val, end='')
    in_order(ptr.right)

my_tree = TreeNode(8)
my_tree.in_order() should return 8 but it is producing an error

NameError: name 'self' is not defined

[haughty mountain]

because root=self presumably

you could do

def in_order(self, root=None):
    if root is None:
        root = self

[fiery cosmos]

but then it will never run?

[haughty mountain]

wdym?

[fiery cosmos]

what is wdym?

[haughty mountain]

"what do you mean"

[fiery cosmos]

because of the condition

[haughty mountain]

if you call the function without giving an argument it will run

[fiery cosmos]

then will it exit? what will be the base case for the recursive behaviour to end?

[haughty mountain]

my_tree.in_order()  # argument root is None, if triggers
my_tree.in_order(something)  # argument root is something, if does not trigger

huh? I meant

  def in_order(self, root=None):
    if root is None:
        root = self
    ptr = root
    if ptr == None:
        return
    in_order(ptr.left)
    print(ptr.val, end='')
    in_order(ptr.right)

i.e. add the thing to the top to replace the invalid thing you had

[fiery cosmos]

I am working on an insert function for a linked list implementation as below:

class LinkedList:
  def __init__(self, val:str):
    self.val=val
    self.next=None
  def insert(self, val:str, loc:int):
    if loc==0:
      new_node=LinkedList(val)
      new_node.next=self
      self=new_node
    else:
      pointer = self
      index=0
      while pointer.next != None and index<loc-1:
        pointer=pointer.next
        index+=1
      new_node=LinkedList(val)
      new_node.next=pointer.next
      pointer.next=new_node  

When I insert a location in between it works, but when I try to insert at the beginning it doesn't work. What is it that I am missing?

[fiery cosmos]

how should I do it?

[fiery cosmos]

I rather not return anything for this case. I tried to use nonlocal keyword for self but then got a SyntaxError: name 'self' is parameter and nonlocal error

I am not sure what you mean by that. Should I implement a node class and have treenode inherit it?

[split urchin]

hello everybody, my python skills are intermediate. can someone help me and push me up or maybe code something with me? im an open mind person and we will be have a lot of fun together. i was born in ukraine but i live in germany. feel free to text me if you can help me or i can help you somehow

[void oak]

There are expert of thread?

[keen hearth]

Hey 👋 If you're looking for something to do, consider contributing to one of our bots https://www.pythondiscord.com/pages/guides/pydis-guides/contributing/

Ask in #dev-contrib if you have any questions.

[split urchin]

hey great, thank you very much! 🙂 do you also know other web sites for practising or maybe someone who like doing group calls and code together?

[keen hearth]

People sometimes code together in the voice channels here. We also host a few coding events each year. The next one will be the Summer Code Jam, in July (https://www.pythondiscord.com/events/code-jams/). The other event is PyWeek, which happens twice a year, where you develop a game with a team (or solo).

I quite like this site for solo coding practice: https://www.codingame.com They have challenges which are centred around making AIs for mini games.

[agile sundial]

codewars is nice too

if you can get a bunch of friends to do it, binarysearch.io is cool too, it's basically just leetcode but with your friends

[split urchin]

thank you very much! do you have some friends for coding together or maybe youd like to join me?

[split urchin]

i appreciate your help a lot!! thank you 🙂

[split urchin]

does anyone know how to create own e-learning platform ?

[shut breach]

this isn't the right channel for this, try #python-discussion or open a help channel

[spiral raptor]

Do you guys think there's a considerable difference between learning algorithms and data structures using Python, compared to using C?

[tired wadi]

You have to be aware of memory management vs. in Python, you can just let the language take care of your garbage.

Overall though, having the principal concepts of certain algorithms and data structures is the most important.

[opal oriole]

In C you will have to make some data structures that Python gives you by default (arrays, dynamic arrays, hashtables). C does not really give you anything, not even in the standard library.

[fervent saddle]

Do people actually learn data structures through coding rather than just reading the idea behind them? Because the latter seems more like general coding practice, because at that point, if you’re coding a data structure or reading the source code for a data structure, you would already understand the idea behind how it works.

[agile sundial]

i mean, you'd have to do both right? how do you know you understand a data structure without making one that works properly

[lapis zenith]

Hi guys! So my current job requires me to write in PHP. While I'm learning the syntax, I find this PHP way of creating array very neat because it lets you assign the elements to an index by just pointing the index to the value. My question is: is there an equivalent of this in python?

[jolly mortar]

not an array/list, but you can create a dict that way

english_num = {
  1: "one",
  2: "two",
  ...
}

[half lotus]

Yeah... https://www.php.net/manual/en/language.types.array.php

An array in PHP is actually an ordered map.

I suppose the name "array" fits if you think of it as an associative array, which is actually a term sometimes used for a dictionary or map.

[lapis zenith]

I see. So the python equivalent is really just the dict()

[half lotus]

Yes

[bleak dust]

Any resources for time series forecasting with machine learning

[unborn mauve]

hi guys

import pandas as pd
from timestampdirectory import  createdir
import numpy as np
print("-------------------------------------------------------")
print("Output.csv FILE")
print("-------------------------------------------------------")
df = pd.read_csv(r"D:\GIT-files\Automate-Stats\SVN_sample_files\sample_svn_input.txt", sep = '|')
df.columns = ['groups']
df['New Columns'] = df['groups'].apply(lambda x : x.split('=')[0])
df['groups'] = df['groups'].apply(lambda x : ' '.join(x.split('=')[1:]))
df['groups'] = df['groups'].apply(lambda x : x.split(','))

df = df.explode('groups')
df.rename(columns = {'groups':'users', 'New Columns':'Groups'}, inplace = True)
df["users"] = df["users"].str.strip()
print(df)
createdir():
    df.to_excel("D:\GIT-files\Automate-Stats\SVN_sample_files\sample_svn_input_update.xlsx" , index = False)```

this is my code and i want to export the df.to.excel on the folder where i createdir()

import shutil
import os


def createdir():
    now = datetime.datetime.today()
    nTime = now.strftime("%d-%m-%Y")
    source = 'D:\GIT-files\Automate-Stats\SVN_sample_files\svnfiles'
    dest = os.path.join(source+nTime)
    if not os.path.exists(dest):
        os.makedirs(dest)
createdir()

this is the createdir() functions

how can i export the df.to.excel file on the directory that just i created above?

[ivory yacht]

A class itself takes up a fair amount of memory, but there's only one so that's constant and almost always irrelevant. The objects themselves are bigger than tuples definitely, but not too much bigger. It's not really a concern, more relevant is the code readability concerns.

[mossy laurel]

yo !

so I'm currently learning python, but I'm a relatively experienced programmer so shouldn't take too long

I want to use python to practice algorithm stuff and get better at leetcode

any suggestions on on courses or books I can read ?

[spring jasper]

so are you trying to learn syntax and python idioms or the algorithms

if you are comfortable with python, i would suggest plain ol wiki and trying algo and ds implementations to start

[mossy laurel]

well I wanted something to follow up after I got the syntax stuff down

I was actually doing some searching

and this course seems like a decent follow up

https://www.udacity.com/course/data-structures-and-algorithms-in-python--ud513

[spiral raptor]

@mossy laurel, I prefer books over courses, but that's just me
for that reason, I'd recommend a book on algorithms and data structures in Python

[mossy laurel]

got anything in mind ?

[spiral raptor]

Yes. May I dm you?

[mossy laurel]

yeah course

[lean walrus]

no, if u use __slots__ your instances can be smaller than tuple: ```py

import sys
class X: slots = ('name', 'age')
...
sys.getsizeof(('NAME', 123))
56
sys.getsizeof(X())
48

[haughty mountain]

does this measure the overall size? I'm very surprised how a class would ever beat a tuple

does tuple have number of elements per instance and the class has some global number of elements?

[lean walrus]

no, it measure only that instance, not all referenced objects

[haughty mountain]

the difference of 8 kinda suggests something like a size member

[lean walrus]

tuples is variable-size (and lists, strings, bytes and ints)
all user-defined classes has fixed size in memory (but you can use instance dictionary)

[lean walrus]

yes it is

[haughty mountain]

makes sense then, I'm used to languages where the size is a compile time thing, and there a tuple should never be worse than the equivalent class

tuples aren't dumb enough types in python

[lean walrus]

you can implement your tuples of fixed size, it will save 8 bytes per instance

[haughty mountain]

I guess the dict is moved to the class and away from the instance if you use slots?

[lean walrus]

__slots__ creates several descriptors for your class, which returns reference by some offset in your object

[haughty mountain]

it's still dict based at some level, right?

[lean walrus]

if you use slots without __dict__ entry, your object will have no instance dictionary
if you do __slots__ = ('__dict__',) your object will have instance dict

[haughty mountain]

even if the value might be an offset

[lean walrus]

no

[haughty mountain]

how do you map the property name then?

I would have expected a per class dict from string to offset or whatever, anything else feels too much magic for a dynamic language

[lean walrus]

for example, __slots__ = ('a', 'b')
it creates two descriptors for attributes a and b
when you do x.a descriptor X.a will extract reference from your object by some offset (i think, 32): *(PyObject**)((void*)obj + 32)
its faster that dict lookup, and it needs only 8 bytes per reference

[haughty mountain]

there is no mapping with e.g. pair ('a', <offset>)?

[lean walrus]

no, every descriptor remembers its own offset at class creation time

>>> class X: __slots__ = ('a', 'b')
...
>>> X.a
<member 'a' of 'X' objects>
>>> X.b
<member 'b' of 'X' objects>

[pale locust]

.

[haughty mountain]

I'm still confused about what handles the mapping. When parsing X.a something must know what the 'a' and 'b' corresponds to, no?

Surely there is some lookup going on?

[lean walrus]

first it looks into class namespace to find descriptors
if there no descriptor for that attribute, it looks into instance dict

[haughty mountain]

that's why I asked if the dict kinda moves into the class from the instance

[lean walrus]

and if there no entry in instance dict, it looks into class namespace again and return value

[lean walrus]

yes, you're right
i misunderstood your question a little

[haughty mountain]

ok, cool

I was scratching my head of how things could possibly work without some mapping

it can in compiled languages, but basically only then I think

[lean walrus]

!e funny ```py

class X:
dict = ...

x = X()
x.a = 5
print(x.a)
print(x.dict)
x.dict = 123
print(x.dict)
x.b = 42
print(x.b)

[halcyon plank]

@lean walrus :white_check_mark: Your eval job has completed with return code 0.

001 | 5
002 | Ellipsis
003 | 123
004 | 42

[lean walrus]

instances have .__dict__, but you cant access it

[haughty mountain]

I guess the main reason I was asking was because this can be an advantage for a tuple, index vs string lookup

even though it's a loss in terms of memory

[lean walrus]

!e also funny, thats a simple namespace object ```py
class X(dict): pass

def new_X() -> X:
x = X()
x.dict = x
return x

x = new_X()
x.a = 7
x.b = 42
print(x)
print(x['a'])
print(x['b'])
assert x is x.dict

[halcyon plank]

@lean walrus :white_check_mark: Your eval job has completed with return code 0.

001 | {'a': 7, 'b': 42}
002 | 7
003 | 42

[lean walrus]

>py -m timeit -s "a=type('',(),dict(__slots__=('a','b')))();a.a=1;a.b=2;print(1)" a.a
10000000 loops, best of 5: 23.2 nsec per loop

>py -m timeit -s a=(1,2) a[1]
10000000 loops, best of 5: 24.4 nsec per loop

[halcyon plank]

Missing required argument

code

[lean walrus]

!timeit

a=type('',(),dict(__slots__=('a','b')))();a.a=1;a.b=2;print(1)
``` ```py
a.a

[halcyon plank]

@lean walrus :white_check_mark: Your timeit job has completed with return code 0.

5000000 loops, best of 5: 50.7 nsec per loop

[lean walrus]

!timeit

a=(1,2)
``` ```py
a[1]

[halcyon plank]

@lean walrus :white_check_mark: Your timeit job has completed with return code 0.

5000000 loops, best of 5: 42.6 nsec per loop

[tacit nova]

https://leetcode.com/problems/word-break/ i need to solve this question using Trie, are there any built-in Trie in Python, or do you have to import it ? or you have to create it yourself

[stuck flume]

public boolean isPalindrome(String s) {
        s = s.toLowerCase();
        s = s.replaceAll("[^a-z0-9]", "");
        int front = 0;
        int back = s.length() - 1;
        while (front <= back) {
            if (s.charAt(front) != s.charAt(back)) {
                return false;
            } else {
                front++;
                back--;
            }
        }
        return true;
    }

the code wirtten above is in java but i'm a bit confused on what the time complexity is — is it theta(n)?

[agile sundial]

yes

[full sonnet]

Is there a way to heapify based on some function input for the heapq library but have the heap itself be based on the inputs to that function? (sort of like sort takes functions with two parameters)
I.e. say I have an array
[[1, 5], [1, 3], [1, 9]]
I want to heapify it based on the sums, but retain the pairs.
So after heapifying it should be
[[1, 3], [1, 5], [1, 9]] and not [4, 6, 10]

What I have so far

import heapq
class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        sums = [x + y for x in nums1 for y in nums2]
        heapq.heapify(sums)
        indices = [0 for _ in range(k)]
        return [heapq.heappop(sums) for _ in indices]

[agile sundial]

according to the docs, you would need to make something to store both the key and actual value, something like (x + y, (x, y)) maybe. then you'd put that in the heap

[full sonnet]

Ah cool thanks

[tired wadi]

Your runtime is right, but be wary that replaceAll() has an implicit runtime impact too. It's O(n) itself so while your code is asymptoticaly O(n), your code is actually more like O(2n). So if you're measuring code performance at all... that maybe a hidden bottleneck. Just food for thought.

[stuck flume]

oh wow i didnt know that, thanks!

[burnt trellis]

how can i make python print/return whole numbers? if i have a number thats way too big it just puts the E on the back of it with some amount of zeros that follow ```py
3.201599999999999763641996518293009188482756144367158412933349609375E-7

i want the whole number, i tried with the decimal lib but it still doesnt print the whole thing for most cases

any ideas ?

[shut breach]

this channel is about algorithms and data structures, but you can open your own help channel from #❓｜how-to-get-help

[burnt trellis]

well okay :/

mb

[proud ferry]

Dn if you got an answer, but is that exaple helpful = print ('%.2f' %arr8 [1]). you put your value instead of arr8[1]

[drowsy solstice]

any recommend for learn DFS and/or BFS in python?

[shut breach]

there are some learning resources in the pins

[slender sandal]

You could use fractions.Fraction(that_number) perhaps

fractions is a module in the standard library

[slender sandal]

You need to print or call str on that because it returns a fractions.Fraction object (which I think can handle math operations done upon it)

[shut breach]

please dont bring the off-topic conversation back here after I already told them to take it elsewhere

[slender sandal]

What

[shut breach]

^

[slender sandal]

Well okay

[fiery cosmos]

I'm sure a lot of people here are experienced with algorithms, i wanna ask what book would you recommend me to read?

[fallen zephyr]

I'm joining this question

[jolly mortar]

the pins in this channel have some resources

clrs is also commonly recommended

i started with algorithms illuminated

(and by started with i mean i was too lazy to do anything else after that)

[fiery cosmos]

Thanks :) @jolly mortar

[haughty mountain]

kinda depends on the regex replace implementation, but I suppose for any sane engine that should be linear, but having regex in general makes is harder to reason about these things

e.g. there are common regex implementations that can have exponential behavior because of their implementation

[abstract turtle]

any sites recommendation for learning python ?

[slender sandal]

!resources

[halcyon plank]

Resources

The Resources page on our website contains a list of hand-selected learning resources that we regularly recommend to both beginners and experts.

[abstract turtle]

t.y

[burnt trellis]

thanks

[mossy laurel]

wow impressive

[zenith wasp]

Is there a way to do an n-dimensional cardinal product? tl;dr I have a bunch of numbers (e.g. 0, 1, 2, 3 and 4, 8, 12) and I want every possible combination as sum. How would I do this if there's a variable number of lists?

[shut breach]

!d itertools.product

[halcyon plank]

itertools.product

itertools.product(*iterables, repeat=1)```
Cartesian product of input iterables.

Roughly equivalent to nested for-loops in a generator expression. For example, `product(A, B)` returns the same as `((x,y) for x in A for y in B)`.

The nested loops cycle like an odometer with the rightmost element advancing on every iteration. This pattern creates a lexicographic ordering so that if the input’s iterables are sorted, the product tuples are emitted in sorted order.

To compute the product of an iterable with itself, specify the number of repetitions with the optional *repeat* keyword argument. For example, `product(A, repeat=4)` means the same as `product(A, A, A, A)`.

[shut breach]

that takes multiple iterables, is that what you mean?

@zenith wasp

[tacit nova]

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
heapq.heappush(heap, 9)

stdout : [1, 5, 2, 9]

why is the stdout not sorted like this [1,2,5,9] ?
my guess, heapq will put that one smallest element at the front, but it doesn't sort the remaining array right ?

[agile sundial]

heaps aren't sorted

this isn't a heapq thing, that's how heaps work

[zenith wasp]

I was moreso thinking of an algorithm, as itertools.product also uses a lot more memory as it creates tuples instead of summing them

[shut breach]

it generates them lazily though, so you could sum as you go

[zenith wasp]

I see

[shut breach]

any algorithm would have to do essentially the same thing

[zenith wasp]

I guess I'll look into the impl then

[shut breach]

unless it short-circuited duplicate sums with DP

(assuming you dont want duplicate sums)

[zenith wasp]

Duplicates luckily won't appear :)

[tacit nova]

cool, thank you

[keen hearth]

The ordering of the numbers in the heap will satisfy the min-heap property, which is that the number at index i will be smaller than (or equal to) the numbers at indexes 2*i + 1 and 2*i + 2.

Which means by induction the number at index 0 will be the smallest.

But not necessarily that the rest of the numbers will be in sorted order.

Although if you did sort the array, then it would satisfy the heap property. But its less expensive to heapify the array than to sort it (in theory).

It's also more efficient to add all the numbers to the array (in any order) then call heapq.heapify on the array, rather than pushing the numbers onto the heap one by one.

This lecture talks about heaps: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/lecture-8-binary-heaps/

[final vortex]

I can't find the six error codes can someone help

[agile sundial]

did you mean to do min_idx == step on line 4, or min_idx = step

[final vortex]

oh ok

I cannot find the rest of the errors

[agile sundial]

does it say any of the errors

[final vortex]

hold on

  
    for step in size:
        min_idx = step

        for i in range(step + 1, size + 1):

          if array[i] < array[min_idx]:
              min_idx = 1

        (array[step], array[min_idx])= (array[min_idx],array[step])

data = -2, 45, 0, 11, -9
print('Original Array:'+ data)
size = len(data)
selectionSort(data, size, step)
print('Sorted Array in Ascending Order:'+ data)```

[fiery cosmos]

can someone help me try to understand the master's theorem and examples?

what i understand so far is that it is a guidebook for how to find the time complexity of recurrences (functions that operate recursively)

[haughty mountain]

yes, iirc there are three very different regions

those are your 1, 2 and 3 there

[fiery cosmos]

where does the epsilon value come from?

[haughty mountain]

in your recurrence there are some important parts

T(n) = a T(n/b) + f(n)
       -     -    ----
       A     B      C

A: how many problems do I split into
B: how much smaller is the new subproblem
C: how much work do I need to do to split into subproblems/combine subproblem results

depending on how these relate to each other, the behavior will vary a lot

it turns out that there are 3 different regions

[haughty mountain]

so it turns out that c_critical = log_b a is a very critical number

[vital inlet]

how can i use some dictionary keys and that dictionary is in a list ?

[haughty mountain]

if your function f(n) = n^c then if c < c_critical the work to split/combine problems is cheap, and solving the subproblems is expensive

if c > c_critical then the situation is the reverse, splitting/combining is expensive compared to solving the subproblems

if c ≈ c_critical then both parts are comparatively expensive

[haughty mountain]

the epsilon is basically just there to make things behave as > and < I think

[fiery cosmos]

thanks algmyr i'm saving all of this thank you so much this will definitely help me to understand

[haughty mountain]

rather then >= and <=

something like merge sort falls into category 2

merging the results is comparatively expensive to solving the subproblems (in fact, they are pretty much equally expensive)

[fiery cosmos]

what is big O of mergesort?

[haughty mountain]

O(n log n)

[fiery cosmos]

ok that's what I thought. so it is then big theta of the same thing?

[haughty mountain]

the recurrence for it would be

T(n) = 2 T(n/2) + n

you split things into two equal parts, and you need to do n work to merge the results

in this case a = b = 2

so log_b(a) = 1

[fiery cosmos]

right i just plugged that into wolfram

so something to the 1th power is itself

?

1st power*

[haughty mountain]

x^1 = x yes

quicksort in the optimal case where it split things in half has the same recurrence as mergesort

it just does all the work when splitting the problem, while mergesort does all the work when joining problem results

are you familiar with quickselect?

[fiery cosmos]

not yet, no

[haughty mountain]

quicksort?

[fiery cosmos]

no the book has only covered selectionsort

before you go on

could you explain their explanation? i'll screenshot

i'll get a photo rather

did you learn from the intro to algorithms book by CLRS?

i don't understand their statement "intuitively, the larger of the two functions determines the solution to the recurrence."

[haughty mountain]

no, I have some algorithm book, but I've hardly read it

[fiery cosmos]

ok

[haughty mountain]

the intuitive part I think is just about which of the two terms dominates in
T(n) = a T(n/b) + f(n)

[fiery cosmos]

ah makes sense

[haughty mountain]

if c < c_critical then I think you can basically ignore the second term

T(n) = a T(n/b)

if c > c_critical you basically have T(n) = f(n)

[fiery cosmos]

is c_crit in this case analogous to the "for all n greater than n_0" in big O asymptotics?

(n naught)

[haughty mountain]

I wouldn't say so? It's more just the point where the system transitions from one behavior into another

[fiery cosmos]

ok

[haughty mountain]

As a dumb example: for x^a a = 1 is a critical point when it comes to the curvature ("shape", roughly) of the function

for a = 1 you have a straight line

for x < 1 you have something that curves downward

for x > 1 you have something that curves upward

so wrt curvature a = 1 is a critical point

[fiery cosmos]

makes sense

[haughty mountain]

I think this kind of thing is very common in all kinds of places, at one extreme you have some behavior, at the other extreme you have another behavior

at some point something happens

you also see this in physics with things like states of matter

solids transition into liquids

liquids into gas

[fiery cosmos]

hmm

[haughty mountain]

all at some critical temperatures

[fiery cosmos]

do you think its a fundamental property of the universe that is given rise to by the way things are constructed (of atoms)?

which i suppose all obey the laws of mathematics in some respect

[haughty mountain]

it's more just a property of systems that tend towards a stable state

when below the critical point you have some stable state

when above you have another

what happens in between?

if this kind of things interest you, this path continues into the study of dynamical systems

and chaos theory

[fiery cosmos]

oh it interests me for sure but i'm no mathematician. i think i have the capacity to but my life course has been plagued by a lot of apathy and i'm always two steps behind. still playing catchup at 33!!

if i can get this degree i'll be in way better shape.

its been tough trying to learn the discrete math while also studying this stuff and my calculus and algebra are pretty shit

math and sciences are the kind of thing you can't fall behind because once you do you're sort of forever playing catchup

[haughty mountain]

I think with higher maths it's important to understand the why and how

and not just the what

in early math much comes down to memorizing stuff

[fiery cosmos]

so with my lack of math intuition im oftentimes asking myself or my teacher "why isn't it some other way" and at some point it just becomes because thats the way we measured it or because thats the way the math works

[haughty mountain]

then you work towards proofs and reasoning your way to stuff

[fiery cosmos]

i'm great at reasoning but theres a certain amount of background knowledge you need for mathematics for example the notation and theory behind things

but thank god there are people like you willing to help me bc i could never learn this stuff straight from the book. i considered an implementation of selectionsort in python straight from the pseudocode in the book a major victory that took many iterations

[haughty mountain]

this is also why it's important to not only know the whats (theorems and results) but also to understand why they are true (the proofs and motivations)

the latter part is what can build intuition

[fiery cosmos]

i think some things though are just statements to make the math make sense but aren't intuitively or inherently true. for example saying a single integer is sorted. no, its not, it has no context and so couldn't possibly be in the correct or incorrect order, just as a single book on a shelf isn't sorted

[haughty mountain]

an empty list or a list with one element are inherently sorted though

it follows from what it means to be sorted

[fiery cosmos]

see i disagree

[haughty mountain]

do you agree with this definition?
a sequence a_1, a_2, ..., a_n is sorted in increasing order if for all i = 1, ..., n-1 it's true that a_i <= a_(i+1)

when you then restrict the n to be 1 (or even 0) you no longer have any pairs to compare, the statement is then said to be vacuously true (not so helpful wiki article https://en.wikipedia.org/wiki/Vacuous_truth)

you can kinda see this in python as well

all([]) == True

I guess it feels a bit weird at first

"all of my 0 items fulfill this property"

and this is true for any property

e.g.
"all the integers in my empty set are odd"
and
"all the integers in my empty set are even"
are both true

even though the properties are contradictory

I guess to come back to sorting:
if you claim that a list with 1 element is not sorted you kinda claim that there exist some pair of adjacent items that are in the wrong order

which is not true

[fiery cosmos]

ok fair enough. hey i have to leave, thank you so much

[half lotus]

I suppose this is in the context of a language like C. The really basic version of it is that static arrays have a size that must be some constant value known at compile time. On the other hand, dynamic arrays can use a variable as its size.

Alternatively, you may have been looking for this definition: static arrays have a fixed size while dynamic arrays can be resized.

[opal oriole]

Fixed length vs non-fixed length. The length does not need to known at compile time for either. Usually dynamic also implies that the length does not need to be known at compile time and it involves reallocating memory to grow or shrink the array. But the only thing that actually sets them apart in general is fixed length or not (if you are tracking the length in some way, do you ever change that value? (languages like Python track the length for you and handle reallocation, and you can get it with len(...))).

[jovial bay]

what is the best data structures/algorithms book to read to prepare for leetcoding? is Sedgwick's or Skiena's book better? should i just skip the books and start leetcoding?

[opal oriole]

In C arrays look something like pointer + length (could be a compile-time value), while a dynamic arrays look something like pointer + capacity + length.

[haughty mountain]

you don't need a capacity to have a dynamic array

pointer + length is enough

just grossly inefficient when you append a lot

[opal oriole]

There is always a capacity, implicit or not, the implicit one is just really slow as you mentioned.

[haughty mountain]

I mean, you could say that for a static array as well

capacity == size

[opal oriole]

And it's why it typically shows up as all 3 in C.

Yeah, but length is capacity in static arrays, same thing.

[haughty mountain]

and they can be the same for a dynamic array

it's just a terrible choice

[opal oriole]

It's whatever, it all depends on how you consider memory allocation to be a thing.

Depends on system too*

[haughty mountain]

at the end of the day a dynamic array is just an array that can grow/shrink in size

[opal oriole]

Yeah, how it looks in code typically was what I was trying to get across. In C.

[haughty mountain]

I guess this is a bit about abstraction levels, a stack is an abstract thing that can do X things, the implementation can vary

[opal oriole]

Yeah, also, in the world of math (CS), we have infinite memory, but on any real machine there is some capacity (often further split up by the OS / user's software). This is a pretty big difference that changes a lot, such as the need for an O(n) copy sometimes or never reallocating and just having a fixed capacity from the start.

[agile sundial]

there probably isn't one single yt video where you can learn data structures

i suggest mit open courseware

a lot of their lectures are on yt

[deft atlas]

max on a column-green in excel, openpyxl library . HELP

[keen hearth]

You'll probably get better responses by claiming a help channel: #❓｜how-to-get-help

[fiery cosmos]

Why do they only care about the highest n power and not the constant term while denoting the complexity. What if the constant was super big. Compared to what the n factors would ever contribute for practical purposes.

[vocal gorge]

Well, asymptotic complexity isn't for practical purposes, it's a computer science concept. 🙂

[fiery cosmos]

Like 10^50+n vs n^2

[agile sundial]

because a really big constant is irrelevant when n is infinitely large. as reptile says, it's not always the most practical measurement, it's more theoretical

[opal oriole]

It's about what happens when N becomes very large / math.

[fiery cosmos]

Yes. But why do they compare at the level of infinitely large n. When it doesn't really denote if it's a good algorithm or not. Don't we care about making good algorithms for real world?

[half lotus]

The goal is to analyse how the function grows as N becomes large. A constant doesn't affect the nature of the function's growth; just shifts it in a certain direction.

[agile sundial]

that's why it's not the only measurement we can use

[half lotus]

And more generally we drop lower order terms because the highest order term dominates the growth of the function

[opal oriole]

It can definitely give you a general feel for how it scales. But it's a starting point. A lot of processing happens on medium to small N and in those cases you are sort of using it as a sanity check to make sure it's not some ridiculous / unnecessarily bad complexity.

A lot of applications also revolve around 1 or a few algorithms and they are central to the performance, in those cases it's worth the extra effort to make sure it's fast and making sure it scales with N matters.

[stark stone]

is there a name for something similar Hamming distance or Levenshtein distance, but rather than substitutions or edit distance, it's more like "sort distance" ? like, the number of transpositions for two lists to become the same, for example

so [A, B, C] would be "one" in distance from [B, A, C]

and [B, A, D, C] would be "two" in distance from [A, B, C, D]

oh maybe it's just called "transposition distance"

and it looks like it's NP hard hah

[ionic locust]

are collections.deque (for queue as a data structure) and queue.Queue (for queues in threading) the main ways of implementing them in python?

[agile sundial]

implementing what

[hybrid dome]

Hi Pythonistas,
I am looking to connect with programmers who are starting to code and wish to solve algoexpert.io problems. If anyone wishes to collaborate and learn please do mention me in this chat guys. So we could connect at the weekends to solve the problems.

[proud sundial]

How I can print parenthesization of Matrix Chain Multiplication like that ?

[ionic locust]

implementing a queue

[vocal gorge]

Well, if you're implementing a queue, you'd, well, make one from scratch using a list as a circular buffer or something like that

but there aren't many builtin queues in Python's standard library, if that's what you mean. I think another one is asyncio-queue

[ionic locust]

Oh yeah I probably meant built-in queue

[ionic locust]

So it'd mainly be these two and asyncio-queue for in-built queues yeah?

[vocal gorge]

sure, I can't think of others offhand

[fiery cosmos]

Hello, what is the best resource to learn algos and adta structures

so far I'm don't know much, I only know Binary search and a few sorting algos like quicksort, bubble sort, insertion sort, mergesort

[shut breach]

there are some in the pins

[lyric crown]

Hi everyone

[zinc fern]

Pavel mavrin on yt

[tiny wolf]

Does anyone know how to create a math func which is between the values 25000 and 500000
and spans from 0.25 to 1

So based on an input of between 25000 and 500000 it spits out a number that is between 1/4 and 1

[runic tinsel]

it's so easy you can do it

i don't know how to hint though

consider it a hint

"there's nothing clever about it"

[tiny wolf]

I know but an still not getting an answer

[runic tinsel]

i'm all about giving the answer but can you try pls

(x − 25000) × 3 / 1900000 + 1/4

[halcyon plank]

Hey @paper yacht!

It looks like you tried to attach a Python file - please use a code-pasting service such as https://paste.pythondiscord.com

[paper yacht]

https://paste.pythondiscord.com/amekoriqit
this is a working program to find Max flow of a network using the Fork-Fulkerson algorithm in which one step is to go through various valid paths from source to sink and find the minimum edge value of that path...

they've used BreadthFirstSearch to consider the various paths but i dont get how just calling the same BFS function with same arguments again and again (as the while condition) is leading it to consider various paths from source to destination, can anyone help?

[fallen wing]

should you use try and except in algorithm questions? I feel guilty for using them for some reason

[runic tinsel]

it's fine

fine adjacent

like, many people will laugh, but they will be only slightly right

[keen hearth]

If you use any for loops, then you already are implicitly using exceptions for flow control.

The loop ends when an StopIteration exception is thrown when trying to get the next item.

[tranquil knoll]

I need help with solving a problem

I have a data structure like the following :

{
  id: 'e1',
  children: [
    {
      id: 'something',
      children: [
        {
          id: 'another1'
        }
      ]
    },
    {
      id: 'someid'
    },
    {
      id: 'sdaksjd'
    }
  ]
}

This can go on infinitely, so basically every JSON object represents an element, with an 'id' attribute and an optional 'children' attribute which is basically a list of further objects / elements that can in-turn contain elements

I want to make a function such that if I provide it with an 'id' it will give me all its childrens' ids in an array.

for-example getChildren ('something') should give me ['another1']

and getChildren('e1') should give me ['something', 'another1', 'someid', 'sdaksjd'] (order doesn't matter I just need all the childrens' ids.

What can I do ? I'm coding in TypeScript / JavaScript.

[steel fjord]

can you guys please tell me why my answer is not correct, the correct answer given by them is t

heres how i did it h i i o o u u u t t p p p a

the photo is from a friend, in this case, my answer would be p, which according to the quizz, is still wrong , it is supposed to be t apparentyl, did i do something wrong?

[coarse sluice]

@proud sundial https://www.geeksforgeeks.org/printing-brackets-matrix-chain-multiplication-problem/

@proud sundial There are probably better resources out there - but that will get you started.

[haughty mountain]

I can't see how the answer would be t. The two versions I can see being implemented here is either one where the limit is capped at 2 and if you enqueue at length 2 that triggers a dequeue first, this would give the answer you suggested p

The other one would be where you just don't respect a limit and just let the later dequeues read garbage (and say it's the user's fault for going past the set limit), my implementation of that gives a

!e

class QueueNoLimit:
  def __init__(self):
    self.start = 0
    self.end = 0
    self.data = [None, None]
  def enqueue(self, x):
    self.data[self.end%len(self.data)] = x
    self.end += 1
  def dequeue(self):
    if self.start == self.end:
      return None
    res = self.data[self.start%len(self.data)]
    self.start += 1
    return res
  def peek(self):
    if self.start == self.end:
      return None
    return self.data[self.start%len(self.data)]

class QueueWithLimit:
  def __init__(self):
    self.start = 0
    self.end = 0
    self.data = [None, None]
  def enqueue(self, x):
    if self.end - self.start >= 2:
      self.dequeue()
    self.data[self.end%len(self.data)] = x
    self.end += 1
  def dequeue(self):
    if self.start == self.end:
      return None
    res = self.data[self.start%len(self.data)]
    self.start += 1
    return res
  def peek(self):
    if self.start == self.end:
      return None
    return self.data[self.start%len(self.data)]

def do_operations(queue_type):
  q = queue_type()
  q.enqueue('h')
  q.enqueue('i')
  q.enqueue('o')
  q.enqueue('u')
  q.dequeue()
  q.enqueue('t')
  q.enqueue('p')
  q.dequeue()
  q.enqueue('a')
  return q.peek()


print('NoLimit:  ', do_operations(QueueNoLimit))
print('WithLimit:', do_operations(QueueWithLimit))

[halcyon plank]

@haughty mountain :white_check_mark: Your eval job has completed with return code 0.

001 | NoLimit:   a
002 | WithLimit: p

[half lotus]

I interpreted it as overriding the oldest element in the queue when the limit is reached.

In which case the answer would be a

Though in hindsight it might not make sense to implement it like that in practice

I would have to code it out to make sense of it

[haughty mountain]

Things will be overwritten, the question is just what happens to the current head and tail of the queue. Are elements dequeued to make things fit, or will the deque just end up with a size greater than the data array but with garbage data for the older elements

[austere sparrow]

observation: questionnaires with poor formatting tend to have vague/ambiguous/otherwise bad questions

[half lotus]

Yeah I was thinking it would dequeue to make space. So if it has A and B, then A would be dequeued and C enqueued. From there, if D is enqueued, then B is dequeued.

Okay that is basically what you did for QueueWithLimit. I just mixed up which element should be returned from the peek. Should be "p" oops

[arctic portal]

Hey people, I' trying to get a row from the dateframe and store it in a dictionary or another dateframe but it won't return or return some crap data.

It's actually only about this bit:
table[query_id] = df_temp[query_id].where(df_temp['day'] == datetime.strptime(date_value, "%Y-%m-%d").date())

table --> empty dict

df_temp --> df with 2 columns - first with name in variable "query_id" and second with date. From which I'm trying to get value stored in the column named with "query_id" along with "query_id" keyword.

I've been trying also converting date to string format and using dataframe instead of an empty dictionary

Thanks! (edytowane)

[rough lynx]

Question: there is no real difference between these two pieces of code, right?

# snippet 1
results = (n % j for j in my_list)

# snippet 2
my_lamba = lambda y: n % y
results = (my_lamba(j) for j in my_list)

Aside from assigning the lambda to a variable (which flake8 tells you is not valid with error E731 "do not assign a lambda expression, use a def"), these are entirely the same right?

[green light]

Whats the OO way of changing an underlying data structure for a field for optimization? Say we have python class Person: name: str age: int and we have a huge list of persons python [Person(name=randomname(), age=randomint()) for i in range(100000)] that we search often for a name. I want to change the backing datastructure of name to a dict (name -> instances for example) so that I can check if a name exists in the list in O(1).

I'd like to keep the Person instances intact as much as possible

My first intuition would be to create a collection class with an the dict i mention as an "index" with a .exists(name="blah") method that uses it

[half lotus]

The outputs are the same. I guess there would be a performance hit for calling a function, but you'd have to benchmark it if you're concerned about that.

[green light]

performance would be the same because the generator isnt consumed 😛

[half lotus]

Well, when it is consumed

[rough lynx]

It's part of my crazy over-engineered performance benchmark thing
It's still a WIP so I haven't run it yet, just been writing out anything that could possible make a performance impact
Guess I'll try to report back about it

[half lotus]

I want to change the backing datastructure of name to a dict
I don't understand the way you're explaining this. If you want to change the backing data structure to a dict, then what is its current backing data structure? The way classes work internally is that there is a dictionary which maps attribute names to values, but that doesn't seem to be what you meant.

If you want to find a Person corresponding to a name in O(1) then use a dictionary instead of a list of persons.

I am not following why it needs to be more complicated than that or how you want OOP to play into it

[green light]

at the moment if i have a list of persons

i have to do python for person in personlist: if person.name == name: return ture return false

if the backing structure of the names was a dict or set i could just return name in person_name_set in O(1)

so whats the OO way of having a list of persons but the ability to search for a name existing in O(1)

[fiery cosmos]

The idea I believe is to have a dict where the keys are name strings and the values are Person objects (so some data is duplicated) but looking up a name and getting the associated person object is O(1)

[green light]

So theres no way around a collection class?

[half lotus]

You want to emulate a list interface but with an additional method to lookup by name in constant time?

[green light]

class PersonCollection:
  people: List[Person]
  index: dict(str, List[Person])
  
  ... complicated logic to keep the index up to date...

  def exists(self, name):
    return name in index

[half lotus]

What's the justification for keeping a list around? Or for emulating a list interface?

[green light]

for other stuff

the idea is we have a list of people. We use it for general things but search for names often

to the point we want performance out of searching names while retain other functionality

[half lotus]

So switching to a dict is not an option? Cause trying to keep a list around makes this more complicated

[austere sparrow]

If you want to iterate over the people, you can do

def people(self) -> Iterator[Person]:
    return itertools.chain.from_iterable(self._index.values())

why do you need a list otherwise?

[green light]

to do other stuff....

like access the age

[austere sparrow]

for example?

[green light]

Say twitter

they dont do for account in accounts: if name == blah: get tweets

they have a backing strtucture for tweets to get them quicker by account

but the accoutn class is just gonna be account: name, tweets, etc...

[austere sparrow]

Right, but you can do e.g.:

person = people_collection.get(name="foo")
print(person.name)

[half lotus]

Can you give an example of code that demonstrates something that you need and can do with a list, but that you could not if it was a dict instead?

[austere sparrow]

and you don't need a list for this

[green light]

what would be the key for your dict

the person objects?

i need the instances

[austere sparrow]

What we're saying is that you can do

class PersonCollection:
  index: dict[str, List[Person]]
  ...

[rough lynx]

If you're trying to use integer indexing for accessing elements, you can use enumeration on a dictionary

for i, (k, v) in enumerate(example_dict.items()):
  # do stuff with i, k, and v

Where i is the index, k is the key, and v is the value at that key

[half lotus]

The name is the key. The Person instance is the value

[austere sparrow]

yep

[half lotus]

Or I guess a list of instances

[green light]

but then the dev using my lib has a weird api

im not passing around a that dict

and if i want to optimize something else

im out of luck

it doesnt scale

[austere sparrow]

^

[green light]

thats O(n) tho

[fiery cosmos]

It might look like this more fleshed out (sorry, no types )```py

class PeopleCollection:
def init(self):
self.people = {}

def add_person(self, person):
    self.people[person.name] = person

def get_person(self, name):
    return self.people.get(name)

def person_exists(self, name):
    return name in self.people

jim = Person("jim", 44)
people = PeopleCollection()
people.add_person(jim)

print(people.get_person("jim").age) # 44```

[austere sparrow]

Do you want to access the person by their numerical index?

or why do you need a list?

[green light]

i was just giving existance as an example

it could be a set instead of dict since we3 just want true false

for the index

and we have the list to keep the rest of the account info...

[fiery cosmos]

the dict values hold the rest of the info like age, no (values, sorry)

[green light]

mhrmmmmmmmmm

its an option for one optimisation i guess

thanks for the help

but say we wanted to get # of people at certain ages also. Then we would need another index

[austere sparrow]

this might sound crazy, but what about an in-memory SQLite database 👀

[half lotus]

I feel like your describing a database with indexed columns

[rough lynx]

You can have a dict within a dict like

my_dict = {
  "adam": {
    "account": 1234567,
    ...
  }
}

and work with that
But yeah once you start getting into using account info, a db is the way to go

[green light]

yeah for this example a database solves this all immeditately

my real application is a list of Atoms in a molecule, we access it's coordinates in the system often, need to calculate nearest neighbors, etc...

but i'd like to keep the meta data of the atoms close by

we don't use a database for them

anyways, thanks all ill think on it

it would be nice to just have my list of classes but all the coordinates in a numpy array to do fast math

[rough lynx]

Since you're working with atoms in a molecule, where each atom can have one or more connections, you'd need to have those connections mapped out

[green light]

Yeah i was trying to simplify with my example to not have to explain everything

[mild night]

so for a project of mine I have an array of N-Dimensional points, I want to take the shape those points make (its not gunna be a pretty shape in any way shape of form) and get the boundary points for the shape, anyone know a method/algorithm to do so?

[bold pelican]

arr1 = []
arr2 = []
arr3 = []
for i in range(2):
n1 = int(input("Enter the ID: "))
n2 = input("Enter the Name: ")
n3 = int(input("Enter the salary: "))
arr1.append(n1)
arr2.append(n2)
arr3.append(n3)

dict = {"ID": arr1, "name": arr2, "salary": arr3}
print(dict)
del arr1[2]

dict["ID"]=arr1

print(dict)

could anyone kindly help

i want to remove a value from arr1 list in dictionary and i also want to remove its corresponding values in arr2 and arr3 lists

[haughty mountain]

are you talking about the convex hull of the points, or something else?

[mild night]

yeah ig thats the best aprox u can rlly get lol

[tender cape]

index=2 # index to delete for arr in dict.values() del arr[index]
dict.values() returns arr1, arr2 and arr3 i.e. it returns a list of values for all the keys present in the dict. So if you have an index that you want to delete from the list corresponding to all keys, this can be done.

[bold pelican]

based on my dictionary it del the whole arr list of akey if i do tht

a key*

[tender cape]

No. What the for loop equates to is
del arr1[2] del arr2[2] del arr3[2]

This does not delete the entire arrx lists from the keys. It deletes the element at index 2 in each of arr1, arr2 and arr3

[bold pelican]

oh ok lemme work on tht again

[austere sparrow]

I prefer to use foo.pop(2) instead of del foo[2]

because the del keyword is cursed: del foo, del foo[bar] and del foo.bar mean completely different things

and del foo should probably not have existed

[lament totem]

I don't think I have ever used del in my life expect like maybe once or twice in a jupyter notebook

[fervent saddle]

What about slice deletion?

[austere sparrow]

foo[1:6] = ()

[covert stirrup]

im trying to do the guess number higher or lower

class Solution(object):
    def guessNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        data = []
        for i in range(1,n+1):
            data.append(i)
        def binarySearch(array, guess, low, high):
            
            while low <= high:
                mid = low + (high - low)//2
                if array[mid] == guess:
                    return guess 
                elif array[mid] < guess:
                    low = mid + 1
                else:
                    high = mid - 1
            return -1
        return binarySearch(data,guess,0,len(data)-1)
        ```

why in tf is this not working

[austere sparrow]

Can you show the task?

[covert stirrup]

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.

You call a pre-defined API int guess(int num), which returns three possible results:

-1: Your guess is higher than the number I picked (i.e. num > pick).
1: Your guess is lower than the number I picked (i.e. num < pick).
0: your guess is equal to the number I picked (i.e. num == pick).
Return the number that I picked.

so i found the mistake

guess

is not defined by anyone

but that still leaves me stuck

guess is not given? like

what do i do?

i thought the given value is there so i can like compare but its not accessible to me

oh fuck

ignore my stupidity

[left lynx]

Hey there! I'm new to this Discord so if this question is better appropriate somewhere else, don't hesitate to let me know! I tried my best to pick the right channel.

I've spent the last day or two trying to research how to create a class that when initiated, will save the object so that if you call a method to get an object by name, it will return the object with the initiated values from where it was first created. Here's an example of what I'm wanting with blatantly wrong code to give you a better hint on what I'm trying to figure out:

class Information():
    list = []
    def __init__(self, *args):
        self.name = ???name of the variable that called the class???
        self.list_values = []
        self.list_values.append(self.name)
        for value in args:
            self.list_values.append(value)
        self.list.append[self.list_values]
    def get_source(self, name_of_wanted_object):
        for list_values in self.list:
            if name_of_wanted_object is in list_values:
                return ???weakref of object that has already been created???
            else:
                return None
    def get_values(self):
        return self.list_values
a_variable = Information('value1', 'value2', 'value3')
start()
def start():
    get_previously_initiated_obect = Information.get_source('a_variable')
    print(get_previously_initiated_obect.name) #output: a_variable
    print(get_previously_initiated_object.get_values) #output: list of a_variable)

I put question marks around the parts I'm trying to figure out, but do note that the structure leading up to that point could be wrong. It should be readable enough though I think to understand what I'm trying to do. I really appreciate any help and your time! Really want to learn how to setup something like this.

[half lotus]

If it's a class attribute, then its name can be obtained using __set_name__. Otherwise, I don't believe it is possible. Even in the standard library, you can see typing.TypeVar requires the name to be passed as a string e.g. T = TypeVar('T').

[covert stirrup]

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        while len(nums1) != m:
            nums1.pop()
            

        while len(nums2) != n:
            nums2.pop()
             
        
        nums1 = nums1 + nums2 
        
        
        
        for i in range(n+m):
            for j in range(0, n+m - i - 1):
                if nums1[j] > nums1[j + 1]:
                    temp = nums1[j]
                    nums1[j] = nums1[j + 1]
                    nums1[j+1] = temp
        return nums1
        
        

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

can someone explain why this isnt workling

working

[haughty mountain]

why is it cursed? all those do the expected thing, right?

[haughty mountain]

wait, are you trying to do a bubble sort? why?

[covert stirrup]

because it needs it to be sorted

at the end

[haughty mountain]

you don't need to sort at all for this task

[covert stirrup]

i mean what else can i do im fairly new at this

i just wanna see if it works like this

but cant figure out why it is only printing nums1

like when i run it on pycharm

i get the correct answer

but here no

[covert thorn]

uhhh

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

[agile sundial]

you don't need to sort at all for this task

[haughty mountain]

you have two lists that are already sorted, can you make use of this

[covert stirrup]

no bro they arent

nums1 = [1, 2, 3, 0, 0, 0]
nums2 = [2,5,6]

when you make nums1 smaller

you need to merge nums1 and nums2

which means

it would be

[agile sundial]

sorted in non-decreasing order

[covert stirrup]

[1,2,3,2,5,6]

thats not sorted?

[agile sundial]

yes, you need to do something smarter than nums1 + nums2

[covert stirrup]

and whats that .extend()?

[agile sundial]

no, that's basically the same thing

[covert stirrup]

it has to fall under the same value nums1 thats why i did nums1 = nums1 + nums 2

but its not even adding on leetcode

[haughty mountain]

do note that they ask you to modify the first list, not return a new one

[covert stirrup]

thats what i did

i did nums1 = nums1 + nums2

same one?

[haughty mountain]

that creates a new list

[agile sundial]

that doesn't modify the list that was passed in

[covert stirrup]

ok then

nums1.extend(nums2)?

that just extends it

but anyways the output is still wrong on leetcode

[haughty mountain]

that would at least modify the first list

[covert stirrup]

thats what it needs to do

i keep getting [1,2,3] on leet code

and on pycharm

i get

[1, 2, 2, 3, 5, 6]

[haughty mountain]

get as what? the modified argument or the return value?

you shouldn't return anything

[covert stirrup]

the return value

i get that

[agile sundial]

you're supposed to modify the list in place

[covert stirrup]

.extend() does that

and even just changing it on pycharm gives me the correct value

ill find that issue later but whats going on now is when im running it on pycharm like this

nums1 = [1, 2, 3, 0, 0, 0]
nums2 = [2,5,6]
n = 3
m = 3

while len(nums1) != n:
    nums1.pop()

while len(nums2) != m:
    nums2.pop()

nums1 = nums1 + nums2



for i in range(n + m):
    for j in range(0, n + m - i - 1):
        if nums1[j] > nums1[j + 1]:
            temp = nums1[j]
            nums1[j] = nums1[j + 1]
            nums1[j + 1] = temp

print(nums1)

i get the correct value

and when i put it it in leetcode

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        while len(nums1) != m:
            nums1.pop()
            

        while len(nums2) != n:
            nums2.pop()
             
        
        nums1 = nums1 + nums2 
        
        
        
        for i in range(n+m):
            for j in range(0, n+m - i - 1):
                if nums1[j] > nums1[j + 1]:
                    temp = nums1[j]
                    nums1[j] = nums1[j + 1]
                    nums1[j+1] = temp
        return nums1
        
        

i get [1,2,3]

ill change the nums1 = nums1 + nums2 thing dw about that

[agile sundial]

that's technically different behavior, because the function creates a local variable

you should use a function in your local testing

[haughty mountain]

that's why you get [1,2,3]

you don't modify the argument

other than the popping in the beginning

[covert stirrup]

what?

i did this rn

nums1 = [1, 2, 3, 0, 0, 0]
nums2 = [2,5,6]
n = 3
m = 3
def sort(nums1, n, nums2, m):
    while len(nums1) != n:
        nums1.pop()

    while len(nums2) != m:
        nums2.pop()

    nums1 = nums1 + nums2



    for i in range(n + m):
        for j in range(0, n + m - i - 1):
            if nums1[j] > nums1[j + 1]:
                temp = nums1[j]
                nums1[j] = nums1[j + 1]
                nums1[j + 1] = temp

    return(nums1)
print(sort(nums1,n,nums2,m))
``` and got the same thing

[agile sundial]

because you're using the return value now

[covert stirrup]

no

got the correct answer

[agile sundial]

yes

[covert stirrup]

[1, 2, 2, 3, 5, 6]

[agile sundial]

you're using the return value. you print out the result of the function

[covert stirrup]

yeah?

wait what?

wait is that not whats supposed to happen?

[haughty mountain]

the expected usage is

sort(a, b)
print(a)  # merged result

[agile sundial]

The final sorted array should not be returned by the function, but instead be stored inside the array nums1.

[haughty mountain]

yes, the input and output format is ridiculous, but that's what they ask for

[covert stirrup]

wait lol mb

what exactly should I change?

[haughty mountain]

if you use extend or += things will work, albeit way slower than needed

this thing can be solved in O(n + m)

[covert stirrup]

yeah ill try to fix that one in a sec but just trying to fix the input and output thing

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        while len(nums1) != m:
            nums1.pop()
            

        while len(nums2) != n:
            nums2.pop()
             
        
        nums1 = nums1 + nums2 
        
        
        
        for i in range(n+m):
            for j in range(0, n+m - i - 1):
                if nums1[j] > nums1[j + 1]:
                    temp = nums1[j]
                    nums1[j] = nums1[j + 1]
                    nums1[j+1] = temp
        
       ```

just trying to get this to output the correct thing

[haughty mountain]

we've said what you could do to solve it multiple times

this creates a new list named nums1, don't do that

nums1 = nums1 + nums2

[covert stirrup]

instead what should I do?

[haughty mountain]

as said earlier, use extend or +=

[covert stirrup]

ok wait is the += faster?

it has a runtime of 66ms rn which is kind of slow

[haughty mountain]

they do the same thing

[agile sundial]

that's not the += fault lol. it's the god awful sorting algorithm you're using

[covert stirrup]

oh ok

is bubble too slow?

[haughty mountain]

your runtime is because of the sorting

you don't even need to sort

you just need to merge sorted lists

[covert stirrup]

if you just merge it doesnt stay sorted anymore

if i merge nums1 and nums2

you get

[agile sundial]

that's why you need to think a little bit

[covert stirrup]

[1,2,3,2,5,6]

[haughty mountain]

you're talking about concatenating

you can merge things in smarter ways

[covert stirrup]

how can you link them together so that you get [1,2,2,3,5,6]

without sorting

[haughty mountain]

make use of the fact that the lists are already sorted

[agile sundial]

well, that's what the problem is asking isn't it

[haughty mountain]

if I gave you the lists

[1, 3]
[2, 4]
```can you think of some way to merge these into a big sorted list without calling/using some sort algo?

e.g. what should the first element in the sorted output be? and how easily can you determine that?

[covert stirrup]

can you iterate through it?

like using a loop?

isnt that still long?

[haughty mountain]

why do you need to iterate through it?

[kind solstice]

hello help me

[covert stirrup]

like you can set two different variables to be a and b and set them to 0

[kind solstice]

Traceback (most recent call last):
File "C:\Users\lands\Desktop\OpenCV-Game-Bot-main\gui.py", line 7, in <module>
from cv2 import cv2
ImportError: Bindings generation error. Submodule name should always start with a parent module name. Parent name: cv2.cv2. Submodule name: cv2

[covert stirrup]

then say if the l[0] is smaller than l2[0] then it goes first

and it keeps doing that?

is there an easier way?

[haughty mountain]

not relevant for this channel, ask in #python-discussion or similar

[agile sundial]

that's the idea, yes

[covert stirrup]

thats it?

is that going to still take a good amount of time?

[haughty mountain]

yes, you're looking for the smallest element over and over

[agile sundial]

have you learned about big O notation?

[kind solstice]

okey

[covert stirrup]

ive heard of it a lot time complexity or something

[agile sundial]

if not, you can just think about what your code would be doing with this solution compared to the other one

[covert stirrup]

and how some are like O(n^2)

can i learn it quickly?

[haughty mountain]

e.g. your bubble sort would be O((n+m)²)

[agile sundial]

m?

[covert stirrup]

bruh lol

isnt that like ass ass

wait how did you calculate that?

[agile sundial]

yes, compared to what you could do for this problem, it's pretty bad

[haughty mountain]

bubble sort goes over the whole list once for every element in the list, the list length is n+m

hence (n+m)²

[agile sundial]

even with the optimization where you don't check the already sorted elements, it's still quadratic, because the number of operations for each iterations is (n + m) + (n + m - 1) + (n + m - 2) + ...

[covert stirrup]

oh ok makes sense

[haughty mountain]

the smarter merging is O(n + m)

also, obligatory fun and not at all obvious O(n + m) solution

nums1[:] = sorted(nums1[:m] + nums2)

sorted is linear time here because timsort is fun for partially sorted data

[covert stirrup]

oh damn

that looks so much nicer

[haughty mountain]

though I say ignore that code

it's very non-obvious why it's linear time unless you know what the internal sort in python is doing

writing the same kind of thing in other languages would usually be O((n + m) log(n + m))

[covert stirrup]

what do you suggest i learning to get to know stuff like that

[haughty mountain]

for the task at hand, look at how merge sort works

what you are writing here is the merge part of merge sort

[left lynx]

Hey, thanks so much for your response! That makes sense. And do you have any insight to the second set of ???s I placed in there - is something like that possible? The line that says return ???weakref of object that has already been created??? . I really would like to get a previous object that was created. Hmm - maybe you could find the values in the list class list, if they are created - not sure on how that works, and call init with the values pulled from that from within get_source?

[half lotus]

I think you want something like the following: ```py
from weakref import WeakValueDictionary

class Information:
_instances = WeakValueDictionary()

def __init__(self, name):
    self._instances[name] = self
    ...

@classmethod
def get_source(cls, name):
    # Return the instance if it exists; otherwise return None.
    return cls._instances.get(name, None)

[pure ferry]

Hello, I am starting to study data structures for my upcoming interviews, any tips and tricks ?

Or a study partner would be great

[left lynx]

@half lotus that's amazing! Thanks so much! That's so cool.

Just implemented it myself with different values and such and worked perfect, thanks to you :D.

[half lotus]

You're welcome

[fiery zenith]

Hey

I could noot understand big o

[austere sparrow]

del foo doesn't do anything meaningful

well, it makes the foo variable inaccessible, but it doesn't mean much

and it's confusing to beginners