algos-and-data-structs

[haughty mountain]

how this is commonly represented is as a string like rwxr-x---

r = read
w = write
x = execute

in this case the owner can read, write and execute
group can read and execute
others can't do anything

[golden ravine]

so i need to turn 10010011 into 010010011 using the leading zero to actually make this work right?

[haughty mountain]

in binary this one would be
111101000
in octal
750

yeah, pad to 9 bits

octal is a very natural representation since it's 3 bits

[haughty mountain]

this one 223 is -w--w--wx which is a very weird permission setup

where user/group have less permissions

[golden ravine]

so it goes owner -group - others?

[haughty mountain]

yeah

[golden ravine]

that makes a lot more sense

thank you

[haughty mountain]

I think the usual terms are really
user, group, other

u g o

e.g. chmod uses that

[golden ravine]

oh i read that wrong idk where i got owner from

yeah you're right

[haughty mountain]

chmod u+x file is giving the execute permission to the owning user

[haughty mountain]

I said that before

but I should have said user

[golden ravine]

huge help man i was skimming through my lecture notes and had zero notes on this

[rancid idol]

initialize matrix with 0 values

for v in V:
for edge in Edge:
if v is in tuple edge then:
assign 2 to matrix[v][edge(1)]

How do I prove the correctness of the nested loop? Do I need two loop invariant? Is this a correct loop invariant to say that the invariant is that matrix has a valid row at row v? I am totally confused now.

[frigid sapphire]

Todays problem: Maximum Width Ramp

https://leetprep.io/problems/962

[empty yarrow]

what is the operator precedence of matrix multiplication with @

[stray fractal]

same as mul

[modern gulch]

https://docs.python.org/3/reference/expressions.html#operator-precedence is the full list.

[empty yarrow]

how did i not know about this list

[modern gulch]

You're one of the 10000

[empty yarrow]

lol

[kind jolt]

pls guys help, how can i solve tuis

i need to take the stars 🌟

[chilly ivy]

I need some help with some code design
I have permissions for RBAC Ghat are strings composed of 3 strings dot-separated in the following format entity.action.scope.
Actions may have different scopes, and the same thing applies to may have different actions

Ideally something like A.B.C and the str repr be "a.b.c" and A.B to be "a.b", A to be "a". You got the point

I want to have enum-like features so I can match A entity, or A.B entity action etc and iterate on all scope of A.B for example as well as all A actions etc

The hard requirement is that they need to be str as I cannot change the parameter type of fastapi internal code (list of str)

Any idea on how to achieve this/how would you do it??

[rancid idol]

