algos-and-data-structs

[old rover]

i called it using that

yeah I am stumped

i've been stuck on this for days

ef dfs(self, v):
    marked = [False] * len(self.vert_dict)
    # a bunch of False values in a list
    if v in self.vert_dict.values():
      print(v)
      # if a vertices is in the values of the dictionary
      marked[v] = True
      #then turn it into true
      for nodes in self.vert_dict[v]:
        #for vertices in the values that store the vertex
        if not marked[nodes]:
          #if these neighbors aren't marked as true... then run DFS on them
          self.dfs(self,v)
          # do I have to pass in the vertices... I think so bc marked is based on those vertices
      
        #O(V + E) time where V is the number of vertices and E is the number of edges

i did graph.dfs(3) and nothing happened

i'm confused as to what should be in the function definiton

and what should be passed through in the recursive call

they should match

it won't work if i take the self out of the recursive method call

like it has to be self.dfs

it won't print a single vertices

i am stuck

i don't know what I have to fix

oh i know why

it won't print "v"

bc the values of the dictionary has the neighbors of v

i think it makes sense until i hit for nodes in self.vert_dict[v]

ok well my method works for marked

when I do print(marked) it prints a list of six False values

 def dfs(self, v,marked):
    marked = [False] * len(self.vert_dict)
    #print(marked)
    # a bunch of False values in a list
    if v in self.vert_dict.values():
      # if a vertices is in the values of the dictionary
      marked[v] = True
      #then turn it into true
      for nodes in self.vert_dict[v]:
        #for vertices in the values that store the vertex
        if not marked[nodes]:
          #if these neighbors aren't marked as true... then run DFS on them
          self.dfs(self.vert_dict.keys(),marked)
          # do I have to pass in the vertices... I think so bc marked is based on those vertices
      
        #O(V + E) time where V is the number of vertices and E is the number of edges

i think this is the correct way to write it?

the keys of self.vert_dict are vertices

I passed in graph.vert_dict for marked

bc marked takes the length of the dictionary and turns it into a list of False values

[False, False, False, False, False, False]

that's what it looks like

wow i have been talking to myself since 11:53

i don't know what to write for visit(v)

no i think i got it

oh righttt bfs isn't recursive

i'm a bit confused

what does if not marked[v] mean?

marked is a list of a bunch of Falses

is it saying if it's not marked True at a certain place in the list

then visit it

and mark it True?

[vocal gorge]

Visualizing with snakeviz, here's the first:

most of the time is spent in __grab_impl itself, and also a similar amount on matchTemplate

Meanwhile, here's the second:

It looks to me like in the second one, all of the time is now taken by your own processing functions - matchTemplate and resize calls.

oh, nevermind actually, I didn't zoom in enough to see, but that resize is actually from the capture:

So yeah, in the second time a much larger part is taken up by your own processing as opposed to the capture, though the resize in the capture still takes quite a bit.

The important thing is that there's no Python here. It's all calls to well-optimized functions.

So your only way to speed it up is to reduce the amount of work being done somehow.

[tribal lotus]

Okay, so the thing is, I have to resize the images.

Because passing a large image will slow down the detection too much.

and there's no real way to lessen the work being done.

the detection loop at most takes 15-16 ms. @vocal gorge

When I screenshot with mss()

but takes as much as 60ms

when I capture via d3dshot

so d3dshot slows stuff down for some reason

@vocal gorge the grab_impl is indeed taxing

mss() takes 30ms to capture on average

[old rover]

meh i think i'm starting to get bfs

i'll look at it tomorrow

time to take a walk in what feels like 90+ heat

[vocal gorge]

You're saying mss is the faster one? That's strange, the profiling results seem to show that your matchTemplate takes the larger proportion of time in the direct3d case, which should imply the direct3d capture is faster, unless matchTemplate starts taking more time for direct3d capture for some reason

[vocal gorge]

yes, you mark it as visited in the array when you visit it.
Also, in your DFS I'd remove the if v in self.vert_dict.values(): check, not sure why you need it - it can only not be the case if the user passes an incorrect starting vertex, which is the user's fault, and doing that check every step should be quite expensive.

actually, you're also passing the entire set of keys to the recursive dfs call for some reason

[tribal lotus]

@vocal gorge I'm saying the direct3d capture is somehow slowing down the matchTemplate()

[vocal gorge]

huh, strange

[tribal lotus]

I have a custom profiler for my own stats

where I use time.time() to calculate the time of each function call

detection_time_start = time.time()
result = reflexLoop_openCV(frame)
detection_time_metric.append(time.time() - detection_time_start)

and at the end

I take the sum of the array / divided by the length of it. @vocal gorge

normally, it's 15s. But as soon as I start moving stuff on my computer (aka the frames have significant difference to trigger DirectX to capture again), it starts slowing down the detection time to upto 50ms and lowering frame rate.

I'll generate a log for you to see.

[halcyon plank]

Hey @tribal lotus!

Uh-oh! It looks like your message got zapped by our spam filter. We currently don't allow .txt attachments, so here are some tips to help you travel safely:

• If you attempted to send a message longer than 2000 characters, try shortening your message to fit within the character limit or use a pasting service (see below)

