#algos-and-data-structs

1 messages · Page 10 of 1

lean junco
#

in my segment tree, my query and make function does good job but update updated on one less index

fiery cosmos
#

Hey, is there any way anyone can help me? I'm having a hard time trying to prove this statement using the definition of the big-O.

Screen_Shot_2022-09-09_at_11.16.51_PM.png
#

I more or less have an understanding of how it works, but it's a bit difficult to write down

vocal gorge
#

well, you need to prove that for all sufficienly big n, n^3 + n^2 log(n) + n sqrt(n) is less than, say, 2 n^3.
That's equivalent to saying log(n)/n + n^(-3/2) < 1, so all you need to prove is that this is true for all n past a certain point.

#

that can be actually made simpler by choosing a bigger constant. For example, let's prove the whole thing is less than 3n^3. Then you need to prove log(n)/n + n^(-3/2) < 2 for large enough n - and that's easy because:

  • log(n) < n for n more than 1.
  • n^(-3/2) < 1 for n more than 1.
    So for n>1, this is true.
fiery cosmos
#

oh i see! but may i just ask how log(n)/n + n^(-3/2) came to be?

vocal gorge
#

n^3 + n^2 log(n) + n sqrt(n) < 3n^3, divide both sides by n^3

fiery cosmos
vocal gorge
#

Yup, I originally chose 2 as you can see but realised 3 or more makes the proof trivial.

fiery cosmos
#

this specific part i mean:

  • log(n) < n for n more than 1.
  • n^(-3/2) < 1 for n more than 1.
vocal gorge
#

The latter is equivalent to saying n^(3/2) > 1 for n>1, which I hope can be assumed obvious, but one way to prove it would be sqrt(n*n*n) > sqrt(1*1*1) = 1

#

the former, log(n) < n for n>1, is a very common inequality too, I believe the way it's commonly proven is by examining the derivative. For n=1 we have 0 = log(n) < n = 1, so the inequality is true for n=1.
Examining the derivatives of the parts, we have log(n)' = 1/n whereas n' = 1. Since 1/n < 1 for n>1, the left part grows slower than the right one, so the inequality will never become false as n rises. (there's a theorem about that, don't remember the name)

fiery cosmos
#

ohhh

#

alright, thank you so much for all your help! really appreciate it!

vocal gorge
#

there's a theorem about that, don't remember the name
right, I googled enough to recall why - it's a consequence of the mean value theorem

#

.latex Suppose $f(x_0) \geq g(x_0)$ and $f'(x) > g(x)$ for all $x>x0$. We want to prove $f(x_1) > g(x_1)$ for any $x_1>x_0$.
Then we apply MVT to $h=f-g$, and MVT tells us that there exists a point $c \in (x_0, x_1)$ such that $h'(c) = \frac{h(x_1)-h(x_0)}{x_1-x_0}$. But that means
$$
f'(c) - g'(c) = \frac{f(x_1)-g(x_1)-f(x_0)+g(x_0)}{x_1-x_0}
$$
and since $f'(c) - g'(c) > 0$ and also $-f(x_0)+g(x_0)<0$, we have
$$
0 < f'(c) - g'(c) = \frac{f(x_1)-g(x_1)-f(x_0)+g(x_0)}{x_1-x_0} < \frac{f(x_1)-g(x_1)}{x_1-x_0}
$$
and hence $f(x_1) - g(x_1)$.

grand havenBOT
vocal gorge
#

and hence f(x_1) - g(x_1) > 0, of course. hate that the bot doesn't rerender edits 😔

jolly mortar
#

be the pull request you want to see in this bot

vocal gorge
#

hmm

haughty mountain
#

a general result is that any logarithm grows slower than any polynomial

#

i.e. n^ε (for any ε>0) grows faster than log(n)

#

(I think faster than any power of log(n), even)

#

because you add two nodes here

                    bfs_list.insertLast(v)
                    bfs_list.insertLast(x)
#

so you add
A and B
A and C
C and F
...

fiery cosmos
#

yes it's wrong

white heron
#

Any ideas on how to fix it

haughty mountain
#

that's for sure not the graph

#

considering you get letters that are not even in the graph

white heron
haughty mountain
#

doesn't look right yeah

unknown.png
#

I can't exactly run your code so hard to verify your code

#

I don't see anything obviously bad

#

maybe confirm the graph you built actually looks correct?

eager root
#

it says correct option is A , but i gave D

#

can anyone confirm it ?

idle pier
#

Hello folks this may seem a little silly but when I comment out neigh inside the 2nd for loop but leave neigh as a global variable per se (as you can see in the 3rd line), my code doesn't seem to run properly. Why is this happening?

def gameOfLife(self, board: List[List[int]]) -> None:
        m,n = len(board),len(board[0])
        # neigh = 0
        dirs = [(1,0),(0,1),(-1,0),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)]
        
        
        for i in range(m):
            for j in range(n):
                neigh = 0
                for r,c in dirs:
                    nr = i+r
                    nc = j+c
                    
                    if 0<=nr<m and 0<=nc<n and abs(board[nr][nc]) == 1:
                        neigh += 1
                        
                if board[i][j] == 1:
                    if neigh < 2 or neigh > 3:
                        board[i][j] = -1
                else:
                    if neigh == 3:
                        board[i][j] = 2
                        
        for i in range(m):
            for j in range(n):
                if board[i][j] == -1:
                    board[i][j] = 0
                elif board[i][j] == 2:
                    board[i][j] = 1```
dark otter
#

how does AtBeginning works in Linked List?

summer fossil
# 
There are two battle arenas, one in ground and other in water. Each Pokemon may have different power in both the arenas.
When two Pokemon fight in an arena, the Pokemon having higher power in that arena wins. It is guaranteed that all Pokemon have distinct powers in the same arena to avoid any ties.

The strength of a Pokemon trainer is determined to be the number of other Pokemon his Pokemon can defeat in at least one arena.

It is known that only the Pokemon trainers with the highest strength will qualify for the next round (multiple trainers may have the same strength). Find the number of Pokemon trainers who will qualify for the next round```
#

How to approach this

vocal gorge
#

what complexity is needed? an O(N^2) solution is obvious - check every pair.

agile sundial
#

argsort would help I think

vocal gorge
#

yeah, probably there is some clever O(N log N) one

#

the thing is, if a beats b in both arenas, that still counts as just one victory, so you can't just sort the two lists independently and check the position

agile sundial
#

that's easy though, you can create a tuple of indices that sort the pokemon for each arena, then compare both in a third sort

#

I think?

vocal gorge
#

If a pokemon has indices i and j in the two sorted lists, then their strength is len(unique(arena1[:i] + arena2[:j])). Which is, hmm

summer fossil
#

water = sorted(list)

#

then

#

ground winner = list()

#

final winner = sum(ground winner+waterwinner)

agile sundial
#

what do you do if p beats q in water, but q beats p on land?

vocal gorge
#

they both beat each other, looks like 🥴

agile sundial
#

ah

agile sundial
vocal gorge
#

hmm, how'd that help?

#

if two pokemon have i1,j1 and i2,j2, then first beats second if i1>i2 or j1>j2.

#

I think I might have gotten it

#

i1>i2 or j1>j2 is the same as max(i1,j1) > min(i2,j2)

#

wait, is it

summer fossil
#

Now I'm confused

#

i wil try tommorow

vocal gorge
austere sparrow
untold island
#

why not

fiery cosmos
# eager root

Can you look up the algorithm. I do not believe there is merit in purely memorizing something

dense urchin
tall flame
#

You basically just need to know that log(n) = O(n) to prove the result

#

As the first and last term are easily O(n^3)

stray flame
# 
list_1.append(list_2)
list_1.append(list(list_2))
``` is there a reason why the first line doesnt work but the second does?
safe jacinth
#

The second one works because the list() function converts it to an object

#

It would be better to use extend()

stray flame
stray flame
safe jacinth
#

!e py li = ['test', 'test', 'test'] li2 = [6, 0, 4, 1] li.append(li2) print(li)

halcyon plankBOT
#

@safe jacinth :white_check_mark: Your 3.11 eval job has completed with return code 0.

['test', 'test', 'test', [6, 0, 4, 1]]
agile sundial
#

there's no reason the first wouldn't work and the second would work

safe jacinth
#

🤷‍♂️

halcyon plankBOT
#
Missing required argument

code

stray flame
#

vs

# 
li = ['test', 'test', 'test']
li2 = [6, 0, 4, 1]
li.append(list(li2))

del li2[-1]
print(li)```
safe jacinth
#

!e ```py
li = ['test', 'test', 'test']
li2 = [6, 0, 4, 1]
li.append(list(li2))

del li[3][0]
print(li)```

halcyon plankBOT
#

@safe jacinth :white_check_mark: Your 3.11 eval job has completed with return code 0.

['test', 'test', 'test', [0, 4, 1]]
safe jacinth
#

its all derived from OOP fundamentals

#

but it can be confusing at times

summer fossil
# 

a =  list(map(int, input().split()))
z=[]
for i in range(a[0]+1,a[1]+1):
    z.append(i)
d = []
for i in z:
    product = 1
 
    # Converting integer to string
    num = str(i)
     
    # Traversing the string
    for b in num:
        product = product * int(b)
    d.append(product)
e = list(map(str, d))
str1 = ' '

