#algos-and-data-structs

1 messages · Page 145 of 1

silk tangle
# 
class Board:
    def __init__(self, state):
        self.state = state
        self.childrenList = []
        self.parent = None
        self.depth = 0
        self.visited = False

    #Function to generate the list of child boards.
    def generateChildList(self):
        #--TODO-- make sure children are legal and not the same as parent.
        tempState = self.state
        temp = Board(self.up(tempState))
        temp2 = Board(self.down(tempState))
        temp3 = Board(self.left(tempState))
        temp4 = Board(self.right(tempState))

        #Set child depth.
        temp.depth = self.depth + 1
        temp2.depth = self.depth + 1
        temp3.depth = self.depth + 1
        temp4.depth = self.depth + 1

        #Check to make sure that a child does not have the same board layout as a parent.
        #If the parent is not the solved state, then a child with that same state will not be solved.
        if temp.state != None: 
                self.childrenList.append(temp)
        if temp2.state != None: 
                self.childrenList.append(temp2)
        if temp3.state != None: 
                self.childrenList.append(temp3)
        if temp4.state != None:
                self.childrenList.append(temp4)

        #Set visisted to true.
        self.visited = True

    #Board moves. (Up,Down,Left,Right)
    #If the 0 is in the top line, it cant go up.
    def up(self, state):
        position = state.index(0)

        #Check for an illegal move.
        if position in (0,1,2):
            return None
        else:
            #Create a temp list for the new positions.
            newPositions = list(state)
            #Swap the positions of the board.
            newPositions[position], newPositions[position-3] = newPositions[position-3], newPositions[position]
            #Return the new list of positions.
            return tuple(newPositions)

    #If the 0 is in the bottom line, it cant go down.
    def down(self, state):
        position = state.index(0)

         #Check for an illegal move.
        if position in (6,7,8):
            return None
        else:
            #Create a temp list for the new positions.
            newPositions = list(state)
            #Swap the positions of the board.
            newPositions[position], newPositions[position+3] = newPositions[position+3], newPositions[position]
            #Return the new list of positions.
            return tuple(newPositions)

    #If the 0 is in the left most side, it cant go left. 
    def left(self, state):
        position = state.index(0)

        #Check for an illegal move.
        if position in (0,3,6):
            return None
        else:
            #Create a temp list for the new positions.
            newPositions = list(state)
            #Swap the positions of the board.
            newPositions[position], newPositions[position-1] = newPositions[position-1], newPositions[position]
            #Return the new list of positions.
            return tuple(newPositions)

    #If the 0 is in the rightmost side, it cant go right.
    def right(self, state):
        position = state.index(0)

        #Check for an illegal move.
        if position in (2,5,8):
            return None
        else:
            #Create a temp list for the new positions.
            newPositions = list(state)
            #Swap the positions of the board.
            newPositions[position], newPositions[position+1] = newPositions[position+1], newPositions[position]
            #Return the new list of positions.
            return tuple(newPositions)
#

I am trying to solve the 8 puzzle game

halcyon plankBOT
#

failmail :ok_hand: applied mute to @fiery cosmos until <t:1644302146:f> (9 minutes and 59 seconds) (reason: duplicates rule: sent 4 duplicated messages in 10s).

silk tangle
#

I figured out my issue. I implemented IDDFS. Only issue now is it's super super slow.

tight patio
#

there is a 3 litre and a 5 litre jug. how can he measure a exactly one litre of water?
whats the quickest way to do this?

#

this is what i found online
can't understand it

3*2-5=1
first fill the 5 litre jug with 3 litre jug once. then there will be two litres space in 5 litre jug.
fill 5 litre jug until full with 3 litre jug once.

that is good!
just remained only one litre in 3 litre jug.
#

so u fill the 3 litre jug fully with 5L one

#

fill 5 litre jug until full with 3 litre jug once.
whats that suppose to mean

#

also idk why we have to do this is algorithmics class

#

ig it suppose to be a introduction

slender sandal
#

Does this help

[_____]
[___]