for each v in V
    for each edge in Edge
         if v is in tuple edge then 
              assign 2 to matrix[v][edge(1)]```

 
can you prove a correctness of a for loop with induction or other methods or do you have to use invariance?

[narrow mica]

you can use getattr/setattr to dynamically access/set the value of an attribute using a str ig
example:

>>> from dataclasses import dataclass
>>> @dataclass
... class Engine:
...     fuel: str
...
>>> @dataclass
... class Car:
...     engine: Engine
...
>>> car = Car(Engine('gas'))
>>> car.engine.fuel
'gas'
>>> getattr(car, 'engine')
Engine(fuel='gas')
>>> getattr(getattr(car, 'engine'), 'fuel')
'gas'

[gritty gulch]

So I'm using the python Ezdxf package in a project to produce graphics for some nametags with a laser marking machine, and I've hit a wall:

I'm unable to create nice looking filled text and export it as a DXF file (with ezdxf).

I was able to do filled text by applying a hatch pattern and using the R12 export module, but that results in text that's too bold and the outline isn't antialiased when rendered. On the printed nametags the same problem is present.

Aside from that I manage smooth/antialiased text but only outlined/hollow, which I can't use.

-- I realize this is the wrong help channel but there's none that's more fitting imo, DXF is a file format and plenty of algos to parse it lol.

[cosmic sky]

Hi

[brave dagger]

alright so it's something like this. A node is discovered when it's traversed through and given a discovery time we increment it when another node is discovered when we backtrack to the same node it's given a finish time

[modern gulch]

Oh. "Visited" is probably a more correct term to use here.

[brave dagger]

ahh yeah

[modern gulch]

You could think of the algorithm as numbering each node... the root node is 1, the first child visited is 2, and so on.

[brave dagger]

Yeah I understand that

but there is one thing that confuses me

it says that if you backtrack to the root node which is 'a' in our case and there are no more nodes to visit the algo stops so I can easily get the discovery and finish time of nodes a b c d e but how does f get 11/12

[modern gulch]

It starts at a, and exhausts the directed graph from there... which gives you a,b,c,e,d... then it backtracks to a (starting point) at time 10

At that point, f is still unvisited... so its visited directly, which is what that arrow pointing at f represents.

and since all of f's links have been visited, it's done immediately (at t+1 = 12)

[brave dagger]

i see but in a directed graph if we have some node that you can't visit don't you skip that or something?

[modern gulch]

(originally, I assumed you were asking about DFS on binary trees... which is a more typical intro question... hence the confusion over discovery time)

[brave dagger]

my bad should have phrased it better

[modern gulch]

nah, just my assumption gone wrong 🙂

[modern gulch]

Just interpreting the diagram here: The algorithm they're showing starts at the first unvisited node, exhausts the graph, then starts again at the next unvisited node (in this case f).

[brave dagger]

Fair enough. Will have to ask my professor about it. I am curious on what will happen if more than 1 nodes remain unvisited by the time the traversal finishes

@modern gulch thank you though it helped alot.

[haughty mountain]

the number of unvisited nodes doesn't really matter

you will visit everything inside your strongly connected component (SCC), everything outside the SCC will be unvisited

[brave dagger]

I see

[haughty mountain]

actually, it's not really SCC in this case, ignore that part

SCC is a stronger requirement than just being reachable

[radiant rose]

Hi people, What are some good resources for Data Structures and Algorithms in Python

[hallow field]

Hey, a quick question: what would be the most efficient way to get all dict keys that meet a criteria?

Would an operation like the one below in any way compromise the dict's hashmap lookup speed properties?

# Find all key-value pairs where the value is greater than 20
filtered_dict = {key: value for key, value in my_dict.items() if value > 20}

print(filtered_dict)  # Output: {'b': 25, 'c': 30}

[vocal gorge]

There isn't really any other way. To find all values matching a condition, you must iterate over them all, which is O(n).

compromise the dict's hashmap lookup speed properties
there isn't any lookups happening here, just iteration

[hallow field]

Damn 😦

[vocal gorge]

If you had a condition on the keys, then you could in theory, instead of a (hashmap-based) dict, use a tree-based one. That'd have lookups only a bit slower than a hashmap (O(log n)), but it'd also be possible to quickly get all keys such that a<key<b, say. But your condition is on values, which aren't even necessarily unique or comparable, so there's not much to do here.

[hallow field]

Hmmm, thanks! Yes, in the example I provided i'm checking the values, but I could switch things up to condition the keys.
I'll check out the tree-based dict's, never heard of them before!

[hallow field]

Oh no. Unfortunately I'm looking for the most hashmap-like efficient way to track timestamps of elements. Looks like a tree-based dict won't work for me, as this would just be an unbalanced tree with each nested element containing the next single element and so on.

Not to mention I intend to occasionally remove the 'expired' timestamp and it's corresponding element.

Really hoped there was a way to do this at the O(1) speed 😦

[vocal gorge]

Hmm, perhaps have a key:timestamp dict and also a queue of (timestamp, key) pairs (always sorted by timestamp). Then you get fast lookups by key, and to do expiration, you popleft from queue while the first element is expired, and remove the elements you pop from the dict too.

[narrow mica]

tree-based dict won't work for me, as this would just be an unbalanced tree...
a naive implementation of a binary search tree would do that... (e.g. if you inserted elements in ascending order)
...but there exist self-balancing trees, which won't degenerate to a linked list

like: avl trees, treaps, red-black trees, splay trees... etc. should all keep a nice logarithmic time on average

[haughty mountain]

Looks like a tree-based dict won't work for me, as this would just be an unbalanced tree with each nested element containing the next single element and so on.
huh, why?
Not to mention I intend to occasionally remove the 'expired' timestamp and it's corresponding element.
you can do that

[haughty mountain]

from the operations we've been told about just a deque would work, was lookup by key even mentioned?

[hallow field]

thats completely valid option, but I was looking for something with a O(1) time complexity.
since i'll be checking for expired timestamps not every second, but rather just occasionally, I still might have multiple expired timestamps so I'll have to loop over them...

[hallow field]

Hm, thanks. I'll look that up

[hallow field]

yes. but again, if I use the timestamp as the key, I might have multiple expired ones, which forces me to loop over the dict keys, instead of employing the constant hashmap lookup speed

[haughty mountain]

why do you keep expired ones?

[hallow field]

I don't keep them. I'll be having a dict of timestamp keys with associated values. Instead of tracking if a timestamp as expired every second, I'll be checking if any of them did occasionlly, on demand. And until I check any number of them might or might not be expired

[haughty mountain]

ok, so drop expired timestamps during the lookup you're doing that would skip them

like

while deque and  deque[0].is_expired():
  deque.pop_front()

# proceed as usual now that the expired stuff is pruned

[hallow field]

exactly. but to find out which of them are expired I'll need to loop over them. and looping over them turns this into an O(n) operation, while i'm looking for a way to keep this O(1)

[haughty mountain]

you will only delete each expired thing once

yes, you might get some spike in the number of things that need dropping if you just keep waiting forever, but then subsequent operations will be cheap

i.e. the amortized performance is good

[lean walrus]

i posted an interesting math problem here: #esoteric-python message
i have no idea how to optimize the search algo further

[empty hound]

Hey guys should we also remove the dashes in words like "well-known", commas in numbers like "7,000", and colons in time like "7:30"?
Context: Natural Language Processing

[lean walrus]

if you have to - do it, if you don't - don't

[empty hound]

i don't get it

[zinc juniper]

Can anyone guide me, what's the best and fastest way to learn DSA with c++ ? any course recommendations? is it possible/practical to aim for CodeChef 1600 rating in just 45 days of learning DSA (Considering I'm giving 12-14 hours of my day to competitive programming, I'm pretty good in high school maths and I know C++, Python) (I'm preparing for IOI 2025)

[narrow mica]

why are you asking this here instead of... in the C++ server?
otherwise, CSES has a problem set of classics and a book; I also find myself referencing cp-algorithms a lot

[fiery remnant]

Hello! Any text based dsa resource suggestion please?

[patent junco]

what's wrong with this code?

var = []

thing = open("klencie.txt","w")
for i in thing.read():
    var += i.split(";",1)[0] + "/n"

thing.write(str(var))

it keeps cleaning file instead of stripping useless data and gives io.UnsupportedOperation: not readable on line 4…

[haughty mountain]

you're opening it in write mode and then reading

[patent junco]

i want both

RW

[haughty mountain]

rw can be messy

why not read first and then write?

[patent junco]

why importing twice?

it's same file anyway

[haughty mountain]

I would do something more like this, separating the read from the write

fname = "klencie.txt"

with open(fname) as thing:
  var = []
  for i in thing.read():
      var += i.split(";",1)[0] + "/n"

with open(fname, "w") as thing:
  thing.write(str(var))

[haughty mountain]

because you couple the reading and the writing, and it requires you to manually truncate (and maybe seek?) the file to make rw work

(also the code itself you have looks incorrect, but I kept it as is when showing the separate read/write)

[patent junco]

anyway. why on the earth it saved only first line and ignored semicolon ?!?!?!
new code:

fname = "klencie.txt"

with open(fname) as thing:
  var = []
  for i in thing.readline():
      var += i.split(";",1)[0]

with open(fname, "w") as thing:
  thing.write(''.join(var))

okay. done. this code good:

fname = "klencie.txt"

with open(fname) as thing:
  var = []
  for i in thing:
      var += i.split(";",1)[0] + "\n"

with open(fname, "w") as thing:
  thing.write(''.join(var))

[raven dagger]

quick question (although this may be more in mathland)

what are the chances a hash table of size n with k keys has a certain amount of key collisions for 1 particular hash

[modern gulch]

Are you asking what's the probability that any single hash will have a (one or many) collision?

[raven dagger]

uh

the probability any single hash will have a given number of collisions

[modern gulch]

Abstractly, ignoring chaining/etc, you're asking what's probability that with k keys in n slots, that a single new hash would collide with y preceding keys?

[raven dagger]

yeah

sorry for the long response

[modern gulch]

I'd guess you start with: given n bins and k balls, what's probability of one bin having y-1 balls? Then, what's probability of selecting that bin.

Or phrase it reverse: what's probability of a specific bin having y-1 balls after k trials?

(Which seems like a straightforward calculation)

[trail light]

does anyone know anything about implementing a CSPS algorithm

in python

tryna make a minesweeper solver

and i am SO LOST

[regal spoke]

CSPS?

[trail light]

constraints satisfaction problem

[regal spoke]

That's just CSP

I would set up an equation system with linear constraints, and Boolean variables.

Then I would solve using something like gurobi

[vocal gorge]

if using an existing solver rather than making your own, might as well use z3

because gurobi, uhhh

This package comes with a trial license that allows you to solve problems of limited size. As a student or staff member of an academic institution you qualify for a free, full product license. For more information, see:

[regal spoke]

If you are at a uni, getting gurobi is pretty easy

[vocal gorge]

i'm sure it's possible to get it whether or not you're at an uni, but it'd need to have some killer features for me to bother doing that instead of using z3 :p

[regal spoke]

From what I understand, it is one of the better solvers out there

But it has its fair share of issues

One funny quirk with gurobi is that even if you declare all variables to be in [0,1]

It might sometimes, only once in a blue moon, output a negative value.

[agile sundial]

average numerical method

[hard wyvern]

just want to ask, is it a good idea if I just leave the DSA stuff until I get onto it next year on my uni course? I feel itll be better if I allow uni to teach me and give me the appropriate resources for all the DSA stuff. Kinda struggling with going about it

[crude zenith]

Hi everyone! I want to share this video about problem solving for beginners I watched on youtube. Hope you like it.

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

[vestal tartan]

hi everyone

Havingh an issue with windows permissions

[stark breach]

Hi everyone, need some help.
Is there a book or free course where it teaches you how to start CP, how much time to solve problem, what approach to take, how to tackle problem?
Any answer might help. Thanks

[stiff quartz]

https://cses.fi/book/book.pdf but it's written in C++, not in Python

[floral nebula]

Hi

I have one question

Is diving deeper into data structures and algorithm worth it to make you a better programmer not to land in faang company

Or only having the basics and not grinding leetcode is enough

[stiff quartz]

Depends on what you wanna achieve as a programmer

Do you want to make blog type websites

Or do you want to work in a high frequency trading firm

[wheat oriole]

Guys help

[lean walrus]

I don't like the question

!rule exam

[halcyon plank]

Rules

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

[raven dagger]

no hank dont abbreviate competitive programming hankkkkkk

[thick granite]

comprog-?

[raven dagger]

eh too vague

[haughty mountain]

() is my favorite binary operator

but yeah, doesn't *, / and // have the same priority?

[narrow mica]

ig they didn't say you can't put multiple operators on the same level

[haughty mountain]

it just odd that they group + and -

but not the other ones that share priority

[narrow mica]

🤷‍♂️

[lean walrus]

it has the funniest priority

[haughty mountain]

priority: yes

[north mantle]

brothers, i haven't been able to find any project making ideas good. But i have seen williamlin's google kickstart VOD and i am interested in CP (Competitive Programming). Is this the way to go, or is this another stupid motive. Any tips eitherway

[narrow mica]

competitive programming is like the opposite of projects, in terms of what you learn
e.g. in projects you care about maintainability, in comp prog you just want to get it out asap

[north mantle]

oh hi there buddy

ah yeah, it's okay. i jsut want to find anything that is fun to code, until i am actually addicted to coding. because rn i do not want to ever open vsc becasue i can't even get a simple program right.

[narrow mica]

if comp prog is what gets you want to code, by all means
just be careful to not pick up bad practices

c++ for example, everyone be doing using namespace std; or #include <bits/stdc++.h>

[north mantle]

💀 . I don't use C++. But i remember after seeing william lin's linked video on a 8 hour C++ guide (Bucky) i deleted all C++ code 2 hours in.

namespace std is the goat though

[north mantle]

I mean that's the thing. I don't know. It's just another new thing, that looks very dopamine releasing when done by MIT students

[narrow mica]

if it looks fun then try it

[north mantle]

i am getting tortured. i can't even solve the first 2 problems on codeforces which seem to be very straightforward.

i submit the solution and i fail it on test 1

[narrow mica]

did you try the sample tests first?

[north mantle]

do you mean the things you copy and paste into your code and check if you get the output that's mentioned

VSCODE's terminal wouldn't let me to. I would copy and paste in the input, but it would have a weird error becasue the input is in different lines.

[narrow mica]

yes, but also on codeforces you can go to problemset > custom test (tiny button)

[vocal gorge]

given this message:

leetcode's "twosum" question requires u to use a class. I dont even know how classes work.
I suspect you messed up the template they gave you (e.g. removed the class), and so the judge doesn't understand how to run your code.

[north mantle]

That's probably the case.

[vocal gorge]

(also, I wouldn't actually say two-sum is an easy task to solve correctly; the O(n) solution is quite nonobvious if you haven't done competitive programming)

(though IIRC the conditions for that task on leetcode are such that a naive O(n^2) solution passes too)

[raven dagger]

excucse me what

[severe gale]

objects: list[tuple[bytes, Any]] = [...] # millions of objects (id, data)
seen = {}
for _id, _data in objects:
  if _id in seen:
    raise Exception(f"ID Collision: {_id}, {_data}, {seen[_id]}")
  seen[_id] = _data
print("No collisions")

Is there a more efficient way to do this? If there is a collision, I need the data from both objects.

[tranquil gorge]

!rule exam

[halcyon plank]

Rules

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

[prime siren]

If I want to store a list of names, uids and prices in ram, should I use a 3d array? Or something else?

[haughty mountain]

If there is a collision, I need the data from both objects.
kinda seems like the structure you want is really dict[bytes, list[Any]]

[severe gale]

What? That's not for an exam, man. I'm trying to make my code run faster

[severe gale]

No, I just need to find any existing collision, not all. I can terminate early as soon as one is found but I need the data. I mentioned that to prevent suggestions like len(objects) == len(set(ids))

[inner imp]

Does anyone have any recommendations on how to improve a cv cascade modal? I'm trying to make it count the amount of kills a player gets in valorant and it's not working super well. I've got 85 images for both positive and negative but like 180 positive instances.

[haughty mountain]

there won't be any solution more efficient than this if your input is a list of key value pairs

the more efficient thing would be to try to avoid ending up with such a list and have a dict instead

[severe gale]

My actual situation is even worse, I have a list of values and need to "generate" the "keys" from the values before checking for duplicates

But alright, I kinda suspected that there wouldn't be any more efficient solution (making this a terrible exam question)

Thanks for the feedback!

[regal spoke]

There isn't much reason to have seen be a dictionary. Just make seen be a set, and linear search through objects to find what id it collided with.

Something else you might want to consider is that make the id be an int instead of a string

[haughty mountain]

right, you could use a set and do two lookups on a collision

though I kinda suspect that one would want to build a dict out of the data as soon as possible

rather than handle a list of key-value pairs

[north mantle]

my friend thought me a method that uses a hashmap

[toxic hare]

ive been working on trying to render squares using numpy and PIL

print("a")
list1 = [ [(255,i%255,i%255),(100+random.randint(0,100)-50,100+random.randint(0,100)-50,100,100)] for i in range(1000)  ]
rendimg = Image.new('RGB', size=(siz,siz))
render_surface = np.zeros((siz, siz, 3), dtype=np.uint8)  # Assuming RGB format
for x in list1:
    col = x[0]
    xpos = x[1][0]
    ypos = x[1][1]
    xwidth = x[1][2]
    ywidth = x[1][3]
    x_range = np.arange(xpos, xpos + xwidth)
    y_range = np.arange(ypos, ypos + ywidth)
    valid_x = (x_range >= 0) & (x_range < siz)
    valid_y = (y_range >= 0) & (y_range < siz)    
    x_range = x_range[valid_x]
    y_range = y_range[valid_y]
    ly = len(y_range)
    x_indices = [  [i]*ly for i in x_range ]
    y_indices = [  [i]*ly for i in y_range ]
    render_surface[y_range, x_indices] = col
render_surface = render_surface.reshape(-1, render_surface.shape[-1])
render_surface = render_surface.tolist()
render_surface = list(map(tuple, render_surface))
    
rendimg.putdata(render_surface)
data = rendimg.tobytes()
pygame_surface = pygame.image.fromstring(data, (siz,siz), "RGB")
surface.blit(pygame_surface, (0, 0))

any feedback or suggestions?

[severe gale]

That's a good point

[weak cradle]

can somebody help me with a cnn problem im trying to do the epoch training but some how im getting this Epoch 6/6 2/2 [==============================] - 0s 188ms/step - loss: 0.3888 - accuracy: 0.8333 - val_loss: 0.2368 - val_accuracy: 0.8333 49/Unknown - 2s 46ms/step - loss: 0.2622 - accuracy: 0.8299

[severe gale]

Just figured out that this is the bottleneck oof

[weak cradle]

i cant figure it out why its dooing that

[mint ruin]

could someone check out my yfinanace post on python help

[agile sundial]

i need an efficient way to find the strings that a given substring is in. the list words is fixed and is about 300k length

found = []
for w in words:
  if my_substring in w:
    found.append(w)

[hybrid umbra]

anyone here doing cp am just stucked with a Uber OA question can anyone help me

[narrow mica]

I assume you want to do better than O(sum(len(word))? otherwise you can just smack a KMP at it or something

[agile sundial]

yes, ideally faster than this naive implementation i showed

[vocal gorge]

I found this answer but I don't understand it. 🥴
https://cs.stackexchange.com/a/90932

(how does having a suffix tree for this string let one do infix search?..)

[narrow mica]

I mean kmp is faster, yours is O(n * m) while KMP is O(n + m) (where m denotes len(substr))

but maybe we can do better cause words is fixed?

[narrow mica]

this seems like it'd be better if you have multiple substrings that you're looking for in all of these words
otherwise if you're just doing 1 pass of this, building the suffix tree would also take O(n)

[agile sundial]

iirc, postgres can do this..

[narrow mica]

I tried looking for how dbs might do this and came across this ig

[agile sundial]

yeah

i think i'll just generate all trigrams and keep the ones that work

[patent junco]

someone know anything better than this https://flowrun.io/scratchpad for prototyping algos? ui hard to manage, too much clicking, no sidebar and generally everything too big while convas too small…
might be downloadable as long as will work offline on linux…
BTW: i know how to code but before i need to visualize it to myself cause otherwise i make too much bugs…

[patent junco]

?

[lean walrus]

draw it on paper/in paint?

[regal spoke]

Do you only have 1 substring?

Or are there many substrings too?

[agile sundial]

many substrings

[haughty mountain]

trigrams for initial filtering is a very general approach for this kind of things, though I've seen employed most commonly with file searching

[agile sundial]

ye

[regal spoke]

Do you want to identify the matches, or just count them?

[haughty mountain]

I think it was finding all the strings with a match

[agile sundial]

identify would be better, but counting technically would work. since i have a limited set of substrings i just brute forced them all. only took like 7 seconds

[regal spoke]

Here is what I would do. Concatenate all words into 1 string by something like '$.join(words)'. Create a suffix array for the big string. For each letter in the big string, mark which word it is part of.

For each substring, you can "binary search" for the interval in the suffix array that matches with your substring.
The matched words corresponds to the set of different marks on that interval. This corresponds to counting unique elements in an interval, which is a famous problem solvable in O((n + q) log n) with a segment tree.

Let n = sum len(word). Time complexity is O(n) to build the suffix array, and O(len(substring) * log(n)) to "binary search" the suffix array. Finally O(log(n)) to count the matches or O(log n * #matches) to find the matches.

[haughty mountain]

I think the question is, do you care about found or just something like len(found)?

btw, what are you actually trying to do?

[agile sundial]

i'm trying to make bomb party. basically, it prompts you with a 2 or 3 letter substring, and you give a word that matches. my question was about generating prompts that have a certain number of words that it matches. but since there are only so many 2 or 3 letter substrings, i just generated them all

[regal spoke]

Wait I was thinking wrong. Let me edit.
Okey fixed it now

[haughty mountain]

tbh, just precomputing a list of indices for every bi and trigram probably solves your problem in a pretty sensible way

I'm guessing that won't blow up too bad memory-wise

[regal spoke]

My proposed solution takes linear memory

[haughty mountain]

right, but it adds a lot of complexity

you might get by with a much simpler solution

[regal spoke]

Well time complexity wise it is nice

But it is complicated, ye

There is a somewhat simple sqrt solution using hashes

Suppose all substrings have the same length

Then you can easily solve the problem in linear time by making precomputations using rolling hashes + moving window

Insight to get sqrt: Turns out that the number of different lengths of substrings is at most sqrt(sum len(subtrings)) since to make the substrings have different size, you need longer and longer substrings

[haughty mountain]

so yeah, it's not that bad for the random wordlist I had lying around

$ wc -l ~/wordlist
500921 ~/wordlist

$ python grams.py < ~/wordlist
Sizes:
  Unique bigrams: 658
  Unique trigrams: 9851
Total indices stored:
  Bigrams: 3640914
  Trigrams: 3192440

(granted, it's python so sizes will blow up by a decent factor)

[regal spoke]

https://open.kattis.com/problems/proteinsyntes here is a cute problem using this sqrt trick

[regal spoke]

If you are actually using real words, you can just generate the hashes of every substring of every word since the words are usually pretty short

(i.e. you can precompute the answer for every single possible substring)

[narrow mica]

there's also the ac automaton which also gives you a very linear time of O(sum(len(word)) + sum(len(substr)) + #matches) or something

[rustic hazel]

I'm not sure this is the correct channel for this, but anyway

What could be causing

with open('key.txt', rb) as file:
    a = file.read().decode('latin-1')
    b = somefunction(a)
    file.close() 

To make the whole programme not work unless I put a time.sleep(0.1) on the second line (so where the read is and move the read down one line)

Like whenever I launch the code it doesn't work

But if I debug it it works

And if I put the time.sleep() it works

Adding some context :
This is all in a try - except sequence, that is in turn In a main() function that has threading in it later down the line

And main() gets run if name == main

[slender sandal]

Why not

with open("key.txt", encoding="latin-1") as file:
    a = file.read()
b = somefunction(a)
```?

"doesn't work" is a terrible description for what's wrong by the way

[stiff quartz]

What's the message you get

[rustic hazel]

That worked 😭

[rustic hazel]

No message at all

Just blank

But it's fixed now

[slender sandal]

I think it's because you had a NameError doing open('key.txt', rb) (rb should have been in quotes)

I'm worried you're handling exceptions wrong

The best practice is to be specific about which exception you handle and how

Something like

try:
    ...
except:
    pass
