algos-and-data-structs

[fiery cosmos]

got it

so linear and quadratic inserts are running and inserting the proper number of elements

but not the chain insert

might it have to run through a different range than tablesize?

[haughty mountain]

no

[fiery cosmos]

here is my very professional error message:
raise Exception('you dun goofed')

[haughty mountain]

if it did your exception would trigger

[fiery cosmos]

would that hit the command line

[haughty mountain]

can you share the code?

[fiery cosmos]

sure thing

[haughty mountain]

if you don't catch the exception elsewhere, your program will terminate with that message (and a bunch of information like tracebacks)

[fiery cosmos]

oh btw, the original file i was supposed to read i modified. it'd be nice to be able to read that or some test input i bake up

[haughty mountain]

do move that hashtype logic at some point 😛

[fiery cosmos]

?

[haughty mountain]

and a handful of messages down

[fiery cosmos]

like move it to the main() function?

or just like as a global looking thing somewhere

[haughty mountain]

main function

use the if to pick a function, pass that function to the hash table rather than the string

[fiery cosmos]

wat

sorry i'm a bit frazzled rn

wait a tic

i think it just worked with one of the chaining functions

lol nvm now its not even making an output

yeah so that exception is getting raised and never printed anywhere its just getting caught at the try i guess but i commented it out and can confirm the chaining insert is not functioning quite right

[haughty mountain]

why do you have a try?

[fiery cosmos]

so i'll be able to do error handling later?

🤷‍♂️ mostly bc we had one in the first program

[haughty mountain]

add it when you need to actually handle errors

[fiery cosmos]

we do have to be able to prove error handling

[haughty mountain]

the sane default is to have exceptions fail loudly

[fiery cosmos]

oh oh

i see

[haughty mountain]

if you need to catch specific exceptions for a good reason, then catch those specific exceptions

[fiery cosmos]

ok there we go

yeah it's raising that

[haughty mountain]

ok, then some logic is wrong

[fiery cosmos]

dang

maybe i wasn't overcomplicating it before

[haughty mountain]

(you were)

try printing the table after each insertion

[fiery cosmos]

its certainly possible, perhaps even probable that i was

[haughty mountain]

see if things make sense

[fiery cosmos]

ok i'll add some print statements

[haughty mountain]

you mean the code where I for sure had examples where it fails?

[fiery cosmos]

😛

should i put the print in my datum in data loop or in the chain insert function

[haughty mountain]

just print after you have called insert

[fiery cosmos]

let me make the table size smaller for readability

[haughty mountain]

maybe I should read the chained insertion code to verify you actually did the change I assumed you would do

you did not

this is wrong

self.table[p].pointer = p
p = self.stack.pop()

and I understand why you would trigger the exception with this

what do you link bucket p to?

[fiery cosmos]

is it pointing to itself perhaps

[haughty mountain]

yes

you want it pointing to the new bucket

you can just make a very safe 3 line thing

new_p = self.stack.pop()
self.table[p].pointer = new_p
p = new_p

hopefully you see why the chained assignment I did was non-obvious

[fiery cosmos]

thats like a temp variable?

[haughty mountain]

order matters a lot

yes

you could also do

self.table[p].pointer = self.stack.pop()
p = self.table[p].pointer

but it's not really better

that's what the chained assignment boils down to though

[fiery cosmos]

yeah i'm not quite sure how to interpret this

[haughty mountain]

it's this

(edited code to do pop)

[fiery cosmos]

this one is more readable for me personally

alright let's try this bad boy

[haughty mountain]

I would do either the one with new_p or the chained assignment

I don't like repeating the long table lookup

[fiery cosmos]

new_p it is

you're thinking like a software engineer and i'm thinking like a grad student 😆

[haughty mountain]

(embrace laziness)

[fiery cosmos]

well i've ID'd at least one error i'd like to correct, i'll make a note for later

for now i just want to see that all the combinations run properly

and print to output text

what time is it there

[haughty mountain]

23:17

[fiery cosmos]

not so bad.. getting kind of late

those things are actually his nostrils

looking good so far

going to try every combination

ah frick i need to get my print statements formatted properly

should be straightfoward enough

