algos-and-data-structs

[elfin sundial]

i thought, me copying and making a new array, in every append could be very problematic in the kwarg usecase

or in larger value appends

what's a good complexity value for this senario, or like what should be the time complexity

[jolly mortar]

O(1) is the best complexity you can achieve for any task

[elfin sundial]

so what's my operation's time complexity

[jolly mortar]

n^2

[elfin sundial]

jesus

[jolly mortar]

after second append, you copy 1 item
after 3rd, 2 more copies
after 4, 3 more copies
after nth, total copy operations is 1+2+3+...(n-1)= n(n-1)/2 = O(n^2)

[jolly mortar]

hmm this was wrong

the nth append on its own is O(n)

[elfin sundial]

what if you have an oscillating increment, first append increments array lenght by the current lenght itself x3 and then 2nd increment is increased by 2x and 3rd is incremented by 1. 4th would increment by 3x again.

in that logic, would the amount of times you'd increment or run the array increase operation decrease?

[elfin sundial]

right cos im not over allocating with a static amount, its just +1 length

[jolly mortar]

not sure

will need some math

[elfin sundial]

yeah, thats where i bounce :p

appreciate the help mate

cheers

[cinder nebula]

i suppose you could approximately say its O(N), since in other words, every time you increase N by 3, it appends 6 times, which is close enough to being linear once N starts getting larger

big-O notation is about how a program's time/space complexity increases as N approaches infinity, which overall seems to increase if the function cycles between appending one, twice, and 3 times over and over N times

i wrote a quick thing to plot input N against the length of the list when appending this way, and it looks like it becomes roughly linear

[fiery cosmos]

Heey heey everyone, is this the chat to discuss generetic algos??

[storm wave]

Hi there everyone is there a library to measure time complexity of a solution, algorithn

[cinder nebula]

you can measure how long it takes for an algorithm to run given a certain input, but that's different to measuring time complexity, which is more something that you do by manually analysing the code

[storm wave]

I have always done it manually but when I think about it I think it can be implemented into a library, no?

[gaunt bobcat]

hello, has anyone here ever used SimPy?

[hexed tiger]

Guys, I want to convert my python program into an exe. But, my command prompt shows me that problem of the system. Pls could you tell me how to fix it?

[jolly mortar]

Mapping is in collections.abc now not collections

[peak jungle]

Hey,... Anyone here willing to help me understand why my code is running with turtle speed...? 🙂

[thick echo]

Did you post the stack trace in a channel?

And the code?

[thick echo]

The idea is you want to be able to learn how to do it by eyeball.

Some things in software we outsource to tools. Visual debuggers, diff tools, etc.

Some things you need to do yourself, in your head.

Big O is one.

[haughty mountain]

you can experimentally try to verify some stuff, e.g. there are cases where in the analysis you simplify something that you think doesn't matter and arrive at some O (an upper bound on the complexity) while in reality the proper bound is lower

[thick echo]

Amortized constant time is definitely a thing.

The idea is you need to understand Big O well enough that you don't need an external tool to estimate the Big O of a block of code.

[haughty mountain]

yeah, there are cases where it's nice to verify things though

could be for the sake of "is my implementation correct complexity-wise"

e.g. I implemented Strassen's matrix mult algo, and it's hard to tell if I didn't slip up when implementing and added some inefficiency

plotting some times allows some level of verification

[thick echo]

Well yes.

So the thing is.

Software Engineering is a process done by heuristic.

Formal verification means we formally prove all the functions in our program.

Are logically true.

I'll let other people talk about TLA+...

The idea with engineering is to get very very good at writing code intuitively.

Hence... intuition.

Hence... we need an intuition for Big O.

[haughty mountain]

yeah, intuition about time complexity and estimating actual runtimes is very helpful

e.g. what's a ballpark runtime for a quadratic algo for n = 10^5

to which a reasonable estimate is tens of seconds to a couple of minutes for cheap operations in a compiled language

scale some depending on the kind of work the code does

(10^5)^2 operations / (10^9 operations per second) gives a quite optimistic estimate of 10s

[austere sparrow]

import turtle 
``` 🙂

[fiery cosmos]

How does this work guys

How do we get mapping of index from hash code

Like for first one 4 mod 11 is 4. But how do I get which index is the value 4 stored in?

[cinder nebula]

well, from the sounds of things, the hash table stores values into the index of whatever the hash function returns, so in this case 4 goes into the table index 4, no?

[simple pier]

i think u can think ur hash table as having position 0 to 10 since it’s mod 11 it will never be >= 11

[fiery cosmos]

That seems to be a bit contradictory with next question

Wait

So for index 1 there's no element

[simple pier]

this is linear probing

[fiery cosmos]

Oh fuck

[simple pier]

it’s different from the above which is chaining

[fiery cosmos]

Right

Omg I need to start reading

[frozen ridge]

hello everyone, I'm taking the course data structures/algorithms. can someone help me with Lists, Stacks and Queues?

[agile sundial]

sure

[frozen ridge]

do you know how to create a function that reverses the list recursively?

[agile sundial]

a linked list? probably

[halcyon plank]

Hey @fiery cosmos!

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.

[fiery cosmos]

I need to design an algorithm which checks consistency between 2 similar lists. Using hash functions. How can hash functions make things efficient

Other than the fact that it's easier to transfer hash compared to the element itself for comparing

[agile sundial]

you're checking if they're equal? wdym by consistency

[fiery cosmos]

The lists are stored in 2 separate databases. And my goal is to minimise the transfer between the 2

As in a[1]=b[1]

Or not.

For all indexes

Oh

I think I have an idea

Nice

[fiery cosmos]

Can someone explain what does reversing a list recursively mean

As in an algorithm that works recursively?

[frozen ridge]

in my case i just need to create a recursive function and not an algorithm

[fiery cosmos]

hey all,
how can i build an optimum binary search tree given a set of key probabilities p_i and probabilities that a given search corresponds to a dummy key, q_i

Could someone recommend a good book?

pretty much every algos course uses introduction to algorithms 3rd or 4th edition, though i wouldnt call it "good"

Okay

i mean, i suppose its good if you have CS or mathematics background

[hollow plinth]

o

[fiery cosmos]

brutal for non traditional types

[static sigil]

Hello I am currently learning genetic algorithms and I would like to ask a couple question if there is anyone with knowledge here?

As new generitions can be created for ever. But that might not result algorithm getting better. So there are reasons to stop the code from working

according to the wikipedia theese are:

---

A solution is found that satisfies minimum criteria
Fixed number of generations reached
Allocated budget (computation time/money) reached
The highest ranking solution's fitness is reaching or has reached a plateau such that successive iterations no longer produce better results
Manual inspection
Combinations of the above

I couldnt understand what "Fixed number of generations reached" means

Is it possible for someone to explain?

[fiery cosmos]

you run it for n= fixed number of generations of the choosing of the user

[static sigil]

oh

[fiery cosmos]

say, it reaches 50, the number of generations you told it to run for

[static sigil]

okay thank you that was simpler than I thought

lol

Do you use python for this subject?

[fiery cosmos]

for writing algorithms? yes. im actually studying bioinformatics MS right now but haven't gotten very far yet. my answer to your question was just my interpretation of what it is taken to mean given the context

[static sigil]

Ok thank you for your time

[fiery cosmos]

np

[static sigil]

Bye have a good day

[fiery cosmos]

👋

[dark sentinel]

i made my first project today

which was a simple quiz game with a point score

even added a bonus round to the quiz

[static sigil]

congrats man

did you publish it anywhere?

[dark sentinel]

no sadly i deleted it by accident

[static sigil]

:(

[dark sentinel]

but it was so simple i can replicate it easily

[fiery cosmos]

!\

[dark sentinel]

it was a little pokémon quiz

[static sigil]

okay good luck on your project

[copper holly]

Hello

I have been playing around with implementing floodfill

Two approaches I did were recursive and iterative

It was surprising to me that the recursion is generally faster (ofc when under recursion limit)

!e

from timeit import timeit
from random import randint

grid = [[randint(0, 2) for _ in range(1000)] for _ in range(1000)]

def find_connections1(i, j, results=None):
    curr = grid[i][j] 
    if results is None:
        results = []
    if not curr:
        return results
    results.append((i, j))
    rows, cols = len(grid), len(grid[0])
    neighbours = ((i-1, j), (i+1, j), (i, j-1), (i, j+1))
    for next_i, next_j in neighbours:
        if (0 <= next_i < rows and
            0 <= next_j < cols and
            grid[next_i][next_j] == curr and
            (next_i, next_j) not in results):
            results = find_connections1(next_i, next_j, results)
    return results


def find_connections2(i, j):
    curr = grid[i][j]
    results = set()
    if not curr:
        return results
    rows, cols = len(grid), len(grid[0])
    to_check = {(i-1, j), (i+1, j), (i, j-1), (i, j+1)}
    checked = set()
    while to_check:
        next_i, next_j = to_check.pop()
        if (0 <= next_i < rows and
            0 <= next_j < cols and
            (next_i, next_j) not in results and
            grid[next_i][next_j] == curr):
            results.add((next_i, next_j))
            temp = (next_i-1, next_j)
            if temp not in to_check and temp not in checked:
                to_check.add(temp)
            temp = (next_i+1, next_j)
            if temp not in to_check and temp not in checked:
                to_check.add(temp)
            temp = (next_i, next_j-1)
            if temp not in to_check and temp not in checked:
                to_check.add(temp)
            temp = (next_i, next_j+1)
            if temp not in to_check and temp not in checked:
                to_check.add(temp)
        checked.add((next_i, next_j))
    return list(results)

for f in (find_connections1, find_connections2):
    print(timeit("find_connections(len(grid)//2, len(grid)//2)",
                 number=1000,
                 globals={"find_connections": f, "grid": grid})/1000)```