• If you tried to show someone your code, you can use codeblocks
(run !code-blocks in #bot-commands for more information) or use a pasting service like:

https://paste.pythondiscord.com

[tribal lotus]

https://paste.pythondiscord.com/neyaxupota.yaml @vocal gorge

[tribal lotus]

For reference, I can do the same log ^ with mss() and it won't slow down the detection loop. mss() just takes 20ms-30ms to capture the screen.

[raven kraken]

@wraith ocean Can you write the code for this problem I am unable to implement the logic that you suggested?

[tribal lotus]

@raven kraken I don't think we can give you the answers.

!rule 8

[halcyon plank]

Rules

8. Do not help with ongoing exams. When helping with homework, help people learn how to do the assignment without doing it for them.

[tribal lotus]

If you show us what you've done, we may be able to see what you did wrong and tell you where the logic is going wrong.

[tranquil barn]

Heyo so I needed help solving this question.
https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem
The solution that I am using is passing for a few test cases meanwhile for others it is showing time limit exceeded.

def climbingLeaderboard(a, b):
    z=[]
    for i in b:
        a.append(i)
        a=list(set(a))
        a.sort(reverse=True)
        for x in range(len(a)):
            if a[x]==i:
                z.append(x+1)
    return z
            ```

[tribal lotus]

@tranquil barn you need to first order the leaderboard in a one-to-one list.

right now the leaderboard can have multiple same values, you need to remove that first.

[tranquil barn]

Yeah I did it. py a=list(set(a))

[tribal lotus]

7
100 100 50 40 40 20 10

this is the first 2 lines of the input

you need to convert it to a list that stores [100, 50, 40, 20, 10]

then you can do a left to right search.

so check if player-score > 100, if not, check if it's greater than 50

if it's greater or equal to 50, get index of 50, and add 1 and you got the leaderboard position

[tranquil barn]

But I have to place it in too, because the rankings are dynamic and keep changing after something is inserted

[tribal lotus]

if it's greater than 50, then u place it into the list

and then push the entire list

I believe python has a method for that (if u Google it up)

[tranquil barn]

Yeah insert(index,value)

[tribal lotus]

if you go through the whole list without finding any value it's greater than, then you append it to the list.

[tranquil barn]

Hmm I actually understand what you are saying, let me try it out

[tribal lotus]

we could also try binary search and allocate but given how small the list is, it shouldn't be required.

[tranquil barn]

Btw the method you told me, wouldnt it have the same complexity or maybe even more

than the one I am currently using?

[tribal lotus]

probably less

you're just comparing numbers

even if you loop over dozens, it shouldn't take that long at all

have you tried it?

[tranquil barn]

It would still be needing nested loops. and once the number is < the other number, then we will be calling the insert function inside the nexted loops

[tribal lotus]

yeah and then continue()

[tranquil barn]

I was trying it, until I thought of this

[tribal lotus]

Trust me, you are thinking way too much optimization way too early.

try it, see if it works.

[tranquil barn]

Okay sure

[tribal lotus]

if it doesn't, we can try using binary search.

[raven kraken]

Ohh!! yes my bad

[tranquil barn]

!e

def climbingLeaderboard(a, b):
    x=[]
    a=list(set(a))
    for i in b:
        for j in range(len(a)):
            if i>=a[j]:
                if i==a[j]:
                    break
                else:
                    a.insert(j,i)
                    x.append(j+1)
                    break  
                break
    return x

print(climbingLeaderboard([100,100 ,50, 40, 40 ,20, 10],[5,25, 50, 120]))```

[halcyon plank]

@tranquil barn :white_check_mark: Your eval job has completed with return code 0.

[3, 2, 1]

[tranquil barn]

it's showing the wrong output

6
4
2
1

should be the output

@tribal lotus

[tribal lotus]

are you sure you implemented it properly?

[raven kraken]

This is the problem the format for the date is wrong.

How can I remove the dash between numbers in the date

[tribal lotus]

use replace() @raven kraken

[raven kraken]

replace works in dictionary?

[raven kraken]

It's not working

[tribal lotus]

it works on strings

use it on strings

@tranquil barn you also need to add to list if it's not >=

[plucky aurora]

!e

"""
https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem
"""
import bisect

def climbingLeaderboard(ranked, player):

    # ranked is the current ranking
    # player is the list of game your results.
    # for each game, where would you rank?

    set_ranked = set(ranked)
    ranked = sorted(list(set_ranked), reverse = False)
    len_ranked = len(ranked)
    answer = list()

    for game in player:
        # is lowest?
        if game < ranked[0]:
            answer.append(len_ranked + 1)

        # is highest?
        elif game > ranked[-1]:
            answer.append(1)

        # is a tie?
        elif game in set_ranked:
            answer.append(len_ranked - ranked.index(game))

        # find position
        else:
            answer.append(len_ranked - (bisect.bisect(ranked, game)) + 1)


    return answer


print(climbingLeaderboard([100, 90,90, 80], [70,80,105]))
print(climbingLeaderboard([100, 100, 50, 40, 40, 20, 10], [5, 25, 50, 120]))

[halcyon plank]

@plucky aurora :white_check_mark: Your eval job has completed with return code 0.

001 | [4, 3, 1]
002 | [6, 4, 2, 1]

[tribal lotus]

There you go.

[ivory flint]

Hi guys! Please tell me, edabit is good resource to python practice?

[austere breach]

hi guys ! i have a problem in converting event data to spadl

[old rover]

  def dfs(self, v,marked):
    marked = [False] * len(self.vert_dict)
    #print(marked)
    # a bunch of False values in a list
      # if a vertices is in the values of the dictionary
    marked[v] = True
      #then turn it into true
    for nodes in self.vert_dict[v]:
        #for vertices in the values that store the vertex
        if not marked[nodes]:
          #if these neighbors aren't marked as true... then run DFS on them
          self.dfs(self.vert_dict,marked)
          # do I have to pass in the vertices... I think so bc marked is based on those vertices
      
        #O(V + E) time where V is the number of vertices and E is the number of edges

so is this correct then?

[knotty magnet]

does it work?

[old rover]

Traceback (most recent call last):
  File "main.py", line 106, in <module>
    print(graph.dfs(3,graph.vert_dict))
  File "main.py", line 63, in dfs
    for nodes in self.vert_dict[v]:
TypeError: 'Vertex' object is not iterable

[knotty magnet]

so it's not correct

[old rover]

nope

[knotty magnet]

i'm guessing you meant to loop over the vertex's neighbors

[old rover]

yep

that's the values of the dictionary

[knotty magnet]

that's probably a method on the vertex class or an attribute or something?

[old rover]

i think it should be this one

def get_vertices(self):
    return self.vert_dict.keys() #gets the vertices of the graph

nope it doesn't like that either

yeah i don't know

i tried calling a function on the self.vert_dict

that doesn't work

for nodes in self.vert_dict.get_vertices:

that throws an error

[knotty magnet]

vert_dict is a dictionary? so it wouldn't have any of the methods you defined on your Graph, right?

[old rover]

it wouldn't

the issue might be this line

marked[v] = True

[knotty magnet]

why?

[old rover]

it's mentioned in the error message

[knotty magnet]

no?

at least, not the one you sent

[old rover]

vertex object is not iterable

[knotty magnet]

yes

[old rover]

when i take out the [v]

TypeError: list indices must be integers or slices, not dict

[knotty magnet]

which [v]

[old rover]

def dfs(self, v,marked):
    marked = [False] * len(self.vert_dict)
    #print(marked)
    # a bunch of False values in a list
      # if a vertices is in the values of the dictionary
    marked[v] = True
      #then turn it into true
    for nodes in self.vert_dict[v]:
        #for vertices in the values that store the vertex
        if not marked[nodes]:
          #if these neighbors aren't marked as true... then run DFS on them
          self.dfs(self.vert_dict,marked)
          # do I have to pass in the vertices... I think so bc marked is based on those vertices
      
        #O(V + E) time where V is the number of vertices and E is the number of edges

for nodes in self.vert_dict[v]

[knotty magnet]

that loops over the keys in self.vert_dict

[old rover]

doesn't it loop over the values

[knotty magnet]

no

[old rover]

the keys are the vertices

don't you get the value of a dictionary by doing dictionary[key] = value?

[knotty magnet]

yes

didn't you remove the [v] though?

[old rover]

{0: <__main__.Vertex object at 0x7f9d694d8670>, 1: <__main__.Vertex object at 0x7f9d6945a310>, 2: <__main__.Vertex object at 0x7f9d6945a3a0>, 3: <__main__.Vertex object at 0x7f9d6945a400>, 4: <__main__.Vertex object at 0x7f9d6945a490>, 5: <__main__.Vertex object at 0x7f9d6945a4f0>}

that's what self.vert_dict looks like

[old rover]

yeah i just did

[knotty magnet]

you want to loop over the neighbors of v though, right?

[old rover]

yes

[knotty magnet]

doesn't your Vertex class have a method to get its neighbors?

[old rover]

def get_connections(self):
    return self.connected_to.keys() #returns the nodes a node is connected to

it has a get_connections

[knotty magnet]

that seems like what you want to be using

[old rover]

so i tried

for nodes in self.vert_dict.get_connections:

AttributeError: 'dict' object has no attribute 'get_connections'

[knotty magnet]

do you understand why that error is happening?

[old rover]

bc i defined what the vert_dict is in my graph class

so it won't have any of the attributes from my vertex class

[knotty magnet]

well yeah, because self.vert_dict isn't a Vertex

you want the neighbors of v

[old rover]

shouldn't it be

self.vert_dict[v].get_connections?

that gives me a new error

"TypeError: 'method' object is not iterable"

[knotty magnet]

do you understand why that error is happening?

[old rover]

it says that a method isn't iterable

[knotty magnet]

ok, that's what it says. but do you understand why?

[old rover]

you can't iterate through something you called a method on?

[knotty magnet]

almost. it's telling you simply that you just can't loop over methods

self.vert_dict[v].get_connections is a method, what you wanted to do was call the method, self.vert_dict[v].get_connections() with parentheses

[old rover]

oh ok

[knotty magnet]

errr wait not that

fixed

[old rover]

yeah now it's saying

Traceback (most recent call last):
  File "main.py", line 107, in <module>
    print(graph.dfs(3,graph.vert_dict))
  File "main.py", line 66, in dfs
    if not marked[nodes]:
TypeError: list indices must be integers or slices, not Vertex

[knotty magnet]

right

[old rover]

bc they are just vertex objects in memory

marked is a list of Falses

[knotty magnet]

you have two different ways to refer to a vertex, which is a little strange. you have a number (v), and a Vertex object (self.vert_dict[v])

[old rover]

so three different ways?

[knotty magnet]

sorry, should have made that clearer. your self.vert_dict contains Vertex objects remember?

[old rover]

yes

as values

[knotty magnet]

right, your marked needs integer indices, but get_connections gives you Vertex objects

[old rover]

could I call get_ID() after this line: for nodes in self.vert_dict[v].get_connections():?

get_ID returns the id of any vertex

[knotty magnet]

yes, that sounds reasonable

[old rover]

for nodes in self.vert_dict[v].get_connections().get_ID():

AttributeError: 'dict_keys' object has no attribute 'get_ID'

oh

bc get_ID

is in the Vertex class

[knotty magnet]

oh, you would use it on nodes

[old rover]

AttributeError: 'Vertex' object has no attribute 'get_vertex'

 for nodes in self.vert_dict[v].get_connections():
      nodes.get_vertex()
        #for vertices in the values that store the vertex
    if not marked[nodes]:
          #if these neighbors aren't marked as true... then run DFS on them
      self.dfs(self.vert_dict,marked)
          # do I have to pass in the vertices... I think so bc marked is based on those vertices
      
        #O(V + E) time where V is the number of vertices and E is the number of edges

sigh

shouldn't it be

nodes.get_ID()?

[knotty magnet]

why?

[old rover]

nodes.get_ID() still doesn't work

get_vertex returns a vertex in the graph

get_ID returns the id of any vertex

[knotty magnet]

is nodes not a Vertex?

[old rover]

4 connectedTo: [0]

that's what happened when I did print(nodes)

it just shows a vertex connected to a given vertex

i need indexes for marked to work

but i don't think i have a method that gives me indexes

[knotty magnet]

i don't understand why you have a Vertex object at all

[old rover]

i don't either

i don't know how to fix the depth first search

i need something that returns the indices of vertexes in a graph

[knotty magnet]

or change marked to a set that stores Vertex objects

[old rover]

ok i created marked as a set

how do i make it store vertex objects?

 marked = set()
    marked.add(self.vert_dict.keys())

def dfs(self, visited, graph, node):
    visited = set()
    if node not in visited:
      # if the node is not in the set
      print(node)
      #print the node
      visited.add(node)
      #add it in
      for neighbor in graph[node]:
        #for each neighbor of the node
        self.dfs(visited, graph, neighbor)
        #visit them and print them

it was that simple

goddamnit

this is a meme

i think it's my fault tbh

hey at least i got through it

[hexed sail]

i need help

[lunar jacinth]

class Queue(SList):
        def __init__(self):
            super().__init__()

        def QPush(self, data):
                result = self.Append(data)
                print(f"Used Push function to push {data} into the Queue")
                return result

        def QPop(self):
                print(f"The item being popped from the Queue is {self.head.data}")
                self.Delete(self.head.data)

        def QPeek(self):
                print(f"Used peek function and found that the item at the front of the Queue is: {self.head.data}")
        
        def QEmpty(self):
                print(f"Check if the Queue has no items -- True if its empty, False if it is not: {self.IsEmpty()}")

        def QGetLength(self):
                print(f"The number of items in the Queue are: {self.Count()}")
``` Is there a way I could turn this into a priorityqueue?

[austere sparrow]

In CPython (the default implementation), priority queues are backed by a heap

which makes it a bit of a misnomer (since insertion order is not respected)

[lunar jacinth]

It tells me to do it after each insert I think ```py
A potential solution is do a sort on your PriorityQueue data after every insert. The PriorityQueue is used to store the weighted edges in ascending order to assist with selecting the least weighted edges. If you decide to sort your PriorityQueue after every insert, don't transfer the PriorityQueue data into an Array, sort the array and then transfer the data back into the PriorityQueue. Directly sort your PriorityQueue.

[keen hearth]

Check out the heapq module in the standard library.

[lunar jacinth]

i'm not sure if im supposed to import any modules, would it be difficult without importing that?

[keen hearth]

Have you learned about heaps in your data-structures course? Once you understand them, it's a good exercise to try implementing one.

A heap is generally preferable to re-sorting the list on each insertion. Inserting into a heap is O(log n), where n is the number of elements in the heap already. Inserting into a sorted list would be Ω(n), because if it turns out to be the new smallest element, then you have to shunt all of the other elements over by one index each.

[lunar jacinth]

Yeah very slightly

I think I have two options, either i can do a priorityqueue or a heap

[knotty magnet]

you would implement a pqueue with a heap

[lunar jacinth]

Is it possible to do so by just adding onto my queue class?

Like without importing heapq or something like that?

[sudden garden]

got a question

Given an integer n, the task is to find the minimum number of cubes whose sum equals N

Input: 74
Output: 4
Since 64 + 8 + 1 + 1 = 74

I understand the recursive solution, just loop from 1 to n, and check if each number i should be part of sum or not.

Case 1: i is part of sum, then recurse n-i

Case 2: i is not part of the sum, then recurse n

Obviously, exponential time since there probably some recalculation happening, so since there is overlap in calculation, can I not use memoization to make it efficient?

[vocal gorge]

Seems to me like you can, since it seems to me you can solve it via dynamic programming in O(n^2) time or so - knowing the minimum cube decompositions for 1,...,n, the minimum decomposition for n+1 can be calculated by taking the smallest n+1-i**3 decomposition and adding i**3 to it.

actually, slightly lower than O(n^2) - for each element we need to check cbrt(i) possible predecessors, so O(n^(4/3))

[sudden garden]

I don't get i**2 part

[vocal gorge]

oops, yeah, I meant i**3

[sudden garden]

oh thought so 😅

how would you check cbrt(i) though

[vocal gorge]

I mean that there's around cbrt(i) numbers the cube of which is less than i.

[quiet jay]

hello noob question. how do I calculate time complexity for stacks and queues?

[vocal gorge]

So to calculate the new element i, you'd need to check around cbrt(i) previously calculated ones. So the total complexity will be around cbrt(1) + cbrt(2) + .. + cbrt(n), which is O(n^(4/3))

[sudden garden]

oh I see, thanks, that helps alot!

[austere sparrow]

Time complexity of what?

You can't measure time complexity of a data structure, it's just sitting there.

Only of operations/algorithms that you perform on them.

[quiet jay]

like pops pushes

enqueues and dequeues for front and back

[austere sparrow]

Well, what do you think?

First of all, what operations does a stack support?

[quiet jay]

pops, pushes and peeks

[austere sparrow]

I don't think peeking at elements is available on stacks. Well, that depends on what kind of stack it is

So what do you think the time complexity of those is?

[quiet jay]

dont really know

pops would be O(n) because it needs to go through the whole list

pushes O(n) as well?

[austere sparrow]

@quiet jay Can you make an implementation of a stack?

[quiet jay]

what

I don't know what implementation means

[austere sparrow]

Implementing something means writing it in code.

If you wanted to implement addition, you would write a function that adds two numbers

[quiet jay]

oh

yeah I already have one

[sinful hawk]

would anyone mind explaining what collections.counters does?

and how its diffrent from like a dictionary

[vocal gorge]

See docs, basically. It's a dict subclass, equivalent to something like:

def counter(it):
    counts = {}
    for el in it:
        if el not in counts:
            counts[el] = 1
        else:
            counts[el] += 1
    return counts

plus a few helpful methods on the resulting dict.

!e

import collections
text = "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum."
counts = collections.Counter(text)
print(counts)

[halcyon plank]

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

Counter({' ': 68, 'i': 42, 'e': 37, 't': 32, 'o': 29, 'a': 29, 'u': 28, 'n': 24, 'r': 22, 'l': 21, 's': 18, 'd': 18, 'm': 17, 'c': 16, 'p': 11, 'q': 5, ',': 4, '.': 4, 'g': 3, 'b': 3, 'v': 3, 'x': 3, 'f': 3, 'L': 1, 'U': 1, 'D': 1, 'h': 1, 'E': 1})

[low dome]

anyone can help me?

[sinful hawk]

so is it like a dictionary specificly used for getting characters in a string?

or whatever elems in a bigger element

[vocal gorge]

No, for counting elements.

[sinful hawk]

oh sorry yeah counting elems i meant

[vocal gorge]

It maps a thing to how many times it has seen it.

[sinful hawk]

so just a specific type of dict got it

[low dome]

make a program to display the sorting of data with the bubble sort method
example
input : samsul, umar, parrot, irawan,imanudin
output :imanudin,irawan,nuri,umar,samsul

[reef remnant]

def bubblesort(input):
  if input == " samsul, umar, parrot, irawan,imanudin":
    return "imanudin,irawan,nuri,umar,samsul"

[dire bluff]

INV_COUNT_SLOW(A,p,r)
count = 0
for i =1 to p
for j= p to r
if A[i] > A[j]
count = count +1
return count

Anyone could help, does the for loop is correct or not?

[sage swift]

`
edad = int(input('Porfavor ingresa su edad: '))
tieneDiploma = int(input('Cuenta con diploma bachiller? (Y/N): '))

if edad > 17 and tieneDiploma == 'Y':
print('El estudiante es apto para ingresar al programa de medicina')
else:
print('El estudiando no es apto para ingresar al programa de medicina')
Porfavor ingresa su edad: 19
Cuenta con diploma bachiller? (Y/N): Y
Traceback (most recent call last):
File "c:\Users\Usuario\Desktop\PythonMinTic\programa.py", line 2, in <module>
tieneDiploma = int(input('Cuenta con diploma bachiller? (Y/N): '))
ValueError: invalid literal for int() with base 10: 'Y'
PS C:\Users\Usuario\Desktop\PythonMinTic> `

Help

I do not understand why I get that

[urban geode]

Did you enter Y as the input?

[urban geode]

I guess you did, vecause it says it's one of the pptions

[urban geode]

You are trying to convert Y to int data-structures

!e

st = "Y"
print(int(st))```

[halcyon plank]

@urban geode :x: Your eval job has completed with return code 1.

001 | Traceback (most recent call last):
002 |   File "<string>", line 2, in <module>
003 | ValueError: invalid literal for int() with base 10: 'Y'

[sage swift]

ok

Thanks

[tribal lotus]

def normalise_zero(data_frame: pd.DataFrame):
    return data_frame / data_frame.iloc[0] - 1

does this no longer work or something?

I mean, I think it used to no?

Now I'm getting the obvious type error of using / for type str and str

[brave oak]

what are you trying to do

[tribal lotus]

Normalize a panda dataframe with base zero. @brave oak

[brave oak]

what do you mean base zero

[tribal lotus]

So there's 2 types of normalizations

one is min max

[brave oak]

actually, this isn't really true

[tribal lotus]

well there are more

types

[brave oak]

but what's the relevance to your question?

it's not apparent to me what you're trying to do, and "base zero" is not a term with mathematical meaning, as far as I know

[tribal lotus]

I'm basically trying to normalize a time series with zero inflated data.

Let me see if I can use

MinMax for it

well

https://stackoverflow.com/a/41532180 does this not work either?

normalized_df=(df-df.min())/(df.max()-df.min())

[brave oak]

what do you mean by "doesn't work"

what happens?

[tribal lotus]

Type error

[brave oak]

do you understand what that means?

[tribal lotus]

Yes

It's because I'm using a - operand on two string types

[brave oak]

operator, actually, but the general idea is right

do you know what the offending values are?

[tribal lotus]

yes

it's because I'm subtracting data_frame.min() from data_frame.

but apparently it is how you're supposed to do it according to multiple Stackoverflow answers. 🤔

[brave oak]

uh

the point is your data is of the wrong type

like

why are there strings in your data?

there shouldn't be, right

so you need to identify the reason

i.e. it's a data quality issue

not an algorithm issue

[tribal lotus]

but like there

is no string

according to pycharm

there are just floats

when I use debugger to inspect data

data_frame.dtypes shows float64s

so I don't see how a string can creep in when the data types are reported as float64s.

[vernal stirrup]

how can i find the properties of the add_widget() function which adds widgets to grid layouts?

i want to add widgets in specific places but i just can t find the properties of the add_widget() function

[livid heron]

Hi, how can i disable the main window (the root), when a Toplevel is active?

[fervent saddle]

Are bit manipulation tricks used a lot outside of leetcode types of questions? Is it practical to learn them, or would that be a waste of time?

And if they are then what’s the best place to learn them?

I know what bitwise operators do, but I wouldn’t know when or how to use them

[half lotus]

It's practically useful when working with performance sensitive code

e.g. trying to reduce branches in your C algorithm

[fervent saddle]

I’m thinking of things like that trick where you have an array where only one of the numbers appears an odd number of times, and you use xor to find it

I get it after seeing it, but I wouldn’t ever think to do it myself

[last fulcrum]

I need help with my solution. I don't need another solution please. I just want to know what I'm doing wrong as that would help me improve. Or where the logic in my code is wrong.

This is the Question.
**A balanced binary tree is defined as a tree such that either it is an empty tree, or both its subtree are balanced and has a height difference of at most 1.

In that case, given a binary tree, determine if it's balanced.**

Solution 1

def is_balanced(tree: Node) -> bool:
    def dfs(root, curr_left = 0, curr_right = 0):
        if not root:
            return 0
        
        left = dfs(root.left, curr_left = 1)
        right = dfs(root.right, curr_right = 1)
        
        if left - right <= 1:
            return True
        else:
            False
            
    return dfs(tree)

Solution 2

def is_balanced(tree: Node) -> bool:
    def dfs(root):
        nonlocal curr_left
        nonlocal curr_right
        
        if not root:
            return 0
        
        if dfs(root.left):
            curr_left += 1
        else:
            dfs(root.right)
            curr_right += 1
        
        if curr_left - curr_right <= 1:
            return True
        else:
            False
       
    curr_left = 0
    curr_right = 0      
    return dfs(tree)

[lunar jacinth]

For priorityqueue using doubly linked lists, would you need an enque and deque instead of push and pop?

[lunar jacinth]

Could someone help me with priorityqueue in #help-orange

[knotty magnet]

how do you make a priority queue with a linked list

[fiery cosmos]

anyone know of a way to generate a hash for a 4d vector?

[lunar jacinth]

good question, very confused myself

[fiery cosmos]

Put the nums in a tuple and use the built-in hash of that

[fiery cosmos]

im in c# but maybe thats a way to go if c# has a structure like that. Not sure how generic types can be hashed though. But it might work for a tuple of ints well

[vocal gorge]

Tuples hash each of the elements, then mix their hashes somehow

so a tuple is hashable iff all the elements are

[fiery cosmos]

yep https://docs.microsoft.com/en-us/dotnet/api/system.object.gethashcode?view=net-5.0

    public override int GetHashCode()
    {
        return Tuple.Create(x, y).GetHashCode();
    }

They suggest using this. But this boxes the type to do so which is overhead. But it is a simple solution.

[fiery cosmos]

Anyone know about bit interleaving?

[rugged swan]

Hi

how do I test this code? Can you explain to me?

[manic hatch]

do you know what dunder-methods are?

https://docs.python.org/3/reference/datamodel.html

[vernal stirrup]

i have defined connected in line 26 and in line 30 the error that connected is not defined why?

[fervent saddle]

You assign a variable of that name at a point in the function, so it’s treated as a local variable, so you’re using it before it’s assigned

global connected
Put that at the start of the function

[vernal stirrup]

ah thank you

[fervent saddle]

Then it knows to look for it in the global scope and treat it as a global variable

np

[lament plover]

class Box:
    def __init__(self, name, data, make_copy=True):
        self.label = name
        self.copy = make_copy
        self.data = data
    
    def __repr__(self):
        return self.label

    @property
    def data(self):
        return self.__data

    @data.setter
    def data(self, data):
        if self.copy:
            self.__data = copy.deepcopy(data)
        else:
            self.__data = data

Came up with this on a whim

Almost an internally mutable variable/a dictionary with one key-value pair

Not sure how useful it might be but I thought it could be interesting

[sweet sail]

heyhey, quick question, so i'm making a thing for my work with creating a route for our driver automatically with routexl, i can find the route, distance and the rest of the data between given locations, but my trouble is in how to load them in (there's more hold on)

the routexl api allows me to give it a number of locations in a dic and then pass it into the api and it'll kick out the routexl results for stuff

my problem is, in json, if i have a location file with this data in it (test data, location is irrellevant)

    "address":"The Hague, The Netherlands",
    "coordinates": {"lat":52.05429,
        "lng":4.248618
    }
}```
is there any way i could make it so that there an be multiple of those blocks in a single json file, while not needing there to be a certain number of those blocks in there? Thanks!

i'm VERY new to json so idek if this would be the right channel for this haha sorry if it's not lol

like, how can i have that be a class in json, so that i can reuse it repeatedly? should clarify haha

oohh nevermind! i've made each location block(above code block) one indent layer deeper, and had them all inside of an array, so that when i load in that array, i can loop through each, Thanks!

[signal cargo]

Hey everyone .

I have two different numpy and I want to have 2d numpy with append.

So sample ; np.array([1,2,3]) and np.array([3,4,5,6)] I have.

I wanted to have at final like np.array([[1,2,3],[3,4,5,6]) how can I do that?

[loud trail]

@signal cargo you can't, np.array([[1,2,3],[3,4,5,6]]) isn't a valid numpy array

!e ```python
import numpy as np
np.array([[1,2,3],[3,4,5,6]])

[halcyon plank]

@loud trail :white_check_mark: Your eval job has completed with return code 0.

<string>:2: VisibleDeprecationWarning: Creating an ndarray from ragged nested sequences (which is a list-or-tuple of lists-or-tuples-or ndarrays with different lengths or shapes) is deprecated. If you meant to do this, you must specify 'dtype=object' when creating the ndarray.

[loud trail]

well, it's technically a valid numpy array, but it's not what you think it is and probably not what you want

[normal dust]

if i have two lists with a bunch of dicts in the lists, how can i find the added, removed, and kept elements between the two lists

[lunar jacinth]

def insert(self, root, key): 
      
        # Step 1 - Perform normal BST 
        if not root:                                         C0                                       
            return TreeNode(key)                             C1
        elif key < root.val:                                 C2
            root.left = self.insert(root.left, key)          O(log(n))
        else:                                                C4
            root.right = self.insert(root.right, key)        O(log(n))        
  
        # Step 2 - Update the height of the  
        # ancestor node 
        root.height = 1 + max(self.getHeight(root.left),     C5
                           self.getHeight(root.right)) 
  
        # Step 3 - Get the balance factor 
        balance = self.getBalance(root)                      C6
  
        # Step 4 - If the node is unbalanced,  
        # then try out the 4 cases 
        # Case 1 - Left Left 
        if balance > 1 and key < root.left.val:              C7
            return self.rightRotate(root)                    C8
  
        # Case 2 - Right Right 
        if balance < -1 and key > root.right.val:            C9
            return self.leftRotate(root)                    C10
  
        # Case 3 - Left Right 
        if balance > 1 and key > root.left.val:             C11
            root.left = self.leftRotate(root.left)          C12
            return self.rightRotate(root)                   C13
  
        # Case 4 - Right Left 
        if balance < -1 and key < root.right.val:           C14
            root.right = self.rightRotate(root.right)       C15
            return self.leftRotate(root)                    C16
    
        return root                                         C17



Total Time = C0 + C1 + C2 + O(log(n)) + C3 + C4 + O(log(n)) + C5 + C6 + C7 + C8 + C9 + C10 + C11 + C12 + C13 + C14 + C15 + C16 + C17 = O(log(n)) which is logarthmic time. 
``` Would this be correct line by line analysis and total time?

[normal dust]

for example if one list was [{"a": "b"}, {"b": "c"}] and another was [{"b": "c"}, {"c": "d"}] it would say removed {"a": "b"}, kept {"b": "c"}, added {"c": "d"}

[fiery cosmos]

    for i in range(len(queries)):
        ans += sum(queries[0:i]) 
    return ans

would this be executed in N time?

or N^2

[main atlas]

import pandas as pd
from sklearn.tree import DecisionTreeClassifier

data = pd.read_csv('/content/student-por.csv')
print(data)
X =  data.drop(columns=['grade'])
print(X)
y = data['grade']
print(y)
model = DecisionTreeClassifier()
model.fit(X , y)
model.predict([[18, 2, 2, 0, 1, 0, 0, 0, 1, 1, 0, 0, 4, 3, 4, 1, 1, 3, 4]])

What am i doing wrong here

ValueError                                Traceback (most recent call last)
<ipython-input-33-4fc4f82f40e4> in <module>()
      9 print(y)
     10 model = DecisionTreeClassifier()
---> 11 model.fit(X , y)
     12 model.predict([[18, 2, 2, 0, 1, 0, 0, 0, 1, 1, 0, 0, 4, 3, 4, 1, 1, 3, 4]])

2 frames
/usr/local/lib/python3.7/dist-packages/sklearn/tree/_classes.py in fit(self, X, y, sample_weight, check_input, X_idx_sorted)
    875             sample_weight=sample_weight,
    876             check_input=check_input,
--> 877             X_idx_sorted=X_idx_sorted)
    878         return self
    879 

/usr/local/lib/python3.7/dist-packages/sklearn/tree/_classes.py in fit(self, X, y, sample_weight, check_input, X_idx_sorted)
    171 
    172         if is_classification:
--> 173             check_classification_targets(y)
    174             y = np.copy(y)
    175 

/usr/local/lib/python3.7/dist-packages/sklearn/utils/multiclass.py in check_classification_targets(y)
    167     if y_type not in ['binary', 'multiclass', 'multiclass-multioutput',
    168                       'multilabel-indicator', 'multilabel-sequences']:
--> 169         raise ValueError("Unknown label type: %r" % y_type)
    170 
    171 

ValueError: Unknown label type: 'continuous'

This works with other data i have but not with this one for some reason
current data : https://paste.pythondiscord.com/pogoqinuko.apache
old data : https://paste.pythondiscord.com/ayazepezoz.apache

Is it that it can only train with 2 parameters

[dim stratus]

Anyone here tried sha256 implementation?

[fiery cosmos]

    def isPali(self, s):
        # O(n) time and O(1) space
        left_p = 0 
        right_p = len(s) - 1
        while left_p < right_p:
            if s[left_p] != s[right_p]:
                return False
            left_p += 1
            right_p -= 1
        return True
    def isPali2(self, s):
        # O(n) time and space (O(n) time for slicing and O(n) time for comparing)
        return s == s[::-1]

why does my isPali2() run faster on LC than my isPali()

I've tried running it many times and it's faster every time

Pali=Palindrome btw

[vocal gorge]

Pretty much just because string comparison and slicing are implemented in C while your isPali has a loop in Python.

[fiery cosmos]

Hey guys, 2 quick questions

1. Are there any numbers that can not be computed with Python?
2. Are there any rational numbers that can not be computed with Python?

[trim fiber]

✋

[dim stratus]

@trim fiber can you help me? My code is in C. Btw i think i am getting endian issue. Reply if you want to look at.

[trim fiber]

Pick some free help channel and ping me there

#❓｜how-to-get-help

[dim stratus]

@trim fiber ok let me install discord on system

[vocal gorge]

Not entirely certain what you're looking to hear. I guess for one, you probably can't compute 2**(10**1000), because while Python int-s are infinitely-sized, that number has 10**1000 binary digits, so unless you have that many bits of memory (around 10**984 times the amount of data in all of Internet), it won't fit there.

[keen hearth]

Theoretically, there are uncomputable numbers. Such as Chaitin's constant, which represents "the probability that a randomly constructed program will halt". This number is uncomputable on any computer, meaning you cannot calculate it with arbitrary precision.

[fiery cosmos]

Alright guys, thanks a lot !

[tribal lotus]

For people who are familiar with the Pandas DateTimeIndex, how does one go about adding a new Numpy Datetime (with same type) to the DateTimeIndex?

I tried getting the DateTimeIndex.values editing the Numpy array using numpy.append() and then setting DateTimeIndex.values to that Numpy array since numpy.append() creates a new appended array.

However when I try to set it, I get an attribute error telling me I can't set that attribute.

So what's the way to go about this?

[tribal lotus]

Please ping me if you're responding. Greatly appreciated. ^

[frigid light]

does anyone have the pdf for deep learning for dummies

[fiery cosmos]

thanks

what about this? #algos-and-data-structs message

[knotty magnet]

if queries is a list with ints, N^2

[trim obsidian]

anyone can guide how to understand in deep about asymptotic notation?

[pallid quest]

`class MatchForm(forms.ModelForm):
class Meta:
model = Match
fields = ["away_player", "home_player", "date_of_play"]

def _init_(self, *args, **kwargs):
    user = kwargs.pop("user")
    super(MatchForm, self)._init_(*args, **kwargs)
    tournament = Tournament.objects.get(on_session=True)

    player = Player.objects.filter(payment_tournament=Tournament.objects.get(on_session=True), payment_paid=True,
                                   host=user.host)

    for players in player:
        st = []
        if players.playerstatus_set.filter(tournament=tournament).exists():
            if not players.playerstatus_set.filter(tournament=tournament)[0].knocked_out:
                st.append(players)
                print(st)
                qs = players

                self.fields["home_player"].queryset = qs

    self.fields["away_player"].queryset \
        = Player.objects.filter(payment_tournament=Tournament.objects.get(on_session=True), payment_paid=True, )`

Someone help me, I wanna filter in such a way that if the playerstatus of that tournament exists and if the first incidence was knocked out then he will not be displayed in the home_player or away_player

[dapper sapphire]

So Gauss's formula for sum:
len * (len + 1) // 2
wouldnt work if the number starts from 0?
Few pages that I have came across start the number from 1(natural number) not 0(whole number).

[fiery cosmos]

You're talking Triangular numbers like 1 + 2 + 3 + 4 + ... + n = (n+1)*n/2 ? https://en.wikipedia.org/wiki/Triangular_number

If you add 0 to that it doesn't change so it doesn't exactly matter

[modern root]

Hello, is this channel busy with a different question or can I pose mine?

[dapper sapphire]

I didnt know about Triangular numbers, but seems like it also uses Gauss' sum formula.

!e

from typing import List

def gauss_sum(nums: List[int]) -> int:
    sum_all = len(nums) * (len(nums) + 1) // 2
    return sum_all

nums1 = [1, 2, 3]
nums2 = [0, 1, 2, 3]
print("nums1:", gauss_sum(nums1))
print("nums2:", gauss_sum(nums2))

[halcyon plank]

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

001 | nums1: 6
002 | nums2: 10

[dapper sapphire]

So nums1 is without 0, but nums2 is with 0

[fiery cosmos]

Well you aren't using the values from nums there, only their lengths. sum(nums1) will equal sum(nums2), both 6

[fiery cosmos]

Sure, if it's about data structures/algorithms check out #❓｜how-to-get-help for more general help

[modern root]

it gives me this error when I follow those instructions :
Your message could not be delivered. This is usually because you don't share a server with the recipient or the recipient is only accepting direct messages from friends. You can see the full list of reasons here: https://support.discord.com/hc/en-us/articles/360060145013

I just joined the server btw.

[fiery cosmos]

Looks like a discord.py question try asking in #discord-bots

[modern root]

Wait, so if my question pertains to an algorithm that I wrote, I don't have to go through that whole process? I can just post my question here?

[fiery cosmos]

Sure, though sometimes you might get more answers in your own help channel this place can be empty sometimes

[modern root]

So I wrote this comparison algorithm. My whole goal is for it to tell me which sentences are most common inside a big list of sentences. The way it works is by comparing sentences and getting a rate, if that rate is above a certain threshold, it would increment the popularity rate of that sentence. But I am not very confident about it.
Here's the code: def rankitup(inin): text = [] for item in inin: item = item.split(".") for sente in item: text.append(sente) lastly = {} counter = 0 # Take two sentences for sentNum in range(len(text)): # Sentences counter right after the current one counter +=1 n = sentNum # Extract the number of current sentence popularity = 0 # Set current sentence popularity counter to 0 sent1= text[n] # index into the current sentence while((n +1) < len(text)): # check that I am not going out of bound sent2 = text[n+1] # Take the sentence after it rate = Levenshtein.ratio(sent1, sent2) # Compare those 2 sentences if rate > 0.4: # If the similarity is above 50% popularity +=1 # Add the popularity and show me it n+=1 # increment the number for next sentence if sent1 != " ": # make sure it is not empty if sent1 in lastly: # make sure there's no duplicates break lastly[sent1] = popularity # Add that sentence and its popularity num return lastly

I would love if someone can help glance over it and see if it is algorithmically correct.

Let me know if you have any questions.

[knotty magnet]

can't you just use collections.Counter?

[modern root]

No, the sentences are irregular and there's nothing identical. But there's a lot of common words

An example is:

Hands-on experience implementing the privacynd securitynd best practices for deploying the the work loads on AWS GCPnd AZURE cloud platforms```

You see what I am saying?

[knotty magnet]

i see

[fiery cosmos]

Well idk about comparing sentences, even with Levenshtein distance "Python is good." will be pretty close to "Python is bad." In general you'd need machine learning and sentiment analysis or something

But you can definitely tighten up the code to loop over pairs of unique sentences:

!e ```py
text = "Java is good. Java is pretty good . Python is way better. . Python sucks . Java is good ."

Split into unique sentences and filter out empty ones and remove leading/trailing whitespace.

sentences = list(set(s.strip() for s in text.split('.') if s.strip()))

Loop over every pair of sentences

for i in range(len(sentences)):
s1 = sentences[i]
for j in range(i+1, len(sentences)):
s2 = sentences[j]
# do stuff
print(s1, '|', s2)

[halcyon plank]

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

001 | Python sucks | Python is way better
002 | Python sucks | Java is pretty good
003 | Python sucks | Java is good
004 | Python is way better | Java is pretty good
005 | Python is way better | Java is good
006 | Java is pretty good | Java is good

[fiery cosmos]

course . is not always a period

[buoyant falcon]

Is this the right section to ask about a Pydantic related question?

pydantic/collections

[lunar jacinth]

Navigate your PriorityQueue, after the Nodes are inserted, to find the Minimal Spanning Tree.  Be sure your paths do not create a cycle.  The end result is a list of Nodes in the lowest cost order with the sum of the lowest cost.  Find the lowest cost starting the shortest edge connection and connecting all other airports.
``` Could someone help me understand this part? I've created my priorityqueue already

Would I need a vertex and graph class?

[modern root]

I just looked over your code, per my understanding it's comparing every two sentences? or does it take one sentence and compares it with the rest of the file?

[fiery cosmos]

yeah, it compares every pair of sentences

[lunar jacinth]

Hey Discrete, are you familiar with heapq's heapify

[modern root]

The way I built is that it would take a sentence, compare to every other sentence, and then move on to the next one and repeat.

I see what you're saying with machine learning, but I have not learned it yet.

[fiery cosmos]

What about it

[lunar jacinth]

I'm trying to make like something similar to it, I was wondering if you could possibly check a function for me?

I think it just sorts data right based on priority i think?

[fiery cosmos]

Right. But I'd say it's easier to split and filter the sentences cleanly first, then you can loop over them as needed (I realize my code gets things out of order because of the set(...) which is fixable)

[fiery cosmos]

Well it reorders the list into a min-heap, so the smallest item will be at the the front https://docs.python.org/3/library/heapq.html#heapq.heapify and you can have tuples and think of it like priority

[lunar jacinth]

Do you think you could possibly check my work so far and see what you think of it in #help-chocolate

Whenever you're free?

[eager narwhal]

ack(4, 3) can't be computed in python, but neither can it in any languages

[modern root]

That has been done in other functions. I wrote specific functions to split sentences and remove belimshes, I wanted to confirm that my algorithm logic was correct.

[fiery cosmos]

Well it can be "computed" just not written down https://www.wolframalpha.com/input/?i2d=true&i=ackermann(4\(%2C)+3)

[thin iris]

hi guys can u tell me where i can find a good place to learn the algorithms (sorting, divide and conquer, greedy and dynamic programming)?? thank u

[knotty magnet]

check the pins

[lunar jacinth]

Would anyone know how to create a minimal spanning tree using a linkedlist?

[knotty magnet]

how would you make a tree with a linked list

[lunar jacinth]

I think its like more of a graph

[knotty magnet]

a tree is a subset of a graph

[lunar jacinth]

hmm yeah i'm a bit confused on how to make this

My priority queue uses the linkedlist to insert based off of priority

It says to ```py
Navigate your PriorityQueue, after the Nodes are inserted, to find the Minimal Spanning Tree. Be sure your paths do not create a cycle. The end result is a list of Nodes in the lowest cost order with the sum of the lowest cost. Find the lowest cost starting the shortest edge connection and connecting all other airports.

I dont think I have to create a tree, but make something thats acts like one? i'm not too sure

[dapper sapphire]

How can I get better at preventing off by 1 error? Think more about the algorithm I've designed?

[fiery cosmos]

#python-discussion works

[keen hearth]

One way I avoid off-by-one errors is by obviating the need to deal directly with indices by using iterators wherever possible.

For example, say you need to iterate over all successive pairs of values in a list. This is one way you could do it: py for i in range(len(mylist) - 1): x = mylist[i] y = mylist[i+1] But you can see that there are a few places here where an off-by-one error could creep in. Here would be my preferred way to do it:```py
for x, y in zip(mylist, mylist[1:]):
...

To go further, you could encapsulate iterating over pairs of successive elements with a function: ```py
def pairs(iterable):
it0, it1 = itertools.tee(iterable)
next(it1, None)
return zip(it0, it1)

for x, y in pairs(mylist):
...

As they say, there are three hard problems in computer science: concurrency and off-by-one errors.

[knotty magnet]

hard are the three problems there are only?

[fiery cosmos]

I don't like such quotes there are hundreds of hard things in cs (though I get that one is joke)

[vocal gorge]

(One nice detail is that in compiled languages, this easier-readable iterator way can actually result in better performance, because it's more readable to the compiler, too - for example, an iterator over an array can never result in out-of-bounds access, and that allows the compiler to optimize this code to a loop without bounds checks - something that may not be obvious (require proving something the compiler isn't capable of proving) in loop-based code.)

