#algos-and-data-structs

1 messages · Page 151 of 1

fiery cosmos
#

why is this a while loop
everywhere i look, the elements that were not "merged" are added using a whiel loop
but wont it only be one element
its either 1 or 0 elements
when merging 2 lists they can only either be the same size, or be 1 off

#

like here, the 4 7 and 2 part, only the 7 wotn have a partner to compare to so it will be simply adde don
like no need for a while loop there

#

i would really appreciate any help on the matter, thank you1

#

why cant this block of code just be replaced with:

# 
if leftpointer < len(left_array):
  array[mergedpointer] = left_array[leftpointer]
  #no need to update pointers as last step
elif rightpointer < len(right_array):
  array[mergedpointer] = right_array[rightpointer]
#

!e

def merge_sort(array):
    if len(array) > 1:
        midpoint = int(len(array) / 2)
        left_array = array[:midpoint]
        right_array = array[midpoint:]
        #recursive call on left and right side
        merge_sort(left_array)
        merge_sort(right_array)
        #merge step, compare the left most element of one array to the left most of the other
        leftpointer = 0
        rightpointer = 0
        mergedpointer = 0
        while leftpointer < len(left_array) and rightpointer < len(right_array): #check if both left and right have values in it
            if left_array[leftpointer] < right_array[rightpointer]:
                array[mergedpointer] = left_array[leftpointer]
                leftpointer += 1
            else:
                array[mergedpointer] = right_array[rightpointer]
                rightpointer += 1
            mergedpointer += 1 #increment the position of the merged pointer we do this for both cases
        #once we have ran out of elements in either one of the sublists, we can add the remaining elements to the array
        if leftpointer < len(left_array):
          array[mergedpointer] = left_array[leftpointer]
          #no need to update pointers as last step
        elif rightpointer < len(right_array):
          array[mergedpointer] = right_array[rightpointer]
        

array = [5,23,1,2,45,6,4,2,1,5,6,1,3,4,6,3,2,1,3,4,5,6,3,2]
merge_sort(array)

print(array)```
halcyon plankBOT
#

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

[1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 2, 1, 4, 3, 2, 4, 3, 4, 5, 6, 3, 2]
fiery cosmos
#

why did this not work

#

?

haughty mountain
#

(also, who calls these pointers, that's just wrong, they are indices)

sharp nexus
#

I had a situation earlier where I found that a floodfill to calculate distances followed by tracing back from the target to find a shortest path was faster than implementing Dijkstra's algorithm using the heapq module. I'm curious why this is.

glossy breach
#

Isn’t floodfill O(V+E) while dijkstra has an extra log factor

#

It’s faster if your graph isn’t weighted

coarse apex
#

has anyone heard of or seen an audio analysis algorithm that distinguishes the different tones made by a conga drum? i'm working on that and looking for prior work to cite.

coarse apex
#

and if anyone is interested in hearing about or working on the project i'm all for including you

shut breach
#

that sounds very specific
I'd guess you'd have to use some sort of general audio analysis and figure out how to distinguish congo drum tones yourself

shut breach
#

that code doesnt produce that error for me

#

also this is off-topic for this channel

haughty mountain
coarse apex
#

Which channel is better for this?

keen hearth
#

We were actually discussing adding a multimedia-processing channel at the last staff meeting.

coarse apex
#

Yes, good idea. I'm using fft. The algo already works fine

#

I'll try data science and ai, too, then. Thanks

charred oyster
#

Can anyone recommend any books for learning data structures and algorithms that uses python code?

flint lichen
#

What's the time complexity of sqrt() ?

red abyss
#

@flint lichen math.sqrt()? It should be constant time, to a very good approximation. math.sqrt(1e308) will take roughly the same time to compute as math.sqrt(1.1). If you're passing a Python int to math.sqrt you'd also need to take into account the time for the implicit conversion to float; that conversion does potentially depend on the size of the input (but only in a fairly limited way).

#

But if you're asking about math.isqrt, that's a whole nother ball game.

fallow agate
#

Hi, Anyone please correct my understanding(Involves insertion sort algorithm)
When an element is copied in the list like below, it’s overriding the existing value.

#

Output:

#

But, when the same copy functionality is used in Insertion sort algorithm, instead of overriding, the value is getting inserted & the remaining values are moving to right.

#

Output:

fiery cosmos
# haughty mountain it's not about the sizes being similar, you might need to merge something like [...

if you were to merge 3,4 and 1,2 it would be done in this part of the code

while leftpointer < len(left_array) and rightpointer < len(right_array): #check if both left and right have values in it
            if left_array[leftpointer] < right_array[rightpointer]:
                array[mergedpointer] = left_array[leftpointer]
                leftpointer += 1
            else:
                array[mergedpointer] = right_array[rightpointer]
                rightpointer += 1
            mergedpointer += 1 #increment the position of the merged pointer we do this for both cases
        #once we have ran out of elements in either one of the sublists, we can add the remaining elements to the array``` 
no?
fiery cosmos
#

you are creating a temp variable and then assinging it after

haughty mountain
fiery cosmos
#

so if it was like 3,4 and 1,2,3 then 3 would be compared with nothing and would just simply get appended

#

like what happens at this timestamp

#

the 2 is compared with the 3 and the 5 with the 8

haughty mountain
#

no, conceptually this is what happens

output = [], left = [3, 4], right = [1, 2, 3]
# 1 < 3
output = [1], left = [3, 4], right = [2, 3]
# 2 < 3
output = [1, 2], left = [3, 4], right = [3]
# 3 == 3, just pick one of them
output = [1, 2, 3], left = [3, 4], right = []
# no elements left in the "right" list, loop ends
fiery cosmos
#

OHHH that makes sense

#

i was under the impression that when 3 is added then 1 also has to be added

#

like i thought output would be 1,3,2,4,3

haughty mountain
#

you keep picking whatever number is smaller

#

so that the output is still sorted

fiery cosmos
#

which now makes no sense lol

#

thank you

#

really helped me

haughty mountain
#

that's what makes merge sort work

#

the merge step takes two sorted sequences and merges them into a new bigger sorted sequence

flint lichen
fiery cosmos
flint lichen
#

Also, anyone got a good resource to learn how to calculate time complexity of a DP problem ?

I can compute the time complexity of a decision tree, but when I start to memoize the solution I start getting confused.

split patio
#

idk if I can ask this question here but is python capable of making a stock trading algorithm?

fiery cosmos
split patio
#

oh ok thanks

#

so what language would you recommend in that case?

fiery cosmos
#

What exactly do you mean by stock trading algorithm?

#

Though Python is probably not a bad choice

dapper sapphire
#

So in an interview, can we say something like, "We could try x approach, but it wouldnt work because of y" and so on?

woven onyx
humble flower
#

is grokking algorithms good for beginners?

agile sundial
hidden orchid
#

can anyone help me excel in python specificly writing in cells

haughty mountain
#

e.g. often there are several different approaches that might work, but each might have issues, e.g. approach 1 might be slow for large parameters X, and approach 2 might be slow for large parameters Y

#

which one is the best fit will depend on problem constraints

karmic halo
gritty wedge
lyric breach
# gritty wedge https://stackoverflow.com/questions/72071424/trying-to-create-family-tree-from-d... 
# Construct a tree from an adjacency list. Adjacency list can be any order.

# Input: [(1, [4]), (3, [1, 2])]
# Output: Node(3, [
#     Node(1, [
#         Node(4, [])
#     ]),
#     Node(2,  [])
# ]

from dataclasses import dataclass
from typing import List, Tuple

@dataclass
class Node:
    name: int
    children: List['Node']

def build_tree(adjacency_list: List[Tuple[int, List[int]]]) -> Node:
    # Convert to dictionary so we can quickly look up parents/children
    d = {key: value for (key, value) in adjacency_list}

    # Need to find the root node -- which node is in the parents set but never referred to?
    all_parents = set()
    all_children = set()

    for parent, children in adjacency_list:
        all_parents.add(parent)
        for child in children:
            all_children.add(child)
    
    possible_roots = list(all_parents.difference(children))
    if len(possible_roots) != 1:
        raise Exception("Could not find root of tree; invalid data?")

    root = possible_roots[0]

    def inner(name):
        if name in d:
            children = [inner(child) for child in d[name]]
        else:
            children = []
        return Node(name, children)

    return inner(root)

if __name__ == '__main__':
    print(build_tree([(1, [4]), (3, [1, 2])]))
#

@gritty wedge You basically have a tree written as an adjacency list, and you want to build the full tree in memory

#

The approach I used is to find the root, then use a recursive algorithm to build the tree

haughty mountain
#

fwiw there is rarely much use for not keeping things as adjacency lists

vocal gorge
#

why not adjacency sets? quick target in neibs[node] checks are nice

gritty wedge
gritty wedge
dapper sapphire
haughty mountain
#

I just find it a weird statement, it reads to me as "We could do X but it wouldn't help at all."

#

if it was "we could do X and it would solve the problem, but it's super expensive so not a good idea" it's another story

#

the latter can also be helpful since you have found some route through the problem

#

it might give some key insight about the problem that can be used

#

e.g. if sorting solves the problem then maybe there are nicer ways to keep something sorted, like a BBST

#

or maybe you just need to know the minimum (which sorting makes easy) in which case a heap might be useful

#

In contrast I think the example statement you gave doesn't give any useful information

dapper sapphire
#

I think I'm starting to get some idea, if we have an approach in mind we could talk about it's trade offs, pro and cons. Takes less time, more space. How we can improve the approach if it takes too long.

#

In a nutshell when we are explaining our thought process it needs to have some useful information.

thick echo
# 
class Solution:
    def minimumCardPickup(self, cards: List[int]) -> int:
        """
        For array cards:

        Return the length of the shortest subset that contains two matching cards 

        [3,4,2,3,4,7]

        eg for this, it's 4.
        """
        
        
        mydict = {}
        
        answer = float('inf')
        
        for index in range(len(cards)):
            card = cards[index]           
            
            if card in mydict:
                prev_index = mydict[card]
                curr_answer = len(cards[prev_index: index + 1])
                
                answer = min(curr_answer, answer)
                
                mydict[card] = index
            else:
                mydict.setdefault(card, index)

            
        
        
        return answer if answer != float('inf') else -1
