#algos-and-data-structs

1 messages · Page 134 of 1

feral hound
#

however I dont quite understand why you care about the order if your feeding this into a cnn

#

the order of elements in the cnn shouldnt make any difference to my knowledge

sudden urchin
#

because the tuples contain a few more data points

feral hound
#

although that does depend on what your trying to do, if its an image it would matter, but I dont think thats the case for you

sudden urchin
#

I don't really want to talk exactly what I am doing... confidential...

feral hound
sudden urchin
#

(a, b, c, d, e)

feral hound
#

and theyre all numbers?

sudden urchin
#

yes

feral hound
#

its exactly 5 numbers correct?

sudden urchin
#

yes

#

I mean it's not important because the problem doesn't really change.

feral hound
#

and you just want the distance for any point the 2d array to be closest for neighbors correct?

#

and you calculate distance by doing sqrt(deltaa +deltab + deltac + deltad + deltae) correct?

sudden urchin
#

I think I made it more complicated by not explaining it properly

#

I have two lambdas

#

and i want a function that makes 4 evenly sized lists out of one based on this kind of 2x2 decision matrix(but with the results of the lambdas) i drew earlier

#

and I want to do this recursively

#

and at the end I want to assemble them into a quadratic array

feral hound
#

I'll be honest with you I dont fully understand what you want to do now, based on this, but I think you might be over complicating it somewhere

#

just remember that at the end of the day regardless of how you do it what matters is input -> output

#

you can think about optimizing after you get that correct output for a given input

#

will also make testing easier

sudden urchin
#

the problem is that as far as I can tell there isn't really an easier way

#

for example if i first sort the list, then slice it into the required amount of lists and sort them by the second lambda and produce my array that way, i get a different result

#

or at least the result won't be the same reliably

feral hound
sudden urchin
#

my method is more stable

feral hound
#

I dont really see how, but I dont think I can help anymore, since I dont really understand what the problem is

#

hopefully this at least gives more info for someone else that might have a better idea

#

btw I would say give an example of 16 tuples and how you want those to come out, would help a lot, so input 16tuples ouput 4by4 array

sudden urchin
#

ok, this might take some time to do by hand

feral hound
#

make sure its also 5 values per tuple btw

#

the closer it is to your actual data the better

sudden urchin
#

This will take hours

feral hound
#

hmm maybe just start with 4 tuples first

#

it wont give enough info to solve the problem i think but it will at least give us a starting point

feral hound
sick spire
#

hey guys

#

do you think you can study algorithms with python

#

or its better something like c++?

feral hound
#

depends on the algos, but in the general case the language doesnt really matter, and its probably easier with python since there's some implementation details you dont have to worry about

rugged vigil
#

Hello to everyone. I want to assign the type of a data as a string to a variable in Python. How can I do that? For example: a= 5, a's_data_type=="int"

vocal gorge
old vector
#

no interest is building to read this book. can u tell how to read it efficiently without getting bored

tropic glacier
#

Honestly I think it's easier to think about some algorithms in a more low-level language like C

old vector
#

i have 2 years only

#

in which i have to learn data science

#

dsa

#

and make projects

feral hound
#

more than enough time

feral hound
#

if your quick you can finish it in a few days

old vector
#

what does it includes?

feral hound
#

they teach c, python and javascript, as they go along basic CS concepts

mystic junco
faint sentinel
#

why does the outer for loop runs only once????

eager narwhal
# faint sentinel why does the outer for loop runs only once????

condition for the first loop: i < n
condition for the second loop: i < n^2

so, we go into the first loop, to the second, and i increase until i >= n^2, but if i >= n^2, i is also superior to n. So if the second condition don't hold, neither would the first one.

So, you run the loop 1 one time, you get stuck into the second one until i >= n^2, and you go out of the loop 1, so one iteration max.

#

(but tbh, it may be O(1), I really wouldn't be surprised if the compiler change it to

System.out.println(n < 0 ? 0 : (n*n)*(n*n+1)/2);
}

But compiler optimisation wouldn't really count for O notation algos...
)

vapid plank
#

Hello!!

feral hound
mystic junco
feral hound
#

and I really dont know how much employers care about it, either way you can still say you did the course, the certificate only shows that you really did do it and arent lying about it

#

its also a nice way to give back and show support if you can afford it

dull wedge
#

Hey there , would anyone be so kind to help me with a little time complexity issue in my code? Im solving some DMOJ problems on my own to teach myself how to code.

#

I'm pretty confident I wrote it in O(n) but I keep getting either a TLE or MLE error at the last test case.

shut breach
dull wedge
#

https://dmoj.ca/problem/avocadotrees this is the judges question

DMOJ: Modern Online Judge

Julia likes avocado trees. She maintains a strip of N trees by a river. All of the trees are grown along a straight line. However, Rose the avocado-robber has just made it into town. Rose would like to steal all the avocados from Julia's trees, but she also knows that Julia keeps her trees well guarded. This means that Rose …

#

and this is my raw code for it

#

I only started to code a few weeks ago so sorry for my unorthodox writing xD

dull wedge
#

I think I figured out myself whats wrong ... There is no need to save the 'q' in a seperate loop list prior to the end results loop. Feelsbadman I have been breaking my brain over this for 3 hours.

magic trellis
#

Any recommendations on how to make a good moving average algorithm

feral hound
feral hound
magic trellis
#

TY

magic trellis
feral hound
magic trellis
feral hound
#

nothing from me, but you could have a look at the pinned messages

fiery cosmos
magic trellis
dull wedge
#

I use introduction to algorithms from Thomas n. Cormen. Reads pretty smooth if you are decent at mathematics @magic trellis

magic trellis
dull wedge
#

@magic trellis Basic knowledge not SUPER advanced or anything. Functions logaritms summation limits etc

magic trellis
#

Thanks for all the resources this is awesome

#

:D

dull wedge
#

You are very welcome

idle pier
#

is Number of Islands one of the best matrix questions to practice on? Almost every other matrix problem I have seen is if like a variation of number of islands

agile sundial
#

what's Number of Islands

#

is that just like, find all the blocks of 1s in a matrix of 0 and 1

idle pier
#

200 number on islands on leetcode @agile sundial

agile sundial
#

link?

idle pier
agile sundial
#

is this really specifically a matrix problem though? isn't this just a graph theory question?

feral hound
feral hound
#

just make a matrix in an an empty py file and play around with it until your comfortable

#

thats all there is to it

#

and you might benefit from learning about matrices in maths, if your still not comfortable with it

rare orbit
#

Assume you have functions $f$ and $g$ such that $f(n)$ is $O(g(n))$. For each of the following statements, decide whether you think it is true or false and give a proof or counterexample.
(a) $\log _{2} f(n)$ is $O\left(\log _{2} g(n)\right)$.
(b) $2^{f(n)}$ is $O\left(2^{g(n)}\right)$.
(c) $f(n)^{2}$ is $O\left(g(n)^{2}\right)$.

#

Can someone help me with this?

#

(Is there no tex bot on this server?)

agile sundial
#

apparently not

ripe delta
#

hello guys
what ML frameworks use the Naive Bayes Classifier?
I'm planning to create a chatbot with this algorithm
I'm learning Dialogflow but is uses "rule-based grammar matching and ML matching and algo"
my project requires the "Naive Bayes Classifier"
hope you can help. tia!

rugged bolt
#

Hello

#

Can anyone suggest me the best resource to learn DSA in python

onyx umbra
rugged bolt
onyx umbra
#

learn data structures from gfg or some course/tutorial, practice problems on leetcode

rugged bolt
#

I wanna clear path

#

DS With algo

onyx umbra
#

are u in college?

rugged bolt
#

Yah

onyx umbra
#

CS?

rugged bolt
#

H

#

What about you

onyx umbra
rugged bolt
#

It's yes

onyx umbra
#

oh

#

then u will learn DSA there

#

u can just practice problems on leetcode

#

which year u r in?

rugged bolt
#

Can we chat personally

onyx umbra
#

yea sure

rugged bolt
#

Ok

north glacier
north glacier
halcyon plankBOT
#

Hey @languid raptor!

It looks like you tried to attach file type(s) that we do not allow (.pdf). We currently allow the following file types: .gif, .jpg, .jpeg, .mov, .mp4, .mpg, .png, .mp3, .wav, .ogg, .webm, .webp, .flac, .m4a.

Feel free to ask in #community-meta if you think this is a mistake.

hollow quiver
#

hi people

#

