algos-and-data-structs

[marsh flame]

print("The list: ", mylist)
NameError: name 'mylist' is not defined

[marsh flame]

# creates the list using the seed provided by the user
def getList():
        seed(theseed)
        mylist = []
        for i in range(1, 10):
            mylist.append(randint(1, 100))
        return mylist
# the bubble sort function
def bubbleSort(a_list):
        a_list = []
        n = len(a_list)
        for i in range(1, n):
                for j in range(1, n - i + 1):
                        if (list[j] < list[j - 1]):
                                list[j], list[j-1]  =  list[j-1], list[j]
                return list
# input: a list of integers
# output: a number of comparisons and swaps

# the main part of the program
theseed = input("What do you want to use as the seed? ")
# insert your main code below.
my_list = getList()
new_list = bubbleSort(my_list)
print("The list:", my_list)
print("After bubble sort:", new_list)```

its somewhat working now but instead of sorting itsays none

What do you want to use as the seed? 1
The list: [62, 62, 6, 88, 15, 56, 49, 38, 1]
After bubble sort: None

@brave owl

[brave owl]

You don’t need a seed for randint

[marsh flame]

you sure? thats what my professor had as the template

[brave owl]

There’s a way to make random numbers from a seed but that’s not it

[tranquil barn]

How do I do this

[shut breach]

this is a combinatorics problem, so it's not so much about an algorithms as it is just finding the right expression

think about how many choices you have to place the first object, then how many for the second, etc

[jolly mortar]

||https://en.wikipedia.org/wiki/Derangement|| if you can't figure it out

[raven kraken]

I also have one doubt while learning Time Complexity that suppose I have a array = [1,3,4,2,7]. If I traverse till end of this array than its time complexity will be O(N). And If I traverse only half of the array then its T.C should be O(N/2) and since in complexity analysis we ignore constants should it become O(N) again?

[winged plover]

Yeah

[raven kraken]

Then If I traverse through only 2 elements in an array of size 10 will it still be O(N)?

[flat sorrel]

If the number of elements traversed scales linearly with the total number of elements in the array then it's O(N)

Complexity is all about how it scales with some property of the input

[fervent saddle]

It’s like, if you were to graph it, then what kind of rate of increase would you see

A flat horizontal line is constant complexity, a flat diagonal line is linear complexity, a logarithmically increasing line is logarithmic complexity, etc

So that’s why constants don’t matter

[raven kraken]

Yeah I know all that but had this doubt like if we find the desired element at the first index itself then it is O(1) constant time but what if we have wanted a 2nd or 3rd element will it still be O(N)?

[vocal gorge]

k = 5
def f(lst):
    for el in lst[:k]:
        pass

This function is O(k) - which is O(1) if you consider k a constant. It doesn't depend on the list's size - if you keep k the same, it'll execute with the same speed for 10,100,1000,10000... elements in the list.

[turbid elk]

it there a way to keep track of word occurences

using tuplles?

I know been checking things out and since they are immutable ive transfer everything from a list into a tuple but i still cannot get word count

[fiery cosmos]

dictionaries?

words as key and occurrences as values.

[fervent saddle]

collections.Counter is the most convenient way

[keen hearth]

Yeah. collections.Counter is the way to go.

Building a table of word frequencies, given a list of words, is as simple as: ```py
from collections import Counter
frequencies = Counter(words)

For example...

!eval ```py
import re
from collections import Counter

text = """
And the Lord spake, saying, First shalt thou take out the Holy Pin.
Then shalt thou count to three, no more, no less. Three shall be
the number thou shalt count, and the number of the counting shall
be three. Four shalt thou not count, neither count thou two, excepting
that thou then proceed to three. Five is right out! Once the number
three, being the third number, be reached, then lobbest thou thy
Holy Hand Grenade of Antioch towards thy foe, who, being naughty
in my sight, shall snuff it.
"""

words = map(str.lower, re.findall(r"[a-zA-Z]+", text))
frequency = Counter(words)

print(f"{frequency['three'] = }")
print(f"{frequency['the'] = }")
print(f"{frequency['banana'] = }")

[halcyon plank]

@keen hearth :white_check_mark: Your eval job has completed with return code 0.

001 | frequency['three'] = 5
002 | frequency['the'] = 7
003 | frequency['banana'] = 0

[fiery cosmos]

wait, how did you print value?

print(f"{frequency['three'] = }") wtf?

!e

a=5
print(f'{a = }')
print(f'{a =: }')

wow

[halcyon plank]

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

001 | a = 5
002 | a = 5

[keen hearth]

Yeah, it's pretty neat. Added in 3.9, I think.

[fiery cosmos]

oh i see can you come in #ot2-never-nester’s-nightmare when free? i have some doubts.

[thorn sequoia]

hey guys i need some help
I have to rank lists of list, for example if I'm given [[1,4,2],[7,5,3]] I should return the output [[1,3,2],[3,2,1]]
This is what i have now;

    array = np.array(table)
    for row in array:
        for elem in row:
            array = np.array(array)
            x = rankdata(array)
            
    return x
    
input: rank([[2,4,6], [4,6,2], [6,2,4]])
output: array([2., 5., 8., 5., 8., 2., 8., 2., 5.])    

I am using rankdata function as it helps with the ties, but the problem is that my loop does not rank by each list in the list, rather the whole bigger list instead.
I've also tried np.array(row) which gives only a list of 2 elements for (though i dont understand how it works) while np.array(elem) returns a list with only one element. :(((

Can anyone tell me how to fix this? thank you :))

[feral hound]

def rank(table):
    sorted_table = [{item : i+1 for i, item in enumerate(sorted(row))} for row in table]
    return [[sorted_table[i][item] for item in row] for i, row in enumerate(table)]

print(rank([[2,4,6], [4,6,2], [6,2,4]]))

so my approach first sorts each row in the table preserving their order in the table

then for each sorted row it replaces it with a dict where the number is the item and its sorted position is the key

then I iterate over the table and return the items position from the sorted_table for that row

I used list and dict comprehensions since its a lot less code but if you find this confusing I can rewrite it using normal loops

[halcyon plank]

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

[[0, 1, 2], [1, 2, 0], [2, 0, 1]]

[feral hound]

!e

def rank(table):
    sorted_table = [{item : i+1 for i, item in enumerate(sorted(row))} for row in table]
    return [[sorted_table[i][item] for item in row] for i, row in enumerate(table)]

print(rank([[2,4,6], [4,6,2], [6,2,4]]))

[halcyon plank]

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

[[1, 2, 3], [2, 3, 1], [3, 1, 2]]

[feral hound]

!e

import numpy as np
from scipy.stats import rankdata
def rank(table):
    array = np.array(table)
    output = []
    for row in array:
        x = rankdata(row, method='min')
        output.append(list(x))
            
    return list(output)

print(rank([[2,4,6], [4,6,2], [6,2,4]]))

[halcyon plank]

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

[[1, 2, 3], [2, 3, 1], [3, 1, 2]]

[feral hound]

using your method

[feral hound]

you dont need to convert the table to numpy array btw

rankdata will do it automatically

[raven kraken]

Can we use collections.counter in any coding interview?

will they allow us to import stuff

[feral hound]

I think its highly dependent on the interview and the question

[winged plover]

!e ```py
def rank(table):
sorted_keys = [dict(zip(sorted(i),range(1,len(i)+1))) for i in table]
return [list(map((lambda x: sorted_keys[i][x]),j)) for i,j in enumerate(table)]
print(rank([[2,4,6], [4,6,2], [6,2,4]]))

[halcyon plank]

@winged plover :white_check_mark: Your eval job has completed with return code 0.

[[1, 2, 3], [2, 3, 1], [3, 1, 2]]

[winged plover]

@feral hound can i ask where did you learn all this algos and stuff from 😅

[feral hound]

I just do a few problems every now and then

[winged plover]

ah so mostly by yourself?

[feral hound]

and tbh I'm not that good at this still struggle a lot with the harder problems

[feral hound]

yup

[winged plover]

i mean from what ive seen here.. you are quite good at the stuff that gets asked here 👀

[feral hound]

I took cs50 when I was starting out as well which goes over some stuff as well so it really helps

[winged plover]

ahh

[feral hound]

I answer what I feel like I can 🙂

theres been quite a few times where I didnt know how to solve something

I remember someone asked about finding a duplicate a few days ago I know the way to do it is floyds turtoise and hare just dont fully understand why that works for example

[winged plover]

ah okay well makes sense
i meant like any source where you get questions or stuff from

[raven kraken]

@feral hound Are you in college?

[winged plover]

ohh whats that

[feral hound]

I like codewars but tbh I found helping people on here is much better

for some reason I can easily think up a solution when someone asks here but not when I'm doing it on my own lol

[feral hound]

graduated uni this year

[winged plover]

haha guess the helper effect lol

[winged plover]

ah okayy will check that out

[raven kraken]

Great

[feral hound]

nice thing about helping here is that someone else often comes and posts a much better solution every now and then and I end up learning something new

[winged plover]

also what was that tortoise thing you stated.. like could u link the problem or soln?

would be grateful

😅 .

[feral hound]

https://leetcode.com/problems/find-the-duplicate-number/

https://www.youtube.com/watch?v=pKO9UjSeLew

this is a fun little video giving a very brief explanation of the solution

[raven kraken]

This could be done with cyclic sort

In place sorting, so Time complexity will be O(N) and no additional space will be required so space complexity will be O(1).

[winged plover]

ohh i guess ill watch it after i try it myself lol

[winged plover]

.bm tortoise hare

[feral hound]

havent heard of this sort before but unfortunately wont work this time

[raven kraken]

https://youtu.be/JfinxytTYFQ?t=3092

[raven kraken]

Just watch this video , I can guarantee you will love it. Literally the best video out there

[winged plover]

what do they mean by constant extra space?

[vocal gorge]

not scaling with n

[feral hound]

as in the extra space you use is the same no matter what size your input is

[winged plover]

ah ohkay

so basically i cannot use stuff like sorted(inp)

that makes it better

[raven kraken]

51:32 at this time stamp duplicate number question has been discussed in this Video

[feral hound]

yeah the constraints are pretty much just there to lead you to the tortoise and hare solution lol

you can also check the solutions tab after you give it a try to see a whole list of solutions and why they work/dont work

[vocal gorge]

https://emre.me/coding-patterns/cyclic-sort/ this has a solution using cyclic sort without having to watch a video.

[feral hound]

btw leetcode will let you submit an answer that doesnt adhere to the constraints and accept it if the output is correct

I initially submitted a solution with a dict which was accepted but it doesnt adhere to the constraints so look out for that when you solve it

[hidden fiber]

how much graph theory is enough to start graph algos?

[feral hound]

no idea tbh but I think if you know DFS and BFS you should be able to solve most problems

