the loop fires twice, once with i set to "I", and once with i set to "e"
#algos-and-data-structs
lean dome
lean dome
the first time through the loop, it replaces "**" with "II" and adds that to the list. The second time through the loop, it replaces "**" with "ee" and adds that to the list.
heavy cloak
how am i able to make it replace the elements and rreturn one list
as well as
how do i make it like replace an asterisk for each element in y
lean dome
You're trying to take the string "**" and combine it with the string "Ie" to get the string "Ie"? That's just... always going to be the string "Ie"
heavy cloak
yea but if i have something like "h* th*re" and "io"
i want it to replace the asterisk
s
in the y's order
lean dome
!e ```py
x = "H* thre"
y = "ie"
for character in y:
x = x.replace("", character, 1)
print(x)
halcyon plankBOT
@lean dome :white_check_mark: Your eval job has completed with return code 0.
Hi there
lean dome
!d str.replace
halcyon plankBOT
lean dome
that code is equivalent to: ```py
result = []
for i in 'ae':
result.append('i'.replace('*', i, 1))
print(result)
but i want it to fit in lambda
lean dome
on the first iteration, i is set to "a", and the first 1 * in "*i*" is replaced with "a", adding "ai*" to the list. on the second iteration, i is set to "e", and the first 1 * in "*i*" is replaced with "e", adding "ei*" to the list. Then you print out the list ["ai*", "ei*"]
lean dome
what's that supposed to be? A generator expression?
lean dome
sure - but you can't use for like that. The only times for can ever be used in an expression, as opposed to a statement, are generator expressions and lilst comprehensions.
Just stop trying to make this a lambda, and make it a regular function.
heavy cloak
ok
lean dome
!e ```py
def replace_asterisks(template, replacement_chars):
for char in replacement_chars:
template = template.replace("*", char, 1)
return template
print(replace_asterisks("H* thr", "iee"))
@lean dome :white_check_mark: Your eval job has completed with return code 0.
Hi there
@lean dome
can u test this for me
[x:= x.replace('*', i, 1) for i in y][-1]
oops
censored = lambda x, y: [x:= x.replace('*', i, 1) for i in y][-1]
lean dome
you can test it yourself in #bot-commands
heavy cloak
!e
censored = lambda x, y: [x:= x.replace('*', i, 1) for i in y][-1]
print('H*ell*', "ie")
You are not allowed to use that command here. Please use the #bot-commands channel instead.
lean dome
it won't work; you cannot use the walrus operator in a list comprehension.
heavy cloak
it won't work; you cannot use the walrus operator in a list comprehension.
it did tho
lean dome
hm.. I stand corrected - I didn't think it works, but if it does, it does.
why are you so determined to use a lambda for this, though?
it's so much easier to just use a regular function.
heavy cloak
thats bec its for a challenge
and there are experienced people on the line
who can legit fit ml algorithms inside a lambda
lmao jk
idk
but they put all there submissions in a lambda
its super short
so i wanna be short as well
lean dome
shorter isn't always better.
if someone reads my version, they'll understand what it does right away. If someone reads yours, they won't.
heavy cloak
true
waxen cairn
is there anyone who is familiar with NEAT who can help with some problems i have with the implementation?
storm sparrow
did somebody know what can i do, that this error does not occur?
Code:
datei= json.load(file)
for wort in wörter:
for lu in alp1:
if wort.upper().startswith(lu):
b0 = lu.lower()
for let in alp:
if wort[1:2] == let:
b1 = let
for w in datei["list"][f'{b0}'][f'{b0+b1}']:
if wort == w:
log = client.get_channel(814840272529784832)
await message.delete()
await message.channel.send(embed=embed01)
await log.send(embed=emebed02)```
Error:
```py
File "g:\Programmieren\Python\Discord\Fertiger Bot\bot.py", line 73, in on_message
for w in datei["list"][f'{b0}'][f'{b0+b1}']:
UnboundLocalError: local variable 'b0' referenced before assignment
trim fiber
did somebody know what can i do, that this error does not occur?
Code:
```py
dat...
Your variable b0 sometimes is not initialized, you can call b0 = 0 before both loops for example
jovial scarab
Is there any good DSA COURSE IN PYTHON ?
pure slate
There's two parts to that with one being python syntax in general, and one being ds techniques in general. The first just requires practice^1024, the latter I'd recommend the Computerphile Data Science videos
proud plaza
cool
i love coding
damn this is interesting
imagine going to school with no knowege of coding lmfao
sick dagger
Hi, does someone know if there's an algorithm that gives all the possible ways in a graph from a point A to a point B ?
young remnant
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
import math
answer=[]
for integer in nums:
index=nums.index(integer)
nums.remove(integer)
answer.append(math.prod(nums))
nums.insert(index,integer)
return answer
is this O(n) ?
agile sundial
Hi, does someone know if there's an algorithm that gives all the possible ways i...
just dfs?
@young remnant no
sick dagger
@agile sundial Will it work ?
agile sundial
yeah
young remnant
<@546303787275517954> no
Because of nums.index()?
agile sundial
among other things
trim fiber
Why you don't use enumerate(nums)?
agile sundial
that would cut down on the constant but it would still be quadratic
young remnant
Okay
agile sundial
you've got lots of operations hidden inside function calls
grizzled schooner
insert and remove are also O(n)
young remnant
Oh I removed one of the functions
young remnant
```py
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[i...
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
import math
answer=[]
for index in range(0,len(nums)):
integer=nums[index]
nums.remove(integer)
answer.append(math.prod(nums))
nums.insert(index,integer)
return answer
modified it like this but yeah still this is too long.
trim fiber
```py
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[i...
First of all you can try
for index, integer in enumerate(nums):
...
Secondly you can try to use filter instead of remove and insert
young remnant
okay
agile sundial
filter wouldn't work
young remnant
this is the question which I am trying to do. if you need this.
https://leetcode.com/problems/product-of-array-except-self/submissions/
agile sundial
and you still have quadratic complexity because of remove and insert and product
young remnant
yep 😦
grizzled schooner
you could solve more quickly using some simple math 👀
young remnant
you could solve more quickly using some simple math 👀
you mean by taking a product initially and then dividing it?
grizzled schooner
yeah lol
young remnant
ah it challenges to solve the question in O(n) and without using division.
agile sundial
there's a cool way to do that
young remnant
give some hints?
agile sundial
I can't think of a hint without giving the entire answer 😦
young remnant
hehe ping me if you think of any hint.
glossy breach
Try thinking of prefixes and suffixes
young remnant
I thought of another way.
Creating a dictionary with numbers and their frequencies. then multiplying the frequencies. and the number which has to be omitted will have it's frequency reduced by one.
should I try implementing it? 
young remnant
I thought of another way.
Creating a dictionary with numbers and their frequenci...
@glossy breach sorry for a ping.
glossy breach
I thought of another way.
Creating a dictionary with numbers and their frequenci...
That's a way, but I'm not sure how the time complexity would be O(n)
young remnant
I understood the prefixes and suffixes method.
Thanks everyone for your help.
hollow dove
data="status=123123&coe=3213"
How i can get arguments ?
trim fiber
```py
data="status=123123&coe=3213"
```
How i can get arguments ?
>>> data="status=123123&coe=3213"
... data = data.split("&")
... data = [part.split("=") for part in data]
... print(data)
[['status', '123123'], ['coe', '3213']]
wow .Thx
old rover
def factorial(num):
if num <= 1:
return 1
else:
return num * factorial(num - 1)
can someone do an ELI5 explanation of why num <= 1 is a base case
the base case is so there's no more recursion
so if you put in 3 eventually you will end up with 1
bc of the base case
and then all of it multiplied together is 6
3* 2 * 1 = 6
trim fiber
```python
def factorial(num):
if num <= 1:
return 1
else:
...
You have recursion algorithm so you need to have stop condition. Factorial is a function for n as a neutral number that for given n it returns n * (n - 1) * ... * 3 * 2 * 1.
If you set n as 0 or 1 there should return just 1 so it's why you have return 1
jolly mortar
base case < 1 so that 0! = 1 holds
tbh it should raise a ValueError or smthn for negatives
but eh
trim fiber
tbh it should raise a ValueError or smthn for negatives
Right
old rover
def sum_recursive(n):
if n == 0:
return 0
else:
return n + sum_recursive(n-1)
if you put in 4
it would be 4 + sum_recursive(3)
glossy breach
Indeed
jolly mortar
yep
trim fiber
```python
def sum_recursive(n):
if n == 0:
return 0
else:
return n +...
It's only for not negative numbers
Try to put -1 for example
jolly mortar
infinite recursion for negatives 🥴
glossy breach
sum_recursive(-1) will result in infinite recursion
trim fiber
Yep
old rover
confusion
jolly mortar
sum_recursive(4)
= 4 + sum_recursive(3)
= 4 + 3 + sum_recursive(2)
= 4 + 3 + 2 + sum_recursive(1)
= 4 + 3 + 2 + 1 + sum_recursive(0)
= 4 + 3 + 2 + 1 + 0
= 10
Yeah, the explanation is quite good
old rover
it's like those slimes in minecraft
when you hit them they spawn more
they break into smaller slimes
old rover
is an exit condition and a base case the same thing
agile sundial
yeah
old rover
ok good just checking
yeah it actually makes sense
the best thing you can do with these functions is to walk through them with inputs
that's how you see how they work
old rover
why do CS profs decide to make it an hour long lecture I don't understand
they made functions an hour long lecture too
so idk why I'm surprised
jolly mortar
idk i prefer one long lecture to 20 5-min lectures
old rover
but idc about how it works in memory I care about using it
old rover
the sad part is after they taught this at my college like 20-30 kids dropped out
the way some people teach it makes it look like it's the most intimidating thing ever
they managed to make bottle(a web framework) look practically impossible
grizzled schooner
this is why it's nice to just learn on your own ¯_(ツ)_/¯
old rover
yeah
I think I make more progress asking questions here
than I would doing stuff for college
lean dome
Recursion is a topic that a lot of people find very difficult. They understand the concepts behind it, but struggle to figure out how to apply them to write a recursive algorithm.
old rover
yeah uh
function getFib(position) {
if (position == 0) { return 0; }
if (position == 1) { return 1; }
var first = 0,
second = 1,
next = first + second;
for (var i = 2; i < position; i++) {
first = second;
second = next;
next = first + second;
}
return next;
}
I got this and they asked me to implement it recursively
I don't really know
lean dome
Right. So those hour long lectures are designed to drill in the concepts and work through enough examples that you begin to feel comfortable doing things like that.
They're not "just the facts", they're also everything you would need in order to better remember it, to learn how and when to apply the technique, etc.
old rover
hang on
I'll watch some more videos and come back to it
so I am watching this video
and the guy said
think of the simplest possible case
it looks like the simplest possible case here is 0 or 1
that could be the base case
dude it's just the fibonacci sequence
it's just an implementation of this video
two adjacent numbers added up equals the next number
jolly mortar
mhm
old rover
smh if it's so simple why didn't I get it the first time
I don't think I should be so hard on myself
lmao
ok so I have an idea
first you think of simplest case bc that's often your base case
then you try to notice the pattern with your inputs as you increase them
you can code binary search recursively
it's less lines of code
so what's the point of writing any algorithm iteratively
if you can write it all recursively
are most recursive algorithms O(N!)?
I read that somewhere
that's why companies ask it
do recursive functions take up more memory?
so what I'm hearing is the only way I'll get good at recursion is by doing a lot of problems
drowsy steppe
can someone help me with a class proj
old rover
!rule 5
halcyon plankBOT
old rover
we can give surface level help but no code
drowsy steppe
okay
If a function returned a list of numbers, would it be possible to use that list as a parameter for another function
old rover
using what you returned in another function??
old rover
I thought the variables you created in one function only exist in the scope of that function
guess I'm wrong
drowsy steppe
yeah, that was my thought too
grizzled schooner
you can access the value that a function returns. not the things that it doesn't return though
drowsy steppe
for context, the project is too create a list of grades (in one function), then use a different a different func to average those numbers out
old rover
it would make sense then to use the list you returned
drowsy steppe
you can access the value that a function returns. not the things that it doesn't...
how would I do this
grizzled schooner
yeah, you could return that list and then use it in the other function
def funcA():
return [1, 2, 3]
def funcB():
l = funcA()
okay
old rover
function getFib(position) {
if (position == 0) { return 0; }
if (position == 1) { return 1; }
var first = 0,
second = 1,
next = first + second;
for (var i = 2; i < position; i++) {
first = second;
second = next;
next = first + second;
}
return next;
}
what is "position"?
oh
I get it
ok
def get_fib(position):
if position == 0 or position == 1:
return position
return get_fib(position - 1) + get_fib(position - 2)
0 or 1 makes sense as the base case
weary wagon
sorry to bust in your conversation but could someone explain what function the for loop is performing in this piece of code? def evaluate_algorithm(dataset, algorithm, n_folds, *args): folds = cross_validation_split(dataset, n_folds) scores = list() for fold in folds: train_set = list(folds) train_set.remove(fold) train_set = sum(train_set, []) test_set = list() for row in fold: row_copy = list(row) test_set.append(row_copy) row_copy[-1] = None predicted = algorithm(train_set, test_set, *args) actual = [row[-1] for row in fold] rmse = rmse_metric(actual, predicted) scores.append(rmse) return scores
old rover
bc they're not using negative numbers
mild cape
maybe position in the recurrence relation
old rover
"recurrence relation"?
drowsy steppe
I'm lost...
old rover
they could have just put n tbh position makes no sense to me
position like in the number line position
maybe
idk
mild cape
Fibonacci is defined as a recurrence relation https://en.wikipedia.org/wiki/Recurrence_relation you're probably very familiar with these, that's just their name. 🙂
mild cape
eh, when you learn about them, the fibonacci sequence is like the defacto example haha
old rover
they just called it the fibonacci sequence
drowsy steppe
old rover
def fibonacci(n):
if n <2:
return n
else:
return (fibonacci(n-1) fibonacci(n-2))
doesn't this do the same exact thing
it's just a different base case
drowsy steppe
ive already created the functions to get the grades, Iand they are all in lists, I just cant figure out how to avg all the values in the list
old rover
how do you take the average of anything?
you add all the numbers up and divide by how many there are
right?
drowsy steppe
well, normally I would just use a for loop to add up all the numbers and divide that total
but I cant figure out how to get that list into that for loop
because the for loop is in a different function
old rover
def funcA():
return [1, 2, 3]
def funcB():
l = funcA()
l.sum would get you all the values in that list
right?
drowsy steppe
yes but there is user input in funcA, wouldn't calling that function in funcB make the user redo the input?
old rover
well yeah for this example it's hard coded in
drowsy steppe
This is the func to get the list of grades
def numMajor(num): maList = [] cnt = 0 while num > 0: cnt += 1 ma = input("Add major grade #" + str(cnt) + ": ") maList.append(ma) num -= 1 return maList
And then I try to avg it out with this, but it doesnt work.
def majAvg(maList): x = 0 y = 0 while len(maList) > y: x += (maList[x]) x += 1 y += 1 x = x / len(maList) return x
old rover
what's the point of the while loop
if you divide the sum of a list by the length of a list
you have the average
grizzled schooner
And then I try to avg it out with this, but it doesnt work.
`def majAvg(maList)...
you can find the sum of everything in a list by using sum(), and then divide that by the length of the list
old rover
yeah what they said
vocal gorge
what's the point of cnt in numMajor? If you were using an IDE, it'd likely tell you something like "variable cnt not used".
nevermind, I'm blind
old rover
idk what top level means
vocal gorge
a builtin function like print
spring jasper
Its imported with the prelude i guess? Functions you have access to without importing anything and theyre not methods
Like print, map, list, etc
spring jasper
Ye
vocal gorge
Its imported with the prelude i guess? Functions you have access to without impo...
Yeah, that's what I want to say too, but I'm not actually sure what languages use the term prelude for that - I've only heard it in Rust
old rover
I just read somewhere that SWE people say if a function can be written recursively it should be written recursively
spring jasper
Never heard of that but i guess im not a swe yet
old rover
is there a recursive function that can't be written iteratively?
old rover
what's a call stack
mint jewel
its how the program remembers where to go after a return
mint jewel
call stack is where function calls are stored to an extent, yeah
even better example is brainfuck. No recursion, and yet turing complete
gusty swallow
I'm not sure if this is the right place, but how would I get a specific item from a config.yml file?
ping me please!
spring jasper
you install pyyaml and load the file like you do with json i think
idle basin
ok so im learning python and someone got me onto hackerrank as a way to practice/learn new stuff from example.
The one im on now is using the groupby() function in itrtools.
Am i right in thinking its basically doing what sorting by a function is but its grouping the results v that work out to the key value pair k:v. ive taken a few examples and played with them but i cant quite get it to click.
on the plus side i learned about lambda functions while looking up answers haha
weary wagon
why would you use row[-1] = None
spring jasper
to set the last element in row to be None?
weary wagon
and what is None exactly?
spring jasper
null value, nothing
weary wagon
literally nothing not even zero?
spring jasper
yes
weary wagon
def evaluate_algorithm(dataset, algorithm):
test_set = list()
for row in dataset:
row_copy = list(row)
row_copy[-1] = None
test_set.append(row_copy)
predicted = algorithm(dataset, test_set)
print(predicted)
actual = [row[-1] for row in dataset]
rmse = rmse_metric(actual, predicted)
return rmse
would the same effect be achieved by removing the last element?
weary wagon
why would you set an element to null
spring jasper
im not sure how i can answer that
where did you get that code
looking at that code i guess its to maintain the shape of the test set
if they removed the last element the shape would change
spring jasper
ok so the last element is like the target
yea i guess its to keep the shape of the test set the same
weary wagon
so it's basically a place holder that does nothing
spring jasper
yes
weary wagon
and they use it because it would shift the numbers around if they didn't
spring jasper
they use it because the test set needs to have a shape of (x, y) so if they removed the last element that shape would change
weary wagon
so they just replaced it with something that wouldn't do anything
maiden mirage
anyone could help me ?
spring jasper
def simple_linear_regression(train, test):
predictions = list()
b0, b1 = coefficients(train)
for row in test:
yhat = b0 + b1 * row[0]
predictions.append(yhat)
return predictions
this is where test_set is passed
it only uses the first element in each row in test, so theres no point in making the last one equal None
idk, this is all kinds of weird
weary wagon
so if it's not necessary why write it?
spring jasper
no idea, lots of unnecessary code in that site
weary wagon
keep in mind I'm doing this without sklearn and that stuff
old rover
I just realized something
In the granola bar box I buy from Costco there’s chocolate almond and coconut chocolate almond
I try to put all the coconut chocolate almond on the top
Isn’t that basically bubble sort?
spring jasper
Depends on the method you use to move them to the top
If youre comparing adjacent almonds and swapping them then yes
old rover
I haven’t learned mergesort and quicksort yet
lean dome
Well, the end result is the basically same regardless of which sorting algorithm you use. The elements wind up in sorted order at the end.
Whether you've implemented any particular sorting algorithm depends on which steps you take to get things into sorted order
old rover
So all of them just end up with numbers from lowest to highest in a list
lean dome
Sure. The purpose of every sorting algorithm is to sort things. They differ in how they sort things, which makes a difference for how fast they run, what sorts of input they perform best or worst on, whether the order of two equal elements is preserved, etc.
past sorrel
so i am stuck in an array problem
can this be done in O(n)
without using extra space while also preserving the order of elements
jaunty cave
#bot-commands
.help
from collections import OrderedDict
students = OrderedDict.fromkeys('abc', value=[])
students['c'].append('123')
print(students)
Edit: the result is this:
OrderedDict([('a', ['123']), ('b', ['123']), ('c', ['123'])])
Why does it append to all values in dict and not only to 'c' ?
half lotus
Cause you use the same list instance for all values
half lotus
Yes
jaunty cave
thank you very much
half lotus
You're welcome
fiery cosmos
Dayum
urban tulip
hi, i'm not sure this is right place to ask this question. which websites are good to learn DSA for beginners?
include both theory and practice exercises
vocal gorge
@old rover, did you end up finding any good ones? 🙂
high abyss
hi, i'm not sure this is right place to ask this question. which websites are go...
Check the pins brother
obsidian bone
im storing image pixel data (currently to list). What should i use to instead, dictionary, np.array? something else. Im doing program like paint.
currently len of list is like 10's of thousand of items and lists goes pretty slow
vocal gorge
im storing image pixel data (currently to list). What should i use to instead, d...
a numpy array would be a good idea, yeah
How are you getting the data, though?
obsidian bone
if len(pixels) == 0:
for i in range(3, round(infoObject.current_w/10)-3):
for j in range(3, round(infoObject.current_h/10)-3):
pygame.draw.rect(screen, (255, 0, 0), pygame.Rect(10*i, 10*j, 10, 10))
pixels.append(((10*i, 10*j), COLOR))
currently this
its my second pygame project and thats what i made. then realized list are kinda sloooow
link to what i made: (this DC) ||https://discordapp.com/channels/267624335836053506/660625198390837248/822048520717598730||
vocal gorge
What's slow here?
Appending to pixels? Are you sure (like, have you profiled it and saw that it's list operations that are slow here)?
obsidian bone
What's slow here?
oh, so when i "paint" if i move my mouse too quickly it skips (code doesnt run fast enough i quess)
This is what i found on web
obsidian bone
yeah but when i print all pixels it takse time, am I right
vocal gorge
printing a lot of stuff is just inherently slow
not because of the list, because of printing
obsidian bone
by printing i mean pygame.draw.rect()`
vocal gorge
That's probably slow, yeah, but it's completely unrelated to your list.
obsidian bone
oh, rly
vocal gorge
Anyway, never make optimization decisions before profiling. Very, very often what you think is an important-to-optimize function ends up taking 1% of your program's time.
halcyon plankBOT
Hey @obsidian bone!
vocal gorge
Here, I very much doubt the list is what's slow here. At least, certainly not in this snippet.
obsidian bone
oh
if u wanna check it out, thanks a lot for vice words. ||https://paste.pythondiscord.com/jatazixuke.yaml||
obsidian bone
Here, I *very much* doubt the list is what's slow here. At least, certainly not ...
mayby its just that u shoudnt use pygame for this kind of project. Afterall im pretty happy with result
jolly mortar
!resources
halcyon plankBOT
old rover
@vocal gorge yeah I will check the algorithms out today
lunar otter
who uses pyttsx3 module? i need help
cloud moth
i = input_val
w1,w2 = weights
p1,p2 = product of input and weights
a1, a2 = activated(sigmoid of p1, p2)
o = output
forward propogation
i x w1 = p1
a1 = sigmoid(p1)
a1 x w2 = p2
a2 = sigmoid(p2)
error rate
mse(mean square error) = 1/2(o - a2)^2
backpropogation
How exactly this magic happens ? I tried every way to understand. But can't understand. I know the w1, w2 is updated in this process.
Have you read a description of the algorithm? ML courses usually cover it, with the mathematics required to prove that it reduces error.
old rover
this may seem like a strange question
are there search algorithms other than binary search?
vocal gorge
...linear search?
old rover
that's it right
vocal gorge
you can also consider generalized binary search where you split the search interval nonequal parts
vocal gorge
the problem is that it's not hard to prove that it's on average best when the parts are equal 😛
spring jasper
Yes?
spring jasper
Uni isnt gonna teach you everything
spring jasper
If its not uni who is "they"
old rover
Udacity
vocal gorge
how do they have the audacity
old rover
~~how do they have the audacity~~
slaps knee
when she says n - 1
what does it mean?
time complexity?
or iterations?
vocal gorge
hell if I know what it's supposed to mean
vocal gorge
bubble sort is O(n^2) total
old rover
with bubble sort
vocal gorge
yeah, it's probably for one iteration
old rover
yeah then it makes sense
I don't really want to hop to another course right now even tho the Java one seems more promising
if I did do the Java one I could still ask questions here right
bc ds/algos is language agnostic
vocal gorge
sure, though you'll probably also have a lot of Java problems
spring jasper
Idk how that would work, i dont think people would appreciate java code here
vocal gorge
but there are offtopic channels, of course
old rover
I don't think I'm losing much doing the udacity course in Python
old rover
I actually did Java a little bit with edx
but I didn't really know what to do with it so I stopped
old rover
my college friend was doing minecraft mods in Java ever since middle school
I like how Udacity simply shows why bubble sort is O(N^2)
not a 3 page long explanation that I can barely read the first paragraph of
it would be nice if they updated from python 2.7 to python 3.9.1
interesting how they don't teach insertion sort
spring jasper
Its bad and its not used
old rover
that explains it
is bubble sort bad too?
bc it's O(N^2)
why don't they even show the code behind bubble sort
I guess it's just that simple
well if you understand the concept you can write it in code
something like that
Grokking doesn't even have Bubble Sort in the book
smh
def bubbleSort(alist):
#Setting the range for comparison (first round: n, second round: n-1 and so on)
for i in range(len(alist)-1,0,-1):
#Comparing within set range
for j in range(i):
#Comparing element with its right side neighbor
if alist[j] > alist[j+1]:
#swapping
temp = alist[j]
alist[j] = alist[j+1]
alist[j+1] = temp
return alist
print(bubbleSort([5,1,2,3,9,8,0]))
I'm confused by this
I've never seen -1,0,-1
is there a better way to write this
and here we go again with using range(len)
can't they use enumerate
agile sundial
exponential and interp search are basically just souped up binary searchs
old rover
oh
so it's not even that big of a deal
ok
for i in range(len(alist)-1,0,-1):
dude what does this segment of code even mean
for i in the range of the length of the list and -1,0,-1 means indexes?
spring jasper
Which -1
agile sundial
but it's len(alist) - 1, not just -1
old rover
you can use the greater than less than operator on strings??
wow I didn't actually know that
jolly mortar
well yes
jolly mortar
you can use it <, > etc on lists/tuples/etc too
old rover
that's cool
def bubble_sort(elements):
size = len(elements)
for x in range(size-1):
swapped = False
for i in range(size -1-x): #indexes of the
if elements[i] > elements[i+1]:
tmp = elements[i]
elements[i] = elements[i+1]
elements[i+1] = tmp
swapped = True
if not swapped:
break
print(bubble_sort([9,1,4]))
Did I screw up somewhere with my indentation
is that why it's printing none
old rover
noob move
for i in range(size -1-x):
the guy in the video said this line makes the code more efficient
but he never really explained why
jolly mortar
more efficient than what?
jolly mortar
yeah, the -x will make sure that it only loops over the unsorted part of the list
and skip over the part which is already sorted
have you watched a visualization of bubble sort?
the reason it's - x is because at each iteration of the outer x-loop, it'll move one more item to the end of the list, which means after x iterations, the last x items are already sorted
well
old rover
yeah I watched this
I still can't write it on my own tho
guess that means I don't actually understand it
if elements[i] > elements[i+1]:
tmp = elements[i]
elements[i] = elements[i+1]
elements[i+1] = tmp
elements[i], elements[i+1] = elements[i+1], elements[i]
have you understood how the algorithm works, even if not its implementation?
old rover
yes
it compares an element and the one it's next to
and then swaps them if the element that is next to is less than it
jolly mortar
mhm
old rover
elements[i], elements[i+1] = elements[i+1], elements[i]
would this replace the 3 lines after the if
jolly mortar
yes
jolly mortar
have you understood how the algorithm works, even if not its implementation?
I meant the full bubble-sort algorithm, not the swapping
old rover
idk how to say it other than it takes an unsorted list and with every iteration keeps swapping until the greatest value bubbles up to to the end of the list
old rover
thanks for that one line it's more readable than what he wrote
jolly mortar
for example, after 5 iterations, the 5 largest numbers would have bubbled to the end of the list
since these 5 are larger than all numbers in the unsorted part of the list, you don't need to compare the numbers in this part again
hence the size - 1 - x optimization
old rover
ok that makes sense
jolly mortar
thanks for that one line it's more readable than what he wrote
what he wrote is pretty much the standard way of swapping variables in most other languages
old rover
the swapped as a Boolean is so that there's no trying to sort an already sorted list
jolly mortar
yep
old rover
I think I get the idea
I don't know if I can instantly reproduce the code right away
but I don't think that's very important
if I spend time trying to re write every algorithm over and over I'll take forever to get through the course
old rover
learning merge sort now
vocal gorge
Now that's where CLRS can come in 😅
old rover
merge sort time complexity is O(N log(n)
I don't fully understand why it's O( n log(n)) from this
old rover
so you cut the array into smaller parts and you build it back up
jolly mortar
the number of 'rows' is proportional to how many times the list can be halved before you reach one, aka log(n)
in each row, you run through all the numbers, aka n
hence O(n log(n))
old rover
oh
ok
that makes more sense
oh boy merge sort is done recursively
that actually may be good tho bc recursive functions are normally done in a couple of lines
from what I've seen
which is not much
vocal gorge
it's not really hard, yeah
quicksort is harder IMO (similar to mergesort, but it works top-down instead of bottom-up)
mild cape
It's not too bad! 🙂
old rover
I didn't know that the tribonacci sequence existed until yesterday
I thought it was just the fibonacci sequence
but tribonacci is adding the three adjacent elements to equal the one next to it
not really changing much from the fibonacci sequence tbh
vocal gorge
yeah, they are all analytically solved via calculating the powers of the tranform matrix using the jordan normal form 😛
vocal gorge
yeah
old rover
I'm gonna learn that after I do ds/algos
so I can live in my data science dream
and here comes someone who says oh but daspecito you don't need data structures/algos for data science
I like this guy
old rover
you certainly do
you'd be shocked by the amount of people who have said you don't need to
I just automatically think now that if there's some data science on Udemy saying you don't need math to know data science that they really don't know what they're talking about
but that has nothing to do w algos/DS
spring jasper
map takes a function and an iterable and applies that function to all the elements in the iterable
vocal gorge
!docs copy
halcyon plankBOT
vocal gorge
they added a new copy function?
spring jasper
Mapreduce applies a function to an iterable and then reduces that iterable down to a single thing
Its the same as doing map() and then functools.reduce()
lean dome
Not really. Can you figure out why it's not a thing?
old rover
not really
lean dome
What's a sort algorithm you've learned so far? Bubble sort?
Most sort algorithms need to be able to access elements by index. That can't be done efficiently on a linked list.
old rover
I googled it and it said merge sort is the best
lean dome
Bubble sort is one of the few that could be implemented reasonably efficiently on a linked list... But, it's a terrible sorting algorithm, so that's not saying much.
old rover
for linked lists
lean dome
One of the steps in merge sort is dividing the list in half. With a linked list, that's a linear time operation. With an array, that's constant time.
vocal gorge
def sort_LL(lst:LinkedList) -> LinkedList:
"""Sorts a LinkedList"""
return LinkedList(sorted(lst.tolist()))
😛
LinkedList lst
I've been doing too much Java
lean dome
Yes, there is.
old rover
sorted is a keyword in python?
vocal gorge
!docs sorted
halcyon plankBOT
lean dome
!e ```py
print(sorted("bca"))
@lean dome :white_check_mark: Your eval job has completed with return code 0.
['a', 'b', 'c']
so then what's the point of bubble sort, merge sort, and quick sort?
if it's already built in?
vocal gorge
so then what's the point of bubble sort, merge sort, and quick sort?
What's the point of learning DS if they are are already implemented? 😛
lean dome
The point of learning any data structures or algorithms is learning when to use which one.
Until you know how they work, you won't be able to reason about when one is the right or wrong tool for a job.
old rover
hmm ok
lean dome
Let's say you have 100 things. You can either make a Python list with 100 items, or a Python dict with integer keys, or a 100 element set, or build your own linked list. When should you do each of those?
Until you understand how the data structures work, and what algorithms are used on them, you won't be able to answer that question.
Also... in real life you're probably never going to write a sorting algorithm, you'll just use one that someone else has already written for you. But you will need to write other algorithms, and analyze their complexity. Sorting algorithms are used as a tool to teach complexity analysis.
old rover
yeah you're right
I've just had people ask me that question
and I didn't actually know how to respond to it
ionic current
Just learned Merge Sort yesterday and I definitely get the data structure reference. In a totally imaginary case if I had long list I wanted to print with an unknown amount of duplicates, triplicates, quads etc... I could spend my time writing a function to take them all out OR If I know how a set works I could change it into oneprint and move on to the next task.
@lean dome
lean dome
Perfect example. But for that to work, you also need to know that a set is a hash table, and so that approach only works if the items are hashable.
ionic current
another good point as to why knowing the underlying mechanisms is important lol
austere sparrow
although sometimes it's a bit of abstraction-leaking
for example, a PriorityQueue is a total misnomer -- it's not really a queue, because it doesn't care about insertion order
old rover
!pastebin
halcyon plankBOT
old rover
please tell me there is an easier way to write this
bc I just watched like a 20 minute video for nothing
austere sparrow
are you familiar with generators?
or iterators
You could try doing mergesort on a deck of cards if you want a demonstration of the merging algorithm
basically: while the first list's top element is the lowest, use it. when that is no longer true, switch the lists.
old rover
yeah I used generators once
oh boy
merge sort is in real python
my savior
I will look at it after I take a nap for an hour bc I'm tired
austere sparrow
!e
This is one very hacky way:
def merge(left, right):
il = 0
ir = 0
try:
while True:
while left[il] < right[ir]:
yield left[il]
il += 1
while right[ir] < left[il]:
yield right[ir]
ir += 1
except IndexError:
yield from left[il:]
yield from right[ir:]
print([*merge([1, 2, 3, 7, 15], [4, 5, 6, 9, 10, 50])])
@austere sparrow :white_check_mark: Your eval job has completed with return code 0.
[1, 2, 3, 4, 5, 6, 7, 9, 10, 15, 50]
interesting
velvet escarp
Hi does anyone know how I would re-write this for counts of LoanRange after grouping? right now the count represents JobsRetained
austere sparrow
interesting
!e
There's a less hacky way, but it's probably catastrophically slow compared to a loop with a list.
def merge(left, right, il=0, ir=0):
if il >= len(left) or ir >= len(right):
yield from left[il:] + right[ir:]
elif left[il] < right[ir]:
yield left[il]
yield from merge(left, right, il+1, ir)
else:
yield right[ir]
yield from merge(left, right, il, ir+1)
print([*merge([1, 2, 3, 7, 15], [4, 5, 6, 9, 10, 50])])
@austere sparrow :white_check_mark: Your eval job has completed with return code 0.
[1, 2, 3, 4, 5, 6, 7, 9, 10, 15, 50]
def merge_sort(array):
# If the input array contains fewer than two elements,
# then return it as the result of the function
if len(array) < 2:
return array
midpoint = len(array) // 2
# Sort the array by recursively splitting the input
# into two equal halves, sorting each half and merging them
# together into the final result
return merge(
left=merge_sort(array[:midpoint]),
right=merge_sort(array[midpoint:]))
what do you think @austere sparrow this is from real python
sorry I pinged you twice
austere sparrow
can you perhaps post a paste, it's very long
old rover
!pastebin
halcyon plankBOT
austere sparrow
Of course not, you can write everything as one giant function (then you can't use recursion, you'll have to unroll it as a loop)
It's just easier to understand some algorithms by breaking them into parts
lean dome
And as a general rule, everything that can be done iteratively can be done recursively, and vice versa. One solution may be shorter, simpler, or more obvious than the other, but both can be used to solve any computable problem.
cerulean river
hey everyone, I was just curious if there is a way to write this
for i, elem enumerate(nums)
``` in such a manner such that it is contained within the range of the list. I know that I can do
```python
for i in range(len(nums))
```and access the elements using indices but I read that this is not "good" or "proper" python code. For reference this is the code I am working on a **two pointer leetcode problem**
```python
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
i = 0
j = 1
for j in range(len(nums)):
if nums[j] != nums[i]:
i =+ 1
nums[i] = nums[j]
return i+1
``` essentially I am asking what is the Pythonic way to make sure this loop does not throw an `IndexError`?It looks like you want precisely for i, elem in enumerate(nums):
this solution, though... does it work?
cerulean river
this solution, though... does it work?
Nope
vocal gorge
Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
cerulean river
Leetcode was throwing IndexError
I seem to have asked the wrong thing. When I was using one pointer
if nums[j] != nums[j+1]
this line was throwing the IndexError I can see why, but I was wondering if there was a way to keep this in range.
vocal gorge
Right now you're getting an indexerror on the last iteration, because i becomes len(nums) there. You want an iteration less.
cerulean river
so basically loop until its len(nums)-1?
lean dome
Or keep using enumerate and do
if i == len(nums) - 1:
break
``` at the start of the loopSo I just solved this problem and have found an interesting problem
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
i = 0
j = 0
for j in range(len(nums)):
if nums[j] != nums[i]:
i += 1
nums[i] = nums[j]
return i+1
``` **solves the problem**
whereas
```python
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
i = 0
j = 0
for j in range(len(nums)):
if nums[j] != nums[i]:
i =+ 1
nums[i] = nums[j]
return i+1
``` **does not**
I am not understanding how this makes a difference as it is just incrementing. `i =+ 1` also passes **16/161** testcases but `i += 1` passes all of them.true this also works
agile sundial
So I just solved this problem and have found an interesting problem
```python
c...
why aren't is and it the same
cerulean river
why aren't `is` and `it` the same
I do not get your question. I have not used is and it does not seem to be a python keyword
lean dome
i += 1 increments i by one. i =+ 1 is the same as i = (+1) - it sets i to 1
agile sundial
I do not get your question. I have not used `is` and `it` does not seem to be a ...
just talking about language in general
lean dome
i =+ 1 is just a funny way of spelling i = 1
cerulean river
`i =+ 1` is just a funny way of spelling `i = 1`
so it does nothing? or is it a relationship like i++ and ++i in java?
cerulean river
just talking about language in general
is is checking if it refers to the same object whereas == checks equality. Not sure what it is could not find anything on googe
agile sundial
nevermind
cerulean river
`=+` isn't a symbol in python, it's really just `= +`
thank you for the explanation
austere sparrow
!e
i = -3
while i <-- 0:
i -=- 1
@austere sparrow :warning: Your eval job has completed with return code 0.
[No output]
I've heard people suggest that we start using while (0 <-- i) in C-like languages, for real.
Advocates call it the "goes down to" operator 😄
lean dome
for (x = 5; x --> 0;) {
printf("%d ", x);
}
``` prints `4 3 2 1 0`That's the formulation of it I've seen before
lofty summit
```cpp
for (x = 5; x --> 0;) {
printf("%d ", x);
}
``` prints `4 3 2 1 0`
for (x == 5: x <-- 0){
sprintf("%$", x);}
That's... Not syntactically valid...
vocal gorge
rof (;0 <-- x ; 5 = x) {
;ftnirp(x," d%")
}
that's the point
vivid sky
Anyone know anything about constraint clustering or something similar. I am looking to cluster a set of red and blue datapoints with a few constraints:
- max total number of points in a cluster
- max total clusters (ideally would give this number of clusters every time)
- certain number of red and blue points in a cluster.
The clusters don't have to be spherical btw
old rover
I'm kind of confused: does sublime text automatically open up even if you didn't install it?
I saw some tik tok saying app academy released their entire bootcamp curriculum so I opened a file they had for linked lists and it opened in sublime text
is sublime text like the default?
old rover
is that a dumb question
agile sundial
afaik you can't open sublime unless you've installed it
old rover
oh I may have forgotten when I installed it then
old rover
def merge(left, right):
# If the first array is empty, then nothing needs
# to be merged, and you can return the second array as the result
if len(left) == 0:
return right
# If the second array is empty, then nothing needs
# to be merged, and you can return the first array as the result
if len(right) == 0:
return left
this isn't the entire algorithm
but why do they use two ifs
instead of if, elif
I thought the second if you use is always an elif
that is how it was taught in college
agile sundial
technically they have different behaviors, but the outcome is the same
old rover
ok then I'll just use elif
lean dome
It's because stylistically, it would be weird to put a comment above an elif
it's syntactically legal, but stylistically strange.
agile sundial
no that's horrible
lean dome
putting comments above code is always fine. Putting it to the right is sometimes OK, as long as the comment is very short.
old rover
I could have sworn people said comments should be put to the right of code
lean dome
https://www.python.org/dev/peps/pep-0008/#comments is what the Python style guide says about it.
the "Use inline comments sparingly." is about comments to the right of the code. They're OK sometimes, but shouldn't be your typical type of comment.
magic pendant
hi guys
spring jasper
Honestly i would suggest you stop writing comments and start writing docstrings instead
lean dome
they're for different purposes, and intended for different audiences. They're not mutually exclusive.
Comments are for maintainers, docstrings are for users.
old rover
but what if my doc string would end up as a gigantic paragraph
lean dome
that's fine. They usually do.
old rover
I would rather read a couple words for every line of code than a whole paragraph
that’s just me tho
agile sundial
if it's hard to explain better to have more words and fully explain than to be concise and leave out details
austere sparrow
Well, a docstring isn't for explaining implementation. That's what #-comments are for.
A docstring is for explaining the contract/interface of the function
As godlygeek says, a docstring is for people who're going to use the function, not fix bugs in it or add new behaviour
lean dome
docstrings explain the "what" of a function - what it does, what it expects as input, what it gives as output, what exceptions it raises. comments explain the "why" of a function - why a particular line of code exists, why it's implemented using one algorithm instead of another, etc.
old rover
ok
lean dome
taking your merge example, the docstring would say something like "Merge two sorted lists, returning a new sorted list." The comments would say things like "If the first list is empty, return the second list"
old rover
Yeah that’s what I wrote for that
fiery cosmos
I have a circle of radius 300 cm on whose circumference robots stop after moving in the environment. The robots only have a communication radius of 10 cm such that they can fit 6 robots along the diameter of the communication circle. Robots can only communicate i.e. receive and transmit messages from robots within their communication radius. Now I want to keep track of how many robots are present on the circumference of the 300 cm circle at any instant t.
What I was doing is this :
If robot_1 stops on the circumference on circle then echo "counter=1". Counter is initialized with counter=0
Another robot_2 stops on the circumference and within the comm. radius of robot_1 and recieves the echoed "Counter=1"
It checks its own counter value and if (recived_counter_value > own_counter_value) then own_counter_value=recived counter value+1
Robot_2 then send its counter value to robot_1
Similarly the counter value propogates as robots keep stopping within comm. radius of each other.
But it doesn't seem to work. Robots also have unique IDs so I can keep the track of IDs from which the current robot is receiving messages from but the memory is limited so I'm trying to avoid using the IDs but if you have an algorithm that makes use of ID then please feel free to help.
timid garden
Hi! I am wondering, how to downscale a image from 4K to 1K, I have found a scikit image processing but maybe someone has here a experience with image processing
And give some tips/tricks
tardy garnet
@timid garden not sure what you need help with. Depends on your focus, too. OpenCV is fast but tedious to install and has a lot of functionality. scikit-image is more focused on "scientific use". Pillow is a more minimal library for handling images. And downscaling exactly 4x is relatively easy to implement in numpy by yourself, too, if you're not too picky on quality!
timid garden
<@!486567039834783744> not sure what you need help with. Depends on your focus,...
I try to use one of given algorithms. Focused on bilinear bi cubic and linear interpolation
and make something in sci kit
decimation downscaling, top-left corner point in 4x downscaling
tardy garnet
Right, I still don't know what's important to you. If it's exactly 4x then binning is feasible and less noisy than decimation. Probably not too much slower, either.
timid garden
efficiency is not important at this time, I just made something like this
import matplotlib.pyplot as plt
import cv2
from skimage import data, color
from skimage.transform import rescale, resize, downscale_local_mean
image = cv2.imread("cat2.jpg",cv2.IMREAD_COLOR)
print(image.shape)
image_downscaled = downscale_local_mean(image, (2,2,1))
fig, axes = plt.subplots(nrows=2, ncols=1)
ax = axes.ravel()
ax[0].imshow(image)
ax[0].set_title("Original image")
ax[1].imshow(image_downscaled / 255.0 )
ax[1].set_title("Downscaled image (no aliasing)")
plt.tight_layout()
plt.show()
and seems to work fine
but, where I can use different functions? If I would like to make a bi linear option
in scikit image processing library
uneven jungle
that is pseudocode
timid garden
you can a write code based on this picture, simple if statements
tardy garnet
@timid garden afaik if you downscale exactly 4x you're not interpolating in the usual sense anyway so the exact interpolation type does not matter much. What you described, local mean, is the same as "binning", essentially. (Same concept has different name in different books, libraries, ...9
night plume
how can i wrtie a pseudo-code algorithm for this?
but my assignment wants us to write it somewhere on excel
can please help me
timid garden
<@!486567039834783744> afaik if you downscale exactly 4x you're not interpolatin...
So; what u recommend?
keen hearth
The : at the end of the line shouldn't be there.
dreamy shell
where can i get good notes on algos and DS for beginner
please dm me
strange bolt
where can i get good notes on algos and DS for beginner
please dm me
Hey,
I think this is a good start on python data structures: https://realpython.com/python-data-structures/
lunar otter
Hi, I need help with a network packet processing simulation problem, Im not asking for codes I just want to understand what's going on.
mild cape
@lunar otter Do you still need help?
mild cape
So, maybe the word packet is confusing, but perhaps thinking of this as a real world problem might be better.
I'm just trying to think of a good food analogy one moment.
Okay, how about a pizza oven.
So, the first number on the first line is how many pizzas can fit in the over, and the 2nd number is how many pizzas are going to attempt to be cooked.
If a pizza is prepared, but there is no room in the oven for it to cook, it is discarded because there is no counter space to store it.
So, the lines that follow have two numbers each,
the first being the time the pizza was prepared, and the 2nd being how long it will take to cook.
lunar otter
ohh i see
mild cape
You have to figure out when a pizza will be processed or if it will be discarded.
lunar otter
but what about the sample number 3
mild cape
Let me see.
lunar otter
the sample 3 here
mild cape
So sample number 3 is saying that the pizza oven can only fit 1 pizza, but there were two prepared at one time so we had to discard one.
lunar otter
yeah but the first output is zero
mild cape
Because that is the time that the first pizza started cooking.
Read the output format one more time.
lunar otter
is that the reason why the second output is -1?
mild cape
It says for each pizza you receive you either output the time it started cooking, or -1 for it being discarded.
Yes, because the 2nd pizza could not fit in the oven so it was discarded.
lunar otter
what about the 2nd and 3rd line of input
mild cape
Because they were both prepared at the same time (time 0)
lunar otter
i mean why does the two output only relates to the first line of input
mild cape
The first input is like the parameters for the pizza oven
the following outputs after are for each pizza
and so for each pizza there is a unique output
So if you have 3 lines of input, you'll have 2 lines of output
since the first line is like metadata for your pizza oven (how many pizzas it can fit, and how many pizzas are going to attempt to be cooked)
lunar otter
i still dont get it lolll ill just backread from ur first message and read it again
mild cape
I'll write some code to show you what I mean.
mild cape
yeah we don't need no oop
lunar otter
class Buffer:
def __init__(self, size):
self.size = size
self.finish_time = []
@property
def is_full(self):
if len(self.finish_time) == self.size:
return True
return False
@property
def is_empty(self):
if len(self.finish_time) == 0:
return True
return False
@property
def last_element(self):
return self.finish_time[-1]
def flush_processed(self, request):
while self.finish_time:
if self.finish_time[0] <= request.arrival_time:
self.finish_time.pop(0)
else:
break
def process(self, request):
self.flush_processed(request)
if self.is_full:
return Response(True, -1)
if self.is_empty:
self.finish_time = [request.arrival_time + request.process_time]
return Response(False, request.arrival_time)
response = Response(False, self.last_element)
self.finish_time.append(self.last_element + request.process_time)
return response
like this
mild cape
yeah ignore that for now.
pizza_oven_size, pizza_attempts = map(int, input().split())
print(f"My oven can fit only {pizza_oven_size} pizzas at a time.")
for i in range(pizza_attempts):
pizza_arrival_time, pizza_cook_time = map(int, input().split())
print(f"Pizza {i} attempt to be cooked at time {pizza_arrival_time}s"
+ f" and will take {pizza_cook_time}s to cook.")
oh god you just made it so simple
im losing my mind already with this problem
i think i get it now I tried writing the inputs in a paper and visualize them
mild cape
that's good!
lunar otter
thank you so much!! you made it so clear for me to understand
mild cape
@lunar otter Here's a possible solution, given you already have one yourself. But this doesn't use any OOP
pizza_oven_size, pizza_attempts = map(int, input().split())
pizza_oven_racks = [0] * pizza_oven_size
for i in range(pizza_attempts):
pizza_arrival_time, pizza_cook_time = map(int, input().split())
was_there_room = False
for i in range(len(pizza_oven_racks)):
if pizza_oven_racks[i] <= pizza_arrival_time:
pizza_oven_racks[i] = pizza_arrival_time + pizza_cook_time
was_there_room = True
print(pizza_arrival_time)
break
if not was_there_room:
print(-1)
thanksss!! tho i got my code working already
fathom prairie
i have an array of integers, now i have to sort the array in such a way that the multiples are side by side in the array
example -
fresh array = [3, 5, 4, 9]
sorted array = [5, 4, 3, 9]
the position of the multiples doesn't matters, it should just be side by side
old rover
while len(result) < len(left) + len(right):
if left[index_left] <= right[index_right]:
result.append(left[index_left])
index_left +=1
else:
result.append(right[index_right])
index_right +=1
if index_right == len(right):
result += left[index_left:]
break
if index_left == len(left):
result += right[index_right]
break
return result
so that while loop is so that while the length of the left list and the length of the right list is less than the length of the result the code block will be executed
index_left = index_right = 0
this is what they write for index_left and index_right
so if the left value is less than the right value you append it to result
result is the sorted list
index_left += 1 is just another way of incrementing by 1
the else does the same thing but for the right side
old rover
def merge_sort(array):
if len(array) < 2:
return array
midpoint = len(array)//2
return merge(
left = merge_sort(array[:midpoint]),
right = merge_sort(array[midpoint:])
)
what is [:]
I've never seen that before
old rover
what's list slicing
>>> nums = [10, 20, 30, 40, 50, 60, 70, 80, 90]
>>> some_nums = nums[2:7]
>>> some_nums
[30, 40, 50, 60, 70]
I know that
it takes the elements from index 2 to index 7
vocal gorge
yup. The only thing different here is that slice syntax allows omitting indexes
first index defaults to 0, second to len(lst)-1, third to 1
so here, it's a slice 0:midpoint and midpoint:len(array)-1
very convenient
old rover
hmmm
0:midpoint
midpoint is the array divided by 2
so 0 through whatever half the array is
and then you're calling merge sort on it
this is big brain stuff
yeah I got no clue
vocal gorge
not sure what you mean
this code just divides the array in halves and passes them to merge
grizzled schooner
that is true
lean dome
Every recursive algorithm needs a base case to terminate
halcyon plankBOT
lean dome
Yeah. That's the merge 2 sorted lists into 1 sorted list function
old rover
yes
vocal gorge
hmm, does it really have to be this long
old rover
it does make more sense the more I look at it
this is the entire website for context
(array[:midpoint]),
does that mean 0 till the midpoint
(array[midpoint:])
and the midpoint till 0?
vocal gorge
does that mean 0 till the midpoint
yeah
old rover
ok
vocal gorge
and the midpoint till 0?
no, till the end
old rover
oh
old rover
hmm, does it really have to be this long
how do you write this shorter
it does make sense tho
vocal gorge
from more_itertools import peekable
def merge(a,b):
lst = []
a,b = peekable(a),peekable(b)
while True:
next_a = a.peek(None)
next_b = b.peek(None)
if next_a is None:
lst.extend(b)
return lst
if next_b is None:
lst.extend(a)
return lst
if next_a > next_b:
lst.append(next(b))
else:
lst.append(next(a))
like that, I guess. I find iterators nicer, is all
hmm, not much shorter
vocal gorge
peekable can be implemented yourself easily enough
old rover
what is peekable
vocal gorge
A wrapper over an iterator that allows you to peek at the next element without taking it
vocal gorge
uhh, no
as the signature implies, you call it by passing in two lists 😛
(and they better be sorted, too)
old rover
Traceback (most recent call last):
File "main.py", line 44, in <module>
print(merge_sort([1,2,3]), [1,2,3])
File "main.py", line 40, in merge_sort
right = merge_sort(array[midpoint:])
File "main.py", line 38, in merge_sort
return merge(
File "main.py", line 26, in merge
result += right[index_right]
TypeError: 'int' object is not iterable
oh boy
old rover
nvm I fixed it
old rover
if index_right == len(right):
result += left[index_left:]
break
if index_left == len(left):
result += right[index_right:]
break
def merge(left, right):
result = []
index_left = index_right = 0
while True:
if index_right == len(right):
result += left[index_left:]
return result
if index_left == len(left):
result += right[index_right:]
return result
if left[index_left] <= right[index_right]:
result.append(left[index_left])
index_left += 1
else:
result.append(right[index_right])
index_right += 1
my take on their merge function
that's a bit shorter
old rover
you don't return result there?
vocal gorge
I do
old rover
oh you do
I am blind
sorry
print(merge_sort([1,2,3]), [1,2,3])
so I just did that
and all it gave me was this: [1, 2, 3] [1, 2, 3]
the paramaters of merge_sort is just a list
oh it works
yayyyy
so it's calling merge_sort recursively
and then calling merge on those two sorted lists?
yes bc merge takes the two lists and uses if to compare them
that's pretty cool
vocal gorge
the paramaters of merge_sort is just a list
yup, you asked about merge before. Mergesort, meanwhile, is a sorting function - takes list, returns a list
vocal gorge
I said something like that
calm knoll
Hi! I'm working on this Leetcode Algo/DSA problem https://leetcode.com/problems/average-of-levels-in-binary-tree/ but a little confused on if I have to construct the tree first using the input array: root = [3,9,20,null,15,7] and how that get's passed into my function. I know how to solve the problem if I construct a tree like this:
root.left = Node(9)
root.right = Node(20)
etc...
But don't quite understand what they want me to do with the array. Any thoughts?
Here's the problem on Leetcode:
Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.
Input: root = [3,9,20,null,15,7]
Output: [3.00000,14.50000,11.00000]
Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.
Hence return [3, 14.5, 11].```
main kiln
Hello everyone, I am new to python programming and would like some help please in building a script!
thorn hamlet
who is algo
glacial crag
how come languages like R dont use loops
You can loop in R
old rover
just bc of speed?
"Loops are slower in R than in C++ because R is an interpreted language (not compiled), even if now there is just-in-time (JIT) compilation in R (>= 3.4) that makes R loops faster (yet, still not as fast). Then, R loops are not that bad if you don't use too many iterations (let's say not more than 100,000 iterations)"
agile sundial
i thought he was comparing looping vs not looping in R itself, not vs othre langs
old rover
oh idk
fiery cosmos
Might be useful to you also ... (it is used everywhere in my small script !
def pathScriptNameSplit():
p, fe = os.path.split(os.path.abspath(sys.argv[0]))
f, _, e = fe.rpartition('.')
return [p, f, e]
modifies original array
fiery cosmos
Those are the basic s type of sort .... some real application can customize them to their need (Ex TimSort )
old rover
what the hell is cocktail shaker sort
that's a thing apparently
yeah quick sort doesn't look that bad
I was overreacting
fiery cosmos
lol there is some there that are just for fun lol
scarlet maple
oh look its das
agile sundial
recursion takes a bit to get used to
scarlet maple
old rover
oh look its das
why are you so surprised to see me here
this is like my home
so quick sort's time complexity is also O(n log n)
so when would you use merge sort v quick sort
scarlet maple
same
old rover
anyways
fiery cosmos
10 elements is probably sort faster by insertion sort that by quicksort ...
scarlet maple
i learned numpy arrays are slower than python lists when appending
i think thats the only thing i can add to this channel
fiery cosmos
btw there is also many variations of quicksort ...
old rover
yeah
scarlet maple
so do your appending first then convert to a numpy array after
vocal gorge
i learned numpy arrays are slower than python lists when appending
Very much yes, because you can't actually append to a numpy array - only create a new one and copy to it the data from the original and the appended element.
(unless numpy does some optimazations for this, but there's only so much it can possibly do while still being an array and not a vector)
scarlet maple
yeah how i interpreted it, its like numpy array is already set in when you instantiated it
vocal gorge
pretty much - that's how actual, C arrays are; just some area of memory, each k bytes of which is a value
scarlet maple
vocal gorge
does it matter what number you pick as the pivot
on average not much, but for any(?) deterministic choice of a pivot, it's possible to constuct a worst case on which the algorithm gets horrible complexity
because of that, some implementation choose it randomly, and others do smart stuff like measure how good the chosen pivots were and change strategy if the chosen pivots are consistently bad
old rover
