algos-and-data-structs

[half lotus]

I think the problem solving/critical thinking skills are transferable even if the direct problem is not.

No sense in thinking about that anyway. Reality is that interviewers ask this so you need to know it to get through

[round glacier]

elif price - min_price > max_profit:

this part for example in my code above

should probably be cleaned up a bit more

its not obvious why we are taking price - min_price

you know?

that could be put into a function

is_profit_gained()

would be nicer i think

[half lotus]

I disagree. It would be too much abstraction for a simple problem.

[round glacier]

it can be, but i prefer english

lol

really just personal choice i feel

[half lotus]

# Check if the current profit is the new maximum.
current_profit = price - min_price
if current_profit > max_profit:
  ...

is better

[round glacier]

yeah i thought aabout that as well

[rare musk]

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        
        int max_profit=0,min_profit;
        
        for(int i=0;i<prices.size();i++)
        { 
            min_profit = min(min_profit, prices[i]);
            max_profit = max(max_profit, prices[i]-min_profit);
        }
        
        return max_profit; 
    }
};

[round glacier]

I don't like how you wrote the two integers in one line like that

and there's no spacing in your for loop

or your min/max functions

You should clean that up

[round glacier]

Also, why not replace the for loop with ranged-based for loop?

[rare musk]

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        
        int max_profit=0
        int lowest_price;
        
        for(auto i : prices)
        { 
            lowest_price = min(lowest_price, i);
            max_profit = max(max_profit, i - lowest_price);
        }
        
        return max_profit; 
    }
};

[round glacier]

for (int price : prices)```

[half lotus]

min_profit is a misnomer. It's not storing a profit. It's just a single price.

[round glacier]

yeah thats much cleaner lol

int max_profit=0,min_profit;

replace this with this

nvm u got it lol

[rare musk]

damn this is a harsh code review here

but i'm thankful i'm learning

[round glacier]

lol

I'm doing a review basically what my boss would do to me 😄

hahaha

I also believe that like 90% of these people making coding algorithms are doing it wrong

Like why use C++?

C++ is so verbose

Python/Ruby is what you should be using

[rare musk]

Disagree

[half lotus]

Use what you're most familiar with

You don't want to waste time looking up how to do basic things

[round glacier]

i guarantee you that you will spend more time doing c++

than if u knew python/ruby

yes, you will take longer to "learn" a new language, but if you took the time to learn that language, long term, you would be more productive

[rare musk]

C++ suits me personally better to learn fundamental CS concepts. In addition to that, the industry I'm trying to get in uses C++ as it has the highest performance.

[round glacier]

C++ is not good for being productive

[rare musk]

Depends on what your goal is, no? As long as you don't have to look up syntax bs all the time as @half lotus said

[round glacier]

I mean being an efficient and productive programmer is important to getting promotions at your job

As you move up past senior, it becomes less about "what you do" and more about "how you unblocked and helped your team do things easier"

[rare musk]

You do know that there are industries where python is just not sufficient due to lack of performance?

Financial industry, specifically in the trading space uses primarily C++ and q/kdb

[round glacier]

I work in gaming. We use C++, Rust, C#, and Python.

[opal oriole]

C++ and Python are both good for being productive, and you can combine them.

[round glacier]

Python is heavily used

I think Rust is a superior language to C++/C

There's almost no reason to use C++ anymore

[rare musk]

Disagree

Don't focus solely on gaming.

[round glacier]

It's 30 years old

Rust can do everything C++ can do

And Rust even outperforms C

In many algorithm tests

[rare musk]

There are certain cases where you need something faster than Python or Rust

[round glacier]

Rust is faster than C/C++

[rare musk]

No, otherwise the UHFT (ultra high frequency trading firms) would use it

They don't, they use C++. Because it is faster

[round glacier]

That's just because their code is probably old as shit lol

[rare musk]

nope

[round glacier]

Rust allows reaching a higher-level performance in comparison to C++ because of its better safety standards that decrease the development process cost. For example, to ensure faster operation, C++ does not have automatic garbage collection tools, which might contribute to multiple runtime errors.Jun 9, 2021

literally just google it bro lol

Rust is faster in 4 of the benchmarks, C++ is faster in 3 of them, and they're basically identical in 3 of them.

Performance of rust is either superior, or equal to C/C++

in almost every benchmark

Rust achieves the same speed while guaranteeing memory safety and thread safety, doesn’t need error handling, doesn’t need null checks...being easier to debug, maintain, etc. The only thing it actually loses at (by a long shot) is compile time.

[rare musk]

Brother I respect your opinion and even agree that you can use Python or Rust for the vast majority of cases (and performance is equal while having easier to read code). But the only reason these firms use C++ is because it is literally faster. They optimize it in ways we don't even know

It's a fact that they can use it in a way that is faster than Rust

[round glacier]

its not an opinion

its fact

Rust beats C/C++ in almost every benchmark

This isn't really up for discussion

[rare musk]

almost

[round glacier]

it does

You should learn Rust

don't fight it lol

its a great language

and you will love it

[rare musk]

I'm willing to and will probably

But first C++ because it is widely used in high frequency trading (because it's faster)

They optimize it in various ways like running it solely on hardware and other stuff.

Don't you think they'd use Rust if Rust was faster?

[round glacier]

No

Companies use whatever their engineers know

And Rust is still a new language

Companies take a long time to change their habits

lol

[rare musk]

Lmao they'd use Rust immediately if it was faster

[round glacier]

Takes like 10-20 years

No they wouldn't.

You don't know what you're talking about

It takes time to train people, hire them, and learn best practices

[rare musk]

Give me a second to explain, you don't know what I'm referrring to

Look

In high frequency trading literal micro to even nanoseconds decide whether you get the trade or not

Companies spend hundreds of MILLIONS of dollars in order to reduce latency

[round glacier]

I don't think you know what you're talking about

[rare musk]

If they're able to send a order to the exchange a couple microseconds faster, then they'll outcompete their rivals and literally gain millions from it

If Rust was faster in this circumstance, they would use it immediately. Some of the smartest people in the world work for such UHFT firms or market makers.

You think they wouldn't figure it out?

[cloud plover]

are we still on the topic of algos and data structs?

[rare musk]

In this specific use case C++ is superior, that is a fact.

[round glacier]

no, probably shouldnt talk about this anymore lol

sorry

[round glacier]

    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0

        for amount in range(1, amount + 1):
            for coin in coins:
                if amount - coin >= 0:
                    dp[amount] = min(dp[amount], 1 + dp[amount - coin])

        return dp[amount] if dp[amount] != amount + 1 else -1```

Found this solution online

Anyone know how to write this so it's more intuitive to understand?

https://leetcode.com/problems/coin-change

[half lotus]