[tropic glacier]

You basically need to know what a graph is, I don't think most graph algorithms require actually knowing advanced graph theory.

[hidden fiber]

I haven't attended even the elementary graph classes so will that be okay?

[vocal gorge]

RE finding the missing number: tbh, my favorite, and probably fastest, solution to that task is by knowing that ||the sum of 1+...+n is n*(n+1)/2||

[feral hound]

ok yeah thats quite simple but issue with this is its not constant extra space so its not the solution we're looking for

[vocal gorge]

it is, though

[feral hound]

its n extra space no?

[vocal gorge]

I don't see where it uses extra space in the snippet provided.

[feral hound]

you cant modify the original array

so you have to make a new one

[vocal gorge]

oooh, now that's correct

[hidden fiber]

O(1) ...

[vocal gorge]

yeah, that solution violates the task

[tropic glacier]

That's exactly what I used, I'm pretty sure it's the only linear time, constant space method

[feral hound]

they put a lot of constraints specifically so that you use floyds tortoise and hare lol

[vocal gorge]

One nice fact about this method is that it scales.

You can use it to find two missing numbers from 1 to n.

[feral hound]

issue with this aswell is that there can be multiple duplicates not just one

[vocal gorge]

you'd need to calculate two moments of the array (sum and sum of squares), then solve a linear system to find the two numbers.

And so on - for k missing numbers, calculate k moments of the array and solve a system.

[feral hound]

I mean that the number can be repeated more than once btw

[tropic glacier]

Ah, we might be talking about different problems, a few days ago someone was asking about consecutive numbers with one duplicate.

[feral hound]

nah I think its the same one

https://leetcode.com/problems/find-the-duplicate-number/

[tropic glacier]

So it scales as k^2 then, since you have to solve the system

[vocal gorge]

hmm

[raven kraken]

I think missing number question can also be solved with Cyclic Sort

[feral hound]

it can but for this particular problem cyclic sort violates the constraints

[vocal gorge]

yeah, that ruins this one I think - more than one duplicate is concerning

[raven kraken]

I didn't knew that

[vocal gorge]

I learned the moments trick from what's apparently a google inteview question - you have numbers from 1 to n, k of them are missing, find them in linear time and constant space. Something like that

[feral hound]

could you link to a resource with more info on it?

[vocal gorge]

let's see if I can find it...

[vocal gorge]

ah, there it is:
https://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe

[feral hound]

thx 🙂

[hidden fiber]

are you doing it from kunal's vid?

[shut breach]

.bm

[feral hound]

forgot to ask about this but how would you do this btw?

[vocal gorge]

like in the question - sum of numbers, sum of squares, and then calculating them as:

K1 is the sum deficiency, K2 is the sum-of-squares deficiency
a + b = K1
a**2 + b**2 = K2

hence, a,b = 1/2(K1 +- sqrt(2K2-K1^2))

[feral hound]

no i mean before you were talking about this

[vocal gorge]

not sure what you mean

[feral hound]

so the method you used to find a single missing number

you said that also works for k missing numbers

[feral hound]

I assumed you meant something other than this since you hadnt mentioned it at that time

[vocal gorge]

I meant the moments method by that:

[feral hound]

ahh fair

btw idk if my brain isnt working rn or what but how would this work for finding duplicates?

I get how it works for missing numbers

[vocal gorge]

I don't think it will

well, it's not obvious to me how to make it work at least

[feral hound]

ok thats reassuring I felt like I was missing something for a while when I was doing the maths lol

[feral hound]

just to clarify you mean for the case of k=1 as well right?

[vocal gorge]

yeah

if there's one number t that is duplicated b times, replacing a few numbers in the 1..n list, then, uhh

the sum will be S_n + t*(b-1) - x_1 - ... - x_{b-1}, where the x are numbers that are missing due to t being duplicated.

which can be anything depending on what the xes are, I think

so it doesn't really tell much

[feral hound]

btw lets also assume b=1 for this

so [1, 2, 3, 4, 4] as an example

[vocal gorge]

for b=2 (two occurences instead of 1), the sum will be S_n + t - x, so you know t - x.

actually, hmm

what if we also calculate the sum of squares... then:

we know also t**2 - x**2, from which we can get t and x.

[feral hound]

issue is there are multiple combinations of missing number and duplicate that make up the difference in the sums

thats why I dont see how it works

[vocal gorge]

So if you know there'll be exactly one duplicate (once) and so one missing one, it's solvable

but if you don't know how many times it's duplicated, don't think so.

[feral hound]

so how would you do [1, 2, 3, 4, 4] in this case?

[vocal gorge]

knowing there's one number appearing twice?
The sum is one lower than it should be for 1+...+5, so t-x is -1.
The sum of squares is 46 instead of 55, so t**2 - x**2 is -9

hence,

t = x - 1
t^2 - x^2 = x^2 - 2x + 1 - x^2 = -2x + 1 = -9 => x = 5
t = x-1 = 4

so 5 is missing and 4 is duplicated

[feral hound]

where did
t = x - 1 come from?

wait nvm is -1 the differnce?

[vocal gorge]

t-x = -1 => t = x-1

[feral hound]

btw I found another way to do it which is also easier

sum of list - sum of range to n-1 instead of n gives the answer

[vocal gorge]

huh?

[feral hound]

!e

nums = [1, 2, 3, 4, 4]
sum1 = sum(nums)
sum2 = ((len(nums)-1) * len(nums)) // 2
print(sum1 - sum2)

[halcyon plank]

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

4

[vocal gorge]

ah, nice

[feral hound]

nah it isnt I just realised this only worked because of that example...

sry for confusing you like that my brain really aint working today

[limpid cove]

hello

[gritty marsh]

Interesting video: https://www.youtube.com/watch?v=cCKOl5li6YM

[turbid elk]

hey guys is there a way to make a small list of Tuples with a word and some random count. Then try to find that tuple and change its count or rearrange the indexes

[thorn sequoia]

so my task is actually to rank list of list in descending order and i have corrected my codes;

def rank(table):
    array = np.array(table)
    output = []
    for row in array:
        x = rankdata([-1 * i for i in row])
        output.append(list(x))
            
    return list(output)```
but i got this error while testing using `rank([[1,2,1],[4,2,5,3]])` ;
```VisibleDeprecationWarning: Creating an ndarray from ragged nested sequences (which is a list-or-tuple of lists-or-tuples-or ndarrays with different lengths or shapes) is deprecated. If you meant to do this, you must specify 'dtype=object' when creating the ndarray.``` but the output was still correct

[knotty magnet]

it's not an error, it's telling you it might break in a future version of numpy

[feral hound]

you dont need this line btw

array = np.array(table)

just remember to change the array in the for loop to table after removing that line

also looking at this input [[1,2,1],[4,2,5,3]]

I didnt know you could have duplicates what would you want the output to be?

!e

from scipy.stats import rankdata
def rank(table):
    output = []
    for row in table:
        x = rankdata(row, method='min')
        output.append(list(x))
            
    return list(output)

print(rank([[1,2,1],[4,2,5,3]]))

[halcyon plank]

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

[[1, 3, 1], [3, 1, 4, 2]]

[feral hound]

@thorn sequoia

the reason it gave you that warning btw is because the nested lists have different lengths

[thorn sequoia]

ohh okay

thank you so much guys!! ^__^

[feral hound]

!e

from scipy.stats import rankdata
def rank(table):
    output = []
    for row in table:
        x = rankdata([-1 * i for i in row])
        output.append(list(x))
            
    return list(output)

print(rank([[1,2,1],[4,2,5,3]]))

[halcyon plank]

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

[[2.5, 1.0, 2.5], [2.0, 4.0, 1.0, 3.0]]

[feral hound]

is this the output you want btw?

[thorn sequoia]

yup it is :))

[idle pier]

Hello folks, am currently working on my sliding window algorithm skills, I have this code

def max_sum_subarray(arr, k):
    max_sum = float('-inf')
    start = 0
    curr_sum = 0
    for end, val in enumerate(arr):
        curr_sum += val
        if end - start + 1 == k:
            max_sum = max(max_sum, curr_sum)
            curr_sum -= arr[start]
            start += 1
    return max_sum

arr = [2,3,4,1,5]
k = 3

print("expected", 10)
print("actual", max_sum_subarray(arr,k))```
Am having trouble understanding `if end - start + 1 == k:`

[feral hound]

they do that to move the window along

and to make it clearer the order of operations its really like this

if (end - start) + 1 == k:

the idea is that as the loop iterates initially end will be 0 and go up by one every time

so in the beginning (end - start) + 1 = (0 - 0) + 1 = 1

which is the size of the window

when end = 1

(end - start) + 1 = (1 - 0) + 1 = 2

this will keep going until eventually (end - start) + 1 = k

start will still be 0 at this point

but once the if statement evaluates to true you do some stuff and then increment start by 1

which keeps the window at a constant size of k for every iteration after this

@idle pier does that explain it?

[idle pier]

I think so, both end and start start at 0 ,0. which is 0 + 0 +1 = 1. So basically the window will keep on growing until it reaches k length.
Once its k length, the window starts to slide(if this makes sense)

[feral hound]

yup thats correct

[mild dove]

maybe, end and start could be curr_index and start_index to be easier to understand idk

[winged plover]

@feral hound sorry to randomly ping you.. could u share the solution to that tortoise hare problem?
i mean i got it that it uses tortoise hare thing...
but what tortoise hare is still doesnt make much sense to me

[feral hound]

its just 2 pointers starting from the beginning of the list and going to the index pointed at the by the value they are at

the turtoise moves 1 step at a time

the hare moves 2 steps at a time

[winged plover]

ah ohkay that way

[feral hound]

keep going unitl they meet

when they meet set one of them to the start

and the other to the meeting point

and make them both go 1 step at a time

the next point they meet is where you looped

which means its the duplicate

[winged plover]

wait hare doesnt really move two steps at a time right?
it moves basically current_val - current_indx steps right?

[feral hound]

watch the video I sent for a deeper explanation

[winged plover]

ah wait shiet

[feral hound]

no its 2 steps at a time

[winged plover]

i think that would explain it

or prolly not

[feral hound]

tbh I know how the algo works but I still dont understand exactly why it works

the longer video does go over the why with some proofs but I wasnt really bothered

[winged plover]

huh okay that is some part i dont even tend to understand

[feral hound]

and I plan to brush up a bit more on my maths then going back to it later

[feral hound]

let me see if I can show you

[winged plover]

hmm so if i get it right if i has a list like [3, 2, 1 , 4, 1]
first my tortoise and hare will go to index 3
then hare moves two steps to index 0
and tortoise to 4
then hare 2 tortoise 0
... till they meet first time?

[winged plover]

alright that cycle makes sense

[feral hound]

