algos-and-data-structs

[split vector]

also I got an idea to make it recursive method, after investing in a project, increase the budget, delete the project from the list, then call the method again

could this work without sorting ?

[haughty mountain]

you will end up considering the sorted order regardless in some form

[haughty mountain]

e.g. imagine the setup is like this, with some permutation of 1, 2, 3, ... as investments and 1 as profit

initial  1
invest  1 2 3 4 5 ...
profit  1 1 1 1 1 ...

if you deviate from the sorted order at all your answer isn't optimal

[split vector]

I see

[haughty mountain]

I guess one dumb brute force would be to loop through the unsorted array over and over to try to find things you can invest in

and removing them from the list after investing

keep doing this loop until nothing changes

maybe this is the brute force they intend?

[split vector]

It could be yea

Thank you guys, really appreciate it

[split vector]

Guys this is considered O(n) yeah ?

[haughty mountain]

why would it be O(n)?

[split vector]

n^2 ?

[split vector]

projects.remove is o(n) yeah ?

[haughty mountain]

the code is for sure not better than n²

e.g. for sorted ascending output you get n O(n) removes

and for sorted descending you can have cheap removes, but only once per loop

so an n long loop n times

[dreamy valley]

I think it's n³ regardless because remove(i) searches for i by value

[haughty mountain]

oh wait, yeah

I read i as an index, because that's what people usually do

[stray fractal]

what if enumerate() was used and instead del projects[idx] was done

is that O(n²)

[haughty mountain]

so yeah, my decreasing case can be O(n³)

or wait...

[dreamy valley]

I think so yeah

[haughty mountain]

is it ever O(n³)

you only remove an element once

so one O(n²) aspect is that the n long loop can run n times

the other is doing remove n times

[dreamy valley]

mmm right

[haughty mountain]

so overall O(n²)

[split vector]

but it is wrapped by while

[stray fractal]

also why is budget -= i.spend_to_establish then budget += i.revenue + i.spend_to_establish done
isn't that just budget += i.revenue

[split vector]

doesn't that make it n^3 ?

[haughty mountain]

that's not how complexity works

[split vector]

I am not good at it 😅

[haughty mountain]

all loops are not created equal

you just need to count operations made

that's all the time complexity is

[dreamy valley]

The inner loop is only O(n) by itself, before you add the while

[stray fractal]

also if projects is a list why are you mutating it while iterating over it?
it can skip a few things because of that

[haughty mountain]

this is a case of amortized cost

[haughty mountain]

doesn't actually matter to the complexity though 😛

[split vector]

I am brute forcing it, and I need to check the list again because when a project is established the budget increases, hence i need to check the list again

[haughty mountain]

the proper solution is just sorting and then one greedy pass, which is simpler than this brute force nonsense you were asked to write

[split vector]

I am required to find a simpler solution than the brute force so I guess I solved it all now

Thank you guys

[haughty mountain]

I'm just saying the brute force solution is harder to code and come up with than the optimal one

[split vector]

Yea ..

it was pain

[still bloom]

opt = gradient_descent_v2.SGD(learning_rate=lr, decay=lr/epochs)
NameError: name 'lr' is not defined

I got this while performing a chatbot python code,
How to clear this error?

[fiery cosmos]

Would it help me significantly if I would pay for LeetCode?

[strange grove]

class Solution(object):
def removeDuplicates(self, S):
st = []
i = 0
while i < len(S):
if len(st)!=0 and st[-1]==S[i]:
i+=1
st.pop(-1)
else:
st.append(S[i])
i+=1
return "".join(i for i in st)

can anyone explain me thia code

?

S[i] what it is defining?

Input
"abbacaca"
Output
"caca"

[winged stream]

hi

test

[vital inlet]

hi guys

is there someone here who know about the modelisation of the road traffic with matrixs ?

i have an exam in the end o f the year and i have to analyse a an issue in cities with maths or physics any suggestions ?

ofc using some simulations with python

[fiery cosmos]

