algos-and-data-structs

[fiery cosmos]

The pins of this channel have some resources

[glass quest]

def binary_search(seq, item):
  start_index = 0
  end_index = len(seq) - 1
  while start_index <= end_index:
    middle_index = len(seq) // 2
    middle_value = seq[middle_index]
    if item == middle_value:
      return middle_value
    elif item < middle_value:
      end_index = middle_index - 1
    else:
      start_index = middle_index + 1
  return None
``` anyone know why its not working

[proud ferry]

Lusername can you tell what is not working

[glass quest]

it doesnt run

it does but no output

[proud ferry]

Ok what is the sequence argument value you are giving for the test?

[fiery cosmos]

middle_index is not len(seq)//2. It should be (start_index+end_index)//2.

and the condition should should be start < end

[proud ferry]

Did it work Lusername with VOID's fix? Curious

[fiery cosmos]

it will work

now help me

#web-development

[proud ferry]

Say anteeksi for me will ya void

[fiery cosmos]

anteeksi

bruh i am fed up

someone help me

😭

[proud ferry]

I'll try my best dont worry

[fiery cosmos]

thanks man

[glass quest]

isnt start_index + end_index basically len(list) -1 since start_index is 0 and end_index is len(list)-1

[fiery cosmos]

no

bro

u r changing the values

after every iteration

understand the concept of binary search

[glass quest]

ohh it changes after every loop ic

[fiery cosmos]

you reduce the search space to half after every iteration

[glass quest]

i know

[fiery cosmos]

good then

help me with #help-pineapple

[glass quest]

end_index is undefined now

start_index = 0
end_index = (start_index + end_index) // 2```

[fiery cosmos]

bro

lemme send u the code

[glass quest]

ight

[fiery cosmos]

def binary_search(seq, item):
  start_index = 0
  end_index = len(seq) - 1
  while start_index < end_index:
    middle_index = (start_index+end_index) // 2
    middle_value = seq[middle_index]
    if item == middle_value:
      return middle_value
    elif item < middle_value:
      end_index = middle_index - 1
    else:
      start_index = middle_index + 1
  return None

[glass quest]

💀 no way my dumbass changed the-

[fiery cosmos]

kek

[west ether]

What's some website where I could practice my algorithms skills with problems?

that are beginner friendly

[fiery cosmos]

Hackerrank @west ether

[west ether]

thank you

[honest dagger]

if anyone wants to help me on #help-potato I owe you a virtual beer. Thanks.

[haughty mountain]

your Nod class is kinda broken even if it randomly works for dict

the default hash impl is not what you want

[honest dagger]

wdym by that tho

[haughty mountain]

if you add these things should behave more sane

def __hash__(self): return hash(self.info)
def __eq__(self, other): return self.info == other.info

[haughty mountain]

the default hash impl is based on id

so different instances will have different hashes, regardless of the values inside

so you want to implement hash and eq on your function, since those will otherwise be based on id

hash and eq is what the dict will actually use

tl;dr: dict will also be broken for your class, fix your class

it's a bit dumb that all classes have hash and eq implemented

most of the time it's not the hash and eq you want, and in other languages you have to implement them to get them

@honest dagger

In [8]: class A:
   ...:     def __init__(self, info):
   ...:         self.info = info
   ...:
   ...:     def __hash__(self):
   ...:         return hash(self.info)
   ...:
   ...:     def __eq__(self, other):
   ...:         return self.info == other.info

In [9]: {A(1): 1, A(1): 2}
Out[9]: {<__main__.A at 0x6f9b594640>: 2}

In [10]: class A:
    ...:     def __init__(self, info):
    ...:         self.info = info

In [11]: {A(1): 1, A(1): 2}
Out[11]: {<__main__.A at 0x6f9a3b36d0>: 1, <__main__.A at 0x6f99c32ac0>: 2}

[honest dagger]

oh so those are different

[haughty mountain]

because the default hash and eq are based on id

[honest dagger]

oh my god

what a joke

class Nod():
    def __init__(self, info):
        self.info = info

    def __str__(self):
        return f'nodul {self.info}'  
    
    def __repr__(self) -> str:
        return f'nodul {self.info}'  

    def __gt__(self, other):
        if self.info > other.info:
            return True
        else:
            return False

    

class Graf():
    def __init__(self):
        self.listaAdiacenta = dict()

    def adaugaMuchie(self, nod1, nod2):
        self.listaAdiacenta[nod1]=nod2
        self.listaAdiacenta[nod2]=nod1

    
    def BFS(self, nodStart, nodScop):
        drumBFS = []

        # setam lista de vizitati 
        vizitati = [False for _ in range(max(self.listaAdiacenta).info + 1)]

        coada = []
        
        #marchez nodStart ca vizitat si ii fac enqueue
        coada.append(nodStart)
        vizitati[nodStart.info] = True # l-am marcat
        
        while coada:

            # scoatem primul element din coada si il adaug in drumBFS
            nodStart = coada.pop(0)
            print(nodStart)

            if nodScop.info == nodStart.info:
                print(drumBFS)
                break

            # iei toate nodurile vecine si treci prin ele
            for nodVecin in self.listaAdiacenta.values():
                if vizitati[nodVecin.info] == False:
                    # atunci il bagam in coada
                    coada.append(nodVecin)
                    vizitati[nodVecin.info] = True
                    drumBFS.append(nodVecin)

graf = Graf()

graf.adaugaMuchie(Nod(0), Nod(1))
graf.adaugaMuchie(Nod(0), Nod(2))
graf.adaugaMuchie(Nod(1), Nod(2))
graf.adaugaMuchie(Nod(2), Nod(0))
graf.adaugaMuchie(Nod(2), Nod(3))
graf.adaugaMuchie(Nod(3), Nod(4))
graf.adaugaMuchie(Nod(3), Nod(3))

graf.BFS(Nod(2), Nod(4))

now it works

if I do it with .values()

[earnest coral]

roman :)

[honest dagger]

din pacate, da.

[earnest coral]

intr-adevar

[haughty mountain]

just implement hash and eq and everything will behave fine

[honest dagger]

I mean it makes sense somehow

but idk

[split sigil]

heyo, please do not use ableist language

[honest dagger]

maybe i didn t work with these until now and my mind is blown because of how weird is this

but still, wtf

[runic field]

Hi, can I ask here for help regarding a task? I asked about it on stackoverflow but didnt get any answer. https://stackoverflow.com/questions/72172274/python-pothole-fixing-machine

[vocal gorge]

I don't get it (probably due to a lack of exact description). Why is the answer not just the total number of potholes? Are you only allowed to switch rods while still moving right one place, or something?

[runic field]

The answer isnt the number of potholes because it is kind of an optimalization problem. You have to go from left to right and you have to fix the most potholes

You can go left, right, up or down

[shut breach]

why cant you fix every pothole

[runic field]

Because you have to go from left to right and if you go through the pothole you cant fix it

Is it better explanation?

[haughty mountain]

how is this not just super greedy?

[shut breach]

so this isnt true?
and why cant you fix the pothole and then go through it or something?
you havent explained the constraints involved here

[haughty mountain]

I think the constraint is that you can move right, or some diagonal to the right

based on the (vague) description, shouldn't it be as easy as this?

sum(a=='x' or b=='x' for a,b in zip(L1, L2))

or maybe not? they say diagonal is banned...

the description is super vague

[vocal gorge]

yeah, that's my guess as well

in which case, yeah, the answer should just be the total number of rows with at least one pothole

[haughty mountain]

I could imagine something like fixing a pothole moves you to the right, and then having the option of moving up/down but you can't fix that pothole

(i.e. effectively a diagonal move)

[kind sundial]

Hi guys can someone try this tricky func

    for i in range( a ):
        list.append( 2 * i )
    print(list)
------------------------------------
func(2)
func(3, [7,3,8])
func(4)
------------------------------------
for func(4) I get 
func(4)

[0, 2, 0, 2, 4, 6]```
I'm not sure I'm getting that output
We expect:
```[7, 3, 8, 0, 2, 4, 6]```
can someone explain? 🤔

[vocal gorge]

Default arguments aren't created once every run, but once when the function is declared.

!e So you're getting remains of previous runs there too:

def f(lst=[]):
    lst.append(1)
    return lst
print(f())
print(f())

[halcyon plank]

@vocal gorge :white_check_mark: Your eval job has completed with return code 0.

001 | [1]
002 | [1, 1]

[kind sundial]

@vocal gorge
yeaa but

but we expect [7, 3, 8, 0, 2, 4, 6,........] - where is 7, 3, 8 if we getting remains of previous runs there
my output:

func(3, [7,3,8])
[7, 3, 8, 0, 2, 4]

func(4)
[0, 2, 0, 2, 4, 6]

[haughty mountain]

your function modifies the input, the calls with no list argument modifies the [] you assigned as the default arg, when you pass the [7, 3, 8] it modifies that list, e.g.

a = [7, 8, 3]
func(3, a)
assert a == [7, 3, 8, 0, 2, 4]

the calls where you don't give an argument are basically the same as

a = []
func(2, a)
assert a == [0, 2]
func(4, a)
assert a == [0, 2, 0, 2, 4, 8]

[runic field]

This is the visualized example from my task

[runic field]

We cannot move diagonally

We can go through the pothole but our task is to fix the most potholes and still go from left to right ...

[runic field]

I didnt say that the roads we kind of connected, sorry

[haughty mountain]

wait, what's the red path?

is the story that you can only fix the pothole on the other side of the road or something?

if so, this is just a very simple dp

how many potholes can I fix after i steps and end up on the top/bottom row

[runic field]

Red path is the path that is chosen so that you go through the least amount of potholes

And yellow are the potholes you can reapir

Repair*

[onyx parrot]

I'm trying LeetCode's easy exercises and I find them kinda hard OTL that's embarassing.

There's the stairs one but can we really solve it using dynamic programming and not estimating the number of combinations?

Like, if we're supposing we have 5 stairs to the top, we already have the min and max combination:

• 1+1+1+1+1
• 2+2+1

Can't we deduce the rest by transforming two 1s in a 2 and sliding it from the beginning to the end?

[onyx parrot]

Ok just spoiled me on the solution but I don't quite get the logic. If I maintain a staircase of 5 stairs, how would I obtain 8 solutions (the solution with 1s only, 4 solutions with one 2, 3 solutions with two 2)?

[vocal gorge]

The logic is that in order to get to the nth step, you need to be on either the n-1th or the n-2th. So the number of way to get to it is the sum of the two previous ones. (That's the recurrence relation for the fibonacci numbers if you met them before.). The only thing that remains is noticing there's 1 way for n=0 (you just stay on that stair), and 1 way for n=1 (you can only go up one stair). So you can calculate it with DP, in time linear with n:

n    0    1    2    3    4    5
f(n) 1    1    2    3    5    8

[onyx parrot]

I ran the simulation in my head and I just noticed 5 for n=4 and 8 for n=5 were straight up Fibonacci numbers lol

So yeah, you have to add over the previous step. It all makes sense now.

[thick echo]

You need to handwrite it essentially to find the subsets with DP

It's very, very difficult to see the angle, top down or bottom up, in your head unless you've seen that type of problem before.

Of course you can just learn all the types of DP problem on LC, which I suspect some do.

[fiery cosmos]

hey guys, How to combine multiple hyperspectral images into one? ```py

Example: Iterate over data set

for sample in dataset:
datacube, labelmap = sample
print(datacube.shape, labelmap.shape)
output -
(240,520,16)(240,520)
(240,520,16)(240,520)
(240,520,16)(240,520)
(240,520,16)(240,520)

[halcyon plank]

:incoming_envelope: :ok_hand: applied mute to @fiery cosmos until <t:1652187960:f> (9 minutes and 59 seconds) (reason: duplicates rule: sent 4 duplicated messages in 10s).

[south abyss]

What does this line do/ mean?

arr = list(map(int, input().rstrip().split()))

[agile sundial]

makes a list of ints from a string read from stdin after stripping whitespace from the right side

[keen hearth]

