algos-and-data-structs

[fiery cosmos]

I enrolled in Learn to Program: The Fundamentals by University of Toronto

should be a good place to start I assume

[half lotus]

You're welcome. Wish you well on your journey to becoming a programmer.

[fiery cosmos]

Thank you! Best to you as well in your endeavors

[median spire]

How do I generate a 16 characters random string without imports?
(out of three lists -> uppercase, lowercase, digits)

[spring jasper]

Why no imports

Just use random

[fiery cosmos]

@valid harness

class ImageTextPair {
    constructor(key, image, text) {
        this.key = key;
        this.image = image;
        this.text = text;
    }
}
class ImgTextDict {
    constructor() {
        this.pairs = [];
    }
    Add(pair) {
        this.pairs.push(pair);
    }
    Find(key_search) {
        for (let index = 0; index < this.pairs.length; index++) {
            if (this.pairs[index].key === key_search) {
                return this.pairs[index];
            }
        }
        return undefined;
    }
    Remove(key_search) {
        for (let index = 0; index < this.pairs.length; index++) {
            if (this.pairs[index].key === key_search) {
                this.pairs.splice(index, 1);
                return index;
            }
        }
        return -1;
    }
}```

I added Remove method

so you can remove any element of dictionary

by it's key

[valid harness]

hm

i'll see how I can incorporate that!

[agile sundial]

what language is that even

js?

[trim fiber]

It looks like JS

[fiery cosmos]

yes

it's JS

the guy had a help channel, he needed help with JS

[agile sundial]

yikes

[fair prairie]

hello

upper bound of T(n), F(n) = O(n), upper bound = number*F(n) is this correct?

[fiery cosmos]

np.full((25, 25), "white", dtype="object")
raises
ValueError: Object arrays cannot be loaded when allow_pickle=False

please ping when you can help

[old rover]

I think this is the wrong place

try #data-science-and-ml

[fiery cosmos]

ok

[harsh timber]

ok not sure

if this is the right place

but

file = open("names.txt", "r")

names = file.read().split("\n")
print(names[0])

so that gives me the first item in the list

how could i seperate it even further

but likke letter

would i go letters = names.split

[grizzled schooner]

to split a string into letters you can cast it to a list (like list(name_of_string) )

there’s no split method for lists

[thin jacinth]

Hey everyone, so Im working on college tasks, and I've been completely stuck on creating a backtracking algorithm. Task goes like this: make an empty list, fill it with 10 random generated numbers, then use backtracking to find smallest whole number which you can add to that list, and it should satisfy condition that the sum of number in a list with that smallest number is dividable by 13.
In general I have an idea what backtracking is, but have no idea how to implement it for this task, if there is any reference on internet to something similar please let me know, as I've been busting my mind for 2 days now. Thanks!
Well seems like writing it down here managed to help me to think better about this algo, looks like I managed to solve it, thanks anyway!

[torpid glacier]

hey, i didn’t really know where to put this. My brain is currently frazzled, I’m thinking of a suitable way to give people a score, based on their score compared to other peoples.

I cant think of one. How do modern day people compare scores!

[spring jasper]

You mean something like an ELO score?

[torpid glacier]

I dont know, Let’s say I have a list of peoples scores. (In this case, Lower is better as its reaction time)
[200, 250, 300]. If the person with 200ms wants to check a leaderboard, i want it to give a rating of their score dependant on other scores

sort of like a percentile, maybe?

[spring jasper]

Ok percentiles are easy to calculate

Just sort the list from small to large and then its some arithmetic

[fathom pilot]

class Graph:

    def __init__(self, vertices):
        """"Initializing graph"""

        self.v = vertices  # Number of vertices
        self.graph = [[0 for column in range(vertices)] for row in range(vertices)]

    def add_edge(self, v1, v2, weight):
        """Adds an undirected edge to the graph"""

        if v1 < self.v and v2 < self.v:
            self.graph[v1][v2] = weight
            self.graph[v2][v1] = weight

    def min_distance(self, dist, visited):
        """Finds vertex with minimum distance from set of vertices
        not yet included in shortest path tree"""
        min_dis = float('inf')
        node = -1
        for j in range(self.v):
            if dist[j] < min_dis and visited[j] is False:
                mis_dis = dist[j]
                node = j
                
        return node

    def dijkstra(self, src, des):
        """Finds shortest distance between 2 nodes in a graph with no
        negative cycle"""

        dist = [float('inf')] * self.v
        dist[src] = 0
        visited = [False] * self.v
        for i in range(self.v):
            node = self.min_distance(dist, visited)
            visited[node] = True
            for v in range(self.v):
                if dist[node] != float('inf') and self.graph[node][v] > 0 and visited[v] is False and \
                        dist[v] > dist[node] + self.graph[node][v]:
                    dist[v] = dist[node] + self.graph[node][v]

        return dist[des]

this piece of code for Dijkstra's shortest path algorithm for adjacency matrix representation of graph only works when the src > des

for some reason and Im not sure why

It gets the right distance when src > des but when the other way around it throws some other number

does anyone know why? im confused

[hollow needle]

hi i need a python function that implements matrices multiplication with divide and conquer using Block Partitioning

[limber fog]

prod_name = {}
for item in page['items']:
    name=[item['item_basic']['name']] 
    id=item['item_basic']['shopid'] 
    seller=['https://shopee.co.id/shop/{}'.format(id)]
    images = ["https://cf.shopee.co.id/file/{}".format(img) for img in item['item_basic']['images']] 
    prod_name['name']=name
    print(prod_name)

why does this code print like this https://paste.pythondiscord.com/vexufewuqi.lua
instead i want in one single line

huft i dont know what to say

what i really want is to be like this

[fiery cosmos]

Hello everyone, does someone have some information on the matplotlib.pyplot.animation library ? I need this for a school project. Thanks !

[vocal gorge]

WDYM by information? That library has docs.

[fiery cosmos]

I'll look for that, thks

[uneven jungle]

Need help with dfs

travsering

[agile sundial]

what do you need help with

[uneven jungle]

pm

[agile sundial]

no

it's better to keep things in the server

ok, and what issue are you having

[uneven jungle]

It's really hard to tell, but Im guessing im not reaching the right leg

of the tree

[agile sundial]

send code?

[uneven jungle]

I'd like to keep it in concept if not pm

[agile sundial]

what

[uneven jungle]

so first i move left as far as possible

[agile sundial]

why not send code?

[uneven jungle]

if i reached the bottom (L and R = None)

I move up

to parent, and then right

and then left

[agile sundial]

I don't think there's an issue with understanding, but with implementation

thus I can't help without seeing code

[agile sundial]

look, whatever your aversion to sending your code and letting other people see it, it's probably unfounded. no one cares about your code, no one's gonna judge you for it, and definitely no one's gonna steal or

[uneven jungle]

@agile sundial

[agile sundial]

!code

[halcyon plank]

Here's how to format Python code on Discord:

```py
print('Hello world!')
```

These are backticks, not quotes. Check this out if you can't find the backtick key.

[agile sundial]

why do you have nested loops?

[uneven jungle]

it's just a dummy

[fiery cosmos]

i think they are thinking of going to lowest left child first

[uneven jungle]

yes

[agile sundial]

right, but you don't need to nest loops fot that

[fiery cosmos]

also why while True?

and that without any breaks

[uneven jungle]

?

ok, im happy with knowing that I don't need this

because it's not working

leaves me in your place, void 🙂

[agile sundial]

I don't know what that means, but you can simply do one operation per iteration of the outer loop. either move left, move right, or move up

[uneven jungle]

ah right

hmm ok, that helped a bit, at least it did stop

[agile sundial]

one of your issue is that you're potentially doing more than one operation per iteration, and they might be out of order

[fiery cosmos]

this will work i think i mean some issue may arise.

[agile sundial]

it's not helpful to send solutions

[fiery cosmos]

ah alright

deleted

[agile sundial]

we want to help them, not just give them solutions

[fiery cosmos]

Also @uneven jungle as this is a tree, i don't think you need to manage visited.

[uneven jungle]

hmm true

[fiery cosmos]

we need visited in graphs usually as it's a tree, its fine i think.

my bad i directly sent solution :' )

[agile sundial]

he doesn't know when he has moved up in the last iteration so he does need it I think

you'd be stuck moving between two nodes

[uneven jungle]

yes that was some initial problem

[fiery cosmos]

exactly. as much i can see, i don't see much reason to move up if i manage a stack.

[agile sundial]

he's not managing a stack

[fiery cosmos]

oh alright

alright, keep the .visited, as you're implementing in this way, however, look out for that
while True, if there is no precise reason, remove it.
if there is reason, break it on precise condition.

[uneven jungle]

yes, I have that part so it's perfectly fine in that way

ok, thanks

[candid holly]

what did i wrong?

can pls help someone

having_acc = input("Do you already have an account: ")
if having_acc == "yes":
email_exist = input("Email: ")
if email_exist in open("email.txt"):
print("This email is registered. Now please enter your username.")
else print("This email is not registered. Try again.")
username_exist = input("Username:")
if username_exist in open("Username.txt"):
print("This username is correct. Now please enter your password.")
password_exist = input("Password:")
if password_exist in open("Password.txt"):
print("Welcome back!")

[uneven jungle]

The Else is indented bad

Should be om same level as if and with : after

But this is not an algo question

Go go reglular help

[lavish flint]

Hey hope everyone is doing well. But of a numpy/pandas algo here going on

I have an issue that shouldn't be this difficult; I have a list of 3 million + flight records, simple takeoff and landing data. I have found and assigned an ID to each row corresponding to what "trip" I have assigned it to (there can be multiple rows per trip, if each row is the same aircraft and the conditions of each row match the parameters of my parent functions). For each OD_OD (as I am calling them), I am trying to take the cumulative concatenation of the landing airports. I have a one line piece of code to do this, however it is running extremely slow for large records and I think I need an alternative approach.

Starting data:

OD_ID    Arrival_Airport
1    LAS
2    BFI
3    PDX
3    BFI
4    YYJ
4    BFI
4    YUM
4    LTO
5    YUM
5    YYJ
5    BFI
5    PDX
5    BFI

then, my algorithm runs this code in one line:

pddf['cumu_path']=[y.Arrival_Airport.to_numpy()[:z+1] for x, y in pddf.groupby('OD_ID') for z in range(len(y))]

which yields the correct column 'cumu_path'

OD_ID    Arrival Airport    cumu_path
1    LAS    LAS
2    BFI    BFI
3    PDX    PDX
3    BFI    PDX,BFI
4    YYJ    YYJ
4    BFI    YYJ,BFI
4    YUM    YYJ,BFI,YUM
4    LTO    YYJ,BFI,YUM,LTO
5    YUM    YUM
5    YYJ    YUM,YYJ
5    BFI    YUM,YYJ,BFI
5    PDX    YUM,YYJ,BFI,PDX
5    BFI    YUM,YYJ,BFI,PDX,BFI

How can I make this more efficient? I have the option of transposing my entire model/application into a spark format and deploying it on one of my company's clusters, but that would be a lot of rework and I'm so close with where I am at.

EDIT: It is important that cumu_path is yielded "triangularly" as it appears above for a next-step that detects loops and adjusts for a new ID (the very last row has a loop, BFI)

[vocal gorge]

Perhaps a more naive function with a @numba.njit decorator would be faster? And in general, maybe profiling that listcomp (on a smaller slice of the data, to make it take only a few seconds) will yield some insights.

[lavish flint]

I think you're right, and after typing it I started experimenting with moving this requirement upstream in my entire process. I think that due to my inexperience sometimes I forget that if you can't solve something in python, go upstream and try to solve it in SQL

Also --- I haven't been imaginative enough to come up with a way to do computations in njit that allow my result to be string concatenations (I have been able to succeed in doing simple string operations by replacing strings with identifiers, but when the concat requirement comes in that sort of broke down on the drawing board)

[slim egret]

Given an array of numbers varying from 50-100. Write an algorithm to make best sub arrays whose sum is equal to or near 1000, also find how many such sub arrays are possible?

[lavish flint]

I dont know the answer but is there an assumption on the distribution that your data has? IE normal uniform etc

i suppose it doesnt matter hence the problem

[slim egret]

non uniform

just random numbers between 50-100

non negative numbers

[fair prairie]

What is upper bound F(n)=n^2+3

[vocal gorge]

what makes you think this function has an upper bound? It goes to infinity as n does.

[fair prairie]

Then I saw it on goolge once

Google*

Can you pls tell me what can be F(n) be

I mean ik it can be 2n or 3n + something

Other than that? @vocal gorge

[vocal gorge]

...what makes you think 2n is bounded?

[fair prairie]

Nothing

I learnt that in video

But I think I m wrong

[agile sundial]

maybe he's talking about time complexity? @vocal gorge

[fair prairie]

Algorithms analysis

Ig

[vocal gorge]

quite possibly

[fair prairie]

I m confused

[fiery cosmos]

O(n^2) is the likely answer desired. O(f(n)) or "big oh" of some function f is the upper bound on how that function grows as n increases

[royal cliff]

Hello, I would like to make a class and a contructor with arbitrary parameters. Is this possible in python? something like the following:

class UwU:
  a=1
  b=2
  c=3
  d=4
x=UwU(c=7,b=22)

how can I make something like this?

[lean dome]

check out https://docs.python.org/3/library/dataclasses.html

[royal cliff]

that works, thanks 🙂

[fiery cosmos]

Use init function

[lean dome]

dataclasses provide an init function by default

[drifting drum]

Hey there!
How would you solve this

You're given an array of integers, you can reduce each number to one of its divisors (greater than 1, that is you cannot reduce it to 1).

After doing this as many times as you want on every number,
you need to find the minimum possible difference between the resulting max and min elements in the array
for example, [6,16,27] can be reduced to [3, 2, 3] and then the diff is 1

Constraints are that array's size can be upto 10^5.. so it's probably needs some sort of sorting, perhaps heap.. but idk haha

One Idea I have is like a greedy + heap thing..
I store the minimum element in my array. Then maintain a maxheap,
Every iteration, pop the maximal element, do ans = Math.min(ans, maximal element - minimal element), then reduce the maximal element if possible and push it back. Repeat this until uh, till the maximal element is equal to the minimal element or something.. hm.. haha not too sure

[fiery cosmos]

I feel making a heap over-complicates it

Map all the numbers to their lowest non-1 divisors, sort the result O(nlogn), find minimum difference from there subtracting neighboring elements O(n)

[shut breach]

what about a large prime and a large prime -1

[fiery cosmos]

Ohh but what if some other divisors have a smaller min diff, yeah

or large nums

Then I'm not sure

[shut breach]

isnt this equivalent to finding the prime factorization of the entire list

[jolly mortar]

what is the best complexity for finding all the factors of a number

exponential?

[shut breach]

i believe it is sub-exponential

[solemn nimbus]

who can help

me how to do algebra?

in python?

[fringe wave]

can anyone help me, i want to make a chating group

i can send messages to the server now but theres a problem

help in dm

[fathom pilot]

Does anyone have any source online or any source code for Dijkstra's shortest path algo for graph (adjacency matrix)?

[vocal nymph]

use sympy lib

!pypi sympy

[halcyon plank]

sympy v1.8

Computer algebra system (CAS) in Python

[fiery cosmos]

https://pastebin.com/mCbZE2Gc

i think lru_cache might be magic

the lru_cache'd function performed 20x faster than the tuple lookup in this case

[snow sphinx]

Hi

I need some help in practicing numpy

I was practicing numpy and got stuck here
ValueError: cannot reshape array of size 8 into shape (4,4)

R1 = 4
C1 = 4

R2 = 4
C2 = 4

print("Enter the entries in a single line (separated by space): ")

# User input of entries in a
# single line separated by space
array1 = list(map(int, input().split()))
array2 = list(map(int, input().split()))

# For printing the matrix
matrix1 = np.array(array1).reshape(R1, C1)
matrix2 = np.array(array2).reshape(R2, C2)

prod = np.multiply(matrix1, matrix2)

it is multiplying 2x2 arrays but not above that
why?

[spring jasper]

This is more appropriate for a general help channel #❓｜how-to-get-help

You should also mention what kind of input you gave and what kind of output you expect to get for that input

[fiery cosmos]

is they bytecode generated by dis.dis() 1:1 with the assembly language it will be compiled to?

[vocal gorge]

Assembly language? WDYM by that?

The bytecode shown by dis is the lowest-level form Python code gets compiled to.

[fiery cosmos]

well i have this weird thing

oh wait really?

oh does it mean that because its what the python interpreter eats?

[vocal gorge]

Yup

Python isn't a compiled language, it doesn't get compiled any further than this.

Unless you're using something like PyPy, I suppose

[fiery cosmos]

at some point it becomes assembly or else how would the computer?

well so i learned this today

that its faster to create a variable for the class method

but why 🤔

[uneven jungle]

you access the class -> method, or the direct adress of the method?

[fiery cosmos]

ohhh hmm

wow

[uneven jungle]

like you can import dis from dis

[vocal gorge]

Suppose I write a long instruction for you to execute, and you do it. At which point do sploshes of ink on the paper become electrical impulses in your brain? Would it be important for me to know what impulses are generated to debug the instructions? 🙂
The bytecode is read by the interpreter, which does certain stuff for each instruction it gets. It's not very productive to try and figure out how exactly that's done.

[fiery cosmos]

is each instruction called on like a clock tick?

so if u have 5 instructions its always better than 10

[vocal gorge]

Even CPUs don't do an instruction per clock AFAIK, but no, nowhere close.

[uneven jungle]

depends on their dependencies

some are better than others

[fiery cosmos]

wow

[fiery cosmos]

when i see the ink

[vocal gorge]

The interpreter is an actual C program just, like, reading the instructions and doing stuff based on them.

simple example: a C program that reads a string, increments a counter for each character it reads, and returns the values when the string is done

does it perform a single CPU instruction per character (just because the character is an "instruction" in that case)? Definitely no, feel free to investigate how many, but probably quite a bit (loop control, actual +1 operation isn't one instruction either, etc)

[fiery cosmos]

interesting

i suppose hmm

thanks for helping, its hard to google what you don’t know what to google for haha

[hot valley]

Hi can you help me with this? I have a device conected to RS232 and I am getting these data : \xe0\x8e\x1c\x9e\xe0\xe0\xf0\xf0\xe0\xfe\xfcp\xf0\xfcp\xfe\xfcp\x80\x1c\x0e~8\xc7\xfc\xf0\x00\xe0\x8e\xe0\x8e\x1c\x8e\xe0\xe0p\xf0\xe0\xfe\xfcp\xf0\xfcp\xfe\xfcp\x80\x1c\x0e~8\xc7\xfcp\x0e\xff but my output should look like this: 32765|04=3.9|05=0.4|06=107.0|07=2.626|08=-32765|09=65.5|10=-32765|11=-
32765|12=0|13=40|14=-32765|15=65.5|16=-32765|17=-32765|18=-32765|19=-
32765|20=21.0|21=-32765| . How can I encode?

[austere sparrow]

When you look up a method like that, you have to:

1. look up the testclass global variable (which could've changed its value in the meantime)
2. look up the method method on the object (which could be looked up with some dynamic logic, otherwise it's just a dict lookup)
3. call the method

But if you save the method as a local variable, it's just:

1. look up a local variable (which is faster than looking up a global, because global lookup is basically dict lookup)
2. call the method stored in it

generally less instructions = faster, but it's not always true

[ancient sonnet]

Hi, does anyone know what efficient algorithm with the time complexity less than O(n3) means?

[jolly mortar]

Are you asking what a time complexity of O(n^3) means?

[sturdy drum]

How can I keep floats from going past the hunderedths like a=232322691.023 be equal to all of it's whole numbers but decimals only .02(tenths and hundredths)

[grizzled schooner]

you can use the round() function. or do some weird integer division stuff if you want to truncate, not round

[sturdy drum]

so I could round to .02?

[grizzled schooner]

(in the future, #python-discussion might be a better channel for this type of question, but it's not a big issue)

[sturdy drum]

Sorry and thx

[grizzled schooner]

yep. round() takes two arguments, the first one is the float that you want to round and the second is the number of decimal places you want to round to

[sturdy drum]

yep round(a,2) worked like a charm.

[grizzled schooner]

great!

[ancient sonnet]

Yes

[fiery cosmos]

It means that in a worst case scenario the algorithm would take time proportional to the cube of the size of the input

Like an O(n^3) algorithm for n = 10 could take (proportional to) 1000 steps

But if it was O(n^2) only 100

[ancient sonnet]

Alright thanks

[pastel bronze]

hello guys I am new to data structure and algorithms can anyone help me to skill up this thing.

[fallen shoal]

❀

[unborn sundial]

!e

from types import SimpleNamespace
dict_ = {
    "data": 456,
}
sdict = SimpleNamespace(**dict_)
print(sdict.data)

[halcyon plank]

@unborn sundial :white_check_mark: Your eval job has completed with return code 0.

456

[unborn sundial]

!e

from types import SimpleNamespace
dict_ = {
    "data": 456,
}
sdict = SimpleNamespace(**dict_)
print(sdict.data)
sdict.data = 123
print(sdict.data)

[halcyon plank]

@unborn sundial :white_check_mark: Your eval job has completed with return code 0.

001 | 456
002 | 123

[unborn sundial]

!e

from collections import namedtuple
dict_ = {
    "data": 456,
}
Custom = namedtuple('custom', dict_)
ndict = Custom(**dict_)
ndict.data
print(ndict.data)

ndict.data = 789
print(ndict.data)

same but read only

[halcyon plank]

@unborn sundial :x: Your eval job has completed with return code 1.

001 | 456
002 | Traceback (most recent call last):
003 |   File "<string>", line 10, in <module>
004 | AttributeError: can't set attribute

[unborn sundial]

!e

from types import MappingProxyType
dict_ = {
    "data": 456,
}
rdict_ = MappingProxyType(dict_)
print("r = " + str(rdict_['data']))
rdict_['data'] = 123

pure read only dictionary, should make my data more secure

[halcyon plank]

@unborn sundial :x: Your eval job has completed with return code 1.

001 | r = 456
002 | Traceback (most recent call last):
003 |   File "<string>", line 7, in <module>
004 | TypeError: 'mappingproxy' object does not support item assignment

[half lotus]

Secure from what?

Trivially circumvented by doing dict_['data'] = ...

[unborn sundial]

secure from by accident changing values

I'll just wrap to return read only object dict from my function

to be sure that after that the object will remain unchangeable

[brave depot]

!e
from types import SimpleNamespace
dict_ = {
"data": 456,
}
sdict = SimpleNamespace(**dict_)
print(sdict.data)
sdict.data = 123
print(sdict.data)

[halcyon plank]

@brave depot :white_check_mark: Your eval job has completed with return code 0.

001 | 456
002 | 123

[subtle quiver]

can anyone help me with class inheritance?

[unborn sundial]

funny enough I have coworker Alex who is struggling with class inheritance too 😉

[old rover]

https://youtu.be/RSl87lqOXDE

Schafer really is goated tbh

[snow sphinx]

Can someone help me in a Matrix problem?

[fringe wave]

can anyone help me with sockets (i want to make a chatting-server with multiplie clients)

im stuck at sending the message to every connected client

[trim fiber]

Check pinned messages on #networks

[drifting drum]

Hey there, I asked this question earlier but well didn't really get much going.. trying my luck out again

How would you solve this

You're given an array of integers, you can reduce each number to one of its divisors (greater than 1, that is you cannot reduce it to 1).

After doing this as many times as you want on every number,
you need to find the minimum possible difference between the resulting max and min elements in the array
for example, [6,16,27] can be reduced to [3, 2, 3] and then the diff is 1

Constraints are that array's size can be upto 10^5.. so it's probably needs some sort of sorting, perhaps heap.. but idk

(Also discretegames, I did read your approach and like Scofflaw was able to point out, it's flawed, unfortunately).

[fiery cosmos]

Yeah. Scofflaw was right

And seems right when he said it is (at least bounded by) finding the factors of all the numbers

plus sorting it I guess

[shut breach]

yeah (thought I added this, but guess I forgot) it's even worse since finding all the prime factors does not immediately give you the proper factors to use

[halcyon plank]

Hey @ancient junco!

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

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

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

https://paste.pythondiscord.com

[ancient junco]

available with the ratios of 1:2:3 and 3:7:1, respectively. By mixing those two
solutions together in the ratio 1:2, it is possible to obtain a solution of the m = 3
components with ratio 7:16:5, but there is no way to combine these two potions
together into a new one with ratio 3:4:5. However, if the witches nd another
potion with ratio 2:1:2 (making the problem into one where n = 3), then a 3:4:5
mixture is possible with eight parts of 1:2:3, one part 3:7:1, and 5 parts of 2:1:2.
So clearly, determining which mixtures can be obtained from a given set of
potions is not trivial. It is your goal in this assignment to do so.
3 Input/Output
The top line of the input le (input.txt) will be a line with a desired ratio in
the form a1 : a2 : a3 : : : : : am. The next n lines will be the base solution ratios.
Your output le (output.txt) will consists of n lines, each containing a single
integer. These will indicate the parts necessary to get the desired ratio. If no
combination is possible, then return the value 􀀀1 on each line.
1
So, for example above, the input le (input.txt) would look as follows:
3:4:5
1:2:3
3:7:1
2:1:2
and the output le (output.txt) would look as follows:
8
1
5```
anyone know how to implement this, i think i have to use matrices and determinants, but im not sure