would anyone be able to give insight into where values for the shortest path tree for any node n in a graph should be stored? (dijkstra's algorithm)

[scarlet jolt]

Perhaps I should ask here, I already asked here "#help-broccoli message". Recommend Me how to save them, Array seems okay.

[coral horizon]

hello!

[glass river]

what is an efficient sorting algorithm that makes a random array strictly increasing in the least amount of steps?

[agile sundial]

what do you mean by "random array". integers? are they bounded? do you just care about the number of steps? no memory constraints?

[glass river]

for example [3,2,1] becomes [1,2,3]

[7,6,8,5] becomes sorted in 2 steps

[agile sundial]

also what do you mean by steps, comparisons?

[glass river]

yea

well

no swaps

7,6,8,5 becomes sorted after swapping numbers 2 times

[agile sundial]

i'm confused what you're asking. are you asking how many swaps are necessary to sort the array?

[glass river]

yea

[agile sundial]

what have you tried so far?

[glass river]

think you could start from the first index and go to the end, counting swaps is a subproblem for the problem im working on so i already know how the array looks like. I tried to look for maybe the difference between the current array and the sorted one and dividing it by 2 ceiling and it didn't work for all cases.
if i were to try and make a sorting algorithm just for this subproblem after already knowing what it looks like sorted. with 2 pointers I'd swap the highest and lowest numbers until the pointers cross if the numbers aren't already at the correct position

[agile sundial]

wait, what's the actual problem then

[glass river]

minimum operations to make each level of a binary tree sorted

my idea was to do an in order traversal of tree and then sort the values and replace the values with the sorted ones

[agile sundial]

how do you count operations for that? because to swap non-leaf nodes, don't you need to swap their children also? i guess it still works, just a little more annoying

[glass river]

its not really a swap

its more like im changing the data

inside the nodes

[agile sundial]

ah

so can you only change within a level?

[glass river]

yea

that was my way of breaking down problem but i have no clue how to sort

[agile sundial]

idk how to give a hint without just telling you the answer. let me think

[glass river]

😭

when i try to sort on paper its inefficient/not ideal # of swaps

isnt there a specific sort algorithm that does it

telling me the name of it cant be that bad 👀

[glass river]

im gonna use selection sort

[agile sundial]

yeah

it's one of the n log n ones

[glass river]

i think i looked at it the wrong way

[glass river]

i used this to solve it but i think there should be an easier solution since they classify it as hard

https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/

[barren skiff]

This doesn’t guarantee the least number of swaps

I could be wrong but I actually do think that selection sort has the least number of swaps

Even though in the normal implementation it runs in O(n^2), it has N-1 swaps

[ionic locust]

How can I find peter in O(1)? I'm thinking you need to access peter via its hash but am unsure how to specifically do it

from dataclasses import dataclass
@dataclass
class Person:
    name: str
    age: int
    
    def __hash__(self):
        return hash(str(self))
    
    def __str__(self):
        return self.name
    
john = Person('john', 20)
jack = Person('jack', 25)
peter = Person('peter',30)

people = {john, jack, peter}

# Return peter instance
# e.g.
print(next(person for person in people if person.name == 'peter'))

[half lotus]

I believe that is not possible with a set. If you instead had a dict with the names as the key s, then you could get constant time lookup.

[ionic locust]

Ah yeah that makes sense thanks

[haughty mountain]

I think selection sort is optimal wrt number of swaps yes

at least when no elements are equal

I think with duplicate elements things might get more complicated

e.g. both of these do some sort of selection sort

3 2 1 1
^   ^
1 2 3 1
  ^   ^
1 1 3 2
    ^ ^
1 1 2 3

3 2 1 1
^     ^
1 2 1 3
  ^ ^
1 1 2 3

[past ruin]

hi guys, how do i get the first element of this json object
[{"a:1","b:2"},{c:3}] stored in the variable "json_data"

i tried json_data[0], it print me out "["

[hybrid epoch]

Is "json_data" originally a string formatted to JSON?
If so, import the json module and use the loads function
Also, the "json_data" as you have it looks like invalid json

[fiery cosmos]

hej

can u make fortnite cheat

[cosmic condor]

!rule 5

[halcyon plank]

Rules

5. Do not provide or request help on projects that may break laws, breach terms of services, or are malicious or inappropriate.

[dusk elbow]

can anyone help me for a python algorhyme?

only ideas

[lean lake]

i dont get this, my runs are faster but the time for the cell to run is almost 10 seconds. in the other example cell ran twice faster, but my runs from timeit were 5 times slower...

only difference

def merge_sort(arr, min_size=16):
    if len(arr) < min_size:
        selection_sort(arr)
    size = len(arr)
    if size > 1:
        m = size // 2
        left = merge_sort(arr[:m])
        right = merge_sort(arr[m:])
        return merge(left,right)
    return arr

in one cell, im forcing merge sort to use selection sort if the length of the "array" is less than 16

[haughty mountain]

because it sampled different number of runs

[lean lake]

oh geez, /facepalm

why is it doing that? i thought it would default on the same number for both

[haughty mountain]

it's adaptive

[lean lake]

can i hard code, lets say 1000 loops and 1 run?

[haughty mountain]

the timeit module sure supports it

[lean lake]

ah got it, %timeit -n 1000 -r 1

thanks for pointing me in the right direction

[haughty mountain]

why do you want a fixed number?

[lean lake]

comparing a merge sort function vs a merge sort function that is modified to use selection sort when the size of the array gets smaller.. lets say 20

to check if combining both is faster than just using 1 of them

[haughty mountain]

that doesn't answer my question

why a fixed number of runs?

you still get the time for a run from timeit

[lean lake]

the cell with 100000 loops takes too long, im testing this a few times as im doing changes

[lean lake]

#help-popcorn i need help to verify my answer for a workshop, before i submit, for uni. thanks

[heavy lily]

Yo I’m looking for some help

I’m new and in my 3rd week of learning Python3

Trying to understand while loops and I’ve almost got the whole problem figured out…I just need to get the actual loop to fully execute but it’s only half working.

[viral ocean]

hello

does someone know good source to learn data structure and algorithem

looking for resources to learn

[haughty mountain]

channel pins link to a bunch of resources

[flat hornet]

guys someone recommend some material for study data structers and algoritsm

but basically, its important know what denotation are using in algoritmo, the resume of BIG O?

[outer ledge]

Hello guys I need help with the " lst_1=[1,3,4,7,9,10]lst_2=[3,7,9,12,15,2]#Returns a new list with elements COMMON between the two lists.# Implement the functions belowdef intersect(lst_1:list,lst_2:list):

lst_1=[1,3,4,7,9,10]lst_2=[3,7,9,12,15,2]#Returns a new list with elements COMMON between the two lists.# Implement the functions belowdef intersect(lst_1:list,lst_2:list):

[fiery cosmos]

you could do it pretty easy with a double for loop and putting items into an output list when you find two are equal

out = []
for item in lst_1:
  for item2 in lst_2:
    if item == item2:
      out.append(item)
return out```

put in a function that takes the lsts as input

call it intersect

[fiery cosmos]

    # while the priority queue is not empty
    while pq:
        u = heapq.heappop(pq)
        # parse weight, node from pop
        weight, node = u[0], u[1]
        # if node has not been visited, add node to 
        # visited set and proceed; ignore otherwise
        if node in visited: continue
        visited.add(node)
        for neighbor in graph[node]:
            # ignore if neighbor has already been visited
            if neighbor in visited: continue
            # calculate weighted cost of path
            cost = weight + graph[node][neighbor]
            # if better path, update distance and entry
            # in priority queue
            if (cost < d[neighbor]):
                d[neighbor] = cost
                heapq.heappush(pq, (cost, neighbor))

does anyone have any suggestions for how to keep track of the shortest path trees? (e.g. uw, ux, uwv, uwvy, uwvyz)

[fiery cosmos]

the partition problem has got me thinking, what are the number of permutations for an input of size n?

example:
n = 2 = {2,4}

possibilities:
a. set1 = {2,4} set2 = {} b. set1 = {2} set2 = {4} c. set1 = {4} set2 = {2} d. set1 = {} set2 = {2,4}

of course, technically combination b and c need not be considered, as they generate the same difference between set sums

[hearty python]

THE FOLLOWING IS INCORRECT:

n = 2
{1, 2}
{1}
{2}
({})

n = 3
{1,2,3}
{1, 2}
{1}
{2,3}
{2}
{3}
({})

I feel like this is a better way to write down the permutations, and you can clearly see that it is the following sumpy sum(i for i in range(n+1)) +1 # +1 for the empty set which is just the triangular numbers:```py
(n*n+n)//2 +1 # +1 for the empty set

[fiery cosmos]

sorry, the partitioning problem each element must go into an output set

@hearty python

[hearty python]

I don't exactly understand what you are refering to

[fiery cosmos]

https://en.wikipedia.org/wiki/Partition_problem#Exact_algorithms

see: optimization version

[hearty python]

ohhh you were talking about the partitioning problem, i thought it was about some question in here lol

[fiery cosmos]

although, what you've written above may be applicable and i just misread it

[hearty python]

wait i made a mistake, I ignored {1, 3} for some reason

[hearty python]

it states the «multiset S [..] has to be partitioned into 2 subsets»

I am pretty sure that this is the definition of the Stirling numbers of the second kind, in this case: S(n, 2), or plaintext S is the unsigned sterling number of the second kind on n elements with 2 cycles

edits:
first kind -> second kind

the empty set can be ignored since S may only include positive integers

[fiery cosmos]

one of the output sets can be empty

of course, it likely never would as we're trying to minimize the difference of the sums

[hearty python]

well, if a set is 0 long, the sum of it's values is 0, and since S may only include positive integers, and afaik 0 is not defined as a positive integer in this field of math, the sum of the other subset cannot be 0 which allows us to ignore the empty set.

if we allow the empty set we just add 1 to s(n, 2)

ah sorry my bad, it's actually the stirling number of the second kind

but the rest stands

[fiery cosmos]

ok! thank you

its not annoying. you mean there are only that many possible combinations?

permutations..?

[hearty python]

well yea the sterling numbers thingy makes it seem like the calculation is rather complex, but since k is constant (k is the number of subsets we split into = 2) it simplifies rather easily

using recursion:

def rec(n):
    if (n < 2):
        return 0
    if (n == 2):
        return 1
    return 2*rec(n-1)+1

[fiery cosmos]

oh wow so only 10 elements have 511 possible combinations

and input of 100 elements has this many combinations:

633825300114114700748351602687

[hearty python]

indeed

[hearty python]

if you want to go deeper than the recursion limit you can use the unrolled function:

def unrolled(n):
    if (n < 2):
        return 0
    s = 1
    while (n != 2):
        s = 2*s +1
        n -= 1
        
    return s

more pythonic

def unrolled(n):
    if (n < 2):
        return 0
    s = 1
    for i in range(2, n):
        s = 2*s +1
    return s

[fiery cosmos]

what is python's default recursion limit

[hearty python]

1000

[exotic nexus]

  path = path + [start]
  if start == end:
    return path
  if not graph.has_key(start):
    return None
  shortest = None
  for node in graph[start]:
    if node not in path:
      if shortestLength == -1 or len(path) < (shortestLength - 1):
        newpath = find_shortest_path(graph, node, end, shortestLength, path)
        if newpath:
          if not shortest or len(newpath) < len(shortest):
            shortest = newpath
            shortestLength = len(newpath)
  return shortest


stationFrom = "Baker street"
stationTo = "Victoria"
print("From: " + stationFrom)
print("To: " + stationTo)
print("Searching shortest route... This may take a while...")
path = find_shortest_path(tubemap, stationFrom, stationTo)
print("Suggested Route: ")
print(path)```

guys im trying to make a train route which takes data of stations from a separate module, does anyone know how i could add the travel time from the start till end?

[stiff brook]

def miniMax(BoardSpot, depth, isMaximizing,alpha,beta,playerPiece):
    winCheck = cpuCheckWin()
    if(playerPiece == 'x'):
        opponentPiece = 'o'
        if(winCheck == 'x'):
            return 100
        elif(winCheck == 'o'):
            return -100
        elif(winCheck == 'tie'):
            return 0
        
    if(playerPiece == 'o'):
        opponentPiece = 'x'
        if(winCheck == 'x'):
            return -100
        elif(winCheck == 'o'):
            return 100
        elif(winCheck == 'tie'):
            return 0
    
    if(isMaximizing):
        i = 1
        bestScore = float('-inf')
        while(i<=len(BoardSpot)):
            if(BoardSpot[i] == "-"):
                BoardSpot[i] = playerPiece
                score = miniMax(BoardSpot,depth-1,False,alpha,beta,playerPiece)
                BoardSpot[i] = "-"
                bestScore = max(bestScore, score)
                alpha = max( alpha, score)
                if(beta <= alpha):
                    break
                
            i+=1
        return bestScore

hey all could someone tell me why my alphabeta pruning is failing

[agile sundial]

you can use a dict to store the parent of a specific node. then at the end, you can sum up the weights for the path to a node

[exotic nexus]

is it possible if you show me an example? ive only listed my values in the dictionary

like this

"Aldgate East" : ["Tower Hill","Liverpool Street"],
"Angel" : ["King's Cross St. Pancras","Old Street"],
"Baker Street" : ["Marylebone","Regent's Park","Edgware Road (C)","Great Portland Street","Bond Street"],
"Bank" : ["Liverpool Street","St. Paul's","London Bridge","Moorgate","Waterloo"],
"Barbican" : ["Farringdon","Moorgate"],
"Bayswater" : ["Paddington"],
"Blackfriars" : ["Mansion House","Temple"],```

etc.

[agile sundial]

oh wait. your code already returns a path, right?

[exotic nexus]

yeah]

try running it

[agile sundial]

just sum up the weights then

[exotic nexus]

how do i do that?

never tried it before

[agile sundial]

do you have data for the travel times?

[exotic nexus]

yeah but for very specific stations only

i can try it with them though

if i showed you my whole dictionary right here it would be a pain to see but you can take ref from it above

[agile sundial]

if you don't have data for everything it'll be pretty hard to calculate the time for an arbitrary path

[exotic nexus]

so i cant add a weight for only the stations that ive been given a time for?

[agile sundial]

you could, yeah, but it'd be a little weird. you'd have a dict (or something) that maps pairs of nodes (from, destination), to a time

[exotic nexus]

i wouldnt mind trying it right now tbh

just to help me get an idea

[agile sundial]

then with your path, you just sum up the costs to get from each station in your path

[exotic nexus]

do you have a link to a site or an example to help?

ive searched all day but havent seen anything useful

[agile sundial]

so if your path is something like path = [a, b, c]. then the cost for this path, if your costs dictionary is

