algos-and-data-structs

[chrome raven]

any one can help me out

[tiny frigate]

i need help with data structures and algorithms please DM me if you can i will appriciate it so much thanks

[halcyon plank]

Hey @left inlet!

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

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

[left inlet]

Hello! Can anyone give me a formula for finding 4 points to draw something like this?

[signal canyon]

You draw a square, then draw a square between the points one unit shorter all round, then recurse

https://pythonturtle.academy/5-degree-square-spiral-in-a-square-source-code/

[left inlet]

Is it any way to calculate coordinates of points? (Without using the turtle)

[agile sundial]

🎉 🎉

[signal canyon]

Now how to work out the complexity?

O(Log(n) + log(n)*log(log(n)))?

[agile sundial]

lgtm 👍

[signal canyon]

Log(log(n)) is always less than one right? So it cancels to O(log(n))?

[agile sundial]

how is it always less than 1?

it's monotonically increasing so there's always an input that would make it greater than 1

!e

from math import log

print(log(log(1e100)))

[halcyon plank]

@agile sundial :white_check_mark: Your eval job has completed with return code 0.

5.439202631236047

[signal canyon]

Hmm

So it's not just O(log(n)) weird

[signal canyon]

Or the Log(n) term is always going to swamp the Log(n)*log(log(n))?

[agile sundial]

it won't

the other log(n) is being multiplied by something that is monotonically increasing, so it'd always be greater than log(n) itself

[proper cloud]

How to solve this

[cerulean jetty]

Hey

I need help

So basically i am working on creating an algorithm that will detect brain tumors with a yes and no response ok using a MVP version for the algorithm. And my teacher told me to firstly import the brain tumor data set onto a new google collab project notebook. And then order me to follow a tutorial guide called tensor flow that will help me out To Split the dataset into training / testing / validation sets which is the other step. However, I don’t comprehend the tutorial guide cuz it seems confusing? Can u be able to help me guide n tell what I should be doing throughout the process

It’s a machine learning project

Below is the tutorial guide
https://www.kaggle.com/navoneel/brain-mri-images-for-brain-tumor-detection

Here is the tutorial guide
https://codelabs.developers.google.com/codelabs/cloud-tensorflow-mnist#1

https://colab.research.google.com

That is the google collaboratory notebook website to get all the work completed

Basically u need to import the data sets onto google collaboratory first

[fiery cosmos]

How could I go about turning

a = '("mouse", 2, 0, (2, 2))'

into

a1 = ("mouse", 2, 0)
a2 = ((2,2))

Yes, a is str and a1 and a2 are tuples

[jolly mortar]

!e

from ast import literal_eval
*a1, a2 = literal_eval('("mouse", 2, 0, (2, 2))')
print(a1)
print(a2)

[mild hound]

*a1 ,a2  = a

[halcyon plank]

@jolly mortar :white_check_mark: Your eval job has completed with return code 0.

001 | ['mouse', 2, 0]
002 | (2, 2)

[half lotus]

Say I have 6 items that need to have the same chance of being chosen. Each item can have its own probability. The way selection works is that it goes through each item one a time in a deterministic order. Thus, if each item had a probability of 1/6, I believe the first item checked would actually have a higher chance due to the bias of being first.

What's the calculation to determine what the probabilities should be for each item such that the net result is the same chance for each item? Items checked first would need to have a lower probability, and items checked last a higher probability. But I am not sure by exactly how much.

Or is there no bias at all?

[keen hearth]

So you have something like ```py
if random.random() < p0:
print(0)
elif random.random() < p1:
print(1)
elif random.random() < p2:
print(2)
elif random.random() < p3:
print(3)
elif random.random() < p4:
print(4)
else:
print(5)

[half lotus]

Yeah, I think that is how it's set up.

I wonder... would it just be a probability of 1/6 for the first item, then 1/5, all the way to 1?

[keen hearth]

Ah right. Uhhh I should know how to calculate this

Yeah, so p0 = 1/6.

[half lotus]

Cause each time you pass a choice, the amount of choices decreases

[keen hearth]

Then you have 5/6 probability for the rest of them.

You could think of it recursively. For n items, the probability for the first one should be 1/n.

So, I think, p0 = 1/6, p1 = 1/5, p2 = 1/4, ...

But I would test this with some simulation.

[half lotus]

That's the conclusion I was coming to as well

[keen hearth]

!eval ```py
import random

def randrange(n):
if random.random() < 1/n:
return 0
else:
return 1 + randrange(n-1)

for n in range(1, 10):
freqs = [0] * n
for _ in range(10000):
freqs[randrange(n)] += 1
total = sum(freqs)
print([freq/total for freq in freqs])

[halcyon plank]

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

001 | [1.0]
002 | [0.5011, 0.4989]
003 | [0.3274, 0.3384, 0.3342]
004 | [0.2571, 0.2482, 0.2414, 0.2533]
005 | [0.1945, 0.2005, 0.2021, 0.2016, 0.2013]
006 | [0.1641, 0.1732, 0.1679, 0.1691, 0.1659, 0.1598]
007 | [0.1411, 0.1394, 0.1523, 0.1385, 0.1416, 0.1445, 0.1426]
008 | [0.1252, 0.1224, 0.1272, 0.1282, 0.1281, 0.1262, 0.1202, 0.1225]
009 | [0.1087, 0.1097, 0.1103, 0.115, 0.1124, 0.1048, 0.1143, 0.1123, 0.1125]

[half lotus]

Those look close enough

[keen hearth]

What was the intended application?

[half lotus]

I'm using a tool that goes through a filesystem and chooses one set of files to use out of many variations, each in a different subdirectory. And each directory has a random value associated with it.

I'm guessing it does it this way for performance reasons - so it doesn't have to first get all chances and then pick one. I think it's trying to do it more "on the fly" as it's traversing directories.

And that's also a consequence of the way chances are specified. It could have just been specified in a single file outside the subdirectories, but hey I didn't make this.

Thanks for your help

[keen hearth]

Yeah that's probably it. The usual way to sample from a distribution is to first pick a number uniformly at random between 0 and 1 (random.random()) and then do a binary-search on the cumulative distribution function of the distribution. But this requires that you either have the CDF as a formula/function or that you've pre-caculated it.

[hollow cairn]

how do you represent a directed graph in python? adjacency list?

[agile sundial]

adjacency matrix, adjacency list, edge list all work

[hollow iron]

when is topological sorting useful

[agile sundial]

deciding what order to take classes, when some classes have prerequisite classes

[hollow iron]

lmao thats the problem on im on right now

[agile sundial]

there ya go, it's useful

[fiery cosmos]

hey guys can someone help me on a little script please

[chrome raven]

Hello

[sturdy sorrel]

hi

[chrome raven]

hey man

any one familiar with graph here, doing hackerrank qns

cant seem to pass one test case

[sturdy sorrel]

what is the que send me ss

[chrome raven]

can u come to my help channel

#help-orange

@sturdy sorrel

[copper holly]

Is there a recommended order of class method definitions for these type of methods other than init? regular methods, setters, getters, dunder methods, class methods, and static methods.

[brave oak]

I don't think so?

but in general

public stuff first

so all the nonpublic methods @ the bottom

attributes before methods

class methods first

is what I do

[copper holly]

Ah ok

[copper holly]

Thnx

[chrome raven]

hello

anyoe can help with a graph algo qns