ngl tho now that I'm looking at it I dont see how this works if a number is the same as its indedx

you will just be stuck in an infinite loop

[winged plover]

similar lol

wait if thats the case

you already found ur dupe

its the number itself

[feral hound]

nah lets say my array is

[0, 2, 2, 3, 4]

dupe is 2 but its gona be stuck at 0

[winged plover]

alright yeah fuck that thing also exists

[feral hound]

I think if we make a condition to say if number is same as index ignore it and move on it might still work

[winged plover]

my best bet is hardcode a condition for 0 to not be 0 if it is 1 is not 1 and so on

[feral hound]

since that number is isolated anyway

[winged plover]

now i wonder what if my array way

[0,1,2,3,2]

oh wait nvm

it works in this condition too

[feral hound]

im sure there is some kind of rule for how to deal with this but idk the algo well enough to say

I think ignoring numbers where the index is the same as the number might work but not sure gota test that out

[lean junco]

Sieve of Eratosthenes

i know how basic implemention work

but how does that i**2 optimised Sieve of Eratosthenes implementation work

[keen hearth]

I'm not sure what implementation you're referring to @lean junco

[keen hearth]

Oh right. I think that's actually just the standard algorithm. Would you like to try implementing this in Python?

[lean junco]

not the standard seive

standard seive in has two for loop ....one i = 2 to n then other j = (2+i, n, i) to make non prime false in a bool array of all true

this has been optimised to check till root n then do false for root n to n

i dont get how this i^2 term makes sense ......

[feral hound]

its getting rid of all multiples of i in the array A

[spice orbit]

Just wondering, using libfreenect2 rn, I need a uint16 image for open3d, but pylibfreenect2 returns float, how do I do this conversion?

[feral hound]

ngl tho this is one of the most confusing looking examples I've seen for the sieve took me a while to understand what was going on

@lean junco

[lean junco]

i get that if you wanna check from 0 to 10
you will start at 2
put all its multiple(4, 6, 8 ,10) as false
then go to 3
put all its multiple (6,9) as false
then 4
put 8 as false
then 5
put 10 to false
.....till 10
then calculate number of trues
that will be at 2 3 5 7

[feral hound]

yeah ngl I dont see how this implementation even works it misses a few numbers

9 being the first number which it misses

oh wait nvm it gets 9

[lean junco]

in above picture it has been optimised to first check from i to root n then put false only for factors of i which are in isquare to n

[fiery cosmos]

I think the i^2 is an optimization. It could start at 2*i

[keen hearth]

Well it starts at i**2, because if you think about it, it has already dealt with all the composites less than that.

[tropic glacier]

For every new prime i encountered in the list, i*i is the next multiple of i that hasn't already been crossed out.

[lean junco]

it is indeeed optimisation no doubt.....but how it makes it work

[keen hearth]

If n = i * j where j < i, then n will have already been declared not prime.

[feral hound]

yeah just realised that but now i need to see a proof for how its not missing any numbers

[lean junco]

2*i is the next**

[fiery cosmos]

but 2*i will have been crossed out by the 2

[tropic glacier]

No, because previous iterations of the loop have crossed out the lower ones. It is important to run the loop in order.

[feral hound]

can you show a proof for this because I can see that from doing it manually but dont see an intuitive reason to work out a formal proof

[keen hearth]

Any composite multiple of i less than i**2 is a multiple of a another number smaller than i.

[feral hound]

0k this answers it for me

[fiery cosmos]

and I guess 3*i will have been crossed out by the 3 loop, same for 4, 5, 6, etc up to i-1

[feral hound]

2i croosed out by 2

[lean junco]

if you could prove it i will be clear of all my doubt...you seem to get my problem

[tropic glacier]

LX just proved it

[feral hound]

3i crossed out by 3

4i crossed out by 2
5i crossed out by 5 and so on until i*i

[lean junco]

is it a theorem or something

i see

[tropic glacier]

Just think about it for a bit

[lean junco]

if its a statement then i am fine with this algo

[feral hound]

have a look at what I wrote for some intuition into it

[lean junco]

yeah it makes sense

thank you guys...

sieve was smart

[feral hound]

thanks from me as well didnt know about this optimisation 🙂

[lean junco]

😂 welcome and thx again

[tropic glacier]

Sieve isn't some guy's name, lol

[lean junco]

Eratosthenes*

[keen hearth]

Professor Sieve

[lean junco]

Eratosthenes**

[tropic glacier]

Those Greeks knew a lot of maffs

[lean junco]

indeed

[keen hearth]

2 + 2 is 4 minus 1 that's 3 quick mafs.

[keen hearth]

No worries!

[feral hound]

btw one note I never understood why sieve is used when it takes N space if we can make an algo that takes K space

K being number of primes

and it will also have the same time complexity

[tropic glacier]

Because a sieve takes N space even though it has K holes in it

[keen hearth]

🤔

What is this algorithm?

[feral hound]

import math
primeNums = []
maxNum = 3

f = open("primeNums.txt", "r")
temp = f.readlines()
for line in temp:
    primeNums.append(int(line))
f.close()

maxNum = primeNums[-1]

num = int(input("enter any number to be checked:\n"))

def PrimeCheck(number):
    for prime in primeNums:
        if number % prime == 0:
            return False
        elif prime >= math.sqrt(number):
            return True
    return True

if num > maxNum:
    for i in range(maxNum, num +1):
        if PrimeCheck(i):
            primeNums.append(i)
            f = open("primeNums.txt","a")
            f.write(str(i) + "\n")
            f.close()

