algos-and-data-structs

[fiery cosmos]

haven't figured how to handle point comparisons

i think i need to rewrite using like P1_x = somename and P2_x = somename and then use those names in my comparisons

[opal oriole]

I'm not sure what you are trying to do.

[fiery cosmos]

im trying to compute and return the closest distance between any two points, which i could easily do by returning the lowest value in my output array. however, i need to handle naming within the function, that is, i need to return something like "the shortest distance between any two points is points 7 and 14 with a distance of 21023

i have the distance part, but haven't handled with points are giving rise to that shortest distance. i also need to return the coordinates of the two closest points.

[opal oriole]

If you computed the distance you already have the two points, j and i.

You just need to make them part of the output.

[fiery cosmos]

i need to return their coordinates as well

[opal oriole]

Your output list contains a bunch of distances, there is nothing stopping you from just doing (index a, index b, distance) instead.

[fiery cosmos]

hmm

ok the issue is i am only appending a single number to my output list after each comparison

the distance between the points being compared

lms

can i do like for tuple in array

to handle them as points?

[opal oriole]

Yes, you already did that before when looping over the points.

[fiery cosmos]

in the outer loop yes. but when i print for j in range it doesnt return the tuple it returns 0 or 1 or the index

ohhh

its bc i made a new variable itemsleft

[haughty mountain]

this is a pretty common pattern

min_distance = 1e100 # large value
min_pair = None
for i in range(n):
  for j in range(i+1, n):
    d = distance(p[i], p[j])
    if d < min_distance:
      min_distance = d
      min_pair = i, j

[opal oriole]

Yeah, getting to that, for now I wanted to build off of what they were already doing with two separate loops (output list in between).

[haughty mountain]

I hope your plans extend to reducing it to a oneliner :P

[opal oriole]

If we have time.

[fiery cosmos]

man i totally botched this trying to get rid of my itemsleft variable

when you loop through a range youre losing the information stored in the tup?

[opal oriole]

No, because you have an index into the list, which contains all the information.

[fiery cosmos]

oooh i see where i went wrong. i was doing

for j in range (0,itemsleft):
  print(j)```

i needed to do py for j in range (0,itemsleft): print(pointsarray[j])

hmm still doing something wrong

whats goofing me up is trying to handle the names universally but needing to do that within the nested loop

it only works when i handle them at the level of the outer loop bc theres something i dont understand

[fiery cosmos]

i'm beginning to think im just not left brained enough for this

or like maybe i dont have the logical/analytical capacity

[haughty mountain]

what's your code?

and what's confusing?

[fiery cosmos]

import math

def closestpairs(points):
    pointsarray = []

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

    itemsleft = len(pointsarray)-1

    output = []

    for j in range(0,itemsleft):

        #print(pointsarray[j])
 
        for i in range(j+1, itemsleft):

            #print(i,j)

            x_diff = int(pointsarray[i][0]) - int(pointsarray[i+1][1])
            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 = round(math.sqrt(x_diff_sq + y_diff_sq))
            #print(math.floor(euc))
            output.append(euc)     

        
        #point1=pointsarray[j]
        #point2=pointsarray[j+1]

        #print(point1)
        #print(point2)

       
        

            #print(x_diff,y_diff)

    print(output,len(output))

i dont know how to handle the naming and passing the names of each point into the output array. i cannot do it within the nested loop bc its too granular and i get lost in what im currently working on? idk. im beginning to think that im just not meant for learning code

[opal oriole]

First, note that: ```py
x_diff = int(pointsarray[i][0]) - int(pointsarray[i+1][1])
y_diff = int(pointsarray[i][1]) - int(pointsarray[i+1][1])

[fiery cosmos]

i just want to get a better job that doesn't involve getting my CDL

[haughty mountain]

oh yeah, that part has several issues

i and i+1 instead of i and j

the 0 and 1 indexing is also off

[fiery cosmos]

sigh

should i just start over using itertools

[opal oriole]

No.

You are a few small tweaks away from something that works.

[fiery cosmos]

so i can see that @haughty mountain posted some code with the nested loop reading for j in range(i+i,n)

thats the idea behind that

why is the concept of a nested loop so confusing

one loop says for each item, do x.

[opal oriole]

For each thing, we need to compute the distance to each other thing.

[agile sundial]

you already have the concept here

[fiery cosmos]

then two loops would say?

[opal oriole]

Multiple things to multiple things.

(loop, loop)

[fiery cosmos]

did anyone see my example with the clusters of bananas?

[opal oriole]

Yes.

That is a different problem though.

[fiery cosmos]

i just wanted to appreciate the concept of a nested loop more generally

and in that case it seemed like you would only be comparing each item to all other items in the group, not all other items total

i just dont see how to handle the names of each point using their indices in the array given that im computing something within a nested loop and at that level idk if you can?

[opal oriole]

What do you mean by the "names"?

[fiery cosmos]

like point 1 is the point at index 0, point 2 is the point at index 1, etc

that way i can make a return that prints their coordinates

[opal oriole]

pointsarray[0]
pointsarray[1]
``` Indexing starts at 0, so [1] is point 2.

[fiery cosmos]

right

[opal oriole]

You are already doing it.

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

[fiery cosmos]

but is point1 = pointsarray[i] or pointsarray[j]

[opal oriole]

It does not matter, you just have some pair of points, i, j.

point1 is either pointsarray[i] or pointsarray[j], your choice.

(distance from a to b is the same as the distance from b to a)

[fiery cosmos]

wat

[opal oriole]

When looping, you are getting two points, j and i.

[fiery cosmos]

i mean universally if each point had their own index i have 25 inputs and so would have 25 different points

[opal oriole]

hmm I think I might know what you mean.

point1 is neither poinsarray[i] nor pointsarray[j].

[fiery cosmos]

right

[opal oriole]

point_i is pointsarray[i] and point_j is pointsarray[j].

You don't assign a variable name to each point manually. Like point1, point2, point3, etc.

[haughty mountain]

the i+i was a typo, should be i+1

[fiery cosmos]

ahh ok 🙂

i knew that didn't make sense few

[fiery cosmos]

this is what i have to do before going into the loops i think

[opal oriole]

   x_diff = int(pointsarray[i][0]) - int(pointsarray[i+1][1])
   y_diff = int(pointsarray[i][1]) - int(pointsarray[i+1][1])
``` Let's get back to this later and focus on what I think you are trying to do.

[fiery cosmos]

ok

[opal oriole]

Which is modify this: ```py
output.append(euc)

You want your output to contain which points the distance is associated with.

[fiery cosmos]

correct

[opal oriole]

This is an easy fix: ```py
output.append((j, i, euc))

It now contains all three things.

[fiery cosmos]

i tried that before, append takes only 1 argument

[haughty mountain]

that is one argument

a tuple

[fiery cosmos]

ohh

[opal oriole]

(like how a point is one thing)

[fiery cosmos]

how can you tell that each point is given by i and j? i cannot see that reading the code the way it is

it lets lost in the mix

i guess i could just print i and print j to see it

[opal oriole]

print(pointsarray[j], pointsarray[i])

In inner loop.

[fiery cosmos]

at what level

ok

[haughty mountain]

because i and j are the indices of the points you are iterating over?

[opal oriole]

You don't have i in the outer loop.

In the outer loop you are getting the first point, and in the inner the second point.

So in the inner you have both points (so you can print both).

In the inner loop you can access anything from the outer loop and stuff outside of it too. But in the outer loop you can't access stuff made in the inner loop (including i). So in general you can only access stuff that is "higher up" (which is why you have both j and i in the inner loop and everything else, it's the most nested / deepest).

This is the general idea of "scope" in programming languages.

[fiery cosmos]

right this is why the scope was confusing me, at the level out the outer loop i'm looking through each point given by j, but in the inner loop where im doing the important computation, i don't know what j then becomes

hmm

don't know how to structure my print statement

min will return the smallest euclidian distance

i think i am printing the shortest distance, and coordinates of the nearest points. but how to structure the print statement to say the points at coordinates (x_1,y_1) and (x_2,y_2) is confusing

oooo

alright so i've got it working i think? but i still believe that the number of comparisons is 1 less than it should be, because of the
itemsleft = len(pointsarray)-1

i guess this is when i learn how to debug 🙂

oh no its doing 24 comparisons given the first point, which is what i'd want to see

not including the function call and the file, this is the code:

import math

def closestpairs(points):
    pointsarray = []

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

    itemsleft = len(pointsarray)-1

    output = []

    for j in range(0,itemsleft):

        for i in range(j+1, itemsleft):

            x_diff = int(pointsarray[i][0]) - int(pointsarray[i+1][1])
            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 = round(math.sqrt(x_diff_sq + y_diff_sq))
            
            output.append((euc,pointsarray[j],pointsarray[i]))

    print(len(range(0,itemsleft)))

    minimum = min(output)
    print('the shortest distance between two points is ' +
          str(minimum[0]) + ' '+ 'and is between points with coordinates ' +
          str(minimum[1]) + ' ' + 'and ' + str(minimum[2]))

