algos-and-data-structs

[haughty mountain]

(3 because the 0th element is the executable name)

[fiery cosmos]

!e
import sys

if len(sys.argv) < 3:
print('Too few arguments!')
sys.exit(1)

input_file = sys.argv[1]
output_file = sys.argv[2]

[halcyon plank]

@fiery cosmos :x: Your 3.11 eval job has completed with return code 1.

Too few arguments!

[haughty mountain]

I don't think you'll get many arguments running on here 😛

!e there should be 1, the script name

import sys
print(sys.argv)

[halcyon plank]

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

['-c']

[haughty mountain]

oh right, the docs mentioned that

[fiery cosmos]

hmm

how can i test if the filename exists upon user input

or like if they've keyed in a file that exists

nvm

[haughty mountain]

try to open it and fail :^)

there are other ways, but this is probably the more pythonic one

[fiery cosmos]

it just wasn't erroring right away but once you input an output filename it'll error at the command line

so one new thing i like (and im showing my age here) but you can simply go into the directory you want to run things in and open a command line (windows powershell) there and it'll default the cwd to the place you want, rather than trying to figure out how to navigate there via command line arguments

super convenient

[stone nova]

Is there an algorithm that does this for example : [0,1,1,1,2,2,3,4,4,5] to this [5,4,4,4,3,3,2,1,1,0] ?
The lists always start with 0

[haughty mountain]

what operation is this even?

5-x?

!e

your_list = [0,1,1,1,2,2,3,4,4,5]
print([5-x for x in your_list])

[halcyon plank]

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

[5, 4, 4, 4, 3, 3, 2, 1, 1, 0]

[stone nova]

It's a list representing node depths in a path of my graph, I want to reverse it.
Your method works I just need to put Max-x instead of 5
Thanks !

[amber dirge]

Can anyone explain whats going on in the highlighted portion for this solution to https://leetcode.com/problems/word-search/. Documentation for sum parameters says sum(iter, start) but counter() returns a dictionary and I thought start had to be an int

[haughty mountain]

Counter doesn't return a dict

it returns a Counter

Counter objects can be added

[amber dirge]

Thank you!!

[agile sundial]

and you can set the start to anything except strings

although i'm not sure if it errors if you add strings or set the start to a string 🤔

[amber dirge]

Neat!

[crystal shell]

Hey anyone doing DSA with Python?

[sonic jasper]

ask your specific question

[acoustic pawn]

hello if i have a loop like
for(int i=0;i<n * n ; i++)
what the time complixaty of it ?

[agile sundial]

n*n

[acoustic pawn]

can you explain ?

[stray fractal]

the loop is iterated over n*n times, so the time complexity is O(n*n) or O(n²)

[acoustic pawn]

interesting

thanq guys

i like your names BTW

[haughty mountain]

it's amusing that string is special cased

seems bytes is as well

[agile sundial]

yeah, i feel like that goes against python's philosophy of just letting you do what you want

let me be slow >:0

[haughty mountain]

fixed it

In [4]: class LetMeDoDumbThings:
   ...:     def __init__(self, s): self.s = s
   ...:     def __add__(self, other):
   ...:         return self.s + other
   ...:

In [5]: sum(['a', 'b', 'c'], LetMeDoDumbThings(''))
Out[5]: 'abc'

[agile sundial]

wild

huh, i wonder if it does isinstance(x, str) (or something that cares about subclasses). would str subclasses work?

[haughty mountain]

it does not work

[agile sundial]

weird

[fiery cosmos]

'''Draw the heap(s) after each neighbour of c has been updated and the
tree has been heapified (see the pseudocode in the lecture Slide 30, Week 9). If there
are multiple updates then draw multiple heaps, each of which is obtained after one
update. Note that neighbours are updated in the alphabetical order, e.g., d must
be updated before e. No intermediate steps, i.e., swaps, are required.'''

Can someone explain what this is asking to me

which multiple heaps is it referring to

do we do one update first, then correct the heap then another update and then correct again?

why not just update all at once and then correct the heap

[fiery cosmos]

depends on your input,
time complexity is measured relative to the input

for example,
if the input is an array of size N, then time complexity is quadratic -> O(N^2)
but if the input is an NxN matrix then time complexity if linear -> O(M), were M=NxN

[agile sundial]

n is clearly a number there

and it's kind of cheating to do that lol. you could just say matmul is linear

[haughty mountain]

matmul is linear in the amount of operations it does

[fiery cosmos]

depends on the algorithms they are using, but matmul is mostly atleas O(N^3)

[haughty mountain]

at most

unless you do something very silly to be worse than the naive way

[fiery cosmos]

a number can represent anything,

[fiery cosmos]

my bad, you are right

[fiery cosmos]

hey all,
what do the stars mean in CLRS?

in some of the problems, they are marked with a star symbol

oh nvm

| We have starred (★) the sections and exercises that are more suitable for graduate students than for undergraduates. A starred section is not necessarily more difficult than an unstarred one, but it may require an understanding of more advanced mathematics. Likewise, starred exercises may require an advanced background or more than average creativity.

[fiery cosmos]

Given:
an integer list "nums"

return:
an integer list "answer"
such that answer[i] is equal to the product of all the elements of nums
except nums[i].

in time complexity of O(n) and without using division

[fiery cosmos]

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

we can make an array of class instances right

in python

[glossy breach]

Calculate two arrays l and r, l[i] is product of first i elements of nums, r[i] is product of last n - i + 1 elements of nums

answer[i] = l[i - 1] * r[i + 1]

[halcyon seal]

bois if ihave a program like

if n = 5
return error;
for (int i = 0 ; i < n ; i++ ) {
iterate things
}

would i say this runs in omega(1) and O(n)? because in the case of n = 5 it runs in constant time?

[merry nova]

depends if n=5 is constant time

[halcyon seal]

what do you mean?
all the program will run if n=5 will check the if statement, and exit the program

[merry nova]

well depends on what language this is since it doesn't look like python

[halcyon seal]

well its java but i dont see how that changes things if its just checking an if statement and exiting, that would be O(1) no matter the language ❓

[merry nova]

assuming n is a primitive integer, then yeah

otherwise equality checks can be a custom implementation whose speed depends on the scale of n

[halcyon seal]

so just to verify you would say its O(N) and omega(1) (since checking if n=5 is constant time in this case)? just trying to wrap my head around this time complexity stuff

[merry nova]

seems correct, on the basis all operations inside the loop are constant time

[halcyon seal]

aight thanks 🙂

[fiery cosmos]

c(n)=2*c(n/2)+1. c(1)=0

Is this the correct reccurence relationship for this algorithm? Assuming addition as base operation.

[fiery cosmos]

Hi can someone please tell me if I have followed all the pseudo code conventions correctly here

[haughty mountain]

so the interesting questions 👀

[haughty mountain]

addition as the only base operation is nonsense, c(1) will be > 0

[haughty mountain]

it's not like pseudocode is standardized

you write a description that conveys what you are doing, if that gets across it's good pseudocode

most of the time writing super detailed pseudocode is just a waste compared to just writing an actual implementation, the power of pseudocode is imo in being able to abstract stuff away

[brazen lodge]

is it allowed to post my bruteforce code (just guessing a random generated string)? im curios if there is any room for improvment (im sure there is) based on performance

[haughty mountain]

like, "do X this many times"

without spelling out the exact details of X

[native stirrup]

can anyone help me in this question

[agile sundial]

have you tried anything

[native stirrup]

yup i have tried conditional statement but it went wrong for 2 test cases

[agile sundial]

what did you try

[native stirrup]

this

its uploading

currenlty the output is correct but with anothers test cases its wrong

[agile sundial]

you're only checking the case where a and b are right next to each other

[native stirrup]

so like whats the approach

[agile sundial]

what do you think? have you tried anything?

[native stirrup]

i m fully blank

nothing is comming into my mind

what can i do

i have tried solving it in notebook, but its running for the sample test cases

[agile sundial]

do you understand the case I'm talking about?

[native stirrup]

should i compare a1, with every element and the a2 with every element

[native stirrup]

no

[agile sundial]

actually, your code doesn't even work for that case, nevermind

do you understand the question itself?

[native stirrup]

yup dude

[native stirrup]

this is running correctly

[agile sundial]

a1 == b2 is only possible if a==b. in the elif, the first condition is fine but the second checks a1 == b2 again.

[agile sundial]

secondly, a and b can be any distance apart, you can apply any number of steps

[native stirrup]

sorry cant understand

[agile sundial]

if your input was 0 100 1, your code should return true, but it doesn't

[native stirrup]

sorry to ask but can you please help with the coding part

I will understand when i see the code

and try make it myself

[agile sundial]

I can't right now

[native stirrup]

atleast tell me the right approach for this then

[agile sundial]

you already have a correct approach, you're just not checking all the cases

and it might be too slow, but that's a different question

[haughty mountain]

isn't the solution trivial?

[agile sundial]

yes (i think, at least)

[native stirrup]

output for this is No

and thats correct as per my code

[haughty mountain]

it should be Yes

[native stirrup]

why ?

and how

[haughty mountain]

you can apply the operation 50 times

to get 50 50

[native stirrup]

cant get it

try to explain in another word

[haughty mountain]

you can repeatedly apply the operation a+1 b-1:
0 100
1 99
2 98
...
50 50

[native stirrup]

yeah i got this, but how ?

[haughty mountain]

wdym how?

[native stirrup]

i understood this code, thanks

[native stirrup]

i m just a beginner, sorry

[haughty mountain]

so in the end this is more of a math problem than a programming one

the question boils down to if this is true for any n

a + n*x == b - n*x

[native stirrup]

where did n come from ?

[haughty mountain]

||difference mod 2x||

[haughty mountain]

I made it up. It's the number of times you apply the operation

[agile sundial]

yeah, ||abs though, it doesn't specify an order||

[haughty mountain]

||abs doesn't matter||

[agile sundial]

oh right, because ||%||

[haughty mountain]

yep

[fiery cosmos]

the ones that everyone is googling /s

i'm working on CLRS 7-5, it's actually quite interesting

[fiery cosmos]

i'm going to need some help adding argparse to my program, i'm reading the documentation now

