#algos-and-data-structs

1 messages · Page 9 of 1

fervent saddle
#

If you have a 1-dimensional list which you're trying to treat like a multi-dimensional list, like what numpy does with ndarrays, is this the algorithm for accessing the actual index of the underlying 1-dimensional array?

def get(self, position):
    x = 1
    actual_position = 0
    for idx, p in enumerate(reversed(position), 1):
        actual_position += p * x
        x *= self.dimensions[-idx]
    return self._arr[actual_position]
runic tinsel
#

probably

haughty mountain
#

also 1 indexing for some reason?

#

the indexing of a a n*m matrix a[i][j] could be translated to a[i*n + j]

fervent saddle
runic tinsel
# 
def get(self, position):
    x = 1
    actual_position = 0
    for idx, p in reversed(zip(self.dimensions, position)):
        actual_position += p * x
        x *= idx
    return self._arr[actual_position]
#

yeah i ended up with about the same

haughty mountain
#

oh, you want a N dimensional formula

#

gotcha

fervent saddle
#

3.11 has reversed on zip?

haughty mountain
#

pretty sure no

fervent saddle
#

What's a good name for the x variable?

fervent saddle
haughty mountain
#

you can write things without it, e.g. the 3d case could be written

i*n*m + j*m + k  =  (i*n + j)*m + k
runic tinsel
#

it's called "place" right?

#

7 in 1703 is "hundreds"

#

x is holding that this is "five hundred fours"

fervent saddle
#

Thanks both of you

haughty mountain
#

I think this works?

index = position[0]
for i in range(1, len(position)):
  index = index*self.dimensions[i-1] + position[i]
#

it might be nicer to prep another dimensions array so you can do the zip, though idk

fervent saddle
#

I'll test that too

runic tinsel
#

hm

#

that feels wrong

#

loading

#

!e

position = [1,1,1]
dimensions = [3,4,5]
x = 1
actual_position = 0
for idx, p in reversed(list(zip(dimensions, position))):
    actual_position += p * x
    x *= idx
print(actual_position)

position = [1,1,1]
dimensions = [3,4,5]
index = position[0]
for i in range(1, len(position)):
  index = index*dimensions[i-1] + position[i]
print(index)
halcyon plankBOT
#

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

001 | 26
002 | 17
runic tinsel
#

dimensions[0] is not part of this computation btw

#

maybe doing dimensions[i] fixes it

haughty mountain
haughty mountain
runic tinsel
#

ok, it gives the same answer

#

just dimensions[i]

haughty mountain
#

the expected result is 3*4 + 4 + 1 = 17, no?

#

which is what my thing gives

#

or am I switching something up?

runic tinsel
#

uh, i expect 26

haughty mountain
#

oh wait, I might be flipping something yeah

haughty mountain
#

!e in which case maybe

position = [1,1,1]
dimensions = [3,4,5]
index = position[0]
for i in range(1, len(position)):
  index = index*dimensions[-i] + position[i]
print(index)
halcyon plankBOT
#

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

25
haughty mountain
#

err...

runic tinsel
#

so with zip

z = zip(position, dimensions)
index, _ = next(z)
for p,d in z:
  index = index*d + p
print(index)
haughty mountain
#

wait, let me rethink my rewriting, I got that wrong

runic tinsel
#

the trick is that the first dimension is irrelevant

haughty mountain
#

n x m x p matrix

i*m*p + j*p + k  =  (i*m + j)*p + k
#

yes, so yeah [i] is correct

runic tinsel
#

given dimensions x,y,z you treat it as y,z,1

haughty mountain
#

!e

position = [1,1,1]
dimensions = [3,4,5]
index = position[0]
for i in range(1, len(position)):
  index = index*dimensions[i] + position[i]
print(index)
halcyon plankBOT
#

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

26
haughty mountain
#

there you go

fervent saddle
#

Why does that work? It's a math trick?

dark aurora
#

How to solve this problem

#

Like I have no idea

runic tinsel
#

some part is added early so it's multiplied by many 2s

#

others are only multiplied by a few

#

"math trick" is fair

fervent saddle
#

So it's not intuitive, right? I'm trying to figure out if I'm being dumb or not.

runic tinsel
#

dim = [30,40,20]
ind = [2,3,4]
we want 2(40*20)+3(20)+4 so we do

2                | ×40+3
2*40 + 3         | ×20+4
2*40*20 + 3*20 +4
#

it's pretty intuitive

fervent saddle
#

Oh no

#

Let me stare at it longer

fiery cosmos
#

strassens algorithm 😵‍💫

runic tinsel
#

originally you were adding factors to x, and you went from right to left
we're going left to right, and throwing the multiplier on everything we already passed

#

only direction is reversed

fervent saddle
#

Is it less intuitive than how I did it?

runic tinsel
#

yes

#

it is how you did it but the direction is reversed, and it's less intuitive

fervent saddle
#

Ok

#

Oh

#

Ok, I think I see now

fiery cosmos
#

i'm confused, im getting a float when i do len(list)

#

is that normal? its a list of lists btw

agile sundial
#

are you sure

#

that is not normal

fiery cosmos
#

im doing a list comprehension where i set a new list, subA, equal to [[] for x in range(len(a))]

#

and its giving me float object cannot be interpreted as integer

agile sundial
#

are you sure that's where the error is from, send code?

fiery cosmos
#

let me see

#

hmm it seems to not being liking my statement subA = [[] for x in range(len(a)/2)]

agile sundial
#

that's different, / produces a float

dark aurora
#

use //

haughty mountain
#

that's what's being computed

#

the thing goes