[austere sparrow]

, as well as message ordering Yeah exactly once delivery is also exactly once delivery is also not easy.

[calm spade]

Sooo i know this is more of a math question but

How can i make a list

That has multiples of 10s

Like [10, 20, 30, 40, ...]

Nvm figured it out

[misty monolith]

is it better if I learn algo and data structs on a website or on videos?

[knotty magnet]

whatever works for you

although imo videos tend to be less information dense than reading

[trim fiber]

Depends what you prefer

I prefer docs instead of videos

You can easily find something in document with CTRL + F, cannot do this with videos 😦

[upbeat smelt]

i want to show the recent chats in left section of chats i use Django channels for chating but while chating in one group the new messages from other groups are not coming in left section as a recent chats of chat please can you tell me what to do

[trim fiber]

Possibly not related with channel's topic

[upbeat smelt]

ANSWER is main did you know that

[dapper sapphire]

I actually didnt know about zip until recently to combine elements of two different strings. But that's an interesting use of zip to iterate over a list. Thanks!

[lunar jacinth]

Algorithm(s,p)
    m = s.length
    p[0] = -1
    for i = 1 to m
        k = p[i - 1]
        while k >= 0
            if s[k] == s[i - 1]
                break
            else
                k = p[k]
        p[i] = k + 1