[split nebula]

    k = [(i + 1) - abs(i + 1 - x) for x in range(1, 2*i + 2)]
    print(k)``` How do i print each k's element without spaces

[split nebula]

Outputs: [1] [1, 2, 1] [1, 2, 3, 2, 1] [1, 2, 3, 4, 3, 2, 1] [1, 2, 3, 4, 5, 4, 3, 2, 1]

I want: 1 121 12321 1234321 123454321

[jolly mortar]

you could pass them k's elements as separate arguments to print and set sep=""

so print(*k, sep="")

[split nebula]

thank you so much it works!!

didnt know you could modify seperator string in print thanks a lot

[chrome raven]

anyone familiar with graph shortest distance algo can help me out at #help-mango

[fiery cosmos]

.

[chrome raven]

need some help man

#help-mango

[analog ferry]

anyone aware of a python lib that allows nicely usable c datastructure "lists" - im looking for something that gives me a list[tuple[uint32, uint32]] but id like to have the overall memory usage of a c uint_32_t data[][2] - ideally without numpy as a dependency

[jolly mortar]

array.array maybe?

its in the stdlib

[analog ferry]

it doesn't support complex types as far as i understood

if array supported struct.struct, it would be easy

but it doesnt

[jolly mortar]

hmm

[keen hearth]

Would it be acceptable to have two arrays side-by-side?

[analog ferry]

@keen hearth thats thinkable, im currently looking into shifting things up so i can use a single array of double size

[rain cedar]

Good evening, who has a solution for an algorithm that finds all the shortest paths between 2 nodes in an undirected and unweighted graph?

[feral hound]

have a look at BFS and A*

[brave owl]

What is the big(O) of a string index slice if I just do string = string[0:len(str)-1]

Basically removing the last element

[feral hound]

https://www.reddit.com/r/learnpython/comments/kqhcys/what_is_the_time_complexity_of_slicing_a_list/

[rain cedar]

I did a bfs but, it return us all of the paths going to the destination node, so in a graph with a high number of vertices it's a very big complexity

[feral hound]

also in python you can just do
string[0:-1] its the same

[brave owl]

follow up question, is there a way to pop last from a string?

in O(1) time?

[feral hound]

strings in python are immutable so if you want to remove the last char in the string you have to assign the variable to a new string without that char

[brave owl]

ok so that means theres no way to do it in o(1)

damn that sucks

[feral hound]

A* is more efficient, you could also have a look at dijkstra's

there are a lot graph search algos, which one works best depends on your situation

[formal forge]

but dijkstra is for weighted graph isnt it

[brave owl]

i jsut had an interview and implements a for loop with string slicing and i though it was o n but itnerviewer explained it was n^2

made me feel stupid for not knowing that

[feral hound]

you could do it by giving all edges the same weight

[formal forge]

@feral hound we implemented something but it's not working for everygraph, could you have a look on DM to what we did

[feral hound]

sure, can't promise that I can help though

[formal forge]

thank you

[agile sundial]

that's just bfs :P

[agile sundial]

you would just stop when you found a single path

since the first you reach something is the shortest path to that thing

because of how bfs works

[feral hound]

I'm not sure if this person was working with @formal forge , but if that was the case then they actually wanted every shortest path to be returned, but they had it only returning one path

[agile sundial]

eh? ok I interpreted that differently

[feral hound]

yeah I did too until I actually saw the problem

[vital valley]

Hi guys! just a quick question i'm doing f or a leetcode

        retptr = None
        ret = retptr
        
        for i in range(len(lessthanx)):
            retptr = ListNode(lessthanx.pop(0).val, None)
            print(retptr.val)
            retptr = retptr.next
        for i in range(len(greaterthanx)):
            retptr = ListNode(greaterthanx.pop(0).val, None)
            print(retptr.val)
            retptr = retptr.next

        return ret

why isn't my ret returning anything here?

[agile sundial]

the only ret = ... line is at the top, when you assign it to None

[vital valley]

but how come if ido something liek this :

ptr = head

ptr = ptr.next
ptr = jdkfjskdf
ptr = ptr.next
...

return head

this would edit head perfectly, and when i return head it's fine

i'm also trying to add new nodes onto "ret"
while retptr is my pointer that iterates through

[feral hound]

theres a few things going on but search up pass by reference vs pass by value

[agile sundial]

in the second example, ptr is referencing the object that head references. this is all good and it works

[feral hound]

thats the main cause for your confusion

[agile sundial]

in the first, ret references what retptr references, namely None

you don't reference a variable name, you reference objects

[feral hound]

even the second one tbh it probably doesnt work the way you think it works

[vital valley]

really?

i feel like i've done something similar with the second one a lot

@agile sundial hm, what if, then

I made a dummy Node just for the sake of referencing an object?

also thanks a lot you two so far

[feral hound]

tbh this shouldnt work at all, every time you do ptr = ptr.next

you set the variable to reference something else it wont change what
head
is referencing

what is the problem you are trying to solve?

[vital valley]

not sure if that part is relevant because this issue has occured to me two/three times

but i'm basically just trying to like

it's so basic but idk why im stuck haha

i'm just trying to add nodes to a node

and return the head

[feral hound]

can you link the leetcode question?

[vital valley]

https://leetcode.com/problems/reorder-list/

i'm sure tehre are other ways to solve it

but i'm trying to figure out how to do what i'm trying to achieve

[feral hound]

and what are
ret and retptr supposed to represent?

[vital valley]

retptr iterates through my new linked list, ret

i wanted ret to always point to the head of this new linked list

so i can just return ret

oh, sorry

https://leetcode.com/problems/partition-list/

this is the specific problem

but still it's the same issue i ran into

[feral hound]

!e

class Node():
    def __init__(self, value):
        self.value = value
        self.next = None


head = Node(0)
cur = head

for i in range(1, 10):
    cur.next = Node(i)
    cur = cur.next

cur = head
while cur != None:
    print(cur.value)
    cur = cur.next

[halcyon plank]

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

001 | 0
002 | 1
003 | 2
004 | 3
005 | 4
006 | 5
007 | 6
008 | 7
009 | 8
010 | 9

[feral hound]

have a look at this it should give you an idea of how to traverse the linked list and how to change its order

[feral hound]

what I just sent should still hold

[vital valley]

@feral hound word i'll take a look at it

[feral hound]

https://www.pythondiscord.com/pages/guides/python-guides/mutability/

have a look at this and also search up pass by reference vs pass by value btw thats whats causing you problems rn

[vital valley]

thanks so much @feral hound

[raven kraken]

Can anyone tell me how can we find product of all elements of an array using map function?

arr = [1,3,4]
def Product(arr):
    p = 1
    for i in arr:
        p *= i
    return p

a = list(map(Product, arr))
print(a)

This is what I tried but it is giving me error

[jolly mortar]

why do you need to use map...?

just Product(arr) should work

map is for when you want to apply a function elementwise
the Product function here operates on the array as a whole

[raven kraken]

Actually I was learning about map function so I thought maybe I should find product of an entire array using this

[jolly mortar]

nah, this isn't a valid usecase for map

[raven kraken]

Ohh okay I didn't knew about that

[sturdy mason]

I have an output with two valid json objects but they aren't separated - ie: [{...},{...},{...}][{...}{...}{...}]
what is the best way to convert this into a csv?
@jolly mortar any chance you have time to help me with this one?

[jolly mortar]

if you wanted to multiply each element in the list with itself, you might have used map:

def multiply_with_self(n):
  return n * n

arr = [1, 3, 4]
for i in map(multiply_with_self, arr):
  print(i)

(this would print 1, 9, 16)

[raven kraken]

yeah after watching this only I tried to find product of an entire array

Anyway thank you so much for your time @jolly mortar

[chrome raven]

Helllo

any kind soul can help me with a shortest path graph algo question

Your task is to complete the function named find_highest_scores_and_paths(edges, weigths, start, end) that take as input edges, weigths, the starting user, and the end item and return the corresponding best path score and a list of paths with the same best path score.

More specically, the inputs are:

edges: this is directed edge list, e.g., [[i0, u1], [i0, obj1], ... ]. (refer to sample1.txt)
weights: edges’ corresponding weights, e.g., [0.1, 0.4, ...].
start: the starting node, e.g., u1.
end: the end node, e.g., i5.
The return values are:

maxscore: the best path score, e.g, 0.3446
list of paths_list: maxscore’s corresponding paths, e.g,
[[′𝑢1′,′𝑖1′,′𝑢3′,′𝑖5′]] for solution with only one maxscore path found [[′𝑢1′,′𝑖1′,′𝑢3′,′𝑖5′] , [′𝑢1′,′𝑜8′,′𝑢2′,′𝑜9′,′𝑖5′] ] for solution with multiple maxscore paths found

[unborn wedge]

Hi, I'm trying to repair a deprecation warning in a library that is using a .tostring() on an array.array
From what I have gathered, it's an array of bytes that combine to a value.

raw data: array('B', [0, 51, 51, 115, 225, 255, 255, 255])
with tostring and struct.unpack: (1932735232, -31)
what the library actually outputs: (parameter name)RT60  (value)0.8999999761581421

array('B', [1, 0, 0, 0, 225, 255, 255, 255]) (1, -31)
RT60ONOFF                1

The code it's using is:

if data[2] == 'int':
  result = response[0]
else:
  result = response[0] * (2.**response[1])```

(edit):
I'd like to get ahead of the deprecation, so I'd like to change how the raw data is converted.

[worthy wing]

Hii, im new to the server, and was looking for help to build a python algorithm to trade in stock markets, is somebody here familiar with how to do it?

[vocal gorge]

A compatibility alias for tobytes, with exactly the same behavior.
https://numpy.org/doc/stable/reference/generated/numpy.ndarray.tostring.html
So it seems to me you just need to change it to tobytes.

alternatively, you could not use struct and instead use numpy methods to reintepret the array as being made of 2 32-bit signed ints, rather than 8 bytes:

assert response.shape == (8,) # make sure it's of the expected form
response = response.view(dtype=np.int32)

[unborn wedge]

Thank you and sorry, I didn't look closely enough at the warning message (hadn't eaten for too long) and didn't notice the '.tostring() is depricated. Use .tobytes()' part of the message. 😳

[restive python]

ive got a list of (x,y,z) tuples were I want to remove similar tuples , not duplicates since duplicates dont exist. ANy suggestions ?

[keen hearth]

Hello 🙂 How are you measuring similarity?

[restive python]

image a 3d axis and I dont want two vectors (x,y,z) to be to close to each other , say 0.5 minimum distance apart on each scalar. Or x,y could be the same for both vectors but say z has a difference of +1 compared to z2, that would also be fine to keep

I know its ambigious but thats the general concept

[keen hearth]

So would just setting a maximum on the Euclidean distance be ok?

Say you want to consolidate pairs of points which are less than d apart from each other. You could build a hash-table of d x d x d buckets. Then for each point, search its neighbourhood of buckets (the bucket it belongs to and the 26 that surround it) for points that are within that distance.

[restive python]

I havent thought about that 😄

Ive got a set of dx dy dz

Then for each point, search its neighbourhood of buckets (the bucket it belongs to and the 26 that surround it) for points that are within that distance. No clue about this concept , link ?

[keen hearth]

Erm, I can't resist writing some code for this. Hold on one second 😄

[restive python]

Wondering where 26 came from ?

[keen hearth]

Alright, this is what I came up with: ```py
import math, collections

points = [(1.0, 2.0, 3.0), ...]
d = 0.5

Build the table:

table = collections.defaultdict(list)

def get_bucket(point):
x, y, z = point
return int(x//d), int(y//d), int(z//d)

def get_neighbourhood(bucket):
i, j, k = bucket
return {
(i+di, j+dj, k+dk)
for di in (-1, 0, 1)
for dj in (-1, 0, 1)
for dk in (-1, 0, 1)
}

for point in points:
bucket = get_bucket(point)
table[bucket].append(point)

frontier = set(points)
consolidated = set()

while frontier:
point = frontier.pop()
for bucket in get_neighbourhood(get_bucket(point)):
for other in table[bucket]:
if point == other:
continue
if math.dist(point, other) < d:
frontier.discard(other)
consolidated.add(point)

But hopefully that illustrates the idea.

[restive python]

talk about inferiority complex 🤣

[keen hearth]

3*3*3 - 1

[feral hound]

wow that was quick

[restive python]

please tell me ur some genius so that i fell less bad

[keen hearth]

It's called the Moore neighbourhood: https://en.wikipedia.org/wiki/Moore_neighborhood

[keen hearth]

Nah, I just do a lot of these sorts of algorithm problems 😄

[restive python]

man this is going in my notes for future reference thanks very much

[rain cedar]

Good evening, does anyone know, or have any documents (sources) on the Expected Force centrality in graph theory (i want to understand this topic for a work)? Here is the formula for this topic that I didn't understand. wikipedia page url : https://en.wikipedia.org/wiki/Node_influence_metric

where dj is

[restive python]

curious whats the time complexity ?

[keen hearth]

Erm, I believe it is O(n) with respect to the number of points.

[restive python]

I kind of had the similiar approach but just with for loops and I think it was gonna be 0(n^2) or worse even 🤔
Appreciate clever people in these chat rooms 😄

[feral hound]

should be a bit worse than O(n), O(n * m * k), n number of points m number of buckets k number of points in a bucket

although I dont think that is fully correct either but I think its closer to that

[restive python]

nice

didnt expect this for 3d

[feral hound]

in 3d its a 3by3by3 cube

[restive python]

In cellular automata, the Moore neighborhood is defined on a two-dimensional square lattice and is composed of a central cell and the eight cells that surround it.

oh ok got u

[keen hearth]

Ah yeah, if all the points lie in the same bucket, you're going to have a bad time 😄

[feral hound]

now that I look back at it its just O(n * k) since get neighborhood returns 26 buckets and k is the number of points in those buckets

[fluid silo]

why is this wrong?

it should work im confused why it isnt working

[agile sundial]

you're trying to use a string as an operator, just remove the quotes

[keen hearth]

Just to clarify, are you trying to print e.g. 1 % 2, or the result of this calculation?

Oh right. I think you probably meant to do print(num1, "%", num2) (missing the commas).

[fluid silo]

ohhh alr

ty

[keen hearth]

👍

[fluid silo]

last thing sorry

how do i make them answer line 11

like it says num1 % num2 and i want them to answer that in the output

not just a print

@keen hearth

[agile sundial]

use another input

[keen hearth]

Yep, just use input rather than print.

[fiery cosmos]

i need help, i have coded a game and when i start it the terminal says AttributeError: module 'turtle' has no attribute 'Screen'

and i have typed screen = turtle.Screen()

[keen hearth]

Hello @fiery cosmos. You'd probably get more attention for your question in a help channel. See #❓｜how-to-get-help for instructions on claiming one 🙂

[feral hound]

I think getscreen is what you want
https://docs.python.org/3/library/turtle.html#turtle.getscreen

[fiery cosmos]

already tried getscreen

[brisk hemlock]

what would the syntax look like to get this sort of table in python

im assuming I will need a 2D array but idk how that would look like (especially with the example above)

is there not a more simple way

i thought you could just do it by 2D arrays or something

ye its ordered luckily so im not too worried about that

i think im just going to print the labels themselves

and not include them with the array

[feral hound]

you could just use a 2d array as you said, you could also use a pandas data frame

https://pandas.pydata.org/pandas-docs/stable/reference/api/pandas.DataFrame.html

[brisk hemlock]

array1 = [[0, 0, 0, 0], [0, 0, 0, 0]]
print("book")  print("ID")
#here i print the elements```