and I think it works 🙂

[opal oriole]

During the inner loop j is constant / unchanging.

[fiery cosmos]

    for j in range(0,itemsleft):

        for i in range(j+1, itemsleft):

could we break apart how this looks conceptually

[opal oriole]

It's best shown with an animation.

[fiery cosmos]

hm ok

[opal oriole]

Can't find one right now so starting with the first loop.

j is 0, now the inner loop starts.

the inner loop has i = j + 1 or i = 1

[fiery cosmos]

i is 1

[opal oriole]

the inner loop runs until it is finished, that is until i is itemsleft

[fiery cosmos]

then j goes to 1

[opal oriole]

yes

[fiery cosmos]

i=2

[opal oriole]

and repeat

[fiery cosmos]

so in my mind i see it doing less comparisons as the loops go on is that it?

bc itemsleft is static

[opal oriole]

Yes, the i = j + 1 thing to avoid duplicates

[fiery cosmos]

and as it goes on it gets ever closer to the end of the list

[opal oriole]

Imagine you just had i = 0

and j is currently 3

You would have (3, 0), (3, 1), (3, 2), etc.

(j, i)

But now lets look at what the previous iteration of the outer loop looks like (when j was 2)

You had:

(2, 0), (2, 1), (2, 2), etc

First note that (2, 2) is not something you want, distance with itself.

[fiery cosmos]

i can visualize it in my mind but its difficult to show on paper

[opal oriole]

And that eventually you will get (2, 3), which is the same as (3, 2).

[fiery cosmos]

ah ok

[opal oriole]

You did a repeat.

(and also with itself)

[fiery cosmos]

you mean if it instead said for i in range(0,itemsleft)?

[opal oriole]

See those arrows on top? The inner loop is doing those. (i = 1, i = 2, i = 3)

We are computing the pairs.

Try drawing j = 1.

and let i = 0 in the inner loop

then draw it again, but this time with i = j + 1

[opal oriole]

Yes.

(Note I just have a single number here for simplicity rather than a point, does not matter though)

[fiery cosmos]

this what you wanted me to see?

wait

[opal oriole]

Note that when you do i = j + 1, it only goes to the right of j

But if you let i = 0, sometimes it will be to the left, and sometimes equal to j

[fiery cosmos]

hmm

[opal oriole]

(i = j + 1)

(Note that we only do the pairs once (e.g. only (4, 8) once))

[fiery cosmos]

it being nested, wouldn't i = 0 just point at the item itself?

[opal oriole]

i = 0 would put it at the start of the array

[fiery cosmos]

ok

[opal oriole]

The outer loop does not affect the inner loop unless you let it.

(e.g. i = j + 1)

(No implicit shenanigans)

[fiery cosmos]

but in my inner loop. i'm not looping through the array, but rather a range from 0-24

i don't call attention to the array itself until my x_diff = variable declaration

[opal oriole]

That is the same. See how I drew an arrow for j?

You can imagine the indices are "pointing" to some element of the array.

So looping through indices is effectively the same as looping through the values of the array since you can get the value from the array using the index.

[fiery cosmos]

right ok. i just feel like here:

    for j in range(0,itemsleft):

        for i in range(j+1, itemsleft):

            x_diff = int(pointsarray[i][0]) - int(pointsarray[i+1][1])
            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

[opal oriole]

If you do something like for blah in foo: in Python it's internally using index looping anyhow, it's just nicer sometimes to write this way so Python provides it as an option.

[fiery cosmos]

the inner loop has no idea of values in the array until set them equal to some variable. otherwise it only knows its beginning at element zero and going to some higher element

[opal oriole]

The inner loop has an index that is increasing from start to end.

You then use that index to do whatever, such as get the value in the array at that index.

You can bind that to a variable name.

for i in range(10):
  my_value = my_array[i]

Or just keep referring to the value with my_array[i], you don't have to give it a new variable.

[fiery cosmos]

i just dont see how it could look back left given the 0th element, i feel like once its been through the outer loop once, then the 0th element is now the second element in the array

[opal oriole]

Well if j is 3, then i could be 0

[fiery cosmos]

like what is zero now becomes the new 0th element

[opal oriole]

I meant to the left of j.

[fiery cosmos]

right. it could never look back left of j unless i said "go to pointsarray[0]". im not saying that, im saying go to the next element up in some range and look there

[opal oriole]

So say you have: ```py
for i in range(0, ...):
for j in range(0, ...):

Draw an array with a couple of numbers in it (like 4).

Let your right pointer finger be i and your left pointer finger be j.

Place both fingers below the first element of the array.

Now follow what the code does by moving your fingers.

Step by step.

What does step 3 look like?

[opal oriole]

Yes, but I recommend trying this step by step on paper.

For a small array.

This is why an animation is best to show this.

[fiery cosmos]

i did it on paper and i also wrote this code to test and see when it does 1,2 and then 2,1

A = [1,2,3,4,5]
for i in range(0,4):
        for j in range(0,4):
                left = A[i]
                right = A[j]
                print(left,right)

so yes, you are correct

[opal oriole]

So you can see how if you let j start at 0 it can be to "the left" of i?

(j < i)

[fiery cosmos]

correct. i was getting mixed up in assuming that bc of the nested nature of the loop, the inner loops new 0 would be j=1 or j=2, which is not the case.

[opal oriole]

Yeah, nothing implicit, i and j are just what we set them to, the only automatic thing happening is that each i and j go plus one at the end of their loops before repeating.

i = 0
loop:
  do whatever
  i += 1
  goto loop

(This is why I prefer BASIC for teaching)

[fiery cosmos]

so underneath loop must have some counter that it automatically increments

[opal oriole]

For loops are a construct built out of that common pattern.

[opal oriole]

Yes. For loops are counting using the variable name you gave it (i and j).

(For loops make sense after you keep doing that pattern over and over and want to write it in a less annoying, safer way (higher level construct / abstraction))

[fiery cosmos]

i mean i can write a loop counter if i want and += to increment it but whoever wrote python must be handling that on the back end

which is why i don't have to increment it

[opal oriole]

Yes, but also because Python wants you to program in a way that is structured, gotos and such allow things to potentially become a mess.

[fiery cosmos]

what IDE do you use?

[opal oriole]

But down under, it's basically doing that.

[fiery cosmos]

or recommend. i can't stand IDLE anymore

[agile sundial]

mu, thonny, pycharm, vscode

[opal oriole]

I can't recommend any IDEs because I don't use any.

Well, I use Unix.

[fiery cosmos]

ok

[agile sundial]

Unix = no ide? lol what

[opal oriole]

It has a compiler, debugger, text editor, and it's integrated. It's what it was originally made to be.

(Also defining an IDE is hand-wavy)

[fiery cosmos]

alright i need to eat.. thanks all

[opal oriole]

These options are def. better than IDLE though, regardless if "IDE" or not.

[hollow peak]

hey whats a good place to learn about algorithms and databases?

[agile sundial]

algorithms and...databases?

[lament totem]

data structures?

[agile sundial]

i don't actually know any good database resources 🤔

but mit opencourseware has good algorithms resources

[lament totem]

You can try some challenges on code sites like codewars and hackerrank

That helped me find out how to properly use dicts and lists and trees and stuff

[haughty mountain]

small caveat, if I touch i in a loop like that I would affect the loop, in python I can do whatever to i and it will just be overwritten

[opal oriole]

Yeah, more safety stuff.

[haughty mountain]

your description is closer to the interpretation of a C style for loop

[opal oriole]

Yeah, or well, what it gets compiled to.

[haughty mountain]

yes

[opal oriole]

Goto is more natural for beginners and structured programming comes from common patterns like that one and added safety / forced stuff.

[haughty mountain]

the standard even specifies that it's the same as a particular while loop

[opal oriole]

(Specifically because with goto you see it doing the jump explicitly)

(And increment)

[haughty mountain]

we should get people to play human resource machine, which only has jumps for flow control

makes you think differently of if statements

it's all just jumps

[opal oriole]

Yea, in BASIC you will often see beginners do something like IF THEN GOTO.

And after a while they will see the pattern where they often goto X and then return.

And functions then make sense.

(procedures)

(And GOSUB in later BASICs)

(explicit to implicit (for beginners))

(unstructured to structured, emergent)

[coarse raven]

data am i right

[azure osprey]

Wut no

Goto becomes a problem immediately

Its used in c a lot tho, for error handling

[thick echo]

Goto is a very natural tool for programmers to use.

Similarly, I have a very natural desire to punch some people in the face.

In neither case should I actually use it.

[nimble lance]

hey

    print(myText)
    myText = "1"
    print(myText)```