for prime in primeNums:
    if prime < num:
        if num % prime == 0:
            print(str(prime) + " is a prime factor of " + str(num))
    else:
        break
    ```

[keen hearth]

There is a variation of the algorithm called the "segmented sieve", which is designed to be cache-friendly, and is also O(sqrt(n)) in space-complexity.

[feral hound]

this is something I wrote a while back before knowing about the sieve dnt know if the algo has a name but it does the same thing just in slightly different order

[tropic glacier]

ew, executing math.sqrt repeatedly in a loop

[feral hound]

instead of crossing out all the number from i*i to n it stores the primes and checks the numbers as it goes along

[feral hound]

its been a while since I wrote this lol

[keen hearth]

Oh, it checks each new number against the previous primes?

[tropic glacier]

There's no need to use math.sqrt at all, although I guess it's not a big deal if you only used it once 🙂

[feral hound]

altlough actually thinking about this now this does do a lot more checks so maybe it isnt as fast

[feral hound]

yup

[keen hearth]

That's not actually the Sieve of Eratosthenes unfortunately.

[feral hound]

yeah its not its different algo

[tropic glacier]

Is the time complexity different?

Since it's now (number of primes) squared

[keen hearth]

Yeah, unfortunately it's worse I think.

[feral hound]

yeah it is worse

[keen hearth]

https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

[feral hound]

I just realised after posting it lol

its O(NK) instead of O(N)

K being the number of primes

[tropic glacier]

Interesting that the premature optimization of wanting to save space results in such a dramatic difference in time performance

[feral hound]

this is what happens because I trusted past me that its O(N) instead of double checking again now lol

[tropic glacier]

I probably would have done the same thing. "A ha! I don't need to store a list of all the numbers!"

Because if I were doing this on paper, I wouldn't want to start by writing down all the numbers up to N

[feral hound]

pretty much although I actually didnt even know sieve existed back then

[tropic glacier]

Although in general I think we're lucky if we can come up with a way to save time by using more space. Time is valuable, RAM is cheap.

[feral hound]

although I am thinking of a alternative that takes O(1) space now I'll come back when I write something up will prob take a few days lol

[feral hound]

true

I can also think of a straightforward way of doing sieve segmented which would be O(K) space

[feral hound]

not sure if what I'm thinking is the same as this though

[keen hearth]

Have a look on Wikipedia: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Segmented_sieve

The really important thing though about that variant is cache-locality.

Which is crucial for performance.

[feral hound]

hasnt anyone tried doing this on gpu?

[tropic glacier]

I think it's difficult to parallelize prime-finding

[feral hound]

segmented sieve allows us to send batches in which would work and we're doing very simple and repetitive operations

[tropic glacier]

But they each depend on the previous one

[feral hound]

hmm yeah the primes themselves are the issue

I dont get how the segmented sieve has a space complexity of O(sqrt(n)) though

[tropic glacier]

One thing a GPU would be good for, I assume, are the large multiplication operations, once you get into truly large numbers

[feral hound]

I read wikipedia and it seems to be the same as what I'm thinking unless I misunderstood something that should be O(K)

[tropic glacier]

Yeah, it would have to store the previous primes as well

So it's like O(K + sqrt(N))

[feral hound]

but why sqrt(N)

[tropic glacier]

But for large N, sqrt(N) dominates

[feral hound]

where is that coming from

[tropic glacier]

Because they're choosing sqrt(N) as the segment length

[feral hound]

why would they do that?

they can just choose a constant value for the segment size

[tropic glacier]

I think the point is it could adversely affect the time complexity, but with sqrt(N) it doesn't

[feral hound]

you only need to find the primes under sqrt(N) but doesnt mean the segment has to be that size as well

[tropic glacier]

true, I think they suggest something else if sqrt(N) is still too large for memory

[feral hound]

so the algo is really O(K)

[tropic glacier]

But sqrt(N) is larger than K

Primes grow something like log(log(N))

[feral hound]

yeah but I mean the segment doesnt have to be size sqrt(N)

it can be size 10000 for example

and then its just O(K + 10000) = O(K)

[tropic glacier]

Not quite

[lean junco]

can we optimise this further

its giving TLE

[tropic glacier]

How many times do you have to re-initialize the array of 10000 booleans?

[feral hound]

that doesnt change its space complexity

since I only store that constant size range I free the memory of the old ranges when I need a new one or I just update the current one inplace

[tropic glacier]

I think any fixed-size array will lead to the same time complexity as your algorithm, where you end up just having to check every number against all previously-found primes.

[feral hound]

hmm I will write up a solution it will probably be apparent as I'm doing it

[tropic glacier]

Your algorithm is of course the case where the array has 1 boolean 🙂

[feral hound]

thats what I thought in the past but I think differently now

I think my algo cant be called a sieve variation

[tropic glacier]

I mean, reducing the array size to 1 is effectively removing the sieve

[lean junco]

..

[feral hound]

yeah your solution seems fine for sieve

I wrote mine like this though

!e

def sieve(N):
    primes = []
    window = [True] * N
    for i in range(2, N):
        if window[i]:
            primes.append(i)
            for j in range(i*i, N, i):
                window[j] = False
        
    print(primes)
sieve(100)

[halcyon plank]

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

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

[feral hound]

I think this is a bit more readable but in terms of time/space complexity its pretty much the same ignoring that I store the primes in your case just count up the total instead of storing the primes and its the same

[feral hound]

!e

import math

def sieve(N):
    primes = []
    window = [True] * N
    for i in range(2, N):
        if window[i]:
            primes.append(i)
            for j in range(i*i, N, i):
                window[j] = False
        
    return primes
def segmented_sieve(N, window_size):
    primes = []
    last_stop = []
    window = [True] * window_size
    for i in range(2, window_size):
        if window[i]:
            square = i**2
            for j in range(square, window_size, i):
                window[j] = False
            primes.append(i)
            if square >= window_size:
                last_stop.append(square)
            else:
                last_stop.append(j + i)


    def seg(N, primes, last_stop,  iteration, window_size):
        window = [True] * window_size
        while window_size * iteration < N:
            for i, (prime, stop) in enumerate(zip(primes, last_stop)):
                for j in range(stop, (iteration + 1) * window_size, prime):
                    window[j % window_size] = False

                if last_stop[i] < (iteration + 1) * window_size:
                    last_stop[i] = j + prime

            for i in range(window_size * iteration, (iteration + 1) * window_size):
                if window[i % window_size]:     
                    square = i**2
                    for j in range(square, (iteration + 1) * window_size, i):
                        window[j % window_size] = False

                    primes.append(i)
                    if square >= (iteration + 1) * window_size:
                        last_stop.append(square)
                    else:
                        last_stop.append(j + i)
            window = [True] * window_size
            iteration += 1
        return primes
                
    return seg(N, primes, last_stop, 1, window_size)

out1 = sieve(300000)
out2 = segmented_sieve(300000, 100000)

for i, j in zip(out1, out2):
    if i != j:
        print(i, j)

[halcyon plank]

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

[No output]

[feral hound]

@tropic glacier @keen hearth

this is what I meant by segmented sieve

the window size is constant so its O(K) space

although Its running a lot slower than the normal sieve when the window is small compared to N not sure why tbh (relationship doesnt seem to be linear)

[tropic glacier]

Because it degenerates into your other algorithm, or one very similar to it

[feral hound]

could you guys help me check in case I missed something that changes the time complexity without realising?

[tropic glacier]

I don't think I can effectively evaluate such a long code fragment this late at night 😛

[feral hound]

fair I'm pretty tired myself so struggling as well lol

will add some comments to this hopefully we can have a more in depth look at this later

[fiery cosmos]

guys

what is wrong here

[feral hound]

the message is too long when I add the comments...

[feral hound]

do you get an error?

[fiery cosmos]

i need to figure out

why this is wrong

[tropic glacier]

Maybe it could use a return

[fiery cosmos]

it passed

thank sir

[feral hound]

https://paste.pythondiscord.com/qobibexita

[stone ruin]

!e

[halcyon plank]

Command Help

!eval [code]
Can also use: e

*Run Python code and get the results.

This command supports multiple lines of code, including code wrapped inside a formatted code
block. Code can be re-evaluated by editing the original message within 10 seconds and
clicking the reaction that subsequently appears.

We've done our best to make this sandboxed, but do let us know if you manage to find an
issue with it!*

[fiery cosmos]

can someone help me on this??

[feral hound]

I think I found the issue with the current code I have

in each iteration for the next window I end up checking for all the primes I currently have even the ones that arent in the current window

although those primes end up doing nothing

dont think it should make this big of a difference in running time so I think there might still be something else wrong

[feral hound]

https://paste.pythondiscord.com/ganowoxaje.py

I fixed that issue and it seems to scale linearly now

although for some reason my fix introduced another bug where it doesnt work for all window sizes so far it seems to be working for 5 but nothing else I tested

the code is too ugly and im too tired to fix it rn but if someone finds the issue feel free to let me know

found a few other numbers it works for (3, 4, 5, 6, 8, 12) theres prob more but yeah somethings broken somewhere

its 10 times slower than the normal sieve but thats a constant 10 regardless of N so we good

nvm I found the error

https://paste.pythondiscord.com/qivisafini.py

^^ finally have a working version of segmented sieve with O(K) space O(N) time now

[lean junco]

But i am geeting a tle

Time limit exceeded

[lean junco]

For this

[lean junco]

this is fastest algo for calculating primes

even faster then optimised seive of e.......

[tropic glacier]

Counting the primes less than N is different from listing them

[lean junco]

We arent listing here are we?

[tropic glacier]

You aren't. But the sieve methods produce a list.

[lean junco]

Yeah but my main question was indeed counting lol

I just used seive beacause i thought it is fast....but it isnt even close to what this above algos performance

[quiet jay]

#help-corn

[feral hound]

@tropic glacier @keen hearth https://paste.pythondiscord.com/igomuqebok made it a bit more readable now that I've had some rest lol

red is sieve blue is seg sieve

also sorry for bothering you guys if your not interested

[hard trail]

Hello!

I'm trying to solve an algorithm question, in a different language than Python, but I can't seem to figure out how.

So I'm trying to create this grid:

1-2-2
2-2-1

1-2-2
2-2-1

Every: 1,6,7,12,13 item is added a '1'.

I used modulos, but been able to acheive only:
1-2-2
1-2-2

how can I solve this?

[feral hound]

!e

for i in range(3):
    print("1-2-2")
    print("2-2-1")
    print()

[halcyon plank]

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

001 | 1-2-2
002 | 2-2-1
003 | 
004 | 1-2-2
005 | 2-2-1
006 | 
007 | 1-2-2
008 | 2-2-1

[feral hound]

doesnt that work?

[hard trail]

😮 What is that lol

How would you use that for a game, not just print

e.g.

 @if($count == 0 || $count == 5 || $count == 6 || $count == 11 || $count == 12 || $count == 17
)
                        <?php 
                            $class = 'md:w-1/2'
                        ?>
                        @else
                        <?php
                            $class = 'md:w-1/4'
                        ?>
                        @endif

this is PHP, but the algorithmic question is rather the same I believe

How would you autoamte that if statement?

[winged plover]

well define automating the if statement

like do you want to check value of count against different set of numbers for different cases?

[hard trail]

I want to automate the statements inside

I have a counter on the loop

each literation the count++

[hard trail]

The full code:

<?php 
                    $class = null;
                    $count = 0; 
                ?>

                <div class="flex flex-wrap -mx-10 mt-50">
                @while( $query->have_posts() ) @php( $query->the_post() )
            
                    @if($count == 0 || $count == 5 || $count == 6 || $count == 11 || $count == 12 || $count == 17)
                        <?php $class = 'md:w-1/2' ?>
                    @else
                        <?php $class = 'sm:w-1/2 md:w-1/4' ?>
                    @endif


                    <x-blogExcerpt 
                        class="w-full mt-50 px-10 {{ $class }}" 
                        title="{{ get_the_title() }}" 
                        permalink="{{ get_the_permalink() }}" 
                        category="{!! get_the_category_list(',‎‎ ‎‎', get_the_ID()) !!}" 
                        rawThumbnail="{!! get_the_post_thumbnail() !!}" 
                        publishDate="" 
                        type="" 
                    /> 

                    <?php $count < 17 ? $count++ : $count = 0; ?>

                    @endwhile


                </div>

And I'm not sure how to automate the statement inside he if statement, to be going like this forever

with that pattern

I tried modulos etc... failed

[winged plover]

sorry mate i dont actually understand php 😅

[hard trail]

But

it has nothing to do with php

This is just a programming language, nothing to do with php

if you were to do this in Python, what algorithm would you write for that statement xd

if statements are the same across all languages right

[winged plover]

could you give an example of what you mean..
a daily life example would work (non php)

[hard trail]

Too sad I don't know Python xd I did some JS before though xd

In Python, if you wanted to create a board, such as

1-2-2
1-2-2
1-2-2

You would write modulos such as `if($counter % 3 == 0) ? '1' : '2' right? Hopefully xd

[winged plover]

yeah i guess i would yeah lol

[hard trail]

So if you now wnated to create a grid like

1-2-2
2-2-1

1-2-2
2-2-1

and repeat, what would you write? xd

[winged plover]

!e ```py
counter = 0
out = ""
while counter < 12:
if counter % 6 == 0:
out += "\n\n"
elif counter % 3 == 0:
out += "\n"
else:
out += "-"
if counter == 0 or counter == 5 or counter == 6 or counter == 11:
out += "1"
else:
out += "2"
counter += 1
print(out[2:])

[halcyon plank]

@winged plover :white_check_mark: Your eval job has completed with return code 0.

001 | 1-2-2
002 | 2-2-1
003 | 
004 | 1-2-2
005 | 2-2-1

[winged plover]

@hard trail i tried the least to use pythonic structures and functions and came up with something like this

[hard trail]

The if statement with 5 or 6 or 11 - what if we are at count number 5499? xd would that still work xd

I wonder how much that translates into say JavaScript, I'll try to decode what you wrote there xD

This feels almot like a video game xD

Talking to anothe rfellow human being, that does different programming langauge

[winged plover]

ah ohkay so you want in such a way alright cool lemme just do that

!e ```py
counter = 0
out = ""
while counter < 39:
if counter % 6 == 0:
out += "\n\n"
elif counter % 3 == 0:
out += "\n"
else:
out += "-"
if counter % 6 == 0 or counter % 6 == 5:
out += "1"
else:
out += "2"
counter += 1
print(out[2:])

[halcyon plank]

@winged plover :white_check_mark: Your eval job has completed with return code 0.

001 | 1-2-2
002 | 2-2-1
003 | 
004 | 1-2-2
005 | 2-2-1
006 | 
007 | 1-2-2
008 | 2-2-1
009 | 
010 | 1-2-2
011 | 2-2-1
... (truncated - too many lines)

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

[winged plover]

@hard trail guess it now works for 5499 too

[hard trail]

What are you doing here?

if counter % 6 == 0:
        out += "\n\n"

Oh

You added -

Ohhh

I know what you did lol

how do you use the pythong bot? xD

print_f('hello')

return print('hi')

[winged plover]

basically got the row to change and get an empty row in middle too

!e

[halcyon plank]

Command Help

!eval [code]
Can also use: e

*Run Python code and get the results.

This command supports multiple lines of code, including code wrapped inside a formatted code
block. Code can be re-evaluated by editing the original message within 10 seconds and
clicking the reaction that subsequently appears.

We've done our best to make this sandboxed, but do let us know if you manage to find an
issue with it!*

[hard trail]

!eval
print('hello')

!e

counter = 0
out = ""
while counter < 39:
        out += "-"
    if counter % 6 == 0 or counter % 6 == 5:
        out += "1"
    else:
        out += "2"
    counter += 1
print(out[2:])

[halcyon plank]

@hard trail :x: Your eval job has completed with return code 1.

001 |   File "<string>", line 5
002 |     if counter % 6 == 0 or counter % 6 == 5:
003 |                                             ^
004 | IndentationError: unindent does not match any outer indentation level

