algos-and-data-structs

[quiet jay]

above and beyond

[lean dome]

word

🙂

hopefully it helps show the algorithm, though - we keep following one path as deep as we can, and once we hit a "dead end" (nothing new is reachable), we backtrack until we find a new path to explore.

[quiet jay]

yup

so for BFS

you start at b

neighbours are c, f, a

so b, c, f, a

all new neighbours are d and e

[quiet jay]

b,f,d,c,e,a

this correct?

[lean dome]

yep, that would be a valid BFS order.

[quiet jay]

sweet as

thanks again

[lean dome]

that's B, followed by everything 1 away from B, followed by everything 2 away

the invariant that has to hold for BFS is that you can't visit anything 2 away until you've visited everything 1 away, can't visit anything 3 away until you've visited everything 2 away, etc.

[jolly mortar]

MSTs can be found with prims and kruskals algorithms
the former starts with an arbitrary vertex as the root and greedily adds edges to it
the latter builds up multiple clusters simultaneously and merges them gradually to a single tree

[fiery cosmos]

can someone explain how this diagram shows that this SLL is both a Stack and a Queue ? if i could get tagged that would be wonderful!

[keen hearth]

Hello 🙂

Well because you have a pointer to the head of the list, it can be used as a stack. You can add and remove elements from the front of the list.

Because you have a pointer to the last node of the list, it can be used as a queue. You can append elements to the end of the list, and pop them from the front.

[fiery cosmos]

ahhhhhhhh that makes sense!

[keen hearth]

Note that given just a pointer to the last node, you wouldn't be able to use it as a stack. Because removing an element from the end of the list would require updating that pointer to point to the second last element, which would require backwards links.

[fiery cosmos]

so just to confirm from our diagram, because we have both a pointer P at the start of our SLL and a R at the end of our SLL this shows that this SLL is representing both the principles of a stack and a queue ?

[lean dome]

This singly linked list can support:
stack push: add a new node at the start of the list
stack pop: remove the node at the front of the list
enqueue: add a new node at the end of the list
dequeue: remove the node at the front of the list

