If you want, I can try to explain
#algos-and-data-structs
cinder wigeon
quasi oracle
@cinder wigeon Hi, it's better not to provide full solutions to problems, but instead explain the general idea you have in mind or key steps. Especially considering this might be for an assignment
humble plinth
hello pythonistas I have a problem 😩
Can someone explain me this gives two different results !! I cant understand the difference. Context : multiplying two matrix.
a = [[1, 2],
[3, 4],
[5, 6],
[7, 8]]
b = [[1, 2, 3],
[4, 5, 6]]
def multiplyInThisOrderV1(a, b):
result1 = [[0] * len(b[0])] * len(a)
for i in range(len(a)):
for j in range(len(b[0])):
for k in range(len(b)):
result1[i][j] += a[i][k] * b[k][j]
return result1
print(multiplyInThisOrderV1(a,b))
## using v1 function outputs :[[96, 132, 168], [96, 132, 168], [96, 132, 168], [96, 132, 168]] which is false
def multiplyInThisOrderV2(a, b):
result2 = [[0 for x in range(len(b[0]))] for y in range(len(a))]
for i in range(len(a)):
for j in range(len(b[0])):
for k in range(len(b)):
result2[i][j] += a[i][k] * b[k][j]
return result2
print(multiplyInThisOrderV2(a,b))
## using v2 function outputs :[[9, 12, 15], [19, 26, 33], [29, 40, 51], [39, 54, 69]] which is THE CORRECT ANSWER
#Strangly if I do for example:
print (([[0] * 5] * 6) == ([[0 for x in range(5)] for y in range(6)]))
# IT OUTPUTS TRUE WHY???? why not the same result tho??
I cant understand why when using [[0] * len(b[0])] * len(a) the result is different from when using[[0 for x in range(len(b[0]))] for y in range(len(a))] Aren't they the same basically??
stable pecan
!e
a = [[0] * 4] * 4
print(a)
a[0][0] = 1
print(a)
halcyon plankBOT
@stable pecan :white_check_mark: Your eval job has completed with return code 0.
001 | [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
002 | [[1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]
why did assigning one value to a[0][0] get repeated 4 times? @humble plinth
humble plinth
I don't really know, I assumed a[0][0] is going to change only one cell
stable pecan
it's the same list repeated 4 times --- each row points to the exact same list in memory
humble plinth
so the two expressions are not equivalent ??
stable pecan
a = [[0] * 4] * 4
for row in a:
print(id(row))
no, they are not equivalent
the second one creates a new list for each row
and doesn't repeat the same list n times
humble plinth
ah ok i understand its like [pointer1, pointer1, ..., pointer1] versus [ptr1,prt2,ptr3]
stable pecan
that's right
humble plinth
how can I verify this
can I see the pointer? or do I have to try to change a value
stable pecan
you can use id like in the little snippet above
!e
a = [[0] * 4] * 4
for row in a:
print(id(row))
@stable pecan :white_check_mark: Your eval job has completed with return code 0.
001 | 140238452404800
002 | 140238452404800
003 | 140238452404800
004 | 140238452404800
!e
a = [[0] * 4 for _ in range(4)]
for row in a:
print(id(row))
@stable pecan :white_check_mark: Your eval job has completed with return code 0.
001 | 139960543736192
002 | 139960543736128
003 | 139960543736000
004 | 139960543735872
note the id's are all equal in the first example and all different in the second
humble plinth
ok man! Thank you, I'm new to python so I assumed they were equivalent! Now I get it. Thanks
stable pecan
np
cinder wigeon
@quasi oracle bold of you to assume it's even correct 
gaunt forge
fair summit
It's really just #computer-science renamed
glossy gust
help
lofty jewel
How can I use dictionary updates to just add a value if the key name is the same? instead of overwriting it
flat smelt
You can’t have duplicates keys, so the only way it to have teh value as a list
Then append to the list
lofty jewel
ok thanks
oak obsidian
@lofty jewel another option is defaultdict
the values would all be lists and if you wanted to add an item you just can always do d[key].append(val)
and if the key doesnt exist it will create it for you and its value will be an empty list
lean dome
There are libraries that provide a MultiDict, but there isn't a built-in one.
cobalt sedge
@cinder wigeon reli thx for ur help i will try it and try to understand it, thank you
stable pecan
a super-deque: slices can also be rotated:
In [52]: d = deque(range(8))
In [53]: d
Out[53]: deque([0, 1, 2, 3, 4, 5, 6, 7])
In [54]: d[2:5].rotate(-1)
In [55]: d
Out[55]: deque([0, 1, 3, 4, 2, 5, 6, 7])
In [56]: d[2:5].rotate(-1)
In [57]: d
Out[57]: deque([0, 1, 4, 2, 3, 5, 6, 7])
oblique panther
@stable pecan is the rotation constant time?
stable pecan
yes
oblique panther
wow
oblique panther
idk when I'd use that but I like it
stable pecan
i don't know when i'd use it either, but i thought it would be fun to make
oblique panther
well was it?
stable pecan
yes
oblique panther
yay
stable pecan
it's incomplete still, but i think most of the legwork is done
https://gist.github.com/salt-die/8ddec60f8387fdeee5bb570652ea0ca7
It's missing some obvious length checks for pops (len == 1)
but that's the gist
neon nova
Hello , just a small question , suppose a class has different functions , and in one of those functions I define
self.a=5
can I use this variable in some other function of that same class ? ( Because normally a should have local scope inside that function , but what does the self. do ? )
stable pecan
yes you can use the variable in some other method of the class
!e
class Test:
def __init__(self):
self.a = 5
def gimmie_a(self):
return self.a
print(Test().gimmie_a())
I see , thank you !
sand pilot
would Union Find be a search algorithm? Or what else would it be classified as?
oblique panther
@sand pilot I spent a good ten minutes reading about that but I can't come up with a definitive answer. But it was an interesting rabbit hole if nothing else.
sand pilot
haha, thank you for the effort. It is kind of a sorting algorithm, could even be used for pathfinding I think? And also searching.
oblique panther
I guess it's a search algorithm in the same way that binary search is for sorted lists
but it's not traversing a directed data structure like a graph or tree.
(I mean I guess you can also traverse an undirected graph)
neat igloo
there man asked to muddle it up, I have everything
oblique panther
@neat igloo what are you referring to?
tepid bear
correct channel for a question about time complexity?
cinder wigeon
ye
oblique panther
@tepid bear yeye
tepid bear
import random
a = [[1, 1, 1], [2, 2, 2], [3, 3, 3]]
x = [1, 2, 3, 4]
for i in a:
for j in i:
if random.randint(1, 3) == 2:
print("hi")
else:
for k in x:
print("hi")
just some example code.
So the time complexity of the first both loops would be O(n²) i think. but do i also have to consider the loop in the else statement?
wild needle
Hi guys, anyone familiar with minimax algorithm? I am trying to complete a tick-tack-toe project on Hyperskill and I am just don't know where to start. JetBrains refers to an article explaining the algorithm in JS. I tried to rewrite it to Python, but I think I am just getting distracted by the different syntax too much.
oblique panther
@tepid bear in this case, the fact that a is a list of lists doesn't matter
if a were guaranteed to be square (so you have to add an element to each sub-list every time you add a new list, and vice versa), I guess it would be quadratic time for the length of each sub-list
import random
a = [[1, 1, 1], [2, 2, 2], [3, 3, 3]] # a := 3; b := 3
x = [1, 2, 3, 4] # x := 4
for i in a: # O(a)
for j in i: # O(b)
if random.randint(1, 3) == 2: # O(1)
print("hi") # O(1)
else:
for k in x: # O(x)
print("hi") # O(1)
There's no guarantee that the lengths of a, x, or sublists of a have anything to do with each other
oblique panther
@tepid bear I believe so. In my ADS education, the only type of algorithm we looked at with more than one variable is graph traversal, so nodes and edges. but I believe you take the dominant term for every variable.
that's assuming of course that a and x change. because if they're constants, then this algorithm is constant time.
even if it has loops.
@wild needle what did you write as far as Python code?
tepid bear
Tech with Tim made a tutorial on minimax for checkers maybe you can adapt than on tick tack toe
eager hamlet
so, i followed this algo to deduce whether a given node is an anecstor of another: https://www.geeksforgeeks.org/query-ancestor-descendant-relationship-tree/
is there a solution for this w.o recursion? bc the problem i need has a tree of depth of maximum 10^5
(ping 2 reply thx)
wide prism
@eager hamlet you can do a dfs while keeping an explicit stack of nodes to process instead of recursing. it's pretty easy to find discussion of this by googling eg "depth first search stack" (looks like there's even some discussion and pseudocode for it on the wikipedia page for dfs)
eager hamlet
yeah
but how am i sposed to implement the in_time and out_time for ancestor calculation
(still ping plz)
wide prism
i think the following should work: when you visit a node n for the first time, record its in-time and push its children onto the stack. eventually you'll process all of n's descendants (if there are any) and have popped them off the stack and will see n again (you can see it's been visited once already since it has an in-time recorded). now record its out-time and pop it off the stack @eager hamlet
fiery cosmos
I'm new to python and i need some help. How do i let my python project paste something to a website for example pastebin and let it save and send the link back of a password and username for example
oblique panther
@fiery cosmos take a look at #❓｜how-to-get-help to learn how to use a help channel. I think Selenium is the package for interacting with browsers but I would not write a program that deals with password storage.
wide prism
looks like there's a pastebin api which will let you programmatically create pastes
fiery cosmos
numberofLines = int(input("Number of inputs: "))
my_list = []
for x in range(numberofLines):
word = input("Word: ")
wordLength = len(word)
word1 = wordLength - 2
word1 = str(word1)
if wordLength >= 10:
firstChar = word[0]
lastChar = word[wordLength - 1]
my_list.append(firstChar + word1 + lastChar)
else:
my_list.append(word)
for a in range(len(my_list)):
print(my_list[a].strip())
output keeps on putting extra line?
eager hamlet
numberofLines = int(input("Number of inputs: "))
my_list = []
for x in range(numberofLines):
word = input("Word: ")
wordLength = len(word)
word1 = wordLength - 2
word1 = str(word1)
if wordLength >= 10:
firstChar = word[0]
lastChar = word[wordLength - 1]
my_list.append(firstChar + word1 + lastChar)
else:
my_list.append(word)
for a in range(len(my_list)):
print(my_list[a].strip())``` ftfy@fiery cosmos print(my_list[a].strip(), end=' ') instead of print(mylist[a].strip()) (by default print() appends a newline)
fiery cosmos
Hey I needed Help in Ternary Tree
eager hamlet
dude epic
rugged saffron
Hello everyone, so I'm doing a little profiling here using map vs list-comprehension (python 2.7). I was expecting map to be the faster, but instead list-comp is 0.01s fast than map. Is there a reason for that, or list-comp will always be faster?
*obs: orientations is a list size 5520
start = timeit.default_timer()
temp1 = map(tf.euler_from_quaternion, orientations)
stop = timeit.default_timer()
print('Time map op: {}'.format(stop - start))
start = timeit.default_timer()
temp2 = [tf.euler_from_quaternion(orientation) for orientation in orientations]
stop = timeit.default_timer()
print('Time list-comp op: {}'.format(stop - start))
Time map op: 0.1549680233
Time list-comp op: 0.140767812729
willow pawn
@rugged saffron There's a tiny bit of overhead with the function lookup when calling map
rugged saffron
@rugged saffron There's a tiny bit of overhead with the function lookup when calling
map
@willow pawn with python 3 would I have the same behavior? Just asking because here (https://stackoverflow.com/a/1247490) apparently map is the one a tiny bit faster
willow pawn
That answer seems a bit incomplete
The reason why map is faster is because it just builds the map object, it doesn't actually iterate over the items and map things.
!e
from timeit import timeit
print(timeit("map(hex, xs)", "xs = range(10)"))
print(timeit("[hex(x) for x in xs]", "xs = range(10)"))
print(timeit("(hex(x) for x in xs)", "xs = range(10)"))
@willow pawn :white_check_mark: Your eval job has completed with return code 0.
001 | 0.42576682940125465
002 | 2.1761272000148892
003 | 0.8017486501485109
@rugged saffron 
rugged saffron
@rugged saffron
@willow pawn Now I got what is happening thanks! Map does not return a map object at python 2.7, so for those three cases you evaluated my output is:
from timeit import timeit
print(timeit("map(hex, xs)", "xs = range(10)"))
print(timeit("[hex(x) for x in xs]", "xs = range(10)"))
print(timeit("(hex(x) for x in xs)", "xs = range(10)"))
001 | 1.00396800041
002 | 1.37580513954
003 | 0.404442071915
still weird this time difference, list-comp is ~0.3 slower for this case
anyway you gave me some insights, I wasn't aware that by using tuple it would be even faster.
sudden rover
guys i need help with comparing the checksum of a downloaded file with its actual checksum
i know how to calculate the checksum of the actual downlaoded fie
i just dont know how to access the correct checksum to compare that to
austere sparrow
@rugged saffron that's because in order to evaluate hex(x) it has to look up the hex name in the global scope every time.
And yes, (hex(x) for x in xs) is equivalent to map(hex, xs), i.e. it's lazy
rugged saffron
@rugged saffron that's because in order to evaluate
hex(x)it has to look up thehexname in the global scope every time.
@austere sparrow makes sense, but and for my first example?tf.euler_from_quaternion(orientation)is also a global name (tf is a third party module), and list comprehension is a bit faster.
fiery cosmos
I'm trying to do codewars, and have a question about list slicing
can i ask or is that stuff not allowed?
like so I don't spoil it
oblique panther
@fiery cosmos you can ask
fiery cosmos
ok
i finished that one
now I'm actually stuck on another one
MORSE_CODE_DICT = { 'A':'.-', 'B':'-...',
'C':'-.-.', 'D':'-..', 'E':'.',
'F':'..-.', 'G':'--.', 'H':'....',
'I':'..', 'J':'.---', 'K':'-.-',
'L':'.-..', 'M':'--', 'N':'-.',
'O':'---', 'P':'.--.', 'Q':'--.-',
'R':'.-.', 'S':'...', 'T':'-',
'U':'..-', 'V':'...-', 'W':'.--',
'X':'-..-', 'Y':'-.--', 'Z':'--..',
'1':'.----', '2':'..---', '3':'...--',
'4':'....-', '5':'.....', '6':'-....',
'7':'--...', '8':'---..', '9':'----.',
'0':'-----', ', ':'--..--', '.':'.-.-.-',
'?':'..--..', '/':'-..-.', '-':'-....-',
'(':'-.--.', ')':'-.--.-'}
def decodeMorse(morse_code):
decodedMessage = ""
for i in morse_code.split(" "):
if i == "":
decodedMessage += " "
continue
decodedMessage += list(MORSE_CODE_DICT.keys())[list(MORSE_CODE_DICT.values()).index(i)]
return decodedMessage
print(decodeMorse(".... . -.-- .--- ..- -.. ."))```
here is my code. the i=="" part is the failure, but without it there are no spaces.i need to decode morse code into a readable string
stable pecan
this might look nicer if you make a reversed lookup dictionary
REVERSE_LOOKUP = {value: key for key, value in MORSE_CODE_DICT.items()}
what does that do?
gimme a second to break it down
wait
oh ok that makes sense
alright
now how do I handle spaces?
stable pecan
have you ever seen the .get method of a dictionary
fiery cosmos
dict.get(key) right?
stable pecan
that's right, but you can give it another argument --- the 2nd argument is a default value to return if the key isn't in the dictionary
{'a': 1, 'b': 2}.get('c', 3) # 3
so we could do:
REVERSE_LOOKUP.get(i, ' ')
that returns "HEY JUDE" with two spaces for me
it's a problem with the split right?
stable pecan
I think so
fiery cosmos
MORSE_CODE_DICT = { 'A':'.-', 'B':'-...',
'C':'-.-.', 'D':'-..', 'E':'.',
'F':'..-.', 'G':'--.', 'H':'....',
'I':'..', 'J':'.---', 'K':'-.-',
'L':'.-..', 'M':'--', 'N':'-.',
'O':'---', 'P':'.--.', 'Q':'--.-',
'R':'.-.', 'S':'...', 'T':'-',
'U':'..-', 'V':'...-', 'W':'.--',
'X':'-..-', 'Y':'-.--', 'Z':'--..',
'1':'.----', '2':'..---', '3':'...--',
'4':'....-', '5':'.....', '6':'-....',
'7':'--...', '8':'---..', '9':'----.',
'0':'-----', ', ':'--..--', '.':'.-.-.-',
'?':'..--..', '/':'-..-.', '-':'-....-',
'(':'-.--.', ')':'-.--.-'}
REVERSE_LOOKUP = {value: key for key, value in MORSE_CODE_DICT.items()}
def decodeMorse(morse_code):
decodedMessage = ""
for i in morse_code.split(" "):
decodedMessage += REVERSE_LOOKUP.get(i, " ")
return decodedMessage.replace(" ", " ")
print(decodeMorse(".... . -.-- .--- ..- -.. ."))```it works
thank you so much, that had me scratching my head
stable pecan
you could also split on " " (two spaces) and then on one space --- this would require two for-loops
fiery cosmos
true
stable pecan
you ever seen .join method?
fiery cosmos
yes
stable pecan
join can simplify your function
fiery cosmos
delimiter.join(list)
stable pecan
...: REVERSE_LOOKUP = {v: k for k, v in MORSE_CODE_DICT.items()}
...:
...: def decodeMorse(morse_code):
...: return ' '.join(''.join(REVERSE_LOOKUP[word] for word in words.split(" ")) for words in morse_code.split(" "))
...: print(decodeMorse(".... . -.-- .--- ..- -.. ."))
HEY JUDE
damn
fair summit
that's significantly worse than the solution using get imo
stable pecan
well, the get solution is technically incorrect unfortunately
since multiple spaces will appear in the answer --- they use three spaces to signify an actual space --- so we should split words first with three spaces
but my variable names are misleading
...: def decodeMorse(morse_code):
...: words = morse_code.split(" ")
...: return ' '.join(''.join(REVERSE_LOOKUP[letter] for letter in word.split(" ")) for word in words)
...: print(decodeMorse(".... . -.-- .--- ..- -.. ."))
HEY JUDE
this is clearer
fiery cosmos
yep
alright now I just need to modify it to not add spaces between all the letters
is there a way i can step through the list by indexes of 3?
because it fails when I give it words without spaces
fair summit
using range and slices, yes, but if the actual words delimiters are always 3 spaces, you're better off splitting on 3 spaces initially
fiery cosmos
morse code words are always 3 characters
so that means that
i can use list[offset:offset+3]
stable pecan
what do you mean they are always 3 characters
fiery cosmos
morse code letters
oh wait it isn't
so the join method fails with a keyerror when you give it this: "...---..."
so I expanded the loop into this
def decodeMorse(morse_code):
solution = ""
for words in morse_code.split(" "):
for word in words.split(" "):
for i in range(3):
solution += ' '.join(''.join(REVERSE_LOOKUP[word]))
return solution```all the solution stuff is just a test
stable pecan
...---... should fail shouldn't it?
fiery cosmos
File "attempt4.py", line 24, in decodeMorse
solution += ' '.join(''.join(REVERSE_LOOKUP[word]))
KeyError: '...---...'```your dictionary doesn't contain it
stable pecan
i don't see ...---... anywhere in the morse code dict
fiery cosmos
yeah it isn't there
they want it to return "sos"
that just got a lot more complicated
stable pecan
should be spaces between the dots and dashes
fiery cosmos
this is their test function for it: py testAndPrint(decodeMorse('...---...'), 'SOS')
fiery cosmos
yep
I think it was a sucsess though
I did learn a lot about this
that reverse lookup table sounds super useful
so thank you for your time
stable pecan
np
quasi oracle
Note that it only works properly for a bijection, since a dict can't have two identical keys
fiery cosmos
true
i was thinking about that
>>> var = {"foo": "bar", "far": "bar"}
>>> REVERSE_LOOKUP = {v: k for k, v in var.items()}
>>> REVERSE_LOOKUP
{'bar': 'far'}
>>>
so it just merges them and takes the last one?
quasi oracle
Just takes the last one
fiery cosmos
ah ok
quasi oracle
It updates the key with the last value
fair summit
replace py for theta in self.thetas:with for j, _ in enumerate(self.thetas) and every instance of theta with self.thetas[j]
wait i edited the wrong block lmao
there
when you use a for loop like that, the origin of theta is lost completely
the python interpreter no longer knows it comes from the nth element in self.thetas
you have to use an index for that
zenith walrus
yo i need help
for poll in all_polls:
if str(poll[1]) != "Michigan":
print("Removed")
all_polls.remove(poll)```
I've got this
it is printing removed
but the stuff isn't actually getting removed(all polls is a list of lists btw)
fiery cosmos
@zenith walrus just use following in last line
del poll
tawny pine
@zenith walrus I'd rather not modify a list while iterating it 🙂 Perhaps, you can use a list comprehension instead?
filtered_polls = [
poll
for poll in all_polls
if poll[1] != 'Michigan']
wheat plover
looking for some good tutorial on back tracking problems
little shard
is python better to learn DS and Algos or Java?
quasi oracle
Both are okay, both have their pluses and minuses. I'd use whatever you're already used to
oblique panther
@little shard I think it's better to learn them in Python because Java's syntax doesn't lend quite as well to thinking about the problem conceptually, and that's really the point of learning algos and data structs
however if you plan to submit solutions for competitions, Python solutions might not be fast enough.
but algos and data structs are language-agnostic so if you feel more comfortable with Java then that's fine.
little shard
Thank you! @oblique panther ! I'm pretty much confused ! All software engineer interviews need DS and Algos! So I asked few friends of mine everybody are like don't learn DS or Algos in python .. go with C++ or java ! So I'm confused😂.
I leanred java already and I'm pretty comfortable with java but with c++ I have to start it from scratch
oblique panther
@little shard Java and especially C++ require more awareness of how the computer does the work of the algorithm, but that doesn't mean that you'll understand the algorithm better if you implement them that way.
did they say why they wanted you to implement them in either of those?
if you're working on an algorithm where the space complexity is an important part of the spec (like a linked list), I guess having to manually delete nodes might be a useful learning tool.
in Python (and in Java for that matter), you'd just have to know that nodes are getting garbage collected when they're no longer in use.
little shard
Ohh!
Interview was like use xyz storing technique on this array! And stuff I guess these are normal interview questions!
oblique panther
xyz sorting technique?
jovial orchid
hey
can someone help with this
i have the code for how to find what the profit is
but how would i find the index?
oblique panther
@jovial orchid what is prices?
can you show me an example of it?
oh
if it's what's shown then it wouldn't work
if you want to iterate over a list, and also get the indices of each element, you use enumerate
!enumerate
halcyon plankBOT
oblique panther
so given a list of integers, is the goal to figure out which index has the integer with the highest value?
jovial orchid
here
i'll show you @oblique panther
that was the first question
(ignore the code)
and now this is the follow up
so basically we're trying to find the index of where we bought and where we sold
@oblique panther
oblique panther
@jovial orchid what do you mean "where we sold"?
is that different from where you bought?
jovial orchid
yes
so basically
the function before part 2 was you buy at a value in the list, specifically the lowest, and you sell at the highest price
each index is its own day
so you buy at a index, and you sell at another index after
you cant do before because then that would be going a day before
so the point is to find the max profit
of a buying index and selling index
so i found the max profit
but now i need to find of where the index
is
where i buy and sell
for max profit
oblique panther
I'm not following with the stock example but can you explain mathematically why you would pick two given elements?
is it the two elements whose values are furthest apart, but where the largest value is first?
jovial orchid
Here i'll give an example
lets say you had
(40,30,500,20,60,700)
what you would want to do here is
you want to buy at 20
and sell at 700
because 20 is the lowest number
and 700 is the highest
actually
bad example
let me give antoher
another*
(40,60,20,500,10,400)
here, you would want to buy at 10 and sell at 400
not 500 because you cant
oblique panther
so you want to pick the two elements that are furthest apart, but where the smaller element is first.
jovial orchid
actually wait im def explaining this wrong im sorry
im bad at that but lemme try again
so
you want to pick two elements
right
oblique panther
and when I say the two elements that are furthest apart
I mean in terms of their value, not their position in the tuple
jovial orchid
two elements that have the biggest difference
but you cant go back in an index and sell for that because that day has passed
and for sure take your time
oblique panther
so the easiest case is if the smallest number in the tuple occurs before the largest one
jovial orchid
i guess yea
that would be ideal
but its not like that in the test cases
Some of the bigger numbers are before smallest
oblique panther
I think I got it
jovial orchid
aight lmk because im struggling
oblique panther
@jovial orchid in what context were you asked to solve this?
like if it's for a class, what is the name of the class?
jovial orchid
Its a intro to cs class
oblique panther
ah
oblique panther
well, I can give you a hint
jovial orchid
sure
oblique panther
so the easiest way to do it would be to get the difference between every pair of numbers in the tuple
jovial orchid
yah
i did that
but im just not sure
how to find the index
of where that was
like my code finds the difference and the max difference
oblique panther
well, that's what you'd use enumerate for
oblique panther
!e
for i, element in enumerate(['a', 'b', 'c']):
print(i, element)
@oblique panther :white_check_mark: Your eval job has completed with return code 0.
001 | 0 a
002 | 1 b
003 | 2 c
it iterates over a list while also giving you the index of each item
it works the same way for tuples though.
jovial orchid
uh
oblique panther
(as an aside, the fact that your instructor is using tuples for this instead of lists is very strange.)
oblique panther
an element is a thing in a list
and an index is the position of an element
sometimes people use them interchangeably but that can quickly lead to miscommunication, especially for a problem like this.
fiery cosmos
hey guys
ive got a python project to complete regarding pyplot. does anyone have any ides?
also, does someone know how to plot a trigonometric graph
oblique panther
@fiery cosmos matplotlib is the most widely used library for plotting. People who know about that are more likely to hang out at #data-science-and-ml
Actually maybe pyplot is widely used. Idk.
You'll probably want to give more detail about what you need to do and what you've tried so far.
desert cedar
pyplot is part of matplotlib
alpine kite
Making an acronym maker for class, unsure of how to join the capitalized letters in one line instead of having them spread across multiple
its not part of the grade but it bugs me because it looks weird
wrong chat i think
mb
brave oak
pyplot is part of matplotlib
@desert cedar think they meant plotly...?
pearl dust
Hey guys I am making a sudoku puzzle generator, I am using a backtracking algorithm to fill in the board with random values at each sudoku square and going through the row by row, I read to make a difficulty score
"We compute a branch-difficulty score by summing (Bi - 1)2 at each node, where Bi are the branch factors. A solution which requires no backtracking at all would thus have a branch-difficulty score of 0.
The final score is given by:
S = B * 100 + E
Where B is the branch-difficulty score and E is the number of empty cells. E is included to bias the puzzle generator in the direction of fewer clues, given multiple puzzles with the same branch-difficulty."
How can I implement this, or how can I find how many branch nodes there are
brazen ore
Anyone wanna help me out with this? https://www.codewars.com/kata/54d4c8b08776e4ad92000835/train/python
fiery cosmos
@brazen ore I can help you
brazen ore
It's alright. It's too much for me lol
fiery cosmos
it shouldn't be too hard if you know a little math...
brazen ore
I do
fiery cosmos
first, observe that you only have to loop up to sqrt(n)
brazen ore
I used math.log() lol. I haven't thought about sqrt(n)
fiery cosmos
from 2 to sqrt(n) that is
brazen ore
I still struggled with the basic like return for None, so I think I'm not ready
fiery cosmos
then for each number in the loop compute x = ceil(log(n) / log(i)) and check if i**x equal n
if they match, return [i, x]
if the loop ends, return None
does that make sense?
brazen ore
Yeah. Well, I will return to this challenge at another time.
fiery cosmos
@brazen ore ```
from math import ceil, log, sqrt
def isPP(n):
for i in range(2, ceil(sqrt(n)) + 1):
j = ceil(log(n) / log(i))
if i ** j == n:
return [i, j]
return None
Hey @fiery cosmos!
cobalt sedge
I got a question about algorithm and probability
Consider modifying the Partition procedure of Quicksort by randomly picking three elements from array A and use the median of the three elements as the pivot. What is the exact probability (not asymptotic form) of getting a split with the sizes of both subarrays are at least |A|/4? You can assume |A| is divisible by 4. Note that, in this question, the pivot element does not count as an element in any one of the two subarrays after the partition. Your answer cannot contain summation and product
notations, but nck, n^k and n! are allowed in your answer.
Anyone can help me solve this? actually I'm not quite understand the problem as well....
signal rampart
I barely passed my data structures and algorithms exam 😦
oblique panther
@signal rampart the worst case is that you'd have to retake the class and that wouldn't necessarily be the worst thing you'd ever experience
What algorithms were on the exam?
signal rampart
I don't even remember its been a year or so
but greedy, divide and conquer, hashing, np-completeness were some of them i guess
vernal venture
@cobalt sedge what part are you stuck on / specific?
Usually in quicksort the pivot is just chosen at a single location , but the suped up versions introduce randomized choosing of the pivot location , which reduces the chances of the algo hitting its O( n^2) worst case.
It’s saying that instead of default choosing a elem at a certain location as pivot, get the median of 3 random numbers in the array, use that as a pivot. It’s asking what’s the probability of getting certain length sub arrays. It’s making the point that different heuristics reduces worst case chance, as mention.
Gotta understand regular quicksort https://youtu.be/Hoixgm4-P4M
The median value is the value that has half the there compare as smaller and half the values compare as bigger. If you took the median for the entire array it would almost guantetee that the size of left and size or right are the same. But I’m this case, just pick 3 to get median.
cobalt sedge
I am thinking like if the Array has 8 elements, which can be divided by 4, then if I pick three numbers and choose their median, then use the median as pivot. How could the sub array still be divided by 4
vernal venture
8 elem, you get a pivot , put it in its right place . Probability of each partition being at least 1/4 of 8 = 2 size.
Aka - given a 8 elem array, and a pivot picked by calculating the median of 3 of those elem, what’s probability that left and right partition >= 2 size
cobalt sedge
Sorry for my fking mind, but I dont understand what means by at least 1/4 of 8 = 2 size
vernal venture
Kk, it says size of subarrays are at least A/4. If A=8, then A/4 = 2 size. ( same thing as saying 1/4 of 8 , a quarter or a 8 piece pie is 2 pieces ) . At least is >= . So -> probability that the partition arrays are >= size 2.
frail valve
not sure how to compose question - so here goes , i have 128k x 8 SRAM external to a microcontroller , im looking for ideas how to structure data to create variables and arrays
cobalt sedge
ummm i know u are trying so hard to help me, but whenever something related to math and calculation, my brain stuck..... if you dont mind, can u illustrate it with some examples...
oblique panther
@frail valve try asking at #microcontrollers
frail valve
i will -- but im looking at how to structure it mathematically in a 128k x 8 bit space
its a data structure - math problem
brisk mango
Hi everyone, I have a small homework task that requires me to find the best number of partitions with the best area possible in a fixed box size, I am supposed to use a genetic algorithm but I am really confused on how to properly implement a good fitness function, setup mutations and populations. We are given a minimum area for each width and height of the partitions as well
I'm not expecting any code, but a good walkthrough on a fitness function would br helpful, or atleast a push in the right direction :)
oblique panther
@jovial orchid I found a solution
I'm not sure that I fully understand it but if you've submitted your assignment, we can talk about it
jovial orchid
yes i have submitted @oblique panther
sudden ember
Is there anyone here that can look at my code and help me a bit? I've run into two major problems with my arithmetic code that me, and a partner of mine were working on, and were stumped. Essentially I can't find a way to define refOp in the code, (anywhere above def evaluate can't be changed for the assignment) and I'm trying to make digit += expression[i], but I don't really know if making digit = '0' is going to help in any way.
halcyon plankBOT
Hey @sudden ember!
sudden ember
flat sorrel
I think refOp refers the operator in the current iteration, so you should define it inside the loop
sudden ember
Idk if that's the case because it's saying it isn't defined when I try it
flat sorrel
You're meant to call repeatOps in the while loop?
I think the logic in each iteration would be to accumulate operations in the stack, then call repeatOps when an operator of higher precedence of refOp is found
placid sonnet
35 years of free software guys
sudden ember
I think the logic in each iteration would be to accumulate operations in the stack, then call
repeatOpswhen an operator of higher precedence ofrefOpis found
@flat sorrel okay now I understand. Thanks
flat sorrel
np
halcyon plankBOT
You are not allowed to use that command here. Please use the #bot-commands channel instead.
lime geyser
Hello, I have this error trying to use pickle module
ImportError: cannot import name 'itemgetter' from 'operator'
Could you help me to fix that?
mint jewel
Do you have a file called operator.py
exotic kiln
how can I write dataclass objects to file?
thin helm
Hello, I need some guidance on best approach to tackle a problem, I have a list of values ( id, body) that I have to order.
To order them, I need to get the previous ID, so with that I can compute the ID = hash(ID (n-1) + body ) and link them.
My obvious initial process is to create a set of different combinations match the ID with previous ID, but on long lists that will be very very inefficient, can anyone give me some pointers on a better algorithm approach ?
vocal gorge
So what you mean is that you need to order them by ID, except the ID of each element depends on the ID of the previous one?
So you'll need to take the first elements, calculate the IDs of all other elements if they are the second one, take the one with the smallest one, and so on?
thin helm
yes, at least that's my first approach, I was considering how could I implement it in a more efficient way
vocal gorge
Not sure there is one, it's a hash after all
so I'm not sure it's possible to reach below O(n^2) complexity
thin helm
yeah that's what I'm assuming too now, was wondering if they're could be something more efficient, but given I have to compute the values before not seeing anything atm, will go with this approach ...
oblique panther
@exotic kiln you can use pickle to save (pickle) certain objects to file, though you want to be cautious about unpickling objects that you didn't create because there's nothing to stop you from unpickling objects with malicious functionality.
if you have more questions about that, I'd open an individual help channel or read the pickle docs
!doc pickle
halcyon plankBOT
cinder wigeon
You can also use JSON, but that takes some work, unless it's like a plain dict
patent dock
Hi, which sorting algorithm does python use under the hood when we do list_name.sort()?
main plank
@patent dock https://en.wikipedia.org/wiki/Timsort i think
patent dock
Oh thanks
patent apex
I was wondering why I am getting this error, can anyone explain what is the use of the first argument in arrays
low palm
Did you check the docs? The table at the top lists the valid args. They define the data type for the elements in the array: https://docs.python.org/3/library/array.html @patent apex
patent apex
ohhhhhhhhhhhhhhhhhhhh
loud lagoon
import pandas as pd
import numpy as np
df = pd.read_csv('BankNote_Authentication.csv')
print(df.head())```i want to print result , but it says Process finished with exit code 0 in pycharm
humble lance
Try pasing the location where file is stored along with the filename
loud lagoon
done man thankss 🙂
humble lance
😀🤙
indigo helm
Hi
So, I'm trying on making a mobile social media app for my project
I can display data from database, which is Posts, but when I'm trying to comment on a Posts, I really don't have an idea how to fetch the Posts' id to sync the comment_id and post_id when making a comment on a post
Please help friends
for i in posts:
# ''' SELECT id FROM Data WHERE id = (?)''', a
a = i[0]
print(a)
# ''' SELECT content FROM Data WHERE id = (?)''', a
b = i[1]
print(b)
print(a + ' ' + b) # printing raw data of db
def commenting():
content = []
grab_post_id = []
comment = content + grab_post_id
# '''INSERT INTO Comments (comment_id, content) VALUE (?, ?)''', (grab_post_id, content)
``` let's say the code goes like this... I'm just dont know how to fetch the post_id so when someone comments, the comment button will trigger and fetch the post id to sync post and comment@indigo helm it looks like this might be a #databases or #web-development question
indigo helm
I'll try switching there, thanks!
fiery cosmos
Hi is it possible to gel helped please with one of my codes?
daring salmon
Is anyone able to help me with a discrete math problem
🙂 idk where to ask
I will be in a VC
I am just looking to work with someone through this
not expecting to be given the answer
I'm having confusions
been staring at it for about 30 minutes stuck
cloud meadow
what level is this? @daring salmon
daring salmon
discrete math I believe
cloud meadow
oh ok
ill try to solve this
@daring salmon have you tried posting this on reddit or other forums?
minor leaf
what does discrete maths mean?
daring salmon
Mhm I'm looking to understand the problem. I've posted it on chegg and Course hero,
cloud meadow
yh we are from the uk
minor leaf
yep
daring salmon
not sure what the other optiuon would be. its in the realm of pure math i believe
cloud meadow
same
cloud meadow
good luck
minor leaf
np
vocal gorge
@daring salmon https://discord.com/invite/BacbVax in discrete math would also be a good place.
stone sun
so im a beginner programmer and im kinda new to things
how would i write a program that would print out all the whole numbers whose squares are less than a number entered by the user
fresh zenith
@daring salmon R_n is the number of right turns and A_n is the number of left turns
split garden
I'm trying to implement a 2-d copy-paste in numpy,
Where I can take a base array
[0] [0] [0] [0] [0] [0] [0]
[0] [0] [0] [0] [0] [0] [0]
[0] [0] [0] [0] [0] [0] [0]
[0] [0] [0] [0] [0] [0] [0]
[0] [0] [0] [0] [0] [0] [0]
[0] [0] [0] [0] [0] [0] [0]
and the pasting array
[1] [1] [1] [1]
[1] [1] [1] [1]
[1] [1] [1] [1]
[1] [1] [1] [1]
I'd like to paste it in at 1,1 to create something like this:
[0] [0] [0] [0] [0] [0] [0]
[0] [1] [1] [1] [1] [0] [0]
[0] [1] [1] [1] [1] [0] [0]
[0] [1] [1] [1] [1] [0] [0]
[0] [1] [1] [1] [1] [0] [0]
[0] [0] [0] [0] [0] [0] [0]
currently I'm doing this to manually copy the data one array item at a time
def paste_image_from_array(self, in_array, coords = (0, 0), pastesize = (None, None)):
x0, y0 = coords #Where in main array to paste
if x0 < 0 or y0 < 0 or not type(x0) is int or not type(y0) is int: raise ValueError(f"Paste coordinates must be postive integers, X - {0}, Y - {0}")
paste_width, paste_height = pastesize #Width and height of passed array to paste
in_array_width, in_array_height = len(in_array[0]), len(in_array)
left_paste_boundary = x0
right_paste_boundary = min(x0 + paste_width - 1, self.width - 1)
top_paste_boundary = y0
bottom_paste_boundary = min(y0 + paste_height - 1, self.height
- 1)
for xd in range(paste_height):
x1 = x0 + xd
if x1 > right_paste_boundary: continue
for yd in range(paste_width):
y1 = y0 + yd
if y1 > bottom_paste_boundary: continue
self.array[y1][x1] = in_array[yd][xd]
but this is pretty slow, is there a faster way to paste one 2d array into another?
flat sorrel
use slice assignment
shy inlet
flat sorrel
!e
import numpy as np
a = np.zeros((6, 7))
print(f"a={a}")
b = np.ones((4, 4))
print(f"b={b}")
a[1:5, 1:5] = b
print(f"new_a={a}")
You are not allowed to use that command here. Please use the #bot-commands channel instead.
split garden
oof I may have oversimplified my problem
I'm actually working with an array of variable width and height but a depth of 4 for rgba
and another always the same size or smaller array of depth 4 being pasted in
nvm I'm dumb got it working thanks so much
and yeah holy crap that's faster than iterating, 8.5ms instead of 530ms for what I was doing
flat sorrel
In general you should avoid using for loops to iterate through numpy arrays
Python loops are way slower than C loops
split garden
I figured numpy had some faster underlying stuff, there is just way too much docu to figure it out sometimes
stable pecan
i would probably use deques myself, I don't think it seems that tedious at all to code
what's different about them
if the functions are that different you can pass them as some parameter to some simpler overarching function
In [7]: moving_averages = [deque(maxlen=15) for _ in range(9)]
In [8]: values = deque(maxlen=20)
In [9]: def update(n):
...: values.append(n)
...: current_average = mean(values)
...: for averages in moving_averages:
...: averages.append(current_average)
...: current_average = mean(averages)
...:
In [10]: update(15)
In [11]: update(20)
In [12]: update(25)
In [13]: moving_averages
Out[13]:
[deque([15, 17.5, 20]),
deque([15, 16.25, 17.5]),
deque([15, 15.625, 16.25]),
deque([15, 15.3125, 15.625]),
deque([15, 15.15625, 15.3125]),
deque([15, 15.078125, 15.15625]),
deque([15, 15.0390625, 15.078125]),
deque([15, 15.01953125, 15.0390625]),
deque([15, 15.009765625, 15.01953125])]
this was simple enough to write though
ashen wharf
hey does anyone have a good site to read about random number generation algorithms
like how the random.py algorithm works
snow swift
random uses mersenne twister
fiery cosmos
😎
gleaming badger
np_data[:, 7]
(column7) = np_data[:, 7] - [3]
np_data[:, 7] = column7
np_data[:, 7]
im trying to make column7 stop subtracting after done -3 once. How do I do this?
fiery cosmos
can you explain what you want to do more clearly? @gleaming badger
gleaming badger
so, im in jupyter. I need to decrease 3 units from that column but everytime i run that cell of code, it decreases -3
Because i have to run several times the code, (or if I sometimes accidentally run the code), I need I way to be ensured that I only get -3 once
@fiery cosmos
fiery cosmos
either don't run that line specifically or start again
gleaming badger
I see alrighty, Thanks
outer crane
Hey guys, this is a really noob question. But how do I create a list of powers of -1?
This is what I have done:
signs = [(-1**i) for i in range(0,n)]
where n =100
fair summit
you don't have to compute the powers here, you can take n elements from an infinite stream of [1, -1, ...]
other than that, your method works
outer crane
Great, thanks, I'll look into infinite streams! However, My method doesn't work, it just gives me a list of -1s
fair summit
oh right, it's because python is dumb and - has less precedence than **
so -1 ** i is -(1 ** n)
gotta wrap the -1 in parentheses
mint jewel
that is how math works too
subtle escarp
Please I want to write a function that returns the height of an AVL Tree by tracing only one path from the root to a investigating all the nodes in the tree
outer crane
Thanks! I assumed it would register -1 as a number. Thanks
fair summit
@subtle escarp i'm a bit confused, are you trying to find the height of the tree by always traversing to the right branch ?
if so, that's not possible, you'll have to use the same operations as for a regular BST to find the height
subtle escarp
@fair summit Okay. But i thought when the question was asked they were expecting something more efficient than the BST height finding.
fair summit
I don't think that's possible, maybe I'm mistaken tho
subtle escarp
@fair summit Yup I Was thinking That Too
tough iron
@subtle escarp - if it's an avl tree (height balanced) then you always know which branch is heaviest. Traverse the heaviest branches all the way to a leaf.
don't forget to count 😉
fair summit
knowing the heaviest branch doesn't help tho
you have to compute the height to get the weight
oh wait, you can use the weights to pick your direction when traversing the tree
subtle escarp
Thanks For The Help Guys
tawny sleet
north cosmos
Why are u pinging the modmaiil
west surge
fiery cosmos
Pytho Help: available
winged pawn
Hi, I have a function and I made a graph of the execution time acording the input. I got an exponential growth, how can I know the O notation? in order to say its efficiency. If you need I can send the graph or the code here
wide prism
you have to look at the code
winged pawn
you have to look at the code
@wide prism that's the only way? using the number of steps?
wide prism
you're asking how the running time changes as a function of input size for all sizes, so looking at a graph you've constructed for a finite number of inputs won't do it if you want to be sure, in general
where that observation is on the spectrum between annoying pedantry and good point depends on the situation, i guess
winged pawn
😕☹️
wide prism
well... if you say more someone might help you!
winged pawn
I think the only info I can add is what I was thinking. Excel for example gives you a tendency based on the points of the data. I thought I could use this to get the time function of the algorithm. Also I know that if my algorithm could solve the problem in one step for each item of the input, my time function would be y = 2ⁿ.
halcyon plankBOT
Hey @winged pawn!
winged pawn
If you want to see the code: https://paste.pythondiscord.com/ruwacolami.pl, sorry for the variables in spanglish
wide prism
oh, are you returning the powerset of a collection? then you're not going to beat 2^n
wide prism
you can get a powerset in a line or so with the combinations function from itertools, btw
ofc if you just wanted to do it yourself then nevermind that
winged pawn
I didn't knew that, but I feel proud of making my own version 🙂
wide prism
something else you might want to know about is bin(number), which gives you a binary representation of a number
winged pawn
thanks again
cinder rivet
I'm trying to write a program that finds all of the anagrams of words in a dictionary. I have code that works on smaller lists of words but it becomes so very slow on large lists of words that it's basically useless.
I would like some help coming up with a new algorithm.
Here is what I've written so far.
https://paste.pythondiscord.com/ovagurekab.sql
mint jewel
I think you can get faster matching with a trie, but I am not sure if that would work for anagrams
cinder rivet
What's a trie?
Ooh I've just sped up my program by quite a bit. I'm comparing the length of the base word with the length of the test word using
elif len(test) != len(base):
continue
A word can't be an anagram of another word if they aren't the same length.
Still way too slow. Still on Al... after multiple minutes.
mint jewel
You could probably speed it up by making a dict that would map length to a list of words that make sense to test at that length
Or just orecomputing the counters and keeping those in a list
cinder rivet
That dict idea is interesting...
So each key in the dict would be an int representing the length of a word and each value of the dict would be a list of words of that length?
Also, what's orecomputing? @mint jewel
mint jewel
Precomputing, typod
cinder rivet
o
I'm going to try the dict idea. Thank you.
The longest word is Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch's at length 60. Do I have to manually set up key:value pairs for ints 1-60 or is there a way to setup a dict in a more automatic way?
TIL that dict comprehensions are a thing.
words_by_length = {i:[] for i in range(1, 61)}
you're constructing counts for the same words repeatedly in line 23, easy optimization there
but the trie thing seems like the thing to do
cinder rivet
Here's what I have now using the dict words_by_length idea. It's the fastest so far.
https://paste.pythondiscord.com/aquwixusoh.sql
Still way too slow.
@wide prism @mint jewel I'm reading about Trie's here. Do you have any other resources to recommend?
https://en.wikipedia.org/wiki/Trie
mint jewel
That's what I used a few years back when I implemented one IIRC, there may be something better/a python lib that has a trie already made
cinder rivet
Do you think that a method/function like this is supposed to go in the Node class or outside of it?
def find(node: Node, key: str) -> Optional[Any]:
"""Find value by key in node."""
for char in key:
if char in node.children:
node = node.children[char]
else:
return None
return node.value
Well I think I've created my Trie. But I'm not really sure how to use it to find anagrams. @mint jewel
cinder rivet
It seems like Trie's are almost entirely used for prefix-based searches which won't work for what I'm doing. I'll have to come up with something else.
fiery cosmos
I think for each word maintain a state of counters and use a structure like dictionary where a counter can be mapped to list of words with same counters
total time complexity O(26*n)
which should be fine ig
cinder rivet
total time complexity O(26*n)
@fiery cosmos Where n is what? The number of words?
fiery cosmos
yeah
mint jewel
you could match the trie against the word with ordered letters
cinder rivet
you could match the trie against the word with ordered letters
@mint jewel So you're saying to sort the characters in each word?
fiery cosmos
yeah this is bad
mint jewel
ye, but I have no idea how performant that would be
cinder rivet
hmm
fiery cosmos
sorting is again nlogn overhead
wide prism
you don't need to sort, you just need the count for each letter
mint jewel
but the n there is word length
mint jewel
which I assume is way less than the amount of words
fiery cosmos
hmm prolly should look at constraints
cinder rivet
The longest word is of length 60 btw. Idk if you saw that.
cinder rivet
can you give the link to the problem?
@fiery cosmos http://codekata.com/kata/kata06-anagrams/
The constraint is basically that it should run in a reasonable amount of time. For me, that's 10 seconds roughly.
wide prism
yeah i guess each word is short enough that sorting is fine but you're looking for anagrams, the order of the letters in the words isn't important, just the number of each letter
cinder rivet
ye
So make a collections.Counter() for each word and then compare the counters?
That's kind of what I'm doing now...
wide prism
yeah, that's basically what you were doing iiuc
fiery cosmos
no make a dictonary where the key is counter
and then push the words with the same counter
should be pretty easy to implement
cinder rivet
yeah, that's basically what you were doing iiuc
@wide prism You can take a look.
https://paste.pythondiscord.com/vuxutuxoji.sql
wide prism
oh, that is better
cinder rivet
There are 338882 words btw.
fiery cosmos
wide prism
looks like counters can't go into a dict? but i guess you can do something like that by hashing the letter count, more or less
cinder rivet
in this?
@fiery cosmos Yeah 338882 words in that txt.
looks like counters can't go into a dict? but i guess you can do something like that by hashing the letter count, more or less
@wide prism Oh right. dict keys must be immutable and Counters are mutable.
wide prism
i mean it's fine, you can make the keys the sorted word or something else that only depends on the counts
cinder rivet
Right now I have the keys as the lengths of the words and the values as a list of words of that length. 60 pairs in total. Then I only need to search one of those lists for each word.
Having the keys as sorted words would be just about as many keys as there are words minus about 28k for the anagrams.
fiery cosmos
why does the text file has this word?
Ard�che
wide prism
from collections import defaultdict
d = defaultdict(list)
def make_anagram_list():
with open("wordlist.txt", "r", encoding = "ISO-8859-1") as f:
for l in f:
l = l.strip()
w = ''.join(sorted(l))
d[w].append(l)
make_anagram_list()
for k in d:
if len(d[k]) > 1:
print(d[k])
here's a version of the idea above, can probably be cleaned up
seems to work ok with the test file
i guess something smarter should be done to handle accents, case, apostrophes ...
cinder rivet
@fiery cosmos It's an e with an accent.
Ardèche
@wide prism so f is the file, l is the line, w is the word, d is the dictionary. What's k? Also, what is this doing?
wide prism
haha sorry, it was quick and dirty. k for key
this prints out the words with anagrams (other than themselves)
...or it's supposed to, def could have screwed something up
cinder rivet
So each key is the sorted word and each value is a list(?) of the words with those letters?
wide prism
yup
cinder rivet
Ahh so defaultdict let's you set the default value for the keys as an empty list. This lets you append the words to that list.
Also, can you explain how you are opening with with? I'm not well-versed in it. Also, what does the encoding parameter do?
@wide prism
wide prism
with opens the file and automatically closes it when the block is over
the encoding parameter is just so the file is opened with the correct (hopefully) encoding, i guess by default it tries to use an encoding that file wasn't using
cinder rivet
Also, what do you think is faster,
line = line.strip()
or
line = line[0:-1]
?
wide prism
no clue
probably worth noting for general use that one will get the wrong result if there's no newline at the end of the file
cinder rivet
Just noticed that lol
anagrams.write(" ".join(sorted_words[key]) + "\n")
This works and it works well. But I don't get why it's so much faster than what I was doing.
wide prism
the first thing you posted was O(n^2) with n the number of words; this is O(n)
since you were going down the list and looking at each word, and for each word, comparing it with every other word one by one
cinder rivet
2 ^ 338000 😳
cinder rivet
o
"In typical usage the O notation is asymptotical, that is, it refers to very large x. In this setting, the contribution of the terms that grow "most quickly" will eventually make the other ones irrelevant."
Interesting...
cinder rivet
I didn't do any encoding and it worked fine.
words_file = open("wordlist.txt", "r")
Would you show me the error, please?
cinder rivet
ah
cinder rivet
o
sec
I deleted those words because I didn't think they were necessary to the problem. I redownloaded the txt to see if I got the error but I didn't.
fiery cosmos
hmm 🤔 idk
cinder rivet
@wide prism Wait I don't think we ever converted the words to lowercase. That probably affects the results.
wide prism
yes, it might
cinder rivet
Simple fix that should work.
line = line[0:-1].lower()
you might also want to treat e-with-an-accent the same as e, etc., or ignore punctuation or not
just at a glance at this file
cinder rivet
I'll not be ignoring punctuation. It makes for interesting results.
"For added programming pleasure, find the longest words that are anagrams, and find the set of anagrams containing the most words (so “parsley players replays sparely” would not win, having only four words in the set)."
I'll be trying this now. Should be easy.
surreal flint
plzz help me to embed a pie chart(figure,canvas,matplotlib) in tkinter gui and to update the values of chart and the pie itslef with click of a button/function
fiery cosmos
Hi, I'm not sure this is the correct channel for this question, sorry if my doubt was true.
I'm trying to sort a nested dictionary while keeping the sub-dictionaries linked to their parent (the names of the sub-dictionaries are generated and not fixed).
Here's a sample of the dictionnary
{'d’enfoncer': {'les': 1, 'dans': 1}, '’enfoncer les': {'ongles': 1}, 'enfoncer les ongles': {'longs': 1}, 'les ongles longs': {'dans': 1}, 'ongles longs dans': {'sa': 1}}
oblique panther
@fiery cosmos this question is in a bit of a grey area for what's on topic for this channel, but regardless I'll try my best to answer it.
Dictionaries do remember their insertion order, but they're primarily meant for looking things up, so I avoid using them for their order.
daring ledge
Could always use OrderedDict instead.
oblique panther
As long as all the values in the dictionary are dictionaries, you can sort them all with a list comp
well, a dict comp
dict_of_dicts = {'d’enfoncer': {'les': 1, 'dans': 1}, '’enfoncer les': {'ongles': 1}, 'ongles longs dans': {'sa': 1}}
new_dict_of_dicts = {k: <do something with v> for k, v in dict_of_dicts.items()}
the expression to sort a dict is a bit ugly and depends on if you want to sort by the keys or the values.
also, there's no straightforward way to sort a dict in-place, but you can make a new one that has the same key-value pairs, but it will be a new object
so if you have other references to the unsorted dict somewhere else, you'd have two things going on.
cinder rivet
@wide prism @fiery cosmos @mint jewel Thank you for helping me the other day. Sorry for pinging but I just wanted to make sure you guys know that I'm thankful.
fiery cosmos
anyone that can help me ?
unexpected indent (<unknown>, line 49)
What does that error means?
oblique panther
@fiery cosmos that question would be better for an individual help channel, but indentation is part of python's syntax so you have to indent consistently and where it's needed.
Also, any time you get an error message, remember to post the whole message and the code that relates to that error. Otherwise no one will know what to fix.
split garden
Working on making snow in python, anybody have a good algorithm for doing so?
This is what I have so far it uses a numpy array and shifts the whole array by an passed vector each frame then randomly generates more at the top
I randomly shift columns and rows up/left/right to generate the fluttering currently
cloud quiver
That’s cool
slender kestrel
can anyone help me in deleting a node in linked list?
fiery cosmos
Can someone help me with an algorithm to make a tween function
I just want to have a function that takes two integers, x and y and a duration of time
and return an array of interpolated value states in the duration
c
fiery cosmos
@slender kestrel what part you are struck/not understanding?
slender kestrel
deleting a node @fiery cosmos
fiery cosmos
did you search for an explanation online?
slender kestrel
yes
it said that python automatically deletes when it the node is not referenced @fiery cosmos
but when i print the list,the element reappeared
dense oasis
well i got a really basic question
about a loop i write
i guess this is the right place to ask
well i want my loop to start/stop with a key input (mouse3 if possible)
tryin to make an on/off switch i can say
raw juniper
i want to make a Stack class. can i inherit it from list (since both are LIFO)?
fiery cosmos
@raw juniper do it both ways using python list and a linked list
raw juniper
oh okay thanks
also, how do i make actual arrays?
like Array(int, [1, 2, 3])
(without using array.array)
or just Array([1, 2, 3]) where the first element decides what type of array has to be created
oblique panther
@raw juniper the python list.pop operation is O(n) so you don't want that
I'll come back and explain in a moment
raw juniper
okay
mint jewel
pop() is O(1), pop(k) is O(n-k)
raw juniper
im here
oblique panther
@raw juniper a python list is secretly an array in C, and it occasionally copies all the elements over into a larger array if you ever run out of space
if you pop the first item from the list, it has to promote each subsequent item in the list
fiery cosmos
but in amortized sense it would be still O(1)
since the copying part does not take too often
mint jewel
but for a stack, you should just need .pop and .append
oblique panther
so I suppose one option is to only work with the end of the list
but then if you want to print it, you'd have to reverse the list, since conceptually the item you're dealing with is "first"
mint jewel
most stack prints I see end in the top element
raw juniper
most stack prints I see end in the top element
@mint jewel oh i was gonna print it likeStack(lst[0], lst[1], ...)
mint jewel
yeah, that should work fine
raw juniper
where lst[0] is a variable and not the string 'lst[0]'
mint jewel
there are 2 ways to print a stack. The debug way is starting from stack bottom, ending at the top, and the actually mathematically sensible way is pop print until the stack is empty
oblique panther
I would implement it as a linked list because then you have a starting place to implement queues and deques
raw juniper
yea i was gonna give it as a choice to the user
a choice between a linked list and an array
for the stack
they have to pass it as a parameter
Stack('a', [1]) for array based stack
mint jewel
linked list impls are less space efficient and cache unfriendly, but they are worth looking at as well
raw juniper
Stack('l', [1]) for linked lists based stacks
mint jewel
why not ArrayStack, LinkedListStack
raw juniper
yea i can do that too
but first ill have to implement arrays and linked lists on my own
ive implemented linked lists
i dont wanna use array.array
like im tryna use as less libs as possible
so i wanna make my own Array class
like Array(int, [1, 2, 3])
or you can do Array([1, 2, 3]) and the first element will decide the datatype of the array
or smth like IntArray, StringArray, etc
oblique panther
you can't really implement arrays without access to memory
oblique panther
oh okay
raw juniper
but i have zero clue
oblique panther
if I know what I think I know from my C class--and I don't know how I got a B in that class--the idea with arrays is that C knows where each memory is in the computer. And for arrays, it allocates a fixed block of memory
And then it knows how many spaces each element takes up and can just do math to figure out which space to go to for the nth element.
raw juniper
yea to store 6 ints between 0-255 (using the correct datatype), the computer will allocate the bytes like 00,00,00,00,00 (remove spaces to reduce memory usage, so 000000000000)
(its all in hex btw)
(so 00-ff)
^ what bats taught me
oblique panther
that sounds right
raw juniper
so.. do i just do class Array(array.array):?
like ```py
class Array(import('array').array):
"""docs"""
pass
@raw juniper are you trying to inherit methods from another class?
raw juniper
yea
oblique panther
which ones?
raw juniper
im basically trying to rename array.array to mylib.Array with my own documentation
cause implementing memory stuff in python is hard
cause Array = array.array wont do much
oblique panther
you can't change what's in the standard library, but you can implement a class meant to do the same thing
raw juniper
yea i am not changing it
oblique panther
!e
from array import array
class Array(array): pass
@oblique panther :warning: Your eval job has completed with return code 0.
[No output]
im just "renaming" it cause, like i said, i cant implement in python so easily
oblique panther
you'd want to do something like that, I guess
oblique panther
why are you using __import__?
raw juniper
im importing array temporarily
so that it cant be found in dir(mylib)
big brain time
oblique panther
in that case you can do from array import array as _array
no funky import trick needed
mint jewel
or just del it at the bottom of the file
mint jewel
that is entirely irrelevant
oblique panther
Array would still have a reference to array.array in it for its whole lifetime
oblique panther
I don't believe you can have an object defined in a certain module without having the whole module loaded somewhere in memory
but it's not worth trying to optimize around that.
(at least not in my opinion)
raw juniper
oh, ill use from array import array as _Array then
man i wish i could fuck with memory in python
for arrays and stuff
oblique panther
there might be a way to do it, but at the end of the day you have C for that
and a lot of Python's syntactic niceties depend on it being in charge of memory.
raw juniper
wait but how can i add C code to a python lib?
oblique panther
there's a C api for writing compiled Python in C. There's also a channel for it here, #c-extensions
raw juniper
lib
|- __init__.py
|- module.py
|- array.c
```?it's not that simple, I don't think.
oblique panther
I did it once but I'm not completely sure how it works
there's a C file and then the setup.py file compiles it when you go to install the package
but I'm not sure what that entails.
raw juniper
im making a LinkedList class. and there are three types of LinkedLists (singly connected, doubly connected and circular linked lists). should i write a single classes which takes the type as a string ('s', 'd', and 'c') and the list or make three different classes (SinglyLinkedList, DoublyLinkedList, CircularLinkedList)? (I think the later would be a better option)
(also, please ping me)
final fjord
Hello, my name is Brian. I am in a beginner's python class and I am working on a pretty simple program but there is one part that I cannot figure out. Can someone give me a bit of guidance?
these are the directions, with the highlighted parts being what is tripping me up.
halcyon plankBOT
Hey @final fjord!
final fjord
this is what I have so far. I just cannot understand how to pass 2 arguments to def grade_calculator in one case and 4 arguments in another case
fiery cosmos
as they have said about defining the grade_calculator function has four parameters and two of them are set by default so the function looks like this
def grade_calculator(lab_score_list, test_score_list, lab_weight=50, test_weight=50):
# your code here
so it can be used as a two argument function where the other two are set by default or a four argument function
so you can call the function in following way
grade_calculator(L1, L2)
or
grade_calculator(L1, L2, 45, 56)
@final fjord
you need to pass scores list along with lab weights in one case and just the scores list in another
final fjord
so i can override the def grade_calculator lab_weight = 50, test_weight = 50 with a grade_calculator(lab_weight = 60, test_weight = 40)?
fiery cosmos
yes along with scores list
final fjord
ok. that makes sense. but we didnt get anything that explains that in our course
thank you so much for your help
final fjord
true, but in the PP for the course it never says that you can do that
regardless, thank you very much for your help
fiery cosmos
Oh so wait you are not allowed to do that?
because there can be many ways to solve a single problem
final fjord
there is nothing that says we cannot, but it was not explained that it is even a possibility
fiery cosmos
I see
fiery cosmos
Lol ok
quasi oracle
@raw juniper I'd make them separate classes
Otherwise you're implementing a circular doubly linked list but limiting part of the functionality according to input
And your singly linked list would still have a "go back" method even though it's singly linked
raw juniper
Yea that's what I did but thanks!
glad chasm
What is the best language for implementing algorithms and data structures?
fiery cosmos
I would say python, but when it fails to pass the validation judge I code the same thing in c++
quasi oracle
@fiery cosmos I'm not sure why you dumped that here
@fiery cosmos the mods deleted it
fiery cosmos
ohk.. but the same post is in a bunch of channels.. over a period of time
quasi oracle
I'll look into it, thanks
fiery cosmos
seems deleted now too...
agile sundial
if you need it for competitive programming python may be too slow
radiant trench
where to start python language for beginners
@fiery cosmos go to the web(youtube)
vocal gorge
@fiery cosmos I'd suggest to read the channel description, then, you probably want #python-discussion.
However,
!resources is what you need @fiery cosmos
halcyon plankBOT
modest drift
H4eolloolo
oblique panther
@modest drift hi
oblique panther
@modest drift I would need to know what the question is
this channel is mainly for algorithms and data structures
oblique panther
@modest drift go ahead and post your question here.
modest drift
Yes the questn is getting uploaded
oblique panther
you'll want to use text as much as possible. Images of questions are more difficult to read.
modest drift
A RBG color is formed by adding different intensities of Red, Blue and Green Colors. So, any RBG color can be represented in the form of a triplet where is intensity of red color, denotes is of blue color and is intensity of green color.
You have been given colors, where each color has the intensities of red, blue and green color as . You can make new colors by mixing a subset of these colors. So, if you mix the colors you would get a color having respective intensities of red, blue and green as max of each .
You have been asked queries, where in each query you need to answer whether is it possible to obtain a color by mixing the given colors.
Note: that you may mix any number of colors (possibly one) to make the required color.
Input Format
The first line of input contains two space separated integers and .
The next lines of input contains three space separated integers and denoting the respective intensities of red, blue and green in the color.
The next lines of input contains three space separated integers and denoting the respective intensities of red, blue and green color required.
Constraints
Output Format
For each query print a single line containing "" if it is possible to obtain the given color, else print "".
Sample Input 0
2 2
1 3 5
5 3 1
5 3 5
3 3 3
Sample Output 0
YES
NO
Explanation 0
For the first query, we can mix both the given colors to get
For the second query, there's no way to acheive the given color.
Sample Input 1
4 3
1 1 1
0 0 2
5 0 0
5 2 2
0 0 2
5 1 2
5 3 2
Sample Output 1
YES
YES
NO
Explanation 1
For the first query, we need not mix any color as the color is the required color.
For the second query, we have to mix the first colors, i.e. , and to obtain the given color.
For the second query, there's no way to acheive the given color.
some parts of the question in text are missing sorry check them in the image
fiery cosmos
Constraints pls
fiery cosmos
Also provide the problem link if it is not from ongoing contest
primal dock
Could someone tell me why there is a for loop, like wouldn't this loop be executed past each level since we are appending the node which results in a bigger array?
Link to the problem https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/
fiery cosmos
actually that for loop just goes over the childs only not over the extra elements that are appended to the list
oblique panther
@primal dock for _ in range(len(q)), where q is a deque and you're popping one element from the deque each time, would just be "do something for each element of the deque"
fiery cosmos
!e
a = [1, 2, 3]
for i in range(len(a)):
a.append(i)
print(a, i)
You are not allowed to use that command here. Please use the #bot-commands channel instead.
fiery cosmos
rip
https://discordapp.com/channels/267624335836053506/267659945086812160/764867986342281268
see here the index doesn't go past 2
fiery cosmos
yeah actually I never do both iterating and appending at same time
primal dock
yeah same lol
oblique panther
oh i see, but why doesn't the len detect the change?
@primal dock a for loop doesn't re-evaluate a condition every time
fiery cosmos
well in c++ you would get a nasty error
primal dock
now i got it, ty everyone!
fiery cosmos
but python is too strong
oblique panther
if you have for _ in range(len(x)), len(x) will be evaluated to an int, and then subsequent changes to x won't matter.
and then the range object will be created and that's the only object you'll iterate over during that for loop. You can't change it.
fiery cosmos
I think another way to do it is to have a dictionary where key is the level and the value points to the sum of all node values at that level
oblique panther
In this case, I think while q would have been better because for deques, q will evaluate as truthy as long as it has at least one element.
primal dock
if u use a dictionary won't be space and time complexities be the same as that solution?
aren't they both o(n)?
fiery cosmos
that solution is actually quite clever
I did this
from collections import defaultdict
level_sum = defaultdict(lambda : 0)
def dfs(root, level):
if not root:
return
level_sum[level] += root.val
dfs(root.right, level + 1)
dfs(root.left, level + 1)
dfs(root, 1)
max_level = curr_sum = -1e9
for level in level_sum.keys():
if level_sum[level] > curr_sum:
max_level = level
curr_sum = level_sum[level]
return max_level
space and time would still be the same 🙂
primal dock
what is (lambda: 0), i still dont quite understand lambda in python
fiery cosmos
uhh its like by default a value to key doesn't exist
primal dock
so is defaultdict same thing as dict but faster?
fiery cosmos
so If I access any key its value would be 0
primal dock
oh i see
fiery cosmos
idk about speed tho
oblique panther
@primal dock a lambda is a one-line function
primal dock
is it just a way for us to bind a function to a variable, i saw some examples and that's what its' usage looked like
in one-line
vocal gorge
so is defaultdict same thing as dict but faster?
no, a defaultdict is a dictionary that returns some "default value" when you access a nonexisting key.
primal dock
so its' better at error-handling
vocal gorge
that default value is provided to it when creating the defaultdict - it has to be a 0-argument function that returns said value.
Such as, for example, lambda:0, a zero-argument function that always returns zero.
for details, see defaultdict docs.
oblique panther
@primal dock you typically don't assign a lambda to a variable. you would just use it in-place
primal dock
oohhhh i see
oblique panther
defaultdict, for example, typically has a lambda as its default_factory attribute, and then every time you do something like my_defaultdict[x] += 5 and x isn't a key, it just does self[x] = self.default_factory() internally and the continues as normal
but it's not required to be a lambda. it can be any callable.
it will just call it without arguments and hope that it works.
vocal gorge
yeah, the defaultdict docs actually use int instead of lambda: 0
like, defaultdict(int)
because int returns 0 when called without arguments.
similarly, defaultdict(list) would be a defaultdict which creates a new empty list each time it needs a default value, because list() returns a new empty list.
autumn anvil
Write a function in Python that counts the number of “Me” or “My” words
present in a text file “STORY.TXT”.
If the “STORY.TXT” contents are as follows:
My first book
was Me and
3
Page 8 of 11
My Family. It
gave me
chance to be
Known to the
world.
The output of the function should be:
Count of Me/My in file: 4
can someone help me with this
fiery cosmos
with open('STORY.TXT') as f:
lines = f.readLines()
cnts = 0
for line in lines:
if 'Me' in line:
cnts += line.count('Me')
if 'My' in line:
cnts += line.count('My')
print(f'Count of Me/My in file: {cnts}')
I believe this is the best channel for my completely inexperienced questions. I've searched, pretty much finding everything but what I'm trying to find.
I hope this is a good question anyway, if not please tell me. I'm brand new and going through the print and math symbols right now. I ask because I plan on game development which will use multiple and long scripts, so I'm trying to learn to reduce memory usage from the get go.
In normal text, a space is considered a character, therefore usage. Would character usage in code increase the amount of memory it uses? Also wondering if skipping lines to make things neater will use any memory? Example..
print('Spaces', 3 - 2 + 1) # Comment
Compared to
print('None', 3-2+1)#Comment
fiery cosmos
I'm making a survey web-app that requires a clustering algorithm to aggregate the results on a spider plot. Can anyone recommend a good clustering algo that can integrate with react.js and mongodb?
quasi oracle
@fiery cosmos
In general spacing should not be a concern at all when thinking about memory / runtime. If a space makes things more readable then you should add it
But for this kind of question you can open a help channel #❓｜how-to-get-help or ask in #python-discussion
fiery cosmos
Thank you very much.
split nymph
Can anybody help with coding Radix Sort?
wide prism
probably? imo you're likely going to get better help if you ask something a bit more specific
brazen glade
Dude i just found out that records and fields aren't just funny names for the parts of spreatsheets. They're data structures
And that a tuple is a record
fair summit
the concept unifying records and tuples is "product type"
split nymph
@wide prism I need to implement radix sort on multiple arrays
def radixSort(n, vectors):
return vectors
# DO NOT EDIT THE FOLLOWING CODE
vectors = [
[3,3,3,3,3,2,2,2,2,2],
[2,3,2,2,2,2,2,2,2,2],
[1,3,0,0,2,1,0,0,0,0],
[1,3,0,0,2,1,0,0,0,0],
[2,3,2,1,2,2,2,2,2,2],
]
sortedVectors = radixSort(5, vectors)
for vector in sortedVectors:
print(vector)
i more meant, if you said what you're running into trouble with
brazen glade
I would go on to say that a database table is a set of tuples but i think there are different kinds of tables that become immutable
wide prism
are you supposed to sort them together? ie a 0 in a late array should end up in the first array? then i think you can effectively treat it as if it's one long array with fiddly indexing, no?
split nymph
No I think we're supposed to sort each array separately
wide prism
oh, then you just need to write a normal radix sort and call it n times, once for each array, yeah?
or am i missing something about the problem here
split nymph
Yeah
This is the notes given for it
Doesn't really say, but I would assume it's per array
cinder rivet
Does the Sieve of Eratosthenes start to break down in terms of speed at higher numbers? I'm getting some memory errors.
ivory aspen
hii guys
which is the best place to learn all data structures and algorithms for python
ping me when you reply
slender kestrel
Hi can someone give me clue for identifying operator in a string
lets say from an infix notation
rain rover
Convert the following infix notation into equivalent postfix notation : 2
A + B * (C-D) / E
Help fastt
rain rover
Ok tysm bro
slender kestrel
check if it is correct on some online platform
you could google infix to postfix converters and you might get it
rain rover
okiee tysm
flat sorrel
I don't think simply providing the answer is the best way to go here...
fair summit
Does the Sieve of Eratosthenes start to break down in terms of speed at higher numbers? I'm getting some memory errors.
@cinder rivet it breaks down in terms of memory, as you need to keep track of all the numbers < the upper bound you're looking for
cinder rivet
Yeah... ty
fair summit
its runtime complexity is O(n log log n), which is decent enough for it to run up to a few millions without noticing the runtime on a decent machine i'd say
cinder rivet
n = 600851475143 for what I'm doing
fair summit
that's definitely "doable" in a "reasonable" time, but that won't fit in memory
cinder rivet
ye
cinder rivet
What's the fastest algorithm for finding the greatest common divisor of two numbers? You don't have to give it to me in code, but if you give the name of it, I can try to implement it.
low palm
@cinder rivet I suppose https://en.wikipedia.org/wiki/Binary_GCD_algorithm . Notice though that gcd is implemented in python's math module, so you don't really have to implement it yourself (unless this is for learning)
cinder rivet
Oh it's builtin? Awesome.
low palm
from math import gcd
cinder rivet
I didn't know that.
cinder rivet
I would like some help coming up with a way to find the greatest prime factor of a large number. I have a working solution but it's much to slow on large numbers.
Here is what I have so far.
https://paste.pythondiscord.com/ihazolojad.py
One optimization I could use is to implement a faster primality testing function. I'm not sure if that's where the big slowdown is though.