#algos-and-data-structs

1 messages ยท Page 34 of 1

pliant bough
#

which i think will be faster than retrieving data from objects

lean walrus
#

Builtin objects are usually faster than custom, yes

modern gulch
#

Given your cuda reference: i think youโ€™re mixing up list comprehensions with stuff like numpy arrays. Youโ€™ll likely end up using dataframes and numpy, not Python lists.

fiery cosmos
#

Paying someone to help me fix a problem

robust canyon
#

is a binary tree with only the root present (i.e. root with root.left and root.right = None) a full binary tree?

vocal gorge
#

sure, the only node has 0 children, so "all nodes have either 0 or 2 children" is fullfilled.

robust canyon
#

alrighty, thanks!

robust canyon
#

(checking for a perfect binary tree). is this solution the same time complexity as this solution: https://www.programiz.com/dsa/perfect-binary-tree

my solution:

    def is_perfect_binary_tree(self) -> bool:
        #traverse the tree in level order, putting nodes into a dict with the keys as levels like so:
        #{0: [4], 1: [2, 6], 2: [1, 3, 5, 7]}
        level_order_nodes = self.collect_level_info(self.root)

        count = 2
        #go through each level, check how many nodes are in each level (call it width)
        #if the current level * 2 isn't = the next levels width, return false
        for k in level_order_nodes.keys():
            if len(level_order_nodes[k])*2 != count:
                return False
            
            count *= 2

        return True

i think that both time complexities should be O(h) + O(n) (where h is the height of the tree), which comes out to be O(n) ofc. i just want to check

haughty mountain
# 
def perfect_depth(node) -> Optional[int]:
  """
  Returns the depth of the perfect binary tree, or None
  """
  if node is None:
    return 0
  d_l = perfect_depth(node.left)
  d_r = perfect_depth(node.right)
  if d_l == d_r is not None:
    return d_l + 1
  return None
#

I think this would work

vocal gorge
#

is_perfect should be perfect_depth

haughty mountain
#

indeed

opaque galleon
#

guys how do i do this in python 3
there is a string s print True if s has any alphabetical characters Otherwise, print False.

analog echo
#

Get a list representing the alphabet. Then iterate trough it and check if the letter is in the given stringโ€ฆ If every letter is in the string, return True

#

Use this: "abcdefghijklmnopqrstuvwxyz"

inland flax
#

Hello

halcyon plankBOT
#

src/darwinio/distribution.py line 413

def get_points_between_2_points(```
inland flax
#

Is there a better way to do this?

fervent saddle
outer rain
#

Consider a pair or points, for example

(ax, ay), (bx, by) = (4, 7), (10, -2)

Calculate coordinate-wise difference between points

(dx, dy) = (bx - ax, by - ay)

Notice that only the difference matters for the amount of points in the answer, not the positions of points.

How are points distributed on the segment? Well, evenly. I hope this part is fairly obvious, but if it is not, grab a piece of paper and draw a few pictures, you will understand why pretty quickly. This means that every point can be obtained as a + k * d, where K is an integer, which "walks" from 0 to N (where N is some number of points), and d is the different between two consecutive points. Consider an example, in our case the answer is [(4, 7), (6, 4), (8, 1), (10, -2)]. Take the difference between the zero-th and first point (or any other consecutive pair, those are evenly distributed, remember?). That's the vector 2, -3. You can then add it again and get another point, which is also on the segment. And then again, and again, and again, until you end up on the end of the segment. Let's say that the the difference is 1/Nth of the length of the entire segment, and K walks from 0 to N inclusive (N=3 in the example), giving you new points every time.

The goal now is to find maximum N such that for every 0 <= k <= N, k * dx/N and k * dy/N are integers. Of course, k must equal to 1 at some point, so it is only required that dx/N and dy/N are integers. So N must be the maximum integer such that both dx and dy are divisible by N. This is called the Greatest Common Divisor, or GCD, and it can be computed very quickly using the Euclidian algorithm, conveniently built-in into math module.

#

!e
Now, let's put it all together.

(ax, ay), (bx, by) = (4, 7), (10, -2)
(dx, dy) = (bx - ax, by - ay)

import math
N = math.gcd(dx, dy)
answer = [(ax + (dx // N) * k, ay + (dy // N) * k) for k in range(N + 1)]

print(answer)

yeah, that's it. But as you can see, there is a pretty complicated math involved in this little piece of code. Ask me anything if you are still confused, and don't forget to rewrite the list comprehension with numpy.

halcyon plankBOT
#

@outer rain :white_check_mark: Your 3.11 eval job has completed with return code 0.

[(4, 7), (6, 4), (8, 1), (10, -2)]
outer rain
#

@inland flax ^^^^

inland flax
#

Good night

outer rain
#

np!

robust canyon
#

can anyone give me a hand with understanding complete binary trees? i don't understand the "leaning to the left" aspect of them

image.png
outer rain
#

not the "last leaf element", but the "last non-leaf element"

#

anyway

#

every white tree is a "complete binary tree", every red tree is a "binary tree", but not complete

image.png
#

I think that basically all this saying is that if you consider the tree layer by layer, from root then every layer, except possibly the last one, must be full, and the last one can be partially full, but if it is, it must use left-most nodes on that layer

I might be wrong though

robust canyon
#

that sounds about right, i'm going to look into it more though

#

actually this makes a bit more sense now, because nodes should be "filled from the left"

#

here's (what I think is) a much better description:

Every level except the last one is full.
The last level's nodes are as far left as possible.

thorny isle
#

hey, anyone need help?

inner horizon
#

guys anyone know a proper algorithm to get a number which needs the less number of exponents to produce a number when divided by a base number gives the remainder of 1?

outer rain
inner horizon
#

exactly

outer rain
#

So I guess the answer n - 1 just always suffice with p=2 (I assume you are not interested in trivial case of 1)

inner horizon
#

right

inner horizon
pseudo falcon
pseudo falcon
inner horizon
outer rain
inner horizon
#

ffs

outer rain
#

Lol, that happens ๐Ÿ™‚

inland flax
#

I am still confused

outer rain
#

you can ask me questions

#

saying you are still confused does not give me any info about what exactly you now undertand

#

if you want to learn more, you can google something like "integer points on a segment problem", it's a pretty common one

inland flax
#

Anything after vector

#

Why we found hcf etc

outer rain
#

Integer points split line into equal pieces, right?

inland flax
outer rain
#

see how in the example, the segment is evenly divided by the points in the answer

#

[(4, 7), (6, 4), (8, 1), (10, -2)]

inland flax
#

Oh yeah

outer rain
#

the difference between each pair of consecutive points is the same

#

(2, -3)

#

so, if we have the amount of points in the answer, we can divide the difference between the last point and the first one by some integer N and get that difference

#

N + 1 is amount of points in the answer btw

#

is that clear?

inland flax
#

Hmm

#

Wait

#

So you find the number of points between them?

#

But how?

#

Using the difference?

outer rain
#

We have not found it yet, but if we did, we could have used it that way. Actually, our goal from now is to find N.

inland flax
#

Okay

#

How do you find it?

outer rain
#

The difference between the pair of consecutive points is (dx/N, dy/N), where (dx, dy) is the difference between the end points

#

what we want, is to find the maximal N such that both dx and dy are divisible by N

inland flax
#

Thank you so much

outer rain
#

if we consider smaller divisor, we might not find every point, and if we consider larger non-divisor, we will get a non-integer difference

inland flax
#

That's just hcf

outer rain
#

so that's gcd

#

yep

fiery cosmos
#

Anyone know what does it mean?> (blind 75 and neetcode 150) mean? If someone can tell me what this means, it would be greatly appreciated. I noticed this word used by several people who claimed to have done this to get job in FAANG

vast adder
# fiery cosmos Anyone know what does it mean?> (blind 75 and neetcode 150) mean? If someone can...

blind is a website, someone made a list of top 75 leetcode question there: https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU

Blind
New Year Gift - Curated List of Top 75 LeetCode Questions to Save Y...

New Year Gift to every fellow time-constrained engineer out there looking for a job, here's a list of the best LeetCode questions that teach you core concepts and techniques for each category/type of problems! Many other LeetCode questions are a mash...

#

neetcode is a youtuber iirc, he must have made his own LC curation

fiery cosmos
opaque citrus
#

can i ask for a hint on how to implement this infinite series for approximating pi to n terms in the series: (pic attached)

image.png
#

for each term i can write a list comprehension for the denominator and for the plus/minus sign i can test if the term is even or odd

vocal gorge
#

yeah, that'd work

#

or you could even do it the direct way: term = (-1)**(i-1) * 4 / ((2*i)*(2*i+1)*(2*i+2))

inland flax
vast adder
inland flax
# outer rain so that's gcd

no_of_points: int = np.gcd(y2 - y1, x2 - x1)

    m = (y2 - y1) / (x2 - x1)
    dm = int(m / no_of_points)

    x_coords: np.ndarray = np.arange(x1, x2, dm)
    y_coords: np.ndarray = np.arange(y1, y2, dm)
#

Am I doing it right?

#

Nevermind

outer rain
# inland flax no_of_points: int = np.gcd(y2 - y1, x2 - x1) m = (y2 - y1) / (x2 - x1) ...

I don't get what you need m for. And the step size for each coordinate can be different, it's not dm for sure. And other useful correctness metric: consider units. Coordinates are measured in units of distance, m is measured in distance/distance=nothing, and then you add nothing to distance in arange. Something is definitely off here. So no, you are not doing it right ๐Ÿ™‚

inland flax
#

I read your explainatioj again

#

Dy: int = y2 - y1
Dx: int = x2 - x1
no_of_points: int = np.gcd(Dy, Dx)
m = Dy / Dx
dm = int(m / no_of_points)
dy: int = Dy // no_of_points
dx: int = Dx // no_of_points

    x_coords: np.ndarray = np.arange(x1, x2, dx)
    y_coords: np.ndarray = np.arange(y1, y2, dy)
#

Did I get it right this time?

inland flax
#

I feel extremely stupid now

outer rain
#

m and dm are unused now

inland flax
#

I think i am going to get crazy performance gains

outer rain
#

np.arange is exclusive of last value

#

so the last point won't be included in the result

inland flax
#

Hmm, any alternative?

#

Btw will it also work if Dx = 0

outer rain
#

maybe just use linspace instead

#

does it work for integers?

#

oh, it does if you set dtype=int explicitly

inland flax
#

How wait

#

So i dont have to do much of the work?

outer rain
#

So I think it's just

Dy: int = y2 - y1
Dx: int = x2 - x1
# I added 1 here because it's what it does now
#                                 vvvv
no_of_points: int = np.gcd(Dy, Dx) + 1

x_coords: np.ndarray = np.linspace(x1, x2, no_of_points, dtype=int)
y_coords: np.ndarray = np.linspace(y1, y2, no_of_points, dtype=int)
#

oh god

#

= instead of : lol

#

started writing typst there for a moment

inland flax
#

Lol

inland flax
#

Hey, I have an numpy array of 4 ints and these are supposed to represent the genes of an organism. I want to color the organisms according to their genes. For this I used the nilsimsa algorithm and used the hex as the color. But i wonder if there is a better way to acheive this.

halcyon plankBOT
#

src/darwinio/genome.py line 82

def array2hex(array: np.ndarray) -> str:```
sleek otter
#

heya quick question letโ€™s say i have a FOR loop (for x in x) and another FOR loop (for y in y). if these FOR loops are not nested but occur within the same algorithm, is the time complexity O(2n) or O(mn)?

# 
function hello():
  x = [] of length ??
  y = [] of length ??
  for x in x:
    #do something
  for y in y:
    #do something
jolly mortar
#

O(max(m, n))

#

also written as O(m+n)

sleek otter
#

ok thanks

#

<3

crisp turtle
#

Hi guys, i have this question:
The basic idea is a gomoku AI. Board is a 15x15 numpy array, and I am looking for the patterns in the board defined in Three_patterns(for now only horizontal check is alright). Here is my current implementation:

def find_threes(board: Board):  # sourcery skip: use-itertools-product
    board_height, board_width = board.shape
    Three_patterns: dict[str, list[int]] = {
        "open_three": [0, 0, 1, 1, 1, 0, 0],
        "three_left": [0, 1, 1, 1, 0, 0],
        "three_right": [0, 0, 1, 1, 1, 0],
        "broken_three_right": [0, 1, 1, 0, 1, 0],
        "broken_three_left": [0, 1, 0, 1, 1, 0],
    }

    for name, pattern in Three_patterns.items():
        pattern_size: int = len(pattern)

        for row in range(board_width):
            for col in range(board_height):
                if np.array_equal(board[row, col : col + pattern_size], pattern):
                    print(f"Pattern found at {row=}, {col=}, {name=}")

However this implementation is flawed, because if I have a row with [0, 0, 1, 1, 1, 0, 0]...(other elements are unimportant) this will be detected as an open_three, three_left and three_right but i would only want it to get detected as an open three. How could i catche the already found threes?

#

i know i could improve on the search but for now performance is unimportant

vocal gorge
#

You could copy board before starting the search, and whenever you find a pattern, zero out that slice so that it doesn't participate in further matches (or set it to 2, depending on whether you want ones to count as zeros for adjacent patterns).

crisp turtle
#

huh, that actually works flawlessly not sure why i did not think of that

#

another followup questions, what would be the right structure for my code, i will obviously need to do the same checks for patterns of fours and one for five. the main logic will always be:

def find_pattern(board: Board):  # sourcery skip: use-itertools-product
    board_copy = board.copy()                           # i think i always need to define these 3 lines
    board_height, board_width = board_copy.shape
    board_values = board_copy.get_board()               # get values on the board

    Three_patterns: dict[str, list[int]] = {               # patterns specific for function, e.g: you can see the 5 patterns for three, 
        "open_three": [0, 0, 1, 1, 1, 0, 0],               # for four there are 6
        "three_left": [0, 1, 1, 1, 0, 0],
        "three_right": [0, 0, 1, 1, 1, 0],
        "broken_three_right": [0, 1, 1, 0, 1, 0],
        "broken_three_left": [0, 1, 0, 1, 1, 0],
    }

    for name, pattern in Three_patterns.items():          # iterate over the board and look for patterns, horizontally,
                                                          # diagonally and vertically
        pattern_size: int = len(pattern)

        for row in range(board_width):
            for col in range(board_height):
                if np.array_equal(board_values[row, col : col + pattern_size], pattern):
                    # set the pattern to 4, so it does not appear in the next iteration
                    # ? is this the right way?
                    board_values[row, col : col + pattern_size] = 4
                    print(f"Pattern found at {row=}, {col=}, {name=}")

I feel like my functions will have a lot of redundant code, but i also feel that shoving all the patterns into one big function is not the best idea

robust canyon
#

could anyone help me understand why this function works?

def isComplete(root, index, number_nodes):
     
    # An empty is complete
    if root is None:
        return True
     
    # If index assigned to current nodes is more than
    # number of nodes in tree, then tree is not complete
    if index >= number_nodes :
        return False
     
    # Recur for left and right subtrees
    return (isComplete(root.left , 2*index+1 , number_nodes)
        and isComplete(root.right, 2*index+2, number_nodes)
          )

the function checks if a binary tree matches the criteria of a complete binary tree (nodes are filled from the left, any internal nodes have 2 children)

i whiteboarded a few examples and it makes sense that it works, but I don't understand why it works. my biggest confusion is the index, where on the left side we pass in 2*index+1, and on the right we pass in 2*index+2. why do we do that?

gloomy brook
#

It requires a prerequisite in mathematics in computer science. Can i skip it and still learn DSA in this perticular course??

#

anyone ? who have done this course?

modern gulch
#

Looking at the syllabus, it's asking for: "Basic knowledge of discrete mathematics: set theory, relations and logic, combinatorics, proofs, recursion, number theory, graph theory, and probability."

#

I haven't done the course, but those seem like reasonable pre-reqs for a DSA course.

gloomy brook
#

how to get that basic knowledge without doing an entire course?

modern gulch
#

Some DSA courses will assume no prior knowledge of recursion... so if the MIT sequence assumes a certain pre-req, I'd say it's probably not wise to skip the pre-req.

#

Maybe just find a different / more introductory DSA course. Or, just take it and if your'e stuck, go study what you don't know.

gloomy brook
#

Got it. In that case can you suggest one?

modern gulch
#

Maybe ask in #python-discussion for what DSA course people have taken. I don't have any first hand experience with any of the online stuff.

#

(although I've watched many OCW courses and love them)

gloomy brook
#

Oke. thanks ๐Ÿ™‚

crude heath
#

Hi. I've implemented a FIFO and a LIFO queue with lists (using .pop(0) / .pop(-1)), now I need a priority queue (like queue.PriorityQueue) where I can take a look at the lowest-priority entry's priority. With queue.PriorityQueue I'd have to .get that item, then .put it again, which seems like wasted computing time, and I don't care about the queue's thread safety anyway for this use case. Is there a simpler way, e.g. another way to abuse lists for this?

jolly mortar
#

!d heapq

halcyon plankBOT
#
heapq

Source code: Lib/heapq.py

This module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm.

Heaps are binary trees for which every parent node has a value less than or equal to any of its children. This implementation uses arrays for which heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] for all k, counting elements from zero. For the sake of comparison, non-existing elements are considered to be infinite. The interesting property of a heap is that its smallest element is always the root, heap[0].

jolly mortar
#

(also using lists for fifo is not very efficient because pop(0) takes O(n) time, use collections.deque for that)

deep jetty
#

How would you approach this?

prime oar
#

Is there a resource where I can train in optimizing not time, but memory? Leetcode and other resources focus more on time complexity

wooden summit
#

i have a list of lists, for example length of each inner list is like : 4, 3, 3, 1, 1, 2, 5, 5
whats the best way to make sure neither inner list have a lenght of 1 so its combines with others like: 4,3,4,3,5,5

snow anvil
lean walrus
snow anvil
#

not wrong only place I knew to ask tho

#

fixed it anyway

lean walrus
dense zinc
# 
def isDifferenceLowerThanTwo(i1: int, i2: int):
  return abs(i1-i2)<2

So I have this function where it compares two ints. And I'm given a list of ints. Is there a way to filter the list so that comparing each int with each other, only the ones which have at least one True result from isDifferenceLowerThanTwo are left, ordered ascendingly?

So:

input = [1,9,2,6,8,16]
output = [1,2,8,9]

# Ordered list
# 6 and 16 removed since there isn't a single other int inside the list that fulfills the isDifferenceLowerThanTwo condition
modern gulch
#

Is this a leetcode or something?

#

Like, a naive O(N^2) implementation is for each i in input, for each j in input, checking isDifferenenceLowerThanTwo, etc. And then adding to a set or list (if not already in) and sorting.

dense zinc
# modern gulch Is this a leetcode or something?

Similar, the issue is very simplified but the main point is this. The isDifferenceLowerThanTwo function is one I've made, is not part of the problem, and the list is of dictionaries, but the point is the same which is to filter some out comparing with the other elements within the list and then order it

dense zinc
modern gulch
dense zinc
#

Isn't that done with graphs and matrices?

modern gulch
#

If input was sorted, would you need to compare input[i] against every other input?

dense zinc
#

Nope, you're right, only the ones adjacent until isDifferenceLowerThanTwo doesn't fulfill

fiery cosmos
dense zinc
#

Wait there's cleanup to do, it would have repeated values inside filteredArray

modern gulch
#

Yes, and you'd miss some values (1,2,9 wouldn't add the 2, I think)