Because you can add and remove from the same end, you can use it to represent a stack (that's enough to implement push and pop).
Because you can add at one end and remove from the other, you can use it to represent a queue (that's enough to implement enqueue and dequeue)

[keen hearth]

Yeah. Although it's more like it simply provides all the things necessary to use it as a (efficient) stack or queue.

[fiery cosmos]

awesome thanks for your detailed response

[fiery cosmos]

yeah i have written down in my notes that it implements both the principles from both a stack and a queue 👍

[lean dome]

It's not that it "implements the principles" of either of those data types. It's that it is sufficiently flexible to allow you to implement those data types using it.

A singly linked list is neither a stack nor a queue, but if you stick to one particular usage pattern (only ever adding elements to the front and removing elements from the front), you can use it as a stack. If you stick to a different usage pattern (only ever adding elements to the end, and only ever removing elements from the front), you can use it as a queue.

[fiery cosmos]

ahhhhhhh interesting thanks for explaining!

[keen hearth]

Hmm, make sure that you understand why this is the case though, rather than simply making a note of this particular example.

To further what Gobblegeek was saying, it's common in the study of algorithms to make a distinction between an "abstract data type" and a "data structure".

[fiery cosmos]

for this particular question it is because off the links that have been created at the start of the SLL and at the end

[quiet jay]

can someone explain the answer to this

I feel like im making a dumb mistake

have tried this about 3 times

pivot is 4

[vocal gorge]

what median-of-3 do you get here?

[quiet jay]

4

[vocal gorge]

Ah, that's right. I think the problem here, rather, is that you for some reason are reordering the elements

like, the elements lower than 4 are 2,3,1 in that order - you wrote 3,2,1.

[quiet jay]

I don't get it

oh

this is using a quicksort partition

[quiet jay]

my bad

[fiery cosmos]

what would be the steps to solve this problem? i understand the concept of leaf nodes but do not understand how to draw out the binary search tree? dependent on the height

[quiet jay]

draw it

least nodes

of height 4

[fiery cosmos]

once i can draw out the binary search tree dependent on the height i should then be able to count the number of least nodes

[quiet jay]

least nodes means all to the left or all to the right of the root. do you understand this

[fiery cosmos]

*LEAF sorry

not least

[quiet jay]

you understand how binary trees

you have the root

left and right

[fiery cosmos]

yup

[quiet jay]

can you draw a tree of height 4 where each node only has a right

[vocal gorge]

not necessarily, no. It just means there's no nodes with two children (since that would increase the number of leaves).

[fiery cosmos]

i did this but did not think it was right lol

[quiet jay]

ok I have been corrected

[fiery cosmos]

i am certain this is not right?

[vocal gorge]

This is a tree of depth 4. It has one leaf.

[fiery cosmos]

they start from 0 right?

[vocal gorge]

if you count depth from 0, then you need 1 more node, but the answer is still the same

[fiery cosmos]

so my workings were right lol

[vocal gorge]

the answer to "what's the least number of leaves a tree of depth k can have" is always 1, for any k.... above zero, I guess.

[fiery cosmos]

ahhhhhhhhhh

[vocal gorge]

said tree would just be a chain

[quiet jay]

@vocal gorge do you know how to use mo3 quicksort partition

[fiery cosmos]

so this kind of question would always be 1?

[vocal gorge]

depending on how you define "tree" and "depth", you could maybe say that a 0-depth tree can have 0 leaves. (by having no nodes at all)

but for any higher depth, yes.

[fiery cosmos]

fantastic thank you!

[alpine lava]

I want to set the default value as self.root, but it's showing error. is there any other alternative to achieve this?

can anyone help me with this?

[grizzled schooner]

you can't access self in the method declaration because self is passed as a parameter so it can't be accessed by the other arguments

you could fix it by setting node=None and then have a check in the function like

if node is None:
  node = self.root

[alpine lava]

noice, thanks man, appreciated

[grizzled schooner]

np :)

[twilit flower]

Hey guys, I made a website containing various DSAs

https://siddhesh-agarwal.github.io/Python-Algorithms

Do check it out

Would love suggestions for other DSAs and improvements int the exxisting one

[turbid abyss]

Anyone here know any website where we can get the Time complexities by entering the code?

[vocal gorge]

I would be surprised if anything like that exists - you're basically talking about writing a program to understand the behaviour of other programs from source code enough to, at least, determine asymptotic complexity

[turbid abyss]

yes exactly that!

I just wanted to know if a problem as such existed before launching the same.
I created a time complexity calculator that uses AI to generate time complexity. I'll be beta testing it soon.

Would anyone here be interested in beta testing the product?

[drifting coral]

guys I have a question
I wanna make a program that takes inputs of teacher and their allowed time slot and the subject they teach, and which class they have to teach in a week and how many times
From this data, I make a time table with all the possibilities of the timetables

My biggest question is which part of python does this belong to and which algorithm to use if there is any

[lapis thicket]

Hey~

Theoretically a bit vector tracking previously seen characters should end up using less space than storing chars in a set, right?

I tried using an int as a bit vector but it doesn't seem to be using less space than a set() of chars. Is using an int as a bit vector not a feasible/right way?

def is_unique_better(s: str) -> bool:
  """1. Is Unique: Implement an algorithm to determine if a string has all unique characters."""
  # Time: O(k), where k is the size of the character set of s
  # Space: O(k)
  
  seen_chars = set()
  for char_ in s:
    if char_ in seen_chars:
      print(f"{getsizeof(seen_chars):10} '{s}'")
      return False
    else:
      seen_chars.add(char_)
  print(f"{getsizeof(seen_chars):10} '{s}'")
  return True

def is_unique_bit_vector(s: str) -> bool:
  """1. Is Unique: Implement an algorithm to determine if a string has all unique characters."""
  # Time: O(k), where k is the size of the character set of s
  # Space: O(k)

  seen_chars_bit_vector = 0
  for char_ in s:
    bit_num = ord(char_)
    if (seen_chars_bit_vector >> bit_num) & 1:  # Test bit #bit_num
      print(f"{getsizeof(seen_chars_bit_vector):10} '{s}'")
      return False
    else:
      seen_chars_bit_vector |= 1<<bit_num  # Set bit #bit_num
  print(f"{getsizeof(seen_chars_bit_vector):10} '{s}'")
  return True

--
Below are outputs printed by the above functions for some inputs, showing results of getsizeof() and the input

is_unique_better
       216 ''
       216 'a'
       216 'aa'
       216 'asd'
       216 'asda'
       216 ':grin:'
       216 ':grin::grin:'
       216 'a:grin:'
       216 ':grin:a:grin:'
       216 'a:grin:a'
       
is_unique_bit_vector
        24 ''
        40 'a'
        40 'aa'
        40 'asd'
        40 'asda'
     17160 ':grin:'
     17160 ':grin::grin:'
     17160 'a:grin:'
     17160 ':grin:a:grin:'
     17160 'a:grin:a'

Reference
https://stackoverflow.com/a/43458926/7121931
https://stackoverflow.com/questions/327311/

Eh Discord converted the unicode smileys I was sending as input into :grin:, but anyway

Also I guess I should add that this performs even worse, but I guess it's not fair to compare to the previous two, considering I am sending in 2**32 and beyond

def is_unique_bit_vector_arbitrary_charsets(s: List[int]) -> bool:
  """1. Is Unique: Implement an algorithm to determine if a string has all unique characters.

  In this implementation, s is a list of ints. Each element represents a character in an arbitrary character set.
  """
  # Time: O(k), where k is the size of the character set of s
  # Space: O(k)

  seen_chars_bit_vector = 0
  for bit_num in s:
    if (seen_chars_bit_vector >> bit_num) & 1:  # Test bit #bit_num
      print(f'{getsizeof(seen_chars_bit_vector):10} {s}')
      return False
    else:
      seen_chars_bit_vector |= 1<<bit_num  # Set bit #bit_num
  print(f'{getsizeof(seen_chars_bit_vector):10} {s}')
  return True```

Output:
```is_unique_bit_vector_arbitrary_charsets
        24 []
        28 [1]
        28 [1, 1]
        28 [1, 2]
        28 [1, 2, 3, 1]
 572662332 [4294967296]  # 2^32
1145324640 [8589934592]  # 2^33
2290649252 [17179869184]  # 2^34
4581298476 [34359738368]  # 2^35```

[lapis thicket]

Nvm, I just needed better test cases

When I send in a string containing all ASCII characters, the bit vector performs better than the set

Whereas, as I undertand it, set "cheats" by dynamically resizing its hashing key size -- so it wins with smaller inputs that only use a smaller section of the character set (for inputs with Unicode characters, anyway -- for ASCII, int wins either way)

[lapis thicket]

Same time complexity, but int is much slower

Here's output for all Unicode characters as the input string

is_unique_better
  33554648 ''.join(chr(x) for x in range(1114111)) -- All Unicode characters. Finishes in the blink of an eye

is_unique_bit_vector
    148576 ''.join(chr(x) for x in range(1114111)) -- All Unicode characters. Takes several seconds```

[wild gate]

Hello there! Looking for people with whom I can do leetcode preferably in Python. I have 3 years of experience so looking for similarly experienced people. Interested ones please reachout with hacker rank or stackoverflow.com profile

[idle pier]

Hello folks am currently doing 96. Unique Binary Search Trees on Leetcode, I found this DP solution

def numTrees(self, n: int) -> int:
        if n < 2: return 1
        res = [0]*(n+1)
        res[0],res[1] = 1,1
        
        for i in range(2,n+1):
            for j in range(0,i):
                res[i] += res[j]*res[i-j-1]
                
        return res[n]```
I'm having trouble understanding whats actually going on

I was wondering if someone could explain it to me

[old rover]

ooh

tabulation

[daring talon]

Can someone help me calculate the worst-case running times?

I calculated it its 0(n) but I am not sure if my calculation is right or wrong.

def postorder_Next(tree,p) : #O(n) 
 
    if (p != tree):
        parent = p.parent
        
        if (parent.right != None or parent.right != p):
            currentValue = parent.right
            
            while (currentValue.left != None):
                currentValue = currentValue.left
             
            return currentValue
        else:
            return parent
    else:
        return None

[turbid abyss]

Is this the TC of the code?

[soft totem]

can someone help me compute backpropagation ```
def sigmoid(z, prime = False):
if prime:
return sigmoid(z) * (1 - sigmoid(z))
return 1 / (1 + np.exp(-z))

def relu(z):
return np.maximum(0, z)

class Network(BaseEstimator):
def init(learning_rate = 0.01, epoches = 30, activations = [], layers = []):
self.learning_rate = learning_rate
self.layers = layers
self.n_layers = len(layers) - 1
self.activations = activations
self.epoches = epoches
self.weights, self.biases = self.initialize_parameters()
self.cache = self.initialize_cache()
self.costs = []

def initialize_parameters(self):
    w = [
        np.random.randn(next_layer, current_layer) for current_layer, next_layer in zip(layers[:-1], layers[1:]) * self.learning_rate
    ]
    b = [
        np.zeros((next_layer, 1)) for next_layer in layers[1:]
    ]
    
    return w, b

def initialize_cache(self):
    c = {}
    for i in range(len(self.weights)):
        c[f'z{i + 1}']
        c[f'activation{i + 1}'] = None
        c[f'w{i + 1}']  = None
        c[f'b{i + 1}']  = None
        
        c[f'dw{i + 1}']  = None
        c[f'db{i + 1}']  = None
        
    return c

def activate(self, z, activation):
    if activation == 'sigmoid':
        return sigmoid(z)
    elif activation == 'relu':
        return relu(z)

def forward(self, x):
    a_prev = x
    for i, params in enumerate(zip(self.weights, self.biases)):
        w, b = params 
        z = self.dot(w, a_prev) + b
        self.cache[f'z{i + 1}'] = z
        self.cache[f'activation{i + 1}'] = a_prev
        a_prev = activate(z, activation[i])
    
    self.cache[f'aL'] = a_prev
    return self.cache[f'aL']

def backward(self):
    pass

[kind wedge]

class TreeNode:
    def __init__(self, data, children = []):
        self.data = data
        self.children = children

    def addChild(self, child):
        self.children.append(child)

drinks = TreeNode('Drinks')
hot = TreeNode('Hot')
drinks.addChild(hot)
print(str(drinks.children))
print(str(hot.children))

here, im trying to create a simple tree in python, data in init stores the node name, n its children r stored in a list
so first i create 2 tree nodes, 'drinks' and 'hot', then i try adding 'hot' child to 'drinks'
but when printing both of their children(the last two lines of code), 'hot' gets a child
can anyone explain how this is happening

[ivory yacht]

The problem is your default - = []. It's a common gotcha, these are computed once when your function is defined, not every time it's called. So both nodes are sharing the same list. Instead, I'd suggest changing the default to a tuple, and calling list() so you always create a new one:

def __init__(self, data, children = ()):
    self.data = data
    self.children = list(children)

[fiery cosmos]

the children = [] default arg is the same list for each, so...TeamSpen beat me to it

We have a command about it but I always forget what it is

!mutable-default-args

[halcyon plank]

Mutable Default Arguments

Default arguments in python are evaluated once when the function is
defined, not each time the function is called. This means that if
you have a mutable default argument and mutate it, you will have
mutated that object for all future calls to the function as well.

For example, the following append_one function appends 1 to a list
and returns it. foo is set to an empty list by default.

>>> def append_one(foo=[]):
...     foo.append(1)
...     return foo
...

See what happens when we call it a few times:

>>> append_one()
[1]
>>> append_one()
[1, 1]
>>> append_one()
[1, 1, 1]

Each call appends an additional 1 to our list foo. It does not
receive a new empty list on each call, it is the same list everytime.

To avoid this problem, you have to create a new object every time the
function is called:

>>> def append_one(foo=None):
...     if foo is None:
...         foo = []
...     foo.append(1)
...     return foo
...
>>> append_one()
[1]
>>> append_one()
[1]

Note:

• This behavior can be used intentionally to maintain state between
calls of a function (eg. when writing a caching function).
• This behavior is not unique to mutable objects, all default
arguments are evaulated only once when the function is defined.

[kind wedge]

ooh so drinks n hot share d same children list, so anything thats added to drinks, gets added to hot as well. thanks alot

[ivory yacht]

Yep!

[kind wedge]

got it

[kind wedge]

thanks

[raven kraken]

Can someone suggest me a approach to solve this problem. just a hint.

for Ex - N = 4325
then P1 = 25 and P2 = 34.

So that the sum lends minimum value of 59

[hardy rampart]

Has anyone here worked with ANN models? If so please ping me!

[feral hound]

I would sort the digits then append them to each number in order of smallest to largest alternating between numbers, not 100% sure but I think that should give you the min sum

[fervent saddle]

You can use Counting Sort or something since the range of values isn’t very high

Which will avoid O(n log n)

Unless N can’t be that big. Then it doesn’t matter too much

[serene hemlock]

Hi all, I am new to programming and studying leetcode. if anyone can help me with one question related to passign variable in a fuction I asked one #help-lollipop .. currently going through blind 75 questions.

[fiery quartz]

where can I learn common algos? anyone

[serene hemlock]

https://runestone.academy/runestone/books/published/pythonds/index.html

[fiery quartz]

hmm, thanks that's like exactly what I'm looking for

[main flower]

if you aren't looking only for python algorithms (but just algorithms as a whole) then https://cp-algorithms.com/ has also some great articles

[fiery quartz]

oo that's like even more what I'm looking for

[serene hemlock]

I watch youtube mostly.

[fiery quartz]

I don't like youtube for this actually

anyways

thanks

[versed nest]

#discord-bots

[open trout]

Why here y is None

def rrange(begin, end, step = None):
    if step != None:
        if step == 0:
            return []
        elif step > 0:
            if begin > end:
                return []
        elif step < 0:
            if begin < end:
                return []
        else:
            return list(range(begin, end, step))
    else:
        return list(range(begin, end))  

x = rrange(1, 10)
y = rrange(10, 1, -1)
z = rrange(10, 1, 1)
print(x, y, z)```
and here y is normal list?
```py
def rrange(begin, end, step = None):
    if step != None:
        if (step == 0) or (step > 0 and begin > end) or (step < 0 and begin < end):
            return []
        else:
            return list(range(begin, end, step))
    else:
        return list(range(begin, end))  



x = rrange(1, 10)
y = rrange(10, 1, -1)
z = rrange(10, 1, 1)
print(x, y, z)```

[agile sundial]

look at the branch where step < 0 and begin < end@open trout

[open trout]

And?

Ah

Understood

Thank you for your help

[signal knot]

In my LinkedList, the way i remove a node is using 2 pointers that reference the previous node and the current node. So once the current node matches the item I want to remove, the previous node is used the set its next node based on the current node.

While this removes the node from the LinkedList object, the node itself still stays in memory correct? And if so how does it get removed?

def remove(self, item):
        current = self.head
        previous = None
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()
        if previous == None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())```

This above is the remove method in the LinkedList class

[agile sundial]

it it's not being referenced anymore, it gets picked up by the garbage collector

[exotic mantle]

Hi, how would you make a recursive function that returns the number of unary operations in an equation passed in parameter? I am stuck on where the recursivity is

[shut breach]

is the input a string?

@exotic mantle

[old rover]

i think a base case would be an empty list if a list is provided

or if there's no unary operators then you return None

and each time there is a unary operator you slice it out and increment the count?

that is probably wrong tho

and then you can memoize it by putting it in a dictionary where the key is the supposed list and the value is how many unary operators?

[exotic mantle]

it's not

I actually have to do it with the TI Nspire and use a function called part()

like so

[shut breach]

!e

def process(s):
    if s:
        print(s[0])
        process(s[1:])

process("abcdef")

[halcyon plank]

@shut breach :white_check_mark: Your eval job has completed with return code 0.

001 | a
002 | b
003 | c
004 | d
005 | e
006 | f

[shut breach]

so you can use recursion like that just to process some iterable

[exotic mantle]

Mhh

[shut breach]

from your examples though, it looks like you would want to call it on subexpressions

[exotic mantle]

yes

[shut breach]

so identify the operands of the given expression, then call your function on each

[exotic mantle]

mhh?

wait how would you call my function on an operator?

so far I'm here... I don't know what to look through my loop?

Would it be like nb_op_un(part(exp))

exp[i]

[shut breach]

i dont understand your examples

[exotic mantle]

Which ones?

[shut breach]

is it counting unary operators... after simplifying?

[exotic mantle]

yes

exactly

This is what the function is supposed to do

part(expr) return 1 2 or 0 depending what the expression contains, at its first level. an unary operator, binary or no operator

part(expr,0) return the operator on the first level of the expr (if there is one) or the expression itself if its only a variable or a number

part(expr,1) returns the first sub-expression of the expression "expr" (if there's one)

part(expr,2) return the second sub-expression of the expression "expr" (if there's one)

other example I've been given is this

the operators highlighted in yellow are the unary operators

[shut breach]

so having it tell you the top level structure of the expression is very helpful

idk how to do this in TIBasic or whatever, but after identifying the top level operator, you'll want to call your function on the two (or one) operands

[exotic mantle]

how would you do it in python lets say

assuming you've been given a function called part()

[half lotus]

I think like this: ```py
def nb_op_un(expression):
count = part(expression)

# Base case
if count == 0:
    return 0

# Recursive cases
if count == 1:
    operand = part(expression, 1)
    # This is a unary operator, so add 1.
    # The total will be this unary operator 
    # plus the amount of unary operators in its operand
    return 1 + nb_op_un(operand)

if count == 2:
    left_operand = part(expression, 1)
    right_operand = part(expression, 2)
    # This is a binary operator, so it doesn't count.
    # The total will be the amount of unary operators in each operand.
    return nb_op_un(left_operand) + nb_op_un(right_operand)

Recursion can be confusing so let me know if there is something I can clarify

But all things considered, this is actually a fairly elegant recursive algorithm

[exotic mantle]

😮

How come you didn't need loops to go through the expression?

[half lotus]

Because it goes through them recursively rather than iteratively.

[exotic mantle]

Also, wouldn't there be another case where you wouldnt have any operators

[half lotus]

And iterative approach would use loops, and I'm not sure what an iterative algorithm would look like.

[half lotus]

Isn't that the base case, when count == 0?

[exotic mantle]

oh yeah

since it's part(exp)

[half lotus]

Each time the function is called, it's being passed a smaller expression than the original.

Until eventually it's so small that it has no operators.

