algos-and-data-structs

[haughty mountain]

you can do n=1 if you want

then our argument shows it's true for n=2

and that implies it's true n=3

and that implies it's true n=4

...

[vocal gorge]

I'd say induction follows immediately from basic logic, from whatever you call it that (A AND (A => B)) => B is true for all A,B

[fiery cosmos]

i still dont understand how to eval the left side. lets try it for the n+1 case where n=3. do you skip 3? and do 1+2+4?

[haughty mountain]

1 + 2 + 3 + 4

[fiery cosmos]

oh it is true

well i'll be darned

[haughty mountain]

the n+1 case is 1 + 2 + ... + (n-1) + n + (n+1)

[fiery cosmos]

alright i guess that's enough for one day

[haughty mountain]

on a personal level I don't like proofs by induction

they get the work done, but you rarely get any nice insights other than "it's true"

[fiery cosmos]

fair enough

[haughty mountain]

like, the formula for 1 + 2 + ... + n has a very nice classical proof

[fiery cosmos]

i hope next time we can work T(n) = 3T(cuberoot(n))+1, and find the asymptotic complexity of it using the master theorem. there are at least two different substitutions and you need the logarithm rules to achieve it, namely:

[agile sundial]

you can't really do that if you don't understand induction

[fiery cosmos]

well that's what we're working on

[opal oriole]

The n+1 case contains the n case. If we want to go to rung 3, we first need to go to rung 1, then to rung 2, then to rung 3. We start on the floor.

[fiery cosmos]

i understand what we're doing i just don't think it inherently makes sense. the presence of something one beyond another thing doesn't imply some assumption holds true

i guess in math it does..

[haughty mountain]

let's call the sum S

S = 1 + 2  + ... + (n-1) + n

add another version of S but in reverse

2S = 1 + 2     + ... + (n-1) + n
     n + (n-1) + ... + 2     + 1
```all pairs sum to `n+1` and we have `n` pairs

2S = (n+1) n

S = (n+1) n / 2

this is a much more satisfying proof

but the induction one is still a valid proof, it's just...boring

[opal oriole]

If you can climb to the first rung, and can "prove" to me that you can make it to any rung after the one you are currently on, then you can make it any rung (infinite stamina assumed).

[fiery cosmos]

let's imagine we could grab a single molecule in my swimming pool, and that we wanted to jump to another one, the jump implying the existence of the mol+1 molecule, because after all, we were able to jump to it. would it be helpful to imagine there are infinite molecules (jumps) simply because we were able to see a base case and a mol+1 case?

[opal oriole]

The infinite part here means we can apply the rung climbing as often as we want for our problem.

[haughty mountain]

you wouldn't be able to prove your induction step in that kind of scenario

[fiery cosmos]

why

[opal oriole]

In physically reality, nothing can be proven in the mathematical sense, only (at best) strongly demonstrated. Science is a method for strong demonstration / reproduction of some causal relationship(s).

"Proof" as used outside of math basically just means strongly demonstrated.

In math we can prove things because we can create ideal scenarios in which we know all the rules and all the variables.

[keen hearth]

Yeah, ironically mathematical induction is a form of deduction.

[fiery cosmos]

i think in a way i believe the rules to be arbitrarily set to make things make sense, and they aren't real rules or laws at all

[opal oriole]

However, the mathematical "worlds" we make up may still reflect real behaviors (that are observed) and so they make for useful predictors. That is when math becomes useful and not just an art (doing math for math's sake).

[haughty mountain]

the only things that are truly arbitrary in math are the handful of axioms at the bottom of math

[opal oriole]

*A good predictor does not need to know all the rules or variables.

[haughty mountain]

everything else is a consequence of those

[opal oriole]

And the axioms are often informed by whatever philosophy or to reflect what was generally observed in reality (for physics use cases).

[haughty mountain]

the math axioms are a bit more...basic

e.g. https://en.wikipedia.org/wiki/Zermelo–Fraenkel_set_theory

[opal oriole]

They are like the primitives that are chosen for whatever reason. But also some other stuff taken into account to make sure they don't break each other.

[haughty mountain]

other systems of axioms are available https://en.wikipedia.org/wiki/Peano_axioms

[opal oriole]

The book I recommend @fiery cosmos covers what axioms are too. And how to come up with your own, etc.

[haughty mountain]

they all end up being similar in terms of what they can express

[fiery cosmos]

concepts of modern mathematics?

[haughty mountain]

but of course Gödel and friends proved that any system of axiom has issues

[opal oriole]

Yes. It really covers a bit of everything without covering EVERYTHING, like all the essentials and common stuff found in modern math (various branches). Basically a dip into the pool at various ends of the pool.

[haughty mountain]

including true statements that are unprovable

[fiery cosmos]

i wish i had time to read it. my algebra is abhorrent

it is sitting here on my desk though

along with discrete math and its applications, shaums outlines on discrete math, and intro to algos 3rd edition

[opal oriole]

Yeah you need to work on your algebra or the rest will be a huge slow pain to go through, your algebra needs to be fast and natural.

[fiery cosmos]

whats the fastest way to brush up?

[opal oriole]

(Only lots of practice can fix this and keeping notes of common patterns like the multiply by fancy form of one)

[haughty mountain]

I think getting comfortable that induction is a technique that works will be something important for future stuff you'll encounter

it's a very common technique

[opal oriole]

(Rewriting things to see them from a new POV is key to math in general)

(Or drawing if you are doing geometry or plotting, etc)

[haughty mountain]

the deadly tricks of math was something that a university professor taught at my uni ages ago, I've only heard it second hand from older students as a legend

I can't recall if there was more than two

but I sure remember the first two deadly tricks

multiplying by 1

adding 0

[fiery cosmos]

how could adding zero help???

[haughty mountain]

add and subtract the same thing

[opal oriole]

Taking the log of an expression or exp it is one, shows up more in calc.

It's another one of those things you just do and see what happens.

A bit more complicated but any trig stuff.

[haughty mountain]

e.g. you can use it for rewriting fractions

  p/(1 + p)
= (1 + p - 1)/(1 + p)
= 1 - 1/(1 + p)

[fiery cosmos]

like +0 to one side and -0 to another?

[haughty mountain]

in the second line I add and subtract 1

and use those to rewrite the expression

[opal oriole]

1-1 is technically zero, so you added zero.

But putting them there makes it more obvious how to rewrite it.

[fiery cosmos]

i don't understand could you walk me through it

oh you add one and subtract one in the numerator

[haughty mountain]

yes

[fiery cosmos]

ok then what

[haughty mountain]

and then I can separate that expression like

(1 + p)/(1 + p) - 1/(1 + p)

which simplifies to just 1 - 1/(1 + p)

[fiery cosmos]

so you pull out the -1 from the top and set it equal to - (1/1+p)

[haughty mountain]

set it equal to?

it's just doing

(a + b)/c = a/c + b/c

you can always separate an expression like that

[haughty mountain]

right

[fiery cosmos]

ok great thanks

[haughty mountain]

actually, I think the example I should have done is probably p/(1 - p) since that kind of thing shows up a ton in probability theory

but it's the same exact kind of thing

and similarly you saw the multiply by 1 trick earlier

[fiery cosmos]

yes in the form of 2/2

[haughty mountain]

it sounds super dumb, but it's kinda silly how often you end up doing it to simplify stuff

[opal oriole]

Here is one to try: ```
2/x + 1/(x+1)

Combine them.

(Hint: you have to use the fancy form of one twice)

[fiery cosmos]

hmm

[opal oriole]

(Bonus general math hint: If the problem is too hard, solve an easier version of the same problem first)

[fiery cosmos]

dumb question but is 2/x + 1/x = 3/x?

[opal oriole]

Yes.

[haughty mountain]

yes

[fiery cosmos]

ok

man i dont know which way to go 😢

[haughty mountain]

make both things have the same denominator

[opal oriole]

Towards the thing you know how to handle.

You know how to add two things with the denominator.

The problem is that you can't add two things with different denominators, so you need to resolve that issue (in the same way we want to resolve issues like T(floor(n/2))).

[fiery cosmos]

what is 1/1 + 2/x?

3/x?

[opal oriole]

It's the same kind of problem from before, don't know how to add when they have different denominators.

[haughty mountain]

partial fraction decomposition goes brrrr

also, this gives me bad flashbacks

[fiery cosmos]

how are you formatting that

[haughty mountain]

not quite LaTeX, but something similar

[opal oriole]

To solve this, you need to find some way to change it without making the value different (e.g. multiply by fancy form of one or add fancy zero).

You specifically want to change it to something you do know how to do, adding two things with the same denominator.

[fiery cosmos]

i got nothing

[opal oriole]

What happens if you multiply the left one by x/x?

[fiery cosmos]

lms

i can multiply both sides by x/x but then i get 2x/x^2 + x/x^2+x

[opal oriole]

Just the left one.

[haughty mountain]

you don't have to multiply both sides by the same thing

[fiery cosmos]

oh sry i applied it to the original

[haughty mountain]

you're just multiplying by 1 after all

[fiery cosmos]

so you can get 2+x / x

[opal oriole]

So you combined both fractions.

Which is what was wanted.

Why were you able to combine them?

[fiery cosmos]

same denom

[opal oriole]

Correct. Is this new combined value different from the original value?

[fiery cosmos]

no

[opal oriole]

Correct. So now try the harder version from before. Same trick.

[fiery cosmos]

multiply one side by x/x?

[opal oriole]

Yes, but will they have the same denominator then?

[haughty mountain]

dumb answers only

[opal oriole]