d = {
  (a, b): 3
  (b, c): 5
}
``` then your total cost is `8`

because to get from a to b is 3, from b to c is 5

[exotic nexus]

ohhhh

but how would i programme it to be as complex as to find a cost between two random stations?

do i have to manually add a cost to all possible outcomes?

like a to b then a to c

[agile sundial]

well no, you just need costs for the connections that exist in the graph

[exotic nexus]

okay, so to summarise i need to create a new dictionary (preferably another module) that maps different stations to and from to a cost (time)

[agile sundial]

yeah

[exotic nexus]

also, when you say graph here what are you referring to? ive seen the term been used around but not in my case

[agile sundial]

a graph is a mathematical thing. it's a thing with nodes (stations, in your case) and edges (connections between stations, in your case)

[exotic nexus]

is it similar to a dictionary in how its structured or completely different?

[agile sundial]

sorta? a dictionary can be used to represent a graph

the idea is that you've got some things and connections between the things

[exotic nexus]

okay i see where youre going

do you know of any useful resources that could help me?

[agile sundial]

the pins in this channel have good resources

[exotic nexus]

alright thanks

can i dm you if i need any help?

[agile sundial]

no

[exotic nexus]

How comes if you dont mind me asking @agile sundial

[agile sundial]

the server is much better for getting help

[dusk elbow]

Hi

does anyone knows how to write an algorhyme for ' slanted square '?

like that

[dense river]

Can i use list/tuple comprehension to only assign a specific value from a tuple to a new variable?

[agile sundial]

can you give an example?

[agile sundial]

to find them?

[dense river]

I have a tuple(["..."], 100) and i want to get the 100 out of it and assign it to a variable prime. The thing is, i don't know if the 100 will always be the last counter, so i probably want to iterate through it and just assign/add it to a variable - but before creating a for loop i was trying to do that with list/tuple comprehension

But it always only returned a generator object

[dusk elbow]

yes find them with an algoryhme

but i don;t know how.....

[agile sundial]

yeah, tuple comprehensions aren't a thing

[agile sundial]

what have you tried?

[agile sundial]

can you give an example of the tuple and what you want to happen

[agile sundial]

@dusk elbow please just use this chat

[dusk elbow]

okay

first i find all of the squares

22 33 4*4

2 * 2 3 * 3 44 55

there is 2 * 2 : 20 squares

because R[0] * C[0]

3 * 3 : 12 squares

result is true

[dusk elbow]

because there is only 2 squares in pic

but

if there is 5 * 5 squre

so there is 4 max 4 diffirence slanted squares

mijn Algorithm can only find 2 of them

v = [[0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 1, 0, 0, 0],
[0, 0, 2, 1, 1, 1, 0, 0],
[0, 1, 0, 1, 1, 3, 2, 0],
[2, 0, 0, 3, 2, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 3, 2],
[0, 0, 2, 0, 3, 2, 0, 0]]

R = [4, 3, 2, 1]
C = [5, 4, 3, 2]
plus = [1, 2, 3, 4]

times = 4

s_v = 0

for t in range(times):
for y in range(1, R[t] + 1):
for x in range(1, C[t] + 1):
if v[y - 1][x] == v[y][x + plus[t] + 1]:
if v[y - 1][x] == v[y + plus[t]][x - 1]:
if v[y - 1][x] == v[y + plus[t] + 1][x + plus[t]]:
if v[y - 1][x] != 0:
s_v = s_v + 1
if v[y][x - 1] == v[y - 1][x + plus[t]]:
if v[y][x - 1] == v[y + plus[t]][x + plus[t] + 1]:
if v[y][x - 1] == v[y + plus[t] + 1][x]:
if v[y][x - 1] != 0:
s_v = s_v + 1

print("Slanted Squares : ", s_v)

[mortal olive]

Trying to implement Red Black Trees for dictionaries in Python. This is about insertion fix-up. After inserting a node, the red uncle rule has been applied as often as possible. Now, it is time for some rebalancing. The functions toNextBlackLevel and balancedTree do some local re-balancing. In many implementations, this is achieved by means of certain rotation operations, but here the approach followed the more simple-minded: inspecting the relevant subtree down to the next ‘level of blacks’, retrieving the relevant 7 components A,a,B,b,C,c,D (capital letters- subtrees and small letters- nodes; notation described in the picture) and building a new and more ‘balanced’ subtree from these. How can one apply both of these functions to the entire tree in a function called endgame:

        # inspect subtree down to the next level of blacks
        # and return list of components (subtrees or nodes) in L-to-R order
        # (in cases of interest there will be 7 components A,a,B,b,C,c,D).
        if colourOf(node.left) == Black:  # node.left may be None
            leftHalf = [node.left]
        else:
            leftHalf = self.toNextBlackLevel(node.left)
        if colourOf(node.right) == Black:
            rightHalf = [node.right]
        else:
            rightHalf = self.toNextBlackLevel(node.right)
        return leftHalf + [node] + rightHalf

    def balancedTree(self, comps):
        # build a new (balanced) subtree from list of 7 components
        [A, a, B, b, C, c, D] = comps
        a.colour = Red
        a.left = A
        a.right = B
        c.colour = Red
        c.left = C
        c.right = D
        b.colour = Black
        b.left = a
        b.right = c
        return b

    # TODO: Task 4.
    #   endgame(self)
    def endgame(self):
        pass #implement here

[dense river]

I've made it work somehow but i had to use a for loop for that (luckily i found more usage for it so it was kinda worth). But now i got another kinda interesting problem (hope it still fits here):

print("Primaries Json in metadata formatting: ", primaries_json)
print("Primaries Json type: ", type(primaries_json))
rint("cp type: ", type(combined_primaries))
#if primaries_json != 0:
combined_data += primaries_json

Output:

Primaries Json in metadata formatting:  0
Primaries Json type:  <class 'int'>
cp type:  <class 'int'>
...
TypeError: unsupported operand type(s) for +=: 'NoneType' and 'int'

Why does it tell me that both classes are int, but then it tells me i can't add those because one is NoneType? Both variables are instantiated with a numeric 0

[agile sundial]

you must have done something in between

[dense river]

I have this codepiece running a few lines above

for p in data_files:
    if isinstance(p, int):
        primaries_json += p

But still "primaries json in metadata formatting" gives me a numeric 0?

[agile sundial]

presumably, something happened in between the time you did the prints and the addition

[dense river]

could be, but i don't really see what. i can keep the if-statement if needed but idk, trying to understand whats happening here 😅

[agile sundial]

well, send the code in between the print and the addition

[dense river]

Sadly i am not allowed to~~, but i think i found the problem~~

[vast shore]

hello i need help, like if i Want to execute a function "EXAMPLE" with a hotkey like if i pres F10 it will execute "EXAMPLE"? how to Do that?

[narrow mirage]

hello, I would like to have some lights on the topic of for-else structure
I found a lot of people bringing criticisms about the feature, sometimes with good arguments, sometimes without

I'd be interested in this particular mail of Guido: https://mail.python.org/pipermail/python-ideas/2009-October/006157.html
within which he says that the feature shouldn't be there, but he doesn't speak about a naming problem, on the contrary, he strongly stresses that it's not because "else" is called "else"

I have this piece of code as an example:

def mutate(entries):
  for entry in entries:
    if "greeting" in entry:
      entry["greeting"] = "Hello"
      break
  else:
    entries.append({ "greeting": "Hello" })

I would like to know:

(-) according to you, what is the problem of for-else in Guido's eyes, and
(-) with that exact reason in mind, how to modify the code so that it doesn't suffer the criticism?

(on my side, I understand Guido's words as: "the possibility to trigger a branch if a break previously occured, might create flows that are difficult to reason about". with that interpretation in mind, I've tried different techniques (local method, try/except, boolean flag, find entry or None then if/else, if not found add new entry then re-entrant...), but none of them would be something I'd consider as really better, in terms of control flow)

[uncut creek]

Really not sure where to ask this, but is the 'run time' measure on leetcode accurate? on this question:
https://leetcode.com/problems/check-if-a-number-is-majority-element-in-a-sorted-array/submissions/

My submission is:

    def isMajorityElement(self, nums: List[int], target: int) -> bool:
        
        
        def binary_search(nums, target):
            l,r = 0,len(nums)
            
            while l < r:
                m = (l+r)//2
                if nums[m] < target:
                    l = m + 1
                else:
                    r = m
            return l
        
        
        left_pos = binary_search(nums, target)
        right_pos = binary_search(nums, target+1)
        
        maj = len(nums)/2
        
        occurs = (right_pos - left_pos)
        if occurs > maj:
            return True
        else:
            return False
        
        #print(f'left_pos: {left_pos}, right_pos: {right_pos}')```

but each time I hit submit, I get a different speed reuslt, i've had varience from 40ms -> 80ms

[agile sundial]

no, it tends to be really bad

[uncut creek]

Ok i wont put much stock in it

[agile sundial]

like, i've had times where 1 submission is like "better than 90%" and no changes, submit again "better than 10%"

[stiff brook]

is anyone familar with alphabeta pruning?

[agile sundial]

a little bit

[exotic nexus]

@agile sundial i know im talking a day later but using the same graph structure for my case mentioned, instead of the nodes A and B id have my stations in their place right?

[agile sundial]

pretty much, yeah

[exotic nexus]

Thanks

[haughty mountain]

Imo it's a useful construct at times, but can be hard to follow especially if misused

[lean lichen]

qui pourrait m'aider a faire un systeme de login dans un programme python mais les user and pass sont heberger sur rentry.co ou autre ?
who could help me to make a login system in a python program but the user and pass are hosted on rental.co or other?

[mortal loom]

Hello I am trying to implement a graph in python but it doesn't seem to work

    def __init__(self):
        self.GraphList = {}

    def AddVertex(self, v1):
        if v1 in self.GraphList:
            print("Vertex Already Exists")

        else:
            self.GraphList[v1] = {}
            print("Added")

    def AddEdge(self, v1, v2, weight):
        if v1 in self.GraphList:
            if v2 in self.GraphList[v1]:
                print("Edge Already Exists")

        else:
            self.GraphList[v1][v2] = weight
            self.GraphList[v2][v1] =weight

    def Display(self):
        print(self.GraphList)

ThisGraph = Graph()
ThisGraph.AddVertex('A')
ThisGraph.AddVertex('B')
ThisGraph.AddVertex('C')

ThisGraph.Display()

ThisGraph.AddEdge('A','B', 2)
ThisGraph.Display()

it doesn't append the dictionary

[agile sundial]

your AddEdge function has a lot of errors in it

trace what happens in your code. v1 in self.GraphList is true, v2 in self.GraphList[v1] is false. so nothing happens, there's no else branch there

also, python naming conventions like to use snake_case for variable and method names

[frozen ridge]

hey everyone, how can i find an element at an index in a tree set?

[keen hearth]

@cobalt shore Please get permission from the server admins before promoting events in the server. Contact @fallow ginkgo to ask about this.

[vernal arrow]

hello

somebody can help me i need to join two dictionaries to a one array index

examples i have value 1 and value 2, and then i want to insert it on array [value1, value2]

how can i do that_

[fiery cosmos]

are the dict values already arrays or are they single values?

[agile sundial]

@sleek gust big O notation is intrinsically theoretical. it talks about the behavior of a function when the input sizes get asymptotically large

[abstract gorge]

^

[lean dome]

And even then, only talks about the behavior after a certain minimum input size.

[abstract gorge]

^

[sleek gust]

I see. Is there a practical use case for it then? Or the assumption is that algos implemented in various systems like in python would behave that way as in theoretical explanation?

[abstract gorge]

import time

def func():
    st = time.time()

    sum_x = 0
    for i in range(1000):
        sum_x += i

    et = time.time()

    elapsed_time = et - st
    return elapsed_time

print([func() for x in range(10)])

For example this returns:

[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]

Which is hard to do analysis

[lean dome]

The theoretical explanation is how the algorithm performs, to within a constant factor. If you implement the algorithm and it behaves differently than that, it's because you implemented a different algorithm.

[agile sundial]

are you sure lol. unless your computer is fast enough that the imprecision from floats is just giving you zeros, there's no way you get that output

[abstract gorge]

[0.0019974708557128906, 0.0030002593994140625, 0.0030002593994140625, 0.002999544143676758, 0.0019998550415039062, 0.0030002593994140625, 0.0029997825622558594, 0.0029997825622558594, 0.0020008087158203125, 0.003001689910888672]

This is the output if it's range(100000)

[0.0, 0.0, 0.0010433197021484375, 0.0, 0.0, 0.0, 0.0009407997131347656, 0.0, 0.0, 0.0]

When range(10000)

[agile sundial]

oh are you on windows lol

[abstract gorge]

Yes

[lean dome]

Though big O doesn't tend to make much of a difference until the input size is relatively large. Hundreds of thousands to millions, often.

[agile sundial]

it's because the timer used by time.time has shit precision on windows

