#algos-and-data-structs

1 messages · Page 56 of 1

solemn moss
#

what's the reason to use it

#

O(n) precalc + O(log) answer will be always enough (and usually faster i guess)
except if you will have problem answer 10^9 queries just for fun

unborn sundial
#

This link will be funny to add to article for showing "domain" in a better way 😄
may be even adding as iframe

regal spoke
#

I'm not sure I understand that map. How are the space bases connected to eachother?

unborn sundial
# regal spoke I'm not sure I understand that map. How are the space bases connected to eachoth...

mm There are Star systems.
Bases are floating in space in them and have X, Y, Z position.
You can move around space system at regular speed in any direction. I joined all relevant star system objects with edges between each other. Weight is equal to normal distance between three dimensional points.
Additionally there is concept of "trade lane", which is speed booster allowing to travel 10 times faster inside a star system. I added their entry points as vertixes and joined with normal edges to other objects in the same system
And added edges inside of trade lanes, with distance divided by 10, to show that you can move faster in them.
You can travel between star systems by Jump Gates and Jump Holes. They literally just connect two star systems in exact locations between them. I added edge between jump holes/gates vertixes with weight 0.
Thus graph was built representing this galaxy map.

regal spoke
#

So the only way to enter/exit a star system is through a Jump Gate or a Jump Hole?

unborn sundial
#

and you have free flight ability (and space filled with different space objects) inside each star system

regal spoke
#

How many warp holes/gates are there in comparision to bases?

unborn sundial
regal spoke
#

But you mentioned like 2000 nodes earlier

haughty mountain
regal spoke
unborn sundial
#

only Space Bases matter to calculate distances as starting points, everything else is intermediate travel point

unborn sundial
# regal spoke But you mentioned like 2000 nodes earlier 
total_systems 119

# vertix counts:
total_bases 550 # in addition i should try exclude Space Bases in dead systems, or that have no shop capabilities
total_jumpholes 425 # jumpgates included
total_tradelanes 1252 # i should remove intermediate vertexes in tradelanes for some optimization. there are some vertex noise that can be optimized
graph.vertixes= 2199 edges_count= 14372

Extracted precise numbers for fun. Excluded some not important stuff in addition

#

that will eliminate some additional starting points for Dijkstra calculations

regal spoke
#

Floyd warshall runs a lot faster too with fewer nodes

unborn sundial
#

a point, a point.

#

but sequential floyd is rather slow in general

#

and algorithm for parallel floyd is rather cucumbersome to make due to lack of any code examples

regal spoke
#

Floyd is great for dense graphs

unborn sundial
#

we can say my graph is sparse enough for Dijkstra stuff being better
I received twice faster calculations with DijstraAPSP without parallelizations

regal spoke
unborn sundial
#

sparsing only from limited jumpholes/gates connections between systems
And currently it is sparser because intermediate travel points in trade lane flight boosters are connected only with trade lane vertixes of same trade lane. Only entry and exit poitns for tradelanes are dense connected with other objects in star system. made this optimization purely for performance speed

storm sun
#

What dsa should I most concentrate on

#

For software engineering

regal spoke
#

Here is what I'm thinking. Solve all pairs shortest path for each system separately.

storm sun
unborn sundial
#

there will be no point i think doing that

regal spoke
#

No there is a point. Each system is small in comparison to the whole thing

unborn sundial
#

yeah

regal spoke
#

Also the graph is dense in each system, so Floyd warshall will be super efficient

unborn sundial
#

but how we will be combining final data then into distances for trade routes across multiple star systems? 🤔

regal spoke
#

Now create a graph with one node per base, and one node per pair of warp holes/gates

#

Create edges between the nodes with weights given by your previous calculation. But don't add any edges between base node, because we don't need those

unborn sundial
regal spoke
#

Ye

unborn sundial
# regal spoke Ye

Briliant ^_^ that will probably help reaching calculating speed to the level of less than 0.2 second (currently having 1.5s as best result)

unborn sundial
#

with such changes it will be probably 10 times faster calculations once again

grizzled cosmos
#

Can anyone help me to write the program of battleship problem? I am not understanding it correctly.

naive oak
#

just had a competitive programming comp, and one question in particular I spent like 2 hours on but kept getting TLE
given an unsorted array of positive integers, print all the indices such that if you remove that element, then the resulting array can be partitioned into two subsets with the same sum

#

I tried sorting the array and then doing a 3d dp of like dp[k, i, j] = there exists a subset of the first j numbers that sum to k that doesn't include i and putting results in a separate thing if i > j to try and squeeze some caching out, but that didn't work

#

the comp is over now to be clear

haughty mountain
naive oak
#

actually wait it might've been 300

#

lemme check

#

it was 300

haughty mountain
#

that feels bruteforce-able

naive oak
#

you mean iterate and do 2 partition for every element?

haughty mountain
#

or hmm...it's close

naive oak
haughty mountain
#

oh wait maybe it is just the usual dp, but with 300 different backtrackings

naive oak
#

I'll try it later tonight and see if it's fast enough

haughty mountain
haughty mountain
naive oak
#

what's the difference?

haughty mountain
haughty mountain
#

you deal with removing an element when backtracking when trying to find a solution for sum (S - x)/2 in that array

#

actually...will that work? you need to make sure the x goes in neither partition pithink

naive oak
#

is the dp still dp[i, j] = there exists a subset sum of i with the first j elements?

haughty mountain
#

yeah

naive oak
#

wait

haughty mountain
#

and the first condition is trivial, it's just the sum of everything except the item

naive oak
#

how do you figure that out from the full dp table?

haughty mountain
naive oak
#

yeah

#

I still don't get that bit

#

would it be feasible to make two dp tables, one for the first j elements and one for the last j elements, and then do 2 sum on each index?

haughty mountain
#

actually I might have lied about which dp I wanted

naive oak
#

o

haughty mountain
#

I think I just want whether sum S is reachable or not

#

so just a 1D dp

naive oak
#

how do you fill that up tho?

haughty mountain
#

!e writing code without testing, but something like

arr = [1, 2, 7]
S = sum(arr)
reachable = [False]*(S+1)
reachable[0] = True
for x in arr:
  for i in range(S+1):
    if i - x >= 0:
      reachable[i] = reachable[i] or reachable[i - x]

print(reachable)
halcyon plankBOT
haughty mountain
#

wait...I need to loop backwards

#

!e

arr = [1, 2, 7]
S = sum(arr)
reachable = [False]*(S+1)
reachable[0] = True
for x in arr:
  for i in reversed(range(S+1)):
    if i - x >= 0:
      reachable[i] = reachable[i] or reachable[i - x]

print(reachable)
halcyon plankBOT
haughty mountain
#

!e and with backtracking

arr = [1, 2, 7]
S = sum(arr)
reachable = [False]*(S+1)
reachable[0] = True
for x in arr:
  for i in reversed(range(S+1)):
    if i - x >= 0:
      reachable[i] = reachable[i] or reachable[i - x]

print(reachable)

# The usual backtracking.
target = 8
assert reachable[target]
solution = []
for x in arr:
  if reachable[target - x]:
    solution.append(x)
    target -= x

print('one solution:', solution)
halcyon plankBOT
haughty mountain
#

I think if you just do len(arr) different backtrackings, each skipping one element, you can find the relevant thing

haughty mountain
#

this (S-x)/2 is guaranteed to be a subset of the S-x set in this thing, which should be the key thing for correctness

#

since it means the other disjoint subset exists and doesn't contain that one x

haughty mountain
naive oak
haughty mountain
#

just an arbitrary example

#

backtracking to find a solution with sum 8

naive oak
#

right

haughty mountain
#

so the idea would be to run this backtracking len(arr) times

#

each skipping some index

naive oak
#

sounds good

#

I'll try it out when I'm back home later

#

do you want the other question I didn't manage to solve?

haughty mountain
#

feel free to drop that too, someone will probably have ideas

naive oak
#

it's kinda weird to explain so gimme a bit

haughty mountain
#

the problem statement isn't available?

naive oak
#

it is but it'd be annoying to grab it rn so I'll just paraphrase

#

two players are playing a game on a simple graph. they take turns choosing vertices. if a player chooses a vertex neighboring an enemy vertex, they gain a point (1 point for each neighboring enemy vertex). they proceed until no vertices are left, and then whoever has most points wins. if both players play optimally, figure who would win (or tie)

#

for example, if you play on K3, it's a tie because player 1 chooses some vertex, player 2 chooses another vertex and gains a point, and then player 1 chooses the last vertex and gains a point

#

I just essentially simulated the game with recursive backtracking and it worked, just TLE because it was O(|V|!)

#

maximum of 20 vertices

#

@agile sundial this is question E btw

dull dawn
#

going straight to the point
i'm trying to generate provable fair numbers for some project i have
and chat gpt + some refactor i made ended up in this. but i have no idea what i'm doing, maybe some harvard mathematics
engineer can check up this code and tell if its really fair
code:

class Game:

    def __init__(self, seed: str = None) -> None:
        self.secret = secrets.token_hex(32)
        self.seed = (
            seed
            if seed
            else "".join(
                secrets.choice(string.ascii_letters + string.digits) for _ in range(16)
            )
        )
        self.nonce = str(int(time.time()))

    def generate(self, amount: int = 1, min: int = 0, max: int = 24):
        numbers = set()

        for iter in range(amount):
            message = f"{self.seed}:{self.nonce}:{iter}"
            hash_bytes = hmac.new(
                self.secret.encode(), message.encode(), hashlib.sha256
            ).digest()

            for index in range(0, len(hash_bytes) - 8 + 1, 8):
                if len(numbers) == amount:
                    break

                number = struct.unpack(">Q", hash_bytes[index : index + 8])[0]
                number = number % (max - min + 1)

                if number not in numbers:  # Check for uniqueness
                    numbers.add(number)

        return list(numbers)
gritty quail
#

Im trying to make a Response class that all my functions can return. However I want any instantiation of said class to behave like the datatype of the first attribute:


token = "hjdkfhujksjhfiuhjkfhs"
loginresp = Response(token, "Done")
print(type(loginresp)) # class of Response, I want this to be class of string or whatever the first parameter in Response is.

print(loginresp.message) # Should output "Done"
print(loginresp) # should output token
#

Is there any way in which this is ever achieveable