# 
curr_answer = len(cards[prev_index: index + 1])
curr_answer = index - prev_index + 1```
what's the time complexity of a length of a slice?  I thought it would be constant because reflection, but apparently it's actually linear.
fallow agate
#

hi.. something wrong is happening in the below merge sort code, anyone pls tell me if you find.

# 
def merge_sort(custom_list):
    #Code for dividing 
    if len(custom_list) > 1:
        mid_index = len(custom_list) // 2
        left_list = custom_list[:mid_index]
        right_list = custom_list[mid_index:]
        merge_sort(left_list)
        merge_sort(right_list)
    #Code for merging   
        i = 0
        j = 0
        sorted_list = []
        while i < len(left_list) and j < len(right_list):
            if left_list[i] < right_list[j]:
                sorted_list.append(left_list[i])
                i += 1
            else:
                sorted_list.append(right_list[j])
                j += 1
        while i < len(left_list):
            sorted_list.append(left_list[i])
            i += 1
        while j < len(right_list):
            sorted_list.append(right_list[j])
            j += 1
        return sorted_list

custom_list = [5,4,1,3,2]
print(merge_sort(custom_list))
#

Output:

thick echo
#

general piece of advice

#

you have too much code in one single method

#

of merge_sort

#

if you instead divide merge sort into 3-4 different functions

#

the main merge sort and some helper functions

#

I guarantee your bugs will sort themselves out a LOT quicker

#

yes I can see what's happening

#

when you reach your LAST recursive cast in merge sort

#

ie when you have [5,4]

#

you are not sorting 5, 4 properly

#

You are recurring a badly sorted array of values

#

take a step back, take a deep breath, and try and refactor your implementation of merge sort.

# 


def sort_and_merge_2_lists():

def divide_list_in_half():

def mergesort():

mergesort()
#

try these helper functions

open moth
#

how to generate distinct list 2d matrix example [[1,2],[3,5],[3,6,8]] difference with [[1,2],[3,5]] is [3,6,8]

runic tinsel
#

try to rephrase

#

this is a mess

cloud portal
#

What are a few of the best performing online complete coverage path planning algorithms?

fiery cosmos
#

Join me in this fun interactive session that will help you in exploring Data Analysis and also walk you through the details of the Microsoft Learn Student Ambassador Program.

Key Takeaways:-
-Introduction to Microsoft Learn Student Ambassador
-Overview of what is Data Analysis
-Creating Microsoft Excel Dashboard
-Introduction to Microsoft Power BI
-Quiz and Giveaways
-Q&A

EVENT DETAILS -
Date - 8th May 2022
Day - Sunday
Time - 5:00 PM IST
Duration - 1 Hour
Platform - Microsoft Teams
Event Host - Aditi Gulati (Alpha Microsoft Student Ambassador)

If anyone is interested then DM for registrations

haughty mountain
thick echo
haughty mountain
jolly mortar
#

wish there was a simple way to slice without copying

stable pecan
haughty mountain
stable pecan
#

i have an implementation somewhere of this

stable pecan
jolly mortar
#

👀

haughty mountain
stable pecan
# jolly mortar 👀

something like this, without multiple copies:

In [36]: from sacks.sequences import View

In [37]: my_list = list(range(20))

In [38]: my_view = View(my_list)

In [39]: my_view
Out[39]: View(sequence=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19], _range=range(0, 20))

In [40]: my_view[5:10]
Out[40]: View(sequence=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19], _range=range(5, 10))

In [41]: _[::2]
Out[41]: View(sequence=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19], _range=range(5, 10, 2))

In [42]: for i in _:
    ...:     print(i)
5
7
9
jolly mortar
#

mm

stable pecan
#

this would only be efficient if the sequence was huge though

jolly mortar
#

why?

stable pecan
#

cause python is pretty fast at making small lists

thick echo
jolly mortar
#

surely that copies too

stable pecan
#

islice doesn't copy

haughty mountain
jolly mortar
#

i mean, it builds up from scratch

stable pecan
haughty mountain
stable pecan
# 
    def __reversed__(self):
        for i in reversed(self._range):
            yield self.sequence[i]
haughty mountain
#

I meant you could almost return self

stable pecan
#

the _range is providing the indices, you don't want to yield those

#

also don't want __reversed__ to mutate the object

#

do you mean return a new view?

#

you could do that

#

with the range reversed

haughty mountain
#

I'm still a bit annoyed that reversed(range(...)) doesn't do that

jolly mortar
#

i think self._range = _range or range(self._olen) should check is None explicitly to account for empty ranges being falsy

haughty mountain
#

while range(...)[::-1] does

jolly mortar
#

reversed needs to return an iterator though

stable pecan
jolly mortar
#

pithink if an empty range is passed in self._range gets set to the entire length of the seq

stable pecan
#

maybe _olen should be length of the range then

#

i haven't looked at this in a year

haughty mountain
#

is it just me or is allowing insert and delete on a view pretty sketchy?

#

at least not without mutating the range extents

stable pecan
#

it's a mutable view -- was sort of the point, it gets invalidated as soon as you insert or delete though

#

so operations afterwards will raise

#

if all you do is iterate with it, it won't invalidate

haughty mountain
#

ah, I should read docstrings huh?

slender sandal
#

Is reversed not implemented like this:

def reversed(iterable):
    return iterable[::-1]
haughty mountain
#

I'm used to things like C++ spans where it's literally "this contiguous chunk in memory"

haughty mountain
slender sandal
#

Yes

haughty mountain
#

it's not

slender sandal
#

I mean, basically

haughty mountain
#

you can reverse things that are not indexable/slicable

slender sandal
#

What? Really?

stable pecan
#

yeah

# 
In [43]: my_dict = dict(enumerate("abcdefg"))

In [44]: list(reversed(my_dict))
Out[44]: [6, 5, 4, 3, 2, 1, 0]
haughty mountain
#

!e

print(reversed(range(10)))
print(range(10)[::-1])
halcyon plankBOT
#

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

001 | <range_iterator object at 0x7f6f0b879500>
002 | range(9, -1, -1)
haughty mountain
#

this is a pet peeve of mine

#

!e you lose useful range abilities

print(range(10)[::-1][2])
print(reversed(range(10))[2])
halcyon plankBOT
#

@haughty mountain :x: Your eval job has completed with return code 1.

001 | 7
002 | Traceback (most recent call last):
003 |   File "<string>", line 2, in <module>
004 | TypeError: 'range_iterator' object is not subscriptable
slender sandal
#

Are there specific iterator types for each corresponding iterable type?

stable pecan
#

i don't know if there is one for each iterable type

haughty mountain
#

not necessarily, yeah

slate jay
slate jay
# slate jay

How is the for loop and if statement n/2 ? I mean the big o notation

haughty mountain
#

I...do not like that analysis

slender sandal
#

Me neither

#

How do they analyze it like that

stable pecan
#

just looks like O(n) from line 1

slate jay
stable pecan
#

line 2 is constant

#

line 3 is constant

haughty mountain
#

I think ned tries to do an average case analysis, hence the /2 in places

fiery cosmos
#

O(n) has something related to time to execute a program?

slender sandal
vocal gorge
#

the most confusing thing here for me is where the 3 comes from

haughty mountain
#

yeah, I have no clue about the 3

vocal gorge
#

is nedbat, like, considering how many bytecode instructions a for-loop iteration is?..

stable pecan
#

the thing is that O(n/2) is the same as O(n) so it's not important

vocal gorge
#

yeah, these coefficients make it more confusing than useful in some ways

haughty mountain
vocal gorge
#

it's impossible to construct a worst case for a quicksort with random pivot choice, right?

slender sandal
#

Assume it picks the worst random pivot

jolly mortar
slender sandal
#

Tough I don't know how that algorithm works

haughty mountain
#

I don't mind annotating the if with 1*n/2 (though I would have probably preferred O(n)) here. It's annotating "how many times does this thing run" multiplied by cost

haughty mountain
stable pecan
#

that's confusing, assigning a tuple or getting the next element could be some P number of steps, dunno the bytecode -- and it doesn't change the O(n) whatever the P is

haughty mountain
#

you could get a lot of different factors depending on how far down you need to go until you say stuff are "primitives"

vocal gorge
#

!e

import dis
dis.dis("""
for a,b in iterable:
    do_smth(a,b)
""")
halcyon plankBOT
#

@vocal gorge :white_check_mark: Your eval job has completed with return code 0.

001 |   2           0 LOAD_NAME                0 (iterable)
002 |               2 GET_ITER
003 |         >>    4 FOR_ITER                 9 (to 24)
004 |               6 UNPACK_SEQUENCE          2
005 |               8 STORE_NAME               1 (a)
006 |              10 STORE_NAME               2 (b)
007 | 
008 |   3          12 LOAD_NAME                3 (do_smth)
009 |              14 LOAD_NAME                1 (a)
010 |              16 LOAD_NAME                2 (b)
011 |              18 CALL_FUNCTION            2
... (truncated - too many lines)

Full output: https://paste.pythondiscord.com/sijupucume.txt?noredirect

vocal gorge
#

I count 4 steps per iteration, not 3 🥴

#

FOR_ITER, UNPACK_SEQUENCE, 2 STORE_NAMEs

#

and it's an implementation detail anyway

#

and no guarantees bytecode instructions are equally fast (almost certainly not)

stable pecan
#

well, it's not my favorite analysis

# 
for child_name, mom_name in moms:  # O(n)
    if child == child_name:        # O(1)
        return mom_name            # O(1)

is how i would do it

haughty mountain
#

though it's way worse if you can construct bad input

#

iirc you can make an actual worst case O(n log n) if you do something like median of medians

#

but it's just slow in absolute terms

haughty mountain
#

with the understanding that you need to multiply the relevant stuff to get the actual complexity

slender sandal
vocal gorge
#

whoops, yeah, I was going to count that and then forgot 😩

slender sandal
#

And at the last time it does FOR_ITER and sees it needs to jump outside the loop I guess

vocal gorge
#

I'd probably do something slightly fancier like

for child_name, mom_name in moms:  # O(1) setup, does O(n) iterations
    if child == child_name:        # O(1) each
        return mom_name            # O(1) (only executes once)

and leave to the reader the calculation of O(1) + O(n)*O(1) + O(1) = O(n)

vocal gorge
slender sandal
#

So GET_ITER is to get the iterator of the iterable?

#

What if you iterated an iterator?

vocal gorge
#

that makes all Iterators Iterable (see collections.abc), which is nice

slender sandal
#

!e

from dis import dis
dis("""for x in iter(range(3)):
    print(x)""")
halcyon plankBOT
#

@slender sandal :white_check_mark: Your eval job has completed with return code 0.

001 |   1           0 LOAD_NAME                0 (iter)
002 |               2 LOAD_NAME                1 (range)
003 |               4 LOAD_CONST               0 (3)
004 |               6 CALL_FUNCTION            1
005 |               8 CALL_FUNCTION            1
006 |              10 GET_ITER
007 |         >>   12 FOR_ITER                 6 (to 26)
008 |              14 STORE_NAME               2 (x)
009 | 
010 |   2          16 LOAD_NAME                3 (print)
011 |              18 LOAD_NAME                2 (x)
... (truncated - too many lines)

Full output: https://paste.pythondiscord.com/mexukufeqa.txt?noredirect

jolly mortar
stable pecan
haughty mountain
#

there are for sure cases where constant factors matter in analysis though, like what's the complexity of this?

def f(n):
  out = []
  m = n
  while m > 0:
    out += [1]*m
    m //= 2
slender sandal
#

What's n to start with

#

Oh

haughty mountain
#

n is just the input parameter

jolly mortar
#

n log n?

haughty mountain
#

O(n)

slender sandal
#

!e

print((-1)//2)
#

Oh dear god

jolly mortar
#

(-1)//2

slender sandal
#

Oh yes

haughty mountain
#

yeah yeah, assume n >= 0

jolly mortar
halcyon plankBOT
#

@slender sandal :white_check_mark: Your eval job has completed with return code 0.

-1
slender sandal
#

Oh dear God

jolly mortar
#

oh yeah its floor division

#

floor(-0.5) is -1

haughty mountain
jolly mortar
#

oh

#

right

slender sandal
haughty mountain
#

point being: you can't just ignore constant factors all the time

#

you need to kinda know when you can ignore them

slender sandal
stable pecan
#

so you know the number of times you loop add 1 to the list

slender sandal
#

So n is the number of times it adds [0] * n to the list

#

So isn't it O(n)

haughty mountain
#

I...should probably not have re-used n for the thing I'm dividing by 2

stable pecan
#

you should end up with n**2 1's

#

in the limit

haughty mountain
haughty mountain
#

2n - 1

stable pecan
#

just O(n) then

haughty mountain
#

the overall complexity is O(n) yes, but if you jump into the analysis ignoring constant factors you could easily arrive at O(n log n)

#

O(log n) iterations doing O(n) work each

#

(which is not wrong because of what O-notation is, but it's not a tight bound)

slender sandal
#

For a ridiculous optimization, use >>= 1 instead of //= 2

haughty mountain
#

pls no

slender sandal
#

It's floor division on positive integers anyway

haughty mountain
#

code with clarity in mind

slender sandal
#

Also why add m

slender sandal
haughty mountain
#

in sane languages /2 and >>1 do the same thing in the end anyway

slender sandal
#

I smell an opinion

haughty mountain
#

I mean it's nice to leave that cruft to a compiler and write the obvious code

vocal gorge
# 
def f(n):
  out = []
  m = n
  while m > 0: # O(log(n)) iterations
    out += [1]*m # m iterations each time
    m //= 2 # O(1)

adding the ms gives n + n/2 + ... + 1, sums to 2n, which is O(n) still

haughty mountain
#

so I can say O(n) without it being potentially ambiguous

haughty mountain
slender sandal
#

Wait

haughty mountain
#

well, it sums to 2n-1

#

but no difference to the analysis

slender sandal
#

Why is it 2n - 1

haughty mountain
#

rather than?

slender sandal
#

Why is it 2n to begin with

haughty mountain
slender sandal
#

That just tells me O(log(n)) == O(n)

haughty mountain
# 
n + n/2 + n/4 + ... =
n*(1 + 1/2 + 1/4 + ...) =
2n
vocal gorge
haughty mountain
slender sandal
#

I know it doesn't

vocal gorge
# 
def f(n):
  out = []
  k = 1
  while True:
      cur = n//k
      if cur==0: return out
      out += [1]*cur
      k += 1

Here's a fun one for y'all 🥴

slender sandal
#

Doesn't this loop exactly n times

vocal gorge
#

it does.

haughty mountain
slender sandal
#

Or n + 1 times considering it needs to loop one more time to return

haughty mountain
#

smells like harmonic series

vocal gorge
vocal gorge
slender sandal
#

Yeah that's where I looked

haughty mountain
#

ah, I summed the wrong part

#

n log n then?

vocal gorge
#

yup

haughty mountain
#

factor out the n and you have the harmonic series left

vocal gorge
#

yeah, it's O(n H_n), where H_n is the nth harmonic number, and those grow as O(log n)

slender sandal
vocal gorge
haughty mountain
#

I did the big O for the typical implementation of Eratosthenes' sieve once, you need to go kinda deep to make is somewhat rigorous

vocal gorge
haughty mountain
#

and it's fun to arrive at O(n log log n)

slender sandal
stable pecan
vocal gorge
vocal gorge
stable pecan
#

because they uses some of these shadowcasting algorithms to determine what characters are visible in terminal games

slender sandal
#

What shadows exist in terminal games

stable pecan
slender sandal
#

What does casting a shadow on a character do in terminal games

#

Oh my god this looks gorgeous

vocal gorge
#

"shadow" as in "some object is behind a wall from your character's viewpoint and isn't visible", Roie

#

line-of-sight is also a common term

stable pecan
#

yeah, also field-of-view algorithms

haughty mountain
#

what we ended up with in my case is more akin to quickselect in the analysis

slender sandal
stable pecan
#

but it's the only algorithm i've ever found that uses continuous interval math

#

which i think is really cool

haughty mountain
#

you mean stuff like working with ranges of reals?

stable pecan
#

that's right

haughty mountain
#

I think it's not that uncommon when you do computational geometry like this

stable pecan
#

probably not, but i haven't encountered it

#

except for this

haughty mountain
#

though I haven't done much of it, CG is kinda painful to me

stable pecan
#

i mean, i've written a couple of raycasters, but they are purely discrete

haughty mountain
#

especially since it tends to be really fiddly when dealing with floats

#

if I can avoid the question of floating point comparison I will do that 😛

stable pecan
#

this algorithm keeps track of the blocked intervals of angles on each step and then adds more blocked intervals on other steps, so you want an efficient way to union intervals

#

interesting here, is that even sympy does O(n**2) interval math i think the last time i checked

#

but you can do a lot better if your intervals are sorted

ionic locust
#

Could someone help explain to me how the function below is O(n^2)?

def my_function(twod_arr):
    for arr in twod_arr:
        for num in arr:
            print(num)

my_2d_arr = [[1,2,3],[1,2,3],[1,2,3]]
my_function(my_2d_arr)

Form my perspective, the inner loop, for num in arr should be independent from the input size of twod_arr, because the individual arr isn't really dependent on the input size of twod_arr.

So really, my_function is more sort of like:

def my_function(twod_arr):
  for arr in twod_arr:
    # execute some code that is O(1)

Where the # execute some code is just a constant, and the runtime depends on the size of twod_arr, and thus the function should be O(n).

This is opposed to another program where I can see it should be O(n^2):

def my_func(n):
    for i in range(n):
        for j in range(i,n):
            print(j)

Since for j in range(i,n is directly dependent on n. So you can multiply:
O(1) from print(j)
n-ish from for j in range(1,n)
n from for i in range(n)
Which gives O(n^2).

Sorry for the long post, to reiterate my question is why is the first code example O(n^2). Thanks haha

haughty mountain
#

it's n² if n is the side length of the "matrix" you have as input

#

n=3 in your example

ionic locust
#

I was watching a yt vid and he said that its O(n^2), (maybe I copied the code example wrong haha)

unknown.png
vocal gorge
#

well, if the input array is n-by-n, then it's O(n^2)

haughty mountain
#

n in the two cases there is 3 and 4 I think

#

but you generally need to specify what n is

ionic locust
#

Oh fr

#

Ohhh I havent gotten to matrices yet so just took the number of lists within the list as n

haughty mountain
#

if n is the total number of elements (e.g. 3*3 = 9) it's O(n)

#

so the definition of n matters a lot

ionic locust
#

No, I think im taking n as the number of sides

#

Could you explain to me step by step how its O(n^2)? How does for each i in row relate to the number of sides in array_2d

haughty mountain
#

there are n rows, each row has n elements

#

the example is dealing with square matrices

ionic locust
#

ohh

#

ohh each row has n elements

#

yea ok that makes sense

#

ty haha

#

Ok then, so if its not a square matrix but instead just a list of lists like so, would it be O(n), if n is the number of lists within the list (which. with my_l, n=4)?

def my_function(my_list):
    for l in my_list:
        for num in l:
            print(num)

my_l = [[1,2,3],[1,2,3],[1,2,3],[1,2,3]]
my_function(my_l)
vocal gorge
#

if it's constant for some reason, then yeah, O(n). But if it's not, you need to include it in the complexity.

ionic locust
#

ah alright

ionic locust
# vocal gorge I'd say it's not valid to ignore the fact that it also scales with the number of...

By scaling with the no, of elements in each sublist, youre referring to the square matrix right? Where the number of elements in the sublist is directly related to the number of sides?

Im just talking about a list of lists where theyre not related. If I instead have 100,000 integers in each sublist that wouldnt’ affect O(n) (where n is the length of the overarching list) in that case right?

vocal gorge
#

Sure, since 100000 is a constant.

ionic locust
#

but the length of each sublist shouldnt matter should it? If each sublist increases in length by 1, how would you calculate big o for that?

vocal gorge
#

Well, if each sublist has length m and there's n of them, then the complexity would be O(n*m)

ionic locust
#

oh actually then yeah, with each larger input into the overarching list youd have an increase of 1 iteration in the sublist

ionic locust
#

Can you have multiple variables in big o notation? Is O(m * n) a valid expression?

#

It makes sense in terms of if you define all the variables, just never seen it done b4

vocal gorge
#

I'd say that's the main point here, yeah. Before you start calculating the complexity, you should ask "with regards to what variables"? Here, you can consider the number of sublists (let's call it n), the number of elements in each sublist (let's call it m), or the number of elements total (N=n*m).
If you consider only n and take m to be some constant, it's O(n). If you consider only m and take n to be some constant, it's O(m). If you consider both, or consider the number of total elements, it's O(n*m) or O(N) (same thing).
What to consider as variables depends on your task - what actually changes when this snippet is going to be run. Here, I'd say both n and m can change and so are important, but that's just my opinion.

ionic locust
#

Definitely definitely, thanks for the insight rly appreciate it!

agile sundial
#

it would be really weird to say "my algorithm runs in O(1), but i define n as (something that doesn't really make sense in the context of the problem)"

fallow agate
#

Hi.. i am trying to understand how merge sort works. i written the program by seeing couple of websites & code is working fine. Understood most code, except below where recursion involved. if anyone can explain me in simple manner, please..

# 
#Merges two sorted lists
def merge(list1, list2):
    combined_list = []
    i = 0
    j = 0
    while i < len(list1) and j < len(list2):
        if list1[i] < list2[j]:
            combined_list.append(list1[i])
            i += 1
        else:
            combined_list.append(list2[j])
            j += 1
    while i < len(list1):
        combined_list.append(list1[i])
        i += 1
    while j < len(list2):
        combined_list.append(list2[j])
        j += 1
    return combined_list

#Splits the list untill it contains one element
def merge_sort(custom_list):
    if len(custom_list) == 1:
        return custom_list
    mid_index = int(len(custom_list)/2)
    left_list = custom_list[:mid_index]
    right_list = custom_list[mid_index:]
    return merge(merge_sort(left_list),merge_sort(right_list))
  
print(merge_sort([3,1,4,2]))
#

The below line of code where recursion happens is confusing me.

vocal gorge
#

The main idea is fairly simple: merge, given two sorted list, combines them into a sorted list.
Now, note that single-element lists are always sorted.
So if you just divide the initial list into halves, and them into halves and so on, you'll eventually end up with single-element lists that are sorted. You can combine them pairwise into sorted 2-element lists, them into 4-element ones and so on, until you get the original list but sorted.

#

So the mergesort algorithm is just "divide the list into halves, mergesort each half, merge the sorted halves into a sorted list".

terse spade
#

i've got this sort of execution flow between files going on for a UI and i was wondering if there is a better way to avoid circular imports (well they're not really avoided here i'm just avoiding importing partially initialized modules) than to use imports outside the top of the file.

unknown.png
agile cove
#

lemme look

#

it looks like you're over modulizing your code honestly

#

or is Main_menu a class and not a package

#

can i see more of your code?

#

also this isn't really a ds/algos question

terse spade
#

well basically i've got these classes that define gui
example:

class Main_menu:
    container = pygame_gui.core.UIContainer(display_rect, gui_manager, visible=1)
    exit_ = pygame_gui.elements.UIButton(relative_rect([[.01, .94], [.1, .05]], resolution), 'Exit', gui_manager, container)
    settings = pygame_gui.elements.UIButton(relative_rect([[.01, .88], [.1, .05]], resolution), 'Settings', gui_manager, container)

    load_game = pygame_gui.elements.UIButton(relative_rect([[0.5, 0.5], [0.2, 0.1]], resolution, mode='centered'), 'Load Game', gui_manager, container, object_id='LoadGame')

    @staticmethod
    @event_response(settings, pygame_gui.UI_BUTTON_PRESSED)
    def settings_response(event: Event):
        print('entering settings')
        Main_menu.container.hide()
        from ui.settings import Settings
        Settings.container.show()

    @staticmethod
    @event_response(load_game, pygame_gui.UI_BUTTON_PRESSED)
    def load_game_response(event: Event):
        print('entering load game screen')
        Main_menu.container.hide()
        from ui.load_game import Load_game
        Load_game.container.show()
        Load_game.reload_selection()

    @staticmethod
    @event_response(exit_, pygame_gui.UI_BUTTON_PRESSED)
    def exit_response(event: Event):
        print('quitting')
        raise SystemExit

and since this is a single ui page, and a rather simple one, having all of them in one file is inconvenient

also this isn't really a ds/algos question
sry i didn't know where to put it where i could paste images

agile cove
#

oh

#

i see the issue

terse spade
#

all of the imports in my original question are these classes that store ui in a neat, dot addressable way

agile cove
#

you should be handling "load game" in your ui package

#

for example

terse spade
#

this is the file structure

unknown.png
agile cove
# 
    def load_game_response(event: Event):
        print('entering load game screen')
        Main_menu.container.hide()
        from ui.load_game import Load_game
        Load_game.container.show()
        Load_game.reload_selection()

      def load_game_response(event: Event):
        print('entering load game screen')
        Main_menu.container.hide()
        from ui.load_game import load_game_procedure
        load_game_procedure()
#

does this make sense

#

the whole point of modules is to isolate their code

#

you're violating the abstraction barrier by doing what you're doing

#

does that make sense?

terse spade
#

long response incoming...

#

ok so this would make sense but the thing doesn't exactly work like you think.

basically i've got this event loop :

    while True:

        for e in pygame.event.get():
            if e.type == pygame.QUIT:
                raise SystemExit

            menu.process_events(e)
            gui_manager.process_events(e)

which calls this from the ui.menu file :

def process_events(event: Event):
    for i in _event_responses:
        if i(event):
            break

in the same file, _event_responses is populated this way :

_event_responses: List[Callable[[Event], bool]] = []


def event_response(ui_elements: List | UIElement, event_types: List | int):  # used as a decorator
    if isinstance(ui_elements, UIElement): ui_elements = [ui_elements]
    if isinstance(event_types, int): event_types = [event_types]

    def _event_response_handler(fnc: Callable) -> Callable[[Event], bool]:

        def _event_handler(event: Event):
            if event.type in event_types:
                if event.ui_element in ui_elements:
                    fnc(event)
                    return True
            return False

        _event_responses.append(_event_handler)
        return _event_handler

    return _event_response_handler

then, each ui page containing file can add new ui element responses using the event_response decorator

# generic example
class MenuPhase:
    
    container = pygame_gui.core.UIContainer(_display_rect, gui_manager, visible=1)
    interactable = pygame_gui.elements.UIButton(relative_rect([[.5, .5], [.2, .2]], resolution, mode='centered'), 'interactable', gui_manager, container)
    
    @staticmethod
    @event_response(interactable, pygame_gui.UI_BUTTON_PRESSED)
    def interactable_response(event: Event):
        print('interacted')

so when i say "pass over execution", that's a lie. the truth is that i load a new ui page, turn off the old page by hiding its container and turn on the new one by showing its container.

#

there was only 31 characters left in the discord character limit wew

agile cove
#

oh, i see

#

that makes it a little more complicated

terse spade
#

so in truth, nothing actually gets executed from these files except the event_responses. the truth is everything gets handled by the pygame_gui and pygame event loop, and i just turn on and off event handling for different pages

agile cove
#

then maybe just do what you're already doing?

#

it doesn't seem that bad

#

or try to find some people who use pygame

#

my python experience is just solely for research/swe purposes

terse spade
#

ok i just felt like having these imports here had to be wrong but if there's no inherent issues with non top level indent imports and circular import architecture that's cool

ionic shuttle
#

I have a function defined like this:
f(x, y) = 0 if xy == 0 else 1
What is the best way to get the output over a range in numpy. I know about np.vectorize, but the function is evaluated in python. Is there a way to do this like with simple addition, multiplication, comparison of ndarrays?

haughty mountain
ionic shuttle
#

f(x, y) = 1 if xy == 0 else 0
other way around 🙂

haughty mountain
#

still, xy=0 is on the x and y axes

ionic shuttle
#

im plotting 3d graphs

haughty mountain
#

so this is 1 on the axes and 0 everywhere else?

ionic shuttle
#

there are a few other fucntions Im working with, I just picked this one as an example

haughty mountain
#

basically give it your x and y values and it will spit out a rectangular matrix you can use in vectorized operations

ionic shuttle
#

I used this already but how do I map the function over the values after this to get a Z?

haughty mountain
#

x*y == 0 is already basically right, though you might want to cast it to some other type than bool

In [11]: import numpy as np

In [12]: x, y = np.meshgrid(np.linspace(-1, 1, 11), np.linspace(-1, 1, 11))

In [13]: z = (x * y == 0).astype(np.float64)

In [14]: z
Out[14]:
array([[0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],
       [1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.],
       [0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.]])
onyx meteor
#

Guys......why am I finding data structures and algs so difficult to learn.....it's irritating

#

And those leetcode questions are scaring me

uneven spindle
#

It takes a while to get used to

#

I’d recommend taking Princeton course on it online

onyx meteor
uneven spindle
#

Have u tried implementing any of the structures?

onyx meteor
#

But still ......iam currently Learning trees ......and......

onyx meteor
fathom delta
#

Hi guys, if i have these 15 numbers, and i apply median of medians quickselect with blocks of three on this array, which element is used as the pivot?

Screen_Shot_2022-05-02_at_2.13.01_pm.png
#

i;m sorta confused on how it works

fallow agate
#

Hi, please see the below merge sort code once. It’s working fine, when I am understanding the working, have a doubt..

#

code:

#

doubt: Input list is custom_list & the code is preparing output also on the same custom_list. doesn't output list override the input list?

lament shale
#

Leetcode: 1385
Can anyone tell me what is wrong with this code?

class Solution:
def binary_search(self, nums: List[int], check: int, test: int) -> bool:
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2
if abs(nums[mid] - check) > test:
if nums[mid] >= 0:
high = mid - 1
else:
low = mid + 1
else:
return False
return True

def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
    arr1.sort()
    arr2.sort()
    distance = 0
    for i in range(len(arr1)):
        search_res = self.binary_search(arr2, arr1[i], d) 
        if search_res:
            distance += 1
    return distance

This is not working for this testcase.
[-803,715,-224,909,121,-296,872,807,715,407,94,-8,572,90,-520,-867,485,-918,-827,-728,-653,-659,865,102,-564,-452,554,-320,229,36,722,-478,-247,-307,-304,-767,-404,-519,776,933,236,596,954,464]

[817,1,-723,187,128,577,-787,-344,-920,-168,-851,-222,773,614,-699,696,-744,-302,-766,259,203,601,896,-226,-844,168,126,-542,159,-833,950,-454,-253,824,-395,155,94,894,-766,-63,836,-433,-780,611,-907,695,-395,-975,256,373,-971,-813,-154,-765,691,812,617,-919,-616,-510,608,201,-138,-669,-764,-77,-658,394,-506,-675,523,730,-790,-109,865,975,-226,651,987,111,862,675,-398,126,-482,457,-24,-356,-795,-575,335,-350,-919,-945,-979,611]

37

tulip moth
#

Hello, do you have any resources to recommend for learning the Bellman-Ford algorithm?

keen hearth
tulip moth
keen hearth
#

The issue is with this part of the code: ```py
if abs(nums[mid] - check) > test:
if nums[mid] >= 0:
high = mid - 1
else:
low = mid + 1
else:
return False