i'm getting:
with open(outputfile,'w') as output: TypeError: expected str, bytes or os.PathLike object, not _StoreAction

hmm

seems i am not handling the files as text files properly

i'm trying to implement a command line argument like:
python myalgo.py input.txt output.txt

here is some code:

parser = argparse.ArgumentParser()
inputmatrices = parser.add_argument("input", help="pass the input .txt document")
outputfile = parser.add_argument("output", help="name the output .txt as you wish")
args = parser.parse_args()

then the function gets called on the last line

then its defined like this:

def matrixmultiplier():
    multiply_counter = 0
    with open(outputfile,'w') as output:
        with open(inputmatrices) as f:

[haughty mountain]

I would say don't bother with argparse unless you really want to learn it

you could just take two positional arguments

[fiery cosmos]

i don't but last night they said i had to call my function like that

i mean not w argparse specifically

but they didnt want me prompting the user for input

so you're saying they can just do python myalgo(input.txt,output.txt).py

[haughty mountain]

wrong syntax

I gave an example a bit back

[fiery cosmos]

like this:
python myalgo.py input.txt output.txt

?

[haughty mountain]

this + another one a bit down from that

yes

[fiery cosmos]

well yeah that's what im trying to implement with what i've outlined above

[haughty mountain]

argpase is super overkill

[fiery cosmos]

is there a way to make it work with this syntax:
python myalgo.py input.txt output.txt

without argparse?

[agile sundial]

yeah if you're just passing 2 file names just get them from sys.argv

[haughty mountain]

as I said, I gave an example

[fiery cosmos]

oh, my bad. i was conflating sys.argv w argparse

[haughty mountain]

argparse is for parsing flags

[fiery cosmos]

oooh

[haughty mountain]

e.g. program --someflag value_of_flag

[agile sundial]

and iirc it lets you do things like short versions, mutually exclusive flags, and other fun stuff

[haughty mountain]

yeah

if you just need a few positional arguments argparse isn't helpful

[fiery cosmos]

oof ok. tysm

[haughty mountain]

I think it even parses out the flags and returns the positional arguments as a list

and you're back in the same situation as with argv and just positional args

positional arguments are easy, flags are hard, hence argparse exists for the hard part 😄

[fiery cosmos]

yeah i've already fixed them both up utilizing sys.argv and tested and they're running properly with the outs and everything. tysm

[native stirrup]

@haughty mountain@agile sundial

[agile sundial]

good job. although, is this a running contest?

[native stirrup]

now its finished

I solved 4 problems

[haughty mountain]

please don't ask questions during a running contest in the future

(not that it matters much for the third easiest problem in a div 4 contest)

just (a - b)%(2*x) works

no need to care about sign

[native stirrup]

Sorry and Thanks

[haughty mountain]

it's been a good while since I looked at codechef

div4 problems are quite boring if you're used to div1 problems

[fiery cosmos]

anyone know why this isn't erroring:

lena = len(matrixa)
lenrowb = len(matrixb[0])
if lena != lenrowb:
  print("incompatible matrices", file=output)
  return

im reading an error input file where the rows and columns are not equivalent

its just not printing anything to my output file

i also tried like this:

lena = len(matrixa)
lenb = len(matrixb)
lenarow = len(matrixa[0])
lenbrow = len(matrixb[0])
if lena != lenbrow or lenb != lenarow:
  print("incompatible matrices",file=output)
  return

[haughty mountain]

could you print matrixa and matrixb?

[fiery cosmos]

hm no it doesn't want to print anything now

im sure its bc of the way im trying to read the in

i just want a simple check to make sure the inputs are not incompatible (simple error handling measure)

[haughty mountain]

as in you aren't even able to print the matrices? i.e. this code doesn't even run?

[fiery cosmos]

it does but not when i put that check in my while True statement

[haughty mountain]

so...can you print matrixa and matrixb?

you're saying that the thing doesn't trigger

knowing what the matrices in the variables are would be helpful to debug

[fiery cosmos]

lms

i could show you what im inputting but im unable to print the matrices as they exist after being read in, unless there is a print to standard out function

[haughty mountain]

unless there is a print to standard out function
so print

[fiery cosmos]

the thing totally breaks when i go and enter new lines in my algo, bc of the hackneyed way im reading the input file

recall i have all those error handling at the end just to get the thing to continue to read

[haughty mountain]

wait, how tf does your code break from printing?

[fiery cosmos]

great ?

it doesnt crash it just never executes properly nor prints anything to the file or back to the command line

hang on

yeah no it doesnt want to print to stout

🤷‍♂️

[haughty mountain]

could you share your code? what you are saying here makes no sense to me

[fiery cosmos]

i'll have to pm

[fallow garnet]

Why is this giving the "TypeError: 'int' object is not iterable" error?

s = "rjgne&;#!23"
k = [1 for char in s if char.isdecimal()]

print(k)

Expected result:
[1, 1]

[jolly mortar]

!e

s = "rjgne&;#!23"
k = [1 for char in s if char.isdecimal()]

print(k) 

[halcyon plank]

@jolly mortar :white_check_mark: Your 3.11 eval job has completed with return code 0.

[1, 1]

[fallow garnet]

Hmmm

It doesn't work for me for some reason

Nvm, I had assigned the variable s to something else

[arctic ginkgo]

How do I go on about doing this without using range?

[haughty mountain]

a bunch of casework

the zero and empty case are very easy to detect

positive/negative is if you have even or odd amount of negatives

that's where you have like 6 cases

in the ways the intervals can intersect/not intersect

[stuck wind]

hi guys, can someone explain to me how this "rotate array by N elements" work? I understand the part when the rotations are positive so the array is rotated right ways. But when the rotations are negative how does this code take than into account?```python
def reverse_array(nums, start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1

def rotate_array(nums, n):
length = len(nums)

# Normalizing the 'n' rotations, I dont' get this part 
n = n % length
if n < 0:
    n += length

# reversing the whole array
reverse_array(nums, 0, length - 1)

# fixing the order of the rotated n elements
reverse_array(nums, 0, n - 1)

# fixing the order of the remaining (l-n) elements
reverse_array(nums, n, length - 1)

return nums```

[cinder nebula]

if you have a list that's 5 items long, but you wanna rotate it by 5 items, it'll end up back how it was originally, so its the same as rotating it by nothing at all. similarly, rotating by 6 is the same as 1, etc, which is where the n % length part comes from.
In addition, sticking with this list of 5 elements, a rotation of -1 places (1 going the other way) is equivalent to a nornal positive rotation of 4, which can be figured out by adding on the length (-1 + 5 = 4), since we already know that adding on a full rotation doesn't affect the outcome

[arctic ginkgo]

I dont get it.

[haughty mountain]

you have two ranges l...r and d...u and you need to figure out what's left when you take away d...u from l...r

and doing that kind of interval work is kinda fiddly

the intervals can intersect in various different ways

[arctic ginkgo]

Ye but like how will the program figure out whats left betweeen l and r.

after d and u.

That is what I dont get

[haughty mountain]

math and logic

[arctic ginkgo]

Like how will the program know that there are 2 positives, 1 negative and 1 zero within l and r.

Without using range

or loops.

[haughty mountain]

that part is easy, e.g.
l=-3, r=5
has 1 zero, 3 negative and 5 positive

[arctic ginkgo]

Yes but like I know that but how will the program know.

Idk what to write. Shit.

[haughty mountain]

how do you know?

[arctic ginkgo]

Bcz I j counted the numbers

[haughty mountain]

ok, l=-123456 and r=456789

can you solve this by hand?

if so you should be able to translate the same process to a program

[arctic ginkgo]

But like Im only suppose to input l and r in the program

so like l = -3 and r = 2.

And lets say Dan chose

d = -2 and u = 1.

Angela is left with

-3 and 2.

How will I do that.

[haughty mountain]

you think in ranges of numbers

e.g. if you have -10...10 and you cut out -3...2 you're left with two ranges -10...-4 and 3...10

[arctic ginkgo]

But like how will you do that without the help of range

[haughty mountain]

math

think about how you would be solving the problem by hand and then you can start to try to translate that process into a program

[arctic ginkgo]

Omg I cant think of anything.

Imma give it another try later.

[haughty mountain]

if you can't solve it by hand, at least in principle, you won't be able to solve it with a program

[arctic ginkgo]

On paper. I would just list all the numbers within that range and then get the product?

of those numbers.

[haughty mountain]

why do you need the product?

and do you actually need to list all the numbers in the range?

[lapis rune]

I've been trying to prepare for technical interviews coming up in a couple of weeks and ive been using algo expert, leetcode, etc. Everytime I try to solve a problem by myself, my solution either solves some of the test cases or non at all and I end up looking at the discussion board for the answer or looking at the code walkthroughs. I dont know how to gauge my progress if Im making any at all and I wanted to ask whats a good way to know if Im prepared for the interviews or not.

[spiral raptor]

From personal experience, you'll never know if you're prepared or not, and doesn't really matter tbh.
Just keep on practicing and studying, and keep on applying for interviews.

[lapis rune]

but if im unable to come up with a working solution to the problems within the timeframe while Im practicing, wont that reflect during the actual assessment?

[spiral raptor]