Yeah, essentially turns a line of input like: 12 34 5 67 8 910 into a list of numbers like: ```py
[12, 34, 5, 67, 8, 910]

[rigid night]

yo! i do comp programming and trying to learn dsa and stuff any guides?

[rigid night]

to be simple, it takes linst inupt

[vernal jackal]

maybe not a python question but how do i add objects into a 2d array with a for loop

[coarse apex]

@vernal jackal create an empty array and in the loop use square bracket indexing to save values.

i haven't figure out how to type code into discord, but:

array1 = numpy.zeros((4,5))
for ii in range(4):
for jj in rahge(5):
array1[ii,jj] = ii+jj

[thick echo]

competitive programmer's handbook

Just do the examples in Python

[thick echo]

Not sure this is the channel, but anyone done any quantum computing work?

[rigid night]

ok ty

[signal knot]

What's the advantage of using a sentinel node instead of null or None in a Linked list?

[stable pecan]

None can't have any links

[burnt iris]

can anyone give me a brief explanation of what data structures and algorithms are? ping me after you reply, thanks

[timber vault]

You can ask that question here: https://www.google.com/, and get an immediate answer

[burnt iris]

okay..

[keen hearth]

This is how CLRS defines algorithm:

Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values as output. An algorithm is this a sequence of computational steps that transform the input into the output.
And data structure:
A data structure is a way to store and organize data in order to facilitate access and modifications. No single data structure works well for all purposes, and so it is important to know the strengths and limitations of several of them.

[burnt iris]

okay thanks

[keen hearth]

An algorithm is a procedure to solve a computational problem. A computational problem might be something like "sort a list of numbers in ascending order", or "find the first occurrence of one string in another string".

[burnt iris]

okay

also can you tell me how this width of a binary tree works

i fail to understand it

[keen hearth]

Oh right. Do you mean generally or is there a specific problem you're working on?

[burnt iris]

wait i'll show the problem to you

okay so this was the example

but i dont understand a thing

[keen hearth]

Oh right. So apparently the "diameter" is defined as the length of the longest path between two nodes in the binary tree.

Do you understand the concept of diameter, or is it an algorithm for finding the diameter you're having trouble with? @burnt iris

[burnt iris]

i dont understand the concept

[keen hearth]

Do you understand the idea of finding a path from one node to another?

[burnt iris]

yeah

[keen hearth]

Alright. Every pair of nodes in the tree has a path between them. Actually, it turns out there is only one possible path to get between any specific pair of nodes.

[burnt iris]

mhm

[keen hearth]

Imagine looking at every possible pair of nodes, and finding the length of the path between them. The longest such path will be the diameter.

The length of a path is just defined as the number of nodes you visit on that path (including the start and end nodes).

[burnt iris]

ohh okay

[burnt iris]

what's the difference between through and NOT through root

[keen hearth]

This actually describes an algorithm for finding the diameter, but it's a pretty inefficient one.

[keen hearth]

The root is the node at the top of the tree. Every node in the tree has exactly one parent, except for the root, which has no parents.

[fiery cosmos]

sounds like https://leetcode.com/problems/diameter-of-binary-tree/ for reference

[burnt iris]

okay thanks

[rigid night]

what are big O notations and stuff

[agile sundial]

it's a way to express how the runtime will grow as a function of the input size

[rigid night]

oh, thanks!

[prime sequoia]

Why even though we use 2 or 3 loops still it have o(n) complexity

[agile sundial]

because of the definition of big O notation

[shut breach]

are you talking about some code in particular?

[prime sequoia]

In leet code I saw a solution for count and say problem ,in that I saw a for looping over with two nested while loop.

[misty plume]

hello, I have a question, how do you differentiate when to implement Kruskal or Prim's algorithms when there is a competetive programming problem?

to me they seem to do mostly the same in a bit of a different way

[molten vigil]

If I want to make a function that would take, for example, some group's id for input and output something from which I would be able to get names group's members, item's in group's possession and such (aka a list containing bunch of strings), what would be the best way to do it? I do something like this now: def get_group_data_from_id(self, group_id: int) -> dict[str, list[str]]:. It returns a dict in which key is for example "members" or "items", and value is list of corresponding type of data (names, items,...). Is there a better way? Maybe using enums? I haven't used it before so I don't know how much more practical it would be and what's the best solution

[lean mica]

does anyone know the answer to this? i'm extremely confused

none of these answers seem correct

it won't return the last position, it'll return the first, it works for non-square arrays, it will return the first occurrence, and j won't be the length of the row

i don't get it

oh got it

[prime sequoia]

What will be the answer

[lean mica]

it will return the last position for which fn is truthy, because break only breaks out of the inner for loop

so if you have like a 2 dimensional array and the last element of each row would return true to the function, it would iterate over the first row, get to the last element, you'd want to break out of all loops and return the position but actually you just break out of the row iteration and move on to the next row, and so on

[limpid raven]

Im not sure how to make a main routine ;-; flow chart
im trying to make a food ordering app
login -> select food quantity -> payment -> display order history -> can choose to order more

if they order more (goes back to this ---->) select food quantity -> payment -> display order history -> can choose to order more

and if they sign up (bring back to login --->) login -> select food quantity -> payment -> display order history -> can choose to order more

[versed wing]

https://artofproblemsolving.com/community/c163h2843420_collisionresistant_hash_functions

[mental crystal]

How would you guys approach this task?

With the third one, I would look at n^5 and see if n^4 is a lower bound of that, which it is, so it is true, right?

[agile sundial]

it's not just a lower bound, it needs to be an asymptotic lower bound

@mental crystal

but yeah, you're right

[mental crystal]

Would these answers be correct?

[agile sundial]

i think so

[prime sequoia]

which should I start first stack or linked list

[mental crystal]

You mean learn?

[prime sequoia]

yes I know basic ,Now I am go in to understand all

[mental crystal]

I would say stack. It's one of the simplest data structures, then learn about priority queues etc

Linked list should be a bit later, I would say

[prime sequoia]

Thanks man

[mental crystal]

Good luck and have fun!

[prime sequoia]

I don't know how to solve coding problems, so I am understanding other's code answers

[haughty mountain]

No it won't, if I have a row that goes [True, False, True] then pos[1] will be 0 and not 2. The only correct response is the third one. It will return the last row with a match, but not the last column in that row

[prime sequoia]

Is it common for all or am I different kind

[mental crystal]

If it works for you, it's all good. This way you learn your strengths and weaknesses, so maybe you should put some time into learning to solve the coding problems

[lean mica]

i think there is a lot of literature on this already

[prime sequoia]

can you say is there any other ways to learn problem solving to problem

[lean mica]

i'm not sure what you mean by this

you can just run that code with a test input and prove that it's the answer i said it was

[mental crystal]

I would say start with easy problems that require basic data structures and/or algorithms

[abstract tinsel]

to learn algorithms, you could try project euler questions

[prime sequoia]

okay i will start learning then

[lean mica]

nvm i gotcha. yeah thats tricky

[haughty mountain]

~ $ cat asd.py
arr = [[True, True], [True, True]]

def fn(x): return x

pos = False
for i in range(len(arr)):
    row = arr[i]
    for j in range(len(row)):
        if fn(row[i]):
            pos = (i, j)
            break

print(pos)
~ $ python asd.py
(1, 0)

[abstract tinsel]

rn im doing pe questions and it helps

[haughty mountain]

and not (1, 1)

[prime sequoia]

what is time complexity of that program

is it O(n^2)

[lean mica]

yeah i see now

[fallow prairie]

Shouldn't the output be (0,0)?

[fallow prairie]

Yep....in the worst case scenario

[haughty mountain]

if the function was correctly written yes

[fallow prairie]

Yep

[haughty mountain]

one of the multiple choice options was that it returns the last element

which is what I wanted to show was wrong

[dapper sapphire]

Not exactly algo and data structure question but related to it.

Can you use leetcode at work(at big tech companies and defense companies(NASA, Boeing, Northrop Grumman)) in your downtime and not get in trouble?
My company is pretty small, so I can leetcode in my downtime.

But I dont know what it looks like at big companies. And I read somewhere that defense companies like Northrop Grumman dont even let you take your phone inside.

The concern isnt more so doing leetcode at these big companies in your downtime.
But logging into your personal account (in this case leetcode) on company machine.

[agile sundial]

maybe also ask in #career-advice

[hollow summit]

hi all, i am new to python and running a traning for myself.
i have crated a list of stocks(160 names) and i want to call each stock name with yahoofinance package to create each stocks historical data with using
yf.download('GOOGLE', start='2019-01-01', end='2021-06-12', progress=False)

but instead of GOOGLE i need to write list element number like (1,1)(2,1)(3,1) where each of them belongs to different stocks.
how can i write it into yf.download? instead of GOOGLE word?

[dapper sapphire]

Thanks just did (:

[cinder cedar]

When i use fopen, where should the file be

[short chasm]

what does import main do PLEASE TELL ME

[haughty mountain]

why would you log into a bunch of personal stuff on a corp machine? sounds like a bad idea in general

[dapper sapphire]

When I said, "logging into my personal account" I meant that just for leetcode and nothing else.

[haughty mountain]

still, why? use your personal device

[dapper sapphire]

I would, but when I'm onsite, I would likely only have access to company's machine.

I dont know how flexible/accepting companies would be with someone bringing their personal device to work.

[haughty mountain]

I don't think my company cares, it's better to not do non-work stuff on work hardware anyway

I don't generally bring a personal laptop to work though, because it's just extra weight to carry

(and I can use my phone to do dumb coding stuff if really needed)

[dapper sapphire]

Ok.

[radiant moat]

Hello there !
Do we have a faster way to check a value in 2 lists like this

list_a = [1, 2, 3]
list_b = [4, 5, 6]
to_check = 2
if to_check in list_a or to_check in list_b:
    print("yay")

I mean we can still use + to concat both but I don't think it is optimal

[covert thorn]

if to_check in {*list_a, *list_b} works

[next loom]

I have a question about if I can be more optimal(faster) with my algorithm. I'm making an algorithm for a mobile robot. The algorithm creates a quadtree of points(points which represent the freespace in map that is accessable to the robot). An Agglomortive clustering algorithm is used to divide the free space in the map into clusters(regions). This is before the part of the algorithm I want to bring to focus for this question.

As the robot moves around, the algorithm searches the quadtree for the points around the robot's postion, these points are then sorted out to account for which points are in which cluster and making calculations. The robot is continously moving about so the algoirthm has to be fast.

Algorithm:
This is the part of the algorithm in focus:
[i] Quadtree is searched to get points around the robot.

[ii] points are fed in a for loop

[iii] Within this first for loop is another for loop involving the clusters where the algorithm figures out which region the point belongs to nd some calculations are made based off that.

[radiant moat]

Ok ok ty, do you know is it faster ?

[next loom]

Here is the part of my actual algorithm this question pertains to:

 """Gets the minimum coverage from the set of clusters, this is used in the algorithm 
    to correctly assign which region of the map the robot should 
    go to next so as to cover it more properly"""
    def minimum(self):
        #number= 10e20
        set = {}
        #clusters = []
        mini = []
        count = {}
        for key in self.region_density.keys():
            mini.append(self.region_density[key][3])
            #print(key," is",self.region_density[key][1])
            set[key] = self.region_density[key][3]
            #clusters.append(self.region_density[key][2])
            count[key] = self.region_density[key][1]

        smallest = min(mini)
        #print("count: ",)
        #print("clusters: ",clusters)
        #print("set: ",set)

        #print("smallest: ",smallest)
        return [smallest,set]
        #return set

 """ This function accounts for a free cell
        and counts said cell into coverage calculation of whatever cluster 
         the cell was assigned to"""
    def zoner(self,free_cell,x,y):
        #free_cell =  self.index_calculator(self.grid_calculator(self.convert(self.pose_calculator(self.cell_grid(free_cell)))))
        #if len(self.identifiers) == 0:
         #   self.pub3.publish("All Done")
          #  self.finish = "finished"
        #else:
            for key in self.region_density.keys():
                inscope = self.in_scope(self.region_density[key][0],0,(len(self.region_density[key][0])-1),free_cell)
                if inscope == True:
                    #print(key)
                    self.region_density[key][1] += 1
                    self.region_density[key][3] = (float(self.region_density[key][1]) /(self.region_density[key][2]))* 100
                    print(key," is ",self.region_density[key][3])
                    if len(self.rden[key]) > 30: #0.3*(len(region[0])):
                       self.rden[key].remove(free_cell)
                       self.markers[key] = self.get_center(self.rden[key])

         ```

This part is outside of the for loop above so you dont need to look at this part```python
if self.region_density[key][3]>= 90:
#try:
#self.identifiers.remove(key)
rospy.loginfo(key + "is 90%")
#except ValueError:
# pass
break
mini=self.minimum()
dist = 10e20
marker = "hoh"
for key in mini[1].keys():
if mini[1][key] == mini[0]:
check_dist = self.get_distance(self.markers[key], [x, y])
if check_dist < dist:
marker = key
dist = check_dist
self.data_to_send.data = self.markers[key]

        #print(marker," is marked")
        #print(self.data_to_send.data)
        self.pub.publish(self.data_to_send)```

""" functions collects the free cells around the robot's location at an instance is time
        and uses those cells in coverage calculation, zoner function is used in this function """
    def new_mirror(self,x0, y0, range,scan):
        scan_angles = self.rad_to_deg(scan)
        rtn = rospy.Time(0)
        #pose_footprint = self.transform([x0,y0],'base_footprint','map',rtn)

        position=self.grid_calculator([x0, y0])
        center, radius = [position[0], position[1]], range
        found_points = []
        center = Target(*center)
        self.qtree.query_radius(center, radius, found_points)

        #scope=[]

        position = self.transform([x0,y0],'map','base_scan',rtn)

        #print("found points",len(found_points))


        for found_point in found_points:
            coord = self.pose_calculator([found_point.x,found_point.y])
            base_scan_scope = self.transform(coord,'map','base_scan',rtn)
            #transformation = self.get_transformation('map', 'base_scan', rtn)
            #base_scan_scope =  self.transform_point(transformation, Point(coord[0],coord[1],0))
            theta = int(round(math.degrees(math.atan2(base_scan_scope[1]-position[1],base_scan_scope[0]-position[0]))))
            #theta = (math.radians(math.atan2(base_scan_scope[1] - position[1], base_scan_scope[0] - position[0])))
            theta = (theta + 360) % 360

          

