algos-and-data-structs

[raw zealot]

i see

[haughty mountain]

@regal spoke would be the resident pypy expert here

[raw zealot]

lmao this got https://cses.fi/problemset/result/11650548/ (0.37s)

n, x = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort(reverse=True)
inf = 10**9
dp = [inf] * (x + 1)
dp[0] = 0
for coin in arr:
    for i in range(coin, x + 1):
        dp[i] = min(dp[i], dp[i - coin] + 1)
print(dp[x] if dp[x] < inf else -1)

remove the sort and it becomes 0.72s 🥴

[raw zealot]

frfr

[regal spoke]

I think it is the min doing something funny

[raw zealot]

this code is O(1e8) and runs this quick in python which is very interesting

[regal spoke]

Using large coins first means you'll likely find the optimum quickly for dp[i], for all i

So min(dp[i], dp[i - coin] + 1) will often become dp[i]. Probably pypy is smart enough to optimize this

[raw zealot]

makes sense

[brave dagger]

Hello people I have a question regarding B+ trees

If I have a tree like this and I want to insert 5 here how do I go about doing that?

I did this but not sure if this is right or wrong. So basically my main question is since we already have a key 5 and our node to be inserted is 5 does it go after the key or before the key

[verbal agate]

Hey i m new here 🙇

[narrow mica]

there's no link to this, but
given an array of length n <= 1e5 and two numbers L, R, how do I count the number of subarrays whose average is between L and R?

[haughty mountain]

just as a first instinct I would try to reduce things to just counting subarrays whose average is >= 0

you could use that to compute the full answer, and it's probably easier to solve

[narrow mica]

I'm not sure how I can do that
rn I need L <= avg(arr[l..r]) <= R
if I subtract L from every element I can get 0 <= avg(arr_subL[l..r]) <= R - L but I don't think that changes much

[haughty mountain]

you should be able to express it as something like

count_pos_avg(arr - L) - count_pos_avg(arr - R)

[narrow mica]

hmm
that may have merit

[haughty mountain]

wait, doesn't that reduce to counting subarrays with sum ≥ 0?

[narrow mica]

count_pos_avg would reduce to count_pos cause dividing by length never changes sign

yea I think so

[haughty mountain]

hmm, instinctively that seems wrong

[haughty mountain]

is this reduction somehow incorrect?

counting sums in range l, r shouldn't be equivalent to counting averages in l, r

[narrow mica]

at least for now I can't think of anything

[haughty mountain]

stickie save us

[naive oak]

this feels wrong

you're counting an intersection

you should need inclusion exclusion

[narrow mica]

count_pos_avg(arr - L) should cover the avg where avg \in [L, \inf)
and count_pos_avg(arr - R) should cover avg \in [R, \inf)
so subtract to get [L, R)? getting to [L, R] shouldn't be too hard

(oh, and L, R and array elements are all integers)

[haughty mountain]

are you saying this does not work in the sum case either?

[naive oak]

ah i see

hmm

[haughty mountain]

there is something fishy

[narrow mica]

imma try coding it in to see empirically

[naive oak]

!e seems to work actually

import random
from itertools import combinations

arr = random.choices(range(-100, 100), k=1000)
pref = arr[:]
for i in range(len(arr) - 1):
    pref[i+1] += pref[i]
l = 40
r = 50

def count_pos_avg(n):
    return sum(
        i <= j for i, j in combinations([
            v - n*i for i, v in enumerate(pref, start=1)
        ], 2)
    )

print(count_pos_avg(l) - count_pos_avg(r))
print(sum(
    l <= (pref[j] - pref[i]) / (j - i) < r
    for i, j in combinations(range(len(pref)), 2)
))

[halcyon plank]

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

001 | 305
002 | 305

[naive oak]

count_pos_avg is O(n^2) rn but you can do it in n log n by sorting or whatever magic fenwick trees let you do

[haughty mountain]

so is this wrong? @naive oak

[naive oak]

no it's correct

[haughty mountain]

but doesn't that imply that the answer is the same for sum in [l, r] and avg in [l, r]?

[naive oak]

yeah that's what i'm still confused about

[narrow mica]

why would it imply that

[haughty mountain]

because count_pos(l) - count_pos(r) should be the elements with sum in that range

[narrow mica]

but the first count_pos is done on arr_subL and the second on arr_subR?

[haughty mountain]

right

[naive oak]

actually i think it doesn't reduce to this

counting the number of averages >= L reduces to counting the number of positive sums in arr - L
counting the number of sums >= L doesn't reduce to counting the number of positive sums in arr - L

[haughty mountain]

right

[naive oak]

because sum((arr - L)[i:j]) is sum(arr[i:j]) - L*(j-i), not sum(arr[i:j]) - L

[haughty mountain]

the sum case is the incorrect one

[naive oak]

that's why averages are nicer in this case, because the j-i gets cancelled

yeah

[haughty mountain]

neat

so the reduction is probably correct

[naive oak]

yeah

with averages you have sum(arr[i:j])/(j-i) - L = sum((arr - L)[i:j])/(j-i) so it works

neat

[rotund steppe]

n=int(input())
for t in range(n):
n,x=map(int, input().split())
a= list(map(int, input().split()))
a.sort()
ps=0
l=[]
for i in range(n):
ps+=a[i]
l.append(ps)

if n*a[n-1]-sum(a)<x:
    print((x+sum(a))//n)
else:
    lo=0
    hi=n-1       
    while lo<hi-1:
        mid=(lo+hi)//2
        if (a[mid]*(mid+1))-l[mid]>x:
            hi=mid
        else:
            lo=mid
    print(a[lo])

someone please tell what to modify in last line for correct output??

[narrow mica]

someone please tell what to modify in last line for correct output??
before anything, at least post what the problem is about?

[rotund steppe]

https://codeforces.com/problemset/problem/1873/E

[rotund steppe]

really sorry

[narrow mica]

dont have to be, its just that without the problem statement basically no one will be able to understand what you're doing

[narrow mica]

why is that the condition for your binary search btw? like did you prove it's fine to do that?
I'd expect something like comparing x with the sum of water you use if height was mid; and also in that case hi shouldn't be n-1

[rotund steppe]

import math
z=int(input())
l=[]
for t in range(z):
n,k,a,b=map(int, input().split())
for i in range(n):
c=list(map(int, input().split()))
l.append(c)

mini=math.inf
for i in range(k):#first part(finding major city nearest to a)
    if a-1<=k:
        dis=0
        break
    else:
        dis=abs(l[a-1][0]-l[i][0])+abs(l[a-1][1]-l[i][1])
        mini=min(dis,mini)
mini2=math.inf
for i in range(k):#last part(finding major city nearest to b)
    if b-1<=k:
        dis=0
        break
    else:
        dis=abs(l[b-1][0]-l[i][0])+abs(l[b-1][1]-l[i][1])
        mini2=min(dis,mini2)
print(mini2+mini)

https://codeforces.com/problemset/problem/1869/B

[rotund steppe]

whats wrong in this code?

getting inf as output

[neat trellis]

website?

codeforces ah

alr

[umbral onyx]

A book that will get me comfortable with most algos and data structures is?

[tight cedar]

I like the one ebook in pins

their sample python code is kinda weird tho

[umbral onyx]

Maybe something that has a cover, I don't really read ebooks

[raw zealot]

https://cses.fi/problemset/task/1639/

def solve(case=None):
    s1 = input()
    s2 = input()
    n, m = len(s1), len(s2)
    INF = 10**9

    dp = [[INF] * (m + 1) for _ in range(n + 1)]

    dp[0][0] = 0

    for i in range(n + 1):
        for j in range(m + 1):
            if i > 0:
                dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
            if j > 0:
                dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
            if i > 0 and j > 0:
                dp[i][j] = min(dp[i][j], dp[i-1][j-1] + (s1[i-1] != s2[j-1]))

    print(dp[n][m])

how to not tle

idt i can avoid 2d arrays this time

wait

3 min operations hm

[narrow mica]

the way you put the ifs in the double loop might be making the constant too big
try moving them to their own loops, and have the double loop do range(1, n+1) and range(1, m+1)

[raw zealot]

yeah thats what i am thinking

can have a separate loop for n =1 , m = 1

[narrow mica]

have a separate loop for when i == 0 and when j == 0

[raw zealot]

yes mb thats what i meant

yep ac

def solve(case=None):
    s1 = input()
    s2 = input()
    n, m = len(s1), len(s2)
    # INF = 10**9

    dp = [[0] * (m + 1) for _ in range(n + 1)]

    dp[0][0] = 0

    for i in range(1, n + 1):
        dp[i][0] = i

    for j in range(1, m + 1):
        dp[0][j] = j

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + (s1[i-1] != s2[j-1]))

    print(dp[n][m])
