algos-and-data-structs

[stray fractal]

maybe not infinity

[haughty mountain]

not in the way that matters

exactness and precise divisibility is what you need for more fun range operations

ints and fractions have that

[stray fractal]

that's the point of giving Fraction() instead of floats

anyways i still don't know why that doesn't work

[haughty mountain]

if you never involve floats then fine

[stray fractal]

they're only involved if the user wants them involved

[haughty mountain]

in which case most things will just plain break

[stray fractal]

but i'm pretty much gonna be the only one using it anyway

now why does n * k / p become negative

[haughty mountain]

it's not even guaranteed to exist for reals, if you accept working with inexactness of floats why not just solve the equation and them check if it looks like a valid point

and then for exact types just do diophantine equations as usual, as you mention

[stray fractal]

using Fraction() works differently from using floats

but even then it doesn't produce a correct result

[eager berry]

hi, i would like to ask if anyone has recommendations for websites to learn basic algorithms (everything less complex than or equally complex as dynamic programming). i've learnt the basics of python coding already. thanks for the advice beforehand

[narrow mica]

if you don't mind reading cpp

[stray fractal]

oh now it doesn't work if i make them integers

and produces different results if i switch them around

[shadow glen]

guys i need help, i'm trying to substitute \n here to \n, but instead it's giving separation between the words:

def exeecho(args):
    if len(args) == 1:
        y = args
        if isinstance(y, list):
            while True:
                print(f"{y = }")
                if len(y) > 1:
                    piv = ""
                    for z in y:
                        piv = piv + (
                            z
                            if z == y[-1] and isinstance(z, str)
                            else (
                                f"{z[1]}"
                                if z == y[-1]
                                else f" {z}" if isinstance(z, str) else f" {z[1]}"
                            )
                        )
                    y = piv
                if isinstance(y, str) or isinstance(y, float):
                    break
                y = y[0]
        y.replace("\\n", "\n")
        print(f"{y = }")
        pages = discord.Embed(description=y)
    else:
        chapters = list()
        for i in args:
            y = i
            if isinstance(y, list):
                while True:
                    print(f"{y = }")
                    if len(y) > 1:
                        piv = ""
                        for z in y:
                            piv = piv + (
                                z
                                if z == y[-1] and isinstance(z, str)
                                else (
                                    f"{z[1]}"
                                    if z == y[-1]
                                    else f" {z}" if isinstance(z, str) else f" {z[1]}"
                                )
                            )
                        y = piv
                    if isinstance(y, str) or isinstance(y, float):
                        break
                    y = y[0]
            y.replace("\\n", "\n")
            embed = discord.Embed(description=y)
            chapters.append(embed)
        pages = Paginator(chapters)
    return pages

here was suppose to substitute \n to \n

and not convert FOR into F O R

[minor pasture]

Is following code:

from article import Article
from scrapReason import ScrapReason
from dataclasses import dataclass

@dataclass
class Job:
    job_id: str
    article: Article

equal to this code?:

from article import Article
from scrapReason import ScrapReason


class Job:
    def __init__(self, job_id: str, article: Article):
        self.job_id = job_id
        self.article = article

[slender sandal]

Yes and more

It also defines __repr__ for convenience

[solemn moss]

How to find all ks where x // k changes value faster than O(n)?

like this

def f(x):
    prev = -1
    res = []
    for k in range(1, x + 1):
        if x // k != prev:
            res.append(k)
            prev = x // k
    return res

[haughty mountain]

how many possible values of x//k can there be?

given one such value, can you find the first k with that value?

[solemn moss]

Should be something about sqrt(x)

With binary search easily.. but should be a straight formula i guess

[haughty mountain]

ok, there's your plan then

[lean walrus]