#

The invariant you're trying to maintain is that:

  1. all the values that come before index low should be less than check - test
  2. all the values that come after index high should be greater than check + test
#

So in order to maintain that invariant, you'd want to do something like this: ```py
if nums[mid] - check < test:
low = mid + 1
elif nums[mid] + check > test:
high = mid - 1
else:
return False

#

Hope that makes sense @lament shale

haughty mountain
#

daily reminder to use [l, r) ranges in your binary search to simplify code

keen hearth
#

The most important thing for getting a binary search right in my opinion is to use an invariant.

haughty mountain
#

the invariant in the [l, r) case is a lot simpler though

#

e.g. f(l) is true f(r) is false

#

rather than f(l) is true and f(r+1) is false, which means a bunch of ±1 to compensate

#

the try to do early exit also introduces another +1, which is independent of the others, but that's not super clear reading the code pithink

#

I don't think the early exit even helps that much, it adds more logic to the body which might even make it slower. This is for sure a topic where I think people are learning things wrong a lot of the time

while r - l > 1:
  mid = (l + r)//2
  if cond(mid):
    l = mid
  else:
    r = mid
pallid current
#

How can I get the head of linkedlist L1?

Screenshot_from_2022-05-02_17-02-15.png
pallid current
vocal gorge
#

That'd be l1 itself. Unless it's empty, in which case l1 is None.

