algos-and-data-structs

[old rover]

def remove (self, d):
        this_node = self.root
        while this_node is not None:
            if this_node.data == d:
                if this_node.prev_node is not None:
                    if this_node.next_node is not None: # delete a middle node
                        this_node.prev_node.next_node = this_node.next_node
                        this_node.next_node.prev_node = this_node.prev_node
                    else:   # delete last node
                        this_node.prev_node.next_node = None
                        self.last = this_node.prev_node
                else: # delete root node
                    self.root = this_node.next_node
                    this_node.next_node.prev_node = self.root
                self.size -= 1
                return True     # data removed
            else:
                this_node = this_node.next_node
        return False  # data not found

whoms't

this is ridiculously long code

just to delete a node?

[onyx root]

also, btw, why use d for data and n for node in the method arguments? That's bad.

[old rover]

not my code

I wanted to see if anyone did it more cleaner than real Python

def remove_node(self, target_node_data):
    if self.head is None:
        raise Exception("List is empty")

    if self.head.data == target_node_data:
        self.head = self.head.next
        return

    previous_node = self.head
    for node in self:
        if node.data == target_node_data:
            previous_node.next = node.next
            return
        previous_node = node

I still don't get why self.head = self.head.next this is necessary

[proper zenith]

yeah, that makes more sense than what i was doing haha, tysm

[onyx root]

What does this method do?

[old rover]

self.head is just the head of the linked list so the head takes the previous node's place?

I'd want to see it visually but visualgo is weird

[onyx root]

what should happen if remove_node needs to remove the first node in the list?

[spring jasper]

visualgo works fine for me

[onyx root]

@old rover in terms of seeing things visually, it might be best to do it yourself with pencil and paper.

[old rover]

it would remove it

if you called remove node on the linked list and gave it the head it would remove the head

<@&267629731250176001>

[wind idol]

good to know

take it away

[desert cedar]

!pban 706209023191547905 Asked to be banned, posted a video with a nitro scam.

[halcyon plank]

:ok_hand: applied purge ban to @elfin kettle permanently.

[old rover]

>>> llist = LinkedList(["a", "b", "c", "d", "e"])
>>> llist
a -> b -> c -> d -> e -> None

>>> llist.remove_node("a")
>>> llist
b -> c -> d -> e -> None

if you provided the head node as the node you want removed then it would get removed

all visualgo shows is just it disappearing

[spring jasper]

try and print(llist.head) after you remove it in the second example

[onyx root]

@old rover ok. How do you get rid of the first node in a linked list? What has to change?

[kindred sinew]

def delete_node (self,key):
    temp = self.head
    #if head itself is the key
    if (temp is not None):
        if (temp.data == key):
            self.head = temp.next
            temp = None
            return
    #searching the key
    while (temp is not None):
        if temp.data == key:
            break
        prev = temp
        temp = temp.next
    #Key not found
    if temp==None:
        return

    prev.next = temp.next
    temp = None

[old rover]

Traceback (most recent call last):
File "main.py", line 76, in <module>
llist = LinkedList(["1","2","3"])
TypeError: init() takes 1 positional argument but 2 were given

[onyx root]

what code are you running? Did you see my question?

[kindred sinew]

llist = LinkedList()

[kindred sinew]

and then create a method in class itself to insert the nodes

[onyx root]

What code are you referring to here?

[old rover]

!pastebin

[halcyon plank]

Pasting large amounts of code

If your code is too long to fit in a codeblock in discord, you can paste your code here:
https://paste.pydis.com/

After pasting your code, save it by clicking the floppy disk icon in the top right, or by typing ctrl + S. After doing that, the URL should change. Copy the URL and post it here so others can see it.

[old rover]

https://paste.pythondiscord.com/icenufaqel.rb

this is the code that gave me the error

[spring jasper]

it was working just a minute ago, why did you change the init

[kindred sinew]

class Linkedlist:
    def __init__(self):
        self.head = None

    def insert_end(self,data):
        #func to insert new node at the end
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        temp = self.head
        while temp.next:
            temp = temp.next
        temp.next = new_node

something like this

[onyx root]

@old rover you need to stop looking at more and more resources.

[kindred sinew]

sorry for misleading

[onyx root]

i don't mean to be harsh, but spinning between different implementations isn't helping you understand.

[kindred sinew]

That is True

[old rover]

ok

so how do I fix my error

[spring jasper]

your __init__ needs to accept other params

and then you gotta insert from that list into nodes, and link them together

[onyx root]

I thought we were talking about self.head = self.head.next

[old rover]

that makes the head the next node (I think)

[onyx root]

@old rover yes, do you see why you want to do that?

[old rover]

so that the previous node becomes the new head?

[onyx root]

I'm not sure what you mean by "previous node"?

[old rover]

previous_node = self.head I was going off this

[onyx root]

That sounds like "so the previous node becomes the new head" means, "so self.head becomes the new head"

[old rover]

ok

[onyx root]

is that what you meant?

[old rover]

yeah

"If you find the data you're looking for and it isn't in the beginning of the list, you'll need to keep track of the previous node so you can remove it. You remove a node by connecting the previous node's next reference to the current node's next reference. That's all the line does. Now when you traverse the list you'll go straight from the deleted node's previous reference to its next reference and skip the deleted node."

that's someone else's explanation

[onyx root]

@old rover self.head = self.head.next is only run when the data you are looking for is at the beginning of the list.

i recommend using a pencil and paper, and stepping through this code as if you were the computer.

[old rover]

ok

[jovial tartan]

does a singly linked list with a dummy header node have a size of 1?

or is it considered zero

[mint jewel]

depends on which result is more useful to the user.

[old rover]

is doing it w visualgo good too?

[mint jewel]

I would expect that if there are no elements from the user in the list, the expected size is 0

[jovial tartan]

i'm just trying to implement a generic linked list right now and the purpose is eventually to make it a stack

[jovial tartan]

thanks!

[mint jewel]

for stacks, an empty stack should have a size 0

if that holds, its fine

[jovial tartan]

that makes sense

appreciate the help!! 🙏

[onyx root]

I don't know what visualgo is, but if it is passive, then no, it's not a replacement for pencil and paper.

@old rover the point of the pencil and paper is to really focus on what each line of code is doing, and how it affects the data structure.

[old rover]

ok

[jovial tartan]

it's a visualization tool that shows what different algorithms are each step but its sometimes not very clear

[onyx root]

tbh, i couldn't figure out how to make it do anything. It just kept showing me dialogs full of densely packed text. 😦

[jovial tartan]

like it doesn't display what exactly is going on under the hood like using pencil and paper would or debugging in the IDE

i couldn't either

my professor just shows them to us as a visual representation of sorting algos in lectures

[old rover]

if self.head.data == target_node_data:

does this line mean if the data of the node is equal to the data of the other node?

I drew it out

so like

if you have a linked list of 1--> 2 ---> 3--> None

and you wanted to insert 1

what would happen?

it would be 1 ---> 1 -----> 2 ---> 3----> None

magic

[onyx root]

i don't know what code you are looking at. You showed us a comparison line. That changes nothing. Perhaps the next line does?

[old rover]

self.head = self.head.next

 def removeNode(self, target_node_data):
      if self.head is None:
        raise Exception("List is empty") #if the linked list is empty then it stops the program
      if self.head.data == target_node_data: #if the head's data matches the target node's data
        self.head = self.head.next  #self.head becomes the new target node???
      previous_node = self.head #what is this line for?
      for node in self:
        if node.data == target_node_data: #if the data matches
          previous_node.next = node.next  #idk
        return
      previous_node = node
      #idk

this is the entire function for context

[onyx root]

i wish i could explain this so that you understood, but I don't know how.

[old rover]

it's all good nedbat

thanks for trying

I'll ask someone else

[onyx root]

you are reading a function called "removeNode", but talking about "you wanted to insert 1"

[old rover]

oh I may have looked at the wrong function

1---> 2---> 3 ---> None

if you wanted to remove 1 the head data would match the target node data

but I still don't get why you need a self.head = self.head.next

def deleteNode(self,node):
      node.val = node.next.val
      node.next = node.next.next

apparently this works tooo?

set the node's value equal the next node's value

don't get that list line tho

the next node is equal to the node after the next one?

[lean dome]

It's not "is equal to", it's "is set to"

[old rover]

the next node's value is set to the node's value

[lean dome]

No, the node's value is set to the next node's value, and the node's next link is set to the next node's next link

[old rover]

why did my programming teacher tell me to read equal signs right to left in Python

https://leetcode.com/problems/delete-node-in-a-linked-list/

this is where I got it from

[onyx root]

@old rover how many Python projects have you written?

[old rover]

3

[onyx root]

if you don't mind me asking, what were they?

[old rover]

linear regression, a website to store drawings, and a badminton game

are you gonna tell me to leave algos/DS and go do more projects?

[onyx root]

i might suggest that 🙂 Is the code for those projects online somewhere?

[old rover]

No I haven't posted them yet

[onyx root]

can you share them?

[lean dome]

You can do that, too - it just becomes "y is assigned to x" instead of "x is set to y".

[old rover]

https://github.com/pythonindent/linearRegression

that's for the linear regression

https://github.com/pythonindent/logRegression

apparently I did log regression too

would not recommend do not just use sklearn algorithms before knowing the math behind them

[onyx root]

@old rover thanks. will you be uploading the other two also?

[old rover]

maybe

[onyx root]

why wouldn't you?

[old rover]

why the sudden interest in my projects

[onyx root]

i want to understand your strengths.

[old rover]

I haven't finished the badminton game bc I don't want to animate stuff rn

but I can upload the drawing thing later