What type of algorithms could this code be used in? Also, could someone explain what it's doing

[keen hearth]

Wait, nvm.

Let's look for clues:
First of all, the array p is interesting, because the values of the array are indices of the same array. So this is some kind of pointer-based data-structure.

[lunar jacinth]

Could it be like a sorting algo?

[keen hearth]

That doesn't seem to be the case, but I could be wrong.

Something puzzling is that the first value of p is set to -1, and it would appear the all the values after that are set to 0. Because after the while loop, k has to be less than 0, which means it could only be -1.

Maybe if you try implementing it in python and experimenting with different inputs, that might give some clues.

[lunar jacinth]

do you happen to know like the purpose of this algo?

[keen hearth]

Yeah, I have no idea tbh 😄 What is the context?

[lunar jacinth]

no context just asks me for the purpose haha

[keen hearth]

Is this a homework exercise? What are you currently studying if so?

[lunar jacinth]

Yeah this is just an exercise in my book

Well its supposed to be like a study guide

[keen hearth]

Oh wait, this is wrong, because it sometimes breaks early.

[lunar jacinth]

Like a study guide question

Hmm maybe I should come back to this question later

Do you think I could ask anther data structures in-order transversal question?

class Node:
    def __init__(self):
            self.data = None
            self.left = None
            self.right = None