>>> n = 100; n2=n**0.5
>>> f(n)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 17, 21, 26, 34, 51]
>>> [*range(1,int(n**0.5)+1)] + [n // x + 1 for x in range(2, int(n**0.5)+1)[::-1]]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 17, 21, 26, 34, 51]
``` something like this

this is O(n^0.5)

[regal spoke]

The trick is that for small k (k<=sqrt(x)), adding 1 to k will always change the value of x//k. The formal statement is that if k * (k + 1) <= n, then n//k != n//(k+1)

As for large k (k>=sqrt(x)), x//k can take at most sqrt(x) values.

If x is a square then the values are precisely 1,...,sqrt(x)

In general the values are 1,..., x//ceil(sqrt(x))

[haughty mountain]

missing a sqrt?

[regal spoke]

Ah ye

Fixed

[regal spoke]

It is easy to get off by 1 errors if you aren't careful

!e

f1 = lambda n: [*range(1,int(n**0.5)+1)] + [n // x + 1 for x in range(2, int(n**0.5)+1)[::-1]]
def f2(x):
    prev = -1
    res = []
    for k in range(1, x + 1):
        if x // k != prev:
            res.append(k)
            prev = x // k
    return res
print(f1(7))
print(f2(7))

[halcyon plank]

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

001 | [1, 2, 4]
002 | [1, 2, 3, 4]

[stiff quartz]

The editorial of this codeforces problem (https://codeforces.com/contest/1950/problem/F) mentions a logarithmic solution (or even better), could anyone help me understand how that's possible? My solution is to greedily build the tree which takes O(a+b+c) time and I can't figure out how to make it better (it gets AC but if the constraints were tougher it wouldn't and there would still be a way to make it work but they don't seem to explain how to get to that complexity)

[regal spoke]

I don't know where you'd get log from

O(1) should be possible

I think the idea is that the optimal solution is to first build a balanced binary tree out of the a nodes

After that add in the b nodes greedily

[stiff quartz]

A balanced?

Balanced tree?

[regal spoke]

yes

edited

[stiff quartz]

This is kinda what I did except I did it explicitly by building the tree which is why it’s linear

So you’d just math out what the height is

[regal spoke]

yes

[stiff quartz]

Yeh probably would be O(1) then - I’ll check if I can find it tomorrow

[tall lance]

if i had an array deque, where i have two variables start(length - 1) and end(0), and i had a condition for addend to check if size == 0(if true, change the value without incrementing, if not, increment end first then change the value), how would i prevent the first value being null if i did addstart (size will = 1, condition for size == 0 will lead to a null value at the start)

[solemn moss]

F in O(1): https://codeforces.com/contest/1950/submission/253827308 (not mine)

[stiff quartz]

Maybe it’s for the height of the balanced binary tree out of the a nodes

While sum < a

sum+=2^i

[regal spoke]

Just use bit_length and nothing will run in log time

[stiff quartz]

Ah fair

[stiff quartz]

actually
isn't bit_length theoretically log(a)? since it needs to count the bits ...

[regal spoke]

I would say no. But it depends on how you see it

In theory everything is log, even adding two numbers

[stiff quartz]

yeah if we go down that rabbit hole indeed

tbf O(log()) seems instantaneous

[regal spoke]

I view it like bit_length is O(1)

I wouldn't be surprised if it is true O(1). But that depends on how big integers are stored in Python

Btw converting the input into Python ints is more expensive than .bit_length

[stiff quartz]

doing int(input())?

[regal spoke]

Yes

[stiff quartz]

fair

[sterile oak]

to find the lonely integer in an array I wrote the following code

for i in range(0,len(a)):
lonely=0
for j in range(i,len(a)):
if a[i]==a[j] and i!=j:
lonely+=1
if lonely==0:
print(a[i])
break

[shut breach]

did you have a question about it?

[sterile oak]

does the lonely==0 condition execute after each iteration in j or after the whole j loop has ended

i know this is a brute approach but I can't seem to figure out why it doesn

*doesn't work

[shut breach]

only after the j-loop has ended

[shut breach]

can you explain your approach to solving the problem in english?

[sterile oak]

basically I ran multiple loops on the same array comparing the elements and keeping a count of that element in the lonely variable if the overall count after the second loop has ended is 0 that means it's a lonely integer otherwise no

i figured it out

I was taking the wrong range in the second loop

[regal spoke]

Another way you could have coded this is

for a in A:
  lonely = 0
  for b in A:
    lonely += a == b
  if lonely == 1:
    print(a)
    break

[haughty mountain]

for a in A:
  if sum(a == b for b in A) == 1:
    print(a)
    break

print(next(a for a in A if A.count(a) == 1))

of course, this is a terrible way to do it

very inefficient

[regal spoke]

That one breaks if A = [2, 2], right?

[haughty mountain]

if would

but I'm guessing the task says there is a single one that's lonely

I recall this being a leetcode question

one that's solvable by just a xor sum

I'm thinking of this one, name doesn't exactly match
https://leetcode.com/problems/single-number/

[glossy lintel]

most performant way to sort a singly linked list?

[agile sundial]

merge sort

[vocal gorge]

since sorting will be O(n log n) anyway, it's valid to just collect it into a normal array-backed list, sort, and turn back into a linked one if needed

[agile sundial]

yeah, if it fits

[glossy lintel]

kinda feels cheaty and slow

why should i supply the user with a built in method thats literally easily replicable lines of code while also not having very good performance

lets say for merge sort, then yes i would implement a built in method for the user to use

bc its not that easy to implement

and is faster than what they could have implemented

[narrow mica]

while also not having very good performance
have you tested it?

[glossy lintel]

well i did

but im not sure if its the best solution

or if it could be optimised even further

[outer rain]

you are literally going to spend more traversing the list than sorting it

because linked lists just suck

and modern sorting algorithms don't

[glossy lintel]

ok yes, but i have to implement them

also

[glossy lintel]

so should i supply them with the sort method or leave them make it by themselves?

since u said its more traversing rather than sorting

[outer rain]

well, I assume your list is iterable, so user can use sorted method themselves already (it will just return a normal list)

as for .sort method which sorts list in-place... that kind of kills the purpose of linked list, but you can implement it if you really want to, it won't hurt

the implementation is going to be LinkedList(sorted(list)) anyway

unless you don't write in python and target native, in which case in-place sorting kinda makes some sense: you reorder fields without changing pointers

of course, you can do that in python too if you want to: extract data, sort it, then put it back in the list in a different order

[glossy lintel]

mhm

[outer rain]

not sure if it's going to be much faster, probably will

[glossy lintel]

ok then

so i shouldn't implement the sort method

since its iterable

[glossy lintel]

so i have implemented the singly linked list

now how should i do so in doubly?

the problem is there are gonna be modifications to the code's internal logic

for example

traversing over a singly linked list starts always at the beginning

but in the doubly, since i know the tail it can start from the end to the destination

if the distance ofc is shorter compared to the singly

[jagged iris]

https://paste.pythondiscord.com/ZDWA Can someone take a look?

error at the bottom

[haughty nimbus]

someone know a good beginenrs code?

[mossy finch]

you just need to start by learning the basics

and try changing stuff and if u get any errors try to fix it or get to know why the error happens

that's how i learnt lol

and slowly go into complex stuff

[serene galleon]

how to install PIL for python 3.6 ?

[slender sandal]

pip install pillow

Or do you get any specific error you wish to share with us

[serene galleon]

On cmd ?

This doesn't make sense

[slender sandal]

On whichever terminal you have

And on your activated virtual environment if you use a virtual environment

[serene galleon]

Cmd

Windows

[slender sandal]

Then type there

[serene galleon]

Bro says that the command pip doesn't exist

[slender sandal]

Then you didn't add it to PATH

Try py -m pip install pillow

[glossy lintel]

is this optimised code for rotating a linked list?

    def rotate(self, shift: int = 1):
        # ......
        if shift == 0 or self.__nodes_length == 1:
            return
        shift = shift % self.__nodes_length
        currNode = self.starting_node
        targetNodeHierarchy = SinglyNode(None)
        targetNodePointer = targetNodeHierarchy
        duplicateBeforeNodes = SinglyNode(self.starting_node.data)
        duplicateTarget = duplicateBeforeNodes
        prevDuplicateTarget = duplicateBeforeNodes
        for i in range(self.__nodes_length):
            if i >= self.__nodes_length - shift:
                targetNodePointer.data = currNode.data
                prevTargetPointer = targetNodePointer
                targetNodePointer.point = SinglyNode(None)
                targetNodePointer = targetNodePointer.point
                currNode = currNode.point
                continue
            elif i == self.__nodes_length - shift - 1:
                currNode = currNode.point
                continue
            currNode = currNode.point
            prevDuplicateTarget = duplicateTarget
            duplicateTarget.point = SinglyNode(currNode.data)
            duplicateTarget = duplicateTarget.point
        prevTargetPointer.point = None
        self.starting_node = targetNodeHierarchy
        prevTargetPointer.point = duplicateBeforeNodes
        self.__ending_node = duplicateTarget
        self.__pre_end_node = prevDuplicateTarget

[serene galleon]

thanks !

[serene galleon]

it worked, but python guy still not find it

[void light]

I think this is the right place to ask this but please let me know if I should post it somewhere else:

I have a data structure in JSON that looks something like

[{"groupID0" : {
  "subordinateGroups" : [
    "groupID1",
    "groupID2"
]}},
{"groupID1" : {
  "subordinateGroups" : [
    "groupID3",
    "groupID4"
]}}
...continued```

My question is how is the best way to approach this given the task of getting a random group ID and creating a new JSON object that continually checks recursively until its exhausted all possible paths such that the initial group is the Key and it generates a tree of all subordinate groups and their subordinate groups etc until no subordinate groups are left. 

```py
def findallnestedorgs(inputorg, jsonlookup):
    nestedjson = {}
    for org in jsonlookup[inputorg]["subordinateOrgs"]:
        if is_nested(org, jsonlookup):
            nestedjson[inputorg] = {org : {}}
        else:
            pass

Is where I started with this and I thought about doing a while loop but (and I could be tired and just need some time away from this to see it clearly), I can't wrap my head around the best way to approach this in a way that doesn't get hyper complex or if it recursively calls itself, to pass data to the function I am defining there such that just...makes sense LOL

[narrow mica]

define f(n) as the function that generates the tree where n is the root and the nodes below are the subgroups, then
f(n) = merge_dict( f(sub) for all sub ) where sub is a direct sub group of n
some python flavored pseudocode:

def f(n):
    if n.is_leaf():  #
        return {}    # not really needed
    sub_groups = {}
    for sub in n.sub_groups():
        sub_groups[sub] = f(sub)
    return sub_groups

[mossy spire]

hey i started learning dsa just completed about big O using this https://www.udemy.com/course/data-structures-algorithms-python/?couponCode=IND21PM

it seems fun or is it?

[hasty eagle]

is codeacademy the best app for learning python?

[glossy lintel]

nothing is best in this world

i think its good tho

haven't really tested it since i didn't use any platform to learn

(also ur asking this on DSA channel, if u talk more generally about python then please refer to a other channel)

[modern walrus]

I had this idea of a sorting algorithm. I would need your opinion and advice on this.

import asyncio

async def aa(x):
    await asyncio.sleep(1/(x*100000))
    return x
    
async def main():
    us = np.random.rand(10000)*10000//1 +1
    tt = np.zeros(len(us))
    runners = [aa(i) for i in us]
    i=0
    for completed_task in asyncio.as_completed(runners):
        result = await completed_task
        tt[i] = (result)
        i +=1
    return tt

g = (asyncio.run(main()))

[glossy lintel]

that idea is basically sleep sort

[mint jewel]

this is basically selection sort

[modern walrus]

sleep sort?

[glossy lintel]

https://www.geeksforgeeks.org/sleep-sort-king-laziness-sorting-sleeping/

you divide all of the elements into seperate threads

and you put a sleep timer on them

[modern walrus]

yeah i did the same

[mint jewel]

asyncio will internally call min on the sleep times and wait until the nearest sleep ends

[glossy lintel]

mhm, but this kind of looks like a jumbled mess

this kinda infurates me

[mint jewel]

or does it do a heap, I actually do not remember

[glossy lintel]

i +=1

[modern walrus]

uh i just wrote things as i thought them of

[glossy lintel]

ok

but why is the function so weird to follow

1/(x*100000)

like why

if its all integers the same thing can be made simpler

[modern walrus]

hmm, i was creating random array of 10000 elements, and if i get "1", then i would need to wait 1 second

cause 1/1

but 1/10000 is 0.00001

[glossy lintel]

oh yeh true actually

i have an idea

[modern walrus]

kinda like making it faster

[modern walrus]

I would love to hear that

[mint jewel]

@modern walrusIt is in fact really weirdly elaborate heapsort

[modern walrus]

yeah, but i was just testing the concept, and i thought it would be simple to implement in async

the main concept is, making it sleep and collect the result once the sleep is done

and do it parallely

[mint jewel]

Ye, that mostly makes sense with threads, where you actually have more than one core

[glossy lintel]

import asyncio

async def main():
   l = np.array([1, 5, 3, 2, 9, 6])
   l_store = []
   for i in l:
      sleep = asyncio.sleep(i)
      l_store.append(sleep)
   await asyncio.gather(*l_store) # Hold on

[mint jewel]

in async, you are adding callbacks to a list, which is then heapified and poped from.

[glossy lintel]

l can be changed to be a other array

[modern walrus]

yes, i did that, but as the array grew in 10 powers, list started to make it slower. i implemented another version with only numpy arrays to make it a bit faster

[glossy lintel]

also if i may ask

why sleep sort out of all the bunch of sorting algorithms

[modern walrus]

nah, it was just reinventing the wheel kind of stuff

[glossy lintel]

oh

[modern walrus]

i just came up on it, on my own

instead of making our computers work, why not use the flow of time?

[glossy lintel]

im an idiot

i realised this could be sped up more

[modern walrus]

yeah, gather gives output in the order you gave input in

and, the code just wait sum(array) time

thats why asyncio.as_completed which gives output as soon as something is finished

[glossy lintel]

no no

import asyncio

async def main():
   l = np.array([1, 5, 3, 2, 9, 6])
   await asyncio.gather(*{asyncio.sleep(i) for i in l})

this

list comprehensions

and even better

set comprehensions if they are only int, or other hashable objects

[modern walrus]

yes, they are but, here you gotta wait based on the max number present inside of the array, that is 9 seconds

[glossy lintel]

yeh its a problem with sleep sort

[modern walrus]

thats where i used 1/x

and we can just reverse the list at end

[glossy lintel]

there might be some floating point issues tho

[modern walrus]

then maybe log would help us

or, just divide by a big power of 10

[glossy lintel]

also another problem with sleep sort is

[modern walrus]

the overhead

[glossy lintel]

no no

[modern walrus]

no?

[glossy lintel]

1/95
0.010526315789473684
1/96
0.010416666666666666

look how similar they are

what happens if something freezes for some micro seconds

or takes a little longer than expected

the 96th element could take 0.010526315789473683s

[modern walrus]

yeah i agree, maybe 1/x wasnt a good idea, what if its /10 powers?

[glossy lintel]

like?

[modern walrus]

like just making each element into a decimal point, like
96 -> 0.96
123 -> 0.123

unless we are sorting very huge number, we wont be facing any kind of problem

or, even /2 and convertion to decimal point too help with huge numbers

after all, big number is a big number, even if all of the elements got halfed

i feel like the main problem is overhead of creating threads

if we get like 10^5 elements, we would need to create 10^5 threads, which is ineffective

but, at this time, other sorting algorithms would have already started to sort

[glossy lintel]

yes

[modern walrus]

maybe like merge sort, we can divde and conquer?

but end of the day, we would have created 10^5 threads

I was thinking of a way to sort on the go, where we take one element, wait for it to finish, and use that time taken to place on a continous distribution, like from 0 to 1. after we gone through all the elements, we just collect everything in order from beginning to end of the continous distribution

I might be litreally spewing nonsense rn

well anyway, i wanted to hear your opinion this.. thanks

[glossy lintel]

np

[modern walrus]

import numpy as np
a = [4,1,3,5,2]
t = np.zeros(max(a)+1)
t[a] = 1
print(np.where(t==1)[0])
#output: array([1, 2, 3, 4, 5], dtype=int64)

is there a name for this sorting algorithm?

[glossy lintel]

interesting little algorithm

(not the name ofc, lmao)

[modern walrus]

lol, i used the sieve method they use for finding primes

the memory space is O(max(array)), and only applicable for Natural Numbers....?

[glossy lintel]

look at dijkstra prime finding algorithm

if u want both of the worlds

[modern walrus]

sure would see it

[agile sundial]

incorrect

[modern walrus]

hmm can you explain more?

yes, im sure it isnt even a sorting algorithm, cause it cant handle duplicate elements

[agile sundial]

yes, that's the problem

[modern walrus]

if we can know how many particular element is present, then i guess, while returning, we can just put the copies in the place of the single element

[agile sundial]

yep. that's counting sort

[glossy lintel]

should i try bring the checkpoints algorithm i developed back to the liked list?

[lean walrus]

https://en.wikipedia.org/wiki/Counting_sort

ah, someone already mentioned it :(

[modern walrus]

Thanks 😄

[modern walrus]

ah thanks, all it matters is that you tried to help me lol

[modern walrus]

what is that?

[glossy lintel]

its basically caching

but more enhanced

when performing any operations on specific nodes(might change it to precompute nodes in a distribution)

you record a checkpoint

when running the same or other operation, the program will check if it has precomputed the same value again(just like caching) if it did then return

However

[modern walrus]

yeah i was waiting for this word

[glossy lintel]

if not then it finds the shortest distance between its target destination and one of the checkpoint

for example

Suppose this linked list

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

on the first iteration since we don't have any checkpoints, we start from the beggining and iterate over

when we reach for example the node with value 5

we not only do the operation but also record it as a checkpoint

now for the second iteration

the program does the checking

for instance again value 5, it has already precomputed it so it returns(caching)

but third iteration

is where it gets interesting

suppose i wanna the node value 8

it isn't cached so the normal thing would be to start from the beggining and go to 8. BUT

it hasn't have to be this way

what if we could just start from node 5 that we already checkpointed

And cut the search down like so

5 -> 6 -> 7 -> 8

[modern walrus]

yeah, but how do we know that 8 node is not before 5?

[glossy lintel]

extremely faster right?

[glossy lintel]

we also record the position(index) on the checkpoints

[drifting quartz]

what does if __name__ == “__main__” do?

is it similar to while ?

[glossy lintel]

it signals to the reader that this script is runnable and not a module

[drifting quartz]

i want my code to be on

[glossy lintel]

if we do position type operations, like insertion at a position. This could save a bunch of time

ofc it would require space to store the checkpoints

[drifting quartz]

what did you mean

[glossy lintel]

thats why il have it as optional

[drifting quartz]

can you give me example ?

[glossy lintel]

adding

def abc():
  ....

def foo():
   ....
   abc()
   return foo()

def main():
   ....
   abc() + foo()

if __name__ == "__main__":
    main()

tells the person reading the code that this is meant to be run and not act as a module

[modern walrus]

i understand that, but we usually fetch the value from inside a node. now, we have traversed until 5, but we only save 5 as checkpoint, but not the 1,2,3,4. as we only have 5 in our memory, we cant find which side 8 is...?

[glossy lintel]

we know the position

thats what im talking advantage of

position / index is always non-negative and a integer

[modern walrus]

and for futher refrence, you can see https://youtu.be/sugvnHA7ElY

[modern walrus]

oh, so we know that our value lies on position 8, am i righ?

so instead of starting from head, we start from the check point if we can reach the goal from checkpoint(i.e, if goal is left of checkpoint).. am i right?

[glossy lintel]

we don't know the value

but we know its position

[modern walrus]

yeah, but only the position

[glossy lintel]

yes

i could easily represent the linked list as

[modern walrus]

if we are reusing it a lot, then its a effective algorithm. and to make it somewhat better, we can store only the nodes as check points which are far from other checkpoints

[glossy lintel]

"abc" -> 6.32 -> ("H", 101) -> object() -> 98

[modern walrus]

so, we will get lot of reach, as well as less memory... am i right?

[glossy lintel]

and same deal

[glossy lintel]

yeh i was thinking the same for distribution of checkpoints

[modern walrus]

what if, instead of waiting for the first iteration, we just get the needed check points, like say index which are factors of 7

then, it will be ready out of the box

[glossy lintel]

example?

[modern walrus]

all factors of 3 are checkpoints, then:
1->2->3(ckp)->4->5->6(ckp)->.....

i used 3 as example, we can use any number, and we assign check points as the linked list is being created

[glossy lintel]

the linked list can include any type of value

it could have integers, strings, lists, tuples, sets....

[modern walrus]

Hmm is that a problem?

[patent spire]

hey need help with simple mandelbrot code

#python-discussion message

just trying to recreate complex squaring algo using floats

what is the issue?

[glossy lintel]

well yeh, since the linked list is unsorted

and jumbled up

[jolly mortar]

you set x = beg, so everytime you modify x you modify beg too

[glossy lintel]

should i use generators / iterators as input for stacks(data structure)?

class Stack():
  def __init__(*args):
     self.__sequence = iter(args)
     self.top = next(self.__sequence)

like so

[honest rose]

use this

your welcome

[glossy lintel]

ik its like a implementation

but is it efficient & unique?

[honest rose]

dont ask me that i dont have that much exprience

[glossy lintel]

so why u responded then?

i need a bit more helpful insight

[keen hearth]

An iterator doesn't really work as a stack because you don't have any way of putting an item back on to the front of the iterator.

A list works nicely as a stack.

[patent spire]

Thanks

[oak shuttle]

Is there builtin support for decreaseKey and increaseKey operation on binary heaps?

heapq doesn’t seem to provide that

[keen hearth]

heapq doesn't provide these operations, but you usually don't need them in practice.

[oak shuttle]

I was trying to implement dijkstra and prim’s using heapq as the priority queue, I have used a set to ignore nodes that have been visited but I didn’t quite like that, I want to implement it with changing the priority of keys

[keen hearth]

Oh right. A set of seen nodes is the approach I would take. I think the code ends up being a bit simpler. What did you dislike about this approach?

[oak shuttle]

I just feel like storing multiple nodes with same key in the pq is quite weird, would it grow to a very large size if the graph is dense?

I haven’t read a through analysis of the algorithms so just my assumptions

[keen hearth]

I'm not sure but I think it wouldn't ever grow larger than the number edges in the graph?

[oak shuttle]

Yeah but the number of edges can be at most the square of the number of nodes

Is it

So it would still be a considerable difference

[acoustic thunder]

hello everyone. I have an issue with my code. I have a minimax function which evaluates each position recursively, and it returns the eval. I would like it to return which move to play as well, but I don't quite know how to get it to do that, if anyone could help me please, I would be very thankfull

https://paste.pythondiscord.com/4M4J4P42PMNZO5KJ7NL72UR5OM

[mossy finch]

you can calculate the weight of each moves and then return the move which has the highest weight

[acoustic thunder]

good idea

thank you for this advice

[glossy lintel]

but this kind of feels like a rip off

implementing with a list a stack

[haughty mountain]

why?

[glossy lintel]

i mean you can easily use an array to represent a stack

[haughty mountain]

a stack is an abstract data type, a list is one way to implement it

[glossy lintel]

yes

but i want better ways to implement it than just placing a list

[haughty mountain]

better how?

[glossy lintel]

idk

what im saying is

why call this?

stack = Stack(1, 2, 3)

and not use this?

stack = [1, 2, 3]

just because you can see the last element

a.k.a 3

doesn't make the stack a lot more unique

[haughty mountain]

I would use the latter

[glossy lintel]

exactly

[haughty mountain]

or maybe using a deque depending on needs

to me Stack is more just an interface

[glossy lintel]

a tree for example is a little more complicated to implement

thus its useful for a class to have

[haughty mountain]

(and e.g. C++ does it that way)

(you can specify the backing container type)

also for the case of a tree there is a bunch of ways to implement it

none of which is optimal in general

[glossy lintel]

true

but they are not that straightforward and easy to implement

thats why they are useful when implemented before

[haughty mountain]

they are quite straightforward imo

[glossy lintel]

also

another thing

[glossy lintel]

iterators don't eat up storage

[haughty mountain]

they are backed by something that needs storage

[glossy lintel]

generators tho?

they compute things on the fly

[haughty mountain]

not really applicable for a stack

if you push stuff on a stack it needs to be stored somewhere

[glossy lintel]

ok

[glossy lintel]

got it quite fast unexpectedly

import time
from PyRallax import SinglyLinkedList

l = [*range(5_000_000)]
t = time.perf_counter()
l.insert(0, len(l) / 2)
print(time.perf_counter() - t)

l2 = SinglyLinkedList(*range(5_000_000))
t2 = time.perf_counter()
l2.insert(len(l2) / 2, 0)
print(time.perf_counter() - t2)

got this script

0.0068 seconds insertion on python's list

but

3.770300099859014e-05 seconds insertion on my singly linked list

it kinda feels wrong since they both have their own weakness

lists need to move 1 block of memory to have a new space for the new element(so everything after 2500k nodes will be moved) but they have way faster access time than linked lists

whereas linked lists have the strength of inserting and deleting but they need to traverse to find the corresponding node on the index

nvm

sad ngl tho(i was right)

actual time was on the lines of

0.0032547079972573556
0.11619720900125685

a bit close

ofc using batch processing on linked list beats python's lists when you wanna do some operation like insertion about ~100x

insanely close when using mypyc

0.0031263929995475337
0.09593938600301044

[haughty mountain]

30x slower?

[glossy lintel]

look the mypyc version

[outer rain]

!e

print(0.11619720900125685 / 0.0032547079972573556)
print(0.09593938600301044 / 0.0031263929995475337)

[halcyon plank]

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

001 | 35.70127000614886
002 | 30.68692452193158

[haughty mountain]

yeah, same-ish relative performance

[glossy lintel]

oh

[thorny holly]

hi

[calm lion]

hi

is anybody familiar with kruskal's algorithm for finding the minimum spanning tree?

our prof implements it like this

I don't understand why they would use a priority queue here, deleting the minimum requires log(n) and that's done n times, building it is nlog(n)

just sorting the edges in a list requires O(nlog(n)) but then traversing it from min to max is only O(n)

am I missing something here?

[agile sundial]

yeah, you don't need a priority queue. but technically you can build one in O(n)

[calm lion]

hmm

really?

hold up

[agile sundial]

didn't you derive this recently?

[calm lion]

I'm studying so much within a few days lemme sort out my brain a bit

dam you right I literally did talk about this before

[modern gulch]

Have you looked at a visual example of Kruskals? It's actually fairly straight forward to understand (even if that code makes it seem complicated).

[calm lion]

I understand kruskal I'm just curious about my professors choice of data structures here

[modern gulch]

(I ran across this recently when implementing Kruskal's in SQL... https://www.cs.usfca.edu/~galles/visualization/Kruskal.html)

[calm lion]

but yah building a heap takes O(n) time

wait no

that can't be right

oh yah

my fault

so in a way using a heap here reverses the computations

takes O(n) at the start to build it, but then sums to O(nlogn) for all retrievals of mins

still useless I'd say, most likely the constant factors are way worse than just sorting and then traversing the list

that being said, this is false then

building the priority queue takes in fact E

no? @agile sundial

[agile sundial]

well, they way they're doing it, it is E log E

but it could be made E

[calm lion]

true

hold up lemme get my brain straight

yah

true

this isn't how heapify works

[agile sundial]

for that to work, you need to get all the elements in at the same time, and defer moving stuff around to the end

[calm lion]

yup yup

basically heapify the whole thing at the start

I'd say that makes the implementation nearly equivalent to sorting using heapsort at the start and then traversing the list

[agile sundial]

indeed

[haughty mountain]

fwiw, you will only pick edges until all nodes are connected

so it's likely you're picking a minimum less than M times

[calm lion]

yah true

would that potentially lead to the usage of the priority queue here being more efficient than simple sorting + traversing?

because building a heap for E total edges is O(E), but then you're only pulling out of it V-1 times (assuming graph is connected)

so it's actually O((V*log(E))

so I get your point, not the same as just heapsort + traversing

I'm actually now convinced that the usage of a priority queue here would almost always be better

considering graphs are usually very sparse

[haughty mountain]

it will typically be more than V-1

you will likely end up popping edges that would connect already connected components, which you need to discard

[calm lion]

oh yah trueee

so actually in the worst case it's still Elog(E)

because I could potentially have the last component be the last in the priority queue

[calm lion]

also

this is for dijkstras

doesn't the pq.contains(w) literally defeat the purpose of priority queue?

cuz I can't see how it's not O(n)

[narrow mica]

the pseudocode is a bit vague, but you can make a boolean array the length of the number of nodes to denote which nodes are in the pq

though personally when I implement it I don't do that check

def relax(self, e):
    v, w = e.from, e.to
    if (self.distTo[w] > self.distTo[v] + e.weight):  # this will filter out any subsequent edges to `w` if they don't make the distance shorter anyway
        self.distTo[w] = self.distTo[v] + e.weight
        self.edgeTo[w] = e
        self.pq.push( (self.distTo[w], w) )  # weight in front, assuming the pq will compare the distance first instead of the node number which is wrong

[calm lion]

yup, exactly what I was thinking

actually for how i implemented it, I have an extra
if distance > distances[node]:
continue
check, which will disregard any distance that isn't the best one discovered yet

I don't know intuitively that feels necessary if I'm not doing the existence check before inserting

[narrow mica]

tbh if you know how to do bfs, you can pretty much copy the bfs code and just do some small changes to make it dijkstra's

[calm lion]

yes

instead of a deque you use a priority queue

that's the main difference

[calm lion]

aight chat

this is the slide MSD Radix sort

am I tripping right now or what's going on

how is NlogrN sublinear

also wouldn't a more accurate average case be something like
O(N * min(W, log_R(N)))

since log_R(N) can potentially become larger than W

[regal spoke]

This isn't a standard priority queue. It is more like a dict and priority queue merged into one. The reason why having a decreaseKey function is nice is that in theory it allows dijkstra to use less memory (O(V) instead of O(E)). But in practice people almost never bother implementing it this way.

[regal spoke]

N = number of strings. W = sum of lengths of strings. R = alphabet size

[regal spoke]

It is sublinear in the sense that there is no W dependence. But it is definitely not sublinear in N.

[regal spoke]

No it cant. W is the sum of lengths of all strings, meaning W >= N

[drifting quartz]

  # # Get text size using a default font (e.g., Arial)
  font_size = int(image.height / 20)
  font = ImageFont.truetype("arial.ttf", font_size)
  text_width, text_height = draw.textsize(watermark_text, font)

guys whats wrong with it

  File "C:\Users\User\Desktop\Workplace\watermark\main.py", line 24, in add_watermark
    text_width, text_height = draw.textsize(watermark_text, font)
AttributeError: 'ImageDraw' object has no attribute 'textsize'```

i am using pillow

[frail zinc]

wtf

[lean walrus]

i am making a puzzle app (puzzle is called slitherlink)

i have to keep the following state about the board:

• number in the middle of the cell
• info about each edge
• info about each vertex (not necessary, but would be nice to have)

how to conveniently store all of this?
right now i have this: ```py
nums: list[list[Num]] # x * y
lines_v: list[list[State]] # x+1 * y
lines_h: list[list[State]] # x * y+1

this works, but i dont like it. it is pretty hard to manipulate entire board at once (shift / transpose),  and there is a big chance of off-by-one errors because of "rectangular" arrays for edges

another idea would be to store everything in big heterogenous 2d array that is double the size of normal one, im still thinking about it
what are your ideas?

[austere sparrow]

Are you only ever planning to support slitherlink on a square board?

[lean walrus]

yes i am

i dont like slitherlink on any other boards

imo, square board has the most interesting patterns

i guess i could have stored it as list of vertices, edges and numbers, with coordinates attached to everything, and also information about relations between objects
but it an overkill for rect boards

[austere sparrow]

Seems okay to me. You could create proxy objects that provide access for the sides/vertices of a single cell (reduces the number of math fiddling)

cell = Cell(x, y, board)
cell.sides()  # list[State]

[austere sparrow]

cairo 🥺

[lean walrus]

+   +   + x +   + - +
          3 |   | 1
+ - +   +   +   +   +
x     0   2       3
+   + - + - +   + - +
|     2   2   3
+ - +   +   +   +   +
    |       |
+ x + x +   +   +   +
      3       0     |
+   +   +   +   +   +

>>> b.data
[   [0, -1, 0, -1, 0, 0, 0, -1, 0, 1, 0],
    [-1, -1, -1, -1, -1, 3, 1, -1, 1, 1, -1],
    [0, 1, 0, -1, 0, -1, 0, -1, 0, -1, 0],
    [0, -1, -1, 0, -1, 2, -1, -1, -1, 3, -1],
    [0, -1, 0, 1, 0, 1, 0, -1, 0, 1, 0],
    [1, -1, -1, 2, -1, 2, -1, 3, -1, -1, -1],
    [0, 1, 0, -1, 0, -1, 0, -1, 0, -1, 0],
    [-1, -1, 1, -1, -1, -1, 1, -1, -1, -1, -1],
    [0, 0, 0, 0, 0, -1, 0, -1, 0, -1, 0],
    [-1, -1, -1, 3, -1, -1, -1, 0, -1, -1, 1],
    [0, -1, 0, -1, 0, -1, 0, -1, 0, -1, 0]]

[lean walrus]

it is cool as well, but i like square more 🥰

hex is the most boring imo

[austere sparrow]

||I tried solving some puzzles on kwontomloop, and the slightly different representation of the board completely bricked me as I've been using sgt-puzzles for years||

[lean walrus]

never seen this one (image is from google)
looks like six square board glued together

im stuck, dont see anything else on this monochrome board 🙂

so i ended up storing everything in one big array and carefully retrieving values from it

i made 3 off-by-one errors along the way

[boreal sigil]

Hi i m now hear

[lean walrus]

proxy objects can have funny consequences
for example: every edge exists between some two cells
and rightmost edge touches some normal cell and some cell that exists just outside the board
and the only thing you can do with this cell is to get its left edge, everything else should be invalid

but i dont think it is a problem
i would have to add padding to the board in any case, and i dont think it is a problem with padding in every direction

[mortal breach]

hey why is this giving me always the giving me the message```python
while True:
Selection = input("""
A foe has appeared, what do you do

1: Attack (a simple attack)
2: Defend (diminish damage equal to your Defense attribute)
3: Flee (1/10 change o skipping this fight, but you dont level up)\n""")

        Selection = Selection.upper()
        
        if Selection != "1" or "ATTACK" or "2" or "DEFEND" or 3 or "FLEE":
            print(f"[{Selection}] is not a valid option choose a valid option\n")
        else:
            break

never breaks out of the loop

[agile sundial]

!or

[halcyon plank]

The or-gotcha

When checking if something is equal to one thing or another, you might think that this is possible:

# Incorrect...
if favorite_fruit == 'grapefruit' or 'lemon':
    print("That's a weird favorite fruit to have.")

While this makes sense in English, it may not behave the way you would expect. In Python, you should have complete instructions on both sides of the logical operator.

So, if you want to check if something is equal to one thing or another, there are two common ways:

# Like this...
if favorite_fruit == 'grapefruit' or favorite_fruit == 'lemon':
    print("That's a weird favorite fruit to have.")

# ...or like this.
if favorite_fruit in ('grapefruit', 'lemon'):
    print("That's a weird favorite fruit to have.")

[mortal breach]

oh thanks

[remote monolith]

Is there anyone that can help me with an application I am trying to write in pygame? Please dm me.

[keen hearth]

Personally I think I'd try something like this: ```py
@dataclass
class Board:
height: int
width: int
active: set[Board.Edge]
ruled_out: set[Board.Edge]
clues: dict[Board.Cell, int]

@dataclass(frozen=True)
class Cell:
    r: int
    c: int

@dataclass(frozen=True)
class Edge:
    r: int
    c: int
    vertical: bool

I've had good experiences in the past using set/dict representations over 2d-array representations for states (in things like Advent of Code puzzles). Here is another possible representation of cells/edges:py
@dataclass(frozen=True)
class Cell:
vertices: frozenset[Board.Vertex]

@dataclass(frozen=True)
class Edge:
    start: Board.Vertex
    end: Board.Vertex

@dataclass(frozen=True)
class Vertex:
    row: int
    col: int

I.e. I'd try to write methods so that you don't have to think at all about the geometry of the board when implementing the rest of the game logic. It kind of makes it more general too (you know the old programming/math adage about it sometimes being easier to solve a more general problem even if you don't need the general solution)

[modern jungle]

what is frozenset

[keen hearth]

It's essentially an immutable version of set.

I.e. after creating it you can't change its members.

[modern jungle]

oh

the name just explains everything lol, it is a frozen set

[keen hearth]

It's handy when you need a set-like datastructure, but you also need it to be hashable.

[keen hearth]

Yeah lol

[calm lion]

yo chat

on some real fucking shit

our prof be giving us a lot of problems I can't fucking solve and it's giving me big anxiety

would you guys say this is a problem suited for a first-year undergrad?

Given an edge-weighted graph G and an edge e, design and implement a linear-time algorithm to determine whether e appears in some MST of G. Note that since your algorithm must take linear time in the worst case, you cannot afford to compute the MST itself.

Hint: consider the subgraph G' of G containing only those edges whose weight is strictly less than that of e.

[narrow mica]

hint 2: use the cycle property, which states:
for any cycle C and an edge in it e, if the weight of e is greater than all other edges' weights in C, then e won't be in any MST
in other words, if you can make a cycle that contains e, and e has the maximum weight out of all the edges in that cycle, then e is not in a MST, and vice versa

[calm lion]

yah I gave up and the solution's only explanation was exactly what you're saying rn

but how the FUCK AM I SUPPOSED TO HAVE KNOWN THAT CYCLE PROPERTY

[narrow mica]

if they didn't teach you about it before asking you to do this then you're f'd

[calm lion]

MAAAAN FUCK THIS SHIT. I mean it is what it is this ain't worth my mental health

[narrow mica]

it's one of those things that's either you know or you don't, unless you're a god and can prove it on the spot

[calm lion]

and nah she ain't teach us any of this

what a fucking waste of my time trying to solve this

[narrow mica]

I don't think there's much you can do about your teacher
so I'd say your next best bet would be to learn more on your own after class or smthn

[calm lion]

you right

but like fuck me dawg

this shit's gon give me gray hairs

yah maybe I'm tripping ion know

[tight cedar]

I guess if you think in Kruskal's way, to determine whether to add e to the mst depends on whether it forms a cycle in the tree formed by edges with weight less than e?

so it is the same thing as the cycle property

[haughty mountain]

right

wdym "the cycle property"?

[tight cedar]

it was mentioned above

[haughty mountain]

does it work to just check if edge e when added joins two components of the subgraph of edges < e?

I think the answer is yes

[calm lion]

kind of

say e = (u, v) the idea is to check whether the u and v are connected in the edges < e graph. If they are, then we know there's a cheaper path so e can't be there. Otherwise, e is necessary to u and v

this can be done in linear time with DFS

[haughty mountain]

I think that's equivalent to what I said

mark all components in the edges < e graph, does e connect two different components?

i.e. does u and v lie in different components

[fresh bramble]

what book you recommend for algo and data structures?

[lean walrus]

!resources

[halcyon plank]

Resources

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

[lean walrus]

and pins

[fresh bramble]

thanks

[regal spoke]

That's definitely the easiest/most straight forward way to do it

[calm lion]

Yah I think so to

I was just rephrasing it in the way that made it click for me

still a very hard question without the second hint purply gave

even with the hint it's not exactly easy

[haughty mountain]

the thing I mentioned doesn't need that hint

I guess it's one way to formalize proving it, but I think of it as just something similar to a substitution argument

[calm lion]

I don't know man but non of this is obvious to me at all

my brian too small for this shit

[hard radish]

hey

i cant speak

[red grove]

look at this crazy lindenmayer curve i made

combination between koch curve and hilbert curve

[lean walrus]

interesting

[soft depot]

hello

does anyone know where i might be able to learn data sorting algorithms such as quick sort. and the likes?

[agile sundial]

any intro dsa textbook will have a section on sorting

[soft depot]

Where might i find an intro DSA textbook?

[agile sundial]

the easiest way is a library, or amazon, or however you want to acquire a textbook

introduction to algorithms by clrs is often used in introductory courses

[keen hearth]

Sorting algorithms are usually taught as a way to introduce algorithms concepts, so yeah any introductory course or book will cover them. Khan academy have a nice introductory algorithms course: https://www.khanacademy.org/computing/computer-science/algorithms

[warped moon]

Should one learn algo and data structure while Learning to code or after a beginner here

[fickle pulsar]

I would say learn to code in one language and then go for data structures and algos

[ripe oxide]

could someone help me at #1226169823218892840 ?

[keen hearth]

Yeah I would agree with this.

Programming knowledge without algorithms knowledge is more practically useful than the other way around.

[warped moon]

Thank you

[woeful lion]

Hello! I'm not sure if this is the correct channel for this, but does anyone know how I might make this bit of code work with an arbitrary number of inputs? The issue is that if I don't do the whole "convolution" (technically not a convolution but it follows the same principles as one) at once, it doesn't produce the proper probability distribution. For reference, I am using a website called "anydice" to check my work.

class dieset(dict):
  #adds special definitions to an otherwise standard dict
  pass #and none of those definitions matter to this problem!
#providing basic dice definitions to play with
d4=dieset({x:1/4 for x in range(1,5)})
d6=dieset({x:1/6 for x in range(1,7)})

def advantage(set1):
    conv=dieset() #Don't worry about it being called a dieset, it's just a dict
    for xkey,xval in set1.items():
        for ykey,yval in set1.items():
            try: conv[max(xkey,ykey)] += xval*yval
            except: conv[max(xkey,ykey)] = xval*yval
    conv=dieset(sorted(conv.items()))
    return(conv)

[upbeat hedge]

quick question.. in a function can we have an if else and in if return and in else yield? I am trying this and even when I hit the if branch with the return it still returns a generator..

[mint jewel]

if a function ever contains a yield or yield from, it becomes a generator function and thus will return a generator. If it doesn't execute any yield, it'll provide an empty generator

[upbeat hedge]

is there a quick solution/pattern to this?

[mint jewel]

that depends a bit on what you want. You can make a function return a generator or a different value by factoring the generator part into a different function and returning the result of that, for example

def foo(a):
    if a:
        return 'win'
    else:
        yield a.bar()
``` becomes
```py
def foo(a):
    def gen():
        yield a.bar()
    if a:
        return 'win'
    else:
        return gen()

[upbeat hedge]

dropped the yields altogether..

I didn't have a problem with yielding everything bit when it was returning 1 value and not a list it was awkward

[idle zephyr]

i might sound dumb,
on codeforces Watermelon problem why this solution doesnt work for input case 6

inp = int(input())


def watermelon(inp):
    if (inp / 2) % 2 == 0:
        print("YES")
    else:
        print("NO")


watermelon(inp=inp)

https://codeforces.com/problemset/problem/4/A

[jolly mortar]

it is not obligatory that the parts are equal

6 can be divided into 2 and 4

[idle zephyr]

there is easy way out given that any (inp/2)<3 can be divided into two even numbers, now im looking for some mathematical formula that'll help me print all resultant pairs

[runic veldt]

is that part of the question too?

doesn’t it just say “print yes” if possible

[idle zephyr]

it doesn't

just looking to build logic solving and satisfying test cases is secondry

[runic veldt]

oh well

mathematically the idea of finding all “splits” is called integer partitioning

[idle zephyr]

yea but it uses a for loop

most of solution uses double for loop

maybe if even number whose half is odd like 6 or 10 (3 and 5) if we add 1 and sub 1 we can have two even numbers

[idle zephyr]

inp = int(input())


def watermelon(inp):
    half = inp / 2

    if inp % 2 == 0 and inp > 3:
        if half % 2 != 0:
            if half - 1 + half + 1 == inp:
                # print([half-1, half+1])
                return "YES"
        # print([half,half])
        return "YES"
    else:
        return "NO"


print(watermelon(inp=inp))

this works

[glossy lintel]

this kinda may sound dumb but should i combine a normal bloom filter and a reversed bloom filter(if it even exists, which instead of saying if a element is possibly present in the bloom filter but definitely not present, it says its definetly present in the bloom filter but possibly not present), will it be basically a hash set ripoff or something more unique and better?

[agile sundial]

you can't say an element is definitely present without retaining the exact element. so your memory costs can't be constant

[haughty mountain]

isn't the answer just if it's an even number > 2?

[tight cedar]

it is

[idle zephyr]

in yes or no it is but i wanted to see even pairs

[glossy lintel]

bloom filters aren't just a 1 bit array m in length that holds the element hashes?

[agile sundial]

i'm talking about your "reversed bloom filter" idea

[glossy lintel]

oh

ok

then

[lilac cradle]

ok so i was thinking about trails (like rendering them) and as it stands i know of an inefficiency; how i do it is i get the position of whatever it is i want a trail to be in, and i append it to a list, then if the list is longer than the maximum, i pop the first entry

the problem of course is that popping the first entry (or anything before the last entry, afaik) is O(n)

is there a more efficient way to do this? maybe some other data type?

[jolly mortar]

!d collections.deque

[halcyon plank]

collections.deque

class collections.deque([iterable[, maxlen]])```
Returns a new deque object initialized left-to-right (using [`append()`](https://docs.python.org/3/library/collections.html#collections.deque.append)) with data from *iterable*. If *iterable* is not specified, the new deque is empty.

Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same *O*(1) performance in either direction.

Though [`list`](https://docs.python.org/3/library/stdtypes.html#list) objects support similar operations, they are optimized for fast fixed-length operations and incur *O*(*n*) memory movement costs for `pop(0)` and `insert(0, v)` operations which change both the size and position of the underlying data representation.

[fresh bramble]

what's the most used algo?

[haughty mountain]

fwiw it's O(distance to the back of the list), so depending on where you pop performance differs

and yeah deque is the answer for your trail

[indigo crag]

Is it possible to redefine arg types for concrete implementation with typing?
https://pastebin.com/jx3emfTL
I want to implement

Schema = TypeVar("Schema", bound=BaseSchema)
SchemaIn:TypeAlias = Schema (base.py) -> redefine SchemaIn = ConcreteSchemaIn (concrete.py)
SchemaOut:TypeAlias = Schema (base.py) -> redefine SchemaOut = ConcreteSchemaOut(concrete.py)

or do I have to assign types in concrete.py manually?

[stiff quartz]

!e

from itertools import combinations

print(list(combinations([1, 2, 3, 4, 5], 2)))

[halcyon plank]

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

[(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]

[stiff quartz]

What is the time complexity of this function, is this truly n chooses 2? (so quadratic)

Or is it 2^n because "under the hood" it's something like:

!e

for s in range(1 << len([1, 2, 3, 4, 5])):
    if bin(s).count('1') != 2:
        continue
    print(bin(s))

[halcyon plank]

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

001 | 0b11
002 | 0b101
003 | 0b110
004 | 0b1001
005 | 0b1010
006 | 0b1100
007 | 0b10001
008 | 0b10010
009 | 0b10100
010 | 0b11000

[mint jewel]

it is actually n choose 2, it uses a more clever algorithm

[narrow mica]

docs

Roughly equivalent to:

def combinations(iterable, r):
    # combinations('ABCD', 2) → AB AC AD BC BD CD
    # combinations(range(4), 3) → 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

[stiff quartz]

damn that's a clever algo

probably wouldn't have understood it without the two examples

so basically i should really refrain from doing that

for s in range(1 << len([1, 2, 3, 4, 5])):
    if bin(s).count('1') != 2:
        continue
    print(bin(s))

to generate all the ways to pick r elements from a set

[mint jewel]

yeah

[lean walrus]

from __future__ import annotations
import typing as t
import dataclasses


@dataclasses.dataclass(slots=True, frozen=True)
class _Node:
    val: str
    next: _Node | None = None

    def __iter__(self) -> t.Iterator[str]:
        node = self
        while node is not None:
            yield node.val
            node = node.next


class StringBuilder:
    __slots__ = ('_node',)
    _node: _Node

    def __init__(self, _node: _Node = _Node('', None)) -> None:
        self._node = _node

    def __iadd__(self, s: str) -> t.Self:
        self._node = _Node(s, self._node)
        return self

    def __getitem__(self, index: slice) -> t.Self:
        if index != slice(None):
            raise ValueError(f'only [::] slice allowed')
        return self.__class__(self._node)

    def __str__(self) -> str:
        s = ''.join(reversed([*self._node])) # is there a better way?
        self._node = _Node(s)
        return s


s = StringBuilder()
s += 'a'
s += 'bc'
assert str(s) == 'abc'

s2 = s[::]
s2 += 'd'
assert str(s) == 'abc'
assert str(s2) == 'abcd'

rate this pls

[stray fractal]

can't you just use reversed(self._node)?

or does it require indexable

oh yeah okay

[lean walrus]

class reversed(Iterator[_T]):
    @overload
    def __new__(cls, sequence: Reversible[_T], /) -> Iterator[_T]: ...  # type: ignore[misc]
    @overload
    def __new__(cls, sequence: SupportsLenAndGetItem[_T], /) -> Iterator[_T]: ...  # type: ignore[misc]
``` it should be either `Reversible` (which it isnt) or `SupportsLenAndGetItem` (which it also isnt)

both options would require either O(N) memory or O(N^2) time

[quiet lance]

I recently came across https://codeflash.ai (pip install codeflash) that claims to solve any algorithms and data structures problems! It asks us to implement a first working version of the code and it by itself finds the best implementation. I have used it a bit and it works pretty well for Python, it even verifies correctness. What do you guys think? Should i stop learning about algorithms? 😂

[lean walrus]

remembering code for common problems != solving problems

[quiet lance]

it unfortunately does not solve all my problems , i still have to implement the first working version. But the good thing is that i can implement a brute force solution or a similarly crappy solution and it just finds the most optimal solution

[narrow mica]

skeptical

[humble carbon]

Maybe someone can check my opened post in python-help (nested-items-problem), read trough it, and maybe provide some valuable insight or code block.

[austere sparrow]

@glass minnow I don't know what that is, but that's not algorithms and data structures

[glass minnow]

how so

[glass minnow]

perhaps I misunderstood you

dont question the ambiquity of said image

[idle zephyr]

bro is using 2 year old meme pfp

[glass minnow]

if 2023 is 2 years ago then so be it

keep liviing in delusion

[idle zephyr]

information reached to you in 2023 information is 2 years old

[glass minnow]

I will not belittle you even though your intelliegence is meagre

im better than that

run along

[austere sparrow]

!ot

[halcyon plank]

Off-topic channel

#ot2-never-nester’s-nightmare

Please read our off-topic etiquette before participating in conversations.

[idle zephyr]

Monday left you broken

[glass minnow]

go tiwddle your thumbs or something

[idle zephyr]

Tuesday crying in server

[glass minnow]

conversing with you is depleting my intelliegnce rapidly

[austere sparrow]

Both of you, get out of this channel

[idle zephyr]

welp

i was here to ask question

[glass minnow]

lets be more respectful

the sole purpouse of this channel is algrothims and data sturctures

[lean walrus]

good morning duckie

[glass minnow]

this person refuses to cooperate

stop spouting nonsense

it's imeprative that you stay on topic

[austere sparrow]

Did you manage to cook the loopy generation?

[glass minnow]

youre a character to say the least

[idle zephyr]

Where can i find such questions to solve which are not leetcode type, i.e
https://www.youtube.com/watch?v=y7FtwrjWXCg
this seems like real world use case

[glass minnow]

but I respect the fact that youre doing your job

[lean walrus]

i managed to sleep a couple of hours 🤪

[glass minnow]

what a meaningless reply

[idle zephyr]

!ot

[halcyon plank]

Off-topic channel

#ot2-never-nester’s-nightmare

Please read our off-topic etiquette before participating in conversations.

[glass minnow]

data structure number 16

[lean walrus]

i guess everyone should go to the offtopic channels

[idle zephyr]

life is offtopic

[glass minnow]

ok

[mint jewel]

I decided to try this out and it got stumped at non-deterministic finite automata determinisation, which is a fairly mundane algorithm, just not one you'll usually find in a leetcode problem etc. It's very slow to actually run things and provides no real information while it does, so I don't think I'll be testing it further. Fed it this with some basic tests.

from dataclasses import dataclass
@dataclass
class FA:
    nstates: int
    f: set[int]
    al: str
    s: int
    edges: list[tuple[str, int, int]]

def nfa_to_dfa(nfa):
    edges = []
    f_ = set()
    for i in range(2 ** nfa.nstates):
        if any((1 << q) & i for q in nfa.f):
            f_.add(i)
        for c in nfa.al:
            n = 0
            for d, f, t in nfa.edges:
                if c == d and i & (1 << f):
                    n |= 1 << t
            if n:
                edges.append((c, i, n))
    return FA(2 ** nfa.nstates, f_, nfa.al, 1 << nfa.s, edges)

[narrow mica]

I asked it a more traditional problem that you may see on coding websites (to count the number of coprime integer pairs between 1 and n), I gave it a naive O(n^2) implementation and this is what it came up with:

from math import gcd

def count_coprime_pairs(n):
    """Find the number of coprime integer pairs (a, b) between [1, n]"""
    def phi(n):
        result = n  # Initialize result as n
        p = 2
        while p * p <= n:
            if n % p == 0:
                while n % p == 0:
                    n //= p
                result -= result // p
            p += 1
        if n > 1:
            result -= result // n
        return result

    coprime_pairs = 0
    for i in range(1, n + 1):
        coprime_pairs += phi(i)

    return coprime_pairs
```credit where credit's due, it is a pretty big improvement, but certainly not optimal
the more obvious optimization from here is to sieve `phi`
after that, it can be improved further by using dirichlet convolution, which is a bit obscure so I wouldn't say I was surprised that it didn't find this

codeflash itself also took a while to run, not sure if that's due to my laptop

[mint jewel]

nah, it is just slow

[indigo musk]

someone please help with my question, I've been waiting over 1 hour for someone to reply (I had to repost) #1227266024231932015 message
🙏 🙏

[haughty mountain]

yeah, that's still quite crap

[sacred laurel]

hello, I'm currently working on an algorithm that rearrange all points in a irregular space so that they are evenly spaced, is that possible ?

[mint jewel]

You'll have to provide more details

[wooden dagger]

Any YT channel and Sites to complete DSA with python ??

[gilded wagon]

Just for the memes.

[quiet lance]

thats interesting, maybe i just tried an easy example and it found an optimal solution and i got excited 🙂
And yeah it is slow, i think because it generates and runs tests.
I now have codeflash as a github actions and it scans and optimizes all the new code i write 🙂

[white anchor]

trying to break python

[hoary flare]

Hey everyone I dont know if this is right place to put this, so let me know if it isn't. I'm trying to write an acceptance rejection algorithm, but I can't see why my code isn't working the way its intended, all the blue lines should at least approximate that of the orange lines. I've attached the plot that I get:

obviously, its not even close:

I'll add my code in a sec

import matplotlib.pyplot as plt
from typing import Callable
from numpy.random import rand
from numpy import arange, log, exp, zeros

_f = lambda x: 2*exp(x)/((1+exp(x))**2)
_g = lambda x: exp(-x)

N = 10000 # sample size
xx = zeros(N) # array to store the samples. Set to zeros initially

def ar(f: Callable, g: Callable, c = 2) -> float:
    X = g(rand())
    Y = rand()*c*g(X)
    return X if (Y <= f(X)) else ar(f,g)

for i in range(N):
    xx[i] = ar(_f, _g)

xxtrunc = xx[xx < 20]

# plot the histogram
plt.figure(figsize = [4,2])
plt.hist(xxtrunc,bins=100,density=True)
#plot the true pdf
t = arange(0, 10, 0.01)
plt.plot(t,_f(t))
plt.show()

I think the issue is in the ar function. I dont know if anyone knows anything about rejection algorithms, but any help would be great

[hoary flare]

nvm, got it

[humble carbon]

Maybe can someone please look at the problem I posted on python-help (recursive breadth)

[humble carbon]

Still relevant, but there is a new updated post with fixes implemented, since the original closed. New post is called Search Problem

[keen hearth]

For future reference, #data-science-and-ml would be a better fit

[sudden zodiac]

the current mainstream crawler libraries is selenium

[uncut horizon]

sorry to post in here but help post hasn't gotten replies in previous hours does anyone have some experience with data management? I have a large object which I mutate every iteration and if some condition is met, these changes are kept, but otherwise I have to reset it back to the state it was in before I did the changes. Is there a way to do it without making a deepcopy (takes a lot of time)?

[outer rain]

If your data is arbitrary, no, there isn't, but it's clearly not. You need to give more details

(also you may want to look into persistent data structures such as these, but I insist on not using persistent data structures if possible - there are good use cases for them, but they are usually just lazy workarounds for properly optimized algorithmic solutions)

[uncut horizon]

happy to do, I posted some more details in python-help (topic is called Help with simple memory management) but I can share the details here as well if you want

this was not in the help one btw, in case you wanted more info on the specific data

I got destroy_sol and fix_sol functions which can change the data structure based on (ref, game)-tuples so I guess I could reverse those to bring the solution back to the original state

this does mean I often have to run those twice which makes it somewhat slower but is at least faster than deepcopying everything

Truth is that I do not have much experience with data management in python (or any language for that matter) so I might miss something obvious to do here

[outer rain]

well ok, from what I see your best bet might be to simply deepcopy as little as possible

I don't know the details of the search algorithm you are using unfortunately

but usually in situtations like this (like in simulated annealing, for instance), you can roll back the operation of the result is thrown away

[uncut horizon]

it's a simple metaheuristic which destroys and adds (ref, game)-tuples

it indeed uses simulated annealing for solution acceptance

[outer rain]

so in your operation you produce some kind of list of actions you have done, which is enough to reverse it

that way you only do exactly as much work undoing operation on your data, as you did when you changed it

[uncut horizon]

ah yes so that is probably this

[outer rain]

yeah, exactly that

[uncut horizon]

It should be okay to code, I just wanted to make sure I didn't have to do that if there was a simpler way

or more efficient

I did something similar in R once and then I didn't have this problem, but I guess R works differently with data

[outer rain]

well, persistency might be a simpler way (but I doubt it's going to be more efficient, but who knows, it's python...)

[outer rain]

is R pass-by-value by default?

[uncut horizon]

it is probably better I do not touch persistency from the look of it

[uncut horizon]

I think it always copies instead of giving pointers

[outer rain]

yeah, makes sense

[uncut horizon]

but somehow that didn't lead to any inefficiency problems

[outer rain]

so it deepcopies by default, probably just optimized well

[uncut horizon]

maybe because it was for some VRP variant which was easier to store

[outer rain]

mayhaps

[uncut horizon]

and probably optimized as well yeah haha

[outer rain]

maybe also clone-on-write 🤔

but I don't know

no idea about R

[uncut horizon]

clone-on-write does sound like it would be efficient

but a quick search says it should be pass-by-value

actually pretty interesting to see these differences, never thought much about it

I didn't do CS but if I would have I probably would have be bored out by such things, but when actually encountering it it is pretty interesting

[worn shard]

Hey, does anyone know how I can determine the heuristic values h(n) in A* algorithm given I only have a graph and some costs? or how using the values obtained from Dijkstra I can make it more efficient by some heuristic values?

[haughty mountain]

you need to know properties and guarantees about your graph

[keen hearth]

A* search uses an atomic state representation (the algorithm doesn't know anything about the states so can't apply any kind of general heuristic) so it depends on knowing something in advance about the structure of the problem.

But if you need to do many searches on the same graph, it can pay to do some pre-computation on the graph to determine something about its structure.

One technique is to select a set of "landmark" nodes, and pre-compute the distance from every node to each landmark, and then use the following admissible heuristic (called a differential heuristic): ```py
def h(node, goal):
return max(
dist[node, landmark] - dist[goal, landmark]
for landmark in landmarks
)

[hushed juniper]

what exactly about that graph!?

[summer jackal]

Can i use heapq with array?

[keen hearth]

Are you actually interested in this discussion? Don't send random messages to meet the voice-verification criteria please or you may be banned from verifying.

[keen hearth]

From the array module?

[summer jackal]

Yes

[keen hearth]

Possibly! I've not thought about that before. I'll look into it

Ah, it appears not. I'm not sure why this restriction is necessary however.

!e ```py
import array, heapq
arr = array.array('H', (1, 2, 3))
heapq.heapify(arr)

[halcyon plank]

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

001 | Traceback (most recent call last):
002 |   File "/home/main.py", line 3, in <module>
003 |     heapq.heapify(arr)
004 | TypeError: heapify() argument must be list, not array.array

[summer jackal]

ok, thanks

[delicate herald]

I'm trying to code sudoku from scratch. I have successfully created the GUI. Each cell is a button that has a unique name: its row (a-f) + column (1-9). The cells are inside squares (frames) inside one big frame. I can generate a random number on each button, but how do I make it follow the rules of sudoku? (No repeats in each row, column or square). I refuse to just Google sudoku code because I want to stretch my brain and learn about different methods and functions and stuff, and I find that fun.

So I think my code needs to check for repeating numbers in each row/column/square?

I'm using tkinter in pycharm

[jolly mortar]

do you mean generating a (solvable) puzzle or solving a given puzzle

[delicate herald]

Generate a full solution, then only display the numbers in 12 randomly selected cells. Then the player uses those to fill in the rest.

[keen hearth]

The vast majority of ways to fill out a sudoku grid will not be valid sudoku puzzles, so you'll need to do some kind of backtracking search or local search to find valid puzzles.

Or you could take a known puzzle and permute the rows/columns in certain ways that guarantee not to break the puzzle.

Local search I think could work well actually. There's an algorithm called "simulated annealing" you could try. I've not tried applying it to finding sudoku puzzles but it works well on similar-ish puzzles like n-queens.

[delicate herald]

Huh, thanks, I'll try that

[keen hearth]

The idea would be that you fill out each row with a random permutation of the numbers 1-9, then repeatedly alter the puzzle in a random way with a bias of moving towards puzzles that are more valid. That bias starts out weaker (more likely to make a random change) and over time becomes stronger (more likely to make a change that brings the puzzle into a more valid state).

It's called simulated annealing because it's like heating a piece of metal up and cooling it down gradually (which is called annealing, in metallurgy). The idea is that, when hot, the molecules can move around randomly and find a more optimal configuration, and this changes the mechanical properties of the metal. So it's like a simulation of that process.

[delicate herald]

I see

very big brain

[keen hearth]

Apparently also with sudoku if you're able to fill in 17 or more squares using at least 8 different digits, without breaking any of the rules, it's likely (but not guaranteed) that this corresponds to a unique solution. So you could combine this fact with backtracking and a solver to check that you've found a puzzle with a unique solution.

[delicate herald]

Fascinating

[keen hearth]

This is pseudocode for a simulated annealing algorithm, from this book https://aima.cs.berkeley.edu/

[inland stratus]

Not 100% sure which channel to ask this so i will ask here, I am currently programming a program that will receive signals from aircraft and then plot them on a map (explained simply) I am using windows and python, I am using an ADS-B receiver but I am not sure how to code the data parsing algorithm and how to plot the aircraft's locations on a map which constantly updates. the program would be similar to rtl1090. For anyone wondering I am doing this for a college project and I have come to a point where I am a bit lost, If anyone thinks they could help it would be amazing you can drop a dm or help out here. Thank you

[worn shard]

ahhh I see, thank you very much !!

[lilac cradle]

thanks for the tip about using a deque for a trail, here's a simple sim i threw together of it

how the fuck can a deque even do that btw

O(1) append and pop on BOTH sides????

[jolly mortar]

linked list of chunks

[muted helm]

I dont know if this is the right disc to ask in, but is it possible to log errors without tossing my entire script in a try except statement?

[vocal gorge]

collections.deque is a linked list of chunks as hsp mentioned, but one can get the same complexities with just a circular buffer

(well, it'd be amortized O(1) for a circular buffer.)

[median sentinel]

I guess its a algo...
So I need a python script where I define a string:

chars = 'abcd'

Then it takes a input (amount)

And then it will print combinations like the following:
aa, ab, ac, ad (d is the end of the letters), ba, bb,bc, bd (d is the end), ca, cb, CC and so on until it printet 100

ChatGPT is to stupid and Im braindead

[mint jewel]

would

for a in chars:
    for b in chars:
        print(a+b)
```work? If so, you may like itertools.product.

[median sentinel]

Works so far but can I somehow limit it?

[mint jewel]

with itertools.product, you can use itertools.islice to only get some number of items.

[shut breach]

can you elaborate?

[cerulean halo]

how do you open an Anaconda Prompt, i've done a quick google search and nothing... https://youtu.be/9Y3yaoi9rUQ?si=Uo-mVkN1_B-068y7&t=957

[hushed juniper]

I’m a fan of brocode

[summer jackal]

can i use heapq as binary tree?

[narrow mica]

well it is a binary heap, so yeah I guess?
what are you gonna use it for, e.g. it definitely won't work as a BST because a heap isn't a BST

[summer jackal]

i just want to get sorted array every time i push some element

[narrow mica]

then no it's not gonna work (you're looking for a Binary Search Tree, or a BST, which... well doesn't equate to a heap)

[summer jackal]

ok, thanks

[agile oar]

Hey where is the best spot to ask about imigrating my powerbi with my postgresql database into my angular project with a springboot backend this seemed like the right place

[compact raptor]

How do I calculate the size of the zero matrix needed to display the entire rotated image?
https://stackoverflow.com/q/78316907/15170972

[vocal gorge]

So you want to calculate the bounding box of a rotated image?

[compact raptor]

yes

[vocal gorge]

Hmm, well, you need this if-statement to always be true

new_x = (j - center[0]) * np.cos(np.deg2rad(angle)) + (i - center[1]) * np.sin(np.deg2rad(angle)) + center[0]
new_y = -(j - center[0]) * np.sin(np.deg2rad(angle)) + (i - center[1]) * np.cos(np.deg2rad(angle)) + center[1]
if new_x >= 0 and new_x < h and new_y >= 0 and new_y < w:

in which case... the slightly complicated part is that you'll need to not just use a larger output image, but shift the coordinates to handle the top-left corner (as in, the center of the original image should map to the center of the new, larger image).
As for the size, though, from geometry you can roughly estimate it as something like this:

the vector between bottom-left and top-right corners is (w cos(φ) - h sin(φ), h cos(φ) + w sin(φ))
the other diagonal (vector from top-left to bottom-right corner) is (w cos(φ) + h sin(φ), - h cos(φ) + w sin(φ))

so the width is max(abs(w cos(φ) - h sin(φ)), abs(w cos(φ) + h sin(φ)))
and similarly for the height

these functions end up looking like this, which I think is right: https://www.desmos.com/calculator/gupawgwecl

This analysis is slightly flawed in that it's continuous, whereas you're doing integer math, so it might be off-by-one or something

[compact raptor]

thanks 🙏

[compact raptor]

You said the width is calculated with max(abs(w cos(φ) - h sin(φ)), abs(w cos(φ) + h sin(φ))), is the height calculated with the same formula? I am asking because my math is not enough to confirm this.

[vocal gorge]

no, it's the second function in the desmos page, max(abs(h cos(φ) + w sin(φ)), abs(- h cos(φ) + w sin(φ)))

[median sentinel]

I need help with pattern. So i take a user input and i have to check if it follows a patter. https:// discord.com /api/webhooks /1228384925733097645/PtTxGO4Fa-wCUaJ-GodnSKJ1nnlAk72S1aB4RVJORCeocNoMFG5IwWFPfzEX-LOR8bdQ

random spacing so it wont be deleted

pattern = r'https://discord.com/api/webhooks/(\d{18})/([\w-]+)'

i tried this but it didnt worked

def validateWebhook(url):
    pattern = r'https://discord\.com/api/webhooks/(\d{18})/([\w-]+)'
    match = re.match(pattern, url)
    print(match)
    if match:
        return True
    else:
        return False

def main():
    url = input("Enter Discord webhook URL: ")
    validated_url = validateWebhook(url)
    if validated_url:
        print("Valid Discord webhook URL:", validated_url)
    else:
        print("Invalid Discord webhook URL format")

if __name__ == "__main__":
    main()

def validateWebhook(url):
    pattern = r'^https://discord\.com/api/webhooks/\d{19}/[a-zA-Z0-9-]{68}$'     #19 #68
    match = re.match(pattern, url)
    print(match)
    if match:
        return True
    else:
        return False

def main():
    url = input("Enter Discord webhook URL: ")
    validated = validateWebhook(url)
    if validated:
        print("Valid Discord webhook URL:", url)
    else:
        print("Invalid Discord webhook URL format")

if __name__ == "__main__":
    main()

works like thsi

[median sentinel]

i know i leaked it. But its on a random crack server

[spring jasper]

I have a solution to https://leetcode.com/problems/trapping-rain-water/ that creates 3 lists and according to leetcode uses less space than the "traditional" 2 pointer solution
is this leetcode being a dummy

[haughty mountain]

how is this a "hard" problem?

[spring jasper]

idk, i've come across harder easies tbh

i know leetcode numbers shouldnt be taken seriously, but really?

class Solution:
    def trap(self, height: List[int]) -> int:
        from itertools import accumulate
        
        max_left = list(accumulate(height, max))
        max_right = list(accumulate(height[::-1], max))[::-1]
        
        mins = [min(i, j) for i, j in zip(max_left, max_right)]
        return sum(u - v for u, v in zip(mins, height))

2 pointers gets 39%

am i doing something wrong

[agile sundial]

average leetcode performance measurements

[spring jasper]

i ran this multiple times

this is basically the same problem as best time to buy/sell stock, that one is marked as easy

[trim axle]

how to solve this problem?

https://paste.pythondiscord.com/FLJA

struggling in this

[fiery cosmos]

hey what is implied by "prefix sum" type problem

[median sentinel]

def getWebhook():
    wh = input(f'{spacing}    -> ')
    if wh.startswith('https://discord.com/api/webhooks/'):       
        return wh
    else:
        print(f'{spacing}Invalid webhook\n')
        getWebhook()

def validateWh(wh):
    data = requests.get(wh)

def main():
    printBanner()
    print(f'{spacing}Enter the webhook to use:')
    wh = getWebhook()
    print(wh)

Why is wh None?

[outer rain]

because you are missing return here:

def getWebhook():
    wh = input(f'{spacing}    -> ')
    if wh.startswith('https://discord.com/api/webhooks/'):       
        return wh
    else:
        print(f'{spacing}Invalid webhook\n')
        return getWebhook()  # <---------------------

(btw a better place to ask would be #1035199133436354600 or just #python-discussion, that question in very vaguely related to algorithms)

[outer rain]

"prefix sum" type problem is when you use prefix sum to solve the problem 👁️👄👁️

[agile sundial]

presumably it's a problem where you build a prefix sum array

[fiery cosmos]

what is that

[agile sundial]

an easily googleable term 😉. basically it's a cumulative sum of an array

[fiery cosmos]

oh

ty. i was trying to get bare bones info without giving away ans

👍🏻

[fiery cosmos]

why isn't this working:

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:

        returnnum = -1

        for i in range(len(nums)):
            if i == 0:
                leftsum = 0
                rightsum = sum(nums[i+1:len(nums)])
                if leftsum == rightsum:
                    returnnum = i

            else:
                leftsum = sum(nums[0:i-1])
                print(leftsum)
                rightsum = sum(nums[i+1:len(nums)])
                print(rightsum)
                if leftsum == rightsum:
                    returnnum = i
            

        return returnnum

solves 724 Find Pivot Index

i'm printing leftsum and rightsum and seeing when they are equal, yet it still doesn't do what i'm trying to accomplish

it does not set returnnum = i when leftsum and rightsum are equal

[haughty mountain]

I mean, it will. Do you have a case to share where you think it doesn't?

[fiery cosmos]

yeah i am failing one of the test cases

lms

[1,7,3,6,5,6]

should return 3, returns -1

so its failing there in the else clause for one reason or another even when i see leftsum and rightsum are both = 11

oh wait

nvm, i failed to see that the way my print statements are grouped, they aren't equal to 11 simultaneously. so i am adding the left and right arrays incorrectly

[rapid sail]

#discord-bots

[fiery cosmos]

any idea why it doesn't work the way i think it should?

leftsum = sum(nums[0:i-1])

this was the error

was able to figure out using pythontutor

v helpful resource where you can step through your code line by line

[sharp edge]

Hi I need help.
I have a list of lists (huge), which I have to read through each element and put it in a table like cell(i,j) = element.
Now running two for loops is getting super expensive in this scenario. Can you please suggest a better approach to this ? Maybe a better algorithm or parallel processing way ?

[fiery cosmos]

is there a way you could go and grab the list you want by index?

i guess if you have to read through every element, there is not

[proven moat]

Hello, I was working on this problem today and arrived at this solution using two pointers after reading a little bit about the problem. I'm pretty new here, but I guess I wasn't expecting this solution to work without having another temp variable to track the largest subarray or a tuple containing left, right.
From what I gather the window just gets 'stuck' at the largest subarray size until it's done iterating over the entire array. Is my understanding correct here?

def findMaxConsecutiveOnesIII(self, nums: List[int], k: int) -> int:

        #this is O(n) time complexity and O(1) space complexity
        left = 0

        for right in range(len(nums)):


            k -= 1 -nums[right]

            if k < 0:
                # We add the value of the                    left pointer to k.                         notice we fliped the                        binary value
                k+= 1 - nums[left]
                #after we've updated k we                   move the left pointer.
                left += 1

        return (right - left + 1)

[keen hearth]

It depends on the specifics. Could you provide a small example?

[keen hearth]

You're essentially running a sliding window over the array (although the length of the window varies) where the window is allowed to contain at most k zeros.

Oh yeah, I see what you mean now sorry 🤔

Yeah you're right that the length of the window gets stuck at the final length, because it can only ever increase in length or stay the same length, and it will only increase in length when k >= 0 (i.e. the resulting window doesn't have too many zeros). I'm not sure if this makes it any clearer, but it could equivalently be written as follows: ```py
def solve(nums, k):
length = 0
for i, num in enumerate(nums):
k -= not num
if k >= 0:
length += 1
else:
k += not nums[i - length]
return length

[fiery cosmos]

this server needs a leetcode problems chan now

i just sat down and solved a leetcode easy by myself in about 3min. i think i am getting better

[rigid trench]

Ok I'm having trouble figuring out how to do this in numpy:
Say I have a matrix T which is the Temperature at each cell and is Nx1. Then I have a matrix A which is a weighted adjacency matrix of size NxN. I also have a matrix H which is the Humidity of each cell and is Nx1.

First, I calculate the gradient between each cell and it's neighbors and I get a matrix G which is Nx1 where "positive" means temperature is flowing in the positive X direction, and negative means it's flowing in the negative direction.
G=A.dot(T)

Now, however, I want to also update the Humidity of each cell using the same gradient... uh... how do I do that.

[fiery cosmos]

love this tool

[proven moat]

Cool! I was racking my brain yesterday over this to the point I stayed up working on it, thanks sounding this out with me . I'm going to try and play around with your snippet on the debugger.

[keen hearth]

Yeah it's fantastic!

[crimson timber]

how do I find the time complexity for
dict.keys function in python: https://docs.python.org/3/library/stdtypes.html#dict.keys

this doesn't mention the keys function:
https://wiki.python.org/moin/TimeComplexity

[lean walrus]

because it is not doing anything expensive

it just creates a keys_view object

[crimson timber]

so safe to assume it is constant time operation

[lean walrus]

in python3, yes

[upbeat hedge]

why is this?

a = [1, 2, 3, 4]
b = [1, 3, 9, 0]
assert id(a[0]) == id(b[0])  # True
assert id(a[2]) == id(b[1])  # True
assert id(a[1]) == id(b[1])  # False

I want the element of the list be contiguous in memory in this case.. Every assert should be false in my mind, because its a different "1" in a different memory location

I want something to store object in continuous memory

@dataclass
class Value:
    x: int


a = [Value(x) for x in [1, 2, 3, 4]]
b = [Value(x) for x in [1, 3, 9, 0]]

for x in a:
    print(id(x))

"""
    this return this which shows
    that memory is not continuous

    129768536742352
    129768536741904
    129768536742096
    129768536743376
"""

[haughty mountain]

small integers are specially handled

[narrow mica]

python caches small integers (-5 ~ 256) so calculations are slightly faster with them

[haughty mountain]

python doesn't do this

it stores pointers to python objects contiguously

[upbeat hedge]

so there is no way to store the actual data contiguously?

do I have to use C for this?

[haughty mountain]

not with python lists

[upbeat hedge]

with what?

[haughty mountain]

numpy can help

[upbeat hedge]

I want a way to do this

Can I add Value objects for example in a numpy array?

[narrow mica]

if python did that, then you can't put elements of different types into a list for example
something more c-based like numpy.ndarrays are contiguous, and that's why you'll see nonhomogenous errors for example

[haughty mountain]

wdym Value objects?

[upbeat hedge]

my custom dataclass example

[haughty mountain]

nope

[upbeat hedge]

can i put tuples in np array?

[haughty mountain]

I mean you can, but it's not stored inline with that

[upbeat hedge]

I want the python way of doing array of structs in C

[haughty mountain]

you kinda don't

[narrow mica]

probably not
e.g. you can say this

class Apple:
    tastiness: int
```but nothing (in native python) is stopping you from doing this
```py
apple = Apple()
apple.tastiness = 'red'

so I'm not sure how you could even hypothetically do it

[upbeat hedge]

if its a dataclass(frozen=True)?

[haughty mountain]

why do you need this?

[narrow mica]

this exists in numpy I guess?

[upbeat hedge]

I am making an ECS by studying FLECS and would like to reimplement it in python. I need to create arrays of structs and they should be stored contiguously and not their references

[narrow mica]

alternatively, instead of

class Point:
  x: int
  y: int

array = ...  # contiguous array of Points... somehow
```you can
```py
point_x = ...  # np array representing `x`
point_y = ...  # np array representing `y`

# or even a 2d array
points = [
    [ ... ],  # np array of `x`
    [ ... ]   # np array of `y`
]

[haughty mountain]

that's the struct of array approach, yeah

doing this in python means avoiding most things python

which makes things quite awkward

[drowsy pecan]

Hi guys, I am a web developer who usually does his DSA with cpp
but recently I have been coming across interviews where they are expecting me to solve questions with Python

Do you guys have any resource or recommendation for me which I can follow to have a quick grasp on DSA with python?

[narrow mica]

it shouldn't matter which language you learn dsa with though, no?
it's the concepts that are important, then you can just implement that idea in the language you're supposed to work with

unless you're looking for what the stdlib offers, then set/dict is #include <unordered_XXX>, import heapq for a priority queue (use a list with its functions), and there's no built-in BST

[drowsy pecan]

I agree that the concepts and logics remains the same
but they expect me to code my logic too

[narrow mica]

yeah so are you trying to learn DSA with python, or just python syntax?

[drowsy pecan]

the right question would be the python syntax for all the data structures and algorithms yesss

like idk how a linked list is defined in python

on a binary tree

[narrow mica]

I wouldn't say it's that different than cpp

[drowsy pecan]

ohh I see

I don't use much libraries in cpp
but I've heard most of the dsa in python is done using libraries and modules only

[narrow mica]

e.g. in cpp you have something like

class LLNode {
    int value;
    LLNode* next;
}
```in python you have
```py
class LLNode:
    value: int
    next: 'LLNode'  # well type annotations don't really matter

top = LLNode(5, None)
first_node = LLNode(5, None)
top.next = first_node

[drowsy pecan]

I think I should first make a solid understanding of the basics of python language first, then it'd be a lot easier to connect and understand the concepts

[drowsy pecan]

yeahhh similar, with constructors ofc

[drowsy pecan]

not much different then, thank you ^^

Still I was hoping to find a resource where I can have a quick overview of all the implementations of these data structures in python tho
If you come across any please let me know, I appreciate the help and explanation above already :))