i
i*m + j
(i*m + j)*p + k
```so it's being build from the inside out
#

it's a pretty common thing as has been mentioned, e.g. for building numbers in base 10, say we have number with digits abcd then

a*1000 + b*100 + c*10 + d =
(a*100 + b*10 + c)*10 + d =
((a*10 + b)*10 + c)*10 + d
#

same idea

fervent saddle
#

It makes sense now that you show it

fiery cosmos
#

how do i check if an input file i'm reading's line contains a single integer

#

my input is screwy, if its only a single int then its the order of my matrix, otherwise multiple ints are the matrix elements

#

is there like a len of a line check

dim pier
#

When should I start learning algorithms and data structures and what do I really need it for?

haughty mountain
#

if you have the order you know how many things to read, no?

fiery cosmos
#

2
2 1
1 2

4
2 3 5 4
2 1 2 3
6 1 3 2
5 7 1 8

#

the order is the n*n of the matrix

#

i already had this working perfectly, prompting users to key in the input matrix and echoing it back to confirm, however they don't want console input or output

#

which is weird bc they also demand like error checking and stuff

#

and how would we print an error statement without "console output"

#

🤷‍♂️

haughty mountain
#

throw an exception?

fiery cosmos
#

wait this says "do not use GUI/console input or output"

#

maybe im misunderstanding

#

i read that as "do not use command line arguments"

#

which i think is, not what they're saying

haughty mountain
#

you could read that with something like

n = int(input())
matrix = [[int(x) for x in input().split()] for _ in range(n)]
fiery cosmos
#

in any case i think they want me reading in the thing the way they have it written

haughty mountain
#

maybe they want you to just take stuff as function arguments?

fiery cosmos
#

i already have a matrix builder i am hoping to repurpose by changing how the input is handled, eg instead of prompting the user to key in the matrices, read them in directly in the format above

dim pier
#

Would i be using A&DS in machine learning?

fiery cosmos
#

ML is very math heavy and yes, requires the usage of lots of programmatic knowledge and DS/algo

#

i know people who do "ML" but have no math or CS training, i liken them to pilots who can fly the airplane but could never engineer it

#

i would not want to be one of those ppl

stray nymph
#

There is no ML without math or CS training

#

No need to liken them to anything

fiery cosmos
#

lol thats how i feel but you're going to come across these people and have to have a way to not automatically tell them their whole career is professionally lying about what they understand or comprehend or work with so good luck

dim pier
#

Understood, how well do I need to understand the concepts before I get on to machine learning

#

I mean I'm basically emerging out of the beginner stage for the moment

fiery cosmos
#

some people never understand the concepts. you're asking about what it takes to go to space before learning to fly a single prop plane

dim pier
#

So does that mean those people can never grasp machine learning either?

stray nymph
#

If you want to meaningfully tweak models even, that minimally takes some experience in coding

#

If you want to actually meaningfully tweak models while having an idea of what each change should do, or reason about why certain changes should result in certain changes, you need formal training in math

#

In a way, anyone can find the best BERT-based model these days, but not everyone knows what a transformer is doing

dim pier
#

seeing as i'm doing maths for college that should work out pretty well right?

#

Or would I need university degree maths

stray nymph
#

Is college != uni for your area?

dim pier
#

Also, how would you recommend studying ds&a? Are there exercises or something I could try, because theres understanding something and then theres being able to use it?

dim pier
stray nymph
#

'CLRS' is supposedly the standard algorithm textbook

#

I don't know the equivalent for data structs, there's probably one

#

(I haven't ever read CLRS properly myself by the way)

stray nymph
stray nymph
# dim pier No its pre-uni

To really do anything with ML you need uni math yes. If not you will have to self-study statistics which I think will be painful

fiery cosmos
#

i wouldn't go so fixed on ML. if you learn programming and math you'll be in a great spot

#

what makes you so focused on ML

dim pier
#

guess this is gonna be painful then, im aware im saying this without even starting

#

I just think the things people can achieve with it are really cool, and I have a bunch of projects I'd wanna use some form of ai for in the future

stray nymph
dim pier
#

I don't think id be satisfied with just playing with stuff other people have made while not understanding anything

stray nymph
dim pier
#

are there any beginner easy to set up ones?

stray nymph
#

By that I mean, you just ignore understanding any model first, just see how they perform

#

Personally I used hugging face and read from there

dim pier
#

hugging face?

stray nymph
#

I think just using a model won't be that difficult these days

dim pier
#

alright got it thank you

stray nymph
#

Yeah I think you'd actually be motivated if you see for yourself

#

Then again, you might not have base models (non-ML) to compare against, hmm

#

but oh well, I think actually using ML leads to more motivation to actually learning how they work

#

rather than starting with statistical theory

dim pier
#

Yeah this is definitely gonna be more fun

stray nymph
#

Hope the fun propels you through uni lol, if not you'd get 'wtf why am I studying this vibes'

dim pier
#

Haha yeah

smoky remnant
#

i

agile sundial
fiery cosmos
#

i've been struggling all day to read in my input

#

i asked about it before w algmyr but the thing is i'm not allowed to use any code posted here directly so i just need generic english word guidance

#

what's tripping me up is im very poor at reading in txt files

fiery cosmos
haughty mountain
#

just the int value of the string from stdin

#

e.g. in your example input() gives "2"

2
2 1
1 2
#

and int(input()) gives 2

fiery cosmos
#

yeah i've been tinkering w eval to try to do away with that, what im really struggling with is line splitting and grabbing the order of the matrix, and trying to append the next amount of proper lines to matrix a / b / etc

#

i cannot take input anymore, need to read it in

# 
def matrixbuilder(inputmatrices):
    with open(inputmatrices) as f:
        for x in next(f).split():
            n = int(x)
        print(n)
#

so this works but only for the first line and matrix order

#

when i try to do stuff like for line in file its very difficult as the program'll want to do the same thing for every line

haughty mountain
#

replace input() with next(f) in my snippet and you have code for reading one matrix

fiery cosmos
#

but i need to understand in the context of like with open(file) as f: for line in f: somestuff

#

might next become helpful if i can grab the order of the matrix

haughty mountain
#

!e

f = iter("3\n1 2 3\n4 5 6\n7 8 9".splitlines())

n = int(next(f))
matrix = [[int(x) for x in next(f).split()] for _ in range(n)]
print(matrix)
halcyon plankBOT
#

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

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

i already have my file open as f though

haughty mountain
#

my f is just to have something that behaves the same as your file does

#

if you put the last 3 lines they will work for your file to read the first matrix

fiery cosmos
#

i see

haughty mountain
#

I was not aware next worked on a file, apparently file handles are iterators

#

iter(f) just gives back f

fiery cosmos
#

see we teach each other (lol yeah right)

#

i did figure out how to partition my input matrix for stassen's algo, so i've got that going for me

#

strassens*?

#

hmm this works for the second matrix when i just do:

n = int(next(f))
        mata = [[int(x) for x in next(f).split()] for _ in range(n)]
        print(mata)
        matb = [[int(x) for x in next(f).split()] for _ in range(n)]
        print(matb)
#

idk how i could make this work for an arbitrary # of matrices though

#

or of arbitrary size

haughty mountain
#

your matb is broken if the second matrix doesn't have the same dimensions as the first

fiery cosmos
#

it always will for this exercise, as we are building square matrix multipliers

#

eg no like 2x3 * 3x2 stuff

haughty mountain
#

what about 2*2 then 3*3?

#

and is the input format picked by you or is it given to you?

fiery cosmos
#

given

haughty mountain
#

so the format is matrices separated by a blank line?

fiery cosmos
#

and idk if we can parse it out into different files, so im running on the assumption that i'll need to read the order and then work from there

#

yeah just like i linked before, i'll link again

haughty mountain
#

it's not the format I would have picked, but I guess it works

fiery cosmos
haughty mountain
#

if I had to read this input I would just read the whole file and then split it per matrix

fiery cosmos
#

that sounds reasonable

keen dome
#

Hello I started Python today, and what’s wrong with the code:

`option1 = input(“What’s ur fav number”)

if option1 == 1:
print(”noice”)`

When I do this and I answer 1, nothing happens

fiery cosmos
#

i'll look into how to read entire files

haughty mountain
fiery cosmos
#

ok but like idk what format that would produce or how to think about it, i need to learn more

#

i've already watched a few youtube vids nothing is clicking yet

haughty mountain
fiery cosmos
#

bet

haughty mountain
#

it gives you a string with the whole file contents

fiery cosmos
#

ugh

keen dome
#

Hello I started Python today, and what’s wrong with the code:

`option1 = input(“What’s ur fav number”)

if option1 == 1:
print(”noice”)`

When I do this and I answer 1, nothing happens

fiery cosmos
keen dome
fiery cosmos
#

i'm working on my own code rn, sry

#

@haughty mountain i won't be able to parse through the read in file by line huh

haughty mountain
#

what's silly is that if you read this way you don't really need the order

def read_from_file(f):
  parts = f.read().split('\n\n')
  for part in parts:
    lines = part.splitlines()
    n = int(lines[0])
    matrix = [[int(x) for x in line.split()] for line in lines[1:]]
    print(matrix)

import io

f = io.StringIO("""2
2 1
1 2

4
2 3 5 4
2 1 2 3
6 1 3 2
5 7 1 8""")

read_from_file(f)
#

though as said I don't like this format

#

a better format would have been

2
2
2 1
1 2
4
2 3 5 4
2 1 2 3
6 1 3 2
5 7 1 8
fiery cosmos
#

i have been wondering about the necessity of the order, i guess it makes it easier in java or something

haughty mountain
#

it first says how many matrices you have to read, which means you can just read as much as you need

#

with the blank line split you kinda just read until the file ends, which isn't super convenient in python if you want to read line by line

keen dome
#

Name of the function that it wait 10 secs

#

?

haughty mountain
fiery cosmos
#

i've really been wanting to read the order and then have a counter or while loop and say do something like:

order = 2
while n <= order:
  ~read the lines i want~
  n+=1```
haughty mountain
#

that's what my first code did

fiery cosmos
#

hmm i guess i didn't understand the list comprehension

haughty mountain
# 
n = int(input())
matrix = [[int(x) for x in input().split()] for _ in range(n)]
#

for _ in range(n) is your loop

#

this reads a line, splits it, and turns the parts into ints

[int(x) for x in input().split()]
fiery cosmos
#

so input() in this case you are envisaging as?

#

a file, a line, ?

haughty mountain
#

something that gives the next line

#

it's a pity you're given this format that is kinda annoying for python

#

it doesn't fit that well with a line oriented thing, unless you wrap stuff in a try catch

fiery cosmos
#

dude you have no idea. i had a perfectly working matrix builder where you just key in each element and it builds it, and was working flawlessly and printing it back to confirm to user that it looks how you might think. my multiplications were also working, (the naiive algo) and im halfway done strassen's algo, then i notice they want the input read in in this weird ass manner

#

i'm happy i was able to read CLRS and get that they were talking about partitioning a 4x4 into 4 2x2's and actually be able to partition

#

anyhow, gotta get this working and without using your code explicitly

#

so gotta learn wth is going on with reading files in

haughty mountain
#

here is what you can have if you wrap stuff in a try except

def read_from_file(f):
  try:
    while True:
      order = int(next(f))
      matrix = [[int(x) for x in next(f).split()] for _ in range(order)]
      print(matrix)
      next(f) # consume the blank line
  except StopIteration:
    pass

import io

f = io.StringIO("""2
2 1
1 2

4
2 3 5 4
2 1 2 3
6 1 3 2
5 7 1 8""")

read_from_file(f)
#

when it runs out of file to read next(f) will raise StopIteration

#