How about this ```py
def coinChange(self, coins: List[int], amount: int) -> int:
# The index is the amount.
# The value is the smallest number of coins needed for that amount.
coins_per_amount = [amount + 1] * (amount + 1)

# As a base case, an amount of 0 trivially requires 0 coins.
coins_per_amount[0] = 0

# Determine the fewest coins needed to reach each amount, starting at the smallest amount.
for amount in range(1, amount + 1):
    for coin in coins:
        deficit = amount - coin

        # If the deficit is negative, then the current coin can't be used;
        # it would go over the current amount needed.
        if deficit >= 0:
            # Does using the current coin result in fewer coins used than the previously known
            # minimum for this amount?
            coins_per_amount[amount] = min(coins_per_amount[amount], 1 + coins_per_amount[deficit])

if coins_per_amount[amount] == amount + 1:
    # The number of coins for the target amount is still at its default value.
    # Thus, it's impossible to reach with any combination of coins.
    return -1
else:
    return coins_per_amount[amount]

[round glacier]

I like that

[rare musk]

At what level were you after several months? Have you been able to solve mediums consistently?

[round glacier]

where did u find ur study bro

[half lotus]

I don't remember by now. That was almost two years ago. I think it was a 3 month span during fall 2020. Doing 2-3 problems 5 days a week.

I doubt I was able to consistently solve mediums.

Maybe like 60%-75% success

[round glacier]

If I dont' get promoted in the next year, I'm going to start looking for a new job.

So I would like to get a study buddy

lol

I want to get up to making 300k+ salary

my total compensation is like 115k righbt now

which is tooo low

[half lotus]

I started practicing again last month and I definitely forgot things. Revisited problems I did 2 years ago and couldn't remember the approach.

[round glacier]

yeah

i feel you lol

what do you do for work?

[half lotus]

Nothing I'm looking for a job right now 😄

[rare musk]

Thats very good. I think FAANG is possible with such a quota(maybe with luck? but thats always needed). From what I've heard they ask easy-mediums.

[round glacier]

FAANG pays less than the gaming industry

Believe it or not lol

You hear all this bad stuff about gaming paying low, it does pay low... At the junior/entry level positions.

[half lotus]

Well this is more of a #career-advice topic

[round glacier]

But when you get to senior+ its actually more, or equal

[rare musk]

Wow for real? I have never heard about that

And the graduate pay is so low because too many applicants?

[round glacier]

Last thing I'll say, it's basically higher at the more senior level because we get royalties + stocks + base salary

Most FAANG companies don't give royalties

They just give salary + rsu's

[half lotus]

On reddit. They were the ones looking actually, not me. I just figured it'd be a good opportunity for me to practice too.

[tacit nova]

'lists' is bunch of linked lists in an array like this
[
ListNode{val: 1, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}
ListNode{val: 1, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}}
]

anyone know why this doesn't work

for l in lists :
    heapq.heappush(heap, (l.val, l) )

but why this work ?

NODE = ListNode(0)    
for l in lists :
    heapq.heappush(heap, (l.val, NODE) )

the error

TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'

[jolly mortar]

tuples are compared elementwise, so if there's a tie on the l.val, it then tries to compare the second elements

[tacit nova]

make senses ... i will look into this, ty

but why wait would NODE = ListNode(0) works ?

[slender light]

difference = lambda x: abs(x - mean)
res = min(x, key=difference)

can anyone tell me how this code works

x is an iterable here and mean is the mean of the elements in x

[haughty mountain]

you could make it even cleaner using max and min rather than the if statement

max_profit = max(max_profit, price - min_price)
min_price = min(min_price, price)

[haughty mountain]

the section this is from has almost nothing to do with runtime performance

[haughty mountain]

and the reddit post this is from doesn't support your point either, if you actually read more than the first line

Rust is faster in 4 of the benchmarks, C++ is faster in 3 of them, and they're basically identical in 3 of them.

While strictly mathematically, Rust wins in more of them (4 out of 10 vs 3 out of 10), this is not that strong of a proof of anything. If you count the C implementation of regex-redux as achievable by C++, it makes it even. Both languages have their merits, but basing any blanket statements about performance on microoptimized code filled with non-standard language extensions (omp and other libraries in the C++ code) can lead you to false conclusions.

The reasonable answer would be - profile the code from both languages, find where their bottlenecks are and determine whether it's reasonably fixable in the given language. Rust can have some interesting guarantees via borrow checker, C++ has stronger compile-time programming capabilities (AFAIK) so it depends on which attribute has a bigger impact.

It would be more interesting to compare how equivalent solutions, both written with idiomatic usage of the language, compares

e.g. no manual simd, avoid unsafe rust

from my experience writing both they are comparable in runtime performance

[low rampart]

Guys is there any material which will help for understanding and implementing ADTs

?!

[tacit nova]

hey yo I just wanted to say i found a fix for that situation https://leetcode.com/problems/merge-k-sorted-lists/discuss/465094/Problems-with-Python3-and-Multiple-Solutions
at line "Here are the two ways"

[jolly mortar]

👍

[flat sierra]

👌

[rare musk]

💯

[opal oriole]

Problem is that it's idiomatic in C and C++ to end up with something more low level / complex for speed. Idiomatic is often taken as "leaving it at the bad solution", which kind of defeats the purpose of both C++ and Rust, in that you can make it as fast as it possibly could be (since you can even do inline assembly), while in other higher level languages you can't, not without switching to C/C++/Rust (e.g. Python calling into a C library / its own implementation like CPython). So it depends on what you consider "idiomatic" and how fair that really is (is it throwing away the languages' possibilities / purpose?).

(It's more about what you CAN do (with reasonable effort), when arguing for using a lower level language)

[final thunder]

Could anyone recommend some reading for time and space complexity analysis? Pretty easy to figure out linear, quadratic, etc complexity but when there is an inherent tree or graph structure I sometimes make mistakes.

[opal oriole]

(Although the answer for C vs Python is BOTH (need consider if you can just call into a lower level language / where you draw the line))

[haughty mountain]

I wouldn't say that's idiomatic at all, you can write fast simple code, and if you really need it you can get your hands dirty

But getting your hands dirty should be the exception, not the rule

[opal oriole]

Yea the simple solution can be orders of magnitude faster depending on language. But when it comes to something like C++ vs Rust, that does not really happen like the way it does for C vs Ruby. So it's more about the details at that point.

They are too close.

[haughty mountain]

That's kind of my point

They are both good performance languages when writing simple idiomatic code

[opal oriole]

Oh, ok, because that was what the quote said already, was not sure. I thought they were doing the standard "idiomatic" code tests.

Anyhow, for C/C++/Rust and pretty much any compiled non-GC language that has pointers / references and is not doing really crazy stuff it will be pretty much the same except for the difference of years of compiler optimizations, although those kind of optimizations that compilers are good for are more like general project-wide optimization for optimizations that are really tedious for humans to do / not feasible on such a large scale.

[haughty mountain]

Oh, I don't disagree with the thing I quoted in full. I disagree with claims of rust being just faster than C++, and pointed out that the sources originally quoted doesn't even support that

[opal oriole]

(Unless the compilers are bugged, which is unfortunately common)

(I remember seeing a Haskell project that actually runs just fine, but GHC was so buggy that they had to switch)

[haughty mountain]

And yeah, the tests mentioned are actually really bad for comparison. A lot of code on benchmarksgame are very hand optimized and non-idiomatic.

[opal oriole]

(Or GCC defragmenting the hard drive on a simple 30 line program)

[haughty mountain]

compiler bugs are a thing yeah, but they tend to be ironed out pretty quickly

[opal oriole]

(It's a 3 year old bug)

(pain)

[haughty mountain]

I can't speak for ghc :P

[opal oriole]

(MSVC with its decade old bugs (what is Microsoft doing?))

[opal oriole]

Yeah, which is also kind of the point of both languages, they both can be as fast as can be, it's why they are chosen, which makes the whole speed comparison thing hard / very dependent on rules chosen.

[haughty mountain]

If I see rust code that is majority unsafe I think that's kinda bypassing a bunch of the niceness of rust

[opal oriole]

(We can just assume / guess that C++ is faster due to being older, but that is not very convincing to those that need convincing)

[haughty mountain]

similarly for stupidly optimized C++

[opal oriole]

Yea like when C++ compilers use UB to do optimizations that change behavior potentially.

[haughty mountain]

I mean, clang and rust both are on top of llvm, no?

[opal oriole]

(Writing non-UB code in C++ is a nightmare)

(So is it idiomatic if nobody does it? (even though it's considered officially the "correct" thing))

[haughty mountain]

UB code should never be considered officially correct

[opal oriole]

LLVM is a nightmare to use and so even though multiple languages use it their results vary a lot.

(Depends on what you feed to LLVM and which specific version)

[haughty mountain]

what would you rather use? or do you think everything is pain in compiler space?

[opal oriole]

The thing is that UB is often "machine defined" in practice and a lot of code relies on that, even for correctness. If writing non-UB code were way more feasible I could see it.

[opal oriole]

LLVM is kind of a "have to use for now until I can replace it with my own back-end". It gets lots of projects up and running.

[haughty mountain]

Making your own backend is a lifetime effort though

[opal oriole]

Actually it's not as bad as it seems. The optimizations can just keep being added over time. But to get to a really usable / fast level is not too hard. And you don't need to support everything right away, even just x86 is fine to start.

[haughty mountain]

and you'll more than likely end up with something that optimizes way worse

[opal oriole]

Odin for example or Zig, use LLVM but have their own backends too. You can select which.

LLVM causes them too many pains for maintenance so they want to phase it out eventually.

[haughty mountain]

llvm has the nice idea of having multiple frontends and 1 common representation for the compiler, which solves a ton of platform issues

[opal oriole]

Yeah, it's unfortunate that the code for LLVM is a huge overly complex template mess in C++.

[haughty mountain]

you don't need to write code gen for N target platforms

[opal oriole]

And they constantly break API with versions.

Lack of documentation, etc.

It's not developer friendly.

Ideally there is a project like it, but not as much a mess and with documentation. Nobody should have to write the Nth backend.

[haughty mountain]

I suspect it's less of a mess than gcc

[opal oriole]

Oh yeah, GCC wew.

It has the Stallman complexity touch.

(see emacs)

(generally a bad state of affairs for compilers (also why they are so slow), but that leaves opportunity for improvement and I suspect it will involve either Rust, Odin, D, or Zig)

[opal oriole]

(decades of hindsight can be applied (hopefully they do))

[north swift]

Does anyone have any good resources for learning data structures and algorithms?

[opal oriole]

See the pins.

[north swift]

ah I forgot to look, thank you

[dark aurora]

Hello, can anyone help me with this task
So we have the josephus problem (https://en.wikipedia.org/wiki/Josephus_problem) but a variation of it, i need to find the list of executed individuals. Now I have seen the solution I just don't understand it
reapeat x*a+b while n>0
n is the number of alive people in each round (so for eight it would be :8, 4, 2, 1)
x is the iterator, a is equal to the round to the power of two (so, 2, 4, 8, 16...) and b is equal to b+a (from last round) if n is odd and b-a if n is even
we use a and b to compensate for the space we have to skip
Now I understand a, but I don't understand why is " b is equal to b+a(from last round) if n is odd and b-a if n is even"

[tight patio]

Create a new algorithm to make the calculation of Fibonacci numbers more efficient. Include calculation counter variable in your implementation

how do i do this

[agile sundial]

well, what's your current algorithm?

[tight patio]

i was able to do it

i use a list

to keep track of the two numbers

it was recursive before

[tight patio]

Prove Prim’s Algorithm using the Loop Invariant technique.
whats the simplest way to explain this

something like this but for prim

[brave rain]

I'm trying to make a python script that runs daily automatically (basically a schedule run) but I'm not sure whats the best way to set up a schedule
for the time being I'm planning to just run an infinite loop checking if its a new day (maybe using time) but I'm quite concerned about it crashing in the future so just wondering if there are proper method out there.

[chilly burrow]

what is your operating system ?

[brave rain]

windows 10/11

kinda heard about task scheduling tho

[chilly burrow]

yes use that

[brave rain]

I see

will take a closer look thx

[haughty mountain]

what property does prim maintain between iterations?

[ionic locust]

try out celery

[fiery cosmos]

hi all, quick and straightforward question:
in CLRS they commonly write in their pseudocode something like: for j=p to r-1: do something
of course, in python one cannot declare a variable in a loop header. so when implementing this, can one simply move that statement to a line above it, eg j = p and then have something like: j = p for j to r-1 ...

or would that change the performance of the function / algorithm?

does it depend on the program/algo in usage or is it a generalized safe conversion to make when implementing pseudocode to python

[opal oriole]

range(p, r)

[fiery cosmos]

so just choose some arbitrary new variable, like for x in range (p,r)?

also see my question regarding if this is a safe conversion to make generally or if it depends on the given situation

[opal oriole]

j = p
for j in r-1
``` Is not valid Python.