Notice that the base case just returns 0. It doesn't keep calling the function.

[exotic mantle]

right

Do you know if the syntax in TIBasics is good like this?

Define nb_op_un(exp)=
Func
count = part(exp)

If count=0 Then
 return 0
EndIF
If count = 1 Then
 operateur = part(exp,1)
 
 return 1+ nb_op_un(operateur)
EndIF
If count = 2 Then
 op_gauche = part(exp,1)
 op_droite = part(exp,2)
 
 return nb_op_un(op_gauche)+nb_op_un(op_droite)
EndIF

EndFunc

[half lotus]

I don't know anything about TIBasic, sorry.

Just run it and see if it works.

[exotic mantle]

yeah no problem ahah

if im trying with 3^-z it says that there is too many arguments

[raven kraken]

Can you try to solve it. I tried but I couldn't

I used a different approach if number of digits in input number is odd than P1 would contain the smallest digits among the entire input number and rest would be p2.

But I am not able to come up with an approach for even length

[idle pier]

hello folks am currently doing 494. Target Sum on leetcode
I found this solution

def findTargetSumWays(self, nums: List[int], target: int) -> int:
        dp = {}
        
        def backtrack(i,total):
            if i == len(nums):
                return 1 if total == target else 0
            if (i,total) in dp:
                return dp[(i,total)]
            
            dp[(i,total)] = (backtrack(i+1, total + nums[i]) +
                            backtrack(i+1, total - nums[i]))
            return dp[(i,total)]
        return backtrack(0,0)```
I'm having a little trouble understanding this part 
```py
dp[(i,total)] = (backtrack(i+1, total + nums[i]) +
                            backtrack(i+1, total - nums[i]))```

[feral hound]

that approach should work for evens too

it doesnt matter which number you append them to as long as the digits are ordered from smallest to largest

although having said that I don't see how your approach worked, unless I'm misunderstanding or you got lucky with the test cases

[sage dove]

def sqr(a):
    return a**2
def cube(b):
    return b**3
def sqcb(d):
    lst=[i for i in range(1,d+1)]
    lst2=list(map(sqr,lst))
    lst3=list(map(cube,lst))
    lst4=[j for j in lst2 if j in lst3]
    lst5=[k for k in lst if k in lst4]
    return lst5
ans=int(input('Enter the number: \n'))
print('Desired numbers are {} and total count is {}'.format(sqcb(ans),len(sqcb(ans))))                            

my code is taking a lot of time for bigger values

can someone help?

[half lotus]

The last 2 steps can be merged together by adding a condition that j is between 1 and d.

[sage dove]

Thanks for your help

[jolly mortar]

what is the problem statement? finding integers between 1 and d which are both perfect squares and perfect cubes?

[sage dove]

yes

[jolly mortar]

wouldn't that be sixth_powers = [i**6 for i in range(1, d**(1/6)+1)]

[sage dove]

sorry i was in hurry

[jolly mortar]

since perfect squares and perfect cubes are perfect sixth powers

[sage dove]

One of the parents, in a family, gives a number N and asks his child to extract list of those numbers that are both squared and cube of some numbers but should be bounded by N. Also, find total such numbers.

this is the question

[vocal gorge]

d**(1/6) would need to be int(d**(1/6)) for this to not produce a TypeError

[jolly mortar]

oh right

[vocal gorge]

that's all the numbers of form i**6 which are below N, total of int(N**(1/6)) of them

a while loop would be the nicest way to do this, IMO

[vocal gorge]

(Proof: each such number would be d = a**2 = b**3 for some integer a,b. Consider the prime decompositions of a**2 and b**3. They must be equal, so the powers of each prime are equal. The powers of primes in the decomposition of a**2 must be divisible by 2, and in the decomposition of b**3 by 3, but they are the same decomposition, so the powers are all divisible by 6. Hence, d can also be represented as d**6 for some integer d)

yeah, since the number of such numbers scales as N**(1/6)

[half lotus]

What's the proof that for a**n, the exponents of its prime factorization are divisible by n?

[chrome raven]

Hello

[drowsy palm]

How to - using itertools - print combinations of 5 times of letter A and 2 times of letter B?

Note: check your solution before replying, please.

Could be set(list(itertools.permutations(['A', 'A', 'A', 'A', 'A', 'B', 'B'], 7))) an only solution? Why?

[vocal gorge]

Multiplying two integers is just adding up the exponents of the corresponding primes, so to put an integer into an integer power n, one just multiplies all of the exponents by n.

[raven kraken]

No No it didn't worked I wasn't able to solve this question that's why I asked for help here.

[chrome raven]

Hello

Any kind soul can help with time complexity analysis, I have an algo I m working on and am trying to find its complexity

[old rover]

def count_construct(target,word_bank):
  if target == "": return 1
  tot_count = 0
  for word in word_bank:
    if target.index(word) == 0:
      num_ways_for_rest = count_construct(target.slice(len(word),word_bank)
      tot_count += num_ways_for_rest
      
  return tot_count

what's wrong w the 7th line here

mismatched parentheses

aaaand the syntax is off

hey good i fixed it

def count_construct(target,word_bank):
  if target == "": return 1
  tot_count = 0
  for word in word_bank:
    if target.index(word) == 0:
      slice_len = slice(len(word))
      num_ways_for_rest = count_construct(target[slice_len],word_bank)
      tot_count += num_ways_for_rest

  return tot_count

print(count_construct("doge", ["d", "o", "g", "f"]))

still not right

ofc this isn't actually going to work bc i didn't memoize it yet

nope

oh i see

string indices must be integers

yeah i'm stumped

oh i see

[plush owl]

Anyone know how sorted list in sortedcontainers is implemented? How does it achieve O(log n) time for element addition/removal? Does it use a BST in the background?

[feral hound]

ah mb then I thought you had it working for odd lengths, is this a school assignment?

[rare sparrow]

Is this the right channel for SciPy-Problems?

I've installed it via pip and it shows up in the list of installed packages but when i try to import it(from scipy import ndimage) it just says ModuleNotFoundError: No module named 'scipy'

[rare sparrow]

OK I found a way not to use this module

[chrome raven]

Hey

any kind soul that's good at complexity analysis?

[fiery cosmos]

Like Big O notation? Time, space, cyclomatic?

[chrome raven]

Time complexity

#help-coconut @fiery cosmos if you don't mind

[fervent saddle]

Just post the question, you don’t need to get anyone to agree to help first

If they see it and want to help then they will

[chrome raven]

    frontier = {}
    parents = {}
    unseenNodes = graph
    infinity = 1.0

    for node in unseenNodes:
        frontier[node] = infinity

    frontier[start] = -1.0                         #O(N)

    while unseenNodes:     
        cur_node = None                             #O(N)

        for node in unseenNodes:
            if cur_node is None:                           
                cur_node = node
            elif frontier[node] < frontier[cur_node]:
                cur_node = node 

        path_options = graph[cur_node].items()

        for child_node, weight in path_options:                                    #O(log p) 
            if (weight * frontier[cur_node]) < frontier[child_node]:
                frontier[child_node] = -1.0 * abs(weight * frontier[cur_node])
                parents[child_node] = [cur_node]
            elif (weight * frontier[cur_node]) == frontier[child_node]:
                frontier[child_node] = -1.0 * abs(weight * frontier[cur_node])
                parents[child_node] += [cur_node]

        unseenNodes.pop(cur_node)

    multiple_paths = get_paths(parents, start, end)

    if frontier[end] != infinity:
        return abs(frontier[end]), multiple_paths```

@fervent saddle Here u go

[plush owl]

Given a binary 2d Matrix, in every step you can convert all connected cells with same value. How many steps to make the complete Matrix to same values?

[raven kraken]

No Actually I was asked this question in amazon SDE 1 OA. And I was not able to solve this

[inland silo]

How would I take output of a function loop and have it saved to a file permanently until deleted on my computer

[calm spade]

"parent": {
    "child": {...},
    "child": {...},
    "child": {...},
    ...
}

How do i sort the parent dict based on a value in the child dicts?

[fiery cosmos]

You can't exactly sort a dict without recreating it since dicts are ordered by insertion order (and used to be unordered). But you could get a sorted list of the key/val pairs with something like py data = sorted(mydict["parent"].items(), key=lambda kv: kv[1]['someproperty']) (fixed a bit)

[fiery cosmos]

!e then you can re-dict if really desired ```py
mydict = {"parent": {
"child1": {'score': 9},
"child2": {'score': -4},
"child3": {'score': 3},
}}
data = sorted(mydict["parent"].items(), key=lambda kv: kv[1]['score'])

print(data)
new_dict = dict(data)
print(new_dict)

[halcyon plank]

@fiery cosmos :white_check_mark: Your eval job has completed with return code 0.

001 | [('child2', {'score': -4}), ('child3', {'score': 3}), ('child1', {'score': 9})]
002 | {'child2': {'score': -4}, 'child3': {'score': 3}, 'child1': {'score': 9}}

[calm spade]

Thanks

[willow garnet]

def get_faster(list):
    how_long = (1 / len(list)) * 100000
    sleep(how_long)

[fiery cosmos]

Is it bad that i know the concept and ADT of linked lists but struggle to implement the code in python

By myself

[lean dome]

I think that if you struggle to implement the code, you don't know the concept of a linked list as well as you think you do. The code is quite simple, once you have a complete understanding of the concept

[fiery cosmos]

@lean dome fair point

I think the issue is perhaps python as well?

I understand how to do it in C, using structures and pointers

however I struggle a bit with python and self and init

[lean dome]

perhaps - though doing it in Python is strictly easier, using objects and attributes.

The basic structure of a linked list in Python is:

class Node:
    def __init__(self, data, next):
        self.data = data
        self.next = next

[fiery cosmos]

right, so i understand that

it is more the methods

I can follow along on a video

but struggle when writing it myself

because from my understanding that is just the node right? [data | memory address]

but none of them are linked yet

[lean dome]

right, that's a single node.

[fiery cosmos]

what would you say are the minimum methods for linked list to say you fully understand

i will try to implement tonight without any help

[lean dome]

if you want a list:

class Node:
    def __init__(self, data, next):
        self.data = data
        self.next = next

last_node = Node(3, None)
second_to_last_node = Node(2, last_node)
first_node = Node(1, second_to_last_node)

that's a length 3 linked list, where the 1st node holds the value 1, the 2nd holds the value 2, and the 3rd holds the value 3.

!e ```py
class Node:
def init(self, data, next):
self.data = data
self.next = next

last_node = Node(3, None)
second_to_last_node = Node(2, last_node)
first_node = Node(1, second_to_last_node)

print(first_node.data)
print(first_node.next.data)
print(first_node.next.next.data)
print(first_node.next.next.next)

[halcyon plank]

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

001 | 1
002 | 2
003 | 3
004 | None

[fiery cosmos]

yeah, i can understand that part

I think the issue is when implementing methods

that I struggle with

[lean dome]

ok - which method?

[fiery cosmos]

well, can I ask you what you would think the minimum methods for a linkedlist

one should implement

[lean dome]

usually a linked list has... hm. front() returning the data in the first node, back() returning the data in the last node, and maybe insert() that adds a new node at a given index, and remove() that removes the node at a given index.

[fiery cosmos]

okay thanks... I will try to implement those myself

[lean dome]