def in_order(root, my_list):
    if not root:
        return None

    my_list  = []
    stack  = []
    temp = root
    while stack or temp:
        if temp: 
            stack.append(temp)
            temp = temp.left
        else:
            temp = stack.pop()
            my_list.append(temp.data)
            temp = temp.right

Would this be correct for in_order

I'm trying to ```py
Write a non-recursive algorithm that does an in-order tree walk.

[fiery cosmos]

That's a doubly linked list node I assume What does in_order traversal mean for a DLL it's not like a tree where you differentiate from pre/postorder

A tree node would look more like py class Node: def __init__(self): self.data = None self.right = None self.left = None

[lunar jacinth]

oh

[lunar jacinth]

do that would be correct?

[fiery cosmos]

Won't it loop on temp.lefts forever since you set temp to stack.pop() after temp.left runs out first

and I expect you'd want return [] in the empty root case

loop, not look

[lunar jacinth]

oh instead of returning None, I return empty list?

[keen hearth]

Isn't that what they wrote?

[fiery cosmos]

they edited it

[keen hearth]

Ah right 😄

[lunar jacinth]

yeah im editing it as i go haha

class Node:
    def __init__(self):
            self.data = None
            self.left = None
            self.right = None


def in_order(root, my_list):
    if not root:
        return []

    my_list  = []
    stack  = []
    temp = root
    while stack or temp:
        if temp: 
            stack.append(temp)
            temp = temp.left
        else:
            temp = stack.pop()
            my_list.append(temp.data)
            temp = temp.right

[lunar jacinth]

what exactly did you mean by this?

[fiery cosmos]

I might be wrong about the inf loop thing

[lunar jacinth]

oh okay

[lunar jacinth]

ty

i think that should be good

unless im missing something

lol

[fiery cosmos]

I think it might work in fact though you wanna return my_list, and I'd call temp current or something else

[keen hearth]

Can you explain the idea behind the algorithm that you're implementing?

[lunar jacinth]

class Node:
    def __init__(self):
            self.data = None
            self.left = None
            self.right = None


def in_order(root, my_list):
    if not root:
        return []

    my_list  = []
    stack  = []
    current = root
    while stack or current:
        if current: 
            stack.append(current)
            current = current.left
        else:
            current = stack.pop()
            my_list.append(current.data)
            current = current.right

[fiery cosmos]

and you don't really need the base case since the while loop won't fire anyway if root is None

[lunar jacinth]

oh

[lunar jacinth]

Its supposed to be like a Iterative function for inorder tree traversal

[keen hearth]

Ah right. But can you talk me through how the algorithm is intended to achieve that?

[lunar jacinth]

i use a "stack" because it tells me to, then i just use a for loop to make sure there is stuff in stack or current. current should be my pointer(i believe)

[keen hearth]

It looks like you're going down the left branch until you reach a leaf, right?

[lunar jacinth]

yeah

[fiery cosmos]

it is, then it repeats on the right

[keen hearth]

And the stack is like a trail of breadcrumbs from the root to your location?

[lunar jacinth]

it visits left, then right

[keen hearth]

It seems to make sense to me.

One implementation note though: you appear to create a new list my_list = [] and then not return it.

[lunar jacinth]

Oh I should probably return my_list shouldnt i haha

[keen hearth]

Yeah, probably 😄

I tried to translate that algorithm from earlier into Python: ```py
def foo(s):
p = [None]
for i, x in enumerate(s):
k = p[i]
while (k is not None) and (s[k] != x):
k = p[k]
if k is None:
p.append(0)
else:
p.append(k + 1)
return p

[lunar jacinth]

would me doing my_list = [] in the parameter be the same thing?

[lunar jacinth]

oh haha that first problem xD

yeah im not sure either cuz my classmates are actually confused about itt ttoo

they're also saying it makes no sense

and its not a typo either...cuz i asked my professor haha

he wants us to apply that to some algos(idk which ones yet)

[keen hearth]

That would create a single list that exists throughout the lifetime of your program. It's generally a bad idea to made the default values of parameters mutable objects like lists.

[lunar jacinth]

okay

[keen hearth]

We have a tag that explains better:

!mutable

[halcyon plank]

Mutable Default Arguments

Default arguments in python are evaluated once when the function is
defined, not each time the function is called. This means that if
you have a mutable default argument and mutate it, you will have
mutated that object for all future calls to the function as well.

For example, the following append_one function appends 1 to a list
and returns it. foo is set to an empty list by default.

>>> def append_one(foo=[]):
...     foo.append(1)
...     return foo
...

See what happens when we call it a few times:

>>> append_one()
[1]
>>> append_one()
[1, 1]
>>> append_one()
[1, 1, 1]

Each call appends an additional 1 to our list foo. It does not
receive a new empty list on each call, it is the same list everytime.

To avoid this problem, you have to create a new object every time the
function is called:

>>> def append_one(foo=None):
...     if foo is None:
...         foo = []
...     foo.append(1)
...     return foo
...
>>> append_one()
[1]
>>> append_one()
[1]

Note:

• This behavior can be used intentionally to maintain state between
calls of a function (eg. when writing a caching function).
• This behavior is not unique to mutable objects, all default
arguments are evaulated only once when the function is defined.

[lunar jacinth]

ah i see. right

ty

[keen hearth]

It definitely does something 😄 I haven't quite figured out what.

[lunar jacinth]

i gotta stare at it some more i think

but rn im just practicing other problems for my upcoming exam haha

[keen hearth]

It seems to jump around an array until it finds a matching value or nothing.

You could try running it with some test-inputs.

!eval ```py
def foo(s):
p = [None]
for i, x in enumerate(s):
k = p[i]
while (k is not None) and (s[k] != x):
k = p[k]
if k is None:
p.append(0)
else:
p.append(k + 1)
return p

strings = 'a ab aba aabb abab abba'.split()
for string in strings:
print(string, foo(string))

[halcyon plank]