lol

[fiery cosmos]

is that an integral or differential

[haughty mountain]

yes

[fiery cosmos]

the long S thing

[haughty mountain]

that's an integral

[fiery cosmos]

ok

[fiery cosmos]

no

[opal oriole]

But they are almost the same right?

[haughty mountain]

I guess take derivative and integrate is another deadly trick to do nothing

[opal oriole]

Can you do the same trick again to make them the same?

[fiery cosmos]

lms

[haughty mountain]

and in this case you it even turns the problem into logarithms, as mentioned before

it's genuinely not that annoying of an approach

and I think this kind of approach is actually used a bunch

[fiery cosmos]

ok so i get 2x/x^2 + x/x^2+x

[opal oriole]

It shows up yeah, but often for even harder stuff than this problem. It's the classic solve this math problem with overkill.

Fun to do.

[haughty mountain]

overkill for this case yeah

i just wanted to disregard your advice when you gave the problem

[opal oriole]

From the start, try multiplying one by the other's denominator over itself x/x and (x + 1)/(x + 1).

(Both are fancy forms of one)

[fiery cosmos]

wow thats kind of brilliant

who figures this stuff out

[haughty mountain]

it's a very standard technique

[opal oriole]

Centuries of mathematicians.

[fiery cosmos]

wait i didnt get that answer

i got 3x+2/x^2+x

[opal oriole]

(more like thousands of years)

[fiery cosmos]

oh

youre just showing the step

so is it that answer i got?

[haughty mountain]

yeah, I didn't want to do things the intended way

but here

[fiery cosmos]

ok ok

[opal oriole]

You leave the bottom factored or not.

[haughty mountain]

now, can we do something truly dumb

[fiery cosmos]

dumb and helpful yea?

[haughty mountain]

maybe a Laplace transform would work

[opal oriole]

Yeah it probably would.

[fiery cosmos]

oh youre doing math silliness

[haughty mountain]

it's a terrible idea, but it probably works

[fiery cosmos]

😵‍💫

[haughty mountain]

helpful is very debatable 😛

[mild obsidian]

What's the best way to learn data structures and algorithms?

[opal oriole]

Ok, so now that you combined them, you want to be able to go in reverse.

If you were given that end result, get to the start.

[fiery cosmos]

uhhh

ill try

[haughty mountain]

it will not involve one of the deadly tricks, sadly

[fiery cosmos]

you know what i will save it, i can't get burnt out on this stuff i have to study all summer in prep for algos in the fall

grad level algos in the engineering school shudder

[haughty mountain]

the boring answer is: read stuff, practice stuff
channel pins has some useful learning resources

[fiery cosmos]

@mild obsidian i did a python specific data structures course, now learning algorithms from the classic CLRS book

trying to learn

[haughty mountain]

the R in CLRS is Rivest right?

[fiery cosmos]

correct

Ronald L.

[haughty mountain]

aka the R in RSA

[mild obsidian]

thanks

[fiery cosmos]

whats RSA

[haughty mountain]

cryptography https://en.wikipedia.org/wiki/RSA_(cryptosystem)

[fiery cosmos]

oh jesus

don't even scare me w that stuff

trying to relearn algebra at 33

[haughty mountain]

my master thesis was actually about a small problem that was attributed to Rivest

[fiery cosmos]

MS in ?

i'm doing a non thesis MS

[haughty mountain]

err, it's complicated

[fiery cosmos]

MS in mathematics?

[haughty mountain]

I did my bachelor in engineering physics which is a ton of math and physics (both theoretical and experimental)

I got a bit sick of physics so I did complex adaptive systems as my master, which was a bit more CS slanted but still a lot of math

my master thesis was somewhere between CS and math

[fiery cosmos]

i guess you're most familiar with python given what server we're in

[haughty mountain]

idk about most familiar, I've probably used python the most, but I've used other languages a ton too

e.g. C++

[fiery cosmos]

nice

im basically just doing mine in a bid to escape the lab, otherwise i'll be stuck being a labhand forever and never make any money

undergrad in bio = youre done for

[haughty mountain]

https://odr.chalmers.se/bitstream/20.500.12380/300583/1/report_final_version.pdf it's only 72 pages

[fiery cosmos]

trying to learn bioinformatics. i got really good at RNAseq and practical lab stuff that nobody understands but it doesn't pay

ahh sweden. my former employer, our founder was from there

Johan

you know im completely incapable of understanding this yea?

so what do you do for work? write software?

[haughty mountain]

i ended up as a software engineer yeah

[fiery cosmos]

smart move

[haughty mountain]

can't complain

I didn't know what to do after university, but things ended up working out very well

[fiery cosmos]

lol im sure they did

software engineering is one of the best positions available

[haughty mountain]

oh god, writing semi-sensible pseudocode was interesting

[fiery cosmos]

yeah i have to do that for my course coming up

i don't think i'll get my B i need to continue, we'll see

[haughty mountain]

tl;dr in our simulation we worked with immensely big numbers, we needed decent algorithms to even find an upper bound

[fiery cosmos]

woah

[haughty mountain]

square stuff until your thing is large enough

and then do the binary search in the exponent

and then do a regular binary seach

[fiery cosmos]

who came up with the idea that you could use a recursive function to reduce runtime

[haughty mountain]

I mean recursion doesn't inherently make stuff faster

[fiery cosmos]

doesn't it?\

[haughty mountain]

it's just a convenient way to phrase problems in at times

[fiery cosmos]

for ever increasing n?

[haughty mountain]

in practice recursive implementations tend to be slower if the same algorithm can also be written iteratively

[fiery cosmos]

for small n thats true?

[covert thorn]

what's the actual explanation of why this is? overhead of function calls?

[haughty mountain]

recursion is just one way of phrasing problems, it's quite expressive and lends itself well to problems that can be broken down into similar subproblems

[haughty mountain]

yes, function calls are kinda costly

and iterative things tend to be easier to make cache friendly which matters a lot on modern CPUs

like, writing a matrix multiplication that goes across memory in the wrong direction can be like an order of magnitude slower

[fiery cosmos]

across memory in the wrong direction?

[haughty mountain]

reading a lot of stuff that is close in memory is fast

because the cpu loads the memory nearby into cache

[opal oriole]

The CPU predicts what you are going to do next / load next and pre-fetches.

[haughty mountain]

if you read memory that is far apart the values you're trying to read is not in cache and things get a lot slower

[opal oriole]

It also fetches in chunks.

[haughty mountain]

it also predicts, yeah

but a cache miss is still a cache miss

[fiery cosmos]

what is the cache

[opal oriole]

Memory speed matters way more now than the actual operations being done.

[fiery cosmos]

who optimizes this, the OS developers?

[haughty mountain]

what part?

the caches are in the cpu

e.g. the biggest cache tends to be something like 4MiB

you actually have many layers of caches on the cpu

[fiery cosmos]

microbase?

im just curious about the workings of the pc. i build my computers and write a little python but the in between is not well known

[opal oriole]

The user can optimize by having things be next to each other in memory, and have a predictable access pattern.

[haughty mountain]

e.g. here are cache sizes for the cpu I have

Caches (sum of all):     
  L1d:                   256 KiB (8 instances)
  L1i:                   256 KiB (8 instances)
  L2:                    4 MiB (8 instances)
  L3:                    32 MiB (2 instances)

the smaller caches are a lot faster, but can fit less

as soon as you need to load in new data, you need to go to a bigger cache, or in worst case to ram

(or disk, even)

[opal oriole]

(or network death)

[fiery cosmos]

what is the purpose of the cache, to quickly load up a small amount of data?

[haughty mountain]

to keep local data around for quick access, since you often fetch data that is nearby

[opal oriole]

Memory that is closer to where the memory is used is faster.

[fiery cosmos]

data being what

[opal oriole]

CPUs are so fast that this small distance for humans matters a lot.

[fiery cosmos]

like a software program? or an image?

[haughty mountain]

any memory that a program uses, really

even code

[fiery cosmos]

whats the difference between cache / RAM / SDD

SSD*?

[haughty mountain]

difference in what sense?

[fiery cosmos]

is the cache a physical piece of the cpu?

[haughty mountain]

yes

[fiery cosmos]

difference like why are they physically different devices

do they all have same function?

[haughty mountain]

they server different purpose

ssd and similar are for permanent storage, which is quite different

ram is quite fast and you can have a lot of it

the caches are small but are very fast

they work together to make things tick

as for speeds, here is some old useful numbers about rough speeds of things

L1 cache reference ......................... 0.5 ns
Branch mispredict ............................ 5 ns
L2 cache reference ........................... 7 ns
Mutex lock/unlock ........................... 25 ns
Main memory reference ...................... 100 ns             
Compress 1K bytes with Zippy ............. 3,000 ns  =   3 µs
Send 2K bytes over 1 Gbps network ....... 20,000 ns  =  20 µs
SSD random read ........................ 150,000 ns  = 150 µs
Read 1 MB sequentially from memory ..... 250,000 ns  = 250 µs
Round trip within same datacenter ...... 500,000 ns  = 0.5 ms
Read 1 MB sequentially from SSD* ..... 1,000,000 ns  =   1 ms
Disk seek ........................... 10,000,000 ns  =  10 ms
Read 1 MB sequentially from disk .... 20,000,000 ns  =  20 ms
Send packet CA->Netherlands->CA .... 150,000,000 ns  = 150 ms

so e.g. reading from RAM is on the order of 200x slower than L1 cache (the smallest cache)

[fiery cosmos]

🤔

interesting i never knew about the cpu cache

