algos-and-data-structs

[regal spoke]

For example 12 vs 0b1100

[restive harbor]

damn, I feel dumb lol

you're right

but no

wait

haha

how do you explain the result of my code then ?

[regal spoke]

You are comparing two very different things

and unsurprisingly, you find that they are different

[restive harbor]

your example convinced me lol

thanks a lot, I got confused

[stiff quartz]

I ended up learning merge split treaps as well for curiosity

For my use case,

it ended up being 20% slower than my SQRT decomposition solution 💀

but I assume this is because the sqrt decomposition doesn't have an ounce of recursion

and i implemented the treap with full on recursion

Why is python/pypy recursion "so slow", is it purely the lack of tail call optimisation*?
* this would actually only help for my inorder traversal, the rest wouldn't benefit from it

[wraith ridge]

Are you familiar with recursion and how it works?

[regal spoke]

You could try the iterative implementation I posted earlier https://github.com/cheran-senthil/PyRival/blob/master/pyrival/data_structures/Treap.py

[regal spoke]

in python you can't solve it for sure
I really want to try solving this in Python

Is it fine if I share this problem/link with some other people?

Want to see if people can find some really smart algorithm for it

It is definitely possible to solve this is O(n sqrt n) time and O(n) memory (assuming n = q)

[hoary flare]

Hey y'all, so I've get given a byte array and I have to compress it to a byte array and decompress it to a byte array. I think huffman encoding is the way to go, but I was hoping that someone had an idea of how I could use one of the LZ algorithms to compress it. I don't think it's possible because there's not really a way to indicate a match, but I was interested to see if anyone had any ideas.

[solemn moss]

sure

[solemn moss]

yeah, i wrote it and it works
not really fast tho, but it can be written better + i have no idea which constants to put

[kind jolt]

not that much, im still stuck to that problem

how can i improve?

[stiff quartz]

When I read « you can’t solve it in Python » I knew that would tick you

[regal spoke]

Yes

[stiff quartz]

There are some ICPC gym problems I’ve done that have 0.1s time limit

And for which the cpp takes 80 ms

[regal spoke]

My current plan is to solve it with an unusual application of mo where queries are sorted using (q_ind, r)

[regal spoke]

I don't care about those

[regal spoke]

There is this problem too https://codeforces.com/contest/1354/problem/D

Stupidly low memory limit

[stiff quartz]

Whenever you do standard Mo you have to sort tuples of length 3 right (l, r, idx)? Is this super slow in Python? I think you mentioned that once, in those cases would you do radix sort to speed it up? (Would that even speed it up)

[regal spoke]

It is, but the sqrt cost of mo is also expensive

So usually it doesn't matter

[stiff quartz]

Fair enough

Makes sense

[regal spoke]

But for that problem, I'm planning on sorting based on (idx, r) instead of (l, r)

Which is a really funny application of mo

[kind jolt]

im stuck at this, i don't really know how to discover how many blocks go down

[rancid idol]

Guys when it comes to Master Theorem I keep getting confused about things. First of all I'd really appreciate it if someone could tell me a site or youtube video that clearpy explain all the variables with examples from code. Most of the resources online just assume everything is given.

Aside feom that lets say I have a recursive function which uses a helper method. I didvide the problem by 2 each time so in this case Ig my a=b=2. I read that f(n) is every other cost in the algoritm other than the recursive. In my helper metod I have a for loop with the T(n)=O(n). The rest of the code in the recursive funtion is O(1). So is f(n) n^2 or 1? What if I had used a built in function with the time complexity of n^3. Would that still be counted in f(n). Thanks beforehand!

[regal spoke]

Actually, I talked to some people about this. Turns out there is a very short and nice Python implementation out there
It runs in O(n log^2 n)

!e

from bisect import bisect_left as bl

def build_SA(S):
    n = len(S)
    for p in range(n.bit_length()):
        O = sorted(S)
        S = [bl(O, c) for c in S]
        S = [(S[i], S[(i + (1 << p)) % n]) for i in range(n)]
    return sorted(range(n), key = S.__getitem__)

S = 'banana$'
SA = build_SA(S)
for i in SA:
    print(S[i:])

[halcyon plank]

:white_check_mark: Your 3.12 eval job has completed with return code 0.

001 | $
002 | a$
003 | ana$
004 | anana$
005 | banana$
006 | na$
007 | nana$

[regal spoke]

It uses the cyclic shift method I was talking about

[half plume]

Then what is this algorithm's complexity?

The algorithm need to run in one sec in case length == 10^6.
Are you sure your algorithm can run in a sec to solve this problem?

🙂

[regal spoke]

As I said #algos-and-data-structs message , it runs in O(n log^2 n)

In C++ I could totally see this run in 1s for 1e6

But not in Python

[half plume]

I already know the alogrithm but I want (n * log n)

[regal spoke]

I kind of doubt even n log n would run in 1 s in Python for 1e6

My O(n) SA-IS implementation runs in about 1s for 1e6

[half plume]

Um, I heard c++ is 4 times faster than python.

But I think it doesn't matter.

[regal spoke]

It is usually far faster than that

It can often be 100 to 1000 times faster

[half plume]

where are you from?

[regal spoke]

Sweden

[half plume]

Great!

How come you know c++ so well?

[regal spoke]

I've done a lot of competitive programming

[half plume]

Me too.

Which university did you graduate?

Or now student?

U there?

[regal spoke]

Those are a little bit too personal questions for me

Especially talking with someone I don't know in a public place like this

I'm a pretty public person. Just google my name if you are interested

[tribal vine]

I like the new icon

[wraith ridge]

Here is the solution - take note of how many times you are calling F2 within F2 . You are adding to the stack every time you move onto a blue square going up. Then once you reach a red square you stop adding to the stack. Now the F2 functions you called numerous times can actually be completed and thus the last arrow in the F2 function can now be accessed and the ship start going back down the same amount of blue squares you went up. This is the essence of recursion and how recursion keeps adding to the stack (or in other words keeps calling itself) even though the function hasn't completely finished.

[kind jolt]

wow bro thanks a lot really, how could be better in algos, there’s some exercise that i would need to do?

[fallow agate]

Hi,
pls see the print statement in traverse_graph fn. The result of that print is:
4,5,4,3,2,1

def largest_component(graph):
    visited = set()
    count = 0
    for node in graph:
        count += traverse_graph(graph, node, visited, 0)
        

def traverse_graph(graph, src, visited, count):
    if src in visited:
        return 0
    visited.add(src)
    count += 1
    for neighbor in graph[src]:
        traverse_graph(graph, neighbor, visited, count)
    print(count)
    return count
    
largest_component({
  1: [2],
  2: [1,8],
  6: [7],
  9: [8],
  7: [6, 8],
  8: [9, 7, 2]
}) # -> 6

Now, see the print statement. i just moved it to largest_component fn. Even now, we should get same result right?
but, i get 1,1,1,1,1,1

def largest_component(graph):
    visited = set()
    count = 0
    for node in graph:
        count += traverse_graph(graph, node, visited, 0)
        print(count)

def traverse_graph(graph, src, visited, count):
    if src in visited:
        return 0
    visited.add(src)
    count += 1
    for neighbor in graph[src]:
        traverse_graph(graph, neighbor, visited, count)
    return count
    
largest_component({
  1: [2],
  2: [1,8],
  6: [7],
  9: [8],
  7: [6, 8],
  8: [9, 7, 2]
}) # -> 6

[haughty mountain]

this part seems suspicious

    for neighbor in graph[src]:
        traverse_graph(graph, neighbor, visited, count)

you're doing nothing with the return value

[fallow agate]

i dont rely on return value.

all i want it whenever we call this fn recursively, it is an indication that there is one new node through which we are travelling. hence in the fn traverse_graph, count += 1 which is doing the work.

[haughty mountain]

so why are you returning count then?

presumably you want to use the returned count from the recursive call

[fallow agate]

yes, take that count & add it to the count present in largest_component fn

[regal spoke]

Yep, very likely you'd want

    for neighbor in graph[src]:
        count += traverse_graph(graph, neighbor, visited, count)

Seems like a bug

[regal spoke]

but, i get 1,1,1,1,1,1

If you take a look at your current code, the traverse_graph(graph, node, visited, 0) call can only return 0 or 1

[fallow agate]

thats my question, where i went wrong?

[regal spoke]

#algos-and-data-structs message I think algmyr is correct

[haughty mountain]

[regal spoke]

Oh wait, maybe you dont know about a weird quirk in python

!e

def f(count):
  count += 1

count = 0
print(count)
f(count)
print(count)

[halcyon plank]

:white_check_mark: Your 3.12 eval job has completed with return code 0.

001 | 0
002 | 0

[regal spoke]

Doing += 1 on an integer inside of a function

will not increment its value outside of it

In python count += 1 is the same as count = count + 1

It doens't actually increment the underlying variable

[wraith ridge]

https://realpython.com/fibonacci-sequence-python/

That will help with understanding recursion.

Google “Data Structures and Algorithms in python”. There’s a bunch of courses free and paid. I can’t recommend any cause I have not tried them. I studied them in a bootcamp I attended years ago. I’m sure most of them are fine.

[regal spoke]

@fallow agate Do you see my point? They way you are recursively trying to increment count wont work in Python

The "correct" way to do it would be

def largest_component(graph):
    visited = set()
    count = 0
    for node in graph:
        count += traverse_graph(graph, node, visited)
        print(count)

def traverse_graph(graph, src, visited):
    if src in visited:
        return 0
    visited.add(src)
    count = 1
    for neighbor in graph[src]:
        count += traverse_graph(graph, neighbor, visited)
    return count
    
largest_component({
  1: [2],
  2: [1,8],
  6: [7],
  9: [8],
  7: [6, 8],
  8: [9, 7, 2]
}) # -> 6

[fallow agate]

first of all: we dont need any explicit return in python like this?

def f(count):
    count += 1
    return count


count = 0
print(count)
f(count)
print(count)

[regal spoke]

Whether you return count there doesnt matter

!e

def f(count):
    count += 1
    return count


count = 0
print(count)
f(count)
print(count)

[halcyon plank]

:white_check_mark: Your 3.12 eval job has completed with return code 0.

001 | 0
002 | 0

[regal spoke]

It is still going to stay 0

[fallow agate]

So, this is what happening:

count is local varible inside the fn traverse_graph --> even though i return that variable, it wont go.

right?

[regal spoke]

In python you cant modify the value of an integer

!e

x = 1
y = x
x += 1
print(x, y)

[halcyon plank]

:white_check_mark: Your 3.12 eval job has completed with return code 0.

2 1

[regal spoke]

Doing x += 1 just creates a new variable with the value x + 1

It doesn't actually modify x

[fallow agate]

it printed 1 --> which means x value modified right?

x = 0
x += 1
print(x)

[regal spoke]

The line x += 1 essentially creates a new varible (also called x) with the value x + 1

In python, you fundamentally cannot modify the value of an integer

The same is true for strings too

[fallow agate]

ok, so , it is mutable & immutable concept

below are immutable:
int
float
bool
complex
Strings
tuples
sets

[regal spoke]

Well sets are definitely mutable. Otherwise that list looks correct

[fallow agate]

it's ok, let python do python however it wants underneath the hood(i mean, let it create new variable assign 1/let it increment the old variable).

But, by the time i print, x value is getting printed as 1 right?

[regal spoke]

yes

[fallow agate]

so, i am getting incremented value at the end of the day & now coming to my program......