print(str1.join(e).count('0'))```
#

Runtimeerror

summer fossil
halcyon plankBOT
#

Hey @peak sun!

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

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

split obsidian
#

I think one idea (not sure how to validate) is to split up the input list and check to see if they are monotonically decreasing

vocal gorge
#

you can go over the list maintaining the stack and input state.
For example, you see a 4. There hasn't been any inputs yet (next input is 4) and stack is empty. So the only way this happened is if 5 pushes were made and then a pop, so now the stack is [0 1 2 3] and next input is 5.
Then you see a 3. That's on the top of the stack, so it's just a pop. Same until 9, on seeing which you conclude 5 more inputs were recieved.

#

If you see a number that's not the top of the stack and couldn't have come from extra pushes (because that number was already pushed, say), that sequence is impossible.

split obsidian
#

So something like this?

def valid_output(lst):
    s = Stack()
    c = 0
    
    for num in lst:
        while c <= num:
            s.push(c)
            c += 1
        if num == c or num == s.head.value:
            s.pop()
        else:
            raise AssertionError("This sequence is not possible")
vocal gorge
#

num == c isn't possible after the loop

#

besides that yeah, looks right to me

fiery cosmos
#

initializing and populating a python array is constant time yeah? O(1)?

#

what about slicing through an existing array and making a new subarray that is like lets say newarray = oldarray[0:n/2]?

fiery cosmos
#

also for this, it looks like between the 2nd and 3rd expressions they are adding 1 to k and the term above the summation, and subtracting 1 from every term to the right of the summation is it?

jolly mortar
fiery cosmos
jolly mortar
jolly mortar
#

so populating with n elements is O(n)

fiery cosmos
jolly mortar
#

yes

fiery cosmos
#

so then is initializing two new subarrays of first half and last half of an existing array 2n time?

# 
oldarray = [2,3,4,5,6,7]
n = len(oldarray)
newarraya = oldarray[0:n/2]
nerarrayb = oldarray[n/2:n]
jolly mortar
#

that is O(n) too

fiery cosmos
#

right its 2n = O(n)

coral grove
#

in conditonal probability, how do you estimate the numerator

#

if I don't have P(AnB)

timid anchor
#

I want to implement the concept of a filter function that takes an object and returns True or False or a third value that means there's not enough information to make a decision. Is there a particularly pythonic way to do this? My naive idea is to return None for the third value, then have conditions checking it check for explicit Falseness rather than implicit falseness.

shut breach
stuck wind
#

can someone explain how 2^(ceil)... has gone to 2(n-1) -1 ?

Screenshot_from_2022-09-11_20-29-23.png
vocal gorge
#

2^log_2(n) is just n. 2^ceil(log_2(n)) is the lowest power of 2 that's higher-or-equal to n.

#

this being 2n-2 is indeed weird, though. I mean, it's true that it's at most 2n-1, I guess.

#

oooh

#

yeah, that's right

stuck wind
#

so at most its 2n-1 ?

vocal gorge
#

That's the thing, 2n-1 is odd, so not a power of two.

#

So we can get a tighter upper bound of 2n-2.

#

that seems to be what's done here

fiery cosmos
#

this problem has to do with the summation of the degrees of a tree equaling 2n-2

#

idk why the formula stated implies that d_n = 1 and d_1 >= 2?

vocal gorge
#

though the second condition requires also n>2. Since if n<=2 (so that 2n-2<=n), then d1 can totally be 1 or less. For example, if n=2, then d=[1 1] gets the right sum without fullfilling the second condition.

fiery cosmos
#

1-2-2-1 is valid tree for this equation

vocal gorge
#

No, I mean if d_n is 2 or more, than by the precondition all d_is are 2 or more. Hence, the sum is at least 2n.

primal halo
#

Can someone try to solve my problem in selenium? ♥

#

Can't finde the element because it comes from a Post request

fiery cosmos
#

how can i do something for every combination of elements in a set

#

i'm looking at itertools, that gave me every combination of all elements in a list, but i want to bin each into its own set and then compare that to all other sets

#

wait i can just append that to a list

#

but then i'll want to try every possible combination where all elements are represented

#

sheesh this gets complex

fiery cosmos
#

Hello! Is is true that a complete search solution, when implemented properly, is always guaranteed to be correct?

runic tinsel
#

well yeah

#

that's what correct means

#

like it won't give the wrong answer

#

if you consider every option you're guaranteed to consider the right answer too, and it will be the one in the output

runic tinsel
#

suppose the set is {1,2,3}

#

what do you want to do

tribal ravine
#

@fiery cosmos are u using any libs to make this code work? :

#

oldarray = [2,3,4,5,6,7]
n = len(oldarray)
newarraya = oldarray[0:n/2]
nerarrayb = oldarray[n/2:n]

#

and in what IDE are u writing?

#

I had to change it to: oldarray = [2,3,4,5,6,7]
n = len(oldarray)
n=int(n)
newarraya = oldarray[0:(n//2)]
nerarrayb = oldarray[(n//2):n]

#

in order to make it work

#

@fiery cosmos when u answer please @me

fluid gate
#

why in the world am I getting this error?

unknown.png
zealous plover
#

because volume isn't defined before that while loop

fluid gate
#

it's in a nested function though no?

#

shouldn't that function have access to that variable?

zealous plover
#

no, you'd have to pass it in

fluid gate
#

then why isn't it complaining about heights ?

zealous plover
#

do you know thats a good question, I know that lists do behave weirdly inside of classes sometimes making them shared when they aren't supposed to be so maybe its that

#

but beyond that all I can suggest is passing the things in and maybe reconsidering using nested functions

fluid gate
#

yeah I don't really like using them but I also hate typing self all over the place lol

zealous plover
#

actually I think can also put "nonlocal volume" at the first line of the inner function definition to bring it into the scope I think, if that works probably also want to do it with k

zealous plover
fluid gate
#

oh wow, so it looks like volume is considered part of the inner scope because I'm decrementing it inside the nested function. I commented out the decrement on line 25 and it worked.

#

thanks for your help

bronze panther
#

i'm working on a program that's supposed to find every way to fill a 9xn grid with tetris pieces, where n%4=0.
rn I have a version of it working where I just go through left-right bottom-top and use recursive permutations to find everything, which doesn't scale well. I think I might've found a more efficient approach, but I'm not sure if it actually is better
the approach:
0) before starting the program, find every permutation of pieces that can make a horizonal line across the grid (aka every way the widths of the pieces (testing every rotation) can add up to 9)

  1. choose a horizontal line and try to put it halfway up the grid. Check if both empty area above and below line is divisible by 4 (otherwise it couldn't be filled by tetris pieces), go through and move each piece in the line up and down as much as it can while still being adjacent to the pieces next to it and check if space%4=0 for each of those two
  2. for all the cases where space%4=0, check above and below line and see if there's still at least one entirely empty row. If there is, do steps 1-4 for those areas too
  3. try to fill any empty spaces left over, discarding solutions where you can't
  4. repeat for every other horizontal line permutation in the list
#

no matter what i do i plan on pruning like crazy, but fundamentally is this algorithm better than just trying to find every permutation bottom-top like i was originally?

slate jolt
#

The other day I made a post on Stack Overflow regarding the statistics.median() function and was trying to come up with the best solution for a reduced time complexity since the current implementation sorts the data. However, the post became stale and I thought what better way than to get the help of the Python community. This is the link to the post: https://stackoverflow.com/q/73641157/10746872 . Any comments or insights are welcome!

Stack Overflow
Efficiently Find Median of an Unordered Set of Data

Background
I was looking into the statistics.median() function (link) in the Standard Library and decided to see how it was implemented in the source code. To my surprise, the median is calculated by

bronze panther
# slate jolt The other day I made a post on Stack Overflow regarding the `statistics.median()...

it looks like ultimately the Floyd-Rivest Algorithm still is partially sorting the list, but some sorting can be good because it'll keep you from having to check the entire list over and over
if you think about it, no matter what you're going to have to check every other element before you know that element is the median, but if the median turns out to be the last element you check you'll have to look at every single item of the list once for every single item of the list, which is a lot worse than a good sorting algorithm
Floyd-Rivest Algorithm finds a good middle ground, where it basically does quicksort, which is picking a number and splitting the other numbers into a "greater than" or "less than" category, but if it finds the median along the way it can end early

#

(plus some extra steps for if it's a really big list to cut it down first)

stuck wind
#

I am working on this question, the solution shows the time complexity of the inner loop is log_2(n), how is this possible? (Since the value of j is not reset to 1 every time)

Screenshot_from_2022-09-12_21-15-42.png
bronze panther
#

if n is twice as long, j will have to double one more time

fiery cosmos
#

Guys. We studied the coin-row problem in dynamic programming. I am not sure how popular it is. But if someone knows, in it we back track to find the bunch of coins that we have selected to achieve the max combination.

In that we take max of if the coin was taken or not. And while backtracking see if it matches with the taken or not taken category. And based on that see if the coin was taken or not.

My question is what if it turned out to be equal. How would we then decide if it was taken or not. Or if not, why can't it never be equal.

#

This is the coin row problem

bronze panther
# fiery cosmos

equal to what? are you asking what if there's two pairs of coins that are tied for the highest value?

split obsidian
#

In this question, the suggestion seems to be to search in the lower half, but it's not clear to me why? If we have no guarantee for ordering, why would it matter if you search the lower or upper half?

unknown.png
fiery cosmos
#

My question is what is the value when the coin was included. And the value when it was not. Turns out to be same in both scenarios.

bronze panther
jolly crypt
#

i have a really large list of words which have a correct spelling and are valid (i.e. kinda like an english dictionary). I would like to make a program that can suggest a list of possible correct spellings if an incorrectly spelt word is found within some text. One way would be to calculate the Levenshtein distance (or edit distance) between the incorrectly spelt word and every word in the so called dictionary and then return a list of words with the least edit distance. This would possibly work if there are only a few words spelt incorrectly, but what if I have a long paragraph with a lot of words spelt incorrectly? This approach would be quite inefficient, so what would be a more efficient way of tackling this problem?

fiery cosmos
fiery cosmos
#

guys my device aint letting me install pypiwin32

haughty mountain
#

which is dominated by the O(n) of the outer loop

haughty mountain
#

I do get a word out, but I only get it for the first one pithink

#

the second and third are slightly different

#

though almost the same when converted to digits

#

hint: ||look at the 1st and 2nd in groups of 3, 3rd in groups of 4||

tropic rover
haughty mountain
tropic rover
haughty mountain
#

I did the conversion in latin letters

#

do the first string, split into groups of 3, convert them to int

#

treat the ints as offsets, I have no clue where the "base" of the offset is, so I subtract the minimum from all the numbers

#

then I just brute force try some bases and see if something sensible pops out

#

with base I mean like if 98 (ascii 'b') is the base, offset 3 would mean 101 (ascii 'e')

#

I ended up with one base that produces what looked like a word and not just randomness

#

and I verified it was actually a word

#

ah, if I shift into the cyrillic part of unicode the 2nd one matches

#

the same word, just in cyrillic

#

the third one probably works in some other alphabet

tropic rover
haughty mountain
#

ah

tropic rover
haughty mountain
#

yeah, I get koloratura from the first one, and I get the thing you wrote from the second one

#

I didn't do anything smart, I just noted that the differences between adjacent numbers are basically the same in all messages

#

and small

#

so I assumed that it was some offsets in ascii/unicode

#

then I just brute forced some sensible bases for the offsets

#

and it ended up working

#

I didn't just want to spoil the thing by giving the word 😛

tropic rover
#

Thanks)

azure flame
#

Good lord I hate the cs program at my school

#

My professor is 70 years old just writing stuff on the board, and 90% of the time he writes something, he makes a mistake and erases it, so it's super hard to follow.

#

Class is Algorithms and Complexity

fiery cosmos
#

dang

#

sounds rough

tropic rover
outer rain
#

Can I share a cool problem I found with y'all?

#

It possibly is the coolest problem in my life, if anyone wants to check it out, you can try. But it's very difficult.

Given a d-regular bipartite graph with n+n vertices and m edges. Color its edges with d colors so that no two edges incident to the same vertex are colored in the same color in O(nm log(d)).

hint 1.1: ||Try to first solve this problem in O(nmd)||
hint 1.2: ||Why is such coloring exists in the first place?||
hint 1.3: ||What Hall's condition tells about such graph?||
hint 1.4: ||How can you reduce the problem from d to d - 1?||
hint 1.5: ||Use Kuhn's algorithm to color n edges per iteration||

hint 2.1: ||Which ideas can be used to improve from O(nmd) to O(nm log(d))?||
hint 2.2: ||What if d is even?||
hint 2.3: ||What if d is odd?||
hint 2.4: ||Why does Eulerian cycle always exists for such graph?||
hint 2.5: ||Reduce the problem from d to d / 2||

Solution: ||Such graph always contains a complete matching because of Hall's condition. This matching can be found in O(nm) using Kuhn's algorithm. All the edges in this matching can be colored in one color and the rest of the graph is still a regular bipartite graph, therefore this idea can be used again, effectively reducing the problem from d colors to d - 1 colors. This can be used to solve the problem in O(nmd). Now let's use divide and conquer. If d is odd, use that same idea. This will reduce d by 1, effectively making it even. If d is even, find a Eulerian cycle, which exists because of Euler's theorem. Take odd-indexed edges of that cycle and build a graph with those edges, recursively run the algorithm on that graph. Notice that this graph is isomorphic to a graph built from even-indexed edges, moreover, the isomorphism is obvious: you can match i-th edge to (i+1) edge. Recursively color the built graph in d/2 colors, and the rest of the edges in the remaining d/2 colors.||

#

I find this problem very difficult, despite having a fairly simple solution, which requires a lot of non-linear steps to figure out. I like that it also requires a lot of knowledge of graph theory, but nothing too advanced, basically ||two algorithms and a deep understanding of them||. Oh, and no, I have not solved it myself.

vast folio
#

Hello, I am learning data structures with Python, do you know of a good book or page, channel, etc. that you recommend for my learning. Also if someone has knowledge on the subject and can help me from time to time I would appreciate it

tall flame
raven kraken
mighty pelican
#

anyone know how to swap linked list nodes?

#

tryna add a sorting method on my linked list

haughty mountain
#

though you'll have a fun edge case for the first node

mighty pelican
#