[haughty mountain]

it's kinda fundamental to what makes CPUs fast nowadays

[fiery cosmos]

they have 'cores' to allow parallel processing?

[haughty mountain]

well, each CPU core tends to have some caches on their own

e.g. on my machine I think every core has two caches of their own

but the biggest cache is shared

[opal oriole]

Parallel processing gets really complicated, when done properly. They can have their own cache each, shared caches, etc. Cores can often come in clusters, so to make it at fast as possible you need to do stuff like make sure the work is placed on the correct cores that are part of the same cluster to share memory.

[haughty mountain]

(of course, little of this matters if you use python, cache misses galore everywhere)

[opal oriole]

*If you just blindly make a new thread, the OS may actually place it in the right place, but often it does not.

*And depends on which OS then (and version).

[fiery cosmos]

what does a language have to do with the cache? or cache misses?

[haughty mountain]

e.g. lists in python are just a list of addresses

that points to other places in memory where things are actually stored

when you jump to that address it's very likely the thing you're jumping to is outside your cache, and you have a cache miss

in other languages the data is often stored in the lists/arrays themselves

so less jumping around

[opal oriole]

Also Python like many other high level languages likes to store everything on the heap, which means your memory is fragments scatters all over the place randomly.

Rather than nice big chunks.

(e.g. region based memory management)

[fiery cosmos]

what is the heap?

[opal oriole]

When you make a new object it needs to be placed somewhere in memory, and there are many ways of doing this. One way is storing it on a "heap".

[fiery cosmos]

is there a relationship between where my py script is stored on my hard drive and the data it references or assigns upon running?

[haughty mountain]

how does one explain the heap and stack in a sensible and short way...

[fiery cosmos]

"making an object"

[opal oriole]

And because of the way a heap works, it's very generic, but also results in downsides (generic solution vs specific one).

Like in Python when you do animal = Dog().

Made a Dog object.

[fiery cosmos]

when you say make a new object you mean declaring a variable

right ok

is that a dog class?

classes need initialized yeah?

[opal oriole]

That Dog has stuff in it, that needs to be somewhere in memory.

Or if you do x = 3, that needs to be somewhere in memory too.

And languages like Python will manage that for you in a generic way so you don't need to think about it, at the trade-off of that solution being kind of slow (or very slow in some cases).

[fiery cosmos]

when you say in memory do you mean RAM?

or hard drive

[opal oriole]

You can assume RAM for now for simplicity, there is more complicated stuff going on that the OS does with memory.

And the hardware.

[haughty mountain]

pages, cache lines, oh my!

[fiery cosmos]

can i ask a generic math question

i guess i could just prove it to myself with some math but i think y'all will know the answer immediately

[fiery cosmos]

go on

hang on

nvm i figured it out. i was just wondering about the diff between +50% over 5 years and +10% each year for 5 years. and they are indeed different. so you cannot look at the market and say +50% over the past 5 years is 10% per year, because 10% per year on the same amount is a different number due to the new principle amount added after the first year and second and so on

[stark stone]

the power of compound interest

[agile sundial]

might be a fun question for #pedagogy 👀

[regal gyro]

Any good books or videos for learning algorithms and algo analysis and data structure?

[halcyon mural]

The python XOR operator is not a very common operator and there's nothing wrong with you not using before.
Solution 1 in the code snippet below is an example of a good use case .
Feel free to share your thoughts.

[jolly mortar]

you can replace ^ with != there and some've argued that's clearer

id read some uses of xor here https://florian.github.io/xor-trick/

[plain violet]

If python's list is array of pointers, then getting element by index is O(1) and inserting/appending is O(n)?

[haughty mountain]

getting element by index is O(1), appending is amortized O(1), inserting is (I guess amortized) O(number of elements after the insertion point)

[plain violet]

Thanks

[tiny needle]

hi, someone could tell me about the libraries for building Blockchain (example: hashlib)

[halcyon mural]

True.

[austere sparrow]

I think it's clearer, but it stems from my general belief that integer arithmetic on bools is cursed

[tulip juniper]

Just started learning py need some help

[shut breach]

this channel is about algorithms and data structures, but you can open your own help channel from #❓｜how-to-get-help

[haughty mountain]

having an xor operator wouldn't be the worst thing ever

though it can't short circuit, sadly

[austere sparrow]

What would it do?

[haughty mountain]

^ but only operate on bool values

it might be easier to read, contrast

(x == 4) != (x == 2)
```vs

x == 4 xor x == 2

[lean walrus]

It can short curcuit in some cases. But it cant always short curcuit and always return original objects

XOR can be implemented in this way:
If first operand is falsy and return second operand:
falsy xor obj -> obj
If second operand is falsy it can return first (it is truthy because otherwise second operand should be returned)
obj(truthy) xor falsy -> obj
Finally, it should return False singleton, because both operands are truthy
truthy xor truthy -> False

def do_xor(obj1: T1, obj2: T2) -> T1 | T2 | Literal[False]:
    if not obj1: return obj2
    if not obj2: return obj1
    return False

>>> do_xor(0, 0)
0
>>> do_xor(0, 1)
1
>>> do_xor(1, 0)
1
>>> do_xor(1, 1)
False
>>> do_xor('', '')
''
>>> do_xor('', 'a')
'a'
>>> do_xor('a', '')
'a'
>>> do_xor('a', 'a')
False

>>> do_xor([], {})
{}
>>> do_xor([1], {})
[1]

[haughty mountain]

this isn't short circuiting though? you still need to evaluate all arguments unlike with or and and

[agile sundial]

what's n

yes

[lean walrus]

if first is falsy you can return second object
partial short circuit maybe?

[halcyon plank]

@mystic basin :white_check_mark: Your eval job has completed with return code 0.

001 | 1
002 | 1

[fiery cosmos]

yeah, the simple approach of checking all 9 columns and 9 rows and 9 squares is 3*81 checks -> O(3n) = O(n)

[agile sundial]

that's not short circuiting; you always need to evaluate both operands

[lean walrus]

def validate(field: list[list[int]]) -> bool:
    assert field and len(field) == len(field[0])
    n = len(field)

    for row in field:
        nums: set[int] = {*()}
        for item in row:
            nums.add(item)

        if len(nums) != n:
            return False

    return True
``` @mystic basin

[lean walrus]

oh, yes, you are right
i meant you can not call bool() on second operand and return it unchanged, but you anyway should evaluate it

[agile sundial]

how? you need the bool value of both operands, always

[lean walrus]

i forgot that sudoku has 3x3 squares
this code only checks rows and columns but not 3x3 squares

[lean walrus]

no
0 ^ x === x
so if first operand is falsy you can evaluate second and return this object, without calling a bool()

def do_xor(obj1: T1, obj2: T2) -> T1 | T2 | Literal[False]:
    if not obj1: return obj2 # we didn't call the bool(obj2)
    if not obj2: return obj1
    return False

[agile sundial]

ah right. you can skip that step, but that's not usually the expensive part that you want to avoid

[lean walrus]