im thinking this sort of thing

[feral hound]

array1 = [(0, 0), (0, 0), (0, 0), (0, 0)]
print("book")  print("ID")
#here i print the elements

I think something like this makes more sense

[brisk hemlock]

ahh in that format

array1 = [(3, 3), (0, 0), (0, 0), (0, 0)]
print(array1[0])```

would that print 3, 3?

[feral hound]

python is 0 indexed

[brisk hemlock]

oh ye i forgot

[feral hound]

!e

array1 = [(3, 3), (0, 0), (0, 0), (0, 0)]
print(array1[0])

[halcyon plank]

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

(3, 3)

[brisk hemlock]

oh pog

nice

[feral hound]

but I do think using pandas dataframe is probably better depending on what you want to do

[brisk hemlock]

but can 1 element be a string and the other element a integer? or will that cause a issue

[feral hound]

yeah no problem

[brisk hemlock]

I have to code most of it myself unfortunately

[feral hound]

wait you mean with a dataframe?

in that case im not 100% sure

[brisk hemlock]

like array1[0]

do both have to be 3, 3

[feral hound]

yeah with that no issue

it can be any type

[brisk hemlock]

ok im sorted then

thanks

i always forget 2d arrays in python after i havent coded for a few months

[dark aurora]

How to make this code fast enough to complete this task in time (https://cses.fi/problemset/result/3075006/)

a,b,md,tfm,it = list(map(int, input().split())),list(map(int, input().split())),(10**9)+7,0,2
n,m = a[0],a[1]
cur,bac = list(map(int, "0"*(m+2))),list(map(int, "0"*(m+2))) 
b.insert(0,0)
b.append(0)

if b[1] != 0:
    bac[b[1]] = 1
else:
    bac = list(map(int, ("0" + "1"*m + "0")))
    


if n == 1:
    if b[1] != 0:
        tfm = 1
    else:
        tfm = m
else:
    while it != n+1:
        if b[it] != 0:
            cur[b[it]] = (bac[b[it]] + bac[b[it]+1] + bac[b[it]-1])%md
            if it == n:
                tfm = cur[b[it]]
                break
        else:
            for i in range(1,m+1):
                cur[i] = (bac[i] + bac[i+1] + bac[i-1])%md   
                if it == n:
                    tfm = (cur[i]+tfm)%md
        bac = cur
        cur = list(map(int, "0"*(m+2)))
        it = it+1
    
           
print(tfm) ```

[idle pier]

what does interweaved structure mean?

[lucid violet]

supposed to be I want to find and replace string inside curly brackets {{}} with matched variable values. but didnt get expected output?

code = {"BossFirst": ["irish","rico"], "BossLast" : ["paclibar","pollante"]}
text = "this i {{BossFirst}} {{BossLast}}"
def loop(code,text):
text_var = text
text_var = text_var.replace("{{"," {{").replace("}}","}} ")
text_var = text_var.replace("{{", "").replace("}}","")
text_var = text_var.split(" ")
for text_var in text_var:
for key,value in code.items():
if text_var == key:
for value in value:
text = text.replace("{{%s}}" % key,value)
print(text)
loop(code,text)

Actual Output:
this i irish {{BossLast}}
this i irish paclibar

Expected Output:
this i irish {{BossLast}}
this i irish paclibar
this i rico {{BossLast}}
this i rico pollante

[fluid silo]

why is it not working

shouldnt the user be able to put in an answer

thats what line 12 is for

and when they answer the question the answer (line 13) shows

that works but in the output i want the user to be able to type an answer

right here

after teh "=" sign

ty

tysm

got it to work

[restive python]

Any hint on what to do if the points dataset keeps on refreshing or adding new data , not to end up with a huge iteration count ?

[restive python]

Hi !
I would really like if you could possibly evaluate my method 🙂

[shut breach]

check the neighborhood of each point as it's added

[fiery cosmos]

class Node:
    def __init__(self, value, left, right):
        self.value = value
        self.left = left
        self.right = right
    
def isOperator(c):
    if (c == '+' or c == '-' or c == '*' or c == '/' or c == '^'):
        return True
    else: 
        return False

def inorder(t):
    if t is not None:
        inorder(t.left)
        print(f'{t.value} ', end = '')
        inorder(t.right)

def constructTree(postfix):
    stack = []
    #traverse through every character for char in postfix:
    for char in postfix:

        #if operand, simply push into stack
        #leaf node 생셩
        if not isOperator(char):
            t = Node(char, None, None)
            stack.append(t)

        #Operator
        else:
            #Pop two top nodes and make them children
            t1 = stack.pop() #right
            t2 = stack.pop() #left
            t = Node(char, t2, t1)

            #Add this subexpression to stack
            stack.append(t)
            #print(t.left.value, '', t.value, '',t.right.value)

    #Only element will be the root of expression tree
    t = stack.pop()
    return t

if __name__ == "__main__":
    postfix = "32*56/+" #input함수 이용
    expressT = constructTree(postfix)
    print("중위 표현의 수식\n")
    inorder(expressT)

In the constructTree function, I get it is iterating through the entire postfix expression and setting it up as a binary tree (I drew the tree on paper) but what is happening in t = stack.pop() and return t?

I drew the tree to represent the constructTree func but i dont get what’s being passed off when returning t?

[hardy dawn]

Do I need to code to study algorithm or just analyze on the paper

Thanks in advance

[grizzled schooner]

you should make sure you're able to implement the algorithms yourself. even if you think you understand the concepts behind it, you can check that you really understand by trying to implement

[hardy dawn]

If I use pseudocode to implement the algorithm, does it count ?

@grizzled schooner

[grizzled schooner]

do you want it to "count"?

using a real lang would probably be better since then you can test that it works

but psueodocde is better than nothing

[hardy dawn]

I meant that I look up a pseudocode to implement the algorithm by real language ?

Is it good or I understand the concept then I implement by myself ?

[grizzled schooner]

i'd recommend looking at the pseudocode and trying to understand it, and then trying to reimplement without looking at the pseudocode

[hardy dawn]

Oh thanks for your advice 😄 @grizzled schooner

[grizzled schooner]

np :)

[restive python]

I just remember the last iteration count and always start from there

[restive python]

wth are they asking 😂

@keen hearth Here's my method works perfect, Euclidian rules thanks 😄

filter_counter <= global variable (list)

[vale drift]

When we are trying to traverse a binary tree, do we write our traversal(inorder, preorder, postorder) method in the node class or in the binary tree class?

I can see a case for both. Thoughts?

[fiery cosmos]

Could be both and the one in the binary tree class simply calls self.root.inorder or preorder etc

[agile sundial]

if you have a binary tree class though it'd make more sense to be in the binary tree

you wouldn't have access to the nodes if you're using the tree class

[dark aurora]

Exactly what i wrote, i don't know how to make a program fast enough for this task?

[signal knot]

Can anyone show me examples of O(log n) and O(n log n) in Python of course?

[jolly mortar]

binary search is O(log n)

many sorting algorithms (heap sort, merge sort) are O(n log n)

[signal knot]

@jolly mortar Thank you!

Why is a list comprehension so much faster than an appending for loop?

For example : ```py
l = []
for i in range(1000):
l.append(i)

l = [i for i in range(1000)]

[honest mantle]

i think its because in list comprehension u are using more c codes than python and also you arent creating any empty list before comprehension.

[vital siren]

This article breaks it down to the assembly calls: https://newbedev.com/why-is-a-list-comprehension-so-much-faster-than-appending-to-a-list

[signal knot]

@vital siren Thanks for sharing

@honest mantle Looks like you were right: "the list comprehension is still faster because the list is created in C, rather than built up one item at a time in Python."

[fervent saddle]

It still does the loop in python

So it’s not completely in C

It’s not like it’s equivalent to list(range(1000))

!e ```py
from timeit import timeit

def f():
return [n for n in range(10000)]

def g():
return list(range(10000))

print(timeit(stmt=f, number=1000))
print(timeit(stmt=g, number=1000))

[halcyon plank]

@fervent saddle :white_check_mark: Your eval job has completed with return code 0.

001 | 0.5517169516533613
002 | 0.30037298146635294

[ivory yacht]

The reason it’s a little faster is that the append() method doesn’t need to be looked up and called, Python can directly call the list append logic.

[fervent saddle]

That’s a reason why it’s not as fast even if you store list.append in a local variable

[brave oak]

what about resizing?

it's not optimised for append, right

[ivory yacht]

It does that the same way as append, nothing special.

[brave oak]

what is "it"

[ivory yacht]

LIST_APPEND.

[brave oak]

don't comprehensions use length hints

[fervent saddle]