I am returning that increamented value. --> whether it is creating new count variable each time/ keep updating old count variable dont't matter. isn't it?

even though looking simple, pretty confusing 🤔

[regal spoke]

Had integers been mutable, then your inital code would have been correct.

But in Python ints are not mutable

The solution is to instead do something like this #algos-and-data-structs message

[haughty mountain]

!e

def largest_component(graph):
    visited = set()
    for node_id in graph:
        if node_id not in visited:
            count = traverse_graph(graph, node_id, visited)
            print('component of size', count)

def traverse_graph(graph, node_id: int, visited):
    if node_id in visited:
        return 0

    visited.add(node_id)
    count = 1

    for neighbor in graph[node_id]:
        count += traverse_graph(graph, neighbor, visited)

    return count

largest_component({
  1: [2],
  2: [1,8],
  6: [7],
  9: [8],
  7: [6, 8],
  8: [9, 7, 2]
})

[halcyon plank]

:white_check_mark: Your 3.12 eval job has completed with return code 0.

component of size 6

[fallow agate]

sorry.. could not really see the difference between
count += 1
&
count += some_fn()

I am comparing based on below criteria.
1.
In both cases count is int

In first case you are incrementing count value by 1 & then asigning back to count once again
In the second case also you are doing same, but instead of incrementing by 1 which is literally typed, you are getting that 1 as a return value from some_fn()

[haughty mountain]

!e this code is quite silly, bit the difference is more between

def f(count):
  count += 1
  return count

a = 0
f(a)
print(a)

b = 0
b += f(b)
print(b)

[regal spoke]

It is perfectly fine to increment count using count += some_fn().
But it is impossible to increment count by calling some function. Like,
some_fn(count), cannot change the value of count

[halcyon plank]

:white_check_mark: Your 3.12 eval job has completed with return code 0.

001 | 0
002 | 1

[fallow agate]

so, you mean to say in the below code --> the incremented count value from line 5 will not be passed to traverse_graph(graph, neighbor, visited, count) in 7th line?

def traverse_graph(graph, src, visited, count):
    if src in visited:
        return 0
    visited.add(src)
    count += 1
    for neighbor in graph[src]:
        traverse_graph(graph, neighbor, visited, count)
    return count

[regal spoke]

Yes, these two lines fundamentally cannot change the value of count

[regal spoke]

Btw maybe you are misunderstanding how return works

Return sets the value the you get from calling the function

!e

def f(x):
  return 5
x = 0
y = f(x)
print(x, y)

[halcyon plank]

:white_check_mark: Your 3.12 eval job has completed with return code 0.

0 5

[regal spoke]

In this code you don't store the return value of traverse_graph anywhere

So the return count inside of traverse_graph does absolutely nothing

It might as well just be return

[haughty mountain]

!return-jif

[halcyon plank]

Print and return

Here's a handy animation demonstrating how print and return differ in behavior.

See also: /tag return

[fallow agate]

you prepared this animation?

[fallow agate]

I completely understood.
But, my point is --> each time i call the traverse_graph fn --> this variable is getting incrementing, right?

[regal spoke]

I don't think I follow

[regal spoke]

The count += 1 increment on line 5 will be passed to the traverse_graph(graph, neighbor, visited, count) call on line 7

[fallow agate]

internet got lossed in the middle of me typing the message.

[regal spoke]

But the value of count will not change from the traverse_graph(graph, neighbor, visited, count) call

Since count is immutable

[fallow agate]

let me complete fully.

[fallow agate]

I completely understood. But, my point is --> each time i call the traverse_graph fn --> this variable is getting incrementing, right?

once all the recursive calls get completed, i am returning that variable here:

I am concisouly not relying on the return value.

but when the recursion call happens --> it is an indication that i came to new node, so i am incrementing count

And that count i am trying to send back as return value

[regal spoke]

It is true that count += 1 happens each time traverse_graph is called

But it currently doesn't do anything

Here is my tip: Don't have count be part of the recursive call.

#algos-and-data-structs message this is a much better way of doing it

[fallow agate]

i agree. at the end i am going to follow this.

just wanted to know whats wrong in my thingking so that next time will not repeat

each time this recrusive call is happening, the new updated count is getting passed

At the end of all the recursive calls, the final incremented count is what returned.

this is my understanding.

what is wrong here?

[regal spoke]

x = 123
some_function(x)

Just remember that no matter what some_function is doing here, the value of x (outside the function) will never change

Since x is an intger, and thus is immutable

Seems to me like you are thinking that you somehow can modify x this way, but you fundamentally cant

Going back to your code. This call does absoultely nothing to count. If it was 1 before the call, then it will stay at 1

[fallow agate]

NO

pls see..

after each call, i am seeing new count

at the end count is 5

[regal spoke]

You are looking at completely different count variables

[fallow agate]

@regal spoke isn't like this?

count is 5 as final answer of this algo?

🤷something is terriblly wrong in my underrstanding..

😦

and however hard work is needed, i will do to know this. you want me to read some article/youtube video etc to know what is happening?

becasue without even clearly knowing this(which is simple variables), no way i write good code.

[narrow mica]

I haven't been following for too long, but the count in traverse_graph and the count in largest_component are 2 different variables

your largest_component could look like this instead

def largest_component(graph):
  visited = set()
  AAAAA = 0
  for node in graph:
    AAAAA += traverse_graph(graph, node, visited, 0)