why cant i change my var here?

[radiant moat]

Hello, i actually have custom dict class but i want to convert original Dict to my custom class, someone have any clue on how i can do this ?
Appreciate your help, ty :b

here is my custom dict clas

class CustomDict(dict):
    __slots__ = ()

    def __init__(self):
        super().__init__()

[plain violet]

Use **kwargs

[radiant moat]

ok ty !

[hollow nebula]

def updatetext():
    global myText
    print(myText)
    myText = "1"
    print(myText)```

böyle yap bacım

[fiery cosmos]

so i have no idea how this is possible but pycharm gets like stuck on one output and i cannot do a different output (for example, i'll comment out a line calling my function with 1 input, and run a line calling the same function on a different input) and it'll output the data associated with the commented out call

how is it possible this is this dysfunctional when IDLE works just fine

[fiery cosmos]

how can i implement this code in python:

[plain violet]

Using range

[half lotus]

for i in range(l, n): x *= i

n + 1 actually

[plain violet]

from math import product

prod(range(l, n + 1))

[agile sundial]

it's prod, 3.9+ iirc

[fiery cosmos]

i just started using vscode and i guess its not configured properly

[agile sundial]

no, math.product doesn't exist

[agile sundial]

do you understand the error?

[fiery cosmos]

yes i never defined l. i cannot set it equal to a variable in a loop header in python, as is shown in the sample code

[agile sundial]

well there ya go

[half lotus]

In the original code you showed, l is also not defined.

Nor is n for that matter

[fiery cosmos]

i guess its pseudocode

[plain violet]

My bad

[half lotus]

There is probably some context that explains what those variables mean

[fiery cosmos]

no this is how the video begins, with this example. never underestimate how little they teach you in online school

"if one of us needed to write a function to calculate the factorial, we'd probably do it exactly like this."

[half lotus]

If it's for a factorial then l = 2 and n is the same as in n!

[fiery cosmos]

what does i++ mean

[half lotus]

It increments the i by 1

same as i = i + 1

[fiery cosmos]

same as pythonic i+=1

[half lotus]

Yes

[fiery cosmos]

so if this is in the loop header, do i put it just inside the loop in python?

[half lotus]

Though it's technically an expression (where as an assignment is a statement), so i++ actually evaluates to something.

[agile sundial]

no, python does loops differently

[half lotus]

But, that's not important in this context

[fiery cosmos]

how would i make a functioning code and pass it an input? this is what i have so far

x = 1
i = l
for i <= n:
    i+=1
    x=x*i

[plain violet]

Like this

[plain violet]

If you have condition for loop, then you would like to use while

[fiery cosmos]

ooh

[half lotus]

Python for loops don't have the same structure. There is no initialisation, condition, and advancement sections. Python is more like a "for each" loop I suppose.

[plain violet]

while condition:
    ...  # Doing something there.

You can put i <= n as condition

[half lotus]

You're still using a for

[fiery cosmos]

wait that should say while

these IDEs, they never save your changes

IDLE is superior!

back to name 'l' is not defined

[plain violet]

IDEs have auto-save option

[plain violet]

Define it before the loop

[fiery cosmos]

i tried saving manually in pycharm and it says that project already exists 😂

i mean i said i=l do i need to declare l and set it equal to zero?

[plain violet]

Just set your i to zero

[half lotus]

i = l defines i, not l. It's saying "take the value of l and give it to i". But of course l is not defined, so it fails.

For a factorial, i should start at 2

It could start at 1 but that's just redundant (since x * 1 = x)

[fiery cosmos]

where do we define n, how do we increment l toward n

[cinder kayak]

how would I code a combination generator in python that would give me every single combination for the letters i input? but then have certain characters like "-" that would make those characters inseparable. so the input could be something like ab-ce-r43 and the output could only rearrange the order without switching the characters that are together. so the output would be like r43-ab-ce?

[half lotus]

For a factorial, n is just the same as in n!. So if you want to calculate 5!, then n = 5

[half lotus]

Since you care about order, what you're after are permutations, not combinations. I think what you need is ```py
import itertools

s = "ab-ce-r43"
split = s.split("-")

permutations = ["-".join(p) for p in itertools.permutations(split)]

[cinder kayak]

thanks

how would i remove the dashes from ['ab-ce-r43'] so when i printed it out it would display ['abcer43']?

[fiery cosmos]

i'm guessing strip() but that may only work for the ends of strings..

[cinder kayak]

.strip dosn't work for strings inside lists

[half lotus]

Generally, like this 'ab-ce-r43'.replace('-', ''). In your case, you can change "-".join(p) to "".join(p)

[agile sundial]

why are you joining them with "-" if you don't want "-"

[vocal verge]

@cinder kayak Change those bitly links in your pasted code. They got zapped by the filter.

[cinder kayak]

ok

import requests
import itertools

string = "Lo-on-fy-93-z0-y."
split = string.split("-")

permutations = ["".join(p) for p in itertools.permutations(split)]
added = ["bitly link here" + letters for letters in permutations]


url = added

response = requests.get(url)
for urls in url:
    if response.status_code == 200:
        print(f"{url} is valid.")
    else:
        print(f"{url} does not work.")

i want to check the list and see which urls give status 200 but im getting errors. any help would be great

[fiery cosmos]

what is the input into a binary search algorithm? what data structure

i know it has to be a sorted array of some sort.. so just a pythonic array?

[agile sundial]

a list, in python

[fiery cosmos]

right i figured that out. i made a listed and sorted it as the test case

what does := mean in java

variable assignment?

[agile sundial]

it's an error in java

[fiery cosmos]

oh

idk what they're saying in their pseudocode then

[agile sundial]

it's common to use that as assignment in pesudocode

[fiery cosmos]

oh ok

hmm i feel like in this pseudocode they are assigning the function equal to something but i instead should be calling it on that something?

what happens when you set a function = something

[agile sundial]

i would guess it's the same as setting any other variable

[fiery cosmos]

so variables like x=7 make sense, but T()=7 not so much

i guess i can test it

[agile sundial]

is this python code you're looking at?

[fiery cosmos]

the pseudocode was written i believe for java and im trying to implement in python

seems like they mean pass that number to the function as an argument, not assign the function = that number

[agile sundial]

can you send it

it's probably not assignment, and they're using = for equality

[agile sundial]

yes, that's assignment

[fiery cosmos]

so i understand passing an argument to a function, how is that different than assigning a function equal to some value

[agile sundial]

why is that a function? it seems just like a normal variable

[half lotus]

That's the variable used to store the result of the search

[fiery cosmos]

its an example of recursion, so i know im going to have to use the function im defining and call it within itself

ok

lol

ok where did i go wrong:

a = [23,27,36,29,42,55,56,41,10,1,8,1209,142,175,283,296]
a=sorted(a)

def binarysearch(searchterm):

    low = min(a)
    high = max(a)
       
    if low > high:
        searchterm = 0

    else:

        mid = (low+high)%2
    
        if searchterm == a[mid]:
            return searchterm 
        else:
            binarysearch(searchterm)

            if searchterm < a[mid]:
                    mid = (low+(mid-1))%2

            if searchterm == mid:
                return searchterm
            else:
                binarysearch(searchterm)

                if searchterm > mid:
                    mid = ((mid+1)+high)%2
                    if termterm == mid:
                        return searchterm
                    else:
                        binarysearch(searchterm)

    

binarysearch(10)

[agile sundial]

low = min(a) and high = max(a) don't make sense

these are supposed to be indexes, not values in the array

[cloud plover]

mina

[fiery cosmos]

🤔

[half lotus]

Besides the low/high, you forgot to return the value of the recursive call.

But having a quick glance at this, it seems much more complicated than it needs to be

[fiery cosmos]

well im going off of pseudocode so

[agile sundial]

the point of binary search is not to find the element, but the index of that element, so return searchterm doesn't make sense

can you show the pseudocode?

[half lotus]

I think it's the screenshot above of the handwritten code

[fiery cosmos]

correct

[agile sundial]

😬

well, it says low := lowest array index, not minimum value of array

[fiery cosmos]

working on that

[half lotus]

In your comparisons, you should be comparing the value at mid i.e. a[mid] rather than the index itself

[fiery cosmos]

how do i return the index given a value in an array

indexOf()

a = [23,27,36,29,42,55,56,41,10,1,8,1209,142,175,283,296]
a=sorted(a)

def binarysearch(searchterm):

    low = 0
    high = len(a)

    if low > high:
        searchterm = 0

    else:

        mid = (low+high)%2
    
        if searchterm == a[mid]:
            return a.index(searchterm) 
        else:
            binarysearch(searchterm)

            if searchterm < a[mid]:
                    mid = (low+(mid-1))%2

            if searchterm == a[mid]:
                return a.index(searchterm) 
            else:
                binarysearch(searchterm)

                if searchterm > mid:
                    mid = ((mid+1)+high)%2
                    if searchterm == mid:
                        return a.index(searchterm) 
                    else:
                        binarysearch(searchterm)

    return binarysearch(searchterm)