no surprise with chaining all the elements are building up toward the end of the table (we're popping new free space from end of a list)

noooooooooo

getting errors

im changing bucket size to 3 and table table size to 40, getting errors

i think i need to just keep the table size 120

anyway, thanks for your help!! @haughty mountain

https://tenor.com/view/the-office-bow-michael-scott-steve-carell-office-gif-12985913

i'll be back tomorrow to work on collision counting and prints

[haughty mountain]

smaller table sizes should work if you're modding correctly

[fiery cosmos]

uh oh

[haughty mountain]

and not inserting too many elements

[fiery cosmos]

yeah so i cranked the table size way down to 40 to try that one problem instance, however its just worded poorly, what they meant was there will still be 120 table locations but we'll be printing only 40 elements bc there are 120 input ints and buckets of size 3 so we just won't print the buckets that are == [None, None, None] (i think)

that's how i'm seeing it anyhow, i should confirm w the instructors. let me at least test a smaller table but that is large enough to fit all the elements

[haughty mountain]

or put fewer elements in a smaller table

[fiery cosmos]

yeah there's got to be a bug, it's inserting exactly the number of elements in my modulo integer value

lms

not gonna lie, sounds like a problem for future me

really weird its only doing up to number of modulo_int value of keys

[haughty mountain]

is it?

you're modding with that integer

[fiery cosmos]

i think my primary hashes should be taking self.tablesize, not modulo_int

i think i found the error

[haughty mountain]

(and again this is why having the mod be different from table_size is kinda bizarre)

[azure osprey]

the evasive fenix is here😛

[fiery cosmos]

all hail

maybe that error was why i couldn't change the table size

i'm testing every scheme over again.. we shall see

ok i see what's happening

it needs to have at least the number of buckets as elements to be inserted or else it'll error, even if there is enough room for all the items to be inserted

eg 40 buckets of size 3 should be able to fit 60 integers

but as soon as i change the table size to 59 it errors

[haughty mountain]

120

[fiery cosmos]

right i just mean this test input with n = 60 should obviously be fine

[haughty mountain]

yeah

[fiery cosmos]

so.. how can i improve this thing to run through the number of bucket slots or whatever

[haughty mountain]

the exception will trigger in that case

[haughty mountain]

wdym?

[fiery cosmos]

we don't want the number of buckets to govern the input size

[haughty mountain]

well, tough luck

[fiery cosmos]

right now it requires 1 bucket for every datum, even if the buckets have multiple slots

[haughty mountain]

wait

[fiery cosmos]

consider that this is a valid call:

and this is not:

wait wth

[haughty mountain]

59 size with 60 data and bucket size 1 is the one that should fail

[fiery cosmos]

its failing somewhere between table size 40-57

for n=60

even when buckets are of size 3

ohhh

as soon as the modulo int becomes greater than the tablesize it throws an error

[haughty mountain]

if you mod by tablesize when working with the table it won't

(and again, their modulo thing is absurd)

[fiery cosmos]

there are two hashes, primary hash is modulo tablesize, for probing, you take your primary hash out and modulo by modulo_int

[haughty mountain]

probing needs to use tablesize

for sure

because probing is working with indices

[fiery cosmos]

so which is which

re: primary vs probing hash

and modulo vs tablesize

[haughty mountain]

I wouldn't call it a probing hash

you hash to get the first bucket, then probe from that point

[fiery cosmos]

so you're saying to do a primary hash with their modulo value, then probe with mod tablesize

[haughty mountain]

their modulo has to do with their hash function

yes

[fiery cosmos]

alright ill change this

[haughty mountain]

because probing works with indices, so you need to live in the space of valid indices

I...don't need to say again how much I dislike their decision to separate the two modulos

[fiery cosmos]

hey i'm right there with you

[haughty mountain]

I've never seen a hash table not use the table size as the modulo

[fiery cosmos]

ok i think it's fixed up now

i can work on error handling tomorrow

like hash table overflows and whathaveyou

but now it's working with like bucket size 3, table size 40, modulo int 42 or 39

🙇‍♂️

[crimson steeple]

does anyone max flow

[timid kraken]

• let's say there's a sequence that is meant to be circular, i.e. an arrangement of elements is equal to its reverse permutation -> [0, 1, 2, 3] == [3, 2, 1, 0] #True
• because of its circular nature, the following are equivalent, too:

[0, 1, 2, 3] == [3, 0, 1, 2] # True
[0, 1, 2, 3] == [2, 3, 0, 1] # True
[3, 0, 1, 2] == [2, 3, 0, 1] # True
etc.```
does anyone know the algorithm for generating the remaining permutations, given an arbitrary number of elements?

to be clear, I don't want to use the built in next_permutation function and skip permutations conditionally, I just want to limit the space in which a permutation may be generated

[haughty mountain]

just index modulo len(your_list)?

[lament totem]

You can just make a rotate function right?

[haughty mountain]

!e

a = [0,1,2,3,4,5,6]
for shift in range(len(a)):
  print([a[(shift+i)%len(a)] for i in range(len(a))])

[halcyon plank]

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

001 | [0, 1, 2, 3, 4, 5, 6]
002 | [1, 2, 3, 4, 5, 6, 0]
003 | [2, 3, 4, 5, 6, 0, 1]
004 | [3, 4, 5, 6, 0, 1, 2]
005 | [4, 5, 6, 0, 1, 2, 3]
006 | [5, 6, 0, 1, 2, 3, 4]
007 | [6, 0, 1, 2, 3, 4, 5]

[haughty mountain]

yes you could

and it's very terse to write rotate in python

a = a[1:] + a[:1]

[outer kayak]

Are there any map implementations that can run binary search in keys? I'm currently trying to create:
Function that returns the [highest key under a specific number]'s value in a map.

[lament totem]

Do you have a dictionary with lists as values?

like

my_dict = {
  'A': [1, 2, 5, 7, 9],
  'B': [1, 4, 5, 6, 7]
  ...
}

@outer kayak

[agile sundial]

you probably just need a BST or BBST impl i think. python's std lib unfortunately doesn't have one

[outer kayak]

dictionary? Oh right it was called a dictionary my bad
I meant a pair from integer to a specific string
e.g. 1 -> "hello", 2 -> "bye", 4 -> "hi"

and if the input is
4 -> returns "bye" since 2 is the largest key under 4
2 -> returns "hello" since 1 is the largest key under 2

[outer kayak]

Oh okay. Should I try to implement one?

[lament totem]

Well you can only use binary search if the keys are sorted

[agile sundial]

yeah. it seems like what you need

[outer kayak]

Okay, thanks

[smoky tapir]

what is going be big oh of 10log(n)+7n+3n^2+6n^3

[fiery cosmos]

O(n^3)

take the largest exponent n term, ignore constant factors

all the other n forms are dominated by the runtime of your n^3 term, and will be "absorbed" by the big O notation

[fiery cosmos]

I was wondering if I can share a opensource project I made for dsa/leetcode preparation here.

[fiery cosmos]

i need to count both primary and secondary collisions

[hardy tapir]

Can someone please help me with a dfs-method

I'm trying to create a method that traverses a tree, picking the node that has the largest subtree (greedy algorithm) until it hits a leaf.

But i can't figure it out

[fiery cosmos]

@haughty mountain i think the insertion methods are incorrect. i think i need to try inserting at the primary hash location first, and only compute the linear probe if a collision is detected

that must have been why i had the primary hash written with the table size and not the modulo invteger

integer

which is also why i think i needed h value longer

[fiery cosmos]

which i think will coincidentally screw up the insertion locations of the loop

[bright geyser]

could u send it?

[fiery cosmos]

https://github.com/itsOwen/leetcode-tracker-helper

[agile sundial]

you know that just links to your notion right. if someone wants to make a copy they'll need to delete what you've filled in

[fiery cosmos]

that's what the template is for to duplicate, track your problems and come back to them from time to time and manage everything, Doing this helps you get better at leetcode and developing patterns for problem solving. You can always do leetcode without this if you can but this is just a management tool to keep track of everything you have done till now.

[agile sundial]

I know, I'm just saying that links to the one that you're using, so everyone will just get your progress, then have to delete it

[fiery cosmos]

oh no its not my progress its a public template that one is the duplicate one, I save my progress elsewhere, The filled in fields are just examples.

[stray oak]

I need help understanding good OOP design patterns. I understand what classes and their attributes (constructors, static functions, the self keyword), but I have trouble using classes effectively. After about 5 or so classes my program gets bloated and feels unpleasant to work on. Are there any resources?

Especially web development with django, I have no idea whats going on there.

[dense cypress]

Been learning OOP and I'm having similar problems, although I'm at the very base of it. Classes feel rigid to code and difficult to understand. Plus, I can't clearly see what they really do... are they some sort of data arranging resource? I prolly won't fully comprehend replies to your message, yet still, tag me when answering if possible, please.

[azure osprey]

@stray oak @dense cypress Everything can be functions. However once you find out how your data flows between functions its wise to create a class. Its important to think about data rather than the way it is used / implemented.

Classes are compartments (instances) which can be independent collections of data who share the same functions.

[haughty mountain]

classes should generally also be good abstractions

if you have a bunch of data and functions that handles users, maybe a UserManager class would be nice to encapsulate all that

with that the rest of the code can deal with users without needing to know the intricacies of how it's actually implemented

maybe the class needs to interface with a db to get things done, but callers don't need to know that, they just want to be able to do actions on users

[hybrid epoch]

I usually recommend this book, by the gang of four:

https://www.amazon.ca/Design-Patterns-Elements-Reusable-Object-Oriented/dp/0201633612

It dives deep into the concepts of software architecture. However it can covers a lot of breadth but serves as a good starting point. The examples are in C++, but the approach and concepts described are not language specific

[azure osprey]

I think OOP works differently across languages. A Java guy has a different outlook towards OOP than a Haskell guy

Seriously tho C++ ||OOP|| sucks ass

[haughty mountain]

it's kinda awkward wrt inheritance since you need to work with pointers all the time

but if you're not doing inheritance the object model of C++ is not terrible

[haughty mountain]

to be fair, most languages only has oop with dynamic dispatch (vtables and whatnot) while C++ also has static dispatch

[stiff plover]

so you are looking for lower and upper bounds?
You can use built-in bisect module on dict's keys

[outer kayak]

Oh thanks

[haughty mountain]

no you can't, unless they are sorted already

[stiff plover]

yes the dictionary has to be sorted by keys

[outer kayak]

(It's resolved)

thanks for replying though

[stiff plover]

!e

import bisect
a = [3, 7, 8, 9, 9, 9, 12]
print(bisect.bisect_right(a, 8))
# the difference is whether you want the left-most or right-most upper bound if there is more than one 
print(bisect.bisect_left(a, 8))```

[haughty mountain]

if you need a dynamically updated sorted thing you want something like a BBST as was discussed previously

[outer kayak]

Oh okay

[halcyon plank]

@stiff plover :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | 3
002 | 2

[stiff plover]

finally, sorry for the spam

[stray oak]

Haha I found this book in my dad's office. I'll give it a read

[cunning copper]

how does one define a bytearray with a single byte of value 0?

I need the byte array to essentially be a bool

[vocal gorge]

https://docs.python.org/3/library/stdtypes.html#bytearray

Creating a zero-filled instance with a given length: bytearray(10)
so bytearray(1) for you

[cunning copper]

Ok, that makes sense. Thanks

Another question, I have an array of lists that I need to check for a specific list. How would I go about this? I assume I do something along the lines of

if array.any([1,2,3,4]):
#blah

Sorry, I am really new to python.

I was getting an error that told me to use a.any or a.all before so I am trying to do that

[vocal gorge]

i suspect you're trying to do something like (array==[1,2,3,4]).all(axis=1).any(axis=0)

[cunning copper]

I will try that out

thanks for the help

[lean lake]

for this example. the max we have to iterate is 2n .. dropping the constant, we can conclude bigO(n) ? .. but what if A was length n and B was length m .. then bigO(n+m) ? im not sure how to handle this case

def number_in_two_arrays(A, B, num):
  arr_len = len(A)
  for i in range(arr_len):
    if A[i] == num:
      return True
  for i in range(arr_len):
    if B[i] == num:
      return True
  return False

worst case both arrays are the same lenght, so we get n+n or m+m, which is still 2n (or 2m) .. which simplifies to bigO(n) .. am i overthinking this? lol

[haughty mountain]

O(n+m) is correct

O(max(n, m)) is another way to write it

they end up being equivalent in O notation, but one tends to be more natural than the other depending on the problem

actually...this code is pretty broken

if n > m then the code will fail

[lean lake]

yeah, they provided the example, i didnt write it

[haughty mountain]

so it will either throw an error or succeed

both in O(n) :^)

m doesn't matter, as the code is written

[lean lake]

yeah, it would succeed without iterating through all of B if A<B .. or complain about index out of bound if A>B

[haughty mountain]

so O(n) because the code is bad, kinda

[lean lake]

isnt O(n+m) still just linear time tho?

should simplify to O(n) ?

i cant find much on google about n+m .. and i was told BigO questions should be asked here instead of the data science channel

[dreamy valley]

O(n + m) is linear in n, and also linear in m

O(n + m^2) would be linear in n and quadratic in m

but it depends on what you know or are willing to assume about n and m

[lean lake]