@keen hearth :white_check_mark: Your eval job has completed with return code 0.

001 | a [None, 0]
002 | ab [None, 0, 0]
003 | aba [None, 0, 0, 1]
004 | aabb [None, 0, 1, 0, 0]
005 | abab [None, 0, 0, 1, 2]
006 | abba [None, 0, 0, 0, 1]

[keen hearth]

I'm not sure if my translation into Python was correct however.

Not sure why I changed -1 to None actually.

!eval ```py
def foo(s):
p = [-1]
for i, x in enumerate(s):
k = p[i]
while k != -1 and s[k] != x:
k = p[k]
p.append(k + 1)
return p

strings = 'a ab aba aabb abab abba'.split()
for string in strings:
print(string, foo(string))

[halcyon plank]

@keen hearth :white_check_mark: Your eval job has completed with return code 0.

001 | a [-1, 0]
002 | ab [-1, 0, 0]
003 | aba [-1, 0, 0, 1]
004 | aabb [-1, 0, 1, 0, 0]
005 | abab [-1, 0, 0, 1, 2]
006 | abba [-1, 0, 0, 0, 1]

[lunar jacinth]

uhhh

🤔

Let me see if i could find something like that in my notes

[keen hearth]

You can get rid of the i actually: ```py
def foo(s):
p = [-1]
for x in s:
k = p[-1]
while k != -1 and s[k] != x:
k = p[k]
p.append(k + 1)
return p

I find the more you remove indices from code, the easier it becomes to understand 😄

[lunar jacinth]

loll

[keen hearth]

It seems to be building some kind of tree maybe? 🤔

Maybe p stands for "parent"

[lunar jacinth]

hmm i think p is supposed to be an array

[keen hearth]

Ah yeah, but it's an array containing its own indices, if that makes sense.

[lunar jacinth]

i tried to find a similar algo to this in my notes but had no luck haha

it cant be like heapq's heapify or something could it

[fiery cosmos]

definitely not that (I hope ) (heapify involves swapping)

[keen hearth]

You could think of the indices as being ids of nodes in a tree.

[lunar jacinth]

true

[keen hearth]

Where each index has a reference to its parent (the value at that index).

Another possible clue: if you look at the outputs of the algorithm, they all seem to have the property that if p[i] == j then s[i-1] == s[j-1].

[lunar jacinth]

do you think its a sorting algorithm or maybe a helper function to do some sorting?

[lunar jacinth]

also is it supposed to be k+1 there in the append?

[lunar jacinth]

Could it possibly do this?

-1 to n

[halcyon plank]

@supple token Please don't try to ping @everyone or @here. Your message has been removed. If you believe this was a mistake, please let staff know!

[lunar jacinth]

Is red-black-tree insert better than AVL insert, or is it the other way around?

[half lotus]

If I remember correctly, RB trees have faster insertion cause AVL trees can end up doing a lot of rotations

[blazing thicket]

Can anyone help me with some code? I'm using openCV

[oblique arrow]

Do you believe that P = NP? Why or why not?

[fiery cosmos]

no

because if P = NP all heck breaks loose

[meager slate]

what is python's hash implementation?

[dapper sapphire]

Are you referring to python's dictionary hash?

https://github.com/python/cpython/blob/main/Objects/dictobject.c

[meager slate]

unfortunately i cant understand C

can you give a bird's eye view of the implementation?

nothing too detailed

[dapper sapphire]

I really dont know. I would have to spend a few hours to get the gist of it .I just pulled it to send the link.

[lunar jacinth]

yep, just read all about that. thanks

[lunar jacinth]

i think it was the KMP algo

[jolly mortar]

the comments look fairly descriptive https://github.com/python/cpython/blob/main/Objects/dictobject.c#L139-L226

[meager slate]

thats one big descriptive comment

[rain valve]

How can I extend a normal class with an existing dataclass?

@dataclass
class B:
    pass

class A(B):
    pass 

I can either generate B in the constructor or beforehand but I'm not sure how to "merge" them

[trim fiber]

!e

from dataclasses import dataclass

@dataclass
class Foo:
  x: int
  y: str

class Bar(Foo):
  @property
  def z(self):
    return self.x * self.y

bar = Bar(3, "*")
print(bar)
print(bar.z)

[halcyon plank]

@trim fiber :white_check_mark: Your eval job has completed with return code 0.

001 | Bar(x=3, y='*')
002 | ***

[trim fiber]

@rain valve as you can see class Bar has default constructor

!e

from dataclasses import dataclass, is_dataclass

@dataclass
class Foo:
  x: int
  y: str

class Bar(Foo):
  pass

print(is_dataclass(Bar))

[halcyon plank]

@trim fiber :white_check_mark: Your eval job has completed with return code 0.

True

[rain valve]

ok thanks alot @ MorowyKomandos 👍

[trim fiber]

👍

[rain valve]

However i need to create the dataclass before hand since its populated with external data

something like this:

@dataclass
class Foo:
    x: int

class Bar(Foo):
    @property
    def y(self):
        print(self.x)

f = Foo(2)

b = Bar(f)
print(b.y)

[trim fiber]

!e

from dataclasses import dataclass, asdict
@dataclass
class Foo:
    x: int

class Bar(Foo):
    @property
    def y(self):
        return self.x

f = Foo(2)

b = Bar(**asdict(f))
print(b.y)

[halcyon plank]

@trim fiber :white_check_mark: Your eval job has completed with return code 0.

2

[trim fiber]

@rain valve

[rain valve]

💯 thx

[nova holly]

I dont understand the difference between a stack and a linked list. A linked list can do everything a stack does so why do stacks exist and when do we use one instead of the other.

[mint jewel]

a stack is an abstract description of a data structure and one way to implement one is with a linked list

though a more common way is with a regular array and having it be of a finite size

[nova holly]

Ok, but when should we use a Stack instead of a linked list

[mint jewel]

when you need a stack for an algorithm

whether you implement the stack with an array, a linked list or sth else doesn't matter that much

though when working in not python, it can be good to keep in mind that linked lists are a bad data structure in terms of performance

[nova holly]

Oh ok thanks!

[nova holly]

k I'll remember that

[fiery cosmos]

For what stuff Database with chatbot is used?

[austere sparrow]

You need a database when you need to persist some data between runs of your program.

[dapper sapphire]

Where/what are the use cases of of nums[nums[i]]:

nums = [0, 4, 1, 3, 2]
nums[nums[i]]

I understand what's happening we are using the value of nums as an index, so we have:
nums[nums[0]] => nums[0] => 0
nums[nums[1]] => nums[4] => 2
nums[nums[2]] => nums[1] => 4
nums[nums[3]] => nums[3] => 3
nums[nums[4]] => nums[2] => 1

So the new list/array now would be: [0, 2, 4, 3, 1]

[fiery cosmos]

I've seen that come up in https://leetcode.com/problems/find-the-duplicate-number/ where you use nums[nums[x]] to advance a kind of index pointer in the list twice.

[dapper sapphire]

Does it have a name?

[fiery cosmos]

Not specifically I don't think

Uncommon in general because it implies all the list elements are from 0 to len-1

[dapper sapphire]

Yup all elements in the list will have to be from 0 to x and the largest element in the list has to be len -1.

otherwise it wouldnt work.

I dont think I had done something like this before. I also saw it in leetcode couple of times.

[south umbra]

is ds algo in python worth it

[mint jewel]

what do you mean worth it?

[south umbra]

are other coder's true that ds algo is not preffered by many companies and many compe coding contest do not allow python

[south umbra]

as a view of job or any competitive coding round interview

[mint jewel]

well, as a job, very few companies needs mathematicians, which is what dsa is.

[south umbra]

oh

[mint jewel]

as for competitive coding, if you know how to do an algorithm in language A and know language B, you know how to do that algorithm in language B (at least within procedural languages, which is C++, java, python, ruby, etc)

[south umbra]

i haven't coded on any other lang

but my friends told learn cpp for dsa

me be like for dsa i have to learn another lang

damn

[mint jewel]

C++ is a great language for dsa, and unlike learning C++ for general programming, it is almost pleasant to use

but python is a viable option as well

[south umbra]

ohk

python

[mint jewel]

if you actually want to do competitive programming on a competition level, you will need C++ in most cases

[fiery cosmos]

you'd probably want cpp for competitive coding because it'll be way faster than python, but for just learning about dsa Python is fine. The concepts hold for any languge

[south umbra]

ohh

[mint jewel]

yeah, there are some problems where C++ lets you get away with a worse solution due to smart compilers, where python needs a smart solution

[south umbra]

some said u r mad to me when i said i'll try with python

i have a very good exp in python i code in django flask and general coding

[mint jewel]

there are some datastructures you can only truly experience implementing them in C, such as a hashtable

[south umbra]

oh

[mint jewel]

but most algorithms are independent of language, and using the correct data structure is also independent

and trees and lists are also possible in python in about the same way

[south umbra]

will i find out resources + help , while using python then for sure python

u have done on python? @mint jewel

[mint jewel]

ye, most of the algorithmic problems I do I do them in python

[lean junco]

https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d40bb
I know knapsack.....winner says its knapsack variation.....
I saw the winners solution but not able to figure out his approach

[south umbra]

got it will follow ur path , ig u will help me , so will u guide me mentor

[mint jewel]

honestly, most of my algo knowledge is from reading pseudocode in wikipedia

[south umbra]

ohh

[mint jewel]

which I am not sure is the best way to learn

[south umbra]

ohh

sadd lyyyfff aryan

[lean junco]

Please helpppp

[mint jewel]

https://runestone.academy/runestone/books/published/pythonds3/index.html

this book is pinned in this channel, so it's likely good

[south umbra]

ohk

[lean dome]

Learning DS&A is more helpful for getting a job than it is for keeping a job.

Lots of companies include DS&A based questions in their interview process, even though the day to day job of software development rarely requires DS&A

[mint jewel]

ye, there is the level of dsa knowledge "I can pass the technical interview" and the level of dsa knowledge "I can come up with one new algorithm that is an improvement on existing solutions"

the two levels are to an extent orthogonal

[lean dome]

I wouldn't say orthogonal... One clearly builds on the other

[mint jewel]

well, someone who researches elliptic curve cracking probably won't solve brace expansion as well or as quickly as someone grinding leetcode 20 hours a week

[lean dome]

Yeah, that's true.

[main flower]

codeforces ftw

[lunar jacinth]

Could someone help me solve my errors in #help-cherries. It's a minimal spanning tree

using doubly linkedlist priority queue

[dapper sapphire]

I was reading a reddit post yesterday, where someone commented along the words:

I have been a dev for 15 years
...
...
but no, they want me to reverse a linked list

made me laugh lol.

[shell knoll]

Hello

I have a date this way

Sorry for quallity. Its a string of a byte of a timestamp

How can i substring the date into a string, without bytes?

[knotty magnet]

decode it with a suitable encoding, it looks like ascii could work

[shell knoll]

Okay, ty

[keen hearth]

So it's a string containing the literal representation of a bytes string?

[pastel bridge]

Hey Could anyone please suggest me the best way to learn data structures and algorithm in Python, course or book or website

[shell knoll]

Yes, str(bytething)

[lean dome]

That's the wrong way to get a str from a bytes. You should have instead done bytething.decode() to decode it from UTF-8 into a Unicode str string