This part is within the for loop above```python
index = self.index_calculator([found_point.x,found_point.y])
#index = self.index_calculator(self.grid_calculator((self.convert((self.pose_calculator([found_point.x, found_point.y]))))))

        inscope = self.in_scope(scan_angles,0,(len(scan_angles)-1),theta)
        #inscope = self.in_scope(scan_angles, int(math.degrees(-0.524276)), int(math.degrees(0.524276)),theta)
        dist =  self.get_distance(coord,[x0,y0])

        if inscope==True and dist<scan.ranges[theta]:
            if self.full_grid[index] == 0 and self.full_grid2[index] !=21:
                self.zoner(index,x0,y0)
                self.full_grid2[index] = 21
                pnt_list = []
                pnt_list.append(found_point.x)
                pnt_list.append(found_point.y)
                where_to = '/home/philip/Desktop/coverage.csv'
                with open(where_to, 'a') as csvfile:
                    csvwriter = csv.writer(csvfile)
                    csvwriter.writerow(pnt_list) ```

As seen, the function new mirror has a for loop that has within it zoner which has a for loop in it as well. Is there any way to make my algortihm faster, the quadtree search can provide a little over a 1200+ points at a time. Can I get what I want without need of the nested for loop?

[covert thorn]

it seems the more verbose if to_check in list_a or to_check in list_b is possibly 3-4 times faster.

[radiant moat]

Ok ty !

[fringe zodiac]

basket1 = ["apple", "pear", "orange"]
basket2 = ["grape", "watermelon", "cherry"]
basket3 = ["peach", "mango", "tangerine"]
basket4 = ["durian", "banana", "lychee"]


def sequentialSearch(basket1, target):
    n = len(basket1)

    for i in range(n):
        if basket1[i].lower() == target:
            return i
    return -1


target = input("Search for fruits: ")
result = sequentialSearch(basket1, target)

if result == -1:
    print("Fruit is not found in basket 1")
else:
    print(f"Fruit is found in position {result} in basket 1")

hi is there any way to do a sequential search among multiple lists?

[gusty grove]

if i have 3d markers with IDs (usually 1-3 in view) how can i estimate the camera pose from that?

i dont know the global position of the markers, just the relative position to the camera whenever they are in view

[vocal gorge]

@radiant moat note that to_check in {*list_a, *list_b} would be slow because it has to create the set (which is ~400ns), but after you create the set:

matches = {*list_a, *list_b}

to_check in matches checks should be faster than in a list (58ns vs 76ns, and should get much more notable as the list sizes grow)

[jovial valley]

concat both lists and try binary search

[radiant moat]

Ty for the infos

[slender sandal]

Guys...

from math import cos, pi


def fib(n: int) -> int:
    return round(((0.5 * (1 + 5 ** 0.5)) ** n - (2 / (1 + 5 ** 0.5) ** n) * cos(pi * n)) / (5 ** 0.5))

It's O(1)

I've implemented one of these: https://www.wolframalpha.com/input?i=fibonacci(n)

[fresh inlet]

Is counting all the nodes in a binary search tree a divide-and-conquer approach or a brute force approach

[vocal gorge]

!e The problem with these formulas is that they become unreliable due to float inaccuracies.

from math import cos, pi


def fib(n: int) -> int:
    return round(((0.5 * (1 + 5 ** 0.5)) ** n - (2 / (1 + 5 ** 0.5) ** n) * cos(pi * n)) / (5 ** 0.5))


def fib_exact(n: int) -> int:
    a, b = 1, 1
    for i in range(n-1):
        a, b = b, a+b
    return b

for n in range(3,1000):
    a, b = fib(n), fib_exact(n-1)
    if a != b:
        print(n, a, b)
        break

[halcyon plank]

@vocal gorge :white_check_mark: Your eval job has completed with return code 0.

71 308061521170130 308061521170129

[vocal gorge]

(And when I experimented with using Decimal to compensate for that, I got a slower solution than direct computation)

[jolly mortar]

i remember reading that youd need linear amount of space to store phi to the correct precision for the nth term

[vocal gorge]

I believe the quick way is numerical matrix powers. Numpy can even do it on Python's infinite-length integers:

def fib_matrix(n: int) -> int:
    mat = np.array([[0, 1], [1, 1]]).astype(object)

    mat = np.linalg.matrix_power(mat, n-1)
    return mat[1, :].sum()

This function gets correct results up to n=1000 at least

[jolly mortar]

why wouldn't it always be correct?

[vocal gorge]

Though it's not actually much faster, hmm:

[vocal gorge]

It should, just testing.

[jolly mortar]

hm

[vocal gorge]

ah, there we go:

it becomes noticable for high n

[fierce pier]

hello!! im unsure of what this error means, can someone help out please?

[humble igloo]

whenever you call that get_vg function it raises NonImplementedError

and hence you get a traceback

[fierce pier]

so should i just remove the error?

[humble igloo]

sure idk why it's there, I guess it was deliberately put up by the exercise creator

[fierce pier]

oh okay thankyou !

[pallid niche]

Hey, how can I create a nested dictionary with an initial value? let's say I have a dictionary dic
if I tried to access any key it should be accessible.

>>> dic['a'][4]['b']
 0

I could make something like that, but not with nested dict

>>> from collections import defaultdict
>>> dc = defaultdict(lambda: 0)
>>> print(dc['w'])
0

[vocal gorge]

You'd use defaultdict with defaultdict values.

E.g. defaultdict(lambda: defaultdict(lambda: defaultdict(int)))

[pallid niche]

Thank you!

[next loom]

I made sure to format the code in my question to python now.

[lethal bronze]

im trying to binary search a huge file, that i sorted on some index, for a line with that index

since all lines are approximately the same lenght i can use f.seek(n) to jump to the nth byte in the file

but i wonder is there a method like f.readline() that returns the line containing the n-th byte of the file?

because if i call f.readline() after f.see(...) I get that line but starting from the byte and not including the rest of the line before the byte

[haughty mountain]

you can also do exact fib in log n time

nvm, you mentioned this

[haughty mountain]

you would have to scan backwards until newline/beginning of file

if you want a fast binary search on a sorted file you probably want an index in the file, like: first item is at offset x, second item is at offset y, ...

then you can binary search the index, and seek the file to read the entry

[lethal bronze]

yes so it work by jumping to the middle byte and then scanning backwards to newline

#data-science-and-ml message

heres the full code

[warped saddle]

Can anyone help me for this question?

prove AP == AQ

PB != BQ

AB is not not perpendicular to line I

[feral trail]

This medium question is making me question my life decisions

Like I can think of a way to solve it but to translate it into code is just pain

[vocal gorge]

10 queries of length up to 100 is low, so even a bad solution might work

there's O(n^2) substrings, checking each substring is O(n) or so if you do it wia something like a Counter-but-hashable (or O(n log n) via sorting)

so it's solvable in O(n^3) or so, which may well pass

[feral trail]

That was actually what I was thinking of doing.
So a hashmap with each keys being a substring and its' string presentation

