#algos-and-data-structs

1 messages · Page 157 of 1

fiery cosmos
#

'indices

opal oriole
#

Well, we are actually creating a function that acts like / gives the same values as returning values from that array.

#

We can do this because we know the array's pattern.

#

If it did not have a pattern we would have to return values manually from it.

#

(Because we can't construct f)

#

(You can think of a function as being like a lookup table to some extent)

fiery cosmos
#

i'm also learning that a function is a relation between two sets A and B

opal oriole
#

Out of the three options of having an array with the values 1, 2, 3, 4, 5, ..., f(i) = i + 1, and the recurrence method, which is the best?

fiery cosmos
#

and that there is a special relation that is a subset of the cartesian product of A x B

#

woof idk. i'm just trying to get a basic understanding of this stuff

opal oriole
#

Well for the array method, you need some amount of memory, up to whatever ith value you want.

#

For the recurrence method, if I want the ith value I first need to compute the (i-1)th value and the (i-2)the value and so on (until I reach f(0)).

#

But for the f(i) = i + 1 I neither need a ton of memory, nor need to do a bunch of steps.

#

It's as direct as it gets, no array, no recurrence.

fiery cosmos
#

so my way was legit?

opal oriole
#

Yes.

#

But the key here is realizing which is more nice and why.

fiery cosmos
#

for sure

opal oriole
#

And sometimes you won't know how to get the nice f(i) = i + 1, maybe you only have the array, or maybe you only can figure out the recurrence.

#

So you have T(n) = 2T(floor(n/2)) + n, which is a recurrence, and your end goal T(n) <= cnlgn is not a recurrence.

fiery cosmos
#

ok i am moving on to understanding the iterative method of solving a recurrence. are you familiar?

#

sry the "iteration" method

opal oriole
#

If for example I have f(i) = f(i-1) + 1 and somehow wanted not a recurrence, it's clear that I need to replace the f(i - 1) with something else that does not involve recurrence (preferably contains whatever end goal i'm going for).

#

We are not doing the exact same thing as with the T(...) situation, but the general idea of getting rid of a recurrence is the same.

#

So would it not be nice if we could replace T(floor(n/2)) AND have it be replaced with something that seems to contain part of what the end goal is?

#

T(floor(n/2)) <= cfloor(n/2)lg(floor(n/2)) is something we can replace it with, and it seems to be pretty similar-ish to the end goal (cnlgn, with the difference of the floors of n/2 instead of just n).

fiery cosmos
#

wow this next example is extremely mathy 😦

#

the iterative method for solving recurrences

#

"the idea is to expand the recurrence and express the resulting sum in terms dependent only on n and the initial conditions"

#

it looks like they first rewrite it with the n out front

opal oriole
#

Did you understand the previous problem though? With the T(floor(n/2)) stuff now?

#

The motivation behind the steps taken.

fiery cosmos
#

not really but i have like an enormous amount of examples to get through so that i can attempt the first hw problem and coding exercise

#

i need to get through all this reading / modules / content / supplements / etc

#

i'm going to ignore the iterative method for now bc its looks nonsensical

#

and move on to recursion tree method for solving recurrences

covert stirrup
#

what is the fastest way to merge sorted arrays

fiery cosmos
#

recursively

#

see implementations of mergesort

#

with O(nlogn) time complexity

covert stirrup
#

im trying to think of one actually wait i have a question

#

if i take one sorted array and compare each value of one array to the values of the other array

#

and if one value is greater than it you place it in front of it?

#

is this the best method?

#

or if it is less i place the number there

#

whats the problem with this

fiery cosmos
#

that sounds more like insertion sort algo which only considers one unsorted array and works iteratively on that

covert stirrup
#

ok so thats not efficient

#

btw whats wrong with that image

fiery cosmos
#

looks like it was deleted, but i usually come here for help, i'd ask one of the experts

covert stirrup
#

yeah

#

i figured it out

#

i mean i figured out one error

#

but im stuck on another

#

whats wrong with this

fiery cosmos
#

hey y'all in their example they argue that the above latex (case 1) is applied to solve this recurrence. i don't understand the epsilon value or where it goes

covert stirrup
# 
class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        t = x
        r = 0
        l = []
        while t > 0:
            r = t % 10
            t = t // 10

        l.append(r)
        strings = [str(l) for l in l]
        a_string = "".join(strings)
        an_integer = int(a_string)
        return an_integer
#

is this a good way of reversing an integer

fiery cosmos
covert stirrup
#

should i multiply by 10s and then add to get back the normal int

rough lynx
#

Not sure if anyone mentioned this but you can convert those lists into sets, which are one of the built-in types like list, tuple, and dictionary
The thing about a list is that you can't have duplicated elements in it, and you can use interesting functions like difference to do the whole thing you wrote code for
There's also intersection which does the opposite, which tells you what elements exist in both sets that you're comparing

#

Alternatively you could do something like list comprehension

#

!timeit

from typing import List
def findDifference(nums1: List[int], nums2: List[int]) -> List[int]:
    new_list: list[int] = list(set(nums1).difference(nums2))
    return new_list
print(findDifference([1, 3, 4], [1, 4, 4]))
halcyon plankBOT
#

@rough lynx :white_check_mark: Your timeit job has completed with return code 0.

50000 loops, best of 5: 3.84 usec per loop
rough lynx
#

!timeit

from typing import List
def findDifference(nums1: List[int], nums2: List[int]) -> List[int]:
    new_list: list[int] = [i for i in nums1 if i not in nums2]
    return new_list
print(findDifference([1, 3, 4], [1, 4, 4]))
halcyon plankBOT
#

@rough lynx :white_check_mark: Your timeit job has completed with return code 0.

100000 loops, best of 5: 3.76 usec per loop
rough lynx
#

vs your implementation

#

!timeit

from typing import List
def findDifference(nums1: List[int], nums2: List[int]) ->List[int]:
    new_list: list[int] = []
    for i, j in zip(nums1, nums2):
        if i not in nums2 or j not in nums1:
            new_list.append(i)
    return new_list
print(findDifference([1, 3, 4], [1, 4, 4]))
halcyon plankBOT
#

@rough lynx :white_check_mark: Your timeit job has completed with return code 0.

50000 loops, best of 5: 4.11 usec per loop
rough lynx
#

Doesn't matter much when it's 3.8s vs 4.1s but it does show that built-in stuff like data types or iterable comprehension works better

tacit halo
#

Tysm

rose thistle
#

I'm trying to make gif animations with pillow, but it's so slow when resizing, is there anyway to speed up this algorithm?

from PIL import Image
import os
from random import choice

def resize(im, scale=0.5):
    return im.resize((int(im.width*scale), int(im.height*scale)), resample=Image.NEAREST, reducing_gap=1.0)

def get_random_card():
    return "saved_cards/"+choice(os.listdir('saved_cards'))

