#algos-and-data-structs

1 messages Β· Page 97 of 1

austere sparrow
#

!e

def cache(f):
    memo = {}
    def new_f(x):
        if x in memo:
            return memo[x]
        result = f(x)
        memo[x] = result
        return result
    return new_f

@cache
def fib(n):
    if n <= 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

print(fib(50))
halcyon plankBOT
#

@austere sparrow :white_check_mark: Your eval job has completed with return code 0.

12586269025
austere sparrow
#

(If you're not familiar with decorator syntax)

def _fib(n):
    if n <= 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)
fib = cache(_fib)
#

and in fact, that thing already exists in Python:

import functools

# python3.9+
@functools.cache
def fib(n):
    if n <= 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

# before 3.9
@functools.lru_cache(maxsize=None)
def fib(n):
    if n <= 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)
#

@feral wadi

feral wadi
#

umm @functools.cache a syntax?

austere sparrow
feral wadi
#

i've never used that one

austere sparrow
#

If you're not familiar with decorators:

@decorator
def f(x):
    ...

is the same as:

def _f(x):
    ...
f = decorator(_f)
#

@feral wadi

feral wadi
#

yeah i get that now

#

i wanna get good in algos but most of the time i fail to recognize a problem

fiery cosmos
austere sparrow
hoary bronze
#

hello guys is there anybody using Leetcode for problem solving

true steeple
#

Hello everybody, I was wondering how to create a matrix of 24 rows and 6 columns in Python , cuz as much as I look on google or books are simple arrays

agile sundial
#

yeah you'd know how to do it if you knew how to do it @mystic basin

static coral
true steeple
#

Thanks guys, I solved it, I come from programming in C , Java and JS, and I do not like that a matrix is something not incorporated in pure python .

keen turtle
agile sundial
#

does C have a matrix structure?

keen turtle
#

or you could use numpy

keen turtle
#

I've attended Olympiad in Informatics and had to use C++ in such contests......

#

When I have to use matrices, I need to write a class on my own...

lean dome
#

C and C++ and Java have two-dimensional arrays, which you could use as a matrix

true steeple
#

in C

lean dome
#

a two dimensional array.

keen turtle
#

there are indeed multi-dimensional arrays

#

but there are no algorithms related to that

#

such as matrix multiplication, fast power and stuff.

lean dome
#

right. A two dimensional array is one potential way to represent a matrix's data, but it is not itself a matrix.

#

A one dimensional array is also a way to represent a matrix's data.

keen turtle
#

I wonder why don't they use python instead of C++ in OI contests(

#

is there a "Graph" structure in python's standard library?

#

or in any libraries I could download with pip

#