for j in range(p, r): is valid Python.

Whatever pseudo-code is given you need to convert to Python and it's up to you to know if your Python mimics the pseudo-code or not. There is no "safe" conversion if you don't know how Python works or what the pseudo-code's intent is. No simple rules (that cover all cases) can be given as the pseudo-code is not well defined and there would be too many rules.

Stick to "for variable in something" (tuple, list, set, dict, range, etc) and if you can't make that fit, then go with "while condition".

The "variable" part may sometimes be multiple parts / variables separated by commas depending on what comes after the "in".

[fiery cosmos]

ok. maybe it'd be more helpful if next time i provide a specific example and can thus learn from that

[fiery cosmos]

help

[lean junco]

Anyone familiar with few-shot/one shot algo used in Cryo EM? I want to study a github algorithm but having hard time understanding.

[dire bluff]

Hi Guys, I have little problem with understanding DSA sometimes. Would you like to suggest a good YouTube channel that teach DSA with C++ so I can practice and learn it both way at the same time to improve my coding skill. Thanks.

[tacit nova]

anyone want to do mock interview leetcode ?

[vocal goblet]

@tacit nova count me in, assuming it is about solving a set of leetcode problems.

[fiery cosmos]

hi all,
trying to understand the for loop at line 2 and what is meant by the C[A[j]] statements in line 5

oh it seems as if the for loop in line 2 is simply setting all the values in the new array C to zero?

[haughty mountain]

yeah

[haughty mountain]

same as it would in python C[A[j]] is the element in C at index A[j]

you would write that increment more nicely as C[A[j]] += 1 in python

[fiery cosmos]

right right. and i think line 10 could be replaced with for i in range (a.length),1,-1))

still not getting the "the element in C at index A[j]" thing

[haughty mountain]

A[j] is some integer

you can index array C with it

for a in A:
  C[a] += 1
```if that helps

[fiery cosmos]

ok let me write an example to be sure i understand:

A = [0, 1, 2]
C = [4, 5, 6]
j = 2
then 
C[A[j]] = 6
```?

[haughty mountain]

you don't want strings

[fiery cosmos]

similarly C[A[j]] = 4 when j=0?

oh thats just improper syntax, nvm that

im just thinking about what it means

[haughty mountain]

C[A[2]] = C[2] = 6 yes

do note that python uses 0 indexing like here, the book does 1 indexing

[fiery cosmos]

correct

[haughty mountain]

yes

[fiery cosmos]

what about what i said here: #algos-and-data-structs message
.. is that correct?

[haughty mountain]

kinda, for 0 indexing it's range(len(A)-1, -1, -1) which is painful to write

nicer: reversed(range(len(A)))

[fiery cosmos]

ok ty

the 1 in range is implied?

[haughty mountain]

0

but yes

[fiery cosmos]

ok

hmm counting sort is giving me trouble. the other algos have been pretty straightforward

[haughty mountain]

lines 1-6 should be straightforward

[fiery cosmos]

i was gonna skip but i need to understand it to understand radixsort

[haughty mountain]

I wouldn't write a counting sort for integers like they do it here though on 7-12

[fiery cosmos]

did i tell you one of the problems in the course im auditing is implementing a DTM.. woof

[haughty mountain]

do you understand what lines 1-6 does?

[fiery cosmos]

lms

[haughty mountain]

like, the idea of counting sort is very simple, e.g.

[3, 1, 4, 1]

I have 0 zeroes, 2 ones, 0 twos, 1 three and 1 four, so

[1, 1, 3, 4]

[fiery cosmos]

ahh i think i see it. they are just binning the number of elements of value x, and saying essentially "i have x index i's"

[haughty mountain]

they are counting the number of occurences, yes

[fiery cosmos]

at least, i can read it that way when analyzing their figure

[haughty mountain]

C[2] is how many 2s there are

(C for count)

[fiery cosmos]

2 0's, 0 1's, 2 2's, 3 3's, 0 4's, 1 5

[haughty mountain]

lines 7 onwards does some extra complications so they in the end can copy elements from A to the output

for integers this is pretty overkill

[fiery cosmos]

the output in this case is array B

they use 3 arrays, A B and C

C is the temporary working array

[haughty mountain]

an array of counts, yes

[fiery cosmos]

ok i see it now

i also recently learned some graph theory and the graph coloring problem and that is super interesting

the number of different problems you can solve with that as a model

[haughty mountain]

if you don't care about copying from A you could write line 7 onward as just

res = []
for i, c in enumerate(C):
  for _ in range(c):
    res.append(i)
```or even
```py
res = []
for i, c in enumerate(C):
  res += [i]*c

what they to is to compute where each group of integers start by doing a cumulative sum

[fiery cosmos]

omg why are they using 0 indexing for array C and 1 indexing for array A!

😱

[haughty mountain]

e.g.

[3, 2, 1, 2]
C = [0, 1, 2, 1]
cumulative sum of C  to get
[1, 1, 2, 4, 5]

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

the start of every group (except the last element which is the index just outside the array)

that info can then be used to copy elements over from A

[fiery cosmos]

which lines do the computation you mention

[haughty mountain]

but it's kinda awkward

line 7-9 is the cumulative sum, though I see now they do a slightly different cumulative sum

they don't make it one larger

so ignore the first number in my 5 element array

actually, them not using zero indexing is pretty awkward here

[fiery cosmos]

right bc in the figure i posted they use 0 indexing for 1 array and not the other (where they use 1 indexing)

[haughty mountain]

they compute cumulative sum [0, 1, 3, 4] in my case, which makes a lot of sense if you zero index

[haughty mountain]

that part doesn't matter that much

it's just that cumulative counts translate to 0 indexing

wait...

oh, they think of it as the ends of each group

not the start

so it makes sense with 1 indexing

so...this

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

index 1 is the last 1

index 3 is the last 2

index 4 is the last 3

then they go backwards through A and copy values over into the groups, starting from the end of each group

[fiery cosmos]

i'm trying to trace lines 10-12 given the figure and i can't see how it works from the end

a.length = 8

A[8] = 3

C[3] = 7

B[7] = A[8] = 3 i see it

man is that involved jeez

so thats line 11

lms if i can do 12

[haughty mountain]

the copying process goes backwards in A and backwards in each group of digits