[hard trail]

!e

counter = 0
out = ""
while counter < 39:
    if counter % 6 == 0 or counter % 6 == 5:
        out += "1"
    else:
        out += "2"
    counter += 1
print(out[2:])

[halcyon plank]

@hard trail :white_check_mark: Your eval job has completed with return code 0.

2221122221122221122221122221122221122

[hard trail]

Hmmmm, I think I deleted something I shoulnd't have xD

I'm jut trying to remove the extra - and spaces xD

[hard trail]

And thank you btw 😄

I tried soemthing similar, but my modulos were wrong, I suppose the one I missed was maybe the 6 == 5

[winged plover]

ah lol np

[hard trail]

!e

counter = 0
out = ""
while counter < 39:
   
    if counter % 6 == 0 or counter % 6 == 5:
        out += "1"
    else:
        out += "2"
    counter += 1
print(out[2:])

[halcyon plank]

@hard trail :white_check_mark: Your eval job has completed with return code 0.

2221122221122221122221122221122221122

[hard trail]

But why doesn't this has 1 in front?

I don't understand xd

There's nothing in this code

 if counter % 6 == 0:
        out += "\n\n"
    elif counter % 3 == 0:
        out += "\n"
    else:
        out += "-"

That would output 1 or is there xd

[winged plover]

oh wait its because of out[2:]

do print(out)

and you are good to go lol

[winged plover]

!e ```py
counter = 0
out = ""
while counter < 39:

if counter % 6 == 0 or counter % 6 == 5:
    out += "1"
else:
    out += "2"
counter += 1

print(out)

[halcyon plank]

@winged plover :white_check_mark: Your eval job has completed with return code 0.

122221122221122221122221122221122221122

[hard trail]

What does out[2] do? 😄 I'm going to try this solution in PHP now xD

[winged plover]

oh well wait ill show what it does

!e ```py
counter = 0
out = ""
while counter < 12:
if counter % 6 == 0:
out += "\n\n"
elif counter % 3 == 0:
out += "\n"
else:
out += "-"
if counter == 0 or counter == 5 or counter == 6 or counter == 11:
out += "1"
else:
out += "2"
counter += 1
print(out)

[halcyon plank]

@winged plover :white_check_mark: Your eval job has completed with return code 0.

001 | 
002 | 
003 | 1-2-2
004 | 2-2-1
005 | 
006 | 1-2-2
007 | 2-2-1

[winged plover]

@hard trail without [2:] this is what it was lol

[hard trail]

WOW this solution you wrote works. I'm still somewhat ish new to programming, why did you do this

 counter % 6 == 5:

Do you know in how many servers I asked this

they told me its not possible

I knew it was possible

So I decided to try in a smart algorithmic python hannel

and 15minutes you solved that, I've spend countless cours on this lol

crazy

they said to do some complicated stuff

or not possible

or whatever

crazy

[hard trail]

oh, so that's specific to the discord bot, it adds lines, nothing to do with python

[winged plover]