!e ```py
bytething = b'2021-08-04 05:31:28'
s1 = str(bytething)
s2 = bytething.decode()
print(s1)
print(s2)

[halcyon plank]

@lean dome :white_check_mark: Your eval job has completed with return code 0.

001 | b'2021-08-04 05:31:28'
002 | 2021-08-04 05:31:28

[shell knoll]

Not working for me

I tried decode and it simply did not work.

[lean dome]

What happened?

[shell knoll]

Error500. I was passing a file in python cgi.

It was cyphered with pycryptodome, and after deciphering into bytes, decode didnt bring string

But str did, so i went with str

[lean dome]

Well, if it's not text, then .decode() won't work

[shell knoll]

Maybe because the original file didnt encode

It was just bytes+bytes

[lean dome]

In that case you're be better off using base64 encoding. That's a way of representing arbitrary binary data as text

!e ```py
import base64
bytestr = b"\x80hello world\x80"
encoded = base64.b64encode(bytestr)
print(encoded)
decoded = base64.b64decode(encoded)
print(decoded)

[halcyon plank]

@lean dome :white_check_mark: Your eval job has completed with return code 0.

001 | b'gGhlbGxvIHdvcmxkgA=='
002 | b'\x80hello world\x80'

[shell knoll]

I see

Ty, ill try to fix it with base64

[lean dome]

!e ```py
import base64
bytestr = b"\x80hello world\x80"
encoded = base64.b64encode(bytestr).decode("ascii")
print(encoded)
decoded = base64.b64decode(encoded)
print(decoded)

[halcyon plank]

@lean dome :white_check_mark: Your eval job has completed with return code 0.

001 | gGhlbGxvIHdvcmxkgA==
002 | b'\x80hello world\x80'

[lean dome]

That's a bit better.

base64.b64encode() returns a byte string, apparently, so you need to decode it to text.

[austere plover]

Guys

i have one question

I need to know "multiplication of a sequence of matrices" in sportive programming?

it's important to know this topic if i want to take a part in programming contests

i just don't know where i need to ask this

just the title of this topic sounds very creepy

[fiery cosmos]

!aki

[halcyon plank]

*args and **kwargs

These special parameters allow functions to take arbitrary amounts of positional and keyword arguments. The names args and kwargs are purely convention, and could be named any other valid variable name. The special functionality comes from the single and double asterisks (*). If both are used in a function signature, *args must appear before **kwargs.

Single asterisk
*args will ingest an arbitrary amount of positional arguments, and store it in a tuple. If there are parameters after *args in the parameter list with no default value, they will become required keyword arguments by default.

Double asterisk
**kwargs will ingest an arbitrary amount of keyword arguments, and store it in a dictionary. There can be no additional parameters after **kwargs in the parameter list.

Use cases
• Decorators (see !tags decorators)
• Inheritance (overriding methods)
• Future proofing (in the case of the first two bullet points, if the parameters change, your code won't break)
• Flexibility (writing functions that behave like dict() or print())

See !tags positional-keyword for information about positional and keyword arguments

[knotty magnet]

i didn't even notice that 😅

[broken cedar]

not sure if this is the right place to ask this but here goes
so I make a python class, with an __init__ function. Then I make another class that subclasses from that class. If i define an __init__ function for the subclass, will both be used? or just the second one? how does this work?

[trim fiber]

!e

class Foo:
  def __init__(self):
    print("Foo")

class Bar(Foo):
  def __init__(self):
    print("Bar")

class Baz(Foo):
  def __init__(self):
    super().__init__()
    print("Baz")

print("Creating Bar")
Bar()
print("Creating Baz")
Baz()

[halcyon plank]

@trim fiber :white_check_mark: Your eval job has completed with return code 0.

001 | Creating Bar
002 | Bar
003 | Creating Baz
004 | Foo
005 | Baz

[broken cedar]

ok so it overwrites it

[trim fiber]

Depends

You can use super() to call parent's init

!d super

[halcyon plank]

super

super([type[, object-or-type]])```
Return a proxy object that delegates method calls to a parent or sibling class of *type*. This is useful for accessing inherited methods that have been overridden in a class.