binarysearch(10)

how about this

[half lotus]

Using .index() defeats the purpose of a binary search, since .index() is a linear search

[fiery cosmos]

oh boy

[half lotus]

While binary search is O(logn) and is meant to take advantage of the fact that the data is sorted

Like, if you don't care about doing a binary search, your entire function could just be one line return a.index(searchterm)

[fiery cosmos]

right

[half lotus]

Maybe this will guide you more in the right direction.

if searchterm == a[mid]:
  # The value at the current position matches the search term.
  # Return the position.
  return mid
elif searchterm < a[mid]:
  # Search the left half.
  return binarysearch(...)
else:
  # Search the right half
  return binarysearch(...)

You need to modify the signature of your function so it takes the start and end indices as parameters.

Because when you go left or right, these indices must change

[fiery cosmos]

ok thanks i'll work with this

although @agile sundial said that the purpose was to return the index, not the search term

[agile sundial]

yes, mark's advice is consistent with that

[fiery cosmos]

yeah no i don't get it, maybe i'll try again tomorrow

[half lotus]

mid is the index a[mid] is the value

[fiery cosmos]

right

i don't understand what should go in the return binarysearch(...)

[agile sundial]

do you understand what binary search does?

the main idea behind it?

[fiery cosmos]

yes the main idea is to check the middle of a sorted array against a search term, and return the location of the term if the search term happens to be there at the center of the array. if not, and the search term is lower than the value in the middle, then only the lower half of the array is considered, and the lowest and highest values are added, and a new center or middle value is considered against the search term. if the search term is instead higher than the value at the middle of the sorted array, only the upper half of the array is considered. implementing it recursively would allow one to get closer and closer to the search value in a manner that is faster than interative search

[agile sundial]

well, you can implement binary search iteratively, but that's a nitpick

the important part is

then only the lower half of the array is considered
and
only the upper half of the array is considered.

[fiery cosmos]

do i have to change my low and high values as i proceed?

[half lotus]

Yes, because they determine the range in which you search.

[fiery cosmos]

hm i dont think they captured that in the pseudocode

[agile sundial]

your binary search function should probably take low and high as parameters, or you need to pass the list into the function

[half lotus]

I think it does. It says "search for x between a[low] and a[mid - 1]"

[agile sundial]

they kinda did, they said "search for x " ^

[fiery cosmos]

right they dont change the value of low, only of mid

[half lotus]

Well, when they do the recursive call, the high becomes mid - 1

Remember, the function should take low and high as arguments.

[haughty mountain]

right, the recursive call has different low and high

[fiery cosmos]

how can you create a low and high for a new input you're just feeing the algorithm for the first time

that would require a priori knowledge of the array?

[haughty mountain]

I mean, you know the array length

[half lotus]

The low and high determine the range you look in. So you start by looking at the entire array, and from there narrow down your search space.

[haughty mountain]

if the value exists, it has the value at an index such that 0 <= index < len(arr)

so you know bounds on low and high

[fiery cosmos]

no i meant when you call the search algorithm for the first time. you'd have to compute the length first and then add that as an argument?

like binarysearch(inputarray, 0, lengthofarray)

[haughty mountain]

yes

[fiery cosmos]

how was none of this captured in the pseudocode 😭

[haughty mountain]

low=0 and high=len(arr) are sensible initial values

[half lotus]

The first two lines say the low and high must be the lowest and highest indices in the array

(initially)

[fiery cosmos]

there is a difference between computing the length of an array within a function after calling and passing the array to the function and inputting the length of the array as an argument along with the array

[haughty mountain]

the pseudocode isn't phrased in terms of a nice recursion, annoyingly

[fiery cosmos]

unless you can do like function(arrayA,len(arrayA))

which i dont believe you can do

[half lotus]

I guess they take it for granted that you can assume the length of the array is known or can easily be obtained in constant time.

[fiery cosmos]

i couldnt believe how fast my factorial computation ran

i input 500 and it was done like instantly and made some extraordinarily huge number

[half lotus]

The signature should be something like def binarysearch(array, searchterm, low, high) and the initial call would be binarysearch(array, ..., 0, len(array) - 1)

[fiery cosmos]

i didn't know you could do len(array) in the function call, ok

wait

i knew that, i didn't think you could make it in the definition

[haughty mountain]

why wouldn't you be able to do that?

you can't do it in the definition

[fiery cosmos]

right thats what i thought ok

[half lotus]

Correct, you cannot reference other params in the definition. But in this case you don't need to do it in the definition

[haughty mountain]

I would vouch for using inclusive low and exclusive high, but that's just my preference

and there is a nice general formulation of binary search that just takes low, high and a function pred

(tl;dr: maintain f(low) == True and f(high) == False during the binary search, when high - low == 1 you have found the transition point from True to False)

[fiery cosmos]

ok where should i go from here:

def binarysearch(array,searchterm,low,high):

    mid = (low+high)%2
    
    if searchterm == mid:
        return mid

    elif searchterm < mid:
        mid = (low+(mid-1))%2
        if searchterm == mid:
            return mid
        
    else:
        mid = (mid+high)%2
        if searchterm == mid:
            return mid

[haughty mountain]

%2 is wrong

it should be //2

[fiery cosmos]

huh they used modulo in the pseudocode

[haughty mountain]

idk why the notes use the % symbol

[fiery cosmos]

ok

[haughty mountain]

the point is to have the midpoint

[fiery cosmos]

right

[haughty mountain]

(low + high)//2 does that

[fiery cosmos]

where do i put my recursive call

[haughty mountain]

maybe they mean this division symbol ÷

(which I hate)

[haughty mountain]

idk what you're doing in the elif and else branches currently

[fiery cosmos]

ok. nvm lets try again tomorrow

[haughty mountain]

also, why are you comparing searchterm to mid?

mid is an index

sesrchterm is an element you're looking for

[fiery cosmos]

looks like this now:

    if searchterm == array[mid]:
        return mid

    elif searchterm <= array[mid]:
        mid = (low+(mid-1))//2
        if searchterm == mid:
            return mid
        
    else:
        mid = (mid+high)//2
        if searchterm == array[mid]:
            return mid

i really do have to go though

[half lotus]

The code inside the conditions should just half a recursive call to the function, like how I showed here #algos-and-data-structs message

[lean junco]

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

i know its easy for O(n^2)

but is it really "easy" for dynamic programming

i keep getting hard time in writing a solution using dp

[haughty mountain]

it is, it's hardly even dynamic programming

keep track of the minimum to the left of you and find the biggest difference to the current element

mini = A[0]  # Just initialize to something valid
max_diff = 0
for a in A:
  max_diff = max(max_diff, a - mini)
  mini = min(mini, a)
# max_diff is the result

so yeah, hardly dp, just two numbers to keep track of, though of course you could formulate it as a full-on dp if you want to

minimum so far and maximum difference to minimum would be the two things to track in the dp, just like the two variables in my code

[lean junco]

i am loosing my mind, trying to do dp question..the loop doesnt comes up to my mind

i am trying to see patter in dp but i get lost easily

[dusk anchor]

Hi there, I dont really know if this should go here, I just want to know if there is a way to check if the items of a list are instances of a certain class, and if not return a tuple of True/False depending if the list items were instances of the given class and also the item that wasn't.
For example for list [True, False, True , 2, "abc"]
It should return (False, (2, "abc"))
I have this code but as you can see it is far away from what I want.

check_validity = lambda data, dtype: all(isinstance(i, dtype) for i in data)
check_validity(data, bool)

(I want to do this as optimized as possible thats why if there is a solution with lambda's I prefer it ;)

[dusk anchor]

Actually, I only need it to return the items that were not an instance of a class. Its very simple to do it, I just cant figure out a way to compress that function into a lambda.

[merry nova]

Lambdas aren't there for optimization

[dusk anchor]

srry my fault i meant less code

[merry nova]

It doesn't make it any faster or slower than regulardefs

[dusk anchor]

srry

[tacit nova]

if get min from minheap is O(logn)
then if we do it n times
then that's O(n*logn) right ?

[dusk anchor]

welp idk forgot what i was typing tbh

[merry nova]

The first issue is the all since it only returns a bool of the result

[nimble lance]

teşekkür ederim 🙂

[dusk anchor]

Yes i think thats correct

[dusk anchor]

That works

invalid = [i for i in data if not isinstance(i, dtype)]

[dusk anchor]

yeah

[merry nova]

Probably something like

check_validity = lambda x: [(i, type(item)) for i, item in enumerate(x[0]) if not isinstance(item, x[1]) else True]

And you'd call that with the tuple of list and type to check

[dusk anchor]

yeah.

Thanks :)

