algos-and-data-structs

[haughty mountain]

len?

[fiery cosmos]

how do i use it?

[haughty mountain]

maybe go though a basic python tutorial if you don't know about len

[fluid haven]

Can someone help me decipher what this algorithm is?

def frabjous_problem(snicker-snack_weight, mome-rath_weights, beamish_values, brillig_count):
    # Twas brillig, and the slithy toves among the wabe did gyre and gimble.
    # Create a 2D array to store the maximum possible value for each subproblem
    chortle_max = [[0 for tove_weight in range(snicker-snack_weight + 1)] for wabe_index in range(brillig_count + 1)]

    # Beware the Jabberwock, my son! The jaws that bite, the claws that catch!
    # Fill in the array using a dynamic programming approach
    for wabe_index in range(1, brillig_count + 1):
        for tove_weight in range(1, snicker-snack_weight + 1):
            # He took his vorpal sword in hand: long time the manxome foe he sought.
            current_tove_weight = mome-rath_weights[wabe_index - 1]
            current_beamish_value = beamish_values[wabe_index - 1]
            if current_tove_weight <= tove_weight:
                # So rested he by the Tumtum tree, and stood awhile in thought.
                # Choose between taking the current item or skipping it
                chortle_max[wabe_index][tove_weight] = max(current_beamish_value + chortle_max[wabe_index - 1][tove_weight - current_tove_weight],
                                                        chortle_max[wabe_index - 1][tove_weight])
            else:
                # And, as in uffish thought he stood, the Jabberwock, with eyes of flame, came whiffling through the tulgey wood, and burbled as it came!
                # Can't take the current item, so just skip it
                chortle_max[wabe_index][tove_weight] = chortle_max[wabe_index - 1][tove_weight]

    # One, two! One, two! And through and through the vorpal blade went snicker-snack!
    # Return the maximum possible value that can be obtained with the given weight capacity
    return chortle_max[brillig_count][snicker-snack_weight]

[stable pecan]

just at a glance it looks like knapsack

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

[fluid haven]

i believe you're right. thank you

[fiery cosmos]

!e

x = [[1,2],[2,4]]

print(x[0[0]])

[halcyon plank]

@fiery cosmos :x: Your 3.11 eval job has completed with return code 1.

001 | /home/main.py:3: SyntaxWarning: 'int' object is not subscriptable; perhaps you missed a comma?
002 |   print(x[0[0]])
003 | Traceback (most recent call last):
004 |   File "/home/main.py", line 3, in <module>
005 |     print(x[0[0]])
006 |             ~^^^
007 | TypeError: 'int' object is not subscriptable

[fiery cosmos]

okay, something wrong is not right

!e

x = [[1,2],[2,4]]

print(x[0][0])

[halcyon plank]

@fiery cosmos :white_check_mark: Your 3.11 eval job has completed with return code 0.

1

[lilac cradle]

does anyone know how you'd detect collision (as well as properties of that collision) with something like a square?
if it's not rotated it's pretty trivial but as best as i can guess i'd need to use something like a rotation matrix to rotate the collision detection point to match the square's rotation

[fiery cosmos]

i don't know why i'm having this problem:
list index out of range

and i forgot to bring the bin thing

[fiery cosmos]

!paste

[halcyon plank]

Pasting large amounts of code

If your code is too long to fit in a codeblock in Discord, you can paste your code here:
https://paste.pythondiscord.com/

After pasting your code, save it by clicking the floppy disk icon in the top right, or by typing ctrl + S. After doing that, the URL should change. Copy the URL and post it here so others can see it.

[fiery cosmos]

https://paste.pythondiscord.com/wofacacuvo

[fiery cosmos]

i'm having problem with this, and the code is up here ^

[vocal gorge]

Collision of what with a square?
Generally, though, check whether it collides with the AABB of the rotated square. If yes, then time to check if it actually collides with the square itself, and how to do that depends on what it's colliding with

[lilac cradle]

a point

[vocal gorge]

there's a formula to check if a point is inside an arbitrary closed polygon

it's something like the sum of cross products with each edge, lemme google

[haughty mountain]

a bunch of cross/dot products

basically just checks to see that all edges agree on which side the point is on

[haughty mountain]

convex polygon

there are ways for non-convex too but they are a tad more annoying

one common one for non-convex is to pick an arbitrary ray starting at the point and count intersections with the polygon

if odd it's inside

if even it's outside

[vocal gorge]

I was actually thinking of the winding number one:

for some reason that's the one I remember well

probably because it has a topological interpretation

[haughty mountain]

seems they are very similar

for both you can just look at the segments intersecting a ray

[vocal gorge]

a point is "inside a polygon" if the polygon is a nontrivial loop in ``𝐂\point` :p

hmm, actually another place comes to mind where I can look it up

[haughty mountain]

just compute this :^)

[crimson timber]

i hate math

[haughty mountain]

there is some information missing there

[vocal gorge]

is there?

[haughty mountain]

oh wait, the second thing is the definition of Q, R, S and not an answer 😅

I feel like that → should be a ⇒?

or am I just not used to the notation used here?

[vocal gorge]

I am interpreting this as \implies, yeah.

[haughty mountain]

so putting this into words and simplifying a tad
"there exists some false S(x) such that all other values of S are true"
"there exists some true Q(x) such that all other values of Q are false"
"there exists some true R(x) such that all other values of R are false"

I think that's what it boils down to at least

[vocal gorge]

that's a good way of putting it

[haughty mountain]

in which case the truthiness is pretty obvious, looking at the definitions of Q, R, S

I suspect this is mostly an exercise in "can you read these symbols and make sense of what they mean?"

[vocal gorge]

that's most of school-level boolean algebra ;p

[haughty mountain]

I'm also missing a : in the statements

I really need to look over my XCompose setup so I can actually type these things

[fiery cosmos]

!e

x = list()

if x != None:
print("empty")
else:
print("not empty")

[halcyon plank]

@fiery cosmos :white_check_mark: Your 3.11 eval job has completed with return code 0.

empty

[lilac cradle]

def bresenham_circle(pos,radius):
    switch = 3 - (2 * radius)
    points = set()
    x = 0
    y = int(radius)
    x2,y2 = int(pos.x),int(pos.y)
    while x <= y:
        points.add((x+x2,-y+y2))
        points.add((y+x2,-x+y2))
        points.add((y+x2,x+y2))
        points.add((x+x2,y+y2))
        points.add((-x+x2,y+y2))        
        points.add((-y+x2,x+y2))
        points.add((-y+x2,-x+y2))
        points.add((-x+x2,-y+y2))
        if switch < 0:
            switch = switch + (4 * x) + 6
        else:
            switch = switch + (4 * (x - y)) + 10
            y = y - 1
        x = x + 1
    return points

how's this for bresenham's circle algorithm?

currently im trying to figure out a better version of bresenham's line algo but i was just curious on your thoughts on this

[upper patrol]

hey guys does someone have a good free course for algorithme and datastructure ?

[haughty mountain]

see pins

[pallid coral]

functional but you can clean it up

def bresenham_circle(pos,radius):
    switch = 3 - (2 * radius)
    points = set()
    x = 0
    y = int(radius)
    x2,y2 = int(pos.x),int(pos.y)
    while x <= y:
        # loop over quadrants
        for xd, yd in [(1, 1), (-1, 1), (1, -1), (-1, -1)]:
          points.add((x*xd + xd, y*yd + yd))
          points.add((y*xd + xd, x*yd + yd))
        if switch < 0:
            switch = switch + (4 * x) + 6
        else:
            switch = switch + (4 * (x - y)) + 10
            y = y - 1
        x = x + 1
    return points

[lilac cradle]

hm

yeah that works

[pallid coral]

I smell an additional simplification

I just

argh

def bresenham_circle(pos,radius):
    switch = 3 - (2 * radius)
    points = set()
    x = 0
    y = int(radius)
    x2,y2 = int(pos.x),int(pos.y)
    for x in range(y):
        # loop over quadrants
        for xd, yd in [(1, 1), (-1, 1), (1, -1), (-1, -1)]:
          points.add((x*xd + xd, y*yd + yd))
          points.add((y*xd + xd, x*yd + yd))
        if switch < 0:
            switch = switch + (4 * x) + 6
        else:
            switch = switch + (4 * (x - y)) + 10
            y = y - 1
        if x + 1 >= y:
          break
    return points

a little odder but now bounded

I mean it was always bounded but

[crude heath]

Hi. I'm trying to implement search (the chess engine kind). Specifically I want to explore all the popular techniques of improving the basic search, like A*, Alpha-Beta pruning, Quiescence search, Monte Carlo Tree Search, and eventually end up doing GOAP and HTN. I think I have a general understanding, but I could use a textbook-type source on it to get a "Okay, now I know enough to start writing code" level of understanding. Any recommendations on a resource? Or do you have the patience to talk through it with me?

Actually, let me dig through the pins first... They all stop just short of implementing generalized tree search...

[lilac cradle]

well that wasn't too hard

[vocal gorge]

nice, uh... wiggling rod?

[lilac cradle]

def create_line(pos_1,pos_2,radius=1):
    points = set()
    radius = int(radius)
    x,y = pos_1
    x2,y2 = pos_2
    dx,dy = abs(x2 - x),-abs(y2 - y)
    sx = 1 if x < x2 else -1
    sy = 1 if y < y2 else -1
    error = dx + dy
    length = int((dx**2 + dy**2)**0.5)
    for _ in range(length+1):
        if radius == 1: 
            points.add((x,y))
        else:
            for y_rad in range(-radius,radius):
                for x_rad in range(-radius,radius):
                    if x_rad**2 + y_rad**2 < radius ** 2:
                        points.add((x+x_rad,y+y_rad))
        if x == x2 and y == y2: break
        if error*2 >= dy:
            if x == x2: break
            error = error + dy
            x = x + sx
        if error*2 <= dx:
            if y == y2: break
            error = error + dx
            y = y + sy
    return points

i modified bresenham's algo a bit to allow you to thicken the line

[vocal gorge]

that's some expensive checks. though I guess nobody cares in python.

[lilac cradle]

like distance? i guess yeah but i couldn't figure out a simpler way

[vocal gorge]

calculating for each y_rad the extent of the filling - should be int(sqrt(radius**2 - y_rad**2)) or so, then filling that range. that'd mean only one calculation per row.

[lilac cradle]

ah

then lemme do that

i mean it's just multiplication for that so it shouldn't be huge either way but

[vocal gorge]

i only really noticed these things because of flashbacks to having to implement some computational geometry for a game AI where they had to be actually performant 🥴

[lilac cradle]

i generally only optimize if it's needed ,tbh

[vocal gorge]

actually, I think I had to manually draw a circle on a numpy array once, too, there this technique was great.

[lilac cradle]

hm i might try marching squares sometime

maybe as a generalized algorithm that i can run on a set of points

actually lemme just try making something myself

[haughty mountain]

bresenham with integer arithmetic is so confusing to read, possibly because my intuition for the algo isn't great :/

[pallid coral]

It's because the algo is rather compressed

[haughty mountain]

with numpy I would be tempted to do x**2 + y**2 - r**2 <= param

just abusing the fact that numpy is so much faster than python that O(n²) might even beat the O(n) python code for not huge circles

[pallid coral]

interestingly enough

It would be faster, but not because O(n^2)

but because it can be parallelized

http://members.chello.at/~easyfilter/bresenham.html

[vocal gorge]

yeah, but that likely will vanish if the function is numbified

[pallid coral]

The magic is that the bresemham algorithm functions by ticking pixels forwards based on the difference in error between two different pixels on the edge of a circle

Which happens to be iteratively dependent only on the radius

[vernal grotto]

in a **randomized binary search tree **where we use rotations to maintain a balanced tree, how can one update the parents pointer to the new root after rotating a subtree?

          / \                                 / \                   
         L   R       ———>                    X   r                          
        / \                                 / \                                   
       X   Y                               Y   R```