Sure, it'll reflect on your actual assessment.
But, what I'm trying to say is, there isn't much you can do besides keep on practicing interview questions (by using the platforms you've mentioned above, and more) - and if you put the effort and have patience, you'll get better at interviewing in general.

[agile sundial]

try to figure out why you're not getting the solution. if you can determine a few reasons, then you've found a few areas to improve in

looking at the solutions can help with this, think about what they're doing differently, what techniques they use, what data structures, algorithms, etc.

[haughty mountain]

when learning, it's not mainly about "how do I solve this"

but rather "how does one arrive at this solution"

i.e. problem solving techniques for breaking down a problem and applying some basic cs concepts to solve it

[wind jewel]

and “what/why to solve” is the driving factor…

[tacit nova]

can i write

SET = set()

my friend said this override something

so its bad practice

[cinder nebula]

it won't override anything (python is case-sensitive, so SET is a different variable than set), but at the same time, do bear in mind that FULL_UPPERCASE is the convention for saying that a variable should be constant

If you're planning on keeping SET as just a constant set, then go ahead. Otherwise, if you're wanting to edit the variable later on, i'd maybe give it a different full_lowercase-style name

[tacit nova]

make sense, at the moment i am asking this for Leetcode purpose so i will keep doing SET. I will think of a better name in actual project like user_set

[native stirrup]

It was a contest question on codechef

its wrong brother also the TC is not good

[fallow garnet]

How can I check if specific key values in a dictionary are the same?

d = {"1":"a", "2":"a", "3":"a", "4":"b"}

valid = [["1","3"],["2","4"]]

#if key 1 and 3 values are the same, return True or if key 2 and 4 values are the same, return True, else return False 

[cinder nebula]

do you want a method using any() with a generator expression, or do you want a method using a for loop?

@fallow garnet

[fallow garnet]

For loop is ideal

[cinder nebula]

alright, and is it always gonna be comparing whether a pair of keys are equal, or could there possibly be more? e.g. whether 3 keys are equal

[fallow garnet]

Could possibly be more

Like 3 valid keys

Ideally 3 valid keys actually

The dictionary can also be bigger

Amount of valid keys can also be more

d = {"1":"a", "2":"a", "3":"a", "4":"b"}  #can have more key value pairs 

valid = [["1","3","5"],["2","4","3"],[any amount of more brackets can be here]]

#if key 1, 3 and 5 values are the same, return True or if key 2, 4 and 3 values are the same, return True, else return False 

[cinder nebula]

hmm, well in that case, the first thing to deal with is probably simply whether a single given list of keys are all equal

[fallow garnet]

So check each valid combo one by one?

[cinder nebula]

uhh yeah, sorta

[fallow garnet]

That's gonna be a lot of code

[cinder nebula]

it's a fair amount, but its also quite a complex thing to check

[fallow garnet]

True

[cinder nebula]

what i'd perhaps do is begin by checking what the value given by the first key is, and then for the remaining keys, check whether they're equal one-by-one

and if any one isn't, you know that list of keys isn't equal, so you can move on to the next set

[fallow garnet]

Makes sense, well thanks for the suggestion

[fallow garnet]

@cinder nebula I was finally able to solve the problem with minimal code by using value index instead of value keys in place of valid combinations

[dark aurora]

How to meausere time in my code

I looke it up but it is all confusing and doesn't work

I need to time this code

n, m = list(map(int, input().split()))
lst = [list(map(int, input().split())) for i in range(n)]

#test this
def test1(lst, n, m):
    arr = []
    for i in range(n):
        d, p, o = lst[i]
        arr = arr+[(d, 1)]
        arr = arr+[(d+o, -1)]
        arr = arr+[(d+p, 0)]
    return arr

#test this
def test2(lst, n, m):
    arr = [j for i in range(n) for j in [(lst[i][0], 1), (lst[i][0]+lst[i][1], 0), (lst[i][0]+lst[i][2], -1)]]
    return arr

#compare test2 and test1 which is faster

[haughty mountain]

start = time.perf_counter()
<code here>
end = time.perf_counter()
print(f'Elapsed: {end - start}s')

[dark aurora]

What do I need to import for that

[haughty mountain]

have a guess

[dark aurora]

time

[haughty mountain]

yep

[dark aurora]

It's super late and I am thinking on autopilot sorry

[fiery cosmos]

lol

[burnt wind]

Hey 🙂 What's better to use to solve the following task in Python 3.10? I need search small wav files inside a big file and output where every small file begins (in minutes and seconds) inside a big audio file.

[native stirrup]

Are u a python developer

[sturdy sierra]

anyone know why this is giving an syntax error

[fiery cosmos]

wish i did

[azure osprey]

What format is this?

Are you reversing it?

[haughty mountain]

seeing Solution(object) suggests this is python 2 and not python 3

[burnt wind]

Big file is a wav file too

[azure osprey]

WAV can't embed other WAVs inside it last I checked

It must be some container format

[burnt wind]

I didn't mean that one wav is embedded inside another. 🙂 I just mean that I have the big wav file and wanna find parts of it which match the content of another wav files. Like recognize song via shazam

[azure osprey]

Ohh

[grand marten]

what application can you use bogo sort to resolve a problem xD

[fierce patio]

guys please help this question (python solution)
https://leetcode.com/problems/remove-duplicates-from-sorted-array/

why this is not working ?

[summer fossil]

How to start dsa in python

i need a roadmap

[haughty mountain]

you're not doing it in-place, you're not maintaining relative order

[summer fossil]

https://tenor.com/view/hello-marketeros-hello-hello-mk-marketeros-gif-23167600

[marsh ermine]

try this out

def runningnums(nums):
return [sum(nums[0:i])for i in range (1,len(nums)+1)]

[shut breach]

check the pins

[summer fossil]

Thanks!

why python dsa has less resource in utube

[shut breach]

dsa is mostly the same regardless of the language you use

[summer fossil]

irst Negative Number in every Window of Size K

How to approach

need brute force approach

[native stirrup]

can anyone help me out with DSA part, I can't find free and best resource to learn DSA from python

[stone ruin]

Try these

Mobile App
AlgoExpert

The awesome github.com python repo

[native stirrup]

@stone ruin ??

[stone ruin]

Try your app store for AlgoExpert

[native stirrup]

app store

?

i really can't get it

[stone ruin]

Google play store

You know, where you find apps

Focus my dear

This is for keeping you away from candy crush

[native stirrup]

i think that app is not for us

can u share the app link in DM

[stone ruin]

In Google type "site:github awesome python repo"

[stone ruin]

Not by me

You can type, right?

[haughty mountain]

Just use a queue

[quartz urchin]

Hi community! Glad to be here

I have a doubt. I need to measure the time complexity of some methods. Which is the best practices to do that?

I mean, hhow can i measure the big O complexity of a method in a class?

[shut breach]

You typically wouldn't determine the time complexity experimentally, you would analyze the function by hand.

[quartz urchin]

Thanks! Can I share to you a bit of code and help me to understand why is not a Linear function?

[shut breach]

sure

[quartz urchin]

I understand that, if values_added list grows, the iteration time complexity grows linearly

But somebody tolds me that is incorrect

told*

[agile sundial]

sorting is n log n in general

[shut breach]

in when checking a list is linear itself

so that's another thing iterating

[vocal gorge]

only if values_stats is a list

looks like it's a dict, since the code does if elem not in values_stats and then values_stats[elem]

so I don't see anything bigger than sorting here

[shut breach]

yeah that's true

[quartz urchin]

So, the only thing that convert this method in a O(nlog) is the sort? besides that, is a O(n) method, right?

[shut breach]

technically we don't know because we don't know the types of some things like self.values_stats, but yeah, otherwise it looks linear

[fallow garnet]

Someone help me understand this problem

[cinder nebula]

it wants you to generate a whole lot of random coordinates within that square, tally up how many land inside the circle, and use that to somehow calculate an approximation of pi

[covert thorn]

!d random.uniform
you can use this to generate the numbers

[halcyon plank]

random.uniform

random.uniform(a, b)```
Return a random floating point number *N* such that `a <= N <= b` for `a <= b` and `b <= N <= a` for `b < a`.

The end-point value `b` may or may not be included in the range depending on floating-point rounding in the equation `a + (b-a) * random()`.

[fallow garnet]

I don't understand that somehow part cuz I'm not good at math, I can only write the code for it if I know what I'm supposed to do step by step

[cinder nebula]

well, given an input N, you want to: ```

• create a counter, starting at 0
• for N times:
  • make a random floating-point coordinate pair between (-1,-1) and (1,1)
  • see if it falls inside of the circle
    • if it does, increment the counter by 1

[fallow garnet]

How do I know if it falls inside the circle?

[cinder nebula]

since the ratio of the area of the square : area of the circle is 4 : pi, you should expect about pi/4 of them to fall within the circle

[cinder nebula]

in your math class, have you covered what the equation of a circle is?

[fallow garnet]

Never attended any math classes to begin with

[cinder nebula]

damn, fair enough

in that case, are you familiar with the the pythagorean formula?

[fallow garnet]

Nope

The name sounds funny

[cinder nebula]

its the formula you use to figure out the long side of a right-angled triangle

[fallow garnet]

I see

Interesting

[cinder nebula]

well, its also useful for finding out the distance between two points

[fallow garnet]

Hmmm

No idea how that formula works

[cinder nebula]

well, with this circle, we know its radius is just set to 1

[fallow garnet]

Ye

[cinder nebula]

so all of the edge of the circle is exactly 1 unit away from its centre

[fallow garnet]

True

[cinder nebula]

therefore, any points inside the circle are less than 1 unit away from the centre

[fallow garnet]

I see

[cinder nebula]

so, the way we can figure out whether a point ends up in the circle is to find its distance from the centre

[fallow garnet]

Isn't the center 0?

[cinder nebula]

yep

[fallow garnet]

I have no idea how I'm gonna calculate that using n amount of x and y pairs

[cinder nebula]

well, you only have to worry about doing the coordinates one-by-one

so really, your job is, given a pair of (x,y), coordinates, find out how far it is from (0,0)

[fallow garnet]

I see

Bot x and y can be -1, 0 or 1

Yes?

[cinder nebula]

x and y can both be any number between -1 and 1

e.g. 0, 0.3, -0.412, 0.99998, etc.

[fallow garnet]

Oh

How do I generate numbers like that?

[cinder nebula]

thurisatic said further up above, random.uniform will generate you random numbers between two given numbers

[fallow garnet]

I see

Got that

I need to know the formula for putting those values in

[cinder nebula]

mhm

what you're looking for is the formula for finding something called the euclidean distance

[fallow garnet]

I see

What's the formula for it?

[cinder nebula]

given a pair of coordinates (x1, y1) and (x2, y2), the formula looks like this:

[fallow garnet]

I see

[fallow garnet]

That formula but for n amount pairs?

[cinder nebula]

nono, this is something you wanna do in a loop for each individual set of coordinates

[fallow garnet]

Oh

[cinder nebula]

where one of your coordinates pairs is the randomly generated set, and the other is (0,0)

[fallow garnet]

Ah

[cinder nebula]

(btw, that last part actually simplifies the formula a little)

[fallow garnet]

Ye

That part is nothing

[cinder nebula]

so really, you've got a coordinate pair (x,y) and the formula (when you get rid of the - 0s) looks more like:

[fallow garnet]

Doesn't the square cancel out the root ?

[cinder nebula]

kinda?

you're squaring the numbers, adding them together, and square rooting it

it's a different value than just x + y though

[fallow garnet]

Oh

Now I have a distance

For 1 n

Now what do I do with that distance?

[cinder nebula]

now we've got the distance, we can compare it to 1 to figure out if its in the circle or not

so if its less than 1, we know its inside the circle, and we can add 1 to our "points inside the circle" counter

[fallow garnet]

That simplifies things a lot

An example for the code

pair_list = n amount of generated pairs 

Counter = 0

For i in pair_list:
    Put the pair in formula to get distance
    If distance < 1:
        add 1 to Counter

Print counter as amount of values inside the circle 

Is that how it's supposed to go?

@cinder nebula

[cinder nebula]

yeah, that could work

i'd personally opt to put both the coordinate-generating and the distance-calculating within the same for i in range(N): loop, since then you don't have to allocate all of the memory to store, say, a million pairs of coordinates at once

and also, you still need to do something with that counter to calculate your approximation of pi

[fallow garnet]

Ah yes , that makes sense

[fallow garnet]

What am I supposed to do with the counter?

[cinder nebula]

so

the odds of a pair of coordinates landing within each shape is relative to its area

so, since we know the square has an area of 4, and the circle an area of pi, we should expect the ratio of total points we make versus the total points within the circle to be approximately 4 : pi

or in other words, given N points generated, pi/4 of them end up in the circle

[fallow garnet]

I see

Where does the counter come in that?

[cinder nebula]

well, in other words, approximately, counter == N * (pi/4)

with a little bit of rearrangement, given the values of counter and N, you should be able to figure out pi

[fallow garnet]

Let's say I got a counter of 13

What do I do next?

[cinder nebula]

well, let's say we set N to 100, and counter ends up being 78

[fallow garnet]

Ye

[cinder nebula]

so 78 = 100 * (pi/4)

here, can you rearrange this to figure out pi?

[fallow garnet]

So (78/100)*4 = pi?

[cinder nebula]

mhm

and so that's our approximation, which works out to be 3.12

[fallow garnet]

So (counter/n)*4 = approximation of pi?

[cinder nebula]

yup

[fallow garnet]

Got it

Thanks

[weak tulip]

How do I learn algorithms and data structures for python

?

[static bough]

For this question https://leetcode.com/problems/jump-game-vii/ and for the test case
s = "01", miniJump=1, maxJump=1
Why it is False?

Whereas when i=0 --> 1 <= j<= 1 (Using given formula) and I reached to s.length - 1 then isn't it is True ?

[mild galleon]

This
a, b = 3
Mean
a=3; b=3?

[shut breach]

this channel is about algorithms and data structures, but you can open your own help channel from #❓｜how-to-get-help

[mild galleon]

Ок

[sullen summit]

does anyone here understand A* tree search?

I'm trying to implement it in python but I don't really understand the theory too well

[agile sundial]

sure

[languid swift]

hi everyone i am not a native english speaker but i will try to explain my trouble
I want to know how to learn algorithms and data structures

is it better to understand the concept of each algorithm or what

[agile sundial]

as opposed to not understanding?

[languid swift]

my question is : is it better to understand (only) the concept of each algorithm ?

[cinder nebula]

what do you mean by "understand the concept of each algorithm"?

[languid swift]

i want to know how to learn algorithms

[cinder nebula]

I wouldn't really consider there to be a technique to learning algorithms, beyond being able to remember their names, pros and cons, and general structure/pseudocode

if you're learning them for some school course, then they might be expecting you to remember how to write one in at least pseudocode. On the other hand, if you're just wanting to learn them yourself, then i wouldn't worry about memorising them fully as much

[fiery cosmos]

how do you go about
implementing an algorithm from research papers ?

[fiery cosmos]

get familiar with all common data structures, and algorithms implemented using them,
and know their advantages and disadvantages in terms of time and space complexity for common operations (search, lookups, insert, etc.)

the key is to solve as many problems using common algorithmic problem solving techniques (recursion, dynamic programming, brute force, etc.), until you are comfortable using those approaches.

[fiery cosmos]

greedy algos

[half lotus]

You should be asking this in #career-advice instead

[last fulcrum]

Hi guys. I can't seem to understand this specific syntax originalToCopy[curr.next] for this question
Copy List with Random Pointer (https://leetcode.com/problems/copy-list-with-random-pointer/)

This is the full code

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        originalToCopy = { None: None }
        
        curr = head
        while curr is not None:
            originalToCopy[curr] = Node(curr.val)
            curr = curr.next
            
        curr = head
        while curr:
            copy = originalToCopy[curr]
            copy.next = originalToCopy[curr.next]
            copy.random = originalToCopy[curr.random]
            curr = curr.next
            
        return originalToCopy[head]

My understanding of python dicts is that we key into them to get the value. But if you look at the code above originalToCopy does not have a value for the curr.next key. Can anyone tell why the code still works?

[ruby quail]

In the first loop the dict is populated with every node.
curr.next will point to the next node. Since all nodes exist in the dicionary it will just look up the nodes value from that dict

A(1) -> B(2)-> C(3) will be stored as {A: 1, B: 2, C:3} . A.next is just B and B is in fact a key in the dictionary

[last fulcrum]

Thank you. That makes sense

[hollow forge]

I have to understand the HyperLogLog article and then be able to use HyperLogLog in Java. However, the article seems chinese to me.

I don't need to understand the technical proofs they make. More about how it is implemented and what it actually does.

How can a beginner understand HyperLogLog? Does anyone have a good video/article/book that can help explain it more simply?

https://www.researchgate.net/publication/29598188_HyperLogLog_The_analysis_of_a_near-optimal_cardinality_estimation_algorithm

[fiery cosmos]

dunno why but you cant access dicts from f stirngs

i just realised this is 2 days old

lol

[agile sundial]

>>> d = {1:2}
>>> print(f"{d[1]}")
2
``` yes you can

[spiral raptor]

A research about programming languages and their energy consumption
(https://medium.com/codex/what-are-the-greenest-programming-languages-e738774b1957)

And their execution time

[agile sundial]

lua slower than python?

[spiral raptor]

Apparently so, I wasn't aware of that at all either

And Haskell being faster than Swift also got me very surprised

[amber inlet]

geth init --datadir node1 genesis.json

[wind jewel]

I dont rely on this report because energy levels are always different and so the level of comprehension...this approach proves nothing...

[agile sundial]

incomprehensible, have a nice day

[wind jewel]

The speed at which they are executed in the energy consumption is usually decisive, but not always the one that runs the fastest is the one that consumes the least energy as other factors enter into the power consumption equation besides speed, as the memory usage.

hence proves nothing from both perspectives..

[native stirrup]

You have an array A of length N. In one operation, You can remove any one element from the array. Determine the minimum number of operations required to make all the elements same
Sample Input:
3
3 3 3
1 3 2 1 2 2
1 2 1 2
1 3 2 4 5
samplt output:
0
3
2
4

[fiery cosmos]

how are greedy and dynamic programming different? how are they related

[agile sundial]

greedy only tries to make the locally best choice, dp uses previous results to produce an optimal result

[lapis rune]

How important is solving the problem with the most optimal solution during a coding interview?

[native stirrup]

t = int(input()) for i in range(t): n = int(input()) m = list(map(int,input().split())) count = 0 for i in m: if m.count(i)>count count = m.count(i): print(n-count)
how to make this code more optimize

[agile sundial]

what does it do

and is this for a competition

[native stirrup]

yeah

[agile sundial]

[native stirrup]

it is giving correct output

but time limit is exceeding in one test case

[agile sundial]

didn't you get told not to ask for help with active competitions

[native stirrup]

🙂 bro my solution is correct just tell me whether it can be more optimized or not, coz i m able to do that

[agile sundial]

that's still helping though 🤔

[fiery cosmos]

did anyone ever read the Hypercube Algrithm for the 0/1 Knapsack problem (1988)?

might be of interest to people here, it's all greek to me

[fiery cosmos]

don't try to go hiking with a greedy algorithm guiding you 😆

[pallid cape]

Hello, I am having trouble with some code I am building. I was wondering if anyone is available for some simple guidance.

I can post here if that would be helpful

def damage():
    assault = [a1,a2]
    barrel = [barrel1, barrel2]
    if damage == "Damage":
        return
    # Compare the stats
    while(True):
        assaultMaxDamage = max(d['Damage'] for d in assault)
        assaultMinDamage = min(d['Damage'] for d in assault)
        if assaultMaxDamage > assaultMinDamage:
            print(assault.items())
            break

I would like to return the item that has the most damage. I thought you can return items, however this is dictionary aparently and now I am having issues with it needing to be "sliced". I don't think I was doing too poorly, but this is kind of rediculous.

If 'fist' is the highest damage resulting list, i would like to return that list after the program determines what is the highest damage weapon. The result should look like:

Weapon fist
Damage 73
Fire Rate 80
Range 59
Accuracy 72
Recoil 79
Mobility 54
Handling 51

[peak wolf]

What's going on here?

[pallid cape]

a lot

[fiery cosmos]

how did you get set notation in your name

[peak wolf]

So, you have a collection of items, with several properties each, yes?

[pallid cape]

yes, there are a total of 7, combination of strings and integers

[spiral raptor]

That makes total sense

[pallid cape]

I just dont know the if or for or while statement needed in order to achieve the result, which would be in plaintext "return the item name and relevant stats that has the highest damage". However I dont really know what I am doing, I started learning about 4 weeks ago

I thought you could find the damage, then return 'assault', but that leads to an error where I cant return the information

[peak wolf]

So surely you have a class for your weapons, no?

[pallid cape]

no there is no class, I have 2 weapons

I have 2 weapons, and the algorithm needs to choose between the 2 weapons.

I am doing this for a game i was playing and it would help if I get this part all down

@peak wolf any clue?

[peak wolf]

Okay, so assault is a list of [a1, a2], what are a1 and a2

[pallid cape]

i dont think it would matter, the result is a1 and a2 can be whatever with the same keys but different values, whats important is that the values are lower than a1

i actually have to go but I will ping you when I amback

have a good day!

[fiery cosmos]

i just learned about using a novel as the basis for a frequency table to give rise to huffman encoding, pretty cool!

[frank hamlet]

Is there any course you guys recommend to get a hold on DS?

[tacit nova]

python dead last

[tacit nova]

for me i just go ahead and do Leetcode; i got stuck a lot at first but now ik enough
still lack theoretical knowledge but hey i think practical knowledge matters more

[haughty mountain]

speed is basically everything, you want to get your work done on the cpu quickly so it can go to rest as quickly as possible

[worldly lava]

hi i need help with this

Create a console program for stack class that will perform the following:

• The stack will only allow to accept maximum of 10 data items on the stack.

• The stack will only accept integers

[worldly jolt]

assuming I have an instance "this" of class "a" that has a copy operator, and a class "b" decorator/class I want to inherit, is there a way for me to create an instance "this" of type (b,a)?

[half lotus]

What do you mean by a copy operator? As in __copy__() is defined? Or you have some custom copy method?

[worldly jolt]

Yea the __copy__() is defined

[half lotus]

I can't think of an easy way to do it then. Problem is that __copy__ is going to try to instantiate the original class rather than the subclass.

I guess there are hacky solutions like ```py
a = A()
a.class = AB
ab = AB.copy(a)

Assuming 
```py
class A:
    def __copy__(self):
        return self.__class__()

Much less hacky would be to define a new method in AB that takes an A instance and creates an AB, but that would effectively be re-implementing what A.__copy__ does so it's redundant code.

[worldly jolt]

That's spicy lol, I was also flirting with the idea of messing with AB's bases

[half lotus]

Hmm thinking through this again I think I have a decent solution. One moment

[worldly jolt]

The problem is that A needs to be generic where as b is my code

[half lotus]

Never mind, what I had in mind does not work as I expected.

[worldly jolt]

like you said

a.__class__ = AB
ab = AB.__copy__(a)

would prob work

I just think it's ugly

[half lotus]

Yeah I did test that before I sent it and it does work

[worldly jolt]

ty

[half lotus]

Yes it's ugly and hacky

Right now the only nice solution I can think of would require effectively re-implementing the copy in the subclass, but that leads to redundant code and I assume your question is posed because you precisely want to avoid that

[worldly jolt]

I cant do the redundant code approach because a is generic in my case

like I have a,b,c,d,e.... instances

that all have a __copy__

and I want to "decorate" them a bit

I ended up writing this:

def copy_inherit_instance(instence_inheriting, class_inherited):
    class tmp_class(class_inherited, instence_inheriting):
        pass
    old_class = instence_inheriting.__class__
    instence_inheriting.__class__ = tmp_class
    new_object = tmp_class.__copy__(instence_inheriting)
    instence_inheriting.__class__ = old_class
    return new_object

fun fact, if you pretend this is multithreading safe then it totally is, push to production

the fun part is that this is not even the ugliest part of my code lol

actualy this won't even do the init for class_inherited

so a bit more chonk is needed

[summer fossil]

Hii, Anyone here that start dsa recently

I need a dsa study partner

[tacit dove]

Does csv.writer.writerow(row) write from right to left by design?

I introduced a row that suddenly had six columns instead of five. It started from the sixth and omitted the first.

[haughty mountain]

I can't reproduce it, it just writes all the elements I give to it

[lapis rune]

I can be your partner

[tacit dove]

            w.writerow(['Email', 'First Name', 'Last Name', 'Employee ID',
                        'Door PIN'])

            for row in r:
                w.writerow(row)```

Pushing 7 columns to this, resulted in the first two columns being omitted entirely.

[lapis rune]

are there any tips for getting better at solving interview problems? Ive been trying to solve problems for a couple weeks now and I still cant manage to solve them without help and Im starting to lose confidence in my abilities.

[tacit dove]

Did you learn how to speak perfectly well in two weeks?

Or type?

[lapis rune]

no, but let me rephrase. a couple weeks for me is like 6-7

i still don't know if thats a lot but i have interviews coming up and dont feel ready at all

also I understand all the basic data structures and their trade offs in terms of time and space complexity, its more so i have a hard time knowing when to use which ones are needed

[summer fossil]

cool dm me

[tacit dove]

I feel like the questions are more to gauge if you can even do the job. If you assemble working code, I think they can work with that.

[haughty mountain]

In [5]: import csv
   ...: import sys
   ...: w = csv.writer(sys.stdout)
   ...: w.writerow(['Email', 'First Name', 'Last Name', 'Employee ID',
   ...:             'Door PIN'])
   ...:
   ...: r = [['1', '2', '3', '4', '5', '6', '7']]
   ...: for row in r:
   ...:   w.writerow(row)
   ...:
Email,First Name,Last Name,Employee ID,Door PIN
1,2,3,4,5,6,7

hopefully not an os difference, but who knows

!e

import csv
import sys
w = csv.writer(sys.stdout)
w.writerow(['Email', 'First Name', 'Last Name', 'Employee ID',
            'Door PIN'])

r = [['1', '2', '3', '4', '5', '6', '7']]
for row in r:
  w.writerow(row)

[halcyon plank]

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

001 | Email,First Name,Last Name,Employee ID,Door PIN
002 | 1,2,3,4,5,6,7

[haughty mountain]

@tacit dove does this snippet truncate for you?

if no, then there is some issue with your code

if yes, then maybe os difference, both I and snekbox are linux systems

[lapis rune]

So how important is it that I come up with an optimal solution that passes all the test cases?

[haughty mountain]

if you give an incorrect solution that's quite bad

correct but slow could be iterated and improved upon, incorrect is just bad

[tacit dove]

You know what? Pandas formats the CSV to a webpage. Dang it. I've been looking in the wrong place.

Pandas probably automatically truncates because it's making a table.

[pallid widget]

So I have a list of item objects in JSON, but all of them have lots of the same key names. What's some proper way to solve this, like create a structure definition at the start of the JSON and somehow make the data follow that scheme?

[fiery cosmos]

why does matrix parenthesization change the number of multiplications one might have to compute

[vocal gorge]

Sure; you could use e.g. pydantic to automatically parse the dicts into instances of a pydantic model.

[frail orchid]

hi could someone help me with this problem:
https://www.codewars.com/kata/57658bfa28ed87ecfa00058a/train/python

Empty positions are marked .. Walls are marked W. Start and exit positions are guaranteed to be empty in all test cases.```

i think my algorithm works but its very slow for some reason, it exceedes the time limit on most test cases:
```py
def path_finder(maze):
    maze=maze.split()
    p=(0,0)
    q=[p]
    final=(len(maze[0])-1,len(maze)-1)
    visited=set(q)
    level={(0,0):0}
    b=False
    while len(q)>0:
        if p==final:
            b=True
            break
        p=q.pop(0)
        for x,y in ((p[0]-1,p[1]), (p[0]+1,p[1]), (p[0],p[1]-1), (p[0],p[1]+1)):
            if (x,y) not in visited and 0<=x<=final[0] and 0<=y<=final[1]:
                if maze[y][x]=='.':
                    level[(x,y)]=level[p]+1
                    q.append((x,y))
    if b: return level[p]
    else: return False```

[fiery cosmos]

hi all,
i'm not understanding CLRS section 15.2: matrix chain multiplication. does anyone have any insight that might help me to see what they are talking about more clearly?

[vocal gorge]

pop(0) is very slow (O(n) complexity) for lists, as it requires moving the entire list an element to the left

replace that list with a collections.deque

[frail orchid]

so wait how would the syntax look idk how to write that

from collections import deque
def path_finder(maze):
    maze=maze.split()
    p=(0,0)
    q=deque([p])
    final=(len(maze[0])-1,len(maze)-1)
    visited=set(q)
    level={(0,0):0}
    b=False
    while len(q)>0:
        if p==final:
            b=True
            break
        p=q.popleft()
        for x,y in ((p[0]-1,p[1]), (p[0]+1,p[1]), (p[0],p[1]-1), (p[0],p[1]+1)):
            if (x,y) not in visited and 0<=x<=final[0] and 0<=y<=final[1]:
                if maze[y][x]=='.':
                    level[(x,y)]=level[p]+1
                    q.append((x,y))
    if b: return level[p]
    else: return False```

this is what i have now, its still too slow

[snow pollen]

Can anyone explain this question for me? If a given array does not contain any adjacent inversion, then all the elements in this array must be in place. Is it false because even if a particular array does not contain any neighboring inversions, this does not always indicate that all of the elements in the array are in the correct positions?

[vocal gorge]

Hmm, I think you're forgetting to update visited. At least, I don't see you ever touching it.

[vocal gorge]

"if a particular array does not contain any neighboring inversions, this does not always indicate that all of the elements in the array are in the correct positions" is literally what it means for the statement "If a given array does not contain any adjacent inversion, then all the elements in this array must be in place" to be false, so it's not really an explanation.

I think ||it's true||, though, because ||if a_1,a_2 are not an inversion, that means a_1<a_2. And if a_1 < a_2 and also a_2 < a_3 and so on, then a_1 < a_2 < a_3 < ... < a_n, so the array is in order.||

[snow pollen]

I am confused this question. So is it true or false?

can you explain why?

[vocal gorge]

Did you read the spoilered text?

[frail orchid]

Oh yea, but its still taking too long for some reason

[haughty mountain]

because you can end up with smaller multiplications

as an example, matrices and a vector

consider a mult with these sizes
(n x n) * (n x n) * (n x 1)

doing this left to right is a matrix-matrix mult, then a matrix-vector mult

doing it right to left is a matrix-vector mult (producing a vector), then another matrix vector mult

which is significantly cheaper

O(n³) vs O(n²)

[fiery cosmos]

hmm ok

chapter 15 did not seem to make a ton of sense to me, the rod cutting problem is straightforward, and its easy to see what they mean by subproblems and overlapping subproblems, but i did not understand most of every other concept, eg whether subproblems are distinct (independent), the recursive matrix chain multiply stuff

im guessing people would not memoize something like the individual matrix multiplications when computing large matrix products, because its probably computationally cheaper (faster) to simply repeat the multiplication rather than maintain some table with previously computed values.

but, first thought is that it would save a lot of computation?

depends on how cheap it is to multiply in the underlying machine language, i would think

like if matrix multiplication is expensive bc of all the multiplications O(n^3) for naive, would it not make sense to memoize? and keep a lookup table for the multiplication of integers a and b so it doesn't have to be repeated? by repeated i mean, elsewhere in the matrix, the same integers are multiplied over again

[vocal gorge]

I don't think it's ever worth it to memoize integer multiplication if the integers are finite-sized (so, if they aren't python's ints which can be infinite). You'd just spend more compute looking them up in a table than multiplying them would take.

[haughty mountain]

would memoization help? how many of the same multiplication do you even do?

I'm guessing very few

[fiery cosmos]

depending on the input matrices, you could be repeating the same thing many many times. i suppose it would only make sense in very specific scenarios

[fiery cosmos]

or not at all, and thats why people dont do it 😂

[vocal gorge]

only in the scenario of your matrices consisting of extremely large python ints, so that it's actually worthwile to memoize their multiplication

you could actually measure how big they need to be for that

[haughty mountain]

well, in that case the chance of you having any multiplications occurring more than once is like zero

[vocal gorge]

only if they're random; if they matrix has a lot of duplicates it'll be common

[haughty mountain]

or wait, is this about integer multiplication or matrix multiplication?

[vocal gorge]

I measured it

import random
def test_ints(bits):
    ints = [random.randrange(2**(bits-1), 2**bits) for i in range(100)]
    %timeit [a*b for a in ints for b in ints]
    dct = {(a,b):a*b for a in ints for b in ints}
    %timeit [dct[a,b] for a in ints for b in ints]

so I'm getting that ints need to be around 2^300 for their multiplication to be slower than a dict lookup

[agile sundial]

pretty small, tbh

[haughty mountain]

idk if this says anything useful

if you have a lot of duplicates you would probably bucket them by value and then multiply

and lots of duplicates is like the one case where this could possibly be useful

[vocal gorge]

that even in perfect conditions (measuring only lookup time, the values themselves are already magically precalculated and stored in a dict) you need giant ints for it to be worth memoizing them

[haughty mountain]

tl;dr: this is a terrible idea all around 😛

[vocal gorge]

🥴

actually if you have ints this large, you might want to look into big-int-mult algorithms

actually no, looking at the wiki page, they are used when you have thousands of digits, not a measly 300/log2(10)

[somber pivot]

hello how do I speak in "voice chat 1" ?

[vocal gorge]

!voice

[halcyon plank]

Voice verification

Can’t talk in voice chat? Check out #voice-verification to get access. The criteria for verifying are specified there.

[fiery cosmos]

jeebus

[fiery cosmos]

not my first

are there any other examples of dynamic programming problems that are well known or straightforward

besides the ones in CLRS chpt 15

is the knapsack problem a dynamic programming problem?

[haughty mountain]

yes, one of the most well known dp problems

or family of problems, i guess

[agile sundial]

the coin one is famous too

[fiery cosmos]

which coin one

googling tells me you're referring to the coin change problem

[agile sundial]

yeah

[fiery cosmos]

this course is so weird. they assign googlable problems and then tell us not to google anything, then we don't, and get D's on our projects

if they don't want us peeking in the secret library, why do they assign problems from the secret library? 👀

[haughty mountain]

coin change problem as in fewest coins to get a given sum? that's a knapsack variant

[fiery cosmos]

https://www.geeksforgeeks.org/understanding-the-coin-change-problem-with-dynamic-programming/

the only one thats made sense to me so far is the rod cutting one

| The following is an example of one of the many variations of the coin change problem. Given a list of coins i.e 1 cents, 5 cents and 10 cents, can you determine the total number of combinations of the coins in the given list to make up the number N?

[haughty mountain]

this one is very typical, a variant of the subset sum problem

but where you count ways, rather than just checking if it's possible

[fiery cosmos]

is there a concise summary anywhere of definitions and examples of NP-hard, NP-complete? also i asked this the other night but i'm still a noob with regards to my comprehension of greedy algorithms vs dynamic programming strategies. is there an overlap? is one a subset of the other?

[haughty mountain]

they are related

dynamic programming is the more general form

as for P NP stuff

you have this class of nice problems that you know how to solve in polynomial time

that is P

there is also the set of problems where we can verify a solution in polynomial time

that is NP

of course, P is a subset of NP because rather than just verify a solution, you could even just solve the problem in polynomial time

there is also a bunch of problems where we don't even know how to verify in polytime, those are outside NP

an interesting thing is that we can transform some problems into others

e.g. if I can translate problem A into problem B, then B is at least as hard as A

because solving B solves A

this kind of relationship is what NP hard is about

the class of NP hard problems are problems that are at least as hard as any problem in NP

and the NP complete ones are NP hard problems that are in NP (i.e. the ones verifiable in polytime)

here you can see P is a subset of NP

NP hard contains some problems in NP and some problems outside

note that stuff in NP but not in P are problems that we don't know polynomial algorithms for

you've probably heard of P=NP?

that's the question whether all problems in NP have polynomial algorithms

this is where NP-complete problems are interesting

if we can show that any NP-hard problem is solvable in polynomial time, then we have shown that P=NP

(though the general impressions seems to be that P!=NP, which is much harder to prove, if it's true)

[still eagle]

        if nums is None or len(nums) == 0:
            return 0

        nums.sort()

        low = 0
        high = len(nums) - 1

        while low + 1 < high:
            mid = low + (high - low) / 2

            if nums[mid] == k:
                high = mid

            elif nums[mid] < k:
                low = mid

            else:
                high = mid

        if nums[low] >= k:
            return low
        elif nums[high] >= k:
            return high
        return len(nums)

what is this algo doing?

[grand marten]

How do you find the big o for your algorithm

Im kinda confused lmao

[agile sundial]

read the code, compute the time complexity

[agile sundial]

it seems to be doing a binary search, but that would error because the float division. I'm kinda confused about what's after the binary search. also, it sorts the input to then binary search which doesn't make sense

[still eagle]

same don’t understand whats after the “binary search” part

[jolly mortar]

the if nums[mid] == k: block is confusing me

it doesnt break the loop

and assigns high = mid...?

[agile sundial]

I would guess they're looking for some number less than k with some property

[jolly mortar]

maybe its supposed to return the index at which k would have to be inserted to keep it sorted

[agile sundial]

but that'd be easy if it was equal

[jolly mortar]

tested with some values and so far this function seems to agree with bisect.bisect_left

[still eagle]

sorry don’t have experience with python what does bisect.bisect_left means?

[jolly mortar]

!d bisect.bisect_left

[halcyon plank]

bisect.bisect\_left

bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)```
Locate the insertion point for *x* in *a* to maintain sorted order. The parameters *lo* and *hi* may be used to specify a subset of the list which should be considered; by default the entire list is used. If *x* is already present in *a*, the insertion point will be before (to the left of) any existing entries. The return value is suitable for use as the first parameter to `list.insert()` assuming that *a* is already sorted.

The returned insertion point *i* partitions the array *a* into two halves so that `all(val < x for val in a[lo : i])` for the left side and `all(val >= x for val in a[i : hi])` for the right side.

[fiery cosmos]

Thank you so much, this is the exact type of thing I was envisioning I wanted to consider as a learning aid

[fiery cosmos]

are there any good graph problem visualization tools? i recall the program to print static maps, im wondering if there is a tool to see how your algorithm is working on a map with a visual aid

sort of like pythontutor but with a graph visualization function

could be a neat tool to create, if it doesn't exist

i'll put that in my maybes pile

wth are matroids

[fiery cosmos]

what is meant by this:

[haughty mountain]

err, I wouldn't worry about them

[haughty mountain]

do you know what a tail recursive function is?

it's a function whose call to itself happens at the end (tail)

def f(...):
  ...
  f(...)

this can be transformed into a while loop pretty easily

e.g.

def ilog(n):
  if n == 1:
    return 0
  half = n //2
  return 1 + ilog(half)

def ilog_iterative(n):
  res = 0
  while True:
    if n == 1:
      break
    half = n//2
    n = half
    res += 1

and yes, a bunch of compilers do this optimization to avoid recursion

(cpython notably doesn't)

[pliant junco]

That explains it

[opal oriole]

def sum_r(n):
  if n == 1: # Some base case to have it stop.
    return 1
  return 1 + sum_r(n - 1) # Recursion is at the end (tail).

def sum_i(n):
  s = 0  
  for i in range(n):
    s += 1
  return s
``` Note that the tail recursion can be expanded to look like `1 + 1 + 1 + 1 + ...`, which can be done with a loop (and especially functional programming languages will spit out loops for it for speed reasons).

And the fastest is just realizing that you don't even need a loop for it.

(Which compilers can also sometimes optimize out)

Example: https://godbolt.org/z/hjx5vjb84

Left is C source code, simple for loop summation. Middle is non-optimized assembly, you can see it does a loop from the jle which is "jump less than" (the loop condition). Right is with basic optimization turned on, you can see that it removed the loop and just moves the value 100 directly into to the register.

(If you write the recursive version and turn on some stronger optimizations (O2), it will end up as the same assembly)

[peak jungle]

Hey, so my problem is that I have a large number of files (e.g. 20.000) and I want to programm a search function which is able to rank the files based on the search term under consideration of having access to both, contence and name, date etc.
Do you maybe have an idea which system/algo would be fast and could be used... I am not asking for specific code but maybe an idea, known algorithm, website or YoutubeVideo as reference ? 🙂

[fiery cosmos]

is the search term an integer?

[peak jungle]

Nope, its a string :/

[fiery cosmos]

maybe a hash table is in order

with a hash table, you can use a string, convert to an int using a hash function, and then go and look in your table which holds the records for the string with that hashed value

how is the data distributed

are there lots of repeat records / values ?

[peak jungle]

Yes

[fiery cosmos]

oh sorry, i don't think a hashtable could offer any sort of ranking system. it'd just be a quick like record storage and retrieval paradigm

im not sure what you mean by ranking though

i'll let the experts weigh in

i am a student

[peak jungle]

Me too 🙂 Of course understandable

[fiery cosmos]

this is really interesting, what exactly is meant by assembly? i'd love to know the differences between assembly / compiler / machine language

[opal oriole]

It actually outputs machine code, but that is then reversed into assembly for your reading pleasure.

[fiery cosmos]

so it interprets your input in whatever language, determines the machine code that the language is dictating, returns that and converts it to assembly

[opal oriole]

You can imagine each assembly instruction being plugged into a giant lookup table to get out the actual machine code bits.

(Actual bits run by computer)

[opal oriole]

Sounds like you want tf-idf (https://en.wikipedia.org/wiki/Tf–idf), this is kind of a #data-science-and-ml question.

[fiery cosmos]

huffman encoding seems really cool

[opal oriole]

Can be combined with more things, however you want to rank stuff.

[opal oriole]

It is, and it's super important.

[fiery cosmos]

it seems.. simple and elegant

[peak jungle]

Thats exactly what I was looking for...Thank you very much

[fiery cosmos]

it'd be cool to build a program to create a frequency table, then you could run it on w.e input you want your huffman encoding to be based on, like a game of thrones novel or something

i can think of one approach that would use a dictionary

did anyone check out that 0/1 knapsack problem paper from 1988

so from what i understand in CLRS the 0/1 knapsack problem is not amenable to a greedy approach, but the fractional knapsack problem is

the fractional knapsack problem is just select the item with the greatest profit to weight ratio, taking more and more until its depleted so long as you still have capacity, then go to the next most profitable item, repeat, etc etc

the 0/1, greedy doesn't give optimal solution

the scheduling problem can be solved with the greedy approach

[amber inlet]

tell me guyss

best book for logic building

[south ivy]

what concepts/algorythms would i neeed to learn to turn this

into this

i managed to do it by myself, but looking for a more efficent way to do it cause i dont wanna reinvent the wheel

as im sure theres a algorythm to do it, idk what its called

[languid swift]

thanks for your advice

[stuck wind]

Hi, what is the time complexity of the this function for computing the power of a number. Since this function is called N/2 then multiplied with the same function calling N/2, wouldn't the TC be (log_2(N))^2 ? The tutorial I am following claims the TC is O(N) but I didn't get why```cpp
int power(int a,int n){

if (n == 0){
    return 1;
}

int halfPowerSquare = power(a,n/2) * power(a,n/2);

if (n%2 != 0){
    return a * halfPowerSquare;
}
return halfPowerSquare;

}```

[vocal gorge]

This should just be O(log n) oh, I see, it wastes work by calling power(a,n/2) twice. So the recurrent equation is T(n) = O(1) + 2T(n/2) which is solved by O(n). If not for the useless second call, it'd be T(n) = O(1) + T(n/2) which is solved by O(log n).

[crystal shell]

Hdu I wrote a code to reverse the number but it is showing error can anyone help me with that

nums = list(map(int, input().split()))

def reverse(nums):
i = 0
j = len(nums)-1

while j<i:
    nums[i],nums[j] = nums[j],nums[i]
    i = i+1
    j = j-1

reverse(nums)
print(nums)

@anyone?

[jolly mortar]

what's the error

also while j < i should be > otherwise it never even enters the loop

[crystal shell]

Yaa I did that but still It is not reversing the number

[jolly mortar]

"1234".split() doesnt give you [1, 2, 3, 4]

it splits on spaces

just list(map(int, input())) should work

[crystal shell]

Okaay

[halcyon agate]

from pydantic import BaseModel

class A(BaseModel):
    x: int
    y: int

class B(BaseModel):
    points: list[A]

c = B(points=[{'x': 0, 'y': 2}, {'x': 3, 'y': 5}])
print(c) # B(points=[A(x=0, y=2), A(x=3, y=5)])

c.points.append({'x': 8, 'y': 8})
print(c) # B(points=[A(x=0, y=2), A(x=3, y=5), {'x': 8, 'y': 8}])

Is there a config option for the appended dict to be parsed into an A object?

[cloud thorn]

Hey, for my homework assignment I had to make a python program that uses binary search to find a specific entry in a large csv file, are there any other algorithms that are faster/better for this?

[vocal gorge]

...is the csv file constant-width? because if not, I don't think you can easily binary-search it without loading it all into memory

[cloud thorn]

Yeah

[vocal gorge]

alright then. It doesn't really get better than binary search if it's available, no.

[cloud thorn]

Okay, thanks

[pliant heath]

if possible, consider using a set and look for desired index in that set

[sharp geyser]

Can someone help me with pyqt? there #help-lemon PLS!!!!

[vital scaffold]

Here is an excerpt from Michael Goodrich DSA book
" On our system, the size of a typical int object requires 14 bytes of memory (well beyond the 4 bytes needed for representing the actual 64-bit number)"
Why is it like this in python ?

[agile sundial]

14 bytes seems on the low end tbh. it has to care about more than just the value of the int. it needs a reference count, plus, it can be arbitrary size

[vital scaffold]

Ok

Can somebody recommend some python memory management resources ?

[agile sundial]

why?

[vital scaffold]

I come from C to python and there are differences in memory allocation so i need to know .

[agile sundial]

I mean, the difference is that you don't have to care. I think the book cpython internals talks about it

[stray fractal]

seems like that's a 32-bit system

[vital scaffold]

Import sys
a = 4
b = 0
c = 685674745
d = -1
print(sys.getsizeof(a))
print(sys.getsizeof(b))
print(sys.getsizeof(c))
print(sys.getsizeof(d))

*** Outputs***
28
24
28
28

Why is it like this ?

Is is correct to say that the instances of objects have size of 28 bytes for the address of the object ?

[woeful crescent]

Hey guys can you help me with this question, what kind of binary tree is it ?

I have to choose either full, perfect or complete

[haughty mountain]

well beyond the 4 bytes needed for representing the actual 64-bit number
err, the math here is just wrong

64 bits is 8 bytes

[haughty mountain]

the one I'm actually surprised about is 0 having a smaller size

[haughty mountain]

ngl I do not understand the struct for this type

struct _longobject {
    PyObject_VAR_HEAD
    digit ob_digit[1];
};

and a comment where PyObject_VAR_HEAD is defined

/* PyObject_VAR_HEAD defines the initial segment of all variable-size
 * container objects.  These end with a declaration of an array with 1
 * element, but enough space is malloc'ed so that the array actually
 * has room for ob_size elements.  Note that ob_size is an element count,
 * not necessarily a byte count.
 */
#define PyObject_VAR_HEAD      PyVarObject ob_base;

These end with a declaration of an array with 1 element, but enough space is malloc'ed so that the array actually has room for ob_size elements

Why is this done? It seems like a very weird thing to do

and this was in the initial revision by guido

from 32 years ago

Ok nice, this relies on undefined behavior

that's just great

[haughty mountain]

fun

/* Nothing is actually declared to be a PyObject, but every pointer to
 * a Python object can be cast to a PyObject*.  This is inheritance built
 * by hand.  Similarly every pointer to a variable-size Python object can,
 * in addition, be cast to PyVarObject*.
 */

assuming 8 byte pointers and 8 byte sizes

total 28

PyVarObject ob_base;        // 24 = 16 + 8
  PyObject ob_base;           // 16 = 8+8
    Py_ssize_t ob_refcnt;       // 8
    PyTypeObject *ob_type;      // 8
  Py_ssize_t ob_size;         // 8
digit ob_digit[1];          // 4

I do not understand how 0 becomes 24 bytes, this feels like a bug in the size calculation if anything

actually wait, maybe it makes sense

In [10]: for i in range(10):
    ...:   print(i, sys.getsizeof((2**30)**i))
0 28
1 32
2 36
3 40
4 44
5 48
6 52
7 56
8 60
9 64

I didn't test far enough out

so it includes the size of the digit array

so it makes sense

I just hate the UB of it

and this is why I get sad a lot when digging into python internals :/

[fiery cosmos]

hey what was the best way to time something again

oh perf_counter()

how do i format

  pass```

mylist is made of tuples like (1,2),(2,3) etc

im trying to implement a dynamic programming approach and i want to first check if the distance between two points is already known, and if so, to not calculate it over again

[full charm]

Create a Point Type with a calc_distance member function.

• A PointA object calls the method with PointB as argument and it returns the distance between the two. You could then check if your known distances array already contains it.
• Or do that with [key, value]: if the value of the key AB is different than 0, then this distance between A and B is already known.
  A sort of map with [2points, distance between them]

Note: I am actually a C++ Programmer who's (literally) just started with Python(subbed to the Anaconda Nucleus); so, my first thought was about Object-Oriented Programming haha

And as a C++ Developer I am finding everything weird in the Python world haha

I started learning Python because of some Stats&Probs stuff I am learning for some Robotics stuff; I picked Python basically because I am kinda more trying to understand the Stats&Probs concepts that the actual programming and Python has all these libraries as an import statement away haha; but apart from that, every programming I do is in C++ haha

[fiery cosmos]

how can i get every different combination of the ints in a list

without itertools, numpy, etc

so i like this:

def looper():
    array = [0,1,2,3]
    out = []
    for i in array:
        for j in array:
            out.append((i,j))

    return out

print(looper())

but i don't want each point with itself

[sharp grove]

hey, I wrote some algorithm, it is working but I don't know how. What we should do in this situation?

[opal oriole]

Inheritance in C.

Oh, you meant the other part with the size 1 array. It's so the memory is all contiguous, rather than have the array data be allocated elsewhere. C99 made this a thing by allowing [] (flexible array members) because it was very common (it's no longer part of the size with [] when you try sizeof).

Most C code out there relies on UB but considers it "machine defined" (some of the UB is actual bugs though). Why the C standard allows UB to continue to be a thing and even worse for compilers to abuse it is beyond me. "The C standard is _clearly_ bogus[****]" - Linus Torvalds.

The C standard throwing everything under the same term "UB" is a problem as the different kinds of UB out there are very different. Some really don't make sense, while others can be "machine defined", etc.

[fiery cosmos]

ok i have my edges as tuples in the form (0,1),(0,2),(0,3)... and i have avoided duplicates eg there is no (0,0), because i have no desire to compute the distance between a point and itself. now i would like to write a dynamic programming solution whereby im going to calculate the distance between a point and all other points on my way through, or, simply calculate all the edges once but stopping and being sure not to calculate both (0,5) and (5,0), as they'll be the same edge (distance)

[safe jacinth]

@agile sundial

I have a question

Say I have one operation that is cubic time, and only effects one element in a array being iterated

is it still O(n) speed

[haughty mountain]

they do at least separate undefined behavior and implementation defined behavior

[opal oriole]

Yeah, but UB is kind of their "I give up" area mixed with actual bug stuff.

[opal oriole]

>>> for i in range(5):
...     for j in range(i+1, 5):
...             print(i, j)
... 
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4
``` You want this?

[fiery cosmos]

i got that bit working, now im trying to unpack tuples in the form (0,2),(1,5) etc from a list. i want to get the first point equal to p1 and the second to p2. edges is a list of tuples of the aforementioned form. i am trying:

for edge in edges:
  p1,p2 = edge
...

it does not work as expected

[fiery cosmos]

my solution was like this:

    for i in points:
        for j in points:
            if i!=j:
                edges.append((i,j))

[haughty mountain]

what you would do depends on whether you want both (a, b) and (b, a)

[fiery cosmos]

yeah i actually don't, but i will get there

[haughty mountain]

if you want one but not the other I would end up doing an index loop like Squiggle mentioned

[opal oriole]

Red lines indicate the pairs made.

[haughty mountain]

that or use itertools.combinations, but you didn't want itertools

[fiery cosmos]

i actually stay away from the j+1 stuff because list index out of range errors later

correct

[opal oriole]

The way it works is that we are taking the current i and making a pair with every j, so j starts at the next element (to avoid with itself pairs (i = j)).

[haughty mountain]

what would cause list out of range?

[opal oriole]

Since i only increases, it does not repeat.

[haughty mountain]

this never produces i and j outside the range [0, n)

for i in range(n):
  for j in range(i+1, n):
    ...

[fiery cosmos]

also, the way it's working now, its actually appending the values themselves, not integers in a range

[fiery cosmos]

eg this

you are correct in that its going to append duplicates of the form (0,1),(1,0), but i'll worry about that later

what im concerned with now is learning to unpack these and assign p1 as a and p2 as b from (a,b) as edge in edges array

[haughty mountain]

that's not an issue though

you can just index your list

[opal oriole]

If you have a pair of integers like (0, 1) they can be used as indices (references into a list).

[haughty mountain]

e.g.

pairs = []
for i in range(len(A)):
  for j in range(i+1, len(A)):
    pairs.append((A[i], A[j]))

[fiery cosmos]

hmm thats true

[opal oriole]

What you typically want when you have some list is the indices, because then as long as you also have the list around, you have the values in the list.

By combination of the list and the indices.

So you can work entirely with indices and only fetch the values when needed.

[fiery cosmos]

for sure

but how do i unpack my edges list?

for edge in edges:
  p1,p2 = edge```

this isnt working as expected

[haughty mountain]

that should work

[fiery cosmos]

i get Exception has occurred: ValueError too many values to unpack (expected 2)

[haughty mountain]

though more consise

for p1, p2 in edges:
  # do stuff with p1 and p2

!e

edges = [(0,1),(2,0),(3,1),(1,4)]
for edge in edges:
  p1,p2 = edge
  print(p1, p2)

[halcyon plank]

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

001 | 0 1
002 | 2 0
003 | 3 1
004 | 1 4

[haughty mountain]

works

[opal oriole]

Error is probably elsewhere. Check which line it says the error happened.

[fiery cosmos]

no its erroring on that line and giving me the error i pasted above

but working for algmyr apparantly

apparently*

[opal oriole]

Exact same code?

[haughty mountain]

it's for sure not the same code

[fiery cosmos]

i mean i'm just trying to do for p1, p2 in edges: and its getting upset

[haughty mountain]

what is edges here?

print to check

you probably have stuff longer than 2 inside

[fiery cosmos]

[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)]

also, this might be all a fools errand or waste of time. i am trying to solve a problem in the book and specifically it must be solved with a dynamic programming approach and in O(n^2) time. the problem is to solve a euclidian bitonic tour, where one finds the shorts path between all points in a plane. it can be assumed that there is only one point with any given x coordinate. the idea for my first algorithm was this:

1. begin at point 0, which is the leftmost point in the plane. calculate distance to every rightward point from point 0, store in a list of distances, proceed rightward toward closest point.
2. from new point 1, calculate the distance to every rightward point from this point, first checking to see if the distance is already known. if it is known, proceed to the next calculation. repeat until the distances between this point and all rightward points are known. take the shortest distance
3. repeat in this manner until reaching the rightmost point, have if check, if at rightmost point, begin return traveral / path, again first checking to see if the distance between current point and closest leftmost point is already known, if not, calculate it, once all distances are known, take the path to the closest leftward point.

as we found out, the dynamic programming never kicks in, because you never get to a situation where you already have calculated the distance between the points in the above scheme, simply as a result of the way it runs / has been written

so i am working on a new approach, whereby i'll begin by first calculating the distances between every point and every other point

which, as written in a double for loop, would repeatedly solve the same distances over and over, and the idea is to implement the dynamic programming approach to solve that. however, as squiggle pointed out, you can write your for loop in such a way that this has already been handled, and there is no dynamic programming aspect of that

[haughty mountain]

like, there is no way the loop will complain on that list

either the error is on a different line, or that's not your list

[fiery cosmos]

ughh how do i get rid of the full path from my error messages

🤷‍♂️

one thing im not grasping is their hint, which was:
scan from left to right keeping track of the most optimum solution along the way

im failing to grasp how to implement a dynamic programming approach to this problem

this is an attempt at solving a bitonic tour for a euclidean traveling salesman problem

but we only just read chapter 15, so we have no background in graph traversals, BFS, etc

its supposed to be strictly a dynamic programming solution, unless they expect us to have read ahead..

[halcyon plank]

Missing required argument

code

[haughty mountain]

!e bot pls

points = [0, 1, 2, 3, 4, 5, 6]
edges = []

for i in range(len(points)):
  for j in range(i+1, len(points)):
    edges.append((points[i], points[j]))

for p1, p2 in edges:
  pass
print('this works')

[halcyon plank]

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

this works

[haughty mountain]

so I can guarantee the code you have in your editor there works

[fiery cosmos]

then why won't it work for me?

[haughty mountain]

it's not like you haven't saved or something?

[fiery cosmos]

no it auto saves

like every 0.001s

sry every 10ms

[haughty mountain]

can you try something like this?

for edge in edges:
  print(edge)
  p1, p2 = edge

[fiery cosmos]

sure

i mean yeah that prints the edges.. do you want me to try using p1 and p2 as i was trying?

output:
(0, 6) 0 6 (1, 2) 1 2 (1, 3) 1 3 (1, 4) 1 4 (1, 5) 1 5 (1, 6) 1 6 (2, 3) 2 3 (2, 4) 2 4 (2, 5) 2 5 (2, 6) 2 6 (3, 4) 3 4 (3, 5) 3 5 (3, 6) 3 6 (4, 5) 4 5 (4, 6) 4 6 (5, 6) 5 6

oh i see whats going on

im sorry

ok i've got all the distances between each point with no dups, they are in the form (distance, point_i, point_i+1)

now how i could use this to solve the bitonic euclidean salesman travelling problem with dynamic programming...

sry, the euclidian travelling salesman problem and generate the shortest possible bitonic tour

and no graph traversals have been learned yet, havent read that chapter

i think they do make a point in the book about any algo which solves BFS would work here or something similar

how many edges are expected in a graph with n points

if each point can connect to each other point

[haughty mountain]

O(n^2)

[fiery cosmos]

ok so this is calculating 21 unique edges for 7 points

i guess being able to calculate the distances is a good start, maybe i need to go and read chapt 15 again

im just not seeing how to implement a dynamic programming approach. i have office hrs tonight, i'll ask then

[opaque onyx]

Hey everyone my code should print the first letter in the sentence and every letter after a period capitalize and the proper word
x = "hello. my name is Joe. what is your name?"
print(string.capwords(x, '. '))

my output so far is :  
Hello. My name is joe. What is your name?

joe should be Joe

[fiery cosmos]

anyone familiar with infix and postfix expressions?

i neeeeed help

[elfin sundial]

im trying to write a static array class and idk if this is cheating or just blatantly stupid

class queue:
    def __init__(self, size: int):
        self.internal_array: list = []
        self.size: int = size

    def increase_size(self, incremental_value: int):
        self.size += incremental_value

        return self.size

    @property
    def __sizeof__(self) -> int:
        return self.size

    def add(self, appending_value: int) -> list:
        if isinstance(appending_value, int):
            new_length: int = self.increase_size(self.size)
            _ = self.internal_array.copy()
            _extended_array: list = append(_, appending_value)
            self.internal_array = _extended_array
        return self.internal_array


new_arr: queue = queue(1)
print(new_arr.__sizeof__)
new_arr.add(1)
new_arr.add(13)

print(new_arr.__sizeof__)
print(new_arr.internal_array)

i dont know how to write my own append

i thought about taking the array, coping it into a temp variable, and then defining another temp array with a value increased by increase_size() and then defining the internal_array as the increased array length and then adding the appending_value at the end

List benchmark took 0.002997875213623047 seconds
Queue benchmark took 1.8808283805847168 seconds
```bro...

[jolly mortar]

if thats the builtin list then you shouldnt be disappointed

the builtin list is implemented in c

[elfin sundial]

i had my doubts for that case

can staticness in native python even be considered faster?

or does it need to be compiled python

[jolly mortar]

thats close to what actually happens, but instead of increasing to just the right length it overallocates extra space so that you dont need to allocate and copy on every append

[elfin sundial]

oo

[jolly mortar]

the growth is such that the average cost of appending over a long run is O(1)