[tacit nova]

for i in [1,2,3]
for i in set((1,2,3))

even though set is O(1) and list is O(n), but the 2 lines above will have same O(n) right ?

[vocal gorge]

yes, but making a set is O(n) just like making a list, you're thinking about in checks

[fiery cosmos]

looks good to me

[fiery cosmos]

bruh

[haughty mountain]

ignoring that you have <= when you mean <, but:

how does your knowledge of low and high change after you learn that searchterm < array[mid]?

(similarly for searchterm > array[mid], the else case)

[fiery cosmos]

i should be working on that, but im reading about discrete random variables 🙄

there is way too much theory in this course. i should be practicing coding and learning runtime analysis

[fiery cosmos]

what does it mean mathematically when you have two variables one over another in parenthesis but its not division

like this:

[supple obsidian]

matrix

used usually with vectors

[fiery cosmos]

its in the context of probability theory

and bernoulli trials

[vocal gorge]

binomial coefficient

[grand haven]

Failed to render input.

View Logs

[vocal gorge]

.latex $\binom{n}{k}$

[haughty mountain]

"n choose k"

the number of ways to pick k elements out of n

which is n!/(k! (n-k)!)

[edgy folio]

!e

[halcyon plank]

Missing required argument

code

Command Help

!eval <code>
Can also use: e

*Run Python code and get the results.

This command supports multiple lines of code, including code wrapped inside a formatted code block. Code can be re-evaluated by editing the original message within 10 seconds and clicking the reaction that subsequently appears.

We've done our best to make this sandboxed, but do let us know if you manage to find an issue with it!*

[edgy folio]

!e
dir(None)

[halcyon plank]

@edgy folio :warning: Your eval job has completed with return code 0.

[No output]

[edgy folio]

ok.

er isn't None an object tho?

[half lotus]

This eval command does not work like a REPL. You have to do print(dir(None)). Anyway, if you want to try out the command do it in #bot-commands please.

[edgy folio]

oh. Ok,thanks for cluing me in

[primal geode]

Hey everyone, I need some help with the N queens problem

How could I add more solutions, so it prints more than one solutions?

[worldly jolt]

id need to see your code to tell you that, but you can try looking for a solution given a starting position for the first queen. and only check positions where you have not seen a queen yet (in any solution you have already printed)

[fiery cosmos]

on implementing binary search, must you keep track of each new subarray by declaring a new subarray and copying the values over? i don't think you have to

i feel like you may to do it recursively otherwise when you call binarysearch again you're looking at the same original input array

[half lotus]

No, the same array can be re-used. It's just a matter of changing the start and end indices for the search

[fiery cosmos]

ok ty

[half lotus]

You could create a new array, but that's not efficient

[fiery cosmos]

my new binary search algo is coming along im about to post it. i worked it on a whiteboard first. i think if it doesn't work it'll only require some minor tweaks

getting RecursionError 😂

i think i need an optional input parameter

so that when i call it recursively i can just tell it to run again? i guess you could always change the search parameter to be the middle of the new subarray

does vscode have block commenting out? like highlight a whole block of code and comment it all out?

Select the block and Ctrl+/

wow thanks very helpful

in my binary search function, i'm writing it such that i can input my search term when calling the function. so i pass the function my input array and an integer im searching for. but as such, when i call it recursively, i am missing that required positional argument. i could call it the same way as where it is defined, but then i get a Recursion error

not sure if that is the issue

[half lotus]

It should be like this #algos-and-data-structs message

And every time you call it you'd pass all those arguments.

The array and searchterm shouldn't change though

[fiery cosmos]

hmm

do i have to structure it in that way?

i suppose i do

[half lotus]

If you're doing it recursively then I can't think of how else you'd do it unless you used global variables, or you sliced to create a new array instead of changing the indices.

[agile sundial]

you could definitely do

def binsearch(arr, x, lo=None, hi=None):
  if lo is None:
    ...
  ...

[opal oriole]

def binarysearch(array, value):
  return _binarysearch(array, value, 0, len(array) - 1)
def _binarysearch(array, value, low, high):
  ...

Proxy function.

(underscore indicating private)

[fiery cosmos]

noww y'all tell me

[opal oriole]

This is common pattern for recursive functions in general that need some start values for the arguments. And you want it to be hidden / more nice to use for the end user.

[fiery cosmos]

alright so my algorithm is working for elements in the middle and those which are left of the midpoint, so i just need to get it working for elements in the right half of the input array

which i currently have defaulted to an else statement, which makes me think i need a > check somewhere

[half lotus]

If you check = and < already, then the only remaining possibility is > for the else.

You could explicitly write out the condition but it's not necessary

[fiery cosmos]

but its // division so could there be an in between case in the event of odd numbers?

[half lotus]

You should be comparing the same value i.e. a[mid] == searchterm or a[mid] < searchterm. Thus the only possibility remaining is >.

[fiery cosmos]

right

[half lotus]

As shown here #algos-and-data-structs message

[fiery cosmos]

dang i just don't know why its working for left half of the array and not the right..

[half lotus]

Does your code follow the structure in that example?

If your if/else statements have more than one line each then you're probably overcomplicating it.

[fiery cosmos]

for the most part. i have a nested if/else within the first elif

[half lotus]

Like, ```py
elif searchterm < a[mid]:
return binarysearch(...)

is all you need to do for that case. Just change `...` to be the right arguments.

You should not need any nested if/elses

[fiery cosmos]

and within the else statement

yo hello guys

[half lotus]

The recursive call will take care of the subsequent comparisons

[fiery cosmos]

will its like if searchterm == midpoint:
return midpoint

import math, pyblake2

# The global seed is the hash of the Bitcoin block published by Rollbit
global_seed = bytes.fromhex("00000000000000000004ab6468e03c35500b5f59b8ef58ef9873f67ffbf12bcd")

# In this example, we'll start with the 369,862nd game round and work backwards.
round = 369862

# The round_hash is initially set to the value published for the 369,862nd round.
round_hash = bytes.fromhex("344893385fa113a48edafe61cc0e52a11fba9c1cd2dc4a92f7e919be87945ec5")

for i in range (round, round - 10, -1):
    # For every round, we append the global_seed to the round_hash to get a final has value.
    round_final_hash = pyblake2.blake2b(round_hash + global_seed, digest_size=32).digest()

    # We then convert that hex value to a floating point number 'x', which is uniformly distributed in the unit interval
    x = float(int.from_bytes(round_final_hash[:8], byteorder='little', signed=False)) / float(2**64 - 1)

    # The round's outcome is calculated by applying the house's 5% edge, rounding to 0.01 precision, and restricting the outcome range to [1.0, 1000000.0)
    outcome = min(1e6, max(1.0, math.floor(100.0*(1.0-0.05)/x) / 100.0))
    print("Round: ", i)
    print("Round Hash: ", round_hash.hex())
    print("Round Outcome: ", outcome)

    # For the next round, we calculate the next value in the chain of hashes.
    round_hash = pyblake2.blake2b(round_hash, digest_size=32).digest()
    ```

anyone know how to create a algo

to be able to see the history?

[primal geode]

Thanks!

[steel imp]

hi everyone,
i'm working on an elevator coding challenge in python, but i'm not sure where to start. i understand bits of the directions, but still struggling.

Write a command line program that takes a command-line like the following:

Elevator `<path to state file> <starting elevator> <final destination>`

The <final destination> argument is specified as <floor>-<time>. So, 3-2 indicates that the final destination is the 3rd floor at time t=2.

At t=1, you begin in the elevator specified by <starting elevator>, e.g. "A"

Can move between elevators so long as they are on the same floor.

If there is a solution, only print solution string to stdout.

If there is no solution, only print to stderr.```

let's say the first example looks like this:
xx.x.x.x.xxx
xx.x.x.x.xxx
xx.x.x.x.xxx
xx.xBx.x.xxx
xx.x.xCx.xxx
xxAx.x.xDxxx

the . are elevator shafts and the letter are the elevators

[astral walrus]

Does anyone have any good resources to start studying algorithms?

[worldly jolt]

I might not be understanding the problem correctly but assuming you know what floor the starting elevator is and moving one floor takes 1 time unit then moving between elevators is pointless and the answer is basically "return (math.abs(currentFloor - detinationFloor) <= time)"

[steel imp]

Hi, yes you know the starting floor and i believe moving one floor takes 1 time.

here's the full directions, might make it clearer:

`
xx.x.x.x.xxx
xx.x.x.x.xxx
xx.x.x.x.xxx
xx.xBx.x.xxx
xx.x.xCx.xxx
xxAx.x.xDxxx
`

In this example, dots represent an elevator shaft, and letters (specifically A-Z) represent 
an elevator. So in the above diagram, there are four elevator shafts, elevator A is on the 
first floor (1-indexed), and there are six floors.

An elevator state file contains a series of elevator state diagrams separated by empty lines,
where each successive state diagram represents a point in time from t = {1, 2, 3...}

Goal: Write a command line program that takes a command-line like the following:

Elevator `<path to state file> <starting elevator> <final destination>`

The `<final destination>` argument is specified as `<floor>-<time>`. So, 3-2 indicates that the 
final destination is the 3rd floor at time t=2.

At t=1, you begin in the elevator specified by `<starting elevator>`, e.g. "A"

In any given time period, you can board a different elevator or stay on the elevator you 
are currently on, but you can only board an elevator on the same floor as the elevator that you 
are currently on (including t=1).

The goal is to find a series of legal actions that lead to you being at the final destination
(the right floor at the right time).

The set of actions should be written to stdout as a series of actions in a single string. 
An action is defined as the elevator you board (or stay on) at time t. For example, "AABDD"
indicates that you were on (or switched to) A at t=1, stayed on A at t=2, switched to B at
t=3, and switched to D at t=4, and stayed on D at t=5.

If there is a solution, the solution string is the *only* thing that should be printed to stdout.

If there is no solution, print something appropriate to stderr, and do not print ANYTHING to stdout.```