anyway it is very non-obvious operation if we want to return original objects sometimes
without returning original objects it can be implemented in this way: ```py
def do_xor(obj1: T1, obj2: T2) -> bool:
return bool(obj1) ^ bool(obj2)

[fiery cosmos]

Hang on, I'm second guessing myself since it's more like checking 27 sets are equal, not 81*3 steps For a general size n*n sudoku checking each region takes at least O(n) and you do that 3*n times

(do general n*n beyond 9*9 sudokus even exist?)

for 9*9 validation is really O(1)

[haughty mountain]

it's 3*n in general to just check everything

any set of 9 can be checked in linear time easily

and you have all rows (n)
all columns (n)
all big squares (n)

[keen hearth]

Yeah, really it's O(1) because the size isn't variable.

If you were to generalise to larger square sudokus, I actually think it would make sense to parameterise them by the square root of the number of rows/cols/boxes

E.g. a size 1 sudoku is 1x1, a size 2 sudoku is 4x4, a size 3 sudoku is 9x9, ...

Then for a sudoku of size n, you'd have to check 3 * n**2 units (rows/columns/boxes), and each can be checked in n**2 time, so it's O(n**4) time overall.

[bright ginkgo]

im trying to solve this leetcode problem https://leetcode.com/problems/path-sum-ii/

this is my solution. I'm close to having a working solution but its not quite there. anyone help? thanks

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
       
    # Recursive function - perform following logic for each visited node
    def pathSumTraverse(self, node, targetSum, sum, currentPath, results):
        
        # base case
        if node is None: 
            return
                
        # add node value to sum
        sum += node.val
        currentPath.append(node.val)
        
        # check if node is a leaf node
        # check if sum equal is targetSum
        if node.left is None and node.right is None:
            print(node.val)
            if sum is targetSum:
                results.append(currentPath)
                
        
        # recursion
        self.pathSumTraverse(node.left, targetSum, sum, currentPath, results)
        self.pathSumTraverse(node.right, targetSum, sum, currentPath, results)

        return
    
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]: 
    
        # edge case
        if root is None: return []

        # initial values
        results = []
        path = []
        sum = 0
    
        # Pass the following to recursive function:
        # current node
        # targetSum
        # sum
        # node path
        # results list
        self.pathSumTraverse(root, targetSum, sum, path, results)
        
        return results

[jolly mortar]

        self.pathSumTraverse(node.left, targetSum, sum, currentPath, results)
        self.pathSumTraverse(node.right, targetSum, sum, currentPath, results)

i think you should pass in currentPath.copy()s here

[bright ginkgo]

replace sum you mean?

yea it works

[merry nova]

also you're comparing the sum with is?

[bright ginkgo]

why do i have to use currentPath.copy()?

i was stuck on this for the longest time

[jolly mortar]

lists are mutable, so the list passed to node.right's traverse will have all the appends made in node.left's traverse

[bright ginkgo]

i have a C++ working solution

#include <iostream>
#include <vector>

     class Solution {   

       void pathSumTraverse(TreeNode *node, int targetSum, int sum, vector<int> currentPath, vector<vector<int>> &results) {
         if (node == nullptr) {
             return;
         }        

        sum += node->val;
        currentPath.push_back(node->val);        
                     
        if (node->left == nullptr && node->right == nullptr) {
            if (sum == targetSum) {
                 results.push_back(currentPath);
            }
        }        
        
        pathSumTraverse(node->left, targetSum, sum, currentPath, results);
        pathSumTraverse(node->right, targetSum, sum, currentPath, results);
        return;
     }
         
         
      public: vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
         vector<vector<int>> results(0);
         vector<int> path(0);
         int sum = 0;
         pathSumTraverse(root, targetSum, sum, path, results);
          
         return results;
     }
 };

are vectors different than lists?

[merry nova]

# check if node is a leaf node
# check if sum equal is targetSum
if node.left is None and node.right is None:
    print(node.val)
    if sum is targetSum:
        results.append(currentPath)

------

if sum == targetSum and not node.left and not node.right:
    print(node.val)
    results.append(currentPath)

you probably want to refactor that if comparison

[bright ginkgo]

isnt is same as ===?

[merry nova]

kind of?

is checks for identity, not just type and value

Python doesn't auto cast types with == so that is what you should use for value comparisons

[bright ginkgo]

so is == in python the same as === in JS?

[merry nova]

'1' won't automatically == 1, for example

[jolly mortar]

yeah

[bright ginkgo]

ok thanks

[merry nova]

!e

a = 123984
b = 123984
print(a == b)
print(a is b)

[halcyon plank]

@merry nova :white_check_mark: Your eval job has completed with return code 0.

001 | True
002 | True

[merry nova]

hm

[jolly mortar]

very hm

[merry nova]

!e

a = 123984
b = 123984 + 64 - 64
print(a == b)
print(a is b)

[halcyon plank]

@merry nova :white_check_mark: Your eval job has completed with return code 0.

001 | True
002 | True

[merry nova]

wat

[jolly mortar]

constant folding probably

!e

a = eval("123984")
b = eval("123984")
print(a == b)
print(a is b)

[halcyon plank]

@jolly mortar :white_check_mark: Your eval job has completed with return code 0.

001 | True
002 | False

[bright ginkgo]

how do you do that?

[merry nova]

!e

from secrets import SystemRandom

r = SystemRandom()

a = r.randint(1, 10**30)
b = a * 2
a += a
print(a)
print(id(a))
print(id(b))
print(a == b)
print(a is b)

[halcyon plank]

@merry nova :white_check_mark: Your eval job has completed with return code 0.

001 | 1518753915678391155875462730128
002 | 139661453617808
003 | 139661453617856
004 | True
005 | False

[merry nova]

well small values of int are usually cached in python, and they're immutable, so sometimes you do end up with the exact same object

but that's not guaranteed, so for value comparison you should use ==

[bright ginkgo]

if i do 1 is "1" I was expecting true but im getting false

[merry nova]

no, python doesn't automatically cast types, it's strongly typed, so to speak

you can do

[bright ginkgo]

then in what situations will using is vs == be different?

[merry nova]

!e

print(1 == int("1"))

[halcyon plank]

@merry nova :white_check_mark: Your eval job has completed with return code 0.

True

[jolly mortar]

two different objects can have the same value, == would be True and is would be False for them

[bright ginkgo]

aren't strings objects?

[jolly mortar]

yes

[bright ginkgo]

hmm ok I'll just use == for now on. I've always thought is and == were interchangeable

[jolly mortar]

with some exceptions, == will always be False if the operands are of different types

[bright ginkgo]

but it seems like it's the same as using == and === in JS

[merry nova]

== ignores types right?

there is no equality in python that ignores types, whether == or is

[bright ginkgo]

yes I believe so

=== will compare types

[merry nova]

with some exceptions though, python does also have the idea of Truthy or Falsy values when evaluated in a boolean context

[bright ginkgo]

interesting

[merry nova]

!e

if 0:
    print('0')
if 1:
    print('1')

[halcyon plank]

@merry nova :white_check_mark: Your eval job has completed with return code 0.

1

[merry nova]

so there 0 is falsy and 1 is truthy

[bright ginkgo]

yes

[merry nova]

but this behavior doesn't carry outside of bool contexts

[bright ginkgo]

so this line if node.left is None and node.right is None: I should just replace is w/ ==?

or do I use ===?

[merry nova]

there is no === operator in python

you can compare None with is because it's always the same object

you're comparing identity

[bright ginkgo]

was it you that told me you use currentPath.copy()?

[merry nova]

but also None types are falsy, so you can also do:

if not node.left and not node.right:

but know that ints of 0 are also falsy

so that might not be what you want

if you only want to match None, then use the is None

[bright ginkgo]

I think I have to check if node is None

[merry nova]

I don't think that's the issue though, lemme see

[merry nova]

do you need to pass both the target and sum? Would the remaining be enough?

[merry nova]

probably like:

class Solution:
    def pathSumTraverse(self, node, remainingSum, pathNodes, pathsList):
        
        # Base case
        if not node:
            return 
        
        # Add current node to path's list
        pathNodes.append(node.val)

        if remainingSum == node.val and not node.left and not node.right:
            pathsList.append(list(pathNodes))
        else:    
            # Otherwise -> recurse on the left and the right children
            self.pathSumTraverse(node.left, remainingSum - node.val, pathNodes, pathsList)
            self.pathSumTraverse(node.right, remainingSum - node.val, pathNodes, pathsList)
            
        # After going through all subtrees, pop the node
        pathNodes.pop()    
    
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        pathsList = []
        self.pathSumTraverse(root, sum, [], pathsList)
        return pathsList

[bright ginkgo]

hmm

[steel jungle]

Can anyone help me with this problem? honestly I don't really know how to start
https://projecteuler.net/problem=83

[haughty mountain]

Dijkstra's algorithm is the thing you want to research

[steel jungle]

thank you so much!

[hollow wasp]

Hey, am 16 and am learning algorithms and would really need help or motivation or company in this journey to become a good programmer

anyone interested?

[prime heath]

A graph contains two kinds of edges, say solid and dotted. We have to find the largest component containing only solid edges, where no two vertices have a path between them which contains dotted edges. How do I solve this in linear time, any idea?
Edit: It has to be a complete component, i.e. all nodes reachable via solid edges from the current answer must also be part of the answer

Here is a horribly drawn illustration. In this graph, 12345 is the answer.

But here, 3 and 4 has a path (3-5-6-7-4) which contains dotted lines(5-6, 7-4), so 1-2-3-4-5 can't be the answer. Neither is 1-2-3-5, since it's not a complete component. So 8-9-10 is the largest valid component here

[steel jungle]

I am, I'm almost in the same situation

[spare olive]

confused, on your first illustration 5-6 are connected by dotted lines but 12345 is accepted answer. On your second illustration because 4 and 7 are now also connected by a dotted line 12345 is not accepted. Ether way they have dotted lines attached no, why is one ok and the other not?

[prime heath]

12345 is accepted in the first as there is no path between any two nodes in that component which contain dotted edges. 6 is connected by dotted edge but is not part of the component.

[ivory yacht]

I reckon you can solve this in two stages - first find all the possible groups, then discard ones with dotted edges. First use a breadth-first or depth-first search to find each component graph, ignoring dotted connections. Make a unique index for each component, and store that on the nodes (or in a dict indexed by node). Make a "valid" bool array, one for each component graph. Then loop over all the dotted links, lookup the component graph index for each side. If they're the same, that component graph is invalid so set the bool flag false. You now know which components are valid.

[prime heath]

Hi, thanks for the idea. But I think it does not work for the second case. We will have three components: 12345, 67, and 8-9-10.

Now we have two dotted edges: 5-6 and 4-7. But they belong to different components. 5 belongs to 12345, and 6 belongs to 67. Similarly for 4-7. So we can't invalidate 12345, right?

[ivory yacht]

Hmm, another approach is to compute components including dotted lines, then if there's dotted links repeat the search ignoring dotted ones, and verify you still find all items.

[spare olive]

Ok so outside path connecting 4-5 which includes the dotted lines excludes that 'component'. dashed link = ok, dashed loop = bad?. Since both examples 12345 are a sub-component with 6 etc also being connected, I assume 1,2,3 would be equally as valid as the 6,9,10 answer in illustration 2 for largest component? trying to understand the problem fully.

I think I would find each fully connected (non dash) component - ie 1,2,3,4,5 + 6,7 + 8,9,10. Then one component at a time, first delete all the solid edges interconnecting it - and test all pairs (1-2, 1-3, 1-4, 1-5, 2-3,, 2-4 etc) with a shortest path algo to test if they are still connected. If you started with max sized component with non-dash i think if any two points that make it up are still connected after deleting those edges then what is connecting it must contain dashed lines? Then if my 123 is valid reasoning holds true, as you find invalid points like 4 and 5 being connected outside you can remove those from the 12345 set and retest on the 123 which should then pass?

[fiery zenith]

how can i swap to variables with python

dooh sorry

wrong channe;

nvm

[slate jungle]

guys i want to ask simple python problem

anyone can help?

[fiery cosmos]

@slate jungle ask mate

Don't ask to ask.

[slate jungle]

Input_list = [
{"id": 1, "item": 2},
{"id": 2, "item": 4},
{"id": 1, "item": 5},
{"id": 2, "item": 6},
{"id": 1, "item": 7},
{"id": 3, "item": 8},
]

Output =

[

{"id":3, "item": 8},

{"id":2, "item": 6},

{"id":1, "item": 7}

] like last repreated keys value will be output.

@fiery cosmos

[runic tinsel]

use a dictionary

[slate jungle]

?

these are dictionaries inthe lisst

[agile sundial]

why do you need that format, why not
{3: 8, 2: 6, 1: 7}

[slate jungle]

yeah it wil work fine

but how?

[agile sundial]

with a dictionary

loop over the subdicts, add the keys and values to a new dict

[naive fulcrum]

hi someone know if can be helpful a method wich replace a key in an ordered hashMap (like the linked hashmap in java)?
so for example {3:4, 5:5, 6:6} replace the key 3 with 4 ---> {4:4, 5:5, 6:6}, and the order is anyway 4:4, 5:5, 6:6
example 2. {7:7, 8:8, 1:2} replace the key 1 with 2 ---> {7:7, 8:8, 1:2}, and the order is anyway 7:7, 8:8, 2:2

[lament totem]

Well adding a key value pair makes it append to the end of the dictionary, since a dict is sorted by insertion order @naive fulcrum

So you would have to remove the original key value pair, add the updated one, and then make a new dict that is sorted

[naive fulcrum]

yeah but there is a solution to this, i think than we can make it in constant time

[lament totem]

What do you mean with ordered hashMap?

Because if you are using an ordered dict or a regular python dict, the order is by insertion

And you can't change a key unless it is mutable, which is not the case as keys need to be immutable and hashable

So you would need to make a new key value pair, and inserting that in a specific position requires you to make a new dict with the key/value pairs inserted in desired order

[tacit nova]

code

print(root.left)
print(root.right.left)
print(root.left == root.right.left)

output

TreeNode{val: 2, left: TreeNode{val: 4, left: None, right: None}, right: None}
TreeNode{val: 2, left: TreeNode{val: 4, left: None, right: None}, right: None}
False

question : so obviously they are 2 different nodes in a binary tree, but they have identical subtree and value, so why a simple == comparison doesn't work ?

[haughty mountain]

have you defined equality?

it defaults to doing id(a) == id(b), which is indeed false in your case

[tacit nova]

oh so it checks id, make senses

thank you

[misty lily]

will someone teach me how to make algorithms

[sonic scaffold]

if you can make a sandwich, you can make an algorithm

the challenge is implementing an algorithm

[misty lily]

#!/usr/bin/env python3
# -*- coding: utf_32 -*-

def AND(a,b):
    if a == True and b == True:
        return True
    else:
        return False

def OR(a,b):
    if a == True or b == True:
        return True
    elif a + b == True:
        return True
    else:
        return False
        
def NOT(a):
    if a == False:
        return True
    else:
        return False

def NAND(a,b):
    if a == True or b == True:
        return True
    elif a and b == False:
        return True
    else:
        return False

def NOR(a,b):
    if a + b == True:
        return False
    elif a or b == True:
        return False
    else:
        return True

def XOR(a,b):
    if a or b == True:
        return True
    else:
        return False```

