algos-and-data-structs

[calm spade]

its not necassery it can touch a path tile

in my case atleast

[wispy hare]

I'll be back in 30min and I'll explain have to go sorry

[subtle hearth]

Oh ok, so the rows where there are 1's stacked is ok?

[calm spade]

ok waitin for ya ty

[calm spade]

ye

[subtle hearth]

ahh ok!

[calm spade]

yeah but in my case where i want to later convert it to emojis on discord having all tiles being defined as one value is easier

how did he manage to make it that fast... wow

[subtle hearth]

He has wizarded up code for me before, it's amazing

[calm spade]

so thats how this channel works? everyone sees what the person is trying to make and races to make it before everyone else? 🤣

[subtle hearth]

stuff i've never seen

[calm spade]

damn

[subtle hearth]

yeah xD It's good practice

[calm spade]

yup

[lime geyser]

Alright how do I go from starting out to understanding this stuff?

[wispy hare]

hey m back

[calm spade]

Hi

Soooo... how ya did it?

[wispy hare]

this type of problems (starting in a particular cell then traversing the grid by following some rules) is usually solved by using backtracking or BFS

[calm spade]

ok

[wispy hare]

for example we have a grid where each cell has a cost, and we want to find the cheapest path to go from top-left cell to bottom-right cell

[calm spade]

Aha

[wispy hare]

in that case we can use backtracking to traverse the possible paths and take the cheapest one

but in your problem

[calm spade]

It has to be random

Right?

[wispy hare]

we are taking only one direction

so we don't need to go back to the previous cell and take another path

[calm spade]

Owh ok

[wispy hare]

which means that we can do it without backtracking/BFS

[calm spade]

Aha

[wispy hare]

we want to generate a path of length k, we can do it recursively, but we can just use a for loop that gonna be repeated k times

it's what I did

[calm spade]

so k is how many tiles i wanr

Want*

Right?

[wispy hare]

and at each iteration, I started by checking what directions I take

yes

[calm spade]

Ok

How do i check the directions?

[wispy hare]

now that I've put them in an array, let's say ['top', 'left', 'right'] for example

I generate a random direction among them, and I take it

[calm spade]

Ok ye thats my idea

But i dont know how to implement it

[wispy hare]

a direction is considered as valid if the next cell of that direction is not out of grid and is not visited yet

note that I assumed that we can't visit the same cell twice

[calm spade]

Ye ofc

[wispy hare]

so I checked the four directions and appended the ones that are valid

[calm spade]

so the direction has to be 0 (not visited) and can't be more than the len(layput[row]) which is offset

Layput*

Layout*

[wispy hare]

and not less than 0

[calm spade]

Ye

[wispy hare]

then when I randomly generate a valid direction, I take it by updating x or y depending on the direction, and I put '1' in it

[calm spade]

Aha

[wispy hare]

Full code:
||```import random
import numpy as np

def path(n, m, k):
grid = [['0']*m for i in range(n)]
grid[0][1] = '2'
x, y = 0, 1
for i in range(k):
directions = []
if x-1 >= 0 and grid[x-1][y] == '0':
directions.append('top')
if x+1 < n and grid[x+1][y] == '0':
directions.append('bottom')
if y-1 >= 0 and grid[x][y-1] == '0':
directions.append('left')
if y+1 < m and grid[x][y+1] == '0':
directions.append('right')
print(directions)
next_direction = directions[random.randrange(0, len(directions))]
if next_direction == 'top':
x -= 1
elif next_direction == 'bottom':
x += 1
elif next_direction == 'left':
y -= 1
elif next_direction == 'right':
y += 1
grid[x][y] = '1'
return grid

print(np.array(path(5, 10, 20)))```||

[calm spade]

Ok this makes sense now but i am still kinda confused (code-wise)

Ok i'll try to implement it myself without looking at this code

[wispy hare]

x-1: previous row
x+1: next row
y-1: previous column
y+1: next column

[calm spade]

Mhm

Thanks so much

[lime geyser]

What is the best way to understand these topics

[calm spade]

Learn python?

Be good at math

Practice

¯\_(ツ)_/¯

[lime geyser]

Data struct and algo

[wispy hare]

solve coding problems

[lime geyser]

Do they start out easy

Cause it’s like normal python is one thing

This is another level

[wispy hare]

I'm actually posting a series on data structures and algorithms in Python on: https://www.instagram.com/inside.code/
I don't know if I'm allowed to put self links, tell me if I'm not

[calm spade]

you're algorithm doesn't work every time btw.
sometimes it raises this error

    raise ValueError("empty range for randrange() (%d, %d, %d)" % (istart, istop, width))
ValueError: empty range for randrange() (0, 0, 0)

i'll try to fix it

i think it's blocking itself by like going throw circles

squares in this case

😆

[wispy hare]

I think that's the case where there is no possible direction

it depends on how you want to handle it

[calm spade]

Yeah

I'll make it so that doesn't happen ig since i am specifying how many tiles i need i have to get all of them

[wispy hare]

oh okay, then you'll need to backtrack to a point that has other directions

[calm spade]

Ahaa

[wispy hare]

did you try?

[calm spade]

Fixing a different problem now

For some reason my convert function wont work

converting the layout to discord emojis

Like that

[wispy hare]

wait are you sure that this is a valid path?

[calm spade]

I wrote this manually

As an example

😂

[wispy hare]

after 4th tile it's going from right and bottom xd

[calm spade]

Ye

[calm spade]

That can be done tho...

[wispy hare]

why

[calm spade]

Looks better ig lol

This damn error wont fix wth

[wispy hare]

wait you agree that your manual example is not valid right?

[calm spade]

What manual example?

I dont get what you mean

[wispy hare]

this one

[calm spade]

Ye its not valid

[wispy hare]

ye

[calm spade]

I wrote it myself

[wispy hare]

do you know how to implement a backtracking algorithm?

[calm spade]

no

it sounds and looks complicated

i looked thru some docs n stuff

[wispy hare]

okay basically backtracking is to try all possibilities while backtracking as soon as you find out that the actual possibility is not valid

backtracking means to go back to a previous point

[calm spade]

Where there is no path anymore

And reverse the last move

And change it

[wispy hare]

in our case, a path represents a possibility, and we backtrack when we find out that the actual cell is out of grid or already visited

[calm spade]

Mhm

[wispy hare]

yes we go back to the cell that still has possible directions to go from

[calm spade]

I know how it works but i don't know how to implement it

[wispy hare]

do you know recursion?

[calm spade]

no

😅

[wispy hare]

that's gonna be a lil bit hard then xd

[calm spade]

So recrusion is calling a function inside itself?

[wispy hare]

yes

[calm spade]

def fun():
    fun()
fun()

How does this work i thought its impossible 😂

[wispy hare]

it works because the same function but with different values for parameters can behave differently

[calm spade]

async def createD():
    layout = await createPath(5,8,15)
    off = "⬛ "
    path = "🟫 "
    player = "🤠 "
    d = ""
    for row in range(0,len(layout)):
        if row == 0:
            pass
        else:
            d += "\n"
        for col in range(0,len(layout[row])):
            if layout[row][col] == 0:
                d += off
            elif layout[row][col] == 2:
                d += player
            elif layout[row][col] == 1:
                d += path
            else:
                pass
    return (layout, dungeon)
``` why is thing returning `d` empty?

[calm spade]

Does it work if its an async function?

[wispy hare]

I'm not familiar with async/await :c

but you have to know that when a function calls itself, it waits for that function call to end, then it continues its work

[odd axle]

Hello! What is a good way to read fast millions of strings? I have a file with nearly 1.000.000.000 lines like this 123456789|word, and I am using this to get a line: ```py
from functools import partial
def readFile():
read= partial(file.read, 104857600)
for text in iter(read, ''):
if "123456789" in text:
textDiv = text.split("\n")
for x in textDiv:
if "123456789"in x:
print(x)
return
readFile()

[fiery cosmos]

read data in chunks

[odd axle]

That is what I did, right? @fiery cosmos I am not reading 100gb to memory

[fiery cosmos]

idk if normal way of reading data is efficient in python

Use special library like pandas to speed up the process ig

[odd axle]

okay, I am going to try it. Thanks

[placid lantern]

So I have a dictionary full of more dictionary's (I dont know what the right term for this is). Say for example {'0' = {'a':'2', 'b':'3'}}, {'1' = {'a':'4', 'b':'5'}}.

I have a value for 'b' and I want to get 'a' from the same record in the dictionary. how would I do this?

[wispy hare]

  if d[key]['b'] == searched_value:
    print(d[key]['a'])```

assuming that all your inner dicts have both 'a' and 'b' as keys

and, I don't know if it's a coincidence, but I noticed that your keys in the outer dict are 0, 1, ..., if it continues like that, I think that it's better to use a list

[placid lantern]

well thats just as my quick example but there are really much more keys and each is associated with a diffrent string

[wispy hare]

oh okay

[placid lantern]

I am still pretty new to this and I dont understand this for loop... whatever I did is now crashing it...

The thing is Im doing this in a discord bot and it doesnt tell me the error

[wispy hare]

the items of a dictionary are pairs of (key, value)

so this loop is traversing all the items of our dictionary (the outer one, the one that contains dictionaries inside it)

wait wait wait

my code is wrong

I got confused because your description doesn't match your example

let me re explain

it's more accurate to say a dictionary where the value of a key is a dictionary

so the right code would be this one:

  if value['b'] == searched:
    print(value['a'])```

what we're doing here is that we're traversing the pairs of key/value of the outer dictionary

and in this dictionary, the value of the pair is also a dictionary, the one that has 'a' and 'b' inside it

[placid lantern]

this makes sense to me...

but its still crashing

[wispy hare]

what's the error?

[placid lantern]

you see its a discord.py bot and it doesnt show the errors

which is annoying

[wispy hare]

does it even have a console?

[placid lantern]

I put

    for key, value in dictionary.items():
        if value['owner'] == username:
            print(value['players'])

[placid lantern]

it does

[placid lantern]

here username is a string

[wispy hare]

then use try/except and print the exception

[placid lantern]

'list' object has no attribute 'items'

[wispy hare]

then it's a list not a dictionary

[placid lantern]

I thought this creates a dictionary from a JSON: dictionary = json.loads(result)

[wispy hare]

print the whole thing and see

[placid lantern]

what would a list look like in comparison to a dictionary?

[wispy hare]

a list in Python is an array

[placid lantern]

ah

It looks pretty much the same as the origonal json

[wispy hare]

can you show me what gets printed?

[placid lantern]

this is one section of it:

{'144': {'ip': '71.29.169.199', 'port': '34617', 'players': '1', 'maxplayers': '10', 'private': False, 'map': '/levels/west_coast_usa/info.json', 'pps': '-', 'sname': 'The Boys Server', 'time': 1608479054240, 'version': '1.13', 'location': 'US', 'playerslist': 'Flaboom;', 'cversion': '1.70', 'official': 0, 'owner': 'Flaboom#3416', 'sdesc': 'BeamMP Default Description', 'modlist': 'Resources/Client/AnyLevel.zip;Resources/Client/MidsizeDieselV8.zip;Resources/Client/Turbo_Everything_rk.zip;Resources/Client/ultrawide_aftermarket_transmission_package_mods.zip;', 'modstotal': '4', 'modstotalsize': '7503094'}}]

[wispy hare]

from where comes the last bracket

the square bracket at the end?

[placid lantern]

a list ig

but

Im so confused

[wispy hare]

isn't it a list of one element?

[placid lantern]

wait

what do you mean

it counts all the way up to '144'

if thats what your asking but Im super confused

[wispy hare]

I asked if it wasn't a list of one element, like a list that contains one element which is the whole thing

[placid lantern]

I think yea

so based off the fact that we now know its a list, I changed d.items() to d[0].items() and its no longer giving me an error, but its not printing anything for value['players']

[wispy hare]

I think that it's because not all your values have the key 'owner'

you first need to check that value is a dict, and that it has the key 'owner' before checking if it's equal to username

  if isinstance(value, dict) and 'owner' in value and value['owner'] == username:
    print(value['players'])```

[placid lantern]

It still doesnt print anything...

[wispy hare]

you're using dictionary instead of d right?

[placid lantern]

yes

[wispy hare]

print this and tell me what it printed:
print([key for key, value in dictionary[0].items if (isinstance(value, dict) and 'owner' in value)])

btw

instead of always adding that [0], just add [0] where you loaded with json

[wispy hare]

write dictionary = json.loads(result)[0]

[placid lantern]

printed ['0']

[wispy hare]

so you have only one dictionary that has 'owner' in its keys

[placid lantern]

what

[placid lantern]

even this has an owner

here is where the json comes from: https://beammp.com/servers-info

I problably should have started with that

[wispy hare]

okay I'll try to work on it and see

[placid lantern]

Thanks

[wispy hare]

I figured it out, the initial list doesn't have only one element, it has 147

[placid lantern]

I just noticed that too, but the number of elements is can change.

[placid lantern]

do you know what the best way to iterate through these elements is?

[wispy hare]

    for key, value in d.items():
        if isinstance(value, dict) and 'owner' in value and value['owner'] == 'Titch#1689':
            print(value['players'])```

this worked for me

remove the [0]

[placid lantern]

already did

[wispy hare]

titch is an example replace it by username

[placid lantern]

data is your dictionary right?

[wispy hare]

no the list

that is returned by json.loads

[placid lantern]

because I did:

        for d in dictionary:
            for key, value in d.items():
                if isinstance(value, dict) and 'owner' in value and value['owner'] == username:
                    print(value['players'])

where username = perfectsquare150#8584 and it didnt print anything

[placid lantern]

yea sorry thats what I meant

its the same as my dictionary variable

[wispy hare]

it worked for me with perfectsquare

[placid lantern]

I am doing something very wrong then

this is my whole thing...

    req = urllib.request.Request('https://beammp.com/servers-info')
    req.add_header('User-Agent', 'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/87.0.4280.88 Safari/537.36')
    data = urllib.request.urlopen(req)
    result = data.read()
    result = result.decode('utf-8')

    dictionary = json.loads(result)

    try:
        for d in dictionary:
            for key, value in d.items():
                if isinstance(value, dict) and 'owner' in value and value['owner'] == username:
                    print(value['players'])

    except Exception as e:
        print(f"ERROR: {e}")

Is it to do with the way I created the list?

[wispy hare]

print the length of dictionary and tell me what did you get

[placid lantern]

138

thats not right

[wispy hare]

got 146, weird xd

[placid lantern]

uhhhhhhhhhhh

[wispy hare]

btw I copied the whole page and saved the text as a json file they I opened it

didn't use requests

[placid lantern]

oh

Its allways updating and I need the most recent when someone runs the command

[placid lantern]

wait so is your data just the raw json?

[wispy hare]

I guess?

[placid lantern]

Thanks for the help, @wispy hare. Apparently that last problem was just me being dumb and not casting username as a string.

[wispy hare]

lmaooo okay okay

[somber kiln]

How do I find the most common prefixes in a big list of strings?

[wispy hare]

what do you mean by "most common"?

[somber kiln]

I don't know how long a prefix should be or how numerous (though I can set a minimum threshold)

Like, if I have ["abc", "abde", "cde", "cfg", "dfg"] it would give me ["ab", "c"]

[wispy hare]

I know that common means present in them all, but I didn't understand most common

[somber kiln]

Well, not all of them, but a lot of them

[wispy hare]

how much is a lot?

[somber kiln]

the most

There is no prefix in those strings that appear in more strings than "ab" and "c"

[wispy hare]

aah okay

[somber kiln]

I can set a minimum threshold like 30% if that helps

[wispy hare]

tries can be useful here I think

I think that you should use a trie

[somber kiln]

A trie works but will need to hold all strings

I suppose it is succinct enough to work

[placid lantern]

I have one more question that I think I should ask in this channel because I dont know which other channel would be the right one...

I want to remove any ^ in a string and the character after it. how would I go about doing this?

[wispy hare]

''.join([s[i] for i in range(len(s)) if s[i] != '^' and (i == 0 or s[i-1] != '^')])

you can also use regex if you want

[placid lantern]

Thank you!

[wispy hare]

you're welcome

tell me if you need explanation

[placid lantern]

I think I do

[wispy hare]

do you know about list comprehension?

[placid lantern]

its like when you take something like a sting and turn all the letters into elements of a list right

[wispy hare]

nope not that, wait lemme just write it with a loop and you'll understand what I did:

for i in range(len(s)):
  if s[i] != '^' and (i == 0 or s[i-1] != '^'):
    new_s.append(s[i])
new_s = ''.join(new_s)```

[placid lantern]

so your basically itertating through a string and if its not a ^ and the index before it is not, then you add the letter back into a list, then after its done you join the list into a string?

[wispy hare]

yess

but it can be done with list comprehension

it's also more Pythonic

[placid lantern]

ok, thanks again!

[wispy hare]

you're welcome!

[subtle orbit]

hello! is anyone working with data science/analysis with Python? I'm just starting and I don't know if I did this question right. some help would be appreciated. Thank you:)

[wraith valve]

lmao wrong channel

but anyways of all the 3 options

c looks the most right

if u were to guess

[oblique panther]

That person only has three messages in the server--"lmao wrong channel" isn't the way we want to approach correcting people.

[oblique panther]

this would be a question for #data-science-and-ml. The third answer is the correct one, though.

[lyric bramble]

temp_str= "test string"


temp_dict = {}

for i in range(len(temp_str)):
    if temp_str[i] not in temp_dict:
        temp_dict[temp_str[i]] = 1
    else :
        temp_dict[temp_str[i]] += 1

for i,j in temp_dict.items():
    if j > 1 :
        print(f"{i}, count = {j}")
``` What is time comlexity of this code ?

[agile sundial]

what do you think

[lyric bramble]

o(n)

[agile sundial]

why

[lyric bramble]

first block of for loop is O(n) then appending in dict is constant time i suppose

again second block of for loop looks to be constant time for me...not sure tho

could u help me plz

[lyric bramble]

bruhh

[agile sundial]

uh

yeah it's O(n)

[lyric bramble]

so was my explaination right

also this line

[agile sundial]

yes, the if statement in the loop runs in constant time

[lyric bramble]

temp_dict[temp_str[i]] = 1 ...this line is O(n) isnt it since i am adding an item into my dict

[lyric bramble]

thanks for the help

[agile sundial]

no, it's O(1)

[wispy hare]

yes it's O(n), and also, what you're doing here can be directly done with a counter

temp_str = "test string"
temp_dict = Counter(temp_str)```
now counter is a dictionary that contains each character and the number of its occurrences

[oblique panther]

@lyric bramble you also don't want to iterate over range len for this problem

!range

[halcyon plank]

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

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

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

for item in my_list:
    do_something(item)

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

[lyric bramble]

ok thanks for the help guys will note them

[wispy hare]

you're welcome

[sly arrow]

I just listened to the first introductory lecture on Day 9 of Udemy 100 days of code, and my question is around the action of the python dictionary type:

If I have an existing dictionary with existing entries that look like -- leaving off the quotes on purpose:

pets = {
Dog: A friendly furry creature
Cat: An aloof furry creature
Python: One type of snake
}
and I want to ADD another entry, i programmatically write:

pets[Hamster] = Round Furry ball of fluff

which adds the key of Hamster, and sets it to have a value of "Round ..."

However, if I want to update the key of Cat: with the value "Warm furry vibrator" I use:

   pets[Cat] = "Warm furry vibrator"

exactly the same syntax!

Why is adding an entry to the dictionary NOT differentiated from an update?
asks curious David -- hoping I am in the right channel for this question.

[ivory yacht]

Well, since you access entries by keys, it's not possible to have duplicate keys. So assigning to the key overwrites the previous value, the same way assigning to a variable or list index or whatever does. There's not really a reason to make the two operations different, it'd just mean two almost identical syntaxes.

[sly arrow]

I was thinking that I as a programmer would want to be explicit for either operation. And then get an error if I tried to do the wrong thing -- such as:

pets[Hamster] += Round Furry ball of fluff <<< indicates that I INTEND to add an entry and fails if entry exists,

And then this syntax for an INTENDed update:

  pets[Cat] = "Warm furry vibrator"        <<< which fails if the key does not exist

surprised that for as much as python wants me to explicitly tell it what to do, and along comes this fuzzy syntax that "lets me get away with both"

[lean dome]

You're viewing d[k] = v as being either adding or updating a key, and saying you would prefer those 2 operations to have different syntax. But that's not really what it does: it sets a key to a value. In both cases the state of the dictionary after d[k] = v is now that, if you get the item from the dict d with key k, you'll find value v.

You're not wrong, exactly, but you're looking at that operation from a different angle than the Python language looks at it. From the Python language's perspective, it is neither an "add" nor am "update", it is a "set"

It's not ridiculous to imagine that a language could exist where instead of a dictionary supporting one set operation, it supported separate insert and update operations, where it is an error to insert a key that already exists or update a key that doesn't exist. From the language designers' point of view, the question they would be asking themselves is if that decision would make it easier or harder to write correct code. And the designers of different languages could conceivably come to different conclusions than the designers of Python came to.

And, note in particular that your suggested syntax of py pets["Hamster"] += "Round furry ball of fluff" is already valid syntax for doing something different than what you propose: it looks up the value stored at pets["Hamster"] and adds to it. py d[k] += v is equivalent to ```py
d[k] = d[k] + v

[sly arrow]

Would this last operation fail if d[k] did not exist?

[lean dome]

Yes

Because looking up the current value of the key is a part of it, and will fail if there is no current value to be found - in that case we don't know what to add the value v to.

[sly arrow]

Thanks for your thoughts and typing. Good night....