``` 0.86s ![ducky_concerned](https://cdn.discordapp.com/emojis/1178032077514477629.webp?size=128 "ducky_concerned")

[rotund steppe]

https://codeforces.com/problemset/problem/1832/B

i think second last testcase is wrong,anyone explain if its not

[rotund steppe]

whose output is 46..

[raw zealot]

remove 22 -> remove 15, you'll get 46

hint ||you can not just remove the smaller of (min1 + min2) and max, there is a reason it fails||

[rotund steppe]

🥰

[full heart]

apparantly the gcd of (16135213523153125, 23513512353122351235) is 12

why am i getting 5 as a result

[devout hare]

the gcd is 5

lol

import math
math.gcd(16135213523153125, 23513512353122351235)

[full heart]

-3-

those gcd calculator websites are scamming me

youre right

[full heart]

thank u

[devout hare]

side note: you can tell that the gcd is not 12, both numbers aren't even even?? lol

[full heart]

ye sorry

me kinda stupid

i was really worried cause i had 2 sites and they both told me its 12

[devout hare]

😭

[haughty mountain]

let me guess the tools are written in js

[devout hare]

I wonder if they're truncating to some number of digits or something

oh

¯_(ツ)_/¯

[full heart]

yea probably

some rounding or overflow idk

[haughty mountain]

js uses its Number type

which is a double

[full heart]

but this confused me a lot

[devout hare]

I thoguht js also has bigint 😭

[haughty mountain]

it does

but I doubt it's being used here

[devout hare]

rip

[haughty mountain]

yeah, this is floating point

[full heart]

that means mistakes very probable

[haughty mountain]

!e let's see

import math
x = 16135213523153125
y = 23513512353122351235
print(math.gcd(x, y))
print(math.gcd(int(float(x)), int(float(y))))

[halcyon plank]

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

001 | 5
002 | 12

[haughty mountain]

yup

(imagine trusting js with math)

idk if it's a good sign that I immediately knew what was messed up 🥴

[full heart]

yea my bad. i dont know that much bout programming yet ig

especially not with large numbers

but it seems to work finding a random relative prime to a number now :D

[haughty mountain]

it wasn't meant as making fun of you, it was complaining about javascript being bad

I imagine python also is sane enough to just refuse to do gcd with floats, because that's the sane thing to do

[devout hare]

I think it's more just a site implementation flaw too

[haughty mountain]

!e

import math
x = 16135213523153125
y = 23513512353122351235
print(math.gcd(float(x), float(y)))

[halcyon plank]

:x: Your 3.12 eval job has completed with return code 1.

001 | Traceback (most recent call last):
002 |   File "/home/main.py", line 4, in <module>
003 |     print(math.gcd(float(x), float(y)))
004 |           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
005 | TypeError: 'float' object cannot be interpreted as an integer

[full heart]

they couldve calculated it serversite 😔

but i couldve just used math.gcd tbh

[haughty mountain]

I mean, I blame js for just having the one Number type

(if you don't count BigInt, which iirc is also a recent thing)

[devout hare]

oh huh, it is fairly recent

didn't realize, I think it was introduced around the time I started programming with js so I always just knew it existed

or I suppose if you count five years as fairly recent

which is fair given how long it takes for things to propagate around the web

[haughty mountain]

seems like it was added in ES2020

[green monolith]

hey

[full heart]

what python function can i use to check this?

[devout hare]

phi(N) can be difficult to calculate if N is difficult to factor

e.g if you're doing RSA and N is p*q where p*q are two primes

but if you know the factorization, then you can just do phi(N) = (p-1)(q-1) and check that e * d mod phi(N) == 1

[full heart]

yea im actually doing rsa but my question was shit

so e and d are given. so i think the calculation is basically (e*d) mod phi and that should be 1

how can i calculate that (a * b) mod c

[devout hare]

(a * b) % c

[full heart]

ah thank you

i thought maybe theres something like pow(a, b, c) for a^b mod c

[full heart]

but with easy multiplication that is just fine

[full heart]

/directory/pythonfile.py

import subdirectory.module1 as th
th.method()

/directory/subdirectory/module1.py

import another_module
def method():
    another_module.do_smth()

why does this give me ModuleNotFoundError: No module named 'another_module'? when i run it from pythonfile.py. when i use module1.py everything works

i even have a __init__.py in the modules directory

[jolly mortar]

pow(e, -1, phi(N)) == d is equivalent i think

[full heart]

interesting that this works

since pow(a, b, m) is usually a^b mod m

[full heart]

and this obviously isnt 1/e mod phi(N)

[jolly mortar]

it is kinda

[full heart]

pow(23, -1, 120) = 47
(1/23)%120 = 0.043478260869565216

how is it the same then

[narrow mica]

it is if you use the modular arithmetic definition of division

cause you can't really just divide "normally" or you get a fraction, and you can't have those in modular arithmetic
so instead, we observe that this is true: x * 1/x = 1 to define that 1/x in mod m is the number x^-1 such that x * x^-1 = 1 in mod m

!e

print( (0.043478260869565216 * 23) % 120 )
print( (47 * 23) % 120 )

[halcyon plank]

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

001 | 1.0
002 | 1

[full heart]

i dont really know if i get that yet. in your first print (1/x * x)%n is always 1 ofc. the second one is finey too

if i would translate pow(23, -1, 120) into normal math, how would that look?

is it calculating the multiplicative inverse?

egcd kind of stuff?

[narrow mica]

exactly

[full heart]

hm okay. the -1 is still kinda confusing

[narrow mica]

why?
you write inverses like x^-1, no?

[full heart]

idk but i have to use the extended euclidean algorthm. Theres no x^-1 in it

[narrow mica]

oh, are you saying you're trying to implement a function to calculate the inverse using egcd?

[full heart]

im on my side mission to understand pow(a, -1, b)

i habe the extended thing already

[narrow mica]

which part are you having trouble with?
why using egcd allows you to calculate the inverse?

[full heart]

d is the multiplicative inverse or nah?

[narrow mica]

d would be the multiplicative inverse of e under modulo phi(N), so yes

[full heart]

could u instead write d^-1 to show that its an inverse?

Is it just different conventions?

[narrow mica]

d^-1
yes
convention
yes

[full heart]

oh okay now i get that

[full heart]

does somebody know how to use the euclidean algortithm and what i did wrong?

def egcd(a, b): #extended euclidean_algorithm / find the multiplicative inverse
    i = 0
    qa = []
    x = []
    y = []
    while True:
        q = a // b
        qa.append(q)
        r = a % b
        a = b
        i += 1
        if r == 0:
            break;
        b = r
    x.append(0)
    y.append(1)
    for j in range(i-1):
        x.append(y[j])
        y.append(x[j] - qa[i-j-2]*y[j])
    #return y[i-1]
    res = {x[i-1], y[i-1]}
    return res

the worst thing is, sometimes the result is correct and sometimes its not

although the left thing of res seems to be always right

its supposed to work like with this table

[rotund steppe]

https://codeforces.com/problemset/problem/1821/B

[full heart]

https://paste.pythondiscord.com/D5OA
example

i have no idea why that happens

wrong results dont happen with every number tho

[haughty mountain]

is returning a set intentional?

the ordering of the elements could be whatever

[full heart]

but the ordering isnt random

left one would be the x value in the first row of the table and right int of the set would be the y

[full heart]

in this one

and the x that im returning in the set is correct every time apparently

magic is happening there idk

[haughty mountain]

sets are unordered

[full heart]

oh right

[haughty mountain]

if you care which is the left/right one then you should not be using a set

[full heart]

shit

i dont even need the k

[full heart]

theyre fr just random?

[haughty mountain]

it's unspecified what the ordering will be, you can't depend on it

why would you return a set anyway?

why not a tuple?

[full heart]

omg thank u

i thought i'd be lost on that forever

i thought using {} would be an array

so the only thing i'd have to do would be change the { to [

[haughty mountain]

I would just do return x[i-1], y[i-1]

to return a tuple

tuples tend to be what you want if you're returning a fixed number of things

[half owl]

codeforces has AVL tree problems? for implementing a new function with adding attributes for example

also, is there any place with such problems? also maybe even a place that has full implementations of DSs like fibo heap for reference

[narrow mica]

AVL tree problems, probably not specifically, but you can probably find many that needs a balanced BST and you can use an AVL in those

[severe sparrow]

so rehearsing some DSA last night, I pause my lecture and type out an pop method for my linked list and for whatever reason its more natural to me to use a single temp pointer to move through the list, though this is the second course that has used two pointers to move to the end. (in a linked list self.tail is already known and you can move until self.next == self.tail). What I'm wondering is, why are two pointers better?

def pop_tail(self):

        self.empty_list_chk()

        point = self.head
        follow = self.head
        while point.next:
            follow = point
            point = point.next
        self.tail = follow
        self.tail.next = None
        self.len -= 1
        if self.len == 0:
            self.head = self.tail = None
        return point.value```

vs using py pop_node = self.tail and py while point.next is not self.tail:

[haughty mountain]

what would you assign to self.tail?

[severe sparrow]

it's a pop method so I'd return the value, once pointer.next == self.tail, I'd reassign self.tail to the pointer

[haughty mountain]

oh, you want to try stopping 1 earlier by using an is check?

[severe sparrow]

basically, since the tail is known i already know what to remove right?

I just need to find the new tail...

I don't mean to knitpick, I just wonder if I'm missing something

[haughty mountain]

I think you can do what you're doing

[severe sparrow]

worried that if I don't memorize this two pointer code it'll screw me later but obv I prefer my own

alright, thanks for looking at it, ima get back to it

oh you know what...

single node edge case would fail

[shut basalt]

lol

[severe sparrow]

TIL

[shut basalt]

but then again, you are still checking if self.len == 0: here, so it isn't more expensive to add that check but move it up for your mthod

[severe sparrow]

This code is from the lecture

I was to tired to sort it out before I went to bed

[shut basalt]

yeah that's what I meant, i meant "your method" as your alternative suggestion

[severe sparrow]

lol i'll chew on that in the shower, ty

[mint sun]

HELP, i have darts tft that went well in the tests but idk y it started giving out train_loss=nan.0, i even converted the covs to dataframes, dropped na and converted them back to series.

[random bison]

Howcome all of a sudden I have an issue with my main.py? Its like saying failed building wheel with aiohttp and failed to build installable wheels for some pyprojoect.toml

[haughty mountain]

<@&831776746206265384>

[halcyon lake]

Hey everyone lol

[full heart]

hey does anyone know any good resources to understand aes-256 key extention?

its the only thing my aes is missing

[terse hedge]

Which book is best for learning data structure and algorithms python

[modern gulch]

There's many standard textbooks.
Intro to Algorithms,
Analysis of Algorithms,
DSA in Python are the ones I know. The first was what my Uni used many years ago.

[full heart]

how am i supposed to do that when i have a 256 bit key

if i'd put it in the 4x4 grid that would be 2 bytes per cell

and obviously that wont be round keys with 16 bytes

any idea what i can do?

or do i instead generate w0 w1 w2 ... w7

[random spear]

Is there a kinda "calculator" of time complexity if i put a code?

(gpt doesnt count)

[haughty mountain]

just learn to analyze your own code

[random spear]

Yea i know how

Wondering if there was a tool

If not, the invention of it would be cool

[haughty mountain]

you can try to approximate based on actual run times, but it will be a quite error prone thing

[lean walrus]

I would not be surprised if that tool turned out to be impossible due to stuff like halting problem

[dim stone]

How do data structs work. Is it uniform across all programming languages

[verbal agate]

do we have anything more optimal than this?

class Solution(object):
def isPalindrome(self, x):
return str(x) == str(x)[::-1]

[haughty mountain]

define optimal

asymptotically you can't do better in the worst case

you can do better in the best case

you're also effectively going over the string twice

but in terms of actual speed this will be quite quick because the actual logic is not written in python

[verbal agate]

yes in terms of speed it is the best although i have 2 more solutions i tried them

but that shows me the best output in terms of execution time

[haughty mountain]

python can be annoying in that in some cases the worse solutions can do better

if the better solution involves writing python code, and the worse solution is just calling some of the stuff written in C

[verbal agate]

solution 2:

class Solution(object):
def isPalindrome(self, x):
split_digit = list(str(num))

reverse_digit = list(reversed(split_digit))

join_digit = "".join(reverse_digit)

if "".join(split_digit) == join_digit:
return True
else:
return False

solution 3:

class Solution:
def isPalindrome(self, x):
if x < 0:
return False

    reverse = 0
    temp = x

    while temp != 0:
        remainder = temp % 10
        reverse = reverse * 10 + remainder
        temp = temp // 10 
    
    return reverse == x

[verbal agate]

yeah that is true

[full heart]

who thought this is a good idea?

numpy solves this but why is it that way in python?

[rare laurel]

not copying implicitly is one of python's design points

[full heart]

copying implicitly?

why would someone need an array with duplicates

[rare laurel]

why would someone want ["hello"]*n to copy the string n times?

[full heart]

just to create a string array with n elements

[rare laurel]

well, the list stores references (pointers), not the actual values, so 1 string and n references to it is enough. what you want needs copies of the actual values.

[full heart]

or is there a way to make a 4*4 array

[full heart]

ah okay

[stray fractal]

nobody thought of it, it's just a side effect

[full heart]

so basically python doesnt support creating empty multidimensional arrays?

[rare laurel]

not with *