The *object-or-type* determines the [method resolution order](https://docs.python.org/3/glossary.html#term-method-resolution-order) to be searched. The search starts from the class right after the *type*.

For example, if [`__mro__`](https://docs.python.org/3/library/stdtypes.html#class.__mro__ "class.__mro__") of *object-or-type* is `D -> B -> C -> A -> object` and the value of *type* is `B`, then [`super()`](https://docs.python.org/3/library/functions.html#super "super") searches `C -> A -> object`.

The [`__mro__`](https://docs.python.org/3/library/stdtypes.html#class.__mro__ "class.__mro__") attribute of the *object-or-type* lists the method resolution search order used by both [`getattr()`](https://docs.python.org/3/library/functions.html#getattr "getattr") and [`super()`](https://docs.python.org/3/library/functions.html#super "super"). The attribute is dynamic and can change whenever the inheritance hierarchy is updated.

[broken cedar]

ok
i think I understand, thanks

[trim fiber]

👍

[azure gulch]

hey how can i created a map at folium and draw some lines i want to add a figure it will move at line as a airplane

[dense walrus]

what size of list do you typically need before deque.appendleft() is worth it?

[knotty magnet]

benchmark it

[onyx root]

why wouldn't you use a deque?

[loud trail]

@normal crescent maybe you could easily make your array extensible on disk with a memory-mapped array? Someone implemented something like that https://github.com/deep-compute/diskarray

Or maybe it's possible to store it as a flat 1d array (not sure what format) and mess with the strides, so it can be simply appended to on disk while keeping the right shape

Seems like a pretty serious optimization though

[normal crescent]

This looks perfect, thanks.

[south umbra]

hey i'm new to drf as most of u r already knowing just learning about the token authentication

my settings and url's are correct and have created token for my superuser "admin" and by that i can fetch it from Postman

but as u can see and i've created url and / for that , so i can open it from my browser but it's showing ERROR

[fiery cosmos]

I know that much lol, but thanks for showing helping hands. I guess I wasn't clear there

[fiery cosmos]

you're kinda at wrong place. #web-development may be a better place to ask this.

[south umbra]

Lmao

Sorru

[ebon kiln]

I am not sure why we use inplace =True while sorting data in pandas

[brave oak]

you don't have to

by default, almost all pandas methods create copies

therefore, you can assign the results to a new variable

[ebon kiln]

I wanted to know what roles does it play , I am sorry i used inplace=False

[brave oak]

say you have

df.dropna(inplace=True)

# basically the same as 
df = df.dropna()

[slim vault]

with inplace=False the result of the operation is returned as a new dataframe, whereas with inplace=True the dataframe that you're operating on is changed

however especially with pandas it is worth saying that the inplace param doesnt strictly dictate how the internal implementation behaves, and inplace operations may still internally create a new dataframe and simply redirect the original pointer

there's even on-going discussion on whether the param should be removed (at least for some operations which aren't truly in-place anyway)

https://github.com/pandas-dev/pandas/issues/16529

[brave oak]

yeah

a lot of this AFAIK

is constrained by the fixed size of numpy arrays

[ebon kiln]

Thank you for the indepth explain

[copper heron]

def partition(data_array, lower_bound, upper_bound):
    pivot_value = data_array[lower_bound]

    start_index = lower_bound + 1
    end_index = upper_bound

    while start_index < end_index:
        while data_array[start_index] <= pivot_value and start_index <= end_index:
            start_index += 1
        while data_array[end_index] >= pivot_value and start_index <= end_index:
            end_index -= 1
        if start_index < end_index:
            data_array[start_index], data_array[end_index] = data_array[end_index], data_array[start_index]

    data_array[lower_bound], data_array[end_index] = data_array[end_index], data_array[lower_bound]
    return end_index

def quick_sort(data_array, lower_bound, upper_bound):
    if lower_bound < upper_bound:
        p = partition(data_array, lower_bound, upper_bound)
        quick_sort(data_array, lower_bound, p-1)
        quick_sort(data_array, p+1, upper_bound)

data_array1 = [1,2,3,4]
quick_sort(data_array1, 0, len(data_array1)-1)
print(data_array1)```

output: [1,2,4,3]

[old rover]

def bubble_sort(a_list):
  #len_list = len(a_list)
  for i in a_list:
    if a_list[i] > a_list[i+1]:
      a_list[i+1], a_list[i] = a_list[i], a_list[i + 1]
    else:
      return a_list[i], a_list[i+1] = a_list[i+1], a_list[i]

this is wrong

[knotty magnet]

yeah

[old rover]

sigh

how do i fix it?

[knotty magnet]

i is an element in a_list, not necessarily a valid index

[old rover]

range(len(a_list)

len gets you the length of a list and range is 0 to that length

nope that still doesn't fix it

oh i see why

File "main.py", line 5, in bubble_sort
if a_list[i] > a_list[i+1]:
IndexError: list index out of range

i will figure it out

oh i was somewhat close

[old rover]

so

def bubble_sort(a_list):
  for val in a_list:
    #values of the list
    for i in range(len(a_list)-1):

i haven't fully written this yet

but if you had a list of four elements

then the length would be four

subtracting one makes it three bc you index from 0

but when you do range right

that's from 0 to 3

so it stops before three

right?

i know why it uses range

bc you can't iterate over a length

it'll throw an error

"TypeError: 'int' object is not iterable"

range returns a sequence of numbers that you can iterate over

[fiery cosmos]

Yeah, a range excludes the stop value

!e so range(4) is 0, 1, 2, 3 (and not 4) py print(list(range(4)))

[halcyon plank]

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

[0, 1, 2, 3]

[fiery cosmos]

exactly

[fiery cosmos]

Hello?

[lyric niche]

no

[edgy otter]

Hey all, I am trying to think of a way to optimize some code. Currently the program is going through each integer and running it through a function to determine a pattern. Based on what that pattern is I know how frequently it will repeat on the number line. I then put the starting number and the frequency into the list. For each subsequent number I subtract the start number and then do a mod of the frequency. If that number is 0 I skip the integer. The problem is that I am now up to 100 million integers that I have gone through and there are 10s of thousands of repeating patterns in the list. It is taking a long time to do each additional check so I need a way to do the skipping a bit faster...

At this point the code should be skipping 98.66% of all numbers so there has to be a way I can reduce this down but I am not sure

[meager slate]

sending the code can help

the text itself is bit tough to understand 😅

[edgy otter]

Sure 🙂 let me clean it up a bit lo

    global intervals_list

    steps_table = calculate_steps_table(1000)
    steps_table = calculate_intervals(steps_table)

    i = 2

    while i < 10000000000:
        steps_cnt, breadcrumb = steps(i)
        intervals_list.append([steps_table[steps_cnt], i])
        i += 1

        while skip(i):
            i += 1

def skip(n):
    global intervals_list

    for e in intervals_list:
        if (n - e[1]) % e[0] == 0:
            return True

    return False```

That's the code stripped down without my debug and print statements 🙂

[azure gulch]

I am looking for a way to get coordinates from a marker/popup in Folium. I want to use the coordinates for further calculations. I know, that Folium is more for visualizing data and maps than getting information back.

[fallow viper]

Hi, anyone know how i would get started using path finding algorithms?

[prime heath]

If anyone has used Google OR-tools, can you please tell me what the objective value in a vehicle routing problem, like in this example https://developers.google.com/optimization/routing/vrp#example, actually mean? In a TSP, the objective value output is simply the total length of the route, but in a VRP it is giving a very large value.

[lethal bridge]

Do you have an example?

The objective should be the total length of the tour

[prime heath]

I have run the code given in the example I have linked as is, and this is the output

Route for vehicle 0:
 0 ->  8 ->  6 ->  2 ->  5 -> 0
Distance of the route: 1552m

Route for vehicle 1:
 0 ->  7 ->  1 ->  4 ->  3 -> 0
Distance of the route: 1552m

Route for vehicle 2:
 0 ->  9 ->  10 ->  16 ->  14 -> 0
Distance of the route: 1552m

Route for vehicle 3:
 0 ->  12 ->  11 ->  15 ->  13 -> 0
Distance of the route: 1552m

Maximum of the route distances: 1552m```

[lethal bridge]

Yes I get the same thing

The 'large' values come from the original data

Note that the original data is given as a distance matrix already

[prime heath]

yes, how does that affect the output?

I mean what does the value mean here?

[lethal bridge]

@prime heath lol now you mention it...

@prime heath The objective seems to be a penalised function of the difference in maximums for the different vehicles

@prime heath Oh I found out the formula for the obj function. It's
100 * max_i(Dist_i) + sum_i Dist_i
where Dist_i is the distance travelled by vehicle i

The 100 comes from distance_dimension.SetGlobalSpanCostCoefficient(100)

The typical objective function is already within the routing thing

I think they do this penalty formulation of the multi VRP because it's a faster solving formulation than a typical ILP

But you could always test it against Gurobi with a 'proper' objective function being the unpenalised maximum of all 4 vehicle distance travelled

I could try it, since I think I have academic gurobi bbut hmmm

[prime heath]

uh huh, I totally did not understand this function

[lethal bridge]

Uhh the source code is like in C so I don't recommend doing that

What I recommend is changing that multiplier to 1000000 and you'll see it does the behavior I just described

Do you have Gurobi? you can try making the formulation via Pyomo and Gurobipy-ing it (in line with this server being python lol)

Pyomo IIRC has additional overhead as compared to like Julia JuMP but it's definitely functional

[prime heath]

No, I actually have no experience in solving optimization problems. OR-Tools was requirement in one of the internships so I thought I should check that out 😅

[lethal bridge]

By the way instead of going Google Maps with their expensive API, I recommend setting up your own OSRM with OSM data - IIRC the license is such that you can use it, even commercially. You have to publish any changes but assuming you're an end user it's likely you have 0 changes and just interfacing means you don't need to do any source code funny things (and so you don't need to publish anything since you're likely not changing source)

[lethal bridge]

TSP solving is quite interesting, OR-Tools generally seems to use a neighbourhood penalty function, and although I get the idea I'm not actually sure how they implement it (and the source code is hard to read)

[prime heath]

Yea there are so many parameters and solution strategy it got overwhelming pretty fast, and the docs seem to be very brief about explaining them.

[halcyon plank]

:incoming_envelope: :ok_hand: applied mute to @fiery cosmos until <t:1628513618:f> (9 minutes and 59 seconds) (reason: chars rule: sent 4608 characters in 5s).

[fiery cosmos]

when there's a collision in a dictionary hash function, i remember that the rest of the items are stored as a linked list.. but what does it actually store in that linked list?

[knotty magnet]

the items?

this is called chaining, it's a collision resolution method

[fiery cosmos]

during chaining, does it store the entire key itself?

[vocal gorge]

Yeah, it's a collision resolution method that Python dicts don't use, I believe

they instead permute the index somewhat (first just incrementing it, then performing more complex bitwise stuff)

[knotty magnet]

yeah, they use open addressing

with a quadratic thing, iirc

[vocal gorge]

I'd expect that, yeah

[knotty magnet]

oh i was wrong, it is linear probing

[fiery cosmos]

Along with quadratic probing and double hashing, linear probing is a form of open addressing. In these schemes, each cell of a hash table stores a single key–value pair. When the hash function causes a collision by mapping a new key to a cell of the hash table that is already occupied by another key, linear probing searches the table for the closest following free location and inserts the new key there.
im shocked that this works

[knotty magnet]

it's quite clever, tbh

python uses open addressing over chaining because the memory overhead of the linked list is too much

[vocal gorge]

actually, reading Fluent Python again, it seems Python doesn't use linear probing at all and resorts to perturbing right away

https://github.com/python/cpython/blob/ac75f6bdd4748b3378dd321f862d13aa1898f77a/Objects/dictobject.c#L138-L142

see the giant comment here for how Python's conflict resolution works

[old rover]

def selection_sort(an_array):
  array_len = len(an_array)
  #length of the array

  for i in range(array_len):
    #0 to however long the array is -1
    minimum = i
    #the first element of the unsorted partition is now the minimum
  
    for j in range(i + 1, array_len):
    #adding one bc 
      if an_array[j] < an_array[minimum]:
        minimum = j

  an_array[i], an_array[minimum] = an_array[minimum], an_array[i]

  return an_array


  print(selection_sort([9,4,5]))

i'm confused about how it's i+1 in the range

or why it's using i+1

[fiery cosmos]

thanks ill have a read

[old rover]

array_len is the length of the list

[vocal gorge]

To start the inner loop from the next element after the current one.

the idea of the selection sort is to find the right element for each position in order

[old rover]

right

[vocal gorge]

so, basically, to fill the ith position we search for the min element among the i+1, ..., n-1th ones.

[old rover]

uhh

i'm gonna try to do it on the whiteboard

[knotty magnet]

ah, you're right

[fiery cosmos]

>>> [hash(i) for i in range(3)]
[0, 1, 2]

Since ints are their own hash codes
🧠 💥

[old rover]

i think i figured it out

if you had a list of

[7,99,2]

the minimum would be 7

bc it starts with the first value in the array

and then it would be replaced by 2

bc 2 is smaller than 7

so it would be [2,99,7]

and it would do the same thing to swap the 99 and the 7

pick 99 as the minimum and then replace it with 7 bc 7 is smaller than 99

[2,7,99]

yay for whiteboards

this is strange to me

def selection_sort(an_array):
  array_len = len(an_array)
  #length of the array

  for i in range(array_len):
    #0 to however long the array is -1
    minimum = i
    #the first element of the unsorted partition is now the minimum
  
    for j in range(i + 1, array_len):
    #adding one bc 
      if an_array[j] < an_array[minimum]:
        minimum = j

    an_array[i], an_array[minimum] = an_array[minimum], an_array[i]

  return an_array


print(selection_sort([9,4,5]))

it prints bc the print call isn't indentented?

i didn't know that was a thing

[vocal gorge]

huh?

[knotty magnet]

when you run a file, it runs the code in that file

[old rover]

if my print is indented one to the right

it doesn't print at all

[knotty magnet]

because after you indent, you put it in the function, after the return

[old rover]

it's in the function?

[vocal gorge]

Well, in your snippet it isn't. That's why it runs without you calling the function.

[old rover]

i did call the function

selection_sort([9,4,5]))

[knotty magnet]

not if you put the print inside the function

[old rover]

oh i'm being a meme

yeah it makes sense

[sage coral]

I’m trying to design a genetic algorithm, but I’m a bit confused. If you start with a population of size k, then select k/2 from the population for crossover: won’t you only have k/2 in your next population? How does the population size reach k again?

[trim fiber]

Afaik you are crossing entries from half of the population to (re)create second half: https://en.wikipedia.org/wiki/Crossover_(genetic_algorithm)

[old rover]

a_list = [1,2,3,4]
print(a_list[:2])

so this starts from the 0th index

and goes up to the 2nd index

but doesn't include the 2nd index

sort of like range

that's cool

[trim fiber]

More about slicing is available here https://docs.python.org/3/tutorial/introduction.html#strings

 +---+---+---+---+---+---+
 | P | y | t | h | o | n |
 +---+---+---+---+---+---+
 0   1   2   3   4   5   6
-6  -5  -4  -3  -2  -1

[old rover]

thank you

[trim fiber]

👍

[sage coral]

So would each of the selected population “mate” with two others? Or is the selected population combined with the offspring for the next generation?

If the latter, what if you want only k/10 of the initial population to make it to the next round, how would crossover work?

[vocal gorge]

There's a ton of different strategies you can use.

Some examples:

1. Each generation, you eliminate some of the population and fill the space by crossover+mutation of the survivors
2. Each generation, you generate an entire new pool by crossover+mutation of current ones (selecting the parents in some way that favors good ones), and replace the current population with the children (so noone lives more than one generation)
3. Technically, you can even have a population size of 1, and replace that gene with a child (generated by mutation) if the child is better - then it's essentially just a local search.

[sage coral]

Do you know of any resources with different methods and their use cases? How do I decide which is most effective?

[vocal gorge]

How do I decide which is most effective?
I want to know that too 😦

[sage coral]

haha yeah I guess thats part of what I need to figure out

Thanks for the help

[dapper sapphire]

So what techniques/concepts are mostly used to solve matrix problems?

[vocal gorge]

What kind of matrix problems?

[dapper sapphire]

For example this, https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/

Someone used binary search tree and heap. And that was new for me. I had no idea we could use binary search tree with lists/array.

[vocal gorge]

In this one, I don't think it's actually related to matrices (in the mathematical sense) at all, really

it's just sorting a list (of rows) by a certain comparison function

the heap/search tree was probably a way of doing that

[dapper sapphire]

Ok.
I read a reddit post where couple of people mentioned BFS and DFS can help with different types of matrix questions.

Yeah, I guess you are right, it could have been done otherwise without using binary seach and heap, and that was just one of the ways.

[knotty magnet]

there aren't really "matrix" questions, there's questions that use matrices

[dapper sapphire]

lol yes

I worded it poorly.

[edgy otter]

Anyone have any thoughts on how I can optimize this code? It basically loops through a set of integers and then skips integers at specific intervals based on patterns determined by previous integers. So it will take 3 run it through a function and based on that it determines that every 16th value from 3 can be skipped and it puts that in a list. Then it does 5 and determines that every 4th value from 5 can be skipped, then 7 it determines every 128th value can be skipped etc. The number of values that can be skipped is well into the 100s of thousands in the list and it is taking quite a long time to get through. I think that adding a sort of the list would help based on interval (since smaller intervals should happen more frequently). However, I am wondering if there is some other method that might make this even quicker. At 125 million times through the loop currently and it is skipping 98.71% of numbers.

    global intervals_list

    steps_table = calculate_steps_table(1000)
    steps_table = calculate_intervals(steps_table)

    i = 2

    while i < 10000000000:
        steps_cnt, breadcrumb = steps(i)
        intervals_list.append([steps_table[steps_cnt], i])
        i += 1

        while skip(i):
            i += 1

def skip(n):
    global intervals_list

    for e in intervals_list:
        if (n - e[1]) % e[0] == 0:
            return True

    return False```

[warped niche]

How

[vocal gorge]

tbh, for one that seems like the kind of thing that would be well faster in something other than Python. That said, you can maybe find the next non-skippable value directly using the chinese remainder theorem? It seems to me like you're searching for the first integer than has remainders of division by certain numbers that aren't certain values, like:

n % intervals_list[0][0] != intervals_list[0][1] % intervals_list[0][0]
n % intervals_list[1][0] != intervals_list[1][1] % intervals_list[1][0]
and so on

it's not obvious to me how to solve it, but perhaps you can just assume a remainder of 0 for all of them except those for which intervals_list[i][1] % intervals_list[i][0] is zero, and 1 otherwise (and you'll also have to make sure all of the [0]s are coprime, otherwise the remainder theorem doesn't apply) - maybe that'd give you the smallest result?

[edgy otter]

Yeah it might be faster in something other than python but python is a lot easier to work with crazy big numbers like 2^68 and decimals out over 500 digits 🙂 C# and C++ would require some work to handle that lol.

[vocal gorge]

that's true, yeah, native biginteger support is pretty awesome

[mint jewel]

C# also has native bigints, no idea bout cpp

but ye, if you know python, use python

[edgy otter]

I know both but it has been a while since I have used C#. Last time I used it I don't think it supported bigints. I think you could specify the size of an integer but if you went past that size you were sol and would have to start the run over with a larger int specified.

[vocal gorge]

(by the way, neither of the functions in this snippet need the global intervals_list declaration - it's only needed when you reassign that variable like intervals_list = .... Reading it or even calling methods like .append on it is fine either way.)