[fiery cosmos]

dag = input('dag?')
print(dag)
maand = [['Jan', 0], ['Feb', 3], ['Maa', 3], ['Apr', 6], ['Mei', 1], ['Jun', 4], ['Jul', 6], ['Aug', 2], ['Sep', 5], ['Okt', 0], ['Nov', 3], ['Dec', 5]]
i_maand = input("Type het overeenkomende getal met jouw maand\nJan=0\nFeb=1\nMaa=2\nApr=3\nMei=4\nJun=5\nJul=6\nAug=7\nSep=8\nOkt=9\nNov=10\nDec=11")
o_maand = [maand[[1][i]] for i in (i_maand)]
print(o_maand)

can you guys help me out here? Im trying to set o_maand to the value in maand

[heady pivot]

What you want to do exactly ?

[heady pivot]

Anything do inside the input() is the prompt message for the console.

[fiery cosmos]

I solved the problem already using a different way to code this. Thanks for the help though! How do I close this discussion?

oh mb Im new here. Posted it in the wrong channel

[kindred sinew]

Hey Guys!

[fiery cosmos]

what does yield do?

I didn t understand it pretty good

it s like a return for loops?

[fiery cosmos]

it is return but it acts only when it is called

so much like you only answer when you are asked

so it only returns some value only when called

def yield_example():
  a = [i * 10 for i in range(100)]
  for el in a:
    yield el

this will return values one by one

and when you call yield_example() it will step once and halts its execution

[agile sundial]

lol, that's a pretty bad example of yield, since you're still holding all the values in memory

[fiery cosmos]

ye much useful case is when you have some infinite stream of numbers

[balmy siren]

try a generator instead of list comprehension

[stoic prawn]

anyone have a guide to understanding big o notation and code efficiency

[kindred sinew]

I would say, go with https://www.geeksforgeeks.org/

Is it confusing to practice DS-Algo fundamentals using Python, rather than C, as I have no prior experience with C/C++.

[agile sundial]

huh?

i can't parse that sentence, but you can implement dsa in any language

[kindred sinew]

Yeah, that is true

[wispy hare]

nope you can use the list

the list is implemented as a dynamic array

[kindred sinew]

Yea, right

Actually, I have started my coding interview preparation for product-based companies, hence I was curious.

Anyways thanks

[wispy hare]

you can check this series of ig posts, check this one and the ones after it: https://www.instagram.com/p/CIdN2_NAxn4/

[lean dome]

The biggest downside to learning data structures in Python is that you'll feel like you're reinventing the wheel a lot. You'll keep building your own, worse versions of things that exist in the standard library. That's not a bad thing, though. It's teaching you how the standard library works.

Just remember that what you're learning is not how to build these days structures in Python, because for the most part someone else has already made a high quality implementation you can reuse. Instead, you're learning how these days structures work internally, which allows you to reason about how they'll behave and perform in any language.

[wispy hare]

reinventing the wheel is fine when you know that it's just to understand how does it work imo

[lean dome]

Yeah, exactly. To use an analogy, the purpose of the exercise isn't to build your radio, because you can buy excellent radios already made that do everything you're likely to want yours to do. The purpose of building your own radio is to learn how radios work, so that you can troubleshoot yours if it ever breaks, or understand what conditions will make it work worse, or understand why it can only pick up certain bands, etc.

As long as you understand that there's value in learning how these things work even though you'll throw away your implementations, Python is a perfectly fine language for it

[wispy hare]

exactly

don't focus on implementation, focus on knowing the time complexity of main operations and when to use a data structure instead of another

[lean dome]

Yeah. Learning the implementation is mostly useful because it helps you understand why the time complexity is what it is.

[eager hamlet]

"""
https://cses.fi/problemset/task/1662
5
3 1 2 7 4 should output 1
"""
divisor = int(input())
remainders_encountered = {}
total = 0
sum_so_far = 0
for i in input().split():
    sum_so_far += int(i)
    remainder = sum_so_far % divisor
    total += remainders_encountered.get(remainder, 0)
    if remainder not in remainders_encountered:
        remainders_encountered[remainder] = 0
    remainders_encountered[remainder] += 1
total += remainders_encountered.get(sum_so_far % divisor, 0)
print(total)
``` (problem in code) why doesn't this work lol

ping 2 reply thx

if anything's not cllear about the code i can explain

[floral shell]

I need major help

This is my code

ideas = ""
num = 1
name = input("Employee first and last name:")
a = ""
b = ""
c = ""
slots = [a, b, c]
while num <= 3:
    idea = input(f"Idea No. {num}:")
    num = num + 1
    if num == 1:
        a = idea
    elif num == 2:
        b = idea
    elif num == 3: 
        c = idea
    if idea == "stop":
        print(f"{name} is still thinking.")
        break
print(f"List of collected ideas. Author: {name}.")
print(f"1. {a}\n2. {b}\n3. {c}\n")

but this is what it outputs

it misses the 1.

can someone help me?

wait, nvm, I figured it out

[stoic prawn]

Cause you do num = num + 1 before the if statement checks if its 1, so you start with 2

Put it at the bottom of the second if statement, and there's an increment operator, so you can do num += 1

[kindred sinew]

Yes, I feel the same.

[kindred sinew]

Sure!

[fiery cosmos]

is this the place for square root code

Im writing one for computer science and im lost

[hollow saddle]

@floral shell You initialize ur num to 1 and when u get into the while loop u add 1 to it before getting to the conditions instuctions

I suggest that u put that after the conditions

!eideas = "" num = 1 name = input("Employee first and last name:") a = "" b = "" c = "" slots = [a, b, c] while num <= 3: idea = input(f"Idea No. {num}:") if num == 1: a = idea elif num == 2: b = idea elif num == 3: c = idea num = num + 1 if idea == "stop": print(f"{name} is still thinking.") break print(f"List of collected ideas. Author: {name}.") print(f"1. {a}\n2. {b}\n3. {c}\n")

[floral shell]

Yeh, I realized that lol

thx anyways

[wispy hare]

and by the way, slots will remain ['', '', ''], even after you update a b c, be careful

[floral shell]

oh ok

[mossy mountain]

I'm trying to parse a JSON file - one whose format I can not control - and it has both a list and an actual key : data pair named the same thing "listpicker_5". How can I get Python to look at JUST the key : data pair and ignore the list? (I'm trying to use python3 installed by Ubuntu 18.04.)

"listpicker_5": {
  "selectedNames": [
    "John"
  ],
  "selectedScores": [
    "0.000000"
  ],
  "selectedValues": [
    "John Smith"
  ]
}

[ more stuff ]

"listpicker_5": [
  "John Smith"
],```

My simple code so far is this:
```python
#!/usr/bin/python3
import os,json

file = os.path.abspath('/some/path') + "/sample.json"
json_data = open(file).read()
json_obj = json.loads(json_data)

roObserverName = json_obj["listpicker_5"]
print(roObserverName)```

Any pointers or links to helpful articles is appreciated.

[trim fiber]

What is it?

"listpicker_5": {
  "selectedNames": [
    "John"
  ],
  "selectedScores": [
    "0.000000"
  ],
  "selectedValues": [
    "John Smith"
  ]
}

Is it your sample.json?

[mossy mountain]

Yeah, or parts of it.

Wait, more to come.

[trim fiber]

So it looks like?

{
  ...
  "listpicker_5": {
    "selectedNames": [
      "John"
    ],
    "selectedScores": [
      "0.000000"
    ],
    "selectedValues": [
      "John Smith"
    ]
  },
  ...
}

[mossy mountain]

Sorry, I missed part of the copy/paste. I've corrected the post.

Basically in the sample.json, I have two "listpicker_5" entries - one is a list of values, the other is a single value (and the one I need) later in the file.

I need to ignore the list form and retrieve the single string version when parsing.

[trim fiber]

I think that you cannot create many keys in JSON object because next value overrides previous one

>>> import json
>>> with open("simple.json") as file:
...     data = file.read()
... 
>>> print(data)
{
    "a": 0,
    "b": 1,
    "c": 2,
    "a": 3
}

>>> json.loads(data)
{'a': 3, 'b': 1, 'c': 2}

As you can see, a is not 0 but 3 now because it's the last value assigned to key a

[mossy mountain]

When I run my script, I get the following error:

Traceback (most recent call last):
  File "./jsontest.py", line 59, in <module>
    print("Observer Name: " + roObserverName)
TypeError: must be str, not list

[trim fiber]

And what is the error message? What can you read from sentence TypeError: must be str, not list?

[mossy mountain]

I read it as "the data contained in 'roObserverName' is a list of things instead of a single string"

When I alter the print statement to:
print(roObserverName)
I get:
['John Smith']
instead of :
John Smith

So you are correct in that it's getting the last value in the file, but it's formatting it weirdly.

[trim fiber]

Right, it's not a str so you cannot make concatenation of str and list

Everything comes from your data

"listpicker_5": [
  "John Smith"
],

so listpicker_5 is an array of strings (one in this case)

If you want to hold only one value just write

"listpicker_5": "John Smith",

Then you can execute print("Observer Name: " + roObserverName) because roObserverName is str

So str + str is stil str but str + list is unknown

[mossy mountain]

So I just altered my script to contain:

roObserverName = json_obj["listpicker_5"].pop()