[full heart]

what instead

you cant create an empty one dimensinal array either right?

[rare laurel]

of immutable values? you can, will be fine

[stray fractal]

!e ```py
a = [[0]*4 for _ in range(4)]
print(a)
a[0][0] = 1
print(a)

[halcyon plank]

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

001 | [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
002 | [[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

[stray fractal]

isn't that just []

[rare laurel]

by empty they mean a bunch of zeros

[full heart]

yea right but you cant do array[x] then

[stray fractal]

doesn't that just do the same thing as in numpy

[rare laurel]

if you made it check whether its mutable or no, then thats another special case for people to remember
the way it is currently is consistent for everything: [x]*n is a list with n references to x

[stray fractal]

wait what are we talking about

what's with array[x] being disallowed

[full heart]

yea but i can use the [[0]*4]*4

[rare laurel]

not "disallowed", but being an indexerror
by "empty array", they mean "array of zeros"

[stray fractal]

that doesn't error in numpy..?

[full heart]

yea thats why the zeros

[full heart]

it does

[stray fractal]

okay i get it halfway

now

[full heart]

but it doesnt use this reference thingies

[rare laurel]

yes, because it stores the actual values, not references. you just initialized it with a list, but its not a list.

[stray fractal]

i see

so np.array() is like a copy.deepcopy()

nvm

[full heart]

i think i got it

although [0]*4 dont reference eachother

[rare laurel]

[0]*4 is a list with 4 references to the same 0 object

[full heart]

no

[rare laurel]

!e

xs = [0]*2
print(xs[0] is xs[1])

[halcyon plank]

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

True

[rare laurel]

yes, because you assigned to a[0]. you did not mutate the object that is at a[0]: in fact, in pure python, you cant, because integers are immutable.

[full heart]

there i assigned it only for [0][0]

[stray fractal]

same object, different alias

[rare laurel]

but a[0] is a[1], so a[0][0] is a[1][0], etc

[full heart]

yea in the multidimensional thing

[stray fractal]

when you do [x] * y, you have y number of references in the list to the same x

[full heart]

i think i understand more or less

[stray fractal]

!e ```py
a = [0]
b = [a] * 5 # 5 references to a

print(a)
print(b)
a.append(1)
print(a)
print(b)

[halcyon plank]

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

001 | [0]
002 | [[0], [0], [0], [0], [0]]
003 | [0, 1]
004 | [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1]]

[full heart]

but def didnt know what happend the first time i tried to use a multidimensional array

[stray fractal]

what we are doing here is modifying a

but all the references stay the same

!e ```py
a = [0]
b = [a] * 5 # 5 references to a

print(a)
print(b)
b[0] = [1]
print(a)
print(b)

[halcyon plank]

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

001 | [0]
002 | [[0], [0], [0], [0], [0]]
003 | [0]
004 | [[1], [0], [0], [0], [0]]

[stray fractal]

now, what we are doing here is modifying the "reference"

[rare laurel]

!e

import ctypes as c
xs = [1] * 2
c.cast(id(xs[0])+24, c.POINTER(c.c_int))[0] = 2
print(xs)

[halcyon plank]

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

[2, 2]

[full heart]

copying the pointer of the onedimensional array a

[stray fractal]

now all python objects are pointers

when you modify the value of the object, all references to it will also look like they've changed

[full heart]

yea i get that

its like having an array of pointers that point to one value

[stray fractal]

however, if you reassign the reference to an object (e.g. a[0] = ...) then the reference points to a different value

[stray fractal]

yes

that's what happens when you multiply lists

[full heart]

does this have any practical value?

or just because python is built that way

[stray fractal]

it's simple and it doesn't cause a huge problem with performance

simply put, python is just built that way

[full heart]

hm okay

ig thats just something you need to know before you try to make multidimensional arrays

but thanks for the explaination

[ivory yacht]

There's a good reason for it - a list is generic, it doesn't know or care about what you put inside it. If you wanted it to copy elements, it'd meed to know how to do that (which isn't always possible, files for instance).

[rotund steppe]

import math
z=int(input())
for t in range(z):
m=int(input())
a= list(map(int, input().split()))
b=list(map(int, input().split()))
cnt=0
cnt2=0
minidiff=math.inf
if a==b:
print('YES')
else:
for i in range(m):
if a[i]<=b[i] :
cnt+=1

    if cnt>1:
        print('NO')
    else:
        for i in range(m):
            if a[i]<b[i] :            
                c=b[i]-a[i]

            else:
                minidiff=min(minidiff,a[i]-b[i])
                if minidiff<c:                   
                    cnt2=1
                    break
        if cnt2==0:
            print('YES')
        else:
            print('NO')

please help with thhis code

https://codeforces.com/contest/2055/problem/B

[worldly linden]

Any one has watched the MIT course for data structure and algorithms on Linear sorting? This is the fifth video I think... I'm a bit lost of what is being explained, if someone could clarify :c

[modern gulch]

Drop a link and specific q?

[worldly linden]

hmm wait

https://www.youtube.com/watch?v=yndgIDO0zQQ&list=PLUl4u3cNGP63EdVPNLG3ToM6LaEUuStEY&index=7&t=132s

Here is the link; normally the user is talking about "linear sorting" so I believe it would be something like bubble sort

I'm completely lost what happens in the video 😭 I know that it becomes tuple sorting something like that I think

[modern gulch]

At the marked time, he's recapping the previous lecture 4 which covered hash tables.

[worldly linden]

ops sorry, this isn't the right time frame... I think it's somewhere in the end at 26min, I didn't really understand what the professor was explaining, like he broke an index with a minimum and maximum limit, then these min and max limit form a tupple and he would sort that tupple

[modern gulch]

To understand this (edit: this = the motivation / purpose), you first have to understand the DAA sort talked about at 20:00-22:00, and understand what "u" represents. Can you explain what "u" means?

there's three steps to understanding: understanding what "u" is, understanding why he says "this is not helpful" at https://youtu.be/yndgIDO0zQQ?list=PLUl4u3cNGP63EdVPNLG3ToM6LaEUuStEY&t=1454, then you're ready for what happens directly afterwords.

** this is assuming you're trying to understand why the stuff at 26:00 is being done.

[modern gulch]

If you just want to understand the tuple sort: is he's sorting by (k//n, k%n)... which basically is sorting by k%n then k//n (note the "stable sorting" part). Forget about "tuples", just think of it as sorting by k%n then k//n. This is explained at 32:00. which leads to counting sort at 39:00

[haughty mountain]

sounds like a build-up to radix sort

[modern gulch]

Yup, literally the next topic right after 🙂

[gaunt coyote]

v

[worldly linden]

euh from memory, I think u is the universe of keys? I don't remember, need to check

[worldly linden]

Ok, later on tonight, will just review from 20:00 to 30:00 to see what is being said once again and will just come back

[modern gulch]

The thing to think about is: Why does the size of U matter?

[worldly linden]

Yep, if u is the universe of keys, then I have some suggestions but I need to confirm whether that's what u is for... I will come back with questions !! Thanks ! 👍

[modern gulch]

Great... all of the intuition here starts with understanding u, why it matters, and why it can't be really large nor really small

[worldly linden]

noted 💯

[worldly linden]

sorry, one small question, I don't understand how a direct access array differs from a normal array, can't we just call it an array? what is the difference between a direct access array and a normal array and why use a direct access array not just a normal array ?

[modern gulch]

In the "direct access array" described in the previous lecture, how are elements indexed? The answer to this is basically the entire previous lecture.

[worldly linden]

euh instantly, just by using the index location

like we that something is at location 23, so we just write something like fetch[23]

[modern gulch]

And what is the index location of "BillyBobby"?

[worldly linden]

euh

we don't know if the value exist, so we would have to search into the array first? then if it's there, return its index?

OR

we can use the hash table for that? Like the key is "BillyBobby"; we know that this key will be found at a particular index. So what we do, is we "query" the hash table to find that key. Then we will find a particular index ? something like that?

[modern gulch]

This is what Lecture 4 covers: Hashing.

[worldly linden]

yep

just use this idea xd

but don't know if its the answer you are looking for

[modern gulch]

So, a direct access array just means: if I know the key, then I know exactly where to get the value from.

[worldly linden]

ah

I think I have a confusion, I thought that, we should know the location to know if the value exist

but this don't make sense I think

Like we don't know where "BillyBobby" is

[modern gulch]

That's the point about U: if the size of the array is the size of U (the range of possible keys/indices), then for a given value, it must be stored in exactly one location.

And lecture 5 then introduces the question: what if U is larger than the size of the array?

[worldly linden]

yeahh I see, I will need to go through the lecture 5 once again, I will come back then, thanks, really appreciate ! 👍

[modern gulch]

When going through the lecture: ask "why" a lot. Why DAA? Why not always DAA? Why counting sort? Why is stable sort important here? Why radix sort? etc.

To me, the "why" is more interesting than the details of "how".

[worldly linden]

got it, ty !

[brazen matrix]

How to practise and where?

[timber moat]

Hello, guys. I'm a beginner python programmer and I've learnt the language, I would like to start learning algorithms. Could anyone pls suggest me a good book or course for that?

[modern gulch]

#algos-and-data-structs message is still a great resource.

[bright coyote]

Desperately need help understanding this A* algorithm question - I have an decent understanding of the question but I think im missing something especially when Im filling in distance travelled. Any help?

[bright coyote]

Figured it out

[hybrid plume]

is this lecture a good breakdown of hash tables? I was having some trouble with open addressing

[modern gulch]

Lecture 4 is on hash tables

[hybrid plume]

do you think the intro to alg book is comprehensive enough for the "all i need to know about dsa" pre-job? I plan on coming back to re-glossing the material over again but while I'm in uni do you think that's a good place to just get everything

[modern gulch]

It's a good question, I know different ppl have different opinions here. My opinion is the bare minimum is: know the contents of your undergrad syllabus. It's not the entire book, and you're not really going to be quizzed on it in an interview... but you should be able to work through problems with perhaps a minimum prompt.

Then: leetcode easy's or equivalent should be easy for you. That's not a high bar. Mediums should be solvable, even if some trip you up. And, hards shouldn't feel impossible.

[hybrid plume]

awesome, much appreciated. I have a weird transfer situation with my uni on dsa so I just wanted to have 1 killer book to cover my bases on it (the way they explained at my uni was not so in depth comparatively). I was recommended the intro to alg cormen and "common sense guide to data structures", but I dont have enough time to dissect both books etc

I'll watch the lecture series and go through the intro book then

[modern gulch]

The lectures are a bit dense, so don't get discouraged... a lot of the details are forgettable, if you can remember the melody.

[hybrid plume]

Preciate it big time, and that’s an amazing add on to describe that as well! I’m dead set on finishing intro to alg’s start to finish and the math for comp sci with leighton book by the end of march

[surreal imp]

sorted_keys = sorted(hash_map, key=lambda x: hash_map[x], reverse=True)
how do I even begin to try and understand this line of code 😭

[regal spoke]

This line is not really complicated once you know how to sort with respect to a key function

hash_map is an iterable

The key parameter tells you in what order to sort the elements in

[regal spoke]

The "lambda" is a way to create a function. It is the same as doing

def f(x): 
    return hash_map[x]
sorted_keys = sorted(hash_map, key=f, reverse=True

[trail light]

is there a more efficient way to put a matrix into RREF than my bug infested code 😭

its genuinely annoying me sm theres way too many like weaknesses (not counting the BUGS) and like im almost certain theres an easier way n im overcomplicating it 🙏😭

[lucid python]

Hi. If I take a discrete math course before d&a are there sections more important than others?

[modern gulch]

? Why would the order matter?

[haughty mountain]

<insert permutation/combinations joke>

[lucid python]

I'm open to hear other povs. Courses often have discrete math as a prerequisite. I may just practice d&a interviews questions while learning discrete maths.

[surreal imp]

does anyone know any good videos for sliding window technique

[modern gulch]

If discrete is a prerequisite, and you're taking discrete first, what's the question? Genuinely don't understand what you're asking

[lucid python]

I asked if anyone structured their learning outside the conventional order DM > D&A and what it was like

[obtuse arrow]

hmmm

[modern gulch]

Is that the conventional order? AFAIK, neither are typically prereqs of each other.

[lucid python]

ok

[wet pendant]

@heady jasper what are you doing here

[vast zephyr]

what does collection means

it says i can't use collections in the homework about Queue

[haughty mountain]

!d collections

[halcyon plank]

collections

Source code: Lib/collections/__init__.py

This module implements specialized container datatypes providing alternatives to Python’s general purpose built-in containers, dict, list, set, and tuple.

[dim rain]

[summer fossil]

class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        delrow = [0,1,0,-1]
        delcol = [1,0,-1,0]
        vis=[[False]*n for _ in range(m)]

        def solve(row,col,vis,cost):
            if row==m-1 and col==n-1:
                return cost

            mincost=float('inf')
            vis[row][col]=True

            for i in range(4):
                nxt_row,nxt_col = row+delrow[i],col+delcol[i]
                if 0<=nxt_row<m and 0<=nxt_col<n and vis[nxt_row][nxt_col]==False:
                    next_cost = cost + (1 if grid[row][col] - 1 != i else 0)
                    mincost= min(mincost,solve(nxt_row,nxt_col,vis,next_cost))
                    
            vis[row][col]=False
            return mincost
        return solve(0,0,vis,0)```