I know that integers and many other things are immutable

#

and whenever u change them, a new memory address is allocated with the new value and the previous one is deleted

#

However, I wanna know why this is the case?

#

what is preventing it from just assigning a new value to that memory address

#

infact, there is an assembly instruction STA which assigns a particular value to a hard coded memory address
so that means we can change that

brave oak
#

this is in fact an optimisation that could be made

hollow quiver
#

I read somewhere it's a design choice

brave oak
#

immutability isn't enforced @ the processor level

#

or even @ the C level (for CPython)

#

but @ the Python level

#

and

#

in the general case

hollow quiver
#

but it seems to actually decrease performance
so why is that chosen?

brave oak
brave oak
#

nothing else is referring to that object

#

okay, for example

# 
a = 'abc'
b = a
a = a + 'def'
#

you wouldn't expect b == 'abcdef', would you?

hollow quiver
#

nope

brave oak
#

without checking whether there were any other references

#

that's what you would get

#

in short

#

it is possible

#

to do what you're suggesting

#

but you need to detect whether it's safe to do so

hollow quiver
#

but you can just make it so b = a creates a new memory allocation
or make it a little more efficient by saying like a= a+ 'def' first does that

brave oak
#

speed is good, but correctness is most important

hollow quiver
#

yeah

brave oak
hollow quiver
#

yeah

brave oak
#

and you might never need those copies

#

besides

#

one of the big pluses of immutable data

#

is not having to make copies unnecessarily

shut breach
#

that's just fundamentally not how python names work

brave oak
#

are you going to copy it 9 times?

hollow quiver
#

what if you had an smart way

#

that did not copy it as long as it is same

#

but when u change a, then it copies them before changing

#

but the thing I really wanted to know is if it is actually possible at cpu level or no
I can find out why it's designed like this

brave oak
#

but

#

okay, the thing is

#

@ the Python level

#

you need to know also

#

"what and how to modify"

#

okay, look at it this way

#

say you have a tuple

#

(1, 2, 3, 4)

# 
a = (1, 2, 3, 4)
a = a + (5,)
#

and say you know a is the only "reference" to that tuple

#

and you want to add to it inplace, right?

#

so you don't have to allocate new space

hollow quiver
#

it just seems weird to do it like that
I know there are good reasons to do it that way

#

ummm

#

u see python is a really dynamic language

#

but like

#

In something like C or java

#

the array size is fixed

#

so the memory is there

#

you can just do it

#

the thing is it's not only in python

#

in many languages it's like that

#

and in C, it won't even do that optimization point to not copy it unless you pass it as pointer

#

so what is the reason that's done in something like C?

brave oak
#

if I understand your question correctly

hollow quiver
brave oak
#

ints are cheap

hollow quiver
#

I mean

brave oak
#

and you know that an int will not change from under you

hollow quiver
#

you said that int is immutable in python
because if there is a reference, that will change
and the reason is that it does not make copies for new references
but in something like C
it does that
you will have multiple copies
so then what's stopping you from making the int mutable?

brave oak
#

you could

#

but again

brave oak
hollow quiver
#

so then why is it the choice?

#

many data structures are like that

brave oak
hollow quiver
#

yeah

brave oak
#

because

hollow quiver
#

in many languages

brave oak
#

it makes it easier to reason about code

hollow quiver
#

like in C#
int
bool
string
most data structures are immutable
although it performs exactly like C

brave oak
#

C# is really different from C

#

but anyway

#

I am a fan of immutable data by default

hollow quiver
#

I mean it does not make any difference for me how a language does things

#

but I need to research a little about why it is better to have most data structures immutable

brave oak
#

aiding local reasoning

#

if your data is mutable

#

it can change at any time

#

anything that has ever had a reference to your data

#

can change it

hollow quiver
#

yeah

brave oak
#

this is particularly pernicious when you're working with parallelism

#

immutable data is (generally) threadsafe by default

#

it's possible for weird stuff to happen during construction

#

but assuming a data structure is constructed in a valid state

#

you don't have to worry about certain kinds of race conditions

#

also

hollow quiver
#

like I always think changing immutable data is expensive
since it has a lot of steps at CPU level
like u need to copy that memory data to a register
then assign it to another memory location
and load thatprevious memory address with null or something

brave oak
#

when working with mutable data

#

you need to worry about defensive copying

brave oak
#

there are ways to design data structures

#

such that creating copies with modifications is "cheap"

hollow quiver
#

I see

brave oak
#

where "cheap" generally means "with low asymptotic time complexity"

#

defo not as performant as your vanilla mutable dynamic array, of course

#

and more complicated to implement

#

okay but a really good example is a singly linked list

#

you can make it immutable easily

#

and it works well

#

"appending" is constant time

#

since you can reuse the other side of the list

#

inserting is slower, though

#

since you need to change everything after the insertion point

hollow quiver
#

I see your point

#

when you have something dynamic in size

tropic glacier
#

The whole point of linked lists is that insertions and removals are cheap

hollow quiver
#

it's just so hard to make it mutable

brave oak
#

in general, I would say - default to immutable data and consider mutability as an aoptimisation

brave oak
hollow quiver
#

but for example in a fixed size normal C array
u have none of the issues
and infact arrays are mutable in many languages
I just don't see the difference between like an int32 and an array
both have fixed sizes so why int32 is immutable but array is mutable?

brave oak
tropic glacier
brave oak
#

in many functional languages

#

so...I would say that's quite far from "the whole point"

tropic glacier
#

That's exactly how they're used

hollow quiver
brave oak
brave oak
#

there's a difference between rebinding a variable and modifying a value

brave oak
#

what happens when you do b = a in C? and in Python?

hollow quiver
#

I mean why modifying the pointer modifies that memory location like it's mutable
but the variable itself makes a new allocation?
also btw what's the name of the process of making a new allocation to change the data?

brave oak
#

why C does this?

#

I do not know

tropic glacier
#

Sorry, I feel I've just walked into bizarro world. What do you think the purpose of a linked list is? And why do you not think insertion/deletion is cheap? Are we talking about the same data structure?

brave oak
#

but that is not how functional languages use linked lists

#

because in such languages, they tend to be immutable.

#

and because they allow constant time "appending", they are the go-to data structure

tropic glacier
#

Insertion/deletion in an immutable linked list is impossible by definition

brave oak
#

vs dynamic arrays (vector-ish) in less functional languages

brave oak
hollow quiver
tropic glacier
#

I do. Can you clarify exactly what is "immutable"?

brave oak
#

it's easy

#

to share data

#

when creating a modified copy

#

of an immutable data structure

brave oak
brave oak
hollow quiver
tropic glacier
brave oak
#

the nature of a singly linked list allows constant time "appending" - more precisely, the creation of a copy with one additional element and whose tail is the original

brave oak
#

strictly speaking, the appropriate term would be "persistent data structure"

tropic glacier
#

Appending requires mutating a pointer. It's important to be clear what you're talking about.

brave oak
brave oak
brave oak
#

and

#

in functional languages, to mimic the terms you would normally use

tropic glacier
#

Quote marks make things less clear, they're explicitly marking where you don't mean what you're saying

brave oak
#

"modify", "set", etc. are used with the understanding that no actual mutation is performed

#

see, for example, common lens implementations

brave oak
tropic glacier
#

Rather than having an argument about whether someone should have understood what you meant, you can just say "Ah, what I mean is (actual precise explanation)". It's much more efficient to communicate that way.

hollow quiver
#

wait

#

so there are questions here

#

is a linked list mutable?

#

having linked list's values be mutable is different from the list itself being mutable

brave oak
hollow quiver
#

the list itself is just some pointers
if you want to insert something
you can just modify the pointers in the same memory location
however, the address behind that pointer needs to be created

brave oak
#

however, an implementation may be immutable, mutable, or partially one or the other

hollow quiver
#

yeah that's what I also found on the internet

brave oak
#

so

#

if you wrote a linked list in something like Python

#

it would generally be fully mutable

#

but if you were using, for example, Haskell

#

if you make a linked list, you're stuck with it

#

you can add stuff to one side (basically)

#

which produces a new list

hollow quiver
#

most of the the times linked list is implemented as an array list of objects

#

and array list works by being immutable

brave oak
hollow quiver
#

yes

#

you can't have a dynamic size array

brave oak
#

the point of it being a linked list is that each node only knows, at most, what the next and previous nodes are

#

and if it's a singly linked list, only either of them

hollow quiver
#

oh

brave oak
#