plz PM or DM me

[odd steppe]

I'm honestly not even sure where to start... is this binary recursion?

Two words are blanagrams if they are anagrams but exactly one letter has been substituted for another.
Given two words, check if they are blanagrams of each other.

Example 1
For word1 = "tangram" and word2 = "anagram", the output should be
checkBlanagrams(word1, word2) = true;
After changing the first letter 't' to 'a' in the word1, the words become anagrams.
Since a word is an anagram of itself (a so-called trivial anagram), we are not obliged to rearrange letters. Only the substitution of a single letter is required for a word to be a blanagram, and here 't' is changed to 'p'.

Example 2
For word1 = "aba" and word2 = "bab", the output should be
checkBlanagrams(word1, word2) = true.

Example 3
You can take the first letter 'a' of word1 and change it to 'b', obtaining the word "bba", which is an anagram of word2 = "bab". It is also possible to change the first letter 'b' of word2 to 'a' and obtain "aab", which is an anagram of word1 = "aba".

Example 4
For word1 = "silent" and word2 = "listen", the output should be
checkBlanagrams(word1, word2) = false.
These two words are anagrams of each other, but no letter substitution was made (the trivial substitution of a letter with itself shouldn't be considered), so they are not blanagrams.



[execution time limit] 4 seconds (py3)

[input] string word1
A string consisting of lowercase letters.
Guaranteed constraints:
1 ≤ word1.length ≤ 100.

[input] string word2
A string consisting of lowercase letters.
Guaranteed constraints:
word2.length = word1.length.

[output] boolean
Return true if word1 and word2 are blanagrams of each other, otherwise return false.```

[stable pecan]

i would start with just counting letters

[fiery cosmos]

Count letters in both words with e.g. collections.Counter. Then loop over all letters for each. If exactly 2 letters differ by exactly 1 they are blanagrams.

Linear time with word length

[fiery cosmos]

how?

[drifting drum]

yeah but like I still don't understand what to do after finding factors?

suppose if the array was [80,81] the answer would be 1 itself

which means the count has to be calculated at every stage of factor elimination for every number

and the constraints are 10^5 so I really can't do it whatever brute-forcey way I can think of

[dire nebula]

is there a way for me to like assign a dummy value to variable?
like

something = -1
int = somethingdummyvalue
if int < something:
    int = something; //because int just have a dummy value

[civic anvil]

Dummy value? I just started Python...I can only help you on a "Dummy level" 😋

[trim fiber]

You shouldn't assign your values to names like int, str

[dire nebula]

yeah I know it just pop into my head so wrote it down 😅

[trim fiber]

Okay, but I still don't know what is a "dummy value"

[jolly mortar]

conventionally I think you'd just set it to None
and use if int is None or int < something: for the check

[austere sparrow]

That's IPython

[worn jungle]

Anyone got an easy to understand guide on parsing? Preferably in text form 🙂

[exotic veldt]

Anyone how can I find the solution for this

I'm trying this. But getting errors

[muted yoke]

can i go to jail for giving someone a virus?

[austere sparrow]

Yes you can, but not sure how it's related to algorithms and data structures

[muted yoke]

wait

can i go to jail for giving a pedophile a virus

[muted yoke]

e

and then getting more info on the dude

[austere sparrow]

Yes, you can go to jail for attacking a murderer, a pedophile, Hitler, Satan, etc., just like you will go to jail if you randomly kill a pedophile. It's the job of the police.

anyway, it's off-topic here.

!ot

[halcyon plank]

Off-topic channels

There are three off-topic channels:
• #ot0-psvm’s-eternal-disapproval
• #ot1-perplexing-regexing
• #ot2-never-nester’s-nightmare

Their names change randomly every 24 hours, but you can always find them under the OFF-TOPIC/GENERAL category in the channel list.

Please read our off-topic etiquette before participating in conversations.

[rotund yarrow]

I need an idea on how to solve the following task ||my current score is 13k words, but I'm completely stuck on it||:

You have a list of about 150k words
You need to find biggest list of words such that the last two letters of previous word are same as first two of next word

(no you don't have to find the longest, your result is number of words in a chain you managed to find)
Yeah, that's it

[finite fulcrum]

for starters, create a test case list for yourself..
like for example:

lst = ['abcd', 'cdef', 'efgh', 'ghij', 'ijkl', 'klmno', 'nopqrstu']

then, figure out how to extract first 2 letters and last 2 letters of any element (Hint: slicing)

iterate over the list of elements one by one by

[rotund yarrow]

yeah I did all that, did DFS in both ways from starting word with some minor optimization and I'm stuck at 13 000 words

[finite fulcrum]

ok, then I didn't understand the problem I guess..

[rotund yarrow]

well, that's a bit low number

I want to optimize the algorithm

to get 20, maybe 25k

but I don't have any idea how

[finite fulcrum]

what is this 13k limit you are talking about?

we cannot store the list in the memory ?

[rotund yarrow]

well, it really goes nowhere from there

I can leave it running for hours and it would still be at 13k

[finite fulcrum]

like the program stops running after the first 13000 words, instead of processing the whole 150000 ?

[rotund yarrow]

it doesnt stop running, it's just super hard do find a better branch i guess

[finite fulcrum]

so when you say, "hours" ?

like you mentioned you can leave it running for "hours"...

[rotund yarrow]

I tried

it gets to 13k in 20 sec

or less

it will not get stuck at exatcly 13k

the other bracnhes will fluctuate around it, +-20 words

[finite fulcrum]

okay, so, this is like a deep learning question?
I thought that the list was already present in a sequence, and we just needed to identify the longest sequence..

[rotund yarrow]

my current code goes forward braching words searching using DFS, the order is to go first to ones that have most possible words to attach to them as next nodes, when reaching the end of branch, I continue that branch but from starting node in opositi direction, adding words that can go before starting... both ways it can manage to get about 6.5k per way

it means my search goes for example like this:
abcd
abcd cdef
abcd cdef efgh (let's say this is end of branch)
jkab abcd cdef efgh
ghjk jkab abcd cdef efgh

[finite fulcrum]

lst = ['abcd', 'cdef', 'efgh', 'ghij', 'ijkl', 'klmno', 'nopqrstu']

this is what I thought the list was like

[rotund yarrow]

nah, it's just a long list of words

[finite fulcrum]

but it seems like we need to generate the list ourselves

[rotund yarrow]

https://shaolin.dev/rijeci.txt

this is wordlist

about 160 000 words

alphabetically sorted

[finite fulcrum]

wow this is interesting.

[rotund yarrow]

My solution is half the result of current highscore which is about 25 000 words

[finite fulcrum]

I think someone with deep learning xp should try helping you further..
I don't have the necessary skill set at this point..

although, I will try to learn how we can do this over the next weekend for sure

[rotund yarrow]

I don't think this has anything to do with deep learning but thanks anyway

[finite fulcrum]

right..

see I don't even know the correct term 🙂

[fervent saddle]

So it’s not about consecutive words? It’s just about how many words start or end with different pairs of letters?

[finite fulcrum]

yea

[rotund yarrow]

yeah

[finite fulcrum]

I think NLP might help then?

like fuzzy finding words?

maybe not..

what is this "branching" you were referring to?

[rotund yarrow]

oh I have one dict of each pair which contains all words that start with that pair and for reverse I have dict containing all words that end with that pair

[finite fulcrum]

this is why I was thinking of deep learning..
because I remembered this "Alpha Go" AI by Google.. which uses alpha-beta cut-off for finding the best solution..

[timber agate]

hey guys! i am new to this but i came here to learn how to do this, could you guys teach me?

[rotund yarrow]

yeah that's what I'm doing, I'm not looking for a solution because I already have that, i'm looking for the optimal solution

There is nothing I can cache / dynamic programming as far as I see, as the words can't repeat so based on branch I choose the whole rest of branch is different

[fiery cosmos]

yes

heres ur options

• https://projecteuler.net
• https://leetcode.com
• school
• algorithm book

oh yeah also - youtube

[spare fog]

Welcome! This seems like a super helpful community so I think you will be well taken care of. Some advice though: if you show that you've put some thought / effort into problems before you ask for help, it will make it a lot easier for others to actually help you

[shut breach]

welcome! here's a collection of resources compiled by this community

!resources

[halcyon plank]

Resources

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

https://pythondiscord.com/pages/resources

[shut breach]

and if you come across specific python questions, we have an individual help system #❓｜how-to-get-help as well as these domain-specific channels

[tiny river]

In [9]: flag
Out[9]: '灩捯䍔䙻ㄶ形楴獟楮獴摟潦弸弰摤捤㤷慽'

In [10]: ord(flag[0])
Out[10]: 28777

In [11]: bytes(flag[0], 'utf8')
Out[11]: b'\xe7\x81\xa9'

How is the 28777 calculated from the bytes of \xe7\x81\xa9 ?

[lean dome]

!e https://en.wikipedia.org/wiki/UTF-8#Encoding

byte1 = 0xe7
byte2 = 0x81
byte3 = 0xa9

bottom_6_bits = byte3 & 0b00111111
middle_6_bits = byte2 & 0b00111111
top_4_bits = byte1 & 0b00001111

print((((top_4_bits << 6) + middle_6_bits) << 6) + bottom_6_bits)

[halcyon plank]

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

28777

[lean dome]

the shifts are because the middle 6 bits are to the left of the bottom 6 bits, and the top 4 bits are to the left of the middle 6 bits.

[fiery cosmos]

does any1 know how to do treaps in java

if so dm me pls

[solar timber]

How would you find the nth term of a Fibonacci word?

Starting from the first term, and then going on doesn't work, since the value of n can be quite large, is there a dynamic programming way?

[keen hearth]

Hey, so can you explain to me what a Fibonacci word is?

Ah right, a word formed by repeated concatenation.

And you want to compute the nth fibonacci word?

[thorn storm]

Can you use memoization technique like with the numbers?

[keen hearth]

I mean, if n is large then the word is going to be very large.

But if you're looking for the ith character of the nth fibonacci word, perhaps there's a more efficient way to find this.

If you know the length of the n-1th fibonacci word, you know whether to look for the ith digit in that word or in the n-2th word.

[keen hearth]

Then you can recur from there.

[tawny nest]

hi hi ..is there a good backtesting python library to test a strategy,.. I have come across a few on net but not able to use them directly..will appreciate any help

[solar timber]

I think we're looking for the n th character of the Fibonacci word

[solar timber]

Nope, that would be too long

Fibonacci Word

[runic tinsel]

can't you calculate the length from scratch for every step

if you have log n steps, and each time you find the previous fib in log n, that's pretty fast

def fibword(n):
   a = 0
   b = 1
   while a+b < n:
      a,b = b, a+b

what am i supposed to do with this lol

oh, so you never want the previous word, you jump to pre-previous

return fibword(n-b)

doesn't work tho

def fibword(n):
   if n < 3:
     return n % 2
   a = 0
   b = 1
   while a+b <= n:
      a,b = b, a+b
   return fibword(n-b)
```ok this does

as a loop it takes 30 seconds for 10**4400

probably can do 10**10000 within 6 minutes

[lean dome]

Doesn't Wikipedia just have the formula for this?

[runic tinsel]

yeah, it does

O(1) is boring

[lean dome]

O(1) is the only solution that will work for 10**100

[runic tinsel]

why

[lean dome]

Well, maybe not that in particular, but at some point you'll reach the limits of your memory

[runic tinsel]

what memory

[lean dome]

In your case, the call stack

[runic tinsel]

you write it as a loop

it's only time bound

[lean dome]

As written, it shouldn't even be able to handle n=1000, at least in CPython - but you're right, it could be done iteratively in constant space

[solar timber]

Why do we subtract b from n?

[runic tinsel]

basically after n-th letter where n is a fibonacci number, the word just repeats from the beginning

0 1 0 0 1 0 1 0 0 1 0 0 1 
  x x   x     x

x says start reading from the start

so we find the largest fib we can subtract

and subtract it

[runic estuary]

Hey guys, if a red black tree contains the maximum number of nodes possible: what would the general structure look like?

[meager chasm]

how do you write like this?

[runic tinsel]

```
text
```

[meager chasm]

hi

shiiiish

thx

[fiery cosmos]

triple backticks will make a new code-block. Single will be inline in text like so

[solar timber]

Okayy, thanks a lot!

[scarlet wadi]

testing this

[sinful nacelle]

https://www.spoj.com/problems/BUGLIFE/

there can never be odd edge cycle

usong graph collor technique

def bfs():
currcolor=color[1]
curr=1
for index,nodes in enumerate(adj):

    if index>=1:        
        
        for node in adj[index]:
            if color[node]==currcolor:
                return False
            if color[node]==-1:
                color[node]=1-currcolor
               # currcolor=color[node]
                curr=node
        currcolor=color[node]
return True

for asd in range(int(input())):
adj=[]
n,m=map(int,input().split())
n+=1
color=[-1]*n
for _ in range(n):
adj.append([])
for x in range(m):
a,b=map(int,input().split())
adj[a].append(b)
adj[b].append(a)
color[1]=1
a=bfs()
print("Scenario #",asd+1,":",sep="")
if a==False:
print("Suspicious bugs found!")
else:
print("No Suspicious bugs found!")

Can someone help me what is wrong with this code

[jovial tartan]

can someone help explain how exactly counting sort actually sorts things? learning it right now and it just seems like pure black magic fuckery, i'm really, really struggling to get an intuition on how we're supposed to use the count of a key to sort by the key's value
thanks!

[shut breach]

take your input, and put each item on the number line

then, scoop them up off the number line in order

voila, linear

@jovial tartan

[snow sphinx]

Need heelllpppp

I need some help

n = 6
mtx1 = []
print("Input elements as per rows: ")

for i in range(n):
   y = []
   for j in range(n):
      y.append(int(input("Input elements: ")))
   mtx1.append(y)

for i in range(n):
   for j in range(n):
      print(mtx1[i][j], end=" ")
   print()

def check():
    if (mtx1[i][j]==1)%2==0:
        print("even")
check()

User must input only 0s and 1s every row
It should display the matrix and print whether every row and every column have an even number of 1s or not.
I'm blank. completely. I have only wrote the code of making the matrix. It displays it but I can't display whether a row or a column has even 1s or not

[subtle quiver]

can someone help me with decoders?

[fiery cosmos]

maybe you just gotta be more specific @subtle quiver

[unique pecan]

how do i call an async method (not in any method or class)

[lean dome]

That's a better question for #async-and-concurrency - but asyncio.run() may be what you're looking for

[unique pecan]

says I need to await it...

idk... asyncio.run(resultUI())

[lean dome]

You don't need to await asyncio.run() - if you got an error about needing to await something, it must have been something in resultUI()

[sinful nacelle]

This one pls

[odd steppe]

I'm still confused about the difference between double and single linkedLlist

[lean dome]

a singly linked list only contains links from each node to the next one.

a doubly linked list contains links from each node to the next one, and from each one to the previous one.

[solemn nymph]

Hi, I am pretty new to complex DS, got a question. I got a question, is it worth converting bulk data of Lists or (and) Dicts (from some api or stored in a DB etc) into a more complex DS; in a scenario where you need speed and memory efficiency or is it okay?

[half lotus]

It can be worth it sometimes, but it depends on the use case

If the data is used a lot, then it can be worth it to eat the upfront cost of converting it into another structure.

[analog wadi]

!Ping

[halcyon plank]

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

[serene oracle]

the data itself is going to play a big role in how you use it... a 50MB file versus a 20TB hive table are going to be treated differently.... or a deeply nested JSON versus a flat CSV. I think it's a good practice to make sure your input data is properly pre-processed before trying to use it (but I'm also biased since that is a big part of my day job)