yeee im tryna do a sorting method for my linked list and idk how i would do itpithink

last fulcrum
#

For the question below I'll like to know why they return the max instead of just returning the ans? Thanks.
Q: Given a binary tree root, count and return the number of nodes where its value is greater than or equal to the values of all of its descendants.
Solution

    def solve(self, root):
        ans = 0
 
        def dfs(root):
            if not root:
                return -math.inf
            nonlocal ans
            left = dfs(root.left)
            right = dfs(root.right)
            if root.val >= left and root.val >= right:
                ans += 1
            return max(left, right, root.val)
 
        dfs(root)
        return ans
outer rain
#

because it traverses the tree and counts amount of required nodes

#

so everything that function must know is whether the current node should be counted or not

#

and to do this it evaluates the max among all the values of its descendants

#

(recursively)

last fulcrum
# outer rain you mean in inner function?

Still a bit confused. A root would know what the values of it's child nodes are. So the root can just check to see if it's greater than it's child's node. Why would it need to count the amount of nodes?

outer rain
last fulcrum
# outer rain how would root node know it's descendants' values?

That means that for a node, then node has to determine if that node is greater than all it's descendants right?
But if we use that thinking then we should only increment ans after the node checks all it's descendants. Not before. But the solution looks like we are doing it before.

outer rain
last fulcrum
outer rain
last fulcrum
#

Thank you again.

fiery cosmos
#

why would i be getting invalid syntax on an else statement

#

indentation is proper

#

there is a return above it in my if statement.. is that the cause?

agile sundial
#

maybe

fiery cosmos
#

so weird

worthy badge
#

Enter N elements to a one-dimensional array and display the divisors of all entered numbers. Use functions and parameter passing to develop the exercise.

#

anyone could help me pls?

#

idk how to resolve it

agile sundial
#

what have you tried so far

fiery cosmos
#

I’ve tried having a little search online but haven’t been able to find anything as of yet.

Can anyone point me in the direction of some resources on or names of algorithms that deal with layout/spacing of things? I want to create a mind map sort of thing and not sure how to approach the layout/automatic positioning of nodes

haughty mountain
#

either use graphviz itself, or you might be able to find the algos they use

fiery cosmos
#

Thanks for the info, I couldn’t find anything after trying a few different keywords. Kept finding a lot of algorithms that had names that sounded like I want but had nothing to do it with it lol

haughty mountain
fiery cosmos
#

Ah cheers

haughty mountain
#

this answer has a bunch of links

fiery cosmos
#

Thanks I’m just trying to find as many resources on the topic as I can find

#

No experience at all with this so want to learn how it all works as best as I can

haughty mountain
#

I don't know that much about how their algos are implemented, I think some of the ones for large networks use spring models, though the output from those isn't always great

#

dot is good if you have a hierarchy in your graph

fiery cosmos
#

Okay good to know

#

Yeah I’m just looking to create a tool to make my own mind maps or possibly other diagrams

haughty mountain
#

and there are a bunch more modes in graphviz

fiery cosmos
#

Everything will be hierarchical so that works out fine

haughty mountain
#

I'm assuming you want something radial? I can't recall if graphviz has a mode for that

#

ah you might want their twopi mode @fiery cosmos

fiery cosmos
#

Tbh I think what I’m looking for at the moment can be done with some simple maths. Since it will be basically a tree. But I do want to know about other layout algorithms anyway

haughty mountain
fiery cosmos
#

Okay thanks! Really appreciate the time/help

haughty mountain
#

it should be easy enough to generate a graphviz file to test it

#

it's a simple format

fiery cosmos
#

hi all,

#

trying to write a random matrix generator for testing my matrix algos (giant thanks to @haughty mountain without which they would not exist)

#

here is what I have so far:

# 
import random

def matrix_generator(size):

    output = []
    for n in range(size):
        n = random.randint(0,5)
        output.append([n]*size for _ in range(n))

    return output

y = matrix_generator(6)
print(y)
#

it's not working but im hoping someone can point out what i'm doing wrong, ty

#

nvm, i can figure it out with python tutor

haughty mountain
#

several issues

#

you don't want to assign the random value to a variable

#

your append is also quite weird

#

what's inside the append is generating n copies of [n, n, ...] (len = size)

#

which is not at all what you want

#

you want to append

[random.randint(0, 5) for _ in range(size)]
#

which gives you 1 list of ken size with random elements

#

and since this is the very typical case of appending to an initially empty array, use another list comprehension

# 
[[random.randint(0, 5) for _ in range(size)] for _ in range(size)]
fiery cosmos
#

ok tysm

#

hmm for testing purpose, do you think i should expand the integer range? i understand larger ints require more computational power. i suppose it doesn't matter so long as i test identical inputs on my naive and recursive matrix multiplication algos

#

actually you know what? i need to print to file in an entirely different format anyway

#

i need the format to be like:
`2
4 1
2 3
4 2
3 1

4
a b c d
d b c e
b c d e
a c d b
a b c d
d b c e
b c d e
a c d b`

#

i guess i could take the way this is working and just split on , and [ ] and print the ints to file..

#

ok so i'm currently printing something like this to output:
[[6, 3, 5, 4], [9, 9, 5, 7], [7, 2, 8, 6], [9, 5, 5, 3]] [[4, 9, 8, 2], [3, 8, 9, 5], [5, 8, 3, 4], [3, 6, 9, 4]] [[6, 7, 0, 5], [2, 1, 2, 5], [9, 9, 6, 3], [8, 7, 8, 5]] [[5, 3, 8, 7], [5, 5, 6, 2], [1, 3, 0, 0], [4, 0, 5, 8]]

#

how can i scrub all the brackets and commas

#

i suppose i could write another function that takes this file as input and splits? but that is probably a complex way of doing things..

vocal gorge
#

i understand larger ints require more computational power
For matrix multiplication? Well, yes, multiplying ints in python takes compute proportional to log(a) log(b).
To be more precise though, ints are stored as 40-bit 30-bit digits, and the more digits, the more operations to multiply them. So until your ints get bigger than 2^40 2^30, you won't see a change in time.

fiery cosmos
#

2^40 bits?

vocal gorge
#

Yeah, for some complicated reasons they don't use all the bits of the underlying 64-bit 32-bit integers. Might be misremembering the number wildly, though.

fiery cosmos
#

what sort of int would be at or larger than 2^40 bits? also:

# 
def matrix_formatter(inpfile):
    with open('formattedmatrixtest.txt','w') as output:
        for f in inpfile:
            y = next(f).split(',','[',']')
            print(y,file=output)

matrix_formatter('matrixtest.txt')
vocal gorge
# fiery cosmos 2^40 bits?

Ah, no, I mean bigger than 2^40 2^30 in value, so that their representation doesn't fit in 40 30 bits.

fiery cosmos
#

trying to split on the chars shown above and print to a new output file, getting 'str' object is not an iterator

fiery cosmos
vocal gorge
#

a long time ago I even got a plot (by timing int multiplication) on which you could see these jumps

vocal gorge
#

it's 30 bits, looks like, I probably forgot the number over the months 😔

halcyon plankBOT
#

Include/pyport.h lines 107 to 113

/* PYLONG_BITS_IN_DIGIT describes the number of bits per "digit" (limb) in the
 * PyLongObject implementation (longintrepr.h). It's currently either 30 or 15,
 * defaulting to 30. The 15-bit digit option may be removed in the future.
 */
#ifndef PYLONG_BITS_IN_DIGIT
#define PYLONG_BITS_IN_DIGIT 30
#endif```
fiery cosmos
#

i guess my question now is, how can i unzip a list of lists into individual lists, and then unpack those into just the containing integers, separated by whitespace

fiery cosmos
#

to instead:
6 3 5 4 9 9 2 1 .. .. ..

vocal gorge
#

you want to flatten the nested list, then

fiery cosmos
#

not all the way

#

i still want each list to be on its own line

vocal gorge
#

ah, true

fiery cosmos
#

in the out

vocal gorge
#

well, just do something like

for sublst in lst:
    print(*sublst, file=fo)
#

print separates by spaces and leaves a newline afterwards, like you want

fiery cosmos
#

this is currently a generator and a formatter function, can i make them both into one?

#

this is what i have:

# 
import random

def matrix_generator(size):
    with open('matrixtest.txt','w') as output:
    
        for n in range(size):
            print(([[random.randint(0, 9) for _ in range(size)] for _ in range(size)]),file=output)


y = matrix_generator(4)

def matrix_formatter(inpfile):
    with open('formattedmatrixtest.txt','w') as output:
        with open(inpfile) as f:
            y = next(f)
            y = y.split(',')
            y = y.split('[')
            y = y.split(']')
            print(y,file=output)

matrix_formatter('matrixtest.txt')
agile sundial
#

I would keep them different, SRP and all that

fiery cosmos
#

i'm really bad with file i/o

#

i'm a hack programmer

#

probably should be in this chan, but here we are

vocal gorge
#

you could json.loads each line instead of manually parsign it

fiery cosmos
#

hm ok i'll have to learn that

vocal gorge
#

also, split is very likely not what you want for [ and ], but rather something like replace("[","")

agile sundial
#

or just json the entire thing

vocal gorge
#

won't be valid json

#

each line is, but the entire thing isn't

agile sundial
#

I mean when they output it also

vocal gorge
#

if they wrapped it in another list it'd work, sure

agile sundial
#

I thought they originally had a matrix?

tropic rock
#

...Can someone please tell me how this works