#

Look at the definition of the ListNode class you're provided with - that's how it's structured. A bunch of objects, each having a reference to the next one.

keen hearth
keen hearth
#

It looks like your plan is to convert the two numbers to regular integers first, add them, then convert the result back to a linked list? It would be more in the spirit of the question to see if you can do the addition without converting the two numbers to integers and back.

#

And actually, the resulting code may end up shorter.

#

Think about what the usual procedure is for adding two numbers together by hand.

jolly mortar
#

grabbing a calculator with the left and plugging in the numbers with the right?

pallid current
haughty mountain
#

I think after sorting you can just do a sweep with two indices

#

and if you do a binary search you only need to find the first index where value[index] >= target, e.g. using my example code

def any_in_range(arr2, center, radius):

  def cond(x):
    return x < center - radius
  
  l = 0
  r = len(arr2)
  while r - l > 1:
    mid = (l + r)//2
    if cond(arr2[mid]):
      l = mid
    else:
      r = mid

  # At this point `r` is the first value that could be in range
  return center - radius <= arr2[r] <= center + radius

Edit: fixed some mistakes, algo seems overall fine, mostly just stuff like initializing l and r

#

And sweeping with two indices is pretty simple as well.
It's the exact same idea: find the first value possibly in range, and the index of that value is non-decreasing, so we can do a single sweep.

def count_in_range(radius):
  arr1 = sorted(arr1)
  arr2 = sorted(arr2) + [10**9]  # add "inf" to remove any
                                 # need for boundary checks
  n_in_range = 0
  i = 0
  for x in arr1:
    while arr2[i] < x - radius:
      i += 1
    if x - radius <= arr2[i] <= x + radius:
      n_in_range += 1
  return n_in_range
#