[halcyon plank]

@copper holly :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | 1.0831206105649471e-05
002 | 1.5149835497140885e-05

[copper holly]

Anything wrong in my approach in the iterative method?

Or is this to be expected?

[fiery cosmos]

what is floodfill

[agile sundial]

an algorithm

[fiery cosmos]

lol well i figured that

i can google

was just curious for "an algorithm to achieve x by taking as input y"

still trying to figure out how to build an optimal binary search tree

https://www.youtube.com/watch?v=vLS-zRCHo-Y

[haughty mountain]

you know paint bucket tool in image editors? that

[fiery cosmos]

interesting. yes i am very well familiar, i've spent many a day playing around in MS paint

[fiery cosmos]

any guidance on this

[haughty mountain]

this is probably what you want https://en.wikipedia.org/wiki/Optimal_binary_search_tree#Knuth's_dynamic_programming_algorithm

[fiery cosmos]

so im running it on paper and its actually a neat problem

im starting with the two smallest probabilities and adding them as the deepest layer

then working upward, but right now i can either place my largest probability key at the root and make everything +1 in depth, or i could add it to lvl 2, which would 2x the cost

very curious

dude Knuth is everywhere

he was a math wizard

https://tenor.com/view/axel-bouvet-math-brain-gif-15488662

[haughty mountain]

lol, Knuth is one of those living legends yeah

[fiery cosmos]

is he still around?

https://www.youtube.com/watch?v=EE1R8FYUJm0

yep

[fiery cosmos]

oof.. trying to run the optimal-bst on pg 402.. yeah no

what is the code for the root of a huffman tree

for example, the left child of the root would have code 0

and right with 1

[fiery cosmos]

is that optional or part of every match

[dark sentinel]

i finished my project and made it a bit more fun

now how do i upload it

or where in particular

[rigid turret]

Hey All, I'm wondering if I got these correct or no?

[haughty mountain]

first one seems fine

[agile sundial]

kinda funny they said "f2 is an anonymous function"
f2 = lambda ... 😔

[haughty mountain]

for the second I think no option is great

[agile sundial]

^ doesn't it error if the file isn't there, because there's no file to close

that'd only work if you got an error while reading, which could happen, ig

[agile sundial]

ig technically that makes the 4th option correct lol

[haughty mountain]

I guess that's a thing yes

but idk if I would call that the error being suppressed

that feels more like except

[agile sundial]

ig 🤔. you don't get that error though, which i think is what they're going for

[haughty mountain]

I guess it's more that the exception in the finally preempts the exception in the try

[agile sundial]

oh, you do actually, it shows "during handling of the above exception ... "

[haughty mountain]

finally in general has weird implications, but that's another story

e.g.

while True:
  try:
    return
  finally:
    continue

[agile sundial]

yeah that q is pretty bad, lol. none of the choices work

[agile sundial]

and also,

def f():
  try:
    return 1
  finally:
    return 2

[haughty mountain]

I think the continue one is weirder, since the return just doesn't happen, rather than the return happening but with a different value

[agile sundial]

you could probably combine the two examples tbh

[haughty mountain]

i.e. returns are not guaranteed to return

[agile sundial]

yeah, although i think you get this in java as well ¯_(ツ)_/¯

[haughty mountain]

yes, it's just interesting behavior, cancelling control flow

[agile sundial]

at least we have this lint 😩

[haughty mountain]

C++ doesn't even have finally iirc

[agile sundial]

you have RAII though, which achieves the same thing

[haughty mountain]

yep

it's a cleaner solution imo

but requires stricter lifetimes

[agile sundial]

yeah, you have 1 drop impl instead of doing cleanup code everywhere you need to cleanup

[haughty mountain]

context managers in python are basically discount raii

[austere sparrow]

I think Alexandrescu had some macro set which lets you implement finally, sorta

[pallid girder]

I started dsa and covered basics like arrays, strings, searching, now I want to start to hashing but i dont know what should I cover in hashing ?
which video to watch?
What topics do I need to cover to master hashing in python?
Please can anybody tell me where to start to and where to end in hashing

[austere sparrow]

PyCon 2010: The Mighty Dictionary https://www.youtube.com/watch?v=C4Kc8xzcA68
Brandon Rhodes - The Dictionary Even Mightier - PyCon 2017 https://www.youtube.com/watch?v=66P5FMkWoVU

[pallid girder]

So basically I should master dictionary in python?

[fiery cosmos]

and functions

maybe linked lists

depending on what sort of hash table you want to build and specifics eg, which collision resolution, will it be open addressed, probing scheme..

[quartz tinsel]

Hi guys anyone knows what is the regex in python to check a word that starts and ends with different letters. Note that spaces and single letter words are not part of the regex matching words

[haughty mountain]

well, understanding how hashing makes hash tables possible is a good idea

hashing and the applications of hashing are two kinda different subjects though

[pallid girder]

Oh okay thank u so much so I should be covering
Hash table
Hash function
Collision resolution
Practice questions on hashing

Should I add anything else

[fiery cosmos]

open addressing and probe sequence

[austere sparrow]

Why do you need regex for that?

[fiery cosmos]

A biologist on a detailed study of flower petals identified that the number of petals consistently follows a number sequence. Each element is obtained by adding two preceding elements, and the sequence starts with 0 and 1. Sequence is defined as, F0 = 0 and F1 = 1 and Fn = Fn-1 + Fn-2. Write a python program and help the biologist to print the number of petals in sequence. ANYONE SOLUTION?

so.. the fibonacci sequence

YEAHH

so find some fibonacci sequence python code and repurpose it

Amazon has got ‘n’ bedsheets of a particular brand. Customers shop online and purchase ‘t’ bedsheets. Orders will be taken until the availability of stock of the brand. Suppose if a customer asks for number of bedsheets ‘t’ more than in stock ‘m’ then amazon only accepts ‘m’ items. Given a value ‘n,’ write a python code to deliver the order of bedsheets until the stock gets over and print the average number of items distributed. Print only 2 decimal places of average.

[fiery cosmos]

hey the other one?

sorry i've got my own problems to solve rn

[quartz tinsel]

I cannot anything else there but regex

[fiery cosmos]

hey is a 2D array in C++ in the form arr[][] the same as an array of arrays in python eg arr = [[]]

[quartz tinsel]

yes

[fiery cosmos]

ty

[fiery cosmos]

dang this bitonic euclidian travelling salesman tour is really tough

been stuck for a few days

i guess the bitonic version is easier than the standard version

[hybrid epoch]

Inputs and outputs needs to be clarified. This can be solved with OOP. Save the state of distributed items as a class variable. Define a method to calculate the average every time there is a distribution. Then for printing two decimal places, use format codes, e.g: f"{math.pi:.2f}" prints pi to two decimal places.

[fiery cosmos]

me confused

can someone help me understand this

is N[i,j] supposed to be indices into the 2D array such that in python it'd be N[i][j]? furthermore, how should i be handling the length l here that is being computed

i think in the tour array, one only stores the point k which minimizes the tour distance, where k < j

i get line 7

we're inputting into our matrix where we store the adjacent nodes with the shortest path to the current node, that the node i is the adjacent node with the shortest path to j (in this case, the trivial case) because there is only one adjacent node, namely i, and j for i=1 and j=2

i don't know where we're storing the distance we are computing

[round glacier]

https://stackabuse.com/courses/graphs-in-python-theory-and-implementation/lessons/dijkstras-algorithm/
https://www.udacity.com/blog/2021/10/implementing-dijkstras-algorithm-in-python.html

Does anyone know any website where it implements dijkstra's with type hints? None of the tutorials I find have type hinting, and the type hints help me to figure stuff out more.

[agile sundial]

can't you just implement one with type hinting?

or take one and add type hints

[round glacier]

if i understood it, yes. but im trying to learn it

[fiery cosmos]