concatScores = [y for x in computingScores for y in x]`
#[[1, 2, 3], [4, 5, 6]] => [1, 2, 3, 4, 5, 6]

it's supposed to concatenate a list of lists into a single list, but i can't follow the comprehension

fiery cosmos
#

the output looks like this:

#

[[0, 1, 5, 4], [9, 8, 4, 9], [3, 9, 1, 4], [8, 5, 4, 9]] [[4, 6, 8, 0], [9, 1, 7, 4], [7, 1, 2, 4], [1, 8, 6, 6]] [[7, 4, 6, 5], [7, 8, 2, 5], [6, 8, 2, 0], [3, 3, 2, 2]] [[5, 8, 9, 2], [0, 0, 6, 1], [3, 8, 2, 4], [3, 9, 9, 6]]

#

i want the same thing but each matrix printed one after another followed by no newlines and w no chars: like:

#

0 1 2 4 4 1 2 0 0 1 2 4 4 1 2 0 0 1 2 4 4 1 2 0 0 1 2 4 4 1 2 0

#

(that'd be the first two)

agile sundial
fiery cosmos
#

anyhow, gotta run, i appreciate any and all information put here which i will review upon my return

vocal gorge
tropic rock
#

oh my god

#

lol usually i can follow this stuff

#

thanks

tropic rock
# fiery cosmos ```py import random def matrix_generator(size): with open('matrixtest.txt',...

You could just skip the .txt middleman and reference the list you make in the print() directly

import random
def matrixgenerator(size):
    for n in range(size):
        formattedmatrix = [[random.randint(0, 9) for _ in range(size)] for _ in range(size)]
    for i in formattedmatrix:
        print(" ".join([str(x) for x in i]))
    return formattedmatrix

#prints
7 8 9 6
5 7 5 8
2 0 1 8
7 6 7 1
#returns (for if writing it somewhere is important)
[[....], [....], [....], [....]]
haughty mountain
#

30 bits per digit

#

dammit, discord showing me old stuff

vocal gorge
#

basically, I learned that tidbit more than a year ago and over months I forgot the numbers 😔

#

i have the memory of a reptile, okay

haughty mountain
#

so, the reasons is probably just convenience

#

multiply two digits and you have 60 bits

#

leave some room for carries and addition

#

you like to have the arithmetic fit nicely in a primitive type

vocal gorge
#

from what I remember from comments, no

#

lemme find them...

halcyon plankBOT
#

Include/cpython/longintrepr.h lines 24 to 36

- PyLong_{As,From}ByteArray require that PyLong_SHIFT be at least 8

- long_hash() requires that PyLong_SHIFT is *strictly* less than the number
  of bits in an unsigned long, as do the PyLong <-> long (or unsigned long)
  conversion functions

- the Python int <-> size_t/Py_ssize_t conversion functions expect that
  PyLong_SHIFT is strictly less than the number of bits in a size_t

- the marshal code currently expects that PyLong_SHIFT is a multiple of 15

- NSMALLNEGINTS and NSMALLPOSINTS should be small enough to fit in a single
  digit; with the current values this forces PyLong_SHIFT >= 9```
haughty mountain
halcyon plankBOT
#

Include/cpython/longintrepr.h lines 17 to 19

Type 'digit' should be able to hold 2*PyLong_BASE-1, and type 'twodigits'
should be an unsigned integer type able to hold all integers up to
PyLong_BASE*PyLong_BASE-1.  x_sub assumes that 'digit' is an unsigned type,```
vocal gorge
#

wait, this is about PYLONG_SHIFT actually, no idea if that puts constraints on the digit size

haughty mountain
#

that's what I mean

fiery cosmos
#

can someone remind me how to do the coverfile generation?

#

i think i have the command written somewhere lms

haughty mountain
#

!d trace this?

halcyon plankBOT
#
trace

Source code: Lib/trace.py

The trace module allows you to trace program execution, generate annotated statement coverage listings, print caller/callee relationships and list functions executed during a program run. It can be used in another program or from the command line.

fiery cosmos
#

idk it was something that generated a cover file. i wrote down the command somewhere i think i can dig it out

#

yes it was this or something similar

#

yeah you're right it was trace

#

hmm how can i run trace on a .py program that i have to also run with an input

#

the way i run trace is a call to the command prompt

#

like this:

#

python -m trace --count bubblesort.py

#

if bubblesort takes in input, would i do like:
python -m trace --count bubblesort('bubinput.txt').py?

haughty mountain
#

I'm assuming

python -m trace --count bubblesort.py bubinput.txt
fiery cosmos
#

ok!

fiery cosmos
#

what's the command prompt command to view files?

#

ls?

#

lol my comp is super not liking the trace and count command

#

i ran it on the smallest input and its getting real loud

#

oh nvm i had the largest inputfile in there as input

past jetty
#

Hey guys, is there a library that does signal alignments automatically in python? for example

unknown.png
#

I could only find very complicated scripts that don't work for many cases

#

to get from a to b

fluid gate
#

does .items() return a list or an iterator? does it run in N time?

#

what's the best way to get the first value in a dictionary?

jolly mortar
jolly mortar
fluid gate
#

Does that run in constant time? I'm trying to use an ordered dict like a queue. I need to check the first element to see if it meets a condition. If it does I want to pop it.

dark aurora
#

Does anyone know how to solve this task in python?

#

My solution doesn't pass the time limits

#

but it should

#

here it is

# 
n, q = list(map(int, input().split()))

a, b = [0]*(n+1), [0]*(n+1)

def upd(i, val, ls):
    while i<n:
        ls[i] = ls[i]+val
        i =  i+(i&-i)

def getS(i, ls):
    sm = 0
    while i>0:
        sm = sm+ls[i]
        i = i-(i&-i)
    return sm


for i in range(q):
    i = list(map(int, input().split()))
    if i[0]==1:
        upd(i[1], 1, a)
        upd(i[2], 1, b)
    elif i[0]==2:
        upd(i[1], -1, a)
        upd(i[2], -1, b)
    else:
        x1, y1, x2, y2 = i[1], i[2], i[3], i[4]
        if getS(x2, a)-getS(x1-1, a)==(x2-x1+1) or getS(y2, b)-getS(y1-1, b)==(y2-y1+1):
            print("Yes")
        else:
            print("No")
dark aurora
#

When I put fast input it gets wrong answer?

#

I used fenwick tree

slim bough
#

hello!

tall flame
fiery cosmos
haughty mountain
brittle moat
#

guys I've been trying to solve this for 3h

# 
def inventory_summary_id():
    bundled_items = []
    index_tracker = 1
    for x, transaction in enumerate(inventory_dump):
        
        inventory_type = inventory_dump[x]['inventory_item_type_fk']
        
        if inventory_type  == inventory_dump[index_tracker]['inventory_item_type_fk']:
            continue
        
        else:
            new_dict = create_inventory_summary(inventory_dump[x: index_tracker])
            bundled_items.append(new_dict)
            index_tracker = x + 1
            
    response = jsonify(bundled_items)
    return response, 200

def create_inventory_summary(collections):
        temp_dict = {
            "inventory_item_type_fk": collections[0]['inventory_item_type_fk'],
            "total in": 0,
            "total out": 0,
            "diff": 0
        }

        for inventory_object in collections:
            if inventory_object['in_qty'] != None:
                temp_dict['total in'] += inventory_object['in_qty']
            elif inventory_object['out_qty'] != None:
                temp_dict['total out'] += inventory_object['out_qty']
        
        temp_dict["diff"] = temp_dict["total in"] - temp_dict["total out"]

        
        return temp_dict```
#

It's only passing through one item in inventory_dump, when there's 2.

shut breach
brittle moat
#

Ye

shut breach
#

it sounds like just a bug

last fulcrum
#

I'm trying to improve my time complexity analysis. Came up with a brute force solution to this question
https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
This is my code and my time complexity should be O(height of tree x height of tree)
If I'm wrong what can I do to better analyse time complexity.

    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        
        if not root:
            return []
        
        max_depth = 0
        
        def find_depth(root, depth = 0):
            
            nonlocal max_depth
            
            if not root:
                return
            
            if depth > max_depth:
                max_depth = depth
            
            find_depth(root.right, depth + 1)
            find_depth(root.left, depth + 1)
            
            return max(depth, max_depth)
        
        depth = find_depth(root)
        res = [[] for _ in range(depth + 1)]
        
        def dfs(root, depth_to_use):
            
            nonlocal res
            nonlocal depth
            
            if not root:
                return
            
            dfs(root.right, depth_to_use + 1)
            dfs(root.left, depth_to_use + 1)
            
            res[depth_to_use].insert(0, root.val)
            
        dfs(root, 0)
        return res[::-1]

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

tall flame
fringe pond
#

hey just a really quick question so a max heap algorithm has a constant nlogn for all cases so let say you have a max heap of A=[1-100] and B=[1-200] and were ask to merge the two heap would it be wrong to just add all element into a new array and then max-heap it?

agile sundial
#

isn't heapify O(n)

fringe pond
#

lgn

#

heap sort is nlgn my bad

summer fossil
#

Subsets of array = {1, 2, 3}

#

how to approach this anyone explain me

#

plz

safe jacinth
#

What is the question?

summer fossil
#

total subsets is 8 =2**3 print all subset

#

I will trying and i found this answer but didn't understand last line

        if A == []:
            return [[]]

        x = self.subsets(A[1:])
        return (x + [[A[0]] + y for y in x])```
safe jacinth
#

:(

summer fossil
dense fulcrum
#

guys is there A good book for Data Structures and Algorithms in Python ?

quaint bluff
#

im having a hard time displaying data from a api call in a clear way: [{'type': {'kode': 'DAGL', 'beskrivelse': 'Daglig leder/ adm.direktør', '_links': {'self': {'href': 'https://data.brreg.no/enhetsregisteret/api/roller/rollegruppetyper/DAGL'}}}, 'sistEndret': '2010-01-25', 'roller': [{'type': {'kode': 'DAGL', 'beskrivelse': 'Daglig leder/ adm.direktør', '_links': {'self': {'href': 'https://data.brreg.no/enhetsregisteret/api/roller/rolletyper/DAGL'}}}, 'person': {'fodselsdato': '1969-08-11', 'navn': {'fornavn': 'Pål', 'etternavn': 'Christoffersen'}, 'erDoed': False}, 'fratraadt': False, 'rekkefolge': 0}]}, {'type': {'kode': 'STYR', 'beskrivelse': 'Styre', '_links': {'self': {'href': 'https://data.brreg.no/enhetsregisteret/api/roller/rollegruppetyper/STYR'}}}, 'sistEndret': '2012-10-30', 'roller': [{'type': {'kode': 'LEDE', 'beskrivelse': 'Styrets leder', '_links': {'self': {'href': 'https://data.brreg.no/enhetsregisteret/api/roller/rolletyper/LEDE'}}}, 'person': {'fodselsdato': '1969-08-11', 'navn': {'fornavn': 'Pål', 'etternavn': 'Christoffersen'}, 'erDoed': False}, 'fratraadt': False, 'rekkefolge': 0}, {'type': {'kode': 'VARA', 'beskrivelse': 'Varamedlem', '_links': {'self': {'href': 'https://data.brreg.no/enhetsregisteret/api/roller/rolletyper/VARA'}}}, 'person': {'fodselsdato': '1967-07-27', 'navn': {'fornavn': 'Runar', 'etternavn': 'Solberg'}, 'erDoed': False}, 'fratraadt': False, 'rekkefolge': 1}]}]

#

i have tried looping through and extracting data, but i find it hard, can anybody give me some tips / help? 😄

tacit drift
#

Hi!
I need to give the tightest possible upper bound for the worst-case running time of some algorithms.
One of them is

Finding and removing all values greater than 12 from a stack implemented 
with a LinkedList (leaving the rest of the stack in its original order)

I think it should be O(n) because we need to perform at least one complete traversal of the stack in order to be sure that we have removed all elements greater than 12.
But how do you leave the rest of the stack in its original order?

icy nymph
quaint bluff
icy nymph
#

Hmm 6429_cute_colors_think We can try putting into a table with the Rich.table module

#

Let me go make some coffee real quick and I'll try to help you out

quaint bluff
icy nymph
#

Do you have any code already written?

#

With the API

wheat timber
#

hey lads, I deeply need your help, been blocking me for a while

#

haven't found a way to convert my spiral matrix function into this (even if i have already the code to plot it)
using this code i generate this spiral matrix:

#

!e```py
#!/usr/bin/env python
NORTH, S, W, E = (0, -1), (0, 1), (-1, 0), (1, 0) # directions
turn_right = {S: W, W: NORTH, NORTH: E, E: S} # old -> new direction

def spiral(width, height):
if width < 1 or height < 1:
raise ValueError
x, y = width // 2, height // 2 # start near the center
dx, dy = NORTH # initial direction
matrix = [[None] * width for _ in range(height)]
count = 0
while True:
count += 1
matrix[y][x] = count # visit
# try to turn right
new_dx, new_dy = turn_right[dx,dy]
new_x, new_y = x + new_dx, y + new_dy
if (0 <= new_x < width and 0 <= new_y < height and
matrix[new_y][new_x] is None): # can turn right
x, y = new_x, new_y
dx, dy = new_dx, new_dy
else: # try to move straight
x, y = x + dx, y + dy
if not (0 <= x < width and 0 <= y < height):
return matrix # nowhere to go

def print_matrix(matrix):
width = len(str(max(el for row in matrix for el in row if el is not None)))
fmt = "{:0%dd}" % width
for row in matrix:
print(" ".join("_"*width if el is None else fmt.format(el) for el in row))

print_matrix(spiral(19,20))```

halcyon plankBOT
#

@wheat timber :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___
002 | 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361
003 | 342 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290
004 | 341 272 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 291
005 | 340 271 210 157 158 159 160 161 162 163 164 165 166 167 168 169 170 227 292
006 | 339 270 209 156 111 112 113 114 115 116 117 118 119 120 121 122 171 228 293
007 | 338 269 208 155 110 073 074 075 076 077 078 079 080 081 082 123 172 229 294
008 | 337 268 207 154 109 072 043 044 045 046 047 048 049 050 083 124 173 230 295
009 | 336 267 206 153 108 071 042 021 022 023 024 025 026 051 084 125 174 231 296
010 | 335 266 205 152 107 070 041 020 007 008 009 010 027 052 085 126 175 232 297
011 | 334 265 204 151 106 069 040 019 006 001 002 011 028 053 086 127 176 233 298
... (truncated - too many lines)

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

wheat timber
#

and now I want to use this spiral matrix output
into:

# 
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle as Rect
import numpy as np

x = np.arange(361).reshape((19,19))

cell_text = []
cell_colours = []
for i in range(10):
    cell_text.append([])
    cell_colours.append([])
    for j in range(10):
        cell_text[i].append(str(x[i, j]))
        if i == j or i == 9 - j:
            cell_colours[i].append("yellow")
        else:
            cell_colours[i].append("none")

fig, ax = plt.subplots()

ax.get_xaxis().set_visible(False)
ax.get_yaxis().set_visible(False)
ax.axes.spines["left"].set_color(None)
ax.axes.spines["right"].set_color(None)
ax.axes.spines["top"].set_color(None)
ax.axes.spines["bottom"].set_color(None)
ax.set_aspect("equal")

table = plt.table(cellText=cell_text, cellColours=cell_colours, cellLoc="center", bbox=[0, 0, 1, 1])

for k, v in table._cells.items():
    v.set_edgecolor((0.7, 0.7, 0.7))

for i in range(10):
    ax.add_patch(Rect((0.5-0.1*i, 0.5-0.1*i), 0.2*i, 0.2*i, facecolor="none", edgecolor="black", lw=1.5))

plt.show()
#

**which gives this outputt: **

#

**What i want to do is to use my spiral matrix generated with the above code and put it inside this plotted matrix with the yellow colors showing up **
it should be like this:

#

any help appreciated, honestly this has been blocking me for days can't find a solution online.... I gave the 2 code I use, i just dont know how to make one use the another thats the problem

tacit drift
#

Does anyone know how I could solve this recurrence relation?

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

I think it's not possible with Master Theorem but I don't know another way. I think the result might be n^n but I'm not sure

haughty mountain
#

turns out the terms shrink quite quickly compared to n^n

#

you could then try an inductive proof to formalize it

#

example induction

Assume:
T(n) = 2^n T(n/2) + n^n < c n^n

Check if consistent, use T(n/2) < c: (n/2)^(n/2)                             
T(n) = 2^n T(n/2) + n^n
     < 2^n c(n/2)^(n/2) + n^n
     = 2^n c n^(n/2) / 2^(n/2) + n^n
     = 2^(n/2) c n^(n/2) + n^n

Now, if this < c n^n? For large enough c and n > 2 for sure yes.
#

trivially a lower bound Ω for the complexity is n^n, so this is even a tight bound Θ

tacit drift
#

Thanks

wheat timber
halcyon tartan
#

anyone can help me solve this?

Sort_the_Fabrics_-_Kick_Start_-_Google_Chrome_19_09_2022_00_33_19.png
haughty mountain
#

not in an ongoing round, wtf?

pulsar light
vocal gorge
austere quartz
#

What is the proper way to pass in the head node in Python?
I'm trying to return the middle node of the list. I think my code is right but i may be passing the argument wrong.

class Node:

    def __init__(self, val, nextNode = None, prev = None):
        #Node constructor sets val = val , sets next to nullptr, sets, prev to nullptr
        self.val = val
        self.next = nextNode
        self.prev = prev

    def __str__(self):
        return str(self.value)


class LinkedList:

    def __init__(self, values= None):
        self.head = None
        self.tail = None

        if values is not None:
            self.addMultipleNodes(values)

    def addNode(self, value):

        if self.head == None:
            self.head = Node(value)
            self.tail = self.head
        else:
            self.tail.next = Node(value)
            self.tail = self.tail.next

        return self.tail

    
    def middleOfList(self, headNode):
        # use fast and slow pointers to find middle of list

        fast = headNode
        slow = fast

        while fast and fast.next != None:
            slow = slow.next
            fast = fast.next.next
        
        return slow

list1 = LinkedList()
list1.addNode(7)
list1.addNode(34)
list1.addNode(55)
list1.addNode(99999)
list1.addNode(5000)

print(list1.middleOfList(list1.head))
dark aurora
pulsar light
tall flame
# dark aurora Mate I don't know how to solve it with sets if you can share it, would be great

My code is C++ unfortunately.

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> xcnt(n);
    vector<int> ycnt(n);
    set<int> x0set, y0set;
    for (int i = 0; i < n; ++i) {
        x0set.insert(i);
        y0set.insert(i);
    }
 
    auto place = [&](int x, int y) {
        --x; --y;
        if (xcnt[x] == 0) x0set.erase(x);
        if (ycnt[y] == 0) y0set.erase(y);
        ++xcnt[x]; ++ycnt[y];
    };
 
    auto remove = [&](int x, int y) {
        --x; --y;
        --xcnt[x]; --ycnt[y];
        if (xcnt[x] == 0) x0set.insert(x);
        if (ycnt[y] == 0) y0set.insert(y);
    };
 
    auto is_attacked = [&](int x1, int x2, int y1, int y2) {
        --x1; --x2; --y1; --y2;
        
        auto xit = x0set.lower_bound(x1);
        auto yit = y0set.lower_bound(y1);
        
        return (xit == x0set.end() or *xit > x2) or 
               (yit == y0set.end() or *yit > y2);
    };
 
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int x, y;
            cin >> x >> y;
            place(x, y);
        } else if (t == 2) {
            int x, y;
            cin >> x >> y;
            remove(x, y);
        } else if (t == 3) {
            int x1, x2, y1, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            cout << (is_attacked(x1, x2, y1, y2) ? "Yes" : "No") << '\n';
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    solve();
}

Notice the ios::sync_with_stdio(false); cin.tie(nullptr);, it makes input/output operations faster, without it my code doesn't pass the time limit. There might be such tricks on Python.

dark aurora
#

I mean from my last few submissions I got wrong answer, and I don't know how I did that

#

Well, seems like this it the time to switch to c

tall flame
#

I might give it a try on Python, with the same idea.
I'll tell you if I get to have any useful insight.

#

Ok... so the Python alternative to ordered_sets is using Segment Trees apparently 😭
I feel so bad for you, it's really frustrating when you get the right idea but for some obscure reason it doesn't work.

dense jolt
tight cobalt
#

can anyone help with an error i get?

#

ValueError: 20 is not in range

#

the code brakes bc of this error

#

and i dont undersant why

agile sundial
#

can you send the code

#

also, is this an algorithm problem?

tight cobalt
#

yes algirthm

#

now i get this

#

ValueError: The truth value of a DataFrame is ambiguous. Use a.empty, a.bool(), a.item(), a.any() or a.all().

agile sundial
#

you still haven't sent the code

tight cobalt
#

cant do that sadly

agile sundial
#

can't really help then

tight cobalt
#

ahh okay thanks haha

austere quartz
#

Question: Im trying to check if my linked list is empty or not. I get two different results based on where im calling the function. Why might this be happening?

list1 = LinkedList()
list1.addNode(7)
list1.addNode(34)
list1.addNode(55)
list1.addNode(99999)
list1.addNode(5000)
# print(list1.isEmpty()) Returns False it isnt empty

arr = [7,99,1222,66]
list1.addMultipleNodes(arr)
list1.addToFront(56875678)
list1.printList()
# print(list1.isEmpty()) Returns True it is empty
fiery cosmos
#

anyone familiar with coalesced hashing?

agile sundial
#

what about it?

agile sundial
fiery cosmos
#

I mean a fixed number of keys

fiery cosmos
#

algorithms 😬

fiery cosmos
#

Is this algorithm divide and conquer? Because it's dividing, but the problem size still remains the same.

Screenshot_20220919-215109317_1.jpg
agile sundial
#

yes

agile sundial
agile sundial
fiery cosmos
#

Can I call it brute force

#

Because the complexity still remains O(n) ig

#

Same as linear search

#

It's probably worse than brute force because of recursions

#

Actually

#

It also returns the frequency

#

Hello , how can i round the result of my code. I dont need exponential nmber but a round nmber. Below is my code with output

#

proba_predict = classifier.predict_proba(df_billets)
proba_predict
array([[9.94439715e-01, 5.56028471e-03],
[9.99141369e-01, 8.58630953e-04],
[9.98590052e-01, 1.40994750e-03],
[8.58594896e-02, 9.14140510e-01],
[4.10139987e-04, 9.99589860e-01]])

agile sundial
fiery cosmos
#

The complexity is coming to be log n by recurrence relation though

#

c(n)=2*c(n/2)+1. c(1)=0

#

Is that correct for addition as base operation

#

So
It would be
2^k c(1) +k finally

#

Where k=log(n)

#

@agile sundial

agile sundial
#

doesn't that mean n? 2^(lg n) is just n

fiery cosmos
#

Naah

#

C(1)=0

#

So

#

n*0+log(n)

haughty mountain
#

it's O(n log n)

#

oh wait

#

nvm, there is no work done

fiery cosmos
#

Wdym

haughty mountain
#

or constant work I guess

#

so it's O(n)

fiery cosmos
haughty mountain
#

this part is correct 2^k c(1) + k

#

but k = log(n)

#

so n c(1) + log n

#

c(1) is not 0 though

#

it still does something, some constant amount of work

#

so overall O(n)

fiery cosmos
#

In the description it said find the recurrence relation based on considering addition as the base function

#

So there's no addition happening in c(0)

haughty mountain
#

that's ridiculous, equality checks and item lookups are not 0 cost

#

and if I want to be super pedantic indexing an array does addition, so 🤷‍♀️

jolly mortar
#

looks like list.count

haughty mountain
#

it is

tall flame
#

Hum I think the closed formula looks something like:
c(2^k) = 2^k * (c(1) + 1) - 1

haughty mountain
#

not that is matters to the complexity at all

#

still O(n)

fiery cosmos
#

Given that A is already sorted in a non-decreasing order, design an algorithm with worst-case time complexity O(n) that outputs the absolute values of the elements of A in an increasing order with no duplications:

#

If I am understanding it right. It just wants me to remove the duplicates and use absolute value for all the elements in an already sorted array?

#

Also in the example shown it is not inputting a sorted array

#

Example: for A = [3,−6,1,−3,20,6,−9,−15], the output is B= [1,3,6,9,15,20]

agile sundial
fiery cosmos
agile sundial
#

¯_(ツ)_/¯ bad example I guess

haughty mountain
#

because ||timsort is O(n) on that input||

delicate orbit
#

Find upper bound for f(n) = n4 + 100n2 + 50

#

c=2 No=50 is this right or wrong

#

some one check this i am new in dsa

quiet minnow
#

Hi!
I have 99% of my program completed. But I need one last step and I don't know how to do that. python

The program is a BFS algorithm. It's looking for the shortest path. It's based on square grid with obstacles. You can **eliminate **those obstacles (e.g. k = 1).
It works like that: You enter the k that is amount of obstacles you are able to eliminate. Then you enter the scale of a grid, source coordinations, destination coordinations and obstacles coordinations.

I need one thing to be done. I want the program to print coordinations of every step. That means coordinations of every square (cell) in the shortest path of that square grid.

I would really appreciate any help 🙏

Thanks in advance!

The code:
https://pastecode.io/s/h94futx5

tall flame
# quiet minnow Hi! I have **99%** of my program **completed**. But I need **one last step** and...

You need to somehow store the predecessor of every point on the shortest paths
Whenever you do something like distance[ax][ay] = distance[x][y] + 1 you do it because the shortest path you know so far from source to (ax, ay) goes through (x, y) (then add one step), so here the predecessor of (ax, ay) is (x, y).
Once you have that, and the BFS is done, you can compute the points of the shortest path by looking at the predecessor of your destination cell, then in turn it's predecessors... up until the source.

quiet minnow
#

@tall flame Btw for your info, I want the output like this:

7 # Number of total steps
0 0 # Step 1 - x y
0 1 # Step 2 - x y
1 1
2 1
3 1
....

tall flame
#

are you sure the algorithm is correct btw?

dreamy kayak
#

!paste

halcyon plankBOT
#

Pasting large amounts of code

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

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

quiet minnow
#

@dreamy kayak Wait a second

#

@dreamy kayak here you are.
Smile icon = Start
X icon = End
Spiral = obstacle

dreamy kayak
quiet minnow
#

The algorithm works like this picture but flipped vertically, like this:

shot-2022-09-19_20-14-26.jpg
dreamy kayak
#

are you really going to make me type out the list by hand?

quiet minnow
#

I don't use this. The list is automatically generated by your input.

dreamy kayak
#

ok:

board = [
    [0,0,0,0,0],
    [0,1,0,0,0],
    [0,0,0,0,0],
    [0,0,1,1,0],
    [0,0,0,0,0],
]
quiet minnow
#

you can make board 3x3 or even 20x20

#

and make the 1's wherever you want

dreamy kayak
#

I just needed a test case

quiet minnow
#

INPUT:
5 # The board will be 5x5 squares
0 0 # The start square is on position x,y = 0, 0
4 3 # The end square is on position x, y = 4, 3
0 # No obstacle eliminations possible.
3 # There will be 3 obstacles on the board.
1 1 # Position of 1st obstacle. (x, y)
2 3 # Position of 2nd obstacle. (x, y)
3 3 # Position of 3rd obstacle. (x, y)

#

Raw input:
5
0 0
4 3
0
3
1 1
2 3
3 3

dreamy kayak
#

oops, posted in wrong channel.

#

here:

from collections import deque

def get_neighbors(board,x,y):
    return {(x+dx,y+dy) for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]
         if 0<=x+dx<len(board) and 0<=y+dy<len(board[0]) }
   