So like 'm': [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

But I'm having problem keeping count of how many times a substring appear

For example the substring 'm' appears twice in 'mom' but how do I keep track of that

[vocal gorge]

I think I'd actually do, like, a dict mapping a sorted string to the number of times it appears. That's the O(n^3 log n) way, but sorting is pretty fast.

[feral trail]

....wait

OHHHH

Wow yeah why did I not think of that

Actually I was reading the editorial answer and it seems like I have the same idea at he did

But I don't understand these 2 lines

            signature = tuple(signature)
            signatures[signature] = signatures.get(signature, 0) + 1

signatures is the hashmap

and signature is the list with 26 0

[vocal gorge]

the cast to tuple is needed simply because lists aren't hashable (because they are mutable), and tuples are

the second line is basically signatures[signature] += 1, but works even if signature isn't present in signatures yet, by using get with a default value

[feral trail]

Oh wait they are using the tuple as key instead of the substring?

AHHH

Oh right why do I need the substring when I already have its presentation

[feral trail]

So that's how you do it, I have always wondered if there's a better way to do it since I always do

for i in i:
  if i not in dict:
    dict[i] = 0
  else: dict[i] += 1

I think it's also doable with defaultdict?

I'm not too sure about that

[vocal gorge]

Or with setdefault when doing mutable values, yes.

[feral trail]

I see, that seems much more concise and pythonic

But your way of solving it by sorting the substrings is really intuitive and understandable though

Should be shorter to code too

[vocal gorge]

I have a love-hate relationship with using sorting instead of Counters

because from a DSA perspective, it's worse - O(n log n) instead of O(n)

but in practice, because Counters are dicts that are updated by python loops and sorting is a very optimized algorithm in C, sorting is usually faster.
at least for stuff like strings.

[fiery cosmos]

also log(n) is only on the order of 32 or 64 for most numbers computers practically deal with

[feral trail]

The python loops incident, I'm always surprised how slow for loops in Python actually are

[feral trail]

Order of 32 and 64 for log2 really doesn't sound like much, I wonder why the curve for O(nlogn) always look so much slower compared O(n)

[fiery cosmos]

Do they? For O(n^2) it is definitely way worse - I always like to emphasize how for up to 32bit integers (up to ~4billion) O(nlogn) is no worse than O(32*n) (because log(2^32) = 32) whereas O(n^2) is up to O(4billion*n)

[feral trail]

Jesus I actually never considered how slow O(n^2) actually is

4billion*n is quite insane

[vocal gorge]

meh, I don't like that reasoning from a formal standpoint, complexity classes can't be compared like that, and also why would it be necessarily a binary logarithm?

[fiery cosmos]

Oh definitely these are different formally in theory, it's just interesting how O(n) and O(nlogn) are closer than people may assume

Does log base matter? base 10 or base 2 or e are within constant multiples of each other (though I know saying O(32*n) is a bit hand wavy)

[vocal gorge]

That's true, but that's also why saying log(n) is at most 64 is handwavy

import string, random
strs = ["".join(random.choices(string.ascii_letters,k=100)) for i in range(10)]
>>> %timeit [count_anagram_pairs(x) for x in strs]
319 ms ± 98.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

looks like the sorting solution should be fast enough indeed

[feral trail]

It's 5am and my brain stopped working, can someone explain to me why this is the case?

Isn't n(n-1)/2 the way to calculate sigma?

Ah nvm I see why now

[fathom thorn]

yo, can someone help me with a code?

I'm having issues defining a function

[fiery cosmos]

def <function name>():

[fathom thorn]

this works

this doesnt

and i dont have a clue why XD

[fiery cosmos]

ah you're not returning it

[fathom thorn]

how come?

[feral trail]

You don't have a return clause on the function

[fathom thorn]

but...

this works

and i dont have a return clause on this either

[feral trail]

Yes

[fiery cosmos]

yes since yo do not need that data back to process

[feral trail]

But you are assigning to a variable on the second case

[fathom thorn]

ooh

so i need "return X"?

[feral trail]

yep

[fathom thorn]

oh right right

and i need to assign an internal variable as well, yes?

[feral trail]

not really, you can just return that long line

[fathom thorn]

will it need self.?

[fiery cosmos]

no

[fathom thorn]

ok, thank you 🙂

[feral trail]

this is not a class so no

[fathom thorn]

so, return pyautogui...

[fiery cosmos]

classes dont really need self, but it's what they're made for

[fathom thorn]

it's easier if i define an internal variable, no?

[fiery cosmos]

not really

[feral trail]

You can yeah, not needed in this case

But if you want to clarify what that pyautogui... is returning for easier readability

Then yeah why not

[fiery cosmos]

let me give you a code example of what to do

[fathom thorn]

like that?

[fiery cosmos]

yes but remove the first line

[feral trail]

You only need one line

[fiery cosmos]

before the time.sleep(0.1)

[fathom thorn]

ok

[fiery cosmos]

Exactly

[fathom thorn]

thank you! 😄

[feral trail]

return function just means call the function and returns what it returns as a result

[fiery cosmos]

that should work

so ```py
def main():
return "Hello"

print(main())
#Prints Hello

if that gives an understanding

[stark elbow]

Hi guys would you recommend learning data structs implementation in python or C?

[fiery cosmos]

i think you would learn it better in python since of the syntax and the libraries python has

just makes it easier

[stark elbow]

Ok Ok thanks

[feral trail]

Definitely, but I recommend implementing the data structures in C yourself to fully understand how it works under the hood

Might be a bit of a torture but I think it's worth it

[fiery cosmos]

i just thought about that, that's very true

[feral trail]

Do that and you will feel grateful for how easy Python makes everything. I 'implemented' a Queue and Stack using python's Lists

Feels like a joke

Not until I do it in C did I understand fully how it works

[fiery cosmos]

very true, i would almost also go ahead and say that python is baby code really, the luxury of high-level languages

it spoils us

[feral trail]

Indeed, but it works well for leetcode type questions since you don't need to be so verbose

And it just makes some problems a joke with list slices and stuffs

[fiery cosmos]

yes it's easier to code what you want it to do

[feral trail]

And no segmentation fault

Still have nightmare about that

[fiery cosmos]

i mean me trying to learn rust just really fucks me up, it's for sure a really big step

it's like drakes song started from the bottom, but inverted really

[feral trail]

This is me but with Ocaml instead

Functional programming feels almost nothing like what I learnt so far

Recursion everything, weird syntax

But at least you can not mess up the type

[fiery cosmos]

What's ocaml i've never heard of it

[feral trail]

A language for functional programming

Haskell but less popular I suppose

[fiery cosmos]

huh, looked at an example, the syntax really is weird, it's nothing easy to get used too

im trying out Ocaml on https://try.ocaml.pro/

I actually like it, it's great for math

well, isn't that what it's used for.... i got myself there

[fierce pier]

im trying to read this csv data but

so this is my code

but it says this

[slender sandal]

Use data["P/bar"] instead of data.P/bar. P/bar looks like division between P and bar to Python

[rough lynx]

Anyone have practical examples of when unrolling loops is beneficial? I often find that when I do make a loop, that unrolling them just makes my code harder to read for an insignificant performance gain

It also doesn't seem as necessary when things like doing loops within a list call is faster than doing a regular loop
Like this example:

# original loop
results = []
for i in range(100):
  if 100 % i == 0:
    results.append(i)

# loop within list
results = [i for i in range(100) if 100 % i == 0]

So far the only thing I see that makes unrolling loops viable is this old paper from 2009 that does this:

# original function containing a loop
def f(bar):
  sum = 0
  for p in bar:
    sum += p

# dynamically unrolled function
def f(bar):
  sum = 0
  it = bar.__iter__()
  try:
    while(True):
      sum += it.next()
  except StopIteration
    return sum

[naive saddle]

How should I implement a stack in python?

[lean walrus]

use list

list.append and list.pop

class Stack(Generic[T]):
    values: list[T]
    def __init__(self) -> None:
        self.values = []
    def push(self, value: T) -> None:
        self.values.append(value)
    def pop(self) -> T:
        if not self.values:
            raise StackUnderflow
        return self.values.pop()

but using list is faster

[lost echo]

Hi to all. Can somebody help me with this; how i can find a specific row and look for the minimum element index in a numpy array not including zero

[stark stone]

are you familiar with list comprehensions?

[lost echo]

no sir, i'm new on python

[stark stone]

oh wait you want the index, nm

[lost echo]

yes search a specific row and then find the index of the lower number in the row from a numpy array.

[stark stone]

so I think another way to say it is you want the minimum positive number?

[lost echo]

yes sir

[stark stone]

there's an example here of finding the number itself (https://stackoverflow.com/questions/27947941/retrieve-largest-negative-number-and-smallest-positive-number-from-list) in a list, and then you could use the index() function to find out where it is... there's likely a little more to it, but that could get you started

I'm new here, so I'm not sure of the rules and how all that works, but I know there's some help channels people ask about specific issues in

[lost echo]

Thanks!!

[stark stone]

check out #❓｜how-to-get-help

[lost echo]

thanks!

[ivory fulcrum]

Hello guys, I will give you a scenario: Imagine there's a machine in front of you where it prints 1 or 0, and you will have to bet and guess what comes next whether 1 or 0. But you have a historical data about the machine around 5000 samples of 1s and 0s. How will you handle the situation?

I don't know machine learning yet but im curious how you guys handle this

[feral trail]

I just heard back from my friend who came back from an interview, they gave him this question.

Given a string and a substring, return the index where the substring first appears in the string given that there will always be a solution

However in a string there will be a random * to represent any character in the alphabet

So string = 'abcde'

Substring = 'a*c' then you should return 0

I just tried doing this with regex but for larger test cases I feel like it will fail miserably

[agile sundial]

why? regex seems like the perfect tool

[feral trail]

It does

But it's also very slow

And there's most likely a test case where this happens https://community.appway.com/screen/kb/article/checking-strings-avoiding-catastrophic-backtracking-1482810891360

[agile sundial]

the regex not that complicated

it's just the input string, with the * replaced with a [a-z]

[feral trail]

I just tried the regex method with 10^5 string and 1000 length substring

It took 2.4948169529998268

Which I guess will pass the tests?

import string

def solve2(big_s: str, pattern: str):
    for i in string.ascii_lowercase:
        subs = pattern.replace('*', i)
        result = big_s.find(subs)
        if result >= 0:
            return result

I tried redoing it like this

And it's much faster than regex

[keen hearth]

Are you sure 🤔 I did the benchmark myself and found the regex solution to be about 5.5 times faster.

[feral trail]

Is it? Here's what it showed for me

26-LETTERS TOOK: 0.27546685800007253
REGEX REPLACE TOOK: 2.4948169529998268

[keen hearth]

What does your regex code look like?

[feral trail]

def solve3(big_s: str, pattern: str):
  if re.search(pattern.replace('*', '[a-zA-Z]'), big_s):
      return 'yes'
  return 'no'

I should return the index but I was just testing it out

[keen hearth]

🤔

How are you benchmarking it?

[feral trail]

uhhh

Here's the whole code

https://pastebin.com/kzhTdbVY

I wasn't the one who wrote the test generator though

I just time it

[haughty mountain]

OPTIMIZED TOOK:  0.024562555001466535
26-LETTERS TOOK:  0.44470020099834073
REGEX REPLACE TOOK:  0.1980608529993333

[feral trail]

🤔

wait

OPTIMIZED TOOK:  0.0135345000308007
26-LETTERS TOOK:  0.3620278000016697
REGEX REPLACE TOOK:  0.08034400001633912

HMMM

[keen hearth]

@feral trail Results of my benchmarking: #bot-commands message

[feral trail]

That's almost 6 times faster

Wait then how did I get that previous result before

Both are slower than the optimized code but still

Interesting, I wonder if a test case can be made to make regex fail though

We also have to factor in the fact the our computer is probably much faster than the one they used to test the code tho

I tried running the code on repl.it and it has been freezing for 30 seconds

26-LETTERS TOOK:  0.8151735749997897
REGEX REPLACE TOOK:  0.8628052330004721```

Yeah 26 letter is still consistently slower

Weird

[haughty mountain]

that there is a single * is a pretty important constraint

[feral trail]

Definitely

[haughty mountain]

the test generating code is...really slow

[feral trail]

If it has like 100 * in 1000 substring regex won't work ever

I think the exercise is pointing us toward KMP algorithm

But is it supposed to be that hard

[haughty mountain]

regex works fine for that

[feral trail]

regex works even for 100 *?

[haughty mountain]

the optimized solution only works ok for 1 *

[feral trail]

Yeah definitely, it says optimized but it's still nothing compared to KMP

[haughty mountain]

it should, it's still a very simple regex

[feral trail]

And very limited use case

And the 3 seconds time limit might be a bit too little for regex

I'm not sure since I don't the IDE to test it but

[haughty mountain]

lol, I'm testing on my phone

[feral trail]

lmao, that's next level

But there's no way the one who makes this problem didn't account for regex though

I wonder what the "actual" solution is

Hopefully not this cause this would make anyone not know about it immediately fail https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/

[haughty mountain]

I mean, KMP is the most famous string matching algo

I don't think I remember how to implement it, but I sure know about it and other string matching algos

[feral trail]

Yeah but to be able to code it in without looking it up is just a matter of memorization

[haughty mountain]

e.g. Boyer-Moore

[feral trail]

This is like 1 of the three question in an online assesment and you have 60 minutes iirc?

They probably detect if you have your tab focused too

Can be circumvented but...

[haughty mountain]

I think the optimized solution has bad cases

actually, the one I was thinking of doesn't end up all that bad

[feral trail]

which case were you thinking about?

[haughty mountain]

nvm, it does work, I just needed to make the match fail

OPTIMIZED TOOK:  6.694881187999272
26-LETTERS TOOK:  0.509963696997147
REGEX REPLACE TOOK:  0.1131640219973633

I'm ignoring the input params for the function, but this

def gen_test(big_s_l=100000, pattern_l=10, fail_ratio=0.2):
  n = 10000
  k = 10
  big_s = 'a'*n
  pattern = 'a'*k + '*' + 'z'
  return big_s, pattern

this isn't even such a bad case

basically force a lot of overlapping matches for the prefix that the optimized one searches for

[feral trail]

Ahhh, yeah that would make it really slow for sure. And also sounds like something in a real test case too.

Almost 7 seconds

oof

[haughty mountain]

7 seconds for a pretty small case

and I could optimize k to make it worse

[feral trail]

I actually found a harder version of the exercise

This is easy? lol

[haughty mountain]

short strings as input

[half ore]

hey guys can someone explain why i need math in programming?

im new to algorithms

can someone explain what algorithms and data structures are?

i know only one algorithm, the binary search

[shut breach]

check the pins for learning resources

[earnest quail]

So, I am trying to understand Kademlia as presented in:

Maymounkov, P., & Mazieres, D. (2002, March). Kademlia: A peer-to-peer information system based on the xor metric. In International Workshop on Peer-to-Peer Systems (pp. 53-65). Springer, Berlin, Heidelberg.

For the "Efficient Key Republishing" section, the second optimization mentioned is that a node refreshes all k-buckets in a subtree of k nodes in order to figure out the k closest nodes to a key. I am assuming this is so that it can send store RPCs for a key-value store to those nodes directly. Given the way Kademlia is set up, this only works for the k-buckets near the node's ID, right?

[next loom]

I have a question about if I can be more optimal(faster) with my algorithm. I'm making an algorithm for a mobile robot. The algorithm creates a quadtree of points(points which represent the freespace in map that is accessable to the robot). An Agglomortive clustering algorithm is used to divide the free space in the map into clusters(regions). This is before the part of the algorithm I want to bring to focus for this question.

As the robot moves around, the algorithm searches the quadtree for the points around the robot's postion, these points are then sorted out to account for which points are in which cluster and making calculations. The robot is continously moving about so the algoirthm has to be fast.

Algorithm:
This is the part of the algorithm in focus:
[i] Quadtree is searched to get points around the robot.

[ii] points are fed in a for loop

[iii] Within this first for loop is another for loop involving the clusters where the algorithm figures out which region the point belongs to nd some calculations are made based off that
Here is the part of my actual algorithm this question pertains to:

 """Gets the minimum coverage from the set of clusters, this is used in the algorithm 
    to correctly assign which region of the map the robot should 
    go to next so as to cover it more properly"""
    def minimum(self):
        #number= 10e20
        set = {}
        #clusters = []
        mini = []
        count = {}
        for key in self.region_density.keys():
            mini.append(self.region_density[key][3])
            #print(key," is",self.region_density[key][1])
            set[key] = self.region_density[key][3]
            #clusters.append(self.region_density[key][2])
            count[key] = self.region_density[key][1]

        smallest = min(mini)
        #print("count: ",)
        #print("clusters: ",clusters)
        #print("set: ",set)

        #print("smallest: ",smallest)
        return [smallest,set]
        #return set ```

""" This function accounts for a free cell
        and counts said cell into coverage calculation of whatever cluster 
         the cell was assigned to"""
    def zoner(self,free_cell,x,y):
        #free_cell =  self.index_calculator(self.grid_calculator(self.convert(self.pose_calculator(self.cell_grid(free_cell)))))
        #if len(self.identifiers) == 0:
         #   self.pub3.publish("All Done")
          #  self.finish = "finished"
        #else:
            for key in self.region_density.keys():
                inscope = self.in_scope(self.region_density[key][0],0,(len(self.region_density[key][0])-1),free_cell)
                if inscope == True:
                    #print(key)
                    self.region_density[key][1] += 1
                    self.region_density[key][3] = (float(self.region_density[key][1]) /(self.region_density[key][2]))* 100
                    print(key," is ",self.region_density[key][3])
                    if len(self.rden[key]) > 30: #0.3*(len(region[0])):
                       self.rden[key].remove(free_cell)
                       self.markers[key] = self.get_center(self.rden[key])
 

This part is below is outside of the for loop above so you dont need to look at this part

if self.region_density[key][3]>= 90:
                        #try:
                            #self.identifiers.remove(key)
                        rospy.loginfo(key + "is 90%")
                        #except ValueError:
                         #   pass
                    break
            mini=self.minimum()
            dist = 10e20
            marker = "hoh"
            for key in mini[1].keys():
                if mini[1][key] == mini[0]:
                    check_dist = self.get_distance(self.markers[key], [x, y])
                    if  check_dist < dist:
                        marker = key
                        dist = check_dist
                        self.data_to_send.data = self.markers[key]

            #print(marker," is marked")
            #print(self.data_to_send.data)
            self.pub.publish(self.data_to_send) ```

""" functions collects the free cells around the robot's location at an instance is time
        and uses those cells in coverage calculation, zoner function is used in this function """
    def new_mirror(self,x0, y0, range,scan):
        scan_angles = self.rad_to_deg(scan)
        rtn = rospy.Time(0)
        #pose_footprint = self.transform([x0,y0],'base_footprint','map',rtn)

        position=self.grid_calculator([x0, y0])
        center, radius = [position[0], position[1]], range
        found_points = []
        center = Target(*center)
        self.qtree.query_radius(center, radius, found_points)

        #scope=[]

        position = self.transform([x0,y0],'map','base_scan',rtn)

        #print("found points",len(found_points))


        for found_point in found_points:
            coord = self.pose_calculator([found_point.x,found_point.y])
            base_scan_scope = self.transform(coord,'map','base_scan',rtn)
            #transformation = self.get_transformation('map', 'base_scan', rtn)
            #base_scan_scope =  self.transform_point(transformation, Point(coord[0],coord[1],0))
            theta = int(round(math.degrees(math.atan2(base_scan_scope[1]-position[1],base_scan_scope[0]-position[0]))))
            #theta = (math.radians(math.atan2(base_scan_scope[1] - position[1], base_scan_scope[0] - position[0])))
            theta = (theta + 360) % 360 ```

This part is within the for loop above

 
 index = self.index_calculator([found_point.x,found_point.y])
            #index = self.index_calculator(self.grid_calculator((self.convert((self.pose_calculator([found_point.x, found_point.y]))))))

            inscope = self.in_scope(scan_angles,0,(len(scan_angles)-1),theta)
            #inscope = self.in_scope(scan_angles, int(math.degrees(-0.524276)), int(math.degrees(0.524276)),theta)
            dist =  self.get_distance(coord,[x0,y0])

            if inscope==True and dist<scan.ranges[theta]:
                if self.full_grid[index] == 0 and self.full_grid2[index] !=21:
                    self.zoner(index,x0,y0)
                    self.full_grid2[index] = 21
                    pnt_list = []
                    pnt_list.append(found_point.x)
                    pnt_list.append(found_point.y)
                    where_to = '/home/philip/Desktop/coverage.csv'
                    with open(where_to, 'a') as csvfile:
                        csvwriter = csv.writer(csvfile)
                        csvwriter.writerow(pnt_list)  ```

As seen, the function new mirror has a for loop that has within it zoner which has a for loop in it as well. Is there any way to make my algortihm faster, the quadtree search can provide a little over a 1200+ points at a time. Can I get what I want without need of the nested for loop?

[fiery cosmos]

We don't give the answer to School questions, we help you understand it.

[harsh wasp]

@fiery cosmos it's not a school question, I have an exam tmrw, so I'm trying to understand it, with the answer I can try to figure out how to do them

However for this particular question I have already understood it, ty!

[celest zenith]

help me with this error please

[barren magnet]

pip install discord

• this isn't the place to ask that question, keep the questions in their respective channels

[fickle jolt]

How can we solve Non Linear Optimization Problem?
Does anyone have idea?

open to talk

[lament shale]

class Solution:
    def elemenate_loosers(self, contestants: list[int], k: int) -> int:
        if len(contestants) == 1:
            return contestants[0]
        diff = k
        while diff >= len(contestants):
            diff -= len(contestants)
        contestants[:] = contestants[diff+1:] + contestants[:diff]
        return self.elemenate_loosers(contestants, k)
    
    def findTheWinner(self, n: int, k: int) -> int:
        players = [_ for _ in range(1, n+1)]
        winner = self.elemenate_loosers(players, k-1)
        return winner

Can anyone help me figure out the time and space complexity of the code?

[onyx umbra]

isn't this an infinite loop? length of contestants is not changing

[lament shale]

Nope

[onyx umbra]

len(contestants) == 1 will never reach

[lament shale]

My code works perfectly

This is the code

[onyx umbra]

then its O(n^2), O(n) for each recursion times O(n) for creating contestants in each call

[lament shale]

O(n^2) space right

?

[onyx umbra]

both

contestants[:] = contestants[diff+1:] + contestants[:diff] time for this is O(n)

[lament shale]

Cool, Thanks bro

[lament shale]

But isn't time for this is O(diff)

I mean then Time would be O(n * diff)

[onyx umbra]

yeah but each time lenght of contestants is decreasing by one, diff only decides from where that element is removed.

[lament shale]

Yeah then, thats what time it should take, creation of list is O(1) Time and O(n) space I think

[onyx umbra]

creation of list is not O(1) time, it is O(n)

O(n) space if u do not consider function call stack

[lament shale]

Cool Thanks again

[onyx umbra]

since recursion isn't doing anything here, you can include everything in while(len(contestants) > 1) to eliminate recursion then space complexity will be O(n)

[mortal rampart]

i = 1
for i to (sqrt(n)+log(n)):
for j = i to sqrt(n):
do something

Is this one O(n^2)?

[agile sundial]

why do you think it's O(n^2)?

[onyx umbra]

it will be O(n), because O(sqrt(n)+log(n)) == O(sqrt(n)) and O(sqrt(n))*O(sqrt(n)) == O(n)

[runic tinsel]

it's not totally obvious though
oh, the inner loop can't even start past i=sqrt(n), you absolutely ignore the log

[wise vale]

Challenge with lists of interconnected item. It's IRL problem actually, that I can't find a solution that doesn't include creating several undirected graphs. The first is a list of lists of items that are connected somehow. The second is a list of groups of interconnected items. It's not an exercise or an interview question but could easily be.

# turn this
connected = [
 ['A', 'B'],
 ['A', 'C'],
 ['B', 'C'],
 ['D', 'C'],
 ['M', 'L'],
 ['N', 'L'],
 ['L', 'K'],
]

# into this
groups = [
  ['A', 'B', 'C', 'D'],
  ['K', 'L', 'M', 'N']
]

[agile sundial]

is this just finding connected components?

[mortal rampart]

Feared so 😫

I know I am suppossed to "just ask," but my next question is rather long and originates from my exam. I am 99% certain I will get my first D thanks to this exam.

So would anyone like to help know whether or not, I submitted the right solution? If not I won't "spam" the chat :)

It's about shortest path with two weight functions.

[runic tinsel]

!e

dct = {k:[k] for k in 'ABCDMNLK'}
groups = [*dct.values()]
connected = [
 ['A', 'B'],
 ['A', 'C'],
 ['B', 'C'],
 ['D', 'C'],
 ['M', 'L'],
 ['N', 'L'],
 ['L', 'K'],
]
for x, y in connected:
   if dct[x] is not dct[y]:
       "news to me!"
       dct[x].extend(dct[y])
       old = dct[y]
       for i in old:
           dct[i] = dct[x]
       old.clear()
print(groups)

[halcyon plank]

@runic tinsel :white_check_mark: Your eval job has completed with return code 0.

[[], [], [], ['D', 'A', 'B', 'C'], [], ['N', 'M', 'L', 'K'], [], []]

[runic tinsel]

as dumb as it looks

but probably works

[wise vale]

@runic tinsel OK, lets she if that's a universal solution and applicable also.

[runic tinsel]

the what

[wise vale]

I running for other cases to see if its an accurate solution. If it is man, all credits to you !

[runic tinsel]

you have test cases for an irl problem

oh you meant irl software development

it's too dumb lol

[runic tinsel]

@wise vale it works?

i'm not 100% sure

[wise vale]

I might need some time to tell but it looks like it could work. I do data science not SF. So if it works it works 😋

There is a solution using graph theory but who has time for that?

[runic tinsel]

for x, y in connected:
   gx, gy = dct[x], dct[y]
   if gx is not gy:
       if len(gx)<len(gy): gx,gy=gy,gx
       gx.extend(gy)
       for i in gy:
           dct[i] = gx
       gy.clear()
```minor optimisation then

update the larger list with the smaller, not randomly

[glacial locust]

hi guys
How can I draw 5x5 empty square using * in phyton?

like this

[neon roost]

""" Fourier Transform """
def FFT(f):
    return npfft.fft(f)

def iFFT(f):
    return npfft.ifft(f)
""" Operator """
def Ukick(x,f,K):
    Uk = np.diag(np.exp(-1j*K*np.cos(x)/kb))
    return np.dot(Uk, npfft.fftshift(FFT(npfft.ifftshift(f))))

def Uprop2(x,f,b):
    """" Takes the parameter beta into account to get an average value """
    Up = np.diag(np.exp(-1j*(x + kb*b)**2/2/kb))
    return np.dot(Up, npfft.fftshift(iFFT(npfft.ifftshift(f))))

""" Sequence """
def loop2(x,p,f,K,b):
    """" Takes the parameter beta into account to get an average value """
    Uk_f = Ukick(x,f,K)
    Up_f = Uprop2(p,Uk_f,b)
    return Up_f

def finalDistrib2(x,p,f,K,n,b):
    """ Takes the parameter beta into account to get an average value """
    res = f
    for i in range(n):
        res = loop2(x,p,res,K,b)
    return res  

def Dot(p,P):
    """" P is the final distribution of Ψ """
    return np.dot(p**2, P)``` first part
```python
N = 100
K = 15

p = np.linspace(start=-N, stop=N, endpoint=False, num=2*N)
init = np.zeros(2*N)
init[N] = 1 # Dirac initial distribution
x = (2*np.pi)/(2*N) * p``` second part
```python
T = (np.linspace(0,400,400, endpoint=False, dtype=int)).tolist()

fig = plt.figure()
plt.title('<p²> as a function of the number of Kicks') 
plt.xlabel('kicks')
plt.ylabel('<p²>')

Sigma = np.zeros(len(T))
Beta = np.random.uniform(low=-0.5, high=0.5, size=(150,))
Sigma_avg = np.zeros(len(T))

for b in Beta:
    for i in range(len(T)):
        #print(t[i])
        Sigma[i] = Dot(p,abs(finalDistrib2(x,p,init,K,T[i],b)))
    Sigma_avg += Sigma

Sigma_avg /= len(Beta)    
    
plt.plot(t,Sigma_avg)
plt.show()``` And final part

So

I'm currently struggling with this because it's very slow

I hate using loops with numpy but I don't see how I could avoid them

Would anyone know how?

[dreamy turtle]

I am currently working on a program that needs to extract prices history data from every symbol in my database which is 19,400+ symbols. I am having issues getting the program to work properly. I am trying to get the program to retrieve the price data, then insert the data into the appropriate table. I am retrieving the data from TD Ameritrades API. I have to make call the method 1 symbol at a time. I have tried creating a generator, queue, using map, processes and almost everything I can think of. I couldn’t add the code bc it’s too long but you can view it at the link below. I would REALLY APPRECIATE it if anyone could tell me what I am doing wrong. This is the link to the pastebin: https://paste.pythondiscord.com/ikovuzavoz

AGAIN, I REALLY APPRECIATE ANY HELP!

[next snow]

Hi, can anyone tutor me on dp?

[terse spade]

i've been looking, but is there for god's love any way to get either the contents or the ast of procedurally generated function (example given, a decorated function (note : this is not what my case is)).
rn i'm trying to get uncompyle6 to work but my code "does not smell like code"

[eager hamlet]

so uh

https://www.geeksforgeeks.org/internal-working-of-list-in-python/#:~:text=Python lists are internally represented,if preallocated space becomes full

are they right?

is repeated appending actually slower than just making an array right at the start?

[fiery cosmos]

In practice probably yes because it can take advantage of knowing it has to allocate all that memory at that moment. But in theory it shouldn't make much difference. Appending is constant time O(1) amortized anyway.

[eager hamlet]

k cool

[fiery cosmos]

And for only 151 elements the difference is likely not enough to really matter 🤷‍♂️

[eager hamlet]

i ran a timeit and found that like

one was better than the other by over 10x

[fiery cosmos]

Appending is 10x slower? Possible

Though the gal is mistaken when he says python creates a new static array every time you append

it's amortized, meaning new arrays are made but only once in a while so it averages out to O(1) (and not O(n))

[eager hamlet]

(they're a girl)
but yeah, i knew that

thx for the insight

[signal knot]

Given an array and a value, remove all instances of that value in-place and return the new length. does removing all instances in-place include swapping the value with another value?

[haughty mountain]

like, if you know the final size just make a list that size

sadly python doesn't expose a reserve method like C++ vector

it would be great for this kind of case

[lean dome]

The closest you can get is [None] * n

[lean dome]

Yes, as implied by the length changing.

[haughty mountain]

which isn't close at all

the usage for a reserve would be to reserve space for elements and then append/extend

the list struct has a capacity field and could expose this kind of functionality, it just doesn't

[lean dome]

Sure, but you can accomplish the same by pre allocating as much space as you need, overwriting elements with your final values, and deleting any values you don't need at the end. It's a different interface, but achieves the same big o runtime and space complexity

[haughty mountain]

it's not so much about what you can and can't express, it's that you can make the optimization without having to change the existing code

[lean dome]

Sure.

[haughty mountain]

and there is technically a small difference, you end up initializing pointers to None, while reserve could just leave whatever was in memory, not that this matters in python because you have way bigger overheads

I've seen this matter in some high performance C++ cases

same scaling though, of course

just constant factor optimization

[lean dome]

That's a difference, but one that doesn't affect the big o complexity in the end, assuming you wind up writing to every element in the end, since O(2n) is O(n)

Right, yeah, what you said 🙂

[glad vale]

Hello I need help with another problem.

N cities are given, each city is surrounded by a wall with two gates: north
and south gate. If you enter a city through one of the gates, you must leave through the other gate.
By leaving each of the gates, one can go directly to one or more other cities.
Please propose and implement an algorithm that checks whether leaving from one of the
cities you can visit all cities exactly once and return to the city from which you
set out from.

So it's basically Hamiltonian cycle search algo for me. So it's NP-problem.

Why did my professor say the complexity of the algorithm is not bigger than O(n^2) as a hint??

What is the solution for this??

I though about checking if the bridge exists in graph if so there is no cycle.
And all the conditions for Hamiltonian graphs like Dirac's theorem etc.
But i guess this it's wrong way.

The connection network is given as a list that, for each
city contains two lists: cities accessible from the north gate and cities accessible from the
south gate. Cities are numbered starting at 0.

G = [ ([1],[2,3,4]),
([0],[2,5,6]),
([1,5,6],[0,3,4]),
([0,2,4],[5,7,8]),
([0,2,3],[6,7,9]),
([1,2,6],[3,7,8]),
([1,2,5],[4,7,9]),
([4,6,9],[3,5,8]),
([3,5,7],[9]),
([4,6,7],[8]) ]

Result: [ 0, 1, 5, 7, 9, 8, 3, 2, 6, 4 ]

[haughty mountain]

it feels like some constraint is missing, since the general problem indeed seems like a Hamiltonian path problem

visiting all edges would fit the complexity stated, but doesn't match the problem statement

[glad vale]

and south gate. If you enter a city through one of the gates, you must leave through the other gate.```
Seems like something to take into consideration but then we have
`By leaving each gate, you can go directly to one or more other cities.`
So yeah it's really weird one

Maybe it's task to finally break the Hamilton cycle problem and get Turing Award 😂

[glad vale]

Hey I need to know only of the cycle exist not how it looks. So there is Palmer's algorithm. ( I found it on Wikipedia while reading about Ore's theorem ).
Is there more algorithms like that one?