[abstract gorge]

Would running on mac make a difference

[abstract gorge]

Oh what would be a better way to calculate

[agile sundial]

time.perf_counter

[abstract gorge]

[2.5999994250014424e-05, 2.379999205004424e-05, 2.3500004317611456e-05, 2.340000355616212e-05, 2.340000355616212e-05, 2.3500004317611456e-05, 2.3200002033263445e-05, 2.3500004317611456e-05, 2.3500004317611456e-05, 2.3499989765696228e-05]

Ah yeah

output for range(1000)

I think we can all agree doing this in an interview will raise red flags for 99.99% of interviewers

Shouldn't be done

[lean dome]

@sleek gust or, let me try this again: the theoretical big O of an algorithm is based on the number of operations it needs to perform for an input of a given size. If you implement it in a way where it performs more operations than it should have needed to, you have not implemented the algorithm correctly. But Big O doesn't tell you anything about how expensive those operations are, only how many of them happen. That's why O(1) hash tables are often slower than O(log n) trees when n is sufficiently small.

The number of operations performed to look a value up in a hash table doesn't depend on the number of elements in the hash table, while the number of operations to look up a value in a binary tree does depend on the number of elements already in the tree. But the fixed number of operations in a hash table lookup can cost more than the variable number of tree lookup operations.

So, crucially, big O doesn't tell you anything about which of two algorithms will be faster for an input of a given size. What it tells you is how much more work a given algorithm needs to do as the data it's operating on becomes larger and larger.

[agile sundial]

it describes how the runtime will go up as the input size goes up. it doesn't tell you what the runtime will actually be though

[lean dome]

And knowing how the runtime of 2 different algorithms will go up as input size goes up doesn't give you any information at all about which of them will have lower runtime for a given input.

[sleek gust]

That makes sense. What is the practical use of that theoretical knowledge. I'm sure there is. I'm just too inexperienced in this to see it just yet. Possibly theory would be s good proxy for real life execution speed of a program. Or i am looking at this from wrong angle?

[agile sundial]

in many cases, it can be used to compare algorithms. for example merge sort and quicksort are both O(n log n) in the average case, while bubble sort is O(n^2) on average. theoretically speaking, you can't draw conclusions about the actual performance of the algorithms, but in practice it works ok

[lean dome]

It's not a proxy for execution speed. It's used for analyzing scalability. If it takes 0.1 second to process one item, how long does it take to process 10? 100? 1000? 10000?

If processing 100 items takes 10,000 times as long as processing 1, you probably shouldn't use that algorithm unless you have no choice. If it takes 100 times as long, that's not bad at all

Big O gives you a scientific way to answer the question "how much slower would this get if the input was 10x larger"

[sleek gust]

I see. I think thats useful in situations where the scale is huge? In practice, is it used a lot by an average python programmer? I mean i see value in it. Just unsure if learning big O and DSA is mostly good for interview stage for average python programmer?

[lean dome]

The most common place you would use that knowledge is when deciding which data structure to use for something.

DSA teaches you that removing an element from the start or middle of a list is very expensive (O(n)) compared to removing the last element of a list (O(1))

Or that checking if a list contains an item is much more expensive (O(n)) than checking if a set does (O(1))

At least, for sufficiently large lists and sufficiently large sets.

[sleek gust]

That's very practical knowledge. Now i need to add another thing to learn to my list. 😭

[stuck rain]

how can i start learning basic pyton

python

[sudden tangle]

Hi 🙂 I'm looking for an operation that could do the following:

Map N values to a single value: f([1002, 122, 3223, 3223]) -> X
Each value from N would be mapped to the same X but no other value: f(1002) -> X, f(122) -> X

I assume there would be as well key that would be the input.
Is there something that could do that, or it's mathematically not possible?

[vocal gorge]

How about f(X) = X in [1002, 122, 3223]? Each value in the list gets mapped to True, anything else to False :p

[sudden tangle]

I need to create an ID for the list [1002, 122, 3223, 3223] that I send to an API, and then I get webhooks from that API which only contain one entry from the list. So I would like to get the ID using only one entry from the list

If that not possible I will make a mapping between the entries of the list and the ID on my side, I just want to avoid it if it's possible anyhow

[vocal gorge]

Interesting. I'd say not possible, no.

[agile sundial]

hash(tuple(sort()))?

oh, wait i see

[sudden tangle]

Basically I have the following data:

Python
{
  "order": {
    "id": 1,
    "order_lines": [
      {
        "id": 1
      },
      {
        "id": 2
      }
    ]
  }
}

I need to create a return order sending through the ids of the order lines, I can tell the API what should be the ID of the return order
I will get a webhook from the API with the ID of the order and the ID of the order line (only one order line ID)

And I would like to get the ID of the return order without having an order line ID -> return order ID mapping on my side

And it's also possible that I need to create multiple return orders for the same order, with different order lines

All the IDs are unique in the system

[exotic nexus]

hi, i have made my data in a dictionary for my tube station route planner

    ("Harrow & Wealdstone","Kenton"): 2,
    ("Kenton","South Kenton"): 2,
    ("South Kenton","North Wembley"): 2,
    ("North Wembley", "Wembley Central"): 2,
    ("Wembley Central","Stonebridge Park"): 2,
    ("Stonebridge Park","Harlesden"): 2,
    ("Harlesden", "Willesden Junction"): 2,
    ("Willesden Junction", "Kensal Green"): 3,
    ("Kensal Green", "Queen's Park"): 2,
    ("Queen's Park", "Kilburn Park"): 2,
    ("Kilburn Park", "Maida Vale"): 2,
    ("Maida Vale", "Warwick Avenue"): 1,
    ("Warwick Avenue","Paddington"): 2,
    ("Paddington","Edgware Road"): 2,
    ("Edgware Road","Marylebone"): 1,
    ("Marylebone","Baker Street"): 2,
    ("Baker Street", "Regent's Park"): 2,
    ("Regent's Park","Oxford Circus"): 2,
    ("Oxford Circus", "Piccadilly Circus"): 2,
    ("Piccadilly Circus", "Charing Cross"): 2,
    ("Charing Cross", "Embankment"): 1,
    ("Embankment", "Waterloo"): 2,
    ("Waterloo", "Lambeth North"): 2, ```

but when i run it with this code it doesnt work as i intend it to

def find_shortest_path(graph, start, end, shortestLength=-1, path=[]):
  path = path + [start]
  if start == end:
    return path
  if start not in graph:
    return None
  shortest = None
  for node in graph[start]:
    if node not in path:
      if shortestLength == -1 or len(path) < (shortestLength - 1):
        newpath = find_shortest_path(graph, node, end, shortestLength, path)
        if newpath:
          if not shortest or len(newpath) < len(shortest):
            shortest = newpath
            shortestLength = len(newpath)
  return shortest


stationFrom = "Queen's Park"
stationTo = "Charing Cross"
print("From: " + stationFrom)
print("To: " + stationTo)
print("Searching shortest route... This may take a while...")
path = find_shortest_path(tube, stationFrom, stationTo)
print("Suggested Route: ")
print(path) ```

To: Charing Cross
Searching shortest route... This may take a while...
Suggested Route: 
None

Process finished with exit code 0 ```

it gives me this

any help?

[agile sundial]

tube seems to just be the weights, not the graph itself. it returns None because it can't find the start in tube

[exotic nexus]

oh i thought it included both weights and values

how do i make it recognise the stations too then?

[agile sundial]

for your code you'd have 2 dicts, one for mapping which station goes to which station, and another that stores the weights

[viral ocean]

hello guys, may someone suggest who resources to learn dsa for python

[exotic nexus]

is there a way i could connect my excel database to it instead? i shouldve mentioned this before

[agile sundial]

I have no idea

[valid sapphire]

can someone please help me ?

[agile sundial]

what have you tried

[jolly mortar]

interesting

[agile sundial]

French lol

I guess the translator couldn't possibly realize it spelled a French word

[valid sapphire]

sorry i got the wrong picture

[valid sapphire]

I'm explaining to you I don't understand how to fill in this table and I don't know how to find the values

[agile sundial]

you're meant to act as if you're the computer performing the algorithm

[fiery cosmos]

hey all,
need some help getting a version of the Karmakar-Karp Set Differencing algorithm running

i found a python implemention

nvm found the error

[smoky tapir]

can anyone explain the meaning of current = self.head

[fiery cosmos]

sounds like you have a variable current being equal to the head of a linked list

hard to tell w.o code

[smoky tapir]

self.head varriable would be node location

?

class Node:

constructor

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

A Linked List class with a single head node

class LinkedList:
def init(self):
self.head = None

insertion method for the linked list

def insert(self, data):
newNode = Node(data)
if(self.head):
current = self.head
while(current.next):
current = current.next
current.next = newNode
else:
self.head = newNode

[fiery cosmos]

so if(something): is like writing if(something) is True:

so note that

it looks like a node is checking whether it is the head of the list

to everyone else:
what is the runtime of python's sort function?

[agile sundial]

no, it's like writing if bool(something)

[agile sundial]

n log n

[fiery cosmos]

ty

[fiery cosmos]

What is the best way to get better at algos and data structure? What can I do except to solve as much as problems as possibly and learn theory as much as possibly?

[exotic nexus]

df = pd.read_excel(r'London Underground data.xlsx')

def find_shortest_path(graph, start, end, shortestLength=-1, path=[]):
  path = path + [start]
  if start == end:
    return path
  if start not in graph:
    return None
  shortest = None
  for node in graph[start]:
    if node not in path:
      if shortestLength == -1 or len(path) < (shortestLength - 1):
        newpath = find_shortest_path(graph, node, end, shortestLength, path)
        if newpath:
          if not shortest or len(newpath) < len(shortest):
            shortest = newpath
            shortestLength = len(newpath)
  return shortest


Departure_station = "Kenton"
Arrival_station = "South Kenton"
print("From: " + Departure_station)
print("To: " + Arrival_station)
print("Searching shortest route... This may take a while...")
path = find_shortest_path(df, Departure_station, Arrival_station)
print("Suggested Route: ")
print(path)```

@agile sundial ive managed to connect my excel db using pandas but the path still wont display

[agile sundial]

what's df

[exotic nexus]

just the name of the variable to read thee excel file

i mentioned it in my path at the end hoping it would use the data in that file

[agile sundial]

well you can't really just hope things will work

[fiery cosmos]

hey all,
trying to understand the subset sum algo pg. 1129 of CLRS

i don't understand the the example set addition

wait i think i got it

[granite vortex]