def simulate_card(card_index, timestamp):
    x_position = 140+((image.width-(5*30))//4)*card_index
    y_position = (timestamp*5)+800
    return cached_images[card_index], (x_position, y_position)

cards = [get_random_card(), get_random_card(), get_random_card(), "images/xp_base.png"]
frames = []

cached_images = {
    "background": resize(Image.open(f"images/background.png").convert("RGBA")),
    "chest":      resize(Image.open(f"images/wooden-open.png")),
    0:            resize(Image.open(cards[0])),
    1:            resize(Image.open(cards[1])),
    2:            resize(Image.open(cards[2])),
    3:            resize(Image.open(cards[3])),
}
setup_background = cached_images["background"]
setup_background.paste(cached_images["chest"], ((setup_background.width-cached_images["chest"].width)//2, 100), cached_images["chest"])
cached_images["setup_background"] = setup_background

for timestamp in range(50):
    print(timestamp)
    image = cached_images["setup_background"]
    
    for card_index in range(4):
        card, position = simulate_card(card_index, timestamp)
        #resize(card, timestamp+1)
        image.paste(card, position, card)
    
    frames.append(image)

frames[0].save('testing.gif', save_all=True, append_images=frames[1:], optimize=False, loop=0, compress_level=1)
#

Currently the commented out line of "resize" makes it run from instantly to taking about 10-15 seconds, and I'd like this to run is roughly < 3 seconds

#

I tried using resample=Image.NEAREST, reducing the size of everything hoping the workload would be less, etc

plain thistle
#

I love algorithms and data structures

fiery cosmos
#

hello iam studying algorithm cuz i chose for my studies and I am still a beginner i want to know what this symbol means and how to convert it to py '∈'

si ch[long(ch)-1] ∈ ["0".."9"] alors
agile sundial
#

means "in", which translates in python to in

fiery cosmos
agile sundial
#

oh hey, that's french right

fiery cosmos
agile sundial
#

oh, i meant in the original message lol

fiery cosmos
#

oh hachuDank

fiery cosmos
#

I have an epsilon in my master theorem formula which I cannot figure out the meaning of

#

The master theorem being a strategy to solve recursions which characterize the running time of recursive algos

fiery cosmos
vocal gorge
#

here's what CLRS has to say about it

unknown.png
fiery cosmos
# fiery cosmos

In your problem f(n) = n, so it's true f(n) can be in O(n^(2-e)) for some positive e (epsilon). f(n) cannot be in Ω(n^(2+e)) because Ω is a lower bound and n^2 is already higher than n.

#

In the same vein, case 2 doesn't work because the f(n), aka n, is not Θ(n^2), i.e. n and n^2 grow differently (n is in O(n^2) but not Ω(n^2), Θ needs both)

#

so Case 1 is the only one that works for that problem

#

Ok

#

Yes reptile I am reading CLRS currently

haughty mountain
#

They use epsilon to basically have the notion of < = and >

#

f(x) = O(x^(a + ε)) could be (sloppily) read as f(x) > O(x^a)

fiery cosmos
haughty mountain
#

sloppy in that > isn't meaningful for bigO notation at all, but it illustrates the point

fiery cosmos
#

it seems as if they don't actually use the epsilon as a number. for example in my example above if they did one would do 9-1 = 8 for log_3(8)

#

once again i am asking myself why isn't it one of the other 3 cases (the cases linked in confused reptiles screenshot)

haughty mountain
#

it's just a consequence of O being like <=, Θ being like =, and Ω being like >=

Screenshot_20220622-174419.jpg
#

the cases they want to have there is <, = and >

#

(i.e. less than and not less than or equal, same for greater than)

fiery cosmos
#

so they want f(n) to be greater, equal, or less than one of those expressions?

#

right ok

haughty mountain
#

like, say I wanted to write a > b, but I couldn't write it as greater than

fiery cosmos
haughty mountain
#

I could say a >= b+ε for some small positive ε

fiery cosmos
#

so can we work this example? i don't understand it

#

i get where the a b and f(n) come from

haughty mountain
#

from the recurrence

fiery cosmos
#

i get the log_3(9)

#

why do they set it equal to theta

haughty mountain
#

they don't set it equal in anything, they talk about the asymptotics

fiery cosmos
#

ok so upon interpreting this i look at the recurrence

unknown.png
#

from here its easy to see what a equals, b equals, and f(n) equals

#

so then what

#

i have 3 cases of the master theorum i could choose from, given that it is in the form T(n) = aT(n/b)+f(n)

#

meaning the master theorum applies and i can use it

haughty mountain
#

tl;dr: n^log_b(a) is in Θ(n²)
f(x) is n which is asymptotically smaller than that, i.e. case 1

fiery cosmos
#

are you jumping straight to the expression T(n) following "then" in the case 1 statement

haughty mountain
haughty mountain
fiery cosmos
#

so something i just saw that i didn't before was case one T(n) = theta(someexpression)
case two T(n) = theta(someexpression lg n)
case 3 is T(n) = theta(f(n))

#

so im beginning to see how the larger of the two terms is going to come to dominate the runtime

#

so i get that, which is a step

haughty mountain
#

in this case f(n) is asymptotically smaller than n^log_b(a), which is case 1

haughty mountain
#

it's O, Theta, Omega

fiery cosmos
#

look at the end of each statement

#

describing the T(n)

haughty mountain
#

ah, yes those are the outcomes

fiery cosmos
#

we're analyzing f(n) using all of O, theta, and omega, you're correct. but the runtime T(n) always comes out to theta of something

haughty mountain
#

the first part before that are the conditions

fiery cosmos
#

correct

haughty mountain
#

yes, it's a tight asymptotic bound

fiery cosmos
#

so to my eyes when i go to case 1 which is:

unknown.png
#

i don't understand how it applies. i get that epsilon is just meant to mean greater than or less then

#

idk why it would be minus epsilon when we want f(n) to be upper bounded

haughty mountain
#

I read f(n) = O(n^(log_b(a) - ε) as "f(n) is asymptotically strictly smaller than n^(log_b(a))"

haughty mountain
fiery cosmos
#

yes the book says polynomially smaller

haughty mountain
#

without the epsilon you're basically saying f(n) <= thing

#

which is not what we want

#

we want f(n) < thing

#

that's what the epsilon does

fiery cosmos
#

i still read that as we would have to subtract epsilon from 9, which is clearly not the case

#

but setting that aside

haughty mountain
#

from 9? no

fiery cosmos
#

i'm not seeing how you automatically get to the conclusion and there is no explanation in the book

haughty mountain
#

log_b(a) - ε

#

so in your recurrence 2 - ε

fiery cosmos
haughty mountain
#

how does f(n) = n and n^(2 - ε) compare?

fiery cosmos
#

seem equal to me

haughty mountain
#

how?

#

ε is just some small number

fiery cosmos
#

book says for some constant epsilon greater than 0 (eg 1?)

haughty mountain
#

you can try to solve for ε like they do, but I don't think that's helpful

fiery cosmos
#

oh i'd never be able to do that. just trying to get the basics

#

hey will you be around in like 10 min? my cousins just got here and i have to help them for a bit

haughty mountain
#

do you see how I could write a < b in terms of <=? like

a <= b - (super small positive thing)
#

super small positive thing is what ε is used for here

fiery cosmos
#

doesn't seem to make sense to me but ok

#

whats the point of that why isnt it a - (super small positive thing) < b

haughty mountain
#

we want to force a to be slightly smaller

#

a <= b - ε accomplishes that

#

a + ε <= b would as well

fiery cosmos
#

if you want a to be slightly smaller, subtracting some small value from a (ensuring it becomes smaller relative to b) would make more sense.

#

i think i need forget the epsilon and just try to figure out how to use the formula

#

so how do i look at that example recursion and know which case to use?

haughty mountain
fiery cosmos
haughty mountain
fiery cosmos
#

sure

haughty mountain
#

which is exactly what we don't want

fiery cosmos
#

but in this case a is the coefficient, b is the term under n in the recurrence and f(n) is the term we want to compare the recurrence expression to

haughty mountain
#

I like a < b and a <= b - ε because it literally says "a is smaller than b even if I subtract a small amount from b"

#

it's easier to read out if you isolate a

fiery cosmos
#

so the top is the master theorum, and the bottom is my recurrence i want to solve. i will also write out the 3 cases of the master theorum

haughty mountain
#

same thing for the statement in case 1
"f(n) is upper bounded by something that is slightly smaller than n^log_b(a)"

#

i.e. it's smaller

fiery cosmos
#

i think when i plug everything in i get some question like "is it true that n is O(n^2)?" which is true, in which case T(n) = theta(n^2). is that it?

#

the "is it true" bit is coming from the if statement

#

if x then y type of thing

#

i think im getting it

#

i'll write out the next example and try to solve

#

is b still = 3 even though there is a 2n in the numerator?

#

oh no b = 3/2. how do you get that?

burnt trellis
#

random question but whats a reasonable IDE or text editor for js ?

fiery cosmos
#

not sure i use IDLE for python (the editor that comes with python)

burnt trellis
#

👍

haughty mountain
#

which is true

#

the other two cases aren't true:
f(n) is not Θ(n^2)
f(n) is not Ω(n^(2+ε))

fiery cosmos
#

how to evaluate a logarithm where the base is a fraction??

haughty mountain
fiery cosmos
#

i figured how to solve for that

haughty mountain
fiery cosmos
#

now i need to solve for log_3/2(something)

haughty mountain
#

these say the same thing
log_b(a) = x
b^x = a

#

the just log asks what I need to raise the base to to get x

#

it's well defined for all bases > 1

fiery cosmos
#

ok so i get 3/2^x = 1

haughty mountain
#

(3/2)^x = 1

fiery cosmos
#

x=0?

haughty mountain
#

yes

fiery cosmos
#

ok!

#

got the correct answer of theta(lgn), given by case 2.

#

i'm learning!!!

haughty mountain
#

🥳

autumn crystal
#

Hi can someone help me do this or do this for me, ive been stuck for an hour

unknown.png
fiery cosmos
tame crystal
#

Does anyone know what a LSI transformation is?

abstract bridge
fiery cosmos
#

anyone familiar with using recursion tree to solve runtime complexity of a recurrence?

haughty mountain
#

example?

fiery cosmos
#

the example they give involves alpha, which i haven't seen used before anywhere in the book. so i've moved on to completing the homework, where they give me a linear search algorithm and im tasked with describing the runtime complexity of it, and to give the tightest asymptotic representation (sigma, O, omega) and argue why that is the tightest bound

#

i was under the assumption that rereading everything would give me direction, but all of the examples are based on mathematical expressions, not pseudocode

#

there was one example in the book where they solved it with summations.. i wonder if thats what i need to do 🤔

#

i mean they analyzed pseudocode and converted it to mathematical expressions

haughty mountain
fiery cosmos
#

its hard for me to tell since they throw this alpha in there i haven't seen before. in the video he describes using the non recurrence of the expression as the root, and expanding the leaves using the recurrent part

haughty mountain
#

can you give the actual example with alpha and everything?

fiery cosmos
#

soo the example expression is T(n) = T(n/3) + T(2n/3) + cn

#

here is the instructor showing us how to solve a recurrence using a tree

haughty mountain
#

so yes, this is about drawing out the recursion tree and try to make sense of things

#

I think what they are analysing there is the more general thing T(n) = T(n α) + T(n (1-α)) + c n

#

in your example α=1/3

#

they draw out the tree and notice that every level sums to cn

unknown.png
#

I think the height argument is a bit iffy like they draw it there, the recursion will actually end at different depths because the split isn't symmetric

#

but the depth is still Θ(log n)

#

so work per level times number of levels gives the total cost

#

so Θ(cn log n) though I guess they just drop the constant, not sure why it's there to begin with

fiery cosmos
#

i need to figure out how to solve this hw assignment and im not sure if they want us to go through all the nonsense like shown in the book:

haughty mountain
#

what nonsense exactly?

fiery cosmos
#

so there are two columns following the insertionsort pseudocode algo in the book, a cost column and times column, and the runtime complexity is you give every line a cost (some constant) and a number of times the line executes (times column) then the runtime would be the summations of all the cost*times rows

#

i don't think? they want us to go through all that algebra to get there but it seems to be the only way they've shown us how to do it

haughty mountain
#

I mean, that's what you want to do if you want to get a more exact expression for stuff, for asymptotics you can take some shortcuts

#

you kinda need to know when you can and can't take those shortcuts

#

e.g. some people see a loop and just think O(n), which isn't generally true

#

very much depends on the details

fiery cosmos
#

i've emailed the prof. i've made the case i can simply argue that since each line takes constant runtime, the T(n) = theta(n) because c1*f(n) <= T(n) <= c2*f(n)

haughty mountain
#

what's the code in question?

fiery cosmos
haughty mountain
#

"each line takes constant runtime" feels a bit weird here

#

considering the thing in the loop can run up to n times

fiery cosmos
#

ehh linear runtime?

#

each line takes at longest linear runtime?

#

at longest would be O though

haughty mountain
#

I mean sure, every line including the i = i + 1 takes O(1) time, but the i = i + 1 is run O(n) times

#

I guess that's what they are trying to drill into you, that you need to take both the amount of work and the number of times executed into account

#

but yes, the loop will run at most n times and doing constant work each time

#

the rest of the code is just doing O(1) work overall

fiery cosmos
#

O(1) describes constant runtime and O(n) describes linear runtime?

haughty mountain
#

yes

#

f(x) = O(1) if there exist a constant C such that f(x) <= C*1

#

so yes, it's bounded by some constant

#

similar for the linear case

haughty mountain
fiery cosmos
#

no

haughty mountain
#

you can also look at best case and average case

fiery cosmos
#

"describe time complexity, choose tightest asymptotic representation, argue why that is the tightest bound." (could choose from O, theta, omega)

#

my argument is that its theta because c1f(x)<=T(n)<=c2f(x)

haughty mountain
#

you still need to specify what you are bounding, is it the worst case runtime?

fiery cosmos
#

i'm bounding the runtime T(n) which is characterized by the summation of all the lines which are either linear or constant and none of which are n^2

#

that is, there are no quadratic runtime lines

haughty mountain
#

the runtime differs depending on your input

#

best case is O(1)

#

worst case is O(n)

fiery cosmos
#

like if the array is a single element, the searched for term x?

haughty mountain
#

that's why I'm asking

#

no, if your element is somewhere close to the front of the array

#

say it's the first element

#

you run the loop 1 iteration in total

#

actually, the loop body doesn't even run once if the element you are looking for is the first one

fiery cosmos
#

right

haughty mountain
#

so it matters a lot what you are trying to find

#

most of the time people care about the worst case

#

but the average case can also be interesting

#

best case tends to be kinda boring to look at, but you can do that too

fiery cosmos
#

the weird thing is that the book uses theta as the worst case running time, not O

#

and this is CLRS we're talking about

haughty mountain
#

considering that they are very careful with what they use everywhere else

fiery cosmos
#

i promise you they do, let me get a photo

haughty mountain
#

Theta just means a tight bound

#

it can be a tight bound of the worst case running time, sure

#

you can do all three kinds of bounds for whatever you are analyzing

fiery cosmos
#

"we write that insertion sort has a worst case running time of theta(n^2)"

haughty mountain
#

it is Theta(n^2) though

fiery cosmos
#

and if i am misunderstanding can you clear my confusion with regards to worst case runtime =/= O

haughty mountain
#

it's a tight bound on the running time

fiery cosmos
#

when i think worst case, i think big O

haughty mountain
#

it's both O(n^2) and Omega(n^2)

#

hence Theta(n^2)

fiery cosmos
#

hmm

#

did you mean omega? as a lower bound? what is sigma?

haughty mountain
#

omega, yes

fiery cosmos
#

ok haha you gave me a panic

haughty mountain
#

O is an upper bound on something
Ω is a lower bound on something
Θ is a tight bound on something, so both O and Ω

#

that something could be whatever

#

best case, average case, worst case, whatever

fiery cosmos
#

can you help me to differentiate between O and worst case in my mind? i have them conflated in a way that is incorrect

haughty mountain
#

do note that a lot of people are a bit sloppy and just use O when they probably should use Θ

haughty mountain
#

whatever you analyze the asymptotics of you can look at any one of lower bound, upper bound, and strict bound

fiery cosmos
#

so i could for example, find a lower bound omega on the worst case runtime

#

or an upper bound O of the best case

haughty mountain
#

you could

#

you can say something like "the worst case is at least this bad" which would be using Ω

fiery cosmos
#

for sure. makes sense

haughty mountain
#

big O is often the most interesting one in practice

#

for running times you want to bound stuff from above to get a feeling for how bad the thing you're looking at can get

fiery cosmos
#

right, because we know in the worst case scenario the algo will take at most O(some_time)

#

woof, next one they give me a binary search algo where the input is a sorted list of elements, and a search term x which may or may not be present. the assignment is "describe the time complexity of the following binary search algorithm in terms of number of comparisons used, choose tightest asympt representation and argue why thats the tightest"

#

i'll have to read over this for awhile, i'll be back later. thank you as always @haughty mountain

#

actually i'm going to try to plow through it because the thing after looks even more complicated

#

haven't even gotten to NP-completeness yet 😵‍💫

haughty mountain
#

I think most of these things aren't that hard when you get used to things, but I guess that's true for everything

fiery cosmos
#

i agree

#

in my case i just have alot of relearning algebra and learning discrete math to do along the way

final ledge
#

How would you compare 2 different sets where a single element from set1 can be similar to multiple elements from set2 and vice versa (looking for something like the Jaccard index)

For example, lets define 2 numbers being simlar as the difference of the absolute value of the 2 numbers being 1, and your sets being (1, 3, 4) and (1, 2). In this instance, the 1 from the first set would be similar to the 1 and 2 form the second, and the 2 from the second would be similar to the 1 and 3 from the first.

I'm looking for a way to quantify how "similar" these 2 sets are

haughty mountain
fiery cosmos
#

yes, and i'm determined to relearn it

#

math is difficult when you have a sporadic history of learning it, once you stop using it it disappears from the mind

#

so the given problem the number of comparisons used is going to be equal to n where n is the distance from the beginning of the array to the search term x

#

at maximum it would have to compare x to every element in the array A, and return 0 if x is not in A

#

so they say "determine the time complexity of the binary search algorithm in terms of number of comparisons"

#

🤔

haughty mountain
#

why would you need to search the whole array?

fiery cosmos
#

to compare x to every element in A

#

the input isn't specified as a binary tree, just a sorted array

#

but theyre calling it binary search

#

"assume the input A is a sorted list of elements"

#

a binary tree is a graph no?

#

oooooo

#

its splitting the input array with each step🤦‍♂️

#

must be characterized by recursive running time then i would suppose

#

need to see if there is any way the master theorum may apply

haughty mountain
#

what would the recurrence for this thing be?

#

what is T(n)?

fiery cosmos
#

all i've got is T(n/2), i don't know what the coefficient a nor the + f(n) terms would be. well i guess a would be = 1, b is 2, f(n) = 0? it's really difficult to convert pseudocode to mathematical formulas

#

the T(n) could be T(n/2)+1 if im missing a 1 somewhere

haughty mountain
#

f(n) is more like 1 yes, you do some constant amount of work still

#

but yes, you split the array in half and only consider one half, hence the 1*T(n/2)

#

so T(n) = T(n/2) + 1 is correct

fiery cosmos
#

what pdf editor do you use? all i want to be able to do is write on a pdf and save

vocal gorge
#

if that's all you want, most pdf viewers allow that

#

okular is a great opensource one

fiery cosmos
#

no mine is behind paywall

#

ok thanks

#

you referring to Okular?

vocal gorge
#

yup

fiery cosmos
#

ty

#

hmm.. next step is to make one small change in the pseudocode to improve the runtime and give the revised asymptotic tightest bounds

#

i feel like they want us to add a recursive call to itself

#

perhaps that would change the runtime from nlogn to just logn

#

or something similar

haughty mountain
#

what's the code?

fiery cosmos
#

One moment

#

i feel like the one small change they want us to make it making it truly recursive

haughty mountain
#

I don't like their indexing standard (inclusive, inclusive), but yes, that's a typical iterative binary search

fiery cosmos
#

i take issue with the same

#

should be i = 0

#

they're typically working in java if that changes things

haughty mountain
#

I don't mind the starting at 1 that much

#

but they need this +1 that you don't need if you index differently

#

switching to 0 indexing you can do

l = 0
r = len(A)
while r - l > 1:
  m = (r + l)//2
  if x >= A[m]:
    l = m
  else:
    r = m
```which is just cleaner and easier to reason about in my head
fiery cosmos
# 
l = 0
r = len(A)
while r - l > 1:
  m = (r + l)//2
if x >= A[m]:
  l = m
else:
  r = m
#

you know you can do python specific formatting

#

what about the return statements

haughty mountain
#

you still need to do the same kind of checks afterwards, that code doesn't change much though

fiery cosmos
#

ok you just rewrote it correct? or did you rewrite it while making the small change

haughty mountain
#

small change

fiery cosmos
#

alright let me analyze both

haughty mountain
#

if you would just translate it to zero indexing it would start with 0 and len(A) - 1

fiery cosmos
#

looks like you removed the if else from the while loop?

haughty mountain
#

I messed up the indentation, fixed

#

so, I'm putting my l and r so that the check in my loop would be true for l and false for r

fiery cosmos
#

omg the cursor blinking in idle is so distracting

haughty mountain
#

it's not strictly true in this case since 0 can make the thing true

fiery cosmos
#

there is a fix but you have to insert some code in the of the python files themselves

haughty mountain
#

but the if check afterwards makes it work

fiery cosmos
#

🤔

haughty mountain
#

I don't like having to think about +1 in random places when it comes to the check, that's why I prefer that standard

fiery cosmos
#

does that change the values of a, b, or f(n) in the master theroem? idk if for example it makes the +1 go away in my previous expression?

#

i think you need the +1 to capture the constant runtime of the other lines

#

furthermore what sort of code would make f(n) equal to 2,3,4, etc

haughty mountain
fiery cosmos
#

ok. i'm going to try to identify a change that would change the runtime complexity

haughty mountain
#

so whatever constant is the same in that regard

fiery cosmos
#

ok

#

what would make f(n) = to something other than 1? why is it one in the previous case

haughty mountain
#

if you want something super explicit you can start counting every operation like in the example you thought was just overly detailed

#

if you only care about asymptotics in the end only the asymptotics of f(n) matters, so everything O(1) is the same in that case

fiery cosmos
#

i dont i just dont understand why in my example it was T(n) = T(n/2) + 1 and not T(n) = T(n/2) + (some other term)

fiery cosmos
#

ok i get it now

#

any integer number would evaluate to constant runtime, unless its n, which would become linear

haughty mountain
#

in another example you had a f(n) = c*n and I was saying I was confused why it was even there

#

because the constant factor doesn't matter to the asymptotics

fiery cosmos
#

hm im not sure either. maybe to help you set up the recurrence tree so that one doesn't start with simply n at the root

#

which should be c*n

#

i don't know that it matters or not

haughty mountain
#

it doesn't matter for the asymptotics

fiery cosmos
#

using the master theorem to solve:

unknown.png
#

i get case 3, T(n) = theta(n^2)

#

working on:

unknown.png
crimson steeple
#

how do i study dsa

#

in python

#

with c

#

done

keen hearth
#

@crimson steeple have a look at some of the resources pinned in this channel.

tidal hawk
#

should i learn dsa in python course on udemy?
I'm now deciding to buy it so please give some advices my friends

covert swallow
vague torrent
#

What approach would be good To calculate coordinates for an image given the corners and the dimension of an image in python?

covert swallow
#

What do you think of this data structure?

@dataclass
class Party:
    name: str
    language: Language
    phonenos: List[Phone]
    emails: List[Email]
    addresses: List[Address]

@dataclass
class Individual(Party):
    citizenship: Citizenship
    nric: NRIC
    passport: Passport


@dataclass
class Company(Party):
    registration_number: str
    registration_verified: str

Where as every other are its own dataclass of extra info.

Is this approach good or bad?

#

The idea is to call which party of either Individual or Company to be registered as a Customer or a Guarantor in a contract.

lament totem
#

Seems like you might as well just use pandas or sql to store the data?

covert swallow
vague torrent
#

What approach would be good To calculate coordinates for an image given the corners and the dimension of an image in python?

lament totem
covert swallow
#

Plus, I can unittest my classes

#

Not sure about testing SQL or Pandas yet

tender atlas
#

`def bfs(cx, cy, dx, dy, grid, m, n, visited):
q = queue()
visited[cx][cy] = 1
q.append((cx, cy))
while len(q) > 0:
cell = q.popleft()
px = cell[0]
py = cell[1]
grid[px][py] = 2
for x, y in dxy:
rx = px + x
ry = py + y
if is_valid(rx, ry, grid, m, n, visited):
q.append((rx, ry))
visited[rx][ry] = 1

print(grid)`

How to get an optimal path from a binary grid after running BFS? In BFS, we are moving to each possible nodes which increases total number of nodes passing cost.

haughty mountain
tender atlas
fiery cosmos
#

hey y'all i need to use the master theorum to find the asymptotic bounds of

#

there is a hint, it says use a substitution to handle the +1 term

fiery cosmos
#

i.. uh.. what?

shut breach
# fiery cosmos

checking the steps that someone else gives you is easy, but coming up with the steps in the first place is sometimes hard

autumn crystal
#

can someone pls do this for me

unknown.png
fiery cosmos
#

what is meant by an instance of the decision problem PATH

#

just like how to traverse a graph

tacit halo
#

!timeit

    length_of_list: int = len(lists) # Getting the length of the 'list'.
    for i in range(length_of_list - 1):
        swap_elements = False
        for j in range(length_of_list - 1 - i):
            if lists[j] > lists[j+1]:
                swap_elements = True
                lists[j], lists[j+1] = lists[j+1], lists[j]
        if not swap_elements:
            break
    return lists
halcyon plankBOT
#

@tacit halo :x: Your timeit job has completed with return code 1.

001 | Traceback (most recent call last):
002 |   File "/usr/local/lib/python3.10/runpy.py", line 196, in _run_module_as_main
003 |     return _run_code(code, main_globals, None,
004 |   File "/usr/local/lib/python3.10/runpy.py", line 86, in _run_code
005 |     exec(code, run_globals)
006 |   File "/usr/local/lib/python3.10/timeit.py", line 376, in <module>
007 |     sys.exit(main())
008 |   File "/usr/local/lib/python3.10/timeit.py", line 315, in main
009 |     t = Timer(stmt, setup, timer)
010 |   File "/usr/local/lib/python3.10/timeit.py", line 123, in __init__
011 |     compile(stmtprefix + stmt, dummy_src_name, "exec")
... (truncated - too many lines)

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

tacit halo
#

!timeit

import typing
def bubble_sort(lists: typing.Any) -> list[int] | int:
    length_of_list: int = len(lists) # Getting the length of the 'list'.
    for i in range(length_of_list - 1):
        swap_elements = False
        for j in range(length_of_list - 1 - i):
            if lists[j] > lists[j+1]:
                swap_elements = True
                lists[j], lists[j+1] = lists[j+1], lists[j]
        if not swap_elements:
            break
    return lists
halcyon plankBOT
#

@tacit halo :white_check_mark: Your timeit job has completed with return code 0.

200000 loops, best of 5: 878 nsec per loop
tacit halo
#

the what

#

nanoseconds?!!
damn

jolly mortar
#

you didnt call the function

tacit halo
#

That's why

fiery cosmos
#

bruh

tacit halo
#

!timeit

import typing
def bubble_sort(lists: typing.Any) -> list[int] | int:
    length_of_list: int = len(lists) # Getting the length of the 'list'.
    for i in range(length_of_list - 1):
        swap_elements = False
        for j in range(length_of_list - 1 - i):
            if lists[j] > lists[j+1]:
                swap_elements = True
                lists[j], lists[j+1] = lists[j+1], lists[j]
        if not swap_elements:
            break
    return lists 
 
bubble_sort([1, 2, 4, 3])
halcyon plankBOT
#

@tacit halo :x: Your timeit job has completed with return code 1.

001 | Traceback (most recent call last):
002 |   File "/usr/local/lib/python3.10/runpy.py", line 196, in _run_module_as_main
003 |     return _run_code(code, main_globals, None,
004 |   File "/usr/local/lib/python3.10/runpy.py", line 86, in _run_code
005 |     exec(code, run_globals)
006 |   File "/usr/local/lib/python3.10/timeit.py", line 376, in <module>
007 |     sys.exit(main())
008 |   File "/usr/local/lib/python3.10/timeit.py", line 315, in main
009 |     t = Timer(stmt, setup, timer)
010 |   File "/usr/local/lib/python3.10/timeit.py", line 123, in __init__
011 |     compile(stmtprefix + stmt, dummy_src_name, "exec")
... (truncated - too many lines)

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

tacit halo
#

Ahh, on mobile rn

tacit halo
#

Not lists

#

1,2,3

#

Like those

fiery cosmos
#

why is it showing N=100 computations for 5!

agile sundial
fiery cosmos
#

oh its doing the factorial function on n=5 different inputs

agile sundial
#

huh?

fiery cosmos
#

nvm, i was evaluating it like n=5 can be computed in 4 steps. but its saying that given 5 inputs it'd take at least N=100 computations to get an answer

agile sundial
#

it's just graphing a function

#

your input is n, output is N

#

input is 5, output is 120

fiery cosmos
#

no it says showing the number of operations N as the result of input size n for each function

fiery cosmos
agile sundial
#

yes

fiery cosmos
#

it does not take 120 operations to compute 5!

agile sundial
#

that's not what it's saying

fiery cosmos
#

according to the label, that is what its saying

#

let me give you the whole screenshot in its entirety

agile sundial
#

no, that's really not what it's saying

fiery cosmos
#

showing the number of operations N as the result of input size n for each function

#

its saying that given 5 different numbers to compute the factorial of, you'd need at least that many basic steps

agile sundial
#

sure

hollow nebula
haughty mountain
haughty mountain
#

e.g. if you run bubble sort on a list of size n you use roughly N = n^2 operations

fiery cosmos
#

they never defined PATH, we just jumped right to the end of the book and started learning about NP-complete problems..

#

and circuit satisfiability

fiery cosmos
#

so circuit satisfiability is simply that a circuit comprised of boolean combinational elements can have a truth assignment that enables the output to be 1

#

seems straightforward

haughty mountain
#

page 1051 in the version I found

fiery cosmos
#

oh thank you, they didn't have us read this section beforehand 🤦‍♂️

haughty mountain
#

it's in the first few pages of the NP-Completeness chapter

fiery cosmos
#

reading now

fiery cosmos
#

its interesting

fiery cosmos
#

is a vertex of a graph the same as a node

#

googled: it is

haughty mountain
#

i.e. an undirected graph has vertices and edges, and a directed graph has nodes and arcs

#

though idk how stringent people are about it

fiery cosmos
#

synonymous with node

#

it feels really silly to go from my struggling to understand the basics to NP-completeness especially without going over graph theory

#

this is the way they structured the course 🤷‍♂️

haughty mountain
#

though I don't think it matters too much what you call them vertices or nodes, the name for the things connecting them matters more

#

in the undirected case you call them edges

#

in the directed case you call them arcs (or sometimes "directed edges")

#

I suspect opinions of naming will differ if you talk to a computer scientist or a mathematician as well

agile sundial
#

as long as you define them consistently it doesn't really matter ¯_(ツ)_/¯

fiery cosmos
#

what's this about?

haughty mountain
fiery cosmos
#

can someone help me set up an IDE for python? i can never get mine working properly. i'm using IDLE for now which i want to move away from

agile sundial
haughty mountain
#

oh god, regular languages

haughty mountain
agile sundial
haughty mountain
#

_In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges often called arcs. _

agile sundial
#

huh. ¯_(ツ)_/¯

fiery cosmos
#

ok thanks

haughty mountain
#

tbh, I think that is a very niche topic

#

your time might be better spent looking at other parts of the book

fiery cosmos
#

It is but it's so cool. It's all the history of how "algorithms" were formalized and the limitations of various computational machines ducky_wizard

#

what's wrong with this line:

with open(C:\Users\Steve\Desktop\desktop\school\fall22algorithms\"points", 'r') as inf:```
#

I like it a lot at least hachuCozy

#

that filepath needs to be quoted

haughty mountain
#

" placement?

fiery cosmos
# 
with open("C:\Users\Steve\Desktop\desktop\school\fall22algorithms\points") as inf:```
fiery cosmos
#

points is a text file

#

ah, you need to make it a raw string open(r"C:\...

#

so the backslashes aren't seen as escape symbols

haughty mountain
#

that or escape all the \ as \\

fiery cosmos
#

(or use / and it almost always works too even on windows)

#

hmm its not seeming to be able to open the file

fiery cosmos
# 
with open("C:/Users/Steve/Desktop/desktop/school/fall22algorithms/points.txt") as inf:```
#

not working 🤷‍♂️

#

is there any error?

#

and are you certain the file exists there?

#

nope just not returning anything. yes i am sure the file named points.txt is there, i copied the path straight from the windows explorer

#

What is the code below that line?

#

this was working on my laptop

# 
        for line in inf:
            pointsarray.append(tuple(line.split()))

    itemsleft = len(pointsarray)-1
   
    for i in range(0,itemsleft):
       
        x_diff = int(pointsarray[i][0]) - int(pointsarray[i+1][0])
        y_diff = int(pointsarray[i][1]) - int(pointsarray[i+1][1])

        x_diff_sq = x_diff*x_diff
        y_diff_sq = y_diff*y_diff

        euc = math.sqrt(x_diff_sq + y_diff_sq)

        print(x_diff,y_diff)
        print(euc)
haughty mountain
#

if there is no error thrown then it opened successfully

fiery cosmos
#

ok maybe im just missing a return statement

agile sundial
#

should your points be strings?

fiery cosmos
#

ye, and looks like it should be read properly

#

put some more prints in there ducky_sus

#

this works:

import math

def closestpairs(points):
    pointsarray = []

    with open(points) as inf:
        for line in inf:
            pointsarray.append(tuple(line.split()))

    itemsleft = len(pointsarray)-1
   
    for i in range(0,itemsleft):
       
        x_diff = int(pointsarray[i][0]) - int(pointsarray[i+1][0])
        y_diff = int(pointsarray[i][1]) - int(pointsarray[i+1][1])

        x_diff_sq = x_diff*x_diff
        y_diff_sq = y_diff*y_diff

        euc = math.sqrt(x_diff_sq + y_diff_sq)

        print(x_diff,y_diff)
        print(euc)

closestpairs("C:/Users/Steve/Desktop/desktop/school/fall22algorithms/points.txt")
#

forgot the way it was running on my laptop

#

how many of y'all code in linux / windows / on macOS

#

learning on windows is the worst

#

the default python installation directly is like within a hidden folder

#

always difficult to know the pythonic scope or where the home directory is or is pointing at

#

You might try WSL2 if you're on windows but want a Linux experience (though imo Python+Windows is nice since it has the py launcher)

#

🤔

#

watching Mike Sipser now

clear rose
#

hey all

#

can somebody help me with figuring out space complexity of the following code

# 
# given input construct target string

def can_construct(target_string, inputs, cache={}):
    if target_string in cache.keys():
        return cache[target_string]
    if target_string == "":
        return True

    for sub_string in inputs:
        if target_string.startswith(sub_string):
            result = can_construct(target_string[len(sub_string):], inputs, cache)
            if result == True:
                cache[target_string] = result
                return result
    cache[target_string] = False
    return False

if __name__=="__main__":
    cache = {}
    print(can_construct("abcdef", ["abc", "def", "ab"], cache)) # T
#

so the max length of target_string is m, and in the worst case scenario we pass target_string[len(sub_string):]m number of times

#

and since string does get smaller each time we have, I have a feeling that time complexity would be m^log(m)

#

not sure if you can do m^log(m)

fiery cosmos
#

Is (-a) % b - a % b the same as (-2*a) % b discre3Hmm

jolly mortar
#

(-a) % b - a % b = b - a%b - a%b = b - 2(a%b)

#

pithink i dont think the two are equivalent

fiery cosmos
#

How did you get (-a) % b = b - a%b? hachuDank

#

Is that a normal mod property lemon_thinking I'm so bad at doing math with mod lemon_sweat

jolly mortar
#

||i tested that it holds for (a, b) = (4, 5) and (-4, 5) so i assumed it holds for everything 🎉 ||

#

ok so it doesnt hold when a%b == 0, but it holds otherwise

a%b = a - b*[a/b]      (where [x] = floor(x))
(-a)%b = -a - b*[-a/b]
       = -a - b*(-[a/b]-1)    ([-x] = -[x]-1 if x not in Z)
       = -a + b + b*[a/b]
       = -a + b + a - a%b
       = b - a%b
haughty mountain
clear rose
haughty mountain
clear rose
#

You mean n-1?

#

So then if you expand you get n^2/2 - n/2 and so you drop n/2 and /2 hence n^2?

jolly mortar
#

n+1 is correct

clear rose
#

Why is it n+1 and not -?

jolly mortar
#

handwavy proof: n + (n-1) + ... + 2 + 1 = (n+1) + (n-1 + 2) + (n-2 + 3) ... = (n+1) + (n+1) + (n+1) + ... n/2 pairs = (n+1) * n/2

clear rose
#

Right right

#

So then if you expand you get n^2/2 + n/2 and so you drop n/2 and /2 hence n^2?

jolly mortar
#

yeah

clear rose
#

So when do you have O(logn)?

#

I thought it is handy when next result is smaller

jolly mortar
#

not just smaller, it has to be a fraction (say half) of the current one

clear rose
#

So much smaller. I see

#

Thanks you

haughty mountain
zenith wasp
#

I'm working on an application with nodes, and each node can have other nodes as inputs and outputs.
What I need is to obtain an ordering of these nodes, starting from the ones with no inputs to the ones with no outputs.
I only have a list of all nodes, and I can't rely on the number of inputs or outputs a node has.
How would I obtain a list of nodes in the order they should act?
The graph is guaranteed to be acyclic.

shut breach
#

what is the order they should act?

zenith wasp
#

the ones with no inputs should act first

#

the problem is that the list I have is not in any guaranteed order

#

but all nodes need to have their inputs run before they themselves run

shut breach
#

any breadth-first traversal should be a valid order then

#

find the root, add it's adjacencies to an open set, deal with those, adding their adjacencies to the set, repeat

zenith wasp
#

what if there's multiple roots that merge into each other?

shut breach
#

instead of adding them to one open set, treat them as layers and deal with one whole layer before moving on

zenith wasp
#

how would I figure out what nodes are on the same layer?

shut breach
#

they're the adjacencies of the last layer

zenith wasp
#

🤔

#

but wouldn't that mean that in the last example Combiner and Splitter 2 are on the same layer as they're both a direct parent to Combiner 1

#

even though Splitter 2 should be two layers up from Combiner

shut breach
#

hmm yeah, so before adding each adjacent node, check whether all its inputs have been visited

zenith wasp
#

...do you have some pseudocode for that?

shut breach
#

all(input in closed for input in current.inputs)

zenith wasp
#

I was looking at topological sorts on wikipedia but they all require modifying the object somehow, and if I want to avoid that I'd need to make wrapper objects but that means allocation of a LOT of objects 60 times per second

zenith wasp
# shut breach `all(input in closed for input in current.inputs)`

this is not helpful in the slightest, so let me rephrase my question.
Given my situation, what algorithm, if one exists, would you recommend I use for getting a topological sort of these nodes?
If no current algorithm exists to solve this, could you give pseudocode for doing a similar topological sort to match the given constraints?

agile sundial
#

is there a reason topological sort doesn't work for topological sorting

zenith wasp
#

the ones I found on wikipedia are Kahn's algorithm (which is a no-go as it requires modifying the graph) and DFS (which I can't use because it requires marking/modifying the objects, and it also seems to require knowing the root)

agile sundial
#

with DFS, you just need a set of visited objects, right?

zenith wasp
agile sundial
#

you only need to care about that to verify if what you have is a DAG

#

if you're guaranteed a DAG, you only care about the permanent mark things

#

the permanent mark is basically just any way to identify a node has been visited, which could be a set

haughty mountain
#

you don't need to modify the graph

bold pelican
#

anyone any idea how to sort a string link list, plz do help

#

feel free to dm me

haughty mountain
#

have a count of the number of arcs pointing out of a node, start with all the leaves (0 arcs) append the node to the toposort output and then "remove" it (reduce the counts of the nodes with arcs pointing at the node), if this makes the count zero for any node it's a new leaf to consider

#

this is equivalent to actually modifying the graph and cutting connections

#

basically you just keep pruning leaves, exposing new leaves in the process

#

looking at the wiki I guess that's Kahn's algorithm

#

I never learned the algo as something with a name, it's just an intuitive thing to do

tacit nova
#

i have succeed/failed

sullen oxide
rose sphinx
#

hi

#

if i have any general predictive modelling questions is this the right channel

clear rose
solid thunder
#

Random "huh" moment: n//2 - p//2 is different from (n-p)//2 which had me stomped in an algo task 🙂

lament totem
#

yeah, that is why you shouldn't round your intermediate results 😛

solid thunder
#

Yup, learnt that the hard way 🙂

#

1 out of 27 tests failing, frustrating much 😉

ionic locust
#

are there any resources for intermediate complexity analysis practice questions.. The ones Ive found reuse many examples and are quite simple

haughty mountain
#

show that the sieve of eratosthenes is O(n log n)

#

bonus point: show that it's even O(n log log n)

#

the latter will require some light number theory

ionic locust
#

looks interesting, thanks

haughty mountain
#

I had this in one of my algo courses, though they only asked for n log n

#

I showed the second stricter bound for fun

jolly crypt
#

i am going through an algorithms and data structures book. So i learnt how the time complexity of recursive functions depends on the number of recursive calls and the number of operations within each recursive call (before the next one is called). So from my understanding, here supposing there are n files/directories (some nested inside others), there will be exactly n calls to disk _usage() (once for each file/directory).

Now there are not only primitive operations within the disk_usage function as there is a for loop and you need to work out childpath for each file in that directory. In the worst case a directory could have n files or even more, so isn't it the case that a call to disk_usage() is at least O(n*n) = O(n^2)?

Screenshot.png
#

Oh wait i guess because there are n files in total by assumption, not all directories will have n or more children (if they did then our original assumption is contradicted)
i think the book talks about amortization resulting in O(n), but if someone could explain me why that is the case that would be great

lament totem
#

Well the total amount of directories+files is n, so each function call will have have the amount of calls equal to directories+files in that sub-directory. And we know the total amount of directories+files is n, so the function calls in each function call sums to n.

zenith wasp
#

@vocal gorge (continuing here from #help-falafel) you mentioned np.argmax; How would that work? According to the docs it only takes a single array

#

the suggestion I got was also calling np.abs() on it first; wouldn't that lose information about the sign?

#

I think part of the problem is that you're assuming I create a single array from two lists; in reality I have two large N-dimensional arrays and concatenating them is going to be very costly on the allocation

vocal gorge
#

If they are truly two different arrays, hmm, annoying. Although... if it's always two arrays, you can simply do:

# 
maxes = arr1 # assume the first array's elements the larger
# When it's not the case, correct them to the second array's:
inds = np.abs(arr1)<np.abs(arr2) # that's three big allocations here
maxes[inds] = arr2[inds]
#

alternatively, maxes = np.where(np.abs(arr1)>np.abs(arr2), arr1, arr2) is basically the same thing

#

If performance and memory are important, though, the best way would probably be a custom numba function, doing something like

@njit
def max_abs(arr1, arr2):
    assert arr1.shape == arr2.shape
    result = np.empty_like(arr1)
    # let's assume they're 2d, there's probably a way to do this in general:
    n,m = arr1.shape
    for i in range(n):
        for j in range(m):
            a = arr1[i,j]; b = arr2[i,j]
            if abs(a) < abs(b):
                result[i,j] = b
            else:
                result[i,j] = a
    return result
#

there's probably a way to do this in general:
(actually, after a few seconds of thought, the way to do this for any shape is obvious: just create the array flattened at first, and iterate over flattened views into arr1 and arr2, then at the end reshape result to the right shape)

haughty mountain
#

why isn't this just something involving max(arr, key=abs)?

#

or is that not available for numpy?

vocal gorge
#

I don't think so, no

strong arch
#

Looking for a bit of advice if folks have the time. I'm designing a text based RPG with Python and Tkinter. Most things have been going well, but when it comes to the story text I was aiming to make it more dynamic. I've been storing most data in pickled JSON files (i.e. characters, items, locations, etc.) but when it comes to large bodies of text I've hit a pause to think. JSON doesn't seem to work well for this as you can't do multi line strings. So, I've been considering YALM. If anyone has advice on how to approach this, that would be amazing. Working within PEP 8 and having many paragraphs is looking challenging. lol

vocal gorge
#

Ah, you mean it's annoying to write the lines in JSON itself, hmm.

strong arch
#

I also couldn't find a solution in JSON that would allow a multi line string, else it wouldn't be so bad. I'd drop it in at the paragraph level. But, does not seem to be an option from what I read.

zenith wasp
#

In that case yaml might be better, yeah. Have you looked at pyaml?

strong arch
zenith wasp
#

oh actually it looks like pyaml was renamed to yaml and later removed and the current pyaml is for serializing only

strong arch
#

If I switch to YAML I might switch everything over to that for simplicity.

strong arch
zenith wasp
strong arch
#

I know that YAML can be used with Python because I've seen it used in many projects. Just haven't spent much time with it, though I understand the structure.

#

I guess the only drawback of YAML is the lack of security, not that pickling secures much. It just makes it less easy to change attributes of characters, items, etc. lol

spiral raptor
#

Hello
Does anyone know a good resource on dynamic allocation in sequential lists with Python?
I've been looking for days, and I haven't found any videos or resources on the topic
Thanks in advance

vocal gorge
spiral raptor
# vocal gorge You mean, how Python's `list` resizes when it runs out of space?

Not exactly
I want to know how to do dynamic allocation in lists with Python.
Let's say I have the following list ['a', 'b', 'c']
And I wanna do things such as insert an element, remove an element, search an element by its index, ...

Let's say I wanna add the letter 'Z' to index 1, so that means my list will be as follows ['a', 'Z', 'b', 'c'], and same thing if I were to remove an element.

Keep in mind, I don't wanna use in-built functions, such as append, remove, pop, and so on, I wanna build my very own functions
does that make sense?

vocal gorge
#

You're pretty much trying to rewrite lists from scratch, then.

spiral raptor
vocal gorge
#

It's not really nice to do in Python, since it already has stuff like refcounting of every object implemented, and abstracts it all away from you.

spiral raptor
#

C?

vocal gorge
#

Something like C or Rust would do, yeah. (In C you have to do this, even, since it basically doesn't have a standard ibrary).

#

But as an example if you want to do it in Python, you can use the array builtin library to create arrays, and write based on it your own list for a specific type of elements. You'd still need to handle stuff like copying the array to a new bigger one when it runs out of space, etc.

spiral raptor
#

Seems like it's time to learn C

#

What are your thoughts about C, is it still used in the market?

#

As far as I know, it is the only programming language that can be used for real life embedded software, besides Assembly.

spiral raptor
vocal gorge
vocal gorge
spiral raptor
vocal gorge
#

There's nothing C can do that those languages can't (the same is true for C++, by the way), it's just that they require you to be more conscious of when you're doing potentially memory-unsafe stuff, as opposed to C where everything is completely unchecked.

spiral raptor
#

I see

#

so, what is the use of C then?

#

I mean, when do you want to use C?

vocal gorge
#

Personally, I don't 😛

#

you might be forced to use C if developing for something that LLVM doesn't support, say (but that's not super common even for embedded devices). And of course, it's just still more popular and you might find it easier to find support.

spiral raptor
#

@vocal gorge, I see
do you think Python is a good choice when learning DSA?

#

it seems to abstract things way too much

opal oriole
spiral raptor
opal oriole
#

Zig is also a C compiler. Some use it as their C compiler. Zig is designed to eat C projects, you can slowly rewrite parts of the project bit by bit since C and Zig can be mixed.

#

D also has a C parser now I think for automatic bindings / C interop.

vocal gorge
#

Personally, I was originally taught DSA in Java and found it decent-ish for it. Python is also pretty decent. Ultimately, stuff like linked lists and stacks and trees doesn't depend on low-level details. A lower-level language will be better at teaching you, say, why dynamic arrays are in practice more efficient than linked lists (no indirection), but all this doesn't affect asymptotic complexities and stuff like that.

spiral raptor
opal oriole
#

C is still the lingua franca of the programming world as all operating systems (the big three) and many programming languages are written in it (with some assembly).

spiral raptor
#

I only mentioned C, because all of the embedded software engineers that I've seen on the internet use it, and companies assume that you have a strong foundation in C before getting into embedded software dev

spiral raptor
spiral raptor
#

I don't think so, right?!

opal oriole
#

For what you are trying to do I would just use C, it's simple and lets you learn the thing you are trying to learn (making dynamic arrays).

#

Zig, Odin, C++, Rust, D, etc, either have dynamic arrays built in the language as a type or in the standard library.

#

(Because it's so common / essential)

spiral raptor
opal oriole
spiral raptor
opal oriole
#

It's main thing is that it's simple and let's you do all the things you need to do (be fast and all that / control hardware). It's simplicity combined with standard spec. (especially ABI) makes it universal and easy to implement a compiler for (so it shows up everywhere).

vocal gorge
opal oriole
# opal oriole Zig, Odin, C++, Rust, D, etc, either have dynamic arrays built in the language a...

C has unofficial / community standard libraries that contain arrays, dynamic arrays, hashtables, etc. And unlike the C standard library it will not cause your program to probably burn and crash (don't use the C standard library, if you do, your program is probably wrong/broken in some way (it's poorly designed because it's really old and never got updated and was designed for a machine nobody uses anymore at a time nobody knew what the best ideas were (no hindsight yet))).

spiral raptor
opal oriole
#

CUDA is Nvidia GPUs only.

opal oriole
spiral raptor
agile sundial
#

it doesn't really focus on the algorithm side of things (which tbh, isn't really that fun with vecs), but more of the low level details

spiral raptor
glossy mulch
#

really small question: is string indexing to look at its chars ("..."[i]) any slower or faster, if you're indexing it dozens and dozens of times, than converting it to a list first?

tacit nova
#

question about big O
we have a matrix, and we loop all 4 borders (first row, last row, first column and last column ONLY). The borders are very small data, but as the matrix grow, it will grow too. So I think this is O(logn) for speed and space right ?

jolly mortar
#

the order of the matrix (no. of rows/columns) or total number of elements

tacit nova
#

total elements

Screen_Shot_2022-06-26_at_12.01.58_AM.png
jolly mortar
#

so, 16 for this matrix?

tacit nova
#

yes 🙌

jolly mortar
#

then it would be O(sqrt(n))

#

each border has sqrt(n) elements

#

4 borders, so 4sqrt(n) which is O(sqrt(n))

#

*assuming its a square matrix

tacit nova
haughty mountain
#

I much prefer working with the height and width in these situations, rather than trying to reconstruct stuff using a square root

#

obviously what we would scan is linear in the height and width O(n + m)

covert stirrup
# 
salary = [48000,59000,99000,13000,78000,45000,31000,17000,39000,37000,93000,77000,33000,28000,4000,54000,67000,6000,1000,11000]

salary.sort()
salary.pop(len(salary)-1)
salary.pop(0)
n = 0
for t in salary:
    n = t + n
avg = n / len(salary)
print(avg)
#

You are given an array of unique integers salary where salary[i] is the salary of the ith employee.

Return the average salary of employees excluding the minimum and maximum salary. Answers within 10-5 of the actual answer will be accepted.

#

Is this a fast way of doing it

#

And also

#

Why does it print the correct answer here

#

But on leetcode

#

It prints the rounded down version?

vocal gorge
# 
import random, string
long_string = "".join(random.choices(string.ascii_letters, k=500))
i = random.randrange(len(long_string))
long_lst = list(long_string)

%timeit long_string[i]
%timeit long_lst[i]

79.2 ns ± 2.08 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
77.3 ns ± 4.46 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

difference of 2ns whereas the sum of stds is 6ns. That's statistically insignificant. Tiny differences like that are hard to measure.

glossy mulch
#

in that case i'm still not sure which to use, lol

#

my use case is a probably-small user input that can be assumed to often be right, which means every single character will be stepped over by the function

#

so just strings, to save the time making lists?

vocal gorge
#

I'd use the string, because converting to a list is a Weird Optimization, and Weird Optimizations reduce readability and should only be used when they are shown to actually have a positive effect - which this one doesn't seem to.

glossy mulch
#

ye

#

okay back to my weird programming now

haughty mountain
haughty mountain
drifting owl
# 

pibpm = C + I + G + NX
pibcf = W + EBE
pibpb = P - CI
EBE = R + L + J
Nx = x - f

pibpm = pibpb + tip 
pibpm = pibcf + tit
pibpb = pibcf + tilp
pibcf = pibpb - tilp    
pibcf= pibpm - tit

tit = tilp + tip
tip = tit - tilp
tilp = tit - tip

If i had an equation system like this and i wanted to get it on python to solve it given few random inputs how would i do that

brittle warren
#

how should i do this problem, don't know how to do this recursively

unknown.png
drifting owl
brittle warren
#

coding ninjas

#

its an online course

agile sundial
drifting owl
#

i guess you could make a fucntion to give you the string index and another one which calls the other one with a loop and loops trought all the indexes

#

Would be easier just to compare them and add a counter

#

if counter >= len

#

Yeah

brittle warren
#

that won't work

agile sundial
#

why do it recursively though

drifting owl
#

wdym wont work

drifting owl
brittle warren
brittle warren
agile sundial
#

oh well, probably just make a recursive find function, that looks for the next character starting at a certain index

drifting owl
brittle warren
#

how tho?

#

im still learning

drifting owl
#

do a double loop

#

first loop iterates trought the 1st str and 2nd loop trought the 2nd if s[i] == t[j] just add 1 to a counter

#

then print(coounter >= len(s))

brittle warren
#

what if i wanted to do it recursively?

drifting owl
#

get a function to return the index keys and compare them in the 2nd functions

#

so the 2nd functions keeps calling the keys from the values

#

i see no point in doing i trecursvely tought

# 

t = str(input())
s = str(input())
counter = 0

for i,let in enumerate(t):
    for j,char in enumerate(s):
        if let == char:
            counter = counter + 1
        else:
            pass

print(counter >= len(t))
#

Something along these lines would do the job

brittle warren
#

well, not every test cases pass

drifting owl
#

input and expected ouytput?

brittle warren
#

counter - 7

drifting owl
#

the counter should be >= S

#

the size of the smaller string

#

mb

#

should be the string youre comparing with IN

brittle warren
drifting owl
#

Well so take a look cause that code on my end is working fine

#

Do you understand what every block of code does?

#

I ran the exact same text case and it worked just fine

brittle warren
#

i don't see a difference

unknown.png
drifting owl
#

i mean

#

first why dont you just print(contains(s,t))

#

Why you still doing conditions in there

#

youre already getting a true or false answer

#

you can just print it

brittle warren
#

you're right

#

but, the expected output is a lowercase true/false

#

not True/False

haughty mountain
#

this kind of thing should work

i = -1
for c in t:
  i = s.find(c, i+1)
  if i == -1:
    return False
return True
rough lynx
#

I feel like I'm missing basic knowledge about replacing nested loops with some other algorithm

x = [1, 2, 3]
y = [4, 5, 6]
for i in x:
  for j in y:
    print(f"{i}, {j}")

I know there's zip like for i, j in zip(x, y) but that just makes 3 combinations of (1, 4), (2, 5), (3, 6)

vocal gorge
#

that'd be itertools.product, not zip

rough lynx
#

Ah that was it
Trying to write down important code snippets that I should be using instead of typical nested loops

fossil wraith
#

The print statement can be formatted as required

rough lynx
#

That's not going to help, and is actually less efficient
I'm actually going through a ton of old coding projects and getting rid of that type of iteration
This:

x = [1, 2, 3]
for i in range(len(x))):
  print(x[i])

Is a worse version of:

x = [1, 2, 3]
for i in x:
  print(i)

If you need the index and value at that index, a smarter way to do it is:

x = [1, 2, 3]
for i, v in enumerate(x):
  print(f"Index {i}, value {v}")
#

I used to do that version you recommended when I was first moving from an entirely C++ background to Python when C++ loops are like for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++)

#

But it's not sensible for Python and shows lack of knowledge / comfort with the language

fossil wraith
#

Could someone please me understand the way to solve this?

Question

In a university, your attendance determines whether you will be allowed to attend your graduation ceremony.
You are not allowed to miss classes for four or more consecutive days.
Your graduation ceremony is on the last day of the academic year, which is the Nth day.

Your task is to determine the following:

  1. The number of ways to attend classes over N days.
  2. The probability that you will miss your graduation ceremony.
    Represent the solution in the string format as "Answer of (2) / Answer of (1)", don't actually divide or reduce the fraction to decimal
    Test cases:

for 5 days: 14/29

for 10 days: 372/773

I found a logic here, but I seem to have forgotten the probability topics studied in school! https://math.stackexchange.com/a/4170321

Mathematics Stack Exchange
Number of ways of attending classes over N days

Problem Statement
In a university, your attendance determines whether you'll be allowed to attend your graduation ceremony. You are not allowed to miss classes for four or more consecutive days. You

runic tinsel
#

@fossil wraithok i remembered F(n) = 2F(n−1) − F(n−4) is not the complement, it's the actual number of ways to not skip 4+

#

on the last say if you haven't skipped 4+ yet, you can go or not go, except there are cases where your n−1 ends like go-skip-skip-skip, and their amount would be equal to F(n−4), that has to be subtracted. or that's F(n−5) that makes more sense

#

what's your question?

runic tinsel
#

the test cases i don't understand, there's something missing

#

it's a strange problem, it implies that you flip a coin to determine if you go to class

covert stirrup
#

python can do that?

#

min and max()?

#

bruh

#

💀

verbal bolt
covert stirrup
elfin mortar
#

e e:/Python/question_test.py
Traceback (most recent call last):
File "e:\Python\question_test.py", line 1, in <module>
from question import Question
ImportError: cannot import name 'Question' from 'question' (e:\Python\question.py)

elfin mortar
#

any idea?🤔

dull quail
#

what is theory of computation??

#

could someone give me a brief, easy to understand description of what it is and its applications?

#

i dont really get what im reading online

tacit halo
#

__init__

elfin mortar
shut breach
#

prove things about mathematical models of computers

hollow nebula
# brittle warren 
string2 = list(input())
for s in string1:
    if s == string2[0]:
        string2.pop(0)
print(len(string2)==0)```
hollow nebula
calm sandal
#

Anyone knows how to implement an interpolation search to a binary tree created with linked lists?

fiery cosmos
#

what would be the formula for the number of comparisons of comparing every item n in an array of length n with every other item

agile sundial
fiery cosmos
#

idk i tried working it out on a whiteboard and i was getting different formulas for different input length n

agile sundial
#

the formula would look different for different n, but if you generalize it to just n, then you'd get 1 formula

fiery cosmos
#

n^2 - 3n works when the input length is 5

agile sundial
#

are you just guessing formulas?

fiery cosmos
#

right

agile sundial
#

think about it a bit more logically

#

if you have n=1 elements, how many comparisons do you need

fiery cosmos
#

0

agile sundial
#

right, now for n=2?

fiery cosmos
#

1

agile sundial
#

for n=3?

fiery cosmos
#

3

agile sundial
#

for n=4?

fiery cosmos
#

6

agile sundial
#

actually, we did look at this sequence before, when you were trying to learn induction

#

if you notice, each time you add a new element, you need to compare that to all the elements that already existed

fiery cosmos
#

so how would one generalize a formula for this

#

i don't really need to solve this problem i just got involved bc im writing an algorithm to compute the euclidian distance of points and the way its working now it only compares the first element to all others

agile sundial
#

think about it. this is the key thing you have to understand

each time you add a new element, you need to compare that to all the elements that already existed

fiery cosmos
#

so i thought it'd be nice as a proof to see later when i think its working if its drawing the correct # of comparisons

#

does that mean you have to add another variable

agile sundial
#

no, i'm talking about when you increase the n

#

say you have n=3 elements. when you add a 4th element, you need to compare that 4th element to the 3 elements that already exist, right?

fiery cosmos
#

correct

agile sundial
#

so, if we generalize to say that you have n elements, and you add a n+1th element

#

how many extra comparisons do you need?

fiery cosmos
#

n-1

#

er

#

maybe just n extra comparions

#

for the n+1th element

agile sundial
#

exactly, so now all you need to figure out is how many comparisons n elements need

fiery cosmos
#

n-1

agile sundial
#

not quite

#

say n=4, the number of comparisons is 6

#

to go to n=5, we add 4 extra comparisons (the 5th element is compared to all the existing ones)

#

but 6 isn't 4-1

haughty mountain
# 
f(n+1) = f(n) + n
fiery cosmos
#

i think the n+1 part is confusing me. how would you calculate it for n

# 
import math

def closestpairs(points):
    pointsarray = []

    with open(points) as inf:
        for line in inf:
            pointsarray.append(tuple(line.split()))

    itemsleft = len(pointsarray)-1
   
    for i in range(0,itemsleft):
       
        x_diff = int(pointsarray[i][0]) - int(pointsarray[i+1][0])
        y_diff = int(pointsarray[i][1]) - int(pointsarray[i+1][1])

        x_diff_sq = x_diff*x_diff
        y_diff_sq = y_diff*y_diff

        euc = math.sqrt(x_diff_sq + y_diff_sq)
#

i also cannot figure out how to get the nested loop right in this. it would have worked if i could declare a variable in a loop header but of course we cannot

haughty mountain
#

f(n) = 1 + ... + (n-1)

#

we did this example when we did some induction examples

fiery cosmos
#

yeah all im trying to know is given an input array of length n how many comparisons must i make to compare every item to every other. this is overcomplicating it i think

#

also in the above code i know that i need another for loop but i cannot figure out how to implement that

#

like i have py for i in range(0,itemsinarray)
but that only compares the first item to every other? or the way its written it only compares the ith item to the very next and then moves on? idk how its working but i know its not making all the comparisons required

#

yeah it only compares the ith item to the very next and then moves along, which doesn't compare say item 3 to item 5

#

maybe i need to make a variable equal to the length of some range

#

no that doesn't make sense

#

yeah im gonna have to totally change the way this is written

agile sundial
#

you need 2 loops

fiery cosmos
#

correct

#

ohhh

#

well first of all i don't need that itemsleft variable

#

x_diff = int(pointsarray[i][0]) - int(pointsarray[i+1][0])

#

this line needs to change

#

i need to compare the x with every other x using a loop somehow instead of just the i+1th x

#

shoot im going to have to store the tuple for comparison as a variable huh

#

alright here's my pseudocode for a nested loop to get this done:

for x in A['a','b','c']:
  itemsleft = len(A)
  while itemsleft:
    do_something
    itemsleft-=1```
#

making sense? maybe i should have just looked this up rather than reinventing the wheel..

#

no that while gets rid of my index i i need

#

hm i keep getting py TypeError: 'int' object is not iterable

#

why do i need 2 loops? why can i not just compare element 1 to all remaining, increment by 1, compare element 2 to all remaining, increment by 1?

#

maybe the only way to actually do that is with 2 loops

agile sundial
#

you just described a loop inside of a loop

fiery cosmos
#

googling for it brings up itertools

#

i found this implementation, how does it work?

for i in range(len(mylist)):
    for j in range(i + 1, len(mylist)):
        compare(mylist[i], mylist[j])
#

looks like they are just comparing 2 subarrays

agile sundial
#

well, it's one array, just with two different index variables

agile sundial
fiery cosmos
#

interesting

#

don't you need to put the start value into the range

agile sundial
#

no, if you omit it, it's set as 0

fiery cosmos
#

ok

#

so the way i've written my code i need to keep a separate variable for the length of the array, otherwise i get list index out of range error. but in doing so i've made the algo just print the same information the number of times equal to that length

#

its not incrementing in the subloop

#

looks like this:

    itemsleft = len(pointsarray)-1

    for j in range(itemsleft):
 
        for i in range(itemsleft):
#

and again its not doing a sufficient number of comparisons

# 
import math

def closestpairs(points):
    pointsarray = []

    with open(points) as inf:
        for line in inf:
            pointsarray.append(tuple(line.split()))

    itemsleft = len(pointsarray)-1

    for j in range(itemsleft):
 
        for i in range(itemsleft):
               
            x_diff = int(pointsarray[j][0]) - int(pointsarray[j+1][1])
            y_diff = int(pointsarray[j][1]) - int(pointsarray[j+1][1])

            x_diff_sq = x_diff*x_diff
            y_diff_sq = y_diff*y_diff

            euc = math.sqrt(x_diff_sq + y_diff_sq)
                   
        #print(x_diff,y_diff)
        print(math.floor(euc))
#

looks like this

fallow coyote
#

trying to convert some js code to python for a project, and im stuck on the if statement. how do i know if it is a buffer?

unknown.png
fiery cosmos
#

so in trying to understand what a nested for loop is really doing i have written the above example. however, in the way it is written it seems as if i would only be comparing each banana to each other banana in the same cluster

lament totem
#

What does the bottom line say @fiery cosmos ?

#

compare banana to bananas?

fiery cosmos
#

right

#

i mean trivially i could just write some different phrasing like for banana in cluster(s), compare banana to bananas, but implementing that is different. the reason i've written it in such a way is the problem im trying to solve does not involve comparing each element in an array to all others, but rather each subelement in an array with all other subelements. in other words if given an input array of tuples like A[(a,b),(c,d),(e,f)] i want to compare and compute things on a and c, c and e, b and d, d and f, etc

#

this runs but clearly is not doing want i'm thinking. i think by using j in my statements i am omitting the nested loop altogether?

# 
    for j in range(itemsleft):
 
        for i in range(j+1, itemsleft):
               
            x_diff = int(pointsarray[j][0]) - int(pointsarray[j+1][1])
            y_diff = int(pointsarray[j][1]) - int(pointsarray[j+1][1])

            x_diff_sq = x_diff*x_diff
            y_diff_sq = y_diff*y_diff
#

but if i instead use the index i it simply prints the same thing over and over

opal oriole
#

During the inner loop j does not change value.

fiery cosmos
#

i'm thinking i'll need to name each tuple for comparison purpose. or at least give each an index

opal oriole
#

i changes value.

fiery cosmos
#

well it doesn't run when i use i

#

or at least, it just prints the same thing over and over

opal oriole
#

Create the two for loops but just print i and j in the inner loop.

fiery cosmos
#

you mean like as a learning exercise?

opal oriole
#

Yes, but also known as print debugging.

fiery cosmos
#

looks like it goes 1,0, 2,0, 3,0, ...

opal oriole
#

i,j?

fiery cosmos
#

when i implement

print(i)
print(j)```
opal oriole
#

That would print two different lines, what do you mean with 1,0, 2,0, 3,0,?

fiery cosmos
#

yes or your way 1 0
2 0
3 0

#

and so on

opal oriole
#

Is the first number i and the second j?

fiery cosmos
#

yes

opal oriole
#

Ok, does it eventually get to something like x 1 (e.g. 1 1 or 2 1).

fiery cosmos
#

it terminates with 23 22

opal oriole
#

Ok, so the loop is not the issue then. You are trying to compare all items to all other items?

fiery cosmos
#

all subitems to other subitems like given input txt file of one number followed by another number (representing points) i arranged them as 2-tuples and i want to compare each first item in each tuple with all other first items

#

and compute something on that

opal oriole
#

So you have an array of tuples?

fiery cosmos
#

that's how i've organized the data after reading in a text file, yes. looks like:

opal oriole
#

And you want to compare the first element of each with the first of every other?

fiery cosmos
#

[('19619', '19602'), ('15159', '12184'), ('520', '30721'), ('11689', '16619'), ('20820', '30175'), ('4483', '12308'), ('8421', '8360'), ('15208', '14169'), ('27673', '16733'), ('26571', '30985'), ('32191', '26639'), ('20752', '8229'), ('23419', '26652'), ('18610', '7993'), ('20036', '18537'), ('18464', '200'), ('32325', '24328'), ('31252', '30119'), ('18005', '31402'), ('11598', '2807'), ('13729', '27556'), ('30136', '12865'), ('11283', '28966'), ('31024', '3001'), ('6185', '1696')]

#

yes but is has to be done at the same time as when i compare the second element of each to every other, bc i have to compute something given each pair (a,b),(c,d) that involves a+c,b+d, return some expression after computing both

opal oriole
#

You are trying to compare all items to all other items? - So you are doing this.

#

Each item can contain more than 1 thing.

fiery cosmos
#

well i dont need to compare say a to d in this example (a,b),(c,d)

opal oriole
#

Oh, compute something with each pair.

fiery cosmos
#

correct

opal oriole
#

Ok, so your two loops were looking ok.

fiery cosmos
#

should i link the entire code?

opal oriole
#

Your problem is this: ```py
x_diff = int(pointsarray[j][0]) - int(pointsarray[j+1][1])
y_diff = int(pointsarray[j][1]) - int(pointsarray[j+1][1])

fiery cosmos
#

right i know i need to work i in there somewhere but then it just returns the same thing over and over

#

omg

#

my print statements were indented to the outer loop

#

🤦‍♂️

#

what is squeezed text?

#

seeing it upon outputting a new array

#

in IDLE

#

nvm, can google

#

is it reasonable to use math.floor(x) to return a nice rounded integer x?

#

or is that computing something im unaware of

#

looks like round() is more appropriate

#

it looks like the way i have written this im only doing 23 comparisons, and should be doing 24 for each item(comparing the item with all others) my input consists of 25 points. in trying to avoid the list index out of range error ive inadvertently made this not compute the final comparison it seems

#

i think i can fix it with an if check

#

no, nvm that would just not make it compute when im near the end

#

what i am struggling with now is how to handle naming

#

for example, i now have an output array with the proper distances stored in it, but there is no information about which points in my input array gave rise to the distance. each point in the input array will have its own index, so i'll need to figure out how to use those.

#

i'm thinking something in my outer loop

opal oriole
fiery cosmos
#

so right now i am printing the name of the point using the outer loop and the j in for j in range...