[fiery cosmos]

there are a lot of good courses on EdX, you'd have to look for an algorithms specific one, outside of that most people opt for MIT's opencourseware content

i'm learning from the classic CLRS text right now, which i do not recommend

i'll link the mit opencourseware class in a moment

https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/video_galleries/lecture-videos/

[fiery cosmos]

actually looking at the MIT course it seems like it'd be great material for me

[fiery cosmos]

oh MIT:
"This is quadratic in n, which is polynomial! Is this efficient? No!"

😂

hmm why are they going to the trouble of implementing an array in python when list is a dynamic array?

something to do with a sequence

"Then how does Python support appending to the end of a length n Python List in worst-case O(1)
time? The answer is simple: it doesn’t"

[agile sundial]

to learn

implementing a data structure ensures you understand it

[fiery cosmos]

yeah i'm just now learning about amortization

python was written in C 😱 😱 😱

Hey! I am trying to learn dsa but don't understand the math needed to learn dsa. Are there any courses or videos that will help?

dsa?

[agile sundial]

data structures and algorithms

[fiery cosmos]

see 6006 MIT course in pinned messages

of course, the prereqs for that are these:

and the prereq for that prereq 6042 is:

sooo as a beginner you really have to go back to the drawing board

[fiery cosmos]

TYSMM

[fiery cosmos]

see prereqs above

[astral walrus]

Awesome thanks ill check it out

[fiery cosmos]

can someone walk me through this?

been trying to work it out on paper and failing hard

[agile sundial]

which part?

the solution there tells you all the rules you need to use

[fiery cosmos]

i just don't see how to use those rules to get that solution. probably bc algebra

i got a schaums outline on algebra im reading at night but not all caught up yet

[agile sundial]

start working from the inside out, log(n^sqrt(n)), what rules can you use?

[fiery cosmos]

that can be changed to sqrt(n)*log(n)

i actually was starting a different way, by pulling the 2 out front. is that wrong? or just different

[tribal sparrow]

what does it mean to Relax all edges |V| - 1 times. when it comes to bellman and ford algorithm?

[agile sundial]

that way is probably better, now that i think about it, but it doesn't really matter, you get the same result

[haughty mountain]

I guess as hints, the 1/log(6006) comes from rule 3, the 2 comes from rule 2, sqrt(n) moving out is also rule 2

[haughty mountain]

you can do the relevant steps in any order

[agile sundial]

can you show your work?

[haughty mountain]

line 1 to line 2 is applying rule 1

[agile sundial]

line 1 is wrong, it's not 2 log_6006 * log(n^sqrt(n)), it's 2 log_6006(log(n^sqrt(n))), although this is kind of a notation nitpick

[fiery cosmos]

wait wait

hang on

[haughty mountain]

importantly in your first two lines you have log_6006(...), but you've written it as multiplication

[fiery cosmos]

that was the first time

[haughty mountain]

don't use the product rule yet

[fiery cosmos]

i had some other rules i was looking at

i want to start fresh, whats step 1?

[haughty mountain]

rewrite the log base 6006

[fiery cosmos]

for step 1?

[haughty mountain]

these are the 3 steps to do for the first equation

[haughty mountain]

this is to get to the second line

hopefully that's enough of an outline

[fiery cosmos]

wait a minute

in these rewrites, does the base stay the same???

like log_a(b) = log_?(b)/log_?(a)?

there is nothing about logarithms in my schaum's outline 😭

[haughty mountain]

log_a(b) = log_c(b)/log_c(a)

you can use this to change the log base

[fiery cosmos]

what does it change to?

like whatever you want as long as they are the same?

[half lotus]

Yes

[fiery cosmos]

ok i'll try solving in the manner someone else showed where they used ln_e

[half lotus]

You don't have to be explicit about the base. If you leave it out it implies they're the same. And ln is commonly understood to have base e anyway.

[fiery cosmos]

right makes sense. im coming from chem where the log was generally base 10

but in CS it is generally 2

it only matters if you actually need to use the base to calculate something, i agree

Right so far?

[half lotus]

No. The 2 should be on the outside, next to log_6006. What you did is effectively state a^2 == 2a which is of course not true.

[fiery cosmos]

dang!! ok. i'll start again

you mean the entire expression will then begin with 2?

eg 2*log_6006...

[half lotus]

Right. log_6006(a^2) == 2 * log_6006(a)

[fiery cosmos]

👍 ❓

[agile sundial]

that looks right

[half lotus]

I agree

[fiery cosmos]

so now is when i do my transformation to get rid of the base..?

[half lotus]

Yes

[fiery cosmos]

ok lms

hmm their answer looks a bit different at this step

is mine equivalent? why did they put the 2 as the num in its own part

[half lotus]

Yes it's equivalent

Basically this a/b == 1/b * a

They wrote it that way because the fraction on the left is a constant

[fiery cosmos]

ok so i can leave mine in this form and convert sqrt(n) to n^1/2

[haughty mountain]

it's all stuff multiplied together, you can reorder as you wish

[fiery cosmos]

hmm i need to just figure out how to get from my expression to theirs and then apply a theta bounding

it looks like they broke out log(sqrt(n)*log(n)) into log(n^1/2)+log(log(n))

ohh

they treat the 2/log(6006) as a constant that can be ignored?

i'm referring to what was done here:

[agile sundial]

yes, remember constants are irrelevant in big theta notation

[fiery cosmos]

https://tenor.com/view/elmer-sheep-thumbs-up-like-approved-gif-10765417

i don't see how i'd get to my expressions and know to put the 2/log(6006) out front so that i'm able to effectively ignore it for purposes of asymptotic bounding, but i hope to get there 🙂

i'm just glad i sort of see how to do this as i've spent much too much time on it today.. i guess that's how you learn

theres no way this is a legitimate manipulation right?

[half lotus]

It is

It's just (2a)/b = 2/b * a

[fiery cosmos]

i cannot simply take that term(log n sqrt one) and put it over 1, as it was over log(6006) before

ok tysm

[half lotus]

But it's not like you got rid of the multiplication.

It's just a different way to write the same thing

[fiery cosmos]

really??? i just don't understand how you can simply ignore its original denominator and instead put it over 1

[half lotus]

You're not ignoring it

[fiery cosmos]

im referring to the expression log(sqrt(n)...)

[half lotus]

a/b = 1/b * a/1 If you multiply those you'll get a/b again. Is that what you are talking about?

[fiery cosmos]

oh you're not because you are going to multiply across?

yeah i guess i see it now..

[opal oriole]

3/4 = 3 * 1/4

"three quarters"

[fiery cosmos]

ok thanks. i promise im not as dumb as i make myself appear here

[oblique haven]

https://leetcode.com/problems/maximum-depth-of-binary-tree/

found big brain solution
print(len(bin(len(root)))-2)

[fiery cosmos]

does that work?

[obtuse grail]

super basic question..thinking about ways to recreate a cluster of colored cells in addition to text in excel. Was thinking a numpy array for the color cluster. Does that sound like the most efficient way to approach it? Vs. using built-in methods of an excel lib?

[fiery cosmos]

hey all

trying to do this basic programming challenge, its semi working but i know i'll need another loop to look at every number

its supposed to find all pairs of numbers that add to the target number, regardless of where they are in the array

nums = [8,7,2,5,3,1]
target = 10

def sumfinder(array,searchterm):
    key = array[0]
    for num in array:
        if num+key==10:
            return print("pair found: (" + str(num) + ', ' + str(key) + ")")


sumfinder(nums,target)

can't figure out how to increment key

im going to need indices

ooh i got it to find the 3,7 but now the 8,2 doesn't work

im thinking i need to learn how to use break and pass and continue

[half lotus]