Leetcode does the job, if a bit to difficult use w3school

[vocal gorge]

codeforces is a very DSA-focused site

[frozen ridge]

hello everyone, let's say we have a tree with the students graduation year. how can we implement a recursive function so that it returns the number of students who graduated at the given year?

Again the same question but with an iterative function. so if anyone knows how to code with either functions please let me know.

[agile sundial]

why is a tree holding a student's graduation year

[lean walrus]

Maybe it is search tree sorted by year?

If so, you can give answer in O(logN) time (if tree is balanced, N - number of students)

[keen hearth]

It's just saying that, in their notation, S + x denotes {s + x for s in S}.

So {1, 2, 3} + 1 denotes {2, 3, 4}.

[frozen ridge]

its a binary search tree

[agile sundial]

yeah but like. i don't get what you'd put in there. why not just a list or something

[frozen ridge]

well idk they question in my projects says that

its not up to me

[fiery cosmos]

Do you think it would be good to take LeetCode premium?

[haughty mountain]

something something convolution

convolution([1, 1, 1], [0, 1]) -> [0, 1, 1, 1])

iirc you can actually use fft for subset sum to compute it using convolutions

[hazy fossil]

helo guys so i am doing this project for university and for one of thesteps i havee to give it a gene which i will giveit as a list and then i will do list.count of x and y , x + y are 40-60% it works for us

however im having trouble to how to write this

im thinking off , list = []^
def GC
X = list.count(G)
Y= list.count(C)
all = list.count(all)
result = (X + Y)/ALL * 100
If result>= 40 and result <=60
print("this gene has " + " " + all + "of whom" + " " + result + "% of the ammount of GC in this gene")

[worthy escarp]

there are a number of syntax errors, but the logic here seems sound

[tepid geyser]

!code @hazy fossil

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

[tepid geyser]

Please

[granite vortex]

not worth, free is ok

[fiery cosmos]

I thought that it is worth because I could get hints for some problems, so it is better to get hints instead of seeing other's solution if after some time I don't know how to solve problem.

[granite vortex]

for me leet code hints are kinda vague tbh, nowadays if i dont understand a problem i just watch an yt video for it then i understand it and do it myself, but do what works best 4 you

[fiery cosmos]

Okay, after I finish with learning about algorithms on graphs and strings I will start to solve these LeetCode problems and also problems from How to crack software engineering interview book

[granite vortex]

sounds like a good path ✌️

[hybrid epoch]

One of the few values of LC premium is the complexity analysis portion of the solution section. It has good rigor.

[fiery cosmos]

So you can basically see few solutions and their complexity?

[tepid igloo]

Can someone explain constructor please?

Not quite able to understand it's functioning

[hybrid epoch]

Most, if not all, of the LC premium questions have a corresponding solution with an analysis of its time complexity. Some, if not most, of these analyses are rigorous.

[hazy fossil]

i know its some of my first time using this lango , well i know some of the basics already but i dont know how to put it to work or how to write it , i was thinking about the arrays in numpy

[worthy escarp]

unless your gene is millions long, you do not need numpy for this.
I think knowing the basics of python well will be more useful for you in the long run then learning numpy from cases where it is not needed
here is your code with the syntax fixed: https://paste.pythondiscord.com/ajojadutuh, perhaps you will find it useful

[hazy fossil]

thank you it works amazing i was kinda stuck on how to put into "words" eheh

[fiery cosmos]

hey y'all,
trying to implement LCS-LENGTH on pg 394 of CLRS. first ?, why do they say to initialize two tables but one is 1..m on one axis and 1..n on the other and the second is 0..m and 0..n?

is it a typo?

[fiery cosmos]

also, their if elseif else clauses aren't nested properly so its difficult to see whats going on there

[fiery cosmos]

anyone know how i'd convert an image to binary

without CV2

[haughty mountain]

no

note how in the loop the look back on step in i and/or j

[fiery cosmos]

will this work?

b = [[0]*m for _ in range(1,n)]
c = [[0]*m for _ in range(0,n)]

[haughty mountain]

are you planning on zero indexing both?

and no it's not right, b should be m x n and c should be (m+1)x(n+1)

[fiery cosmos]

i don't think they want that..

[haughty mountain]

how so?

[fiery cosmos]

no sry discord is being weird. i meant they don't want both to be initialized to all zeroes

only some of the arrays

[haughty mountain]

they only initialize one row/column of c

you don't really have the option to not initialize in python, you need to init to something

[fiery cosmos]

right

thats why i typically do zeroes

i guess one could do empty lists

[haughty mountain]

but yeah, for c it only matters that the first row/column is correctly initialized

[fiery cosmos]

also, i've copied everything they've written in the pseudocode and converted to python, however, its an absolute maelstrom of list index out of range errors

[haughty mountain]

^

[fiery cosmos]

    b = [[0]*m for _ in range(n)]
    c = [[0]*m+1 for _ in range(0,n+1)]