(I should probably verify this last one works by submitting it, I haven't test run it at all)

#

forgot to invert the answer, but other than that it works fine, version to match what leetcode expects

class Solution:
  def findTheDistanceValue(self, arr1: List[int], arr2: List[int], radius: int) -> int:
    arr1 = sorted(arr1)
    arr2 = sorted(arr2) + [10**9]  # add "inf" to remove any
                                   # need for boundary checks
    n_in_range = 0
    i = 0
    for x in arr1:
      while arr2[i] < x - radius:
        i += 1
      if x - radius <= arr2[i] <= x + radius:
        n_in_range += 1
        
    return len(arr1) - n_in_range
keen hearth
vocal gorge
#

also Java naming conventions

haughty mountain
#

I think I inverted the binary search condition pithink

keen hearth
haughty mountain
#

fun how I have more issues to connect the binary search solution together than writing the linear scan

keen hearth
#

If you want to go the binary search route, you could also use the bisect module: ```py
class Solution:
def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
arr2 = sorted(arr2)
total = 0
for elem in arr1:
i = bisect.bisect_left(arr2, elem - d)
j = bisect.bisect_right(arr2, elem + d)
total += (i >= j)
return total

haughty mountain
#

yeah, bisect works fine in this case

#

but fwiw it's very specialized for finding the insertion point in a sequence

#

lol, found the bug

# 
center - radius <= r <= center + radius
```should have been
```py
center - radius <= arr2[r] <= center + radius
#

this dumb trick of tacking infinity at the end of a list removes so many annoying bounds checks

#

welp, I also need to start with l at -1 because I don't know of my condition is true at 0

#

feels like the binary search is kinda fiddly in this case in general pithink

#

I could insert -inf before and inf after if i wanted to hackily make it work

#

in any case it's like 2x slower than the simple and less error prone sweep

haughty mountain
#

lol, thanks copilot

unknown.png
#

leetcode constraints pls

1 <= arr1.length, arr2.length <= 500

#

with such small input you can just do whatever silly thing

keen hearth
lament shale
# keen hearth The issue is with this part of the code: ```py if abs(nums[mid] - ch...

Thanks, this is my code which worked:

class Solution:
def binary_search(self, nums: List[int], check: int, test: int) -> bool:
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2
if abs(check - nums[mid]) <= test:
return False
elif check > nums[mid]:
low = mid + 1
else:
high = mid - 1
return True

def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
    arr2.sort()
    distance = 0
    for i in range(len(arr1)):
        search_res = self.binary_search(arr2, arr1[i], d) 
        if search_res:
            distance += 1
    return distance
young tangle
karmic halo
#

Hi can someone help me with this simple python problem. I may be overthinking https://stackoverflow.com/questions/72093859/how-do-i-delete-a-particular-sheet-in-a-flat-file-with-python?noredirect=1#comment127383697_72093859

Stack Overflow
How do i delete a particular sheet in a flat file with python?

Im trying to write a loop that browses through my directory to find a file that starts with a particular filename('TVC') and deletes a specific sheet within that file. In the below case 'Opt-Ins' i...

fiery cosmos
#

what is the best way to optimize a peak finding system so that it can effectively match my data set

#

i have a realtime use situation where the total variance will vary wildly across individual data sets and across different data sets

#

and so far i have not managed to achieve useful peak decomposition of my data

#

im presently using a matlab-equivalent function for it

#

but i would like to use peakutils with perhaps some kind of matching? i am not a data scientist at all, just a hobbyist trying to adapt an algorithm called intrinsic time -scale decomposition

#

but it doesnt adapt well to my data set, or so it seems

#

the decomposition trends it produces do not seem to correspond significantly to any measurable feature in the data- decomposing it into up to 12 different frames and then removing them before recomposition leads to static

#

that is to say, again, because i am not skilled or meaningfully educated with data analysis, i have applied this to audio, and then deleted some of the decompositioned trends and reintegrated the others, and then fed-through the frame to the audio output, where i listen and examine specgram with audacity to see what changes

#

I had some hopes this method could lead to useful intermediate results for noise reduction

#

It is used commercially at present in EKG and a lot of research has come out in the past 6 years on the method

#

so i decided to port it to python over the last month

#

I'm done porting ITD as it was written in matlab

#

except for the interpolation routine, that part of the baseline decomposing method was contributed by a friend, and consists of akima spline calculations combined with a linear interpolation(im not even sure how it works, i just know it doesnt crash, LOL)

#

it appears to be a reversable decomposition routine because

#

when you reintegrate all the frames of the output, despite the complex math involved in their creation

#

they add up to the input with e-12 precision or better decimal

#

sometimes exactly

#

the difference seems to be due to near-NAN values and INF values which do have a habit of appearing in the composition as well

#

I am not sure how or why that happens, my best effort is to add normalization and pound the keyboard in frustration

fiery cosmos
#

seen here, the orange line is the decomposition of the series in jupiterlite

decomposition.png
fiery cosmos
#

this is a large picture, click open original and then magnifying glass for full detail

fiery cosmos
keen hearth
#

Sorry to tell you this after typing all that out, but this is a question for #data-science-and-ml @fiery cosmos

#

I recommend copying your question over there.

#

This channel is more for algorithms in the computer science sense than the data science sense.

fiery cosmos
#

you say this because i have posted some matplotlib plots to try to visualize the data, but this algorithm is not a statistical analysis algorithm- it is a frequency decomposition algorithm

#

i have no experience with data science or with matplotlib aside from today and using it for specgram generation

#

this is the publication, although the algorithm itself is better depicted in another paper. it is presently being used for EKG, mechanical failure analysis, and seismology, all of which I do appreciate use a lot of data science approaches- however, isnt ITD better categorized with FFT, wavelet transforms and EMD as a fundamental algorithm in the computer science sense?

#

"We introduce a new algorithm, the intrinsic time-scale decomposition (ITD), for efficient and precise time–frequency–energy (TFE) analysis of signals. The ITD method overcomes many of the limitations of both classical (e.g. Fourier transform or wavelet transform based) and more recent (empirical mode decomposition based) approaches to TFE analysis of signals that are nonlinear and/or non-stationary in nature. The ITD method decomposes a signal into (i) a sum of proper rotation components, for which instantaneous frequency and amplitude are well defined, and (ii) a monotonic trend. The decomposition preserves precise temporal information regarding signal critical points and riding waves, with a temporal resolution equal to the time-scale of extrema occurrence in the input signal. We also demonstrate how the ITD enables application of single-wave analysis and how this, in turn, leads to a powerful new class of real-time signal filters, which extract and utilize the inherent instantaneous amplitude and frequency/phase information in combination with other relevant morphological features."

As depicted in the matplotlib graph posted, the data set of 250 was indeed decomposed into a monotonic trend in the second row

#

it is unironically true that IMD will likely see a great deal of utilization in improving machine learning approaches and data science and makes use of data science interpolation and peak fitting functions, but frankly, i dont understand how those work any better than i understand how ITD does, and if you look at the code, you can tell me which it better relates to - data science or computer science- and i can take it to the relevant expertise

keen hearth
#

I'm just saying that you'll probably get better answers from the people that frequent that channel. I personally don't know very much about signal processing.

fiery cosmos
#

alright, i think i agree

crystal shell
#

Hello

#

Is python good for Data Structure?

shut breach
crystal shell
#

Haan how is it with Python?

#

I tried it and found it great. But i m currently on my basics so, wanted to know about higher levels!

warm ibex
#

I have a question

#

for a series like 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, ... how do I find the sum of the nth term

#

i've tried this all week and have no hope or time left,

#

honestly, I just need an algorithm since apparently I should reduce the complexity and not use loops

#

a single algo for the sum of nth term of this series

crystal shell
haughty mountain
haughty mountain
#

now, to make use of that you need to know how many of those runs you can fit in <= n terms

#

(and then manually handle the small extra, but that part is easy)

#

so, how high do you get in n terms?
hint: ||1 + 2 + 3 + ... + x <= n||

warm ibex
#

Wait no but, the nth term does not work with that formula

#

Like for n = 3, the value is 2

#

so sum is 5

runic oasis
#

Hi guys, I currently need help with a python logic problem.
I need to convert a dict with sublist within, then capture this sublists and transform the dict with simple arguments. Like this.

Example:

dict = [[''], ['215'], ['219,320,352,361'], ['225'], ['220'], ['235'], ['250'], ['242'], ['319']] ; len = 9

the sublist ----> ['219,320,352,361']

transform ----> [219, 320, 352, 361] ; len = 4

Update dict ---> [[''], ['215'], ['219'],['320'],['352'],['361'], ['225'], ['220'], ['235'], ['250'], ['242'], ['319']] ; len = 12

Someone can help me please?

lament totem
#

that's a list not a dict @runic oasis

#

and you probably want to use

#

!d str.split

halcyon plankBOT
#
str.split 

str.split(sep=None, maxsplit=- 1)```
Return a list of the words in the string, using *sep* as the delimiter string. If *maxsplit* is given, at most *maxsplit* splits are done (thus, the list will have at most `maxsplit+1` elements). If *maxsplit* is not specified or `-1`, then there is no limit on the number of splits (all possible splits are made).

If *sep* is given, consecutive delimiters are not grouped together and are deemed to delimit empty strings (for example, `'1,,2'.split(',')` returns `['1', '', '2']`). The *sep* argument may consist of multiple characters (for example, `'1<>2<>3'.split('<>')` returns `['1', '2', '3']`). Splitting an empty string with a specified separator returns `['']`.

For example:
lament totem
haughty mountain
#

e.g. n=12 terms
1 + 2 + 3 + 4 = 10 <= 12, so 4 full terms and 2 extra terms

#

1²+2²+3²+4²+5*2
= 1 + 4 + 9 + 16 + 10 = 40

#

!e

print(1+2+2+3+3+3+4+4+4+4+5+5)
halcyon plankBOT
#

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

40
haughty mountain
#

some derivations

1 + 2 + ... + x <= n
x(x+1)/2 <= n
x² + x <= 2n
(x + 1/2)² <= 2n + 1/4
x <= ±sqrt(2n + 1/4) - 1/2
```and I'll just note that

1² + 2² + 3² + ... + x² = x(x+1)(2x+1)/6

#

!e

from math import sqrt, floor
def f(n):
  x = floor(sqrt(2*n + 0.25) - 0.5)
  extra = n - x*(x+1)//2
  squares = x*(x+1)*(2*x+1)//6
  return squares + extra*(x+1)

print(f(12)) 
halcyon plankBOT
#

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

40
haughty mountain
#

there we go

#

O(1) computation

haughty mountain
edgy flare
#

hey guys, I'm having a little trouble with OOP. trying to apply OOP to my secret auction program, and I'm trying to make an Auction class which will keep a list that tracks the highest bidder, then spit out the highest bidder at the end (I don't even know if this is possible)

#

`from classes import Auction, Bidder
import replit

bidders = {}
print("Welcome to the Auction!")

bid_on = True

while True:
while bid_on == True:
name = input("What is your name?: ")
bid = input("What is your bid?: $")

    bidder = Bidder(name, bid)
    bidders[name] = bidder
    other_bidders = input("Are there any other bidders? (y/n): ").lower()

    if other_bidders == 'y' or other_bidders == 'yes':
        replit.clear()
        continue
    elif other_bidders =='n' or other_bidders == 'no':
        replit.clear()
        bid_on = False
        
# work out who has highest bid
v_list = list(bidders.values())
k_list = list(bidders.keys())
# pos = v_list.index(max(v_list))
# winner = k_list[pos]
bid_list = []
print("Bidders\n --------")

for k,v in bidders.items():
    bid_list.append([k, v.bid])
    print(f"{k}: ${v.bid}")

sorted(bidders.values())
print(bidders)
break`

`class Auction():
def init(self):
self.bid_list = []

class Bidder():
def init(self, name, bid):
self.name = name
self.bid = bid`

tepid fern
#

Hello people, I hope you have a nice day. How could I avoid that when I am making a loop of requests to an API, if the internet cuts me, I lose all the queries that the program had already made and have to start over.

In python is my query

Practically, if the communication is cut, the program waits for it to resume and does not break

fiery cosmos
#

hhello down there

void pecan
#

Other Insert Sort, Bubble Sort and section sort, what other complicated algorithms are there?

agile sundial
#

the actually good sorting algos: quicksort, mergesort, heapsort

#

there's also algorithms completely unrelated to sorting

void pecan
#

What about shellsort?

void pecan
vocal gorge
agile sundial
#

chapter 3 doesn't count

vocal gorge
#

Sure, I guess

#

a simple example would be, say, breadth-first search in a graph

agile sundial
#

well, ig they use algorithms to make the structure work

barren magnet
#

it's complexity is O((n-1)*n!)

haughty mountain
terse frost
fiery cosmos
#

@mossy gorge

#

@mossy gorge

#

@mossy gorge

#

CAN U UNMUTE ME?

#

PLS

#

PLS

#

PLS

halcyon plankBOT
#

:incoming_envelope: :ok_hand: applied mute to @fiery cosmos until <t:1651677400:f> (9 minutes and 59 seconds) (reason: duplicates rule: sent 4 duplicated messages in 10s).

fiery cosmos
#

please stop

mossy gorge
#

Not the way to get unmuted, that's for sure

fiery cosmos
#

xDD

vagrant vapor
#

is there a good source for learning dsa in python for free...

#

please suggest

unborn junco
#

Hi guys, do you guys have like advanced question 1 or 2 related to python datastructures / math with oeprator, which I will use to ask in an interview. Just to get an idea

keen hearth
feral trail
#

I have been solving this problem

unknown.png
#

I have read through the title of the discussion page and it seems like this can only be solved in O(nlogn)

#

However this was how I solved it

def find(time):
    maxLeft, maxRight = time[0][0], time[0][1]
    
    for i,j in time:
        maxLeft = max(maxLeft, i)
        maxRight = max(maxRight, j)
    for i,j in time:
        if ((i > maxLeft and i < maxRight) or (j > maxLeft and j < maxRight)):
            return False
    return True

print(find([[5,8],[9,15]]))
#

And it's O(n) time with O(1) space. Maybe I'm missing some edge case?

#

Sadly it's a leetcode premium question so I can't test out my code except for the 2 given example

#

Basically I just find the maximum range of time through all the input

#

Then run through the input again and check if there are any start time or end time within that range, if yes there are conflict, if no then no conflict

#

Nvm that was just a huge oversight

#

mb

glad vale
#

Hey!
Any idea how to get an answer in the most efficient way?

We have undirected graph **G = (V, E) **and 2 vertices s,t.
We need to implement algorithm that will be checking if there exist edge {p,g} from E which deleted cause the shortest path among s and t extend.

We need to return that edge
for example.
( indexes are the vertices and given list indicate the edges between vertices )

G = [ [1, 2], [0, 2], [0, 1]]
s = 0
t = 2
Answer: (0, 2)
Because the shortest path is
0 -> 2
And if we delete edge (0, 2) it cause the shortest path to extend because it's
0 -> 1 -> 2

runic tinsel
#

so it's like, find all shortest paths, then look for an edge they all use

#

no, then maybe there's no path

worldly agate
#

well, number of shortest paths can be pretty huge so imo it'd be better to just remove each edge and check if the shortest path's length is same

#

if bigger then we found that edge

#

but rn can't think of anything better

#

that'd be like O(VE) so like O(V^3)

haughty mountain
#

isn't is enough to do that for all edges in a shortest path?

#

because either there is an edge that is shared by all shortest paths, or there are independent shortest paths

#

In the former case we find the edge, in the latter no such edge exists

glad vale
#

Hmm that's right

glad vale
#

Like I'm doing BFS and saving some stuff then i will try to look which edges are the same in every path in the same length but for now I'm doing something like this

# 
def longer( G, s, t ):
    que = deque()
    processed = []
    que.append(s)
    pathSoFar = [None for _ in range(len(G))]
    pathSoFar[s] = [s]
    paths = []
    while len(que) > 0:
        v = que.popleft()

        for neighbour in G[v]:
            if neighbour not in processed:
                # processed.append(neighbour)
                que.append(neighbour)

                if neighbour == t and [*pathSoFar[v], neighbour] not in paths:
                    paths.append([*pathSoFar[v], neighbour])

                if pathSoFar[neighbour] is None:
                    pathSoFar[neighbour] = [*pathSoFar[v], neighbour]
                else:
                    if len(pathSoFar[neighbour]) > len(pathSoFar[v]) + 1 or pathSoFar[neighbour][-1] == t:
                        pathSoFar[neighbour] = [*pathSoFar[v], neighbour]
        processed.append(v)

    print(paths)

    return (0,0)
#

So i know that to get an element I have to get all elements of the parent element. but the memory complexity is increasing

#

Remembering the edges is helping but how to use it then... 😳

#

Because if i will have

edges = [
    [(0, 1), (0, 4)],
    [(0, 1), (1, 2)],
    [(1, 2), (2, 3)],
    [(2, 3), (3, 5)],
    [(0, 4), (4, 5)],
    [(3, 5), (4, 5)]
]

For every vertex i still need to know how long is the shortest path

worldly agate
#

So that would make it O(V^2)

haughty mountain
#

find one shortest path, remove one of the edges and find the shortest path again, repeat for all edges in the path

glad vale
#

Hmm would it be more efficient than getting all possible ways to get an destination of the same length and see which edge is common in all paths?

haughty mountain
#

I can easily create a graph with an exponential number of shortest paths

glad vale
#

Because just removing edge seems to me like there should be something better because it's first what came out to mind

glad vale
#

Then we need only to check which edge is in all paths of the same ( smallest ) length if there is one pick it if not there is no such an edge

haughty mountain
#

we can get the paths in O(V+E)
wdym "get"?

#

you sure can't process all the paths one by one

#

or store them

glad vale
#

I mean to traverse the graph using BFS and store several paths at once, not just the one being searched for

haughty mountain
#

how many are "several"?

glad vale
#

With BFS we will get first the vertex which are one edge far then two etc.

#

Look at my code It's not working because i can't see something there but look

haughty mountain
#

but you care about what path you took to get there, right?

#

because you are looking for overlaps in edges

glad vale
#

Possible answers : [(0,2)]

unknown.png
#

But here it's not working because the answer is the only (8,9) but in my array i store 2 path that has more than one edge intersecting

unknown.png
glad vale
haughty mountain
#

here is a very simple graph that has an exponential number of shortest paths

unknown.png
#

yes, it's probably possible do better than O(V) BFS traversals, but I don't know any obvious way off the top of my head

#

but trying to explicitly consider all paths is a no-go

glad vale
#

Okey so you advice my to make this greedy algorithm with deleting the edge form the shortest path and see if the newest shortest path after deleting is greater than previous if so return the deleted edge yes?

haughty mountain
#

that's a path that will for sure work and that is reasonably efficient

#

there is probably some max-flow formulation for this problem, but I'm not good with finding flow formulations

glad vale
#

As a hint I will tell that I currently had BFS, DFS, Topological sort, finding euler cycle and finding the bridges in graph

haughty mountain
#

The problem is FPT parameterized on the distance d and number of edges you are allowed to delete, k: The algorithm is as follows: Find an (s,t)-path of length at most d and branch on the d edges to which you can delete. This results in an algorithm which runs in time O(d^k * n^2).
in this case k = 1, and (I'm assuming) n is the number of vertices, which matches the complexity of the thing I proposed

#

that answer also gives a reference which might be interesting to you

glad vale
#

Hmm thanks @haughty mountain. Will go through that tomorrow because today is late a little.

worthy bane
#

Hi, I have a problem but i'm not sure if someone can help me with that ... I have a grid (4x6) where at first it's empty, the aim of it is to fill all the spaces of the grid in as few attempts as possible with random figures (from a set of six figures). You can skip the figure and get a new one if you want (but this is an extra step)... So my question is, does anyone know about a technique or algorithm in order to minimize the steps to fill the grid?

lament totem
#

So like tetris or?

misty plume
#

is the channel free to ask?

shut breach
misty plume
#

sure, I have a problem with understanding divide and conquer algorithm, they have showed us a base but I don't really get the conditions of the ifs inside the function

#

I have the code

#

I did one problem, but I don't really get the conditions

# 
def _rec_bs_(e, low, high, elements):
    if low > high:
        return -low - 1
    mid = (low + high) // 2
    if elements[mid] == e:
        return mid
    elif e < elements[mid]:
        return _rec_bs_(e, low, mid - 1, elements)
    else:
        return _rec_bs_(e, mid + 1, high, elements)


def rec_binarysearch(e, elements):
    return _rec_bs_(e, 0, len(elements) - 1, elements)
#

so high is the lenght of the base elements you have -1

#

and low begins as a 0

#

e is the element of a sample you are given and elements are a bunch of base elements you have

#

so basically my problem is inside the rec_bs_ function, what do the conditions do for it to work? why first you check if low>high and you would return -low-1

lament totem
#

Not sure why you return -low - 1 @misty plume

#

when low > high that means the element is not present I believe, so you would normally return something like -1

#

Do you understand binary search, and why it works and is quicker than just going through the elements from left to right?

misty plume
#

my guess is that it checks if the item would be on one half or the other of the sample, and from there it gets closer to the values you want based on if it's higher than that mid variable or lower

#

but I might be quite off

lament totem
#

yeah sort of

#

with each step, you eliminate half of the possible numbers

#

So first you check for the middle number, is your number higher or lower

#

if it is lower, than you don't have to check any number higher than the middle number

#

because the values are sorted

misty plume
#

that's why the high becomes mid - 1 on that elif I guess then

lament totem
#

yeah, so after you eliminate the right half of the numbers, you are left with the left half

#

and you take the middle of the left half

#

and check if your number is higher or lower

#

etc.

misty plume
#

so first low > high would determine if your element exists as such?

lament totem
#

Well if you got to a point where low > high, that means your left bound is higher than your right bound

misty plume
#

the elements[mid] == e it's if your element is the middle one

#

and then you check if it's lower or higher than the middle?

lament totem
lament totem
misty plume
#

oooo

#

ok so no matter the problem

#

it's always

#

checking middle

#

higher middle part

#

lower middle part

#

until it either exists

lament totem
#

well each time it either checks the higher or lower part

misty plume
#

or doesn't

lament totem
#

because we can eliminate the rest

misty plume
#

yea and with each loop the sample if halved

lament totem
#

jup

#

So it takes log N steps

#

instead of N

misty plume
#

omg I think I actually get it

lament totem
#

where N is the amount of elements

misty plume
#

like to do it myself

#

and I have 2 more questions

#

if is not too much

lament totem
#

sure shoot

misty plume
#

ok first one, is related with competitive programming but it's on terms of making an input

#

I know how to take in one line with many arguments to group it into a list

#

but then I found this

#

first 8 and 2

#

that's a matrix, and the problem is also a divide and conquer one

lament totem
#

alright, so your problem is taking the input?

misty plume
#

yes, for example for a line

#

i would do

#

things_on_one_line = input().strip().split()

lament totem
#

Do you know about nested lists?

misty plume
#

and then a for with int(things_on_one_line[i])

#

but I haven't done something like that

misty plume
#

or [] []

lament totem
#

yeah, lists within a list

#

That's how people normally represent a matrix

#

each sub list is a row, and the outer list contains all rows

misty plume
#

hmm and to do that I have to declare something like a list of lists and append a whole line into it?

lament totem
#

!e

matrix = []
row_amount = 3
column_amount = 4

for i in range(row_amount):
  row = []
  for j in range(column_amount):
    row.append(j)
  matrix.append(row)

print(matrix)
halcyon plankBOT
#

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

[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]]
misty plume
# 
elements = [[]]
for i in range(8):
    things_to_introduce = input().strip().split()
    elements[i].append(things_to_introduce)
misty plume
#

and the last question

#

would be

#

understanding how to print paths on dijkstra

lament totem
#

dijkstra is a method for finding the shortest path between two needs, what do you need to understand about printing?

misty plume
#

because I get the part on writing a dijkstra to get the number for the shortest path

#

but sometimes they ask a modification

#

where it includes printing the nodes it goes through to get to a selected node

lament totem
#

Well you need to somehow remember for each path where it came from

#

For each node you could store from which node you travelled to it

#

and then you could basically travel back to see what path you took

misty plume
# 
n, m = input().strip().split()
g = []
for i in range(int(n)):
    g.append([])
for i in range(int(m)):
    c1, c2, d = input().strip().split()
    g[int(c1)].append((int(c1), int(c2), int(d)))
    g[int(c2)].append((int(c2), int(c1), int(d)))
origin, destiny = input().strip().split()

def select_min(distances, visited):
    minima = float('inf')
    index = 0
    for i in range(len(distances)):
        if not visited[i] and distances[i] < minima:
            minima = distances[i]
            index = i
    return index


def dijkstra(g, origen):
    distances = [float("inf")] * len(g)
    visited = [False] * len(g)
    visited[origin] = True
    distances[origin] = 0
    for c1, c2, d in g[origin]:
        distances[c2] = d
    for i in range(len(g)):
        best = select_min(distances, visited)
        visited[best] = True
        for c1, c2, d in g[best]:
            distances[c2] = min(distances[c2], distances[c1] + d)
    return distances


result = dijkstra(g, int(origin))
print(result[int(destiny)])```
#

this is how I do a dijkstra, but I never know how to get the "parent" of the node to trace back the path

lament totem
#

It depends on your implementation, but whenever you make a choice of the best node to travel to next, you could update that next node to also store the node at which you are right now

misty plume
#

hmm I see

#

I have an example that does it

#

but I don't get how

# 
 for i in range(1, len(g)):
            next_node = select_min(distances, visited)
            visited[next_node] = True
            path[next_node].append(next_node)
            for start, end, weight in g[next_node]:
                if distances[start] + weight < distances[end]:
                    path[end].clear()
                    distances[end] = distances[start]+weight
                    for i in range(len(path[start]) - 1):
                        path[end].append(path[start][i])
                    path[end].append(start)

    print(distances[e])
    for i in range(len(path[e])):
        print(path[e][i], end = " ")  ```
#

is the same code of before but inside the def_dijkstra they add that bit

#

is there a way to make it easier or shorter?

lament totem
#

I don't have time to look through all this code rn sorry

misty plume
#

yea it´s fine

#

you already helped me a lot with divide and conquer

#

thank you very much

misty plume
#

I do have another question

#

so this is a matrix that it's NxN based on the first number (the eight on the top left)

unknown.png
#

and the 2 in this case, represents "cuts" you make on that matrix

#

and those cuts are horizontal and vertical, on each half and they count for 1, so that 2 would make 16 groups of 4 digits

#

like that, so how would I do that, the input I did like this

# 
side_length, cuts = input().strip().split()
matrix = []
for i in range(int(side_length)):
    numbers_row = input().strip().split()
    for i in range(len(numbers_row)):
        numbers_row[i] = int(numbers_row[i])
    matrix.append(numbers_row)
print(matrix)```
wheat plover
#

hi.. I am working with a library that has a bug in its __init__ function. Is there any way to edit __init__ function MethodType?

sleek gust
#

if i have a list and i get n subsets from that list, then i calculate the sum of the subsets and select maximum sum. Do i get it right that the time complexity of that operation is O(n) where n in the number of subsets?

haughty mountain
#

n times subset length

#

I hope you're not looking at all subsets, because there are 2^len(list) of those

lament totem
keen thicket
#

What sorting algorithm is this? :)

arr = [79, 23, 88, 2, 34, 51, 5, 9, 17]

for currentElement in range(0, len(arr)-1):
	for movingElement in range(currentElement+1, len(arr)):
		if arr[movingElement] < arr[currentElement]:
			temp = arr[currentElement]
			arr[currentElement] = arr[movingElement]
			arr[movingElement] = temp
	print(arr)
lean walrus
#

Bubble sort

covert thorn
sleek gust
# lament totem Well calculating the sum of a subset would be constant if the size doesn't chang...

Thanks! How to express the total complexity if the number of subsets are exponential complexity O(1.6**n). As these are subset made of non adjacent positions, so like Fibonacci (n as number of elements in input array). And sum is linear O(n), but n as the number of subsets.
But as i think about it now the subsets size will increase when size of input array (list) from which subsets are created increase. 🤔

jolly mortar
#

.latex if you have $n$ items, then there are $^nC_r$ subsets with a length of $r$, so your total number of iterations would be $\sum_{r=0}^{n} r \cdot {^nC_r} = n2^{n-1}$

grand havenBOT
jolly mortar
#

.latex in terms of the number of subsets, if $N = 2^n$, $n2^{n-1} = \frac{1}{2}N\log_2N$

grand havenBOT
sleek gust
#

Oh nice I've learnt latex command for discord. Thanks. Still trying to digest the complexity though...

sleek gust
jolly mortar
#

its the number of ways of selecting r objects from a set of n objects

#

n!/((n-r)!r!)

sleek gust
#

Does it make a difference If the subsets are only made of non adjacent positions?

brittle lintel
#

Is it possible to sort like... if you have a list of numbers of two digits, three digits and four digits. You need to insert the elements in a way like it shows all the 3 types in different lists?

#

Like we have 10 random numbers upto 4 digits and then we seperate the accordingly into the 3 types

vocal gorge
#

still exponential, though, so you definitely shouldn't even try iterating over all of them, unless your problem limits n to something very small (like, 20 or less) - an if I recall correctly, your problem (https://www.hackerrank.com/challenges/max-array-sum/problem) does n up to 10**6 or something like that 10**5

haughty mountain
#

that's just a ||simple dp problem|| right?

vocal gorge
#

That's actually a common trick in competitive programming: looking at the input limits to estimate what complexity of an algorithm is expected from you. Very very roughly, you can aim for about 10**6-10**9 operations in a second. Since n goes up to 10**5, even an O(n^2) algorithm is likely too slow. I'd guess you're meant to do some divide-and-conquer approach to do it in O(n log n) or lower

vocal gorge
haughty mountain
#

yeah 10^5 suggests something like n log n, maybe n sqrt n if you want to be weird

haughty mountain
sleek gust
# vocal gorge still exponential, though, so you definitely shouldn't even try iterating over a...

yes i read your message many times and i think i understand it now :). Thanks again!
yest they test it with large numbers so this will not likely pass.
I am trying to understand how to determine the complexity of the full solution, that means selecting the subsets which is 1.6**n (n - size of the input array) and then next step is to make the sum of elements in the subset and compare with the maximum. The comparison operation, and assignment to new max operations are constant time, so can be skipped i think.
So we have the sum operation, which would be linear time complexity i think if the subset size was the same, so the more subsets to sum over the more time it would take.
But in this case we also have subsets of varying size, the larger the input array n the more larger in size sums to do. Not sure how to combine these to time complexities into one for the complete solution.

haughty mountain
#

what is the actual statement of the problem you're trying to solve?

sleek gust
vocal gorge
#

.latex sum_{k=0}^n N_k(n) k

grand havenBOT
vocal gorge
#

lol, so much for latex

#

where N_k(n) is the number of k-element (!) non-adjacent subsets from an n-element array.

#

I'm frankly not sure what N_k is, so this sounds hard.

haughty mountain
vocal gorge
#

so the complexity of the naive solution is the nasty O(n 1.6**n) - because the number of non-adjacent-subsets scales like 1.6**n, and also the time to sum an averagely-sized subset scales like n

sleek gust
#

that was my thinking about it. thank you for confirmation.
is this O(n * 1.6**n) n times 1.6**n ?

vocal gorge
#

yup

sleek gust
#

thank you!

haughty mountain
#

are you familiar with dynamic programming? if not this is a great task to learn and practice it

sleek gust
#

i have read about it when solving this task, and i saw solution which i think is dynamic programming, although not sure. it's pretty simple when you look at it. but difficult if you don't know it 🙂
is this dp?
||

def max_subset_sum(arr):
  t = 0,0
  for v in arr:
    t = t[1]+v, max(t)
  return max(t)

||

vocal gorge
#

Yup, I'd say that counts as DP still. They essentially cut the DP solution down further by noticing you only care about the values for the last two values of n

#

it's kinda like computing fibonacci numbers:

# 
# naive solution
def fib(n):
    if n<=1: return 1
    return fib(n-1) + fib(n-2)
# DP solution
def fib(n):
    arr = [1,1]
    while len(arr) < n+1:
        arr.append(arr[-1]+arr[-2])
    return arr[-1]
# Notice we only use the last two values each time, so we don't need to store the rest:
def fib(n):
    a,b = 1,1
    for i in range(n-2):
        a,b = b,a+b
    return b
#

(might be off-by-one-iteration in that third one)

#

(In fact, I'd say your task and computing fibonacci values are intrinsically connected, so it's no surprise there are parallels like that)

sleek gust
#

nice one. i like that explanation. thanks! need to read more about dp for sure.

haughty mountain
#

Formulation a dp tends to boil down to coming up with the right parametrization of the problem. A good one in this case: let DP(i, used) be the max value if you're allowed to use the first i items and if used you were allowed to pick the ith item.

#

In this case this ends up being easy to simplify further in the implementation since you only depend on a few other states

young yacht
#

What tree is good for storing Classes?, i have 2 People that have their own characteristics, Hair Color, Eye Color, Height.. Etc etc..

pine sandal
#

any hints on how I can use recursion efficiently to solve the element uniqueness problem?

#

atleast better than O(n^2)

vale tide
# 
    if len(self.maxHeap) > len(self.minHeap) + 1:
      heappush(self.minHeap, -heappop(self.maxHeap))
    elif len(self.maxHeap) < len(self.minHeap):
      heappush(self.maxHeap, -heappop(self.minHeap))

Looking through an algorithm in python, why is there a negative in front of popping from the heap?
The question has to do with finding median of input stream using two heaps

haughty mountain
#

having a minus on the thing they call minHeap is pretty disturbing though

#

because the regular thing in python for doing heap operations heapq maintains a min heap

keen thicket
#

Hello what sorting algorithm is this?

arr = [4,9,3,2,8,1,6,0,5,7]

def sort(array):
	for currentElement in range(0, len(array)-1):
		currentMin = array[currentElement]
		for movingElement in range(currentElement+1, len(array)):
			if arr[movingElement] <currentMin:
				currentMin = array[movingElement]
				swapTemp = array[currentElement]
				array[currentElement] = currentMin
				array[movingElement] = swapTemp
	print(array)
	
sort(arr)
haughty mountain
severe ledge
#

Yoo Fellow Coders, check out the latest solution for Leetcode: 876 "Middle of the Linked List" problem, just solved today,.

Time Complexity: O(N/2)
Space Complexity: O(1)

https://github.com/DestinationFAANG/Destination-FAANG---Java-Solution/blob/main/876 Middle of the Linked List/876 Middle of the Linked List.java

GitHub
Destination-FAANG---Java-Solution/876 Middle of the Linked List.jav...

Contribute to DestinationFAANG/Destination-FAANG---Java-Solution development by creating an account on GitHub.

haughty mountain
#

O(N/2) 🥴

#

that's not how big O notation works

vale tide
fiery cosmos
#

the light blue in the upper left is the original input. the left side are the baselines. the right are the rotations. the 5th rotation overlays the samples as a thin red line. Check it out, its pretty neat!

download.png
woven wyvern
#

i got an exam coming up soon, any one any websites to solve on it? besides hackerrank

spiral raptor
#

Does anyone know of a good resource to learn algorithms and data structures in Python?
Preferably not using OOP

fiery cosmos
#

data structures are objects

#

so, no. none.

bitter nacelle
#

Hey

#

Can someone explain how to find the time complexity of this algo?

hallow flame
#

what is that i on line 10

#

the runtime of this is O(n) I think

shy gull
#

Don't know

misty scaffold
#

why not use google colab or vscode?

quick cliff
lean walrus
# bitter nacelle

Its O(n^2) because str+str creates new string, and you do it in every iteration

hallow flame
#

what?

#

why does creating new strings result in O(n^2)

fiery cosmos
#

so it's like having an extra linear time thing when the else triggers

hallow flame
#

ah

fiery cosmos
#

But this could be made O(n) with a few changes by using lists

oblique gazelle
#

can a binary tree or a ternary tree have null values 😅

#

amongst other data type values

hallow flame
#

wrong reply but whatever

haughty mountain
#

python optimizes that to O(n)

fiery cosmos
# hallow flame ```py string = '' for _ in range(n): string += 'a' ``` so this will result in ...

I think so in theory. Or it can depend on implementation it seems https://stackoverflow.com/questions/37133547/time-complexity-of-string-concatenation-in-python

As of Python 2.4, the CPython implementation avoids creating a new string object when using strA += strB or strA = strA + strB, but this optimisation is both fragile and not portable. Since you use strA = strB + strA (prepending) the optimisation doesn't apply.

#

So the run length encoding algo above is O(n) after all, assuming this optimization lemon_glass

haughty mountain
# bitter nacelle

and wrt this algo, even if we assumed the string concatenations weren't O(n), this is technically not O(n)

fiery cosmos
#

Why not pithink because of the str(ctr)?

haughty mountain
#

yes

#

str(ctr) is O(log(ctr)) long

#

so it's more like O(n log n)

fiery cosmos
haughty mountain
#

it would be nice to have a proper optional type in python

#

actually, I guess it doesn't matter much because python is dynamically typed, I guess my complaint is more that T|None has horrible semantics

#

I want my None coalescing operators lemon_angrysad

fiery cosmos
# 
c = a if a is not None else b

c = a ?? b``` ![lirikHMM](https://cdn.discordapp.com/emojis/929435334872285306.webp?size=128 "lirikHMM")
#

the one thing JS has on python lirikSMUG

keen thicket
#

Is this selection sort?

arr = [5,2,6,1,3]

for i in range(0, len(arr)-1):
	minIndex = i
	for j in range(i+1, len(arr)):
		if arr[j] < arr[minIndex]:
			minIndex = j
	temp = arr[i]
	arr[i] = arr[minIndex]
	arr[minIndex] = temp
	
print(arr)
fiery cosmos
oblique gazelle
fallow agate
#

Hi,
Please correct my understanding regarding the BFS:
Let’s consider below graph.

#

||

#

Started with node “A”

#

||

#

It’s siblings are B,C ----- So, they should be covered next

#

||

#

Next; you should cover all the child’s of B,C ----- So, E,D &G should be covered next

#

||

#

Finally, F

#

traversal logic is right?

fiery cosmos
fallow agate
#

But, most of sources say: below is the BFS pattern, which led to confusion.

fiery cosmos
# fallow agate

Hmm, I find that diagram misleading, at least the "levels". In my mind the levels of a BFS match your first diagram. However in this example a BFS very well could follow the maroon path ABCDGEF (and does assuming you do things in a-z order when there's a choice)

fallow agate
#

||

#

But, in reality it's not the case.

fiery cosmos
#

Right. Starting A then C is just as valid as a BFS as starting A then B

fallow agate
#

Because of this misleading diagram in udemy course, 1/2 day consumed to get clear on this confusion..

haughty mountain
#

unless you for some reason say both A and B are your starting nodes

#

which is something you can do, but it's not typical

keen hearth
glad vale
#

@haughty mountain this works almost for all test but it takes 70s 😳

# 
Queue: 5 , 6 , 4 , 3, 2, 1

Neighbours vertex 7:  5, 6 } this vertices have distance = splen - 1 (4) so we are pushing them to Queue

Neighbours vertex 5:  4, 7 } We are considering only 4 beacuse 7 has greater distance than splen  - 2 (3)
-> Push 4 to Queue

Neighbours vertex 6: 4,7 } We are considering only 4 beacuse 7 has greater distance than splen  - 2 (3)

-> 4 has been pushed to queue already so we are not pushing this vertex
-> The program can't return this vertex and his parent as a result beacuse 4 has more neighbours than 1 ( len(G[4]) - len(Queue) - 1 !=  1 ) (2 != 1)


Neighbours vertex 4: 3,2 } Push both ( splen - 3 == 2 and their distances are 2 as well )


Neighbours vertex 3: 4, 1, 9 }  Push only 1 because 4 and 9 have greater distance than ( splen -4 ) ( 1)