[austere sparrow]

@serene oracle your cat has gone wild

(unless you're intentionally spamming)

[keen hearth]

Excuse me? 😄

Key stuck?

[austere sparrow]

they probably really like object-oriented programming

in which case #software-architecture is probably the right channel

[white pelican]

how to get muted speedrun edition

[unborn sundial]

any efficienct way to write __repr__ for class?

[keen hearth]

This can be the only conclusion.

[keen hearth]

Hey, what kind of data structure does it represent?

[vivid girder]

line 1, in <module>
from PyQt5 import QtCore, QtGui, QtWidgets
ModuleNotFoundError: No module named 'PyQt5'

help

[grizzled schooner]

you have to install it using pip

[unborn sundial]

class
more precisely db model in Django

with multiple django db model attributes

[unborn sundial]

I think I have an answer

There is information about attributes in meta fields

It can be used to make auto made repr perhaps

[worn jungle]

is "i" used often in while loops for any particular reason or is this just the type of rule people have used over time out of habit?

[leaden rampart]

just a habit

because it is convenient

[worn jungle]

similar to how strings are usually expressed using "a" and "b"

[leaden rampart]

yew after all it is a dummy variable

[worn jungle]

Thanks was just wondering

[austere sparrow]

if a name doesn't have a particular meaning (like student_count or timeout_ms) and it's a local variable, it's fine to use a 1-letter variable name for it

although with for loops, there's almost always a better way than iterating over an index

[leaden rampart]

yes exactly

[worn jungle]

That's what I thought, pretty new to programming so just always looking for answers 🙂

[agile sundial]

i -> index ¯_(ツ)_/¯

[grand kettle]

guys i've got a problem with a basic code . Given a dictionary with {key:name and value: message} i need to find the messages that have the same words even not in a specific order. I need a simple answer with no use of function. I can provide the code that i 've done

[balmy crown]

hi, basic question. I have a string that is returned from a post command that I receive like this: '{'{"command":"relay","token":null,"channel":null}': ''}' and my brain is struggling to pull out the dictionary with the name value pairs. Help!

[lean dome]

Looks like that's JSON, so you'd parse the string into a Python dict using json.loads()

[stark plank]

Hi all, does anyone know why {}.update({}) returns None instead of {}? Is there some algorithmic reason for this? I would have expected the invariant my_dict.update({}) == my_dict to always be true.

[balmy crown]

didn't work - it complains that json.loads only works on strings, bytes etc - not dictionaries

[agile sundial]

it modifies the dictionary, it doesn't return the new one

[stark plank]

amazing, thanks

[lean dome]

You said you had a string, but if you have a dict then something already decoded it from JSON.

[agile sundial]

from a post command right? you're using requests?

[balmy crown]

yeah, sorry. I am receiving it from a POST and converting it to a dict (I thought I could work with that better)

yes on the post and requests...

[fervent saddle]

Is it possible to make arbitrarily large Tetris O(1)? I was thinking about it, and I had an idea which I think would be O(1) during the game, but it involved using linked lists so I thought it might not be the best way. I also couldn’t think of how you could reload the game without setting all the grid spaces to a default state.

I’m thinking there must be people who have thought about and came up with something about this, but I couldn’t find anything on Google. All I could find was something talking about the complexity of playing Tetris.

The idea I had was for the grid to be represented by a linked list, and each node represents a row. Each node has an array of booleans, whether True or False counts as a filled space, and the count of how many spaces are filled

And when the row is filled, it’s removed and put on the end of the linked list, and filled_count is set to 0 and counts_as_filled is set to !counts_as_filled
EDIT: Someone said you can just use a normal array where each thing says another index in the array where the neighbor node is, and you just switch those around. So it seems like that’s how to avoid linked lists

[rocky ibex]

does a module that tells me if a string is literal or numeric exist ?

[vocal gorge]

what's a literal or numeric string?

are you perhaps looking for str.is_digit or str.is_numeric (IIRC)?

If you want "does that string convert to an int/float right", just try it and except the ValueError.

[sage coral]

I'm thinking about learning the MCTS algorithm, and trying to implement it into chess. Any recommendations on what I should learn/know before I start?
*I have a pretty solid understanding of python, a basic understanding of data structures & algos, and an intermediate understanding of AI and NNs

[jolly mortar]

(no underscores in the name)

[loud trail]

@brisk saddle this might belong in #unix 🙂

[honest mantle]

#help-lemon

[brisk saddle]

oh shit, i am sorry i thought this was in #ot0-psvm’s-eternal-disapproval actually.
@loud trail

apologies

[fiery cosmos]

maybe some basic heuristic search algorithms like A*, best first. It can give you a basic idea of search methods

[copper forge]

Hello

Can someone help why I am Getting this error

Traceback (most recent call last):
  File "main.py", line 127, in <module>
    MessageDecrypt()
  File "main.py", line 93, in MessageDecrypt
    MainDecryptionKey = base64.urlsafe_b64encode(input())
  File "/usr/lib/python3.8/base64.py", line 118, in urlsafe_b64encode
    return b64encode(s).translate(_urlsafe_encode_translation)
  File "/usr/lib/python3.8/base64.py", line 58, in b64encode
    encoded = binascii.b2a_base64(s, newline=False)
TypeError: a bytes-like object is required, not 'str'

Anyone?

[vocal gorge]

Not really the right channel for this question. The error tells you exactly what's wrong, though - that function works with binary data, and you're passing it a string. You likely want to use .encode("utf-8") to encode it before passing it to the function.

[copper forge]

Ok then where should I ask?

[vocal gorge]

In a help channel, see #❓｜how-to-get-help.

[fiery cosmos]

Hello I need help

[vocal gorge]

Unless it's about #algos-and-data-structs, see #❓｜how-to-get-help too.

[cloud moth]

i don't understand anything in this algol.
https://spinningup.openai.com/en/latest/algorithms/vpg.html#pseudocode

[honest mantle]

#help-carrot am doing sudoku solver using backtracking, can anyone spot the mistake in the code?

[mystic steppe]

so if you pu 9786% of10345% then thats appel juice

[fiery cosmos]

ima need help guys https://github.com/CorentinJ/Real-Time-Voice-Cloning/issues/609 how am i supposed to export the embedding output?

🤷‍♂️

i used the demo_toolbox

[wispy hare]

yes show

[fiery cosmos]

odd discovery, for some reason on 3.7 OrderedDict is 2.1% faster than a normal dict for lookups

[fervent saddle]

It has to check what index to go to in a different array with regular dicts, maybe that’s why

[vocal gorge]

that sounds pretty insane, what did you test it on?

[fiery cosmos]

tested on win 10

hw is zen 2, 3990x

[fervent saddle]

Do ordereddicts do the same thing that regular dicts started doing in 3.6?

Where they use a second array?

[fiery cosmos]

they're pretty much identical to dicts nowadays, but the code is still the separate implementation that was written for collections

why was dict ordering made the default anyway though?

seems like it causes a lot of problems

or could cause a lot of problems

[fervent saddle]

They were optimizing it and that was just a side effect

[fiery cosmos]

neat that clears it up

[fervent saddle]

And you weren’t supposed to rely on ordering in any way before, so it shouldn’t make any difference

[fiery cosmos]

yeah, but doesnt it break comparison

[fervent saddle]

I guess maybe it might make it slower, and they might just say “that kind of thing it what sets are for”
Actually, it seems like it might be faster since iteration is faster in new dicts since it doesn’t have to go over as much empty space.

But someone with more knowledge on this might have a better answer

[fiery cosmos]

no i mean like two dicts wont compare equal if the values were inserted in a different order

something like that

[fervent saddle]

They should be able to compare as equal by searching for each key in one dictionary in the other

[fiery cosmos]

nah, its not that. they still compare equal

there was something else that broke

huh, i guess there was no issue with it

[fervent saddle]

But yeah I wonder why looking up from OrderedDict is faster than regular dict

[fiery cosmos]

probably just a lot more rules governing dict

[fervent saddle]

And I wonder if OrderedDict uses the same 2 array optimization that regular dict uses

Because if it doesn’t, if it only uses one array, that might be the reason why

[lean dome]

OrderedDict inherits its __getitem__ from dict. It can't be faster, it's the same method.

[fiery cosmos]

it consistently beats it

and in the dll there are seperate ODict functions

my guess is that its a different path dispatched from the getitem code for dict, python uses dynamic typing, which means functions may accept two objects of different types

[lean dome]

ah, you're right - there's an _collections.OrderedDict that takes precedence over the Python OrderedDict implementation if it's available

[fiery cosmos]

oh ok

ignore my condescending dynamic typing message

jumped da gun

if it were just a little faster it could provide FAST INTEGER ADDITION

alas

[lean dome]

what's your test case?

[fiery cosmos]

excuse me while i mash undo

[lean dome]

https://github.com/python/cpython/blob/3.7/Include/odictobject.h#L30 - PyODict_GetItem is just another name for PyDict_GetItem; even the C implementation just inherits this from dict

[halcyon plank]

Include/odictobject.h line 30

#define PyODict_GetItem(od, key) PyDict_GetItem((PyObject *)od, key)```

[fiery cosmos]

https://pastebin.com/FJRUR7XL

there has not been a single run in which normal dict has won

ignore the naming

i was trying to find a faster way to look up stuff to replace integer addition

(im high as a kite, its true)

[lean dome]

you should try to simplify that a bit before trying to reason about the performance differences... there's a lot going on there, heh

[fiery cosmos]

what exactly needs simplification

the bound methods?

[lean dome]

what's functools doing here? Why do you need randomness?

[fiery cosmos]

randomness shouldnt matter, they both have the same random keys

its just so i dont have to type out 2000 unique keys by hand

[lean dome]

I just tried running this on 3.8, and the second timeit was faster

[fiery cosmos]

yeah

same result then

oh yeahh

i just found the FASTEST INTEGER MULTIPLY

in python

9% faster than actually multiplying, ladies and gentlemen...

[lean dome]

then I reversed the two prints, and... the second was still faster.

[fiery cosmos]

https://pastebin.com/dwKbhUFP

oh really

cache should be factoring in there, im creating two different dicts

*shouldnt

1 sec

[lean dome]

could be the garbage collector, could be something about what winds up in the cache, or locality of reference...

[fiery cosmos]

1.325711
1.2938629999999998
1.3207377999999999
1.3194084999999998

and now reversed...

alright, increasing the number of iterations done makes the results more consistent

also do gc.collect and freeze beforehand

ODict still wins

[lean dome]

well, whatever effect you're seeing, it's not ODict being faster, because it can't be - ODict subclasses dict, and doesn't override getitem.

it is the same method that you're timing.

[fiery cosmos]

okay, ODict isn't faster, it just performs better

ODict isn't faster, timeit just prints out a smaller time for it.

glad thats settled

[lean dome]

something is performing better, but it isn't OrderedDict.__getitem__, because it cannot be, because OrderedDict.__getitem__ is dict.__getitem__

!e ```py
from collections import OrderedDict
print(OrderedDict.getitem is dict.getitem)

[halcyon plank]

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

True

[fiery cosmos]

yes, but the implementation of dict.getitem is likely aware of ODict

[lean dome]

ctrl-f for odict in https://github.com/python/cpython/blob/3.7/Objects/dictobject.c and you'll see it doesn't have any special cases for it

it just calls dk_lookup, and - ctrl-f for dk_lookup in https://github.com/python/cpython/blob/3.7/Objects/odictobject.c and you'll see that ODict doesn't override that, either.

Timing stuff is hard - so far, I think it's much more likely that the difference in times isn't attributable to differences in what __getitem__ does, but to some other effect that's getting picked up.

[fiery cosmos]

well, at least i've pioneered fast python multiplication

what i dont understand is how is what you're saying the case, given that odict uses a different data structure from dict?

[fervent saddle]

It sounds like it uses the same things for looking up a key

It does something different for iteration

But looking up a key involves the same steps as a normal dict, right?

[fiery cosmos]

eh yeah i guess all the other stuff is built around the base dict and the other tables/lists are for the ordering

did a pool map with 128 processes and it lucks like its random with a large sample set

[lean dome]

yeah - ordered dict has a normal dict's hash table, plus some extra stuff for maintaining an ordered list of keys that is used when iterating

[iron swallow]

Hello everyone
I have tried to implement stack using linked list node

Few methods of stack class are not working

Can someone help me to find out what the problem is

The code can be found out at
https://replit.com/@BanarasiVaibhav/FrostyUpsetCleantech#main.py

[agile sundial]

looks like your size method works

your top method could be fixed by simply using the same check in your pop method

@iron swallow

your display method is messing with the self.head pointer, it is actualyl modifying it to point to the bottom element

that's not what you want

[iron swallow]

Pop method is not working

It shows that the stack is empty even when it has elements

[agile sundial]

no, pop method works

your display method doesn't

[iron swallow]

Ohh thanks I got your point

Let me correct my display method first

And then see what else is needed

Thanks @agile sundial

Now it seems that everything is working as it should work

Without you pointed out I could have never figured it myself

Thanks for valuable les

Thanks for valuable lesson

[odd steppe]

does anyone know about that algorithm question about brackets and Stacks in python

[agile sundial]

like, validate if a string of brackets is valid?

[fathom whale]

Open a help channel if you need help

[scenic goblet]

https://codeforces.com/problemset/problem/1138/A how to apprach ?

[subtle aurora]

Anyone have a 10crop feature in imaging?

[fringe pasture]

!code

[halcyon plank]

Here's how to format Python code on Discord:

```py
print('Hello world!')
```

These are backticks, not quotes. Check this out if you can't find the backtick key.

[languid jacinth]

!code

[halcyon plank]

Here's how to format Python code on Discord:

```py
print('Hello world!')
```

These are backticks, not quotes. Check this out if you can't find the backtick key.

[languid jacinth]

print('Hello world!')

[idle pumice]

Hello everyone I want to learn the full begining course of python

[pearl umbra]

Here is a good starting point:

!resources

[halcyon plank]

Resources

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

https://pythondiscord.com/pages/resources

[idle pumice]

Thank you so much enimus

[woven heart]

hello guys i have just finished learning core python can anyone please recommend any video courses on data structures using python

[old rover]

you can try the MIT OCW course it's pinned on the channel

you may also like the Udacity Python data structures/algos course but it's in Python 2.7

[woven heart]

anything on udemy i am new to programming

so please guide me

[vernal birch]

@woven heart I would recommend this course on Udemy I'm really enjoying this course on Udemy and think you might like it too.
https://www.udemy.com/share/1025QIB0UfcltVRQ==/

[woven heart]

thanks

[fiery schooner]

Guyysss i need to start with data structures using python. Can anyone recommend any good udemy or course courses for basic to advance.

[dark goblet]

@woven heart for just starting out, check out "100 days of Code" by Angela Yu. Its highly rated, im taking it myself and really enjoy it, and its beginner friendly .

[lean junco]

Why does softmax function when used without hidden layer classify data using boundaries that are only straight line ?

[loud trail]

@lean junco softmax doesn't "classify" anything. it just takes a vector and normalizes it so that the elements sum to 1 and each element is between 0 and 1

understanding why a "neural network" with no hidden layer is just a linear model is a great homework exercise

also this belongs in #data-science-and-ml

[fiery schooner]

I mean I've done python till intermediate level. I know numpy pandas and matplotlib too.
But i need to start with data structures in particular. So if someone has any good course please recommend it to me!

[dark goblet]

@fiery schooner oh my mistake, it looks like i misread a comment

[celest kiln]

Not sure if this fits here but, does anybody happen to have a snippet I can borrow that mimics the x86 rol instruction? I'm reversing some malware that's decrypting a payload but it's rotating the key by 7 bits on each iteration. My attempts have failed and various copy/paste attempts have failed. First byte decrypts fine but as soon as I rotate the key, we're way off, has to be an inaccuracy in how these rol implementations are written.

[brave oak]

huh

like...bitwise rotation?

[celest kiln]

@brave oak correct

[lean dome]

how many bits is the value that's being rotated?

[lean junco]

Yeah thank you .....though the homework is what i wanted to ask😅
But i think now i want to figure out myself

[lean dome]

It should just be this:

val = 0b01001010010010100101001001010010

for i in range(32 + 1):
    lo = (val >> 32-i)
    hi = ((val << i) & 2**32-1)
    ret = hi | lo
    padding = " " * i
    print("{:02d} {:032b} {} {:032b}".format(i, ret, padding, ret))

the output of that is https://paste.pythondiscord.com/rurufajefa.yaml - the first column is the number of bits the original number has been rotated left by, the second and third column are both the original number rotated by that many bits, but the third column is padded by extra leading whitespace so that each value stays in the same column as it was in before shifting (so that you can see that the values in a column are the same throughout, other than being shifted by some offset)

[arctic field]

wa

[halcyon plank]

Hey @fiery cosmos!

It looks like you tried to attach a Python file - please use a code-pasting service such as https://paste.pythondiscord.com

[fiery cosmos]

why its not working?

[fiery cosmos]

Can we hack nasa by using python

[runic tinsel]

unknown

hacking is doing something weird that isn't supposed to be possible

as soon as you know if something can be done, that's not really hacking

[languid jacinth]

!code

[halcyon plank]

Here's how to format Python code on Discord:

```py
print('Hello world!')
```

These are backticks, not quotes. Check this out if you can't find the backtick key.

[fiery cosmos]

Hacking is more like playing with model train sets

[empty trout]

do you know anything as effective as range, but exponentially?
such as range with step x2

[lean dome]

That's trivial to define yourself if you need it

def exp_range(start, stop=None, factor=2, /):
    if stop is None:
        stop = start
        start = 0
    while start < stop:
        yield start
        start *= factor

[misty light]

Although with a start of 0 that's not going anywhere

[loud trail]

🙂 write out the equations for both models. you might see a surprising resemblance.

[lean junco]

yes i saw instructor saying they are similar

heard

[arctic nebula]

leeddddddddddddzzzzzzzzzzzzzz goooooooooooooooooooooooooo

grubuma sıçayım

[worldly osprey]

i just made a path finding script using A* Algorithm and it was pretty fun now i want to try and implement other algorithms too but im out of ideas any suggestions what i should make?

[main flower]

Find bridges/articulation points in a graph

[worldly osprey]

oo sounds interesting, ill give it a read since i dont really know what do you mean by bridges/articulation points in a graph

[hoary bronze]

is it only for me or do you guys also think the api docs was easier to follow before

[empty trout]

how to write "in" magic operator?

[agile sundial]

i believe it's __contains__

then if that's not defined it just iterates and checks equality i think

[remote quiver]

Can someone help me find the bug in my code, I'm very confused
I'm solving: https://leetcode.com/problems/path-sum-ii/

class Solution:
    def dfs(self, root, sum_so_far, list_so_far, targetSum):
        if not root:
            return
        sum_so_far += root.val
        list_so_far.append(root.val)
        left = self.dfs(root.left,sum_so_far,list_so_far, targetSum)
        right = self.dfs(root.right,sum_so_far,list_so_far, targetSum)
        if not left and not right and sum_so_far == targetSum:
            self.ans.append(list_so_far) # WHY DOESN'T THIS UPDATE
            print(list_so_far)
        list_so_far.pop()
        return 1 # Have to return something to go back in the stacktrace
    
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        self.ans = []
        self.dfs(root, 0, [], targetSum)
        print(self.ans)
        return self.ans

I don't understand why self.ans.append doesn't update to hold the correct ans

Please do tell me if this isn't the right place for this

[halcyon plank]

Hey @bleak ether!

It looks like you tried to attach a Python file - please use a code-pasting service such as https://paste.pythondiscord.com

[bleak ether]

Is a python set sorted? like when I convert a set to a list do I get sorted elements? Now I know it's false. But when I run the following script, after a few iterations it gives me a 'sorted set'? and a sorted list when converted? How is this happening? Am I triggering some inbuilt function unintentionally? If yes what is that function? what is it's time complexity?

[halcyon plank]

Hey @bleak ether!

It looks like you tried to attach a Python file - please use a code-pasting service such as https://paste.pythondiscord.com

[bleak ether]

from random import randint

please_sort = set()
while True:
for _ in range(5):
please_sort.add(randint(1, 20))
print(*list(please_sort))

[grizzled schooner]

sets are unordered

[bleak ether]

I dont know how to paste a code here... sorry about this

[bleak ether]

I read that but this script is converting the random numbers into a sorted list after a few iterations

sorry there is no stop in the while loop... I was debugging it to figure out what's happening so I never added one

[agile sundial]

elements are inserted into the set (the underlying array, really) into indices calculated by the equation index = hash(element) % table_size. since in python, integers hash to themselves, this gives the appearance of a sorted order. @bleak ether

you can see this is the case by running this

L = ['hey', 'yo', 'tada']
H = [hash(x) % 8 for x in L]
print(H)
print(set(L))

you'll see that strings in the set are not sorted, but ordered by the list H

[bleak ether]

okay that makes sense, so for large sets this might not always give a sorted array but for smaller lengths we get one? but it's still unclear so as to why during the first few iterations the set is unsorted? the table size is too small? something like that?

[agile sundial]

!e

from random import randint
s = set()
for _ in range(5):
  for _ in range(5):
    s.add(randint(1, 20))
  print(s)

[halcyon plank]

@agile sundial :white_check_mark: Your eval job has completed with return code 0.

001 | {3, 4, 13, 6}
002 | {3, 4, 6, 8, 13, 14, 16}
003 | {3, 4, 5, 6, 8, 13, 14, 16}
004 | {3, 4, 5, 6, 8, 9, 11, 13, 14, 15, 16}
005 | {2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15, 16, 20}

[agile sundial]

ah yeah, because 13 % table_size < 6 % table_size

i believe the starting table size is 8, so 13 = 5 mod 8, and 6 = 6 mod 8

@bleak ether

and when the table is "resized", the elements are copied to a larger array, so elements could be inserted in a different order

[bleak quarry]

How can I access kwargs?

Example:

chatterbot = ChatterBot("name", discord_message=message)

print(chatterbot.discord_message)

[agile sundial]

this isn't really suited for #algos-and-data-structs , but there is no guarantee that you can access it afterwards. for example

class A:
  def __init__(a=None):
    pass
t = A()

[bleak ether]

Thanks a lot! that perfectly clears my doubt.

[fervent saddle]

What’s it called when you make all the lines of a big text file the same length so you can seek to a specific line, or when you do something similar to that?

[mint jewel]

the general format is a flatfile database

[fervent saddle]

Like when you’re doing the same kind of thing that an array does, but you’re doing it with something in storage

Alright thanks

[mint jewel]

though it is very rare these days, since you can just use sqlite instead

Cobol uses these very often though

[vocal jolt]

hey I'm starting to learn DSA and thought it will be easy to do it in python, so can anybody suggest me some refrence books or courses?

[onyx lodge]

my question is
Check to see if a string has the same amount of 'x's and 'o's.
and why do my code

def xo(s):
    xn=0
    on=0
    n=len(s)
    for x in range(1,n):
        if s.lower() == "x" :
            xn+=1
            print("xn + 1")
        elif s.lower() == "o" :
            on+=1
            print("on + 1")
    if xn == on:
        return True
    elif xn!=on:
        return False

dont work?

help:(

[agile sundial]

walk through your code one line at a time until you find the mistake

[lean dome]

Try it with short strings, like 1 or 2 characters, and watch that gets printed

[red palm]

Does anyone have any experience with weighted reservoir sampling? Or something similar? Something that can iterate through a list once, and then pick a random item, accounting for weighted probabilities?

[lean dome]

that sounds like a description of https://docs.python.org/3/library/random.html#random.choices

[red palm]

Seems kind of like that, except that would need to iterate multiple times to do what I need, as far as I can tell. If I have a .txt with random weighted names like

John, 100
Bob, 100
Xenthor, 1
Henry, 75
and so on, I'd need to go through the whole list once to separate it into population and weights, then run choices on a second pass, yes? My understanding is that reservoir sampling can pick a random line on the first pass.

[lean dome]

ah, yes. But, if the list is small enough that you can fit it in memory, saving the extra pass doesn't seem terribly worthwhile.

[red palm]

Yep

[lean dome]

I haven't heard of reservoir sampling before, but it does look like it could do it in one pass.

[agile sundial]

is that the "pick a random number from an infinite stream algo"

[lean dome]

but all that saves is some O(1) operations - at least, assuming you have enough memory to store the whole list.

[lean dome]

yep, seems like.

actually - not infinite, just arbitrarily large

I think it still needs one full pass

if I'm skimming Wikipedia correctly 😄

[agile sundial]

ooh, right yeah.

[red palm]

Yes: arbitrarily large because it still needs to reach the end of the list/stream/whatever before it can make a pick. There is reservoir sampling, but then also weighted reservoir sampling, which is what I'm looking for (same thing but with weighted probabilities attached). Seems to be pretty scarce information, though :/

[robust path]

Why is quicksort used more than merge sort in professional development ?

[agile sundial]

is it?

[robust path]

That is what I have heard, at least?.?.

[agile sundial]

from where? source?

python's sort uses a hybrid mergesort. the same algo is used by a few other langs too, like java

[fiery cosmos]

yeah its O(nlogn) but its mix of two.

[fiery cosmos]

I'm not sure if quicksort is used more in pro dev or not but technically quick sort has less complexity in best case, while in merge sort its always O(nlogn).

also here's some info about what algo python uses. Its Timsort. hybrid of merge sort and insertion sort.
https://stackoverflow.com/questions/10948920/what-algorithm-does-pythons-sorted-use which public static void said.

[robust path]

I was watching the efreecodecamp beginner algorithms and data structures video on Youtube. The person compared the two and said that quicksort is used over a merge sort a lot in professional dev.

[robust path]

Alright. That is pretty much what I found from https://www.geeksforgeeks.org/quicksort-better-mergesort/

[fiery cosmos]

alright but as much i know, if data is big, professions are gonna prefer O(nlogn) first, and java and py and js(not 100% sure) rely on them as O(nlogn) is exceptionally less.

[robust path]

Yup, makes sense

[agile sundial]

that's not really a consideration. in practice, quicksort impls are never gonna be O(n^2)

the main issue is that quick sort is not stable

[winged scaffold]

is introduction to algorithms and data structures a good book for beginner?

not a complete beginner though, i'm asking because heard a lot of em say it requires some advance math knowledge

[vocal jolt]

@glacial berry thank you so much 🙌

[robust path]

I am going through MIT right now

[agile sundial]

i like it, but you're right that it heavily math oriented. it's very rigorous

[meager slate]

i want to know why there are memo hits in a memoized knapsack? it is not clear to me where the same array will be encountered later down in the recursive calls since in each recursive call you decrease the lenght of the array and the target weight is different for them. thanks!

[wispy hare]

the weight isn't always different

If we have weights = [7, 5, 2, 6] and max weight = 20, at i = 2, we could have taken the first element only, or the second and the third one

in both cases, the remaining weight would be 13, we get the same recursive call

[meager slate]

ah gotcha!

[empty trout]

when should i use map() Instead of loop? for perfomance

[vocal gorge]

When it'd look nicer.

For performance? map isn't much faster than a normal loop - it's only faster for simple functions, probably because it uses different flow control or something. Usually it doesn't really make a difference.

[placid bluff]

yo

[lime ice]

hi, I had a discussion with somebody about data structures

he said i can easily use an ordinary list to mimic stack or queue

Is it right to do so rather than using libraries or creating my own implementation of them

[vocal gorge]

stack - yes, no problem with that. Queue - would be a very bad idea, as pop/insert into the beginning of a list is O(n), not O(1) like in a proper queue.

Note that collections.deque exists providing a proper deque.

[lime ice]

there was actually someone else who said it is not recommended to use a list as queue or stack in any production level project

[vocal gorge]

There isn't really a reason to use a list as a stack when deques exist, but I think the complexity is the same.

[lime ice]

ok thx

[onyx root]

on the other hand, lists are great at being stacks, so there's no reason to use a deque

[agile sundial]

of course, if the entire point is to create an implementation of a stack or queue, using a list+append/pop kind of defeats the purpose a little

[lean dome]

Does it? If you were creating your own queue class in a language with manual memory management, you'd probably do it by creating a dynamic array to back it

[onyx root]

I think @agile sundial 's point is that you don't learn much about the mechanics of stacks by using a list.

[lean dome]

I think that assumption is wrong. Production quality queues are implemented in terms of (one or more) dynamic arrays, and Python doesn't give you a way to make your own dynamic array, so you're pretty much forced to use list in your implementation

Or implement it in terms of a linked list instead, which will be worse and slower and less like a real world queue

[agile sundial]

hmmm. ok, i retract my statement. i agree with godlygeek

[onyx root]

it depends what the learning exercise is meant to teach

[fiery cosmos]

This is what I thought too until I read godlygeek's comments and researched a bit. You can have a dynamic array queue and the trick is you never shift it, rather let it circle around to the start and keep track of head and tail. https://stackoverflow.com/a/37220350

I always thought Queues and LinkedLists went together since there no shifting needs to happen.

[vocal gorge]

so it works as long as it's finite-sized?

ah, right, you can also add in the end if needed

[lean dome]

You can detect the full condition and copy into a new, larger ring buffer

[fiery cosmos]

Well a dynamic array can append in O(1) on avg, right

yeah

[agile sundial]

yes

[night cove]

I made a simple code that go through a string and appends matched words and the the not matched

it's that a simple algo, right? my question is if complex algos its a bunch of simple ones

[agile sundial]

lots of algos will use ideas from simpler algos if that's what you mean

[worldly osprey]

im trying to implement the recursive division maze generation algorithm (http://weblog.jamisbuck.org/2011/1/12/maze-generation-recursive-division-algorithm) but im getting stuck at one of the main parts, i cant figure out how to find the largest portion of the grid to divide, like say my grid is 10x10 and my starting random point is at (4, 6) now from here how do i find out the largest portion that exists withen this divided grid

any ideas how i can implement this

[mossy forge]

anybody know how to implement bloom filters?

[chilly acorn]

why would that be?

[chilly acorn]

take a look at this, I've done a similar thingy in the past https://github.com/erlete/search_algorithms (pathgen file)

[serene mango]

but I think the complexity is the same
You mean the complexity when using a list instead of deques, would be the same?

[worldly osprey]

Ahh ok I'll take a look at it, thanks

[chilly acorn]

for some reason, it is slow as hell for big arrays, but it stops generating a smooth path if I touch anything

:S

[wispy hawk]

i know heap is not for searching but i want to know how come searching in heap has complexity O(n), isn't it O(logn)? anyone can explain me?https://stackoverflow.com/questions/2372994/search-an-element-in-a-heap

[worldly osprey]

Oo I made a pathfinding algorithm a while back using A* and it works pretty fast considering how inefficiently I wrote every, but that may partly be due to the fact that the creation of boundaries was manual and left to the user

[chilly acorn]

that's so nice, I'm working on a backtracking method for explored nodes

the pathfinding method is also really fast, but the slow part is the whole array wall-avaliable_to_path structure random generation

but anyway you gotta be random if you wanna determine the true potential of your algo

[worldly osprey]

true thats why i decided to take on the task of making a maze generation thingi for it, im pretty new to algorithms but its so fascinating to get something to work

[agile sundial]

why do you think it is log N?

[fiery schooner]

Guyss does anyone have list comprehensions pratice problems?

[agile sundial]

i think hackerrank has one, but i doubt you'll find many explicitly asking for list comprehensions. you'll typically use them as part of a larger solution

[subtle dock]

can someone help me?

[trim fiber]

What's up?

[subtle dock]

i need help with my repl

[trim fiber]

What is the problem?

[wispy hawk]

sorry, i mixed up - heap(without sorted) and heap(after sorted). I got the ans

[sudden cobalt]

wheres chat

[sage coral]

Anyone have resources for learning how to use a Monte Carlo tree search? Both for it itself and for other things related. I have a decent understanding of data structs & algos, have done things like A* and minimax, and I've done some basic neural nets. However, I've never done reinforcement learning or something a bit more complex like this. Any help would be appreciated 😄

[rich bluff]

Hi how can I store a large sized variable in memory as I am getting an out of memory error

[keen hearth]

Are you taking part in a certain bot programming competition right now by any chance? 😄

[wraith valve]

How to do this problem in a reasonable amount of time
https://adventofcode.com/2020/day/10#part2 (essentially a "coin flip" problem but with different parameters)
Essentially what I have right now is some recursive algorithm that continuously checks a subset until i hit the end or i cant go any further. Thing is I get the right answer for input size of 11 and 31 but my input size of 93 takes forever to run.

[keen hearth]

@sage coral Erm, if you have access to Russell & Norvig AI 4th edition, there is a chapter on MCTS. There's also this lecture series on reinforcement learning from the people that made AlphaGo: https://www.youtube.com/watch?v=ISk80iLhdfU&list=PLqYmG7hTraZBKeNJ-JE_eyJHZ7XgBoAyb

[keen hearth]

Hey 🙂 Have you done any dynamic programming problems before now?

[wraith valve]

nope lol

[austere sparrow]

What data do you need to store?

There are generally two possibilities:

1. You don't need to store it all at once, and you can process it in chunks (e.g. item by item)
2. You really can't store it in memory, so you'll have to store it on disk (and perhaps load chunks of it in memory)

[keen hearth]

Alright, so think about the adapter with "joltage" j. Working backwards from the device (which has joltage max(joltages) + 3), can you figure out how many ways there are to stack adapters so that the last adapter you add is j? What previously computed values (computed for adapters with joltage k such that k > j) could you use to calculate this value?

[wraith valve]

oh i think i see

[rich bluff]

its a large json object, by storing in the disk did you mean storing it as a file

[wraith valve]

u dont actually go generate all the valid combinations and count them

[keen hearth]

Yep, as there might be a very large number of valid combinations.

@wraith valve Once you solve it, you can compare with my solution, if you like: ||https://github.com/lxnn/advent-of-code-2020/blob/main/day-10/p2.py||

[wraith valve]

i think everybodys input is different?

ima not click but i think thats not the value right cuz thats real long

[agile sundial]

solution still works though

[austere sparrow]

where do you get a JSON file so large you can't store it in memory?

[agile sundial]

json db

[rich bluff]

I am filtering a large log file with regex and after the process I have to store it in the database as a jsonb object or as a json file in cloud, I am using celery

[keen hearth]

Ah, it's a link to the github repo containing my solution (python program) 😄

[austere sparrow]

is the file a single JSON document? or is every single line a JSON object?

can you give a snippet?

[rich bluff]

the code is not available with me now

[wraith valve]

@keen hearth oh lol

[sage coral]

Nope, I am not

[keen hearth]

Oh right nvm. Well check out the resources I mentioned anyway 👍

[rich bluff]

I am iterating through a log file in a function, if regex pattern matches with the current line of the file that line is stored in a list. this list is returned and stored in a variable. that variable is further processed for some other info and the result is stored as a jsonb object in db or a json file in cloud based on the size of the data

[sage coral]

I’ll definitely check out the deep mind course, that looks great 😁. Do you know any way to get that book for free 😅

[keen hearth]

I do not, and I wouldn't recommend that. You can rent a digital version of the book from VitalSource.

It's relatively low cost to rent. The physical textbook is quite expensive unfortunately. It's a very recently released edition.

[sage coral]

Alright, thanks for the help!

[austere sparrow]

So:

• you have an unstructured log file
• you parse this log file with regex
• you want to do something with it afterwards
• the result of parsing doesn't fit in memory
  correct?

[rich bluff]

yes

[austere sparrow]

!e
Then you can lazily process the file. Instead of storing the result in memory, perhaps make a generator.

import re

def things(source):
    for match in re.finditer(r"(\d)", source):
        yield int(match[1])

logs = "foobar1baz2bizbiz3fffffff4ggg"
for thing in things(logs):
    print(thing + 38)

for example, read the file line by line (that's what iterating with for over a file object does) and yield something on each line.

If the file is so large, why do you want to store it as a single json object as a single value in a database? That seems painful to work with. Maybe you should store it as a table in an SQLite database, so that you can query it easily?

[halcyon plank]

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

001 | 39
002 | 40
003 | 41
004 | 42

[rich bluff]

I think storing in a jsonfield in postgres is ok?

or storing as a file in s3

[austere sparrow]

well, it's so large you can't fit it in memory, as you said. is it, like, 1 gigabyte large?

If you store it as a plain json file, you won't be able to query it, right?

[vocal gorge]

For a stack, yes. (for a queue you'd need to implement it as a ring buffer as in <#algos-and-data-structs message>).

[austere sparrow]

although in postgres you can do manipulations in json

IIRC

[vocal gorge]

Why a list has O(n) pop/insert in the beginning? Because all other elements need to be shifted by one position left/right when that happens.

[wraith valve]

@keen hearth thanks! i got the answer after a bit of debugging! essentially mine was a sort then a linear iteration. its pretty neat how the asymptotics becomes so much better

[chilly acorn]

you can also adopt a more memory-consuming approach using ```py
original = [1, 2, 3]

def pop(array):
temp = array[-1]
array = array[:-1]
return temp

def pre_insert(array, element):
array = [element] + array

[vocal gorge]

Not sure what you mean. That's still O(n) time.

[chilly acorn]

but you don't iterate through anything

[vocal gorge]

(also, that pop is from the right side, not left)

[chilly acorn]

yeah, same thing but reversed

[vocal gorge]

So? array = [element] + array is O(len(array)). All elements of array need to be copied into the new list.

(perhaps you think that Python lists are implemented as linked lists or something - they aren't, they are essentially Vectors (dynamic arrays)).

[keen hearth]

Yep. That's the magic of dynamic programming 😄

If you want to practice specifically dp problems, this is a good site: https://binarysearch.com/learn

[wraith valve]

ive only really heard about dynamic programming but never really looked into it

[odd steppe]

would someone be able to help me spot my error.
The problem is a mergeTwoLinkedList
should intake both lists and output the combo
on other tests, the l2 is not being added, but in this test, part of it is being added

where might the problem be? My merge function looks fine

[serene mango]

But won't a list undergo doubling append , while a stack would just add a new pointer to add a new object? (Making append in stack O(1), while O(n) for lists in worst case) ?

[vocal gorge]

Append to a vector is O(n) worst case, but it's not usually considered such, because it's O(1) amortized.

[serene mango]

Yes that's what I meant. It's O(1) amortized but worst case (when it causes a doubling append is O(n))
But for stacks, worst case is O(1)
Assuming python uses linkedlist for stack (or does it not?)

[vocal gorge]

That's true I suppose, if you care about non-amortized worst case

and yeah, deques are linked lists (though they do something smart and have the list consist of arrays for somewhat better efficiency)
https://wiki.python.org/moin/TimeComplexity>

[serene mango]

Oh I see. I will check how dequeues are handled like that.. using list of arrays.

[dapper sapphire]

I'm working on an algorithm and I'm thinking of using nested dictionary. Below is how I'm currently thinking of setting up the nested dictionary:

{
  'LG-12127': # Does it make sense to create key on this? or could I just use indexes as keys? 
    {
      'internal_sku': 'LG-12127',
      'external_sku': 'LG12127'
    },
   'LG-12128':
    {
       'internal_sku': 'LG-12128',
       'external_sku': 'LG12128'
    },
   'LG-12129':
    {
        'internal_sku': 'LG-12129',
        'external_sku': 'LG12129'
    },
}

I have to make requests to Internal API that use internal_sku and requests to external API that use internal_sku.
So does it matter if I use internal_sku as primary key which itself is a dictionar
or could I replace internal sku being used as a primary key with indexes as shown below:

{
  '0':
    {
      'internal_sku': 'LG-12127',
      'external_sku': 'LG12127'
    },
   '1':
    {
       'internal_sku': 'LG-12128',
       'external_sku': 'LG12128'
    },
   '2':
    {
        'internal_sku': 'LG-12129',
        'external_sku': 'LG12129'
    },
}

[vocal gorge]

It depends on whether you want to find entries by their internal_skus.

Note also that the latter case (keys are 0,1,...) is basically just a list implemented using a dictionary.

[dapper sapphire]

Yeah, lol I just realized as I was typing this that it could be a list/array of dictionaries

Yeah I would have the main loop to traverse through the list and each index would be a dictionary that would have internal_sku and external_sku

[vocal gorge]

so... why are you using dicts at all? Just to store these two fields as one object?

[dapper sapphire]

When you say why am I using dicts at all, are you referring to external dicts?

[vocal gorge]

Both, really

[dapper sapphire]

Do you mean not use dicts at all, and create 2 dimensional array/list?

[vocal gorge]

If you just want to store these two fields as one object, I'd use a tiny simple class like this:

@dataclass
class MyClass: # Placeholder name, as I don't know what object does this represent
    internal_sku: str
    external_sku: str

and then have either a list of these, or (if you need to find them by their internal_sku) a dict mapping an internal_sku to the corresponding object

[dapper sapphire]

well, when I do the below, it's hard to know know what [0][1] is:

item[0][1]

Below is a bit more explanatory:

item[0]["internal_sku"]

[dapper sapphire]

oh wow this is much better lol!!!

This way people would know what properties are in that array/list

[vocal gorge]

yup, using classes is a lot better than just remembering what your tuples are

And this approach can be used for much more complex and even nested structures. Actual example from my code:

@dataclass
class PlayerBaseTemp:
    user_id: str
    name: str


@dataclass
class LeaderboardPlayer(PlayerBaseTemp):
    aco: float
    aco_games: int
    aco_exposure: float

    num_games: int
    win_rate: float
    damage_per_game: float
    kills_per_game: float


@dataclass
class Leaderboard:
    players: List[LeaderboardPlayer]

@dataclass
class LeaderboardRequest:
    leaderboard: Leaderboard
    fetch_timestamp: UTCUnixTimestamp  # in utc! datetime.utcnow().timestamp()

(and there's a way (dataclass-factory, say) to automatically convert such dataclasses to and from, say, JSON - I use this to parse API responses)

Basically, classes are amazing and one shouldn't evade using them, especially since there are ways to quickly define simple classes for storing data: @dataclass, NamedTuple...

(there's also the attrs library which is kinda like dataclasses but supposedly uses some low-level feature to make the resultant classes more performant; no personal experience though)

[azure pelican]

what does the @sharp pilotclass change?

sorry for @ someone 😛

[vocal gorge]

Without:

class MyClass:
    def __init__(self, internal_sku: str, external_sku: str):
        self.internal_sku = internal_sku
        self.external_sku = external_sku

With - just:

@dataclass
class MyClass:
    internal_sku: str
    external_sku: str

and the __init__ gets generated automatically - and, as a bonus, also __str__ and __repr__

[azure pelican]

oh, that's useful, thx

and init is generated with proper arguments?

[vocal gorge]

With the ones you specify this way, yes

[azure pelican]

what other useful decorators are there?

[vocal gorge]

well, I'm partial to @functools.lru_cache 😛

[dapper sapphire]

So when we store data like this using a class and if we have 1000 items, we would be creating 1000 instances of the class. Is there a downside to it?

[vocal gorge]

It does have some performance impact compared to using a tuple, but that'd only matter if you're doing something performance-critical

(and apparently attrs can do something smart for specifically these situations - it has "slotted classes" which are apparently good enough even for that?)

[keen hearth]

Also checkout typing.NamedTuple. It's similar to a dataclass, but can be used anywhere a tuple can.

[vocal gorge]

And in general, well, Python is about sacrificing performance to get readable code, not the opposite 🙂

[dapper sapphire]

Recently, I have started using classes more mainly because I have noticed how it can help in code organization. But what you suggested with creating a class was pretty good actually. Thanks @vocal gorge !!!

[dapper sapphire]

How is it that in the last line print(item.internal_sku, item.external_sku) doesnt give a suggestion for internal_sku and external_sku:

class Info:
    def __init__(self, interal_sku: str, external_sku: str):
        self.internal_sku = interal_sku
        self.external_sku = external_sku

llist = []
for i in range(10):
    info_instance = Info(f"internal_sku{i}", f"external_sku{i}")
    llist.append(info_instance)

for item in llist:
    print(item.internal_sku, item.external_sku)

I dont think there's something wrong with the code.

values print fine.

[vocal gorge]

Hover over llist

is your IDE smart enough to have figured out the type of it to be List[Info]?

if not, specify it explicitly: llist:List[Info] = []

and it should then know that when iterating over it, the elements are Infos

(that List is from typing import List)

[dapper sapphire]

When I hovered over llist it gave me

(variable) llist: list

Yeah, explicitly telling it by using llist:List[Info] = [] worked! Thanks!

So I can just do:

llist = []
llist:List[Info] = []
for i in range(10):
  ...
  ...

I dont need llist:List[Info] = [] insdide the for loop, telling it once works?
And we are telling it llist is List of class called Info

Actually, yeah telling it once before the for loop works fine.

[vocal gorge]

yup

and remove the first line in this snippet, you're initializing the list twice

[dapper sapphire]

oh ok got it thanks!

[fiery cosmos]

how do I get all simple paths from point a to point b in an undirected graph

[brave owl]

is it possible to do an infinite linked list in the sense that the last value points to the first value in the list

so basically a loop

[onyx root]

yes

[agile sundial]

it's called a circular linked list

[fiery cosmos]

Anyone know ressources for cp for python (specifically for the CCC contest hosted by uWaterloo)?

[agile sundial]

most dsa resources will be in pseudocode. those will work well for any language

there are some good ones in the pins

[fiery cosmos]

Thanks

[gritty marsh]

@silk breach

[silk breach]

im here

[gritty marsh]

could you tell me the definition of big-O notation as defined by that book?

[silk breach]

this notation gives the tight upper bound of the given function

[gritty marsh]

what's the mathematical definition? the one with c and n0?

[silk breach]

uh one sec

O(g(n)) = {f(n), there exist positve constants c and n0 such that 0 <= f(n) <= cg(n) for all n >= n0

g(n) is an asymptotic tight upper bound for f(n)

@gritty marsh

[gritty marsh]

Okay, so essentially

let's say, we have an algorithm that searches for an element in an array

let's say it iterates over each element in that array

what is the time complexity of this algorithm?

[silk breach]

depends on the number of elements in the array

O(n) ig

[gritty marsh]

right. linear time

[silk breach]

yeah

[gritty marsh]

okay, so know we know g(n)
g(n) = n

you are familiar with functions in math, right?

[silk breach]

uh somewhat

[gritty marsh]

alright

let's say the algorithm would be implemented like this:

for num in nums:
  num = num * 2
  if num / 2 == 5:
    return True

for some stupid reason, I multiply the number by two, and I divide it by 2 and check if it's 5.

Essentially, I'm checking if num is 5.

[silk breach]

yes

[gritty marsh]

Okay, so how many operations can you see is happening there?

[silk breach]

3?

[gritty marsh]

We have one operation num = num * 2

[silk breach]

multiplication division and comparison?

[gritty marsh]

that's O(1)

[gritty marsh]

correct!

[silk breach]

yay

[gritty marsh]

So we iterate over n elements, what would be the exact time complexity?

considering we have 3 O(1) operations per iteration?

[silk breach]

O(3n)?

[gritty marsh]

no need to write it in big-O notation

it'll just be confusing

[silk breach]

k

3n then

[gritty marsh]

so the time complexity is 3n

now we have our f(n)

[silk breach]

yes

[gritty marsh]

f(n) = 3n

[silk breach]

understood

[gritty marsh]

so
O(g(n)) = {f(n), there exist positive constants c and n_0 such that 0 <= f(n) <= cg(n) for all n >= n_0}

basically, there exists a number, that when you multiply g(n) with it, it's greater than f(n) starting at some n_0

the number in this case would be 3

n_0 can be negative infinity, but that's not very useful

because there's no negative input

[silk breach]

wait for g(n) to be greater than f(n) wouldnt the number have to be 4

or else g(n) = f(n)

oh wait nm f(n) can be equal to g(n)

[gritty marsh]

What O(g(n)) basically is in plain English is:

there exists a number, that when you multiply g(n) with it, it will be greater than f(n) after some point

let me give you an example

let's say we have a g(n) of n^2

and f(n) of n

does there exist a number, that when you multiply g(n) by it, it's greater than f(n) given some input?

[silk breach]

yes

[gritty marsh]

Look at this graph:

the red line is n^2

the blue line is n

if you have c = 1

is there a number n_0 that, after that number, c * g(n) >= f(n) for all n > that number?

of course!

it's 2!

right?

[silk breach]

yes