basically to check the position in small blocks ```
0 1 2
3 4 5

so what u wanted was "1" at position 0 and 5

[winged plover]

nope its specific to the way i used the code.. i had 2 extra newline characters at the top of the output due to if counter % 6 == 0 being true even at the start

now that i think.. a better way would have been

counter = 0
out = ""
while counter < 12:
    if counter % 6 == 0 and counter != 0:
        out += "\n\n"
    elif counter % 3 == 0:
        out += "\n"
    else:
        out += "-"
    if counter % 6 == 0 or counter % 6 == 5:
        out += "1"
    else:
        out += "2"
    counter += 1
print(out)

[hard trail]

But that's the same right counter % 6 == 0 or counter % 6 == 5:

[hard trail]

I think I need to do more exercises like these

How do you improve algorithmik thinking like that xd

I feel like I could improve this a bit

[winged plover]

ah i have just started out too
so idk lol
i just solve random questions here which i can

[hard trail]

Maybe I should too xd I focus mainly on web development

[hard trail]

I can't believe the solution to this is so easy.

So the 6 ==5

Checks the 6th element, every 5 blocks?

in chunks or somethig

[winged plover]

yup basically every 1st and 6th element are returned one in simple terms

[hard trail]

I feel that's what I was lacking. I will need to create some demo grids to practice this, I thikn I get the idea now.

I seriously appricaite your help. I was on this since yesterday night, its already night as well xdd

I just cna't believe it lol

[idle pier]

hello folks, whats the best way to learn and practice graph problems?

[hard trail]

I don't know, but I suppose by solving simple questions first right

[feral hound]

do more graph problems

[brazen flume]

Hello, I want to ask is "Priority Queue" and "Max-Heap" some kind of synonyms or are there actually differences between each other? I'm kinda green into the algos and ds stuff and trying to learn some basic understanding.

[half shore]

I need help guys!

Is this statement true or false?

[knotty magnet]

yes

[half shore]

f(n) and g(n) are funtions. If f(n) ∈ O(g(n)), then 2^f(n) ∈ O(2^g(n))

[keen hearth]

Technically correct 😄

[keen hearth]

Hmm, well f(n) ∈ O(g(n)) is the same as saying that there exists n0 and a such that, for n > n0, f(n) < a g(n).

And 2^f(m) ∈ O(2^g(m)) is to say there exists m0 and b such that, for m > m0, 2^f(m) < b 2^g(m).

The function 2^x is monotonically increasing, so x < y is the same as 2^x < 2^y.

And I'm not sure where to go from there actually 🤔

Maybe it's false actually.

Because 3 log(n) is O(2 log(n)), but n^3 is not O(n^2)

[knotty magnet]

aren't you done at that point? if you have 2^x < 2^y => x < y, doesn't 2^f(m) < b * 2^g(m) => f(m) < b * g(m)?

[fiery cosmos]

I think false because say f(n) = 2n and g(n) = n, then 2^f(n) = 2^(2n) = 4^n which grows faster than 2^g(n) = 2^n (because 4^n and 2^n don't differ by a constant factor)

[shut breach]

yeah I've never considered the other side of this coin

[keen hearth]

Nah, we want to show the implication in the other direction. Ie we want to derive m0 and b from n0 and a, such that 2^f(m) < b 2^g(m).

[knotty magnet]

i c

[keen hearth]

Same ¯_(ツ)_/¯

[shut breach]

explains my struggle in proving it lol

[keen hearth]

Yeah, I just spent like 10 minutes trying to prove it 😄

If you compare timestamps 👀

@half shore

[fiery cosmos]

What's the complexity of f(x) = log(x) + log(log(x)) + log(log(log(x))) + ...

I figured just 2*log(x) for Theta(log(x)) because you can bound each term by 1, 1/2, 1/4, etc times log(x), so you have log(x) * (1 + 1/2 + 1/4 + 1/8 + ...)

But I wonder if there's a simpler way

[agile dirge]

how would you guys solve this problem efficiently.

cisco_devices = ["R1","R2", "R5", "R10"]
juniper_devices = ["R3","R4","R6", "R9"]
arista_devices = ["R8", "R7"]

pe_devices = ["R1", "R9", "R7"]
p_devices = ["R2", "R10", "R3", "R8"]

<some code to transform the top to the below>

{
R1: groups: ["cisco", "pe"],
R2: groups: ["cisco", "p"],
R3: groups: ["juniper", "p"],
R4: groups: ["juniper"],
R5: groups: ["cisco"],
R6: groups: ["juniper"],
R7: groups: ["arista", "pe"],
R8: groups: ["arista", "p"],
R9: groups: ["juniper", "pe"],
R10: groups: ["cisco", "p"],
}

[gritty marsh]

given you have a variable all_devices = ["R1", "R2", ...], it would look like this

d = {device: [] for device in all_devices}
for device in cisco_devices:
  d[device].append("cisco")
for device in juniper_devices:
  d[device].append("juniper")
...

this is the best non-hacky solution. if your current architecture doesn't allow for a more dynamic, DRY solution then you might want to rethink your architecture

[feral hound]

!e

cisco_devices = ["R1","R2", "R5", "R10"]
juniper_devices = ["R3","R4","R6", "R9"]
arista_devices = ["R8", "R7"]

pe_devices = ["R1", "R9", "R7"]
p_devices = ["R2", "R10", "R3", "R8"]


def add_devices(all_devices, devices, name):
    for device in devices:
        if device in all_devices:
            all_devices[device]["groups"].append(name)
        else:
            all_devices[device] = {"groups": [name]}

all_devices = {}
add_devices(all_devices, cisco_devices, "cisco")
add_devices(all_devices, juniper_devices, "juniper")
add_devices(all_devices, arista_devices, "arista")
add_devices(all_devices, pe_devices, "pe")
add_devices(all_devices, p_devices, "p")

print(all_devices)

[halcyon plank]

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

{'R1': {'groups': ['cisco', 'pe']}, 'R2': {'groups': ['cisco', 'p']}, 'R5': {'groups': ['cisco']}, 'R10': {'groups': ['cisco', 'p']}, 'R3': {'groups': ['juniper', 'p']}, 'R4': {'groups': ['juniper']}, 'R6': {'groups': ['juniper']}, 'R9': {'groups': ['juniper', 'pe']}, 'R8': {'groups': ['arista', 'p']}, 'R7': {'groups': ['arista', 'pe']}}

[feral hound]

how about something like this?

!e

cisco_devices = ["R1","R2", "R5", "R10"]
juniper_devices = ["R3","R4","R6", "R9"]
arista_devices = ["R8", "R7"]

pe_devices = ["R1", "R9", "R7"]
p_devices = ["R2", "R10", "R3", "R8"]


def add_devices(all_devices, devices, name):
    for device in devices:
        if device in all_devices:
            all_devices[device]["groups"].append(name)
        else:
            all_devices[device] = {"groups": [name]}

all_devices = {}
add_devices(all_devices, cisco_devices, "cisco")
add_devices(all_devices, juniper_devices, "juniper")
add_devices(all_devices, arista_devices, "arista")
add_devices(all_devices, pe_devices, "pe")
add_devices(all_devices, p_devices, "p")
all_devices = {device: all_devices[device] for device in sorted(all_devices, key=lambda x : int(x[1:]))}
print(all_devices)

if you want it sorted

[halcyon plank]

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

{'R1': {'groups': ['cisco', 'pe']}, 'R2': {'groups': ['cisco', 'p']}, 'R3': {'groups': ['juniper', 'p']}, 'R4': {'groups': ['juniper']}, 'R5': {'groups': ['cisco']}, 'R6': {'groups': ['juniper']}, 'R7': {'groups': ['arista', 'pe']}, 'R8': {'groups': ['arista', 'p']}, 'R9': {'groups': ['juniper', 'pe']}, 'R10': {'groups': ['cisco', 'p']}}

[fiery cosmos]

is there a way to improve my algothinking ?

[wispy sky]

excuse me , i'm not good about algorithm.
can you help me ?

[eager vapor]

can anyone help me with this

[mild dove]

I think you can mark the elements you already passed. run to right, down and left changing the direction when you see the end of the matrix or a marked element.

[feral hound]

I did this by keeping track of 4 limits which were the top, bottom, left and right sides initially it started at

top_limit = 0
left_limit = 0
bottom_limit = len(matrix)
right_limit = len(matrix[0])

then I would print going from left to right
then top to bottom
then right to left
then bottom to top

keep repeating this and decreasing/increasing the respective limit and add a check to see when you printed everything and your done

[keen hearth]

You could also think about it recursively. After one spiral, you're left with a smaller rectangular matrix.

You could actually think of it as yielding the elements from the top row; then chopping off that row, rotating the matrix 90 degrees anti-clockwise, and doing the same again until the matrix is empty. But you'll have to find a way to represent the matrix so thatyou can do that rotation without actually constructing a new matrix.

[dapper brook]

hello

i am stuck in a algo can someone help

You can think of this as a huge box filled with an unknown number of coloured balls. You get to empty the box one ball at a time through a “tap” at the bottom; you cannot see how many balls are left at any point in time until the box is actually empty. You are, however, told that one of the colours comprises more than 50% of the balls. Your job is to name that colour when you finish.
Provide an algorithm to do this. How many things do you need to remember? Do you need to keep all the balls/integers or can you throw them away after you pick them? How much time would it take you, assuming it takes one unit of time to compare two balls and decide whether or not they are the same colour?

[keen hearth]

@feral hound So it would be like: py def solve(matrix): m = RotatedMatrixView(matrix) while m: yield from m[0,:] m = m[1:,:].rotated Then you "just" have to implement RotatedMatrixView 😄

[dapper brook]

can u explain please

[keen hearth]

Oh sorry, that was in response to someone else.

[dapper brook]

lol

[keen hearth]

Erm, have you any ideas of how you might do this?

[dapper brook]

can someone help with this. it's killing me

[keen hearth]

There is actually a really clever streaming algorithm to solve this, called the Boyer-Moore majority vote algorithm, but I'm guessing your instructor doesn't expect you to discover this.

[dapper brook]

yup

but we are allowed to google

[keen hearth]

Have you thought about counting up the frequencies of the different colours?

Like how many of each colour ball there is.

In a table.

[feral hound]

learnt something new its fairly simple as well

also based on the text I think this is what they are expected to work towards

although I dont think they are expected to find it more so just get them thinking towards it

@dapper brook think of any solution to begin with

[dapper brook]

yup

[feral hound]

any ideas?

[dapper brook]

yeah assuming n balls

i thought like this sort the array with any algorith say quick sort and what we got in the first half or second half may be the answer

[feral hound]

would you need to sort it though?

remember you only care about the maximum value

[dapper brook]

ohh

[feral hound]

so do you have some kind of solution now?

[dapper brook]

not yet because the array is un known

how do i check

i am very confused in this

but enjoying it

[feral hound]

btw there are many ways to do this do you want me to walk you through multiple solutions or do you just want the optimal one?

[dapper brook]

no multiple

[feral hound]

ok so lets start from the beginning

you have a box with colored balls and you can only get 1 random one out at a time

[dapper brook]

yeah

[feral hound]

whats your first idea dont worry about the implementation details for now

[dapper brook]

take a ball out hold it in one hand then take out other to compare

if it came same then i note down that color

that's what i am thinking now

[feral hound]

and then what would you do?

remember you want to find out which color is 50% or more

[dapper brook]

then at last i will again look for those color of ball whose i had noted

i don't know actually

[feral hound]

so what do you mean by noted?

[dapper brook]

like i took note when my both hand have same color ball

[feral hound]

did you have a look at the Boyer-Moore majority vote algorithm?

btw im not telling you to look at it rn but asking if you looked at it

[dapper brook]

not yet

[feral hound]

ok no worries its just your repsonse is along those lines but for the other solutions its not something you should be doing

ok how about this everytime you see a ball of a specific color throw it in a bin for that color

keeping track of how many ballls are in each bin

at the end when you got all the balls you know that your answer is the color of balls in the bin with the most balls correct?

[dapper brook]

wait what

i need time to process this

[feral hound]

lets do a few steps from the beginning

I get a red ball from the box

[dapper brook]

okay

[feral hound]

so I get a red bin and throw the ball into it

I also say that the red bin has 1 ball in it

[dapper brook]

make sense

[feral hound]

then I get a yellow ball the second time so I get a yellow bin and throw the yellow ball in it saying the yellow bin has 1 ball

then I get another red ball the third time so I get the red bin and thow the red ball in it increasing the count of balls for that bin by 1 so it now has 2 balls

and so on until the box is out of balls

then I check which color bin has the most balls and thats my answer

[dapper brook]

ohh but what if all 50% balls are diffrent

[feral hound]

?

[dapper brook]

then i need 51 box right

[feral hound]

yeah

the number of bins doesnt matter

if you see a new color just get a new bin

[dapper brook]

yeah

i want to explore more

are there more ways

[feral hound]

there are but for now I would say try to write this solution out

in code

there are also different ways to code this particular solution which either make it a lot faster or a lot slower

[dapper brook]

so the approach is this but we can code it faster or slower

[feral hound]

yes depending on how you do it

[dapper brook]

u are great @feral hound

[feral hound]

given this

box = ["red", "red", "yellow", "green" "red"]

write a solution

[dapper brook]

no we don't need code

for this

[feral hound]

oh this is just a discussion kind of thing?

[dapper brook]

yeah

[feral hound]

well you dont have to worry about this that much then

[dapper brook]

we have to discuss and use all the resource and find this thing

[feral hound]

the idea here was if you thought of the bins as an array it would be slow

if you thought of the bins as a dict it would be a lot faster

[dapper brook]

hmm

you could became a teacher😂

[feral hound]

if you dont know what a dict is dont worry about it too much for now you will find out when you need it

[dapper brook]

seroiusly i had never understood a thing on chat

before this

[feral hound]

np 🙂

we can now move on to whats wrong with this solution and what would be better

so the issue here is that have to keep all the balls

[dapper brook]

yeah

[feral hound]

and depending on how you choose to implement it you might be doing a lot of comparisons as well but thats an implementation detail in the best case you would still be doing a single comparison for each ball

the optimal solution
Boyer–Moore majority vote algorithm
allows you to do 1 comparison and store only 1 ball and single count

so it uses a lot less space

[dapper brook]

how

[feral hound]

https://en.wikipedia.org/wiki/Boyer–Moore_majority_vote_algorithm

have a quick read through this and have a look at the pic on the right

come back afterwards and I will explain what you dont understand

as to how and why it works

[dapper brook]

okay

it's something like this if i found a number then i assign a frequency

not sure but

[feral hound]

ok lets walk through this example

first you start with nothing hence the ?

you get a blue ball

so you keep holding the blue ball and set the count to 1

then you get another blue ball

you compare the balls and since its the same color you set the count to 2 and keep holding the blue ball

throwing away the other one

then you get a red ball

you compare the red ball and the blue ball they are different colors

so you -1 from the count

but keep holding the blue ball

the count is now 1 again

then you get a blue ball

[dapper brook]

okay

[feral hound]

thats the same color as the ball you are holding so you add 1 to the count

the count is now 2

then you get a red ball

-1 from the count

the count is now 1

throw away the red ball

you get a yellow ball

thats different from your blue ball so -1 from the count

the count is now 0

keep holding the blue ball

you then get a yellow ball

thats different to the blue ball your are holding

the count is 0 so instead of doing -1

throw away the blue ball and hold the yellow one instead

setting the count to 1 now

[dapper brook]

ohh

[feral hound]

now keep repeating this process until the box runs out of balls

the ball you hold at the end is the majority

so does it make sense how this algorithm works?

[dapper brook]

yeah

[feral hound]

do you understand why it works or do you want an explanation for that?

[dapper brook]

explainaton

would be better

[feral hound]

ok so this algorithm only works when you specifically have only 1 color that is either 50% or more

for some simple intuition as to why

imagine you have exactly 100 balls

[dapper brook]

okay

[feral hound]

51 are red
20 are blue
29 are yellow

[dapper brook]

okay

[feral hound]

51 - 20 = 31

31 - 29 = 2

so if you take away all the blue and yellow balls from the red balls you will still have 2 red balls left in the end

now the rule about keeping the ball when the count is 0 allows it to work for exactly 50 aswell

since if we have
50 red balls
20 blue balls
30 yellow balls

50 - 20 = 30

30 - 30 = 0

but we would still be holding a red ball at the end

does that explain it?

[dapper brook]

perfectly

100%

wait can i ask something about u

[feral hound]

?

[dapper brook]

u are not a student right

[feral hound]

graduated uni this year

[dapper brook]

from which university

sorry that a bit persnal

[feral hound]

city university of london but now we're getting a bit too specific so lets leave it at that

[dapper brook]

yeah

right

[tropic glacier]

ah, I had a friend who did a postdoc there, in quantum info

I miss London...yet another place where I can say, wow, it would be so awesome to live here if I had money 😉

[feral hound]

^^ its way too expensive lol

[sly flower]

hiii

👀

[idle pier]

folks am currently doing merge binary trees on leetcode

def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        
        if root1 is None:
            return root2
        if root2 is None:
            return root1
        
        root1.val = root1.val + root2.val
        root1.left = self.mergeTrees(root1.left,root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)
        return root1```
What exactly is ```py
root1.left = self.mergeTrees(root1.left,root2.left)
root1.right = self.mergeTrees(root1.right, root2.right)``` doing?

[feral hound]

if your wondering why you cant just do

self.mergeTrees(root1.left,root2.left)
self.mergeTrees(root1.right, root2.right)

its because it can be that one or both of left/right nodes is None

[idle pier]

umm not really, I just want to know what is happening

I know its using the BFS algo. I think whats happening is that its checking if there is a left/right node

[feral hound]

try to work through what would happen using a very simple example to start with it should hopefully make sense as you work through it

[feral hound]

its not really doing any searching

its just adding the overlapping nodes

[idle pier]

ohhh I think I get it now, so the first 4 lines of code is basically doing this, if there isnt a left/right node on root1, then simply put the left/right node from root2 and vice versa. As for the rest of the code, its basically adding the overlapping nodes, correct?

[feral hound]

yup

[desert stratus]

Make a Node class. The class should hold a value variable, and a reference to another instance of itself

How to do that pls help ping me too

[fiery cosmos]

Have anything so far? @desert stratus

[desert stratus]

I have this

class CustomArray {
    private int[] items;
    
