algos-and-data-structs

[forest tundra]

why is np.array([1,2,3]).shape [3,] instead of [3]?

[agile sundial]

well it's a tuple

[fiery cosmos]

sais-tu pourquoi ils me disent que ce n'est pas appelable ?

la fin ;
def attack_player(self, target_player):
if self.weapon is not None:
self.attack += self.weapon.get_damage_amount()
target_player.damage(self.attack)

def has_weapon(self, weapon):
    self.weapon = weapon()

Mon but est d'inscrire l'objet "a une arme"/"n'en a pas" pour faire + ou moins de dégats
ps: je ne cache pas que les noms choisis sont personnels haha

j'ai rééssayé et je comprends beaucoup plus, cependant je ne m'étais jamais trouvé devant cette erreur

[rose glacier]

et si tu enlèves les parenthèses après weapon ? juste self.weapon = weapon

we should probably speak English in here tho

[rose glacier]

Guys, help. I have a dataframe that looks like this. I would like to transform it so that each 'acteurRef' gets a line. How do I do it? (the dict has only one key, 'votant', and each item of the list ist a dict with three keys, let's say it's pretty convoluted data)

[fiery cosmos]

okay, sorry

oh, the parenthésis mean that there's not only one weapon, because here there is knife, but there will be also a gun maybe or other things

I think it is because we don't have a function for weapon, i will try to resolve it

No, I have this is... weird

wow you're so amazing @rose glacier, you were right : only parenthésis and it's works, but they deducte that thisi is knife, so i have to differenciate every weapon, cause i'd like to have a lot of weapons

ho no, it is e who don't remenber good what i wrote haha, it works really, thanks beautiful girl (or no i don't care just thx)

it is me*

[vagrant perch]

is it normal that ive been reading and learning about linked lists and still cannot comprehend how the dummy node gets updating in python when merging the lists in order?

because tail.next shouldnt impact dummy as its its own variable after changing

        dummy = ListNode()
        tail = dummy

        while list1 and list2:
            if list1.val < list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next
        if list1:
            tail.next = list1
        elif list2:
            tail.next = list2
        return dummy.next

returning dummy.next should return ListNode().next, and that object has never been changed so ought to return None

tail, its own reference to dummy, gets updatewd and should become a new object no ?

[thin yoke]

does anybody works with discrete event simulations

[uneven vine]

Ez

[dim light]

Hello, I was wondering if there is someone here who has "The Complete Data Structure and Algorithm" course by Elshad Komarov? I would like to integrate it in my learning journey, however, I have no means to enroll

[vagrant perch]

can anyone tell me if this is how youre meant to do it because i cudnt do it without try statement as I had NoneType error at the end of the while: ```class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
hare = head
tortoise = head

    while hare:
        print(hare.val)
        try:
            hare = hare.next.next
            tortoise = tortoise.next
            counter+=1
        except:
            break
    return tortoise```

(middle node)

[vagrant perch]

nevermind, just used if statement

now can any help me with a second question, Im getting non type error even after checking not none for another LL problem

[vagrant perch]

also how do i return ONE node, when i return one it gives me the entire remaning list from that node on wardw

or rather up until that node, how

[split garden]

https://media.discordapp.net/attachments/874844963656044564/1091900397452546068/2023-04-01_18-42-04.mp4

I've been building a graphing calculator using numpy, matplotlib, and py_simple_ttk, I was wondering if there where any good resources on essentially writing your own interpreter, currently I'm relying on python's eval for the expression handling, multiplier expansion, and operator substitutions but I'd like to see a better way of going about it.

[vagrant perch]

damn whys this channel so dead

[haughty mountain]

no

both refer to the same object

updating through one updates the underlying object

!e e.g.

a = []
b = a

b.append(42)

print(f'{a = }')
print(f'{b = }')

[halcyon plank]

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

001 | a = [42]
002 | b = [42]

[vagrant perch]

yeah wat had me was that i was not used to objects but speerate variables

for example when you assign a variable to another one then change one it wont impact the other

[haughty mountain]

it will affect the other

all variables in python are references

so modifying through one reference modifies the underlyign object

[vagrant perch]

not when you assign X = Y where Y is not an Object type though right? what if Y is a Dict

if Y is a dict then changing X will not impmact Y

if Y = {1:2} and you say X = Y, then you do X.add something and recall Y it will still be original

fuck im wrong

ur right

idk ive been using too muich pandas

[haughty mountain]

when would pandas do this?

it should always be references regardless

[agile sundial]

pandas sometimes makes a copy when you do certain operations

[haughty mountain]

true, but then it's not a simple reassignment

and basically something like

a = b.copy()
```in disguise

[agile sundial]

pretty much, yeah. pandas also warns you when you copy, because you're probably doing it by accident

[pine axle]

Is there some sort of data structure like a range-map? Where it be like this:

x = {0-2:"a", 2-3:"b", 3-5:"c"}```
Where
```py
x[1.5] -> a
x[2.8]-> b
x[3.1] -> c

I know this can be mimicked with a list like: [[2,"a"],[3,"b"],[5,"c"]
But I'm looking for a solution with O(1) fetch speed

[vagrant perch]

i am not aware of being able to index using decimals

i hopep someone can answer this its very interesting

how is that mimick solving your problem though because those are ints only

[pine axle]

you would iterate through the list and stop when the integer is greater than the target

[agile sundial]

bst would make it log n, but not sure if it's possible in O(1)

[haughty mountain]

without assumptions on the ranges you can't do better than O(log n) afaik

BBST or binary searching the list of ranges are two ways

[haughty mountain]

is O(log n) not good enough?

[pine axle]

It's for a leetcode problem that has O(1) as a requirement

I've come up with an alternative solution now tho

[viscid coral]

to define a shape to work with, is it sufficient for me to have a list of each node, where the number in the list refers to how many edges are attached to that node?

for example, if i have an pentagon of 5 people, can i work with that shape by representing it as a list of [2,2,2,2,2]?

or if i have a line of 7 people, can i represent it as [1,2,2,2,2,2,1]?

(closed shapes only)

context: wondering whether it is possible to have a script that finds the number of unique arrangements of any closed shape that people can arrange themselves in. e.g. [1,2,2,1] should return 24 (4!), while [2,2,2,2] should return 6. is it possible to handle more complex (open) shapes like a cross too? not sure how i would input this into a list: maybe as [1,1,4,1,1,1,1,1,1] but i dont know for sure...

[pale kraken]

Hello, I wanted to know how I could turn this JSON:

 "temp1": 57.0,
 "wind1": 12.5,
 "humidity1": 31
}{
 "temp2": 55.9,
 "wind2": 9.4,
 "humidity2": 30
}{
 "temp3": 55.9,
 "wind3": 9.4,
 "humidity3": 30
}```
 

back into a Python dictionary. Ive tried using this (below) code to structure it properly, but it didnt work. 
 
```with open(weatherdir,'r') as file:
    contents = file.read()

print(contents)

contlist = list(contents)

contlist.insert(1,'[')
contlist.append(']')

for i in contlist:
    if i == '}':
        contlist.insert(contlist.index(i)+1,',')

print(contlist)```


Thanks for your help.

[agile sundial]

where did you get this data? it's not valid json

and it doesn't really make sense either