[narrow mica]

since you already know cpp...

• think of every python variable like a pointer
• the assignment operator = is the "point to" operator
• "(im)mutable" data: whether the underlying data can be changed; if not, it always creates new data

x = 10
y = x    # y points to what x is pointing to; now they point to the same 10
y += 7   # `int` is "immutable," meaning you can't change the 10 x and y were pointing to; instead python creates a new data 17 and points y to that

a = [1]
b = a
b += [5]  # `list` is "mutable," so you can change the underlying list; python does this so both `a` and `b` are now `[1, 5]`

[narrow mica]

I mean rosetta code exists, not sure the quality of python code on dsa there though

[drowsy pecan]

that was such a beautiful explanation, thank you very much 🙏
I see! so all the variables are just pointers here, got it ^^

[drowsy pecan]

just looked
at first I thought it redirected me to wikipedia lmao

[keen hearth]

You probably just need a general for-programmers python course. This one by David Beazley is pretty good I think: https://dabeaz-course.github.io/practical-python/

[stiff quartz]

Anyone could help me understand the segment tree we can build without padding with extra values to get to the nearest greater power of 2?

I've got a good grasp of the recursive and iterative versions of segment trees

But I'm trying to see how the version that takes O(2n) instead of O(4n) works

Been trying to follow https://codeforces.com/blog/entry/18051 but they don't explain how to visualise the set of perfect binary trees the segment tree consists of in this approach