```doesn't cut it. It's dangerous even

[rustic hazel]

Wait what !_0

I'm doing exactly that

You mean like I should put which exception

After except:

Yeah that's probably true

[regal spoke]

The entire point of with open is that it automatically closes the file at the exit of the with.

Don't close the file manually like that

That said, I don't think calling file.close() will cause an issue

[valid adder]

Guys quick question, just to refresh my memory, elements added to a dictionary/ data that is surrounded by curly braces will automatically weed out duplicate values?

[rancid idol]

    if (tree1 == nullptr && tree2 == nullptr)
        return true;
    if (tree1 == nullptr || tree2 == nullptr)
        return false;
    return (tree1->data == tree2->data) &&
           areSame(tree1->left, tree2->left) &&
           areSame(tree1->right, tree2->right);
}

What is the time complexity of this? I am thinking 2n where n is the number of nodes and 2 because 2 calls for n nodes.

[modern gulch]

One interesting thing to do is measure it, and test your theory. Plot the number of areSame invocations for varying n.

[solid moss]

Problem: Trapping Rain Water
Given an array of non-negative integers representing the height of bars, compute how much water can be trapped after raining.

Input:

• An array height where height[i] represents the height of the i-th bar.
  Output:
• An integer representing the total amount of water that can be trapped.
  Example:

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output:
6

The water can be trapped in the valleys between the heights, and the total amount trapped is 6.

Requirements:

• Aim for a solution with O(n) time complexity and O(1) space complexity.
• Water can be trapped between the heights based on the minimum of the tallest bars to the left and right of each bar.

[haughty mountain]

maybe consider the subtly different problem of solving this when you know the maximum is at the end

if you can solve that, you can also solve the original problem

[rancid idol]

I did and that is how I came to the conclusion that there were 2n+1 calls for different n's.

[toxic hare]

Rate my leetcode submission

[stiff quartz]

happened to me loads recently

It's kinda suspicious

either they upgraded their servers or they changed the way they time programs

or it's a bug

[narrow mica]

or leetcode times are simply not to be trusted

[toxic hare]

lmao
thats actually not the issue
i actually DID get a really fast result

the funny part about the submission is when you take a look at how i solved the problem lmaooo

[stiff quartz]

you didn't need to do that though, the most naive solution I can think of gets it fast as well (faster actually if you trust leetcode times)

just don't trust leetcode timings (or memory usage for that matter) unless you're at 100 ms and everyone else is at 2000 ms or the other way around

[regal spoke]

0 ms sounds like a bug

Not trusting numbers with variations is one thing. But here it looks like there is straight up a bug on leetcode's side.

[stiff quartz]

yeah got loads of 0 ms recently

[haughty mountain]

worst case you traverse both trees, each has n nodes

I guess it's more like O(min(n, m)) where n and m are the tree sizes

[regal spoke]

https://leetcode.com/discuss/general-discussion/4800799/How-to-get-runtime-0-ms-(in-certain-problems)/ 0ms normally on leetcode seems to be from abusing the judge system

Can find bug posts about 0ms from at least 1 year ago https://www.reddit.com/r/leetcode/comments/15tnaee/is_leetcode_giving_way_too_many_0ms_runtime_for/

https://leetcode.com/problems/binary-string-with-substrings-representing-1-to-n/solutions/271969/something-wrong-why-the-runtime-is-0-ms/

[stiff quartz]

We’re horrible - poor guy was just happy about their performance and we are saying nah not good just average nothing to brag about

[regal spoke]

Actually the issue goes back a long time

[vocal gorge]

nah I've gotten 0ms without trying at all or doing anything weird. their measurements are just really bad.

[regal spoke]

Because of a bug?

[vocal gorge]

Not sure if this is a bug per se or intended behaviour, but I've had submissions which, if submitted multiple times, got either 0ms or 10-30 ms

[stiff quartz]

There was a huge (stupid) thread on the French Reddit on people trying to reason why a solution was like 5% faster in Java than C++

Until they tried reproducing it locally and no one could

[haughty mountain]

I wonder if for stuff that expects an int you can return a subclass of int as the response, or maybe even just a class implementing __index__

[regal spoke]

You probably could

[stiff quartz]

I wonder if the duck is a reference to @regal spoke

[toxic hare]

built in bit_count()
smh lmao

[rancid idol]

yes but worst case will automatically be the largest tree nodes but it will be the same given 3 or 4 nodes tree instead of binary tree right. Btw if we strictly say that a tree cannot have more than 3 or 4 children of course.

[haughty mountain]

the smaller of the trees

[rancid idol]

But is my observation correst for the other cases?

[haughty mountain]

which observation exactly?

the number of children doesn't really matter at all to the analysis

[rancid idol]

If we have max 4 children for each node then it is still the same reasoning right, I definitely believe so but just want to double check

[haughty mountain]

you could reason the same in such a case

but the better reasoning is just about the number of nodes

you will visit the nodes at most once

[rancid idol]

not sure I understand you totally

[haughty mountain]

all the function does is traverse the graphs and compare stuff

is any node visited more than once?

no

so the number of calls total is limited by the number of nodes

[stiff quartz]

@regal spoke @toxic hare they (supposedly) did recently improve the timing measurements (https://leetcode.com/discuss/general-discussion/5926441/0ms-with-python/)

[toxic hare]

yall are missing the point of my code

its fast because i load all the answers in and then just index the list for the answer
lmaoo

[stiff quartz]

Loading all the answers in the first place still takes O(nlogn) time

[haughty mountain]

0ms still seems like a bug

or they have utter garbage test cases that are trivially small and they bucket their runtimes and round them down aggressively

[stiff quartz]

There are several posts asking about it and the staff always says it’s normal so it’s probably just small test cases

If I re run that same code I sometimes get 1 ms

Or 2 ms

🤷‍♂️

Doesn’t matter much I guess

[steep sundial]

explain this to me no

>>> b
array([[7, 4, 7],
       [8, 5, 8],
       [9, 6, 9]])
>>> z
array([7, 8, 9])
>>> type(z)
<class 'numpy.ndarray'>
>>> b[:,0] is z
False
>>> b=np.array([[1, 4, 7],
...        [2, 5, 8],
...        [3, 6, 9]])
>>> b
array([[1, 4, 7],
       [2, 5, 8],
       [3, 6, 9]])
>>> z = b[:, 0]
>>> z
array([1, 2, 3])
>>> b[:, 0] is z
False
>>> b[:, 0] = [7, 8, 9]
>>> b
array([[7, 4, 7],
       [8, 5, 8],
       [9, 6, 9]])
>>> z
array([7, 8, 9])
>>> b[:, 0] is z
False

How is z changing

[jolly mortar]

z is a view of b

[opal oriole]

The z variable is not a copy of the first column of b, it's a reference to it, a slice.

[jolly mortar]

in your b[:, 0] is z checks the b[:, 0] creates a new view

[merry pewter]

I read the book of runestone academy mentioned by @old rover in #algos-and-data-structs message
I find it really good and easy
Would recommend 👍
And thanks @old rover for suggesting :)

[slender sandal]

Names refer to objects and objects may also refer to objects.
b[:, 0] creates an array object that references each item in b[:, 0]. Assigning the name z to b[:, 0] means z refers to the new array object created by b[:, 0] which references those items, and has the consequence of seeing the same changes that apply on those items in memory, which is why z, and maybe more obviously also b[:, 0], referred to array objects with new values once you changed what they were. You could have instead done it through z[:] and see the same items changing values when inspecting b or more narrowly b[:, 0].
Note the first pieces of detail in all of this: "Names refer to objects. b[:, 0] creates an array object". b[:, 0] always creates a new, different object, and this part is less relevant but, with references to those specific items referenced by b or more narrowly by b[:, 0]. z refers to an array object that was created with b[:, 0], and that array object cannot be the same array object as other array objects created with b[:, 0] at other times.
You can think of it like this:

foo = [1, 2, 3]
bar = foo[:1]. # bar refers to a new list object that references the first item in the list referenced by foo
bar is foo[:1]. # False, because bar refers to its own object and foo[:1] creates a new list object that references the first item referenced by the list referenced by foo, a new list object like the one referenced by bar, but they are their own list objects

[meager geyser]

get a job bro

[half owl]

in what course are you introduced to the Ackermann function? i see this in an old iteration of our cs 101 course, but they said there r future courses that talk about its inverse funciton

[narrow mica]

not a course specifically
but the amortized time complexity of a DSU with both path compression and union by rank is the inverse ackermann

applying only path compression or union by rank gets you amortized log n instead, iirc

as for when the ackermann function itself might be introduced... ig when recursion is taught? like as an exercise to calculate a recursive function or something

[lament quarry]

I got an interesting prime coding challenge:

Let d(p) be the number of digits that the prime p has.

Let g(p) denote the repeated composition of d() on p if and only if d yields a prime each time.

What are the proportion of primes or number of primes that have the property of g(p)=1?

Say, for 10^9 or something.

One example:

Let p = 23, then d(23)=2, which is prime. d(2)=1, which is what we're after. Then, g(23)=1, and we say that 23 has this special property.

[grand chasm]

Guys I really need help with this homework

please help me I'm really stuck on this

someone please?

[haughty mountain]

10^9 is a kinda silly limit

the answer for that limit is just

(num 1, 2, 3, 5, 7 digit primes)/(num primes)
```isn't it?

!e let p(n) = 10^n/ln(10^n) then the answer should be roughly

import math

def p(n):
  return 10**n/math.log(10**n)


print((p(3) + p(5) - p(4) + p(7) - p(6))/p(9))

[halcyon plank]

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

0.011517642857142858

[haughty mountain]

mainly brought way down because 8 and 9 digit primes are bad

if the limit was 10**7 it would be more like 0.9

[lament quarry]

Try 10**12 then

[lament quarry]

You need to argue more about that one

[haughty mountain]

why?

for the limit you originally gave everything reduces to 1 digit after one usage of d

so (ignoring the 1 digit numbers) it reduces to just which numbers reach 2, 3, 5, 7 in one application of d

which is 2, 3, 5, 7 digit primes

[haughty mountain]

that would just add 11 digit primes 11 -> 2 -> 1

actually, I guess this means that up to like 10**1000 nothing super interesting happens, we know all primes <1000 reduce via 2 or 3

if I interpret things correcrly the first thing that works "unexpectedly" is actually is the first 1009 digit prime

the first instance of d(n) being prime and d(d(n)) being not prime

[lament quarry]

No, it doesn't, a prime which has more than 10 digits will not break down like that

But hm, interesting point on the threshold I suggested

[haughty mountain]

how so?

so the original point was with the 10**9 limit

but the pattern "the number of primes with a prime number of digits" should hold up to ~10**1009

[lament quarry]

Yeah, which is why I said interesting point ^^

[lament quarry]

Hmm, even with the iterated compositions?

[haughty mountain]

for 10-999 digits it reduces to 2 or 3, which we know reduces to 1

seems my approximation is pretty close
approximation in blue, real values in red

plotting approx/exact tends to 1 pretty quickly after the initial messiness

sadly I can't easily compute really far out where the function has interesting behavior

this is how my approximation looks like up to 10**9

taking log of the x axis

the first drop should be around when you get to 6 digit numbers

going up to 10^8, x-log plot

fits nicely

drops at start of 6 digits and 8 digits

[lament quarry]

That's very interesting!

[lament quarry]

Maybe a range between some values would work here?

[lament quarry]

Huh, ngl, did not expect those spikes there

[haughty mountain]

it's expected

you get a ton on ones that work in a row, and then loads that fail

[lament quarry]

Spikes around 10^k?

[haughty mountain]

it's not around every 10^k

[lament quarry]

k=5,7 atleast

Perhaps it continues for k=11,13?

[haughty mountain]

it does

then 17

[lament quarry]

So, 10^k, where k is a prime number bigger than or equal to 5?

[haughty mountain]

you could call 10^3 a peak as well I guess

there is a drop after it

when you get to 4 digits

[lament quarry]

Kinda cool, ngl

You said that it is expected, but why so?

[haughty mountain]

but yeah, it will do this thing for every prime length up to 1009

which as said is the first kinda non-trivial case

[lament quarry]

And 1009 is also prime

But it doesn't spike there?

[haughty mountain]

but 1009 -> 4

so it fails on the second call to d

that's the first time that happens

[lament quarry]

As 1009 is the first 4 digit prime

[haughty mountain]

yes

[lament quarry]

All primes before that has the property

Which makes sense

[haughty mountain]

it's not that weird

             |  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17  |
reduces to 1 |  x  x  x  -  x  -  x  -  -  -  x  -  x  -  -  -  x  |
             +-----------------------------------------------------+
               at start
             all primes   rise  rise          ...
                +++++++  -  +  -  +  -------  +  -  +  -------  +
                      drop   drop   long drop

you get long runs, e.g. at 8 9 10 where everything fails

so you have a long dip there

[lament quarry]

🤔

[haughty mountain]

you reach 4 digits and drop, then drop at 6, long drop at 8 up until 17 starts, drop at 18, ...

but yeah, this is way beyond what you could feasibly verify, but I'm pretty confident this pattern is correct

(up until 10**1009)

[wide oriole]

Hello
Should i watch any dsa course before starting to solve leetcode problems

[stiff quartz]