your best bet is probably to just str.split on }\n{ or something, readd the } and {, maybe

[haughty mountain]

!e just do some string replacement?

import json

bad_json = '''
{
 "temp1": 57.0,
 "wind1": 12.5,
 "humidity1": 31
}{
 "temp2": 55.9,
 "wind2": 9.4,
 "humidity2": 30
}{
 "temp3": 55.9,
 "wind3": 9.4,
 "humidity3": 30
}
'''

good_json = '[' + bad_json.replace('}{', '}, {') + ']'
print(json.loads(good_json))

[halcyon plank]

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

[{'temp1': 57.0, 'wind1': 12.5, 'humidity1': 31}, {'temp2': 55.9, 'wind2': 9.4, 'humidity2': 30}, {'temp3': 55.9, 'wind3': 9.4, 'humidity3': 30}]

[haughty mountain]

realistically you would also remove the digits since it's kinda silly to have them when you have an array

!e which can be done easily with some post processing

import json

bad_json = '''
{
 "temp1": 57.0,
 "wind1": 12.5,
 "humidity1": 31
}{
 "temp2": 55.9,
 "wind2": 9.4,
 "humidity2": 30
}{
 "temp3": 55.9,
 "wind3": 9.4,
 "humidity3": 30
}
'''

good_json = '[' + bad_json.replace('}{', '}, {') + ']'

data = json.loads(good_json)

data = [
  {key.rstrip('0123456789'): value for key, value in obj.items()}
  for obj in data
]
print(data)

[halcyon plank]

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

[{'temp': 57.0, 'wind': 12.5, 'humidity': 31}, {'temp': 55.9, 'wind': 9.4, 'humidity': 30}, {'temp': 55.9, 'wind': 9.4, 'humidity': 30}]

[hollow elbow]

@fiery cosmos how are you doing with python? did you keep practicing?

[fiery cosmos]

yes, building along with a blackjack game, at the moment 🙂

ty for asking

[novel copper]

Hey guys. I need some help, today I started to learn algos and I stuck with code of binary search. I do not understand what the construction inside the red square and what it does. Does anybody can help me?

[agile sundial]

it's indexing into the list

[novel copper]

Damn, you’re right, thank you man

I really forgot about indexing

[midnight citrus]

whats the time complexity of this code?

nums is something like [1,1,1,2,2,3,3,3,3]

is it o(nlogn) because of heappop?

[dusky trellis]

depends on what heapq is

[midnight citrus]

wdym

[agile sundial]

k log n

[midnight citrus]

worst case k =n ?

sorry i havent provided the problem so this is very vague

[agile sundial]

yes, O(n log n) is technically correct

[midnight citrus]

ok i see

[vocal gorge]

it's a builtin

[quartz scroll]

is there any site that i can learn python in a easy and simple way

?

[uneven vine]

readthe python docs

it covers likealot

[glacial crypt]

Yes, code with mosh will give u an insider atleast imo

[mint folio]

Hello. Can you help me?
This is my code: https://paste.pythondiscord.com/niruqihejo
And this is the value of classIds = [2, 2, 2, 2, 7, 2]
So, it is supposed to draw a bounding box only for specific ID of classIds, but the code somehow throws this error:

IndexError                                Traceback (most recent call last)
~\AppData\Local\Temp\ipykernel_5840\3590414005.py in <module>
     81     #print(outputs[2].shape)
     82 
---> 83     findObjects(outputs,img)
     84 
     85     cv2.imshow('try',img)

~\AppData\Local\Temp\ipykernel_5840\3590414005.py in findObjects(outputs, img)
     41                 classIds.append(classId)
     42                 for i in classIds:
---> 43                     if classIds[i]==0 or classIds[i]==2 or classIds[i]==5 or classIds[i]==7:
     44                         w,h=int(det[2]*wt),int(det[3]*ht)
     45                         x,y=int((det[0]*wt)-w/2),int((det[1]*ht)-h/2)

IndexError: list index out of range```
What is happening here?
What should i do?

[quartz scroll]

thanks

[brisk ginkgo]

Hi i'm looking for a simple algo:
i'm iterating in a list (lets call it list_input) to fill an other list (list_output) but i need the elem in list_output to be unique.
I'm looking to have the lowest algorithmic complexity possible, what is the best way:

list_input = [1, 2, 2, 3, 3, 3, 4, 4, 5, 6, 6, 7]
list_output = []

for i in list_input: # O(n)
  if i not in list_output: # O(n)
    list_output.append(i)

Maybe using sets ? is it optimized ? thanks in advance
edit: ping me if answer
edit2: i know sets are better in this case but i'm looking for the BEST way

[agile sundial]

you can easily prove that O(n) is the best you can do

[brisk ginkgo]

y i know but now it's O(n2) in the worst case (if list_input have only unique elements)

[agile sundial]

hm? using a set would be O(n^2) worst case, but not necessary if the input was all unique. it would be O(n^2) if every element had the same hash

[brisk ginkgo]

i talked about my exemple, not sets

in my exemple i'm checking for each element if it's in list_output

[agile sundial]

well that's always O(n^2)

[brisk ginkgo]

ok w/e but so what is the best way to do that ?

[agile sundial]

sets or dicts

or if it's sorted, a stack

[brisk ginkgo]

not sorted so ok

ty

[little wagon]

hello, is there any difference in terms of complexity between creating an entire list and then sorting it or making sure of inserting items in a sorted position as you create it?

[jolly mortar]

the second one is worse

its O(n^2)

(its insertion sort)

[little wagon]

I see, thanks

[dusk sand]

Hello everyone

[south wren]

weird syntax question, is there a way to define a function as part of an object directly (outside of the object definition) instead of defining the function and assigning?

e.g.

def myobj.execute():
  #blah

instead of

def execute():
  #blah
myobj.execute = execute

[swift breach]

If you want the pragmatic answer that is generally faster than keeping a set of already seen values yourself vs just exploring the algorithmic portion:

# on all currently supported python versions (relies on dict insertion order guarantee)
# this deduplicates retaining ordering
# requires that list_input is list[Hashable]
list_output = list(dict.fromkeys(list_input))

[leaden lagoon]

not sure if this is the right chat

but i want to code the structure F_2[x]/(m)

where m is a polynomial such that I can find inverses of elements and factorize and such

but

I have no idea how to

otherwise where do i ask 😭

cant find anything online

[haughty mountain]

maybe sympy is useful

https://docs.sympy.org/latest/modules/polys/index.html

[leaden lagoon]

YESSS

Exactly what i need

thanks a lot!

[hybrid zodiac]

Are there modules for tree and graph data structures?

[lean walrus]

!d heapq

[halcyon plank]

heapq

Source code: Lib/heapq.py

This module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm.

Heaps are binary trees for which every parent node has a value less than or equal to any of its children. This implementation uses arrays for which heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] for all k, counting elements from zero. For the sake of comparison, non-existing elements are considered to be infinite. The interesting property of a heap is that its smallest element is always the root, heap[0].

[hybrid zodiac]

heaps?

I asked for general purpose modules for tree and graphs data structures

[agile sundial]

a heap is a tree

[robust dagger]

networkx for graphs.

[buoyant goblet]

Hello folks,
Given a self-reiterating method, what's the best approach to collect output of the method for printing it out?
I do not want to alter the method signature, as it sounds a very dirty approach.

Any ideas?

[haughty mountain]

maybe consider a generator

I pretty frequently write generator functions that do things like yield lines of output

an example from a while back

def gen_section(content):
  yield 'Some header'
  yield '-----------'
  yield '\n'.join(content)

def gen_text(content):
  yield from gen_section(content['something'])
  yield ''
  yield from gen_section(content['something else'])

text = '\n'.join(gen_text(content)) 

[buoyant goblet]

@haughty mountain I have a generator already to print the whole "collection". What I was after is to print the output of a given subset, processed at the entry time.

I'm processing a tree structure, holding the output into a root variable for which an iterator has been implemented to traverse the full object (including branches).
What I want is to return an output I can print for the given branch

Array thinking, pretend something like

root = []
root.appen('hello')
root.append('something/else/appended')

The iterator prints

• hello
• something
• else
• appended
  As to me those are 4 nodes

All I'm missing is a print for the single append command

as a very bad practice, the last resort could be a global variable.

I can see a couple of options: either a closure or a decorator

[haughty mountain]

you want something based on the path from root to every other node?

if so, dfs with append/pop to a list as you traverse (append before recursing, pop after), and yield a str based on the list

[haughty mountain]

i.e.

!e

from dataclasses import dataclass

@dataclass
class Node:
  value: str
  children: list['Node']

tree = Node('root', [
  Node('hello', []),
  Node('something', [Node('else', [Node('appended', [])])])
])

def dfs(cur, path=[]):
  path.append(cur.value)
  yield '/'.join(path)
  for child in cur.children:
    yield from dfs(child)
  path.pop()

print('\n'.join(dfs(tree)))

[halcyon plank]

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

001 | root
002 | root/hello
003 | root/something
004 | root/something/else
005 | root/something/else/appended

[chilly zephyr]

Yesterday, I appeared for a contest on Codechef, there was this question that involved sum upto n natural numbers. Link : https://www.codechef.com/problems/MELTGOLD
I solved it using the most basic method of adding numbers but got TLE (solved it using CPP though) :

    x, y= map(int, input().split(' '))
    n= x- y
    if n:
        i= -1
        while(n> 0):
            i+= 1
            n-= i
        print(i)
    else:
        print(0)

After the contest I saw Python accepted answers and found some kind of mathematical formula that is involved in solving such problems.
The mathematical logic :

    x,y = map(int,input().split())
    a = math.sqrt(2*(x-y))
    print(round(a))
    # Accepted

other solution had some different formula :

x,y=map(int,input().split())
    ans = ceil(sqrt(8*(x-y)+1))-1
    if (ans%2==0):
        print(ans//2)
    else:
        print(ans//2+1)
    # Accepted

Can someone explain how these formulas were derived and what are these formulas called ?
Thank You 😊

[stray fractal]

i think they simplify x(x+1)/2 >= X-Y but i'm not sure

[stray fractal]

@chilly zephyr i ran x(x+1)/2 >= X-Y, solve for x in wolfram alpha and i got x <= (-sqrt(8*(x-y) + 1) - 1)/2 which should have x be equal to the second solution
for the first solution there's also x(x+1) >= (X-Y)*2 and taking advantage of the fact that x(x+1) is somewhat equal to x²/has the same >= properties as x²; then they use x² >= (X-Y)*2 or x >= sqrt((X-Y)*2)
the round() just converts it into an integer

i really don't like the approximation for the first one but if it works, it works

[chilly zephyr]

even I thought so for the first
but second is the correct solution for x

[chilly zephyr]

the solution for x that has 8 in it comes down to two different inequalities for x one with + and other with - then how to determine which one is correct ?

[swift breach]

It's not actually an approximation. it's clever use of the math at play and python's rounding behavior, specifically:

if two multiples are equally close, rounding is done toward the even choice

[haughty mountain]

binary search is another option here, and doesn't require any cleverness

l = 0
r = 10**9
while r - l > 1:
  mid = (r + l) // 2
  if mid*(mid + 1) // 2 >= x - y:
    r = mid
  else:
    l = mid
# r is the largest integer where >= holds
# i.e. the answer

this is a useful technique in cases where explicitly solving something is hard, but checking if a value is ok is easy

[haughty mountain]

one is negative

[chilly zephyr]

but what to print at last ? (as asked in problem)

[haughty mountain]

r

as I mentioned in the comment

basically l is always < in the check and r is always >= in the check

so after the loop
l is the biggest value such that you have < in the check
r is the smallest value such that you have >= in the check

[spark lynx]

what algos and data structs would I need to learn to be a better data engineer?

[scenic schooner]

not directly related concepts, strong understanding of any field in programming is more than likely to translate over to other fields

however questions like this shouldn't be asked in this chat

[wispy thistle]

how do i create a folder in the parent directory using a relative path?

file = open("\\..\\test.txt", "w")

This doesnt work

[tepid pivot]

import os
os.mkdir(‘../test.txt’)

[tepid pivot]

This might work

[verbal depot]

Hey guys I need help 3d modelling a monster for my game are anyone willing to help me? This is a picture of the monster:

[tepid pivot]

What help do you need?

[haughty mountain]

and how does it relate to #algos-and-data-structs

[midnight citrus]

LMAO

[naive oak]

you're trying to 3d model a ruin guard?

that's probably more suited towards #game-development if any channel at all

[fiery cosmos]

Hi, can someone help me please ? I try to create an app about a clicker on a cookie for counting clicks and give forwards when the clicker give a lot of clicks but I have a problem for showing the cookie

I can't understand why my "self" isn't defined

[golden cove]

Hi everyone, I need help parsing a string that has multiple fields in it, and I'm fairly new to python and I'm not sure the best approach.

I have this string:
Comments: 'CHG0098743-AP03042023',Destination: Changed to '.dns.google.com', 'x-8.8.4.4',Services & Applications: Changed to 'TCP-443',Source: Changed to 'yyy-i-192.168.15.0/24',Action: Changed from 'Drop' to 'Accept',Track: Changed from 'None' to 'Log',UseLogPerSession: Changed from 'Disable' to 'Enable',Layer Name: 'Layer-Policy-03022022 Application',Policy Names: 'Policy-Policy-03022022'

I need to get each key/value pair:
Comments: 'CHG0098743-AP03042023',
Destination: Changed to '.dns.google.com', 'x-8.8.4.4',
Services & Applications: Changed to 'TCP-443',
Source: Changed to 'yyy-i-192.168.15.0/24',
Action: Changed from 'Drop' to 'Accept',
Track: Changed from 'None' to 'Log',
UseLogPerSession: Changed from 'Disable' to 'Enable',
Layer Name: 'Layer-Policy-03022022 Application',
Policy Names: 'Policy-Policy-03022022'

Each key is delimited as "word: " and the value is everything up to the next ",word: ", but not the next key.

I have thought of looping through the string, character at a time and building a map of the start and end positions to try to determine the key/value pairs, but there must be a better way ...

[lament totem]

@golden cove is this for hw or personal project or?..

[golden cove]

This is a work related topic. I'm trying to parse a report

a report csv file

[lament totem]

I'm not super experienced with regex, but this is a possible solution

!e

import re

string = "Comments: 'CHG0098743-AP03042023',Destination: Changed to '.dns.google.com', 'x-8.8.4.4',Services & Applications: Changed to 'TCP-443',Source: Changed to 'yyy-i-192.168.15.0/24',Action: Changed from 'Drop' to 'Accept',Track: Changed from 'None' to 'Log',UseLogPerSession: Changed from 'Disable' to 'Enable',Layer Name: 'Layer-Policy-03022022 Application',Policy Names: 'Policy-Policy-03022022'"

keys_values = re.split(r'([^,]+:)', string)
keys = [key.strip(':') for key in keys_values[1::2]]
values = [val.strip(' ') for val in keys_values[2::2]]

result = dict(zip(keys, values))

for key, value in result.items():
    print(f'{key}: {value}')

[halcyon plank]

@lament totem :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | Comments: 'CHG0098743-AP03042023'
002 | Destination: Changed to '.dns.google.com', 'x-8.8.4.4'
003 | Services & Applications: Changed to 'TCP-443'
004 | Source: Changed to 'yyy-i-192.168.15.0/24'
005 | Action: Changed from 'Drop' to 'Accept'
006 | Track: Changed from 'None' to 'Log'
007 | UseLogPerSession: Changed from 'Disable' to 'Enable'
008 | Layer Name: 'Layer-Policy-03022022 Application'
009 | Policy Names: 'Policy-Policy-03022022'

[lament totem]

I check for any pattern that is repeatedly characters that are not a comma ,, ending with a colon :. These will be your keys. I split the string on these keys to get they keys in one list, and in another list the values.

I also strip some spaces from the sides of the values, and I strip the : from the keys

Lmk if you have questions

This does mean that there cannot be a : inside the keys or values

[golden cove]

@lament totem thank you very much for this suggestion, I would have never thought of using list comprehensions

I have been a bash shell scripter for a long time, so flipping my mind to think pythonic has been a big struggle for me

[golden cove]

@lament totem that code works like a charm - thank you very much !!

[lament totem]

nws!

[fiery cosmos]

what's up all it's been awhile

[halcyon plank]

:incoming_envelope: :ok_hand: applied timeout to @tough grotto until <t:1680820519:f> (10 minutes) (reason: duplicates spam – sent 4 duplicate messages).

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

[midnight citrus]

Anyone have ideas of what type of technique I can use to solve this problem? I'm thinking maybe dynamic programming and backtracking but not sure.

https://docs.google.com/document/d/1D3bIj9ZRDV-S2T0YS4Lqe2z99xAQg-txNYuVGkLGZYs/edit?usp=sharing

[naive oak]

I believe the document is wrong
for n=3 there should be 6 cases not 5
also this is a math problem
look into derangements

[midnight citrus]

nope

this is not just derangements

consider

1 sec

[midnight citrus]

When n=3 , the failed sequences look like {1},{∗,2}, {∗,∗,3}. You cannot just count non-derangements of the whole group, since two sequences are considered the same if they are equal up until the first failure

[naive oak]

ah

[midnight citrus]

also

i kinda want to make a solution thats more computer science orientated (recursion,backtracking etc) rather than making a mathematical solution :d

i just dont know what technique would be best ^^

[naive oak]

well you could probably do dp

[midnight citrus]

i see

[naive oak]

probably go through a combinatorial argument to get a recurrence relation on your operator

and then do dp to compute it

[midnight citrus]

guess i can use that as a starting point ty!

[near forum]

Hey guys, I have a code were i wane find out if a string is equal to a specific word. I tried it like u see in my code but it doesnt work and i can find a solution. Do you have a idea?

My code: https://hatebin.com/fdqfvnsviw

[runic tinsel]

mooooods

[midnight citrus]

any idea how this solves the problem? I dont really understand this solution

from functools import lru_cache

@lru_cache(maxsize=1000000000)
def count(next, pile):
    if len(pile) == 0:
        return 0
    c = 0
    for i in pile:
        if next == i:
            c += 1
        else:
            next_pile = tuple(x for x in pile if x != i)
            c += count(next + 1, next_pile)
    return c

## Checking N From 0 -> 20
for i in range(20):
    print(count(0, tuple(range(i))))

[naive oak]

that's just going through the problem by hand

at first you have all range(i) hats

then, you consider each hat in the pile

for the hat that belongs to your current person, you add 1 to the count since that's a collision

for hats that don't you move on to the next person, with the hat pile reduced by that one hat

this isn't really a good solution

doesn't take into advantage any symmetry at all

[stray fractal]

why is next used as a name here

[midnight citrus]

I see.
the way I was thinking about things was counting the number of derangements for the first k people before the collision, but somehow including the people after the collision person aswell in the derangements for those k players before.

[midnight citrus]

I think its for the next player maybe? im not sure

[stray fractal]

i feel like it could be next_el instead for "next element" because next is a builtin but almost nobody uses next() anyway so i think it should be fine

[naive oak]

wdym

next() is so useful

[midnight citrus]

is current person i?

[naive oak]

in the function?

no

the current person is next

the hat being considered is i

[midnight citrus]

ah

[swift phoenix]

quick array question

I got some arbitrary array a = np.array([....])

now I need to sum this array from first to last value apart: so sum(a[0:0]) then sum(a[0:1])

now there immediately lies my issue: a[0:0] does not return the first value of the array

kinda makes sense, but is there a way to solve this

[vocal gorge]

well, yes, because slices in python are exclusive of last index just like ranges. so [0:0] is an empty slice. First element would be [0:1], which can be shortened to [:1].

[swift phoenix]

exactly

[vocal gorge]

Also, it sounds like what you want is np.cumsum(a).

[swift phoenix]

yeah gotta try that again but last time I did that it did not work

cumsum just sums all cumulatively right, so first is just a0, then a0 + a1 etc

[vocal gorge]

do you want the first element of the result to be zero instead?

[swift phoenix]

nah I want my first result

[vocal gorge]

but that's what cumsum does, though?

[swift phoenix]

the first slice a[0:0] returns nothing, obviously

but I need to work around that, since cumsum requires me to store a lot of data in my case

[vocal gorge]

I still don't get what you want the result to be. Suppose a = np.array([1,2,3,4,5]). Then what's your desired output?

[swift phoenix]

got a for loop, summing that array

wait a sec I might see how to fix this now

yeah this was a lot easier than expected thanks man I fumbled the bag

first element would be 0:1, so instead of summing 0:i, I sum 0:i+1

[vocal gorge]

I still don't get why you can't just do a cumsum, but good job figuring it out, I guess.

[swift phoenix]

I should try to get cumsum to work since it will probably be a lot faster than for loops

okay cumsum works perfectly for a certain part of my code

it doesn't actually but I can't figure out why

I'm just stupid ignore that

the speedup oh my god

125x speedup

[near forum]

Hey guys, I have a code were i wane find out if a string is equal to a specific word. I tried it like u see in my code but it doesnt work and i can find a solution. Do you have a idea?

My code: https://hatebin.com/fdqfvnsviw

[clever mural]

instead of pipe (‘|’) symbol use ‘or’ in while statement

| symbol is used for set operands for union operation.

[dusky trellis]

| does not mean logical or

it is either set union or bitwise or. you want to use the operator 'or'

[near forum]

hey i got a errorcode: Traceback (most recent call last):
File "c:\Users\const\OneDrive\Dokumente\Schule\Fächer 2\Informatik\euklidischer_algorithmus.py", line 156, in <module>
decode.append(buchstaben_zahlen[(zahlen_buchstaben[liste[i]])%26])
TypeError: There are no type variables left in list['hallo']

in my code (https://hatebin.com/olazrojkwu) i wanne programm the rsa-system and i can`t solve my problem

[clever ocean]

Help solve this question

these are the fibonacy and sum functions:

    return int((((1 + 2.23606797749979)/2)**i - ((1 - 2.23606797749979)/2)**i)/2.23606797749979)

def s(i, j):
    sum = 0
    while i <= j:
        sum += f(i)
        i += 1
    return sum```

[haughty mountain]

that formula will break even for pretty small inputs

and the summing also breaks since the inputs can be huge

you'll want to find a recurrence for the sum of the first n fibonacci numbers, and then use something like matrix exponentation to compute things in O(log n)

(the sum of the first n terms is actually a nice formula, play around a bit and you will find it)

[mint folio]

Hello! I need help.

So this is the code: https://paste.pythondiscord.com/recucineqa
This code was supposed to count vehicles drawn in bounding box with a centroid in it, using a line as the counter.
But when a centroid hits the counter line, the vehicle count scores 1 point and then returns to zero once the centroid leaves the counter line, which is the case i don't expect.
What's wrong with this code?

If you want the full code: https://paste.pythondiscord.com/ipofibuqer

[naive oak]

i don't think you actually need to calculate fibonacci at all for that problem

[haughty mountain]

as in there is something special about the gcd?

[naive oak]

you're calculating gcd(F_(a+2), F(b+2)-F(a+2)) right?

which is equivalent to gcd(F_(a+2), F_(b+2)) by properties of gcd

[haughty mountain]

I guess it boils down to that yeah

[naive oak]

ah actually

no

you do need to calculate it

but only once

because gcd(F_n, F_m) = F_gcd(n, m)

[haughty mountain]

ah cool, so just evaluate that fib number

[naive oak]

i think you might be able to get away with even more optimization

[haughty mountain]

do you need it?

[naive oak]

probably not but it's fun

[haughty mountain]

O(log gcd(n, m)) ought to be good enough

[naive oak]

hmm

eh don't think it works

the matmul/recurrence approach with modulo is probably the best approach then yeah

[robust dagger]

For computing S_{1,a}, it looks to me like the simplest approach is to write down a recurrence for it. There will be a recurrence for S_{1,a} involving the past three terms S_{1,a-1}, ..., S_{1,a-3}. This can be turned into a matrix. And you can get S_{a+1,b} as S_{1,b} - S_{1,a} of course.

[robust dagger]

To get the recurrence for S_{1,n}, observe that it equals S_{1,n-1} + F_n = S_{1,n-1} + F_{n-1} + F_{n-2} = S_{1,n-1} + S_{1,n-1} - S_{1,n-3} = 2*S_{1,n-1} - S_{1,n-3}. So we can compute it with matrix exponentiation by:

from sympy import Matrix

def S1(n):
    M = Matrix([[2, 0, -1], [1, 0, 0], [0, 1, 0]])
    return (M**n)[1, 0]

[naive oak]

||you could also compute it by notating that the sum of the first n fibonacci numbers is the n+2 th fibonacci number - 1 btw||

[robust dagger]

||But that requires not blindly marching forward without thinking!||

Besides, I was having fun.

The relation between the two methods basically comes down to ||the factorization x^3 - 2x^2 + 1 = (x - 1)(x^2 - x - 1). The polynomial x^2 - x - 1 is the one associated to the Fibonacci recurrence, while x^3 - 2x^2 + 1 is associated to the S_{1,n} recurrence.||

||I saw right away that S_{1,n} would be associated to a degree three polynomial but didn't try to factor it.||

[mild dove]

hi does someone understand what is the idea of this algorithm (multiply the chars and append with a xor of the chars). need to generate a key that should be the same if s is an anagram (sorry the guy wrote in java 🙇‍♂️ ) private String getKey(String s){ int prod = 1, xor = 0; for(int len=0; len<s.length(); len++){ char i = s.charAt(len); prod *= i; xor = xor^i; } return String.valueOf(prod) + '_' + String.valueOf(xor); }

[robust dagger]

It looks like a bad hash function. It already does not depend on the ordering of the characters, so if you input an anagram you will get the same result.

[vocal gorge]

well, both product and XOR don't depend on the order, so they are indeed obvious choices for a permutation-invariant hash function.

[robust dagger]

I found an interesting article on hash functions of this type: https://kevinventullo.com/2018/12/24/hashing-unordered-sets-how-far-will-cleverness-take-you/

[mild dove]

oh good, ok, I thought it was a known algorithm

[sleek mortar]

ا

ا

[gray garnet]

Is it possible to determine whether or not a directed disconnected graph contains a cycle in linear or linearithmic time?

[robust dagger]

Attempt to topologically sort it. This takes linear time if it succeeds, and it fails if and only if the graph has a cycle.

[gray garnet]

oh ive never heard of topological sort before but ill look at it

[jagged linden]

lgkt''l';'5333

[agile sundial]

you can also just dfs

[light hollow]

is there a beginners channel were i can ask for help i am just learning python

i am at dicitonary

[robust dagger]

See #❓｜how-to-get-help

[noble sluice]

Me 2 i am a beginner learner as well

Thank you

[warped furnace]

hey guys I'm a bigginer and trying to learn basic coding. Im trying this question in leetcode ,wether a number is power of 2 or not .

The code worked , but for value of 16 it failed

Then I plugged in a couple of print statements , Then found that the control is going into the first IF loop where conditon is n==2 or n==1 , But not returning True

I'm kinda confused and did know what to do

Can anyone help

[covert thorn]

you never told it too. for n=16 the method gets called for 16, then 8, 4, and finally 2, where it returns True, but there's currently no way for that True to propagate all the way back up to the top to be outputted.

I believe as well that the false it says is being returned is misleading, and it's converting the output (None) to boolean, which is then False

[warped furnace]

sorry, I didn't understand it , How do I make sure that the True is propagated back to the original call

[covert thorn]

well of your three conditions there, the first (n being 1 or 2) has a return True, and the last (the else) has a return False. but the middle case that uses recursion has only a method call and no return statement. In many instances where recursion is used - and yours is one of them - the proper return is the recursive call itself (i.e. return self.isPowerOfTwo(n//2))

RealPython has a page on recursion if you'd like to read it: https://realpython.com/python-recursion/

[warped furnace]

wow I get It ,I I'm not returning the result from the function call back to the original call .I Was just calling the function

Thanks @covert thorn That helped alot

[midnight citrus]

more maths related but anyone know how this actually works in determining the big square a coordinate is in, in a sudoku grid

def helper(row, col):
    reduceRow = row // 3
    reduceCol = col // 3

    return reduceCol * 3 + (reduceRow + 1)

[opal oriole]

1D grid version.

How many 3's go into 4?

[midnight citrus]

1

[opal oriole]

So you can fit 1 3-long chunk into it.

And some remainder.

[midnight citrus]

yeah

[opal oriole]

That remainder is where we are in the next chunk.

(Going left to right in this image)

We don't care about that though, only which chunk we are in, so we round down.

[midnight citrus]

i see

[opal oriole]

// is integer division, it will cut off the decimal places.

(Round down in this case for positive values)

You can think of it as trying to get to the 4 position starting at 0. How many 3-long chunks can we skip forward, and then how many 1 blocks?

Division does that, it asks how many times we can fit 3 into the target position.

[midnight citrus]

yea so you can get the amount of chunks before by int division and then add one to get to the current chunk it is in right?

[opal oriole]

Minus one, because we start at index 0.

A programming specific detail.

[midnight citrus]

oh ye

[opal oriole]

But we actually don't need to add or subtract anything, because that plus one cancels out with the minus one needed for zero indexing.

Just the division is enough.

[midnight citrus]

but

[opal oriole]

For getting +1/-1 details right I recommend just playing with some pictures like I drew and see if the math is giving you the desired index. Keeping in mind that chunks need to start at 0 in programming.

[midnight citrus]

wouldnt the division just give big square before it?

like 8 // 3 would give 2

which is the second not the third

[opal oriole]

Which is correct, look at the image. It's the third.

[midnight citrus]

oh

ye

[opal oriole]

.

[final cedar]

do you talk to yourself?

[opal oriole]

Is this question for me?

[final cedar]

@midnight citrus No, I am writing to him

[midnight citrus]

❓ why lol

weird question

[midnight citrus]

i get this now tho ty for the help

[unborn ferry]

https://paste.pythondiscord.com/leleyihoqu

does anyone know how I could make the start button make the intro frame disappear and the choice frame appear?

[cloud halo]

Guys. I just started studying Data structures and algorithms on my own. Recently, I learned about arrays. I went to LeetCode to try out a problem in this topic, but I wasn’t able to even have an intuition of how to get started. I heard that this builds overtime, but I don’t want to keep looking at the solution. How do you guys recommend I study data structures and approach this?

[fiery cosmos]

Someone know how to convert list in int, please ? Because the line 19 doesn't work

[fiery cosmos]

Hello if anyone is a new in dsa so you can contact me also I just started dsa in python. Then you can ping me we can make a duo for our upcoming journey. Thank you

[sonic scaffold]

Are you doing the Arrays 101 card? I wouldn't feel too bad about not intuitively knowing what to do on some programming problems. Some just have a trick that you don't know yet. Some require a specific algorithmic approach.

[cloud halo]

Ahh I see. I went to try out a medium problem. It was problem 73 - set matrices to 0.

[blazing nebula]

https://github.com/reactDevCloud/HURLS

[snow anvil]

I suggest learning how list indexing works

Right now your number variable is not a number

[snow anvil]

If you are just starting out do not feel bad about not being able to solve a medium

[cloud halo]

Should I just learn a data structure, do a few easy problems and move on to another data structure and repeat until I learn all of it and then attempt medium and hard problems?

[snow anvil]

I cannot tell you that to be honest.
Move at a pace you are comfortable with and read some books.

[dusky trellis]

it's best to get a broad overview first before diving in deep. IMO, of course

[snow anvil]

I assume you know about big O if not that is where you should start

[vagrant perch]

Look for the easy problems and filter by pass %

[vagrant perch]

You have no chance, those are extremely hard

First learn how to iterate over arrays, index them, and add remove values

[vocal gorge]

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.
that looks... very straightforward

ah, though I was thinking of the O(n+m) space one and it claims an O(1) one is possible.

[agile sundial]

interesting

[vocal gorge]

bad O(1) space idea: || for each row, check if it has a zero and replace all the nonzero elements with Nones if it does. Same for each column. Finally, replace all nones with zeros. This esentially uses the matrix itself as scratch space.|| The bad thing is that it requires you to ||use Nones despite the matrix really being of ints||.

ah, I looked at the official solution, it's similar to that but cleverly avoids that issue.

[vagrant perch]

How is it possible to beat o nm when you need to replace every value

Oh, space

Yeah still dunno

[urban kiln]

cant remember exactly how i did it but it was something with using some row as place to safe information if row has to be made full 0s

cant really explainhow

i can send my solution once im home

like use
matrix[0][i] = 0 if for any j matrix[j][i] == 0

and

matrix[i][0] = 0 if for any j matrix [i][j] == 0

idk how efficient it is

it should be space O(1)

O(nm) for time i think

i think it was a daily problem a few weeks or months ago

i love leetcode

its so much fun doing the problems

cant understand how people dong like doing leetcode

[urban kiln]

you cant

(i think)

[urban kiln]

and then in second iteration, if matrix[i][0]==0,then replace row with 0s and same for matrix[0][i]

thus 2nm,

O(nm)

let me know if there is a better way of solving this

@vocal gorge @agile sundial
sowwy for ping >_<, but is this good?

^_^

[urban kiln]

leetcode is great for learning

took me like a month to undrrstand what im doing

took me way too long to underszand what a linked list is

and that it isnt a buildin datastructure

in python

i just did leetcodw a few hiurs a day

and watched videos

and implemwnted everything i sqw

[cloud halo]

Thank you for your suggestions @snow anvil @vagrant perch @urban kiln I was able to solve a 5 easy array problems on my own. It felt pretty good. Guess I’ll take things up a notch slowly

[urban kiln]

damn congrats

_<

[vocal gorge]

that's the O(1) space solution they suggest, yeah

[urban kiln]

yay

ill implement in öython once im home

[still spear]

import pyttsx3
import speech_recognition as sr
import datetime

engine = pyttsx3.init('sapi5')
voices = engine.getProperty('voices')

print(voices[0].id) #Windows voices

engine.setProperty('voices', voices[0].id)

#text to speak
def speak(audio):...

To convert voices into text

def takecommand():
r = sr.Recognizer()
with sr.Microphone() as source:
print("listning...")
r.pause_threshold = 1
audio = r.listen(source,timeout=1,phrase_time_limit=5)

try:
    print("Recognizing")
    query = r.recognize_google(audio, language='en-in')
    print(f"user said: {query}")


except Exception as e:
    speak("Say that again...")
    return "none"
return query

To wish

def wish():
hour = int(datetime.datetime.now().hour)

if hour>=0 and hour<=12:
    speak("good morning")
elif hour>12 and hour<18:
    speak("Good After Noon")
else:
    speak("good evening")
speak("i am jarvis sir, tell me how may i help you")

if name == "main":
wish()

hmn this code is not working 😐 can somebody help me

[naive anchor]

Hi All. hopefully, this is allowed and isn't classed as advertising

I recently wrote an article on Medium regarding styling Plotly Sankey diagrams.

I cover the following areas.

• Specifying colours for nodes
• Specifying colours for links
• Specifying X and Y coordinates for nodes
• Adding annotations to the Sankey
• Hiding label text on the diagram but having it available when hovering your mouse over an area.

The article is available at https://medium.com/@twelsh37/further-adventures-in-plotly-sankey-diagrams-fdba9ff08af6

[naive anchor]

I'm no expert, really just a beginner, but you have an incomplete function, either that or you haven't posted all the code. is it your code or a copy from somewhere? Where are you trying to run it, and in what IDE etc?

the function in question is

#text to speak
def speak(audio):...

which should really be

def speak(audio):
pass

[still spear]

I am beginner actually It's my code I was trying to make a bot which can do basic stuff
well I found code error and it's working now

[naive anchor]

Excellent!

[runic tinsel]

that's valid

def can be one lined

!e
def f(): ...
print('is ok')

[halcyon plank]

@runic tinsel :white_check_mark: Your 3.11 eval job has completed with return code 0.

is ok

[noble sluice]

Wait then how do we make the variable a number?do we use int()? sorry im really new to python so kinda lost.

[naive anchor]

in the python interperter

a = '1' # set a to be the string '1'
type(a) # check its type
<class 'str'> # its a string
b = int(a) # convert string to int
type(b) # check its type
<class 'int'> # its an integer

[noble sluice]

So basically just change it to

if number >= int(10): ?

[fiery cosmos]

Yeah, I know it is a variable but, every time I click on the cookie, it puts a new number, and I'd like to affect, to verify, the number that we can see at a precise moment. Have you an idea pls ? Or another idea for addition 1 to the anterior number when i click on my cookie ?

[fiery cosmos]

sorry for my bad english, I am a french people

[snow anvil]

Go to #1035199133436354600

[midnight citrus]

 
  def longestConsecutive(nums) -> int:
    if nums == []:
        return 0

    nums = set(nums)
    longest = 0
    longestConsecutive = 0

    startpoints = [[x, 0] for x in nums if x - 1 not in nums]
    for x in startpoints:
        while x[0] + longestConsecutive in nums:
            longestConsecutive += 1
        longest = max(longest, longestConsecutive)
        longestConsecutive = 0

    return longest

i dont get how this is linear time

say nums is length n

worst case startpoints is also n
so for loop runs n times
while loop, worst case runs n-1 times

so surely thats n(n-1) which is o(n^2)

oh wait thats not worst case since while loop wont even run if start points is length of n

i see now

[noble sluice]

Does changing it to int(10) work?

[fiery cosmos]

unfortunately, no "TypeError: '>=' not supported between instances of 'list' and 'int'"

[noble sluice]

Oh

Sorry then im not sure what else to suggest for now.i just started python so i have no idea whats going on as well.

[rustic eagle]

Hi. Does anyone know how to implement a method that finds N-largest elements from a doubly linked list ?

[haughty mountain]

right, after making things unique you can have a few chains of increasing numbers, what that code is doing is finding the start points of the chains

and overall all values are part of exactly one chain

so you will only go through every value once

this is actually a similar trick that was possible in an interview question I used to ask

the question is here
#algos-and-data-structs message

basically, warm up question:

you're given a list of values, return a new list of double the length which contains the original elements, as well as the elements doubled
(in some random order)

follow-up:

now do it backwards! you're given a list, figure out if the given list could have been produced through the process from the warm up task applied to some list

and if so, give one such original list

[midnight citrus]

i wrote the code and i subconsciously did this wow

[haughty mountain]

I mean, you also have a useless value as the second value of the tuple, so all is not great 😛

[midnight citrus]

OH yeah

that was my solution before hand

i forgot to remove it

when i realised max can take two parameters

[midnight citrus]

so does the follow up function return a boolean i.e it only determines if the list is producable by the first function or do you need to actually find the input list

nvm i didnt read the bottom

[haughty mountain]

they are similarly hard questions

[mint folio]

Hello! I need help.

So this is the code: https://paste.pythondiscord.com/uxopuneman
This code is designed to detect specific moving objects, especially vehicles, draw bounding box and centroid within them, and finally count their centroids using a counter line.
So far the code works well, but i have encountered a minor problem within the code.

Whenever a centroid is within the counter line, it will continuously add into the vehicle count in an endless iteration, until there's literally no centroid in the counter line. This, which is the case i never expected.
I expect the counter line to stop iterating the addition of vehicle count after it detects a new centroid once.

If you want the full code: https://paste.pythondiscord.com/xeqitomado

[dusty dune]

Hey I was practicing generators, here is the code I was using

#A function to test weather a number is palindrome or not

def is_palindrome(num):
# Skip single-digit inputs
if num // 10 == 0:
return False
temp = num
reversed_num = 0

while temp != 0:
    reversed_num = (reversed_num * 10) + (temp % 10)
    temp = temp // 10

if num == reversed_num:
    return True
else:
    return False

A generator function to generate infinite palindrome numbers

def infinite_palindromes():
num = 0
while True:
if is_palindrome(num):
i = (yield num)
if i is not None:
num = i
num += 1

Main funtion which returns the 10 ** len(palindrome) to generator

pal_gen = infinite_palindromes()
for i in pal_gen:
print(i)
digits = len(str(i))
if digits == 5:
pal_gen.throw(ValueError("We don't like large palindromes"))
pal_gen.send(10 ** (digits))

Current output is :

11
111
1111
10101

ValueError

Here why palindrome numbers 101 is not getting printed?

[proven mango]

Hello everyone

I am new to Cs, I wanna start learning algorithm

What do u think is the best approach to learn algorithm

[earnest ruin]

$$

[haughty mountain]

you misunderstand how send works

send returns the yielded value and sends a value to the generator

so the first yield makes you miss the first palindrome

you're also missing 1001 and 10001

[dusty dune]

got it thanks for the help!!

[little wagon]

hello, would a heap be a good structure for ordering a graph's edges by weight? If I'm trying to implement kruska'ls MST algorithm

[vocal gorge]

why not just a sorted list?

[agile sundial]

just sort a list

[little wagon]

isn't sorting a list O(n log n) at best? I want to add the time it takes to generate the entire graph and then run the algorithm itself

[agile sundial]

creating a heap and processing all the nodes is also n log n

[vocal gorge]

yes? there's no way to comparison-sort elements in less than n log n

that doesn't affect the complexity since the rest of the algorithm is O(E log E) anyway:

[agile sundial]

because you can't merge all the edges in less than that

[little wagon]

ah well, I thought I could save the sorting time for the edges with a heap but I guess I misunderstood a heap's complexity then

[vocal gorge]

a heap takes initially O(n) time to create and O(log n) to pop an element; the nice feature of heaps is that it's cheap to insert an element into them while preserving the heap structure

[agile sundial]

||it's O(n) to create||

[vocal gorge]

so they're used when you need to repeatedly "add some stuff into the heap" and "get the lowest element". A* comes to mind, and dijkstra too I think.

[vocal gorge]

huh, hold on

[little wagon]

Actually I'm shooting for the O(E a(V)) complexity

[vocal gorge]

hmm, are all your weights integers?

[vocal gorge]

ah, makes sense. edited my reply.

[little wagon]

they may not be but I think the teacher said it didn't matter if we decided to ignore decimal places and make them integers

[vocal gorge]

if that's the case then you can use one of the linear-time sorting algorithms, like counting or radix sort.

[agile sundial]

if you use sift down rather than sift up for implementing build-heap, then you get linear

you also need to use a fancy disjoint set, where it uses path compression or path splitting

[little wagon]

yeah, we saw in class how those sets worked so I wanted to implement that.

[agile sundial]

they're pretty fun. good luck

[little wagon]

cool, I'll look into that then, thx for the help

[haughty mountain]

you can get that only if you assume your input is sorted, but yeah you want DSU

it's a fun data structure

[agile sundial]

you can use a linear time sorting algo and achieve that

[haughty mountain]

depends, not in general

well, it will be linear in the number of edges, sure

but it will start scaling in other ways

[edgy flume]

can somebody help me with some c code

[dusty bloom]

I would like to get some input on how to store and load multiple choice test. I would like to use some file-format that is both human readable/edible and machine readable. I think json is out of the question, but maybe yaml/toml or xml would do?

[honest iron]

You could do JSON, yaml, and toml in more or less the exact same structure within your code, so the decision between them falls down to your personal preferenc

All valid though

[green robin]

ight wouldnt this work??

;--;

[dusty bloom]

I'll look into yaml/toml, as I think there are not so many special characters that have to be typed in this format.

[dusty bloom]

Your error message says that max recursion depth has been reached. As a default, Python has a max recursion depth of 1000, but this can be overridden I think. Maybe the end condition isn't being met?

[green robin]

Made stupid mistakes btw, I fixed them but however, its stucking with queryRange now

[green robin]

Ill try to analyze the matter

[willow vapor]

Yoo

guys, do you think this is the most efficient way to get chat ids into a list?

def get_chats(self):
    sql = "SELECT chat_id FROM chats"
    self.cursor.execute(sql)
    return (row[0] for row in self.cursor.fetchall())```

there is only 1 element in the db

pretty simple, I was wondering if there is a way to do so with unpacking or something

[willow gust]

When learning DSA w/ Python, is it really necessary to learn to write them 'the pythonic way'? I've heard good things about Goodrich's book but some people say it's a poorly translated C++ into Python thing

[little wagon]

translating non pythonic code into pythonic code may be a good exercise I would think. It teaches you first how to write pythonic code and it also makes sure that you're not just copying the code they give you but actually understanding it.

[willow gust]

I see. So do you think that Goodrich's book on DSA in Python is a good start?

[little wagon]

haven't read it tbh, I was just thinking out loud about what I would do if heard that :P

[willow gust]

Ah okay! if you do have some DSA suggestions, feel free to send them my way 😄

[iron vector]

What is a good amount of time trying to implement a DSA problem before looking for solutions.

[opal oriole]

Infinite, try solving a different problem and coming back to it later.

Or no time, depends on your context.

[iron vector]

Right, you ruminate on a problem for some time, and eventually the solution comes to mind.

[opal oriole]

I think it's more concrete to say that you go solve some other problem because if you can't solve a specific problem in reasonable amount of time, then you probably are not ready for it and need to go practice something else first (that will help you solve that problem you could not solve before).

*This also happens within a problem. When solving a problem you often have to solve some number of more simple sub-problems.

*A certain number of examples is very useful in the beginning, but eventually you have to not look up the solutions anymore and just keep trying to solve it and solve other problems that may help solve it. Especially since unsolved non-practice problems in the real world don't have solutions to look up.

[iron vector]

Thank you @opal oriole.

[amber minnow]

any Rabin Karp experts here?

[brittle moat]

does anyone know the relevance of "value = i.ratio * unusedWeight" in this code? ```py
class Item2:

def __init__(self, weight, value):
    self.weight = weight
    self.value = value
    self.ratio = weight / value

def knapsack2(items, knapsackCapacity):

items.sort(key = lambda x:x.ratio, reverse=True) # sorting by ratio, biggest -> small

usedCapacity = 0
totalValue = 0

for i in items:
    if usedCapacity + i.weight <= knapsackCapacity: # if current weight in bag + items weight is smaller or equal
        usedCapacity += i.weight # using the item - addings its weight
        totalValue += i.value # adding item's val to totalValue

    else: # maximizing the last element to add to knapsack
        unusedWeight = knapsackCapacity - usedCapacity # weight remaining if previous item would overflow
        value = i.ratio * unusedWeight
        print("Remaining value", value)
        usedCapacity += unusedWeight # fillng up rest of bag
        totalValue += value # adding last element's value - which will be fractional

print("Total value obtained", totalValue)

knapsack2(cList, 40)

[fiery cosmos]

how do i remove contents from a list similar to how slice select a content from a list?

[amber minnow]

Does anyone have a rough estimate it takes your average laptop to generate a randomised string of Length 100 million on Python? It’s only generating ATGC in a randomised order. I’m doing it for an assignment but 100 million is the maximum limit given. I had 100k-100mil or (up to 2 minutes)

[agile sundial]

like 10 seconds probably

[haughty mountain]

with a naive ''.join(choice('ATCG') for _ in range(n)) it takes 3s to do 10M on my desktop

but you can do better since what you're really doing is generating 2 bits per letter

!e

from random import choice
import time

n = 1_000_000

start = time.perf_counter()
with open('some_file', 'w') as f:
  print(''.join(choice('ATCG') for _ in range(n)), file=f)
end = time.perf_counter()
print(end - start, 'seconds')

[halcyon plank]

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

0.5039229011163116 seconds

Files with no extension can't be uploaded.

[haughty mountain]

ok, can't run 10M here

!e and here is a slightly more clever one, hopefully 10M should work now

from random import randbytes
import time

n = 10_000_000

start = time.perf_counter()

def make_lookup():
    for a in 'ATCG':
        for b in 'ATCG':
            for c in 'ATCG':
                for d in 'ATCG':
                    yield a+b+c+d
lookup = list(make_lookup())

assert n%4 == 0
with open('some_file', 'w') as f:
    print(''.join(lookup[b] for b in randbytes(n//4)), file=f)

end = time.perf_counter()
print(end - start, 'seconds')

[halcyon plank]

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

0.22906531300395727 seconds

1 file upload (some_file) failed because its file size exceeds 8 MiB.
Files with no extension can't be uploaded.

[haughty mountain]

10M in 0.22

not shabby

let me try doing bytes rather than str

!e

from random import randbytes
import time

n = 10_000_000

start = time.perf_counter()

def make_lookup():
    for a in b'ATCG':
        for b in b'ATCG':
            for c in b'ATCG':
                for d in b'ATCG':
                    yield bytes([a, b, c, d])
lookup = list(make_lookup())

assert n%4 == 0
with open('some_file', 'wb') as f:
    f.write(b''.join(lookup[b] for b in randbytes(n//4)))

end = time.perf_counter()
print(end - start, 'seconds')

python go home, you're drunk

in any case, randbytes to generate a big chunk of random bytes is a good idea

let me run the three methods for 100M for fun

code

from random import choice, randbytes
import time

start = time.perf_counter()

def naive_choice(fname, n):
    with open(fname, 'w') as f:
        f.write(''.join(choice('ATCG') for _ in range(n)))

def randbytes_bytes(fname, n):
    assert n%4 == 0

    def make_lookup():
        for a in b'ATCG':
            for b in b'ATCG':
                for c in b'ATCG':
                    for d in b'ATCG':
                        yield bytes([a, b, c, d])
    lookup = list(make_lookup())

    with open(fname, 'wb') as f:
        f.write(b''.join(lookup[b] for b in randbytes(n//4)))

def randbytes_str(fname, n):
    assert n%4 == 0

    def make_lookup():
        for a in 'ATCG':
            for b in 'ATCG':
                for c in 'ATCG':
                    for d in 'ATCG':
                        yield a + b + c + d
    lookup = list(make_lookup())

    with open(fname, 'w') as f:
        f.write(''.join(lookup[b] for b in randbytes(n//4)))


n = 100_000_000
for method in [randbytes_bytes, randbytes_str, naive_choice]:
    name = method.__name__
    start = time.perf_counter()
    method(f'{name}.txt', n)
    end = time.perf_counter()
    print(name, end - start, 'seconds')

randbytes_bytes 1.9004504280164838 seconds
randbytes_str 1.7282409869949333 seconds
naive_choice 30.179710222990252 seconds

so not bad at all

another option, numpy

def numpy_randint(fname, n):
    with open(fname, 'wb') as f:
        indices = np.random.randint(4, size=n, dtype=np.uint8)
        nucleotides = np.frombuffer(b'ATCG', dtype=np.uint8)
        f.write(np.take(nucleotides, indices).tobytes())

numpy_randint 0.9357267509913072 seconds

that's closer to the speeds I might expect if I wrote this in C

and this is on an HDD, so on an SSD it should be a bit quicker than this

tentatively I see 0.4s for the numpy version there

@agile sundial @amber minnow I guess I should actually tag the people I'm writing stuff to 🥴

[agile sundial]

oh slower than i thought

[haughty mountain]

calling choice a ton of times isn't exactly fast yeah

one call to randbytes saves so much overhead

I feel the numpy version is probably the cleanest

though the randbytes with a lookup table has some charm, too bad it's not amazingly fast because logic in python

[fiery cosmos]

guys, how do i remove contents from a list similar to how slice select?

i'm planning to remove content similar to slice

like

slice(start:end)

like this

but for removal

[ivory yacht]

You can simply do del mylist[start:end] to delete those items from the list, with stuff after moving up to fill as normal.

[fiery cosmos]

okay, now how do i remove contents from a string?

i'm planning to remove "[" or "(" without eliminating the string entirely

[naive oak]

easiest way is probably str.replace

I'd use re.sub but that can be slightly more complicated if you don't know regex

alternatively you can turn it into a list and then do what spen said

[stray fractal]

just use str.replace() it's faster

[naive oak]

I care less about speed and more about convenience in this case

[stray fractal]

eh only 1 character saved

[naive oak]

as in it being easy to add/remove characters that get replaced

[stray fractal]

ok

it's only 2 characters for this case though

[lone moss]

Hi coders

[icy mango]

Hi

[fiery cosmos]

sup @icy mango

[icy mango]

Can someone tell me how I get python on iOS

[fiery cosmos]

Hi

[fiery cosmos]

pyto

[midnight citrus]

    def numberOfSubstrings(self, s: str) -> int:
        alphabet = [0, 0, 0]
        left = 0
        curr = 0
        global_max = 0
        for R in s:
            # Expanding the window
            alphabet[ord(R) - ord("a")] += 1

            while alphabet[0] and alphabet[1] and alphabet[2] and left < len(s):
                alphabet[ord(s[left]) - ord("a")] -= 1
                left += 1
                curr += 1

            global_max += curr
        return global_max

is this o(n) time ?

or quadratic im not sure

s would be a string containing only A,B and Cs

so like maybe worst case is something like aaaaaaabbbbbbbc and then the while loop iterates n-2 times?

so it is n^2 ?

oh wait

but the while loop itself only runs n times

not n times for each R

right?

so its just O(n)

[icy mango]

Anyone have any starter codes/ideas? My first time learning to code lol

[haughty mountain]

!kindling

[halcyon plank]

Kindling Projects

The Kindling projects page on Ned Batchelder's website contains a list of projects and ideas programmers can tackle to build their skills and knowledge.

[gleaming ferry]

228391

228391

228391

[fiery cosmos]

how do i use the str.replace?

like i'm planning to remove all "[" from a string

exaple: "[[2d6", "[d20"

i want to make them become "2d6" and "d20"

[lilac cradle]

anybody know a way i can do dunders like add,sub,etc without having to copy the same code over and over but just change the op?

https://paste.pythondiscord.com/woleqopetu
here's my vec2 class, it works but it's very lengthy

like instead of

    def __add__(self,other):
        return vec2(self.x+other.x,self.y+other.y)
    def __sub__(self,other):
        return vec2(self.x-other.x,self.y-other.y)
    def __mul__(self,other):
        if type(other) in (int,float):
            return vec2(self.x*other,self.y*other)
        return vec2(self.x*other.x,self.y*other.y)

i'd like something like

    def __add__(self,other):
        return self._op("add",other)
    def __sub__(self,other):
        return self._op("sub",other)
    def __mul__(self,other):
        return self._op("mul",other)
    def _op(self,op,other):
        #do something
        pass

unless someone knows a better way?

[stable pecan]

you can do something like:

from operator import mul, add, sub, neg


def binary_vectorize(op):
    def vect_op(a, b):
        return type(a)(op(a.x, b.x), op(a.y, b.y))

    return vect_op

def unary_vectorize(op):
    def vect_op(a):
        return type(a)(op(a.x), op(a.y))

    return vect_op


class Vec2:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return f"Vec2({self.x}, {self.y})"

    __mul__ = binary_vectorize(mul)
    __add__ = binary_vectorize(add)
    __sub__ = binary_vectorize(sub)
    __neg__ = unary_vectorize(neg)

[lilac cradle]

huh, this works?

[stable pecan]

yep

also your __reversed__ method isn't exactly what is intended

[lilac cradle]

ah ok

[stable pecan]

sometimes there's a __iter__ method that returns an iterator over your class, and __reversed__ would be that iteration reversed, e.g.,:

...
def __iter__(self):
    yield self.x
    yield self.y

def __reversed__(self):
    yield self.y
    yield self.x

[stable pecan]

the functions only consider vector operands, so you'd have to modify it a bit if you want to use a numeric operand

[lilac cradle]

i'll work on it yeah

thanks

[stable pecan]

np

[lilac cradle]

would importing the function module in the class be bad practice? it's not super important but i'd like to be able to just paste it without having to worry about imports

not function, i mean the operator module lol

[stable pecan]

yeah, you'd end up with some class methods that you probably don't want

class Vec2:
    from operator import sub


print(Vec2.sub(1, 2))  # -1

[lilac cradle]

i guess i could put it in the actual function to do the ops but eh

i'll just import operator lol

also nice work on your terminal stuff, i wanna make something like you have

[stable pecan]

thanks

[fiery cosmos]

.

i need help here

[robust dagger]

s.replace("[", "")

[lilac cradle]

the only thing i don't like (this might just be me being a bad dev) is the separation of things into a million scripts, but it's p good

[fiery cosmos]

thnx

[lilac cradle]

if you need multiple characters there also translation

it's kinda weird syntactically since it uses character codes (there's a method to make a translation table tho) but it's a lot simpler than doing .replace().replace().replace()

[fiery cosmos]

the problem is that this method is not working for my program

[lilac cradle]

translate isn't?

[fiery cosmos]

it's suppose to remove the ( here

but it's not working

[lilac cradle]

well if you're doing this that's replacing '[' and not '('

[fiery cosmos]

if "[" in inp:
            inp.replace("[", "")
            print(inp)
        if "]" in inp:
            inp.replace("]", "")
            print(inp)
        if "(" in inp:
            inp.replace("(", "")
            print(inp)
        if ")" in inp:
            inp.replace(")", "")
            print(inp)

[lilac cradle]

you don't really need to check if it's in it

[fiery cosmos]

i made a situation for each

one for a [

one for a (

and their final

[fiery cosmos]

yep, but i modified and placed it to each situation

[fiery cosmos]

and as you can see it still keeps the (

[lilac cradle]

translation_table = str.maketrans({"[":"","]":"","(":"",")":""})
inp = "[]()ab[c[d]e(f)"
print(inp.translate(translation_table)) #abcdef

so maketrans works using a dict

the key is the thing you wanna replace, and the value is what you replace it to

translation_table = str.maketrans({"a":"x"})
inp = "abcdefg"
print(inp.translate(translation_table)) #xbcdefg

you don't necessarily need maketrans but it's a lot simpler since string.translate uses character codes like i said

like without maketrans the same translation would be print(inp.translate({97:"x"})), and idk about you but i don't have the character code for 'a' memorized lol

[robust dagger]

.replace does not modify the string (strings in Python are immutable). Instead it returns a new string.

You can instead write something like:

inp = inp.replace("[", "")
inp = inp.replace("]", "")
inp = inp.replace("(", "")
inp = inp.replace(")", "")

or you can put it all in one line with:

inp = inp.replace("[", "").replace("]", "").replace("(", "").replace(")", "")

Or you can switch to something like .translate or regular expressions.

[lilac cradle]

also this is a really cool way of doing it, thanks for this
I never would have thought of returning a function and then assigning it, maybe with a dict, but not like this

[haughty mountain]

||if only we had a preprocessor||

[opal oriole]

||Or even better, hygienic macros (there are still things to learn from LISP).||

[haughty mountain]

but cpp already fits with python

https://asciinema.org/a/qvzv4kx5JSnAI2CdVtFC3Vt5c

[idle pier]

not sure if this is the right channel for this but any good CS books you folks recommend?

[fair elm]

Hello

Can someone tell me why my server is rejecting hashlib?

Hello Can someone tell me why my server is rejecting hashlib?

Anybody?

[wraith knoll]

is it possible to download app apk through python?

🤔

[amber minnow]

Thank you

[fiery cosmos]

I mean, yeah, if its uploaded somewhere, you can just use requests module, however this question is not kinda related to #algos-and-data-structs

[fallow orchid]

guys can ya'll check my question about heap deletion i posted it in a help channel

[robust dagger]

Looks correct to me.

[fallow orchid]

thanks bro

[fiery cosmos]

!e
args = "(d5"

num = args.count("(")

print(num)

[halcyon plank]

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

1

[floral pine]

How can heapify be O(n)?

My understanding is every insertion to a heap is O(logn), but that's only worst case. Average case insertion is O(1)

So while heapify is worst case O(nlogn), it'll be average case linear?

[fiery cosmos]

!e
args_result = ["((d20", "d6"]

if "(" in args_result:
print("detected")
else:
print("not detected")

[halcyon plank]

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

not detected

[fiery cosmos]

okay, what am i doing wrong here?

[floral pine]

When you do if "(" in args_result:

args_result is a list, not a string

so it compares each list item to "("

you're essentially asking if "(" == "((d20"

[agile sundial]

there's a very good stack overflow article that you can find if you Google that exact question

[floral pine]

or "(" == "d6"

[floral pine]

gotchu

[fiery cosmos]

my plan was to search if there is "(" in "((d20"

not "(" == "((d20"

[floral pine]

then you want to do the if "(" in __ for everything in the list

though the way you implement this will depend on what args_result is

as in - if it can be a list of arbitrary length, that means you have to check for every item in that list

if it's always going to just have 2 items, then just check for those two

[fiery cosmos]

nope, it's not just 2 items

but variable items

can be 1

can be 5

can be 7

[floral pine]

then you want something like

for whatever in args_result:
  if "(" in whatever:
    print("detected")

[floral pine]

Just to answer my own question - It's because there are two implementations for building a heap.

1. siftDown
2. siftUp

Heapify uses siftDown which builds the heap from bottom-up, which is O(n). This is possible when given a list that we want to heapify, meaning we already know the number of elements and can build from bottom-up. Building from bottom-up means less "corrections" need to be made to re-order the heap.
The siftUp implementation is more akin to starting an empty heap and inserting each element individually, which is O(nlogn).

Which is why Python's heapq.heapify(list) is O(n).

Cool

[chrome veldt]

How to get started with dsa

[amber minnow]

Finally Done it!

realised how simple to do this after banging my head at it for 4 weeks!

Instead of generating random DNA every time I run the program just create a script that will generate a text file like this:

49 7
TGCTGGCCGAGAGGCCGACCCAATGAGGTGTAACCGCTTCGAGTCGTTT
5 5 TCGAG 2 GTAGA
3 4 GTT 1 TCGC
4 5 TCGC 3 TAGCT
5 4 TTCGT 4 CCAC
4 4 CCCA 2 CGCG
3 3 GCA 3 GAC
5 5 GAGTC 5 CGTGC

[slender sandal]

Wow find and load are that different?

[amber minnow]

thats only for 10 insertions

[slender sandal]

But why is it any different

Actually pulling the strands takes time?

[amber minnow]

load increases as the DNA string is getting bigger after each insertion. it starts at 100k and every time a restriction enzyme is found it will insert a modified strand to it

[slender sandal]

Oh huh

[amber minnow]

I have to do this test on 100 insertions and 1000 insertions

then do the same tests with 2 other data structures

1 being a linkedlist method and the other with Rabin Karp Algorithm to hash

[slender sandal]

Should take you around half a minute for the thousand insertions

Perhaps more of you're not utilizing multiprocessing

[amber minnow]

im not

[slender sandal]

You could, couldn't you? You're measuring three different operations

[amber minnow]

purely for a Introduction to Algorithms assessment

[slender sandal]

Yeah but waiting seconds between tests is a big deal for me lol

[amber minnow]

yeah you should meet my prof

[vocal gorge]

is that right? 0.05s*1000 is 50s already, plus the previous 999 insertions

[amber minnow]

hes given us a range to use from 100k-100mil

I havent bothered with 100 mil because its too slow to do that with a Naive Dynamic Array

plus my vivobook will melt

[slender sandal]

Oh right I thought 0.30 meant 30 over 1000

[amber minnow]

yeah when a insertion is made it will then search through the string for other restriction enzymes till theres nothing left then it will move onto the next target restriction enzyme

49 7
TGCTGGCCGAGAGGCCGACCCAATGAGGTGTAACCGCTTCGAGTCGTTT
5 5 TCGAG 2 GTAGA
3 4 GTT 1 TCGC
4 5 TCGC 3 TAGCT
5 4 TTCGT 4 CCAC
4 4 CCCA 2 CGCG
3 3 GCA 3 GAC
5 5 GAGTC 5 CGTGC

Like this example:

49 is the original length of the DNA strand
7 is the number of restriction enzyme inserts
5 5 TCGAG 2 GTAGA
5 is the length of S1
5 is the length of S2,
TCGAG is S1
I is the index of S1 where the insertion is going to take place
and S2 is the insertion enzyme

so if you have a strand of 100k that will end up finding more restriction enzymes after inserting just one.

the algorithm takes the account of if it finds another restriction enzyme after the inserion beyond it it will then do that one too.

[slender sandal]

Linked list?

Oh still dynamic array

What has changed?

Just sample?

[pallid cape]

I could use some hel[p

[cloud iris]

Hey guys! I'm doing some research for my comp sci class, and my topic is entropy in machine learning systems. I have a few specific topics written down, but I'm not sure if they make sense or not. LOL. (Idk much about ML so a lot of this is just me merging cool topics together)

1. Evaluating the impact of entropy in deep generative models: insights into latent space learning, Representation, and Data synthesis quality
2. Boltzmann Machines and thermodynamic principles: understanding the connection between entropy and stochastic optimization in unsupervised learning systems
3. Entropic forces in self-organizing networks: the emergence of complexity and robustness in learning systems
   Do any of these stand out? Any of them seem like they have potential?

[dusky trellis]

how do you even measure entropy in a neural network?

[eager hamlet]

looking at this commit which supposedly fixed the dijkstra's
can anyone telll me what was wrong with it initiallly
it seems to add checks for if a new & improved state was added and skip old states that were added to the pq
but i'm not sure if w/o this the algo would WA or any ting
https://github.com/SansPapyrus683/USACOSols/commit/941b08cd0db3f79fc80d37b9fcbccfb074c7dfc3

[robust needle]

Is Prim's algorithm a type of decrease and conquer?

[robust needle]

Also, regarding Dijstra's Algorithm, why is it neccesary to store the so called 'parent' node?

[agile sundial]

to reconstruct the path

[potent light]

i feel like i could ask this here because i feel like a list is a data structure. im sorry if im wrong im still learning. I have to write code for an assignment but I am so confused on how to access the data and use the data in a list . this is the chapter that we are on. I was out for health reasons and have no idea what to do and need help fast.

[snow anvil]

value = List[index]

Is how you extract data from a list the other stuff is too vague to answer

@potent light

You need to be more precise with your questions I have 0 idea where you are trying to access data from

[agile sundial]

a list, duh

[haughty mountain]

as mentioned, it's to reconstruct the path, but it's really not necessary

if you don't care about the path you can just not store it

and you can reconstruct the path without the parent anyway

[snow anvil]

Well I answered that one guess I shouldn't read questions while in a lecture

[meager temple]

Is there anyone who can help me regarding structures? I'm having serious trouble with different search trees ..

please, if there is someone who can help me, please tell

[fierce meadow]

Ask your question don’t ask to ask

[meager temple]

it is quite a task, might have to send the file. i'm having trouble finding why my bst is not working. it is adding nodes and when removing, it gets super scrambled and actually i've found it is adding nodes which shouldn't be added, since they're already in the tree

[fierce meadow]

Send code

It’s not in English….

[meager temple]

the fact is that the trouble is only regarding removals. but as far as i'm concerned, it's correct

I can translate tho

here it goes

[floral pine]

Been trying to think of good ways to solve this leetcode question - https://leetcode.com/problems/design-most-recently-used-queue/description/

Not sure how I should approach this

so that fetch() can be faster than O(n)

[meager temple]

so... no one?

[fiery cosmos]

im starting my own math lib for c++ but im planning it out in python first. first time writing python properly in a while: would y'all say this is clean enough for defining functions?

import math 

def pythO(missingSIDE, side1, side2):
    missingSIDE = math.sqrt((side1**2) - (side2**2))
    #finds the Opposite side of a rightangle triangle with
    #the other two side using Pythagoras' theorem
    return missingSIDE

def pythH(missingSIDE, side1, side2):
    #finds the Hypotenuse side of a rightangle triangle with
    #the other two side using Pythagoras' theorem
    missingSIDE = math.sqrt((side1**2) + (side2**2))

    return missingSIDE

def pythA(missingSIDE, side1, side2):
    #finds the adjacent side of a rightangle triangle with
    #the other two side using Pythagoras' theorem
    missingSIDE = math.sqrt((side1**2) - (side2**2))

    return missingSIDE

[eager hamlet]

https://github.com/SansPapyrus683/USACOSols/commit/941b08cd0db3f79fc80d37b9fcbccfb074c7dfc3
looking at this commit (the first file) which supposedly fixed the dijkstra's- scroll down a bit
can anyone tell me what was wrong with it initially
it seems to add checks for if a new & improved state was added and skip old states that were added to the pq
but i'm not sure if w/o this the algo would produce a wrong answer or anything of the sort

[vocal gorge]

i feel like this stuff isn't worth having functions for. also, naming convention here is against pep8. Also, why is your return one of the arguments?

[mellow mirage]

hello

anyone has any tip to remember the algorithme of "tri" or changing between bases

cuz everytime i try to remember them i forgot them the next day

any tips pls ty $

[eager hamlet]

in c++ you can pass to functions by reference

this includes numbers

[vocal gorge]

i know, but it's not c++ :p

and even in c++, it'd be pretty weird to do that with a float; not like you're winning any allocations there

i guess maybe as an overload

[eager hamlet]

who knows lmao

[haughty mountain]

idk why, but pythA and pythB being identical is kinda amusing

[robust needle]

Hi does dijkstra's algorithm break on negative edges?

I know it doesn't work on negative edge cycles but it should work on negative edge weights, right?

I was looking it up and on GeeksForGeeks, i found a page showing it doesn't work. but the examples seems...wrong???

this is the graph

after processing A, then B, when it processes C, shouldn't it find the shortest path from A to B, via C?

[floral pine]

holy moly ok I solved it and now I understand how

was definitely not an easy one

[eager hamlet]

dijkstra stops as soon as it goes to b

(assuming b is the destination)

[fiery cosmos]

wouldn't you be passing a 64 bit ptr to a 32 bit number in that case and actually losing out? 😄

[haughty mountain]

correct. negative edges are fine, negative cycles are not

[haughty mountain]

it's objectively bad yeah

larger thing passed, behind a reference

worst of both worlds

[inner marten]

dijkstra's doesn't work with negative edge-weights, at least plain dijkstra's

negative edge weights breaks the greediness of dijkstra's

[haughty mountain]

hmm, you're probably right

[inner marten]

you can offset the edge weights with the absolute value of the greatest negative edge weight to make them all nonnegative

then shift it back over hwen you're done

otherwise it doesn't work

[haughty mountain]

this would be a counterexample I guess

   10  -9
A---B---C
\______/
    5

[inner marten]

the proof of dijkstra's relies on the invariant that when you extract a node from the priority queue, the shortest path to that node has been found which you can easily find a counterexample to w/o the need for negative weight cycles

[eager hamlet]

bump?

[haughty mountain]

"if the cost of the state I'm looking at isn't the best cost I know at this node, then it can't be optimal so it's garbage"

[eager hamlet]

would removing it cause the algorithm to produce a wrong answer for some inputs?

i know it causes a performance hit

but does it still work

[haughty mountain]

it shouldn't cause wrong answers assuming the algo is right overall

[eager hamlet]

(also i just realized i'm asking about java code in a python server, sorry about that)

[haughty mountain]

it will just be slow

in this problem you always put the same or 1 higher weight back into the priority queue, right?

if so you can actually solve it without a priority queue

you can use a deque and add either to the left or right end depending on if it's +0 or +1

[eager hamlet]

actually

i think it's a bit diff bc of how java pq comparators work

who knows

[robust needle]

isn't the example I showed an example of negative edge weights?

or does it mean dijkstra's works if i don't specify an end_node, and it just tries to explore all of them?

[echo hawk]

if i have a list of dicts, e.g. [{date: datetime(..), open:float, close:float high:float, low:float, volume:int}, ...] what is the best method to create a pandas dataframe out of this rows?

[haughty mountain]

I did remember it wrong, look up in here a tad

[vocal gorge]

wouldn't just pd.DataFrame(list_of_dicts) work?

[echo hawk]

you're right, it works! thanks.

[tawny tulip]

https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/submissions/936280786/

Hi, for this LeetCode question memomized approach gives TLE but brute force approach passed all testcases. Why??

Brute force:

class Solution:
    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        lengths=[]
        
        def zigzag(node , direction=None):
            nonlocal lengths
            if node==None: return 0
            
            x=zigzag(node.left, 'left_child')
            y=zigzag(node.right, 'right_child')
            lengths+=[x,y]
            
            if direction=='left_child': return y+1
            elif direction=='right_child': return x+1

        zigzag(root)
        return max(lengths)

Memomized:

class Solution:
    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        lengths=[]
        dp={}

        def zigzag(node , direction=None):
            nonlocal lengths
            if node==None: return 0
            
            try: x=dp[(node.left, 'left_child')]
            except: 
                x=zigzag(node.left, 'left_child')
                dp[(node.left, 'left_child')]=x
            
            try: y=dp[(node.right, 'right_child')]
            except: 
                y=zigzag(node.right, 'right_child')
                dp[(node.right, 'right_child')]=y
            lengths+=[x,y]
            
            if direction=='left_child': return y+1
            elif direction=='right_child': return x+1

        zigzag(root)
        return max(lengths)

hmm...If I use if-else instead of try-except then it is passing all test cases....

so is try-except slower than if-else?

[robust dagger]

It used to be true (I don't know if still is) that if the two branches of the if were about equally likely, then if was faster than try; but if the except was rare, then try was faster than if. But I don't remember the exact code I used to test this behavior, and besides, I did this years ago.

[tawny tulip]

but if the except was rare, then try was faster than if

So...recovering from exceptions are extremely slow...?...

[sullen lance]

any way to get a graph like this

[haughty mountain]

wait, what would the memoization even help with?

isn't the "brute force" linear time already?

and you can't do better than linear time

[tawny tulip]

Hmm....Now I got it! All elements of this tree are unique so there's no overlapping subproblems. No subproblems=No memomization.

Stupid me forgot the first rule of dp🤦

[lilac cradle]

does anyone have any examples of stuff like game ai (like, say, the ghosts in pacman), or just pathfinding (like a*) in general?

i’m just not really sure how to go about coding AI and pathfinding (not like actual ai obviously lol)

[twilit spear]

is anyone comfortable with big OH?

[haughty mountain]

you know what you want to show right?

f(n) is in O(g(n)) if for all n ≥ N, there exists a constant c such that f(n) ≤ c g(n)

in my head I kinda prefer to consider f(n)/g(n) ≤ c

[vocal gorge]

the screenshot looks correct to me albeit circuitous; I'd just do c=7 and show that 6n+5 < n^2 for n>10 or whatever

(that's assuming I can't use the alternative definition that f(n) is O(g(n)) if lim f(n)/g(n) is finite, which would be easier - clearly the limit of (6n^2+6n+5)/n^2 is 6)

[haughty mountain]

(6n² + 6n + 5)/n² = 6 + 6/n + 5/n²

[robust needle]

Hi, sorry i'm a bit lost again with dijkstra's and bellman-ford algorithms ;-;

[haughty mountain]

which is clearly bounded by a constant

[robust needle]

So, Dijkstra's works on negative edge weights but breaks on negative edge cycles?

[haughty mountain]

no, it was pointed out negative edge weights breaks Dijkstra

[vocal gorge]

dijkstra doesn't support negative weights I think

and nothing supports negative edge cycles because they make the very notion of minimal distance undefined

since you can circle along a negative cycle an arbitary number of times, decreasing the distance however close to negative infinity you want to get

[haughty mountain]

depends on what you mean by support

[robust needle]

okay where does dijkstra's mark a node as processed?

[haughty mountain]

-∞ is a sensible answer

[robust needle]

because I thought it's after it processes the neighbouring nodes

like here, why would it stop at B?

because I thought the way these single-source path algorithms work is first fully processing the graph, then backtracking by the parent attribute of the end_node

[haughty mountain]

apparently there are two variants of Dijkstra

the traditional one does not consider a node twice

[robust needle]

wait WHAT

[haughty mountain]

when you're done with a node you're done with it forever

[robust needle]

is a node 'done' when it's been checked as a neighbour or when it's neighbours are done being checked?

[haughty mountain]

the first time it's picked from the top of the priority queue

much like in a bfs on an unweighted graph

the first time you encounter a node, it's at the shortest distance

(assuming no negative edges)

[robust needle]

okay so in that process, the graph above would process A, then B and then C

but since B is already processed, the new path A-C-B would be ignored?

[haughty mountain]

correct

[robust needle]

okay then the way we've learnt the algorithm is a bit different

we only use the unexplored_nodes set or whatever to see when to stop the algorithm, not as a check (like in BFS)

i could show my code if that helps?

[haughty mountain]

bfs and Dijkstra are equivalent on unweighted graphs

which might be useful to recognize

[robust needle]

oh wow

did not realise tha

[haughty mountain]

(actually dfs, bfs and Dijkstra follows the same template)

dfs uses a stack
bfs uses a queue
Dijkstra uses a priority queue

the rest of the code should be basically identical

[robust needle]

i see

[haughty mountain]

in the unweighted case a queue ends up naturally having things in sorted order

which is one way to see that Dijkstra reduces to bfs

[fiery cosmos]

hi guys

anyone here knows system design and analysis

[robust dagger]

Compared to an if statement, yes. With an if statement, you have to test the condition and take a branch, but that's it. With a try statement, you have to set yourself up to potentially handle an exception. If there turns out to be no exception, then it's hardly any work; just record where the try happened. If there is an exception, then Python has to create an exception object and find the handler, and that's more expensive than an if.

[ebon ocean]

Hi there I'm using Thistlethwaite's algorithm in a Rubik's Cube solver, however I've been having some issues when it comes to more complex patterns as it stops responding. I'm wondering if anyone can see any errors I've made as I'm guessing the solver is the issue.

https://paste.pythondiscord.com/emefohokuw

If you need any other parts of my code just ask.

[full current]

Could anyone comment inside https://www.reddit.com/r/learnpython/comments/12soxsd/adjacency_matrix_code_snippet/ ?

[ebon ocean]

Nvm figured out my issue, it was in error handling bit within the cube itself, gonna hand this as coursework wish me luck

[fiery cosmos]

i corrected it after i realised

[robust needle]

Hi everyone. I'm learning best-first search and I have some questions because i'm a bit confused on how the algorithm operates

1. Is this algorithm capable of backtracking?
2. If I don't really have a good heuristic function, are they some 'boilerplate' ones that are useful?
3. When is Best-first better than BFS & DFS and when isn't it?

[keen wadi]

Hi

[vocal gorge]

Best-first searches are a whole category of algorithms, the one most well-known of them, AFAIK, is A*.

For A* there's a simple condition for the heuristic: https://en.wikipedia.org/wiki/A*_search_algorithm

If the heuristic function is admissible – meaning that it never overestimates the actual cost to get to the goal – A* is guaranteed to return a least-cost path from start to goal.
[...]
If the heuristic h satisfies the additional condition h(x) ≤ d(x, y) + h(y) for every edge (x, y) of the graph (where d denotes the length of that edge), then h is called monotone, or consistent. With a consistent heuristic, A* is guaranteed to find an optimal path without processing any node more than once

3. When is Best-first better than BFS & DFS and when isn't it?
   For one, I don't think one can generally run BFS/DFS on arbitrary graphs, unless your distance measure is the number of edges traversed.

A* generally is better (explores fewer nodes) than undirected searches. For example, this is A* (left) and Dijstra (right) on a grid with obstacles:

[haughty mountain]

on the other hand A* requires you to have some decent admissable heuristic

and you can totally run BFS and DFS on any graph

but BFS will only encounter nodes in distance order if the graph is unweighted

(and DFS has no such guarantees)

I guess as a general point, if you have an unweighted graph, using Dijkstra over BFS is just wasting effort

if you have a good heuristic, you can slap it on top of either BFS or Dijkstra and get something like A*

but you would lose the niceness of not having to deal with a priority queue in BFS

[distant otter]

https://stackoverflow.com/questions/76075412/matplotlib-spiral-from-three-arguments-length-gap-padding-using-numpy-and-ma please take a look

[soft apex]

can anyone here help me with an assignment?

its just one question

[dusky trellis]

no one can help you until you ask your question

[fiery cosmos]

I mainly code in c++ but I've been warming up to writing algorithms in python recently!
Here is one:

# file to get binomial coefficients, count the even sums, and print out results
# author: a cute trans girl

# Implementation of lucas's theorem
def Lucas(n, k, prime):
    if k == 0:
        return 1
    ni = n % prime
    ki = k % prime
    if ni < ki:
        return 0
    num = den = 1
    while ni > 0:
        niq, kiq = ni // prime, ki // prime
        num *= 1 if niq == kiq else -1
        num *= ni % prime
        den *= ki % prime
        ni, ki = niq, kiq
    return num * pow(den, prime-2, prime) % prime

# Retrieve all coeffeints in the given row using the Lucas theorem
def GetRow(row_index):
    row = []    # We store coeffients here
    prime = 1000000007    # Default Prime for the Lucas theorem 
    for k in range(row_index):
        coeff = Lucas(row_index-1, k, prime)
        row.append(coeff)
    return row

# Process list of coeffients to find evens
def CountEvenSums(row):
    count = 0
    for i in range(len(row)):
        for j in range(i+1, len(row)):
            if (row[i] + row[j]) % 2 == 0:
                count += 1
    return count

# Get binomial coefficients for every input case and count even sums
cases = int(input()) 
for _ in range(cases):
    n = int(input())
    row = GetRow(n)
    even_count = CountEvenSums(row)
    print(even_count % 10e9)```

If there are any improvements i can make do let me know

[haughty mountain]

is count evens just the number of pairs with even sum? you can do that in a smarter way

n_odd*(n_odd-1)//2 + n_even*(n_even-1)///2

[haughty mountain]

also wait, does this even work properly?

Lucas's theorem gives you coefficients mod the big prime and after that you check odd/even

n%p%2 = 0 doesn't mean n%2 = 0

e.g. p=5, n=15

if you want the odd/even result you would need a prime divisible by 2

(i.e. 2)

[main canyon]

Hey, is there anyone how could help me with creating a lattice structure to visualize a cell size gradient? I've got the code so far, however I don't know how to implement the lattice structure as a body to realize it...

[midnight citrus]

is bottom up dp usually faster than top down?

cuz its kinda hard for me to visualise a bottom up approach for most problems

[fiery cosmos]

Ive only gotten the desired solution from two algorithms
Lucas'
And finding the coefficients manually via recursion :/

I tried other methods but none got the right answer for some reason

[haughty mountain]

if you actually want to check whether the coefficients are even/odd the thing you have now shouldn't work

[fiery cosmos]

Im checking for how many even sums are in the row

Not how many even / odd numbers

[haughty mountain]

still, working mod an odd number loses all information about odd/even

[fiery cosmos]

But it outputs the correct answers 😭

Here is the problem

I didnt write the notes on it

[haughty mountain]

like, is 1000000007 + 0 even?

mod 1000000007 that's 0 + 0

[fiery cosmos]

its just there for when the number is too large

Read the statement in the output section

[haughty mountain]

oh, they actually ask for even/odd modulo 10**9 + 7

[fiery cosmos]

Yup

[haughty mountain]

that's a very weird thing to ask for :/

[fiery cosmos]

Its p standard in programming competitions actually

For these kinds of problems

Notice that the input can be 10^18

My algorithm doesn't work for such huge number sadly so im still workshoppinh it in c++ instead of python

[haughty mountain]

values more 10**9+7 is normal, odd/even after taking that mod is the weird thing

[haughty mountain]

lol, that won't help

10^18 is way way too big of a number

[fiery cosmos]

I know it didn't work still LMAO
Im gonna read more into the maths theory of Pascal's triangle

In hopes of finding a more efficient way to calculate it

[haughty mountain]

you can't calculate a full row

too expensive

[fiery cosmos]

Yeah ik

Maybe i can find some maths magic trickery somehow

To calculate the result via a formula

[haughty mountain]

if the question had just been to count the number of zeroes mod p I know how to do that quickly

pascal's triangle mod a prime looks like a variant of a sierpinski triangle

[fiery cosmos]

Im gonna grill the shit out of chat gpt first before i start reading

I already did that last night not but no luck cuz i ran out of queries for gpt4 lmao

[fiery cosmos]

Yeah its related i was gonna look into it first

[haughty mountain]

isn't gpt pretty terrible at math and logic?

[fiery cosmos]

It kind of is but I've found ways around it

[haughty mountain]

I suspect diving into how pascal's triangle looks mod p is the thing you need

there is a bunch of redundant information that can be abused

[fiery cosmos]

How i solve logic questions using chat gpt:
first phase: bully it to write shitty code, by making it write the algorithm incrementally one step at a time, the resulting code will be extremely ugly

second phase: make it refactor and optimize the code and hope to the gods it doesnt misunderstand the point of the code with given context, because you cant do this on the same thread that you did phase one with
you have to create a new thread, give it the written context, and ask it to use the shitty code as a template to work off of

This was more for gpt3.5
Ive had much better luck and less time was consumed using gpt4

[haughty mountain]

try solving https://projecteuler.net/problem=148

[fiery cosmos]

Yes sirrr

I'll solve it once im home

[haughty mountain]

I suspect you can use similar insights to solve your problem

the project euler problem should be the easier one

[fiery cosmos]

Gotcha

[haughty mountain]

you can solve it in O(||log(n)||) time

[snow anvil]

Idk how programming languages handle stuff like this but taking the last binary digit would be easy. This is probably not helpful tho

I don't even understand the question tbh

[fiery cosmos]

lmaao
n is the number of the row

[snow anvil]

Don't mind the ramblings of the deranged

[fiery cosmos]

I think I may have found a solution using binary bit manipulation tho

it processed 10^18 in basically O(1) time😭

Im just not sure if the answer is correct for anything aside from the samples

so Im gonna have to solve some more rows by hand just to make sure

naaaaw its not correct

reading it is

[fiery cosmos]

!e
x = [1,1,3,5]
y = [4,2,7,5]

if x.count() == y.count():
print("worked")
else:
print("not worked")

[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 4, in <module>
003 |     if x.count() == y.count():
004 |        ^^^^^^^^^
005 | TypeError: list.count() takes exactly one argument (0 given)

[fiery cosmos]

okay i seems that count is not the best to count how many stuffs is in a list

anyone know something that can work as i intended?