... # the same everything afterwards
```and it'd function the exact same as what you have now

[regal spoke]

Maybe count is 5 in the inner most call to traverse_graph. That doesn't matter. Because in the outer call to traverse_graph, count still has the value 1. So 1 is returned.

Here is a simple example that I hope will show you your missunderstanding

!e

def f(x):
  x += 1
  if x < 10:
    f(x)
  return x

print(f(2))

[halcyon plank]

:white_check_mark: Your 3.12 eval job has completed with return code 0.

3

[regal spoke]

In the inner most recursive call to f, x reaches 10, and 10 is thus returned (in the inner most call)

But that doesn't matter for the return value of f(2)

[fallow agate]

This made clear to me. Sorry for testing your patience.

So, this is what happening:

In the stack --> f(3) --> f(4) --> f(5) --> f(6) --> f(7) --> f(8) --> f(9) --> f(10)

Now, execution starts from top, so

f(10) --> f(9) --> f(8) --> f(7) --> f(6) --> f(5) --> f(4) --> f(3)

The mistake here is NO WHERE THE RETURN VALUES ARE BEEN COLLECTED

Where as when you do x += f(x) --> This works because we are collecting the return values & adding at at each recursive call.

right?

But, then you were telling about immutability concept & because of that x is not changing, which is nothing to do with the problem here, right?

[fallow agate]

Hi,
anyone find the problem in this shortest path algo?

[fallow agate]

def shortest_path(edges, src, dst):
    graph = build_graph(edges)
    shortest_distance = float("inf")
    curr_distance = 0
    for node in graph[src]:
        curr_distance = find_distance(graph, node, dst, set(), 0)
    if curr_distance < shortest_distance:
       curr_distance, shortest_distance = shortest_distance, curr_distance
    
def find_distance(graph, src, dst, visited, nodes_travelled):
    if src == dst:
        return 0
    if src in visited:
        return 0
    visited.add(src)
    nodes_travelled += 1
    for neighbor in graph[src]:
        nodes_travelled += find_distance(graph, neighbor, dst, visited, nodes_travelled)
    print(nodes_travelled)
    return nodes_travelled

def build_graph(edges):
    graph = {}

    for edge in edges:
        a,b = edge
        if a not in graph:
          graph[a] = []
        if b not in graph:
          graph[b] = []
        graph[a].append(b)
        graph[b].append(a)

    return graph

edges = [
  ['w', 'x'],
  ['x', 'y'],
  ['z', 'y'],
  ['z', 'v'],
  ['w', 'v']
]

shortest_path(edges, 'w', 'z') # -> 2

[regal spoke]

I would say there is a mix of both issues. Here is the same example as before but this time with a mutable data type (list)

!e

def f(A):
  A.append(1)
  if len(A) < 10:
    f(A)
  return A

print(f([]))

[halcyon plank]

:white_check_mark: Your 3.12 eval job has completed with return code 0.

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

[regal spoke]

Had x been mutable in my previous example, the result would be completely different (it would have printed 10)

[fallow agate]

so you say both these are separate variables? i mean, their memory addresses are different?

[regal spoke]

No. So what is actually happening is that doing something like count += 1 changes the memory address of count

[fallow agate]

🤯

[fallow agate]

ok, how does that affect here?

[regal spoke]

I dont understand what you are asking

[fallow agate]

i mean, how does the below thing created problem?

you were saying mutability was as issue. so, just trying to connect the dots & see

how does that mutability things affected my code & resulted in wrong answer

so, eveytime we write program, we need to keep thinking mutability & immutabily in mind 😦
apart from thinking how to solve problem, this aspect also should paralally running in mind?:(
dont know how u could able to acheive that... you are great

[fallow agate]

@regal spoke you were typing something, but suddenly stopped?

[regal spoke]

Was just going to say something like, you'll get used to it

[fallow agate]

@regal spoke any help about this?
already 5 hours gone for above problem, dont know how much time will go now 🤷

may be instead of telling me the solution, pls tell me how are you analysing & finding out the bug. tell me that process..

may be if you give some standard steps that i need to check one by one? that would be really helpfull.

i will follow them & find out the problem myself

[fallow agate]

i kept thinking what you said & i got you now....
if this count would have been mutable like list, the reference of list would have been passed to the traverse_graph fn, hence even though i dont collect the result, it would have worked fine.

but since it is immutable, the reference was not went instead only the value went to fn as parameter

this is what your intention?

[regal spoke]

yes

Infact your original code would have been correct had int been mutable

[stiff quartz]

Technically even when you send an int to a function you send a reference

It’s just that when you do count +=1 or count = 4 you assign a new reference to the variable count. That variable count used to contain a reference to the int you originally had but then don’t reference the int that the outside variable still references to.

!e

def modify_value(a):
    print(f"Inside function, id(a) before modification: {id(a)}")
    a = 5  # new reference for this a
    # instead of keeping same reference
    # and changing the value
    print(f"Inside function, id(a) after modification: {id(a)}")

a = 4
print(f"Outside function, id(a): {id(a)}")

modify_value(a)

[halcyon plank]

:white_check_mark: Your 3.12 eval job has completed with return code 0.

001 | Outside function, id(a): 140070701868968
002 | Inside function, id(a) before modification: 140070701868968
003 | Inside function, id(a) after modification: 140070701869000

[half plume]

If you wanna learn algorithm and data structure, pls come across to me with a bottle of wine. 🙂

[austere nymph]

Can you tell me the Space/Time complexity of this solution and explain why?

Leetcode Solution link:
https://leetcode.com/problems/repeated-string-match/solutions/5834648/simple-arithmetic-python-beats-95-no-loops-o-n-m

class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:

        a_len = len(a)
        b_len = len(b)
        
        if b in a:
            return 1
        
        if b in a+a:
            return 2

        if a_len < b_len:

            repeat = b_len//a_len
            
            if b_len % a_len:
                repeat +=1
            
            if a[0] != b[0]:
                repeat+=1

            if b in a*repeat:
                return repeat
          
        return -1

[fallow agate]

Guys, any one pls help me on this. dont tell me the answer, pls tell me houw would you debug, i will do same from next time

def shortest_path(edges, src, dst):
    graph = build_graph(edges)
    shortest_distance = float("inf")
    curr_distance = 0
    for node in graph[src]:
        curr_distance = find_distance(graph, node, dst, set(), 0)
    if curr_distance < shortest_distance:
       curr_distance, shortest_distance = shortest_distance, curr_distance
    
def find_distance(graph, src, dst, visited, nodes_travelled):
    if src == dst:
        return 0
    if src in visited:
        return 0
    visited.add(src)
    nodes_travelled += 1
    for neighbor in graph[src]:
        nodes_travelled += find_distance(graph, neighbor, dst, visited, nodes_travelled)
    print(nodes_travelled)
    return nodes_travelled

def build_graph(edges):
    graph = {}

    for edge in edges:
        a,b = edge
        if a not in graph:
          graph[a] = []
        if b not in graph:
          graph[b] = []
        graph[a].append(b)
        graph[b].append(a)

    return graph

edges = [
  ['w', 'x'],
  ['x', 'y'],
  ['z', 'y'],
  ['z', 'v'],
  ['w', 'v']
]

shortest_path(edges, 'w', 'z') # -> 2

Answer is 4, but expected is 2

[fallow agate]

i found one mistake

    if curr_distance < shortest_distance:
       curr_distance, shortest_distance = shortest_distance, curr_distance

this code should be inside the loop....

i will keep updating as soon as i find new bugs, if you see any, you also pls update

[regal spoke]

You are using the completely wrong algorithm here

What you want is called a BFS algorithm

[fallow agate]

yeah..i implemented using BFS

from collections import deque

def shortest_path(edges, node_A, node_B):
  graph = build_graph(edges)
  visited = set([ node_A ])
  queue = deque([ (node_A, 0) ])
  
  while queue:
    node, distance = queue.popleft()
    
    if node == node_B:
      return distance
    
    for neighbor in graph[node]:
      if neighbor not in visited:
        visited.add(neighbor)
        queue.append((neighbor, distance + 1))
        
  return -1
  
def build_graph(edges):
  graph = {}
  
  for edge in edges:
    a, b = edge
    
    if a not in graph:
      graph[a] = []
    if b not in graph:
      graph[b] = []
      
    graph[a].append(b)
    graph[b].append(a)
    
  return graph

it is working also..

its just that, i am trying in different way. you noticed any wrong?

[regal spoke]

The other code you posted is a DFS

which is completely different to a BFS

I dont think there is a way to make the DFS run within reasonable time complexity

[fallow agate]

its not about complexity, i just wanted to see how to make it work.

any way, looks complex, i am leaving it.

i will follow that BFS one

[regal spoke]

The algorithm for min distance is BFS if all edges have weight 1, or more generally dijkstra if the edges can have different weights

I dont think you will get anything from attempting to do things with a DFS

[narrow mica]

wdym by that
dijkstra's doesn't work with negative weights, period

use a diff algo like bellman-ford

[frosty stratus]

Hi guys, Im having a little issue with my assignment, I keep running into an assertion error with one of my functions but I cant seem to tell what the issue is. Could anyone please help?

could i private message anyone pls?

[lean walrus]

why not ask here?

[frosty stratus]

ah sure thing

https://paste.pythondiscord.com/SOWQ

[hybrid epoch]

Any good books on combinatorial optimization with examples written in Python?

[half plume]

HI

[scenic coral]

could someone help me walk through the CS50 credit problem
its in C language tho

[fallow agate]

Hi,
I am solving island count problem

def island_count(grid):
    rows = len(grid)
    cols = len(grid[0])
    




grid = [
  ['W', 'L', 'W', 'W', 'W'],
  ['W', 'L', 'W', 'W', 'W'],
  ['W', 'W', 'W', 'L', 'W'],
  ['W', 'W', 'L', 'L', 'W'],
  ['L', 'W', 'W', 'L', 'L'],
  ['L', 'L', 'W', 'W', 'W'],
]

island_count(grid) # -> 3

The idea is first navigate through grid using BFS

And during that navigation, if you find, land --> then apply DFS there. My question is: Why only DFS, not BFS in this case?

[narrow mica]

doesn't matter in this case

[narrow mica]

that sounds strange but ig it could work

[fallow agate]

could you pls brief a bit more, why doesn't matter

[fallow agate]

navigating by using BFS is strange?

[narrow mica]

explain more
implemented correctly, both dfs and bfs will correctly mark all connected Ls as visited
navigating grid by BFS is strange?
imo yeah, you could instead just iterate over every cell, when you find an unvisited L then start a d/bfs there

[fallow agate]

imo yeah, you could instead just iterate over every cell, when you find an unvisited L then start a d/bfs there

hmm...

right.

no need of any algo to just navigate grid

below code is enough

    rows = len(grid)
    cols = len(grid[0])
    for row in rows:
        for col in cols:
            print((row, col))

thx

btw,

https://pasteboard.co/CTv5g8PgFOWR.png

i executed in the same way many times. dont know what happned now.

may be i am overlooking somehing like spelling mistake etc

[narrow mica]

file name

.py

[fallow agate]

🤦‍♂️🤦‍♂️

[fallow agate]

I want to share one learning here.
Currently i am solving island count problem.
usually whenever i solve leetcode problems, i try to think whole problem at a time & during the process of coding get confused.
but, looks like it is better to have big picture in mind, but during the time of code, do it part by part
for example, when solving this problem, as a first step, our target is to just navigate the grid & what is there at each position

def island_count(grid):
    rows = len(grid)
    print(rows)
    cols = len(grid[0])
    print(cols)
    for row in range(0, rows):
        for col in range(0, cols):
            print((row, col), grid[row][col])

grid = [
  ['W', 'L', 'W', 'W', 'W'],
  ['W', 'L', 'W', 'W', 'W'],
  ['W', 'W', 'W', 'L', 'W'],
  ['W', 'W', 'L', 'L', 'W'],
  ['L', 'W', 'W', 'L', 'L'],
  ['L', 'L', 'W', 'W', 'W'],
]

island_count(grid) # -> 3

print it & see, this part is working/not
once this is successful, then proceed to next step.

Now, once again come back to problem & think. It says, find the islands --> island is indicated by L --> so, when we are navigating through grid, try to find are u encountering L in a cell --> you can achieve this by if grid[row][col] == L
So, programming is like: first we should have solution in mind in terms of english(whatever language) language
Then during the time of writing the code, it's about translating that English language into python(whatever language) language which interpreter understands.

---

How do u guys solve the problems?

---

[fallow agate]

sum_possible.py

def sum_possible(amount, numbers):
    if amount == 0:
        True
    for num in numbers:
        new_no = amount - num
        if new_no >= 0:
            if sum_possible(new_no, numbers):
                return True
    return False

print(sum_possible(8, [5, 12, 4])) # -> True, 4 + 4

some where i am making a small mistake....

[solemn moss]

You have just True instead of return True

[fallow agate]

Hi,
For the below graph

{
  1: [2],
  2: [1,8],
  6: [7],
  9: [8],
  7: [6, 8],
  8: [9, 7, 2]
}

This is the corresponding diagram for recursion. I my self drawed this in power point for 2 hours to understand the recursion. is it right?

Please note that this is DFS call only for key 1. For other keys named 2, 6, 9, 7, 8, once again DFS calls will be made similar to this. But i did not showed here.
https://pasteboard.co/gPoSi1AWuwPo.png

And the program is :

def largest_component(graph):
  visited = set()
  
  largest = 0
  for node in graph:
    size = explore_size(graph, node, visited)
    if size > largest:
      largest = size
  
  return largest

def explore_size(graph, node, visited):
  if node in visited:
    return 0
  
  visited.add(node)
  
  size = 1
  for neighbor in graph[node]:
    size += explore_size(graph, neighbor, visited)
    
  return size

@regal spoke

[haughty mountain]

if anything that is the tree rooted at 1

this would visualize the dfs recursion better

missed one red arrow between 8 and 2 😔

[grizzled trellis]

which book were you guys using to learn algo and data struct?

[haughty mountain]

||none||

[modern gulch]

https://en.wikipedia.org/wiki/Introduction_to_Algorithms is the (a?) classic. Old enough that I had it in Uni

I've heard good things about Goodrich (the Python edition): https://www.amazon.com/Structures-Algorithms-Python-Michael-Goodrich/dp/1118290275

[fallow agate]

one small correction in this. at the right side, when we visit 2, that 2 is already visited, hence no more calls. so, full fledged tree will look like

[haughty mountain]

oh wait

I just now saw what you put was not just the graph

[modern gulch]

In case you missed it, here's the tree for your code earlier: recursionvisualizer

[fallow agate]

saw it. thank you.

[fallow agate]

it's time for me to animate this & i will post in my blog. so that the beginners will not suffer like me to understand reucrsion.
unless you think with focus & patience, it's not that easy to understand the recursive calls, expecially we need keen observation to recognize the fact that the calls will be initiated from root node to leaf node --> where as, will receive values form leaf node to root node. it's all becaue underneeth the hood stack is used for recursion.

when someone understand this, then only they can do some code with the returned values inorder to solve the problem. otherwise it is just mugging

[fallow agate]

some more insights i found during this process:
As you can see, the visited variable is a set, since it is mutable object, only one set is used across the whole program.
If it is a dict / list, then also no problem.

But, if it is an other data type like string, then it will not work the same way

@modern gulch

[modern gulch]

The use of "set" isn't the issue. The issue is that you initialize it once and reuse the same object. You'd have same issue with a dict or list.

[fallow agate]

issue? there is no issue..

[modern gulch]

You said: "If it is a dict / list, then also no problem.". I'm saying: that's incorrect. The problem was where it was initialized, not that it was a set.

[fallow agate]

now, the way i initialized is ok?

[modern gulch]

Show code plz.

[fallow agate]

def largest_component(graph):
  visited = set()
  
  largest = 0
  for node in graph:
    size = explore_size(graph, node, visited)
    if size > largest:
      largest = size
  
  return largest

def explore_size(graph, node, visited):
  if node in visited:
    return 0
  
  visited.add(node)
  
  size = 1
  for neighbor in graph[node]:
    size += explore_size(graph, neighbor, visited)
    
  return size

[modern gulch]

Add a print sttement in explore_size:

print(f"{node=} {visited=}")

[haughty mountain]

fwiw, I would do this as

def largest_component(graph):
  visited = set()
  
  largest = 0
  for node in graph:
    if node not in visited:
      size = explore_size(graph, node, visited)
      if size > largest:
        largest = size
  
  return largest

through re-using the visited set and doing the check before trying to find the size, you get the size of each component exactly once

[modern gulch]

This is identical to the original code you posted here; #python-discussion message

[fallow agate]

yes. i am talking about that code only

[modern gulch]

So you understand it now? Just making sure.

[fallow agate]

looks like some miscommunication. Let's forget what happned previously.
Once pls see this code:

def largest_component(graph):
  visited = set()
  
  largest = 0
  for node in graph:
    size = explore_size(graph, node, visited)
    if size > largest:
      largest = size
  
  return largest

def explore_size(graph, node, visited):
  if node in visited:
    return 0
  
  visited.add(node)
  
  size = 1
  for neighbor in graph[node]:
    size += explore_size(graph, neighbor, visited)
    
  return size

Now, even if the visited variable is dict / list, they get mutated in the fn calls, hence only one object of set / dict / list will be maintained per program.

as of now you agree?

(This is becasue list, dict & set, all fall into the category of mutable objects)

[haughty mountain]

you couldn't even do the mutating actions on immutable objects in the first place

[fallow agate]

as of now i did not even bring the immutables into picture. just saying about set, list & dict

[haughty mountain]

if you passed an immutable object as an argument it would still only be one object

unless you create new ones

but yes, there is only one set being used in one call to largest_component

[fallow agate]

ok, so what you are saying is whether you pass mutable object/immutable object to a fn as a parameter, rererence of the object is passed in both cases. right?

[haughty mountain]

yes

[fallow agate]

ok now: This is where the difference comes in:

--> Scenario 1: You are passing mutable object as param --> changing that object inside the fn, but not returning the changed value --> Even though you did not returned the changed value, still you will see the changed value outside the fn, because set, list & dict are mutable(means, when we change the value inside the object new object is not created, instead the original is modified)

will proceed step by step.

as of now you agree with me/any deviations?

[haughty mountain]

if you do changes to that particular object like my_list.append(42), sure

but my_list = my_list + [42] would not affect the original object because it's creating a new one

in the case of immutables you can't do the first kind

[stiff quartz]

This is what I explained here #algos-and-data-structs message

[fallow agate]

for example, lets consider my_list = [1,2,3]

1. --> my_list.append(42) = [1,2,3,42]
2. -- > my_list = my_list + [42] = [1,2,3,42]

In both cases outputs are same, but case one same object modified, but case 2 new obejct created. right?

but, why this sort of behaviour? i am not sure.......

i mean, if there is some reason, then only the designers would have created this behaviour.

[haughty mountain]

my_list + [42] creates a new object

[fallow agate]

yes. but, why this sort of behaviour? i am not sure.......
i mean, if there is some reason, then only the designers would have created this behaviour.

[haughty mountain]

wdym this sort of behavior?

it would be very weird if this modified a

a = [1, 2, 3]

a + [4]

[fallow agate]

why weired?

initially there are 3 elements inside the list & you are adding an additional one

[haughty mountain]

!e

a = [1, 2, 3]
print(a + [4])
print(a)

[halcyon plank]

:white_check_mark: Your 3.12 eval job has completed with return code 0.

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

[haughty mountain]

with something like + you would expect that the things you are adding stays unchanged after the operation

it's not modifying an object, it's creating a new one

a += something on the other hand could (but doesn't have to) modify a in-place

[fallow agate]

when it will modify & when it will not?

[haughty mountain]

for mutable types += tends to do it in-place

for immutable types you can't do it in-place

(you could still define a mutable type where += returns a copy, but it would be weird)

[fallow agate]

🤷 let's consider x person had 5$, when 1$ is added, it is expected that the total becomes 6$.
not sure why it feels more reasonable to say 5$ stays as it is & then 1 extra $ came 😦

after all, programming is nothng but converting real life scenarios into programming

we do things in english langauge(i mean whatever langauge), where as computer understands different lanaguges like python etc

[haughty mountain]

if you do

pi = 3.14

pi + 2
```would you expect `pi` to change?