akdljf[029q-[0cx293r92i.,3rx[092ir,

[round glacier]

@agile sundialalso none of these have good variable names

"v" and "j" and "i" are not condusive for learning how the code works

            if dist[u] + l < dist[v]:
                dist[v] = dist[u] + l```

like how is this helpful?

[agile sundial]

fair enough. those are probably nodes

well, v is probably a node, l is probably the current distance to v

[round glacier]

Do you know any tutorials where dijkstra's is implemented with valid variable names and type hinting that is simple and easy tounderstand?

I feel like all of the tutorials i read are confusing because the naming is awful.

I want to be able to just read the code, easily.

I don't want to have to sit here and try to figure out what's going on (because the names are bad).

[fiery cosmos]

typically if you have like a vertex v, it follows that other vertices are w, x, y etc

[agile sundial]

CLRS

[fiery cosmos]

for u to imply a preceeding vertex

[agile sundial]

usually it's u and v, yeah

[round glacier]

its honestly amazing how godly awful mathmeticians are at variable naming conventions

@agile sundial

lol

[agile sundial]

¯_(ツ)_/¯

yeah, but is node1 node2 really much better

like, ig you could say like, compare_against or something

[round glacier]

i mean you know the reason why math is so hard for many people to learn?

its because its taught in such abstract terminology

lol

[agile sundial]

variable names is not why lmfao

[agile sundial]

because it's abstract

you can't really get away from that

[round glacier]

yea but u can still bring things back to reality

lol

[agile sundial]

that usually makes it much harder, though

anyways, i disagree that the reason it's hard is because of bad teaching. it's just hard

[agile sundial]

in the third edition, it's chap 24.3

also, are you just looking at code without explanations?

[round glacier]

i think ive read that, its still using u, v, i, j, k, a, b ,c

lol

[agile sundial]

are you just looking at code without reading the explanations?

[agile sundial]

it is, but it also explains what all of the variables mean and why

[round glacier]

i stil find it confusing 😄

[agile sundial]

what part?

this isn't a resource issue anymore, then

[fiery cosmos]

i appreciate the terminology used until there are too many subscripts

or like, when they say given a set of matrices A_1, A_2, A_3, just use A, B, C

[agile sundial]

there's usually a reason for that, though. by naming them all A, you can do something like..

.latex $$\sum_{i=1}^{3} A_i$$ or something

[agile sundial]

ok it's missing the subscript, but you get the point though. you can parameterize it

obviously, naming everything the same variable without a use is...useless

[fiery cosmos]

right great point

[haughty mountain]

this thing would be a lot more readable if the else if didn't get extra indentation

[fiery cosmos]

lol did you see the meme

public are you spooky now on account of October

woah what just happened

spooky

spooky

awesome

[agile sundial]

indeed

[haughty mountain]

to prove the point compare these two

wait

my indentation is wrong...

[fiery cosmos]

btw this is from here:
https://www.cs.huji.ac.il/course/2004/algo/Solutions/bitonic.pdf

[haughty mountain]

there

[fiery cosmos]

here is the recurrence relation

l is length, l(i,j) is the length of the edge between nodes i and j

dist is euclidian distance, which is simple to calculate

[haughty mountain]

l(i,j) is the length of the edge between nodes i and j
you sure? that sounds like dist(p_i, p_j)

[fiery cosmos]

i'm pretty good with the various conditions and what all the variables mean, but implementing it is another thing. i haven't figured out how to handle the recursion and how to break it into different functions. rn i have one function to compute the euclidian distance, i have a main function, etc. i don't understand how/where we are storing the edge lengths. maybe we aren't

yeah you're right. i was describing the first recursive case

[haughty mountain]

surely l is some minimal distance up to some point

[fiery cosmos]

so the thing of it is, it seems as if in their scheme they are only storing the adjacent node of j, that is, node the which gave rise to the minimum distance on the way there. that could be i, it could be j-1st node, etc

in their dp table

so idk what to do with this distance i am coimputing

computing

[fiery cosmos]

i hope you saw this, it made me laugh

i need to go pick up medicine for my cat, i will be back

[haughty mountain]

so if I understand correctly the algorithm would still be correct if you ignore case 2 here and just do case 3 instead

it would just be slow

as a consequence of some of the observations, if i < j-1 then they know k must be j-1

wait, maybe not

maybe they don't reduce to the same case actually

the last case probably assumes that p_i and p_j are adjacent

it still feels like case 2 is just an optimization

I just need to get my head around the idea of case 3

oh, l(i, j) is the length of the shortest bitonic paths with endpoints i and j

not tours

ah, right in case 3 we consider all possible shortest bitonic paths that only consider nodes < j

and we try to find the one that is least expensive to attach to

[fiery cosmos]

thats how i've understood it

[haughty mountain]

tbh, it might be helpful to substitute i=j-1 in the case 3 expression

[fiery cosmos]

i don't think you need the j>2 bit, correct

i'm just not getting where we are archiving the lengths

here is another resource:

[haughty mountain]

.latex $$\min_{1 \leq k < j - 1} (\ell (k, j - 1) + \tmop{dist} (p_k, p_j))$$

[grand haven]

Failed to render input.

View Logs

[fiery cosmos]

https://www.geeksforgeeks.org/bitonic-traveling-salesman-problem/

[haughty mountain]

welp

.latex $$\min_{1 \leq k < j - 1} (\ell (k, j - 1) + \textrm{dist} (p_k, p_j))$$

[haughty mountain]

wdym where we are archiving the lengths?

[fiery cosmos]

like when i set out to write this code, i know in each one of the recursive cases, how to compute the length of the path. ok great, then what?

sidebar: we have an assignment of i into the 2D array to indicate that the node prior to j that gave rise to the shortest path is i, trivial case, line 7. so we can say array[1][2] = i in the case that i = 1 and j = 2. similarly we see other assignments to the dp table or 2D array or whatever you want to call it

but im not seeing the lengths stored anywhere, if i had to guess the recursive call will return said length

[haughty mountain]

l will be a n x n array in the code

[fiery cosmos]

right which i figured how to create with a list comp

wait so you are calling l = dp = 2D array

most people call it a dp table

geeksforgeeks calls it a 2D array

[haughty mountain]

I mean, it is a dp table

[fiery cosmos]

right

just making sure im on the same page

[haughty mountain]

but they call it l for length

the code iterates in an order so that it only depends on values of l that have already been computed

bottom-up dp, I guess

[fiery cosmos]

ok i definitely missed that bit

[haughty mountain]

no actual recursion going on

[fiery cosmos]

wait soo if l is the dp table, what is N

Compute l(i, j) and N (i, j), for all 1 ≤ i < j < n.

[haughty mountain]

book-keeping to be able to reconstruct stuff later

if you only wanted the length and not the actual path you could completely ignore N

[fiery cosmos]

so just another n*n array

[haughty mountain]

yes

[fiery cosmos]

yeah the way it reads in CLRS its not really clear. they say give an algo for determining an optimal tour. in their example they only give the length of the shortest said tour, but i read that as we need to return the path as well

[fiery cosmos]

dang! i had that feeling earlier, i should have just tried to implement and seen that that was the proper interpretation

[haughty mountain]

I'm interpreting that as they want the tour

not just the length of it

[fiery cosmos]

right

ok ok so N gets the points and l gets the distances

https://tenor.com/view/typing-computer-twitter-gif-12385391

[haughty mountain]

yes, N(i, j) is book-keeping to remember what choice created the minimum l(i, j)

[fiery cosmos]

perfect i think i can implement now

see above gif, thats me

[opal oriole]

DP notation can get very confusing because there are two ways to implement solutions which are the direct method, and successive approximations, and then also they could want either the value solution of the recurrence relation or the "path" in getting that value as a structure.

[fiery cosmos]

not for me bra. its big brain time

[opal oriole]

(Which requires the extra book keeping)

[haughty mountain]

idk if successive approximations is the right term

[fiery cosmos]

🧠

[haughty mountain]

it tends to be the optimal solution for some subset

not an approximation

[opal oriole]

I took the terms from a paper on DP perspective on various problems, not sure if it's the best.

/ what DP actually means / when a problem is DP or not.

[fiery cosmos]

DP can be used to get an approximation, or solve the problem outright, depends on the DP method / implementation / approach and the problem

if i understand correctly

[haughty mountain]

DP is a terrible name for what it is 😛

[opal oriole]

DP is a terrible name on purpose.

[fiery cosmos]

well yeah i mean w the word programming right in there

which does not mean computer programming

[fiery cosmos]

this

[haughty mountain]

well, there is programming

but also dynamic

what's dynamic about it?

[fiery cosmos]

they just mean dynamic tabulation

or maybe static memoization

[opal oriole]

I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. An interesting question is, "Where did the name, dynamic programming, come from?" The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word "research". I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term research in his presence. You can imagine how he felt, then, about the term mathematical. ```

[fiery cosmos]

LMAOO

what the hell hahahahaaha

[opal oriole]

What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word "programming". I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying. I thought, let's kill two birds with one stone. Let's take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense```

It was to avoid his research getting blocked.

— Richard Bellman, Eye of the Hurricane: An Autobiography (1984, page 159)

[agile sundial]

🤔 this seems like a good read lol

[fiery cosmos]

oh, it is actually a terrible name on purpose. i thought you were being cynical

[opal oriole]

No, I meant it was on purpose.

[fiery cosmos]

i see that now

[haughty mountain]

the essence of DP is exploiting optimal substructure, sadly this simplicity is hidden behind a cryptic name

[opal oriole]

Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.

[fiery cosmos]

pathological fear and hatred

[opal oriole]

Yeah, and it's why the paper I was reading was trying to categorize the implementations into direct and successive approximations (e.g. Q-learning in reinforcement learning).

[haughty mountain]

sad that someone so influential as Bellman needed to do this

[fiery cosmos]

exploiting optimal substructure by not constantly re-solving the same problems

[haughty mountain]

successive approximation would be stuff like relaxation?

[opal oriole]

DA is the successive approximations as well form DP POV.

(And BFS is a special case of that)

The successive approximations approach is also linked to fixed point iteration methods.

[fiery cosmos]

have y'all seen the self organizing maps solution to travelling salesman?

[opal oriole]

Yes, I work with self organizing maps every day.

They can solve a lot of things you would not expect.

[haughty mountain]

I've done some self-organizing maps, but not for TSP specifically

[fiery cosmos]

i haven't dug into the code or anything, i saw a gif online by chance and thought it was really cool

[haughty mountain]

it's for approximation, right?

[fiery cosmos]

like, before i even knew what travelling salesman problem was

not sure.. squig?

[opal oriole]

They come from neuroscience, many neural networks do something like a self-organizing map or pretty much exactly, and it's especially used by small(er) networks (e.g. in bees).

Yes it's approximate.

[haughty mountain]

I did self-organizing maps in my intro to neural networks

[fiery cosmos]

self organizing how

[opal oriole]

Other biological approximations include things like ant simulations (also fun to implement).

[haughty mountain]

which went through the fundamental stuff from ages ago

[fiery cosmos]

like in what way would cells organize by what metric

[haughty mountain]

organize to minimize something, typically

in physics it might be minimizing energy that gives rise to structures

[opal oriole]

The key to SOMs is that they preserve topological structure of the data.

[fiery cosmos]

cells typically organize and communicate by tissue type and physical locality or gene expression, i wonder how a given subsection of the brain would do that or how one might even measure that

its really hard to do in vivo stuff

[haughty mountain]

let me find the relevant problem set report...

[fiery cosmos]

its ok i need to go implement the bitonic thing and quick screwing around

https://www.youtube.com/watch?v=NIpns4R9Ep4

happy spooktober

[haughty mountain]

I know the, as Kohonen networks, but I guess the usual term now is self-organizing map

https://en.wikipedia.org/wiki/Self-organizing_map

[fiery cosmos]

uhhh why are they setting shit equal to + infinity in this pseudocode

[cerulean river]

hey guys quick question. So I am solving a question that is asking me to define the class structure of a MinStack which is a regular stack but is also able to output the minimum value in the stack in O(1). So obviously the class the will use a python list to be the stack. my question is since this list used in every method where do I declare it?

class MinStack(self):
stack = []

def __init__(self)

or should the declaration go under the __init__?

[haughty mountain]

because they are computing a minimum, so they default to a large value

you can write this neater with python's min and a generator expression

actually...you probably want some kind of argmin since you care about what caused the min

[fiery cosmos]

ok

i'll look into argmin

[haughty mountain]

it's not a function

more of a math thing

what argument gives the minimum

[fiery cosmos]

is it in the python literature

[haughty mountain]

no

[fiery cosmos]

ok

[haughty mountain]

like, you can do stuff like

min((function_to_minimize(arg), arg) for arg in arguments)

which will give you both the value and the argument

[fiery cosmos]

ok i've jotted this down. we saw we'd need a for loop to compute the min, my idea was just append each min to an empty list and then get min of the list at the end

[haughty mountain]

!e

value, arg = min((x**2 - 9*x + 51, x) for x in range(-10, 11))
print(f'min value {value} at x={arg}')

err, not the value I intended

but whatever

[halcyon plank]

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

min value 31 at x=4

[fiery cosmos]

this takes 68 steps to execute in pythontutor

amazing so much can be instructed with such little input

[haughty mountain]

!e

value, arg = min((x**2 - 6*x + 51, x) for x in range(-10, 11))
print(f'min value {value} at x={arg}')

[halcyon plank]

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

min value 42 at x=3

[haughty mountain]

there we go, apparently expanding a quadratic correctly is hard

if I were to write this without min I would do something like default to infinity

!e

min_value = 10**9  # some big value
min_x = None
for x in range(-10, 11):
  value = x**2 - 6*x + 51
  if value < min_value:
    min_value = value
    min_x = x
print(f'min value {min_value} at x={min_x}')

[halcyon plank]

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

min value 42 at x=3

[opal oriole]

Self-organizing map is the generalized term.

But either can be used.

[fiery cosmos]

this could be repurposed and replace lines 12-15

er

12-14

[haughty mountain]

what I wrote there is the same structure they use in their pseudocode yes

you end up writing that kind of code a lot

[fiery cosmos]

🤔

[haughty mountain]

computing a minimum or an argmin (or both)

C++ has std::min_element that is basically argmin on iterators
python can do

min((arg for arg in args), key=some_function_to_minimize)

[opal oriole]

You can think of min of a list giving you the min value in the list, while argmin gives you the index of that min value in the list.

If you think of a list as having an index as an argument passed to it, and it gives back a value.

[haughty mountain]

the name kinda explains itself

min is the minimum

argmin is the argument that causes the minimum

[fiery cosmos]

alright im going to translate that and you tell me how incorrect it is

[haughty mountain]

in math speech

though I guess this is the definition that gives the set of arguments

not just one of them

[fiery cosmos]

q = min((k for k in range(1,i-1)), key = l[k][i]+euc(points_array[k],points_array[j]))

euc here being a function that takes two points as input and returns the euclidian distance

[haughty mountain]

that doesn't compute q in their code

(and the range is one off)

range(0, i-1) if you zero index

[fiery cosmos]

hmm good point. i hadn't noted the 1 based indexing

so this should all be for i in range(0,j) instead of for i in range(1,j-1)

[haughty mountain]

and you need a lambda for the key

[haughty mountain]

range(0, j-1) I'm pretty sure

I think their notation is inclusive-inclusive while python does inclusive-exclusive

[fiery cosmos]

perfect, that won't make things confusing at all

[haughty mountain]

well, welcome to translating math indexing to programming

it happens a lot

[1, i-1]
[0, i-2]   # shift down one for zero indexing
[0, i-1)   # exclusive right side

[opal oriole]

(-1, -0), because the right is already -1 from being exclusive then.

(minus ones due to the start being at 1 instead of 0)

[haughty mountain]

right, the end effect is just subtracting one from the left hand side

N[i][j] = min(
  (k for k in range(0,i-1)),
  key=lambda k: l[k][i]+euc(points_array[k],points_array[j])
)

[fiery cosmos]

[0, i-1) this excludes or includes final index element

[haughty mountain]

excludes

the typical range notation in math is [] brackets for inclusive and () for exclusive

(there is another notation, but it's terrible)

[0, i-1[

I hate it

[fiery cosmos]

lol

bracket hate huh

brb

[haughty mountain]

unbalanced bracket hate

[opal oriole]

Green is start, from book inclusive, inclusive, start at 1.

Red is -1 to the range ends.

[haughty mountain]

(reminds me of Khan academy drawings)

[opal oriole]

Then make the end exclusive (add 1 back (or just don't subtract 1 from it)).

(closed inclusive, open exclusive)

[haughty mountain]

for clarity red is shifted by 1

it's not like it starts at -1

shouldn't the magenta be longer?

ending at 5

[opal oriole]

Uh yeah.

At 5.

So the magenta would have grown the range by 1 if the end was inclusive, but it's exclusive.

(I should change my red color maybe)

[1, n] -> range(0, n)

[fiery cosmos]

same

[opal oriole]

I like silly colorful math drawing.

[haughty mountain]

because red-green color blindness? I checked and the contrast seems good enough anyway

[opal oriole]

Yeah, but it may also be a bit too dark.

And not consistent with the neon style.

[fiery cosmos]

it'd be cool to do this and write in the notation just next to it

im sure a lot of people would find it super helpful

in the same color

let me try

[haughty mountain]

so this

[fiery cosmos]

should have grouped the same range inc exc next to one another

[haughty mountain]

that or actually insert the value yeah

though use filled and hollow circles for the end-points

that's the usual way to indicate inclusive/exclusive in plots

like in Squiggle's plot

[fiery cosmos]

whoops

[haughty mountain]

pink and green is wrong

should be filled

because inclusive

[opal oriole]

(pro tip, never use full black or full white (in digital), if you need really dark, try dark purple)

[fiery cosmos]

ok

[haughty mountain]

I don't mind full black tbh as long as the contrast is reasonable

[fiery cosmos]

alg what is this key = lambda business

[haughty mountain]

you need to provide a function as the key argument

[fiery cosmos]

so this is simply another way of writing that for loop where we seek the min among all the q's

[haughty mountain]

except this doesn't give you the min value

just the argument

[fiery cosmos]

hm

[haughty mountain]

this is something that would give both

[fiery cosmos]

this returns the argument which gave rise to the min?

[haughty mountain]

(though in practice I would probably end up writing the loop as soon as the logic to check is non-trivial)

[haughty mountain]

yes, the k for which the key is minimum

that's what the statement is saying

[fiery cosmos]

ok cool

[opal oriole]

The min of f will give you the min y value, the argmin will give you the x that gives that min value (when plugged into f).

[fiery cosmos]

oof ok. i guess i need to develop this math <--> CS intuition

[opal oriole]

So you could imagine different ways to finding the argmin, like trying different values of x and see which gives the smallest f(x).

What argmin exactly means in code depends what you are getting the argmin of and it may be easy or hard.

[fiery cosmos]

i'm not understanding the tail bit of this pseudocode

ok i have a python script and i have no idea what its doing, i can't run in pythontutor as they don't allow import statements

[haughty mountain]

you need imports?

[fiery cosmos]

well yeah im using import math for sqrt

[haughty mountain]

you could do **0.5

[fiery cosmos]

ok thanks

313 steps

ahh i already found a mistake

yeah so it only ever inputs a single value into one of the array locations

[fervent saddle]

why is this Time Limit Exceeded on leetcode? Isn't it O(n)?

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        numset = set(nums)
        seen = set()
        longest = 0
        
        for n in nums:
            if n not in seen:
                length = 1
                seen.add(n)
                while n + 1 in numset:
                    length += 1
                    n += 1
                    seen.add(n)
                if length > longest:
                    longest = length
        
        return longest

https://leetcode.com/problems/longest-consecutive-sequence/submissions/

[fervent saddle]

It just accepted the sorting solution

so lol, they didn't account for the overhead of hashing making the O(n) solution slower for their data sizes nvm

[agile sundial]

i think you technically have O(n^2) if the input is something like [1, 2, 3, 4, ...]

oh, nevermind i missed if n not in seen

yeah, possibly 🤔, but hashing ints is just an identity function, so it can't be that

[fervent saddle]

their own O(n) solution works:

class Solution:
    def longestConsecutive(self, nums):
        longest_streak = 0
        num_set = set(nums)

        for num in num_set:
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1

                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1

                longest_streak = max(longest_streak, current_streak)

        return longest_streak

but not mine

[haughty mountain]

try list(reversed(range(...))) as input

[fervent saddle]

that's the one it fails on

[haughty mountain]

yes

[fervent saddle]

it counts backwards from several thousand

why does that fail?

[haughty mountain]

it will make your code quadratic

[fervent saddle]

wait, I think I see why now

[haughty mountain]

your seen check doesn't save you

[fervent saddle]

yeah

[haughty mountain]

they only try finding the length when they know it's the first in a sequence

i.e. if n-1 doesn't exist in the set of numbers

[agile sundial]

ah, i was almost right

[fervent saddle]

got it!

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        numset = set(nums)
        seen = {}
        longest = 0
        start_number = None
        
        for n in numset:
            if n not in seen:
                start_number = n
                length = 1
                while n + 1 in numset:
                    n += 1
                    if n in seen:
                        length += seen[n]
                        break
                    length += 1
                    seen[n] = None
                if length > longest:
                    longest = length
                seen[start_number] = length
        
        return longest

I know theirs uses less memory, and it's probably faster. But still, I got it.

I can't ever think of the optimized stuff that they come up with. Like with the longest palindrome one, I didn't think to expand around the center to get O(1) space instead of O(n)

[thick hazel]

hi all, i need help with an algorithms question

Question: Given an input string of digits and a text file containing a list of all valid words, your goal is to produce a vector of possible, valid words in alphabetical order for the given string of digits.```

ive been stuck on this for 5 fucking days

what i tried to do was like

do it recursively

but that went over like a pile of bricks !

[haughty mountain]

why would you recurse?

you can convert words to digits easily

at that point solving should be easy

[shut hazel]

Actually on older cellphones to type cat you would have to pres

222 [c] 2 [a] 8 [t]

[thick hazel]

i know lol tell the person who made this GOD AWFUL PROBLEM that

[shut hazel]

I just saw your message and I'm trying to figure out why is anyone trying to reinvent the wheel when right now we are at prediction texts and all

[thick hazel]

but then id have to go thru the entire list of 200,000 words

[haughty mountain]

yes, but only once

[shut hazel]

You guys want to help build something useful that can generate a $ glitch?

It has to do with the stock market

And I mean real life gta up down x x square square l1 l2 r1 $ glitch but it's actually real $

[haughty mountain]

!rule 9

[halcyon plank]

Rules

9. Do not offer or ask for paid work of any kind.

[shut hazel]

It's not asking for paid work

It's helping build an algorithm trader

But no problem 😇

[haughty mountain]

you have to read the file anyway, so you can't avoid working through the whole data at least once

[thick hazel]

but why? lets say we are given "228"

then we know all the possible words will be between a-c, so we dont have to search the entire data

(list is alphabetically ordered)

[haughty mountain]

it's a file, no?

[thick hazel]

yea but the problem gives u the file as a vector of strings

u dont have to implement that

[haughty mountain]

ok, that's wildly unhelpful in the description then

if you only have one sequence of digits you can binary search for the range of words with valid first letters

but then you just have to check all those words

note that this can't be done if this was actually a file and you have different length words

[thick hazel]

different length words are in the vector yea

[haughty mountain]

so the problem statement is terrible

[thick hazel]

yep kinda haha

heres what i tried

we know the problem can be solved recursively because lets say we have string "228" as input
then if we take the list of letters from a-c, that gives us a new list of valid words and the "new input" would be just "28"

now if we remove the firsst letter from the new list of valid words, we will ahve 3 sorted lists bc thats how alphabetical ordering works

so now we ujst loop thru the list of words that start with "a", "b", and "c" and see what list of valid words we can pull out using the string "28"

that...did not work

it gave me an error called "DEADLYSIGNAL" and at that point i just gave up

(please help me)

(im in pain)

[haughty mountain]

oh, I guess you can just recurse per letter yeah

[thick hazel]

but then why DOES THAT NOT WORK 😭 😭 😭 😭 😭

[haughty mountain]

what is this problem even?

[thick hazel]

this simply isnt working and i feel like its the wrong approach

too complicated

[haughty mountain]

!e

words = [
    'asa',
    'asd',
    'ast',
    'rad',
    'red',
    'sad',
    'sadd',
    'sb',
    'ssa',
    'sss',
    'zyx',
]

letters = {
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz',
}

def bs(l, r, pred):
  # Find first integer in [l, r) where pred is True.
  l -= 1
  while r - l > 1:
    mid = (r + l) // 2
    if pred(mid):
      r = mid
    else:
      l = mid
  return r

def f(i, digits, l, r):
  if i == len(digits):
    for i in range(l, r):
      if len(words[i]) == len(digits):
        yield words[i]
    return

  for letter in letters[digits[i]]:
    lower = bs(l, r, lambda x: words[x][i:i+1] >= letter)
    upper = bs(l, r, lambda x: words[x][i:i+1] > letter)
    if lower < upper:
      yield from f(i+1, digits, lower, upper)

print(list(f(0, '723', 0, len(words))))

[halcyon plank]

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

['rad', 'sad']

[haughty mountain]

@thick hazel

[austere sparrow]

That's even better than "it's for educational purposes"

[summer fossil]

class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
# Step1:
m = len(matrix) #no. of rows
n = len(matrix[0]) #no.of columns

    # Step2: rows = False
    first_row_has_zero = False
    first_col_has_zero = False
    
    # Step3:  
    for row in range(m):
        for col in range(n):
            if matrix[row][col]==0:
                if row == 0:
                    first_row_has_zero = True
                if col == 0:
                    first_col_has_zero = True
                matrix[row][0] = matrix[0][col] = 0
            
            
    # Step4: 
    for row in range(1,m):
        for col in range(1,n):
            if matrix[0][col] == 0 or matrix[row][0] == 0:
                matrix[row][col]=0
            else:
                matrix[row][col]
            
                
    # Step5: 
    if first_row_has_zero:
        for col in range(n):
            matrix[0][col] = 0
    
    if first_col_has_zero:
        for row in range(m):
            matrix[row][0] = 0

Can u plz explain me what is the diff. b/w step 4 and step 5

[fiery cosmos]

how's this for pseudocode

does it get the message throughj

[agile sundial]

hashing requires you to look at all the elements anyways, so it's a waste of time

unless you don't anticipate changing the lists often, then you should store the hashes with the list, not compute it again

[fiery cosmos]

really?

A cryptographic hash function h(·) takes as input any piece of
data x of any size and returns a fixed-size string h(x) (e.g., h(x) is of size 256 bits for
SHA-256).

This is the definition I have been given

in specification

[agile sundial]

that is a correct definition

[agile sundial]

yes

well, it should. it would make for a pretty bad cryptographic hash function if it didn't

and if you're not doing cryptography you can probably get away with a faster, less robust hash function, if you need it like the case i said before

[haughty mountain]

what does h(x) -> h(y) mean?

[haughty mountain]

I don't get why -> is a good symbol for this

this is an equality check right?

[fiery cosmos]

transfer+equality

->=

maybe?

I wanted to show transfer too

it has cost

[haughty mountain]

maybe dumb question, but what does transfer mean here?

[fiery cosmos]

sending hash from one db to the other'

It's db synchronisation checker algorithm

[haughty mountain]

ah, gotcha

is the hash check actually correct? or do you willingly ignore very rare false positives?

hashes are great for verifying things are different quickly, for verifying things are the same hashes aren't great unless you're fine with some rare false positives

[fiery cosmos]

algmyr are you around today? i'd love to get this bitonic TSP script solving the problem

[robust obsidian]

how is the value selected in a knn regressor, I understood how its done for a classifier, you take the k nearest points and choose the most common label, but just averaging in case of a regressor wouldnt really be accurate ?

is it done thru some form of extrapolation ?

[royal trout]

Hello guys can someone help me with some video tutorial or smth like that.For algorithms in pyton for absolutely beginner :))

[robust obsidian]

wrong channel my bad (didnt see the name at the top)

[fiery cosmos]

https://www.youtube.com/channel/UCZCFT11CWBi3MHNlGf019nw

[royal trout]

Thank you so much man

[fervent saddle]

This is how I'm trying to solve Sliding Window Maximum on leetcode:

from itertools import islice
from collections import Counter

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if k == 1:
            return nums.copy()
        
        tree = RBTree()
        iter_nums = iter(nums)
        counts = Counter(-n for n in islice(iter_nums, k))
        for k in counts:
            tree.insertNode(k)
        minimum = min(counts)
        answer = [-minimum]
        
        for left, right in zip(nums, iter_nums):
            if left == right:
                answer.append(-minimum)
                continue
            
            right, left = -right, -left
            if right in counts:
                counts[right] += 1
            else:
                counts[right] = 1
                tree.insertNode(right)
                if right < minimum:
                    minimum = right
            if counts[left] == 1:
                del counts[left]
                tree.delete_node(left)
                if left == minimum:
                    minimum = tree.minimum(tree.root).val
            else:
                counts[left] -= 1
            answer.append(-minimum)
        
        return answer

and I'm using this tree: https://favtutor.com/blogs/red-black-tree-python

and this is the error I'm getting:

AttributeError: 'NoneType' object has no attribute 'color'
    if s.left.color == 0 and s.right.color == 0 :
Line 146 in fixDelete (Solution.py)
    self.fixDelete ( x )
Line 238 in delete_node_helper (Solution.py)
    self.delete_node_helper ( self.root , val )         # Call for deletion
Line 243 in delete_node (Solution.py)
    tree.delete_node(left)
Line 295 in maxSlidingWindow (Solution.py)
    ret = Solution().maxSlidingWindow(param_1, param_2)
Line 342 in _driver (Solution.py)
    _driver()
Line 353 in <module> (Solution.py)

with this data:

[halcyon plank]

Hey @fervent saddle!

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

[fervent saddle]

https://paste.pythondiscord.com/ulerikipez

why?
This is the leetcode problem: https://leetcode.com/problems/sliding-window-maximum/

[fiery cosmos]

thank abdul, he's the 🐐

[severe ravine]

!e

[halcyon plank]

Missing required argument

code

Command Help

!eval [python_version] <code, ...>
Can also use: e

Run Python code and get the results.

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

If multiple codeblocks are in a message, all of them will be joined and evaluated, ignoring the text outside of them.

By default your code is run on Python's 3.11 beta release, to assist with testing. If you run into issues related to this Python version, you can request the bot to use Python 3.10 by specifying the python_version arg and setting it to 3.10.

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

[cerulean river]

Hi I am solving a problem that asks to implement the class, objects and methods for a stack that will be able to output the min and max values in the stack in O(1) time this is my solution:

# Feel free to add new properties and methods to the class.
class MinMaxStack:

    def __init__(self):
        self.minMaxStack = []
        self.stack = []

    def peek(self):
        # Write your code here.
        if self.stack:
          return self.stack[-1]
        return

    def pop(self):
        # Write your code here.
        
        if self.stack[0]
          self.minMaxStack.pop()  
          return self.stack.pop()
        
        return

    def push(self, number):
        # Write your code here.

        if not self.stack[0]:
          self.minMaxStack.append([number,number])
        
        elif number < self.minMaxStack[-1][0]:
          currMax = self.minMaxStack[-1][1]
          self.minMaxStack.append([number,currMax])
        
        elif self.minMaxStack[-1][1] < number:
          currMin = self.minMaxStack[-1][0]
          self.minMaxStack.append([currMin,number])

        self.stack.append(number)
        return

    def getMin(self):
        # Write your code here.
        if self.stack[0]:
          return self.minMaxStack[-1][0]
        return

    def getMax(self):
        # Write your code here.
        if self.stack[0]:
          return self.minMaxStack[-1][1]
        return

the first if statement for the push method seems to be throwing an IndexError: list index out of range . since I am initializing self.stack would it not make sense to check if values have not been pushed already? I have to to maintain my second that which will keep track of the min and max values in O(1) time and space.

[fiery cosmos]

hi! can anyone help me find an O-bound for the running time by using the recursion tree method?

T(n) = 4T(n/2) + O(n log n)

if i've understood it correctly there will be 4 (n/2) from n log n?

[vital scaffold]

In case of 1 2 & 3 i understand the use of self since we are modifying the actual object, but why we need to use self for 4 th ?

[dark aurora]

Does anyone know hot to solve this problem

https://codeforces.com/contest/1737/problem/B

I solved it and I don't know why I get wrong answer

[fiery cosmos]

do we use deque for stack implementation in python?

[agile sundial]

you could. a list works too

[fiery cosmos]

oh. forget this stack nonsense then. and just do pop and append?

wait i wouldnt use append

that goes to the end, i think

so maybe pop and.. ?

[agile sundial]

isn't that what you want your stack to do

cause pop pops from the end

[fiery cosmos]

oh. bet ok great

hmm

ok i have 2 stacks and i have to be able to do a push operation to one or another based on a variable, in the pseudocode its like stack[k]. how could i implement this for my two stack1 = [] and stack2 = []

my gut says i'll need a class or deque? is it possible without this

yeah i feel like i'll need a class attribute

will a != None check against a list allow a while loop to continue if the list is non-empty?

[agile sundial]

no

you would do if the_list or if len(the_list) > 0

[fiery cosmos]

just wrote that out to find out haha thanks

so just like, while list:

[haughty mountain]

stacks = [[], []]
stacks[0].append(...)
stacks[1].append(...)

[fiery cosmos]

🤔

good point

hmm

i must be reading this wrong

heres what i'm trying to implement:

here's my code so far:

stacks = [[],[]] 
    k=0
    i=n-2
    j=n-1
    while j>0:
        stacks[k].append(j)
        j=N[i][j]
        if j < i:
            i,j = j,i
            k = 2-k
    stacks[1].append[0]
    while stacks[2]:
        stacks[1].append(stacks[2].pop())
    T=[[0]*n for _ in range(n)]

[haughty mountain]

k=2-k is wrong

and stacks[1].append[0] is an error

[fiery cosmos]

they use 1 based indexing

the idea was make it 1 less

is that incorrect

[haughty mountain]

think through the operation

[fiery cosmos]

ok ok

[haughty mountain]

k=0 and apply your operation, what do you get?

and what do you want to get?

[fiery cosmos]

well the n stuff won't work as it is from higher up in the script where n=len of input array

[haughty mountain]

execute the one line in your head, dammit

k=0

k = 2-k

what is k?

what should it be?

[fiery cosmos]

ah it cannot oscillate now

[haughty mountain]

it will oscillate

[fiery cosmos]

2-0 = 2

[haughty mountain]

what do you want the value of k to jump between?

[forest oxide]

hello someone help me to make a menu in pydroid 3?

[fiery cosmos]

0 and 1

[haughty mountain]

and what expression would make that happen?

x = ??? - x

||x = 1 - x||

in general to swap between a and b you can do ||x = a + b - x||

[static zenith]

Hello my name is Sami, im french and i have a homework with python but i have a probleme. Someone can help me please ?

i dont know why i dont have result

[lean walrus]

You cant return value from global scope. You should use print(vn)

[static zenith]

Thank you very mutch

but now he tell me no module is named matplotlib and that's false

I tried also : import matplotlib.pyplot as plt

and this is doesn't work

[static zenith]

I tried with another software

[hybrid epoch]

pip install matplotlib

[fiery cosmos]

what would a proof to prove the correctness of a graph traversal algorithm look like? for example, with sorting algorithms, we can do an inductive proof to prove correctness on arbitrarily large input with showing the math works out on the runtime complexity expression for the n and n+1 forms, hence proving true for all n. however, what would a proof look like to prove correctness of a graph traversal algorithm? it outputs both a path and a distance. i know the recurrence relations that characterize the algorithm's runtime (their mathematical expressions).

it takes as input a series of points in the euclidian plane

[reef trout]

Does data and algos make us problem solving much better

[gusty rock]

I still don't get the concept of yield keyword. Can anyone help me with this

[hybrid epoch]

Tldr; yield creates generators. Supposed you have a list a of 10e9 elements. Without yield, Python will copy all 10e9 elements to memory and do operations on it. With yield, only the elements up to the current index i are copied into memory

[fiery cosmos]

I'm unable to solve a question in python

I come from rust

It is a decoding question

Given a string, you have to decode it.

it is already encoded this way:
college -> ceoglel
sequence:
first char, last char, second char, second last char....

Input:
ceoglel
output:
college

[haughty mountain]

ok, try following where the characters end up in the output

or better, start with a sequence like
[0, 1, 2, 3, 4, 5, 6]
and see what happens

it becomes: ||[0, 6, 1, 5, 2, 4, 3]||

hint ||consider odd/even indices separately||

[fiery cosmos]

in python you can also do -1, -2 as last and second last indexes. That might be helpful for you too

[fiery cosmos]

wow that was helpful thanks

[vale smelt]

could anyone help me determine the time complexity of my code?

[agile sundial]

what code?

[bronze sail]

Should I use deque with pop append, or list to modify params? Trying to optimize loops

from collection import deque

"Prepare 1"
stack = deque(maxlen=1000)
stack.append(("Key1", 0))
"Solution 1"
k,_ = stack.pop()
stack.append((k, 2)) # adding new number


"Prepare 1"
stack = deque(maxlen=1000)
stack.append(["Key1", 0])
"Solution 1"
stack[-1][1] = 1

[agile sundial]

modifying will probably be faster. why not measure it?

[bronze sail]

ye I did

!e

from collections import deque
import time


def measure_time_decorator(func):
    """ Function times measured with `perf_counter`. Wraps used."""

    def wrapper(*a, **kw):
        time_start = time.perf_counter()
        out = func(*a, **kw)
        duration = time.perf_counter() - time_start

        if duration < 1e-3:
            txt = f"{duration * 1000000:>4.2f} us"
        elif duration < 1:
            txt = f"{duration * 1000:>4.2f} ms"
        else:
            txt = f"{duration:4.2f} s"

        print(f"{func.__name__} elapsed in: {txt}")

        return out

    return wrapper


@measure_time_decorator
def test1(N):
    stack = deque(maxlen=20)
    stack.append(("key", 0))
    for i in range(N):
        stack.append(("key", i))


@measure_time_decorator
def test2(N):
    stack = deque(maxlen=20)
    stack.append(("key", 0))
    for i in range(N):
        stack[-1] = ("key", i)


@measure_time_decorator
def test3(N):
    stack = deque(maxlen=20)
    stack.append(["key", 0])
    for i in range(N):
        stack[-1][1] = i


if __name__ == "__main__":
    N = int(1000_000)
    test1(N)
    test2(N)
    test3(N)

[halcyon plank]

@bronze sail :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | test1 elapsed in: 126.08 ms
002 | test2 elapsed in: 118.59 ms
003 | test3 elapsed in: 70.81 ms

[bronze sail]

this order does not change

as I though

[austere sparrow]

depends on how long the deque is

internally, it's a linked list of small (64-long) arrays

so if your deque is 64 or smaller, it's going to behave like a list

[fiery cosmos]

hi, how do i do a recursion tree with O(n log n)?

[lunar jacinth]

def getMinMax(low, high, arr):
    arr_max = arr[low]
    arr_min = arr[low]
 
    # If there is only one element
    if low == high:
        arr_max = arr[low]
        arr_min = arr[low]
        return (arr_max, arr_min)
 
    # If there is only two element
    elif high == low + 1:
        if arr[low] > arr[high]:
            arr_max = arr[low]
            arr_min = arr[high]
        else:
            arr_max = arr[high]
            arr_min = arr[low]
        return (arr_max, arr_min)
    else:
 
        # If there are more than 2 elements
        mid = int((low + high) / 2)
        arr_max1, arr_min1 = getMinMax(low, mid, arr)
        arr_max2, arr_min2 = getMinMax(mid + 1, high, arr)
 
    return (max(arr_max1, arr_max2), min(arr_min1, arr_min2))
 
 
# Driver code
arr = [1000, 11, 445, 1, 330, 3000]
high = len(arr) - 1
low = 0
arr_max, arr_min = getMinMax(low, high, arr)
print('Minimum element is ', arr_min)
print('nMaximum element is ', arr_max)
 

How is this 3n/2- 2?

[gleaming tapir]

Hello everyone,

I'm working on simple Towers of Hanoi problem.

I've solved it simply using strings:

steps = 0

def print_transaction(n, source, target):
  global steps
  steps += 1
  print(f"{steps}. Moving {n} from {source} to {target}")

def tower_of_hanoi(n, source, auxiliary, target):
  # print_current_state(source, auxiliary, target)
  if n == 1:
    print_transaction(n, source, target)
    return

  tower_of_hanoi(n-1, source, target, auxiliary) 
  print_transaction(n, source, target)
  tower_of_hanoi(n-1, auxiliary, source, target)  

tower_of_hanoi(3, "A", "B", "C")

Now I want to solve it using stacks (using lists actually) but it's not working as intended. Can you give me any directions based on my code:

class Tower:

  def __init__(self, number_of_disks = None):
    self.a_rod = self.fill_the_rod(number_of_disks)
    self.b_rod = list()
    self.c_rod = list()


  def fill_the_rod(self, input_size_of_pile = None):
    if input_size_of_pile is None:
      input_size_of_pile = int(input("Enter the number of disks: "))
    return list(range(1, input_size_of_pile + 1 ))

  def sort(self, source, auxiliary, target):
    disk = source.pop()
    if disk == 1:
      target.append(disk)
      self.print_current_state()
      return
    
    self.sort(source, target, auxiliary) 
    target.append(disk)
    self.print_current_state()
    self.sort(auxiliary, source, target)  

  def print_current_state(self):
      print("_______________________________")
      print(f"A Rod: {self.a_rod}")
      print(f"B Rod: {self.b_rod}")
      print(f"C Rod: {self.c_rod}")


tower = Tower(num_of_disks)
tower.print_current_state()
tower.sort(tower.a_rod, tower.b_rod, tower.c_rod)

[bronze sail]

thats some efficency scam!

[agile sundial]

probably faster even, because no resizing

[ivory yacht]

It's slightly cleverer than that actually. They are allocated in 64-item blocks, but unlike lists the first block can have unused slots at the start. Popping from the left will simply increment an offset value, until that block is completely empty and we can move to the next. If you're pushing on one end and popping on the other, it'll reallocate the block every 64 items.

[gleaming tapir]

Anyone?

[glossy mulch]

can't you just check if front-rear == -1 or something?

[glossy mulch]

your problem is that target.append(disk) belongs BEFORE the first self.sort

you need to obey hanoi's rules- you can't pop from ANY source until you've appended the piece you took off back on.

so
quick question
how efficient is deque reversal?
i want the most efficient object for stack-like behavior (list insert(-n)/pop(-n) for small n) with the most efficient full reversal (.reverse())

nvm i finally found the docs

deque access is approximately O(1) on the edges and O(n) in the middle which is a general slowdown over lists for my usage

[gleaming tapir]

@glossy mulch thanks for the feedback. I'll try to fix it.

But... if I put it before the first sort then it will just take that item from the list and add back all the time

and that's what I get:

_______________________________
A Rod: [1, 2, 3]
B Rod: []
C Rod: []
_______________________________
A Rod: []
B Rod: [2]
C Rod: [3, 1]
_______________________________
A Rod: []
B Rod: [2]
C Rod: [3, 1]
_______________________________
A Rod: []
B Rod: [2, 1]
C Rod: [3]
_______________________________
A Rod: []
B Rod: [2, 1]
C Rod: [3]
_______________________________
A Rod: []
B Rod: [2]
C Rod: [3, 1]

[midnight sorrel]

Hey, I have a logical assessment, and I'm unsure how to do it.

Let's say you are in a high-rise building and at the bottom there are 27 wires and 27 wires at the top
each of these wires are paired bottom-top.
You can connect wires as you like and make as many groups as you want
You have a multi-meter which will light up if you connect 2 wires and they are connected on the other end as well.

You have to find these pairs and label them with least trips from bottom to top and from top to bottom.
How do you do it and what's the final trip count? 

The answer should be 2 trips, but I really don't know how.
Could you help me please?

[glossy mulch]

not quite since you're using the stacks in a different order

assume an initial sort call with:
s, a, t = [3,2,1], [], []
a proper hanoi game advances...
s, a, t = [3,2], [], [1]
call (s, t, a)
s1, a1, t1 = [3,2], [1], []
s1, a1, t1 = [3], [1], [2]
call (s1,t1,a1)
s2,a2,t2 = [3], [2], [1]
s2,a2,t2 = [], [2], [1,3]
wrong

which means the entire sort paradigm is wrong

instead what you'll want is an additional target parameter that tells it which term in the list it wants to move from source to target.

i, s, a, t = 3, [3,2,1], [], []
with this initial state, observe the action sequence
i, s, a, t = 3, [3,2,1], [], [] : s does not begin with 3. delegate with item=s[s.index(3)+1], swapping a & t
i,s,a,t = 2,[3,2,1],[],[] : likewise.
i,s,a,t = 1,[3,2,1],[],[] : pop item and send to target.
i,s,a,t = 1,[3,2],[],[1] return
i,s,a,t = 2,[3,2],[1],[] : pop item and send to target.
i,s,a,t = 2,[3],[1],[2] : pull items from a to t, to clean up. do this by calling with target = a[0]
i,s,a,t = 1,[1],[3],[2]
i,s,a,t = 1,[],[3],[2,1] return
i,s,a,t = 2,[3],[],[2,1] return
i,s,a,t = 3,[3],[2,1],[] pop item and send to target.
from here, you get the idea

which is to say, your idea is really close already, but you need an additional target parameter so that your code can know what you're even trying to do

[gleaming tapir]

yeah I was thinking about it. Thank you so much. I'm gonna try it.

[thick hazel]

hey man sorry for the lat response

but a) thank you

