algos-and-data-structs

[regal spoke]

There is a really cool trick for that https://codeforces.com/blog/entry/53170

Turns out you can do it pretty easily at the cost of an extra log factor

To remove that log factor you need to use splay trees, which is quite complicated

[stiff quartz]

Thanks! What does HLD mean?

[regal spoke]

Heavy light decomposition

Think about it like this:
The preferred child of a node is the child that has the largest subtree

Edges between a node and it's preferred child is called heavy, and all other edges are called light

The heavy edges form "heavy paths"

[stiff quartz]

It says "the path from v to the last vertex in ASCENDING HEAVY path from v" so how do I get all ancestors

[regal spoke]

The cool insight is that if you walk up from a leaf to the root, then you have to switch heavy path atmost log(n) times

[stiff quartz]

ahh

so you'd do log(n) queries

[regal spoke]

Yes

[stiff quartz]

so qlognlogn instead of qlogn I assume for the query part

[regal spoke]

(log n)^2, ye

[stiff quartz]

I see

[regal spoke]

If you follow adamants blog

You'll just have one big segment tree

Some intervals in the segment tree correspond to intervals in a heavy path

There are also intervals that correspond to subtrees

So you kill two birds with one stone

[stiff quartz]

I see

That's definitely something I'll have to implement myself otherwise I'll just forget

A year ago I thought I had reached the end of new ideas when I first encountered dfs ... lol

[regal spoke]

Note that all you really need is the DFS prefix ordering created by dfsing into the child with the largest subtree first

[stiff quartz]

Yes as fiery said, the "real" Euler Tour is then only ever useful when you want to be able to "de-flatten" the array?

[regal spoke]

I don't think a full Euler tour is useful here

[stiff quartz]

Why "DFS prefix ordering", why "prefix"? Isn't it just "DFS order" (just curious if there's a subtlety)

[regal spoke]

There is however another related algorithm that uses the full Euler tour

[regal spoke]

Preorder means store the time you first reach a node

(meant preorder and not prefix)

[dense light]

uhh

hi

[stiff quartz]

ok, fair I guess

thanks!

[stiff quartz]

I'm probably not ready for that yet

Maybe in six months 😄

[regal spoke]

Have you heard of moos algorithm?

[stiff quartz]

I have not

[regal spoke]

It is a more brute force alternative to segment tree

Costing sqrt(n) instead of log(n)

[stiff quartz]

The only alternative to segment tree I know is RMSQ but you can't update with it

[regal spoke]

Moo's you can't do update with either

[stiff quartz]

sounds like it has no upside then 🤔

[regal spoke]

But you handle lots of tricky type of queries that a segment tree cant

A simple example is if you want to find the most common occurrence in an interval

[stiff quartz]

I see

https://cp-algorithms.com/data_structures/sqrt_decomposition.html#mos-algorithm I think I found it

[regal spoke]

Yes

I would say moo's algorithm is seen as very standard and relatively basic

[stiff quartz]

found the thing you were mentioning https://www.spoj.com/problems/FREQ2/

[stiff quartz]

thanks for the reference, will definitely look at it

[regal spoke]

I would start by implementing moo's with stupidly simple queries, like sum queries on ranges

Once you understand that, it is easy to extend to more general queries

[regal spoke]

https://codeforces.com/blog/entry/43230 here is what I was refering too

It is basically moos + (full) Euler tour

[raw zealot]

hello there

https://codeforces.com/contest/1997/problem/D solved with iterative bfs

there seems to be some problem with my recursive one

probably the way i am yielding cuz rest is same

the bootstrap is the pyrival one

oh wait

[stiff quartz]

is your function recursive?

it doesn't call itself

[raw zealot]

i messed up nvm

def solve(case = None):
    n = int(input())
    a = list(map(int, input().split()))
    p = list(map(int, input().split()))
    adj = CustomHashMap(defaultdict, lambda: [])
    for i, parent in enumerate(p):
        adj[parent-1].append(i+1)

    @cache
    def recur(vertex):
        if not adj[vertex]:
            return a[vertex]
        m = recur(min(adj[vertex], key = lambda x: recur(x)))
        if vertex == 0:
            return m + a[vertex]
        else:
            if a[vertex] >= m+1:
                return m
            else:
                return (m + a[vertex])//2
    
    print(recur(0))

need to bootstrap this

actually the weird part is that i am calling recursion as a key to get the smallest child lol

should be some better way

[regal spoke]

You'll have to manually add the cache to it if you want to memoize it

[raw zealot]

ah i figured

i saw the bootstrap function there was no caching

i am getting invalid syntax for yielding inside lambda 💀

[regal spoke]

Ye python doesn't allow that

[raw zealot]

sad

[regal spoke]

You probably should just learn iterative bfs

It usually very nice to use

And very fast too

[raw zealot]

alright

stack way works so guess i will stick with it only

recursion looks concise but comes with problems fr

[stiff quartz]

Is lazy propagation in segment trees worse when you do the segment tree the iterative way (instead of total/partial overlaps from top to bottom when querying you go from bottom to top)?

I feel like it is since whenever you go up and lazy[pos] != 0 you need to propagate down so you may end up doing log(n)**2 operations?

[regal spoke]

I did not mean to use a stack. The "nicest" way is BFS with a list

[raw zealot]

yeah thats what i meant, list is technically stack right

[regal spoke]

Stack is specifically if you add/remove from the "top" of the stack

That's not what I meant at all when I said BFS

A list can be used as a stack, but a stack is not what is used in a BFS

[raw zealot]

yeah we use a queue true

i exchanged

this works

def solve(case = None):
    adj = defaultdict(list)
    for i, parent in enumerate(p):
        adj[parent-1].append(i+1)
    stack = [0]
    processed = {}
    visited = set()
    while stack:
        vertex = stack[-1]
        if vertex not in visited:
            visited.add(vertex)
            for child in adj[vertex]:
                stack.append(child)
        else:
            stack.pop()
            if not adj[vertex]:
                processed[vertex] = a[vertex]
            else:
                m = processed[min(adj[vertex], key =lambda x: processed[x])]
                if vertex == 0:
                    processed[vertex] = m + a[vertex]
                else:
           
                    if a[vertex] >= m:
                        processed[vertex] = m
                    else:
                        processed[vertex] = (m + a[vertex]) // 2
    print(processed[0])

wait this will be called a dfs right

idk i get confused

yeah both works i think because either way i am getting the childrens for the vertex

[regal spoke]

https://codeforces.com/contest/1997/submission/273911833 Here is the solution that I was talking about

I am a big fan of exploring a tree like this

bfs = [root]
for u in bfs:
    for v in graph[u]:
        graph[v].remove(u)
    bfs += graph[u]

Once the bfs order is computed, the problem is easily solved