[fallow agate]

correct right? thats the math

[haughty mountain]

why would pi change just because you compute pi + 2?

2 + 3 wouldn't change the value of 2

[fallow agate]

no, i did not mean changing 2. two mins pls, will show you something.

a = [1,2]

here a is memory address

when we say a.append(2)
it's changing the value present inside that memory.

[haughty mountain]

[fallow agate]

typing mistake. not removed

[haughty mountain]

!e it's still the same object, yes

a = [1,2]
print(id(a))
a.append(3)
print(id(a))

[halcyon plank]

:white_check_mark: Your 3.12 eval job has completed with return code 0.

001 | 140255085480384
002 | 140255085480384

[haughty mountain]

just its value changed

[fallow agate]

exactly. this is so stratght forward & this is what we expect in real life also right? I mean, the money example, suppose we have 5$ & someone gave us 10$, how much you have in total means will say 15$.

irrespective of immutable, mutable, if every data type was behaving this way, it would have been simple.
i am not saying python developers are wrong. They would have some reason to design multiple behavious, all i am trying is to understand those(not deeply, atleast a prime reason, so that it sticks well into mind).

[haughty mountain]

append very explicitly acts on the object though

there aren't really multiple behaviors

the expectation is that something like

a + b
```acts the same regardless if `a` and `b` are immutable or not

it doesn't modify anything, it just computes a new value, the sum of a and b

if you wish to assign that value to something you need to do that, e.g.

# new name
c = a + b
# update `a`
a = a + b

for types you'll encounter a = a + b will produce a new object and give it to the name a

there is also the operator += which could make use of the fact that you are assigning to the same name, re-using the object

a good mental model is that all the usual operators like +, *, ... produce new values

while things like +=, *= might re-use/modify the same object if it can

for immutable types it never can, but for mutable types it can

methods on objects could also modify objects in-place, like list.append(...) or set.add(...)

but it doesn't have to, e.g. list.copy() returns a new value

just depends on how the method is implemented

[haughty mountain]

5$ & someone gave us 10$, how much you have in total means will say 15$
that would correspond to something like

money = 5

money = money + 10
# or
money += 10

not just money + 10

another example, where the value of money does not change

money = 5

if money + 10 == 15:
  print('if I gave you 10, you would have 15')

[fallow agate]

i am confused! 😦
so, we need to keep in mind so many aspects like mutable, immutable, are we doing +, are we doing += etc when we programming?

[haughty mountain]

it's not that many concepts

mutable vs immutable you will need to keep in mind for a bunch of reasons

but for stuff like + and += it's more just realizing what the operations even mean

a + b is kinda "the result when I add a and b"
a += b is more "assign the result of adding a and b to a"

if things are implemented properly, whether += modifies or not shouldn't really matter for the resulting value that you can observe

[modern gulch]

To say what fff said: it is fundamental to understand when a new object is created vs when an object is modified. Forget about words like immutability and mutability, you can have otherwise mutable objects who have methods that return a new object or methods that modify the method in place. This is part of understanding how an API works, and why checking the method doc is important. ... as an aside, this is one thing that makes libraries like Pandas confusing: the apparent mix of mutability and immutability.

[fallow agate]

here: no confusion. just a new object is getting created, because we are not modifying the existing one

a = 1
b = 2
c = a+b
print(id(a))
print(id(b))
print(id(c))

140720894638520
140720894638552
140720894638584

But, below case: we are just modifying the existing one, yet a new object got created. As we are just changing the existing object, isn't the address should remain same?

a = 1
print(id(a))
b = 2
a = a+b
print(id(a))

140720938613176
140720938613240

Again , same. we are just modifying the existing one, yet a new object got created. As we are just changing the existing object, isn't the address should remain same?

a = 1
print(id(a))
a += 1
print(id(a))

140720938613176
140720938613208

These are all multiple scenarios, right?

[haughty mountain]

in this case mutability matters

python ints are immutable

so a new one will always be created

!e with lists that are mutable the story is different

a = [1]
b = [2]
print(f'{id(a)=}')
print(f'{id(b)=}')

c = a + b
print(f'{id(c)=} is different')
a = a + b
print(f'{id(a)=} is different')

[halcyon plank]

:white_check_mark: Your 3.12 eval job has completed with return code 0.

001 | id(a)=139670563916224
002 | id(b)=139670563918080
003 | id(c)=139670561899264 is different
004 | id(a)=139670561924992 is different

[haughty mountain]

!e but on the other hand

a = [1]
b = [2]
print(f'{id(a)=}')
print(f'{id(b)=}')

a += b
print(f'{id(a)=} is the same')

[halcyon plank]

:white_check_mark: Your 3.12 eval job has completed with return code 0.

001 | id(a)=140097445005760
002 | id(b)=140097445007616
003 | id(a)=140097445005760 is the same

[fallow agate]

and again a.append(b) will give different address for a right?

[haughty mountain]

nope

!e

a = [1]
print(f'{id(a)=}')

a.append(2)
print(f'{id(a)=} is the same')

[halcyon plank]

:white_check_mark: Your 3.12 eval job has completed with return code 0.

001 | id(a)=140692535314880
002 | id(a)=140692535314880 is the same

[haughty mountain]

because append modifies the object

the id of obj when calling a method actually can't change

it can't modify what object the name a refers to

to do that you need some form of assignment

[fallow agate]

This is also modifying the object, right?

yet, the id of a became different

[haughty mountain]

it's not

a + b is a new list

and that's assigned to a

[fallow agate]

we should not think like this?
a initially has 1 inside it,
then we are adding one more element i.e. b to it
so, it's like updating the existing a

where am i going away from the correct thinking path?

[haughty mountain]

a + b will modify neither a nor b

then we are adding one more element i.e. b to it
this is false, it's creating a new list with the contents of a and b concatenated

[fallow agate]

exactly. that was my question. python developers designed it to create new list & we are not sure about the reason.
we just have to remember this is how it is happening.

[haughty mountain]

what would you expect [] + [1] to do?

modify the empty list?

[haughty mountain]

I don't see what the alternative is

[fallow agate]

yes. like this:

[haughty mountain]

if we would follow your logic we would have nonsense like

pi = 3.14
two_pi = pi*2

print(pi)  # 6.28

because according to you something like pi*2 should modify pi

[agile sundial]

or just pi+pi+pi would be amusing

[fallow agate]

because pi is a constant, we should not modify. that's what you are saying?

[haughty mountain]

computing the sum of two values shouldn't modify either of the two values

[haughty mountain]

and yeah, stuff like this would get very odd

[fallow agate]

pls tell me, what's wrong in this:

[agile sundial]

x = 2
print(x + x + x) # 8!!!

[haughty mountain]

not sure what you mean here

[fallow agate]

i think, same logic? adding 2 things should not modify any one of the operands?

so, thats why if we do a = a + b, a new object will be created insread of modifying the exisiitng a?

[haughty mountain]

such operators in general tend to never modify their arguments

I don't think there is any type you'll see in the standard libaries with an operator that would modify their arguments

[fallow agate]

yeah....understood now. Thank you
i was arguing in stupid way...
even when we do math: If the question is what is 5 + 7, we say 12, not like let's take 5 & update it to 12.

[haughty mountain]

in math everything is kinda considered immutable anyway

[fallow agate]

so, bottom line is:
when it comes to operations(+, -, /, *) performed between immutable objects --> A new object is created
when it comes to operations(+, -, /, *) performed between mutable objects --> The first operand on whcih the operation performed will get updated instead of creating new object.

[haughty mountain]

for these operators it doesn't really matter if things are immutable or not

they will always create new values

immutable/mutable matters for the extended assignment operators like +=, -=, /= and *=

for immutable things it should end up equivalent to just doing a = a + b or whatever

for mutable things a tends to be updated in-place, but the value will be the same as if we had done a = a + b

it's just that in the mutable case we can be more efficient since we can make use of the mutability

[fallow agate]

why so?

i mean, pls tell some reason like this:

[haughty mountain]

a += b is a bit like a = a + b but we know that the first element will be immediately reassigned, i.e. the value of a we had before this operations won't really matter after this operation

so maybe we can be more efficient and just modify the a directly

in the case of immutable types you can't do this and you need to just do the usual a = a + b, but for mutable types you can often to better

e.g.

long_list = [1, 2, 3, 4, 5, 6, 7, 8, ...]
short_list = [-1]

# here we need to make a copy of all of the long list,
# because we must produce a new value
long_list = long_list + short_list

# here we could be clever and instead of copying we can
# just add the small list at the end, this will behave
# like list.extend which modifies in-place
long_list += short_list

[fallow agate]

Then if same thing happens in case of immutable also, efficiency increases, right?
I mean a = a + b --> with existing way of working, first a+b need to be added & new object needs to be created, that memory address need to be copied into variable a. to do this process, lot of memory & resources are required.

instead if it would have updated a in place, resource saving?

[haughty mountain]

it can't do it for immutable types

they are immutable

[fallow agate]

yeah i got you. python developers would not have kept immutable it self in the first place. everything is mutable.

they would have their reasons, obviously, i am not a qualified to question them, it's just my doubt, why they crearted so...

[haughty mountain]

python developers would not have kept immutable it self in the first place. everything is mutable
huh?

[fallow agate]

why to keep even string as immutable?

[haughty mountain]

it means that if you have duplicate strings we don't need to have duplicate strings in memory

we can just refer to the same object, and that ends up being safe to do

otherwise someone could modify that thing and we have a mess

we also allow additional operations on some immutable types, e.g. we allow doing things with tuples that we won't allow for lists

like hashing

[fallow agate]

yeah... hashing depends on contents of obj. if someone modifies in the middle, then hash changes, eveything becomes messy

[blissful cypress]

Could you point to some reading or resources about this?

[haughty mountain]

idk about resources, but it's just...how things work

+= and whatever has the option to be more efficient, as highlighted by += on list

for immutable stuff you just can't

[lean walrus]

+ calls __add__
+= calls __iadd__ if it exists, otherwise __add__

[fallow agate]

if it exists --> wdym by it?

[lean walrus]

I think you mixed up mutable/immutable a couple of times

[lean walrus]

__iadd__ method

[fallow agate]

correct. pls see now.

[lean walrus]

now it seems fine

any string literal or bool literal is an example
if you are doing color-related stuff it is not rare to see stuff like RED = (255, 0, 0)

__slots__ = ('x', 'y')

[haughty mountain]

the size of data doesn't necessarily matter for immutability

you could have small mutable values or large immutable values

[haughty mountain]

it's one reason

if you have a large thing you need to mutate a bunch you want something mutable

for large stuff that doesn't need to change much immutable can be fine

[lean walrus]

big immutable stuff isn't necessarily slow

there are data structures that allow fast creation of new immutable lists/strings

[haughty mountain]

yeah, there are some more niche stuff if you deep-dive into the functional programming world

[wintry agate]

Hiya, I'm just learning python and was looking for a really basic answer, I'm coming from unreal C++ and I was looking for something similar to a map or a set with a key and a value?
So stored like so:
KeyArray = [[6, A], [7,B], [2, C]]
And then I'd like the ability to order if by the Key, is there a data type that fits that well?
So KeyArray.SortByKey
KeyArray = [[2, C], [6,A], [7, B]]
Or is it just using a set and then telling it to order it myself, from what I understand using multiple data types is fine in an array?

[narrow mica]

there's no std::set nor std::map equivalent in python
there exists however an std::unordered_set equivalent (set) and an std::unordered_map equivalent (dict)

if you don't need it to be ordered at all times, you can just call list.sort() or sorted(list) when you need it to be sorted

sorted containers would probably be your best bet otherwise

[wintry agate]

Thanks, sort does the job just fine by the looks of things!

[lean walrus]

dict's are guaranteed to maintain order
so they are kinda equivalent to std::map

[narrow mica]

dict maintains insertion order
not key order

[stable pecan]

can also use bisect.insort to keep a list sorted if you want to stay in the std lib

[regal spoke]

The closest thing to std::map built into python is heapq.

[regal spoke]

std::map is something completely different compared to Pythons dict. However std::unordered_map and dict is essentially the same thing.

[haughty mountain]

(and that's way off)

[narrow mica]

heapq is close to std::map kind of maybe, I guess you can argue they're both trees (but then a heap is usually implemented thru arrays)
but heapq is way closer to std::priority_queue (in fact they're pretty equivalent)

[fallow agate]

what could be the mistake in this program 🤔

def change_possible(value, coins):
    if value == 0:
        return True
    if value < 0:
        return False
    for coin in coins:
        new_value = value - coin
        if change_possible(new_value, coins) == True:
            return True
        else:
            return False
 
print(change_possible(5, [4, 1, 5]))

[haughty mountain]

your loop will run exactly one iteration

you'll want

def change_possible(value, coins):
    ...
    for coin in coins:
        new_value = value - coin
        if change_possible(new_value, coins) == True:
            return True
    return False

[lean walrus]

def change_possible(value, coins):
    ...
    for coin in coins:
        new_value = value - coin
        if change_possible(new_value, coins) == True:
            return True
    else:
        return False
``` is also fine