Not sure that's the right channel but I've been trying since this morning to get something that works well and it's not going great.
The problem (pretty sure it's NP-hard) is to find two dominating sets (https://en.wikipedia.org/wiki/Dominating_set#:~:text=In graph theory%2C a dominating,smallest dominating set for G.) of a graph and minimize score_to_minimize = len(dom_set_1) + len(dom_set_2) + len(dom_set_1.intersection(dom_set_2))) / |V|.
I've been doing beam search (adding nodes to dom_set_1 or dom_set_2 till they are dominating) with that heuristic:

def heuristic(state, n):
   # big is bad
   return (2*n - len(state.dominated_1) - len(state.dominated_2)) / n + score(state.dom_set_1, state.dom_set_2, n)

But it's kind of terrible (for a 50 nodes 50 edges graph even with a beam width of 100, my final score_to_minimize is > 1 and getting 1 is trivial (get one dominating set dom_set_1, use V \ dom_set_1 as the other and the score is 1). My code is here https://pastebin.com/99PjM8zb (dominated_1 and dominated_2 are dictionary with key a vertex and value the number of times they are being covered, I could just use a set but I don't think it'd change much)

Just looking for some tips on beam search because I don't think I'm going about it the wrong way but I clearly missed something

[haughty mountain]

did you check the part that mentions a log approximation factor algorithm?

[stiff quartz]

This is to find one (small) dominated set?

[haughty mountain]

oh you have a different problem I guess, finding two dominating sets that are ideally small and independent

[stiff quartz]

Yeah exactly

[night laurel]

Can someone write a code for simulating this problem. It seems to me like a tree kind markov chain.
Initial state (root node) has 25W,50B balls then node 2 can have 3 possible states
We draw 2 black balls --S1 : 25W,49B
We draw 1 B, 1 W balls--S2 : 25W,49B
We draw 2 White balls--S3 : 23W,51B

Now these 3 states at node 2 will further divide onto 3 other ststes and node 3

and so on ... 1 -- 3---9---27---81 .... like this the states at each node will be.

Sorry for being off-topic

[haughty mountain]

you could use dynamic programming to compute the number of ways to end up in whatever combination of white/black balls

err

you would need to track the expected counts, but same idea

something akin to

from functools import cache

@cache
def whites(b: int, w: int):
  if b == 1 and w == 0:
    return 0
  if b == 0 and w == 1:
    return 1

  p_bb = ...
  p_bw = ...
  p_ww = ...
  return p_bb*f(b-1, w) + p_bw*f(b-1, w) + p_ww*f(b+1, w-1)

which should give you the expected number of whites

[half owl]

is lst += [ ord ( c )] in O(1) TC? or O(n)

def text2Unicode ( text ):
  lst = []
  for c in text :
    lst += [ ord ( c )]
  return lst

[agile sundial]

amortized constant. but why are you not appending

[silk field]

hello i am new member

[night laurel]

Thanks

[silk field]

    if n < 0:
        return 
    elif n == 0:
        return 1
    else:
        return n * factorial(n + 1)  # Intentional mistake: using n + 1 instead of n - 1


try:
    number = 5
    result = factorial(number)
    print(f"The factorial of {number} is: {result}")
except RecursionError as e:
    print(f"A recursion error occurred: {e}")```

can you help me with this code, it shows a error in it

[stiff quartz]

Isn't the error literally pointed out by the comment

[hushed nova]

[fair helm]

hello guys , i have a question , in a sorting algorithm , if the dataset is tiny or the list is almost sorted we can use insertion_sort right ? so my question is , how do we determine its almost sorted ? what definy it ? 50% of the list ? 60 % of the list almost sorted ? at what point we could use insertion sort ? 😄 just in case here my current inplementation of my insertion sort in a heap sort ``` python
import math

def heapSort(a):
"""
Performs heap sort on the given list.

Args:
    a: The list to be sorted.
"""

END = len(a)
# Build the initial heap
for k in range(int(math.floor(END/2)) - 1, -1, -1):
    heapify(a, END, k)

# Extract elements one by one
for k in range(END-1, 0, -1):
    swap(a, 0, k)
    heapify(a, k, 0)

def swap(a, i, j):
"""
Swaps elements at indices i and j in list a.

Args:
    a: The list.
    i: The first index.
    j: The second index.
"""
a[i], a[j] = a[j], a[i]

def heapify(a,iEnd,iRoot):
    iL = 2*iRoot + 1
    iR = 2*iRoot + 2
    if iR < iEnd:
        if (a[iRoot] >= a[iL] and a[iRoot] >= a[iR]):
            return

        else:
            if(a[iL] > a[iR]):
                j = iL
            else: 
                j = iR
            swap(a, iRoot, j)
            heapify(a, iEnd, j)
    elif iL < iEnd:
        if (a[iRoot] >= a[iL]):
            return
        if almost_done(a[iL:iEnd+1]) and iEnd - iL <= 50:
            swap(a, iRoot, iL)
            insertion_sort(a, iL, iEnd)
               
        else:
            swap(a, iRoot, iL)
            heapify(a,iEnd,iL)

    else: 
        return 
def almost_done(liste):
    """
    Vérifie si au moins 50% des éléments d'une liste sont dans le bon ordre.

    Args:
        liste: La liste à vérifier.

    Returns:
        True si au moins 50% des éléments sont dans le bon ordre, False sinon.
    """

    longueur = len(liste)
    elements_dans_lordre = 0
    for i in range(1, longueur):
        if liste[i] >= liste[i-1]:
            elements_dans_lordre += 1

    return elements_dans_lordre / longueur >= 0.5

def insertion_sort(arr, low, high):
    for i in range(low + 1, high + 1):
        key = arr[i]
        j = i - 1
        while j >= low and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j+1] = key ```

[agile sundial]

you should pick a small constant number, like 50. if you pick something like "50% of the list", you'll run into n^2 performance

[fair helm]

ok si i just delet my almost done function and replace it by a constant

[dense finch]

im currently writing a neural network and have a bug in my backpropagation function. i find it very difficult to debug it because its just a bunch of nested vectors and loops. are there methods to debug such things efficient?

[regal spoke]

It needs to be a lot higher than 50% for insert sort to be useful.

A lot lot higher

The main situation you'd use insert sort is when n is small, since it has a really good constant factor if implemented correctly

But for large n it is practially never used

[fair helm]

small like 20 or 1000 bcs 1000 is tiny in front of 100k

[regal spoke]

small n is probably up to like 100

[fair helm]

okk thx

[regal spoke]

Note however, that this implementation is slow

[fair helm]

i am no't good in implementation optimisation :<

binary maybe ?

def binary_insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        left, right = 0, i - 1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] < key:  

                left = mid + 1
            else:
                right = mid - 1
        for j in range(i - 1, left - 1, -1):
            arr[j + 1] = arr[j]
        arr[left] = key    ```

[regal spoke]

from bisect import bisect_right as binary_search
def insert_sort(A):
    B = []
    for a in A:
        B.insert(binary_search(B, a), a)
    return B

Was talking about this one

This one is practically really fast

[fair helm]

ah i basically never done import for that

[narrow mica]

what about bisect.insort?

[regal spoke]

Oh there is a built in function for what I'm doing

But ye

[narrow mica]

usually calling existing functions would be faster than implement by hand
less overhead

[regal spoke]

Its doable to implement the binary search yourself

[fair helm]

yeah but by hand mean becoming less stoopid and i really need to become less stoopid xD

[fair helm]

yeah thx

bcs the thing is i maybe gonna have to do this in js too

[regal spoke]

# implementation of bisect.bisect_right
def binary_search(A, x):
    L = 0
    R = len(A)
    while L < R:
        mid = (L + R) // 2
        if A[mid] <= x:
            L = mid + 1
        else:
            R = mid
    return L

def insert_sort(A):
    B = []
    for a in A:
        B.insert(binary_search(B, a), a)
    return B

Here is the full thing implemented from scratch

[fair helm]

hoooo thx

[regal spoke]

!e

def binary_search(A, x):
    L = 0
    R = len(A)
    while L < R:
        mid = (L + R) // 2
        if A[mid] <= x:
            L = mid + 1
        else:
            R = mid
    return L

def insertion_sort_binary_search(A):
    B = []
    for a in A:
        B.insert(binary_search(B, a), a)
    return B

def insertion_sort(A):
    arr = list(A)
    for i in range(1, len(A)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j+1] = key 

import time
import random

A = [random.randint(1, 10**4) for _ in range(5*10**3)]

start = time.time()
sorted(A)
print("Built in sort:", time.time() - start)

start = time.time()
insertion_sort_binary_search(A)
print("insertion_sort_binary_search:", time.time() - start)

start = time.time()
insertion_sort(A)
print("insertion_sort:", time.time() - start)

[halcyon plank]

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

001 | Built in sort: 0.0005309581756591797
002 | insertion_sort_binary_search: 0.011200904846191406
003 | insertion_sort: 0.6603119373321533

[regal spoke]

@fair helm Here is a benchmark with n = 5000

As you can see, the insertion_sort_binary_search version is a lot faster

[fair helm]

yeah binary search is log(n) right ?

[regal spoke]

The binary search part is log n

But the insert is O(n)

[fair helm]

yeah the part

[regal spoke]

However, the insert is really fast since it is a low level built in operation

[fair helm]

ok i see thx

so this one + my heap + quick sort than i dont know how to build and then i will try to make a introsort xD

[jolly mortar]

damn i got hacked and the hack was based on a template by pajenegod

i am gradually learning why no one uses python 😩

[fair helm]

lol

def quick_sort_iterative_dynamic(array):
    """
    Performs a hybrid quick sort and insertion sort on the given array.

    Args:
        array: The array to be sorted.

    This function implements an iterative version of quick sort 
   
    """

    l = len(array)
    if l <= 100:
        # For small arrays, use insertion sort
        insert_sort(array)

    stack = []
    stack.append((0, l - 1))
    while stack:
        low, high = stack.pop()
        if low < high:
            # Calculate the average value of the subarray
            sum_ = sum(array[low:high+1])
            count = high - low + 1
            avg = sum_ / count

            # Find the element closest to the average as the pivot
            pivot_index = low
            min_diff = abs(array[pivot_index] - avg)
            for i in range(low + 1, high + 1):
                diff = abs(array[i] - avg)
                if diff < min_diff:
                    pivot_index = i
                    min_diff = diff

            # Move the pivot to the beginning of the subarray
            array[pivot_index], array[low] = array[low], array[pivot_index]
            pivot = array[low]

            # Partition the subarray around the pivot
            i = low + 1
            for j in range(low + 1, high + 1):
                if array[j] <= pivot:
                    array[i], array[j] = array[j], array[i]
                    i += 1

            # Place the pivot in its final position
            array[i - 1], array[low] = array[low], array[i - 1]
            pi = i - 1

            # Push the smaller subarrays onto the stack
            if pi - 1 > low:
                stack.append((low, pi - 1))
            if pi + 1 < high:
                stack.append((pi + 1, high)) ``` do you think a more simple way for searching pivot should be better ? or this way of searching a pivot is fine ?

dont know where to put the heap for the moment

[narrow mica]

the objectively best pivot is the median, but then you'd need O(n) to look for it so the constants go way up
a simple approximation is to use the median of 3 instead, i.e. the median of array[0], array[-1], array[middle]

[fair helm]

yeah bcs my brain was thinking than choosing a pivot close to the average value can be effective for uniformly distributed data

[narrow mica]

in that case the median and the arithmetic mean would be close, yes
but then for something like [1, 1, 1, 1, 1, 10000] it'd not be so great
and you're using O(n) to sum to find the average anyway, at that point just look for the actual median

[fair helm]

ok i see

so now i tested it against heap and

first batch is when in a list of 10k you have only between 1 and 10 number , second batch you have a diversity of between 1 and 1000000 (same len of list)

so i find interesting than heap is better for list with a lot of identical number and quicksort is better for list with unique number

[fair helm]

re guys, so i got this ```python
def median_of_three(arr, low, mid, high):
a, b, c = arr[low], arr[mid], arr[high]
if a <= b <= c or c <= b <= a:
return mid
elif b <= a <= c or c <= a <= b:
return low
else:
return high

def Quick_sort(array):
if len(array) <= 100:
insert_sort(array)
return
def _quick_sort(arr, low, high):
while low < high:
if high - low < 10:
insertion_sort(arr, low, high)
break
mid = (low + high) // 2
pivot_index = median_of_three(arr, low, mid, high)
arr[low], arr[pivot_index] = arr[pivot_index], arr[low]
pivot = arr[low]

        i = low + 1
        for j in range(low + 1, high + 1):
            if arr[j] <= pivot:
                arr[i], arr[j] = arr[j], arr[i]
                i += 1

        arr[i - 1], arr[low] = arr[low], arr[i - 1]
        pi = i - 1

        if pi - low < high - pi:
            _quick_sort(arr, low, pi - 1)
            low = pi + 1
        else:
            _quick_sort(arr, pi + 1, high)
            high = pi - 1

_quick_sort(array, 0, len(array) - 1) ```

def insertion_sort(arr, low, high):
    for i in range(low + 1, high + 1):
        key = arr[i]
        j = i - 1
        while j >= low and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key ```

so you wonder why i still use insertion sort for the case in quick sort , i tried to implement the binary thing but i don't know why the results where a bit worse than the function insertion_sort

i still use binary in the "inser_sort" in the start

typically if i tried to insertion in a binary search like ```python
def binary_search(arr, key, low, high):
while low <= high:
mid = (low + high) // 2
if arr[mid] == key:
return mid + 1
elif arr[mid] < key:
low = mid + 1
else:
high = mid - 1
return low

def insertion_sort(arr, low, high):
for i in range(low + 1, high + 1):
key = arr[i]
pos = binary_search(arr, key, low, i - 1)
for j in range(i, pos, -1):
arr[j] = arr[j - 1]
arr[pos] = key ``` my time was going from a average of 0.0249 to 0.0289

and if i tried to use directly insert_sort the time was jumping to 1 .++ seconds so i think its the best i can do

[fair helm]

ok guys after (in quicksort function)```py
arr[i - 1], arr[low] = arr[low], arr[i - 1]
pi = i - 1

        ``` i added ```py

iteration_count[0] += high - low
if iteration_count[0] > len(arr) * (len(arr).bit_length() - 1):
heap_sort(arr)
return and between the start of the function and the tail def _quick_sort(arr, low, high): i addedpy
L = len(array)
if L <= 0:
return
if L <= 100:
insert_sort(array)
return
iteration_count = [0]

my heap is ```py
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2

if l < n and arr[l] > arr[largest]:
    largest = l

if r < n and arr[r] > arr[largest]:
    largest = r

if largest != i:
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, n, largest)

def heap_sort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
if n - i <= 10:
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0) ```

[fair helm]

and now this case is solved , when to much number identical quick sort become to be more than n log n then it switch to heap sort alright , feel free to use this one if you want it work nice :D

[real musk]

Can anyone explain this pattern? :c

[fair helm]

maybe i will say shit who is maybe sure at 99% but maybe its the garbage collector ? when he free its dropping cache limit and all dat

[real musk]

Horizontal scale is n, vertical is time

I mean I also have a solid guess, but I'm curious about your opinions

[ionic flame]

how do i learn this topic i know python and most of its basics and advanced topics so where do i start from?

[real musk]

Which topic are you talking about?

[fair helm]

you mean algorithmic ?

learn time complexity then space complexity (maybe learn that later the space ), then try to do simple searching algorithm like binary search for finding a specific value in a list its a good start

[haughty mountain]

could be some transition between different algorithms

granted, these are probably too big numbers for that

[ionic flame]

algorithms and data structures i like problem solving and saw questions like linked lists or array some sorta shi like that on leetcode so how do i get started like i dont understand there are many tutorials and hardly any in python

[haughty mountain]

yeah, karatsuba cutoff is at like 70 2^30 base digits, way earlier

[fair helm]

maybe jump in the soop on codingame.com and try to solve level1 problem

[ionic flame]

and im asking this because i dont wanna regret that i learnt the wrong way and shouldve learnt to think like thag instead

[ionic flame]

oh

[real musk]

My guess for the patter would be is how computers calculate powers. like for us x^27 would be x*x*x*...*x 27 times, which is a linear time complexity, meanwhile for the computer is is

x2 = x * x
x4 = x2 * x2
x8 = x4 * x4
x16 = x8 * x8
x24 = x16 * x8
x26 = x24 * x2
x27 = x26 * x

And how we know which multiplications to make is hidden in the number's binary form, like 27 is 11011 meaning we go up to 16 then multiply by x8 than x2 than x1, so it is a logarithmic time complexity because the number of operations depends on the length of the numbers binary form. In my opinion the pattern is because the closer we get to a power of 2, the more operations we do since the number of 1's in the binary representation increases. As we hit a power of 2, we get a number that is a 1 followed by a bunch of zeros, therefore it drops the number of multiplications. Maybe....

[haughty mountain]

actually...maybe it's just powers of two in the exponent where the dips are

[fair helm]

and when you have solved a puzzle you can see the answer of other people

[haughty mountain]

if it does some exponentiation by squaring those will be the suddenly cheaper ones

[haughty mountain]

btw, this might get interesting if you continue this like 10x longer

when you start to hit cache sizes

[real musk]

it already took a few seconds to plot, but let's start it than lol

[haughty mountain]

you could skip values

like take every 10th or 100th power or something

[stray fractal]

whatever this means

[halcyon plank]

Objects/longobject.c lines 5058 to 5063

/* Left-to-right binary exponentiation (HAC Algorithm 14.79) */
/* https://cacr.uwaterloo.ca/hac/about/chap14.pdf            */

/* Find the first significant exponent bit. Search right to left
 * because we're primarily trying to cut overhead for small powers.
 */```