for u in bfs[::-1]:
    if not graph[u]:
        continue
    val = min(A[v] for v in graph[u])
    if u != root:
        # Maximize smallest value in u's subtree (including u)
        A[u] = min(val, (val + A[u])//2)
    else:
        # Maximize the value of the root
        A[u] += val
print(A[root])

[bronze shale]

Hey guys, I'm doing a research project utilizing Python and a certain library and I'm seeking help since I'm getting some errors. Is there any1 here who can help since I'm getting errors in the main method such as numpy and I'm lost on how to fix it. Also pls DM

[regal spoke]

The style for how lazy segment tree are coded is very different between iterative and recursive.

The time complexity should be log(n) either way

Check out the _build and _update functions here https://github.com/cheran-senthil/PyRival/blob/master/pyrival/data_structures/LazySegmentTree.py#L41-L59 for the iterative version

There are two types of propagation. When you update the segment tree, then the ancestors need to learn of the update, which is taken care by _build

When you do a query, you first need to push down any prior lazily stored updates, which is done by _update

Both _update and _build clearly run in log time

[raw zealot]

is it okay to use list.remove , and also is bfs += thing O(1)

[regal spoke]

A += B takes O(len(B)) time

[raw zealot]

infact a new list is created

yeah

oh

[regal spoke]

No new list is created if you do +=

[raw zealot]

okay iadd moment

damn

[regal spoke]

About the .removes. In total they will take O(n) time.

The reason for this is that in graph[v].remove(u), u is the parent of v

So graph[v].remove will only run once for each v

[stiff quartz]

Ah I see, so first you go up the ancestors and push down everything that could've been in lazy and THEN you go up so that's 2*log(n) so O(logn)

damn that's smart

[tight cedar]

How do you actually use those premade data structures

do you just copy paste it into the python file submitted

[regal spoke]

Most websites require you to only submit 1 source file, so copy paste is the most common

[haughty mountain]

I'm half tempted to see how feasible using #includes in python is

i.e. run the c preprocessor before running/submitting code

[stiff quartz]

🤔

[haughty mountain]

it's a dumb idea

but technically would work

[north nebula]

Hey all
This might not be the right channel, but I hope it is
I have some data that comes in a format semi to HTML b, i, u tags
So something like:
{b}{i}test{/i} me {u}now{/u}{/b}
what libraries are available to detect all the ranges and the applied "formatting" on them?
ex: range 0-3: b, i
range 4-7: b
range: 8-11: b, u

[lilac cradle]

if it's actually html, there's a module in stdlib for it (html.parser)
otherwise you could probably do it with re or something like shlex (i have no clue how shlex works though, so that's just a guess)

[haughty mountain]

wouldn't be hard to write a parser for this

[young totem]

<@&831776746206265384>

[rigid steeple]

!cban 1240591183076392980 Seems like you're only here to advertise/recruit

[halcyon plank]

:incoming_envelope: :ok_hand: applied ban to @distant lance permanently.

[outer rain]

it's a perfectly reasonable idea, with the exception of that you will need to try hard to get the good ide support

perhaps a better way would be to inline from <module> import * imports

(which is almost #include)

I have such preprocessor for C++ #includes (a custom one, I can't use GNU because I don't want c++ std in my submission) and for Rust use

[outer rain]

the C++ one is actually even better, because I have two versions of each "library" I use: the one I have for debug, and the one I actually submit

so for instance the library for debugging will have ostream &operator<<(ostream &, const vector<T> &) implementation which will print vector in [1, 2, 3] format, and the submitted code will print it as 1 2 3 .

another example is dbg macro which in debug is something like #define dbg(o) ({auto x = (o); cout << #o << " = " << x; x}), and in submitted code it's #define dbg(o) (o). Fancy

[burnt charm]

I got this interesting problem where I have dictionary where keys are sequences of arbitrary but similar and values are integers representing scores.

Since the sequences are highly redundant I would like to remove sequences that are too similar to any other sequence in the dictionary and then only keep the one with the highest score.

Anybody know of an algorithm that can accomplish this efficiently?

[meager jetty]

Maybe you need this for List ```
def vRotateRight(v,n=1):
n = n%len(v)
a = v[-n:] + v[:-n]
return a

b = [0,1,2,3,4,5]
aa = vRotateRight(b)
print(aa)

Can be more generic for right or left ...

[lilac cradle]

is there a simpler way to make a triangle wave than offsetting and taking the absolute value of a sawtooth wave?

[lilac cradle]

collections.deque has this by default

[haughty mountain]

does that work?

oh yeah, it does

it's probably one of the easiest way to make it, yeah

[meager jetty]

y(x) = mx+b from i to j, going up and the other line another going down.

[lilac cradle]

kinda hard to vectorize that

i got a pretty simple equation for it though, just by messing around with the math

for a point on the triangle wave n and a frequency f you can do abs( (n * f) % 1 - 0.5 ) * 2
from there it should be pretty obvious how to vectorize that

my original function for it was this:

def tri(n,f):
    f2 = f/2
    return abs((n%f)-f2)/f2

which works but it's a lot more complicated

since it needs the division to keep the amplitude from increasing as the frequency does

[lilac cradle]

hm
now that i think of it, the real thing i'd like to do is an efficient square wave
how im doing it as of rn is i get the sign of a sine wave (and shift it up/down for duty) but that means its not linear
lemme try triangle or saw

[haughty mountain]

sign of shifted sawtooth?

[lilac cradle]

yeah

it works well actually

[lilac cradle]

#ot0-psvm’s-eternal-disapproval message

[crimson timber]

what does it refer to as finite memory?

I thought the memory of the turing machine was the tape

[agile sundial]

it's probably just presenting a variant where you can consider multiple bits to be under the "head" at once. it doesn't change how powerful it is, only makes it easier to express things

[crimson timber]

this is the definition we use

[crimson timber]

the internal states?

[agile sundial]

no. conceptually a turing machine is a long tape with a "head" that reads the tape, right? i'm guessing they're just saying the head can read multiple bits at once

[crimson timber]

How reading multiple bits at once is memeory

[outer rain]

The memory of the Turing machine is a tape and its state. And the state is an element of a finite set Q. So the state has finite memory of log |Q| bits

[outer rain]

To be fair, this phrasing is a bit unusual and confusing tbf, especially considering that you are probably unfamiliar with the details of how TMs work and don't have an intuition for what state is.

What it trying to say is, perhaps, TM consists of the head - the smart part of TM which encodes all the logic in the transition function, it's the thing that does all the cool stuff, but it is limited, because it's only got |Q| states, and it's incapable of doing actual logic on its own; and the tape - the dumb part, which only stores data, but also infinite. Tape is used by the head (or the processing unit) to actually make it useful, and have the whole system both have unlimited computational capacity and memory.

[crimson timber]

yeah I don't know what a state is

I thought it was making an analogy for computer where its got RAM for memory and SSD for storage

[haughty mountain]

state there means something like where in the program you are

really, what you define is a state machine

like, if I am in state A and see a 0 on the tape I jump to state B, if I see a 1 I jump to state C

(possibly modify the value on the tape, possibly move the head left/right, and then jump to a new state)

[crimson timber]

ik that you can transition from one state to another
but what exactly is q0, q1, q2 that usually define as the states

[crimson timber]

I think i kinda get what you mean here

[haughty mountain]

here is a simple state machine (one that doesn't write, which is kinda boring)

A
if 0: move head right, jump to A
if 1: move head right, jump to B

B
if 0: move head right, jump to A
if 1: move head right, jump to C

C
if 0: move head right, jump to A
if 1: move head right, jump to F

F: terminate

A, B, C, F are the states

F is a final state

the transitions would really be defined by δ

[crimson timber]

Is the label itself the state?

Also wouldn't say a finite-state automota is boring

nvm FSA don't have head

[haughty mountain]

well, compared to a full turing machine it's a bit simple 😛

[haughty mountain]

kinda, I compared it to "where I am in the program" before

you just need some way of knowing what your next instructions are

labels for nodes in a state machine is one way of encoding that

[crimson timber]

ah i think i understands bit more about states now. thanks for explaining it

I wonder how @outer rain was able to quantify set of states into log |Q| bits

state seems to be abstract thing for me

its prob possible to quantify states
as you need to encode states in a string somehow

for universal turing machine

[agile sundial]

you need log n bits to represent a number n

[crimson timber]

oh yeah huffman encoding?

[outer rain]

it's just the amount of information head has. If something can be in X different states, it contains log |X| bits of information by definition. I mentioned it because there is really no difference between, say, having 8 bits of memory, and having a single memory cell which can be in 256 different states. Sometimes the first way of dealing with information is moreintuitive, and sometimes the second.

[agile sundial]

no.. just representing a number in binary

[outer rain]

from theoretical standpoint, my 2TB hard drive can be considered both a 16 trillions memory cells, each can be 0 or 1, or a single memory cell which can be in one of 2^(16e12) states

the same way TM head can be in |Q| states, or you can think of it as a small memory unit with log |Q| bits

if you consider the modern computer an implementation of a turing machine, then CPU and it's registers is a head (so if your CPU has 19 registers 32-bit registers, it has 2^(19*32) states), and it's RAM is a tape (which can so much space compared to the CPU, it might as well be considered infinite)

ofc, it's a rough approximation, but hopefully it gives you an intuition, I shouldn't have mentioned information theory concepts really 😅

[crimson timber]

very interesting how you can think memory as just set of states
i think i got intuition for it

thanks for your clarification!

[neon jetty]

why do we need to convert to string for outputting all the elements in a linked list

why not just output them without converting to str

[haughty mountain]

you don't

[neon jetty]

yeah, it seems like unnecessary operation, I am giving my CS A levels next year and they put this code in the answer sheet on one of the past papers so I was confused about the str()

[regal spoke]

I could see a couple of reasons.

Some print functions (like stdout.write) require you to explicitly convert to string before calling the function.

[neon jetty]

so they were just trying to make it universal for all languages? in that case, I should be fine with not using it, right?

[regal spoke]

Another possible reason is that if the students dont know Python well, it might be a good idea to be very explicit in the code.

Clearly any print function should be ok with a string as input

[regal spoke]

It is 100% ok to not have the str call

I'm just saying that having the str call might not be that bad of an idea

[neon jetty]

yep, its a good habit to induce among beginners, I get you

[regal spoke]

I know of a really good example of unnecessary code that can be really helpful

def f(x):
  if x > 5:
    return 0
  if x < 0:
    return 1

def g(x):
  if x > 5:
    return 0
  if x < 0:
    return 1
  return None

These two functions are identical

[neon jetty]

is None never outputted?

what if x = 0 or 1 or 2 or 3 or 4

[regal spoke]

In python, functions without a return value returns None

That's why both f and g are the same

[regal spoke]

Both f and g would return None

[neon jetty]

I see

then why is the second function more helpful?

[regal spoke]

The line return None is completely unnecessary

[neon jetty]

yes

but you said that its really helpful

[stiff quartz]

to communicate intent

[regal spoke]

But unless you know Python well, you wouldn't know that

[neon jetty]

wb comments

[neon jetty]

true, I didnt know this either

[stiff quartz]

It's like if you went to C# or Java and said, I'm going to declare everything public, I'm not going to encapsulate anything, because I can use comments. Actually, maybe not the best comparison but comments are not always the best way to show intent imo

[regal spoke]

Sometimes being explicit / showing intent can be good, even if that means adding unnecessary code

(Longer) explicit variable names is another example of this

Technically completely unnecessary

But they can really help a reader understand the code

[haughty mountain]

it's pretty bad for teaching idiomatic python though

[neon jetty]

it's good for teaching beginners though

[haughty mountain]

the extra str? not really

[stiff quartz]

Could also be that the person that wrote that isn't a Python expert

[haughty mountain]

it's just causing confusion

[stiff quartz]

Most languages require you to cast to string before printing

[haughty mountain]

like in your case

[neon jetty]

I wouldnt use it, but wouldnt it help other students transition easier to other languages that requires str() for its output functions

[haughty mountain]

I wouldn't say that's a strong argument

[haughty mountain]

also, do they?

[haughty mountain]

this is the way more likely thing

[regal spoke]

I would guess this too

[stiff quartz]

For arrays, I don't know any languages that support print(array) but i mainly use Python and C# so idk

[regal spoke]

However, that also shows that print(str()) might not be that bad of an idea

Someone that doesn't know Python, still understands how it works

[neon jetty]

still, it does cause confusion for students like me

[stiff quartz]

Not really, you asked yourself, tried without it, found out it was the same and learned something out of it, it's not that bad

[neon jetty]

I look at it and think "isnt that just unnecessary, am I missing something"

[haughty mountain]

having it as the solution to an exam is very questionable

[stiff quartz]

Fair, fair

[neon jetty]

yeah because the teacher will compare it with my code which doesnt have str() call

[stiff quartz]

In that case it's just a guy who wrote the solution and that is not used to Pythonic syntax

[stiff quartz]

if the teacher marks it as wrong when your code doesn't have the str() call it's just a bad teacher

[regal spoke]

No sane person could ever fail someone for not using str before print. Not needing the str is a feature of print

[haughty mountain]

do those languages even allow you to turn arrays into strings? I know C++ doesn't have stuff for it

[stiff quartz]

C# doesn't

you have to iterate over the array

I mean you could modify the class I assume

to implement a .ToString()

[haughty mountain]

I would be tempted to do a deduction or at least a remark for using it

[stiff quartz]

I think the print in C# calls .ToString() when available

[haughty mountain]

so basically same as python

(other than repr as well)

[stiff quartz]

Yeah, it's just in Python all objects have the method by default (I think? since it prints the mem adress or something when you don't implement it?)

but other than that it's the same, you create / overload (python) the method if you want to do your pretty display

[haughty mountain]

to me it's just a sign of "you don't know what you're doing"

much like seeing stuff like

str(input())

[stiff quartz]

I mean, it's no breaking news - not all teaching assistants are expert of the language they grade you in

[haughty mountain]

it feels a bit like cargo cult programming

[regal spoke]

Sometimes I write code in an unnecessarily complicated way, just because I'm 100% sure that it will work

print(str(x)) is that type of code

[neon jetty]

https://media.discordapp.net/attachments/1237480037922504776/1270019233949941812/image.png?ex=66b22d15&is=66b0db95&hm=2763ce085aca88ee1031d44422910509c532a62cd1aa528f48bbd563eb68e9e4&=&format=webp&quality=lossless&width=972&height=554

those brackets there are also unnecessary

[stiff quartz]

Yes

[regal spoke]

Those brackets are horrible and should be removed

[stiff quartz]

The brackets on the line above are too

[neon jetty]

oh yeah

[haughty mountain]

so...yeah

[stiff quartz]

That really shouldn't be overwhelming though

And if it is, it's fine, but you'll get used to it

[haughty mountain]

also the naming is nicely inconsistent

and bad whitespace

[neon jetty]

how to add stuff in a linked list, I am having trouble understanding it

[haughty mountain]

and calling stuff "pointer"

when they really aren't

strikes me as someone who might know C better than python

[neon jetty]

they already terrorized us with the pointer datatype in pseudocode, thats why

[neon jetty]

could someone explain the logic over here

my brain is not brain-ing

[haughty mountain]

is this storing linked list nodes in a list? 🥴

[regal spoke]

Yes

[haughty mountain]

like...you can do that

[neon jetty]

adding

[haughty mountain]

but I probably wouldn't teach that

[regal spoke]

How much object oriented programming do you know in Python?

[stiff quartz]

don't look at the while statement @regal spoke

[regal spoke]

:

[neon jetty]

I do understand how classes and objects work

I also know what methods and attributes are

[regal spoke]

The linked list you have there is essentially not implemented using object oriented programming

With everything stored in a python list

[stiff quartz]

I think it's faster than using a class (in Python) actually i'm not sure why they teach it like this it's confusing

[neon jetty]

that makes sense because object oriented programming is in chapter 20 and this is in chapter 19

[haughty mountain]

wat

if emptyList<0 or emptyList>9:

[neon jetty]

checking if the linked list is full or not

[haughty mountain]

if you want to teach a linked list to people, teach the typical linked list

[haughty mountain]

the name is just really weird

[neon jetty]

yeah when I search linked list on youtube I get the typical one and I cannot relate it to what Im being taught so that just confused me further

[haughty mountain]

because of course emptyList is an int and not an empty list

[regal spoke]

Obviously emptyList is the number of elements in the linked list

[neon jetty]

that is why I am having trouble understanding this code

[neon jetty]

@regal spoke but here the value of emptyList is 5

[stiff quartz]

so instead of a linked list having in its attribute nextNode another linked list

[neon jetty]

which means I think its referring to the index 5

[stiff quartz]

it has an index

[haughty mountain]

int(dataToAdd) for spice

[stiff quartz]

where, in the master list, the next node is

[neon jetty]

that is atrocious

int(input()) supremacy

[stiff quartz]

this is why the new node has -1 because there is no new node (yet)

[neon jetty]

I dont get it

[haughty mountain]

oh fun, it really treats that list as you would treat an array in C

[stiff quartz]

I don't think the code is complete though

[neon jetty]

why not

[regal spoke]

Teaching object oriented programming using c 😩

[stiff quartz]

nextNode is never modified

[haughty mountain]

the new node points to -1 because it's at the end

[haughty mountain]

oop in c in python

[stiff quartz]

but the penultimate node should point to the emptyList integer

[neon jetty]

that one is from a youtube video, I will pull up the ans sheet

same thing, right?

[haughty mountain]

oh yeah, the code is broken

[stiff quartz]

no there are two extra lines

not the same thing

(after the while statement)

[haughty mountain]

yeah, there the next pointer of the previous last element is assigned

[neon jetty]

I see it

[stiff quartz]

So basically

You have an array
[a_node, another_node, another_another_node, empty, empty, ...]

and in a_node you have a .nextNode

Instead of directly being another node
It is an integer
That integer represents the position in the list where that other node is

[haughty mountain]

the last assignment does nothing though 🥴

[neon jetty]

which one

[stiff quartz]

emptyList =

emptyList is a local variable that will get discarded when you return True

[neon jetty]

doesnt it assign it to its next index

[stiff quartz]

emptyList is a local variable

It will disappear

[neon jetty]

at the beginning they made us write emptyList out of the function

when we were making the linkedList

[stiff quartz]

!e

a = 4
def f():
  a = 5
f()
print(a)

[halcyon plank]

:white_check_mark: Your 3.12 eval job has completed with return code 0.

4

[stiff quartz]

Do you understand why 4 is printed and not 5

the a in the function f is not the same as the a outside f

The teacher should absolutely not call these two variables the same

[neon jetty]

yeah because we didnt put global a

[stiff quartz]

So in your example

did we put global emptyList

Also, I would highly suggest not to watch this youtube video anymore if not necessary for your exams and if you're just doing it to learn linked lists

[neon jetty]

no, that one is the answer sheet

that one shouldnt be wrong but

[stiff quartz]

do you undersatnd why fiery said emptyList = is useless then

[neon jetty]

is this better

[stiff quartz]

this looks horrendous

[neon jetty]

it was in the teacher's powerpoint slide

[stiff quartz]

Doesn't prevent it from being horrendous

[neon jetty]

no, just confirming that I didnt write it myself

[regal spoke]

Just so you know, that code is not typically what someone means if they say linked list in Python.

[neon jetty]

I do know that but if thats what is in my syllabus, I have to learn it this way

[stiff quartz]

Look at your linkedList here

It will be easy to understand

[neon jetty]

I understand this fully

[stiff quartz]

ah ok

[neon jetty]

just want to understand the addnode function

[regal spoke]

I still would seriously consider changing the name of emptyList.

[neon jetty]

that shouldnt be an issue, yeah

[regal spoke]

Btw that while loop could be made considerably easier by checking if nextNode==-1. Then you would need currentPoiner and previousPointer

[haughty mountain]

this is not how you would implement a linked list in something like C either

it's just kinda...bad and confusing

there are rare cases where you might want a linked list backed by an array or whatever, but it shouldn't be the first thing to teach

using -1 as a magic value also irks me

[regal spoke]

There is also the weird thing that happens if currentPointer starts with -1

[haughty mountain]

there is this one special value to represent the lack of a value

None

[regal spoke]

Not in C there aint

[haughty mountain]

there you would use actual pointers and NULL 🙃

[opal oriole]

This is pretty normal in C. Indices are just relative pointers, and you need some NULL value :)

[haughty mountain]

I would be surprised to see a -1 in a linked list in C

as the pointer to next element

[opal oriole]

Usually just actual pointers, but sometimes if it's backed by an array. Although even when backed by an array (a memory arena), it's still just pointers.

What is even better than raw pointers / indices in C is handles. Which you can think of as opaque pointers, and those could be a regular pointer or index under the hood, the user does not need to know and the implementation can now be swapped out (backed by array, heap, etc).

You can also force null checks on handles, avoiding the classic null ptr dererfence problem.

Makes things more memory safe.

[haughty mountain]

I wouldn't teach an arena allocated linked list as someone's first linked list 🥴

[opal oriole]

Heap is more convenient since malloc is built in.

But it's the beginner method, not really how you usually want it in a real project.

(memory management nightmare)

(also worse performance often)

(anyhow this is getting off topic into C interface design quirks and problems)

(Python is ref counted so it covers up any issues)

[haughty mountain]

the conclusion is still that the code discussed is pretty awful 🙃

[neon jetty]

I actually did not understand that part of the code at all, what is it trying to do

[regal spoke]

It creates a new node, stores it at index emptyList

Then it starts traversing the Linked List, starting from the node at index currentPointer

Once it reaches the end of the linked list, it adds a link to the new node

Increasing the length of the linked list by 1

[regal spoke]

what is it trying to do
It extends the linked list by adding one more node to the end of the linked list

[neon jetty]

but the end of the linked list is not the only one where the nextNode value is -1

https://cdn.discordapp.com/attachments/650401909852864553/1270054291234750607/image.png?ex=66b2f67b&is=66b1a4fb&hm=a298b7a75086d58ab363c509e38e5628fab2b84aaabfd922a6d59e22a7333ee1&

wont it stop at index 3 then

[regal spoke]

Yes, so at the end of addNode(0), it will set linkedList[3].nextNode = 5

This extends the chain by one more node

[neon jetty]

when we are calling addNode(0) what do we mean by the 0?

[regal spoke]

Before calling addNode(0), the linked list looks like this

Index data nextNode
0     1    1
1     5    4
2     6    7
3     7    -1
4     2    2
5     0    6
6     0    8
7     56   3
8     0    9
9     0    -1

After calling addNode(0), the linked list looks like this

Index data nextNode
0     1    1
1     5    4
2     6    7
3     7    5
4     2    2
5     x    -1
6     0    8
7     56   3
8     0    9
9     0    -1

(here x represents the data value that was inputted by the user)

[neon jetty]

will that parameter's value always be 0? indicating the start pointer?

[regal spoke]

Are you asking if startPointer always needs to be 0?

[neon jetty]

I am asking how a linked list functions when the startPointer is not 0

[regal spoke]

"Linked list" normally refers to a datastructure the elements appear in a chain
a -> b -> c -> d
From each node, you know how to get to the next one

[neon jetty]

yup

[regal spoke]

You need to set startPointer to be that a

[neon jetty]

so if i set the startPointer as 2, the elements in index 0 and 1 will cease to exist but the rest of the operations of a linked list will still work?

[regal spoke]

no

[neon jetty]

in that case, for this particular code, the startPointer always has to be 0

[regal spoke]

All these "pointers" simply point around in memory. Their exact values dont matter

[neon jetty]

you are right, I phrased it poorly, what I meant was, index 0 and 1 will no longer be part of the linked list, but the linked list will still work as before?

[regal spoke]

In theory you could have a linked list with pointers like this

2 -> 1 -> 3 -> 0 -> 9

Maybe the code you have will never be able to build a linked list like this

But fundamentally it could have any shape

[neon jetty]

it needs startPointer to be 0?

[regal spoke]

Fundamentally no.

Suppose you want to add a node to the start of the linked list

If the current start node is at index 0

Then the new start node cant have index 0 (since that is occupied)

[neon jetty]

ah, so the startPointer only determines the order in which the data is appended

[regal spoke]

It simply points to the start of the linked list

Probably it will start out as 0, but over time that can change

[neon jetty]

so there is two -1 there, the first one is indicating the last data added and the second one is indicating the end of the entire linked list

[regal spoke]

I honestly dont know why there are two -1 in there

My guess is that some rows just contain nonsense data that should be ignored

[neon jetty]

yeah Im trying to understand what cambridge wants me to learn

[neon jetty]

but when we are adding newNode, it will always have the nextNode value of -1

[regal spoke]

Thats true

[neon jetty]

why is it changing into 3?

[bold lichen]

Hello

[regal spoke]

I'd still guess that this is what is actually going on ^

[regal spoke]

Thats a typo, I meant to write 5 and not 3

Fixed it now

[neon jetty]

yep, that makes a lot more sense

so the first -1 will always be associated with the most recent appended data

[regal spoke]

The most recent added node will have a -1

If there are other -1s, then I would guess those rows should just be ignored

[neon jetty]

no I do not think there should be any more -1s except for 2

[regal spoke]

In theory, if a row is not being used, you could put anything in that row

[neon jetty]

yeah but Im learning this code, and here the user only inputs the value of the data, but not the value of nextNode, which will be -1 uptil another node is added

[neon jetty]

@regal spoke is emptyList the index with the next 0 value?

[regal spoke]

Honestly I have no clue exactly what emptyList is

I think it is supposed to be a pointer to an unused row

[neon jetty]

yup

but not just any unused row, its always pointing to the empty row next to the most recent value appended

[neon jetty]

I thought I could rename it to something else but it seems I have to keep it as it is because of the way the exam question is presented to me

they have specified this name in the question

[regal spoke]

I havent seen the code that computes the emptyList variable, so I don't know exactly what it is

[neon jetty]

https://media.discordapp.net/attachments/650401909852864553/1270056463477379176/image.png?ex=66b2f881&is=66b1a701&hm=db2a3662afe4383bb3f93c3d34092a406245c7ef5ae3ab68c29e41bdfb86f79b&=&format=webp&quality=lossless

[regal spoke]

Thats worthless

information

There emptyList is just a hardcoded constant

[neon jetty]

it was originally set to be 5 because the 5th index is next empty row

[regal spoke]

I'm starting to think thats not the case

[neon jetty]

I shouldve started with ordered linked list, the unordered version has so much chaos

[regal spoke]

We've been pretty clear that what you've got there is a messy version of a linked list

It looks like someone explaining a linked list in C using only the most basic operations

[neon jetty]

does the less messy version involve object oriented programming?

or does the pointers just point to the value of the next node instead of index

[regal spoke]

Yes. Infact the entire reason for teaching linked list is usually to teach object oriented programming.

Linked lists as a data structure are honestly almost completely useless in practice

[stiff quartz]

You could still point to next index in a list and do it more properly than they did

[neon jetty]

I am assuming I have to learn it in the next chapter and then compare

[hardy raft]

Hello everyone

[neon jetty]

I am not fully understanding what they did

or what they want to do

[stiff quartz]

my_list_of_linked_lists = [(0, 2), (1, 3), (4, 1), (5, -1), (-1, -1), (-1, -1)]
start_idx = 0
index_empty = 4

def add_node(my_list_of_linked_lists):
  if index_empty < 0 or index_empty > len(my_list_of_linked_lists):
    return
  new_value = int(input())
  curr_idx = start_idx
  while my_list_of_linked_lists[curr_idx].next != -1:
    curr_idx = my_list_of_linked_lists[curr_idx].next
  my_list_of_linked_lists[curr_idx].next = index_empty
  my_list_of_linked_lists[index_empty] = (new_value, -1)
  # Set index_empty to the next free location in my_list_of_linked_lists
  # ...
  return index_empty  # the new one

Something like this?

[neon jetty]

add_note 🤣

[stiff quartz]

Does that make more sense to you?

[neon jetty]

we also need to check if the linked list is full or not

since the size of it is pre-defined in the question

[regal spoke]

https://www.datacamp.com/tutorial/python-linked-lists Here is the standard explanation of a linked list (in Python). It even uses standard terminology like head.

[neon jetty]

https://cdn.discordapp.com/attachments/650401909852864553/1270055552977866884/image.png?ex=66b2f7a8&is=66b1a628&hm=f89845ebd1703c36337663ed50ca701eac38e79264b1327c84f5289aeb7022dd&

[neon jetty]

I am guessing that I have to globalise the linkedList ?

because it will disappear

[stiff quartz]

just pass it as an argument

[neon jetty]

yeah thats what my exam board prefers

for some reason

[stiff quartz]

global variables are rarely good practice

[neon jetty]

I see

[stiff quartz]

I updated the code, should be easier to understand? I'm not sure how they "find" the next free location though in their approach

[neon jetty]

yeah thats why i came here in the first place

[stiff quartz]

Your linked list will be 0 -> 4 -> 3 -> 5 before adding

and 0 -> 4 -> 3 -> 5 -> new_value after adding

(in my notation in the code above the first number is value and second number is index of next)

[neon jetty]

I think they find it because its always on the nextNode from the current emptyList

[regal spoke]

What I suspect is going on is that they in the problem description tells you which value to use for emptyList.

So you don't have to "find it"

[stiff quartz]

nextNode from a node that is not created is not defined

[neon jetty]

Index data nextNode
0     1    1
1     5    4
2     6    7
3     7    -1
4     2    2
5     0    6
6     0    8
7     56   3
8     0    9
9     0    -1

initially emptyList was 5

5's nextNode is 6

[stiff quartz]

It doesn't look empty

[neon jetty]

6's nextNode is 8

the data is empty

[stiff quartz]

it looks like there is already a node, whose value is 0 and next is 6, at position 5

[neon jetty]

they are treating it like the empty row apparently

cuz during addnode, thats where the data will go

[stiff quartz]

Ok that makes sense I guess, so they already forced the location the next will go to

[neon jetty]

yeah

[regal spoke]

It is weird that they've put junk data into the table

[neon jetty]

junk data?

[stiff quartz]

I think all rows without 0 as a value are used actually?

[neon jetty]

do you mean index 0,1,2,3,4 and 7? why are they junk data

[regal spoke]

These things in blue

[stiff quartz]

I think they predefined

[neon jetty]

those arent junk, they are the index to the next empty row

[stiff quartz]

That the node that will be sitting in position 5

[regal spoke]

They look like junk to me

[stiff quartz]

will have a next at position 6

[neon jetty]

from 5, the next empty row is at 6

from 6, the next empty row is at index 8

[regal spoke]

ohh what

WHYY

[stiff quartz]

(which is contrary to the whole linked list philosophy)

[neon jetty]

from 8, the next empty row is at index 9

[stiff quartz]

it is literally an array

[neon jetty]

IDK MAN

[regal spoke]

So the unused rows also form a linked list

[stiff quartz]

It's a long linked list with an "early stop"

for you to add the data at this "early stop"

[left mulch]

two linked lists for the price of one

[stiff quartz]

I think you learned enough, you shouldn't try to dig deeper

[neon jetty]

https://tenor.com/view/kronk-emperors-new-groove-its-all-coming-together-gif-12813012

[regal spoke]

This is smelling more and more like some C implementation of a linked list randomly found online

[stiff quartz]

@regal spoke even then you couldn't insert one linked list at the end of the other linked list actually maybe you could but that'd be mayhem

[neon jetty]

I actually dont have that in my syllabus, its just searching, insertion and deletion

theres also outputnodes which is not written in the syllabus but I have seen it in question paper

[regal spoke]

Now the variable name emptyList is starting to make more sense. It is the head of the "empty" linked list

[stiff quartz]

yes i think so too

[regal spoke]

Still an absolutely shitty naming scheme

[neon jetty]

should be named headPointer then

[stiff quartz]

head is usually fine

[regal spoke]

It isn't just any head.

[neon jetty]

its an empty head

[regal spoke]

So headPointer would be a bad name

[stiff quartz]

not empty head

head of the empty linked list where you're allowed to put stuff

head_of_the_empty_linked_list_coming_after_the_end_of_the_linked_list_you_currently_have

[neon jetty]

emptyPointer?

🗿

[stiff quartz]

Again, do not worry

and also, stop looking at this code

[neon jetty]

I need to study 😭

but I will try to improve it and still get the marks in exam

[stiff quartz]

Study other questions

of that same paper

Don't overanalyse that ill-asked/ill-answered one

[neon jetty]

but still only delays the thing that I have to learn eventually

[stiff quartz]

Is there still something that confuses you about that linked list?

[neon jetty]

how does it find the next empty index

I mean I know I explained it

[stiff quartz]

Index data nextNode
0     1    1
1     5    4
2     6    7
3     7    -1
4     2    2
5     0    6
6     0    8
7     56   3
8     0    9
9     0    -1

after your while statement

your previousPointer will be at index 3

[neon jetty]

because thats the first -1?

[stiff quartz]

yes

the first in order (indices) 0 1 4 2 7 3

do you agree?

[neon jetty]

and then 3's nextNode will be updated to 5

[stiff quartz]

yes

and empty list will look at index 5

who is next

[neon jetty]

yeah I get it 🛐

[stiff quartz]

they forgot that at index 5 they need to put -1

after getting who is next

otherwise you don't know where your linked list ends

[neon jetty]

they did put that actually

[stiff quartz]

Index data nextNode
0     1    1
1     5    4
2     6    7
3     7    5
4     2    2
5     x    -1
6     0    8
7     56   3
8     0    9
9     0    -1

well then

here you go

[stiff quartz]

this is a nice variable they happen to not use

newNode is not used

[neon jetty]

so if newNode is added to index 5, the -1 appears

[stiff quartz]

ah

my bad

it is

[neon jetty]

yeah

why brackets tho

is that needed

[stiff quartz]

no

no but there is a mistake still

if you put newNode directly

when you get the "Next"

you'll get -1

for empty list

[neon jetty]

ok but thats the 2nd -1

[stiff quartz]

you need to assign the new node AFTER retrieving where is next

[neon jetty]

not the first -1

[stiff quartz]

Take the example

Index data nextNode
0     1    1
1     5    4
2     6    7
3     7    -1
4     2    2
5     0    6
6     0    8
7     56   3
8     0    9
9     0    -1

[neon jetty]

oh

[stiff quartz]

if you do

you get

Index data nextNode
0     1    1
1     5    4
2     6    7
3     7    -1
4     2    2
5     x    -1
6     0    8
7     56   3
8     0    9
9     0    -1

how do you get 6 now

but that's ok

it's just the order of things that is wrong

as long as, conceptually, you get it, you will be able to implement it

[neon jetty]

emptyList just becomes -1 here

[stiff quartz]

yes

because they assigned linkedList[emptyList] to newNode too early

"losing" track of "6" before retrieving it

[neon jetty]

so we should put that line earlier?

[stiff quartz]

you should put the assignment later

or the retrieval earlier

up to you

[neon jetty]

that does seem stupid, how did they put that in the mark scheme

[stiff quartz]

Do you have classes in August??

[neon jetty]

are we missing something

[stiff quartz]

No definitely not

[neon jetty]

yeah

but linked list wont be taught for months, they havent even taught python basics yet

[stiff quartz]

I didn't know that was a thing

[neon jetty]

what?

[stiff quartz]

Classes in August

[neon jetty]

my AS ended in June, so got a decent summer break

still am on summer break technically

[stiff quartz]

Advanced Subsidiary?

[neon jetty]

yeah

[stiff quartz]

So you're from the UK? When I studied there, first week was in October

Maybe I'm getting old 😦 or maybe high school starts earlier than uni

[neon jetty]

no but my school follows cambridge curriculum which is in UK

[stiff quartz]

ah okok

[neon jetty]

@stiff quartz what does this mean?

[stiff quartz]

setting it to 6

in our example

[neon jetty]

yeah, they failed at doing that

[stiff quartz]

in addition to not coding properly

they don't know grammar

this is killing me

[neon jetty]

where?

[stiff quartz]

its

not it's

[neon jetty]

🤣

[neon jetty]

isnt 's suppose to show possession

[stiff quartz]

not in that case

here it means it is

do you say "this is he's car" or "this is his car"?

[neon jetty]

I dont think it's here means it is

[stiff quartz]

It really does

[neon jetty]

interesting

[neon jetty]

@stiff quartz is there a better way to write this?

just swapped it 🤣

nope, doesnt work, -1 doesnt get assigned to the nextNode of the last appended value

[stiff quartz]

What

What’s the problem

[stiff quartz]

Ah yeah no

[neon jetty]

-1 gets updated

[stiff quartz]

You had to put it at the end

Send me the code and the example

[neon jetty]

I wanted to avoid making a new temporary variable

but it seems like I dont have a choice?

[neon jetty]

I have updated it and introduced another variable to hold the value of emptylist before it disappears but I wanted to avoid introducing any new variables in the already messy code:

def AddNodes(linkedList, emptyList, currentPointer):
    data = int(input())
    if emptyList < 0 or emptyList > 9:
        return False
    else:
        newNode = node(int(data), -1)
        freelist = emptyList
        emptyList = linkedList[emptyList].nextNode
        linkedList[freelist] = newNode
        previousPointer = 0
        while currentPointer != -1:
            previousPointer = currentPointer
            currentPointer = linkedList[currentPointer].nextNode
        linkedList[previousPointer].nextNode = freelist
        print(emptyList)
        return True

[stiff quartz]

do you have the example as well

like the initial linked list etc

[neon jetty]

oh yeah

[stiff quartz]

wait you didn't send me that one

[neon jetty]

class Node:
    def __init__(data, nextNode):
        self.data = data
        self.nextNode = nextNode

linkedList = [node(1,1), node(5,4), node(6,7), node(7,-1), node(2,2), node(0,6),node(0,8),node(56,3),node(0,9),node(0,-1)]
emptyList = 5
startPointer = 0

[neon jetty]

I updated it, now it works, but I dont like what I have done to make it work

[stiff quartz]

no that's good

wait no

it doesn't work

[neon jetty]

huh? I tested it by printing the emptyList and outputed the nodes afterwards

should be correct

[stiff quartz]

yeah it works

so what don't you like

that you had to introduce a new variable?

[neon jetty]

yeah

[stiff quartz]

to avoid losing emptyList?

You probably have to

I wouldn't do it like this I guess

[neon jetty]

what happened here 💀

[stiff quartz]

emptyList is not global

so it's still 5

[neon jetty]

damn

[stiff quartz]

but nah that's pretty much it

you have to remember what's the next position is

before erasing the position emptyList

with (new_value, -1)

[neon jetty]

can you show me how you would do it

[stiff quartz]

linkedList = [
node(1,1),
node(5,4),
node(6,7), node(7,-1), node(2,2), node(0,6),node(0,8),node(56,8),node(0,9),node(0,-1)
]

this is wrong?

[neon jetty]

!e

    def __init__(self, data, nextNode):
        self.data = data
        self.nextNode = nextNode

linkedList = [node(1,1), node(5,4), node(6,7), node(7,-1), node(2,2), node(0,6),node(0,8),node(56,3),node(0,9),node(0,-1)]
emptyList = 5
startPointer = 0

def outputNodes(linkedList, startPointer):
    currentPointer = startPointer
    while currentPointer != -1:
        print(linkedList[currentPointer].data)
        currentPointer = linkedList[currentPointer].nextNode

def AddNodes(linkedList, emptyList, currentPointer):
    data = "x"
    if emptyList < 0 or emptyList > 9:
        return False
    else:
        newNode = node(int(data), -1)
        freelist = emptyList
        emptyList = linkedList[emptyList].nextNode
        linkedList[freelist] = newNode
        previousPointer = 0
        while currentPointer != -1:
            previousPointer = currentPointer
            currentPointer = linkedList[currentPointer].nextNode
        linkedList[previousPointer].nextNode = freelist
        print(emptyList)
        return True

AddNodes(linkedList, emptyList, startPointer)
outputNodes(linkedList, startPointer)

[halcyon plank]

:x: Your 3.12 eval job has completed with return code 1.

001 | Traceback (most recent call last):
002 |   File "/home/main.py", line 33, in <module>
003 |     AddNodes(linkedList, emptyList, startPointer)
004 |   File "/home/main.py", line 21, in AddNodes
005 |     newNode = node(int(data), -1)
006 |                    ^^^^^^^^^
007 | ValueError: invalid literal for int() with base 10: 'x'

[neon jetty]

the node has a capital letter

rename Node to node

[stiff quartz]

not but is it different?

that the table you gave us?

[neon jetty]

no

same

why? anything wrong with it?

[stiff quartz]

give me a sec

[neon jetty]

!e

    def __init__(self, data, nextNode):
        self.data = data
        self.nextNode = nextNode

linkedList = [node(1,1), node(5,4), node(6,7), node(7,-1), node(2,2), node(0,6),node(0,8),node(56,3),node(0,9),node(0,-1)]
emptyList = 5
startPointer = 0

def outputNodes(linkedList, startPointer):
    currentPointer = startPointer
    while currentPointer != -1:
        print(linkedList[currentPointer].data)
        currentPointer = linkedList[currentPointer].nextNode

def AddNodes(linkedList, emptyList, currentPointer):
    data = "x"
    if emptyList < 0 or emptyList > 9:
        return False
    else:
        newNode = node(data, -1)
        freelist = emptyList
        emptyList = linkedList[emptyList].nextNode
        linkedList[freelist] = newNode
        previousPointer = 0
        while currentPointer != -1:
            previousPointer = currentPointer
            currentPointer = linkedList[currentPointer].nextNode
        linkedList[previousPointer].nextNode = freelist
        print(emptyList)
        return True

AddNodes(linkedList, emptyList, startPointer)
outputNodes(linkedList, startPointer)

[halcyon plank]

:white_check_mark: Your 3.12 eval job has completed with return code 0.

001 | 6
002 | 1
003 | 5
004 | 2
005 | 6
006 | 56
007 | 7
008 | x

[stiff quartz]

linkedList = [
    node(1,1),  # 0
    node(5,4),  # 1
    node(6,7),  # 2
    node(7,-1),  # 3
    node(2,2),   # 4
    node(0,6),  # 5
    node(0,8),  # 6
    node(56,8),  # 7
    node(0,9),  # 8
    node(0,-1)  # 9
]

it is definitely wrong

[neon jetty]

wdym

[stiff quartz]

0 - > 1 -> 4 -> 2 -> 7 -> 8 -> 9

emptyList should be 9 not 5

[stiff quartz]

yeah there was a typo

in what you gave me

[neon jetty]

is it (56, 8)?

[stiff quartz]

no it is 56, 3

and you gave me 56,8

[neon jetty]

yeah thats the typo

[stiff quartz]

nevermind

!e

class node:
    def __init__(self, data, nextNode):
        self.data = data
        self.nextNode = nextNode

linkedList = [
    node(1,1),  # 0
    node(5,4),  # 1
    node(6,7),  # 2
    node(7,-1),  # 3
    node(2,2),   # 4
    node(0,6),  # 5
    node(0,8),  # 6
    node(56,3),  # 7
    node(0,9),  # 8
    node(0,-1)  # 9
]
emptyList = 5
startPointer = 0

def AddNodes(linkedList, emptyList, currentPointer):
    data = 69
    if emptyList < 0 or emptyList > 9:
        return False
    else:
        newNode = node(int(data), -1)
        nextEmptyList = linkedList[emptyList].nextNode
        linkedList[emptyList] = newNode
        previousPointer = 0
        while currentPointer != -1:
            previousPointer = currentPointer
            currentPointer = linkedList[currentPointer].nextNode
        linkedList[previousPointer].nextNode = emptyList
        print(emptyList)
        print(nextEmptyList)
        return True

print([(linkedList[i].data, linkedList[i].nextNode) for i in range(len(linkedList))])
AddNodes(linkedList, emptyList, startPointer)
print([(linkedList[i].data, linkedList[i].nextNode) for i in range(len(linkedList))])

[halcyon plank]

:white_check_mark: Your 3.12 eval job has completed with return code 0.

001 | [(1, 1), (5, 4), (6, 7), (7, -1), (2, 2), (0, 6), (0, 8), (56, 3), (0, 9), (0, -1)]
002 | 5
003 | 6
004 | [(1, 1), (5, 4), (6, 7), (7, 5), (2, 2), (69, -1), (0, 8), (56, 3), (0, 9), (0, -1)]

[stiff quartz]

That's how I would do it

does that make sense?

it's similar

also naming a class without a capital letter is kinda bad practice

[neon jetty]

I originally did Node but then thought its more comfortable to not press the shift key so many times when initialising linkedList

[stiff quartz]

yeah that doesn't matter don't worry

[neon jetty]

yeah same approach I guess, save the nextNode of emptyList before updating it

[stiff quartz]

yep

[neon jetty]

I want to globalise emptyList so it can be used more than once but the question is annoying

[stiff quartz]

you can

I mean otherwise there's no way

if they force you to return True and False

[neon jetty]

how about this approach

I am still taking emptyList as parameter as the question instructs me

but also globalising it

[stiff quartz]

i don't think they want you to get it as a parameter

they might be talking about startPointer only

[neon jetty]

its annoying

[stiff quartz]

ah lol

yeah

[delicate swallow]

how to start dsa in python + plz can anyone suggest a free cource (btw i live in india)

[ancient goblet]

https://jovian.ai/learn/data-structures-and-algorithms-in-python

[ancient goblet]

https://runestone.academy/ns/books/published/pythonds3/Introduction/WhyStudyAlgorithms.html

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

[neon jetty]

why is this printing -1

[outer rain]

because in one line it's nextnode and in the next one it's nextNode

I suggest learning to use the debugger to figure out mistakes like these quickly on your own

[neon jetty]

that fixed it, thanks

[neon jetty]

I was coding in shell just so I could see the outputs

[sonic fossil]

can anyone suggest any good book or channel to learn DSA from scratch

[half owl]

can someone how in the Diffie Hellman algo for secret key exchange, the 3rd party can't just eavsedrop easily? i mean it seems obvious

[haughty mountain]

they can eavesdrop, but do they get any useful information?

given g^x % p and g^y % p can you compute g^(x*y) % p easily?

(where g and p are known)

[half owl]

since g,p are known, and also g^x % p, g^y % p are known

and we know this identity holds true:

(a^b)^c mod d = (a^c)^b mod d

what's stopping the eavesdropper Eve from just picking an integer z to calculate g^z % p or something to make it equal the end-game private key?

im looking at this explanation as well

https://www.youtube.com/watch?v=YEBfamv-_do&t=144s

[haughty mountain]

what z?

[half owl]

just a number like x, y

i dont see how im wrong it just seems very obvious

[haughty mountain]

you would need to pick a very specific z

how do you figure out the z?

[half owl]

no problem

[swift breach]

you're not wrong here, it's not impossible.

[haughty mountain]

iirc that z needs to be x*y mod p, you don't know x and y

[swift breach]

There's actually been published research on this in 2015. The goal of DH isn't to be mathematically impossible, but computationally impossible

[half owl]

i know but i dont see how the discrete log makes it

[half owl]

yes, so whats the problem?

[swift breach]

Because it's 2 unknowns and a large enough number that computing it just isn't feasible, however, as published research has shown, bad choices here can cause it to be feasible to calculate: https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf

[haughty mountain]

it's possible, but not feasible because there are no good methods of recovering x from g^x mod p

[half owl]

once i find 2 integers such that z = k1 * k2 and it satisfies:
z = x / k1, z = y / k2

im done

which i know both
g^x % p, g^y % p

so i can get both x and y

[swift breach]

for what it's worth here, you're not strictly wrong mathematically, the security here is from picking parameters that make the computation of that take an impossibly long time

[half owl]

yes but i dont see how "discrete log" is a one-way function

[haughty mountain]

it's not

[half owl]

it was never explained neither in the video nor in the lecture

[haughty mountain]

wrong reply...

[haughty mountain]

it's not

it's just infeasibly hard to reverse

[half owl]

they call "one-way function"="not really feasible to reverse function"

[half owl]

yeah but why?

it seems straightforward enough

[swift breach]

your step of finding 2 integers that satisfy the parameters here is the expensive part, when g, p, x, and y are all chosen with safe values.

[half owl]

"abelian groups"? is all this needed?

[half owl]

i just dont see how it is expensive

i mean i wanna see why but i just dont know what calculations here are expensive

[swift breach]

I would suggest reading the paper I linked, it explains it better than I will both in how it can fail, and reccomendations for better.

[half owl]

i know exponention is about O(n^3) in python if im not mistaken (n being the amount of bits of the bigger number)

[swift breach]

RSA and DH are both things we should stop using though (which is a great topic for #cybersecurity )

[half owl]

does it explain why discrete log is exponential TC?

[half owl]

i havent yet read what RSA encryption is (it might have been removed from the syllabus so i'll need to look for resources later)

i do know it also uses prime numbers

group=set?

or do i have to wait for future math courses to understand this?

[devout hare]

take a course on abstract algebra / group theory

[half owl]

oh wait i do know what it is

[half owl]

yeah

[haughty mountain]

let's take a smallish example

In [2]: g = 5

In [3]: p = 10**9 + 7

In [4]: pow(g, x, p)
Out[4]: 382532690
```what is x?

[half owl]

r = g^x mod p, r,g,p are given

log_r(g mod p) = x?

did i miss something?

[left mulch]

what's the number?

[haughty mountain]

if we weren't working mod p computing it would be straightforward

[swift breach]

Well, for one thing, there's a whole group of solutions:
|| x = 1000000006 n + 12345678, for real valued integer solutions n>=0 ||

[half owl]

is there a closed formula?

like the one i tried to make

[swift breach]

but computing that for even numbers in the 10^9 size range takes a while

[haughty mountain]

yeah, this small example is solvable even with brute force methods 🙂

[half owl]

but would it compute?

and would my closed formula solve it?

regardless of speed

[haughty mountain]

regardless of speed, yeah you can solve it

but the speed is the issue

[half owl]

and this is the formula to compute x? or am i wrong?

[swift breach]

DH is safe* because we aren't assuming an adversary will wait till the heat death of the universe

* caveats apply due to number theory, you can pick really bad options and weaken this, as well as quantum computing

[half owl]

yes i saw this too

[haughty mountain]

"formula"

[half owl]

"quantum computing" is real?

[swift breach]

yes

[half owl]

yeah

[haughty mountain]

just testing x=1, x=2, x=3, ... until you get the answer will get you there

but it will take absolutely forever

for larger p

[half owl]

but why? what are the O(...) here?

[swift breach]

FWIW, at that scale, I didn't use a brute force method and it still took about 40seconds.

+-10 seconds for a remote running matlab to wake up and handle it

[haughty mountain]

for this naive thing Ω(p)

[half owl]

gg?

that sounds great

linear TC

well exponential in n bits

[haughty mountain]

p will be a huge prime

[half owl]

well

thanks everyone, i think i get it now

[naive oak]

when setting up your data structures for a problem, do yall prefer having like a list of lists or multiple separate lists, and why?
for example, say I'm doing painting subarrays offline as described here, and you're storing for each node its parent, rank, and next_node. Would you do something like

nodes = [[i, 0, i] for i in range(n)]

or

parents = [*range(n)]
ranks = [0] * n
next_nodes = [*range(n)]

or maybe even something else? my thoughts on the differences rn are
the first one would probably have better locality of reference
second one may be easier to convert if you had to swap something out for say a priority queue or smthing
but otherwise they seem mostly equivalent, but maybe I'm missing something

[vocal gorge]

You're describing array-of-structs vs struct-of-arrays, I believe.

The latter approach is often faster in compiled languages due to cache coherence (if you only access the parents, this approach lets you not load ranks and next_nodes at all) and hence is associated with "data-oriented programming" (though I only barely understand what that means), but this shouldn't matter in python.

[lean junco]

So, is there any well known maths/coding olympiad/contest for Masters student?
I saw some are there but I will not meet the age criterion as I will work 2 year professionally before MS and exceed the age limit by a year or so by the time I join.

excluding codeforce like competitions

[pseudo lynx]

let me hit you up with serious one

i will dm u

check dm

dont waste ur time on that one they sent it will waste ur time. i got the one that will make u be a master of it. check dm.

[lean walrus]

why didnt you send it here?

[pseudo lynx]

oh my bad

i will

https://youtube.com/playlist?list=PLKYEe2WisBTFEr6laH5bR2J19j7sl5O8R&si=U50roHcsWg2hCQHt

https://linktr.ee/greghogg

After solving DSA, I posted all I did and worked on it on GitHub with python solutions. https://github.com/salahudeenezz/Data-Structures-and-Algorithms-DSA-using-Python

first two is what you should look at fr not my at the last. first is the main one.

[pseudo lynx]

there you go brother.

[crimson timber]

anyone know if (a|b)* same as (a*|b*)

in the conext of regular expression

[lean walrus]

does 01 match (0|1)* ?
if so, then no
if not, then yes

[crimson timber]

yea 01 does match to (0|1)*

it should also match to (0*|1*)

L(0*|1*) = (L(0))* U (L(1))* = {_, 0, 00, ...} U {_, 1, 111, ...}

where _ denote empty string

same for (0|1)*
L((0|1)*) = (L(0) U L(1))* = {0,1}* = {0, 1, 00, 11, 01, 10 ... }

hol up (0|1)* does not include the empty string

still 01 is accepted by both regular expressions

i messed up 01 does not match (0*|1*)
cos {_, 0, 00, ...} U {_, 1, 111, ...} = {_, 0, 1, 00, 11, 000, 111 ...}

[lean walrus]

01 does not match (0*|1*)

[lean walrus]

it does

[crimson timber]

yeah, forgo power set include the empty string
L((0|1)*) = (L(0) U L(1))* = {0,1}* = {_, 0, 1, 00, 11, 01, 10 ... }

only If I do (a*|b*)* it would be equal to (a|b)* i reckon

[crimson timber]

nvm * not called the power set

I think its called the Kleene closure

[lean walrus]

i wonder why are you using rigorous definitions?

isnt it a lot easier to treat x* as "x repeated 0 or more times", x|y as "x or y" etc

x+ is "x repeated 1+ times"

[gusty oasis]

Hi everybody
Currently, our team is researching the leetcod solution every day and has posted it on the repo
https://github.com/software-engineer-learning/leetcode-algorithms
So if everyone is good, you can give our team a few stars
Thank you

[crimson timber]

that's a good way to think about it for * and +. for x|y i think of it as set union operator. i get confuse whether it's include both x and y when I think it as 'or'

and these are the rule im familiar with

[crimson timber]

ig it's cos it's the way i was taught

[last fulcrum]

Hi guys. Currently I suck at time complexity and I'm trying to improve. I have this code below and I think the time complexity is O(n^2).
My thinking is that there are two for loops, one where we go through every character in s and then other where go through s again to count how many times a character occurs.
If it's wrong then can someone please explain why it's wrong and what I can do to improve.

import string

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:

        if len(s) != len(t):
            return False

        for char in s:
            if s.count(char) != t.count(char):
                return False
        
        return True

[lean walrus]

this is O(n*(n+m)) where n is a length of s and m is a length of t
if they are of roughly the same length, then this is O(n^2)

[regal spoke]

The first if statment makes it so n = m

[lean walrus]

I see, I missed it

[regal spoke]

Nothing wrong with your code, but the time complexity can definitely be improved. One simple improvement is to do return sorted(s) == sorted(t)

[lean walrus]

it is O(1) if n!=m 🙂

[lean walrus]

return Counter(s) == Counter(t) would be even better (n vs nlogn)

[opal oriole]

If you want to make sure (check it yourself) count is O(n), here is the code: https://github.com/python/cpython/blob/2d9d3a9f5319ce3f850341d116b63cc51869df3a/Objects/listobject.c#L3210-L3243

You can see it's a for loop.

[last fulcrum]

So I was right in saying n squared?

[regal spoke]

O(n) time complexity and O(1) memory complexity

return sum(map(hash,s)) == sum(map(hash, t))

[regal spoke]

Yes your code is O(n^2)

[last fulcrum]

Yes that's true. I doubt in an interview you'll be allowed to do this though.

[lean walrus]

I like that ❤️

[regal spoke]

Depends on the goal of the interview. If they ask you for a simple solution, then return sorted(s) == sorted(t) is a really good answer

But if the task is to implment things from scratch, then using sorted is kind of cheating

That said, in that sense using .count is kind of cheating too

[last fulcrum]

Yea a hash map is the right goal for an interview. Also, I don't get your sum solution.

[opal oriole]

This relies on lack of collision no?

[regal spoke]

yes

[opal oriole]

So it might fail, so not really a valid answer unless you want really high speed and are ok with some fails.

[agile sundial]

the speed wouldn't even be that much better than a dict though, right?

[opal oriole]

It would probably be a lot better.

Actually hmm.

Depends on how long the strings are and such I think.

[lean walrus]

less memory allocations => better speed
that is my guess

and less memory hops in general, I feel

[opal oriole]

This is the real gain.

[regal spoke]

One issue with my sum of hash solution is big ints. You have to do things a little bit smarter to avoid "overflowing"

[regal spoke]

The probability of a failure is like 1 in 10^18

[opal oriole]

Yeah, if long enough you run into big ints, and memory becomes an issue again.

[regal spoke]

Not really. You can simply mod the sums.

[opal oriole]

Yes, there is this general class of algorithms where you can fail randomly but not often, but gain a lot of speed in exchange.

There is also an interesting case to those involving floating points, since you have limited precision anyhow and roundoff you end up with the exact correct answer as the non-random solution, but it's faster.

(Sprinkling in randomness and also lack of precision makes things fast)

[regal spoke]

There is one reason I like the sorted algorithm over using hashes. You never know when a hash function is implemented in some broken way, causing unexpected hash collisions.

So using sorted is more "stable"

[opal oriole]

Yeah, if you are using some library for the hashing, especially questions with how CPython is handling things.

[haughty mountain]

and then you mindlessly try to apply the same thing to sequences of int and things become sad

[regal spoke]

Indeed

[left mulch]

Why do things become sad with ints?

[haughty mountain]

the hash of an int is just that int

(except for -1)

so it would say [1, 5] is an anagram of [2, 4]

[left mulch]

I don't get it, why would it be an anagram?

[regal spoke]

Earlier I proposed this test (#algos-and-data-structs message) to check if s and t are anagrams

It works well for strings, since strings (this includes single letters) have randomized hashes in Python

But if s and t are lists of integers, it can easily fail.

[left mulch]

Mm, I see that I have to learn more about hashes before I start understanding this 🙂

[regal spoke]

It is just adding tons of random numbers. There is nothing fancy going on.

[last fulcrum]

There's an easier way to do O(n)

import string

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        
        if len(s) != len(t):
            return False
        
        letters = string.ascii_lowercase

        for letter in letters:

            if s.count(letter) != t.count(letter):
                return False

        return True

[regal spoke]

Thats technically O(n * alpha), where alpha is the alphabet size

[last fulcrum]

26 * O (n) is basically O (n)

[regal spoke]

By that argument O(n log n) is basically O(n), since in practice log_2(n) < 30

[last fulcrum]

The 26 is basically constant though. It will never change. So at the point it does not matter.

[regal spoke]

I see people hide that alpha factor as a O(1) from time to time. But in practice it is still noticable.

This is espeically problematic when this factor is hidden in the memory complexity

Programs taking 30 times more memory than expected can cause a lot of problems

[last fulcrum]

Ah. That's a solid argument.

[regal spoke]

I'd personally prefer using return sorted(s) == sorted(t) over this. The time complexity is about the same for smaller alphabets. But for larger alphabets the sorted version "wins".

[shut breach]

no, big-O has a formal definition
O(26n) is O(n), and O(nlogn) is not
that being said if you wanted to describe how it scaled with the size of the alphabet, O(alpha*n) would be the way to do that

[tight cedar]

In practice everything is constant time

[rose pollen]

Is this code wrong?

[regal spoke]

Yes and no.

Here is the extreme case. Suppose you have an algorithm that loops over all possible values of a 32 bit variable. In the past, I've seen people claim this kind of algorithm O(1) since 2^32 is a constant.

While the size of the alphabet is a lot smaller than 2^32, I would still say we are in the same kind of situation. I think it is wrong to sweep the alphabet size under the carpet.

A string algorithm that I'm a big fan of is the SA-IS algorithm (used for computing suffix arrays). The reason why it is so nice is because its time complexity is O(n + alpha), while many other similar algorithms out there are O(n * alpha).

[oak shuttle]

Yes mid should be divided by two

[rose pollen]

nope the return should be under else

[left mulch]

is that from grokking algorithms?

[rose pollen]

Yes

[left mulch]

you might be reading an older edition if there are mistakes like that

unless they just missed it in the newest edition too then rip

[left mulch]

oh yeah that print statement looks like it's from python 2 so that's probably an older edition

[clear glen]

hi

[clear glen]

what is it for?

[rose pollen]

can you send me link of newer version?

[left mulch]

Well, there's this preview from the publisher, I'm not sure if it's just the first chapter for free or the whole book
It also needs an online connection
https://livebook.manning.com/book/grokking-algorithms-second-edition/chapter-1/1
I don't know of other links

[shut breach]

no, they aren't
time complexity is a property of an algorithm, not the runtime of a program

[shut breach]

a program that takes no input and loops over all possible values of a 32-bit variable is O(1)
big-O describes the relationship between some chosen measure of input size and the number of operations the algorithm has to perform
it does not mean a program implementing that algorithm will take a short time to run

you could describe the time-complexity relative to the size of the alphabet or not, it depends on what you pick as your input size measure
presumably you would pick whichever is more useful to you

[outer rain]

uhm, akshually🤓 it's O(n + min(n, alpha)*log(min(n, alpha))) because you🤓need to first map the🤓alphabet to integers by sorting it otherwise🤓you would be able to🤓sort any🤓array of alpha elements in O(alpha)

[rose pollen]

Thanks

[outer rain]

Outside from "choose whatever is useful", this depends on a model too.

• In true RAM machine it's O(1), but there is no notion of X-bit variables anyway
• In word RAM it O(2^w) because one iterate for all values of word length
• In transdichotomous model (most useful of all, fight me) this problem is techinically not defined, because there is no input

I usually try to describe the problem in terms of a model where primary datastructure is an external oracle, so I would say that some algorithm is, say 6n of binary heap accesses, or 3n hash table accesses, or something like that. At least it's most descriptive. In case of SA-IS I'm pretty sure it's something like 24n indicrect 2-deep vector-memory accesses, or something close to that.

because constant matters

[regal spoke]

On this subject of ignoring things in big O expressions. There are some pretty decent arguments for why log factors should be ignored.

For example, take the Karatsuba algorithm, it famously has time complexity O(n^log_2(3)) = O(n^1.58496250072...).

In this case, you could hide an arbitrary number of log factors inside the big O expression. Since changing the expontent ever so slightly would "drown out" the log factors.

[outer rain]

ah yes, sorting in O(n^1.0000000000000000000001)

[outer rain]

that's such a cursed idea in math lol

O(1/(n * log n * log log n * log log log n * ...)) barely diverges on it's own, removing logs from here is bad

but ig it's ok for CS 🤔

still cursed

no, actually, it's bad

it kills the idea of theta

or ig if you ignore 1 + o(x^eps) term in theta it is ok too 🤔

goddammit I hate it..

I understand why would you want to do this for some algorithms, but