should I bother learning C++ to do linked lists there bc I found a website that offers it?

[onyx root]

please stop looking at yet more websites

[old rover]

or is that too much of a timesink

why not

[onyx root]

because a tenth explanation isn't going to be better than the previous nine

[old rover]

the more implementations you look at the more confused you'll get

something like that

is it time to just start writing these on my own?

maybe I can think of simpler things to do

[fervent saddle]

Does anyone here know if you can program snake game with an arbitrarily large board, but the only data structure you’re allowed to use is a single array, and everything is O(1)?
I had an idea where you could have 4 different numbers for snake segments, and each of the numbers says which direction the next segment is in. But then randomly placing the food for the snake to eat might be O(n) because if the snake occupies almost the whole board then the program will possibly have to search almost the whole board for a valid spot for the food.
Has anyone here come up with anything that could do this?

[old rover]

@fervent saddle school project?

[fervent saddle]

No

[old rover]

@onyx root interesting I don’t even know my strengths

Talking is my strength

[fervent saddle]

I don’t know if it’s even possible to do it. I can’t think of a way, but I’m definitely a lot worse at thinking of algorithms than people who spend time on this channel

So I’m wondering if anyone here has ever happened to think about something like this

Or if anyone knows if it’s definitely not possible

Snake game is such a well known game that I’m hoping someone has thought about this before and has an answer

Also what if the array’s data had to be a limited size? Like what if it was a byte array?

And each grid space had to be represented by a single byte

[lean dome]

Technically, a hash table keyed by (row, col) allows representing an arbitrarily large plane with all accesses and updates in O(1) time.

And you can, with an arbitrarily large array, represent a hash table with open addressing

You'll occasionally need to resize and rebalance, but you can do that by growing the array and just ignoring the first half of it from then on, if you're not even allowed to create a second array.

[fervent saddle]

What if each space in the array had to be part of the grid?

Or, you could use another data structure aside from the one to store the grid, but it can’t grow at all with the grid

You know what I mean?

[onyx root]

@fervent saddle i'm not sure what you meant by "and everything is O(1)?"

[fervent saddle]

Keeping everything O(1) time complexity

How could you keep food placement O(1)?

If the snake is taking up the whole board, the program might have to go through the entire board until it finds a valid spot to put the food

[agile sundial]

keep a set of coordinates where the snake isn't

it wouldn't be random though, since you can't use random.choice on a set

[onyx root]

it could be O(1) if you have a set of available spots

but creating that set initially would be O(N)

[fervent saddle]

Would the set need to have more space per index if the board got big enough in order to store the grid numbers?

[lean dome]

Yes, but that's still O(n) space, and O(1) time.

[fervent saddle]

What if the array wasn’t allowed to have a varying amount of space per index, it had to be the same size no matter how big the board got?

[lean dome]

You can't store an infinite amount of information in a fixed amount of space

[fervent saddle]

I mean that the array could have any amount of space, but each index had to be the same size

Well, I guess you could use multiple indexes

Or something like that

[lean dome]

You're just describing memory, at that point, and a turing machine possibly.

[fervent saddle]

So that requirement doesn’t make sense when said like that

But you know what I’m trying to say?

[mint jewel]

You can't store an unbounded index in a O(1) space

But you could just have a tile index and then an index within the tile

[lean dome]

honestly, no, not at all 😄

[fervent saddle]

Like how if you used a set to store all available spaces, at first you could keep track of the available grid spaces with 1 byte. But then with larger grid spaces, you need 2 bytes. What if you couldn’t do that?

[onyx root]

it's unusual to think about byte size like that with Python

[fervent saddle]

I’m thinking about it because I thought it would be interesting to make snake game by using a byte array. But then I realized that placing food could conceivably be slower based on the board size

That’s what made me start thinking of it

[lean dome]

another way to represent this that might be closer to what you're looking for, though, is some sort of spiral addressing for board cells.

Zabcdef
wJKLMNg
vYBCDOh
uXIAEPi
tWHGFQj
sVUTSRk
rqponml

The cells are numbered A through Z, then a through z

there's any number of spiral numbering schemes you can pick, I didn't give this too much thought. Once you pick a scheme, though, you can map any given (X, Y) value to a particular index of an array, and you would only ever need to grow the array at the end as the snake moves.

[onyx root]

@fervent saddle but it's not a problem to have O(N) here, is it?

[lean dome]

The mapping would basically be taking your coordinates, figuring out which concentric ring around the origin they fall on. Based on how many rings are inside the one they fall on, you have an offset you can use into a single dimensional array, and you can add the offset within the ring to that.

[fervent saddle]

Where did you read about that?

[lean dome]

I didn't

Here's a stackoverflow that works along with a similar spiral indexing scheme, though: https://stackoverflow.com/a/30827007/337899

https://math.stackexchange.com/a/163093 is a pure math one.

https://superzhu.gitbooks.io/bigdata/content/algo/get_spiral_index_from_location.html has an algorithm for it as well.

the idea of numbering grid cells in a spiral to map an infinite plane isn't terribly clever, and once you have that idea, it's just a a bit of math to figure out the coordinates -> number of steps mapping.

[fervent saddle]

And you can use that to make it so the program always finds a spot to place the food in the same amount of time regardless of board size?

[lean dome]

sure. pick a random index 0 <= idx < board_size, see if it has food or snake in it. If so, loop and try again, if not, place food in it.

that's O(1) with respect to the board size, though it's not O(1) with regards to the snake size.

[fervent saddle]

Yeah

If the snake is occupying most of the board

Why would it need to grow as the snake moved? and also wouldn’t that be O(n) if the array needed to be resized?

[old rover]

Am curious

Should I be doing leetcode questions for every algo/data structure I learn?

Or should I finish all of Grokking and then do them

[onyx root]

there's no right answer to that

yes

or link to it

[agile sundial]

is that just a tree?

how is that a binary tree

oh sorry, it is a binary tree 😔

it's not a binary search tree

yeah, no worries, i'm just being dumb

you have a sentinel for the leaf nodes?

how does if v is leaf work

[lean dome]

Dynamic array appends are amortized constant time. Each time you grow the array, you grow it by a larger amount than the last time (typically you resize it to 1.5x or 2x its current size). This way, even though every resize is more expensive than the last, resizes happen less frequently over time. On average, that's O(1), not O(n).

[agile sundial]

so, you're trying to find the max and min value of all possible paths to the leaves, right? @uncut glen

yeah, gotcha

so traversing all the nodes of a binary tree can be done in O(n)

[fervent saddle]

The one single append that causes a resize is O(n), and it’s just effectively O(1) in the context of something like growing it in a for loop, right?

[agile sundial]

why do you need to sort at all, you can use min and max functions

faster than sorting, for sure

O(n), both

i think i still don't understand what you're trying to do

what's the problem

do you have words i could read

[lean dome]

right, exactly. Any given append can take O(n) time to move stuff, but on average that's O(1) time when considered across all appends.

[agile sundial]

ok, thanks

right, and you think it's O(n)?

what about that nested for loop

right

no the for loop is fine

yeah, it looks O(n) to me

[dapper sapphire]

Is it wrong to call a python list() or [] an array?

[onyx root]

it's better to call it a list

[dapper sapphire]

Whenever I create one, I name it as array and what it is supposed to store, so array_of_students.

[agile sundial]

they're practically interchangeable but they're technically not arrays, unless you're working with numpy or some library that provides actual arrays

why not just students

[dapper sapphire]

sometimes I create dictionaries, so it's easier to distinguish if it's a list or dictionary when me and other people are looking at the code.

[dapper sapphire]

Yeah, I think I'll start doing that. Especially when we do print(type(list())) it says list type

[dapper sapphire]

Oh so like when we do this:

import numpy as np
arr = np.array([1, 2, 3, 4, 5])

print(arr)
print(type(arr))

it says <class 'numpy.ndarray'>

[agile sundial]

hm?

[dapper sapphire]

Because when we print the type it says array.

[agile sundial]

not only that, but numpy arrays are actual arrays

while python lists are not arrays

[fair brook]

hi!!

[old rover]

python lists are dynamic arrays

[dapper sapphire]

Oh ok for a moment I was thinking numpy arrays are different from the regular arrays, but they are not. Thanks!! That was helpful.

[dapper sapphire]

How do you describe dynamic arrays?

[agile sundial]

wdym "the regular arrays"

[old rover]

the size of the dynamic array can be modified

[dapper sapphire]

By regular arrays, I was thinking more in terms of C array.

[agile sundial]

huh, ok

[lean dome]

When I name dictionaries, I often call them value_by_key when I want people to understand them. Like, score_by_student_id or something.

When someone sees score_by_student_id[sid] they know exactly what's happening

[old rover]

Lmao I was using camelcase before stelercus corrected me

I’m surprised not a single TA or prof even told me to not use camelcase w python

[sweet crest]

Hey, is anyone available to explain the following algorithm to me?
It is the Cooley-Tukey FFT algorithm.
It is written in pseudo code, and while i understand what each operation is supposed to do i get highly confused by the indices in line 5 and especially 6.

X0,...,N−1 ← ditfft2(x, N, s):             DFT of (x0, xs, x2s, ..., x(N-1)s):
    if N = 1 then
        X0 ← x0                                      trivial size-1 DFT base case
    else
        X0,...,N/2−1 ← ditfft2(x, N/2, 2s)             DFT of (x0, x2s, x4s, ...)
        XN/2,...,N−1 ← ditfft2(x+s, N/2, 2s)           DFT of (xs, xs+2s, xs+4s, ...)
        for k = 0 to N/2−1 do                        combine DFTs of two halves into full DFT:
            t ← Xk
            Xk ← t + exp(−2πi k/N) Xk+N/2
            Xk+N/2 ← t − exp(−2πi k/N) Xk+N/2
        end for
    end if

