Note: I don't want to be just given the answer.
#algos-and-data-structs
cinder rivet
fair summit
greatest_prime_factor = 0
for factor in factors:
if isItPrime(factor):
if factor > greatest_prime_factor:
greatest_prime_factor = factor```that bit of code can be entirely removed if you improve the part that finds the factor to only find the prime factor directlyremoving the isItPrime call which is what is slowing the program down
think of it this way, any number can be represented by multiplying all its prime factors together
cinder rivet
So do you think that I should make a function is_prime_factor that tests if a number m is a prime factor of n?
fair summit
nope, you should make a get_prime_factors function that directly gets the factors, you don't have to do anything specific to only get the prime factors
i'm not sure how to help you without spoiling you the answer
hint: division
cinder rivet
Here's my new idea.
def get_prime_factors(n: int, factors_so_far: list) -> list:
"""Returns a list of n's prime factors"""
for i in range(2, n):
if n % i == 0:
if isItPrime(i):
smallest_prime_factor = i
if n % smallest_prime_factor == 0:
return [smallest_prime_factor]
else:
return get_prime_factors(n % smallest_prime_factor, factors_so_far + [smallest_prime_factor])
sqrt n algorithm
@fiery cosmos I haven't heard of this. Can you explain?
fiery cosmos
hold up I am writing the algorithm
fair summit
i can give you another hint: use a while loop, not a for loop
and the past one: use division
fiery cosmos
fair summit
welp, there you go i guess
cinder rivet
If I click that, will it just give me the answer?
fiery cosmos
the algorithm not your problem answer
fair summit
it's the prime factor algorithm
fiery cosmos
Also that can be the answer to your problem facs[-1] is the answer
cinder rivet
I'm working with this now.
def get_prime_factors(n: int, factors_so_far = []) -> list:
"""Returns a list of n's prime factors"""
smallest_prime_factor = 1
for i in range(2, int(n)):
if n % i == 0:
if isItPrime(i):
smallest_prime_factor = i
if n / smallest_prime_factor == 1:
return [smallest_prime_factor]
else:
return get_prime_factors(n / smallest_prime_factor, factors_so_far + [smallest_prime_factor])
Trying out using recursion.
get_prime_factors(13195) = get_prime_factors(13195 / smallest_prime_factor) = get_prime_factors(13195 / smallest_prime_factor / smallest_prime_factor) etc
fair summit
i think you're not gonna get far with that solution
cinder rivet
Why not?
fair summit
it's way too heavy computationally speaking, and the recursive part is actually not useful, you can directly return smallest_prime_factor (poorly named variable btw, it's actually the biggest prime factor)
ditch the isItPrime function entirely
and use a while loop
cinder rivet
How am I supposed to check for primality then?
cinder rivet
I'm unaware.
cinder rivet
ye
cinder rivet
ye
cinder rivet
ye
cinder rivet
no
fair summit
yes, is 3 a prime factor ?
cinder rivet
yes
cinder rivet
no
fair summit
is 5 a prime factor ?
cinder rivet
no
cinder rivet
okay yes
fair summit
[2, 2, 2, 3, 7], x = (1001/7) = 143
is 7 a prime ? no
is 11 a prime ? yes, [2,2,2,3,7,11], x = 143/11 = 13
is 11 a prime factor ? no
is 13 a prime factor ? yes
[2, 2, 2, 3, 7, 11, 13], x = 1
x = 1, we stop
you have your list of prime factors
24024 = 2 * 2 * 2 * 3 * 7 * 11 * 13
cinder rivet
I don't get how this checks for primality.
cinder rivet
oh
def get_prime_factors(n: int) -> list:
"""Returns a list of n's prime factors"""
prime_factors = []
d = 2
while n != 1:
if n % d == 0:
prime_factors.append(d)
n /= d
else:
d += 1
return prime_factors
if we divide by 2 until it's no longer divisible by 2
we will never find 4 later on
@fair summit How do you know this to be true?
fair summit
if it's not divisible by 2, it's not divisible by any number that has 2 as a prime factor
stable pecan
this is fun to do with collections.Counter
In [1]: from collections import Counter
...:
...: def prime_factors(n, cache={1: Counter(), 2: Counter({2: 1})}):
...: if n in cache:
...: return cache[n]
...:
...: if n % 2 == 0:
...: cache[n] = prime_factors(n // 2) + prime_factors(2)
...: return cache[n]
...:
...: factor = 3
...: sqrt = int(n ** .5) + 1
...: while factor < sqrt:
...
I did this recursively, but memoized
cinder rivet
What is memoized?
stable pecan
memoized means the function caches previous results
cinder rivet
I see...
stable pecan
so it doesn't have to do all the calculations again
i didn't add the n% 2 part to cache
there we go
In [2]: prime_factors(24024)
Out[2]: Counter({13: 1, 11: 1, 7: 1, 3: 1, 2: 3})
gaunt forge
So basically if it's memoized then it's dynamic programming?
fiery cosmos
nope if there are overlapping subproblems and you can form some kind of relation among the subproblems and the main problem then you can use dynamic programming.
burnt hill
yo guys i need help
im still new to python
and im trying to figure out how to make vectors
stable pecan
there's a few libraries that have implemented them already
burnt hill
my first programming language i guess is matlab
stable pecan
if you're familiar with matlab, then try numpy
burnt hill
and im trying to figure out how to make vectors like in matlab
like this
coz im trying to get values from 6 to 20
fiery cosmos
vectors as in vectors in c++?
stable pecan
In [1]: import numpy as np
In [2]: np.linspace(6, 20, 15)
Out[2]:
array([ 6., 7., 8., 9., 10., 11., 12., 13., 14., 15., 16., 17., 18.,
19., 20.])
ohh okay
fiery cosmos
oh that seems like
list(range(6, 21))
fair summit
you can use np.arange if you get tired of specifying the number of element
stable pecan
yeah, arange is simpler for this case
burnt hill
yeah i think so
stable pecan
In [3]: np.arange(6, 20)
Out[3]: array([ 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19])
the end is non-inclusive like python ranges though
burnt hill
im trying to pratice python on hackerRank lmao
stable pecan
so keep it in mind
burnt hill
thnxxx
stable pecan
you can add/subtract/multiply/divide arrays
is why
In [4]: np.arange(6, 20) * 2
Out[4]: array([12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38])
this doesn't work with lists
will, you can multiply lists, but the result is not the same at all
burnt hill
wait if i do an if statement that check that equality of a number to a list does it check every value of that list?
like
burnt hill
ohh okay
fair summit
oh wait i completely misread
check that equality of a number to a list does it check every value of that list
that would be how it is done for numpy arrays, for lists it would check that it is a similar-looking list
[0, 1, 2, 3] == list(range(4)) # True```ohhh
stable pecan
you'll just get a boolean mask with numpy:
In [7]: 5 == np.arange(20)
Out[7]:
array([False, False, False, False, False, True, False, False, False,
False, False, False, False, False, False, False, False, False,
False, False])
lunar jacinth
hey could someone help me with implementing an algorithm using linked lists and stack?
i got the files for them both made already, no error code
i just need some help testing it
so if someone can, ill post my code in here
vernal venture
oblique panther
@lunar jacinth it's best to just ask your question. The question itself is the most useful information for deciding if one knows how to answer it.
agile sundial
nice that you gave a link to a resource for Java
round acorn
heyyy is c++ better or python .
oblique panther
@round acorn that question isn't on-topic for this channel, however Python is the greatest programming language and thing ever created.
kind sparrow
Hey anyone knows a library to optimize a matrix using constraints?
fiery cosmos
What do you mean by optimize a matrix?
kind sparrow
I need to find a binary matrix that minimizes a sum of squares of a product that is a vector
Min Sum_squares(Ax-b)
With some constraints
In the A matrix
fiery cosmos
I think this is like
Ax - b = zero matrix
kind sparrow
x and b are fixed
Not really
Constraint is that each A's column is one
So it's not possible to get zero
b is composed by floats
And the rest are integers
fiery cosmos
Okay so do you need to find such A which makes that result minimum?
fiery cosmos
After doing Ax-b do you get a single continuous value?
kind sparrow
Ax-b is a vector
Composed by floats
That's is why I am minimizing sum_squares(Ax-b)
fiery cosmos
Aha this seems smth related to calculus
In particular if I am right a gradient descent algorithm can help you
kind sparrow
It is a linear programming problem
I am tied to use integers
I tried doing what they suggested
But it doesn't work
So I am looking for a new library
fiery cosmos
For linear programming?
vocal gorge
That's what I got from googling python mixed-integer solver
looks like an established library
@kind sparrow
kind sparrow
Thanks I am gonna try it
gleaming badger
guys how do i split this string so that exp will be intact like this:
['5','+','exp','3','/','2']```
worldly mural
use list splicing
gleaming badger
ill try that, thanks mate
fast arch
can someone suggest good resource for learning data structure & algorithms?
fiery cosmos
The almighty CLRS
kind sparrow
Hey
Does anyone knows why I get an Infeasible in optimization status
Please help me
fiery cosmos
This should go to #data-science-and-ml
glossy mulch
i have a quick tiny question
what exactly happens when you do sorted(X) if X is a list of tuples? my intuition and initial findings suggest it sorts by the first entry in each tuple, then the second if equal, etc
but i wasn't able to find documentation on how stable this is
wide prism
tuples are sorted lexicographically (which i think is what you're saying too)
it's mentioned here https://docs.python.org/3/howto/sorting.html
glossy mulch
ah. under #the-old-way-using-decorate-sort-undecorate
thanks, i just stopped reading at stability before
wide prism
looks like it's also mentioned in the built-in types documentation
glossy mulch
does anything bad happen if the second entry is unsortable?
assuming the first items in two tuples are equal
wide prism
it tries to compare them, can't, and you get an error
glossy mulch
sounds like what it would do. i'll stick to lambda e: e[0] then
oblique panther
what exactly happens when you do sorted(X) if X is a list of tuples? my intuition and initial findings suggest it sorts by the first entry in each tuple, then the second if equal, etc
@glossy mulch this is correct.operator.itemgetter(n)is an alternative tolambda x: x[n]
thorny atlas
Hi
oblique panther
@thorny atlas if you have a question about algorithms and data structures, go ahead and ask
rich meteor
@rich meteor https://www.geeksforgeeks.org/multidimensional-arrays-in-java/
@vernal venture Thanks!
fallow tide
Hi ! I have some question on solving Differential equation. I am working to solve an ODE of the form dy/dt=f(y,t), with f a function which depend of combination of sin(y) and polynomial function of t as t*(t-2) but I cannot find any exemple on the web which seems like my question. Is someone can help ?
mellow steppe
h!trick
worn mountain
Hey guys I fear algorithms and have never been able to study or learn them!! Now I understand how big a mistake it is!! How should I start with them and any easy resources that you can point me towards?
oblique panther
@fallow tide if your question is purely about math I would join the math discord
@worn mountain implementing a linked list and knowing the big-O complexity of each operation would be a good place to start.
worn mountain
@worn mountain implementing a linked list and knowing the big-O complexity of each operation would be a good place to start.
@oblique panther I'll start with that thanks man
¯_(ツ)_/¯
@wide prism I have clrs but i find it overwhelming
I got cracking the coding interview by gayle laakman do you think it is a good place to start? or should be referenced and not studied from?
oak obsidian
@gleaming badger
What you want is called a tokenizer
Very important concept for programming languages
wide prism
@worn mountain sorry, i can't comment on ctci
my general self-learning from textbooks advice is to take a couple hours and read a bit of a bunch of them, maybe after getting a short list by looking at reviews, to see what seems to take an approach and speed that appeals to you
btw there's a free course from mit (with video lectures and lecture notes) linked in the pinned posts that you might want to try
worn mountain
That is great advice!! I'll put that to use. And thanks for all the help.
wide prism
np
fallow tide
No it is not a question of mathematics. I am trying to understand how to use odeint. I am close to reproduce the solution that I want. But I don't know why for some initial parameter the result seems to give random values
oblique panther
@fallow tide is odeint a python library? if you're working with python code I'd post some sample that's relevant to what you're trying to do.
glossy mulch
another quick question- how safe / dangerous is object function calling in a list comprehension?
if some object has a variable, and edit(self, x) alters the variable...
i would like to write:
[object.edit(3) for object in things]
will this work, or will some strange memory problem emerge? no new space is being taken up or freed by the edit function.
i have tested this briefly in code and it appears to work, so if nobody contradicts, i'll move forward with that
distant sierra
I'm trying to plot a basic mean squared error one-variable cost function.
Below is my code for calculating the array of costs. How can I vectorize it with numpy and get rid of the for loops?
def calc_cost(x, weights, y):
costs = np.zeros(len(weights))
for i in range(len(weights)):
total_err = 0
for j in range(len(y)):
total_err += (np.dot(weights[i], x[j]) - y[j]) ** 2
print("total err:", total_err)
costs[i] = total_err / len(y)
return costs
I tried using np.mean() to shorten it, but I still don't know how to eliminate the for loops:
return [np.mean([(np.dot(weights[i], x[j]) - y[j]) ** 2 for j in range(len(y))]) for i in range(len(weights))]
flat sorrel
@glossy mulch It works but not very good coding practice especially if object.edit doesn't return anything. A for loop would be more explicit in showing that the function has side-effects
@distant sierra Use newaxis to add the j axis to the weights and the i axis to x and y, then you can use the vectorized ops via broadcasting
glossy mulch
i do understand that. the test returned a list of Nones, though i'm mainly worried about computation time. I have to compute hundreds of thousands of these operations, and it usually takes about 10 seconds each time.
though i'm probably only saving time by not having them return things, and whether it's a for loop or a list comprehension doesn't matter nearly as much as that, yes?
flat sorrel
not sure, I guess you can time that
distant sierra
o
flat sorrel
If you're really concerned with computation time you might want to take a look at Numba @glossy mulch
This depends on what your code looks like, if your code is numerically orientated (does a lot of math), uses NumPy a lot and/or has a lot of loops, then Numba is often a good choice.
distant sierra
im fairly new to this stuff, is there any way u can elaborate?
flat sorrel
are x, weights and y all 1-D?
what are their shapes?
The reason being that you're using np.dot
distant sierra
x is a 2d array of shape (a, 2)
weights is a 2d array of shape (b, 2)
y is a 1d array of size a
where a and b are some numbers and b > a
oblique panther
@glossy mulch there might be some edge case I'm not aware of but a list comprehension should do everything it would do if it were a regular for loop. However I never use for loops for a side effect because I want people who read my code to see a list comp and know "he's transforming a list into another list"
there's also a got-ya if you're in the mindset of using list comprehensions as a shorthand for a "for loop that does something"
namely generator expressions. If you have a list comp but with parens instead of square brackets, you're not making a tuple, it's a generator. so the iterations won't happen right away.
flat sorrel
def calc_cost(x, weights, y):
weights = weights[:, np.newaxis] # Shape: (b, 1, 2)
x = x[np.newaxis] # Shape: (1, a, 2)
y = y[np.newaxis] # Shape: (1, a)
weighted_x = (weight * x).sum(axis=-1) # Shape: (b, a)
return ((weighted_x - y) ** 2).mean(axis=-1) # Shape: (b,)
@distant sierra
flat sorrel
np
primal dock
can someone confirm if i have the right idea about heapq runtimes?
heapq.heappush log n
heapq.heappop log n
heapq.heapify n
heapq.heappushpop log k?
heapq.heapreplace log k?
fiery cosmos
In general what we desire is "yes" but idk about python
I hope they have something like this page
http://www.cplusplus.com/reference/map/map/insert/
Which has complexity along with method
fallow tide
@oblique panther yes it is with python from the scipy library. it could be nice if I can have some sample to compare with.
undone hemlock
Hi, I'm new to python and I'm looking for someone willing to help me for a small task
fiery cosmos
@undone hemlock Sure if its related to algorithm and data-structures post it here else #python-discussion would get you more answers
undone hemlock
Thank you 🙂
burnt hill
hey guys
how do i check if a list has the same element of another list
for ex
[1, 20, 30]
[1, 90, 40]
how do i make it return a repeating value like 1
or get a boolean value if it has a repeating value
sorry im still new to python xD
fiery cosmos
for el in a:
if el in b:
# el is in both a and b
this is O(n^2)
if you need still faster use hashmap
wicked pebble
Hi, this may be kinda unrelated but would there be a way to improve this code? The question is in the code
'''
The first two consecutive numbers to have two distinct prime factors are:
14 = 2 × 7
15 = 3 × 5
The first three consecutive numbers to have three distinct prime factors are:
644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.
Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?
'''
primes = [2, 3]
factors = {2:(2), 3:(3), 4:(2)}
def factorization(n):
result = []
for i in primes:
if n % i == 0:
result.append(i)
if len(result) == 0:
primes.append(n)
result = [n]
factors[n] = tuple(result)
if len(factors[n]) == 4 and len(factors[n - 1]) == 4 and len(factors[n-2]) == 4 and len(factors[n - 3]) == 4:
return (n - 3, factors[n - 3]), (n - 2, factors[n - 2]), (n - 1, factors[n - 1]), (n, factors[n])
else:
return 0
n = 4
while factorization(n) == 0:
n += 1
print(factorization(n))
btw, the answer is:((134043, (3, 7, 13, 491)), (134044, (2, 23, 31, 47)), (134045, (5, 17, 19, 83)), (134046, (2, 3, 11, 677)))
fiery cosmos
@wicked pebble
- Your factorization is slow
- Why primes are only [2, 3]?
wicked pebble
- hmm.... would there be a better way than dividing the number by all the prime factors(that are smaller than the number)?
- Oh it's because the list keeps expanding itself(append a number) whenever it finds a number that cannot be divided by any number in the list.
And to be clear it's not exactly factorization, I just find the prime factors.
fiery cosmos
Here's what I would do
Precompute prime numbers until a N and then I would run the same loop you did at the last and check if the number distinct prime count is 4 and check if number - 1 and number -2 follow the same thing if its true then you have your answer.
The N should be decided, maybe 10,000 is enough I guess
and you can make a hashmap to check to count distinct prime factors of number - 1, and number - 2
like a dictionary or so
and the most important step is precomputing prime numbers until N
Do you know sieve of eratosthenes?
If you are still don't understand I can provide an implementation.
wicked pebble
Hmm... thanks for the help. I'm not sure I understand.. could you give an implementation? Also how would I decide N? The answer is like 134044 so 10000 won't be enough..
fiery cosmos
Sure
No I mean primes below 10,000 would suffice
@wicked pebble https://paste.ubuntu.com/p/7Bh35Ncd74/
you can search for sieve of eratosthenes in python, they explain better than me :)
also that program is slow because of N which we assumed to be 10,000
you can plug some small values and see if it still works
it works for 750 too
so that is a massive time reduce
wicked pebble
ooh, that's a big decrease in runtimes
fiery cosmos
yes I don't know so I start by assuming big number
wicked pebble
works for 700, only 1.3 seconds
fiery cosmos
yep you can do a binary search to get the right number
but assuming a bit big never hurts 🙃
not 10,000 but 1000 or 2000
wicked pebble
Ok, thanks a lot! I could probably use a learning rate(?) or something to increase the N automagically if the number of consecutive numbers needed gets bigger
Thanks a lot!
fiery cosmos
be sure to check sieve of eratosthenes
cinder rivet
What does the integer n have to do with this? Am I meant to put it into the list as well?
cinder rivet
ok
ty
I'm not sure why theirs is taking 12 swaps and mine is taking 8.
def insertion_sort(a: list) -> int:
"""Returns the number of swaps performed by insertion sort algorithm on list a"""
swaps = 0
for i in range(2, len(a)):
k = i
while k > 1 and a[k] < a[k-1]:
swaps += 1
a[k], a[k-1] = a[k-1], a[k]
k -= 1
return swaps
a = [6, 10, 4, 5, 1, 2]
print(insertion_sort(a))
>>> 8
Looks like the list isn't fully sorted...
That's probably why lol
drifting ore
product(range(n), repeat=d)
Does anybody know whether there's a variant of this that only gives combinations up to renamings?
I.e. it should give me [0,1,2,1] and [1,2,2] but it shouldn't give me [0,2,1,2] since that's just a renaming of the first one.
stark bluff
Basic question guys. Is it possible to parse and modify a JSON file with python so I reduce this big ass JSON file to only the information I need for further use? It contains a lot of data I dont need. How would you do this?
drifting ore
I mean you can of course write a loader and specify a list of keywords that you want to allow and then filter it like this recursively.
I imagine it will look something like
def dict_filter(x):
WHITELIST = ["foo_key", "bar_key"]
return {k : dict_filter(v) for k, v in x.items() if k in WHITELIST} if type(x)==dict else x
Somehthing like that.
cinder rivet
Looks like I have to do while k >= 1 instead of what they had in the pseudocode which was while k > 1. Either the pseudocode is wrong or I'm interpreting it wrong.
fiery cosmos
@cinder rivet the pseudocode assumes 1 indexing
cinder rivet
I see...
cinder rivet
1 indexing in programming
fiery cosmos
yes professors dont want to use 0-indexing
cinder rivet
why tf not
cinder rivet
Then their students get to the real world and they're fucked.
cinder rivet
I'm trying out merge sort now using a recursive method. This one isn't behaving how I expect it to.
def merge_sort(a1: list, a2: list) -> list:
"""Returns a sorted list of all of the elements from a1 and a2"""
if a1 == [] and a2 == []:
return []
elif a1 == []:
return [a2[0]] + merge_sort(a1, a2[1:])
elif a2 == []:
return [a1[0]] + merge_sort(a1[1:], a2)
else:
if a1[0] < a2[0]:
return [a1[0]] + merge_sort(a1[1:], a2)
else:
return [a2[0]] + merge_sort(a1, a2[1:])
I'm pretty sure that I have my base case and recursive cases set up correctly. But when I try to say print the length of a merged array, it just doesn't print anything.
Even when I try to print the type of the merged array, nothing is printed.
fiery cosmos
I don't think this is merge sort
cinder rivet
I'm trying to implement this idea.
fiery cosmos
ah yes well I was confused caue you use merge sort as function name
cinder rivet
Because I'm merging the arrays?
fiery cosmos
nah that's not merge sort lol merging is a part of it
cinder rivet
Well I think I'm merging them one element at a time.
Like the next element in the new list is always the smaller of the elements a1[0] and a2[0].
cinder rivet
hmm
fiery cosmos
did you forget to call the function?
cinder rivet
That's strange. I get expected outputs when
a1 = [2, 4, 10, 18] and
a2 = -5, 11, 12
But I have to merge these two fairly large arrays from a text document.
I don't think I can upload it directly.
sec
I can't even use paste.pythondiscord because it's too long.
fiery cosmos
wait are arrays A and B sorted?
cinder rivet
ya
fiery cosmos
well then you are implementing the merge part of the merge sort
cinder rivet
You can download a similar dataset from here.
http://rosalind.info/problems/mer/
Note that lines 0 and 2 are the lengths of the arrays.
So you have to process the data a bit to get it into working form.
fiery cosmos
C = []
i = j = 0
while i < len(A) and j < len(B):
if A[i] > B[j]:
C.append(B[j])
j += 1
else:
C.append(A[i])
i += 1
while i < len(A):
C.append(A[i])
i += 1
while j < len(B):
C.append(B[j])
j += 1
I'm not really looking for a different way to do it. I just want to know why my way isn't working.
cinder rivet
Oh that's a good idea.
Here I am processing the data.
Everything is behaving as expected. This leads me to believe that the problem doesn't lie here.
read_file = open("rosalind_mer.txt", "r")
lines = read_file.readlines()
a1 = lines[1]
a1 = a1.split(" ")
a1 = [int(e) for e in a1]
print(type(a1))
print(len(a1))
print(a1[0])
a2 = lines[3]
a2 = a2.split()
a2 = [int(e) for e in a2]
print(type(a2))
print(len(a2))
print(a2[0])
read_file.close()
Here is my full code.
https://paste.pythondiscord.com/odehusagon.py
See if you can get it to work on the large dataset.
fiery cosmos
I think you need to write the answer to the file
acc to the paste you provided
and your code seems fine to me
cinder rivet
Well I can't write anything to the file if there's nothing to write. Like I can't even print the merged array.
Or even any element of it
fiery cosmos
did you try on local computer?
fiery cosmos
not on that site
fiery cosmos
🤔
fiery cosmos
cinder rivet
Yeah mine works on those small arrays as well.
Have you tried it on the large arrays?
fiery cosmos
well where can I download the data
It says I need to solve insertion sort to solve the current problem :/
cinder rivet
I said that you can download a similar dataset on the link that I posted.
oh rip
one sec
Can I DM you the text file?
fiery cosmos
👍
cinder rivet
Recall that line 0 is the length of the first array, line 1 is the first array, line 2 is the length of the second array, and line 3 is the second array
split nymph
# Impement radix sort
# Input is a list of vectors, and an integer n, the number of vectors in the list
# Each vector is a list of digits
# Every vector is the same length
# Sort ascending
def radixSort(n, vectors):
for i in vectors:
arr = vectors[i]
max = max(arr)
exp = 1
while max/exp > 0:
arr = countSort(arr, exp)
exp *= 10
return vectors
def countSort(arr, x):
n = len(arr)
out = [0] * n
count = [0] * 10
for i in range(1, 10):
count[i] += count[i-1]
i = n - 1
while i >= 0:
index = (arr[i]/x)
out[count [int ((index) % 10) ] - 1 ] = arr[i]
count[int((index) % 10)] -= 1
i -= 1
for i in range(0, n):
arr[i] = out[i]
return arr
# DO NOT EDIT THE FOLLOWING CODE
vectors = [
[3,3,3,3,3,2,2,2,2,2],
[2,3,2,2,2,2,2,2,2,2],
[1,3,0,0,2,1,0,0,0,0],
[1,3,0,0,2,1,0,0,0,0],
[2,3,2,1,2,2,2,2,2,2],
]
sortedVectors = radixSort(5, vectors)
for vector in sortedVectors:
The error it's giving me is
Traceback (most recent call last):
File "C:/Users/Patrick/Downloads/Q1.py", line 52, in <module>
sortedVectors = radixSort(5, vectors)
File "C:/Users/Patrick/Downloads/Q1.py", line 13, in radixSort
arr = vectors[i]
TypeError: list indices must be integers or slices, not list
What can I do to fix this?
fiery cosmos
@split nymph you wrote
for i in vectors
instead you wanted to write
for i in range(len(vectors))
stable pecan
alternatively, just do for arr in vectors: and you won't need the assignment
icy ivy
anyone good with set algebra?
oblique panther
@icy ivy go ahead and ask your question
worst case, no one here knows the answer, but you have it written down
oblique panther
you'll have to tell me what superscript C means in this context
icy ivy
it means its complement
oblique panther
alright, so if A is a set, then A^c is "everything that is not in A", yes?
icy ivy
that is correct
oblique panther
Alright. I'll go ahead and solve it and tell you if I got the same answer
icy ivy
thank you
oblique panther
(but if I got a different answer, I won't necessarily tell you what I think it is)
icy ivy
that is quite ok with me
mint jewel
I concur with A^C
icy ivy
Thanks @mint jewel
fiery cosmos
I think that is correct
icy ivy
thank you
fiery cosmos
Doing it the venn diagram way seems easier
oblique panther
That's what I got too
"A union compliment of A" is just the universe
the intersection of the universe and something else is just that something else
mint jewel
U is union afaik
oblique panther
if we pretend that ~ is a compliment operator
A & ~A would be the empty set
right?
mint jewel
ye
icy ivy
that is correct
oblique panther
and then we're taking the intersection of that and something else, right?
icy ivy
its 0 nothing
oblique panther
which would idempotently be the empty set also
oh no it's union in the problem
the union of the empty set and something else
@main wigeon please don't advertise a help session in other channels. If someone is available, they'll come to you
unless there's some other context I'm missing
anyway
icy ivy
could i ask one last question
for part ii. of that last image i sent i ended up with ~Q
I did DeMorgans Law then double negation flipped the signs and the absorption law
wide prism
what are you trying to do with it? just find an equivalent simpler version? there is a valuation with Q true (set P to true as well)
~Q does satisfy the formula, though
icy ivy
I am just trying to simplify it to smallest terms so id be using as little as logic gates as possible
wide prism
you can push the negations in repeatedly to get (P ^ Q) v ~Q
i guess i'm not sure if that's the formulation with the fewest connectives without thinking about it some more
icy ivy
right i ended up with that after i did the double negation
(P ^ Q) v ~Q can you do the absorption law from here?
wide prism
seems like a good bet that it's simplest but i'm not sure how to show that without "manually" checking equivalent formulas
also depends on your language, if you don't have nand/nor/xor/other funny connectives i'm more confident
wide prism
np
fiery cosmos
guys any expert can tell me how come performance is instant when i remove condition ffom my code
but when i add a filter ( if ) it takes 5 minutes for the same task
i bet the smartest person here won't figure it out lol
because it makes no sense
fiery cosmos
for user in ulist:
for password in plist2:
passwd = plist2.get(user[0].lower())
if user[1] != '':
text=.....
break
break exists the innermost loop
fiery cosmos
i'm on my phone sry
fair summit
without a condition, it only gets the first element in plist2
fiery cosmos
not that condition
fair summit
if you had the condition, it no longer easily hit the break
that's the only condition you code has
fiery cosmos
when i add anything about passwd in the if
like if .. and passwd
it just takes 5 minutes
fair summit
yeah, same concept really
fiery cosmos
the one i posted is instant and outputs all 75k list
and it's correct list
same as the one that takes 5min
but i figured right now that the issue could be from password as it's not a used loop
so it's useless loop
as i'm using dict instead of if loop
it's so fast to search. too op
if loop takes 5 minutes while the dict takes like 3 seconds
fair summit
yes, because lookup takes constant time on average for dicts
whereas for lists, you have to iterate through the whole thing
fiery cosmos
thanks tho 😘
split nymph
@fiery cosmos @stable pecan Thank you both for your input, I was able to get the right solution because of it
Hate to continue the problem but do either of you by chance know how to do it with bucket sort instead of count sort?
junior granite
hello
can someone help me with Binary Trees/ maneuvering around a Binary Tree, please PM me
vernal venture
@junior granite I can help if you want
oblique panther
@junior granite go ahead and ask your question in the chat
lethal grotto
Ok, so this may be a noobie question, but is there anyway I can make a simple little database with lists?
not like too serious, just trying to see if there is a simple way to create one, or if I'll have to bee a little more advanced.
flat sorrel
you'd need classes at the very least, a basic list won't exactly qualify as a database
lethal grotto
Ah, I got you, just wondering, thank you for the information! Have a great rest of your evening.
oblique panther
@lethal grotto a dict of dicts might be an easier way to do that
pearl thorn
How can I find the recurrence of such an equation? I'm a little confused as to where to start especially if I'm not given a base case (such as if T(1)=1)
snow swift
wait how do you do it without a base case
oblique panther
@snow swift I think the base case is when n is 0
zinc tapir
Python allows negative integers to be used as indices into a sequence, such as a string. If string s has length n, and expression s[k] is used for index −n ≤ k < 0, what is the equivalent index j ≥ 0 such that s[j] references the same element?
agile sundial
why did you subtract 2
modest wasp
Couldn’t get help in general so now Im in here. What’s the purpose for {value:width.precision f}? Is it useful. I’m learning rn & I don’t get it.
zinc tapir
@agile sundial 0 > j > n
Couldn’t get help in general so now Im in here. What’s the purpose for {value:width.precision f}? Is it useful. I’m learning rn & I don’t get it.
@modest wasp
in what context ?
modest wasp
Float formatting.
zinc tapir
yes it's usefull
oblique panther
@modest wasp this question isn't on topic for this channel. Take a look at #❓｜how-to-get-help
oblique panther
@zinc tapir is who I should have pinged
Sorry, I'm clearly confused. Though my earlier point stands.
zinc tapir
Python allows negative integers to be used as indices into a sequence, such as a string. If string s has length n, and expression s[k] is used for index −n ≤ k < 0, what is the equivalent index j ≥ 0 such that s[j] references the same element?
@oblique panther my answer is 0 > j > n
is this correct?
agile sundial
no it is not correct
oblique panther
Isn't it basically asking,if a[n] is a character of a string and n is >= 0, what negative integer is for the same index?
agile sundial
yeah, you want to find a negative index so that you get the same char as a positive one
oblique panther
Do you get to know the length of the string?
agile sundial
yeah that's n
oblique panther
I'm not really sure how to guide them to the answer without giving it away
@oblique panther my answer is
0 > j > n
@zinc tapir this is a comparison but I believe the question wants a formula
Look at the variables the question gives you
How would you solve for j?
What about specifically for k = -1
zinc tapir
@zinc tapir this is a comparison but I believe the question wants a formula
@oblique panther i m thinking the same
oblique panther
That would give you the last char
burnt hill
guys if an input is recieved does it treat it as a string if u put it into a variable?
fiery cosmos
yes
burnt hill
oki thxx
oblique panther
@zinc tapir j is the number you're solving for but in your solution you're defining it in terms of itself
zinc tapir
n = [1, 2, 3, 4, 5]
k = -2
print('n[k]: ', n[k])
j = k + len(n)
print('n[j]: ', n[j])
@oblique panther is this okey?
oblique panther
@zinc tapir here are your variables:
k = a negative integer
n = the length of the string
j = 0 or a positive integer
the answer needs to be j = ...
anything else is extra
zinc tapir
j = k + n
oblique panther
Not quite
Actually yes, I was just thinking of it with absolute values
yay!
The way you can remember, Guido says that s[-1] should be thought of as s[len(s) - 1]
zinc tapir
s[j] == s[j-n]i had done same thing here but i converted it to
k
The way you can remember, Guido says that
s[-1]should be thought of ass[len(s) - 1]
this is reverse of what i was doing
oblique panther
@zinc tapir why did you switch from k to j on the right? s[j] == s[j-n]
zinc tapir
@oblique panther dude you deleted my msg too
icy ivy
I have a word problem for you all which involves Counting
The delivery truck driver union is concerned that the workload is unequal. How many ways can 120 IDENTICAL packages be loaded into 10 delivery trucks where each truck must have at least 5 packages
icy ivy
anybody any thoughts?
icy ivy
I ended up with 59!/ 50! 9!
fathom saffron
yea
but then you have to add 5!
since you can rearrange the 5 packages that each of them have
i think
actually my answer would be 79 C 9 + 5!
which is 79!/70!9! + 5!
im not too good
so im probably wrong
icy ivy
haha no no i appreciate all help
fathom saffron
so what was the answer
icy ivy
so the 79! where did that come from
fathom saffron
because if each truck already has 5 packages that means that 120 - 50
70 packages are left to give out
gleaming badger
mubix hahah here we meet
icy ivy
right but then its identical so you have to do the balls and bins method
fathom saffron
yea
icy ivy
which is k+n-1/k
fathom saffron
/k?
if you have 7 apples and 3 people
you can give it like 10 choose 2 ways
using sticks and stones
icy ivy
so 50+10-1 which is 59!
fathom saffron
yea but why 50
50 is already determined
you can just rearrange them using 5!
all trucks need to have at least 5 packages
icy ivy
i got 50 from subtracting 70-120
fathom saffron
why would you subtract 70 from 120
icy ivy
because each package is identical and there are 120 of them
to be loaded into 10 delivery trucks with 5 packages
fathom saffron
yes but if you use sticks and stones for fifty packages you will overcount
since in some cases the trucks may not have 5 packages
icy ivy
well what if you assign every truck 5 packages out of 10
icy ivy
70+10-1
fathom saffron
yea
icy ivy
79!
fathom saffron
ummm
icy ivy
let me see what i get
icy ivy
well thanks again for your help
i got everything i just dont understand why you add 5 at the end
fathom saffron
because you can rearrange the last 5 packages
the packages that are given at the beginning
you can rearrange those
so you get 5!
frozen ermine
hey everyone, i've been tasked with taking a string, splitting it into a list of words in each string, extracting the second letter of each word, and then joining all those letters together
silly = 'newly formed bland ideas are inexpressible in an infuriating way'
bland = [silly.split()]
that's what i have so far
i'm having a hard time writing the list comprehension to get me the second character in each word in bland
when i write secondletter = [w[1] for w in bland], that just gives me the second word in bland, rather than the second character of each word in bland
wide prism
you almost have it
silly.split() gives you a list of words
you want to look at each word in that list and take the second letter, so you want a list comprehension that looks at that list of words, and does something for each word in that list
then you can join them all together
so: ''.join(w[1] for w in silly.split())
@frozen ermine
frozen ermine
thank you @wide prism i guess i don't need the bland variable at all then
gleaming badger
s = 0
i = 1
while True:
i *= 2
s += 1
if i >= N:
break
return s```
can someone tell me the time complexity for this one?I was thinking it was squred root of N
gleaming badger
oh i see
thanks mate
for i in range(N):
A[i][:i] = [0 for _ in range(i)]
return A```anyway u could help with this one as well?
oblique panther
@gleaming badger what question do you have about that?
you just want to know the big-O complexity?
fair summit
yes it's O(log2 N)
oblique panther
@fair summit shouldn't they get a chance to figure that out?
fair summit
oh i was referring to the one above that was first posted (and already answered)
oblique panther
ah
fair summit
i didn't even see they re-asked a question either lol
wraith valve
its a divide and conqure alg
i cant spell
but anyways
u split the problem into 2 sub problems
and then u reassemble
the 2 sub problems back together
so basically u would continue to make a recursive call until the problem size is 1
since the problem size is one, u know that subproblem is sorted and then u gradually build it back up by reassembling 2 done sorted subproblems together until u reassembled it back to a size of n
wraith valve
tbh most ppl do it half way
fair summit
anywhere, as long as its in 2 equal (+- 1 element) lists
fair summit
the only thing you need to check is the base case, in the case of merge sort, if your array is empty
wraith valve
def merge(my_list):
if (len(my_list==1):
return my_list
else:
midway = len(my_list)/2
first_half = merge(my_list(0:midway))
second_half = merge(my_List(midway:len(my_list))
result = combine(first_half, second_half)
return result
ill prob look something like this
fair summit
that's closer to a quicksort
wraith valve
where combine is a function that will combine the two lists in order
fair summit
oh wait no there's no pivot for splitting i'm dumb
fiery cosmos
So where is the sub programs in your code
wraith valve
the "sub problems" are the recursive call
each recursive call is on a size that is n/2
so u end up having 2 sub problems each of size n/2
once u solve the two sub problems of size n/2 (sorted them) u reassemble with combine to make it back into a solved problem of size n
fiery cosmos
Aha i got ut now
wraith valve
and combine is a function that will loop through the two each time placing the smallest of the front of the two lists into a new list
fiery cosmos
Each recursive call is on division
wraith valve
basically
the recursive call makes the problem smaller
by a factor of 2
until u get to size 1
which is the base case
once u are there u solved that subproblem
and u can now return and reassemble
wraith valve
np
usually u should trust the natural recursion
it makes wrapping ur head around recursive calls easier
fiery cosmos
Recursion is one of the methids of duvide and conquer alghorithms?
wraith valve
well u do have a recurance relationship
so basically yeah cuz u make the problem size smaller to solve the bigger problem
so u have something like T(n) is related to something previous to it like T(n-1) or something
manic pilot
how do i count the number of countries without looping the same name?
fiery cosmos
Group by function
wraith valve
i was thinking about pushing them all into a set
but then u still gonna have to go through all ur entries
i dont think u can get a runtime better than linear
manic pilot
ok thanks guys
ionic dove
hey all I'm attempting to solve the first challenge in LeetCode (TwoSums), but fail the submission keeps failing 1 test case and it does so due to (Time Limit exceeds).
I am attempting to track the code to see how I can optimize it further but cant seem to arrive at any solution the runtime of the current code should be O(n^2), any guidance would be much apprecited.
def twoSum(nums, target):
list_length = (len(nums) -1)
newNums = []
for i in range(len(nums)):
for j in range(len(nums)):
if i == list_length:
break
if nums[i] + nums[j] == target and i != j:
newNums.append(i)
newNums.append(j)
return (newNums)
if j == list_length:
j = 0
Okay so what you are doing is running over two loops for i and j such that nums[i] + nums[j] == target right? @ionic dove
ionic dove
yes if nums = [1,2,3,4,5] and target = 7 the goal would be index (2,3) which is (3 and 4 respectively)
then i = 0 and j goes through the list j = 0,1,2,3,4 looking for summing up each one searching for the target
then i =1 and j hoes through the list j=0,1,2,3,4 and so on
that should be the only solution I feel
fiery cosmos
Okay now lets say you are solving a + b = c
ionic dove
alright
fiery cosmos
If you know a and c can you get what b is?
ionic dove
correct
fiery cosmos
which means b = c - a right?
fiery cosmos
now you are running a loop over the nums list
for a in nums:
b = target - a
# How to check if b is in nums?
How quick you can check if b is in nums
fiery cosmos
Can you make it O(1)?
ionic dove
Oh
fiery cosmos
think how you can make it O(1)
ionic dove
alright will searh for a bit and get back to you then
fiery cosmos
Spoiler if you do not know this term already || hashmap ||
what is this?
#algos-and-data-structs message
Starts from here.
ohk
ummmm
i dont get it
whats this append?
ionic dove
I see not familiar with hasmaps will have to brush up on it. So theoratically I can make the runtime O(n) by b = target-a and making sure it results in a int of 0. Looping through the list only once.
@fiery cosmos the append is there for LeetCode submission they needed the output to be [1,2] and I could only think of printing out a new list
fiery cosmos
Yes you only loop once and making the check whether b is present in nums in O(1)
no im asking what does this append do?
So total time complexity O(n)
idk what it is
which should pass the judge.
ionic dove
@fiery cosmos well it simply appends (adds) a number to the list I created.
nums = []
nums.append(1)
# now nums = [1]
nums.append(2)
# now nums = [1,2]
ohhh
thnx
i get it now
so it only adds to a list?
and can it remove a num from it?
ionic dove
alright @fiery cosmos I have one final question. How can I deduce a in this case. Am I selecting a at random. I would have to iterate through the list to find a int that would make b 0 by b = target -a
fiery cosmos
You are just iterating through elements in the list in order
Since you want indices too what you can do is
for i, a in enumerate(nums)
i is the position and a is the value
k i'll ask in general
np
ionic dove
@fiery cosmos sorry forgot myself, should be easily avaialbe to search up though!
brave swift
Is there way to use bitset data structure in python?
fiery cosmos
Like in C++?
ionic dove
@fiery cosmos hey just wanted to say that I'm pivoting the solution a little. Will have to study hasmaps before I implement them so another user suggested an alternative and I came up with this
with each looped iteration of j it would be as follows
num = [1,2,3,4,5] and j iterates as follows i = 0 and j=0,1,2,3,4
2nd iteration would be i = 1 and j=1,2,3,4
3rd iteration would be i=2 and j=2,3,4 and so one
it'll still be O(n^2) but LeetCode should accept the submisison then once I'm faimiliar with hahmaps will return to optimize it further
anyways thatnks a bunch @fiery cosmos I appreciate the help!
fiery cosmos
👍
fervent quiver
Could someone explain why linked lists are better for insertion and deletion than the tree data structure?
Or does it depend if the linked lists are ordered/unordered and the tree is balanced/unbalanced?
oblique panther
@fervent quiver sure, which one do you want to talk about first?
I guess the first part
trees and linked lists do different things
they're both very useful, but neither is meant to solve exactly the same problems as the other
fervent quiver
yea, trees are generally better for searching, but idk why they're saying linked lists are faster for insertion and deletion
oblique panther
however, it's true that appending to a (doubly) linked list is a lot faster than adding to a tree
"better" isn't the right term, I don't think
fervent quiver
right, faster
fervent quiver
I fairly know both of them, just dont know why they're considered faster in terms of deletion/insertion than trees
fiery cosmos
Searching in trees can be done in O(log n) idk how you can do faster than this in linked lists
tardy scarab
How to prove language { 1^p | p is prime} is not a regular language without using the pumping lemma ?
oblique panther
@fervent quiver searching a linked list is slower than a tree
@tardy scarab if you don't get an answer, try the computer science discord
fervent quiver
sorry, my bad it's supposed to be insertion/deletion
oblique panther
@fervent quiver is that insertion within the list? not to the front or end?
tardy scarab
@tardy scarab if you don't get an answer, try the computer science discord
@oblique panther Ok bro thanks
fervent quiver
within the list
oblique panther
what do you think is the big-O complexity of that task?
fervent quiver
O(Logn)?
oblique panther
@fervent quiver why
fervent quiver
if its avl/BST it would be O(Logn), but if its unbalanced then it would be O(N) I think
oblique panther
I asked about insertion to a linked list
tardy scarab
insertion to a linked list is O(n)
oblique panther
@tardy scarab please don't give away answers. I'm trying to help them really learn the material.
tardy scarab
@tardy scarab please don't give away answers. I'm trying to help them really learn the material.
@oblique panther Oh sorry bro
What is Computer science discord channel id?
oblique panther
fervent quiver
its O(n) for linked list cause of the pointers right?
oblique panther
you're on the right track, but a lot of things in programming are because of pointers 🙂
@fervent quiver what are you thinking?
fervent quiver
tbh, Im still out of ideas.
oblique panther
@fervent quiver if we were irl I'd write it out for you on a white board. let's see if there's a good youtube video.
fervent quiver
@fervent quiver if we were irl I'd write it out for you on a white board. let's see if there's a good youtube video.
@oblique panther thanks, Im currently researching about it atm
oblique panther
@fervent quiver I can't find a good animation that illustrates how it works
suppose you had a linked list of ten items
and you want to insert a new element at the fifth index
fervent quiver
yea?
fervent quiver
@oblique panther traverse until the 5th element sequentially using pointers
starting from head
oblique panther
@fervent quiver that sounds good. what would you do once you're at the fifth element?
fervent quiver
the node before the new element(4th element)'s next pointer should be pointed to the new element
same goes for the next node's previous pointer
and the next and previous pointer of the new element should be pointed accordingly as well
oblique panther
@fervent quiver so, update all the pointers. exactly right
fervent quiver
yess
oblique panther
that's it. Get to the right node, and update the pointers so that your new node is in place
So what are the big-o complexities of these two steps?
fervent quiver
O(n)
oblique panther
for both of them?
fervent quiver
O(1)
oblique panther
which is which?
fervent quiver
O(1) for both of them
oblique panther
hmm, you were actually on the right track before
how could "traverse until the 5th element sequentially using pointers" be constant time?
fervent quiver
darn, yea, should be O(n)
oblique panther
exactly
but updating the pointers is O(1)
so O(n) is your performance bottleneck
and that's why insertion into a linked list is O(n)
oblique panther
do you know why it's still O(1) for the whole thing if you're pushing to the front of the list, or appending to the end?
oblique panther
yes, that's exactly right
oblique panther
well, there's a key difference with BSTs
for a linked list, it's just an ordered list. But it's not a sorted list unless you want it to be and do work to make that happen
for a BST, the position of a node in the tree is super important
so you have to do work to make sure everything is getting inserted to the right place
fervent quiver
@oblique panther but if we're gonna compare the speed of these two even though the linked list is ordered, linked lists would still be faster than BSTs in terms of deletion/insertion right?
fiery cosmos
How fast can you delete 5th element in 10-length linked list
oblique panther
@fiery cosmos is that a rhetorical question, or do you want me to answer it?
fiery cosmos
No I was answering to his doubt sorry for the interruption, continue
oblique panther
no problem. we like crowd-sourced help as long as no one is sabotaging the teaching plan of another user
@fervent quiver I'll give you a hint, it's faster to append to a linked list because, well, you can't do better than constant time from a complexity standpoint
but other than that, insertion to a BST is faster
fervent quiver
well, it would only take us two steps to delete 5th element in a 10 length linked list. First one would be traversing it till the 5th element, then fixing the pointers. So all in all that would be O(n) correct?
oblique panther
yes, deleting a node from a linked list is fundamentally the same process as adding one
you're just updating the pointers differently
if you're not working in a garbage-collected language, you also have to ANNIHILATE the node
but that's really just an implementation detail
agile sundial
a n n i h i l a t e
fervent quiver
but other than that, insertion to a BST is faster
@oblique panther could you pls explain why?
oblique panther
@fervent quiver you know how adding a node to a linked list shares a lot of the same steps as looking one up?
it's the same for a BST
unfortunately I can't really illustrate how that well without imagery
fiery cosmos
What you use in BST is a "Binary search" hence Binary search tree
It searches for a element in O(log n) time
lets say you have an array [1, 2, 3, 6, 7]
and you need to find whether 4 is present in it how do you do it?
fervent quiver
check each element in the list
fiery cosmos
yes that's the traditional way which is O(n)
but why did we have "sorted" array does it make some difference 🤔
fervent quiver
so that depending on the value you're searching for, it would be faster to find it?
fiery cosmos
hmm not true, but you use the fact that if you take some index i and check if nums[i] with the element you are searching for how many cases can be there?
fiery cosmos
No I mean like this
- nums[i] == the element you want to search for
- nums[i] is greater than what you want
- nums[i] is less than what you want
do you understand until now?
fervent quiver
Ahh I see
fiery cosmos
either one of those are true right?
fervent quiver
Yes
fiery cosmos
okay if 1 is true then you found your element
if 3 is true, does it make sense to search for elements in [0...i - 1]?
nums[i] < your target
fervent quiver
** [0...i - 1] ** this means numbers above i right?
or from the first up to the last?
fiery cosmos
no I am explaining Binary search in a linear array
lets discuss about bst after this
this is the main part which makes BST special
fervent quiver
nums[i] < your target
@fiery cosmos then yes
fiery cosmos
can you tell me why it doesn't make sense?
fervent quiver
cause the number we're looking for is less than the ones in the end of the list, theres no point in searching the whole list
fiery cosmos
okay let me give the previous example
[1, 2, 3, 6, 7]
here target = 4 and i = 2
now is it "smart" to search in [0..1]
fervent quiver
no
fiery cosmos
why so?
fervent quiver
cause the one were looking for is above 0 and 1
fiery cosmos
No [0...1] means the indices of the array
array = [1, 2, 3, 6, 7]
indices = [0, 1, 2, 3, 4]
now i = 2 and target = 4
is it "smart" to search in [0...1] indices?
are you confused?
fervent quiver
tbh yea
fiery cosmos
okay
lemme finish
[1, 2, 3, 6, 7]
------|------
okay now what can you tell me about left elements of 3?
are they less than or greater than like that
fervent quiver
no
fervent quiver
oh yea, it should
fiery cosmos
and why again 
fervent quiver
all elements on left of 3 is less than 4
fiery cosmos
because the array is ......
fiery cosmos
ordered or sorted?
fervent quiver
sorted
fiery cosmos
right
so if nums[i] < target does it make sense to search for elements to left of nums[i]
you still confused?
fervent quiver
nope
fervent quiver
correct
fiery cosmos
okay so what we do is cut off that left part and search in the right part because we might guess that element "might" be present in the "right" part of array
fervent quiver
yep
fiery cosmos
and what if nums[i] > target
fervent quiver
still shouldn't
fervent quiver
we should search in right
daimkdknasnoadkmdakd
ughh damn, sorry im a bit high now, but im getting most of it
fervent quiver
since our target could be there, we already cut off the left part of the array
fiery cosmos
wait that was when nums[i] < target
- nums[i] == the element you want to search for
- nums[i] is greater than what you want
- nums[i] is less than what you want
1 is simple
3 one is you don't care left
2 one is?
fervent quiver
you don't care right
fiery cosmos
it's actually simple
[1, 2, 3, 6, 7]
------|-----
see this example and tell me
you don't care right
@fervent quiver why
I will suck up all answers from you
fervent quiver
cause if our target is** 2**, while on the right side we have** 6,7** which is greater than what we want, then no point in searching for it
fiery cosmos
yes!!!!
that's what how binary search works
you take mid element and check with the element
and you cut off the part which is not necessary
and you repeat on the left out part
now did you get it?
fervent quiver
Ohh, so that's why it has a time complexity O(n) when it comes to searching
Yess, thank you
fiery cosmos
it doesn't have O(n)
it has O(log n)
its because initially you have whole array of size n
right?
fervent quiver
Oh yea, my bad, looked at the right side
fiery cosmos
n + n/2 + n/4 + ... + 1
| | |
1st 2nd 3rd
it takes exactly log n steps to make that go to 1
fiery cosmos
so if the array was sorted you can make search fast
it works with anything say with BST , some objects sorted according to a rule
you can do this everytime you have something "sorted"
now coming to BST, it is arranged in the following way
The left node is always less than the parent
The right node is always greater than the parent
can you see something similar to binary search in it?
fervent quiver
- nums[i] == the element you want to search for
- nums[i] is greater than what you want
- nums[i] is less than what you want
2 would be the right node
3 would be the left one
and the root would be 1
fiery cosmos
yep it works the same way
now you need to search for 5
starting from 1
where will you go to the right or left?
wait how does that hold
1
/ \
2 3
is 2 < 1?
this is not BST
fervent quiver
yes
cause the left node's less than the root
and the right node's greater than the root
fervent quiver
yes
fervent quiver
go the right child of 32, then the right child of 46. then the left child of 65
fiery cosmos
how did you do it so fast? why did you not go to left of 32 first?
fervent quiver
cause 65 is greater than 32
fiery cosmos
yeah so?
fervent quiver
it should be on the right child
cause right nodes contain something greater than the root
fervent quiver
Thanks for bearing with me!! I got it more clearly now
fiery cosmos
Now read up some material regarding them all the leftover holes will get filled
oblique panther
Computer Science Discord: https://discord.sg/cs
They may be in a better position to help with theory of computation questions.
oblique panther
Computer Science Discord: https://discord.sg/cs
They may be in a better position...
fiery cosmos
I have TOC this semester 😳 . Didn't even listen to one class
oblique panther
@fiery cosmos I hope you like flow-charts
I took theory of computation last year and I described it to my parents as "a flowchart class"
fiery cosmos
also the link is broken discord.gg
oblique panther
it worked for me
fiery cosmos
lmao I joined some random server it is indeed correct
I thought all servers should have .gg
bronze sail
is there some algorithm to find center of mass of white pixels? 😛
wraith valve
from my understanding center of mass is measured from a reference point (although i don't think the choice of reference matters because you will end up having the final value at the same place). one method that I thought about was loading that picture into an 2x2 array, i think pillow or open_cv has a function to do that. Then grab all the coordinates of the white pixels (since its in an array the coordinates are just the index of the array) and then apply the center of mass formula to each individual white pixel and give each pixel a mass of 1 because they are all the same size and their distance would be the euclidan distance using their index values.