As an example I'm building a MaxSegmentTree with this array: [-1, 2, 1, 4, -2, -3, 2] (len = 7 which is not a power of 2) and instead of building a segment tree of size 16 it is supposedly possible to build a segment tree of size 14 in that manner:

    def __init__(self, data: list[int]):
        self.n: int = len(data)
        self.data: list[int] = [-10**9] * self.n + data

        for i in range(2 * self.n)[::-1]:
            self.data[i//2] = max(self.data[i//2], self.data[i])

Which gives [4, 4, 4, 2, 2, 4, 2, -1, 2, 1, 4, -2, -3, 2], however I have no idea how to represent it, doing it with the standard representation of binary trees (children of i are 2*i+1 and 2*i+2) (obviously) doesn't work

But how do I know if it's three segment trees of size 2 and one of size 4 or two segment trees of size 4 and one of size 8 (random numbers, I know they don't sum up correctly)

[narrow mica]

children of i are 2*i+1 and 2*i+2 (obviously) doesn't work
it works, for 0-based binary trees (root index is 0)
for 1-based binary trees, children of i is 2*i and 2*i+1

[stiff quartz]

yes but here it's not a binary tree it's a set of binary trees right?

[narrow mica]

well no, it's still 1 big binary tree

[stiff quartz]

oh