you'd usually have a LinkedList class as well - because you can't represent an empty list if you only have Node, since every node has data, and so you can't represent the absence of data with just a Node

so it would be typical to have:

class Node:
    def __init__(self, data, next):
        self.data = data
        self.next = next

class LinkedList:
    def __init__(self):
        self.first_node = None
        self.last_node = None

and all 4 of those methods would be on LinkedList, not on Node

[fiery cosmos]

thank you

[lean dome]

and there are a few invariants for LinkedList:

1. If the list is empty, then first_node and last_node are both None
2. Otherwise, last_node.next is None, and either first_node is last_node (for a length 1 list), or it's possible to reach last_node by repeatedly following the .next from first_node

[chrome raven]

Hey

Need some help to figure out the time complexity for my algorithm, anyone can do a quick look?

def dijkstra(graph, start, end):
    frontier = {}
    parents = {}
    unseenNodes = graph
    infinity = 1.0

    for node in unseenNodes:
        frontier[node] = infinity

    frontier[start] = -1.0                         #O(N)

    while unseenNodes:     
        cur_node = None                             #O(N)

        for node in unseenNodes:
            if cur_node is None:                           
                cur_node = node
            elif frontier[node] < frontier[cur_node]:
                cur_node = node 

        path_options = graph[cur_node].items()

        for child_node, weight in path_options:                                    #O(log p) 
            if (weight * frontier[cur_node]) < frontier[child_node]:
                frontier[child_node] = -1.0 * abs(weight * frontier[cur_node])
                parents[child_node] = [cur_node]
            elif (weight * frontier[cur_node]) == frontier[child_node]:
                frontier[child_node] = -1.0 * abs(weight * frontier[cur_node])
                parents[child_node] += [cur_node]

        unseenNodes.pop(cur_node)

    multiple_paths = get_paths(parents, start, end)

    if frontier[end] != infinity:
        return abs(frontier[end]), multiple_paths```

[grizzled onyx]

Hi guys

Where is the problem

[grizzled onyx]

Thank u

It works

[feral hound]

ok I wrote a solution that I think should work, based on the approach I described before, do you want to see the code or should I try to explain it a bit more first for you to try?

[raven kraken]

You can show me the code, I have given enough effort to solve this question.

[south ermine]

[feral hound]

!e

def smallest_sum(N):
    P1 = ""
    P2 = ""

    for i, digit in enumerate(sorted(str(N))):
        if i % 2 == 0:
            P1 += digit
        else:
            P2 += digit

    print("P1:", P1)
    print("P2:", P2)
    return int(P1) + int(P2)


number = 8361451
print("Sum:", smallest_sum(number))

[halcyon plank]

@feral hound :white_check_mark: Your eval job has completed with return code 0.

001 | P1: 1358
002 | P2: 146
003 | Sum: 1504

[feral hound]

the idea is that the bigger digits should have less significance

[old rover]

i want to remove a smaller string from a bigger string in python

and i'm not sure how to do it

like if i had the string "dog"

and if i wanted to remove "do" and just be left with g

i thought the answer would be slice notation but slicing it only gives me "do"

[meager forum]

hello

P(LCS=4 | s1=9, s2=9): Calculate the probability of seeing an LCS of length 4 in two random DNA sequences of length 9.

X random variable is the frequency of the maximum number (LCS value) in the LCS matrix.

To calculate P(X=4);

1. Produce two random sequences length 9 using python’s random library (you can use the scripts learned in the lab session).

2.   A) Run the ‘compute_lcs’ function.
     B) Get the maximum score of LCS.
   

3. Beginning from the 1st step, repeat at least 10,000 times.
4. Plot the distribution of scores (a histogram would work fine).
5. Return the frequency of score = 4.
6. How can you calculate the p-value of seeing an LCS of length 4 in two random DNA sequences of length 9? (DNA sequence represents AGCT OR ACGT meaning adenine tymine guanine and citosine) please can anyone help ?

[jolly tusk]

If you're looking to remove all occurrences of a specific substring, you should consider trying out either the replace or translate methods from string library. (A Google search is your best friend here).

[old rover]

yep i think i'll figure it out

gotta take a break

figured it out

[vapid dirge]

is this free

[old rover]

didn't know that JS and python have different slice behaviors

[vapid dirge]

def findNumOfValidWords(words: List[str], puzzles: List[str]) -> List[int]:
    start = perf_counter()
    result = {}
    for puzzle in puzzles:
        result[puzzle] = 0
        for word in (sorted(set(word), key=word.index) for word in words):
            if puzzle[0] in word and all((letter in puzzle for letter in word)):
                result[puzzle] += 1
    print(f"Took: {(perf_counter() - start) * 1000}ms")
    return [v for v in result.values()]

what can i improve here to make it faster?

i get Time limit Exceed

[jolly tusk]

What are the constraints?

[vapid dirge]

the code works, but i guess its too slow

example input:

words = ["aaaa","asas","able","ability","actt","actor","access"]
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
# first letter puzzle is in word
# all letters of word must be present in puzzle

what is big o of my algo?
For double for loop, its O(n^2) but what about the generators?

is that right?

[agile sundial]

why not slice the part you want instead of the part you don't want

[old rover]

oh yeah that would make sense

i went on this wild goose chase and used .replace

thanks

that would probably be from the len of the word as the start to the len of the target

idk i'll take a look tomorrow

[jolly tusk]

Although I don't have the question, it looks like you'll be using the sorted set everywhere once it's sorted. Perhaps you might want to try and do that beforehand?

[vapid dirge]

if i do that beforehand it just increases the memory

but i will try like that

[jolly tusk]

What kind of memory and time constraints are you working with here?

[vapid dirge]

there is no constraint in memory, there is time constraint idk how much

i tried creating the generator beforehand

still TLE, i think i should get rid of the nested loop

uhh the testcase has
len(words) of 100000
and
len(puzzles) of 10000

[jolly tusk]

You should probably move that sorting operation out of the loop. The additional memory used won't be a deal-breaker here imo

[vapid dirge]

i tried that too

still slow

[jolly tusk]

I'm not sure about the Question, but check if there's a way to do it without nested loops

[vapid dirge]

yeah pretty sure i need to get rid of nested loop

[jolly tusk]

If you could share the Q, we can try working through it here

I assume this is a practice Q and not part of any contest. Right?

[vapid dirge]

no, its practice in leet code

[jolly tusk]

Cool. Kindly share the Q here and I'll try to assist you.

[vapid dirge]

https://leetcode.com/problems/number-of-valid-words-for-each-puzzle/

its daily problem of Nov 9th

[jolly tusk]

Right. The constraints show that the puzzle length is 7, exactly, and that it doesn't have repeated characters. Looks like smthin that can be used while designing the loops

[knotty cliff]

Input: [["Jim", 100], ["Jeff", 75], ["Jane", 80], ["Juan", 110], ["Jim", 20]]
Output: [["Jim", 120], ["Jeff", 75], ["Jane", 80], ["Juan", 110]]

it just adds the numbers for the elements with the same name

[agile sundial]

and the code?

[knotty cliff]

def summarizeFines(fines)
    sum = 0
    differentFines = fines
    for i in range(len(fines)):
        for k in range(i+1, len(fines)):
            if fines[i][0] == fines[k][0]:
                sum = fines[k][1] + fines[i][1]
                del differentFines[k]
                differentFines[i][1] = sum
 return differentFines

i forgot how to format it in python

there it is

[agile sundial]

that doesn't look like python formatting, but whatever

[knotty cliff]

and i said i thought it was n^2 + n

[agile sundial]

where's the + n from?

[patent patrol]

I am trying to implement BFS on Binary Tree Recursively and this is what I tried I believe it is some form of DFS instead.

from queue import Queue

class Node:
  def __init__(self, val: int):
    self.value: int = val
    self.left: Node | None = None
    self.right: Node | None = None

class BST:
  def __init__(self):
    self.root: Node | None = None
    self.q = Queue()

  def insert(self, root: Node | None, val: int) -> Node:

    if root == None:
      return Node(val)

    if val < root.value:
      root.left = self.insert(root.left, val)
    
    else:
      root.right = self.insert(root.right, val)

    return root

  def bfs(self, root):
    self.q.put(root)
    visited = self.q.get()
    print(visited.value)
    if visited.left != None:
      self.bfs(visited.left)
    if visited.right != None:
      self.bfs(visited.right)

[knotty cliff]

from the comparison

[agile sundial]

what comparison

[knotty cliff]

if fines == fines

[agile sundial]

that's a constant time operation

you do it n^2 times

[knotty cliff]

oh so n^2

cuz of the nested for loop

[agile sundial]

yeah

[knotty cliff]

there is no best or worst case right

[agile sundial]

there is a best case

the overall time complexity isn't n^2, too

[knotty cliff]

uhh

[agile sundial]

and a worst case

[knotty cliff]

is the sum = counting as well

[agile sundial]

that assignment is constant time

the del differentFines[k] takes O(n) time

[keen hearth]

Yep, I think you're right. If you trace the contents of the queue over time, you'll see that it never contains more than one element. You put a node in the queue, then immediately remove it.

You have the right idea on using a queue, but an implementation of BFS likely wont be recursive.

[knotty cliff]

oh so does that make it n^3

[agile sundial]

mhm

[keen hearth]

Pseudo code for a BFS implementation: ```
Add the root to the queue.
While the queue still contains elements:
Pop a node from the front of the queue.
Visit that node.
Append that node's children to the end of the queue.

[knotty cliff]

i sort of understand it but im going to try to find the time complexity of another function

[agile sundial]

practice makes perfect

[knotty cliff]

this is n^3 right

def optimizeContainer(total, packages):
    for i in range(len(packages)):
        for j in range(i+1, len(packages)):
            if packages[i][1] + packages[j][1] == total:
                value = (packages[i][0], packages[j][0])
    return value

[agile sundial]

doesn't seem like it

as long as those are lists of ints, that is

[knotty cliff]

String and an int

[agile sundial]

uhh, what's the string

[knotty cliff]

wait sorry total is an int and packages is the list

[agile sundial]

it looks like n^2

all the operations inside the loops are constant, and the two loops make it n^2

[knotty cliff]

oh i keep forgetting that comparisons are constant

wait ik for this function the best case could be the first 2 elements and the worst case can be the last 2 elements

the first function confuses me tho

on best or worst case

[agile sundial]

for the first one, the best case is when the if statement inside never runs

[knotty cliff]

oh i see

[dreamy pewter]

i see that im icy

[idle pier]

hello folks is this both runtime and space complexity of O(n)?