What's the approach you're trying to use?

There's a brute force approach, and then there's an approach that relies on sorting the array.

Also an approach that uses a dictionary.

[fiery cosmos]

i guess it would be brute force. but its obvious i need more to my code to do it that way

[half lotus]

Do you understand what the brute force approach should be?

[fiery cosmos]

i didn't look at the example code but yes in essence you should be able to check every number against every other and return a print if their sum are equivalent to the target number

sry every number against the target number

[half lotus]

Right. Try to focus on that first: a way to get every pair possible.

[fiery cosmos]

matrix? then make tuples? overcomplicating?

[half lotus]

If you were to store them, it would just be a list off tuples.

But ultimately you don't need to store them. You can check each pair on the fly.

[fiery cosmos]

ok

i know i'll need two loops

[fiery cosmos]

every time i try to increment a loop counter variable to check an array i end up getting out of range error

ok i did it. but unfortunately i had to look at the sample code for the first few lines 😦

[haughty mountain]

I like to think of it as three factors, a, b and 1/c (I'll use letters to not retype your expressions)

you can freely re-order and combine those terms to get other equivalent expressions, e.g.

a * b * 1/c
a * b/c
b * a/c
a/c * b   (not to be confused with a/(c * b)

[fiery cosmos]

ok thanks

[haughty mountain]

tl;dr: multiplication is commutative

and associative

a * b = b * a

(a * b) * c = a * (b * c)

[agile sundial]

hmm, transitive is the wrong word there, i think that's associative?

[fiery cosmos]

well now i'm doing inductive proofs via matrix multiplication

so thats been.. fun

[haughty mountain]

ack, fixed

[haughty mountain]

yeah, with matrices you lose commutativity

[fiery cosmos]

can you walk me through how to convert the expression on the left to its n+1 expression?

did she just multiply that entire top line by (n+1)?

let me try it

[haughty mountain]

huh? no

[fiery cosmos]

or you plug in n+1 for all n?

[haughty mountain]

add (n+1)² to the left one and mess around with the expression a bit

[fiery cosmos]

why (n+1)^2?

[haughty mountain]

because that's the next term

see the sum limits

[fiery cosmos]

you square it bc of the k^2?

[haughty mountain]

sum(i=1, n, k²) + (n+1)² = sum(i=1, n+1, k²)

which is the new left hand side

now do the same to the right hand side of the equality and see what you get

[haughty mountain]

you have 1²+2²+...+n² before and 1²+2²+...+n²+(n+1)² after

that's what the sum is a short form for

[fiery cosmos]

but just to be clear that is given by the k^2 expression

[haughty mountain]

well, yes

[fiery cosmos]

ok

[haughty mountain]

the expression in the sum determines what the terms look like

[fiery cosmos]

so i want to add (n+1)^2 to the numerator

[haughty mountain]

not to the numerator

[fiery cosmos]

just add it to the entire left hand expression

[haughty mountain]

n(n+1)(2n+1)/6 + (n+1)²

[haughty mountain]

add it to both sides of the first equation

[fiery cosmos]

both sides? there is only the right side expression. the left just describes a formula

[haughty mountain]

myself I much prefer starting with the messier looking n-1 case and working towards n case, rather than starting at the neat n case and working towards the n+1 case

but that's a matter of taste

[fiery cosmos]

i should practice that next time yeah

[haughty mountain]

you have an equation

the left hand side and the right hand side are equal

you can manipulate this equation

in this case adding (n+1)² to both sides is a useful thing to do

it adds the next term to the sum, and you get a new expression for the n+1 case sum

[fiery cosmos]

bruh

[haughty mountain]

you had

S(n) = something
S(n) + (n+1)² = something + (n+1)²
S(n+1) = something + (n+1)²

[fiery cosmos]

like this? for the left?:

for lefthand side of first eq

[haughty mountain]

yes

you do the same addition on both sides

[haughty mountain]

err, that thing has a typo also in the notes

that should be i² in the sum I think

not k²

[fiery cosmos]

its been like that throughout:

[haughty mountain]

it's wrong

[fiery cosmos]

ok

good bc that was confusing the f*** out of me

[haughty mountain]

if it's really some other k the sum would just be n*k^2

it should be the sum of the n first square numbers

[fiery cosmos]

so one thing i fundamentally dont understand is adding (n+1)^2 to both sides is adding the same term, which you could then just subtract out and be right back where you started

[haughty mountain]

adding (n+1)² turns the sum up to term n into the sum up to term n+1

which is what you want to get to

[fiery cosmos]

i think to convert between the equations you simply let the left hand side be equal to itself for purpose of induction, and to "get to" the equation on the right you simply write in n+1 on the top of the summation and add (n+1)^2 to the right hand side of the first equation to get the right hand side of the second?

[haughty mountain]

adding (n+1)² is what makes the upper limit of the sum increase

[fiery cosmos]

e.g. the theory is "if it is true that (left hand side equation), it should be true that the n+1th version of the equation is given by (right hand side)"

[haughty mountain]

you want to show that if the n case is true, the n+1 case is also true

[fiery cosmos]

no the basis was shown above

this is the inductive step

[haughty mountain]

exactly

that is the inductive step

if the n case is true, the n+1 case is also true

[fiery cosmos]

so you've described doing it like so??

[haughty mountain]

yes

[fiery cosmos]

ok i'll try..

[haughty mountain]

on the left you can move (n+1)² into the sum

and it becomes a sum up to n+1

[fiery cosmos]

what happens to the exponent?

[haughty mountain]

what exponent?

[fiery cosmos]

its not n+1 its n+1 squared

[haughty mountain]

you know what the sum is short for right?

[fiery cosmos]

the summation of every value in a series

[haughty mountain]

1² + 2² + ... + n²

[fiery cosmos]

so you're saying its already captured in the i^2 value

[haughty mountain]

you are now also including the next term, (n+1)²

hence the upper limit going up by 1

[fiery cosmos]

🤦‍♂️

ok so whats going on w the right

should i expand the (n+1)^2?

[haughty mountain]

I wouldn't

[fiery cosmos]

multiply by 6/6?

[haughty mountain]

yep

now, you have n(n+1)(2n+1) + 6(n+1)² in the numerator

there is a common factor (n+1)

we can factor that out

and get (n+1) * (n(2n+1) + 6(n+1))

[fiery cosmos]

wait

[haughty mountain]

and yeah, this is why I like going n-1 to n

[fiery cosmos]

what do i do

[haughty mountain]

because then you have a cleaner target to work towards

[haughty mountain]

this

[fiery cosmos]

how do i factor it out

[haughty mountain]

if you have a b + a c you can rewrite it as a (b + c)

in this case your a is (n+1)

[fiery cosmos]

im sorry this is so rudimentary but i cannot do it

i don't understand the factoring out rules, let me look them up

[haughty mountain]

it's just how multiplication works

a*(b+c) = a*b + a*c

the distributive law, I guess

[fiery cosmos]

so my 2n+1 doesn't have an n+1 term

2n+1 =/= 2(n+1)

[haughty mountain]

your term n(n+1)(2n+1) has a factor (n+1)

[fiery cosmos]

ok so i just factor that out along with the one from the second term and get (n+1)^2 as the new leading term in the numerator?

[haughty mountain]

you get this

so no, not that

to have a more hands on example of factoring out a common factor

2*3*7 + 6*3² =
3 * (2*7 + 6*3)

now, we have the (n+1) factor we want

[fiery cosmos]

ok ok i see it now

thank you for that

ty ty

[haughty mountain]

we're missing the (n+2)*(2*(n+1) + 1)

[fiery cosmos]

https://tenor.com/view/spongebob-worship-worshipping-now-bowing-gif-12297363

[haughty mountain]

(and this again, is why I prefer to go n-1 to n, this expression is no fun)

tl;dr: the only thing missing is showing that

n(2n+1) + 6(n+1)
```is equal to

(n+2)(2(n+1) + 1)

[fiery cosmos]

there is no n+2 term

[haughty mountain]

a completely legit way is to just expand both and see if they match

[haughty mountain]

another error, nice

that should be (n+1) and not (n+1)²

[fiery cosmos]

are you serious

how am i supposed to learn from this crap

[agile sundial]

time to consider using a different resource lol

[fiery cosmos]

this is literally a prestigious US uni

[agile sundial]

well

[fiery cosmos]

so im working on expanding this

and i first get
((n+1)(2n^2 + n) + 6n + 6) / n

then i could multiply through more and get more exponents?

this is ridiculous to spend all day on one example like this. i quite literally dont have time

[haughty mountain]

wait, how did you get that?

[fiery cosmos]

multiply n through the first term and 6 through the second?

beginning from ((n+1)*n(2n+1)+6(n+1))/6

[haughty mountain]

I don't want you to multiply everything out

[fiery cosmos]

o

then what should i be doing

maybe you want me to work backward from the answer but when i do proofs i wont be given the answer and i'll have to work toward it myself

[steel imp]

does anyone have any ideas for this challenge? i believe this is the right place for it. it seems like a data structure and algos question.

Thanks

[haughty mountain]

the thing we hope to reach is

(n+1)*(n+2)*(2(n+1) + 1)/6
```and we already have

(n+1)*(n(2n+1) + 6(n+1))/6

[fiery cosmos]

that looks way different from her answer

there is no n+2 term

[haughty mountain]

(n+1) + 1

[fiery cosmos]

oh

and you're saying the first (n+1)^2 should just be (n+1)

[haughty mountain]

yeah

the annoying expansion is

n(2n+1) + 6(n+1) =
2*n² + n + 6*n + 1 =
2*n² + 7*n + 1

and

(n+2)*(2*(n+1) + 1) =
(n+2)*(2*n + 3) =
n*(2*n + 3) + 2*(2*n + 3) =
(2*n² + 3n) + (4*n + 6) =
2*n² + 7n + 6

so yeah, the differing part is the same

maybe there is a nicer way of transforming it

you can always expand and then factor it using the quadratic formula, but that's also annoying

[haughty mountain]

this is actually a case where working backwards from the answer is ok

you guessed the formula, so you know what you want to arrive at

[fiery cosmos]

don't you have to multiply the leading (n+1) through (2n^2+n) term??

[haughty mountain]

@fiery cosmos look at these two

both have a (n+1) and both are divided by 6

so those parts are the same

the only question is if the rest matches

[haughty mountain]

"the rest" I expanded here

[fiery cosmos]

i got to a point where i have 2n^3+3n^2+7n+6, maybe there is actually a (n+1)^2 term when you factor it all out

[haughty mountain]

you do not want to factor that

[fiery cosmos]

well i think we got lost in the weeds on this one

[haughty mountain]

tbf, this one is annoying to rewrite

[fiery cosmos]

there is another example, i should work that one instead

[haughty mountain]

I'm guessing the intended path is to factorize the last quadratic using the quadratic formula

[fiery cosmos]

seems more straightforward

[haughty mountain]

it's not hard arithmetic/algebra to do, it's just annoying

[fiery cosmos]

the matrix one was suprisingly easy considering i had to look up how to multiply matrices

@haughty mountain is it late where you are

i'll be back in a bit

then i'll be working this one:

[haughty mountain]

7pm

[fiery cosmos]

sweden yeah?

would you mind giving me a hint for this one?

[fiery cosmos]

oh so you're saying do the "assume its true" part for n-1, that way you only have to prove it for n?

ok now i really have no clue whats going on

[haughty mountain]

this is just moving the last term in the sum out

i.e. if you have the sum

sum(k=0, n, A_k) = A_0 + A_1 + ... + A_n
```you can move out some terms out of the sum, e.g. move the last term out

sum(k=0, n+1, A_k) = sum(k=0, n, A_k) + A_(n+1)

note that the upper limit in the sum went down by 1

[fiery cosmos]

can you tell me what she did here

btw i'm asking about this is math/science help server, haven't gotten response yet

here is the context:

[haughty mountain]

this is just rearranging stuff

and a + 1 - 1 trick

tbh I don't know what their goal is

[fiery cosmos]

the goal is they're doing the inductive step first

and then will do base case later

[haughty mountain]

they haven't really arrived at anything useful? that or I'm blind

[fiery cosmos]

i'll let you know

she's getting there

[haughty mountain]

it's =0 if n=1, sure, but for n>0 they haven't showed the right thing?

[fiery cosmos]

correct

oh. she's just showing that if your inductive proof fails, go back to base cases, and continue evaluating different input variables to see if the claim is indeed true or not. in this case it's just a false statement

not super helpful example

[haughty mountain]

this statement isn't even true? e.g. when n=0 the left side is 0 and the right side is -1, if I'm not being dumb

[fiery cosmos]

right its simply not a true statement

let me try to find another example of an inductive proof to work

i recall doing inductive proofs using summations in the book and it worked fine

[haughty mountain]

right, the correct formula is

2^(n+1) - 1 - (n+1) =
2^(n+1) - n - 2

(which is easy to derive without induction)

ah, they showed the base case n=1 and then the induction step fails

cool

[fiery cosmos]

alright im going to try this one:

[haughty mountain]

they isolate the part they expected from the assumed formula, and show that there is something extra

[haughty mountain]

that's the previous one

[fiery cosmos]

yes but i need to know how to work to a solution

[haughty mountain]

this

[fiery cosmos]

ok so i believe its true based on 3 base cases, now i need to do my inductive step

hmm

how do i eval the left side

i have it like this

[haughty mountain]

starting from case n-1 and showing case n, with probably too many intermediate steps:

    (n - 1) n (2n - 1) / 6 + n²
  = ((n - 1) n (2n - 1) + 6n²) / 6
  = ((n - 1) n (2n - 1) + 6n²) / 6
  = n ((n - 1) (2n - 1) + 6n) / 6
  = n ((n - 1) (2n + 1) - 2(n - 1) + 6n) / 6
  = n ((n - 1) (2n + 1) + 4n + 2) / 6
  = n ((n - 1) (2n + 1) + 2(2n + 1)) / 6
  = n (n + 1) (2n + 1) / 6

[fiery cosmos]

how am i not getting the same thing as you when plugging in n-1 for n

how do you get from this:

to what you started with

(n - 1) n (2n - 1) / 6 + n²

[haughty mountain]

the two first factors should be obvious

the third one I simplified

[fiery cosmos]

ok before we do anything

[haughty mountain]

2(n-1) + 1
2n - 2 + 1
2n - 1

[serene zinc]

Anybody who can help me in Data structure and Algorithm

please I shall be thankful

Using the programs of the previous graph assignment, create a function that prints the graph in the format required by the app in this online graph editor: https://csacademy.com/app/graph_editor/ (Links to an external site.). Then, use the output of the new print function to generate the diagrams of all graphs from the previous assignment.

To generate the diagram of the graphs, simply copy the output of the print function into the Data field of the online app. Submit the .java code of your program along with screenshots of the graphs.link to the code.........> https://www.studocu.com/ro/document/universitatea-din-bucuresti/algoritmi-si-tehnici-de-programare/dijkstra/28013581

[heavy grove]

duds i had my HDD damaged, after copying the files, i found some of them r corrupted. pics, docs are easy to check. exes, installation files simply cant be verified. but how about zips, do zips have error correction? can i assume itz perfect if it can be open ''correctly"? i know zips have CRC check, should i run a CRC check?

[runic storm]

what is the best way to get key from nested dictionary in python

[runic storm]

this is my dictionary

what i want to do is get the main key using ip address if i enter '192.168.31.1' i want to get the key value sc

sorry what?

[runic storm]

no i don't want to flatten the dict

[pseudo walrus]

I can't say the efficient way yet, but this can do your work!
Restriction: Slower for millions and thousands of {key: values}.

def function(ip: str) -> str:
    for key, values in locs.items():
        if ip in values:
            return key, values[ip]

def main():
    ip = "192.168.31.1"
    key, servername = function(ip)
    print(f"{key} : {servername}")

[runic storm]

Thank you this works well but how do i get the servername?

return values.get(ip)

this works well

Thank you

[pseudo walrus]

updated the code

[runic storm]

Thank you

@pseudo walrus ++

[pseudo walrus]

welcome.

[burnt trellis]

what are these for ?

why all the cities from sri lanka lmao

[runic storm]

it is a little project i'm working on

[halcyon plank]

Hey @runic storm!

You either uploaded a .txt file or entered a message that was too long. Please use our paste bin instead.

[tacit nova]

what's the difference between Dynamic Programming and Greedy ?

Like I understand DP is an optimization of brute force by storing previous computed results, there are 2 types top-down recursion or bottom-up tabulation. And Greedy is try to get as many as possible at each steps. So I thought DP and Greedy is the same ?

[agile sundial]

greedy doesn't take into account past computations

[tacit nova]

that is ? lol, thank you

[agile sundial]

all greedy uses is the info at the current step to try and produce a globally optimal solution

[haughty mountain]

greedy is about making greedy choices that are (hopefully) optimal

dp considers all possibilities, but in a more clever way

[swift idol]

If I do X,Y = np.meshgrid(x, y) and plot Z = np.log(1/(X*Y), would I need to log scale both X and Y axes or just Y axis?

[fiery cosmos]

what does mean by this operator <> in algo? i just see some of it like in a condition of state for exemple ```
si (a <> b) alors
etc.
finsi

does it mean it is not equal? according to what i understood or does it have another meaning?

[half lotus]

That's what I've seen it mean in SQL

So most likely yes, that is what it means in this context too

[fiery cosmos]

is there another form for this condition (i mean as i have but in french lang) or only this form but general?