this is the code i have

uft_32 whawts that

its that what arcutecture its using

(A ~ B) -> (B - A)

is that an algorithm?

i just make that from scratch

[misty lily]

(A ~ B) -> (B - A)

[sonic scaffold]

this looks like a bunch of functions checking logic

[misty lily]

i not understand this

https://softwareengineering.stackexchange.com/questions/184089/why-dont-languages-include-implication-as-a-logical-operator

im trying to write an implies

->

[shut breach]

a -> b == (not a) or b

== not (a and not b)

[misty lily]

ah okay so its not at the first varable and or at the second then that equals not at a and not at be

?

[shut breach]

i didnt understand that

[misty lily]

to imply a varble agaisnt another varaible

A -> B

why is there a perentisis

iws that like encapsualtng the varible

no sure how i can pass in a not if the value is 1

[shut breach]

the parentheses are for appropriate scoping

[misty lily]

which one of the funcs has a as true and b as true just that

so i can imply

or would i make a global a and b

that would be an nand gate

sec

im not sure how to apply your implies logic

@shut breach

are you there?

i want to write an assembly file after i get the logic gates connected

and connect the assembly to the py file

[elder bolt]

bro what you want is a
"""
def impl(a,b):
return not(a) and b
"""

[misty lily]

ah okay

[elder bolt]

Do you want to use it as a function?

Or as a symbol?

[misty lily]

something like a buffer

?

[elder bolt]

A buffer??

[misty lily]

yeah a not with out the circle at the output

[elder bolt]

Without th3 circle at the output?? You mean the error mark?

[misty lily]

how to use the function in a fucntion

    return not(a) and b

NAND(1,0) ```

i want to do A -> B

inside of the nand

[fiery cosmos]

Good evening, can anyone explain to me how this code works?

"index = 0
while index < len(fruit):
letter = fruit[index]
print(letter)
index = index + 1"

[misty lily]

while the index is 0 which is false it will chave a comparrsion operator that conditions while the index is less than the length of fruit letter assign to fruit with the index being iterated of the fruit array then prints the letter then index assign to index and modulate 1

is that what it means?

i wouldnt ask that question in here

this is for algorithms an datastructs

open a help channel

@fiery cosmos

[fiery cosmos]

Ohhhh, I see, thank you

[fiery cosmos]

Oh sorry, I didn't notice that

[misty lily]

i worked it out

    return (not a) or b
    
implies(NAND(1,0), NAND(0,1)) ```

problem solved

can someone tell me what ~ means?

i looked it up i cant find it

[lament totem]

Generally means not

[misty lily]

ah olay

[lament totem]

It's a lazy ¬

[misty lily]

(A ~ B) -> (B - A)

whats missing?

(NAND(1,0) NOT(1) NAND(0,1)) implies(NAND(1,0), NAND(0,1)) (NAND(0,1) - NAND(1,0))