[haughty mountain]

pretty superfluous, but fine

[hard wyvern]

is there any website that has exercises for each algorithm? i dont want to use something like leetcode. just a simple website with exercises and solutions for each algorithm.

[hybrid locust]

Can I use Python to make a template like Canva where I can autofill content and upload my required image?

[modern gulch]

Which algorithms?

[haughty dew]

Can I do DSA with python? Is it advisable to do so? Or should I learn another language and then try DSA in that

[fallow agate]

If you want to copy data from mutable variable, then .copy is the way.

x = [1,2,3]
y = x.copy()

print(id(x))
print(id(y))

How do you copy variable whose datatype is immutable?

[hard wyvern]

For example, binary search, selection sort, recursion. Just want a plain website that just has exercises for each algorithm.

[serene nexus]

I don't know if this is the right place for this question, but do people have good resources for understanding python's internals around object creation, method calling etc? Im trying to make design decisions and I just don't know enough about python's internals to make informed decisions.

[modern gulch]

Searching snd sorting are covered in DSA courses, and any DSA textbook will contain exercises. I don't know a specific website but maybe search for DSA practice problems.

[haughty mountain]

https://cses.fi/problemset is a good problemset covering a bunch of topics

[raw zealot]

@regal spoke https://codeforces.com/contest/2020/problem/E
does this code have any room for optimization , its apparently tleing at O(400n)
https://codeforces.com/contest/2020/submission/284027286

[regal spoke]

Lol, I just got tagged on a different server about this exact problem and python

Do you know eachother

[raw zealot]

lmao yes

i was trying to help him

but the problem is a bit orz for me so i cant understand the code

[regal spoke]

https://codeforces.com/contest/2020/submission/284027116 got his code to pass after some standard optimizations

Indexing is expensive in Python

[raw zealot]

ah

[regal spoke]

Just flattening the DP array should give a big boost

[raw zealot]

even when its a dp[n][2]?

damn

[regal spoke]

I've kind of done that by caching the indexing from the outer loops

[regal spoke]

especially in that case

[raw zealot]

oh

3953 ms is crazy

💀

[regal spoke]

Codeforces has a lot of fluctiations, and on each submission you get 3 tries.

So it is common for AC submissions to have a time like 999 ms

[raw zealot]

i see

btw

does icpc have this much relaxation for python as codeforces does

because i think i will have to switch for this reason

;-;

[regal spoke]

I know people that have gone to icpc finals just using python

[raw zealot]

insane

orz

but like then you need the whole team to use it

[regal spoke]

I'm not sure that all regionals have PyPy

NWERC and the final does

But I don't know about the other regionals

[raw zealot]

alright

cool

[modern gulch]

feel free to add stuff / revise 🙂

[hard wyvern]

Exactly what I want. Thank you

[solemn moss]

lol

1024n passes in less than 3sec

https://codeforces.com/contest/2020/submission/284039124

[raw zealot]

Yeah ikr

[fallow agate]

@modern gulch there are no solutions?

[haughty mountain]

no, it's just a set of problems separated by category for you to solve and submit

the categories should suggest what kind of approach is needed

[fading heath]

Hi guys hope you’re all good m facing a problem rn with my exe in python, the code work fine in the IDE, but when i launch it as an exe it pop ups a cmd screen and it closes quickly

If there is any solution please i need your help and thx !

[regal spoke]

Some optimizations to that one brings it down to 1656 ms
https://codeforces.com/contest/2020/submission/284051996

[fallow agate]

if you can't solve, there are no solutions like in the leetcode?

[narrow mica]

it's a classic problemset so you can easily find how other people did it online
there's just no direct link from cses to a solution page

[regal spoke]

https://codeforces.com/blog/entry/50728 there is an accompanying book to cses that you probably could use if you get stuck.

[ionic silo]

Just want to check if my thinking is right around the time complexity of dijkstra. After initialisation, its simply predicted on the time complexity for each operation of FindMin, DeleteMin and DecreaseKey within the expression O(V (FindMin + DeleteMin) + E (DecreaseKey)) being implemented. Assuming a binary heap, FindMin and DeleteMin are log V however, no language really has DecreaseKey natively implemented so assume log V as an upper bound, thus the time complexity would be O(V(log V + log V) + Elog V) = O(Vlog V + Elog V) but in any simple connected graph, E < V(V - 1) thus E < V^2 is a good upper bound. Therefore we can further simplify by taking E = O(V^2) and therefore O(Elog V) dominates thus we have that O(V^2log V) = O(Elog V)?

[regal spoke]

O(V^2log V) = O(Elog V) is wrong

But O(Elog V) = O(V^2log V) is correct

The big O notation works in a funny way where a = b does not imply b = a

The time complexity of dijkstra is O(E log V) indepedently if you have access to a DecreaseKey datastructure, or just have a heap

The exception is if you use a fibonacci heap, then the time complexity can be brought down to O(E + V log V)

[ionic silo]

Oh gotcha yeah, i did get caught up in the notation here

[ionic silo]

Is this because the E log V dominates either way regardless?

[regal spoke]

What time complexity do you assume DecreaseKey has?

Thats is the question that decides everything

[ionic silo]

I thought it was log V

[regal spoke]

If that is log V, then dijkstra becomes O(E log V).

However, with fibonacci heap, DecreaseKey takes O(1)

[ionic silo]

yeah thats true

ive just been under the impression of thinking in the context of a binary heap for implementation purposes

[regal spoke]

I've never in my life seen anyone attempt to use fibonacci heaps in an implementation of dijkstra. It is more of a theorectical data structure.

[ionic silo]

yeah i agree, its asymptotically optimal but through my research ive realised ive sometimes conflated research papers on the theory side vs more practical implementations of the algorithm

thank you for clearing things up

[fallow agate]

byte by byte system design course review?

[patent junco]

someone knows how to join newlines? i have this:

like i want to keep newlines but only collapse if there is nothing else on line than other newline…

[patent junco]

send help!

:|

help…

[modern gulch]

#❓｜how-to-get-help use a help thread pl

[patent junco]

fixed anyway. current full code here: https://gist.github.com/hacknorris-code/fcf7e30f2787ef1e689448adff08111b

[tulip hazel]

Hi I need some help regarding DSA as i am a college first year student i have completed my basics in Python and want to advance so I have decided to learn DSA in Python but i don't have any resources and not able to understand where to start and learn from
please give some suggestion I am looking if anyone can suggest a yt free couse where things can be learning in proper way and help me slove problem

[serene galleon]

how to do this property in python ?

[fallow agate]

any source to study about patterns in ds & algo?

[kind jolt]

sorry for my ignorance but im not understanding how it know how many bloks go down, how u count it?

[lusty crown]

u can implement the __getitem__ method on a class if u want the same exact implementation otherwise just implement a normal function and call it

class ...:
  def __getitem__(self, num: int) -> int:
    return num * num

square = ...()
square[5] # same as sqaure.__getitem__(5)

[stoic aspen]