    public CustomArray() {
        items = new int[0];
    }
    
    public void addFirst(int item) {
        int[] newArray = new int[items.length + 1];
        newArray[0] = item;
        
        for (int i = 1; i < newArray.length; i++) {
            newArray[i] = items[i-1];
        }
        
        items = newArray;
        
        Print(items);
    }
    
    private void Print(int[] arr) {
        System.out.println("************");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

public class Main
{
    public static void main(String[] args) {
        CustomArray customArray = new CustomArray();
        customArray.addFirst(5);
        customArray.addFirst(12);
        customArray.addFirst(6);
        customArray.addFirst(24);
        customArray.addFirst(122);
        customArray.addFirst(16);
        customArray.addFirst(24);
    }
}

But that’s not what I have to do

Here’s the actual question

[fiery cosmos]

I meant your node class, but that isn't Python 🐍

This server is for Python questions.

You can head to off topic #ot0-psvm’s-eternal-disapproval to talk non-Pythony stuff

Though in python the Node class might look like py class Node: def __init__(self, value, childnode=None): self.value = value self.childnode = childnode

[desert stratus]

Hmmm

But I need on java lol

[quiet jay]

#help-apple

[safe crane]

How can i send information from class to another class in python? first class has self.url information and i want to send it second class, how can i do that?

[fluid copper]

@safe crane are they subclasses? metaclasses? if they don't have an inheritance you'll likely need to build some kind of interface between them

Question while I am here (I don't know really where else to put it.) since a method is just a callable, if I want to reference kwargs before instantiation, I essentially have to set a list of values in the file that contains the function, correct? (I am pretty sure this is true, since precompiler/parser mro other words yadda yadda, but I get caught up in small things and forget.)

[safe crane]

May I send the source codes as a private message? I don't know much about connections between classes, I'm just a beginner.

[fluid copper]

go for it

[agile dirge]

@feral hound @gritty marsh thank you both. Sorry to tag, but just wanted to reach out and say thanks for the code yesterday 😄

[feral hound]

np 🙂

[agile dirge]

I went for this in the end

def add_devices(all_devices, devices, name):
    for device in devices:
        if device in all_devices:
            all_devices[device]["groups"].append(name)
        else:
            all_devices[device] = {
                "groups": [name],
                "port": 22,
            }

all_devices = {}
for region, devices in region_list.items():
    add_devices(all_devices, devices, region)

[raven tide]

can anyone explain what a monotonic stack is and its uses?

i heard its something like an increasing/decreasing stack but i didnt really understand after that

[lime fable]

@raven tide I found this article it might help you https://medium.com/techtofreedom/algorithms-for-interview-2-monotonic-stack-462251689da8

[timid orbit]

where can i get resources for algo and ds?

[urban flame]

anyone know how i can speed up this?

:

    zipped_lists = zip(l1, l2)
    sorted_pairs = sorted(zipped_lists)

    tuples = zip(*sorted_pairs)
    l1, l2 = [ list(tuple) for tuple in  tuples]
    return l2

def Get_Z(faces,PointsInSpace):
    Z = []
    for face in range(len(faces)):
        c_face = faces[face]
        v_1 = int(c_face[0,0]) - 1
        v_2 = int(c_face[0,1]) - 1
        v_3 = int(c_face[0,2]) - 1
        v_1 = PointsInSpace[v_1]
        v_2 = PointsInSpace[v_2]
        v_3 = PointsInSpace[v_3]
        z_1 = 1/(10 - v_1[2][0])
        z_2 = 1/(10 - v_2[2][0])
        z_3 = 1/(10 - v_3[2][0])
        z = (z_1 + z_2 + z_3) / 3
        Z.append(z)
    return Z```

[hidden fiber]

for basic or advanced?

[timid orbit]

basics and probably intermediate level

[vocal gorge]

Most likely, you can rewrite this using numpy arrays, but I don't quite understand what you're doing enough.

[hidden fiber]

both freecodecamp and nesoacademy are good to start and then get your mind dirty with CLRS 🙂

[dusty hollow]

hope this is proper channel to ask the question. can someone help me port py code to c++?

s =  np.mean(df['High'] - df['Low'])
def isFarFromLevel(l):
   return np.sum([abs(l-x) < s  for x in levels]) == 0

this is pretty self-explanatory i suppose, so far i have this, but it misbehaves and I couldn't spot error

std::vector<double> TickerSize(TickerData->High.size());
std::transform(TickerData->High.begin(), TickerData->High.end(), TickerData->Low.begin(), TickerSize.begin(), std::minus<double>());
double Sum = std::accumulate(TickerSize.begin(), TickerSize.end(), 0.0f);
this->Mean = Sum / TickerSize.size();

bool IsFarFromLevel(double Level, double Mean, std::vector<Marker>& Marker)
{
  return std::accumulate(Marker.begin(), Marker.end(), Level, 
    [&Mean](double level, struct Marker marker) {
      return (std::abs(level - marker.Price) < Mean);
    }) == 0;
}

with == 0 in IsFarFromLevel return no levels are added
if i remove == 0 in IsFarFromLevel return only first level is being added and the rest are ignored

[sharp lake]

my program is returning list index out of range, and idk why

cpf = str(input("Type the cpf: ")).replace("-","").replace(".","")
    with open("cadastros.txt","r") as file:
      for k,c in enumerate(file.readlines()):
        txt = convert(file.readlines()[0])[1]
        if cpf in txt:
          cpfcadastrado = True```
inside the txt file:

joao-0568
alcione-05644```

the error is on txt = convert(file.readlines()[0])[1]

[mild dove]

I don't understand why you need to read again the same file inside the 'for' loop

[rough lynx]

You've already read the line by looping with for k,c in enumerate(file.readlines()): so doing it again with txt = convert(file.readlines()[0])[1] is causing you issues

Also not sure why you're enumerating with that statement
You should be doing for line in file.readlines(): where line becomes a string of data for you to work with for each iteration of the loop

[idle pier]

Is an O(n^2) alogrithm better than O(n) algorithm?

[jolly mortar]

an O(n^2) algorithm may or may not perform better for relatively small inputs, but if the input size grows without bound, O(n) is better

(the O notation drops constants, which can be significant factors for small inputs)

[idle pier]

Yea I was thinking about that, if n=10, then one really wouldn't tell the difference but if n=10000000000, then I think we would clearly see the difference

[jolly mortar]

yeah

[idle pier]

@jolly mortar I saw this question somewhere and it got me thinking, what data structures and algorithm are good for a library system but in a simple summary?

I thought about maybe using a binary search algo or a sorted array but not sure if its the best way

[jolly mortar]

dictionaries?

dictionaries/hashmaps have O(1) lookup

the tradeoff is that they are slightly memory inefficient

[idle pier]

hmmm I see

Hashmap/hashtable is always more efficient (faster) than linear search?
I think for this question, is it really depends on what kind of program

[fiery cosmos]

yeah, linear is O(n), hashtables(assuming nicely managed) take O(1)

[winged plover]

@fiery cosmos that reminds me... Were u able to solve level 3 of yday's leetcode thing

[fiery cosmos]

oh i did solve 2nd but bad performance then i had to study.

i will see if i have time today, I'll make 2nd better and then try 3rd.

[winged plover]

Ah alright cool

[idle pier]

@fiery cosmos What the data structures and algorithm for a library system would you use?

[fiery cosmos]

depends on the need, i'd prefer dict with something unique.
say for student system

students = {
202061003: ClassObjectOfStudent<>,
}

so dicts and classes.
and for certain fastness if you need, you can create (and manage tho) extra data structures to make things faster.

[halcyon plank]

Hey @crisp isle!

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

[crisp isle]

How can I proceed to implement the Prim's algorithm in this case? I think the difficulty arises because I have converted the weighted edge list to an adjacency list. So I don't know how I can traverse the adjacent vertices of the adjacent vertices to include that in my minimum spanning tree list. I hope someone helps. https://paste.pythondiscord.com/niyataxado.py

[timid nexus]

your code isn't showing

[crisp isle]

https://paste.pythondiscord.com/niyataxado.py

[timid nexus]

to add your code

[crisp isle]

It's here.

[crisp isle]

I tried doing that, but the code was too long! Also, I wasn't able to upload the file.

[timid nexus]

Ah okay

[crisp isle]

Anyone?

[feral hound]

I havent seen this algo before but if im understanding correctly it just chooses some node as the starting node then it finds the which node connection has the least weight connecting to the starting node and adds it to the tree then it just repeats this process however it will now have to check the weights for all nodes in the tree and their connections outside the tree to find the lowest weight connection to connect next is this correct?

the algo would also be O(N^2) based on this

[crisp isle]

I didn't understand from "however", but the first part is correct.

[feral hound]

so I mean it has to check every node not in the tree against every node in the tree to find the lowest weight connection

I think you can do this easily with nested for loops you just need 2 lists

nodes in tree nodes not in tree

and a way to find the connection weight for the nodes then just find the minimum connection on each iteration and add that node into the tree and remove it from the list of nodes not in the tree

you can simultaneously build the min span tree as you do this however your algo doesnt need to directly know about any of the connections to work

[feral hound]

adjacency_list

this is just a dict with the weights between every node correct?

[crisp isle]

Yes, I have implemented it in the form of a dict where key contains every vertex and the corresponding value is a list of tuples of (adj_vertex, weight).

[feral hound]

ok all you need to do is to find the adj_vertex that has already been added to the tree with the least weight

how do you want to represent your min span tree?

list of tuples (node1, node2, weight) like this?

[crisp isle]

It's the print_min_spanning_tree in my code. It's will be a list of lists [vertex, adj_vertex, weight]

[crisp isle]

Yeah

[feral hound]

ahh so it is what I thought yeah this is fairly simple then

do you have a list of every node in the tree?

it just has to be
[node1, node2, node3 ,....., node n]

[crisp isle]

It is present when I add_link to the graph and construct the structure in my code.

[feral hound]

if you pass this into the algo it will be much easier to do

[crisp isle]

So I will have to first find the nodes by using self.graph and make them a part of a separate list, right?

[feral hound]

I would say that makes it easier yeah

[crisp isle]

vertices = list(adjacency_list.keys())

[feral hound]

    def prim_min_spanning_tree(self, all_nodes):
        visited: List[int, str, float]
        adjacency_list: Dict
        minimum_spanning_tree: List[List]

        nodes_not_in_tree = copy.deepcopy(all_nodes)
        nodes_in_tree = [nodes_not_in_tree.pop()]
        minimum_spanning_tree = []
        adjacency_list = self.edge_to_adjacency(self.graph)
        # What should I do from here? How should I implement Prim's?
        while nodes_not_in_tree:
            for node_in_tree in nodes_in_tree:
                for node_not_in_tree in nodes_not_in_tree:
                    # finding min weight
             # add the min weight to the node_in_tree list and remove it from the node_not_in_tree list construct the graph here as well
        return minimum_spanning_tree

[maiden hornet]

is anyone here familiar with constructing DFA’s

[nimble kestrel]

Hi,
Do you have any idea about this school question?

Consider a time series of daily price of EUR/USD in 2020. You have 1000 Euro and want to invest by these rules:

Buy 100 Dollar when the price today is the highest price during last T1 days.

Buy 100 Euro when the price today is the lowest price during last T2 days.

If needed, you can consider any other restrictions. Find the optimized values for T1 and T2 and discuss your favorite statistics.

[trim fiber]

Any idea about solution or what?

[tropic glacier]

Those instructions tell you exactly what to do. So where do you get stuck?

[split musk]

Master theorem question,
t(n) = 2t(n/3) +1
a = 2
b = 3
k = ?
p = ? guess is 1

[trim fiber]

Is this the whole question?

[grim stone]

Not sure if this is the right spot, but I need some help with rotating numpy arrays. I am representing a 3x3 rubix cube as its 27 smaller cubes with 6 sides. That makes the shape of the array (3, 3, 3, 6). The first dimension is the 3 horizontal layers, the 2nd is the 3 rows in the layer, the third is the 3 cubes per row, and the last dimension is the 6 sides of the small cubes. I am able to rotate the cube horizontally due to the structure of the array, but that makes rotating vertically difficult. Does anyone know how I could rotate vertically?

[brave oak]

what are you using to rotate?

I would imagine rot90 would work for all cases

[stable pecan]

i just wrote a rubix cube program not long ago -- but represented the cube with just a (3, 3, 3) array

there's no need for a fourth axis

[unreal marsh]

where should i start learning algorithms?

[ivory yacht]

There's a few suggested courses pinned in this channel.

[dapper sapphire]

if we have

num1 = 1
num2 = 2
num3 = 3

Then doing
num1 < num2 < num3 is the same as num1 < num2 and num2 < num3?

!e

num1 = 1
num2 = 2
num3 = 3

print(num1 < num2 < num3)
print(num1 < num2 and num2 < num3)

[halcyon plank]

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

001 | True
002 | True

[jolly mortar]

yeah, operator chaining is equivalent to joining them with ands

[ivory yacht]

There is a slight difference though, num2 isn't re-evaluated, so if it has side effects those occur only once.

[dapper sapphire]

Could you elaborate on if it has side effects those occur only once please.

[ivory yacht]

def disp(value):
    print("The value is", value)
    return value
a = 1 < disp(2) < 45
b = 1 < disp(2) and disp(2) < 45

In the first one, disp() only gets once so you only get a print once.

[dapper sapphire]

oh ok I see exactly what you mean

Thank you for the example!

[nimble kestrel]

The solution

[trim fiber]

!rule 8

[halcyon plank]

Rules

8. Do not help with ongoing exams. When helping with homework, help people learn how to do the assignment without doing it for them.

[trim fiber]

Show your minimal effort

[twin quiver]

hi could someone help me with question pls?

source = [1, 2]
source[1] = source
[[source[:] for i in range(n)] for j in range(n)]
y = [z[:] for z in x]

the question is how many lists are contained directly or indirectly in variable x?

[halcyon plank]

Hey @crisp isle!

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

[crisp isle]

class MaxHeap:
    def __init__(self, array):
        self.heap = array
    
    def heap_sort(self, array):
        self.build_max_heap(array)
        for end in reversed(range(1, len(array))):
            self.swap(0, end, array)
            self.sift_down(0, end - 1, array)
        return array

    def build_max_heap(self, array):
        first_parent_index = (len(array) - 2) // 2
        for current in reversed(range(first_parent_index + 1)):
            self.sift_down(current, len(array) - 1, array)
    
    def sift_down(self, current_index, end_index, heap):
        child_one_index = current_index * 2 + 1
        while child_one_index <= end_index:
            child_two_index = current_index * 2 + 2 \
                if current_index * 2 + 2 <= end_index else -1

            if child_two_index > -1 and \
                    heap[child_two_index] > heap[child_two_index]:
                index_to_swap = child_two_index
            else:
                index_to_swap = child_one_index

            if heap[index_to_swap] > heap[current_index]:
                self.swap(current_index, index_to_swap, heap)
                current_index = index_to_swap
                child_one_index = current_index * 2 + 1
            else:
                return

     def swap(self, i, j, heap):
        heap[i], heap[j] = heap[j], heap[i]

array = [3, 8, 34, 32, 5, 9, 20]
max_heap = MaxHeap(array)
max_heap.heap_sort(array)

I am getting an incorrect output: [3, 34, 5, 8, 9, 20, 32]

Can someone help me?

[vivid thistle]

I'm trying to implement KMedians but am super stuck on how to assign each point to the nearest cluster using manhattan distance. I have 4 centers that are just 13 values at this point and I don't know how to go from there.

[idle pier]

Hello folks am currently doing 897. Increasing Order Search Tree. I had trouble solving it so I looked up a solution but am also having trouble understanding the solution

class Solution:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        arr = []
        
        def inorder(root):
            
            if not root:
                return []
            inorder(root.left)
            arr.append(root.val)
            inorder(root.right)
        inorder(root)
        
        new_root = TreeNode(arr[0])
        temp = new_root
        for i in range(1,len(arr)):
            temp.right = TreeNode(arr[i])
            temp = temp.right
        return new_root```

[fiery grove]

Hello Guys

I have learnt intermediate level python programming

like OOP

A lil bit of Async Await in discord.py

So i think its time for me to learn algorithms and data structures

can anyone suggest some materials or course

to learn algo and data structs

[shut breach]

check out the pins here ^

[fiery grove]

Oh thanks

[shut breach]

np

[desert shadow]

is anyone able to help explain why this algo is time complexity of O(N)?

[finite spruce]

I'm no CS expert but is it? It seems like it should be O(log_2(n))

[desert shadow]

yeah ur right, i asked a few other people 😅 seems like my answer key was wrong..

[glossy breach]

That is actually O(n)

Not O(log2(n))

[feral hound]

I dont know if im missing something but that does seem to be O(log2n)

[glossy breach]

It should be O(log2(n)) if he just calls mystery(n//2) once

In this case he actually called mystery(n//2) + mystery(n//2)

[feral hound]

calling it twice doesnt change the complexity

[glossy breach]

It does

So it becomes a perfect binary tree

It's not a straight line any more

[feral hound]

O(log2n) + O(log2n) = O(log2n)

[glossy breach]

however

Each mystery(n//2) does the same thing once again

[feral hound]

actually yeah your right it is a binary tree

[glossy breach]

mystery(n)
   |
mystery(n // 2)
   |
mystery(n // 4)
   |
mystery(n // 8)
...
   |
mystery(0)

Normally if he calls it once it would go like this right

[feral hound]

yeah just realised what your saying

[glossy breach]

alright

[feral hound]

it is indeed O(n) guess thats another thing to look out for

[desert shadow]

oof

im confused

[feral hound]

you can draw out your function calls so that they look like a binary tree

excuse my drawing skills

@desert shadow

I only drew the right side but the left would look the same

imagine m is your function and n is the input number you pass when you call it

you can see from this that your function will actually be called 31 times which is 4n - 1

this relationship should stay constant no matter the size of n so its O(n)

[feral hound]

only exceptions being n=1 and n=0

[shut breach]

another way of thinking about it is that each call halves the input, so you reach the bottom of the tree in log(n) calls, and a binary tree of height log(n) has n nodes (aka a binary tree of height n has 2^n nodes)

[glossy breach]

Oh wait

Sorry misread

[shut breach]

or another way, T[n] = 2*T[n/2], so doubling the size of the input doubles the time it takes, which is only true in linear relationships

[desert shadow]

ohhh so it become 2^(logn)?

[shut breach]

yeah

[desert shadow]

thank u for taking the time to draw the tree

and u use this to get O(n) right

thank u very much btw 😄

[shut breach]

this is probably the more intuitive way of thinking about it

[cinder yacht]

could someone explain why this script is causing data sharing across different objects

from typing import List

class a:
  def __init__(self, test: List[str] = []):
      self.test = test

y=a()
x=a()
x.test.append('a')
y.test.append('b')
x.test.append('c')
y.test.append('d')
print (x.test)
print (y.test)

# output
# ['a', 'b', 'c', 'd']
# ['a', 'b', 'c', 'd']

This happens because of the optional parameter in the constructor, but I'm unsure why it would do that

And what's a better way to create a default param without this happening

[ivory yacht]

The default parameter is evaluated when you create the function initially, so you only actually have one list. Instead there's two ways to fix this:

from typing import Optional, List, Iterable
def __init__(self, test: Optional[List[str]] = None) -> None:
  if test is not None:
      self.test = test
  else:
      self.test = []

def __init__(self, test: Iterable[str] = ()) -> None:
    self.test = list(test)

The first way just sets the default to None, and manually makes a new list if you don't provide one. The second is something I kinda prefer - specify that test can be passed in as any iterable, default to an empty tuple and build a new list out of it always. It allows you to pass in other things that aren't yet lists, and if you do pass a list it'll make a copy so it's not shared.

[cinder yacht]

Thanks so much for the detailed response. This clears up a ton! Gonna implement this tomorrow. With Python typings, is it standard to declare a return type of None from constructors?

[ivory yacht]

__init__ isn't quite a constructor, it's an initialiser - the object already exists to be passed in as self. And it is yes, __init__ must return None, you'll get an error if you don't so you can really leave off the return annotation.

[strange loom]

help

[fossil pulsar]

Hey guys....I want to solve an if else question with if else. How can I do so? The question is- input marks from user and if marks less than 80, print C, if marks less than 90, print B and if marks less than 100, print A

Any idea how to do this?

[fiery cosmos]

why is O(n^2) capitalized and not?

is there a difference?

N^2 and n^2?

[trim fiber]

Technically n and N can be different variables

[fiery cosmos]

in the image above, why is it like that? @trim fiber

is he trying to show something

or simple mistake?

[trim fiber]

In that case it maybe misspelling

[trim fiber]

I am guessing that it's a mistake

[fiery cosmos]

so what is the conventional way to write big o?

using capital?

or lower case

[trim fiber]

I am using lowercase letters

O(n + k) for example

[fiery cosmos]

ok thanks

[trim fiber]

Instead of O(N + K)

[crisp isle]

It depends on your definition of constructor. In some languages, constructor even sets the member variables; in some, it creates the object. In that sense, __init__ may be called as a constructor. However, the term "constructor" is not explicitly defined in the documentation but has been used several times in PEPs. That being said, the documentation still contains the term "constructor expression". It still is disputable.

[fossil pulsar]

anyone?

[trim fiber]

Do you have any code?