[fervent saddle]

Are they talking about this as the alternative?

a, b, c = [], [], []

for _ in range(MAX_PASTURE):
    a.append(0)
    b.append(0)
    c.append(0)

Because if they are, the version shown in the image is also faster because it avoids any loop in python. It initializes all the values through compiled code instead.

I think it’s able to take advantage of cache locality too, because it’s just copying the pointer a number of times

[glad verge]

Guys im struggling with data structure

[dark notch]

?

what's problem?

[glad verge]

Hash tables and other stuff

I also have a problem that

I would learn some concepts and understand them

And then I'd come back

And not understand them

Simple concepts like nested loops

And other

[haughty mountain]

that doesn't make the problem much easier

was the thing you posted the exact formulation you were given?

[glad vale]

I don't understand.

[haughty mountain]

as written it is about if there is an Hamiltonian cycle, which is a very hard problem

so I'm asking if what you wrote was exactly the task you were given

or if the original wording was different

[glad vale]

I get this problem like that we have (north_gates, south_gates) if we enter through one of notrh_gates we have to choose one in south_gates.
A ([1,5],[2,3,4]),
B ([0,7],[2,5,6]),
So if we entry 1 -> we can chose one of ( 2,3,4) gates
if we entry 5 we can chose one of (2,3,4)
And Then we can entry through south or north. So let's assume we entry from 5 -> 2
and now we entry from south_gates so we can pick 0 or 7