[haughty mountain]

yeah, this is exponentiation by squaring

[stray fractal]

if the value is greater than or equal to 2**1800 (for 30-bit digit implementations of cpython) it uses another thing

[haughty mountain]

maybe we are too far removed from low level stuff to see super clear issues from cache misses

[real musk]

you can still see the pattern if you know what to look for but much less visual

[haughty mountain]

I'm guessing the impl will be something akin to

def mypow(base, power):
  res = 1
  x = base
  while power:
    if power&1:
      res *= x
    x **= 2
    power >>= 1
  return res

[real musk]

let's time it with the other... lol

[haughty mountain]

this one does one more square than needed, which might hurt a bit

oh wait

x should start as base

fixed

[real musk]

now that's crazy

blue is first one orange is yours

[fair helm]

what is the goal , its pow benchmark ? (keep in mind iam stoopid pls)

[haughty mountain]

this one will probably be a bit better

def mypow(base, power):
  res = 1
  x = base
  while True:
    if power&1:
      res *= x
    power >>= 1
    if power == 0:
      break
    x **= 2
  return res

of course, totally untested code

I'm half surprised I seemingly didn't write some syntax error in the first one

[stray fractal]

i have no idea how to translate it

[real musk]

lol you basically went under the official implementation

green is new

[haughty mountain]

yeah, the extra square hurts

err, wrong reply

[real musk]

so basically if you optimize anything now you might as well write it in assembly and become rich lol

[haughty mountain]

this thing should look similar

[stray fractal]

def smallpow(a, b):
    z = a
    bit = 1 << b.bit_length() - 2
    while bit:
        z *= z
        if b & bit:
            z *= a
        bit >>= 1
    return z

that's how i interpret it

[haughty mountain]

I'm a bit surprised they are going in that direction

oh nvm

[stray fractal]

... because we're primarily trying to cut overhead for small powers.

[haughty mountain]

they are not

[stray fractal]

it says that

wait

[haughty mountain]

I'm shifting my power down and doing a check on the smallest bit

[stray fractal]

oh..

i get it now

[haughty mountain]

they are keeping their power constant and shifting a bit up that they check against

same effect

[real musk]

Also are there any built-ins where the time function is something interesting?

any other

[haughty mountain]

comparing multiplication of int vs multiplication of decimal.Decimal might be interesting

for whatever reason someone implemented asymptotically faster versions for Decimal

so it should win out for large enough numbers

[real musk]

Also, for 4th power doing it manually is faster, curious where is the point where exponentiation optimizations become faster

[modern gulch]

Maybe some memory / gc cost (not sure why given that code, but could explain a cost at higher N)

[fallow agate]

from math import floor

def counting_change(amount, coins):
    if amount == 0:
        return 1
    if amount < 0:
        return 0
    
    no_of_ways = 0
    for coin in coins:
        for x in range(0, floor(amount/coin)+1):
            no_of_ways += counting_change(amount-coin*x, coins)
    
    return no_of_ways

print(counting_change(4, [1, 2, 3])) # -> 4

This problem is about how many ways we can make the given amount using the coins infinitly. on the left most branch of the decision tree, it runs infinitly, any idea to stop that?

[silk field]

    # Base cases
    if amount == 0:
        return 1  # One way to make zero amount: using no coins
    if amount < 0 or len(coins) == 0:
        return 0  # No way to make change if the amount is negative or no coins are left

    # Recursive case: choose to include the current coin or not
    # Include the first coin or skip it and move to the next
    return counting_change(amount - coins[0], coins) + counting_change(amount, coins[1:])

# Example usage
print(counting_change(4, [1, 2, 3]))```

i have fixed it you can use it now

in the original code

for x in range(0, floor(amount/coin) + 1)

loop was unnecessary. This loop essentially duplicated efforts, causing the function to over-count combinations.
By iterating over x, you were making recursive calls multiple times for the same coin in different quantities, leading to incorrect counting.

The original logic allowed the same combinations to be counted in multiple permutations because you were considering all coins in each recursive step. For example, using coin 2 after coin 1 and vice versa would result in counting the same combinations multiple times.

To address these issues, the revised solution eliminates the nested loop and properly handles the counting

[narrow mica]

did you fix it or did you ask chatgpt
no offense, but the way both you write your code and explanations seem copy pasted from an LLM
and please don't copy-paste responses from LLMs

[narrow mica]

what's the definition of your recursive function, and based on that, what would be the recurrence relation?
in words, not in code

[silk field]

A recursive function is defined as a function that calls itself in order to solve a problem by breaking it down into smaller, more manageable subproblems. This definition can be articulated through several key components

[narrow mica]

!rule 10

[halcyon plank]

Rules

10. Do not copy and paste answers from ChatGPT or similar AI tools.

[silk field]

Oh! one more point i didn't copy it

[narrow mica]

cool, how bout you don't do that

[dense star]

hi

in one use react/next js

any*

[silk field]

hey! can you give me questions to make a quiz in python

[dense star]

like what

[silk field]

some quiz questions

[narrow mica]

I don't
but also, why are you asking this in a python server?

[silk field]

because i have to make a quiz in python

[dense star]

i think it's normal python can be used in backend so front end is a cummon thing

[fallow agate]

i got it.

def counting_change(amount, coins):
  return _counting_change(amount, coins, 0, {})

def _counting_change(amount, coins, i, memo):
    key = (amount, i)
    if key in memo:
        return memo[key]

    if amount == 0:
        return 1

    if amount < 0:
        return 0
    
    if i == len(coins):
        return 0
    
    coin = coins[i]

    no_of_ways = 0
    for qty in range(0, amount+1):
        remainder = amount - (qty * coin)
        no_of_ways += _counting_change(remainder, coins, i+1, memo)
    
    memo[key] = no_of_ways
    return memo[key]

print(counting_change(4, [1, 2, 3])) # -> 4

[dense star]

im creating a cards game in front end at the mooment

[silk field]

ooo! cool

[narrow mica]

sure, if you have python backend related problems you can ask here (maybe #web-development in this channel instead of algos and data structs)
if it's more related to react/next js maybe it's better suited for a javascript server

[dense star]

i know just the web chat in sleep rightnow

nayway did u try before creating game logic with only recursion

not loops

[fair helm]

hell ,o people

liddle question ! we know than the worst case scenario of quick sort is quadratic , but i need a value than i didn't found , at what % of homogeneity quick sort start to really lost performance

and just in case i have made a liddle visualiser in pygame for showing me when the algo decide to switch to heapsort (without erasing the data already done) AND ! only in the given partition ! like this i erase the problem with the pivot ! and then if the next partition have a % of homogeneity low then it will no't switch to heap or whatever you want i can do merge sort maybe it can be better , bcs for the moment i set it for 80%

[fair bloom]

how do you guys visualize recursion in ur head ??

[fair helm]

try to imagine than its a loop and you writing what is going on inside and then when you call the recursion you write what do you want to happened if it was a loop who go to the next iteration of course generally people start to the max and go to 0 and put a condition if 0 return for not having infinite recursion

[lean walrus]

just as any other function call

[fair helm]

and if your interested i have made a video of it running

[fair helm]

liddle quesdion , i have this python def is_unbalanced(low, high, pi,valueofHomogeneity): left_size = pi - low right_size = high - pi # Ajuster le seuil selon les besoins return max(left_size, right_size) > valueofHomogeneity * min(left_size, right_size) it was designed to check if the partitioning of the array during a quicksort is unbalanced. Specifically, it compared the sizes of the left and right partitions created by the pivot index pi. If one partition was significantly larger than the other, it would return True, indicating an unbalanced partition. ,what i want to know is if this is a good method for switching or no't , bcs in my algo its working fine i guess ? but i don't know if the function can be better

[bold helm]

Hey

[wide oriole]

Hey

[fallow agate]

given this graph, you need to find whether there is a path between f & k.
In this problem, which algo will gives fast results? DFS / BFS ?

graph = {
  'f': ['g', 'i'],
  'g': ['h'],
  'h': [],
  'i': ['g', 'k'],
  'j': ['i'],
  'k': []
}

has_path(graph, 'f', 'k') # True

[fair helm]

dfs: research in depth , bfs: research per level usecase: dfs : cycle detection , components, bfs: the shortest path in unweighted graph time complexity for the two : O(v+e) space : O(v)

dfs consume less memory

and if you want the best path use bfs

[narrow mica]

which algo will gives fast results? DFS / BFS?
depends on the graph

[fair helm]

a deep graph dfs a fat graph bfs

[fair helm]

F wrong screen

so we can see than without insertion and for unique value the 5 pivots quicksort explode everyone

[haughty mountain]

not generally

depends on the graph

[fair helm]

yeah if he is fat or long

now i will try with the insertion optimisation with a specified treshold of 60 for only the dual one , i don't know how to put it in the 5 pivots partition since its radically different from the other one

[fair helm]

youknow what i will do it another day with proper test time to eat

[fair helm]

re guys so here is a version than i have found on google in a study : ```python
def QuickSort2Pivot(list):
n = len(list)
if n <= 1:
return list
elif n == 2:
return sorted(list)

pivot1, pivot2 = sorted([list.pop(0), list.pop(0)])
a = []
b = []
c = []
for element in list:
    if element < pivot1:
        a.append(element)
    elif pivot1 <= element < pivot2:
        b.append(element)
    else:
        c.append(element)
    
return QuickSort5Pivot(a) + [pivot1] + QuickSort5Pivot(b) + [pivot2] +QuickSort5Pivot(c) ``` this version  is really easy to  extend the only drawback is that you need to do list = QuickSort2Pivot(list)  but its more fast than the version of quicksort2pivot than i have  with the partition logic    ,if you dont like the 'sorted' you can use whatever sort you want  , you can even do a 5 pivot really easily

5 pivot example : ```py
def QuickSort5Pivot(list):
n = len(list)
if n <= 1:
return list
elif n >= 2 and n <= 4:
return sorted(list)

pivot1, pivot2, pivot3, pivot4, pivot5 = sorted([list.pop(0), list.pop(0),list.pop(0), list.pop(0), list.pop(0)])
a = []
b = []
c = []
d = []
e = []
f = []
for element in list:
    if element < pivot1:
        a.append(element)
    elif pivot1 <= element < pivot2:
        b.append(element)
    elif pivot2 <= element < pivot3:
        c.append(element)
    elif pivot3 <= element < pivot4:
        d.append(element)
    elif pivot4 <= element < pivot5:
        e.append(element)
    else:
        f.append(element)