print("Observer Name: " + roObserverName)```
And it works.

Can you recommend a more elegant solution?

[trim fiber]

If you know that json_obj["listpicker_5"] contains only one element you can unpack it using

(roObserverName,) = json_obj["listpicker_5"]

Or call by index

roObserverName = json_obj["listpicker_5"][0]

[mossy mountain]

I'll use the index route - it's more readable for me. Thank you!

[trim fiber]

Your welcome!

[quasi hinge]

Hey guys, I wanted to know that as I am going to learn Data Structures and algorithms, do I need to learn C++ as well or python will do the job?

[warped maple]

Python will do the job.

[quasi hinge]

K thx

[lean dome]

@quasi hinge ^ see this conversation from yesterday.

[surreal ingot]

sorry to ping. but the first solution, (obviously im a bit inexperienved on data stuff) how does that work? and if you dont want to explain, what is that called? is that just a tuple with a second empty val in which you are assigning to his list...?

[split obsidian]

What exactly is a functor? From my perspective it seems to create functions (objects?) that share an interface?

Also has something to do with map?

[brave oak]

in the programming context, there are two meanings

the first doesn't really exist in Python because functions are first-class

but in some other languages you'd need to turn functions into things that can be passed around like other objects (ints, floats, etc.)

those "things" are called functors.

on the other hand, there is also a more category theory-ish meaning of "functor"

basically, something that can be mapped over.

[split obsidian]

@brave oak Is there also a third case that looks something like functools.partial?

[brave oak]

what do you mean

[quasi hinge]

thx man . thats means i need to learn C++ which will hardly take 2 weeks

[wraith valve]

c++ has nice parts and also has parts that give big headaches

[quasi hinge]

Ohk

[trim fiber]

No problem at all with your ping.
If you have a tuple with many values you can unpack it by writing

>>> x = (0, 1, 2)
>>> (a, b, c) = x
>>> print(a, b, c)
0 1 2

When you have tuple with only one element you can unpack it by writing

>>> x = ("a",)
>>> (a,) = x
>>> print(a)
a

When you write a = x you just assing tuple ("a",) to variable a but you want to unpack it so you need to add ,.

You can omit ( and ) so in short

>>> a, = x
>>> print(a)
a

It's very useful when you write with struct like struct.unpack("<Q", data) - it returns struct with only one element and to unpack it you can get value by index but by unpacking is better to read in my opinion

>>> import struct
>>> data = struct.pack("<Q", 2481632)
>>> num = struct.unpack("<Q", data)[0]
>>> print(num)
2481632
>>> num, = struct.unpack("<Q", data)
>>> print(num)
2481632

Hope that it's clear now @surreal ingot

[surreal ingot]

I see

yes! thank you so much

[trim fiber]

Your welcome!

[ashen wharf]

def shellSort(l):
    interval = len(l)//2

    while interval >= 1:
        for i in range(interval, len(l)):
            for j in range(interval, i+1, -interval):
                if l[j] > l[j - interval]:
                    l[j], l[j - interval] = l[j - interval], l[j]
                else:
                    break
        interval //= 2
    return l

this shell sort doesn't work

[grand zenith]

hi

class Node { public: int data; Node* next; };

can somebody explain whats "Node* next"

i totally have no clue

[wispy hare]

it represents the next node in that linked list

a linked list node must know where is the node after it located, so it needs a pointer next that points to the next node

[grand zenith]

int *p is a pointer

whats Node* ?

[wispy hare]

a pointer to an element of type Node

[grand zenith]

what is the datatype

sorry but i am not getting it @wispy hare

[grand zenith]

can u share any resource that explains this concept..

[wispy hare]

yes sure just search for linked list in C

[grand zenith]

what if i write Node *next instead of Node* next

[hardy haven]

It's the same

[grand zenith]

never saw a variable declared with class name..

[hardy haven]

It's similar to all the primitive datatypes

[abstract barn]

In what context would an adjacency matrix be favoured over an adjacency list?

[kindred sinew]

Have a great coding day ahead guys !

[gusty grove]

if i have a function F(x,y,z) that outputs (a,b,c) is there a way to solve for F?

[kindred sinew]

Could you share the code?

[gusty grove]

i dont have any yet, im just asking if its possible

[kindred sinew]

Yes, you can define a function in the way just you want.

[abstract barn]

Yeah, it would be

[gusty grove]

hm.

i dont know the function

im trying to find it

[abstract barn]

Is this for a specific task or just an idea

[gusty grove]

just a idea

[abstract barn]

Well the context is obviously important

[gusty grove]

im asking if i can solve for a mathematical function F given its inputs and outputs

without doing numeric regression

[abstract barn]

Is f(), a complex function or just a simple coefficient?

[kindred sinew]

you need to define it. I would say refer for resources that include constructing basic functions with some parameters.

[gusty grove]

no, im trying to find it. its a mathematical function

not a python function

[kindred sinew]

Okay

Got it

then plotting the graph would be simpler technique, to solve the function that has dependent and independent variables, ie performing Regression and fitting it into straight line. Lol 😅

[split obsidian]

These seem equivalent to me:

class Thing:
    def __init__(self, b):
        self.b = b

    def __call__(self, a):
        return a + self.b

thing = Thing(b=1)
thing(5)

from functools import partial

def add(a, b):
    return a + b

thing2 = partial(add, b=1)
thing2(5)

[trim fiber]

As you can read from docs functools.partial returns partial object which is very similar to your Thing class: https://github.com/python/cpython/blob/3.9/Lib/functools.py

[split obsidian]

But is Thing a functor? What about add?

[trim fiber]

Thing is not a function, it's callable object so it can work as a function

[cloud bough]

If our middle element is less than target, our low point becomes mid + 1 and if our mid element is greater than target, our high point becomes mid - 1.

do i have this correct?

for a binary search

[wraith valve]

i think i remember talking to to yesterday about binary search

basically if our target is less than mid

our high becomes mid - 1

and if our target is greater than mid

our low becomes mid + 1

u just flipped it around but otherwise its right

[vital mist]

I just wrote a short en/decryption algorithm, can someone tell me, wether it (or the concept implemented) has some major flaws?

#!/usr/bin/env python3
import sys
import random
file_path = sys.argv[1]
plain_data = ""
with open(file_path,"r") as f:
    plain_data = f.read()
password = input("Password: ")
random.seed(int("".join([str(ord(i)) for i in password])))
new_file = ""
for l in plain_data:
    new_file += chr(ord(l)^random.randint(0,10000))
with open(file_path,"w") as f:
    f.write(new_file)
print("[+] Program done!")

[cloud bough]

thank you! i had to write that down. hopefully ill remember it. 😁

[wraith valve]

i think the easiest way to remember it

is not what exactly it does

but rather the invariant (the thing that doesnt change)

ie in this case it is that the element u are looking for is at an index from low to high

and that ofc the array that u are looking though is ordered

[trim fiber]

Don't roll your own crypto, you rely on PRNG and it's not good idea

[vital mist]

I couldn't find a seed() function in the crypto module

[trim fiber]

I don't understand

Anyway, use well known ciphers like AES

[brave oak]

@split obsidian in that sense of "functor", there is no distinction between a function and a functor in Python

since functions are first-class objects

[eager hamlet]

is there some method

so i can process 2 types of queries in a tree (each set to some random initial number)

1. just xor sum of all nodes between 2 nodes

2. update val of node

https://softwareengineering.stackexchange.com/questions/305456/finding-xor-sum-in-a-tree

i found this link

but idk how to process part 2

(ping 2 help thx)

[gusty grove]

can someone help me convert this to numpy?

sum((min(dst(house, shop) for shop in shops) for house in houses))

a bit more readable:

running_total = 0
for house in houses:
    value = min(dst(house, shop) for shop in shops)
    running_total += value

return running_total

[severe geyser]

What is the most efficient way to built a large dataset for ML or DL? Break it up in pieces? Dicts? Tuples in dicts?
I've a dict with 10k entries, iterating through it isn't memory-wise cheap, any ideas?

[drifting trellis]

Hi, do we consider Cross Entropy Method (RL) as an algorithm ?

[ivory pilot]

Don't suppose anyone can help me with this, I can't seem to work out how to translate the solution to the input

https://github.com/google/or-tools/blob/stable/examples/python/arc_flow_cutting_stock_sat.py

[cloud bough]

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def is_empty(self):
        return self.items == []

    def peak(self):
        if not self.is_empty():
            return self.items[-1]

    def get_stack(self):
        return self.items

is this good enough for a stack data structure? or am i missing something

[mint jewel]

@cloud bough peek is the proper spelling, .get_stack() is useless as you can just use .items. I would also make is_empty() __bool__, implement __len__ and __iter__.

[wispy hare]

you can also add more methods to train on stacks (sort, reverse...)

[cloud bough]

ahh got it, thank u both

[agile sundial]

how would sorting a stack even work

err, not how would it work, why would you do it

[wispy hare]

just to practice, because a real stack is more limited than a python list, so it's interesting to try sorting it by using push/pop/is_empty/peak only

[agile sundial]

sure

[wraith valve]

i feel being able to access all elements of a stack defeats its purpose

[wispy hare]

exactly

[pallid phoenix]

should asking for help in improving code for an algorithm asked here? or in a help channel?

[wispy hare]

yes you can do it here I think

[pallid phoenix]

  
    for y in range(len(datarows)):
        for x in range(len(datarows[0])):
            gridindexes.append(list([y, x]))
    for index in gridindexes:
        digit2list = touching(datarows, [index], [index])
        for digit2 in digit2list:
            digit3list = touching(datarows, [digit2], [digit2] + [index])
            for digit3 in digit3list:
                if digitlength == 3:
                    final.append(str(datarows[index[0]][index[1]])
                                 +
                                 str(datarows[digit2[0]][digit2[1]])
                                 +
                                 str(datarows[digit3[0]][digit3[1]]))
                else:
                    digit4list = touching(datarows, [digit3], [digit3] + [digit2] + [index])
                    for digit4 in digit4list:
                        if digitlength == 4:
                            final.append(str(datarows[index[0]][index[1]])
                                         +
                                         str(datarows[digit2[0]][digit2[1]])
                                         +
                                         str(datarows[digit3[0]][digit3[1]])
                                         +
                                         str(datarows[digit4[0]][digit4[1]]))

def touching(grid, cv, exc):
    digits = []
    leny = (len(grid) - 1)
    lenx = (len(grid[0]) - 1)
    for digit in cv:
        digitlist = []
        touchinglist = [[digit[0] - 1, digit[1] - 1], [digit[0] - 1, digit[1]], [digit[0] - 1, digit[1] + 1],
                        [digit[0], digit[1] - 1],                               [digit[0], digit[1] + 1],
                        [digit[0] + 1, digit[1] - 1], [digit[0] + 1, digit[1]], [digit[0] + 1, digit[1] + 1], ]
        for t in touchinglist:
            if 0 <= t[1] <= lenx and 0 <= t[0] <= leny and [t[0], t[1]] not in exc:
                digitlist.append(t)
                digits += digitlist
                digitlist.clear()
    return digits

[pallid phoenix]

here i use digitlength to determine if i want to use my function 3 times, or 4 times, but i want to be able to use about any user defined number, not just 3 or 4, but im having a hard time properly looping it to make it so dynamic

i udnerstand my variable names are bad, if you have any advice in that regard i would appreciate it

Made a Reddit post asking the same, but i described all the variables here :(https://www.reddit.com/r/learnpython/comments/kiyvbd/hello_i_want_to_make_my_code_more_dynamic_than_it/)

[wispy hare]

can you explain what is this algorithm supposed to do?

[pallid phoenix]

so it takes a 2D list, and returns every possible 3/4 digit length string of elements adjacent to each other

touching returns the indexes of the original grid, that are adjacent to the index in the arguments, so i loop through every index in the 2D list, get whats t adjacent, from the list returned from that, get whats adjacent, and repeat that till i have 4 digits, if that makes any sense?

[pallid phoenix]

an example of how to get 2 numbers, a 2x2 grid has 24 4digit results

[sweet crest]

Hey,
does anyone know of a good recourse to learn approximations?
Im specifically looking for ways to approximate functions to given sets of points such that the average distance of all the points to the function is minimized.
eg.: given 3 points, approximate a function of degree 1

[wispy hare]

I'm not sure but isn't it linear regression?

[fiery cosmos]

hey guys do u know how to open tor with selenium

[oblique panther]

@fiery cosmos that's a question for #web-development, assuming that what you wanted to do with Tor is ethical

[fiery cosmos]

Okay thanks bg

[austere sparrow]

A linked list is essentially a stack, and linked lists can be sorted with O(n logn) complexity using mergesort, so that's a reasonable goal

[lean dome]

hm. If you sort a stack, it's not a stack anymore. Or, to put that differently, "sort" isn't an operation that makes sense for the stack abstract data type. The stack abstract data type can only be mutated by pushing and popping, so the only way to sort a stack using the public interface of a stack would be to pop every item and push them back in sorted order.

[lean glade]

That is what syph proposed to do though

To sort only by pushing/popping/checking if is_empty/peeking

[eager hamlet]

The organizers of the children's holiday are planning to inflate m balloons for it. They invited n assistants, the i-th assistant inflates a balloon in ti minutes, but every time after zi balloons are inflated he gets tired and rests for yi minutes. Now the organizers of the holiday want to know after what time all the balloons will be inflated with the most optimal work of the assistants, and how many balloons each of them will inflate. (If the assistant has inflated the balloon and needs to rest, but he will not have to inflate more balloons, then it is considered that he finished the work immediately after the end of the last balloon inflation, and not after the rest).

Input
The first line of the input contains integers m and n (0≤m≤15000,1≤n≤1000). The next n lines contain three integers each, ti, zi, and yi, respectively (1≤ti,yi≤100,1≤zi≤1000).

Output
In the first line print the number T, the time it takes for all the balloons to be inflated. On the second line print n numbers, the number of balloons inflated by each of the invited assistants. If there are several optimal answers, output any of them.

Example
input
1 2
2 1 1
1 1 2
output
1
0 1 ```so i'm doing this problem

