when you visit a node, you enqueue its child nodes
#algos-and-data-structs
oblique panther
you also pop the node that you're visiting off the queue
then you go to the next one
kindred flame
and how can i yield all of these
so lets say we have this
14 (root node)
7 21
3 10 17 25
oops
14 (root node)
7 21
3 10 17 25
hmmm why is it not indenting correctly
oblique panther
it's alright
I see what you mean
so when I say "visit a node", "visit" can mean a lot of different things depending on the situation
it just means "do the thing", basically
kindred flame
se you are saying we first add 14 and 7 and 21 to the queue
then 7 3 10
then 21 , 17 ,25
but wouldn't that make duplicates
oblique panther
so if the point of your search is to yield every node in BFS order, yield node would be the visit
that's not the order you'd visit them for BFS
starting at the root, you have to visit each node that's one away from the root before you can visit any that are two away from the root
oblique panther
yes
kindred flame
I know how the function is supposed to output but i don't know what to add to the queue
oblique panther
once you've enqueued all the nodes reachable from the node you're on, you can officially visit that node
kindred flame
like i can see it takes them line by line from left to right
oblique panther
and then go on to the next one in the queue
kindred flame
which node are you talking about
oblique panther
whichever node you're about to visit
kindred flame
enqueue is adding to the queue ?
hmmm I think the way you explained it make it seem not the same way as it was supposed to be implemented
oblique panther
@kindred flame "enqueue" and "add to the queue" mean the same thing
kindred flame
okk
jolly sigil
I need to map the following ranges to 0-total-1 points so that If I lookup a value in the original range I get back a number indexed to 0. Some of the ranges are decreasing. Starting range is z1.
For example 150000 maps to 0, 31800 maps to 118,199, 1557100 maps to 1,637,000.
I could so this by making ranges for each interval but maybe there is a better way. I could to is with a linear function also.
Any other ideas of a clean way to do this. Ideally some fiction that would accept an arbitrary list of ranges and return a mapping function.
z1 = (150000, 31800)
z2 = (893300, 1005000)
z3 = (1557100, 149999)
placid trout
your idea is vague
halcyon rain
hi all( i have been working on a 15 line code ( list evaluator )
i spent like 3 hours so far... still i have syntax errors
its due tomorrow... can someone help me
its just 15 lines that i have
halcyon rain
the topic is algoritm.. so i came .. sorry for that bro
quasi gyro
Can someone explain this to me, I found it on stack overflow but I don't quite understand how it works (btw this is the algorithm for the goldbach conjecture)
def eratosthenes(n):
primes = list (range(2, n+1))
for i in primes:
j=2
while i*j<= primes[-1]:
if i*j in primes:
primes.remove(i*j)
j=j+1
return primes
def odd_primes(N):
oddprimes = eratosthenes(N)
oddprimes.remove(2)
return(oddprimes)
def goldbach(N):
x, y = 0, 0
result = 0
if N % 2 == 0:
prime = odd_primes(N)
while result != N:
for i in range(len(prime)):
if result == N: break
x = prime[i]
for j in range(len(prime)):
y = prime[j]
result = x + y
if result == N: break
return x, y
I don't understand the yielding
of the different functions
cobalt sedge
We have two menus from two restaurants, and each of them has n items. More specifically, there are two arrays A[1..n] and B[1..n], representing the prices of items of the two menus respectively. A[i] is the price of the i-th item in menu A, and B[j] is the price of the j-th item in menu B. You want to order one item i from restaurant A and one item j from restaurant B, so the total price is A[i] + B[j]. To save money, you want to list out some of the combinations of items from the two menus according to their total prices. Therefore, you are going to give the first k combinations of items in increasing order of their total prices, where k < n.
For simplicity, assume that no two items have the same price regardless of which menu they belong to, and that the two menus have been sorted in increasing order of the prices, which means for all 1 โค i < j โค n, we have A[i] < A[j] and B[i] < B[j]. We assume that the total price A[i] + B[j] is distinct for a distinct combination (i, j).
Design your algorithm using the heap data structure. Your algorithm should run in O(k log k) time. Proof of the algorithm is not necessary.
Therefore, you are going to give the first k combinations of items in increasing order of their total prices, where k < n.
What is this question about... Is it mean I am going to make a heap tree like this?
For i from 1 to n:
Insert(A[i]+B[i])
Insert is the insert of the heap tree
fiery cosmos
@quasi gyro what part of the algorithm seems difficult to you?
the eratosthenes one or goldbach one?
goldbach conjecture states than any even positive number besides 2 can be expressed as sum of two odd prime numbers
so what you are doing is checking if thats true for a given N.
First you find all the odd primes until N using eratosthenes method.
Second you find two integers in those odd primes such that they sum to N
quasi gyro
No that I understand
I don't understand how the second function and third get the yielded of the previous one
fiery cosmos
okay first functions finds all the primes from [2...N]
and second function calls the first one and removes 2 from it which yeilds all the odd prime numbers
and the third calls second and stores all those odd primes in prime variable in the code
did you understand?
quasi gyro
but doesn't a function only execute when called?
fiery cosmos
yes true
quasi gyro
so how do I call this?
fiery cosmos
which one?
fiery cosmos
yep
quasi gyro
would call upon the others
fiery cosmos
yes
fiery cosmos
๐ you will learn more techniques when you do math in programming
@cobalt sedge can you link the source of this problem
cobalt sedge
Maybe i put a screen capture here, as it is a question of my course
pale steppe
Maybe i put a screen capture here, as it is a question of my course
@cobalt sedge
i think they want heap structure of combination of a[i] + b[j]
cobalt sedge
they want me to have a increasing order of the total price list, and the array A and B is already sorted. Isn't it the combination of A and B is just S[1] = A[1] + B[1]
S[2] = A[2] + B[2]
....
S[k] = A[k] + B[k]
And write a heap data structure which every notes store S[i] ?
I am not sure am I interpret it correctly, coz I think it wont be that straight forward
final fjord
good morning, I am trying to get this to take a string(user_string) and remove anything that is not an alphabetical character and create a list of those characters, but this is not removing any integers at all.
snow swift
not an algo or ds question
#โ๏ฝhow-to-get-help @final fjord
and its char.isalpha()
final fjord
thank you
gloomy mason
I'm trying to something rather simple where I make a float into a integer by just removing the decimal places but what I am trying does not seem to be working properly. Any chance anyone can help a noob out?
def change_number(number):
number = number / 4
if number is float:
number = int(number)
super().change_number(number=number)
candid lichen
@gloomy mason Don't bother with the super() method, there is no class to apply it on
Import the math library, and use the floor() method to round down
Sample code:
def change_number(number):
if number == int(number):
print("Please enter a float")
else:
print(math.floor(number))
change_number(4.78)```sorry, just copy pasted the method. thanks though
candid lichen
No problem
wispy sierra
@cobalt sedge you have not understood the question correctly.
it asked u to get k smallest of pairs from A and B. So if you have
A= [1,2,3,4], B= [6,7,8,9,10], you will have 4*5 = 20 different pairs and get k smallest pairs from that 20 pairs
you ll need to apply min heap to obtain the complexity of O(klog(k))
try to play around with some example to see whether u can think of any way to solve that problem, else i ll explain my algorithm for u but give it a try first
slender kestrel
can anyone suugest me a book for datastructures and algorithms
that has pdf available online
please @ me
fiery cosmos
https://discordapp.com/channels/267624335836053506/650401909852864553/769833512252735489
Is online one and CLRS is available as pdf just give a google search
@slender kestrel
pale steppe
@cobalt sedge you have not understood the question correctly.
it asked u to get k smallest of pairs from A and B. So if you have
A= [1,2,3,4], B= [6,7,8,9,10], you will have 4*5 = 20 different pairs and get k smallest pairs from that 20 pairs
@wispy sierra
it can be done in O(n) as we know a[i] + b[j] where i < j so we know by sure that if we iterate through a in sequence we will get increasing price
fiery cosmos
@slender kestrel Cormen algorithm textbook, actually there are four authors and I remember only 1 lol
cobalt sedge
@pale steppe thanks for ur help, is it mean that if k is 5, the pair would be: 1,6 2,6 1,7 2,7 1,8 3,6 ?
@wispy sierra i will try that first thanks
wispy sierra
@pale steppe I dont really get what u mean, if you dont mind, please give me more details, it isinteresting to find the solution O(n) (perharps u mean here is k ??)
anw, i have heard the method for O(k) to find the kth largest value ( only one value) but not really read about it
pale steppe
@pale steppe I dont really get what u mean, if you dont mind, please give me more details, it isinteresting to find the solution O(n) (perharps u mean here is k ??)
anw, i have heard the method for O(k) to find the kth largest value ( only one value) but not really read about it
@wispy sierra
yea i tried it it is useless ๐ my bad sorry
@pale steppe thanks for ur help, is it mean that if k is 5, the pair would be: 1,6 2,6 1,7 2,7 1,8 3,6 ?
@cobalt sedge yea note one thing that i is strictly smaller that j 1,6 is not a possible combination
cobalt sedge
Okay, thanks I think Ive got the answer, really thanks for your help
For this question, I have got your help and said we can sort it by P[i]/L[i] but I dont get why the ans is P[i]/L[i].... could someone explain it? thanks
wispy sierra
for that timetable question, even we use sort but the idea based on Greedy (at least in my view) so there are no prove or for sure that the approach is optimal solution
@cobalt sedge @pale steppe I still believe u guys have read the question wrong for the Kth smallest elements. the i, j part is to ensure there is no duplicate value for each array. it is no related to "i strictly less than j for a[i] and b[j]", for my example: there are 20 pairs includes: a[1][b[1], a[1]b[2],...,a[1]b[n],a[2]b[1],..a[2]b[n].. till a[n]b[n]
pale steppe
@wispy sierra yeah maybe it is typo coz otherwise this question will not require heap
cobalt wraith
hi
having a problem with this newb code
def Impact():
print(SelectionImpact)
if SelectionImpact == "Glances" or "Clips":
print("the")
elif SelectionImpact == "Collides":
print("With")
else:
print("into the")
its always returning the
never into the
sorry, wrong place
topaz pulsar
halcyon plankBOT
covert maple
What's a depth-first Algorithm, I seemed to have come across one when generating a randomised maze structure?
fiery cosmos
Yes a depth-first algorithm is the same when you are in real life trying to figure out the exit of a maze, but you do in the following way
You select a path and you go to the path as deep as you can, you might not find the exit so you comeback few steps back and see if there is anything left to visit, if there is you again visit it as deep as you can.
You keep doing this until you reach an exit or you completely visited everything
agile sundial
it's useful when you know the solution is at the bottom of the tree (in a maze it is)
fiery cosmos
No it should be a graph, tree and graph are a bit different ๐
agile sundial
sure
brave oak
No it should be a graph, tree and graph are a bit different ๐
@fiery cosmos a tree is a kind of graph...
agile sundial
when you dfs you create a tree
gleaming badger
does anyone who knows dynamic programming have 5 minutes?
cant understand a piece of code
fiery cosmos
well when it should be a graph you should not say tree,
you can say tree as a graph but not vice versa
agile sundial
sure
runic spoke
pure slate
I come from a TypeScript background where I can really easily define specified data structures in the form of typed objects, which guarantee certain fields exist. In Python I haven't really found a proxy for this to have "fixed" data structures.
Is it common to define a class without methods for this kind of 'records'? Is that bad form? Are there other paradigms to approach this?
pure slate
@snow swift Named tuples are not mutable so not really what I am looking for.
Dataclasses aren't anything more than syntactic sugar for writing the __init__ based on the constructor's arguments, right?
So yea, they could be used for the method-less class I described, but that still leaves the question whether that's a common pattern, bad practice, or there's something else out there
arctic veldt
dataclass looks like exactly what you want
snow swift
^
arctic veldt
should you use it? i would reach for a dict and let it crash if something tries to access a missing field
pure slate
Thanks for pitching in ๐
Right now I've been alternating between simple dicts and dataclasses, depending on the complexity of the data structure I was going for. Big advantage of the class approach is the autocomplete, which you don't get for dictionary keys, and being guaranteed fields exist.
snow swift
personally i dont like using dicts as records/structs
arctic veldt
yea speaking more about the question of whether that's a common pattern/good practice
snow swift
because dicts are more used specifically for mapping keys to values
unlike js objects
gusty grove
if i have a 3d grid of values, how can i find local minima?
lunar schooner
like a gradiant?
arctic veldt
personally i don't like using dataclasses with default values, defaults can make failures silent
so the question is do you want it to fail when you instantiate or when you access
and in that context namedtuple is just as good
(but immutable)
pure slate
That's a fair warning. I usually have no defaults. If there are defaults, the problem is simple enough to use a dictionary and d.get()
arctic veldt
@gusty grove this? https://stackoverflow.com/a/3986876/5939768
pure slate
An example of where I ran into this specific issue: I was working on a simulation study, and we were running hundreds of different configurations.
Configurations were a dictionary with parameter names and values that were used to initialize each simulation.
However as the scope grew and new parameters were added this got quite chaotic. For example, later down the line these same config dicts were used in the analysis ("all sims with param x = val y performed above average") and things got pretty spaghetti. A class could the simulation config could have prevented a lot of issues in our unit testing and probably streamlined development
arctic veldt
interesting, so you can forcibly deprecate and curate the parameter space better with a dataclass
pure slate
That's my thought, yea. And it is self-documenting code as there is now a fixed record of which parameters exist.
arctic veldt
generating docs is a big win for dataclass
a tricky thing i'm running into now is the people configuring might not be coders or even have access to source code
so docs for parameter space kind of need to be on a google drive or something
but if i could just link to generated autodoc it would be ideal
pure slate
In this case anyone working with the code would be a team member of mine, as it was part of a research project within our business unit. So only a handful of people would be messing with it. But for future proofing it would be a big win.
arctic veldt
a caveat of dataclass is it can be a lot slower to instantiate and a little slower to access fields compared to dict, for parameters probably not a thing
for simulation objects, maybe a thing
also this answer touches on __slots__ which is very relevant https://stackoverflow.com/a/55256047/5939768
more words on dataclass and slots https://www.python.org/dev/peps/pep-0557/#support-for-automatically-setting-slots
pure slate
Cheers for the supplementary materials!
In the example I mentioned the config was only used when instantiation a Simulation class, so then access wasn't really a big deal.
eager hamlet
http://www.usaco.org/index.php?page=viewproblem2&cpid=551
would a slightly modified dijkstra's work for this? (ping 2 reply)
keen hearth
@eager hamlet possibly
I suppose a tricky element of that approach is going to be knowing when to stop.
That is, knowing when the maximum energy has been achieved.
keen hearth
Hey ๐
Also, perhaps Dijksta's wont work as the energy level can go down as well as up.
Another way to think of the problem is this:
- You look at all possible paths through the field.
- For each path you plot a line graph of Bessie's energy over time.
- You find the global maximum of each line graph.
- You find the maximum of the maximums.
Obviously this is a naive approach, but it's a way to picture the problem, and might lead to a more efficient approach.
My approach would always be to try to find as compact a representation of the search state as possible, and to find ways to prune the search tree.
There might be a "trick" to solve it with a greedy algorithm, but that's the sort of thing you either see or you don't.
keen hearth
Because Bessie doesn't eat grass with the same or lower quality again, you don't need to keep track of which patches she's visited.
Sorry, trying to stick to the analogy here ๐ฎ
So, you can represent the current state as a triple:
- The patch she's currently at.
- Her current energy level.
- The highest quality level so far.
But this is still a large state-space: 10**3 possible patches, 10**9 possible energy levels, and 10**6 possible 'highest quality' levels.
eager hamlet
yeah, even if i used java i wouldn't be able to do it lol
keen hearth
So, basically, you're trying to find the maximum energy level of any search state.
You can probably calculate an upper-bound on the energy achievable at or after a state.
And use this for pruning.
- Any reachable state.
void kiln
I created my own sort called Hamburger Sort. Does anyone know if a sort like this exists already and how to calculate the time complexity of such a thing.
import math
list_to_sort = [3,1,1, 100, 100, 100, 5.3,33.9,40,40,40,40,80,90,30,86,69,43]
def Hamburger_Sort(Hamburger):
length = len(Hamburger)
temp_list = Hamburger
sorted_list = []
for iteration in range(math.floor(length/2)):
top_bun = temp_list[0]
bottom_bun = temp_list[0]
for n in temp_list:
if n > top_bun:
top_bun = n
if n < bottom_bun:
bottom_bun = n
temp_list.remove(top_bun)
temp_list.remove(bottom_bun)
sorted_list.insert(iteration, top_bun)
sorted_list.insert(-(iteration+1), bottom_bun)
if len(temp_list) == 1:
sorted_list.insert(math.ceil(length/2), temp_list[0])
return sorted_list
print(Hamburger_Sort(list_to_sort))```I posted this in two discord servers in hopes of getting answers twice as fast
keen hearth
How does it work?
arctic veldt
iterations based on length / 2 is O(N) right?
flat sorrel
not sure about the first part, but you have n/2 iterations in your for loop and for each of those iterations, you're iterating through the entire input list of n elements, so that would be O(n^2)
flat sorrel
oops I missed that
so it would be n + (n - 1) + (n - 2) + ... + (n / 2 + 1)
it's still O(n^2), as you can see each term is still on the order of n (you can compute the exact total since you're just summing an arithmetic series)
arctic veldt
it's not the "cocktail shaker sort" which is bubble sort, not exactly sure of that nomenclature
keen hearth
So, each iteration it finds the largest and smallest remaining values, and inserts them iteration places from the beginning and end of the list respectively.
So, it's kind-of like a double-ended insertion sort?
arctic veldt
wikipedia throwing out confusion on that, it's just double selection sort
arctic veldt
on the grill
split nymph
shrewd cradle
The return probably does work, but return does not print
You can do print(findMedianSortedArrays(nums1, nums2)) to print the returned value
keen hearth
If you don't create a reference to the object returned by a function, then the object is discarded.
Creating a reference just means, e.g., assigning it to a variable or saving it in a list.
If you do:
x = 1 + 1
```it calculates the value of the expression `1 + 1`, and then saves the result in the variable `x`.But if you just do
1 + 1
```it calculates the value and discards it.@eager hamlet whether we allow to go pass the same patch multiple time?
true inlet
@wispy sierra yes.
fiery cosmos
yes
an
algorithym question
I have a function called download,
def download(pkglist):
loop = True
index = 0
try:
while loop == True:
pkglist[index] = pkglist[index].replace(" ", "space")
printf(f":: Downloading {pkglist[index]}...")
url = f"{config.server}{config.repository}/{pkglist[index]}.tar.gz"
try:
request.urlretrieve(url, "{}/{}.mkg.tar.gz".format(getcwd(), pkglist[index]))
printf(f"{try_done}\n")
except:
printf(f"{try_error}\n")
printf(f"{op_fail} Unhandled error happened.\n")
printf("The error may be due to poor or absent internet or the package cannot be found.\n")
index = index + 1
except IndexError:
loop = False
When I execute it I don't know why but, this try block,
try:
request.urlretrieve(url, "{}/{}.mkg.tar.gz".format(getcwd(), pkglist[index]))
printf(f"{try_done}\n")
except:
printf(f"{try_error}\n")
printf(f"{op_fail} Unhandled error happened.\n")
printf("The error may be due to poor or absent internet or the package cannot be found.\n")
gets executed before this print function,
printf(f":: Downloading {pkglist[index]}...")
and why? Isn't printf function supposed to gets executed before than try-except block?
sudden sinew
The code will be executed in order, so printf(f":: Downloading {pkglist[index]}...") should be executed before the try block, what is making you think it is not?
fiery cosmos
I see,
It uses internet
And my internet is slow
So there is a delay while printing it
sudden sinew
printf(f":: Downloading {pkglist[index]}...") should be printed pretty much as soon as the function is called (assuming there is no indexerror on the first loop), then there may be a pause while it downloads, and then it should print if it failed or succeeded
fiery cosmos
"should be printed pretty much as soon as the function is called" if yes,
DONE should be added to near to it after a delay
but DONE and download status indicator gets output at the same time
sudden sinew
Is the download working?
fiery cosmos
yep
it downloads the file
and does not brokes the binary of file
there is no problem with it
sudden sinew
Maybe the pause before printf(f":: Downloading {pkglist[index]}...") is something else, e.g. something being run before calling the function, or the python interpreter starting up
fiery cosmos
pause before printf(f":: Downloading {pkglist[index]}...") its because of request.urlretrieve(url, "{}/{}.mkg.tar.gz".format(getcwd(), pkglist[index])) function executed before than printing function.
fiery cosmos
def printf(value):
return print(value, end="")
but I tried with straight print() function too
it does not works either
sudden sinew
Try changing it to return print(value, end="", flush=True)
sudden sinew
flush: whether to forcibly flush the stream. By default python will only output to the screen on a newline character, before that it will just keep it in a buffer
sudden sinew
Niiice ๐
fiery cosmos
soooooooo much
wispy sierra
@keen hearth @eager hamlet in that case, just use Dynamic programmjng then O(n^2)
Start by sorting the node by the Q increasing order which mean i<j then q(i)<q(j) nlogn for this sort
Then for s[i] shows the best benefit if i is the last node, intialize s[i] = q[i].
S[i] = max (s[i], s[j]+q[i]- (eรdistance[i,j])) for all j <i (based on the order from previous sort) O(n^2)
Distance[i,j] is the shortest path from i to j, we could pre-calculate using BFS (O(n+E))or any other method u like and store in 2dimension array.ex, if we have a graph which 1-2, 2-3, 1-4, 3-4 then distance[1,2] = 0, distance[1,4]=0, distance[2,4]=1
The final result is max value from s[i]
๐๐Plz let me know if there is test case proving this approach does not work ๐
royal kestrel
it's not like you can look it up ๐
regal sparrow
can someone explain me how to do that? or you can even code it if you are bored because I need this homework so much on tommorow but idk how to do it
Write a function that takes any string and any character, and returns the ASCII code of the character if the character is in a string.
but if you dont want to code just please explain how to do that
fiery cosmos
You can use in function to check whether the character is present and ord function to get the ascii value now you code it
placid wolf
anyone familiar with conflict-directed backjumping algorithms?
fading granite
can anyone help me with a shuffle encryption algorithm?
placid wolf
I figured it out, thanks
fading granite
import string
def encode_text (s):
new = ''
random.seed (2)
letters = list(string.ascii_lowercase)
newletters = list(string.ascii_lowercase)
random.shuffle (newletters)
for i in range (len (s)):
print (s[i], letters.index (s[i]), newletters.index(s[i]))
new += letters [newletters.index(s[i])]
return new,newletters,letters
def decode_text (s):
new = ''
# add your code to decrypt here
# first number is original position in unscrambled alphabet. second number is scrambled. find way to reverse and implement
#abcdefghijklmnopqrstuvwxyz
#random.seed(2) outputs the same randomization everytime. use this to reverse the encryption
newletters,letters = encode_text(s)
#print(newletters)
#print(letters)
"""for i in range (len (s)):
print (s[i], letters.index (s[i]), newletters.index(s[i]))
new += letters [newletters.index(s[i])]
"""
return new
def main ():
textToEncode = input ("Enter text to encode - lower case letters only: ")
encodedText = encode_text (textToEncode)
origText = decode_text (encodedText)
print ("Original text: ", textToEncode, "\n")
print ("Encoded text: ", encodedText, "\n")
print ("Decoded text: ", origText, "\n")
if textToEncode == origText:
print (decode_text ("yipscekbwektipn"), "- there is a match!")
else:
print ("Oups - text does not match!")
if __name__ == "__main__":
main()
my issue is in the decode_text method
i cant figrue out what to do
the encode text part was done for me but the decode is making my brain hurt
the comments are personal notes that i thought would guide me in the right direction but I havent gotten anywhere
snow swift
hm
the encode maps each character from a char in newleteters to a char in letters
so for the decode
just map each character from a char in letters to a char in newletters
fading granite
thats the issue im having. im struggling with python so im not sure how to do that
snow swift
do you know what new += letters [newletters.index(s[i])] does?
fading granite
i have a feelign that i do but i dont know how to put it into words so no i dont
snow swift
ok lets break it down
s[i] is the current character
newletters.index(s[i]) will get the index of the current character in newletters
and then letters[] will get the character in letters at the same index
in other words, letters[...] gets the corresponding character in letters to the input character in newletters
honestly, the variable names are kinda bad
let me rewrite it and it might be more clear
fading granite
ok
so in order - if s is the letter, letter is the index of that letter, and new_letter is the shuffled index of that latter. would it be something like a 0 4?
snow swift
encoded = ""
random.seed(2)
new_chars = string.ascii_lowercase
original_chars = list(string.ascii_lowercase)
random.shuffle(original_chars)
for c in s:
encoded += new_chars[original_chars.index(c)]
is the same thing, but with variable names that actually make sense
fading granite
this is a imrpovement to the encode method, correct?
snow swift
yep
fading granite
ok so with a corrected encode method. you said "map each character from a char in letters to a char in newletters"
how would one do that
by map, you mean like associating a index number to said letter
snow swift
ok
so new_chars == "abcdefghijklmnopqrstuvwxyz"
original_chars == list("durpaxehoqtwmsknvzgijflycb")
fading granite
so new would be the normal message while original would be shuffled?
snow swift
so if the 1st character in the input is a "u"
original_chars.index("u") would be 1
new_chars[1] is "b"
so the "u" would be mapped to a "b"
same with "r" mapped to "c"
and "p" to "d"
etc
fading granite
ok so yea original is shuffled
snow swift
yeah
fading granite
so what i need to do is print both encypted and the unshuffled messages?
snow swift
wdym
fading granite
like
i print the whole alphabet, bc thats how i test the encoding part. and i print the shuffled alphabet
or did wires get crossed some where
snow swift
yeah ig
fading granite
question then
does the decode method have to interact with the encode method
like, at all
as in do i have to call a variable from one method to another
uhh im coming up with a error in the new encode method
encoded = ""
random.seed(2)
new_chars = string.ascii_lowercase
original_chars= list(string.ascii_lowercase)
random.shuffle(original_chars)
for c in s:
print (s[c], new_chars.index (s[c]), original_chars.index(s[c]))
encoded += new_chars[original_chars.index(c)]
return encode_text
its saying "TypeError: string indices must be integers" on the print statement
jade ridge
i need a algorithm based on setting a number 0.00 to 1 depending on the state of a number that goes high, and goes low
if it goes lower, set the threshold higher, goes higher, threshold lower
snow swift
@fading granite not s[c]
just c
original code used indexing with range len so I cleaned it up into a normal loop over s
void cliff
hey guys
Make a subclass of np.ndarray that overrides 'fill', 'nonzero', 'reshape', 'tolist', and 'sort'
The overriding functions will change nothing but add a print of what is happening
Write code to test that your overriding has worked
class myArray(np.ndarray): def fill(self): print("fill") def nonzero(self): print("nonzero") def reshape(self): print('reshape') def tolist(self): print("tolist") def sort(self): print("sort")
am i doing it right?
flat sorrel
you need to match the function signature of the original function
otherwise it'll error out when you try to call those functions with parameters
Since the parameters don't really matter you can use *args and **kwargs to make them compatible
void cliff
is it something like
def reshape(self,shape,order='C'): print('Reshaping the array...') super().reshape(shape,order='C')
flat sorrel
if you run super().reshape(shape,order='C') it will actually do the reshaping which is not what you need to do in the task
remove that line and it will be ok
void cliff
i have updated my code
`class myArray(np.ndarray):
def fill(self,value = value):
print("fill")
return np.fill(value)
def nonzero(self,value):
print("nonzero")
return np.nonzero(value)
def reshape(self,shape,order = 'C'):
print('reshape')
return np.reshape()
def tolist(self,array):
print("tolist")
return array.np.tolist()
def sort(self,value ,axis=-1, kind=None, order=None)):
print("sort")
return np.sort()`
you don't have to return anything
void cliff
should this be ok?
flat sorrel
just print and be done with it
void cliff
I'm trying to get nonzero but it doesnt work somehow
import numpy as np class myArray(np.ndarray): def nonzero(self): print("nonzero") super(myArray, self).nonzero()
array = np.array([[3, 8, 0], [7, 0, 2]])
a = array.view(myArray)
print(a)
a.nonzero()
print(a)
and I get this
[[3 8 0]
[7 0 2]]
nonzero
[[3 8 0]
[7 0 2]]
void cliff
it's weird
i looked up on the documents
and it said @snow swift
it should be returning a new array
void cliff
oh so it returns the same result as the original one is fine right?
How to get the new array then?
snow swift
return super().nonzero()
flat sorrel
did you return super().nonzero()?
flat sorrel
what is myArray?
where did you define it
wait it is the class name
please don't use camelCase for classes
Looks like you're not using view correctly
you're missing the dtype argument
void cliff
`import numpy as np
class myArray(np.ndarray):
def fill(self,*args , **kwargs ):
print("fill")
super(myArray, self).fill(*args, **kwargs)
def nonzero(self):
print("nonzero")
super(myArray, self).nonzero()
return super().nonzero()
def reshape(self,shape ,order = 'C'):
print('reshape')
super(myArray, self).shape(shape, order = 'C')
def tolist(self,*args, **kwargs):
print("tolist")
super(myArray, self).tolist(*args, **kwargs)
def sort(self,value ,axis=-1, kind=None, order=None):
print("sort")
super(myArray, self).sort(*args, **kwargs) `
!code
halcyon plankBOT
flat sorrel
Triple backticks
void cliff
class myArray(np.ndarray):
def fill(self,*args , **kwargs ):
print("fill")
super(myArray, self).fill(*args, **kwargs)
def nonzero(self):
print("nonzero")
# super(myArray, self).nonzero()
return super().nonzero()
def reshape(self,shape ,order = 'C'):
print('reshape')
super(myArray, self).shape(shape, order = 'C')
def tolist(self,*args, **kwargs):
print("tolist")
super(myArray, self).tolist(*args, **kwargs)
def sort(self,value ,axis=-1, kind=None, order=None):
print("sort")
super(myArray, self).sort(*args, **kwargs) ```with py after the first triple backticks
but anyways
please don't use camelCase for classes
Looks like you're not using view correctly
you're missing the dtype argument
void cliff
what is camelCase ?
flat sorrel
it is a naming convention
where the words are not separated by a space
the first word is not capitalized
but all other words are
flat sorrel
your class name should use the PascalCase naming convention instead of camelCase (key difference being that the first word is capitalized)
flat sorrel
you just specify the dtype of the array
void cliff
the dtype should be list right
flat sorrel
no
please read your class notes again (I refuse to believe that you haven't learned about dtype by the time you're beginning to subclass ndarray)
void cliff
so dtype = int?
flat sorrel
yup
flat sorrel
no, I mean the dtype parameter in view
severe matrix
I've string my_string = "take 2/3 tablets of first tablet and 4 4/5 of second tablet daily" and I wanted to replace all those fraction values with their decimal representation (0.66 and 4.8). I created the regex st = re.findall(r"(\d+[\/\d. ]*|\d)", my_string). Now, how do I replace all the occurrences of the string with corresponding fraction?
import re
my_string = "take 3 /4 tablets 4 4/5 daily"
st = re.findall(r"(\d+[\/\d. ]*|\d)", my_string)
def check_if_int(s):
try:
int(s)
return True
except ValueError:
return False
#Split the string "a b / c" into ['a','b','c'], this list is 'numbers' and then perform: (a+b/c)
print("st : ", st)
numbers = [a for a in re.split(r'(\s|/)', st[0].strip()) if check_if_int(a)]
print(numbers)
if(len(numbers) == 3):
replace_with = str(int(numbers[0]) + int(numbers[1])/int(numbers[2]))+" "
elif(len(numbers) == 2):
replace_with = str(int(numbers[0])/int(numbers[1]))+" "
elif(len(numbers) == 1):
replace_with = str(int(numbers[0]))+" "
else:
replace_with = " "
print("replace_with : ", replace_with)
st = re.sub(r'(\d+[\/\d. ]*|\d)', replace_with,my_string)
print(st)
# numbers
@void cliff no, it should be
a = array.view(int, MyArray)
int corresponds to dtype and MyArray corresponds to type
void cliff
oh i got it
lone escarp
@severe matrix for regex i think use this link: https://regex101.com/r/uR7rN1/1
and if they match it would return something like this;
'1/2 apples'.match(/^\S+/) #["1/2"]
now just replace the output all these outputs in a list a and then loop for every item in the list and replacce it with its decimal version
severe matrix
@lone escarp is that python code? doesn't work
lone escarp
the link has regex code, then jut follow what i said below, it shld probably work
severe matrix
Thanks for the link. I've found the desired regex but I'm in doubt as to how to use that with re.sub()
@lone escarp
lone escarp
import re
string = "at what time?"
match = re.sub("\s","!!!",string)
print (match)``` like this?This replaces all the whitespace chars with !!! but I've to replace all the fractional values with their corresponding decimal values
lone escarp
hmm, use my way i told up, lemme do some code and figure out with .sub()
severe matrix
ok
lone escarp
lambda function in the replacement part of re.sub
>>> import re
>>> from __future__ import division
>>> s = "7 1/2"
>>> re.sub(r'(\d+)/(\d+)', lambda m: str(int(m.group(1))/int(m.group(2))), s)
'7 0.5'
>>> #If we don't put str() it will error out since it won't be able to replace
>>> #It is more better to use divison from __future__
>>> re.sub(r'(\d+)/(\d+)', lambda m: str(int(m.group(1))/int(m.group(2))), '7 9/2')
'7 4.5'```
This is what `__future__.division` does:
```py
>>> from __future__ import division
>>> 1/2
0.5```
This is what `re.group()` does: https://stackoverflow.com/questions/20202365/the-groups-method-in-regular-expressions-in-python@severe matrix 
severe matrix
previously, I had trouble understanding the re.group() function, now in the SO link that you provided, there "abc" is the strings and the pattern is [abc]+
@lone escarp so should the matched strings be a, b, c, ab, bc, abc?
lone escarp
try it out ๐
lone escarp
https://regex101.com/r/0RDlQU/2 here a regex link showing that @severe matrix
use this online regex tool, it is really nice
solved your query?
severe matrix
should re.match("([abc]+)", "abc").groups() give me all the groups?
a, ab, abc, b, bc, c ?
oh ! There's a difference b/w "([abc]+)" and "([abc])+" ?
@lone escarp No, I still didn't understand the group thing. It says group(i) stands for i'th group, but what is a group?
is it the matched strings or sth else?
lone escarp
hmmm, give me a minute, i will see if ic an find some better explanation
severe matrix
I think anything enclosed within the paranthesis are counted as a group
I saw the first 3 minutes of this vid: https://www.youtube.com/watch?v=c9HbsUSWilw
and it says so.
severe matrix
It says that group() picks up parts of the matching text
I don't think it has anything to do with the searching multiple occurrences
@lone escarp
as in the prev. examples abc was matching text but a was also the matching text..so that's where it picks a also.
lone escarp
currently the group gets the first thing that is the 1 in fractions 1/2 and the group(2) gets the 2
severe matrix
yes because you've enclosed /d+ with paranthesis
lone escarp
that are for capturing the group
severe matrix
If u rmove the paranthesis then u won't have any group
lone escarp
yes
severe matrix
but i wanted to tackle with multiple occurrences
import re
my_string = "take 3 /4 tablets 4 4/5 daily"
st = re.findall(r"(\d+[\/\d. ]*|\d)", my_string)
def check_if_int(s):
try:
int(s)
return True
except ValueError:
return False
#Split the string "a b / c" into ['a','b','c'], this list is 'numbers' and then perform: (a+b/c)
print("st : ", st)
numbers = [a for a in re.split(r'(\s|/)', st[0].strip()) if check_if_int(a)]
print(numbers)
if(len(numbers) == 3):
replace_with = str(int(numbers[0]) + int(numbers[1])/int(numbers[2]))+" "
elif(len(numbers) == 2):
replace_with = str(int(numbers[0])/int(numbers[1]))+" "
elif(len(numbers) == 1):
replace_with = str(int(numbers[0]))+" "
else:
replace_with = " "
print("replace_with : ", replace_with)
st = re.sub(r'(\d+[\/\d. ]*|\d)', replace_with,my_string)
print(st)
# numbers
I had already written code but just need to handle multiple occurrences
lone escarp
!e
import re
from __future__ import division
s = "take 3 /4 tablets 4 4/5 daily"
print(re.sub(r'(\d+)/(\d+)', lambda m: str(int(m.group(1))/int(m.group(2))), s))```You are not allowed to use that command here. Please use the #bot-commands channel instead.
severe matrix
like s = "2/3 and 1/2"
as
s = "0.66 and 0.5"
lone escarp
is this the way u wnat?
severe matrix
yes
now since i want to do something complex with these groups, i can call a function instead of lambda function
@lone escarp
def fun(m):
return str(int(m.group(1))/int(m.group(2)))
import re
from __future__ import division
s = "take 3/4 tablets 4/5 daily"
print(re.sub(r'(\d+)/(\d+)', fun(m), s))
This will give error, how can i pass m to the fun here?
lone escarp
m is not defined
i am not sure how to do that
also i gtg for my exams, sry ๐ฆ
try searching on google
u may get something
severe matrix
ok sure. Thanks for all your efforts !!
severe matrix
@lone escarp
def fun(m):
return str(int(m.group(1))/int(m.group(2)))
import re
from __future__ import division
s = "take 3/4 tablets 4/5 daily"
print(re.sub(r'(\d+)/(\d+)', fun, s))
This worked well !
lone escarp
np ๐, gr8!
unreal rock
Anyone have past competitive programming experience? Pls dm I need help joy
I find easy problems on leetcode hard :/
But I would like to learn to solve them :)
fiery cosmos
whats a data structure?
agile sundial
it holds data in a smart way
fiery cosmos
like compression?
agile sundial
no, like an array or hash table
stable pecan
or deque or graph
lone escarp
Anyone have past competitive programming experience? Pls dm I need help joy
@unreal rock there is a competitve programming discord server ig
i am not sure if i can send the invite here
unreal rock
dm me ig
lone escarp
just search competitive programming on discord explore
here u go ๐
@unreal rock
unreal rock
ty
snow flower
Can sm1 help me wid splay trees i mean teach me how exactly they work
vagrant condor
hey guys im totally new in python. i have a list of words and i want to make a if statement that if there isnt a word in that list .append() that word.
"fname = input("Enter file name: ")
fh = open(fname)
lst = list()
for line in fh:
w = line.split()
w.sort()
for r in w:
print(r)"
fiery cosmos
@vagrant condor i suggest you look into this videohttps://www.youtube.com/watch?v=Uh2ebFW8OYM&t=0s
for me, it's really hard to read a python script that handles files that doesnt use the "with open("file_name", "read(r)/write(w)/ append(a)") as file:"
vagrant condor
thanks man! im in a course for begginers and stated about a month and a half ago. its really frustrating sometimes specially if you are stuck in a code.
fiery cosmos
def binarySearch():
import random
import math
import sys
num = int(input('>>> '))
numrange = list(range(1, num))
number = random.choice(numrange)
print('The number is: ', number)
guesses = round(math.sqrt(num))
print(guesses)
for _ in range(guesses):
guess = round((numrange[0] + numrange[-1]) / 2)
if guess == 0:
guess = 1
if guess > number:
del numrange[guess + 1:-1]
elif guess < number:
del numrange[0:guess - 1]
else:
print('Computer: ', guess)
sys.exit()
Hi I tried to implement a binary search algorithm in a number guessing game. I cannot figure out why this doesn't work.
I get an Index Error
but if I input a low number
then it works
vernal stirrup
can someone explain the folowing line of code it will crate a list with the moving average x being the list and n the number of added values: pd.Series(x).rolling(window=n).mean().iloc[n-1:].values
rocky silo
how can i acsess jsons like this
[{"id":59366,"answer":"kiss","question":"Buss is a synonym for this","value":800,"airdate":"2004-05-20T12:00:00.000Z","created_at":"2014-02-11T23:23:15.201Z","updated_at":"2014-02-11T23:23:15.201Z","category_id":51,"game_id":null,"invalid_count":null,"category":{"id":51,"title":"4-letter words","created_at":"2014-02-11T22:47:25.679Z","updated_at":"2014-02-11T22:47:25.679Z","clues_count":165}}]
agile sundial
if you have deserialized it, then you access like any other python container
fiery cosmos
How can I access a variable in function to another function???
wraith valve
dont think thats possible unless u pass that variable into a parameter of the second function
snow swift
params
@vernal stirrup #data-science-and-ml
also how tf are people still using this channel incorrectly
even after it got renamed
vernal stirrup
Sorry
eager tapir
How can I access a variable in function to another function???
@fiery cosmos use a closure?
agile sundial
@snow swift it's def better now though
gleaming badger
can someone help coding a simple recursion function?
fiery cosmos
just ask your doubt
wicked rock
hey can someone help me find a better heuristic function for a * ??
currently using
def h(p1, p2):
x1, y1 = p1
x2, y2 = p2
return math.sqrt((x1-x2)**2 + (y1-y2)**2)
it works and way better than Manhattan Distance but it is still a bit slow (removing the sqrt makes it faster and more optimal for simple pathfinding but in a maze it just goes around brute forcing in the end taking more time)
fiery cosmos
use a closure?
@eager tapir ุ
raven kite
hi guys, i need some brainstorming
I have a array like this (10,5,25,30) for example
this is my target array
and i have list of arrays like (1,2,3,4) ..... (a,x,y,z). I need to find arrays from this list and sum them to reach target array
And i need to minimize difference between sum
fiery cosmos
Hi
raven kite
for example 11,6,26,31 is better than 20,5,25,30
i implented it with brute force it works
how can iimplent this problem to dynamic programming
raven kite
np bro
fiery cosmos
ah
and You want print or ?
var1 = 1162631
var2 = 2052530
print(str(var1) + " is better than " + str(var2))
output:
1162631 is better than 2052530
nope dude
its kind of np hard problem
if there are 100 list, its complexity is 2^100 with brute force
but maybe i can reduce this complexity with dynamic programming, so im trying to get some help
fiery cosmos
Hi guys , I need help understanding a structure of binary tree for a phone book . Input would be name , address and phone number. Would I be correct in saying that the name would be the parent and address + phone number would be the children ?
quartz oxide
U guys know an l-system ?
fiery cosmos
@fiery cosmos binary tree or binary search tree?
@fiery cosmos binary search tree
yeah so you can create an node object that has the following fields
Node
- name
- address
- phone-number
and you should create a binary search tree as you add more nodes to it
and they property to compare would be name
so would each node consist of name,address,phone-number
yep
and when you add nodes to the search tree you would do name comparision
like you know how dictionary(english) has its words sorted right?
yes i do
yeah in the same way you sort the nodes wrt name
but you know with normal binary tree diagrams , each node has single number . What would a diagram of phone book bst look like ? could you draw an example , just really want to visualize this
example
d
/ \
b f
/ \ / \
a c e g
yes !
just assume letters are names
but what about 2 other inputs (phone number and address)
that makes sense
oh so you dont add the number and address to the binary tree ?
just gimme a min I am taking a test
I will be back
thank you
you can dm if you like ,
but you know with normal binary tree diagrams , each node has single number . What would a diagram of phone book bst look like ? could you draw an example , just really want to visualize this
@fiery cosmos actually for the sake of understanding binary search trees we just include an integer, left and right attributes, but you can have any type of data instead of an integer like a string, character, your own defined type too!
about this use case the data are the following
- name
- address
- phone number
so a number would represent a name ?
Okay you are getting confused. So tell me how did you implement a BST with only integers?
can I dm you ? I can show you some code
yeah ok
hexed spade
@quaint snow
fiery cosmos
hi guys, i need some brainstorming
I have a array like this (10,5,25,30) for example
this is my target array
and i have list of arrays like (1,2,3,4) ..... (a,x,y,z). I need to find arrays from this list and sum them to reach target array
And i need to minimize difference between sum
@raven kite hi so can you explain this a bit, seems hard to understand
raven kite
you have one target array
(10,5,25,30) like i mentioned
and you have a pocket of arrays, you need to choose them
there are 100 array for example, you choose (7,5,20,10),(2,0,5,15)(3,1,5,5)
lone escarp
ok
fiery cosmos
hmm seems like a subset sum problem
fiery cosmos
you implemented the bruteforce 2^n solution right
raven kite
yes
and some greedy thing which give me some good solutions but not best
but how i do it with dynamic
me and my friends thinking about this for days
no one find a good solution
we have some solutions ilke nD array, for example if arrays size is 4 its 4d array
but its complexity is getting bigger than 2^n in long term
im close to give up, so iask here
fiery cosmos
yeah I understand
raven kite
yeah I understand
@fiery cosmos do we have hope?
fiery cosmos
I can't guarantee, I am thinking
I am thinking how can you reduce this to a subproblem
@raven kite is there any kind of test data
raven kite
letme print for you
[1834, 2021, 2002, 1750, 1811, 2031, 2022, 1788, 2414, 1771] this is target list
'[183, 629, 347, 0, 213, 709, 595, 562, 694, 55]'
'[836, 236, 129, 891, 605, 654, 879, 147, 263, 903]'
'[188, 75, 256, 522, 167, 384, 192, 471, 14, 402]'
'[419, 266, 360, 523, 511, 160, 432, 177, 77, 452]'
'[14, 136, 26, 324, 346, 516, 513, 212, 185, 323]'
'[535, 305, 190, 342, 400, 104, 430, 204, 229, 222]'
'[543, 260, 568, 265, 80, 465, 552, 96, 588, 572]'
'[397, 130, 36, 471, 236, 309, 210, 324, 189, 208]'
'[273, 475, 21, 293, 397, 418, 277, 442, 141, 107]'
'[362, 202, 492, 123, 102, 214, 525, 227, 114, 311]'
'[49, 114, 406, 88, 479, 158, 311, 107, 222, 39]'
'[415, 364, 183, 641, 596, 153, 224, 335, 280, 531]'
these are lists that i can choose
@fiery cosmos
vagrant condor
hey i have a question. why its still used .rstrip() and in other line .split() if split removes all the white spaces?
fading granite
hi im having a issue with a shuffle cipher algorithm. do you know anything about that?
fallen mason
if im looping through a list and i wanna check 2 elements at the same time
does it makes a difference if i check the
i and i+1
vs
i-1 and i
my thought was that looking at something I've already looked at would be easier than looking ahead
but I'm not sure if thats how it works
fiery cosmos
what are you checking the 2 elements for ?
fallen mason
im checking if one is greater than the other
fiery cosmos
so if your starting position 0 and you increment or decrement every time , it wouldnt make a differnce
thick surge
result_perms = [[]]
for n in nums:
new_perms = []
for perm in result_perms:
for i in range(len(perm)+1):
new_perms.append(perm[:i] + [n] + perm[i:])
result_perms = new_perms
return result_perms
my_nums = [1,2,3]
print("Original Cofllection: ",my_nums)
print("Collection of distinct numbers:\n",permute(my_nums))```This code is for all possible variants but I can not understand what perm [: i] does? perm is an empty list
wraith valve
lmao i think scipy has literal functions to permute stuff for u
wide prism
so does itertools
arctic veldt
do you have a question about shuttle ciphers, or just a question about who is on this discord server?
fading granite
the shuffle ciphers
i asked earlier but no one responded
and i asked yesterday and i got some answers but stopped for a while then i jsut went to bed
arctic veldt
it looks like your question is about python and may not require knowledge of shuttle ciphers
fading granite
m. well im making a shuffle chiper in python but im having trouble making the deciphering part of it
fleet thorn
does anyone know a fast ray-cube intersection algorithm?
I'm trying to make a real-time raytracer that only has axis-aligned cubes to make things simpler
I've already made one with spheres, but I'm trying to find a very fast implementation with cubes
brave oak
btw I don't really know much about raytracing but I gotta say that sounds really cool
fleet thorn
yea lol, it's really fun when it works, but when it doesn't work it's a serious pain lol
fading granite
but can i get help with the shuffle cipher thing, please?
lone escarp
@fading granite u are using random.shuffle() ?
or u want to do something like this:
import random
alphabet = 'abcdefghijklmnopqrstuvwxyz.,! '
key = 'nu.t!iyvxqfl,bcjrodhkaew spzgm'
plaintext = "Hey, this is really fun!"
def makeKey(alphabet):
alphabet = list(alphabet)
random.shuffle(alphabet)
return ''.join(alphabet)
def encrypt(plaintext, key, alphabet):
keyIndices = [alphabet.index(k.lower()) for k in plaintext]
return ''.join(key[keyIndex] for keyIndex in keyIndices)
def decrypt(cipher, key, alphabet):
keyIndices = [key.index(k) for k in cipher]
return ''.join(alphabet[keyIndex] for keyIndex in keyIndices)
print(plaintext)
print(encrypt(plaintext, key, alphabet))
print(decrypt(cipher, key, alphabet)) ```
raven snow
fading granite
Im using the first option.
fiery cosmos
Hey guys ! Could someone help me with a bst program , I can explain in more details if you can help
agile sundial
please explain
fiery cosmos
Im trying create a program without classes and objects which inserts in a bst . Could I dm you?
agile sundial
no, it's best to keep it here
fiery cosmos
Oh okay , can you help ?
fiery cosmos
So I want to insert and search numbers in a bst , but without using any classes or objects. So I think we should have a list to store the data. Most bst classes and withinn those classes they have init , self.leftChild , self.rightChild (we cant use any these objects)
agile sundial
why can't you use a class?
agile sundial
in python?
fiery cosmos
yes
agile sundial
sure, a list would be a good idea
fiery cosmos
yes it would , but I need help with insertion and searching
cause the first entry would be the root
correct ?
agile sundial
yeah
fiery cosmos
so can you help
agile sundial
send your code
fiery cosmos
ive only dont the list and append numbers , but sure ill send it
agile sundial
well, then try to make them first
fiery cosmos
No but I have a program wrote with using objects and classes , so I need help with removing them
I can send you that part if you like ?
agile sundial
let's solve the algorithms question first
north cosmos
wait is this place to ask about logic for the code?
fiery cosmos
apparently
north cosmos
ohh i see
agile sundial
read the channel topic
fiery cosmos
@agile sundial what would you recommend doing ?
agile sundial
well, i haven't seen any of your code, so i have no idea
fiery cosmos
yeah because you said "let's solve the algorithms question first"
agile sundial
yes, because you have 2 problems, an algorithm question, and that you don't want it object oriented
fiery cosmos
true , but do you have an idea of algorithm that I could use ?
agile sundial
to insert into a binary tree?
agile sundial
add it to one of the leaves
agile sundial
yes
fiery cosmos
so when you say "add it to one of the leaves" am I adding everything to a list first ?
?
agile sundial
essentially, just do binary search until you find a spot for the new value
fiery cosmos
but how do I do a binary search without objects and classes lol
agile sundial
it's just a normal binary search
fiery cosmos
def binarySearch(arr, l, r, x):
while l <= r:
mid = l + (r - l) // 2;
# Check if x is present at mid
if arr[mid] == x:
return mid
# If x is greater, ignore left half
elif arr[mid] < x:
l = mid + 1
# If x is smaller, ignore right half
else:
r = mid - 1
# If we reach here, then the element
# was not present
return -1
# Driver Code
arr = [ 2, 3, 4, 10, 40 ]
x = 10
# Function call
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print ("Element is present at index % d" % result)
else:
print ("Element is not present in array")
something like this ?
agile sundial
sure
fiery cosmos
okay so could you explain the benefit and relation this will have for my bst ?
agile sundial
you'll be able to insert an element
fiery cosmos
and what would you recommend for searching
agile sundial
binary search
agile sundial
what?
fiery cosmos
use the same code for search too ?
agile sundial
sure
fiery cosmos
so the binary search search does the insertion and searching thats cool. I have another thing to add to this , I want put entries with differnt inputs for example (name,address,email) --> ("Tony","123 main street","tony@mail.com") so a tuple . But if want search using name or email , how would I add this ?
agile sundial
compare the element you want instead of the entire tuple
fiery cosmos
What are the best resources for learning DSA in Python?
marsh swallow
I am confused on how I can choose moves with MiniMax and Alpha Beta Pruning
I am fairly certain my implementation of the algorithm is correct, but in terms of a way to actually choose the move I am confused.
This is for a chess AI im making
here is the MiniMax code:
def MiniMax(Board, depth, alpha, beta, isMaximizer):
if depth == 0:
return score(Board, "black")
#Max
if isMaximizer:
maxEval = -math.inf
for x in [x for x in Board.legal_moves]:
BoardCopy = Board.copy()
BoardCopy.push_san(str(x))
Eval = MiniMax(BoardCopy, depth - 1, alpha, beta, False)
BoardCopy.pop()
maxEval = max(maxEval, Eval)
alpha = max(alpha, Eval)
if beta <= alpha:
break
return maxEval
#Min
else:
minEval = math.inf
for x in [x for x in Board.legal_moves]:
BoardCopy = Board.copy()
BoardCopy.push_san(str(x))
Eval = MiniMax(BoardCopy, depth - 1, alpha, beta, True)
BoardCopy.pop()
minEval = min(minEval, Eval)
beta = min(beta, Eval)
if beta <= alpha:
break
return minEval
Since Im just trying to get the algo working I didnt use a very sophisticated function to evaluate a board state (It simply looks at how many pieces you have on the board). Ill add piece values/ square tables after I fix the algorithim
quick tapir
Hey! I'm looking for some way to represent what to do to a variable before testing it against another as an object in a list.
https://repl.it/@HopperAlt/HopperBot#Cogs/Shared/Playlist/playlist.py Pretty much, on line 183, I start doing a few repetetive try/except blocks (and I want more and for it to be more specific) where it's trying almost the exact same thing each time.
I want to somehow represent the self.songs[s]['Authors']+self.songs[s]['Singers'] or [self.songs[s]['Note'],self.songs[s]['URL']]+self.songs[s]['Lyrics'] as objects in a list, where we don't know what s is
I'll then do something along these lines:python hierarchy = [...] success = False for test in hierarchy: if not success: try: song = choice([s for s in self.songs.keys() if song.lower() in test(s)]) success = True except: passPreferably, I'd be able to turn this into a function that returns song or None where I can also accept something else to do to song before returning it such as self.songs[song] or even self.songs[song]["lyrics"] for my other commands that essentially do the same thing but need different information that can also produce an exception (line 111 and 150). This would end me up with something like this:python def testHierarchy(self,song,hierarchy,postTest=None): for test in hierarchy: try: song = choice([s for s in self.songs.keys() if song.lower() in test(s)]) if postTest == None: return song else: return song,postTest(song) except: pass
quick tapir
I managed to get it working! https://repl.it/@HopperAlt/HopperBot#Cogs/Shared/Playlist/playlist.py Line 100
(though it's not very accurate. If anyone has any ideas on how to improve it, please let me know!)
autumn mason
Hello everyone
what is datetime object/class that retruns current datetime?
I know datetime.datetime.now() returns current datetime but it doesn't upgrade meaning it doesnt't give you actual datetime after like one minute or so
Could anyone help with this?
quick tapir
That's not possible afaik
You can't have an variable that always returns something different
You need a function for that
Why don't you just call datetime.datetime.now() every time you need the current datetime?
That's what you're expected to do
autumn mason
let's say in my database I have datetimes and I need to query them when relevant time comes (kind of like in to do apps)
quick tapir
You can't store a constantly-updating variable in a database lol
To-do apps don't store the time for the to-do as the current time, anyways, so I don't see your point?
And if they did, they'd just call the current datetime.datetime.now()
Oh, do you mean to-do notifications? Notifications use listeners which you can imagine as while loops that run in the background
autumn mason
user chooses date and time and it adds to db, after that when that datetime comes I want to compare it to current date so it can send notifications/reminder kinda thing)
quick tapir
Ok- so you'd just do if database.get("datetimeForNotification") <= datetime.datetime.now()?
autumn mason
like lets I have it stored in my system like task_due and task_due == current_datetime
would not it work like that?
I'm new in web dev so sorry for annoying questions))
quick tapir
I don't see what the difference is between datetime.datetime.now() and an 'object that upgrades to give current datetime constantly' or whatever
autumn mason
Thank you @quick tapir for your info) it was helpful)
fiery cosmos
anybody here know haskell ?
abstract thunder
nvm answered elsewhere, thanks
hardy knot
xyz = []
CurDifList = []
print(lolol)
print("X:")
print(len(rowlist))
#print(lolol)
for y in detlist:
CurDifList = []
#getDif(a)
#print(detlist)
#print("Intriuging")
pxa = lolol[0]
pxb = lolol[1]
dxa = y[0]
dxb = y[1]
pya = lolol[2]
pyb = lolol[3]
dya = y[2]
dyb = y[3]
difex = (int(dxa) - int(pxa)) / 2
difey = (int(dya) - int(pya)) / 2
difscore = (difex + difey) / 2
hoc = [abs(int(difscore)), int(dxa), int(dxb), int(dya), int(dyb), int(pxa), int(pxb), int(pya), int(pyb), lolol[8]]
xyz.append(hoc)
#print(xyz)
from operator import itemgetter
sorte = sorted(xyz, key=lambda x: x[0])
CurDifList = []
CurDifList = sorte[0]
#print(sorte[-1])
#print(CurDifList)
#print("Next line Is Calling KalmanUpdate")
NewPreds = KalmanUpdate(CurDifList)
print("Sorte:")
print(sorte)
print("CurDifList")
print(CurDifList)
print("NewPreds:")
print(NewPreds)
#print(NewPreds)
#print("Should Have Printed NewPreds")
Niteration = iteration + 1
sql1 = "INSERT INTO coords (xmin, xmax, ymin, ymax, vel1, vel2, sector, iteration, tag) VALUES (%s, %s, %s, %s, %s, %s, %s, %s, %s)"
val1 = (NewPreds[0], NewPreds[1], NewPreds[2], NewPreds[3], NewPreds[4], NewPreds[5], sector, Niteration, CurDifList[9])
mycursor.execute(sql1, val1)
print("SQL Values:")
print(val1)
mydb.commit()```hey can someone plz explain to me why the values in the val1 are not updating
every time it just commits the exact same sor index's 0,1,2,3,4,5 but when i print val1 it prints the correct updated values
spice ermine
can anyone suggest a good video resource to learn data structures?
marsh swallow
Is anyone here familiar with minimax and alpha beta pruning
fiery cosmos
how do i start making algos?
eager hamlet
http://www.usaco.org/index.php?page=viewproblem2&cpid=433
after sorting the cows, i can calculate whether a segment is valid in O(1), but the minimal complexity to actually find the segment that i can think of is O(n^2), which is too slow
any help? (ping plz)
fiery cosmos
what algo do you want to make?
@oblique panther an encryption algo
oblique panther
@fiery cosmos I dunno. Try #cybersecurity
raw bridge
can someone tell me where can i learn sorting algorithms ?
fiery cosmos
try geeksforgeeks
raw bridge
i see
fleet thorn
Im using the first option.
@fading granite then there's not really an easy way to decode that
fading granite
but there is a way to decode it, right?
the code itself gives a map of the original letters index and the shuffled index
like a is index 0 then shuffled its 4, mking . it replace e
fiery cosmos
I'm making a .txt brain for referencing
wispy sierra
@eager hamlet instead of run 2 for loops, run 1 for loop for the min pos and use binary search to find max position , so now we have O(nlogn)
wispy sierra
After sorting. Let i,j which x[i] and x[j] is the start and end pos. First for loop is to find i, binary search is to find j. As we know the pos is in order (as we sorted already) so instead of run the second for loop, we could use bs to reduce the complexity
fiery cosmos
I think its like this ig
2 2 2 2 2
2 1 1 1 2
2 1 0 1 2
2 1 1 1 2
2 2 2 2 2
I think the corners/diagnals are also close to 0
bronze sail
sounds like snake predator
bronze sail
I think its like this ig
2 2 2 2 2 2 1 1 1 2 2 1 0 1 2 2 1 1 1 2 2 2 2 2 2
@fiery cosmos thanks
it worked
eager hamlet
@wispy sierra what's start and what's end
of the photo?
(sorry for the incessant pinging- i can stop if you want me to)
raw bridge
def bubbleSort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]``` can someone explain this bubble sort to me? i mean i understand the syntax, but i dont understand the logic at all
fossil sluice
Where does the logic fall through for you?
raw bridge
the second for loop
why n-i-1 ?
i think i only need to know this, i understand what its doing next
or maybe not
fiery cosmos
ok bubble sort goes like this lets take an array for example
5, 3, 6, 1, 7, 9, 4
you need to sort this array
so at first you scan the array from left to right checking the adjacent elements
3, 5, 1, 6, 7, 4, 9
@raw bridge did you understand until here?
raw bridge
u can use a condition what to do with the adjacent elements, in that code its checkcing if first_element > next_element, if yes then it swaps
fiery cosmos
def bubbleSort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
do you understand the first for loop?
raw bridge
yes
raw bridge
nope
i think if i get a visualization i will understand
i cant imagine what the second for loop does, because
fiery cosmos
ok lets take my example
raw bridge
sure
fiery cosmos
no I mean the first i loop as a whole
raw bridge
yeah
fiery cosmos
notice how the maximum element of the array has gone to the end
now do the second pass and tell me whats the array
raw bridge
ooh
fiery cosmos
so when doing some ith pass you only need to check until n - i - 1
raw bridge
oh then 6 will come there, then 5, then 3, then 1, wow
fiery cosmos
because its waste to check the other since they have gone to their own place
fiery cosmos
it really doesnt matter it you remove that -1 but it has a meaning according to the array
3, 1, 5, 6, 4, 7, 9
this is the i = 1 pass
so you only check until [0 ... 7 - 1 - 1]
raw bridge
ooohh
raw bridge
-1 because python starts with 0 ๐
fiery cosmos
do you really need to check them?
raw bridge
nope
raw bridge
oohh, alright i understand the second for loop :D
fiery cosmos
you will still get the same answer
raw bridge
ooh
raw bridge
yep
fiery cosmos
thats it
raw bridge
:D
fiery cosmos
you do such passes until you get a sorted array
raw bridge
epic!
fiery cosmos
now how do you know how many passes to do?
raw bridge
so the inbuilt sort() function uses this ??
fiery cosmos
nope this is terrible sorting algorithm
raw bridge
oh lol
fiery cosmos
there are more sorting algorithms which are faster than this
raw bridge
i see
fiery cosmos
but you still need to learn these to understand fundamentals
raw bridge
yeah
fiery cosmos
this is usually taught in universities
fiery cosmos
okay all you know is
after 1 pass the maximum element gets its own place
after 2 pass the 2 max element gets its own place
now after how many pass will the minimum element gets its own place?
raw bridge
do you mean like this algo iterates n number of time s (n = number of elements), even when the list is sorted in middle but the program doesnt know to stop?
fiery cosmos
yeah thats what you do to improve the algorithm a little
maybe the array gets sorted in middle so why do extra work
fiery cosmos
yep but think about worst case like this
5, 4, 3, 2, 1
ooh, full iterations
fiery cosmos
yep thats why you do n times
raw bridge
yah
fiery cosmos
but you can also stop in the middle if the array is sorted
raw bridge
how do we do that?
raw bridge
when it is in ascending order?
or any order, ascending in this case
oh wait, we just need an else
fiery cosmos
how?
raw bridge
def bubbleSort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
else:
break```nope
fiery cosmos
well the j and j+1 don't satisfy but what about others?
fiery cosmos
take this example
1, 3, 2
well no
fiery cosmos
def check(arr):
for i in range(1, len(arr)):
if arr[i] < arr[i - 1]:
return False
return True
ooh
fiery cosmos
you just insert this in each loop
and if it returns true you break out of the algorithm
fiery cosmos
|| these are super easy ones you will find harder ones as you learn ๐||
raw bridge
๐
eager hamlet
http://www.usaco.org/index.php?page=viewproblem2&cpid=433
so uh i can validate photo segments in O(1)
but i can't seem to think of an algo that's less then O(n^2)
halp (someone mentinoed binsearch, but idk how to apply it and ping plz)
fading granite
I have a shuffle cipher program and I am having trouble making the function that decrypts the encrypted message. my exact issue is that I dont know how to undo the encryption that this method does. one thing I noted is that the out put of this method id such that it give the letter, is original alphabetical index, and its shuffled index
I feel like I can use the original vs shuffled index to decrypt it but dont know how
import random
import string
def encode_text (s):
new = ''
random.seed (2)
letters = list(string.ascii_lowercase)
newletters = list(string.ascii_lowercase)
random.shuffle (newletters)
print("\n")
for i in range (len (s)):
print (s[i], letters.index (s[i]), newletters.index(s[i]))
new += letters [newletters.index(s[i])]
return new
@eager hamlet you're basically starting with a binary string and finding the longest substring with an equal number of 0s and 1s, and that has an O(n) solution, so what are you doing on top of that to account for the ability to turn 0s to 1s (but not vice versa)?
fresh fox
not sure if this is the right place to ask for help.
Would anyone be able to help me with the my search implementation (linear search and hash table search ) project.
If you can help me, I can compensate you for your support and time.
Its my homework and I am lost as to how to accomplish it.
-regards
eager hamlet
!rule 5
halcyon plankBOT
eager hamlet
@oblique panther i mean it's really the longest substring where the # of 0's >= the # of 1's
so what are you doing on top of that to account for the ability to turn 0s to 1s (but not vice versa)?
what do you mean by this
oblique panther
@eager hamlet the fact that it's the longest substring where num_0 >= num_1 is slightly different than "longest substring where num_0 == num_1", so I'm wondering if you based your solution on existing solutions to the latter problem and how you changed it
oblique panther
@eager hamlet there's an O(n) solution so let me know if you want to see it.
eager hamlet
oh cool there is?
eager hamlet
yeah ok well i moved on to this problem:
http://www.usaco.org/index.php?page=viewproblem2&cpid=434
(ping if you have any idea on what to do)
oblique panther
@eager hamlet well, the way I found that article was I figured out a formal description of the problem and searched it. But it seems you did a better job formally describing the cow problem than I did.
oblique panther
@eager hamlet aren't they all variations on classic algorithms? I assume the people who participate in these competition just memorize algorithms and apply the ones that work for a situation.
eager hamlet
i mean i guess...
lusty sand
I'm struggling with BST (Linked List) on the deletion method
could I get feedback on this error?
fiery cosmos
BST using linked list?
lusty sand
Correct
fiery cosmos
you mean like BST using linked list nodes?
fiery cosmos
yeah so you constructed a BST from scratch using the insert method right?
lusty sand
everything is done except the two child case deletion part
fiery cosmos
yeah okay lets understand that part using a picture
7
/ \
5 9
/ \ / \
1 6 8 10
this is a subtree of a BST and you want to delete 7
now tell me what leaf value can you place instead of 7 to make it a BST
lusty sand
def delete (self, k):
""" Delete a node with value 'k' if it is in the tree. Raise NotInBST if elt. not in tree. """
deleteThis, found = self.subtree_search(self.root, k)# Find node to be deleted
node_parent = deleteThis.parent
# Cases: (1) element to be deleted is not in the tree, raise exception
if found is False:
raise NotInBST ("element not in BST")
# (2) element has no children, just set it's parent's pointer to None
elif self.num_children(deleteThis) == 0:
if node_parent.left == deleteThis:
node_parent.left == None
else:
node_parent.right == None
# (3) element has one child: reset parent of 'k' to point to child
elif self.num_children(deleteThis) == 1:
if deleteThis.left != None:
child = deleteThis.left
else:
child = deleteThis.right
if node_parent.left == deleteThis:
node_parent.left = child
else:
node_parent.right = child
child.parent = node_parent
# (4) element has two children: harder case
elif self.num_children(deleteThis) == 2:
a, successor = self.find_min(deleteThis.right)
deleteThis.k = a.k
self.delete(successor) ```AttributeError Traceback (most recent call last)
<ipython-input-57-0e2bfc618a5b> in <module>
28 #Delete Specifc Node
29 elif a[0] == "R":
---> 30 BST.delete(int(a[1]))
31
32 #Display BST Inorder
<ipython-input-54-ad4959708bef> in delete(self, k)
174 a, successor = self.find_min(deleteThis.right)
175
--> 176 deleteThis.k = a.k
177
178 self.delete(successor)
AttributeError: 'Node' object has no attribute 'k' ```deleteThis.val = a.val ig
wraith valve
i think u can make a choice if u want to replace with successor or predeccessor
when deleting for the two child case
half quarry
hey guys
noob question here
if i want to subtract from a dict using a list of string
how would i do that
agile sundial
wdym subtract from a dict
oblique panther
@half quarry do you want to delete a key?
fiery cosmos
If writing a get path function to do dijkstra algorithm in python, how should I approach coding it ? because I understand how it works on paper but not sure when coded.
eager hamlet
what've you tried
vagrant condor
!code
halcyon plankBOT
vagrant condor
Hey guys.. im having a little problem by adding my index to a directory
for w in u:
f[w] = f.get(u, 0) + 1
ive got the u that its indexed for a splited line in a text.
now when i want to make a list and the directory.item()
my output its diferent
any ideas??
x = list()
for u,w in sorted(f.items()):
print(u,w)
this is the rest of the code
??
halcyon plankBOT
:incoming_envelope: :ok_hand: applied ban to @swift silo permanently.
vagrant condor
any suggestion about my code? please ๐ซ
wind idol
i think a general help channel would be fine for your question @vagrant condor
mossy gorge
It's so cool to watch it just take care of business
mossy gorge
Perhaps the racism bit?
vagrant condor
ok cool i thought that is here becouse its algos and data structs