https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid why it's not workin!

[narrow mica]

and wdym by its not working

also, looks like a bfs problem imo

[summer fossil]

my code gives wrong ans!

brute force!

[narrow mica]

doesn't even look like the code will run tbh

next_cost = cost + (1 if grid[row][col] - 1 != i else 0)
```where's this `cost` variable

oh nvm i see it

ahem, anyways...
the problem is you visiting a cell doesn't guarantee that whatever cost you've calculated so far is best for that cell
e.g. imagine this graph

↓→→↓
→→→→
```your code will visit the cells in this order (due to using dfs & the order of delrow + delcol)

1234
8765
```so your answer will be 1 (from changing the starting cell to →) when the actual answer is 0

your code is also not actually really a brute force solution
I'd imagine that for this problem such a solution would be like trying out every possible combination of cell changes and seeing if it works
though this would very likely time out

[summer fossil]

r u saying it's worst than brute force!

[narrow mica]

I'm just saying your code isn't brute force because the latter usually entails some sort of "trying every possibility of ..." which your code isn't doing
brute force wouldn't really be practical here anyway

[summer fossil]

     return cost```
is it going only one times then break!

[narrow mica]

not sure what you're trying to say here

[narrow mica]

the problem w/ your code is this

the actual solution involves looking at this as a shortest path problem

[summer fossil]

Lord Djikstra!

[worn ore]

or A*

[narrow mica]

you can, though it's not required here because of a special property of the graph you get in the problem, which allows you to use a slightly modified version of bfs

[narrow mica]

overkill in most cases in terms of dsa problems

[narrow mica]

like remember to the time when you can use plain ol' bfs to find the shortest distance on a graph. this likely came up in some grid scenario, i.e. the graph just looked like a 2d grid. why could you just use bfs here, and didn't need dijkstra?
then think about the graph you get in this problem

[worn ore]

my idea i just to solve a problem with the most efficient solution like Design Patterns

[narrow mica]

not sure what your point is

[worn ore]

i mean there a solution to this problem but yes it depends on your system

[shell breach]

Hi guys I just created a hash or encryption algorithm

[finite sierra]

does anyone have experience with integrating functions that are noisy? like the sensor data from an accelerometer to get the velocity?

im trying to control the mouse with my phone's accelerometer, but its going kinda rough tbh. the pointer is either drifting or moving back or not moving at all

[raw zealot]

import sys
input = sys.stdin.readline

t = int(input())


def check(k):
    total_need = 0
    max_need = 0
    for x in arr:
        need = max(0, k - x)
        total_need += need
        max_need = max(max_need, need)
    return total_need <= m * s and max_need <= m

for _ in range(t):
    n, s, m = map(int, input().split())
    arr = list(map(int, input().split()))
    lo, hi = min(arr), min(arr) + m


    ans = 0

    while lo <= hi:
        mid = (lo + hi)//2
        if check(mid):
            lo = mid + 1
            ans = max(ans, mid)
        else:
            hi = mid - 1

    print(ans)

[raw zealot]

what makes this code slow? i get tle on 2 cases

sadly the platform i am practicing does not have pypy

[naive oak]

it's not guaranteed that if k is doable, then all larger k is also doable, no?
like take

3 2 100
0 0 1

you can reach 1, but never 2

[raw zealot]

yeah its not

wouldn't it make

monotonic decreasing [works works works ,doesnt , doesnt ... doesnt]

also it did not wa anywhere too

[naive oak]

oh I misread your binary search

[raw zealot]

but tle's for some reason

ah

cpp passed smh

i think python3 is being a bottleneck

[naive oak]

maybe nlog n is just too slow for python

yeah

[raw zealot]

yep

[naive oak]

this seems doable in O(n) tho

[raw zealot]

yeah but idk how

difference array maybe or smth

[naive oak]

for a quick optimization, doesn't lo = max(arr) work

[raw zealot]

i might not have that much operations

oh i didnt send constraints

s subset size, m operations

[naive oak]

what do you print if there is no way?

[raw zealot]

min of array

if M = 0

[naive oak]

oh

the question is phrased confusingly

[raw zealot]

true

[naive oak]

I thought it meant the min value should be the max value in the array

[raw zealot]

vague

[naive oak]

not the max over all possible thingies

ok

[raw zealot]

i think shifting to cpp is easier at this point

make pypy general python interpreter fr

[silent kayak]

Hey

[signal hatch]

anyone by chance knows an active disocrd for compittive programing

[lilac cradle]

how would one take a list of values and try to find an exponential fit for it?

[jolly mortar]

fitting y = A e^Bx ?

taking ln on both sides transforms it into a linear regression

[worldly linden]

sorry it's been a long time, I'm currently re-watching the video, I'm at 26:00, I'm not understand what the professor is trying to do :c

I'm lost about the equations/ lower bound or upper bound

I don't understand, why use the quadratics of n^2 ? what is being proved ?

[modern gulch]

Which video?

[worldly linden]

https://www.youtube.com/watch?v=yndgIDO0zQQ&list=PLUl4u3cNGP63EdVPNLG3ToM6LaEUuStEY&index=7

This one, sorry it's been a long time, you already have a looked at it I think

[modern gulch]

Are you asking why he asks: "What happens if we expand the range a little bit, say, u<2**2?"

At around 23:56?

[worldly linden]

yeah at first, but I think I've understood that part. The idea is what if input size becomes larger than u, the universe of keys which normally should be distinct; if n is greater than u, this mean there will be duplicated values.

This is ok but I don't understand later on at 26:00 where he derives the formula of (a,b) etc

[modern gulch]

He is saying: if a=k//n, and b = k%n, then: If you know "a", "b" and "n", how do you solve for k?

[worldly linden]

yeah he is deriving an equation to find the value of k, given a and b but I don't understand why a and b are being created, like why use them or why k is being split into a lowe and upper bound

[worldly linden]

it's like this

[modern gulch]

Do you see the data structure he creates later for counting sort? It has n slots, and collisions in each slot are ordered.

a and b are how they determine which slot, and which order within the slot

[wicked cosmos]

Hi

[rotund steppe]

https://codeforces.com/contest/2061/problem/B

z=int(input())
for _ in range(z):
n=int(input())
a = list(map(int, input().split()))
dl={}# of duplis
for i in a:
if i not in dl:
dl[i]=1
else:
dl[i]+=1

if len(set(a))==len(a):
    print(-1)
# elif len([key for key, value in dl.items() if value >=2])>=2:
#     print(*[key for key, value in dl.items() if value >=2])
elif len([key for key, value in dl.items() if value >=4])>=1:
    print((4[next(key for key, value in dl.items() if value >=4)]))
else:
    res=[]
    cnt=0
    for i in d l:
        if dl[i]>=2:
            res.append(i)
            res.append(i)
            cnt+=1
        if cnt>=2:                
            break
    if cnt>=2:
        print(*res)
    else:
        for i in a:
            if a.count(i)>=2:
                temp=i
                a.remove(i)    
                a.remove(i)
                break 
        a.sort()
        l=0
        r=len(a)-1
        cnt3=0
        while l<r:
            if a[r]-a[l]<2*(temp):
                cnt3=1
                break
            l+=1
            r-=1
        if cnt3>0:
            print(temp,temp,a[l],a[r])
        else:
            print(-1)

🐱 ...which edge cases is getting missed ,anybody tell plzz

[wicked cosmos]

Hello Everyone

[sharp pilot]

unfortunately cant help

Good day all, I am trying to work through Problem 2 of this coding challenge but I have no idea how to proceed https://challenges.reply.com/challenges/coding-teen/code-teen-2024/detail/

The only idea I have is a brute force solution ie trying to divide the truffles of Mia and Genga into groups with total sums that are equal and

total_sum_of_truffles / Amax <= total_sum_in_each_group <= total_sum_of_truffles /  Amin <= W

If i can make groupings in both that satisfy the above condition with equal sums, then Mia could harvest her group of truffles in a day, Genga can harvest his and they will be able to harvest all in the allowed range of days.

However even trying to implement that is a pain. Could someone please give a hint as to how to proceed ? Thank you

[tight cedar]

I can't view the problem without login it can you send it here

[manic bear]

Bit stumped. I'm working on what I think is a simple problem. Read in two files into two different data frames. Outer merge with a common field. Second file in the merge has a qty column. Last step was to filter the data frame to find quantities in the qty column over a certain value. No matter the steps I take I can't seem to get that string as an integer in the second file to be handled by the filter as an integer. I've tried various fixes like fillna, astype'ing etc. Wondering if there is some sort of concept that I'm missing?

[sharp pilot]

Its a bit long and we cant send pdfs. Ill attach sreenshots

[outer talon]