def inflated_amt(worker, time):
    chunk_time = worker[0] * worker[2] + worker[1]
    return (time // chunk_time) * worker[2] + min((time % chunk_time) // worker[0], worker[2])


def inflatable(workers, time, req):
    return sum(inflated_amt(w, time) for w in workers) >= req


ballons, workerNum = [int(i) for i in input().split()]
# balloon inflation time, rest time, and balloons for rest time
workers = [[int(i) for i in input().split()] for _ in range(workerNum)]

lo = 0
hi = 10 ** 20
best_time = -1
while lo <= hi:
    mid = (lo + hi) // 2
    if inflatable(workers, mid, ballons):
        best_time = mid
        hi = mid - 1
    else:
        lo = mid + 1

each_inflated = []
alr_inflated = 0
for w in workers:
    this_inflated = inflated_amt(w, best_time)
    alr_inflated += this_inflated
    if alr_inflated >= ballons:
        this_inflated -= alr_inflated - ballons
        each_inflated.append(this_inflated)
        break
    each_inflated.append(this_inflated)

while len(each_inflated) < len(workers):
    each_inflated.append(0)
print(best_time)
print(' '.join(str(i) for i in each_inflated))
```and my code is as follows- however, it doesn't work- anyone know why?

[thick nymph]

Hey guys, I've just uploaded a video about the sieve of eratosthenes implementation in Python (in German language), and I would love to get your opinion about it. Surely I'm not a pro in video production, but I'd like to improve myself with time in that kind of activity. If demand is there, I will also post this kind of algorithm implementations in English language and for sure also other interesting topics about computer science on that channel. Please show me demand in terms of subs, likes or comments (:

My goal is to post a wide range of python basics, implementations, examples of complex projects and also highly theoretical fields of computer science, too. Surely I can only afford this time investion, if I see any kind of reaction to it.

Greetings,
Pio

https://www.youtube.com/watch?v=8uftjpYJnQU&t=479s

(It's here in the algos-channel, because it is about algorithms) 😄

[ashen venture]

hey

find the sum of even fibonacci numbers with time complexity of log(log(n))
can anyone do it?
i cant figure it out

someone help

[wispy hare]

what does n represent?

[ashen venture]

just a sec wait

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

this is the problem

i can do it with log(N), N is 4 million

how about log(log(n))

[wispy hare]

you can't say: n is 4 million

because 4 million is a constant

[ashen venture]

4 million will change

what if N is 4*10**(10**7)

40^(10^7)

[wispy hare]

so you mean n is smaller than 4 millions

[ashen venture]

wait forget everything let me rephrase the question

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

so this is the question

we can solve it

using some code

but that will provide time complexity of log(n)

i wanted to do it with Log(log(n))

did you get it no?

@wispy hare

[wispy hare]

https://iq.opengenus.org/sum-of-even-fibonacci-numbers/

I found this

[ashen venture]

thats the complexity?

whats*

https://projecteuler.net/thread=2;page=5#55828

here look at this post

someone made some big brain optimizations to work it in log(log(N))

@wispy hare

[fiery cosmos]

someone can recommend to me any videos about backtracking? I simply cannot understand this concept and the implementation of it. I want a general implementation, not a shitty maze/sudoku solving

[wispy hare]

Try to understand the concept instead of the general implementation, because backtracking can be applied to trees, graphs, 2D arrays, miscellaneous situations...

[fiery cosmos]

well i know the concept, if your next step is wrong you go back to the previous correct step

[wispy hare]

yes, this is why a backtracking algorithm usually has two base cases

a positive base case, that occurs when we've been able to find a valid solution to the problem, and a negative base case, that occurs when we notice that the actual solution is not valid

for example, we can have a collection of items, each one of them has a weight

and we want to find all combinations of items such that the total weight doesn't exceed maxWeight

the backtracking algorithm that we can use here is that at each index of weights, we try both possibilities, when we take the item i and when we don't

by doing so, we will be able to reach all possible combinations of the items

but here we want only those that respect the condition of having a total sum that doesn't exceed maxWeight

we can wait to generate all combinations, then filter, by writing something like this

return filter(lambda comb: sum(comb) <= maxWeight, combinations)```

but we can avoid having to generate them all, by subtracting weight[i] from maxWeight when we take an item

[fiery cosmos]

i think it s too much for what I really want to do on the generating subsets of a set problem

[wispy hare]

so if maxWeight become negative, we abondon the actual combination, because we already know that it exceeds maxWeight, so we backtrack

[wispy hare]

generating subsets of a set is easier, you have to use the take-or-leave method I explained here without caring about a particular condition

For example this is what happends when we want to generate subsequences of the string "abcd"

you can see that at each index, we have two new possibilities, one where we take the actual character and one where we don't

[fiery cosmos]

set = [10, 23, 42]
parts_set = []

def subsets(set, k):
    if k == len(set):
        print(parts_set)
    else:
        subsets(set, k + 1)
        parts_set.append(set[k])
        subsets(set, k + 1)
        parts_set.pop()

i think i did it

[wispy hare]

nice!

[wispy hare]

now you can try now dealing with conditions

for example print only subsets whose sum is less than k

or those that have at most k elements

or those that have exactly k elements

you can also learn how to deal with cells problems in matrices

example: given a matrix, check if there is a path between (x1, y1) and (x2, y2)

by the way, the problem that I was explaining at the beginning (combinations that don't exceed maxWeight) comes from the course on recursion I released this week: https://bit.ly/recursioncourse (tell me if courses links are not allowed in this channel)

[fiery cosmos]

i follow on instagram inside code but idk if i can trust them with this recursion course

[wispy hare]

inside code is my account xd

it's me :c

[fiery cosmos]

oh really?

lol

[wispy hare]

yes!

[fiery cosmos]

that s cool

[eager hamlet]

The organizers of the children's holiday are planning to inflate m balloons for it. They invited n assistants, the i-th assistant inflates a balloon in ti minutes, but every time after zi balloons are inflated he gets tired and rests for yi minutes. Now the organizers of the holiday want to know after what time all the balloons will be inflated with the most optimal work of the assistants, and how many balloons each of them will inflate. (If the assistant has inflated the balloon and needs to rest, but he will not have to inflate more balloons, then it is considered that he finished the work immediately after the end of the last balloon inflation, and not after the rest).

Input
The first line of the input contains integers m and n (0≤m≤15000,1≤n≤1000). The next n lines contain three integers each, ti, zi, and yi, respectively (1≤ti,yi≤100,1≤zi≤1000).

Output
In the first line print the number T, the time it takes for all the balloons to be inflated. On the second line print n numbers, the number of balloons inflated by each of the invited assistants. If there are several optimal answers, output any of them.

Example
input
1 2
2 1 1
1 1 2
output
1
0 1 ```
so i'm doing this problem

def inflated_amt(worker, time):
    chunk_time = worker[0] * worker[2] + worker[1]
    return (time // chunk_time) * worker[2] + min((time % chunk_time) // worker[0], worker[2])


def inflatable(workers, time, req):
    return sum(inflated_amt(w, time) for w in workers) >= req


ballons, workerNum = [int(i) for i in input().split()]
# balloon inflation time, rest time, and balloons for rest time
workers = [[int(i) for i in input().split()] for _ in range(workerNum)]

lo = 0
hi = 10 ** 20
best_time = -1
while lo <= hi:
    mid = (lo + hi) // 2
    if inflatable(workers, mid, ballons):
        best_time = mid
        hi = mid - 1
    else:
        lo = mid + 1

each_inflated = []
alr_inflated = 0
for w in workers:
    this_inflated = inflated_amt(w, best_time)
    alr_inflated += this_inflated
    if alr_inflated >= ballons:
        this_inflated -= alr_inflated - ballons
        each_inflated.append(this_inflated)
        break
    each_inflated.append(this_inflated)

while len(each_inflated) < len(workers):
    each_inflated.append(0)
print(best_time)
print(' '.join(str(i) for i in each_inflated))```
and my code is as follows- however, it doesn't work- anyone know why? (ping 2 help thx)

[agile sundial]

"i can't understand"
"just try to understand"

[carmine anvil]

Can anyone suggest a data structure where I can store points and efficiently query all points within a particular radius, and also efficiently insert and remove points

Or, does something like this exist?

Also, if I can get support for toroidal space with that (assuming all points are within an aabb) it'd be amazing

(Sound too much like I'm making an order at a restaurant or something)

[eager hamlet]

is that supposed to like
say my help request is bad?

i mean i fixed it in the end

was a small problem with array indices

[agile sundial]

oh

i was scrolled up a lot sorry ;-; @eager hamlet yours looks fine

[eager hamlet]

oh yeah

i mean looking back at it it was kinda bad

[agile sundial]

although yeah, "it doesn't work" isn't the best

[fiery cosmos]

what is a problem

[eager hamlet]

uh i fixed it already loll

[austere sparrow]

We don't allow advertising your own paid resources, but you can share your open-source projects freely.

[wispy hare]

okay thanks for telling me!

[cloud bough]

does someone have a full implementation of a linked list coded?

all these websites have different implementations and its confusing me

[wraith valve]

if ur seeing the -> thats c

[cloud bough]

oh is that like a pointer

[wraith valve]

thats basically dereference then dot

[cloud bough]

ah

[wraith valve]

its not really applicable to python tho

-> syntax

[cloud bough]

in python for a linked list, should i create a node class and a linked list class, or should it be all in one class?

[fiery cosmos]

you can have class inside class ig?

[wraith valve]

ive seen both ways

where there is a class to hold the variable to the start of the list and maybe a variable to the end of the list

and then u have a class for the nodes

[cloud bough]

this works, right?

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.head = None

[wraith valve]

that should work

[cloud bough]

ah okay great

thanks

[wispy hare]

would be better to do:

  def __init__(self, data=None, next=None):
    self.data = data
    self.next = next

class LinkedList:
  def __init__(self, head=None):
    self.head = head```

it gives more flexibility when creating a Node or a LinkedList

[agile sundial]

you could also have something to store the length of the list, but that's not required

[cloud bough]

ahh got it

[cloud bough]

so increment a value for every node created?

[agile sundial]

something like that

[cloud bough]

good idea, thanks

[wispy hare]

you can create an empty node: Node()
node by giving it a value: Node(5)
or creating many nodes at a time: Node(2, Node(3, Node(1, Node(8))))
same thing for the linked list

[wispy hare]

yes, because otherwise, you'd have to traverse it again to know the length

[cloud bough]

ahh

im learning all these data structures, but i have no idea when to use them when asked on a problem 😭

[agile sundial]

you would need to learn why to use one over another

for example, sets are nice when you need to do many membership tests

[wraith valve]

advantages vs disadvantages

[cloud bough]

oh

[wraith valve]

like there are always advantages and disadvantages with a choice

and u just pick the one that fits the best

[cloud bough]

i see. okay i need to look more into pros and cons of each data structures then

[wraith valve]

thats one place to start

usually pros and cons related to runtime and memory usage

[wispy hare]

yes, focus more on that instead of implementation

[wraith valve]

like for example if u wanted an ordered list or sth

u can choose a linked list or an array

for example

and of the two each one has its advantages and disadvantages

[cloud bough]

like appending or prepending on a list is O(n) right?

cuz u have to move each index when adding an element

[wraith valve]

yeah

usually ur problem has constraints to it ie what types of operations u need to support

and once u took into consideration all the constraints, u try to pick one that suits it the best

[cloud bough]

ahh i see

[wraith valve]

although i will say when u go look into runtimes and such u might encounter some math

[wispy hare]

yes, excpet for appending an element at the end of a list which is O(1)

[agile sundial]

it's amortized O(1), O(n) worst case

occasionally when appending you need to copy the elements into a larger buffer

[wraith valve]

and i guess that math part can also be considered to be part of the "science" of computer science

[cloud bough]

yeah i got a lot to learn about that

im understanding time complexity right now

[wraith valve]

with lists stacks queues there isnt too much math

prob only thing is the asymptotic notation

[cloud bough]

ah

[wraith valve]

the runtimes are a bit intutitive as there isnt much proofs with theses

[agile sundial]

sets and dicts are quite magical though

[cloud bough]

most problems that i solved on leetcode happened thx to dictionarys

[wraith valve]

u can also look into hashing and looking at their ways of dealing with collisions if ur interested in dicts and such

[cloud bough]

yeah ill do that. those are all for hash tables aka dicts, right?

collisions and etc

[wraith valve]

yeah there are different implementations

and they deal with collisions differently

[cloud bough]

ah

[wraith valve]

and ofc there are pros and cons to each

[fiery cosmos]

What's the algorithm for cubic interpolation with only one coordinate

like i want to transition from 1 to 8 for example with 60 iterations

[fiery cosmos]

how to generat sphere in python

visually or mathematically? @fiery cosmos

[wraith valve]

x^2 + y^2 + z^2 = r^2 works mathematically

i would imagine with python u would simply evaluate this expression at ur desired radius at intervals that suits ur accuracy of what looks like a sphere

[fiery cosmos]

1. How do I get the surface area of a sphere and cylinder (separately)
2. How do I calculate the length of all edges of a cube or 3d rectangle

[austere sparrow]

Once you understand time and space complexity, the advantages of one structure should become much more clear.
You can always implement a data structure in terms of another (e.g. impelment a list using a dict with integer keys), the only differences are convenience for certain problems and performance

[cloud bough]

ah that makes sense, I am going to really try and understand time/space complexity.

[fiery cosmos]

given a string i need to find a t so that s = t + t + ... + t

how can i do that?

if i have s = abcabc, t is abc and k = 2

s = "cicici"
chars = ""
t = ""
k = 1

for i in s:
    chars += i
    t += chars
    while len(t) <= len(s):
        t += t
        k += 1
    if t == s:
        print(k)
        break
    else:
        t = ""
        k = 1

if i do this it repeats more than once

and if i debug it

when k = 3

this thing is cicicici

[stray geode]

hmm, well the way i see it. we can incrementally split the string (first at 0 and 1, then at 0 and 2, 0 and 3, etc.) and then repeat that string until it matches the length of the original string. this explanation wasn't worded all that well, but here's a solution that works for that specific case

# string to find the substring of
s = "cicici"


i = 1
while i <= len(s):
    substr = s[0:i]
    
    newstr = substr * (len(s) // i)
    if newstr == s:
        print(f'found {substr} to be the correct sequence!')
        break

    i += 1

[fiery cosmos]

well i cannot see any difference

between your version and my version

but why len(s) // i

[stray geode]

that's just to force integer division

since len(s) / i could potentially produce a float, and i can't multiply a string by a float

[fiery cosmos]

so the 'k' in this case is len(s) // i

and that s how many times it repeats itself

[stray geode]

it repeats the string?

[fiery cosmos]

and why it s not

i < len(s)

oh, i <= len(s)

i forgot how slicing works

[fiery cosmos]

i have a number. I need to put 3 points so I can get all IP combinations:
1721601 -> 172.16.0.1 | 17.216. 0. 1 | 1.72.160.1

How can I do that? I have no idea

[agile sundial]

why not just generate the 4 numbers separately

[lean dome]

it seems like the puzzle is to figure out every possible way to place three . into the string 1721601 to divide it into 4 legal octets. In which case, I'd go for a recursive solution: there's 3 legal places to put the first . (after the 1, after the 17, and after the 172), and then you have to figure out where it's legal to place 2 . inside 721601, 21601, or 1601 respectively. Inside 721601 it's only legal to put it after 7 or 72 (because 721 > 255), so then you recurse to put 1 . into 21601 or 1601 respectively.

though this seems to exclude 172.1.6.01 as a solution for some reason - I can't see why; that seems legal to me - it results in 4 octets, each with a value <= 255 (maybe there's an implied but not stated rule that an octet can't have any unnecessary leading zeroes?)

this is also a tiny enough input that the total brute force option is fine: the places where a . could be placed in 1721601 to divide it into 4 non-empty sections are after the 0th character, or after the 1st, or 2nd, or 3rd, or 4th, or 5th. Use something like itertools.combinations to generate all possible locations to insert the 3 dots, and then filter out the invalid ones like 1.7.2.1601 afterwards by splitting the string into 4 sections at those positions and making sure that 0 <= x < 255 for each section.

[wispy hare]

note that this solution is considered as a brute-force solution, it runs on O(n²) time complexity, where n is the length of s

I've read about an O(n) solution where you try to find s in (s+s) at an index that is different from 0 or something like this

[stray geode]

good point! i wrote it up pretty quickly haha. i had actually thought about this earlier and how there might be a better solution

[agile sundial]

yes, it's possible in O(n) by ||creating a suffix tree and finding the deepest node||

actually, i may have read the problem wrogn

[stray geode]

i think we could assume that the input is always gonna be something like abcabcabc

so i think we could optimize around that :p

[agile sundial]

ok, it is possible in O(n)

[cloud moth]

i don't get it, as a developer, is it necessary to understand time-space complexity. Do developers actually check this stuff in live code ?

[stray geode]

i doubt most developers are thinking too heavily about it. most stuff that really benefits from complexity analysis, like searching, sorting, etc. are either built-in or established in the environment. but i'm not a developer, so don't take it from me :p

also, that O(n) solution looks something like

def get_generating_substring(string):
    repeated = string * 2
    index = repeated.find(string, 1)
    if index != len(string):
        return string[:index]
    return string

get_generating_substring('abcabcabc') spits out abc
and get_generating_substring('hello') gives us hello

[cloud moth]

@stray geode is recursion better than loops. I heard recursion is better in performance too.

do you have any comment

[stray geode]

iteration is almost always the best way to go haha. recursion is really cool, but it rarely ends up being the most efficient solution

[primal sparrow]

What exactly does this do text = a[i].text with i being the number looping in a for loop

i cant wrap my head around it

[cloud moth]

@stray geode how do you actually calculate the performance of the code. i meant doesn't it vary per hardware

[stray geode]

you usually don't calculate the performance of code, just the performance of it relative to other code that does the same thing

but uh

i shouldn't say that because, i mean maybe you do often calculate the performance of code?

i never see anyone saying "this code should run in approximately this time" though :p

[cloud moth]

@stray geode i just code sub consiconusly

[agile sundial]

you determine time complexity, which is how your runtime scales as input size increases

[stray geode]

but that's really the question that complexity analysis solves. if one solution works in O(n), while the other works in O(log n), then it's pretty clear which one to use if you plan to scale

[agile sundial]

yes, you want to pick the data structures and algorithms best suited for your task

for production code, the wrong data structure may lead to huge slowdowns

[carmine anvil]

Technically no. O notation hides the hidden constants. Fibonacci heaps are amortised O(1) for a bunch of operations, but they have such a high constant factor that you just don't want to use it unless you have huge inputs

10n is better than 10000000000logn for a large range of inputs

[stray geode]

right, of course

[agile sundial]

he said if you plan to scale lol

[stray geode]

wat santa said

relevant reading lmfao https://en.wikipedia.org/wiki/Galactic_algorithm

[carmine anvil]

Even if you plan to scale. My aforementioned fiboancci heaps example, I tested. Binary heaps were the fastest even for graphs of 2500nodes and 0.8V² edges. Fibonacci just wasn't worth it

[wraith valve]

bogosort be like

[carmine anvil]

Ackermann function be like

[cloud moth]

i heard about ackermann, what is it actually used in realworld though

[carmine anvil]

It's mostly theoretical afaik, but the inverse Ackerman function comes up in the time complexity of disjoint set union data structure implemented with pointers and path compression

[cloud moth]

but there is no pointers in python, as per my knowledge

[wraith valve]

basically if u have a disjoint set implementation

and u want to do path compression

and disjoint sets can also be implemented as an array

or use an array to hold the connections instead of using pointers

like the value is the index of the parent

[cloud moth]

@wraith valve oh. i am just a noob though

[wraith valve]

its one possible implementation

and pointers can be just thought of as a variable in python

lots of times ppl use c++ for writing an algorithm

and thats when there is a pointer

[cloud moth]

interesting

[wraith valve]

but u can do the same thing in python

[cloud moth]

does anyone know about back-propogation algol

[carmine anvil]

Yeah pointers are not necessarily "pointers", just some sort of reference. Index arrays are the same thing, and probably more efficient than linked list trees

[lean dome]

You definitely need to understand time complexity in order to write real world code. Unless you understand why a linked list performs better than a Python array for insertions in the middle, or why checking if an element is in a dict is much faster than checking if an element is in a list, you'll forever be choosing the wrong data structure to represent your code, and making it run much slower on real life data sets as a result.

it's true that most developers will never need to write a sorting algorithm, or build a dynamic array or a hash table in real world code - language's standard libraries give those things to developers out of the box, and it almost never makes sense to reinvent them yourself. But, if you don't understand time complexity, and to some extent space complexity, you'll never know when choosing one of them is the wrong option.

[cloud moth]

@lean dome guess i need to start following in my codes now.

Probably a dumb question... how exactly do i encrypt a large video/any file without slowing down the device. For example. suppose i have a video file of 50gb, how exactly should data be read for encryption process. A) Do i read & perform encryption operation on raw bytes of particular fixed length (like chunks) from original source B) Convert entire file to raw bytes and then do procedure A. c) any better solution, please suggest.

[wraith valve]

ur talking about compression right?

[lean dome]

regardless of whether you're talking about encryption or compression, the answer is the same: read bytes from the file in fixed-size blocks, and feed those blocks to the encryption or compression library. The library may have a method for doing this for you.

[wraith valve]

from talking to someone who made a decompressor

u definately want to use threads to split up the work

[lean dome]

if you've written it in Python, that will only make it slower.

[cloud moth]

@wraith valve but threads run pretty much random, how exactly do i know which thread completed which and which has not

[wraith valve]

use synchronisation

[lean dome]

threads in Python cannot be used to parallelize Python code running in multiple threads.

[wraith valve]

mutex semaphore take ur pick

[cloud moth]

interesting...

[wraith valve]

i have a feeling with decoding or whatnot there is no shared data access

im not sure about the exact algorithm on how the video is chopped up

[lean dome]

they can be used to parallelize IO bound code, but not CPU-bound code, because only one thread can be holding the GIL at a time, and only the thread with the GIL can modify Python data structures or execute Python bytecode. If the function running in the thread spends most of its time crunching numbers - like a decompression algorithm would - and that algorithm is written in Python (as opposed to in C, let's say), adding threads to the mix will only slow it down

[cloud moth]

but what if, i want the first-encrypted blocks hash needs to act as the key for second-block to be encryption key

[wraith valve]

i guess i should say the person that made a decompressor wrote it in c++

[lean dome]

right - in that case threads could help much more than they could in Python.

[lean dome]

then it sounds like you're trying to invent your own encryption algorithm, which is A Very Bad Idea

[cloud moth]

just learning,not re-inventing wheel

[wraith valve]

i mean how u would approach it depends on how u chop up the video?

like frame by frame or sth

[cloud moth]

you can do frame by frame? how isn't mp4 like properiatry code

[wraith valve]

idk for sure thats why i said depends on how u handle the vid

[lean dome]

getting encryption right, in a way that makes it difficult to break and unable to leak information about the encrypted contents to someone who doesn't have the key, is very, very difficult. People spend their entire careers working on just that one problem. You really want to use an existing encryption algorithm. If your goal is to learn, you should look up how some existing encryption algorithm works and study it.

[wraith valve]

i mean things that are independent from each other can be easily parallelized

dont need to worry about synchronisation in those cases

[cloud moth]

oh...

Introduction to algorithms by mit press. Is this book good ?

[keen hearth]

The Cormen book? It's good. It's pretty much the standard algorithms textbook.

Quite mathy though, if that's not your thing.

[fiery cosmos]

from numbers import Real
from collections.abc import Iterable

def maximum(it: Iterable[int]) -> Real:
    try:
        maxi = it[0]
    except IndexError:
        return None
    for i in range(len(it)):
        if it[i] > maxi:
            maxi = it[i]
    return maxi

def minimum(it: Iterable[int]) -> Real:
    try:
        mini = it[0]
    except IndexError:
        return None
    for i in range(len(it)):
        if it[i] < mini:
            mini = it[i]
    return mini
``` Can I get some feedback on these max and min algorithms? is there any way to find the max and min without iterating?

[stable pecan]

there isn't, every item needs to be compared to find the min or max, but you can iterate through the items directly, without having to index:

def maximum(it):
    mx = -float("inf")  # Everything is greater than negative infinity, no need to prime the first value
    for item in it:
        if item > mx:
            mx = item
    return mx

[fiery cosmos]

would you return mx?

[stable pecan]

yep

fixed

[fiery cosmos]

omg that's so much better than mine

thank you

[stable pecan]

np

[fiery cosmos]

need someone to try my game dm .py

[peak nimbus]

can anyone help me with genetic algorithm in python ? have to use it to solve a maze

[quartz oxide]

with open(problem_set, "r") as stageFile :

I have a txt file named probem_set

and its in the same file with python file

so when I use open

It doesnt open my file

Anyone help ?

Found it nvm

[carmine anvil]

I need to store a bunch of points in 2D space. Ordinarily, I would do this with a quadtree. However, I need to be able to handle toroidal space. What kind of data structure can I use for toroidal aabb queries?

[fiery cosmos]

if I have a list of tuples, where each tuple has 3 elements, can I create a key function for the sorted function so that the t[1] is ascending and if t1[1] == t2[1], the t[2] is descending?

[('a', 2, 100), ('b', 1, 19), ('c', 2, 27), ('d', 1, 25), ('e', 3, 15)] to become [('d', 1, 25), ('b', 1, 19), ('a', 2, 100), ('c', 2, 27), ('e', 3, 15)]

oh, okay lmao i m dumb

just needed to put a -

def for_sorting_tuples(t):
    return t[1], -t[2], t[0]
tup = sorted(tup, key=for_sorting_tuples)

[wispy hare]

you can use a lambda function btw

[ashen niche]

I'm trying to print a graph (vertices, edges) using pyplot but it doesn't seem to work, for example:

            x, y, z = node.get_pos()
            circle1 = plt.Circle((x, y), .2, color='r')
            plt.gcf().gca().add_artist(circle1)

throws an error matplotlib.units.ConversionError: Failed to convert value(s) to axis units: '35.212217299435025'

how do I plot properly for some (x,y) positions?

[trim fiber]

x and y are str?

[sonic night]

how do i use a list of strings as a key for a dictionary/

the dicitonary is going into a pandas array if there is a better way to do this

[wispy hare]

you can convert it to a string or a tuple

[sonic night]

i figured out a better way to do what i was trying to do

thanks for the help

[wispy hare]

you're welcome!

[sonic night]

how do I append data to a column instead of a row

df["COLUMN INDEX"] = tempdf.iloc[:,3].tolist()

this puts it in a row

I followed what w3 schools did, but thier put it in a row and not a column

oh i see, its making itself a series

can i make the thing stay as a 1d dataframe?

So i'm doing this if first:
first = False
df = pd.DataFrame([stock, tempdf.iloc[:,3]])

    else:
        
        print(stock)
        df[stock] = tempdf.iloc[:,3].tolist()

[sonic night]

think i figured it out

stock and the tempdf thing needed to be swapperd

never mind

it didn't work

[brave oak]

@sonic night #data-science-and-ml would be better, probably

since that's pandas-specfic

[sonic night]

ok thanks

[eager hamlet]

does anyone have like

a good python implementation of hld

[fiery cosmos]

https://github.com/cheran-senthil/PyRival

[pseudo summit]

Hi, I would like to learn data structures and algorithms, can someone recommend me a good (free) resource?

[humble igloo]

Check the pins

[pseudo summit]

Thanks 😅

[atomic kraken]

Hi, I'm having trouble doing a question
The question is basically -

We have to put gears on every peg. Each gear will touch the gear to its right. Find the radius of the FIRST gear such that the speed of rotation of the last gear is half that of the first gear. If this is not possible return -1, -1.```
ping me if you respond please

[balmy kraken]

hello. This is probably a stupid question, but Im trying to wrtie a summation function. I have a coefficent array, C, of size n and want to write the function:

sum (from i to n) C[i]*x**(2/2**i)

Instead of writing C[0]*x**2+C[1]*x**1+(C[2]*x**(1/2))+(C[3]*x**(1/4))+(C[4]*x**(1/8))+(C[5]*x**(1/16))

I could do this in a for loop, but there is probably a one line way of doing this, right?

[wispy hare]

you can use list comprehension + sum() function: sum([C[i]*x**(2/2**i) for i in range(len(C))])

[balmy kraken]

Great, that works! Thanks!

[wispy hare]

you're welcome!

[echo mauve]

Hola, I want to learn data structure suggest in can anyone suggest me good stuff to learn 🙂

[lean glade]

There is a link to an MIT course in the pins

[echo mauve]

tysm

[eager hamlet]

http://www.usaco.org/index.php?page=viewproblem2&cpid=921 so i'm doing this problem
and i found this pretty helpful link: https://cp-algorithms.com/graph/tree_painting.html
however, this one is for painting edges- i have no idea how to paint the vertices in something like O(log n) as is in the problem

that's because even though each edge occurs only once, each vertex can occur multiple times

any help? (ping plz)

[pseudo summit]

I just started with data structures and algorithms, in the first lesson of the MIT course a binary search algorithm is explained to find a peak in an array of positive integers, I understand why the algorithm works, but I can't explain it "formally", can someone help me?

[vestal minnow]

Look up "heavy light decomposition"

i mean there's nothing other than hld here

you're most likely to not find too many CPers here, you might wanna join a cp server for that

[eager hamlet]

oh ok then

[lean dome]

What's the algorithm, specifically?

binary searches belong to a class of algorithms commonly called "divide-and-conquer algorithms". https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm

For a divide-and-conquer algorithm, a formal proof that the algorithm works is generally done using proof by induction: first prove that it works correctly on an empty list, then prove that if it works correctly on a list of size N it will work correctly on a list of size N+1. https://www.comp.nus.edu.sg/~sma5503/recitations/01-crct.pdf walks through this proof for a typical binary search.

[warped bluff]

Hey all, does anyone have good resources for preparing for technical ML interviews? Currently an ML eng at big tech co. I've been using leetcode.com for coding prep for traditional data structures & algorithms, and datascienceprep.com for ML/stats questions, was wondering if anyone knew of others.

[fiery cosmos]

join kaggle

thats the main site for all ml competitions, it has a lot of datasets, some courses and communities too

[pseudo summit]

so in the case of a binary search I'm just breaking down the problem by taking part of the array that will definitely contain a peak, and I can prove that the algorithm works by simply testing it on various inputs, right?

[humble igloo]

Hey so I am having problem understanding Space complexity

def avg(n):
    sum = 0

    for i in n:
        sum += i
    
    return sum / len(n)

print(avg([1,2,3,4]))
```What would the the Space Complexity in this and why?

[worn shuttle]

what kind of formula would give this kind of graph (x can't be negative)

btw is there a tool where I could just draw a line and it would give me the formula for the graph? I know TI-Nspire has that sort of function but that's paid

[oblique panther]

I believe there's "regular" space, and then there's "auxiliary" space.

if you're taking the average of n numbers, you have to have at least n numbers in memory.

But what other memory do you need? It looks like there are only other two other numbers you need to keep track of: the running total (which you named sum) and the total number of numbers, which is given by the len(n) expression.

Note that it's always two extra numbers, no matter how many numbers n is.

It doesn't scale relative to the size of n.

So my guess is that avg has either an O(n) or O(1) space complexity. Because the amount of auxiliary space is a constant.

[humble igloo]

I was learning Big O : I understand that the time complexity is O(n) but I don't get why the space complexity is O(1)

[oblique panther]

for what algorithm?

the average of a list?

[humble igloo]

yea

[oblique panther]

alright, so I guess the space complexity is O(1) because the number of extra memories you need to solve the problem is a constant.

[humble igloo]

Ok

thx

[trim fiber]

cosinus function from 0 to pi/2

[worn shuttle]

ty

[trim fiber]

Or -x^2 + 1 where x is from 0 to 1

[lean dome]

I don't know what "peak" means in this context, and you haven't linked to the algorithm you're asking about, so I can't say.

[lean dome]

Not "is a constant" but "does not increase with the length of the input", to be precise.

[oblique panther]

isn't that what is usually meant by "constant" in the context of discussing complexity?

[lean dome]

Yeah, O(1) is referred to as "constant time" commonly, but what it means isn't that it takes the exact same amount of time for all possible inputs, but that the time it takes is not correlated with the length of the input.

Imagine you've got an algorithm like:

def sleepy(lst):
    time.sleep(lst[-1])

That doesn't always sleep for the same amount of time, but its time complexity is still O(1), because the amount of time it takes is not correlated to the length of the input list.

Same argument goes for space complexity. O(1) there doesn't necessarily mean that all possible inputs need exactly the same amount of space, just that the space required isn't greater for longer inputs.

[agile sundial]

it's O(last_item_in_list) though

[lean dome]

Sure, but when we use O() we generally define N to be the length of the input, and that's what I'm using here.

[agile sundial]

sure

[lean dome]

You're right that the time it takes varies with something, but that something isn't the sequence length, and so it is "constant time" with respect to the sequence length, even though it doesn't always take the same amount of time

[lean dome]

Wikipedia phrases it this way:

the amount of time taken and the number of elementary operations performed by the algorithm are taken to differ by at most a constant factor.
Not that the time is literally constant, but that any difference in time is bounded by some constant

[trim mango]

How would I go about sorting nested lists based on min() of say the 2nd element in the list, example [ ['id1',29]['id2', 36]['id3', 22] ] -> [ ['id3',22]['id1', 29]['id3', 36] ]

[robust trellis]

sorted([['id1', 29], ['id2', 36], ['id3', 22]], key=lambda x: x[1])

[oblique panther]

comparison-based functions like sorted, min, max, etc. have a key argument where you pass a function that will get called on each element. And that function needs to return what value can be used to sort the object it came from.

Often it's going to be a lambda, like in sumedhbala's example.

though it can really be any function.

!e

strings = ['Hi!', 'Apple', 'abcd', 'bOb']
strings.sort(key=str.lower)
print(strings)

[halcyon plank]

@oblique panther :white_check_mark: Your eval job has completed with return code 0.

['abcd', 'Apple', 'bOb', 'Hi!']

[oblique panther]

The strings get sorted in terms of their lower-case form, so 'Apple' doesn't go before 'abcd'.

[wispy hare]

What you want to do is to sort by first attribute (AACG, NWS...) then by second attribute (date)

For example, if we have this array: [(4, 5), (4, 2), (6, 8), (1, 2), (1, 9)] and we want to sort it by first element then by second element, we would write: sorted(arr, key=lambda x: (x[0], -x[1]))

the minus is to sort in descending order, which is what you want to do with your dates

[wispy hare]

and this is what we get [(1, 9), (1, 2), (4, 5), (4, 2), (6, 8)]

now try to find a way to do the same thing with your problem

you can do that ye

[robust trellis]

with open('data.csv', "r") as file:
    lines = file.read().splitlines(True)
    data = lines[1:]
    data.sort(key=lambda x: (x.split(", ")[0], datetime.datetime.strptime(x.split(", ")[1],"%m/%d/%Y"), float(x.split(", ")[2].replace("$",""))))

with open('data.csv', 'w') as fout:
    fout.write('Symbol, Date, Close/Last\n') # adding csv header
with open('data.csv', 'a') as fout2:
    fout2.writelines(data[1:])```

[median terrace]

is there a way to print it, export it to csv just so i could look at it's content easily

[ancient turtle]

What's a good book for learning about algorithms

[fiery cosmos]

well you can just google it but

a) clrs is the bible . The book if you want to learn everything. It has pseudocode
b)sedgewick's book (the C++ one) is also very interesting . The C one is outdated but again both books aren't in not in python so headsup there.

Knuth if you want to learn really really everything

For pseudocode -> code , you can always look up python implementations of the said algorithms !

[ancient turtle]

Introduction to Algorithms

This book?

[fiery cosmos]

yes that is CLRS

yep

[ancient turtle]

It doesn't have anything regarding IDA*, BFS or DFS

[fiery cosmos]

@ancient turtle

it is really hard to say cormen doesn't have "x"

[ancient turtle]

Ah, thanks

[tawdry shard]

can someone help me in solving this problem with Python 3.8? I'm beginner so i can't solve but i want to know solution of this

[north zealot]

Hey @tawdry shard, is that a graded exam?

[agile sundial]

looks like hackerrank?

the green and font

[tawdry shard]

it's like an exercise from my course, and as i said i'm beginner, couldn't solve it so i thought if i asked you guys for help then you can help me

[carmine anvil]

It's a math question more than a python question

Or a DSA question tbh

[tawdry shard]

yeah i know, but the problem is i don't know how can i solve it in python

[neat surge]

Aside from the already mentioned CLRS, another good book is The Algorithm Design Manual by Skiena. The thing I like about it is that it's filled with "real world" examples & applications. Depending on where you're located, you might be able to check it out as an eBook from your local library.

[fiery cosmos]

isn't skiena hard tho

i haven't used it but from what i have seen it is more into the design logic etc

it is good book , yes

[neat surge]

It's not any harder than CLRS, imo.

[trim fiber]

Can you describe some example?

[wispy hare]

aren't you talking about an n-ary tree?

[calm mortar]

Can someone confirm if the time and space here is correct?

[runic tinsel]

sure

uh

_str += char technically isn't constant time

[wispy hare]

adding a character to a string creates a whole new string because strings are immutable in Python

[runic tinsel]

right but like someone benchmarked it and it doesn't behave like that

https://stackoverflow.com/a/34008199/3993379

unpredicatable basically

[calm mortar]

For understanding: that would make the above code snippet quadratic in time and linear in space?

[wispy hare]

better use an array then join

[runic tinsel]

yes

[calm mortar]

this chat was helpful, I shall be back

❤️

[velvet raptor]

How do i get the index of an element in a pandas series if i have the value, like mySeries.index(myVal)

[flat sorrel]

You would be better served in #data-science-and-ml, #algos-and-data-structs is generally for CS stuff

[fiery cosmos]

would someone please help me with a problem? I started learning python 2 days ago and i'm stuck on a homework problem

does anyone know about the vigenere cipher?

[fiery cosmos]

Did you check this https://www.youtube.com/watch?v=SkJcmCaHqS0 ?

[drifting marsh]

Python noob here, can anyone lend me a hand in trying to get a simple program I am working on working?

I'm creating a shopping list generator. I want it to randomly select X number of meals, get the ingredients for making each meal, append them to a list. I have done this part, but now I want the program to sort the shopping list items by category (produce, meat, dairy, etc.). this is where I'm stuck

[wispy hare]

shopping_list = sorted(shopping_list, key=lambda item: item.product)

[drifting marsh]

and I assume I'd need to define what category items belong to, which I am currently trying to do in a JSON file, right?

or is there a better way?

I can share a snippet if it helps

[wispy hare]

yes show please

[drifting marsh]

sure

this is my JSON file that I am using to outline the ingredients for each meal, while also assigning the ingredients to categories

{
    "grilled chicken caesar salad": {
        "produce": ["romaine lettuce", "tomatoes"],
        "meat": ["chicken breast"],
        "dairy": [],
        "grocery": ["caesar dressing", "garlic and herb croutons"],
        "deli": [],
        "bakery": [],
        "frozen foods": []
    },


    "reubens": {
        "produce": ["pumpernickel bread"],
        "meat": [],
        "dairy": [],
        "grocery": ["thousand island dressing", "sauerkraut"],
        "deli": ["swiss cheese", "pastrami"],
        "bakery": [],
        "frozen foods": []
    },```

and this is my .py file, the area where I am stuck I suppose

# determines number of meals to make a shopping list for
number_of_meals = int(input("Enter how many meals: "))

# reads from the JSON file. Creates a Python dict object.
with open('meal ingredients2.json', 'r') as json_file:
  data = json.load(json_file)

# selects a random assortment of meals. The # of meals depends on value of number_of_meals variable above.
meals_selected = random.sample(data.keys(), number_of_meals) 
print(meals_selected)

# for every selected meal, this loop grabs the ingredients needed and compiles a list. The list contains all the ingredients needed for all selected meals to be prepared.
ingredients = []
for item in meals_selected:
    ing = data.get(item)
    ingredients.extend(ing)
print(ingredients)```

[wispy hare]

yes so you need something to know the category of a product

[drifting marsh]

does the structure of my JSON file accomplish that, or no? would this be a good use for classes?

[wispy hare]

wait I didn't fully get what do you mean by sort the shopping list, can you give me an example?

[drifting marsh]

sure

so instead of an unorganized list of things like:

apples
chicken breast
peanuts
toothpaste
dental floss
bottled water
milk
eggs

it's sorted depending on the area of the grocery store they're found in, so:

PRODUCE
apples

DAIRY
milk eggs

PERSONAL HYGIENE
toothpaste
dental floss

so on and so forth

[wispy hare]

yes so you need a dict that contains each product and its category

like in general, not necessary of one specific recipe

then when you have a shopping list, you can organize it by transforming it into a map where the key is the category and the value is a list of ingredients

[drifting marsh]

I see

I will give that a try. Thank you very much @wispy hare for your help!

[wispy hare]

Example:
category_map = {"apples": "produce", "toothpaste": "personal hygiene", "dental floss": "personal hygiene", "milk": "dairy"}

now if you have shopping_list = ["apples", "milk", "dental floss", "toothpaste"]

you can organize it by writing:

for product in shopping_list:
  organized[category_map[product]].append(product)```