like how do i make the parent of "r" point to the new root "L" ?

[lilac cradle]

this works but its so damn laggy lol

[opal oriole]

Naive (or not-so-naive depending on if you extend it) surface nets is faster and more extensible than marching squares / cubes. You might want to give it a try. Also if most of your space is empty consider breaking it up into chunks.

[lilac cradle]

oh i think the reason why it's so slow is that a lot of the particles arent even being rendered

[opal oriole]

*But yeah, this kind of crunching is not Python's strong suit, so it will always be slow (without using mypyc / cython).

[old rover]

def count_bits(x):
  num_bits = 0
  while x:
    num_bits += x & 1
    x >>= 1
  return num_bits


print(count_bits(10))

so this gives me 2

but how does bit counting work?

[agile sundial]

it sees if the rightmost bit is set then right shifts

[old rover]

LSB?

[agile sundial]

edited

[old rover]

i'm gonna watch a video and then come back to this

[agile sundial]

note in python there's bit_length or something like that

[old rover]

ok so i just went over going from bit to decimal

is that part of this?

[haughty mountain]

10 = 0b1010

loop 1: x = 0b1010; x&1 -> 0
loop 2: x =  0b101; x&1 -> 1
loop 3: x =   0b10; x&1 -> 0
loop 4: x =    0b1; x&1 -> 1
x is 0, loop exits

[old rover]

i'm confused but idk what i'm confused by

[haughty mountain]

the equivalent thing is doing a digit sum in base 10, maybe that's more familiar

x%10 gives the rightmost

x//10 "removes" that digit

1234 % 10 -> 4
1234//10 -> 123

keep going until there are no digits left (i.e. until the number is 0)

this is the exact same thing in base 2 using bit operators

you could do %2 and //2 as well, it would do the same thing as the bit operators

[old rover]

i know & is an AND operator

if that helps

[agile sundial]

well i hope you know what the operators in the code mean. otherwise you can't really understand the code

[old rover]

yeah i think i need to review lol

i'm gonna do it tomorrow

[eager ruin]

@balmy oak I dont think I have smaller input I created "test" file to debug and working on script.

[balmy oak]

Could you at least explain what the algorithm should do?

[eager ruin]

But its doing it right now I have it working.

This is how example file looks.

And its structure of the file.

ZenGin Archive
ver 1
zCArchiverGeneric
ASCII
saveGame 0
date 17.9.2002 15:21:1
user mario.roeske
END
objects 7        
END

[% oCWorld:zCWorld 64513 0]
    [VobTree % 0 0]
    
        childs0=int:2
        
        childs1=int:3
        
        childs2=int:0
        
        childs3=int:2
        
        childs4=int:0
        
        childs5=int:0
        
        childs6=int:2

        childs7=int:0
        
        childs8=int:0
        
        childs9=int:2

        childs10=int:0

        childs11=int:2

        childs12=int:0

        childs13=int:0

    [WayNet % 0 0]
    []
    [EndMarker % 0 0]
    []
[]

Ofc its simplified.

Each childs have int for example 2

That means this object have two childs.

If next one also have some childs, that mean it also have number of childs.

Looking at that structure you can read is as. Wait I need write it.

[balmy oak]

But how child and parent are associated? 🤔

[eager ruin]

By integer.

[balmy oak]

So for example 12 and 13 are children of 11?

[eager ruin]

Exactly.

[balmy oak]

So next N elements are it's children?

You definitely don't need 6 for loops there 👀

You could use a stack to keep track of nodes you're currently in

[eager ruin]

This is how relations looks more or less.

[% oCWorld:zCWorld 64513 0]
    [VobTree % 0 0]
    
        childs0=int:2
        
            childs1=int:3
        
                childs2=int:0
        
                childs3=int:2
        
                    childs4=int:0
        
                    childs5=int:0
        
                childs6=int:2

                    childs7=int:0
        
                    childs8=int:0
        
            childs9=int:2

                childs10=int:0

                childs11=int:2

                    childs12=int:0

                    childs13=int:0

So childs9 and childs1 is childs of childs0.

childs6 childs3 and childs2 are childs of childs1.

Etc.

[balmy oak]

You definitely can use a stack

[eager ruin]

Its more efficent?

Im novice at coding I dont know many good techniques.

[balmy oak]

It's more generic, easier to work with

And should work with any depth

[eager ruin]

Its also work with any depth I guess, but I just need more nesting there.

[balmy oak]

But, well, you don't

Nesting is bad 🤓

That's just duplicate code in your case

[eager ruin]

Yes, only one difference is parent_fourth, parent_fifth, parent_sixth etc. 😄

Second first and so one.

@balmy oak what exactly is stack?

[balmy oak]

A structure you can put and pull things from

List can act as a stack

list.append, list.pop

[eager ruin]

So if I input something to stack it will output something?

[balmy oak]

Kind of, you can check how tree traversal algorithms work, here's a good SO answer: https://stackoverflow.com/questions/320052/how-do-you-iterate-over-a-tree

def children(self):
    stack = [self.entities]
    push = stack.append
    pop = stack.pop
    while stack: 
        for e in pop():
            yield e
            if e.entities:
                push(e.entities)

You can use similar approach to construct your tree

And you always can use recursion instead too

[eager ruin]

I will consider it as optimization step after I finish working on entire code.

[uncut zodiac]

this is not only optimization, your code can easily break.

[eager ruin]

How can it break? 🙂
@uncut zodiac

I want hear about your bad experiences with nesting, so I will know what can go wrong.

[haughty mountain]

it's not just the nesting, code duplication is bad

and is a sign you should rethink or refactor things

[warped furnace]

hey , I was learning the priorityQueue inbuilt data structure, I was tring to solve a leetcode problem.("https://leetcode.com/problems/last-stone-weight/"). The priorityQueue order is changing for some reason. I did't understand why. Somebody please help me.I'm a new person to python or any computing language.sorry if its a sily question

[agile sundial]

do you know roughly what a priority queue is?

[eager ruin]

If its work, there is no need to touch it.

[haughty mountain]

don't look at queue

I'm assuming it's a min heap

idk why they even expose it

also, PriorityQueue does way more than you need, it deals with synchronization between threads which will slow it down

[agile sundial]

but it's so much easier to use 😦

[haughty mountain]

if only python exposed a thin wrapper around heapq so people can do the right thing

that would be nice, but we can't have nice things

[agile sundial]

there's pretty much no downside 😔. stick a real heap object in collections and add a bbst while you're at it

[haughty mountain]

no, code can technically work for the thing you're doing but still be terrible

or even wrong for slightly different cases

[agile sundial]

an explanation I heard once was that heapq let's you use your own sequence, but I've never seen anyone do that

[eager ruin]

I highly agree with it but tell that to my terrible car that is old, its breaking up but still working and doing job. Haha

This is just example. 😄

[haughty mountain]

if you need to a change in your code currently you need to make the same change in a bunch of places, and hope that you never forget to keep them in sync

[agile sundial]

if it's working, why change it

[haughty mountain]

as a first step, these sections are identical, break it out into a function

at least that will remove some noise

[old rover]

so all the code does is convert the numbers to binary and then count the amount of 1s? can’t you convert to binary using bin or something?

[agile sundial]

it's not converting to binary

[old rover]

like the reason why the code outputs 2 for 10 is because 10 is 1010

[agile sundial]

well. you could interpret it that way

[old rover]

so there are 2 1s

[haughty mountain]

my main annoyance is with how annoying it is to make a max heap

[agile sundial]

yeah.

[old rover]

could a solution be made where you just use bin and then count the 1s?

[agile sundial]

yes

but it would be sad and slow

[old rover]

bRuTe fOrce

[haughty mountain]

yes, but in any other language than python it would be slow for no reason

[haughty mountain]

the code extracts digits one by one

it's a useful pattern

while n > 0:
  digit = n % base
  n //= base

[old rover]

i think i get it now

i added a print(bin(x))

it’s making sense

thanks guys!

[agile sundial]

in python, you can just just int.bit_length nevermind

[jolly mortar]

int.bit_count

length is total number of bits count is just the 1s

[old rover]

yeah but i guess the book wants me to go more in depth

into using the bitwise operators

idk why that corrected to hotwire lol

[agile sundial]

that doesn't even exist

[jolly mortar]

gaslighter!! https://docs.python.org/3/library/stdtypes.html#int.bit_count

[agile sundial]

is that new

[haughty mountain]

somewhat

[jolly mortar]

3.10 apparently

[agile sundial]

wow I was testing in 3.9 lol

ok nevermind

[old rover]

the book is called elements of programming interviews in python if anyone’s curious

[agile sundial]

I thought you were doing project management

[jolly mortar]

the project is reading the book

[old rover]

ik i just wanted to read a chapter or two

brush up on coding if centene has me doing actual coding

[eager ruin]

Sorry for late answer but what advantage I will get if I split it in function?

As I mentioned previously Im still novice so I can throw around dumb questions.

If its completely readable and clean, and understanable for me there is any reason to use function?

[haughty mountain]

because you can get rid of the repeated code. Repeated code is very annoying and error prone to maintain

[eager ruin]

Maybe for you but for me its easy to read it like this.

[eager ruin]

I can easily modify function, this is good reason to use it.

I see what you mean.

You have more tips according to this code?

[haughty mountain]

like others have mentioned use a stack, you can get rid of all the nesting that way

[eager ruin]

I dont understand stack I need make huge research about it. I think nesting is first step in coding world, but I will check it.

[haughty mountain]

doing it recursively could also be an option

!e here is an unpolished recursive thing

data = '''
        childs0=int:2
        childs1=int:3
        childs2=int:0
        childs3=int:2
        childs4=int:0
        childs5=int:0
        childs6=int:2
        childs7=int:0
        childs8=int:0
        childs9=int:2
        childs10=int:0
        childs11=int:2
        childs12=int:0
        childs13=int:0
'''

def parse_line(line):
  line = line.strip()
  s, n_children = line.split('=int:')
  ident = s.removeprefix('childs')
  return int(ident), int(n_children)

parsed_data = [parse_line(line) for line in data.strip().splitlines()]

from collections import defaultdict

C = defaultdict(list)
def f(it, parent, n_children):
  for _ in range(n_children):
    ident, n = next(it)
    if parent is not None:
      C[parent].append(ident)
    f(it, ident, n)

f(iter(parsed_data), None, 1)
print(C)

[halcyon plank]

@haughty mountain :white_check_mark: Your 3.11 eval job has completed with return code 0.

defaultdict(<class 'list'>, {0: [1, 9], 1: [2, 3, 6], 3: [4, 5], 6: [7, 8], 9: [10, 11], 11: [12, 13]})