ok i was able to ask a question and get the instructor to tell me that according to question 1.3 .. the code for 1.2 should be modified to fit question 1.3 .. even tho 1.3 says "above" referring to 1.2 ..
so code for 1.3 is

def number_in_two_arrays(A, B, num):
    for i in range(len(A)):
        if A[i] == num:
            return True
    for i in range(len(B)):
        if B[i] == num:
            return True
    return False

[lean lake]

is it correct to say O(n+m)? if it's linear, shouldnt we refer to simply O(n) .. thats where im confused

[dreamy valley]

it depends on whether n and m are linearly related

the complexity of an algorithm can depend on multiple inputs, that's what n and m represent

if you assume m is constant, sure you can say it's O(n)

if you assume m and n are "about" the same magnitude, you can still say it's O(n)

but if n never grows beyond 5 and m goes to 100000000, O(n) doesn't capture anything useful about the function's behavior

loosely speaking

[lean lake]

well it would be O(m) which is still constant, it's always the biggest list that will have the most impact so yeah, idk, nested for loops is easier to understand.. when they are side by side like this, i just cant wrap my head around it

[dreamy valley]

O(m) is wrong if m is limited and n is unbounded

O(m + n) is not the same as O(m) or O(n) unless you make an assumption about the relationship between m and n

[lean lake]

im refering to specific code provided a few comments up there. n and m are len(A) and len(B)

[dreamy valley]

yes, I saw it

big O is about how the function grows as the input parameters grow without bounds

if n grows without bounds, the time it takes the function to complete will also grow unboundedly

same with m

so you can't capture that by just saying O(n) because n is only related to one of the inputs

if you suppose len(A) >= len(B) then that's one way you could flatten it

but there's nothing wrong with just quoting the complexity as O(n + m)

[chilly parrot]

Is the algorithm design manual a good book to get started with DSA?

[haughty mountain]

it depends on two variables, so O(n+m) is correct

if the code was

for i in range(len(A)):
  for j in range(len(B)):
    # do stuff
```you similarly wouldn't say O(n²) or O(m²), but O(n m)

[lean lake]

i couldnt find anything on google that would relate to that answer, it's always reduced to O(n) or O(n²) and im not sure why

[haughty mountain]

if you have two parameters you specify the complexity in two parameters

[azure osprey]

How would I convert (position, length) values into (position, delta-length) ones.

First I should sort the input values by position

However the length is completely independent from position, a value having a lower position but a higher length is possible

Dunno what to do

[fiery cosmos]

just like reformulate with the length_2 - length1 tuple?

[azure osprey]

I don't understand

[haughty mountain]

wdym by delta-length here?

[azure osprey]

difference between where last ended and where current ends

[haughty mountain]

idk why that's useful, but makes sense at least

no overlaps?

is this what you're saying?

(pos[i], pos[i] + len[i] - (pos[i-1] + len[i-1]))

[azure osprey]

wait hang on

i am creating a picture

it will make it clear

on the top left you have got (position, length) values, on the right there's midi events (delta-length) for the notes shown in bottom left

take a look at the final MidiTrackon right

this is a better image

C7 note is 84 and G6 is 79 in MIDI

@haughty mountain

[azure osprey]

anybody?

[haughty mountain]

so what you really want is the time delta between adjacent events?

in that case you could generate an on and off event for each

sort those

[azure osprey]

I want to convert the position, length repr on left to the delta length repr on right

[haughty mountain]

then take the delta

[azure osprey]

how?

how can we sort based on 2 parameters

[haughty mountain]

you don't

[azure osprey]

also note 1 can be bigger than note 2, hence note 2's off event will come earlier and that all will change deltas

[haughty mountain]

your (pos, len) generates two events

on at pos

off at pos+len

[azure osprey]

right

[haughty mountain]

then sort the events by time

[azure osprey]

i am trying to process what you mean

[azure osprey]

the pos or len?

[haughty mountain]

after generating the events there is no len

[azure osprey]

yes after both of them

[haughty mountain]

note 0, pos 0, len 2
note 1, pos 1, len 2
```into

note 0 on at 0
note 0 off at 2
note 1 on at 1
note 1 off at 3

then sort by time

[azure osprey]

so say the first thing is i get the (pos, len) values
then i create note_on and note_off events for them
sort how?

[haughty mountain]

the events have an absolute time

[azure osprey]

the time is nothing but length between adjacent events and its 192 for 3 events in my case

as all events are equidistant

the time is actually delta_length

[haughty mountain]

not in your repr on the left, right?

[azure osprey]

consider a playhead moving over the notes from left to right, it would interpret the midi messages in that order

[haughty mountain]

(wrote right, meant left, edited)

[azure osprey]

in the repr to the right, yes. that's where time is 192 its difference between the last note event and current note event length

hence the term "delta_length"

[haughty mountain]

I meant the left repr, sorry

there you have actual start times, right?

[azure osprey]

yes in left repr

[haughty mountain]

and you want to go left to right?

[azure osprey]

(pos, len) == (start, end) basically

[azure osprey]

yes convert the left repr to the right (midi) one

[haughty mountain]

ok, then what I said holds

[azure osprey]

what if there are a clusterfuck of notes

[haughty mountain]

this is a very simplified example

[azure osprey]

delta length calcs all makes it super confusive

[haughty mountain]

delta length is just time between events right?

[azure osprey]

yes but your interpretation of the right repr isn't how it is in midi

note 0 on at 0
note 0 off at 2
note 1 on at 1
note 1 off at 3

should be