algorithms need a math? for high knowledge?

and where can i learn algorithms for free yt videos or docs send i want to start learning algos

[wraith ridge]

It’s not really “being counted” so to speak. You call F1, then within F1 you keep calling F1 over and over as long as your on a blue square. But note that the original F1 function hasn’t finished completing. You will need truly understand recursion to get what is happening. I recommend studying linked lists, doubly linked lists and then binary search trees. If you understand BST traversals than you will understand recursion.

[serene galleon]

not at all. we only see math in recursive algorithms

[serene galleon]

does it makes my class enumerable ?

[lusty crown]

no u would need to implement __iter__

and __next__

[toxic hare]

i made an isometric projection in pygame
the entire thing is coded by hand using numpy
(including the noise function)

[fiery cosmos]

looks cool

[stoic aspen]

wow

algorithms can speed up your script? and make script with auto thinking when doing something?

[toxic hare]

im not sure i understand what you mean?

[haughty mountain]

for anyone interested, facebook hacker cup is starting now

ends in 3 hours

[kind jolt]

thx a lot, there some path you follow to be good in algos. If it is please write me from what start

[quaint bridge]

def to_numbers(word: str):
    asci = ''
    for i in word:
        asci += str(ord(i))
    return asci



def to_luth(number: int):
    number = str(number)
    sum = 0
    paros = False
    for i,v in enumerate(reversed(number)):
        if paros:
            double = int(v) * 2
            if double > 10:
                double = str(double)
                sum += (int(double[0]) + int(double[1]))
            else:
                sum += int(double)
            paros = False
        else:
            sum += int(v)
            paros  = True
    return sum

print(to_luth(to_numbers("password")))

Output: 70
Is this a good algorythim to passwords for example? Have this is an inverse?
(e.g. save the users password to the database this way and compare this way)

[wraith ridge]

I did a bootcamp where I learned about data structures. No longer exists. There are numerous free courses online such as freecodecamp and also this https://youtu.be/aCQbXObVsiM?si=AdQkNu2gLxt3Mnv1

[kind jolt]

thx a lot, i will do it

[acoustic rivet]

no you're probably thinking of making your class iterable there. adding getitem lets your class behave like a dict where you can put things other than integers in [], so my_instance['key']

[cedar turtle]

how to input python code on discord chat?

[quaint bridge]

write the code between 3 `

[narrow mica]

```py
code in here
```

[lilac zinc]

does design patter questions can be asked here?

[agile sundial]

#software-architecture may fit better

[weak oyster]

Is there anyone who intrested or currently doing TRADING and Trading algorithams automation

[stiff quartz]

Is that fair to say we assume integer addition is O(1) even though it kinda should be O(log(integer_value))

I get that an integer will never be in practice more than like stored on 100 bits in the most extreme cases but

we do say log(n) with arrays of size n and let's be honest it's not like we are going to have more than 2^100 elements in our array either, right? (Definitely won’t fit in RAM)

That question is more of a philosophical one but I thought about it randomly earlier today and I can't find the consistency here

[haughty mountain]

it depends, in hardware for fixed sized integers it really is constant time to do such arithmetic operations

as in, kinda more constant time than just saying that we have a fixed number of bits

the operation is basically performed in parallel

[stiff quartz]

Ah I see, fair enough

[regal spoke]

I think of it like pretty much all algorithms out there have a hidden log factor

[lilac cradle]

accidentally discovered a way better way to make a sierpinski triangle using only bitwise operations, it’s mostly the same as the method i found before but it takes the previous value into account

def sierpinski_bin_new(n,prev):
    new = (n<<1) ^ prev
    prev = n
    return new,prev

[haughty mountain]

why do you even need prev?

!e

def sierp():
  n = 1
  while True:
    yield n
    n ^= n << 1

for _, n in zip(range(8), sierp()):
  print(f'{n:b}')

[halcyon plank]

:white_check_mark: Your 3.12 eval job has completed with return code 0.

001 | 1
002 | 11
003 | 101
004 | 1111
005 | 10001
006 | 110011
007 | 1010101
008 | 11111111

[lilac cradle]

yeah, it does that without it

which works but it's a bit less cool

i.e it's like this

[fallow agate]

any source for OOP design for FAANG interviews?

[stiff quartz]

Yeah so like whenever someone describes a log(log(n)) term in an algorithm I'm like, you add this term but you don't account for the log in addition (which I guess is actually parallelisable so that's a bad example but I'm not sure you can parallelise anything when doing a modulus division for example)

It feels a tiny bit inconsistent

Although I see the mathematical value of deriving log(log(n)) etc, I'm just frustrated by the inconsistency I guess (well, I'll survive)

[regal spoke]

There are two kinds of people that care about this hidden log factor

People working with really big numbers

or theoretical computer scientists

But theoretical computer scientists usually dont cara about log factors in the first place

[stiff quartz]

Ah yes especially since you don't have to implement big int in Python, it can become hidden to the naked eye if you truly work with big numbers?

[regal spoke]

Python doesnt use optimal algorithms for it big int operations. But I was just trying to say that people dealing with big integers will realize that integer operations arent O(1).

Btw one good example of this hidden log is
https://en.wikipedia.org/wiki/Multiplication_algorithm

Lastly, in 2019, Harvey and van der Hoeven came up with an galactic algorithm with complexity O(n log n).

That log is the "hidden" log explicitly written out

Using the same terminology, something like merge sort would be O(n log^2 n)

It is probably pretty easy to find tons of people talking about O(n log n) multiplication algorithms based on fft.

But they would be O(n log^2 n) if you include the hidden log factor

[stiff quartz]

On a side note, I've never even thought about how multiplication would be implemented and if someone had asked me I would've said probably the "grade school multiplication" they mention

[regal spoke]

The trick is that multiplying polynomials can be done fast using fft.

Somehow you express your integer multiplication as a polynomial multiplication, and then use fft

If you think about it, the naive way of multiplying integers is pretty much already polynomial multilication

where the "x" variable is the base

[stiff quartz]

Ah yes fair enough

Although multiplying polynomials without fft is n*m I guess (and I’m not a fft person yet haha)

Where n is log(first number) and m is log(second number)

[regal spoke]

The idea behind fft is actually very simple

Suppose you want to know the product R(x) of P(x) times Q(x)

Note that while it is not easy to figure out the coefficients of R(x) =P(x)*Q(x)

It is easy to evaluate R(x)

[stiff quartz]

Ah so you just need to evaluate it at enough points for the unknown coefficients to be fully determined? 👀

[regal spoke]

Yes

FFT_n(P) means evaluating P in all complex nth roots of unity

Inverse FFT_n is the opposite, by giving it a polynomial evaluated at all complex nth roots of unity, you get back the polynomial

[regal spoke]

This is exactly it

[stiff quartz]

Except there is a difference between: you could theoretically do it and inverse fft_n does it for you

The second sounds black magic to me for now

[regal spoke]

Here is the thing. If you could give me some algorithm that quickly is able to evaluate a polynomial at n different points

Then I could probably make a polynomial multiplication algorithm out of it

FFT just happens to be simplest way to make such an algorithm

[regal spoke]

It turns out that inverse_FFT_n(P) = FFT([P[-i]/n for i in range(n)])

So once you've implemented FFT, you get inverse FFT for free

Btw this code [P[-i]/n for i in range(n)] is something that chatgpt seems to have a really hard time with. It is not the same thing as reversing P. But chatgpt seems to think that it is

[P[~i]/n for i in range(n)] would have meant reversing P

Here is everything combined

"""
Calculates FFT(P) in O(n log n) time.

This implementation is based on the 
polynomial modulo multiplication algorithm.

Input:
  P: A list of length n representing a polynomial P(x).
     n needs to be a power of 2.
Output:
  A list of length n representing the FFT of the polynomial P,
     i.e. the list [P(exp(2j pi / n * i) for i in range(n)]
"""
rt = [1] # List used to store roots of unity
def FFT(P):
    n = len(P)
    # Assert n is a power of 2
    assert n and (n - 1) & n == 0
    # Make a copy of P to not modify original P
    P = P[:] 
    
    # Precalculate the roots
    while 2 * len(rt) < n:
        # 4*len(rt)-th root of unity
        import cmath
        root = cmath.exp(2j * cmath.pi / (4 * len(rt)))
        rt.extend([r * root for r in rt])

    # Transform P
    k = n
    while k > 1:
        for i in range(n//k):
            r = rt[i]
            for j1 in range(i*k, i*k + k//2):
                j2 = j1 + k//2
                z = r * P[j2]
                P[j2] = P[j1] - z
                P[j1] += z
        k //= 2
    
    # Bit reverse P before returning
    rev = [0] * n
    for i in range(1, n):
        rev[i] = rev[i // 2] // 2 + (i & 1) * n // 2

    return [P[r] for r in rev]

# Inverse of FFT(P) using a standard trick
def inverse_FFT(fft_P):
    n = len(fft_P)
    return FFT([fft_P[-i]/n for i in range(n)])

"""
Calculates P(x) * Q(x)

Input:
  P: A list representing a polynomial P(x)
  Q: A list representing a polynomial Q(x)
Output:
  A list representing the polynomial P(x) * Q(x)
"""
def fast_polymult_using_FFT(P, Q):
    # Calculate length of the list representing P*Q
    n1 = len(P)
    n2 = len(Q)
    res_len = n1 + n2 - 1
    
    # Pick n sufficiently big
    n = 1
    while n < res_len:
        n *= 2

    # Pad with extra 0s to reach length n
    P = P + [0] * (n - n1)
    Q = Q + [0] * (n - n2)
    
    # Transform P and Q
    fft_P = FFT(P)
    fft_Q = FFT(Q)

    # Calculate FFT of P*Q
    fft_PQ = [p*q for p,q in zip(fft_P,fft_Q)]

    # Inverse FFT
    PQ = inverse_FFT(fft_PQ)
    
    # Remove padding and return
    return PQ[:res_len]

The FFT function is kind of advanced, but the fast_polymult_using_FFT should be simple to understand

[astral knot]

guys python program to find the sum of digits in a number ALGORITHM FOR THIS HELP ME

lke with the basic knowledge

[regal spoke]

There are two common ways to do it.

def digit_sum(x):
  y = 0
  while x:
    y += x%10
    x //= 10
  return y

or

def digit_sum2(x):
  return sum(int(digit) for digit in str(x))

[rancid idol]

Maybe a very very stupid question here guys but it is by asking you learn so here is it.

If we have a problem size of n.

We have a for loop like

    for j from 1 to n
        for k from 1 to n
        do only one line operation```