fiery cosmos
#

Hi, anyone here has ever made an algo for MT5? Is yes, do you find that python can be as robust as MQL5 in fast-moving markets ?

regal spoke
#

The tricky thing is how to get it down from 3^20 states, to 2^20 states

naive oak
#

what's the dp?

lean walrus
#

dynamic programming

naive oak
#

no like what's the table storing

regal spoke
#

For the 3^20 dp,

#

Note that each node has either

  1. not been picked yet
  2. picked by player 1
  3. picked by player 2
#

So the state of the game can be described using an integer < 3^20

#

Let dp[state] = (score player 1, score player 2), where both players played optimal

#

You can compute the dp values bottom up

naive oak
#

ah i see

#

would storing p1 score - p2 score also work?

regal spoke
#

Sure

naive oak
#

would the 2^20 dp be something like storing whether each node has been picked yet, and the table stores like dp[state] = min(player1 - player2) if it's player 2's turn otherwise max(player1 - player2)?

regal spoke
#

hmm actually

#

Suppose player 1 gets a point for each neighbouring node that has previously been picked (by either player), and loses 1 point for each neighbouring node that has not yet been picked, and player 2 never gets any points.

#

I think this should be equivalent to the game you described (equivalent as in the two games have the same score difference if you play the same in both games)

#

But in this modified version of the game, for the state it doesn't matter which players owns a node

#

Do you follow?

outer rain
#

it's binom(20, 10, 10, 0) + binom(20, 10, 9, 1) + binom(20, 9, 9, 2) + ...

#

surely it's not that much..

regal spoke
outer rain
#

741365049

#