note 0 on at 0
note 1 on at +1   (note 0 on + 1)
note 0 off at +1  (note 1 on + 1
note 1 off at +1  (note 0 off + 1)

[haughty mountain]

I know

you just need to sort and take differences

[azure osprey]

ok so for example i have the left repr

how do i "sort" it into the right repr

[haughty mountain]

generate on/off events with absolute time

sort events by absolute time

[azure osprey]

you mean start, end values?

[haughty mountain]

take difference

[haughty mountain]

yes

[azure osprey]

ok let me work it out

oh i was wrong about (pos, len) being (start, end)

aboslute end would be pos+len

[haughty mountain]

in my example, sort to get

note 0 on at 0
note 1 on at 1
note 0 off at 2
note 1 off at 3
```take differences in time

note 0 on at 0
note 1 on at +1
note 0 off at +1
note 1 off at +1

basically midi wants two things, on/off events and delta time, we can easily do events in absolute time, so that's the first step

then sort+diff to get delta time

[azure osprey]

step 0:

note 0 (0, 384)
note 1 (192, 384)

step 1 (events wrt absolute time):

note_on 0 (0)
note_off 0 (0+384)
note_on 1 (192)
note_off 1 (192+384)

step 2 (sort):

note_on 0 (0)
note_on 1 (192)
note_off 0 (0+384) == 384
note_off 1 (192+384) == 576

step 3 (diff):

note_on 0 (0)
note_on 1 (192-0) == 192
note_off 0 (384 - 192) == 192
note_off 1 (576 - 384) == 192

@haughty mountain thanks

gift me your brain cells 😛

[odd walrus]

I have a question about the way python compiler optomizes for recursion
https://leetcode.com/problems/binary-tree-postorder-traversal/submissions/
This Morris Traversal algorithm has a space complexity of O(1)

class Solution:
    def postorderTraversal(self, root):
        def reverse(a, b):
            if a == b: return
            prev, curr = a, a.right
            while prev != b:
                prev, curr.right, curr = curr, prev, curr.right
                
        res, node = [], TreeNode(-1, root)
        while node:
            if node.left:
                prev = node.left
                while prev.right and prev.right != node:
                    prev = prev.right
                if prev.right == node:
                    curr = prev
                    reverse(node.left, prev)
                    while curr != node.left:
                        res.append(curr.val)
                        curr = curr.right
                    res.append(curr.val)
                    reverse(prev, node.left)
                    node, prev.right = node.right, None
                else:
                    node, prev.right = node.left, node
            else:
                node = node.right
        return res

Yet this recursive solution seems to use less space

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        
        if root is None:
            return None
        
        out = []
        
        def recurse(root):
            if root is None:
                return None
            recurse(root.left)
            recurse(root.right)
            out.append(root.val)
        
        recurse(root)
            
        return out

I've noticed this trend generally for other cases when I'm using Morris rather than iterative or recursion.

And this seems to only occur when I write in Python for some reason. Does anyone have any ideas?

[fiery cosmos]

having a bug in my hashtable algo

the number of elements that get added only runs up through the modulo integer value

i also need to implement some way of counting failed inserts and do some minor error handling

i added logic for primary and secondary collisions

[haughty mountain]

you're not doing this

cool, then you literally can't insert more than modulo_int elements

like, the elements with index >= modulo_int will literally just sit there unused for the probing versions

which is insanely dumb

implement and submit versions, one with the sensible mod for probing and one terrible one with the professor quoted, and then complain how broken it is :^)

actually, one sensible way is to write it with two variables for mods

[fiery cosmos]

i was able to add the logic for primary and secondary collision counting, and make the initial insertion attempt at the primary hash location, and then go to probing

[haughty mountain]

a probing_mod and a hashing_mod

[fiery cosmos]

thats a good idea

[quaint basin]

ios minus 17 great...

[haughty mountain]

and then you can just assign the same value to both and add an angry comment 😛

[quaint basin]

that aint ios thats soi

[fiery cosmos]

dang. you're right, i'll need to do that 😢

[haughty mountain]

I think I've done similar stuff before

where the stated problem is bad, but I write a general enough good solution such that it can turn into their terrible version if needed

[fiery cosmos]

yeah but now i have to compare all the variables against one another for two diff versions, instead of just looking at how the aspects of the table change with increasing input

[haughty mountain]

I don't mean write two completely different impls

[fiery cosmos]

oh i know what you mean

and i'm going to implement and add that to my like 7-8 input arguments i'm already taking

[haughty mountain]

you'll do it just to emphasize you know what you're supposed to be doing 😛

[fiery cosmos]

and they'll have no base for what is to be expected. bc the grader is just going to come along and look at where the outputs land and mark correct if the output line is as expected

[haughty mountain]

btw, you know what I meant when I said to pull

#
        if self.hashtype == 'division':
            primary_hash = primary_div_hash
        elif self.hashtype == 'multiplication':
            primary_hash = primary_mult_hash
```out of the class?

[fiery cosmos]

not really

[haughty mountain]

so, this if can be outside the class, and it decides which of the two hash functions to use

you can then pass the function as an argument to the class

rather than having this annoying if elif in several places

[fiery cosmos]

it's only in one place now no?

[haughty mountain]

I count 3 places

[fiery cosmos]

oh

[kindred notch]

is there a formula for quadratic probing?

[fiery cosmos]

how would you modify what i've done given that i'm taking the type of hash as a string when i call the program

[fiery cosmos]

yeah its in intro to algos third edition

[fiery cosmos]

i think i see

let me try

[haughty mountain]

contrived example but

def apply(op, x, y):
  if op == 'add':
    return x + y
  if op == 'mul':
    return x * y
  ...

###

def apply(op, x, y):
  return op(x, y)

def add(x, y): return x+y
def multiply(x, y): return x+y

if op == 'add':
  apply(add, x, y)
elif op == 'mul':
  apply(multiply, x, y)

so move what is basically input handling outside the logic

and make the code more generic by taking a function

this way adding a new hashing function is trivial

just pass a new function

[fiery cosmos]

i'm not understanding

i think there is a bit too much going on in this algo and i'm struggling to comprehend everything all at once

ok i've added the primary_hash and probing_hash inputs

and i already had a primary_hash var 🤦‍♂️

alright let's test this bad boy

still need to test larger / new / diff inputs and add error handling

[opal oriole]

{
  "division": primary_div_hash,
  "multiplication": primary_mult_hash
}
``` Is another option and allows for easily adding more.

(string -> function map (with a dict))

[fiery cosmos]

hmm ok

[opal oriole]

Or you can pass the function as an argument directly, rather than looking it up as shown in the add multiply example above.

[fiery cosmos]

i won't be adding more hash methods, the issue that had come up was that there are two hashes, the primary hash and the probe compute hash, and that i wanted to be able to mix and match whether i'm doing mod (tablesize) or mod (custom modulo integer)

with the modifications i've implemented suggested by fiery, i can do such a thing. the primary hash is now a required positional argument primary_hash_int, and the probe hash integer so too, probe_hash_int

[opal oriole]

You can do mod custom modulo integer, and have it default to tablesize.

[fiery cosmos]

thats a good idea

[haughty mountain]

no, there aren't two hashes

there are two modulos

[fiery cosmos]

there are two hashes, if you check CLRS. the primary hash (what they call auxiliary hash for some reason), and the probe hash computation

they both do mod m

m could be custom mod, or tablesize, or it could be different

[haughty mountain]

I'm still iffy about calling the probing index a hash, but sure

my point was that you'll have 2+ primary hashes

[haughty mountain]

and you can push the choice of that out of your class

because having a hash table do command line input parameter handling is weird

[fiery cosmos]

that's what they wanted 🤷‍♂️

[haughty mountain]

wdym?

[fiery cosmos]

oh nvm

[haughty mountain]

you need to handle input somewhere, sure

[haughty mountain]

but inside the table is a weird place

[fiery cosmos]

no i know what you mean

honestly im trying to confer all the possible functionality first, then optimize. adding the primary collisions and printing stats is cool, but i need to make new test inputs and do error checking

eg these two things:
i need to do some error handling, for example, if one of the input integers is a letter
or someone passes a blank file

[haughty mountain]

just saying, factoring this kind of stuff out will make your life making changes to the program later on easier

e.g. when adding your own primary hash

[fiery cosmos]

i am erroring out for one of the req'd input schemes

that must be because i'm doing modulo of larger than the tablesize?

hmmm

sigh this is complicated

no i don't think my logic above is correct

[haughty mountain]

mod 41 for 40 buckets is just broken

it will not work

[fiery cosmos]

i am aware

i'm also being fed conflicting information, being told different things within a 24 hr period. not sure why i'm being misled or led astray, extremely frustrating

this is worth more than 10% of our grade

[dreamy valley]

Unclear and contradictory specifications are a hallmark of basic CS courses for reasons I don't entirely understand

[fiery cosmos]

well this is grad school and C's mean you get the boot

[dreamy valley]

of course they are also a feature of real world work

[fiery cosmos]

no room for unclearness

[dreamy valley]

then you are in some bad luck

[fiery cosmos]

yep

[dreamy valley]

best talk to the prof

[fiery cosmos]

i did yesterday, they told me to do all the things that completely break the algo

then told me something today that would mean im violating what they told me to do y'day

[dreamy valley]

have you (tactfully) pointed out any of these contradictions?

[fiery cosmos]

yes just did in an email

[dreamy valley]

It may be that you aren't understanding something

Well good luck 🤷‍♂️

[fiery cosmos]

no, i'm being told conflicting info, and/or they're doing things differently than in the book without telling us what to do differently and how

ty

[vale hill]

Hello ladies and gents, I'm new to using numpy, I would like to add a numpy array of shape (3,) to a numpy matrix of shape (3, 3)

What method would I use

Like so

[haughty mountain]

mod > buckets won't work

[vocal gorge]

You want to join two arrays along an already-existing axis, so concatenate (or a specialization for joining horizontally (along axis 1), hstack).

[vale hill]

I'm not really sure how to progress

They're both the same dimension (in one axis), which is all thats needed really

I'm trying to concatenate (1560, 20) with (1560,)

so the new shape is (1560, 21)

Not bothered if it's on the left or right of the 'matrix'

[vocal gorge]

You'll want to cast the second one to (1560,1).

[vale hill]

.reshape?

[vocal gorge]

that can be done via .reshape(-1,1) or via [:,None]

[vale hill]

Thank you

♥️

[muted oracle]

Could use a bit of assistance

I have two dataframes old and new (records)

I want to compare the two and get a list of any of the records that share the same value in three specific columns

that list would be a dataframe, but only contain the data from the old records

then I would iterate over each row in that dataframe and delete the records that match in the database

essentially I am adding data to a database from a csv while also being sure to delete old data which has a new version, determined by a match of those three specific columns

[analog owl]

is someone active? i need some help.

[worn spruce]

can anyone here help on bagel?

binary search with duplicates question

[thorny acorn]

@analog owl @worn spruce dontasktoask.com

[frozen ridge]

are hashTables and hashMaps the same thing?

[agile sundial]

pretty much

[sick crypt]

pls help

[worn spruce]

so instead of actually helping on the clearly specified problem you correct me on how to ask questions. cool ty for the help!

[vocal gorge]

pretty much, but I'd say that hash tables are the structures that power both hashmaps and hashsets (hashsets only differ in that they don't have values associated with keys)

[fiery cosmos]

do y'all use adjacency lists for graphing algos or adjacency matrices? i guess it depends on the size of the graph. eg a graph with few vertices and edges is reasonably viewed as an adjacency list. however as the number of vertices and edges grows it would become unrealistic to represent in such a way

[vocal gorge]

adjacency matrixes need V^2 space, which is kinda horrible (any graph takes as much space as a full graph). I usually immediately use adjacency lists or adjacency sets even.
(of course, there are some algorithms which need the matrix representation, which is an exception)

[fiery cosmos]

i thought one is typically more concerned with runtime reqs than space reqs? i guess in the case you might have many thousands of nodes or more this becomes an issue.

[leaden root]

    def isPalindrome(self, x: int) -> bool:
          x = str(x)
          j = len(str(x))-1
          i=0
          while(i<=j):
              if x[i] == x[j]:

                 i+=1
                 j-=1
                 print("true")
                 return True
              else:
                  print("false")
                  return False



p = palindrome()
p.isPalindrome(1000021) ```

hi guys i'am making this palindrome programme and i dont know why it's not working for this test case 1000021

it returns true as it's just comparing the last and first numbers then it returns directly true without checking the others ?

why is that

it is suppose in the 2nd iteration to figure out that x(1) != x(5) then enter the else loop and return false but it's not

am i missing anything ?

[vocal gorge]

you don't even have a loop here. it's literally just comparing the first and last elements

[haughty mountain]

even then, finding neighbors of a node is faster with adj lists

checking if two nodes are neighbors is more expensive though, not that that's a too common operation

[haughty mountain]

going through all neighbors of u is O(n) with an adj matrix and O(#neighbors(u)) for adj list

[fiery cosmos]

thanks i am learning DFS and BFS now

[haughty mountain]

DFS and BFS are identical if written iteratively

the one difference is the data structure to hold the things to do

DFS - stack
BFS - queue

("Dijkstra" - priority queue)

[leaden root]

i am incrementing and decrementing i and j

and i'am using while loop

[haughty mountain]

your loop will never loop

you return in the first iteration

[leaden root]

yeah that what i was thinking, where should i return ?

[haughty mountain]

if x[i] == x[j] do you know that it's a palindrome?

[leaden root]

it should iterate till i=j to know the answer

[haughty mountain]

right

if x[i] != x[j] do you know that it's not a palindrome?

[leaden root]

yeah

[haughty mountain]

cool, so in the != case you can return False

in the == case you just continue the loop

if the loop completes, then you can return True

[leaden root]

or i can just use a boolean variable and when it's x[i] != x[j] i assign a false to it then outside while variable i use that variable to decide what to return false or true

@haughty mountain thank's man!

[haughty mountain]

you don't need such a variable

[leaden root]

my problem is where to place the return exactly lol

[haughty mountain]

class palindrome:

    def isPalindrome(self, x: int) -> bool:
          x = str(x)
          j = len(x) - 1
          i = 0
          while i <= j:
              if x[i] != x[j]:
                  return False
              i += 1
              j -= 1
          return True

[leaden root]

ah i see now

[haughty mountain]

if you pass all the checks, you can return true

if any check fails, it's False

[leaden root]

i see i see now thank you very much

[haughty mountain]

a slightly more fun and simple solution

x = str(x)
return x == x[::-1]

[fathom forge]

You could also do it by recursion but I don’t know if that would be efficient or not

[rotund swift]

Could someone help me out with this? I'm taking a python class for school and I'm not sure what's going wrong here
(srry if this is bad, i'm sorta new to this)

I intend for it to do one or another, but when it plays out it does both.

(Triangle one, then rectangle one)
Ping me if you can help (Any and all is appreciated)

[glossy breach]

a = x or a = y

a = x or y isnt really a thing

[rotund swift]

Wdym
What i'm trying to do is make it so that when a certain option is typed, only one of those code pieces activates

Both do

[glossy breach]

I mean the part where you wrote a == "Rectangle" or "rectangle"

It should be a == "Rectangle" or a == "rectangle"

[rotund swift]

ohhhhh

Lemme test that out real quick

Tysm I had no clue what I messed up

[raven steeple]

Finally, I used the learning from leetcode tree questions like path sum , find good node in a real world project. 😊 https://github.com/Agent-Hellboy/trace-dkey

[hollow needle]

Does anybody here know Adaline algorithm i have a question about it ?

[fiery cosmos]

'''Develop an algorithm and write a python program to read the Date of Birth, if the number of
digits is not 8 then print “Cannot be processed” and terminate program. If the number of digits
is 8 and if the DOB is a lucky number, output the DOB with the message “Lucky Number.” If
the number of digits is 8 and if the DOB is not a lucky number, output the DOB with the
message “Not a Lucky Number.'''

having tuff time understanding this

[wooden bluff]

maybe the format of the input must be dd/mm/yyyy or mm/dd/yyyy

The lucky numbers are similar to the prime numbers

[warped tendon]

Is there any good course/guide that I can follow to learn ds algo the right way that you guys would recommend to a beginner? I just picked up the language, solved a very few basic leetcode questions and want to get my fundamentals strong. Would prefer if the course/material explains things in either pseudo code or python

[fiery cosmos]

see pins

[fiery cosmos]

having trouble getting my optional arguments working with argparse

i'm not using required = True for any of them, so i cannot 'omit' that for my optional one

can someone help me add logic to my hash table algo?

i want to default keys that hash to a location beyond the length of the table to instead get the index value 0 (beginning of the table)

but i already have quite a bit of other logic already there so i'm not quite sure how to work it in

nvm pretty sure i got it

[fiery cosmos]

hmm yeah I need help getting an argument to be able to be either an int or None. also i think i am mixing up optional and required positional arguments that have a default

[agile sundial]

why though, that's just asking for collisions

[quiet minnow]

Please help 🙏
Question:
What algorithm is best to use to solve these type of tasks with graphs?

[agile sundial]

where's the question

[fiery cosmos]

you are correct. the reason is bc, that's how they want us to do it. say how can i get my optional argument to be optional?

[agile sundial]

for a function?

[fiery cosmos]

i haven't used the required flag or any of my args, does it default to True?

for args into argparse

[fiery cosmos]

well both

sry not both

i think im getting optional arguments and required args with defaults mixed up. basically i want to be able to omit an argument and have it default to another

[agile sundial]

to another what

[quiet minnow]

I don't know how to type it

You get like this input:

2
6
0 1 1
0 2 2
1 3 3
2 4 1
2 5 1

every number in circle stands for oil tank

[agile sundial]

ok but what is it asking you to do

[quiet minnow]

the oil powers the lights, which are represented by dots

[fiery cosmos]

to another input argument

[quiet minnow]

1 litre of oil is required for each light one length away.

The task is to find out how many total litres are needed to run all the lights.

[agile sundial]

I'm not sure if that's possible directly with argparse, but if say the default is None, then you just set the value to what you want after parsing

[fiery cosmos]

i'm getting confused about None vs. the using typing in 'None' on the command line for that argument, or what the proper setup would be

[agile sundial]

if you set a default it becomes optional iirc

[fiery cosmos]

it might be optional to the function, but the command line is telling me its a required positional argument (argparse?)

[agile sundial]

send code? also this isn't #algos-and-data-structs

[fiery cosmos]

where should i put it? i cant do #python-discussion everything moves too fast and gets buried

TypeError: 'required' is an invalid argument for positionals

[agile sundial]

what line

[fiery cosmos]

sorry, i'm jumping around a lot. let me send the most recent code

i don't really understand how but i think its working

i'm missing the collision logic for my chaining scheme

@fiery cosmos you still face this? TypeError: 'required' is an invalid argument for positionals

[quiet minnow]

Is there anyone here who can solve a larger problem and explain the solution procedure to me?

[fiery cosmos]

no i think i got that resolved

oh wait

Right, I was coming to that.

its still in the code

i think that was handled with a flag

maybe i can just delete the required bit

arguments with flags are by default not required

i need to add logic for counting collisions as part of my chaining

crap i totally broke something today

i think just by adding these two lines:

now my linear and quadratic probing are giving me the same output

[fiery cosmos]

i need help with sockets.

[lethal gazelle]

box = {}
jars = {}
crates = {}
box['biscuit'] = 1
box['cake'] = 3
jars['jam'] = 4
crates['box'] = box
crates['jars'] = jars
print (len(crates[box]))

A. 1
B. 3
C. 4
D. Type Error

Correct answer is D. Will anyone kindly explain the train of thought behind this ??

[agile sundial]

can't hash a dict

[brisk swift]

hi

can you help me?

how to make a random with your chance. for example, 1 number will come up with a 90 percent chance and others will come up with a 5 percent chance

I use a translator so the translation may not be accurate

🙃

[haughty mountain]

!d random.choices

[halcyon plank]

random.choices

random.choices(population, weights=None, *, cum_weights=None, k=1)```
Return a *k* sized list of elements chosen from the *population* with replacement. If the *population* is empty, raises [`IndexError`](https://docs.python.org/3/library/exceptions.html#IndexError "IndexError").

If a *weights* sequence is specified, selections are made according to the relative weights. Alternatively, if a *cum\_weights* sequence is given, the selections are made according to the cumulative weights (perhaps computed using [`itertools.accumulate()`](https://docs.python.org/3/library/itertools.html#itertools.accumulate "itertools.accumulate")). For example, the relative weights `[10, 5, 30, 5]` are equivalent to the cumulative weights `[10, 15, 45, 50]`. Internally, the relative weights are converted to cumulative weights before making selections, so supplying the cumulative weights saves work.

[idle pier]

hello folks, currently doing 300. Longest Increasing Subsequence. I couldn't come up with a binary search algo so I looked up an binary search algo

def lengthOfLIS(self, nums: List[int]) -> int:
        temp = [nums[0]]
        
        for i in nums:
            x = bisect_left(temp,i)
            if x == len(temp):
                temp.append(i)
            elif temp[x] > i:
                temp[x] = i
        return len(temp)```
I understand the algo except for this particular line ` if x == len(temp):`
Its really throwing me off

[humble flower]

What are datastructures and Why are They so important?

[restive python]

I consider myself to be a savvy programmer, but when it comes to DP , im a lost cause, what should I learn about to understand videos like this one https://www.youtube.com/watch?v=cl8Kdkr4Gbg&t=30s ?

[agile sundial]

because arrays are annoying to use for a lot of problems. we make data structures so things are easier (and faster sometimes)

[lost atlas]

Okay so I am personally a C++ user. How I make a linked list/stack/queue there is making a struct of node with next, prev pointers to nodes and then making a class of linked list that has only head,tail node pointers and a bunch of functions to insert, delete.
I'd like to know how to implement that in python since there are no pointers.

[worthy escarp]

There are plenty of tutorials for how to make linked lists on the web, but if you need this for an actual project and not just practice I suggest collections.deque

[fiery cosmos]

i can't help you with the video but DP is relatively straightforward, it stores pre-computed subproblems and looks them up rather than re-computing them each time.

[restive python]

I completely get the concept, I just dont get the exeution

[fiery cosmos]

anyone can help me with the asymptotics of my program / hashtable more generally?

[fiery cosmos]

i've only ever had to use it so far for graphing algorithms, where to find the shortest path, you go and look in your DP table and select and return the shortest path given rise to by the culmination of all the shortest subpaths between each node

[restive python]

yeah thats what im trying to do rite now

[fiery cosmos]

what problem are you trying to solve

[fiery cosmos]

slash add error handling

[restive python]

get from point A to B in the shortest with the shortest amount of steps

[austere forum]

What would make a dataframe pass a dataframe to a def and that same call also pass the dataframe as a list?

It's messing up my def

I tried the help channels but nobody was on

[restive python]

by def u mean function ?

[humble flower]

what is a good project which would force me to learn datastructures and algorithms?

[fiery cosmos]

probably one of the games in a python crash course?

https://nostarch.com/pythoncrashcourse2e

[humble flower]

what is that?

[fiery cosmos]

hmm maybe that's not the best to learn DS

[stoic nexus]

So, according to leetcode, the longest substring without repeating chars in "dvdf" is 2. Maybe I'm fundamentally misunderstanding what they want, but "vdf" sure seems longer and non-repeating. I don't feel like my output is wrong for the asked question.. Is that not what a longest non-repeating substring is?

[humble flower]

yeah i was a little confused when it said "the basics of programming" lol

[fiery cosmos]

idk most people use intro to algorithms 3rd edition, so im drawing a blank wrt what project you could undertake

[humble flower]

hmmm

[fiery cosmos]

are they counting from zero?

[humble flower]

well im just looking for something to make that would teach me datastructures and algos

where could i find that?

[vocal gorge]

this? https://leetcode.com/problems/longest-substring-without-repeating-characters/

[stoic nexus]

Not according to the test cases that passed. One is even a single char, expected output is 1.

[fiery cosmos]

you cannot find something you want to make, it does not exist yet

[stoic nexus]

So modified, i'm not crazy here right? that does seem like what they're asking?

[humble flower]

i see what you did there

[stoic nexus]

https://leetcode.com/problems/longest-substring-without-repeating-characters/

[fiery cosmos]

im sure you're not crazy but i am not looking at leetcode, working on my own analysis rn

[humble flower]

leetcode isnt a project

[stoic nexus]

Sorry, is this only for projects?

[humble flower]

thats what im looking for

[fiery cosmos]

no, selon thinks you were recommending something for his question

[stoic nexus]

I'm just asking my own question 🙂

[humble flower]

oh ok im sorry

i misunderstood you

[stoic nexus]

no problemo!

[gentle cypress]

Hi I wanted to know how can I find the sum of the numbers until the imput number from the user

If user gave number 5 then I would like it to sum 1+2+3+4

but there are no restrictions so the number could even be 1mil

[stoic nexus]

Have you tried anything yet? what is your plan now? just a hint, sum(range(5)).

[gentle cypress]

I'm trying to do this in shapes not code

[gentle cypress]

but if run this on code I get no output

[stoic nexus]

print(sum(range(int(input("Enter any num: "),0)))) (print outputs the result, input gets from cli user input, substitute input with whatever input you're really using, and print with whatever output you're really using.)

Don't know which shapes you mean, but, if you're using plotly shapes, you'd need to get the user input another way, like from input() and pass it to the plotly call. Or use something like tkinter and connect it's forms to variables. I'd assume whatever it is you're using probably will require another lib, as it's likely not designed for user interaction as much as graphics.

[gentle cypress]

I think i found it

from the internet

could you explain why it does end + 1, 1

[stoic nexus]

because range doesn't go from [start, end], but [start, end), in math [] means include the given numbers too, () means don't include them. so [0,1,2) is actually[0,1]. ranges are always of the form [start, end), so to get [start, end], we do [start, end+1). So range(start, end+1, 1) just means go from the start to the end, and rather than stopping before end, stop at the end. (The last number, 1 means stepping forward 1 element each time.)

[gentle cypress]

damn

wow

okay I understand end+1 in order to reach the final number of the )

but why both end+1 and ,1 after it ?

oh wait

I got it

[stoic nexus]

So, the ,1 is the "step" of the range. basically if you do range(1,100,30) you'll get [1, 31, 61, 91], or range(0,10,2) you'll get all the evens

[gentle cypress]

yes yes

got you

[stoic nexus]

Sorry, was wrong about what it'd return xD (edited it)

[gentle cypress]

I understood it now thanks a lot! really appreciate it fam

[stoic nexus]

Np bro! keep up the grind!

[gentle cypress]

I couldn't get my head around it

I am new to that stuff hehe

[stoic nexus]

There's lots of caveats, it just takes time and experience. Like this one 🙂

[gentle cypress]

yep! totally!

[stoic nexus]

I just gotta say, I'm recently a rust convert. Rust has both inclusive ranges[,] and exclusive ranges [,) (like python's). Furthermore the syntax is awesome:
range(1, 10) becomes 1..10, and if we want range(1, 10+1, 1) we just do 1..=10 (which reads so intuitively to me)

[hybrid epoch]

I got three

[hybrid epoch]

bisect_left will return an index (or insertion point) that's equal to the length of the input list if (in this case) i is greater than the largest element in temp. Hence x == len(temp) is true. I would change x to i and i to x. It makes your code a little bit easier to read.

[fiery cosmos]

@haughty mountain i need your help if you are around at any point today

[haughty mountain]

the easier thing is just to ask the question and see

[fiery cosmos]

basically i modified the algo to compute an alternative load factor taking into consideration the case when the modulo is 113 and the tablesize is 120, it'll instead calculate the true load factor meaning keys / 113, since the other slots can never be used. now this is fine but i either screwed up my chaining load factor calculation or it never worked to being with. i imagine i just have to do keys in table / (bucketsize * tablesize)

[haughty mountain]

I think that should be correct, yes

[fiery cosmos]

i think i can just do away w the second one alltogether

no nvm

i need these to somehow all work for the cases where bucketsize is not 1 and in the event that the modulo integer is less than the tablesize, so use that to calc the load factor

[lost atlas]

||see if you can make up a formula for it :)||