#

And, why a while loop? If it's sorted, why do you need to check anythign past the next value?

#

Also, you can use enumerate instead of range() there.

dense zinc
#

so there could be a couple

modern gulch
#

If it's sorted by date.

dense zinc
#

Sure, but
value[i] = 10:00:00 # yes
value[i+1] = 10:00:01 # Yes
value[i+2] = 10:00:15 # Yes
value[i+3] = 10:05:00 # No

#

Last one is after 1 minute, the rest are within 1 minute

modern gulch
#

I'm really unclear on what you're trying to do then.

#

But, if you just want to know if, given a value[i], whether there's a value[j] within some X of value[i]... then you had the right idea: but you only need to compare value[i] to value[i+1] (and value[i-1], but yuou can do that in a single comparison) if value is sorted.

dense zinc
#

I see what you're saying, you're right

crisp turtle
#

Hey guys, i have this piece of code. What i want to do is when i find the patterns in the board i want to get their gain squares to create a class object.
What is the best way to do this dynmically if i want to use it for all patterns?

def find_threes(board: Board):  # sourcery skip: use-itertools-product
    board_copy = board.copy()
    board_height, board_width = board_copy.shape
    board_values = board_copy.get_board()

    Three_patterns: dict[str, list[int]] = {
        "open_three": [0, 0, 1, 1, 1, 0, 0],
        "three_left": [0, 1, 1, 1, 0, 0],
        "three_right": [0, 0, 1, 1, 1, 0],
        "broken_three_right": [0, 1, 1, 0, 1, 0],
        "broken_three_left": [0, 1, 0, 1, 1, 0],
    }

    for name, pattern in Three_patterns.items():
        pattern_size: int = len(pattern)

        for row in range(board_width):
            for col in range(board_height):
                if np.array_equal(board_values[row, col : col + pattern_size], pattern):
                    """
                    Here i wanna identify the gain squares e.g.: for open three they are open_three[1] and open_three[5].
                    Then i want to create objects from them:
                    for open_three[1]:
                    Threat1 = Threat(gain_square=board_values[row + 1, col:col+pattern_size], 
                    for open_three[5]:
                    Threat2 = Threat(gain_square=board_values[row + 4, col:col+pattern_size], 
                    """
                    # set the pattern to 4, so it does not appear in the next iteration
                    # ? is this the right way?
                    board_values[row, col : col + pattern_size] = 4
                    print(f"Pattern found at {row=}, {col=}, {name=}")```
fiery cosmos
#

guys any recommendations to learn data structures and algorithms it can be udemy course or yt tutorials

#

is this any good?

image.png
cedar needle
#

Did it way back and realised it doesn't explain Big O as well as any other paid course

#

Best course I found was this one

deep jetty
#

Hey, I have a problem:
Given a M x N grid filled with some values I need to find a path from a target node which maximizes the sum of all values along its path.
I can move in any direction. Path has a max length of x

modern gulch
fiery cosmos
robust canyon
modern gulch
# robust canyon bump ^

The intuition is: that at each depth, either there are no children (both left and right are false) or there's a children at each position of the tree. If the tree is length 3, then there must be a node at position 0, 1, and 2 (0, 20+1, 20+2) and so on. If the tree is complete, a tree with length 5 will have nodes at positions: (0, 20+1, 20+2, 21+1, 21+2). Here's a visualization (sorry for long URL, it encodes your code): https://www.recursionvisualizer.com/?function_definition=from dataclasses import dataclass %40dataclass class Node()%3A i%3A int left%3A "Node" right%3A "Node" tree1 %3D Node(i%3D0%2C left%3DNode(1%2C left%3DNone%2C right%3DNone)%2C right%3DNone) tree2 %3D Node(i%3D0%2C right%3DNode(1%2C left%3DNone%2C right%3DNone)%2C left%3DNone) def isComplete(root%2C index%2C number_nodes)%3A %23 An empty is complete if root is None%3A return True %23 If index assigned to current nodes is more than %23 number of nodes in tree%2C then tree is not complete if index >%3D number_nodes %3A print(f"Index exceeded numnodes {index}") return False %23 Recur for left and right subtrees return (isComplete(root.left %2C 2*index%2B1%2C number_nodes) and isComplete(root.right%2C 2*index%2B2%2C number_nodes) ) &function_call=isComplete(tree1%2C 0%2C 2)

#

So, to simplify: if the left side is None, then the Right side must be None.

robust canyon
#

ah ok, that makes more sense. awesome website by the way, that looks a lot easier to use than a whiteboard

modern gulch
#

I'm having a little hard time verbalizing the point/intuition here too, it's a subtle point: that if the node is None and we've exceeded the number of nodes, then we return false.

robust canyon
#

yea, that makes sense, thank you!

fervent orbit
#

Assuming that I have two objects performing approximately the same motion. Each object has the same size and shape and the duration of the motion of each object is the same. I have access to a 3 dimensional array that consists of:

  • Dimension 1: The n frames of the motion
  • Dimension 2: The n points that the objects consist of
  • Dimension 3: The X, Y coordinates of each point
    Now each point of an object may or may not move the same way as the same point of other would. What I want to do is to find a way to calculate the overall percentage of divergence of the second motion compared to the first motion and which point diverges more. Is there any algorithm I can look at?
robust needle
#

I'm studying an Algorithms class in which we're doing mergesort, and I want to know about the analyzing the time complexity (Big-O) of it. Well, i actually want to know if what I've done is correct. Here's my notes:

#

the only thing i don't quite get why the n log n is next to the c (i.e. the merge function) instead of the T(1), because isn't the splitting the function the 'longer' function?

vocal gorge
vocal gorge
robust needle
#

so, in a sense, each split includes a merge, and so that merge function is what tends to grow more

vocal gorge
#

Yeah, sure. I'd say merging is the actual work and splitting just ends up traversing the entire list once (if the merging wasn't there, the solution would clearly be T(n) ~ n)

slender hound
#

Do someone knows Backtesting py ?

haughty mountain
robust needle
#

well don't u sort the halves only before you merge it?

ember igloo
# 
class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:

        e = sorted(events, key=lambda x: x[0])
        d = {}

        def g(i, j, t, c):
            if i > j:
                return c
            m = (j+i)//2
            if e[m][0] == t:
                return m
            if e[m][0] < t:
                return g(m+1, j, t, c)
            if e[m][0] > t:
                return g(i, m-1, t, min(m, c))

        @cache
        def f(i, k):
            if k == 0 or i == len(e):
                return 0
            a = g(i+1, len(e)-1, e[i][1]+1, len(e))
            if a == len(e):
                x = e[i][2]
            else:
                x = e[i][2] + f(a, k-1)
            y = f(i+1, k)
            return max(x, y)
        
        return f(0, k)

Wrong Answer
66 / 67 testcases passed
https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended-ii/

what am i doing wrong?

#

(returns 300 for the last test case when it should return 304)

wispy stag
# ember igloo (returns 300 for the last test case when it should return 304) 
from functools import cache
from typing import List

class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        events.sort(key=lambda x: x[0])
        n = len(events)
        
        @cache
        def dp(i, k):
            if k == 0 or i == n:
                return 0
            next_event = self.findNextEvent(i, events)
            if next_event == n:
                include_value = events[i][2]
            else:
                include_value = events[i][2] + dp(next_event, k - 1)
            exclude_value = dp(i + 1, k)
            return max(include_value, exclude_value)
        
        return dp(0, k)
    
    def findNextEvent(self, i, events):
        start_day = events[i][1]
        left, right = i + 1, len(events) - 1
        next_event = len(events)
        while left <= right:
            mid = (left + right) // 2
            if events[mid][0] > start_day:
                next_event = mid
                right = mid - 1
            else:
                left = mid + 1
        return next_event
ember igloo
haughty mountain
summer fossil
# 
class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def feasible(days):
            boquets, flowers = 0,0
            for bloom in bloomDay:
                if bloom>days:
                    flowers = 0
                else:
                    boquets += (flowers+1)//k
                    # print(boquets)
                    flowers = (flowers+1)%k
                    # print(flowers)
            return boquets>=m
        
        if len(bloomDay)<m*k:
            return -1

        left,right= 1, max(bloomDay)
        while left<right:
            mid = left + (right-left)//2
            if feasible(mid):
                right = mid
            else:
                left = mid+1
        return left```