def bfs(board, walls, start, goal):
    queue = deque([(start, [], set(), walls)])
    while queue:
        cell,path,seen,walls = queue.popleft()
        if cell == goal:
            return path
        seen.add( (cell, walls) )
        for x,y in get_neighbors(board,*cell):
            if ((x,y), walls)  not in seen:
                if board[x][y]==0:
                    queue.append(((x,y), path + [(x,y)], seen.copy(), walls))
                elif walls>0:
                    queue.append(((x,y), path + [(x,y)], seen.copy(), walls-1))
    # no path
    return []

I used a deque because it's faster than a list, but a list would work too, just slower.

#

also works when there is no possible path. 🙂

#

Like I said before neighbors function does not change per run, so you might want to precalculate that instead of finding it every run. Or add a cache to it with @functools.cache()

merry hornet
#

I'm trying to use recursion to delete the first instance of an item within a list, I'm getting the correct output, but is there any way to maintain the original order of the list without adding an extra parameter or global static variable?

idk.PNG
fiery cosmos
#

hi all,
in CLRS they claim that for a binary tree, the children's subtrees each have size at most 2n/3, and thus the runtime of max heapify is T(n)<=T(2n/3)+theta(1)

#

what is the formula for the size of the subtrees of a d-ary tree

#

guess: dn/d+1?