Neighbours vertex 2: 1 , 4} Only 1 has distance equal 1 ( splen - 4 )

-> 1 has been pushed already to queue and 1 has only 1 neighbour left
( len(G[1]) - len(Queue) - 1  == 1 )

RETURN parent[1], 1
#

And here is a code

from collections import deque
import queue


def longer(G, s, t):
    V = len(G)
    que = deque()
    processed = []
    que.append(s)
    parents = [None for _ in range(V)]
    distance = [0 for _ in range(V)]

    pQue = queue.PriorityQueue()

    # BFS
    while len(que) > 0:
        v = que.popleft()
        processed.append(v)

        for neighbour in G[v]:
            if neighbour not in processed:
                que.append(neighbour)
                parents[neighbour] = v
                distance[neighbour] = distance[v] + 1

                processed.append(neighbour)

    spLen = distance[t]
    sameVertexQue = deque()

    for nei in G[t]:
        if distance[nei] == spLen - 1:
            sameVertexQue.append(nei)

    if len(sameVertexQue) == 1:
        return t, sameVertexQue.popleft()

    while spLen > 1:
        el = sameVertexQue.popleft()
        spLen = distance[el]

        for nei in G[el]:
            if distance[nei] > spLen: continue
            print(nei, G[nei])
            if nei in sameVertexQue and len(G[nei]) - len(sameVertexQue) - 1 == 1:
                return parents[nei], nei
            else:
                if distance[nei] == spLen - 1 and nei not in sameVertexQue:
                    sameVertexQue.append(nei)

    return None