[_____]
[###]

[###__]
[___]

[###__]
[###]

[#####]
[#__]
tight patio
cursive leaf
#

Hi. which algorithm should i use to solve this problem thanks.

Screenshot_from_2022-02-08_10-12-10.png
lean dew
#

what's Big o for py def Add(self,*data): temp = self.head self.head = Node(data[0]) self.head.next = temp temp.previous = self.head for i in data[1:]: self.head.previous = Node(i) self.head.previous.next = self.head self.head = self.head.previous

austere sparrow
fiery cosmos
#

Lmaoo idk about python ig I should leave this channel

fiery cosmos
#

does someone know what change i need to make to the dijkstra algorithm to make it so that the edges can be for a car or someone walking (or both), when the algorithm chooses to use a walking path it needs to leave the car behind and only choose walking paths until its at the destination vertex

#

i have changed the edges to include the data, tho idk what id need to change in the algorithm

agile sundial
#

you could include some flag or enum or something to show off your a car or walking, then you can choose paths based on the flag

fiery cosmos
#

so it starts in a car and then at every node it can choose to leave the car behind and do the rest walking

agile sundial
#

I c

fiery cosmos
#

so it somehow needs to explore all edges in a car without finishing the vertices and then explore all walking paths and finish the nodes

#

something like that i think, tho im not sure

halcyon plankBOT
#

Hey @halcyon kraken!

It looks like you tried to attach file type(s) that we do not allow (.save_multipla). We currently allow the following file types: .gif, .jpg, .jpeg, .mov, .mp4, .mpg, .png, .mp3, .wav, .ogg, .webm, .webp, .flac, .m4a, .csv, .json.

Feel free to ask in #community-meta if you think this is a mistake.

lean dew
# austere sparrow what do you think?

Well i thought generally length of data will be 1 so it will be constant and even if data is 2 or 5 or any constant no, it was like O(2) or O(5). So its again constant but then i also thought that len(list) can be 1 and constant integer and if i was to iterate through it , big O will be O(n). but still i wasn't sure. What is it ?

haughty mountain
fiery cosmos
haughty mountain
#

and then allow to move to the corresponding node in the graph without car for free

#

it's probably the neater option

#

car graph, no car graph, directed edges from the first to the second graph

fiery cosmos
#

ahh thats pretty smart! so find best path in both and then check in both results from where it could be faster to ditch the car?

fiery cosmos
#

So gcd stands for greatest common divider

#

Is this underlined statement gcd(a', b) % d true because gcd(a', b) = d and d % d

fiery oar
#

Does anyone know—or know any literature on—the amount of error introduced by doing comparisons on the floating point representation of rational numbers, versus comparing the rationals themselves?

#

Like, for a Fraction in the fractions package, rational numbers are compared by converting each to the same denominator, and then comparing the numerators.

vocal gorge
#

well, naively (or exactly? not sure. It is basically asking if float division is perfectly accurate to within float precision, which I believe is true), the error of converting a rational into a float is around the float precision near that float - so, basically math.ulp(a/b)

#

so at worst, I think the difference between Fraction(a,b) - Fraction(c,d) exactly and a/b - c/d is around math.ulp(a/b)+math.ulp(c/d)

#

if that error is higher than the difference between the fractions, then floats may cause the comparison to have a wrong result

#

If that's not what you want, try asking on the Computer Science server too - I have asked questions about floating-point errors there with great success

fiery oar
#

No, that answers my question 😅 Thank you! Now I just have to contemplate whether that is small enough that I can safely say it will never occur...

vocal gorge
#

it can definitely occur sometimes, e.g. consider:

#

!e

from fractions import Fraction as F
def cmp(x,y):
    return (x>y)-(x<y)
def test(f1,f2):
    return cmp(f1,f2) != cmp(float(f1),float(f2))

x = 10**20
a = F(x,x)
b = F(x,x+1)
print(test(a,b))
print(a,b)
print(float(a),float(b))
halcyon plankBOT
#

@vocal gorge :white_check_mark: Your eval job has completed with return code 0.

001 | True
002 | 1 100000000000000000000/100000000000000000001
003 | 1.0 1.0
vocal gorge
#

here, the second fraction is 1 too as far as floats are concerned

#

!e

from fractions import Fraction as F
import math
x = 10**20
a = F(x,x)
b = F(x,x+1)
total_error = math.ulp(float(a)) + math.ulp(float(b))
delta = float(a-b)
print(f"{delta=}, {total_error=}")
halcyon plankBOT
#

@vocal gorge :white_check_mark: Your eval job has completed with return code 0.

delta=1e-20, total_error=4.440892098500626e-16
vocal gorge
#

the total error is indeed much higher than the delta between the numbers, so the rule works here

fiery oar
#

I certainly see what you mean. I was really hoping to get away with using floats, but for robustness it seems that won't work.

zealous bloom
#

How to make discord bot with python

rustic salmon
vocal imp
#

hi

#

what does O(n) mean for time complexity or space complexity?

agile sundial
#

it means the runtime increases linearly as you increase the input size

#

or the amount of memory you use

keen hearth
#

I generally think of it in terms of the effect of doubling the size of the input.

#

O(n) runtime (essentially) means if you double the size of the input, n, you double the runtime.

#

O(1) means if you double n, the runtime stays the same.

#

O(n^2) means if you double n, the runtime is multiplied by four.

#

O(n^3) ... multiplied by eight.

#

And so on.

fiery cosmos
dire trench
fiery cosmos
# 
for a in range(lmao):
    for b in range(lmao):
        for c in range(lmao):
            for d in range(lmao):
                for e in range(lmao):
                    for f in range(lmao):
                        for g in range(lmao):
                            for h in range(lmao):
                                for i in range(lmao):
                                    for j in range(lmao):
                                        for k in range(lmao):
                                            for l in range(lmao):
                                                for m in range(lmao):
                                                    for n in range(lmao):
                                                        for o in range(lmao):
                                                            for p in range(lmao):
                                                                for q in range(lmao):
                                                                    for r in range(lmao):
                                                                        for s in range(lmao):
                                                                            for t in range(lmao):
                                                                                for u in range(lmao):
                                                                                    print('lol')
#

This is O(n^21) time complexity

#

script:

# 
a=''
b=97
while True:
    print(a+'for '+chr(b)+' in range(lmao):')
    a+='\t'
    b+=1
halcyon plankBOT
#

Hey @rain sparrow!

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

open swift
#

how to find time complexity

lean walrus
# 
import random
while True:
    if random.randint(0, 1) == 0:
        break
``` what is time complexity of this code?
#

strictly speaking it is O(inf), but in practice it is O(1)

rain sparrow
#

Hello everyone, if there is no issue, could you please help me. Actually I just want to alter bars' colours and the background colour. However when I do add color="gold" for example, some syntaxis error appear. I am a newbie to Python, so would be grateful if you help. The code was taken from sergei perfiliev. He allows to change it on his twitter acc.

https://paste.pythondiscord.com/anovozucuc.py

Could you please help me with that

drowsy bear
# 
arr=[3,2,4,5,21,2,4,5]
for x in range(len(arr)):
        for i in range(len(arr)-1):
            if arr[i]%2!=0 and arr[i+1]%2==0:
                current=arr[i]
                arr[i]=arr[i+1]
                arr[i+1]=current
print(arr)

This is a program that puts all even numbers in first half of the list and the odd numbers after that what I don't understand is why does outer loop have to go to len(arr)

tight epoch
#

help !!

#

I wanna create a sub array from a given array , but for a specific range..
how this could be done?

#

for eg-

#

arr = [ 1, 2, 3 , 7, 4, 9 ,8]
new array from 3 to 9 , in the same order as in "arr"

#

new_arr = [3,7,4,9]

#

plzz help!

drowsy bear
# tight epoch plzz help! 
arr = [ 1, 2, 3 , 7, 4, 9 ,8]
arr2=[]
a=int(input('a='))
b=int(input('b='))
x=0
while arr[x]!=a:
    x+=1
y=0    
while arr[y]!=b:
    y+=1

if y>x:
    for i in range(x,y+1):
        arr2.append(arr[i])
else:
    for i in range(y, x+1):
        arr2.append(arr[i])

print(arr2)
agile sundial
#

tfw you reimplement slicing

dire wadi
#

Hey guys, I dont really know how to use this server ahaha, but I have been trying to navigate my way through telemetry Scripting in python. Can anyone provide any sources to help me find some info?

late beacon
#

Hi! How can i change a repeated element inside a column of a Matrix?

#

The Matrix Is NxM

haughty mountain
dark aurora
#

If I had to find the longest path in a graph would this code/solution work
function findlongest(inx, distance)
maxdistance = 0
proccesed[vertex] = 1
for vertex in connections(inx)
if proccesed[vertex] = 1:
continue
if findlongest(vertex, distance+1)>maxdistance
maxdistance=findlongest(vertex, distance+1)
return (distance+maxdistance)
#this is kinda the logic, not the actual code

haughty mountain
#

longest path in a general graph is a NP-hard problem

quick harbor
#

hey anyone cna help me so i started coding like few days ago and im making pong game yk for learning and the ball gets stuck in the ground

#

ball.setx(ball.xcor() + ball.dx)

#

they say this is the problem

#

but for going up its the same just changed xcore and dx to y

#

ball.sety(ball.ycor() + ball.dy)

#

what do i do?

haughty mountain
#

the update rules for dx and dy is probably the issue

quick harbor
#

but when its up it bounces off normal

#

but what do i type in there then

haughty mountain
#

you haven't posted how you update dx and dy

quick harbor
#

wdym posted

haughty mountain
#

code

quick harbor
#

which one

haughty mountain
#

for what the logic for dx and dy is

quick harbor
#

can i send the whole ocde?

#

code?

#

its 80 lines

#

but its not finished

haughty mountain
#

80 is fine to post here

#

!code

halcyon plankBOT
#

Here's how to format Python code on Discord:

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

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

quick harbor
#

actaully 90 lines

#

import turtle

wn = turtle.Screen()
wn.title("Pong by @roberts_vierpe")
wn.bgcolor("black")
wn.setup(width=800, height=600)
wn.tracer(0)

Paddle A

paddle_a1 = turtle.Turtle()
paddle_a1.speed(0)
paddle_a1.shape("square")
paddle_a1.color("white")
paddle_a1.shapesize(stretch_wid=5, stretch_len=1)
paddle_a1.penup()
paddle_a1.goto(-350, 0)

Paddle B

paddle_b1 = turtle.Turtle()
paddle_b1.speed(0)
paddle_b1.shape("square")
paddle_b1.color("white")
paddle_b1.shapesize(stretch_wid=5, stretch_len=1)
paddle_b1.penup()
paddle_b1.goto(350, 0)

Ball

ball = turtle.Turtle()
ball.speed(0)
ball.shape("square")
ball.color("white")
ball.penup()
ball.goto(0, 0)
ball.dx = 0.1
ball.dy = 0.1

Functions

def paddle_a1_up():
y = paddle_a1.ycor()
y += 20
paddle_a1.sety(y)

def paddle_a1_down():
y = paddle_a1.ycor()
y -= 20
paddle_a1.sety(y)

def paddle_b1_up():
y = paddle_b1.ycor()
y += 20
paddle_b1.sety(y)

def paddle_b1_down():
y = paddle_b1.ycor()
y -= 20
paddle_b1.sety(y)

Keyboard Binding

wn.listen()
wn.onkeypress(paddle_a1_up, "w")
wn.onkeypress(paddle_a1_down, "s")

wn.onkeypress(paddle_b1_up, "Up")
wn.onkeypress(paddle_b1_down, "Down")

Main Game loop

while True:
wn.update()

# Move The Ball
ball.setx(ball.xcor() + ball.dx)
ball.sety(ball.ycor() + ball.dy)

# Border Checking
if ball.ycor() > 290:
    ball.sety(290)
    ball.dy *= -1

if ball.ycor()  < -290:
    ball.sety(-290)
    ball.dx *= -1

if ball.xcor() > 390:
    ball.goto(0, 0)
    ball.dx *= -1

if ball.xcor() < -390:
    ball.goto(0, 0)
    ball.dx *= -1
#

its at move ball

haughty mountain
#

do
```py
your code here
```
for code formatting

quick harbor
#

k

# 
import turtle

wn = turtle.Screen()
wn.title("Pong by @roberts_vierpe")
wn.bgcolor("black")
wn.setup(width=800, height=600)
wn.tracer(0)

# Paddle A
paddle_a1 = turtle.Turtle()
paddle_a1.speed(0)
paddle_a1.shape("square")
paddle_a1.color("white")
paddle_a1.shapesize(stretch_wid=5, stretch_len=1)
paddle_a1.penup()
paddle_a1.goto(-350, 0)

# Paddle B
paddle_b1 = turtle.Turtle()
paddle_b1.speed(0)
paddle_b1.shape("square")
paddle_b1.color("white")
paddle_b1.shapesize(stretch_wid=5, stretch_len=1)
paddle_b1.penup()
paddle_b1.goto(350, 0)

# Ball
ball = turtle.Turtle()
ball.speed(0)
ball.shape("square")
ball.color("white")
ball.penup()
ball.goto(0, 0)
ball.dx = 0.1
ball.dy = 0.1


# Functions
def paddle_a1_up():
    y = paddle_a1.ycor()
    y += 20
    paddle_a1.sety(y)

def paddle_a1_down():
    y = paddle_a1.ycor()
    y -= 20
    paddle_a1.sety(y)

def paddle_b1_up():
    y = paddle_b1.ycor()
    y += 20
    paddle_b1.sety(y)

def paddle_b1_down():
    y = paddle_b1.ycor()
    y -= 20
    paddle_b1.sety(y)

# Keyboard Binding
wn.listen()
wn.onkeypress(paddle_a1_up, "w")
wn.onkeypress(paddle_a1_down, "s")

wn.onkeypress(paddle_b1_up, "Up")
wn.onkeypress(paddle_b1_down, "Down")

# Main Game loop
while True:
    wn.update()

    # Move The Ball
    ball.setx(ball.xcor() + ball.dx)
    ball.sety(ball.ycor() + ball.dy)

    # Border Checking
    if ball.ycor() > 290:
        ball.sety(290)
        ball.dy *= -1

    if ball.ycor()  < -290:
        ball.sety(-290)
        ball.dx *= -1

    if ball.xcor() > 390:
        ball.goto(0, 0)
        ball.dx *= -1

    if ball.xcor() < -390:
        ball.goto(0, 0)
        ball.dx *= -1
#

its at ball move

#

move the ball *

haughty mountain
#

i guess this shouldn't be dx here?

    if ball.ycor()  < -290:
        ball.sety(-290)
        ball.dx *= -1
quick harbor
#

the ball gets stuck liek this

quick harbor
#

lemme go check

#

bruh

#

how do you see it

#

ty sm

#

how tf did u see it

dark aurora
haughty mountain
quick harbor
#

wow

haughty mountain
#

and then having a y coordinate check together with a change to dx just looked wrong

dark aurora
quick harbor
#

one more thing something is wrong but doesent show up

#

nvm im just stupid

#

nvm something is wron

#

g

#

i made th code so the ball bounces off the paddle but it goes through

#

!code

halcyon plankBOT
#

Here's how to format Python code on Discord:

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

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

quick harbor
# 
# Paddle and ball collisions
        if ball.xcor() > 340 and (ball.ycor() < paddle_b1.ycor() + 40 and ball.ycor() > paddle_b1.ycor() -40):
            ball.dx *= -1
#

is is something wrong in there?

haughty mountain
worldly solar
# 
def example4(manatees):
    oldest_manatee = "No manatees here!"
    for manatee1 in manatees:
        for manatee2 in manatees:
            if manatee1['age'] < manatee2['age']:
                oldest_manatee = manatee2['name']
            else:
                oldest_manatee = manatee1['name']
    print oldest_manatee
#

what is the big o notation of this?? I am confused as to what to count and what not to

#

It'd be O(n^2) for the for loop iteration but how do I count the if else statements or do I not count them at all?

#

and is it just +2 for the other 2 declaring and print statements?

#

cause the quiz I am doing says in the answer that

def example2(manatees):
    print manatees[0]['name']
    print manatees[0]['age']

big o notation of this is O(1) but in the lesson they add 2 for a declaring command and print command

#

I have just started with O notations so am confused

#

sorry if my questions seem silly

haughty mountain
#

count the number of "simple" operations, and find the order of that

#

and because you only care about the O of the thing you can be a bit sloppy (in ways that won't affect the final answer)

worldly solar
#

I see

worldly solar
haughty mountain
#

lower order terms don't matter, we can drop 2x and 1
constant factors don't matter, we can drop the factor of 3

worldly solar
#

I see

worldly solar
dark aurora
haughty mountain
#

but there are...many paths

dark aurora
dark aurora
haughty mountain
dark aurora
pseudo star
#

Hi, I don't undestand something ,is it normal that an 8*8 array made with a numpy array is much larger than an 8*8 array made with a python list using the getsizeof method? Isn't numpy array supposed to use less memory than python lists? (I understand the concept of lists using pointers ,and of array being a "chain" in the stack memory but still...). I intend to do a project using machine learning ,so I would like to store a lot of data (8*8 array) using as little space as possible ,which should I prefer ? the python list implementation or the numpy array ? :/

austere sparrow
#

it's not particularly useful if you want to know how much memory something occupies

#

!e

import sys
xs = [[0]*1000, [0]*1000, [0]*1000, [0]*1000]
ys = [1, 2, 3, 4]
print(sys.getsizeof(xs))
print(sys.getsizeof(ys))
halcyon plankBOT
#

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

001 | 88
002 | 120
austere sparrow
#

for some reason the ys list is even larger.

#

but the idea is the same

#

so I would like to store a lot of data (8*8 array)
an 8x8 array of integers is not a lot of data 🙂

austere sparrow
pseudo star
austere sparrow
#

Moreover, you can have shared ownership, like ```py
a = [0] * 1000
b = [1] * 2000
c = [2] * 3000

xs = [a, b, b, b, b, b]
Ys = [c, c, c, b, b]
``` so it doesn't really make sense to say "xs occupies (some amount) of bytes" or "ys occupies (some amount) of bytes"

austere sparrow
#

If you want to perform some fast operations provided by numpy, use numpy

pseudo star
#

it's for encoding chess positions ,so yeah a lot of fast operations too

austere sparrow
#

numpy doesn't make your program faster automatically, but it lets you apply certain operations on the whole array, like multiplying the whole array by some number, really fast.

pseudo star
#

it is somehow faster than a python list because of the adjustment of the array in memory no ?, like for example for a dichotomic search

#

but i guess this is relevant when the array is really big

austere sparrow
#

A Python list is not a linked list, it's actually a dynamic array. So looking up an element by index is O(1)

#

If you want a fixed-size fixed-type integer array, you can also use the built-in array module. I think it will be more memory-efficient than a list, but not sure about speed.

#

!d array

halcyon plankBOT
#
array

This module defines an object type which can compactly represent an array of basic values: characters, integers, floating point numbers. Arrays are sequence types and behave very much like lists, except that the type of objects stored in them is constrained. The type is specified at object creation time by using a type code, which is a single character. The following type codes are defined:

Similar names: numpy.term.array
fiery cosmos
#

python

faint spoke
#

https://www.techiedelight.com/shortest-superstring-problem/

I want to convert the C++ solution for this to Python and have written the Python code below. It doesn't output anything. Please debug it. C++ code is in the link above and my Python code is below. Thank you, would be of enormous help.

https://pastebin.com/Tgy91nCF (edited)

Techie Delight
Admin
Shortest Superstring Problem | Techie Delight

Given a list of strings where no string is a substring of another, find the shortest string that contains each string in the list as a substring.

Pastebin
Shortest Superstring Problem - Pastebin.com

Pastebin.com is the number one paste tool since 2002. Pastebin is a website where you can store text online for a set period of time.

quick harbor
#

!code

fiery cosmos
#

hay boy

fiery cosmos
#

I am interested how did we get this underlined expression?

shut breach
#

same coefficients as the LHS, with the order of the highest term

#

for the purpose of combining the terms

fiery cosmos
shut breach
#

3n^2 + 5n^2 + 2n^2 = 10n^2

austere sparrow
#

they could pick 100 instead of 10 and it would also be right

#

To prove that 3n^2 + 5n + 2, they say:

  1. 3n^2 <= 3n^2
  2. 5n <= 5n^2
  3. 2 <= 2n^2
  4. (from 1, 2, 3), 3n^2 + 5n + 2 <= 3n^2 + 5n^2 + 2n^2
  5. add up the right part, 3n^2 + 5n + 2 <= 10n^2
fiery cosmos
#

@austere sparrow Yeah, I understand that, but I don't understand why we compare that, I mean, isn't it a case that if there is some largest exponentiation, big o will always be O(n^largest exponentiation in expression)?

austere sparrow
austere sparrow
shut breach
#

the blue is the definition, the green is proving that 3n^2 + 5n + 2 meets that definition

fiery cosmos
#

This passage is introducing the formal definition of O(n^2)
Hmm, I don't understand how is that derived from definition above about Big O. I mean, isn't it said that second expression should be multiplied by some constant c? In this case, what was done is that they just raised all unknowns (variables, in this all x) to the same exponentiation

austere sparrow
fiery cosmos
austere sparrow
fiery cosmos
#

@austere sparrow @shut breach did they just wanted to show that whatever n if taken as input, it will always be less than 10n^2?

austere sparrow
#

f(x) is O(g(x)) means that there exist some factor and starting_point, so that for for all x starting with starting_point, f(x) <= factor * g(x).

For example, let's take f(x) = 3x^2 + 5x + 2 and g(x) = x^2. We can pick factor to be 10 and starting_point to be 1, therefore f(x) is O(g(x))

#

that's what they meant

shut breach
#

yeah the point is that 3n^2 + 5n + 2 <= 3n^2 + 5n^2 + 2n^2 <= 10n^2

austere sparrow
#

math examples are bad at separating levels of abstraction

fiery cosmos
#

The idea is that we want something that cares about what happens when the inputs get very large and sort of only care about things up to constants.
what is meant here up to constants?

austere sparrow
# fiery cosmos Haha, now what does that mean? what are levels of abstraction?

it It's the level of detail a function or a class is operating with. For example, this would be a very strange function: ```py
def update_customer_avatar(customer):
try:
avatar = customer.create_avatar()
except psycopg2.UniqueConstraintViolation:
# already exists
avatar = customer.avatar()

if user.is_pro_user():
    avatar.add_star()

# save the avatar to cache
with open(os.path.join(cache.avatars_path, customer.uuid + ".png"), "wb") as fh:
    ... # do some file I/O

because you're mixing high level concepts (like the premium status of a user) with low level concepts (file I/O, a database exception all of a sudden). Compare to this:py
def update_customer_avatar(customer):
try:
avatar = customer.create_avatar()
except CustomerAlreadyHasAvatar:
avatar = customer.avatar()

if user.is_pro_user():
    avatar.add_star()

avatar.sync()
#

I think the textbook example mixes levels of abstraction because it presents a high-level concept (f is O(g)) but then all of a sudden starts multiplying stuff. It usually turns out a bit confusing, obscuring the bigger picture

#

anyway... that's a bit of a side note

fiery cosmos
#

yeah now I think I understand what you meant by level of abstractions

austere sparrow
#

If you compare f(n) = 10n and g(n) = (1/1000) * n^2, f will be bigger at first, but then g will win over it

#

the details are interesting, but this is a good explanation of the bigger picture

#

(levels of abstraction came back 🙂 )

#

or rather, it comes from a computational angle, rather than a (purely) mathematical

fiery cosmos
#

How did they calculate this underlined?

fiery cosmos
austere sparrow
#

I don't remember the exact proof to be honest, let me think for a bit

fiery cosmos
#

I understand how did they get n^5, that's big o polynomial, but how did they get big o ((sqrt(2)^2)?

austere sparrow
#

wdym?

fiery cosmos
#

Isn't it a case that in the example above they wanted to show difference in growth between polynomial function and exponential function?

#

So I said that I guess that n^5 is big of of particular polynomial here highest exponentiation is 5

#

but I don't know why is n^5 = O((sqrt(2)^n)

shut breach
#

the short answer is that exponentials just grow faster than polynomials no matter the base

fiery cosmos
shut breach
#

i think they were just giving an example of that

austere sparrow
#

yeah

haughty mountain
#

big O is a notation for upper bounds

#

e.g. things in O(1) is also in O(n)

shut breach
#

fwiw I disagree with their use of = here

haughty mountain
#

it should technically be a set contains, yeah

fiery cosmos
haughty mountain
#

but using = is convenient (and not that incorrect)

austere sparrow
#

There isn't a single "big O" for a function, it's a relation between two functions. For example, x is O(x^2), but also O(x) and O(10x) and O(x!) and O(6^x).

shut breach
#

O(f(x)) is a set
it should be g(x) ∈ O(f(x))

haughty mountain
#

yeah, they are families of functions

shut breach
haughty mountain
#

O(n) * O(n) = O(n^2) is very convenient though, granted I'm a physicist/engineer and not a mathematician 😛

shut breach
#

you can make that work for some creative definition of *

haughty mountain
#

or more usefully f(x) = g(x) + O(small term that we can disregard)

fiery cosmos
#

did they mean that for particular polynomial, for example for polynomial with highest exponential 5 where big o is 5 is equal to big o for exponetiation function here n is equal to 5 and big o for exponentiation function is O((sqrt(2)^n)?

haughty mountain
#

e.g. ignoring O(epsilon^2)

haughty mountain
fiery cosmos
#

guys, when you write O, does that mean big O?

shut breach
#

O(f(x)) is the set of functions that grow slower or the same as f(x)

haughty mountain
#

there are several related notations
O is an upper bound
Ω is a lower bound
Θ is a tight bound

shut breach
austere sparrow
#

oh wait, no

#

I'm stupid sorry

fiery cosmos
haughty mountain
#

polynomials are in general smaller than exponentials (for large input)

#

(finite degree polynomials, before someone complains)

fiery cosmos
#

guys @austere sparrow @shut breach what do you mean that those equalities mean?

shut breach
#

for any n you can always come up with a polynomial that is larger at that n than an exponential, however for all p(x) and e(x) there exists an n such that e(x) * C >= p(x) for x>n

shut breach
haughty mountain
#

writing them as equalities is technically not correct, as mentioned earlier

#

but my reading is what is meant

shut breach
#

n^100 ∈ O(1.1^n)

tranquil shard
#

Best Book/tutorials for learning data structures and algorithms??

haughty mountain
#

n^100 is in the family/set of function that aren't "larger" than 1.1^n for large n

shut breach
haughty mountain
#

formally: there exist constants C and N such that n^100 <= C*1.1^n when n >= N

fiery cosmos
#

but why they wrote that?

austere sparrow
#

well, it is a true statement

haughty mountain
#

it's a terrible bound, but it's correct

fiery cosmos
#

I mean how does that picture above relates to this text

#

What's more surprising is that if you have any polynomial and any exponential, the exponential always grows faster. So n to the fifth is O of root two to the n.

#

so are these big o for expontiation functions?

#

@shut breach

haughty mountain
#

it has all these higher order terms

#

e.g. x^4 <= 24*e^x

fiery cosmos
#

so are these big o for expontiation functions?

#

I mean those O's

shut breach
#

i dont understand what you're asking

fiery cosmos
#

It's confusing for me

#

why this underlying is a case

shut breach
#

why not?

haughty mountain
#

fwiw n^5 = O(1.1^n) and n^100 = O(sqrt(2)^n) as well

#

one very big reason to not use = here is that you can't reverse the relation

#

n^5 ∈ O(1.1^n) and n^100 ∈ O(sqrt(2)^n)

#

for all functions f ∈ O(1.1^n) it's also true that f ∈ O(sqrt(2)^n)

#

but the reverse is not true

#

for all functions f ∈ O(sqrt(2)^n) it's not generally true that f ∈ O(1.1^n)

#

O(sqrt(2)^n) is "bigger" than O(1.1^n)

fiery cosmos
#

yeah but how did they found out that n^5 = O(1.1^n)?

#

@haughty mountain @shut breach @austere sparrow

haughty mountain
#

you show that there exist constants C and N such that n^5 <= C*1.1^n when n >= N

#

like I said the definition was

austere sparrow
#

are you asking how to prove this formally?

fiery cosmos
#

Ok I will read what you guys wrote after break, I think I don't understand Big O definition that much clearly as to think in way of families of functions

haughty mountain
#

the general definition of f(n) being in O(g(n)) is that there exist constants C and N such that f(n) <= C*g(n) when n >= N

fiery cosmos
haughty mountain
#

is the confusion about how you prove that n^a is in O(b^n)?

fiery cosmos
haughty mountain
#

there are many ways of proving or motivating it

#

if you're comfortable with the Taylor series of b^n it's also very straightforward to convince yourself it's true that way

fiery cosmos
haughty mountain
#

O(1) are constants, let's pick some constant k

Does there exist constants C and N such that k <= C*n when n >= N?

#

||C = k|| and ||n >= 1|| works

fiery cosmos
#

@haughty mountain Differently said, O(1) means for some function, upper bound is 1, that means that for any given X, biggest output value is always less than 1?

agile sundial
#

less than 1 times some constant

haughty mountain
#

also for large enough inputs

haughty mountain
shut breach
#

i.e. the run time does not scale with the size of the input at all

fiery cosmos
#

So to start with the definition. The idea is that we want something that cares about what happens when the inputs get very large and sort of only care about things up to constants.
I don't understand part "about things up to constants"

haughty mountain
#

n and 123n are "the same", up to a constant factor

fiery cosmos
#

I see, thanks. That's what I meant but just wanted to check

valid vortex
#

how to print ('helo(hi))

rustic perch
#

Print("hello")

#

Like that

fiery cosmos
#

I think it's asking if you plug in come concrete number n0 into both at what point does A do better than B

#

It's Maths
Solve the inequality 5n^2 <= 1000n

#

The question is basically, find the maximum 'n' such that A is better than B

#

You need to find n0, and the condition is that for all numbers below that and including that n0, algo A is better than algo B

#

n0 is what we're looking for; n0 here = the maximum value of n such that A(n) is better than B(n)

#

Yes

#

👍 that's it

charred halo
#

Does anyone have any advice/resources to learn + practice python lists and algorithms and working with data to improve on those topics

serene wedge
lean dew
#

Is there any platform or site which will provide dsa examples or code which have most functionality and efficiency like for linked list , stack etc

charred halo
serene wedge
lean dew
#

I was looking for file to download or look to learn on my own how they did it, but i guess that works as well

swift junco
#

Hi

#

May I ask for help about a program i'm trying to do ?

#

its about matrix

gusty spire
#

I'm having trouble implementing the algorithm for min max heap mentioned on this page as find(k) which retrieves the kth smallest element. The time constraint for this should be O(logn) or less. link: https://en.m.wikipedia.org/wiki/Min-max_heap#:~:text=In computer science%2C a min,and maximum elements in it.

Min-max heap

In computer science, a min-max heap is a complete binary tree data structure which combines the usefulness of both a min-heap and a max-heap, that is, it provides constant time retrieval and logarithmic time removal of both the minimum and maximum elements in it. This makes the min-max heap a very useful data structure to implement a double-ende...

lucid orbit
fiery cosmos
#

I tried to use google translate for coincide but I don't understand what would it mean in this context?

haughty mountain
fiery cosmos
haughty mountain
#

G1 = G

fiery cosmos
#

maybe this explains context better

haughty mountain
#

"If G1 = G, then our lemma is proved already"

fiery cosmos
#

and how do you mean that g1 = g if g is further than g1?

haughty mountain
#

Where does it say that G is further than G1?

#

It says that G is the furthest point, not that it is further than G1

gusty spire
#

Does anyone know how to find kth smallest in min max heap tho?

haughty mountain
#

I suspect the argument is that if some optimal path contained G1 you could pick G instead and still have an optimal path. So you can always greedily pick the last ok point

fiery cosmos
#

@haughty mountain is english your native lang?

haughty mountain
fiery cosmos
haughty mountain
#

G is the furthest point, but nothing prevents G1 from also being that furthest point

#

but the point you'll get to is that if G1 < G you can just pick G and the path is not worse

#

so as a consequence you can just pick the furthest reachable point

fiery cosmos
haughty mountain
agile sundial
#

it's not a min/max heap

#

it's a min-max heap

gusty spire
#

Exactly

#

Wikipedia says it's possible

fiery cosmos
#

@agile sundial Do you think that coincide in question above means that G1 = G?

gusty spire
#

In constant time

haughty mountain
gusty spire
#

The strangest thing is I cannot find info about this anywhere online

haughty mountain
#

Do you mean the thing mentioned in the extensions section?

The min-max-median heap is a variant of the min-max heap, suggested in the original publication on the structure, that supports the operations of an order statistic tree.

gusty spire
#

Despite the 100s of algorithm articles i can't find a single about min-max heap getting kth smallest element

#

No it's mentioned in the second paragraph

#

Find(k)

haughty mountain
#

I think that's referring to that extension

gusty spire
#

delete-median,[2]find(k) (determine the kth smallest value in the structure) and the operation delete(k) (delete the kth smallest value in the structure), for any fixed value (or set of values) of k. These last two operations can be implemented in constant and logarithmic time, respectively.

haughty mountain
#

Yes, the paragraph that begins with

The structure can also be generalized to support other order-statistics operations efficiently...

gusty spire
#

Oh yeah

haughty mountain
gusty spire
#

Ohh I see

#

Thank you so much

#

Hmmm

#

I don't really understand

#

I'm having trouble implementing the find kth smallest

haughty mountain
#

seems the min-max heap for order statistics trees only works with pre-determined k

#

and not any k at runtime (after construction)

gusty spire
#

By k u mean the kth smallest element?

haughty mountain
#

yes, the k in "kth smallest element"

gusty spire
#

I see

haughty mountain
#

just count them? also not the right channel for this

gusty spire
#

Oh would this work? https://en.m.wikipedia.org/wiki/Order_statistic_tree

Order statistic tree

In computer science, an order statistic tree is a variant of the binary search tree (or more generally, a B-tree) that supports two additional operations beyond insertion, lookup and deletion:

Select(i) — find the i'th smallest element stored in the tree
Rank(x) – find the rank of element x in the tree, i.e. its index in the sorted list of elem...

#

I don't think u need AVL for this

haughty mountain
#

I think the more general solution to kth order statistic is some variant of a self balancing tree, e.g. an AVL tree or a RB tree with some extra metadata

gusty spire
#

Ah I see

haughty mountain
#

is k a constant you know beforehand or not?

gusty spire
#

The thing is Im not allowed to use AVL

gusty spire
#

0.618 is golden ratio I think

#

So k changes everytime tree gets or loses an element

haughty mountain
#

if so, can't you just keep one min-heap and one max-heap and balance them against each other

#

oh, you need to be able to remove elements as well?

gusty spire
#

I just need to lookup kth smallest element in O(logn) or less time

gusty spire
#

I know how to build min and max but I'm stuck on the actual algorithm to find kth smallest

haughty mountain
#

you have elements less than the ratio (the current k) in a max-heap, and elements larger in a min-heap

#

when you add an element you add it to whatever side should contain it, and maybe you need to move an element between the heaps to keep the ratio right

#

@gusty spire you get the idea?

gusty spire
#

Sorry just reading

gusty spire
fiery cosmos
#

"If G is closer than G2, refill at G instead of G1". G2 = next stop in R. G1=position of first reffil in R. First thing that confuses me - If G2 is next stop, how can G be closer than G2?

unknown.png
gusty spire
#

Ohhh I think I get it

haughty mountain
#

if you have two heaps where you have the balance you need (in your case the smaller one should be something like 0.618 of the size)

small           large
[..., max] [min, ...]
```when you add a new element it just goes whereever it needs to go, and then you rebalance to keep your ratio correct
#

I think you only ever need to rebalance by moving 1 element

gusty spire
#

I see

#

So whenever you insert an element x you check if x > ratio then insert in min otherwise max.

haughty mountain
#

if it goes in the small partition you might need to pop the max from there and move it to the large partition to keep the ratio right

#

and vice versa if you end up adding it to the large one

gusty spire
#

I see

#

Sorry just to confirm by small partition you mean max heap and large partition min heap right?

haughty mountain
#

right, when I say small partition I mean the max-heap containing the small values, and when I say large partition I mean the min-heap containing the large values

#

this setup structure allows you to shuffle elements between the parts to keep the balance at all times

gusty spire
#

I see

#

So if I wanted kth smallest which will just be the result of Ciel(0.618*Len(tree) how do I get that?

haughty mountain
#

something like keep a fraction 0.618 of elements in the small part

#

e.g. such that the element you're looking for is always the min element in the large heap

gusty spire
#

Ohh I see

haughty mountain
#

with this you have O(log n) insertion and O(1) lookup for your current value of k = Ciel(0.618*Len(tree))

gusty spire
#

But how would I get min elem of large heap?

haughty mountain
#

it's a min heap

gusty spire
#

Ohhh I see

#

That makes sense

#

The only thing I don't understand is how do I know what position and where element should go when I insert.. won't I have to know the order of the elements to do that?

haughty mountain
#

no? If you are inserting element x

small           large
[..., max] [min, ...]
```if `x <= max` insert among small, if `x >= min` insert among large, otherwise do whatever (you could be clever in this case, but lets not)

then you check if the balance between `len(small)` and `len(large)` is right, if it's not then shuffle elements across until the balance is correct
haughty mountain
#

classic exchange argument

fiery cosmos
# haughty mountain fwiw even if that was to make sense I don't like that proof approach. All you ne...

So, G = farthest reachable refill from current position, G1 = position of first refill in R, G2 = next stop in R (refill or B). "If G is closer than G2, refill at G instead of G1" - isn't it a case to 1) move to G1 which is first refill place 2) move at next refill station G2 which is refill station after G1? So if it's a case that G is the farthest refill station that is reachable from current position, G1 is only place before G2, isn't it a case that it's a must to refill at G1?

haughty mountain
#

if G > G1 then you can go to G and you're not in a worse situation than before

#

that's pretty much the whole argument that's needed

#

from G you can for sure reach G2, so the solution after G is still valid

#

now you can again pick the furthest point from G

#

and if you keep going you have a solution that is as good or better than the presumed optimal solution you started with

#

that only makes the greedy choice of picking the furthest refill station

fiery cosmos
#

@haughty mountain Could you please answer to my question because it confuses me?

#

I understand general logic, but proof confuses me

haughty mountain
#

I don't really know what they are trying to say 🤷‍♀️

fiery cosmos
#

Haha, okay

#

btw what are some other places where I could ask for help with regards to alghoritms?

haughty mountain
#

you would pick G even if it was for some reason to the right of G2, so I have no clue why they say the G < G2 thing

lean junco
#

will it be better to use jupyter rather then ide for NN

haughty mountain
fiery cosmos
#

Maybe it has to do with this lemma

fiery cosmos
haughty mountain
silent pewter
#

does anyone have any good beginner small project ideas for a beginner like myself? I've done some search algorithms and stuff like that

rigid cradle
#

Hi

dark aurora
#

why doesn't this code work for finding longest path in directed acyclic graph (i need to find the longest path with the same charachters through a grid)

# 
from copy import deepcopy as dcopy

n = int(input())
mx = [list("#"+input()+"#") if i != 0 and i != (n+1) else ["#"]*(n+2) for i in range(n+2)]
pro = [[1]+[0]*(n)+[1] if i != 0 and i != (n+1) else [1]*(n+2) for i in range(n+2)]
pro1 = dcopy(pro)

def dfs(tup):
    x,y = tup[0], tup[1]
    pro1[x][y] = 1
    cn = [(x,y+1),(x,y-1),(x+1,y)]
    dist = 0
    for i in cn:
        if pro1[i[0]][i[1]] == 1 or mx[x][y] != mx[i[0]][i[1]]: continue
        disttemp = dfs((i[0],i[1]))
        if disttemp>dist:
            dist = disttemp
    return (dist+1)
            

rez = 0
for k in range(1, (n+1)):
    for l in range(1, (n+1)):
        reztemp = dfs((k,l))
        if reztemp>rez:
            rez = reztemp
        pro1 = dcopy(pro)

   
print(rez)```
shut breach
gusty spire
#

plsss

#

someone

#

how to get kth smallest element from a heap in O(1) time

#

and dont just link the wikipedia page for max-min heap cus it doesnt explain it

haughty mountain
# gusty spire and dont just link the wikipedia page for max-min heap cus it doesnt explain it

I outlined the process already, but sure here is a sample implementation that it quite literally just what I outlined

import heapq
import math

class MinHeap:
  def __init__(self):
    self.data = []

  def push(self, value):
    heapq.heappush(self.data, value)

  def pop(self):
    return heapq.heappop(self.data)

  def top(self):
    return self.data[0]

  def __len__(self):
    return len(self.data)

class MaxHeap:
  def __init__(self):
    self.data = []

  def push(self, value):
    heapq.heappush(self.data, -value)

  def pop(self):
    return -heapq.heappop(self.data)

  def top(self):
    return -self.data[0]

  def __len__(self):
    return len(self.data)

class PercentileTracker:
  def __init__(self, percentile):
    self.percentile = percentile
    self.small = MaxHeap()
    self.large = MinHeap()

  def push(self, value):
    # Add to appropriate place
    if len(self.small) and value <= self.small.top():
      self.small.push(value)
    else:
      self.large.push(value)

    # Rebalance
    total = len(self.large) + len(self.small)
    k = math.ceil(self.percentile * total)
    while len(self.small) >= k:
      self.large.push(self.small.pop())
    while len(self.small) < k - 1:
      self.small.push(self.large.pop())

  def value_at_percentile(self):
    return self.large.top()

# Test code to check against brute force sorting to get kth order statistic
percentile = 0.618
pt = PercentileTracker(percentile)
data = [1, 3, 2, 5, -7, 1, 2, 3, 4, 1, 7]
reference = []
for value in data:
  reference.append(value)
  reference.sort()

  pt.push(value)

  k = math.ceil(percentile * len(reference))
  assert reference[k - 1] == pt.value_at_percentile()
  print(reference[k - 1], pt.value_at_percentile())
dapper mountain
#

do you have any idea why the first solution is giving about 3000 ms?
it just taking the last item in the array with pop() and adding that to index 0
it's not doing calculations as other solutions like #2 and #3. i mean it seems like, it doing less calculations than others but no
i guess the time complexity of #2 and #3 is O(n) but what #1 is?
is it giving such high ms because it uses build-in functions or something?
like insert and pop
(i don't know much about time complexity)

agile sundial
#

the first one is really bad compared to the others since to insert an element to the front of a list, you have to shift all the other elements to the right

#

and you do this every rotation, so it's quadratic

#

the others are just linear

dapper mountain
tight patio
#

what does this mean

unknown.png
#

the cambridge definiton of abstraction is "the situation in which a subject is very general and not based on real situations"

#

how does it relate to algorithmics

slender sandal
#

It's my take at it, but maybe it means that you don't have to know exactly how and what the algorithm does but you know its purpose. You may know about merge sort and not know about what it does or how it works, but you know its purpose is sorting

fiery cosmos
# tight patio how does it relate to algorithmics

A lot of times if you can abstract out the idea of an algorithm you can make it more general and more powerful. Like an algorithm that solves a maze can be abstracted into a more general graph search algorithm.

tight patio
#

ooh that make sense
thx u both for providing the examples as well
it helps a lot for understanding

#

also merge sort and graph search algorithms are "algorithm designs patterns" right?
u can use these general ideas to complex problems

is that what mean here?

unknown.png
fiery cosmos
#

I'm haven't really heard that term "algorithm designs patterns" before pithink Merge sort is a particular algorithm that can sort lists, and there are multiple types of graph search algorithms. But that text is right that getting a high level overview (aka abstract overview) of a problem can help you solve other problems.

tight patio
#

ooh ic
i just started learning a subject called "Algorithmics" in school

im making sure that i understand theory

slender sandal
#

In programming, abstraction is to take something as a given and just use it. You know that merge sort is a sorting algorithm, use it for this purpose. Abstraction hides the complexity of code under a function, a class or anything else.

young eagle
tight patio
slender sandal
#

Variables are an abstraction of how data is stored in memory. Instead of worrying about the memory and addresses of data stored in it, you can use the name of your variable to access and manipulate your data.

#

Data types is an abstraction of operators done upon the data in memory. They restrict functionalities data can have

tight patio
#

i see

fiery cosmos
tight patio
#

i guess another importance of these abstractions is you can reuse them
there are like patterns

#

like you dont have reinvent the wheel

#

i think this is good representation of abstraction

unknown.png
foggy roost
#

hay guys, someone in here

fiery cosmos
#

maybe discre3Lurk

foggy roost
#

well, i have a little

#

i dont really understand this import the twitter package and run help() on it

fiery cosmos
foggy roost
#

i did but i had no reply

foggy roost
fiery cosmos
#

Huh?

dire cipher
#

Hey guys, so i have a problem regarding this topic. create a program to find minimum steps to get all treasures, we know how many treasures are there in the maze and starting point depends from input. let me elaborate on my thought process. also i'm using C but if you want to explain in any language, then no problem.

P=Path
T=Treasure
W=Wall
    12345
   ------
1 | PPTPT
2 | WPWWW
3 | TPPWT
4 | PPPPP
5 | TWWWP

the starting position will depend on the input, but lets say we start at (1,1) then the minimum steps to collect all treasures is 18 (can use same path)by going right 4 steps to collect 2 treasures, then go left 3 steps then go down 2 steps, go left 1 step, go down 2 steps, go up 1 step, go right 4 steps and finally up ending at (3,5)

at first i was thinking about DFS and to optimize the DFS by checking whether i have explore a coordinate or no.

char maze[5][5];
bool wasExplored[5][5]={false};
void exploreMaze(int x,int y){
  (if x<1 || x>5 || y<1 || y>5 || wasExplored[x][y]==true) return;
  wasExplored[x][y]=true;
  exploreMaze(x-1,y);
  exploreMaze(x+1,y);
  exploreMaze(x,y-1);
  exploreMaze(x,y+1);
}```

but i realize that i cant optimize it by simply checking like that because i might have a faster solution. i consider to change array type from bool to int, but if i found a better way to get into a certain coordinate, then i would have to explore it all over again right?

also i still dont get when or how should i start counting the steps, my current solution is like this

```c
char maze[5][5];
int wasExplored[5][5]={0};
int exploreMaze(int x,int y){
  (if x<1 || x>5 || y<1 || y>5 ,maze[x][y]=='W') return;
  int step=0;
  if(maze[x][y]=='T') step=1;
    
    if(exploreMaze(x-1,y)>0)step+=wasExplored[x-1][y]+1;
    if(exploreMaze(x,y-1)>0)step+=wasExplored[x][y-1]+1;
    if(exploreMaze(x+1,y)>0)step+=wasExplored[x+1][y]+1;
    if(exploreMaze(x,y+1)>0)step+=wasExplored[x][y+1]+1;
  
wasExplored[x][y]=step;
return step;
}```
#

to elaborate more why there's if condition before increment the step, is that we only start counting steps if we found a treasure.

so, that is my current solution, but i couldnt grasp the idea how to compare between 2 paths. also since we know how many treasures are there, i think that we could make a condition to stop if we have found all treasures. but that would mean if i visited the same treasure via 2 routes, that would be a miscalculation?

i heard about BFS algorithm to find exit but i cant imagine it being use for this problem.

fiery cosmos
daring light
#

what is the time complexity for mergesort? one book says that it is O(n lg(n)), while another video says its \theta(n lg(n))

dire cipher
agile sundial
#

it's technically not the same

daring light
agile sundial
#

to be precise, the average case is \Theta(n lg n)

quasi sorrel
#

is there a nice way to get the kth largest element from a max heap?

#

for example if i have the following max heap [18,17,14,16,9,11,13,10,15,3,8,2,6,5,12,1,7,4] and i wanted to find the 7th largest element that would be 12

#

i first thought about sorta finding the general area the kth largest element would be then making another max heap with the elements in this range but i realized that it doesnt really work out in the case above

haughty mountain
quasi sorrel
#

i thought about it when i was dealing with finding the second largest number in [3,1,2] and [3,2,1] both should return 2

haughty mountain
#

merge sort is always n log n

#

i.e. both O(n log n) and Ω(n log n), so Θ(n log n)

haughty mountain
quasi sorrel
#

is there a nice way to find the kth largest element from a max heap if i know what k is before hand?

haughty mountain
#

assuming you don't have to be able to remove elements

#

if you need removing elements you need something fancier

quasi sorrel
#

i was trying for a solution with a better space complexity like working directly with a list

haughty mountain
#

better space complexity than O(n)?

quasi sorrel
#

im not that good with guessing space complexity

haughty mountain
#

heaps are just stored as lists

quasi sorrel
#

wouldnt a object oriented approach use more space?

haughty mountain
#

how is it object oriented?

quasi sorrel
#

your solutions uses classes doesnt it?

haughty mountain
#

it uses one object per heap, the overhead is miniscule

#

the actual data inside them is just a list

#

if it was a list containing classes then maybe overhead might start to matter

#

but this is just classes that holds large chunks of data and provides a nice interface

#

you could inline the logic, but it will be super messy

quasi sorrel
#

when you pop in your max heap part is that removing the largest element or the smallest? @haughty mountain

haughty mountain
#

popping from a max heap removes the maximum element in the heap

quasi sorrel
#

i see

#

so it looks like your algorithm takes about logn time to push or maybe im wrong

#

also why are the values going to the maxheap being multiplied by -1

haughty mountain
haughty mountain
halcyon plankBOT
#

Hey @open moth!

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

fiery cosmos
#

Guys, what do you think is complexity, BigO of this algorithm?

#

In the video, instructor said "And the external loop and internal loop combined also spend at most linear time of iterations. Because they change variable currentRefill and it changes at most linear number of times. "

#

"spend at most linear time of iterations" part confuses me

#

and also "and it changes at most linear number of times."

#

so linear time is O(n)

#

so because these both loops, internal and external depend on same value which is increased linearly, complexity is O(n)?

raven prism
#

It's O(n), but it's difficult to explain without just repeating what the instructor said. Because the loops share the same looping variable, the combined number of times that you go back to the beginning of either loop is n. Or in other words, every iteration through the inner loop reduces the number of iterations you need to perform through the outer loop by 1.

fiery cosmos
fiery cosmos
#

Also, to check this - safe move is a move that is done instead of first other move in optimal solution - what is important is that taking safe move doesn't influence optimal solution, so the expected outcome is same

quasi sorrel
#

is there a way to sum all the elements of an avl tree/bst in logn time?

haughty mountain
#

then you have the sum in O(1)

fiery cosmos
#

Basically, this algorithm will consider every possible partition of the children into groups
I am not sure what does that mean, can someone explain?

fiery cosmos
#

So basically if I have ages of children 1,2, 3, then there are partitions: { {1}, {2}, {3} }, { {1, 2}, {3} }, { {1, 3}, {2} }, { {1}, {2, 3} }, { {1, 2, 3} } - is by word "partition" that meant?

haughty mountain
#

presumable yes, this would be a brute force thing where you consider any possible grouping, which are those 5

#

this problem can be solved greedily: the lowest age can't be paired with anyone younger, so the best we can do is to just remove the youngest and hope we can get the year above for free as well, repeat with the new youngest

fiery cosmos
dark aurora
#

This really weird thing is happening and i don't know why?

#

So i want to add a[i]+a[i+1] from either side and in these two seemingly same cases, only one of them works

#

here is the code for the case that doesn't

# 
dis = [[0,0]*(8)]
for i in range(1, 7):
    j = -(i+1)
    dis[i][0] = dis[i-1][0]+1
    dis[j][1] = dis[j+1][1]+1

print(dis)```
#

and this one does, i am seriously so confused?!

# 
dis = [[0,0], [0,0], [0,0], [0,0], [0,0], [0,0], [0,0], [0,0]]
for i in range(1, 7):
    j = -(i+1)
    dis[i][0] = dis[i-1][0]+1
    dis[j][1] = dis[j+1][1]+1

print(dis)```
ivory yacht
#

The problem is that multiplying a list doesn't create copies of the items in the list, it just gives you a list containing the same item multiple times. So in the first code (I think you mean [[0, 0]] * 8), there's only one [0, 0] list in existence. When you modify it, that change is visible from all the indexes.

dark aurora
#

I was just so confusedd

agile sundial
#

?

fiery cosmos
#

@cedar cove delete your stuff 😅

young merlin
#

Lets say I have an array A. I want to make an array B, with elements in A from i:j. (less than O(n) time)
can it be done? is there a function to directly put in elements in A in a given range to B?

haughty mountain
#

other languages solve this by having a span or slice type that acts as a wrapper and just indexes into the original array

fiery cosmos
#

what's the difference between using an OrderedDict and a list of tuples?
like orderedDict of values {1: "I", 5: "V"} vs list like [(1, "I"), (5, "V")]

#

both can iterate through the values in order, which is what I want/ought to do for this problem

fiery cosmos
#

But dicts/lists have different lookup times and other behaviors as you may know

#

If you only need iteration then lists may be fine

agile sundial
#

OrderedDict also has methods to change the order, where normal dicts don't

young merlin
haughty mountain
young merlin
#

if not in python, is it possible in other languages

young merlin
haughty mountain
#

e.g. this does what you want but is linear time because it copies stuff

B = A[i:j+1]
young merlin
#

ah

#

got it

#

thanks!

#

because its still looping through

#

its still the same time

#

as it would have been to use a for loop

young merlin
haughty mountain
#

C++20 has std::span for this kind of thing

young merlin
#

okay

haughty mountain
#

similar to std::string_view but more general

young merlin
#

thx

#

ill try it out then.

haughty mountain
#

you could always write your own Span type in python

#

that delegates indexing and slicing to the underlying list

fiery cosmos
fiery cosmos
#

what do you mean by change the order? like more than just reversing it?

#

how is that done?

strong ledge
#

ordereddict remembers the order that the items were inserted in

fiery cosmos
#

how is OrderedDict implemented? oh it's doubly linked list

strong ledge
#

!e

from collections import OrderedDict
ord_dict = OrderedDict().fromkeys("abcdefg")
print(ord_dict)

ord_dict.popitem()
print("popping last item")
print(ord_dict)

ord_dict.popitem(last = False)
print("pop first item")
print(ord_dict)
halcyon plankBOT
#

@strong ledge :white_check_mark: Your eval job has completed with return code 0.

001 | OrderedDict([('a', None), ('b', None), ('c', None), ('d', None), ('e', None), ('f', None), ('g', None)])
002 | popping last item
003 | OrderedDict([('a', None), ('b', None), ('c', None), ('d', None), ('e', None), ('f', None)])
004 | pop first item
005 | OrderedDict([('b', None), ('c', None), ('d', None), ('e', None), ('f', None)])
strong ledge
#

the purpose is so that you can iterate over the keys in a certain order

fiery cosmos
#

I'm confused so OrderedDict has the complexity of Doubly-linked list?

#

because apparently that's how it's implemented

#

so even tho it has "dict" in the name, it's not actually a dict/hashmap

#

that's confusing

agile sundial
#

it also has O(1) lookup

strong ledge
halcyon plankBOT
#

Lib/collections/__init__.py line 78

class OrderedDict(dict):```
strong ledge
#

feel free to look at the implementation : p

#

but yes, setitem, popitem, and move_to_end are constant time

fiery cosmos
strong ledge
agile sundial
fiery cosmos
#

it acts like a doubly linked list at times and at other times like a normal dict?

#

interesting

strong ledge
#

argh

strong ledge
halcyon plankBOT
#

@strong ledge :white_check_mark: Your eval job has completed with return code 0.

001 | 100
002 | 1
003 | 100
fiery cosmos
#

?

strong ledge
#

@fiery cosmos it is a "lookup table", implemented internally with a dict + doubly linked list

fiery cosmos
#

oh I see

strong ledge
halcyon plankBOT
#

Lib/collections/__init__.py lines 106 to 112

def __setitem__(self, key, value,
                dict_setitem=dict.__setitem__, proxy=_proxy, Link=_Link):
    'od.__setitem__(i, y) <==> od[i]=y'
    # Setting a new item creates a new link at the end of the linked list,
    # and the inherited dictionary is updated with the new key/value pair.
    if key not in self:
        self.__map[key] = link = Link()```
strong ledge
#

this is the "magic" i tihnk

fiery cosmos
#

I dont understand

strong ledge
#

they still keep a mapping of key to doubly linked list node

#

in order to do O(1) lookup

#

internally they still store things in a normal dict, which is the self.__map variable

fiery cosmos
#

it is wasting memory?

strong ledge
#

for fast lookup

#

i dunno, if it's good enough for CPython it's good enough for me 😅 if you only used doubly linked list, how else would you achieve O(1) lookup..

fiery cosmos
#

so actually it's better to use a list of tuples when you just want to iterate in order

#

actually the reason why I didnt want to do that is just because typing out the list of tuples is longer

#

but I see that it actually saves memory

strong ledge
pine sapphire
#

don't normal dicts use an array instead of a linked list?

#

how is popitem/del O(1) in a dense array

agile sundial
#

it doesn't resize after a del, it just marks the spot "dummy", which can be turned into an active key on another insertion

pine sapphire
#

wouldn't that make the next popitem or iteration slower?

#

surely it can't reuse the spot and maintain insertion order?

agile sundial
#

this is all explained in dictobject.c

halcyon plankBOT
#

Objects/dictobject.c line 88

Preserving insertion order```
pine sapphire
#

I'll take a look thanks

zenith berry
#

How do defaultdicts work from the collections module? I can't seem to understand the KeyError thing, because I get them as well...

#

you can format python code by doing:
```python

my code here

```

so, the code will look like:

# my code here
halcyon plankBOT
#

Hey @tired sapphire!

It looks like you tried to attach file type(s) that we do not allow (.pdf). We currently allow the following file types: .gif, .jpg, .jpeg, .mov, .mp4, .mpg, .png, .mp3, .wav, .ogg, .webm, .webp, .flac, .m4a, .csv, .json.

Feel free to ask in #community-meta if you think this is a mistake.

tired sapphire
#

Please help me to resolve this problem

unknown.png unknown.png unknown.png unknown.png
rigid steeple
#

Might anyone know if there is an advantage to using linked lists in Python? I know it's advantageous in languages such as Java due to how their Arrays and ArrayLists are built, but how about in Python?

rustic salmon
#

they have similar memory usage. the main performance difference is with time complexity

rigid steeple
#

Ah gotcha, do we know the time difference between those or is that too hard to calculate?

rustic salmon
#

linked lists have constant time complexity

stray fractal
#

in what field?

#

if append yes

#

if search no

#

if delete no

#

if sort definitely not

rustic salmon
#

ye i meant in append

fiery cosmos
#

Which is great for things like queues (collections.deque) since you can append or remove from both sides in constant time ducky_party

#

Though I think queues can also be implemented in a circular buffer which uses an underlying array rather than a doubly linked list pithink

vocal gorge
#

Linked lists aren't commonly used in practice because they are slow and memory-hungry in absolute terms (rather than asymptotically)

#

a naively implemented linked list needs one (for single-) or two pointers (for doubly linked) for each element. That's 8/16 bytes of overhead for each element. If your element is even 8 bytes, that's kinda massive.

#

Similarly, to iterate over a linked list requires following a pointer for each next element. That's O(1), but slow compared to just looking into an array, and has no cache locality.

#

There are smart hybrid implementations, though. Say, collections.deque is implemented as a linked list of arrays. That way, there's only a pointer to the next node every X elements, rather than every one element, and so the memory and runtime overheads are X times smaller.

vocal gorge
jolly mortar
fiery cosmos
#

There are basically no modern languages that aren't just using vectors for many of these things

#

things like rust have really weird stuff going on in their DS/Collections and some of them are really really innovative, like the btreemap that more or less outperforms the hashmap in the collections because of modern caches

versed tulip
#

Hello

#

Whats poppin

#

1

#

💯

#

Hey

dire trench
versed tulip
#

Hello mate

#

I need the vc role

#

Where

#

Can i get the role?

#

Does anyone knows

rustic salmon
keen hearth
fluid sand
#

Can anyone help me solve these

IMG_20220214_193654.jpg IMG_20220214_193639.jpg IMG_20220214_193621.jpg
urban creek
#

hello, I have a question about divide and conquer method/ recursion in min max
I have done this code passing whole array each time but, I want to do it by passing half array each time. How to do it?

halcyon plankBOT
urban creek
fiery cosmos
#

However, the way you're doing it by passing indexes around is technically more efficient because slicing is an O(N) operation since it makes a shallow copy of the sliced portion of the list ducky_tube

bright geyser
#

Hi, I am working on a subset sum problem, which states that "Given an array of non-negative integers and a value sum, determine if there is a subset of the given set with sum equal to given sum." I have to solve this problem in constant complexity 0(1) in iterative method.
``def get_sum(arrays, target):
result = [False]*(target+1)
# initializing with 1 as sum 0 is always possible
result[0] = True
# loop to go through every element of the arrays
for ele in arrays:
# to change the value o all possible sum values to True
for j in range(target, ele - 1, -1):
if result[j - ele]:
result[j] = True

# If target is possible return True else False
return result[target]

Driver code

arrays = [2, 3, 5]
target = 17

if get_sum(arrays, target):
print("YES")
else:
print("NO")``

Just wanted to know that this is the correct method for the constant space 0(1) using iterative method. Can anyone please help me out.

charred zodiac
ivory yacht
#

I guess the question is constant space, not time - so you use the same amount of memory regardless of the size of the input array.

charred zodiac
mossy forge
#

hey I have been trying to create an algo that uses divide and conquer to find the longest contiguous increasing subarray

#

but I'm not sure how to create the crossarray function that finds the longest chain in the middle

fiery cosmos
#

Guys, do you have any advice with regards to learning algorithms? How to learn them as much as efficiently as possible?

#

I have two idea: break what I don't understand in parts and then learn about particular part

#

when I finish with particular material from course, book or whatever, then I should write about what I learnt in order to check whether I understood it

#

Any other idea?

lament totem
#

Start with the basics, having a good understanding of statistics and linear algebra goes a long way

rustic salmon
#

^

#

and practice them

#

big o notation also

#

and notes are very helpful to look back on later

lament totem
#

yeah learn about the theoretically, think about what usecases they have, the pros, the cons, and maybe try em out for an example problem

rustic salmon
#

don’t be ashamed

fiery cosmos
rustic salmon
#

you don’t memorize programming syntax, etc you memorize the logic and principles

lament totem
#

oh I thought you meant "any adive with regards to learning algorithms"

#

So I was giving advice on understanding ML/AI

rustic salmon
#

lol

lament totem
#

yeah ignore that

rustic salmon
#

Linear algebra is the basis for some graph algorithms

fiery cosmos
#

yeah, I mean about a & ds that are used in interviews

lament totem
#

What really helped me after getting to know the basics, is practicing a lot with codewars/leetcode/hackerrank @fiery cosmos

fiery cosmos
#

I see, thanks

hexed osprey
supple scroll
#

How much python should I know before starting with DSA?

hoary kayak
haughty mountain
#

Yeah, DS&A is really about learning the concepts. Python would just be one way of encoding the concepts into instructions a computer can make sense of

#

The concepts generalize across languages

rustic salmon
#

^

#

you can use DSA in pretty much all langs

supple scroll
#

Thanks guys!

inland prawn
#

Detect text inside the circle?
I am trying to detect the text in the circle, i have two pictures one is plain and one has some circle on it i need to extract only text which has a circle around it. i have tried EasyORC, Tesseract already but did not get actual result also i have tried OPENCV too but in open cv the accuracy is very low because of the picture red background is there anyone who can help or suggest to me how i achieve these text under circle I am also attaching some pictures below.

Picture: My Result

circles_black_dot.png
tight patio
#

is this going to work

unknown.png
fiery cosmos
fiery cosmos
tight patio
#

hmm

#

didnt think of that

tight patio
fiery cosmos
#

Is this for a test pithink

tight patio
#

nope
hw

#

also me trying latex

fiery cosmos
#

Looks better. Do you really need the r variable?

tight patio
#

oh yeah u can do it without r as well

#

thx

#

btw do u use return keyword in pseudocode

fiery cosmos
#

return thevalue 🤷‍♂️

#

pseudocode has no hard keywords pithink

tight patio
#

ig
it is anyhting readable

#

the examples ive seen use print

opal oriole
#

It will always return False.

#

(except for when N = 1)

tight patio
#

nvm

fiery cosmos
#

Hey guys can you tell me good resources to learn data structures and algorithms. I have a decent understanding of python. I just finished OOP.

opal oriole
tight patio
#

lemme find a fix

tight patio
#

i recreate the alogrithm in python

# 
N = 9
r = True
for i in range(2, N):
    print(i)
    if N % i == 0:
        r=False
print(r)
opal oriole
#

2 to N can be read as [2, N].

#

Which is what I did.

tight patio
#

ooh misuderstand whay u sai

#

d

#

my abd

opal oriole
#

By default python subtracts 1. Because it's a programming language and it comes from the convention in older languages of doing i = 0 ... i < N

tight patio
# 
N = 2
r = True
for i in range(2, N):
    print(i)
    if N == 2:
        r=True
        break
    if N % i == 0:
        r=False
print(r)

ez fix

tight patio
opal oriole
#

Translating your latex to Python is something like for i in range(2, N + 1):

# 
>>> N = 10
>>> for i in range(2, N + 1):
...     print(i)
... 
2
3
4
5
6
7
8
9
10
#

2 to N -> 2 to 10

#

[2, 10]

tight patio
opal oriole
#

You can just do 2 to N - 1

#

Or since this is whatever made up language you could do something like i <- [2, N)

#

That's pretty well understood as exlcusive.

tight patio
#

thx for the clarification

opal oriole
#

You really want to help people avoid off-by-one errors and stuff like that when reading your pseudocode.

tight patio
#

ik that list index starts with 0

#

do u mean that

opal oriole
#

The python range range(N) gives values from 0 to N-1.

tight patio
#

or the fact that
when u do

for i in range(2,4):
    print(i)

it only print 2 and 3

tight patio
tight patio
#

is this pseudocode ambiguous

unknown.png
#

add the ith letter to r
if it was in python i would do i-1 letter

#

but ig in this pseudocode
it is clear enough

fiery cosmos
#

How about subtract 1 from i? Remove makes it sound like a list or something

tight patio
#

oh yeah thx for the suggestion

rocky temple
#

I am trying to print a pattern ```
*
**

**** and this is the code which I hav written
for row in range(1,6):

for col in row:
    print('*')
'/n'``` I am getting error ```for col in row:

TypeError: 'int' object is not iterable``` Can someone help me out what am I doing wrong

dire cipher
haughty mountain
rocky temple
haughty mountain
#

or if you really want to replicate the java code verbatim

for row in range(1, 5):
  for col in range(row):
    print('*', end='')
  print()
rocky temple
haughty mountain
rocky temple
haughty mountain
#

it loops row times

rocky temple
# haughty mountain wdym? `col` in the loop goes `0, 1, ..., row-1`

I am so sorry, for asking silly questions, but how are we getting to know that col is going 0 ..1.. row-1 .. because like in row we have specified that for row in range(1,5) that row is going from 1 ..6 but similarly in col we havent specified anything.. in col we have specified that whatever the value of row is . it is the same value of column

haughty mountain
rocky temple
haughty mountain
#

I would much recommend the first version I posted, messing with end in print is pretty hacky

#

though the second version might be good as a learning exercise, I guess

rocky temple
haughty mountain
#

np

fiery cosmos
#

now for my question:

for col in zip(*board):
    unit = [i for i in unit if i != '.']

what is zip(*board)

#

why does the above code work

#

it seems to give the column of the 2D array/list

#

like
[1
2
3
4]

#

then
[-- 2
-- 5
-- 6
-- 8
]

#

for the second column

#

when I try to print out the zip(*board) in Python, it just returns the whole list

#

but I know the code works (I copied it 🙂 )

#

oh wait, it turns every column into a row, and vise versa?

#

nvm I thought it printed the copy of the list

haughty mountain
fiery cosmos
#

I thought zip command was for combining two values or lists

#

like zip(a,b) = [[a0,b0), etc] ]

haughty mountain
#

it combines however many arguments you give, in this case you give a bunch of lists as arguments

#

if board is [list1, list2, ...] then zip(*board) expands to zip(list1, list2, ...)

fiery cosmos
#

what is *

#

do the lists need to be of the same size? (Does board need to be a square or can it be a rectangle?)
how can I can do this without zip? I mean how can I iterate through the columns one by one
like this?

for col in range(board[0]):
  for row in range(board):
wanton shell
#

hi guys I have a large 3d scene with roughly 2000 stars/orbiting planets and am looking to use an octree spatial query structure to improve performance. I am using django with three js on the front end; from my understanding I cannot import modules/libraries and can only import within html tags linking to a hosted text doc. The following library looks great, however I do not see a relevant html tag https://github.com/vanruesc/sparse-octree. Am I correct in my understanding, that I need an html tag? Is there a way to create one? Alternatively, is there another appropriate library that does have an appropriate html tag? Thanks in advance.

haughty mountain
haughty mountain
haughty mountain
naive grove
fiery cosmos
haughty mountain
fiery cosmos
#

oh yea sorry I did that

fervent saddle
#

In the 8 queens algorithm where you use permutations and pruning, you build up an array which starts out as being filled with empty space, right? And when you backtrack, you’ll reset the positions to being empty, right?

fervent saddle
#

So like:```
1*******
13******
135*****

#

And then eventually you backtrack to:```
2*******
24******
241*****

#

Is that how it works?

halcyon plankBOT
#

Hey @patent ore!

It looks like you tried to attach file type(s) that we do not allow (.pdf). We currently allow the following file types: .gif, .jpg, .jpeg, .mov, .mp4, .mpg, .png, .mp3, .wav, .ogg, .webm, .webp, .flac, .m4a, .csv, .json.

Feel free to ask in #community-meta if you think this is a mistake.

glass river
#

im learning linked lists and i notice it uses yield to show the list

#

how does yield work

fiery cosmos
#

a yield in a function makes it a generator function so it can be put in a for loop like for yielded_value in yielding_func(): ...

#

yield is kinda like return but the state of the variables in the function are remembered and you can resume it to, for example, get the next loop value

#

!e py def yields123(): for i in range(1, 4): yield i for yielded_value in yields123(): print(yielded_value)

halcyon plankBOT
#

@fiery cosmos :white_check_mark: Your eval job has completed with return code 0.

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

the for loop extracts all the yielded things from the yields123 generator

bronze vigil
#

It's nothing but the return function

fiery cosmos
#

yields123 effectively returns 3 values (1, 2, and 3) when you call and loop over it

bronze vigil
#

So?

fiery cosmos
#

but, importantly, the internal state of the function is remembered between each of those 1, 2, and 3

#

which isn't the case with a normal function call

bronze vigil
#

Yo I get it I get it

fiery cosmos
bronze vigil
#

Okay I think it returns all the three integers at once after iteration.

fiery cosmos
#

I need help with github can anyone help me out? ;-;

uncut gale
#

Hey, I have a question about Big O. If I have a function with time complexity = x^2 + 2x + 3 so f = O(x^2) is it also true that f = O(2^x)

jolly mortar
uncut gale
fiery cosmos
#

cause big O is an upper bound (though people often speak of it like a tight bound) ducky_ninja

fiery cosmos
#

j=hi

#

hi

#

Ban me pls

#

<@&831776746206265384>

#

@fiery cosmoss

#

ban me

#

fix errors

#

pls

austere sparrow
#

!mute 722821122743205960 666y seems like you're here just to spam

halcyon plankBOT
#

:incoming_envelope: :ok_hand: applied mute to @fiery cosmos until <t:22661973327:f> (665 years and 11 months).

stiff wing
#

Hey guys, can you help me?

halcyon plankBOT
#

Hey @stiff wing!

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

stiff wing
stiff wing
hoary kayak
#

Hi guys, if my algorithm is O(n/2) do I skip the 1/2 part when writing it as an answer?

austere sparrow
hoary kayak
fiery cosmos
#

hi

rocky temple
#

In my PyCharm I want my file to be formatted automatically like when we code in Intell ij it formats the file autmatically.How can I do that, can someone please tell me

shut breach
weak tulip
#

How sould I learn data stuctures for FREE??

opal oriole
#

Plus some book's table of contents (as a guide for which order to learn them in).

#

Also see pins.

mental crystal
#

Hi guys. Can someone help me debug a basic merge sort algorithm? I have been sitting here for ages, and i think it's a small detail

# 
def Merge(A,i,m,j): #Merging SORTED arrays
    #if len(A) == 1: return A
    L = A[:m]
    R = A[m:]
    i = j = o = 0

    while i < len(L) and j < len(R):
        if L[i] < R[j]:
            A[o] = L[i]
            i += 1
        else:
            A[o] = R[j]
            j += 1
        o += 1

    while i < len(L):
        A[o] = L[i]
        i += 1
        o += 1

    while j < len(R):
        A[o] = R[j]
        j += 1
        o += 1


def MergeSort(A,i,j):
    if i < j:
        m = (i+j)//2
        MergeSort(A,i,m)
        MergeSort(A,m+1,j)
        Merge(A,i,m,j)

newarray = [16,31,1,36,47,50,42,12,7,4,51,28,45,25,18,33]
j = len(newarray)-1
MergeSort(newarray,0,j)
print(newarray)
#

Output: [1, 4, 12, 7, 16, 31, 33, 36, 42, 45, 25, 18, 47, 50, 51, 28]

#

Expected output: [1, 4, 7, 12, 16, 18, 25, 28, 31, 33, 36, 42, 45, 47, 50, 51]

celest quest
#

anyone got a turotial or something that explains how pathfinding works, i want to make a program that finds the best way between x amount of points, something that explains pathfinding would be helpful

opal oriole
austere sparrow
#

!e
Basically:

def f(x):
    x = 5
    print("x =", x)

y = 10
f(y)
print("y =", y)
halcyon plankBOT
#

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

001 | x = 5
002 | y = 10
mental crystal
celest quest
shut breach
#

this channel is for questions about algorithms and data structures, you could ask your question in a help channel: #❓｜how-to-get-help

kindred oracle
#

sry

ivory parrot
#

i have a question

#

what does @ does

haughty mountain
#

you can implement if for a class by implementing __matmul__

ivory parrot
#

Can you give me a example how to use it

shut breach
ivory parrot
#

ok sry

glass river
#

when you solve problems how do you create well designed code

#

or what makes certain codes well designed

fervent saddle
# 
def find_positions(positions, diags1, diags2, l, r):
    global x
    
    if l == r:
        print(diags1, diags2, positions, " - - - - - ", sep="\n")
        x += 1
        return
    
    for col in range(l, r):
        d1 = col + positions[l]
        d2 = len(positions) - 1 - positions[l] + col
        if not (diags1[d1] or diags2[d2]):
            diags1[d1] = True
            diags2[d2] = True
            positions[l], positions[col] = positions[col], positions[l]
            find_positions(positions, diags1, diags2, l + 1, r)
            diags1[d1] = False
            diags2[d2] = False
            positions[l], positions[col] = positions[col], positions[l] # backtrack

x = 0
positions = list(range(8)) # 8 queens
r = len(positions)
diags1 = [False] * ((r * 2) - 1) # downwards from left to right
diags2 = diags1.copy() # upwards from left to right
find_positions(positions, diags1, diags2, 0, r)
print(x) # this prints 0

This is 8 queens but it doesn't work, it prints 0

#

Why is it doing this?

fervent saddle
# 
def diag(x, y, queens):
    return (x + y, queens - 1 - y + x)

def check_valid(diags1, diags2):
    if all(d < 2 for d in diags1) and all(d < 2 for d in diags2):
        return True
    return False

def find_positions(positions, l, r):
    global result
    
    if l == r:
        diags1 = [0] * ((r * 2) - 1)
        diags2 = diags1.copy()
        for x, y in enumerate(positions):
            d1, d2 = diag(x, y, len(positions))
            diags1[d1] += 1
            diags2[d2] += 1
        result += check_valid(diags1, diags2)
        return
    
    for i in range(l, r):
        positions[l], positions[i] = positions[i], positions[l]
        find_positions(positions, l + 1, r)
        positions[l], positions[i] = positions[i], positions[l] # backtrack

result = 0
positions = list(range(8)) # 8 queens
r = len(positions)
find_positions(positions, 0, r)
print(result)

This is how I solved it, but it's not very good

#

It fully generates all 40,320 permutations

#

I wanted to do it the way which prunes them and only generates 5,508, like what the 8 queens problem wikipedia page mentions

fervent saddle
# 
def diag(x, y, queens):
    return (x + y, queens - 1 - y + x)

def check_valid(diags1, diags2):
    if all(d < 2 for d in diags1) and all(d < 2 for d in diags2):
        return True
    return False

def find_positions(positions, l, r):
    global result
    
    if l == r:
        result += 1
        return
    
    for i in range(l, r):
        positions[l], positions[i] = positions[i], positions[l]
        diags1 = [0] * ((r * 2) - 1)
        diags2 = diags1.copy()
        for n in range(l + 1):
            d1, d2 = diag(n, positions[n], len(positions))
            diags1[d1] += 1
            diags2[d2] += 1
        if check_valid(diags1, diags2):
            find_positions(positions, l + 1, r)
        positions[l], positions[i] = positions[i], positions[l] # backtrack

result = 0
positions = list(range(8)) # 8 queens
r = len(positions)
find_positions(positions, 0, r)
print(result)

How to do this without needing to rebuild diags1 and diags2 every time? Can it be done where you only need to update the specific diagonals which were changed?

fervent saddle
fiery cosmos
#

Yes retry

fervent saddle
# 
def diag(x, y, queens):
    return (x + y, queens - 1 - y + x)

def check_valid(diags1, diags2):
    if all(d < 2 for d in diags1) and all(d < 2 for d in diags2):
        return True
    return False

def find_positions(positions, diags1, diags2, l, r):
    global result
    
    if l == r:
        result += 1
        return
    
    for i in range(l, r):
        positions[l], positions[i] = positions[i], positions[l]
        d1, d2 = diag(i, positions[i], len(positions))
        diags1[d1] += 1
        diags2[d2] += 1
        if diags1[d1] < 2 and diags2[d2] < 2:
            find_positions(positions, diags1, diags2, l + 1, r)
        diags1[d1] -= 1
        diags2[d2] -= 1
        positions[l], positions[i] = positions[i], positions[l] # backtrack

result = 0
positions = list(range(8)) # 8 queens
diags1 = [0] * ((len(positions) * 2) - 1)
diags2 = diags1.copy()
r = len(positions)
find_positions(positions, diags1, diags2, 0, r)
print(result) # it still prints 0

It still doesn’t work

fiery cosmos
#

crazy how many solutions are possible for this problem

#

I dont know so much about Python even after years of using it :_:

proper sail
#

ayo mates,tell me the best platform to learn python

sick wyvern
#

nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sort_lambda = sorted(nums, key = lambda x: x%2)
print(sort_lambda)

how is key getting any value? how is this lambda function getting any value

daring light
#

anyone here know how to solve a recursion tree with a square root?

austere sparrow
sick wyvern
#

yes

austere sparrow
# sick wyvern yes

The sorted function will just call the key function on each of the items

sick wyvern
#

but where is the key function?

austere sparrow
# sick wyvern but where is the key function?

lambda is just a shorthand for creating a function. You could rewrite your snippet like this:

nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

def my_key(x):
    return x % 2

sort_lambda = sorted(nums, key = my_key)
print(sort_lambda)
sick wyvern
austere sparrow
sick wyvern
#

ohhh thank you

austere sparrow
# sick wyvern ohhh thank you

!e
For example, this is how you could implement bubble sort accepting a key function:

def bubble_sort(a_list, key):
    swapped = True
    while swapped:
        swapped = False
        for i in range(len(a_list) - 1):
            if key(a_list[i]) < key(a_list[i + 1]):
                a_list[i], a_list[i + 1] = a_list[i + 1], a_list[i]
                swapped = True

nums = [6, 7, 1, 3, 4, 5, 2]
bubble_sort(nums, key = lambda x: x)
print(nums)
bubble_sort(nums, key = lambda x: x % 2)
print(nums)
halcyon plankBOT
#

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

001 | [7, 6, 5, 4, 3, 2, 1]
002 | [7, 5, 3, 1, 6, 4, 2]
haughty mountain
#

the end result will be the same though, unless you have a really weird key function

#

(maybe slower, if the key function is slow)

austere sparrow
#

well, it doesn't really matter here

haughty mountain
#

just pointing out that the semantics are a tad different 🙂

#

e.g. you could implement shuffle in a really silly way by generating a random number in your key function with the internal sort

austere sparrow
fiery cosmos
#

what is that function doing?

#

sort_lambda = sorted(nums, key = lambda x: x%2)

sick wyvern
#

it is sorting the nums list on the basis of values that is returned by lambda function

#

For example, if we pass a list of strings in sorted(), it gets sorted alphabetically. But if we specify key = len, i.e. give len function as key, then the strings would be passed to len, and the value it returns, i.e. the length of strings will be sorted. This means that the strings would be sorted based on their lengths instead

fiery cosmos
#

0 or 1?

#

oh I see

#

it's sorting all the even numbers first

#

and then the odd numbers

#

because % 2 returns 0 for even numbers

#

nice

sick wyvern
# 
L = ["cccc", "b", "dd", "aaa"]

print("Normal sort :", sorted(L))

print("Sort with len :", sorted(L, key=len))

output

Normal sort : ['aaa', 'b', 'cccc', 'dd']
Sort with len : ['b', 'dd', 'aaa', 'cccc']

fiery cosmos
#

Python is cool

sick wyvern
#

yes it sure is

sick wyvern
dreamy ocean
#

can anyone help me with a DP solution i implemented

# 
def rob_house_memo(nums,memo={}):
    if tuple(nums) in memo:
        return memo[tuple(nums)]
    elif len(nums) <=2:
        return max(nums,default=0)
    else:
        memo[tuple(nums)] = max(nums[0]+rob_house_memo(nums[2:]),nums[1]+rob_house_memo(nums[3:]))
    return memo[tuple(nums)]
#

this is for the 198. House Robber on leetcode, i did DP properly here, but the thing is my memoization is not ideal

#

im bascially storing slices of the input array as tuples in the dictionary

#

is there a better way of memoizing in this scenario?

lament totem
dreamy ocean
#

yea

lament totem
#

what is DP?

dreamy ocean
#

dynamic programming

lament totem
#

ah

#

do you have a link to the problem?

dreamy ocean
lament totem
#

There seems to be a O(n) time complexity solution that doesn't use any memoization

dreamy ocean
#

hmm

#

well is the solution i made good enough on a interview?

lament totem
#

Yeah it seems linear in time complexity, just the space complexity could be a problem

#

think that might actually be quadratic

dreamy ocean
#

yeah i thought so too

lament totem
#

There also already is a memoization decorator you could use if you wanted to go that route

#

functools.lru_cache

dreamy ocean
#

that could work, also do you think i could store indexes instead of the whole array in the dictionary?

lament totem
#

if there is only 1 solution for a given index then yes