If we entry one of [2,3,4] we can choose one from [1,5]

[glad vale]

It's exactly that what i was given

So we have some constrains here because when we entry from one gate (South for example G[1]) we must leave through one of North gates ( G[0] )

But how to take advantage of this 🤯

It's really weird one

[haughty mountain]

it's not much of a constraint at all

[glad vale]

I see :/

[turbid jetty]

Could anyone help me solve this HackerRank problem?

Lexicographical order is often known as alphabetical order when dealing with strings. A string is greater than another string if it comes later in a lexicographically sorted list.

Given a word, create a new word by swapping some or all of its characters. This new word must meet two criteria:

• It must be greater than the original word
• It must be the smallest word that meets the first condition
  I'm not solving it at all. Does anyone have any tips? How do you organize your thoughts and ideas?
  One string in lexicographical order is greater than another if some item in the same position is greater than an item in the same position in the other string. Right?
  But still there is no idea how I can sort this string.
  😢

Link: https://www.hackerrank.com/challenges/bigger-is-greater/problem

[vocal gorge]

I think all you need to do is to try sorting increasingly large suffixes of the string in descending order nah, that's sufficient but not quite the smallest

[runic tinsel]

make up a word, find its permutations, sort and look at the list

you need to find the pattern

oh i misunderstood

[vocal gorge]

I think you got it right

[runic tinsel]

yeah just that

[turbid jetty]

I didn't understand the part about the increasing suffix

[turbid jetty]

okay

I'll try this and get back to you

[runic tinsel]

...
atelr
aterl
atler
atlre
atrel
atrle
ealrt
ealtr
earlt
eartl
eatlr
eatrl
elart
...

yeah, that's not very simple

0 4 2 1 3
0 4 2 3 1
0 4 3 1 2
0 4 3 2 1
1 0 2 3 4
1 0 2 4 3
1 0 3 2 4
1 0 3 4 2
1 0 4 2 3
1 0 4 3 2
1 2 0 3 4
1 2 0 4 3
1 2 3 0 4
1 2 3 4 0

at least see it as numbers

[turbid jetty]

What do you think?

import itertools

def biggerIsGreater(string):
    # 1. I converted the string to a tuple of characters to compare with the permutations.
    stringTuple = tuple(string)
    
    # 2. I tried to generate all permutations of the string.
    permutations = itertools.permutations(stringTuple)
    
    # 3. I sorted all the strings, lexicographically, from smallest to largest.
    sortedPermutations = sorted(permutations)
    
    # 4. I removed all strings from the list that are less than or equal to the string itself.
    filteredPermutations = list(filter(lambda current: current > stringTuple, sortedPermutations))
    
    # 5. I just returned the first element in the list (converted to string) or warning that there is no answer.
    return "".join(filteredPermutations[0]) if len(filteredPermutations) > 0 else "no answer"

The problem is that it is very slow...

Only 4 HackerRank tests worked.

[vocal gorge]

yeah, that's not going to pass the time limits. the number of permutations of an n-element sequence scales faster-than-exponentially, as n!.

[turbid jetty]

Which string is this from?

[runic tinsel]

it's a small portion of the full 120 list

it's for any string of length 5

that's not how the solution is supposed to work, that's how you can get to the solution

like, "try to solve this instead" sorta

only it's not a simpler version but the same thing

[turbid jetty]

Should I find a pattern in this list of integers?

And from this I arrive at the answer? From what I understand

[runic tinsel]

yeah pretty much

[turbid jetty]

well... at first he just swapped the last two characters around

[runic tinsel]

there's no "memory", every line only requires the previous one

[turbid jetty]

good point

[runic tinsel]

you don't need to know if you "already did that once" or whatever

[turbid jetty]

Maybe I can think of recursion?

since you only need the previous one to generate the next one

def f(x):
  newX = # do something, maybe to increment the string?
  nextX = f(newX)
  # ....

[runic tinsel]

i'm sorry how is that going to help

you're skipping the problem for the second time

[turbid jetty]

for sure

[runic tinsel]

ok, here's the solution
1 0 4 3 2
1 2 0 3 4

he found the last number that has a larger one immediately after it → 0
he found the last number that's larger than 0, going after 0 → 2
he swapped them → 1 2 4 3 0
and finally he reversed the order of the "tail", starting from the 4

this is exactly the rule

[turbid jetty]

what did you use to realize this?

[runic tinsel]

nothing

i didn't, i knew this from wikipedia, it's not an easy task

[turbid jetty]

can you send me the link to the article?

[runic tinsel]

https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

[turbid jetty]

thank you

do you think you could solve this without research?

[runic tinsel]

no

i would give up

[turbid jetty]

oh yes

I have been trying to solve it for 3 weeks

I didn't want to look at the direct solution, because I am trying to learn how to solve problems

[runic tinsel]

i maybe could if this was ultrainteresting to me for some reason, but it's not

[turbid jetty]

oh yes

[haughty mountain]

I think the solution is:
find first adjacent pair (x, y) from the right that has x < y, swap them, and then sort the "tail"

e.g.

adecb
a(de)cb # swap pair d < e
ae(dcb) # sort tail
aebcd

oh, someone mentioned it just above

the motivation is that you want to keep as much of the prefix the same as you can

so swap the first thing from the right you can swap

and then minimize the tail

[runic tinsel]

thanks

it's not quite right, though

[haughty mountain]

counter-examples?

[haughty mountain]

oh, I guess you swap with the smallest largest element on the right

but other than that, it's correct

my code from like 5 years back

t = int(input())

def task(s):
    i = len(s)-2
    while i >= 0:
        if s[i] < s[i+1]:
            _,j = min((el,ix) for ix,el in enumerate(s) if el > s[i] and ix>i)
            s[i],s[j] = s[j],s[i]
            s[i+1:] = sorted(s[i+1:])
            print(''.join(s))
            return
        i -= 1
    print('no answer')

for _ in range(t):
    s = [x for x in input()]
    task(s)

[rough lynx]

Is there any reason to use a queue over a list if I'm pre-populating my list/queue and only popping elements without any future insertions?
I figured a queue is built to more easily and reliably put into and get from compared to pushing into / popping out of a list, but if I'm only removing elements as they are used, is there any reason to use a queue?

[fiery cosmos]

wtf is this

ඩ

AMOGUS

ඩඩඩඩඩඩඩඩඩඩඩඩඩඩඩඩඩඩඩඩඩඩඩඩඩඩඩඩඩඩඩඩ

I am from Ukraine!

https://open.spotify.com/playlist/6gAhTDl8Kvw930Hbk6RMH7?si=fa264516a5ac4852&pt=b14f50f86a99da2180716e757741185a

listen the best Ukrainian songs

ඩඩ

[halcyon plank]

:incoming_envelope: :ok_hand: applied mute to @fiery cosmos until <t:1652952586:f> (9 minutes and 59 seconds) (reason: duplicates rule: sent 4 duplicated messages in 10s).

[vocal verge]

Please don't spam channels. Also, stick to the channel topics, please.

!unmute 935146485908135947

[halcyon plank]

:incoming_envelope: :ok_hand: pardoned infraction mute for @fiery cosmos.

[fiery cosmos]

thx

idk where is global chat

[vocal verge]

for general Python discussion there is #python-discussion

for random topics

!ot

[halcyon plank]

Off-topic channel: #ot2-never-nester’s-nightmare

Please read our off-topic etiquette before participating in conversations.

[crimson steeple]

tbh how do i change to from c to python

i learnt structs and pointers and malloc

in data structs and algos

[haughty mountain]

i.e. just going through the elements in reverse order?

[rough lynx]

My case is basically this:

my_container = []
for x in some_variable:
  for y in other_variable:
    my_container.append(tuple(x, y,),)

while len(my_container) > 0:
  pair = my_container.pop()
  # do stuff with pair[0] and pair[1]

[haughty mountain]

so yes, this is just going through things in reverse

you could even ship generating the whole thing into a list

for x in reversed(some_variable):
  for y in reversed(other_variable):
    # do stuff with x and y 

[haughty mountain]

and fwiw that is using a list as a stack and not a queue

[shut pebble]

How can I replicate the behaviour of current_app or request in flask? Is using werkzeugs LocalProxy correct outside of a wsgi context?

[shut breach]

this channel is about algorithms and data structures, but you could ask in a more appropriate topical channel like #web-development

[onyx parrot]

I'm trying to solve House Robber but so far my "ideal" solution is

1. finding the max in the array
2. register the max
3. exclude the house and the adjacent houses
4. rince and repeat

isn't there any other way to make the algorithm more efficient?

[onyx parrot]

My previous attempts were checking out the biggest number between index n and index n+1 but I locked myself in a sub-optimal solution.

[stiff thicket]

Hey, I'm trying to build a data structure with the following methods:

def initialise(limit: int): ...
def add_item(obj): ...
def remove_item(obj): ...
def get_least_frequent_items() -> List[Any]: ...

Basically what I want is topk but in reverse, and I'm not sure if there's a good algorithm for it. Any suggestions?

[vocal gorge]

Least frequent? Not the smallest?

[stiff thicket]

yes

Preferably using the least amount of memory as possible

[chrome quartz]

I'm doing the invert binary tree on leetcode (https://leetcode.com/problems/invert-binary-tree/). I was wondering how we can tell by looking at the array that 1, 3 are child nodes of 2, and 6, 9 are child nodes of 7, and that 2,7 are child nodes of root 4.

[4,2,7,1,3,6,9]

Trees seem so overcomplicating to me.

[agile sundial]

it's written level order, first the root, 4. then the next level under it, and so on

    4
  2    7
1  3  6  9

[keen hearth]

You mean level order I think Pub. In-order would be [1, 2, 3, 4, ...].

https://support.leetcode.com/hc/en-us/articles/360011883654-What-does-1-null-2-3-mean-in-binary-tree-representation-

[agile sundial]

ah

[merry kelp]

anyone know cryptography encryption decryption in python?

[keen hearth]

Hey. It's best just to ask your question.

[fallen wing]

do you guys think hackerrank is a good practice site

just to see what skill level you are I guess

[dapper sapphire]

Good Lord man, even no name companies want to test you on ds & algos 🤦‍♂️

[next loom]

