so like
#algos-and-data-structs
vocal gorge
if you pick the first element as the pivot each time, reversed(range(n)) would be a worst case for you with compexity O(n^2), I think
vocal gorge
on deterministic ones, yes
https://en.wikipedia.org/wiki/Quicksort#Choice_of_pivot
check this out
agile sundial
yea
fiery cosmos
and the semaphore etc.etc ...
eager hamlet
So I’m doing this problem: https://oj.uz/problem/view/JOI18_commuter_pass, and I can’t seem to figure out how to calculate the cost of a path. I can easily tell if a single point or edge is on a shortest path for the commuter pass, but I can’t tell if a series of paths are, resulting in an incorrect output.
Could anyone help?
(ping 2 reply thx)
proper zenith
anyone knows what the running time of something like v**n would be? is it constant?
runic tinsel
log probably
you square v logn times
yep, log n for integers
constant for floats
winged vale
You are given a set of points on a line and a set of segments on a line. The goal is to compute, for
each point, the number of segments that contain this point.
naive will be m*n
any optimized way?
glossy breach
Yes
I'm not sure what the algorithm is called but I usually call it prefix sum trick
So basically you maintain an array called a of length k
We call pre the prefix sum of array a
Notice that by adding 1 to a[i], you are adding 1 to pre[i] -> pre[k]
So when you add a segment, just add 1 to a[l] then add -1 to a[r + 1]
pre[l] -> pre[r] will increase by 1
Afterwards just calculate pre then you have pre[i] the number of segments that go through point i
@winged vale
winged vale
@glossy breach found it under the name prefix sum algo and GOG has the same method although I don't understand it much. Will take a look again at night
glossy breach
Alright
proper zenith
can someone lemme know whats the running time of this algo? i want to make sure im doing it right
def Poly(A,n,v):
if n == 0:
return A[len(A)-1]
return (Poly(A,n-1,v) + (v**(n))*A[len(A)-1-n])
old rover
by running time do you mean time complexity
proper zenith
yeah
onyx umbra
apply master theorem
proper zenith
im a bit confused about the time complexity of multiplication and power operations
onyx umbra
the code you wrote above is recursive so master theorem will work here
old rover
what's master theorem
proper zenith
this part specifically
(v**(n))*A[len(A)-1-n])
is it constant?
onyx umbra
** is O(n) and multiplication best can be O(n^1.5)
use pow() if u want more optimized
but most of the time u dont need to worry about math operations as those wont effect your progarms
there are many optimizations done by compiler also
onyx umbra
this part specifically
```py
(v**(n))*A[len(A)-1-n])
```
is it constant?
if u assume it constant it wont cause any issues
proper zenith
hmm
ok, i think i will just count them in, i was asked to specifically analyze the time complexity
old rover
so is every try block coupled with an except block
I'm just curious
I never used exception handling in my code
atomic kraken
a try without an except should be a SyntaxError I think
agile sundial
some sort of error
grizzled schooner
>>> try:
... a = 1
... print('hi')
File "<stdin>", line 3
print('hi')
^
SyntaxError: invalid syntax
I found this but it's a lot to read
maybe some time later
pivot = array[randint(0, len(array) - 1)]
what is the point of this line
agile sundial
do you know what it does?
agile sundial
to partition around
agile sundial
it picks a random pivot, which gives a better performance on average than picking the end to pivot
old rover
why is that a better performance
old rover
yeah I heard that before
Udacity said the same thing
so pivot is just a random value in the list
agile sundial
using a random element also makes sure no particular input gives worst case performance
old rover
oh
yeah that makes sense
the worst case for quick sort is O(N^2)
from random import randint
def quicksort(array):
if len(array) < 2:
return array
low, same, high = [], [], []
pivot = array[randint(0, len(array) - 1)]
#this is just a random value in the list
for item in array:
if item<pivot:
low.append(item)
elif item == pivot:
same.append(item)
elif item > pivot:
high.append(item)
return quicksort(low) + same + quicksort(high)
so uh
why am I confused by this recursion here
it looks like if len(array) < 2: is the base case
and it's not calling quicksort on same bc it's the same numbers as the pivot
also you can add lists in python???
oh boy you can add lists in python
agile sundial
why am I confused by this recursion here
what are you confused about?
old rover
the recursion aspect
agile sundial
what part
agile sundial
what's the point of a hash class?
vital rune
I have to implement a hash table from scratch
agile sundial
why not just have a hash function?
agile sundial
did you mean you were creating a hash table class?
vital rune
I believe I've been given 2 hash functions
I need to implement the other methods
But maybe I'm understanding it wrong
vital rune
did you mean you were creating a hash table class?
yes that's what I'm doing
old rover
they didn't call quicksort on same bc it's all of the same numbers
maybe it would be good if I try tracing the input
agile sundial
they didn't call quicksort on same bc it's all of the same numbers
of course, that would just be a waste
agile sundial
yes that's what I'm doing
right, so what do you need help with?
lean dome
You know the order of elements in same won't change, because they're all equal, so there's no reason to sort them
vital rune
right, so what do you need help with?
I'm just starting but I'm having trouble understanding where to start on this
vital rune
Honestly I'm completely lost so any advice would help haha
I was provided the code for these already
agile sundial
are you familiar with the idea of hashing?
old rover
!pastebin
halcyon plankBOT
vital rune
Is that right?
agile sundial
essentially, yeah
old rover
how am I supposed to know where pivot is
pivot is just in the array
but like if pivot was the lowest number
agile sundial
pivot is what you define as pivot
old rover
if I had a list of [5,7,1,9]
and I selected 1 as the pivot
the low list would be empty
agile sundial
that's correct
old rover
the same list would also be empty
agile sundial
no, the same list would have 1 in it
old rover
oh
that's where the pivot is
ok and the high list would be [5,7,9]
but then it calls quick sort on an empty list
nothing on same
and quick sort on [5,7,9]
lean dome
Right.
old rover
so it ends up as [1,5,7,9]
agile sundial
it would do more recursive calls though
lean dome
it picks another pivot to sort [5, 7, 9]
Those are already sorted, but it doesn't know that.
agile sundial
is that a question?
old rover
no I think I answered it
vital rune
so how do I get an index from using double hashing with thw 2 hash functions
lean dome
index = hash1(key) % array_size gives you an initial index into your array to look at. If that index has never been used, you're done - that's the index for the new item. If that index has been used, you do index += hash2(key). If that index has never been used, you're done. If it has been used, you add hash2(key) again, and keep trying.
@vital rune ^
vital rune
Does this make sense?
t = (self._hash_1(key) + i * self._hash_2(key)) % self.capacity
while incrementing i
lean dome
it's not wrong, but it's inefficient. You're recomputing hash_1(key) and hash_2(key) over and over on each loop iteration, even though they'll give the same result every time.
since the hash algorithm is usually the slowest part of a hash table, that should be avoided.
vital rune
ok that makes sense
thanks!
Can someone look at this? I'm not sure if I'm on the right track
vital rune
I'm just starting but I'm having trouble understanding where to start on this
This is what I'm doing again
royal nymph
How do i implement Dijkstra’s Shortest Path Algorithm in python
agile sundial
the same way you would in any other language
understand the algorithm first, the implementing is easy then
fiery cosmos
For every number to look at count the number of segments that contain it 
blazing edge
please ping me
agile sundial
is there error?
vital rune
I'm getting an attribute error in my _insert and setitem methods in a hash table class could anyone help with that?
I'm very close
spring jasper
Code?
vital rune
I'd appreciate any help, I have an hour to finish this by lol
@spring jasper lmk if it makes any sense
balmy siren
Hey Everyone,
I've a nested list and I want to find out all the elements that are adjacent to a particular element..
for example :
[
[0, 0, 0],
[0, 2, 0],
[0, 0, 0]
]
Here, I want to find out all the pair of elements that are adjacent.. like adjacent elements of list[0][0] are list[0][1] and list[1][0]
Any ideas how to do this, one idea that I've right now is to create a graph, and add all the elements to it, then find the adjacent elements of each element...
balmy siren
Thanks for replying,
Actually here the problem is, I have to first check out if the next index exists or not.. for example, if we have a nested list where the first container contains only 2 element and next container contains 3 element...
That requires a lot of conditional statements tbh
half lotus
It's four checks
fiery cosmos
[
[0],
[0, 2, 0],
[0, 0]
]``` they might mean jagged like this If I is against either edge and if j is against either edge
Maybe you can come up with something that uses min/max functions in the calculated indices and just store pairs in a set, which will make sure duplicates resulting from clamping are discarded
Not the most efficient solution but it's maybe less code
fiery cosmos
or could always put the list access in a try and if it errors out you know the index is invalid 
half lotus
Yes that's a much better idea
glossy tinsel
a question is there a way to get the equation of a given graph? I dont know the degree and I generated the graph with matplotlib and the y values are randomly generated.
vocal gorge
an arbitrary graph does not necessarily has any simple equation. I mean, plt.plot literally just joins the (x,y) points with line segments in the order provided.
sounds like you want polynomial interpolation, but you'll have to decide what degree polynomial you want.
glossy tinsel
so there no way to get a of a given graph? It doesnt need to be precisely.
vocal gorge
getting an equation that approximates some set of points is pretty much what interpolation/approximation is.
glossy tinsel
but I need the degree for that right?
btw is that the right channel for this question?
vocal gorge
well, yes, because a set of N points can always be perfectly approximated by a polynomial of degree N-1.
for example, you can draw a line through any 2 points, a parabola through any three...
glossy tinsel
ahh alright. So if I have 10 points, I could use 9 as the degree, right?
vocal gorge
Well, sure. And if you have 10000 points, you can make a 9999-degree polynomial perfectly passing through them. It just isn't very useful, because the coefficients of that polynomial take exactly as much (maybe more) space as the original data.
wheat wave
Hello there, good morning 
I wanted to ask if there's a way to be able to use an attribute's decorator within a class for the other attributes
I've been trying to do something like this, in order to take advantage of decorators, but It seems that self can't be used that way
hence why I'd like to know if there's some good approach to deal with this issue, other than using bot outside of the class.
vocal gorge
Functions of a class are evaluated when the class is defined, and naturally there's no self then.
vocal gorge
Hello there, good morning <:wave_leafeon:817951364772397086>
I wanted to ask i...
One approach is to, in __init__, assign these functions to the instance, like:
self.get = self.bot.chrono()(self.get)
(also, this'd fit more in a help channel.)
wheat wave
Oh interesting, and ah my bad, wasn't sure which channel it'd fit, so assumed it was data structure related ^^;
but thanks
wet urchin
Hello there. Good morning.
I need some help with this problem.
def bitStr(n, s):
if n == 1:
return s
return [digit + bits
for digit in bitStr(1, s)
for bits in bitStr(n - 1, s)]
print(bitStr(3, '01'))
Can someone can explain me How it works?
lean dome
This is sort of confusing. It plays it very fast and loose with types - sometimes the function returns a string, other times it returns a list of strings. It gets away with this because both strings and lists of strings are iterable, and in both cases iterating over it returns a string.
I'd start by turning that list comprehension back into a regular nested for loop: ```py
def bitStr(n, s):
if n == 1:
return s
ret = []
for digit in bitStr(1, s):
for bits in bitStr(n - 1, s):
ret.append(digit + bits)
return ret
print(bitStr(3, '01'))
!e Then I'd add some debugging statements that print out each call that's made, and what it's returning: ```py
def bitStr(n, s):
if n == 1:
print(f"{n=} {s=} returning {s}")
return s
ret = []
for digit in bitStr(1, s):
for bits in bitStr(n - 1, s):
ret.append(digit + bits)
print(f"{n=} {s=} returning {ret}")
return ret
print(bitStr(3, '01'))
@lean dome :white_check_mark: Your eval job has completed with return code 0.
001 | n=1 s='01' returning 01
002 | n=1 s='01' returning 01
003 | n=1 s='01' returning 01
004 | n=1 s='01' returning 01
005 | n=2 s='01' returning ['00', '01', '10', '11']
006 | n=1 s='01' returning 01
007 | n=1 s='01' returning 01
008 | n=1 s='01' returning 01
009 | n=2 s='01' returning ['00', '01', '10', '11']
010 | n=3 s='01' returning ['000', '001', '010', '011', '100', '101', '110', '111']
011 | ['000', '001', '010', '011', '100', '101', '110', '111']
so: if we call bitStr(1, "01") it returns "01". That happens a few times. If we call bitStr(2, "01") it sets digit to first 0, then 1 - for each of those, it makes a call to bitStr(1, s) which again returns "01", then it iterates over each character of that, prepending digit to it. That results in ["00", "01", "10", "11"]
if we call bitStr(3, "01"), then it sets digit to first "0", then "1", and for each of them, it calls bitStr(2, "01") (which we already know returns ["00", "01", "10", "11"]. First for "0", it loops over that return from bitStr(2, "01"), prepending "0" to each of them, then it repeats that for "1", resulting in ["000", "001", "010", "011", "100", "101", "110", "111"]
!e note that this can be written more efficiently, too - because the recursive call to bitStr(n - 1, s) doesn't depend on digit, we don't need to do it for every iteration of the for digit in bitStr(1, s) loop. We can make fewer total calls if we do:
def bitStr(n, s):
if n == 1:
print(f"{n=} {s=} returning {s}")
return s
ret = []
for bits in bitStr(n - 1, s):
for digit in bitStr(1, s):
ret.append(digit + bits)
print(f"{n=} {s=} returning {ret}")
return ret
print(bitStr(3, '01'))
@lean dome :white_check_mark: Your eval job has completed with return code 0.
001 | n=1 s='01' returning 01
002 | n=1 s='01' returning 01
003 | n=1 s='01' returning 01
004 | n=2 s='01' returning ['00', '10', '01', '11']
005 | n=1 s='01' returning 01
006 | n=1 s='01' returning 01
007 | n=1 s='01' returning 01
008 | n=1 s='01' returning 01
009 | n=3 s='01' returning ['000', '100', '010', '110', '001', '101', '011', '111']
010 | ['000', '100', '010', '110', '001', '101', '011', '111']
Note that that prints out only 10 lines, instead of the 11 from the version above - we saved an unnecessary call to bitStr(2, s).
!e We can also make this easier to read by replacing the calls that hardcode n=1 to with s, since we know that bitStr always returns s if n == 1:
def bitStr(n, s):
if n == 1:
print(f"{n=} {s=} returning {s}")
return s
ret = []
for bits in bitStr(n - 1, s):
for digit in s:
ret.append(digit + bits)
print(f"{n=} {s=} returning {ret}")
return ret
print(bitStr(3, '01'))
@lean dome :white_check_mark: Your eval job has completed with return code 0.
001 | n=1 s='01' returning 01
002 | n=2 s='01' returning ['00', '10', '01', '11']
003 | n=3 s='01' returning ['000', '100', '010', '110', '001', '101', '011', '111']
004 | ['000', '100', '010', '110', '001', '101', '011', '111']
that's more efficient, and I think it's a bit more readable. Does it make sense to you, @wet urchin ?
!e Another thing that might help is seeing an iterative, rather than recursive, version of this algorithm. It looks like this:
def bitStr(n, digits):
results = [""]
for i in range(n):
print(f"generating {i+1} digit strings")
new_results = []
for digit in digits:
for result in results:
new_results.append(digit + result)
print(f"generated {new_results}")
results = new_results
return results
print(bitStr(3, '01'))
@lean dome :white_check_mark: Your eval job has completed with return code 0.
001 | generating 1 digit strings
002 | generated ['0', '1']
003 | generating 2 digit strings
004 | generated ['00', '01', '10', '11']
005 | generating 3 digit strings
006 | generated ['000', '001', '010', '011', '100', '101', '110', '111']
007 | ['000', '001', '010', '011', '100', '101', '110', '111']
Thanks for the reply. I finally understood it, thank you really.
wet urchin
that's more efficient, and I think it's a bit more readable. Does it make sense ...
Yes. I really appreciate it. Thanks a lot :,,)
glossy tinsel
A question. How I can round an float like this 6.232412441e-7 to 6.2e-7?
old rover
yes trees are definitely harder than linked lists
I have all this new vocabulary thrown at me
so uh
how do you find the height of B
agile sundial
you would count
old rover
oh
agile sundial
etc
old rover
bc it has two arrow things going down
like it has two children
and then one child has another child
so that makes the depth 2
agile sundial
correct
old rover
how do you even create a tree
agile sundial
very similarly to a linked list
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
root = Node(3)
root.left = Node(4)
root.right = Node(10)
3
/ \
4 10
oh that's not that bad
rocky ibex
how can i create like a lot of variables with a cicle for?
ehm can someone answer me please?
agile sundial
ehm can someone answer me please?
why do you need a lot of variables?
rocky ibex
it's hard to answer
lean dome
it sounds like you should probably be making a list that contains 4 values, rather than 4 separate variables, if they're so closely related that a single loop can make them.
agile sundial
there are many archetypes of trees, you could say
old rover
are binary trees the most common types of trees
agile sundial
no idea ¯_(ツ)_/¯
lean dome
a ternary (or trinary) tree would have up to 3 children per node. A quaternary tree would have up to 4. Etc.
Binary trees are most common, from what I've seen, but there's nothing that stops you from creating a different type of tree.
old rover
what's a "leaf"
lean dome
a tree node without any children.
lean dome
if it's not explaining them, then it may be assuming some prior knowledge of trees.
lean dome
throwing terms at you without explaining their meaning sounds like it's not the greatest course, then. 🤷
lean dome
it means searching every node at a particular depth before moving down to the next depth.
lean dome
breadth is searching one level at a time. Depth is searching all children of some node before moving on to its sibling nodes.
old rover
did she really think she was going to explain this all in 2 minutes and 35 seconds
lean dome
So given ```
A
/
/
B C
/ \ /
D E F G
Depth first order is `ABDECFG`. Breadth first order is `ABCDEFG`.so breadth first search is more like level first search
old rover
what is post order again
I'm sorry I keep bothering you guys
just trying to learn this
lean dome
in order vs pre order vs post order is about when you process the data attached to each node. An in-order traversal of a tree processes the data of a node after its left child, and before its right child. A pre-order traversal would process a node before either of its children. A post-order traversal would process a node after both of its children.
austere sparrow
@old rover A file system is a very common example of a tree. You can have 'leaves' (files) and 'nodes' (folders).
/ (root)
|
+--system/
| |
| +--main.exe
| +--ie.exe
|
+--users/
|
+--alice/
| |
| +--weapons/
| +--shovel.png
| +--machinegun.png
+--bob/
|
+--javascript/
| +--the-good-parts.pdf
| +--index.js
| +--test.html
+--python/
+--main.py
Suppose that you want to find the first file called main.py.
With depth-first search, you would first try to take a folder and go as deep as you can, backtracking when you need.
With breadth-first serach, you would:
- First look at
/: neithersystem/notusers/are calledmain.py. - Then look at the next level: search among
/system/ie.exe,/system/main.exe,/users/alice/,/users/bob/. None of the files match. - Then look at the next level: search among
/users/alice/weapons/,/users/bob/javascript/,/users/bob/python/. None of the files match. - Then look at the next level: search among
shovel.png,machinegun.png,the-good-parts.pdf,index.js,test.html,main.py. You've foundmain.py.
austere sparrow
it depends 🙂
austere sparrow
for example, you can't search among an infinitely long tree with DFS
old rover
bc you'd always be searching?
lean dome
An in-order traversal of the tree in your screenshot would be DBEFAC. A pre-order traversal would be ABDEFC. A post-order traversal would be DFEBCA.
lean dome
breadth first search and depth first search are approximately equally fast, assuming the tree is finite and you have no reason to assume that one search would be better than the other for the particular data in a given tree. When you get to algorithms for walking a tree, the algorithm for a depth-first search and a breadth-first search are almost exactly the same, and the only difference is whether you put the nodes that you've discovered but not yet visited into a queue or a stack.
agile sundial
there are reasons why one may be better if you can use both though. if you know the answer is near the bottom of a tree (maybe it's a decision tree), then dfs may be better
dapper sapphire
Wondering if someone can share resources they used to learn doubly linked lists? I have looked at geeksforgeeks and I wanted to see couple more different implementations Are push, insertAfter, and append the most common methods for a doubly linked list?
wet urchin
that's more efficient, and I think it's a bit more readable. Does it make sense ...
Hey bro, May you send me some good resources about Backtracking?. I hope You could answer me.
lean dome
I don't have any specific resources I can recommend on that. Backtracking is just going back to a previous state and trying a different path forwards - depending on the particular algorithm or data structure, that can mean very different things.
lean dome
Wondering if someone can share resources they used to learn doubly linked lists?...
There's basically 3 cases when adding an element to a doubly linked list: the element will be the new tail of the list, the element will be the new head of the list, or the element will be neither the new head nor the new tail of the list. Splitting those 3 operations out as separate functions is reasonable.
you can do it with only 2 functions, if you prefer, though - it can be handled with just append and insert_before, or with just prepend and insert_after
in which case you'd handle both tacking a new element on as the first element of an empty list or the last element of a non-empty list with append and all other inserts with insert_before, for instance.
dapper sapphire
Is @lean dome following prepend to add to the beginning:
def add(self, data):
newNode = Node(data)
if(self.head != None):
self.head.previous = newNode
newNode.next = self.head
self.head = newNode
serene oracle
Hey bro, May you send me some good resources about Backtracking?. I hope You cou...
CLRS ch. 15 (dynamic programming)
lean dome
Is <@!451976922361102357> following `prepend` to add to the beginning:
```pytho...
that's prepending a new element as the first element of the list, yes.
spring jasper
What dont you like about it
old rover
the code is long
spring jasper
You have to change/set double the references so yea, naturally its longer
old rover
yeah true
timid drum
I'm a noob but can anybody help me understand how to understand how to implement a time function into my code? 😅
fierce lark
e
old rover
@fierce lark ?
west jasper
I have thousands of points on a two-dimensional plane. Every tick these points move in a random direction, new points appear, some disappear. What will be the best aproach to find a nearest point for every point? A circular search doesn't really look good.
misty plume
hey, I'm having some trouble with graphs algorithms and I was wondering if anyone could help me
keen hearth
Hey @misty plume, what do you need help with?
misty plume
basically it's a graphs problem from a competitive programming sheet, I've just started with python and I'm finding it quite complicated to find a solution by myself
misty plume
I suck at both don't worry
old rover
trees are just spicy linked lists
I actually didn't do much yesterday I just took a day off
misty plume
later on I'll be trying some stuff if you want someone to cry with while you do it hahaha
old rover
sounds good
full zenith
Hello! I'm doing investing strategy on Python based on Awesome Oscillator. My problem is that I kinda stuck in entry and exit points. Can someone review my code and give any recommendations?
winged vale
Can someone explain from slide 7 https://people.csail.mit.edu/indyk/6.838-old/handouts/lec17.pdf. (How did we get the first proof and the third proof. How do we have 8 points in total). This is the question https://www.geeksforgeeks.org/closest-pair-of-points-using-divide-and-conquer-algorithm/
old rover
both deleting and searching in a tree is O(N)
agile sundial
are you asking or telling
old rover
telling
agile sundial
that sounds about right
agile sundial
sure yeah
old rover
I think I'll be learning hash maps and graphs soon
agile sundial
trees are just a subset of graphs
flat sandal
currently struggling with writing a certain algorithm, if anyone could help in #help-mushroom that would be greatly appreciated
eager hamlet
so i'm doing this problem https://oj.uz/problem/view/JOI21_ho_t4
and came up with a simple dijkstra's that treats an edge's cost as 0 if it's unique relative to that node and its normal cost otherwise
however, it WAs on most of the test cases because changing an edge can result in the other node on that edge having a new "unique" edge as well
so does anyone know how to fix this? (ping 2 reply thx)
dapper sapphire
Ok so I'm working on remove an element from a doubly linked list:
def remove(self, targetData):
current = self.head
previous = None
found = False
while current.next:
if current.data == targetData:
found = True
break
previous = current
current = current.next
if found == True or current.data == targetData:
if previous is None:
self.head = current.next
self.head.prev = None
elif previous is not None:
previous.next = current.next
if current.next is not None:
current = current.next
current.prev = previous
So in the last two lines I have to do current = current.next so in the next line I can point its current.prev to previous node.
Is there a way to put them in one line? something like current.next.prev = previous which of course doesnt work.
vocal gorge
current.next.prev = previous does work, but don't you also need to update the current node?
ah, nevermind, that's not in the loop.
You can indeed do that, not sure why you think it doesn't work.
lean glade
Ok so I'm working on remove an element from a doubly linked list:
```python
...
You dont need a current and previous variable when removing from a doubly linked list
dapper sapphire
Oh actually never mind it work, I had some other mistake in the code which made me think it doesn't work,
but is this a good practice? or would it make the code harder to read?
lean glade
Ok so I'm working on remove an element from a doubly linked list:
```python
...
current.next.prev = previous does work
dapper sapphire
Yeah, it does.
I made a mistake which made me think it doesnt
And I guess it's common to write it like so because I'm also seeing current.prev.next = something
lean glade
And just do current.next.prev = current.prev
Same with current.prev.next = current.next
dapper sapphire
And just do `current.next.prev = current.prev`
So I based the following of what you mentioned:
def remove(self, targetData):
current = self.head
found = False
while current:
if current.data == targetData:
found = True
break
current = current.next
if found == True:
if current.prev is None:
current.next.prev = current.prev
self.head = current.next
elif current.next is not None:
current.next.prev = current.prev
current.prev.next = current.next
elif current.next is None:
current.prev.next = current.next
And it works, I just dont think there's a way around to conditional if else statements. We have to create 3 separate conditions to check if it's the beginning, middle, or end
lean glade
I would put the check for current.prev is None and the check for current.next is None first, and put the other part as an else
dapper sapphire
oh ok I see what you mean.
@lean glade that was helpful thanks for mentioning we dont need the previous node because we always have access to it in doubly linked list.
lean glade
You're welcome!
dapper sapphire
So this is how a doubly linked list looks like:
None <- 3 <-> 2 <-> 1 -> None
head(3) would have previous that points to none, and tail(1) would have next that points to None
dapper sapphire
Actually should I do be doing:
elif current.next is None:
current.prev.next = current.next
del current
If we are removing the last node, then should we delete the last node. Otherwise last node's previous would point to second last node, so we end up with two representations of the list?
None <- 3 <-> 2 <- 1 -> None
None <- 3 <-> 2 -> None
What del current does is pretty much unassign that name; nothing else. It's not really different from, say, assigning it to something else, like current = "". Either way, when the function ends, all local variables like current will be dropped. del does not do anything with the object the name points to.
dapper sapphire
oh ok I see. So if someone has access to 1 node, they could traverse backwards to the entire list?
vocal gorge
Well, yes, they could.
eager hamlet
so i'm doing this problem https://oj.uz/problem/view/JOI21_ho_t4
and came up with a simple dijkstra's that treats an edge's cost as 0 if it's unique relative to that node and its normal cost otherwise
however, it WAs on most of the test cases because changing an edge can result in the other node on that edge having a new "unique" edge as well
so does anyone know how to fix this? (ping 2 reply thx)
old rover
!pastebin
halcyon plankBOT
old rover
so here's how Udacity does their binary search tree
class Node():
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BST():
def __init__(self):
self.root = Node(None)
def insert(self, new_data):
if self.root is None:
self.root = Node(new_data)
else:
if self.root.val < new_data:
self.insert(self.root.right, new_data)
else:
self.insert(self.root.left, new_data)
def inorder(self):
if self.root:
self.inorder(self.root.left)
print(self.root.val)
self.inorder(self.root.right)
this is how some guy's github repo does it
should I be using a certain one?
this one has a Node class
vocal gorge
Have you considered implementing your own?
I don't think there's much difference between using a Node class and just having a .val attribute here
old rover
idk what find_val is in the udacity code
and I don't know how to implement my own
Udacity kind of glosses over it
vocal gorge
idk what find_val is in the udacity code
The value to search for.
I mean, preorder_search just returns True or False depending on if the value is in the tree.
eager hamlet
so i'm doing this problem https://oj.uz/problem/view/JOI21_ho_t4
and came up with a simple dijkstra's that treats an edge's cost as 0 if it's unique relative to that node and its normal cost otherwise
however, it WAs on most of the test cases because changing an edge can result in the other node on that edge having a new "unique" edge as well
so does anyone know how to fix this? (ping 2 reply thx)
lone escarp
@functools.lru_cache()
def findSum(numbers, queries):
totals = []
for query in queries:
totals.append(
sum(numbers[query[0] - 1:query[1]]) + (query[2] if 0 in numbers else 0)
)
return totals
``` how can i make this faster?(don't give the answer, solving hackerrank, just a hint or something)
vocal gorge
sum(numbers[query[0] - 1:query[1]])
It looks like you are calculating many sums over the list. By precalculating a list of cumulative sums, you can make each such operation O(1).
lone escarp
Right, i will do that
@functools.lru_cache()
def sum_li(li, a, b):
return sum(li[a - 1:b])
@functools.lru_cache()
def findSum(numbers, queries):
totals = []
for query in queries:
totals.append(
sum_li(numbers, query[0], query[1]) + (query[2] if 0 in numbers else 0)
)
return totals
``` even this is slow, i don't see any other way of precalulatingquery[2] if 0 in numbers else 0
and this will be calculated each time, which is inefficient - as far as I can tell, this can be calculated just once outside the loop instead.
vocal gorge
```py
@functools.lru_cache()
def sum_li(li, a, b):
return sum(li[a - 1:b])
...
uhh, no, not like that
it's a very common trick for calculating subarray sums
consider a list of cumulative sums:
cumsum[i] = numbers[0] + numbers[1] + ... + numbers[i]
That entire list can be calculated in O(n). Now suppose you want to find sum(numbers[a:b]) for some a,b. This is just subtracting two elements of cumsum - which is O(1).
lone escarp
uh ok
lavish flint
Hey guys, I have been getting trouble coming up with a pandas one-line solution for the problem I am facing.
I am playing with stock data and have minute-by-minute data for a ticker in a single day. I want to take my price column df['price'] and create a new column called df['max_price_after_this_minute']... Which is essentially the series.max() of the price for all rows AFTER the given minute. The data is already sorted by minute, ascending.
I have succeeded in accomplishing this with a loop, but I need something vectorized to improve the speed of my greater algorithm
vocal gorge
Hey guys, I have been getting trouble coming up with a pandas one-line solution ...
I'd start by just applying @numba.njit to make your function run on C speeds, which may be all that you need.
I can see a way to vectorize it with just numpy, but it's pretty ugly and uses a lot of memory (duplicate the column N times, creating an NxN rectangular array, then set the lower-right triangle to negative infinity and take the max along the vertical axis)
lone escarp
That entire list can be calculated in O(n). Now suppose you want to find `sum(nu...
i didn't understand the second sentence, how is it just subtraction of two elements?
vocal gorge
Perhaps using the sliding window functions from bottleneck (an library adding some functions like this to numpy) would be another way.
vocal gorge
i didn't understand the second sentence, how is it just subtraction of two eleme...
sum(numbers[a:b]) = numbers[a] + ... + numbers[b-1]
Look closely at the definition of cumsum, and you'll see that's equal to cumsum[b-1] - cumsum[a-1].
lavish flint
I'd start by just applying `@numba.njit` to make your function run on C speeds, ...
I will try this and try the numpy method, I appreciate your input. I'm definitely more analyst than programmer so I'm a tad slow, but I will report back if I have more questions
lone escarp
@vocal gorge do you mean something like this?
@functools.lru_cache()
def sum_li(cumsum, a, b):
return cumsum[b - 1] - cumsum[a - 1]
@functools.lru_cache()
def findSum(numbers, queries):
li = tuple(accumulate(numbers))
totals = []
x = int(0 in numbers)
for query in queries:
totals.append(
sum_li(li, query[0], query[1]) + ([0, query[2]][x])
)
return totals
lru_caching the first function is kinda overkill, it's O(1) anyway. for that matter, it doesn't need to be a function at all
but yeah, itertools.accumulate is a nice way to calculate it
lone escarp
what am i doing wrong here
vocal gorge
that's not the same as you were doing before, though
lone escarp
yeah
vocal gorge
you were doing + (query[2] if 0 in numbers else 0)
so why not make x = query[2] if 0 in numbers else 0, and add that x to each total?
vocal gorge
ah, right. Okay then
vocal gorge
what am i doing wrong here
you're taking the sums over slightly different subarrays than before
you used to do sum(numbers[query[0] - 1:query[1]])
note the -1
vocal gorge
I will try this and try the numpy method, I appreciate your input. I'm definitel...
There's actually a simple solution I totally forgot exists. itertools.accumulate with max as the function (and you'll have to call it on the flipped column, then unflip it, I think). Probably slower than the numba way, but likely faster than a naive loop, because accumulate is a C function.
lavish flint
There's actually a simple solution I totally forgot exists. `itertools.accumulat...
Thanks I'll see how easy that is - I actually just got numba to work too, that is going to be a good one to keep in my back pocket for a rainy day
while I don't care to test, I wonder if it will be faster or slower than itertools.accumulate
vocal gorge
while I don't care to test, I wonder if it will be faster or slower than itertoo...
If I'm not mistaken and you have to use it like this to apply to this task:
import numba
@numba.njit
def f(arr):
result = np.zeros(arr.shape,dtype=arr.dtype)
n = len(arr)
cur = arr[-1]
result[-1] = cur
for i in range(n-2,-1,-1):
cur = max(cur,arr[i])
result[i] = cur
return result
import itertools
def f2(arr):
return np.flip(np.array(list(itertools.accumulate(np.flip(arr),max))))
arr = np.random.random(1000)
assert (f2(arr)==f(arr)).all()
%timeit f(arr)
%timeit f2(arr)
the results are:
2.54 µs ± 108 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
340 µs ± 4.99 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
so 130 times slower
but, well, np.flip(np.array(list(itertools.accumulate(np.flip(arr),max)))) is not exactly a nice way
fiery plank
im trying to get to know algos and some people said insertion sort is pretty good, anyone know any tutorials or projects to learn them(feel free to @ me)
vocal gorge
insertion sort is an O(n^2) sorting algorithm
it is usually taught among other basic algorithms like bubble sort
lavish flint
If I'm not mistaken and you have to use it like this to apply to this task:
```p...
I implemented your code and it moves with literal god-like speed compared to the loop I was running... it was (390 rows x 90 days of data x 120 stock tickers) for my loop... You can use your imagination for how many hours faster this is
@vocal gorge I actually have one slight issue with your loop, looks like when the new max value is found it is off by a single row --- where in your loop do I add a +1 or a -1 to fix this?
sorry for being an absolute scrub, I know with a fresh night of sleep I could figure that out on my own
vocal gorge
huh, it seems to be fine for me
import numba
@numba.njit
def f(arr):
result = np.zeros(arr.shape,dtype=arr.dtype)
n = len(arr)
cur = arr[-1]
result[-1] = cur
for i in range(n-2,-1,-1):
cur = max(cur,arr[i])
result[i] = cur
return result
arr = np.random.random(10)
print(arr)
print(f(arr))
[0.43355963 0.3684732 0.10920699 0.36049394 0.15896217 0.14580983
0.92202411 0.50997125 0.58052465 0.63217428]
[0.92202411 0.92202411 0.92202411 0.92202411 0.92202411 0.92202411
0.92202411 0.63217428 0.63217428 0.63217428]
maybe the issue is how I am applying the list back to my df
lavish flint
@vocal gorge I ended up just saying result[i-1]=cur and it worked for all but the last 2 rows of each data frame, which is fine because technically for my study the last few minute of a trading day are not in scope by definition
thanks again!!!
eager hamlet
so i'm doing this problem https://oj.uz/problem/view/JOI21_ho_t4
and came up with a simple dijkstra's that treats an edge's cost as 0 if it's unique relative to that node and its normal cost otherwise
however, it WAs on most of the test cases because changing an edge can result in the other node on that edge having a new "unique" edge as well
so does anyone know how to fix this? (ping 2 reply thx)
rough saffron
!levelx
halcyon plankBOT
You are not allowed to use that command here. Please use the #bot-commands channel instead.
rough saffron
!levels
halcyon plankBOT
You are not allowed to use that command here. Please use the #bot-commands channel instead.
lost rampart
There are exactly N bus stops from Tracy’s coaching center to her home. The number of buses that can be boarded from each bus stop is also given. A bus will only stop at a bus stop whose number is a multiple of the bus stop number from which the bus originates. Find the number of buses originating from each bus stop between her coaching center and her home.
flat sandal
trying to implement an algorithm based on the sieve of eratosthenes, if anyone could help in #help-mango, that would be appreciated
warm solstice
def is_even(k):
l = 2
for l in range(1, k+1):
l += 2
if(l == k):
return True
break
elif(l > k):
return False
break
return False
print(is_even(5))
```This is my attempt at solving the question below, now I have seen solutions using bit-wise operations, but I think this method should work, only that it doesn't work. `Write a short Python function, is even(k), that takes an integer value and
returns True if k is even, and False otherwise. However, your function
cannot use the multiplication, modulo, or division operators.`
main flower
Well
- You only check for
k>= 2 and the question doesn't say thatkcannot be e.g. -6 - You could have just used
k & 1
coral loom
Hey 🙂 I don't suppose you guys can help me out on something? I'm on #help-peanut
warm solstice
1. You only check for `k` >= 2 and the question doesn't say that `k` cannot be e...
Thanks you very much, I'll just get the magnitude of k then
eager hamlet
so i'm doing this problem https://oj.uz/problem/view/JOI21_ho_t4
and came up with a simple dijkstra's that treats an edge's cost as 0 if it's unique relative to that node and its normal cost otherwise
however, it WAs on most of the test cases because changing an edge can result in the other node on that edge having a new "unique" edge as well
so does anyone know how to fix this? (ping 2 reply thx)
old rover
def preorder_search(self, start, find_val):
if start:
if start.value == find_val:
return True
else:
return self.preorder_search(start.left, find_val) or self.preorder_search(start.right, find_val)
return False
what does this function do?
preorder_search??
agile sundial
are you just looking at functions?
agile sundial
there's no editorial or explanation or something?
old rover
no
agile sundial
that sounds very inefficient
old rover
yeah I question why google sponsored this course every day
MIT OCW also does it in python
old rover
class BinaryTree(object):
def __init__(self, root):
self.root = Node(root)
def search(self, find_val):
return self.preorder_search(tree.root, find_val)
def print_tree(self):
return self.preorder_print(tree.root, "")[:-1]
def preorder_search(self, start, find_val):
if start:
if start.value == find_val:
return True
else:
return self.preorder_search(start.left, find_val) or self.preorder_search(start.right, find_val)
return False
def preorder_print(self, start, traversal):
if start:
traversal += (str(start.value) + "-")
traversal = self.preorder_print(start.left, traversal)
traversal = self.preorder_print(start.right, traversal)
return traversal
this is everything
halcyon plankBOT
old rover
this is the quiz
this is MIT ocw's notes on binary trees
I know that search returns false if a value is not in a tree
but I don't understand the function they're using in search
agile sundial
they taught this before quizzing on it right
old rover
yeah like 3 minute videos
agile sundial
basically preorder is 3 steps
procedure PRE-ORDER-TRAVERSAL (root):
visit root
PRE-ORDER-TRAVERSAL(root.left)
PRE-ORDER-TRAVERSAL(root.right)
it's used to create a copy of the tree
agile sundial
are you asking or telling
old rover
telling
agile sundial
it could be used to do that, yeah
it's used to visit all the nodes
say...if you wanted to look for a specific one...
old rover
what does granularity even mean
lean dome
it could be used to do that, yeah
So could a post-order traversal, though.
agile sundial
well, any way that gets to all the nodes can do that
lean dome
Exactly.
old rover
I googled granularity and it said the quality of being granular
agile sundial
lul
lean dome
Ability to reflect capture something small precisely
lean dome
A volume knob that lets you pick 20 different settings is more granular than one that lets you pick 10.
old rover
bc more options?
lean dome
More control for the user.
old rover
oh ok
def preorder_search(self, start, find_val):
if start:
if start.value == find_val:
return True
else:
return self.preorder_search(start.left, find_val) or self.preorder_search(start.right, find_val)
return False
so this is preorder tree traversal?
agile sundial
yeah
lean dome
Yes. It checks whether the start node holds the value it's looking for, then it checks whether any node in the left subtree of start holds it, then it checks whether any node in the right subtree holds it.
That order - root, left subtree, right subtree - is pre order traversal
old rover
why is it convention to go to the left subtree from the root?
lean dome
Probably because we read most languages left to right.
old rover
why is it even called pre order?
agile sundial
¯_(ツ)_/¯
there's probably some semantic thing
there's also post and in-order
which just change when you look at the current node
old rover
def inorder(self):
if self.root:
self.inorder(self.root.left)
print(self.root.val)
self.inorder(self.root.right)
I was talking about this one
agile sundial
that's in-order then
old rover
yeah so I said it looks like I have in order
agile sundial
i know why in-order is called in-order though
old rover
how come
agile sundial
it gives all the nodes from left to right
lean dome
And pre order is a node before its children, and post order is a node after its children
agile sundial
oh that makes more sense
agile sundial
it's pretty much already python. except the visit function is just some action that you do to the value of the node you're at
lean dome
def preorder(node):
if node is None:
return
visit(node)
preorder(node.left)
preorder(node.right
does if node is none mean if there is no root return nothing?
lean dome
it's pretty much already python. except the `visit` function is just some action...
It could also be a global function defined in the same module as preorder
agile sundial
yes
agile sundial
It could also be a global function defined in the same module as preorder
;-;
keen hearth
Potentially a more pythonic way to do this is to use a generator function: py def preorder_nodes(node: Optional[Node]) -> Iterable[Node]: if node: yield node yield from preorder(node.left) yield from preorder(node.right) Then you can map some function to each node: ```py
map(somefun, preorder_nodes(root))
Generators are great for untangling the different parts of your code.
The same, but using a stack: ```py
def preorder_nodes(root: Optional[Node]) -> Iterable[Node]:
stack = [root]
while stack:
node = stack.pop()
if node:
yield node
stack.append(node.right)
stack.append(node.left)
your first used a stack too :P
old rover
def printPostorder(root):
if root:
# First recur on left child
printPostorder(root.left)
# the recur on right child
printPostorder(root.right)
# now print the data of node
print(root.val),
is that really all I have to do
agile sundial
pretty much
old rover
that is so easy
agile sundial
yeah
old rover
why'd they say trees are so hard then
agile sundial
you haven't gotten to the hard part yet :P
old rover
oh boy
keen hearth
why'd they say trees are so hard then
They're not inherently hard. They are a useful abstraction.
old rover
def insert(self, new_data):
if self.root is None:
self.root = Node(new_data)
else:
if self.root.val < new_data:
self.insert(self.root.right, new_data)
else:
self.insert(self.root.left, new_data)
so uh
why insert to the right if the value is bigger
and insert to the left if smaller
is that just convention
agile sundial
is that a binary search tree
old rover
yes
agile sundial
yeah, higher numbers go to the right
old rover
oh ok
keen hearth
Yeah, i think it's a convention.
old rover
I must have forgot
old rover
oh
ok
now I feel bad about myself that I couldn't actually figure it out
are there repr functions for trees too?
there probably are
keen hearth
You mean to print out the structure of the tree?
old rover
yes
keen hearth
Yep, you could write one. That might be a good application of the pre-order function.
old rover
I mean doesn't post order, in order, and pre-order do that too
they just don't print the entire tree
keen hearth
They visit the nodes of the tree in a particular order.
old rover
yeah
agile sundial
you could certainly use that to create some sort of fancy display
old rover
so preorder, in order, and post order are all algorithms?
agile sundial
sure
old rover
do I have to know the time complexities of them too?
old rover
the time complexity for pre order traversal is O(N)
bc you call it once if there is a root
grizzled schooner
bc you call it once if there is a root
how is this related to the time complexity?
eager hamlet
so i'm doing this problem https://oj.uz/problem/view/JOI21_ho_t4
and came up with a simple dijkstra's that treats an edge's cost as 0 if it's unique relative to that node and its normal cost otherwise
however, it WAs on most of the test cases because changing an edge can result in the other node on that edge having a new "unique" edge as well
so does anyone know how to fix this? (ping 2 reply thx)
old rover
how is this related to the time complexity?
it looks like here you call visit for every node in the tree
old rover
any course for algo ds begineer?
you can try the Udacity course I'm doing
but it's in Python 2.7
buoyant spear
but it's in Python 2.7
I m using 3.7
old rover
There is also MIT OCW
buoyant spear
you can try the Udacity course I'm doing
Can u send the link
old rover
buoyant spear
Thanks
keen hearth
so i'm doing this problem https://oj.uz/problem/view/JOI21_ho_t4
and came up wit...
Hey, I'm unable to open that link.
grizzled schooner
it looks like here you call visit for every node in the tree
Yes that’s right. Your original wording was just unclear for me
buoyant spear
https://classroom.udacity.com/courses/ud513
I should begin with the lesson 1 ?
Or is there something different course for algo ds?
@old rover
old rover
I should begin with the lesson 1 ?
yeah the first lesson is good
def printPreorder(root):
if root:
# First print the data of node
print(root.val),
# Then recur on left child
printPreorder(root.left)
# Finally recur on right child
printPreorder(root.right)
this looks like recursion to me
is the base case if root:?
spring jasper
No that looks like bad variable naming
root there should be called node
It just checks if the node exists
silent widget
Hey,
I have this def that takes a string and a DataFrame as arguments.
def accuracy_by_species(specie_name, df):
Now, I want to use apply function and pass DataFrame as argument. Is this possible?
Something like:
['a', 'b', 'c'].apply(accuracy_by_species, MyDF)
Any help would be appreciated.
old rover
so it's not recursion?
spring jasper
It is
old rover
oh
def preorder(self):
if self.root:
#print the data of the node
print(self.root.val)
preorder(self.left)
preorder(self.right)
then did I misspell something?
spring jasper
No but your function calls are incorrect
The function should take a node, not self
old rover
def preorder(node):
if node:
#print the data of the node
print(node.val)
preorder(node.left)
preorder(node.right)
it still says undefined name preorder
agile sundial
root there should be called node
It just checks if the node exists
why?
it is a root
lean dome
It's the root of a subtree, rather than the full tree
But each subtree is a tree with its own root
spring jasper
Its not self.root tho and that might be confusing
grizzled schooner
it still says undefined name preorder
are you within a class?
eager hamlet
Hey, I'm unable to open that link.
what do you see instead?
old rover
class Node():
def ____init___(self, val):
self.val = val
self.left = None
self.right = None
class BST():
def __init__(self):
self.root = Node(None)
def insert(self, new_data):
if self.root is None:
self.root = Node(new_data)
else:
if self.root.val < new_data:
self.insert(self.root.right, new_data)
else:
self.insert(self.root.left, new_data)
#higher numbers go to the right, lower numbers go to the left
def inorder(self):
if self.root:
self.inorder(self.root.left)
print(self.root.val)
self.inorder(self.root.right)
def preorder(node):
if node:
#print the data of the node
print(node.val)
preorder(node.left)
preorder(node.right)
Erm, just didn't load.
Could you copy and paste the question?
halcyon plankBOT
Hey @eager hamlet!
grizzled schooner
```python
class Node():
def ____init___(self, val):
self.val = val
sel...
it's a method of a class, so you have to pass self as a parameter
and look at all the other times that you have called functions within your class
old rover
so it is self
grizzled schooner
for example, you use recursion in your insert method
grizzled schooner
well, you should keep the node parameter as well
old rover
def preorder(self,node):
if self.root:
#print the data of the node
print(self.root.val)
preorder(node.left)
preorder(node.right)
why are you using self.root
don't you want to check for node? self.root will always be the same node every time you call the function
old rover
def preorder(self,node):
if node:
#print the data of the node
print(node.val)
preorder(node.left)
preorder(node.right)
what does if node even do
check if the node exists?
I normally see a condition I haven't seen just if something
spring jasper
Yes
spring jasper
You need self.preorder when youre calling the func again
grizzled schooner
I normally see a condition I haven't seen just if something
this basically checks if the value is truthy or falsey, in this case checking whether the node is not None
old rover
yeah I remember asking if ____ is the same as if ____ is not None
oh that didn't come out the way I intended
discord is weird with underscores
I meant to say I asked before if BLANK is the same as if BLANK is not None
grizzled schooner
yeah I remember asking if ____ is the same as if ____ is not None
not always, for example empty collections, the number 0, empty strings, etc. are all falsey
spring jasper
I usually have two functions for this kind of thing, one public and one private
def preorder(self):
if self.root:
self._preorder(self.root)
def _preorder(self, node):
if node:
print(node.value)
self._preorder(node.left)
self._preorder(node.right)
you can do private functions with python?
spring jasper
Cause you cant have instance attributes in function definitions and i dont like passing self.root into functions
Its not private private
grizzled schooner
what's the hard part about trees 👀
spring jasper
Anything other than traversals i guess
lean dome
Balancing is tricky.
old rover
this is a stupid question
ok you have been warned
but why can't you use a for loop to traverse trees
mint jewel
you can
mint jewel
if you use a stack or a queue to do so
since a tree isn't a linear
so there isn't a clear definition of where the "next" element is
old rover
it's not like linked lists
mint jewel
which is what the post in pre do
they determine which order the leaves should be accessed in
mint jewel
that seems pretty reasonable
when you think about it, a linked list is a binary tree that always has a value on the left, and the rest of the list on the right
old rover
yeah
def preorder_print(self, start, traversal):
if start:
traversal += (str(start.value) + "-")
traversal = self.preorder_print(start.left, traversal)
traversal = self.preorder_print(start.right, traversal)
return traversal
I am confused by this
doesn't preorder traversal already print out the values
def preorder_search(self, start, find_val):
if start:
if start.value == find_val:
return True
else:
return self.preorder_search(start.left, find_val) or self.preorder_search(start.right, find_val)
return False
def preorder_print(self, start, traversal):
if start:
traversal += (str(start.value) + "-")
traversal = self.preorder_print(start.left, traversal)
traversal = self.preorder_print(start.right, traversal)
return traversal
they have two preorder functions
what the hell is the point
lean dome
They... Do different things...
old rover
one searches for a value and one prints?
lean dome
One visits every element and prints it. One sees if any node in the tree holds a given value
They're both pre-order traversals, but what they do while traversing is entirely different
old rover
oh cool
ok
depth first search is like going down a rabbit hole
um
I still don't get the difference between in-order and post order
lean dome
In-order visits a node after its left child and before its right child. Post-order visits a node after its left and right child
lean dome
A leaf is a node without children
spring jasper
In a BST, inorder traversal is basically the order of values from lowest to highest
Its the "sorted" order
lean dome
It's also the left to right order of the tree if you draw it out on paper
Since, when you draw it, you draw every node in the middle of its left children and right children
Assuming you're good at drawing, at least 😅
lean dome
AVL trees are a special case of binary search trees that maintain an invariant that the two subtrees of any node never differ in height by more than 1.
agile sundial
it makes it so that operations on it always take O(log n) time, instead of O(h) time
fiery cosmos
you can implement a level traversal also, you need to add a next field for that, try it after each time an AVL treee is rebalanced 🙂
agile sundial
the height differs by more than 1 on different sides
lean dome
A completely unbalanced tree is a linked list. All the nodes are in a straight line from the root.
Balanced tree:
A
/ \
B D
/
C
Unbalanced tree:
A
\
B
\
C
\
D
Linked list:
A -> B -> C -> D
Those last 2 are the same picture, just rotated.
scarlet maple
lean dome
I could have been an artist
old rover
So it has nothing to do w the values
of the nodes
it has to do w it being a straight line
Ok
half lotus
It doesn't have to strictly be a straight line. As was said previously, it's when the heights of subtrees differ by more than 1.
At least in the context of an AVL tree that's what the definition is.
agile sundial
is it different for different flavors of bst?
half lotus
I don't know so I wanted to be safe
!e ```py
from binarytree import bst
print(bst(height=3))
@half lotus :x: Your eval job has completed with return code 1.
001 | Traceback (most recent call last):
002 | File "<string>", line 1, in <module>
003 | File "/snekbox/user_base/lib/python3.9/site-packages/binarytree/__init__.py", line 11, in <module>
004 | from pkg_resources import get_distribution
005 | ModuleNotFoundError: No module named 'pkg_resources'
lul
half lotus
But okay I guess I need to fix that
wow thank you very much I need to add setuptools just so it can fill a version variable. how useful
half lotus
Sounds to me like that would involve a sort
glossy breach
You can just sort it and add values to a dictionary:
lst = [103, 42, 13, 99, 10]
f = sorted(lst)
idx = 0
d = {}
for i in f:
idx += 1
d[idx] = i
lst = [d[i] for i in lst]
print(lst)
In terms of time complexity that would be dominated by the sort
But it does use o(n) memory
I can't think of a way to do it that wouldn't involve a sort but would be faster than a sort
half lotus
Don't use python then
agile sundial
100k is fairly small even for python. sorting and creating that map should still be very fast
half lotus
It's not sounding like that's good enough apparently
jolly mortar
might use numpy or something to speed things up a bit
glossy breach
It can be faster if the limit of the numbers is small enough
jolly mortar
scipy seems to have a rankdata function (https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.rankdata.html)
glossy breach
Oh
dapper sapphire
So I implemented this doubly linked list insert method. Wondering if I can get some feedback:
def insert(self, position, new_data):
new_node = Node(new_data)
current = self.head
previous = None
while position:
previous = current
current = current.next
position = position - 1
if previous is None:
new_node.prev = None
new_node.next = current
current.prev = new_node
self.head = new_node
elif current is not None:
previous.next = new_node
new_node.prev = previous
new_node.next = current
current.prev = new_node
elif current is None:
previous.next = new_node
new_node.prev = previous
new_node.next = None
I tried doing it without previous variable, but I couldnt do it
my singly linked list insert was a lot shorter mainly because we are just dealing with the next pointer. But because we have two pointer next and prev, it's a bit longer.
jovial tartan
Are leaves of a binary tree considered subtrees?
agile sundial
sure
agile sundial
the same way you can consider a single node as a tree
jovial tartan
so if I have this BST
would 3, and 6 all be roots of subtrees?
or just 4? nvm 4 is just the tree
sterile grail
lean dome
So I implemented this doubly linked list insert method. Wondering if I can get s...
Other than the fact that this will do wacky things if position is not a non-negative int, or if the given position is past the end of the list, this looks reasonable to me.
lean dome
would 3, and 6 all be roots of subtrees?
4 is a tree of height 1, with a left subtree 3 and right subtree 6.
3 and 6 are each trees of height 0, with no left subtree and no right subtree.
dapper sapphire
Yeah, I agree. I should take into consideration negative index and overboard index. I guess a quick fix would be index -1 would be a return and while loop would be something like:
while position and current so if the index goes overboard it will insert to the end.
lean dome
def insert(self, position, new_data):
new_node = Node(new_data)
current = self.head
while position:
current = current.next
position = position - 1
if current is not None and current.prev is None:
new_node.prev = None
new_node.next = current
current.prev = new_node
self.head = new_node
elif current is not None:
current.prev.next = new_node
new_node.prev = current.prev
new_node.next = current
current.prev = new_node
elif current is None:
current.prev.next = new_node # oops!
new_node.prev = current.prev
new_node.next = None
@dapper sapphire I think that's right for a version without previous
Wait, no it isn't. Scratch that: I don't think you can do a version without previous, unless you keep track of tail in addition to head.
If you've only got current and head, then when the position points you to the end of the list, you're holding a current that's set to None, and you have no way to know what the previous node was, to attach the new node to the list
dapper sapphire
lol I had something similar to what you just did, but yeah it didnt work because when we are at last node which is None we cant go back.
lean dome
Ah, actually, I think it will work if, instead of making current the node to insert before (as it is in your current version), you make it the node to insert after. Something like...
def insert(self, position, new_data):
new_node = Node(new_data)
if position == 0:
new_node.prev = None
new_node.next = self.head
if self.head is not None:
self.head.prev = new_node
self.head = new_node
return
current = self.head
position = position - 1
while position:
current = current.next
position = position - 1
new_node.prev = current
new_node.next = current.next
if current.next is not None:
current.next.prev = new_node
current.next = new_node
Actually I will run some test cases on this tomorrow.
lean dome
I'm typing this in a tiny window on a phone keyboard, heh
dapper sapphire
Actually I will test this right now lol
lean dome
I think that's right, at least 😅
dapper sapphire
oh wow it works
None <- 6 <-> 4 <-> 2 -> None
None <- 2 <-> 4 <-> 6 -> None
Inserted at 0
None <- |5| <-> 6 <-> 4 <-> 2 -> None
None <- 2 <-> 4 <-> 6 <-> |5| -> None
Inserted at 1
None <- 6 <-> |5| <-> 4 <-> 2 -> None
None <- 2 <-> 4 <-> |5| <-> 6 -> None
Inserted at 2
None <- 6 <-> 4 <-> |5| <-> 2 -> None
None <- 2 <-> |5| <-> 4 <-> 6 -> None
Inserted at 3
None <- 6 <-> 4 <-> 2 <-> |5| -> None
None <- |5| <-> 2 <-> 4 <-> 6 -> None
inserts |5|
lean dome
Making current hold the element to insert before means that at the end of the list it holds None, and you're in trouble because you don't know what came before it to link the new node to that previous node.
Making it store the element to insert after moves that edge case to the start of the list instead of the end, and at the start, you've got self.head available to use
Inserting at position 0 into an empty linked list is an interesting edge case here that you should test, too.
dapper sapphire
lmao your insert works on an empty list, but mine crashes hahaha
ok I will fix it tomorrow and look at your code. Thanks @lean dome ! Really appreciate the help!
lean dome
Yeah, yours tries to assign to self.head.prev in that case, which is None.prev, which fails
sly verge
hi guys, any pointers on how to normalize an array between 0 and 1?
round grotto
hi guys, any pointers on how to normalize an array between 0 and 1?
The math is something like this:
a = [0, 100, 34, 5, 3, 6]
high = max(a)
low = min(a)
norm = [(i-low)/high for i in a]
print(norm)
[0.0, 1.0, 0.34, 0.05, 0.03, 0.06]
sly verge
hi @round grotto thank you for the def. I'm trying with np.linalg.norm
before I try to implement your solution, is there any easy way to cast an np.array to a regular python array?
agile sundial
if it's in numpy there's certainly a np way, which would be way better than using lists
sly verge
@agile sundial it wasn't a numpy array, but after using the np method I'm getting back an np array. Anyway, I think I can work with that
agile sundial
you can just use the list constructor I think
round grotto
np.linalg.norm does this
Normalizing an array will return the normal form of the array, which has a vector magnitude of 1.
Which I believe is another type of normalizing than what you want, right?
sly verge
I'm not sure. Based on the example I found online, np.linalg.norm returns something and then I used that something to divide the original array, obtaining the normalized numpy array
round grotto
At least based on your question, I understood that you want an array with the same dimensions as the original, but where all of the values are between 0 and 1
round grotto
Put three ` above the code and under
agile sundial
!code
sly verge
'''
halcyon plankBOT
round grotto
Use backtick `
sly verge
norm = np.linalg.norm(mse_partial_results)
norm_mse_partial_results =
mse_partial_results / norm
norm_mse_partial_results =
list(norm_mse_partial_results)
norm_mse_partial_results.insert(0,
path_a[-9:]) norm_mse_partial_results.append(";")
I needed the regular array as opposed to a np.array in order to insert the strings
here's the code for normalizing the array
it didn't work. It seems I need to convert the python array into a np array before doing the np.linalg.norm
round grotto
I believe my original suggestion should have been
a = [0, 100, 34, 5, 3, 6]
high = max(a)
low = min(a)
r = high-low
norm = [(i-low)/r for i in a]
print(norm)
To give the right result, when min isn't 0
This can also be accomplished with np as
import numpy as np
a = np.array([0, 100, 34, 5, 3, 6])
norm = (a - np.min(a))/np.ptp(a)
print(norm)
And if you want it as list:
import numpy as np
a = np.array([0, 100, 34, 5, 3, 6])
norm = (a - np.min(a))/np.ptp(a)
as_list = list(norm)
print(as_list)
Now, I have a question. (I asked in a help channel instead)
Why is split faster than index, here?
import timeit
message = "This isatestwith1space"
n = 1_000_000
print(timeit.timeit(lambda: message.split()[0], number=n))
print(timeit.timeit(lambda: message[0:message.index(' ')], number=n))
0.1783948
0.21728000000000003
If there are more spaces in the message, index will be faster
sly verge
thank you very much @round grotto
round grotto
You're welcome 🙂
sly verge
any idea why np.around may not be working? I'm doing the following
np.around(norm_mse_partial_results, 2)
print(norm_mse_partial_results)
>>>[0. 0.56356602 0.03644162 ....]
the np.around function doesn't change the array you give it
It returns a new array, where the values are rounded
sly verge
I thought the output was optional
from github
Examples
--------
>>> np.around([0.37, 1.64])
array([0., 2.])
>>> np.around([0.37, 1.64], decimals=1)
array([0.4, 1.6])
>>> np.around([.5, 1.5, 2.5, 3.5, 4.5]) # rounds to nearest even value
array([0., 2., 2., 4., 4.])
>>> np.around([1,2,3,11], decimals=1) # ndarray of ints is returned
array([ 1, 2, 3, 11])
>>> np.around([1,2,3,11], decimals=-1)
array([ 0, 0, 0, 10])
You have two options:
import numpy as np
# Option 1
a = np.array([3.00005, 23.345, 0.0001, 0.001, 0.009])
rounded = np.around(a, decimals=2)
print(rounded)
# Option 2
a = np.array([3.00005, 23.345, 0.0001, 0.001, 0.009])
np.around(a, decimals=2, out=a)
print(a)
damn I'm an idiot. Thanks again
round grotto
No worries, let me know if there's anything else
sly verge
can I do a = np.around(a, decimals=2)
round grotto
Yes
sly verge
cool, thanks
round grotto
I assume out= is slightly faster, though. It should use the existing array instead of creating a new one and assigning a to that.
old rover
not sure if this is the right channel for that
but I also don't know if we have a channel for that
rare charm
nocturne harbor
Hi, I just implemented the levenshtein distance and came across a weird case:
b a c
[0, 1, 2, 3]
a [1, 1, 1, 2]
b [2, 1, 2, 2]
Here, there should be two 1 cost substitutions and 1 insertion leading to a total cost of 3. However, the cost turns out to be two through the sequence a -> b, a -> a, b -> c. So it's the zero cost substitution of a with a that breaks things. Does anyone know which condition I might be missing here?
agile sundial
are you including swapping adjacent letters?
nocturne harbor
I'm not including transposition
This is using only insertion, deletion and substitution and is a 1:1 implementation of the pseudocode on wikipedia
Even doing it by hand I still arrive at this so there seems to be something missing
Even online implementations produce this result: http://www.let.rug.nl/~kleiweg/lev/
actually nvmd I'm wrong. The correct path is inserting b at the start and then substituting b with c
wet urchin
Hi there, Can someone help me with linked lists? I can't understand.
nocturne harbor
What specifically are you having trouble with?
wet urchin
class Node:
def __init__(self, data):
self.data = data # Assign data
self.next = None # Initialize
# next as null
class LinkedList:
def init(self):
self.head = None
I don't understand what is a node
and why he puts in self.head the word None.
hushed geyser
You can think of the node as 1 piece of data
Each node stores exactly 1 value (in self.data)
The reason it's not just an integer or something (in the case that you are making a linkedlist of integers) is because with a LinkedList, each node, or each item that is in the LinkedList, needs to know what the node or item after it is
And so in order for the node to know what the node after itself in the list is, it is made into a class so that another variable, self.next, can store a reference to the next node
The reason they did self.head = None is because head refers to the first Node in the LinkedList. The "head node". Each node knows what the next item in the list is after itself, so when you have the first node or "head node", then you can find the second node by doing head.next (because each node has a next property storing a reference to the node after itself in the list)
When you first create a LinkedList, you have no items or data in your list. Therefore you don't have any nodes to refer to, so head will be None until at least one element is added to the LinkedList.
old rover
wow this was a good explanation
why did Udacity just decide to skip the implementation for heaps
🙂
!pastebin
halcyon plankBOT
old rover
is this a good implementation of a heap
why did Udacity just say "heap implementation"
but not even show any actual code for the heap
nocturne harbor
Honestly when I implement (a derivative of) a common data structure or algorithm like that I usually just check the pseudocode on Wikipedia
old rover
class MinHeap:
def __init__(self):
self.heap_list = [0]
self.current_size = 0
what's the point of not putting heap_list and current_size in the paramaters of the def init
vocal gorge
putting current_size there would be weird, as it's calculated from heap_list
as for not allowing to create it from an existing list - meh, just the way they chose to make it
vocal gorge
most operations on the tree are O(<height of that node>)
hushed geyser
The more unbalanced your tree is the more taxing it is going to be to find an element, for example if you balance your tree properly and you have 8 values in it, say there's the head node, 3 nodes on the left, and 4 nodes on the right, then at most you'll have to go down like 2 levels past the head to get there. But if you have a head node and 7 values all to the right of each other than you're going to have to go down 7 levels past the head to get there, and that's really inefficient
vocal gorge
if you don't balance your tree, in the worst case it may degenerate to something like a chain, where the height is at worst n. A perfectly balanced tree, meanwhile, has highest height at log n.
see also: AVL trees
nocturne harbor
I tried writing a self balancing interval tree two years ago and never got around to finishing it
Might be a good exercise to go back to that with a fresh mind
old rover
def sift_up(self, i):
while i//2 > 0:
if self.heap_list[i] < self.heap_list[i//2]:
self.heap_list[i], self.heap_list[i//2] = self.heap_list[i//2],self.heap_list[i]
i = i//2
what is i supposed to be
index?
self looks like it's the heap
vocal gorge
...well, yes, it's an instance method.
old rover
but what's i
I don't know for some reason this code is confusing
whatever
heaps are just another form of trees
vocal gorge
Do you know what sift_up is supposed to do? Like, don't you have a description of what methods heaps must have?
or where did you get this source?
vocal gorge
yeah, the ith value it looks like
old rover
this is the source
nocturne harbor
If the value is in a place where it doesn't satisfy the heap property it needs to be moved up or down until it's satisfied again
which, after looking at the source you linked, I now realize is already specified in the documentation
old rover
a max heap needs the values of the parent nodes to be higher than the child nodes
a min heap has the parent values lower than the child values
that is the heap property
right?
nocturne harbor
Exactly
old rover
so this is to create a heap
and this is heapsort?
so what is the point of implementing a heap?
when heapsort turns the array into a heap
am I making sense?
agile sundial
heaps are commonly used to implement priority queues
heapsort works by creating a heap and repeatedly popping the min (or max) off
old rover
so I have to know both things
agile sundial
huh?
old rover
nvm
lean dome
In a regular queue, each pop returns the value that was enqueued least recently. In a priority queue, it returns the item with the highest priority, instead. You could implement that by sorting all the items by their priority each time a new item is added, and always having dequeue take the last one. But sorting is pretty slow. Using heaps gives you a way to find what's the highest priority value without needing to pay the cost of keeping the items completely sorted by priority
old rover
it's ok I'm watching a vid on it rn
wet urchin
You can think of the node as 1 piece of data
Thanks a lot. 🙂
old rover
!rule 5
halcyon plankBOT
old rover
the point of a contest is so that you compete based on your own ability
light birch
bruhh
old rover
🤷
light birch
it s a test its ez but need sm1 pro domain
sudden sinew
@light birch We wont help you with an active test/contest.
Please don't ask people to
weak panther
Idk if this is the right channel to ask this in.
auction_id = i['id']
item_id = i["item"]['id']
# if 'bid' in i:
# bid = i['bid']
# else:
# bid = 'nil'
if 'quantity' in i:
qty = i['quantity']
else:
qty = "nil"
if 'bonus_lists' in i['item']:
bonus_lists = 'true'
else:
bonus_lists = 'false'
# if 'modifiers' in i:
# modifiers = 'true'
# else:
# modifiers = 'false'
if "pet_species_id" in i["item"]:
pet_species_id = i["item"]['pet_species_id']
else:
pet_species_id = '0'
pet_species_id = res.headers['pet_species_id']
current_time = res.headers['Date']
I'm trying to dump sections of an item string into a file that's used in game. These variables change in value and I don't know how to structure them accordingly.
Do I really need to use if else statements or can I just follow what I did for auction id and item id?
Some strings don't use modifiers or bonus_lists.
light birch
<@!461953914351386625> We wont help you with an active test/contest.
why ppl r like that
old rover
this Abdul Bari guy is great
I just wish his stuff was in Python not C++
but ds/algos is language agnostic so it doesn't really matter
light birch
sm1 to help it s just a schoool shit
alpine tide
!warn 461953914351386625 You've been told we won't help with that here. Please stop asking.
halcyon plankBOT
:incoming_envelope: :ok_hand: applied warning to @light birch.
lunar jacinth
whats the best way to get some practice on algos and data structs?
half lotus
There isn't a best way. What may work well for one person may be ineffective for another.
Using sites like leetcode and hackerrank to practice is a popular choice. You could try that.
Or maybe you'd prefer to purchase a book and do the problems out of that.
old rover
pick your poison
unkempt umbra
is there a python implementation of a scapegoat tree that doesnt use classes to represent nodes?
acc wait k nvm
lean dome
If you have something that does use classes to represent nodes, you can easily replace it with something that doesn't...
unkempt umbra
im using lists rn to store the nodes
but k better question
i wanna find an iterative version of the tree rebuilding
lean dome
Anything that's done recursively can be turned into an iterative algorithm by replacing the call stack with an explicit stack in the code.
To be any more specific, we'd need to see the code.
unkempt umbra
dang rip aight imma try coding up the version i got in my head
and sry i only got inserting and deleting rn
fiery cosmos
Anything that's done recursively can be turned into an iterative algorithm by re...
No sure about that, tail recursion can often be replace by iteration, replacing general recursion by usign only a stack od data I dont think so, you probably need some kind of state machine that also map the recusion path ...
vocal gorge
but a stack is just, like, how function calls work
half lotus
I read that the trick was to convert it to tail call recursion first and then convert that to iterative.
Granted that isn't much of a trick since it isn't always obvious how to convert something to be tail recursion
fiery cosmos
but a stack is just, like, how function calls work
a function call encode you entry and exit place in the code and at the same time you data state, if your problem has many situation of recusion call (ex what do withthe result base on a condition) then this is not save in you stack of data in an iteration mode ...
lean dome
Well, I didn't say the stack you replace it with would contain only the data, to be fair.
weak panther
Can I ask about f-strings usage in here?
unkempt umbra
i think that would be better suited for a more general help channel
cuz this channel is for algorithms and stuff
weak panther
I figured it would be in the realm of solving problems in python.
I'll post over there
fiery cosmos
hi, how can i do something like command option text?
sudden garden
is there a discord group or any other nice communities that focuses on competitive coding?
fiery cosmos
hey could someone help me with this data structure problem
We want to design a list-like data structure that supports the following operations
on integers.
• addToFront(e): Adds a new element e at the front of the list.
• addToBack(e): Adds a new element e at the end of the list.
• removeFromFront(): Removes the first element from the list and returns it.
• removeFromBack(): Removes the last element from the list and returns it.
• setElement(i, e): Sets the element of the i-th element of the list to e.
Each operation should run in O(1) time. You can assume that we know that the list
will never contain more than k elements (k is not a constant and should not show
up in your running time).
half lotus
This sounds like something that can be implemented using a ring buffer.
Maybe not actually. I didn't think about it too hard.
Yeah, I think a partially filled buffer will always have space after/before the start and end, so doing operations on the head and tail should be constant - wouldn't involve shifting elements.
fiery cosmos
what is buffer space
half lotus
The size of the buffer would be k, if that's what you're asking
fiery cosmos
what is a buffer i am asking
half lotus
It's just an array basically
fiery cosmos
okay so what kind of data structure i need to create
half lotus
The underlying data structure would be a list. You'd need to fill it with k initial values to get the list to the correct size. Initial values can be anything e.g. None.
fiery cosmos
okay how do i make all the given operations in constant time