and we have 
```for i from 1 to n
    for j from 1 to n
        do 1st operation
        do 2nd operation
        do 3rd operation
        ...............
        ...............
        do k_th operation

We would say that the first one is of O(n^3) and the second is O(n^2), but if we have multiple lines of code of constant sizes. How can we say that second one is faster? I'm confused If I have an algorithm containing these two for-loops what would the time complexity of my algorithm be? O(n^3)???

[astral knot]

bro when i type this in the compiler it dont give nothing

shit got it thanks

[regal spoke]

In most programming languages, you cant add more lines of code to your program depening on the input. So the 2nd case cannot happen.

[rancid idol]

Not following? Are you saying there is a minmu limit to how many lines you can have in a for loop?

[regal spoke]

Here is a function that runs in O(n^2) time

def f(n):
  x = 0
  for i in range(n):
    for j in range(n):
      x += i * j
  return x

But it is not possible to make an unrolled version of it

This is not valid python code

def f(n):
  x = 0
  for i in range(n):
    x += i * 0
    x += i * 1
    ...
    x += i * (n - 1)
  return x

[rancid idol]

no I am just saying assume there is like 50 lines of code inside the inner for-loop

not randomly fill each line with dot dot dot

[regal spoke]

In the big O world, 50 is merely a constant

[rancid idol]

1000

[regal spoke]

Still just a constant

[rancid idol]

That is kinea what I am asking tbh

[regal spoke]

The thing big O measures is how the number of calculations grows when you increase the input (the n parameter)

Something that doesn't depend on n will be ignored

[rancid idol]

Realistically tho a for-loop with 3 nested loops finishes faster than 2 nested loop with 10k lines of constant lines?

No?

[regal spoke]

You have to think about absurdly large n. That is the only time when the big O notation makes sense

Think that n is much larger than any constant in your program

[narrow mica]

in the second, k is probably assumed to not change when n changes
so say k is 1000, it'd still be 1000 whether n was 10 or 10 billion; thus, time complexity is O(k * n * n) = O(1000 * n * n) = O(n^2)
if k scaled with n then it'd be a different story, like in the first piece of code

[rancid idol]

Yeah make sense TBH when you say it like that.

[regal spoke]

One of the flaws with big O notation is that it sometimes very poorly describes the real world

You see people talk about "good" and "bad" constants. Thats exactly the 1000 factors that the big O misses.

[rancid idol]

Can I ask another question, I am working with graphs and I am supposed only give the time complexity in number of vertices in the worst case.

Can I use this as the worst case |E| <= |V|^2

[regal spoke]

Yes

[rancid idol]

but this is not true for sparse graphs, but sparse graph is not the worst case tho right

[regal spoke]

Note that big O is only used to describe upper bounds

The big O notation is a little bit wonky. For example

O(n^2) = O(n^3)

but

O(n^3) != O(n^2)

[rancid idol]

Yeah I learned that. Everything under n^3 is for example polynomial time

[regal spoke]

def f(n):
  x = 0
  for i in range(n):
    for j in range(n):
      x += i * j
  return x

This function is O(n^2), but it is also O(n^3), as well as O(n^100)

[rancid idol]

but what about the graph being a sparse graph tho?

do I need to give 2 cases?

[regal spoke]

no

[rancid idol]

Or can just summerize the worst case?

[regal spoke]

Well you could give two cases.

But unless that is explicitly asked for

I think they just want you to use |E| <= |V|^2, or in big O terms, O(|E|) = O(|V|^2)

[rancid idol]

Btw how can someone prove the correctness of a adjacency matrix initialization?

Like it is so straight forward and can explain it with words but is there like a formal way to prove it, I am like using two nested for loops.

[naive oak]

what exactly do you want to prove?

[rancid idol]

Honestly I have no clue, I used dikijstras algorithm to solve a problem where I get edges as a tuple (v1, v2) and vertices as inputs. I have proved everything in my algorithm except the part where I create an adjcency matrix like: ```

for vertex in vertices

#     for edge in edge 
#         if edge[0] == v then
            add edge[0]in matrix as a neigbor to v

It is a little longer and I have get minimum values of certain thing using functions but that is just if/else statements.

Can you prove this using a loop-invariant or another formal proof to prove that vertices are put correctly in adjcancy matrix.

Because informally I can definitely explain how this is the case.

[naive oak]

well when it comes to a proof of that the details do matter

I would probably formalize the statement you want to prove as roughly "an edge (v1, v2) with weight w is in edges if and only if matrix[v1][v2] = w"

but I'm not sure how your adjacency matrix is set up

[rancid idol]

"do this" to abstract away things (function calls) I have already proven.

[naive oak]

I still have no idea what you're doing there

[modern bronze]

def minimax(node, depth, maximizingPlayer):
    if is_terminal_node(node) or depth == 0:
        return evaluate(node)

    if maximizingPlayer:
        maxEval = INT_MIN
        for child in get_children(node, maximizingPlayer):
            eval = minimax(child, depth - 1, False)
            maxEval = max(eval, maxEval)
        return maxEval
    else:
        minEval = INT_MAX
        for child in get_children(node ,maximizingPlayer):
            eval = minimax(child, depth - 1, True) 
            minEval =min(minEval, eval)
        return minEval
    
print(minimax([[1,0,-1],[-1, 1, 1],[0,0,-1]], 20000, True))

I dont understand whats wrong with my minmax

this returns an output of 0
[[1, 1, -1], [-1, 1, 1], [-1, 1, -1]]
1
[[1, 1, -1], [-1, 1, 1], [-1, 0, -1]]
0
[[1, 1, -1], [-1, 1, 1], [1, -1, -1]]
0
[[1, 1, -1], [-1, 1, 1], [0, -1, -1]]
0
[[1, 1, -1], [-1, 1, 1], [0, 0, -1]]
0
[[1, -1, -1], [-1, 1, 1], [1, 1, -1]]
0
[[1, -1, -1], [-1, 1, 1], [1, 0, -1]]
0
[[1, 1, -1], [-1, 1, 1], [1, -1, -1]]
0
[[1, 0, -1], [-1, 1, 1], [1, -1, -1]]
0
[[1, 0, -1], [-1, 1, 1], [1, 0, -1]]
0
[[1, -1, -1], [-1, 1, 1], [1, 1, -1]]
0
[[1, -1, -1], [-1, 1, 1], [0, 1, -1]]
0
[[1, 1, -1], [-1, 1, 1], [-1, 1, -1]]
1
[[1, 0, -1], [-1, 1, 1], [-1, 1, -1]]
0
[[1, 0, -1], [-1, 1, 1], [0, 1, -1]]
0

shouldnt it return 1?

[urban wagon]

i would try using AI to solve these types of questions

[modern bronze]

what do you mean?

[urban wagon]

AI like chatgpt

[modern bronze]

to tell me whats wrong?

[urban wagon]

yeah.

[modern bronze]

gpt said my that my code is fine

and that my evaluate node is probably the issue -- its definitely not

[urban wagon]

ur probably prompting wrong you have to describe your problem

very specifically

[agile sundial]

[urban wagon]

?

much better to move on and be productive than wait for someone to explain it to you 😁

[modern bronze]

smash head into keyboard until i figure it out

[tribal vine]

Pretty sure suggesting chatgpt is against the rules here

It’s also the laziest and least helpful way to try to help anyone

Making a help post is a better idea

[modern bronze]

i did but to no avail

[hushed nova]

man I am having hard time Implementing linked list (singly/doubly) like i understand the concept but when it comes to implementation, i might think it's cause of oop? Any suggestions?

[narrow mica]

maybe show the problematic code you're stuck on?

[hushed nova]