[haughty mountain]

I feel you're overcomplicating it

[fiery cosmos]

can you help me find my direction? i've spent all day generating data i'm not sure i will use. i just need one insightful graph to show how the load factor and collisions change as a result of increasing input size, maybe 2 eg my scheme and the professors

oh and i need to do error handling

[haughty mountain]

why can probing_hash_int even be None here?

[fiery cosmos]

it defaults to None in the args, then if it is also none in the function it'll default to the primary hash modulo

it should be the other way around

[haughty mountain]

why don't you just assign the right thing in the constructor?

[fiery cosmos]

i should default it to tablesize, and then change to primary hash w a flag

[fiery cosmos]

wdym

[haughty mountain]

if self.probing_hash_int is None:
    self.probing_hash_int = self.primary_hash_int

[fiery cosmos]

I’ll have to check the code. I do something similar to that somewhere

[haughty mountain]

if you do that in __init__ you don't need any other checks on probing_hash_int

like the ones you have in your code above

[fiery cosmos]

Yeah so I could never figure out the difference between required positional arguments that default to None and optional arguments and ones given by flags. I was trying to sort out like what if you have two optional args and you omit one, how the program would know which optional one it was. And someone said use argparse so that’s why I went in that direction but I’m still fuzzy on all those things I mentioned above and clearly I am conflating things that needn’t be conflated