[haughty mountain]

though it has a lot of concepts going on at once

iterators, recursion

I would make a closure as well, but that would make it harder to follow

[agile sundial]

regex would make the parsing nice

[haughty mountain]

yeah, but the parsing is the boring part 😛

using a stack in this case is a bit fiddly

the ordering gets weird

the recursion just works

with some iterator magic

it's an interesting way to store trees

!e idk why I did ints when I also use dicts

from collections import defaultdict

data = '''
        childs0=int:2
        childs1=int:3
        childs2=int:0
        childs3=int:2
        childs4=int:0
        childs5=int:0
        childs6=int:2
        childs7=int:0
        childs8=int:0
        childs9=int:2
        childs10=int:0
        childs11=int:2
        childs12=int:0
        childs13=int:0
'''

def parse_line(line):
  line = line.strip()
  ident, n_children = line.split('=int:')
  return ident, int(n_children)

def read_tree(data):
  C = defaultdict(list)
  it = iter(data)

  def f(parent, n_children):
    for _ in range(n_children):
      ident, n = next(it)
      if parent is not None:
        C[parent].append(ident)
      f(ident, n)

  f(None, 1)
  return dict(C)

parsed_data = [parse_line(line) for line in data.strip().splitlines()]
print(read_tree(parsed_data))

[halcyon plank]

@haughty mountain :white_check_mark: Your 3.11 eval job has completed with return code 0.

{'childs0': ['childs1', 'childs9'], 'childs1': ['childs2', 'childs3', 'childs6'], 'childs3': ['childs4', 'childs5'], 'childs6': ['childs7', 'childs8'], 'childs9': ['childs10', 'childs11'], 'childs11': ['childs12', 'childs13']}

[old rover]

def parity(x):
  result = 0
  while x:
    result ^= x & 1
    x >>== 1
  return result

what is ^=?

[agile sundial]

bitwise xor

(and assignment)

though x >>== 1 is an error

[old rover]

yeah i just realized that, nice catch

oh right xor switches

[old rover]

def parity(x):
  result = 0
  while x:
    result ^= 1
    x &= x - 1
  return result
``` so this does the same thing but just written differently

[lean walrus]

parity = lambda x: x.bit_count() & 1

[lilac cradle]

by parity do you mean like, error detection?

[agile sundial]

parity is odd or even number of 1 bits

[floral pine]

anyone on the leetcode grind

[robust needle]

do recursive algorithms count as divide and conqueur?

or is it dynamic programming?

[agile sundial]

recursive algorithms are not necessarily divide and conquer

and they're not necessarily dynamic programming

[robust needle]

can u give me an example please?

[agile sundial]

e.g., a recursive function to search for a value in a linked list is neither of those

[robust needle]

what about graph recursive functions? (that's mainly what i'm studying)

since they usually start from a node/edge, and build from that, does it count as divide and conquer?

[agile sundial]

are you dividing? (no)

[robust needle]

wait dfs isn't divide and conquer?

[agile sundial]

not really

[robust needle]

okay thanks

[lilac cradle]

i accidentally did antialiasing by sampling a function at a higher res and plotting different characters at different thresholds

def get_points(scale,threshold):
    points = {}
    for y in range(h*scale):
        for x in range(w*scale):
            n = test_func((x/scale)-center[0],(y/scale)-center[1])
            if c-threshold-0.75<=n<=c+threshold+0.75:
                points[(int(x/scale),int(y/scale))]=0.25
            if c-threshold-0.5<=n<=c+threshold+0.5:
                points[(int(x/scale),int(y/scale))]=0.5
            if c-threshold-0.25<=n<=c+threshold+0.25:
                points[(int(x/scale),int(y/scale))]=0.75
            if c-threshold<=n<=c+threshold:
                points[(int(x/scale),int(y/scale))]=1

the code is a mess since it was a super quick and dirty test, im gonna try and see if i can do it as a generalized function

[robust needle]

just one last question:
does a recursive factorial function count as a decrease-and-conqueur method?

[agile sundial]

sure

[robust needle]

cool thx

[lilac cradle]

wow that was easy, all you have to do is iterate through and add to a dict's value if a point is there

def anti_alias(input_points,area):
    points = {}
    for y in range(h):
        for x in range(w):
            for y2 in range(-area,area+1):
                for x2 in range(-area,area+1):
                    if (x+x2,y+y2) in input_points:
                        if (x,y) not in points:
                            points[(x,y)]=1
                        else:
                            points[(x,y)]+=1
    return points

pretty inefficient but it works

[haughty mountain]

same effect, different mechanics

x & (x - 1) clears the lowest bit of x

[eager ruin]

You are clearly many levels above me when we speak about coding I dont really understand half of this code.

You directly read lines without previously putting it in list?

But its not exactly what I doing.

I see it now.

[amber minnow]

Struggling here with Rabin Karp

I really dont get how to use it

[lost lily]

Can you be more specific? Do you understand what it's used for?

[amber minnow]

if you want I can show you my code?

Ill give you a full rundown

managed to get a bit done

[lost lily]

Sure

I'm not an expert but I can try to help

[amber minnow]

I got it working

CLRS is my hero

[fiery cosmos]

i stopped here:

and then i got this problem:
'int' object is not subscriptable

this is the log of my debug:

[snow anvil]

Can we please stop sending code as screenshots

It's very upsetting

[haughty mountain]

what is i?

is it something indexable?

[fiery cosmos]

actually i discovered why it bugged, the problem was i re-writed i in nother for, so i changed it to j. i is suppose to be the pivots of the parentesis

now i got a new error, this is my log:

index 1 = 0
[1, 9]
index condition meet
initial parentesis = [1, 9]
indice = ['+', '*', '+', '-', '*', '*', '/', '*']
store = [5, 2, 5, 4, 8, 5, 3, 3, 14]
RNParentesis = [[1, 2], [6, 7], [11, 12]]
index 2 = 0
parentesis index = [1, 2]
index 2 condition meet
modifier = 1
index 2 = 1
parentesis index = [6, 7]
index 2 condition meet
index 2 = 2
parentesis index = [11, 12]
indexed
index 1 = 0
[0, 1]
index condition meet
initial parentesis = [0, 1]
indice = ['+']
store = [5, 2]
RNParentesis = [[5, 6]]
index 2 = 0
parentesis index = [5, 6]
indexed
7
index 3 = 0
in range
test complete
index 1 = 1
[5, 6]
index condition meet
initial parentesis = [4, 5]
indice = ['*']
store = [5, 3]

and this is the error i got:

list assignment index out of range

!paste

[halcyon plank]

Pasting large amounts of code

If your code is too long to fit in a codeblock in Discord, you can paste your code here:
https://paste.pythondiscord.com/

After pasting your code, save it by clicking the floppy disk icon in the top right, or by typing ctrl + S. After doing that, the URL should change. Copy the URL and post it here so others can see it.

[fiery cosmos]

this is my code:
https://paste.pythondiscord.com/orololucid

[haughty mountain]

when in doubt add more prints, see what the list and index are, backtrack from there

[fiery cosmos]

now i thought

it's not considering that the first element is a thing

imnw

[fiery cosmos]

anyone know how bitwise flags work

this is a required second column in a format i'm learning

[agile sundial]

for each row in that table, if the bit is set then the right side is true, or happening, or some interpretation of "on"

it's just a way to send a bunch of booleans as an integer, if you look at the binary representation of say, 13, then you get 0b1101. this tells you that the 0x10 (or 0b1000) bit is set, the 0x8 (or 0b100) bit is set, and the 0x1 (or 0b1) bit is set

[fiery cosmos]

ok ty

[hot latch]

anyone know how to do this problem:
want to schedule some long-ruinning tasks on remote servers optimally to minimize the cost of running them locally. The analysts have two servers, a paid one and a free one. The free server can be used only if the paid server is occupied. The ith task is expected to take time[i] units of time to complete and the cost of processing the task on teh paid server is cost[i]. The task can be run on the free server only if some task is already running on the paid server. THe cost of the free server is 0 and it can process any task in 1 unit of time. Find the minimum cost to complete all the tasks if the tasks are schedule optimally.

Take the following example:

Suppose n=4, cost=[1,1,3,4] and time = [3,1,2,3]

The first task must be scheduled on the paid server for a cost of 1 and it takes 3 units of time to complete. In the meantime, the other three tasks are executed on the free server for no cost as the free server only takes 1 unit to complete any task, Thus we return the total cost as 1.

the method header looks like

def getMinCost(cost,time):

where cost and time are obviously arrays

my original thought is that we can approach this problem as a knapsack problem with some modification

[agile sundial]

wait, the free server only takes 1 unit of time to process any task ?

[hot latch]

yeah

[agile sundial]

sounds like a really nice server lmao

[hot latch]

yeah

but it can only be used if the paid server is being used

[calm eagle]

can anyone help me with interview prep for dsa, I would have a interview soon for software development engineer internship as I got referral , my dm is open or you can text me here

[waxen delta]

Not sure if this is the right channel - this is a numpy indexing question. I wrote it up on SO: https://stackoverflow.com/questions/76107279/numpy-indexing-substrings-of-different-lengths

[robust needle]

Hi can anyone explain prim's proof of correctness?

or more specifically, cut property

I'm trying to understand it via youtube but the explanations don't really click with me

Here is what I get so far

Using induction if T0 is an MST, and we assuming Ti-1 is an MST, then we just need to prove that Ti is an MST

Using contradiction (Ti-1 is MST implies Ti is an MST)' = Ti-1 is MST AND Ti is not in MST

I get there is a minimum edge (e) between Ti-1 and unvisited nodes. If this edge is added (or any edge), Ti-1 becomes Ti

and that the only way to assume the contradiction is if e creates a cycle

https://stackoverflow.com/questions/3327708/minimum-spanning-tree-what-exactly-is-the-cut-property

in the answer, to prove by contradiction the cut property, they are assuming there is an MST T that doesn't contain minimal edge e, but another edge e'. What i don't get is that since e is the minimal edge, isn't this tree containing e' not an MST but just a normal Spanning Tree?

OH MY GOD THAT'S THE POINT

i get it now

[mint tapir]

Hey guys, for some reason my code is breaking when I try to get a value from a map using its key. I'm fetching a command map from the database, and I need to get a list from that map. However, when I try to get the value using the usual method, the function stops working. How can I fix this and get the value from the key?

[worthy kiln]

what are some datastructures i shoul master generating with chatgpt

[uncut zodiac]

you don't master anything with chatgpt 😂

[agile sundial]

what a strange question

[agile sundial]

training to be a prompt engineer? 😔

[misty perch]

hello
im trying to make a function that requires a list of all paths from node p1 to node p2 in a directed acyclic graph, via one of their common ancestors

for i in ancestors:
    paths_up = depth_first_begin_end(family, p1, i, [], [])
    for j in paths_up:
        paths_down = depth_first_begin_end(children_tree, i, p2, j, [])
        for k in paths_down:
            # calculations based on the paths it found

this is my code

• ancestors is a list of p1 and p2's common ancestors
• depth_first_begin_end is a function that uses simple recursive DFS to get all paths between a starting node and an end node

so i loop over ancestors, find all paths from p1 to i, and store those in paths_up
and then i loop over every path in paths_up and find all paths coming down from i to p2, which is stored in paths_down (this variable contains a list of full paths from p1 to p2 via i)

children_tree is just the original graph but backwards so i can go down it as well

this works but its very slow at big complicated graphs (say multiple thousand paths per direction, meaning multiple million paths in total)

depth_first_begin_end is.. kinda fast (takes like 0.007 ~ 0.01 seconds to run)
the for k in paths_down: is pretty fast (takes 0.001 seconds to run)
thus one iteration of for j in paths_up: takes about 0.01 seconds to run

the problem is that the 0.01 seconds pile up and it ends up taking 20+ seconds for the for loop to complete once (and if there are multiple ancestors the whole function takes like a minute to run)

i would appreciate any ideas on how to optimize this

[fiery cosmos]

!paste

[halcyon plank]

Pasting large amounts of code

If your code is too long to fit in a codeblock in Discord, you can paste your code here:
https://paste.pythondiscord.com/

After pasting your code, save it by clicking the floppy disk icon in the top right, or by typing ctrl + S. After doing that, the URL should change. Copy the URL and post it here so others can see it.

[fiery cosmos]

guys, is there a way to upgrade this code?
https://paste.pythondiscord.com/uzahiweqaw

i'm predicting that in a case where you give it a 2/58/3 it would first operate with 58 resulting in 40, then 2/40 resulting on 0.05 then 0.05/3 resulting on 0.1667

okay maybe translate the operators to variables

or better translate it to string than from string convert into operation

guess i found one

with sympy library

how do i update my vscode to update the libraries

i installed sympy library

[haughty mountain]

do you need the actual paths in your computations?

[misty perch]

technically just their lengths

but i dont think there is a way to get the length of the path without finding the path itself first

[haughty mountain]

it's much easier and can be made more efficient

[misty perch]

really?

how so?

i need the length of every single path (that doesnt have loops) from p1 to p2 via i

[fiery cosmos]

in my case, how do i update visual studio code to update their libraries?

[haughty mountain]

do you need all the lengths or do you just care about shortest/longest/whatever?

[misty perch]

all the lengths sadly

[fiery cosmos]

i already installed what i need that is the sympy function

[haughty mountain]

so one big thing is that you only need the unique lengths and how often they appear

[misty perch]

the calculations are summing up 0.5^length for ALL paths

[haughty mountain]

which is a simplification over needing all paths

[misty perch]

how would i go about figuring that out

[haughty mountain]

I can easily construct a DAG that has exponentially many paths, but the number of unique lengths is low

[misty perch]

sure but...

how would i figure that out

[haughty mountain]

there should be some dynamic programming-like way to do this, the one in my head involves keeping a histogram of lengths as you walk the DAG, which kinda still seems a bit wasteful

[misty perch]

doesnt this still involve walking every possible part of the DAG

also sorry im still

kinda not very experienced in programming since i dont do it too often

[haughty mountain]

yes, but you end up bundling things together, so you won't do one pass per path like you would now

[misty perch]

so the code will be like

wait idk how this helps tho idk

😔

for i in ancestors:
    paths_up = depth_first_begin_end(family, p1, i, [], [])
    for j in paths_up:
        # get dictionary(?) of frequencies of lengths of paths from i to p2
        # do calculations of those lengths

i understood this is what u meant
and.. it still has that for j in paths_up loop

unfortunately because im doing this in 2 steps (p1 to ancestor, ancestor to p2)
i cant replace paths_up

because the paths down depend on which nodes the path up took, since there cant be any loops

[haughty mountain]

histogram p1 -> ancestor
histogram p2 -> ancestor

combine those

and you get a new histogram of all lengths

[misty perch]

but p2 -> ancestor depends on the specific p1 -> ancestor path

[haughty mountain]

maybe I'm dumb, why are they dependent?

given p1, p2 and ancestor everything is independent I think

[misty perch]

because this isnt 2 separate paths, its 2 halves of 1 path
the 2nd half cannot go over the same nodes the first half has

if the path from p1 to ancestor is p1 -> A -> ancestor, the path from p2 to ancestor cannot be p2 -> A -> ancestor

[haughty mountain]

hmm, for arbitrary ancestors that'll get annoying yeah

what are you actually trying to calculate?

[misty perch]

coefficient of relationship

how much blood 2 individuals in a family share

and coefficient of inbreeding
how likely a random gene is likely to be homozygous

used a lot in animal breeding and a useful measure in genetics generally

its easy to do by hand on the small scale but like.. anything beyond 4 generations rlly needs a calculator

and i made one and it works but its slow when its above like 20 generations (which rlly you dont really need that many generations of history but i just wanted my program to be fast )

its especially slow since this is used a lot for like.. inbred animals, like certain dog breeds

the additional edges makes it more complicated

[sharp arch]

Hi, I have a class that contains all of the instance created. Like this :

class Foo:
  insts = list()
  def __init__(self, ...):
    self.__class__.append(self)```