return QuickSort5Pivot(a) + [pivot1] + QuickSort5Pivot(b) + [pivot2] +QuickSort5Pivot(c) + [pivot3] + QuickSort5Pivot(d) + [pivot4] + QuickSort5Pivot(e) + [pivot5]+ QuickSort5Pivot(f) ```

[regal spoke]

elif n >= 2 and n <= 2:?

[fair helm]

ah yeah it's n == 2

[sleek flint]

Magnificent!

[errant umbra]

function dijkstra(graph, start) {
  let dists = {};
  let queue = [];
  let processed = new Set();

  // Setting up distances for each node
  for (let node in graph) {
    if (node == start) {
      dists[node] = 0;
    } else {
      dists[node] = Infinity;
    }
    queue.push(node);
  }

  while (queue.length > 0) {
    queue.sort(function (a, b) {
      return dists[a] - dists[b];
    });
    let node = queue.shift();

    if (processed.has(node)) {
      continue;
    }

    if (dists[node] === Infinity) {
      break;
    }

    processed.add(node);

    for ([target, weight] of graph[node]) {
      if (processed.has(target)) {
        continue;
      }

      let pathCost = dists[node] + weight;
      if (pathCost < dists[target]) {
        dists[target] = pathCost;
      }
    } 
  }

  return dists;
}

module.exports = dijkstra;

am i right in saying that the time complexity of this dijkstra implementation is V^2logV
?
My for loop that is setting initial distances to nodes runs |V|$times. My while loop will also run |V| times.

The most expensive operation inside my while loop is the standard sort() function, which is generally |VlogV|. My while loop is |V*VlogV| which equals |V^2logV|.

Also, for each vertex that is processed, all adjacent edges are checked. This is |E| time.

I now have |V| + |V^2logV| + |E| ∈ O(|V^2logV|)

[stiff quartz]

Why do you sort if you just pop the minimum

Just pop the minimum in O(V) instead of sorting first if you really don’t want to use a priority queue

[twin void]

It seems learning algo without being mathematically inclined is not a good option

[brazen python]

how do I go about grouping together similar strings?
the strings are names of articles (same articles written by different publishers), I dont want to go to crazy about this, was hoping to find a solution with just a line or two of code.

seems like levenshtein distance would be one of the ideal ways, thoughts?

[haughty mountain]

levenshtein distance is a sensible way yes

though it's not super obvious how you would want to do the grouping

[brazen python]

similar names? I dont want to use any fancy ML, so ig it wont be context aware which is fine

hope that makes sense

[haughty mountain]

I know what you're trying to accomplish, I just meant it's not obvious how you would define such groups

like
if A is similar to B and B is similar to C,
is A also similar to C?

questions like "what titles are similar to title A?" is easier to define

[narrow mica]

see #python-discussion message

[clever forge]

What is the best website to get good with algorithms?

I am very bad at them

like VERY bad

(Euler was too complicated for me after some point 💀 )

[brazen python]

yes it would be much easier if I also had a list of main-articles/categories that I can throw each title in (kind of like buckets)

I guess I will just run a similarity on each title which would be O(n ^ 2)

[fallow agate]

hi, i am getting 4 always, even with different test cases. looks like something is wrong.

def semesters_required(num_courses, prereqs):
    graph = _build_graph(prereqs)

    visited = set()
    longest = float("-inf")
    for course in graph:
        curr_longest = _explore_dfs(graph, num_courses, course, 1, visited)
        longest = max(curr_longest, longest)
    return longest

def _build_graph(prereqs):
    graph = {}
    for a, b in prereqs:
        if a in graph:
            graph[a].append(b)
        else:
            graph[a] = [b]
        if b in graph:
            continue
        else:
            graph[b] = []
    return graph

def  _explore_dfs(graph, num_courses, course, no_of_courses_taken, visited):
    # Base case
    if graph[course] == []:
        return 1
    if course in visited:
        return no_of_courses_taken
    else:
        visited.add(course)
        no_of_courses_taken += 1

    # Recursive calls
    neighbor_courses = set()
    for neighbor in graph[course]:
        neighbor_courses.add( _explore_dfs(graph, num_courses, course, no_of_courses_taken, visited)) 
    max_neighbor_courses = max(neighbor_courses)
    no_of_courses_taken += max_neighbor_courses

    return no_of_courses_taken

num_courses = 7
prereqs = [
  (4, 3),
  (3, 2),
  (2, 1),
  (1, 0),
  (5, 2),
  (5, 6),
]
print(semesters_required(num_courses, prereqs)) # -> 5

[solemn quarry]

hey guys - I am learning to code and have attempted a leetcode roman numeral problem. Essentially you need to take any roman numeral and convert it to numbers. The leetcode link is here - https://leetcode.com/problems/roman-to-integer/description/.

I wrote a solution but i keep getting my worst nightmare ( index out of range ) - it works with MCMXCIV but anything else it comes out with an index error

# Taking a roman numeral and turning it into an integer

# Create Arrays 

rSingle = ['I','V','X','L','C','D','M']
rValue = [1,5,10,50,100,500,1000]

rCombo = ['IV','IX','XL','XC','CD','CM']
rComboValue = [4,9,40,90,400,900]

allRomanNumerals = []

def analyse(numeral):
    
    index = 0 # starting point
    tally = 0 # tally when counting through all the roman elements
    
    while index < len(numeral): # This function iterates through the roman numeral and separates all possible elements into a list called allRomanNumerals

        x = str(numeral[index]) # looks at the index value
        y = str(numeral[1+index]) # looks at the next index value to see if it is a subtraction scneario
        combo = x + y # joins x and y to see if there is a combo
        
        if combo in rCombo:
            allRomanNumerals.append(combo)
            index += 2
            
        else:
            allRomanNumerals.append(x)
            index+=1
            
    for element in allRomanNumerals:

        if element in rSingle:
            tally += rValue[rSingle.index(element)]
        
        if element in rCombo:
            tally += rComboValue[rCombo.index(element)]
    
    return print(tally)

analyse('MCMXCIV')
analyse('III')                                 

[obsidian bluff]

import webbrowser as wb
import mouse
import os
from PIL import ImageGrab
import schedule
import pytesseract
import time
import pyautogui

target_color1 = (229, 1, 5) #red
target_color2 = (0, 119, 192) #bleu
target_color3 = (85, 85, 85) #grey


def autovote():
    wb.open("https://www.pactify.fr/votes")
    time.sleep(4)

    while True:
        screen = ImageGrab.grab()
        color_at_xy = screen.getpixel((987, 307))


        if color_at_xy == target_color3:
            screenshot = pyautogui.screenshot(region=(914, 297, 141, 27))
            screenshot = screenshot.convert('L')
            text = pytesseract.image_to_string(screenshot)
            text1 = text[9:-1]
            print(text)
            print(text1)
            hours = 0
            minutes = 0
            for i in range(len(text1) + 1):
                if text1[i] == 'h':
                    try:
                        hours = int(text1[i - 1])
                    except ValueError:
                        print("Error parsing hours")
                    print("hours =", hours)
                if text1[i] == 'm':
                    try:
                        if text1[i - 2].isdigit():
                                minutes = int(text1[i - 2:i])
                        else:
                            minutes = int(text1[i - 1])
                    except ValueError:
                        print("Error parsing minutes")
                    print("minutes =", minutes)



            break


        time.sleep(1)


    check_color(987, 307, target_color1, 0)

    mouse.move(987, 307, 50)
    mouse.click('left')
    time.sleep(15)

    check_color(917, 121, target_color2, 0)

    mouse.move(917, 121, 50)
    mouse.click('left')
    time.sleep(17)

    mouse.move(160, 23, 50)
    mouse.click('left')
    time.sleep(1)

    check_color(987, 307, target_color1, 0)


    mouse.move(975, 307, 50)
    mouse.click('left')
    mouse.click('left')
    time.sleep(0.5)
    os.system("taskkill /im chrome.exe")

def check_color(x, y, target_color, attempt_count):


    screen = ImageGrab.grab()
    color_at_xy = screen.getpixel((x, y))

    if color_at_xy != target_color:
        attempt_count += 1

        if attempt_count >= 100:
            print("Exceeded 100 attempts. Restarting autovote.")
            os.system("taskkill /im chrome.exe")
            run()
            return
        time.sleep(1)
        check_color(x, y, target_color, attempt_count)


def run():
    schedule.every(190).minutes.do(autovote())
    while True:
        schedule.run_pending()
        time.sleep(1)

run()

can anyone help with this program ?

im tryna automate a python program that can vote itself

[modern gulch]

Best to open a help thread: #❓｜how-to-get-help

[modern gulch]

Also, a help thread would be good here #❓｜how-to-get-help ... and share the exact error/traceback you're seeing

[haughty mountain]

why are you recursing into course rather than neighbor?

!e overall, I would try some simpler recursion

def semesters_required(num_courses, prereqs):
    graph = _build_graph(prereqs)

    cache = {}
    return max(
        _explore_dfs(graph, course, cache)
        for course in graph
    )

def _build_graph(prereqs):
    graph = {}
    for a, b in prereqs:
        if a not in graph:
            graph[a] = []
        if b not in graph:
            graph[b] = []
        graph[a].append(b)
    return graph

def _explore_dfs(graph, course, cache):
    if course not in cache:
        if graph[course] == []:
            return 1

        cache[course] = 1 + max(
            _explore_dfs(graph, neighbor, cache)
            for neighbor in graph[course]
        )
    return cache[course]

num_courses = 7
prereqs = [
  (4, 3),
  (3, 2),
  (2, 1),
  (1, 0),
  (5, 2),
  (5, 6),
]
print(semesters_required(num_courses, prereqs)) # -> 5

[halcyon plank]

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

5

[pure crest]

Someone should try to write this as a pure function, I got close but I can't figure it out:
https://leetcode.com/problems/binary-tree-maximum-path-sum/description/

my best attempt at a pure function (no global mutable state):

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode]):
            if node is None:
                return (float('-inf'), float('-inf'), float('-inf'))

            left, left_split, left_single = dfs(node.left)
            right, right_split, right_single = dfs(node.right)

            no_split = max(node.val + max(left, right), node.val)
            split = max(left_split, right_split, left + right + node.val)
            single = max(node.val, left_single, right_single)

            return (no_split, split, single)

        no_split, split, single = dfs(root)
        return max(no_split, split, single)

passes on NeetCode but not Leetcode

[fallow agate]

previously, i was trying same max path problem like this with the help of set. but set wont work in this courses problem.
we must store the recursive calls results into dictionary & then utilize them. why is this difference?

def longest_path(graph):
    visited = set()
    longest = float("-inf")
    for node in graph:
        curr_longest = _explore_dfs(graph, node, 0, visited)
        longest = max(curr_longest, longest)
    return longest 

def  _explore_dfs(graph, node, distance, visited):
    # Base case
    if graph[node] == []:
        return 0 
    if node in visited:
        return distance
    else:
        visited.add(node)
        distance = 1

    # Recursive calls
    neighbor_distances = set()
    for neighbor in graph[node]:
        neighbor_distances.add(_explore_dfs(graph, neighbor, distance, visited)) 
    max_distance_neighbor = max(neighbor_distances)
    distance += max_distance_neighbor

    return distance

graph = {
  'a': ['c', 'b'],
  'b': ['c'],
  'c': []
}
print(longest_path(graph)) # -> 2

[haughty mountain]

fwiw, both having the distance as an argument and having it returned strikes me as weird

[fallow agate]

where?

[haughty mountain]

in your function

[fallow agate]

you are taking about _explore_dfs(graph, neighbor, distance, visited)?

[haughty mountain]

yes, having distance both passed as an argument and being returned seems weird to me

why do you need to pass the distance as an argument?

[fallow agate]

now? pls let me know for further questions.

# If node is in visited, then we won't explore that path, as that path is already visited.
# Will just return the distance whatever is calculated as of now.
if node in visited:
    return distance
else:
# If node is not visisted, then will have to consider that node into the distance. so, distance = 1
    visited.add(node)
    distance = 1

# Recursive calls:
# Recursive calls are initiated on all neighbours
# max of the returned value is choosed
# Thats is added to distance
neighbor_distances = set()
for neighbor in graph[node]:
    neighbor_distances.add(_explore_dfs(graph, neighbor, distance, visited)) 
max_distance_neighbor = max(neighbor_distances)
distance += max_distance_neighbor

return distance

[haughty mountain]

I don't get the logic you're trying to write

[fallow agate]

😦 how would you do, instead?
and also, pls tell me why passing distance seems weired?

[haughty mountain]

idk how to phrase why it's weird, it's just not something you see much

like, passing the arguments is kinda pushing a value forward, while returning is pulling a value back, doing both for the same thing (distance in this case) feels very odd

[haughty mountain]

won't distance be 1 in every call anyway?

[fallow agate]

like, passing the arguments is kinda pushing a value forward, while returning is pulling a value back, doing both for the same thing (distance in this case) feels very odd

this is what we do in recursive calls? we push the same argument & pull the same argument in recursive fn.

[fallow agate]

yes

[haughty mountain]

so why pass it at all?

[fallow agate]

any way, let's not waste time on something feeling weired.
You would have done like this?

def longest_path(graph):
    visited = {}
    longest = float("-inf")
    for node in graph:
        curr_longest = _explore_dfs(graph, node, visited)
        longest = max(curr_longest, longest)
    return longest 

def  _explore_dfs(graph, node, visited):
    # Base case
    if graph[node] == []:
        return 0 
    if node in visited:
        return visited[node]
    else:
        visited[node] = 0

    # Recursive calls
    neighbor_distances = set()
    for neighbor in graph[node]:
        neighbor_distances.add(_explore_dfs(graph, neighbor, visited)) 
    visited[node] = 1 + max(neighbor_distances)

    return visited[node]

graph = {
  'a': ['c', 'b'],
  'b': ['c'],
  'c': []
}
print(longest_path(graph)) # -> 2

[haughty mountain]

what are you even trying to calculate, the diameter of a tree?

[haughty mountain]

the kinda brute force way would be to just do independent dfs calls from every single node

but you're not doing them independently, you are keeping the visited thing between calls

[fallow agate]

yes, in visited dict

[haughty mountain]

pretty sure that's just incorrect

even within a single dfs I'm pretty sure it's incorrect

e,g. say you start at A and start →B→C

A-->B-->C
|   ^
+>D-+

you find a path with length 2, when you then try the other path through D you get stopped by visited

you never find the length 3 path if you happen to do this order in the dfs

[thick granite]

that's if visited was a set

[haughty mountain]

why would that change anything?

[thick granite]

visited as a dict could work as a cache, no?

[haughty mountain]

the issue is more that dfs is not a good fit for this problem at all

like, you can do it, but then you need to throw out visited and literally just try every path

which is super wasteful

[narrow mica]

doesn't change much
with dfs, you just need to brute force every path

standard way is (again) topological sort + dynamic programming

[haughty mountain]

yeah, topological sort is the proper solution here

one approach I kinda like for toposort (which can be used to solve this problem as you go) is what I call "trimming leaves"

you start by finding all the leaves in the DAG, and you start removing them, and adding the new leaves that appear to your list of leaves

keep going until the graph is down to one node

[narrow mica]

think that's called kahn's algorithm, if you want a name

[haughty mountain]

if you during this process start by assigning 1 to all leaves, and then update the parent's value to be max(parent, leaf+1) when you trim a leaf, then the value of the last node is the length of the longest path

[haughty mountain]

right, that name sounds familiar

I've never really bothered putting a name to it because it just makes such intuitive sense 🥴

[fallow agate]

but, i tried many test cases like below & all worked. there is a big one in last. If the path is getting skipped like you said, atleast one test case shoud catch it?

graph = {
  'a': ['c', 'b'],
  'b': ['c'],
  'c': []
}

longest_path(graph) # -> 2

graph = {
  'a': ['c', 'b'],
  'b': ['c'],
  'c': [],
  'q': ['r'],
  'r': ['s', 'u', 't'],
  's': ['t'],
  't': ['u'],
  'u': []
}

longest_path(graph) # -> 4

graph = {
  'h': ['i', 'j', 'k'],
  'g': ['h'],
  'i': [],
  'j': [],
  'k': [],
  'x': ['y'],
  'y': []
}

longest_path(graph) # -> 2

graph = {
  'a': ['b'],
  'b': ['c'],
  'c': [],
  'e': ['f'],
  'f': ['g'],
  'g': ['h'],
  'h': []
}

longest_path(graph) # -> 3

graph = {
  'a': ['b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o'],
  'b': ['c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o'],
  'c': ['d', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o'],
  'd': ['e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o'],
  'e': ['f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o'],
  'f': ['g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't'],
  'g': ['h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't'],
  'h': ['i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't'],
  'i': ['j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't'],
  'j': ['k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w'],
  'k': ['l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w'],
  'l': ['m', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y'],
  'm': ['n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x'],
  'n': ['o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'],
  'o': ['p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x'],
  'p': ['q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y'],
  'q': ['r', 's', 't', 'u', 'v', 'w', 'x', 'y'],
  'r': ['s', 't', 'u', 'v', 'w', 'x', 'y', 'z'],
  's': ['t', 'u', 'v', 'w', 'x', 'y', 'z'],
  't': ['u', 'v', 'w', 'x', 'y', 'z'],
  'u': ['v', 'w', 'x', 'y', 'z'],
  'v': ['w', 'x', 'y', 'z'],
  'w': ['x', 'y', 'z'],
  'x': ['y', 'z'],
  'y': ['z'],
  'z': []
}

longest_path(graph) # -> 25

[haughty mountain]

what about the case I mentioned?

graph = {
  'a': ['b', 'd'],
  'b': ['c'],
  'd': ['b'],
}

[fallow agate]

working!

[fallow agate]

i think the reason why it is working is:
e,g. say you start at A and start →B→C. you find a path with length 2, when you then try the other path through D you get stopped by visited B

A-->B-->C
|   ^
|   |
+>D-+

When you find the B node which is already visited --> we are not only skipping the path, but doing below.

    if node in visited:
        return visited[node]

and this return value is getting added to the current path lenght uptoB here.

    # Recursive calls
    neighbor_distances = set()
    for neighbor in graph[node]:
        neighbor_distances.add(_explore_dfs(graph, neighbor, visited)) 
    visited[node] = 1 + max(neighbor_distances)

That way, it's equal to visiting the path A --> D --> B --> C

any way; if you have time, pls post the triming leafs way that you mentioned.

[narrow mica]

quick glance, and this might be fine cause it's just top down dp
as opposed to toposort then bottom up

[thick granite]

i had an idea once

• place all nodes at index 0
• iterate over all the nodes; if a node points to another, move that other node up one index
• repeat until no more nodes move up
  is there a name for this sort of algo?

also is it a kind of toposort-

[narrow mica]

what do these steps mean more concretely

[fallow agate]

isn't it bottom up DP?
the values into the dictionary are collected when the recursion call hits the leaf node, collects 0 --> when this results keep moving up, +1 is added.

[narrow mica]

bottom up DP would employ no recursive function calls

[fallow agate]

anyways;
solving the problem like this results in more time/space complexity rather than topolocial sort you mentioned?

[narrow mica]

complexity of both should usually be the same if implemented correctly
however, bottom up is usually faster by a constant because you don't have the overhead of function calls

for python the difference is sometimes larger than in other languages because python doesn't do tail call optimizations

and also be careful that by default python allows for 1000 layers of recursion
to change this,

import sys
sys.setrecursionlimit(10000)
```you can't make it go beyond around 2 * 10**9 though (doesn't fit in a C `int`, this is basically the hard limit)