#

Can anyone explain me feasible part

#

i didn't understand the question how we make boquets

ember igloo
#

so the fix turns out to have been

        def g(i, j, t, c):
            if i > j:
                return c
            m = (j+i)//2
            # if e[m][0] == t:
                # return m
            if e[m][0] < t:
                return g(m+1, j, t, c)
            if e[m][0] >= t:
                return g(i, m-1, t, min(m, c))
iron harbor
#

Those variable names tho

modern gulch
# summer fossil can u help me to explain this https://leetcode.com/problems/minimum-number-of-da...

The idea of this algorithm is that, for each feasible(days) : you walk through the "bloomDays" left to right and accumulate flowers until you fill a bouquet. If a flower isn't bloomed if bloom>days, then you restart flowers=0 . The else block (inside feasible) says: If I've accumulated enough flowers, add 1 to my boquet boquets += (flowers+1)//k. And, if the flower is in bloom, then add to my bundle flowers = (flowers+1).... but, as a shortcut, use %k so that if my bundle is full, then flowers = 0. The "else" block could've been written as an if statement: pseudocode like: flowers += 1 and if flowers ==k, then add 1 to boquet and set flowers = 0

#

So, as an analogy: You're walking through a row of flowers with a basket that holds "k" flowers. You keep filling the basket until you reach "k" flkowers in the basket. If your basket is full, you make a bouquet: and of course, that means your basket is empty. When/if you reach a flower that isn't in bloom, you put all the flowers in your basket back, and continue.

summer fossil
modern gulch
#

The left and right part is just using a binary search to subdivide the problem so you don't check every day rather than iterating over every day. This shrinks complexity from O(n^2) to O(nlogn), I think.

dense zinc
#

If I want to append to add an element at the start of the list, which is the most efficient method? Is it the dequeue.appendleft()?

modern gulch
#

Just list.insert(0, obj)?

dense zinc
modern gulch
#

Oh, most efficient. Yah, i guess deque.appendleft is supposed to be faster.

dense zinc
#

Okay thanks

vocal gorge
#

it's a tradeoff. if you only need to read/pop/push elements on the sides, a deque is made for it - but getting an element from the middle of a deque is slow, unlike a list.

dense zinc
#

Alright, thanks

summer fossil
modern gulch
# dense zinc Alright, thanks 
# Test List
l = [i for i in range(1000000)]

o = 'abc'
%timeit l.insert(0, o)
# 698 ยตs ยฑ 9.02 ยตs per loop (mean ยฑ std. dev. of 7 runs, 1,000 loops each)

# Test Deque
from collections import deque
l = deque(i for i in range(1000000))
o = 'abc'

%timeit l.appendleft(o)
# 107 ns ยฑ 1.18 ns per loop (mean ยฑ std. dev. of 7 runs, 10,000,000 loops each)
#

Bigger diff than I expected.

dense zinc
#

Damn quite a bit, is it that much better with the normal append too? I gotta try that

modern gulch
# 
# Test List
mylist = [i for i in range(1000000)]

%timeit mylist.append('abc')
# 95.5 ns ยฑ 7.99 ns per loop (mean ยฑ std. dev. of 7 runs, 10,000,000 loops each)

# Test Deque
from collections import deque
myd = deque(i for i in range(1000000))

%timeit myd.append('abc')
# 74.6 ns ยฑ 4.75 ns per loop (mean ยฑ std. dev. of 7 runs, 10,000,000 loops each)
vocal gorge
#

append should be about the same

#

insert at 0, though, is done in O(1) for a deque but O(n) for a list, so up to infinity times faster ๐Ÿ˜›

#

(on the other hand, indexing is the opposite.)

dense zinc
#

Oh alright, thank you!

vocal gorge
#

Sure it does:

l = list(range(10**6))
d = collections.deque(l)
%timeit l[5*10**5] # 49.3 ns ยฑ 3.4 ns per loop (mean ยฑ std. dev. of 7 runs, 10,000,000 loops each)
%timeit d[5*10**5] # 89.2 ยตs ยฑ 943 ns per loop (mean ยฑ std. dev. of 7 runs, 10,000 loops each)
sleek otter
#

quick time complexity question, when writing big o notation, are you allowed to have coefficients? for exmaples O(4n) or would i have to write O(n)

modern gulch
#

we ignore the coefficient, because big O is about asymptotic behavior, where the coefficient is dominated by N as N approaches infinity... but in real world, of course, the coefficient matters.

sleek otter
#

okay thank you

fervent saddle
#

If you're going through the data multiple times, you can call it "two-pass", "three-pass", etc., and "one-pass" if you only go through it once.

vocal gorge
scarlet pagoda
#

Hi

turbid crag
#

Wenegaide waida

#

Wenegaide waider

haughty mountain
#

it's "how does this quotient behave as n tends to infinity"

#

i.e. take f(n) and g(n), how does f(n)/g(n) behave?

#

if it tends to zero or a constant f(n) is in O(g(n))

#

if it tends to infinity or a constant f(n) is in ฮฉ(g(n))

#

if it tends to constant f(n) is in ฮ˜(g(n))

#

having these several notations might seem intimidating at first, but they are literally just what โ‰ค โ‰ฅ and = corresponds to in asymptotics