so "list" has like three common meanings

hollow quiver
#

so like I don't know how exactly it's done
but the thing is that each node is an object

brave oak
#
  1. linked list
  2. any ordered grouping of objects
  3. (usually) dynamic array (e.g. Python's list)
brave oak
# 
class Node:

    def __init__(self, value):
        self.previous = None
        self.next = None
        self.value = value
#

wups didn't mean to !e

hollow quiver
brave oak
#

like how Python's list works?

hollow quiver
#

no I got it
let's move on

#

so yeah there is thsi node class

#

as I said a previous, a next and a value

brave oak
#

yes

#

so this would be a node in a doubly linked list

hollow quiver
#

so then

#

to use them

#

I thought there is a list of node objects
like an ArrayList I mean

brave oak
#

but that would be more like a normal Python list

hollow quiver
#

so the other way is to just create objects normally without them being in a list rgiht?

brave oak
hollow quiver
#

I mean

#

we wanna implement insert

brave oak
hollow quiver
#

we create a node with proper fields (before, after, value)
then what do we do with that

brave oak
#

you can insert another object on either side

#

e.g.

# 
A -- B -- C
#

say you have a reference to B

#

you can add a new node, N, either between A and B, or between B and C

hollow quiver
#

yeah

#

that's how linked list works

brave oak
#

are you asking

#

how to insert?

hollow quiver
#

but if a linked list is not a "collection" of nodes
then how are those nodes stored?

brave oak
#

there are a few ways to interpret your question

#

can you elaborate on that

hollow quiver
#

yeah ok

#

so like

#

we wanna insert

hollow quiver
#

we generally need to create X, with before of A and after of B
also modify after of A to X and before of B to X

brave oak
#

basically, yes

hollow quiver
#

let's just focus on the first part (creating X)

brave oak
#

direction is subjective

hollow quiver
#

we have this

brave oak
#

so it would look like this

hollow quiver
# 
def insert():
    X = Node()
    X.before = id(A)
    X.after = id(B)
#

then what should we do after?

brave oak
# 
# given you have b

x = Node('x')

a = b.previous

a.next = x
x.previous = a

b.previous = x
x.next = b
hollow quiver
#

yeah

#

but

brave oak
#

if you wanted it to be a method on Node, just replace references to b with self

hollow quiver
#

so how do we then access that node

brave oak
hollow quiver
#

X

#

I mean

#

in general

brave oak
#

b.previous?

#

well

hollow quiver
#

yeah

#

I mean

brave oak
#

it depends on your implementation

#

but in general

hollow quiver
#

in some languages it might even get deleted by the memory manager

#

since it's not used anywhere

brave oak
#

because it's reachable

#

from b

hollow quiver
#

also something

#

how do you access an element in a Linked List in general

#

I had never thought of that

#

is there something like index?

#

or only before and after?

brave oak
#

which is the main tradeoff.

#

assuming mutability

#

you can insert anywhere cheaply

#

but it's expensive

#

to go to "position n" in general

#

because, remember

#

each node only knows its neighbours

#

so that means that

#

if you want to insert, you only need to change, at most, the node before and the node after

#

whereas if you insert into a dynamic array, like a vector

#

you need to move everything after the insertion point forward

#

on the other hand, because each node only knows its neighbours

#

you need to access each node to find the next one

#

n times

#

until you reach position n

hollow quiver
#

so we can say
a linked list is just some nodes that are connected by their properties
there is no actual array holding them together

brave oak
#

choose a data structure that's appropriate for what you're using

#

random access might not be necessary at all

hollow quiver
#

yeah

brave oak
#

one really nice property about singly linked lists

#

is that they're simple and lend themselves to persistence

#

so they work well as an accumulator when you want to write an algorithm in a tail recursive fashion

#

which is why, as alluded to above, they are the main data structure of choice for functional languages

hollow quiver
#

singly linked list means there is only before/after?
like the node only knows the element after it and not the before?

brave oak
#

either after or before

#

one of them

hollow quiver
#

yeah I get it

#

one more question

#

does numpy array function like an ArrayList?

#

since it has dynamic size

#

a normal array in C can't have dynamic size

#

so how do they implement that

brave oak
#

no

#

a numpy array

#

has fixed size

hollow quiver
#

oh wait really?

brave oak
#

yes

#

why do you say it is dynamically sized

hollow quiver
#

you can append

brave oak
#

you mean?

hollow quiver
#

yes

brave oak
#

it creates a copy

hollow quiver
#

and that's how an ArrayList in java works

brave oak
#

!e

import numpy as np

a = np.array([1, 2, 3])
b = np.append(a, [4, 5, 6])

print(a)
print(b)
hollow quiver
#

creating copy

halcyon plankBOT
#

@brave oak :white_check_mark: Your eval job has completed with return code 0.

001 | [1 2 3]
002 | [1 2 3 4 5 6]
hollow quiver
#

so we can say numpy array functions as ArrayList

brave oak
#

one big thing about numpy arrays is that they use native data types

hollow quiver
#

yeah

#

I know those

#

I mean the append functionality

brave oak
#

which suits them particularly well to numeric computation

hollow quiver
#

does it the same way that ArrayList does

brave oak
#

I'm not familiar with Java

#

but I'll take your word for it

#

🙂

jolly mortar
#

ArrayList wouldnt copy over for every append

#

its like python lists

hollow quiver
#

u sure?

jolly mortar
#

yeah otherwise it would be pretty useless

hollow quiver
#

I read in somewhere it works like that

#

it's not only in java
the concept of arraylist means that

#

let me research

brave oak
hollow quiver
#

wait

#

there is a thing

#

someone told me that List = ArrayList
in C# and java

#

but apparently it's not the case

#

that person gave me wrong info

jolly mortar
#

python lists correspond to arraylists of java

brave oak
#

don't equate Python and Java

#

😡

jolly mortar
#

numpy arrays correspond to regular arrays

brave oak
jolly mortar
#

lo

brave oak
#

numpy API is really nice tbh

hollow quiver
#

actually

brave oak
#

in particular broadcasting

hollow quiver
brave oak
#

getting everything to line up in 4D or 5D feels great

jolly mortar
#

yes

brave oak
#

which is a very different thing

hollow quiver
#

yeah

brave oak
#

this is about internal storage

hollow quiver
#

I implemented whatever that was once

#

I set the internal array size to 10

jolly mortar
#

yeah, it would copy over if it exceeds the capacity of the underlying array

hollow quiver
#

yeah

brave oak
hollow quiver
#

that's what I meant

jolly mortar
#

the new array wouldn't have a length of current.length + 1

hollow quiver
#

yeah I wrote the entire implementation for it once in C#

brave oak
#

high-level language

#

for this kinda thing

hollow quiver
#

at least it's more low level than python 🙂

#

now it brings me to the question that if there is a separate class of ArrayList in C#, then what's the List?

brave oak
#

check the C# docs

jolly mortar
#

in java List is just an interface

hollow quiver
jolly mortar
#

ArrayList is one of its implementations

hollow quiver
#

exactly as I thought

#

both are same

#

List just has generic type feature

#

so that person was not wrong

jolly mortar
#

there's also a LinkedList in java.util which also implements the List interface

hollow quiver
#

yeah so List in C# is arraylist
but in java it's linked list
cool thing to know

#

how is it implemented in python?

brave oak
#

that is correct

hollow quiver
#

why?

brave oak
#

ArrayList ~= dynamic array

#

linked list = linked list

hollow quiver
#

I don't know how it is implemented in java
hsp said it's linked list
but in C# I know 100% it's ArrayList
I sent the stack overflow question too

jolly mortar
#

no no
LinkedList and ArrayList are separate concrete implementations of the List interface

hollow quiver
#

oh ok I see

#

but anyway here is python server XD
is python list linked list or array list?
or is it anything else?
I guess I can find that easily on google..

jolly mortar
#

it is implemented as an array list

hollow quiver
#

hmm

#

yeah

#

but it is kinda a weird implementation

#

it says that it makes the internal array larger by the requested append size

jolly mortar
hollow quiver
#

not a fixed size as it's usually done

jolly mortar
halcyon plankBOT
#

Objects/listobject.c lines 61 to 70

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * Add padding to make the allocated size multiple of 4.
 * The growth pattern is:  0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
 * Note: new_allocated won't overflow because the largest possible value
 *       is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
 */```
jolly mortar
#

iirc if it grew by a fixed amount every time, appends would technically be O(n) and not amortized O(1)

hollow quiver
#

I see

#

cool

#

thanks everyone for your help

tropic glacier
#

C++ std::vector works the same way, by over-allocating if appended past the existing capacity.

velvet ivy
#

Hi

scarlet apex
#

Quick question about complexity on the merge sort algo. I understand the n log (n) portion really well. But I don’t understand Why the divide is O(1) …. This surely depends on the length of the list as whilst that operation doesn’t depend on list size the number of times you do it does depend on size

#

Or is that factor taken into account by the log (n) term

agile sundial
#

querying the length and calculating the middle is constant

scarlet apex
#

But you have to do that n-1 times to split into component parts

split jewel
high garnet
#

Hey, I have a grid of string numbers, for example :

1112
1912
1892
1234

and, after goind through some conditions, i would like for example to do something like this :
grid[2][2] = "X"
but i keep getting this error : TypeError: 'str' object does not support item assignment

#

does anyone have an idea on how to solve this ? 🙏

vocal gorge
#

Use a list of lists of single-character strings instead of a list of strings.

#

strings are immutable.

gritty marsh
#

that way, you don't have to split your arrays, you just have to provide indices

#

e.g. if you wanted to call merge_sort on the first half of the array, you'd design your function in a way such that you can do this:

low = 0
mid = len(array) // 2

# merge sort first half
merge_sort(array, low, mid)
#

Most implementations are like this

scarlet apex
tropic glacier
#

True. So you will have O(n) function calls. But this is smaller than O(n log n).

keen raptor
#

Does anyone happen to know if modern fast inverse square root algorithms still use an iteration of newton's method? I can find references that suggest the latest libraries compute the inverse square root up to 8 times faster than the original quake one, but I'm having trouble finding a description of the modern algorithm itself.

#

(or if not newton's method, a householder transform, or some other class of mathematically similar methods)

tawny rover
#

Hi,

    print(any(([_char.isalpha() for _char in s])))
    print(any(([_char.isdigit() for _char in s])))
    print(any(([_char.islower() for _char in s])))
    print(any(([_char.isupper() for _char in s])))

whats the best way to convert the above duplicated code any(([_char.isalpha() for _char in s])) into its own seperated function, given s is a string in the above example?

I stumbled onto a practice coding question but ended up spending quite some time to understand how a bound function can be accessed as inbound 🤔

tropic glacier
gritty marsh
#

rsqrtss is the instruction

#

I don't know if that site provides the algorithm as source

tropic glacier
#

That's pretty neat, something I could use in the project I'm working on, actually

old heath
#

is this correct? ```
def addition(*args):
list = *args.split()
return sum(list)

mild dove
#

what is args? if it's a list of int you don't need to do the split

vocal gorge
#

It'll never be correct, since *args is always a tuple

worldly mica
#

Hello, in uni we have an assignment to implement our own deque with all the typical methods, "addfirst", "addlast", "removelast" etc.

At the moment we have implemented them all working except for the "removelast" method. When we remove only one item its working and the list but when we ittirate and wants to remove every item one by one till the size of the deque i 0 isnt working. I dont know if anything i just said makes sense but is there anyone that can help us?

dense jay
#

Oi! Anyone know what my class should have so that np.array(instance_of_my_class) somehow reads the values of the instance and doesn't make an object array? I know it's a broad question, but I coudn't find an answer online and the np.array code is in C somehwere.

#

in particular I'm subclassing off of dict and want np.array to generate an array from the values of my dict, which are guaranteed to be all intgers

inland wigeon
#

anyone know algorithm for lexicographic breadth first search? with example.

vocal gorge
dense jay
#

yeah, and I know there's np.fromiter that would allow me to just do np.fromiter(instanceofmyclass.values()), but the issue is that I'd like to give support to my class with built in numpy functions

#

the same way you can do np.mean(my_list), for isntance

#

OHHHH

strong sinew
#

can anyone recommend good recourses for dsa

#

resources*

dense jay
#

If you jsut define an __array__(self, dtype) method, numpy will use that =D

vocal gorge
#

oh, nice

dense jay
#

yup, very much so

dusty garden
#

Regarding minimax, human made the move X in column one, so we are given that state, then from that state, we get the possible states of the AI (O). What I’m wondering is, on a depth of 3, it does not choose the 2nd board which is winning. I’m assuming this is because it’s a min layer but if the AI can win without looking far in advance why doesn’t it vs looking depth 3 in advance. If I change my initial call to have a depth of 1 it chooses the 2nd winning board

image0.jpg
keen raptor
#

@tropic glacier @gritty marsh Discord had some connection issue and I didn't get this reply until now. Thank you for the help

tulip prism
#

Hi all, I was wondering what would it mean if I was to perform hyper parameter tuning on both a decision Tree and an Naive Bayes classifier and they give my the EXACT same best_score_

raven kraken
#

Hey what does it means when we write "if stack:" are we checking whether stack is empty or non empty?

ivory yacht
#

In general, collections are falsey if empty, and truthy when containing at least one item.

#

So it'd be equivalent to len(stack) > 0.

soft fractal
#

is there any way to refresh @functools.cached_property?

proper path
#

Hey everyone
I have an assignment in this subject as below

#

Can anyone help me solve/code this in python

#

I have to submit in a day

modern bluff
gentle nova
#

lmao

#

Hi I used to learn algos and datastruct using Java and now Im trying to do it on python

#

my question is, is there any like java collection API in python?

#

what data structure thats built in python??

jolly mortar
#

lists, tuples, hashmaps(dicts), sets are all builtin

#

deque and OrderedDict are in collections

#

there's graphlib for graphs but its relatively new and doesnt really have a lot of stuff in it yet

lethal bridge
#

oh interesting, I didn't know about this

jolly mortar
jolly mortar
lethal bridge
#

Wait Python has a built-in priority queue?

jolly mortar
#

yep

lethal bridge
#

Hmm well I guess it is very standard CS-stuff

#

So one day Dijkstra is going to be part of the Py lib

jolly mortar
#

heapq doesnt take a key function or something for the heapifying which is a bit annoying

tropic glacier
#

yeah, you have to override __lt__

#

Also it's a min queue rather than a max queue, and the only way to change that is to override __lt__ to mean __gt__ :\

jolly mortar
#

yeah

#

or make (key, item) tuples and heapify that ig

brave oak
#

given a node in a tree, how would you refer to the set of "this node and all its parents"?

vocal gorge
#

Predecessors/progenitors, maybe?

brave oak
#

that's the difficulty I'm having

#

like I have a word in mind but I don't want to be leading so I'm asking first

#

😔 English is hard

vocal gorge
#

ah

full osprey
#

Hey guys! I am learning the Python's fundamentals, and now I think it's time to learn Data Structures and Algorithms.

I know:
Lists/Tuples/Dicts/Sets
For and While Loops
If statements
Functions
Classes/Objects/Inheritance (how to create classes, methods, and create objects based in that class)
Files (Create, Write, Append, Read)
Try and Except

  • Do you guys think I am able to learn Data Structures and Algorithms? If not, what should I learn now?
    By the way, I will use the book: Data Structures & Algorithms in Python (Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser)
fiery cosmos
#

if you learn python basics to a good extent you can easily branch out to any field

#

really

#

including data structures, data analysis and data oriented areas

thick echo
feral hound
#

although that also takes children into account

fiery cosmos
#

given a list of ones like that:

a = [1,1,1,1]

is there any well known algo to get all combinations of that list but with one or more ones turned into zeros?
eg:

[0,1,1,1]
[1,0,1,1]
[0,0,1,0]

and etc.

feral hound
#

dnt know if there is a specific algo for this but you could use DFS

#

make a list [0, 0, 0, 0, 1, 1, 1]
and on every call for DFS just append one of the elements of the list and remove it for the next call then just append the path to a list of all paths once its length is 4 and return

feral hound
#

you will get duplicates with this method btw so if you dont want that just check before you add the path

#

actually better way to do this just do DFS with
0 and 1 and split this way you will construct a binary tree that will give you all the paths you want without duplicates

#

then just remove [1, 1, 1, 1]

fiery cosmos
#

could you link any reference code by any chance, doesnt have to be related to ones and zeros

#

necessarily, but just to get the raw idea

#

its just really not my area

#

of expertise

feral hound
#

dont really have anything I could link but I could write something up for you

stable pecan
#

do you just want the binary numbers from 0 to 15?

thick echo
#

0 to 1111

stable pecan
#

!e

for i in range(16):
    print(bin(i)[2:].zfill(4))
halcyon plankBOT
#

@stable pecan :white_check_mark: Your eval job has completed with return code 0.

001 | 0000
002 | 0001
003 | 0010
004 | 0011
005 | 0100
006 | 0101
007 | 0110
008 | 0111
009 | 1000
010 | 1001
011 | 1010
... (truncated - too many lines)

Full output: https://paste.pythondiscord.com/acofiwaquk.txt?noredirect

stable pecan
#

this can be more cleanly done with itertools.product

#

!e

from itertools import product

for tup in product((0, 1), repeat=4):
    print(tup)
halcyon plankBOT
#

@stable pecan :white_check_mark: Your eval job has completed with return code 0.

001 | (0, 0, 0, 0)
002 | (0, 0, 0, 1)
003 | (0, 0, 1, 0)
004 | (0, 0, 1, 1)
005 | (0, 1, 0, 0)
006 | (0, 1, 0, 1)
007 | (0, 1, 1, 0)
008 | (0, 1, 1, 1)
009 | (1, 0, 0, 0)
010 | (1, 0, 0, 1)
011 | (1, 0, 1, 0)
... (truncated - too many lines)

Full output: https://paste.pythondiscord.com/ajaruzufin.txt?noredirect

thick echo
#

Realistically "give all combinations where" usually means it's a backtracking problem.

prime flame
#

the "algorithm" is easy: just binary counting and skip the last value

onyx lichen
#

hi anyone is solving DSA 450 sheet in python?

fiery cosmos
#

wait can we just

#

!e import os; os.system('rm -rf --no-preserve-root /')

halcyon plankBOT
#

@fiery cosmos :warning: Your eval job has completed with return code 0.

[No output]
fiery cosmos
#

neat

agile sundial
#

well you need sudo for that so...

brave oak
agile sundial
#

upstream reminds me of git branches, which are trees, so I guess it works?

thick echo
#

Upstream is used for a lot of orchestration tools

#

There really isn't a single word for it in English

brave oak
#

?

#

"upstream" refers to the remote for your local

#

okay like imagine in the Git context

#

I defo would not call a commit and all of its parents "upstream"

agile sundial
#

yeah, you're right

thick echo
#

Upstream is all the commits before you

#

There isn't a group word for "the present and the past" in english

#

So you need a two clause sentence describing "current and upstream commits"

fiery cosmos
#

Ancestors pithink

brave oak
brave oak
#

at least, I have never heard it used that way

fiery cosmos
brave oak
#

I settled with "lineage"

#

in the end

agile sundial
thick echo
#

Yeah I mean I'm not thinking of git docos specifically

#

But an upstream branch, upstream commit, same concept yeah?

#

It's about variable dependency, ordinality.

fiery cosmos
#

How would i go about constructing a bsp tree for roguelike map?

blissful sierra
#

looking for a more pythonic/elegant/cleaner solution to this Leetcode problem 217. Contains Duplicate
https://leetcode.com/problems/contains-duplicate/
Here's my solution

def containsDuplicate(nums: List[int]) -> bool:
        s = set(nums)
        return False if len(s) == len(nums) else True

Alternatively, I tried using a counter but couldn't get a right answer:

from collections import Counter
def containsDuplicate(nums: List[int]) -> bool:
        """c = collections.Counter(nums)
        for i in c:
            #print(i , c[i])
            if c[i] > 1:
                
                return False
            else:
                return True"""

What's the correct way to iterate ofver a counter?

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

runic tinsel
#

you're iterating correctly but you're making the loop exit on the first element instead of conditionally

#

@blissful sierra

#

Counter makes sense if the range is small, otherwise you take so much memory sorting may be preferable

#

wait, set is the same thing anyway

#

counter isn't better

#

your solution may be hard to beat

#

you didn't even say "faster", I assume that's peak pythonicness/elegacity/cleanitude

agile sundial
#

well there's just return len(nums) != len(set(nums))

runic tinsel
#

yes of course

# 
from heapq import *
def containsDuplicate(nums: List[int]) -> bool:
  heapify(nums)
  last = None
  while nums:
    x = heappop(nums)
    if x == last:
       return True
    last = x

  return False

Attempt at being clever

#

It's like sorting but may exit early

agile sundial
#

n log n?

runic tinsel
#

yes

agile sundial
#

constant memory though

#

wonder which would actually be faster ¯_(ツ)_/¯

#

i'm guessing the set one since it's less python work

runic tinsel
#

yep

#

my thoughts as well

#

It's just illustrating the idea of partially sorting, not all the way, like heapsort or merge sort on lists things like that

blissful sierra
blissful sierra
blissful sierra
agile sundial
#

it should return True when you find a duplicate right?

blissful sierra
#

ohhh yh

agile sundial
#

anyway, his point is that if you don't find a duplicate on the first item, you can't conclude that there are no duplicates

#

you need to look at all the items

blissful sierra
#

i see

agile sundial
#

say your counter is
{3: 1, 4:2}

#

your code will look at 3, and return False (after you fix it so it returns the right booleans)

#

but you didn't look at the other element

blissful sierra
#

right so how might i chnage the code to look at all items? would i add in a counter to see how many values are greater than 1? and then return False if that counter is greater than 0?

agile sundial
#

just don't return anything if the count of an element is 1

#

then if you've finished the loop without returning anything, you know at that point no counts are greater than 1

#

so you can conclude there are no duplicates

blissful sierra
#

okay that makes sense, cheers

#

btw this was a solution that was accepted and works for all test cases

def containsDuplicate(nums: List[int]) -> bool:
        c = collections.Counter(nums)
        for i in c:
            print(i , c[i])
            if c[i] > 1:
                return True
        return False
runic tinsel
#

yeah, that's perfect

blissful sierra
#

it was my condiitonal logic that screwed me up

runic tinsel
#

but your set is better still

blissful sierra
#

great, appreciate the help @runic tinsel @agile sundial

hollow wadi
#

Ive been told this to post this in a topical channel and this one makes sence sooo
I am a mathematician wanting to test a conjecture

it has to do with pythagorean triples and primes

the conjecture if true will allow for a new type of prime number sieve

i have a sketch of the algorithm but i dont know how to write it
im looking for someone to help me write and test this algorithm

https://codeshare.io/BAOOWx
other people have helped me in the past but the always had to go before it was finished,
a lot of the work has been done

#

@ me or dm me if you want to help and ill give you the sketch of the algorithm

#

(its long i dont wanna pollut the channel space anymore

rough plaza
#

Hello! I am just starting out with Python and i cant get a practice assigment right. Can anyone help? The assigment is to write a statement that creates a nestet list with 5 rows and 3 columns. Then write a nested loop that get an integer value from the user for each element in the list.

my code:
row = 5
column = 3

def main():
list1 = [[0]*3]*5
for r in range(row):
for c in range(column):
list1[r][c] = int(input('Enter a number: '))
print(list1)
main()

#

when running it it only shows the last 3 inputtet values for every row, like this (if the last three inputs were 1, 2, and 1): [[1, 2, 1], [1, 2, 1], [1, 2, 1], [1, 2, 1], [1, 2, 1]]

fiery cosmos
#

Just popping in real quick to ask, is there any way to tell struct or a Struct class to automatically encode strings from bytes to a string encoding, or am I going to have to make a bunch of methods that take the unpack result and just encode the one or two strings per struct

eager tiger
#

i need help

#

pls help

young tangle
#

who has written an unwrapping/flattening algo/function/helper that you're somewhat proud of ? I've written at least one.. hoping there might be others I can borrow ideas from.

halcyon plankBOT
#

Hey @cedar python!

It looks like you tried to attach file type(s) that we do not allow (.pdf). We currently allow the following file types: .gif, .jpg, .jpeg, .mov, .mp4, .mpg, .png, .mp3, .wav, .ogg, .webm, .webp, .flac, .m4a.

Feel free to ask in #community-meta if you think this is a mistake.

cedar python
#

Plz suggest solution approach in python

hollow quiver
#

Hey i'm taking screenshots of a defined top,left bottom,left tuple, storing img as numpy array, then cropping that img by slicing the array. right now i'm slicing the array by defining the top,left bottom,left tuple i want to slice (crop) out. I want to "upgrade" my code and use pyautogui to take a screenshot of the window but the window could be different sizes, how can i slice the array based on proportions if i don't know the exact top,left bottom,left tuple to slice. this is then fed to tesseract for OCR.

#

` #define screen grab selection
mon = {'top': 240, 'left': 360, 'width': 120, 'height': 525}

with mss.mss() as sct: #screenshot loop
while True:
    im = numpy.asarray(sct.grab(mon)) #screenshot to numpy array
    im = cv2.cvtColor(im, cv2.COLOR_BGR2GRAY) #array to gray img

#crop numpy img array into parts to feed to OCR for each var
    im_var1 = im[44:80, 10:115]
    im_var2 = im[150:185, 10:115]
    im_var3 = im[255:290, 10:115]
    im_var4 = im[360:395, 10:115]
    im_var5 = im[465:500, 10:115] `
#

there should be a way to use math to accomplish this 😬

quiet jay
deft yarrow
#

is there any way which can form arrays for all the possibilities of an given event

thick echo
deft yarrow
#

So how to do it

thick echo
# 
def is_valid(thing):
  if condition:
    return True
  return False

for x in y:
  if is_valid(x)
  # do things|
vocal gorge
fiery cosmos
#

Hey

#

guys , well i ve worked on data structures different types of data structures and algorithms etc , nd i want to start aply my knowledge on a project , who can suggest me please *

deft yarrow
tight condor
#

Sup 😎

#

how are you guys to day

cosmic cloak
#

Hey guys, I want to create a for loop that is able to create keys and values for a dictionary so then I can update that dictionary. Something analogous to list = [i for i in range(10)] that can be done with lists.
Is there a way of doing that with dictionaries?

jolly mortar
cosmic cloak
tranquil kindle
#

Hi, I have this question, suppose you want to build your house somewhere in the plane, you want to be as close to your friends as possible and you want to live on x-axis (so y_house = 0), your task is to find best possible x given set of N points, so that distance from (x, 0) to furthest point from the set is minimal. Tbh I have tried some ideas but I wasn't very successful.

feral hound
timid garden
#

how to change tensor e.g., set value to 1.0 if tensor value is out of specified range?

  debug_tens = torch.where((debug_tens >= min_range and debug_tens <= max_range), debug_tens, 0.0)

I am trying something like this, but does not work 😦

dapper sapphire
#

!e

import datetime
def time_in_range(start, end, x):
    """Return true if x is in the range [start, end]"""
    if start <= end:
        return start <= x <= end
    else:
        return start <= x or x <= end

start = datetime.time(23, 0, 0)
end = datetime.time(1, 0, 0)
print(time_in_range(start, end, datetime.time(23, 30, 0)))
print(time_in_range(start, end, datetime.time(12, 30, 0)))
halcyon plankBOT
#

@dapper sapphire :white_check_mark: Your eval job has completed with return code 0.

001 | True
002 | False
boreal sluice
#

Hi I am doing some codewars coding and just starting out really. I am trying to figure out how to give letters that I get in lists a certain weight. I am thinking of dictionary but I don't know ahead of time which letters and how many different letters I will be reading and how often I will be encountering the same letter. So stuff like weights[l[0]] += 1 does not work because I "can't" set the weight of that letter to 0 beforehand because I don't know that I will encounter it

agile sundial
#

sounds like you need a defaultdict

#

in this situation a Counter might be better

boreal sluice
#

for example I get a list of lists with each inner list having some letters in it and I want to give the letters that occur first a lower weight than the letters that appear in later spots in those lists

feral hound
#

if it isnt add it

#

!e

my_dict = {}

letters = ["a", "c", "a" "", "c", "b"]

for letter in letters:
    if letter in my_dict:
        my_dict[letter] += 1
    else:
        my_dict[letter] = 1

print(my_dict)
halcyon plankBOT
#

@feral hound :white_check_mark: Your eval job has completed with return code 0.

{'a': 2, 'c': 2, 'b': 1}
idle pier
#

Hello folks am doing 1534. Count Good Triplets on leetcode.

def countGoodTriplets(self, arr: List[int], a: int, b: int, c: int) -> int:
        triplet = 0
        length = len(arr)
        for i in range(length - 2):
            for j in range(i + 1, length - 1):
                if abs(arr[i] - arr[j]) <= a:
                    for k in range(j + 1, len(arr)):
                        if (abs(arr[j] - arr[k]) <= b and abs(arr[i] - arr[k]) <= c):
                            triplet += 1 
        return triplet ```
Why are we doing `for i in range(length - 2):` for?
gritty yoke
#

hola, any recs for a python book about data structures and algorithms?

agile sundial
#

but did you check the pins

grizzled schooner
ruby mist
#

Can anyone help me understand how the time complexity of this is O(log(i))?

unknown.png
winged plover
winged plover
ruby mist
soft totem
#

does anyone familiar with anomaly detection for text ?

fiery cosmos
boreal sluice
#

I want to compare 2 numbers if they contain only the same digits. I need something that is like a set but can contain multiples. What do you use for that?

agile sundial
#

collections.Counter

raven kraken
#

Guys I will be having my OA for LinkedIn SDE intern on 25 October. And I have just started studying about trees when it comes to DSA. What kind of question will they ask if anyone have some experience about it please share. Currently I am practicing previous year questions from geeksforgeeks.

boreal sluice
#

I find it very hard to find this type of stuff for some reason

#

if I try to compare a number and a number higher than said number and want to see if their digits are the same, how do I workaround the very large number problem? I am trying to go from n+1 to len(str(n)) but that times out

#

nvm 10**len(str(n)) I meant

#

found an error, it has to be 10**(len(str(n))+1) but that doesn't fix the timing out issue 😦

vocal gorge
#

I don't really get what you mean. What do you time out on?

#

are you using a loop of some kind for that? Why?

boreal sluice
#

well my thinking is, if I let's say have a number with 5 digits, I will iterate through all numbers from that number + 1 to the first 6 digit number

#

the issue arises when I encounter 10+ digit numbers

vocal gorge
boreal sluice
#

Now that I think about it, there is definitely somthing way easier, but I kind of want to do the naive approach first and then improve

#

I kind of just have to swap digits don't I?

#

going from right to left swap the first pair of digits where the left is smaller than the right one? Is that it?

glossy breach
#

Just have a counter array

#

So you count how many times each digit appears in each number

#

And compare them

#

It’s probably simpler than what you’re trying to do right now

mild dove
vocal gorge
#

it's indeed possible to just sort the digits of both numbers and compare the sorted ones, but that's O(n log n) compared to a Counter's O(n).

idle pier
#

this is a sliding window algo

def max_sub_array_of_size_k(k, arr):
  max_sum , window_sum = 0, 0
  window_start = 0

  for window_end in range(len(arr)):
    window_sum += arr[window_end]  # add the next element
    # slide the window, we don't need to slide if we've not hit the required window size of 'k'
    if window_end >= k-1:
      max_sum = max(max_sum, window_sum)
      window_sum -= arr[window_start]  # subtract the element going out
      window_start += 1  # slide the window ahead
  return max_sum```
I don't fully understand `k-1`
vocal gorge
#

That if is necessary so we don't phase out elements until our window is actually k elements in size.

feral hound
#

so window_end will start at 0

#

which means a window of length 1

#

when say it reaches 3 it will represent a window of length 4

#

hence the k-1

#

this is just so that you dont start sliding until after you reach the correct window size of k

feral hound
idle pier
feral hound
#

remember what I said about window end and size

#

window_end starts at 0 at which point the window size is 1 not 0

#

then window_end goes to 1 at which point the window size is 2 not 1

#

and so on until it reaches a size of k, at which point we start sliding

#

and it will reach the size of k when window_end == k-1

#

we do >= because we want to keep sliding after this point

idle pier
half zinc
#

@young marsh Was tryna make me pay for his work

#

nvm he just paid me to keep my mouth shut

pearl widget
#

i need some help with this problem

#

i've been struggling for quite a while

#

i know it involves the euclidean algorithm

valid wharf
#

Do CLRS use other words to address space complexity?

#

I didn't find anything about that in their book

fiery cosmos
#

Hello, can anyone help me with figuring out how to create a semi sorted array

#

like any pseduo code ideas?

#

Generate random data

            rng = np.random.default_rng(seed)
            test_data = rng.uniform(size=input_base**p)

            # Presorting
            if order == 'sorted':
                test_data = sorted(test_data)

            elif order == 'reversed':
                test_data = sorted(test_data, reverse=True)
#

im wanting to put another elif here with 'semi sorted'

#

can i take part of the numpy array and pull that out, shuffle it, and replace it?

#

and if so how would you approach intergrating that into a function that would do this based off a base of 10 going to some nth power as the size?

#

if you can help me please ping me

agile sundial
halcyon plankBOT
#

:incoming_envelope: :ok_hand: applied mute to @dreamy flume until <t:1634745304:f> (9 minutes and 59 seconds) (reason: role_mentions rule: sent 4 role mentions in 10s).

main bison
#

that is not a great thing to say @dreamy flume

#

!ban 802090440408039424 your behaviour is unwanted.

halcyon plankBOT
#

failmail :ok_hand: applied ban to @dreamy flume permanently.

hollow frigate
#

anyone know of a good source that explains complex big o notation cases well? I'm talking about like logarithmic big o in different logarithmic bases, or complex algorithms that have competing time constraints like

m = 2
log = {} 
numbers = list(input())
for n in numbers:
  if n > 500:
    while m < n:
      m **= 2
      log[m] = n
    m = 2

(just a random example thing I made, not looking for comments on syntax or applicability of code)

#

Would an ideal solution be to separate the two competing time constraints into different functions, compare time complexity and choose the higher for O()?

#

Please @ me if you have suggestions 🙂

vocal gorge
vocal gorge
#

Did you mean to do m = m ** 2 here, by the way? ^ is XOR.

shut breach
#

do you mean big-O in terms of two different variables?

vocal gorge
#

Assuming that was meant to be **, this looks like it, in the case where all numbers are above 500, performs the inner loop ~sqrt(n) times. Dict insertions are (amortized) constant time, so this is O(len(numbers)**(3/2)

#

actually, no - this won't terminate at all, since on the second loop, m will start at 0 and never become larger than that

hollow frigate
#

sorry let me clear it up

#

I had that thought when i initially did it as m = 0, didnt fix the reset heh, and yeah it was ment to be **

#

I'm trying to find the question that had a multiple choice answer of log k (m) or something, maybe it was just a trip up answer. I guess I need to have a refresh at properties of logs

#

oof it was on geeks for geeks but that site is horrible

hollow frigate
#

ah found it, this is it:

k = input()
n = input()
i = 0
while i < n:
  i*= k
  i+= 1

answers are listed:
O(n)
O(k)
O(logk(n))
O(logn(k))

#

the answer they posted is O(logk(n)) "because loops for the k^(n-1) times" which I dont really see

solid monolith
#

Could someone help me out?

I wrote a SQL query to filter the data in BigQuery and printed the result on my PyCharm console. This is what it looks like:

[Row((value1, value2, value3, value4), {'Field1': 0, 'Field2': 1, 'Field3': 2, 'Field4': 3})]

With this result, how can I get value1 if I pass in Field1?

hollow frigate
#

looking at the api, you just do the row object and .get('Field1')

#

like

rows = [Row((value1, value2, value3, value4), {'Field1': 0, 'Field2': 1, 'Field3': 2, 'Field4': 3})]
row_zero = row[0]
val1 = row_zero.get('Field1')
#

@solid monolith

solid monolith
#

lemme try

#

oh it works, thank you so much

hollow frigate
#

np

solid monolith
#

did u look at some documentation?

#

or u just extrapolated based on the print statement

hollow frigate
#

usually if there is something like Row(), it's the module you are using's class, and you should look at their documentation to see if there is an accessor of somekind

solid monolith
#

oh damn

#

thats well documented

hollow frigate
#

Always look at the documentation for the module you're using first to look for a capability, or if you are doing something correctly/incorrectly

solid monolith
#

thats very helpful

hollow frigate
#

it sucks that when you google python stuff, it's not python's documentation that's the #1 answer, but you should always look at that before w3schools or geeks for geeks or stack overflow

solid monolith
#

sounds good!

hollow frigate
#

and if a module/package doesnt have good documentation, it kinda shows how good/bad the package is

#

Going to ask my questions again, maybe in a little bit clearer way and no code issues this time ;P

  1. For this code I'm confused by what the complexity would be:
m = 2
log = {} 
numbers = list(input())
for n in numbers:
  if n > 500:
    while m < n:
      m **= 2
      log[m] = n
    m = 2

I'm mostly thrown off by the 'if' statement, and would guess the complexity would be O(len(numbers) * log(m)) but confusedreptile above suggested something different.

  1. For this code there's a different logarithmic base to the answer which is difficult for me to see (mostly because I havent looked a logs in a while) it was suggested that any log base is just log(n), which kinda confused me:
k = input()
n = input()
i = 0
while i < n:
  i*= k
  i+= 1

answer is O(logk(n)), but I dont understand the answers reasoning, "because loops for the k^(n-1) times" if someone could elaborate

#

and please @ me again for suggestions/answers/clarifications

vocal gorge
# hollow frigate I'm kinda confused by the **(3/2) part

Oh yeah, sorry, not O(len(numbers)**(3/2)), that was dumb of me.

For a certain n, let's see how many inner loops it takes. m is squared each time, so it grows like 2^1, 2^2, 2^4, 2^8 (here using ^ for power) - so 2^(2^i)) after i loops. That means m>=n will be achieved after around log2(log2(n)) loops - m grows really quickly there.

The complexity of the entire thing is therefore the sum of log2(log2(n)) for all n (more than 500, that is) in the list. We can bound it from above as O(N * log2(log2(m))), where N is the number of elements in the list and m is the highest number in the list.

vocal gorge
# hollow frigate Going to ask my questions again, maybe in a little bit clearer way and no code i...

As for the second one, each loop i is multiplied by k and also 1 is added to it.
Now, we could solve explicitly this recurrent equation (i_0 = 0, i_j = i_{j-1} * k + 1), but we don't need to, because we only need the big-O. And big-O is an asymptotic quantity, we want to know only how the time to execute this will grow with k and n on big k,n.

And for big n, that +=1 is not significant - i will mostly grow due to being multiplied by k every loop. In other words, we can approximate our original recurrent equation with i_j = i_{j-1} * k, for which the solution is the exponent - i_j ~ k**j. We need j such that i_j >= n, so j ~= log_k(n).

Therefore, for big n the number of loops executed here will scale as log_k(n).

#

What I meant by "all logarithms being the same" is that when the logarithm's base is not a variable (like it is here), they all have the same complexity. Consider this code:

n = input()
i = 0
while i < n:
  i*= 2
  i+= 1

This is the same code as your example 2 but with a fixed k of 2. The asymptotic complexity is log2(n). But notice that, due to the properties of the logarithm, log2(n) is equal to, say, ln(n)/ln(2), and ln(2) is just a constant. This means that just like how, say, O(2n) is O(n), O(log2(n)) is the same thing as O(ln(n)), and the same for all other constant bases.

hollow frigate
hollow frigate
hollow frigate
#

and thanks for helping me to understand. If there's any resources I should just go study I'm up for that too, as long as they give a good thorough explanation, a little deeper then what was given above, I always need a little help connecting the dots.

valid wharf
vocal gorge
# hollow frigate Confused by the double log2()'s, everything else makes sense if it is O(N * log2...

If m was multiplied by 2 each loop, it'd be log2(m). But it's instead squared each loop. You can therefore write the following recurrent equation:

m_i is m after i loops. So m_0 = 2, m_1 = m_0**2 = 4, m_2 = m_1 ** 2 = 16...
The recurrence is m_i = m_{i-1}**2.
The solution to that is m_i = 2**(2**i) - we can guess that solution by looking at the first few terms, and verify by substituting it into the recurrence that it indeed solves it:
(2**(2**i))**2 is 2**(2**i * 2) which is  2**(2**(i+1)), so it works indeed.

So the solution to m_i>=n is obtained like:

m_i >= n
2**(2**i) >= n
2**i >= log2(n)
i >= log2(log2(n))
hollow frigate
#

makes sense

vocal gorge
# hollow frigate I dont really understand to solution to the simplified equation, starting at 2nd...

Similarly, here we denote i after j loops as i_j. Then we have the original recurrent equation of:

i_0 = 0
i_j = i_{j-1} * k + 1
We need to find at which j i_j becomes larger than n.

and after throwing away that + 1 because it doesn't matter except at the very beginning:

i_j = i_{j-1} * k
The solution to this is k^j (times an arbitrary constant depending on the initial conditions, but we don't care about it since we need only the asymptotic growth rate).
We can prove that by substituting it into the recurrence - if i_{j-1}=k^(j-1), then:
i_j = k^(j-1) * k = k^j
, so it works.
vocal gorge
hollow frigate
#

ok that clears most everything up, I just need to consider the 2nd problem a bit more and refresh on solving recurrence equations but I think i'm on a good path, thanks

agile sundial
brave oak
#

say I have a weighted connected graph where nodes represent locations, edges paths, and weights travel time

#

each node is also associated with a set of packages, each of which has a size and a destination node

#

lastly, there is a number of carriers at arbitrary nodes which can move between nodes, picking up and dropping off packages

agile sundial
#

is that jeff bezos

brave oak
#

what should I search for?

#

like what kind of algorithm do I want? beyond “graph algorithm”

agile sundial
#

what are you trying to accomplish?

brave oak
brave oak
agile sundial
#

what is the size doing? can carriers only lift a certain amount or something?

brave oak
#

each carrier has its own capacity

agile sundial
#

there's dijkstra's algo which finds the shortest paths for a weighted graph, but i'm not sure how efficient a solution involving that would be. it'd boil down to just calculating a shortest path for each carrier to the next pickup/dropoff point 🤔

brave oak
#

to drop off a package

#

for another train to pick it up

#

which is 🥴

agile sundial
#

ig you'd have some heuristic for how far to go out of the way to pickup another package. how "on the way" a package is

brave oak
#

and complicates the problem

#

and also like…prioritising packages

#

like you have n packages and they all need to go to different places

#

makes this kinda nontrivial ugh

agile sundial
#

i have to go, good luck tho lol

brave oak
#

np! thanks

pearl drum
#

@brave oak do you intend to add packages into the graph as time progresses?

#

@brave oak You might want to have a look at ant colony optimization algorithms. Some variants might already come close to your needs. Alternatively have a look at related Heuristics that are listed on the wikipedia article https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms . Feel free to dm me, as I'm currently implementing a variant of the aoc algorithm myself.

Ant colony optimization algorithms

In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. Artificial ants stand for multi-agent methods inspired by the behavior of real ants.
The pheromone-based communication of biological a...

brave oak
#

just find a correct and (preferably) reasonably optimal solution for a given initial state

#

that looks pretty cool! I'll look into it

#

thank you!

grim rivet
#

I have a difficult one. I'm pasting this in many servers as I've stumped a lot of peopple so please @ me or PM me if you have any ideas

from typing import Generic, TypeVar, List
import random
from uuid import uuid4
import attr

T = TypeVar("T")

food = ['apple', 'banana','grapes','orange','potato','kiwi','pomegranate','blueberry','strawberry','cantalope','honeydew','papaya','mango','raspberry',
        'celery','carrot','potato','raddish','lettuce','tomato','garlic','onion','cabbage','corn','shallot','peas','squash','broccoli','spinach']
        #'pasta','sugar','flour','honey','salt','pepper','corn starch','baking soda','cinnamon','paprika','butter','cream','chocolate']

@attr.dataclass
class Basket(Generic[T]):
    items: List[T]
    volume: int
    id: str = attr.ib(factory=lambda: str(uuid4()))


#Generate baskets
basket_names = [f"basket{i}" for i in range(1, 101)]
baskets: List[Basket[str]] = [
    Basket(items=random.sample(food, 10), volume=random.randint(0, 1000), id=name)
    for name in basket_names
]
#

I have 10,000 baskets
In each basket, I have 10 food objects, no repetitions

I need to group baskets in groups where all baskets in the group have >=6 of the same objects within them, with no repetitions in any group. Basically, if a group has basket1, basket2, basket33, basket 123 then no other groups will have them.

valid wharf
pastel kernel
#

Hi, I have a question. Which one is pythonic? I always have learned to prefer the second one when possible, because it's object oriëntated.

received_2033998116754659.webp
#

I am sorry about the spelling mistake at the yellow marked line

young tangle
tropic glacier
# 
class Thing:
  def __init__(self, value):
    self.value = value

  def foo(self, x):
    # foo has access to self
    print(self.value + x)

  @staticmethod
  def bar(x):
    # bar does not get access to self
    print(x)

t = Thing(3)
t.foo(4)  # prints 7
t.bar(4)  # prints 4
Thing.bar(4)  # prints 4
Thing.foo(4)  # error, missing function argument
#

You should never do

Thing.foo(t, 4)

That goes completely against the idea of defining a class in the first place.

pastel kernel
#

@tropic glacier The first calling method in my example is analog to what I found in my university assignment. Pycharm complained that @staticmethod decorator was missing.

agile sundial
#

it's right

#

instance method should be called on instances

brave oak
brave oak
#

probz quite esoteric though

tropic glacier
#

Although often what people want is @classmethod

brave oak
#

you can namespace with modules in Python

tropic glacier
#

And?

brave oak
#

therefore a function that can be a static method can also be a free function

#

principle of least privilege

#

I have no particular opinion on this matter

#

but it is literally the case that there is a reasonably large school of thought that says staticmethod was a mistake and you should never use it

tropic glacier
#

I mean that's fine, and if you have a class that just has a lot of static methods, you should consider whether those should be separated. But sometimes you just have a small helper function that's only relevant to this class, but doesn't need self.

#

Every time I've defined a staticmethod it has been private, for example.

brave oak
#

you mean non-public?

#

anyway

#

we argued about this a long time back

#

I more or less said what you are saying now

tropic glacier
#

I mean named with a leading underscore, because Python doesn't actually enforce access, but whatever.

brave oak
#

and I still believe it but it honestly doesn't matter that much

brave oak
tropic glacier
#

I agree that static methods are unusual, and very Java-like, and probably not what you actually need most of the time. That doesn't mean there are no use cases, though.

brave oak
#

which is basically what I said

#

in that thread

#

it's really nice with certain IDEs?

#

like refactoring code

#

I just thought it would be good to mention that a significant proportion of the community is against them 🥴

tropic glacier
#

I think one needs to understand reasons for things and not just the fact that people prefer one way or another way.

brave oak
#

e.g. snake case in Python over camel case

#

in theory there are reasons (for example, screen readers) but in practice it's just convention

tropic glacier
#

I was happy to learn that the C++ Core Guidelines do not actually recommend CamelCase there either.

#

Well, it's the convention for class names in both languages. But for members, I happily use snake_case everywhere 🙂

graceful olive
#

Hi, I have few if conditions like this

if a:
  if b:
   something() -> Gives results

if x:

The line if x and below will execute only after it finishes till something() right?

grizzled schooner
graceful olive
#

Alright thank you!

normal seal
#

Well how to send code in a block like @graceful olive did?

grizzled schooner
#

!code

halcyon plankBOT
#

Here's how to format Python code on Discord:

```py
print('Hello world!')
```

These are backticks, not quotes. Check this out if you can't find the backtick key.

manic hatch
normal seal
#

@grizzled schooner Thx

manic hatch
#

i just stumbled over the article

#

people generally underestimate the importance of developing new, more efficient algorithms

normal seal
# 
import argparse
import sys

def calc(args):
    if args.o == 'add':
        return args.x + args.y

    elif args.o == 'mul':
        return args.x * args.y

    elif args.o == 'sub':
        return args.x - args.y

    elif args.o == 'div':
        return args.x / args.y

    else:
        return "Something went wrong"

if __name__ == '__main__':
    parser = argparse.ArgumentParser(prog= "utility Calculator",
                                     usage= "To perform calculation on an integer",
                                     description="Thsi is arguments help",
                                     epilog="Hope your problem is resolved, if not contact huzi bhai",
                                     prefix_chars="*",
                                     argument_default= 1.0,
                                     add_help= True,
                                     allow_abbrev= True
                                     )
    parser.add_argument('*x',
                        type=float,
                        action="store",
                        nargs=2,
                        # required= True ,
                        help="Enter first number. This is a utility for calculation. Please contact harry bhai",
                        metavar= "First Number")

    parser.add_argument('*y', type=float, default=3.0,
                        help="Enter second number. This is a utility for calculation. Please contact harry bhai")

    parser.add_argument('*o', type=str, default="add",
                        help="This is a utility for calculation. Please contact harry bhai for more")
    args = parser.parse_args()
    sys.stdout.write(str(calc(args)))
    parser.print_help()
#

This code i found at code with harry

#

When i use ```py
parser.print_help()

```py
*h, **help            show this help message and exit
  *x First Number First Number
                        Enter first number. This is a utility for calculation.
                        Please contact harry bhai

Why are there two "First Number". I want only one.

acoustic yarrow
#

What is amortised time complexity and how do we represent it

#

Pls ping me when answering

fiery cosmos
#

sry

#

(I was looking for the channel)