(the Graph in graph theory

lean dome
#

networkx

agile sundial
#

speed, mainly

keen turtle
#

Oh, Thx!

lean dome
#

which is limited, but can traverse a DAG in dependency order.

keen turtle
#

hmmm, I see

#

so the graphlib is using dictionaries as graphs

keen turtle
#

importing numpy takes something like 2.77s

#

and a common OI problem has a time limit of at most 1s.

lean dome
#

that doesn't matter as long as everyone's using the same language - they can just adjust the limits accordingly.

#

but in competitive programming situations where you can choose the language you use, you probably shouldn't choose Python if your competitors can use C++

keen turtle
#

yeah

lean dome
#

it's pretty common for a bad C++ algorithm to run faster than a good Python one.

keen turtle
#

C++ is fast indeed

#

but it's also pretty difficult to get along with(

lean dome
#

and #include <bits/stdc++.h> is pretty close to from * import *, heh - handy for reducing typing when time is on the line

keen turtle
#

C++ even has optimise(2) or optimise(3) to increase its speed

#

#include command does the import operation when compiling

#

(while python does no compiling work

wraith valve
#

yeah u can tell the complier to optimize ur code

winter solar
winter solar
sage coral
#

How difficult is a monte carlo tree search and does anyone have any good resources on them?

keen turtle
#

I guess "Monte Carlo" is a sort of random algorithm

#

and I'm pretty bad at random algorithms, so maybe I can't help you (sad

meager verge
#

Hello, I have a stupid question about arrays, can i ask it here ? ^^

frank zinc
#

yes

winter solar
upper holly
#

I have a question about json.loads(). I guess everyone has experienced once, but I can't find a solution...

import json

jsonString = '{"employees": [{"name": "John Watson", "dateOfJoin": "01/01/2018", "active2": True, "awards": None}]}'
_json = json.loads(jsonString)
print(_json["employees"][0]["name"])
```raises```arm
JSONDecodeError("Expecting value", s, err.value) from None

I have no idea what wrong.
Thanks in advance!

trim fiber
#

JSON notation uses rather true and null

upper holly
#

lol thanks so much

trim fiber
#

Your welcome

fiery cosmos
#

hi

hoary bronze
#

hi guys , my recursion with memoization was working fine but suddenly it broke and it raises an error like " RecursionError: maximum recursion depth exceeded in comparison " , i dont understand what did change before the last time because in last time it worked fine , with same input and same func .. Can anybody tell me what happened

fiery cosmos
#

Hello guys

frosty ocean
# 
for dictionary in db_list:
  for key, value in dictionary.items():
    print(key, value)

what is a better way to do this?
i have a list of dicts in my db
id like to iterate through them and get the key and value of each dict

this code works, but is there a... nicer? way to do it?

quasi oracle
#

@sleek shale We don't allow recruitment here

rotund prism
scarlet maple
paper yacht
#

how do i send a mail to HackerRank support regarding a correction?

fiery cosmos
#

hey guys

#

i want to find number of "x" in my output

#

the output is like :
x
x
y
x

#

now there are three x's here

#

but i want dont want to count them manually

keen turtle
#

maybe you can save it as a file and read the file, and

f = open("file.out", r) # assume file.out as the file name
print(f.read().count("x"))
f.close()
#

or simply use Word

keen turtle
blissful stone
#

Could someone tell me if this is an optimal or near-optimal solution for finding if two words are anagrams? ```python
def map_word(word):
words_letters = {}

for letter in word:
    if letter not in words_letters:
        words_letters[letter] = 1
    else:
        words_letters[letter] += 1

return words_letters

def are_anagrams(word_one, word_two):
if len(word_one) != len(word_two):
return False

mapped_one, mapped_two = map_word(word_one), map_word(word_two)
for char in mapped_one:
    if char not in mapped_one or mapped_one.get(char) != mapped_two.get(char):
        return False
return True

if name == "main":
word_one = "racecar"
word_two = "carcear"
print(are_anagrams(word_one, word_two))```

#

I understand there are good solutions which involve sorting a list of the letters for each word but this feels like it would be more efficient. Would love to hear someone's take though

keen turtle
#

if the word is only English words with English alphabet, then you could use a list of length 26

#

which I think would be faster

agile sundial
#

the solution that involves sorting that you're talking about is something like

sorted(word1) == sorted(word2)
#

it sorts twice, so it's O(n log n + m log m)

keen turtle
#

I guess you could judge whether the words have the same length

#

before sorting them

#

and the list version is only O(n)

agile sundial
#

in your solution, you loop over each character in a string and use in to check if it's in another string, which is O(n^2)

blissful stone
#

I don't know what I was up to with that statement geez. What if I change this line from if char not in mapped_one or mapped_one.get(char) != mapped_two.get(char): to if mapped_one.get(char) != mapped_two.get(char):

agile sundial
#

your solution is also not guaranteed to work, i believe

keen turtle
# 
def areAnagrams(a: str, b: str) -> bool:
    if len(a) != len(b):
        return False
    length = len(a)
    lsta = [0 for _ in range(26)]
    lstb = [0 for _ in range(26)]
    for i in range(length):
        lsta[ord(a[i]) - 97] += 1
        lstb[ord(b[i]) - 97] += 1
    return lsta == lstb
#

Assume they use ASCII

fiery cosmos
# 
def are_anagrams(first_word: str, second_word: str) -> bool:
    return sorted(first_word) == sorted(second_word)
``` lol
keen turtle
#

since this is O(n log n) and the list is just O(n)

agile sundial
#

it's probably just as fast for strings under 1000 chars or so, but i'm just guessing

blissful stone
#

Feels like cheating lol. Just taking a data structs and algorithms course so I'm trying to dip my toes in the proverbial water

fiery cosmos
#

yeah, I know the interviewer wouldn't accept this anyways

#

44 ms, faster than 78.81% of Python3 online submissions for Valid Anagram.

agile sundial
#

that's kind of sad

keen turtle
#

well, as an OIer, I think the faster the better lol.

agile sundial
#

well yeah, but

keen turtle
#

but I guess using numpy.array will even increase its speed(

agile sundial
#

probably not

blissful stone
#

Runtime: 52 ms, faster than 50.39% of Python3 online submissions for Valid Anagram.

#

Guess I have a lot to learn this semster πŸ˜ƒ Thanks everyone for the input

keen turtle
#

!e

def areAnagrams(a: str, b: str) -> bool:
    if len(a) != len(b):
        return False
    length = len(a)
    lsta = [0 for _ in range(26)]
    lstb = [0 for _ in range(26)]
    for i in range(length):
        lsta[ord(a[i]) - 97] += 1
        lstb[ord(b[i]) - 97] += 1
    return lsta == lstb

print(areAnagrams("abc", "cba"))
halcyon plankBOT
#

You are not allowed to use that command here. Please use the #bot-commands channel instead.

agile sundial
#

oop

#

you could use collections.Counter

fiery cosmos
fiery cosmos
#

that was the runtime for your counter solution

agile sundial
#

well it was the same speed as my solution using sorted, so i just assume their test cases weren't large enough to make a difference

keen turtle
#

I guess anyway the words are pretty short

#

longest common words are something like 20 or 30 letters.

agile sundial
#

they didn't have to be actual words though, could just have been long strings

fiery cosmos
#

not the most efficient way but clever indeed

stable pecan
#

Counter is linear

agile sundial
#

indeed

dense mauve
#

dm ads

agile sundial
#

dm @fallow ginkgo to report @dense mauve

pseudo pilot
#

could anyone here help me solve a recursion problem in #help-popcorn ?

amber egret
#

help

carmine anvil
unique loom
#

this is kind of unclear to me, but does anyone know, in ant colony optimization algos, is the pheromone matrix initialized to 0, or some non-zero positive value?

#

having it be all 0's at the start would require some sort of special case for picking the next vertex for the ant, no?

#

and it would mean that whatever paths the first ants choose and then deposit the pheromones on, if there are any edges with 0 pheromones left after that, they will always have 0% probability to get chosen compared to any other edges with any amount of pheromone on them

#

or am i misunderstanding something

valid coral
#

hello just wondering if anyone knows how to implement a functional recursive merge sort in python?

agile sundial
#

i'm sure a few people do

valid coral
#

i'm tying to make one right now but there's always an error when I try to use the len() function on the arrays that i pass in the parameters

keen hearth
#

Hey @valid coral

#

Perhaps they are iterables (can be iterated with a for loop), but not sequences (can be accessed by index with [] and have a defined length)?

#

Do you get an error message like this? ```
TypeError: object of type 'generator' has no len()

valid coral
mint jewel
#

your functions need to return something

#

I am guessing you have something like

def fun():
    if ...:
        ...
        fun()
``` where you need
```py
def fun():
    if ...:
        ...
        return fun()
small drift
#

Can someone explain why we need to use gradient descent, for example for linear regression, when we can just take the derivative of the function and see where it = 0?

mint jewel
#

because there is no easy way to compute the derivative of the function.

small drift
#

so if our error function was only, say 3D, then would that be a feasible solution?

#

in other words, if we only had 2 features in our data set

#

because the derivative function would be a single variable equation..?

#

oop nvm im wrong about that

mint jewel
#

remember that the function you use gradient descent to take the derivative of takes all of your network parameters as arguments and outputs the error over some slice of the dataset.

small drift
#

ok...what do you mean some slice? doesnt it use the whole dataset for its parameters?

mint jewel
#

not always, it can often yield better results if you descend after only going through part of the dataset, or even only one datapoint since it much more performant, though this is more a topic for #data-science-and-ml

#

let's say I wanted to search if a phrase (string/rope/...) is a subsequence of several other stored phrases (subsequence in the can you remove elements to get the sequence). I know of the dynamic programming algo for this, but that is for 1:1, but here I have 1 phrase which may be a subsequence of several other phrases, so I wonder if there is some e.g. tree I could build to not have to do

phrases = ["pricey orange grafter"]
for phrase in phrases:
    if issubsequence("peter", phrase):
        print(phrase)
```. It may  turn out fast enough this way, didn't write it yet, but this more of a let's practice algorithms project than a let's get something useful done project
mighty stream
#

y

mint jewel
#

you need '\\'

#

since \ will escape the ending '

rotund prism
#

does heapify do heapsort on the array? I am trying to get the next smallest element from heap by interatign thru the heapified array, will go in heapsorted way or do i have to heappop everytime?

wraith valve
#

generally heapify creates a heap

#

and i think if u actually want the sorted values u need to pop them all out

mint jewel
#

yeah, you have to iteratively pop, though I think that is what heapsort does

#

there is no heap iterator builtin, so you can make your own

def iter_heap(heap):
    heapq.heapify(heap) # optional
    while heap:
        yield heapq.heappop(heap)
#

you may want to copy the heap as well before depending on your usecase

#

though why not just use sorted() instead?

brave oak
#

Can someone explain why we need to use gradient descent, for example for linear regression, when we can just take the derivative of the function and see where it = 0?
@small drift remember that the equation is overdetermined in the general case

#

therefore it has no exact solutions

small drift
#

ok thank you!!

valid coral
#

Hi! i was actually able to do the merge sort but I need to have the out put where I print the elements of the array after each sort and I'm not really sure where to place the prints :< can anyone help out?

# 
def merge(a, b):
    
    out = []
    
    while (len(a) > 0 and len(b) > 0):
        if (a[0] <= b[0]):
            out.append(a[0])
            a.pop(0)
        else:
            out.append(b[0])
            b.pop(0)

    while(len(a) > 0 ):
        out.append(a[0])
        a.pop(0)

    while(len(b) > 0 ):
        out.append(b[0])
        b.pop(0)
    print(out) 

    return out

def half(arr):
    mid = len(arr) // 2
    
    return arr[:int(mid)], arr[int(mid):] # array colon python

def mergesort(arr):
    
    if (len(arr) <= 1):
        return arr
    
    left, right = half(arr)
    
    L = mergesort(left)
    R = mergesort(right)

    #print (merge(L, R))
    return merge(L, R)

def inputList(size):

    arr = []
    
    for n in range (0, size):
        arr.append(int(input()))
    return arr
#

i have this so far with the print in the merge function but it doesn't print everything out

rich ridge
#

ans = max(helper(k, k), helper(k, k + 1), ans, key=len)

rich ridge
wispy hare
#

for example, if we have a list of lists and we want to get the longest one, we write max(lists, key=len)

#

your code means max(len(helper(k,k)), len(helper(k,k+1)), len(ans))

rich ridge
wispy hare
#

you're welcome!

rich ridge
#

How does string slicing work in this example s[i + 1 : j] ??

wispy hare
rich ridge
tawny narwhal
wispy hare
wispy hare
tawny narwhal
#

ah

wispy hare
#

Example:

>>> s = "inside code"
>>> i = 1
>>> j = 5
>>> s[i+1:j]
<<< "sid"
>>> s[i:j+1]
<<< "nside"
mighty cedar
rocky fractal
#

the second one?

twilit gate
#

The second one looks cleaner

half lotus
#

How coarse should a lexer be? Should every operator get its own token or should they be grouped e.g. a token encompassing all binary operators?

clever crag
#

hello everyone , i just start to learn data-struct

#

i install a repo to record my study

#

can someone help me to do code review?

#

thanks a lot

wispy hare
# 

csv = """AACG, 01/02/2015, $4.7
AACG, 01/02/2018, $5.43
AACG, 01/02/2019, $0.94
AACG, 01/02/2020, $1.35
AACG, 01/31/2017, $3.04
AACG, 01/31/2018, $5
AACG, 01/31/2019, $1.08
AACG, 01/31/2020, $1.1569
NWS, 01/20/2017, $12.35
NWS, 01/21/2014, $16.76
NWS, 01/21/2015, $14.45
NWS, 01/21/2016, $12.72
NWS, 09/27/2019, $14.17
NWS, 09/28/2015, $12.44
NWS, 09/28/2016, $14.27
NWS, 09/28/2017, $13.65""".split('\n')
csv.sort(key=lambda x: datetime.datetime.strptime(x.split(', ')[1], '%m/%d/%Y'))```
fiery cosmos
#

Are there any Python packages or other software/tools that will return the discrete form of a differential equation?

vernal stirrup
#

how do I write the label for a matplotlib chart? I have r"$a_y$ in $\frac{m}{s^2}$" but i want the m ans s to be straight up (not like a variable) because they are units

vernal stirrup
#

(if i should delete my messages pls tell me)

buoyant bone
# 
mynumbers = [15, 12, 2, 6, 10, 20, 1, 4, 21, 18, 5, 14, 3]

for i in range(len(mynumbers) - 1):
    minindex = i
    
    j = i + 1
    for j in range(j, len(mynumbers)):
        if mynumbers[j] < mynumbers[minindex]:
            minindex = j

    if not minindex == i:
        temp = mynumbers[i]
        mynumbers[i] = mynumbers[minindex]
        mynumbers[minindex] = temp

print(f"The sorted list is {mynumbers}")

My attempt at selection sort...
Is there a more efficient way to do this?

runic tinsel
#

you don't need temp stuff in python, you just swap

#

a, b = b,a

fiery cosmos
# buoyant bone ```py mynumbers = [15, 12, 2, 6, 10, 20, 1, 4, 21, 18, 5, 14, 3] for i in range... 
def selection_sort(numbers: list):
    for sorted_index, _ in enumerate(numbers):
        # get index of smallest element
        min_element, min_index = numbers[sorted_index], sorted_index
        for index in range(sorted_index, len(numbers)):
            min_element, min_index = (numbers[index], index) if numbers[index] < min_element \
                                                             else (min_element, min_index)
        
        numbers[sorted_index], numbers[min_index] = numbers[min_index], numbers[sorted_index]
buoyant bone
#

uhhhh

#

πŸ€”

#

Thankyou 😁

hidden sequoia
#

hi, any king of string slicing?

void hatch
#

formatting: teststring.slice("what to slice by")

ashen yarrow
queen patio
#

hot

fading shell
#

how do i create a simple program that calculate the mode of a given number list?

lean dome
#

Loop over the list to find how many times each number occurs in it, then loop over the counts to find which number has the most occurrences

autumn whale
fading shell
#

Thanks so much

autumn whale
#

the simplest and probably least algorithmic way is to use mode from the statistics module

fading shell
#

Yep but that one was the one in looking for

trail totem
#

Does someone know how to turn a set of integeres in a matrix ?

vocal gorge
#

A set? Into a matrix? What order would you arrange them in, and why?

uncut cradle
#

Hi, I've got a question.

Suppose I'm looking at multiple stocks all in the format of [initial price, end price] and given that I have a limited amount of money to buy said stocks once, what is the best way i can calculate which stocks i should buy to maximize profits.

Take note that just doing (end price - initial price) and choosing the most profitable may not necessarily work in all cases

vocal gorge
#

With profit being the value and initial price being the weight.

uncut cradle
#

wow yeah looks really similar! how did you find out about this knapsack thingy

agile sundial
#

it's a classic well known problem

ionic vine
#

My mom wants me to code a program to help her in packaging for exports:

Given a list of items of different weights in grams (example, [6.5, 6,7, 6,7, 7, 7, 8]), pack them into boxes of 100g. The criteria is to pack as many full boxes with exactly 100g (or other weight), and return the list of boxes.

I'm not quite sure how to tackle this problem other than just filling the boxes with the heaviest items first and try every possible combination.

wispy hare
# ionic vine My mom wants me to code a program to help her in packaging for exports: Given a...

https://en.wikipedia.org/wiki/Bin_packing_problem might help you

Bin packing problem

In the bin packing problem, items of different volumes must be packed into a finite number of bins or containers each of a fixed given volume in a way that minimizes the number of bins used. In computational complexity theory, it is a combinatorial NP-hard problem. The decision problem (deciding if items will fit into a specified number of bins...

ionic vine
#

cb_pika_think thank you, I will have a read. I see that it seems like an NP-complete problem

wispy hare
#

you're welcome!

ionic vine
#

hmmm the heuristic algorithms don't guarantee (unless I misread) filling up most boxes to max weight though, it's more like minimizing the boxes used but not filling them up to the brim

#

I feel like my problem is slightly different

fiery cosmos
#

need help

fiery cosmos
#

why do we have so many sorting methods. Just do bogosort and be lucky like me and it'll sort in O(1)

runic tinsel
#

it would take O(n)

#

you want something like "it's probably sorted already sort"

agile sundial
# 
def sorted(L):
  return L
lean dome
#

Timsort - Python's default sorting algorithm - basically does that. If the data is already sorted, Timsort is O(n)

fiery cosmos
#

How should i seperate the items in this list so that i can print each out individually

πŸ“Ž unknown.png
#

Anyone help?

fiery cosmos
#

imagine checking it's sorted

#

I'm so lucky I just know

#

right to a return

balmy dove
#

this thread is cool! i'm learning so much. thanks πŸ˜…

dense mauve
#

@shrewd solar u looking kinda cute ngl

shrewd solar
#

thanks grapes

rich ridge
#

How long did y'all take to get a decent grasp on DSA ??

trail totem
lean dome
# rich ridge How long did y'all take to get a decent grasp on DSA ??

Data structures didn't take me much work. I understood most of them the first time I was taught them, including what operations were efficient and what operations weren't on each. Learning algorithms was much harder for me. It took a year or two of different classes discussing big o notation before I really was comfortable with it and could reason about it.

#

In retrospect, the more theoretical aspects of computer science were always much harder for me to grasp and internalize than the more practical aspects, so it's not surprising that algos was tougher for me than data structures.

serene phoenix
#

can this be condensed into a single line list comprehension?

  tempsls.append(file_io.read_cpu(i))```
Where templs is an empty list and file_io.read_cpu(i) returns a floating point value
wraith valve
#

yeah if u loop and append u can list comp

#

i think it would be templs = [file_io.read_cpu(i) for i in [8,12,16,20]]

rancid flower
#

hello does anyone now python in here

#

that can help

lyric bramble
#

need some help

celest skiff
#

I would love to try to help :D

lyric bramble
#

its going in a infinite loop

#

can some one help me with this problem

#

it goes to infinte loop

celest skiff
#

I would suggest adding whitespace, makes code a lot easier to read.

#

What exactly are you trying to do here?

wraith valve
#

im just thinking

#

if none of the if and elif work

#

like the first if evaluates to false

#

and the elif also evaluates to false

#

the whole thing is a while true loop

celest skiff
#

Exactly, there's no default else case.

wraith valve
#

oh i just saw the dude's question in general

#

he wants to sort the squares of the numbers

#

i personally would first square the numbers ie doing a map using lambda x: x**2 on the list

#

and then doing ur sort on the newly created list

#

@lyric bramble just to ping u about the question u had

lyric bramble
#

yes but its going to an infinite loop

wraith valve
#

how is that an infinate loop

lyric bramble
#

what is wrong with the code?

#

exactly

#

no output comes

wraith valve
#

what im saying

#

is u first do no sorting on the list

lyric bramble
#

the output section is blank

wraith valve
#

and make a new list

lyric bramble
#

ok

wraith valve
#

by squaring each value in the list

lyric bramble
#

ok

wraith valve
#

oh wait ur code actually isnt totally wrong

lyric bramble
#

but buddy i need a linear solution

wraith valve
#

sorting will never be linear

lyric bramble
#

with squaring and then sorting i would get o(nlogn)

wraith valve
#

ur just implementing the sorting wrong

lyric bramble
#

but im not sorting

wraith valve
#

like ur quicksort that u made is wrong

lyric bramble
#

im just comparing the values, which is bigger gets appended first

carmine anvil
#

How does that sort the array?

wraith valve
#

so ur basically trying to find the biggest value

#

and append that first

#

and doing that for the entire array

#

well thats getting u quadratic

#

not linear

carmine anvil
#

^

lyric bramble
#

yessss

wraith valve
#

dude

#

ur not getting linear runtime by doing that

#

and sorting will never be linear

#

if u do comparision

carmine anvil
#

You can't get a linear comparative sort

#

If you do something like radix you can get close

lyric bramble
wraith valve
#

n + n-1 + n-2 + ... + 2 + 1

#

is what ur code is doing

#

if ur finding max

#

and appending to list

#

until the initial list is empty

lyric bramble
#

oh damn and that is o(n^2)

carmine anvil
#

It's called selection sort

wraith valve
#

lmao facts

lyric bramble
#

see this video

#

he says its o(n)

carmine anvil
#

Your input is already sorted

#

That's why

wraith valve
#

lmaooooo

carmine anvil
#

You're getting a sorted input, so the largest square at any point in time is at either end

lyric bramble
#

exactly

carmine anvil
#

Yeah so you didn't tell the entire question till now lmao

#

The fact that the input is sorted makes a huge difference

lyric bramble
#

yea ur righr

wraith valve
#

okay ur code now makes more sense

lyric bramble
#

oh so u werent aware it was sorted?

carmine anvil
#

I mean, you didn't mention it so we couldn't have known

lyric bramble
#

no issues man

#

sorry my bad

carmine anvil
#

Cool

lyric bramble
#

but now my code isnt working

#

its going in infinite loop

wraith valve
#

ur idea is right

#

u compare the ends with each other

#

and keep on doing it till u meet

lyric bramble
#

but the code isnt working

#

what maybe the issue

wraith valve
#

also i noticed

#

y dont u use append

#

ur repeatedly inserting into the first index

#

with insert(0, value)

lyric bramble
#

bocz im sorting from desceding to ascending

wraith valve
#

well u can just flip at the end

#

which doesnt change asymptotics

#

eh

agile sundial
#

actually it makes it much faster, since insert(0, val) is very slow

#

compared to append

lyric bramble
#

but then it would get sorted in reverse manner

wraith valve
#

well call reverse at the end

#

which is also linear

lyric bramble
#

are u usre?

#

sure?

wraith valve
#

well im not sure about its exact implementation

#

either it does a backwards iteration and appends

lyric bramble
wraith valve
#

or it can do the insert(0,val)

#

i mean if ur just caring about asymptotics

agile sundial
#

list.reverse is linear time

wraith valve
#

and not really worried about actual running time in terms of seconds

#

u know whats the actual issue with ur code

#

its the inequalites

#

what if the two numbers at the ends are equal

lyric bramble
wraith valve
#

ur if and elif dont capture that

#

so u get a while true

lyric bramble
#

tht is the main issueeeee

#

what made u to think about that?

#

thanks mate

wraith valve
#

saw ur test case

#

it had -2 and 2

#

u square them and its both 4

lyric bramble
#

thanks

#

absolutely right

wraith valve
#

ive also made that mistake before

#

frogetting about things being equal

lyric bramble
#

def sort_sq(arr):
n = []
low,high = 0,len(arr)-1
while low <= high :
if arr[low]**2 >= arr[high]**2:
n.append(arr[low]**2)
low += 1
elif arr[low]**2 <= arr[high]**2:
n.append(arr[high]**2)
high -= 1
n.reverse()
print(n)

#

this is my code now

wraith valve
#

i mean

#

how u decide on how to break the ties

#

is up to u

lyric bramble
#

im appending both

wraith valve
#

and the second = in the elif is unneccessary

lyric bramble
#

order doesnt matter

wraith valve
#

bc the first if would capture the equals

lyric bramble
#

yes

wraith valve
#

i mean u can still do a insert(0,val)

lyric bramble
#

no ill dothe reverse

wraith valve
#

yeah either have the equal in the if or elif

#

and the elif can be turned into an else

#

bc its either less than or equal which is captured in the if

#

or its greater than

lyric bramble
#

changed it

wraith valve
# 
def sort_sq(arr):
    n = []
    low,high = 0,len(arr)-1
    while low <= high :
        if arr[low]2 >= arr[high]**2:
            n.append(arr[low]**2)
            low += 1
        else:
            n.append(arr[high]**2)
            high -= 1
    n.reverse()
    print(n)
#

this is my version

#

which is basically what u did

lyric bramble
#

correct

#

thanks

#

could u help me w one more problem

#

Run-length encoding is a fast and simple method of encoding strings. The basic idea is to represent repeated successive characters as a single count and character. For example, the string "AAAABBBCCDAA" would be encoded as "4A3B2C1D2A".

brave oak
lyric bramble
#

i want to implement it on my own

brave oak
steady arch
#

A good way would be to use nested loops

#

And u can speed it up by skipping indexes

#

Is what I feel

stiff pewter
#

Hello guys. There's this piece of code:

def productSum(array, multiplier = 1):
    sum = 0
    for element in array:
        if type(element) is list: 
            sum += productSum(element, multiplier + 1)
        else:
            sum += element
    return sum * multiplier

That I'd like to turn into this:

def productSum(array):
    currentSum
    productSumHelper(array, 1, 0)
    return currentSum

def productSumHelper(array, multiplier, currentSum):
    for i in range(len(array) - 1):
        if type(i) is list:
            sum+= productSumHelper(array, multiplier + 1, currentSum)
        else: 
            currentSum += i
    return currentSum * multiplier

Right now I'm getting compilation errors of currentSum not being defined. But if I set it to zero then the entire thing returns 0. What's the correct way of doing it?

#

Please ping me

lyric bramble
# 
def selection_sort(arr):
    start = 0
    while start < len(arr):
        min_item = min(arr[start:])
        index = arr.index(min_item)
        arr[start],arr[index] = arr[index],arr[start]
        start+= 1
    return arr
#

what is the time complexitiy of this program??

stiff pewter
#

O(1) space since you're not storing anything extra and O(n) time since you're just going through the input without anything crazy

lyric bramble
#

is this the correct method of implementation of insertion sort

#

bcoz traditionaly its o(n^2)

stiff pewter
#

Oh yeah I'm sorry, it's n^2 actually, you're right

lyric bramble
#

could u explain how is it o(n^2)

stiff pewter
#

I don't know about your implementation specifically, I'm not very well versed in python

#

It's 0(1) Space because you're not storing anything. And O(N^2) time. N is the size of your input. And it's N^2 because you keep re iterating through the unsorted part of the list

lyric bramble
#

ok

stiff pewter
#

I'm pretty sure your implementation is wrong because there has to be a double for loop which is also an indicator that the complexity is n^2

vocal gorge
shrewd trail
#

@stiff pewter Its O(n^2) time because you get a sum 1 + 2 + ... + n = n(n-1)/2 = O(n^2)

#

@lyric bramble

#

Oh wait, yeah ConfusedReptile is correct. However, properly implamented you get a sum as described above.

mint crow
#

Do u guys have any website/video/book suggestions to learn about algorithm, data structure, the inside and out of cs?

trail dirge
#

so im doing quick sort right now, and this is the part i dont understand
p = partition(array, start, end)
quick_sort(array, start, p-1)
quick_sort(array, p+1, end)

celest skiff
#

Quick sort is what's known as a divide and conquer algorithm.

#

It choses a pivot element and creates two arrays to hold numbers less than and greater than the pivot.

#

It then uses recursion to sort the two arrays.

trail dirge
#

so it sorts before the pivot and after the pivot in this case it seems

#

but what does it return when it is sorting before/after and also how does it combine everything

fiery cosmos
trail dirge
#

oh it is starting to make more sense

#

ty

fiery cosmos
#

hey can someone help me with understand a hash func from an ctf. i have the answer and it is not sitll happening

#

plz

polar panther
errant dagger
#

Hi guys.I'm new here. I've been learning python for more than a month. Is it right time to start learning data structure and algorithms. If yes, how should I study?

keen hearth
keen hearth
#

For example, when and why you might use a dictionary or set instead of a list.

errant dagger
#

I cant able to solve a single problem easy in hanckerank

fiery cosmos
#

hey lx, where would I go with my qestion

errant dagger
keen hearth
fiery cosmos
#

kk

keen hearth
keen hearth
#

You might not be quite ready to dive into algorithms if you've only been programming for a month, but it depends.

#

What resources have you been using to learn?

errant dagger
#

Book - automating the boring stuff with python(only theory)

keen hearth
#

Oh right. That book is often recommended.

polar panther
keen hearth
#

Are you making much progress?

#

I would maybe work all the way through that book before moving on to programming challenge websites like HackerRank.

#

And maybe do a couple of small projects.

#

After that, Khan Academy have a nice introduction to algorithms course online. Unfortunately the programming challenges are in Javascript, but you can skip those (or try doing them in python on your own computer and posting your answers here for feedback).

heady jewel
errant dagger
bleak cloud
#

guys how do I make this more efficient so that I can find the sum of all prime number till 2 million
[10:32 PM]

#

num_l=[]
y = int(input("enter till what number do you want the sum"))
for count in range(0,y):
num_l.append(count)

total = 0

for counter in range(0,y):
num = num_l[counter]
if num > 1:
for i in range(2,num):
if (num % i) == 0:
break
else:
total = total + num

print(total)

fiery cosmos
scarlet maple
#

so the reason why this:

list1 = [1, 3]
list2 = list1
list1[1] = 4
print(list2)```
#

returns

#

[1,4]

#

instead of

[1,3]

#

is bc python is a dynamic language or something else?

mint jewel
#

= never copies, it just makes list2 refer to the same list as list1 does

scarlet maple
#

ah

#

even when you reassign the elements huh

#

interesting

#

thanks

wispy hare
scarlet maple
#

makes sense

wispy hare
#

or use list2 = list1.copy()

scarlet maple
#

its more just trying to understand the limits than a specific purpose

#

but good to know

#

that i can also do that

#

thanks

wispy hare
#

you're welcome

scarlet maple
wispy hare
#

related to the topic: don't use * operator with a mutable element (e.g.: list)

#

[[]*10] for example is just creating a list of 10 lists that have the same reference

#

write [[] for i in range(10)] instead

scarlet maple
#

you mean tuple being immutable right

#

i thought lists were mutable

wispy hare
#

mutable my bad

scarlet maple
#

oh gotcha

#

got it

#

yeah it gets messy when you throw arrays in there

#

but numpy has some cool functions

elder stirrup
#

So I'm trying to do something interesting

#

My class played a bunch of games w/ each other and recorded down who beat who

#

for example person A beat C, person C beat B, A beat B, etc

#

I was trying to see who was best/worst using a topological sort but it seems to not actually possible to write it that way in this case

#

so then does anyone know if there's some way I can take these relationships and extract a few cycles sorta like a circular topological sort

#

so in this case A -> C -> B -> A ...

#

i thought about this a bit and i'm not even sure whether an ordering like that would be well defined but ummm

#

if anyone has any ideas please lmk

kindred coyote
#

Can someone help me better understand how to implement BFS?

#

Like problems with explained code

wraith valve
#

i mean one way is have a queue

#

u start at a vertex

#

and u append all the neighboring vertex to the queue

#

and u loop though till queue is empty

keen hearth
keen hearth
keen hearth
keen hearth
# kindred coyote Like problems with explained code

I find the simplest way to implement bfs is to go level-by-level: ```python
def bfs(start: T, goal: T, successor_fn: Callable[[T], Set[T]]):
level = {start}
visited = {start}
depth = 0
while level:
if goal in level:
return depth
level = set.union(*map(successor_fn, level)) - visited
visited |= level
depth += 1

fiery cosmos
#

can anyone suggest me some good resources to learn algorithms and data structures

vocal gorge
#

I don't know any courses, but Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein) is a popular book.

#

Though one problem in learning DSA in Python is that manually implementing DSes (like many courses involve) in Python will result in very inefficient ones. It's not really a big problem, though.

fiery cosmos
#

can someone PLEASE help me with hash funktiosns

#

i have one from a ctf last year with answer but id ont understa

#

ply

vocal gorge
#

What's your question?

fiery cosmos
#

I posted it a while back want me to ss you what i posted

fiery cosmos
#

Can anybody help me implementing piority quues???

#

Pls help me

wispy hare
kindred coyote
vernal stirrup
#

can somebody help me pls?

uneven jungle
#

append does not return the list, so remove ts2 =

vernal stirrup
#

oh okay thanks

hallow vortex
#

quick question. why code in the photo outputs this?

#

I wanted the output to be [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0]]

#

Can anyone help me for the right output?

uneven jungle
#

add print(cols) after

wispy hare
hallow vortex
hallow vortex
wispy hare
#

[[0]*cols for i in range(rows)]

hallow vortex
#

isn't that the same thing?

wispy hare
#

nope because * operator will give the same reference to all the lists

#

but list comprehension will create rows distinct lists

hallow vortex
#
  • operator is better for time complexity cause it si O(1)
#

oh....

wispy hare
hallow vortex
#

got it. Thanks let me try it if it has all different references

hallow vortex
wispy hare
#

'a'*n will create a string of length n, so it probably has a time complexity of O(n)

hallow vortex
#

awesome.

hallow vortex
#

I think it makes sense if each list should be aligned in a list. that could be O(n). Thanks

wispy hare
#

like if you're doing s*n where s is a string of length m and n the number of repetitions, you get an O(nm) time complexity

keen hearth
keen hearth
#

So, start and goal are the starting node, and the goal node.

#

And successor_fn is a function that takes a node and returns a set containing its 'successors' (these could be e.g. neighbours, in a maze problem).

blazing current
#

Hey, any good sites or recources for learning/practicing algorithms? I wanna get into AI and I dont know any good place to start

pine kindle
#

algoexpert?

blazing current
#

ok thanks ill check that oyut

#

out**

wraith valve
#

y would u go to algoexpert

#

its literally paying for a service that u can get free else where

pine kindle
#

i dont know bro its just the only one i can think of off the top of my head

wraith valve
#

those yt ads indoctrinating u

agile sundial
#

rofl

#

leetcode, hackerrank, codewars

pine kindle
#

yeah but those are coding challenges, isnt algosexpert specifically for data structures and algos

agile sundial
#

i mean

small drift
#

When doing gradient descent for categorical cross entropy, is the loss function summed up over all samples or is it just per sample? I am kind of confused on how to calculate loss with multiple inputs..can someone explain?

fiery cosmos
#

Can someone helps my with my businnes?

#

It is Affiliate Marketing.

sand pilot
smoky chasm
#

Hi everyone, I am stuck on a activity. I 250 for the area walls apparently there is more to it. I don't know how to correctly get the 2nd answer I tried substituting the 250 gotten a totally different answer.

πŸ“Ž Capture.JPG
small drift
#

remove line 4 in your code

#

@smoky chasm

#

and line 6

#

4 is the one causing error, but 6 is not needed in the code

smoky chasm
#

@small drift thank u

#

i really struggle with python

small drift
#

np

scarlet arch
keen hearth
past flare
#

Does someone know how can I print out the process a memory address belongs to?

#

I don't even know if it's possible but would be great if it is

keen hearth
#

That might be more suitable for #unix, assuming you're talking about Linux. I'm not sure this is really the right forum to ask this though, as python programming mostly deals with higher-level stuff.

agile sundial
#

??

past flare
#

There is a module called pymem which is an wrapping for the ctypes module, allows reading and writing to memory addresses

#

but i'd like to figure out how to print out what process module a mem address belongs to

hard leaf
fiery cosmos
#

I'm not sure if this fits here, but I have a program that automatically adds a stat (it's user count and current UTC timestamp) to a csv file. I then want to display the user count over time using matplotlib.

My problem is I now have more than 1300 samples, and the matplotlib graph is fairly long to generate. How could I "reduce the resolution" of the list by taking 500 elements that are representative of the list ?

I could remove half of the list by keeping only the values that have an even index for example, but this will get an issue again when I will hit 2600 samples...

How could I get a number of samples always between 500 and 1000 ?

wispy hare
fiery cosmos
#

I finally found a solution

#

step_size = len(base_list) // 500
usercount = usercount[::step_size]

wispy hare
#

or

>>> random.sample(range(1, 100), 3)
[77, 52, 45]```
wispy hare
fiery cosmos
#

I think random sampling will not necessarily always be the best solution to get an accurate representation of the list

#

I would like the list to reduce it's resolution but keep the same space between samples

wispy hare
#

depends on your definition of "accurate representation"

#

oh okay then use your method

fluid robin
#

Δ±'m stuck when Δ± try to create a tree with my inputs can anyone help me

#

[('bike', {'wheel': 2, 'frame': 1}), ('wheel', {'rim': 1, 'spoke': 1, 'hub': 1}), ('rim', 60.0), ('spoke', 120.0), ('hub', {'gear': 2, 'axle': 1}), ('gear', 25.0), ('axle', {'bolt': 5, 'nut': 7}), ('bolt', 0.1), ('nut', 0.15), ('frame', {'rearframe': 1, 'frontframe': 1}), ('rearframe', 175.0), ('frontframe', {'fork': 1, 'handle': 2}), ('fork', 22.5), ('handle', 10.0)]

#

what should I do

wispy hare
fluid robin
#

yes

wispy hare
#

what does 22.5 mean in fork?

fluid robin
#

their cost when Δ± have to calculate the complete bike cost

wispy hare
#

you can do so without building the tree

#

do you need the tree?

fluid robin
#

using tree is mandatory for this problem

wispy hare
#

okay so you want to actually build the tree right?

fluid robin
#

unfortunately

#

yes Δ± have to create tree

wispy hare
#

your tuples can either be (str,float) or (str,dict) where dict contins the children right?

fluid robin
#

this is sample input input are depend on user

fluid robin
fluid robin
shy zenith
#

I recommend using a dictionary here.

# 
tree_dict={'bike': {'wheel': 2, 'frame': 1}, 'wheel': {'rim': 1, 'spoke': 1, 'hub': 1}, 'rim': 60.0, 'spoke': 120.0, 'hub': {'gear': 2, 'axle': 1}, 'gear': 25.0, 'axle': {'bolt': 5, 'nut': 7}, 'bolt': 0.1, 'nut': 0.15, 'frame': {'rearframe': 1, 'frontframe': 1}, 'rearframe': 175.0, 'frontframe': {'fork': 1, 'handle': 2}, 'fork': 22.5, 'handle': 10.0}
#

Access it by:
Example: tree_dict["bike"]

#

Not sure if I am going in the right direction :)

hearty canopy
#

can someone here help with a quick question, its about stacks

wispy hare
hearty canopy
#

so I am trying to run this code but it says that bag isnt initalized

wispy hare
rough osprey
#

you can have a nested dictionary, probably:

{'bike': {
    'wheel': {
        'tyre': 'value',
        ...,
    },
    'frame': {
        'child': 'value',
        ...,
    },
    ...,
}
fluid robin
#

I have to convert it to tree

#

First Δ± tried to make children dictionary but Δ± confused

grizzled vigil
#

hey, so i am trying to learn some sorting algorithms right now, and i learned selection sort and bubble sort. i was told that the advantage of bubble sort over selection sort is that in the best case, bubble sort will be more efficient because you have the ability stop the alg whenever you don't need to sort it anymore. my question is why can't you implement this in selection sort?

lean dome
#

For bubble sort, if the inner loop performs no swaps, the list is sorted. For selection sort, if the inner loop performs no swap, the i'th element was already in the right position

#

That doesn't imply anything about whether the (i+1)th element is in the right position

rough osprey
final egret
#

I use other languages han python ... can someone let me know why this doesn't work?

def climb_stairs(n):
dp[0] = 1
dp[1] = 1
for i in range(2,n):
dp[n] = dp[n-1] + dp[n-2]
return dp

I get a NameError ... I would like to be able to write code like this with lists

agile sundial
#

pretty sure that wouldn't work in other languages either

#

you have to define dp before you can use it

rough osprey
#

your list only contains 2 items, but you are trying to use 3

#

yes, and the name is not defined, of course

final egret
#

that's basically what I'd like to do

agile sundial
#

well, i'm not very familiar with matlab

rough osprey
#

where is this line [dp] = function climb_stairs(n) in your python snippet ?

#

oh, this is a function signature πŸ™‚

#

if you can explain what that matlab code does, I may try to make a python of it

final egret
#

you basically have a vector that you make within your function for the first two cases of dp

#

In Go it would be "dp := make([]int, n+1)
dp[0] = 1
dp[1] = 1" ...

#

u just want to say ok i know the base value

#

for dp[0] and dp[1] are equal to zero

#

and then just run a loop that takes the value of n

rough osprey
#

so, you also need to define dp in python, which you did not do

final egret
#

so that's it? otherwise it's fine?

#

thanks

rough osprey
#

in you case it would probably, be dp = []

final egret
#

gotcha

rough osprey
#

not all, actually

#

your for loop will not work

final egret
#

I actually get:

"---> 16 dp[0] = 1
17 dp[1] = 1
18 for i in range(2,n):

IndexError: list assignment index out of range
"

rough osprey
#

because you only have 2 items in your list, but you are trying to use 3

final egret
#

even when i define dp = [] on line 15

#

aaha

#

1

rough osprey
#

yes, because you onl have 2 items in your list

agile sundial
#

well actually, he has zero items

#

so trying dp[0] will error

#

you could do dp = [0] * n for a list with length n

rough osprey
#

adding items to a list you need to use append

final egret
#

got it

#

let me try

rough osprey
#

i understand now, what you are trying to do

#

just use append - should work

#

but initailly you can just do dp = [0, 1]

#

or whatever your values are

final egret
#

ok so dp = [1 1] and then dp.append in the for loop

#

got it

#

thanks

rough osprey
#

yes

final egret
#

perfect, thanks

#

also wrote i instead of n

#

works fine

#

just out of curiousity why can't you just do:

"dp[n] = (dp[n-1] + dp[n-2])"? why do you need to do append?

rough osprey
#

because doing dp[n] you are getting an existing element with index n

near sequoia
#

anyone know how to solve this

#

In this exercise, you are going to count by 2, starting at 2 and ending with the provided number.

You should return the numbers as a space seperated string.

Example:

count_by_two(10) --> "2 4 6 8 10 "
count_by_two(4) --> "2 4 "

fluid robin
#

For example

rough osprey
#

each of the internal lists has a name as a first item and some tuples as the other items.

#

so, the tuples are, probably, the children πŸ˜‰

fluid robin
#

= [["rearframe", 175.0], ["bike", (2, "wheel"), (1, "frame")],
["frontframe", (1, "fork"), (2, "handle")], ["hub", (2, "gear"), (1, "axle")],
["fork", 22.5], ["nut", 0.15], ["rim", 60.0], ["axle", (5, "bolt"), (7, "nut")],
["handle", 10.0], ["frame", (1, "rearframe"), (1, "frontframe")], ["bolt", 0.1],
["spoke", 120.0], ["gear", 25.0], ["wheel", (1, "rim"), (1, "spoke"), (1, "hub")]] the list is not ordered is it problem

#

So you say Δ± don’t have to use dictionary

rough osprey
#

no, you, probably, have to use dictionaries, but there is an easy way to create a function, which will do this for you for this data structure

final egret
worthy fjord
#

hey guys

#

and gals, hey people, ok here goes my question:

#

So, let's say that we have a system that count resources needed for tasks, let's say ovens, i distribute the work in 15 minutes buckets, but i need to identify which ovens are made available in the middle of the 15 minute bucket. So I have oven tasks finishing withing the 15 minute time range and others starting within, so by looping through the list i can see which ovens i can reutilize hence minimizing the total ovens needed

#

is there a good algo based way to do this?

#

currently I looped through the ones that finish before others start and then store in a list the "reused oens" that way I dont assign a nnon existen new oven task to the 3rd oven in this example

vocal gorge
fluid robin
#

I need some help who can help me to solve about data structure

fluid robin
#

part_lisr= [["bike", (2, "wheel"), (1, "frame")],["wheel", (1, "rim"), (1, "spoke"),
(1, "hub")],["rim", 60.],["spoke", 120.],["hub", (2, "gear"), (1, "axle")],
["gear", 25.],["axle", (5, "bolt"), (7, "nut")],["bolt", 0.1],["nut", 0.15],
["frame", (1, "rearframe"), (1, "frontframe")],["rearframe", 175.],
["frontframe", (1, "fork"), (2, "handle")],["fork", 22.5],["handle", 10.]]

#

this is input

#

but output have to be like this

#

formatted=["bike",[2,"wheel",[1,"rim",[60.0]],[1,"spoke"[120.]],[1,"hub",[2,"gear",[25.]],[1,"axle",[5,"bolt"[0.1]],[7,"nut",[0.15]]]]], [1,"frame",[1,"rearframe",[175.]],[1,"frontframe",[1,"fork",[22.5]],[2,"handle",[10.]]]]]

#

how can I write this algorithm

main flower
#

Ummm... What

lusty ivy
#

I have a question for people who learn programming in schools, as someone who just read books in spare time.

Why do you so often see people ask questions like, "Does anyone know a good course to study algorithms and data structures in Python that is beginner friendly?"

What does this mean? Why do they always specify these two things together. If they just learn python, they'll learn lists, dicts, etc.

Do they want to know sorting algorithms? If so, why dont they say that instead of "algos and data structs"

I have to assume this is something that is common for a university course to be called.

bleak pulsar
#

I was learning Python for four months plus, and had my fundies down before I ever tackled a recursion. Whatever it is, I doubt I'll ever find a use case for it as a freelancer or on my own project.

I think the algs are really for those looking to get into traditional work with start-ups and such, because they use them to filter applicants in interviews.

lusty ivy
#

After doing some reading in seems like "algos and data structs" is what people say when they mean "mathematical computer science"

#

So yeah.

wispy hare
bleak pulsar
#

Oh yeah. I'm glad I studied it. It def forces you to think in a non-traditional way. I like any structure/problem that allows you to have an epiphany, when you finally "get it". Unlike syntax rules, which erodes through lack of use, once you really understand recursion, or something similar, you usually don't forget it.

#

Just today I came upon a Singleton method using a new-type object in some open source code. I didn't even know WTH a singleton was, really. One thing about coding, is if you love learning, you are going to love coding.

dense acorn
#

!range

halcyon plankBOT
#

Iterating over range(len(...)) is a common approach to accessing each item in an ordered collection.

for i in range(len(my_list)):
    do_something(my_list[i])

The pythonic syntax is much simpler, and is guaranteed to produce elements in the same order:

for item in my_list:
    do_something(item)

Python has other solutions for cases when the index itself might be needed. To get the element at the same index from two or more lists, use zip. To get both the index and the element at that index, use enumerate.

lean dome
# lusty ivy After doing some reading in seems like "algos and data structs" is what people s...

sometimes it's a shorthand for "mathematical computer science", but it's more than just that. If you just learn Python, yes, you'll learn lists and dicts, but you won't learn how lists and dicts work. At most, you'll learn that dicts require keys to be hashable, and that immutable objects like strings and ints and tuples are hashable. You won't learn what a hash table is, or how it works, or which operations are fast on a hash table and which are slow, or why hashability is useful and why dicts require it. Likewise, you won't learn that a list is a dynamic array, and that each time it needs to grow it grows itself by some factor (50% larger on each resize, or 100% larger, or whatever) in order to achieve amortized constant time appends to the end of a list. Or that removing things from the start of a large list is very slow.

#

when someone says that they want to learn Python data structures, they might mean that they want to learn how to use Python's builtin data structures, but when someone says that they want to learn data structures and algorithms, it always refers to how the data structures themselves work, and what algorithms they use internally, and what algorithms can be efficiently applied to them.

lusty ivy
#

That fully clears it up. I would say even I dont really know that. I know how to use it, not so much why and how it was designed that way

bleak tapir
#

Hi, I'm looking for some books / video / info or introductions to Data Science or similar. I have a project in mind regarding string manipulation and matching using FuzzyWuzzy. Project is quite huge (lets say over 5k individual strings needs matching against a huge library (> 100k strings), but I need some reading to understand fundamentals. Any recommendations?

lyric bramble
#

what is the time complexity of string concatenation in python

lyric bramble
lyric bramble
agile sundial
vocal gorge
# agile sundial O(n + m)

this , because of which joining N strings of length n is a total of 2n + 3n + ... + N n = O(n N^2). That's why one should use join instead.
(there's an optimization that makes += work in O(m) in some circumstances, but it only works when there's a single reference to the string)
For details on all this, see https://blog.mclemon.io/python-efficient-string-concatenation-in-python-2016-edition.

EDIT: oh damn, the blog got deleted. Thankfully, the Internet remembers: https://web.archive.org/web/20190715231220/http://blog.mclemon.io:80/python-efficient-string-concatenation-in-python-2016-edition

tranquil nest
#

do we have a java channel?

vocal gorge
#

Nope, this is a Python server. There's the offtopic channels, but also, well, there's Java discords.

tranquil nest
#

they werent much help:P

#

but thx

languid onyx
#

Is it possible to get the arbitrary precision functionality from decimal module in python to work with GPU using pyCUDA without losing the benefit of a GPU speedup? I do not need to vary the precision across the runs, but I need significantly larger than double precision floats. (Not sure of the appropriate channel)

keen hearth
#

GPUs work mostly on single and double floats.

#

Are you sure you need that much precision?

languid onyx
#

I am assuming it must be technically possible to divide a higher precision decimal operation in terms of lower precision floats? Perhaps the decimal module internally does something similar?
But implementing it in C++ from scratch looks like a lot of work. So was wondering if it is possible to avoid that.

#

Would Numba be any good instead of pyCUDA?

fiery cosmos
#

(N3, C, RES) ~ (NI + N2, 0~0);
while (min(Nl, N2) # 0) V (C ~ 0)
do NEXTBIT; (NI, N2) ~ ([N1/2], iN2/21) od;
RLINK[RES] *-- if NI ~ 0 then R1 else R2 fi;
R3 *-- RLINK[0]
endproc UNION

#

Cam somebody explain me this algorithm

#

Pls

wicked coyote
#

uhhhhh

#

idk

#

also

keen hearth
#

Can you re-write the pseudocode in a code block?

#

!code

fiery cosmos
#

@keen hearth explain me pls

keen hearth
#

Sorry, the command didn't work πŸ˜…

#

I don't understand what some of the symbols in this pseudocode mean, and I'm assuming there's some missing indentation.

fiery cosmos
#

Can I send you pics?

keen hearth
#

Alright πŸ‘

fiery cosmos
covert wedge
#

the data structure needed to proceed after that is DSU, i'm guessing not actually solved the problem yet but i'm pretty sure that a DSU will give the answer :D

brave oak
#

I am assuming it must be technically possible to divide a higher precision decimal operation in terms of lower precision floats? Perhaps the decimal module internally does something similar?
But implementing it in C++ from scratch looks like a lot of work. So was wondering if it is possible to avoid that.
@languid onyx I don’t think so...?

#

because of the bit layout of floats

#

like I don’t think you would lose the parallelism but you’d need to write a lot of custom code, it seems?

#

I’m not a CUDA expert though

wicked coyote
covert wedge
lean dome
#

And GPUs have no facilities for manipulating base 10 floating point numbers, as far as I know.

#

!e ```py
import decimal
print(decimal.Decimal("0.3") == 0.3)

halcyon plankBOT
#

@lean dome :white_check_mark: Your eval job has completed with return code 0.

False
kindred coyote
#

how would I do this problem:

halcyon plankBOT
#

Hey @kindred coyote!

Uh-oh! It looks like your message got zapped by our spam filter. We currently don't allow .txt attachments, so here are some tips to help you travel safely:

β€’ If you attempted to send a message longer than 2000 characters, try shortening your message to fit within the character limit or use a pasting service (see below)

β€’ If you tried to show someone your code, you can use codeblocks
(run !code-blocks in #bot-commands for more information) or use a pasting service like:

https://paste.pythondiscord.com

kindred coyote
#

problem S3

kindred coyote
#

ping if answer

fiery cosmos
#

Can someone explain me why this error comes when I try pickle.loads(f) (I had already created f with a context manager)

_pickle.UnpicklingError: invalid load key, '\x0a
#

Ping to answer btw

bleak tapir
#

So \x0a is a linefeed character. is the file local? Can you verify the file actually exist and is readable? Able to reproduce on another system?

#

@fiery cosmos

languid onyx
# lean dome That's not at all how the decimal module works. float is a base 2 floating point...

Base 10 might be how it represents the number but I meant that ultimately the actual calculations must involve integer/float manipulation being done by the CPU, right? And I don't need to convert it into the regular floats at any time. Something like breaking up the significant digits into smaller integer/float chunks based on the prec and then piecewise adding/subtracting/multiplying and then combining the result? No clue how the internals of the Decimal module work though, all is guesswork.

languid onyx
lean dome
#

I meant that ultimately the actual calculations must involve integer/float manipulation being done by the CPU, right?
Integer, yes, float, no.
And I don't need to convert it into the regular floats at any time. Something like breaking up the significant digits into smaller integer/float chunks
If you can't losslessly represent a number like 0.3 as a single float, how could you hope to losslessly represent it as the product of multiple floats?

languid onyx
#

@lean dome
Thanks! Will check it out.

For my GPU purposes, based on the downstream analysis, the high precision decimal object will give a tiny integer which is the actual output. And that is all I want. Hence if decimal like calculation can be broken into 32-bit ints, I was hoping to do it on a GPU (Nvidia ones can handle 32-bit ints?). But it looks like the decimal module has a lot of padding code surrounding this decimal -> int breakdown on piece-together.

lean dome
#

for there to be any hope of accomplishing what you want, you're gonna need to read and internalize that wiki page, and understand how Decimal works. Just like a regular float, it has a sign bit, exponent bits, and significand bits. They're just interpreted in a different way.

#

And CPUs and GPUs are really fast at working in base 2, and not at working in base 10.

lean dome
#

from what I can find from a quick google, Mandelbrot set renders typically use doubles...

#

and others use fixed point, instead of floating point.

#

and CPUs typically have 80 bit floating point registers, which might be able to be used in some cases.

languid onyx
fierce mantle
#

Hey guys can anyone tell my what sort of data this is and point me in the right direction to go learn about it?

#

-3.200000 -0.480000 -3.040000 -0.480000 -2.720000 c\n-0.320000 -2.560000 -0.160000 -2.400000 0.160000 -2.240000 c\n0.480000 -2.240000 0.800000 -2.080000 1.440000 -1.920000 c\n1.920000 -1.760000 2.240000 -1.600000 2.400000 -1.600000 c\n2.560000 -1.440000 2.720000 -1.280000 2.720000 -1.120000 c\n2.720000 -0.800000 2.560000 -0.640000 2.400000 -0.480000 c\n2.240000 -0.320000 1.920000 -0.320000 1.440000 -0.320000 c\n1.120000 -0.320000 0.800000 -0.320000 0.480000
-0.480000 c\n0.320000 -0.800000

stark prawn
#

well, where did you get it from?

fierce mantle
#

it's decompressed flatedecode but it doesn't look the same as other decompressed flatedecode

#

it's normally straight up bytes

stark prawn
#

mayb u parsed them as floats instead of bytes by accident

fierce mantle
#

what a pickle i've found myself in

#

nah i've deffs handled everything as bytes

ruby mortar
#

guys Δ± have data mining final exam its really important for me to get higer result can sombody help me after 4-5 hour its not long

#

actually Δ± fucked up in yhe first time

#

now its make-up exam

lean dome
#

!rule 5 @ruby mortar

halcyon plankBOT
#
Rules

5. Do not provide or request help on projects that may break laws, breach terms of services, be considered malicious or inappropriate. Do not help with ongoing exams. Do not provide or request solutions for graded assignments, although general guidance is okay.

lean dome
#

We will not help with ongoing exams.

ruby mortar
#

okey

#

sorry

stable pecan
# 

In [7]: from random import randrange, choices

In [8]: NODES = list(range(20))
   ...: my_graph = {node: choices(NODES, k=randrange(2, 6)) for node in NODES}

In [9]: my_graph
Out[9]:
{0: [9, 18],
 1: [2, 19, 1],
 2: [16, 8, 19, 15],
 3: [12, 15, 1, 9, 14],
 4: [4, 0, 15, 1, 8],
 5: [16, 4, 0, 11],
 6: [18, 18],
 7: [9, 6],
 8: [7, 6, 7],
 9: [4, 17, 5, 3],
 10: [6, 10, 14, 9, 11],
 11: [3, 18, 6, 17],
 12: [11, 2, 3],
 13: [11, 7, 3, 18],
 14: [6, 9, 15, 6],
 15: [16, 13],
 16: [10, 9, 16],
 17: [17, 10, 5, 11, 15],
 18: [16, 4, 19, 12],
 19: [15, 7]}
#

note choices needs a sequence so you can't use dictionary keys

# 
In [10]: choices(dict.fromkeys("abcdef"), k=3)
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-10-9203d8559d44> in <module>
----> 1 choices(dict.fromkeys("abcdef"), k=3)
...
#

though you can just use a range object directly, don't need to make a list first

# 

In [14]: range(20)[3]
Out[14]: 3

one doesn't see too many examples of indexing ranges

#

range objects have some useful features that are a bit esoteric

#

or at least less used

vocal gorge
#

huh. I always assumed random.choice has a special case for handling range objects, but if they are like this, it might as well just work with them like lists... cool.

keen hearth
#

I think this is actually a fairly subtle problem.

#

One sec while I do some research...

#

Is the desired graph directed or undirected?

#

Actually, I think I just forgot the meaning of the term 'simple graph' πŸ˜„

vocal gorge
#

it's equivalent to generating a random symmetric matrix with 2-5 nonzero entries in each ro- oh, has to be simple too, yikes.

keen hearth
#

The thing is, there are probably many different such distributions, with different properties.

keen hearth
#

Alright, so, I did some reading, and found this algorithm:

  1. Randomly generate the degree sequence.
  2. Generate a simple (not necessarily connected) graph with that degree sequence:
    2.1) Give each vertex a number of 'stubs' (two stubs connect to make an edge) matching its degree.
    2.2) Repeatedly select any vertex, and bind all of its stubs to other vertices' stubs to form edges (always choosing the other vertex with the most stubs left).
  3. Connect the graph, without changing the degree sequence.
  4. Shuffle the edges to make it random, while keeping it simple and connected.
#

It's the algorithm under the heading "Markov chain Monte-Carlo algorithm"

#

Generating the degree sequence is just a matter of doing: ```python
degree_sequence = sorted(
random.choices(range(2, 6), k=num_nodes),
reverse=True
)

#

I was having a go at implementing it but got distracted sorry πŸ˜„

#

Yep. I think that's the desired behaviour in this case.

#

random.sample selects without replacement.

#

It's generating the degree sequence, which is like the number of edges out of each node.

#

It's presumably fine for two nodes to have the same degree.

#

Sorry for mixing the terms node/vertex and edge/arc πŸ˜„

#

Not sure what you mean. πŸ€”

#

Ah no, this isn't generating the edges themselves, just the number of edges (the degree) of each node.

#

So it's a random choice from range(2, 6) because each node should have at least 2 edges, and at most 5 edges.

#

It's just the first step in the algorithm.

#

Oh, are you talking about the code Salt posted earlier?

#

The code I posted only generates the degree sequence, which is the degrees of the nodes sorted in reverse order.

#

Alright πŸ˜„

#

Np

ionic ibex
#

Hey, so I was just watching some youtube videos and they mentioned binary search and I had previously heard about it and wanted to make an implementation of it. So I gave it a go. Is this a good implementation or is it bad and hard to read? ```py
#tVal: Target Value
#l: List
#sVal: Smallest Value
#lVal: Largest Value
def binarySearch1(l, tVal, sVal=0, lVal=0, index=0):
if index == 0 and lVal == 0: index, lVal = math.floor((len(l))/2), len(l)
if l[index] == tVal: return index
elif l[index] > tVal: lVal, index = index, math.floor(index/2)
elif l[index] < tVal: sVal, index = index, math.floor((index+lVal)/2)

return binarySearch1(l, tVal, sVal, lVal, index)
agile sundial
#

why do you need to condense everything

#

just press enter

ionic ibex
#

Haha yeah, idk as I don't work with other people and I myself just for some reason think it's easier to read I usually condense it like that

vocal gorge
#

Instead of math.floor(a/b), you can do a//b.

ionic ibex
#

Oh okay, thank you. Is it like a to-integer division sign or something?

agile sundial
#

it's floor division

ionic ibex
# 
def binarySearch1(l, tVal, sVal=0, lVal=0, index=0, comp=0):
    if index == 0 and lVal == 0: index, lVal = (len(l))//2, len(l)
    if l[index] == tVal: return comp
    elif l[index] > tVal:
          lVal = index+1
    elif l[index] < tVal: 
          sVal = index-1
    return binarySearch1(l, tVal, sVal, lVal, (sVal + lVal) // 2, comp+1)
``` Why would the change in the index declaring make such a big difference in the search? It went from averaging about 45 comparisons to 13. The new index declaration is the (sVal + lVal) // 2
keen hearth
#

Binary search is often a little bit trickier to implement in practice than you would think.

#

They key thing is to think in terms of an invariant, which is just a property that is guaranteed not to change throughout the execution of the algorithm.

#

Although you seem to have implemented it recursively.

ionic ibex
#

Oh okay, thanks. Is it bad to use it recursively or would it have any effect?

fiery cosmos
#

Hey

ionic ibex
#

Hey

agile sundial
#

in this case, recursion is slower than iterative

ionic ibex
#

Why would that be?

agile sundial
#

calling a function is slower than doing another iteration

ionic ibex
#

Then why would someone ever use recursion if they can just use iteration and it would be faster?

agile sundial
#

recursion is sometime easier to use

stark prawn
#

readability/maintenance but that's partially subjective

#

some algorithms break down nicely recursively

ionic ibex
#

Oh okay that makes sense

agile sundial
#

like tree traversal algorithms

ionic ibex
#

Yeah

eager hamlet
#

hey, is there an algo/data structure that can get all the points (x, y) that are strictly greater than a given point (a, b)?

#

(ping 2 help thx)

brave oak
#

in other words how do you order points

#

my first impression is Euclidean distance from origin but it could be any metric

eager hamlet
#

uh

#

oh yeah

#

(a, b) is strictly greater than (c, d) if a >= c and b >= d

#

wait sorry

#

i shouldn't have said strictly greater

#

just greater than or equal to

brave oak
#

hm

brave oak
#

it seems to me like a basic BST would work?

#

you don't really have a total ordering but

#

you can treat (a, b) and (c, d) where a >= c and d >= b as equal

#

...does that make sense?

#

πŸ€”

#

actually

#

if it's greater than or equal to

#

that wouldn't work

#

or

#

you could have two trees

#

one for each coordinate

#

but that would be a lot slower

#

hm there's probably a better solution

#

the problem is the ordering

lean dome
#

what do you mean by "all the points"? do you have some collection of points and you're trying to find which of them are greater than some reference point?

eager hamlet
lean dome
#

off the top of my head, two binary search trees - one that is point-by-x, one that is point-by-y. Search the first tree to find all of the points with high enough X, search the second tree to find all of the points with high enough Y, and then take the intersection of the two sets.

eager hamlet
#

oh

#

i mean that's O(N)

#

or (log N + N)

lean dome
#

hm. isn't this just a graph traversal problem with weighted edges? The only points that are interesting are the start location, the target location, and the start and endpoint of each springboard. There's a cost for getting from each interesting location to each other interesting location, there's some locations that cannot ever reach other locations (since you can't walk or spring backwards), and your goal is to find the path with the lowest cost from the start location to the target location

#

so that's a directed, acyclic graph, and the weight of any given edge is the amount of moves it takes to reach the latter vertex from the former - either by springing for one action or by walking for (x2-x1 + y2-y1) actions.

#

granted that's still a graph with up to 20,002 vertices, though - I'm sure it can be simplified further than that...

#

Ah, you can start building it up from the origin, and then you only need to keep a running tally of the cheapest path from the origin to each other vertex...

eager hamlet
#

uh

#

wouldn't building it up

#

take too much time

clever stratus
#

Hi, I have a list of times, and I need to calculate the difference between each time, anyone know an easy way to do this that is not too complicated?

lean dome
#

[t2 - t1 for t1, t2 in zip(lst[:-1], lst[1:])] perhaps?

clever stratus
#

damn, you are a god if this works

#

I would have never thought of that, thanks!!

lean dome
#

!e ```py
lst = [1,2,3,5,7,10]
print([t2 - t1 for t1, t2 in zip(lst[:-1], lst[1:])])

halcyon plankBOT
#

@lean dome :white_check_mark: Your eval job has completed with return code 0.

[1, 1, 2, 2, 3]
wicked coyote
#

also, I just wanted to check if my implementation of building a graph is correct (I know that there isn't a "correct" way of implementing a graph as it is based on a problem, but I am wanting to make sure if my implementation is rarely used or if it can be improved)

# 
social_strucutre = [[1,2],[2,3],[1,4],[5,6],[7,6]]
social_strucutre.sort()
graph = {}
for element in social_strucutre:
    if element[0] in graph:
        graph[element[0]].append(element[1])
    else:
        graph[element[0]] = [element[1]]
print(graph)
#

and that implementation is for the below problem

stark prawn
#

looks like a typical adjacency list implementation to me @wicked coyote

safe acorn
#

Bruh use formatted code blocks

languid ember
#

hello idk if Im in the right channel but I'm a beginner, and I wanted to make a simple algorithm that generates a password.. and I'm not sure if my method is the most efficient but its kind of well randomized

#

it looked pretty neat and simple but I'm very sure that it can be easily cracked

wispy hare
worldly sigil
#

I'm playing around with the mandelbrot set, but I'm not sure how I to do the "zooming" at a specific point? I basically start from -2-2i to 2+2i - I suppose I need to shrink that area for each zoom, right?

candid pulsar
#

hey, super beginner here, is it possible to use python to create a gui that then fill an excel file ? I got a student job and at this place they use a computer with an open excel sheet as a checkout. It's long and boring when people pay because I have to write the type and sub type of item, the price, the amount, et weight, all that manually x)

#

So I'm wondering if it is possible to easily make a GUI with like dynamic box for the type and subtype and that can calculate the price instead of me

vocal gorge
#

Not #algos-and-data-structs, but yeah, that's possible. The GUI will probably be the most annoying part, as you'll have to learn the basics of some GUI library.

candid pulsar
#

oky, thanks !

abstract umbra
#

Hey, I need some help for a math exercise, and i need Python, but I don't understand how to do it. It's for a square matrix "M" order 2, we note s(M) the sum of the coefficients of M. We consider the matrix A=(1 2)
(3 4)

  1. Determine s(A^k) for k belonging {1, 2, 3}.

2)Write a python function "seuil (M)" which take for argument a real number superior or equalt to 10 and return the smallest natural number k =>1 as s(A^k)=>M

With the help of this function, determine the smallest natural number k =>1 as s(A^k)=>2021

#

If someone can help me? It will be super nice

vocal gorge
#

It doesn't sounds like an algorithm problem, really, you just calculate higher and higher powers of A.

#

numpy will make this trivial. The @ operator is how you do matrix multiplication in it.

abstract umbra
#

But the probleme is, i don't know how to use an Ide Python and i don't know how to write a python functions 😭

vocal gorge
#

!e

import numpy as np
A = np.array([[1,2],[3,4]])
tot = A
for i in range(5):
    print(f"s(A^{i}) = {np.sum(tot)}")
    tot @= A
halcyon plankBOT
#

You are not allowed to use that command here. Please use the #bot-commands channel instead.

vocal gorge
abstract umbra
#

oh

#

This is the function ?

vocal gorge
#

!resources, I suppose, but it's hard to learn programming from scratch quickly.

#

!resources

halcyon plankBOT
#
Resources

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

https://pythondiscord.com/pages/resources
agile sundial
#

hm, that's a bug or not ?

#

can you do that again i'll take a screenshot

vocal gorge
#

!resources, I suppose, but it's hard to learn programming from scratch quickly.

#

this?

agile sundial
#

yeah

#

it should only say "did you mean: !resources" not the rest of your sentence

vocal gorge
# 
s(A^1) = 10
s(A^2) = 54
s(A^3) = 290
s(A^4) = 1558

is the output

abstract umbra
#

in the function we don't need any return ?

vocal gorge
#

That's not a function, and it's not doing what the second question asks either.

abstract umbra
#

ah

#

okay

#

Thanks a lot for the first question πŸ˜‰

#

and for the sencond, do you have any idea ?

vocal gorge
#

I mean, yes, but you're supposed to write it yourself.

#

The idea is simple though - calculate higher and higher powers of A until you get one with a sum that's >= the number you were passed; return what power that is.

abstract umbra
#

i don't know all the function,

#

It will help me so much

#

or anybody else ?

#

so @vocal gorge do you know how to make the function ?

main flower
#

Hey. It's not a python question, but I'm wondering, how did you understand dynamic programming?

sudden kernel
#

How would I find a path in a tree that involves a specific set of nodes

#

Let's say this is the tree. How would i find a path that includes [0,6,2,4,3,7]. You can go back from a path as long as you get the nodes

πŸ“Ž unknown.png
#

The answer is 6 β†’ 1 β†’ 0 β†’ 2 β†’ 3 β†’ 7 β†’ 3 β†’ 4 but I was curious how they got that answer.

kindred coyote
#

There could be multiple answers ^ but they need to be the shortest path. It could also be 7 > 3 > 4 > 3 > 2 > 0 > 1 > 6, 4 > 3 > 7 > 3 > 2 > 0 > 1 > 6

#

Forgot to add (yes that's an alt)

main flower
#

I'd just use recursion

#

Like

#
  1. Choose a random node (from list of wanted nodes)
#
  1. Run dfs or sth like that
#

For every instance of dfs, pass an array or sth like that where you can check if node v (from wanted nodes) was visited

#

Also

stable pecan
#

always start on a leaf and know that other leaves will add an extra step

main flower
#

Pass a list/vector/array whatever which will keep the path

#

When you Reach a point where all wanted nodes were visited then just stop and retrive values from that vector

stable pecan
#

(it won't matter which leaf node you start on)

#

actually it could matter

kindred coyote
#

One solution i saw is thst you could eliminate all nodes that aren't in the list

#

But that might lead to no paths

main flower
#

Well, yeah

small drift
fiery cosmos
buoyant badger
#

can anyone help me out in a call ?

wicked coyote
# 
N = 7
#Keeping track which nodes are visited
visited = [False for i in range(N)]
#Edges in list
social_structure = [[1,2],[2,3],[1,4],[5,6],[7,6]]
#Converting edges into a graph
#Extending the reversed version of the edges so it isn't directed
social_structure.extend([element[::-1] for element in social_structure])
social_structure.sort()
graph = [[] for i in range (N)]
for element in social_structure:
    graph[element[0]-1].append(element[1])
#Finding the Subsets
def dfs(index, father):
    global visited
    visited[index] = father
    for path in graph[index]:
        if visited[path-1] != father:
            dfs(path - 1, father)
for i in range(len(visited)):
    if visited[i] == False:
        dfs(i, i)
print(visited)
#

Is this the most effecient way to find all of the different connected components in a graph ?

vocal gorge
#

Running DFS or BFS (doesn't matter) on every non-visited node in order is the common way, yeah.

vocal gorge
# wicked coyote ```py N = 7 #Keeping track which nodes are visited visited = [False for i in ran...

Node that you can even number them by component:

next_component = 0
for i in range(len(visited)):
    if visited[i] is False:
        dfs(i, next_component)
        next_component += 1
print(f"Total components found: {next_component}")

Oh, and note how I used is False instead of == False. 0 is equal to False, but is False only detects Falsees. I think using comparison in your code might produce bugs in which the component with a father of 0 will be considered nonvisited, and recalculated each time.

#

(for context, a is b means id(a) == id(b), and id gives the memory address of an object. So only a few things should be compared using is - mainly, you use is to do checks like is True/is False/is None when you want to not accidentally detects ones/zeros as such.)

wicked coyote
#

okay, ty! πŸ™‚

vocal gorge
#

at worst, however many neurons there are in the typical 5-year-old's brain, so 10-100 billion or so, times however many you need to represent a neuron (though an actual neuron network would be a better choice).

dusky plank
#

.code

buoyant badger
#

can anyone help me out with recursion ?? i dont get the logic of this question