summer fossil
# 
def findKthNumber(m: int, n: int, k: int) -> int:
    def feasible(num) -> bool:
        count = 0
        for val in range(1, m + 1):  # count row by row
            add = min(num // val, n)
            if add == 0:  # early exit
                break
            count += add
        return count >= k 

        left, right = 1,n*m
        while left<right:
            mid = left + (right-left)//2
            if feasible(mid):
                right = mid
            else:
                left = mid+1
        return left ```
#

Can anyone explain me add part of code

# 
add = min(num // val, n)
            if add == 0:  # early exit
                break
            count += add```
#

This one

modern gulch
#

Imagine num is 10 and val is 3: you know there are three multiples of 3 less than 10: 3,6,9. And, if you want to know how many values in a multiplication table are less than 10, then youโ€™d check 1, 2, 3, 4, and add them up (from 1 to m+1). So, that min function says: for a given num, how many multiples of val are less than it (up to a max of n), and this is wrapped in a loop that adds up for each value from 1 to m+1

summer fossil
modern gulch
#

Youโ€™re asking about why the left/right part is there? Thatโ€™s a binary search that narrows down the lower and upper estimate, until they converge. You donโ€™t need that: you could just iterate over all the n*m values to search for the kth, but the binary search reduces the search space to logn. Its easiest to just step through the function to understand whatโ€™s happening, try pasting the code here and step through the results: https://pythontutor.com/visualize.html

summer fossil
#

I think i understand if add becomes zero that means no values is smaller than nums/mid.

#

Thanks for ur help
i am not able to solve binary search problem how can i solve difficult problem/topics graph and dp

modern gulch
summer fossil
#

I am learning binary search from this i think this a good template

modern gulch
#

If you really want to understand it, start with a simple case, add some debug print statements, and walk through what happens at each iteration. This stuff is really hard to understand intuitively without visualizing it, at least for me

#

Secondly, you should first understand the algorithm without binary search: look at the On^2 linear search. Then see how/why a binary search improves things.

summer fossil
#

firstly i tried brute force than binary search

modern gulch
#

Are you only running the code inside leetcode? Copy it out and run it locally.

#

Itโ€™s good practice to learn how to debug (either with a debugger or print statements), rather than trying to logically decipher the code.

summer fossil
fiery cosmos
#

I started learning Python a month ago, and now that I feel im in a intermediate level, is now the right time to use the start dsa? Or do I need to become more proficient in Python?

summer fossil
summer fossil
fervent saddle
silver tree
#

i am stuck on a porblem in which i have to enumerate all combinations

lets say I have 3 platforms and the following 4 nodes
each node can talk to itself
nodes on the same platform are interconnected
how can i enumerate all possible links on each platform

platform: node
1: 1
2:2,3
3:1

possible links on platform 1 is 1,1 1,2 1,3 and 1,4
possible links on platform 2 is 2,1 2,4 2,3 3,1 and 3.,4
possible links on platform 3 is 4,4 4,3 4,2 , 4,,1

For enumerating all possible links on each platform is it possible to do it with itertools

do u have any guidance

violet jetty
#

Hey guys I need some help here.
Long story short I took DSaA course in the first semester of the last year of university and the course was in java, and now I'm learning python and I wanna learn the data structures in it and solve problems on leetcode, any general tips and advices will be appreciated โค๏ธ

bronze sail
#

Is shelve optmial for collecting results from loops? Lets say I will have million results, can I append 5 reults every iteration or should I just go with csv ?

radiant rose
#

Hey guys, How do I realistically complete data structures and algorithms within 6 months

haughty mountain
#

define "complete"

lean walrus
summer fossil
trail oxide
# summer fossil Can anyone help me

seems like an interesting problem. Can you rephrase you solved it with binary search and now want it solved again with... um, binary search?

trail oxide
summer fossil
summer fossil
trail oxide
# summer fossil Using This Template 
def binary_search(array) -> int:
    def condition(value) -> bool:
        pass

    left, right = min(search_space), max(search_space) # could be [0, n], [1, n] etc. Depends on problem
    while left < right:
        mid = left + (right - left) // 2
        if condition(mid):
            right = mid
        else:
            left = mid + 1
    return left

You just need to implement the condition function here

trail oxide
haughty mountain
# 
def binary_search(l, r, cond):
    while r - l > 1:
        mid = (l + r)//2
        if cond(mid):
            l = mid
        else:
            r = mid
    return l
#

this looks for the largest l such that cond(l) is True

#

and r will be the smallest where cond(r) is False

summer fossil
summer fossil
summer fossil
# 
class Solution:
    def findMin(self, nums: List[int]) -> int:
        def feasible(num):
            if (nums[num]) <= nums[right]:
                return False
            return True      

        left,right = 0, len(nums)-1
        while left<right:
            mid = left + (right-left)//2
            if feasible(mid):
                right = mid
            else:
                left = mid+1
        print(left)
        print(right)
        return min(nums) if len(nums) >= 3 else nums[(left+1)%len(nums)]
#

len(nums) >= 3
any way to modify the code so i don't need to write this statement in feasible part?

haughty mountain
#

l is included in the range, r isn't

lean walrus
haughty mountain
crisp turtle
#

I have a 15x15 numpy ndarray. I need to traverse all diagonals and find patterns which are all 1d lists, with a length of 6 or 7, the problem is if i match a pattern i need to know the starting coordinates of the pattern too, what would be an effiecent to check this?

crisp turtle
#

Yes

#

But if i extraced them, i would not know the starting position of the pattern

#

In the original matrix

#

Could you elaborate please?

crisp turtle
#

E.g.: i have a pattern [2, 3, 4, 5] i would want the output to be (0,1),(1,1),(2,1)

summer fossil
crisp turtle
#

Okay, thanks

#

Will try to implement it

haughty mountain
crisp turtle
#

Could be altered, but yes.

#

@fiery cosmos a follow up question on this one, i have around ~40 patterns stored in lists in another file, then the list is imported.
The patterns are for an gomoku ai.
The porblem is i defined the patterns with 1-s only meaning they are like [0,1,1,0] or [1,1,1] however the players are represented with 1 and 2 on the board so i need to be able to switch beetween the values in runtime.

#

So i would need a switch to convert them into [0,2,2,0] and [2,2,2] respwctivly

#

The pattern, yes

#

I could but not sure how does that help me

#

I wanna avoid duplication of patterns, and i dont want to recreate the whole pattern set everytime i am switching players

wind meteor
#

It is said that bfs and dfs both run in O(V+E) time, does that apply for both adjacency list and adjacency matrix representations?

#

Where in adjacency matrix you may write the big-O as O(V^2) since |E| = O(|V|)

#

|E| = O(|V|^2) **

crisp turtle
#

Yes, but i think i will try to implement it and then get back to you if i need any more help

#

Thanks

outer rain
#

but also usually people only consider adjacency list anyway

#

adjacency matrices are rare and usually used either for compression of dense graphs, matrix multiplication based algorithms (like for counting triangles), or some transitive closure algorithms (think floyd), and if you have a matrix, you can convert it to a adjacency list in O(size of the matrix), which is worse than O(V + E) (unless you have a lot of duplicate edges, which you can get rid off trivially in 99% of the cases), but... I mean... you got that matrix somehow, or at least you have memory for it allocated, so you can spend some time doing something to it, so you lose nothing in big-O terms if you run that first, and then run DFS/BSF/whatever.

#

so if every graph is practically representable with adjacency list, and it is a better repr, why bother with other reprs?

wind meteor
#

It's probably easier to work with adjacency matrices when writing the code out, but the performance is still worse when you have a non-dense graph. Tuple/list indexing to access weight is a constant time operation, and you're not using a significant amount of extra memory

#

I.e. search is still O(V)

#

The extra memory to store weight for each node is linear in the number of edges, so O(E)

#

In non-dense graphs, E = O(V) so, the extra memory totals out to O(V + E) or O(V + V) = O(2V) => still O(V)

outer rain
#

honestly, even for weighted graphs lists are better

#

you just store a pair (to_vertex, weight) and everywhere you need to iterate over edges, simply use for u, w in graph[v] instead of for u in graph[v]

#

it's not much of a difference

#

fair, I guess

stiff quartz
#

Here, NeetCode says his solution is O(m*n*26):
https://youtu.be/vzdNOK2oB2E?t=264

But his code is:

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = defaultdict(list)

        for s in strs:
            count = [0]*26
            for c in s:
                count[ord(c) - ord("a")] += 1
            res[tuple(count)].append(s) 
        
        return res.values()

This is O(m*n + m*26) right? He got it wrong? The 26 coming from the conversion from a list to a tuple.

vocal gorge
#

Sure, you're calculating it better, though remember that O(m*n*26) and O(m*n + m*26) are both O(m*n).

stiff quartz
#

Yeh of course! It was just a hypothetical question in case we are using an alphabet with k letters then it'd be O(m*n*k) or O(m*n+m*k)

vocal gorge
#

Ah, that makes sense.

stiff quartz
#

Although I'm a bit confused as to why the O(m*n + m*26) solution (above) is longer than the O(m*n*log(n)) solution below:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        sorted_strs = []
        for i in range(len(strs)):
            sorted_strs.append(''.join(sorted(strs[i])))
        
        output = []
        already_in_output = {}
        for i in range(len(sorted_strs)):
            if sorted_strs[i] not in already_in_output:
                already_in_output[sorted_strs[i]] = len(output)
                output.append([strs[i]])
            else:
                output[already_in_output[sorted_strs[i]]].append(strs[i])

        return output
vocal gorge
#

What do you mean by longer?

stiff quartz
#

takes longer sorry

#

like 15% longer

#

I'd assume it's purely due to hashmaps overhead?

vocal gorge
#

I'd mostly worry about how long it takes to construct sorted_strs - a loop over all the strings, sorting the characters of each and joining it...

#

(But also, note that leetcode's values are extremely unreliable; the same program resubmitted minutes afterwards can get a much different rating)

stiff quartz
#

Yeh that's where the O(m*n*log(n)) comes from

#

Is there a better way of sorting a list of strings?

stiff quartz
vocal gorge
#

Here I'd say it's a waste of time to construct that list - just iterate over the strings, sorting each right before usage.

stiff quartz
#

Not sure I understand

#

Oh no I do

#

Yeah that's fair enough

vocal gorge
#

I'd write it like this:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mapping = {}
        for s in strs:
            sig = "".join(sorted(s))
            mapping.setdefault(sig, []).append(s)
        return list(mapping.values()) # it's technically not valid to omit list here, since a dict_values isn't a List
stiff quartz
#

I see

#

This is indeed cleaner

#

Complexity is O(len(strs) * len(strs[i]) * log(len(strs[i]))) right?

vocal gorge
#

Yup, that looks right.

#

In practice I expect the sorting solutions to be faster because sorting, while O(n log n), is a very optimized builtin function, whereas counting what characters the string has, despite being O(n), takes a Python loop.

#

like, the complexity implies that for large enough n the counting solution would win, but they'd have to some quite dramatic n.

stiff quartz
#

that's fair

#

thank you for your help!!

vocal gorge
stiff quartz
#

My breaking point is a lot earlier

vocal gorge
#

You're including the generation of the random string, here

stiff quartz
#

that's fair but it's the same for both right?

vocal gorge
#

Sure, it'll just make the difference harder to see

stiff quartz
vocal gorge
#

I was timing these; just the sorting and counting:

s = random.choices(string.ascii_lowercase,k=100000);s="".join(s)
def count_chars(s):
    counts = [0]*26
    for c in s:
        counts[ord(c)-97]+=1 # a
        return tuple(counts)
%timeit count_chars(s)
31.2 ms ยฑ 12 ms per loop (mean ยฑ std. dev. of 7 runs, 10 loops each)
%timeit "".join(sorted(s))
16.5 ms ยฑ 318 ยตs per loop (mean ยฑ std. dev. of 7 runs, 100 loops each)
#

it's interesting that as full solutions the sorting one has more problems

stiff quartz
#

oh no I know

#

in the sorting one i return a list

#

in the non sorting one i return res.values()

#

the conversion must be long

vocal gorge
#

actually the 31ms one seems to have been a fluke:

In [22]: %timeit count_chars(s)
20.6 ms ยฑ 984 ยตs per loop (mean ยฑ std. dev. of 7 runs, 10 loops each)

In [23]: %timeit "".join(sorted(s))
16.9 ms ยฑ 369 ยตs per loop (mean ยฑ std. dev. of 7 runs, 100 loops each)
stiff quartz
# 
from collections import defaultdict

def groupAnagrams(strs: list[str]) -> list[list[str]]:
    mapping = defaultdict(list)
    for s in strs:
        sig = "".join(sorted(s))
        mapping[sig].append(s)
    return list(mapping.values())

print(groupAnagrams(["eat","tea","tan","ate","nat","bat"]))

def groupAnagrams2(strs: list[str]) -> list[list[str]]:
    res = defaultdict(list)
    for s in strs:
        count = [0]*26
        for c in s:
            count[ord(c) - ord("a")] += 1
        res[tuple(count)].append(s) 
    return list(res.values())

print(groupAnagrams2(["eat","tea","tan","ate","nat","bat"]))

import random
random_strings = ["".join([chr(random.randint(97, 122)) for _ in range(10000)]) for _ in range(1000)]
# Big lists (word of size 1000)
%timeit groupAnagrams(random_strings)
%timeit groupAnagrams2(random_strings)

776 ms ยฑ 3.12 ms per loop (mean ยฑ std. dev. of 7 runs, 1 loop each)
682 ms ยฑ 3.12 ms per loop (mean ยฑ std. dev. of 7 runs, 1 loop each)

#

This seems fair right?

#

I don't see where the additional problems in the sorting one would come from

vocal gorge
#

Yeah, that looks right

stiff quartz
#

so taking the n to extreme, big O theory is actually right

#

reassuring

#

hard to see the difference when it's just a log

image.png
vocal gorge
#

The extra time might not be coming from the sorting vs counting here, but from the hashing to access the dict

#

it's hard to say

stiff quartz
#

they both hash as much right?

vocal gorge
#

though that's again something where the counting solution should be advantaged because the length of sig grows with the inputs while the length of tuple(count) is fixed

worn shuttle
#

Is there any suggested roadmap for learning algorithms? What should I learn first, learn last, or is there no real roadmap? And I should just learn whatever comes to mind.

I found this resource, but don't know if its realistic:

NeetCode.io

A better way to prepare for coding interviews.

haughty mountain
stray fractal
stray fractal
#

the counting solution still wins at k=100000 for me

stiff quartz
#

Yeh it did for me too

#

It ended up working I think

stiff quartz
prime sequoia
#

class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle:
return 0

    haystack_stack = []
    needle_stack = []

    for i in haystack:
        haystack_stack.append(i)

        if len(haystack_stack) >= len(needle):
            if haystack_stack[-len(needle):] == list(needle):
                return len(haystack_stack) - len(needle)

    return -1
#

Is this memory-efficient code? because leetcode shows it beats 95 percent in space.

#

66 percent in time

outer rain
#

Btw this solution is super overcomplicated, it is pretty much equivalent to just writing if needle in haystack: ... else return -1. You don't even need stacks.

haughty mountain
#

or if you really want to do things this way you can just use indices

#

if you're fine with a slight risk of error there is polynomial hashing which can do O(n) with O(1) memory

outer rain
#

You can validate solution right after in O(len(needle)) so you can always be correct

#

But in this case it will be possible to build an example where it works in O(n^2), I think

modest temple
#

im not sure if this is the right place to ask but is there any python library that has maths intervals? I want something like x = interval(1.2, 3.2) and the ability to check whether any arbitrary number lies in that interval or not

stiff quartz
#

Interval(0, 1).contains(0.5) -> True

modest temple
#

ofc sympy has them
why does google search shows obscure libraries and not sympy ๐Ÿ˜ญ

#

thank you

haughty mountain
#

1.2 <= value <= 3.2?

#

or do you need fancy stuff like math on intervals?

#

intersections and whatnot

crisp turtle
#

i have this sample code which does the follow:

 x = np.arange(25).reshape(5, -1)
print(x.shape)
x = rotate(x, angle=45)
print("\n")
print(x)
x before permutation:
 [[ 0  1  2  3  4]
 [ 5  6  7  8  9]
 [10 11 12 13 14]
 [15 16 17 18 19]
 [20 21 22 23 24]]
>>>(5, 5)
>>>
[[ 0  0  0  0  0  0  0]
 [ 0  0  0  6  0  0  0]
 [ 0  0  4  9 14  0  0]
 [ 0  3  8 12 16 21  0]
 [ 0  0 10 15 20  0  0]
 [ 0  0  0 18  0  0  0]
 [ 0  0  0  0  0  0  0]]```
 this works as expected,
however when i try to apply it on my code:
```py
board_copy: Board = board.copy()
  board_values: npt.ArrayLike = board_copy.get_board()
  print(board_values)
  print(board_values.shape)
  rotated = rotate(board_values, 45)
  print(rotated)
>>>[[2. 0. 2. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]]
>>>(12, 12)
rotated:[[ 0.00000000e+00  0.00000000e+00  0.00000000e+00  0.00000000e+00
   0.00000000e+00  0.00000000e+00  0.00000000e+00  0.00000000e+00
   0.00000000e+00  0.00000000e+00  0.00000000e+00  0.00000000e+00
   0.00000000e+00  0.00000000e+00  0.00000000e+00  0.00000000e+00
   0.00000000e+00]
 [ 0.00000000e+00  0.00000000e+00  0.00000000e+00  0.00000000e+00
   1.64769036e-04  2.01137262e-02 -8.24857823e-04  6.56837874e-03
   3.73857664e-03 -1.04155600e-02  3.32723879e-04 -3.09713083e-03
   1.77443895e-03  0.00000000e+00  0.00000000e+00  0.00000000e+00
   0.00000000e+00]....```
 why am i getting all these random values?
crisp turtle
#

How can i rotate an numpy 2d array by 45 degrees? without using interpolation

haughty mountain
#

how would you expect that to work?

#

the grids don't match up at all

fiery cosmos
#

Hi I've got a quick question, let's say I have a pandas dataframe with 4 columns, each row of the column either only has one non na value or they're all na. How can I extract that one value in each row or the na value if there is none into one column. I've got methods using .apply to work but my dataframe has more than 200,000 rows so its quite slow. Any way to do this better?

rough compass
silver plover
# crisp turtle How can i rotate an numpy 2d array by 45 degrees? without using interpolation

To rotate a 2D Numpy array by 45 degrees without using interpolation, follow the steps

  1. Import the required libraries:
from scipy.ndimage import rotate```

2. Create a sample 2D array:
```arr = np.array([[1, 2, 3],
                [4, 5, 6],
                [7, 8, 9]])```

3. Define a function to rotate the array by 45 degrees:
```def rotate_array(arr, angle):
    angle = np.deg2rad(angle)
    rotated_arr = np.zeros_like(arr, dtype=np.float64)
    center_x = arr.shape[1] / 2
    center_y = arr.shape[0] / 2

    for y in range(arr.shape[0]):
        for x in range(arr.shape[1]):
            px = x - center_x
            py = y - center_y
            qx = int(px * np.cos(angle) - py * np.sin(angle) + center_x)
            qy = int(px * np.sin(angle) + py * np.cos(angle) + center_y)

            if 0 <= qx < arr.shape[1] and 0 <= qy < arr.shape[0]:
                rotated_arr[qy, qx] = arr[y, x]

    return rotated_arr```

4. Call the function with the array to rotate and the desired rotation angle:
```rotated = rotate_array(arr, 45)
print(rotated)```

The rotate_array function calculates the new position of each pixel based on the given rotation angle using basic trigonometric calculations. The resulting new positions are used to assign the corresponding pixel values from the original array to the rotated array.

Note that this approach might result in some loss of precision due to the discrete nature of the resulting array.

Remember to import the required libraries and define the rotate_array function before calling it. You can modify the function as per your requirements and extend it to handle different cases.
silver plover
# fiery cosmos Hi I've got a quick question, let's say I have a pandas dataframe with 4 columns...

Yes, there is a more efficient way to extract the single non-null value or NaN value from each row of a Pandas DataFrame. You can use the pd.DataFrame.stack() method followed by pd.Series.reset_index() to achieve the desired result.

Here's an example:

import numpy as np```

```# Create a sample DataFrame
df = pd.DataFrame({'col1': [1, np.nan, np.nan],
                   'col2': [np.nan, 2, np.nan],
                   'col3': [np.nan, np.nan, 3],
                   'col4': [4, 5, 6]})```

``` # Extract the single value or NaN from each row
result = df.stack().reset_index(drop=True)```

``` # Output the result
print(result)
Output:

0    1.0
1    2.0
2    3.0
3    4.0
4    5.0
5    6.0```
dtype: float64
By using df.stack(), the DataFrame is converted into a stacked Series object. The reset_index(drop=True) method is then used to reset the index of the resulting Series, dropping the original index and ensuring a continuous numeric index.
crisp turtle
#

Bruh

#

copy pasting chatgpt answers is not very useful

#

i can do it myself too

lean walrus
halcyon plankBOT
#
Rules

10. Do not copy and paste answers from ChatGPT or similar AI tools.

split robin
#

Hi I am currently struggling to understand how Quadtrees and Octrees make Depth Sorting faster

#

This is related to the Painter's Algorithm which is relevant in my computer graphics course and it is mentioned in the script that these trees split the scene into squares/cubes containing at most a certain amount of objects inside of them

#

But the thing I dont understand here is how the tree sorts itself by the position of the viewer

#

its so confusing

#

Wait is it even necessary to sort the tree Thonk

#

Oh I guess it isn't necessary to sort the tree...

#

So the Quadtree/Octree is generated once for the entire scene then?

outer rain
# split robin Hi I am currently struggling to understand how Quadtrees and Octrees make Depth ...

This is very weird. The depth sorting itself is trivial, it is just a normal sorting algorithm. You can't make that faster.

I think it is actually referring to optimizing the polygon intersection. In normal circumstances, you have to intersect every pair of polygons, but by using octrees you can get away with only intersecting polygons in the node. But at the same time, aren't kd-trees better for that?..

vocal gorge
#

Doing a depth sort initially is of course just O(n log n), but wouldn't a tree structure allow inserting new nodes into the sorted tree in O(log n)? don't know if people actually do that, though.

outer rain
#

I don't think there is a benefit from it. Traversing the octree tree in O(n) is probably slower than sorting the array of floats in O(n log n).

feral wigeon
#

guys I'm trying to reverse a linked list and the output should be [3,2,1] but instead the output is [2, 1, None]. Do you guys know why this is ?

feral wigeon
#

This is the file I used for learning Linked lists. I'm still new to Python so I don't know a lot.

lean walrus
# 
def display(self):
    screen = []
    current = Node(next=self.head) # ugly af
    while current := current.next: # nice
        screen.append(current.value)
    return screen
``` ig this should also work
#

i think you should rename your .display() method to .to_list()

#

consider making __iter__ method
it would allow you to do list(a), for example: print(list(a)) or print(*a) instead of print(a.display())

# 
def __iter__(self) -> Iterator[T]:
    cur = self.head
    while cur:
        yield cur
        cur = cur.next
``` something like that
this is essentially a `display` function, but instead of `screen.append(x)` i do `yield x`
#

oh, i noticed a typo here, you should fix it ๐Ÿ˜„

feral wigeon
#

thank you guys so much I was able to fix it.

manic kite
#

In python there aren't really any thread safety problems even if some data structures like lists aren't implemented to be thread safe because python executes a single thread at a time?

lean walrus
#

You're wrong. GIL makes single opcodes atomic, but not groups of opcodes.
So during x.counter += 1 first thread can fetch this value, then second thread fetches, increments and stores here new value, then first increments it and stores.

So, two threads performed +=1 operation, but value incremented only once

#

!e import dis; dis.dis("x.counter += 1")

halcyon plankBOT
#

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

001 |   0           0 RESUME                   0
002 | 
003 |   1           2 LOAD_NAME                0 (x)
004 |               4 COPY                     1
005 |               6 LOAD_ATTR                1 (counter)
006 |              16 LOAD_CONST               0 (1)
007 |              18 BINARY_OP               13 (+=)
008 |              22 SWAP                     2
009 |              24 STORE_ATTR               1 (counter)
010 |              34 LOAD_CONST               1 (None)
011 |              36 RETURN_VALUE
... (truncated - too many lines)

Full output: https://paste.pythondiscord.com/6A42ZV3V5VVCLY4JU6RVSU5BVY

vocal gorge
#

(i dimly remember something about += on ints specifically having been made atomic recently? not sure)

outer rain
#

To add to this, no matter which groups of operations is atomic, you can not guarantee thread safety, unless you have full control over what is shared and what is locked. For example, if two threads execute something like:

if array.len() > 0:
  array.pop()

(overcomplicate this as much as you want: wrap this in classes, functions, whatever)
If the array size is 1, and one thread passes the control flow after the if, before the pop, you will get IndexError no matter what:

array = [element]
# step 1: thread 1 is about to do the "if"
# thread 1             || thread 2
> if array.len() > 0:  |> if array.len > 0:
|   array.pop()        ||    array.pop()

#step 2: thread 1 is about to do the "if"
# thread 1             || thread 2
| if array.len() > 0:  |> if array.len > 0:
>   array.pop()        ||    array.pop()

# step 3: thread 1 is about to do the ".pop()"
# thread 1             || thread 2
| if array.len() > 0:  || if array.len > 0:
>   array.pop()        |>    array.pop()

# step 4: thread 2 is about to do the ".pop()", but the array is empty
# thread 1             || thread 2
| if array.len() > 0:  || if array.len > 0:
|   array.pop()        |>    array.pop()
>                      ||

# step 5: popping from empty array :(

So you still need to care about mutexes and other means of thread safety.

#

ok that's a lie, there are languages where there are no locks, and you are guaranteed thread safety and, unsuprisingly, the lack of deadlocks, but those use different synchronization mechanisms

austere sparrow
outer rain
austere sparrow
#

ah

vocal gorge
somber olive
#

Actually, some one here might also have a good idea on how to approach this: #game-development message I am running into exponential time complexity.

lilac cradle
#

my matrix math is busted because matrices are weird bruh ๐Ÿ˜ญ

#

a 3x2 matrix is 3 tall, 2 wide

vocal gorge
#

it sure is

versed hinge
#

Anyone knows any paper that involves mastering music, what makes a professional mastered track good?

radiant gate
hexed ginkgo
#

@fleet verge i saw noone answered your question before, forgot to send this before the thread was locked, but heres what you were looking for to find the longest consecutive subarray

x=[2, 6, 1, 9,10,11,12,4, 5,6,7,8,9,3]
temparray=[]
prevarray=[]
currlongest=[]

for z in range(len(x)):
    if z==0:
        temparray.append(x[z])
    elif x[z]-x[z-1]==1:
        temparray.append(x[z])
    elif x[z]-x[z-1]!=1:
        if len(currlongest) < len(temparray):
            currlongest = temparray
        temparray = []

print(currlongest)
print(len(currlongest))
fleet verge
#

Ok thanks ,whats the time and space complexity here

#

@hexed ginkgo ??

hexed ginkgo
hidden rock
hidden rock
#

what's the time and space complexity in my script?:
class Solution: def climbStairs(self, n: int) -> int: result = 0 for i in range(n//2+1): j = n - i*2 result += factorial(i+j) / (factorial(i) * factorial(j)) return int(result)

vocal gorge
#

that'd depend on the complexity of your factorial implementation

hidden rock
vocal gorge
#

math.factorial(n) takes roughly O(n log n) i believe
so this loop overall is at most O(n^2 log n).

fiery cosmos
#

how can i add proxies to a python file

solemn moss
vocal gorge
solemn moss
#

Ahh lol

vocal gorge
#

what a funny form though

solemn moss
#

The most interesting realisation of the ||fibonacci|| that i have seen

haughty mountain
#

oh, it this the cute fact about diagonals in Pascal's triangle?

#

i.e. this

image.png
#

my consistency with the triangle wasn't great huh?

chilly burrow
#

I have implemented a bijective base 35 in python from scratch, but I want to ask are there any better ways to do it ( ie some library or inbuilt package)

vocal gorge
#

wikipedia lists this fact without a proof or a reference ๐Ÿ˜”

haughty mountain
#

proof by induction should work though it's a bit boring

#

oh, it might actually be a very boring fact

#

see how it adds things from the two diagonals above?

#

that should be very easy to show inductively

hollow frigate
#

Am I missing something about leetcode-like sites? everyone suggests I should be 'improving' or 'learning' something and if i'm having problems just do more of them, but they dont seem to be educational, more like asking a 5 year old what's the square root of different numbers are until they somehow miraculously come to a viable solution?

#

(aside from the questions seemingly not applicable to real world applications and more just a brain teaser)

modern gulch
#

I think theyโ€™re good measurements of a very narrow ability for certain classes of algorithms.

hollow frigate
#

I guess I was looking for something that could give me off the wall interview like questions but it seems leetcode-likes are more tuned to problem analysis and familiarity with ds/algos which, I dunno it's fine but it's more about if you already understood the problem and are familiar with the solution, and if you're not you're stuck in the sand. There's not many sources explaining the problem analysis to it either so you're stuck just reverse engineering solutions that people post and... well it just doesnt feel very productive

modern gulch
#

Personally, I agree. I might ask one leetcode style question per interview, and only because I want to see whether candidate can work through that class of problem. Itโ€™s a useful skill and shows maturity in thinking, but thereโ€™s plenty of things to learn

haughty mountain
#

Problems that are just "you either know the solution or not" are generally bad interview questions. The good interview questions will assume some basic ds&a knowledge, and will expect you to break a problem apart into managable pieces that can be attacked with this knowledge

#

I generally don't find leetcode a good site. The problems are either badly posed or have really crappy constrainst or test cases (or all of that)

raw stream
#

I am trying to recusively remove adjacently repeating characters from a string and only leave one character such as "Hellllo Worlllld" returns "Helo World", however the issue that I am running into is that repeating characters of more than 2 my algorithm isn't able to remove and leave one character. Is anyone good at recursion and want to check out my algorithm?

haughty mountain
#

Generally just ask the full question already and post the code. Allows people to drop into the channel and help if they feel like it

raw stream
#

Ok so I am trying to recusively remove adjacently repeating characters from a string and only leave one character such as "Hellllo Worlllld" returns "Helo World", however the issue that I am running into is that repeating characters of more than 2 my algorithm isn't able to remove and leave one character. Is there a way to allow me to remove repeating adjacent characters that are greater than 2, and only leave one?

def collapse_string(value, search):
if not value:
return value
else:
if value[0:1] == search and value[1:2] == search:
value = value[1:]
if value[2:3] == search and value[3:4] == search:
value = value[1:]

    `return value[0] + collapse_string(value[1:], search)`
haughty mountain
#

this would technically work, but the slicing is unnecessarily expensive

def collapse_string(value, search):
    if not value:
        return value
    while value and value[0] == search:
        value = value[1:]
    return value[0] + collapse_string(value[1:], value[0])
raw stream
#

They don't want me to use loops of any kind

haughty mountain
#

this then, though again this is slow because of slicing

def collapse_string(s, last=''):
  if not s:
    return last
  if s[0] == last:
    return collapse_string(s[1:], s[0])
  else:
    return last + collapse_string(s[1:], s[0])
#

you can make it neater with a generator

raw stream
haughty mountain
#

that doesn't match what you said before pithink

I am trying to recusively remove adjacently repeating characters from a string

raw stream
haughty mountain
#

regardless, passing an extra argument with the last character seen will make your life easier

#

you can easily modify the function I gave to only apply the logic to a specific character

raw stream
#

So it works, however it seems to remove ever instance of "l" when I replace LAST with SEARCH = "l"

#

I'd want "Helo World"

#

def collapse_string(value, search):
if not value:
return value

`if value[0] == search:`
    `return collapse_string(value[1:], search)`
`return value[0] + collapse_string(value[1:], search)`

print(collapse_string("Hellllo Worlllld", "l"))

lean walrus
# haughty mountain i.e. this

that is cool, despite it is easy to prove

  • horizontal lines - sum up to 2^n
  • diagonal lines (from your picture) - sum up to fib_n
  • maybe other diagonals will result in nice result?

i think, there are even more cool sums in pascal's triangle

#

idk what this is

image.png
#

oeis doesnt have this sequence

#

oh, wait, im dumb
there should be 6 instead of 5

#

reading oeis is now my new hobby
it is crazy how many interpretations this simple sequence has

haughty mountain
vagrant perch
haughty mountain
#

yeah

raw stream
# haughty mountain you can easily modify the function I gave to only apply the logic to a specific ...

I figured out what the issue was, before the logic of my code was if value[0] == search therefore with this logic statement I would remove all instances of search value. But with this new logical statement if value[0] == search and value[1] == search allows me to delete all instances of adjacent repeating characters in the string while also saving one character, so not delete all instances of search. Thank you for the help

#

Seems though with different values it goes out of range interesting

fathom sundial
#

Hi guys, I want to write code to convert my data from a list of strings to a dictionary tree,

This is the sample data

keys_list = [
    'aProperty.aSetting1',
    'aProperty.aSetting2',
    'aProperty.aSetting3',
    'aProperty.aSetting4',
    'aProperty.aSetting5',
    'aProperty.customSettings4.checkThisOut',
    'bProperty.bSetting1.bPropertySubSetting.cData1',
    'bProperty.bSetting2',
    'cProperty.cSetting',
]

I want it to be in this format

data = {
    "aProperty": {
        "aSetting1": 1,
        "aSetting2": 2,
        "aSetting3": 3,
        "aSetting4": 4,
        "aSetting5": 5,
        "customSettings4":{
            "checkThisOut":"you will see"
        }
    },
    "bProperty": {
        "bSetting1": {
            "bPropertySubSetting": True
        },
        "bSetting2": "bString"
    },
    "cProperty": {
        "cSetting": "cString"
    }
}

How can I do this please. I am sure the solution would be using recursion .please note that sample 1 isn't not exactly the same with sample 2, but you get the point, the point is to split the string by the dots into nexted properties.

high wasp
#

hello my best ๐Ÿ˜๐Ÿ˜๐Ÿ˜

fathom sundial
#

I thought about this approach but I think I will have to define a seperate iteration block for each step I want the function to go, because for this scenario, I will be having a string of any depth, meaning it can be like "a b.c.d.e.f"

#

Uhm.. I do not understand, could you give a code snippet

slow perch
#

hello

#

wassup

#

is making algorithm difficult? imma try to do my hw and its difficult for me since i nub

solemn moss
simple cove
#

hi can anyone help me with some theory of computation on propositions?

agile sundial
#

just ask the question

runic tiger
#

Can someone explain this?
A short footpath is divided into four numbered squares. You start at square 1 (at time 0). Time is a series of discrete steps. At each timestep, you either step one square forwards or one square backwards, never standing still. You must not move backwards from square 1. For each square s=1,2,3,4 and each time t=0,1,..., let v(t,s) be the proposition with the meaning:
At time t you are at square s.
How many clauses would be needed in a CNF expression to completely describe the rules of movement for t=0,1,2,3 ?

outer rain
#

even if you consider the most natural ones, it is not obvious

#

for example, you can eliminate about half of all variables if you consider that you cannot stand on even square on even timestamp

#

but generally, to aswer that question you simply introduce boolean variables and then describe relation ships between them in a boolean formula, which you then convert to CNF

#

in this example, you can have t * t variables, X_(time, pos) means that at the time time you are at position pos

#

and then add constraints from the problem

#

I think you need 1) X_(0, 1) is true, which is a unit clase, 2) X_(time, pos) --> X_(time + 1, pos - 1) or X_(time + 1, pos + 1), if in bounds. That's a clause of form (!X_(time, pos) or X_(time + 1, pos - 1) or X_(time + 1, pos + 1)), and 3) X(time, pos) --> for every p != pos, not X_(time, p). That's t - 1 clause for every time.

#

but the question does not really make sense to me

fiery cosmos
#

just learned about the word RAM model of sorting. pretty cool

#

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

Word RAM

In theoretical computer science, the word RAM (word random-access machine) model is a model of computation in which a random-access machine does bitwise operations on a word of w bits. Michael Fredman and Dan Willard created it in 1990 to simulate programming languages like C.

#

is anyone considering making a new map app based on the new dataset? i'll get a link

fiery cosmos
#

is it published what sorts of algorithms are used to operationalize google or apple maps?

outer rain
#

that's pretty much it

#

of course, it is augmented with a lot of additional heuristics

#

landmarks is a big one

fiery cosmos
#

yeah i saw another resource claiming it was dijkstra's and A*

outer rain
#

there are also various tree decompositions methods to help split the problem into smaller parts

#

also maybe some grid heuristics, idk how often those are used though

#

If the graph is not "geographical", you can run force simulation on it in N-dimensional space, and it usually becomes more applicable for A* after that

#

so basically, it's just A*, and seven human-years of work to make it run better for every specific problem

fiery cosmos
#

who developed A*

outer rain
#

I heard that it was an algorithm for a problem on some competitive programming contest

#

and it was a harder version of the problem A

#

so it was labelled A*

fiery cosmos
#

found the original paper

#

1968

outer rain
#

and the name sticked

fiery cosmos
#

Hart, Nilsson, Raphael

#

A Formal Basis for the Heuristic Determination
of Minimum Cost Paths

outer rain
#

that sounds more believable than what I have been told lol

fiery cosmos
whole aurora
# 
if arr is []:
        return 0
    
    for i in range(len(arr)):
        
        if sum(arr[:i]) - sum(arr[i+1:]) is 0:
            return i
    return -1
#

what time complexity would you say this code is?

#

I think its O(n) but I only vaguely understand what that term means anyways

agile sundial
#

probably quadratic

whole aurora
#

Lmao

#

that is tuff.

whole aurora
agile sundial
#

prefix sum

whole aurora
#

I uh, don't get what that means

agile sundial
#

you do a cumulative sum over the array, then do math to get the answer

summer fossil
# 
class Solution:
    def maxConsecutiveAnswers(self, key: str, k: int) -> int:
        l,r = 0,1
        maxa = 0
        while l <len(key):
            while r < len(key)-1:
                if key[l] == key[r]:
                    r+=1
                    
                if key[l] != key[r] and k!= 0:
                    r+=1
                    k-=1
                if key[l] != key[r] and k== 0:
                    break  
                                            
            maxa = max(maxa,r-l+1)
            print("k",k)
            print(maxa)
            print(key[l:r+1])
            l+=1
            r+=1
        return maxa
        ```
summer fossil
summer fossil
#

My approach is moving r until we got key[l] != key[r] and k== 0

#

and we decrease value of k if we got key[l] != key[r]

fiery cosmos
#

Heya! @fiery cosmos

fiery cosmos
willow vapor
#

should all algorithms be less than O(N ^ 2)?

#

why does every tutorial say that it is bad

agile sundial
agile sundial
willow vapor
#

does algorithm has certain limit

#

or do you just keep learning new stuff all the time

glad owl
#

I kind of understand the idea

#

but I think it fails because

  1. greedy narrowing is sub-optimal
  2. iterative narrowing works only when you assume that you replace only 'T' or only 'F'
#

for example, here with k=3:
if you greedily narrow, then each time you'll choose to move the right boundary to the left, because it costs less in terms of length

image.png
summer fossil
#

One more question if anyone?

# 
class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        arr1.sort()
        arr2.sort()
        print(arr1)
        print(arr2)
        def feasible(m):
            print(arr1[m])
            ans = False
            for i in arr2:
                print("diff: ",abs(arr1[m]-i))
                if abs(arr1[m]-i)<=d:
                    ans = True
                    break
            print(ans)
            return ans

        left, right = 0, len(arr1)-1
        while left<right:
            mid = left + (right-left)//2
            print("mid: ",mid)
            
            if feasible(mid):
                right = mid
            else:
                left = mid+1
        return left
    ```
glad owl
summer fossil
glad owl
#

this was my first attempt:
||```py
def solve(s, k, q):
ix = [-1]
for i, c in enumerate(s):
if c == q:
ix.append(i)
if len(ix) <= k + 1:
yield len(s)
return
ix.append(len(s))
i = 0
j = k + 1
while j < len(ix):
yield ix[j] - ix[i] - 1
j += 1
i += 1

class Solution:
def maxConsecutiveAnswers(self, s: str, k: int) -> int:
return max(max(solve(s, k, 'T')), max(solve(s, k, 'F')))

#

important tag:

SPOILER_image.png
#

I solved it very memory-inefficiently, for the benefit of faster times

summer fossil
#

Great!
You have impressive skills

regal spoke
# glad owl this was my first attempt: ||```py def solve(s, k, q): ix = [-1] for i, ...

There is also a pretty nice way to solve the problem without seperately doing it as two cases

def solve(s, k):
  true_count = false_count = j = 0
  for i in range(n):
    if s[i] == 'T':
      true_count += 1
    else:
      false_count += 1
    
    while min(true_count, false_count) > k:
      if s[j] == 'T':
        true_count -= 1
      else:
        false_count -= 1
      j += 1
    
    yield true_count + false_count
sterile ravine
#

hi. wondering if anyone has had experience working with recommendation systems/algorithms. ive found some open source projects and familiarized myself with how theyre made

if you have advice, please tell. thank you

gaunt widget
#

Back after 1 month lol

#

Anyone here?

gaunt widget
#

It is something like this

#

We have to iterate over those 2 arrays ( nested loops )

#

back with internet now let me continue

gaunt widget
#

now we have to subtract those two from eachother and have to compare that with d if it less greater than or equal to it

#

If no element in in array2 can statisfy element of array 1 then we will add 1 to our track variable

#

def distance_value(arr1, arr2, d):
count = 0
for num1 in arr1:
print(f"num1: {num1}")
for num2 in arr2:
print(f"num2: {num2}")
if abs(num1 - num2) <= d:
print("True")
break
else:
count += 1
print(f"count added, new count: {count}")
return count

#

there we go

#

Note i realized that abs was important caus we can also a get a negative subtraction and a negative number is never equal to positive number

south stag
#

I finally learned bubble sort yesterday lmao

#

in python of course, thinking about making it in C++ or C

#

Or Java, I don't know lol

#

ALSO

#

whats the use of binary trees?

haughty mountain
summer fossil
rich gazelle
#

Hey folks,
I want to create an object of type C and add it to a set, there will be duplicates so I want them to be removed.
I know sets use hashing to distinguish between objects, but I have no idea how the objects are hash.
The object will have two fields (string and enum), I can do with the string field being different, that'll be enough.
Help would be appreciated :)

lean walrus
haughty mountain
#
  • implement __eq__
lean walrus
#

Yeah

tribal pendant
#

as said above you absolutely want to ensure (and test) that equals objects imply that they have the same hash, so a == b -> hash(a) == hash(b), otherwise you're up to very nasty bugs (speaking from experience years ago! that I still remember)

ocean glen
#

do we have a polynomial time algorithm to find minimum cost walk to visit all the nodes atleast once?

lean walrus
lean walrus
ocean glen
lean walrus
#

Note that this wiki page also explains why it is the same problem

spice ingot
#

Hi, i'm currently learning python and it's the first time I do some algo and i'm really bad at it so I would like to know if you have some good ressources to be better at algo ?

fiery cosmos
#

anyone here that knows algos at least well?

lean walrus
solemn moss
#

why dontasktoask link is banned :(

gloomy brook
#

hello every one. I need some learning material for data structures and algorithms

lunar sparrow
hexed sinew
#

Or on edx.org the course about data structures and algorithms

#

freecodecamp has made a tutorial on it too

meager cypress
#

hello.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        charset=set()
        x,res=0,0

        for y in range(len(s)):

        ------->while s[y] in charset:   
                charset.remove(s[x])
                x+=1
            

            charset.add(s[y])
            res=max(len(charset),res)```
This is the solution for finding the longest string that doesn't repeat(leetcode 3) .Can anyone tell me why do we use `while` instead of `if`. Doesn't `charset` only contain one copy of every element, using `set().remove(element)` should work if done once.
vocal gorge
meager cypress
#

ahh,you're right

#

it just shifts the string to the next one

meager cypress
robust needle
#

Is there a recursive DP implementation to calculate fibonacci numbers?

#

i figured out a naive recursive, and a iterative DP, but am struggling to get the recursive DP

vocal gorge
#

without it, not sure how it can be done, since the "chain" of recursion will only get you half the needed values. Well, unless you just slap a functools.cache on the function, turning the naive recursion solution into a DP one.

robust needle
#

okay i managed to slap together one (well technically two functions)

robust needle
#

took me a while to grasp it, and i guess you could just have another function that returns only the first part of the tuple

vocal gorge
#

yup

haughty mountain
haughty mountain
#

which is basically never pretty

buoyant schooner
#

Guys, starting off programming

#

Could anyone explain what the string variable means

shut breach
buoyant schooner
#

Sorry about that

sterile ravine
soft apex
#

can someone please help me

#

i can show how to calculate for example uh

limber panther
soft apex
#

just finding the answer

soft apex
#

i understand how the rotations work and balacne factors work but

#

just doing that algebraic expression confuses me a lot

limber panther
soft apex
#

B is connected to hA and hC
D is connected to hE

^ this is oldBal(B)

B is conneceted to hA
D is connected to hC and hE

this is newBal(B)
balance factors values can only be like 1 or 0

i just dont know how to express it alegbraically

soft apex
#

i just dont know how to notate it and solve it liek this

soft apex
fiery cosmos
fiery cosmos
regal spoke
# soft apex

So the definition of balance factor is height of left subtree minus height of right subtree.

regal spoke
# soft apex

There are two errors in that calculation. The sign is wrong after the first =. Also, h_a - h_c isn't newBal(B), it is oldBal(B)

regal spoke
#

The h_a will cancel, and you will be left with some expression involving h_c and h_e

buoyant schooner
summer fossil
# 
def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
        visited = [False]*V
        queue = []
        queue.append(0)
        visited[0] = True
        
        i = 0
        while i<len(queue):
            for v in adj[i]:
                print(adj[i])
                if not visited[v]:
                    visited[v] = True
                    queue.append(v)
            i+=1
        print(queue)
        return queue```
What is wrong in my bfs?
outer rain
summer fossil
outer rain
#

If your graph is a cycle of two vertices, you will visit 0, then 1, then 0 again

summer fossil
# outer rain and?

Given a directed graph. The task is to do Breadth First Traversal of this graph starting from 0.
I think no cycle

outer rain
#

I don't think it says it anywhere

summer fossil
outer rain
summer fossil
outer rain
#

Oh, still no?

#

Lemme see

#

Ohhh

#

You use the index of the head of your queue instead of actual vertex

#

You store vertices in queue, but you never access it

#

And when you do adj[i] you get vertices adjacent to some other vertex, not the vertex at the head of the queue, which is adj[queue[i]]

summer fossil
outer rain
#

ok weird, I don't see anything else

#

!e

def bfsOfGraph(V: int, adj: list[list[int]]) -> list[int]:
        visited = [False]*V
        queue = []
        queue.append(0)
        visited[0] = True
        
        i = 0
        while i<len(queue):
            for v in adj[queue[i]]:
                if not visited[v]:
                    visited[v] = True
                    queue.append(v)
            i+=1
        return queue

print(bfsOfGraph(4, [[1, 2], [0, 3], [0, 3], [1, 2]]))
halcyon plankBOT
#

@outer rain :white_check_mark: Your 3.11 eval job has completed with return code 0.

[0, 1, 2, 3]
outer rain
#

ok, I don't see what I am missing, perhaps someone else will notice

regal spoke
#

Btw I've personally always been a big fan of coding bfs like this in python

#

!e

def bfsOfGraph(V: int, adj: list[list[int]]) -> list[int]:
        visited = [False]*V
        bfs = [0]
        visited[0] = True
        for u in bfs:
            for v in adj[u]:
                if not visited[v]:
                    visited[v] = True
                    bfs.append(v)
        return bfs

print(bfsOfGraph(4, [[1, 2], [0, 3], [0, 3], [1, 2]]))
halcyon plankBOT
#

@regal spoke :white_check_mark: Your 3.11 eval job has completed with return code 0.

[0, 1, 2, 3]
regal spoke
vocal gorge
regal spoke
#

It can also be very convenient to not have to import deque and try to recall what deques methods are called

outer rain
#

Of course it is O(n) worst case, but if you take a random graph, wouldn't it also be O(n)?

#

If that's the case, what is the constant?

haughty mountain
#

you're likely to want some per node info anyway

regal spoke
soft apex
#

18 level 1, 9 level 2, 30, level 3, 50 level 4

#

its 4 correct?

#

thank you

#

@fiery cosmos

#

do you think this is 2?

#

or 1

#

its height of right subtree

#

minus height of leftt

#

so i think its 3 -2

#

or wait

#

2 - 3

#

it might be -1

#

i think its -1?

#

Balance factor of a node in an AVL tree is the difference between the height of the left subtree and that of the right subtree of that node. The self balancing property of an avl tree is maintained by the balance factor. The value of balance factor should always be -1, 0 or +1.

#

it has to be -1 or 0 or + 1 so its not 2

#

and its not 0 because we have an uneven

#

one sub tree is higher

#

The balance factor of a node is the height of the subtree rooted at its left child minus the height of the subtree rooted at its right child

#

ah so +1

#

this example is similar

#

so i think its +1 for sure

soft apex
#

yeah i got it

#

what about this

fiery cosmos
#

im guessing 3

leaden ibex
#

p.s. to highlight code you need triple `

snow anvil
#

!code

halcyon plankBOT
#
Formatting code on discord

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.

For long code samples, you can use our pastebin.

fiery cosmos
#

Where we can hire people?

summer fossil
fiery cosmos
#

what website is that?

#

btw who is telling you that the "secretCode" is always a number

#

that's the problem

#

for somecases the secret code is "\u00a0"

outer rain
#

this a python discord server, and a channel dedicated to algorithms, and you ask why your java code does not compile

#

do not do that

#

(anyway, you probably copied that code from somewhere and it copied with non-breaking spaces instead of normal ones. Just rewrite it, or replace all nbsp-es with default ones)

outer rain
haughty mountain
haughty mountain
outer rain
#

ik, but why doesn't it work for @summer fossil?

#

I can't be just debug prints, right?

#

Because aside from that their code looks ok to me

lament merlin
#

is that like the wrong text formatting?

stiff quartz
#

I'm currently doing this problem: https://codeforces.com/contest/1851/problem/E

My answer uses memoization to avoid calculating the price of potion i twice since calculating it may call loads of other calls and maybe i have done it already.
Here is my code:

from __future__ import annotations

def find_price(pot_idx) -> int:
    if final_costs[pot_idx] is None:
        if pot_idx in unlimited_potions:
            final_costs[pot_idx] = 0
            return 0
        else:
            if mixes[pot_idx]:
                cost_mix = sum([find_price(i) for i in mixes[pot_idx]])
                if cost_mix >= costs[pot_idx]:
                    final_costs[pot_idx] = costs[pot_idx]
                    return costs[pot_idx]
                else:
                    final_costs[pot_idx] = cost_mix
                    return cost_mix
            else:
                final_costs[pot_idx] = costs[pot_idx]
                return costs[pot_idx]
    else:
        return final_costs[pot_idx]


if __name__ == "__main__":
    n_tests = int(input())

    for _ in range(n_tests):
        n, k = map(int, input().split())
        costs = list(map(int, input().split()))
        final_costs = [None for _ in range(n)]
        unlimited_potions = list(map(int, input().split()))
        unlimited_potions = [k - 1 for k in unlimited_potions]

        mixes = [[] for _ in range(n)]
        for i in range(n):
            mix_i = list(map(int, input().split()))
            if len(mix_i) > 1:
                mixes[i] = [k - 1 for k in mix_i[1:]]

        for pot_idx in range(n):
            final_costs[pot_idx] = find_price(pot_idx)

        for cost in final_costs:
            print(cost, end=" ")
        print()

And I have:

Time limit exceeded on test 8

Without memoization I have:

Time limit exceeded on test 4

Can someone help me? I'm a beginner.

Codeforces
Problem - E - Codeforces
velvet parrot
#

Codeforces problems are usually not solvable in python and only in c++

#

because of the time limits

haughty mountain
#

they are usually solvable, especially for something like div3

#

there is also pypy

#

that with enough skill and know-how can get you really really far

fiery cosmos
#

because of the time complexity you can change the code to make a code in python faster

haughty mountain
#

oh there for sure are problems where the intended solution written in python can be too slow

outer rain
haughty mountain
#

ah, nice find

stiff quartz
haughty mountain
#

yeah

stiff quartz
#

Maybe I should use a set for unlimited_potions then?

haughty mountain
#

and yeah

stiff quartz
#

since a set is hashed it's O(1), is that true?

outer rain
haughty mountain
#

you could even put the zeroes in the lookup directly

#

just a loop and set zeroes

#

would also start simplifying the function

haughty mountain
# haughty mountain would also start simplifying the function

if you set the zeroes outside before calling and simplify a bit the function can become

def find_price(pot_idx) -> int:
    if final_costs[pot_idx] is None:
       if mixes[pot_idx]:
           cost_mix = sum(find_price(i) for i in mixes[pot_idx])
           final_costs[pot_idx] = min(costs[pot_idx], cost_mix)
       else:
           final_costs[pot_idx] = costs[pot_idx]

    return final_costs[pot_idx]
stiff quartz
#

that's fair yeah

haughty mountain
#

annoyingly, no really nice way to remove the inner if-elaw

stiff quartz
#

So update, I got past test 8 thanks to your idea

#

But runtime error on test 12 so I guess I made another mistake haha

haughty mountain
#

recursion depth probably

stiff quartz
#

STATUS_STACK_OVERFLOW

#

Is that recursion depth?

stiff quartz
haughty mountain
#

sounds like it

stiff quartz
haughty mountain
#

when I do contest problems in python I usually avoid recursion if I can

#

though maybe you can get by with increasing the limit this time

stiff quartz
#

I already had

#

sys.setrecursionlimit(2*10**9)

#

I don't know what's the maximum though

agile sundial
#

that probably is above the maximum if you got a stack overflow, lol

haughty mountain
#

it worked for smaller cases

stiff quartz
#

mmmh

outer rain
#

resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))

#

This may help

#

No promises though

stiff quartz
#

I'm thinking how I can make it so that it's not recursive

haughty mountain
#

you need to evaluate things in the right order

stiff quartz
haughty mountain
#

so it turns into a graph problem

outer rain
#

๐Ÿ˜ฆ

haughty mountain
#

find a topological ordering of a DAG, compute in that order

outer rain
#

There is also starting a new thread with bigger recursion limit, I don't remember if that is allowed on cf though

#

Anyway, better rewrite non-recursuvely

agile sundial
haughty mountain
#

it shouldn't

#

@regal spoke want to advertise your recursion bootstrapper?

stiff quartz
#

I know what is a DAG but that's about it

haughty mountain
#

a topological ordering is an ordering where the "dependencies" of a node are always before the node itself

stiff quartz
#

oh so knowing what's the right order is

#

like i need to find the potions which depend on no mixes

#

then the one that depends on no other or the ones i just computed

#

etc etc ?

#

and this iteratively

#

(btw thank you so much guys for helping)

haughty mountain
#

one simple algo that I like is conceptually that you keep chopping off leaves of the DAG

#

chopping off a leaf might expose a new leaf that is now valid to pick

#

seems this is known as Kahn's algorithm

Topological sorting

In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one ta...

stiff quartz
#

oh so you make the graph, then you sort it, then you process the leaves, you chop them off, you process the leaves, etc ...

haughty mountain
#

no sorting

#

in this algo you would find all leaves, and then keep removing leaves until you have nothing left

#

the order you process the leaves is a topological ordering

stiff quartz
#

oh ok

#

so now I just need to figure out how to create the graph

#

obviously the first leaves are the "free" potions

regal spoke
stiff quartz
regal spoke
#

I linked to an iterative solution in my comment on that blog

stiff quartz
#

Well thatโ€™s where my second question comes in, if I start doing harder contests are there questions that are not solvable on python just because it takes too much time?

#

Compared to a compiled lang

regal spoke
stiff quartz
#

Thatโ€™s fair

haughty mountain
#

but you might need to fight for it...

regal spoke
#

But you sometimes need to put in a lot more work of getting the code to not TLE even if you have the intended solution

stiff quartz
#

I wouldโ€™ve assumed they put different time limits

#

Depending on the language haha

haughty mountain
#

codeforces doesn't

#

other sites do

stiff quartz
#

Do you know what isograd does? Iโ€™m training on codeforces because my uni organises a competition next year on isograd and isograd doesnโ€™t have a ton of problems

#

Sorry if Iโ€™m getting off topic btw

regal spoke
#

I don't know about isograd

haughty mountain
#

in the distant past when I competed I used python when I was confident it would be fast enough without too much hackery, but switched to C++ when I felt I needed raw performance

#

pajenegod is more of a python masochist than me ๐Ÿ˜›

stiff quartz
#

To come back to the DAG graph

#

It's gonna be O(nยฒ) just to build it right?

haughty mountain
#

why nยฒ?

regal spoke
stiff quartz
#

I need to iterate through all the potions, to add the easiest ones, than re-iterate to add the ones I can make using the ones I already solved, than re-iterate to add ... and this maybe n times because maybe potion n needs n-1 which needs n-2 which ... needs 1

#

I'm definitely missing something

snow anvil
stiff quartz
#

yeh something like this right?

#

oh i just realized, you literally code a graph

#

like a dictionary of nodes and value is a list of the other nodes it goes to?

snow anvil
#

it just irked me that you said directed ... graph graph don't mind me

stiff quartz
#

and that's O(m) m the number of edges

stiff quartz
haughty mountain
#

there you would find leaf e, you remove the edges going to e and note that d is a new leaf

fiery cosmos
#

hey guys good resources to learn in deep cp?

haughty mountain
#

then remove the edges to d and b and c are exposed as leaves, ...

#

you can do this pretty lazily

stiff quartz
#

ok and my initial set of leaves is literally the set of "free" potions?

#

the one i used to treat as a list and that cost me O(n) instead of O(1)

haughty mountain
#

I haven't read the problem closely, but I think yes

stiff quartz
#

I'm gonna give it a go!

haughty mountain
#

this is worth learning regardless

#

DAGs and topological orderings pop up a bunch

stiff quartz
#

I actually thought competitive programming was easy before starting to train for it a few weeks ago

#

damn

#

but it's cool i really like it

haughty mountain
#

getting to div3E within a few weeks isn't too shabby

stiff quartz
#

well it took me a bit more than the time of the competition

regal spoke
# stiff quartz

There are two ways to find a topological ordering of a DAG.

  1. Either do what @haughty mountain is saying and pick and remove one leaf at a time

  2. Or do a dfs and pick and remove the outer nodes first (which is what my iterative solution does).

Both of these are common ways to find a topological ordering. For your graph you should end up with either [e,d,c,b,a] or [e,d,b,c,a] (both are valid topological orderings).

haughty mountain
#

ah right, you can also do a dfs to get a topological ordering

regal spoke
haughty mountain
#

and you get to learn how to do an iterative DFS

#

which also generalizes to BFS

#

and Dijkstra

regal spoke
#

I think that competitive programming is a great complement to theoretical algorithmic studies. In competitive programming you get to learn to apply and implement algorithms

stiff quartz
#

(i'll answer in five minutes i'm just trying to understand why my solution doesn't work right now ๐Ÿ’€ )

stiff quartz
#

so you need a copy of the dag in which you remove the edges but you need to keep the original dag?

stiff quartz
stiff quartz
stiff quartz
haughty mountain
#

e.g. it's enough to keep track of the number of children

regal spoke
#

Then you ignore any node that has already been removed

haughty mountain
stiff quartz
#

It's probably a disaster complexity wise though

#

Everytime I remove a leaf I did this

#

I was doing the fiery frumpy fenix option

regal spoke
#

ye

regal spoke
stiff quartz
#

Makes sense

haughty mountain
#

as said, the thing I usually do is keeping a count of children

stiff quartz
#

Yeah but when you remove a leaf

#

You can't access its parents

#

Easily

#

Without going through all the nodes

#

Unless you also a keep of parents for each node

haughty mountain
#

you can build a reverse graph

stiff quartz
#

Which i guess would be fine (trade off space complexity time complexity?)

regal spoke
#

Btw I dont think that children/parent is a good terminology for a DAG.

#

It is commonly used for trees

stiff quartz
#

Yeah makes sense

#

A tree is a DAG right?

#

Hence my confusion

regal spoke
haughty mountain
#

a rooted tree is a DAG

stiff quartz
#

yep makes sense

#

ok i understand why you both say rooted

regal spoke
stiff quartz
#

my graph is a dict[int, list[int]], is that the correct data structure for it?

#

I feel like if I want to build a reverse graph it might be complicated complexity wise

haughty mountain
#

that's fine

stiff quartz
#

Oh no I can just create it in parallel of creating my initial graph

haughty mountain
#

though you could even use list[list[int]]

regal spoke
haughty mountain
#

using a set instead of a list in the inner part is also an option that can sometimes be useful, if you need to be able to remove quickly

regal spoke
haughty mountain
#

you can usually do other things yeah

#

e.g. in this toposort case a fast remove might be nice, but you can also just keep track of the number of out edges

regal spoke
stiff quartz
#

makes sense

#

my brain is currently exploding

haughty mountain
#

as it should

#

information overload is always fun

stiff quartz
#

damn ok i implemented it

#

but I think

#

it's too slow because removing an element from a list is too long

#

removing from a set is O(1)?

#

i guess yeah it makes sense

regal spoke
stiff quartz
#

a set is basically elements that are not contiguous in memory

#

and to find the reference

#

you hash the integer for example

#

and it gives you where the element is (by pointing to an index in an array)

#

along with a bit saying if it's in the set?

#

first time in my life i have a memory limit ๐Ÿ’€

image.png
regal spoke
#

Btw I took a peek at your code. I think it would be a lot easier for you if you just started by creating topological ordering, and then use that topological ordering to solve the problem

#

It is a lot easier to solve the problem in steps

stiff quartz
regal spoke
stiff quartz
#

wait how the hell did you find this

#

๐Ÿ˜†

regal spoke
#

I knew which problem you are solving, so I went into status and sorted by last submission for that problem

stiff quartz
#

oh fun

#

Oh I understand what you mean

#

First I create an array of what nodes to look at

regal spoke
regal spoke
stiff quartz
#

Ok it's true that it's a lot more readable

#

But as expected it didn't change time nor space complexity

#

Maybe maintaining a dag AND the reverse dag is too expensive

regal spoke
#

The variable leaves should be initialized as all nodes u for which dag[u] is empty

stiff quartz
#

I think that's what I'm doing?

# 
        cannot_be_created_with_mix: set[int] = set()
        for i in range(n):
            mix_i = inlt()
            if len(mix_i) > 1:
                dag[i] = set([x - 1 for x in mix_i[1:]])
                for child in dag[i]:
                    reverse_dag[child].append(i)
            else:
                cannot_be_created_with_mix.add(i)
                dag[i] = set()

        # Leaves = cannot_be_created_with_mix
        leaves: list[int] = list(cannot_be_created_with_mix)
regal spoke
#

Yes I think so

#

You should just use something like leaves = [u for u in range(n) if not dag[u]]