craggy glade
#

how can i invert a tree in my ass

#

width of the tree is very high

fiery cosmos
#

uh what

haughty mountain
fiery cosmos
#

so was my guess for dn/d+1 totally wrong

haughty mountain
#

tbh I haven't really thought about what it boils down to for d-ary trees

#

it should be easy enough to derive

fiery cosmos
#

i'll try on my whiteboard but the wording in confusing, they talk about a given subtree of size n rooted at node i, the size of it's children's subtrees, it isn't straightforward which nodes exactly to count when deriving a new expression

haughty mountain
#

useful fact: a complete subtree of height h has 2^h - 1 nodes

fiery cosmos
#

a complete binary tree

#

a complete binary subtree

haughty mountain
#

complete binary subtree, right

fiery cosmos
#

so a complete d-ary subtree of height h presumably has d^h-1 nodes

#

also, how can i return a simple counter variable from my functions without ruining the code? eg right now the return statements return the only thing i need (which is not this counter), i guess i'd have to return them both as a tuple and then change a bunch of other statements elsewhere

#

i'll be back, i need to eat dinner before it gets too late (i have reflux disease)

haughty mountain
fiery cosmos
#

im not surprised

haughty mountain
#

the number of nodes in a binary tree is 1 + 2 + 4 + ... which is why it's one less than a power of two

#

in a d-ary tree it's 1 + d + d^2 + d^3 + ...

#

so it should boil down to a geometric sum

#

so I think it's (d^h - 1)/(d - 1)

#

yeah, seems to check out

#

so roughly 2/3

unknown.png
#

equivalently for d-ary:

n = (d^h - 1)/(d-1) + (d^(h-1) - 1)/(d-1) + 1
haughty mountain
#

so for large d this tends to 1 pithink

#

interesting

#

the worst case gets more and more unbalanced

fiery cosmos
#

oh so i was correct? wow

#

its so strange to me when something seems intuitive and its totally wrong and other times the intuitive answer is correct

#

oh thats the proof for the number of nodes of children's subtrees of size n in d-ary subtree

haughty mountain
#

intuition is a double edged sword, rely on it too much and you'll have issues

#

intuition + some math to verify/debunk goes a long way though

haughty mountain
fiery cosmos
#

ok so i can use dn/(d+1) and plug into the recurrence relation for the runtime of max heapify

fiery cosmos
haughty mountain
#

it's the same argument I kinda made in the image for a binary tree

fiery cosmos
haughty mountain
#

just algebraically

haughty mountain
#

a small example

..o
 / \
 o o
/ \
o o
fiery cosmos
#

O / \ O O / \ O O

haughty mountain
#

apparently the code block doesn't like leading whitespacem at least in the phone client

fiery cosmos
#

oof

#

oh was it bc you were doing a half empty subtree

#

ok so my new expression for the runtime of EXTRACT-MAX, in a d-ary max heap is based on the runtime of MAX-HEAPIFY of the underlying d-ary tree (which is called by extract max), and that runtime recurrence is given by
T(n)<=T(2n/3)+theta(n)

#

they go on to solve that w the master theorem, but my b is equal to d+1

#

oh

#

but that's strictly greater than 1 because any d-ary tree has d>2 children

#

so i can solve w master theorem. sweet

#

oof. i think i derived the runtime for this operation on a d-ary tree but theres such a great chance its incorrect

tight cobalt
#

Someone can explain something to me?

ruby quail
#

Just ask man. At least that way someone can read your question and help rather than you waiting for hours for someone to say yes

delicate orbit
#

yo

fiery cosmos
#

is this the only way to make this work?

fiery cosmos
haughty mountain
#

one subtree with height h + one with height h-1 + the root

#

the size of a complete d-ary subtree we discussed yesterday

fiery cosmos
#

i don't understand why they are different heights at the same lvl, but that's a discussion for another time. rn i am trying to implement another parameter coming back out from the multiply function in the strassen's algo, but simply telling that function to return something like calls_to_multiply is breaking things elsewhere, i am thinking i'll have to return them as a tuple and unpack elsewhere? what is the difference between return a, b and return(a,b) is the first statement valid

#

hmm they are the same statement according to my test

#

so like i can see how to make it work here:

# 
def my_test_function():
        a=1
        b=2
        return (a,b)

unpack,unpack2 = my_test_function()
print(unpack)
#

but not in an algo with all the various calls and recursion

halcyon plankBOT
#

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

1
fiery cosmos
#

i'm getting a Type error in the matrix_addition function

#

googling gives:

#

Python TypeError: 'int' object is not subscriptable
This error occurs when you try to use the integer type value as an array. In simple terms, this error occurs when your program has a variable that is treated as an array by your function, but actually, that variable is an integer.

#

but i don't see why adding another variable to my return statement elsewhere would cause this

#

maybe im just reading the input in wrong somehow

haughty mountain
haughty mountain
#

the left subtree of the root has height 2

#

the right had height 1

#

h and h-1 in my terminology

fiery cosmos
#

oh right

fiery cosmos
haughty mountain
#

the error should tell you what is an int that shouldn't be an int, and then you can try to track that variable backwards from there to see where the int assignment happens

fiery cosmos
#

it'd be tough to show the whole thing and i'm getting like 7 errors. basically i am trying to return a counter of the multiplications done by the multiply function. right now that only returns a matrix product, so adding another variable to my return has broken things elsewhere

#

right now i am doing it "by hand" and generating a cover file trace run for each input

#

which i cannot call with a flag, i have to modify the python code each time to handle the new input

haughty mountain
#

what are you trying to count?

#

ah

#

multiplications

fiery cosmos
#

the number of matrix multiplications utilized by strassen's and naive and return it as a statistic after running for example, "your return matrix is a and was computed utilizing b multiplications"

#

right

haughty mountain
#

you could wrap the numbers in a class

#

that would be fairly clean

fiery cosmos
#

so it works pretty well by utilizing cover files, but its painfully laborious

#
  • time consuming
#

i think for the naive algo it'll be easier but the strassen's is proving difficult bc of the recursive nature

haughty mountain
# 
class MyInt:
  mul_count = 0
  def __init__(self, value):
    self.value = value
  def __add__(self, other):
    return MyInt(self.value + other.value)
  def __mul__(self, other):
    MyInt.mul_count += 1
    return MyInt(self.value * other.value)
  ...
#

i.e. wrap all ints in a class, define the relevant operator overloads, and have this class track multiplications

#

no change to the implementation of strassen

fiery cosmos
#

i appreciate the simplicity of your solution, but that's likely above my skill level

haughty mountain
#

you say that

#

it's not that involved

#

you need to learn about operator overloading, but that's mostly it

fiery cosmos
#

yeah i'm still working on classes and list comprehensions 😂

#

but ok, probably worth attempting at least

agile sundial
#

I think that does fit here

rare musk
#

I just wanna talk about DSA and not generally about careers @fiery cosmos

wheat timber
#

hey guys i needyour help

# 
MASTER_WIDTH    = 19
MASTER_HEIGHT   = 19

degrees = helio[helio.Date == today].values.tolist()[0]
degrees.pop(0)
planets = ["Ear", "Mer", "Ven", "Mar", "Jup", "Sat", "Ura", "Nep", "Plu"]
planet_hash = dict(zip(degrees, planets))
planet_hash

matrix = [[307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325],[306,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,326],
[305,240,183,184,185,186,187,188,189,190,191,192,193,194,195,196, 197,258,327],[304,239,182,133,134,135,136,137,138,139,140,141,142,143,144,145,198,259,328],[303,238,181,132,91,92,93,94,95,96,97,98,99,100,101,146,199,260,329],
[302,237,180,131,90,57,58,59,60,61,62,63,64,65,102,147,200,261,330],[301,236,179,130,89,56,31,32,33,34,35,36,37,66,103,148,201,262,331],[300,235,178,129,88,55,30,13,14,15,16,17,38,67,104,149,202,263,332],
[299,234,177,128,87,54,29,12,3,4,5,18,39,68,105,150,203,264,333],[298,233,176,127,86,53,28,11,2,1,6,19,40,69,106,151,204,265,334],[297,232,175,126,85,52,27,10,9,8,7,20,41,70,107,152,205,266,335],
[296,231,174,125,84,51,26,25,24,23,22,21,42,71,108,153,206,267,336],[295,230,173,124,83,50,49,48,47,46,45,44,43,72,109,154,207,268,337],[294,229,172,123,82,81,80,79,78,77,76,75,74,73,110,155,208,269,338],
[293,228,171,122,121,120,119,118,117,116,115,114,113,112,111,156,209,270,339],[292,227,170,169,168,167,166,165,164,163,162,161,160,159,158,157,210,271,340],[291,226,225,224,223,222,221,220,219,218,217,216,215,214,213,212,211,272,341],
[290,289,288,287,286,285,284,283,282,281,280,279,278,277,276,275,274,273,342],[361,360,359,358,357,356,355,354,353,352,351,350,349,348,347,346,345,344,343]]
new_matrix = []