def sortedSquares(self, nums: List[int]) -> List[int]:
        l,r = 0,len(nums)-1
        output = []
        
        while l<=r:
            left_square = nums[l] ** 2
            right_square = nums[r] ** 2
            
            if left_square < right_square:
                output.append(right_square)
                r -= 1
            else:
                output.append(left_square)
                l += 1
                
        return reversed(output)```

[runic tinsel]

yeah

you;re not returning a list though

you gotta do output.reverse() on a separate step

[patent patrol]

Thanks didn't knew that maybe that's why I didn't found any solution on Google as well. Though I've already implemented BFS iteratively.

[patent patrol]

Yes its O(N) for both T & S

[raven kraken]

@feral hound I dry run your solution and it worked perfectly. Can you tell me one thing I am still wondering why does your logic work? Like is there any predefined way in mathematics to find the min sum that I am unaware of ? Even if I would have tried solving it for an entire day I wouldn't have came up such brilliant approach. Can you share your thought process while you try to solve questions?

[feral hound]

my logic behind it is that you want the largest digit have to have the least significance so you sort a string representation of the number N, so now the smallest digit is first and the largest digit is last, then you go along and append each digit from smallest to largest to P1 and P2 the important part here is to alternate for each digit, this way the numbers have either the same number of digits or one is only longer by a single digit if the number of digits is odd, and by appending and alternating from smallest to largest you give the largest digits the least significance aka the "ones place"

and I didnt really have any mathematical proof for it and dont know if one exists, which is why I told you that im not 100% if it works or not since I dont have a proof I'm just going by some logical assumptions I've made, let me know if this made sense

keep in mind that there might be some clever method that has a much better complexity than my solution btw, this is just A solution not THE solution

[hexed granite]

Maximal bipartite graph

You are given a graph with W nodes. There are exactly M bidirectional edges in the graph. You can remove any number of nodes from the graph.

Task
You have to determine the maximum size bipartite graph that can be formed after removing any number of nodes from the
graph
Assumption

N = 3
M= 3

Edges = [[1-2],[2-3],[1,3]]
Given graph is not bipartite, so we remove node 1 Now the graph becomes a bipartite graph. Therefore the maximum size of the bipartite graph is 2.

Input 1

4 5
1 2
2 3
3 4
2 4
1 3

Output
3

def solve(N,M,Edge):
# func here

N,M = map(int,input().split())
Edge = [list (map(int,input().split())) for i in range(M)]

print(solve(N,M,Edge))

How should i get started with this? Please help?

[graceful bobcat]

Hey people

I’m trying to learn pointers in python but I can’t find anyone who talks about them

[feral hound]

you can't find anyone who talks about them because they don't exist in python

[agile sundial]

they're too low level for the general usage of python

they do exist, but no one cares because that's all that exists

variables are just references

there isn't really a "value" type, it's all objects

[feral hound]

meant more so in that you can't use them

[agile sundial]

i mean, you can only use them

[graceful bobcat]

->

Those things

[feral hound]

how?

[agile sundial]

those aren't pointers, that's typehinting

[graceful bobcat]

What are they called

oh

Thanks

[agile sundial]

you can't make a variable without making a reference

[feral hound]

ok let me reword, you can't explicitly use them

[agile sundial]

sure

[raven kraken]

For how long have you been doing DSA , I have started studying DSA for like past 4 months but still I am unable to solve leetcode medium problem all on my own. any tips that you can give me to do good in DSA would be highly appreciated.

[graceful bobcat]

Yeah i see it in leetcode all the time but never understand it lol

Oh it’s like in c with int main

I get it

Tysm bro

lol

[vocal gorge]

...what's exact packed string matching? It sounds like it's just substring search on ASCII strings stored as one byte per char?

[agile sundial]

given two strings T and P we want to find all substrings of T that are equal to P.
is this correct?

[feral hound]

I never really specifically did DSA but I've been coding for ~3yrs and tbh I actually learnt a lot more about DSA after I joined this server just by seeing other ppls questions, its weird but very often I find that questions that I would usually struggle with myself are a lot easier to solve when someone else asks them

[fiery cosmos]

That can be done in o(n) no, there are methods like knf(i think)? And the one in which we take mod of each value and stuff.

Quite good algos.

[feral hound]

the biggest thing I would say though is work on your fundamentals before focusing on DSA, and its a lot easier to understand an algo when you actually need to use it

[agile sundial]

probably. actually definitely

[vocal gorge]

I'd read the code of something like https://docs.rs/crate/memchr/2.4.1 then, maybe

[raven kraken]

Its just opposite for me when someone asks me a programming question even if I have done it before I will screw it up.

[vocal gorge]

I suspect that what you're looking for and what that library calls "Generic SIMD" (https://0x80.pl/articles/simd-strfind.html#algorithm-1-generic-simd) are at least related

At time of writing, this crate's implementation of substring search actually has a few different algorithms to choose from depending on the situation.

For very small haystacks, Rabin-Karp is used to reduce latency. Rabin-Karp has very small overhead and can often complete before other searchers have even been constructed.
For small needles, a variant of the "Generic SIMD" algorithm is used. Instead of using the first and last bytes, a heuristic is used to select bytes based on a background distribution of byte frequencies.
In all other cases, Two-Way is used. If possible, a prefilter based on the "Generic SIMD" algorithm linked above is used to find candidates quickly. A dynamic heuristic is used to detect if the prefilter is ineffective, and if so, disables it.

[feral hound]

I think thats the same for me when I'm asked directly, I mean more so in a chat like this

people ask their questions I read it and think about it for a bit if I can think of a solution I reply

but on the spot I tend to mess up a lot as well

[vocal gorge]

the site just doesn't support https

I get that sometimes when trying to access a site that doesn't support HTTPS via HTTPS, try removing the s from the link maybe

it works for me via http

[turbid abyss]

Hey guys, we've created a time complexity calculator that would help calculate TC of code purely based on AI. It is built using the most powerful AI algorithm, OpenAI. You can join the waitlist to access by filling in the form below.
https://timecomplexity.herokuapp.com/

[bleak rock]

nice project

Hello people, I'm struggling with a task involving Tree Data Structure

I'd be really grateful if someone could help me understanding these requirements...

[novel gorge]

I have written the same algorithm for getting the closest point in a list of points using bruteforce and numpy (with einsum and argmin) and measured it using timeit.timeit but the bruteforce method was way faster. Why?

[agile sundial]

can't really answer without the code

[crude tangle]

i am using networkx. I add edges with custom attribute G.add_edge(pair[0], pair[1], weight = 1), and later increase weight if this same pair already has an edge with G[pair[0]][pair[1]]["weight"] += 1. How can i check how many edges have weight of 1 or higher, of 2 or higher and so on?
I want to make analisys how many edges and nodes i have left if i only keep edges with weight = 1, weight = 2, weigh = 3 and so on

[old rover]

so

what's the point of tabulation

it's a dumb question ik

memoization is using a dictionary while tabulation uses a list of length of the input

it's a bottom up approach

that's all i'm really getting out of it

[mild dove]

I think you can check all edges https://networkx.org/documentation/stable/reference/classes/generated/networkx.Graph.edges.html, idk if there is a efficient way to remove. You can also run a BFS and DFS manually and ignore edges outside your criteria.

[mild dove]

dictionary is O(1) to search and unordered list O(n). in short, it scales better

[old rover]

i see

[crude tangle]

@mild dove managed to solve it this way for now:

        edgesToRemove = []

        for node1, node2, data in G.edges(data= True):
            if data["weight"] < minWeight:
                edgesToRemove.append([node1, node2])

        for edge in edgesToRemove:
            G.remove_edge(edge[0], edge[1])

        G.remove_nodes_from(list(nx.isolates(G)))

[dapper sapphire]

Was it for a senior position?

[idle pier]

hello folks am doing 62. Unique Paths its DP problem

def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for i in range(m)]  # DP Matrix of size m*n intialized to 1

        for r in range(1, m):
            for c in range(1, n):
                dp[r][c] = dp[r - 1][c] + dp[r][c - 1]

        return dp[-1][-1]```
this part `dp = [[1] * n for i in range(m)]`, can someone explain to me whats going on? because I seen other solutions in which they don't include the `[1]*n`, they have `0` but they also include a `for` loop for `n`. Is this way just a shorter of what I just mentioned?

[vocal gorge]

This is initializing a 2d list of ones of size m x n. The inner * n can be turned into a for-loop, but it's not necessary. The outer loop, however, is necessary and can't be replaced by a * m, because * copies references - if you use it on a list, you'll get several references to the same list, which will produce behaviour you likely don't want:

!e

lst = [[0]*3]*5
print(lst)
lst[0][2] = 4 # this changes one element, right?
print(lst) # nope - because all the sublists are the same sublist here.

[halcyon plank]

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