Alright wait, hope i can pull it on phone

    if self.head is None:
        return

    current_node = self.head
    position = 0
    
    if index == 0:
        self.remove_first_node()
    else:
        while current_node is not None and position < index - 1:
            position += 1
            current_node = current_node.next
        
        if current_node is None or current_node.next is None:
            print("Index not present")
        else:
            current_node.next = current_node.next.next```
So after the traversal, we're at the index which we needs to remove, but i dont really understand the method
``current_node.next = current_node.next.next``

[narrow mica]

v `current_node`
A -----> B -----> C
         ^ the node we want to delete

         v `current_node.next`
A -----> B -----> C
                  ^ `current_node.next.next`

         v `B` gets garbage collected
A --/--> B -----> C
|                 ^
|-----------------|  `current_node.next = current_node.next.next`

in something like C you'd have to manually free the memory B is occupying
but it's python so that's done automatically by the garbage collector

[hushed nova]

Thanks i can somewhat visualize the process now

[rancid idol]

I've been stuck on a problem for a long time now.

How do I check if two non binary trees of maximum children of 10 are isomorphic. It is pretty easy to do it for binary but 10, it would require 10! cases if I use the same method. I have no clue how to do that.

[lilac cradle]

oh btw if you set prev to a value other than 1, it gets freaky, here's a gif i rendered of it

it almost reminds me of cellular automata, ngl
also how im rendering this is by the iteration count being the X coordinate, and the Y values are each bit with the bottom being 1, and the top being 2^256 (this algorithm takes an inordinate amount of bits, good thing this is in python)

[acoustic rivet]

what's the definition of isomorphic for your problem? that the trees are basically 100% identical? does a given node with 10 children have a certain order for those 10 children or unordered?

[rancid idol]

What would say is the time complexity of this algorithm given a list lst = [[1, 2, 3], [1, 2, 3], [1, 2, 6], [1, 2, 3]] where the maximum size of the sublist is k and the outer list size is n. By printing statements I came to the conclusion that is is O((n-1)*k).

How do you prove this more formally? I guess Master Theorem won't work because our algorithm depends on two variables.

[rancid idol]

isomorphic for me means that the parents of children nodes should still be similar but the order of the children for example in binary tree whether the children are left or right doesn't matter as long as they belong to the same parent in both trees. This is pretty easy on binary tree since you only have maximum children of 2 ofr each node.

[regal spoke]

Easiest way to figure out isomorphism is using hashes

Let the hash of a node be the hash of the sum of hashes of its children

There are tons of ways to do it

[halcyon jacinth]

Hey
Does anyone here have idea about implementation of opencv or YOLO

[narrow mica]

TIL there's cool algorithm for generating all permutations in a gray-code-like way, where the next permutation only differs from the current one by 1 swap of 2 adjacent elements

and also mapping integers 0~(n!-1) to a permutation (and vice versa) is called ranking / unranking a permutation

[narrow mica]

this looks like your exact problem?

[snow quartz]

Hello gang, what is algorithm?

[stable jacinth]

!rule 9 6

[halcyon plank]

Rules

6. Do not post unapproved advertising.

9. Do not offer or ask for paid work of any kind.

[stable jacinth]

Your message has been removed for violating both of these rules

[regal spoke]

I have absolutely no clue what this code is trying to achieve

Do you want to check if all "sublists" are equal?

for i in range(len(list_1)):
    if list_1[i] != list_2[i]:

This looks like a broken way to check if two lists are equal

What if list2 is shorter than list1?

[rancid idol]

Technically I am supposed to compare trees of maximum 10 children so I decided to put it a list cuz I thought it was easier and space complexity was not a requirement. Now given a list of trees I am to return false if they are not equal.

[regal spoke]

I still cant make sense of this

[rancid idol]

so I call check_sublist with a list that contains trees represented as lists.

[regal spoke]

To me, that does not look like what it is doing

[rancid idol]

I have tried it and it works but I am beginning to think if I should maybe use tree as a datastructure.

[rancid idol]

what do you think it does?

[regal spoke]

Your goal is to check if two rooted trees are isomorphic?

[rancid idol]

not isomorphic, rather identical

[regal spoke]

Just do == in that case

[rancid idol]

huh?

[fiery cosmos]

how do i fix it, anyone???

path = "C:\\Users\\maruf\\Projects\\sdf\pp\\o level\\" + pdflink["name"] + "(" + pdflink["code"] + ")" + "\\" + pdflink["year"] + "\\" + pdflink["session"] + "\\"

[regal spoke]

This is not the place to ask about that

[fiery cosmos]

where do i ask?

i just need help quick

[regal spoke]

Well not in #algos-and-data-structs

[fiery cosmos]

i am here...

[regal spoke]

So what

[fiery cosmos]

huh?

this channel is #algos-and-data-structs

[regal spoke]

I said, do not ask in #algos-and-data-structs

[rancid idol]

what @regal spoke is trying to say is that this is room for only Algorithm and data structure so your chances of getting the question answered is low

[fiery cosmos]

ohh

which channel do i ask then?

[regal spoke]

Idk

[stiff quartz]

Probably python-help

[regal spoke]

Anyways going back to this. The standard way to represent a rooted tree is as a nested list, graph = [[]], where the inner list graph[i] contains the children of node i represented as integers

[rancid idol]

so like adjacency list for graphs?

[regal spoke]

Yes, but in this case the tree is rooted. So you only need to store the children

[rancid idol]

We went thru in class how to represent trees whose maximum children size is know and how to save it in a file as an array so that is there I got it from so for every given index the you can find the child of the the node by doing 10*i+k where is the k:th child in this case 1-10 and i is the index of the parent. It has horrible space complexity but I thought it was easier to solve this with.

[rancid idol]

So wouldn't my list of trees contain 2 nested lists .

[regal spoke]

graph[i] is a list of integers

graph is a list of list of integers

graph[i][j] is an integer

[rancid idol]

I meant I will have [Graph1, Graph2, Graph3, ....., Graphn]

but do you think it is a bad idea to do what I did? Should I change it so I use actual trees?

[regal spoke]

This tree (root = 0)

has representation

graph = [[1,4], [2,3], [], [], []]

[rancid idol]

But wouldn't comparing it be a little more complex

[regal spoke]

I guess graph = [[1,4], [2,3], [], [], []] and graph = [[4,1], [2,3], [], [], []] would represent the same graph. So you would have to sort the sublists if you want to check if two trees are equal

Still just a one liner

[rancid idol]

I mean in my case your graph would have a list where the tree is flattened like [0, 1, 4, 1, 2, 3,-1,-1] and you would compare to see if they are equal just compare the lists but in terms of adjacency list

[rancid idol]

exactly this would happen.

sort how?

[regal spoke]

def rooted_trees_equal(graph1, graph2):
  return [sorted(g) for g in graph1] == [sorted[g] for g in graph2]

There

[rancid idol]

but what is it sorting? Sorry technically I am supposed to implement everything on my own. My algorithm should be language independent pseudo but I just prefer to work on it on python then make it pseudo.

[regal spoke]

graph1 and graph2 contains lists of integers

It is sorting those lists

[rancid idol]

but that is given that my data is integer?

[regal spoke]

That depends on you / problem statement

I just said that the standard way is to represent a tree like this

[rancid idol]

but anyways looking at my code, would you consider it is a divide and conquer algorithm as a whole?

[regal spoke]

Well firstly I dont know what it is doing

Secodnly, the "divide" part seems completely pointless

[rancid idol]

check_lists compares lists using for loop.

check_sublists compares uses check_lists to compare a list of lists recursively. If I used for loop then I would need to compare a given list [a,b,c,d] where a-d are sublists. I would need to compare a with b, c, and d. Then b with c and d. But now given [a,b,c,d]. I divide [a,b] and [c,d] compare a and b and return a if they are equal, compare c and a and return c if equal. Then compare a and c and make the conclusion. In my algorithm we only compare 3 times in total than a for loop where we would compare 6 times.

[regal spoke]

[a,b,c,d], why not just compare a with b,c,d?

If it ever fails you are done

[rancid idol]

But that is not the worst case tho, what if we have like 8 lists, we would compare 7 times with for loop while we only compare 6 times with this algorithm and the more the problem size grows the bigger the difference.

[regal spoke]

no

[rancid idol]

Then I am really mistaken and I'd love the clarification.

[regal spoke]

both would use 7 comparisions

6 would fundamentally not be possible

[rancid idol]

I am thinking like

[regal spoke]

I see 7

[rancid idol]

I see that now too

Damn me

[rancid idol]

so it will never actually be better?

[regal spoke]

exactly

Infact, all it does is complicate things terribly for no reason

[rancid idol]

How am I supposed to solve this using divide and conquer algorithm then where it perfoms better.

[regal spoke]

My guess is that you are missunderstanding the task itself

[rancid idol]

The task can be summerized as that I will get a list of n trees to compare with maximum nodes of k. How I represent the data structure of the tree is up to me. I shall use divide and conquer to solve it where the time complexity is still not bad.

[regal spoke]

Well in my representation of trees I would use sorting to compare them

And merge sort is a divide and conquer algorithm

So technically I would use divide and conquer

But that's a bit far fetched

[muted viper]

Question: is there a python algorithm that visualizes if statements (like if the user clicks a certain part of the screen, another screen pops up. etc)?

or library

[eternal vessel]

what does an if statment have to do with clicking a screen?

[muted viper]

nvm

[distant quiver]

Quick question

For Dynamic Programming why isn't dict reccomended for memos

[haughty mountain]

is it not?

for sure if you can express stuff as just integers a list will save a bunch of memory and some performance

but dicts for memoization is common

[stable pecan]

it might not be recommended due to unbounded growth --- if that's a possible issue, using a cache with a max size would fix it

[distant quiver]

i feel like using dict makes the code more readable for me, i have to really look closely. and also its more intuitive

but i guess because og the unbounded growth.

[haughty mountain]

if your stuff is sparse dicts are natural

if you have something nicely bounded, a list will end up more efficient

[regal spoke]

I would definitely recommend using dicts for dynamic programming memoization unless you really care about performance.

For readability it is wonderful

[regal spoke]

Who told you to not use it?

[acoustic rivet]

dict / equivalent datatypes in other languages vary in how they're hashing their keys, etc., so it varies by language, but people often use dict memoization in python. did you know there's a provided way? "from functools import cache" then put "@cache" above a function

you can find people discussing the pros and cons if you google for "functools.cache" and performance etc.

[distant quiver]

an insutrcute on coursera

[regal spoke]

There are a couple of typical styles for coding DP

1. There is the recursive approach, usually combined with a memoization dictionary

2. There is also the bottom up approach using only for loops, usually using some kind of list for storing the DP-values

I would say that the main drawback of 1. is the use of recursion (and not the dictionary part)

Going deeper than 1000 function calls in Python can be really problematic

[distant quiver]

iirc the naive approach is pure recursion

which can be redundant if it has seen a subproblem it already has computed, thus we go for memoization

bottom up approach is pure beauty no need for recursion, and generally easier imo to comprehend

[regal spoke]

Just pure recursion is not even called DP

Some kind of memoization is an essential concept of DP

[distant quiver]

I thought what is deemed as DP is the nature of the problem, pure recursion is just a way of solving it tho ineefficianet

Like the "If a problem has an Optimial Substructure, where you have to mak an optimal choice overall to get the solution" classic textbook definition

and you have to make a sequence of decisions, compare them to find the optmial choice

[regal spoke]

There is no formal definition of DP. It a "you know it when you see it" kind of thing.

But something that I would agrue is pretty much always the case is the memoization part

For example, something like merge sort is NOT dp

Merge sort is using some kind of substructure, but there is no memoization involved

So it is not DP

[regal spoke]

In the theoretical world, the view is the complete oposite of this.

[acoustic rivet]

this is very interesting I didn't realize this was contentious

[distant quiver]

you hit the bullseye for me

when i was learning this i was asking myself, isnt it the same as divide and conquer (sorta)

i just brushed it off that DP uses divide and conquer as one of its tools. But if you ask me i feel like its pretty much the same if you go with the traditional definition

[distant quiver]

wait really?

[regal spoke]

Yes. They love this kind of thing where you describe everything recursively

For time complexity, they analyse the "computational tree" you get from the recursive calls

[distant quiver]

welp thanks alot, now i know that dp = memo. more or less

[distant quiver]

gotcha

im beginning to hate doing dsa in python

[hushed nova]

[narrow mica]

eh, sometimes you just can't be bothered to figure out the correct order in which to loop

[haughty mountain]

<@&831776746206265384>

[modern gulch]

!warn 1102938723777253457 Cracked software and advertisements are not permitted on this server. Your post has been removed.

[halcyon plank]

:incoming_envelope: :ok_hand: applied warning to @sullen flicker.

[fiery cosmos]

W

[rancid idol]

Can someone explain to me how come

1+2+4+...+2^log₂ (d) =2d-1=O(d)?

[modern gulch]

What's the complexity of y=x, or y=2n+5?

[rancid idol]

I think for y=x it is just O(1) because it only assigns x to y, and for y=2n+5 it is O(1+1)=O(1) because we use one operation and then assign.

[regal spoke]

Note that if you add one to 1+2+4+8+16+32+...+2^n

you get 2^(n + 1)

so 1+2+4+8+16+32+...+2^n = 2^(n + 1) - 1

[rancid idol]

not following really

[regal spoke]

Lets do a simple example

1 + 2 + 4 + 8 + 16

Now add one to this

[rancid idol]

32

[regal spoke]

1 + 1 + 2 + 4 + 8 + 16

which is 2 + 2 + 4+ 8 + 16

which is 4 + 4 + 8 + 16

8 + 8 + 16

16 + 16

32

[rancid idol]

then?

[regal spoke]

Thats it. The sum 1+2+4+8+16+32+...+2^n plus one is equal to twice the largest number

I.e. 2^(n + 1)

[rancid idol]

How is it related to 1+2+4+...+2^log₂ (d) =2d-1=O(d)?

[regal spoke]

Just plug in n = log_2(d)

and you are done

2^(log_2(d) + 1) = 2 * d

[rancid idol]

where did n go here?

[regal spoke]

Dude

n = log_2(d)

Lets go back to using n

Do you agree that
1+2+4+8+16+32+...+2^n = 2^(n + 1) - 1?

[rancid idol]

shouldn't it be 1+2+4+8+16+32+...+2^n = 2^(n + 1)

why -1?

[regal spoke]

Okey lets go back to the simple example

1 + 2 + 4 + 8 + 16 = 32 - 1

[rancid idol]

I get it lol

continue

[rancid idol]

I agree

[regal spoke]

Okey so we have this formula

1+2+4+8+16+32+...+2^n = 2^(n + 1) - 1?

This holds for all integer values of n >= 0

Now plug in n = log_2(d)

We get

1+2+4+8+16+32+...+2^log_2(d) = 2^(log_2(d) + 1) - 1?

The thing on the left is your original question

[rancid idol]

Okay how then 2^(log_2(d) + 1) - 1 = 2*d-1?

[regal spoke]

This is just how logarithms work

By definition 2^(log_2(d)) = d

[rancid idol]

What logarithmic rule is being used here. I feel so dumb

[regal spoke]

and

2^(n + 1) = 2 * 2^n

Let me do everything from the start

1+2+4+8+16+32+...+2^n

= 2^(n + 1) - 1

[rancid idol]

No worries

[regal spoke]

= 2 * 2^n - 1

[rancid idol]

it makes sense 10^log(100) = 100

Can't belive I'm missed this haha

[regal spoke]

Now plug in n = log_2(d), and use the definition of log_2

= 2 * 2^log_2(d) - 1

= 2 * d - 1

[rancid idol]

Thank you so much for the help!!

[golden ravine]

i can do question a

i got 10010011

but i don't get how that relates to the other questions

does linux use binary to decide permissions?

[haughty mountain]

it uses a binary encoding yes

[golden ravine]

is there a place i can find out what read write and execute binaries are

[haughty mountain]

the things you encounter typically is a 9 bit value, 3 groups of three bits

• 3 bits for what the owner of the file can do
• 3 bits for what the group associated with the file can do
• 3 bits for what others can do