(https://en.wikipedia.org/wiki/Cooley–Tukey_FFT_algorithm)

The indices dont show up very well on copy paste, here is a screenshot:

eg in line 6 the input is x+s. On the wiki Page they specify that this is to be interpreted as if x were starting with x_s, but does this mean only the first index is swapped with the s-th index or should i start at index s and end at index N; or maybe start at index s and end at index s-1 by adding the start of the array to the end. im so confused

[half lotus]

The comment on the right seems most helpful

When recursing, you pass x[s:] as the subarray

And you'd index it using 2s because you're doubling the stride

This is all written from the perspective of the caller. When you recurse, x = x[s:] and s = 2s

N basically denotes the length of the array x I believe

Cause it shows it goes up to x_N-1

[neat oracle]

what is big o notation

[sweet crest]

f = O(g) if f > g for large numbers iirc
eg. if you have f(x) = x² and g(x) = x + 1000, because f diverges faster to infinity than g, even though f(1) < g(1)

it is pretty much large omega notation with the > / < swapped.

[neat oracle]

tanks

[sweet crest]

the large notation can be equal as well though btw, while the small notation cannot.
eg. f(x) = x² and g(x) = 3x², even though f(x) < g(x) for all x, f = O(g) is still true because they diverge at the same rate.
This will result in the Theta notation wich describes functions for wich f = O(g) and g = O(f)

[neat oracle]

tytytyty

[shadow rune]

Can anyone tell me how to add labels/text or a second yaxis from another Col to this: Do you know how I can add this legend or text to my px.bar, need to display the text for each of my values:

def SetColor(y):
        if(y <= 1):
            return "red"
        elif(y <= 2):
            return "orange" 
        elif(y <= 3):
            return "yellow"
        elif(y <= 4):
            return "lightgreen"
        elif(y <= 5 | y <= 6):
            return "green"
        elif(y <= 7):
            return "darkgreen"
        elif(y <= 8):
            return "silver"
        elif(y <= 9):
            return "gold"
def Setlabel(y):
        if(y <= 1):
            return "Very low (1)"
        elif(y <= 2):
            return "Low (2)" 
        elif(y <= 3):
            return "Below average (3)"
        elif(y <= 4):
            return "Average (4)"
        elif(y <= 5 | y <= 6):
            return "Average (5, 6)"
        elif(y <= 7):
            return "Above average (7)"
        elif(y <= 8):
            return "High (8)"
        elif(y <= 9):
            return "Very High (9)"


px.bar(filtered_df, x=filtered_df["ID"], y=filtered_df["Score"]).update_traces(marker = dict(color=list(map(SetColor, filtered_df['Score'])))).update_layout(legend = dict(list(map(Setlabel, SetColor, filtered_df['Score']))))

[trim fiber]

Is it Python? I have never seen y <= 5 | 6 or y <= 5 | y <= 6 notation before

[shadow rune]

Python, plotly, numpy. My mistake with y <= 5 | 6, but y <= 5 | y <=6 works

[trim fiber]

>>> y = 6
>>> y <= 5 | y <= 6
False
>>> y <= 5 or y <= 6
True

[shadow rune]

Thanks @trim fiber

Surprised it worked still for the color

[trim fiber]

Glad to help, at first I thought it was some new-unknown syntax

[shadow rune]

I’m learning still

@trim fiber wouldn’t happen to know plotly as well? 🙂

[trim fiber]

Unfortunately no, used Matlab during studies to make plots... However maybe #data-science-and-ml channel can be helpful

[late wharf]

what's the best/most common way of representing Binary Search Trees in Python? Is it the way shown here?
https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/
i.e just one root node to represent a tree rooted at that node

when I learned about BSTs in my CS101 course we used functions so I'm finding this a bit confusing to work with

[spring jasper]

I dont see why you wouldnt have a BST class to group all tree related functionality

[late wharf]

well they're trying to do it from a functional programming perspective I think (in my course)

so no OOP yet

[late wharf]

but yeah that too, i was thinking even with the OOP way you'd have a Node class and a BST class

then you'd call something like bst.insert instead of having it as a separate function like in the geeks for geeks python implementation

[old rover]

@late wharf would not recommend geeks for geeks as a reference

Are you sure something like real python doesn’t have it?

[iron plover]

please help with this code i ran
import statsmodels.formula.api as sma
X_train = sma.add_constant(x_train) ## let's add an intercept (beta_0) to our model
X_train = sma.add_constant(x_test)
it came out with this error
File "C:/Users/Hommaston17/PycharmProjects/lineer regression/regression.py", line 31, in <module>
X_train = sma.add_constant(x_train) ## let's add an intercept (beta_0) to our model
AttributeError: module 'statsmodels.formula.api' has no attribute 'add_constant'
please help to solve it

[spring jasper]

there's no add_constant in that module

[old rover]

why is he or she using that instead of sklearn

[spring jasper]

Does it matter?

[old rover]

not really but sklearn is customary for that kind of stuff

whatever they like more tbh

[stray crane]

Anybody who can help me with matplotlib and pandas working in conjunction? I've described the problem here: https://stackoverflow.com/questions/66547963/plot-an-infinite-line-between-two-pandas-series-points

[old rover]

oh boy you asked it on Stack Overflow

gonna be marked as a duplicate real soon

[spring jasper]

You have two points per line, that means you can figure out its slope and y intersect and plot the line for the whole of x-axis

[stray crane]

The embedding with pictures and code is far better on stackoverflow than on discord. Its literally posted there as not to taint ones eyes

[old rover]

whatever you wanna do dude

[old rover]

 def __iter__(self):
    for node in self:
      head = self.head
      next_node = head.next
      return next_node

so I tried to write an iter method through a linked list in 5 minutes

well actually 20 minutes I was stumped in 5 minutes

this is not an _iter method bc it only returns the node after the head?

I have to do something else other than looking at 30 implementations a day

 def __iter__(self):
      node = self.head
      while node is not None:
        yield node
        node = node.next

this is how real Python did it

[spring jasper]

to use for loops on self you need to implement __iter__ first, so that it knows how to make it an iterator

[agile sundial]

__iter__ defines what happens when you iterate over an instance of the class. you can't use for node in self in the __iter__, since that would call the __iter__ of self, which would cause recursion @old rover

[spring jasper]

but youre using the for loop inside __iter__

[old rover]

so don't use for loops inside iter?

[spring jasper]

dont use for loops on self inside __iter__

[old rover]

ok

[blissful pumice]

Hi ! i'm new to this server so excuse me if i don't respect some rules.
As part of a challenge, I have to solve this small problem, purposely containing errors and is incomplete. Unfortunately, I am a beginner on python and do not understand everything. Can i ask u here ?

[old rover]

this channel is for algos/DS exclusively if the problem has that you can ask

#❓｜how-to-get-help otherwise this may be helpful

ELI5 how does it cause recursion?

recursion is when a function is called in itself

right?

[spring jasper]

for loops use __iter__ so when you have for loop in the __iter__ it causes recursion

this is for self btw

[blissful pumice]

Ty @old rover

[agile sundial]

@old rover did you see my earlier message?

[old rover]

yes

[agile sundial]

did i explain adequately

[old rover]

let me re read it again

[agile sundial]

or, do you understand now that mariosis has added stuff

[old rover]

oh self is an instance of the class

[agile sundial]

self is the instance that you're trying to iterate over, in __iter__

[old rover]

so it wouldn't make sense to use a for loop

bc it's already doing that for you

[grizzled schooner]

yeah, you're defining how to iterate in __iter__ so you can't use a for loop yet because you haven't defined it yet

[old rover]

the iter_ method is used to iterate over something

so don't use a for loop in it

TIL

see I wouldn't know this if I didn't try to code it on my own

[agile sundial]

welll it's not that you can't use forloops in __iter__, it's that you can't iterate over self in it

[spring jasper]

dont use a for loop for self

[old rover]

def __iter__(self):
      node = self.head
      while node is not None:
        yield node
        node = node.next

but they can use a while loop?

[agile sundial]

it's not that for loops are banned in __iter__

[spring jasper]

yea, while loops dont use __iter__

[old rover]

bc a while loop is conditional

while node is not None: means if there is a head

right?

[agile sundial]

it means it will loop until node is None

effectively, it means keep yielding nodes, until there aren't any more

[old rover]

it doesn't mean if there is a head?

[grizzled schooner]

nope

remember, node is being changed to node.next in each iteration

[old rover]

is while node is not None: talking about how after the tail node it's None?

[spring jasper]

the condition in the while doesnt reference any specific node

its going to keep looping until there are no nodes left

[old rover]

so until it hits None

[grizzled schooner]

yeah

[old rover]

ok

[grizzled schooner]

because for the last node in the linked list, node.next will be None

[old rover]

ok

yay so does this mean writing without resources is working?

gonna have to do that for an interview anyways

[agile sundial]

did you write that __iter__ without any resources?

[old rover]

which iter__

[agile sundial]

the most recent one you posted

[old rover]

no

[agile sundial]

are you familiar with yield?

[old rover]

so if you had numbers 1 to 100

you could read them off one by one

but instead you create a generator

and it yields number by number?

[agile sundial]

what do you mean by "read them off one by one" then? it seems similar to the second thing you said, "yields number by number"

[old rover]

if you are processing a list of 0 to infinity with yield you can return one number at a time instead of the infinitely big list

that's the best I can explain it

[agile sundial]

yeah, that's a pretty good explanation

the idea is to give values back one at a time to the caller

[old rover]

so this gives one node at a time

until it hits None

[agile sundial]

yep

exactly

[old rover]

yay

[old rover]

omg guys

I actually wrote the _iter method without even looking at the real python code

maybe I am starting to understand this stuff

[agile sundial]

show us?

[old rover]

class Node:
  def init(self, data):
    self.data = data
    self.next = None
  


class LinkedList:
  def __init__(self, llist):
    self.head = None
    self.tail = None


  def __iter__(self):
    node = self.head
    while node is not None:
      yield node
      node = node.next

[agile sundial]

very nice

[old rover]

if I carry on like this I'll develop less of a reliance on their code

[agile sundial]

huh?

[old rover]

whoms't?

yeah but why'd you ping that user and what does this have to do w algos/DS

[fiery cosmos]

Is it algos?

Oh fuck.

Sorry @old rover @agile sundial

[old rover]

all good

[halcyon plank]

You are not allowed to use that command here. Please use the #bot-commands channel instead.

[old rover]

def addFirst(self, data):
    node = Node(data)
    node.next = self.head
    node = self.head

so i tried writing this

def addFirst(self, data):
      new_node = Node(data)
      new_node.next = self.head
    #the one after the new node is the old head
      self.head = new_node
    #the new node becomes the head

but it doesn't match this

I don't think it does the same thing

[agile sundial]

they do not

your code just points node to self.head, and the new node that you created is discarded

[old rover]

ELI5

my understanding of the correct code

is that it creates a reference from the head to the new node

and then the new node turns into the head

2-->3-->None

i think that node.next = self.head does this

---> 2 ---> 3 ---> None

like it creates a reference for the new head to the older head

[agile sundial]

in the correct code, on the first line, you just create a new node

it's not connected to anything

consider the linked list 2 -> 3 -> 4 -> None, and we want to use addFirst to add 1 to it

so, after the first line, we have

self.head
|
2 -> 3 -> 4 -> None

somewhere else:
1 -> None

makes sense?

[old rover]

yeah that somewhere else refers to somewhere in memory right?

[agile sundial]

yep, right now, the linked list and the new node are not related at all

well, not necessarily somewhere else in memory, but it's just that they're not connected in any way

[old rover]

and then that .next creates a reference from the node to the original head

[agile sundial]

yep, so after the second line

     self.head
     |
1 -> 2 -> 3 -> 4 -> None

then after the third

self.head
|
1 -> 2 -> 3 -> 4 -> None

[old rover]

hm

ok

so then what does my code even do?

[agile sundial]

your first and second lines are the same, so i won't bother showing them

on the third line

you say node = self.head, which creates another reference to self.head, and the reference to your new_node is gone

self.head
|
2 -> 3 -> 4 -> None
|
node
``` they both refer to the same node

[old rover]

oh

ok

I've just never made a mistake like that before

[agile sundial]

and now you've learned about it ¯_(ツ)_/¯

[old rover]

most of linked lists is just reassigning things

and .next, .prev, .head, .tail

so if you can figure out how to reassign things properly you don't need to worry

[spring jasper]

Wait till you get to trees and rotations

[vocal gorge]

...rotations?

[agile sundial]

rotations?

[old rover]

do you mean tree rotations?

[spring jasper]

Am i being wooshed

Tree rotations

[vocal gorge]

ah, I see, it's a tree operation I haven't learned the name for. I thought you were talking about something fun like quaternions, and wasn't sure how that related to linked lists.

[old rover]

a = 15
#So this means that a is a reference to 15? They said assigned the value 15 in college

[spring jasper]

Wtfrick how are quaternions fun

I didnt actually go through tree rotations in school, maybe i should do it now

[old rover]

I don't get it I understand reassignment

if you did a = 15 and then you did a = 19

a would now be 19

[vocal gorge]

It doesn't really matter in Python because there are no primitive data types - that is, there does not exist objects that are simple and passed-by-copy - everything is passed by reference. Though ints being immutable, it doesn't really matter.

[old rover]

why did I even make that mistake does this mean I don't know reassignment

I can explain why the correct code is correct, but I can't explain why the incorrect code is incorrect

[vocal gorge]

If you want to be fully implementation-agnostic: a would be associated with an object of type int and value 19 🙂

[old rover]

boi

[vocal gorge]

Is it the same 19 as you get when you do 15+4? Maybe, depends on the implementation.
If you do a = 19;del a; a=19, do you get the same object both times? Maybe, depends on the implementation.

[old rover]

a = 19
z = 5
a = z
print(a)

a would now be 5

[agile sundial]

yep

[old rover]

I tend to read equal signs in coding right to left

[vocal gorge]

yeah, and that 19 object that was previously assigned to a would (theoretically, ignoring small int caching) be dropped at the a = z line

[old rover]

so before it was a ----->19, but now it's a ----> 5

[vocal gorge]

yeah, and z--->5 still

[old rover]

I don't know why I don't read equal signs left to right in coding

self.head = new_node
this line makes the head the new node

[agile sundial]

right to left makes the most sense, for assignment

[old rover]

oh now it makes sense

ok

I may be tired

maybe take a break

[vocal gorge]

here's one interesting way to look at it:

a = 19 # 1 reference to 19
z = 5  # 1 reference to 19, 1 reference to 5
a = z  # this adds an extra reference to whatever z is (so 5), and removes a reference from whatever a was pointing at, so 19
# so 5 has 2 references and 19 has 0. 19 should get dropped now (it won't because of small int hashing, but with most types it would be)

[old rover]

interesting

[agile sundial]

the () on line 4 is an implementation detail ¯_(ツ)_/¯

[vocal gorge]

from a refcounting perspective, an assignment:

a = b

always adds +1 reference to whatever the name b points at (because a now points to it too), and if a was assigned to something, removes 1 reference to whatever a was pointing at (because a no longer points at it)

[old rover]

what () on line 4?

oh

the one after the print statement?

[agile sundial]

yeah, in the comment

[austere sparrow]

yep

[vocal gorge]

yeah, it's only a CPython thing that small ints get reused

[old rover]

You didn't actually need parentheses for print statements in earlier versions of Python right

I read that somewhere

[austere sparrow]

I mean... refcounting is an implementation detail.

[old rover]

what's refcounting

[vocal gorge]

uhh, yeah, but I meant the parantheses in my comments

[austere sparrow]

reference counting -- it's when an object keeps track of how many references it has.

[agile sundial]

fair enough, what does pypy use to garbage collect?

[vocal gorge]

hmm, fair enough. I suppose that's the main reason you can't know when __del__ gets called - it depends on the implementation

[austere sparrow]

it's not part of the language definition. You can write a Python implementation that doesn't discard objects at all. It would be a silly implementation, but still a valid one.

[austere sparrow]

of if it gets called, I suppose

[old rover]

oh my bad

[vocal gorge]

yeah. Presumably JPython only does GC, for example, so you'd only have objects dropped on the next GC pass

[fiery cosmos]

Hi everyone. Can I get your opinion on a search function I wrote?

[old rover]

you don't need to ask to ask questions

[fiery cosmos]

I didn't want to break the ongoing discussion.

[old rover]

no that's fine

[plain halo]

any RegEx veterans here?

[fiery cosmos]

So, I thought this is a recursive tournament search. But is it really?

def min_max_tournament(arr):
    #print(arr)
    if len(arr) <= 2:
        return([min(arr), max(arr)])
    else:
        a = min_max_tournament(arr[:int(len(arr)/2)])
        b = min_max_tournament(arr[int(len(arr)/2):])
        return([min(a+b), max(a+b)])

[vocal gorge]

this looks like it won't work to me

your function's return type is a two-element array of numbers

ah, I see

So you're finding the minimum and maximum in a big array recursively.

This looks pretty inefficient though if it's all that it does, since you can do so in O(n), and this looks more complex than that. What's the intention of this? I haven't heard of a tournament search before.

nevermind, the complexity is in fact O(n) here, it's just not very obvious due to it being recursive.

[agile sundial]

the overhead of the function calls will make it much slower than max and min

[vocal gorge]

that's definitely true.
(though also aren't max and min C-implemented, which will make it even more unfair?)

[agile sundial]

would be slower than a python-implemented max and min too ¯_(ツ)_/¯

[fiery cosmos]

This is just an exercise.
You take pairs of elements, compare, then go to the next 'tournament'. Normally in a tournament search, I'd expect the input to be partitioned into n pairs (+1, if it's len is odd). In this one, there can be n pairs +2 I think. depending on the length of the input.

[onyx root]

@fiery cosmos is there any advantage to doing it this way?

[fiery cosmos]

Probably not. Just an exercise because I read about it.

[vocal gorge]

Ah, I see. It looks right to me, but I'm not sure about what the exact number of pairs there's supposed to be.

[agile sundial]

log n pairings?

no wait, n log n now i am doubting myself :/

it's the same as an ideal comparison sort

[vocal gorge]

the original pairs(with maybe one remaining one) there should just be (n+1)//2

I'm not sure that this is how many this code does, though.

[fiery cosmos]

I'm not sure either. Recursion is messing with my head...

[old rover]

imagine if you opened a door and walked in but it's the same door

and you're going nowhere

that's recursion

[fiery cosmos]

I tried a visual representation of how the input is partitioned for n=6. Behold:

# Regular tournament
o o o o o o
 o   o   o
   o   o
     o
    
# Recursive 'tournament'
o o o o o o
 o  o  o  o
   o    o
      o

The difference is: pairing up in the regular tournament vs. recursively halving the input length.

[late wharf]

Dont think binary trees are a part of the standard python packages, there is a package on pip for it though. But I'm doing this for my own learning so I want to implement it myself

[spring jasper]

Realpython is a website with python articles

He doesnt mean the python builtins

[old rover]

what mariosis said

[late wharf]

Oh nope just checked dont think they have anything on bsts

For what its worth i've seen the bst implementation from geeks for geeks in some leetcode questions tbf

[old rover]

yeah real python doesn't have it

[old rover]

class Node:
  def init(self, data):
    self.data = data
    self.next = None
  


class LinkedList:
  def __init__(self, llist):
    self.head = None
    self.tail = None


  def __iter__(self):
    node = self.tail 
    while node is not None:
      yield node
      node = node.prev

so this would work on a doubly linked list too right?

but it would only iterate from the head node to the tail

not the other way around

By other way around I mean the tail to the head bc it has references going the other way too

[lean dome]

anything that only uses next will work on either a doubly or singly linked list. Things that use prev will require a doubly linked list.

[old rover]

@lean dome would they ever ask me to write a method that iterates backwards through the list?

Bc then I would just change node = node.prev

actually no you can’t do that

Start w the tail

And then go backwards from that

[lean dome]

right.

[old rover]

good that means I actually understand this stuff now

nedbat was right

The more implementations I was looking at the more I was slowing myself down

You gotta write the code on your own eventually

[lean dome]

yep!

[old rover]

so I literally sat there and wrote methods over and over until I understood what I was writing

if that’s what it takes for me to understand data structures I’ll gladly do it

class Node:
  def init(self, data):
    self.data = data
    self.next = None
  


class LinkedList:
  def __init__(self, llist):
    self.head = None
    self.tail = None


  def __iter__(self):
    node = self.tail 
    while node is not None:
      yield node
      node = node.prev

This is what would work to iterate backwards through the linked list

[lean dome]

looks right to me.

[old rover]

it feels so good to finally understand something that I spent like a week on

that is why I like CS

it’s so satisfying to get things right

Dude

I just figured out how to add a node after a given node too in my head

Where was this a week ago???

[lean dome]

seems like you've finally wrapped your head around how the data structure works, and how to manipulate it 🙂

nice job.

[old rover]

if you wanted to do a circular linked list wouldn’t you just do self.head = self.tail.next

so that you have a reference from the tail to the head

[lean dome]

other way around - self.tail.next = self.head

and if it's doubly linked, also self.head.prev = self.tail

[old rover]

Interesting

I’ll look at it tomorrow

[old rover]

@lean dome why am I even making that mistake

I made that mistake last time too

I swear I understand reassignment

[agile heath]

hey anyone know how to decipher this

i need t turn Ilv aa oeJv! into I love Java! but I have no idea what code i need to use to do that

[supple needle]

@agile heath Try mapping the letter positions to see if you find a pattern

[exotic chasm]

Anyone knows python folium map here?

[fiery cosmos]

which one should i download?

[grizzled schooner]

visual studio code, if you want to use python

also, this isn't the best channel for this maybe try #editors-ides next time

[fiery cosmos]

oh okay thank you!

[fiery cosmos]

will do

[mighty cedar]

this is the question i am working on, i have time limit in it, so can't go with the naive approach.
The below solution was what i came up with

[halcyon plank]

Hey @mighty cedar!

Uh-oh! It looks like your message got zapped by our spam filter. We currently don't allow .txt attachments, so here are some tips to help you travel safely:

• If you attempted to send a message longer than 2000 characters, try shortening your message to fit within the character limit or use a pasting service (see below)

• If you tried to show someone your code, you can use codeblocks
(run !code-blocks in #bot-commands for more information) or use a pasting service like:

https://paste.pythondiscord.com

[mighty cedar]

def sumsDivisibleByK(a, k):
    count=0
    freq=[0]*k
    for i in range(0,len(a)):
        freq[a[i]%k]+=1
    count=0
    if k%2==0:
      count+=int((freq[0]*(freq[0]-1))/2)
      count+=int((freq[int(k/2)]*(freq[int(k/2)]-1))/2)
      for i in range(1,int(k/2)):
        count+=int(freq[i]*freq[-i])
    else:
      count+=int((freq[0]*(freq[0]-1))/2)
      for i in range(1,int(k/2)+1):
        count+=int(freq[i]*freq[-i])
    return count

this is the error i am getting, unable to see the hidden test cases, no idea as to how to proceed.

[grizzled schooner]

try running it in your own text editor

[mighty cedar]

the code is working fine,
all visible test cases are getting passsed.
6/6
and 3/5 hidden test cases are getting passed.
Its just the 2 hidden ones i have 0 idea as to why they are not passing.

[old rover]

https://youtu.be/o6VuST08S60

idk I found this nice

but she talks about arrays not dynamic arrays or lists in Python

are all arrays dynamic arrays in Python?

are heaps and queues considered easy data structures too?

they're not in Grokking

they call them "advanced data structures"

it looks like the syntax for stacks and queues is really easy

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



class LinkedList:
  def __init__(self, llist):
    self.head = None
    self.tail = None


  def __iter__(self):
    node = self.head
    while node is not None:
      yield node
      node = node.next

  
  def addBefore(self, data):
    node = Node(data)
    node.next = self.head
    self.head = node


  def addAfter(self, data):
    node = Node(data)
    node.next = self.tail
    self.tail = node

I wrote it without looking

addBefore and addAfter are literally the same method it's just .tail instead of .head

how was I having trouble with this before

[spring jasper]

Do they work tho?

[old rover]

how do you test that without using repr functions

[spring jasper]

You dont, make a repr

[old rover]

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

  def __repr(self):
    return self.data


class LinkedList:
  def __init__(self, llist):
    self.head = None
    self.tail = None


  def __iter__(self):
    node = self.head
    while node is not None:
      yield node
      node = node.next
  
  def __repr__(self):
    node = self.head
    nodes = []
    while node is not None:
      nodes.append(node.data)
      node = node.next
    nodes.append("None")
    return "--->".join(nodes)

  
  def addBefore(self, data):
    node = Node(data)
    node.next = self.head
    self.head = node


  def addAfter(self, data):
    node = Node(data)
    node.next = self.tail
    self.tail = node



llist = [1,2,3]
llist.addBefore(Node(5))
print(llist)

Traceback (most recent call last):
File "main.py", line 46, in <module>
llist.addBefore(Node(5))
AttributeError: 'list' object has no attribute 'addBefore'

confused

[spring jasper]

llist is a regular list

[old rover]

am dumb

soryr

[agile sundial]

heaps are pretty complicated

queues and stacks can be implemented with a linked list

[old rover]

llist = LinkedList(["1","2","3"])

[spring jasper]

Heaps are just trees with an extra constraint

[old rover]

this is what real python does

[spring jasper]

Ok, but what are you going to do

[old rover]

oh I know why

<main.LinkedList object at 0x7f7e3c7ad7f0>

it just shows it at memorry

[spring jasper]

Show the code again

[agile sundial]

only the relevant parts

[old rover]

!pastebin

[halcyon plank]

Pasting large amounts of code

If your code is too long to fit in a codeblock in discord, you can paste your code here:
https://paste.pydis.com/

After pasting your code, save it by clicking the floppy disk icon in the top right, or by typing ctrl + S. After doing that, the URL should change. Copy the URL and post it here so others can see it.

[old rover]

https://paste.pythondiscord.com/tokivaqima.rb

[spring jasper]

You commented out the repr

[old rover]

oh no

I copy pasted the wrong code

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

  def __repr(self):
    return self.data


class LinkedList:
  def __init__(self, nodes=None):
      self.head = None
      if nodes is not None:
        node = Node(data=nodes.pop(0))
        self.head = node
        for elem in nodes:
            node.next = Node(data=elem)
            node = node.next

  def __iter__(self):
    node = self.head
    while node is not None:
      yield node
      node = node.next
  
  def __repr__(self):
    node = self.head
    nodes = []
    while node is not None:
      nodes.append(node.data)
      node = node.next
    nodes.append("None")
    return "--->".join(nodes)

  
  def addBefore(self, data):
    node = Node(data)
    node.next = self.head
    self.head = node


  def addAfter(self, data):
    node = Node(data)
    node.next = self.tail
    self.tail = node



llist = [1,2,3]
llist.addBefore(Node(5))
print(llist)

this is the code I'm using right now

[spring jasper]

Ok, the llist in that code is a regular list

Not a linkedlist

[old rover]

Traceback (most recent call last):
File "main.py", line 51, in <module>
print(llist)
File "main.py", line 33, in repr
return "--->".join(nodes)
TypeError: sequence item 0: expected str instance, Node found

[spring jasper]

Thats because your linkedlist uses Node internally

But youre also passing a Node instance

[vocal gorge]

you'll want to map repr over the nodes too

[spring jasper]

If he just passes strs into addBefore then it should work

[old rover]

it works in the original code

[spring jasper]

The original code is different

[vocal gorge]

presumably original code didn't use Nodes.

[spring jasper]

Just try llist.addBefore("5")

[topaz pulsar]

also I assume in your Node class, __repr is supposed to be __repr__

[old rover]

fixed it thanks

[old rover]

tried that too

def add_after(self, target_node, new_node):
      if self.head is None:
        raise Exception("List is empty")
      #if there is no head on the linked list, it's empty
      for node in self:
      #iterating through the linked list
        if node.data == target_node.data:
        #if the data of the node matches the data of the target node
          new_node.next = node.next
        #create references for the new node
        node.next = new_node
        #make the new node the last node or tail
        return

    def removeNode(self, target_node_data):
      if self.head is None:
        raise Exception("List is empty") #if the linked list is empty then it stops the program
      if self.head.data == target_node_data: #if the head's data matches the target node's data
        self.head = self.head.next  #self.head becomes the new target node???
      previous_node = self.head #what is this line for?
      for node in self:
        if node.data == target_node_data: #if the data matches
          previous_node.next = node.next  #idk
        return
      previous_node = node
      #idk
    def deleteNode(self,node):
      node.val = node.next.val
      node.next = node.next.next

these are the functions I didn't write yet

but it shouldn't really matter

[spring jasper]

Thats different code

[old rover]

yes

[spring jasper]

Why are you showing us this

Does your code work?

[old rover]

no

[spring jasper]

Why not

[old rover]

that code I just showed all of it works

[spring jasper]

Ok but does your code work

[old rover]

but the file where I tried to re code all of it

Traceback (most recent call last):
File "main.py", line 51, in <module>
print(llist)
File "main.py", line 33, in repr
return "--->".join(nodes)
TypeError: sequence item 0: expected str instance, Node found

[spring jasper]

Did you change the addBefore line like i showed you?

[old rover]

llist = LinkedList(["1","2","3"])
llist.addBefore(Node("5"))
print(llist)

[spring jasper]

Thats not what i wrote

[spring jasper]

Do this

[old rover]

that works

it actually works

[spring jasper]

Ok

Now test the other function

[old rover]

AttributeError: 'LinkedList' object has no attribute 'tail'

[topaz pulsar]

just one suggestion for improvement, you have already defined __iter__ in your LinkedList class, so in your __repr__ method, you dont need to do py node = self.head nodes = [] while node is not None: nodes.append(node.data) node = node.nextto make the list of nodes, you can do nodes = list(self), making your __repr__ into py def __repr__(self): nodes = list(self) nodes.append("None") return "--->".join(map(repr, nodes))

[old rover]

I fixed it

[spring jasper]

Do they both work now?

[old rover]

nope

[spring jasper]

Errors?

[old rover]

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

  def __repr___(self):
    return self.data


class LinkedList:


  def __init__(self, nodes=None):
      self.head = None
      self.tail = None
      if nodes is not None:
        node = Node(data=nodes.pop(0))
        self.head = node
        for elem in nodes:
            node.next = Node(data=elem)
            node = node.next

  def __iter__(self):
    node = self.head
    while node is not None:
      yield node
      node = node.next
  
  def __repr__(self):
    node = self.head
    nodes = []
    while node is not None:
      nodes.append(node.data)
      node = node.next
    nodes.append("None")
    return "--->".join(nodes)

  
  def addBefore(self, data):
    node = Node(data)
    node.next = self.head
    self.head = node


  def addAfter(self, data):
    node = Node(data)
    node.next = self.tail
    self.tail = node



llist = LinkedList(["1","2","3"])
llist.addBefore("5")
llist.addAfter("6")
print(llist)

no errors but it's 5--->1--->2--->3--->None

[agile sundial]

I don't think your add after is accurate

you've got the order backwards

the next of the tail should be your new node, not the other way around

[old rover]

it should be node = self.tail?

[spring jasper]

Also, self.tail needs to be updated in the init

[old rover]

 def __init__(self, nodes=None):
      self.head = None
      self.tail = None
      if nodes is not None:
        node = Node(data=nodes.pop(0))
        self.head = node
        for elem in nodes:
            node.next = Node(data=elem)
            node = node.next

[spring jasper]

You need to make the last node self.tail

But youre not, youre keeping it at None

[old rover]

idk how

I don't get why I'm having so much trouble

the add after method should be as simple as the add before method

[spring jasper]

It is but just not the same way addBefore is

[old rover]

the real python implementation is completely different

 def addAfter(self, data):
    node = Node(data)
    node.next = self.tail
    self.tail = node

[spring jasper]

Stop looking at implementations and just draw it out

[old rover]

is there something wrong with that function?

[spring jasper]

No but you'll understand it better if you figure it out yourself

[old rover]

I wrote that myself

[spring jasper]

It doesnt work tho

So instead of looking for other impls just figure out why

[old rover]

"You need to make the last node self.tail" what does that mean?

[spring jasper]

Grab a pen and paper and draw the addAfter function

That was about your init function

[spring jasper]

Add print(llist.tail) right after all of this

[old rover]

<main.Node object at 0x7f6811038d00>

[spring jasper]

Ok, add that print before you do the addAfter func

Between addBefore and addAfter

It should print out None

[old rover]

yeah it prints None

[spring jasper]

But you already have elements in the list, so it shouldnt be None

It should point to Node("3") at that point

So theres a bug in your init

[old rover]

I should be writing that self.tail is equal to the last node in the linked list

but isn't the last node in the linked list the tail?

[spring jasper]

self.tail cant figure out on it own what its supposed to be unless you tell it

[old rover]

isn't that the same issue w self.head?

[spring jasper]

self.head = node the head is assigned, but the tail is never reassigned from None

[old rover]

and you can't do self.tail = node

[fiery cosmos]

Anyone know how to do "tri par insertion", insertion sort

[old rover]

I have found myself in quite the conundrum

self.tail = node wouldn't work right

bc then you would be saying the head and tail is the same node

[spring jasper]

Thats normal tho in some circumstances

If a list only has one item in it then the head and the tail noth point to that one item

But if you add one more, the head stays the same and the tail moves to the new item

[quiet escarp]

Anyone learning javascript here.
I need a little assistance on the materials I need

[old rover]

python only server

and you can't index a linked list for the last node

and range won't do anything either

nope idk what to do

[quiet escarp]

I know

[spring jasper]

You need to do something about self.tail in the for loop in the init

[old rover]

self.tail = node.next

def __init__(self, nodes=None):
      self.head = None
      self.tail = None
      if nodes is not None:
        node = Node(data=nodes.pop(0))
        self.head = node
        self.tail = node
        for elem in nodes:
            node.next = Node(data=elem)
            node = node.next

[spring jasper]

That sets both head and tail to the first node

But then you add more nodes and you dont change the tail

[old rover]

what if you stopped the code before it hit None

and then just set self.tail = to the last node

idk how to do that tho

yield?

break?

idk

[spring jasper]

Focus on the for loop

The for loop will keep running as long as there are elements in the list you pass in

So the last node will be the last element

And you need to set self.tail to that

[old rover]

so why can't I change self.tail = node.next

that last line there

[spring jasper]

Why node.next

[old rover]

node.next is just a pointer

or a reference

right?

just like node.prev is a reference going back

node.next is a reference going forwards

[spring jasper]

Yea but at the last element its going to be None

[old rover]

oh

right

[nova holly]

So why is this

def sum_until_one(num):
    while num > 9:
        num = sum(map(int, str(num)))
    return num

Faster then this

def sum_until_one(num):
    if num < 10:
        return num
    return sum_until_one(sum(map(int, str(num))))

Are recursive funcions slower ?

[old rover]

so it should be self.tail = node

[spring jasper]

Try it

[old rover]

doesn't work

and if you flip it and say node = self.tail

it gives a new error

[agile sundial]

yes, by a lot

[spring jasper]

You'll need to show code and errors
"doesnt work" doesnt do anything for us

[nova holly]

k

[old rover]

are you talking to me?

[spring jasper]

Yea

[old rover]

 def __init__(self, nodes=None):
      self.head = None
      self.tail = None
      if nodes is not None:
        node = Node(data=nodes.pop(0))
        self.head = node
        for elem in nodes:
            node.next = Node(data=elem)
            node = self.tail

so there's the function

Traceback (most recent call last):
File "main.py", line 53, in <module>
llist = LinkedList(["1","2","3"])
File "main.py", line 20, in init
node.next = Node(data=elem)
AttributeError: 'NoneType' object has no attribute 'next'

[agile sundial]

in python, the overhead of calling a function is much greater than iterating again

[spring jasper]

Why did you remove stuff from the for loop

[old rover]

def __init__(self, nodes=None):
    self.head = None
    if nodes is not None:
        node = Node(data=nodes.pop(0))
        self.head = node
        for elem in nodes:
            node.next = Node(data=elem)
            node = node.next

this is real python's implementation

[spring jasper]

You need to add stuff to the for loop

Not replace

[old rover]

Traceback (most recent call last):
  File "main.py", line 54, in <module>
    llist = LinkedList(["1","2","3"])
  File "main.py", line 20, in __init__
    node.next = Node(data=elem)
AttributeError: 'NoneType' object has no attribute 'next'

def __init__(self, nodes=None):
    self.head = None
    self.tail = None
    if nodes is not None:
        node = Node(data=nodes.pop(0))
        self.head = node
        for elem in nodes:
            node.next = Node(data=elem)
            node = node.next
            node = self.tail

[spring jasper]

self.tail doesnt change

[trim fiber]

Something like that? Not tested

def __init__(self, nodes=None):
  if nodes is None:
    nodes = []
  nodes = [Node(data=node) for node in nodes]
  next = None
  for node in reversed(nodes):
    node.next = next
    next = node
  self.head = next

[spring jasper]

Dont just give out code please

[old rover]

but what does that have to do with self.tail

[spring jasper]

Nothing really

[trim fiber]

Oh, sorry... I have notifications from this (and few other channels) so...

I tried to help

[old rover]

it's ok

what am I supposed to add other than that?

and which way is the correct way? node = self.tail?

or self.tail = node

I think it's the second one

[spring jasper]

Try them both

[old rover]

5--->1--->2--->3--->None

so nothing really happened

there's no 6 after the 3

Traceback (most recent call last):
  File "main.py", line 54, in <module>
    llist = LinkedList(["1","2","3"])
  File "main.py", line 20, in __init__
    node.next = Node(data=elem)
AttributeError: 'NoneType' object has no attribute 'next'

but then you get this if you write node = self.tail

[spring jasper]

node = self.tail is not the answer

You need to set self.tail to something not node to self.tail

[old rover]

I don't know what

still confused

can you give me a hint?

I drew it out too

and I still don't get it

def add_last(self, node):
    if self.head is None:
        self.head = node
        return
    for current_node in self:
        pass
    current_node.next = node

I refuse to believe that this is the only way to do it

I just don't know how to define self.tail

[spring jasper]

add_last is three lines

You make a node for the value

You change the tail's next to point to that node

You change the tail to be that node

[old rover]

so just ditch the method I wrote bc it doesn't work?

[vocal gorge]

So, uhh, even I personally, despite all my anxiety about not using the most efficient algorithm for any task, believed that in most real-world cases, nothing is actually going to happen if you use an O(n^2) algorithm instead of an O(n) one - most data is small, after all, so maybe it will even be faster due to lower C.

And now I found this article.
https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times-by-70/

About a person who disassembled GTA Online, found out two ways (in the same area of code, too!) it did something that can be done in O(n) in O(n^2), and patched it to load into online mode 3 times faster.

Spoilers: the problems were:

1. String-parsing code that had to recalculate the string's length (by iterating over it, apparently) after reading every few symbols from it. I don't think I fully get this one - it's something related to how strings are done in C, so mostly I'm just once again assured that C strings are evil.
2. Appending to a list after checking, for each element, whether it's already in there - yes, in O(n) for each element. This gets far worse considering there were hashes of each item being calculated right there, and yet still the developer didn't think to use a hashmap/hashset.

The second one is something you can often see beginner programmers do in Python, and here's a programmer from Rockstar making it in GTA Online and resulting in 3x loading times full of useless CPU work.

for even more context, what the problematic code was doing was essentially parsing a JSON dict as a HashMap. In Python it's one line - json.loads - and in GTA Online it was apparently done manually, and the developer messed up twice in the process, resulting in decent computers needing 4 minutes of CPU time to parse a 10MB JSON string.

[old rover]

so O(N^2) is faster than O(N)?

I thought it was slower

[vocal gorge]

where did I say that?

[old rover]

"About a person who disassembled GTA Online, found out two ways (in the same area of code, too!) it did something that can be done in O(n) in O(n^2), and patched it to load into online mode 3 times faster."

[spring jasper]

Yea it could be done in linear time but instead it was done in quadratic

[vocal gorge]

Yeah, GTA Online code was messed up and had n^2 compexity where it should have been n.

[old rover]

cool

turns out my "reference code" is wrong too

 def addLast(self, data):
      tail = self.tail
    #make the tail the end of the linked list
      new_node = Node(data)
    #create a new node
      tail.next = new_node
    #make a reference to the new node
      tail = new_node
    #make the new node the tail

this doesn't do anything either

at least I know two methods

[agile sundial]

yikes

[vocal gorge]

for even more context, what the problematic code was doing was essentially parsing a JSON dict as a HashMap. In Python it's one line - json.loads - and in GTA Online it was apparently done manually, and the developer messed up twice in the process, resulting in decent computers needing 4 minutes of CPU time to parse a 10MB JSON string.

[rancid mica]

I need a study partner to learn and implement algo and ds in python anyone there to volunteer

[spring jasper]

Without proper checking for head, that works

def append(self, val):
	 node = Node(val)
	 self.tail.next = node
	 self.tail = node

[old rover]

@spring jasper but I’d still need to define what self.tail is in the init method right?

[spring jasper]

Yes

[old rover]

Idk how to do that

[spring jasper]

In the for loop everytime you move a node forward you update self.tail too

[cerulean river]

Hey, I am doing this problem: https://www.hackerrank.com/challenges/ctci-array-left-rotation/problem?h_l=interview&playlist_slugs[]=interview-preparation-kit&playlist_slugs[]=arrays

this is my solution:

  def rotLeft(a, d):
    i = 0
    while i < d:
        x = a.pop(0)
        a.append(x)
        i += 1
    return a

this is their solution:

def solve(a, d):
  i = d%len(a)
  return(a[i:]+a[:i])

is my solution really inefficient and is their solution a lot more efficient. If so can someone explain why and what their return statement actually means?

[spring jasper]

!e

[halcyon plank]

You are not allowed to use that command here. Please use the #bot-commands channel instead.

[spring jasper]

Sad

[vocal gorge]

They take two slices of the array: from element i to the end, and from the beginning to the element i, then concatenate them in that order.

And yes, your solution is very inefficient as it involves popping elements from the beginning of a list - which is O(n) for each pop, for a total of O(n^2) for your program.

[cerulean river]

Thank you for the answer.

[old rover]

by everytime you move a node forward, do you mean node = node.next?

[spring jasper]

Yes

[old rover]

so I have to set self.tail equal to something

and it can't be self.tail = node

[spring jasper]

Why cant it be

[old rover]

well it doesn't work

5--->1--->2--->3--->None
5--->1--->2--->3--->None

[spring jasper]

Show the code whenever you change it

[old rover]

def __init__(self, nodes=None):
    self.head = None
    if nodes is not None:
        node = Node(data=nodes.pop(0))
        self.head = node
        for elem in nodes:
            node.next = Node(data=elem)
            node = node.next
            self.tail = node

that just sets self.tail equal to a reference

that doesn't do anything

am confused

[vocal gorge]

are you trying to make a Linkedlist out of a linked list?

like, what can the type of nodes be?

[old rover]

strings

[vocal gorge]

strings don't have .pop(0)

[old rover]

llist = LinkedList(["1","2","3"])
llist.addBefore("5")
print(llist)

[spring jasper]

That works just fine tho

[old rover]

those are strings right?

the data those nodes contain are strings?

[vocal gorge]

ah, a list of strings

[old rover]

whoops

[spring jasper]

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

class LList:
	def __init__(self, nodes=None):
	    self.head = None
	    if nodes is not None:
	        node = Node(data=nodes.pop(0))
	        self.head = node
	        for elem in nodes:
	            node.next = Node(data=elem)
	            node = node.next
	            self.tail = node
	def __repr__(self):
		curr = self.head
		nodes = []
		while curr is not None:
			nodes.append(str(curr.data))
			curr = curr.next
		return f"<{', '.join(nodes)}>"
		
llist = LList([1,2,3,4,5])
print(llist)
print(llist.tail.data)

Gives

<1, 2, 3, 4, 5>
5

[Program finished]

Pardon the indentation, on phone

[vocal gorge]

notes:

1. you're not handling the case of nodes being empty and so not having a first element to pop
2. it doesn't sit well with me to pop the first element of - that requires rearranging the entire list. Sure, that's only done once, but consider the fact that this one pop is as expensive as the rest of your function (both the pop and the for-loop iterate over the list once)

[old rover]

not my code it's real python

but the adding at the end of the the tail is mine

[spring jasper]

And it works

[vocal gorge]

this gives me the same feeling as when I look at "best practices" solutions on codewars and see O(n^2) stuff there

[old rover]

yeah I know it's frustrating

I eventually did what nedbat told me to do and sat down and coded it without resources

I just didn't really prioritize the repr function too

print(llist.tail.data)
6

so yay that prints out a 6 meaning 6 is the data for the tail node

but it still doesn't actually show that 6 is the tail

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

  def __repr___(self):
    return self.data


class LinkedList:


  def __init__(self, nodes=None):
    self.head = None
    if nodes is not None:
        node = Node(data=nodes.pop(0))
        self.head = node
        for elem in nodes:
            node.next = Node(data=elem)
            node = node.next
            self.tail = node


  def __iter__(self):
    node = self.head
    while node is not None:
      yield node
      node = node.next
  
  def __repr__(self):
    node = self.head
    nodes = []
    while node is not None:
      nodes.append(node.data)
      node = node.next
    nodes.append("None")
    return "--->".join(nodes)

  
  def addBefore(self, data):
    node = Node(data)
    node.next = self.head
    self.head = node


  def addAfter(self, data):
    node = Node(data)
    node.next = self.tail
    self.tail = node



llist = LinkedList(["1","2","3"])
llist.addBefore("5")
print(llist)
llist.addAfter("6")
print(llist.tail.data)
print(llist)

this is the code

[spring jasper]

Your addAfter is incorrect

[vocal gorge]

note that the tail (and only the tail) always has a None .next

yet you set node as the tail... after setting its next.

[agile sundial]

i've got a coding problem (apparently asked by google), and am wondering if my solution is ideal.

We can determine how "out of order" an array A is by counting the number of inversions it has. Two elements A[i] and A[j] form an inversion if A[i] > A[j] but i < j. That is, a smaller element appears after a larger element.

Given an array, count the number of inversions it has. Do this faster than O(N^2) time.

Example:
A = [2, 4, 1, 3, 5]
ans: 3
inverted pairs: (2, 1), (4, 1), (4, 3)

my sol: https://paste.pythondiscord.com/tazocesoju.py
i think it can be faster by a constant if instead of using the insert method on the BST class, i just inserted it manually in the loop, since I had already found where the node should go. i think my solution is O(n log n) best, and O(n^2) worst.

the worst case would be a strictly descending sequence, which would make the search tree just a chain of nodes, so N^2

what could i have done better in my solution?

[agile sundial]

@old rover it's doing something like this. consider these few lines

L = LinkedList([1, 2, 3])
print(L) # 1 -> 2 -> 3 -> None
print(L.tail) # 3
L.addAfter(5)

the structure of L is now

   1 -> 2 -> 3 -> None
             ^
self.tail -> 5
``` which is not what you want

[old rover]

def addAfter(self, data):
    node = Node(data)
    self.tail = node.next
    self.tail = node

that doesn't do anything

node.next creates a reference to self.tail

[spring jasper]

No, youre reading things backwards

[old rover]

aren't you supposed to read equal signs right to left?

[spring jasper]

No, self.tail is a reference to node.next

Not the other way around

[stone herald]

not sure you will get better than O(n^2) using bubble sort or something similar

[old rover]

so you're not supposed to read equal signs right to left?

[stone herald]

You would probably have better luck using a higher level sorting algo such as heapsort or mergesort and then just counting the swaps

[spring jasper]

Why would you read assignments right to left

How would you read this

x = 5

[agile sundial]

both work, tbh, it doesn't really matter

5 is stored in x
x holds 5

[agile sundial]

the amount of swaps is not necessarily the amount of inversions though

[spring jasper]

Yea but if he's getting confused about it then i guess it matters

[old rover]

5 is assigned to the value x

so x has the value 5

[spring jasper]

So self.tail = node.next

[grizzled schooner]

ok, so in your example self.tail contains node.next

[agile sundial]

i'm not using any sorting in my solution

[old rover]

that means that there is a reference from self.tail

I was having this problem yesterday too

it's very strange

[spring jasper]

from self.tail?

[old rover]

z= 15
x= 4
z = x

z is now 4

[spring jasper]

self.tail is a reference to node.next

[old rover]

no just with assigning things with linked lists

like I did it the wrong way

I swear I understand it I just did it

[stone herald]

it would be though, merge sort specifically would necessitate counting inversions on each side then for the merge step at each recursive call. The reason it works is you are recursing down to 1v1, so the most low level merge is simply an inversion. so basically each time you compare L < R == False then you can increase the counter by one. And it would finish by big O for merge sort.

[old rover]

I don't know why I get confused with it

I got confused on this yesterday too

[spring jasper]

Just read it left to right like you read everything else

x = 3 # x points to 3
self.tail = node.next # the tail points to node.next

[agile sundial]

mergesort doesn't even swap elements. it just interleaves them, how would i count that

[stone herald]

You're not actually sorting, but you are stepping through the array and comparing each value. What I meant is the cursor movement of your algorithm is similar to bubble sort, just without actually performing swaps.

[old rover]

ok

 def addAfter(self, data):
    node = Node(data)
    node.next = self.tail
    self.tail = node

so this is the opposite of what should be happening

[agile sundial]

how is it similar to bubble sort? i do binary search for each element of the input list

[old rover]

    self.tail = node

so this should be node = self.tail

[spring jasper]

Ignoring head checks, what you need to do is point the tail.next to the new node and then move the tail to that node

[old rover]

tail.next = node

what's a head check

[spring jasper]

Checking if self.head is empty or not

[old rover]

checking if there's a head?

ok

so is what I just wrote correct?

[spring jasper]

Show us the whole function

[old rover]

def addAfter(self, data):
    node = Node(data)
    self.tail.next = node
    self.tail = node

[stone herald]

I apologize, I should be more exact in my language. I am suggesting to count when merging the two sides if the left side's first item is greater than the right sides. Doing so at each recursion and adding the values would give you the count without needing to compare every value with every other.

[spring jasper]

Does this work?

[vocal gorge]

I believe this is indeed the classic way to count inversions: take mergesort, and make it just count inversions instead of fixing them

[old rover]

yes. yes it does.

damn I was close

[spring jasper]

Alright then

[agile sundial]

i see i see, and that'd be O(n log n) average

[stone herald]

your method may actually be faster in practice, but merge sort would avoid the worst case

[agile sundial]

right

i could avoid the worst case by using one of those fancy trees that balances themselves

using mergesort is definitely easier though

[stone herald]

that's true, but that's a lot of overhead for tree generation. Honestly what you have is pretty slick. 👍

[agile sundial]

thanks for the feedback !

[old rover]

maybe I shouldn't be reading right to left with .next and .prev

It makes it harder to visualize for me

[old rover]

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

  def __repr___(self):
    return self.data


class LinkedList:


  def __init__(self, nodes=None):
    self.head = None
    if nodes is not None:
        node = Node(data=nodes.pop(0))
        self.head = node
        for elem in nodes:
            node.next = Node(data=elem)
            node = node.next
            self.tail = node


  def __iter__(self):
    node = self.head
    while node is not None:
      yield node
      node = node.next
  
  def __repr__(self):
    node = self.head
    nodes = []
    while node is not None:
      nodes.append(node.data)
      node = node.next
    nodes.append("None")
    return "--->".join(nodes)

  
  def addBefore(self, data):
    node = Node(data)
    node.next = self.head
    self.head = node


  def addAfter(self, data):
    node = Node(data)
    self.tail.next = node
    self.tail = node

so let's say I'm in an interview right

and the interviewer says can you write a function that adds a node after the tail

does that mean I still need this function?

  def __init__(self, nodes=None):
    self.head = None
    if nodes is not None:
        node = Node(data=nodes.pop(0))
        self.head = node
        for elem in nodes:
            node.next = Node(data=elem)
            node = node.next
            self.tail = node

[vocal gorge]

Most likely, you're supposed to just not mention how the list is created, etc

like, write the function:

  def addAfter(self, data):
    node = Node(data)
    self.tail.next = node
    self.tail = node

then if you're asked, write what fields do LinkedList and Node have

[spring jasper]

I think converting a python list to a linkedlist through the init is a misplay

Just initialise it as an empty linkedlist and then add stuff to it

[vocal gorge]

yeah, I personally wouldn't bother with a nontrivial init

[old rover]

ok good

[vocal gorge]

just make an extend function that accepts any iterable and adds it to the end

[old rover]

idk what an extend function is

[spring jasper]

Extend adds all the elements in another list to your current list

Basically "extending" the list by another list

[vocal gorge]

Roughly:

def extend(self, it: collections.abc.Iterable):
    """Adds all the elements in the iterable to the end of the list in the same order as they appear in the iterable"""

[spring jasper]

Cant use eval here sadly

You can test it out yourself

l = [1,2,3]
l.extend([4,5,6])
print(l)

[old rover]

def addAfter(self, data):
    node = Node(data)
    self.tail.next = node
    self.tail = node

so if I just write that function

that would answer their question right?

[spring jasper]

No, that just works with a single item

It would basically be list.append

[old rover]

"and the interviewer says can you write a function that adds a node after the tail"

that wouldn't answer their question??

[spring jasper]

Oh yea, but thats not extending

[old rover]

no

[spring jasper]

That function you posted is missing some important checks

Like whether self.head is None

I would not accept it

[old rover]

you're right

i'll fix it

[fiery cosmos]

def func1():
    print(1)
    a = func2()
    next(a)
    print(3)

    ret = next(a)   # bug here

    print(ret)

    print(5)


def func2():
    print(2)
    yield 'yield 1'
    print(4)
    return 'yield 2'

func1()

how can i get the func2 return value in func1

[latent wasp]

v

Hi, how could I do the following with sqlalchemy:

I have a database of users, a user can follow another user but it isn't necessary they get followed back. A user can create a post, the post is timestamped with an integer timestamp. How can I get the latest X posts of a user's follower list?

[lean dome]

it's raised as the value of the GeneratorExit exception

[lean dome]

You'd probably get a better answer on #databases

[lean dome]

!e ```py
def func1():
print(1)
a = func2()
next(a)
print(3)
try:
next(a)
except StopIteration as e:
print(e.value)
print(5)

def func2():
print(2)
yield 'yield 1'
print(4)
return 'return 2'

func1()

[halcyon plank]

@lean dome :white_check_mark: Your eval job has completed with return code 0.

001 | 1
002 | 2
003 | 3
004 | 4
005 | return 2
006 | 5

[knotty kiln]

Hello, every i'm making a checkerboard and I want to create a function add_100 to add 100 pawn in my checkerboard
this is my function

print("Hello World!")

def pion():
global x3,x4,y3,y4,choix
i=0
while x3<195 and y3<195:
choix.append([x3,y3,x4,y4])
i,x3,x4=i+1,x3+20,x4+20
if i == 10:
y3,y4=y3+20,y4+20
i,x3,x4=0,5,15

n = choice(choix)

can.create_oval(n[0],n[1],n[2],n[3], fill='red')

x3,y3,x4,y4=5,5,15,15
choix=[]

this function add only one pawn and I want to add 100 pawn

[flat sorrel]

You might have more luck asking in one of the general help channels. Please also provide more information about your question. (#❓｜how-to-get-help )

Also,

!code

[halcyon plank]

Here's how to format Python code on Discord:

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

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

[old rover]

what does O(n^n) even look like

does that even exist

[vocal gorge]

import itertools
def nn(n):
    """Returns all n-length tuples of elements 0...n-1."""
    return list(itertools.product(list(range(n)),repeat=n))

[old rover]

interesting

[vocal gorge]

!e

import itertools
def nn(n):
    """Returns all n-length tuples of elements 0...n-1."""
    return list(itertools.product(list(range(n)),repeat=n))
print(nn(2))

[halcyon plank]

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

[(0, 0), (0, 1), (1, 0), (1, 1)]

[vocal gorge]

example. 1 for n=1, 4 for n=2, 27 for n=3...

[old rover]

nice

nested loops are only O(N^2) when you're iterating through the same array

if you're iterating through a different data structure in the next for loop it would be like O(N*M)

[vocal gorge]

if you have reasons to believe m<=n, then that can be written as O(n^2) still 🙂

[spring jasper]

The super naive solution to twoSums, the very first leetcode problem is O(n^2)

[old rover]

"naive"?