#algos-and-data-structs

1 messages · Page 54 of 1

regal spoke
#

At the point in time when you've added in all edges with weight <= x, you can instantly find the size of the connected component containing v using the DSU

grizzled copper
#

So I don't have to be using an adjacency list here?

#

Just an edge list?

#

And then sort it by weight

regal spoke
#

For 1, you just need two things
a). A list of the edges sorted by weight
b). A DSU (used to keep track of the sizes of the connected components)

#

Do you know what a DSU is?

grizzled copper
#

It keeps track of unconnected elements in a relation

#

but i've never implemented one

regal spoke
grizzled copper
#

What do you mean by size of connected components btw?

#

As in the largest weight of any edge connecting them?

regal spoke
#

No. The size of a connected component is that number of vertices in that component

grizzled copper
#

Ohhh so that would be the max number of nodes reachable

regal spoke
#

yes exactly

regal spoke
# regal spoke For 1, you just need two things a). A list of the edges sorted by weight b). A ...

Btw this is very reminicant of Kruskal's algorithm for computing MST, https://en.wikipedia.org/wiki/Kruskal's_algorithm

Kruskal's algorithm

Kruskal's algorithm finds a minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree. It is a greedy algorithm that in each step adds to the forest the lowest-weight edge that will not form a cycle. The key steps of the algorithm are sorting and the use of a disjoint-set data struc...

haughty mountain
#

what prevents just adding all the edges < w and then just traversing to check reachability? pithink

#

if you want all possible answers then sure, you want the DSU solution

regal spoke
#

I'm describing something that runs instant for each type 1. query

grizzled copper
#

Just what vertices I can reach

regal spoke
grizzled copper
#

Ohh

haughty mountain
grizzled copper
#

Let me check the runtime constraint

#

18 seconds max

haughty mountain
grizzled copper
#

where each file can contain up to 5k queries

haughty mountain
#

the idea of multiple queries seems odd to me given that 3 can just be done in one way

regal spoke
grizzled copper
#

So for the DSU thing, i'd initialize a DSU(num of vertices) and then for every edge, union them?

regal spoke
#

You might want to modify the implementation I sent you if you want to use dictionaries

grizzled copper
haughty mountain
regal spoke
#

ye

grizzled copper
#

So a nested list?

haughty mountain
grizzled copper
#

theres no vertice 0

haughty mountain
grizzled copper
#

maybe use a list but just add a dummy element to make indexing easier

haughty mountain
#

you can just subtract 1

#

and if really needed you can add 1 later if you need the 1 indexed ones for printing results or whatnot

grizzled copper
#

Oh no that's not necessary

regal spoke
#

I personally always keep 0-indexing inside my own code. I handle the conversion between 1-indexing / 0-indexing at parsing/printing.

#

I think that is the most sane solution

#

Instead of adding a dummy 0

grizzled copper
#

That's what I have now

# 

[[0, [(1, 8), (2, 4)]], [1, [(0, 8), (4, 6), (5, 12)]], [2, [(0, 4), (3, 7), (4, 20), (6, 15)]], [3, [(2, 7), (5, 13)]], [4, [(1, 6), (2, 20), (5, 15)]], [5, [(1, 12), (3, 13), (4, 15), (6, 10)]], [6, [(2, 15), (5, 10)]]]
[False, False, False, True, True, False, True]
regal spoke
#

Here is how I would code the input parsing for that problem

n,m = [int(x) for x in input().split()]

has_weapon = [c == 'W' for c in input().split()]

edges = []
for _ in range(m):
    u,v,weight = [int(x) for x in input().split()]
    # Switch to 0-indexing
    u -= 1
    v -= 1
    edges.append((u,v,weight))
# Sort edges by increasing weight
edges.sort(key = lambda e:e[2])

graph = [[] for _ in range(n)]
for u,v,weight in edges:
    graph[u].append((v, weight))
    graph[v].append((u, weight))
grizzled copper
#

Not an adjacency list?

regal spoke
grizzled copper
#

Oh, i was thinking of an equivalence set

#

Something like this?

image.png
regal spoke
#

It is missing size

grizzled copper
#

Oh my bad

regal spoke
#