b) can u explain the code? still a bit confused

[haughty mountain]

binary search to find the valid intervals for each possible letter, then recurse for the next letter

[fiery cosmos]

hey whats the summation (n-1)(n-2)/2 i can't remember

is it from n=0 through n-1?

[haughty mountain]

try for some low n 😛

[fiery cosmos]

good look

[haughty mountain]

n=2 -> 0
n=3 -> 1
n=4 -> 3
n=5 -> 6

[thick hazel]

so find first integver in which pred is true means l = lower, r = upper, pred = letter that u want?

[haughty mountain]

so I have an array where my predicate value goes

[False, False, False, ..., False, True, True, ..., True]

I want to find that transition point

[thick hazel]

ahhh okok

[haughty mountain]

to find what the first/last element in my range is

(and I define my range in the python sense with the right index being one larger)

because that's nicer to work with

[thick hazel]

Ahhh okok

[thick hazel]

Can u explain the lambda statements?

[haughty mountain]

re-posting code so I don't have to scroll up

words = [
    'asa',
    'asd',
    'ast',
    'rad',
    'red',
    'sad',
    'sadd',
    'sb',
    'ssa',
    'sss',
    'zyx',
]

letters = {
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz',
}

def bs(l, r, pred):
  # Find first integer in [l, r) where pred is True.
  l -= 1
  while r - l > 1:
    mid = (r + l) // 2
    if pred(mid):
      r = mid
    else:
      l = mid
  return r