[{
"resource": "/c:/Users/Guest1/Programming_new/python projects/12-5-2022/main.py",
"owner": "generated_diagnostic_collection_name#0",
"severity": 8,
"message": ""(" was not closed",
"source": "Pylance",
"startLineNumber": 49,
"startColumn": 1,
"endLineNumber": 49,
"endColumn": 2
}]

@lament totem

can you find anything wrong with the syntax, it looks correct to me

i jsut added ,

(NAND(1,0), NOT(1), NAND(0,1)), implies(NAND(1,0), NAND(0,1)) (NAND(0,1) - NAND(1,0))

SyntaxError: encoding problem: utf_32```

why is this happening?

PS C:\Users\Guest1\Programming_new\python projects\12-5-2022> py main.py Traceback (most recent call last):
File "C:\Users\Guest1\Programming_new\python projects\12-5-2022\main.py", line 50, in <module>
(NAND(1,0), NOT(1), NAND(0,1)), implies(NAND(1,0), NAND(0,1)) (NAND(0,1) - NAND(1,0))
TypeError: 'bool' object is not callable
PS C:\Users\Guest1\Programming_new\python projects\12-5-2022>

what is this?

[fiery cosmos]

Seems missing a comma after the implies chunk

[fiery cosmos]

And maybe a final )

[slate jungle]

this dictionary should be in list

[misty lily]

works

thanks

can someone explain this to me what is actually happening

are you sure its # (A ~ B) -> (B - A)

(True, False, True) True 0
i think i could use these methods to make AI functionality
then i should work on more deep learning so i can learn more bout machine learning code
and i also want to make it so i can have assembly connected with the python so i can access system archietecture
that way i can program the hard ware of a computer

and that way can use machine code and deep learning to program the functionaliuty of a computeres architecture

[open moth]

How to solve time limit exceeded at sublime and python could only run first several lines and couldnt output all input how to run all input at ide

[naive fulcrum]

ok i understand, i don't know how much expensive that idea can be for the spatial complexity, but if we follow the order from a queue wich have double linked nodes(the value of the node is the key of the dict), in this way we can change the the value of the node and insert the new value of the key wich we would like to replace, but at the same time we should crate an hashMap of keyValue: NodeAdress, maybe later i can show you the code, or here is good too? (so yes we add a new key:value in the hashMap, and with ordered hashMap i mean an order by insertion)

[misty lily]

looking for a trust worth person, hit me up in a dm

[open moth]

Have you used numba

[ionic locust]

https://stackoverflow.com/a/26551061/10613037
Trying to understand bfs graph traversal time complexity. In this answer, why are there 6 steps, when the the total number of iterations of V + E should be 8? Is that because the steps don't include the checks for when the adjacent edges have been visited?

[wraith pivot]

Can yall tell me where I coukd learn dsa efficiently

[lethal bronze]

you are confusing big O notation with how many steps it actually takes, O(V + E) it just means as V and E get very big the number of iterations is less than some multiple of V + E

https://en.wikipedia.org/wiki/Big_O_notation sometimes its also revered to as landau notation or symbols

[glacial sail]

unsorted_list = [6,3,1,7,9,11,4,15,99,12,199,2,-1]
def selection_sort(list_to_sort):
    new_list = list()
    for i in range(len(list_to_sort)):
        def find_the_smallest_num(our_list):
            first = our_list[0]
            for i in range(len(our_list)):
                if our_list[i] < first:
                    first = our_list[i]
                else: continue
        smallest = find_the_smallest_num(unsorted_list)
        new_list.append(list_to_sort.pop(smallest))
    return nowa_lista

print(selection_sort(unsorted_list))

Traceback (most recent call last):
File "C:/Users/sebik/Desktop/algorytmy/selection_sort.py", line 15, in <module>
print(selection_sort(unsorted_list))
File "C:/Users/sebik/Desktop/algorytmy/selection_sort.py", line 12, in selection_sort
new_list.append(list_to_sort.pop(smallest))
TypeError: 'NoneType' object cannot be interpreted as an integer

help me, guys

update:

unsorted_list = [6,3,1,7,9,11,4,15,99,12,199,2,-1]
def selection_sort(list_to_sort):
    new_list = list()
    for i in range(len(list_to_sort)):
        smallest = min(unsorted_list)
        new_list.append(list_to_sort.pop(smallest))
    return nowa_lista

print(selection_sort(unsorted_list))

Traceback (most recent call last):
File "C:/Users/sebik/Desktop/algorytmy/selection_sort.py", line 17, in <module>
print(selection_sort(unsorted_list))
File "C:/Users/sebik/Desktop/algorytmy/selection_sort.py", line 14, in selection_sort
new_list.append(list_to_sort.pop(smallest))
IndexError: pop index out of range

how to fix it, guys?

problem solved:

unsorted_list = [6,3,1,7,9,11,4,15,99,12,199,2,-1]

def findSmallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index

def selection_sort(list_to_sort):
    new_list = list()
    for i in range(len(list_to_sort)):
        smallest = findSmallest(list_to_sort)
        new_list.append(list_to_sort.pop(smallest))
    return new_list

print(selection_sort(unsorted_list))

[tacit halo]

wouldnt in the findSmallest min(arr) work?

[haughty mountain]

because it's an argmin, not a min

though you could write it using min if you want to

min(range(len(arr)), key=lambda i: arr[i])

[glacial sail]

It doesn't work, because it needed index of the smallest number, not a value

[lament totem]

min(zip(values, range(len(values))))[1]

[haughty mountain]

-1 for being a lot more obscurely written

rather than min with key which literally is a form of argmin

[ionic locust]

Ah yeah true

[misty lily]

https://stackoverflow.com/questions/72682041/global-statemachine-handler-in-godot

will someone help me out with this

[heady lotus]

are there any other algoritm for image classification other than using cnn

?

[haughty mountain]

of course there are other approaches, but ML based neural nets outperform basically anything else for general image recognition

[tacit halo]

right

[tacit halo]

yeah

[radiant fox]

how would I generate combinations like the following (using the example string '1234')?

1 + 2 + 3 + 4
1 + 2 + 34
1 + 23 + 4
1 + 234
12 + 3 + 4
12 + 34
123 + 4
1234

(the string of digits has a variable length and I only need need the sum of each of these combinations)

I tried looking at itertools.combinations/permutations but it doesn't seem like they would help me here

[vocal gorge]

That's equivalent to all possible choices of whether to place a separator in each of the 3 places between the numbers.

so powerset(range(3)) (where powerset is one of the recipes in itertools docs), and then transform them like () => 1234, (2,) => 123 + 4, (0,1) => 1 + 2 + 34

[fiery cosmos]

hey can y'all give me a hint without giving up the answer

i wanted to assume the summation was equal to the expression for purpose of induction and then evaluate the n+1 case, but n+1 in the expression is confusing. let me try by plugging in n+1 for n in the expression

[vocal gorge]

wow, that's some super confusing notation

[fiery cosmos]

don't worry, i know what it means

after my first step i get:

[vocal gorge]

just to check: you got that it means (n+1)*n/2, right?

[fiery cosmos]

yes, allow me to rewrite it the way it appears in the book

[vocal gorge]

alright then

[fiery cosmos]

anyway after my first step (allowing it to be true for purpose of induction and then setting out to prove the n+1 case) i get:

am i on the correct track?

[vocal gorge]

You forgot to change n to n+1 on the left.

[fiery cosmos]

i dont think i did?

oh oh oh

in the summation

[vocal gorge]

yeah

[fiery cosmos]

ok

like so?

[vocal gorge]

Sure

[opal oriole]

The important part here is showing the steps.

[fiery cosmos]

for sure

[fiery cosmos]

where should i go after i get here.. its just algebra yeah?

[opal oriole]

A base case.

[fiery cosmos]

hm

[radiant fox]

thanks, this works! ```py
def operation_combinations(digits: str):
length = len(digits)
for separators in powerset(range(length-1)):
total = 0
prev = 0

    for separator in separators:
        total += int(digits[prev:separator+1])
        prev = separator + 1

    if prev < length:
        total += int(digits[prev:])

    yield total

[fiery cosmos]

trying to figure it out without turning the page and revealing answer

[opal oriole]

What I meant is that you need to show how to transform the n case into the n+1 case, just showing the n case and n+1 case and not how to get from one to the other does not prove anything, it's jumping to the conclusion.

[fiery cosmos]

hm

[opal oriole]

You showed the start and end point, but you need to connect the dots in between.

[fiery cosmos]

then they sub in the expression for the summation on the right hand side

[opal oriole]

That works too, you can connect the dots from either end.

[fiery cosmos]

^^ which becomes this ^^

how do you algebraically evaluate the expression on the right?

[opal oriole]

You are given some value for n, substitute, simplify.

I'm guessing you don't mean evaluate though.

[fiery cosmos]

no they go right from that to

wondering how they did that

right hand side of eq

[opal oriole]

2/x + 1/(x+1)
``` Remember?

How to combine them.

[half lotus]

Are you asking how to go from #algos-and-data-structs message to #algos-and-data-structs message ?

[fiery cosmos]

yes

[half lotus]

Would you like to see the step by step algebra for it or you want to try to figure it out yourself?

[fiery cosmos]

i think i can figure with something squggle showed me before, let me try

[fiery cosmos]

3x+2/x^2+x

i just reworked it but not sure how to apply that trick to the given problem

[opal oriole]

You have something/2 + something else = something/2 + something else/1 = ...

[fiery cosmos]

can i rewrite 1/2n(n+1) as n(n+1)/2?

[half lotus]

Yes. Multiplying by half is equivalent to dividing by 2

[radiant fox]

unfortunately this doesn't seem to be fast enough for my purposes (there can be 10^4 digits), I posted my code above, can you think of any way to speed this up?
(it seems to slow down because of powerset)

[opal oriole]

The notation is ambiguous as written.

[opal oriole]

It's (1/2)*(2(n+1)) or (2(n+1))/2.

[fiery cosmos]

this is as written in the book

[opal oriole]

1/2n(n+1) is not the same thing

[fiery cosmos]

as what

[opal oriole]

Inline math requires some more notation (or other context) to make it not ambiguous.

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

[fiery cosmos]

right its 1/2n*(n+1)

?

[opal oriole]

When doing inline math just use parenthesis for the numerator and denominator.

[fiery cosmos]

ok i've just proved to myself that 1/2n*(n+1) can be rewritten as n(n+1)/2 and evaluates the same

so i get that

now let me solve the original problem

err

let me solve going between here and here:

[haughty mountain]

remember what I showed last time?

1/2*n*(n + 1) + (n + 1)
```how many (n+1)s do we have?

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

^
that many (n+1)s

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

[fiery cosmos]

i remember being confused last time but i was able to transform the expression to the final answer using the multiply by one trick and setting the expression 1/2n(n+1) to the form n*(n+1)/2

[haughty mountain]

or maybe use the deadly trick of multiplying by 1 again

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

[fiery cosmos]

and multiplying each expression by the other's denominator

[haughty mountain]

right

[fiery cosmos]

in the form of 2/2 for example

anyway, i don't understand your "how many (n+1)'s do we have?" but i'll get there

[haughty mountain]

I mean, it's on the same line as, I have 5 apples and 3 more apples, how many apples do I have?

[fiery cosmos]

working through the appendix on bounding summations

i'm not seeing it from that perspective, don't worry about it. it'll click. need to move on

[haughty mountain]

the apples example is just

x*a + x*b = x*(a + b)

e.g. look at

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

my x in this case is (n + 1)

on the left I have 1/2*n copies of (n+1), on the right I have 1 copy of (n+1)

I guess phrased more properly you can just factor out the common factor (n+1)

factoring expressions is a very common thing to do when simplifying expressions, you should get used to it

[fiery cosmos]

ok. thanks for help. next example is using induction to prove:

[haughty mountain]

but intuitively it just boils down to "I have a copies of x and b more copies of x, so in total I have a+b copies of x"

[fiery cosmos]

oh. thanks for that explanation, its surprisingly logical

[opal oriole]

(ax is the area of the first rectangle, bx is the area of the second, and (a+b)x is the area of them added together)

[fiery cosmos]

oh wow

[dapper sapphire]

Is python's in and not in for a dictionary O(1) or O(n)?

[haughty mountain]

O(1)

[fiery cosmos]

O(1)

[haughty mountain]

(typically, unless you have very very bad data)

[opal oriole]

(geometry and algebra are talking about the same things (algebra just becomes more efficient with more complex things and goes beyond things easy to visualize (especially more than 3 dimensions)))

[haughty mountain]

what have you tried?

[fiery cosmos]

i'm just looking at how they get their initial expression. last time it was straightforward and i was able to do myself. this one is a bit more involved

[haughty mountain]

wdym how they get their initial expression?

[dapper sapphire]

ok thanks!

[fiery cosmos]

like so for the last one, they set out to prove that

so i was able to generate the new expression by assuming the expression to be true, and writing a new expression:

[haughty mountain]

yes, what you try to improve with induction is kinda just an educated guess

[fiery cosmos]

so i'm seeing now how they did that for this more complicated example and its not quite as straightforward

they begin here:

they then go here:

[haughty mountain]

that should be =, right?

[fiery cosmos]

oh, you're correct

i guess whats got me confused is in the n+1 case you must add 3^(n+1)

but theyre using this to try to prove that the geometric series is O(3^n), so i guess that makes sense

[opal oriole]

3^0 + 3^1 + 3^2 + 3^3 + 3^4 + ... + 3^n = sum from 0 to n of 3^k, so the n+1 case is?

[fiery cosmos]

right right i see it

this is just the appendix 🥵

very necessary though i suppose

thanks @opal oriole @haughty mountain i'll be back tomorrow 🙂

[haughty mountain]

is there a nice proof that doesn't boil down to proving that 1 + 1/3 + 1/9 + ... is bounded by a constant?

the think I'm doing boils down to basically that

let the sum with n terms be S(n), the claim is

  S(n) <= c 3^n

let's assume that that's true then
  S(n) =  S(n-1) + 3^n
       <= c 3^(n-1) + 3^n
       =  c/3 3^n + 3^n
       =  (c/3 + 1) 3^n

so the constant goes c -> c/3 + 1

if you keep iterating things will grow, but ultimately will be bounded by a constant

[opal oriole]

Yea

[haughty mountain]

bounded by 3/2, but making use of the sum of a infinite geometric series feels like cheating

maybe the argument that for any c > something the constant will decrease is a solid enough argument actually

e.g. for 2 and above this thing will decrease, so the constant can never grow larger than 2

actually, that's not quite enough

since that's true for some divergent series as well

[fervent saddle]

If you were making snake game with an arbitrarily large grid, how could you generate the food on the grid in O(1) time? How could you avoid snake occupied spaces?

[runic tinsel]

set

oh i get what you're asking

you mean O(1) relative to grid size too, or only snake length?

[opal oriole]

Keep track of unoccupied and occupied cells. To place a food, choose a random cell from the list of unoccupied cells and moved it to the occupied list, O(1).

(sets)

[fervent saddle]

Relative to grid size too

[haughty mountain]

you can't pick a random element from a set in O(1)

[fervent saddle]

How do you remove grid spaces in the occupied list in O(1) time?

[opal oriole]

Yea, not randomly my bad.

Still is the correct answer then, random was not a requirement.

[haughty mountain]

given it's a snake game, random is kinda implied

idk if there is a nice O(1) way to pick a random unoccupied space

just picking randomly until you find something unoccupied will work well until you have very few points left

[opal oriole]

The issue is the removing is O(n) from the list.

If you have a list of unoccupied cells you can pick a random index. But removing it requires O(n) shift.

You could do something like randomly pick from all cells and check if something is there (and repeat if there is something there) when the number of unoccupied cells > N, then when below the threshold you can keep track of the unoccupied cells and pick and remove O(n), but n is small so whatever.

(For large enough unoccupied N, the probability of re-picks is low enough)

(Average time is probably O(1) if the threshold is picked correctly, gotta do some math though)

[haughty mountain]

if you only continue until some fixed ratio r is unoccupied, you'll only do 1/r checks on average

[fiery cosmos]

hi all, reading the section on Bounding Summations. can someone pls explain:
bounding the terms
we can sometimes obtain a good upper bound on a series by bounding each term of the series, and it often suffices to use the largest term to bound the others. for example, a quick upper bound on the arithmetic series A.1 is:

[fervent saddle]

What about if the grid spaces have a reference to where they're positioned in the list of available spaces, and you move them around?

[half lotus]

At the start, put all unoccupied indices into a list in random order. Then just pop from the right in O(1) time?

I suppose that's not O(1) overall since you have to build the list.

[fervent saddle]

*O(1) while the game is playing

[opal oriole]

The building the list would not count, but what about when you need to add back to the unoccupied when the snake moves?

(each frame the snake adds one cell to unoccupied and removes one cell from occupied)

[half lotus]

I see, I didn't realise they need to be added back

[opal oriole]

(At the first frame it would be O(1), but i'm assuming this should be O(1) at every frame)

(Not including setup/init before the first frame is run)

[fervent saddle]

I'm thinking of something like:
The snake head moves into a space.
That space has a reference to where it's listed in the available spaces list.
In the available spaces list, the space the head entered is moved to a spot which is for occupied spaces, and it swaps positions with whatever space the tail left.

[agile sundial]

probably easiest with an example.
1 + 2 + 3 + 4 is obviously less than 4 + 4 + 4 + 4

[opal oriole]

The problem is that moving that cells from where the snake is moving is not random and if you always pop off the last element it would spawn the food at the tail of the snake each time.

(You could consider the player a random source and then it's technically random (but the player is not suppose to choose where the food is implicitly))

[fiery cosmos]

ok i didnt understand what they were trying to say with this but i suppose now i do after that example

[agile sundial]

it's just an easy upper bound

[fiery cosmos]

any idea whats going on here?

[agile sundial]

where's here

[fiery cosmos]

in general, for a series (summation), if we let a_max = max_1<=k,=n*a_k, then..

then "the technique of bounding each term..."

i just don't understand what they are claiming

or trying to say

[agile sundial]

it's just what we talked about earlier

if a_max is the max element in the series, then the sum is less than or equal to n * a_max

[fiery cosmos]

ok

[opal oriole]

So, O(1) no, but you could do some spatial partitioning.

[fervent saddle]

Alright

[rough lynx]

@tropic glacierhate to tag you, but I'm still curious if you have any alternative to what I wrote here that you said could be optimized

def consecutive_decrease(ratings):
    combinations = [i for i in ratings]

    for i in range(len(ratings)):
        prev = ratings[i]
        bins = [prev]
        for j in ratings[i+1:]:
            if prev > j:
                bins.append(j)
                combinations.append(bins)
                bins = [k for k in bins]
                # could alternatively do this
                # bins = bins.copy()
            else:
                bins = []
                break
            prev = j
    return combinations

print(consecutive_decrease([3, 2, 1, 3]))

And to point it out again, I was given only 30 minutes to write and test the question that was given

[haughty mountain]

yeah, spacial partitioning like a quadtree can do the operations in O(log n)

[crimson steeple]

how to learn dsa

from C -> python

[tacit halo]

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

this simple enough?

!e

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

[halcyon plank]

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

[3]

[haughty mountain]

what is this even computing?

[tacit halo]

Prints out the elements that is not in nums2 that nums1 has

[signal knot]

So I can traverse a 2D matrix in O(n) time it seems. How am I supposed to figure out the math behind calculating the row and column for each iteration? Like how was I supposed to know i//n will give me the row?

def traverseMatrix(matrix):
    m = len(matrix)
    n = len(matrix[0])

    for i in range(m*n):
        row = i // n
        col = i % n
        print(matrix[row][col])

traverseMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]])```

[haughty mountain]

set(nums1) - set(nums2)?

if you don't care about order and duplicates

[haughty mountain]

I also think this code is broken, e.g. (if I executed stuff correctly in my head)

[1, 1, 2] [3, 1, 1] -> [1, 2]
```which makes no sense