[thick granite]

suppose a graph that looks like this ```
a -> b -> c
| ^
+> d +

```py
[[a, b, c, d]]  # all nodes at index 0
[[a], [b, c, d]]  # all nodes that are pointed to are moved up
[[a], [d], [b, c]]  # all nodes at idx 1 that are pointed to are moved up again

[[a], [d], [b], [c]]  # same for idx 2

[a, d, b, c]  # combine all the lists

*pointed to by other nodes in the same index

[narrow mica]

ig that could work as well, tho I don't think there's a name for it
kahn's idea seems similar, but the process is way simpler
it goes like this:

keep a stack: stk = []
init stk with nodes of degree 0
repeat until no more nodes:
  vtx = stack[-1]
  output <- stack.pop()
  degree of every node vtx points to -= 1
    if degree becomes 0, put it in stk
```and `output` at the end is a valid topo ordering

degree is a fancy term for how many edges point to it
e.g.

a -> b -> c
|    ^
+> d +
``` then `a` has degree 0, `d` 1, `b` 2, `c` 1

[fallow agate]

Also, the solution to below minimum semesters required problem is exactly same as max_path problem which we discussed until now.
it's looking counter intuitive because
first problem says --> max path
second problem says --> min semesters
but, answer for both problems is maximum, instead one should work on max logic & other should work on min logic?

def semesters_required(num_courses, prereqs):
    graph = _build_graph(num_courses, prereqs)

    visited = {}
    longest = float("-inf")
    for course in graph:
        curr_longest = _explore_dfs(graph, course, visited)
        longest = max(curr_longest, longest)
    return longest

def  _explore_dfs(graph, course, visited):
    # Base case
    if graph[course] == []:
        return 1
    if course in visited:
        return visited[course]
    else:
        visited[course] = 0

    # Recursive calls
    neighbor_courses = set()
    for neighbor in graph[course]:
        neighbor_courses.add( _explore_dfs(graph, neighbor, visited)) 
    visited[course] = 1 + max(neighbor_courses)

    return visited[course]

def _build_graph(num_courses, prereqs):
    graph = {} 
    for course in range(num_courses):
        graph[course] = []        
    for prereq in prereqs:
        a, b = prereq
        graph[a].append(b)  
    return graph

num_courses = 6
prereqs = [
  (1, 2),
  (2, 4),
  (3, 5),
  (0, 5),
]
print(semesters_required(num_courses, prereqs)) # -> 3

[narrow mica]

do you have a test where this fails?

[fallow agate]

No, this is not about failing. This is working algorithm.

[narrow mica]

then what's your question?

[fallow agate]

This minimum number of semisters required question. The question is asking about minimum.
But, it's all max logic

def semesters_required(num_courses, prereqs):
    longest = float("-inf")
    for course in graph:
        curr_longest = _explore_dfs(graph, course, visited)
        longest = max(curr_longest, longest)

def  _explore_dfs(graph, course, visited):
    # Recursive calls
    neighbor_courses = set()
    for neighbor in graph[course]:
        neighbor_courses.add( _explore_dfs(graph, neighbor, visited)) 
    visited[course] = 1 + max(neighbor_courses)

[narrow mica]

I mean... idk what else to say other than "if you see minimum in the question, you don't always have to use min"?

if a class A is a prerequisite of B, then you've (correctly) modeled it to be a path A -> B
and by the problem brief, you can only take B after you take A in a prior semester, so a path A -> B can be thought of costing 1 semester
then the longest path is how many semesters at minimum you must spend to take all the classes

[fallow agate]

also, If below is the input:

prereqs = [
  (1, 2),
  (2, 4),
  (3, 5),
  (0, 5),
]

graph is built in this way, where we iterate only over the 1st indexes of the tuples.

def _build_graph(num_courses, prereqs):
    graph = {} 
    for course in range(num_courses):
        graph[course] = []        
    for prereq in prereqs:
        a, b = prereq
        graph[a].append(b)  
    return graph

But, let's think about this:
(1, 2) --> where 1 is prerequiste & 2 is course.
but, 2 can be prerequisite of some other course?
To cover this; shouldn't we also iterate over 2nd indexes of the tuples like below:

def _build_graph(num_courses, prereqs):
    graph = {} 
    for course in range(num_courses):
        graph[course] = []  

    for a, b in prereqs:
        if a in graph:
            graph[a].append(b)
        else:
            graph[a] = [b]

        if b in graph:
            graph[b].append(a)
        else:
            graph[b] = [a]
    return graph

[narrow mica]

no, clear up the definitions in your mind again
the path A -> B corresponds to the fact that before you take B, you must take A
graph[a].append(b); graph[b].append(a) would create two paths in your graph: A->B and B->A
This corresponds to: before taking B, you must take A; but also before taking A, you must take B
This creates a cycle where you can never take A nor B (which isn't a testcase as stated in the problem brief, so you don't need to worry about it)

[quasi oracle]

This is a good question! This can be solved as a minimization problem: Given a directed graph with a source and a target, each vertex is assigned a non-negative integer. For each edge, the number of the end vertex has to be at least 1 more than the number of the vertex at the beginning of the edge. Find a numbering which minimizes the highest number across all vertices.

A possible solution is greedy: At each step, assign the step number to all the vertices you can reach from the vertices visited so far, and mark them as visited.

So how can a minimization problem be solved using a maximization algorithm?

Well, your question touches on a subject called duality. Specifically, this problem can be formulated as a linear program, so it's duality in linear programming.

In short, a minimization problem has a dual maximization problem, and vice versa. You can think of it as tackling one thing from opposite directions. From that last page I linked:

The strong duality theorem states that, moreover, if the primal has an optimal solution then the dual has an optimal solution too, and the two optima are equal.
Meaning, given that an optimal solution exists, you can reach the same answer to your minimization problem by solving the maximization dual.

A common example for duality (often taught in a computer science degree) is the max-flow min-cut theorem.