I'm trying to make a table where one of the columns of said table is gonna match the id number of the corresponding number in the first column. I'm bad at explaining but here is the code and hopefully it makes sense ```python
import numpy as np
import math

t = np.zeros((20,2))
d = [19,17,33,36,15,1,3,5,7,22,28,20,16,14,37,6,8,9,25,26]
d.sort()
t[:,0] = d #these numbers are in the first column of table g
t[:,1] = [4,4,4,2,4,1,1,3,2,2,1,1,3,3,3,1,2,2,4,4] #id's of table t

g = np.zeros((40,3))
g[:,0] = list(range(40))
print("here is table t")
print(t,"\n")
print("here is table g")
print(g) #I want the third column of table g to get the id numbers of the
#matching numbers of the first column of table t ```

[[ 0.  0.  0.]
 [ 1.  0.  4.]
 [ 2.  0.  0.]
 [ 3.  0.  4.]
 [ 4.  0.  0.]
 [ 5.  0.  4.]
 [ 6.  0.  2.]
 [ 7.  0.  4.]
 [ 8.  0.  1.]
 [ 9.  0.  1.]
 [10.  0.  0.]
 [11.  0.  0.]
 [12.  0.  0.]
 [13.  0.  0.]
 [14.  0.  3.]
 [15.  0.  2.]
 [16.  0.  2.]
 [17.  0.  1.]
 [18.  0.  0.]
 [19.  0.  1.]
 [20.  0.  3.]
 [21.  0.  0.]
 [22.  0.  3.]
 [23.  0.  0.]
 [24.  0.  0.]
 [25.  0.  3.]
 [26.  0.  1.]
 [27.  0.  0.]
 [28.  0.  2.]
 [29.  0.  0.]
 [30.  0.  0.]
 [31.  0.  0.]
 [32.  0.  0.]
 [33.  0.  2.]
 [34.  0.  0.]
 [35.  0.  0.]
 [36.  0.  4.]
 [37.  0.  4.]
 [38.  0.  0.]
 [39.  0.  0.]]```

I bascially want he third column in my table g to look like the one above

is there a clean way to do this?

[violet eagle]

putting this before print(g) works (there might be a numpy one liner but im not aware of any)-
for item in t: g[int(item[0])][2] = item[1]

[fiery cosmos]

Hi I'm new what do I do

In the server

[violet eagle]

read stuff, ask for help if you need it in appropriate channels or help people out if you know an answer

[idle dune]

Hi, I've studied few data structures in my college (Stack, Que, Linked List),
I understand how they work theoretically however don't understand what is the need for them in real life?

Also at which point should one start implementing data structures into their programs?

[unkempt shadow]

please say a book to refer for python programming for beginners?

[agile sundial]

automate the boring stuff

[frozen sleet]

I can't seem to develop an intuition to code up the sliding window...anyone got any good resources?

[haughty mountain]

sliding window as in add stuff in front and remove at the back to slide the window along?

it's literally just that

e.g. if you do a sliding sum with window size k you first compute the sum of the first k elements, and then to move it a step to the right you add the element at k and subtract the element at 0

and to move it another step add the item at k+1 and subtract the item at 1

[frozen sleet]

yeah I think the way I am thinking about it python wise....I'm slicing the lists like this

list[start:end]

but every resource I see doesn't slice it that way

[frozen sleet]

I think this is what I need to internalize better

[haughty mountain]

what you will be computing (but more efficiently) is f(list[0:k]), f(list[1:k+1]), f(list[2:k+2])

for some f you can easily add/remove the contribution from some particular element

e.g. if f is sum you can add and subtract to add/remove contribution from items

[frozen sleet]

thanks man that helps

[haughty mountain]

if it was a product you can (mostly) multiply and divide

and so on

the important thing is that you can add and remove contribution, which allows you to slide the window around by only operating on the head and tail of the window

[whole roost]

neetcode in youtube is good

[solid island]

How can I write an abstract syntax tree? I'm pretty confused about hat. Can someone inform me?

[half lotus]

You should start by defining a class for each type of node you need in your tree. For example, to represent 1 + 2 in an AST you'd need a node for the + operator (or more generally a binary operator node) and a node for an integer (or more generally a node for some constant). The + node would have two class attributes: one for the left operand and one for the right. When the + node is created, it will need to be given the two integer nodes.

[keen hearth]

It's useful general knowledge when you're writing programs. Knowing the right data-structure to use in a given situation can make a huge difference to the performance of your code, particularly when you have to scale to larger problems. Also, learning about algorithms has the side-effect of improving your ability to reason about the correctness of code.

[stark stone]

it's almost more like... "gosh what can't you build with the right data structures and algorithms?" 🙂

a lot of times a problem becomes trivial with the right data structure, for example, and really hard and convoluted with the wrong one

[dapper sapphire]

!e

from typing import List
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        array_2d = [[]]
        for i in range(len(nums)):
            for j in range (len(array_2d)):
                num = nums[i]
                inner_array = array_2d[j]
                array_2d.append(inner_array + [num])
        return array_2d

nums = [1, 2, 3]
print(Solution().subsets(nums))

[halcyon plank]

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

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

[dapper sapphire]

Is this approach considered backtracking?

Can this approach be used to tackle common backtracking questions?

[hard reef]

Is it possible to get a list of class attributes that are uninitialized? I have something likeClass A: a: int b: str c: intBut dir(A) doesn't return those attributes unless they are initialized. Is there any way to do it?

[keen hearth]

__annotations__?

https://docs.python.org/3/howto/annotations.html

[hard reef]

I dont know how I missed that. Thank you. I've only just started getting deep enough into python start using dunder methods/fields like this.

[haughty mountain]

no, what part of it would it be backtracking?

[dapper sapphire]

It isnt backtracking because it doesnt use recursion. But I thought it could be considered backtracking since it traces back each time to create a new list/array.

If recursion is necessary for backtracking then the above approach wouldnt be backtracking.

We would call it iterative?

[half lotus]

I don't think recursion is necessary for backtracking since any recursive solution can be rewritten in an iterative manner.

Anyway, a key aspect of a backtracking algorithm is that it tries some value, and if it realises it's not valid, it goes back to the previous step and tries a different value. Effectively, it tests a value and discards it if needed.

Your code doesn't seem to be doing that.

[dapper sapphire]

oh ok that's a pretty good point!

If I do more questions with this approach, I'll implement a discarded to see if it works or not.

[half lotus]

It's not applicable to all problems, keep that in mind.

Not sure what you're trying to solve.

[dapper sapphire]

What's not applicable to all problems?

I was just trying to figure out a template that could solve several different backtracking questions. But I think even if we use backtracking that goes back to previous step, even with that approach we would still have to modify the backtracker based on the question requirement?

[half lotus]

A backtracking algorithm

[dapper sapphire]

Oh ok.

[half lotus]

There seems to be a generic approach outlined here https://en.wikipedia.org/wiki/Backtracking#Pseudocode

[solid island]

ok, I got that. I'm trying to define a loop that can call itself. After creating AST, shouldn't I define a method that makes it do the action I mentioned? How can I do that? Should I define the method in AST?

[frail valve]

Signals and Systems - 2nd Edition - Schaums Outline Series - Hwei Hsu...... has anyone ever read this book OR something like it .... advanced math for dignal processing

signal processing

[half lotus]

What do you mean by a loop that calls itself? Like recursion?

I'm not sure how that relates to an AST

[solid island]

yes, I meant recursion. I'm writing a parser and the program can parse the loop command but can't run the loop action properly. Therefore I'm trying to use AST, I thought if I connect the rules with nodes, it can run the action properly.

@half lotus If you want to see code, here is: https://github.com/euleriscoding/A-Parsing-Trial/blob/main/parsing.py I think AST doesn't work properly. Can you check that what exactly is the problem?

[dapper sapphire]

Questions that require backtracking are also dp questions?

[fiery cosmos]

Not necessarily. e.g. solving a Sudoku involves backtracking but I don't think it's dp

[dapper sapphire]

ok

[half lotus]

What is the loop action (p_loop) supposed to do?

The code is difficult to read because a variable name like p says nothing, and it's not clear what any of the indices mean. I am guessing that the AST node needs to be assigned to p[0]?

[foggy fiber]

could anyone take a look at my A* algorithm and tell me what im doing wrong

[spring cloud]

Hi, so I've been trying to write an in-place implementation of quicksort with the lomuto partition scheme, but I can't seem to get it to work.
I've followed the pseudocode provided in the wikipedia article for quicksort, but my implementation doesn't seem to work as intended. Could someone possibly read through my code and check if I've done anything wrong?
https://pastebin.com/hZ8TbXPy

[grand marten]

Hey guys how do you print front and rear of a queue?

New to Datastructures

[short carbon]

yo can anyone here help me with the insertion sort code in python

Insertion Sortlist = [2, 1, 5]length = len(list)for i in range(1, length - 1): data_to_insert = list[i] inserted = 0 next_value = i - 1 while next_value >= 0 and inserted != 1: if data_to_insert < list[next_value]: list[next_value + 1] = list[next_value] next_value = next_value - 1 list[next_value + 1] = data_to_insert else: inserted = 1print(list)

i cant get my self to understand it reslly

[onyx umbra]

front: queue[0] , rear: queue[-1]

[solid island]

p is a part of yacc file and represents parsing and yes, AST node should assign to p[0]. p[0] represents the rule.

[fiery cosmos]

hello, can anybody help me with my code regarding minheap and prims algo?

[random sedge]

i dont know if this is the right channel but i wasnt able to get help from the help channels so i was hoping someone here could help please

    """remove header row, convert values to float unless specified, then convert to tuple"""
    
    #convert to dataframe
    dataframe1 = pd.DataFrame(data, columns = ['0','1','2','3','4','5','6','7','8'])

    #code to remove header
    dropped = dataframe1.drop(0, axis=0)

    #code to convert all columns to float other than those specified by index
    update = dropped.astype({'0': 'unicode30','1': 'unicode30','7': 'unicode30','8': 'unicode30'})
    update = dropped.astype({'2': 'f8','3': 'f8','4': 'f8','5': 'f8','6': 'f8'})

    #code to convert every row into a tuple
    data1 = update.to_records(index=False)
    data = list(data1)
    
    return data```

i am trying to use this code to do a few things but my problem is with the part that is involved in turning certain columns to type <U30 and other columns to float64

i am fine with the float part and my code works for that

however, the line of code involved with turning some of the columns in the dataframe to type <U30 is not working and instead i am getting type object

how do i resolve this issue?

[half lotus]

So why do you have a while loop in there? Presumably it should only be generating one Loop node.

[solid island]

What can I do then? I created another three.

[solid island]

    pass
class Start(Node):
    def __init__(self,start):
        self.start=start

class Loop(Node):
    def __init__(self, number, stmt):
        self.number=number
        self.stmt=stmt

def p_start(p):
    '''start : function 
             | option
             | errormessage'''
    
    p[0]=Start(p[1])
def p_loop(p):
    'loop : LOOP NUMBER LSQB start RSQB '
    i=1
    while i<=p[2]:
        p[0]= Loop(p[2],p[4])```

[half lotus]

I don't totally follow your code but I am guessing what you need to do is something like ```py
def p_loop(p):
statement = p_start(p[4])
p[0] = Loop(p[2], statement)

Basically, parse the statement into a `Start` node, and then pass that `Start` node into a new `Loop` node. And that's it. But I am not sure how YACC works exactly.

[solid island]

Thanks but how can I make 'loop' an actual loop? There is a number which represents how many times does the loop run and there is a start statement. Let's say I connected these nodes each other, then how can I call start statement in a while loop?

[half lotus]

That's out of scope for a parser. What you're talking about would be the responsibility of an interpreter or code generator, depending on what kind of language you're designing (interpreted vs compiled)

The parser just needs to generate an AST. Once you have the AST, it can be fed to other components like a typechecker, interpreter, or code generator

@solid island

If it's an interpreted language then you'd have something like ```py
def evaluate_loop(loop_node):
for _ in range(loop_node.number):
evaluate_start(loop_node.stmt)

Here is a nice tutorial for a simpler intrepeter. There are also further tutorials about code generators on the right sidebar if you want to go down that route. https://lisperator.net/pltut/eval1/

[somber kiln]

What's a good example of a computationally intensive job? I want something I can use to demo batch job submission. Something like computing digits of PI, but it would be better if it had multiple independent tasks

[half lotus]

How about computing hashes of many files in a directory. Or is the disk I/O more of a bottleneck there?

Or perhaps something to do with media processing, such as video encoding

3D renders, etc.

[somber kiln]

Oh 3D render might be good, like a software raytracer

[last fulcrum]

I'll like to know what is the runtime of this algorithm. Does the while loop make it quadratic?

def totalFruit(fruits: list[int]) -> int:
    baskets, start, max_fruits = {}, 0, float("-inf")
    
    for index, fruit in enumerate(fruits):
        
        baskets[fruit] = baskets.get(fruit, 0) + 1
        
        while len(baskets) > 2:
            
            baskets[fruits[start]] -= 1
            
            if baskets[fruits[start]] == 0:
                del baskets[fruits[start]]
                
            start += 1
            
        max_fruits = max(max_fruits, index - start + 1)
        
    return max_fruits if max_fruits > float("-inf") else 0

[half lotus]

I'm not sure but try to think of the worst case for inputs for the second loop.

For example, alternating pairs would cause the while loop to go for longer than if it was just straight i.e. ["A", "B", "A", "B", "C", "D", "C", "D", "E"] makes it take longer than ["A", "A", "B", "B", "C", "C", "D", "D", "E"] but not sure if that is the worst possible case still.

[vocal gorge]

The while loop itself is already quadratic in len(baskets), because del baskets[fruits[start]] is linear.

[agile sundial]

is this just finding the max value in fruits? i'm so confused what this is doing

[half lotus]

baskets is a dictionary so I don't think so

Assuming that the alternating fruits as I showed is the worst case (important for there to be an odd number of unique fruits), then the runtime complexity is ```
O(unique_fruits * count_per_fruit + [(unique_fruits - 1) * count_per_fruit] - 1)