well damn :(

regal spoke
#

Anyways the equivalent game I mentioned above works

#

It can be simulated with a 2^20 state

#

Pretty sure that is intended

naive oak
regal spoke
#

Then there is a cool trick

#

You can add/remove numbers from the array, and then update the DP values accordingly

regal spoke
haughty mountain
#

you don't need to do that is this case, do you?

#

you can deal with the removal when backtracking to check if a solution exists

regal spoke
#

You don't need any "backtracking" the way I would do it

haughty mountain
#

but you get the solution I'm suggesting?
it's something like O(sum * n) for the reachable DP and then O(n^2) to backtrack n times

#

I'm guessing you want to do some fancier DP?

regal spoke
#

Mine would be O(sum * n)

haughty mountain
#

so effectively same complexity-wise, but I guess you would store some more state

regal spoke
# 
def solve(A):
  n = len(A)
  m = sum(A) + 1

  dp = [0] * m
  dp[0] = 1  
  def add_number(x):
    for i in range(m - x)[::-1]:
      dp[i + x] += dp[i]
  def remove_number(x):
    for i in range(m - x):
      dp[i + x] -= dp[i]
  
  for a in A:
    add_number(a)

  ans = []
  for i in range(n):
    remove_number(A[i])
    cur_sum = sum(A) - A[i]
    if cur_sum % 2 == 0 and dp[cur_sum//2]:
      ans.append(i)
    add_number(A[i])
  return ans
regal spoke
haughty mountain
#

did you mean to add all numbers to dp first?

regal spoke
#

oh ye

#

fixed

#

I need to add one thing more to make this run fast

#

The dp values can become really large, so the trick is to pick some random large prime

#

and then store all dp values modded by that prime

haughty mountain
#

I suspect this would end up slower than my thing pithink

regal spoke
haughty mountain
#

the first step of adding all the numbers is the same (other than me using booleans, so no big values)

and then the work per element is O(n) rather than O(sum) twice in your case

regal spoke
#

Tbf, the code I posted can be speed up by a ton

#

You don't need to modify dp if you are smart about it

haughty mountain
#

untested, but my thing would be something like this, broke stuff out into functions just to make the parts clearer

def backtrack_possible(reachable, values, target):
  for x in values:
    if target - x >= 0 and reachable[target - x]:
      target -= x
  return target == 0


def solve(arr):
  # Typical DP.
  S = sum(arr)
  reachable = [False] * (S + 1)
  reachable[0] = True
  for x in arr:
    for i in reversed(range(S + 1)):
      if i - x >= 0:
        reachable[i] = reachable[i] or reachable[i - x]

  def arr_without(ix):
    return (x for i, x in enumerate(arr) if i != ix)

  # Backtrack, but removing some value.
  res = []
  for i, x in enumerate(arr):
    if (S - x) % 2 != 0:
      continue
    target = (S - x) // 2
    if backtrack_possible(reachable, arr_without(i), target):
      res.append(i)

  return res
regal spoke
#

Can't you be tricked in backtrack_possible to backtrack into a path that requires arr[i] to reach 0

#

While there is a different path that works

#

Suppose arr is [3,1,2,1,6,4]

#

And i = 0

#

@haughty mountain this should be a counter example

#

1+2+4=1+6=7

#

But the backtrack will do 7-1-2-1=3 and then get stuck

haughty mountain
#

pithink you're saying I pick a path that would have required the 3

regal spoke
#

Yes

haughty mountain
#

yeah ok, the idea might just be broken

lucid geyser
#

Hi HELP :
js exceptional error 503

haughty mountain
#

not the right channel, not the right server 🥴

regal spoke
#

Btw there is a way to use a Boolean reachable dp

#

Make one for prefix, and another one for suffix

#

They can be used in combination to effectively skip index i

fair sky
#

guys how can i import chatgpt in a scratch projecy

unborn sundial
# regal spoke Inside each system, your graph is dense, right?

made all final touches to the stuff ^_^
https://darklab8.github.io/blog/article/article_shortest_paths.html
In the end decided not building second graph with lesser vertixes
Because just with joining vertex for Trade Lanes of same structure i decreased vertex count from 2218 to 1218 count. building second graph to have 900 vertixes i think not a big point.

Removed Johnson's algo parts, stripped down to Dijkstra APSP.

And added path reconstructions capabilities to it.

So i get now for 1218 vertex and 22896 edges, okay enough 1.5 seconds speed to find all shortest paths ^_^

#

The final result is used for the game data navigational tool that provides the trading routes with profit per time 😎 as well as telling where to go for this shortest path

darkstat_tab_trades.png
lilac cradle
#

is there a way to rotate points in 3d space without using something like scipy or matrices?

haughty mountain
#

quaternions

lilac cradle
#

right but with what

haughty mountain
#

idk what implements it

#

it wouldn't be hard to implement yourself

lilac cradle
#

i might

haughty mountain
#

or just suck it up and use matrices and linear algebra

lilac cradle
#

i implemented matrices but i doubt its going to be performant

#

kind of annoying how much overhead it seems you need just to rotate shit

haughty mountain
#

should be pretty performant

lilac cradle
#

i might just hardcode the equations for rotation

haughty mountain
#

it's just one big matrix multiplication to transform a bunch of points

lilac cradle
#

ive already done that for 2d but 2d is simple

lilac cradle
#

well i guess i could cache it or some shit

haughty mountain
#

you're doing a bunch of rotations to single points?

lilac cradle
#

yeah
trying to orient blocks but they put the axis of rotation off center so i need to account for that

#

so i can't just set the angle value

#

also would numpy be good for lots of small vector operations? im considering using numpy in the backend for my vector code but idk if that would even help much

opal oriole
lilac cradle
#

im aware

haughty mountain
lilac cradle
opal oriole
#

If you don't like quaternions, you can use rotors instead, very similar implementation though, just easier to understand.

haughty mountain
lilac cradle
#

so these are all at the same position but different angles, which is annoying when using stuff like this because it fucks up things when i want it rotated

image.png
lilac cradle
opal oriole
lilac cradle
#

thanks

lilac cradle
opal oriole
# lilac cradle cause

It's a geometric algebra thing, and they do rotate things. Better than "quaternion" (wow, "quat," it has four parts, how descriptive).

haughty mountain
#

rotor math would be the natural search term

lilac cradle
#

fair

opal oriole
#

Main feature of GA is that things have nice visualizations, so it's easier to debug and reason about. Also not 4D (not the awkward extra dimension needed).

haughty mountain
opal oriole
#

(Btw the reason it seems so strange to have to go to quaternions suddenly for rotations of vectors is because vectors come from quaternions, quaternions came first, and the vector part was separated out (now just called a "vector") because people found quaternions too hard to understand, from this the cross product was born to fill the gaps, but it only works for 3D and causes other issues...)

#

(Separated by Gibbs and Heaviside for the physicists to understand and use)

#

(GA unifies all of this, so we don't have this mess of all these separate things, including all the other stuff (all these things physicists come up with for the specific problems))

#

(sign up for the GA cult community)

haughty mountain
#

actual photo of squiggle

Hermann_Gramann.jpg
lilac cradle
#

uh how to you make a bivector

#

i cant find much information on what its actual components are

#

its apparently just like a vector in terms of its values but idk how it all works out

opal oriole
lilac cradle
#

yeah that code is bizarre and i believe actually evil

#

it also literally just declares it like a vector

opal oriole
#

It's C++.

lilac cradle
#

im not convinced theres an actual difference

image.png
opal oriole
#

It's a different object, both may have 3 floats, but they behave differently.

#

Like how I can have 3 floats for a 2D position and health or something, not the same as 3D position, just both can use 3 floats.

lilac cradle
#

the code also literally only declares it and gives it a single method afaik
all the rest is rotors

opal oriole
#

Yup, you only care about wedge.

lilac cradle
#

i guess i can just implement that into vectors then instead of making a whole new class for it

opal oriole
#

You can, but it's technically not type safe/correct.

#

Since it's a different object/type technically.

#

Represents something else.

lilac cradle
#

i can just subclass it probably

opal oriole
#

It's just kind of coincidence both are just 3 floats.

#

What really matters is the functions on them.

lilac cradle
#

oh actually speaking of which i should probably redo some of my vector code since i had some of it duplicated (it wasnt returning the right type without it)

opal oriole
#

How you store the internals is up to you, can do it multiple ways.

#

Basically the interface defines the type here, the internals of needing those 3 floats to keep track of the state is an internal detail, which happens to align with the internal details of your vector3.

lilac cradle
#

mmk

#

ok so to return a subclass type i think i can do like self.__class__(blablabla)

opal oriole
#

I would just do a different class.

lilac cradle
#

i mean internally

#

vec2 and vec3 inherit from a generic vec class

#

otherwise it's a bunch of repeated code

opal oriole
#

Yeah, whatever works easiest for you.

#

Can always un-inherit it later and implement stuff elsewhere if needed.

lilac cradle
#

ok yeah it works

#

damn it i cant use 'self' in the actual class declaration

#

so i cant do like 'self.func' in order to then get it to return the right type

regal spoke
lilac cradle
#

ik

#

i might just do 3 2d rotations but that seems a bit much

regal spoke
#

I meant just a single 2d rotation

lilac cradle
#

and how exactly would you change the basis without rotating?

regal spoke
#

Easiest would probably be to use cross product to find the new basis

lilac cradle
#

im declaring a bunch of methods like add, sub ,etc based off of another function because i'm not calling it outside of the class it doesnt work

#

would putting it in __init__ be slower or is it just the same

#

lemme try a classmethod nvm got it to work
i just got one of the inputs and used its class to do it

opal oriole
lilac cradle
#

maybe

#

also i should fix my vectors i think since it has a bug where if you pass other vectors as components it silently errors (sorta, it's kinda intended behavior but kinda not so im gonna remove it to prevent bugs i think)

#

awesome

image.png
fiery cosmos
#

Anybody used pyhhon for MT5 here ?

turbid saddle
#

I am learning Python, and I had an idea while learning the built-in sort() function. But couldn't find this way of sorting exists or not. The bucket sort seems similar to this approach. I am curious if there is any existing research or algorithm that explores this interval grouping and sorting approach.

Can anybody help me with this info, please.

Let’s consider an array with 100,000 numbers, for example: array[] = [3, 5, 7, 3, 6, 3, 67, 8, 332, 75, 53, 5724, 656, 34, 63, 733, 75, 34, ...]. Suppose we define an interval size of 10 with help of Sturges’ formula.

We will create a 2D array where each sub-array contains unsorted data from the original array, grouped by the interval range. For instance:

2D[0] will contain all data from array[] that falls within the range [0, 9].
2D[10] will contain all data from array[] that falls within the range [10, 19].
2D[20] will contain all data from array[] that falls within the range [20, 29].
And so on…

Next, we will flatten this 2D array into a 1D array, new_array[], such that new_array[] contains the elements from 2D[0], followed by elements from 2D[10], then 2D[20], and so forth.

Finally, we will apply the sort() or timsort() function to new_array[]. The question is whether this method will sort the data faster than directly applying sort() to the original array.
haughty mountain
#

it's kinda radix sort

#

I expect if it's written in plain python you won't gain anything

#

actually idk why timsort would gain anything from this pithink

vocal gorge
#

..huh, interesting. Timsort can take advantage of partially sorted arrays, but I think it needs runs, not just regions like these.

haughty mountain
#

timsort benefits from runs of sorted values

#

radix sort is kinda nested bucket sort, and can be plenty fast when it's applicable

turbid saddle
#

timsort() have O(n log n). but in fortunate times it becomes close to O(n). so, I wanted to give semi-sorted value to timsort.

vocal gorge
# vocal gorge ..huh, interesting. Timsort can take advantage of partially sorted arrays, but I...

testing shows it might help a little - I'm getting 13ms vs 16ms normally.

def test_sorting():
    unsorted = random.choices(range(1000), k=100_000)
    buckets = [[el for el in unsorted if bucket_i*10 <= el < (bucket_i+1)*10] for bucket_i in range(100)]
    partially_sorted = [el for bucket in buckets for el in bucket]
    assert len(partially_sorted) == len(unsorted)
    %timeit sorted(unsorted)
    %timeit sorted(partially_sorted)
#

(oh, of course I'm timing only the final timsort, not the initial partitioning. with the partitioning it'd be way slower.)

#

but it's interesting that transforming the array this way helps timsort at all. Perhaps because on the edges between buckets, runs of sorted elements may form?

turbid saddle
turbid saddle
#

but why partially_sorted always takes more time? shouldn't it take equal time?

vocal gorge
#

sorted(partially_posted) takes less, 13ms vs 16ms for sorted(unsorted)

turbid saddle
#

no, sorry, I tried thrice, and got unsorted < partially_sorted.
then again I tried multiple time, I think it's now random.

regal spoke
#

So if you are feeling lazy when implementing merge sort, you can use pythons built in sort for the merge step

silent ember
fiery cosmos
silent ember
fiery cosmos
#

So you're using the API to control the terminal?

silent ember
#

No I am still looking for how to implement it

fiery cosmos
#

I see

#

I think I figured out what I was looking for by myself anyway. What I want to do with the terminal might be impossible or highly difficult to implement

#

I asked on the forum will see

silent ember
#

Okie

#

I wanted to wait to apply what I want with pinescript

#

Then would move on to mt5

crimson salmon
#

where can i find algorithm and data structs

#

?

novel sorrel
novel sorrel
crimson salmon
lone ivy
#

When should I start learning DSA ?

#

Like how comfortable I should be with the language ?

opal oriole
fair moat
#

nice

wintry pine
novel sorrel
#

@wintry pine ofc bro it's one of the greatest websites of all time... Quite informative 🔥❤️

haughty mountain
wintry pine
lilac cradle
#

btw i think i asked this before but is numpy significantly faster if you're doing lots of small operations on small (like less than 10 element) arrays a lot? i think ive heard its better for a smaller amount of large operations on large arrays

haughty mountain
lilac cradle
#

mmk

#

cause like i was like 'hm maybe i should use np arrays internally for my vectors' but idk if that'd really help much

#

rn my vectors store their values internally as a list and function mostly equivalent to a list comprehension or iterating through a for loop in terms of operating on them, just with much more compact and convenient syntax

haughty mountain
# wintry pine then which is?

Depends what you're looking for, I have good resources I can point to for some more advanced topics. For more basic stuff it shouldn't be too hard to find resources

g4g (and w3s) is good at search engine optimization, less good content-wise

lilac cradle
#

i mean 'the best website' for a thing is going to depend on what you want to learn

#

if it's just the language itself then python's own documentation is probably the best i'd think

opal oriole
lilac cradle
#

hm

#

kk

opal oriole
#

Creating and destroying numpy arrays has high overhead.

#

(allocation / deallocation)

#

Or if you are using a game engine like Panda3D, it has its own vector, matrix, and quaternion types too.

lilac cradle
#

ye, i know at least pygame has its own vectors

#

also i think i recreated the function jpeg compression uses for its cosine transform thing
not the mapping itself, but the actual grid it uses

#

the first one is apparently what jpeg uses, right is my own render
the actual parameters are likely a bit off but i think its the same thing

2024-01-22-image-5.webp image.png
#

or maybe it's just that i've managed to approximate it with a different method

#

this is the entirety of the code i used

#=============#
image_res = 512
visual_scale = 72
grid_scale = 12
#=============#
from PIL import Image
import math

def snap_to_grid(n,grid_size):
    return (n//grid_size)*grid_size

sines = []
for i in range(image_res):
    n = snap_to_grid(i,grid_scale)/image_res
    cs = math.cos(n*n*visual_scale*math.pi)
    sines.append(cs)

im = Image.new("L",(image_res,image_res))
image_data = []
for y in range(image_res):
    for x in range(image_res):
        n = (sines[x]*sines[y])/2 + 0.5
        n = int(n*255)
        image_data.append(n)

im.putdata(image_data)
im.save("cos_test_render.png")
#

oh theres a thing that says how it actually works on wikipedia, lemme implement that

iron flare
#

is that normal

image.png
#

how do I execute my script

#

like if I coded a bot that will do something on discord how do I execute it ?
and should I use visual studio pycharm or other ?

swift oracle
#

!get_help

#

🙄

inland viper
#

<@&831776746206265384> suspicious link

slim sparrow
#

what's the fastest way to find LCM of numbers 1...N?

lean walrus
#

possible way: go through all prime numbers p up to N, and multiply your result by p ** floor(log(N, p))

#

it feels like O(N) or O(NlogN)

solemn moss
#

well power is surely not O(1) so nlogn
though we won't have big powers.. but still i think nlogn

#

+the problem is that we need to deal with big integers

#

i guess for something like n=50 lcm 1..n will be already greater than 2^64
yep, 3099044504245996706400 for n=50

regal spoke
slim sparrow
#

Cuz in C++ I had trouble, numbers didn't even fit in unsigned int128

regal spoke
#

But I havent tested it

#

If you really need speed, you should check out how to do it using GMP

#

Thats the library that people normally use when they need fast big integers

#

The module is called gmpy2 in Python
Here is how to do it with math.lcm:

#

!e

import math
res = math.lcm(*range(1, 1001))
halcyon plankBOT
regal spoke
#

Somehting that might be helpful is that lcm(1,...,1000) = lcm(501,...,1000). This could possibly speed things up

haughty mountain
#

can't you be more clever for that range in particular?

#

like for a range 1...n what matters is the largest powers of primes that are <= n

#

ok @lean walrus mentioned that already

lean walrus
#

lcm(x, y) = x * y // gcd(x, y) is O(log(x+y)) (in out case O(logN)) (using Euclid algo) (assuming arith operations are O(1) which is not true)
so if lcm(x, *args) = lcm(x, lcm(*args)), it performs N calls to lcm which are O(logN), so in total O(NlogN)

#

every time i try to take into account the fact, that integer operations are not constant, i get it wrong

turbid saddle
modern gulch
turbid saddle
#

if this sorting algorithm actually works, (which I think have the potential) I want to license it as fully open source

regal spoke
#

It feels like something is wrong when bucket sort is ~10000 times slower than both bubble sort and insertion sort

lean walrus
#

bubble sort is the fastest 💪

turbid saddle
regal spoke
#

I would not trust those numbers

regal spoke
#

So you need to send them copies of the list to be sorted

#

Bubble sort and insert sort are really fast for already sorted data, which is what I'm guessing happened in your benchmark

#

Seems the reason bucket sort is slow is because they are using some weird O(n^2) sorting algorithm

#

That said, your numbers are still absurd

image.png
#

Looks to me like algorithms.sort.min_heap_sort is buggy

#

No way that should take 627s

lean walrus
#

O(N^3)?

regal spoke
#

Probably

#

They claim it is O(n log n)

#

But it doesn't look that way

regal spoke
#

There are two O(n) nested for loops with no break condintion, then inside the inner for loop, there is a while loop that runs log(n) iterations

lean walrus
#

i like wiggle sort

#

recently we had a conversation about counting sort
i was a bit confused because the algorithm i remembered apparently was not called counting sort
today i found it (rather a slight variation of it) in this repo, it is called "pigeonhole sort" 😄
wikipedia, as usual, has something smarter

regal spoke
turbid saddle
#

at first i wanted to used pysort. but it showed error while importing. so I used algorithms. thank you for pointing out that to me.

haughty mountain
#

oh, they are implementing their own crappy heap

#

otherwise heap sort is literally just

heapify(seq)
res = []
while seq:
  res.append(seq[0])
  heappop(seq)
regal spoke
#

Maybe this could be called heapify sort

lilac cradle
#

im not sure if this is the place for it, i asked in discussion but didnt seem that anyone noticed

is there a possible way to make a sort of subtree / element in XML.etree and then, after the fact, 'merge it' to another tree with all its subtags?

#

i might be off in this but i wrote like an example of what i'd like to do in terms of the tags

so going from something like this:

<tag1 />

<tag2>
    <subtag1 blabla=blablabla>
        <subtag2 />
    </subtag1>
    <subtag3>blabla</subtag3>
</tag2>

where tag2 is its own element, to

<tag1>
    <tag2>
        <subtag1 blabla=blablabla>
            <subtag2 />
        </subtag1>
        <subtag3>blabla</subtag3>
    </tag2>
</tag1>

where it's a subelement of tag1

#

with all its subelements moving with it

rancid compass
#

I am cooking up an example now, just gotta run some test cases on it

agile sundial
#

making a montage, i see

#

yeah that looks right

rancid compass
#

here is something that any one can feel free to use, my favorite function for formatting xml elements vvv

rancid compass
#

i have done many different things with xml data structure, and tbh formatting is the hardest part

#

hey everyone, since i was helping with this problem i put together a function that you can call from your lib and pass args to do merging of xml tags for you. it only works 100% effectively on parent tags nested within the root. But yeah basically you call function and pass the xml string arg that i assume you have already parsed from a file, then you pass the target_tag and the tag_to_merge_into, and boom!! done...

#

i also added some pretty formatting built in!!

#

ie... xml_nest.merge(xml_string, target_tag, tag_to_merge_into)

haughty mountain
#

find relevant empty (or self-closed if you can check for that) tag T, move next sibling into T

rancid compass
rancid compass
haughty mountain
#

if you want to do an actual merge things get more annoying, but from the example I assumed this was a much easier case

waxen pewter
#

i need a course in datastrucyures and algo

wintry pine
languid girder
raven shard
#

any alg for converting 2d array into 1d array

narrow mica
# raven shard any alg for converting 2d array into 1d array

in what way?
there's always .flat (or .flatten())

>>> import numpy as np
>>> a = np.array([[1, 2, 3], [4, 5, 6]])
>>> a
array([[1, 2, 3],
       [4, 5, 6]])
>>> a.flat
<numpy.flatiter object at 0x000001C70429E090>
>>> a.flatten()
array([1, 2, 3, 4, 5, 6])
>>>
raven shard
#

what if without libaries

narrow mica
raven shard
#

have a 2d array

narrow mica
# raven shard have a 2d array

there's no array in python without libraries, but assuming you have a 2d list

>>> l = [[1, 2, 3], [4, 5, 6]]
>>> flat = [value for row in l for value in row]
>>> flat
[1, 2, 3, 4, 5, 6]
>>>
raven shard
#

oh thanks

pseudo lynx
#

hi

halcyon plankBOT
#

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

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

rare laurel
haughty mountain
#

(for general chat)

image.png
halcyon plankBOT
#
array.array 

class array.array(typecode[, initializer])```
A new array whose items are restricted by *typecode*, and initialized from the optional *initializer* value, which must be a [`bytes`](https://docs.python.org/3/library/stdtypes.html#bytes) or [`bytearray`](https://docs.python.org/3/library/stdtypes.html#bytearray) object, a Unicode string, or iterable over elements of the appropriate type.

If given a [`bytes`](https://docs.python.org/3/library/stdtypes.html#bytes) or [`bytearray`](https://docs.python.org/3/library/stdtypes.html#bytearray) object, the initializer is passed to the new array’s [`frombytes()`](https://docs.python.org/3/library/array.html#array.array.frombytes) method; if given a Unicode string, the initializer is passed to the [`fromunicode()`](https://docs.python.org/3/library/array.html#array.array.fromunicode) method; otherwise, the initializer’s iterator is passed to the [`extend()`](https://docs.python.org/3/library/array.html#array.array.extend) method to add initial items to the array.
narrow mica
lean walrus
mighty crater
#

Guys do you know a good course where I can learn DSA

lean walrus
#

!res also check pins

halcyon plankBOT
#
Resources

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

mighty crater
wicked basalt
#

is string operation slower than storing chars in a list and doing "".join?

narrow mica
regal spoke
# narrow mica yes, as `str`s are immutable, doing `+=` makes a new string every time (it has t...

https://stackoverflow.com/questions/44487537/why-does-naive-string-concatenation-become-quadratic-above-a-certain-length/44487738#44487738 This is a really good stack exchange post about that.
TLDR: strings in Python do not allocate extra memory (unlike lists that do allocate extra memory to be able to expand), so appending anything to a string is fundamentally O(n) in Python

Stack Overflow
Why does naive string concatenation become quadratic above a certai...

Building a string through repeated string concatenation is an anti-pattern, but I'm still curious why its performance switches from linear to quadratic after string length exceeds approximately 10 ...

#

''.join(list) is definitely the good way to do it

vocal gorge
#

I get uneasy every time this question is asked tbh, because the common wisdom is "concatenating strings is O(n+m)", but, well, it's false in practice. The optimization cpython uses is pretty good.

tribal pond
#

Does anyone knows how to compute Triangular Moving Average?

vocal gorge
#

googling failed me - when I search this term all I find are probably-machine-written articles regurgitating the same content that makes no sense. what's the formula for it?

atomic elm
#

Hey, anyone has any yt vid suggestion to learn Inhereitence in DS

shadow grail
#

I was solving this hackerrank question ... I figured the logic to be a simple if-else ladder and I can't think of any other better way to solve this ...Is there any other way to solve this?
My solution:
if name == 'main':
N = int(input())
list_of_elems = []

for _ in range(N):
    statement = input().split()
    
    if statement[0] == 'insert':
        i, e = int(statement[1]), int(statement[2])
        list_of_elems.insert(i, e)
    elif statement[0] == 'remove':
        e = int(statement[1])
        list_of_elems.remove(e)
    elif statement[0] == 'append':
        e = int(statement[1])
        list_of_elems.append(e)
    elif statement[0] == 'sort':
        list_of_elems.sort()
    elif statement[0] == 'pop':
        list_of_elems.pop()
    elif statement[0] == 'reverse':
        list_of_elems.reverse()
    else:
        print(list_of_elems)
image.png
stiff quartz
#

I don’t think you can do much better

#

It seems that question is just there to test a interviewee basic knowledge of the standard library they said they are knowledgeable in

autumn pivot
#

Hi, I have been primarily using c++ for solving leetcode or algorithm problems in general, now I use c++ for leetcode only, and in the future I might have to do ds/ML for which I def. Have to use python, should I start solving with leetcode with python ? I just want to reduce the number of programming languages so I can focus on few properly and know them in depth. (Currently in the JavaScript environment as well)

haughty mountain
naive forge
#

yo anyone down to grind some usaco problems together

fiery remnant
#

Resources to learn dsa in python?

serene hornet
#

Hi. I'm trying to groupby a list of db rows several times. In Java i would do like groupingBy(Row::customer, groupingBy(Row::department, groupingBy(Row::list))) Can I do something similar with itertools.groupby ?

vocal gorge
#

I'm not sure what it means to groupby several times. Perhaps you're looking for grouping by several columns, like .groupby(["customer", "department", "list"])?

lilac cradle
#

if anyone needs a simple but kinda jank (i think) menger cube algorithm, here's one i wrote yesterday

menger_points = ((-1,-1,-1), (-1,-1,0), (-1,-1,1), (-1,0,-1), (-1,0,1), (-1,1,-1), (-1,1,0), (-1,1,1), (0,-1,-1), (0,-1,1), (0,1,-1), (0,1,1), (1,-1,-1), (1,-1,0), (1,-1,1), (1,0,-1), (1,0,1), (1,1,-1), (1,1,0), (1,1,1))
def menger(steps):
    scales = [3**i for i in range(steps)]
    points = {(0,0,0)}
    for n in scales:
        points2 = set()
        for i in points:
            ix,iy,iz = i
            for px,py,pz in menger_points:
                points2.add((
                (px*n) + ix,
                (py*n) + iy,
                (pz*n) + iz,
                ))
        points = points2
    return points

I probably could have just had the points generated before the function call but whatever
it also is probably more efficient to only store the points you remove but once again whatever

#

luckily for my use case any more than tier 4 is unviable to generate anyway so

haughty mountain
lilac cradle
#

nice

#

how's that work?

#

like are you doing this in py or something else, and how do you do the raymarching

haughty mountain
#

a vertex shader

lilac cradle
#

ah
i ought to learn shaders but idk if python really works with em so i might end up having to really learn something like c/cpp

haughty mountain
#

I mean, you can make it work for sure. The shader stuff is pretty language agnostic

#

well, in the sense that you write the shaders in glsl and can use them in any other language

#

so basically I start with a box

image.png
#

and subtract out crosses

image.png
#

actually, intersection might make more sense

#

for level 1 I end up subtracting

image.png
#

a nice thing about signed distance functions, is that tiling patterns are easy to make, so for level two I create something like

image.png
#

and tile it

image.png
#

rinse and repeat for the deeper levels

#

the whole computation of the sdf boils down to

    float shapes = sdBoxScaled(p, vec3(0.5), 1.); // Unit cube.
    float sc = 1.;
    float fac = 1./3.;
    for (int i = 0; i < 10; i++) {
      sc *= fac;
      shapes = opSubtraction(shapes, sdCross(mod(p + sc, sc/fac) - sc, sc));
    }
```where sdCross is a function I wrote for drawing one such cross
#

cheap computations for generating something so complex

#

the boolean operations are also weirdly simple

float opUnion(float d1, float d2) {
    return min(d1, d2);
}

float opSubtraction(float d1, float d2) {
    return max(-d2, d1);
}

float opIntersection(float d1, float d2) {
    return max(d1, d2);
}
naive ridge
#

hey guys what are the 5 most important algorithms or data structures?

haughty mountain
haughty mountain
naive ridge
#

i have a book about neural networks which i tried one time but i remember that it was pretty advanced

#

so i want to prepare myself

lethal trail
#

what's the fastest way to convert a string like '12.34' to an integer, truncating everything after the decimal point?

#

int(float('12.34'))?

austere sparrow
lethal trail
#

somewhere around 5-10 digits

austere sparrow
#

before the .?

lethal trail
#

including before and after

austere sparrow
# lethal trail `int(float('12.34'))`?

This does seem to be the fastest way to do it in pure Python, pretty hard to beat 200ns

In [11]: small = "1.234567809"

In [12]: big = "123456780.9"

In [13]: %timeit int(float(small))
173 ns ± 1.25 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

In [14]: %timeit int(float(big))
198 ns ± 2.29 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
lethal trail
#

ok thanks

#

wasn't sure if maybe something with f strings could be faster

austere sparrow
#

f-strings create new strings, they don't parse them 🙂

#

why do you need this though?

lethal trail
#

i have a list of numbers i'm reading from a file that I want to truncate

#

a csv

austere sparrow
#

Do note that this will not work if the numbers have 16 or more digits before the .

#

!e

n = 2.0**53
print(n)
print(n + 1)
print(n + 1 == n)
print(n + 2)
halcyon plankBOT
lethal trail
#

ah

#

well good thing my numbers aren't that big

serene hornet
earnest scaffold
#

Whats the largest number a program can calculate?

#

Does it dependd of the software or hardware we are using?

opal oriole
# earnest scaffold Whats the largest number a program can calculate?

If by calculate you mean "write out" the whole number in binary (store the whole thing physically, not just write a symbol representing it). Then using the Bekenstein bound for the observable universe (basically turning the whole thing into a black hole to store the largest integer possible (making use of all the space / all possible states)), somewhere around log_2(e) * 10^123 bits (or maybe 10^102, hard to tell, this is all speculation).

opal oriole
#

However much memory you physically have, and the software has to make use of it.

earnest scaffold
#

hmmm

haughty mountain
static sigil
#

anybody here knows about YOLO custom cfg?

#

Traceback (most recent call last):
File "train.py", line 616, in <module>
train(hyp, opt, device, tb_writer)
File "train.py", line 88, in train
model = Model(opt.cfg or ckpt['model'].yaml, ch=3, nc=nc, anchors=hyp.get('anchors')).to(device) # create
File "C:\Users\kuzey\yolov7\models\yolo.py", line 528, in init
self.model, self.save = parse_model(deepcopy(self.yaml), ch=[ch]) # model, savelist
File "C:\Users\kuzey\yolov7\models\yolo.py", line 738, in parse_model
anchors, nc, gd, gw = d['anchors'], d['nc'], d['depth_multiple'], d['width_multiple']
KeyError: 'depth_multiple'

keep getting this error no idea how to fix

#

Even thought I got depth multiple in the cfg

#

YOLOv7 custom configuration file

Number of classes

nc: 3 # Number of classes (Kalsifikasyon, Normal, Kitle)

Anchors

anchors:

  • [10,13, 16,30, 33,23] # P3/8
  • [30,61, 62,45, 59,119] # P4/16
  • [116,90, 156,198, 373,326] # P5/32

YOLOv7 backbone and head configuration

backbone:
name: darknet53 # Darknet53 or any other supported backbone
depth_multiple: 0.33 # Depth multiple for backbone
width_multiple: 0.50 # Width multiple for backbone

head:
num_classes: ${nc}
anchors: ${anchors}

Training parameters

train:
img_size: 640
batch_size: 16
epochs: 300
data: C:\Users\kuzey\OneDrive\Masaüstü\data.yaml
cfg: models/yolov7-custom.cfg
weights: yolov7.pt
device: ''
multi_scale: False
freeze: [0]

Testing parameters

test:
img_size: 640
batch_size: 16
data: C:\Users\kuzey\OneDrive\Masaüstü\data.yaml
cfg: models/yolov7-custom.cfg
weights: yolov7.pt

naive ridge
#

.

modern gulch
# earnest scaffold Whats the largest number a program can calculate?

Phrased the way you asked, there's no answer. First, what do you mean by 'calculate'? Second, a program could divide a big problem into smaller problems, and summarize without needing an entire "number" in memory. Third, 'can' has no constraints: when? How long? Some future computer?

valid comet
#

Does anyone know of any good libraries for sparse octrees? Preferably something running C or C++ under the hood

lethal trail
#

seems to work fine

haughty mountain
#

I was probably thinking of the integer division behavior

sharp dawn
#

Hi i was trying to solve this problem which the correct answer like this:
[A, B, C, DD, E, FFF, G, HHHH, I]

I tried to implement my logic, but the pattern is almost correct. My output looks like this: ['A', 'B', 'C', 'DDD', 'E', 'FFFFF', 'G', 'HHHHHHH', 'I']
I used various methods but still can't resolve the issue.

Anyone have any hints or suggestions to solve this problem? I've been stuck on it all day

Screenshot_20240704-201928_Chrome.jpg
vocal gorge
#

if i%2==0, print one letter, otherwise print (i+1)//2 letters

sharp dawn
#

number = []
for i in range(0,len(df)):
  if i==0:
    number.append(df["Letter"][i])
    i_t.append(1)
  elif i%2==0:

number.append(df["Letter"][i])

else:
    number.append(df["Letter"][i]//2)

You mean like this?

print(number)
print(i_t)

sharp dawn
granite dove
#

Probably a super basic question but why does this work:
self.contents = []
for i in range(val):
self.contents.append(str(key))
but this doesn't:
self.contents = []
(self.contents.append(str(key)) for i in range(val))

The second set of lines just returns an empty list

regal spoke
#

!e

squares = (i * i for i in range(5))
for square in squares:
  print(square)
halcyon plankBOT
granite dove
#

Makes sense. Thanks very much!

gritty tulip
#

hi guys i wrote a background processor using python it is running using asyncio.run and im using while True: to infinitely run my asyncio.run that process records from database and upload the result to database. but sometimes it suddenly hangs for no reason? what do you is the reason for this scenario?

fiery cosmos
#

Given two strings s and t, return true if the two strings are anagrams of each other, otherwise return false.

An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.

I guess this code doesn't work if there is some letter in countT that isn't in countS?

(This is NeetCode's solution)

image.png
stiff quartz
#

Youre not gonna reach anything after the first return Counter(s)==Counter(t)

#

But that’s correct

fiery cosmos
#

Yeah, I know that code wouldn't be executed, so just wanted to check whether my assumption is correct

fiery cosmos
#

Is there any website where are a lot of DSA patterns explained? By DSA pattern I mean something like two pointer pattern or fast and slow pointer or sliding window.

I am doing this course https://www.designgurus.io/course/grokking-the-coding-interview but I am interested if there is something like that

Design Gurus: One-Stop Portal For Tech Interviews.
Grokking the Coding Interview Patterns | #1 Course

Grokking the Coding Interview Patterns in Java, Python, JS, and C++. Most comprehensive course with 325 Lessons & 350+ Exercises.

haughty mountain
tight cedar
#

what

stiff quartz
#

Usually it’s correct

haughty mountain
stiff quartz
#

that should be enough of an indication it's correct

#

depends on the number of test cases i guess

tight cedar
#

if it is in s but not in t you would get countS[c] != 0

haughty mountain
stiff quartz
haughty mountain
#

I've seen both

stiff quartz
#

that's fair

haughty mountain
#

tests failing to test edge cases and whatnot

stiff quartz
#

to be fully honest if your solution works but you forgot to treat the case where the input list is empty I feel like you've learned what you should've learned

#

actually i'm not sure i agree with what i just said

#

😆

tight cedar
#

I couldn't understand why the time limit for all languages are the same leading to something that is "impossible" for python to pass

#

well at least in few cases a shitty c++ can pass but the same shitty python cannot

stiff quartz
#

on what platform?

#

on leetcode, time limits are different

haughty mountain
#

balancing multipliers is hard

lilac cradle
#

i wrote this silly little thing while super pissed off

image.png
regal spoke
#

Most of the time I see people .strip() or .rstrip(), they actually don't need it

stray fractal
#

i see multiple violations of D.R.Y and convenient code writing

narrow mica
# lilac cradle i wrote this silly little thing while super pissed off

match is not switch btw, don't use it as such
it's not faster than if-elif, and on the other hand you can do a lot more with it

parts = line.split()
match parts:
  case "v", *tail:
    vts.append(scale * vec3([float(i) for i in tail]))
  case "vt", *tail:
    ...
  case "vn", *tail:
    ...
  case "f", *tail:
    ...
  case _:
    # p[0] isn't any of those
lilac cradle
stray fractal
#

just providing code comments =w=

lilac cradle
#

fair

lilac cradle
regal spoke
#

That one effectively calls .strip() for you

fiery cosmos
#

Hey guys can someone who doesn't know variables be a good colleague

shut sierra
#

hey, so I wrote some code, which kind of seems to work, but then I continued to write a similar thing and started to wonder whether I'm doing a right thing or not

    for path, dirs, files in dotfiles.walk():
        for d in itertools.chain.from_iterable(
                fnmatch.filter(dirs, skippath)
                for skippath in [".git", ".mypy_cache", "blog", "scripts"]
            ):
            dirs.remove(d)

(dotfiles variable is Path from pathlib and I think every other function should be clear)
So, like, here we use itertools.chain.from_iterable which acts sort of like a flat_map, where I take the list of directories I want to skip while traversing the file tree (that's what Path.walk() does btw), and then over these "blacklisted" directories I create an iterator of paths I want to skip, which is then spliced by itertools.chain.from_iterable into one iterator.

Am I deleting the elements from dirs while I'm iterating dirs?
like, whatever way itertools.chain.from_iterable works, somewhere inside it hidden either yield or custom next() function, which means that it slowly builds my filtering list while I'm iterating over it my iterating over my dirs while I'm deleting them. Or simply put it seems that I mutate the list I'm iterating over.

#

which is sort of bad, I'd guess

#

but maybe it's actually ok in this case?

final night
#

Hey guys.
I was wondering, there is a mooc for dsa https://tira.mooc.fi/spring-2024/
And I was wondering if anyone could take a quick look, and tell me if it's worth following as a course? I'm hoping to learn dsa, but I'm not a fan of watching videos.
I tried coursera's princeton course, which everybody recommends. but I found it too difficult for me. it was discouraging.
Anyway, just wondering if this course is worth it, or if I should give coursera another try. Ideally I'm looking for a course with theory, and then accompagnying relevant exercises with solutions

fiery cosmos
final night
ashen niche
#

Assume I have 3D points(I drew in 2D for simplicity)
and a few unordered target points, is there a way to find out all the points to the left of the target points?(I drew a line for ease of understanding whats "left" of the target points)

image.png
#

with green ones being to the left of the target points

#

I thought looking at the nearest neighbor but it doesn't work 100%

lament totem
#

You could sort the target points from top to bottom, then draw a line between each of them (and continue the line above and below if necessary). Next for each other point you check between which two target points it is in y-coordinate, and check the corresponding line whether this point is to the left or right of it.

#

If you want a more smooth line, or a line that also continues after the target points, you may want to fit a curve through these target points instead.

#

@ashen niche

ashen niche
lament totem
#

I'm gonna walk my dog, so I can respond in like 20 mins, sorry

ashen niche
#

and they're 3d as I said so top to bottom in what axis?

#

aight 🙂

vocal gorge
ashen niche
vocal gorge
#

why isn't it, though?

ashen niche
#

well, if we imagine the line I drew I guess it makes sense

vocal gorge
#

in 2d there's some natural ways to connect the points, e.g. by ascending y coordinate - but in 3d I think there isn't a corresponding natural way to make a mesh out of them.

ashen niche
#

imagine you have two steel metals that you meld together in an awkward shape and you want to know which is which based on a few melting points, if that's an alright analogy

acoustic nest
#

hey guys, im looking for a good (free) DSA python course before I start AI/ML/DL. does anyone have any recommendations? im not really trying to prepare for interviews/jobs yet, im just looking to gain enough knowledge to start AI

ashen niche
lament totem
#

So are these points generally on a line?

#

Because it is hard to automatically determine what would be "left" or "right" @ashen niche

ashen niche
#

maybe they'd go from the top to the left, then to the right, then flip, etc
the end goal is the same but the process there is arbitrary so it makes it a bit more difficult, I guess

lament totem
#

So this is some idea I have:

image.png
#

Example is in 2d, but could do in 3d as well, just need to fit a 2d plane, and later on fit a hyper plane through the points.

#

But this makes an assumption that the separation is 2.5D (I.e. each x value has a single y value)

ashen niche
#

what do you mean?

#

by the 2.5D

lament totem
ashen niche
#

hmm

#

I'm guessing the 2nd part is possible, but maybe some error is acceptable if it is low enough

lament totem
#

Well it would try to fit a curve through the points somehow

#

Or a hyperplane* in your case

ashen niche
#

My first solution was fitting a 2D ellipse, but with an angle(so it's sorta 2D in 3D space) and then just projecting that onto the points lol

#

but sadly that was too generalizing

lament totem
#

But some assumptions are made for this method.

#

I wouldn't know how to find out what would be "left" or "right" in some other simple way.

ashen niche
#

I'll try this out, cool concept.

#

I'm wondering if I can just run a spline on the original points

opal oriole
#

After it's multiple convex hulls it's just point inside convex hull test.

haughty mountain
#

there are neat approaches where you use radial basis functions and neural nets to fit boundaries like these

#

I did some of it ages ago in uni, dots are the origin of the placed radial basis functions, the black line is the fitted boundary using these bases

unknown-9.png
zinc sky
#

how can I optimize this code further for this Maximum Number of Vowels Problem

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = set('aeiou')
        ss = list(s[:k])
        count = sum([1 for x in ss if x in vowels])
        for i in range(0,len(s)-k):
            ss.pop(0)
            ss.append(s[i+k])
            count = max(count, sum([1 for x in ss if x in vowels]))
        return count

failing under time limit exceeded for long strings of more than 50k chars on leetcode

boreal relic
#

Popping and appending are going to kill your timings.

#

It looks like a different approach would be better: how can you get every substring of size k from ss? The count vowels in those and return the max.

shut breach
stiff quartz
#

Why do they say

(8, 4), (4, 2), (8, 2), (8, 1), (4, 1), (2, 1)

and not

(8, 4), (8, 2), (8, 1), (2, 1), (4, 1), (4, 2)

?

image.png
shut breach
shut breach
stiff quartz
#

well if we do the inversions

#

8, 4, 2, 1 becomes 4, 8, 2, 1

#

and then we want to swap 8 and 2

#

4, 2, 8, 1
and then we want to swap 8 and 1
4, 2, 1, 8

#

at least that's how i understood the inversion count problem

zinc sky
shut breach
shut breach
stiff quartz
tight cedar
#

it is counting how many 2 pair inversions exists ig

stiff quartz
#

Isn't the number of inversions basically how long a bubble sort would take to sort the array?

#

oh i see inversion is just the number of i, j such that a[i] > a[j]?

shut breach
#

yeah

stiff quartz
#

ah that's my bad

#

i really thought it was linked to bubble sort

#

and like swapping them

#

It's actually the same number though right?

shut breach
#

same number as what?

zinc sky
stiff quartz
#

as the number of steps a bubble sort would take if we only count the steps where it swaps two elements of an array

zinc sky
#

Even append has same o(n) complexity?

shut breach
#

no, append is O(1)

shut breach
final night
#

I'm having trouble with an algorithm
let's say I have 3 rectangles, the sides of each rectangle are parallel to the x and y axis.
These rectangles can overlap, the goal is to find the area of all rectangles minus the intersection.

I have a few test cases and the area it's supposed to result in

Here's what I tried
I tried calculating the area of each of the 3 rectangles
Then I calculated the intersection between rectangles 1 and 3, 1 and 2 and 2 and 3, and substracted that.
I can't get that result.

If I could get a hint on what I'm supposed to do that would be great

#

Oh, there is the simple solution where I can map every point of each rectangle, but the question specifically states that it won't be accepted because it's too inefficent

lilac cradle
#

because you'd want to make sure you aren't subtracting twice if all 3 rectangles overlap, so really the overall bit you subtract should be the union of the two intersections

final night
#

can I show you my function?

lilac cradle
#

sure

#

im honestly not entirely sure how you'd do it but i dont think checking all the points is the play

#

i think its possible to do it just from knowing the start and end points, and then sort of constructing a shape from that

final night
#

it's a mess sorry about that

def area(rec1, rec2, rec3):
    area1 = abs(rec1[2]-rec1[0])*abs(rec1[3]-rec1[1])
    area2 = abs(rec2[2]-rec2[0])*abs(rec2[3]-rec2[1])
    area3 = abs(rec3[2]-rec3[0])*abs(rec3[3]-rec3[1])
    
    #find intersection
    left12,right12 = max(rec1[0],rec2[0]), min(rec1[2],rec2[2])
    left13,right13 = max(rec1[0],rec3[0]), min(rec1[2],rec3[2])
    left23,right23 = max(rec2[0],rec3[0]), min(rec2[2],rec3[2])
    bottom12,top12 = max(rec1[3],rec2[1]), min(rec1[3],rec2[1])
    bottom13,top13 = max(rec1[3],rec3[1]), min(rec1[3],rec3[1])
    bottom23,top23 = max(rec2[3],rec3[1]), min(rec2[3],rec3[1])

    area = area1 + area2 + area3
    if left12<right12 and bottom12<top12:
        area -= (right12-left12)*(top12-bottom12)
    if left13<right13 and bottom13<top13:
        area -= (right13-left13)*(top13-bottom13)
    if left23<right23 and bottom23<top23:
        area -= (right23-left23)*(top23-bottom23)
    return area
`
lilac cradle
#

honestly i'd recommend using some sort of vector to do this sort of thing
having all the operations be done one by one manually tends to be tedious

#

having an actual rectangle/box class would also make it a lot easier to work with

lilac cradle
#

so basically you trim any redundant area
this pr obably wont work for some edge cases though

#

also this is ignoring angling the boxes because that's a whole can of worms you don't want to deal with

haughty mountain
lilac cradle
#

hm yeah that seems simpler

haughty mountain
#

principle of inclusion-exclusion

lilac cradle
final night
#

now the question is how to find the value of (1&2&3)

lilac cradle
#

1&2&3 is a composition so you can just do (1&2)&3

lilac cradle
#

functionally the intersection of two boxes is essentially like using each one's corner (the ones facing into the intersection as a corner for the new box

lilac cradle
final night
#

works

#

there was a typo

#

but it works now

#

the suggested solution is basically the same in principle, but refactored

#

so thanks

opaque gorge
#

hi

# 


arr = [0] * (max(nums)+1)
for i in (nums):
    
    arr[i] = 1
z = set()
count = 0
for i in range (0,len(arr)):
    if arr[i-1] == 1:
        count += 1
    else:
        z.add(count)
        count = 0
print(z)
u = max(z)

print(u)```


this code runs for me in online compiler

but the following gives me error

```class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        arr = [0] * (max(nums)+1)
        for i in (nums):
            
            arr[i] = 1
        z = set()
        count = 0
        for i in range (0,len(arr)):
            if arr[i-1] == 1:
                count += 1
            else:
                z.add(count)
                count = 0
        print(z)
        u = max(z)

        return u

it says z is empty on leetcode (q.128)

#

leetcode error message

        ^^^^^^
    u = max(z)
Line 16 in longestConsecutive (Solution.py)
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    ret = Solution().longestConsecutive(param_1)
Line 38 in _driver (Solution.py)
    _driver()
Line 49 in <module> (Solution.py)
agile sundial
#

leetcode tries multiple inputs. did consider what happens when z is empty

#

though, max doesn't take a sequence..

opaque gorge
#

naw the same test case is failing

#

the one with nums = [100,4,200,1,3,2]

#

in leet code when I print the values of z it shows up, but when i put it in max function it says its empty.

agile sundial
#

what's the output

opaque gorge
#

out put for z is {0,1,4}

shut breach
#

please dont use ableist language

ashen niche
#

so the green/red I colored in are isolated based on the points I drew

acoustic nest
#

anyone have a good free dsa course for python? im not really looking to prep for interviews or anything im moreso just learning for the sake of learning. id also like to get into ai or data science later and i know most of your basic python stuff for reference

ripe flame
#

okay this is funny and kind of irrelevant, although how does that pop up with my "Username" being the class 😂

chrome mountain
#

Hello, I am making a custom data structure based on lists and dictionaries and am having some trouble understanding how the heirarchy is implemented between list and dictionaries in python. can somebody explain it?

narrow mica
chrome mountain
#

Elaboration:
I am trying to implement a tree, in which each Node is similar to a python dictionary

head
|-> child
    {
        key:  value
    }
|->child2
    |-> child3

something like this
The problem I'm facing is, that one of the data types that can be used as a value is an array, similar to a Python list(will call this data structure list).
The twist is, that a list can also be a node in the tree, as well as a value in a node. (I am trying to make a wrapper for another software, hence trying to abstract the data types of that software into Python for the wrapper)

list1
(
    child1
    {
        key: value
    }
)

something like that. In order to implement this, I remembered that Python also has a similar use case: A list can be stored inside a dictionary and vice versa. I want to know how it is achieved internally, as there should be a proper hierarchy between the data types and this use case mixes the hierarchy.

narrow mica
chrome mountain
#

I'm not wrapping everything around nodes because the nodes has some attributes other than the children which are stored as key value pairs, while list does not. And the software also supports multiple values for a single key, so that's another reason for not wrapping everything withing Node

narrow mica
chrome mountain
chrome mountain
narrow mica
chrome mountain
#

basically I made a custom data structure that stores multiple values for a single key

narrow mica
narrow mica
narrow mica
chrome mountain
#

this is fine. but how will I use the same list class when I need to store the list as a value inside the Node

Node
{
  list1: 
  (
    value1
    value2
  )
}

In this case, Node is the NodeInterface object and the list1 is a List object, except the list is not a child but a value to an attribute

narrow mica
narrow mica
chrome mountain
chrome mountain
narrow mica
#

I'm probably missing something but I can't really tell

chrome mountain
#

let me show an example of a file that I'm trying to make an abstraction of

narrow mica
narrow mica
chrome mountain
# 
/*--------------------------------*- C++ -*----------------------------------*\
  =========                 |
  \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
   \\    /   O peration     | Website:  https://openfoam.org
    \\  /    A nd           | Version:  7
     \\/     M anipulation  |
\*---------------------------------------------------------------------------*/
FoamFile
{
    version     2.0;
    format      ascii;
    class       dictionary;
    object      blockMeshDict;
}
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //

convertToMeters 1;

vertices
(
    (0 0 0)
    (0.012 0 0)
    (0.012 0.03 0)
    (0 0.03 0)
    (0 0 0.001)
    (0.012 0 0.001)
    (0.012 0.03 0.001)
    (0 0.03 0.001)
);

blocks
(
    hex (0 1 2 3 4 5 6 7) (100 150 1) simpleGrading (1 1 1) 
    hex (8 9 10 11 12 13 14) (100 150 1) simpleGrading (1 1 1) 
);

edges
(
);

boundary 
(
    walls 
    {
        type wall;
        faces
        (
            (0 1 5 4)
            (1 2 6 5)
            (2 3 7 6)
            (3 0 4 7)
            (0 3 2 1)
        );
    }
    

    atmosphere
    {
        type patch;
        faces    ((2 3 7 6));
    }

);

mergePatchPairs
(
);

// ************************************************************************* //

This is an example file. In the file structure, the file is refresented as a Node. All the containers(List and dictionaries) inside the file are also Nodes
you can see that the list blocks holds only physical values, so it can be represented a simple python list with some formatting while generating an output from the wrapper. The problem arises with the boudary list. It contains dictionaries(data in {} ), which are supposed to be Nodes, but are contained inside the list, which is supposed to be a container only for physical values. The current implementation I made manages this using flags. But is there a better solution other than separating the two types of lists?

narrow mica
# narrow mica or instead of inheritance, just use composition 
class TreeNode:
    stuff: List | Node
    children: list[NodeInterface]

class List:
    values: ...

class Node:  # this is your original definition of the node, with kv pairs and extra attributes and stuff
    values: MyClassThatStoresMultipleValues
    apple: ...
    orange: ...
    lemon: ...
narrow mica
chrome mountain
#

yep. and yes the main software is in c++

#

By PhysicalValues I mean int, float, string, vector etc.

chrome mountain
narrow mica
#

oh wait, do you mean that PhysicalValues as in all int, or all float, etc.

chrome mountain
narrow mica
chrome mountain
#

will do, thanks!

narrow mica
#

the way python does it is through storing pointers, in c++ that'd look something like

class Interface {};
class Type1: public Interface {
  public:
    void type1Method() {}
};
class Type2: public Interface {};

std::vector<Interface *> vec;  //
vec.push_back(new Type1);  // ok
vec.push_back(new Type2);  // ok

Type1 *p = dynamic_cast<Type1*>(vec[0]);
if (p)  // it'd be null if the cast fails
    p->type1Method(); // ok
#

I'm not sure how easy that'd be for you cause you also have stuff like int in your list

#

or actually, maybe what you need is just template?
(this is how you can have "different" vectors like std::vector<int>, std::vector<float> without having to make multiple definitions of std::vector)

narrow mica
chrome mountain
narrow mica
chrome mountain
chrome mountain
narrow mica
chrome mountain
narrow mica
chrome mountain
narrow mica
# chrome mountain Yes. While keeping a single class for list

so... do some recursive parsing ig? idk what to tell you cause this is very dependent on what you have
e.g.

def parse(o):
    if isinstance(o, MyList):
        for thing in MyList:
            parse(thing)
    elif isinstance(o, Node):
        for key, value in o:
            parse(value)
    else:  # this leaves PhysicalValues
        render(value)
chrome mountain
#

yes I'm doing a recursive parsing and I am trying to avoid these if-else conditions for types as much as possible.

hardy ferry
#

guys is there any data structures and algorithms certification exam available?

opaque gorge
#

how to get started with dsa if i dont know any thing.

#

should i just start tackling nc150 and look up toutorials when i get stuck on the topic

drifting hare
#

the first 1/3 of the course is data structures, second third is graph algos, third is dynamic programming

gritty tulip
#

hey guys, can you recommend some good and comprehensive tutorials about asyncio and multithreading in python thank you very much

vocal gorge
safe burrow
#

how do for loops work

haughty mountain
#

topic pls

chrome mountain
safe burrow
chrome mountain
#

in python the way those three conditions are declared is different but yea, that is the basic gist of for loop

haughty mountain
chrome mountain
haughty mountain
#

python doesn't do this kind of loop

#

unless you phrase it as a while

chrome mountain
haughty mountain
#

there is only the for each

haughty mountain
#

the C style for is just a while in a thin disguise

chrome mountain
#

how abt this?

for i in range(10):
  #do stuff
#

I see the same implementation tbh

#

just written differently

haughty mountain
#

e.g. these won't do the same thing

#

for each loops behave differently, less like a plain while loop

chrome mountain
haughty mountain
#

the top loop iterates 5 times, the bottom 10

chrome mountain
#

why son't the bottom one iterate 5 times?

haughty mountain
#

because i is reassigned with the next value of the iterable on each iteration

#

that's how for each loops work

#

!e

for i in range(10):
  i += 100
  print(i)
halcyon plankBOT
chrome mountain
haughty mountain
#

what would be another way of writing a for loop in python? pithink

woeful lion
#

Is there a fast way to evaluate the intersection of a bezier curve and a vertical line?

#

Like if I want to find Y of a point on a bezier curve at X, is there a way to do that that doesn't involve root-finding algorithms?

haughty mountain
chrome mountain
haughty mountain
#

if you don't want to do the proper math

haughty mountain
#

it's the only thing for can mean in python

chrome mountain
#

true, without in, for is practically useless. But in is also used in other places, like in conditions. I guess in that use cae also, in works the same way.

#

if in future some other way of defining a for loop is made in python other than just the for .. in then maybe the iteration will be like the regular for

agile sundial
#

no.

agile sundial
#

you need both to make a for loop, it's not in giving it power or something

haughty mountain
#

in in for ... in and the containment check in are completely different

#

then only really share the same name because they are vaguely semantically similar

crude pier
#

I am looking for suggestions for a data structure. My case is:

  • I have several ranges a particular variable can take for instance range1 = np.arange(-3, 3) and range2 = np.arange(0,6)
  • I have a particular function for mapping a value in range1 to range2 and vice versa
  • I want to be wrap the ranges in a class or enum so that my code is more readable
#

I tried using enums but this did not work with numpy ranges since they are not easily comparible and I dont want the ranges to be mutable

opaque gorge
drifting hare
#

that way you get some practice to familiarize yourself before moving on to the next topic

stiff quartz
#

Is this not nlogn? (Edit nvm, it is nlogn, it's just the problem expected O(n) solution and the nlogn solutions time out except if i code it in cpp and optimize a bit)

    def compute_global_inversions_merge_sort(self, arr: list[int]) -> tuple[int, list[int]]:
        if len(arr) < 2:
            return 0, arr
        
        mid: int = len(arr) // 2
        left_inv, left_arr = self.compute_global_inversions_merge_sort(arr[:mid])
        right_inv, right_arr = self.compute_global_inversions_merge_sort(arr[mid:])
        
        tot_inv = left_inv + right_inv
        merged: list[int] = []
        i = j = 0
        while i < len(left_arr) and j < len(right_arr):
            if left_arr[i] < right_arr[j]:
                merged.append(left_arr[i])
                i += 1
            else:
                merged.append(right_arr[j])
                tot_inv += j + mid - i
                j += 1
        
        merged.extend(left_arr[i:])
        merged.extend(right_arr[j:])
        
        return tot_inv, merged
#

But I feel like that's the standard way to count inversions with merge sort

half owl
# 
def f1(L):
  n = len(L)
  while n > 0:
    n = n // 2
    for i in range(n):
      if i in L:
        L.append(i)

return L

whats the time complexity? O(n log n)?

stiff quartz
#

I think so yes?

#

well no i in L is O(n)

#

but I don't have any lookup

#

@half owl

half owl
stiff quartz
#

ah no it is O(nlogn) overall

#

you lookup in O(n) then twice in O(n/2) then four times in O(n/4)

#

right?

#

ah yes no you don't resize L

#

but my list is resized

half owl
#

then again i did see someone think it's o(n) but im pretty sure thats wrong

stiff quartz
#

what

#

i don't get it

#

were you answering my message or did i get confused and you asked a question that just happened to be similar?

half owl
half owl
half owl
#

if LFS is the amount of operations done, why is the time complexity (big O) equal to the RHS? why is the -1 even there? it should not exist since we only have + summation and 2^i as elements summed

image.png
vocal gorge
half owl
vocal gorge
#

2^n-1 is O(2^n), yeah

half owl
vocal gorge
#

Huge numbers? Like what?

half owl
half owl
half owl
#

and here's the answer

image.png
stiff quartz
#

I think that's wrong

#

i in L is O(n)

#

they miss it

haughty mountain
#

assuming L is a list

# 
n*n + n/2*n + n/4*n * ... =
n*(n + n/2 + n/4 + ...) ~ O(n^2)
#

err...actually worse than that

#

because L gets larger

vocal gorge
#

I think O(n^2) in both best and worst case, since len(L) at the end is between 1x and 2x of the original value.

haughty mountain
#

or wait no, you're right

#

the //2 is before the inner loop

outer rain
#

there is also that in is short circuiting, but ig it's still Θ(n^2)

half owl
#

for k >= 1, can someone help me prove for >=?

i can only manage <=

Screenshot_20240710_020028_Gallery.jpg
regal spoke
#

Two nested loops resulting in O(n^2) time

half owl
half owl
regal spoke
#

The outer loop has to run n times

#

And then in each iteration it has to do the costly i not in L operation

half owl
regal spoke
half owl
#

but then it's doing log n times (first loop) * (n/2^i)*n (2nd loop + lookup)

half owl
regal spoke
#

Btw what is the L in your code?

#

If L starts out empty, then nothing will ever get added to it

half owl
half owl
regal spoke
#

In that case, the time complexity is definitely O(n^2)

half owl
regal spoke
#

First iteration takes n^2 time

#

2nd iteration takes n^2/2 time

#

3rd iteration takes n^2/4 time

half owl
regal spoke
#

The way I think of it is that i on L is always O(n)

#

The cost of that doesn't change between iterations

half owl
regal spoke
#

But the for loops decreases in size in each iteration

#

That's what causes the division by powers of two

half owl
regal spoke
half owl
#

I mean I want to regirously calculate the time complexity to show it

half owl
regal spoke
#

Oh you use () to explain what you mean by log n etc

half owl
#

yeah

regal spoke
#

Just a thing. 1 + 1/2 + 1/4 + 1/8 + ... = 2

#

So when you sum up the cost n^2 + n^2/2 + n^2/4 + ... <= 2 * n^2

half owl
half owl
#

oh right we had 1*n^2 already

regal spoke
#

Ye

#

The first iteration

half owl
#

I'm trying to think up a formula to this using i and n

regal spoke
#

If you want to do a rigorous derivation, then you will have to take into account that L's size is slowly increasing. Meaning the cost of running i in L slowly increases

#

You can prove that L will have a size between n and 3n

half owl
devout jay
#

Hello I am a starter, and have learned Python a bit, can anyone help me guide a bit please? seriously passionate guy here seeking guidance! Thanks in advance

serene tartan
#

Can anyone provide me a good source to learn about run time complexity of an algorithm in python from scratch

vocal gorge
rose pollen
#

Can anyone tell me why we need to learn DSA as a programmer?

haughty mountain
rose pollen
#

to program better

half owl
#

which can save both money and time and lives in some cases

rose pollen
#

ok

#

thanks

haughty mountain
rose pollen
lilac cradle
#

is there a good simple way to shuffle an image while knowing the original position of each point? i did this yesterday but i think the method was somewhat inefficient
i basically had a set() of used points, and randomly generated a position until i found one that wasn't in the set

vocal gorge
lilac cradle
#

ig
is it possible to do it without np? ik its faster but in this usecase the speed isnt actually a big concern

#

also is it faster to do a concat or "".join() for combining two strings

vocal gorge
vocal gorge
lilac cradle
#

or a handful really

lilac cradle
#

hm i wonder if pillow lets you get a single index for a pixel
cause i know it lets you push data in that format to it, since i use that all the time but i dont think ive ever gotten single index pixels

#

i can prob jsut use tuple coordinates and shuffle that anyway though

vocal gorge
#

with a numpy array it'd be straightforward, without one, uhh, can get the image as a bytes instead

#

yeah, that'd work too

lilac cradle
#

btw is there a way to only give an argument to a function if a condition is met? other than just if statement and calling it differently in each block

vocal gorge
#

unpacking a variable-size collection comes to mind

#

e.g. args = (x,) if cond else () and then f(*args)

lilac cradle
#

hm

haughty mountain
#

sorry, this is better

f(*(x,)*cond)
gloomy yew
#

What is the best way to implement a trie?

vocal gorge
#

a nested dict would work fine

#

for a real application, I'd use a compiled third-party library like marisa-trie

gloomy yew
#

Yeah i was talking about real world application

fiery cosmos
#

Hi,
I was trying to solve a greedy problem. The problem is something else but the main crux of the algorithm is what i have stated below.

Given two integer arrays, nums1 and nums2, each of length n, for each index i in nums1, we select an index j in nums2 and calculate the absolute difference between the values at these indices. How can we determine the minimum possible sum of all these absolute differences?
So apparently by sorting both arrays and then pairing the elements at the same indices, we are minimizing the differences at each position.
Can someone help me figure out a formal prove for it (preferably not by contradiction) and maybe some tips on how to convince or prove myself of greedy solutions in the future?

lean junco
#

Anyone understands why max manhattan distance problem works in O(N) ??

vocal gorge
haughty mountain
lean junco
haughty mountain
#

...

#

that doesn't mean much to me

vocal gorge
opaque grotto
haughty mountain
#

i.e. a permutation

haughty mountain
lean walrus
#

WLOG = without loss of generality?

haughty mountain
#

yeah

#

if it's not true I could just swap the sequences

#

what this shows is that taking a pair that is not in the sorted order and making it sorted, we get a smaller or equal sum of absolute values

#

keep doing this and you end up with a sorted sequence

#

there is probably a neater way of showing the substitution property, but this works

haughty mountain
#

maybe it's more natural to start with
a, a+da
x, x - dx
and showing that swapping makes it ≤, but whatever

spare warren
#

i see

haughty mountain
lilac cradle
#

is there a better way of comparing a vector / numerical list (i.e checking if one is greater than the other) other than just checking if all entries of one are greater than / less than / etc than the other? (which is what i've been doing)
of course im not sure what 'greater than'/'less than' would necessarily mean for vectors

haughty mountain
#

maybe figuring out what it should mean is the first step 🙃

#

if you just need some ordering of vectors you can just lexicograpically sort it or whatever

lilac cradle
#

asking cause i just had to fix a problem with the class where != wouldn't work; it was because i was using all() for the comparison (i.e all(a.x!=b.x,a.y!=b.y,a.z!=b.z)) but that doesnt work if any component is equal

#

i fixed it by adding an option to switch what comparison it uses and set it to any() for __ne__

lilac cradle
haughty mountain
#

err, how did you define == and != to make that happen?

lilac cradle
#

i use an internal function for all comparisons, it just take in an operator and compares it for each pair of components

lilac cradle
haughty mountain
#

let me write a generic thing because I'm lazy

== -> all(x == y for x, y in zip(a, b))
!= -> not all(x == y for x, y in zip(a, b))
#

these work fine, and != is just not ==

lilac cradle
#

thats fair, and fairly similar to what i am doing anyway

haughty mountain
#

you don't even need to implement both, do you?

#

I think if you implement == then != will use it

lilac cradle
#

lemme see

#

ah so it does

lilac cradle
#

.. wait why do i have that

haughty mountain
#

the default definition should be basically

return not (a == b)
lilac cradle
#

probably just a holdover tbh

#

is there a better way to check for iterability than try-except? afaik handling the error is kinda computationally heavy, no? or maybe thats just in other langs

#

maybe using iterable from collections.abc?

lean walrus
# 
== -> all(x == y for x, y in zip(a, b))
!= -> any(x != y for x, y in zip(a, b))
haughty mountain
lilac cradle
#

also i assume that syntax is just for this and not for actual implementation?

#

yeah it doesnt likei t when i try that lol

haughty mountain
#

the -> and stuff isn't meant for the actual impl no

solemn moss
#

Is bit shift for long integers in python n or n/int_size ?

#

If first, where can i find some bitset implementation? (in python)

regal spoke
#

So like n/64

#

However, changing a single bit of an integer is also n/64

#

So using Python big integers as bitsets is kind of flawed

solemn moss
#

Well usually i would just switch to cpp ofc
But sometimes there are cases when I don't want to do that (happened recently)
so wanna prepare for such case

regal spoke
#

The nice thing about using python integers as bitsets is that they are dynamic, which is not the case for most bitsets out there

regal spoke
#

I've found that for most bitset problems out there, python integers are sufficient

solemn moss
#

There was some expression parsing
For example A-(B-(C-(Z+A+B+Z-20+11)))+8-11
(that's why i didn't want to use cpp) and after that i had an equation like
C[0] * a + C[1] * b + C[2] * c + ....
where all variables (a, b, c...) can take value in range [1; 10]

Maybe there is another solution but I did just

possible = {0}
for x in C:
    if x:
        new_possible = set()
        for i in range(1, 11):
            for v in possible:
                new_possible.add(x * i + v)
        possible = new_possible
print(len(possible))

and it passed because of small constraints

#

(need to find how many different results can it give)

regal spoke
#

That way the range over i can be kept to either 1 or 2

#

After that the code is

possible = 1
for x,count in C:
    for i in range(count): # note: count here is either 1 or 2
        possible |= possible << x
print(possible.bit_count())
solemn moss
#

I am not sure I understood

regal spoke
#

Ops just noticed you have range(1,11) and not range(10)

#

You can still use the same trick, but it needs to modified slightly