for row in matrix:
    x = []
    for i, degree in enumerate(row):
        if i < len(row):
            x.append(planet_hash[degree]) if degree in planet_hash.keys() else x.append(degree)
    new_matrix.append(x)

out_mat = new_matrix

cell_text = []
cell_colours = []
for i in range(MASTER_HEIGHT):
    cell_text.append([])
    cell_colours.append([])
    for j in range(MASTER_WIDTH):
        cell_text[i].append(str(out_mat[i][j]))
        if  i == j \
            or i == (18-j) \
            or j == (MASTER_WIDTH // 2) \
            or i == (MASTER_HEIGHT // 2):
            cell_colours[i].append("yellow")
        else:
            cell_colours[i].append("none")

fig, ax = plt.subplots()
fig.set_size_inches(15, 15, forward=True)

ax.get_xaxis().set_visible(False)
ax.get_yaxis().set_visible(False)
ax.axes.spines["left"].set_color(None)
ax.axes.spines["right"].set_color(None)
ax.axes.spines["top"].set_color(None)
ax.axes.spines["bottom"].set_color(None)
ax.set_aspect("equal")

table = plt.table(cellText=cell_text, cellColours=cell_colours, cellLoc="center", bbox=[0, 0, 1, 1])

for k, v in table._cells.items():
    v.set_edgecolor((0.7, 0.7, 0.7))

for i in range(10):
    ax.add_patch(Rect((2-0.1*i, 2-0.1*i), 0.2*i, 0.2*i, facecolor="none", edgecolor="black", lw=1.5))

plt.show()```
#

^ this above code generate:

#

i just want now the Planets case ("Ear", "Nep", "Mer", etc...) to have a different background, make it purple (so it can be way more easier to read them)

# 
cell_text = []
cell_colours = []
for i in range(MASTER_HEIGHT):
    cell_text.append([])
    cell_colours.append([])
    for j in range(MASTER_WIDTH):
        cell_text[i].append(str(out_mat[i][j]))
        if  i == j \
            or i == (18-j) \
            or j == (MASTER_WIDTH // 2) \
            or i == (MASTER_HEIGHT // 2):
            cell_colours[i].append("yellow")
        else:
            cell_colours[i].append("none")
#

i think i have to add to the if statement something about the Planets inside the spiral matrix
but idk how to do it
the expected output should be this

haughty mountain
# haughty mountain ```py class MyInt: mul_count = 0 def __init__(self, value): self.value =... 
In [6]: class MyInt(int):
   ...:   mul_count = 0
   ...:   def __init__(self, value):
   ...:     self.value = value
   ...:   def __add__(self, other):
   ...:     return MyInt(self.value + other.value)
   ...:   def __mul__(self, other):
   ...:     MyInt.mul_count += 1
   ...:     return MyInt(self.value * other.value)
   ...:

In [7]: a = [MyInt(i+1) for i in range(10)]

In [8]: sum((x*y for x,y in zip(a, a)), start=MyInt(0))
Out[8]: 385

In [9]: MyInt.mul_count
Out[9]: 10
haughty mountain
#

if so maybe just use a global variable

fiery cosmos
#

for strassen's?

#

i think we're forbidden from global variables, i could check

#

i'm wondering if im counting the multiplications wrong. i don't think i am. for strassen's i'm only counting when it gets to the base of the recursion and does a multiplication operation

#

but its like less than half of the operations of naive

#

which i wouldn't expect

#

i thought it was supposed to be like 2 for each 3 of naive or similar

#

oh its n^2.8 vs. n^3

#

oh wow

wheat timber
fiery cosmos
#

for naive, it's in exact precise agreement

haughty mountain
fiery cosmos
#

wow these trace runs are taking ages

#

python is really slow huh

#

maybe i should start learning rust

haughty mountain
#

you're also using the variant that recurses all the way down

fiery cosmos
#

trueee

haughty mountain
#

I get 823543 muls for N=128, the math checks out

In [6]: 128**3 / 823543
Out[6]: 2.546499697040713

In [7]: 128**(3 - 2.8074)
Out[7]: 2.545942788702071
#

actually, maybe just

In [8]: 128**2.8074
Out[8]: 823723.1446465984
fiery cosmos
#

i got the exact same

#

823,543

#

my 256*256 trace run took 10 minutes, i'm afraid to run the 512*512 ☠️

#

5764801 mults

#

its very close to 256^2.8

#

which is 5.53m

haughty mountain
#

10 minutes seems pretty slow

#

let me check how mine does

#

granted, faster hardware

fiery cosmos
#

well it's a trace w count, the algo itself takes 94s

#

without a trace

haughty mountain
#

ok 22s gives 5764801

#

lol, I just use a global

fiery cosmos
#

huh

#

256x256?

haughty mountain
#

yes

fiery cosmos
#

yeah i get the exact same number

#

damn i need to learn global variables, wasting so much time

#

what is the theoretical time this'll take? if i run a trace w 512 by 512?

fiery cosmos
haughty mountain
fiery cosmos
#

yeah no i'm not gonna burn up energy doing that. i'll just model it based on my previous runs

haughty mountain
# 
muls = 0

def mat_mul_strassen(A, B):
  ...
  n = len(A)
  if n == 1:
    global muls
    muls += 1
    return [[A[0][0] * B[0][0]]]

  ...

...

n = 2**8
A = rand_matrix(n, n)
B = rand_matrix(n, n)
C_strassen = mat_mul_strassen(A, B)
print(muls)
fiery cosmos
#

i tried going that route and got local variable referenced before assignment

#

also, my "style" grade is based on not using globals

#

whatever that means

haughty mountain
#

even for counting muls?

#

it's such a trivial and simple way to do it though

#

add it, get the count, remove it

#

rather than modifying the whole code

fiery cosmos
#

yeah you're right, i'm going to use that

#

it'll still take 11m just to run without any of the trace stuff

#

my naive did 134m mults in 37s 😝

#

thats why you get a 3.7GHz 6-core

haughty mountain
#

do they expect you to do 512?

haughty mountain
fiery cosmos
#

loose guidelines

#

oh rly?

haughty mountain
#

this is single threaded

fiery cosmos
#

what is, python?

wheat timber
haughty mountain
fiery cosmos
#

can one write a python script that'd take advantage of the ability of the cpu to do parallel processing?

haughty mountain
#

not really in python itself

#

if non-python code does the heavy work then you can get some of that

#

but multithreading strassen feels like pain anyway

fiery cosmos
#

like a different language or how do you mean

fiery cosmos
haughty mountain
fiery cosmos
#

i can look at the individual cores but they're kind of all over the place. i expected to see a single one near 100% utilization

#

i guess the others are handling other processes, discord, etc

fiery cosmos
wheat timber
haughty mountain
fiery cosmos
#

another reason to implement this would be error checking

#

eg, an input is a letter

#

i'm trying and failing to implement in a different manner

#

how do i do like if myfun returns Error, do y

wheat timber
haughty mountain
haughty mountain
#

returning some special value?

#

raising an exception?

fiery cosmos
#

i'm handling it as

  raise ValueError```
and then handling the ValueError later. it's working well except that there are a lot of different combinations of errors that could occur and that the required input looks different than my input
haughty mountain
#

what are you even trying to do here?

fiery cosmos
#

for example, the various errors that are raised might be occurring due to trailing whitespace, or an unexpected blank line, and my test inputs are slightly different than their required input

haughty mountain
#

tbh, I would probably just try to make something that works with their input, as flawed as it is

fiery cosmos
#

so at first i just wanted to return an error to the output file if one of the matrix elements is a letter, but more generally fulfill the requirement of error checking

haughty mountain
#

oh, do they require you to do error checking on their input?

fiery cosmos
#

no, i have the exact input. they want us to generate our own input that simulates novice errors, for example, a value occurring in one of the matrices is a letter, or both matrices are all zeroes (input that checks extreme case). i'm just dreaming up examples to fit their requirements

haughty mountain
#

both matrices being zero is valid though

fiery cosmos
#

i'm pretty happy with what i have, not going to be able to fulfill every expert programming requirement

#

especially when my input and theirs are slightly different

haughty mountain
#

do you still have this hackiness of catching a valueerror to detect end of file?

fiery cosmos
#

i'm sure i do, yes

haughty mountain
#

eww

fiery cosmos
#

🤷‍♂️

#

wwad

haughty mountain
#

you could make something more sensible if you just do f.read().strip().split('\n\n') to get a list of the blocks

#

and then you have blocks to parse that don't have annoying whitespace issues

fiery cosmos
#

hmm

#

oh i also found the "random matrix generator" was returning a second matrix all the same lol. so i fixed that

#

like every row was the same integers

fiery cosmos
haughty mountain
#

like, it should work fine

#

the strip is to remove all leading and trailing whitespace

fiery cosmos
#

it should work fine for their input or mine

haughty mountain
#

what's your input format?

fiery cosmos
# 
matrixA
matrixB```
haughty mountain
#

isn't that the same as theirs?

fiery cosmos
#

no theirs is 1 file like:

order
mata
matb

order
matc
matd

order
mate
matf
haughty mountain
#

oh, you only give 1 case?

fiery cosmos
#

with whitespace between

#

i do one case at a time in my tests, yeah

haughty mountain
#

that's the same format though

fiery cosmos
#

no they have the whitespace between inputs

haughty mountain
#

it's their format but with just one case

fiery cosmos
#

well yes but i would not test it doing multiple sized matrices at once

haughty mountain
fiery cosmos
#

then counting multiplications would become difficult with regards to input size

#

the inputs would be conflated

haughty mountain
#

not if you add the counting stuff to the code

#

rather than relying on the trace tool

fiery cosmos
#

right well they said 'no globals' and i couldn't figure out how to implement return calls giving me counts without breaking everything

haughty mountain
#

!e

import io

f = io.StringIO('''
order
mata
matb

order
matc
matd

order
mate
matf

''')

for block in f.read().strip().split('\n\n'):
  print('TODO: parse this block')
  print(block)
  print('---')
halcyon plankBOT
#

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

001 | TODO: parse this block
002 | order
003 | mata
004 | matb
005 | ---
006 | TODO: parse this block
007 | order
008 | matc
009 | matd
010 | ---
011 | TODO: parse this block
... (truncated - too many lines)

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

haughty mountain
#

every call to multiply would return the multiplications happening inside it, right?

fiery cosmos
#

i tried making a counter within the base case and returning that along with the matrix product, but that requires changing and unpacking things everywhere else. i showed like my base knowledge with the demo code before

fiery cosmos
haughty mountain
#

this kind of thing, it's terrible but should work

def multiply(a, b):
  total_mults = 0
  ...
  mults, res = multiply(...)
  total_mults += mults
  mults, res = multiply(...)
  total_mults += mults
  
  return total_mults, result
#

what actually failed in your code?

fiery cosmos
#

Python TypeError: 'int' object is not subscriptable

haughty mountain
#

it gives more info than that, surely

fiery cosmos
#

like i wouldn't even know where to put it i don't want to return the multiply counter every time i do the base lvl recursion, i guess it doesn't matter if i'm not printing it?

fiery cosmos
#

i just don't like that my error statements print my entire directly

#

directory

haughty mountain
fiery cosmos
#

i'll get you the exact errors, hang on

#

Exception has occurred: TypeError 'int' object is not subscriptable File "C:\Users\Steve\Desktop\desktop\school\fall22algorithms\codingprojects\strassens_matrix_multiplier.py", line 42, in mat_add c[i][j] = a[i][j] + b[i][j] File "C:\Users\Steve\Desktop\desktop\school\fall22algorithms\codingprojects\strassens_matrix_multiplier.py", line 95, in multiply C11 = mat_add(mat_sub(mat_add(P5, P4), P2), P6) File "C:\Users\Steve\Desktop\desktop\school\fall22algorithms\codingprojects\strassens_matrix_multiplier.py", line 86, in multiply P1 = multiply(subs_a[0][0],S1) File "C:\Users\Steve\Desktop\desktop\school\fall22algorithms\codingprojects\strassens_matrix_multiplier.py", line 86, in multiply P1 = multiply(subs_a[0][0],S1) File "C:\Users\Steve\Desktop\desktop\school\fall22algorithms\codingprojects\strassens_matrix_multiplier.py", line 86, in multiply P1 = multiply(subs_a[0][0],S1) File "C:\Users\Steve\Desktop\desktop\school\fall22algorithms\codingprojects\strassens_matrix_multiplier.py", line 133, in strassensmatrixmultiply c = multiply(matrixa, matrixb) File "C:\Users\Steve\Desktop\desktop\school\fall22algorithms\codingprojects\strassens_matrix_multiplier.py", line 153, in <module> strassensmatrixmultiply('16by16random_matrix_test.txt')

#

can i hide the entire path any way?

haughty mountain
#

idk other than just doing a search replace in a text editor

#

so one of your a, b and c seems to end up as int at line 42

#

figure out which (e.g. by printing just before)

#

and then backtrack to figure out what sets it to an int

haughty mountain
#

returning two values in all returns, packing up two values in every call to the function

fiery cosmos
#

no i've only added:

def multiply(matrixa, matrixb):
    n = len(matrixa)
    c = make_zero_matrix(n, n)
    mult_counter = 0

    if n == 1:
        if isinstance(matrixa[0][0],str) or isinstance(matrixb[0][0],str):
            raise ValueError
        c[0][0] = matrixa[0][0]*matrixb[0][0]
        mult_counter+=1
        return c, mult_counter
haughty mountain
#

wait, what does the lines that call multiply look like?

fiery cosmos
#

c = multiply(matrixa, matrixb)

haughty mountain
#

so...

#

can you see the issue there

fiery cosmos
#

right i need like c,mult = multiply(mata,matb)

haughty mountain
#

right

fiery cosmos
#

hmm

#

i may actually be able to implement counting multiplications into the output file this way

#

what about these calls:
P1 = multiply(subs_a[0][0],S1) P2 = multiply(S2,subs_b[1][1]) P3 = multiply(S3,subs_b[0][0]) P4 = multiply(subs_a[1][1],S4) P5 = multiply(S5,S6) P6 = multiply(S7,S8) P7 = multiply(S9,S10)

haughty mountain
#

yeah...have fun duplicating that thing for all those

#

this is why I don't exactly like the idea of an extra return value

#

so much bookkeeping

#

so, another solution could be to not return the counts, but instead pass something in that can do the counting

fiery cosmos
haughty mountain
#

like, it's not hard, it's just annoying bookkeeping

fiery cosmos
#

wouldn't that be counting all multiplications for every integer though?

haughty mountain
#

I meant you can pass in some special object that just holds the count and that can be incremented

fiery cosmos
#

a single 512*512 has 262,144 ints

haughty mountain
#

e.g.

def multiply(a, b, counter):
  ...
  counter.increment()
fiery cosmos
#

i'd want to only increment it at the base case however, and there are hundreds of recursive calls to multiply that are not the base case

haughty mountain
#

!e

class Counter:
  def __init__(self):
    self.count = 0
  def increment(self):
    self.count += 1

def f(n, counter):
  if n == 1:
    counter.increment()
    return
  f(n-1, counter)
  f(n-1, counter)

counter = Counter()
f(6, counter)
print(counter.count)
halcyon plankBOT
#

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

32
haughty mountain
#

it's less invasive, but still not...great

#

I've seen similar stuff before though

#

you don't have to modify the returns to make this thing work

#

you just need to pass an extra argument along

fiery cosmos
haughty mountain
#

it should remove the awkward bookkeeping summing return values

fiery cosmos
#

what's the problem we are solving ?

#

ok so that is working, although i think maybe not exactly in the way you had envisioned

haughty mountain
fiery cosmos
#

like i think some bits of it are.. not used in my implementation? or redundant? maybe not. it's definitely printing the exact proper value..

haughty mountain
#

what's redundant?

fiery cosmos
#

what's the f function about

#

and the two lines:
f(n-1, counter) f(n-1, counter)

haughty mountain
#

just an example function where I want to count something

fiery cosmos
#

ohh ok

haughty mountain
#

I pass the counter object along, and increment it at the last level of the recursion

#

just an example of how you can do this kind of counting

#

it's not as invasive as having a bunch of return value handling

#

just pass an extra argument in all calls and you can always act on that object

fiery cosmos
#

right. and only required passing the counter to each of the 7 P matrices. easy

#

its working for 32by32 as well

haughty mountain
#

in each call to multiply

fiery cosmos
#

and i've got it printing to an output, which i needed to implement anyhow

haughty mountain
#

you don't pass stuff to the matrices

fiery cosmos
#

huh

#

i'm just allowing it to go along for the calls to multiply

#

like this:

# 
P1 = multiply(subs_a[0][0],S1,counter)
P2 = multiply(S2,subs_b[1][1],counter)
P3 = multiply(S3,subs_b[0][0],counter)
P4 = multiply(subs_a[1][1],S4,counter)
P5 = multiply(S5,S6,counter)
P6 = multiply(S7,S8,counter)
P7 = multiply(S9,S10,counter)
olive quail
#

So... say i have X amount of user names that are all fake, but are being created and used by 1 individual (who is a scammer) is there a way to have python compile all known data, and possibly return a true user?? If so where the h*ll do i start.

haughty mountain
haughty mountain
fiery cosmos
#

ok i got it working with a naive one as well

#

awesome

olive quail
#

@haughty mountain thanks! I wasnt sure where to start, figured algorithms was a good place as any

twin yew
#

Hey guys I now this isnt python but is someone here able to help me with basic level Nasm assembly code?

patent spire
twin yew
fiery cosmos
#

Is there someone here who has implemented a coalesced hashing deletion algorithm?

crimson steeple
#

any function with log(logn)

#

algorithm*

haughty mountain
fiery cosmos
#

there is strassen again

#

must have been a sharp cookie

haughty mountain
#

fwiw sieve of eratosthenes is O(n log log n) which is fun to try to prove

#

and schönhage strassen is O(n log n log log n)

last fulcrum
#

@haughty mountain quick question. Any books or videos you can recommened for me to improve my time complexity analysis?
At this point it's really bad

haughty mountain
#

I don't know of too many resources, for me it's mostly been reading about random algos and writing a bunch of my own stuff

#

doing competitive programming kinda forces you to get good at recognizing and estimating time complexities 😄

last fulcrum
#

So you'll say it was because you practised a lot then

haughty mountain
#

I think that's true for basically everything though

#

I have a pretty strong math background which certainly helps

#

time complexity is all about counting something, and doing that easily requires some math shortcuts

#

combinatorics, recurrences, ...

#

for the sieve of eratosthenes even some number theory if you want to get the log log n bound rather than the easier log n bound

#

which already requires some math knowledge

#

e.g. sieve of eratosthenes is basically

for every prime p < n:
  mark all multiples of p as not prime
#

it's not trivial to analyze

last fulcrum
haughty mountain
#

which you kinda have to recognize as the harmonic series to know 1 + 1/2 + 1/3 + ... + 1/n ~ log(n)

haughty mountain
#

so you can probably ask here

#

(preferably with a not too terrible code sample)

fiery cosmos
#

also who is that guy on youtube who describes the asymptotic notations to well, i'

#

i'll find it

haughty mountain
fiery cosmos
#

of course. but you have to have a base somewhere or at least a systematic approach to get a handle on things

fiery cosmos
# last fulcrum I do admit that I need to practise a lot but I wish when I write the code and es...

https://www.youtube.com/channel/UCZCFT11CWBi3MHNlGf019nw

YouTube
Abdul Bari

I have started this channel to help Students Community to learn difficult topics, from computer science, with a simple and detailed explanation.
I have been teaching some computer science subjects and Programming Languages for a long time and also been working as a freelancer and providing software solutions.
My experience and understanding of...

haughty mountain
#

when we get to "all we need to do is to count X" we can start attacking things with math

#

and vastly simplify the situation

#

turning loops into sums that we know how to work with and manipulate

#

that kind of thing

last fulcrum
fiery cosmos
#

his asymptotic complexity explanations were great for me as a beginner

last fulcrum
#

Thank you @haughty mountain @fiery cosmos
I learnt some things and hope to incorporate them

fiery cosmos
#

you can probably get a .pdf of the "bible" on algos and complexity, introduction to algorithms, for free on the internet somewhere

#

lots of great cost analysis stuff in there in the first 4 chapters

#

i myself need to learn indicator random variables, number theory, and expectations

fiery cosmos
#

is naive matrix multiplication O(n^3) or Θ(n^3)?

#

i'll check the book

#

it's Θ(n^3)

haughty mountain
fiery cosmos
#

when submitting code for assignments, should it be text or like .py format

#

i'm not seeing it specified anywhere

haughty mountain
#

.py is a text format pithink

#

thanks lancebot

fiery cosmos
#

i'm a bit confused on how to make this so one can run it from the command line. i typically change my calls to my function and outputfile name right directly within vscode and run. i've modified the scripts so that one can run it and it'll give prompts for the input file and a name for the desired output file

#

but trying to run this script with cmd or python i am not having any luck

haughty mountain
#

than reading from stdin

#

!d sys.argv

halcyon plankBOT
#
sys.argv 

sys.argv```
The list of command line arguments passed to a Python script. `argv[0]` is the script name (it is operating system dependent whether this is a full pathname or not). If the command was executed using the [`-c`](https://docs.python.org/3/using/cmdline.html#cmdoption-c) command line option to the interpreter, `argv[0]` is set to the string `'-c'`. If no script name was passed to the Python interpreter, `argv[0]` is the empty string.

To loop over the standard input, or the list of files given on the command line, see the [`fileinput`](https://docs.python.org/3/library/fileinput.html#module-fileinput "fileinput: Loop over standard input or a list of files.") module.

See also [`sys.orig_argv`](https://docs.python.org/3/library/sys.html#sys.orig_argv "sys.orig_argv").

Note

On Unix, command line arguments are passed by bytes from OS. Python decodes them with filesystem encoding and “surrogateescape” error handler. When you need original bytes, you can get it by `[os.fsencode(arg) for arg in sys.argv]`.
fiery cosmos
#

oh i figured it out, i can just go to the dir where the scripts are and call python myscript.py

#

after running cmd there

haughty mountain
fiery cosmos
#

oh!

#

is that what you've linked above?

haughty mountain
#

yes

fiery cosmos
#

and you're saying this is better than prompting the user for an in and prompting for them to name an output

haughty mountain
# 
$ cat a.py
import sys
print(sys.argv)
$ python a.py hello world
['a.py', 'hello', 'world']
haughty mountain
#

of course you can make reading from stdin work as well if you want to

#

but it's a bit more annoying to call from the command line like that

#

though easier to use if you're not using the command line I guess

fiery cosmos
#

hmm yeah i never really thought about this side of execution, i'll probably just go with a simple and easy implementation

haughty mountain
#

idk if they are so different in terms of hardness

fiery cosmos
#

which is the way it currently is until i learn things like python myscript.py arg1inp arg2out

haughty mountain
# 
import sys

if len(sys.argv) < 3:
  print('Too few arguments!')
  sys.exit(1)

input_file = sys.argv[1]
output_file = sys.argv[2]
#

that's all there is to it