algos-and-data-structs

[azure matrix]

log(n)+k where k is changes then?

[haughty mountain]

I expect log(n)*k if anything

you binary search for the end of the current value, k times

[azure matrix]

I'll DM you the code (+ anyone else that asks) if anyone wants to take a go at optimizing the real world example, but I'm more interested in the general solution so my dummy code above is probably a much better starting point.

[haughty mountain]

so just make a function that returns the value at time t (the value of the last event before t)

with caching to not recalculate stuff

and then you can binary search in t

[azure matrix]

Hm so like... Binary search on a hypothetical time, and look for the closest actual time

doing API calls if necessary?

[haughty mountain]

yes

[azure matrix]

That's pretty smart!

[haughty mountain]

a bunch of the time you'll probably end up checking against the same event, but caching solves that

if samples are evenly spread this should work fine

[azure matrix]

Yeah. I like that idea. I'll see if I can implement it on my toy example...

[haughty mountain]

if they aren't you could try to make a better guess than just splitting by 2

like if there is some sampling pattern

but getting the simple binary search in t working is the first thing to do regardless

[haughty mountain]

it's nice in that it abstracts away a very annoying part of the problem

with that it's just a sequence of binary searches, binary search for the last value_at(t) == first_value and you'll get l, r such that value_at(l) == first_value and value_at(r) != first_value

r is your new start point for the next value

[acoustic pebble]

Anyone who is willing to share Leetcode subscription?
DM me

[azure matrix]

Been playing with a tree structure that plays nicely with all of this:

    class TimeTree:
        DEPTH_FUNCTIONS = [cache(f) for f in (get_years, get_days, get_times, get_value)]

        def __init__(self, depth=0, args=()):
            self.depth = depth
            self.args = args

        @property
        def children(self):
            if self.depth == 3:
                return []
            return [TimeTree(self.depth + 1, (args,)) for args in self.DEPTH_FUNCTIONS[self.depth](*self.args)]

        @property
        def value(self):
            if self.depth != 3:
                return None
            return get_value(*self.args)

        @property
        def left(self):
            if self.depth == 3:
                return self
            return self.children[0].left

        @property
        def right(self):
            if self.depth == 3:
                return self
            return self.children[-1].right

        @property
        def middle(self):
            if self.depth == 3:
                return self
            return self.children[len(self.children) // 2].middle

Not sure if I can really use it to solve the problem, but if I initialize an empty tree and do .left, .middle, and .right, it seems to get me the nodes I'm looking for with minimal API calls

Need to be able to find the middle node between two child nodes though, that's trickier..

I tried doing an implementation that bisects using the date values but haven't had much luck yet

[gaunt bridge]

code to add data to the next empty line in a dataframe in pandas?

👆

[near gazelle]

def count(motifs):
  count = []
  for col in motifs.T:
    col = list(col)
    count.append([col.count(nuc) for nuc in 'ACGT'])
  return np.array(count).T
``````py
Motifs = np.array([list(i) for i in [
  "TCGGGGGTTTTT",
  "CCGGTGACTTAC",
  "ACGGGGATTTTC",
  "TTGGGGACTTTT",
  "ATGGGGACTTCC",
  "TCGGGGACTTCC",
  "TCGGGGATTCAT",
  "TAGGGGATTCCT",
  "TAGGGGAACTAC",
  "TCGGGTATAACC"
]])

print(count(Motifs))

Is there a more efficient/pythonic way of doing that? I feel like I shouldn't convert back and forth from lists

I'm trying to generate the second array from the first (each cell is the frequency of that character in that column... A appears in col 1 two times so it's 2 in row 1 col 1)

[haughty mountain]

use something like unix time for first and last event, find the midpoint, convert to year, day, time and search the tree for the first event <= that

[vocal gorge]

Iterating over a numpy array basically means sacrificing all of its performance advantages. Instead, you can get away with a loop over only the 4 kinds of elements. Something like:

def count(motifs):
    results = np.zeros(shape=(4,motifs.shape[1]), dtype=np.int32)
    for i, el in enumerate("ACGT"):
        results[i,:] = (Motifs==el).sum(axis=0)
    return results

getting

array([[ 2,  2,  0,  0,  0,  0,  9,  1,  1,  1,  3,  0],
       [ 1,  6,  0,  0,  0,  0,  0,  4,  1,  2,  4,  6],
       [ 0,  0, 10, 10,  9,  9,  1,  0,  0,  0,  0,  0],
       [ 7,  2,  0,  0,  1,  1,  0,  5,  8,  7,  3,  4]])

on your array, which looks right.

[haughty mountain]

@azure matrix
Ok, I ended up doing a bunch of hackery to not have to deal with weirdness with datetime (it does not like year zero), but the basic idea is the same. I create this weird new "timestamp" space of values that I can binary search (in my code here I represent the tuple as an integer in base 10000).

The code for snapping to the value before the timestamp is slower than needed and more complicated than needed (complicated in part because the api is weird). The slowness doesn't matter since the api calls are super slow in comparison.

Sadly the code is too long to post in a comment here, it would have been nice to eval it here to have the times.

https://paste.pythondiscord.com/vijuhepodo

get_changes_binary_search took 0.5648s.
Cache statistics:
get_years: CacheInfo(hits=450, misses=1, maxsize=None, currsize=1)
get_days:  CacheInfo(hits=450, misses=6, maxsize=None, currsize=6)
get_times: CacheInfo(hits=450, misses=30, maxsize=None, currsize=30)
get_value: CacheInfo(hits=394, misses=56, maxsize=None, currsize=56)

get_changes_linear_search took 2.485s.
Cache statistics:
get_years: CacheInfo(hits=0, misses=1, maxsize=None, currsize=1)
get_days:  CacheInfo(hits=0, misses=6, maxsize=None, currsize=6)
get_times: CacheInfo(hits=0, misses=30, maxsize=None, currsize=30)
get_value: CacheInfo(hits=0, misses=210, maxsize=None, currsize=210)

answer has 11 changes

the numbers used for the ranges and values are very arbitrary

It took me way too much debugging to realize my snap to nearest smaller logic was completely broken so I could fix it 😭

[tame whale]

!! Graph Theory Problem
Given a graph of nodes and edges that definitely can be traversed so that each node is visited exactly once, how can we derive the traversal path?

graph = {0: [2], 1: [3], 2: [1], 3: [0, 4], 6: [3, 7], 7: [8], 8: [9], 9: [6]}
Node = random.randint(0, len(graph) -1)
Path = [Node]
print(Path)

while len(Path) != 0:
    if len(graph[Node]) > 0:
        Path.append(Node)
        Next_Node = graph[Node].pop(0)#both remove and store in variable
        Node = Next_Node
    
print(Path)

my code so far

[tame whale]

nvm

[haughty mountain]

this is an NP hard problem

traveling salesman problem

[vocal gorge]

hamiltonian path problem, no?

[haughty mountain]

err...right

still NP hard

just unweighted TSP

[wary idol]

i forgot how to use a split(), how i put it on a list

helpo

[split sigil]

your question is off-topic for this channel but, for example, if you want to split a string "hello-spam-eggs" at each occurrence of "-", you'd do words = "hello-spam-eggs".split("-")
if you don't specify the separator (i.e the "-") in split(), the string will get split at whitespaces.

[azure matrix]

just saw this -- very cool! At work but I'll check it out more this evening. Performance looks great

[near gazelle]

Thanks a lot :)

[gilded wedge]

any idea of how to start learning python oop

[azure osprey]

@haughty mountain u there?

[haughty mountain]

maybe

[azure osprey]

ok

hang on

this is about the mutable dict view we discussed earlier https://paste.pythondiscord.com/qefiyekeza
It so happens that the first element appended (inserted at -1) always ends up with the last rootidx

its because i suspect 0 and -1 point to the same position for a list of size 1

[haughty mountain]

they do

[azure osprey]

but if i modify the logic around

def insert(self, pos: int, ev: AnyEvent):
        """Inserts :attr:`ev` at :attr:`pos` in this and all parent trees."""
        rootidx = cast(int, self.indexes[pos]) if len(self) else 0

        # Shift all root indexes after rootidx by +1 to prevent collisions
        # while sorting the entire list by root indexes before serialising.
        for ie in chain.from_iterable(self.root.dct.values()):
            if ie.r > rootidx:   # CHANGED!!!
                ie.r += 1

such that the rootidx of first element is correct, other tests of mine (that passed initially) fail.

[haughty mountain]

why do you end up with insert at -1?

[azure osprey]

that's what append does

[haughty mountain]

append is not insert at -1

[azure osprey]

and its the same result if i do self.insert(len(self), ...)

[azure osprey]

then what is it

[haughty mountain]

insert at -1 inserts before element -1

which is the last element

[azure osprey]

I tried self.insert(-1 if len(self) else len(self)) but same result, but that's what insert does within itself already

[haughty mountain]

wait, what are you trying to do there?

[azure osprey]

well you know what rootidx is right?

[haughty mountain]

roughly

[azure osprey]

well it increments by one when append happends and decrements when remove happens

[haughty mountain]

the logic in the if expression makes no sense to me though

[azure osprey]

if .... self.root.dct.values() .... that line

[haughty mountain]

this

[azure osprey]

well that was just a try

[haughty mountain]

try at what?

[azure osprey]

try so that the first element rootidx doesn't become the last as events keep on getting inserted

[haughty mountain]

you're basically written

-1 if x != 0 else 0

which just seems weird

[azure osprey]

This causes correct order of first event but fails some tests which means probably later indexes get messed up?

if ie.r > rootidx:

and this only messes up the first event rootidx

if ie.r >= rootidx:

[haughty mountain]

it should be the second one I'm pretty sure

to insert at i you need to move element i and onwards

[azure osprey]

that's what I am thinking

[haughty mountain]

what is cast?

[azure osprey]

its just finally down to -1 and 0 being the same for a single element list but i dunno how to solve it

[azure osprey]

typing.cast

[haughty mountain]

why do you need that?

missing annotations on self.indexes?

[azure osprey]

because i am returning sortedcontainers.SortedSet from self.indexes

which is an untyped library

[haughty mountain]

I can't even recall if that thing is good or terrible

I'm guessing what you would want in most languages is a BBST

[azure osprey]

well i am using ortedlist as the value of dct attribute as i don't need to sort the list each time i return it from some function

(and ordering by rootidx is the most important!) (list index is useless)

[haughty mountain]

why is this a problem again?

[azure osprey]

because when -1 is done on a single element list it is same as 0 and the logic if ie.r >= rootidx: will push it all the way to last rootidx for that reason

[haughty mountain]

what is -1 meant to do?

[azure osprey]

self.indexes[-1] will be 0 when only first element is added

and rootidx is 0 when self.indexes is empty

[haughty mountain]

why does -1 even enter the picture?

[azure osprey]

means rootidx is effectively 0 for two items, but due to shifting the earlier event gets pushed to the end

[azure osprey]

self.indexes[pos] where pos is always -1 as passed by append via self.insert(-1, ...)

[haughty mountain]

ok, what is self.insert(-1, ...) meant to do?

[azure osprey]

bruh

[haughty mountain]

because for insert on say list that's a weird operation

[azure osprey]

well what do you say how should I implement append if I choose not to use insert at all?

[haughty mountain]

!e

a = [1,2,3]
a.insert(-1, 42)
print(a)

[halcyon plank]

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

[1, 2, 42, 3]

[azure osprey]

how does it go there

[haughty mountain]

-1 is the last element

[azure osprey]

shouldn't it be [1, 2, 3, 42]

[haughty mountain]

insert before that

[azure osprey]

well how do insert after last element

[haughty mountain]

!e

a = [1,2,3]
a.insert(len(a), 42)
print(a)

[halcyon plank]

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

[1, 2, 3, 42]

[haughty mountain]

(interestingly, anything >=len(a) works, which is disturbing to me)

[azure osprey]

i did try len(self) instead of -1 and it resulted in the same error

[haughty mountain]

regardless, -1 for append is just wrong

the question is why len(self) causes issues then

[azure osprey]

wait i just tried len(self) again and all tests failed for this insert impl

    def insert(self, pos: int, ev: AnyEvent):
        """Inserts :attr:`ev` at :attr:`pos` in this and all parent trees."""
        rootidx = cast(int, self.indexes[pos]) if len(self) else 0

        # Shift all root indexes after rootidx by +1 to prevent collisions
        # while sorting the entire list by root indexes before serialising.
        for ie in chain.from_iterable(self.root.dct.values()):
            if ie.r >= rootidx:
                ie.r += 1

        self._recursive(lambda ed: ed.dct[ev.id].add(IndexedEvent(rootidx, ev)))  # type: ignore # noqa

try:
    rootidx = cast(int, self.indexes[pos])
except IndexError:
    rootidx = 0

this fails too, but not all tests

I am really at doubt how -1 works correctly now

[azure osprey]

after seeing this

[haughty mountain]

maybe you broke something else trying to fix the -1 issues

[azure osprey]

i have a null test in my tests and using -1 passes it

the null test basically parses the event structure and dumps as is

[haughty mountain]

what pos are meant to be allowed?

if >= 0 maybe assert on that

[azure osprey]

anything list can accept

[haughty mountain]

ah, so you want to accept negative indices

[azure osprey]

pos is a list-like index (relative), rootidx is a zero-based index (absolute) and self.indexes is like the glue between them

[haughty mountain]

am I dumb or is indexes basically range?

[azure osprey]

no, root indexes aren't always sequential

[haughty mountain]

you sort them though?

[azure osprey]

yes because how else will i use a "relative" index with them?

i might as well use a list or tuple since it preserves insertion order

[haughty mountain]

oh are you allowed to have gaps?

is that it?

[azure osprey]

its basically that the modifier of the EventTree uses it like a list and list is ordered

[azure osprey]

yes

[haughty mountain]

how do gaps appear?

[azure osprey]

since it uses it like a list, it has no knowledge of rootidx, it only passes a relative list-like index. the EventTree impl handles the lookup of pos to rootidx

[gilded wedge]

hey can i ask a question?

[azure osprey]