```?

[haughty mountain]

(m+1)

but yeah

[fiery cosmos]

no need for that zero in the second range statement

[haughty mountain]

and the loop should actually be one indexed like theirs

in which case you need to index b with -1s

because you zero index that

[fiery cosmos]

both loops should run (1,n/m)?

[haughty mountain]

range(1, n+1) and range(1, m+1)

[fiery cosmos]

weird ok

[fiery cosmos]

every b index? like b[i][j] in pseudo should be b[i-1][j-1]?

[fiery cosmos]

this gives string index out of range error

[haughty mountain]

right, the strings are also zero indexed

so -1

[fiery cosmos]

like this?

ohh i see what's going on

my input strings are different lengths

so my if errors

wait no

its the structure of the for loops and their range

its always going to look "outside" of the length of the input string

[haughty mountain]

did you fix the string indexing or no?

those will need -1s

[fiery cosmos]

yes but it is erroring before that, because of the m+1 and n+1 since m and n are the length of my input strings

they are saying to do the same thing in an online example, so you must be correct

this is their example to set up the initial tables:

where m and n are the length of S1 and S2, i presume

[haughty mountain]

that's such a bad signature

[fiery cosmos]

although here they have only one table

how are we to look beyond the length of the input string though? i don't get it

[haughty mountain]

there is also the option of doing a zero indexed loop and indexing the table differently

[haughty mountain]

you're not

[fiery cosmos]

maybe i am reading the pseudocode wrong. i notice that their input strings are X and Y but in the if statement they say to consider x[i] and y[j]. i assumed we were looking at the strings.

[haughty mountain]

they probably are

[fiery cosmos]

not sure why they would change capitalization

im sure they are thats the main comparison happening

[haughty mountain]

are they indexing the strings with stuff outside 1..len?

[fiery cosmos]

clearly this would look beyond the length of the string

[haughty mountain]

[haughty mountain]

[haughty mountain]

there is another alternative

[fiery cosmos]

in what world would this not error

[haughty mountain]

you haven't corrected for zero indexing

like I said twice

[fiery cosmos]

this is not in the pseudocode

they run up to m and up to n

[haughty mountain]

where is this?

[fiery cosmos]

what you said to do

[fiery cosmos]

here

[haughty mountain]

that is correct if you want to match their loop indexing

but their strings are 1 indexed

yours aren't

so -1

when indexing

[fiery cosmos]

alright so everywhere in the pseudocode, when it says c[i] i'll make it c[i-1] and when it says c[i-1] ill instead make it c[i-2]

[haughty mountain]

the indexing for c is 0 based

[fiery cosmos]

yeah i have it as -1 for all b indices yes

[haughty mountain]

everything but c basically

you could also do the reverse

do range(n) and similar

and correct the indexing of c

[fiery cosmos]

so i thought a fix for all this would be make m and n equal to length of input string minus 1, then the loops with the +1 indexing will work?

i'll try

[haughty mountain]

m and n are and should be the string lengths

[fiery cosmos]

oof

[fiery cosmos]

yeah this seems like a good approach

[haughty mountain]

s = ...str with len n...
t = ...str with len m...
c = [[0]*(m+1) for _ in range(n+1)]
for i in range(n):
  for j in range(m):
    s[i]
    t[j]
    c[i+1][j+1]
    c[i][j+1]
    c[i+1][j]
    c[i][j]

[fiery cosmos]

its confusing bc there are two loops and two tables

[haughty mountain]

basically they want to do 1 indexing

but they also need an extra column/row at the beginning

it would be like adding a -1 row/column in python

[fiery cosmos]

here is the pseudo

lines 4-7 were ignored and everything is initialized to zeroes

and the rest i cannot figure out how to augment, given that there are both b and c tables and +1's outside of indices

i guess that doesn't matter, its only.. actually what is that even doing? is that like a +=1??

line 11 +1

i made all c indices +=1 and it errors

[haughty mountain]

how so? code?

[fiery cosmos]

list index out of range errors. 1s

[haughty mountain]

you're mixing up n and m

[fiery cosmos]

in the pseudocode, thats how it is

m is the length of the first input string

and the loops are nested that way

m<n

not literally but m before n

[haughty mountain]

if you want that then you need to change c

[fiery cosmos]

im more concerned about if we have interpreted line 3 properly

[haughty mountain]

or index it with [j][i]

[fiery cosmos]

bc their pseudocode is weird

[haughty mountain]

jfc, I know what they are trying to do

your tables are transposed compared to theirs

[fiery cosmos]

seems like table b should get the (m+1) clause?

err

[haughty mountain]

their tables are m x n

yours are n x m

(ignoring the +1)

the fact that their table is m x n annoys me but that's a separate issue...

[fiery cosmos]

so im supposing i just flip the variables in these statements:

m -> n
n -> m

its says it computes the entries in row major order if that changes anything

[haughty mountain]

it's row major but with dimensions m and n which is...annoying

the standard for matrices is n, m

n rows, m columns

[echo fjord]

How would a brute force integer multiplication algorithm would work, is it same as the procedure used in elementary school to multiply two numbers

[fiery cosmos]

really? why would they do it opposite from the standard paradigm

[haughty mountain]

idk why they would do that

[fiery cosmos]

maybe this is why the profs dont know what theyre doing

[haughty mountain]

the naive way would be the elementary school method yes

[fiery cosmos]

not literally but idk how i get wrapped up in such nonsense

anywho

[echo fjord]

thanks

[fiery cosmos]

i've moved on to the print_lcs method

and it too is erroring

let me get the pseudocode..

[haughty mountain]

one better method would be karatsuba multiplication

[fiery cosmos]

i google for it bc i dont have a digital copy of the text

the initial call is print_lcs(b, X, X.length, Y.length)

so i've written this verbatim into python and im guessing there is an obvious reason that will not work

not verbatim but like, i haven't done any index augmentations

[haughty mountain]

b is zero indexed

so you'll need to do some shift

b[i-1, j-1] is one way

[fiery cosmos]

will that change what is needed on line 4

[haughty mountain]

no

[fiery cosmos]

hm

seems to error on "line 5" of the pseudocode

in my code line 34

[haughty mountain]

i-1 there

[fiery cosmos]

got it

ok i think its working

see this is really cool, bc this is the beginning of bioinformatic stuff, you could input 2 different genes as their nucleotide sequences and find the LCS, and hence a measure of "sameness"

[haughty mountain]

or you can use it to diff code

[fiery cosmos]

that being said, there are for sure more powerful tools out there to do this very thing, and ones that have been optimized and can handle doing multiple sequence alignment, eg https://www.ncbi.nlm.nih.gov/projects/msaviewer/

and NCBI nucleotide blast

[fiery cosmos]

what would you use it for

lol i wonder why they make us reinvent the wheel. i guess so we know how the tools work

[haughty mountain]

would you rather dig into some much more complex sequence alignment algo?

rather than a simple one

this algo also has a lot of similarity to some other string algos

like edit distance

it only differs in the rules in the loop

same structure

[fiery cosmos]

no this stuff is important for sure. but so is learning how to use bash or linux to pipe different ins and outs between tools to build an entire bioinfo pipeline, maybe that'll come in later courses

[haughty mountain]

that's not computer science 😛

[haughty mountain]

you mean how it applies to diffing code?

[fiery cosmos]

yeah the example you gave me with the different lists really made me not confident in my python comprehension

some of the basics im still really iffy on even after all this time

kind of sucks but im trying. i really want to learn some mathematics so i dont look like a fool in the future. like linear regression stuff

i guess once i start using numpy and R and data science stuff that'll be easy "to do"

but i'd like to comprehend it

[fiery cosmos]

oh. you meant diff as a verb

what is diffing code

[haughty mountain]

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

[fiery cosmos]

the long short of it is i need to learn more algebra and then do linear algebra

diff is line-oriented rather than character-oriented

LCS is character oriented i believe

[haughty mountain]

LCS doesn't care

LCS only cares if things are equal or not

your particular example used characters, but it's more general than that

[fiery cosmos]

alright im gonna start working on making it a proper program that can read input

gotta remember how to use argparse

[haughty mountain]

if you just read two files, split into lines and feed it into LCS it will find the common lines in the file

the steps taken in the table can be read as insertions/deletions and common lines

I've had to use LCS for work, so knowing it exists is certainly helpful

so you might encounter problems where random algos you've learned pop up

[fiery cosmos]

well that's the interesting thing about all of this. they're each like unique puzzles that can be solved and optimized. and not always, but oftentimes there is a "best solution" to a given problem

alright i have to figure how to parse this input. all strings are in the same file like this:
s1 = 'abcd'
s2 = 'bced'
s3 = 'cbefg'
so on

i can ask in help chan

[fiery cosmos]

Anyone know how I could create a local binary pattern of an image? without using the CV2 stuff

[fiery cosmos]

actually can you help

help channel isn't going to smoothly

[fiery cosmos]

alright this is as close as i've gotten:

and i still have annoying whitespace after my variable name and before the string

can i just throw in another strip()?

ok i got it

with some abomination of code

[median escarp]

Is Data Structures and Algorithms using Python preferred by companies ?

[brittle moat]

you can use whatever lang you want

[upper kite]

Isn't python kind of slow in terms of creating/sorting data structures, though? At least, in comparison to C++ or other compiled languages?@brittle moat

[brittle moat]

who cares?

they don't

[brittle moat]

use the lang you're most familiar with. I would highly suggest python

[indigo quest]

guys, which is a great course/book to learn data structures and algorithms in python?

[hybrid epoch]

Check pins

[barren skiff]

I would say it’s more about the knowledge than the language

[slender dew]

This is a ques regarding sum of subsets using a space tree. How is the solution to this question : 11010
IDK where last zero comes from ?
Sol in bottom right

[haughty mountain]

for learning the stuff language for sure doesn't matter much, and the knowledge is language agnostic

[dreamy valley]

The solution is the subset of the original set that adds up to 9
They are representing that as a sequence of 0 or 1: 1 if the corresponding item in the original set is included in the subset and 0 if it is not included

So {1, 1, 0, 1, 0} represents the subset {1, 2, 6}

[slender dew]

yes, but according to the sol:
With 1 - 1 Sum = 1
with 2 - 1 Sum = 3
without 5 - 0 Sum = 3
with 6 - 1 Sum = 9

Sollution must be : 1101 right ? where does the additional 0 at the end come from?

[dreamy valley]

the original set is 5 items

Not 4

You need to decide whether or not to include each of them in the sum

ignore the tree for a moment and think about what 11010 means as a solution

it means 1 is included (1), 2 is included (1), 5 is not included (0), 6 is included (1), and 8 is not included (0)

[slender dew]

oh yeah I completely missed the point of having to access every element of the set!! TYSM thats clears things up !

[swift shadow]

@fiery cosmos

[fiery cosmos]

?

[swift shadow]

can you help me with this question??

[eager cliff]

That looks like a test?

[swift shadow]

assignment

[eager cliff]

So what do you have so far? What's the hold up?

[swift shadow]

nothing😢

[eager cliff]

What's stopping you from getting started?

[lethal raptor]

Hi, how to implement the suzuki-kasami algo for contour border drawing?

[wide gale]

I'm trying to write my own pokemon iv calculator. (for gen 3-4) and obviously, I need to have all the pokemon names and their base stats. What's the best way to import/use this data in my program? this is my first proper project. ive done coding excercises on code wars and some scripts for 3d software like Maya but nothing bigger than that so im especially clueless about like how to deal with data like that.

ive been trying to follow an open-source iv calc here as a guide. but its been difficult for me to follow because its in javascript which im not familiar with , and ive had a hard time testing what certain parts do because the code is pretty messy and is not modularized at all. just everything in one script. (he is by his own admission not a professional developer ) though he seemed to compress the data and import it which makes sense though i don't know what compression algorithm he used because compression is completely new to me.

//Compressed Pokemon data: HP/ATK/DEF/SP.ATK/SP.DEF/SPD/Type1/Type2/Egg1/Egg2/EPs2/EPs1 - national order + forms
pkmn='      ??    2ρρ**21()B )"~^00"1()B !0λM4401()B :οHE"&*AA)9D }D}0*0AA)9D)XhXν84A-)9 (Uz*& ... '
pk='00,05,3c,04,0b,32,03,01,41,0f,46,02,37,28,50,0c,2d,5a,64,4b,23,69,55,0e,06,0d,08,5f,1e,09,5b,0a,07,6e,40,2b,6c,14,34,91,10,19,96,53, ..'
//Decompression Arrays
pk=pk.split(',');
mn=' !"#$&()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[]^_`abcdefghijklmnopqrstuvwxyz{|}~%αβγδεζηθικλμνξοπρστυφχψωΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩςάέήίόύώϊϋΐ'; mn=mn.split(''); base=[];

function get_base(p,s) { //Returns values from pkmn
    if (!base[p]) {
        base[p]=pkmn.slice(12*p,12*p+12).split('').map(function(v,i){v=pk[mn.indexOf(v)];if(i<10)v=parseInt(v,16);return v});
        base[p].push(('000000000000000'+parseInt(base[p].pop()+''+base[p].pop(),16).toString(2)).split('').reverse().join('').substr(0,12).split('').reverse().join('').match(new RegExp(".{1,"+2+"}", "g")).reverse().map(function (v) { return parseInt(v,2); }));
        base[p][10].push(base[p][10].splice(3,1)[0]);
    }
    return base[p][s];
}

i cut down the compression and decompression arrays for readibility because they went on a for a while

[haughty mountain]

that code is genuinely terrifying

[topaz surge]

reducing the length array by merging adjacent elements and replacing them with either of their modulo. Find minimum length of array that can be reduced

any clues how to do?

[haughty mountain]