[3, 2, 1, 2] [-, -, -, -]
[3, 2, 1, -] [-, -, 2, -]
[3, 2, -, -] [1, -, 2, -]
[3, -, -, -] [1, 2, 2, -]
[-, -, -, -] [1, 2, 2, 3]
```like this, if this makes sense

[fiery cosmos]

no i don't see how line 12 runs

🤔

line 10 starts with j = 8

so line 11 makes sense

but 12??

[haughty mountain]

C kinda marks the end of the groups

[-, -, -, -]
 ^     ^  ^
 1s   2s  3s

it picks the last element of A, which is a 2 in my example, and puts it at the 2s marker

(that's line 11)

[-, -, 2, -]
 ^     ^  ^
 1s   2s  3s

it then moves the marker back 1

(that's line 12)

[fiery cosmos]

ok, how does 0 get placed in output array B in figure (d)

[haughty mountain]

[-, -, 2, -]
 ^  ^     ^
 1s 2s    3s

[fiery cosmos]

its no longer enumerating instances of a given value its now placing them into output array B in sorted order

[haughty mountain]

in their example a 0s marker would be at index 2

insert a zero there

move marker back one step

so that it now points at index 1

(where the other zero will later go)

[fiery cosmos]

like according to C in (c)?

oh no

thats a 4 at index 2

[haughty mountain]

the C you have in figure (b) onward

[fiery cosmos]

you're talking about fig B

wow this is complex

who came up w this

[haughty mountain]

this is all so that you can copy elements over

if you just deal with integers this is overkill

as I mentioned earlier

[fiery cosmos]

how do you mean

[haughty mountain]

a 2 is as good as any other 2, right? the process here makes sure it's the same 2 that gets moved over

it makes sense if what you deal with is actually objects that has some integer value attached

in that case you really want to copy/move objects over

[fiery cosmos]

yeah this is one thing i've been wondering about, like in all these algos we learn they essentially all just sort integers, but like in real world applications you'd be sorting records of some sort or metadata or customer logins or whatever so how does the implementation change

also when would you actually need to sort giant datasets of just integers

if it's just looking up a customer record (by number) it shouldn't matter if its sorted? or it does to be able to find it?

[haughty mountain]

for counting sort and radix sort and similar you need to be able to translate your object into some integer for sorting

for an integer it's just itself

for a Person class it might have some property like age you want to sort by

it's the latter case where you have to be careful and copy stuff over like in the code here

because people with the same age isn't just interchangable, they have other stuff attached

integers on the other hand are interchangable, this 2 is as good as the other 2

but this code handles the more general case where stuff isn't just interchangable

as for comparison based sorting, there it doesn't really matter if you work with integers or not, you just need to be able to check if one element is less than another, so those generalize easily

[fiery cosmos]

so but things must be sorted in order to find a search value in an array, otherwise no search algo can function efficiently*, because its searching for an integer indexed record (or integer record) given an integer input

and if the data isn't sorted, it'll take worst case runtime, having to check each element in the array with the search term

which would happen every time that the search term isn't actually in the dataset

is that right? so in essence there is a lot of time spent sorting so that searches can be efficient

i'm answering the sort of basic theory question like "why do we care about sorting so much"

[haughty mountain]

in part because searching yes

sort once search a bunch

there are also applications where doing things in sorted order is important

because doing things in that orders can give some guarantees

e.g. minimum spanning tree algorithms like Kruskal's algorithm

[fiery cosmos]

i understand that heaps can be used to create priority queues

[haughty mountain]

yeah, yet another case where sorted order is important

[cerulean river]

Anyone here use AlgoExpert or Leetcode? If so if say the name of teh question talks about a data structure like BST I haven't looked at in a while, would it be "cheating" to review it prior to solving the problem? Or is the question looks like it needs an algorithm I forgot about so I review prior to tackling the problem? Just want to mitigate time wasters.

[undone stream]

Hello, can anyone here help me with LaPlace method for calculating the determinant of a matrix?

[stable pecan]

i can help

[undone stream]

when you get a matrix which order is 5 or more, it gets a huge ramification of cofactors and stuff, right?

[stable pecan]

yes, expansion is pretty large, but you can use a recursive function

[undone stream]

because you will eliminate the line and column from each number of the chosen line/column and a matrix of order 1 number smaller would remain for calculating cofactors

[undone stream]

yeah, but I don't know how to do that

[stable pecan]

i would start with a minor function that gives you the matrix with row i, column j removed

[undone stream]

I have already functions for matrix of orders 3 and 4

the problem is in order 5+

[stable pecan]

can you generalize it for any matrix?

[cerulean river]

Solving reversing a String using recursion where is my code going wrong:

class Solution:
    def recursive_swap(string, left, right):
        if right < left:
            return string
        
        string[left], string[right] = string[right], string[left]
        self.recursive_swap(string, left + 1, right - 1)
        
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        left = 0
        right = len(s) -1
        recursive_swap(s, left, right)
        

[undone stream]

matrix have to be square and numbers integers

[stable pecan]

yes, but can your minor function take any size matrix

[undone stream]

don't know if I got your question. One function is for matrix of size 3x3 and the other for 4x4

[stable pecan]

yes, i'm saying make a function for any size matrix

[undone stream]

that's what I have to do now and don't know how

[stable pecan]

you can't even do a function that creates a minor from a given i, j ?

[undone stream]

I've thought about making a variable number of for loops

[stable pecan]

you only need two loops

[undone stream]

sorry, what do you mean by "minor"?

[undone stream]

really?

[stable pecan]

https://www.cuemath.com/algebra/minor-of-matrix/

the minor (i, j) of a matrix, is the matrix with the ith row and jth column removed

once you have a function that creates a minor, you can start to piece together a determinant function

[undone stream]

oh, sorry, I was referring to it as "cofactor", I didn't know it was called minor

[undone stream]

makes sense

[stable pecan]

it's not a cofactor --- cofactor is +/- the determinant of a minor

but we need the minor first

[undone stream]

I mixed things

so a function that creates minors, right?

[stable pecan]

that's right

i can provide a template if you want to fill it in

[undone stream]

if it's easy for you, I'd like to see

[stable pecan]

def minor(matrix, i, j):
    return [
        [_ for _, _ in enumerate(_) if _ != j] 
        for _, _ in enumerate(_) if _ != i
    ]

we just need to fill in the blanks here

this assumes you've seen list comprehensions and enumerate, if not i can rewrite this as a normal loop

[undone stream]

and change j and i for sliced lists, right?

[stable pecan]

no, i and j are just integers

[undone stream]

I see it

so it's going to return a minor for each element

[stable pecan]

yep

[undone stream]

but we are going to use only the ones from the chosen line/column, right?

[stable pecan]

yep

but we don't worry about that yet, we just make a general minor function that works for everything

[undone stream]

ok

[stable pecan]

once you've written this function, you can create a sort-of one-line function for cofactor and determinant

the cofactor and determinant functions will refer to each other, but are basically just the math definitions put into python

[undone stream]

then we would be breaking the problem into smaller things, that's nice

because I haven't defined functions for determinant, cofactors and minors

I'm just kinda confused on filling the blanks in minor function

[stable pecan]

ok, we first want to loop over the rows of the matrix -- this is the outer-loop, i'll fill this one in:

def minor(matrix, i, j):
    return [
        [_ for _, _ in enumerate(_) if _ != j] 
        for n, row in enumerate(matrix) if _ != i
    ]

so we want to include every row except the ith row --- do you see how to fill in the conditional at the bottom?

[undone stream]

yeah

the one above was difficult to get

the blank before for

what goes there?

[stable pecan]

that's gonna be for each entry in the row -- the inner loop is over items in the row

[undone stream]

hmm

ok

[stable pecan]

you can test your function in the interpreter and make sure it works:

In [2]: my_matrix = [
   ...:     [1, 2, 3],
   ...:     [4, 5, 6],
   ...:     [7, 8, 9],
   ...: ]

In [3]: minor(my_matrix, 0, 0)
Out[3]: [[5, 6], [8, 9]]

In [4]: minor(my_matrix, 0, 1)
Out[4]: [[4, 6], [7, 9]]

[undone stream]

so it's returning each line of the minor

the way I was doing was an entire list with the elements

like: M = [1, 2, 3, 4, 5, 6, 7, 8, 9] for a 3x3 matrix

[stable pecan]

i see, i'm using a list of lists

[undone stream]

ok

is there any advantage in that or both ways are good?

[stable pecan]

!e also makes indexing the matrix more convenient:

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

print(my_matrix[0][0], my_matrix[1][1])

[halcyon plank]

@stable pecan :white_check_mark: Your eval job has completed with return code 0.

1 5

[undone stream]

I see

makes sense

def fourth_order(lst):

    if len(lst) == 16:
        n_order_matrix = list(lst)

        #cofactors
        results = dict()

        for i, ele in enumerate(n_order_matrix[:4]):

            del (n_order_matrix[i::4])
            a_set = set(n_order_matrix)
            n_order_matrix = list(lst)

            del (n_order_matrix[:4])
            b_set = set(n_order_matrix)
            n_order_matrix = list(lst)

            results[ele] = -1 ** (i + 2) * third_order(list(a_set.intersection(b_set)))

        #determinant
        determinant = 0
        for key, value in results.items():
            determinant += key * value

        return determinant

    else:
        raise ValueError

now I see how easier it would be if I had done your way

[stable pecan]

you often don't want to modify arguments you pass into functions, better to create new lists

[undone stream]

I thought I had copied lst that way

[stable pecan]

but if you break everything down into minors, cofactors, and finally determinants, you'll have about as much code as you wrote above, but it will handle arbitrary sized matrices

oh, you did, i didn't see

[undone stream]

that's right

do you think I can keep these two functions (3x3 and 4x4) I've already written for making the process a bit faster when the passed matrix is already 3x3 or 4x4?

[stable pecan]

you could keep them, but the more general function will probably be just as fast if not faster

[undone stream]

yeah, probably

well, thanks for your time, you have helped me a lot 🤝

[stable pecan]

np

[rough lynx]

What is considered the standard way to overload functions in Python? I know it used to not be a thing but is doable now

I'm seeing all sorts of different implementations, such as:

1. the naïve method of doing if type(x) == str or the like for each argument
2. Using the functools.singledispatch module and registering alternative versions of a given function based on argument type (but this is limited to single argument functions)
3. using metaclass=OverloadMeta in your class declaration, but this only applies to classes AFAIK
4. Using 3rd party packages like overload to handle this for you

But I'm not sure if there's a proper standard library way of doing this

[haughty mountain]

I would go for "don't do it" but that's just me

overload sets that do significantly different stuff per type seems like a bad idea

[dark aurora]

Does anyone know a python solution for this task https://cses.fi/problemset/task/2163 ? If so can they explain it to me?

[dusk anchor]

Im new to data structs. In a hash table how can I avoid collisions

[agile sundial]

you can't

there are mitigation strategies, though, like chaining or open addressing

[dusk anchor]

So thereis not a way, only ways to make it less likely to happen

Thx, ill do some research and learn bout them

[agile sundial]

they're already highly unlikely with a proper hash algorithm. chaining and open addressing are for when collisions do happen

[dusk anchor]

Yeah. I imagine a way would be to create a list for each index and store collided pairs in this list

[agile sundial]

yep, that is indeed a way. it's called "chaining"

[dusk anchor]

Alright. Thank you

[rough lynx]

I was more so thinking that it would reduce the number of if type(arg) is X calls within a function, and it would let you annotate argument types for each of the different overloaded function definitions

[shut breach]

why not just write different function if you're doing different things with it?

also this isn't an algorithms question, but feel free to ask about it in #python-discussion or open a help channel in #❓｜how-to-get-help

[fiery cosmos]

hi all. the photo shows the runtime of bucketsort. the theta(n) term is given but the runtime of the bucketsort lines of the program, which contains an insertionsort algo within it, given by the next term. it is a summation because they are indicating the enumeration of the number of calls the algorithm must make to insertion sort, which runs in O of quadratic time (n^2). just making sure i'm reading and understanding this correctly.

[fiery cosmos]

Is there an itertoolsy way to turn some iterable (A, B, C, ...) into (A, A, A, B, B, B, C, C, C, ...), i.e. each element is repeated over k times (k = 3 in example)

cc @median dawn

[runic tinsel]

(x for x in i for _ in range(k))

there's no itertoolsy way

!e

from itertools import *
i= [1,2,3]
print(*chain.from_iterable(zip(*[i]*3)))
print(*(x for x in i for _ in range(3)))```