gaps in the root index rootidx, not list indexes (i.e. the one passed to pos

[gilded wedge]

[azure osprey]

a modifier (i.e. a model) of the EventTree cherry-picks the events it needs from its parent list and then uses it like it got a list (so it is freed from handling the root indexes)

[haughty mountain]

insertion shifts indices up, removal shifts down, so where do gaps appear?

[hybrid epoch]

Ask away

[azure osprey]

gaps appear in the root indexes (self.indexes) of events held by a model / modifier

[gilded wedge]

im a newbie so, how do i start learning data structures?

[azure osprey]

Model can have events cherry-picked like [(100, Event...), (200, Event...)] but it doesn't care about 100, 200 (root indexes). it just accesses the Events like a list

[haughty mountain]

wait, why are you doing -1 on indices before rootidx on removal?

shouldn't that be -1 on everything > rootidx?

[azure osprey]

yea, right

🐛 spotted

[gilded wedge]

i like the way @hybrid epoch ignored me

[hybrid epoch]

Not ignoring, looking for sources. I recommend these books:
Introduction to Algorithms, 3rd Edition
Cracking the Coding interview
https://runestone.academy/runestone/books/published/pythonds3/index.html

And checking the links in the pinned post

[gilded wedge]

thank you my lord

[wary idol]

Where is supposed to go? I thought this one was the one i had to use.

[magic sierra]

Hi, is there a way to use startswith() but ignoring spaces?

[azure osprey]

Use .strip().startswith()

[magic sierra]

I can use it for words (like, I can check for the word "hello" in "hello world"), but it doesn't work when there are no spaces (startswith returns false if I look for "hello" in "helloworld")

[azure osprey]

[magic sierra]

I meant ignoring space as word separators

[azure osprey]

It should work

[magic sierra]

It.. should? o.o

[azure osprey]

Yes

"helloworld".startswith("hello")

[magic sierra]

Maybe it's because I'm using a file?

But I also converted it to str, even if path should be a string itself

The file path, in the denugger, starts with "SOS_"

Ohh, wait

found the problem, I'm dumb 😦

ty anyway

[plain marsh]

Hope im on right place to ask this question

      con = sqlite3.connect('db.db')
      cur = con.execute("SELECT Constitution,Max_Constitution,Dexterity,Intelligence,mana,Strength,floor,class FROM Character WHERE user_id = ?", (user_id,))
      stats = cur.fetchone()
      cur = con.execute("SELECT floor_number,Floor_Boss_Damage,Floor_Boss_Health FROM Floor where floor_number = ?", (stats[5],))
      floor = cur.fetchone()
      return stats,floor```

I have this fuction 
and on another class I do 
``` def __init__(self,author) -> None:
        super().__init__()
        self.value = None
        self.author = author
        self.player,self.boss = get_stats(author)
        etc....
        self.boss[2] = self.boss[2] - self.damage

and I get problem with tuple conversion... how could I fix this?

[half lotus]

#databases would be the right place. Make sure to also include the traceback you get

[plain marsh]

understood

thank you

[simple spire]

hello everyone 🙂 noob here

a wild algorithm has appeared infront of me and i understand the solution but i don't understand the problem can anyone clarify for me?
it's apparantly called the maximum-subarray-problem

def max_sub_arr(nums):
    max_sub = nums[0]
    cur_sum = 0

    for num in nums:
        if cur_sum < 0:
            cur_sum = 0

        cur_sum += num
        max_sub = max(max_sub, cur_sum)

    return max_sub


print(max_sub_arr([-1, 2, 3, -9]) == 5)
print(max_sub_arr([-1, 2, 3, -9, 11]) == 11)

so what are we doing here exactly? we trying to find out what the largest sum if we were to add all possible subarrays?(that doesn't sound right)

[half lotus]

Looks like it's finding the largest sum of consecutive numbers in the array

[split sigil]

A help channel ( #❓｜how-to-get-help) or #python-discussion

[untold jewel]

I need to transform each element of a list-like json value to single element by duplicating the rest of the json values.

example_input={
"a":"A",
"b": [
      {"c": "C"},
      {"d":[ {"e":"E"},{"f":"F"}
              ]
      }
      ] 
"g":[
     {"h":"H","i":"I"},
     {"j":"J", "k":"K"}
     ]
}
desired_output = [
{"a":"A","c":"C","h":"H","i":"I"},
{"a":"A","e":"E","h":"H","i":"I"},
{"a":"A","f":"F","h":"H","i":"I"},
{"a":"A","c":"C","j":"J","k":"K"},
{"a":"A","e":"E","j":"J","k":"K"},
{"a":"A","f":"F","j":"J","k":"K"},
]

this is my first try where i kept a global accumulator to hold resulting jsons. This doesn't work and i understood that duplicating while tracking the index's become complicated as the granularity increases.

out = [{}]
def flatten(x, name='',i=0):
    global out
    if type(x) is dict:
        for a in x:
            flatten(x[a], name + a + '_',i)
    elif type(x) is list:

        out[i:i+1] = [out[i].copy() for __ in x ]
        for ii,xi in enumerate(x):
            new_i = ii + i
            flatten(xi, name,new_i)

    else:
        out[i][name[:-1]] = x

This is my second try. i have no idea what to do in the marked step.

def flatten(input):
    all=[]
    d = {k:input[k] for k in input if type(input[k]) is not list}
    l = {k:input[k] for k in input if type(input[k]) is list}
    if not l :
        all.append(d)
        return all

    for k in input:
        if type(input[k]) is list:
            for _ in input[k]:
                res = flatten(_)
                for __ in res:
                    __.update(d)
                all.extend(res)


    return all

please help

[little stag]

At = np.array([[5, 4, 2], [0, -3, 1], [0, 0, 45]]) #Code input
bt = np.array([5,-5,45])
x = 0


num_rows, num_cols = At.shape
num_rowsBT = np.shape(bt)[0]
results = []

unknowns = 1;

while unknowns < 4:
  a = At[(num_rows-unknowns),(num_cols-unknowns)] #Get last number from matrix At
  b = bt[(num_rowsBT-unknowns)] #Get last number from matrix bt
  b += -x 
  x = b/a # Solves X

  results.append(x)
  unknowns += 1

results.reverse()
print(results)

This returns 0.6, 2.0, 1.0 but it should return -1.0, 2.0, 1.0 what is wrong with my code? This is a backtracking function that should solve this:

[delicate ore]

quick question: why do i feel some recursion is really hard to get flatten as a single loop? But many people said any recursion can be flatten using loop. I did flat a lot recursions myself, I feel it would only be practical when we don't need store many states. So I doubt it should be a theoretical 'can be flatten' (it would be great if you guys can throw a paper with proof to me.), my reason is, e.g. TSP problem, how to use only one loop solve it. I think I can implement it, but it will be a stupid deeply nested loop. I want to know if what I am thinking is right, otherwise I will get uncomfortable

[vocal gorge]

TSP as in the travelling salesman problem? How are you solving it with recursion?

assuming you're using held-carp, the example code on wikipedia doesn't use recursion:

[ivory yacht]

The reason we know any recursive code can be converted into a looping version is that you can do it generically. Basically you emulate the function stack with a regular array/list - have a list storing like a dict holding all relevant state. Whenever you’d want to make a recursive call, append a new dict with the new parameters, continue to the start of the loop. When done, pop it off and go to the next one on the list.

If you think about how a CPU actually works, this is what it’s doing when you call a function. It stores the current instruction pointer and registers on the top of the stack, then overwrites the pointer and registers with the new function to call. Every call appends to the end of the stack. Returning involves popping from the stack, and restoring values.

[delicate ore]

I think we are not saying the same thing, i am thinking if any recursion can be flatten into a loop and how to proof it is correct, rather than, if a recursion solvable problem can be solved using another algorithm. For sure, there are a lot methods can solve TSP without touching recursion and so as many other problems

[delicate ore]

Yeah, thanks for the explanation. I think I know the basics, what i am looking for is more like a theoretical proof.

lol

[delicate ore]

Therefore, we can say if the function inside status is complicated, it will be hard to flatten the recursion into a single loop. Since there are a lot status (variables) we need to write down.

[ivory yacht]

It’s not hard, more annoying.

[delicate ore]

Yes, annoying. I say 'hard' means, it will always be easy to make an overwhelming number of status(variables) & operations to make the recording stack overcomplicated. And people make mistakes when programming. We will always forget something.

[ivory yacht]

Of course. But like it’s something you could write an algorithm to do.

[delicate ore]

If only analyzing from the perspective of computer architecture, I think i definitely get it. Like, just imagine a recursion is unwrapping on the program stack and so as what the loop is doing. I understand how it works. But I will look for some theoretical proof, that will make me feel comfortable, lol. Call it paranoid

anyways, thanks for the help! @ivory yacht

[ivory yacht]

I’m not 100% sure, but I think this is actually part of the original Church-Turing thesis proofs - demonstrating that lambda calculus (recursive functions) and Turing machines (looping code) are equivalent…

[forest tundra]

how would i make a program that locates small images from a big set of images inside a bunch of bigger images?

I'm trying to think of code that decides on pixel patterns unique to each small image so that the program doesn't have to filter through every single pixel in every single image but the logic already seems like it's gonna require stuff like this

is this normal?

[worthy escarp]

@forest tundra can you load the images to a multidimensional numpy array, and use array slicing to extract the relevant regions?

[forest tundra]

i'd need to see what that is

huh i didn't know you could do that, that's very useful thx

oh you can't

only with np array

[worthy escarp]

you need to use numpy arrays.

[forest tundra]

i see they can't be altered, though, is it still better to use them even if you have to redefine them every time you need to add an element?

[worthy escarp]

you have 6 nested for loops, python for loops are relatively slow, and you need to reduce this
numpy slicing is implemented in c

[tacit drift]

Hi! I need to perform a running time analysis on 3 different GCD algorithms.
I chose Euclid, Dijkstra and Bishop. But the last two seem like the same algorithm basically.
Any recommendation for another algorithm? Not a very complicated to understand one.

[vocal gorge]

I feel like there are very few GCD algorithms. Looks like there's the gcd(a,b) = gcd(max(a,b)%min(a,b), min(a,b)) one whatever you call it (Euclid's, usually), Lehmer's, and binary gcd.
I think binary gcd is the one that people actually use in serious implementations.

I guess you can also consider the obvious-bad-idea ones like calculating gcd by computing prime factorizations of a and b.

[red lily]

# find second largest
# element in an array
 
 
# Function to print the
# second largest elements
def print2largest(arr, arr_size):
 
    # There should be atleast
        # two elements
    if (arr_size < 2):
     
        print(" Invalid Input ")
        return
     
 
    first = second = -2147483648
    for i in range(arr_size):
     
        # If current element is
                # smaller than first
        # then update both
                # first and second
        if (arr[i] > first):
         
            second = first
            first = arr[i]
         
 
        # If arr[i] is in
                # between first and
        # second then update second
        elif (arr[i] > second and arr[i] != first):
            second = arr[i]
     
    if (second == -2147483648):
        print("There is no second largest element")
    else:
        print("The second largest element is", second)
 
 
# Driver program to test
# above function
arr = [12, 35, 1, 10, 34, 1]
n = len(arr)
 
print2largest(arr, n)
 
# This code is contributed
# by Anant Agarwal.```

[red lily]

can somebody please explain why first = second = -2147483648 is happening

like is it hard coded but why to such a small number

why not just -1

[vocal gorge]

it's -2^31, the lowest value a 32-bit signed integer can represent

of course, that's a pretty weird thing to do in python because ints are variable-width there

and also, I'd just use None as the placeholder value instead of a specific small int

Because right now, the code isn't really right - give it an array of ints all lower than this placeholder number, and it'll say there's no second largest element.

[agile sundial]

I bet that's just badly converted java code

especially since it uses indexing

[red lily]

cool thank you so much : )

[wicked zephyr]

simple question i think: i have two lists: l = list(range(226)) and k = list of specific numbers. I want to compare them and see which ones from l don't appear in k. Any ideas how to do that?

[vocal gorge]

set(l)-set(k)?

[wicked zephyr]

thank you very pretty much

[haughty mountain]

None is annoying as a placeholder where you really want -inf

it worked in python 2 :^)

>>> None < -10**100
True

[fiery cosmos]

can someone help me with my hashing algorithm assignment

kind of lost my way. i have created a classes HashTable, TableEntry, functions divmod120, hashtablecreate, getdata (for reading in input values to get hashed / stored) and a main function

