algos-and-data-structs

[manic kite]

Yeah, for some reason i thought that there should be a way to free elements at the beginning or end of a contiguous chunk of memory but not the middle, so it would stay contiguous. Thanks!

[opal oriole]

You can depending on the allocator, but they are allocating on the heap, because it's the most generic allocator (paired with garbage collection it lets you code very freely / not having to think about memory mechanics).

[opal oriole]

Deque's with ring buffers are effectively doing it.

[vocal gorge]

i think the last time I googled this I found a mention of some obscure platform on which it's possible to shrink an allocation from the start, but I can't find it now...

[opal oriole]

You actually can on many, but it's some Linux syscalls or Win32 api function calls most never use (directly).

You can also do fun things like resize your stack, or your data section.

(Win32 api has many secrets and fun things, like non-rectangle windows (e.g. the donut window))

(Infinite technical debt that can be abused for funny things)

[vocal gorge]

I barely even know how to make transparent windows and there's donut ones? 👀

yeesh

[opal oriole]

Can do arbitrary shapes with a bitmask.

Can have the user paint the shape.

(Maybe even have them modify the main Desktop window (which is a window, the default main one for the window manager))

[robust canyon]

Side question on this; if I connected 6 pointing to 2, would there be a so called "sub SCC"? I.e., would the SCC (3,4,5) and the SCC (1,3,4,5,6) exist?

[haughty mountain]

being maximal is part of the definition of an SCC

[zealous needle]

y'all talkin bout SCC n stuff when ya can't even tie ya shoelaces rofl

[haughty mountain]

so no, the strongly connected components are (only) these two

[robust canyon]

ah ok, that makes a lot more sense now. Thanks!

[haughty mountain]

in particular the "component" part is what requires it

(3, 4, 5) would be a strongly connected subgraph

but it's not a strongly connected component of the whole graph

[robust canyon]

so SCC's should always be in the focus of the whole graph then?

[haughty mountain]

I mean you could decide to remove some nodes and then talk about the components of that

but yes, SCC is a splitting of some particular graph into components

every node will be in exactly one SCC

and if you then consider how the components are connected to other components, they form a DAG

e.g. for the graph without that edge

hopefully it's obvious why the graph formed by the components can't have any cycles 😛

[robust canyon]

ok, that helps me understand how we find SCCs with algorithms. and the graph formed by the components can't have any cycles because we basically just combine any and all cycles (the SCCs), right?

[outer rain]

Correct, after you condense SCCs you get a DAG.

[haughty mountain]

basically, if there was a cycle in the condensed graph, that means the components in the cycle is part of the same SCC

but that's a contradiction since SCC should be maximal

so there can't be cycles

[robust needle]

why would prim update new distances?

it's not meant to keep track of them, just to compare right?

[haughty mountain]

you need to keep track of distances from the current tree to the nodes reachable from the tree

that's the thing you want to minimize at each step

[robust needle]

ah okay right now i see what ur getting at

okay so. we can agree that the worst case of prims is on a complete graph right?

[haughty mountain]

so at the start everything is ∞, you pick some arbitrary node, that is now in the tree (distance 0) and then you update its neighbors according to the distance to the node you just added, then pick the cheapest node not in the tree already, set its distance to 0 and update neighbors, ...

[haughty mountain]

that sounds correct yeah

[robust needle]

why update the distances when u can just check edge weights?

because that distance updating sounds like dijkstra's relaxation

[haughty mountain]

O(E)

[robust needle]

yeah i got that as well

and since u run this check on every vertex

[haughty mountain]

keeping the distances and updating the min distsnce as needed is O(V) to find the minimum

[robust needle]

it's O(|E||V|), right?

ohh

wait but getting that specifc min distance requires a check on the edges right?

sorry I might be misinterpreting things