[halcyon plank]

@runic tinsel :white_check_mark: Your eval job has completed with return code 0.

001 | 1 1 1 2 2 2 3 3 3
002 | 1 1 1 2 2 2 3 3 3

[fiery cosmos]

double for comprehension strikes again

[stable pecan]

there's itertools.repeat

[slender sandal]

You could do

sum(map(lambda x: tuple(itertools.repeat(x, 3)), range(10)), start=())

or something

[slender sandal]

bRuh

[stable pecan]

just (repeat(i, n) for i in my_iterable)

[slender sandal]

But that's a generator expression

[stable pecan]

chain from it

[slender sandal]

My solution is totally functional

What do you mean chain from it

[stable pecan]

chain.from_iterable(repeat(i, n) for i in my_iterable)

[slender sandal]

Yeah I like that

Still has a generator expression though

[stable pecan]

yes

[haughty mountain]

the bucketsort they have is to put ranges in different buckets and then sorting each bucket with insert sort, so you get many smaller quadratic costs, note that it's not O(n²) but O(n_i²), so the size of the ith bucket squared

[slender sandal]

This is cool though

tuple(itertools.chain.from_iterable(map(lambda x: itertools.repeat(x, 3), range(10))))

itertools.chain.from_iterable is like using sum except it's less hacky and better in every other way

[haughty mountain]

at what point do you just give up write the neat readable generator expression?

[slender sandal]

Idk I was just trying to find a solution

[stable pecan]

In [1]: from itertools import chain, repeat

In [2]: my_list = [1, 2, 3, 4, 5]

In [3]: def repeater(iterable, n):
   ...:     return chain.from_iterable(repeat(i, n) for i in iterable)

In [4]: list(repeater(my_list, 3))
Out[4]: [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5]

[slender sandal]

!d itertools.starmap is a cool idea

[halcyon plank]

itertools.starmap

itertools.starmap(function, iterable)```
Make an iterator that computes the function using arguments obtained from the iterable. Used instead of [`map()`](https://docs.python.org/3/library/functions.html#map "map") when argument parameters are already grouped in tuples from a single iterable (the data has been “pre-zipped”). The difference between [`map()`](https://docs.python.org/3/library/functions.html#map "map") and [`starmap()`](https://docs.python.org/3/library/itertools.html#itertools.starmap "itertools.starmap") parallels the distinction between `function(a,b)` and `function(*c)`. Roughly equivalent to:

```py
def starmap(function, iterable):
    # starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000
    for args in iterable:
        yield function(*args)

[haughty mountain]

other fun options

def my_repeat(it, k):
  for x in it:
    yield from [x]*k

[stable pecan]

i wouldn't create intermediate lists

but you can just add another loop

[haughty mountain]

but that's less fun :(