G = [[1, 5, 7],
     [0, 2, 4],
     [1, 3],
     [2, 4],
     [1, 3, 5],
     [0, 4, 6],
     [5, 7, 8],
     [0, 6, 8],
     [6, 7]
     ]
s = 0
t = 2


G = [
    [1, 8],
    [0, 2, 3],
    [1, 3, 4],
    [1, 4, 9],
    [2, 3, 5, 6],
    [4, 7],
    [4, 7],
    [5, 6],
    [0, 9],
    [3, 8]
]
s = 0
t = 7
print(longer(G, s, t))
haughty mountain
#

make processed a set

glad vale
#

Unfortunately i can't use sets

#

Only list, prority queue, deque

haughty mountain
#

why?

glad vale
#

these are the requirements of the task to use only those structures

haughty mountain
#

you could use a list with booleans, one per node

#

and then do

if processed[i]
```and
```py
processed[i] = True
glad vale
#

That's makes sense

#

But conceptually it's good?

#

Or am i doing something unnecessary

haughty mountain
#

I haven't read it closely, but the BFS part looks like expected

glad vale
#

But i still have two tests with wrong answer so something is wrong with this approach

#

It's happening when the expected result is None

#

Can you see where the problem is in here?

young yacht
#

What is the best data structure for storing classes, for example, a class that represents a person, and has their name, hair color, eye color, height, age.. etc...