001 | [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
002 | [[0, 0, 4], [0, 0, 4], [0, 0, 4], [0, 0, 4], [0, 0, 4]]

[vocal gorge]

Using * to copy an integer is fine, however, because they are immutable, so [1] * n resulting in a list of n references to the same integer can't cause any problems.

[eager cargo]

I am comparing 2 CSV files by opening the files, reading them into DictReaders, going through each row in CSV1, finding the same row based on a key:value, then comparing the entire line in CSV1 to the entire line of CSV2. For some reason it only does this once and stops.

[agile sundial]

pretty sure that's completely irrelevant

[agile sundial]

solving the problems bottom up let's you avoid the cost of recursive calls

time complexity is the same, but you get a lower constant factor

except in some cases

[vocal gorge]

DictReaders are iterators (you can't iterate through them a second time without recreating them)

[eager cargo]

So DictReaders are a one and done?

[vocal gorge]

Yeah. They are like that because they don't even store the previous lines, just read the file line-by-line and yield each line after transforming it into a nicer form.

You could either recreate the second dictreader for each line of the first one, or just load the second file into memory entirely. The second approach is faster but requires storing that entire file in memory.

[eager cargo]

Storing it in memory, as in creating a Dictionary manually out of the file I opened?

Or readlines() ?

[vocal gorge]

Depends on what form is most convenient for you, but for example, you could just store all the rows of a DictReader in a list.

if you are "finding the same row based on a key:value", a dict would most likely be the fastest way

[eager cargo]

So I could create a blank dictionary, go through the DictReader and insert keys/values?

I'm sure there is an easier way

[vocal gorge]

Pretty much, though it can probably be written as a dict comprehension.

something like

second_dict = {row["whatever col you use as the key"]:row for row in DictReader(second_file)}

[eager cargo]

Would it be an easier to use Pandas, do a merge and output mismatched lines to another CSV? That's essentially what I'm needing.

[muted siren]

Hi I am learning DS at the moment and I have a question about arrays.

We know that arrays in Python stores data by referencing, thus I have a doubt.

Lets say we have two lists:

A = [1,2,3,4]
B=[9,8,7,6]

Now if we do:
B = A
List B will refer to the same elements as A hence if we change anything in A it will be reflected in B

However, if we do:
B.extend(A)

B returns [9,8,7,6,1,2,3,4]
If we change any element of A now, lets say:
A[0]=50

B still returns the old value and not
[9,8,7,6,50,2,3,4]

Why so?
If B is only extended by pointing to where A is pointing, why does changing value in A is not reflected in B??

[fiery cosmos]

B.extend(A) appends all the elements of A to B, A could be any iterable, so it's not chunking on A itself

A remains unchanged

[muted siren]

This is where I am confused, appending A to B will create a list of lists. However if we extend then all the elements of A are added individually to B

What I am meaning to ask is, once we extend B, are the new cells refering to same memory of a different one?

[fiery cosmos]

Yeah. Appends adds a single element to the end. That single element could be an int or another list or whatever. B.extend(A) is equivalent to py for a in A: B.append(a)

The new cells will be new memory (specifically new pointers)

[muted siren]

Ahhh I see.. So as long as those extended cells points to the same value they use the same pointer but as soon as we change any element of A or of B the cell will point to a diff object

[eager cargo]

Ok, I'm so close. I'm comparing 2 CSV files with identical headers with Pandas and a Concatenate. However, the results show me the different rows in both source and destinations. What is the option to only show items from the destination?

[brisk hemlock]

array1 = [[0, 100], [0, 200] [0, 300]]
array2 = [10, 20 , 30]

#how would i loop through 2d array and get the second index of each array so how would i be able to get 100, 200 and 300 AND then multiply the first index (100) with the first index of array2.```

can someone show me what a for loop would like if i was trying to do that ^^^

100 * 10
200 * 20
300 * 30
``` this is what its operation should be like i just dont know how i would do it using loops

[cunning rock]

i guess this works?

def looping1(array1, array2):
    x = []
    z = []
    for i in array1:
        x.append(i[1])
    for i in range(len(x)):
        z.append(x[i] * array2[i])
    return z
looping1([[0, 100], [0, 200], [0, 300]], [10, 20 , 30])
    ```

[brisk hemlock]

lemme see

[cunning rock]

k

[agile sundial]

you can loop over both at the same time, using zip

!zip

[halcyon plank]

The zip function allows you to iterate through multiple iterables simultaneously. It joins the iterables together, almost like a zipper, so that each new element is a tuple with one element from each iterable.

letters = 'abc'
numbers = [1, 2, 3]
# list(zip(letters, numbers)) --> [('a', 1), ('b', 2), ('c', 3)]
for letter, number in zip(letters, numbers):
    print(letter, number)

The zip() iterator is exhausted after the length of the shortest iterable is exceeded. If you would like to retain the other values, consider using itertools.zip_longest.

For more information on zip, please refer to the official documentation.

[brisk hemlock]

hmmm it looks sus

[cunning rock]

lol

[brisk hemlock]

what about 2 d arrays tho

[agile sundial]

a 2d list is just a list with lists in it

you can loop over it as well

[brisk hemlock]

exactly

show

pls

[agile sundial]

show what

[brisk hemlock]

this but using 2d arrays. you're telling me syntax is the exact same to get the second element of each list ?

[agile sundial]

not the exact same

[brisk hemlock]

show pls 🙏

ive never used zip before

it looks clean af

[agile sundial]

!e

A = [[0, 100], [0, 200], [0, 300]]
B = [10, 20 , 30]
for a, b in zip(A, B):
  print(a, b)

[halcyon plank]

@agile sundial :white_check_mark: Your eval job has completed with return code 0.

001 | [0, 100] 10
002 | [0, 200] 20
003 | [0, 300] 30

[agile sundial]

you should be able to figure it out from t here

[brisk hemlock]

hmm

[brisk hemlock]

Yeah IDK how i get the second index of each list in a 2d array using that

[agile sundial]

you're looping over the sublists

a is a sublist, which i printed out

[brisk hemlock]

yup i know that i could do py for _, x in A

but idk how it would look using ur method

[agile sundial]

that's just unpacking

!e
with zip, it'd be like

A = [[0, 100], [0, 200], [0, 300]]
B = [10, 20 , 30]
for (_, x), b in zip(A, B):
  print(x, b)

[halcyon plank]

@agile sundial :white_check_mark: Your eval job has completed with return code 0.

001 | 100 10
002 | 200 20
003 | 300 30

[brisk hemlock]

ahh ok i see

that is weird syntax

[brisk hemlock]

💪 nice it works

[agile sundial]

you need the parentheses so it unpacks the list

[brisk hemlock]

ok ok now listen to this bit

cool = [0, 0, 0]
for (_, x), i in zip(A, B):
    cool[???] = i * x```

@agile sundial thoughts ?

[agile sundial]

why pre-create the list? just append to an empty one

if you had to, enumerate does that

[brisk hemlock]

ok well we still need to loop through it

[agile sundial]

!enumerate

[halcyon plank]

Ever find yourself in need of the current iteration number of your for loop? You should use enumerate! Using enumerate, you can turn code that looks like this:

index = 0
for item in my_list:
    print(f"{index}: {item}")
    index += 1

into beautiful, pythonic code:

for index, item in enumerate(my_list):
    print(f"{index}: {item}")

For more information, check out the official docs, or PEP 279.

[brisk hemlock]

there's a function for everything in this language ...

i come from the olden dark age where i create all the functions for it

[brisk hemlock]

ok i think I understand it now but how would I utilize it in my for loop?

[brisk hemlock]

this one here

[agile sundial]

just wrap it around it

[brisk hemlock]

hmmm i dunno if that'd work

[brisk hemlock]

if i wrap it around another for loop it does it the calculation twice as much

[agile sundial]

i mean something like, enumerate(zip(...))

[brisk hemlock]

hmmm

[brisk hemlock]

ahh this is too confusing

[brisk hemlock]

for index, (_,  x), i  in enumerate(zip(A, B)):
    print(x, i)``` ive tried everything and it doesnt work

for i, (_,  x)  in enumerate(zip(table, speed)):
    print(_, x)``` I also tried this and it doesnt work

[agile sundial]

enumerate gives you tuples (index, element)

zip gives you tuples of the elements of the two iterables

so it'd be like

for i, ((_, x) b) in enumerate(zip(A, B))

[brisk hemlock]

ahhh ok

[brisk hemlock]

OIIII it works

that is some weird syntax but im glad it worked

[idle pier]

hey folks, am doing 566. Reshape the Matrix on leetcode

if len(mat) * len(mat[0]) != r * c:
            return mat
            
        ans = [[]]
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                k = mat[i][j]
                if len(ans[-1]) < c:
                    ans[-1].append(k)
                else:
                    ans.append([k])
        return ans```
Ok so from what I know, we are flattening the matrix and than storing it in `k`. Then we check if the last row is less than `c`, if it is, we append the flatten matrix to the last row, `else` we do otherwise
Is this correct?

[fiery cosmos]

k is just one value in the matrix, namely at (i, j). You append that over and over to the most recent row ans[-1]

[cobalt lynx]

im pretty new to python and algorithims in general could someone tell me how my syntax is wrong

[cobalt lynx]

ps: i corrected the spelling mistake in range but its still not working

[idle pier]

are you using python2 or python3?

[cobalt lynx]

hmmm

im pretty sure its python 2

will changing it to 3 work?

[cobalt lynx]

ive changed it to python 3 it still does not work

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for x in range((len)nums):
for z in range(x + 1, ((len)nums)):
if nums[x] + nums[z] == target:
return [x , z]

[idle pier]

it should be
for x in range(len(nums)):
check your parentheses

[cobalt lynx]

oh

[idle pier]

same for the other for loop

[cobalt lynx]

ok i changed it for both

now error is in second line

[idle pier]

should work now

[cobalt lynx]

for z in range(x + 1, (len(nums)): this one

[idle pier]

yea the second for loop has the same issue

check your parentheses

[cobalt lynx]

wait no

ya thx i fixed it

ive been staring at this code for 30 mins straight thanks a lot

[idle pier]

never thought of that solution lol

since your using a nested for loop, your runtime is O(n^2)
try using using a hashmap for faster look up

[fiery cosmos]

what is python?

[fiery cosmos]

uh

im sure you know-

||its a programming lang||

its a prog language, that is all i know...

or that info is wrong...

[fiery cosmos]

i dont understand what the fuck this man is trying to say here

yea
thats what it is
a programmign language

[fiery cosmos]

yea..
the vast majority of people don't know

but he/she and the person he/she is talking to definitely do

thats python

mate im the guy who doesnt know how to use excel i found this on discord servers

o

this server is for programming languages (mainly used for support)
It's probably not the thing for you

[fiery cosmos]

Best to ask your questions in #python-discussion , this channel is for discussions on algorithms

[fiery cosmos]

Though O(n^2) is big O notation for saying that the time that algorithm takes is proportional to the square of the size of the input (which means it's kinda slow)

[tepid bolt]

Is there any tutorials on how to calculate time complexity in python?

[mild dove]

omg yeah, I didn't know that it is a DP problem

[raven kraken]

Guys google just dropped its DSA course using Python on Udacity. Go enroll now

[feral palm]

any idea on this

[supple peak]

I want an idea how to build a logic for multiple smtp servers.. If one disconnects or gives error then we connect another.. [We have a list of smtp servers].. After each connected we send email.. If servers disconnects it reconnect to another smtp and then resume sending emails... How can i achieve this? Anyone have some idea, experience or some sample code snippets..

[drowsy kite]

Shouldn't the height be 3?

[agile sundial]

yes

[drowsy kite]

Thank you

[hollow iron]

anyone understand how to use hashlib and hmac?

[rough wharf]

hello

could someone help

[drowsy kite]

Is A) different from B)?

If so, why?

[lethal walrus]

hello does anyone know how to order numbers from an array and get the ordered numbers into a new array

[grizzled schooner]

!e python has a sorted() function which returns a list with the sorted version of an iterable. eg.

l = [3, 2, 1]
l2 = sorted(l)
print(l)
print(l2)

[halcyon plank]

@grizzled schooner :white_check_mark: Your eval job has completed with return code 0.

001 | [3, 2, 1]
002 | [1, 2, 3]

[mild dove]

is this not 4? 12 -> 10 -> 9 -> 7

[drowsy kite]

Apparently, the definition of height of a BST varies from place to place. Some say its the number be edges from the root node to the farthest leaf node, while others say its the number of nodes from the root node to the farthest leaf node. So, depending on the definition you are referring, it can be either.

[lethal walrus]

this is the array

and i want to use this function

to calculate the distance between to numbers

and put it in a new array in order

however im stuck

[mild dove]

ah, make sense now. thank you

[covert yew]

Can i ask a panda related question here?

[mild dove]

something like this? ordered_result = [ll_to_distance_matrix(i) for i in array] ordered_result.sort()

[idle pier]

I thought they been having that already

[grizzled schooner]

you may get a better response if you ask in #data-science-and-ml or a help channel

[covert yew]

aight

[cunning rock]

guys

is

the call stack in python

like in built to python?

[agile sundial]

of course

[cunning rock]

oh ok

ty

[raven kraken]

The one that I am talking about is a free one

[thorny vector]

hi guys

so I made a program on binary search tree

and wanted to make a function to calculate its depth

but for some reason the loop is running infinitely

should I send the code here?

[jolly mortar]

yes

[halcyon plank]

Hey @thorny vector!

Uh-oh! It looks like your message got zapped by our spam filter. We currently don't allow .txt attachments, so here are some tips to help you travel safely:

• If you attempted to send a message longer than 2000 characters, try shortening your message to fit within the character limit or use a pasting service (see below)

• If you tried to show someone your code, you can use codeblocks
(run !code-blocks in #bot-commands for more information) or use a pasting service like:

https://paste.pythondiscord.com

Hey @thorny vector!

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

[thorny vector]

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

[thorny vector]

here, this is the link

the function is on line 85

it runs infinitely

[jolly mortar]

temp = self.left
self.left never changes, temp wouldn't become None

temp = temp.left should work

[thorny vector]

AttributeError: 'int' object has no attribute 'left'

[jolly mortar]

and the initialisation should be temp = self

[thorny vector]

def calculate_depth(self):
        count=0
        temp=self.data
        while self.data is not None:
            count+=1
            self.data=self.data.left
            print("hi")
        return count

i did this

but got the same error

[jolly mortar]

the point of the while loop is that temp should be updated to its left child in each iteration

the data attribute is irrelevant in this function

temp = self
while temp is not None:
  ...
  temp = temp.left

[thorny vector]

yep this worked

thank you so much 😄

wait

hold on

@jolly mortar

the function should give the max depth right

[jolly mortar]

yeah?

[thorny vector]

like the depth for this is 4

[jolly mortar]

oh, i assumed your trees would always be balanced

[thorny vector]

oh

any fix for that?

[jolly mortar]

i'd just do this recursively then

depth of the tree is max(depth of left child, depth of right child) + 1

[thorny vector]

so should I create another function for checking children

[jolly mortar]

and the base case would be depth of a node where both children are None is 0

wait am i confusing terminology

[jolly mortar]

the height of such a node would be 0, not depth*

[thorny vector]

oh

but height and depth are the same thing right

[jolly mortar]

iirc depth is counted from the root and height is counted from the leaf

[thorny vector]

oh

okay

[thorny vector]

I'll try this

[dark osprey]

def median_of_three(list):
    first = list[0]
    middle = list[math.ceil(len(list) / 2)]
    last = list[-1]
    median = statistics.median([first, middle, last])
    return median

def partition(arr,left,right):
    pivot = arr[left]
    i = left - 1
    j = right + 1
    while (True):
        # Find leftmost element greater than
        # or equal to pivot
        i += 1
        while (arr[i] < pivot):
            i += 1
        # Find rightmost element smaller than
        # or equal to pivot
        j -= 1
        while (arr[j] > pivot):
            j -= 1
        # If the two pointers meet.
        if (i >= j):
            return j
        arr[i], arr[j] = arr[j], arr[i]

If I were to change the pivot to median_of_three(list), how would I go about that?

[fiery cosmos]

+1 to hsp's answer and more detailed answer can be found here.
https://stackoverflow.com/questions/2603692/what-is-the-difference-between-tree-depth-and-height

[fiery cosmos]

theoretically speaking, code would not change a lot IMO(or at all if I'm not mistaken), it is also shown that taking pivot randomly also helps. i mean all that happens at the end is pivot gets its right position.
Also right here means that, it is right at its position which we will find in final sorted array and the bigger/equal elements(not yet sorted) are on right and smaller/equal(not yet sorted) elements would be on left.

[fiery cosmos]

would someone be able to explain to me please how this function is counting the number of nodes? if i could get tagged in the response that would be great!

[jolly mortar]

the number of nodes in a binary tree is the number of nodes in its left subtree + number of nodes in its right subtree + 1 (for itself)

and the base case is that the number of nodes in an empty tree (i.e. root is null/None) is 0

[fiery cosmos]

ah so the root would be 1 and so would the left and right node?

[jolly mortar]

the number of nodes in the left subtree and right subtree are found via recursive calls to the same function

and 1 is added to the sum of those to represent the root node

[dark osprey]

But would I need to swap the median index and the right index?

[fiery cosmos]

right okay thanks for explaining!

[fiery cosmos]

Why don't you just try it and just take an example and figure out? I think it would need bit of conditioning since the place where it is needed may be needed in left subarray or right subarray.

[dark osprey]

Will do! Cheers

[maiden bobcat]

Hello, can someone please recommend me a book on data structures and algos?

Someone recommended me “The Algorithm Design Manual”, what do you think about it or what did you use to gain more knowledge on data structures

[shut breach]

there's some in the pins

[wet ledge]

Hello, I have super uber noob question on help-potato, can someone help me ?

[eager cargo]

Can I use Pandas to search for column values that include a wildcard?

I'm close but can't get it to find the right results

pdA = pd.read_csv('file.csv')
pdB = pdA[pdA['Email Address'] == '*company.com']
print(pdB)
None```

[eager cargo]

Here's the trick:

pdB = pdA[ pdA['Email Address'].str.endswith('company.com')]

[serene hemlock]

Does anyone know the syntax of class LargerNumKey(str)? passing "str"

class LargerNumKey(str):
    def __lt__(x, y):
        return x+y > y+x
        
class Solution:
    def largestNumber(self, nums):
        largest_num = ''.join(sorted(map(str, nums), key=LargerNumKey))
        return '0' if largest_num[0] == '0' else largest_num

[cold mulch]

!e
This is how you inherit a class. Inheriting a class entails inheriting its methods*, access to super (https://realpython.com/python-super/ is a great article on super), etc.

the syntax for it is
Class(class_to_inherit_from)

The code below would show that method is called and works with an instance of B even though we didn't explicitly define it there because it exists in A

class A:
  def method(self):
    print("Calling from A!")

class B(A):
  pass

b = B()
print(b.method())

[halcyon plank]

@cold mulch :white_check_mark: Your eval job has completed with return code 0.

001 | Calling from A!
002 | None

[serene hemlock]

Thank you. So is this OOP concept?

[cold mulch]

Yep!

[serene hemlock]

Thanks 🙂 Newbie so no idea in programming

[cold mulch]

No problem! If you want me to explain it more in depth I’d love to

[serene hemlock]

@cold mulch i dont even know what to ask. your sample code was very clear.

[unique dirge]

so

im doing this algorithm question

and i need to return 2 indexs that add up to a target value

and they cannot be the same index

def find_addends_array(target,array):
    xindex = 0
    missing_num = 0
    missing_pos = 0
    list2 = []
    for x in range(len(array)):
        xindex = x
        if target > 0:
            missing_num = target - array[x]
        elif target < 0:
            missing_num = target + array[x]
        if missing_num in array:
            missing_pos = array.index(missing_num)
            if missing_pos == xindex:
                for i in range(len(array)):
                    if array[i] == array[x]:
                        missing_pos = i
                        if missing_pos == x:
                            continue
            else:
                list2.append(x)
                list2.append(missing_pos)
                return list2
#test case:
print(find_addends_array(6,[4,3,3,6]))

the test case returns

[2,1]

but i expected [1,2]

can someone explain plz

[idle pier]

hello folks, when using two pointers like l,r = 0,len(somethingHere)-1
when for example doing a Binary Search,
while l < r:
I sometimes dont know when to use either just < or <=

[left inlet]

Hello! How to move an iterator forward in 5 steps?
I use this code:

for i in string:
    for x in range(5):
        next(i)```
How to optimize this code?

[flat sorrel]

Don't use a for loop to iterate through the string, instead use a while loop

usually a for loop indicates that the iterable is only advanced once per iteration

if you plan to advance the iterator a variable number of times in each iteration, a while loop is more appropriate

This is a bit of a silly example but it demonstrates how you can do that

!e

from random import randint
from string import ascii_lowercase

it = iter(ascii_lowercase)
while True:
    try:
        substr = ''.join(next(it) for _ in range(randint(1, 6)))
        print(substr)
    except StopIteration:
        break

[halcyon plank]

@flat sorrel :x: Your eval job has completed with return code 1.

001 | abc
002 | defg
003 | hijk
004 | lmnopq
005 | rstuvw
006 | Traceback (most recent call last):
007 |   File "<string>", line 7, in <genexpr>
008 | StopIteration
009 | 
010 | The above exception was the direct cause of the following exception:
011 | 
... (truncated - too many lines)

Full output: https://paste.pythondiscord.com/noyuweceyi.txt?noredirect

[left inlet]

Thanks. But is it any way to move an iterator in n steps?

[flat sorrel]

you just call next (n times) as you have shown above

[left inlet]

A way without using for loop?

[flat sorrel]

I don't think you can do that

If you want convenience you can wrap it in a custom function

but you still have to use a for loop in that function

[left inlet]

ok, thank you

[flat sorrel]

actually

Hmm

[flat sorrel]

There is a built in function in itertools that can do that

nvm

it's listed as a recipe

def consume(iterator, n=None):
    "Advance the iterator n-steps ahead. If n is None, consume entirely."
    # Use functions that consume iterators at C speed.
    if n is None:
        # feed the entire iterator into a zero-length deque
        collections.deque(iterator, maxlen=0)
    else:
        # advance to the empty slice starting at position n
        next(islice(iterator, n, n), None)

according to the documentation

[left inlet]

Thabks

[gleaming anchor]

hello guys here is my question

In the file, you will find test data of 50 jobs, each of which is associated with a processing length p_j and release (arrival) time r_j. Job j cannot start its processing before r_j. We want to construct a processing schedule such that the sum of job completion times is minimum.

Question 1. Enumerate all feasible solutions and find the best one. Try the data sizes 8, 10, 11, 12, ... that you can solve for.
Question 2. Apply the SRPT (shortest remaining processing time first) algorithm to find an optimal solution value of the preemptive version. Compare the solution values with the optimal values of Question 1.

is it possible to use SJF to answer the first question? or there are other ways to solve it? thanks!

[rough wharf]

can someone tell me how to modify quick sort to find the last 20 greatest numbers

[eager cargo]

I'll add to the questions lol. If I use Pandas to merge data, is there a way for it to show me which columns were different?

[idle pier]

Hello folks, the runtime and spacetime is O(n) correct?

def isAnagram(self, s: str, t: str) -> bool:
        counter = {}
        
        for char in s:
            if char in counter:
                counter[char] += 1
            else:
                counter[char] = 1
        
        for char in t:
            if char in counter:
                counter[char] -= 1
            else:
                return False
                
        for val in counter.values():
            if val != 0:
                return False
        return True```

[agile sundial]

yes

[rich aspen]

can someone help me?

if u can enter on a voice chat is better, tks

[idle pier]

Hello folks am currently doing 733. Flood Fill, this is the solution

def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        
        curColor = image[sr][sc]
        height = len(image)
        width = len(image[0])
        
        def dfs(sr,sc):
            if 0 <= sr < height and 0 <= sc < width and image[sr][sc] == curColor and image[sr][sc] != newColor:
                image[sr][sc] = newColor
                dfs(sr+1,sc)
                dfs(sr-1,sc)
                dfs(sr,sc+1)
                dfs(sr,sc-1)
        dfs(sr,sc)
        return image```
For this part,
`if 0 <= sr < height and 0 <= sc < width`
its basically checking that we are not out of bounds of the matrix, correct?

[shut breach]

looks like it

[summer elbow]

i need some quick help

is there any way i could edit properties of an object from the user end?

i.e, let the user edit the properties of an object

[dim maple]

Doh!!! This is the wrong channel for this...

Thought I was in general... my bad... will move. moved to #python-discussion

[sinful juniper]

Is anyone give star in my GitHub

[vagrant path]

Guys where can i learn basic-adv DSA for free?

[fiery cosmos]

See the channel pins.

[sturdy oracle]

hello do you have free time?

[agile sundial]

"basic-adv"?

[old rover]

hello am dumb

over here

the branching factor is 2 bc there's two recursive function calls?

bc i think

if there was just one function call

it would be a straight line down

does that mean if there were three different recursive function calls there would be a branching factor of 3?

so like

O(3^n)?

where n is the input?

or the height of the recursive tree

[agile sundial]

mhm

[old rover]

ohhh

good i think i'm getting it now

shoutout to free code camp their videos are really good

idk why i didn't use their videos sooner

[keen hearth]

Random question: am I right in thinking Θ(n!) = Θ(n^n) ?

[shut breach]

n! is obviously O(n^n), but I don't think n^n is O(n!)

[agile sundial]

ya I agree with scoff

[onyx parrot]

At its core, permutation algorithms are quite complicated

I only know the top-down approach but that notebook made me consider stuff I've never even thought about: https://www.kaggle.com/ryanholbrook/getting-started-with-santa-2021

[idle pier]

Hello folks, am doing 64. Minimum Path Sum on leetcode
I found this solution

def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        
        for i in range(1,m):
            grid[i][0]+= grid[i-1][0]
   
        for i in range(1,n): 
            grid[0][i]+= grid[0][i-1]
            
        for i in range(1,m):
            for j in range(1,n):
                grid[i][j] += min(grid[i-1][j],grid[i][j-1]) 
        
        return grid[-1][-1]```
can someone explain what exactly is going? This the first time I actually dont fully understand the solution since I first started a few months ago lol

[shut breach]

it's calculating the minimum path to each point in the grid

and then returning the bottom right value

think of it backwards, you're in the bottom right
you either came from up or to the left, and the shorter path is the one with the smaller value

grid[i][j] += min(grid[i-1][j],grid[i][j-1])

that is true of every cell in the grid

[idle pier]

ok, so the first for loop is adding all the numbers in the first row and the second for loop its adding all the numbers in the first column

[shut breach]

yes, in that row and column there is only one valid path to each cell

so you can immediately calculate all of them

then those are used to calculate the rest

[idle pier]

hmmmm

[shut breach]

imagine you're in the bottom right and you know the minimum path to both grid[i-1][j] and grid[i][j-1]

then the minimum path to you is a simple matter of choosing the smaller one

now how did you already know grid[i-1][j] and grid[i][j-1]?
through exactly the same logic

every cell is the bottom-right corner of a rectangle

and you're filling them out in an order such that every cell in that rectangle is already filled out by the time you get there

it might help to think of this as a recursive solution, the only difference here is that instead of calling the function to calculate an answer for you, that answer is already calculated and recorded in the grid

[idle pier]

ok, so we are starting at the bottom right which is 1 which is grid[2][2]. Is this correct?

[shut breach]

your code isnt actually starting there

i was just having you imagine being there having already calculated all the other cells, to show you why calculating all the other cells first would help you

[shut breach]

@idle pier does that make sense?

[idle pier]

umm a little lol, still trying to understand it

[shut breach]

do you think it would help to see it as a recursive function?

[idle pier]

umm maybe

[shut breach]

!e

from math import inf
grid = [[1,2,3],[4,5,6]]
h = len(grid)
w = len(grid[0])

def minpath(i, j):
    if not (0<=i<w) or not (0<=j<h):
        return inf
    if (i,j) == (0,0):
        return grid[0][0]
    return grid[j][i] + min(minpath(i-1, j), minpath(i, j-1))

print(minpath(w-1, h-1))

[halcyon plank]

@shut breach :white_check_mark: Your eval job has completed with return code 0.

12

[shut breach]

this is doing exactly the same calculation, except it starts at the end and backtracks to calculate what it needs

whereas your code starts at the beginning and builds up the solution as it goes

[idle pier]

hmm ok ok, am getting a better idea now lol
Iet me double check if am understanding your solution correctly
the first if is checking its out of bounds, the sec ifam a little lost and after its passes all the if's, it returns the min path?

my brain aint working properly today lol

[shut breach]

the second is the base case of the top left corner

it has its own path length, so we can just return that

min(minpath(i-1, j), minpath(i, j-1))
this is choosing whether to go up or left, depending on which is shorter
and this adds the current cell's weight to the chosen path's length
grid[j][i] +

[idle pier]

hmmmmmm ok ok, yea this solution makes a whole lot more sense to me

[shut breach]

right, so imagine if you just already had access to the results of these recursive calls ahead of time
minpath(i-1, j), minpath(i, j-1)

[maiden willow]

Can anyone tell the roadmap of learning python for begginer s

[thorny vector]

I learned from Corey Schafer's youtube channel

Great teacher

Hi guys, about the google course on Udacity on DSA

Will I get a certificate after completion?

[lean junco]

how to do these type of question

[runic tinsel]

so 4 elements total?

just look into every case

[lean junco]

how many cases i mean

3?

[runic tinsel]

3 cases
ABBA , ABAB , AABB

but maybe some are more common

I'm not sure what's the answer

[lean junco]

this is wht i found

is this correct?

[runic tinsel]

sure

(3+3+2) / 3

[lean junco]

i dont get the combination part

[runic tinsel]

that's what I thought

it's just 6 if you count ABBA , ABAB , AABB and the mirror

[lean junco]

yeah but lets say if i have2 array of 4 elemnt

then how many possibities

8c2?

[runic tinsel]

8c4

so yeah, 35 cases would need some other way

[fiery cosmos]

I mean @lean junco i hope you understood why 4 came over there.

[lean junco]

i didnt

plz explain

[runic tinsel]

you choose 4 letters to be A making the rest B

8 choose 4

it's in the name

[lean junco]

thats you teachers way right?

[runic tinsel]

the what

[lean junco]

"choose"

combination means order matter or it doesnt?

i forgot

[runic tinsel]

no order

[fiery cosmos]

Well in simple manner, out of n distinguish numbers if you want to group them in half halfs then the total nunber of possible solutions would be Nc(N/2)
Please note that we are using c here because for us, groups like a1a2 can be considered as a2a1 and not different.

[lean junco]

on point

[fiery cosmos]

Now read this example. Example makes it very clear.

[runic tinsel]

i didn't get that

[lean junco]

you hit the bulls eye in my brain

[fiery cosmos]

Oh my bad. What part did you not get?

[lean junco]

sort of asian teachers way you can say

[fiery cosmos]

Well i am asian. Lol.

[lean junco]

me too thats why resonance

[runic tinsel]

i didn't get what's a1a2

[lean junco]

he meant order doesnt matter

12 same as choosing 21

[runic tinsel]

yeah within a group, so 12 is 21

exactly

[fiery cosmos]

Since we are gonna take sorted, order won't matter.

[lean junco]

thx guys

[runic tinsel]

why is there "a" twice between them is unclear

[fiery cosmos]

Oh yes that. I meant a1,a2

a1 and a2

[runic tinsel]

aha i see

[fiery cosmos]

Can I use Python for competitive programming and contests? I know that c++ is preferable but is Python really bad and I must learn c++?

[agile sundial]

python is generally too slow

[old rover]

there must be a mistake here

it should be 2,0

this is the grid traveler problem

where m the first parameter is rows and n the second parameter is columns

moving down would make the rows go down by one moving right would make the cols go down by one

base cases are when either m or n is zero meaning there's zero ways and it's an impossible situation or it's 1,1 meaning one way

def g_t(m,n):
  if m == 1 and n == 1:
    return 1
  if m == 0 or n == 0:
    return 0
  return g_t(m-1,n) + g_t(m,n-1)

print(g_t(2,3))

here's the brute force solution

memoizing this brute force solution would involve putting a dictionary and storing m and n as inputs

[old rover]

def g_t(m,n,memo={}):
  key = "m" + "," "n"
  if key in memo: 
    return memo[key]
  if m == 1 and n == 1:
    return 1
  if m == 0 or n == 0:
    return 0
  memo[key] = g_t(m-1,n,memo) + g_t(m,n-1,memo)
  return memo[key]

print(g_t(2,3))

running into an issue here

why am i only getting 2

and not 3

everything looks the same to me

it could be indentation

nope idk why this won't work

oh

see i put a return value

too early

that is interesting

bc he returns it early on and everything's fine

yeah now it works fine

def g_t(m,n,memo={}):
  key = "m" + "," "n"
  if key in memo: 
   memo[key]
  if m == 1 and n == 1:
    return 1
  if m == 0 or n == 0:
    return 0
  memo[key] = g_t(m-1,n,memo) + g_t(m,n-1,memo)
  return memo[key]

print(g_t(2,3))

print(g_t(3,3))

nope

nope g_t(18,18) takes way too long for it to be memoized

yea idk

[agile sundial]

what's the grid traveler problem

[agile sundial]

that doesn't seem to be python... ¯_(ツ)_/¯

[old rover]

it was JS

[agile sundial]

can't you just solve this in O(n + m) with combinatorics?

[old rover]

with what

[vocal gorge]

I wouldn't be surprised if you could solve it in O(1) by using some fancy math

[old rover]

what am i doing wrong w memoizing it here

[vocal gorge]

nothing

[agile sundial]

you need to calculate factorial of some numbers, so it's not super fast, but faster than actually simulating

[old rover]

but it should give me a 3

not a 2

i thought it would be indentation or a return that's too early but that's not the issue

[fiery cosmos]

Totally depends on website tho btw. Yes python is slow. But some websites have different matrices for each language. Leetcode has different matrices for each language. You are compared with py solns if you submitted py soln.

[agile sundial]

maybe you're being tripped up by mutable default args?

[old rover]

possibly

bc i passed a memo dict in the parameters?

strange

[fiery cosmos]

Thank you, I appreciate that. I think you can't add a problem aimed to be solved in C++ and allow other languages and expect from them a fast solution. That makes sense

[agile sundial]

your memo key is the same on each call

if key in memo: 
   memo[key]
``` also...this does nothing

[fiery cosmos]

I have kind of not seen problems aimed to a certain language. I just mean while time complexity can be compared, actual time of code can't be compared between languages.

[agile sundial]

in many competitions, you will need to optimize your python solution more than say, a cpp solution

[old rover]

what

ugh

i'll look at it later

[grizzled schooner]

the key is always the string "m,n", it doesn't use the actual values of the variables m and n

[old rover]

OH

[grizzled schooner]

hydroxide

[old rover]

def g_t(m,n,memo={}):
  key = str(m) + str(n)
  if m == 1 and n == 1:
    return 1
  if m == 0 or n == 0:
    return 0
  memo[key] = g_t(m-1,n,memo) + g_t(m,n-1,memo)
  return memo[key]

print(g_t(2,3))

print(g_t(3,3))

print(g_t(18,18))

something like this?

no wait

wait i think i'll figure it out

[grizzled schooner]

you could just use a tuple or something

[agile sundial]

why not use a tuple instead of using some js hack

[old rover]

def g_t(m,n,memo={}):
  key = (m,n)
  if m == 1 and n == 1:
    return 1
  if m == 0 or n == 0:
    return 0
  memo[key] = g_t(m-1,n,memo) + g_t(m,n-1,memo)
  return memo[key]

print(g_t(2,3))

print(g_t(3,3))

print(g_t(18,18))

[agile sundial]

by "does nothing" i meant the check is useful, but you don't do anything inside of it

[old rover]

i think it's a base case

[agile sundial]

it's not a base case

[old rover]

hm

[agile sundial]

that's your check to see if you've computed that already

[old rover]

there must be something wrong w the memoized solution bc g_t(18,18)

takes eons

[agile sundial]

because you removed the memoizing

[old rover]

def g_t(m,n,memo={}):
  key = (m,n)
  if key in memo: 
   memo[key]
  if m == 1 and n == 1:
    return 1
  if m == 0 or n == 0:
    return 0
  memo[key] = g_t(m-1,n,memo) + g_t(m,n-1,memo)
  return memo[key]

print(g_t(2,3))

print(g_t(3,3))

print(g_t(18,18))

[agile sundial]

memo[key] doesn't do anything

[grizzled schooner]

  if key in memo: 
   memo[key]
``` consider what this code accomplishes

[old rover]

if the key is in the memo

the value of the key is returned

oh

i'm missing a return

ah yes