So, not quite n^2 (where n is the length of fruits) but pretty close

[vocal gorge]

ah, right

[half lotus]

So it simplifies down to 2n^2 - n - 1 when unique_fruits = count_per_fruit, and since for big O lower order terms and constants are dropped, it is essentially n^2

Maybe there is an even worse case input, but we know it's at least O(n^2) worst case

[frozen sleet]

Hey guys...noob question. Can anyone help me interpret the BigO for the code below? Specifically the call to this line if arr[i] > arr[i + 1]

arr = [1, 2, 3, 4]

for i in range(len(arr)):
    if i != (len(arr) - 1):
        if arr[i] > arr[i + 1]:
            print("Greater")
        else:
            print("Smaller")

[half lotus]

That line in particular is constants so O(1)

Array lookups via index are constant, and so is a > comparison between ints

[frozen sleet]

Even if I revisit that element again in the next iteration?

[half lotus]

Well no, if you visit it n times then it becomes O(1 * n) = O(n) for example

[frozen sleet]

Ah okay. So overall this is O(n)

[prime sequoia]

For i in range(len(n)):

[half lotus]

Yeah, where n is the length of arr

[frozen sleet]

Cool, thanks!

[open moth]

import matplotlib.pyplot as plt
data = {}
#data[(10, 10)] = [0.55, 0.45, 0.25]
#data[(10, 20)] = [0.2, 0.5, 0.3]
data[(50, 50)] = [0.55, 0.45,0]
#data[(20, 20)] = [0.6, 0.15, 0.25]
#data[(30, 10)] = [0.4, 0.35, 0.25]
#data[(30, 20)] = [0.5, 0.1, 0.4]

labels = ['Frogs', 'Hogs', 'Dogs']
explode = [.2]*3
colors = ['gold', 'beige', 'lightcoral']
radius = 30
margin = 0

fig, ax = plt.subplots()

for x,y in data.keys():
    d = data[(x,y)]
    ax.pie(d, explode=explode, colors = colors, center=(x,y), 
            shadow=True, startangle=90, radius=radius, 
            wedgeprops = {'linewidth':0, 'edgecolor':'Black'})

    ax.annotate("({},{})".format(x,y), xy = (x, y+radius), 
                xytext = (0,5), textcoords="offset points", ha="center")

ax.set_frame_on(True)
xaxis = list(set([x for x,y in data.keys()]))
yaxis = list(set([y for x,y in data.keys()]))
#xaxis = 100
#yaxis = 100
ax.set(aspect="equal", 
       xlim=(min(xaxis)-radius-margin,max(xaxis)+radius+margin), 
       ylim=(min(yaxis)-radius-margin,max(yaxis)+radius+margin), 
       xticks=xaxis, yticks=yaxis)
fig.tight_layout()  

plt.plot(30, 70, marker="o", markersize=5, markeredgecolor="red", markerfacecolor="green")

plt.show()

How to draw the plot plt.plot(30, 70, marker="o", markersize=5, markeredgecolor="red", markerfacecolor="green")

why if I draw plt.plot(30, 80, marker="o", markersize=5, markeredgecolor="red", markerfacecolor="green") that outside the axis

[haughty mountain]

how is this not just O(n)? in total the while loop will do at most one operation per element in the list

tl;dr: the main loop adds 1 for every fruit in the list, the while loop removes 1 per iteration

[half lotus]

Here is the sample I was using to test it https://paste.pythondiscord.com/rayamativa

Notice the output has 26 lines. The input has 5 unique fruits and 3 of each fruit.

And if you plug that into unique_fruits * count_per_fruit + [(unique_fruits - 1) * count_per_fruit] - 1 then it comes out to 26

[haughty mountain]

if you phrase it in terms of unique_fruits, sure

but it's bounded by len(fruits)

[half lotus]

Ah yeah i think i confused n^2 for just being the length when I tried to simplify that

[haughty mountain]

e.g. in your example the number of prints in the while loop is < len(fruits)

[half lotus]

So it's 2n^2 - n - 1 but n = unique_fruits = count_per_fruit so n^2 = len(fruit)

[haughty mountain]

I think formulating it in terms of the length of the list is just cleaner, I don't think a reformulation in some other variable gets you anything in this case

[half lotus]

Perhaps ultimately yes, it should be in terms of the length. I did it in terms of unique fruits and counts because it made more sense to me when I was trying to discover a worst-case input.

[haughty mountain]

In this case the worst case isn't really much worse than any other case

Everything is just O(len(fruits))

because you need to loop through the whole list regardless

[half lotus]

Yes but that was not evident until I found the worst case

Maybe it's more obvious to you by reading the code but it wasn't to me so I played around with inputs

[haughty mountain]

It's pretty obvious when you look at things from the right angle, but knowing the right angle to look from isn't obvious 😄

I think this pattern in particular is pretty common, you have a loop in a loop, but the inner loop is constrained such that it's still cheap overall. In this case the inner loop is amortized O(1) per loop iteration (O(n) total)

naively it looks worse than that, but when you see the constraint, things become very obvious

[solid wharf]

is O(k*n) in O(n) if n and k are independent variables and k<=n?

[haughty mountain]

is k a parameter of the input or is it a constant?

it's for sure not true in general, here n and k are independent, and we could let k <= n, but the complexity is O(k*n) and can't be reduced to O(n)

def f(n, k):
  for i in range(n):
    for j in range(k):
      ...

you could bound it by O(n^2) because k <= n

but that's a worse bound

[solid wharf]

It is like your example so it would be O(n^2) in worst case

I understand ty

[void pecan]

Hi! What do yall think of bogo sort?

Just curious

[arctic coral]

does anyone want to help me code something

its only a few lines of code

[agile sundial]

sure

[south elbow]

What is it?

[dark aurora]

Does anyone have a solution to this problem in python

https://cses.fi/problemset/task/1625/

[quasi sapphire]

Learning about sorting algos currently. I am trying to code a mergesort but its obvious its well above me. My main issue is that the way I find implementing recursion very hard. How do I get to the ability to code a mergesort?

[fervent saddle]

You could do it with a while loop instead if that’s more comfortable, it doesn’t need to be recursion

[full sonnet]

While loops are ideal when you can get them anyways because python lacks tail call optimization and recursive functions will have O(N) auxillary space complexity due to callstacks

so if you have to do a while loop don't sweat it, it's better in python

[idle pier]

Hello folks, I'm currently doing 74. Search a 2D Matrix
I have this question by flattening the matrix but it really isn't efficient in terms of time complexity
I found this solution which is a binary search algo and its way more efficient

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        M,N = len(matrix),len(matrix[0])
        l,r = 0,(M*N)-1
        
        while l<=r:
            mid = (l+r)//2
            
            if matrix[mid//N][mid%N] == target:
                return True
            if matrix[mid//N][mid%N] < target:
                l = mid+1
            else:
                r = mid-1
        return False```
where i'm lost is on the `matrix[mid//N][mid%N]` part, I know that `[mid//N]` is for what row your in and the other part is for what column your in but I just don't know how it fully works. Hope this makes sense lol

[runic tinsel]

you're asking to explain division and modulo

you can't have a youtube video for every single thing

(not saying you can't have one for this, there must be many)

[signal knot]

Is this O(n^2)?

def maxProfit(prices):
    right = 0
    maxProfit = 0

    for left, n in enumerate(prices):
        right = left
        while right < len(prices):
            if prices[right] - n > maxProfit:
                maxProfit = prices[right] - n
            right += 1
    return maxProfit if maxProfit > 0 else 0```

[half lotus]

Yes, I believe so. This is just a summation like the following

Which boils down to n^2

Cause the inner loop first has n iterations, then n-1, n-2, ..., 0

[zinc grail]

=help eval

[thick echo]

One of the most important things to learn is the formula for arithmetic sum for these questions.

[meager trout]

Notes:
1 = (A = B)
2 = (C ≠ D)
3 = (E = F)
4 = (G = H)
~2 = (C = D)
~3 = (E ≠ F)
~4 = (G ≠ H)
~ = negative
/ = or
➞ = then

Logical statement question:
(A = B) / (C ≠ D)
(E = F) ➞ (G = H)
(C = D) / (G ≠ H)

We can write it like this for easier work:
1 / 2
3 ➞ 4
~2 / ~4

Answer:
1 / 2 = ~1 ➞ 2
~2 / ~4 = 2 ➞ ~4
~1 ➞ ~4 = 4 ➞ 1
3 ➞ 1 = ~1 ➞ ~3
1 / ~3
(E) A = B or E ≠ F

.......... Example:
X = Y always same as ~Y = ~X in logic
• (X) If I turn on the light, (Y) I can see anything.
• (~Y) If I can't see anything, (~X) I didn't turn on the light.

So there your question right. @rare moss

[rare moss]

Yes, thank you for the answer

[midnight dew]

Does anyone have a good resource for helping to understand how the fourier transform is used to calculate convolutions? I've implemented an algorithm that does it from github, but I'm very confused on why it works and the intricacies of it. For instance, if I flip a symetric matrix, the fourier transform is different from the matrix itself? I'm very confused.

[vocal gorge]

It's one of the properties of the fourier transform: F(convolve(f,g)) = F(f)*F(g), where F is fourier transform and * is ordinary, pointwise multiplication. (Maybe with some coefficients that I don't remember)

So instead of convolving two functions, you can calculate their FFTs, multiply them, and calculate an inverse FFT of the result.

[midnight dew]

right, I understand that part because that's exactly what my code does. What I don't understand is the why. I know it's some pretty deep linear algebra so I'm looking for some resources that go further in depth.

From what I understand it has something to do with complex numbers and associating a complex and real coefficient to each vector and some more stuff

But for instance in this case

y = np.array([[1, 1 , 1], [1, 0, 1], [1, 1, 1]])

np.fft2(y)
np.fft2(np.flipud(np.fliplr(y))

These two functions have two completely different outputs

Despite the input to the fft2 function being essentially the same

[ionic locust]

Time complexity for appending to a linked list is apparently O(n) since you need to iterate over the whole list to get to the tail. Why not save the tail value? Or is this no longer a linked list?

@dataclass
class LinkedList:
    head: Optional[Node] = field(init=False, default=None)
    tail: Optional[Node] = field(init=False, default=None)

    def append(self, data):
        if self.head is None and self.tail is None:
            node = Node(data, None)
            self.head, self.tail = node, node
            return
        
        node = Node(data,None)
        self.tail.next_node = node
        self.tail = node

[jolly mortar]

yeah that's valid

[vocal gorge]

From the definition of the fourier transform, yeah. Here's a proof for continious transforms:

Definition of fourier transform:

Definition of convolution:

Then:

[midnight dew]

I appreciate you trying to be helpful, but unfortunately this does nothing for me

I need to be taught like a high school student because my eyes glaze over when I look at that

[vocal gorge]

I guess the main point is that... the fourier transform is itself a convolution, one with a sine/cosine (for real transforms) or an exponent for complex ones

Ah, apparently it's called the convolution theorem. The wiki page has a proof (I think it is one?) for discrete sequences:
https://en.wikipedia.org/wiki/Convolution_theorem

[midnight dew]

The fact that anyone can look at that page and discern useful information from it is astounding to me

[vocal gorge]

Hold on

don't they?

[midnight dew]

I honestly have no idea what's happening

[vocal gorge]

these outputs look the same to me

[midnight dew]

Yeah I reran it and it is the same

but for some reason when I take out the flips, my program doesn't work

I think it's because the kernal gets padded

but I don't understand why that would affect it

It makes no sense to me

import numpy as np

myarray = np.random.randint(2, size=(10, 10))
m, n = myarray.shape
y = np.zeros((m, n))
y[int(m/2-1) : int(m/2+2), int(n/2-1) : int(n/2+2)] = np.array([[1, 1 , 1], [1, 0, 1], [1, 1, 1]])

fr = np.fft.fft2(myarray)
fr2 = np.fft.fft2(np.flipud(np.fliplr(y)))
m,n = fr.shape
cc = np.real(np.fft.ifft2(fr*fr2))
cc = np.roll(cc, - int(m / 2) + 1, axis=0)
cc = np.roll(cc, - int(n / 2) + 1, axis=1)
cc = cc.round()

This is the full code

I only just realized that the kernal was padded, so maybe that added to my confusion

But it still doesn't make sense to me why the positioning of the kernal would matter in the y matrix

[vocal gorge]

hmm, interesting

[midnight dew]

like if I don't flip the kernal diagonally, the entire thing breaks

[vocal gorge]

I think they aren't totally different

rather, the result is just flipped compared to if you don't flip the y