Hi, since this channel too is more or less for helping, I have created a post (#1331968013934530630) and need help. It's about SymPy, its Expr objects and black holes

[worldly linden]

Hello guys, can someone explain how counting sort algorithm works pls. I understand that we have an input array and from that input array, we create a count array in which we store the frequency of each digit, where the index of the count array represent the number, like index of 0 = number 1 and the number of times it appears.

What I'm confused about is how we create the sorted array from that. I know that we create a cumulative array, this is where I don't understand how we come to the sorted array. There are also some formula used where we must subtract 1, I didn't understand why. Would really appreciate if someone can explain from the cumulative part pls

[narrow mica]

the detailed explanation depends on the implementation, which there are a few
general idea: through some way, create an array offset, where offset[x] is how many elements should be placed before element x. Then, you can just do:

for x in original_array:
  index_to_place_x = offset[x]
  sorted_array[index_to_place_x] = x
  offset[x] += 1  # the next `x` we see should be placed after the current `x`

e.g. for this array:

1, 2, 3, 1, 2, 3, 1, 2, 3
````offset[2]` is `3`, because in total there are 3 elements (the three `1`s) less than `2`. This means that there are 3 elements that should be placed before any `2` in the sorted array. So, the first `2` in the sorted array should go into the 3rd position (0, 1, 2 should be the `1`s), the second `2` into the 4th position, etc.

[worldly linden]

Hmm, from what I understood from a counting sort:

We have an input array (unsorted array). Let say we have the following: [0,1,2,1,1,3,4].

In order to build a counting sort, we must first know the number of times (frequency) that each element appears in the array.

For this, we create another array, a count array / frequency array. Based on the input array, we would normally have an array of size (4 - 0 + 1) = 5. The formula is max value - min value + 1.

count_array = [1,3,1,1,1] - 0 appears once, 1 appears 3 times, 2,3 and 4 appear once.

Now that we have the count_array, we need to find the cumulative of these number to know at which position each number would be at most.

Like, cumulative array = [1,4,5,6,7]

So this tells us that 0 would be at most a location 1, <= 0. Similarly, 4 will be at most at location 7, <= 7.

From that, we need to create the sorted array now. To maintain stability, we start reading the input array backwards. This is where I'm lost, I don't know how to proceed next.

I found the following formula online:

outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i]
countArray[ inputArray[i] ]  = countArray[ inputArray[i] ]–-

But I don't really understand what's happening :c

[narrow mica]

it's just a slight variant of what I said

• the cumulative array (countArray in your formula) you have is the offset I have
• inputArray is my original_array
• outputArray is my sorted_array
• you place the elements going backwards
  if using my code as demonstration again, barely anything changes

for x in original_array:
  index_to_place_x = offset[x]
  sorted_array[index_to_place_x] = x
  offset[x] -= 1  # the next `x` we see should be placed before the current `x`
```the idea is that now, you start by placing the last `x` instead.
for this array:

1, 2, 3, 1, 2, 3, 1, 2, 3
````offset[2]now starts from5, because there are 5 elements that should be placed before the last 2(the 31s and the first 2 2s). The second-to-last 2should go into position4, and the third-to-last 2should go into position3`

some details:

• offset is slightly different from the cumulative array - the latter is always 1 above the offset we want, so that's why you see countArray[ ... ] - 1 in the first line of your formula
• the 2nd line of the formula is just trying to say countArray[ ... ] -= 1

[worldly linden]

yeah I see, I also understood the code

It's clearer now, thanks !

the offset, the way you used it, the values are always 1 less than in a cumulative array , then we don't need to subtract 1?

In fact, like you said, there may be many implementation of a counting sort? Like there is no "universal" way of how a counting sort should be implemented?

[narrow mica]

sure, though in actual implementation, offset will be calculated doing the cumulative array thing anyways

[narrow mica]

well, there are at least 2 ways as demonstrated, i.e. placing the elements forwards or backwards

[worldly linden]

Yep I see, thanks !!

By the way, is there a difference between radix sort and counting sort?

[narrow mica]

radix sort usually uses counting sort in its code

[worldly linden]

yeah just read that, is there a difference between the 2?

I mean, why one is called radix sort and one counting sort

[narrow mica]

a big simplification is just: radix sort is you do counting sort on each digit

so e.g. if your array to sort is [1, 9999999] counting sort will need an array of size 10000000 while radix sort wont

[worldly linden]

yep I see, thanks !

[queen stirrup]

@ionic gulch

[ionic gulch]

what bro

[queen stirrup]

can you accpet my

discord friend req

[noble river]

can anyone tell me what the | operator does?

[narrow mica]

bitwise or
& is bitwise and while ^ is bitwise xor

[noble river]

| is the same as ^?

[noble river]

but isnt | used for something else?

[narrow mica]

no, | is OR while ^ is XOR

[noble river]

class User():
  ...

selected_user: User | None = None
print(selected_user)

[narrow mica]

sure, do you have a specific example in mind

[narrow mica]

that's a typehint union, i.e. selected_user might be a User instance or None

[noble river]

ah i see, thanks!

[narrow mica]

prior to 3.10, you'd use typing.Union instead of |

[noble river]

oh ok

i understand

thanks

[blazing basalt]

Can you recommend a YouTube channel that explains algorithms? please

[noble river]

i watch "Greg Hogg" a lot

[blazing basalt]

i'll try thank you, just have a competition in algorithms this week need to be prepared

[noble river]

do you just want the algorithms or the math behind them too?

[blazing basalt]

both

[noble river]

oh ok

good luck

[blazing basalt]

thanks

[haughty mountain]

xor for types would be wild

[rare laurel]

with intersections it could make sense, though not sure when would it be useful
"either one, just not the intersection"
though then maybe (A | B) & ~(A & B)

[fiery cosmos]

It probably exists somewhere

Lambda is right, with intersections it would make more sense

[rare laurel]

imagine you have something like a.. List2[A, B], which is basically 2 lists, but with type dispatch on append: it can take an A | B (currently), and append it to one of the 2 lists accordingly
with ^ you could express it not being both so there would be no confusion on something like a TypeError happening when its in the intersection (which could easily happen if A or B are an abc / protocol / whatever)

i imagine there should be a better example but, just the first thing that came to mind

[slim vault]

Guys so I'm new to leetcode, I wanna know if there is a console option available or something where I can run print statements that I'm writing. I don't wanna run the internal test cases yet.

[modern gulch]

You should probably get comfortable running code outside leetcode, such as in VSCode or an online environment like colab. That'll help with running and debugging.

[slim vault]

yeah I just wanted to prepare for real test cuz sometimes they don't let you change tabs

but yea ig they won't use leetcode for it but their own environment

[brave kettle]

Anyone good at using turtle

[modern gulch]

Ask in #python-discussion , and just ask the question.

[toxic hare]

3d noise generator

https://paste.pythondiscord.com/37IQ

[lean walrus]

is it 3d?

[rare laurel]

x, y, time

[lean walrus]

fair enough

[lusty wadi]

anyone ever coded crypto arbitrage bot?

[lusty wadi]

why clown emoji?

[lime haven]

Hello everyone!
I am a full stack developer with rich experience about python and python web, app frameworks.
Now I am looking for a python job here. Please let me know if you have any project and need any help from me.
Thx.

[boreal wadi]

I have problem... I developed algorithm for technical analysis and it needs to be 1200x faster but I can't share the code because it would be sharing my own personal data and strategy 😦

[upper ingot]

Im trying to build a recommendation system for golfers. What this will do is tell the golfer which club and where to hit the ball on the golf course based on data from users and their preformance throughout a round.

I've made custom data sets since Im specalizing it all for my local golf course and i am at the point where I am generating simulation data for the first hole. This data will be used to recommend stuff for users. Does this data have to be "good" golf shots or does it have to be a mix?

[blazing veldt]

I would say mix, as it would need to average it out.
If you only give it good shots, what is it gonna do when a player is not close to a good shot?

[upper ingot]

ahhh okay I didn't really see it from that point of view

thank you

[blazing veldt]

I mean I don't play golf, so not sure my comments made sense.
But as with any data, I would say give it variable options.

[upper ingot]

yeah makes sense. If all the shots hit the fairway then it won't know what to do if I land in the rough or a bunker

if im going to do that i deffo will need a more diversed club selection for each data point

[boreal wadi]

he is idiot dw about him

[toxic hare]

i made an updated version of it
and yes its 3D and no it doesnt use time, im actually just moving throught the Z axis using q and e as the keybinds lol

it doesnt use perlin noise either

[outer rain]

I'm struggling to proof the following problem is NP complete

There are N agents on a rectangular grid. Each agent can move in one of four cardinal directions or stay in it's current place. Agents can't swap or collide. Some agents actions are locked, known, and cannot be changed. Can other agents move in such a way that they won't collide this step? Problem considers each agent moving (or staying) exactly once.

I tried reductions to 3-SAT (building a circuit out of this) and to grid hamiltonian path (known to be NP complete https://www.researchgate.net/publication/220616693_Hamilton_Paths_in_Grid_Graphs), but to no success.

maybe it is in P after all?..

wait, I think it's just a flow problem, I'm dumb, nevermind

[haughty mountain]

at first glance this sounds like P, yes

[raven dagger]

chat

the governemnt here

fucking blocked bbc

the bri'ish broadcasting corporation

lmfao

absolutely hilarious

hysterical

[shadow glen]

can a bigger list be compared with a smaller list?

like
if big_list in small_list?

[narrow mica]

I assume you mean if small_list in big_list, still no though

[shadow glen]

nope, i mean big_list in small_list literally

[narrow mica]

oh, I think I see what you mean
then yeah, it'll check if big_list is an element in small_list

>>> big_list = [1, 2, 3, 4, 5]
>>> small_list = ['a', [1, 2, 3, 4, 5]]
>>> big_list in small_list
True

[plush isle]

trying to do a leetcode problem (I'm probably in the wrong direction) and the yellow underscore says it's a tuple and gives an error, I checked everything and it's either int or list, don't understand why I get this at all

[narrow mica]

what are you expecting from those returns that's getting marked?

you're essentially doing something like my_list[1, 2], which isn't allowed

[plush isle]

trying to return a
list[ list[int] ]

[toxic hare]

i would reccomend taking a look at
"the reverse puzzle game"

they have it so an agent finds the optimal path to the exit

and included in this is another agent, the evil bunny, which can move in cardinal directions

icelypuzzles and aliensrock made videos on the game

[shadow glen]

how do i check if a dictionary has as key i offer

i also need that for value

[narrow mica]

if key in my_dict:

[upper ingot]

whats the best way to learn algorithms? I feel like im just chatgpting everything and I cant replicate

For example I wanted to make a mixture distrubution and wanted to adjust a pitch based on a players score. I couldnt figure out how to do it on my own

[narrow mica]

well, we wouldn't recommend LLMs here for starters (prominent reason being you can't check by yourself if it's wrong or not if you don't already have the knowledge)
depends on where you encountered the algorithm I suppose, i.e. if you see it on a book then read what that book says

personally I'm not that familiar with what you're doing, here's one of the search results if that helps
you can also consider posting the incomplete code you have and wait for someone knowledgeable enough to come help

[upper ingot]

yeah that link helped a lot thx. This is such a rabbit hole lol I've taking programming seriously in the past few months once I realized i was cooked in my course

[shadow glen]

how do i clear a value from a key in a dict?

[narrow mica]

dict.pop(key)

[lusty wadi]

anyone can check my code ?

[shadow glen]

guys, i need help with an algorithm, i'm trying to compare if the day is the next day, but it's already flawed due to when it's next month it won't work

if end.day > start.day:
            time = (end.minute + end.hour*60) - (start.minute + start.hour*60) + 1440
        else:
            time = (end.minute + end.hour*60) - (start.minute + start.hour*60)

how do i properly compare if the next day is a new day?

even being a new month or year?

end and start gets a datetime.datetime thing

each in a different part of time

[modern gulch]

Could you ask in #python-discussion ? And, tell us what data types you have here.

[rigid charm]

What channel can I ask about pytesseract?

[half owl]

how do i fix the pointers for a,v,w,e? so that i'll end up with a correct circular linked list

[solar steppe]

Hi can someone pls explain recursion to me. I’m trying to write a matrix multiplication recursively but I’ve been told how I’m doing it isn’t recursive. I don’t know why I don’t understand the logic of recursion 😭

[jovial pilot]

Uhm, quick question (might be dumb) i am trying to multiply a matrix and a vector in my normal calculator yet i get a different result than my python code:

X = np.array([
    [1, 6, 0],
    [1, 7, 1],
    [1, 9, 2],
    [1, 11, 3],
    [1, 13, 4],
    [1, 15, 5],
    [1, 17, 6],
    [1, 18, 7],
    [1, 19, 8]
])

y = np.array([96, 189, 283, 373, 467, 553, 647, 733, 832])

U= X.T @ X
theta_star = np.linalg.inv(U) @ X.T @ y
print(theta_star)

I can confirm that X.T @ y is the same as the vector shown here

X = np.array([
    [1, 6, 0],
    [1, 7, 1],
    [1, 9, 2],
    [1, 11, 3],
    [1, 13, 4],
    [1, 15, 5],
    [1, 17, 6],
    [1, 18, 7],
    [1, 19, 8]
])

y = np.array([96, 189, 283, 373, 467, 553, 647, 733, 832])

U= X.T @ X
# Berechnung von theta*
theta_star = np.linalg.inv(U) @ X.T @ y
print(np.linalg.inv(U))
print(X.T @y)
print(theta_star)

[[18.86666667 -3.2         5.53333333]
 [-3.2         0.55384615 -0.96923077]
 [ 5.53333333 -0.96923077  1.71282051]]

[ 4173 62916 22176]

[106.6         -1.47692308  93.98461538]

[haughty mountain]

you have rounded the intermediate results

[jovial pilot]

Ouhh damn, ye that has a huge impact

Gonna change it to fractuales

[haughty mountain]

!e

print(18.86666666*4173 - 3.2*62916 + 5.53333333*22176)
print(18.87*4173 - 3.2*62916 + 5.53*22176)

[halcyon plank]

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

001 | 106.59989825998491
002 | 46.58999999999651

[haughty mountain]

it matters a lot because there are large numbers cancelling to form a small result

[jovial pilot]

Yes thx a lot

[verbal agate]

Given a positive integer n, write a function that returns the number of
set bits
in its binary representation (also known as the Hamming weight).

Example 1:

Input: n = 11

Output: 3

Explanation:

The input binary string 1011 has a total of three set bits.

Example 2:

Input: n = 128

Output: 1

Explanation:

The input binary string 10000000 has a total of one set bit.

Example 3:

Input: n = 2147483645

Output: 30

Explanation:

The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

Constraints:

1 <= n <= 231 - 1

Follow up: If this function is called many times, how would you optimize it?

class Solution(object):
    def hammingWeight(self, n):
        count_one = 0

        while n > 0: 
            if n % 2 == 1:
                count_one += 1
            n = n // 2  

        return count_one

please suggest me other possible way to solve it

[meager rivet]

Hello chat
There's money on the line and I need some help.

Here's the question
Two very big integers
As big as the mind can imagine
You're supposed to take 2 such inputs and add them together.
Since there is a limit to the number that can be represented while coding, how can we overcome that?

[hollow monolith]

the bin() constructor returns the binary representation of the integer.

x= str(bin(input))
return len([item for item in x if item == “1”])

90% confident this works. But haven’t tested

[verbal agate]

only this much needed @hollow monolith
thank you for providing this method 🙂

[half wadi]

You can also do x.bit_count()

[verbal agate]

thanks

[half wadi]

Ofc

[finite pond]

does anyone have good introductory books on algorthimns

[charred kayak]

why are algos and data structs important?

[haughty mountain]

because we want software that is efficient and fast

[modern gulch]

And, it's good practice for the harder stuff that comes later.

[charred kayak]

like do i need it early on my journey

[modern gulch]

Depends where you're going, but: if you want to be a SWE, then yes, you'll learn the standard Uni level DSA at some point.

[charred kayak]

SWE?

[modern gulch]

But learn it in Uni. No need to learn before.

[modern gulch]

Software engineer

[charred kayak]

i am not in computer science

can i learn it

[modern gulch]

Ask in #career-advice and share more info, hard to give advice without knowing where you're at

[charred kayak]

you said to learn it in a uni

i am not in a uni

[modern gulch]

So why do you want to learn it?

[charred kayak]

to work in tech

[modern gulch]

Ofc you can learn anything you want.

[charred kayak]

oooh so you mean that i dont need it early on

[modern gulch]

DSA isn't going to, by itself, get you a job in tech

[charred kayak]

yeah it is a componant

of many componants

[modern gulch]

It's just one of many things CS majors learn, and something SWEs should be familiar with. Yes.

[charred kayak]

thank you

[lapis yarrow]

Finding all Articulation points is easy

[grand socket]

bruh how do ii end up doiing so bad on the leetcode problem number 1

[atomic cypress]

Hi dears

I am glad to participate to this discord group

I would like your opinion or help about an issue in my piece of code regarding the datetime and timedelta

n_months_ago = datetime.now() - timedelta(days=90)
yy_months_ago = n_months_ago.strftime('%Y/%m')
print(f"Deleting files for {yy_months_ago}")
print(' ')

I would like to remove S3 bucket files older than 90 days

[modern gulch]

Open a help thread plz: #❓｜how-to-get-help

[half owl]

how do i prove T(n)=Theta(n)?

[vocal gorge]

I use tqdm.contrib.concurrent a lot and I'm driven a bit insane by its bad predictions of estimated time until completion. Anyone knows of what the "correct" way to do it is?

As in, suppose I have N tasks, and they are approximately equal (they take either literally the same time to complete, or, as a more realistic problem, at least are samples from the same normal-ish distribution), and we do them all by distributing them between M parallel workers. We log the times at which each task gets submitted and completed. From these times, what's the right way to calculate the ETA?
Naive solution is remaining_tasks/M * mean(task_completion_times-task_submission_times); I'm wondering if there's better ones. Does anyone know if there's research on this? I can't seem to find any studies; probably I'm not thinking of the right keywords.

[vague maple]

!e

import java.util.HashMap;

public class TrieNode {
    private boolean endOfWord;
    private HashMap<Character, TrieNode> childNodeMap;

    public TrieNode() {
        endOfWord = false;
        childNodeMap = new HashMap<>();
    }

    public boolean isEndOfWord() {
        return endOfWord;
    }

    public void setEndOfWordStatus(boolean endOfWord) {
        this.endOfWord = endOfWord;
    }

    public void addCharacter(Character letter, boolean endOfWord) {
        if (childNodeMap.containsKey(letter)) {
            return;
        }
        else {
            childNodeMap.put(letter, new TrieNode());
            childNodeMap.get(letter).endOfWord = endOfWord;
        }
    }

    public boolean containsChildNode(Character letter) {
        return childNodeMap.containsKey(letter);
    }

    public TrieNode traverseToChildNode(Character letter) {
        return childNodeMap.get(letter);
    }

    public boolean isEmpty() {
        return childNodeMap.size() == 0;
    }

    public void clear() {
        childNodeMap.clear();
    }
}

[halcyon plank]

:x: Your 3.12 eval job has completed with return code 1.

001 |   File "/home/main.py", line 3
002 |     public class TrieNode {
003 |            ^^^^^
004 | SyntaxError: invalid syntax

[vague maple]

!e help

[halcyon plank]

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

[No output]

[vague maple]

!e java

import java.util.HashMap;

public class TrieNode {
    private boolean endOfWord;
    private HashMap<Character, TrieNode> childNodeMap;

    public TrieNode() {
        endOfWord = false;
        childNodeMap = new HashMap<>();
    }

    public boolean isEndOfWord() {
        return endOfWord;
    }

    public void setEndOfWordStatus(boolean endOfWord) {
        this.endOfWord = endOfWord;
    }

    public void addCharacter(Character letter, boolean endOfWord) {
        if (childNodeMap.containsKey(letter)) {
            return;
        }
        else {
            childNodeMap.put(letter, new TrieNode());
            childNodeMap.get(letter).endOfWord = endOfWord;
        }
    }

    public boolean containsChildNode(Character letter) {
        return childNodeMap.containsKey(letter);
    }

    public TrieNode traverseToChildNode(Character letter) {
        return childNodeMap.get(letter);
    }

    public boolean isEmpty() {
        return childNodeMap.size() == 0;
    }

    public void clear() {
        childNodeMap.clear();
    }
}

[halcyon plank]

:x: Your 3.12 eval job has completed with return code 1.

001 |   File "/home/main.py", line 3
002 |     public class TrieNode {
003 |            ^^^^^
004 | SyntaxError: invalid syntax

[stable jacinth]

The eval command only runs python code

[vague maple]

oh

[stable jacinth]

Also, please use #bot-commands for bot commands

[vague maple]

oh ok

sorry

i saw someone else use it here so i thought it was fine as long as it's related to dsa

i'll use it in bot commands next time

[haughty mountain]

a sledgehammer approach would be to just use
https://en.wikipedia.org/wiki/Akra–Bazzi_method

[haughty mountain]

A slightly (but not very) hand-wavy argument: clearly it's Ω(n) given that we have an Θ(n) term.

Let's put a concrete bound for the linear term, it's bounded by d*n for some constant d

Assume T(n) = cn, then

T(n) = c n/9 + c 13n/18 + d n
     = (17c/18 + d)n
```so if we can pick `c` such that  `17c/18 + d ≤ c` we have shown the upper bound O(n) as well. Can we do that?

17c/18 + d ≤ c
d ≤ c/18
c ≥ 18d

[vague maple]

what do you use for non divide and conquer (it's called sequential right)

i know masters theorem covers all but is more tedious

[haughty mountain]

master theorem doesn't cover your case

[haughty mountain]

I mean, just count stuff

[half plume]

Who can explain about Suffix Tree algorithm to me?

[haughty mountain]

it's not an easy algorithm

[cedar mauve]

who can code me a thing saying wanna be my valentine and theres a yes and no button but if you press no the yes button gets bigger

and the no button says please

[tribal vine]

I'm sure you could figure that out on your own. Why not give it a try and post in #1035199133436354600 if you have trouble?

Also this question is better suited for #python-discussion

[vague maple]

insane preparation lmao

[cedar mauve]

bro help

what if she says no tho cuz i

asked without nothing

just

will you be my valentine

but i deleted it

can you make it

[vague maple]

i don't know how

asking people to make it is insane lol

i feel like if you're into full stack then this would be good practice to try on your own

and you could always ask copilot to make this for you

[rare laurel]

this is a purely frontend task

[vague maple]

oh

makes sense

oh cause you can do it all with js

[cedar mauve]

idek how to code

[vague maple]

tell me you're an anomaly here without telling me you're an anomaly

nah but seriously though not knowing doesn't mean you should ask others to do it for you

[bronze nexus]

leetcode 621*: Task scheduler sucks😣

[ocean veldt]

Ask the AI to do it and be as specific as possible

[haughty mountain]

621?

it looks super greedy

[ocean veldt]

Respectfully no one is going to waste time for your sake

[haughty mountain]

just keep picking the task with the largest remaining count that can be picked

[bronze nexus]

yeah 621*

[haughty mountain]

which screams "use a heap/priority queue"

probably together with a queue to handle the constraint that you need to wait n steps before re-using stuff

[bronze nexus]

Yeah, but inserting and popping from a queue seems tough

[cedar mauve]

she said yes

[vague maple]

nice

see that's what happens when you do these kinds of things yourself

it becomes personal to you

and i'm sure you learned from the experience

[worldly linden]

Hello guys, I recently learnt about the hash table and graph data structure. I did understand roughly how both works. The problem is I don't understand the use cases of graphs, where they are useful and why. How does it differ from hash table. Can someone explain please. I know graphs have kind of 2 traversal algorithm, Breadth-first search and Depth-first search, I know how they work but I don't really understand how they are useful in real world scenarios. (please tag me for any response)

[haughty mountain]

a lot of real world stuff can be modeled as graph problems, and we have good theoretical foundations on how to work with graphs

[worldly linden]

yeah, just read that graphs allows us to model things and allows us to ask question about how these things are connected. For example, in a social networking site, if A and B are friends and C is a friend of B, using graphs, we can ask question like "are A and C related?"... using an appriopriate algorithm we can find in fact that A and C are related (please confirm if what I said is correct or if their is anything that can be added pls... would really appreciate)

[haughty mountain]

you can model stuff like social connections as graphs yes

but it's applicable to loads of stuff

[agile sundial]

graph theory is super important for analyzing networks

[worldly linden]

yep I see

[haughty mountain]

or for stuff like pathfinding

navigation

it's a very general modeling framework

[junior oar]

Anyone do Qs on leet or gfg?

[lean walrus]

or dependency resolution

[haughty mountain]

https://tenor.com/view/dags-yda-like-dags-mickey-oniel-brad-pitt-snatch-do-you-like-dogs-gif-21722450

[inland pond]

can someone explain to me what is big oh, theta ,omega ? I tried searching on google but im more confused

[haughty mountain]

basically the asymptotic versions of ≤, = and ≥

so f(x) = O(g(x)) basically means f(x) "≤" g(x)

what matters for asymptotics is what happens when the input grows large, in particular what happens to f(x)/g(x) as x grows large

if it → 0 then f(x) "<" g(x)
if it → ∞ then f(x) ">" g(x)
if it → some positive constant, then they are basically equal as far as the asymptotics go

in this sense O means we approach 0 or a constant
Ω means we approach a constant or ∞

[vague maple]

dude hash table and graphs are completely different

graphs are an entire field of study

huge part of discrete math and a very important data structure

and graphs are nonlinear, while hash tables are a way of setting up dictionaries/maps which are a linear data structure

[inland pond]

Do you have any article or videos about this?

i still dont know your explanation

[haughty mountain]

as an example, if you look at x - y, can you tell which one of x and y is bigger/smaller?

[blazing basalt]

hey guys i just started to solving problems on leetcode and I don't understand why i'm getting this error SyntaxError: invalid syntax
^
def isPalindrome(self, x: int) -> bool:
Line 2 (Solution.py)

here is my code:
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0:
return False
x = str(x)
if x == x[::-1]:
return True
return False
solution = Solution()
print(solution.isPalindrome(121))

[rare laurel]

i think you're using python as the language rather than python3?

[blazing basalt]

ohh yes, thanks

[opal oriole]

https://en.wikipedia.org/wiki/Wolf,_goat_and_cabbage_problem

You can solve this by representing each possible world state (where everything is, imagine a board state in chess) as a vertex in a graph. There is an edge between vertices if there is a move (the edge is labelled with the move) transforming the state from one to the other. So now you have a graph. Now remove all edges that are invalid moves and delete all vertices that are failure states. Now run BFS or DFS to find a path from start state to end goal state. This path's edges are the series of moves needed to solve the puzzle (there is more than one valid solution (which shows up as multiple paths from start to finish in the graph)).

(lower case means on start side of river, upper case means on goal side of river)

(f = fox, g = goose, b = beans)

[urban kiln]

currently studying stochastic analysis and was wondering whether the easiest way to implement a wiener process/brownian motion is to use the fact that it is the limit of a scaled random walk as n goes to infinity?

prolly not the most efficient way but as you can see it isnt that fast

i assume that in practice youd need your timesteps to be smaller (yeah nvm you wouldnt use python/ dumb question)

i just used google and it answered my question

[teal lotus]

hey guys .. recently i'm having some issues with downloading 'deepface' library on VS code
i tried every i know but still not working .. i would appreciate ur help

[half wadi]

Run powershell Set-ExecutionPolicy unrestricted then run the activate script again then run pip and python and whatever you need

[haughty mountain]

haha, wiener

[vague maple]

there's no way, is that the actual name

[inland pond]

Theyre variables and i dont know their value but i couldve tell

The only thing that explains recurrence relation is from abdul bari on youtube but he literally has a thick accent and i cant understand anything from him

[sly spindle]

I mean there are infinite ways of doing this, literally

Depends on what idea ur trying to exploit

You could literally write a function that flips a coin repeatedly and samples from the coin flipping and then add that to a signum function and boom you have simulated a random walk which is indeed a Weiner process

[narrow mica]

for this snippet, since each random event is independent of others, you can easily convert this into numpy

[woven drift]

fuck you

IndentationError: unindent does not match any outer indentation level" what does it mean

[lean walrus]

exactly that

your indentations level are not right

look around the error location

[wild temple]

I think industry is hungry for talent in algorithm design. It's a very important aspect of codebases. However, people working on a personal portfolio project where algorithm design is a big part of it are rare. I could say the same thing about tool development.

In industry, algorithm design is not about making the next Big Breakthrough in computer science. Its more about solving niche problems, knowing what approximations can be gotten away with, etc. But it's still fun and interesting and a needed skill.

Anyone here diving deep into this subfield?

[strange gorge]

Hi there, I am learning to implement a queue with 2 stacks and wondering why in the solution where enqueue is more costly (I.e. performs the reverse), why front(n) would still be O(n)? Wouldn’t it be O(1) if the elements were already reversed when they were enqueued?

[tight cedar]

it is not reversed because you are resuming the order after reversing in every enqueue (step 3)

so actually reversed twice

you can remove step 3 by just checking (or popping) from stack 2 before looking at stack 1

[carmine onyx]

Set-ExecutionPolicy unrestricted

[light river]

Having a little problem here: I'm using argparse to parse CLI args, and I created this argument:

parser.add_argument("-c", "--check", type=str, const='.', nargs='?', help="list files to include in archive without packing them.")

So far so good, but when I run my program with -h, the help message looks like this:

-c [CHECK], --check [CHECK]
                        list files to include in archive without packing them.

Is there a way to change the part where it says [CHECK]? I'd like to make it more specific about the parameter being a directory path, and use something like [path] instead.

[fiery cosmos]

hmmm very peculiar algos and data structs question if I do say so myself...

[light river]

I had no idea where to put it...

[narrow mica]

metavar?

[light river]

oh I totally overlooked it!

that's exactly it, thank you

[haughty mountain]

It doesn't seem too bad

reverse engineering a stack based language sounds like fun

I have code handling the first 6 programs, and it's now just kinda about extending things

[half owl]

do you say Quicksort is O(nlogn) "expected" TC, or O(nlogn) "average" TC?

[lean walrus]

i dont think there is a difference

[sly spindle]

Maybe in certain contexts expected could be interpreted as theoretically proven lower bound if the code is written and optimized properly whereas average would be what it actually ran at based an individuals own implementation

Plus like overheads start to come into play constructors and destructors CPU core utilization parallelization data structure usage etc etc

[haughty mountain]

if it's the statistical meaning of it then it's the same, yeah

[haughty mountain]

these don't affect the time complexity

[sly spindle]

Yes they all do. Negligible in small scale code, in massive code yes, they all matter

[haughty mountain]

how do they matter for the time complexity?

time complexity is all about asymptotic behavior

are you saying these things will affect things more than just a constant factor?

[sly spindle]

Every time you stick anything on the stack it contributes to time complexity

And u clearly saw in nothing I typed I said more* or less*. I quantified nothing

[haughty mountain]

you suggesting it changes the time complexity implies that it slows things down with more than a constant factor

the time complexity only cares about asymptotic growth

even if something is a constant 100000x slower across all inputs, the time complexity is the same

[sly spindle]

I run algorithms that process quadrillions of data points so yes every single line of code I type matters and my point was asymptotically which quadrillions of points affect then yes they all come into play

[haughty mountain]

what is the asymptotic slowdown you suggest exists of constructors and destructors?

you imply there is a ω(1) slowdown

[fiery cosmos]

there's not

[atomic elm]

any yt vid suggestions for learning naive bayes classifier and implementing it

[mint grove]

its really confusing me to learn data structures, does anyone have a good blueprint to learn

[summer fossil]

neetcode.io

[buoyant wolf]

I mean are you in college or uni?

also C is a better language to learn DSA in cause its much more basic

[mint grove]

Well I'm in uni but I went directly to it with a foundation programme without Als

[haughty mountain]

is basic better though?

having to constantly think about memory allocation seems quite unfun

[half owl]

I don't it, dsa is done with pseudocode unless it's implemention hw no?

[shell delta]

How did anyone start with leetcode, because each problem is different and I have to think really hard just to give up and look at solutions, even after having 3 works of experience. Anyone facing the same problem? How can I make myself better?

[hearty bronze]

its your way of problem solving. i wouldnt look at solutions until you're stuck and have no other option , i would look at discussion posts and write notes on the subject to gain a better understanding of it

[haughty mountain]

learning algorithms but never implementing things is a bit like someone studying cooking without cooking 🥴

I guess it's not uncommon in more theoretical cs, but it just feels a bit sad

[mint jewel]

I've done implementation work for some CS research before. Even found a bug. But ideally you'll at least have a reference impl

[analog hamlet]

@haughty mountain did you see the new hash table findings

https://www.quantamagazine.org/undergraduate-upends-a-40-year-old-data-science-conjecture-20250210/

so i never knew about hackerrank until now, i guess its hackerrank and leetcode both now..

for studying purpose

[fiery cosmos]

a lot of companies do assessment on hackerrank

[analog hamlet]

yeah im just finding this

IBM does

[fiery cosmos]

traumatic

[undone geode]

Is there a better DSA practice set than "Blind75" ?

[summer fossil]

https://takeuforward.org/strivers-a2z-dsa-course/strivers-a2z-dsa-course-sheet-2

[undone geode]

thanks

[modern gulch]

Also see Pins, first pin is a great set

[split garden]

Is there a good (but still fast) way to "address" certain sections of a numpy array? This is getting too unwieldy, I have an enum that handles the index name currenly but even that is getting to be a bit much. It does have to be a numpy array since it gets passed to a shader.

(Not looking for code review I don't want to post the code to some external website, just looking for a general approach)

[narrow mica]

!rule paid

[halcyon plank]

Rules

9. Do not offer or ask for paid work of any kind.

[empty yarrow]

pov: mutable objects

[haughty mountain]

🥴

[austere sparrow]

https://leetcode.com/problems/separate-squares-i/
I don't understand why the suggested solution is ||binary search||... does that suggest that the problem is solvable in O(log n) somehow? It is definitely solvable in O(n) if you use ||radix sort||

or maybe they're suggesting an O(n logn) solution?

[jolly mortar]

its O(n * log(size of search space))

[haughty mountain]

BSTA

(i.e. binary search the answer)

[austere sparrow]

oh right

i'm a dummy

But it's still a surprising suggestion to me. I had a much simpler solution

[austere sparrow]

Take this input for example: four squares with a side of about a billion. If you binary-search the breaking point from 0 to 2 billion, you're gonna iterate over those squares over and over til the cows come home

whereas if you search for the threshold more procedurally, any input with four squares will be solved very fast. You can even use fractions and report the exact breaking point

[haughty mountain]

you won't iterate over them that many times

to be within 1e-5 where the numbers are up to 1e9 large is ~log2(1e14) which is like 47

yes, you can get away with less by being a bit more clever, but there is some charm to the dumber way

[austere sparrow]

Yeah it's true

this was kind of my thought process, I imagined the "area below h" as a piecewise function constructed of linear sements

[haughty mountain]

in the end that's what it is

the key for the bs solution is that evaluating that for an arbitrary y is easy

[austere sparrow]

Yeah, it might be cooler if the shapes were circles or something like that

[haughty mountain]

the same bs solution works, it's just a tad more annoying to evaluate

[austere sparrow]

anyway. i like this problem, it's interesting

not something i often say about leetcode problems

[haughty mountain]

this is a fairly common pattern

if you have something that is monotonous, and you can evaluate it relatively cheaply, the problem is essentially solved

[slender copper]

Chatgpt

[fresh fjord]

No idea if this is the place for this, but I'm going to pull my hair out if I keep trying to just brute-force my brain through it. Feel free to tell me I'm in the wrong chat or the wrong server or whatever's appropriate. I'm wondering if anyone has ever encountered data stored this way or might have a lead on where I can get more information. Worst comes to worst, it might be an interesting puzzle.

I'm digging through an old game and have a file in the root of an unpacked archive of assets that's structured as follows:

4-byte int (num_extensions)
[num_extensions-length array of NUL-terminated file extensions]
4-byte int (num_files)
[num_files-length array of NUL-terminated file names] 
4-byte int (num_associations)
[num_associations-length array of 4-byte int + 1-byte char]
4-byte int (num_mysteries)
num_mysteries-length array of the following:
  4-byte int (Mystery Index)
  4-byte int (Mystery Count)
  Mystery Count-length array of increasing 4-byte ints (Mystery Array)
EOF

I know that the "associations" data structure is an index of files and the extensions that go with them. Using it that way produces a list of every file in the archive with the correct extension. I strongly suspect that my processing of the "mystery" arrays is correct - the value of Mystery Index over loops increases from 0 to num_files, though it does skip, and the values in the Mystery Arrays are always ordered low to high, no exceptions.

I assume that the Mystery Arrays are some kind of extra data for certain files. num_mysteries is 4,026 and num_files is 17,303, so it maps to just under 1/4 of the files in the list if we go with that assumption. What I've done is taken the Mystery Index and used it to map each Mystery Array to the file that matches its index.

The problem is I have no idea what the Mystery Arrays are for. They're arrays of 1 to 40 increasing integers between 9 and 4,222,223. There are only 4,872 unique values used. There seems to be no rhyme or reason to which files, roots, or directories have them. Arrays are not unique to a single file - multiple different files can have identical arrays. Four different files share [9729, 50436, 64257, 99841, 101379, 108551, 125697, 211201, 378883, 961793, 1678081, 1708033, 3073800, 3188227, 3347210, 3416838]Three of them are different LODs of the same model (promising!) and the fourth is a particle effect from a completely unrelated directory (never mind).

Any leads? Does this look like anything to anyone who knows data structures better than I do? Thanks for reading and sorry if I'm wasting people's time.

[vocal gorge]

I'd try comparing the file's mystery values to the file's size, to see whether it's possible that those are offsets into the file

[tropic pelican]

https://youtu.be/mSGQr9b6dag

[hard wyvern]

What general techniques or modules or whatever, I can do to make my code faster? Ive seen some posts saying trying to utilise the 'itertools' module as a way to make my code run faster. Are there any specific sorting algorithms I should use when using python and databases?

[vocal gorge]

What general techniques or modules or whatever, I can do to make my code faster?
Profile your code to see what's taking the time, then rewrite those parts to be faster. There isn't really a general technique; I use numpy and numba a lot for numerical computations but they aren't for everything, etc.

utilise the 'itertools' module as a way to make my code run faster
itertools is well-optimized but there are few circumstances in which it'll speed things up, since typically you consume those iterators with normal python code and the latter will be the bottleneck.

Are there any specific sorting algorithms I should use when using python and databases?
If you're looking for performance you shouldn't be implementing any sorting algorithms yourself - just let your database or python's list.sort handle it.

[stable flower]

hello, I am looking for a partner to learn DSA with me using python and on intermediate level

[haughty mountain]

the solution to performance in python is writing less python code 😌

[halcyon ridge]

How can I develop problem-solving skills in programming? When I try to solve a problem it takes a lot of time and i can't solve it even with the basic level problems. I want to improve my coding skill so how can I do it ??

[haughty mountain]

I don't think there is a good answer other than just "practice"

do stuff

get used to programming stuff

[halcyon ridge]

like what for example?

[haughty mountain]

just whatever

small tasks on places like codewars might be good practice

[halcyon ridge]

okay thanks Bro

[tacit olive]

Hello there

[stray fractal]

how would i go about implementing the fundamental counting principle (without repetition) for a list of sets?

[mint jewel]

Is it distinct from itertools.product?

[stray fractal]

yup

for example using the sets {1, 2, ..., 9}, {0, 1, ..., 9}, {0, 2, 4, 6, 8} gives a result like 9*8*1 (0 case in third set) + 8*8*4 (2 to 8 case in third set) = 328

[hazy sigil]

u know how to make fibonacci numbers and print the prime number out?

ive been trying the whole day :))

[mint jewel]

so {0,1}, {1,2}, {2,3}, {3,4}, {4,5} would have 1 * 1 * 1 * 1 * 2 (0 in first set) + 1 * 1 * 1 * 1 * 1 (1 in first set) = 3?

@stray fractal^

[hazy sigil]

so there would be 5 variables?

:))) im sorry bro, im very new to this stuff