!e ```py
import sys

print(sys.getsizeof([None] * 1000))
print(sys.getsizeof([None for _ in range(1000)]))

[halcyon plank]

@fervent saddle :white_check_mark: Your eval job has completed with return code 0.

001 | 8056
002 | 8856

[ivory yacht]

Comprehensions can't use length hints because of if and additional for clauses, those could make it produce more/less items.

[slender sandal]

But aren't they being evaluated?

Weird

[fiery cosmos]

Given 2 numbers from the board eg (0, 1) i want to find the shortest distance between them using a knights move in this case the shortest number of moves would be 3

can someone help with that please

is there a formula that could be created to solve this

[fiery cosmos]

would someone be able to explain why the bigo notation is o(1) in this particular question? and tag me please that would be wonderful !

[fervent saddle]

Because you’re just changing a value in the array

Most of that stuff is a red herring, it’s basically just asking “time complexity to write a value in an array”

[fervent saddle]

Forgot to tag

[fiery cosmos]

oh so to further expand upon this, every time you would enter a value it would just be the same time right like if i was to pass in another value into the function lets say i could only input one number at a time due to the (n) right?

[fervent saddle]

I’m not sure

But

It’s like it’s asking “complexity of list.append ignoring resizing”

I guess that’s what it’s trying to ask

[fiery cosmos]

ahh right so yeah each time you would input another value into the unsorted list it would take the same amount of time each time you inputted a value?

[fervent saddle]

Yeah

[fiery cosmos]

awesome thank you so much for explaining!

[fervent saddle]

np

[fervent saddle]

I think that’s a path finding thing where you could use something like A* algorithm, but I might be wrong about that

[glossy breach]

simple bfs should work

A* is overkill, i think so

[fiery cosmos]

can i just confirm that the reason why the answer is o(n^2) is because of the n x n in the question?

[ivory yacht]

When calculating time/space complexity, the first thing you need to do is pick the size variable you care about (so n), and then the 'basic operation' you're counting. Here that's sort of implied, but it'd be the addition operation. So then the complexity is simply the number of times that operation occurs.

How many times do you do a + for any given n value?

[fiery cosmos]

hold on i am just reading what you have said

[fiery cosmos]

what do you mean by a + for any given value?

[ivory yacht]

The "function" we're evaluating here is "add 1 to every element" in the matrix.

So, how many add operations does it need to perform?

[fiery cosmos]

2 because it needs to add 1 to each element in each array?

because its 2 demensional?

[ivory yacht]

No, once for every element..

[fiery cosmos]

so for example

arr = [[1, 2, 3], [4, 5, 6]]

[ivory yacht]

Well that's a 2x3 array, not nxn.

[fiery cosmos]

we would need add the value of 1 to each element in that array?

oh

[ivory yacht]

Yeah. So 6 times.

[fiery cosmos]

arr = [[2,], [6]]

this is a n x n right?

[ivory yacht]

Yeah, 1x1.

2x2, 3x3, 4x4 etc

[fiery cosmos]

so because i need to add 1 to each element in the 2d array that would be they would times by themself or would mean that the bigO notation is 0(n2)?

[ivory yacht]

Yeah, because you're doing it once nxn times.

[fiery cosmos]

so

if

i had a 3x1 array

would the notation be O(n3)

👀

[ivory yacht]

No, still n^2, because nxn = n^2.

[fiery cosmos]

so the size of the array does not matter

[fervent saddle]

You mean like if it’s just the size of a chess board and it’s not arbitrarily large?

[glossy breach]

yeah

but bfs is O(n * m) anyway

[fiery cosmos]

/yo

can someone explain alogos and data types

i have a test coming up

[grizzled schooner]

which ones specifically do you need help with?

[fiery cosmos]

Pseudocodes basics

[grizzled schooner]

what? like interpreting pseudocode?

[fiery cosmos]

yea

[grizzled schooner]

oh

do you have any specific difficulties with interpreting it or is it just hard to understand in general

[fiery cosmos]

general

[grizzled schooner]

um, can you send like a sample bit of pseudocode from your class?

and then maybe i can walk you through it or something

[fiery cosmos]

ok

Write an algorithm which inputs password, the password must have two numeric characters and one capital letter.

[grizzled schooner]

ok

uhh it seems like in this scenario you would have to write the code, not interpret it

[fiery cosmos]

okay

can u explain that'

[grizzled schooner]

so you would basically just have to make one if statement checking whether there is a capital letter, and one if statement checking whether there are 2 numeric characters

i'm not sure about the syntax of your pseudocode because all pseudocode is different

[fiery cosmos]

okay thanks anyways

may i ask, are you a teacher or a student?

[native fjord]

So guys a simple question

how to convert this

testcode3 = '[123, 456, 789]'
# into this:
result = [123, 456, 789]

[grizzled schooner]

student

[grizzled schooner]

regex would be good for this, or you could slice out the "[" and "]" and split on ", "

[native fjord]

it already works

thanks

[grizzled schooner]

oh ok

[round rain]

Hi fellow python coders ! I search PyPI and google for this but I did not find a good answer so I'm asking here.
Does anybody here know a good module about nested dictionary manipulation ? Thanks a lot !

Basically what I would like to do is to edit all keys of the same level, or all keys of a sub-dict, that sort of stuff

[vocal gorge]

There is actually a module for that, yes:
https://pypi.org/project/jmespath/

(disclaimer: never used it; I stumbled upon it by accident when looking at PyPI's most popular packages)

(I don't know why it's in most popular either; presumably it's a dependency for some popular packages)

it's not very clear whether it allows editing though, might be only searching.

[round rain]

Thanks a lot !

[cosmic geode]

this might be a bit basic, but I was going through AoC2020 and there's one puzzle where you have to use "binary space partitioning" to find the seats of a bunch of boarding passes, and use those to "calculate their seat ID" and find the highest one.
It's really cooks down to "find the highest number in a list of 10-bit values" (sort of clever design though. really allows anyone to participate)

Anyway, the 2nd part of the puzzle has you find your own seat, which should be the only one available (not in the previous list)
It mentions that there are no seats for the upper and lower most parts of the range, but you know that that your ID +/- 1 both exist.
ie. for some slice range(2**10)[x:y] you know that x+1 <= your_seat <= y-1

That was a long explanation, sorry.
I can't help but think that the 2nd part is also possible to solve using some of the theory around b-trees / binary partioning. at least there must be a better way than brute forcing?
All I really know is that b-trees makes it really efficient to find an element in a sorted list... does it provide any tools to find a missing value?

perhaps if I had actually built the binary tree for the first part of the puzzle instead of just parsing the values directly?

[vocal gorge]

Like, you have a sorted list with one missing element, something like x, x+1, x+2, ..., y-1, y with one missing?

I feel like you can then consider the function lst[i] - lst[0]-i, which is 0 until the missing element, then -1, and use binary search to find the first i for which it's -1.

[timid goblet]

YO, i need help, how to turn keys (strings) of a dictionary into num ??

[cosmic geode]

map(int, yourdict.keys())

[timid goblet]

it doesnt work, maybe i did smthing wrong in my code

[cosmic geode]

yeah, actually it isn't sorted... that's why I'm thinking I should've probably done the whole b-tree to solve the first part.
I have an unordered list, in the range described above, and one missing value...
That's a great idea though... It's sort of like taking the sum of values, and finding the difference from the expected value, right?

[timid goblet]

i have this thing xD

[cosmic geode]

What does your dict look like? can you provide a bit more context? What are you trying to achieve?

[vocal gorge]

It's somewhat similar, yeah - I basically notice that when a number gets skipped, the value "element minus its position" gets increased by one compared to all the previous positions in the list

If the list is unordered though, then yeah, you can absolutely use the "calculate the sum and subtract it from the expected one" trick, that's probably the best way

[timid goblet]

my BDD is

[cosmic geode]

map doesn't mutate the dict

you'd want something like newkeys = list(map(int, dict.keys()))

[timid goblet]

or can i define the x axis as a list of strings ?

would it work ?

[cosmic geode]

you don't need to define the x axis at all, as long as your y samples are evenly spaced

you can use strings for labels, sure

iirc you can just plt.plot(y_values)
I'm not entirely sure though

also, nitpicking a bit here, but the idiomatic way to check if x belongs to some set would be with the in keyword
ie. if test['indice'] in (dic1, dic2):

[timid goblet]

in this case, i need to create a new loop to assign each newkey to its value

?

[cosmic geode]

another way to express it, if that makes more sense:
keys = [int(k) for k in ele] (i just remembered that dictionaries iterate over keys by default)
is basically equivalent to keys = list(map(int, ele))

it creates a new list, consisting of every key of the dictionary parsed to an int

[timid goblet]

OH U RE A GENIUS

IT WORKED

THAAANK UUU ❤️

[cosmic geode]

You come from a C-like language, don't you?
for i in range(len(bd)) seems like you're trying to make a traditional for loop
in python that would be for i, test in enumerate(bd):

You're very welcome! ^^
I'm glad I could help !

I'm still just nitpicking btw. Great job!

[timid goblet]

ohh that s true, i m just used to do loops like that in every prog language XD

it s a little bit close to algo, so it has it charm

[unborn cobalt]

Hello i started learning Python some months ago and would like to know some real life examples of class methods in an actual application and how they are used. If someone could send me some code I would be glad.

[cosmic geode]

A common use case is constructors, when you want more variety than you can reasonably generalise in a regular constructor.
something like Color.from_hex("#c0ffee") and Color.from_rgb(255, 0, 127)
this is a sort of trivial example that could easily be parsed via normal arguments. Imagine that you have very different construction patterns that use entirely different logic

[unborn cobalt]

I think we are not talking about the same thing.

class Test:
    somevalue=0
    
    def __init__(self):
        do_stuff=True
    
    @classmethod
    def change_somevalue(cls):
        cls.somevalue+=1

[cosmic geode]

Yup. That's a classmethod alright

[unborn cobalt]

I know that I can keep values across all instances of a class like this but I dont know many use cases why this is usefull

[primal dock]

How did we go from step 2 to step 3, like how can we assume that m is always even?

What I'm thinking is the reason why we get m, is because there's an intermediary step that's not shown where since it's m goes all the way to 0 so like

Let's say y = 5 and we have done step 1
2 * Increment(3) -> 2 * Increment(2 *Increment(2 *Increment(0))) -> 2 * 2 * 2 

[stone lake]

I am not very familiar with python's built in string algos.
I want lex_line to be a generator which takes a string and returns a sequence of
(col, word)
Where word is a substring with no space characters and col is the starting index of that substring.
I have this, is there a way to make it more succulent? I am aware of str.find but as far as I am aware that doesn't take a predicate.

def lex_word(line, col):
    while col < len(line) and line[col].isspace():
        col += 1;
    col_end = col;
    while col_end < len(line) and not line[col_end].isspace():
        col_end += 1;
    return (col, col_end);

def lex_line(line):
    col = 0;
    while col < len(line):
        (col, col_end) = lex_word(line, col);
        if col == col_end:
            break;
        yield (col, line[col:col_end]);
        col = col_end;

[split star]

do you mean dividing space-separated words?

[stone lake]

Yes, but I also want the string index of the substrings

[split star]

if so hello world'.split() would do that

and to get the string index

you can just enumerate

so enumerate(string.split()) would get you the generator/iterator

[stone lake]

Enumerate? That gives 0, 1, 2, 3... etc not the index of the original string

[split star]

oh do you mean the character index itself?

[stone lake]

Yes

[split star]

ohhh gotchu

[vocal gorge]

the way you did it is pretty good, I'd say

[split star]

lex_word looks alright to me minus some edge cases (e.g. end of file before start of token when the file ends with whitespace)

nvm that's handled in lex_line

since you're trying to write a lexer it might match academic writings more if you created an iterator over the line

since iirc old-school lexing tokenizes from an input stream

[stone lake]

I check if the start col equals the end col then end the generator, that shouldn't be an issue

[stone lake]

What do you mean, am I not making an iter over the line?

I made it better with some predicatory logic, but that's probably as good as it can get.

def find_col(line, col, predicate):
    while col < len(line) and not predicate(line[col]):
        col += 1;
    return col

def lex_line(line):
    col = 0;
    while col < len(line):
        col = find_col(line, col, lambda c: not c.isspace());
        col_end = find_col(line, col, lambda c: c.isspace());
        if col == col_end:
            break;
        yield (col, line[col:col_end]);
        col = col_end;

[split star]

oh no i htink your code is fine

as is

i guess if you're learning how to make a lexer from a textbook

[stone lake]

It really surprises me that python doesn't have a predicatory find built in

[split star]

doing line_iter = iter(line) will let you do it char-by-char

that way you don't need the indexes to find the substring

[stone lake]

I am pretty experienced in tokenisation, I've written a few lexers

[split star]

ok sweet

i wasn't sure if you were adapting a textbook or not

[stone lake]

I don't really see using char enumeration as being a good way to lex imo, it can get the job done I guess but wouldn't be a go to

[vocal gorge]

yeah, the iterators in Python are a bit lacking and annoying to use. There is itertools.dropwhile, though, which can be used for it

[stone lake]

Hmm, I guess I could then take the difference of the lengthes to get the cols

Oh wait no, I see, use enumerate(line) then it will have the cols already

And then dropwhile will have the col at index 0

[split star]

wait doesn't dropwhile stop

once you reach a point that it doesn't match

[stone lake]

Yeah, so I'll loop till I get a len of 0

[split star]

can't you just filter instead to actually go all the way thru?

oh nvm

dropwhile is pretty dope for that

[stone lake]

No, I want dropwhile so I can consume just the word each iteration

Oh, I can't take the len of the enumerate

[split star]

!e print(len(list(enumerate([]))))

[stone lake]

Ah, right

[halcyon plank]

@split star :white_check_mark: Your eval job has completed with return code 0.

0

[split star]

could you also just take len(line) beforehand?

[stone lake]

Wait, no I can just use drop while on the lists, and then use the lengths to compute the col. It would be faster then using dropwhile on an enumerate because then I don't have to collect.

Wait, no, the enumerate would have the col in it, ok I am not thinking clearly

[split star]

yeah lol i was curious what u needed the length for

i figured you might need the length of the entire line for some reason

[stone lake]

Wait no, I can't use an enumerate because then I can't advance it more than once per iteration, fuck this is confusing

[split star]

you can do list(enumerate([])) to get the list

[stone lake]

Yeah, but I don't want to have to continuously collect the iter

[split star]

!e print(list(enumerate(reversed(range(16)))))

[halcyon plank]

@split star :white_check_mark: Your eval job has completed with return code 0.

[(0, 15), (1, 14), (2, 13), (3, 12), (4, 11), (5, 10), (6, 9), (7, 8), (8, 7), (9, 6), (10, 5), (11, 4), (12, 3), (13, 2), (14, 1), (15, 0)]

[stone lake]

There is just no way to know if the iter has ended with out consuming it

Which is a problem

[split star]

you can add a sentinel value as a default if it has ended, is that what you mean?

!e

i = iter([])
print(next(i, 'hello world'))

[halcyon plank]

@split star :white_check_mark: Your eval job has completed with return code 0.

hello world

[stone lake]

Well, if I do next on the iter it might not return the sentinel, is there a way I can put it back in to the iter?

[split star]

no, but is there any harm in consuming extra whitespace?

assuming you are dropping while string.isspace()

[stone lake]

Ah, there is peekable

I'll just use peekable

[vocal gorge]

yeah, itertools.peekable is the way

(that's how one does lexers in general, isn't it - with peekable iterators? my lexer experience is, like, having read most of Building Interpreters)

(at least ones which don't have too much lookahead)

[split star]

yeah i think the classic simple one taught in school just uses 1 char lookahead and stores it in a single char variable

[ivory lintel]

can i ask java questions here or nah?

[stone lake]

Yeah, if you just have the line it would be like peek(Infinity) and with C's ungetc you would have peek(1)

Peekable seems to actually be non standard, but you can do itertools.chain([peek], iter)

import itertools

def lex_line(line_str):
    line = enumerate(line_str);
    peek = next(line, None);
    while peek is not None:
        line = itertools.chain([peek], line);
        
        #get start of word
        line = itertools.dropwhile(lambda c: c[1].isspace(), line);
        peek = next(line, None);
        if peek is None: break;
        col = peek[0];

        #get word
        line = itertools.dropwhile(lambda c: not c[1].isspace(), line);
        peek = next(line, None);
        col_end = len(line_str) if peek is None else peek[0];
        yield (col, line_str[col:col_end]);

        peek = next(line, None);

[nimble dew]

Hi all! Do you have any good links about nested dictionarys? There babys are definately not my favourite, and have to do some tasks with those..

[stone lake]

Like how to copy them? Or?

[vapid dirge]

i can't get myself around recursion, can't break down problems into smaller pieces. Most of the online explanations are breaking down factorial but problems on leetcode seem much harder

Any tutorial suggestions?

[stone lake]

I would probably recommend doing stuff with lists, so instead of iterating through them with a for loop recurse through them. Array manipulation is definitely what opened my mind to the concept of recursion.

[stone lake]

For example, instead of reversing a list by using a decrementing for loop try reversing a list recursively.

Getting a sense of recursion linearly can help understand it before using recursion on recursive structures.

[vapid dirge]

thanks

[shut breach]

say you have

d = {
  "A": {
    "thing1": 8,
    "thing2": 7
  },
  "B": {
    "thing1": 5,
    "thing2": 6
  }
}
```really the only concept you have to remember is that `d["A"]` *is itself* a dictionary
that's why you can do `d["A"]["thing2"]`, the first part is a dict so you can access it with a key `["thing2"]` just like any other dict