so children of index 0 is itself and 1?

[narrow mica]

the problem is the root in your array is at index 0, but the blog seems to be working with a binary tree that starts with 1?

[stiff quartz]

I was using an implementation in Python pajenegod posted here so that might be the problem - it seemed easier to understand:

class segment:
  def __init__(self, data, f):
    self.f = f
    self.n = n = len(data)
    self.data = [0] * n + data
    
    for i in range(2 * n)[::-1]:
      self.data[i//2] = f(self.data[i//2], self.data[i])
    
  def query(self, l, r):
    l += self.n
    r += self.n
    
    ans = 0
    while l < r:
      if l&1:
        ans = self.f(ans, self.data[l])
        l += 1
      if r&1:
        r -= 1
        ans = self.f(ans, self.data[r])
      l//=2
      r//=2
    return ans

[narrow mica]

e.g. if you look at this (code in the blog)

void build() {  // build the tree
  for (int i = n - 1; i > 0; --i) t[i] = t[i<<1] + t[i<<1|1];
}
```that definitely won't set a value in `t[0]`

[stiff quartz]

looking at this implementation though (which is 0-index based I think), how do we get the visualisation of the set of perfect binary trees that form the segment tree?

I hope I'm clear sorry

[narrow mica]

the same really? if it is 0-based, then

children of i are 2*i+1 and 2*i+2
should work

you can just look at the pictures in the blog and -1 to all the tree indices that appear in them

[stiff quartz]

yes agreed, however, do they just draw it out with this rule when they say:
"But for those interested in some kind of explanation, here's how the tree for n = 13 looks like"?

because it doesn't seem to work in my case

or maybe i'm just confused wait

no yeah there's something wrong here (max segment tree)

[narrow mica]

the n: -- nodes will still be in your array with some number, it's just that those nodes will never affect query so the author wrote them that way

[stiff quartz]

assuming i'm correct in saying the max segment tree (the one of size 2n) of [-1, 2, 1, 4, -2, -3, 2] is [4, 4, 4, 2, 2, 4, 2, -1, 2, 1, 4, -2, -3, 2]

[narrow mica]

actually

  def __init__(self, data, f):
    self.f = f
    self.n = n = len(data)
    self.data = [0] * n + data
    
    for i in range(2 * n)[::-1]:
      self.data[i//2] = f(self.data[i//2], self.data[i]) # <--
```that line looks wrong

[stiff quartz]

ah what

that's why then

damn

[narrow mica]

in fact the loop range also looks pretty weird

here's Pyrival's implementation that I'm referencing

[stiff quartz]

isn't that one in O(4n) though?

self._size = _size = 1 << (self._len - 1).bit_length() this is taking the closer greatest power of 2

so that's the naive segment tree if i'm not mistaken

here it'd build a segment tree of size 16

instead of 14

[narrow mica]

the query doesn't look like the naive tree

[stiff quartz]

that's just the zkw one right?

still O(4n) space

The query is not recrusive yeah but still isn't the one I was referring to (I think)

[narrow mica]

well in any case your loop probably needs fixing

  def __init__(self, data, f):
    self.f = f
    self.n = n = len(data)
    self.data = [0] * n + data  # <-- here you already have n of 2n filled 
    
    for i in range(2 * n)[::-1]:  # <-- should only need n operations here to fill the remaining nodes
      self.data[i//2] = f(self.data[i//2], self.data[i]) # <-- also wrong (probably)
```I'd guess its something like
```py
    for i in range(n)[::-1]:
        self.data[i] = f(self.data[i*2 + 1], self.data[i*2 + 2])