i have to implement linear probing, quadratic probing, and chaining (not linked list chaining but chaining as defined by string of pointers pointing at a chain of values stored within the table

[haughty mountain]

linear probing should be easy, no?

hash to get the index you would want to put things at, if taken check the next index

and so on

for retrieval you do basically the same thing, though you need to make sure you stop when you reach keys with the wrong hash (i.e. you need to stop somewhere)

quadratic probing is basically the same, but you jump around a lot more because the next index to try is computed differently

[fiery cosmos]

i think im struggling just with data structures and the logistics of the whole thing. i have to take as input parameters the modulo divisor and bucket size. the bucket size input should modify the default table from 120 buckets of size 1 to 120/x buckets of size x

i made a table entry class so that i can do the pointers for the chaining

but each entry could honestly be a list, that's fine

just trying to get the thing to run and print a blank table for now

although, with no keys in the table entry class and nothing in the table, idk what that would look like 😂

right now i have 5 command line inputs: the input file containing the integers to be hashed, the table size, the modulo divisor, the bucket size, and the output file name

i use these inputs to create a hashtable class

kind of struggling with how to handle telling the program which hashing type i want. its taken as a string from the command line rn. but idk how to pass that to my hashtable class and tell it to use a certain function

[haughty mountain]

which hashing type as in what?

which hash function?

[fiery cosmos]

it has to handle division of different modulo int values, and i need to select and implement my own hashing scheme as well which cannot be division based

i'll get there but first trying to implement the basics

[haughty mountain]

pass a function to your hash table?

also what buckets? you don't have buckets for linear or quadratic probing

[fiery cosmos]

yeah im struggling w that part. so you are recommending passing the divmodX function when X is input on the command line for the modulo divisor and during table creation? right now when i create a hashtable instance i also pass tablesize,modulo_divisor,bucket_size,hashingtype which is default to division mod 120 rn

when those probing schemes are run, just consider each bucket to be of size 1

[haughty mountain]

you don't mean "division mod 120" right?

there is such a thing, but I don't think that's what you mean

[fiery cosmos]

no i do why

[haughty mountain]

you don't mean just x%120?

the thing I would call division modulo 120 would be discrete math stuff, modular inverses

[fiery cosmos]

it says "division modulo 120" in the assignment hashing scheme, maybe its poorly worded. im sure they just mean X % 120

[haughty mountain]

like, 1 divided by 2 mod 101 is 51

if you want to talk division modulo something

[fiery cosmos]

i'll check the textbook

[haughty mountain]

!e

half = 1 * pow(2, -1, 101) % 101
quarter = half*half % 101
print(f'{half = }')
print(f'{(half + half)%101 = }')
print(f'{quarter*4%101 = }')

[halcyon plank]

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

001 | half = 51
002 | (half + half)%101 = 1
003 | quarter*4%101 = 1

[haughty mountain]

err

I think I messed up my 1/4

no wait

it's supposed to be 1

but yeah, they for sure mean just modulo

not division modulo something

[fiery cosmos]

CLRS:
"in the division method for creating hash functions, we map a key k into one of m slots by taking the remainder of k dividied by m. that is, the hash function is
h(k) = k mod m"

so yeah. what you said

[haughty mountain]

yeah "remainder of k divided by m" is sensible to say

[fiery cosmos]

so lets see, i got stuck creating my table, got an error on trying to create a table like this:
table = [TableEntry]*str(tablesize), where TableEntry is a class. so maybe i just make each entry itself a list, to simplify things. i don't like what this would do asmyptotically however, prof said it'd be fine

[haughty mountain]

err, that thing just won't work at all

first off you should create instances of your class

[fiery cosmos]

do you ever see areas where you could simplify things but just think "yeah but thats not the way i want to do it?"

[haughty mountain]

second, that multiplication won't work as you want it to

I feel like we've covered this before

!e

a = [[]]*10
a[0].append(1)
print(a)

[halcyon plank]

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

[[1], [1], [1], [1], [1], [1], [1], [1], [1], [1]]

[haughty mountain]

the multiplication creates a bunch of references to the same object

also why are you converting tablesize to string?

[fiery cosmos]

🤦‍♂️ that should be int

[haughty mountain]

or better convert it to int when you read it

better convert it as early as possible

[fiery cosmos]

like this:

tablesizeinp = int(sys.argv[2])
```?

[haughty mountain]

I would just call it tablesize or table_size but yeah

[fiery cosmos]

so i think i have my data read in the way i want as a list, but its hard to tell when working with command line / file I/O. i think i should comment out that bit and work hard-coding things for now

[haughty mountain]

ideally just make a function that takes your command line arguments

and then you can call that with whatever

[fiery cosmos]

ahh ok

ty

[haughty mountain]

or have a function to convert the command line arguments to something more sensible and pass the more sensible things to a function

and then you can call the more sensible thing directly

[fiery cosmos]

🤔

[haughty mountain]

remember the matrix mult code?

[fiery cosmos]

so in my function commandlineargs, would i put the sys.argv arguments in the function definition or in the body

yeah of course

[haughty mountain]

in the matrix multiplication you can separate the reading of matrices from actually calling the logic

so the logic can be called directly without reading from file

for testing and development (or use as a library)

[fiery cosmos]

feeling like a name change?

i like your icon btw, i wanna copy and make the black background of space on mine to match the disc grey

[haughty mountain]

or just make things transparent

[opal oriole]

Try solving it by hand with backward substitution. Can you see the pattern? Notice the summation (i = 1 to m - 1) in the equation given in: https://en.wikipedia.org/wiki/Triangular_matrix#Forward_and_back_substitution . The sum is done at each level and the number of variables involved increases as you go up.

[fiery cosmos]

test

ahhhh awesome!

hmm

ok so what's the deal with this just creating many pointers to the same object

so if i did like

myint = 90
table = [None]*myint

then im just creating 90 pointers to the same None list?

[little stag]

Okey, I understood how to solve this problem now, but I am quite lost when applying to my code, as I should be storing my values from X and multiplying them for each value in my matrix to get my x y z soltion and the solving x = b/a with b being b - x result. Does this make sense?

[fiery cosmos]

/could recommend fixes

[opal oriole]

The equation given by Wikipedia having two subscripts m and i should be a hint that you need two loops.

Can you solve it by hand using the equation given by Wikipedia?

.latex $x_m = \frac{b_m-\sum_{i=1}^{m-1}{l_{m,i}x_i}}{l_{m,m}}$

[opal oriole]

Notice that the value of x_m depends on the previous x's (1 to m - 1), not just the previous x.

[haughty mountain]

90 references to the same None, but that's not really an issue since None is immutable

why does hash take modulo_int?

and is modulo_int just the length of the list?

[fiery cosmos]

so i can change it as necessary. has to handle different mod values eg k mod 120, k mod x, k mod y, where k is the input to be hashed and x and y are other integers

[haughty mountain]

so the normal thing to do is to compute hash(x)%len(arr)

because then you get a valid index into the array

if you mod by something smaller you're just wasteful

if by something larger you get invalid indices

and speaking of invalid indices, your loop has issues

[fiery cosmos]

so the point of all this is the combination of each scheme. so the first 3 schemes are mod 120, table size 120, bucket size 1, and probing methods linear, quadratic, and chaining

the second group of 3 is table size 120, modulo 113, bucket size 1, and linear, quadratic, and chaining probing again

[opal oriole]

The % len(arr) is basically to make the buffer circular, making invalid indices that would be out of bounds wrap around. Not sure why you would have this be a parameter.

[fiery cosmos]

the point is to see the combination of each hash along with a different collision handling scheme

[haughty mountain]

there is the hash function, which outputs a large number (in python 64 bit number), and there is modding it to get an index

the modding shouldn't really be part of the hash function I feel

and with what size array?

[fiery cosmos]

the array will always be 120 except in the modulo 41 case where it must be 40 buckets of size 3 (so len(40)) im thinking

[opal oriole]

If the mod is larger than the array size it will break. If it's smaller then that is the same as having a smaller array with mod len(arr).

[haughty mountain]

how does it make sense with 120 size and mod 101?

it's just wasteful

[fiery cosmos]

i think the point is just to learn about the various combinations and compare performance, load factor, etc

[haughty mountain]

since you won't get to the higher indices other than through collisions

[opal oriole]

If this were C and you wanted to just allocate a fixed size buffer (large) and play around with different modulos I could understand the point.

[fiery cosmos]

also to prove that we can write a hashtable and properly handle chaining and quadratic probing

[haughty mountain]

all that has little to nothing to do with your choice of mod

[fiery cosmos]

i don't get to pick the modulos, they're assigned

the thing i do get to pick eventually is my own hashing scheme

[haughty mountain]

do they genuinely say size 120 mod 101?

[fiery cosmos]

no i changed that i'll pm you

[haughty mountain]

@fiery cosmos but again, this

can you see how your thing can crash in the loop?

[fiery cosmos]

no but from running on my end i know it doesn't work

just whirrs up my fans to keep the RAM cool

[haughty mountain]

what happens if location==len(table)-1?

[fiery cosmos]

you can see what i'm attempting to do im sure

list index out of range error

[haughty mountain]

and if that space is taken

[fiery cosmos]

wait

oh you're saying it looking beyond the length of the table

so i need a wrap

[haughty mountain]

i.e. mod len(table)

which is again why I think mod anything but len(table) is bizarre

[fiery cosmos]

wait mod len table would be zero

nvm

[haughty mountain]

if you +1 after location==len(table)-1, yes

it will wrap to 0

not for quadratic probing though

[fiery cosmos]

so the input it just random integers, so no need to do any string conversions or anything

ok so to recap i need some sort of

if location>len(table):
  location = location-len(table)```

[haughty mountain]

=

or you know

% len(table)

[fiery cosmos]

lol

they're just forcing collisions, i think

slash handling how to write a program that will not look beyond the end of a hashtable?

idk

idk why every time i run this my fans whirr up 😂

[haughty mountain]

also your loop is weird anyway, why start at i=1 and why is the increment where it is?

shouldn't you first try i=1?

or better, you don't need an if like this

[fiery cosmos]

that's what i was trying to do, yeah

[haughty mountain]

you just want the first free space, no?

[fiery cosmos]

yes

for linear probing

[haughty mountain]

and...why are you writing datum everywhere in the loop

[fiery cosmos]

oh hey i did a thing

i got this:

uhh

why is there a No in there lol

[fiery cosmos]

wdym

don't call the loops weird, you'll hurt their feelings

they're doing their best

[haughty mountain]

walk through in your head what the code does if location is at the marker

[5, 2, 3, 2, None]
 ^

[fiery cosmos]

loop =
👀
👉 👈

me weird?

ok

[haughty mountain]

if datum = 42 this code should end up with

[5, 2, 42, 42, None]

which is...a thing

[fiery cosmos]

lmao ok let me look at this

[haughty mountain]

like, being able to run the steps of the code in your head is a very worthwhile skill to practice

[fiery cosmos]

im going to, stuck on the modulo bit

wolfram outputs 42 for 42 mod 120

let me just right it in python

[haughty mountain]

the modulo bit isn't interesting for the thing I showed

[haughty mountain]

yes it is

42/120 = 0 with a remainder of 42

0 + 42/120

[fiery cosmos]

ok so in your example, it'd automatically throw list index out of range error

[haughty mountain]

it won't

[fiery cosmos]

oh i thought u meant use that specific table of len 5 as if it were my hash table

ok lms

[haughty mountain]

yes, those are the keys in your table

[fiery cosmos]

oh, if you give python list[index] where it doesn't exist, will it find None? i thought it'd always throw an error, list index out of range

[haughty mountain]

wdym?

[fiery cosmos]

the only way this wouldn't error automatically would be if python interprets a list index which doesn't exist as None

[haughty mountain]

if you index a list out of range you get an error

[fiery cosmos]

right

i think we're having communication difficulties

you want me to run the code in my head on a hash table of len 120 with every entry initialized to None.. correct?

or on your example table

[haughty mountain]

on my smaller table, you are in this code, assume location=0 as I marked

[fiery cosmos]

you mean your table is a list of keys to hash

or the hashtable itself?

[haughty mountain]

hashtable itself

or at least the keys stored

[fiery cosmos]

ok ok i see how you got that output

[haughty mountain]

in short there are many things weird with that code

[fiery cosmos]

it never tries the next over slot, automatically makes i=2, writes 42 to location+i, increments i, writes 42 again to i=3 location, then terminates at None

[haughty mountain]

right

[fiery cosmos]

ok so my new code, i can step through it again with this as an example

my code is currently this:

going to try in my head first

with this as the existing table:

[5, 2, 3, 2, None]

where datum is 42 location is 0

[haughty mountain]

yeah that code is also quite broken, I can give you an example

[1, None, None, None, None]
 ^

think about the logic that function should do

find the first slot that is None, insert there

does your code do that?

[fiery cosmos]

you're making me think i don't want a while loop

[haughty mountain]

two steps, find the first slot that is Node, then insert the datum

while loop is fine

but you're making the code way more complex than needed

[haughty mountain]

can you do the first part of this?

[fiery cosmos]

if table[location] == None:
  table[location] = data```

[haughty mountain]

that doesn't do the first step I described

that doesn't find the location of the first None

[fiery cosmos]

ok so i will need like a "while table location is not None" statement

[haughty mountain]

good start

[junior warren]

hi, does anyone know what the time complexity (in Big-O) is of the exec() function?

(please ping me bc i am busy rn)

i can't really figure it out

[haughty mountain]

for what input?

[junior warren]

well i can calculate the time complexity of whatever the input is

but im wondering what the exec function actually adds

in terms of time complexity

[haughty mountain]

parsing the code I guess, but idk if that's a useful way of looking at it

[junior warren]

so like would it be O(n) where n is the amount of characters in the string)?

or does it not add any time complexity

that would be ideal lol

because if so that actually can be used to save a bunch of time complexity (avoids a for loop)

[haughty mountain]

idk what their parser does, it's at best O(n)

could be worse depending on the parser

[fiery cosmos]

i keep getting list index out of range error

oh wait it runs now

[haughty mountain]

did you finish this thought in code or not?

[fiery cosmos]

sort of, i just wrote it in notepad

[haughty mountain]

in general trying to code by accident (modifying random parts until it randomly works) is generally a way worse idea than thinking first and coding second

[fiery cosmos]

yeah youre right

i should be doing this on my whiteboard

[haughty mountain]

this still doesn't do just the first step I asked for

[fiery cosmos]

yeah so i tried going off in the direction of
for i in range (location, len(table)) to look but that'd only go through to the end of the list

and then im scanning based on i and not datum

so i thought maybe i have to combine these loops somehow

[haughty mountain]

like, the full logic for your function (ignoring computing location) only needs 4 lines, 3 of which does the first step I asked about

[fiery cosmos]

i could have another loop that once i = len(table), switch to a different range from the beginning of the list up through location

[haughty mountain]

I can give a hint, the first line is i = 0

two more to find the first non None position

[fiery cosmos]

i = 0 while table[location+i] != None: i+=1

[haughty mountain]

very close

you just need the wrapping behavior

i = (i + 1)%len(table)

that code does the first simple part I described

just find the position

and now you can do the second part

[fiery cosmos]

boy if linear probing is this complex, how am i ever gonna handle quadratic and chaining

[haughty mountain]

wdym complex?

[fiery cosmos]

i mean, its v difficult for me

for whatever reason

[haughty mountain]

i = 0
while table[location + i] != None:
  i = (i + 1)%len(table)
table[location + i] = datum

that's the whole thing

the only difference between this and quadratic probing is how i change

[fiery cosmos]

right

[haughty mountain]

like, literally that's the only change

[stray fractal]

is not None

[haughty mountain]

I mean, pedantically correct

but who cares for dumb example code

[fiery cosmos]

they function in the same way correct

[haughty mountain]

almost

is checks identity

== checks value

[agile sundial]

for None, hopefully there's no difference

[haughty mountain]

i.e. x is not None -> id(x) != id(None)

[fiery cosmos]

how did you figure out that wrapping logic

you've just seen it b4?

[haughty mountain]

for None it really should not matter, for True and False there are subtle differences between is and ==

[haughty mountain]

that's just what % does

it goes in cycles

!e

print([i%5 for i in range(13)])

[halcyon plank]

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

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

[haughty mountain]

and what you want is exactly this cyclic behavior

[fiery cosmos]

of course

[haughty mountain]

so yes, it's a matter of knowing what % is and the fact that remainders are cyclic in nature

it's quite common to consider numbers modulo something in math, big chunks of mathematics studies these things

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

group theory

pick your favorites

[fiery cosmos]

hm

[haughty mountain]

https://en.wikipedia.org/wiki/Finite_field in general I guess

but all you really need to know at the moment is modulo makes the ints go round

[fiery cosmos]

right i guess thats why its baked into the hashing function. it'd be of no use if it spit out locations that weren't going to exist your table

[haughty mountain]

you generally don't bake some random mod into your hash

for hash tables you generally compute hash(x)%mod

i.e. the hash function gives you some number, do with it whatever fits your needs

[fiery cosmos]

the weird thing is im not seeing one of my known inputs in the table anywhere

[haughty mountain]

(in sane hashtables that's hash(x)%len(table))

[haughty mountain]

you probably overwrite it somehow

[fiery cosmos]

i think the hash is h(x) = x % len(table) no?

[haughty mountain]

I guess hash(x)%len(table) is also a hash function with a smaller range

[fiery cosmos]

must be really late where you are no?

[haughty mountain]

it's a hash function

[fiery cosmos]

right

[haughty mountain]

hash functions in programming languages tends to refer to something more specific though

[fiery cosmos]

well yeah python has its own hash correct

[haughty mountain]

!e

print(hash('hi'))

[halcyon plank]

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

-850131429895669728

[haughty mountain]

right, its hash functions spits out a 64 bit value

[fiery cosmos]

right. the book covers string to integer conversion via radix or ASCI or something

so the location is computed directly from the key and the key need not be an integer

[haughty mountain]

iirc for strings python uses siphash which is a bit more fancy than just interpreting as a base whatever number

[fiery cosmos]

hm ok. hey im going to log for tonight, been feeling sick all day. thanks for help as always

ill be around to pester ppl tomorrow 😉

[hybrid epoch]

The time complexity it seems to add is O(max(globals, locals)) = O(max(argcount, kwcount))

which isn't much if you're passing small amounts of locals/globals.

see 👉 : https://github.com/python/cpython/blob/main/Python/ceval.c#L5801

[haughty mountain]

that's for sure not the whole truth

if I pass a zillion long code snippet it will run immensely slow

not proportinal to globals/locals

[agile sundial]

not even that,

while True:
   ...

[haughty mountain]

the question was about "what's the overhead of exec"

[agile sundial]

I thought it was just TC of exec

[haughty mountain]

which is a kinda odd question

that's the question that was asked, but not the question they meant 🙂

[agile sundial]

isn't overhead by definition like, constant?

[haughty mountain]

how so?

[agile sundial]

idk, ig it is an English language thing. like a constant cost

[haughty mountain]

I guess in any case the answer to the question isn't that interesting

unless you're very interested in parsers

and bytecode compilers

for any non-trivial code snippet the code will vastly dominate the runtime, compared to python preparing the code for execution

[agile sundial]

yeah

unless you make something like that thing on reddit that generates a ton of bytecode or something

[delicate ore]

anybody know any python networkx script to generate s-t flow styple graph (directed acyclic graph) ?

[winged crow]

Is is possible to report the keys in a binary min-heap in sorted order in O(n) time? I know heapsort is O(n log n), so that can't be used, but is there another way?

[jolly mortar]

if you could, wouldnt heapsort be O(n) too

[peak matrix]

Hi all,
Given a sentence like this, and i have the data structure (dictionary of lists)
{'cat': ['feline', 'kitten']}

A feline was recently spotted in the neighborhood
protecting her little kitten

How would I efficiently process these set of text to convert the word synonyms of the word cat to the word CAT such that the output is like this:

A cat was recently spotted in the neighborhood
protecting her little cat

I would also like to inquire whether my data structure is relevant and efficient for this task?
https://cs.stackexchange.com/questions/154833/best-data-structure-for-text-processing

[hybrid epoch]

Is the dictionary of lists a requirement? Are you allowed to use a dictionary of strings instead?

A dict seems fine for what you're doing right now.

!e

s = "A feline  was  recently  spotted  in  the  neighborhood protecting her little kitten".split()
d = {'feline':'cat','kitten':'cat'}
s = ' '.join([d[x] if x in d else x for x in s])
print(s)

[halcyon plank]

@hybrid epoch :white_check_mark: Your 3.11 eval job has completed with return code 0.

A cat was recently spotted in the neighborhood protecting her little cat

[vocal gorge]

what if there's more than two words all synonyms to each other? I'd probably go instead with a structure like {"feline": ["cat", "kitten"], "cat": ["cat", "kitten"]}, where the values aren't equal lists, but the very same list.

[fiery cosmos]

hey im back

[azure osprey]

What is the fastest way to parse structs?

[hybrid epoch]

This was going to be my second recommendation. I'm not sure the constraints/requirements of the problem
Implementing a trie may also do the trick 🤔
A dict of lists makes more sense here

[azure osprey]

I found struct.Struct slower than int.from_bytes why could that be?

[fiery cosmos]

can someone help me w my code? its a mess

trying to create hashtable class and im not v good w classes yet

why is my code unable to see an attribute of one of my classes:

this errors on the line w location

Exception has occurred: AttributeError 'NoneType' object has no attribute 'modulo_int'

i'm clearly making some trivial error wrt classes and their attributes

also im sure these two lines are wrong:
table = Hashtable(120,1,120) table = table.buildtable(table.tablesize)

[halcyon plank]

Hey @dire totem!

You either uploaded a .txt file or entered a message that was too long. Please use our paste bin instead.

[dire totem]

How do I form an adjacency matrix of a given edge list?
More details:

1. Each pair in the edge list contains two strings (the input form is a text document from which I was able to extract data to form a proper edge list).
2. I was able to form an adjacency list.
3. The challenge here I'm facing is how do I form a 2D matrix wherein the nodes are strings.
   (Please don't mind if I'm ignoring something trivial, I've just started learning this stuff)

[fiery cosmos]

[[A,B],[B,C],[D,C]] like this?

[dire totem]

yes

[fiery cosmos]

you just have to create and populate a list of lists

[dire totem]

Sorry I didn't understand. pls elaborate

[fiery cosmos]

the syntax is:
mylist = [[A,B],[B,C],[D,C]] mylist[0][0] is the index of A mylist[1][1] is the index of C in [B,C]

[dire totem]

yes, then?

[fiery cosmos]

so you should do like 2 adjacent lists like this:

vertices = [0,1,2,3,4,5,6,7] neighbors = [[1,4],[0,5],[3,5,6],[2,6,7],[0],[1,2,6],[2,3,5,7],[3,6]]

so neighbors[0] are the nodes connected to vertex 0, neighbors[1] are the nodes connected to vertex 1, and soforth

eh maybe not

[dire totem]

Yeah, how do I map each string to a number?

[fiery cosmos]

im a beginner as well

[dire totem]

No your answer makes sense

[fiery cosmos]

vertex_labels = ['r','s','t','u','v','w','x','y']
label_to_index_map = {label: i for i, label in enumerate(vertex_labels)}
print(label_to_index_map)

try this

change the strings to your strings

[dire totem]

yeah, thanks a lot

[fiery cosmos]

np

converting strings to numbers is pretty easy, you could use pythons inbuilt hash but its going to make a huge integer

and then your node integers would be nonsensical

the above approach is much better

[dire totem]

Also if I had to place those strings in the 2d matrix look like the following, how would I do that?

[fiery cosmos]

looks like where 1 indicates an edge between these nodes and zero indicates no edge?

[dire totem]

yes

[fiery cosmos]

to which strings are you referring

[dire totem]

A, B, C... so on

[fiery cosmos]

i mean this comment

the A B C are already there

[dire totem]

nah, the algo which you told me will just give out a matrix of 1s and 0s. I want corresponding strings at the edge of the matrix

never mind, I'll try

thanks for your help tho

[fiery cosmos]

yeah i mean, keep an eye on this channel, much better experts here that will know how to help

im waiting on said experts at the moment 😉

[fiery cosmos]

ok i got my primary hash and linear probe working:

quad probe is working

[forest tundra]

is this making proper use of them? i managed to get it working, it finds all instances of the small house in the big town, takes about 6,7 seconds

[worthy escarp]

looks good.
you may want to use for i, _ in enumerate(x) instead of for i in range(len(x)) and x.shape[1] instead of len(x[0]) but this is largely a matter of taste.
Also, all your coordinates are multiples of 32 plus some offset, so you can limit your search to possible multiples of 32 if you know the offset (in case you care about speed).
I suggest you DM me if you have want to talk further, as this is not a help channel.

[haughty mountain]

yes, the second one in particular, buildtable returns nothing

though why do you pass the size to buildtable?

the class already knows it

and also, why is the contents of buildtable not just in __init__?

that's kinda what it's for

initializing

additionally buildtable creates a local list table, which should probably be a class member

[fiery cosmos]

i tried making the table creation part of __init__ but it errored saying __init__ should not return anything

[vocal gorge]

you can limit your search to possible multiples of 32 if you know the offset
this is a great idea, but also if it doesn't work out, you can speed up what you have now by using a convolution (scipy.ndimage.correlate) instead of a double loop
EDIT: actually, it doesn't quite work does it, hmm

oh right, but you can use opencv's matchTemplate which is specifically for searching images in images

[fiery cosmos]

could you expand on this

[haughty mountain]

yes it shouldn't

[haughty mountain]

your class should probably have a self.table

and the operations on the table like insertions should be part of the class

[fiery cosmos]

honestly i got away from making table classes bc im very not skilled at using classes and i couldnt figure it out

[haughty mountain]

and put the initialization there as well

the stuff that was in buildtable

[fiery cosmos]

ok its running but now when i want the table i have to do myclassinstance.table , i guess that's normal

how should i handle hashtype like with a string input?

definitely want to have linear probing run by default

hmm

my i isn't working properly with the pseudocode i converted from the book

i should run 0 - m-1, where m is tablesize

or did they just mean it should fall somewhere in that range

how can i work these into the existing architecture

they don't use i as the probe, i is an input into the linear probe function

i'm going to have to change the table initialization based on collision resolution

that way if im doing collision resolution by chaining the table can be a list of lists, where each zeroth index is a key and each 1st index is a pointer to another array index

also need to work in bucket size into the fold somehow

[haughty mountain]

why do you need the table outside the class?

why should the user need to know about how you implement the hash table internally?

you would provide functions to operate on the hash table

insert, remove, ...

as part of the class

[fiery cosmos]

idk what im doing. there is probably some better way of doing this that i am not aware of. also i just realized something, as long as i always make the table a list of lists of length bucketsize + 1, i'll always have an additional slot to store a pointer for the chaining option

this is all going to be run from the command line with a single line and like 5 arguments

the end user won't see much?

[haughty mountain]

the point of a class is to store some data and provide ways to operate on that data

[fiery cosmos]

ok i can write deletion and addition functions, thats fine

deletion will get complicated with chaining

[haughty mountain]

as part of the class

[fiery cosmos]

right

right now im just trying to work in the pseudocode functions i converted from the book into my existing code

i'm still fuzzy on the i bit

should i make the hash functions part of the class as well?

[haughty mountain]

if you have that, along with some lookup function, the user of the class shouldn't need to touch the internal table in the class

[fiery cosmos]

by touching the internal table you mean the use of .table

[haughty mountain]

the hash functions could be separate

[fiery cosmos]

?

[haughty mountain]

yes

[fiery cosmos]

ok

[haughty mountain]

it's part of the internal representation, the user shouldn't need to touch it

in fact in other languages you would make it so that the user can't touch it

[fiery cosmos]

so you're saying that the way it's written now, if i gave the end user methods to operate on the data in the class, they'd have to type mytable.table to do so?

from command line

i mean

[haughty mountain]

wdym?

if you add methods to your class the user of the class won't ever need to say hashtable_instance.table

[fiery cosmos]

i mean, outside of looking under the hood to see what's happening, nobody is going to be modifying this code. they'll just run it with a single command line call with a set of arguments

so unless you're saying they'd need to type something like that as a command line argument, i'm willing to overlook that

which, idk if they would have to, say if i write inbuilt class methods for deleting and inserting elements into the table, which can be used from the command line

[haughty mountain]

why not just design the class in a sensible way?

so that the class has all the functionality a hash table needs

[fiery cosmos]

i will im just trying to understand each side of the coin wrt what a user might need to type in cmd vs what is written in python

[haughty mountain]

when I say user of the class I mean the code that instantiates and uses the class

[fiery cosmos]

oh. ok

what do you think of the idea that the hashtable is a list of lists of size bucketsize+1

so i have extra storage for chaining pointer

[haughty mountain]

or a list of some entry class

that's probably cleaner

[fiery cosmos]

hmm right

how about this:

also then when the bucketsize is 3, i'll need 3 of these to be in the same addressable location

so maybe it'll be a list of length 3 holding these, in slot 0 of the table, for instance

there are a lot of combinations involved in this deployment

[haughty mountain]

huh? no

you only need one pointer per bucket right?

[fiery cosmos]

or i could make key = list of length bucketsize?

[haughty mountain]

right

and maybe the name should be something with Bucket

rather than Entry, I guess

[fiery cosmos]

the key name?

oh ok

[haughty mountain]

the class name

[fiery cosmos]

right

this is a separate class, how do i give my bucket class access to bucketsize

which is an attr of hashtable class

hmm i need to modify my Hashtable class

[haughty mountain]

Like the point of classes is to abstract something away, here the user has no need to look at the internal n to make use of the class. They can just call the method and the class does its thing

class Counter:
  def __init__(self):
    self.n = 0
  def get_next(self):
    ret = self.n
    self.n += 1
    return ret

that's what I mean when I say the user of the class shouldn't need to touch the internals

[fiery cosmos]

hmm ok i see

[haughty mountain]

if you surface the operations you can hide the internals, e.g. a stack or queue can expose push/pop methods and that's more or less all you need

[fiery cosmos]

so i've seen when trying to make a default for a required positional argument that python gets angry when you make a default for an argument before another required positional argument, what is the workaround

eg:

[haughty mountain]

you can pass bucketsize when you create the bucket instance, and it can use it to create the list

there is no workaround for positional arguments

optional args go last for positional arguments

[fiery cosmos]

oh you're required argument cannot have a default

duh

ok ok so getting back to bucket instance, now i need that to be instantiated sort of like inside of my hashtable class, so how might i handle that

[haughty mountain]

what's the problem?

feels like that should go in the __init__

[fiery cosmos]

so i'll call an instance of bucket within the hashtable __init__

?

cause rn it doesn't exist and im trying to use its attributes which fails

for obvious reasons

[haughty mountain]

class Bucket:
  ...
class Table:
  def __init__(self):
    i_has_a = Bucket()
    i_has_many = [Bucket() for i in range(5)]

[fiery cosmos]

also the way i am reading in the data, i don't have the keys yet ready to assign to bucket instances

[haughty mountain]

wdym?

aren't you supposed to insert the values?

[fiery cosmos]

ok so default bucket's key to None

[haughty mountain]

right

your hash table starts empty

[fiery cosmos]

i notice that you don't have any required inputs when defining classes, should i be doing the same?

rn i have all sorts of required inputs

[haughty mountain]

no, I'm just making basic examples

[fiery cosmos]

ok

[haughty mountain]

you'll want to pass the needed arguments that the class needs

[fiery cosmos]

i'm struggling with modifying the bucket instance to default to [None] and then modifying that times bucketsize in my Hashtable instantiation

[haughty mountain]

pass bucketsize to Bucket and then have Bucket create the list it needs

[fiery cosmos]

oh right, bc these will be inputs from a user

rn bucketsize only exists after i pass it in as an argument to my hashtable instance

[haughty mountain]

class Bucket:
  def __init__(self, bucket_size):
    self.entries = [None]*bucket_size

[fiery cosmos]

then i have to pass it again when i create the instance inside of hashtable instantiation

[haughty mountain]

wdym pass it again?

[fiery cosmos]

if it's a required positional argument

[haughty mountain]

class Table:
  def __init__(self, table_size, bucket_size):
    self.table = [Bucket(bucket_size) for _ in range(table_size)]
    ...

[fiery cosmos]

ok now i just need to learn how to modify the keys of the buckets of the table

guess i should add bucketsize

as an attribute

here is how i was writing to the table:

so print statement confirms that bucket.keys looks the way i want

including when bucketsize is modified

i guess i thought each bucket would have to be instantiated first? how are these named?

i guess they aren't they're just all objects of class bucket with attributes awaiting modification

[halcyon plank]

Hey @fiery cosmos!

You either uploaded a .txt file or entered a message that was too long. Please use our paste bin instead.

[fiery cosmos]

over and over

so i guess i need a string representation of my bucket

return self.__repr__() didn't help

might need a string rep of hashtable class

[fluid gate]

anyone have any suggestions for good cheat sheets to have visible during an interview? something with a bunch of common libraries and stuff

[haughty mountain]

why do you need to pass keys or pointer to Bucket?

will you ever need them to be anything other than None?

[fiery cosmos]

huh? the keys are the values to be stored themselves

i'm going to go and look at a slot in my table containing a bucket and write the input integer to that location in bucket.key

h(key) is the storage location

[haughty mountain]

right, but why would the initializer of Bucket ever need to be passes keys or pointer that aren't None?

you're only ever going to create empty Buckets

[fiery cosmos]

hmm ok

[haughty mountain]

and you'll fill them later

[fiery cosmos]

so you're saying i can modify bucket.keys after the fact

ok

[haughty mountain]

that's kind of the point, no?

to put stuff in the bucket

[fiery cosmos]

i guess i am operating from the mindset that i need to first have stuff before i can place in bucket

which doesn't seem to be necessary in programming

or, rather it is, but we're just building out the bucket first

[haughty mountain]

we're just building the structure first

[fiery cosmos]

right

[haughty mountain]

ok, this is exactly the kind of thing that should go in the class

[fiery cosmos]

with a buildtable method

or similar

[haughty mountain]

for datum in data:
  mytable.insert(datum)

no

have a method for inserting one element

[fiery cosmos]

is this separate from reading in the input file? my required input

wait how do i handle attributes i want a class to have without requiring them as arguments

[haughty mountain]

let's step back, what kind of operations should a hash table support?

[fiery cosmos]

insert, delete, lookup(search)

[haughty mountain]

cool, let those be methods of your class

[haughty mountain]

then you can write this

nice and simple

[fiery cosmos]

what about this modification you recommended like not having bucket take the keys or pointers arguments in its __init__

what if i still want a class to have those attributes

and default them to none

i just do self.myattribute = None?

[haughty mountain]

yeah?

if you want to have that thing be None, just set it to None

or whatever value it should be

[fiery cosmos]

i sort of naively thought the attributes had to correspond to input arguments

[haughty mountain]

not at all

[fiery cosmos]

does my insert method need self before other arguments

[haughty mountain]

the first argument will always be the class instance

and you normally call that self

[fiery cosmos]

in case anyone is learning along w me

[haughty mountain]

mytable = Table()

# These two are the same
mytable.insert(42)
Table.insert(mytable, 42)

the form where you call it through the instance is just syntactic sugar

[fiery cosmos]

ok i'm still stuck on this whole i business. let me check the book

[haughty mountain]

also why are you having this extra if?

didn't we arrive at a short 4 line thing yesterday?

[fiery cosmos]

linear probing:
given an ordinary hash function h' : U -> {0, 1, .. m-1}, which we refer to as an auxiliary hash function, the method of linear probing uses the hash function
h(k,i) = (h'(k)+i) mod m for i = 0, 1, ... m-1

so my ordinary / auxiliary hash function is this:
def primary_hash(key): return key % tablesize

linear function:
def linear_probe(key,i): return (primary_hash(key)+i) % tablesize

[fiery cosmos]

lms

[fiery cosmos]

you mean this

[haughty mountain]

look at your code, does the if mytable.table... do anything useful?

[fiery cosmos]

i guess the operation should be, write to a location by default, after first checking that you're not writing to a location that already has data

as in the while check

so no

it's unnecessary

[haughty mountain]

find the first free spot, then put the element there

the loop you have there does that

there is no special case if the location bucket is free

so yeah, you can just remove the if and just keep the loop and assignment

with well designed code often the special cases just go away

like in this case

[fiery cosmos]

you should see all these cases exactly what you're talking about in CLRS. where instead of defaulting to else they do elseif (the other condition that we know must exist anyway, by default)

anyhow

they write it out explicitly. i guess for learning but then you have people learning how to write redundant unnecessary code

so rn i need to see how all these puzzle pieces fit together, and also how to make a method of def tableinsert

so far i just have it taking a key as input

so next step is hashing to determine insertion location

weird that other methods do not have access to things made in the __init__ function

like i'm trying to use modulo_int and it cannot see it, unless maybe i use self.modulo_int?

if you're curious, there are already well made functions on how to do this distributed for free

published this year with CLRS 4th edition under MIT license

oh boy what on earth is lambda

`A lambda function is a small anonymous function.

A lambda function can take any number of arguments, but can only have one expression.`

[haughty mountain]

yes

[fiery cosmos]

ah crap hash is already used in python huh

[haughty mountain]

it is

[fiery cosmos]

as in i cannot do def hash

i'll just call it auxhash

like the book

[haughty mountain]

you can if you want to

[fiery cosmos]

then which one does it do when i hash stuff then tho

[haughty mountain]

though it's a similarly bad idea as def int

[fiery cosmos]

lol ok

[haughty mountain]

if you define a function/variable hash, it will "shadow" the builtin hash

[fiery cosmos]

does this look right so far:

next i want to look at table[probe] and insert key there into bucket.key

[haughty mountain]

err, why are you computing the same thing twice?

[fiery cosmos]

ah shit i got rid of the incrementing of i

i'm not, did you see what i wrote from the book above

they use i as input into their linear probe

oh wait

[stray fractal]

is auxhash a method in the class

[fiery cosmos]

i see what u mean

[fiery cosmos]

outside

function

[stray fractal]

ok

[fiery cosmos]

ok i think this is what i want:

how might one accomplish such a thing

ahhhh

[plain marsh]

async def CheckLvlUP(user_ID):
    lvl = []
    async with aiosqlite.connect('db.db') as con:
        cur = await con.execute("SELECT level, xp FROM Character WHERE user_ID = ?", (user_ID,))
        row = await cur.fetchone()
        for i in row:
            lvl.append(i)
        while int(lvl[1]) >= (((int(lvl[0]) - 1) + int(lvl[0])) * 100):
            await con.execute("UPDATE Character SET level = level + 1, XP = ?, Points = Points + 5 WHERE user_ID = ?", (lvl[1],user_ID,))
            await con.commit()
            cur = await con.execute("SELECT level, xp FROM Character WHERE user_ID = ?", (user_ID,))
            row = await cur.fetchone()
            lvl[1] -= (((int(row[0]) - 1) + int(row[0])) * 100)
            if int(row[1) < (((int(row[0]) - 1) + int(row[0])) * 100):
              await con.execute("UPDATE Character SET XP = 0 WHERE user_ID = ?", (user_ID))
              await con.commit()```


I have this fuction to calculate lvl up and if user has enough xp to lvl up more than once. Atm I don't feel like this is the best and could be improved so im here to ask for yall opinion on what I could improve and try to "open my eyes" if possible ![bow](https://cdn.discordapp.com/emojis/835422168380342282.webp?size=128 "bow")

[haughty mountain]

why are you recomputing auxhash over and over?

it doesn't change in the loop

[fiery cosmos]

its based on the key and the modulo value

both of which vary

or may / can vary

python doesn't like me making attributes that aren't passed as input paramters

parameters

the above code errors

oh i'll just make it None

ok my print still looks ridiculous

just this over and over

[haughty mountain]

define __repr__ on Bucket

[fiery cosmos]

lol what have i done

ok got that going

all the buckets are currently [None]

which makes sense bc i haven't yet operationalized the insert functin

hmmm

ok yeah something wrong w my insert function

{
    'acpitz': [shwtemp(label = '', current = 27.8, high = 100.0, critical = 100.0), shwtemp(label = '', current = 29.8, high = 100.0, critical = 100.0)],
    'coretemp': [shwtemp(label = 'Package id 0', current = 58.0, high = 80.0, critical = 99.0), shwtemp(label = 'Core 0', current = 53.0, high = 80.0, critical = 99.0), shwtemp(label = 'Core 1', current = 55.0, high = 80.0, critical = 99.0), shwtemp(label = 'Core 2', current = 56.0, high = 80.0, critical = 99.0), shwtemp(label = 'Core 3', current = 55.0, high = 80.0, critical = 99.0)]
}

Help me how to find out the temperature of only one core 0?

[haughty mountain]

not within the loop

    def insert(self, key):
        i = 0
        h = auxhash(key, self.modulo_int)
        for i in range(self.tablesize):
            j = ((h + i) % self.tablesize)

[fiery cosmos]

ok so im loosely guided by pseudocode in CLRS where they are actually saying things like if table[location] == None: do assignment there

they also use repeat, is that a thing?

[haughty mountain]

not in python

while is the closest you get

[fiery cosmos]

ok yeah didn't think so

[haughty mountain]

what was wrong with the while loop?

[fiery cosmos]

lms

i think it'd be fine so long as it ran while i < tablesize

[haughty mountain]

like why did you switch away from the while you had?

and instead do a for loop?

I guess you can do it that way, but then you need a for with an if and a break inside

[fiery cosmos]

you mean repurpose this?

[haughty mountain]

right, why isn't that in your insert?

[fiery cosmos]

i can use it

[haughty mountain]

writing it with a for loop will be longer and more awkward

[fiery cosmos]

i think we're getting our wires crossed with the i and j and h

[haughty mountain]

how so?

[fiery cosmos]

so they want i to run 0 through m-1 eg one less than the table size yeah?

[haughty mountain]

you probe until you find a None, right?

err, not the right reply, but whatever

[fiery cosmos]

right, ignoring the case for buckets of size 3

[haughty mountain]

sure, you probe until you find something empty

the while loop does that

[fiery cosmos]

i thought i should run range(0,mytable.length), not be redefined in terms of itself

[haughty mountain]

you let i increase until you find a None

which (if the table isn't full) will take at most mytable.length steps

[fiery cosmos]

in the book they increment i by 1, rather than something like i = (i + 1)%len(table)

i guess they're equivalent

when i+1 < table length

im looking at pages 270 and 272 in intro to algorithms 3rd edition

the pseudocode outlines their idea of what insert would look like

then 272 has the linear probing, which indeed does recompute another hash location based on the normal or auxilary hash and adding values of i and modulo ing

in it they compute j, which uses the linear probe function

h(k,i)

well they just set a variable j = that function rather

j = h(k,i)

[haughty mountain]

their h function does a modulo I think

[fiery cosmos]

they have h', your standard, vanilla input % tablesize

they then use that and i in their linear probe computation

h(k, i) = (h'(k)+i) % tablesize)

[haughty mountain]

so sure, their impl does what's basically a for loop with a break/return

the one advantage that has is that it realizes after m steps that the element is not there

you could easily modify the thing from earlier to do that, but at that point the code is basically the same anyway

[fiery cosmos]

i think i'm just running a while loop that runs forever now

[haughty mountain]

so sure you can use your for i in ... with a break/return

[fiery cosmos]

no i've done away w that

[haughty mountain]

well, the infinite loop will happen if your hash table is full

[fiery cosmos]

no i don't have enough keys to fill it

something else is wrong

[haughty mountain]

granted you could keep the nice short code and instead keep track of the number of elements inside, and only do the probing if you know a free element exists

[haughty mountain]

so what is your code? I can't say much without knowing that

[fiery cosmos]

i see an error

[haughty mountain]

what is your insert loop doing...

[fiery cosmos]

hmm i should probably try to use those methods i wrote

[haughty mountain]

you know, I should start pointing to my old messages when I feel like i repeat myself

[fiery cosmos]

eg primary hash linear probe

i am aware that you do not like the if something is none, then insert

[haughty mountain]

but for the current if

and yes this is very obviously an infinite loop

because the condition does not change

[delicate ore]

anybody can give me a discord server for python's 'networkx'?

or at least something like a server for python + graph algorithm

[jolly mortar]

this channel?

[delicate ore]

lol

yes

[delicate ore]

anybody know how to handle small conditional probability precision issue?
for instance, I got an event need 0.90.80.30.1.....*0.25 = 1e-40 or something, it will hurt the precision. Any way to transfter it to integer or something? (I know -log() will help, but if the probability is something like 0.999999999999999999999999999, log will be 0.0)

[ivory yacht]

Sounds like what you're looking for is the decimal.Decimal class. That class implements arithmetic in code, which is a lot slower but it can be as precise as it needs to be.

[haughty mountain]

what operations are you doing to the probabilities?

[delicate ore]

mulitplication

conditional probability, but very deep multiplication

[haughty mountain]

that shouldn't be too lossy

float will still be precise up to some number of significant digits

until you get very very small

but if you actually need some ridiculous precision you could look at Fraction

(or Decimal)

Fraction will be exact though

[little stag]

At = np.array([[5, 4, 2], [0, -3, 1], [0, 0, 45]]) #Code input
bt = np.array([5,-5,45])
x = 0


num_rows, num_cols = At.shape
num_rowsBT = np.shape(bt)[0]
results = []

unknowns = 1
counter = num_rows + 1

while counter > 1:
  a = At[(num_rows-unknowns),(num_cols-unknowns)] #Get last number from matrix At
  b = bt[(num_rowsBT-unknowns)] #Get last number from matrix bt
  x = b/a # Solves X

  results.append(x)
  unknowns += 1
  counter -=1

results.reverse()

I am making a function that gets a matrix At with a solution bT and solves X unknows, the expected result would be X shown in image [-1, 2, 1], but the result my function returns is [1.0, 1.6666666666666667, 1.0], could someone help me?

[dreamy valley]

That's not how you solve a matrix equation. You're ignoring everything except the main diagonal of At

[opal oriole]

Is this for school / homework? Or do you just want an understanding of how solvers work internally?

Did you see my previous advice?

[little stag]

School, all I got from my teacher was to check pdf again... And yes I did see your previous advice but I still can't manage to code it in python I do understand how to solve this problem by hand but not how to code it that's why I am asking again

[opal oriole]

Did you solve it by hand using the Wikipedia equation?

[little stag]

Yes, and I got the exepected result but I know nothing about python and the teacher isn't helping either

[dreamy valley]

do the instructions say that you should use numpy to solve the equation?

[little stag]

Yes, I must use numpy

[opal oriole]

Are you suppose to write the algorithm yourself or just call some numpy?

[little stag]

Write a backtracking algorithm

Usining numpy functions

[opal oriole]

By backtracking do they mean back substitution?

As done by hand.

The thing is, numpy can do the whole thing for you.

[little stag]

Yes

[opal oriole]

So using numpy functions would be a one liner unless they say only a specific set of functions.

[little stag]

I can use whatever function in numpy

[opal oriole]

Then you don't need to write any algorithm.

Numpy already has it.

[little stag]

I mean the whole point of the exercise is to write this:

def backtracking(At: np.ndarray, bt: np.ndarray) -> np.ndarray:
    """
    Backtracking(At, bt) takes a triangular and regular matrix At, and an 
    independent term bt as input and produces a vector with the solution of such 
    system. 3.1 solve for x r by:
     x r = 1/diagonalTerm r * (bt r - At r {r+1:end} * x {r+1 to end})
    """
    # TODO: your code here!
    return x

[little stag]

Which function does that?

[opal oriole]

solve

!e ```py
import numpy as np

At = np.array([[5, 4, 2], [0, -3, 1], [0, 0, 45]]) #Code input
bt = np.array([5,-5,45])

print(np.linalg.solve(At, bt))

[halcyon plank]

@opal oriole :white_check_mark: Your 3.11 eval job has completed with return code 0.

[-1.  2.  1.]

[opal oriole]

Given this comment I think I know what they want.

[little stag]

So I just need to recreate np.ling.solve?

[dreamy valley]

I assume this is a translation issue and you copied it from somewhere, but "backtracking" is the name of a technique that doesn't apply here. Back substitution is what you mean.

[opal oriole]

" x r = 1/diagonalTerm r * (bt r - At r {r+1:end} * x {r+1 to end})"

The only problem is that other than the advice I already gave, the next step would just give the solution directly, which I can't do.

It's a pretty exact translation of the Wikipedia equation.

[little stag]

That's what my teacher gave me

[opal oriole]

Backtracking means some else specific. Back substitution is not back tracking, it's the same as forward substitution with a trivial change to the code.

[delicate ore]

is there anybody familiar with directed graph contraction? either edge/node contraction

[little stag]

okey thank you for everything guys^^