Btw as an example of how to use the DSU, here is how I would find the MST (using kruskal's algorithm)

def mst(n, edges):
    mst_edges = []
    
    dsu = DisjointSetUnion(n)
    for u,v,weight in edges:
        if dsu.find(u) != dsu.find(v): # u and v are in different components
          dsu.union(u, v) # Connect u and v
          mst_edges.append((u,v,weight))
    
    return mst_edges
grizzled copper
#

Oh, so the third query can also be solved using dsu

regal spoke
#

Probably all of it can be solved using dsu in one way or another

#

However as @haughty mountain using DSU is probably overkill for this problem. I would expect a good DSU solution in Python to take like 0.1s with those constraints

#

Which is a lot faster than the time limit of 18s

grizzled copper
#

so I assume the next step is to find the set which contains the current node i'm in (1, or 0 in this case) and then filter all un-weaponzied elements?

regal spoke
#

Are you talking about 2.?

grizzled copper
#

1

#

So that would be the max amount of weaponized cities able to be reached from vertice (1)?

#

wait, i'm not accounting for weight

regal spoke
#

The weight part comes in from only using edges with weight <= x

grizzled copper
#

so I'd initialize a DSU after running query F

regal spoke
#

F?

grizzled copper
#

1*

regal spoke
#

No

#

If you want to solve 1. using DSU, then do the following

  1. Initialize a DSU object, and set self.size = list(has_weapon)
#

Now dsu.set_size(v) corresoinds to number of weaponized cities in v's connected component

#
  1. Go over the edges (u,v,weight) in order from lowest weight, and join u and v in the DSU
grizzled copper
#

oh, so i need to pass has_weapon as an argument to DSU()

regal spoke
#

Yes

#
  1. At the point in time when you've just added all edges with weight <= x, then you can solve a 1. query by calling dsu.set_size(v)
haughty mountain
#

and if you save the answer after adding each weight, you have effectively computed the answer for all possible w

regal spoke
#

So ye

haughty mountain
grizzled copper
# 

DSU = DisjointSetUnion(n, has_weapon)
answers = [0]*(max(e[2] for e in edges) + 1)

for u,v,weight in edges:
    if DSU.find(u) != DSU.find(v):
        answers[weight] = DSU.set_size(u) + DSU.set_size(v)
        DSU.union(u, v)
#

so i can just compute all answers at once and then check when running the query itself?

haughty mountain
#

basically with slight variations you can either get answers for all nodes for a fix w, or for a fix node get the answer for all w

regal spoke
#

Two things. The weights can be really large (<=10^9), so you cant just index answers[weight] like that. It could also be that some w never appears as a weight, but appears in a type 1. query

#

Also you have a bug in your code

#

You should have something like

# 
DSU = DisjointSetUnion(n, has_weapon)
answers = {}

for u,v,weight in edges:
    if DSU.find(u) != DSU.find(v):
        DSU.union(u, v)
        answers[weight] = DSU.set_size(1)
#

or

# 
DSU = DisjointSetUnion(n, has_weapon)
answers = {}

for u,v,weight in edges:
   DSU.union(u, v)
   answers[weight] = DSU.set_size(1)
grizzled copper
#

{4: False, 6: 0, 7: 0, 8: 0, 10: 0, 12: 1, 13: 1, 15: 1, 20: 1}
so this means that I can reach 1 weaponized city if I have a W of 12 or above?

regal spoke
#

yes

grizzled copper
regal spoke
#

ops I see my error

#

1 should be 0

#

🤦‍♂️

#

at least that is one error

grizzled copper
#

Yeah i changed that too

#

I think it's because i should convert the list of booleans into 1 and 0s?

#

Since size depends on a +=

#

But that should work though

regal spoke
#

True = 1 and False = 0 in Python, so that should be fine...

#

Oh I see the bug

grizzled copper
#

Eh? where

regal spoke
#

has_weapon = [c == 'W' for c in input()] should be has_weapon = [c == 'W' for c in input().split()]

grizzled copper
#

Ohhhh 😭 i see , thanks

#

no idea how it was still making a list with false and true though

regal spoke
#

c == 'W' is false if c is a white space

grizzled copper
#

Ohh that makes sense

#

Btw, this doesn't have much overhead right

#

so I can run it whenever the file is first initialized and then just call answer{} when a query needs it

regal spoke
#

What you probably should do is to convert answers into a list

#

and then binary search over it to solve queries

#

That will make everything take O(log n) per query

grizzled copper
#

Or would there be a bottleneck finding the lower weight bound if the specific w isn't found in the dict

regal spoke
#

Accessing dict is O(1), yes

#

But you cant do binary search over answers if you store it as a dict

#

For example, suppose the answers dict is

{4: 0, 6: 0, 7: 1, 8: 2, 10: 2, 12: 3, 13: 3, 15: 3, 20: 3}
#

and someone asks for query type 1. with weight 11

#

Then you cant simply look up answers[11], because it doesn't exist

#

The answer to the query should be answer[w] for the largest w in answers with w <= 11

#

in other words, w = 10

grizzled copper
regal spoke
#

Think about it like you want to "round down" 11 to the next edge weight (a weight that appears in some edge). Which is the same as the largest edge weight <= 11. This is easiest computed using the bisect module

#

The answer is simply print(answers[round_down(11)])

grizzled copper
ripe prism
#

hello everyone, im studying DSA so i can start leetcoding, im just lost on how to start

grizzled copper
regal spoke
#

bisect_left returns the smallest valid index

grizzled copper
#

Ohh i see

regal spoke
#

bisect_right returns the largest valid index

grizzled copper
# 
memo = {}
    if query[0] == "S":
        city = int(query[1]) - 1
        if has_weapon[city]:
            print(0)
        else:
            if city in memo:  
                print(memo[city])
            else: 
                DSU = weaponizedDSU(n, has_weapon_integer)
                for u, v, weight in edges:
                    DSU.union(u, v)
                    if DSU.set_size(city) >= 1:  # Break out of loop as soon as union found with weaponized city found
                        memo[city] = weight  # Store the result in the memo dictionary
                        print(weight)
                        break

how do i shave .4 seconds off this

regal spoke
#

Don't do the break at the end there

grizzled copper
#

To do more memoization?

regal spoke
#

Compute that memo thing once

grizzled copper
#

can start at any arbitrary vertice

#

so i have to add to memo once everytime i have a different city

regal spoke
#

Oh ehm

#

There is a much better way to do this

grizzled copper
#

Huh

regal spoke
#

In the dsu, start by connecting all 1 vertices

#

Then loop through the edges in increasing order of weight, and join u and v

grizzled copper
#

1 vertices as in union (city 1, x...etc)?

regal spoke
#

1 vertices are all vertices with weaponds

grizzled copper
#

Ohhh

#

So connect them with each other, or just union all of those vertice's edges first

regal spoke
#

Join all weaponized vertices first, before doing anything with edges

grizzled copper
#

find a path between any pair in the set of weaponized vertices?

regal spoke
#

Do a Dsu join/merge /whatever it is called

regal spoke
grizzled copper
# 
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a != b:
            if self.size[a] < self.size[b]:
                a, b = b, a

            self.num_sets -= 1
            self.parent[b] = a
            self.size[a] += self.size[b]
``` this?
regal spoke
#

I think of all weaponized vertices as essentially the same vertex

grizzled copper
#

Oh there isn't any join/merge in dsu you sent

regal spoke
#

Use that function, yes

regal spoke
grizzled copper
#

I see

grizzled copper
# regal spoke People call it by many different names 

    if query[0] == "S":
        weaponized_vertices = [i for i in range(n) if has_weapon[i]]
        DSU = weaponizedDSU(n, has_weapon_integer)
        base = weaponized_vertices[0]
        for vertex in weaponized_vertices[1:]:
            DSU.union(base,vertex)
#

Like that?

regal spoke
#

Yes

#

For each vertex, what you want to know is at which moment does the vertex get joined into the "1 component"

grizzled copper
regal spoke
#

Kinda

grizzled copper
#

im not sure how that works

regal spoke
#

You'll need a slightly different implementation of dsu

# 
class DisjointSetUnion_smalltolarge:
    def __init__(self, n):
        self.parent = list(range(n))
        self.components = [[i] for i in range(n)]

    def find(self, a):
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            self.parent[acopy], acopy = a, self.parent[acopy]
        return a

    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a != b:
            if len(self.components[a]) < len(self.components[b]):
                a, b = b, a

            self.parent[b] = a
            self.components[a] += self.components[b]

    def find_connected_component(self, a):
        return self.components[self.find(a)]
#

find_connected_component(v) returns a list of the vertices in v's component

# 
weaponized_vertices = [i for i in range(n) if has_weapon[i]]
DSU = DisjointSetUnion_smalltolarge(n)
base = weaponized_vertices[0]
memo[base] = 0
for vertex in weaponized_vertices[1:]:
    DSU.union(base,vertex)
    memo[vertex] = 0

for u,v,weight in edges:
    if DSU.find(u) == DSU.find(v):
        continue
    if DSU.find(v) != DSU.find(base):
        u,v = v,u
    if DSU.find(v) == DSU.find(base): # u's component will be merged into the weaponized component 
         for vertex in DSU.find_connected_component(u):
             memo[vertex] = weight
    DSU.union(u, v)
grizzled copper
regal spoke
#

This keeps track of when a components gets merged into the weaponized component

#

And at that time, it stores the answer for all of those vertices that just joined the weaponized component

grizzled copper
regal spoke
#

ops

#

meant base there

#

fixed it

#

All of the already weaponized cities should have ans = 0, right

grizzled copper
#

Mhm

#

since we're already in it

ornate bluff
#

Mb if I ever offended u

Fwapd0waUAATBO0.jpg
covert wind
#

hey if I have a list of list:

[['x1'],['x2'],['x3'],['x4', 'x5'], ['x6'],['x7', 'x8']

How would I check if x1 is also in x2?

urban tundra
#

I was quite confused about python been slow in CP than java and c++.
So, how much exactly is it slow?? is there a very big margin or just slightly.

Also, as I'm more comfortable at Python than Java.. I have switched to doing DSA in python.. ik its all about concepts.. but should I practice in java or python for placements as well as some sort of CP in future.. ??

#

CP means Competitive programming..

#

Or.. I should go with C++??

#

ping me when replying..

next raven
#

has anyone experience with CT Scans -> Organsegementation?

ivory sun
halcyon plankBOT
#
Missing required argument

code

regal spoke
#

That code is just a class defintion, nothing interesting would happen if you run it

regal spoke
#

Under ideal circumstances, PyPy is like 3x slower than C++. But it can easily be a lot slower than that.
There are also other cons of using Python for CP other than it being slow. For example, Python can't really handle recursive solutions.

regal spoke
#

It is the safe bet

outer rain
#

if only there was a programming language built specifically for competitive programming, with good syntax, and performance, and tooling...

#

but I suppose no one is dumb and/or bold enough to dedicate their life appeasing everyone 😩

regal spoke
outer rain
#

I think they failed from step 0 being a JVM language with completely unoptimized native backend

#

don't get me wrong: you can do CP on JVM, but it still puts you behind

regal spoke
#

There is a guy that tried using Kotlin for the ICPC-finals a couple of weeks ago

#

He is normally doing pretty well using Kotlin

#

But from what I heard he really struggled using Kotlin in the finals because of two reasons:

  1. His teammates don't know kotlin. So they couldnt help him debug code / find errors in the code
  2. There was some kind of bug in the judge system with Kotlin. Probably no one else had noticed it because litterarily no one else uses Kotlin.
outer rain
#

yeah, that's understandable

#

I have heard similar stories from the guy who uses D

#

he was discovering interesting bugs in the compiler during some championship..

regal spoke
#

Never heard anyone use D in CP, other in random challenges where you are forced to use unusual programming languages

outer rain
#

I mean, D seems good for CP

#

you get c++ like syntax

#

strong metaprogramming with string mixins

#

good standard library (with built-in fft!)

#

and so on

regal spoke
#

Does it have fast built in IO?

outer rain
#

I think it's the same as C?.. I may be wrong

regal spoke
#

C is smart about its built in IO

#

It notices if stdout is a file or not. It uses a buffer for stdout only if it is a file.

#

In CP that is nice, because that avoids unnecessary flushing of stdout

outer rain
jolly mortar
#

im pretty low rated and ime ive never TLEd a question because of choosing python

#

its only been for having a suboptimal algorithm

outer rain
outer rain
#

like segment trees in python are tough

#

in my expereience, at least

regal spoke
#

Also graph problems

outer rain
#

@regal spoke will tell a lot more 😂

#

yeah, also that: you get no dfs, basically

#

well, not "no" dfs, but, you know, less dfs

#

I think there is another side to performance: knowing "yep, I can probably survive 10^7 binary searches" is just nice... C++ performance is way more predictable that CPython/PyPy to me.

jolly mortar
#

i can believe that

regal spoke
#

Turns out it wasn't impossible

jolly mortar
#

div 1 C sounds way beyond my paygrade 💀

urban tundra
#

@regal spoke understood.
I will switch to C++ very soon.

narrow mica
#

most material on CP also assumes you use C++ and have their code in C++

wispy nacelle
#

guys is neetcode dsa and system design course is best for me

limber relic
#

hello

twin remnant
#

I want to create a simple program that can simulate electrical circuits, though right now I have no clue where to start. I checked some existing projects but those have very large code bases and I wasn't able to understand anything
for starters i want to find a suitable data structure for storing the electrical components and the connections between the components (nodes)

ornate bluff
#

If ur indian do striver

wispy nacelle
ornate bluff
#

Yes u can do neetcode if ur doing it in python

wispy nacelle
ornate bluff
#

It doesn't matter. An indian always looks for pirated options before buying a course and doesn't pay unless he absolutely have to

#

I am an indian as well

wispy nacelle
ornate bluff
ornate bluff
#

Hackerrank python

#

It's very language specific

#

Nd not for dsa

#

But do that first

#

Before moving to doing dsa with python on leetcode

wispy nacelle
ornate bluff
#

If u want to do some more language specific questions u can go to codewars as well

wispy nacelle
#

i say i just finnish my python so i want to solve some questions

ornate bluff
#

Hackerrank python

#

Already told u

wispy nacelle
#

okay

#

what are you doing now in studies

ornate bluff
#

I'm balding

#

nd

#

malding

urban tundra
#

@wispy nacellewhat are you doing in studies??

wispy nacelle
#

currently i am doing nothing

urban tundra
#

In which college / course??

#

or dropper?

wispy nacelle
urban tundra
#

Jee?

#

@wispy nacelle

wispy nacelle
urban tundra
#

%ile??

wispy nacelle
#

85

urban tundra
#

Ohh..

wispy nacelle
#

are you new at python or you know some basics

urban tundra
#

I'm at Intermediate level.. ig

#

theoretically I'm all done..

wispy nacelle
urban tundra
#

koi ni bhai, ho jayega

wispy nacelle
#

just completed learn what matters series in python

urban tundra
#

is this a tutorial series??

#

send link,, if possible..

wispy nacelle
#

yup

#

you can search it on you tube sheryians coding school python learn what matters series

urban tundra
#

Ok dude

#

So you preparing for jee advanced or not??

wispy nacelle
#

@urban tundra

urban tundra
wispy nacelle
urban tundra
#

Ok

#

accepted

keen hatch
#

working on my final and maybe a bit confused about something time complexity related. we're doing a study on an algorithm that iterates over a sorted list, and normally the algorithm is O(n^2). there's an optimization we can apply that ends the algorithm once we iterate to a positive integer from our outer loop. would that mean the time complexity is still O(n^2) but theta(n^2 - nm) where m is the number of positive integers?
or am i misunderstanding theta

gloomy prism
gloomy prism
#

see every function f(n) would always be theta(f(n)),
here confusion is regarding whether we can say if f(n) is theta(n^2) which depends on whether you consider m as a variable or not

strong crypt
#

wsp sussys

keen hatch
lilac cradle
#

how do encodings like utf8 store text? i see it described as ‘variable length’ which indicates to me that not every character has to take up the full 4 bytes (now that i think of it, why is it called utf-8 if it only uses 4 bytes), but then how do you know what bytes represent a full character?

#

like cause you could have 4 bytes be 4 1-bytes chars, 2 2-byte chars, a 3-byte char and a single 1-bit char, etc

outer rain
#

you look at first bits and see how much you need to eat to get a single character

#

it's called utf-8 because it 8 bits per character at least

outer rain
lilac cradle
#

im sure you could do it with less than a byte using bitmasking but you'd barely be able to display any characters

#

if you split it into nibbles that's only 16 options

#

lmao

lilac cradle
hidden glacier
#

Or is there like more parts that I need to cover

frozen elm
#

I haven't seen the tutorial. Why not get a nice book?

#

There are some good resources in the pinned messages.

hidden glacier
frozen elm
#

Ah. the MIT course in the pinned messages is free.

hidden glacier
#

ok

outer rain
#

Huffman (and other compression methods) encodes each character in variable number of bits

outer rain
# lilac cradle how do they deal with ambiguity though? do they just reserve some slots of each ...

Look at the table again. You start with first byte - it's definitely a first byte of some character. You look at it first bits and see how long that character is. Let's say it's 3 bytes. You then read the next 3 bytes, and extract the meaningful bits out of them to get the codepoint. Then you know that fourth byte is a beginning of the next character (because the three bytes before is the first character, and the next one immediately follows), so you check how many bytes does the second character contains. Extract bits, get the codepoint. And then repeat until the whole encoded stream is exhausted

#

In fact, in utf-8 it's even easier. Look at any byte. If it starts with 0 - it's a one byte character. If it starts with 11 - it's a beginning of multibyte character. If it starts with 10 - it's a continuation of another character. You can go to the left and to the right to get the remaining bytes. Or slide forward, until you see the beginning of the next character.

ripe oxide
true shore
burnt kraken
#

hello

#

can anybody recomend me a library to learn?

#

or a project

summer thunder
#

Hey guys, so I havent done DSA in a bit, any good quick resources to refresh my mind

merry kestrel
quaint girder
plush badge
#

does anybody here do t levels course
cus i really need help asap
and the esp is soo close
starts tommorow

twin remnant
#

I want to create a simple program that can simulate electrical circuits
what will be a suitable data structure for storing the electrical components and the connections between the components (nodes)

#

i thought a graph might work but in parallel wire connections more than 2 components will reference one node, in a graph thatll be like one edge connecting to more than 2 vertices

vocal gorge
#

you can use a graph, where both components and wires are vertices

jolly mortar
#

!cban 708387638650077357

halcyon plankBOT
#

:incoming_envelope: :ok_hand: applied ban to @wintry fossil permanently.

agile sundial
#

holy moly

opal oriole
hasty junco
#

does any1 have an intuition for the 3Sum leetcode problem?

shut breach
#

once you've fixed 2/3 of the triplet, you know what the last number must be and only need to find out whether it's in the array
some ways of figuring out whether its in the array are faster than others

rigid furnace
#

(Not sure if this is an appropriate topic...)
How to make an abstract generic class attribute?
The idea is to force the child class to define it while the base generic class handles this attribute to initialise some internal logic.

Something like this (but it doesn't work):

T = TypeVar('T')
class A(Generic[T], ABC):
    @abstractmethod
    some: Iterable[T]
    
    def __init_subclass__(cls) -> None:
        some_logic(cls.some)
class B(A[int]):
    some = [1, 7, 90]
b = B()
jolly mortar
#

https://leetcode.com/problems/path-with-maximum-gold
im interested in the upper bound on the number of paths starting from a given point in this setting
i feel like the worst case is when the 25 gold cells form a 5x5 subgrid and you start from a corner, is that true/can we prove that

#

if thats true then there's this bound

WhatsApp_Image_2024-05-14_at_12.47.10_018e0378.jpg
haughty mountain
jolly mortar
#

m x n grid, 25 of the cells have gold
for what (arrangement, starting point) pair is the number of paths maximized

#

you can only travel from one gold cell to another and you can't revisit a cell

haughty mountain
#

hmm, yeah this is a non-trivial problem

twin remnant
vocal gorge
#

connections between stuff

vocal gorge
# twin remnant what will be the edges?

for example, this circuit can be modeled as just two nodes (one before and one after the resistor), each node representing an entire section of conductor (along with the voltage is fixed). These two nodes are connected with two edges - along one edge the resistance is fixed, along the other the voltage difference is fixed.

image.png
#

this is enough info to solve the circuit.

#

(Have you ever used Spice, by the way? It'd be a major source of inspiration.

twin remnant
twin remnant
shut mauve
#

I want to detect squares on my screen and return a list of coordinates for each square.
I use color pixel detection(RGB) to detect the 2 squares on the images:

def find_pixel_coordinates(target_color, image):
    screenshot_array = np.array(image)
    indices = np.argwhere(np.all(screenshot_array == target_color, axis=-1))
    if len(indices) == 0:
        return []
    coordinates = [(idx[1], idx[0]) for idx in indices] 
    return coordinates

The function returns all green pixels found in the image:

[(317, 127), (318, 127), (319, 127), (320, 127), (307, 128), (308, 128), (309, 128), (310, 128), (311, 128), (312, 128), (313, 128), (314, 128), (298, 129), (299, 129), (300, 129), (301, 129), (302, 129), (303, 129), (304, 129), (305, 129), (292, 130), (293, 130), (294, 130), (295, 130), (321, 130), (292, 131), (321, 131), (293, 133), (322, 133), (293, 134), (322, 134), (294, 136), (323, 136),  (362, 263), (331, 264), (331, 265), (363, 265), (363, 266), (332, 267), (332, 268), (364, 268), (332, 269), (363, 269), (364, 269), (358, 270), (359, 270), (360, 270), (333, 271), (353, 271), (354, 271), (355, 271), (333, 272), (348, 272), (349, 272), (350, 272), (343, 273), (344, 273), (345, 273), (334, 274), (338, 274), (339, 274), (340, 274), (334, 275), (335, 275)...]

How do I detect which x,y coordinates belong to which square?

image.png
vocal gorge
#

This example isn't very useful I think since it's very idealized (you could solve this one by just e.g. floodfilling the image and excluding the outer region). For a solution that'd work in a real environment (where you have tons of stuff on the screen, including many green pixels and even closed regions that aren't squares and shouldn't be detected), try something like cv2's contour detection.

shut mauve
#

The only green pixels on screen are those of the squares. Since there is always a white distance between the square, then why can't I just look at the absolute differences? And determine when a new square begins?

#

I wanted to show the entire output but it's too long

vocal gorge
#

The only green pixels on screen are those of the squares
If you can rely on that, then I'd do mask = screenshot_array == target_color and then apply cv2's connectedComponents. For this image, there's three connected components - the internals of the two squares, and the external one. The external one can be determined by e.g. looking at what component some boundary pixel belongs to. All other components are the internals of squares, which is what you're looking for.

shut mauve
#

Thanks will try 🙂

haughty mountain
vocal gorge
#

I don't see how that'd help

haughty mountain
#

that finds the squares separately

vocal gorge
#

but... how'd you direct the floodfill inwards and not outwards?

wild perch
#

Hey guys I am new to this server and I came here to ask help on the flowchart I created and i wanted to see where I can improve on it as most of it is all input/output

#

This is my flowchart

#

I need feedback to see what i should improve and how I should structure it

haughty mountain
#

I assumed the outline

vocal gorge
#

ah, makes sense. I think that person wants to detect the rect (location, width, height) knowing the outline.

strong crypt
#

My birthdays trmw btw, looked up some object and getter/setter stuff

rigid trench
#

If you know you're looking for exactly that shape, you actually only need to look for the four corners

#

Which can be defined by a 3x3 mask

#

Very simply, you can slide the mask over every pixel and wait for the match. That gives you the corner

wild perch
#

I can make it shorter

#

But when the program will be created the user would have input the names/teams

wild perch
#

I never thought of the loop I'll do that and I'll show you

unborn jacinth
#

Hello I am new to python and am trying to figure out why I can't find my self object in my method

outer rain
# unborn jacinth

you method implementation is on the same indentation level as the class, not as the function. In other words, your problem reduces to:

class Something:
    def genres_string(self):
        """ string """
    self.something  # wrong level of indentation
#

(btw I would highly recommend asking questions like this in #1035199133436354600 or #python-discussion, as this chat is for algorithms and math and such. It's likely to be answered anyway, but it might take longer)

unborn jacinth
#

my class is on the very first indentation and im still getting the error

unborn jacinth
hasty junco
#

Any1 have a good rationalization on how to deal with linked lists in python?

wooden dagger
#

def is_leap(year):
if year % 4==0:
if year % 100!=0 or year % 400==0:
return True
else:
return False
year = int(input())
print(is_leap(year))

input = 2100
output = none
expected output = False

#

can anyone help mer here

#

@young tangle @buoyant monolith help me here

haughty mountain
#

what path is taken?

wooden dagger
#

actually im solving rookie level python question from Hackerrank and I'm stuck in this Leap year question

wooden dagger
haughty mountain
#

walk through the code by hand, for input 2100 what happens in the code?

#

which branches of the ifs are followed?

#

i.e. what path is taken through the code

wooden dagger
#

I'm using nested if else here

#

The year can be evenly divided by 4, is a leap year, unless:
The year can be evenly divided by 100, it is NOT a leap year, unless:
The year is also evenly divisible by 400. Then it is a leap year.

this are the conditions

haughty mountain
#

that's not what I asked

wooden dagger
buoyant monolith
#

Your code doesn't exactly reflect the conditions required for a leap year

haughty mountain
# wooden dagger expected output was False

again, not what I asked, let's start here, what happens for input 2100?

   def is_leap(year):
->     if year % 4==0:
           if year % 100!=0 or year % 400==0:
               return True
       else:
           return False
wooden dagger
#

1st if condition is to check if it is divsible by 4 or not

haughty mountain
#

and the result is?

wooden dagger
haughty mountain
#

so we enter the if body.
ok, now what?

   def is_leap(year):
       if year % 4==0:
->         if year % 100!=0 or year % 400==0:
               return True
       else:
           return False
wooden dagger
#

in nested if condition is to check if year is also divisble by 100
and if it is divisible than output should be false

haughty mountain
#

what is the answer for the input 2100 we're looking at?

wooden dagger
haughty mountain
#

ok, where in the code do we end up now?

wooden dagger
#

2100 is divisble by 4 and also divisble by 100
so output should be "false" here
but it shows "None"

haughty mountain
#

pls

#

so the condition in the if I pointed to fails for 2100

wooden dagger
#
  1. The year can be evenly divided by 4, is a leap year, unless:
  2. The year can be evenly divided by 100, it is NOT a leap year, unless:
    2-1) The year is also evenly divisible by 400. Then it is a leap year.

this might help

haughty mountain
#

what happens after that?

#

please, just focus on the specific case of 2100

#

I'm trying to help you figure out the problem with the code on your own

wooden dagger
#

okay

haughty mountain
#

there is no else, so we just continue, we were in the if branch of the outer if statement so we don't trigger that else

#

we end up at the end of the function

   def is_leap(year):
       if year % 4==0:
           if year % 100!=0 or year % 400==0:
               return True
       else:
           return False
->
#

which will implicitly return None

wooden dagger
#

understood

haughty mountain
#

so there are a few ways to solve it

#

this path of execution needs to end up returning false

#

you could put a return False at the end but that ends up quite messy

wooden dagger
haughty mountain
#

this is one option

   def is_leap(year):
       if year % 4==0:
           if year % 100!=0 or year % 400==0:
               return True
           else:
               return False
       else:
           return False
```though an if-else returning True/False can be simplified into just
```py
   def is_leap(year):
       if year % 4==0:
           return year % 100!=0 or year % 400==0
       else:
           return False
```which ends up fairly neat
#

trying to walk through the code for some input you know misbehaves is an important debugging technique

wooden dagger
#

can you explain the working of your 2nd code

gentle cliff
#

if year mod 100 is not equal to 0 or year modulo 400 is not equal to 0 then it returns true

#

if year modulo 4 is equal to 0 and year modulo 100 is also equal to 0, it returns false (since one of the conditions ot get "true" is year % 100 != 0)

#

and if year modulo 4 isnt equal to 0 then it just prints false

#

because its not a leap year

haughty mountain
#

into just "return thing"

wooden dagger
#

okay thank you i got it

wooden dagger
gentle cliff
#

because its divisible by 100

haughty mountain
#

the issue wasn't the logic

gentle cliff
#

!e

def is_leap(year):
    if year % 4==0:
        return year % 100!=0 or year % 400==0
    else:
        return False
print(is_leap(2100))
halcyon plankBOT
#

@gentle cliff :white_check_mark: Your 3.12 eval job has completed with return code 0.

False
haughty mountain
wooden dagger
#

so if i just merge my both of condtion making it 1 and getting rid of excess it will be sucess, right ?

#

like

#

def is_leap(year):
if ((year % 4==0) and (year % 100!=0 or year % 400==0)):
return True
else:
return False
year = int(input())
print(is_leap(year))

this

gentle cliff
#

you forgot to add != after 400

#

but otherwise i think its okay

#

!e
def is_leap(year):
if ((year % 4==0) and (year % 100!=0 or year % 400==0)):
return True
else:
return False
year = 1978
print(is_leap(year))

halcyon plankBOT
#

@gentle cliff :white_check_mark: Your 3.12 eval job has completed with return code 0.

False
gentle cliff
#

seems like it works

wooden dagger
#

yes all test cases are succes

#

thanks everyone

#

def is_leap(year):
if year % 4==0:
return year % 100!=0 or year % 400==0
else:
return False
print(is_leap(2100))

can we write conditions in return statement ??\

lean walrus
neon glen
#

I am wondering if there is any type of maze, path, system where performing a BFS is impossible?

Background: I am framing a question from a pedagogical perspective and rather than explicitly tell the problem-solver to find the path via DFS, Ideally, I'd like to create a scenario where if they attempt to use BFS it will either fail or take an unreasonable amount of time.

I have managed to do the opposite so far by creating a large maze with loops, thereby causing a DFS approach to not result in the shortest path but rather just the first path it encounters. But I cannot conceive of a scenario where doing BFS would be impossible/incorrect.

narrow mica
neon glen
#

I know this. It's not what I asked

narrow mica
# neon glen I know this. It's not what I asked

ok I'll just assume you got that sorted then
one difference between dfs and bfs is the memory use, bfs will store all nodes that are the same distance to the origin at the same time
so if you had a very "wide" graph (e.g. many same-distance nodes, but not very deep), you might get the situation where bfs runs out of memory but dfs runs fine

neon glen
#

So you're saying there is no pathfinding scenario that cannot be solved with bfs?

narrow mica
#

by design it will visit the nodes with smaller distances first, dfs doesn't guarantee that

neon glen
#

I suppose I'll have to influence the choice of DFS in the wording of the question then

#

Subliminal messaging 😝

narrow mica
#

dijkstra's algo is also really bfs-y (with the heap implementation), and that's like one of the path finding algorithms

neon glen
#

thanks

haughty mountain
#

with the only difference being the data structure used

#

respectively: stack, queue and priority queue

eager marsh
#

guys how do we make a child class?

#

class Employee:
def init(self,HourlyPayp,EmployeeNumberp,JobTitlep):
self.HourlyPay = HourlyPayp
self.EmployeeNumber =EmployeeNumberp
self.JobTitle = JobTitlep
self.PayYear2022 = [0.0]*52

def GetEmployeeNumber(self):
    return self.EmployeeNumber

def SetPay(self,week_nop,hour_workedp):
    pay_of_week = hour_workedp*self.HourlyPay
    self.PayYear2022[week_nop-1] = pay_of_week

def GetTotalPay(self):
    total =0
    for i in range(len(self.PayYear2022)):
        total = total + self.PayYear2022[i]
    return total
#

I have dont this so far

#

I have to do this

image.png
eager marsh
#

class Employee:
def init(self,HourlyPayp,EmployeeNumberp,JobTitlep):
self.HourlyPay = HourlyPayp
self.EmployeeNumber =EmployeeNumberp
self.JobTitle = JobTitlep
self.PayYear2022 = [0.0]*52

def GetEmployeeNumber(self):
    return self.EmployeeNumber

def SetPay(self,week_nop,hour_workedp):
    pay_of_week = hour_workedp*self.HourlyPay
    self.PayYear2022[week_nop-1] = pay_of_week

def GetTotalPay(self):
    total =0
    for i in range(len(self.PayYear2022)):
        total = total + self.PayYear2022[i]
    return total

class Manager(Employee):

def __init__(self,BonusValuep):
    self.BonusValue = BonusValuep
    
    super.__init__
#

How is this??

exotic parrot
#

is this channel fit for questions about backtracking?

#

bcs I've got one

covert python
#

I am trying to parse a dict like structure to dict. However I am stuck where key has list indices e.g. a[0][0] , this should create a list of values. Here is the code that I am working on: https://collabedit.com/mrahk (If this doesnt work, let me know I will create a paste)

#

!paste

halcyon plankBOT
#
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 Paste! button in the bottom left, or by pressing CTRL + S. After doing that, you will be navigated to the new paste's page. Copy the URL and post it here so others can see it.

weak osprey
lilac cradle
#

i found this code i did a good long time ago for converting to a quaternion, do you guys know if there's a simpler way to do this

image.png
#

oh wait i can do the cos and sin just once for each but it'll take a lot more variable declarations
or only 6 actually nvm

violet panther
#

hai guys

haughty mountain
#

one rotation in each of X,Y and Z

eager marsh
#

Got a python exam on thurs 😭

rare laurel
ivory sun
#

!eval 3.12.3 ```python
def is_leap(year):
if year % 4==0:
return year % 100!=0 or year % 400==0
else:
return False
print(is_leap(2100))

halcyon plankBOT
#

@ivory sun :white_check_mark: Your 3.12 eval job has completed with return code 0.

False
weak osprey
#

What's the question

eager marsh
#

Im on anew question now

#

class Card():

def __init__(self,Numberp,Colorp):
    self.__num = Numberp
    self.__Color = Colorp

def GetNumber(self):
    return self.__num

def GetColour(self):
    return self.__Color

def ChooseCard(ValInput):
CardsChosen = [0]*5

if (ValInput < 0) or (ValInput > 30):
    return -1 #Value is not in range

if UserCardAttempt == 0:
    return -2 #User has used up all his attempts

for i in range(30):
    if ValInput == My_1D_Array[i]:
        return i #Value has been found
    
UserCardAttempt = UserCardAttempt - 1
ValGuess = input("Your attempt was wrong try again.")
return ChooseCard(ValGuess)

#Main
My_1D_Array = [Card(0,"")]* 30
UserCardAttempt = 5
try:
file = open("CardValues.txt", 'r')

for i in range(30):
    no = int(file.readline())
    clr = file.readline()
    My_1D_Array[i] = Card(no,clr)

except:
print("File not found")

#

I have done this so far

#

The rest I think is ok im at part (d)

#

def ChooseCard(ValInput):
CardsChosen = []

if (ValInput < 0) or (ValInput > 30):
    return -1 #Value is not in range

if UserCardAttempt == 0:
    return -2 #User has used up all his attempts

for i in range(30):
    if ValInput == My_1D_Array[i]:
        print("Your value has been found")
        CardsChosen.append(ValInput)
        return i #Value has been found

    
UserCardAttempt = UserCardAttempt - 1
ValGuess = input("Your attempt was wrong try again.")
return ChooseCard(ValGuess)
#

This is the procedure but I think im messign up somehwere

weak osprey
# 
# your code goes here
print("Like this")

Do this for embedding code

IMG_20240518_083046.jpg
weak osprey
eager marsh
weak osprey
eager marsh
#

ohhh

weak osprey
#

those ^

eager marsh
# 
def ChooseCard(ValInput):
    CardsChosen = []
    
    if (ValInput < 0) or (ValInput > 30):
        return -1 #Value is not in range
    
    if UserCardAttempt == 0:
        return -2 #User has used up all his attempts

    for i in range(30):
        if ValInput == My_1D_Array[i]:
            for y in range(len(CardsChosen-1)):
                if ValInput == CardsChosen[y]:
                    ValGuess = input("Your attempt was laready ocne found") 
                    return (ChooseCard(ValGuess))

                
            print("Your value has been found, try to find another")
            CardsChosen.append(ValInput)
            return i #Value has been found

        
    UserCardAttempt = UserCardAttempt - 1
    ValGuess = input("Your attempt was wrong try again.")
    return ChooseCard(ValGuess)
weak osprey
#

And if the card has not been selected, then you add it to that list

#

And if it has been selected, then you ask the user for another one

#

I don't know if I explain myself xd

eager marsh
#

yeah I think I get it

#

Lemme try smthns

weak osprey
#

Oka

#

I would code it and give you the example but I'm not at home xd

eager marsh
#

The main issue I have with these things is that its hard for me to understand what the question is asking 😭

#

Im gon try to redo the whole thing and then see if that works better

#

I have done something not sure if that is fine

# 
def ChoosenCard(ValInput):
    if (ValInput < 0) or (ValInput > 30):
        return -1 #Value is not in range
    
    for i in range(30):
        if ValInput == My_1D_Array[i]:
            return i

#Main
CardsChosen = [] #array which will have the values which have been found already

for i in range (5):
    if len(CardsChosen) < 4:
        ValReq = input("Input a value to search (in the rnage of 0-30)") 
        Cardreturn = ChoosenCard(ValReq)
        if Cardreturn == -1:
            print("The value you have entered in not in the range try again")
        else:
            for y in range(len(CardsChosen-1)):
                if ValReq == CardsChosen[y]:
                    print("You had already previously found this value try again")
            print("Your value has been found at index {}".format(Cardreturn))

    else: 
        print("you have used up all your attempts")
#

This the other part 🤔

image.png
lilac cradle
olive coral
#

can anyone help me here? i cant run .py Files

image.png
haughty mountain
#

and you lose stuff like x y = y x when going from complex numbers to quaternions

lilac cradle
#

ye im aware of that

#

just not all the specifics

#

oh huh i think i maybe got an algorithm i was working on for a couple hours to work

#

trying to group up pixels into rectangles, so as to more easily fill areas

#

i gave it this image as input, and it did this
i think it still needs some work tho

image.png image.png
#

oh that's why

#

that orange rectangle kinda softlocked itself by going into that little divot, since it couldnt expand anymore
the algorithm basically has 4 options, expand right, expand down, expand left and expand up

i might remove the second two if they turn out not to be useful but it seems fine for rn

but it basically checks the new pixels in the area and if it's not occupied and they're all the same color, it expands to that area, and keeps trying to until it hits a dead end
after it hits one, it tries a different direction until it manages to expand again (resetting its amount of attempts to expand) or until it runs out of attempts

haughty mountain
#

the key part of this is the same as your problem

lilac cradle
#

nvm i broke it

#

i fucking hate this algorithm

#

specifically write code to make it NOT OVERLAP
it overlaps

#

im just deleting this entire thing

#

i think the term for what i want specifically is Rectangular Image Separation or something like that

lilac cradle
#

oh i think i see why my implementation was failing, they are iterating through coordinates to choose the starting point

lilac cradle
#

YES THERE IS VSCODE

image.png
lilac cradle
#

ok i got it to work
its the same general idea but i rewrote it from the ground up

#

as a bonus it's like a gajillion times faster

lilac cradle
#

the hue is showing which quad is being drawn

image.png image.png image.png
#

the image is just something i scribbled on, to test

fiery cosmos
#

Hey

covert python
#

HI, I have a string like this {a[0][0][0] : 'b'}, I want to create a list from this which would be { a : [ [ ['b'] ] ] }

I am trying with regex: list_pattern = re.compile(r"[([0-9]+?)]") , not sure how to create the lists and put data into it.

quiet heath
#

What would be the best book for leanring ds and algorithms? I was looking at CRLS and I am fairly certain that would be best. Any suggestions that would be better than that one?

clever panther
#

I am in school and wondering if anyone knows about flowgorithm?

lilac cradle
lilac cradle
haughty mountain
#

np, glad my memory clogged of random programming stuff ended up helpful :P

lilac cradle
#

heres a sc of the code btw
i had an issue with it 'hanging' for a while after it generated all the necessary quads, but i managed to fix it when i realized i never implemented a 'cut-off' for when there was no more space for them

image.png
#

and yeah idk if the nested function is cursed but its a hall of a lot cleaner than what i did before (i had the 'fail check' code for literally every condition individually)

#

im sure i could condense the multiple move types into one block but i dont think its worth it

#

also this script represents the first time i seriously used the debugger and breakpoints

lilac cradle
lilac cradle
# lilac cradle heres a sc of the code btw i had an issue with it 'hanging' for a while after it...

btw, some specific questions related to it, 1. is there any efficient conversion from the image grid in pillow (i.e im.load()) to some other datatype? ideally this algorithm should be able to work on any 2d-array like object
and also, is there a good datatype for destructively reading something? one way that that one video mentioned increasing performance is by deleting the stuff to work on so you don't have to 'revisit' it, i could just write over the existing image grid but that'd probably be slower than just doing it like im already doing (i add all the positions that i visit to a set, and check if new coordinates are in that set)

haughty mountain
#

in the impls in the video the solution to doing these efficiently is bit math

lilac cradle
#

yea i saw that

#

that won't work for what i'm doing though

#

because a pixel can be any color

#

the reason the bitmath works is because they reduce it to binary and only have a few types of voxel iirc

haughty mountain
#

how many unique colors are you working with? pithink

lilac cradle
#

it just takes in an image and segments it

#

for a big enough image, millions but i think the segmenter would have a very hard time doing that

haughty mountain
#

at that point segmenting doesn't help you anyway

lilac cradle
#

yeah

#

but even in a small image you can potentially have a couple hundred

#

also maybe i should add a chroma key feature..

#

before, i had a simple alpha threshold option, so as to not bother creating useless transparent quads, but i think it'd be better to simply blacklist some colors

#

also just checked, the 'pixel grid' object i mentioned is properly called a PixelAccess object

#

maybe i could work with numpy arrays but afaik, numpy arrays excel at doing big operations, not lots of little ones like i'm doing here

haughty mountain
#

numpy arrays and throwing numba at the problem is probably not a bad idea

#

assuming you can boil things down to fairly raw operations

#

and when doing that you might win a bunch from modifying the underlying array instead of keeping a set

lilac cradle
#

im mainly doing this for things like besiege where im trying to make stuff out of the blocks

#

specifically the surface blocks which are very customizeable but super laggy

#

so like i can do it by just making each one at each pixel but it gets unbearable very quickly (like 75x75 with a transparent background was enough to instantly crash the game when i tried using the move tool)
so ideally i'd like to instead of having a bunch of them for each pixel, i just group them up and make big ones instead

lilac cradle
#

god damn it the algo overlaps

lilac cradle
#

fixed it, my 'passed checks' code was improperly placed so it went ahead and expanded it if even a single pixel was acceptable (since it was in the loop
for transparency i had to add it in the start selection code as well as the checks code, otherwise it just started quads on transparency, none of the checks passed,so transparency just ended up as a bunch of single pixels

covert python
haughty mountain
lean walrus
#

noop, according to their example

lucid rose
#

guys I need a help

#

im mind___ over this

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

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0

    def __str__(self):
        temp_node = self.head
        result = ''
        while temp_node is not None:
            result += str(temp_node.value)
            if temp_node.next is not None:
                result += ' -> '
            temp_node = temp_node.next
        return result

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.length += 1

    def part(self , val):
      temp = self.head
      prev = None
      while temp is not None:
        if temp.value < val:
          this_node = temp
          temp = temp.next
          this_node.next = self.head
          self.head = this_node
        else:
          blah = temp
          temp = temp.next
          self.tail.next = blah
          blah = self.tail
          blah.next = None

The prblm is coming in the function PART() , so u dont need to check anything else (ur wish tho)

The Aim : Write a code to partition a linked list around a value x , such that all nodes less than x comes before all the nodes greater than x

#

there was not much of help in the doubt section so I thought of maybe asking it here

# 
f = LinkedList()
f.append(12)
f.append(3)
f.append(9)
f.append(15)
f.append(13)
print(f)
f.part(10)
print("yahoo")
print(f)
          ```
#

Im trying to run this

#

tho it never prints after using PART() func , which ig means that a loop is forming

#

tho I would appreciate very much if someone can help me to solve this

orchid violet
flat sorrel
#

that's a Java problem, not really related to Python. you're probably better off asking in a space that is dedicated to Minecraft

fiery cosmos
# 
# 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

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
                
        # Base case: If the root is None or the root's value is the target value
        if root is None or root.val == val:
            return root

        # If the value to be found is less than the current node's value, search in the left subtree
        if val < root.val:
            return self.searchBST(root.left, val)
        # If the value to be found is greater than the current node's value, search in the right subtree
        else:
            return self.searchBST(root.right, val)
#

not understanding how this code also returns the subtree rooted at a given value

#

it seems to me that it could only return a single value

#

i think i'm not understanding this line:

def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
brave hound
#

it is returning a TreeNode object which itself is a tree

fiery cosmos
#

ooohh

brave hound
#

the left and right attributes in TreeNode are tree nodes (or None)

haughty mountain
#

yeah, it is returning a single value

fiery cosmos
#

a single object?

fiery cosmos
#

looking for help with 374 guess number higher or lower

# 
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
#          1 if num is lower than the picked number
#          otherwise return 0
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:

        if n == 1 or n == 2 or n == 3:
            
            if n == 1:
                return 1

            first_guess = guess(2)

            if first_guess == 0:
                return 2

            else:
                if first_guess == 1:
                    return 3
                
                else:
                    return 1
        
        first_guess = n//2

        ans = guess(first_guess)

        if ans == 1:

            for i in range((n//2),1,-1):

                ans = guess(i)

                if ans == 0:
                    return i

        if ans == -1:

            for i in range((n//2),n):

                ans = guess(i)

                if ans == 0:
                    return i
#

how am i getting a null out of this code

fiery cosmos
#

hm i'm not sure i agree with the categorization of some of the leetcode difficulties. i just solved a medium that was much simpler than the above problem

#

i'd guess certain problems are more easily solved in Python vs. other languages

narrow mica
#

it will never be accurate because different people will have learned different topics when they tackle a problem

plain goblet
#

could someone please explain to me why the program is outputting "None" after each message??? Any help appreciated

image.png
#

here is a more complete screenshot of the whole thing

haughty mountain
#

clearly the intention is a binary search

haughty mountain
#

and yes there is a path where you do that

#

I'm also very confused why you special case some small sizes

fiery cosmos
#

@haughty mountain can you help me with the logic

haughty mountain
#

just read about binary search

#

like, the idea of looking at the midpoint isn't wrong

#

but you need to take that further

fiery cosmos
#

also, LC 238 product of array except self is super interesting, i'm thinking it'll require a list comprehension or generator somewhere. the catch is you have to do it in O(n)

haughty mountain
#

seems fairly trivial

fiery cosmos
haughty mountain
fiery cosmos
#

you'd add them all together and subtract the value at that location however, they forbid you from performing division, an added caveat

#

so in other words you cannot simply multiply everything in the array and then divide out that integer at that location

haughty mountain
#

that's dumb

fiery cosmos
#

why?

haughty mountain
#

with allowed division there is already gotchas

fiery cosmos
#

it's a neat problem bc of these constraints, i think

haughty mountain
#

it's still a pretty trivial problem

fiery cosmos
#

medium LC problems are not yet trivial to me 😅

#

some easys are not as well, e.g. the number guessing one

haughty mountain
#

the sum and product version of this problem is the same if division/minus is disallowed

fiery cosmos
#

🤔

haughty mountain
#

well not same, but same approach works

#

only the operation differs

#

for sum you can just compute two cumulative sums, one from the left and one from the right

#

and then the problem is basically solved

fiery cosmos
#

perhaps we should return to the guess number higher or lower first, if you wouldn't mind

#

i moved toward an approach where my guess becomes my guess // 2 on the lower side and myguess + n//4 on the upper, but i'm well aware this will not work

#

i'll read on binary search

#

no i don't get it

#

i mean i get binary search but not how to make it work with the guess API that is part of problem 374

haughty mountain
fiery cosmos
#

this takes n, not multiple parameters like array, high, low

#

really have no idea how to make it work within their existing guess() and guessNumber() functions

lilac cradle
#

Is using bitflags a bad idea? Yesterday i ran into the problem of needing 3 boolean arguments for roughly the same thing (it was to change the “mode” of an input value between acting as if it was a single key or a string, but i needed that to be able to be changed for 2 inputs and an output) and i just said ‘screw it’ and made it a int, then bitmasked the individual flags from it

#

like is there something specific for this, or should i use something else, or what

keen hearth
# lilac cradle Is using bitflags a bad idea? Yesterday i ran into the problem of needing 3 bool...

Bit flags can be appropriate in some circumstances. E.g. python's re module uses flags to change certain things about how the regular expressions are interpreted. If you are going to use flags though I recommend using enum.Flag: https://docs.python.org/3/howto/enum.html#flag

Python documentation
Enum HOWTO

An Enum is a set of symbolic names bound to unique values. They are similar to global variables, but they offer a more useful repr(), grouping, type-safety, and a few other features. They are most ...

lilac cradle
#

kk

keen hearth
#

E.g. ```py
class Perms(enum.Flag):
READ = 4
WRITE = 2
EXECUTE = 1

lilac cradle
#

does that allow combining them i.e WRITE | EXECUTE

keen hearth
#

Yep!

lilac cradle
#

kk

fiery cosmos
#

i don't understand the leetcode situation at all. in this problem there is a notion of n but i don't know where it comes from or which functions have scope of it

#

this is leetcode 374 Guess Number Higher or Lower

#

trying to go in this direction:

class Solution:
    def guessNumber(self, n: int) -> int:

        myguess = n // 2

        ans = guess(myguess)

        if ans == 0:
            return myguess
        
        elif ans == -1:
            low = 1
            high = myguess
            newguess = high // low
            return guessNumber(newguess)

        elif ans == 1:
            low = myguess
            high = n
            newguess = high // low
            return guessNumber(newguess)
            
        guessNumber(n)
# 
NameError: name 'guessNumber' is not defined
           ^^^^^^^^^^^
    return guessNumber(newguess)
Line 28 in guessNumber (Solution.py)
          ^^^^^^^^^^^^^^^^^^^^^^^^^
    ret = Solution().guessNumber(n)
Line 50 in __helper__ (Solution.py)
                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    guessed_number = __DriverSolution__().__helper__(n, pick)
Line 70 in _driver (Solution.py)
    _driver()
haughty mountain
#

you're just asking "is the value at this point >, < or =?"

#

which is exactly what the function given to you lets you ask

fiery cosmos
#

Is there any obvious misunderstanding of the leetcode solution class you’re perceiving that I may have

haughty mountain
#

no, more a misunderstanding of binary search

#

you don't need an array to do binary search

#

let's assume the number you're looking for is between >=0 and <n

if so you start with an interval [0, n) where the value could be

you check the mid point

  • if the value is lower you know the new relevant interval is [0, mid)
  • if the value is greater you know the new relevant interval is [mid+1, n)
  • if it's equal you have found the number, done
#

in the first two bullet points you now have a smaller instance of the same problem

#

so repeat the same procedure

fiery cosmos
#

I’m comfortable with the binary search logic just not implementing it recursively and in leetcode and without an array

#

I’ll try again tomorrow. I see some obvious mistakes in my above code

#

I don’t understand how to get the middle of the upper half of the array

#

The lower half you can always divide in two again from the midpoint

#

But if you tried to do the opposite (multiply by 2) to get the upper half array midpoint you’d instead just get n

#

I’m noticing that if I take the existing midpoint and add it to n (total length of array or in this case range of guesses) I could then divide by 2 to get a mid point

#

Of the upper half

lilac cradle
#

why is that a class anyway

fiery cosmos
#

alright i got a working binary search going locally but it takes array, low, high, and search value as arguments and returns the index of the search term

#

so now i just need to shoehorn this into leetcode and get it working

#

ok so i actually cannot use an array to solve

lilac cradle
#

you dont even need recursion, literally just a for loop would work

fiery cosmos
#

this is a good opportunity to learn recursive binary search tho

haughty mountain
lilac cradle
haughty mountain
#

you have a lower and upper bound, you check the midpoint, you update the bounds based on the result

#

repeat

fiery cosmos
#

yeah im seeing that now

#

i see the logic that i stumbled upon e.g. the existing mid plus the highest value // 2 is the mid of the upper half

#

mid becomes new low

#

et cetera

#

nailed it

haughty mountain
#

every query you do here effectively splits the ranges in three

[low, high)
into
[low, mid), mid, [mid+1, high)

fiery cosmos
#

ty for not helping me, forced me to learn it on my own. plus it was bothering me all day so i refused to rest until i got it 💪🏻

#

you can write functions within the Solution class guessNumber method that comes predefined for you

#

here is the answer:

# 
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
#          1 if num is lower than the picked number
#          otherwise return 0
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:

        x = n
        def bin_search(low, high, x):

            if high >= low:

                mid = (high + low) // 2

                if guess(mid) == 0:
                    return mid
            
                elif guess(mid) == -1:
                    return bin_search(low,mid-1,x)

                else:
                    return bin_search(mid+1,high, x)

        
        return bin_search(1,n,n//2)
fiery cosmos
shadow glen
#

@signal canyon it's because i can add more than 1 language package

#

i wanna make it easy to maintain

#

when adding

#

if i don't use importlib

#

it would becomes a spagetti code

#

sorry for confusing the tops

#

*topics

shadow glen
#

okay so i feel like i'm gonna repeat this many times:
}

image.png
#

you guys probably knows the json thing that i forgot

#

how do i do that?

#

my plan here is to also allows cross stuffs

#

like bi for text

#

ils for ||text||

#

until i get into biuls

#

tha\t makes

#

||Hello World||

fiery cosmos
#

any hints on leetcode 238 Product of Array Except Self?

#

must run in O(n), no division

#

initial thought is make a list with all indices of the products, but i keep end up having to do a nested loop

jolly mortar
#

hint ||prefix product||

stiff quartz
#

Hi, I'm looking at this problem (https://leetcode.com/problems/the-number-of-beautiful-subsets/description/) (today's daily leetcode problem).

I found a solution that runs in O(n^2 * 2^n). It's a very simple solution and obviously naive one. I use bitmasks, define the forbidden couples of integers like so:

forbidden: set[int] = set()
for i in range(n):
    for j in range(i+1, n):
        if abs(nums[j] - nums[i]) == k:
            forbidden.add((2**i) + (2**j))

and then I look at all the possible bitsets and check if they "conflict" with the at most n^2 elements of forbidden:

ans: int = 0
for i in range(1, 2**n):
    for forbidden_couple in forbidden:
        if (i & forbidden_couple) == forbidden_couple:
            break
        else:
            ans += 1
#

My solution runs in 1s

#

Then i looked at the editorial which first solution is O(n*2^n)

#

So it should be about n times faster than mine

#

I implemented their solution, recursively and iteratively (they only provide it recursively, here is the one I used iteratively: https://pastebin.com/7KYye7f3)

#

and it takes 10 times longer instead of going n times faster (11 seconds with the recursive version, 9.7 seconds with the iterative one)

#

Am I missing something??

#

Is my initial solution (https://pastebin.com/pDd0pvEU) not as naive as I thought it was? (PS I'm not trying to understand how to make a solution to this problem in O(nlogn) (which is possible), but just trying to make sense of what I pointed out as inconsistent, theory-of-complexity-wise)

fiery cosmos
#

isn't recursion known to be slow

#

Not really.

Python fonction calls are quite expensive, python does not provide tail recursivity optimisation and will not, python has a (configurable) euristic to crash after too much recursive calls, and finally there is a theorem that says that for every recursive algorithm exists at least one non-recursive algorithm that is at least as efficient as the recursive one (this is true for all languages)

#

but being off by 10x while it should be simpler big-O wise doesn't add up. is it possible the complexity of your solution is different than what you stated

#

or that their O complexity is off?

fiery cosmos
#

hm.. still stuck

stiff quartz
stiff quartz
stiff quartz
fiery cosmos
#

hey is there any dev can make tool can auto repost vidoes on tiktok

#

@stiff quartz have you done LC 238?

#

i need a hint but without giving it away

#

so far i know prefix sum

#

struggling w the time complexity requirement and doing everything other than a given position in the array

stiff quartz
fiery cosmos
#

found this help online:

#

lmao

fiery cosmos
#

alright, i got it but w help from gpt

#

you basically make other prefix and suffix arrays and make them equal to the products of everything multiplied through up to that point except for that number which occurs at a given location/index

#

then populate the answer array by going through and multiplying all the prefix and suffix integers from each array

#

kind of hate AI for this but i also don't have unlimited time

haughty mountain
#

suffix array is a very different thing

haughty mountain
#

!e something like this

seq = [1, 2, 3, 4, 5]
left = [1]
right = [1]
for x in seq:
  left.append(left[-1]*x)
for x in reversed(seq):
  right.append(right[-1]*x)
left.pop()
right.pop()
for l, r in zip(left, reversed(right)):
  print(l*r)
halcyon plankBOT
fiery cosmos
fiery cosmos
#

it's soo hard for me to follow the logic. this is right up against my capabilities in this area

fiery cosmos
#

saved, thanks

regal spoke
#

Btw it is possible to solve this problem in O(2**n) time by using the fact that ((x) ^ (x + 1)).bit_count() is O(1) in average

modern agate
stiff quartz
#

So all good, maths is not wrong, we are safe

stiff quartz
# regal spoke Btw it is possible to solve this problem in `O(2**n)` time by using the fact tha...

I found a way to do it in O(2**n like so (a bit like when looking up the longest path in a graph)

class Solution:
    def beautifulSubsets(self, nums, k):
        
        def beautifulSubsetsRec(idx, count):
            if idx == len(nums):
                return 1
            
            res = beautifulSubsetsRec(idx + 1, count)
            if not count[nums[idx] + k] and not count[nums[idx] - k]:
                count[nums[idx]] += 1
                res += beautifulSubsetsRec(idx + 1, count)
                count[nums[idx]] -= 1
        
            return res
    
        return beautifulSubsetsRec(0, Counter()) - 1
#

but don't really get what your solution would look like

#

how would a XOR be useful here?

haughty mountain
#

product of everything to the left/right is something we can easily and efficiently precompute across the whole array

shadow glen
#

okay so, is there a better way of selecting what i want to remove?

#

foir exaple here:

image.png
#

instead of removing all * i wanna just remove the ones at beggining and end

#

**Lifespan * Neutrality** -> Lifespan * Neutrality
instead of
**Lifespan * Neutrality** -> Lifespan Neutrality

narrow mica
fiery cosmos
#

Hey guys do you use VS code or the cloud platforms

shadow glen
#

anyone here knows regex?

#

i need one that get all the characters that are inside in between _, __, ___, *, **, ***, ~~ and/or ||

#

so i can capture all of those strings which are inside this

#

and i'm planning to it also sabe those "special characters" as a reference

#

so i can work on it later

#

i can't ask this for an ai since it's way too complex

outer rain
#

Unless I misunderstood..

#

if you want to just get what strings are inside the matching pairs, you can just match everything with /\b__.+?__\b/, for instance, but you won't be able to combine the expressions well

#

parsing something like a*b_c*d_ is going to be annoying

#

anyway, still, don't use regex please, it's probably not worth it

silent jasper
#

anyone has any good image similarity algo

#

ppls

#

pls

#

pls

waxen crypt
#

is 10h screentime bad?

fiery cosmos
# waxen crypt is 10h screentime bad?

< 1hr (less than one hour): Very healthy and minimal.
1 - 3 hrs: Healthy and moderate.
3 - 5 hrs: That must be your job and source of income.
5hrs+ : Either you work for NASA or at least maintaining an important infrastructure OR you have unhealthy addiction.

regal spoke
# stiff quartz I found a way to do it in `O(2**n` like so (a bit like when looking up the longe...

Btw this should be a linear time solution for the problem

import sys
n,k = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

import collections
buckets = collections.defaultdict(list)
for a in A:
    buckets[a % k].append(a // k)
buckets = [buckets[key] for key in buckets]


new_buckets = []
for bucket in buckets:
    bucket.sort()
    for i in range(len(bucket) - 1)[::-1]:
        if bucket[i] + 1 < bucket[i + 1]:
            new_buckets.append(bucket[i + 1:])
            del bucket[i + 1:]
    new_buckets.append(bucket)

buckets = [[b - bucket[0] for b in bucket] for bucket in new_buckets]

dp0 = 1
dp1 = 0
for bucket in buckets:
    m = max(bucket) + 1
    counter = [0] * m
    for b in bucket:
        counter[b] += 1

    for c in counter:
        dp0, dp1 = dp0 + dp1, dp0 * (2**c - 1)

    dp0, dp1 = dp0 + dp1, 0

# -1 to not count the empty set
print(dp0 - 1)
#

Well it is technically not linear since the numbers could become large. But it would be linear had the task been to print the answer mod 10^9 + 7.

toxic hare
fiery cosmos
#

Hii, I'm going to start leetcode from today to 12th July in my summer break (~45 days), 2q a day min - if someone wanna do alongside, let me know. I'm clear with data-structures concepts but haven't did much leetcode and cp yet.

fiery cosmos
#

Did this message go through?

toxic hare
fiery cosmos
toxic hare
spring basin
brittle vine
#

Trying to check my understanding of something: PEP-342 and 380 effectively turned generators into de facto coroutines. Then, 492 gave us async/await syntax and a separate Coroutine type, but Generator objects still have all the methods and semantics required to be coroutines.

I was reading https://eli.thegreenplace.net/2009/08/29/co-routines-as-an-alternative-to-state-machines/, which was written before PEP-492 and is an example of using coroutines for an algorithm that has nothing to do with asynchronous I/O, which is pretty much what I understand to be the purpose of the Coroutine type in Python. I'm honestly not sure if this algorithm could be (easily) expressed with async/await, but that's probably just me being used to thinking of them as "functions that magically don't block" (and I do know that's inaccurate).

I guess I could condense my thoughts here into the question: with PEP-492, is there any case where one might write a coroutine algorithm using generator functions instead of coroutine functions and an event loop like asyncio?

south umbra
#

yes, a few secs more

#

yes appending into a list at merge_json function,
tho i have a issue can u help me in rag

flat sorrel
#

feel free to explain it here

calm token
#

Greetings people!

#

People I'm having an issue with a code. I'm trying to create a program where the user picks 2 values randomly (without repeting) from 2 different list. Then at the end I make a sum() about it but for some reason i'm getting errors. This is the code that I have

from random import sample
from random import choice


List1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
List2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12]

User1_List = []
User2_List =[]

for i in range(2):
    User1_List.append(sample(List1 or List2,1))

print(User1_List)
#

So, I created a list called User_List = [] where I assign 2 different values to the list by using he for loop!

#

This is the error that I'm getting

36d3a9ae28b8a2c8c86a7b15463052ec.png
haughty mountain
haughty mountain
#

sample returns a list of samples

#

also, I don't think the List1 or List2 does what you think it does

calm token
#

Oh yeah! I found the isse

#

It was a missunderstanding and I fixed it!

#

Now I have to develop the logic to make it work

# 
from random import sample
from random import choice


List1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,12]
List2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,12]

List_Choice = [List1, List2]

User1_List = []
User2_List =[]


for i in range(2):
    Random_List = choice(List_Choice)
    if Random_List == List1:
        print("First List was Selected")
    else:
        print("Second List was selected")

    User1_List.append(choice(Random_List))



print(User1_List)
haughty mountain
calm token
#

I had to create another list to select randomly a list

#

Now I have to develop a logic that when I select 2 different values randomly from one list and one from another list, it doesn't have repeat

haughty mountain
#

what's the actual goal?

calm token
#

For example, if the software randomly selects the number 9 from the List1, that number can't be selected again from that list, but it can be selected from the other list.

#

I don't know if you understood me Peepo_Giggle

#

But I'll do it tomorrow because It's almost 2 am here lul

haughty mountain
#

say

List1 = [1]
List2 = [2, 3]
```and you pick one item, what should the chance of picking each item be?
#

1/3, 1/3, 1/3
or
1/2, 1/4, 1/4

calm token
haughty mountain
#

with your current code and the lists I gave it would be 1/2, 1/4, 1/4

#

i.e. much more likely to pick the 1

calm token
#

Oh

#

but it has to be randomly

#

hehe

haughty mountain
#

uniformly random?

calm token
#

Yep!

#

For now

#

With the random command

#

Well, function hehe

haughty mountain
#

if so your current code doesn't work

calm token
#

Oh no, for now is currently working!

#

I mean, I can append numbers and make Sum!

#

But tomorrow, I'll develop the logic to add numbers on the list without repeating them YesYes

haughty mountain
#

I meant it's not uniform

#

ok, it is uniform only of the two lists are the same length

#

if you move away from that things become non-uniform like with my example lists

#

is all you want to do to treat the lists as if it was one long list for the sake of sampling?

calm token
#

Yeah yeah!

#

Maybe like that!

haughty mountain
#

if that's what you want, why not just make one big list and sample that? pithink

calm token
lilac cradle
#

say i have a class A and a subclass of A, called B
if i have some method that returns an instance of A or B, how would i make it so that when an instance of B uses the method, it returns an instance of B, rather than an instance of A?

brittle vine
# lilac cradle say i have a class A and a subclass of A, called B if i have some method that re...

if we're talking methods on A and B, a class method is probably appropriate:

class B(A):
    @classmethod
    def method(cls, *args) -> "B":
        # do stuff 
        return cls(*args)

If you're trying to use a standalone function or static method, maybe something like

def func(obj: T) -> T:
    # logic to make init_args, if needed
    return type(obj)(*init_args)

Otherwise, return self should pretty much handle a regular method returning an object of the same class (by simply returning itself).

lilac cradle
#

kk

brittle vine
young totem
modern agate
#

like the other one is walking up stairs I think, the only patter I see is like turning something into an array and reusing the previous answer. but if someone asked me what dynamic programming is I wouldnt know what to say

narrow mica
#

e.g. for your coin change, if you had coins of 1, 2, 5, and you wanted to get to 17, you could

  • get 16 then take a 1 coin
  • get 15 then take a 2 coin
  • get 12 then take a 5 coin
    the question now becomes, how do you get to 16, 15, or 12? but pause, because notice that you've just asked the same question - "How do I get to x" - just with smaller inputs. That's the divide & conquer part
#

let's draw a tree of dependencies (and go 1 layer deeper on 16 - to get there, you can do 15 + 1, 14 + 2, or 11 + 5)

  --- 17 ----
 /     |      \
12    15    - 16 --
           /   |   \
          11  14   15
```notice that the problem of "How do I get to `15`" appears twice - you could just calculate it twice, or you can calculate it once, store the result, and just use the result if you need it again. That's the memoization part
modern agate
#

wow that was super helpful, now I know what they mean by divide and concur (split up) then cache/memoize thank you very much!

lilac cradle
#

is there a way to sort of template for an object with classes? so say i have different types of NPC, so some can be ranged, melee, or not attack at all, some are from different areas, etc
would i just use if statements to check for something like 'if npc.is_ranged' and then run code for that, or is there a more elegant way

#

or like say im storing a bunch of properties about different types, so like say "warrior":{is_ranged: False, health: 200, armor: 15, attack: 10} or whatever, would i just use a dictionary for that or is there something for it

im pretty sure theres some concept in oop im grasping at here but im not sure what it is

haughty mountain
lilac cradle
#

i guess

#

i just was thinking using a subclass for each thing would be a bit much but i might just try it

#

rn im doing this lmao

image.png
#

oh wait i dont think i even needed to do this

#

oh well

sacred oracle
# lilac cradle rn im doing this lmao

Hey! I'm a super new coder and I know very little so take what I say with a HUGE grain of salt, but surely using a class would work better here and be more code length efficient right?

lilac cradle
#

yeah, i eventually switched to that

#

specifically an enum

flat sorrel
#

that way you can use the existing syntax (literal dicts) for defining new objects

radiant rose
#

Hey guys so the question is to encode and decode a given list into a string and back. Its a leetcode question. I dont know what my error is please do help

a = ["Hello", "world", "he::o", "Hello World ", "hello##world"]
temp_str = ""

for i in a:
    temp_str = temp_str +str(len(i)) + "#" + i

result, j = [], 0

while j < len(temp_str):
    k = j
    while temp_str[k] != '#':
        temp = ""

        k += 1
        length = int(temp_str[j])
        temp = temp_str[k+1: k+1+length]

        result.append(temp)

        j += k+1+length

print(result)
fluid siren
#

does anyone know what's the mistake in this

image.png
stray fractal
fluid siren
#

okayy thank youu

haughty mountain
agile sundial
fiery cosmos
lilac cradle
lilac cradle
lilac cradle
#

oh i see what you're trying to do, you have the numbers for how long each segment is and then try and jump to the next from that
the problem with that is that even though you check for a character being '#' for the index k, you don't check the index after that since you add 1 to k after that check

you're also only using one character for the number of characters to jump to, so if something has, say, 10 characters, it won't interpret that '10' that you encode as the number 10, but as a '1' and a '0' respectively, so it jumps into the wrong character and errors

lilac cradle
#

took me a bit but i wrote what i think is a working version of that encoding/decoding process

a = ["Hello", "world", "he::o", "Hello World ", "hello##world"]

def encode_list(l):
    temp_list = []
    for i in l:
        temp_list.append(f"{len(i)}#{i}")
    return "".join(temp_list)

def decode_list(s):
    result = []
    k = 0
    while k < len(s):
        digits = ""
        new_char = s[k]
        while new_char.isdigit():
            digits += new_char
            k += 1
            new_char = s[k]
        else:
            length=int(digits)
            temp = s[k+1:k+1+length]
            result.append(temp)
            k += 1 + length
            digits = ""         
    return result

encoded_string = encode_list(a)
print(encoded_string) # "5#Hello5#world5#he::o12#Hello World 12#hello##world"
decoded_list = decode_list(encoded_string)
print(decoded_list) # "['Hello', 'world', 'he::o', 'Hello World ', 'hello##world']"
radiant rose
# 
a = ["Hello", "world", "Hello", "#hel" ,"j@#@"]
temp_str = ""

for i in a:
    temp_str = temp_str +str(len(i)) + "#" + i

result, j = [], 0

while j < len(temp_str):
    k = j
    while temp_str[k] != '#':
        temp = ""

        k += 1
        length = int(temp_str[j])
        temp = temp_str[k+1: k+1+length]

        result.append(temp)

        j = k+1+length

print(result)```
radiant rose
#

Btw thanks for the reply

lilac cradle
#

np

sage flax
#

This is a Game

#

Like Math Game WIth Python GG

fiery urchin
#

how i can master data structs and algos

dawn plover
#

can someone explain why this while loop gets skipped?

image.png
#

putting the "g+=2" in the loop does nothing

#

I just rewrote the entire thing except:
g=-9
while g<69:

haughty mountain
#

it won't be skipped

#

are you actually running this code?

flat sorrel
#

looks like you're going to get infinite recursion since you are always calling self.in_order_travelrsa

dawn plover
#

Now it says: "name 'in_order_traversal' is not defined"

image.png
#

WHAT THE MAGNA LUPA?

flat sorrel
#

have you studied OOP?

#

in_order_traversal is an instance method so you need to call it as a member of self

dawn plover
#

the function with the 2 is the one Bing AI made

image.png
flat sorrel
dawn plover
#

It's now this

image.png
#

it gives me a loop of 1

flat sorrel
#

where is your own code?

#

please don't rely on the AI to generate code for you, especially when you're still learning

#

it can and will generate bad code

dawn plover
#

ik, I adjusted it

#

I'm still getting the hang of it and try not to use AI

flat sorrel
#

I think you should try using a debugger to go through the code line by line

#

it would help you understand the recursion that's going on

mortal sparrow
#

can you guys give some tips on implementing codes with deep logic, where a simple mistake can lead to days of debugging.. example: implementing a toy compiler/interpreter..

ive been coding for 3 years now, but im still, really not good.. still at beginner level.. i just want to know how you guys work with really complex or difficult algorithms, because its really hard.. i used to just copy algos in the internet, use it on my projects, if it works, i just let it be.. but right now i wanna start understanding how things work.. then i realize that to understand how 1 works.. u need to understand 0.9 and 0.8 and 0.7 etc etc.. i really dont know, please give me ur experiences on this thanks

flat sorrel
#

Prefer immutable objects over mutable ones to avoid accidentally breaking invariants elsewhere

fiery cosmos
#

hi

#

can someone explain to me how traversal 1 correction done, coz i have no idea how with this is i can verify

spiral sorrel
#

can someone answer ii the bottom question

image.png
worn mountain
ornate summit
#

hey i want to learn data structures and algorithms using python can anyone help me in this?

river hare
river hare
spiral sorrel
#

and breadth checks the whole level before going down so bredth would check e g r then go down

river hare
spiral sorrel
#

depth would check q, e n

#

then go back to e and then u?

spiral sorrel
#

or does it go back to q then down another route

#

but those are the only2 methods i can think of anyways it asks for 3

river hare
river hare
fiery cosmos
#

ıslak baba kralı

spiral sorrel
#

i have another questions lol

#

for this question

image.png
#

i got the big o as

#

O(n) for adding element

#

O(1) for removing an element

#

reasoning for adding element, you would have to go through the whole set to make sure ur not adding a duplicate

#

removing element is 1 since you dont have to go through the set and just remove it instantly

#

would that get me the full marks?

rare laurel
spiral sorrel
#

N is the length of the set

rare laurel
#

what do you mean "just N"?

#

O(n) to check if something is in a set?

spiral sorrel
#

Yeah

rare laurel
#

i think thats where your misconception comes from

#

its O(1) (unless hash collision)

spiral sorrel
#

I’d that wrong

#

Is that wrong

#

Wait

#

Is it actually just a constant

#

But doesn’t it take longer if the set is longer

#

So it’s not just constant

rare laurel
#

nope, thats the point of a set

#

what do you think dictionary key lookup time complexity is? same problem

spiral sorrel
#

Is that the same in every language

rare laurel
#

not really, no

spiral sorrel
#

This exam is kinda in c

#

Lol

#

I know I’m asking in a python server

#

It’s the only active computer science server

#

I’m in atleast

rare laurel
#

mh, its always an implementation detail, but usually sets are backed up by a hash function

#

in haskell there is no magical hash function for everything though (or, well, there is, but stdlib containers dont use it as its not really pure and not implemented for a lot of types), so it is backed up by comparison of elements and stored as a tree, so its log(n)

spiral sorrel
#

I mean I think the question is just a bad question

#

They don’t mention how it’s implemented

rare laurel
#

depends if there is previous context, e.g. if you implemented it in your classes

spiral sorrel
#

With an array? With a linked list? With a dictionary

#

No that’s literally the first question

#

For 4

#

3 was abt np and p problems