def f(i, digits, l, r):
  if i == len(digits):
    for i in range(l, r):
      if len(words[i]) == len(digits):
        yield words[i]
    return

  for letter in letters[digits[i]]:
    lower = bs(l, r, lambda x: words[x][i:i+1] >= letter)
    upper = bs(l, r, lambda x: words[x][i:i+1] > letter)
    if lower < upper:
      yield from f(i+1, digits, lower, upper)

print(list(f(0, '723', 0, len(words))))

so what I want to do is to look at the ith letter and find the first/last word that has the letter I'm looking for

the [i:i+1] slicing is there so I don't have to worry about words ending early, e.g.

s = "asd"
s[1:2]  # "s"
s[1]    # "s"
s[3:4]  # ""
s[3]    # Error

other than that, I'm looking for the first time a particular letter appears, and the first time something greater than it appears

for the first part I'm looking for the first time something it >= letter for the second part the first thing > letter

[burnt wind]

hey) I hope this link help u https://stackoverflow.com/questions/3344115/how-to-obfuscate-python-code-effectively 🙂

[haughty mountain]

as an example, looking for letter = 's' for i=0 (the first letter in the words) I will find

words = [
    'asa',
    'asd',
    'ast',
    'rad',
    'red',
    'sad',  # <- lower = 5
    'sadd',
    'sb',
    'ssa',
    'sss',
    'zyx',  # <- upper = 10
]