[stray fractal]

it goes something like that, yup

[hazy sigil]

thanks, lemme try

[mint jewel]

do you know how to do those separataly -- find prime numbers, and produce fib numbers?

[hazy sigil]

i hv produced fib nums, but it just ignore the other commands for the prime numbers

[mint jewel]

do I understand correctly that your task is to print out fibonnaci numbers that are also primes?

[hazy sigil]

yep

[mint jewel]

in that case, can you, completely separately, make an is_prime function, that just returns True or False depending on whether the number is prime?

[hazy sigil]

never heard of that function, but ill look it up :))))))

[mint jewel]

it doesn't exist yet, you would have to make it

[hazy sigil]

oh

ok

wait how do u do that?

i tried to loop a number from 2 to the number that i need to check and % it, if it != 0 then ill print it, but that doesnt work, the numbers just straight up ignore all of that and print out the normal fib

[mint jewel]

could you show code, that seems like a bug in your implementation

[hazy sigil]

ok

hold on

[fiery forge]

Is this a correct queue?

queue = [None for _ in range(10)]
rear = -1
front = 0
height = 10
items = 0

def enqueue(item):
    global queue, rear, items
    if items == height:
        print('Already full')
    else:
        if rear == height - 1:
            rear = 0
        else:
            rear += 1
        queue[rear] = item
        items += 1