thing.split('').reverse().join('').substr(0,12).split('').reverse().join('')```
is a very awkward way to write
`thing[-12:]`
in js 🤡

which is only needed because the code wants a zero padded binary string

and the regex is...splitting in groups of 1 or 2?

but...won't it always be 2 because of the padding and cutting?

[worthy escarp]

though he seemed to compress the data and import it
I think this makes sense to do for javascript, but I don't think this makes sense to do in python.

[haughty mountain]

I'm assuming the specific compression isn't even sensible

it's more serialization than compression

welp, I actually need the data to actually validate this

omfg

https://github.com/LegendaryPKMN/ivcalc/blob/master/javacalc.html

[wide gale]

Then what makes sense for python?

[worthy escarp]

I would parse it directly from the source, no compression/serialization
what data structure you parse it into depends on how much a fan you are of object-oriented code

[haughty mountain]

I'm rewriting this thing for fun, I should have something shareable soonish

[haughty mountain]

rate my rewrite

data = ...
data.push(('000000000000000'+parseInt(data.pop()+''+data.pop(),16).toString(2)).split('').reverse().join('').substr(0,12).split('').reverse().join('').match(new RegExp(".{1,"+2+"}", "g")).reverse().map(function (v) { return parseInt(v,2); }));
data[10].push(data[10].splice(3,1)[0]);
```to
```py
def base4(n: int, n_digits: int = 6) -> list[int]:
  """Base 4 digits."""
  return [n//4**i % 4 for i in range(n_digits)]

ev = base4(data.pop()<<8 | data.pop()) # ev yield is 6 x 2bits, encoded as 2 bytes
ev.append(ev.pop(3))  # Fixing wrong ordering.
data.append(ev)

Full thing, with their data in a separate file

import sys
from dataclasses import dataclass
from functools import cache

# This is just the raw data from the js file.
import raw_pkmn_data

# Put their data in more sensible form.
def parse_name(s: str) -> tuple[int, str]:
  name, i = s.split(':')
  return int(i), name

class PkmnData:

  def __init__(self):
    self._pkmns = dict(map(parse_name, raw_pkmn_data.pkmns.split('|')))
    self._pk = bytes.fromhex(''.join(raw_pkmn_data.pk))
    self.types = raw_pkmn_data.types
    self.eggs = raw_pkmn_data.eggs

  def name(self, i: int) -> str:
    return self._pkmns[i]

  def raw_data(self, i: int) -> bytes:
    # Data read with some lookup table. I guess that's their compression?
    return bytes(self._pk[raw_pkmn_data.mn.index(v)]
                 for v in raw_pkmn_data.pkmn[12 * i:12 * i + 12])

pkmn_data = PkmnData()

# Let's make something nice.
@dataclass
class Pokemon:
  name: str
  HP: int
  ATK: int
  DEF: int
  SP_ATK: int
  SP_DEF: int
  SPD: int
  Type1: str
  Type2: str
  Egg1: str
  Egg2: str
  EPs: list[int]

def base4(n: int, n_digits: int = 6) -> list[int]:
  """Base 4 digits."""
  return [n // 4**i % 4 for i in range(n_digits)]

def make_pkmn(p):
  """Make pokemon."""
  data = pkmn_data.raw_data(p)
  hp, atk, df, spatk, apdef, spd, type1, type2, egg1, egg2, eps1, eps2 = data

  ev = base4(eps2 << 8 | eps1)  # EV yield is 6 x 2bits, encoded as 2 bytes.
  ev.append(ev.pop(3))  # Fixing wrong ordering.

  return Pokemon(
      pkmn_data.name(p),
      hp,
      atk,
      df,
      spatk,
      apdef,
      spd,
      pkmn_data.types[type1],
      pkmn_data.types[type2],
      pkmn_data.eggs[egg1],
      pkmn_data.eggs[egg2],
      ev,
  )

@cache
def get_pokemon_stats(p):
  return make_pkmn(p)

print(get_pokemon_stats(int(sys.argv[1])))

> python pkmn.py 373
Pokemon(name='Salamence', HP=95, ATK=135, DEF=80, SP_ATK=110, SP_DEF=80, SPD=100, Type1='Dragon', Type2='Flying', Egg1='Dragon', Egg2='Dragon', EPs=[0, 3, 0, 0, 0, 0])

[vocal gorge]

interesting

[haughty mountain]

the js code does some seriously weird stuff

[vocal gorge]

i have a gen3 pokemon data parser and battle simulator in Rust, but it can only do fairly basic stuff like damage for now

thankfully the bulbapedia religiously documents the memory format, great stuff

[haughty mountain]

class PkmnData:
  ...
  def raw_data(self, i: int) -> bytes:
    # Data read with some lookup table. I guess that's their compression?
    return bytes(self._pk[raw_pkmn_data.mn.index(v)]
                 for v in raw_pkmn_data.pkmn[12 * i:12 * i + 12])

def base4(n: int, n_digits: int = 6) -> list[int]:
  """Base 4 digits."""
  return [n // 4**i % 4 for i in range(n_digits)]

def make_pkmn(p):
  """Make pokemon."""
  data = pkmn_data.raw_data(p)
  hp, atk, df, spatk, apdef, spd, type1, type2, egg1, egg2, eps1, eps2 = data

  ev = base4(eps2 << 8 | eps1)  # EV yield is 6 x 2bits, encoded as 2 bytes.
  ev.append(ev.pop(3))  # Fixing wrong ordering.
```which one would you rather maintain? 😛
```js
function get_base(p,s) { //Returns values from pkmn
    if (!base[p]) {
        base[p]=pkmn.slice(12*p,12*p+12).split('').map(function(v,i){v=pk[mn.indexOf(v)];if(i<10)v=parseInt(v,16);return v});
        base[p].push(('000000000000000'+parseInt(base[p].pop()+''+base[p].pop(),16).toString(2)).split('').reverse().join('').substr(0,12).split('').reverse().join('').match(new RegExp(".{1,"+2+"}", "g")).reverse().map(function (v) { return parseInt(v,2); }));
        base[p][10].push(base[p][10].splice(3,1)[0]);
    }
    return base[p][s];
}

I guess I don't have the caching in my small snippet here, but...

[vocal gorge]

this needs some types very badly

[haughty mountain]

mine?

I added hints to make_pkmn in my local code just after posting this

btw, I have no clue what they are doing with the regex

well

I know what it does

but idk what they were thinking

why building the regex like this ".{1,"+2+"}"
why match 1 or 2 bits? you are guaranteed to have 12 bits, an even number

the whole code is...interesting

it was a fun reverse engineering exercise though

[dreamy valley]

the real mystery is why abbreviate pokemon to pkmn when pikmin exists

[haughty mountain]

not my naming scheme 🤷‍♀️

[fiery cosmos]

hi everyone,
i'd like some help converting a written algorithm i have found to pseudocode

so far i have just taken the input set and reverse sorted it

[lunar jacinth]

@vocal gorge can u confirm this please?

[austere flame]

Hi everyone, it looks like I create a data structure name "class list" of "list" in my algorithm. I use function "type()" to realize it. But I cannot find any documents about class <list>. Does anyone know about this?

[agile sundial]

a list?

[lunar jacinth]

does this run in O(|V |) algo?
https://www.geeksforgeeks.org/program-to-count-number-of-connected-components-in-an-undirected-graph/

[austere flame]

actually I cannot use this element as a list

It looks different

[agile sundial]

that's just the string representation of the list class

[austere flame]

Oh it looks like I found it : https://www.geeksforgeeks.org/python-convert-a-string-representation-of-list-into-list/

let me try

thankss

[haughty mountain]

that sure ain't it

[austere flame]

oh not this one

[austere flame]

is the "list" class different from a normal list like a=[1,2,3]

[haughty mountain]

list is the class

[agile sundial]

have you learned about object oriented programming?

[haughty mountain]

that a is an instace of the class

[austere flame]

not really 😦

it looks like my [1] is not a list to use some function like "max" or "append"

normally, when I use the function type() for a=[1,2,3]. It's a list. But that [1] in my code appears as <class list> which made me confused

[haughty mountain]

where does it appear like that?

[austere flame]

I cannot use my classroom_code.get(index) as a list even it equals to [1] and exists as < class "list">

that made me confused between class list and list

[haughty mountain]

it's the same thing, if you print it it will show the "<class 'list'>"

[fiery cosmos]

anyone know where i can find "karmarkar-karp complete" pseudocode?

the OG one won't do it; must be complete

[austere flame]

But I don't know why I cannot use it as a list

[haughty mountain]

wdym you cannot use it as a list?

[austere flame]

you can see the code, the function append doesn't work on it

it then becomes the Nonetype if I try to append new element :((

[haughty mountain]

this line doesn't do what you think it does

[austere flame]

yep

that's what I mean 😦 but I dont know how to fix

[haughty mountain]

append on a list doesn't return a new list

it modifies the list in place

[austere flame]

ahhh I understand

I was stupid omg

thanks a lot

[haughty mountain]

so you can just do

classroom_code[index].append(new_order)

also no real need to use .get in this case

[austere flame]

ah thanks :)) it works now

[fiery cosmos]

or maybe the complete greedy algorithm?

i found some python, but idk how to convert that to pseudocode bc it uses numpy and other tools

[haughty mountain]

do you need the sets or just the difference?

because just getting the difference is easy

[fiery cosmos]

i have papers showing the CKK binary tree and python for both CKK and complete greedy

https://www.ijcai.org/Proceedings/95-1/Papers/035.pdf

the paper discusses the extension of the karmarkar karp to form the complete karmarkar karp by also using the sum of the largest two numbers, not just the difference

[haughty mountain]

any reason you need the complete version?

[fiery cosmos]

yes, the object of the assignment was to write a deterministic solution to the problem, not an approximate solution

[haughty mountain]

why not just do the typical dp to solve it?

it's super simple

[fiery cosmos]

i'd love to, i was unable to find a version that either also returns the sets or augment an existing pseudocode to also return the sets

i need to be able to trace the logic and show how it works with examples, so i need to be able to wrap my mind around the dp aspect, whichever way that works

[haughty mountain]

do you know how the dp works to begin with?

because if you do backtracking to find the solution is easy

[fiery cosmos]

i'll look again, i'd say no

[haughty mountain]

then learn it

it's a very basic application of dp, well worth understanding

I talked about it in this channel some time ago

maybe you can find something interesting

[fiery cosmos]

another issue is that the implementations we've found use the |= operator

so like, how are we gonna convert that to pseudo

[haughty mountain]

implementation of what?

[fiery cosmos]

the dp solution to solve the partitioning problem such that the difference in sums of two subsets is minimized

[haughty mountain]

just use a dp table

the | is just cute bit magic you could do

[haughty mountain]

did you read this?

in particular this dp

[fiery cosmos]

i'm looking now

[haughty mountain]

and I described the reconstruction process as well

[fiery cosmos]

ok so with that as a pretext i seek to understand the following:

We can create a 2D array dp[n+1][sum+1] where n is the number of elements in a given set and sum is the sum of all elements. We can construct the solution in a bottom-up manner.

[haughty mountain]

my thing is related to it

[fiery cosmos]

yeah i tried to use your explanation as a primer

[haughty mountain]

but I don't use a ~n x sum table

I just store ~sum numbers

but I can't store true/false if I want to be able to reconstruct it with my way

I need a bit more info than that

[fiery cosmos]

im confused should i try to use just an array as well

[haughty mountain]

idk, up to you what approach you want to do

the 2d table might be conceptually easier, idk

[fiery cosmos]

i just need an approach i can understand well enough to walk through the pseudocode in my head and show examples of how it works on paper

[haughty mountain]

the method is stupid simple

[fiery cosmos]

not for us hack CS people 😩

this is what im trying to understand now

[haughty mountain]

let's do a dumb example

[fiery cosmos]

sure

let me get my pen and paper

[haughty mountain]

[3. 7. 2]

we can reach 0 using 0 elements

(dumb base case)

what can you reach if I also allow the 3

(express it in the numbers you can already reach)

[fiery cosmos]

first i would like to understand how the dp table will look. it says [n+1]*[sum+1]. so i have 4*13. so i will have a list of length 13 where each element is a list of length 4, is that accurate

[haughty mountain]

I don't care about the dp table atm

what numbers can you reach?

[fiery cosmos]

that may be but i don't think i'll understand this if i don't consider that. let me see.. {0, 3}

[haughty mountain]

discussing the mechanics when you don't understand the underlying idea is a bad idea

yes

you either include 3 or don't, i.e. {0, 0+3}

what if I also allow the 7?

[fiery cosmos]

0, 3, 7, 10

[haughty mountain]

expressed in the previous answer?

[fiery cosmos]

reachable_sums = {0, 0+3=3, 0+7=7, 0+3+7=10}

oof

[haughty mountain]

I don't care so much about the 0+3 part now

{0, 3} -> {0, 3, 0+7, 3+7}

and lastly what if I allow 2?

[fiery cosmos]

{0, 0+2, 2+3, 7, 2+7, 3+7, 2+3+7}

[haughty mountain]

why 2+3+7?

I tell you to express it in terms of the previous result for a reason...

{0, 3, 7, 10} -> {0, 3, 7, 10, 0+2, 3+2, 7+2, 10+2} = {0, 3, 7, 10, 2, 5, 9, 12}

you see the overall pattern going on?

[fiery cosmos]

the next subset is generated by adding to each element x in the previous subset, the current element

[haughty mountain]

you either add or you dont

two options for each element

ok, let's take a simple case of the dp then

you start with
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...]

the 0th element is set because you can reach it using 0 elements

actually, maybe we should do different numbers

one thing that didn't appear here were duplicates

[haughty mountain]

take [3, 4, 7, 2]

[haughty mountain]

what's the updated version of this after each number added?

[fiery cosmos]

add 3:
[1, 0, 0, 1, ..., 0]

add 4:
[1, 0, 0, 1, 1, 0, 0, 1, ..., 0]

add 7:
[1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, ... 0]

[haughty mountain]

(you're missing one)

[fiery cosmos]

14?

[haughty mountain]

yes

[fiery cosmos]

ok

alright im with you so far

baby steps

also at this point you should be collecting my profs salary

100%

[haughty mountain]

this sequence is the dp array

[fiery cosmos]

what about the dp table? alternatively, could we instead store the integer itself to allow for subset retrieval once an answer is found

[haughty mountain]

if you have the 2d thing you can do retrieval

like, what I mean that this is the 2d thing

[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...]
[1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...] 
[1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...]
[1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, ...]

this is the table

[fiery cosmos]

oh!

that's actually pretty intuitive

[haughty mountain]

that's why I said it's kinda dumb

it's nothing super clever

[fiery cosmos]

i think of greedy algos as dumb. this is perhaps not sophisticated but i wouldnt call it dumb 😛

ok so my dp table will have n+1 rows and sum+1 columns. and now i get this: dp[n+1][sum+1] = {1 if some subset from 1st to i'th has a sum equal to j 0 otherwise}

bc j runs from 0 through the sum of all elements

[haughty mountain]

if you want to reconstruct a partition with sum s you would start at dp[n][s] and check if you could have gotten there by adding number num[n-1] (here I'm zero indexing)

if you could have, add that number to the partition and subtract num[n-1] from s

(else do nothing)

then n -= 1 and repeat

greedily add things to the partition, going backwards

[fiery cosmos]

huh? you lost me. does this allow for returning the two subsets that gave rise to the minimum difference?

[haughty mountain]

dp[n][s] means you're able to get to sum s by using some subset of the n first numbers

right?

[fiery cosmos]

yes

[haughty mountain]

(specifically dp[n][s] == 1 means that)

ok, what could have caused that 1?

[fiery cosmos]

one or more integers of a subset

[haughty mountain]

be a bit more specific

[fiery cosmos]

some subset of integers from 0 through the ith integer in the input set

[haughty mountain]

I mean going back one step

[fiery cosmos]

🤔

[haughty mountain]

to dp[n-1]

what elements in that row could have caused dp[n][s] to be 1?

[fiery cosmos]

the elements with value 1?

i know what you're asking but fuzzy on answer

[haughty mountain]

what number was added between the rows?

[fiery cosmos]

the ith element in range (0,n) where n is |S|

[haughty mountain]

ith?

[fiery cosmos]

oh n

i was staying away from n bc thats the total number of elements. but yeah n

[haughty mountain]

(n-1 if we 0 index)

[haughty mountain]

ok, so what about this?

[fiery cosmos]

i'm not sure. i want to say any of the 0 through (n-1) elements, but unless we just added a 1, that's unlikely to be the answer?

[haughty mountain]

0 through n-1?

[fiery cosmos]

any elements in the row marked with a 1

oooh

wait wait

wait

just clicked give me second

any of the elements where element + n = s

[haughty mountain]

element + n isn't quite right

[fiery cosmos]

any element in the dp[n-1] row indicated by 1 such that dp[n-1][s] + n = dp[n][s]

[haughty mountain]

not quite right

[fiery cosmos]

im grasping at straws but i kind sort of feel the logic

[haughty mountain]

going from dp[n-1] to dp[n] I had the option to add the n-1 th number

let's call it num[n-1]

so what could have caused a sum of s?

[fiery cosmos]

s - value of num[n-1], or some subset of values in dp[n-1] totaling s?

[haughty mountain]

it's dumber than you think

I either added num[n-1] or I didn't add it

that's the only change between the two rows

so s - num[n-1] or s

[fiery cosmos]

s could have caused s if we added zero, yes

but would that be the best, under such duress and stress

[haughty mountain]

not by adding zero, but by not adding num[n-1]

[fiery cosmos]

ah ok

[haughty mountain]

?

[fiery cosmos]

i made a little rhyme with those two lines. just as i just did this time

[haughty mountain]

so either of dp[n-1][s-num[n-1]] == 1 or dp[n-1][s] == 1 could have caused dp[n][s] == 1

we just want to find some possible partition, so we could just greedily add num[n-1] to the set if it's allowed

[fiery cosmos]

wdym if its allowed

are we building setA beginning from n and going backward

|=

[haughty mountain]

dp[n][s] == 1 and dp[n][s-num[n-1]] == 0

could I have come from num[n-1]?

[fiery cosmos]

i don't understand the "could i have come from" bit

[haughty mountain]

consider the example from before

consider the example from before

let's say we're interested in the partition with sum 9

there are only two possible places that could have set this 1

the option where we don't add the 2 has value 0

so there is no sum 9 using the first 3 numbers

so that's an impossible path

[fiery cosmos]

ok i am beginning to see

[haughty mountain]

but if we added a 2 then things check out

going further back we have two options

either would work

adding 7 would get us back to 0 (7 + 2)

not adding 7 could still give us something valid

if we only care about some solution we could just pick the 7 and be done

but for the sake of the example we could decide to skip it

both possible paths

this is what I mean by "where could I have come from"

I'm trying to backtrace our steps

[fiery cosmos]

ok

[haughty mountain]

to build the path we took

[opal oriole]

A path in the DAG.

[haughty mountain]

hopefully this sequence of images should give a nice idea of it

a path in a DAG but where we don't store the DAG

we just know the rules that constructed it

[opal oriole]

(DAG and DP go hand in hand, but the DAG may be implicit, it's just that one will show up (if you look at the "compute route" or whatever you want to call it))

[haughty mountain]

graphs are everywhere if you have the right mindset 😛

[fiery cosmos]

also this pseudocode as T/F values in the table, will that work?

sry this python code

i don't have the right mindset rn, im completely burnt out from the stress of this semester, my absurd prof telling me to do shit wrong, and covid. still very covid positive. trying to button this up as it is due very very soon

[opal oriole]

(What matters here in DP is that it's directed, acyclic / ordered (a tree) (which is why you need to sometimes first sort stuff))

[fiery cosmos]

we still started from the basis of some sum s we want, but where does such a sum come from

[haughty mountain]

we generate the table which can give us the answer for any sum

in your example where you try to divide into two equal parts you would generate the table and then look at sum/2

(or the numbers nearby if you can't get exactly sum/2)

[fiery cosmos]

how do i put look at nearby numbers into pseudocode

[haughty mountain]

is dp[n][s] == 1? if yes we're done

is dp[n][s-1] == 1 or dp[n][s+1] == 1?

is dp[n][s-2] == 1 or dp[n][s+2] == 1?

...

[fiery cosmos]

smells like a for loop?

[haughty mountain]

yup

for loop and break when you find the relevant thing

when you have the number, you do the process showed earlier to reconstruct

why not write your own thing now that you know what to write?

[fiery cosmos]

i'll replace their T/F statements with 1/0

[haughty mountain]

that way you for sure understand what the code is doing

[fiery cosmos]

^^^

i mean, i do need to know what its doing

and walk through with examples

hence all the practicing

[haughty mountain]

just saying, writing it on your own might actually be quicker than trying to understand some random code

granted, this one should be easy enough

for everyone's sanity, if you're mentioning line numbers

     1    def findMin(a, n):
     2     
     3        su = 0
     4     
     5        # Calculate sum of all elements
     6        su = sum(a)
     7     
     8        # Create an 2d list to store
     9        # results of subproblems
    10        dp = [[0 for i in range(su + 1)]
    11              for j in range(n + 1)]
    12     
    13        # Initialize first column as true.
    14        # 0 sum is possible
    15        # with all elements.
    16        for i in range(n + 1):
    17            dp[i][0] = True
    18     
    19        # Initialize top row, except dp[0][0],
    20        # as false. With 0 elements, no other
    21        # sum except 0 is possible
    22        for j in range(1, su + 1):
    23            dp[0][j] = False
    24     
    25        # Fill the partition table in
    26        # bottom up manner
    27        for i in range(1, n + 1):
    28            for j in range(1, su + 1):
    29     
    30                # If i'th element is excluded
    31                dp[i][j] = dp[i - 1][j]
    32     
    33                # If i'th element is included
    34                if a[i - 1] <= j:
    35                    dp[i][j] |= dp[i - 1][j - a[i - 1]]
    36     
    37        # Initialize difference
    38        # of two sums.
    39        diff = sys.maxsize
    40     
    41        # Find the largest j such that dp[n][j]
    42        # is true where j loops from sum/2 t0 0
    43        for j in range(su // 2, -1, -1):
    44            if dp[n][j] == True:
    45                diff = su - (2 * j)
    46                break
    47     
    48        return diff

[fiery cosmos]

i kept 16-17 and made True into 1

how about this:

[haughty mountain]

```py
code
```

the part with |= is basically

dp[i][j] = dp[i - 1][j] or dp[i - 1][j - a[i - 1]]

but with a range check

[fiery cosmos]

ok

[haughty mountain]

since we don't want to index out of bounds when looking back

[fiery cosmos]

wait how can u have an or after an assignment

[haughty mountain]

you could do this, but it's probably less readable

dp[i][j] = dp[i - 1][j] or (j - a[i - 1] >= 0 and dp[i - 1][j - a[i - 1]])

[haughty mountain]

!e

a = True or False
print(a)
b = True and False
print(b)

[halcyon plank]

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

001 | True
002 | False

[fiery cosmos]

oh does that correspond to the pictures above where its either one row back or value of n-1 element back

like either same column one row back or one row back and n-1 element value back

[haughty mountain]

kinda yeah

if either or the two is 1 this entry should be 1

though the things I show is the backtracking process

not the building the table process

which that loop is