should i start a new thread (so we don't crowd chat?)

[haughty mountain]

find the node with minimum distance O(V)
find the edge that yielded that minimum O(V) (in worst case)

[robust needle]

oh..i can't.

[haughty mountain]

here is fine

you only do the second check for one node

tbh I don't know if the thing I'm describing is the canonical way, but it's a way that would work for the O(V²) algo

[robust needle]

okay. uh.

i think i got more lost lol

[haughty mountain]

the update the minimum part will generalize to heaps for better efficiency, the edge picking part needs to somehow be replaced for the improved versions

[robust needle]

;o;

[haughty mountain]

what in particular?

[robust needle]

okay so. i pick a random node right

[haughty mountain]

sure

[robust needle]

and then from there i look at all adjacent nodes (via edges) and update their distances

this would take O(|E|) time,

[haughty mountain]

no

O(V) at worst

the node can't have more than V-1 neighbors

[robust needle]

oh right yup makes sense

okay O(V)

and then this distance updating happens for every new node I add to the MST

[haughty mountain]

yes

[robust needle]

resulting in (O(V*V))

so O(V^2)

so, there's nothing related to the edges, whatsoever?

ah i see my mistake

in the psuedocode where it asks to get all outgoing edges

[haughty mountain]

indirectly there is, you process all the edges connected to the nodes

[robust needle]

i assumed at worst-case all outgoing edges would be all the edges

but that can't ever be the case

at worse it checks V-1 edges.

wait no

okay in terms of the psuedocode, i think it's O(|V||E|)

but i think the general naive implementation is O(|V|^2)

[near crow]

@cinder quest broke a rule for pinging everyone!

[cinder quest]

Hi All I am starting to learn DSA using Python I believe it would greatly benefit me to do this learning with someone who shares an same interest in DSA and Python and Also This would really help me not to lose my interest throughout the learning process. So Is anyone interested in getting along with me?

[robust canyon]

Hey, i just wanna check that this is the correct algo for reversing the arcs in a graph. I'm very sure it is

def reverse_graph(graph, graphrev):
    #should just be O(m+n)
    for key in graph:
        for i in range(len(graph[key])):
            #the new key to put in the reversed graph
            new_key = graph[key][i]
            graphrev[new_key] = [key] + graphrev.get(new_key, [])

The input graph: {1: [2, 3], 2: [3], 3: [4], 4: [5], 5: [3]}

The output graph: {2: [1], 3: [5, 2, 1], 4: [3], 5: [4]}

[haughty mountain]

the complexity is wrong

but because of your implementation

adding elements at the front of a list is O(n)

[robust canyon]

oh, so graphrev.get(new_key, []) + [key] instead of [key] + graphrev.get(new_key, [])

and why is the time complexity wrong? I thought it was right because we iterate through the edges (m) and vertexes (n)

[haughty mountain]

that won't work, you can use setdefault and append

[haughty mountain]

it's wrong because you do linear work on insertion

[robust canyon]

so O(m + n + n)? i thought big O removed constants, but i'm likely wrong about the first part

[haughty mountain]

O(m (n + m)) in the worst case

[robust canyon]

ok yeah, that makes more sense

but using a defaultdict would get it back down to O(m + n), because the insertion would just be O(1), right?

[haughty mountain]

defaultdict(list) and append or a regular dict and doing setdefault and append both work

[robust canyon]

alrighty, thanks!

[ivory path]

Want to feel more strong in this area any video,books, websites, exercises etc… you guys highly recommend?

[robust canyon]

Leetcode: https://leetcode.com
Codewars: https://www.codewars.com

Leetcode and codewars are great for exercises and practice, but don't just run into stuff blindly, follow something like Neetcode https://neetcode.io

[visual tree]

i need help with coding this

s  = 12
p = int(input("Number: "))

def primeFunc(num):
    for i in range(2, num):
        if (num % i) == 0:
                return False
                break
    return True

def ifEven(num):
    if num % 2 == 0:
        return True
    else:
        return False

def compare(x,y):
    if x < y:
        return True
    else:
        return False

def checkFor0(s):
    if s == 0:
        return True
    else: 
        return False

#----------------------------
level = 1
backTo2 = False
while True:
    if level == 1:
        if ifEven(p):
            p = p + 1
            print(p)
            level = 2
        else:
            level = 2
            print(p)
            
    if level == 2 and not backTo2:
        if primeFunc(p):
            level = 3
            print(p)
            
    if level == 2:
        p = p + 2
        backTo2 = False
        level = 1
        print(p)

    if level == 3:
        if compare(p, s):
            level = 3
            print(p)
        else:
            s = s - 1
            level = 4
            print(p)

    if level == 3:
        s = s - p
        level == 2
        backTo2 = True
        print(p)

    if level == 4:
        if checkFor0(s):
            print(p)
            break
        else:
            level = 2
            backTo2 = True

what i got so far which does not work

[ivory path]

I already do these two things

[ivory path]

I’ll check out neet code tho I just saw they have courses, ty!

[robust canyon]

oh also this https://github.com/TheAlgorithms/Python. just a massive list of all the algorithms you could ever need. I don't recommend learning from it, as its better to work through the algorithm and actually understand it, but it's still useful 🤷‍♂️

[ivory path]

Thank you appreciate it

[modern meteor]

first of all did u get to make it O(|V|^3)

[fiery cosmos]

Hello guys i need someone to help with an alogs task that i can't seem to figure, it would mean alot if you're able to help me🙏 DM open.

[ruby igloo]

Hey friends! Challenge time! Can you create an algorithm to generate random outputs from a set? No libraries allowed! Get coding, be creative, and let's compare solutions. May the randomness be with you! 🚀

[ruby igloo]

see DM

[fervent saddle]

There's a leetcode exercise for that.

You can store the values in a dict which maps to indexes in a list which is used for getting random values.

When you delete a value from the dict, you look up where it's located in the list, then copy the value at the end of the list into its position, and delete the now duplicate value at the end. And then you update that former end value's mapped index in the dict.

[outer rain]

Why would you need a dict for that?

[fervent saddle]

How else would you do it?

[snow anvil]

random number in the range of a length of list elements use that as the index

I assume but tbh idk if I understand the task correctly

[outer rain]

generate a random index, swap the element at that index with the last one, pop the last one

I hope you don't use dict as an rng source lol

[fervent saddle]

No, you use the list

https://leetcode.com/problems/insert-delete-getrandom-o1/
It's this exercise.

[outer rain]

ohh, i see, sorry, I though the problem was to just get random elements from the array

[fiery cosmos]

any algo to group n floats in groups of x so that the average is the most similar for all groups?

Ive though about sorting it and pick first and last, 2nd and -2, and so on, but if x is odd?

[modern gulch]

Naive approach is: itertools.combinations and perhaps sort by stdev?

[vocal gorge]

this feels like some accursed version of the knapsack problem

depends on what you mean by "most similar", though. if it's minimizing stdev, hmm...

[fiery cosmos]

?

i said

all groups same average times

or close

like, u have 20 runners, and u wanna make the most similar groups

u are not grouping the fastest together

[modern gulch]

Just clarifying what I meant: by naive, I mean: compute every possible combination of x equal bins from n elements, compute averages per bin, and score each combination (by stdev?), and then find the lowest/best score

And I'm sure this is an np complete problem

[fiery cosmos]

?

no way u can only do this by brute force

[modern gulch]

I didn't say that, I just said it was likely np complete.

Prove me wrong 😉

[fiery cosmos]

i already told u

first with last, 2nd with index -2, third with index -3, and so on

[vocal gorge]

np complete doesn't mean it can only be solved by bruteforce

[fiery cosmos]

no, but his approach was brute forcing it

[vocal gorge]

surely that wouldn't be an optimal solution in most cases.

[fiery cosmos]

by naive, I mean: compute every possible combination of x equal bins from n elements, compute averages per bin, and score each combination

[fiery cosmos]

why not?

[fiery cosmos]

this is brute force

[modern gulch]

do you agree that’s ‘a’ solution? And this seems just like a formulation of https://en.m.wikipedia.org/wiki/Bin_packing_problem

[fiery cosmos]

well, my case is easier tho. 20 runners and groups of 4, or 5

!e
import random
print([random.random() for i in range(10)])

yeah so these are the times, for example

[outer rain]

I would just dump it into ILP solver like z3. This is not an easy problem.

[haughty mountain]

it's a generalization of the subset sum problem, which is np complete

actually, is the group size fixed?

if so it might be an easier problem

(but probably still np hard for general group sizes)

[robust canyon]

(Kosaraju’s algo) for the second DFS call(s), assuming my stack is correct, is this the right path that the search would follow?

I didn't think that you had to go straight down the stack, but im not sure now

also I know there's not a lot here, I'd be happy to provide more context and stuff when I'm not passing out 😅

[copper ether]

How much dsa is required for those who are aspiring to be data analysts?

[modern gulch]

all of it?

I mean, dsa is a separate field to be precise... or perhaps considered foundational, I dunno, but, a good portion of my life is DA related, and it'd be very hard without a strong command of dsa.

[copper ether]

Ohh

Which language should I use python or c++?

I know python but not c++

[fiery cosmos]

is there a better way to type this?
I'm trying to tell python to go to the 52 + 016 offset of the code AFTER the 4th byte of the code
so think of it like byte 4 + (52+016)

in c# you could do something like this (input_file.seek(4, 52 + (0*16))) whic, afaik, would start at offset 4 and then got 52 offsets after that and etc

but when i try to do that in python (comma between .seek) python tells me 52 isn't whence value or something lel

[royal kestrel]

use the whence parameter to seek relative to current position instead of the file beginning

[fiery cosmos]

yea what the heck is whence

because apparently value 52 doesn't exist in whence

#algos-and-data-structs message

[royal kestrel]

https://docs.python.org/3/library/io.html#io.IOBase.seek

[fiery cosmos]

ah so i can only pick between 0-2 for after comma in python

and then have to put another comma

ok thx

[royal kestrel]

it mirrors the C function, alternatively you can just add file.tell() to whatever offset you want

[fiery cosmos]

this error seems to be contradicting what you showed me in the docs. It says at most 2 arguments but the docs show you can add an argument (comma) after the whence thingy

[royal kestrel]

there is no third parameter

[haughty mountain]

I'm unsure what you're talking about exactly here. Kosaraju has 2 phases, one where you do a DFS from each node, marking things visited as you go and adding nodes to a list in post order, and one where you in the reverse list order do a flood fill and claim the unvisited nodes you see as one component.

The reason this works is because the SCCs form a DAG, and by going in a reverse post order you are starting in a sink node in the DAG. You find the nodes in that component and (effectively) remove it from the graph. The next unvisited node in the ordering of the main graph you encounter will be in a new sink node.

[fiery cosmos]

found a workaround i think

also what alternative is there to this?

apparently, in python, int can't use length.

how do i make python detect the length of bytes?

[robust canyon]

i think just len(str(data)), unless i'm misunderstanding your question

[fiery cosmos]

ah ok

now it tells me int object not subscriptable

I tried doing data[str(pos)] but i get same error

i did the str(pos) for both data[pos] in that line

still gives me that error

[robust canyon]

i think its because you're trying to index into an integer

because something like

i = 333
print(i[2])

would throw an error

[fiery cosmos]

ah you mean the data is an int and python doesn't like that i'm searching for an index in it?

[robust canyon]

yeah, exactly

[fiery cosmos]

this code was originally written by someone using c# (i used an online onverter to convert it to python code)

i guess the converter sussy

[haughty mountain]

wdym length of bytes?

oh

[fiery cosmos]

hex code

anyways

[haughty mountain]

len(data) when data is bytes is fine

[fiery cosmos]

well then idk why python had problem with it

it thought data was int rather than byte

[haughty mountain]

maybe you're passing an int

[fiery cosmos]

when i did len(data)
but len(str(data)) worked

[haughty mountain]

and violating the type annotation

[fiery cosmos]

then how do i actually convert data to byte

b(data)
like this?

[haughty mountain]

by converting it

[fiery cosmos]

ah i see

[haughty mountain]

annotation don't magically convert stuff

what type do you want to convert to bytes? int?

[fiery cosmos]

i just got this from c# and that's probably why there's issues (i used online converter from c# to python lel)

[fiery cosmos]

yea

[haughty mountain]

and how should the resulting bytes object look like?

[fiery cosmos]

this is how the original c# code looks like btw (made by someoene else)

[fiery cosmos]

hex would be good

i'm fine with decimal too

0-255 is decimal version

[fiery cosmos]

sorry forgot to paste image lel

[haughty mountain]

like, should 258 be b'\x01\x02'?

or something similar to that

[fiery cosmos]

well 0xA (hex) is 10 (decimal/integer).
65,535 (decimal/integer) is 0xFFFF (hex)

examples ^

[fiery cosmos]

thx i'll do that

[haughty mountain]

In [1]: x = 258

In [2]: x.to_bytes(2)
Out[2]: b'\x01\x02'

In [3]: x = 65535

In [4]: x.to_bytes(2)
Out[4]: b'\xff\xff'

[robust canyon]

yea, poorly asked question, sorry about that!

let me back up a little bit; with this graph, is the stack from the first DFS call correct, where S = [5,4,3,2,1]

[haughty mountain]

what is the first dfs call?

the first stage typically involve many searches

but if you start at 1 there will be only one call, and the post ordering would be 5, 4, 3, 2, 1

[robust canyon]

wouldn't starting from vertex 1 result in every node being searched, thus there's only one call?

for i in range(len(graph.keys())
if visited[i] == False:
            fillOrder(i, visited, stack)

thats the code im using right now, fillOrder is just a DFS call that adds to the stack.

[haughty mountain]

yeah, I said that 😛

with other ordering of the searches the order of 3, 4, 5 in the result might differ

[robust canyon]

would that make the stack incorrect then?

[haughty mountain]

no

all are ok orderings for what we need

the only important thing is that things in the sink component [3, 4, 5] will be done first in the second phase

the order doesn't matter for the result

[robust canyon]

oh ok, that makes more sense

last thing, in the second set of DFS calls, as we're popping from the top of the stack (i.e. 1 , then 2, etc.), do we have to go straight down the stack?

for example, we call DFS on 1, returns 1 as SCC, call DFS on 2, returns 2 as SCC, then when we call DFS on 3, we technically have to go to 5 first, right?

which would leave 4 in the stack, which we still visit, and then returns the correct SCC

DFS calls on the reversed graph ofc

[outer tapir]

534

[haughty mountain]

you would do a dfs/flood fill on 5 first

which will cover 3, 4, 5

4 is already covered

3 is already covered

2 is not, flood fill to cover 2

1 is not flood fill to cover 1

there are your 3 SCC

[robust canyon]

is there any other way to do it? I've just never heard of a flood fill being used for the last part of this algo

[haughty mountain]

I mean you need to find everything you can reach

[sterile lake]

search a good resources to learn dsa with all data structure and Algorithms explained. do yall have some recommandation?

the more detailed one if possible

[haughty mountain]

maybe flood fill isn't that frequently used as a term for graphs, but I just mean "find everything reachable, mark them as visited"

[robust canyon]

oh ok, that makes sense

in that case, DFS does that, right? as long as we're taking an approach like this at least:

while stack:
        i = stack.pop()
        if visited[i] == False:
            dfs_traversal(graphrev, i, visited)

[haughty mountain]

any traversal works

(that's one reason I like saying "flood fill" rather than saying to use some specific traversal)

flood fill can be implemented in a ton of ways

[robust canyon]

yea, that tracks, i was a bit confused cause i looked it up and i thought it was a matrix algorithm. makes a lot more sense now though

so assuming we go from the top of the stack (1 first, 2 second, etc.) we would find all SCCs on the 3rd DFS call (vertex 3), because 3 finds 5, then 4, then itself.

[haughty mountain]

wrong way around

you want to start at the things that are first in the post traversal

they are the "deepest" nodes, and will be in a sink component

[robust canyon]

so start from the beginning of the list?

i.e. 5, 4, etc

[haughty mountain]

I'm assuming that's the dfs post ordering, if so yes

[robust canyon]

ok, thank you very much for all the help

i think ive finally gotten this algo down

[haughty mountain]

if you realize how sink components are special, the algorithm makes a lot of sense

[robust canyon]

i have the proof for it saved somewhere, so i'll look at that + sink components. should make more sense after that

[haughty mountain]

tldr: if you are in a sink component you can flood fill and you won't leave the component

now you have effectively removed that node from the component DAG

so new sink components are exposed

[robust canyon]

im having another problem with this algorithm. I have it all coded up, it makes perfect sense, etc, except that the graph i'm supposed to use for my class throws an error when I run it. I haven't been able to recreate this error with my own simple graphs, and I'm not sure what's going on.

here's the pastebin: https://pastebin.com/xwad5rQ4

and the error is

if not visited[v]:
IndexError: list index out of range

in first_dfs()

[worldly ermine]

I don't really know where this goes so I'll go here

I've run into the problem of Python slowing down the further it gets into it's execution

Last time this was in a pretty obvious loop where I just made sure to reset all variables that I had at every iteration, among some other things, and this seemed to work. However, I don't really understand why it was happening (and no, my input size doesn't increase; each iteration should have about equal input size) and now I have the same issue with a pretty complex algorithm.

Any tips for what to do when this happens, given that it is obvious it's not something else (such as an infinite loop, increasing data object, etc.)?

[vocal gorge]

I'd probably use a debugger to inspect each iteration and see what's happening there. It'd be really weird if nothing changes.

[worldly ermine]

Not too comfortable with a debugger to be honest, I normally use print statements

But I'm more refering to things like ways to free variables in memory or something

Say you call function foo() 10 times

def foo(points_300k)
  points = set(points_300k)
  points.pop()
  ...
  return

I'm guessing this takes significantly longer each call right? Even though the input is always 300k points

So would I then need to free up the variable points? Or do you think this shouldn't slow down?

[vocal gorge]

well, the thing is, it shouldn't

all local variables get cleaned up at the end of the function. And also, even if they didn't, even if you have some sort of memory leak, that should cause the memory usage to rise, but the speed shouldn't change much*.

* at least at first - in the long run it will make GC pauses take longer.

[worldly ermine]

Then alternatively, Python performance on sets is not very good

[vocal gorge]

So basically, I'd look for places where things potentially may be changed over the runs. Writes to a global variable, that sort of thing.

[worldly ermine]

The thing is, I already did that. I'm kind of praying it isn't the performance of the R*-tree I used

Would you mind checking the code for anything obvious?

[vocal gorge]

Could you post the function in question?

[opal oriole]

Can you provide a minimum reproducible example?

[worldly ermine]

Some additional info:
strip contains a list of 3D points.
RT stores the list of points in an R*-tree.

def connected_components(strip, tau):
    # Find the connected components in a strip
    # Returns a list of lists of points
    data = RT(strip)
    
    # Converts the arrays of coordinates to 3-tuples to store in a list
    points = set()
    for point in strip:
        coord = point.get_point()
        points.add((coord[0], coord[1], coord[2]))

    components = []
    while len(points) > 0:
        component = set()

        next_point = points.pop()
        to_visit = {next_point}
        while len(to_visit) > 0:
            new_point = to_visit.pop()
            component.add(new_point)

            neighbors = data.get_neighbors(new_point, tau)

            for neighbor in neighbors:
                points.discard(neighbor)
                to_visit.add(neighbor)
        points.discard(component)
        components.append(component)
    return components, compute_centroids(components)```

[vocal gorge]

points.discard(component)

hmm, this feels weird to me

lemme annotate this with types and see if my hunch pays out...

[worldly ermine]

data.get_neighbors() returns a list of 3-tuples

Which is what the points variable contains as a set

So I loop through the returned list of 3-tuples and for each 3-tuple, I discard it from the set

[vocal gorge]

Well, component is a set of points (3-element tuples) - so it can't possibly be in points, which consists of points, not sets of points

So this line never does anything, which is suspicious.

[worldly ermine]

    points = set()
    for point in strip:
        coord = point.get_point()
        points.add((coord[0], coord[1], coord[2]))```

[vocal gorge]

Perhaps you wanted to do something like points -= component do discard all points in component from points?

[worldly ermine]

Oh wow that's a thing? Neat

It's not really faster, but that's a good start

[vocal gorge]

ah, shame, I kinda expected that to be the problem.

[worldly ermine]

So as you can see this is a 'find components in point cloud' problem, and I always find it a bit funky to do with complex data structures because I'm always scared to make performance in Python much worse.

But apparently there is some DBSCAN algorithm worth looking into, just found it

Although it seems that without knowing the algorithm I basically did that

[vocal gorge]

also, huh... it looks to me like your algorithm may visit a point multiple times. is that right?

as in, it seems to me that a search should only add a point to to_visit if that point used to be in points; otherwise a point may be visited (which marks its neighbours for visiting), then the neighbour is visited, which marks the point again...

[worldly ermine]

It might seem like that, but what I did was every time I extract the points from the KD Tree/R* Tree I delete the points from the tree, to prevent double inclusions

Which is why I looked into an R* Tree

[worldly ermine]

So no worries, there is no infinite loop. But I understand what you're getting at

[arctic gazelle]

can be difficult some times

[haughty mountain]

visited is a list, you read the graph as a dict

it's quite likely their graph is 1 indexed or something similar

[robust canyon]

yeah thats the thing, my test graphs are 1 indexed too... either way, my testcases run, i understand the concept, so I'm happy. i'll come back and troubleshoot this stuff later

[haughty mountain]

hmm, I kinda forgot that you need the graph transpose

I think what I said is broadly correct, other than doing things on the transpose graph, and which direction you process the post ordering

I think it should be reverse post ordering and then step 2 on the transpose graph

[robust canyon]

so you think read the post ordering from the start of the list, or insert it the opposite from how I'm inserting it now?

either way, I still haven't found a way to get around the error in first_dfs

[haughty mountain]

if I had to guess vertices = list(graph.keys()) is not correct

e.g. take a graph like

{
  1: [2],
  3: [2],
}

then your list of vertices is wrong, so your count of vertices is wrong, and you'll fail when trying to deal with the 3

[robust canyon]

oh yeah, thats it apparently. what's the best way to fix that? just put graph.keys() and graph.values() into a set?

[haughty mountain]

that or build a set of vertices as you build the graph

[robust canyon]

ah ok I could save constant time doing that, right?

[haughty mountain]

It's more about whatever is more convenient

[plush coral]

AttributeError: 'WebDriver' object has no attribute 'find_element_by_name' how can ı solcve thıs error

can soneone help me pls

[robust canyon]

wrong channel, #1035199133436354600 is probably best, and also just google it. there's likely a stack overflow post already

[plush coral]

oh sorry ım new ın here but thanks so much

[robust canyon]

all good!

[robust canyon]

figured that out, now I have a different error :/. ran into a recursion depth error, so I did sys.setrecursionlimit(10000), and it now just exits with exit code 1. no information from python or anything

this is all i get, let me know if this is a #1035199133436354600 question and not a #algos-and-data-structs question!

[frank bluff]

haven't gone back through the thread but if you're setting a high recursion limit there's always the possibility of segfaulting

!e ```py
import sys
sys.setrecursionlimit(9**9)
f = lambda: f()
f()

[halcyon plank]

@frank bluff :warning: Your 3.11 eval job timed out or ran out of memory.

[No output]

[haughty mountain]

10000 isn't that large though

I have a hard time seeing why you would get no python error

unless there is a segfault or similar

(windows notoriously just silently fails on segfaults)

[robust canyon]

yeah, it's really confusing me. i see no reason why it should be failing

[worldly ermine]

hot

[silent cove]

HI! How do I print a VISUAL tree like the one below? I have a complete dictionary whose values are weighted branches from the parent 'CORE'?

What library can I use?

{'R2P1': [(80, 'MORE'), (30, 'MBRE'), (20, 'MBIE'), (10, 'MBID')],
 'R2P2': [(200, 'BORE'), (90, 'BRRE'), (40, 'BRKE'), (10, 'BRKS')],
 'R2P3': [(120, 'JORE'), (30, 'JKRE'), (20, 'JKIE'), (10, 'JKIC')],
 'R2P4': [(80, 'MORE'), (30, 'MRRE'), (10, 'MRRY')],
 'R2P5': [(200, 'BORE'), (30, 'BTRE'), (20, 'BTLE'), (10, 'BTLR')],
 'R2P6': [(40, 'AORE'), (30, 'ADRE'), (20, 'ADBE'), (10, 'ADBY')],
 'R2P7': [(80, 'DORE'), (30, 'DRRE'), (20, 'DRNE'), (10, 'DRNT')],
 'R2P8': [(40, 'IORE'), (30, 'IRRE'), (20, 'IRVE'), (10, 'IRVN')],
 'R2P9': [(40, 'HORE'), (30, 'HRRE'), (20, 'HRDE'), (10, 'HRDN')],
 'R2P10': [(80, 'DORE'), (30, 'DNRE'), (20, 'DNCE'), (10, 'DNCN')],
 'R2P11': [(200, 'BORE'), (90, 'BRRE'), (20, 'BRNE'), (10, 'BRNT')],
 'R2P12': [(80, 'PORE'), (30, 'PARE'), (20, 'PAUE'), (10, 'PAUL')],
 'R2P13': [(40, 'WORE'), (30, 'WRRE'), (20, 'WRTE'), (10, 'WRTH')],
 'R2P14': [(120, 'JORE'), (30, 'JNRE'), (20, 'JNSE'), (10, 'JNSN')],
 'R2P15': [(40, 'LORE'), (30, 'LLRE'), (10, 'LLRD')],
 'R2P16': [(200, 'BORE'), (30, 'BIRE'), (10, 'BIRD')],
 'R2P17': [(120, 'JORE'), (30, 'JRRE'), (20, 'JRDE'), (10, 'JRDN')],
 'R2P18': [(80, 'PORE'), (30, 'PIRE'), (20, 'PIPE'), (10, 'PIPN')],
 'R2P19': [(40, 'EORE'), (30, 'EWRE'), (20, 'EWNE'), (10, 'EWNG')],
 'R2P20': [(200, 'BORE'), (90, 'BRRE'), (40, 'BRKE'), (10, 'BRKL')],
 'R2P21': [(40, 'OORE'), (30, 'OLRE'), (20, 'OLJE'), (10, 'OLJW')],
 'R2P22': [(40, 'CRRE'), (10, 'CRRY')],
 'R2P23': [(80, 'TORE'), (30, 'TMRE'), (20, 'TMPE'), (10, 'TMPS')],
 'R2P24': [(80, 'TORE'), (30, 'TTRE'), (20, 'TTUE'), (10, 'TTUM')],
 'R2P25': [(40, 'GORE'), (30, 'GRRE'), (20, 'GRNE'), (10, 'GRNT')]}

[vocal gorge]

My first thought is networkx, though it's more a library for computations on graphs, and visualization is only a minor feature: https://networkx.org/documentation/stable/tutorial.html#drawing-graphs

[silent cove]

Thanks !

[twin mango]

hey

[fallen vale]

this is so sophisticated

i wish im good at that

[warm wren]

Huh

[haughty mountain]

graphviz :V

[austere sparrow]

Yeah ^^^^ graphviz

You can generate a dot file from your graph, and then render it separately with graphviz

[lean walrus]

dot will not generate picture like this

there is a better tool to visualize graphs like this

[austere sparrow]

which one?

[lean walrus]

neato, for example

[austere sparrow]

ah yes, you meant the layout engine

I think that's still part of graphviz

[lean walrus]

yes

[austere sparrow]

the file format is still the same 🙂

oh wait, the actual extension is gv

[haughty mountain]

.dot is the extension I usually see

and that's the example the docs give

https://graphviz.org/doc/info/command.html

[austere sparrow]

oh yeah, maybe that's the source of my confusion

damn... powerful statement

[sinful thorn]

i suck at coding

def array_play(x):
rev_arr=[]
rev_arr2=[]
for i in x:
print(i,'+',end=' ')
rev_arr.append((i))
print('=',rev_arr,'putting this digit inside a list as an array element')
print('=',sum(rev_arr))
# adding the integeres
nums=0
sumed=0
result=0
k=0
for j in rev_arr:
if k<len(rev_arr):
r=j%2
sumed= sumed+nums
nums=nums+r
k=k+1
print(sumed,end=' ')
result+=sumed
print('=',result,' Here it is the sum remainder value of those int after being divided by the 2','\n','reversed arr')

rev_arr2=list(reversed(rev_arr))
## Now array gonna be reverse
print(rev_arr2)
print('max of that array is ',max(rev_arr2))
#[poping out last element last in first out]

n=int(input("enter a number: "))
rev_arr2[0]=n

print(rev_arr2,'first in and it gonna be out')
if type(rev_arr2[0])==int:
    if n<max(rev_arr2):
        z=rev_arr2.pop(0)
        print(z,rev_arr2,"the value that is lower than the max element value will be out of the array")
l=int(input("enter a number: "))
rev_arr2[-1]=l
print(rev_arr2)
if type(rev_arr2[-1])==int:
    rev_arr2.pop(-1)
    print(rev_arr2,' last in first out')

i am newbie

my code not reabable at all

[limpid tartan]

can anyone assist me with this code I am working on, It works fine till N = 9 and after that it doesnt
import math

def print_spiral_numbers(N):
# Calculate the size of the matrix
size = math.ceil(math.sqrt(N))

# Create an empty matrix of size `size` x `size`
matrix = [[None] * size for _ in range(size)]

# Define the initial position
row = size // 2
col = size // 2

# Define the initial direction
direction = 0  # 0: right, 1: down, 2: left, 3: up

# Define the change in position for each direction
row_change = [0, 1, 0, -1]
col_change = [1, 0, -1, 0]

# Fill the matrix with numbers in spiral pattern
for num in range(1, N + 1):
    matrix[row][col] = num

    # Move to the next position in the current direction
    row += row_change[direction]
    col += col_change[direction]

    # Change direction if necessary
    if col >= size or row >= size or matrix[row][col] is not None:
        row -= row_change[direction]
        col -= col_change[direction]
        direction = (direction + 1) % 4
        row += row_change[direction]
        col += col_change[direction]

# Print the spiral matrix in the specified format
for i in range(size):
    for j in range(size):
        if matrix[i][j] is not None:
            print(matrix[i][j], end=' ')
        else:
            print(' ', end=' ')
    print()

given_number = int(input("Enter the given number: "))
print_spiral_numbers(given_number)

[snow anvil]

!code

[halcyon plank]

Formatting code on discord

Here's how to format Python code on Discord:

```py
print('Hello world!')
```

These are backticks, not quotes. Check this out if you can't find the backtick key.

For long code samples, you can use our pastebin.

[snow anvil]

and #1035199133436354600

[gaunt widget]

finally found DSA channel

[gaunt widget]

first tip will be:
Always try to write small functions......

it helps alot to debug it later

[outer rain]

No, this is a bad advice just like any categorical advice ever

[gaunt widget]

for me it always worked

writing small function has this advantages:
Readability and Maintainability
Reusability
Testability
Debugging and Troubleshooting
Flexibility and Scalability

[outer rain]

I won't go into that, you will realize that some of that is false eventually anyway if you program long enough. Or I will realize that I am wrong, idk, anything can happen

Anyway, I got a problem:

Given array of floats, is it possible to assign signs to them to make the result as close as possible to a given value in o(2^N)? For example, given

a = [5, 3, 1.5]
goal = 4

It will return either +5-3+1.5 = 3.5 or +5+3-1.5=4.5, (maybe there is something even closer to that and I missed it). I know it's a trivial O(2^N), but is there a better solution? Or maybe even a good enough approximation? I really don't want to use ILP lol.

[gaunt widget]

well it depends on the scenario.

[outer rain]

(oh no... i can't resist)

[gaunt widget]

let me think

[outer rain]

just like your advice
ok now I shut up, sorry everybody

[gaunt widget]

no one is telling you to shut up.
This is python server and we all here to learn

[outer rain]

ok, it's me, I tell myself to shut up 🙂

[gaunt widget]

well can you say what is the input and what is the target ( value )

[outer rain]

The input is an array of 100 floats at most, can't give any range guarantees, the target is always 1, but that should not matter anyway, you can divide every number by target and normalize it

actually, let's say ints instead of floats because it's easier and associative

[gaunt widget]

can i have the example array

and is it allowed to use any method like plus, minus, divide or multiply?

to get target 1

[outer rain]

No, only + and -

[gaunt widget]

ok only + and - allowed

[outer rain]

OHHHH

I am an idiot, that's just knapsack

well I guess the problem is solved

you can just set the goal to be the sum of array + your goal, and instead of putting signs put either + 2* and + 0*, and it's trivially reducible from there

[gaunt widget]

ik a better solution....

just say print(1)....
time complexity and space complexity is O(1)

xD

[gaunt widget]

can anyone tell me what spiral numbers means?

guys i found an ez question on leetcode here it is:

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

 

Example 1:

Input: x = 123
Output: 321
Example 2:

Input: x = -123
Output: -321
Example 3:

Input: x = 120
Output: 21
 
**SOME INPUTS FROM ME**
Number: 8463847412
output: 0

Number: -2147483648
output: 0

Number: 2147483647
output: 0

Number: -2147483647
output: 0

Constraints:

-231 <= x <= 231 - 1```

[gaunt widget]

btw what do you think about the difculty of this question??

Here is the diffculty : ||medium||

[snow anvil]

My first instinct would be to turn it to a string and then reverse that back to int and check if it is within range

Nvm need to read question more carefully next time

Me apperently

[gaunt widget]

.....

[gaunt widget]

@snow anvil look

hehe something looks like is vanished

[gaunt widget]

going for direct solution would be bad approch

as i said the input can also be start with "-"

[snow anvil]

Well yeah I missed the I 64 requirement

[gaunt widget]

32 bit...

[snow anvil]

That is easy to account for with a simple if statement

[gaunt widget]

well it is pretty simple if you look a little closely

[snow anvil]

Assume the environment does not allow you to store 64-bit integers (signed unsigned)

[gaunt widget]

ye

[snow anvil]

This is where my initial idea would have failed

[gaunt widget]

hmmm then let me help you

if your reverse number is not in between -2147483648 to 2147483647 it will return 0

dont worry i also asked google for help what that [-2^31, 2^31 - 1] means

[snow anvil]

That is obvious but I could not store anything larger than I64 at all

[gaunt widget]

this [-2^31, 2^31 - 1] means the number have to be between -2147483648 to 2147483647

[gaunt widget]

ye but number between -2147483648 to 2147483647 is 32 bit

[snow anvil]

If I do the str to int like I first thought I would get some sort of overflow or the like for numbers greater or smaller than I64 range because they would not be able to be stored

[gaunt widget]

well do you want the answer?

[gaunt widget]

gtg to solve something

[velvet plume]

Can someone help with this - #1123215386280738906 message

[gaunt widget]

help with what?

i just readed the rules.....

can someone tell me which DSA are best to learn

[gaunt widget]

Whoever here , here is a task for you :

imagine you have a list that not sorted.
i.e li = [2, 7, 4, 1, 5, 6, 10, 9, 8]

now sort this list.

Note: Focus on time complexity instead of space complexity. build that in python without using python built in module "sorted()" or any other function that sort. Build a function by yourself.

i just want to see is this really a uncommon question in DSA

[nimble tulip]

Does removing the last element of a heapified list change the invariant?

So if its a min heap, the last element of the list should be the largest right? If I remove it, the list still remains as much of a heap right?

[gaunt widget]

it may affect the overall structure of binary heap i guess

[jolly mortar]

its not necessarily the largest

but it shouldnt disturb the invariant, yeah

[gaunt widget]

right

[lean walrus]

there are a lot of algos with different complexity: bogosort, bubblesort, mergesort, timsort, ... (and a lot more...)
what algo do you want us to implement?

[gaunt widget]

you can use any algo you want . just make sure it is efficient in time

[nimble tulip]

It's not the largest? Oh you mean if the heap was internally implemented such that the right element is not bigger than the left but the reverse was the case?

[gaunt widget]

@jolly mortar how you got the trophy role! I WANT IT

[jolly mortar]

yeah, like
2
/
4 3
is a valid heap but the last elem in the list [2, 4, 3] isnt the largest

[nimble tulip]

Cool got it..

I will go check how python implements the heap

[jolly mortar]

win a pyweek or summer code jam

[gaunt widget]

where can i found that?

plus when will it start

[jolly mortar]

ask in #community-meta
code jam is still TBD, pyweek should be sometime in sept

[lean walrus]

!e ```py
import random
import itertools as it

arr = [4,1,3,2] # we want to sort this

is_sorted = lambda a: all(a <= b for a,b in it.pairwise(a))

while not is_sorted(arr):
random.shuffle(arr)

print(arr)

[halcyon plank]

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

[1, 2, 3, 4]

[lean walrus]

done

[gaunt widget]

will i get ping when it it near to start

[gaunt widget]

let me run that code and let me see the time

[lean walrus]

bruh

it is quite fast on short arrays

[gaunt widget]

i will implent a 1 million un sorted list

[lean walrus]

good luck

[jolly mortar]

get the Announcements role from #roles

[gaunt widget]

@lean walrus

GJ

It gave a error

😆

[lean walrus]

which error

it works perfectly on my machine

[gaunt widget]

wait i think i forgot something

[lean walrus]

thats because you did arr = None

[gaunt widget]

sorry that was my fault i forgot to made 1 million unstored array

give me some seconds

its taking time ....

let me change the value to 10000

[lean walrus]

def sort(arr):
    while any(a > b for a,b in __import__('itertools').pairwise(arr)):
        __import__('random').shuffle(arr)

arr = [4,1,3,2] # we want to sort this
sort(arr)
print(arr)
``` updated version

[gaunt widget]

thx

[lean walrus]

of course! every algorithm takes time

[jolly mortar]

smh denball trolling hard

[lean walrus]

!resources

[halcyon plank]

Resources

The Resources page on our website contains a list of hand-selected learning resources that we regularly recommend to both beginners and experts.

[nimble tulip]

You Sir, won the discord server today with this one..

[lean walrus]

maybe this ^ will help you

[nimble tulip]

Hat's off to the devil within you lol

[gaunt widget]

@lean walrus

did you forgot to add a conditional statement and return statemeant.....

[lean walrus]

no, my function sorts array inplace

def sort(arr):
    arr = arr[::]
    while any(a > b for a,b in __import__('itertools').pairwise(arr)):
        __import__('random').shuffle(arr)
    return arr

arr = [4,1,3,2] # we want to sort this
print(sort(arr))
``` this version returns new sorted array (just like `sorted()` function)

@gaunt widget

[jolly mortar]

😭

[gaunt widget]

@jolly mortar

can you run this script on your pc please:

from numpy.random import shuffle
import itertools as it
import operator as op
from time import time

def sort(arr):
    arr = arr[::]
    while any(a > b for a,b in __import__('itertools').pairwise(arr)):
        __import__('random').shuffle(arr)
    return arr

arr = list(range(10)) # we want to sort this

shuffle(arr)

print("started")
s = time()
sort(arr)
e = time()
print(e - s)```


my pc showing it took 34 seconds 💀

[gaunt widget]

this code seems pretty legit.....

[sick marsh]

can i get flask on VS code? im on Mac

[jolly mortar]

its not lol

[gaunt widget]

yep you can

[jolly mortar]

it just keeps shuffling the list randomly till it happens to get sorted

[sick marsh]

how?

[gaunt widget]

💀

follow this steps:

Create a new project folder
Open the project folder in Visual Studio Code: In Visual Studio Code, go to File → Open Folder and select the project folder you created in the previous step.
Create a virtual environment (optional)
pen a terminal in Visual Studio Code by going to View → Terminal or using the shortcut Ctrl+Backtick (`)
in terminal type this :

Activate the virtual environment (optional):
on mac:
source venv/bin/activate
install flask:
pip install flask

[gaunt widget]

this way

[gaunt widget]

@lean walrus YOU JUST WON THE WINNER TROPHY OF PYTHON COMPETION!!! 💀

[lean walrus]

💀

[gaunt widget]

bro i really thought you were genius when you said "which algo is have to be use?"

[gaunt widget]

Can anyone solve this question , i want to see what techinque you guys use to solve this effiently

[sick marsh]

i got that

[gaunt widget]

nice 🙂

@sick marsh is the virtual enviromeant module installed or not?

run this command to check python -m venv --version

[lean walrus]

just use sorted

[gaunt widget]

This is DSA bro.....
i heard those kind of question also asked in interview

[lean walrus]

then learn about mergesort or timsort and still use sorted

[gaunt widget]

looks like you need to reinstall python

[gaunt widget]

bro do you know why sorted function is fast?

[lean walrus]

yes, it uses timsort

[gaunt widget]

.....

[sick marsh]

how?

[gaunt widget]

do you know it uses C for his performance speed.....

[gaunt widget]

....

@sick marsh
run this to unistall python:

install python again from their website

then run this:

then run this two:
source venv/bin/activate
then
pip install flask

also since you unistall python so you need reinstall those package that you installed before using pip

[gaunt widget]

Verify that you are in the correct directory: Make sure you are navigating to the correct directory where your virtual environment is located. Double-check the path and ensure that the virtual environment folder exists.

ELSE:
one alternative way is:
just is
pip install flask

the problem with this is:
This will install Flask in your global Python environment, allowing you to use it in your scripts. However, it's generally recommended to work within a virtual environment to isolate project dependencies.

@sick marsh
gtg
if you face more problem go to https://discord.com/channels/267624335836053506/366673702533988363

[snow anvil]

this is irrelevant for algorithmic complexity which I am pretty sure is what you asked for

[robust canyon]

working on dijstrkas (however you spell his name) algorithm right now. what does the pi value mean? for some context:

Line 1 initializes the d and pi values in the usual way

[outer rain]

You can prove that if you can only compare the elements (equivalently, if you only have a total ordering defined) you will need at least O(n log n) comparisons. If you can use other operations then it's difficult: for example integers less than N can be sorted in O(n), permutations can be sorted in... Well... O(1), kinda. The question is totally valid.

[vocal gorge]

presumably that's described somewhere else in the description you're reading. I'd guess, simply from first letters, that d is distances and π is predecessors, but that's merely an educated guess based on what dijkstra's algorithm requires one to keep track of.

[robust canyon]

yea, i found an old slideshow from some college that explained what you said. thanks!

when we run extract-minimum, are we also assuming that said function works like a pop() function, where it removes the selected item?

[agile sundial]

that's correct

[robust canyon]

alrighty, thanks

[orchid violet]

you can just run it on the bot

anyways you import random at the very top and you import it yet again in the sort func? also import numpy random but dont use it

[robust canyon]

does djistraks have to navigate directly between linked nodes? for example, in this graph, if we're currently on node 2, but node 5 has the lowest distance value, do we go to node 5? that makes sense, I just wanna check

[tiny compass]

hey guys I wanna ask is algorithm and data structures really matter to AI, for example: Machine Learning, Deep Learning, Neural Network etc ?

[agile sundial]

is 2 in the top middle or bottom left

[tiny compass]

I still struggling with the basic and I'm afraid it might affect my study about AI

[robust canyon]

oh sorry about the horrible writing, bottom left

[agile sundial]

no, it doesn't. the only thing it does is take the shortest edge it can take

[robust canyon]

so it would go from 2 to 5?

[gaunt widget]

Where is that?

[agile sundial]

yeah

[robust canyon]

alrighty, thanks again

[gaunt widget]

Answer seems legit but the script....

[outer rain]

wdym "the script"?

[gaunt widget]

Is that graph ?

[gaunt widget]

I wanted the scripture cause
Impending your thoughts in coding is the real work in programming

[robust canyon]

yup, im working on dijkstras

[gaunt widget]

Gl 👍

[robust canyon]

thanks 🫡

[outer rain]

I mean, just any merge sort implementation, lol

Why do you need the code when you have the algorithm? It's not hard to implement it once you understand it, the opposite is not true. I mean, if you want the code:

def merge(a, b):
    i, j = 0, 0
    c = []
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            c.append(a[i])
            i += 1
        else:
            c.append(b[j])
            j += 1
    return c + a[i:] + b[j:]

def merge_sort(a):
    if len(a) <= 1: return a
    return merge(merge_sort(a[::2]), merge_sort(a[1::2]))

well never mind, I failed to write a basic algorithm out of my head apparently🤡

[gaunt widget]

Hmm seems good let me run on bot first

[outer rain]

no it's not, one sec

[gaunt widget]

.....

[outer rain]

ok cool I made a typo, now fixed

[gaunt widget]

@robust canyon
When running a script on bot, how to check how much seconds it took?

[gaunt widget]

👍

[gaunt widget]

@outer rain

[outer rain]

!timeit

def merge(a, b):
    i, j = 0, 0
    c = []
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            c.append(a[i])
            i += 1
        else:
            c.append(b[j])
            j += 1
    return c + a[i:] + b[j:]

def merge_sort(a):
    if len(a) <= 1: return a
    return merge(merge_sort(a[::2]), merge_sort(a[1::2]))

import random
a = list(range(10 ** 5))
random.shuffle(a)
merge_sort(a)

[halcyon plank]

@outer rain :white_check_mark: Your 3.11 timeit job has completed with return code 0.

1 loop, best of 5: 496 msec per loop

[gaunt widget]

Where is seconds?

[outer rain]

0.496

[gaunt widget]

Hmm that's pretty good

You passed

@outer rain
ANSWER HONESTLY DO YOU Have any idea how to solve that question without knowing that Algo?

[outer rain]

wdym?

[gaunt widget]

I meant can you solve that question without knowing that DSA

[agile sundial]

isn't the answer just by definition? if you don't know.. you don't know

[gaunt widget]

😂

[gaunt widget]

I agree lol

Btw I have a question is Pikachu the famous animal in this world.....

[outer rain]

Like, inventing the fast sorting algorithm is not too difficult, but you need to know how to program, what time complexity is, and so on, just so you could formulate what you are trying to achieve. The proof of the fact that a better algorithm does not exist only requires knowing stirling's formula and general knowledge about combinatirics and logarithms and asymptotics. I don't know how to answer that question, but, I mean, that Hoare guy come up with a sorting algorithm somehow so...

Ok, your question is like asking "Can a blind person draw a good painting?" and like the answer is.. yes? but also like you understand that they won't perceive the painting as you do, so they will need to practice in a different way... or idk, have mr beast cure their blindness (fking go learning dsa if we go away from the analogy). The question is very flawed. "Can you invent the algorithm without knowing it?" Yes, that's not difficult, but you need a proper background.

[gaunt widget]

I meant can you apply it with having your general knowledge

[outer rain]

define "apply"

[gaunt widget]

to use something or make something work in a particular situation.

[outer rain]

It's not hard to write merge_sort(a), is it?

[gaunt widget]

Depends on the person general knowledge

Whatever bye

[agile sundial]

what are you even asking

if you don't know something, you don't know it

[robust canyon]

whats the best way to store distance values for dijsktra? my one idea was just with classes like

class Node:
  def __init__(self, node, distance):
    self.node = node
    self.distance = distance

but that does seem a little bit tedious, as i've just been using an adjacency list (through a dict) up to now

[vocal gorge]

I'd just use two dicts.

(with the keys being vertex indices or whatever unique identifier your vertices have)

[robust canyon]

ah yeah, that makes sense, thanks

[orchid violet]

#bot-commands

[gaunt widget]

I'm talking about can someone solve that problem with using their general knowledge.....

OK. MY FAULT THAT I ASKED THAT QUESTION

[humble linden]

Does anybody know of a name for this operation/algorithm/function?

Summary: Working with a bit stream, and essentially the function takes N bits and accumulates them into an integer. If that value + 1 << N (essentially adding another on bit to the highest position, creating an N+1-bit integer) is greater than a user-defined MAX, then it simply returns the N-bit integer it reader. If not, then one extra bit is read and added to the result (in the position of highest significance).

Code example:

def take_bits(count: int) -> int:
    """Takes `n` bits and accumulates into an integer."""

def take_bits_max_computed(count: int, maximum: int) -> int:
    data: int = take_bits(count)
    up: int = data + (1 << count)
    if up > maximum:
        return data
    if take_bits(1) == 1:
        return up
    else:
        return data

[gaunt widget]

There is many Algo but sadly idk

😢

[cedar gale]

Hello there ,
I am currently doing some Algorithms Questions and not surprisingly enough there were many questions I was not able to do .

When I went to Youtube and other platforms to find solutions , I found that even though there were many videos regarding how to solve a question , many failed to explain why the logic works and how to replicate the logic in future for other questions and I also facing difficulties in visualizing the logic

I mean , I believe you can related if I ask you to visualize a complex Recursion Problem or a DP Problem by just using pen and paper and lets not even start talking about when it comes to trees and graphs

I just Created a google form to know what issues do you face when you are stuck at a particular programming problem and are you able to visualize a particular logic and its working

If anyone is interested in giving their input , You are welcomed to do so
and pls share this to people who you believe will benefit from this

docs.google.com/forms/d/1qTiZ-NymWHykbai_NfnyexG0xFXNsFNoQuhoHhZfseM/edit

[fiery cosmos]

Can you provide me with tips on improving my skills in recursion? It's one of my weaknesses in data structures and algorithms and it often confuses me. When is the best time to utilize recursion? The only instances I can think of are factorials and finding the nth number in the Fibonacci sequence. If you know any websites where I can practice recursion, please let me know.

[hollow mesa]

Not sure if on topic but here is the result of my first python project. It takes some psychedelic art my brother made and plays conways game of life on it

[cedar gale]

hey i was going through some leetcode questions
and obviously i got stuck at some questions
I find multiple resources for solution but no one was upto mark for the same
they only told how to solve that particular question but not telling the underlying foudation of the logic they used
Do you know any sources that explain the questions using visual representation
Pls Dm me for the same
chat becomes a little to fussy for that

[robust canyon]

anyone know whats up with my algorithm (dijsktras still) https://pastebin.com/HYPSJuNd

It gets vertex 82, 99, and 115 correct, but fails on all other vertexes in the print statement

[lean walrus]

this art is very cool!

[noble sluice]

Nice

[haughty mountain]

there is #media-processing but I'll gladly accept a finite state automaton here 🙂

[modern gulch]

I think you’ll have to tell us the actual problem you’re talking about.

[spiral sierra]

more complicated than i thought x_x

[spiral sierra]

this art make my eyes hurt x_x

[robust canyon]

updoot ^

[gaunt widget]

i tried to find alot but didn't find it......
i think it can be a custom impletation

[gaunt widget]

good art but dont know what it is doing here lol

my brain kinda got dmg cause i tried to understand that art

[knotty badge]

does anyone know where i can find anything like this

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

[gaunt widget]

@knotty badge
It is related to machine learning I think

[knotty badge]

yes it is for sure, i am a researcher trying to figure out how to enhance our BRUV

[haughty mountain]

idk if it warrants a specific name

def take_bits_max_computed(count: int, maximum: int) -> int:
    data = take_bits(count)
    if data | 1 << count > maximum:
        return data
    return data | take_bits(1) << count

[gaunt widget]

Ok gl

[fallen vale]

hi can u teach me binrt search in this case?

hi
my home work:
there is a list A full of numbers
and number S
check in A if there is 2 items that Ai+ Aj =S
Can you pls tell me how to do this in binary search? i can use brute force but not binary search

[haughty mountain]

binary search is an awkward way of doing that

you can use a set to do it in O(n)

or you can sort and do a two pointer walk kind of thing

the binary search also would need sorting, and is just worse than doing the two pointer thing

[naive oak]

isn't a dict more efficient

still O(n)

[haughty mountain]

I mean, it's the same

"do I have S - cur_element in my set of seen things?"

[naive oak]

oh right we don't have to keep track of indices

nvm then

[haughty mountain]

if you need indices then a dict is good yeah

[kindred mango]

Is an LRU cache (implemented as a dict or similar container) still not part of the standard library?

[vocal gorge]

!docs functools.cache ?

[halcyon plank]

functools.cache

@functools.cache(user_function)```
Simple lightweight unbounded function cache. Sometimes called [“memoize”](https://en.wikipedia.org/wiki/Memoization).

Returns the same as `lru_cache(maxsize=None)`, creating a thin wrapper around a dictionary lookup for the function arguments. Because it never needs to evict old values, this is smaller and faster than [`lru_cache()`](https://docs.python.org/3/library/functools.html#functools.lru_cache "functools.lru_cache") with a size limit.

For example...

[vocal gorge]

Oh, but if you need just the cache without the function wrapping, no.

[agile sundial]

@functools.cache
def cache(func, *args):
  return func(*args)

# usage
x = cache(lambda: expensive())
``` 🥴

wait that doesn't work

there

[lean walrus]

lambda: expensive() is just expensive

[lean walrus]

wait, that will not cache anything

lambda: expensive() is a new lambda every call, so @ft.cache will treat them all as different arguments, so it will compute expensive on every call (and store result in cache for no reason)

[haughty mountain]

@jade tusk
@vocal gorge
it was a fun thing to implement, my implementation is a tad hacky and inefficient, and I needed to add some special casing to not be ok with solid color borders

[jade tusk]

........

U think this method will work on black and white pages?

And what are those lines exactly?

[haughty mountain]

if it has a lot of solid colors this will easily fail

[jade tusk]

And how long did it take to get this result

[haughty mountain]

the minimal spanning tree

[jade tusk]

Did u make a fully funtion python code for this or something?

Can u try it on other images too?

[haughty mountain]

runtime? like 15s, but most of that is just from building the graph

[jade tusk]

💀

Wtf that's quick...

U are a genius

[haughty mountain]

doing something with backtracking like @vocal gorge suggested would be a better idea, what I'm doing here is basically building an mst and hoping for the best

[jade tusk]

Can i dm u few more pages to see if it works on them?

Or can u share the code with me

[haughty mountain]

I can show the garbage I get when I don't try to filter out stuff that is mostly a solid color 😛

[jade tusk]

😂😂😂😂

[haughty mountain]

I mean, I can try some more image

or you could try the program on your own if you want

[jade tusk]

I sent u some images in dm

[haughty mountain]

@jade tusk
https://gist.github.com/algmyr/4ef4080a617f3b04e8d0f01fedccbee3

[jade tusk]

Thanksss 🫂

[fiery cosmos]

does anyone know how to make a user input that isn't a input where your write the answer?

i want the user to select between 3 choices

i don't want him to have to write down the choices, even if i tell him what they are

[naive oak]

this isn't really an #algos-and-data-structs question

[fiery cosmos]

ah mb

[naive oak]

but the easiest way is probably to just number the choices and have them enter like 1 2 3

[fiery cosmos]

do you know which channel ism ore convenient for this?

[naive oak]

just #1035199133436354600 probably

[fiery cosmos]

yea but then they have to write down rather than clicking, for example, up arrow, to go to answer above and then press enter or smtg, to select it. That kind of thing

i'll post in #1035199133436354600
i thought this counted as data structure question lel

since structuring choices

[stuck sorrel]

ig structuring but not really data

[fast lynx]

hey guys i hope everyone is doing well , so am new and i mastered the basics n can solve some problems but i still don't know where to learn dsa and for example where should i use a binary tree or linked lists or graphs ..........

if someone can give me some ressources or some tips to how can i implement them i'll be so grateful

[modern gulch]

If you comfortable with the equivalent of CS50 material, then look at a DSA course. MIT OCW has 6.006: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/

[unborn terrace]

Hey everyone, i'm not a coder but have sort of a cost optimization problem. Hoping someone could point me in the right direction. Essentially I'm trying to optimize multi-origin shipping based on the cheapest courier rates.

So in this case the customer lives in Saskatchewan but due to inventory, the optimal result is to ship everything from Ontario DC. But there are many times it's cheaper to split orders from multi warehouses and many times its best to keep everything together - this is due to courier multi-piece discounts and weight thresholds

[fiery cosmos]

im back on leetcode and I'm thinking about the psycology of it, do questions like this ever become "obvious"? or is it more like that youve just seen the question so much and you know the optimal solution immediately and so youre comfortable with it

"""Given an array of integers nums and an integer k, return the total number of
subarrays whose sum equals to k.
Example 1:
Input: nums = [1,1,1], k = 2
Output: 2
Example 2:
Input: nums = [1,2,3], k = 3
Output: 2"""
def subarraySum(self, nums: List[int], k: int) -> int:
    count = sum = 0
    mp = {0: 1}
    for num in nums:
        sum += num
        if sum - k in mp:
            count += mp[sum - k]
        mp[sum] = mp.get(sum, 0) + 1
    return count

[modern gulch]

In this case, yah, I can think of two solutions (one naive/brute force, other slightly smarter) immediately.

Would require thought to think about optimal solution and convince myself that I’m right

[haughty mountain]

they do get obvious

once you pick up some algorithms, data structures and techniques (and how to use them) you have the tools and building blocks to tackle harder problems

with training you also get better at breaking problems into smaller parts you know how to solve

you might encounter a new problem, but after breaking it down you're left with pieces you can handle, and you've conquered another problem

[opal oriole]

If you have ever done chess puzzles before, it's very much the same.

You can find books that throw a lot of simple problems at you, then later ones can be broken down into those (dynamic programming yay).

Your brain will automatically remove the problem specific details / noise and find that general shape it matches with enough practice, including unconsciously. In chess this is extreme to the point of being able to zone out of reality and somehow still solve it.

(Like how you don't need to think (consciously) about how to walk, you just do it (although you can switch back to manual and need to in order to improve further (this part is slow)))

[fervent saddle]

Isn't chess skill strongly correlated with high IQ?

[opal oriole]

IDK, top chess players have scored slightly above average.

[fervent saddle]

Hopefully it's not too much like chess, because then people with below average IQs are boned.

[fervent saddle]

https://leetcode.com/problems/partition-equal-subset-sum/
What about this one? I can't think of a way besides just checking the sums of every possible partition pair.

[fiery cosmos]

im looking at my favorite solution reference for this and it's hilariously incomprehensible will figure this out tomorrow

    def canPartition(self, nums: List[int]) -> bool:
        sm = sum(nums)
        if sm & 1: return False
        bits = 1
        for x in nums: bits |= bits << x
        return bool(bits & (1<<sm//2))

[fervent saddle]

What the fuck

[fiery cosmos]

im new to competitive programming and i wondering how to use them effectively?

this Constraints are really helpful?

[fervent saddle]

They can be

But actually, if they're highly relevant, it will mention them in the description.

Like that one where you need to find the duplicate value, and the constraint is 0 <= array[i] <= len(array) or something.

[naive oak]

it's doing dp with bits

bits |= bits << x essentially updates the table with all the sums reachable by adding x

which you get by shifting the entire table by x

and you do that for every item in the array to get all the possible sums

and then you just check if your target is in there

[lean walrus]

thats really smart! i like it

[outer rain]

Is this leetcode? If so, no, they are mostly irrelevant. The only thing they tell you is that O(nums.length^2) won't work, which is... duh, obviously. (But at the same time if I saw this on codeforces I might consider O(n^2) solution with cache-efficient implementation). You will get an intuition for constraints at some point, for now just remember that if you have O(f) time complexity, you put maximum values inside f, and you get more than 1e7, it is probably too slow.

A wierd question, borderline "mathematical concept", "algorithm" and "offtopic", but it still has a huge algorithm and math basis.

Is there any way to sort colors? I know those are 3D and the sorted array is 1D, but is there a way to order colors in such way, so that the human will find this ordering "natural"?

literally three minutes later I find this article and looks like the problem is solved. Not in the satisfactory way, but solved https://www.alanzucconi.com/2015/09/30/colour-sorting/

[fiery cosmos]

I appreciate the brief explanation very much.

[haughty mountain]

this is https://en.wikipedia.org/wiki/Subset_sum_problem

in particular it's an NP complete variant of it

there is a simple knapsack-like solution though

[haughty mountain]

lol, this is doing the knapsack thing for subset sum, but using the int as a bitset

[harsh skiff]

Hey, I'm creating a really huge dict (north of 30M keys), and it consumes tons of memory. They're all (Decimal, int) pairs, and I was wondering if there's something I could use to reduce the RAM usage. I only need the __setitem__ and __getitem__, everything else is redundant in this case. Is there some C library I could use for this to reduce the memory footprint (maybe to avoid the overhead of a PyObject or something)?

I am not doing any arithmetics with any of them, so I can convert Decimal to float if that helps

(or at least that's what I think, I'm parsing multiple 30GB+ JSON files, and everything I looked at that I need for this mapping were float values)

[vocal gorge]

I'm not sure you can, if you want it to still be a dict.. maybe a pandas dataframe would be more memory-efficient, actually, and accessing a dataframe by a key of the index is fast-ish. But they aren't quickly appendable to.

[grizzled bough]

aren't pandas dataframes in memory as well?

[vocal gorge]

Of course they are, but storing this in a pandas dataframe would be only 8 bytes per float or int, compared to ~28 bytes for a python object in a dict (which needs an object header). So around 3 or 4 times less memory.

[grizzled bough]

i agree though 30gb seems like a good candidate for a dataframe, whether pandas or pyspark. you can read pyspark dataframes from json files

[grizzled bough]

nice, didn't know the exact byte differences between dicts and pandas

[harsh skiff]

Never used either of them, and I'd like to avoid adding an external dependency (Spark server). Also considering SQLite in memory... How much of an overhead are we talking about for appendability?

[vocal gorge]

Pandas dataframes aren't appendable to at all (they are internally a numpy array per column) - an append requires copying all the data to a bigger dataframe.

[harsh skiff]

I can batch load into it, like 50k keys at a time or something. I am first building the entire dict, and then only reading from it until end of exec

[vocal gorge]

Sqlite in memory might work tbh

maybe also duckdb?

[harsh skiff]

Heard of it, guess it's a great time to take a look

Thanks

[vocal gorge]

example:

import sys
dct = {i:float(i) for i in range(10**6)}
sys.getsizeof(dct) # 41943128, which is around 41 bytes per item - that actually seems low; I don't think it counts the elements themselves
import pandas as pd
df = pd.DataFrame({"col":dct.values()},index=dct)
sys.getsizeof(df)  # 16000032 - exactly 16 bytes per item (8 for an int, 8 for a float) and 32 bytes of header

[fervent saddle]

floats would take up a lot less memory.

[harsh skiff]

It's a totally random order, so I can't really partition it either, so I guess pandas are out of the view. The rebuilding would really kill it :/

[vocal gorge]

But beware:

%timeit dct[634327] # 201 ns ± 60.9 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
%timeit df.loc[634327] # 91.2 µs ± 13.4 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

(because the index is an Int64 one, there's no assumed order for e.g. a binary search, so it's just a linear lookup. If it's possible to sort the index, that'd allow binary searching instead)

[harsh skiff]

DuckDB is so lightweight and fast! Thanks a bunch!!!

I might even get some sleep tonight 😄

The question_num incrementing line is after the for loop (if the formatting didn't get broken), and it increments by 0. You probably wanted that to be 1 instead?

[robust canyon]

I know that this is probably the most basic question ever, but what exactly is this question asking?

[haughty mountain]

example

[-2, 1, 5, 2]
```possible values of `t`

-2 + 1 = -1
-2 + 5 = 3
-2 + 2 = 0
1 + 5 = 6
1 + 2 = 3
5 + 2 = 7
```unique values of t

-1, 3, 0, 6, 7
```-> answer is 5

I guess the distinct part is that you're not allowed to us the same value twice

[fierce meadow]

how does optimized bubble sort work?

[robust canyon]

then its also asking that the value of t must be between -10000 and 10000, right?

[haughty mountain]

I guess, yeah

though it's weird to constrain t rather than the elements

[robust canyon]

according to my class, we're supposed to use a standard solution to a 2sum problem, something like

Insert elements of A into hash table H in O(n) time
For each x in a, lookup t-x in O(n) time

but t isn't really defined, because it could be anything. little bit confused

[robust canyon]

*use the solution to a 2sum problem in this scenario ^

[vocal gorge]

t is the sum you need to find.

i guess you could iterate over the interval and check solvability for each.

[rare pumice]

Can you someone please help me fix a python code ? It was working 2 days ago but i don't know what happened. Please help me its very important to me. Thank You!

[vocal gorge]

you can write it slightly nicer as
||

for ind, num in zip(index, nums):
    target.insert(ind, num)

||

It's possible to do it in O(n log n) instead of O(n^2) but that's much more complicated and, in python, probably not actually faster.

[stray fractal]

fastest i can think of || ```py
class Solution:
def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]:
return [*map((target := []).insert, index, nums)] and target

[mossy quartz]

so cool

[analog ferry]

hmm, there is no good way to do explicit order "selection insert sort" fast in pure python
unless there is a effective algorithm to transform the insert locations to put at locations it seems like a lost cause as insert is pretty optimized

the task is pretty much to zip and call insert, and i would naively presume that sort/transform of the indexes in python to allow append would not be able to consistently offset the speed of list.insert

[robust canyon]

im confused on what this is asking again. for example, is it asking:

with input arr [1,2,3]

median of [1]
median of [1,2]
median of [1,2,3]

[lone magnet]

I’m trying to come up with an O(n) solution for this. Can someone help me out?

def questiontwo(arr, n):
    if n <= 0:
        return None
    if n == 1:
        return arr[0]
    res = 1  # O(1), we'll keep the result here
    for s in range(n):  # O(n)
        # s is now the size of the subarray we're checking
        product = mul(arr[:s])
        res = max(res, product)
        i, j = 0, s
        while j < n:
            product *= arr[j]
            product /= arr[i]
            res = max(res, product)
            i, j += 1
    return res

This is what i have so far but im afraid this is O(n^2)

[naive oak]

you might want to have a look at kadane's algorithm

this is essentially the same thing with products

in fact if you take logarithms then it is the same problem

[lone magnet]

i think thats exactly what i was looking for

continuous sum of subarray, now i can implement the multiplication version of it

thank you

[modern gulch]

Fwiw, my initial thought was dynamic programming, to avoid re-computation of common products.

But that’s not going to get you O(n)

[lone magnet]

I was thinking more of a sliding window approach but i cant seem to get lower than n2 because i need two loops for 1. keeping the size of current subarrray 2. the computations

I ended up doing a n^3 in the actual exam, now that im retaking it i feel like i can do better

[lone magnet]

I'm not sure if this is o(n^2) though, im not sure how "while j < n" part contributes to the time complexity

since j is always smaller than n

[modern gulch]

Oh, maybe this isn’t so bad: iterate, maintain largest product so far. Reset when product shrinks (multiplied by less than 1.0), etc. Seems like O(n)

Just a single iteration/loop

[lone magnet]

Why reset when when product shrinks? Something bigger might come up later to kinda neutralize it

[haughty mountain]

or as mentioned, take log of all entries and you have the sum version

[modern gulch]

(Yah, I was just thinking about the DP approach)

[modern gulch]

Not reset, but I think there’s a somewhat inductive approach here, knowing the max to date and the max at each point. If you know max at previous point, then you can check if the max at current point is greater. I need to noodle on this.

[lone magnet]

please noodle on this

[modern gulch]

If at index 2, the max could either be 1*2 or 2. At index 3, the max is either max(previous) * 3 or 3. And so on, right? (I’m typing on phone so excuse lack of brackets)

[haughty mountain]

Kadane's algorithm

[modern gulch]

Oh. 🙂

Oh yah, hah, I didn’t really look thinking it was something cleverer

Then why bother with the logs?

[haughty mountain]

log convert the product version into the sum version

[modern gulch]

Yah, I get that, but seems like an extra perhaps unnecessary operation?

[haughty mountain]

the point is just that it reduces to a well known O(n) algo

it would be a slightly more interesting variant if zero was allowed

[modern gulch]

Ops question did have an interesting constraint: positive only.

[haughty mountain]

wait...

oh nvm

yeah, 0 is what would cause issues

managable issues, but issues nonetheless

[modern gulch]

I guess you already have O(n), but if I was microoptimizing, and it’s positive only: I wonder if you could leverage the points where value < 1. Just compute product until hit a < 1, no need for a max comparison.

[haughty mountain]

positive only is what makes it equivalent to Kadane's algo

[modern gulch]

Yah, I just don’t like the logs :), but, I care about the C 🙂

[haughty mountain]

you don't need the logs

just switch + to * and - to /

(and 0 to 1)

a fun variation: what if 0 was allowed?

what breaks?

can it be fixed?

[rare laurel]

Just solved https://www.codewars.com/kata/648f2033d52f51608e06c458, then realized that it was.. supposed to be like 1000 times easier.
My solution: ||https://paste.pythondiscord.com/eluyomibat||
Efficient solutions are like: ||```py
def count_skills(tree, required):
skils = set()
for r in required:
while r not in skils:
skils.add(r)
r = tree[r]
return len(skils)

[outer rain]

you can do it in O(n) if you really want to

||you can counting-sort the indexes and do the two-pointers thing|| nope, probably not right

[outer rain]

one sec, it's a little more difficult than I anticipated lol

[haughty mountain]

I think this solves the question
||https://en.wikipedia.org/wiki/Skip_list||

[outer rain]

Ok sorry, I give up. I don't know if it is possible now. Here is my idea if you want to elaborate yourself, I fail to implement it, so maybe it's just not possible at all:
||First of all, there is no need to have the initial array set to something. We can do a trivial substitution index = list(range(len(target))) + index and nums = target + nums. This means that target can be considered empty, and we just look at the operations we do to it. Now, let's distribute the events of insertion into buckets by the index we provide, counting-sorting them. For example:||

||```py
index = [0, 1, 2, 3, 4, 5, 1, 5, 0, 1, 1]
nums = [1, 2, 3, 4, 5, 6, -1, -2, -3, -4, -5]
events: list[list[tuple[int, int]]] = [[] for _ in range(n)]
for time, i, x in zip(range(n), index, nums):
events[i].append((time, x))

now events = [[(0, 1), (8, -3)], [(1, 2), (6, -1), (9, -4), (10, -5)], [(2, 3)], [(3, 4)], [(4, 5)], [(5, 6), (7, -2)], [], ...]

so we read it as follows: element 1 was added at index 0 as the event #0, element -3 was added at index 0 as the event #8, etc.

||Now, let's backtrack. We know that at index 0 is the element of the *latest* event of that index. So in our example, the first element of the result array is -3. Now, the next element is either *some* element with a smaller index, or the element at the next index with a bigger time value. I though it would be easy to find the element with a smaller index in some way by tracking "the time we are at" with a second pointer on that same bucket-structure, but it looks like it's not as simple as I though. I am probably either too tired to see a proper way, or this is actually difficult. But if I was that simple, and if we could do it in O(1) amortized, this means that now we have a pointer which either increases by one, or decreases by some value we can easily calculate in O(1), so this this O(n).||

[robust canyon]

little bit confused on binary trees, I know there's a bunch of different types, but should I make insert functions for each type (i.e. insert as a full binary tree), or should I just make functions to check what kind of tree they are?

[fiery cosmos]

Hi, I'm trying to learn data structures and algorithms. I have tried Hackerrank and LeetCode, but do you happen to know of any other websites or resources where I can effectively and thoroughly learn data structures and algorithms? I'm looking for the best possible options.

[vocal gorge]

This solution, say: https://leetcode.com/problems/create-target-array-in-the-given-order/solutions/549583/o-nlogn-based-on-smaller-elements-after-self/

[fervent saddle]

look at all those "O(n)" solutions.

class Solution:
    def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]:
        target = []
        for idx in range(len(nums)):
            target.insert(index[idx], nums[idx])
        return target

[haughty mountain]

O(n) where n is the runtime of the algorithm

[velvet plume]

Can someone please help with this - https://stackoverflow.com/questions/76615910/why-is-my-gaussian-elimination-algorithm-failing

[sterile dove]

guys anyone best resources to master dsa pls...

[azure osprey]

What kind of DSA questions get asked in an interview on a basic level?

[raven steeple]

linkedlist, tree

what can be the worst time complexity for set intersection , it can be O(n^2) right, as there can be a case where lookup can become O(n) in hashtable due to n collisions?

talking about https://leetcode.com/problems/intersection-of-two-arrays/description/, we should sort and use 2 pointer here right for O(n)

[haughty mountain]

nothing that advanced

[modern gulch]

I used to ask BFS, because 9/10 people don’t remember making it a nice problem to talk through.. Everyone remembers DFS. Yes, for real, most cs grads can’t remember how to BFS.

[pure fiber]

Hi guys, i would appreciate your help with my little problem

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

[haughty mountain]

which means they don't know how to write an iterative dfs

if they had known that they had known bfs as well

[modern gulch]

Yah, I should say, everyone seems to remember a recursive DFS.

[haughty mountain]

it's kinda sad

considering the iterative version gets you dfs, bfs and Dijkstra for free

just by swapping between stack, queue, priority queue

[modern gulch]

Yah, so I’d usually have to give interviewees a hint (about a queue or stack) and most could work it out from that point… rarely would anyone get it right (and if so, I’d just ask another question that they didn’t know… because I wanted to see how they work through a question).

[somber mango]

hello guys

my question is very simple

I have this code

import numpy as np

a = np.vstack(([1,2,3],[4,5,6]))
a = np.matrix(a)

b = np.array([1,1,1])

for c in a.dot(b)[0]:
    print(c)

I do a simple matrix vector product

and would like to access each scalar of my vector result separately

but for some reason i cannot seem to figure out on my own, I can't do this

I tried to iterate over a for loop but that doesn't do the trick

can anyone provide some assistance please ?

thanks

[azure osprey]

I got asked about time complexity of a custom sort algorithm and fucked up right there

And a few more in which i fucked up equally

[robust dagger]

Do you just want:

a = np.vstack([[1,2,3],[4,5,6]])
b = np.array([1,1,1])
for c in a @ b:
    print(c)

?

[rough lynx]

I'm generating a large list of combinations based on 10 items which each may have 2-10 values, and later filter out combinations that shouldn't be possible (IE: item 1 with option A can not be used with item C option 5, etc.)
The problem is that I end up creating over 82 million combinations which is taking up an obscene amount of memory (roughly >40GB)
I figure the best way to optimize this is to filter out the impossible combinations as I'm making the original list, rather than doing so after making a list of all combinations
This is how I'm creating that list now, ad how I filter it out later:

combinations = list(
  itertools.product(
    item_one,
    item_two,
    item_three,
    ...
  )
)

option_names = [
  "item_one",
  "item_two",
  "item_three",
  ...
]

# convert to a list of dicts
combinations_converted = [
  dict(zip(option_names, combination))
  for combination in combinations
]

# example function for filtering out a requirement
def requirement_1(combination: dict):
    """Prevent combination that is not possible"""
    if combination["item_one"] == "A" and combination["item_three"] == "B":
        return False
    return True

# create filtered combinations
filtered_combinations = [combo for combo in combinations_dict if all(requirement_1(combo), ...)]

[vocal gorge]

Just don't use lists for the intermediate steps, pretty much. E.g.

combinations = itertools.product(
    item_one,
    item_two,
    item_three,
    ...
  )
combinations_converted = (
  dict(zip(option_names, combination))
  for combination in combinations
) # this is a generator expression
filtered_combinations = [combo for combo in combinations_converted if all(requirement_1(combo), ...)]

[dense zinc]

def getSumValuesBetweenDates(start: datetime, end: datetime, *dicts: dict)

dicts is a list of dictionaries with keys value and date. What I have to do is return the sum of all the values the dates of which are between start and end

At first my initial thought is to do the simple for and go through the whole list adding whichever value gets into the if, but I'm wondering if there's a better way.

Other things I've thought are to sort the list of dictionaries by date so I know when to stop (once I reach the end date), but I imagine sorting will make this less efficient and the code is less readable imo.

Another idea I had was to do this, but I don't see how this would be more optimal and again, is less readable:

filteredList = [transaction["value"] for dic in dic if dic["date"] >= start and dic["date"] < end]
    return sum(filteredList)

[fervent saddle]

Too bad python doesn't have built-in BST

[vocal gorge]

If you only do this once, there isn't any way to do it faster than an O(n) linear search.

If you have to do many queries with the same dicts but different starts and ends, then yeah, the sort-once-and-binary-search solution would be good - would be O(n log n) to sort at the start, and then it'd be O(log n) for each query.

[vocal gorge]

Personally I'd probably write it as a one-liner like

return sum(trans["value"] for trans in dicts if start<=trans["date"]<end)

[fervent saddle]

What if you need to add more keys later?

[vocal gorge]

Not sure what you mean

[fervent saddle]

As far as the sorting solution goes.

[vocal gorge]

Ah

well, it'd be an extra O(n) each insertion, I guess, to recalculate the list of sorted-by-date-cumsums

maybe there's a tree solution I'm not thinking of

yeah, seems to me you could store all the dates in a binary tree, and to a span search on the tree to find sums

it'd be the same for queries, but allow cheaper changes to dicts

[dense zinc]

Yeah this makes sense

Thanks!

Also, what would make good unit tests for this? I've done with an empty list, with items on each border of the dates, negative values... I can't think of more, I'm unsure if there's like a standard procedure for tests since I've done very little on them

[vocal gorge]

Not sure; most times I write unit tests, it's to test that a clever algorithm I have produces the same result as a dumber but definitely-correct algorithm, and for these I usually use randomly generated data.

[dense zinc]

I get you, since mine is a dumb algorithm from the start it's difficult to use your approach

[vocal gorge]

Yeah, pretty much - if it was one of the binary-search solutions I'd compare it with the basic linear search one.

[fiery cosmos]

can someone help me solve some code

[robust canyon]

what's the right way to DFS a binary tree? i understand the concept of DFS, but do we go down the right or left subtree first?

[agile sundial]

doesn't matter

[robust canyon]

kinda figured, thanks

[haughty mountain]

DFS isn't a unique thing

anything that goes deep first is a dfs

[dense zinc]

I'm given a string like: "2018-02-25T08:00:00.000Z" and want to convert it to datetime. I've found about the strptime function, but I can't seem to find the right format for this string. I don't know how to represent the 000Z at the end. At first I thought it was %f but that's 6 decimals. I don't know what I'm missing

[lean walrus]

08 - hours
00 - minutes
00 - seconds
.000 - milliseconds
Z - timezone?

[dense zinc]

No idea about Z, I thought it was just a static letter. But the milliseconds flag is a 6 digit number, not 3

So I'm a bit lost

[lean walrus]

Hmm

[modern gulch]

Z is Zulu time.

Or zero hours ahead of gmt

That’s an iso 8601 string

!d datetime.datetime.fromisoformat

[halcyon plank]

datetime.datetime.fromisoformat

classmethod datetime.fromisoformat(date_string)```
Return a [`datetime`](https://docs.python.org/3/library/datetime.html#datetime.datetime "datetime.datetime") corresponding to a *date\_string* in any valid ISO 8601 format, with the following exceptions:

1. Time zone offsets may have fractional seconds.

2. The `T` separator may be replaced by any single unicode character.

3. Ordinal dates are not currently supported.

4. Fractional hours and minutes are not supported...

[robust canyon]

how important are binary tree types? is it necessary to be able to identify them? i get the feeling that they aren't that important, but i dont know

also, binary trees and binary search trees are different, right?

of course a binary search tree is a binary tree

[modern gulch]

Why do you ask? To me, it’s just a fundamental concept that arises in many forms.

[robust canyon]

im just wokring my way through data structures by recreating some of them in code. what do you mean by "rises in many forms"?

[snow anvil]

Binary trees are a core concept that underpins a lot of algorithms for example a binary heap as a priority queue or avl trees for fast searching

[robust canyon]

ah ok, so binary search trees are different?

[snow anvil]

well they are a subtype of binary trees

[robust canyon]

yea thats what i meant, thanks, that helps a lot

[robust canyon]

should you be able to delete the root from a binary tree? it doesn't seem like you should be able to, i just wanna check

[shy iris]

I was trying to find a dict in a list of dicts, and extract the values as an array:

missingRowInfo = list(
    row.values()
    for row in self.__missingRows
    if row["Id"] == dataRow[0]
)[0]

Is there a better way that doesn't involve getting the [0] index from the list? Otherwise I get something like [["Id": 2, "otherData": True]]

[modern gulch]

You could flatten it with a nested comprehension, maybe something like [value for row in … for value in row.values()]

[modern gulch]

Just not exactly sure what you’re aiming for

[shy iris]

what does that flatten comprehension look like? I was trying to do that within one statement

[modern gulch]

Try it out, it’s just two for loops

Here’s a link that provides a few examples of nested comprehensions. The syntax always screws me up (I feel like the for’s should be in opposite order) https://www.geeksforgeeks.org/nested-list-comprehensions-in-python/amp/

[naive oak]

next(row.values() for row in self.__missingRows if row['Id'] == dataRow[0])

[shy iris]

beautiful this works thanks, I will look into next()

[shy iris]

ty for the link, I think I get the concepts but was struggling with the syntax for how to add another flatten function in the code I posted

[modern gulch]

Yah, it can be easier to just write it as for loops and avoid comprehensions, especially when just trying to get the logic right

[rough lynx]

This worked like a charm! I should've just gone with generators in the first place, I was too focused on trying to pre-emptively filter out the possible results to think of that
Now my question is, how can I write out the contents of the generator without converting it into a list or tuple beforehand - any ideas here?

Just doing json.dump([combo for combo in combinations], outfile, indent=4) has the same effect as me convering the entire generator to a tuple of the results and then writing it out to the file

I suppose I could iterate over each combo and append it to the file instead of writing the whole object to it?

pathlib.Path("combinations.json").unlink(missing_ok=True)
with open("combinations.json", "a") as outfile:
    outfile.write("[\n")
    for combo in combinations:
        json.dump(combo, outfile)
        outfile.write("\n")
    outfile.write("]\n")

Seems to have done the trick

[opaque citrus]

I have a program that converts a given frequency to musical note (C4, A1, etc) for eight octaves. Rather than iterating through all the notes in eight octaves, I compare the frequency to the 'B' note in each octave so that i can find the lowest possible octave and skip testing notes in octaves whose notes are less than the given freq. i am wondering if there wouldn't be a more efficient way of doing this

min_frequency = 16.35
max_frequency = 7902.08

min_octave = 0
max_octave = 8

middle_note_frequencies = {
    'C' : 261.63,
    'D' : 293.66,
    'E' : 329.63,
    'F' : 349.23,
    'G' : 392.00,
    'A' : 440.00,
    'B' : 493.88
}

def getFrequency(note, octave):
    return middle_note_frequencies[note] / (2 ** (4 - octave))

def getNote(frequency):
    # determine the lowest octave
    floor_b = min_octave
    for i in range(min_octave, max_octave):
        if (getFrequency('B', i)) <= frequency: 
            floor_b += 1
        else:
            break       
    # start iterating at the lowest octave
    for j in range(floor_b, max_octave + 1):
        # for each note in the octave
        for x in middle_note_frequencies.keys():
            # is the user frequency close to the note frequency?
            if abs(getFrequency(x, j) - frequency) <= 1:
                return (x + str(j))
    return None

[sterile dove]

hi guys im a beginer in programming .

is programming with python is effecient or any other language ? pls suggest

[frosty plank]

i think it depends on what will you do with python, but I am not sure

[jaunty finch]

In the same boat, and sticking with Python. Goal of building an MVP. Any advice/tips?

Would like to implement a simple matching/routing algo eventually. Any libraries anyone could recommend?

[sterile dove]

how about python for backend dev?

[rough lynx]

Not really the topic for this channel (probably best for #python-discussion), but tl;dr Python is an incredibly versatile language - just look at the number of topic channels in this channel group
There are some performance costs associated with Python but there are similarly many ways to optimize your code without using external libraries or tools, and if you do use those external libraries and tools then you can typically get extremely close to native C performance

[latent moth]

cool

i have a program, the output is "hello world" 😄

[snow anvil]

please stay on topic

[modern gulch]

First thing that came to mind (if this were a df) is use Pandas asof or merge_asof, with a series of the octave frequencies?

[modern gulch]

But, there's certainly a one liner to convert frequency to an octave, a quick google shows this formula: ||O=log(Fu/Fl)/log(2)||

[opaque citrus]

oh right!! that would be essentially solving for octave in the getFrequency() def

[ember igloo]

i'm stuck on https://leetcode.com/problems/stone-game-v/

this is what i have, which TLE's:

class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:

        a = {}
        b = {}
        v = stoneValue

        def f(i, j):
            s = []
            if (i, j) in a:
                return a[(i, j)]
            if i + 1 == j:
                return 0
            if i > j:
                return 0
            if i == j:
                return 0
            for k in range(i+1, j):
                if (i, k) in b:
                    x = b[(i, k)]
                else:
                    x = sum(v[i:k])
                    b[(i, k)] = x
                if (k, j) in b:
                    y = b[(k, j)]
                else:
                    y = sum(v[k:j])
                    b[(k, j)] = y
                if x < y:
                    s.append(x + f(i, k))
                if x > y:
                    s.append(y + f(k, j))
                if x == y:
                    s.append(x + f(i, k))
                    s.append(y + f(k, j))
            a[(i, j)] = max(s)
            return a[(i, j)]
        return f(0, len(v))

[fiery cosmos]

'''
import turtle
import time
import math
from random import randint

font= ('Arial', 16, 'normal')

My_screen = turtle.Screen()
My_screen.bgcolor("light blue")
My_screen.title("Aim screen")

turtle_instance = turtle.Turtle()

turtle_instance2 = turtle.Turtle()
turtle_instance2.penup()
turtle_instance2.hideturtle()

turtle_instance3 = turtle.Turtle()
turtle_instance3.penup()
turtle_instance3.hideturtle()

score=0

My_screen.addshape("ezgif.com-resize.gif")

turtle_instance.shape("ezgif.com-resize.gif")

speed = 1

num = math.floor(My_screen.numinput("Timer", "Enter the seconds", minval=0, maxval=59))
stop = False

turtle_instance.penup()
turtle_instance.setposition(randint(-300,300),randint(-300,300))

def change_position():
turtle_instance.hideturtle()
x = randint(-300,300)
y = randint(-300,300)
turtle_instance.penup()
turtle_instance.goto(x,y)
turtle_instance.pendown()
turtle_instance.showturtle()

def update_score():
global score
score = score + 1
turtle_instance3.clear()
turtle_instance3.write(score, font=("Arial", 15))

def spot_clicked(x,y):

global num
if num > 0:
    update_score()
    change_position()
else:
    turtle_instance.hideturtle()

My_screen.listen()
My_screen.onclick(spot_clicked, 1)

while True:
turtle_instance2.sety(300)
turtle_instance2.setx(-30)
turtle_instance2.write(str(num), font=("Arial", 50))
turtle_instance2.sety(370)
turtle_instance2.setx(-50)
turtle_instance2.write("Time Left:", font=("Arial", 15))
num -= 1
time.sleep(1)
turtle_instance2.clear()

if num <= 0:
    turtle_instance2.clear()
    turtle_instance2.sety(320)
    turtle_instance2.setx(-90)
    turtle_instance2.write("Time Over", font=("Arial", 30))
    time.sleep(5)
    turtle_instance2.clear()
    break
print(num)
My_screen.update()

turtle.mainloop()
'''

Guys i need help. No matter where I press, the score goes up. I want only when i click on the target.

[modern gulch]

update_score() is called in spot_clicked(). It's called every time a spot is clicked.

Perhaps you want to add an if statement to check if the target is clicked, before calling update_score().

[rough lynx]

Also wrap your code with three back ticks at the beginning and end

[fiery cosmos]

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(self.size)]

    def get_hash(self, key):
        count = 0
        for i in key:
            count += ord(i)
        return count % self.size

    def insert(self, key, value):
        h = self.get_hash(key)
        found = False
        for idx, element in enumerate(self.table[h]):
            if element[0] == key:
                self.table[h][idx] = (key, value) 
                found = True
        if not found:
            while self.table[h]:
                h = h + 1
                if h >= self.size - 1:
                    new_size = self.size * 2
                    new_table = [[] for _ in range(new_size)]

                    for bucket in self.table:
                        for key, value in bucket:
                            index = self.get_hash(key)



                            new_table[index].append((key, value))
                    self.table = new_table



            self.table[h].append((key, value))


    def hash_found(self, key):

        index = self.get_hash(key)
        bucket = self.table[index]
        for element in bucket:
            if element[0] == key:
                print(element[1])

            else:
                found = False
                while index < self.size -1:
                    index = index + 1
                    bucket = self.table[index]
                    for element in bucket:
                        if element[0] == key:
                            print(element[1])
                            found = True
                

# Testing the HashTable class
t = HashTable(10)
t.insert('hello', 10)
t.insert('hello',15)
t.insert('helol', 5)
t.insert('helol', 59)
t.insert('heoll', 59)
t.insert('hlelo', 59)
t.insert('hleol', 59)
t.insert('hlleo', 59)
print(t.table)``` can someone pls help my code is only updating certain values when they already exist

and when resisizng the table instead of linear probing all the keys and inserting them into a new list its putting them in a sinlge list

[frosty plank]

This is what I m studying python for, for data science to be more specific

[fervent saddle]

I only skimmed this, but have you tried precalculating all the sums of the v slices?

v_sums = list(itertools.accumulate(v))

Then instead of sum(v[x:y]), you could find it by finding the sum at x and subtracting it by the sum behind y

[fast lynx]

hello , guys am learning dsa and i found like libraries and built-in functions like heapq and priotiyuqueue , can i use them or is it necessary to learn how t implement them manually for maybe interviews or idk

[fervent saddle]

If the interview problem isn't just "implement this built-in data structure", they'll probably just let you use it.

[haughty mountain]

and if the interview problem is implementing a specific readily available data structure that's a pretty bad interview problem

[ember igloo]

thanks, that definitely helps but even with this trick i still get Time Limit Exceeded, updated code below:

import itertools
class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:

        a = {}
        b = {}
        v = stoneValue
        v_sums = list(itertools.accumulate(v))
        v_sums.append(0)

        def f(i, j):
            s = []
            if (i, j) in a:
                return a[(i, j)]
            if i + 1 == j:
                return 0
            if i > j:
                return 0
            if i == j:
                return 0
            for k in range(i+1, j):
                if (i, k) in b:
                    x = b[(i, k)]
                else:
                    x = v_sums[k-1] - v_sums[i-1]
                    b[(i, k)] = x
                if (k, j) in b:
                    y = b[(k, j)]
                else:
                    y = v_sums[j-1] - v_sums[k-1]
                    b[(k, j)] = y
                if x < y:
                    s.append(x + f(i, k))
                if x > y:
                    s.append(y + f(k, j))
                if x == y:
                    s.append(x + f(i, k))
                    s.append(y + f(k, j))
            a[(i, j)] = max(s)
            return a[(i, j)]
        return f(0, len(v))

[robust canyon]

def fill_balanced_tree(self, arr, L, R):
        if L > R:
            return None
        
        #get middle index
        mid = (L+R) // 2
        root = node(arr[mid])

        #recursive calls on the left and right subtree
        root.left = self.fill_balanced_tree(arr, L, mid - 1)
        root.right = self.fill_balanced_tree(arr, mid + 1, R)

        return root

#tree and node structure
class binarytree:

    def __init__(self, root) -> None:
        self.root = root
        self.node_count = 1 

class node:

    def __init__(self, data) -> None:
        self.data = data
        self.left = None
        self.right = None

trying to fill a balanced tree with the sorted input array as [1,2,3,4,5,6,7]. This code only sets the trees root as 5, any ideas on what's going on? I'm very confused

[jaunty finch]

Morning everyone, I’m currently learning Python basics via learn Python the hard way and automate the hiring stuff (as recommended) .. was curious about a beginner friendly intro to DSA? Preferably a book or online resource I can use to do exercises that will build up a good foundation

Any recommendations are welcomed 🙂

Boring stuff*

[robust canyon]

https://runestone.academy/ns/books/published/pythonds3/index.html (from the pins)

theres more in the pinned section too! https://roadmap.sh is also a nice one, the computer science roadmap has a bunch of DSA listed on it

[jaunty finch]

Thanks a ton!

[modern gulch]

Before DSA, you may want to get some proficiency with Python, then take a CS50x style course. A normal freshman year CS program has a CS50x type , followed by a DSA class.

[jaunty finch]

I can see the value in those courses but what if I don’t have the time? I find I learn faster if I have the material to read and more importantly can start coding faster. What would you recommend in this situation?

[modern gulch]

CS50x is an online self-paced course. But, if it's not to your taste, I would review the syllabus to make sure you learn all the pieces. There's not a lot of shortcuts here: there's a certain amount of information that professional programmer are expected to know.

[jaunty finch]

Noted. What if my goal was not to be a professional programmer, but to be skilled enough just to useful and build an MVP for a startup?

[modern gulch]

Oh I dunno… You asked about DSA, so my point was there’s some fundamentals you should know first. More broadly, what you need to know sort of depends on what the mvp entails

[robust canyon]

in a full binary tree, if we have a node with only one child, do we just set the other (the empty) child to none, i.e. a dummy value?

[vocal gorge]

That wouldn't be a full binary tree, I believe.

[agile sundial]

yeah. nodes in a full binary tree have either 0 or 2 children

[wind ore]

Do people talk about algorithms for trading here too?

[mortal rampart]

Does anyone know any good route optimization packages?

[edgy quartz]

open a help ticket and ping me

[grizzled bough]

seems like leetcode is down. doing my first contest there lol.

[robust canyon]

I understand that there are types of binary trees, such as binary search trees, AVL trees, etc. I also understand that there are tree categories, such as a full tree, a complete tree, etc. Is a balanced binary tree a type of tree, or a category? I'm completely confused on the definition of it

To add on to that, should I make functions to interact with a balanced binary tree, or should I just be able to check if a binary search tree is a balanced binary tree?

[umbral seal]

A balanced binary tree is just a tree that all nodes have equal the amount of nodes

So a balanced tree would be all nodes having two children each and extend to the same depth

Use a redblack tree if you are concerned with balancing

redblack by default to its algorithm will be balanced

I don’t see any apparent reason for a function that interacts with a fully balanced tree

You can write a function that recursively traverses the tree and see if the nodes have both children

In fact throughout your traversal you could just see if the node itself is empty or not

One node missing would mean it is not a balanced tree

@robust canyon

So really balancing is more of a state/action

As it is an inherent property within b trees

[robust canyon]

ah ok, that makes more sense. a balanced tree is just a possible state of a tree, and not an actual "type" of tree

[umbral seal]

exactly

Look at red and black trees

Fun to learn and the algorithms used to balance itself are relatively easy to understand

As in the evaluation is binary

(Rather makes the same kind of binary choices to balance as it does to traverse)

[robust canyon]

Yeah, that tracks. I made a function to create a balanced binary tree, but I didn't know if that belongs in its own type of tree, or if it was just a state of it, like you said. per your advice, I'll look into red-black trees next

[umbral seal]

👍👍

[robust canyon]

thanks again!

[upper coral]

Hi everyone
I'm getting prepared for a code interview in algorithms and data structures so I want to practice as much as I can for that interview
So I'm here asking for interest problem that I can try to solve and study for my inteview

[fresh void]

what am I declaring when I declare

newThing = {}

and how do I correctly pass that to a function? 😂

[orchid violet]

you're declaring a dict, and you would just pass the variable to a func, it depends

[humble raft]

leetcode

[bold bear]

Hi everyone, I am looking for resources to learn data structures and algorithms. I am beginner and It would be great if you guys can provide me with some list of resources that can help me to get started. Thanks.

[pliant bough]

I have a specific question on a data structure for my perlin noise program.
Essentially, I generate a random grid of points, then generate a vector of length 1 for each point.
I need to store (preferably in one place):

• X position of the point on the screen ( Xpos )
• Y position of the point on the screen ( Ypos )
• X position of the point in the grid ( Xgrid )
• Y position of the point in the grid ( Ygrid )
• X magnitude of the vector ( Xmag )
• Y magnitude of the vector ( Ymag )

My current plan is to use a big list:
[ [ [Xpos,Ypos, Xmag, Ymag], [Xpos,Ypos, Xmag, Ymag], ...... [Xpos,Ypos, Xmag, Ymag], [Xpos,Ypos, Xmag, Ymag] ]
[ [Xpos,Ypos, Xmag, Ymag], [Xpos,Ypos, Xmag, Ymag], ...... [Xpos,Ypos, Xmag, Ymag], [Xpos,Ypos, Xmag, Ymag] ]
......
[ [Xpos,Ypos, Xmag, Ymag], [Xpos,Ypos, Xmag, Ymag], ...... [Xpos,Ypos, Xmag, Ymag], [Xpos,Ypos, Xmag, Ymag] ]
[ [Xpos,Ypos, Xmag, Ymag], [Xpos,Ypos, Xmag, Ymag], ...... [Xpos,Ypos, Xmag, Ymag], [Xpos,Ypos, Xmag, Ymag] ] ]

My friend suggested I use a 2D list and a class to hold the Xpos, Ypos, Xmag and Ymag, but im not sure how this would work (i havent used any custom data structures yet) @robust canyon

Also, which would be faster for large numbers of values?

[robust canyon]

I don't exactly understand what you're doing here (just because I've done image manipulation like once), but your current plan should work fine. If you want to be fancy about it, you could store each [Xpos,Ypos, Xmag, Ymag] in a class like this:

class XYPos():
  def __init__(self, Xpos, Ypos, Xmag, Ymag):
    self.Xpos = Xpos
    self.Ypos = Ypos
    self.Xmag = Xmag
    self.Ymag = Ymag

But there's nothing wrong with how you're storing the variables, and if you haven't done OOP, I wouldn't worry about it. In terms of speed, the best thing I can think of is just to use list comprehension. Also again, I'm not good at this stuff, so take what I said with a grain of salt.

[pliant bough]

ok thanks

that makes sense

I have done some OOP, but it was a while ago so i might try it to jog my memory

I think list comprehension might be faster because i hope to impliment some concurrent CUDA stuff later, which is quite fussy about input data structures

[lean walrus]

List comprehension is not a data structure, it is a one of a lot of ways to create a list

[pliant bough]

yeah but if I use a list, i can use list comprehension to sort and select items