(lst[i//k] for i in range(k*len(lst)))

so many silly ways

[slender sandal]

(x for x in iterable for _ in range(k))

[haughty mountain]

yeah, that's the sensible way that was mentioned a while back

[slender sandal]

Ye

[haughty mountain]

I just remembered Kronecker nonsense exists

In [1]: import numpy as np

In [2]: np.kron([3, 1, 4, 2], [1] * 3)
Out[2]: array([3, 3, 3, 1, 1, 1, 4, 4, 4, 2, 2, 2])

reminds me of my matlab days

apparently numpy has this function anyway

In [12]: np.repeat([3, 1, 4, 2], 3)
Out[12]: array([3, 3, 3, 1, 1, 1, 4, 4, 4, 2, 2, 2])

[undone stream]

Is salt-die online? don't want to ping him but I need his help

[stable pecan]

i'll ask

[undone stream]

!e ```py
def minor(lst, i, j):
return [
[num for pos, num in enumerate(row) if pos != i] for n, row in enumerate(lst) if n != j
]

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

print(minor(my_matrix, 0, 0))

[halcyon plank]

@undone stream :white_check_mark: Your eval job has completed with return code 0.

[[5, 6], [8, 9]]

[stable pecan]

looks right

[undone stream]

I don't know if it's working correctly, since I had trouble completing that

actually, I don't know if the names for the variables are correct. If not, it may confuse me in the future

because I changed a bit that template you did for me yesterday

[stable pecan]

def minor(matrix, i, j):
    return [
        [e for m, e in enumerate(row) if m != j] 
        for n, row in enumerate(matrix) if n != i
    ]

i use this as my variable names, the names in the inner loop are mostly arbitrary --- i used e for entry

[undone stream]

I inverted j and i

maybe it worked coincidentlly

[stable pecan]

!e you can test it real quick:

def minor(matrix, i, j):
    return [
        [e for m, e in enumerate(row) if m != j] 
        for n, row in enumerate(matrix) if n != i
    ]

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

for i in range(3):
  for j in range(3):
      print(minor(my_matrix, i, j))

[halcyon plank]

@stable pecan :white_check_mark: Your eval job has completed with return code 0.

001 | [[5, 6], [8, 9]]
002 | [[4, 6], [7, 9]]
003 | [[4, 5], [7, 8]]
004 | [[2, 3], [8, 9]]
005 | [[1, 3], [7, 9]]
006 | [[1, 2], [7, 8]]
007 | [[2, 3], [5, 6]]
008 | [[1, 3], [4, 6]]
009 | [[1, 2], [4, 5]]

[undone stream]

I'd better invert that again I suppose

since it works correctly only when j and i are equal

[stable pecan]

did you write a cofactor function?

[undone stream]

not yet

after our talk yesterday I came back to this project now

I'll start it now

[halcyon plank]

@undone stream :white_check_mark: Your eval job has completed with return code 0.

[[], [], []]

[undone stream]

for a cofactor function I'll need a determinant one first, right?

def cofactors(lst):
    return [
        -1 ** (2 + pos) * minor(lst, 0, pos)
        for pos, n in enumerate(lst[0])
    ]

I did this using minor instead of determinant 😐

will I need a closure with determinant and cofactors functions?

[stable pecan]

the cofactor and the determinant will both refer to each other, so they'll be mutually recursive, but this isn't exactly right

try something like this:

def cofactor(matrix, i, j):
    return <sign of cofactor> * <determinant of some minor>

the determinant function doesn't have to be defined, we'll define it next -- but you can use it as if it was already defined

[undone stream]

I used -1 ** (2 + pos) for defining the sign of cofactor. Shouldn't I change only the minor(lst, 0, pos) for the determinant?

[undone stream]

like this? ```py
def determinant(mino):
pass

def cofactors(lst):
return [
-1 ** (2 + pos) * determinant(minor(lst))
for pos, n in enumerate(lst[0])
]```

[stable pecan]

kind of, but try to keep the same function signature -- you shouldn't need a comprehension for this function

[undone stream]

ok

def determinant(mino):
    pass


def cofactors(lst):
    for pos, n in enumerate(lst[0]):
        return -1 ** (2 + pos) * determinant(minor(lst))

I didn't get the signature thing

[stable pecan]

this is closer, but you don't need a loop --- signature means the functions arguments:
note that minor 's arguments are matrix, i, j but you're only passing one argument -- similarly my example cofactor function also has 3 arguments matrix, i, j

you just need to implement this definition

[undone stream]

hmm now I see

[stable pecan]

you're very close though

[undone stream]

but that worked as well, doesn't it?

[stable pecan]

the loop will be in the determinant function

when we get there

cofactor has a simpler definition

[undone stream]

right

I got to go now. I'll come back tomorrow and probably will ask for your help again 😅

[stable pecan]

you can ping me in here if you want

[undone stream]

ok

thanks again by now

[stable pecan]

np

[dark aurora]

Can someone explain to me this solution for this task (here https://cses.fi/problemset/task/2163)

Solution

from collections import deque
from itertools import cycle
 
SPLIT_SIZE = 1000
 
n, k = map(int, input().split())
 
numbers = range(1, n + 1)
splits = cycle(list(numbers[i:i+SPLIT_SIZE]) for i in range(0, n, SPLIT_SIZE))
 
i = 0
split = next(splits)
res = []
while n:
    i = (i + k) % n
    while i >= len(split):
        i -= len(split)
        split = next(splits)
    res.append(split.pop(i))
    n -= 1
print(' '.join(map(str, res)))```

[runic tinsel]

it makes a sort of circular list, but each node has many people in an array

so large steps are cheap

i don't know if this is better than just using deque as is

it seems that it's worse

from collections import deque

n, k = map(int, input().split())
 
numbers = deque(range(1, n + 1))
res = []
while n:
    numbers.rotate(-k-1)
    res.append(numbers.pop())
    n -= 1

``` like this seems to run faster

@dark aurora got it?

it avoids using deque, implements an alternative manually, and gets half the speed

[dark aurora]

so, it makes a circular list and then he can remove any number because it will be the end of a list(?) which makes the pop much faster?

sorry, i have never used deque (so am a bit confused here)

[runic tinsel]

oh, actually not using anything is faster

n = 181923, k = 18900000
"splits" : ~8s
deque: 2.9s
list: 1.6s

that's strange

[runic tinsel]

it will be at the end in the sense that it will be at most 1000 from the end

and if you don't do anything and just pop, that's the fastest way

numbers = list(range(1, n + 1))

 
i = 0

res = []
while n:
    i = (i + k) % n
    res.append(numbers.pop(i))
    n -= 1

like this

i didn't expect deque to make it worse but i also don't know how it really works

[dark aurora]

yeah, I mean the solution should be much faster than just a list

[runic tinsel]

true

🤷‍♂️

[dark aurora]

???

this is the simple solution

I will look into his solution a bit more, and see what I find

[runic tinsel]

so the splits pass?

but list doesn't

that's what you;re saying?

yes, i can see that

if i run in pypy

the splits benefit the most for some reason

so it's like, splits are better, but the overhead is not worth it (for these constraints or always?), but pypy removes it completely

strange but ok

@dark aurora so it's a circular list of small python lists

[dark aurora]

" A lot of it is using copypasta SortedList (list-of-lists decomposed over some loading threshold) to account for the lack of stuff like std::map built-in" this is what i found about the solution though I don't understand it maybe you do

[runic tinsel]

maybe that's referring to another problem from this site

[dark aurora]

no, it is reffering to this specific problem

[runic tinsel]

i mean "SortedList"

i don;t understand it

[dark aurora]

can you explain why he does this

[runic tinsel]

does what

[dark aurora]

Il send it

 while i >= len(split):
        i -= len(split)
        split = next(splits)

[runic tinsel]

this is going through the circular list

he makes k steps

by subtracting length of the sublist, and going to the next sublist

[dark aurora]

why not just if i>=len(split), split = splits[it+i//len(split)] (it = index of curent split)

[runic tinsel]

wait...

yeah im confused

[dark aurora]

same man

[runic tinsel]

no ok, that makes sense, i is like "increment", not "index"

i is how many steps you need to make

your splits get shorter, you can't just do arithmetics to figure out the correct split

like
[1,2,3] [4,5,6] [7,8,9]
[1,2,3] [4,5,6] [7,9]
[1,3] [4,5,6] [7,9]
[1,3] [4,5,6] [9]
[1,3] [4,5] [9]

it's really just popping from a list, except you make each pop cost 1000 at most

and you have to do this loop to navigate

and it's worth it somehow

i'm still confused about this (i+k) % n

[dark aurora]

I don't quite understand that, can you elaborate

[runic tinsel]

it should give you index, not increment 🤔

[dark aurora]

isn't that pretty straigthforward it just gives you the index of the next step

[runic tinsel]

it's neither

[dark aurora]

wait il go eat for a few mins

[runic tinsel]

when you do this, your i is an offset into the current slice

it's always the increment

i get it

hard to visualize

so yeah it's index into how your current list looks like

like this
[1,2,3] [4,5,6] [7,8,9] new i; i = 4 (so number 5)
[4,5,6] [7,8,9][1,2,3]; i = 1
[4,6] [7,8,9][1,2,3] (pop) new i; i = 1
[4] [7,8,9][1,2,3] (pop) new i ; i = 4
[7,8,9][1,2,3][4]; i=3
[1,2,3][4] [7,8,9]; i=0
[2,3][4] [7,8,9] (pop)
...

[dark aurora]

what is an offset?

[dark aurora]

how did you get i=4 on the fourth one?

[dark aurora]

I don't understand this sequence really?

[runic tinsel]

@dark aurorawhen it says new i, it comes from nowhere

it's (i + k) % n, unpredictable

i didn;t have a k in mind

[dark aurora]

aaah I see, i though these sequences were connected

but how does that make the code that much faster?

[runic tinsel]

when it doesn;t say new i, we cycle once and decrease i by the length we just cycled

i don't know why it works, it just looks to me like a middle ground between n one element lists and 1 list length n

whether it's predictably better than both, or it's just somehow optimal on real hardware in pypy, no clue

[dark aurora]

I see what you mean, do you think we could get similiar results with hashmaps?

is it even possible?

[runic tinsel]

don't know sorry

there's a possibility that it's just how you make a deque, beczuse i tried the built in deque version in pypy and it completely freaks out

like there's an insane slowdown

[haughty mountain]

deque in python is basically a linked list, so yeah it will be super slow

I can imagine a solution using something like a segment tree (or fenwick tree) to keep track of "how many elements are to the left of index i. Then you can ignore removing elements from the list and instead do a range update in the tree

The tree can then be searched to find the index with the kth element

You can get that down to O(n log n)

[dark aurora]

will try that out , thanks

[haughty mountain]

it's probably a lot more involved than what's necessary, but in my head it should work

ah, some solutions I see around use trees where you can get order statistics

which is what the thing I described basically is, just hackier

[fringe zodiac]

V * W * 8 + Y - Z
= (((((V * W) * 8) + Y) - Z))
= ((-(+( * (* V W) 8) Y) Z))
= - + * * V W 8 Y Z

is this the correct way to convert from an infix to prefix?

[shut breach]

depends on the precedence of the infixes

[fiery cosmos]

hi all i'm reading about 'dynamic sets' in CLRS, how would a dynamic set be implemented in python, like what DS

oh

"the best way to implement a dynamic set depends upon the operations that must be supported."

nvm

[thorn oriole]

how important is to know a binary search tree and what use can I give to it in the day to day?

[vagrant perch]

hey guys pretty new to dsa here: why does this not append to alist

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        empty = []
        def rev():
            empty.append(head.next)
            head = head.next
            rev(head)
        return empty[0]```

[thorn oriole]

.append(name_of_list)

[vagrant perch]

oh

[thorn oriole]

try that

or maybe head.next is nothing

so it appends nothing

try printing head next

[vagrant perch]

it is something surelyt

they given me head

1 is head

i was under the impression i could .append nodes to a list and use that as the answer but it turns out you cant

I thought head.next gives you 1

[vagrant perch]

this not how append works

class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
empty = []
def rev(head):
empty = empty.append(head.next)
head = head.next
rev(head)
return empty

why does this return an empty list?

iunstead ofa list of nodes

[shut breach]

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        empty = []
        def rev(head):
            empty = empty.append(head.next)
            head = head.next
            rev(head)
        return empty

the inner function you defined is never called

so you're defining an empty list, defining a function, and then returning the empty list

[vagrant perch]

ahhhh ok

thanks alot

but by inner do u mean first one?

u cant call rev inside itself right

I think it expects me to return as a liunked list not as a list of nodes

[agile sundial]

it's pretty rare to use a bst, but you don't want to not know about it when you need to

[opal oriole]

Variants of the idea are often used. But it depends on what your "day to day" is. For some they can't go a day without running into some kind of tree.

If you are a systems programmer you have probably needed one or more of them at some point: https://en.wikipedia.org/wiki/Completely_Fair_Scheduler

It also shows up as part of other data structures.

[haughty mountain]

gemeric bst is rare, bbst is actually useful

[blazing hound]

This is a sliding window problem, Best Time to Buy and Sell Stock
https://leetcode.com/problems/best-time-to-buy-and-sell-stock
The brute force solution is

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0
        for i in range(len(prices) - 1):
            for j in range(i + 1, len(prices)):
                profit = prices[j] - prices[i]
                if profit > max_profit:
                    max_profit = profit
                    
        return max_profit

The loop runs n(n - 1) / 2 times.
How do we get that?

[fiery cosmos]

there are 2 loops there

[blazing hound]

Yep. I know it generalizes to O(N^2). But how do we get the exact total sum?

[fiery cosmos]

you said "the loop," runs in.. which loop in the above are you referring to

[blazing hound]

I believe it means the number of operations
Like if we had 7 elements in the array, we would run operations (7 * 6)/2 times

[tacit nova]

it can also be solved with Dynamic Programming (State Machine pattern)

i do too much leetcode now i feel 🤢

[fiery cosmos]

how did y'all learn hash tables / functions

what is leetcode

[agile sundial]

look at the loops. there's no early exit, so we just need to care about the start and ends of each loop. the outer loop runs len(prices) - 1 times. the inner loop runs len(prices) - i + 1) times, where i is 0, 1, 2, 3, ... len(prices - 1). then just multiply the two

[agile sundial]

yeah, they're definitely useful, but i think they're still pretty rare to actually need

[undone stream]

hello @stable pecan

This is how I left yesterday```py
def determinant(mino):
pass

def cofactors(lst, i, j):
return -1 ** (i + j) * determinant(minor(lst, i, j))

I think cofactor function is all right, now I need to develop determinant() for looping over the matrix, right?

[stable pecan]

yep, looks correct

[blazing hound]

Thanks, but I don't think that answers my question on how the number of operations simplifies to n(n - 1) / 2
The outer loop runs n times and the inner loop runs (n - 1) + (n - 2) + (n - 3) ... 1 times. So it should be n(n - 1) + n(n - 2) + n(n - 3) + ... 1
I'm guessing there's a series summation thing that says that simplifies to n(n- 1) / 2

[agile sundial]

yeah

oh wait, i'm wrong

[agile sundial]

you don't multiply, you just have the inner loop running 0 + 1 + 2 + 3 + ... len(prices - 1) times

[stable pecan]

for the determinant, there's a base case i'll give you --- without the base case function will error when it tries to take cofactors of a 1x1 matrix:

def determinant(matrix):
    if len(matrix) == 1:
        return matrix[0][0]
    
    return <laplace expansion>

[undone stream]

so that's just an error handling?

[stable pecan]

for recursive functions, you usually need a way to stop the recursion at some point --- usually with a base case

[undone stream]

oh, I see

[stable pecan]

for 1x1 matrixes we know the determinant is just the element in the matrix, so that can be our base case

[undone stream]

we need another condition for 2x2 matrixes I think

since it doesn't have minors

[stable pecan]

no, for 2x2 matrices it will be split into smaller cases!

[undone stream]

ooh, makes sense

wow

[stable pecan]

the minors will be 1x1

[undone stream]

yeah

[undone stream]

I think I got into the same problem as in the old way I was trying to do before your help: I think I need a variable number of nested loops according to matrix's length, but if it's correct, I don't know exactly how to do it

someone recommended me using itertools lib for that

[stable pecan]

you only need a single loop, do you have the definition of laplace expansion on hand?

found this

[undone stream]

it's like e * [e], right? the sum of each element times its cofactor

[stable pecan]

so we have (-1)**(i + j) * M_i,j is our cofactor

so we should have something like:

sum( something * cofactor for loop_variables in what_we_loop_over)

we only have to loop over a single row to get our expansion though

i also just realized there's a typo in the cofactor function

def cofactors(lst, i, j):
    return (-1) ** (i + j) * determinant(minor(lst, i, j))

put parens around this -1 otherwise it will raise 1 to that power and then negate it

[undone stream]

right

[stable pecan]

i've made this mistake lots of times

[undone stream]

sorry, I haven't got how it could work. I think I'm kinda fixed in that lots of loops thought

[undone stream]

and what is B_i,j supposed to be?

[stable pecan]

ok, i'm going to paste the example from wikipedia and we can work it out in python:

so in this case they decided to loop along the first row --- each entry in the first row was multiplied by the cofactor of that entry

in python:

sum(entry * cofactor(entry) for entry in first_row)

so we just have to fix these variables

[undone stream]

like I said here, I think. But those -1 and -2 entries don't make sense. Shouldn't they be positive?

[stable pecan]

B_ij is just the ith, jth entry in B

[stable pecan]

they took the signs from their cofactors

[undone stream]

oh, I see

ok

correct me please: for each entry from the first row, cofactor and determinant functions will refer to each other until it's "not possible"

[stable pecan]

yep

[undone stream]

ooh, that makes a lot of sense now

[stable pecan]

determinant will call cofactor, cofactor will call determinant, but on smaller determinants

[undone stream]

that's incredible

[stable pecan]

until it reaches the base case

[undone stream]

yeah

then I think determinant() is ok now: ```py
def determinant(lst):
if len(lst) == 1:
return lst[0][0]

return sum(entry * cofactor(entry) for entry in lst[0])

not actually

[stable pecan]

ok, now we just need to fix the arguments to cofactor

[undone stream]

we need cofactor arguments

yeah

[stable pecan]

we know the matrix is just lst

cofactor(lst, _, _)

what is i?

[undone stream]

the row

[stable pecan]

right

so cofactor(lst, 0, _)

[undone stream]

right

doesn't j come from enumerate(lst[0])?

[stable pecan]

thats right

[undone stream]

i'll change

return sum(entry * cofactor(entry, 0, pos) for pos, entry in enumerate(lst[0]))

I think this line is conflicting with ```py
if len(lst) == 1:
return lst[0][0]

[stable pecan]

looks like first argument of cofactor is wrong

(entry is actually given by i,j in our function) but we need to pass the matrix

[undone stream]

like this?```py
return sum(entry * cofactor(cofactor(entry, i, j), 0, pos) for pos, entry in enumerate(lst[0]))

[stable pecan]

return sum(entry * cofactor(lst, 0, pos) for pos, entry in enumerate(lst[0]))

[undone stream]

hmm

[stable pecan]

the 0, pos arguments give the entry pos

i just put cofactor(entry) clues above to not give too much away

[undone stream]

I think it's working now

to see if it's correct we can check with a matrix of consecutive numbers, its det will always be 0

[stable pecan]

!e

def determinant(matrix):
    if len(matrix) == 1:
        return matrix[0][0]

    return sum(e * cofactor(matrix, 0, j) for j, e in enumerate(matrix[0]))

def cofactor(matrix, i, j):
    return (-1)**(i + j) * determinant(minor(matrix, i, j))

def minor(matrix, i, j):
    return [[e for m, e in enumerate(row) if m != j] for n, row in enumerate(matrix) if n != i]

matrices = (
    [
        [4, 6],
        [3, 8],
    ],
    [
        [6, 1, 1],
        [4, -2, 5],
        [2, 8, 7],
    ],
)

for matrix in matrices:
    print(determinant(matrix))

[halcyon plank]

@stable pecan :white_check_mark: Your eval job has completed with return code 0.

001 | 14
002 | -306

[stable pecan]

ez pz

[undone stream]

it's so nice

[stable pecan]

this explodes for huge matrices though and will take forever to compute

[undone stream]

even though you did most of the job, the point of this project for me was to learn, and I learned so much with your help. That's what matters

[stable pecan]

but it's still super elegant

[undone stream]

I appreciate your patience. Thanks a lot

[stable pecan]

the super take away is we can almost copy the math definitions verbatim and everything just works!

[undone stream]

yeah

[stable pecan]

the only nuance being the base case

[undone stream]

this was very nice

[harsh bolt]

nah

it was very boring

[ebon heron]

Hey, not sure it this is the best place to ask. I'm following the websockets tutorial bulding a connect 4 game. They have a code snippet to determine if there's a winner on the board, and I'm having very hard time understanding it

@property
def last_player_won(self):
    """
    Whether the last move is winning.

    """
    b = sum(1 << (8 * column + row) for _, column, row in self.moves[::-2])
    return any(b & b >> v & b >> 2 * v & b >> 3 * v for v in [1, 7, 8, 9])

https://websockets.readthedocs.io/en/stable/intro/tutorial1.html#connect4.Connect4.winner

!e

[halcyon plank]

Missing required argument

code

[stable pecan]

this is pretty esoteric, but they're mapping the location of all checkers in the grid to a 54-bit number -- here's the number when every spot in the grid is filled:

In [28]: from itertools import product

In [29]: moves = product(range(7), range(6))

In [30]: bin(sum(1 << (8 * col + row) for col, row in moves))
Out[30]: '0b111111001111110011111100111111001111110011111100111111'

here's how some other combinations of moves fill out the number:

In [31]: moves = [(6, 5), (6, 4), (6, 3), (6, 2)]  # column connect4

In [32]: bin(sum(1 << (8 * col + row) for col, row in moves))
Out[32]: '0b111100000000000000000000000000000000000000000000000000'

In [33]: moves = [(6, 5), (5, 5), (4, 5), (3, 5)]  # row connect4

In [34]: bin(sum(1 << (8 * col + row) for col, row in moves))
Out[34]: '0b100000001000000010000000100000000000000000000000000000'

In [35]: moves = [(6, 5), (5, 4), (4, 3), (3, 2)]  # diagonal connect4

In [36]: bin(sum(1 << (8 * col + row) for col, row in moves))
Out[36]: '0b100000000100000000100000000100000000000000000000000000'

In [37]: moves = [(0, 5), (1, 4), (2, 3), (3, 2)]  # diagonal connect4

In [38]: bin(sum(1 << (8 * col + row) for col, row in moves))
Out[38]: '0b100000010000001000000100000'

so this final line any(b & b >> v & b >> 2 * v & b >> 3 * v for v in [1, 7, 8, 9])
is checking if there's a column connect4 (v = 1), a row connect4 (v = 8), or one of the diagonal connect4's (v = 7 or v = 9)

[stable pecan]

the >> is shifting this (binary) number that many digits to the left and the & is a bitwise-and

[dark aurora]

Can you elaborate

I tried using segment trees and dictionaries but my solution got really complicated so I gave up

[haughty mountain]

To explain the basic idea, imagine you have a second array with 0s and 1s depending on if the number is still there in the original array. I start with all ones, and when I remove an element I just turn that 1 to a 0. You can then count how many ones there are to find the kth unset item

In practice we don't want a 0/1 array because counting ones is slow

That's where something like Fenwick trees or segment trees (range query trees) come in. With such trees you can easily compute sums of subarrays

You could also do something similar with range updates and seeing the value at a single point, which is what I wad thinking earlier. Put updating a single element and querying ranges is probably the more straightforward thing

[dark aurora]

How do I use sums of subarrays to find the kth item

I think i get it, so if we have a num at position n i calculate the range sum from (0, n) which is it's index if we were popping them, because each num not popped has value one

[haughty mountain]

to find the index of the kth item you want the first index i such that the sum up until i is k

naively you could binary search for that i, but that would be O(log(n)²) because each prefix sum costs O(log(n))

you can be a bit more clever and find it by walking down the tree from the root in O(log(n))

but probably correctness is the more important part in the beginning

[dark aurora]

that should still be enough

[dark aurora]

I was able to solve it, thanks so much

[fiery cosmos]

Why are they checking the heap size in lines 3 and 6

[haughty mountain]

to detect if there is no such child

[haughty mountain]

i.e. if the computed index > heap_size then the index is outside the heap

[fiery cosmos]

how would i go about solving c.

i can ask in the math server nvm

[agile sundial]

what's equation 7.5

[ebon heron]

Thank you so much .. I'll spend more time trying to comprehend! This is pretty hard for me 😰

[fiery cosmos]

the one shown right above it in b

[agile sundial]

i c

is that for quicksort?

[fiery cosmos]

sure is. let's table that for now

i'm learning hashing algos 🙂

[agile sundial]

ok, it looks scary but it's actually quite straightforward

[fiery cosmos]

i definitely can read b and understand what its claiming mathematically

i'm reading in CLRS that hashtables where collisions are resolved by chaining with doubly linked lists can be searched successfully for a search term in theta(1+alpha) where alpha is the load factor, that is, the average number of elements in each linked list.

given the assumption of simple uniform hashing. but i don't see how that could be, i think at least half of all the elements in all the linked lists would have to be searched on average..

is there something im misunderstanding

[agile sundial]

if you assume simple uniform hashing, each spot is equally likely, so on average, you would need to search the load factor + 1 items, because each spot has load factor items on average

you're forgetting that you only need to search the items in one index of the table

[fiery cosmos]

because.. given the search term x its location within the table will be computed by the hash function h(x)?

[agile sundial]

yes

[fiery cosmos]

yes that's what i was missing

now if i could just understand it in the following terms:

[agile sundial]

which part are you having trouble with?

[fiery cosmos]

the entire thing but maybe once i look back at lemma 5.1 and learn the linearity of expectation and look at equation A.1 i can put it all together

[agile sundial]

linearity of expectation is very simple, it's basically just: "the expected value of the sum of random variables is equal to the sum of the expected values of the random variables"

basically, you transpose the E and the sum

[fiery cosmos]

i wonder if they have a definition for the expectation in this book anywhere

[agile sundial]

i would assume in chapter 5

[fiery cosmos]

they do but its not well defined in that it isn't clear how its different than the probability

[agile sundial]

ah, nevermind, it's in the appendix, C.20

[fiery cosmos]

they have the def of expected value of an indicator random variable on pages 118-119

[agile sundial]

the expected value is basically the "weighted average" of the values the random variable can have

this is different from probability

[agile sundial]

that's a wide screenshot

[fiery cosmos]

clicking open original and then zooming in helps

[opal oriole]

So the expected value of a six sided die is?

*Fair die.

[fiery cosmos]

1/6

wait

[opal oriole]

Value, not probability.

[fiery cosmos]

3.5

[opal oriole]

Yes. To understand that value, roll a die that always lands on six. What is the expected value. Don't even need math for this one, just the natural answer to that.

*Which value do you expect to show up / what do you predict.

[fiery cosmos]

so i just made a hypothetical example in which value 1 has probability 0.1, val 2 has prob 0.2, val 3 prob 0.5, val 4 prob 0.1, and val 5 has prob 0.1

[agile sundial]

that adds up to more than 1 probability

[opal oriole]

The probabilities of all the possible outcomes need to add up to one, because when you roll the die, it has to be one of the values.

One of the possible outcomes.

[fiery cosmos]

nvm the die example, i'll tweak mine to add to 1

[opal oriole]

*The probability of getting any outcome being 1.

Any at all.

[fiery cosmos]

so the expected value in my example is 2.9

i'll do it again

no i'm getting 2.9

just the v1p1 + v2p2... + v5*p5

[agile sundial]

oops, you're right lol

[opal oriole]

I got 2.9.

[fiery cosmos]

ok great thanks

well that's easy for a random variable. in the book they expand on the concept to indicator random variables, expected value of binomial distribution, and geometric distributions

this is important for me to know

in the future i'll be dreaming up ways of how to normalize the expected value of transcripts of gene A in tissue B during condition C

[agile sundial]

an indicator random variable is just 1 if some event happens, and 0 otherwise

[fiery cosmos]

yeah thats where the book misleads you as they define the expected value of an indicator random variable in a very circular way using the probability of some event

pg 119

[agile sundial]

how is that circular? the expected value of an indicator random variable is very closely tied to the probability of the event happening

[opal oriole]

Create an indicator variable for rolling a six.

[fiery cosmos]

perhaps it isn't what i mean to say is that when learning the expected value, seeing it explained in this manner first doesn't do well to differentiate the concept from probability in the eyes of a beginner (me)

[agile sundial]

i can see where you'd be confused, considering they're numerically equal

[fiery cosmos]

so in the hash table search analysis using doubly linked lists as chains to avoid collision, they let the indicator random variable be the probability that your search term is equal to k_j, what is k_j?

[agile sundial]

they define it in the paragraph, it's a key

[fiery cosmos]

it simply says for keys k_i and k_j

[agile sundial]

yeah, it's a key

it's the key of x_j

[fiery cosmos]

its abundantly clear what k_i is, k_j not so much

[wind nexus]

hello, im brand new to python

well i took a class once 2 years ago

[fiery cosmos]

welcome

[agile sundial]

you need two keys for a hash collision, k_j is the other key

[wind nexus]

is the syllabus still compatible with python now after the updates?

[fiery cosmos]

not sure what you mean

are you in a specific course right now?

[wind nexus]

no, im running a coding and robotics club with my friend for extracurriculars.

he asked me to cofound because i write good emails

also power points

[fiery cosmos]

so.. you want to learn python?

this is the algorithms and data structures specific channel, you may want to learn the basics before trying to implement specific algorithms

[wind nexus]

sorry i didnt sleep well so my english isnt good

[wind nexus]

ah ok

i thought this was like general lol

[fiery cosmos]

https://discord.com/channels/267624335836053506/267624335836053506

general is there and you can get help in the help chans

[stone crystal]

I don't feel like reposting the question so imagine I just posted #help-cake message here

[haughty mountain]

do you actually have issues with that case?

[stone crystal]

yes

I'm working with opencv contours and I have a vertex on the polygon like every pixel pretty much, and I'm running into issues because of that

[haughty mountain]

why would it not hit both segments?

[stone crystal]

wym

like if it hit a vertex like in the image?

[haughty mountain]

the vertex is in both segments

[stone crystal]

yeah

but the issue is that if it hits two like that then it'll always be counted as outside even if it's inside

[haughty mountain]

lin any case, you could rewrite things with dot products if you want to, which might behave better

[stone crystal]

how would that work

[haughty mountain]

compute the perpendicular pointing into the polygon the for all segments, if the point is on the correct side of all sides it's inside

[stone crystal]

I think that would only work for convex shapes right?

[haughty mountain]

though I think this only works properly for convex polygons, yeah

[stone crystal]

yeah that's why I asked about converting to triangles or convex polygons

[haughty mountain]

if it's only the perimeter that's annoying you could handle that as a special case

e.g. if it's within ε of the perimeter it's inside

[stone crystal]

hm

actually since my fake infinity is so far away I could just offset the y of the endpoint by 1

so that it won't hit any vertices

since all of this is on a pixel grid and is an integer

[tacit nova]

so binary tree 'depth' is counting from 0 as top to bottom, and 'height' is counting from 0 as bottom to top

i think left-right-root traversal is better for counting the 'height' of a node right ?
and root-left-right traversal is better for 'depth' right ?

[gleaming pelican]

Does anyone have a good introductory tutorial for someone that doesn't know anything about dsa/time complexity?

And what math do I need to know beforehand?

[haughty mountain]

for depth you want push an incrementing counter down the tree

for height you want to increment the return value of nodes (and a max over nodes)

so probably what you said, just phrased differently

[tacit nova]

yes sir, you put it more elegantly, also 'incrementing counter' sounds great for depth

something like this dfs(node.left, depth+1)

[fiery cosmos]

what does this mean in python, when you have two variable assignments in a single line:

def add_node(self, value):
    if self.head is None:
        self.tail = self.head = Node(value)

[rose flicker]

https://paste.pythondiscord.com/dinomelize
How should i go about adding multiple objectives to a bin packing problem with or tools?
I have a list of items each with a weight, volume, vendor, customer and port. I am easily able to constrain the bins on weight and volume but i want to alter the objective from least ammount of bins to least ammount of cost. Cost for a bin with 1 vendor and 1 customer is lower then a bin with 3 vendors, 3 ports and 3 customers for example.

[agile sundial]

the rightmost thing is assigned to everything on the left

basically, a = b = c is the same as b=c; a=b

[rose flicker]

I was thinking to create a model which generates the cost for bins and the objective is minimize cost. But i didnt know if there was a standard way of doing it

[fiery cosmos]

wouldn't it be b=c; a=c

thats how i interpret your statement at least

given by "the rightmost thing..."

[agile sundial]

no since c could be something like [], and both variables get the same reference

yeah, that explanation could be better

[fiery cosmos]

ok thanks

[vagrant perch]

can anyone walk me thru a traversal to find deepest leaves sum

its hard to grasp at first

how to make the queue?

[gleaming pelican]

Does anyone have a good introductory tutorial for someone that doesn't know anything about dsa/time complexity?
And what math do I need to know beforehand?

[opal oriole]

I would generally avoid this kind of multi-assignment because it's kind of confusing (I don't want to have to look up more language rules), with not much gain (just 1 less line).

[fiery cosmos]

I agree

[haughty mountain]

can you do something funky there through overloading?

I'm guessing no

actually, I seems like the assignment order is actually

a = c
b = c

though idk if you can detect that in any simple way

other than looking at the bytecode

ok, you can totally detect it

In [10]: a = [1, 2]                                                                                                                                     In [11]: a = a[1] = [42]                                                    --------------------------------------------------------------------------- IndexError                                Traceback (most recent call last) Input In [11], in <module>                                                  ----> 1 a = a[1] = [42]                                                                                                                                 IndexError: list assignment index out of range                                                                                                          In [12]: a                                                                  Out[12]: [42]

[fiery cosmos]

hey y'all,
i'm sort of struggling to implement functions where they take the array length input as arguments.. wouldn't it have to be precomputed? or how would you write from pseudocode that says something like:

def somefunction(A, p, r):
  do function stuff
  return A.modified

where r is taken to mean the length of the array

i think we were talking about this before

i'll try A.length as an argument

eh, i can just use it as is until i need to call it recursively

[haughty mountain]

wdym precomputed?

[fiery cosmos]

p and r are the beginning and end of the array A

i think to call this you'd have to compute the length of the array beforehand

bc the argument to a function len(array) when you're just passing it the same array as input won't work

[haughty mountain]

in the case of something like binary search the first call would just be smth like

bs(A, 0, len(A))

[fiery cosmos]

i think what they're calling for from the pseudocode is assigning the length of the array to a new variable r

idk i'm sort of struggling with how to structure the function definition when the input is the array, the beginning of the array, the end all in the def statement

def somefunction(A, startindex, endindex): like you have is fine