[jovial kernel]

I'm looking for an algorithm, maybe a type of clustering algorithm, but I'm not really sure where to start. I have a list of entities and a list of the tasks they performed (1,000's of different tasks ids and includes duplicates if the entity did the task multiple times). I need to put the tasks into categories such that an entity that performed one of the tasks is likely capable of performing all the tasks in that category even if they don't have a history of having done that task.

[tacit halo]

That is true, the second list dosent have 1 and 2 elements

[fiery cosmos]

alright need help y'all

oh

the inductive step sets out to prove it holds for n/2, rather than what i've seen before in other examples e.g. (n+1)

hmm

still not getting why they don't set the base case equal to the right hand side of a new equation

what happens to the T after the second line in consider T(n) work

also not seeing where one of those (n/2) expressions comes from. for example the log of a quotient is equal to the difference of the logs. so when the lg(n/2) is broken out it should be lgn-lg2 no? not lgn-(n/2)lg2???

[opal oriole]

Already answered previously, but it's substitution.

[opal oriole]

(n/2)lg(n/2)
= (n/2)(lg(n/2))
= (n/2)(lg(n)-lg(2))
= (n/2)lg(n)-(n/2)lg(2)

[fiery cosmos]

i dont understand these final two lines here

[opal oriole]

https://www.khanacademy.org/math/4th-grade-foundations-engageny/4th-m3-engage-ny-foundations/4th-m3-te-foundations/a/distributive-property-explained

The second to last line is using log rules.

[fiery cosmos]

ooooh i finally see now thanks lol

the 4th grade thing really bummed me out 😢

i just saw that its simply distributing the (n/2) to both terms

[opal oriole]

https://www.khanacademy.org/math/cc-sixth-grade-math/cc-6th-expressions-and-variables/cc-6th-evaluating-expressions/a/terms-factors-and-coefficients-review

Actually this one seems better: https://www.cuemath.com/algebra/expression-term-factor-and-coefficient/

[fiery cosmos]

maybe i should go to the STEM helpers and students server and come here for algorithm specific things

what should it have been called

[opal oriole]

Whenever you see something like f(x) or (...) imagine it as one block, like how you would look at x.

[fiery cosmos]

the n/2 when i used the word expression

coefficient?

[opal oriole]

(n/2)x

[fiery cosmos]

factor?

[opal oriole]

It can be considered a coefficient or just a factor, depends on context, what you care about.

[fiery cosmos]

ok

[opal oriole]

Factor is correct though either way.

[fiery cosmos]

right bc its involved in multiplying two terms

[opal oriole]

Usually a coefficient is just a number.

[fiery cosmos]

coefficients have to be a factor * variable

[opal oriole]

But if you said that n was just set to something that does not change, it's the same thing.

[fiery cosmos]

but then do we consider lg(x) a variable? its not but it does vary..

like lg(x) would be but not lg(2)?

[opal oriole]

Like 3x, 3 can def. be called a coefficient.

(And a factor)

[fiery cosmos]

yeah thats the definition is a term multiplied by a variable

| Coefficients
| A coefficient is a number multiplied by a variable.

[opal oriole]

What matters more generally is terms and factors.

[fiery cosmos]

got it

i still dont understand how you know to substitute what where when it comes to substitution method for solving recurrences

[opal oriole]

You know how you can have something like f(x) = 10x + x, and then have x = 3 and replace all the x's with (3)?

[fiery cosmos]

sure

[opal oriole]

Well lets say you have f(x) = 10(x / 2) + (x / 2) and you have x / 2 = 3, you can still do substitution.

f(x) = 10(3) + (3).

You can replace entire blocks.

[fiery cosmos]

ok

[opal oriole]

And T(n/2) is treated as a single block. it's one thing.

So you can replace it.

[fiery cosmos]

could we go through this line by line

i'm happy to write it out in latex or similar

[opal oriole]

You have T(n) = 2T(floor(n/2)) + n.

You can replace T(floor(n/2)) as one block.

[fiery cosmos]

this is the recurrence i want to determine the upper bound on:

[opal oriole]

The reason you can replace (x/2) as one block in this is because you know what (x/2) is equal to.

So do you know what T(floor(n/2)) is equal to? (or in this case, less than or equal to)

[fiery cosmos]

we don't know what its equal to, we guess that the recurrence can be upper bounded by the expression T(n) = O(nlgn)

the substitution method requires that we prove T(n) <= cnlgn given our guessed soltn

and given the formal definition of big O

we begin by assuming our solution bound hold for all positive m < n, in particular for m = floor(n/2)

so floor(n/2) is the equivalent of what i've seen previously written as n+1 case (the inductive proof step)

therefore we get T(floor(n/2)) <= c*floor(n/2)*lg(floor(n/2))

which is the expression before any substitution into the recurrence

now i just have to combine the two red lines to create the green one

which is.. not intuitive.

[opal oriole]

What is the problem?

[fiery cosmos]

it just never clicks for me it looks like they built a new house out of some pieces of two older houses and picked at random

[opal oriole]

The original guess is for O(nlgn) is not random.

[fiery cosmos]

i wasn't even considering that i just don't see how they recombined them or how you would "know" to choose each piece

[opal oriole]

You know that your end goal is T(n) <= cnlgn. And you have T(n) = 2T(floor(n/2)) + n, so naturally you want to find something that lets you get from the start to the end. And the main thing in your way is this being a recurrence relation instead of what the end goal is, not a recurrence relation. To get rid of the recurrence-ness we need to get rid of the T(floor(n/2)) or in other words you need to substitute it with something.

[fiery cosmos]

so you substitute T(floor(n/2)) with c*n*lg(n)?

[opal oriole]

No, cnlgn is the end goal.

After substitution we hope to find a way to the end goal.

[fiery cosmos]

so you substitute m < n where m = floor(n/2)?

so we're essentially trying to get rid of the T() function on the right hand side?

[opal oriole]

We choose m = floor(n/2) because it ends up given us something to substitute T(floor(n/2)) with.

[opal oriole]

Yes, but more importantly get to the end goal, and that is the main obstacle in getting there.

[fiery cosmos]

so that would make sense if we were simply subbing m = floor(n/2) in for T(something). however, we first substitute floor(n/2) into the expression cnlgn, then sub into the T(n) equation. i guess i don't understand that.

[opal oriole]

If you want to substitute T(floor(n/2)) you need to know what it's equal to (or in this case less than or equal to).

[fiery cosmos]

if we want to get a bound on T(n) = 2T(floor(n/2)) + n, wouldn't we have to take the entire equation into account? eg that + n that is there as well?

[opal oriole]

Yes and we do.

[fiery cosmos]

why do we not substitute in floor(n/2) for that n?

[opal oriole]

Why would we?

[fiery cosmos]

bc its part of the eq we're trying to solve by replacing other n's..

why wouldn't we?

[opal oriole]

We are not replacing n's. We are replacing T(floor(n/2))'s.

[fiery cosmos]

ah ok

so this is really all about doing away with the recurrence by inputting our guess on its upper bound of cnlgn

[opal oriole]

n is not a problem, T(floor(n/2)) being on the right side is, because it makes it a recurrence.

[fiery cosmos]

what does the floor notation mean?

[opal oriole]

Round down.

[fiery cosmos]

i've read it in the book several times

oh

its the same as floor division in python?

[opal oriole]

floor(3.1) = 3

No, because floor goes towards negative infinity, and integer division goes towards zero.

[fiery cosmos]

more generally what makes this a recurrence, bc we have functions on both sides of the eq? or because the same function T is on both sides?

[opal oriole]

For positive values basically the same.

(Also depends on programming language (floor and ceil do not))

[opal oriole]

It's because the function is equal to itself in some way (with some modifications).

[fiery cosmos]

right ok thank you

[opal oriole]

f(x) = f(x - 1) + 1

[fiery cosmos]

is a recurrence

[opal oriole]

Yea

[fiery cosmos]

ok

[opal oriole]

If I now say f(0) = 1 I can generate more values from that base case.

From the recurrence f(1) = f(1 - 1) + 1 = f(0) + 1 = 1 + 1 = 2, etc.

I can go from f(0) -> f(1) -> f(2) or backwards until I reach the base case.

[fiery cosmos]

yeah no you lost me. baby steps 🙂

[opal oriole]

Let's say that I have something like 1, 2, 3, 4, 5, ... I could say that this sequence starts at 1, and that the next value is the previous plus 1.

And you can write that idea with some math.

I could say that I have some function f(i) which gives me the ith value of that sequence.

I could then start defining it as something like ```
f(0) = 1
f(1) = 2
f(2) = 3
...

But what if I want it work for any i?

[fiery cosmos]

f(i) = i + 1

[opal oriole]

Yup that works but jumping a bit further than wanted.

Can you make a recurrence relation for this function?

I already wrote it in plain English.

[fiery cosmos]

f(i) = f(i-1)+2?

[opal oriole]

+1, not +2

[fiery cosmos]

f(i) = f(i)+1?

i had f(i-1) which is why i put +2

[opal oriole]

You still need the i-1

With just i you can see it's wrong because what happens if you subtract f(i) from both sides?

[fiery cosmos]

ah ok

[opal oriole]

The f(i-1) is the "previous" value.

[fiery cosmos]

sry i wasn't thinking f(i-1) referred to the previous number, i was evaluating is as f(

right right

[opal oriole]

So it reads as "current" value is "previous" plus 1.

[fiery cosmos]

yeah thats where i goofed up. it's just like if you want the previous value in an array from element with index j, you do return A[j-1]

[opal oriole]

But there is one more thing to cover, what happens if you want to compute f(0)?

[fiery cosmos]

it works does it not?

ooooh

no it yields -1 = 0

is this like a boundary condition? or the concept of it?

[opal oriole]

f(0) = f(-1) + 1

We don't know what f(-1) is.

It's not defined.

[fiery cosmos]

wdym

[opal oriole]

The sequence starts at index 0.

Negative index makes no sense.

[fiery cosmos]

ah ok

wait

you can totally do return(someindex-1)

in that sense it is "negative" from where you are starting

[opal oriole]

f(i) returns the ith element in the list, there is no -1th element in the list.

[fiery cosmos]

ok

[opal oriole]

To cover this hole of the recurrence, we need a special case for when i = 0 so that we don't try to do f(-1).

We can simply say that f(0) = 1, explicitly.

So when doing any i other than 0, we use the recurrence, which will work fine then.

f(0) = 1 is known as a base case.

So we have: ```
f(0) = 1
f(i) = f(i - 1) + 1

And from that we can get any value in the sequence.

[fiery cosmos]

lol this is where you just invent things to make the equations make sense

this is why math is a certain amount of BS to me

[opal oriole]

We are constructing f, so we get to choose anything we want, we just choose it such that it does what we want and does not break.

Want to create a function f that will give me any ith value in the sequence.

[fiery cosmos]

so what are these boundary conditions the book goes on about

[opal oriole]

That would derail a bit.

[fiery cosmos]

alright well im going to continue my reading

[opal oriole]

So when constructing f, you may notice that you have multiple options, you already constructed another f(i) = i + 1.

Both work, but which is more nice to use?

[fiery cosmos]

i don't see how they could ever produce the same output

[opal oriole]

1, 2, 3, 4, 5, 6, ...

Using f(i) = i + 1:
f(0) = 0 + 1 = 1
f(1) = 1 + 1 = 2
f(2) = 2 + 1 = 3
...
Using f(0) = 1 and f(i) = f(i - 1) + 1:
f(0) = 1
f(1) = f(0) + 1 = 1 + 1 = 2
f(2) = f(1) + 1 = 2 + 1 = 3
...

[fiery cosmos]

right i keep forgetting in this example we're returning values from an array A with index i

or rather just from that sequence which i suppose has inices