[chrome raven]

Hello

Any kind soul can help with shortest path algo

[quiet jay]

#help-coconut could someone who knows postfix come help plz

[quiet jay]

what one

[chrome raven]

@quiet jay any

[quiet jay]

djikistras or

[chrome raven]

I m doing a hackerrank qns

And facing some issue

Can u help

[quiet jay]

is it in the format of nodes?

[chrome raven]

@quiet jay yeap

I do have a working code

[quiet jay]

https://www.youtube.com/watch?v=_lHSawdgXpI

[chrome raven]

But due to various circumstance it doesnt work

@quiet jay I know what is it but I cant implement it

Xan u help

[quiet jay]

you don't need to ping me everytime btw

I haven't done it myself

[chrome raven]

Oh

U want try

[quiet jay]

sure

[chrome raven]

I will start a help room

[quiet jay]

a what now

[shut breach]

check the pins

in discord we can pin certain messages in a channel to use as reference

you can see them by clicking the pin icon in the top right

[primal mirage]

Does anyone have a good implementation of the pubsub pattern for multiprocessing. I want to emulate something like kaftka but in pure python to make data processing more modular.

I have this so far...

class PubSub:
    def __init__(self):
        self.topics = defaultdict(mp.Queue)
        self.subscribers = defaultdict(set)
        self.pool = mp.Pool(4)

    def subscribe(self, topic: str, consumer):
        if not callable(consumer):
            raise ValueError("callback must be callable")
        if topic is None or topic == "":
            raise ValueError("Event cant be empty")
        self.subscribers[topic].add(consumer)
    
    def publish(self, topic: str, msg):
        self.topics[topic].put(msg)
    
    def start(self, topic: str):
        tasks = []
        for topic, consumers in self.subscribers.items():
            for consumer in consumers:
                tasks.append(self.pool.apply_async(consumer,(self.topics[topic])))
        [x.get() for x in tasks]

[hard bison]

hey all, I'm doing some leetcoding and I've come across some code accessing a list of integers nums = [2, 3, -2, 4] using nums[~i], I've done a bit of research and it looks like the ~ operator is the bit negation, and it could be used to access a reversed list, such that assert [nums[~i] for i in range(4)] == nums[::-1]. But I'd like to understand the time complexity better, I believe that list(reversed(nums)) takes O(n) because it has to actually flip the list, but is the same true for nums[~i]? is a reversed list being generated underneath and then accessed or is it the case that it's just being read backwards thus resulting in O(1) access?

[agile sundial]

it's not that nums[~i] is magically reversing the list

you're just accessing the indices in reverse order because of how ~ works

[hard bison]

ok, so any reading with nums[~i] should be O(1) right?

[agile sundial]

yep

[hard bison]

cool, thanks!

[agile sundial]

but it's still O(n) overall to reverse

all list accesses are O(1)

[hard bison]

right, so num[~i] is a way to bypass the actual reversing by just reading backwards

[agile sundial]

idk what you mean by bypass here

[hard bison]