#

^^ If any1 could tell me it would help so much

dry crow
#

i should probably lurk here more often

shut breach
young yacht
#

@shut breach a bunch of classes, i also want a way to search for stuff in them classes

shut breach
#

do you know the difference between a class and instances of a class?

young yacht
#

yes

shut breach
#

so what stuff are you searching for?

mystic pollen
#

Good evening, could someone help me with refactoring, I have the book to consult. But I wish I could find more content on the internet. The method I'm looking for is Replace Inline Code with Function Call, but I just can't find any repository, did you change the name? I'm usually finding method inline, but I don't know if it's correct. In case someone knows a repository to be able to consult it, it helps too

haughty mountain
# glad vale Can you see where the problem is in here?

(was on a flight for the last 9ish hours)
so what I expected code-wise for the task is something like

path = shortest_path()
for i in range(len(path)):
  p = shortest_path_banning_edge(path[i], path[i+1])
  if len(p) > len(path):
    return "found the edge!"
return "no such edge!"
cinder cedar
#

Anyone can explain what a linked list in a very simple easy way to understand for a new person see this for the first time?🙂

glad vale
glad vale
#

My code does it in 0.06/ 0.08

#

If you want i can send you how the code looks like now

runic tinsel
glad vale
# cinder cedar Anyone can explain what a linked list in a very simple easy way to understand f...

In this video you have everything that you should know about linked lists as If i remember correctly https://www.youtube.com/watch?v=WwfhLC16bis

YouTube
CS Dojo
Introduction to Linked Lists (Data Structures & Algorithms #5)

Learn the basics of linked lists. Java & Python sample code below.

Check out Brilliant.org (https://brilliant.org/CSDojo/), a website for learning math and computer science concepts through solving problems. First 200 subscribers will get 20% off through the link above.
Special thanks to Brilliant for sponsoring this video.

Find sample code in...

▶ Play video
runic tinsel
#

one slot for anything you want, the value
the other for some other object of this type

cinder cedar
#

Actually i watched this and understand everything

#

Thx anyway🌹

runic tinsel
#

the important thing is linked list is not a type, it's a pattern, it just happens

#

only nodes are real

naive saddle
#

How would I approach this

#

I want to write it as an equation but i don't know how

haughty mountain
#

and does your code even work for all cases atm?

fiery cosmos
# naive saddle I want to write it as an equation but i don't know how

So i keeps doubling until it is greater than n. Say the number of iterations, aka the number of time i doubles is D. That means roughly 2^D = n. Rearrange that and you get D = log(n) (base 2 or e doesn't matter since those are a constant multiple apart). So the number of iterations is log(n).

#

(Strictly the 2^D = n doesn't make sense when both n and D are integers but 2^D can't go beyond 2*n, so still within a constant multiple.)

fallow agate
#

Hi,
Below is the BFS & DFS program & I am understanding it when analyzed individually. But, when I compare two at a time, seeing only the change of queue to stack is turning BFS to DFS, which is not clear. I mean, not getting big picture with confidence….

#

||

#

Can anyone pls tell the crux because of which BFS is changing to DFS, by just changing queue to stack….

# 
from collections import deque
class Graph:
    
    def __init__(self,dictionary):
        self.custom_dict = dictionary
 
    def bfs(self,vertex):
        visited_vertices = [vertex]
        queue_vertices = [vertex]
        while queue_vertices:
            dequed_vertex = queue_vertices.pop(0)
            print(dequed_vertex)
            for adj_vertex in self.custom_dict[dequed_vertex]:
                if adj_vertex not in visited_vertices:
                    visited_vertices.append(adj_vertex)
                    queue_vertices.append(adj_vertex)

    def dfs(self,vertex):
        visited_vertices = [vertex]
        stack_vertices = [vertex]
        while stack_vertices:
           popped_vertex = stack_vertices.pop()
           print(popped_vertex)
           for adj_vertex in self.custom_dict[popped_vertex]:
               if adj_vertex not in visited_vertices:
                   visited_vertices.append(adj_vertex)
                   stack_vertices.append(adj_vertex)
    
custom_dict = {
    "a" : ["b","c"],
    "b" : ["a","d","e"],
    "c" : ["a","e"],
    "d" : ["b","e","f"],
    "e" : ["c","d","f"],
    "f" : ["d","e"]
}

graph_dict = Graph(custom_dict)
graph_dict.dfs("a")
tribal surge
tribal surge
#

output=[]
for i in range(int(input(""))):
a,b,c,d=map(int,input("").split(" "))
if (a+b+c)<=d:
output.append(1)
elif (d*2)>=(a+b+c)>=d:
output.append(2)
else:
output.append(3)
for i in output:
print(i)

tribal surge
fiery cosmos
# fallow agate Hi, Below is the BFS & DFS program & I am understanding it when analyzed individ...

With the stack, new unvisited nodes you come across are put on the top of the stack, so they will be the next ones popped. So it is always delving into the deepest part of the graph seen so far (hence dfs). With the queue, new unvisited nodes are put at then end of the queue, so it won't pop them until all the nodes already noticed are run through, so the fringe of the next to-visit nodes is always the breadth of the graph at the current state in the search (hence bfs).

#

Hope that makes sense. This is how I understand it hachuDank

fallow agate
#

Let’s consider this graph

#

BFS ----- queue = [B,C] ----- Popped out elements are B & C
Note: I am not mentioned A here, because when we start with A, we will insert in into visited vertices directly, so, let’s not worry about it for understanding purpose.

#

DFS ----- stack

#

During 1st loop:
C
B
||
C pops out

#

During 2nd loop, we are inserting adjacent vertices of C into stack, so:
E
C
B
||
E pops out

#

Because of stack; we can clearly see that adjacent vertices are not popping out, but the distance one’s.

fiery cosmos
#

So with dfs, stating at A (and appending things in A-Z order when there's a choice), the state of the stack changes like |A # start with A |BC # pop A, push B C |BE # pop C, push E |BDF # pop E, push D F |BD # pop F |B # pop D | # pop B leaving empty stack where | represents the base of the stack and the rightmost letter is the top

#

though you're right, the search travels far away from the A start pretty quickly (deeply you might say - depth first search)

olive sage
#

so cool

trail warren
#

hey guys

haughty mountain
glad vale
glad vale
#

How to recognise what type of problem it is? Either DP or greedy algorithm? I know that DP is based on sub problems that overlaps and are connected in some sense each other. But exists there any way to look at the problem and know for sure it's greedy or it's 100% DP problem?

tame whale
#

ik this is stupid, but given a regular adjacency list of edges, how can i simply find the minimum amount of bridges needed to get from x to y

#

like no minimum cost or anything

#

just a path

fiery cosmos
fiery cosmos
#

Who can help me

IMG_9057.png
#

Anyone?

lament totem
fiery cosmos
#

Idk how to phrase my question

#

Like I just get it wrong

#

It’s not a coding question where I can say got it wrong here

#

Idk what I’m doing wrong

#

Anyone? I have no idea I’ve watched khan academy videos tried mostly everything

solid wharf
#

Is 2^(n/4) in O(2^n) or is it its "own class"?

fiery cosmos
# solid wharf Is 2^(n/4) in O(2^n) or is it its "own class"?

Technically yes, it is O(2^n) but maybe not in the way you mean. 2^(n/4) is the same as (2^(1/4))^n or about 1.19^n. but 2^n grows faster than 1.19^n so 1.19^n != θ(2^n), where θ (big theta) means bounded on both sides (above and below). So in a θ sense they are different classes.

#

But 1.19^n is O(2^n) because big O is just an upper bound. So in the same way n is O(2^n)

solid wharf
fiery cosmos
keen hearth
# fiery cosmos Anyone? I have no idea I’ve watched khan academy videos tried mostly everything

You're given that T1 and T2 are conditionally independent given L. That means, if you know whether or not the person has the disease, then the results of the two tests are independent of each other. (If you don't know whether or not the person has the disease, then the two tests are not independent of each other, as they have a dependence through L.) A more formal way of putting this is: P(T1, T2 | L) = P(T1 | L) * P(T2 | L) and P(T1, T2 | ~L) = P(T1 | ~L) * P(T2 | ~L) You want to find P(L | T1, T2). You're given P(L) and, from the equations above, P(T1, T1 | L) and P(T1, T2 | ~L). Try applying Bayes' rule.

#

Hint: ||Treat the joint event (T1, T2) as if it were a single event A. Then the goal is to find P(L | A), given P(L), P(A | L), and P(A | ~L)||

fiery cosmos
#

Hope everyone’s had a good weekend. I was wondering if anyone has recommendations on resources for algorithms / data structures for general interview prep.

Reading a book rn / trying to mix in leetcode exercises here and there but I wanted to see if anyone had a website / YouTube channel / book / etc that they found helpful. Would be greatly appreciated.

Thanks