[haughty mountain]

positional optional args to functions are order dependent

if you have a bunch of values that you want to maybe provide you can use keyword arguments

[fiery cosmos]

yeah so like what if i have

reqargA reqargB redargC optionalargA optionalargB

and i call myfunct(1, 3, 5, 4)

[haughty mountain]

In [8]: def f(x=None, y=None): print(x, y)

In [9]: f(42)
42 None

In [10]: f(42, 123)
42 123

In [11]: f(x=42)
42 None

In [12]: f(y=42)
None 42

[fiery cosmos]

how could i do optional argB and not A

[haughty mountain]

like I just posted

[fiery cosmos]

ok. i think i'm just getting confused regarding arguments as args on the command line vs args to functions

what about optional command line args

btw, i never used required = True, and everything was defaulting to required. i guess required = True by defult

for command line args

[haughty mountain]

optional command line args you just don't specify on the command line

[haughty mountain]

probably not if you give a default value

[fiery cosmos]

i haven't given any of them a default, except for the optional one

[haughty mountain]

actually no

https://docs.python.org/3/library/argparse.html#required

they are optional by default

[fiery cosmos]

that's funny bc it kept telling me that one was required

and like i said none of them have required = True on

and i know it wasn't my function telling me it was missing one bc it was saying argparser