def dequeue():
    global queue, front, items
    if items == 0:
        print('Empty')
    else:
        print(queue[front])
        queue[front] = None
        if front == height - 1:
            front = 0
        else:
            front += 1
        items -= 1

[hazy sigil]

YOOO

[hazy sigil]

@mint jewel u gud bro?

is there anything wrong?

[mint jewel]

@hazy sigil You need to check that all of the modulos are nonzero, as you've written just one is enough to print the number

[hazy sigil]

nonzero ?

whats that mean?

[rare laurel]

not zero

[hazy sigil]

so like make it != 0 ?

[rare laurel]

you already have that, you just stop as soon as you have one non-zero modulus, when it should be all of them

[hazy sigil]

so how do i keep checking nonzero modulus for all of them?

[rare laurel]

by not breaking on a non-zero modulus?

[hazy sigil]

well when i try it, it just repeated the result like a gazillion times

and the results r still not prime yet

[rare laurel]

yes, because you should only print if all of the moduluses are not 0
if you just removed the break, you're now printing the number for each non-divisor

you could break and say that the number is not prime when you get a 0 modulus, but a not 0 one means you have to continue checking

[hazy sigil]

so check for nonzero modulus after the break?

:)))

[rare laurel]

prime = True
for divisor in range(2, number):
  if number % divisor == 0:
    prime = False
    break

does this make sense?

[hazy sigil]

oh ok

lemme put dat in

hold on

:))) now it only produce 1 result

which is number 2

:))))) lmao, i think im losin my mind already

wait lemme fix that again

[rare laurel]

well, you only set it to True once

you should start with it being True for each number you check for being prime

the code duplication and not using functions makes this.. very messy

[hazy sigil]

yea

im kinda new so therer a lot of functs that i havent known

[rare laurel]

its not functions you dont know, you can define your own functions

[rare laurel]

how are you learning python?

[hazy sigil]

so its just how i think right?

i just started from a couple online guide :)))))0

[fiery cosmos]

Is it worth learning dsa with python?

[undone geode]

in general, DSA is worth the time it takes

what language you use shouldn't matter.

Some CS programs purposefully teach you DSA using old and obsolete languages for this reason

Now, having said that, it might be easier to do a DSA problem during an interview using python vs C++ or Perl or whatever