(because that's how iterators work)

#

now you can have this nice line based reading you were after

fiery cosmos
#

thanks for your help tho

haughty mountain
#

at least steal the StopIteration thing and use next(f)

#

to keep your sanity

fiery cosmos
#

as a design paradigm i may choose to go in that direction. sanity is gone as i'm already paranoid something i write will be too close to something on the interwebs and i'll get dinged really hard. we'll see

haughty mountain
#

as said, there aren't too many options for how to read this format

#

option 1: read everything and split the parts and deal with each part

#

option 2: read line by line through the format (and handle that the read fails at the end)

fiery cosmos
#

yeah im looking at your option 1

#

but idk how im going to know which int is an order and which is a mat element

haughty mountain
#

wdym?

#

you know you'll first get the order

#

and then order lines of matrix elements

#

you know what you need to read at each point

fiery cosmos
#

if i read it in as a string i mean

haughty mountain
#

you don't have to read first and then try to figure it out

fiery cosmos
#

and it'll be 2x order, because i'll be reading 2x order lines and have 2 matrices of order*order

haughty mountain
#

new format?

fiery cosmos
#

no, it goes order and then 2 matrices, eg:

2
2 1
1 2
2 3
3 1

4 
1 3 2 4
3 2 1 1 
3 2 4 1
4 1 3 2
1 3 2 4
3 2 1 1 
3 2 4 1
4 1 3 2
haughty mountain
#

so new format

fiery cosmos
#

so order 2 means reading 4 lines

haughty mountain
#

two matrices in a row

fiery cosmos
#

maybe i wrote it incorrectly before

haughty mountain
#

your thing before has one matrix per block

#

not that it matters much for reading

fiery cosmos
#

sigh thats my mistake

haughty mountain
#

each block is just

  1. read order
  2. read order lines of matrix
  3. read order lines of matrix again
fiery cosmos
#

right im just not good at that in a for line in lines context. let me try what you just said and implement a next() based approach

#

so does next(f) just give the next line?

haughty mountain
#

for line in lines will get super awkward

fiery cosmos
#

oh i've come to discover that 😂

haughty mountain
#

because you will basically need to build a state maching

fiery cosmos
#

yeah forget that

haughty mountain
#

it's perfectly doable, but it's annoying

fiery cosmos
#

doable for some

haughty mountain
#

doable with some practice

#

but yeah next(f) gives the next line

#

you could also use f.readline()

#

same effect

fiery cosmos
#

so the trivial examples on next() involve iterators, how should i think about it in the context of with open(myfile) as f:

#

ok ok

#

let me go implement some stuff. thanks

haughty mountain
fiery cosmos
#

huh. who would have thought

haughty mountain
fiery cosmos
#

LoL

#

how are things over there in Europe

haughty mountain
#

business as usual

fiery cosmos
#

good good

#

hmm '\n' chars are messing me up

#

do i need the io statements and import?

#

@haughty mountain

#

Exception has occurred: ValueError invalid literal for int() with base 10: '\n'

#

also tried f.readline

haughty mountain
fiery cosmos
#

ok ok

opal oriole
#

(etc)

haughty mountain
fiery cosmos
#

it's the order = int(next(f)) line

haughty mountain
#

did you consume the empty line?

opal oriole
#

"while read empty line, continue"

fiery cosmos
#

oh it looks to be not occurring until the end, i can fix

haughty mountain
opal oriole
#

Will have same result.

fiery cosmos
#

so this while loop is just True while there is a successful next(f) call?

haughty mountain
#

when the iterator runs out an exception is raised

#

which is then caught

fiery cosmos
#

the iterator being the file

haughty mountain
#

yes

fiery cosmos
#

huh

#

interesting

haughty mountain
#

this is how iterators work

#

this is how for loops in python work

fiery cosmos
#

lol ok ok

#

i sense some agitation

haughty mountain
#

no

#

it's just a surprising thing

#

that for loops are basically a while with a try-except

fiery cosmos
#

and how is it doing this 'consume the blank line' you mention

haughty mountain
#

these are functionally the same

for x in thing:
  do_stuff

it = iter(thing)
while True:
  try:
    x = next(it)
  raise StopIteration:
    break
  do_stuff
fiery cosmos
#

i changed the except to except ValueError and i think its working now

haughty mountain
#

that will totally break

#

you're catching the failure to convert

#

what's your code?

fiery cosmos
#

ok maybe i need a diff try/except

#

1s

#

ok so if i run with the except stopiteration, i get the value error after its done parsing and goes back into the while loop. there must be blank lines in my input file

#

after the matrices

#

but i swear it works without it, lms

opal oriole
#

And then skip.

haughty mountain
#

there is no checking needed if you just read the format correctly

#

you always know what you're about to read

#

(other than the end of file at the end)

haughty mountain
opal oriole
#

Oh ok if you want to do that then start by reading the int, then you know how much to read, then repeat.

haughty mountain
#

exactly

fiery cosmos
#

i think it works fine without the stopiteration pass

#

and with a valueerror pass

haughty mountain
#

share the code

#

you shouldn't need the valueerror thing at all

#

you know when you're about to read an empty line

fiery cosmos
#

what about the lines at the end of the file that throw the ValueError

#

more blank lines

#

with '\n'

haughty mountain
#

why do you have lines at the end of the file?

fiery cosmos
#

im just using it as written, i guess i could scrub them..

haughty mountain
#

as written where? pithink

fiery cosmos
#

as given in the assignment required input

haughty mountain
#

if you explicitly have extra newlines at the end this is such a garbage format

fiery cosmos
#

welcome to academia

#

out of curiosity, let me compare the output with your stopiteration approach and without it

#

bc i wanna see if its working the way you think

haughty mountain
#

my thing will fail on garbage at the end

opal oriole
#

(I recommend not reading an exact format and just doing stuff like skip all blank lines as I wrote above)

#

(Unless such a format is specified by the teacher)

haughty mountain
#

this is also why I hate this kind of format where you just read like this

fiery cosmos
#

no but i dont think its breaking when i remove it as you might suspect

haughty mountain
#

if they just specify the number of parts at the beginning all issues go away

#

because then you can just read what you need

#

garbage at the end doesn't matter

haughty mountain
fiery cosmos
#

yeah .txt file

haughty mountain
#

ok, this is just garbage then

fiery cosmos
#

agreed

haughty mountain
#

a terrible fix would be to

f = iter(f.read().strip().splitlines())
#

not clean, but it would fix your issues

#

read the full string, strip whitespace at the end, split into lines, get the iterator over those lines

fiery cosmos
#

but the outputs are the same with the except StopIteration and without it

#

very curious

haughty mountain
#

it's not surprising

fiery cosmos
#

and when i say without it i mean with a except ValueError in the palce

haughty mountain
#

you start reading the garbage empty lines

#

so you get ValueError

#

if you hadn't had garbage StopIteration would have been raised

fiery cosmos
#

ok

haughty mountain
#

(god I hate this input)

opal oriole
#

The end of the file has garbage in it / not following the format.

haughty mountain
#

yes

#

it's terrible

#

bad format, and the input file is invalid

opal oriole
#

When parsing input from a professor assume it's not properly formatted, so you have to build into some prevention stuff like removing blank lines and stripping.

fiery cosmos
#

alright well now that i'm reading them in let me implement the code i had running before. i think i'll need to do that within the while block, as the two matrices get declared in there and then overwritten. i'll need to write my computed matrix, c, to an output file.

#

must i pass a blank txt file as input to my function or can i declare a new file within it and have it create it and then start writing to it

opal oriole
#

It will overwrite it.

#

But you can append too.

fiery cosmos
#

oh i meant like if i want a separate output file, must i pass in a blank file as an argument to the function to be written to or can i declare a new blank text file within the body and then start writing stuff to it? right now i'm not in read or write mode, well i must be in the default for with open(myfile) as f

#

i haven't explicitly declared 'r' or 'w'

opal oriole
#

It will create the file if it does not exist.

#

x requires it to not exist already.

haughty mountain
#

the default is 'r'

fiery cosmos
#

what might a 'declare a new text file with name `output`` line look like

#

within a function

opal oriole
#

open(file, mode='r',

#

mode is a default argument.

#

So you optionally not pass it and then it's "r".

fiery cosmos
#

also i have to 'echo the input', so i'll want to append the entire input file to it, ideally as i go?

haughty mountain
#

best used with with just as you've done before

#

it will create the file if it doesn't exist already

fiery cosmos
#

hm im thinking i want to read in each matrix and print them to output with a statement like input matrix 1 is x and input matrix 2 is y and their product is z

#

i've got this

#

thank you guys so much

#

hmm

#

for purposes of testing, is it going to get mad every time i rerun this bc the output file will already exist?

#

after the first time i mean

#

oh nv

#

nvm

haughty mountain
#

it won't

#

you will overwrite

#

as Squiggle mentioned there is another mode that will complain, if you want that behavior

fiery cosmos
#

what does a "write this stuff to my output" line look like in python

#

output.write()?

haughty mountain
#

you could do that, or you can use print

# 
print(..., file=f)
fiery cosmos
#

ty

#

ah shit

#

while file i/o is sort of an art huh

opal oriole
fiery cosmos
#

i mean its working beautifully now, i feel like the most sophisticated part was simply reading the inputs

#

i have a naive matrix multiplication function (O(n^3)), and after also implementing strassen's algo i'll compare the two

#

strassen's brings it down to like O(n^2 point something)

#

maybe implementing strassens will be more difficult than i think and yet i already got the partitioning down

cerulean river
#

hi can someone tell me why my code is giving one more value then I want?
Leetcode: https://leetcode.com/problems/top-k-frequent-elements/submissions/

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        buckets = [None]*(len(nums)+1)
        count = {}
        k_freqs = []
    
        for i in nums:
            if i not in count:
                count[i] = 1
            else:
                count[i] += 1
    
        for k,v in count.items():
            if buckets[v] is None:
                buckets[v] = [k]
            else:
                buckets[v].append(k)
            
        print(buckets)
        
        for counts in reversed(buckets):
            if counts:
                for elem in counts: 
                    k_freqs.append(elem)
                    print(k_freqs)
                    if len(k_freqs) == k: return k_freqs    
        return k_freqs

Algorithm:

  1. count occurrences of each element using a dictionary
  2. use dictionary to do bucket sort where the index is the count and the element is a list of elements that have particular count
    This means that say our input list is [1,1,2,2] then at index = 2 the value stored would be [1,2 because they both have a count of 2
  3. Iterate through buckets from the end of the list and append k elements into a list that will be returned
Input:
nums: [4,1,-1,2,-1,2,3]
k: 2

Output: 
[-1,2,4]

Expected: 
[-1,2]
-------------------------------------
Input:
nums: [1,1,1,2,2,3]
k: 2

Output: 
[1,2,3]

Expected:
[1,2]
-------------------------------------
Input:
nums: [1]
k: 1

Output: 
[1]

Expected:
[1]

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

vocal gorge
#

So by the time you do if len(k_freqs) == k, it's not the right k.

cerulean river
#

in the counting loop?

vocal gorge
#

Yup, with for k,v in count.items():.

cerulean river
vocal gorge
#

I looked at it a lot too, came to the conclusion this can't be happening and started looking elsewhere 😅

#

by the way, an IDE could likely spot this mistake, by pointing out you're not using the argument k

cerulean river
#

true but I am practicing for white boarding interviews some of which might use google docs so getting ready for that.

vocal gorge
#

Nevermind, it's also false, looks like pylance at the very least isn't smart enough for that

#

maybe pycharm could but I don't want to boot it up to check

#

some of which might use google docs
well that's some nightmare fuel, good luck

zenith wasp
#

Is there a good way of calculating what percentage of a given sphere intersects a shape given by connecting a point to a all corners of a rectangle (like a pyramid but the tip doesn't need to be above the base) and is there a similar way to do that calculation for a box?

lean junco
#

i am now able to write the dp[i] = ... from orserving recurrence relation but still gets stuck quite a bit on dealing with initialising dp[0] or dp[1] correctly (where its needed)
is there any other better way to properly deal with this without wasting time?
Currently i only initailise dp[0] after dry running example in mind(which is slow).

fiery cosmos
#

how can i automate making a bunch of different blank matrices that are all lists of lists

#

and give each one a diff name

#

how would you use loops to create structures of different names, like say i wanted 10 lists all a1, a2, a3.. etc

lament totem
#

Why would you need names if you are going to call them a1, a2, a3...

#

Just use a list, and the index 0, 1, 2, .. to access the one you want to acess

# 
import numpy as np

matrices = np.zeros((10, 8, 4))
#

This would make an ndarray that contains 10 8x4 matrices

stray nymph
fiery cosmos
#

for strassen's algo, i'm supposed to make 10 new matrices s1-s10, just thought it'd be nice to automate rather than what im going to do now which is literally copy and paste the declaration and change s1 = the thing to s2

stray nymph
#

use a dictionary called s and populate it with indices 1 to 10

#

That's how you should be reading mathematical notation and converting that to code

#

not actually write s1 = ...; s2 = ...; s3 = ...

fiery cosmos
#

but you see my matrices are lists of lists, so that would complicate the indexing

#

interesting that you can start a variable name with a letter but not a number

stray nymph
#

That's still just ijk, it's not too bad yet

haughty mountain
fiery cosmos
#

hey alg,
i was hitting you up before to better understand a list comprehension. now i'm like midway through implementing strassen's, and some of my submatrices are all zeroes in the bottom rows, so i feel that i'm going wrong somewhere

haughty mountain
#

list comprehensions are just a more convenient way of writing stuff you could otherwise write with appending to a list

#

e.g. these are functionally the same

a = [i**2 for i in range(10)]

a = []
for i in range(10):
  a.append(i**2)
#

or was it some specific example you were confused about?

fiery cosmos
#

yes but i got help on it and i think i'm good now. i had a lingering question though if its like a double for loop

#

one sec ill get the code

# 
matrixa = [[int(x) for x in next(f).split()] for y in range(order)]
#

i see two for's there

haughty mountain
#

yes, there it's just a list comprehension inside another list comprehension

#

i.e. the same as

matrixa = []
for y in range(order):
  matrixa.append([int(x) for x in next(f).split()])
fiery cosmos
#

ok. i wasn't understanding the int(x) bc i was reading it as calling int() on a list but i then learned it was just calling int on each element of the list and repackaging it into a new list as Type int instead of Type str

haughty mountain
#

you can also several fors in the same comprehension

a = [(i, j) for i in range(10) for j in range(10)]

# functionally the same as

a = []
for i in range(10):
  for j in range(10):
    a.append((i, j))
fiery cosmos
#

my strassen's algo is 340 lines and nowhere near done

opal oriole
#

10 4x4 matrcies is then a list of length 10 with lists of length 4 with lists of length 4.

#

Or 10x4x4.

opal oriole
mint gorge
#

I have a question.

#

How can I find patterns and outcomes in time series data(stock market data), by building a classification model. I am a python native coder and I believe this is completely possible with Python although I am curious if there is a certain stack out there which would be more efficient for this project. Also what libraries specifically would help me execute this task.

Also would anyone have any good recommendation for sites I can download stock market data, I have used Quandl but I want to see what other options are out there.

Thank you.

fiery cosmos
#

hi, i just want to clarify

# 
Foo(n):
  sum = 0
  k = 1
  while k < n:
      sum = sum + 1
      k = k * 2
  return k
#

is it right to say that the algorithm above performs n addition operations as a function of n?

jolly mortar
#

no, log n operations

#

k is doubled in each step

fiery cosmos
#

can i also just ask, how do we find the asymptotic running time of this algorithm? im a bit confused 😅

Bruh(n):
  count = 0
  for i=1 to n:
      for j=1 to 10:
          for k=1 to n/2:
              count += log(n)
  return count
jolly mortar
#

so O(5n^2) = O(n^2)

fresh stratus
#

Not entirely sure if this is the right channel, but I have a 2D numpy array and I want to run a lambda on each item (not each row) like map() would do

frosty plover
#

hi. i have a time complexity question.
If i loop over an array that increments the index by 4 for each iteration, then inside the for loop - loops over these 4 items (so 4 is a constant), is it considered an O(n+1) or O(n^2) ?

cerulean river
# 

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        i =0
        j =1
        k = len(nums) - 1
        triples = []
        
        nums.sort()
        
        all_zero = True
        
        for i in nums:
            if i != 0: all_zero = False
        
        if all_zero:
            return [[0,0,0]]
        
        while i != j and i != k and j != k:
            if nums[i] + nums[j] + nums[k] == 0:
                triples.append([nums[i] , nums[j] , nums[k]])
                k -= 1
            else:
                i += 1
                j += 1
        
        return triples

Solving 3Sum not sure why this solution returns an [] when the input is [-1,0,1] because it is supposed to return [[-1,0,1]]

cerulean river
#

correctly*

marble hawk
#

u have a billion apple baskets. each apple has green and red side, ratios of which are different for each apple. how to pick 10 baskets that will in total have the highest possible ratio of red color?

#

and you cant have more than 100 apples in total

#

baskets have random amount of apples

frosty plover
lean junco
#

I had this question:
given maximum moves,
[m n] which is size of array and
[i,j] which is initial position

find all the possible ways to reach arrays boundary

i applied a dfs approach but it gave TLE, how would i apply DP in this?
the recurrence relation is dfs was like return dfs(...i-1,j...)+dfs(...i,j-1...)+dfs(...i+1,j...)+dfs(...i+1,j+1...)

#

it doesnt seems the index are such that normal dp would work

#

plus the moves are also decresing

#

how to approach

haughty mountain
jolly mortar
fresh stratus
#

x.rgb

#

lambda x: x.rgb

flat sorrel
fresh stratus
#

a custom class

flat sorrel
#

numpy.vectorize should do the trick

#

but tbh you probably should use a 3D array (width, height, 3) of floats/ints to store RGB images instead of a 2D array (width, height) of Python objects

#

it would speed up numpy operations by a lot

fiery cosmos
#

how to interpret asymptotically?

haughty mountain
#

for n^sin(x)?

#

idk if there is something that would disqualify it from being valid, but O(n) fits the definition

#

the lower bound is just messed up though

#

I guess Ω(1)?

fiery cosmos
#

the correct answer is that when comparing the two, the asymptotic equalities fall apart, and that sqrt(n) is not O, o, big omega, little omega, nor theta of n^(sin(n)), i suppose due to the fact that the "for all n greater than n_0" requirement is lost

#

i had another ? though

#

regarding n vs sqrt(n) asymptotic relationship

#

hmm nvm

haughty mountain
#

oh, you want to compare these functions?

#

yeah, these two break

#

basically just consider the definitions

#

is there a constant that makes sqrt smaller than c n^sin(n)?

#

no, because n^sin(n) is Ω(1)

#

and sqrt(n) is bigger than that

#

same kind of argument for O

#

first is O(n), sqrt(n) is asymptotically less than that

#

so it's neither an upper or lower bound

#

I guess in general if the second function is strictly between the upper and lower bound on the first function, then this happens

jolly crypt
# 
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        hashmap = {}
        for s in strs:
            sortedS = "".join(sorted(s))
            if sortedS in hashmap:
                hashmap[sortedS].append(s)
            else:
                hashmap[sortedS] = [s]
                
        return hashmap.values()```
In terms of time complexity, most of complexity comes from sorting each word s, and sorting a single word s takes O(mlogm) where m is the length of the word and you do it for each word s (there are n of them) -> O(n*mlogm). Is this correct? Also in terms of space complexity, i am a bit unsure on how to work that out. Like sorted(s) produces a list of the characters in the word s in sorted order so O(m) but like after each iteration of the for loop, doesn't that list get destroyed, as in that list is only used to produce sortedS, so like would that still add up to the space complexity or not?. I guess i need to work out how much space the hashmap will take.
ruby quail
#

hi, not sure where to ask this so I ask here. I'm struggling with understanding the difference between apache beam and apache spark (specifically for Google Cloud's Dataflow Vs Dataproc). Could someone help me out here?

haughty mountain
haughty mountain
#

and yes the space complexity boils down to how much is stored in the hashmap

fiery cosmos
#

is n= theta(1)?

#

sort of hurting my brain to even consider this

#

i guess the more appropriate question would be is f(n) in the set of functions which can be upper and lower bounded by 2 arbitrary constants for all n > n0?

haughty mountain
fiery cosmos
#

and i guess it would be bc you can always choose two constants which are greater than and less than when multiplied by 1?

haughty mountain
#

no wait

#

theta

#

it's not theta(1)

#

I thought sigma

fiery cosmos
#

i think it is unless i'm getting to the answer incorrectly

#

i have a recurrence T(n) = T(n/2)+n, and im using the master's theorem

#

a=1, b=2, log_2(1) = 0, n^0 = 1

#

compare f(n)=n with n^(log_b(a))

haughty mountain
#

(just looking at it, T(n) < 2n, but go on)

fiery cosmos
#

question becomes, compare f(n)=n to n^(log_b(a))=1

#

so case 1, is n = O(1)

#

case 2: is n=theta(1)

haughty mountain
#

let's dump the master theorem here so we have it

unknown.png
#

it isn't, any guess as to why?

#

hint: you just basically said it isn't

#

n = O(1) is false, right?

fiery cosmos
#

correct

#

oh i see

#

if that's false, theta of same term is false by definition

haughty mountain
#

Θ requires both O and Ω, yes

fiery cosmos
#

but let's revisit n=O(1)

haughty mountain
#

wait

#

I keep writing the wrong letter, fixed

#

theta requires both

fiery cosmos
#

its false because for every constant c we choose, there can always be a greater n?

haughty mountain
#

basically

#

you can try the definition if you want to

fiery cosmos
#

in other words there is no point at which an arbitrarily large constant times 1 is still larger than ever increasing n?

haughty mountain
#

but n grows quicker than 1, that's the basic truth

haughty mountain
fiery cosmos
#

but it's not just 1, it's c*1

haughty mountain
#

for any choice of c, n will eventually grow larger than c*1

fiery cosmos
#

ok for sure

#

so i'm left w case 3, in which case i have to check the special condition

haughty mountain
#

so the question is, is n = Ω(1)?

fiery cosmos
#

seems that way. i'm not good at checking the special case however given a=1, b=2, f(n)=n, we have, is:
1 * f(n/2) <= c * f(n) for some constant c < 1?

#

i'm actually really bad at this part, i usually just ignore the f( ) and write in is n/2 less than or equal to 1/2 times n

#

which for c = 1/2, is true

haughty mountain
#

it's not that you ignore f(...)

#

substitute in the actual value

#

f(n) = n
f(n/2) = n/2

fiery cosmos
#

right so when n=2, f(n/2) = 1

haughty mountain
#

wait, why do we care about n=2?

#

oh, you want to pick an n0?

fiery cosmos
#

no we dont care about that

#

i was just reminding myself a separate for instance

haughty mountain
# 
1 * n/2 <= c * n
n/2 <= c * n
#

when is this true?

#

||c >= 1/2|| and ||n >= 0||

fiery cosmos
#

when c >= 1/2, but c must be < 1 per definition

haughty mountain
#

per what definition? pithink

fiery cosmos
#

case 3

haughty mountain
#

ah, right

#

but yeah, any 1/2 <= c < 1 works

#

it's not immediately obvious why c >= 1 breaks, but there probably is some simple reason

#

oh, I guess it's just about whether this term

unknown.png
#

is small compared to f(n)

fiery cosmos
#

hmm something is off

#

i should have written T(n) = T(n/2) + theta(n), which is the same recurrence as mergesort

#

which we know to be n lg n runtime

haughty mountain
#

it's not the same recurrence

fiery cosmos
#

i know i should have written theta(n), because i was analyzing the cost of recursive binary search + the time taken to give the entire array and not just a pointer, which is theta(n). so I think what I wanted to be analyzing is really T(n) = T(n/2)+theta(n)+1, which i'm deriving from the cost of recursive binary search + cost of passing the entire array and not just a pointer

#

and i think that +1 means no master theorem

haughty mountain
fiery cosmos
#

ok

haughty mountain
fiery cosmos
#

i should be putting this in python general?

haughty mountain
#

no

fiery cosmos
#

lol ok

haughty mountain
#

I sense the sarcasm didn't come through 😛

fiery cosmos
#

it rarely can successfully via the internet

#

i don't think you're "allowed" to let the theta absorb the 1, i think if its not in the proper form you cannot use the master?

#

ohh nvm

#

im thinking of the example where its n and not theta(n)

haughty mountain
#

"proper form" would probably be to put n in there

#

or whatever

#

though I think at some point there was an example that showed that a multiplicative constant on the right term doesn't matter at all

#

for the asymptotics

fiery cosmos
#

i recall previous problems where the +1 rendered the master non usable however IIRC that was due to it being n middle term and not theta(n)

haughty mountain
#

yes

#

the first term is the sensitive one

#

the second term you can multiply by any constant and it doesn't matter

#

you could try replacing + f(n) with + C f(n) in the master theorem and the result should be no different to the result

fiery cosmos
#

in general, are O(n) and c*n interchangeable?

haughty mountain
#

strictly no

#

but kinda

fiery cosmos
#

hm

haughty mountain
#

math people would hate you for doing it

#

but it's basically true

#

if you want to be strict you won't mix asymptotic notation with O, Θ, Ω with the non-asymptotic stuff

#

(my education skews towards engineering and theoretical physics, I'm much more fine with doing that kind of stuff)

#

(you just need to know what you're doing)

fiery cosmos
#

i'm really bad w showing the exact forms of things

#

i get what's going on in general but when the exact form comes up there are a lot of variables and a lot of things that seem to be "you can do away with that" and others "you absolutely cannot do away with that"

haughty mountain
#

that's also why trying to throw asymptotics where they don't really belong is kinda dangerous

#

you need to know what you can and can't be sloppy with

#

which basically means you need to know how you would do the strict way

lean junco
#

does this still count as dp lmao?

haughty mountain
#

sure, you're counting the number of paths by using previous known values

#

so feels like it fits

lean junco
#

will faang laugh at this, i would if i saw this xxl ifs

haughty mountain
#

you can remove a lot of them by just initializing the i=0 and j=0 edges on their own

lean junco
#

hmm doing something like that

lean junco
#

aye y0, incoming sde

fiery cosmos
#

so desmos seems to be telling me there is a tighter bound on T(n)=4T(n/3)+nlgn, how can i prove that?

#

by tighter bound i mean o(nlgn)

#

the master theorem gives me that its O(nlgn)

#

but what if i want to prove its o(nlgn)

#

it looks like it is for a small value of n

fiery cosmos
#

nvm apparently little o is a looser bound..

cinder crystal
#

anyone up to help me speed up an array loop 😉 i'm trying to build an array with random numbers, then convert the numbers and slice each array, then convert that array into an array of those array's lengths.. (see #help-cheese )

swift forum
#

Hi I have some question related to building binary tree

#

Can I get some ideas about building binary tree from input math operation string with brackets?

safe jacinth
#

Hello.

#

Can someone explain to me how this algorithm works?

# 
for i in range(1, len(elements)):
        anchor = elements[i]
        j = i - 1
        while j>=0 and anchor < elements[j]:
            elements[j+1] = elements[j]
            j = j-1
        elements[j+1] = anchor```
#

It is called insertion sort, however I am having a difficulty understanding it conceptually

#

Please reply if you can offer assistance

lean junco
lean junco
safe jacinth
#

The indexes are quite confusing. In the animation, the number with the red box, is that anchor or j in the code I provided?

lean junco
#

dont read the code, if it confuse you
try to implement with pen and paper with an example

#

you will see how it works

safe jacinth
#

Yes the code is hard to visualize in my mind

lean junco
#

@safe jacinth also the basic idea is same but dont expect that everyone would use "anchor" etc. variables
the style can be a bit different

safe jacinth
#

Everytime I try to understand the code, my brain is too dumb, I am trying to imagine the index and if this index < index[i] and all this stuff

jolly mortar
#

anchor is the number inside the red square

safe jacinth
grave vortex
#

hi, i have a lucky draw program
in this, ppl buy tickets,** more the tickets they buy, more is the chance of their win**

i tried to make its algorithm to choose a winner

i init a empty list, append the user's id in the list with number of tickets they have

like a guy x has 4 tickets, and y as 2 tickets, then the list will be: [x,x,x,x,y,y]

then i shuffle the list using random.shuffle() 3 times

and then choose one element from the list using random.choice()

is the algorithm correct, do it have some loop holes?

vocal gorge
#

then i shuffle the list using random.shuffle() 3 times

and then choose one element from the list using random.choice()
why not just one random.choice?

austere sparrow
#

and why shuffle 3 times

austere sparrow
#

Can a person own a million tickets, for instance?

stable pecan
halcyon plankBOT
#

@stable pecan :white_check_mark: Your 3.11 eval job has completed with return code 0.

['y']
grave vortex
jolly mortar
#

theres no increase in randomness

grave vortex
grave vortex
fiery cosmos
#

does anyone have experience in making discord bots with python?

agile sundial
fiery cosmos
austere sparrow
# grave vortex Yes

so if someone has a million tickets, there's going to be a t least a million items in the list

#

that's quite a lot

#

in other words, your time/space will grow as O(tickets)

haughty mountain
bronze panther
#

Hey, i've been working on a project in my free time, but i'm curious to hear other people's thoughts on high-level optimizations/approaches to keep the processing time reasonable when i eventually start to scale it up. I know a bit about different algorithms but definitely not a ton. Also, the program's centered around Tetris, but it doesn't really need any background knowledge of the game to understand so bear with me on the vocabulary
Quick tetris vocab stuff: in the game, if you clear lines so the board's completely empty afterwards it's called a "Perfect Clear" (PC), and if you do it by clearing four lines with a line piece that's a "Tetris PC," and if you do one right away when the game starts it's called a "1st Tetris PC"
so basically I want to find every way to do this at the start of a game:

#

the only other constraint is that it's trying to find solutions with the "7-bag" system, which is basically where in the game, instead of rolling a die for what the next piece will be, it has a 7 card deck- one for each piece- that it shuffles, deals out, shuffles, deals out, etc.

#

rn i have a version that takes about 7 seconds to run on my computer, but i want to start having it look at filling more than just 4 rows soon, and rn i'm basically just using permutations to find everything and O(n!) isn't exactly the best for scaling

#

rn my approach is: use permutations to find every way the pieces (within the 7-bag constraints) can fit a 9x4 area

#

then i go through and see if there's any vertical lines i can make that don't cut through any pieces

unknown.png
#

and make that into another solution by moving the last line piece

unknown.png
#

then from all the solutions i have so far, i flip all the pieces to get the rest of the solutions

#

that way the permutation part only comes down to that first step (filling the 9x4 area with pieces)
so basically is there a faster/more efficient way to find all the ways pieces can fill a 9x4 area (with the 7-bag constraints) than permutations?

haughty mountain
#

I suspect a pretty brute force search wouldn't be too slow

#

you should be able to prune pretty aggressively as well

#

since you will very easily end up with gaps

haughty mountain
#

though I guess things kinda explode if you try to expand much further up

dark aurora
#

Is there any way to solve this in python

#

I solved it in O(n) and it still gets time limit exceeded

fiery cosmos
#

hey how can i return all the indices of a list.. enumerate?

agile sundial
#

range(len(L))

fiery cosmos
#

ok that gave me a single int but i

#

i'd like to print every index in a list of lists of lists structure

#

well not a single int but a range

agile sundial
#

range gives you a range, so not sure what you mean by that

bronze panther
#

like for a list [4,4,4] you want it to give you [0,1,2] right?

fiery cosmos
#

its printing a range but i'd like to see every index of every list so for example if i have like [[[4,1],[2,3],[3,1],[1,3]],[4,1],[2,3],[3,1],[1,3]],[4,1],[2,3],[3,1],[1,3]]] i'd like to see every index at each position

bronze panther
#

like [0][0][0],[0][0][1],etc. ?

fiery cosmos
#

format doesn

#

doesn't matter

#

well i'd like it to be an int, not a list with an int, but doesn't matter

bronze panther
#

you want the length of the whole list including all the sub-lists?

#

like [[5,6],[2,3]] => 4

fiery cosmos
#

not the length i just want to see the indices. it might be a list of lists of ints or further nested, doesn't matter

#

idk what it would look like except a lot of 0's,1's,2's, etc

bronze panther
#

so would something like:
[[5,6],[2,3]] => [0][0], [0][1], [1][0], [1][1]
work?

fiery cosmos
#

sure but kim mine is triply nested

bronze panther
#

gotcha
so you know for sure it's triply nested and not more

opal oriole
#

It is possible to turn a triple nested list into one flat list, which then has indices that single ints.

fiery cosmos
opal oriole
#

If you don't want to actually flatten the nested lists and just want to know what the 1D index would be for a given 3D index you can use a conversion formula.

bronze panther
#

so basically the range(len(L)) thing gives you the indeces for one layer, but you can nest that too for each layer

fiery cosmos
#

ohh

#

(range(len(L))(range(len(L))range(len(L))))

opal oriole
# fiery cosmos ohh

So you want something like: ```
0 0 0
0 0 1
0 0 2
...
0 1 0
0 1 1
0 1 2
...

fiery cosmos
#

whatever. it's not critical to my algo more of a curiosity thing. that would work great

opal oriole
#

One for each dimension (x, y, z).

bronze panther
#

like the messy version of it would be

indexList=[]
for i in L:#One layer deep
  subList=[]
  for j in i:#Two layers deep
    subList.append(range(len(j)))
  indexList.append(subList)
opal oriole
#

The first loop can loop over the outer-most list, the second over the current list in that, and so on.

#

(The nested loops match the nested-ness of the lists)

bronze panther
#

so say you had: [ [[5,5,5],[5,5]], [[5,5,5,5],[5,5]], [[5],[5]] ]
basically that's a list of a lists
the first for loop will look at each element of that list: first [[5,5,5],[5,5]], then [[5,5,5,5],[5,5]], and lastly [[5],[5]]
the second loop is looking at each of those elements one at a time, and it'll do the exact same thing the last for loop did, looking at each element the given list, ie: for [[5,5,5],[5,5]] it'll look at [5,5,5] then [5,5]
the next layer down has the range(len(j)) line from earlier, which will make a list of indeces the length of the list, ie: for [5,5,5] it'll return [0,1,2]
"append" just adds the given element to the end of a list, so in this case it'll add the entire list [0,1,2] as the next element

opal oriole
#

!e ```py
for z in range(3):
for row in range(3):
for col in range(3):
print(z, row, col)

halcyon plankBOT
#

@opal oriole :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | 0 0 0
002 | 0 0 1
003 | 0 0 2
004 | 0 1 0
005 | 0 1 1
006 | 0 1 2
007 | 0 2 0
008 | 0 2 1
009 | 0 2 2
010 | 1 0 0
011 | 1 0 1
... (truncated - too many lines)

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

bronze panther
#

woah

#

you guys are fancy

fiery cosmos
#

lots of brain power here as others have pointed out

opal oriole
#

Python also has itertools:

#

!e ```py
from itertools import product

for z, row, col in product(range(3), range(3), range(3)):
print(z, row, col)

halcyon plankBOT
#

@opal oriole :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | 0 0 0
002 | 0 0 1
003 | 0 0 2
004 | 0 1 0
005 | 0 1 1
006 | 0 1 2
007 | 0 2 0
008 | 0 2 1
009 | 0 2 2
010 | 1 0 0
011 | 1 0 1
... (truncated - too many lines)

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

fiery cosmos
#

get truncated on

bronze panther
#

(keep in mind that only works if the sublists are all the same size as the other sublists (and sub-sublists to sub-sublists))

#

but either way the idea's the same

fiery cosmos
#

that makes me wonder why you cannot use variables in python eg for y in range(x) and x is a variable, which allows you to iterate over variable sized structures?

#

perhaps you could set x equal to some range? what happens if you try to loop over a nest of ranges?

bronze panther
#

you can

opal oriole
#

In the example given you would replace the 3s with whatever is needed.

#

Such as the length of the outer most list, etc.

fiery cosmos
#

i don't mean where a variable is equal to a constant, i mean like a true variable where you could have allow x=anyvalue

halcyon plankBOT
#
Missing required argument

code

bronze panther
#

so when you're dealing with nested functions like function1(function2(function3())), you start at the inside at work your way out, aka function3() resolves so function2() has an input and when function2() resolves function1() has an input and will execute
aka function1(function2(function3())) executes function3() then function2() then function1()

opal oriole
#

!e ```py
blah = 5
for i in range(blah):
print(i)

halcyon plankBOT
#

@opal oriole :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | 0
002 | 1
003 | 2
004 | 3
005 | 4
bronze panther
#

how else would that work

fiery cosmos
bronze panther
#

wdym

#

you can run the same line again after changing the value of x, if that's what you mean

opal oriole
#

"blah" can be anything, not a constant.

bronze panther
#

well variables can only be one thing at a time lol

fiery cosmos
#

yeah i guess you can do it, like a house counting function would work on any street bc you can simply do py housecount = 0 for house in houses: housecount+=1 return housecount

#

i was thinking like things that can loop over variable ranges

#

without explicitly changing the parameters in the range each time

bronze panther
#

you can do that too

opal oriole
#

range(x) is a variable range.

bronze panther
#

so basically for loops are always expecting a list

fiery cosmos
#

yeah i guess that's just a while loop

fiery cosmos
#

oh you can change x

bronze panther
#

so basically in python all for loops work like:

for i in someList:```
then every loop they set i to the next value in the list and run the code
fiery cosmos
#

i see

opal oriole
#

If I say an algorithm is O(n) it's runtime is variable. n is not constant.

fiery cosmos
#

eh true but the n must take on some discrete input size?

opal oriole
#

Which can be whatever.

#

Not always the same.

# 
blah = get_number_of_tennis_balls_used_in_recent_tournament()
for i in range(blah):
  print(i)
#

Here blah is dynamically given by some server.

#

Each time you run this program, it may given a different result without any modification to the code.

#

Or how about:

#

!e ```py
import random

blah = random.randint(1, 10)
for i in range(blah):
print(i)

halcyon plankBOT
#

@opal oriole :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | 0
002 | 1
003 | 2
004 | 3
fiery cosmos
#

i have looked into randomness before yeah. i have a quicksort that uses random partitioning

bronze panther
#

range(X) basically makes a list counting up from 0 to just before X, ie: range(3) => [0,1,2]
range(Y,X) gives it a starting number, ie: range(2,6) => [2,3,4,5]
range(Y,X,Z) tells it how much to increase by each time, ie: (2,10,3) => [2,5,8]

for loops always iterate through a list, ie: for i in someList:
if you set it to a list you have it can go through that, ie: for i in [5,2,8,8,202,3,1,1,4,3.1415,2]
if you use range, you can make it create the list for the for loop, ie: for i in range(2,10,3):

#

(sorry that took me a sec to write out lol)

fiery cosmos
#

speaking of, i keep getting errors in my strassen algo, i'm getting
Exception has occurred: TypeError 'NoneType' object is not subscriptable

opal oriole
#

It means you are doing something like array[i] but array is None.

bronze panther
#

None is null in other languages btw

#

(you're trying to look into a list you haven't assigned any values to yet)

opal oriole
#

None, nil, null, nothing, ...

bronze panther
#

make sure you're not looking for any sublists that aren't there

fiery cosmos
#

yeah in my book the special Nonetype value is Nil and in python it's None

bitter sierra
#

is there any other good resources to learn algos and data structure other than the ones in pinned messages?

thorny bluff
#

Does anyone has recommendations to learn algos and data-structs?
I'm having difficult time doing leetcode questions most of my answers exceeded the time limit
I have not taken any courses on ds and algos

#

What is a good resource to learn from?

#

oh nvm i see them in the pin section thanks!

agile sundial
lean junco
#

I was reading how to implement Segment tree, for the inserting new number an any index, it said just add number to all nodes having its index in its range.
My doubt is that, yes we should add but should we also subtract the number which is at the last of that range?
FOR EXAMPLE if node has range 3 to 7 and we insert number at 4, after adding number at 4 wouldnt the number at index 7 go to index 8? so we also have to subtract it from node that had to store from 3 to 7

fiery cosmos
#

#bot-commands

random ridge
#

hey not sure where to put this, but how would i convert e.g. \x75 to bytes b'\x75' instead of 'u'

#

data = (b'\xf8\xc6\x9e\x91\xe1\x75\x87\xc8')
print(data)
this prints
b'\xf8\xc6\x9e\x91\xe1u\x87\xc8'
you can see that the \x75 has been converted to b'u' - i want it to just be b'\x75', its really annoying and i havent found a solution for this anywhere else

dark aurora
# haughty mountain I suspect a pretty brute force search wouldn't be too slow

When you solve problems do you prove your solution first and then code it or... Because I often code solutions on intuition, like this should be right, but I don't have any proof that it will work (to be more precise I don't have any proof that it won't work) Do you think this is bad practice or is it fine? Usually it works out fine, but of course there are times when my intuition is wrong.

haughty mountain
#

sometimes it's very important to verify formally that what you're doing works

#

sometimes it's obvious that it should work, even if you have no formal argument for why

#

(you also get better at spotting the obvious correctness over time as you solve problems)

#

I think if I was unsure if something would work I probably wouldn't waste time implementing before I had tried to motivate it

#

or at least try to prove it wrong

opal oriole
# dark aurora When you solve problems do you prove your solution first and then code it or... ...

I think that if it's not too hard to code then coding it is similar to playing around with it on paper. Most large improvements happen in the order of playing around with specific cases -> intuition -> more cases -> generalization -> proof. And the proof / rock solid foundation part has historically come much later in some cases (e.g. calculus). But there are times when you want to stop and prove things before continuing because if it does turn out that it's wrong you may have just wasted a lot of time.

#

(The deeper you go, the more proofs you want to make sure you are not building on sand)

#

Whether you stop and prove things or not is a multi-arm bandit problem so there is no nice general / simple rule that can be given for this.

fiery cosmos
#

is n = Θ(sqrt(n))?

kindred galleon
#

!e print("hi")

halcyon plankBOT
#

@kindred galleon :white_check_mark: Your 3.10 eval job has completed with return code 0.

hi
naive mauve
#

@chilly crane

tacit nova
#

can i use normal list [] or deque with bisect ? even if that list is sorted, i still think not
but if its from sortedcontainers import SortedList then its possible

prime flicker
#

Hey, why this is illegal :D?

#

Is it only problem with pylance?

vocal gorge
vocal gorge
#

use a string here, "Node". the typechecker will understand.

prime flicker
vocal gorge
# prime flicker

btw you probably want Node|None, since if it's Node, then you can never create a Node, because to create one you need to already have one... 🥴

prime flicker
#

That's right. I was just anxious about yellow underlining first 😛

#

Something like this happens

unknown.png
vocal gorge
#

"Node | None" should work

prime flicker
#

Okay, thanks a lot. It's funny that I can't use Node in arguments of constructor but can inside body :P.

haughty mountain
#

and when the function is called Node is valid

safe jacinth
#

In quick sort, does it matter what the pivot is. Can I simply select a random value within the array?

fiery cosmos
#

why does Bubble, Selection, and Insertion Sort have O(1) space complexity?

glossy breach
#

Because you dont need any extra array for those algos

glossy breach
agile sundial
#

if you pick a poor pivot, you may run into bad performance, but using a random pivot gives you on average good performance

kind crown
prime flicker
agile sundial
prime flicker
#

Can you send me? I'd like to see this.

#

Im sorry if I ask something trivial. Just started studying algos ;)

agile sundial
#

see section 7.2 in clrs

#

the basic, very not rigorous idea is that as long as the pivot puts a constant fraction of elements on one side of the pivot, then the recursion tree has depth Theta(lg n), and since you do O(n) work on each level, you can get an upper bound on the total time, O(n lg n)

haughty mountain
#

random pivot is quite good in practice yeah

#

many other approaches are pretty easily exploitable

#

there is the median of medians technique to have actual O(n log n), but that's quite slow in practice

agile sundial
#

hand waving a bunch of probability details

haughty mountain
#

well, there are more bad pivots than 2

#

they are just slightly less bad

#

picking anything in the smallest/largest k elements (for some constant k) over and over would make it O(n²)

agile sundial
#

ah, yeah

haughty mountain
#

but it's true it's rare

#

quicksort impls can be exploitable in general, I remember causing a stack overflow in Java with intentionally bad input

#

that did actually get fixed at some point though to not just use a quick sort variant

agile sundial
#

i think java uses timsort now

haughty mountain
#

I think it's introsort, but let me check

agile sundial
#

interesting. apparently for numeric primitives they used quicksort? but for other things they used mergesort?

#

in jdk7, at least

#

it seems to have not changed in jdk15

haughty mountain
agile sundial
#

it doesn't seem to have

haughty mountain
#

This algorithm offers O(n log(n)) performance on all data sets

#

this was different before

halcyon plankBOT
#

src/java.base/share/classes/java/util/DualPivotQuicksort.java line 38

* There are also additional algorithms, invoked from the Dual-Pivot```
haughty mountain
#
  • There are also additional algorithms, invoked from the Dual-Pivot
  • Quicksort, such as mixed insertion sort, merging of runs and heap
  • sort, counting sort and parallel merge sort.
#

this is some bs naming

agile sundial
#

huhh? bruh

low grove
marsh topaz
#

Hello! I am looking for a solution to a programming problem I am suffering

#

I am parsing another language using the Python Tree sitter bindings

#

However the output of those bindings is a class which is a problem

#

You see I want to convert the AST tree Treesitter outputs in to a graph DB

#

And I can't really do this to a class because I have no way to easily either a) serialize it or b) extract all the node vertex relationships

#

What would make it easy for me is if there were some unique way of referencing a node

#

So I thought to somehow add a field to the node class such that it has a unique ID

#

But python classes instances don't allow for this to happen.

#

Is there some object oriented programming technique where I can easily alter the behavior of this class?

#

I'd hate to have to go to altering the python tree sitter source code to change it's behavior, that would complicate my ability to support my tool using the library in the future

vocal gorge
marsh topaz
#

I tried that but for whatever reason the id of referenced children doesn't match up

#

Maybe some deep copying is going on somewhere, I have no idea

vocal gorge
#

huh, interesting

marsh topaz
#

I don't want to have to DFS the entire tree and copy it into a dict or something, it'd be super stupid wasteful memory wise

#

I'm planning on running this at very large source code

#

Alternatively is there a way to automatically extract all of the datafields from the objects to a dict?

vocal gorge
marsh topaz
#

That's the list. What I'm asking for is a library that will convert for me without me having to DFS the entire massive tree.

#

I know what fields I want, I just don't want to have to book keep the entire structure of the AST again redundantly.

#

I just want to rip out all of the fields of this gnarly nested class structure and put them in something mutable / serializable like a dict

vocal gorge
#

I don't think it's possible to do this without DFS. If you're concerned it'd be slow to write in Python for a massive tree, you might be right - you could make a compiled extension for it or something.

marsh topaz
#

That's soooo stupid though. Surely python has a way for me to forcibly decorate a class? Like, it'd be a lot less wasteful for me to just assign vertex IDs at the time of the original parse.

vocal gorge
marsh topaz
#

Yes

vocal gorge
halcyon plankBOT
#

tree_sitter/binding.c lines 167 to 178

static PyObject *node_child_by_field_id(Node *self, PyObject *args) {
    ModuleState *state = PyType_GetModuleState(Py_TYPE(self));
    TSFieldId field_id;
    if (!PyArg_ParseTuple(args, "H", &field_id)) {
        return NULL;
    }
    TSNode child = ts_node_child_by_field_id(self->node, field_id);
    if (ts_node_is_null(child)) {
        Py_RETURN_NONE;
    }
    return node_new_internal(state, child, self->tree);
}```
marsh topaz
#

I just feel like if I write a DFS over this giant object I am 1) going to run out of memory in some cases and 2) I am going to screw up the book keeping of something

#

And it's all kind of a waste just to preserve node to edge relationships

#

I'm converting this to Amazon Gremlin which has a CSV file for nodes and a CSV for edges (with ids of node parents and children)

#

I don't see a good way in that tree sitter API to do it without doing my own book keeping about where we are in the graph

vocal gorge
#

Yeah, that seems true. Ultimately, you want a representation that's basically a list of edges, whereas the library uses a graph representation. Converting between them needs a DFS.
(I'm not sure why you want to convert it to a nested dict instead - wouldn't you still need another pass afterwards to convert it?)

marsh topaz
#

I mean how else would I preserve the structure?

#

I need to do a pass over every node to give it an ID then I can get the parent and child ids of every node

#

therefore I need a representation of the tree with unique id's for nodes

#

If there's a way to do it with one pass I'm all ears but I haven't been able to conceive of one.

vocal gorge
#

This is always a tree, right? Guaranteed to not have e.g. nodes with more than one parent?

marsh topaz
#

Yeah

vocal gorge
#

In that case, wouldn't it always be the case that you'll always visit a node exactly once in a DFS/BFS? Every time you see a node, assign to it id i and increment i.

marsh topaz
#

Yeah but I have to store that id for later use somewhere

#

In a structure that preserves the tree?

#

If I just did it all in place then I'd have to keep track of my "parent" node at all times or whether I was inside a branch or something

#

I guess that's not so bad idk

vocal gorge
#

hmm, in addition, looking at the treesitter api... I think nodes have a unique id, actually

marsh topaz
#

It doesn't look like I can access them in python

vocal gorge
halcyon plankBOT
#

tree_sitter/binding.c lines 8 to 13

typedef struct {
    PyObject_HEAD
    TSNode node;
    PyObject *children;
    PyObject *tree;
} Node;```
vocal gorge
halcyon plankBOT
#

lib/include/tree_sitter/api.h lines 92 to 96

typedef struct {
  uint32_t context[4];
  const void *id;
  const TSTree *tree;
} TSNode;```
vocal gorge
#

although id is a pointer?? weird. anyway

marsh topaz
#

dir() doesn't list any id field

vocal gorge
#

It's indeed not exposed by the API, but you could read it via ctypes anyway, if you're willing

#

actually, hmm

halcyon plankBOT
#

tree_sitter/binding.c lines 194 to 196

static PyObject *node_get_id(Node *self, void *payload) {
    return PyLong_FromVoidPtr((void *)self->node.id);
}```
vocal gorge
halcyon plankBOT
#

tree_sitter/binding.c lines 501 to 502

static PyGetSetDef node_accessors[] = {
    {"id", (getter)node_get_id, NULL, "The node's numeric id", NULL},```
marsh topaz
#

Let me see if that works

vocal gorge
#

does node.id really not work? seems like it should

marsh topaz
#

it really doesn't

#

"tree_sitter.Node Object has no attribute id"

#

Neither is that function attached to node - node object doesn't have a node_get_id method

vocal gorge
#

huh, I don't understand why that getter doesn't get attached

#

might be a bug in the library, but I also don't see what's wrong

#

Are the others like node.is_named, node.has_changes, etc available?

marsh topaz
#

Yes

#

Both are.

#

Could it be hidden somehow?

#

It's not coming up under dir...

vocal gorge
#

so if it's hidden, it's not intentionally so

#

by the way

#

Are you using the latest version of that library?

marsh topaz
#

I'm using the version from pip

#

This is where I learn the hard way they don't update their pip releases isn't it?

vocal gorge
#

Quite possibly. Which one is installed?

marsh topaz
#

Whatever pip installs, I need to go remember how to summon library versions from pip

vocal gorge
#

pip list and pipe it into something like grep to get the right line, e.g. pip list | grep tree_sitter

#

(I don't know if there's another way)

marsh topaz
#

0.20

#

0.20.0

vocal gorge
#

Latest is 0.20.1 3 days ago, but it should be fine either way...

#

try updating, I guess?

marsh topaz
#

That did it.

#

Thank god, I was going to have to write some stupid code. Hopefully the parent children Ids line up now.

#

Let me check real quick....

vocal gorge
#

huh, it did??

#

that's wild, because 0.20 -> 0.20.1 was literally just a bump of the parent library version, no changes to the bindings

marsh topaz
#

Yeah that's mad weird.

#

Did the trick, though.

#

And the ID's line up. Yuss.

#

Thank you so much for talking me through that. I think I should be able to solve this efficiently now.

#

I may come back for DFS tips if I end up needing to do it the dumb way after all, but thank you.

vocal gorge
marsh topaz
#

Ah that makes sense.

#

Again, huge thanks!

safe jacinth
#

!e ```py
def partition(a, start, end):
p_index = start
pivot = a[end-1]
for i in range(start, end-1):
if a[i] <= pivot:
a[i], a[p_index] = a[p_index], a[i]
p_index += 1
pivot, a[p_index] = a[p_index], pivot
return p_index

def qs(a, start, end):

if start < end:
    p_index = partition(a, start, end)
    qs(a, start, p_index-1)
    qs(a, p_index+1, end)

return a

arr = [5, 16, 33, 7, 44, 20]

print(qs(arr, 0, len(arr)))```

halcyon plankBOT
#

@safe jacinth :white_check_mark: Your 3.11 eval job has completed with return code 0.

[5, 16, 7, 20, 20, 20]
safe jacinth
#

Why do I get three 20's in my newly sorted array?

haughty mountain
#

and shouldn't the swap with the pivot be using array indexing and not pivot?

#

seems those were the two issues yeah

#

!e

def partition(a, start, end):
        p_index = start
        pivot = a[end-1]
        for i in range(start, end-1):
            if a[i] <= pivot:
                a[i], a[p_index] = a[p_index], a[i]
                p_index += 1
        a[end-1], a[p_index] = a[p_index], a[end-1]
        return p_index

def qs(a, start, end):

    if start < end:
        p_index = partition(a, start, end)
        qs(a, start, p_index)
        qs(a, p_index+1, end)

    return a

arr = [5, 16, 33, 7, 44, 20]

print(qs(arr, 0, len(arr)))
halcyon plankBOT
#

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

[5, 7, 16, 20, 33, 44]
haughty mountain
#

I fuzz tested it a bit on randomly generated lists and nothing broke

#

though do note that your pivot picking means n² complexity on already mostly sorted data

pulsar light
haughty mountain
#

for each divisor of the board size, check if that size can tile the board, I guess