take this iteration: ```for i in range(len(nums)):

 suffix = (suffix or 1) * nums[~i]

vs for n in reversed(nums): # do something with n

[agile sundial]

idk what you're doing with suffix there

[hard bison]

suffix doesn't matter... my point is in the first one you just have an index and you use it to read backwards with num[~i

[agile sundial]

wdym by "read backwards"

the only thing you're doing is calculating an index to read from

[hard bison]

in the second one, you actually pay the cost of reversing the list O(n)

[mint jewel]

reversed returns an iterator

so you aren't reversing anything

[hard bison]

😮

[agile sundial]

reversed basically works like what you've written. it just indexes into the sequence

even if it returned a list, it would still be O(n)

[spark pelican]

@hard bison note also you could get the same effect as indexing with ~i somewhat less concisely with:

for i in range(len(nums)-1, -1, -1):
  # do something with nums[i]

Or:

for i in range(len(nums)):
  # do something with nums[-i - 1]

~i is just a hackerish way of doing the -i - 1

(Which maybe you know?)

[hard bison]

is that equivalent to the below? : for i in reversed(my_list):

[hard bison]

I didn't know, first time I come across it which has got me a bit confused...

[spark pelican]

As I understand it, yes, since reversed is returning an iterator which indexes in reverse when the thing to be reversed supports __len__ and __getitem__

It's kind of like how i << 2 is the same as multiplying by 2.

[hard bison]

this doesn't help lol

but the rest does, thank you

I'm also reading this https://stackoverflow.com/questions/56884366/does-looping-through-a-reversedlist-add-to-the-time-complexity-of-my-function

it's much clear now, thanks all

[spark pelican]

Whoops, sorry, i << 1 is multiplying by two. i << 2 is multiplying by four.

Basically, ~ and << are manipulating numbers at the level of their bit-representation. So shifting all the bits to the left is the same as multiplying by two just like if you took a decimal number and shifted everything one place to the left and filled in a zero it would be the same as multiplying by ten.

[hard bison]

I see what you meant by 'hackerish' now, that kind of code is not readable at all...

would you happen to have any blog post for dummies to work through some "bit basics" in python?

[spark pelican]

I don't. But if you really want to dig into this kind of thing the book Hacker's Delight is supposed to be quite a good collection of the lore. https://en.wikipedia.org/wiki/Hacker's_Delight

[hard bison]

cool, ty

[idle pier]

Hello folks, has anyone done 11. Container With Most Water on Leetcode?

[fiery cosmos]

A queue consisting of n elements is implemented using a 1D array with the position of the head fixed. What is the time complexity (Big-O) of removing the second element from the queue (dequeue) while preserving the order of the remaining elements? would someone kindly explain how and why the bigo notation to this question is O(n^2)? if someone tag me that would be wonderful!

[quiet jay]

can someone show me a good resource on A*

I understand djikstras

[burnt current]

Hey, Can anyone share data structure algorithms tutorial links?

[jolly mortar]

see channel pins

[keen hearth]

This site is pretty good: https://www.redblobgames.com/pathfinding/a-star/introduction.html

[agile sundial]

I don't see how that's n^2

[fiery cosmos]

neither do i lol?

[fiery cosmos]

hence why i am asking for help

[agile sundial]

it's not n^2

[fiery cosmos]

what is it then

[agile sundial]

n

[hard bison]

I'm doing leetcode 104 (max depth of binary tree), and they give you a TreeNode class and an input: root = [3, 9, 20, null, null, 15, 7] . I can solve the problem using recursive DFS on their platform, but how could I run it on my own machine? I'm struggling to convert from the root list to an actual tree using the TreeNode class. This is the class: ```# Definition for a binary tree node.

class TreeNode:

def init(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right ```

DFS solution: ```class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

[vocal gorge]

I'd try something like:

• Notice the nodes in the root list go in layers - root, its two children, 4 children of these, 8 children of these...
• For a specific layer, we know which node of the previous layer each element refers to
• So arrange the nodes in a list of layers first. As in:

1. Read the first node value from the list. It goes, alone, into layers[0] - layers[0] = [TreeNode(root[0]))
2. Read the next 2 nodes, put them in layers[1], and update layers[0][0] to point to them (taking into account that they might be None, in which case they shouldn't be created, but Nones should be added to the list anyway to preserve position
3. For the next layers, do the same - each pair of elements are children of a node of the previous layer.
   So, something like:

from math import log2, ceil
def tree_from_lst(lst) -> TreeNode:
    # by this model, the length of list should always be 2**depth-1
    if len(lst)==0: return None
    depth = ceil(log2(len(lst)+1))
    assert 2**depth == len(lst), f"The list has an invalid length {len(lst)}"

    layers = [[TreeNode(lst[0])]]
    i = 1 # next node to read
    layer_ind = 1 # next layer to fill
    while i<len(lst):
        layer = []
        for c in range(2**layer_ind):
            val = lst[i]
            if val is None:
                layer.append(val)
            else:
                node = TreeNode(val)
                layer.append(node)
                side = "left" if c%2==0 else "right"
                setattr(layers[layer_ind-1][c//2], side, node)
            i+=1
        layer_ind+=1
    return layers[0][0]

this seems to produce the right result on this case at least:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right 
    def tree(self):
        return f"Node({self.val=},"+\
        f" left={self.left.tree() if self.left else None},"+\
        f" right={self.right.tree() if self.right else None})"
def tree_from_lst(lst) -> TreeNode:
    #...

>>> root = tree_from_lst([3, 9, 20, None, None, 15, 7])
>>> root.tree()
'Node(self.val=3, left=Node(self.val=9, left=None, right=None), right=Node(self.val=20, left=Node(self.val=15, left=None, right=None), right=Node(self.val=7, left=None, right=None)))'

[hard bison]

@vocal gorge wow, that looks amazing! I like your logic to unpack the nodes by layers. I'll take some time to work through your implementation line by line to really get it. I'll keep you posted. Thank you so much

[restive python]

i need an ordered set

python sets are unordered by default is there a way to set it as ordered ?

[vocal gorge]

you could use a dict instead

[vocal gorge]

It can be simplified, probably, since for one the layers I don't really use - only the last layer and the current one, and also I store Nones where there aren't nodes just to pad the space.

[restive python]

that sounds expensive since it will have a key and value

[vocal gorge]

Yeah, it'd double the overhead from one reference per item to two, but do you really have many enough items to worry?

iirc there's also a pypi library providing an ordered set

!pypi orderedset

[halcyon plank]

orderedset v2.0.3

An Ordered Set implementation in Cython.

[vocal gorge]

this one, say

[restive python]

oh yes , there are many

[restive python]

wow looks great , negative being its five times slower

[vocal gorge]

It looks like even for small objects like ints, the difference is tiny enough to be hard to even distinguish:

>>> %memit set(range(10**6))
peak memory: 141.97 MiB, increment: 61.82 MiB
>>> %memit dict.fromkeys(range(10**6))
peak memory: 151.54 MiB, increment: 70.02 MiB

>>> %memit set(range(10**6))
peak memory: 149.51 MiB, increment: 66.91 MiB
>>> %memit dict.fromkeys(range(10**6))
peak memory: 148.83 MiB, increment: 66.22 MiB

[restive python]

and 3x1(tuple) floats ?

[vocal gorge]

looks like for a set, it's 64+-3 MB for 1 million, whereas for a dict, it's 68+-2 MB for 1 million. The difference is within the error, so it's not even noticable

this is mostly the size of the 1 million ints themselves, of course

[vocal gorge]

these are bigger, so the overhead would be even less noticable compared to the size of the elements themselves

[restive python]

so what your saying is that dict and this ordered set libarary would produce roughly the same overhead

[vocal gorge]

so basically, you don't really need to worry about the memory overhead

[vocal gorge]

This is normal set, not ordered

[restive python]

ohh

[vocal gorge]

I'm saying that there isn't really a reason not to use a dict

[restive python]

how bout speed?
Ordered set is five times slower than ordinary set as they claim, what about dict

[vocal gorge]

%timeit set(range(10**6))
%timeit dict.fromkeys(range(10**6))
70.2 ms ± 2.16 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
105 ms ± 2.39 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

dicts are 1.5x slower, which should make them 3+ times faster than orderedsets

[restive python]

sweet

items = dict() vs. items={}
Any pros cons ?

and the way to simulate a set with dict would be to name the keys as the values , right ?

[vocal gorge]

no real difference, though the latter should be very slightly faster

[vocal gorge]

just use something like None - that's what fromkeys does

[restive python]

i did
my_dictionary.update({ (x,y,z) : (x,y,z)})
It works , but its fine to do apart from it looking mental ?

[vocal gorge]

why not just my_dictionary[(x,y,z)] =, say, None?

[restive python]

no idea whats happening is this mentioned in the docs or w3?

since i have manyyy x,y,z

[vocal gorge]

This is the normal way to alter dicts - you just assign to them using the same syntax as list element assignment

[restive python]

looks like this just keeps the one xyz

[brisk hemlock]

table = ["book1" , 1), ("book2 " , 2), ("book3" , 3)]```

how do i loop through that to get the second element of each segment

[agile sundial]

just loop over the list and index into the second element when you need it, or unpack it like

for _, number in table:
  ...

[brisk hemlock]

what

[agile sundial]

what

[brisk hemlock]

u heard

[agile sundial]

ok

[brisk hemlock]

i keep getting the first element printed

I dont want it!!!

[agile sundial]

can you show your code, also this is more suited for a normal help channel

[brisk hemlock]

this doesnt work fella

[agile sundial]

well yeah

[brisk hemlock]

i dont know how to tell the first element to fuck off

[agile sundial]

you don't need 2 loops

[brisk hemlock]

you cant put 0

ye ik

but im just testing random stuff

i dont know what to do

[agile sundial]

why do you have 2 loops then

[brisk hemlock]

im testing

random stuff

i dont know how to get it to work

i was trying soloutions from the internet

and they had 2 loops

[agile sundial]

!e

table = [("book1" , 1), ("book2 " , 2), ("book3" , 3)]

for tup in table:
  print(tup[1])

# or

for _, number in table:
  print(number)

[halcyon plank]

@agile sundial :white_check_mark: Your eval job has completed with return code 0.

001 | 1
002 | 2
003 | 3
004 | 1
005 | 2
006 | 3

[brisk hemlock]

wait

[brisk hemlock]

nice one, u are a genius

can you go over the syntax for the second one

ive never seen that syntax

second option

[agile sundial]

it's unpacking, since i know the tuples have 2 elements, i can break them down into separate variables

[brisk hemlock]

thats weird looking

hold on

ok i kinda see it

its weird tho

[agile sundial]

!e

some_tuple = (1, 5, 3)

a, b, c = some_tuple

print(a)
print(b)
print(c)

[halcyon plank]

@agile sundial :white_check_mark: Your eval job has completed with return code 0.

001 | 1
002 | 5
003 | 3

[brisk hemlock]

wait wtf

python splits it up?!?!?

this language is crazy

[agile sundial]

it's very useful

[brisk hemlock]

for _, number in table:
  print(number)```

[agile sundial]

yeah, in this case the _ is just a variable name that means "i don't care about this variable"

[brisk hemlock]

so this splits it up _ = to each segment [a, b] but how does the "number" know to output the second index

[agile sundial]

so in this example, you see the a gets paired with the first value, the b with the second, and so on

[brisk hemlock]

ahh ok i see now

number is pairing with the second index

[brisk hemlock]

number being the variable here

makes sense fella

[brisk hemlock]

hey hey hey

i got a quick question about this

how can i make this allow me to edit the list

[agile sundial]

you can't

[brisk hemlock]

rip

[agile sundial]

you need to iterate using range(len

that's the only way to modify the values

[brisk hemlock]

no problem fella ive got it fixed :)))

btw in python how do you change a element?

can i do it using = or .append() or some other function???

[agile sundial]

change an element if you know the index?

[brisk hemlock]

yessir

OII

i fixed it

lets go

[royal light]

Hey guys. I’m super confused on this problem I have. So I have to solve tower of Hanoi recursively but for each move, it needs to use the middle peg

And I understand how to do it regularly but only using the middle peg confuses me

[cerulean river]

Can someone please explain to me why this is not working for this problem? https://leetcode.com/problems/remove-nth-node-from-end-of-list/solution/

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        counter = 0
        trav = head
        
        while trav:
            counter += 1
            trav = trav.next
        # print(counter)
        trav = head
        
        while counter != n:
            trav = trav.next
            counter -= 1
            
            if counter == n - 1:
                temp = trav.next
                trav.next = trav.next.next
                temp.next = None
                del temp
                return head        
            
        print(trav)
        return head

Your input
[1,2,3,4,5]
2

stdout
ListNode{val: 4, next: ListNode{val: 5, next: None}}

Output
[1,2,3,4,5]

Expected
[1,2,3,5]

[chrome raven]

Hello

I an trying a hackerrank qns and need help with a pathfinding algo. I have a solution but one test case is not passing, can anyone help take a look?

[cloud perch]

print("hello world")

[fiery cosmos]

So this is a problem involving priority queues where you are supposed to calculate overwork tiredness? basically you accept the work load as a list and enter remaining work time as N and calculate the rest of the work amount by doing ^2 but I am unsure where the [2, 2, 2] and 4 is from. I understand the 12 in the left example

But does anyone know the logic in which [2, 2, 2] and 4 are from?

import heapq

def solution(n, works):
    for i in range(len(works)):
        works[i] *= -1
    heapq.heapify(works)

    for i in range(0, n):
        m = heapq.heappop(works)
        if m >= 0:
            heapq.heappush(works, m)
            break
        m += 1
        heapq.heappush(works, m)

    answer = 0
    while len(works) > 0:
        m = heapq.heappop(works)
        answer += pow(m * -1, 2)
    return answer

print(solution(4, [3, 3, 4]))

this is an example code, not the exact answer but something i found related to it

[chrome raven]

@fiery cosmos Hello

I m working on a graph qns not sure if u can help

[fiery cosmos]

I'm looking for help too bro

:(

[daring talon]

hello, I'm having trouble trying to code algorithm in python, any help would be great 🙂
I can't manage how to output such as if my tree is [1,2,3,4,5], and then input any number such as 3 in inorderNext(3) method, my output should be [4,5] excluding the first 3 nodes. Anyone can help?

[desert shadow]

Hi guys. For a directed cyclic graph with weights, how do I get its absolute min weight? The problem is that I need to get all paths that have the same min weight. Please let me know if there is any algo you might know that solves my problem. Thanks in advance.

[thin otter]

What do I need to know in order to write an atmospheric fluid simulation for a game? I would need to be able to operate on a very large scale (planet sized), so I would need to be able to section off and perform lower detail simulation.

[misty wagon]

@thin otter That's a navier stokes equation set type of problem

that's a fucking hard one

@thin otter https://www.google.com/search?q=navier+stokes+atmosphere+simulation+python&oq=navier+stokes+atmosphere+simulation&aqs=chrome.1.69i57j33i22i29i30l2.9329j0j7&sourceid=chrome&ie=UTF-8

I vote PyCLES

[thin otter]

You're telling me 😂
Thanks for the info!

[misty wagon]

maybe we can trade tips

[thin otter]

what are you looking for?

[misty wagon]

any advice on how to create a left tailed normal distribution formula? I need to be able to set the min max mean and stddev and then pull random values out of it

all of the libraries Ive found only allow a regular normal distribution

[thin otter]

I honestly do not know what left tailed means

I have very little distribution experience

[misty wagon]

it's a statistics thing

[thin otter]

yeah statistics is something I have done very little of since high school math

[misty wagon]

you are going to find navier stokes to be... challenging

numberphile and computerphile I believe both have videos on the subject

[thin otter]

thank you

I had seen a different model of computation, but I wasn't too sure how it would scale into 3d

This will be difficult...

[vocal gorge]

"left-tailed normal distribution" isn't some well-defined term, right (I can't seem to google it)? If you want a distribution that's similar to a normal one but has a heavy left tail, you could, hmm,

1. take a heavy-right-tailed one like lognormal and flip it horizontally
2. One of the betas, like Beta(5,2)

option 2:

actually, hmm, beta(5,2) doesn't have a heavy left tail, it doesn't have a long tail at all, it's limited to 0<x<1

[vocal gorge]

I need to be able to set the min max mean and stddev
actually, if these are your only requirements, why not, say, take a normal distribution with the mean and stddev, and reroll until you get a result within the [min,max]?

[fiery cosmos]

hello i am looking for some feedback for the following question please what is the worse case time complexity (Big-O) of inserting an item into a stack (Note: assume there is space to insert the item) the answer is O(1) but i would like to just confirm as to why? to further add to this i believe why this is the answer is because O(1) is constant and will never change therefore meaning that the efficiency of this will never improve? 👀 (if someone could @ me that would be great!)

[vocal gorge]

If there's space to insert the item, then, well, you just write the item into the first empty slot and that's it. Nothing that is related to the length of the stack here, hence O(1).

(if there wasn't space, then you would need to resize the stack and that'd be O(n))

[fiery cosmos]

ahh right okay i guess this comes back to sorted and unsorted data because this is sorted we do not need to move anything to get our data into the stack if we did it would then be O(n)

thanks!!

[misty wagon]

@vocal gorge dude, exactly how are you doing that

damn he went to bed

[vocal gorge]

the what?

[misty wagon]

that chart

can i pull random values from that at those probabilities?

i can hop into voice if thats easier?

[vocal gorge]

that's wolfram alpha plotting beta 5 2 for me

[vocal gorge]

sure, scipy probably has beta distributions

[misty wagon]

ok so i found some stuff

[raven kraken]

Can someone tell me what I am doing wrong in this question?

[misty wagon]

its as easy as

[raven kraken]

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        
        i = 0
        
        
        ans = []
        while i < len(nums):
            heapq.heapify(nums)
            ele = heapq.heappop(nums)
            if ele not in ans:
                
                ans.append(ele)
                
            i += 1
            
            if len(ans) == k:
                break
            
        return ans

[misty wagon]

from scipy.stats import skewnorm
a = -5
skewnorm.rvs(a)

any idea on how I can get the theoretical min and max of rvs() ?

[vocal gorge]

that'd be minus and plus infinity, I'd guess, like the normal distribution.

[misty wagon]

well ok

[plush owl]

Where are you calculating the frequency?

[raven kraken]

I don't have to

everytime I am poping an element I will check whether it exists in the answer array or not if it exists then I will increment i and if doesn't then will append

My idea is that I will traverse the entire array and pop the minimum value from the array and I will only append it to the answer array if it doesn't already exists inside the array and as soon as length of my answer array reaches k I will break out of the loop

@plush owl

[plush owl]

that doesn't give you the k most frequent elements.

it gives k smallest distinct elements

[quiet jay]

#☕help-coffee

[raven kraken]

Ohh yes yes you are right

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        
        C1 = Counter(nums)
        ans = []
        for key,val in C1.most_common(k):
            
            ans.append(key)
            
        return ans

@plush owl Here I solved it

[novel gorge]

whats the time complexity of this? id guess its O(n log n)

while True:
        if temp_n in temp_w: 
            res.append(temp_n)
            return (True, res)
        
        elif temp_n == 0: 
            return (True, res)
        
        elif temp_n < temp_w[0]: 
            return(False,res)
            
        elif temp_n > temp_w[-1]:
            temp_weight = temp_w[-1]
            res.append(temp_weight)
            del temp_w[-1]
            temp_n -= temp_weight
            
        elif temp_n > temp_w[0] and temp_n < temp_w[-1]: 
            for i,weight in enumerate(temp_w):
                if weight > temp_n:
                    temp = temp_w[i - 1]
                    res.append(temp)
                    del temp_w[i - 1]
                    temp_n -= temp
                    break

[mint oak]

I have a string for a file location, and when I do print(str) it may return C:\Path\To\File

if I just type in the string name, like str, then it will return C:\Path\To\File

Any idea why this is the case?

[shut breach]

that doesn't fit the topic of this channel, try #❓｜how-to-get-help

[thin garnet]

What is a good resource to learn DS and algorithms for free?

[agile sundial]

there are good ones in the pins

[thin garnet]

Thank you

[novel gorge]

If you like listening to some indian guy explaining what a stack is, you might as well enjoy this one: https://www.youtube.com/watch?v=pkYVOmU3MgA
Besides the indian guy (which i personally hate listening to) its a very informative tutorial. If you would really like to dive deeper into the whole algorithms and datastructures thing there are some very good udemy courses out there: https://www.udemy.com/course/data-structures-and-algorithms-bootcamp-in-python/
Sometimes they cost 120$ and sometimes just 10$

[fiery cosmos]

Best course to learn Data Structures and Algorithms? And is it best to Learn Python at a basic level prior to starting the course?

[shut breach]

check the pins for resources

do you already know a programming language other than python?

[dense ibex]

if you have basic knowledge of any programming language i think you could consider yourself ready, if not, maybe a little bit of python practice could really help you out before going into it :>

[agile sundial]

dsa aren't a beginner topic though, although the only real way to know if you know enough is to try

[fiery cosmos]

No just a little bit of python at the moment

[shut breach]

yeah you should get a handle on the basics first

otherwise you won't be able to implement any examples, but more importantly you need to start to get used to algorithmic thinking

[fiery cosmos]

Ahh okay will do a refresher and will jump on DSA after

[mint oak]

sorry, i didn't realize what topic chat I was in. I don't use Discord a lot and forgot to check. thx

[quiet jay]

can someone help plz?

its a practise exam

I tried (1/10)^5

[glossy breach]

It's rather (1/10)^4 I think

[quiet jay]

I have tried both

[fervent saddle]

Did you write ^ or **

^ is bitwise XOR

** is exponentiation

[agile sundial]

it says to actually calculate it and write the fraction or decimal

not an expression with ^ or **

@quiet jay

[quiet jay]

ah

that was the problem

thanks

[acoustic yarrow]

GeekforGeeks?

[agile sundial]

that's leetcode

[acoustic yarrow]

Ooh I see

[raven kraken]

Just search Kunal Kushwaha on youtube . It is the best DSA course available

[dry beacon]

how to use list properly

[restive python]

Need a double nested dict

main_dict = {}
sub_dict = { "A": 0 , "B": 0}

main_dict[0][sub_dict]["A"] = 15
main_dict[1][sub_dict]["A"] = 125

How can I do this ?

[agile sundial]

do you have any specific questions

[agile sundial]

can you explain what final structure you want

[restive python]

sorted it out thanks

[dry beacon]

Yes, i wonder how to make a code that give output like this with list

here, what i ve tried py cvdt10 = [[USA ,+80425 , +2005], [Russia , +34073 , +1028], [Ukraine, +18912 , +495], [Mexico , +4220 , +446], [Romania, +17158 , +414]] t_ncase = 0 t_ndeath = 0 n = len(cvdt10) print("TOP 10 - Update : 21 Oct 2021") print("-"*28) print("No County NCases NDeaths") print("-"*28) for line in cvdt10: line = line.replace('+','') line = line.replace(',','') data = line.split() rank = new_cases = new_deaths = print(cvd10[0][0]) print(cvd10[0][1]) print() print() t_ncase += nwcase t_ndeath += nwdeath anwcase = int(t_ncase/n) anwdeath = int(t_ndeath/n) print("-"*28) print(f"Total \t : {t_ncase:8,d}{t_ndeath:7,d}") print(f"Average \t : {t_ncase:8,d}{t_ndeath:7,d}") print("-"*28)

[agile sundial]

you probably want to be using strings in the list in line one

[dry beacon]

can we modify the string to integer?

[agile sundial]

other than that, this doesn't look to fit #algos-and-data-structs try #❓｜how-to-get-help

[meager slate]

Say I have an array of fixed size which acts as pool to store something and another array of bools with the same size indicating whether each index is in use or not. I need to have 2 functions get_slot and free_slot to manage this pool. When get_slot is called, i need to return a index such that in_use[index] is False (or raise an exception when there is no free slot) and then set the in_use[index] to True, and free_slot is very simple, simply setting in_use[index] = False.

What scheme should I use in get_slot to find a slot as fast as possible? Simply iterating over in_use till a free index is found doesn't seem very efficient. Thanks

[jolly mortar]

why not maintain two lists, one for the free ones and one for the in-use ones

[meager slate]

thats actually a good idea

infact you can maintain only a single list

a single list for free slots, you can pop from it for get_slot and append to it for free_slot and both are sweet sweet O(1)

thanks hsp, very cool 👍

[fiery cosmos]

ob

[restive python]

I need a nested nested dictionary

Is there a pythonian way

[acoustic hatch]

Hi,

I am trying to create a small teleprompter prototype program that is able to return the content from the user’s note every time a user says something, as long as it’s within the pre-made list of strings.

So what the answer should return when calling this function should be:

Enter words you gonna say next: my
‘my’

Enter words you gonna say next: accommodation
‘accommodation’

Enter words you gonna say next: roughly two miles
‘roughly two miles’

Enter words you gonna say next: distance campus stations
‘distance campus stations’

Enter words you gonna say next: foo
‘Sorry, try again’

When the user is trying to type a word that’s not from that pre-made list of strings, the function will keep asking users until they’ve entered the correct input.

However, I am not entirely sure how to come with such an algorithm/solution, I managed to implement it myself but the function didn’t seem to return the output as expected, can someone here suggest a fix?

[loud trail]

!paste @acoustic hatch this might get more visibility in a help channel, see #❓｜how-to-get-help . Note that screenshots are difficult to read. Use a code block; read below for instructions 👇

[halcyon plank]

Pasting large amounts of code

If your code is too long to fit in a codeblock in discord, you can paste your code here:
https://paste.pythondiscord.com/

After pasting your code, save it by clicking the floppy disk icon in the top right, or by typing ctrl + S. After doing that, the URL should change. Copy the URL and post it here so others can see it.

[cosmic temple]

Hi. I am looking for AVL TREE HELP. I am trying to get my Trees to work right and need a little help with algorithm coding it is my first time.

I am having this error. I am looking for a one on one sessions So I can ask questions

[fallen gale]

im coding a python script that will solve for forces acting on an object (2d)... would apply OOP be a good idea as opposed to loops and just if elses?

[agile sundial]

no reason you can't do both

[old rover]

def how_sum(target_sum, nums):
  if target_sum == 0:
    return [ ]
  if target_sum < 0:
    return None
  
  for num in nums:
    remainder = target_sum - num
    remainder_res = how_sum(remainder, nums)
    if remainder_res == None:
      remainder_res = [*remainder_res, num]
      return remainder_res
  return None


print(how_sum(7, [2,3]))

there's something wrong w this

very wrong

[agile sundial]

ok, and

what's it supposed to do, how is it wrong, what have you tried

[old rover]

ok so it's supposed to return a combination of numbers to get any given number equal to zero in a list

like if i did how_sum(7, [3,4]) i would get [4,3]

and the video i was following used javascript and a spread operator

[agile sundial]

wdym "to get any given number equal to zero in a list"

[old rover]

like that

[agile sundial]

i see

why doesn't it work?

actually, i don't see

can you just post the problem statement

[old rover]

oh actually i figured it out

def how_sum(target_sum, nums):
  if target_sum == 0:
    return [ ]
  if target_sum < 0:
    return None
  
  for num in nums:
    remainder = target_sum - num
    remainder_res = how_sum(remainder, nums)
    if remainder_res != None:
      remainder_res = [*remainder_res, num]
      return remainder_res
  return None


print(how_sum(7, [2,3]))

it should be not equal to none

[agile sundial]

what's the problem statement

[agile sundial]

subset sum

[old rover]

is that what it's called

[agile sundial]

yeah

it's a classic

[old rover]

yeppp

classic dp/memoization problem

https://youtu.be/oBt53YbR9Kk

[agile sundial]

but you're not using dp

[old rover]

not yet no

just brute force rn

and i was going to do the memoized solution after

but memoizing it shouldn't be terrible

it seems like the solution is to just dunk in a dictionary

[agile sundial]

pretty much

[old rover]

if only i knew that

4 months ago

😐

[agile sundial]

there's a little bit more work, but yeah

[foggy temple]

@simple mortar why do you sound like the bad guy from portal 2

[quiet jay]

help plz, is prac exam

[lean dome]

What's the worst case for an unbalanced binary search tree?

[quiet jay]

O(n)?

[lean dome]

Well, I more meant - what's the worst case shape that it can take on?

Or to put that a little bit differently: why do unbalanced BSTs have O(n) performance for many operations?

If you can explain why an unbalanced BST might give O(n), you should be able to explain why an unbalanced BST does worse than a sorted list.

(because a sorted list would be able to give better than O(n))

[quiet jay]

the nodes would go all to the left or all to the right

[lean dome]

Right. And if that happens, it's basically a linked list, right? All the nodes are in a straight line.

[quiet jay]

yes

how does this help me answer the question

[lean dome]

Well, why would a sorted linked list be worse than a sorted Python list?

[quiet jay]

hmm

that makes sense

but you need to use binary search on the sorted python list

obviously if you wanted to access a certain index that would be easier with a python sorted list

like the last would be O(n) compared to O(1)

[lean dome]

Right. Linked lists don't have random access for a node in the middle, so you need to start from the beginning and scan forward, one link at a time. With a sorted Python list, you can start in the middle, and jump around to repeatedly bisect the list

[quiet jay]

oh I see

when you actually split the list

whats another case?

need 2 better and 2 worse

[quiet jay]

could the get() method be one and delete() be another?

what would be better on the bst?

[lean dome]

Insert and delete would both be better on the BST, because a list requires moving a bunch of elements when inserting or deleting in the middle.

Search would be better on the list. Insertion at the end would be better for the list. So if the numbers being inserted are always in order, a list wins because it has amortized O(1) appends, while the BST would have O(log n) appends

[quiet jay]

oh true

we haven't really learnt about having to move the elements

is the time complexity of inserting a new item at index 0 O(n)

[lean dome]

amortized basically means "on average" - it's about the performance of an operation when that operation happens an infinite number of times.

[quiet jay]

ah

[lean dome]

The way a list works, when appends happen it may need to resize, and if you append an infinite number of elements, each resize is more expensive than the last - but, because each resize allocates more extra space than the last as well, you wind up in a situation where resizes become increasingly expensive, but increasingly rare

and those two factors balance each other out, and let us treat appends to the end of a list as though they're constant time. In actuality, once in a while you hit a slow one, followed by a bunch of fast ones - but that means that, overall, the cost of appending a new item is independent of the current size of the list.

[quiet jay]

makes sense 👍

what about inserting at the start of the list

[lean dome]

the way a list works, if you insert a new first item, it needs to move all of the other elements back one first, to make room for the new one

that's expensive - a O(N) operation.

[quiet jay]

yea

cool

thanks for explaining all that!

[lean dome]

sure!

[quiet jay]

do you happen to know how dfs, bfs and minimum spanning trees work?

[lean dome]

I remember dfs and bfs off the top of my head, though I don't remember any algorithms for minimum spanning trees

[quiet jay]

ok

whats dfs starting at b

I tried b,c,d,f,b

[lean dome]

b,d,c,e,a I'd say

[quiet jay]

what?

how did you get from b to d

[lean dome]

I missed one, sorry - I meant b,f,d,c,e,a

though I suppose - we can consistently pick the child with the lowest weight to visit first, I guess. If we did that, we'd get: b,c,d,f,e,a

[quiet jay]

how do you do this tho

you are going from f to e but they are not connect

[lean dome]

for a dfs, they don't need to. basically, for a dfs, we start at some node. We visit each of its neighbors, in some order - dfs doesn't require any order, but let's say we visit them in order from the smallest cost to the highest. For each of the neighbors, in that order, we visit it (and all its children, recursively), ignoring any that we've already visited.

[quiet jay]

would b, a, e, c, d, f be a correct answer?

[lean dome]

so:
visit b: b's neighbors will be visited in order c, f, a (that's lowest cost to highest)
visit c (b's lowest cost neighbor) - c's neighbors will be visited in order b, d, e
don't visit b (it's already been visited)
visit d - d's neighbors will be visited in order c, f
don't visit c, it's already been visited
visit f - f's neighbors will be visited in order d, b
don't visit d, it's already been visited.
don't visit b, it's already been visited.
done visiting f
done visiting d
continue visiting c by visiting e - e's neighbors will be visited in the order a, b, c
visit a - a's neighbors will be visited in the order e, b
don't visit e for a - it's already been visited
don't visit b for a - it's already been visited
done visiting a
don't visit b for e - it's already been visited
don't visit c for e - it's already been visited
done visiting e
done visiting c
don't visit f for b - it's already been visited
don't visit a for b - it's already been visited
done visiting b

yes, b,a,e,c,d,f is a possible DFS path.

[quiet jay]

wow