probably explaining that that's the Python syntax for a swap, in case you're not already familiar with it.
#algos-and-data-structs
lean dome
old rover
but what is the point of if largest != i:
in other languages you would declare a temporary variable and swap them
but Python is different
but that doesn't help me figure out what the point of if largest != i
misty plume
hmm I see @lean dome , I'm going to try some things
thank you a lot by the way
https://gyazo.com/c699e24ecdf5a8e09ad03123f6df6ae2 the input (left) and output(right) show how it should look like. So maybe I can create a counter of True/visited nodes?
lean dome
but that doesn't help me figure out what the point of if largest != i
it skips that step when i and largest are the same number, because in that case the swap would be a no-op, and it's already a heap so there's no need to heapify
misty plume
and after it check if the number equals the length of the original node input?
lean dome
https://gyazo.com/c699e24ecdf5a8e09ad03123f6df6ae2 the input (left) and output(r...
You said you were supposed to check whether or not it's a connected graph, but that output would just be a true or false - right?
misty plume
and after it check if the number equals the length of the original node input?
considering that I do that afterwards aswell
you said checking that every value of the array is true
old rover
def heapify(self, n, i):
#n is heap size
largest = i
l = 2 * i + 1 #left child
r = 2 * i + 2 #right child
#if the left child is bigger make largest = left child
if l < n and self[largest] < self[l]:
largest = l
#if the right child is bigger make largest = right child
if r < n and self[largest] < self[r]:
largest = r
#if they're not the same number
if largest != i:
self[i], self[largest] = self[largest], self[i]
heapify(self, n, largest)
so this is apparently wrong
misty plume
oh, wait yea, actually that's it
old rover
bc it's saying undefined name
lean dome
unless I'm missing something, you can answer your question by just deleting some code. If you did ```py
def dfs(g):
n = len(g)
visited = [False] * n
dfsRec(g, visited, g[0])
for was_visited in visited:
if not was_visited:
return False
return True
coming from java, Im struggling a lot with python, yes I see it now, thank you so much 😦 sorry for being a slow learner
old rover
idk what's undefined about heapify
it's not the indentation
oh nvm
nothing is wrong it just disappeared
magic
old rover
yeah I have been stuck on heaps for quite a while
no
it's still wrong
🙂
def heapify(self, n, i):
#n is heap size
largest = i
l = 2 * i + 1 #left child
r = 2 * i + 2 #right child
#if the left child is bigger make largest = left child
if l < n and self[largest] < self[l]:
largest = l
#if the right child is bigger make largest = right child
if r < n and self[largest] < self[r]:
largest = r
#if they're not the same number
if largest != i:
self[i], self[largest] = self[largest], self[i]
heapify(self, n, largest)
what is so horribly wrong about this
is it bc I'm using self?
instead of arr?
old rover
!pastebin
halcyon plankBOT
lean dome
what is this method supposed to do?
old rover
heapify?
turn an array into a heap
oh now I see
it doesn't make sense to put it in a binary heap class
is that what you're trying to say?
lean dome
what I'm trying to say is that you've got a method called heapsort that does not appear to use a heap to sort an input list, so I don't understand what it's doing or what its purpose is
is it supposed to be heapify, not heapsort?
misty plume
unless I'm missing something, you can answer your question by just deleting some...
@lean dome I have tried to delete the def dfs class and put yours, and It didn't work, could you explain why you had on dfsRec(g, visited, g[0]) and maybe instead of g[0]?
and also, I'm trying something like this, It might be horrible so I warn your eyes before sending it
it's just to know If what I thought as a solution has any sense
but I would prefer to understand your way of doing it too
old rover
def heapify(self, n, i):
#n is heap size
largest = i
l = 2 * i + 1 #left child
r = 2 * i + 2 #right child
#if the left child is bigger make largest = left child
if l < n and self[largest] < self[l]:
largest = l
#if the right child is bigger make largest = right child
if r < n and self[largest] < self[r]:
largest = r
#if they're not the same number
if largest != i:
self[i], self[largest] = self[largest], self[i]
heapify(self, n, largest)
You say my version didn't work. What happened?
misty plume
TypeError: list indices must be integers or slices, not list
lean dome
well, yes. Every place where you put self[ should be self.heap[, and you should stop passing n as a parameter and just do n = len(self.heap)
misty plume
TypeError: list indices must be integers or slices, not list, this error apparently affects lithe lines where the def are called
old rover
def heapify(self, n, i):
#n is heap size
largest = i
l = 2 * i + 1 #left child
r = 2 * i + 2 #right child
n = len(self.heap)
#if the left child is bigger make largest = left child
if l < n and self.heap[largest] < self.heap[l]:
largest = l
#if the right child is bigger make largest = right child
if r < n and self.heap[largest] < self.heap[r]:
largest = r
#if they're not the same number
if largest != i:
self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
heapify(self.heap, n, largest)
here's what I added
lean dome
just remove the parameter. Get rid of n from the def heapify() line, and get rid of n in the heapify() call.
lean dome
TypeError: list indices must be integers or slices, not list
Ah, I see - try this: ```py
def dfs(g):
n = len(g)
visited = [False] * n
dfsRec(g, visited, 0)
for was_visited in visited:
if not was_visited:
return False
return True
I think I had a `g[0]` that should have just been `0`er, wait...
Fixed it 😄
misty plume
it was the 0 then?
old rover
def heapify(self, i):
#n is heap size
largest = i
l = 2 * i + 1 #left child
r = 2 * i + 2 #right child
n = len(self.heap)
#if the left child is bigger make largest = left child
if l < n and self.heap[largest] < self.heap[l]:
largest = l
#if the right child is bigger make largest = right child
if r < n and self.heap[largest] < self.heap[r]:
largest = r
#if they're not the same number
if largest != i:
self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
heapify(self.heap, largest)
still is wrong
lean dome
it was the 0 then?
Yeah, I think I passed the wrong thing down to dfsRec; I passed a list where it expected just a node number.
lean dome
```python
def heapify(self, i):
#n is heap size
largest = i
l = 2 * ...
that heapify call at the end should be self.heapify(largest)
misty plume
how does it work? what's was_visited?? when you have the time If you could explain it a bit in depth
misty plume
https://gyazo.com/76a5f356f19f4baedd80aa4b67da1a00
and did my primitive non efficient way had any sense in some world?
old rover
for i in range(n//2 - 1, -1, -1):
heapify(arr, n, i)
yeah uh I don't really know what that means
lean dome
how does it work? what's was_visited?? when you have the time If you could expla...
visited is a list of bools, one per node, initialized to False for each of them. If node n has been visited, we set visited[n] = True. At the end of the traversal, if visited[n] is True for every node n in the graph, we know that every node has been reached.
So, we start a search at one node - any node. We've chosen 0, but we could have picked any arbitrary node. Starting from the node we've picked, we record that it has been visited, and then we visit every node that's adjacent to it, and every node that's adjacent to any of them, recursively. If a node has already been visited we don't recurse (since if we did, we would loop forever)
misty plume
what a living legend
lean dome
does it make sense now that you've seen the explanation?
old rover
I googled how to use range
well I do know how to use range
the first value is the starting value the second value is what it should reach and the third is what it's incrementing by
lean dome
```python
for i in range(n//2 - 1, -1, -1):
heapify(arr, n, i)
```
That's equivalent to ```py
i = n // 2 - 1
while i >= 0:
heapify(arr, n, i)
i = i - 1
if you pass 3 values, that's right. first is the starting value, middle is the number to stop once it is reached, last is the amount to increment by.
misty plume
yes It makes sense, the only thing I still don't understand, it might be python basics, but was visited is a boolean, list, thing?¿
for was visited in visited is for every visited node in visited list?
old rover
that said visited too many times in a sentence
misty plume
😦 true
lean dome
for was visited in visited is for every visited node in visited list?
yes, exactly. for e in x is "for every element in x"
the Java equivalent would be something like ```java
for (bool wasVisited : visited)
why does it print only one time then? and not for every element?
lean dome
why would it print for every element? There's no print at all
misty plume
oh, well I changed it so that the output on the screen is yes or no
for was_visited in visited:
if not was_visited:
return print("NO")
return print("YES")
lean dome
because you return immediate after printing
so the function stops running, so none of the other prints are reached
misty plume
and only the last one gets printed?
lean dome
the first one that's reached, whichever it is
serene oracle
sometimes the best thing to do when you are not sure what a block of code does... is to try it out. hard code some parts and stub out function calls and run it.
old rover
I know what it does
like I know what range with those three arguments does
I just don't understand why they used it
why use -1?
serene oracle
try running it without using the -1 and see. I'm not sure tbh, but that is what i would do as a start
lean dome
that starts at node n // 2 - 1, and then heapifies every node from that up through 0. At the end, the entire tree has been heapified
old rover
but it goes up till -1
but that doesn't mean anything
bc there is no -1 index
yes there is
halcyon plankBOT
@lean dome :white_check_mark: Your eval job has completed with return code 0.
001 | 5
002 | 4
003 | 3
004 | 2
005 | 1
006 | 0
oh
lean dome
it never reaches -1.
serene oracle
@lean dome there was another example a while back that used for i in range(n, -1, -1) which also worked
old rover
that was also probably me 🙂
serene oracle
no, i tried both, they both worked
serene oracle
at least for my 1 test case i made up. there is probably a corner case where they are different, but i didnt dig into them enough to find it
serene oracle
n//2 is just a division
old rover
but what's the point of it
so you start mid heap?
that seems like the most plausible reason
serene oracle
it is floor(n/2)
serene oracle
it starts half way because that is as far as it needs to go
old rover
ok
serene oracle
try making up an example and walking through it line by line with pencil and paper and see what happens if you start at n instaed of n//2-1
its because of the way the array is used to represent a tree
serene oracle
there are only 3 arguments
serene oracle
that happens to me all the time, means it's time to go outside for a bit 🙂
serene oracle
so look in heapify, it is trying to find the left and right child nodes of the current one, which are at indexes 2*i+1 and 2*i+2. The it checks l<n and r<n to make sure the left and right children exist (ie. are the computed locations actually valid indexes into that array?) if you start beyond 1/2 up the array, l and r will be larger than n (the size of the array) and heapify will do Nothing until you've iterated down to.... where?
old rover
0
serene oracle
no
len(arr) == 100. then if i==50, what are l and r ?
101 and 102
what if i==60 ?
121 and 122
thos are all larger than 100. heapify will do nothing.
the end of the array is all leaf nodes. they have no children. it doesn't make sense to call heapify on them, it only makes sense to call it on non-leaf nodes. its because the array has the property that if index n is a node, then it's left child is at 2*n+1 and right child at 2*n+2. if an array has 100 elements, i know that nothing beyond 49 can have children, because if it did then they would have to be at indexes 2*50+1=101 and 2*50+2=102, which contradicts the assertion that the array has 100 elements.
misty plume
SO
i'm back hahahh last question of the night I promise
@lean dome's solution to my problem works, but in order for the program to print a yes or a no when all the nodes were visited, I needed something
and I figure this out
def dfs(g):
n = len(g)
visited = [False] * n
collection = []
dfsRec(g, visited, 0)
for was_visited in visited:
if not was_visited:
collection.append([False])
else:
collection.append([True])
if all(collection):
print("YES")
else:
print("NO")
does it make sense? because for some reason I get a YES with some cases that should be NO
unkempt umbra
yo dudes k so i got a scapegoat tree working kinda ish and i tested it by inserting range(20000) to it
and it was hella slow
and then i added an instance variable to store number of rebuildings
and it was 10000 i think
around half the number of elements
which is kinda sus
cuz inserts should be around log n
and the linear rebuildings shouldn't happen that often
unless they do
acc k imma see how many times this other scapegoat tree code i found online rebuilds
hmm ok
ig it depends on the value of a
the other scapegoat tree also had half the number of rebuilds
wait sike k i tested with 200,000 and now the number of rebuildings is up to 133,315
trees are weird
wait oh
it was 13,318 before
hmm k
imma need a graph between alpha and the number of rebuildings (and probably total number of nodes rebuilt too)
dang ok the relationship between alpha and number of nodes rebuilt is kinda like that hyperbole thingy
unkempt umbra
o dang hmm
red is the number of times it is rebuilt
blue is the number of nodes rebuilt
green is the time (kinda cherrypicked so ignore this)
graph made using desmos
the number of times rebuilt looks like a step function lol
ohhhhh
depth > floor(log(self.node_count, 1/self_a))
floor'd
k idk how the math works out but this is pretty neat
thank you for coming to my ted talk
glass crane
frozen smelt
Can someone help me understand why this is not acceptable as a codewars answer
Given n, take the sum of the digits of n. If that value has more than one digit, continue reducing in this way until a single-digit number is produced. The input will be a non-negative integer.
16 --> 1 + 6 = 7
942 --> 9 + 4 + 2 = 15 --> 1 + 5 = 6
132189 --> 1 + 3 + 2 + 1 + 8 + 9 = 24 --> 2 + 4 = 6
493193 --> 4 + 9 + 3 + 1 + 9 + 3 = 29 --> 2 + 9 = 11 --> 1 + 1 = 2
def digital_root(n):
number = [int(x) for x in str(n)]
new_number = sum(number)
if len(str(new_number)) > 1:
digital_root(new_number)
else:
print(new_number)
return int(new_number)
Test Results:
Log
7
Test Passed
Log
6
None should equal 6
Log
6
None should equal 6
Log
2
None should equal 2
solar timber
Heyyy, what's the best way to learn algorithms?
Any good YouTube channel or a good book?
glossy breach
Can someone help me understand why this is not acceptable as a codewars answer
...
You aren't returning the value of digital_root(new_number)
So basically when len(str(new_number)) > 1, the function returns None
Anyway there's a one-line solution for this problem
fathom prairie
i have a string that has either the letter C, or J, or a ?
examples - "CJ?CC?" or "C?JJC?"
now in this string i have to replace each ? with either C or J and find all possible combinations
lets consider "CJ?CC?" as this string, if we start replacing ? and find all the possible combinations then the possibile combinations will be "CJJCCJ" and "CJCCCJ" and "CJCCCJ" and "CJJCCC"
how can i find all possible combinations using python
hearty creek
hello
hearty creek
anyone can make like this in python?
yes thats easy
fathom prairie
anyone can make like this in python?
s = "12345"
x = s[0] + " "*(len(s)-2) + s[-1]
print(s)
print(x)
print(x)
print(x)
print(s)
vocal gorge
i have a string that has either the letter `C`, or `J`, or a `?`
examples - `"CJ...
itertools.product is likely what you want.
fiery cosmos
pls ping
grizzled portal
```py
s = "12345"
x = s[0] + " "*(len(s)-2) + s[-1]
print(s)
print(x)
print(x)
p...
Oke thank you
hearty creek
is there a way that my variable can hold values of text allignment f-string?
frozen smelt
You aren't returning the value of `digital_root(new_number)`
sorry for the delay,
thank you, I got there in the end eventually, I realized I was not returning any value back into the recursive call and was only logging the change of number and not returning it!
I saw the one liners and was blown away, I have a long way to go
fathom prairie
`itertools.product` is likely what you want.
I don't understand how can i accomplish that with itertools.product
lunar otter
def shift(s, n):
alphabets = 'abcdefghijklmnopqrstuvwxyz'
new_word = ''
for letter_s in s:
ctr = 0
if letter_s == ' ':
pass
for letter_a in alphabets:
if letter_s == letter_a:
new_word += alphabets[(ctr-1)+n]
ctr += 1
return new_word
hi, i have this code that shifts letters on a string based on a given number however im having a trouble when there are spaces since it is also shifted in the loop even though i added a pass condition
agile sundial
pass doesn't do what you want, you probably want continue
lunar otter
print(shift('hello world', 2))
ifmmpxpsme
it outputs this
ohh
continue doesn't work too
displays the same result
i tried break but it just ends the loop entirely
agile sundial
it's probably because of how you're applying the shift
you're creating the new string in the inner for loop for some reason
why do you have an inner for loop
lunar otter
oh i tried putting it on else statement
def shift(s, n):
alphabets = 'abcdefghijklmnopqrstuvwxyz'
new_word = ''
for letter_s in s:
ctr = 0
if letter_s == ' ':
new_word += ' '
continue
else:
for letter_a in alphabets:
if letter_s == letter_a:
new_word += alphabets[(ctr-1)+n]
ctr += 1
return new_word
it works now
thankss
old rover
so all an unbalanced tree is
is when all the children are on the right side?
or on the left side
so like this is unbalanced
bc all the children are right children
it's basically a linked list
lean dome
That's the worst case of an unbalanced tree, but not the only case
An unbalanced tree is a tree that is not balanced.
old rover
so every parent needs to have a left child and a right child
agile sundial
a balanced tree is a tree that is not unbalanced 
lean dome
A balanced tree has the heights of the left and right subtree of any node differ by not more than 1
lean dome
Phone keyboard 😅
mint jewel
depends. There are a lot of parameters that affect it, but the general idea is pretty simple. Actually implementing one from scratch is quite the large project though if you want it to be in the complexity category as python, JS and such
old rover
depends. There are a lot of parameters that affect it, but the general idea is p...
"complexity category"?
mint jewel
O(1) time lookups, O(n) space
agile sundial
O(1) adding keys and stuff
old rover
oh ok yeah that's what I thought
mint jewel
since if you just hardcode the hash space, you get O(n) lookups
old rover
is there a difference between an AVL tree and a red black tree?
how important are AVL trees? Do I have to worry about the implementation for them too?
agile sundial
is there a difference between an AVL tree and a red black tree?
the difference is just how they maintain balanceness
old rover
it really annoys me how Udacity just skips AVL trees
it just jumps directly to red black trees
so this is one implementation of AVL trees
this is another implementation of AVL trees
which one is better?
worthy fjord
anyone knows an algo to find the yellow areas?
maybe rectangles
its essentially, fixed sized buckets, and how they can satisfy demand
for context, bars are manpower requirement per 15 minute range
agile sundial
it really annoys me how Udacity just skips AVL trees
you don't have to learn them sequentially, they're two different ways to solve the same problem
old rover
So I don’t have to learn them both?
old rover
ok sounds good
fervent saddle
from timeit import timeit
setup = """
from random import randrange
s = ''.join([chr(randrange(97, 123)) for _ in range(10000)])
"""
stmt1 = "x = sum([ch in {'a'} for ch in s])"
stmt2 = "x = sum([ch == ('a') for ch in s])"
print(timeit(setup=setup, stmt=stmt1, number=1000))
print(timeit(setup=setup, stmt=stmt2, number=1000))```why is stmt2 slower than stmt1?
Someone told me to ask this here
If you use a tuple instead of a set, stmt1 is slower. But like this, stmt1 is somehow faster
fervent saddle
#bot-commands message
It seems like it’s consistently faster
And I’m just wondering how that can be when it seems like stmt1 would be doing what stmt2 does, but with the addition of hashing the characters it comes across
willow narwhal
How can I implement ML into a discord bot that I am making, I want to use it for my Anti-Spammer mechanism
agile sundial
@fervent saddle
oop, one sec
did string of length 26
std dev overlap, no difference
fervent saddle
When I switched stmt1 and stmt2 so stmt2 runs first, stmt2 seems like it tends to be a little faster
On repl.it
agile sundial
¯_(ツ)_/¯
agile sundial
¯_(ツ)_/¯
fervent saddle
Alright
dapper sapphire
So we dont have duplicate values/keys in a Binary tree? What about just Trees?
When I look up Trees, I get Binary Search Tree.
fervent saddle
Nvm, that’s just for binary search tree. You’re not asking specifically about that
This has duplicates: https://www.geeksforgeeks.org/heap-data-structure/
dapper sapphire
So do trees and other derivatives of trees(bst, heap trees) involve a lot of recursion?
old rover
some of the functions associated with them use recursion
agile sundial
the definition of a tree is naturally recursive, and many operations will be
old rover
what does naturally recursive mean
agile sundial
intrinsic, by definition, or whatever
a tree's children are trees
see the recursion?
dapper sapphire
I see what you mean
gritty ibex
anyone ever written a snmpwalk in pure python ?
dapper sapphire
Is it bad that I am implementing binary tree using traversal instead of recursion?
agile sundial
what do you mean by traversal?
old rover
in order, pre order, post order??
dapper sapphire
using a while loop to find the left or right node and then inserting the new value
lean dome
Some algorithms are harder to implement that way, or require keeping extra state. For the algorithms that can be implemented that way, it's usually the better way
dapper sapphire
Some algorithms are harder to implement that way, or require keeping extra state...
When you say that way you mean traversal?
Yeah, I have heard something similar that recursion can produce some nice solutions.
misty plume
@lean dome you remember me from yesterday's question streak? Can I ask you about the same problem? I tried some things out but it still doesn't work the way it should
unkempt umbra
```py
from timeit import timeit
setup = """
from random import randrange
s = ''...
your "tuple" aint actually a tuple
it's just a char wrapped in parentheses
maybe that's why
fervent saddle
I know
fervent saddle
I think I had a tuple there at one point, and I forgot to remove the parentheses. That’s why it has parentheses around it
unkempt umbra
lol aight good to know
fervent saddle
Forgot or was too lazy
unkempt umbra
xD
lean dome
<@!451976922361102357> you remember me from yesterday's question streak? Can I a...
Sure, ask. If I'm around and see the question, I'll try to help
misty plume
so, I have this
but the output isn't always yes, basically I fill collection with trues or falses based on the nodes visited, and if all of the elements inside collection are true, it should print yes
misty plume
ow ok, I'll check it now
unkempt umbra
also this aint code review but you can remove the collection list and just do all(visited) instead which is way shorter
unkempt umbra
did it work?
misty plume
well it says yes and no in the cases I'm trying
misty plume
I'm trying to log in into DOMjudge, in order for it to be proved
unkempt umbra
nice dmoj
misty plume
but for some reason it isnt logging in, but as soon as I join I'll report back hahaha, yesterday it took a while for it to let me log in too
unkempt umbra
lol which problem is it
misty plume
my university created the accounts, and they did something wrong when introducing my password
misty plume
hahaha thx, the problem is also one made by them
misty plume
(what's ccc?) 😦
unkempt umbra
ohh then nvm
ccc is a contest by waterloo's cemc
pretty big one in canada
but lol which problem are you doing
imma solve it too
for the points
waait a second
u didnt misspell it
wtf is domjudge lmao
misty plume
I can send it to you, it's on spanish but I guess you will get it pretty quick, I can also tell you if you don't get it
unkempt umbra
alright lol it'll be good practice
misty plume
it checks your code, I guess It's just another platform for programming contests
misty plume
alright lol it'll be good practice
sure 😄
unkempt umbra
lol the website looks pretty clean
misty plume
(I'm still trying to get in to see the problems)
unkempt umbra
xD
misty plume
I have 4 graphs problems and 4 of vortex algorithms (i think it's called vortex in english, not sure tbh)
unkempt umbra
lol there's probably another word for "vortex problems"
unkempt umbra
ohh
misty plume
sorry for the eye pain
misty plume
for saying vortex
unkempt umbra
xD it wasn't that bad
misty plume
well... could have said something worse probably, but... hahah
unkempt umbra
lol its ok translating stuff is hard
misty plume
apparently the answer is still wrong
fiery cosmos
is there a way to make something run after your pc turns on using python
old rover
is there a way to make something run after your pc turns on using python
something run?? like a desktop app?
old rover
not so sure
fiery cosmos
oh okay
agile sundial
spring jasper
I would not do that tho, startup apps are a plague
old rover
@spring jasper I got no clue why but Amazon music always opens up on my desktop but I literally shut it down so it shouldn’t be opening up
anyways that has nothing to do w algos/DS so I’ll stop
fiery cosmos
hommie i heard there is a linear time algo for mst
any one knows?
not prims kruskals or brouvka
meager jetty
Cool my first version of shortest path for graph works !!! now let study how dijkstra do it 🙂
or not let go to sleep...
fervent saddle
Where in built-in python is there a linked list or deque where you can have references to intermediate nodes and remove them and insert before/after them?
with collections.deque, you can’t
wispy rune
Hello! Someone know why this is returning none?
import re
reg = re.compile(r'@\ \d{4}')
value = reg.match("Copyright @ 2015 Panini")
print(value)
Thanks
fervent saddle
What do people usually use when they want one which can do that?
lean dome
What do people usually use when they want one which can do that?
most people never want that. The fact that there is no builtin type that does it is indicative of it not being a common need.
What's your use case?
lean dome
I wouldn't use a linked list for that, I'd just use a regular list as a circular buffer
fervent saddle
So you have the sequence of numbers with None at the start or end, and you just move the None forward each time you remove from the start?
Or something like that?
lean dome
I think, on the ith iteration, you would just set arr[i % len(arr)] = arr[(i + k - 1) % len(arr)]
you could do it with a None that you move around, but you could also just keep track of the index. It moves forward 1 on each iteration.
fervent saddle
And you just replace the start position with the value that gets added to the end, and move the start position forward by 1?
So that the replaced position becomes the end position?
lean dome
if you view the numbers as a ring, the two operations they can do - write something to the end, and remove what's at the beginning - can be viewed as just overwriting a single value - the index that is at the start of the current sequence is also one past the end of the current sequence, so adding something to the end and removing the start is just overwriting the current start value
lean dome
So that the replaced position becomes the end position?
yep, exactly.
fervent saddle
Yeah. That seems like a better solution to it
I read that linked lists are almost never ideal, but does that even apply to algorithm exercises?
lean dome
yes - they're rarely used in the real world because they're slow and inefficient. They're rarely used in algorithms exercises for the same reason.
a hash table, dynamic array (regular Python list), or a tree is almost always a better choice than a linked list.
fervent saddle
Alright, thanks for the help. I’ll keep that in mind
cerulean river
hey guys, I have a question on an array algorithms question I am doing on Leetcode : https://leetcode.com/problems/plus-one/
I have solved this problem with the code below
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
new_number = []
temp = ''
for i in digits:
temp = temp + str(i)
temp = int(temp) + 1
temp = str(temp)
for char in temp:
new_number.append(char)
return new_number
however this code typically outperforms mine (well others do too but this beat those too and the one that beat this for some reason I cannot see when I click). My solution oscillates between 20ms - 40ms runtime I can see why my algorithm is less efficient since it needs 4 passes of the array and string but I am not understanding the return statement. I see that they are first making a string out of digits then they are iterating over the newly formed string and incrementing by 1 but what is the purpose of the int(i) . I am not getting what this is doing and how this is resulting in better runtimes than mine?
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
'''
num = 0
for i in range(len(digits)):
num += digits[i] * pow(10, (len(digits)-1-i))
return [int(i) for i in str(num+1)]
'''
num_str = ''
for i in digits:
num_str = num_str + str(i)
return [int(i) for i in str(int(num_str)+1)]
unkempt umbra
i guess the new_number.append lookup might take a bit longer but also why do you print the list
int(i) is to turn the digit (string) back into a number (int) btw
cerulean river
Oh that was me checking if my code was working properly. Oops meant to take that out
cerulean river
My trails with the same code lol.
That code is 16ms according to Leetcode's metrics. Still below anything I hit
unkempt umbra
your code and the other code does basically the same thing lol. what if you store the new_number.append method into a variable and use that instead?
wait imma just create an account to try it lol
cerulean river
Yeah I just used this code to test 5 times in a row. We seem to match performance and or I beat it haha.
unkempt umbra
xD
cerulean river
I guess I done goofed sorry to waste your time. If you wanna talk about this I am down. Maybe I will learn something new.
unkempt umbra
wait hol on wdym you used the code to tets 5 times in a row
did u save the method into a variable?
and then that was faster
or was your original faster lol
cerulean river
I used the second solution the one I was asking about
my original was often times faster not always though
unkempt umbra
lol yea when you're down to milisecond levels, it ain't that accurate anymore
but if your code was slower by a factor of 10 or something
then like yea there might be a real problem causing it
cerulean river
Sensible
mighty kestrel
hi guys sorry maybe this is the wrong topic but if anyone can help me doing a simple script can dm pls?
old rover
hi guys sorry maybe this is the wrong topic but if anyone can help me doing a si...
wrong channel
hearty creek
Hello, I have a question, is there a way I can place entire this output inside one variable, with space between like this? So far I managed to set it each value under each other, but I could get entire array value space between, this is how it is supposted to look https://prnt.sc/10z4qfn
rancid patio
this seems rather simple but I believe I am getting an infinite loop
for i in range(len(nums)):
if nums[i] == 0:
nums.insert(i,99)```!e
nums = [1,0,4,10,14]
for i in range(len(nums)):
if nums[i] == 0:
nums.insert(i,99)
print(nums)
@mint jewel :white_check_mark: Your eval job has completed with return code 0.
[1, 99, 99, 99, 99, 0, 4, 10, 14]
Trees!!!!
I'm trying to understand how preOrder, inOrder, postOrder, levelOrder recursion works.
old rover
I'm trying to understand how preOrder, inOrder, postOrder, levelOrder recursion ...
I like this for that: https://youtu.be/WLvU5EQVZqY
also this: https://youtu.be/BHB0B1jFKQc
fiery cosmos
hi
how can i make a compiler?
example:
@include os
definition(
name: mydef
code: <
log<'hi'>
>
)
output:
import os
def mydef():
print("hi")
You start by reading compiler books
Idk what kind of help you expect for a question so vague
fiery cosmos
Maybe I am missing a module that I provided the solution and I am missing it
spring jasper
I can recommend craftinginterpreters.com tho its in java and c
But the ideas are the same
old rover
do compilers have anything to do DS/algos
spring jasper
I'd say its a #software-architecture topic tbh
fiery cosmos
how can i make a compiler?
example:
```
@include os
definition(
name: mydef
code...
a = open('mycode.lang')
b = a.read()
b = b.replace('$include', 'import')
I mean something like that, the difficulty is in stripping part of a string from brackets or parentheses and repositioning it
but this does not work like that
lean dome
You don't really need a compiler for this. You need to parse your file, walk the parse tree, and emit Python code for each node in the parse tree.
You could try using something like https://tatsu.readthedocs.io/en/stable/use.html or https://www.dabeaz.com/ply/ply.html
fiery cosmos
thanks
It is not to create a programming language, but to facilitate the creation of mods of an application
fiery cosmos
@lean dome
lean dome
Why the ping? I've already told you what to explore to build this.
lunar otter
how long does it take to read the whole python documentation?
onyx root
how long does it take to read the whole python documentation?
you don't have to read all of it.
lunar otter
but if im about to learn from the documentation alone what would be the best strategy to retain information from the documentation?
old rover
to use the info from the documentation
fervent saddle
You probably have to do practice exercises, I think anyone who could become good at python or any programming language just by reading the documentation would have to be like 1000 IQ
old rover
there are some great project ideas on github and also Ned's blog
lunar otter
but theres like so many pathway on python lmao
old rover
using those concepts in projects is going to be far more helpful than doing them in Hackerrank
lunar otter
u can do web dev or ai
lean dome
but if im about to learn from the documentation alone what would be the best str...
Most of the documentation is meant as a reference - it's not meant to be read and retained, it's meant to allow you to look things up. But this part of the docs is meant to be read: https://docs.python.org/3/tutorial/
that's a pretty good overview of the entire Python language.
lunar otter
thanksss
im having a dilemma about learning python on ebooks alone or through the docu
i've red learn python 3 the hard way but there's still so much to learn
lean dome
is it your first language? And if so, do you already know the basics?
lean dome
ok. Then I'd definitely try reading the tutorial, and see where that gets you.
My usual complaint with it is that it moves a bit too fast for people who haven't ever programmed before - but if you know 2 languages reasonably well already, it should be paced just fine for you.
old rover
I bet python error messages are much nicer to read than C++'s error messages
that's what I found
lean dome
C++'s compiler errors messages are usually about on par with Python's runtime error messages. C++ gives no error messages at runtime, though, it just crashes. And C++'s template error messages are awful. Much better than they used to be, but... still a complete pain to read.
lunar otter
its also hard to code on c++ without dev c++ ide lmao or is it just me
when it comes to python i can just use sublime text
lean dome
I do all of my C++ coding in Vim, personally. I don't like IDEs.
old rover
not sure I only used sublime like once
lunar otter
i tried compiling c++ scripts on cmd but it takes too many commands tho
like 2 commands 1 for compiling and 1 for running
on python you just run the script and thats it
old rover
can someone give me an ELI5 explanation of balance in trees
I'm watching a video and getting confused
what does left-heavy v right-heavy even mean
lunar otter
what does EL15 mean
old rover
explain it to me like I'm 5
a simple explanation
the formula is B(n) = H(Tl) - H(Tr)
and with avl trees the balance is always less than or equal to 1
spring jasper
x-heavy means that x side is taller
Or deeper?
Not sure what the correct term is
old rover
I'm unsure but maybe once I code it it'll make more sense
dude this whole time I thought AVL stood for some crazy shit
it doesn't actually it stands for the inventors names
fiery cosmos
hi
Is there a way for an entry to end like this:
[{"command": {"name": "!ping"}, {"code": "$send[hello!]"}, ["$send[hello!]"]}]
input:
command(
name: !ping,
code: [
$send[hello!]
]
)
@lean dome something like that I meant
old rover
🥴
def getHeight(self, root):
if not root:
return 0
return root.height
def getBalance(self, root):
if not root:
return 0
return self.getHeight(root.left) - self.getHeight(root.right)
isn't this stuff considered unpythonic or something
they look like getters to me
lean dome
they are, and it is unpythonic.
old rover
are AVL trees really that important
like can I just move back to hash maps
I don't know if I should be spending this much time
sorry I meant hash maps
spring jasper
Yes they are important
spring jasper
Bad python devs, half decent java devs
old rover
can I just use the getters and then figure out how to change the code
so I don't need getters
I didn't get that far into Java to even know what getters and setters are
or why they're necessary in Java
grizzled schooner
(disclaimer idk much about Java) Java has private variables, so you can’t access them from outside the class without getters and can’t change them without setters
they’re just methods that return or attributes
old rover
oh ok
grizzled schooner
whereas in python you can simply access and modify using object.attribute
so basically removing them shouldn’t require many changes in the code
old rover
ok sounds good
lean dome
I would just focus on one thing at a time, honestly.
yes, getters and setters aren't used in idiomatic Python code. But your goal right now isn't learning how to write idiomatic Python code, it's learning how some data structures and algorithms work.
no reason to focus on too many things at once. Focus on learning the DS&A, then worry about learning the Python idioms later.
getters and setters work in Python, they're just not the best tool for the job.
lean dome
yeah.
lean dome
(disclaimer idk much about Java) Java has private variables, so you can’t access...
and... You can make attributes public in Java, too. The reason why getters and setters are idiomatic in Java, and are not idiomatic in Python, comes down to a feature that Python has that Java doesn't: properties.
In Java, if you expose direct access to your attributes, you can't ever lock that down afterwards. If you discover that you need to do some validation, you can't - you're out of luck, because you've told users they can do pants.size = 42, and nothing stops them from doing pants.size = 42000 - there's nowhere where you can hook in to add that validation.
so instead, you're encouraged to do everything with setters like pants.setSize(42), because the author of the Pants class can add validation into that setSize function later, if they need to.
In Python, though, we have a way to make it so that pants.size = 42000 does run some code that we control, through properties. And so Python doesn't have the same problem as Java - we get the best of both worlds. In Python, it's possible to use the nicer x.y = z syntax, and add validation as needed to it.
grizzled schooner
cool 👀
yeah, I knew that private variables were just convention, but I wasn’t really sure why
molten dust
hello guys i ned help
old rover
help with what
molten dust
i have homework
to write something in algo
but i dont understanf it
if someone can explain
old rover
what's the algo called
what algo is it
is it a sorting algorithm?
is it a searching algorithm?
molten dust
i hink its sorting
or writing
i need to wrtie something like 2x3=6
she said somethin we need to write start and end
my teacher
but she does not know how to explaing good
only how to make us more confused
but nvm
can somebody explain me this
like this
start
hello
end
but
sometimes its
start
end
hello
thats confuisng me
sry for spaming 😦
old rover
I forgot you have to typehint in Java 🥴
you can do it in python too
class AVLTreeNode:
def __init__(self, key, val= None, bf =0):
self.key = key
self.val = val
self.left = None
self.right = None
self.parent = None
self.bf = bf
self.height = 1
def get_height(self, root: AVLTreeNode) -> int:
if not root:
return 0
else:
return root.height
so uh what's wrong with this
I just put whatever the tutorial did
the problem is root: AVLTreeNode
I don't think I spelled anything wrong
I autocompleted it
worthy fjord
ok, same question as yesterday I have been trying to come up with a solution but its very time consuming toi iterate over all possibilities, so, is there an algo to assign squares of different heights and lengths to optimally cover the blue bars, given a fixed set of possible rectangles?
X axis is 15 minutes buckets per tick, and y graph is count of people needed at that time due to tasks
i have the task array to that looks like a gantt, from the gant i gather this
now i want to turn this into a shift schedule
agile sundial
I forgot you have to typehint in Java 🥴
lol it's not typehinting, it's just typing
probably the issue with
def get_height(self, root: AVLTreeNode) -> int:
is you need from __future__ import annotations to have forward referencing annotations
old rover
@agile sundial idk what that means
worthy fjord
i have the feeling its a variation of bin packing
agile sundial
```python
class AVLTreeNode:
def __init__(self, key, val= None, bf =0):
se...
what does your get_height do? why does it take another node?
old rover
@agile sundial I don’t really even know it just gets the height of a given node in a tree
heavy cloak
ye thats correct i forgot where the ifs and for loops whent
lunar otter
if i have [x, y,z] coordinates having both x,y,z highest value is 1 how can I calculate the total permutations?
[[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 1], [1, 1, 0], [0,1,1]]
these are the permutations, im curious as to how to calculate the total permutations
jolly mortar
There's two possible states for each of x y and z (0 and 1), so its 2^3=8
Its essentially like counting in binary from 0 to 7
lean dome
And you missed 101
lunar otter
yepp i forgot abt that but what formula can I use to calculate all of the permuatations?
coz when i try 3! it only gives 6 but theres 7
quasi basalt
can somebody help with pandas
ValueError: If using all scalar values, you must pass an index
tardy pilot
Hello, I need help with comparing coordinates to each other. I have data that contains 1-3 sets of coordinates for each item (Example: Id, [x,y],[x,y], [x,y]), and I need to find the coordinate set with the largest x (or y) value, then look at all the coordinates of the other items to find one that matches. I feel like this is pretty straightforward but I am struggling with it.
split obsidian
Is there a package for visualizing data structures and how they mutate as we step through?
native oar
what kinda data structures would i use to represent stations and railway information?
For station information i have Station name, latitude, longitude and
for railway information i have Tube line, from station, to station and i should represent these using some data structures. From what im thinking i would think of this as a weighted undirected graph, right?
I would need to be able to find the minimum distance from one station to another, minimum number of stops from one station to another.
old rover
@split obsidian there’s no package I know of but try visualgo
it’s a site that visualizes data structures and algorithms
old rover
There’s also another one but I forgot the name
midnight sorrel
Hi, I have an interesting task and I'm quite lost on what algorithm / approach should I use.
Task:
Find minimum possible cuts within a main rectangle(s), given x number of smaller rectangles and return those cuts.
All cuts should be from the start to the end. It's not possible to make a cut only until the half of the main rectangle.
When one main rectangle is out of area, it is possible to take another main rectangle of the same size and cut the remaining from that.
So let's say I have a rectangle (in this case square) 5x5
Now I'm given two input rectangles of which are:
1x1 and 1x2
So I should cut the rectangle to 1x5 and 4x5, then the 1x5 cut to 1x1 and 1x2 and I will be left with 1x2 (spare) and 4x5 (spare)
Also if I have for example rectangle 7x7
and I'm given two input rectangles of size 6x6 and 6x6
Then It should take another main rectangle and start cutting off of the second one.
vocal gorge
what kinda data structures would i use to represent stations and railway informa...
that does indeed sound like a graph.
old rover
class AVLTree(BST):
def __init__(self):
super().__init__()
def insert(self, key, val=None):
"""
Public insert function to insert a node into an AVL Tree.
:param key: key of node to be inserted
:param val: corresponding value
:Time: O(log(n))
:Space: O(log(n))
:return: none
"""
self.root = self._insert(self.root, key, val) # Returns root of resulting tree after insertion - update it
self.n += 1
since when do classes take paramaters
vocal gorge
since when do classes take paramaters
class AVLTree(BST):
...you mean this? This is inheritance; AVLTree is a subclass of BST.
old rover
class AVLTreeNode:
def __init__(self, key, val= None, bf =0):
self.key = key
self.val = val
self.left = None
self.right = None
self.parent = None
self.bf = bf
self.height = 1
def get_height(self, root: AVLTreeNode) -> int:
if not root:
return 0
else:
return root.height
class AVLTree:
def __init__(self):
self.root = None
def insert(self, key, val = None):
self.root = self.insert(self.root, key,val)
def _get_height(self, root: AVLTreeNode) -> int:
if not root: # empty tree means height of 0
return 0
else:
return root.height # return instance var height
this is what the tutorial does too
I don't get what's wrong
vocal gorge
...what's your question? What do you believe to be wrong here?
vocal gorge
I don't really get what you mean
vocal gorge
I still don't get what "issue" are you talking about.
old rover
it's being underlined in red
vocal gorge
what's the actual error, when you hover over it/look in Problems?
mint jewel
can't type hint with a class that you are defining right now
you can use "AVLTreeNode" to fix that, and typecheckers will still understand the type hint
vocal gorge
can't type hint with a class that you are defining right now
oh, nice idea, I was looking at the wrong root: AVLTreeNode typehint
old rover
so that get_height function should be outside of the AVLTreeNode class?
dude why didn't they make it clear in the tutorial then 🥴
they have two functions both called insert 🥴
I didn't know that was even possible
vocal gorge
they have two functions both called insert 🥴
...where?
outer lake
If you're a visual learner or just like to view visualisations of algorithms, check out https://visualgo.net/en and https://www.cs.usfca.edu/~galles/visualization/Algorithms.html. Both websites have nice and interactive visualisations of a lot of the core algorithms.
old rover
!pastebin
halcyon plankBOT
old rover
I put it in a pastebin bc it's very long
oh well
there is an underscore before insert for the next function
old rover
you can call a function when the function is defined after the call?
🥴
this is what I'm talking about
they call getBalance and then later on in the code getBalance is defined
class TreeNode():
def __init__(self,val):
self.val = val
self.left = None
self.right = None
self.height = 1
class AVL_Tree():
def insert(self, root, key):
if not root:
return TreeNode(key)
```if there is no root
what does returning TreeNode(key) do?
half lotus
Yes it's possible because all functions here are defined before they are executed
The call is happening within a function
old rover
oh ok
not sure what TreeNode(key) does
if not root means if there is no root
but what does TreeNode(key) do?
half lotus
Creates an instance of the node class which contains the given.key
old rover
is it bad that I literally watched a 20 minute video on balance in trees
and I still don't get what it means
old rover
"Binary search trees can be balanced (applying a data algorithm to rearrange the nodes to prevent poor data arrangement [ex. formatting data to look like a linked list which has a less ideal search complexity of O(n)]."
I saw another explanation that balanced means shorter branches
half lotus
Balance is the difference between the heights on either side
old rover
the height of the left minus the height of the right
half lotus
The smaller the difference, the more balanced it is
old rover
so like over here
what indicates that the height of the left child is 1?
bc it has two children?
that would make sense
that the right child is 0 bc it has no children
mint jewel
it has height 1 because the lowest child of it has height 0.
old rover
maybe my problem is figuring out how to determine height in a binary tree
mint jewel
in essence, its how many "layers" the tree has
for example, how high is the tree in the image
old rover
2
mint jewel
yes
does the mathematical explanation of a balanced tree in that image make sense to you
mint jewel
yes
mint jewel
height of 1 is 1, since it has one "layer" below it
old rover
oh
it goes by layers
ok
ok then I guess it makes sense
def insert(self, root, key):
I don't know what key is
is key the value you're inserting into the tree?
half lotus
The value the node will contain
old rover
oh ok
def leftRotate(self, z):
y = z.right
T2 = y.left
# Perform rotation
y.left = z
z.right = T2
# Update heights
z.height = 1 + max(self.getHeight(z.left),
self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left),
self.getHeight(y.right))
# Return the new root
return y
what's z 🥴
z seems like a parent
and y is the right child of the parent
vocal gorge
the node to rotate.
old rover
couldn't they call it that
instead of z 🥴
for a site that has a lot of people reading and reusing their code they could use some more helpful variable names
vocal gorge
or docstrings, or both, yeah
old rover
def left_rotate(self, node_to_rotate):
right_child = node_to_rotate.right
left_child_of_right_child = right_child.left
somehow this
makes this
def leftRotate(self, z):
y = z.right
T2 = y.left
# Perform rotation
y.left = z
z.right = T2
even more confusing
yeah I don't really know what to call them
yay guys
I can finally leave AVL tree hell
old rover
so uh
are hash maps easier than trees?
it doesn't really matter I'm going to learn them anyways
agile sundial
there's some annoying math (probability, random analysis) that goes into proving things with them, but they're ok
old rover
ok sounds good
amber vector
hi I am looking at a library and i see you take one node out of a matrix of nodes, so you do node=nodes[y][x] later in the code this is done ((node.x, node.y) in path I don't understand what the .x,.y does. Can anybody help?'
amber vector
for y in range(len(self.nodes)):
line = ''
stpsLine=0
for x in range(len(self.nodes[y])):
node = self.nodes[y][x]
if node == start:
if (nodes[y][x+1]==start):
line+='>'
else:
findDirection(y,x,self.nodes)
stpsLine+=1
elif node == end:
line += end_chr
stpsLine+=1
elif path and ((node.x, node.y) in path or node in path):
line += path_chr
stpsLine+=1
its form this library -> https://github.com/brean/python-pathfinding/tree/main/pathfinding/core the Grid.py file
old rover
pathfinding is way above my level hopefully someone else can step in 🥴
agile sundial
that seems like a strange way to handle things 🤔
why does he have a node if he's also using an adjmat
velvet plume
Hello,
This is the solution to the dynamic programming coin change problem. The recursion is just driving me crazy. Can someone please explain it to me -
import sys
class Solution:
def leastCoins(self, coins, amount):
'''
:type coins: list of int
:type amount: int
:rtype: int
'''
if amount < 1:
return 0
return self.coin_change(coins, amount, [0] * (amount + 1))
def coin_change(self, coins, remainder, cache):
if remainder < 0:
return -1
if remainder == 0:
return 0
if cache[remainder] != 0:
return cache[remainder]
system_max = sys.maxsize
minimum = system_max
#print("Minimum = ", minimum)
for coin in coins:
change_result = self.coin_change(coins, remainder - coin, cache)
if (change_result >= 0 and change_result < minimum):
minimum = 1 + change_result
cache[remainder] = -1 if (minimum == system_max) else minimum
return cache[remainder]
a = Solution()
coins = [1,2,5]
amount = 11
a.leastCoins(coins, amount)
so with a map
you can have a key that has multiple values?
and if you want to add a value to that key it's just the dictionary name ["key].append(99)
so do dictionaries have a built in hash function too
since dictionaries are hash maps in python
so a collision is when the hashing function hashes 2 keys and the values end up being the same
do I need to implement hash tables on my own? or can I just use dictionaries?
fervent saddle
Python dictionaries use the object’s __hash__ method to find out what its hash value should be. And by default, if you have a user defined class without a __hash__ method, they use the object’s memory address.
Python dictionaries deal with collision resolution, you don’t have to worry about implementing that yourself if you’re using a python dictionary
old rover
what is udacity saying then 🥴
old blade
hello
uhh i need help
its more of a math question
but its based around algoirthms
can someone help
agile sundial
what is udacity saying then 🥴
maybe you're misinterpreting it, what did they say?
old blade
its a quick question
agile sundial
can someone help
maybe, but we can't know if you don't ask
old blade
maybe, but we can't know if you don't ask
ik its a dumb question and i should know this but i kinda forgot. What are constant factors
in algoirthm terms
algorithm*
agile sundial
talking about big O notation?
old blade
talking about big O notation?
ig
wherver it fits into
with algorithms
so if its with big O than yeah
agile sundial
it's just something that doesn't depend on the input, multiplied by something
old blade
it's just something that doesn't depend on the input, multiplied by something
wdym im confused
agile sundial
say we have this function
def loop_twice(L):
for x in L:
print(x)
for x in L:
print(x)
```what is the big O of this functionL
agile sundial
what is L
old blade
its what is defined with loop_twice
agile sundial
ok, the time complexity depends on the length of the list, right
agile sundial
right
but if we compare it to this function
def loop_once(L):
for x in L:
print(x)
```the first function has double the number of loops, so it does twice the work. that is the constant factorit also is based on the algorithms way of sorting if im correct
agile sundial
the big O of both those functions are the same, but they still differ by a constant factor
old blade
ok so like the first function (for x in L:) doubles the amount of loops and it does twice the work
meaning its a constant factor?
old blade
sadly im not quite understanding
agile sundial
the two functions have the same time complexity right?
old blade
the two functions have the same time complexity right?
yes
wait no why would they have the same time complexity one of the functions does twice the work
just when i thought algoirthm anaylsis couldnt get any harder
agile sundial
right, so let's go back to how we determine the time complexity
agile sundial
or actually, if they are different, what are the time complexities of them?
old blade
by the length of the list and the sorting method used
agile sundial
sorting method? we're not sorting anything here
old blade
sorting method? we're not sorting anything here
oh yeah ur right sorry
for some reason i think algorithms are all sorting algos
thats the main thing i have been studying
fervent saddle
what is udacity saying then 🥴
A key can map to a list
Probably is what it’s saying
agile sundial
maybe talking about hash collisions
old rover
maybe talking about hash collisions
oh yeah I totally misread it
they were saying append bc the value was a list
so ig my question is
do I have to implement a hash map like the G4G people do?
or can I just use a dictionary
agile sundial
using dict kinda defeats the point of making one yourself
you dont have to use chainint though
old rover
not sure what chainint is
agile sundial
chaining
old rover
oh ok
Udacity says normally the key gets hashed into a value and it's stored in an array
but you can store it in a bucket to avoid collisions
old rover
so once I finish this and graphs
should I be practicing using binary search?
or should I be using leetcode
I don't think it really matters
agile sundial
any way you practice is good
old rover
should I be doing these leetcode questions by sections?
like linked lists first and then searching/sorting algorithms
agile sundial
i don't, it might work for you ¯_(ツ)_/¯
lean dome
or can I just use a dictionary
The whole point of learning data structures and algorithms is to learn how things like dictionaries work, and what they're good at, and what they're bad at. You'll probably never need to implement your own hash table IRL, you'll use one provided by the standard library of whatever language you're using. The point of knowing how to do it is understanding and internalizing how they work.
old rover
The whole point of learning data structures and algorithms is to learn how thing...
the same way you learn about arrays but you use lists in python
bc python abstracts things
lean dome
Pretty much every language does.
lean dome
Almost every language has a built in dynamic array type.
lean dome
Right. Java's ArrayList and C++'s vector and Python's list are all dynamic arrays.
fiery cosmos
basically vectors in java are the thread safe versions of arraylists
agile sundial
yeah
lean dome
Both are dynamic arrays, though.
old rover
are graphs like the hardest data structures
agile sundial
not really?
fiery cosmos
Both are dynamic arrays, though.
yes. but arraylists are not thread safe
old rover
oh bc the students I was talking to said they found graphs the hardest
but their experience doesn't determine my experience so
agile sundial
so once I finish this and graphs
it'd be useful to also learn some algorithms to go along with the data structures
old rover
well I know binary search, sorting algorithms, and I'll be learning BFS + DFS
also graph traversal
agile sundial
graph traversal would be bfs and dfs
lean dome
Possibly, but also things like Dijkstra's Algorithm
fiery cosmos
I need some help. I am a bit unsure about the 2nd part of this question. is the function f(n) here Theta(n^m)?
here, k = {0, 1, 2, 3} & m = {0, 1, 2}
I am thinking it's not because the the condition 0 <= c1*g(n) <= f(n) <= c2*g(n) is not satisfied for k=3?
lean dome
I need some help. I am a bit unsure about the 2nd part of this question. is the ...
no - big o, big omega, and big theta are all forms of asymptotic notation. They're allowed to cross the function, as long as there exists some point after which the relationship holds
fiery cosmos
I am not sure if i am following...
lean dome
it doesn't matter whether it's satisfied for k=3 - it matters whether there is some n above which it always holds
lean dome
yes, but n isn't, and we're looking at a function that's f(n)
agile sundial
yeah
fiery cosmos
so, since it holds for k={0, 1, 2} it doesn't matter if it doesn't hold for k=3?
but now I am confused. why shouldn't it matter for k=3?
lean dome
I'm having trouble wrapping my head around this question, honestly. I think in order to make sense of it, you're supposed to actually plug your student id into the question, maybe?
fiery cosmos
our student ids are just integers
lean dome
I'm not sure if it doesn't or not - but I think it might
lean dome
and if I'm gonna work it out with some numbers, might as well work it out with the right numbers
so - what's k and what's m for you, @fiery cosmos ?
fiery cosmos
k = {0, 1, 2 ,3} and m = {0, 1, 2}
since k = id % 4 and m = id % 3, and id is just an integer
wait a minute....is the question asking about my id specifically or just any id in general? lmao
lean dome
the answer to this question depends on what m and k are.
and m and k depend on the person answering it, I think.
I think you're supposed to use your own student id.
fiery cosmos
ah.....if that's the case, it makes things much much more simple
lean dome
it's very confusingly worded - but that's the only way I can make sense of it.
fiery cosmos
thanks for the help. I really appreciate it.
hallow vortex
Can anyone help me with this?
what I know about dfs is that there are two versions. we mark visited before call and after call.
def solution1(start):
def dfs1(cur):
for nei in cur.neighbors:
if nei not in visited:
## mark visit before call
visited.add(nei)
dfs1(nei)
## drive dfs1
visited = set()
visited.add(start)
dfs1(start)
def solution2(start):
def dfs2(cur):
## mark visit after call
visited.add(cur.val)
for nei in cur.neighbors:
if nei not in visited:
dfs2(nei)
## drive dfs2
dfs2(start)
However, I tried version 1 (visit mark before a call) to https://leetcode.com/problems/clone-graph/ But it gives me an error.
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
class Solution:
"""
def dfs1(cur):
for nei in cur.neighbors:
if nei in visited: continue
visited.add(nei)
dfs1(nei)
visited.add(start_node)
dfs1(start_node)
"""
def dfs(self, cur, visited):
new_node = Node(cur.val)
# visited[cur.val] = new_node
new_neighbors = []
for nei in cur.neighbors:
if nei.val not in visited:
visited[nei.val] = nei
new_neighbors.append(self.dfs(nei, visited))
else:
new_neighbors.append(visited[nei.val])
new_node.neighbors = new_neighbors
return new_node
def cloneGraph(self, node: 'Node') -> 'Node':
if node == None:
return None
visited = {}
visited[node.val] = node
return self.dfs(node, visited)
This is what I tried
old rover
this has nothing to do with your code
but using a pastebin with large blocks of code is nice so it doesn't clutter the channel
hallow vortex
how can I use a pastebin? TBH, Idk what it is
lean dome
!paste
halcyon plankBOT
shut root
I'm trying to pair target and gmail passwords based on alike emails in the return format of {same_email,[target_password,gmail_password]}, but the passwords that I get back are giving me the same values even though they're different in my text files:
https://paste.pythondiscord.com/kurohuqige.lua
returns : {'ioawefjiowejiof@hotmail.com': ['cwefawefecwce\n', 'cwefawefecwce\n']}
halcyon plankBOT
shut root
!pastebin
cerulean river
So I am solving problem 283 on Leetcode (https://leetcode.com/problems/move-zeroes/), correct solution aside, I am not sure why I am getting an IndexError, I thought I accounted for length of nums.
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
i = 0
j = 0
count = 0
while j < len(nums) and i < len(nums):
if len(nums) == 1:
break
if nums[j] == 0:
while nums[j] == 0:
j += 1
temp = nums[j]
nums[i] = temp
nums[j] = 0
i += 1
j += 1
This is the error message LC is giving me and the condition that is causing it.
fiery cosmos
J can run off the end of the list in the inner while loop
And why bother having if len(num)==1 within the loop? 
spiral wind
I have an interesting formula problem: How can I calculate the incremental cell number from the row and col numbers?
1 2 3
1 1 2 3
2 4 5 6
3 7 8 9
I'm seeing patterns, but I can't really sort it out
spiral wind
got it: col + (colMax * (row -1)) if anyone is interested
hearty creek
#fourth row
if val:
arranged_problems += "\n"
for test in problems:
blank = " " * 4
num = str(eval(test))
width = max(len(test[0]), len(test[2]))
result_width = len(num)
arranged_problems += f"{blank}"
if not "-" in test:
arranged_problems += f"{num:>{result_width + 2}}"
else:
arranged_problems += f"{num:>{result_width + 1}}"```
This is my code, and here is my output:
https://prnt.sc/110vhaq
Basically, I'm trying to modify my result in each column to be right allign
cerulean river
And why bother having `if len(num)==1` within the loop? <:rooThink:7310603538399...
I initially did not have this, but once of the testcases [0] was failing so I thought it was an edge case when len(nums) == 1
cerulean river
J can run off the end of the list in the inner while loop
I put in checks in other versions of the code to check for if j < len(nums) but then I i gets an IndexError. Not quite sure why or how to prevent this.
vital rune
how do I fix a binary search tree with two nodes swapped?
I have to put their values back in the right place
but I'm not sure how to go about finding those nodes
half lotus
You can do an in-order traversal and check where the sequence stops increasing.
vital rune
I would do this with a recursive function right?
half lotus
Doesn't have to be recursive but the recursive algorithm is simpler to write.
fiery cosmos
Is there an easy way to make the simplex algorithm in Python where you can input numbers and then the computer pivots the numbers using the simplex algorithm?
fiery cosmos
can i have help pls
vital rune
Can anyone help with finding values in wrong place in binary search tree using inorder traversal?
vital rune
I'm not sure how to implement it
This is me trying to print out the mistakes but its not printing the right ones
I'm supposed to swap 2 inccorectly places nodes but I'm not sure how to dothat
sly verge
I have a two dimensional np array shape (100,14). I want to slice the array such that I keep a shape (100,2). The "2" should be (n,0) and (n,m), m being any arbitrary number. I am currently slicing but can only get adjacent columns. How can I select any pair of non-adjacent columns?
X = np.asarray(mat_features)
XS = X.shape
X = X[0:XS[0],0:2]
This is what I have now
vocal gorge
I have a two dimensional np array shape (100,14). I want to slice the array such...
You can pass an array of ints as any index.
So X = X[:,[0,m]], say. Might need to cast it to np.array.
sly verge
works great, thank you @vocal gorge
fiery cosmos
hello, i'm new here and i really need help
i'd like to program pixels to create an image
and i have no idea where to start
any information would be much appreciated
sage quartz
Any good tutorial for recursion? I know the basics, but still not enough to understand backtracking...
stone hound
Any good tutorial for recursion? I know the basics, but still not enough to unde...
well then i will say solve a lot of problems on recursion from gfg you will be good to go
dry crow
I have a question regarding algos. I have two versions of sieve algorithm (sorry the code is nonpython but i want a general idea), sieve1(1000) resulted in 32 allocations with 1.07MiB vs sieve2(1000) resulted in 2025 allocations with 314.48KiB. Execution time for each is 2.268 milliseconds and 589.668 microseconds, respectively. What are allocations? Is having a large number of allocations bad? What should i look out for when writing algorithms (e.g. trade-offs, speed?, memory?)?
wary hatch
https://youtu.be/wRH2I6IN4BE
And then this https://youtu.be/oBt53YbR9Kk
honestly, nobody has explained recursion to me better than this guy
clear adder
So, basically I want to make a for-loop chain in which it asks me what word I wanna loop how to make that
floral dew
python just released a fully-developed official pep that'll change booleans forever?!?!?!? and it's gonna be implemented in 3.11
link -> https://docs.google.com/document/d/1gvq4rdMVzrEFAlVCSPvGs4mstI8831seOEDpwiRRWW4
bronze sandal
Can someone suggest me a book or video tutorial on discrete math?
someone told me that I need to learn it before learning DSA
I've found the MIT's free course on youtube but it is like 8 years old
should I just go with it?
agile sundial
arguably dsa is discrete math
bronze sandal
any good resource to learn it?
agile sundial
mit's 6.006 is pretty good iirc
bronze sandal
the math
agile sundial
oh, i don't know of specifically discrete math courses
the mit one i mentioned is a dsa course
bronze sandal
mit's 6.006 is pretty good iirc
ya but it is very old...math doesn't change but is it still the best course out there?
agile sundial
wdym very old
bronze sandal
the mit one i mentioned is a dsa course
I suppose they have discrete math as well
soft totem
guys i have one small doubt ```
t1 = [i for i in range(n)]
t2 = [i for i in range(n)]
even if this considered as O ( n ) then how is it diff from ```
for i in range(n):
for j in range(n):
pass
``` i am sure this one is O ( n^2 )
trim fiber
guys i have one small doubt ```
t1 = [i for i in range(n)]
t2 = [i for i in ran...
It's O(2 * n) which means O(n)
soft totem
It's `O(2 * n)` which means `O(n)`
i see thanks , so in the end all the constants are ignored
trim fiber
i see thanks , so in the end all the constants are ignored
Yep, consts may be ignored as far as I remember from studies
lean dome
guys i have one small doubt ```
t1 = [i for i in range(n)]
t2 = [i for i in ran...
The one with the loops nested runs N sub iterations for each of N iterations. That's 1 total operation for n=1, 100 total operations for n=10, 10000 total operations for n=100. That's O(n^2).
The one with the loops not nested does 2 operations when n=1, or 20 when n=10, or 200 when n=100. That's O(2n), which - since constants are dropped in asymptotic notation - is O(n)
But just by plugging in some real numbers for n, you can see that the growth rate of the nested loop is much higher.
woeful gorge
Is there a built in function that returns true if one atleast one of the elements in a list statisfy a condition