anyhow

i should have written a script to do all these combinations of tests for me, i've been doing it manually all day (i am not a smart man)

haven't figured out what to say about runtime complexity

the book describes numbers of probes required as a function of load factor

load factor being totally fricked bc of this weird deployment

[haughty mountain]

like, I can easily construct inputs that totally messes up the quadratic probe load factor

[fiery cosmos]

for which scheme

[haughty mountain]

example?

[haughty mountain]

wdym which scheme?

e.g. in the 120/120 case I can force a failed insert at load factor 1/3

40 collisions will mess you up

if the table was a power of 2 size I couldn't do that

[fiery cosmos]

oh i see. any chance you could help me implement some rudimentary error handling? doesn't have to be tonight obv

[haughty mountain]

if you have specific questions about it, ask

[fiery cosmos]

also i don't have any fullness function eyt

yet

ok

[haughty mountain]

what does fullness even mean here?

[fiery cosmos]

great question

i'll ask specific ones tomorrow

[haughty mountain]

like, for the quadratic one (because it's broken) the table can fail to insert even without being full

[fiery cosmos]

sigh

maybe i should set out to prove that and prove why the whole scheme is so broken

[haughty mountain]

!e

import argparse
parser = argparse.ArgumentParser()
parser.add_argument('--foo')
parser.parse_args(['no', 'foo', 'here'])

[halcyon plank]

@haughty mountain :x: Your 3.11 eval job has completed with return code 2.

001 | usage: -c [-h] [--foo FOO]
002 | -c: error: unrecognized arguments: no foo here

[haughty mountain]

oh, you can't take positional args as default?

boo

[fiery cosmos]

i remember we removed my try block

[haughty mountain]

!e

import argparse
parser = argparse.ArgumentParser()
parser.add_argument('--foo')
parser.parse_args([])

[halcyon plank]

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

[No output]

[haughty mountain]

see, optional by default

[fiery cosmos]

no you used the -- optional flag

i think i was going to use that try for error handling, but i'm not sure i need it like in the case that one of the keys is a letter or string, surely i'd be able to catch that somewhere and raise an error?

[haughty mountain]

well yeah, don't wrap everything in a try block...

you should try to catch errors as locally as possible

[fiery cosmos]

when reading in integers as strings like text from a file, they're always str until converted, yeah? or is 11111 known to be an int when read in?

[haughty mountain]

string

you'll need to convert it

[fiery cosmos]

ok so i could catch a failed conversion

like trying to convert 'ABC' into int

[haughty mountain]

yes, but as locally as possible

[fiery cosmos]

but then blanklines would be seen as a non-int string input..

[haughty mountain]

try:
  x = int(s)
except ValueError:
  # oh noes, not an int

[haughty mountain]

what now?

[fiery cosmos]

nvm, that impl above won't work due to the way i am reading in my values:

[haughty mountain]

do you get some terrible input format again?

[fiery cosmos]

there is an except ValueError to skip over blank lines

slash their text header

[fiery cosmos]

you know it 😂

[haughty mountain]

example of input?

[fiery cosmos]

just a text that also contains non-data integers and strings and blank spaces

the dots are continuation

[haughty mountain]

do you really have input like

one
2
3
four

6

that's lame if so

[fiery cosmos]

no. the non-data ints are the header course number

once you hit the keys its just them or blanklines

after the annoying header and minimal required input string

[haughty mountain]

why blank lines?

it's not separated cases?

[fiery cosmos]

idk i certainly didn't add them to my additional test inputs

no each time i run this, i do a command line argument and get an output, which is why i have many dozens of different cases now

[haughty mountain]

so the input genuinely has useless blank lines?

[fiery cosmos]

100%

[haughty mountain]

so what you could do is just

f.readline()  # skip header
all_strings = f.read().split()

and then parse the strings to int

[fiery cosmos]

you're saying this would enable catching strings in the input later on?

there is definitely a bug at the intersect of chaining and calculating the load factor based on the primary hash modulo

[haughty mountain]

how so?

[haughty mountain]

this gets rid of all dumb whitespace and leaves the strings

so you can convert them

[dreamy valley]

method isn't coherent: it takes two arguments, but the recursive call uses only one

it looks like you solved it for (r^2)^n and not r^(2^n) like they said

[fiery cosmos]

im getting tables with the same size, same number of keys, same everything, but different load factor

i think you were right in that this should have been two different programs 😦

[haughty mountain]

what part of it?

this will be very slow

oh wait, maybe I misread

oh that's n and not 2^n

but yeah, you want to square n times

return f(r, n-1)**2

[fiery cosmos]

for my two supplemental inputs with 108 keys

chaining

the sane method vs the profs method

[haughty mountain]

how do you keep track of the load factor?

[agile sundial]

a**2 is just the same as a * a so

[haughty mountain]

res = f(r, n-1)
return res*res

[fiery cosmos]

basically just let it default to the first assignment, if any of these if checks pass, that otherwise

[haughty mountain]

why didn't you fix the None thing?

and what is key?

well that's wrong, isn't it?

[fiery cosmos]

yeah it's only going to work for the required cases we've been given

[haughty mountain]

or wait, are you just brute force counting the number of elements?

[fiery cosmos]

it wouldn't work for bucketsize = 2

[haughty mountain]

why not just keep track of things?

[agile sundial]

^ every time something happens that adds or removes elements, modify a variable that counts the elements

[fiery cosmos]

i should. the most important part now is counting the number of comparisons needed to insert all the keys

[haughty mountain]

(also, have you heard of this nice construct called a loop?)

[fiery cosmos]

im not sure what is meant by number of comparisons.. primary collisions? primary and secondary?

[fiery cosmos]

how about this:

[haughty mountain]

closer to nice

count = 0
for bucket in hashtable.table:
    for entry in bucket:
        if entry is not None:
            count += 1

[fiery cosmos]

i need keys in there somewheres

[haughty mountain]

I renamed it

oh, right

because bucket class

yeah that

but really, just have the class keep track

[fiery cosmos]

wdy think they mean by count the number of comparisons

[haughty mountain]

and load_factor should for sure be a method of the class

[fiery cosmos]

for sure i would just need a way to keep track of if im using tablesize as mod or the insane way

bc the insane way i calculate the load factor as keys / modulo integer if modulo integer < tablesize

but then my outputs look super wrong

emailed prof about it with screenshots of output, no response

[haughty mountain]

why do you need to keep track?

it's always the probe mod, no?

[fiery cosmos]

see above: line starting bc

if you recall, re-moduloing by the primary hash modulo artificially constrains the size of the table

so, in the event that keys can never get placed into that area of the table, i calculate the load factor differently

[haughty mountain]

but it's still the probe mod

[fiery cosmos]

oh i see what you're saying

[haughty mountain]

it's just the probe mod is the same as the primary hash mod

[fiery cosmos]

i could just use the probe mod in either case

[haughty mountain]

yes, it's not a special case

[fiery cosmos]

ok i'm trying to implement load_factor method now

also why are you still awake lol

are you not in your regular timezone?

hmm

i think load factor will get complicated when i have bucketsize bigger than 1

[haughty mountain]

surely this just boils down to a special case for chaining and in all other cases
count/(bucketsize*probe_mod)

it's...1 am?

because DST ended

[fiery cosmos]

oh thats cool

[haughty mountain]

why?

[fiery cosmos]

nvm. complicated for my confused mind

hmm my scope is messed up

[haughty mountain]

edge cases tend to melt away if things are formulated properly

[fiery cosmos]

i put the count logic in main

so hashtable doesnt have access to count

[haughty mountain]

well

[haughty mountain]

hashtable can just increment a variable on insertion and decrement on deletion

[fiery cosmos]

ok im going to add += 1 to count when try_insert passes

TypeError: type method doesn't define __round__ method

print(str('Load factor: ' + str((round(hashtable.load_factor, 3)) + '\n'), file = output)) TypeError: type method doesn't define __round__ method

uhh

does load factor need a repr method?

i must have really goofed something

oh i think i was just missing a ()

like hashtable.load_factor()

ok that's working nicely

[austere forum]

hi

anyone here?

[humble flower]

What is the best coding language for algorithms?

[fiery cosmos]

What is one of your favorite algorithms?

[fiery cosmos]

Id say C

But if you end up not liking C after trying it Id try to use python

[austere forum]

hello

can someone answer a dataframe join question?

[humble flower]

But python is really good for algorithms aswell right?

I read something like that

[fiery cosmos]

yeah

[fiery cosmos]

python is slow

algos can be implemented in nearly any language, python would be a poor choice if you wanted efficiency

the good thing is the object orientation

hey how do i print a raised error to file

nvm i will ask in general

[vital scaffold]

Why is the value of nums not changing here , i am not able to understand why this error is happening.
Please Help!!

[fiery cosmos]

i am trying to add comparison logic to my algo, lmk if anyone can assist. it is a hashtable algorithm, so i take comparison to mean looking at a table slot and seeing it is full as +1 comparison. more generally i would consider it to be each time a new probe location is computed

[carmine scaffold]

Try this:

s_nums = set(nums)
return list(s_nums)

[vital scaffold]

Yes, i understand this, but i want to know why is the original list not altering ?

[vital scaffold]

Does it means that if i pass a list to a function and perform some operations on it but do not return it ,then the original list will not alter ?

[runic tinsel]

no, it's not because of return

it's because nums = means you change what nums means

a = 2
a = 3

like here, you;re saying i changed my mind, a is 3, forget that i said a is 2

[haughty mountain]

catch the error, print it to file

[runic tinsel]

so you're just saying nums is not the what i got as argument, i changed my mind

[fiery cosmos]

i got that sorted, i'm working on implementing comparisons counters. i don't have an objective what is correct for any one of the schemes though

[haughty mountain]

try:
  ...
except SomeException as e:
  print(str(e), file=your_file)

[haughty mountain]

I guess you have counters as members of the class?

[fiery cosmos]

yes i have implemented a self.comparisons attribute of the table

and right now it's running and "working", i'm just trying to confirm the logic by looking at trace files of the program

[haughty mountain]

I would flip the sides of that inequality, but that's more of a me thing. It reads easier to me that way

[fiery cosmos]

i'm considering a comparison as any failed try_insert execution, and any time a probe is recomputed

what i don't yet know is if this is a separate value than primary_collisions + secondary_collisions

[haughty mountain]

as in
if len > something computed
reads better as a sentence than
if something computed < len

what is a secondary collision here?

[fiery cosmos]

yeah thats probably a good point

secondary collision = a failed probe location insert. primary being failed initial hash insert

btw for my sanity, i'm working on the real version of the algo, and i'll do her defunct version if i get time

i did some error checking, like i won't take an inputfile with more keys than there are places to put them

[haughty mountain]

there is a term for such comparisons 😛

https://en.wikipedia.org/wiki/Yoda_conditions

[fiery cosmos]

right, i'm just so wise and philosophical that use yoga conditions instead of the normal ones

{this is sarcasm}

[haughty mountain]

how do you count multiple collisions in a row?

[fiery cosmos]

i don't know that this is a strict requirement for this algo, so i'm not too worried about that. but it is definitely a requirement to count the number of comparisons

[haughty mountain]

say I insert 3 or more elements that have hash collisions

do the later ones have many secondary collisions?

btw, have you implemented lookup and deletion?

or is that not part of the task?

[fiery cosmos]

no i think i just have to mention the asymptotic implications that chaining have on deletion, but yes, it is not a part of the task to implement these characteristics

[hybrid epoch]

This is Leetcode's fault. For some problems, Leetcode will modify your output into something that matches the required format. In this case, you're returning None. Hence Leetcode chooses the input list as your answer. I'm not really sure why or the exact details on how this is done, but it must be some internal implementation.
Try implementing the same class in a separate editor and running that. You'll get different results

[hybrid epoch]

This is False in general

[haughty mountain]

it's not leetcode's fault, it clearly specifies that the operation should be done in-place

(in multiple places in the problem statement)

[fiery cosmos]

i'm having trouble making a nice graph for this. excel just puts 1-5 at the x axis, not informative at all

the keys is irrelevant except that you can see how the comparisons begins to dwarf the number of keys in the input

[hybrid epoch]

We're saying the same thing. I'm also not saying that this is necessarily an error
OP is wondering is wondering why his input list isn't changing. To your point, the likely reason Leetcode is taking the input list as the output is because the problem specifies that the list must be modified in place. However, my previous point about them modifying the output still stands. Take a look at leetcode 22 (https://leetcode.com/problems/generate-parentheses/) for example. You can return any iterable although the type hint specifies a list of strings

[haughty mountain]

"division modulo 120"

just say "modulo 120"

I'm curious why you would want to have a bar for "keys in table" when that's on the x axis

btw, is the instruction to check those values specifically? what I would do is insert a key and note the load factor and number of comparisons

and then plot load factor on the x axis and comparisons on the y axis

so just one curve plotted

as having both load factor and number of keys is kinda pointless for this hash table, it's just a straight line

(if it was a hashtable that resizes, then that could start being interesting)

[fringe valve]

how do you make such a code text

[fiery cosmos]

ah this is a great idea, thank you

[haughty mountain]

!code this?

[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.

[fiery cosmos]

does the number of objects in an algo contribute to asymptotic complexity in any meaningful way?

the book only talks about cost of successful and unsuccessful searches, what are the asymptotics of hashtable insertions? O(1) on successful insertion for sure.

[haughty mountain]

worst case for insertion at load factor f is f*table_size (ignoring the dumb modulo)

[fiery cosmos]

oh really?

[haughty mountain]

(i.e. O(number of keys in the set))

[fiery cosmos]

big o cheatsheet says O(1) without mentioning load factor

[haughty mountain]

not in the worst case

[fiery cosmos]

yeah you're right

Hash table Type Unordered associative array Invented 1953 Time complexity in big O notation Algorithm Average Worst case Space Θ(n)[1] O(n) Search Θ(1) O(n) Insert Θ(1) O(n) Delete Θ(1) O(n)

[haughty mountain]

if you keep the load factor < some constant you'll have constant costs on average

[fiery cosmos]

yeah that's what i'm noticing. i argued that above some load factor threshold one would be better off making a second duplicate hashtable and putting key sin there, though i haven't derived an exact factor

this has been near impossible w all the prof's fuckery. so much for going to my great aunts funeral

[haughty mountain]

not duplicate, you would create a bigger table

and rehash your current values

[fiery cosmos]

ok ok

[haughty mountain]

and that's what is done in practice

[fiery cosmos]

wait do you extend the current table or make a bigger one and copy everything over

[haughty mountain]

I would say the latter

maybe there are more clever things you can do, but probably not worth thinking about now

[fiery cosmos]

is any constant time number of operations always O(1)? is O(1,000,000) O(1)?

[haughty mountain]

yes

[fiery cosmos]

ok

[formal schooner]

Hi

[fiery cosmos]

what's good

[haughty mountain]

idk why, but it reminded me of

[fiery cosmos]

lol it was a common phrase here while i was growing up, what's good means like hello what's going on

still is according to a recent AOC tweet

how is the space complexity O(n) when I have a 2D array

thats a contradiction i think

[dreamy valley]

n is the number of elements in the array

not just one dimension

[fiery cosmos]

i'm talking about a hashtable which is a list of lists

list of lists should be space complexity of n^2

oh, nvm

i figured it out, its cause i don't have an n*n array, i have like n by 1 or n by 3

[dreamy valley]

I don't know what you were referring to so I probably shouldn't have jumped to answer

[fiery cosmos]

hashtable length * bucketsize to be more specific

its ok i know

[haughty mountain]

O(number of slots)

[fiery cosmos]

precisely