Does it exist a built-in function name to check if the `insts` list contains an instance (retrieved by an ID) ? 
```py
class Foo:
  ...
  def __contains__(cls, id: int):
    # If `id` is equal to an instance Id then returns True else False```

*Forum post : [#1100854505131753542](/guild/267624335836053506/channel/1100854505131753542/)* **Closed**

[haughty mountain]

isn't ancestor here the closest ancestor?

[misty perch]

nope

its every common ancestor

well

in a normal tree, the common ancestors are also the closest common ancestors

but not when there is uhh.. inbreeding

i can give an example if you want

(kinda afraid to talk about this in detail cuz idk maybe some people find it uncomfortable)

[haughty mountain]

apparently there is a python package for this kind of thing

!pypi pypedal

[halcyon plank]

PyPedal v2.0.3

Tools for pedigree analysis

[misty perch]

there.. is?

huh

well the point of my thing was just to see if i could program something myself (most of my programming is for this reason)

if i ever do need to do calculations with 20 or more generations i will use this package

thanks for telling me about it

[haughty mountain]

maybe digging into the code of that package might point you to something interesting

[misty perch]

how do i check that

oh

[haughty mountain]

apparently this package is a python 2 package, so that's annoying

[misty perch]

yeah its old

anyway its very late for me

i need to sleep

thanks for all your help

😄

[fiery cosmos]

guys, how do i update my VS code library?

i'm trying to import sympy but it says: Import "sympy" cannot be resolved

[sharp arch]

I have a problem with my decorator raising UnboundLocalError
Complete post : #1100921400669257729
Closed thread

[untold oriole]

Pip install

[untold oriole]

Is it local or global variable, I can’t seem to open the link you have provided

[sharp arch]

Closed thread : I have to insert nonlocal foo in my nested function my decorator as scope can't assign and only read inside a nested function ! Thank you anyway !

[fiery cosmos]

how do i verify if a list is out of range?

like i have an array that have 12 elements and i want to check if there is the element 12, considering 0 the start element

[fiery cosmos]

nevermind i found it

okay who here understand regex?

i want to separate numbers from brackets and parentesis here:

pattern = re.compile(r"[\+\-\*\\/]")

i want to allow people to make expressions such as:

8(2d20(10+1d5)/1d6)+25

and also do stuffs such as:
8((20+1d6)/2)

being it either "(" or "["

!e

pattern = re.compile(r"[+-*\/()\[\]]")

expression = 8(2d20(10+1d5)/1d6)+25

args = pattern.split(expression)

print(args)

[halcyon plank]

@fiery cosmos :x: Your 3.11 eval job has completed with return code 1.

001 |   File "/home/main.py", line 3
002 |     expression = 8(2d20(10+1d5)/1d6)+25
003 |                    ^
004 | SyntaxError: invalid decimal literal

[fiery cosmos]

well, i don't know how i do it

strange

[dusky trellis]

what's strange about that?

2d20 is not a number

and that is not a valid expression

[dusky trellis]

I think you want that expression as a string

[lilac cradle]

mainly because the default is already decimal i guess

and also because you don't use a number other than 0 for specifying the type like for hex, bin, oct

[fiery cosmos]

2d20 it's a dice roll

it will be updated after rolling

[dusky trellis]

python doesn't have the concept of dice rolls

[fiery cosmos]

in a number from 1 to 20

[dusky trellis]

you want expression = "8(2d20(10+1d5)/1d6)+25"

[fiery cosmos]

ik, i proggramed one

[lilac cradle]

well it does, but just not that syntax i suppose

[fiery cosmos]

ik, but it's an example of what is about to run in my code

i made funcitons to polish it

[dusky trellis]

well, it won't run as-is

[fiery cosmos]

and ransform it into numbers

[lilac cradle]

you can just use a generic function for all dice, probably

[fiery cosmos]

!paste

[halcyon plank]

Pasting large amounts of code

If your code is too long to fit in a codeblock in Discord, you can paste your code here:
https://paste.pythondiscord.com/

After pasting your code, save it by clicking the floppy disk icon in the top right, or by typing ctrl + S. After doing that, the URL should change. Copy the URL and post it here so others can see it.

[fiery cosmos]

https://paste.pythondiscord.com/ujozajufux

this is the dice funcion

[lilac cradle]

lemme just check if it's even i guess

[fiery cosmos]

check up

i'm using this function in a for funcion

[lilac cradle]

that seems a bit excessive, you can just have an argument for the count and an argument for the number of sides

so you can do roll(2,20) for 2d20

[fiery cosmos]

uhmm, but i would need to re-do all my code

[lilac cradle]

def generate_dice_rolls(count,sides):
    return sum(random.randint(1,sides) for i in range(count))

[fiery cosmos]

yeah but like, i made one to also return the result of each and then the total

so players can calculate if it's matching

[lilac cradle]

you could just do something like ```py
def generate_dice_rolls(count,sides):
rolls = []
for i in range(count):
rolls.append(random.randint(1,sides))
return rolls,sum(rolls)

i tested the evenness of it and it seems mostly fine

{5: 33212, 1: 33009, 3: 33698, 6: 33080, 2: 33452, 4: 33549}
this is the sum of all the results for 200,000 singular d6 rolls

[fiery cosmos]

ik, but i already solved the problem with dices

[lilac cradle]

fair ig

[fiery cosmos]

what i'm trying to do is to separate the string using the operators and the brackets and parentesis

that's what i want

[lilac cradle]

oh that's the hard part, if you figure that out lmk

i want to do something like that for stuff like a graphing calculator that takes an expression and parses it

[fiery cosmos]

!e

pattern = re.compile(r"[+-*\/()\[\]]")

expression = "8(2d20(10+1d5)/1d6)+25"

args = pattern.split(expression)

print(args)

[halcyon plank]

@fiery cosmos :x: Your 3.11 eval job has completed with return code 1.

001 | Traceback (most recent call last):
002 |   File "/home/main.py", line 1, in <module>
003 |     pattern = re.compile(r"[\+\-\*\\/\(\)\\\[\\]]")
004 |               ^^
005 | NameError: name 're' is not defined

[lilac cradle]

you forgot to import re

[fiery cosmos]

!e
import re

pattern = re.compile(r"[+-*\/()\[\]]")

expression = "8(2d20(10+1d5)/1d6)+25"

args = pattern.split(expression)

print(args)

[halcyon plank]

@fiery cosmos :white_check_mark: Your 3.11 eval job has completed with return code 0.

['8(2d20(10+1d5)/1d6)+25']

[fiery cosmos]

okay it seems that it didn't worked the way i wanted it work

it was suppose to be like:
['8','2d20','10','1d5','','1d6','','25']

the empty string will be nescessary to forms the final expression

[cinder rivet]

Does there exist an algorithm that finds this distance between two lists of strings?
ABC,ADC: Expected .33
ABB,AAB: Expected .33
AAA,BBB: Expected 1.0
AAB,BCC: Expected .66
ABC,CDE: Expected .66

[agile sundial]

yes

[cinder rivet]

Thank you.

[cinder rivet]

We are trying to figure it out. Can you give any hints?

[agile sundial]

well, what's the exact specification?

[vocal gorge]

check out e.g. levenstein distance

there's tons of string distances though

[cinder rivet]

We just have to define a distance metric for KNN. Out data is lists of strings so we thought we could find the distance between the lists.

So there's not a strict specification.

[vocal gorge]

You could use e.g. https://pypi.org/project/python-Levenshtein/ if you want a fast implementation, or something from difflib if you prefer it being builtin.

[cinder rivet]

Does edit distance/Levenshtein distance work on unordered groups of objects?

[agile sundial]

not really

[cinder rivet]

hmm

[vocal gorge]

If it's unordered, then you essentially have two multisets

[cinder rivet]

That's a good way to describe it.

[vocal gorge]

Googling a tiny bit: https://arxiv.org/pdf/2206.08858

they investigate a ton of different distances, but one simple one they mention is just

where you could also consider no elements similar to each other, in which case it's just len(a) + len(b) - 2*len(a&b)

[cinder rivet]

Out multisets will all be the same length (100).

[cinder rivet]

By "M is a matching of X and Y", do they mean like a set intersection or is this something different?

[vocal gorge]

They define it as any way to construct min(len(X), len(Y)) pairs of elements from X and Y.

and they need that definition so that they can use distance between elements to define distance between multisets of elements.

[robust dagger]

You may already be aware of this, but in case you're not: It's impossible to check that parentheses are correctly matched using regular expressions alone. It's a good first step to separate the numbers from the brackets and parentheses; this is called lexical analysis or lexing, and it's something regular expressions can do. But the second step, where you figure out what the expression means, is, in a precise sense, a harder problem.

Also: "Some people, when confronted with a problem, think “I know, I'll use regular expressions.” Now they have two problems." – Jamie Zawinski. (http://regex.info/blog/2006-09-15/247)

[naive oak]

it's possible in re tho right?

[subtle depot]

Lottery Sort "We'll tell you tomorrow if it's sorted or not"

[stiff quartz]

Why is a queue.Queue so much longer than a collections.deque

All I find on the internet between the two is if they are the same multi-threading wise and I don't understand anything

Not sure I understand but that should be the reason why?

[naive oak]

they aren't the same multithreading wise

[vocal gorge]

Because queue is a pure-python module (using collections.deque), whereas collections.deque is in C.

[naive oak]

queue.Queue is a wrapper around deque to make it threadsafe

deque itself isn't threadsafe

[ivory yacht]

The Queue as mentioned is designed for multithreading, and has a lot of extra logic and locks to make it behave correctly even if multiple threads are trying to manipulate it simultaneously.

[vocal gorge]

or is it?.. hmm

yup, it looks like there's _queue.c but it only implements SimpleQueue whereas the Queue implementation is always pure-python.

[stiff quartz]

Oh ok

So basically, Queue adds loads of stuff to make it threadsafe

and is therefore not in C

[ivory yacht]

deque is protected by the GIL, and is weakly thread-safe (like all data structures) in the sense that you can't like corrupt it into having a broken state. But it has no protections around popping the wrong thing or whatever.

[stiff quartz]

so if i'm not doing any multithreading i should be perfectly fine?

[stiff quartz]

What is the GIL?

[ivory yacht]

If you're not doing multithreading it's overkill and pointless.

Queue's main additional functionality is the blocking functions. It's designed for when you have multiple threads wanting to insert data into one end, and then more threads extracting the data from the other. If there's no room when they insert, or no items when they try to pop, it'll make the thread wait until that can be completed.

[stiff quartz]

thank you!

[agile sundial]

the docs say deque is threadsafe for appends and pops

!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 "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 "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.

[agile sundial]

but I'm not sure if they're talking about an implementation detail or an actual feature

[fiery cosmos]

is there a python function to cryptograph stuffs?

[haughty mountain]

I'm surprised by that

[haughty mountain]

what kind of cryptographic stuff?

[agile sundial]

yeah same. but I think it's just like how lists are thread safe when just appending

[fiery cosmos]

like a code that only the computer understand, in hexadecimal

neither me knows it

[haughty mountain]

that doesn't say much

[fiery cosmos]

it's because i want to protect users from hackers

[haughty mountain]

if you're after encryption you'll want a separate library

[fiery cosmos]

yes

i need it to protect the users

from hackers

if a hacker steal my code they won't be able to hack the users that used it

[haughty mountain]

what's the current flavor for pycrypto?

pycryptodomex?

[fiery cosmos]

wdym?

[haughty mountain]

but note that encryption isn't some magic you can just sprinkle and things magically work

[fiery cosmos]

i see

[haughty mountain]

there has been a bunch of project named pycrypto-something

I'm not sure which is the recommended one nowadays

!pip pycryptodomex I guess this one

[halcyon plank]

pycryptodomex v3.17

Cryptographic library for Python

[warped tendon]

what is different between arr[0].shape and arr.shape?

[lilac cradle]

if you mean encrypting your code, imo that's kinda pointless

[lilac cradle]

from the syntax alone, arr.shape would get shape of the whole thing, whereas arr[0].shape gets the shape of the first element of arr

[rare nymph]

anyone here good at making indicators for trading view?

[sharp arch]

📂 Opened thread #1101888198747099246
I want to return a custom Timestamp object by using the datetime.fromisoformat method but I can't see why it doesn't work and still asks me for 9 arguments. Workaround solution has been found but I'm not please with it ! Help is appreciated

[haughty mountain]

it would be nice if people read the channel title

[agile sundial]

it's a write only channel, duh

[naive oak]

no appends?

[warped tendon]

import numpy as np
Xs = [
[
[4, 2, -1],
[1, -5, 2],
[2, -1, -4]
],
[
[3, 4, 5],
[-3, 7, -4],
[1, -4, -2]
],
[
[9, -2, 3, 2],
[2, 8, -2, 3],
[-3, 2, 11, -4],
[-2, 3, 2, 10]
]
]
Ys = [
[41, -10, 1],
[34, -32, 62],
[55, -14, 12, -21]
]
how to check diagonal dominant or not if we only get this code in python?

[vocal gorge]

I mean, just check whether the matrix fits the definition:

I don't see how the Xs array is involved, though, it's 3d - unless there's a generalization of diagonal dominance to n-dimensional arrays I don't know about

[warped tendon]

i mean i want to seperate each question like this
the 1th question
4 2 -1
1 -5 2
2 -1 -4
the 2th question
3 4 5
-3 7 -4
1 -4 -2
..

[warped tendon]

do you understand what i mean?

[haughty mountain]

the weirder part is Ys

Xs being a list of matrices makes sense

[solemn flint]

Hello can install sklearn

  Preparing metadata (setup.py) ... error
  error: subprocess-exited-with-error

  × python setup.py egg_info did not run successfully.
  │ exit code: 1
  ╰─> [8 lines of output]
      Traceback (most recent call last):
        File "<string>", line 2, in <module>
        File "<pip-setuptools-caller>", line 34, in <module>
        File "C:\Users\yuvra\AppData\Local\Temp\pip-install-amdp700a\sklearn_17747a87e8b4446dac4d96bf7941a4e1\setup.py", line 10, in <module>
          LONG_DESCRIPTION = f.read()
        File "c:\python\lib\encodings\cp1252.py", line 23, in decode
          return codecs.charmap_decode(input,self.errors,decoding_table)[0]
      UnicodeDecodeError: 'charmap' codec can't decode byte 0x8f in position 7: character maps to <undefined>
      [end of output]
  
  note: This error originates from a subprocess, and is likely not a problem with pip.
error: metadata-generation-failed

× Encountered error while generating package metadata.
╰─> See above for output.

note: This is an issue with the package mentioned above, not pip.
hint: See above for details.
WARNING: You are using pip version 22.0.4; however, version 23.1.2 is available.
You should consider upgrading via the 'c:\python\python.exe -m pip install --upgrade pip' command.

my error log

[haughty mountain]

.

[agile sundial]

write only!

[tired rivet]

[junior rain]

https://www.amazon.ae/gp/product/B0B412LRC6?smid=APXQ3R91YGDQC&psc=1&linkCode=ll1&tag=pcbuildae-21&linkId=169017d3c452cd6896e3a550a6a88348&language=en_AE&ref_=as_li_ss_tl

[warped tendon]

X= [
[4,-1,1],
[4,-8,1],
[-2,1,5]
]
Y=[7,-21,15]
import numpy as np
def gaus(x,y):
x=np.array(x)
y=np.array(y)
diags=np.diag(np.abs(x))
X=x

print(diags)

mat=np.zeros(x[0].shape)
np.fill_diagonal(x,0)
sum=np.sum(np.abs(x),axis=1)
if not np.all(diags>sum):
    return false
for i,a in enumerate(X):
    d=y[a]
    for j,b in enumerate(X):
        if(j != i):
            d-=X[j][i]*mat[i]
    print(mat)
    mat[j]=d/X[j][j]

gaus(X,Y)

why i cannot run this code?

[atomic mauve]

can i set an optional parameter to required later in the function ?

[warped tendon]

yes

[atomic mauve]

by setting i meant making it from optional1 = None to optional1: str

[haughty mountain]

it might break existing code using the function

moving from required to optional is the one that will not affect callers

[worthy kiln]

can someone link me a good data structure video in whatever lang if i had to have a preference rb js or ts

or if there are books

that works too

[solemn flint]

Hello cant download fb prophet with python pip

this is what i get ERROR: Could not build wheels for prophet, which is required to install pyproject.toml-based projects

Can someone help me

[rigid holly]

Anyone here. Please help with Alpha Beta pruning Algorithm

[magic lodge]

this is the error from pip, can you paste in the error that comes before it (should say something about a subprocess)

[upper tangle]

Does anyone understand Weighted Interval Scheduling? I really need some help with it overall

[proud otter]

A dictionary has keys that are integers and arrays (lists) as values. Since I don't know whether or not the key 2 has a corresponding value, how do I add a value to key 2's array?

[vocal gorge]

You'd usually do something like dct.setdefault(key, []).append(value). Or use a collections.defaultdict which does a setdefault automatically on each access.

[raven badge]

can i ask a doubt in here??

[lean walrus]

https://nometa.xyz/

[raven badge]

Just new in here so figuring out everthing

[proud otter]

Thanks! that's litterally the exact thing I was looking for!

[haughty mountain]

another point to add to that, if I engage with a non-question it feels like I'm obliged to try to answer the question since I asked for the question

[solemn flint]

yep subprocess error

[haughty mountain]

it doesn't actually do setdefault right?

[haughty mountain]

seems it doesn't

In [1]: from collections import defaultdict

In [2]: def default():
   ...:     print('default')
   ...:     return []
   ...:

In [3]: D = {}

In [4]: D.setdefault(42, default())
default
Out[4]: []

In [5]: D.setdefault(42, default())
default
Out[5]: []

In [6]: D = defaultdict(default)

In [7]: D[42]
default
Out[7]: []

In [8]: D[42]
Out[8]: []

[lean walrus]

defaultdict uses __missing__

[haughty mountain]

the constraint you're given is that the graph is bipartite

(+ the degree of 3 thing)

maybe that's helpful

[outer rain]

I think you can add three more round vertices, call them A, B and C, and connect them to a single square vertex. That way you can't get rid of any of those three. Then for each variable X and corresponding round vertex, add a square vertex and connect it to A, B, X, and not X. You can then force k = num of vars. You can't remove A, B or C, and you can't remove X and not X at the same time because it will leave only two edges at the corresponding square vertex. And since you are forced to remove exactly k vertices, you have to remove either X or not X for each variable. And then add your reduction for clauses to that structure. Perhaps this may work, but it depends on how you reduced the clauses.

I don't get the deg >= 3 constraint though, isn't >= 2 enough?

[outer rain]

Seems like it.

wait for each literal? You mean 4 round vertices per variable?

oh ok, got it

Variables are "letters", literals refer to either "letter" or not letter

So clauses are build from literals

and literals are either variable or not variable (negation of variable that is)

yes

don't worry, I get what you mean now

[prisma sigil]

Hi, could I ask in this channel, please? I was wondering if you can recommend good exercises for scipy, numpy, matplotlib including algorithm development?

[vocal gorge]

https://www.labri.fr/perso/nrougier/from-python-to-numpy/ comes to mind

[lost lily]

i have barely any interest in numpy, but this looks really cool, thanks for the link!

[wooden venture]

who is the failure now

[rigid holly]

Hello everyone. I need someone to help me develop an Intelligent system using Alpha Beta pruning Algorithm. I have been trying for the last four days but nothing happens. Your help will be highly appreciated.

[fiery cosmos]

do anyone is experient with postgresql?

i need help on this

please DM me

[keen hearth]

You'll have more luck asking in #databases

[agile sundial]

we should have a channel on top of this channel

[fiery cosmos]

Search Create programm voice clone come private thanks

[haughty mountain]

a read only channel with only instructions to please post in the relevant help topic

[tiny jay]

just reorder and put #esoteric-python first 😈

[sullen lily]

p

[spring stag]

hi, I try to make a binary tree in python for my university, I really need help cause I have to deliver it in 2 hours. Anyone can help me please 🙏 🙏

[agile sundial]

what have you tried so far

[spring stag]

here is my code

https://paste.pythondiscord.com/aseqakaveh

the problem is when I execute the script I should have as result 2.3333 and I actually have 2

[spring stag]

there is probably a mistake in the script but I have not yet found it I ever tried to use chat gpt to help me but there is no result. could you please help me ?

[fiery cosmos]

what's the best way to learn graph problems in python

any algos that are feasible to qualify as puzzle programs (<1 hr of coding or less)

sry if this sounds trite or something

minimaxing my practice time

[vocal gorge]

bfs and dfs can be written in a few minutes each if you're familiar with them, and probably <1h even if you aren't. Then dijkstra. A* is a bit more complicated than dijkstra but pretty similar.

If you want practice problems, perhaps look at low-kyu codewars katas with the Graph Problems tag: https://www.codewars.com/kata/search/python?q=&r[]=-8&r[]=-7&r[]=-6&tags=Graph+Theory&beta=false&order_by=total_completed+desc

[haughty mountain]

and all are following the exact same mold

with minor variations

stack → dfs
queue → bfs
priority queue → Dijkstra
priority queue + heuristic → A*

[magic lodge]

a lot of the sorting algorithms are perfect for this! you can write a lot of the basic ones in a single line: ```python
from itertools import islice, repeat, starmap, dropwhile
from random import shuffle, sample
binradixsort=lambda l:([(le:=[],ri:=[],[(ri if(1<<b)&i else le).append(i)for i in l],l:=le+ri)for b in range(max(l).bit_length())],l)[1]
bogosort=lambda l:next(dropwhile(lambda l:not all(starmap(operator.le,zip(l,islice(l,1,None)))),map(lambda x:sample(x,len(x)),repeat(l))))
bubblesort=lambda l:[[[l.insert(i,l.pop(i+1))if(l[i]>l[i+1])else () for i in range(len(l)-1)] for _ in range(len(l)**2)], l[:]][1]
cocktailsort=lambda l:[[[l.insert(i,l.pop(i+1))if(l[i]>l[i+1])else l.insert(r,l.pop(r-1))if(l[r]<l[r-1])else()for i,r in zip(range(len(l)-1), range(len(l)-1,0,-1))]for _ in range(len(l)**2)],l[:]][1]

most of them are some variation of keep going over the list and swapping adjacent elements until it's sorted but the variants like cocktailsort are pretty fun to do as well

I just went through this list and found the more simple ones: https://rosettacode.org/wiki/Category:Sorting_Algorithms

if you wanted a harder challenge then try implementing binary finite field arithmetic, or one of the algorithms to generate many digits of pi

gausse-legendre is a really good one, as it performs quite well and is short

but you have to deal with decimals and stuff like that so its fun

[magic lodge]

also this is probably better for #esoteric-python but theres also a website called https://code.golf that has a bunch of nice challenge problems along with test cases and basic dev environment

if you ignore the whole "min number of chars" part then its a great list

[haughty mountain]

or you can write an actual nice looking algo in just a few more lines 😅

or some even in one line

qs = lambda l: l if len(l) <= 1 else qs([x for x in l[1:] if x < l[0]]) + [l[0]] + qs([x for x in l[1:] if x >= l[0]])

not a PEP8 compliant line sadly

[naive oak]

tbf you can just do def instead of lambda

[haughty mountain]

but it's so long 😭

qs = lambda l: l if len(l) <= 1 else qs([x for x in l[1:] if x < l[0]]) + [l[0]] + qs([x for x in l[1:] if x >= l[0]])
def qs(l): return l if len(l) <= 1 else qs([x for x in l[1:] if x < l[0]]) + [l[0]] + qs([x for x in l[1:] if x >= l[0]])

(and it's totally not to match the lambda stuff that was in the code I replied to)

[fast galleon]

Hello , it's newbie struggle. I felt like completely lost in learning DSA. I felt depressed while I can't think about solutions for even basic things like recursion , tree , etc. Do you guys also had similar experiences and how did you manage to escape it? Most of recommendations will be to practice. I tried Codewars , LeetCode , but can solve easy problems but being stuck in medium (never able to touch Advanced). May I also know any suggestions for the study plan to practice ?

[magic lodge]

hahahaha that’s true but where’s the fun in that? hahah

also if you use black on them, it ends up not looking nearly as bad: ```python
cocktailsort = lambda l: [
[
[
l.insert(i, l.pop(i + 1))
if (l[i] > l[i + 1])
else l.insert(r, l.pop(r - 1))
if (l[r] < l[r - 1])
else ()
for i, r in zip(range(len(l) - 1), range(len(l) - 1, 0, -1))
]
for _ in range(len(l) ** 2)
],
l[:],
][1]

[runic tinsel]

read the solutions

[magic lodge]

most people have to practice for quite a while to be able to solve hard leetcodes to be fair. the best way to study it is imo just finding a problem you want to solve first (like for another hobby), and then researching the best algorithms to do that, and then trying to implement those. it's a slog, but if you make the subject matter interesting to you it becomes easier

[haughty mountain]

that looks O(n^3)

which is...pretty terrible

actually, maybe it's even worse

O(n^4)?

arbitrary inserts and pops inside an O(n) loop inside an O(n^2) loop

sure sounds like O(n^4)

rather than the O(n^2) that cocktail sort should be

[magic lodge]

they are clearly not written for speed hahah

it’s O(1) in code size

[haughty mountain]

meanwhile my thing is an actual quicksort with the expected time complexity 😅

[magic lodge]

I absolutely appreciate super efficient implementations, I implemented a branchless binary search that beats the stdlib recently: https://github.com/juliusgeo/branchless_bisect. the purpose of the sorting algorithms I posted was to show that it can be both fun and educational to try to implement the basic sorting algorithms with constraints

for me though, I think it can be fun to both focus on short size if you want to really understand an algorithm

[agile sundial]

branchless binary search sounds interesting

[magic lodge]

yeah it's from that article on HN

i adapted it to a C-extension though

so it beats the bisect.bisect_left func

it technically is only branchless if your compiler compiles it to a CMOVE though

the original article has a lot of info about the implementation: https://probablydance.com/2023/04/27/beautiful-branchless-binary-search/

also I would highly recommend all the other articles on this blog

[agile sundial]

that's very cool

[fiery cosmos]

Hello

Create voice clone come

[magic lodge]

haha to be fair I didn't really invent anything new, I just ported it to Python. But I appreciate it

[naive oak]

how do you do unary operations with shunting yard?

[haughty mountain]

you can often do short and "performance correct"

selection sort

[l.pop(l.index(min(l))) for _ in [0]*len(l)]

[magic lodge]

that’s not the same sorting algorithm tho. it’s possible to do short and performance, but much harder to do short and performance (expressions only edition )

[magic lodge]

for example while loops are the simplest way to write a lot of these algorithms, but those are super annoying to do in the context of list comps so I just make it iterate the max number of times it theoretically could need

also imo using min in the main loop of a sorting algorithm means you're just deferring the hard part of the sorting to stdlib, which obviously will be much faster than if you implemented it without using sorting related builtins

also because we're talking about performance I did some benchmarking and once the array is larger than like 1000 elements, my first sorting algorithm easily beats yours: for idx, func in enumerate( [binradixsort, selsort] ):

0 took 0.1459877920569852 seconds to sort
1 took 0.5075588340405375 seconds to sort

that's at 10k elems, the gap is even more stark once you get to 100k:

0 took 0.9977649580687284 seconds to sort
1 took 56.34158737503458 seconds to sort

my point is that theoretical runtime performance is useful, but in the real world it matters much more the specifics of your implementation (bitwise ops are cheaper than divising by 2, etc)

[stray fractal]

what if you add proper error checking

[magic lodge]

where would I be adding error checking? it's using python c bindings functions which would throw a python exception themselves

i'm pretty sure

[stray fractal]

PyObject_RichCompareBool

it returns a negative value on error

[magic lodge]

that's what it returns, but wouldn't it also trigger an exception in the interpreter?

[stray fractal]

also you can use PyList_GET_ITEM() instead of PyList_GetItem()

[stray fractal]

yes but ```c
for (step >>= 1; step != 0; step >>=1) {
if ((next = begin + step) < size) {
begin += PyObject_RichCompareBool(PyList_GetItem(list_obj, next), value, compare) * step;
}
}

[magic lodge]

hmm let me test that

[stray fractal]

doesn't matter anyway it'll still have step until 0

[stray fractal]

might be able to optimize it with this ^^

[magic lodge]

also just to put the nail in the coffin of this silly discussion, but I graphed the performance of your impl vs two of mine vs the stdlib, and...

[stray fractal]

PyList_Size -> PyList_GET_SIZE

[stray fractal]

i'm gonna make the functions a tad bit faster

[magic lodge]

wait I found this in the PEP: int PyObject_RichCompareBool(PyObject *, PyObject *, int) This performs the requested rich comparison, returning a Boolean: -1 for exception, 0 for false, 1 for true. The 3rd argument must be one of Py_LT, Py_LE, Py_EQ, Py_NE, Py_GT or Py_GE. Note that when PyObject_RichCompare() returns a non-Boolean object, PyObject_RichCompareBool() will raise an exception.

This seems to imply that it will raise an exception in the interpreter on error, while also returning -1. So hopefully I would just need to check for -1 and break

[boreal sedge]

Hello! I have a question how to skip iteration inside a generator? Thank you in advance

[magic lodge]

if you mean you want to skip the iteration on the side consuming the generator, you can just yield None

if the iteration is inside the generator you can just use continue as you normally would, and then yield the next element

[stray fractal]

ok @magic lodge i'm about to compare your branchless bisect vs an optimized version

do u have benchmark sets

[magic lodge]

yeah wait give me one sec, I just did a few of the optimizations you mentioned

the benchmarks are in benchmark.py you can just modify the sizes variable to change where its sample at

will also need to change which things are being plotted because by default it also plots the python versions

[stray fractal]

ok

[magic lodge]

before optimizations

after

[stray fractal]

i'm having segfault issues wait

resolved

[stray fractal]

ok results are back for me

[magic lodge]

oh yeah that's a better way to compare lol

nice! you can open a PR if you want, or I can also just add the changes myself

[stray fractal]

ok benchmarking with sizes up to 2**100 almost crashed my pc
maybe that was a bad idea

[stray fractal]

i do think the code optimizations are pretty compiler dependent

[magic lodge]

lol to be fair I have never tried that high--2**29 takes like a few minutes to run for me

[stray fractal]

i added more stuff than just using macros

[haughty mountain]

no way that cocktail beats a sensible radix sort

[magic lodge]

yeah real world performance is often not what you expect at all. hence why I posted benchmarks.

especially in an interpreted language like Python haha

[stray fractal]

should i add new functions or modify the existing ones?

[magic lodge]

probs just modify the existing ones--I'll update the benchmark images once it's merged

[stray fractal]

ok

[stray fractal]

juliusgeo/branchless_bisect#1

[grand haven]

GitHub

[branchless_bisect] #1 faster bisect

[magic lodge]

nice!!!

[bold marten]

Hello , I am new to this discord srv and my english is bad so I dont know where to put this question but here it is :
This is a 3d modelisation of a pingpong table , the blue is a surface and the green is the net. I want to put the green part on the forground , and the blue surface on the background but I don't how to do it . Does anyone know ?

[raven mirage]

Want to collaborate dsa for array,linkedlist, stack , queue, tree in python. We can do online collaborations for problem solving

[haughty mountain]

I'm confused about your benchmarks, I get nothing even close to that. I just did one size for now, but the pattern is clear:

Running for 10 samples of size 200

Algorithm            Time
selection_sort       0.000212s
cocktailsort         0.648962s
bubblesort           0.448048s
binradixsort         0.000096s
quicksort            0.000186s

[magic lodge]

You're not getting the same result because you're comparing one size of list, and presumably not a large one based on the times

[haughty mountain]

from itertools import islice, repeat, starmap, dropwhile
from random import shuffle, sample, seed
from time import perf_counter

selection_sort = lambda l: [l.pop(l.index(min(l))) for _ in [0]*len(l)]
qs = lambda l: l if len(l) <= 1 else qs([x for x in l[1:] if x < l[0]]) + [l[0]] + qs([x for x in l[1:] if x >= l[0]])

binradixsort=lambda l:([(le:=[],ri:=[],[(ri if(1<<b)&i else le).append(i)for i in l],l:=le+ri)for b in range(max(l).bit_length())],l)[1]
#bogosort=lambda l:next(dropwhile(lambda l:not all(starmap(operator.le,zip(l,islice(l,1,None)))),map(lambda x:sample(x,len(x)),repeat(l))))
bubblesort=lambda l:[[[l.insert(i,l.pop(i+1))if(l[i]>l[i+1])else () for i in range(len(l)-1)] for _ in range(len(l)**2)], l[:]][1]
cocktailsort=lambda l:[[[l.insert(i,l.pop(i+1))if(l[i]>l[i+1])else l.insert(r,l.pop(r-1))if(l[r]<l[r-1])else()for i,r in zip(range(len(l)-1), range(len(l)-1,0,-1))]for _ in range(len(l)**2)],l[:]][1]

def timeit(name, func, n_size, n_samples):
    # generate lists
    seed(42)
    lists = [list(range(n_size)) for _ in range(n_samples)]
    for l in lists:
        shuffle(l)

    start = perf_counter()
    for lst in lists:
        func(lst)
    end = perf_counter()
    avg = (end - start) / n_samples
    print(f'{name:<20} {avg:.6f}s')

n_size = 200
n_samples = 10

print(f'Running for {n_samples} samples of size {n_size}')
print()
print(f'{"Algorithm":<20} {"Time":<10}')

for name, func in [
    ("selection_sort", selection_sort),
    ("cocktailsort", cocktailsort),
    ("bubblesort", bubblesort),
    ("binradixsort", binradixsort),
    ("quicksort", qs),
]:
    timeit(name, func, n_size, n_samples)

[magic lodge]

why didn't you just import timeit.timeit?

[haughty mountain]

I mean I see cocktailsort skyrocket in time

as input grows

[magic lodge]

Graph please?

It's really pointless to compare a graph to you plugging in a bunch of sizes

[stray fractal]

i'm gonna go use julius's benchmark script

[magic lodge]

tests = [(binradixsort, times_radix), (selsort, times_stackless),  (sorted, times_native), (cocktailsort, times_cock)]
num_trials = 5
from random import shuffle
for size in sizes:
    #a function that takes a size and creates a list with elements that are random strings
    test_arr=list(range(size))
    shuffle(test_arr)
    for func, times_arr in tests:
        times_arr.append(timeit(lambda:func(test_arr), number=num_trials))
        assert (out:=func(test_arr)) == sorted(test_arr), f"{func.__name__} failed to sort {test_arr},\n instead produced: {out}"

plt.plot(sizes, times_native, label="native")
plt.plot(sizes, times_stackless, label="selsort")
plt.plot(sizes, times_radix, label="radix")
plt.plot(sizes, times_cock, label="cocktail")

imports are left as an exercise to the reader

sizes = list(range(100, size:=10**5, size//10))

[haughty mountain]

it's not really, see how huge the difference between cocktailsort and others are

[magic lodge]

are you genuinely arguing that you can compare single points of data to a graph showing the trend over many sizes?

because if you're trolling me that's fine

single points are basically only used to identify regressions across commits, characterizing runtime is inherently asymptotic

[haughty mountain]

no, if I see a huge discrepency that I don't see in your graph that is a red flag

I can't really generate graphs atm

[magic lodge]

but you haven't tried it with the same values

[haughty mountain]

on my phone

[magic lodge]

well I literally just copy pasted your implementation you posted earlier

this is the same benchmarking code I've used for other projects as well, so I'm pretty confident it's right

like try comparing the speeds for a list of size 10**5

[vocal gorge]

trying to make a plot, but having trouble running binradixsort

seems to get ValueError: max() arg is an empty sequence on some inputs

[stray fractal]

case for 0 elements isn't handled

[vocal gorge]

i'll just exlude it

[magic lodge]

oh I was getting that error I forget how I fixed it

[stray fractal]

fixed

[magic lodge]

I tried your benchmarking code with just 10**3 and it shows a gap:

Algorithm            Time      
selection_sort       0.008451s
binradixsort         0.001560s
quicksort            0.000909s

[stray fractal]

i'm gonna get larger input wait

[magic lodge]

this will be super useful to find the fastest algorithm for sorting my 16 favorite foods in order of mold quantity

[haughty mountain]

the cocktailsort basically doesn't terminate for me

for n=1000

[stray fractal]

@haughty mountain their graph is real

i'm getting the same results

[haughty mountain]

try my code with a few sizes?

[stray fractal]

i'm gonna remove selection sort

[haughty mountain]

or does my code have some fatal flaw?

I just do the dumbest perf counter elapsed time measurement

columns are n=10, n=100, n=1000

Algorithm            Time
selection_sort        0.000006s  0.000063s  0.004750s
cocktailsort          0.000119s  0.081092s 108.320311s
bubblesort            0.000079s  0.051480s 69.660311s
binradixsort          0.000014s  0.000058s  0.000569s
quicksort             0.000012s  0.000085s  0.001149s

[stray fractal]

cocktail sort is hanging somewhere

[haughty mountain]

no

it terminates

let me post my slightly modified code

from itertools import islice, repeat, starmap, dropwhile
from random import shuffle, sample, seed
from time import perf_counter

selection_sort = lambda l: [l.pop(l.index(min(l))) for _ in [0]*len(l)]
qs = lambda l: l if len(l) <= 1 else qs([x for x in l[1:] if x < l[0]]) + [l[0]] + qs([x for x in l[1:] if x >= l[0]])

binradixsort=lambda l:([(le:=[],ri:=[],[(ri if(1<<b)&i else le).append(i)for i in l],l:=le+ri)for b in range(max(l).bit_length())],l)[1]
#bogosort=lambda l:next(dropwhile(lambda l:not all(starmap(operator.le,zip(l,islice(l,1,None)))),map(lambda x:sample(x,len(x)),repeat(l))))
bubblesort=lambda l:[[[l.insert(i,l.pop(i+1))if(l[i]>l[i+1])else () for i in range(len(l)-1)] for _ in range(len(l)**2)], l[:]][1]
cocktailsort=lambda l:[[[l.insert(i,l.pop(i+1))if(l[i]>l[i+1])else l.insert(r,l.pop(r-1))if(l[r]<l[r-1])else()for i,r in zip(range(len(l)-1), range(len(l)-1,0,-1))]for _ in range(len(l)**2)],l[:]][1]

def timeit(func, n_size, n_samples):
    # generate lists
    seed(42)
    lists = [list(range(n_size)) for _ in range(n_samples)]
    for l in lists:
        shuffle(l)

    start = perf_counter()
    for lst in lists:
        func(lst)
    end = perf_counter()
    avg = (end - start) / n_samples
    return avg

print(f'{"Algorithm":<20} {"Time":<10}')

for name, func in [
    ("selection_sort", selection_sort),
    ("cocktailsort", cocktailsort),
    ("bubblesort", bubblesort),
    ("binradixsort", binradixsort),
    ("quicksort", qs),
]:
    times = []
    for n_size in (10, 100, 1000):
        n_samples = 1
        times.append(timeit(func, n_size, n_samples))
    fmt_times = [f'{t:9.6f}s' for t in times]
    print(f'{name:<20}', *fmt_times)

wait, you're sorting sorted lists?

[stray fractal]

?

[magic lodge]

it gets shuffled

[stray fractal]

i'm sorting choices(range(size), k=size)

[haughty mountain]

nvm

misread

let me read the code proper

[vocal gorge]

perfplot's plot looks horrible, but shows about n^3 time of cocktail and bubblesort

[stray fractal]

still wondering when my benchmark will finish

[vocal gorge]

I did this:

import perfplot, numpy as np
import random
def wrapper(f):
    return lambda l: f(l.copy())
res = perfplot.bench(
    kernels=[wrapper(x) for x in [selection_sort, qs, bubblesort, cocktailsort]],
    n_range=np.unique(np.round(np.geomspace(30, 200, 10)).astype(int)).tolist(),
    setup=lambda n: [random.randrange(10000) for _ in range(n)],
    labels="selection_sort, qs, bubblesort, cocktailsort".split(", "),
    target_time_per_measurement=1,
    equality_check=None,
)

[stray fractal]

ok i will just give up on benchmarking

it's still on cocktail sort

[magic lodge]

you gotta make each list a lot longer haha

the x axis should be up to 100k at least to be comparable to my plot

[haughty mountain]

oh wait

[magic lodge]

asymptotic performance estimates need to have at least like several different orders of magnitude

[haughty mountain]

my selection sort destroys the input

so anything after that is broken in your code

I always pass a fresh array

[magic lodge]

ohhh lol that makes sense

you can just do l[:]

[haughty mountain]

so your cocktail sort ran on an empty list

no wonder it's fast

[magic lodge]

wait but my implementation doesn't destroy the input

[vocal gorge]

well, your plot is broken; getting cocktail to work on 100k elements once would take about 3.9 years

[haughty mountain]

the code runs the functions in sequence

[magic lodge]

you can exclude cocktailsort....

[haughty mountain]

selection sort runs early

[agile sundial]

that's not really the point

[magic lodge]

my point is that my plots with 100k elements used binradix sort as well, you can use that to compare

[haughty mountain]

so yeah, change your code to run on a copy

[magic lodge]

I could also just post the entire benchmark file but that would clutter the chat

but I will do that

[agile sundial]

but none of your plots are accurate anymore

[haughty mountain]

and then we should get comparable numbers

[magic lodge]

yeah but that isn't an argument to use fewer elements, I'll just fix the graphs

I'm just saying at the very least, if you're going to compare your graph to my graph, they should have the same limits roughly

from there we can ask about whether the graphs are right

or wrong

but we have to be comparing apples

[haughty mountain]

you won't be able to run the quadratic ones for more than like 10000

the cocktail sort even less so

(run as in complete in a sensible timeframe)

[magic lodge]

that completely depends on what computer haha

obviously on your phone or whatever server it's getting run on would be super slow

I'm running the benchmarks on my m1

[haughty mountain]

no, time complexities tell a story

your cocktail sort is O(n³) or maybe even O(n⁴)

[magic lodge]

time complexity and time it takes to complete a benchmark run aren't the same haha

yeah my cocktail sort is garbage, I've been excluding it on all the graphs

the original point in this whole thread was that you said your selsort implementation had good time complexity

[vocal gorge]

That's true - if your computer is a hundred times better than mine, it'll only take you two weeks.

[haughty mountain]

"good" meaning quadratic

[magic lodge]

I'm not sure how my computer has to do with excluding the garbage cocktailsort implementation I had

[vocal gorge]

bubblesort too

[magic lodge]

ok, well that is fair. you seemed to be saying that it was significantly faster than all of my implementations

[vocal gorge]

if you exclude both of them, then sure, a plot up to 10^5 is obtainable

[magic lodge]

that is assumed considering they're the same exact implementation

[magic lodge]

that's exactly what I did in my graph. did you read the legend? it has helpful labels

[haughty mountain]

looking at my benchmarks yes it is

[vocal gorge]

...which?

[haughty mountain]

this

n=10 100 and 1000

[magic lodge]

yeah you used up to size 1000, that's super small

again, you have to compare apples to apples

[haughty mountain]

look at the times

[agile sundial]

because it would take years to finish at 100000 🥴

[magic lodge]

I know what the times are, I'm saying you need to time larger lists

[haughty mountain]

I kinda can't

[magic lodge]

yes, as I have said like I think 3 times at this point, the cocktail and bubblesorts are broken as hell

[haughty mountain]

your bubblesort takes more than a minute for n=1000

[vocal gorge]

Unless you mean the branchless vs normal bisect one, I don't see a plot of yours which excludes cocktailsort

[magic lodge]

I think I hallucinated it. My bad

Ok here's the benchmark with new arrays for each func:

    for func, times_arr in tests:
        test_arr=list(range(size))
        shuffle(test_arr)
        times_arr.append(timeit(lambda:func(test_arr), number=num_trials))```

[vocal gorge]

I'd suggest plotting it in loglog axes to estimate the complexity easily

[haughty mountain]

yes, selsort is terrible compared to good sorting algos

[magic lodge]

like the ones that I posted earlier haha?

[haughty mountain]

try bubble vs cocktail vs selsort with the fix

[magic lodge]

I would also have to fix my garbage impl and I'm about to sleep haha

I'm running the log log one now

Should have used a notebook :/

for the beavers in the chat:

(get it log log)

[vocal gorge]

My plot finished. Selsort is almost exactly ∼n² here, qs is a bit more than linear (makes sense, n log n)

[haughty mountain]

now try the sel, bubble and cocktail for not too large inputs

with the impls from earlier

[vocal gorge]

I've done that earlier ^

[haughty mountain]

I think they are n², n³ and n⁴

[magic lodge]

ok those impls are broken though

[vocal gorge]

the plot looks like n^3 for bubble and cocktail

[magic lodge]

please compare to binradix

[haughty mountain]

of course binradix is fine

it's an ok impl of a good algo

the selection sort is a terrible algo, but implemented with the correct complexity

[magic lodge]

ok well this whole thing started because you said that all my impls were super bad time complexity, then you posted your own algorithm, and it is clearly slower than my fastest impl

[agile sundial]

my interpretation was that the original disagreement was not about comparing across algorithms. rather, that your algorithms could be implemented better while still retaining the one-lineness

[magic lodge]

my bad impls are obviously pretty bad but that wasn't the discussion

[magic lodge]

based on this comment, and the following comment where they posted their selsort implementation

[haughty mountain]

when I said performance correct I meant that it has the complexity expected for that algo

[magic lodge]

then wouldn't the answer be to post the same algorithm, but better? not a completely different algorithm haha

[magic lodge]

then why post selsort?

[agile sundial]

it's just an example

[magic lodge]

an example of what?

[haughty mountain]

it's an example of an O(n²) algo whose implementation is actually O(n²)

[magic lodge]

how does that help me refactor mine though

like it's super cool, but that doesn't tell me how I could improve my own algorithms

if the comment was "you could do these better", and not "my algorithm is better than yours" then I would normally expect to see something related to refactoring

but I'm glad I got to practice benchmarking stuff haha

this was a good discussion

[haughty mountain]

my point was just that you're impls are not the expected complexity for the algo, but that you can write the expected complexity for some sorting algos pretty easily

[magic lodge]

besides the broken ones though, which ones aren't the expected complexity?

[haughty mountain]

no advice for how to turn yours into the expected complexity, I suspect it might be near impossible in one expression

[magic lodge]

that's fair haha

[haughty mountain]

wdym besides the broken ones? it's bubble and cocktail I complained about 😛

I haven't read the radix sort closely, it's possible that one is perfectly fine

[magic lodge]

the ones with the double for loops that iterated len(l)**len(l) times?

hahaha

[fiery cosmos]

Hey,

This message doesn't really fit here.

If you have a question regarding a program you're working on & having trouble with, please open a help thread.

You can refer to #❓｜how-to-get-help for that.

[granite vortex]

im doing some error catching for some urls, is this inefficient?

[limber tendon]

@granite vortex ```py
try:
...
except (ExceptionType1, ExceptionType2):
# handle the exceptions
...

[granite vortex]

thanks

[magic lodge]

also if you want these errors to be retried, the prints are good, but if you just want to put a wrapper with more info about the exception, you can use raise ... from exc:

try:
  ...
except (Exc1, Exc2) as exc:
  raise Exception("Oops: something else") from exc

this will make the user able to see the stack from the root exception

[cunning bison]

Not super python but this is completely wrong right?

ADTs don’t actually hide anything

[agile sundial]

it's a strange way to say encapsulation and abstraction

[agile sundial]

but basically, they do kind of

[cunning bison]

Im 95% sure he believes that the implementation is like

encrypted or something

[agile sundial]

if all you know is that some object implements an ADT (a Protocol in python), then you don't know anything about how it's implemented

[cunning bison]

Wait what

Yeah of course

[agile sundial]

so they hide the implementation

[cunning bison]

if thats all you know about it

but if you have the library you can look at it

[agile sundial]

but hiding is like, not the "right" term. you would say encapsulation and abstraction

[cunning bison]

Because its not actually hidden, right?

[agile sundial]

yes, you can look at all the implementations you might use, but your code will not know exactly which one it is at runtime

[cunning bison]

Wait what why not?

[agile sundial]

conceptually it is. but the strength of Protocols is that your code will work the same regardless of the concrete implementation, because you design it around the abstract contract

[opal oriole]

Seems like a very complicated way of saying that you are doing polymorphism.

Single interface, multiples types.

[agile sundial]

yeah, ADTs are a way to do polymorphism

in python, Protocols

[cunning bison]

Yeah thats not what hes saying

[agile sundial]

that's what the slide says 🤷‍♂️

[cunning bison]

Hes saying "you can change the implementation and nobody will ever know" or "they will have no idea how you actually implemented it because its private"

[cunning bison]

Thats what the 2nd and 3rd say.

The first one says that it "hides how it is implemented" which is just not true.

[agile sundial]

it is true though

[haughty mountain]

it's hide in the sense of "doesn't expose the internal implementation"

[opal oriole]

Hides comes from languages like Java preferring that all the members be private, in addition to the user not needing to reading the source code to use it.

[cunning bison]

But fundamentally you could

[opal oriole]

If I make a function called add, that adds the two arguments you give it, you don't need to read its implementation to use it.

[cunning bison]

which means there is no benefit to security

[opal oriole]

Yes, and often you do need to.

(Because details often matter)

But sometimes they don't. And it's really nice to not have to care.

[haughty mountain]

if you need to dig into the internals from the outside the interface is probably broken

[opal oriole]

*Or optimize.

You can think of the goal being to make this new layer with which you actually program your end goal.

[haughty mountain]

one big advantage of hiding the internals allows you to do changes internally without breaking users code

keep the interface the same, change the internals

[opal oriole]

For example I could write some loops for manually doing matrix multiplication, or I could make a function for it, and use that function everywhere. Now i'm thinking in terms of matrix multiplications rather than the underlying loops.

And someone could optimize that multiply function, and I don't have to change the rest of the code (usually).

[haughty mountain]

yeah

you expose some interface/public api

and give some guarantees

but everything else could change, and the users shouldn't notice

(in a perfect world)

in reality subtle implementation details can leak

[opal oriole]

This is where the art of good API design comes in.

[haughty mountain]

well

take something simple like my hash table happening to have a consistent iterations order

it's nothing that I guarantee, but this detail leaks

and people might start depending on it

which causes grief if you try to then do a change that changes that order in some way

[agile sundial]

hmm, sounds familiar

[opal oriole]

There are times when you want hard boundaries to prevent people from touching things they shouldn't. Not because they don't understand the code, but because of communication of intent.

The original author may want to have changed it later.

With ADTs the author is saying "let me change things on the back side without breaking your side."

[haughty mountain]

at work they started randomizing iteration order of hash maps to see what tests broke

they found a good deal of them

[slate seal]

Is there a simple way of changing the iteration order of dicts across a code base?