And, if you take the problem statement I wrote in the beginning, convert it into a linear program, and find its dual (there's a straightforward algorithm for that), you'll get the linear program for the maximum path problem.

While the solution you showed uses DFS, my solution (for the dual problem) uses BFS. Coincidence?

[fiery cosmos]

(I have been out of practicing DSA for like 4 or 5 months, so I forgot some stuff)

I am trying to solve this problem

https://neetcode.io/problems/lowest-common-ancestor-in-binary-search-tree

Lowest Common Ancestor in Binary Search Tree
Given a binary search tree (BST) where all node values are unique, and two nodes from the tree p and q, return the lowest common ancestor (LCA) of the two nodes.

The lowest common ancestor between two nodes p and q is the lowest node in a tree T such that both p and q as descendants. The ancestor is allowed to be a descendant of itself.

I know that this is wrong solution, but I am wondering why in the end I don't get 5 for returned value but instead I get 10000000. So, this is input

root=[5,3,8,1,4,7,9,null,2]
p=3
q=8

and this is my code

# 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 lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        self.counter = 0
        self.la = TreeNode(10000000)
        self.dfs(root, p, q)
        return self.la
    
    def dfs(self, root, p, q):
        if root is None:
            return
        if root == p:
            self.counter += 1
        if root == q:
            self.counter += 1
        if self.counter == 2:
            return
        self.dfs(root.left, p, q)
        self.dfs(root.right, p, q)
        if self.counter == 2:
            if self.la.val > root.val:
                self.la = root

[quasi oracle]

I can answer your question, but have you tried debugging it? Going line by line and following the flow of your program

I wasn't sure where the problem was, so that's what I did to find it

[fiery cosmos]

I used this code to check locally what is happening (not sure whether approach for testing is correct)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    
class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        self.counter = 0
        self.la = TreeNode(10000000)
        self.dfs(root, p, q)
        return self.la
    
    def dfs(self, root, p, q):
        if root is None:
            return
        if root == p:
            self.counter += 1
        if root == q:
            self.counter += 1
        if self.counter == 2:
            return
        self.dfs(root.left, p, q)
        self.dfs(root.right, p, q)
        print(f"Visited Node: {root.val}")
        if self.counter == 2:
            print("blabla")
            if self.la.val > root.val:
                self.la = root

def insert_into_bst(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_into_bst(root.left, val)
    else:
        root.right = insert_into_bst(root.right, val)
    return root

if __name__ == "__main__":
    values = [5, 3, 8, 1, 4, 7, 9, 2]
    root = None
    for value in values:
        root = insert_into_bst(root, value)
    
    p = root.left  
    q = root.right  
    
    solution = Solution()
    lca = solution.lowestCommonAncestor(root, p, q)

    if lca:
        print(f"The Lowest Common Ancestor of nodes {p.val} and {q.val} is: {lca.val}")
    else:
        print("Lowest Common Ancestor not found.")

and I got 5 as result

[fiery cosmos]

Where do you see problem(s)? I mean problems that are related to 5 not being returned from this online IDE. I know that approach for this solution is not correct, so I am just wondering about how so that 5 was not returned from online IDE

[quasi oracle]

Wait, I apologize, I misread your code. Instead of comparing root with p and q directly, try comparing their values instead

[fiery cosmos]

Thanks, now "it works" (I mean it returned 5)

[quasi oracle]

Great. The problem is that if you don't define explicitly for a class how to compare objects, it will fall back to comparing object IDs. That means that if, for example, the tests constructed the tree, and then did, Solution().lowestCommonAncestor(tree, TreeNode(3), TreeNode(5)), even though the values are the same, Python doesn't know it's how you want to define equality, and it will see p and q that are different from the nodes already in the tree.

That's why if equality is not defined for a class, it's better not to rely on it.

[clever forge]

Is this a good Hash Table?

class HashTable:
    size: int
    buckets: list[Any]
    elements: int

    def __init__(self, size = 10):
        self.size = size
        self.buckets = []
        self.elements = 0
        for _ in range(size):
            self.buckets.append([])

    def _hash(self, value):
        return hash(value) % self.size

    def _get_load_factor(self):
        return float(self.elements) / float(self.size)

    def _increase_size(self, increment):
        prev_buckets = self.buckets.copy()
        self.buckets = []
        self.size += increment
        for _ in range(self.size):
            self.buckets.append([])

        for elem in prev_buckets:
            if elem == []: continue

            for kv_pair in elem:
                self.buckets[self._hash(kv_pair[0])] += [kv_pair]

    def set(self, key, value):
        if self._get_load_factor() > 0.5:
            self._increase_size(self.size)

        done = False
        for i, elem in enumerate(self.buckets[self._hash(key)]):
            if elem[0] == key:
                self.buckets[self._hash(key)][i] = (key, value)
                done = True
        if not done:
            self.buckets[self._hash(key)] += [(key, value)]
            self.elements += 1

    def get(self, key):
        for v in self.buckets[self._hash(key)]:
            if v[0] == key:
                return v[1]

        return None

[regal spoke]

HT = HashTable()
for i in range(10**5):
    HT.set(i * (2**61 - 1), 1)

Try this out

[clever forge]

it... is stuck

so it is inefficient?

But like.... 10**5?! Isn't that a lot?

Still going lol

Is it because of the for _ in range(...): self.buckets.append([])?

[regal spoke]

It's just me trolling a bit

hash(i * (2**61 - 1)) is always 0

!e

for i in range(2, 10):
    print(hash(i * (2**61 - 1)))

[halcyon plank]

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

001 | 0
002 | 0
003 | 0
004 | 0
005 | 0
006 | 0
007 | 0
008 | 0

[clever forge]

oh lmaoo

damn

yeah it just finished doing the job

it's full of []s

But

that hashmap works right?

like it's a good one?

[regal spoke]

I think your code is fine, other than relying on the built in hash function

!e

for i in range(10):
    print(hash(i))

[halcyon plank]

:white_check_mark: Your 3.12 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

[regal spoke]

As you can see, the built in hash function is very far from being random

[clever forge]

Ah

I see

nice

[twin void]

Hi guys, what's the best place to learn algos that's In a structured format

[quasi oracle]

Check the channel pins

[vale gulch]

Chat

I use a folder named "config" and txt files inside for settings, is that good practice or change?

Also mention me

[devout hatch]

idk I use toml file

but thats not rlly config for the bot

its just the project stuff

[fiery cosmos]

Also .... if interested in problems https://usaco.guide

[tribal vine]

Look at the while loop and the conditions under which it returns

[little tangle]

Hi everybody

I need your help

[modern gulch]

Just ask your q, or open a help thread #❓｜how-to-get-help

[tight cedar]

is the actual answer true or false?

anyway what I would guess is that you don't reset your colouring dict every iteration so your second iteration starts by trying to make y red but the last iteration already coloured it blue so it returned False

just do dfs only if the node is not already in colouring

no

y would be blue after your tried colouring from x

then you will try to start colouring y with red

which returns False

you are not reading what I said

[cedar gale]

hi im not sure if this is the correct channel for this but its the same name as my class lol, but does anyone have really good youtube videos explaining bfs and dfs? im using it for a maze-path finding thingy for a class assignment, but the prof just gave us wiki links to teach it to ourselves

[tight cedar]

also you are changing curr_color everytime you visit a neighbour node

which should actually only be changed once before you visit them

[lament pecan]

https://www.youtube.com/watch?v=oDqjPvD54Ss&pp=ygUSYmZzIGFuZCBkZnMgdmlkZW9z

you can watch this video, it helped me

[tight cedar]

you are changing curr_color for each neighbour

like when you are at y and trying to go to x and z

curr_color will be red for x and blue for z

[cedar gale]

thank u i will take a look at it :)

[ancient goblet]

Hello, i wanted to do competitive programming in python, from where i can do?

[tight cedar]

you should be able to fix those issues yourself

[halcyon plank]

:incoming_envelope: :ok_hand: applied timeout to @median dew until <t:1730390725:f> (10 minutes) (reason: duplicates spam - sent 4 duplicate messages).

The <@&831776746206265384> have been alerted for review.

[pure crest]

what a cursed line this is in my union find```python
while p != par[p]:
par[p] = par[par[p]]
p = par[p]

[regal spoke]

The name of this DSU style is called "Halvening path compression" since it halves the length of the path. It is a perfectly valid way of doing path compression. This algorithm is a perfect fit for Python since it doesn't use any recursion. See
https://dl.acm.org/doi/pdf/10.1145/62.2160 .

About something cursed. I've seen people erroneously implement this in Python as

while p != par[p]:
    p = par[p] = par[par[p]] # <- Error

[gray summit]

guys i am just starting dsa can someone recommend a tutorial to start my journey on dsa

[regal spoke]

This is an easy mistake to make if you don't know about Pythons order of assignment. Especially if you start off with the pseudo-code above.
The correct implementation is either the code you have (#algos-and-data-structs message), or

while p != par[p]:
    par[p] = p = par[par[p]]

[haughty mountain]

the most readable thing

[twin void]

Thanks would check this out

[twin void]

Would check this out, thanks

[narrow mica]

wait what
how does python order of assignment work then

[regal spoke]

First RHS left to right, then the LHSs left to right

!e

A = [0,0,0]
i = A[i] = 1
print(A)

[halcyon plank]

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

[0, 1, 0]

[regal spoke]

Here 1 is the RHS

Both i and A[i] are LHSs

The LHSs are handled from left to right

First i gets assigned 1, then A[i] gets assigned 1

[narrow mica]

So in this order basically?

// 1
a = b = c = ... = X
^                 |
+-----------------+

// 2
a = b = c = ... = X
    -------------->

[regal spoke]

!e

i,A,A[i] = 1,[0,0,0],1
print(A)

[halcyon plank]

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

[0, 1, 0]

[regal spoke]

There is this to consider too

[regal spoke]

yes

[narrow mica]

I see...
TIL

[regal spoke]

Thats why this is so tricky

[narrow mica]

then, written like this

while p != par[p]:
    p = par[p] = par[par[p]] # <- Error
````p = par[par[p]]` happens first, then `par[p] = par[par[p]]` actually becomes `par[par[par[p]]] = par[par[par[par[p]]]]` in terms of the original variables, which is wrong
^ is the above right?

[regal spoke]

no. RHS first

So p = par[p] = par[par[p]] is the same as

ans = par[par[p]]
p = ans
par[p] = ans

There is another relatively common situation when people mess this up. You'd assume that this swaps a and b

a,b = b,a

But take a look at these two examples

i,A[i] = A[i],i

A[i],i = i,A[i]

||the first is buggy, but the second is ok||

[narrow mica]

for say the second one, does something like this happen then?

e1 = i
e2 = A[i]
A[i] = e1
i = e2

[regal spoke]

yes

[narrow mica]

ooo
brain enlarged

actually this got me a cursed idea

[regal spoke]

This is why code ⛳ can be good for you. It teaches you many of the quirks you wouldn't normally think of.

[fallow agate]

https://discord.com/channels/267624335836053506/1301912231918702632

[haughty mountain]

"good"

[regal spoke]

was talking about avoid the ```py
i,A[i] = A[i],i

bug

[haughty mountain]

mostly quirks you really shouldn't need to know 🥴

that one I could maybe see someone encountering

[thorn oriole]

hey guys, I'm trying to understand how to calculate the height of a tree

I'm learing AVL

the balanced trees

I dont wanna code it, I just want to know how to manually calculate it

for example I'm checking if 9 is balanced, why is the right height 3? isnt it 2? since we have 2 nodes after 9?

[haughty mountain]

what's the longest path on the left/right side?

[thorn oriole]

ok now I think I got it

yeah I was only going all right or all left

😄

[floral nebula]

any resource on trees and graphs

[quasi oracle]

check the second pin

[floral nebula]

ok is it ok if only thing i know is array and singly linked list

before starting that

[quasi oracle]

should be fine

[floral nebula]

ok

[quasi oracle]

You also have https://runestone.academy/ns/books/published/pythonds3/Trees/toctree.html from another pin

[floral nebula]

is this similar to cs50s where problem sets are checked by cs50 team

do they give us support on our submission

[quasi oracle]

I honestly don't now but I don't think so. But if you're using cs50, doesn't it have graphs?

[agile sundial]

no. there aren't submissions

[floral nebula]

they dont have datastructures

[floral nebula]

ok np i will try to workout the problems by pdf

is mit university same that provide cs50

[agile sundial]

no

[floral nebula]

ok

[floral nebula]

oh wait i do need to know graphing theory and other discrete maths as pre req

[stiff quartz]

Is a^b mod n equal to a^(b mod n) mod n
I think not because if a = b = n = 2, I get respectively 0 and 1.

But for this problem: https://open.kattis.com/problems/associativeexponents, I managed to pass with

    if pow(pow(a, b, 2**61-1), c, 2**61-1) == pow(a, pow(b, c, 2**61-1), 2**61-1):
        print("What an excellent example!")
    else:
        print("Oh look, a squirrel!")

which makes me confused

I used a mod to avoid dealing with big integers (and probably getting a TLE)

But I'm pretty sure I assumed a^b mod n is equal to a^(b mod n) mod n on the RHS of my equality check

[narrow mica]

I think it works if you define 0^0 = 0 (and assuming n is prime)

[stiff quartz]

Well, in my example 2 is prime

but there has to be a property that holds

[stiff quartz]

but we'd need to find another assumption

ah no I see what you mean

(a mod n)^b mod n is equal to (a mod n)^(b mod n) mod n

That's what you were suggesting?

[narrow mica]

I meant it holds if you define the thing I said
use a^p = a (mod p) to prove the rest

[stiff quartz]

Umm, it only holds if we do a mod p right

[stiff quartz]

if we don't take a mod n in my example I get
2^2 % 2 = 0 and (2^(2 % 2)) % 2 = 2^(0) % 2 = 1

[narrow mica]

yes, this is Fermat's little theorem

[narrow mica]

which is why I said to define 0^0 = 0

[stiff quartz]

but there is no 0^0 here

it's 2^2 = 4

then 4 % 2 = 0

and 2^1

[narrow mica]

2^0 = 0^0 mod 2

[stiff quartz]

ahhh

this is so weird though

we get the equality even though it's not equal, so it's just wrong to assume 0^0 = 0 in that situation no?

otherwise we just proved 0 = 1

[narrow mica]

No, we're not assuming, we're defining
but he problem might be that a^p-1 = 1 only works if p does not divide a

[stiff quartz]

So if we use, a=2, b=6, n=5

a^b mod n = 2^6 % mod 5 = 4

and a ^(b mod n) mod n = 2^1 = 2

here 5 doesn't divide a

[stiff quartz]

and this doesn't hold

[stiff quartz]

neither does this actually rip

ok so I managed to hack my own solution

rip

it was just weak test cases

not that a secret theorem made it correct

[narrow mica]

You can prob alter the eq a little to smhn that actually works
It's inconvenient for me to think about it hard rn

[stiff quartz]

no worries

I'm gonna look for a true property

I was just wondering if I had missed something obvious

and it seems not, I just was lucky my solution had passed

[narrow mica]

Prob use a^(p-1) = 1 to your advantage

maybe exp has to mod p-1?
Tbh I feel like I've seen this question somewhere b4 but forgor

[stiff quartz]

it's Alberta Collegiate Programming Contest 2021

[stiff quartz]

The only issue with trying to use Fermat here is that the exponents are not necessarily of the form p - 1 with p prime

[narrow mica]

Ah, here
https://usaco.guide/problems/cses-1712-exponentiation-ii/solution

[stiff quartz]

when we have a^(b^c), b^c can absolutely be non prime

[narrow mica]

yep, mod - 1 on exp

[stiff quartz]

ah nice

[coarse aspen]

me explaining a simple list w/pointers (one way links) to my friend xD

my artistic talents went off the charts here

this should be clear enough for someone who's never heard of stuff like this right?

in it's most basic form at least

[stiff quartz]

did you write queue as cue

[haughty mountain]

(also que)

[coarse aspen]

lmao

maybe

this is what I meant.

[haughty mountain]

no 🥴

[coarse aspen]

oh wait

[haughty mountain]

you meant queue

[coarse aspen]

no

this I mean ofc

with a C

[coarse aspen]

lmao alr MAYBE i meant queue

but my english is so cooked that it became cue

[stiff quartz]

for sure you meant queue

[coarse aspen]

xD

true

[snow bridge]

How can i start learning DSA?

[craggy canopy]

hi . i am looking for any simple implementation of maximal marginal relevance

[stone stratus]

What is eval() in python?

[regal spoke]

https://en.wikipedia.org/wiki/Euler's_theorem this is what you are looking for

(a^phi(n)) % n == 1

if n is a prime, you get
(a^(p - 1)) % p == 1

[regal spoke]

So if anything it should be a^b mod n == a^(b mod n - 1) mod n (if n is prime)

[stiff quartz]

Yep I figured it out eventually

Didn’t know about that function at all

It’s a pretty cool one I must say

[regal spoke]

You've indirectly used it if you've ever done pow(x, p-2, p)

[stiff quartz]

To get the modular inverse?

[regal spoke]

yes

Essentially same thing as x^p = x mod p

[stiff quartz]

Yeah I guess I’d say I used little Fermat

But since little Fermat is just a corollary of that one

[stiff quartz]

Kinda crazy that this had passed

But there were like only 15 test cases which is surprising I guess since it was a « real » competition?

[regal spoke]

Here is my guess of what happened.
Really the only thing that matters is if b*c = b^c

meaning b and c need to be really small

The value of a doesn't really matter

So many of your mods wont matter in the case where b*c = b^c

[regal spoke]

It is very likely that just b*c % (2**61 - 1) == pow(b, c, 2**61 - 1) would have worked

[stiff quartz]

Ah yes fair we don’t care about a at all if the exponents are the same

[haughty mountain]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int id;
    char name[20];
} User;

void create_user(User **user) {
    *user = (User *)malloc(sizeof(User));
    if (*user == NULL) {
        perror("Failed to allocate memory");
        exit(EXIT_FAILURE);
    }
    (*user)->id = 1;
    strncpy((*user)->name, "Alice", sizeof((*user)->name) - 1);
    (*user)->name[sizeof((*user)->name) - 1] = '\0'; // Ensure null-termination
}

void free_user(User **user) {
    free(*user);
    *user = NULL; // Set to NULL to avoid dangling pointer
}

void use_before_free(User *user) {
    if (user != NULL) {
        printf("User ID: %d, Name: %s\n", user->id, user->name);
    } else {
        printf("User has been freed!\n");
    }
}

int main() {
    User *user = NULL;

    create_user(&user);
    printf("Created User: ID = %d, Name = %s\n", user->id, user->name);

    // This is not a use after free vulnerability
    use_before_free(user); // Accessing not yet freed memory
    free_user(&user); // Free the allocated memory

    return 0;
}

free UAF free sample

[craggy canopy]

can i ask about machine learning algorithms here ?

[stiff quartz]

The more I think about it the more I think this is what the authors expected us to do

[regal spoke]

Intended was very likely just a==1 or c==1 or b==c==2

[stiff quartz]

🤔

Yes

Damn

[craggy canopy]

Nvm . I found the ml channel

[fallow agate]

I just came across this problem, but could not find solution any where.
anyone knows solution to this one/ at least to similar problem to this?

problem name: positioning plants

You've been hired to plant flowers in a garden with n different positions. There are m different flower types. The prices of flowers types vary depending on which position they are planted. Your bosses are picky, they tell you to never plant two of the same flower type right next to each other. What is the minimum cost we need to plant a flower in each position of the garden?

Write a function, positioningPlants, that takes in a 2D list with dimensions n * m. Each row of the list represents the costs of the flower types at that position. This means that costs[i][j] represents the cost of planting flower type j at position i. For example:

Given these costs,

costs = [
  [4, 3, 7],
  [6, 1, 9],
  [2, 5, 3]
]

The costs of plants at position 1 are $6, $1, and $9.
The cost of planting flower type 0 at position 1 is $6.
The cost of planting flower type 2 at position 1 is $9.

The function should return the minimum cost of planting flowers without placing the same flower type in adjacent positions.

positioning_plants([
  [4, 3, 7],
  [6, 1, 9],
  [2, 5, 3]
]) # -> 7, by doing 4 + 1 + 2.

[modern gulch]

If you search for 'paint house problem' you'll find the same problem on leetcode.

[fallow agate]

Ok, thank you.

@modern gulch
How did you learnt ds & algo?
any courses taken? if so, pls share the name of those.

[modern gulch]

Many years ago... Uni and grad school. I enjoy DSA problems as puzzles, but it's not something I spend much time on. I'm not nearly as good as some others in this channel.

[modern gulch]

There's a few common patterns in DSA... so whenever I see a problem, I try to "map" the new problem to something I've seen before.

[modern gulch]

But, MIT OCW has several DSA classes... starting with MIT 6.006