everything in range(5, 10) starts with an "s"

now I can focus in on that range and look at the second letter (that's the recursion)

[thick hazel]

ahhhhhhhhhhh

okokok

yea so ur basically doing what i did but i see why i had an issue now

[thick hazel]

cause of this

i didnt think of the lambda or sliving thing

recursion so hard to debug on god 😩

[haughty mountain]

the lambda is just so I can re-use my binary search code

so I don't have to write it twice

and you can totally do this without the slicing, it's just an annoying edge case to deal with

[thick hazel]

oh u do the binary search non recursively

[bronze sail]

Can you use regex?

[haughty mountain]

for this task regex wouldn't be a good idea, the point is to not try to check all words

[thick hazel]

@haughty mountain i feel like im missing smthng crucial...doesnt the lambda function go thru each element in the words list?

[haughty mountain]

no, why would it?

the lambda is just the function that the binary search uses to check "is the condition true for the thing at position x?"

[thick hazel]

i didnt know that, ty

[haughty mountain]

the binary search for sure will not look at every element

[bronze sail]

ye I don't quite understand the problem

also regex can work on lines

🤔 but then not sure if you could scrap line number from it

why letters are dict ?

[haughty mountain]

so you have a sequence of digits 1-9, on old phones every digit corresponds to a few letters, so we're curious what words in the list would match such a sequence

the word list is given as a list of strings in sorted order

and yes, you can do better than just going through all the words in the list and applying a regex to each word

[bronze sail]

you read words or numbers?

you want to get number sequence in return?

maybe reversed dict?

!e

words = [
    'asa',
    'asd',
    'ast',
    'rad',
    'red',
    'sad',
    'sadd',
    'sb',
    'ssa',
    'sss',
    'zyx',
]
letters = {
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz',
}
letters_back_dict = {sub_let : key for key,val in letters.items() for sub_let in val}

print(letters_back_dict)
for word in words:
  pattern = [letters_back_dict[let] for let in word]
  print(word, pattern)

[halcyon plank]

@bronze sail :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | {'a': '2', 'b': '2', 'c': '2', 'd': '3', 'e': '3', 'f': '3', 'g': '4', 'h': '4', 'i': '4', 'j': '5', 'k': '5', 'l': '5', 'm': '6', 'n': '6', 'o': '6', 'p': '7', 'q': '7', 'r': '7', 's': '7', 't': '8', 'u': '8', 'v': '8', 'w': '9', 'x': '9', 'y': '9', 'z': '9'}
002 | asa ['2', '7', '2']
003 | asd ['2', '7', '3']
004 | ast ['2', '7', '8']
005 | rad ['7', '2', '3']
006 | red ['7', '3', '3']
007 | sad ['7', '2', '3']
008 | sadd ['7', '2', '3', '3']
009 | sb ['7', '2']
010 | ssa ['7', '7', '2']
011 | sss ['7', '7', '7']
... (truncated - too many lines)

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

[bronze sail]

and then you can check sequences

just store patterns in set for fast checking during in

[haughty mountain]

you are looping through all the words

that could be expensive

consider if you had a huge list of words

you only care for a very small handful

the point is that you can solve this without looping through all the words, making use of the fact that the strings are sorted

as a silly simplified example, if I have a big sorted wordlist and I'm curious if a word is in it, looping through all the words would be a waste

you can binary search for it

which is in the end what you do in the more complicated version with the digits

[bronze sail]

i though you got more sequences

[oak lintel]

rq how would i print this https://paste.pythondiscord.com/nakicuhisi

[bronze sail]

?

[oak lintel]

the error im getting is node is not defined\

[bronze sail]

init has double lines __init__

also errors are pretty accurate, just read them from bottom to top

dont do ==None do is None

this code confuses me, it looks like you mixed linked list methods that should be in node

im talking abotu insert_after you assign same node both to head and tail which is baaad...

this too oop this problem could be solved with 2 dicts I think

class LinkedList:
  def __init__(self):
     self.links = {}
  def add_edge(parent_id, child_id):
    if parent_id not in self.links:
      self.links[parent_id] = set() # or list but sets are hashable
    self.links[parent_id].add(child_id)
    "You could do also operation for storing reverse links in separated dict"

num_list = LinkedList()

num_list.add_edge(50, 60)

[fiery cosmos]

        queue = deque([(target, 0)])
        seen = {target}
        while queue:
            if queue[0][1] == k:
                return [node.val for node, d in queue]
            node, d = queue.popleft()
            for nei in (node.left, node.right, node.parent):
                if nei and nei not in seen:
                    seen.add(nei)
                    queue.append((nei, d + 1))

what do you think nei is short for?

[round glacier]

why does amazon always send me these super hard questions

lol

[hybrid epoch]

Neighbor

[fiery cosmos]

OF COURSE ty

[bronze sail]

Node edge index?

Dunno xd

[tight parcel]

Does anyone know how I can get all the possible combinations of this problem?

Its the staircase problem where I can only do 1 - 2 steps to get to the top of the staircase with the size of n

I know how to get the total combinations...

I just dont know how to make the loop to print out all the possible combinations

[haughty mountain]

you don't want to print all combinations

you just want to count them

[tight parcel]

No like the photo I sent is from leetcode

and its asking for the total amount of unique combinations

in my case... for one of my assignments

I want to have a loop that prints all of them out

I just dont know how to 😭

and ive been trying for the past 2 hours

[haughty mountain]

that's kinda ridiculous since the number of solutions grows exponentially with n

[tight parcel]

Do you know how I can read up the tree?

So in this image... I just need to print out the path of the green circles (where its equal to 5)

and go up the tree to where its zero

so for instance the very left... to get from 5 --> 0 it is...

+1 + 1 +1 +1 +1

And then the next green circle to the right would be...

+2 +1 +1 +1

and the third one from the left would be...

+1 +2 +1 +1

and so on

😭

[haughty mountain]

just do it recursively?

[tight parcel]

Do you know how it would look?

Sorry im new to all of this in general 😭

Is there like an external resource guide I can use? cause tbh idk what to enter in google

to search

[haughty mountain]

the recursion is basically just trying to take 1 step (one recursive call) or 2 steps (another recursive call)

[zinc storm]

How can I sort a list with string values as elements?

[agile sundial]

the same way you sort any other list. sorted, .sort

[zinc storm]

Can you tell me a way of doing it without these built in functions?

I need sort a list in alphabetical order

[agile sundial]

implement your own, then

[agile sundial]

the builtins can do that

[hybrid epoch]

Lexicographically or alphabetically? Either way, implement quick sort. Do a comparison like:

ord(arr[i]) < ord(pivot)

In the partition function. If you can't use the built-in ord function, then create a dictionary where you assign increasing numeric values to each letter in the alphabet and use that instead

[fiery cosmos]

how do y'all interpret this pseudocode:

its just an array of arrays of the same 1 .. m values yeah

[fiery cosmos]

can someone help me understand dp tables better

[opal oriole]

Consider computing the first 20.

You can make a table with length 20, and fill in the first two values with 0 and 1.

Then go left to right.

You are building up values from previous sub-problem values. Starting at the bottom and going up (bottom-up).

Tracking values of the recurrence relation of the problem.

[fiery cosmos]

right right bc then rather than recomputing each time you are simply looking up what the F_i-1 and F_i-2 values are

most of the dp tables i've come across are like n*n, what is the reason for this

[opal oriole]

If you look at the recurrence you will see why.

[fiery cosmos]

hmm ok. i'm trying to solve a string-cutting problem rn

given a string s of len(s), determine the minimum cost to cut it at prespecified places. the cost may be different if you cut from right to left, left to right, or some combination. this is bc for each cut you must copy the existing length string over again

[opal oriole]

I gtg. I recommend trying these steps:

https://www.youtube.com/watch?v=aPQY__2H3tE

[fiery cosmos]

ok thank you

[opal oriole]

DP has a way of being nicely formulaic to solve.

When you get used to it.

(Identifying that the problem has a DP solution can be hard)

[fiery cosmos]

the directed acyclic graphs in the video make for nice visualizations of a given solution

[haughty mountain]

identifying how to twist the problem into being a nice dp formulation is hard, yeah

[fiery cosmos]

i think whats tripping me up is like string index shifting. maybe i don't need that.

maybe i don't need the indices i mean

i don't think i do

gonna try writing cut left and cut right functions

just gotta understand the table

clearly its going to be some sort of lookup previous cost of cuts approach

[fiery cosmos]

i don't understand this problem at all. they don't specify which bit of the string you are doing away with

found this:

[fiery cosmos]

also:

[fiery cosmos]

i think im not understanding the table

[fiery cosmos]

how can i use these statements above to design a dp algo

its the string cutting problem

is it the same or different than the rod cutting problem?

looks like there is a leetcode version of the problem as well

[fiery cosmos]

ok i have a working version of the algo i just need someone to walk through it w me in python tutor

[thick hazel]

out of curiosity, how would u implement this without lambda function?

like now im just wondering what would happen if i tried to code the same thing but in, say, c++

[keen ibex]

Got a question for anyone who can help:
Can I reverse engineer a structure? Meaning if I have a structure with a data type, and a reference to the data type, can I use the reference to the data type to return the structure?

[haughty mountain]

C++ has basically this function already, it's called std::partition_point and takes a lambda

[haughty mountain]

obviously you could just inline the logic in the lambda, so you write the same while loop with a slightly different check inside

the point of passing a lambda/function is that I don't have to repeat the same binary search structure multiple times

[vocal gorge]

i wonder if c++ inlines the lambda into the function when compiling

[opal oriole]

Sometimes (often, also depends on optimization settings/flags).

[haughty mountain]

often yes

or rather, it inlines the function which allows inlining the lambda

[azure osprey]

How do I make a list slice modify the original list?

a = [0, 1, 2, 3, 4, 5, 6, 7, 8]
slice_of_a = a[1:4]
slice_of_a[1] = 9    # This should modify a[2] somehow
assert a == [0, 1, 9, 3, 4, 5, 6, 7, 8]

List elements in my case are mutable, but how can I do something like appending to the slice and it changes the original list?

Came across https://stackoverflow.com/a/31443874, any better solution?

[wanton dawn]

guys

im doing my masters and need to start preparing data structures and stuff , do you recommend learning basics from leetcode/algoexpert/educative .. and also im looking for a study partner if anyone interested

[haughty mountain]

you could make your own list slice type, but that's probably more work than you would want to do

[azure osprey]

#software-architecture message

quite a discussion there

[fiery cosmos]

masters in what

[fiery cosmos]

see channel pins for MIT course

hey all,
i have two different DP algos to solve the same problem, they print the same solution for one case but not another. how can i solve which one is the proper algo??

that is, which one gives the true answer in all cases

i'm also trying to understand all the variables in each case if anyone has some time

[haughty mountain]

if the case is small you could solve it by hand or write a brute force solver