#algos-and-data-structs

1 messages · Page 26 of 1

naive oak
#

yeah

#

it's something called the master theorem

long plume
#

I found this online, and was wondering why they stopped at T(1)=0

image.png
naive oak
#

how many comparisons do you need to merge sort a one element array

long plume
#

Oh, I have not answered this as well

long plume
naive oak
#

why would it compare itself with itself

long plume
naive oak
#

exactly

long plume
#

What about this though? Is it just n(n-1)/2?

naive oak
#

yeah

long plume
inner spade
#

Hello guys, can anyone give direction on how i can work with this xml type of files. (there are files i send, and then files i receive).
same service run on API but i didn't yet access that,
Is there any method i can use ? or library ?

image.png
silver lotus
#

Hey all, I have a question, given a grid like this; grid = [
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 4, 0],
[0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0],
[0, 1, 1, 5, 1, 5, 1, 0, 1, 0, 1, 0],
[0, 0, 1, 0, 0, 5, 1, 0, 1, 1, 1, 0],
[0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0],
[0, 3, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]
How would i go about finding the shortest path from the start point 3 to end point 4, while passing by all the 5? (1 indicates open path, 0 indicates closed path, 5 indicates must pass points)

outer rain
# silver lotus Hey all, I have a question, given a grid like this; grid = [ [0, 0, 0, 0, 0,...

Have you figured out how to solve a problem you wanted to solve before? This one is harder.

Let points 3, 4 and 5s be called checkpoints. Run bfs from every checkpoint to compute the shortest path between every pair of checkpoints. Build a complete graph which vertices are checkpoints and edges have a weight equal to shortest distance between a pair of checkpoints. Solve the traveling salesman problem on that graph. There is a fairly simple dynamic programming algorithm in O(n^2 * 2^n). In total it would work in O(n^2 * k + k^2 * 2^k) where k is the amount of checkpoints.

silver lotus
peak matrix
#

hi all may I what is the best stop condition for left hand wall follower algorithm, assuming there is no path to the destination?

robust dagger
#

When you return to the original location.

peak matrix
#

thank you very much i solved my problem

#

I wrote an algo that produces a perfect maze as such but may I know how do I convert the perfect maze to a non perfect one so that there are more than one possible path from one point to another. This is to increase the difficultly of the maze solving.
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
[0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0],
[0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0],
[0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0],
[0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0],
[0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
Thank you

outer rain
peak matrix
#

back tracking

outer rain
#

Also wdym by "the difficulty of maze solving"? Are you trying to heuristically increase humans' confusion?

#

In that case you can randomly destroy the wall that goes to the dead end you have already traversed if the distance to the start of the maze between the dead end tile and your current tile is relatively small.

#

The constant parameters will require a little tweaking, but I think this can be done. Tbh it's purely experimentation at that point. Just try out stuff and see what works for you.

silver lotus
outer rain
silver lotus
#

Yea bitmask for the dp right?

outer rain
# silver lotus Yea bitmask for the dp right?

Bitmask (or bitset) is basically a set of numbered objects represented by bits in the number. For example if you have 3 objects A, B, C, you can represent a set, say {A, C} as 0b101 (binary number 1*4 + 2*0 + 1*1 = 5), set {A, B} as 0b011, or {A, B, C} is 0b111. You may notice how if object k is in set, the k-th lowest bit is set to 1 and vice versa. This is a very compact representation which usually only takes a few bits, which fit in a single integer, allowing to do some sick stuff with it. Want to intersect 2 sets? Do binary and (pipe operator: |). Want to add element numbered k? bitset |= 1 << k. Empty set? Easy, just 0. You should probably read about bit manipulation yourself, there is lots of cool stuff out there. In the dp you need to use bitmasks as indexes in your dp. You can think of it as map which uses sets of vertices as keys, but more efficient.

By the way, I said that DP algorithm of solving TSP is "fairly simple" but if you struggle with it I suggest you using the trivial algo which works in O(n*n!). If your amount of checkpoints is about 10 it would take about one second. The DP approach usually works in under a second if n < 20. Is implementing it worth it? Sorry for possibly sending you in the wrong direction. I should have asked constraints first.

The trivial algorithm is super easy: iterate over every permutation of 5s in the graph you build and trivially calculate the length of the path from start to end visiting every 5 in the order of permutation.

silver lotus
outer rain
silver lotus
silver lotus
# outer rain Yes, I don't know a simpler way

By the way for my previous problem, I tried solving in another way because I wasnt so familiar with your proposed solution: Use BFS to label each node with distance from start node, then use DFS to find all paths from the start node to the end node such that the depth increases for each step of the path

outer rain
silver lotus
#

Yea, do you happen to know what is the O

outer rain
# silver lotus Yea, do you happen to know what is the O

In best case O(n) where n is the area of a grid if there is a single path to the end. In the worst case it's O(ans), same as what I proposed. There isn't a way to solve it faster though. By the way I said that I believe ans is always less than n^2 on grid graphs, but I was super wrong. It's more like O(2^sqrt(n)) (this is achieved if there is no walls at all, and start and end are on the opposite corners of the map) but I'm still unsure if this is the real upper bound.

Edit: no sqrt in big-O, I messed up my math

Edit 2: yes sqrt in big-O, but in a different place. I messed up my math again!!1

silver lotus
outer rain
#

I'm super bored anyway so glad to help

silver lotus
outer rain
#

This is an opposite - a specialized version of TSP

silver lotus
outer rain
#

Seems like it

silver lotus
# outer rain Seems like it

Hey, sorry another question, is there a more efficient method to solve the 2 problem scenarios i mentioned in terms of time complexity?

outer rain
# silver lotus Hey, sorry another question, is there a more efficient method to solve the 2 pro...

No one knows, of course, if P=NP there is a polynomial algorithm for sure.

As far as I'm aware, (big-O wise) there is no known algorithms for solving TCP in o(2^n). There are a lot heuristically more optimal algorithms though.

I don't know if your specific problem can be solved faster though. It probably can be reduced to some faster ILP, but I don't know how. But it's definitely NP-complete. You would be able to find Hamiltonian paths in planar graphs otherwise, which is NP-complete problem.

#

So if P != NP the there definitely would be an exponent in the big-O, the base might be smaller than 2 but I don't know how to achieve this. I also don't know if the power itself can be smaller than k.

silver lotus
outer rain
silver lotus
#

Can you help me see my program please

silver lotus
# outer rain If your algorithm is `O(n^2 * 2^n)` and grid size is less than 1000x1000 - No. I... 
for i in range(len(grid)):
    for j in range(len(grid[0])):
        if grid[i][j] in [3,4,5]:
            checkpoints.append((i,j))
m, n = len(grid), len(grid[0])
graph = {}
for i in checkpoints:
    graph[i] = {}

def bfs(start, end):
    queue = Deque([(start, [])])
    visited = set()
    while queue:
        curr, path = queue.popleft()
        if curr in visited:
            continue
        visited.add(curr)
        x, y = curr
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            neighbourX, neighbourY = x + dx, y + dy
            if 0 <= neighbourX < m and 0 <= neighbourY < n and grid[neighbourX][neighbourY] != 0:
                if (neighbourX, neighbourY) == end:
                    return path + [(neighbourX, neighbourY)]
                queue.append(((neighbourX, neighbourY), path + [(neighbourX, neighbourY)]))
    return []

for i in checkpoints:
    for j in checkpoints:
        if i != j:
            graph[i][j] = bfs(i, j)


# employs a recursive backtracking approach (the tsp function), which generates all possible permutations of visiting the checkpoints and finds the shortest path using Breadth First Search
def tsp(mask, pos, path):
    # If all the checkpoints have been visited, return the path
    if mask == ( 1 << len(checkpoints) ) - 1:
        return path
    res = []
    for i in range(len(checkpoints)):
        if not (mask & (1 << i)):
            new_path = path + graph[checkpoints[pos]][checkpoints[i]]
            tsp_result = tsp(mask | (1 << i), i, new_path)
            if len(tsp_result) > 0 and (len(res) == 0 or len(tsp_result) < len(res)):
                res = tsp_result
    return res

def shortest_path(grid, start, end, checkpoints):
    result = tsp(1 << checkpoints.index(start), checkpoints.index(start), [start])
    return result
    
print(shortest_path(grid, (7,1),(2,12),checkpoints)  )```
outer rain
silver lotus
# outer rain What's the grid size?

grid = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
[0, 1, 5, 1, 5, 1, 0, 0, 0, 0, 0, 1, 4],
[0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0],
[0, 0, 0, 0, 5, 1, 0, 1, 0, 1, 0, 0, 0],
[0, 1, 1, 1, 5, 1, 0, 1, 0, 5, 0, 1, 0],
[0, 1, 0, 1, 1, 0, 0, 1, 0, 5, 0, 1, 0],
[0, 3, 1, 1, 1, 1, 5, 1, 5, 5, 1, 1, 0],
[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

outer rain
# silver lotus grid = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [5, 1, 1, 1, 1, 1, 1, 1, 1, 1,...

Your TSP works in O(n*n!). It stateless and does not store the intermediate results. It basically checks every single possible path and returns the shortest path among every path... The easiest way to fix it is to get rid of path from function parameters (to make tsp only return the path from pos to the end) and add @functools.cache decorator to tsp. It will do memoization for you and every shortest path is going to be only evaluated once and cached.

Was tcp generated by Chat-GPT?

silver lotus
silver lotus
outer rain
silver lotus
silver lotus
outer rain
silver lotus
# outer rain Yes

Hey, may I ask for the BFS for calculating shortest path between every pair of checkpoint, would it be faster if A* is used?(for tsp)

outer rain
silver lotus
outer rain
#

Failing is too cheap to not try

silver lotus
#

ur right thanks

fiery cosmos
#

Hello there, we found a puzzle or some kind of code regarding people that are probably working (or being in recruitment process) for Polish or Russian special services - military intelligence, support and counterintelligence. No one seems to be able to solve it… maybe you could?

80-g. d-4n 8r. 0d- 5ky1 - Uptime Development, Przasnyska,
49n-1e. 57-k. 4 K. r-ó 1, Oerlikon, 83773R 3n3rgy,
M-1k. 01-4. j 5. 0n-d. 3j, Traveller, 5F,
Hu-b. 3-rt J. 4-m. r0-z. 1k - exInter Polska, Włodarzewska,
K-4r0. l1n-4 L1-w1ń. 5k4 BAT, Wyścigi Służewiec,
94. try-cj. 4 Ur. b4-n. 3-k, in USA,
L-y. d1-4 6. 4-vr. y-l1. v, 83773R 3n3rgy,
1-9. 0r 5-k4. w1-n. 5-k1, Fly Focus.
M. 4-6d. 41-3n. 4. J4-r. 0-57, 83773R 3n3rgy,
K. 47- 4r7. yn4 6 4-w3 nd. 4 - Leasys, Garwolin, Accounting,
J04nn4 5k4tu15k4, Zoofocus, Makolągwy,
94w. 3ł C. hr-u 57. c7 3-w 5. ki - PIT RADWAR, 6PS-2OO-SO2,
D0m1n1k4 Kn1tt3r, D0D0, Traveler, in Costa Rica,
K4r. 1n-4 R3. 7 n-3r, Actress, WUM,
J. 04-n n4 (N. 4-6ł. 0-n3. k) C-up. r1-4. k, Legal,
M1ch4ł 4d4m14k, BAT, Turek,
Jul14 Ł0w1ń5k4, Warsaw Film School, Bruna.

buoyant monolith
#

Not sure this belongs in this channel

haughty mountain
#

3 → E
8 → B
...

pliant oyster
#

best sources to learn DSA?

stoic moat
modern coral
#

Hi everyone! Can somebody recommend books/courses about algos and data structs while I learn python syntax(googled suggestions differ vastly)? Sorry if the info about it is presented somewhere on this server.

outer rain
#

@pliant oyster @modern coral don't overthink. If you read a book try to actually read it as little as you can and practice more. Usually when studying with a good resource people begin to procrastinate and say to themselves "I will first finish a book, and then practice once I learn the basics", but even after finishing the book they realize how they learnt nothing and become frustrated while practicing. Aside from that,

#

!resources

halcyon plankBOT
#
Resources

The Resources page on our website contains a list of hand-selected learning resources that we regularly recommend to both beginners and experts.

modern coral
#

Thanks @outer rain !

flat sorrel
#

I wonder whether it is possible to write a decorator to convert any recursive function into an iterative one

keen hearth
flat sorrel
#

so as to preserve readability

keen hearth
#

You'd have to have some way of distinguishing the recursive calls from the non-recursive ones.

#

Maybe by inspecting the call stack?

flat sorrel
agile sundial
#

that would be super cool

flat sorrel
#

well, the first step would be to implement our own call stack that listens to when the wrapped function gets called

#

actually it would need to be a call graph

outer rain
#

You can build a call graph, find calls which cause recursion (mutual recursion exists so you will have to deal with that). Then we must somehow analyze the function to build, say, a state machine. For example

def phi(x):
  if x <= 1: return x
  return phi(x - 1) + phi(x - 2)

has three states. Before first recursive call, after but before the second, and after the second. So you can unwrap it into something like this:

# we will need a return stack with values which functions return,
# a state stack, which is similar to return addresses in normal recursion
# and a local variables stack which is not really used here
def phi(x):
  state = pull_state_from_a_special_stack()
  match state:
    case 0:
      if x <= 1: return push_value_onto_return_stack(x)
      put_state_on_a_special_stack(1)  # we will continue from state 1
      put_locals_onto_stack(locals())
      return now_call_this(phi(x - 1))
    case 1:
      pop_locals_from_stack(locals())
      put_state_on_a_special_stack(2)
      put_locals_onto_stack(locals())
      return now_call_this(phi(x - 2))
    case 2:
      pop_locals_from_stack(locals())
      v1 = pop_from_return_stack()
      v2 = pop_from_return_stack()
      return push_value_onto_return_stack(v1 + v2)

This idea might work... the problem is that there is a lot of annoying stuff in python, with's for example. Or generators. I have to idea how to deal with those.

rose juniper
#

learning about sorting algorithms, what's more expensive? swapping elements in array, or creating new array?

rose juniper
#

i think creating new one is def more expensive in space wise, but what of time complexity?

actually just realized this is useless discussion because I remembered I'll rarely get in situation to implement my own sorting algorithms...

agile sundial
#

creating a new array uses more memory

agile sundial
haughty mountain
#

!e from an earlier discussion

from types import GeneratorType

def bootstrap(f, stack=[]):
  def wrappedfunc(*args, **kwargs):
    if stack:
      return f(*args, **kwargs)
    else:
      to = f(*args, **kwargs)
      while True:
        if type(to) is GeneratorType:
          stack.append(to)
          to = next(to)
        else:
          stack.pop()
          if not stack:
            break
          to = stack[-1].send(to)
      return to

  return wrappedfunc


@bootstrap
def fib(n):
  if n <= 1:
    yield n
  else:
    yield (yield fib(n-1)) + (yield fib(n-2))

for i in range(1, 10):
  print(fib(i))
halcyon plankBOT
#

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

001 | 1
002 | 1
003 | 2
004 | 3
005 | 5
006 | 8
007 | 13
008 | 21
009 | 34
haughty mountain
#

you might be able to hack on the ast to make this happen automatically

#

I remember playing around with it, but I didn't spend much time on it

#

basically replace return with yield, replace recursive calls to yourself with a version with yield

#

this restricts what you can do a bit though

#

e.g. no recursive calls in a comprehension

haughty mountain
#

!e

import ast
import inspect
from types import GeneratorType


def bootstrap(f, stack=[]):

  def wrappedfunc(*args, **kwargs):
    if stack:
      return f(*args, **kwargs)
    else:
      to = f(*args, **kwargs)
      while True:
        if type(to) is GeneratorType:
          stack.append(to)
          to = next(to)
        else:
          stack.pop()
          if not stack:
            break
          to = stack[-1].send(to)
      return to

  return wrappedfunc

def get_ast(f) -> ast.AST:
  return ast.parse(inspect.getsource(f))

def auto_bootstrap(fun):
  f = get_ast(fun)
  fname = f.body[0].name
  f.body[0].decorator_list = []

  class Yieldify(ast.NodeTransformer):

    def visit_Return(self, node: ast.Return):
      self.generic_visit(node)
      new_node = ast.Expr(value=ast.Yield(value=node.value))
      return new_node

    def visit_Call(self, node: ast.Call):
      self.generic_visit(node)
      if node.func.id == fname:
        new_node = value = ast.Yield(value=node)
        return new_node
      else:
        return node

  fixed_ast = ast.fix_missing_locations(Yieldify().visit(f))
  d = {}
  code = compile(fixed_ast, filename='', mode='exec')
  exec(code, d)
  return bootstrap(d[fname])

@auto_bootstrap
def fib2(n):
  if n <= 1:
    return n
  else:
    return fib2(n - 1) + fib2(n - 2)

for i in range(1, 10):
  print(fib2(i))
halcyon plankBOT
#

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

001 | Traceback (most recent call last):
002 |   File "<string>", line 55, in <module>
003 |   File "<string>", line 30, in auto_bootstrap
004 |   File "<string>", line 27, in get_ast
005 |   File "/usr/local/lib/python3.11/inspect.py", line 1270, in getsource
006 |     lines, lnum = getsourcelines(object)
007 |                   ^^^^^^^^^^^^^^^^^^^^^^
008 |   File "/usr/local/lib/python3.11/inspect.py", line 1252, in getsourcelines
009 |     lines, lnum = findsource(object)
010 |                   ^^^^^^^^^^^^^^^^^^
011 |   File "/usr/local/lib/python3.11/inspect.py", line 1081, in findsource
... (truncated - too many lines)

Full output: https://paste.pythondiscord.com/anomeciyuv.txt?noredirect

haughty mountain
#

welp

#

inspect.getsource doesn't work without a file? pithink

stray fractal
haughty mountain
#

in any case, code that converts returns/calls to yields which work with the recursion bootstrapper

haughty mountain
#

to getting ast from a function def

stray fractal
#

i don't think there's any

haughty mountain
#

welp

stray fractal
haughty mountain
stray fractal
haughty mountain
#

🥴

stray fractal
haughty mountain
#

oh right

#

I should still keep a return

#

that doesn't work well with NodeTransformer huh?

stray fractal
haughty mountain
#

I guess return (yield ...) would work

#

to exit the function

#

even though the return value is just ignored

flat sorrel
#

e.g. for graph traversal

def preorder_traversal(node):
    yield node

    for child in node.children:
        yield from preorder_traversal(child)
vital scaffold
#

Has anybody read the book Data Structure and Algorithms in Python by Michael T. Goodrich ?

lethal turret
#

is anyone able to point me in the right direction? Im having trouble figuring out my issue with a forward chaining program that uses rules to determine a type of animal. The problem is I am a beginner and only allowed to use 'if' statements.

plain marten
#

Okay i misunderstood the question, but you could solve this with nested if statements. ##first rule if (something == 1337): ##now for the second rule if (something_entirely_different == 0): ## the patient has a fever.. else: ## patient doesnt have a fever else: ...

#

in the case of animals, i would find out what larger groups and sub groups exist, like mammals and Felidae

mystic gate
#

How would I calculate the complexity (O notation) of the following algorithm?

def f(x, y):
    if x == 0:
        return y+1
    elif y == 0:
        return f(x-1, 1)
    else:
        return f(x-1, f(x, y-1))

I don't seem to understand everything, could anyone tell me step by step how to calculate it for that algorithm?

cobalt hamlet
#

Hi, need your help. Having 2 arbituary boolean functions, is it possible to tell that the first one implies another without brute-forsing them on all domain values?

outer rain
outer rain
# cobalt hamlet Hi, need your help. Having 2 arbituary boolean functions, is it possible to tell...

You can try to build CNF from both and check if one implies the other (for each clause of one formula check if there is a clause in another formula which implies it), but those are sometimes very hard to obtain and may have an insane size. If I was you I would probably just dump both into high level SAT solver like z3 and ask if one implies another. That's an overkill, but it probably won't even be that slow.

outer rain
# mystic gate How would I calculate the complexity (O notation) of the following algorithm? ``...

I thought about it for like half an hour and I have no idea either. This function clearly computes the Ackermann function, the but complexity of this function itself is though to calculate. The relation between call count and values is as follows:

   1:1       2:2       5:3      15:5      107:13
   1:2       4:3      14:5     106:13   
   1:3       6:4      27:7     541:29   
   1:4       8:5      44:9    2432:61
   1:5      10:6      65:11  10307:125  
   1:6      12:7      90:13  42438:253  
   1:7      14:8     119:15 172233:509  
   1:8      16:9     152:17 693964:1021

Perhaps an upper bound of calls(x, y) < A(x + 1, y + 1) can be proven?

lean walrus
#

https://en.wikipedia.org/wiki/Ackermann_function?wprov=sfla1

Ackermann function

In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive. All primitive recursive functions are total and computable, but the Ackermann function illustrates that not all total computable functions are prim...

naive oak
#

just looking at the values of A(m, n) there seems to suggest the big O might involve knuth uparrow/conway's chained arrow

#

since the only operation is +1 and you so you need at least that many increments

pallid plank
#

relatively comfortable with python (know the following : while/if/functions/for/data structures).

I'm looking for co-programming, or for a more senior python developer to work with on projects

can anyone help?

robust dagger
fiery cosmos
#

Hey I am making a tic tac toe game AI. In that I have to find if a cell in a row/column is empty, how to do that?

The board is a matrix of 3x3 size and if it is empty, its value is 2

#

this is my code

halcyon plankBOT
#

Hey @fiery cosmos!

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

fiery cosmos
#

Alternatively I did this change

# 
    # Scan column 1
    for i in [(0,0),(1,0),(2,0)]:
        if states[i]==2:
            counter=counter+1
            emptycell=i
        if counter == 1:
            product = product * i
            if product == 18 or product == 50:
                return emptycell
#

is it better?

fiery cosmos
#

But the algorithm I have says to take count of the players too in Posswin(p) function? is it important? Like will it cause some ridiculous moves

fiery cosmos
#

Guys I dont think I will get help in help channel as it will be offline soon. So if anyone of you can help me please read this and answer me here :
#1073859018843488296

open hearth
#

hey guys, i'm new here and would like some help with a merge dataframe thingy that's been keeping me frustrated for 2 days now
or a workaround, idc really
df is 1min chart for a full day and df1 is all trades, about 2 million rows
only 28 show up upon merge
i figure because only 28 have the same datetime
'Date' in my columns as index on both tho

halcyon plankBOT
#

Hey @open hearth!

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

fiery cosmos
#

Yo

#

Anyone here

bright geyser
#

this is the linked list cycle II problem. I'm confused about the while statement here. If I reverse the 2 conditions in the while statement to, "while rabbit and rabbit.next" I get a NoneType object error, but if I keep it as is I don't. What's goin on here?

image.png
fiery cosmos
#

that is strange

#

i thought so to. it eventually does

bright geyser
#

I don't think so? That's what I thought too but I remember that when turtle does hit rabbit, all you have to do is return that node

#

yeahhh

#

yeahhhhh

#

I watched neetcode's explanation on floyd's algo and implemented that

#

and it somehow worked

fiery cosmos
#

i wrote out you algorithm on paper and it always seems to give the head as the node where it starts

bright geyser
#

tf

fiery cosmos
#

it does tell if there is a cycle correctly just not where it starts

bright geyser
#

oh no it does tell where it starts

#

that's floyd's algo right

fiery cosmos
#

ah

bright geyser
#

when the turtle and rabbit first meet

#

I put the turtle alll the wayyyy back to head

fiery cosmos
#

i think i kept stepping by 2 instead of switching to one steps for rabit

bright geyser
#

and then I move the rabbit(initially it was at that node where it met turtle) and the turtle would move forward one node at a time, until they do meet each other again, and at that piont is the node where the cycle starts

#

its very very unintuitive

bright geyser
#

also btw for my previous question

#

some dude explained it to me nicely

fiery cosmos
# 
while turtle!=rabbit:
  turtle = turtle.next
  rabbit = rabbit.next
bright geyser
#

yea after u set the turtle to head, u do that

fiery cosmos
#

this seems like it would loop indefinetly if turtle and rabbit do not start at the same place

bright geyser
#

the thing is turtle will go back to head right

#

and rabbit will always stay some distance away from the node that started the cycle

#

and the funny thing is, the distance from the head to the node taht started the cycle is identical to the distance that the rabbit is from the node that started the cycle

fiery cosmos
#

right and each will step by one in a never edning cycle

bright geyser
#

not really, coz rmr the rabbit is always behind the node that started the cycle

#

floyd's algo is better explained with a vid:

#

as he said, this question is shit lol

#

ooo you basically implemented floyd's algo here too

#

yeah likew tf

#

I thought I was a dumass coz it seemed simple

#

its like one of hte niche things in leetcode u need to memorize/understand

#

well kinda, its like, the rabbit and hare meet up some distance away from the node that started the cycle, then u put the rabbit in the head, where the distance between the head is the exact same distance from the node that started the cycle. Then you increment both the rabbit and turtle one move at a time til lthey meet up again, and taht's the node that started the cycle

#

it's fine, I get to reiterate my thoughts

#

sameeeeee

#

its so gud for retainign info

#

and someone can catch ur mistake if u have any

fiery cosmos
#

I always get the head if it cycles

#

i'll draw out an example in gimp

#

they always end up at the starting point

#

@bright geyser

#

I have tried with 3,4,5 nodes

#

maybe its different for higher nodes

bright geyser
bright geyser
fiery cosmos
#

yeah

bright geyser
#

then yea it would make sense that it loops back to head, coz the head node is the start of the cycle

#

try making it loop back to the middle node

fiery cosmos
#

i did it with 8 nodes and it ended at B

bright geyser
#

wai did u watch the vid I sent?

fiery cosmos
#

well i am saying it ended at b when it has fouind a match

#

not when it trys to find the starting node i mean

#

sure ill watch the video

bright geyser
#

o

bright geyser
#

@fiery cosmos I also tried with 8 nodes, and I still ended bacc at the head

fiery cosmos
#

i messed up my table you are right

#

still watching the video

#

better to use numbers and just count by two and one instead of letters

bright geyser
#

yea it gets kinda confusing when for a moment the 2 pointers are in the same node, but u also have to move the other pointer at the same time

bright geyser
fiery cosmos
#

got it

#

it makes sense now

bright geyser
#

niceeee

scarlet dove
#

yép !

lucid bay
#

Hey as anybody got experience using scrapy?

harsh hedge
#

What is the most efficient way to for example share data between a python and a java program during runtime?

dusky trellis
#

shared memory, I would think

agile ledge
#

Hey guys, I am currently into trying to understand recursion, unfortunately after 1 month hustling 6h a day I can tell that I've made no progress at all, I know all the theory but when it comes to code I'm getting lost, so my questions are : Is recursion actually very impotent when it comes to write code, applying for job...? Is there any chance that I still learn this after failing to learn it for a month if yes please tell me how if not should I just quit recursion and continue with something different?

unkempt onyx
idle pier
#

Hello folks, I need help understanding a particular section of my zero one knapsack algorithm

def knapsack(capacity, weights, values, numOfItems):
    if numOfItems == 0 or capacity == 0:
        return 0

    if weights[numOfItems - 1] > capacity:
        return knapsack(capacity,weights,values,numOfItems-1)
    else:
        val_included = values[numOfItems-1] + knapsack(capacity-weights[numOfItems-1],weights,values,numOfItems-1)
        val_not_included = knapsack(capacity,weights,values,numOfItems-1)
        return max(val_included,val_not_included)```
I really don't understand why we have to `[numOfItems - 1]`, am completely lost there
shut breach
honest bramble
#

I have this code for calculating what value is the nth int in fibonacci sequence. It is my understanding that the recursive call to return fib(n-1) has to run its course, before the first (and all subsequent) calls of fib(n-2) can be pushed to the stack and eventually run. My question is: it seems there is redundant calculations going on, since anything fib(n-2) calculated will have already been calculated by fib(n-1). Is there a way to save all the results of fib(n-1) instead of running fib(n-2), and is this any more efficient?
def fib(n):
assert n >=0 and int(n) == n, 'The number must be a positive integer only'
if n in [0,1]:
return n
else:
return fib(n-1) + fib(n-2)

idle pier
glossy breach
#

save anything thats already calculated

#

and if a value is already calculated, stop the recursion

honest bramble
#

Is that any more efficient than doing the recursion?

naive oak
#

functools.cache is a pretty easy way to implement memoization

keen hearth
tiny jay
haughty mountain
#

it's something you can research easily

#

how to find cycles in graphs

timid elbow
#

I didn’t really know which one to go on for this, but I’m wondering if there’s anyway that you can change the color of words inside of an embed

#

Or even if it’s not inside an embed

haughty mountain
#

ah, yeah it's a bad interview question

#

good interview questions are about combining and applying a few points of DS&A knowledge solve a problem

#

what the level of expected knowledge you can expect can differ, but if the task is literally just "apply thing" that's pretty questionable

haughty mountain
#

yeah?

#

in your problem we are working with a graph, we have parts of the graphs that are already connected, those are components

#

the question then boils down to just connecting the components

#

so step 1: find all components

#

step 2: connect the components with the fewest possible edges

#

to rephrase the idea, take each component and replace it by a single node

#

then you just need to connect these nodes

#

and it shouldn't be hard to figure out how many edges you need to connect a set of points

#

there shouldn't be any edge cases in the thing I wrote

fiery cosmos
#

Hey, so I'm finding that on my machine, this function is taking about 1.5 seconds...
There has got to be a faster way!

s = requests.Session()
content=""
with s.get(url=searchUrl, headers=header3) as response:
  content = response.content.decode('utf-8')
  begin=content.find("https://yahoo.com/")
  if(begin>-1):
    content = content[begin:content.find('"',begin)]

The code is trying to search through a response for a specific hostname. Any ideas on what I can do to speed this up?

agile sundial
#

you should measure which parts are taking time. if it's the request, not much you can do without getting better internet

fiery cosmos
#

the 1.5 seconds is only processing this code here. The request is already complete.

agile sundial
#

s.get is the request, isn't it?

fiery cosmos
#

Oh well... yes I suppose you're right 😄

#

I made an improvement to cut the time in half

s = requests.Session()
content=""
with s.get(url=searchUrl, headers=header3) as response:
  content = response.content
  begin=content.find(b"https://yahoo.com")
  if(begin>-1):
    content = content[begin:content.find(b'"',begin)]
#

yeah I'm wondering if there are maybe other tricks. Like if I know approximately where the URL is expected to appear, do you think I can reasonably save time by starting the find somewhere in the middle ,etc

#

or if this is maybe doing unnecessary copies

agile sundial
#

do you need to slice? also have you done benchmarks?

fiery cosmos
#

I'm doing very rudimentary time.time() benchmarking right now

agile sundial
#

i wonder if something like bs4 would be faster, but probably not. i don't think you'll get any faster from just .find

haughty mountain
#

I'm confused why this would even be slow

#

how big is content?

fiery cosmos
#

Well after benchmarking the internals here, I think you're right. The .find time is almost 0, the remaining time is network time

#

maybe 1 MB

haughty mountain
#

yeah, the find should be very fast then

fiery cosmos
#

yeah the UTF-8 decode was slow, but the rest seems OK

#

alright I won't hyper optimize this 🙂 benchmarking is always the right answer

agile sundial
#

always the first thing you should do when trying to speed things up

fiery cosmos
#

Yeah I was benchmarking the full function, and forgot to benchmark the network separate from the parsing. Thanks for reminding me

agile sundial
#

now the only thing left to do is get better internet

fiery cosmos
#

💀

fiery cosmos
# 
def tryparsenum(w):
    w = int(w)
    return type(w) == int


w = '56'
print(tryparsenum(w))
print(type(w))
#

how do I make tha argument passed also change

#

in print(type(w)) I don't want it to be a string, I want it to be an int

#

as modified in the tryparsenum method

#

how do I do that?

unkempt vapor
#

return the w variable too

#

btw I don't think this is the right channel

severe lance
#

your function will always return true or just error

#

it's kinda pointless

fiery cosmos
#

idc about it being pointless

severe lance
fiery cosmos
#

um im in Topical chat/help

#

that should do it

severe lance
fiery cosmos
#

sure why not

#

done

tall stratus
#

Hey guys, I want to use the python wrapper talib for TA-lib but I cannot install it, what could be wrong? (I'm using manjaro-linux)

image.png
velvet ivy
#

Hi is it true that we aren't allowed to functions while solving a problem in company interviews

velvet ivy
#

Hi so this is the leetcode question is 2529 and Its saying to use Binary Search ```nums = [-2,-1,-1,1,2,3]

target = 0
def binarySearch(arr,target,start, end,counter):
print(start,end,counter)
mid = int(start + end / 2)
print(mid)
if end < start:
print("Pritning the final",counter,arr)
return [len(arr),counter]
else:
if target < arr[mid]:
counter += 1
arr.pop(mid)
print(arr,target,start,end,mid,counter)
binarySearch(arr,target,0,mid - 1,counter)
elif target > arr[start]:
binarySearch(arr,target,mid , end,counter)
elif target == arr[mid]:
arr.pop(arr[mid])
end = len(arr) - 1
binarySearch(arr,target,start,end,counter)

end = len(nums) - 1
start = 0
counter = 0
value = binarySearch(nums,target,start,end,counter)
print(value)

#

I am trying to do this

#

it is able to separate it out however it goes out of index can some one please help me

full kernel
#

can anyone recommend me a good algos course with exercises?

velvet ivy
full kernel
velvet ivy
fiery cosmos
#

hi im learning DS&A through a udemy course. I basically wait for the instructor to describe how the algorithm works (demonstrating on real data) and then I write my own code accordingly, then compare with their code at the end (after thoroughly testing mine). Is this fine or are you supposed to know how algorithms and data structures work just based on mentioning them?

#

^im asking what the correct approach is to learning this stuff

full kernel
cunning lily
#

Hello guys, I have some questions:

  1. Look at the instruction set for the IAS computer which we discussed in class. Pick one of those instructions that you think is the fastest, and another that you think is the slowest, and use what you know about instruction execution to describe why they take such a different amount of time.

  2. Use an example to illustrate the tradeoffs (both the advantages and disadvantages of different design decisions) of different specific CPUs.

fiery cosmos
silk nova
#

Beside Cython, is there any way to increase the speed of looping through a JSON file? I tried doing it async using aiofiles but its slower than normal synchronous loop ... my JSON loop is in a pyx file written in cython

vast adder
twin steppe
#

i was trying to use vosk i got the model and everything

#

but this error keeps coming

# 
  File "/Users/dineo/PycharmProjects/polan_deepspeech/venv/lib/python3.11/site-packages/vosk/__init__.py", line 12, in <module>
    from .vosk_cffi import ffi as _ffi
ImportError: attempted relative import with no known parent package

Process finished with exit code 1```
#

or this

# 
Exception ignored in: <function Model.__del__ at 0x1065900e0>
Traceback (most recent call last):
  File "/Users/dineo/PycharmProjects/polan_deepspeech/venv/lib/python3.11/site-packages/vosk/__init__.py", line 60, in __del__
    _c.vosk_model_free(self._handle)
                       ^^^^^^^^^^^^
AttributeError: 'Model' object has no attribute '_handle'
URLError: <urlopen error [SSL: CERTIFICATE_VERIFY_FAILED] certificate verify failed: unable to get local issuer certificate (_ssl.c:992)>
lean walrus
#

How are you running your code?
Can you show your code?

twin steppe
#

do you need to see its structure ?

#

like file structure

#

also i dont really want to use the small model

ionic locust
#

As a math noob what is the name of this type of number 3.510000e+03

vocal gorge
#

this is written in engineering notation, if that's what you mean. it's just 3510.0.

ionic locust
#

Oh ok

agile sundial
#

huh, i've never heard "engineering", always "scientific"

#

though my calculation has an "ENG" mode which always uses a multiple of 3 for the exponent

vocal gorge
#

I have a cached thought that engineering notation is when you use E instead of * 10^

agile sundial
#

huh

#

why is the e notation even a thing. is it for "exponent"?

boreal schooner
#

Hey guys, what is the best way to enforce that a subclass of a Django ModelViewSet has a specific class attribute implemented? I've created a function that does so, but when should I call it? __new__ and then call super().__new__?

umbral gulch
#

whats the fastest time complexity of fibonacci numbers?

severe lance
umbral gulch
# severe lance O(log n)

so like this?

def fast_fib(n):
    if n == 0:
        return (0, 1)
    a, b = fast_fib(n >> 1)
    c = a * ((b << 1) - a)
    d = a * a + b * b
    return (c, d) if n & 1 == 0 else (d, c + d)
severe lance
#

that looks like the fast doubling method, sure

#

although you'd probably also want to define fib = lambda n: fast_fib(n)[0]

#

so that it doesn't return two numbers

#

also be careful that this is not the most efficient way to generate a sequence of fibonacci numbers

#

i.e. if you wanted to generate the fibonacci numbers between 100 and 200, it would be a lot faster to just generate the 100th and the 101th, then just add those together linearly up to the 200th term

edgy folio
opal oriole
native garden
#

how do we deal with doing for loops within for loops within for loops within...?

#

i feel like explicitly typing each 'iteration' isnt the best way

#

unless it is

jolly mortar
#

you could use itertools.product

#

for x in xs: for y in ys: for z in zs: becomes for x, y, z in product(xs, ys, zs):

native garden
#

i want to do n number of nested loops

naive oak
#

you can do like

for items in itertools.product(range(10), repeat=n):
robust dagger
#

If you have a list l consisting of iterators it1, it2, up to itn, then you can use for items in itertools.product(*l):.

naive oak
#

do note that I believe it's slower than nested for looping

haughty mountain
#

and obviously, this explodes really quickly as n grows larger

lean walrus
#

it also allocates all results at the start, so it uses a lot of memory

fiery cosmos
haughty mountain
#

itertools.product is lazy

tacit halo
# 
@staticmethod
def triplet_result_zero(l: list[int]) -> list[list[int]]:
    result: list[int] = []
    for i in range(len(l) - 2):
        for j in range(i + 1, len(l) - 1):
            for k in range(j + 1, len(l)):
                if l[i] + l[j] + l[k] == 0:
                    result.append([l[i], l[j], l[k]])
    return result

thoghts?

haughty mountain
#

you can easily do this in O(n²)

#

for all pairs a, b; check if -(a + b) exists

tacit halo
tacit halo
#

typo

#

whoops

haughty mountain
tacit halo
haughty mountain
#

e.g.

for i in range(1, n):
  for j in range(0, n, i):
    ...do some O(1) work
tacit halo
#

would a while loop be faster?

haughty mountain
tacit halo
#

a + b - a + b

fiery cosmos
tacit halo
#

0

#

thanks man

#

great help

fiery cosmos
#

i'm planning to make a operation thing

haughty mountain
tacit halo
fiery cosmos
#

like, operate division first then multiplication then sum and subtraction

haughty mountain
fiery cosmos
#

i also discovered a bug that the thing is instead of subtracting it's summming and turning into negative

tacit halo
fiery cosmos
#

yep

tacit halo
fiery cosmos
#

it'sx because i made a dice rolll algorythm

#

and it's working

haughty mountain
#

precedence is kinda annoying to deal with

fiery cosmos
#

but the math part is failing

tacit halo
tacit halo
fiery cosmos
#

so i can learn better with python

tacit halo
fiery cosmos
tacit halo
fiery cosmos
#

here

tacit halo
haughty mountain
#

reverse polish notation might be interesting to look at to see a system without precedence rules

tacit halo
#

avoid using del for deleting elements from the list. Instead, consider using slice notation to remove elements, which is faster and more efficient

fiery cosmos
#

i see, i was planning to remove those elements just to show up as solved problem

tacit halo
#

i saw another flaw

fiery cosmos
#

slice? uhmm..., lemme search rq

tacit halo
#

use built-in Python functions like 'sum', 'reduce', and 'operator' instead of manually iterating through the list and performing calculations, this isnt a flaw rather an improvment i would recommend

#

and use list comp

#

thats all i could see from your code

fiery cosmos
#

list comp?

tacit halo
#

[i for i in ..]

fiery cosmos
#

like, indice is the pivot list that store the operators

#

like +-*/

lean walrus
# haughty mountain itertools.product is lazy

My bad.

It lazily creates resulting tuples, but all internal iterables are iterated over and cached at beginning (on product() call or on the first next() call, idk).

I remembered that some part of .product is not lazy, but forgot what, so i was wrong.

agile sundial
#

product needs to store the entire iterable first because it needs to support repeat

#

like for product((i for i in range(10), repeat=2), there's no way to ungenerate the values, so it needs to store them

fiery cosmos
#

how do i add a and condition here?
re.compile(r"^(")

#

i'm plannning to add a ")$" condition

#

i'm planning to the pattern gather all values from ( to )

agile sundial
#

wdym "and" condition

#

you could just accept any character in between

fiery cosmos
#

like, gather value that starts with ( and ends with )

#

that's the condition i'm plannintg to add

agile sundial
#

you probably want something like r"^\(.+\)$"

fiery cosmos
#

!e

pattern = re.compile(r"[+-*\/()]")
x = "5+8+(5*3)-7
print(pattern.split(x))

halcyon plankBOT
#

@fiery cosmos :x: Your 3.11 eval job has completed with return code 1.

001 |   File "<string>", line 2
002 |     x = "5+8+(5*3)-7
003 |         ^
004 | SyntaxError: unterminated string literal (detected at line 2)
fiery cosmos
#

!e

pattern = re.compile(r"[+-/()]")
x = "5+8+(53)-7"
print(pattern.split(x))

halcyon plankBOT
#

@fiery cosmos :x: Your 3.11 eval job has completed with return code 1.

001 | Traceback (most recent call last):
002 |   File "<string>", line 1, in <module>
003 | NameError: name 're' is not defined
fiery cosmos
#

!e
import re

pattern = re.compile(r"[+-/()]")
x = "5+8+(53)-7
print(pattern.split(x))

halcyon plankBOT
#

@fiery cosmos :x: Your 3.11 eval job has completed with return code 1.

001 |   File "<string>", line 4
002 |     x = "5+8+(5*3)-7
003 |         ^
004 | SyntaxError: unterminated string literal (detected at line 4)
fiery cosmos
#

!e
import re

pattern = re.compile(r"[+-/()]")
x = "5+8+(53)-7"
print(pattern.split(x))

halcyon plankBOT
#

@fiery cosmos :white_check_mark: Your 3.11 eval job has completed with return code 0.

['5', '8', '', '53', '', '7']
agile sundial
#

#bot-commands

fiery cosmos
#

!e

x,y = 1,2

print(x)
print(y)

halcyon plankBOT
#

@fiery cosmos :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | 1
002 | 2
fiery cosmos
#

oh, so that works

#

nice

fiery cosmos
#

!paste

halcyon plankBOT
#

Pasting large amounts of code

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

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

halcyon plankBOT
neon sierra
#

hi im having hard time rounding these numbers for my intro class

#

any suggestions

#

ive tried a lot of things

fiery cosmos
#

is there a way for me to create a function assuciated with a function?

#

like

function a(x, y, z)
function a(w)

#

i'm planning to make a function of a function

#

like, one fuction to compile an input for another function

#

i'm planning to it accept one input and it have a function to compile the input to make 2 input for another function

umbral gulch
#

is there anything in python maybe itertools where i can give it an array of cahracters like
["a", "b", "c"]

and it'll return all combinations of those so

"a", "b", "c"
"ab", "c"
"a", "bc"
"abc"

or an algorithn

crude pond
#

!e import itertools
print(dir(itertools))

halcyon plankBOT
#

@crude pond :white_check_mark: Your 3.11 eval job has completed with return code 0.

['__doc__', '__loader__', '__name__', '__package__', '__spec__', '_grouper', '_tee', '_tee_dataobject', 'accumulate', 'chain', 'combinations', 'combinations_with_replacement', 'compress', 'count', 'cycle', 'dropwhile', 'filterfalse', 'groupby', 'islice', 'pairwise', 'permutations', 'product', 'repeat', 'starmap', 'takewhile', 'tee', 'zip_longest']
keen hearth
#

There's nothing exactly like this in itertools, and I'm not sure what the combinatoric term is for this, but you can achieve this with the following recursive function: ```py
def foo(s):
if len(s) == 0:
yield ()
return
for i in range(len(s)):
prefix, suffix = s[:i+1], s[i+1:]
for rest in foo(suffix):
yield (prefix,) + rest

knotty magnet
#

Probably some term with "partition" in it.

keen hearth
#

If s is long, the maximum recursion depth may be an issue, but then the number of possible ways to split up the string would be impractically large anyway.

keen hearth
knotty magnet
#

But "ac" isn't a possible output, so I'm not actually sure.

keen hearth
#

!eval ```py
def foo(s):
if len(s) == 0:
yield ()
return
for i in range(len(s)):
prefix, suffix = s[:i+1], s[i+1:]
for rest in foo(suffix):
yield (prefix,) + rest

print(list(foo('abc')))

halcyon plankBOT
#

@keen hearth :white_check_mark: Your 3.11 eval job has completed with return code 0.

[('a', 'b', 'c'), ('a', 'bc'), ('ab', 'c'), ('abc',)]
keen hearth
#

@umbral gulch

umbral gulch
#

nice

crude pond
#

!e from itertools import combinations as c
print([list(c("abc",i)) for i in range(1,4)])

halcyon plankBOT
#

@crude pond :white_check_mark: Your 3.11 eval job has completed with return code 0.

[[('a',), ('b',), ('c',)], [('a', 'b'), ('a', 'c'), ('b', 'c')], [('a', 'b', 'c')]]
agile sundial
#

tfw you read 2x10^5 instead of 2x10^6 and you realize it's not brute forceable 😔

flint otter
#

if i have n!, would n be considered a constant when referring to Big O Notation?

#

because I’m trying to see if n!+2n is = or ≠ to O(3^n)

knotty magnet
#

If n changes, it's not constant.

gentle island
#

i was wondering if i could send over my code for anyone to take a look at and see if i can reduce clutter and increase readability while keeping optimisability the same in my code?

buoyant stream
gentle island
buoyant stream
mild rain
#

I have two pandas data frame a and b, both have the same shape.
I want to element-wise divide a by b

#

Tried things like
a / b
a.divide(b)

#

The resulting data frame has only NaN and somehow duplicates the columns

#

I am very new to pandas... what is the "normal" way of dividing one data frame by another element-wise?

native garden
#

is it faster to go through a large list a small number of times, or a small list a large number of times?

gentle island
#

this will drop the nan values in the sample df

knotty magnet
gentle island
#

then try doing df1.div(df2)

#

with df1 and df2 being the names of your dataframes

mild rain
#

Thanks Fishy but the result is the same

#

Like the resulting data frame only has NaN

gentle island
#

do you mind sending over the code and i can take a look

mild rain
#

Pasting the code right here ok?

gentle island
#

yeah maybe put backticks round it so its a bit easier to read

mild rain
#

df = pd.read_csv("sheet3.txt", sep='\t') at0w = df2.iloc[:, [i for i in range(len(df2.columns)) if i%2 == 0]] at4w = df2.iloc[:, [i for i in range(len(df2.columns)) if i%2 == 1]] at0w.div(at4w)

#

(Sorry but I cannot share the actual sheet3.txt)

#

So I am trying to divide each even column but its next, uneven column.

#

Actually:

#

df2 = pd.read_csv("sheet3.txt", sep='\t')

#

(There was a typo in the first line)

gentle island
#

``df2 = pd.read_csv("sheet3.txt", sep='\t')
at0w = df2.iloc[:, [i for i in range(len(df2.columns)) if i%2 == 0]]
at4w = df2.iloc[:, [i for i in range(len(df2.columns)) if i%2 == 1]]
result = at0w.div(at4w)

print(result)``

is this identical to your code?

#

just got myself a bit confused with your typos haha

mild rain
#

Yes, identical

#

I just ran it with my data

#

The result is just NaN in each element of the frame
And the column are duplicated with _at0w and _at4w appended.

gentle island
#

``# Drop NaN
at0w = at0w.dropna()
at4w = at4w.dropna()

Same dataframe lengths

min_rows = min(len(at0w), len(at4w))
at0w = at0w.iloc[:min_rows, :]
at4w = at4w.iloc[:min_rows, :]

Divide

result = at0w.div(at4w)

Print

print(result)``
Try this

mild rain
#

I just tried that. at0w and at4w originally both have a shape of (58, 59).
After doing dropna on both frame, at0w has a shape of (57, 59) and at4w is unchanged.
I then bring both into a shape of (57, 59). and div

#

However, the result is still the same

#

I.e. all NaN and columns duplicated with _at0w and _at4w appended.

gentle island
#

It sounds like the issue might be that there are NaN values in the same rows of both dataframes, so dropping NaN values from only one dataframe will result in a mismatch in the number of rows between the two dataframes, you could use how='any' when dropping NaN values so update that line to...
at0w, at4w = at0w.dropna(how='any'), at4w.dropna(how='any')
let me know how this works

mild rain
#

I will try that in a minute but I noticed something interesting

#

So after I do the min_rows thing

#

both at0w and at4w have 57 rows × 59 columns

#

But the indices of the rows must be different because at0w has 57 as the last index
and at4 has 56 as the last index!

mild rain
#

But I noticed, after removing NaN from the input data frames and bringing them to the same number of rows

#

Both at0w and at4w now have the same shape, 57 rows × 59 columns

#

However they do not have the same row indices!

#

I.e. in at0w row 27 is missing and in at4w row 57 is missing

#

could that be the issue? I.e. maybe div someow expects both data frames to not only have the same nu,ber of rows, but also the same indices?

#

By "at0w row 27 is missing and in at4w row 57 is missing" I mean: after I remove rows containing NaN from the input data frames, these lines are removed

#

I think I figured it out

#

The indices apparently must align

#

This works:
at0w / at4w.values

naive oak
#

what is your dp problem?

naive oak
#

what implementation are you referring to?

naive oak
#

like why do you say you need to do that

#

did someone tell you to?

keen hearth
#

@cobalt mirage Your goal is to find the minimum cost to reach stop i, for each i in {1, ..., n}. That's going to be the minimum cost ending up either on the regular or express side. Ie py min( cost(stop=i, express=False), cost(stop=i, express=True), ) How would you recursively define the function ```py
def cost(stop: int, express: bool) -> int:
...

#

Hopefully that's enough of a hint without giving too much away.

ripe kayak
#

Hello team in pandas I have two dataframes df1 & df2 I want to compare column ['A'] on both. If the values are the same concat df1. Is that possible?

keen hearth
limber harbor
#

If I have a bunch of enums all with a ".CREATE" and a ".UPDATE" member and I pass any one of these enums to a function is there a pythonic way to see if I passed a "CREATE" or "UPDATE".. At runtime I won't know the actual enum type

class type1 (str, Enum)
  CREATE = "type1.create"
  UPDATE = "type1.update"

class type2 (str, Enum)
  CREATE = "type1.create"
  UPDATE = "type1.update"


def somefn(some_enum):
  if some_enum == <variable>.CREATE:   #Here I won't know what type of enum until runtime, what is the correct way to do this conditional?
    do something

Any help appreciated

keen hearth
quaint perch
#

what are the advantages of using redis sorted sets compared to an ordinary hash table that is manually sorted
they said it has O(log n) compared to O(1) of hash tables which is a disadvantage

limber harbor
keen hearth
agile sundial
limber harbor
outer rain
quaint perch
outer rain
#

oh wait "sort a hash table" does not make any sense

quaint perch
agile sundial
outer rain
#

it's... not... I mean it's kinda is but insertion is O(n) now

quaint perch
quaint perch
agile sundial
# quaint perch sort by value

if you sort by value, then you won't be able to find where it is, since it's no longer where you expect it to be according to the hash function

keen hearth
#

I'm not very familiar with SQLAlchemy though.

limber harbor
#

sorry yeah you're right this is definitely in the wrong section. my bad

quaint perch
agile sundial
#

no? i've never heard of that

outer rain
quaint perch
agile sundial
#

ah. these use a linked list to maintain the order. insertion is still linear

#

also, they're not "ordered" in the sense like a binary search tree is, rather they're "ordered" in the sense that you can change the order

quaint perch
agile sundial
#

well you don't need to sort to insert

quaint perch
agile sundial
#

sure, but you're extremely limited in how you can do that with OrderedDict. you're probably better of making your own linked list if you want to do this

#

actually, this entire point is moot if you're using redis. redis doesn't expose any ordering functions for its hash sets

quaint perch
#

ok im talking about sorted sets in general

#

the takeaway here is that hash table is not an end all be all data structure 😩

agile sundial
#

well yeah. if you need to order a hash table you're literally doubling your memory consumption

haughty mountain
#

BBSTs are what you want if you want to keep an ordered mapping

ionic lark
#

Anyone here familiar with python and flask

#

api jason and all that good stuff

halcyon plankBOT
flat sorrel
fiery cosmos
#

can anyone tell me what the time complexity of this code is

IMG_6372.png
dusky trellis
quaint perch
#

actually len check means O(n)
but it doesn’t matter anyways

outer rain
quaint perch
dusky trellis
#

python lists are not linked lists

outer rain
dusky trellis
#

that depends on the value of length

outer rain
dusky trellis
#

for example, int(5.5/2) != round(5.5/2)

outer rain
#

because in else branch length % 2 == 0

#

but yes, you are right, that's worth clarifying anyway

dusky trellis
#

oh that, sorry, I had a brain fart

fiery cosmos
#

Sorry im fairly new to dsa in python and these inbuilt functions are quite overwhelming 🥲

agile sundial
agile sundial
lean walrus
agile sundial
#

it does even better. it optimizes for "runs", where there might be multiple presorted bits

agile sundial
haughty mountain
woeful arrow
#

Hi @agile sundial

#

Are you a java programmer?

agile sundial
#

no, why would you think that

#

then why do 3 billion devices use it

keen hearth
agile sundial
#

big if true

keen hearth
#

Well I know there is because I solved it yesterday

#

Someone was talking about this same question in voice-chat.

agile sundial
#

oh we can binary search

keen hearth
#

It's a bit edge-casey though.

agile sundial
#

hmm. a lot of off by one errors

keen hearth
outer rain
#

bruh that's an insane overkill

#

Just check for each point signs of cross product with sides of the triangle like in the picture. Or sum up areas of triangles PAB + PBC + PCA and compare it with area of ABC.

image.png
#

Not sure if my signs in correct, but the idea is that if all three signs are equal, then point is inside of the triangle, otherwise outside

#

Or check if the ray going in horizontal direction intersects triangle once

image.png
#

intersecting segments with horizontal ray is not difficult

#

be careful with edgecase where ray goes though triangle vertex

naive oak
#

are you asking for 2d triangles or 3d triangles?

outer rain
#

just geometry with a bit of a vector algebra basics

outer rain
#

there is dot product and cross product, you probably need cross, but you should read about both. Those are related.

naive oak
#

no clue

#

if they're asking for a 2d triangle tho then cross products are a bit overkill

outer rain
#

but to compute the area you need cross product, huh?

#

sure, that will work... I guess just don't use heron's formula to compute the area and you are fine

#

I see

#

well that works

#

I usually just use cross product

image.png
#

To calculate the area of a triangle

naive oak
#

i didn't actually know there was a definition for a 2d cross product

#

TIL

outer rain
#

You can do that. This requires you to check if point is above/below a segment, which may be painful because of the edge cases (stupid vertical lines with no equations), but will work.

naive oak
#

i mean you kinda already know the convex hull

#

since it's just a triangle

outer rain
#

well... yes... plus it requires cross product so I'm not sure if... you know... you are able to implement it... but if you can just copy and paste it I guess you can use it...

#

I might be dumb but when I'm given a convex hull and I don't know how it's oriented I might sometimes just copypaste my implementation of convex hull and apply it to... already a convex hull just to orient it properly. So if something works for you - go ahead.

robust dagger
outer rain
outer rain
# robust dagger Explain

In 3d space the cross product of two vectors on XOY plane is a vector which is perpendicular to XOY plane (so both X- and Y-components zero out) and length of which is equal to the area of parallelogram between those two vectors. And 2d cross product is just a signed area of that parallelogram. Convenient.

By the way I said the wrong thing. Not the "length" of 3d cross product, the projection of 3d product on Z axis.

image.png
naive oak
robust dagger
#

That's not a cross product.

naive oak
#

if it works it works

robust dagger
#

You're using the exterior product, which is a different construction.

#

It happens in three dimensions that you can identify the two. The cross product of two vectors is the result of taking their exterior product, then their interior product against a fixed volume form.

#

But the two are distinct operations in general.

outer rain
robust dagger
#

No.

outer rain
#

or not generalized, whatever

#

I'm not talking about algebra anyway,

naive oak
outer rain
#

that's geometry 🙂

robust dagger
#

The cross product is defined by interpreting a Euclidean space as the imaginary part of an algebra and using the multiplication in that algebra. In order to define a cross product, this multiplication has to satisfy several properties (like being well-defined, a vector cross itself being zero, and so on). This can only be done in dimensions 0, 1, 3, and 7.

outer rain
#

I used to

robust dagger
#

It's identically zero in dimensions 0 and 1, which just leaves 3 and 7.

#

The exterior product, however, is a general operation you can perform on any vector space.

#

It happens to be related to the cross product, basically because there aren't that many things you can do with a three-dimensional object.

#

But it has a completely different definition in terms of the exterior algebra.

#

And the "two-dimensional cross product" you defined above is exactly the two-dimensional exterior product.

outer rain
#

Ok fair I got it. Let me defend my self:

#

So you are right, in algebra we call that exterior product, but in most programming literature it's called just 2d cross product, because it's similar to 3d cross product and used way more often than that. So usually when referring to cross product in algorithms definitions, either "z-component of cross product" or just "cross product" term is used. I agree that it refers to a formally different algebra operation, but I believe it's ok to use domain-specific jargon. Thanks for clarifying that though, this may be helpful for others.

robust dagger
#

If the programming literature calls it anything, it calls it a determinant.

#

Anyone calling it a 2d cross product is just wrong.

outer rain
robust dagger
#

I hate to sound so aggressive, but this terminology has been stable for at least 80 or so years.

outer rain
#

oh wait not to that

#

no wait that's not for you.....

#

god

outer rain
robust dagger
#

You can look this up in innumerable algebra books.

#

Artin, Hungerford, Dummit and Foote, etc., will all agree that this is the exterior product.

#

People on the Internet are allowed to be wrong. They're often wrong. (I'm wrong too sometimes.) So I'm not too surprised that you can find websites that use wrong terminology. But it's still wrong.

#

My objection to calling this a two-dimensional cross product is that the result is not a vector (unless you embed the whole situation in three dimensions. To be fair that's what you did, but then it's not really two-dimensional). It's a scalar.

outer rain
#

Alright, I'm not going to argue about it and I won't change my opinion either. I understand what you mean and where are you going from, but I disagree and I will continue to call it "cross product" like in "Introduction to algorithms" or something.

robust dagger
#

The exterior product isn't supposed to give you another vector (it just gives you back another element of the exterior algebra, or the Clifford algebra if you've embedded everything there). But that's what a cross product is.

robust dagger
outer rain
#

deal

#

ow sorry

#

I did a bit of codeforces, but mostly a local contests at my school under teacher supervision, so I can't really give good sources.

#

I dont remember one sec

#

To be honest, I don't know... just try out different sources

#

this really depends on who you are and how you learn things so I can't recommend something specific

#

I remember a one good article which helped me a while ago but it's in russian so... you know... language barrier

#

you know a lot of methods now, just use any

#

I don't think you are ready for convex hull yet

#

a somewhat good understanding of cross product, stack, basic sorting

#

and the first one is the most relevant

#

well again I can't really recommend the source so...

haughty mountain
#

since the cross product points along z

outer rain
haughty mountain
#

oh right, you want the signed version of the thing

#

right

#

projection is right then, my bad

#

but yeah, the two ways I think of when doing point in (convex) polygon is to either check a bunch of cross products or a bunch of dot products

#

so, on the orientated edges of the polygon, is the point always on the same side of the edges

#

which can be computed using a cross product like thing, or doing a dot product against the normal vector of the edge

#

there are other fun approaches that work even for the non-convex case

#

take a ray from the point, if it intersects an odd number of segments it's inside, if even outside

#

but that has fun edge cases, as with a lot of computational geometry

dusky trellis
#

what if math makes your head hurt?

thorn torrent
#

but I need to learn this stuff for a project I'm working on with some friends😭 but it will definitely worth while!

#

tell me where is the best place to start if one wants to learn this topic

dusky trellis
#

hands Fring some ibuprofin

thorn torrent
robust dagger
#

What you need is that the cross product takes two vectors as input and returns a third vector which makes the three vectors form an oriented basis. Informally, we say that the cross product satisfies the right-hand rule: If you point your right hand in the direction of the first vector and curl your fingers towards the second vector (which may require turning your hand over!), then your thumb will point in the direction of the cross product.

The most elementary way to check whether a point is inside a triangle is: Each segment of the triangle determines a line, and the line cuts the plane into half-spaces. The remaining vertex of the triangle is in one of these half-spaces; the point is inside the triangle if and only if it is in all three of these half-spaces.

That method uses the third vertex to determine which half-space is the correct one. We can also encode this information as an orientation of the sides of the triangle (making them vectors and not just segments). If the orientations are consistent, so that the triangles make a loop, then the interior of the triangle is either the intersection of the left half-spaces or the intersection of the right half-spaces, while the other intersection of half-spaces is empty.

This is where the cross product comes in. We embed the plane into space (as {(x, y, z) : z = 0}). If v and w are two vectors in the plane, and we translate them so that they begin at the same vertex, then v x w points up (z positive) if w is in the left half-space of the line determined by v, and it points down (z negative) if w is in the right half-space. So if the triangle has vertices A, B, C, and the point is P, then we can test whether P is in ABC by checking whether AB x AP, BC x BP, and CA x CP all have the same sign. We get effectively the same test if we look at AP x AB, BP x BC, and CP x CA (because this just reverses the orientations, i.e., all the signs)) or PA x BA, PB x CB, and PC x AC (again, it just reverses all the signs).

rich moat
#

Hello,

I have a understanding problem with pandas / dask.

My Data looks at the moment like this:

id;neuronal_data;
9928-1231-1231; [.23, .21 ....]
9928-5218-1101; [.1, .51 ....]

The shape of neuronal_data is [1024] now I want do a simple matmul over all that values with a 1D list of data with the same shape.
If someone want know what I do, I use open_clip.

Now I have problems to implement that in a fast and good way. My CSV files are big (over 250.000 rows) and I have to get the ID later back, after the matmul + top_k function. To get rid of the memory problems, I wanted use dask, but even in pandas i dont know if I have the best practice. Dask is a another thing, I cant get it running like I want to. My goal is to process in chunks over the data and that so native with the library like it is possible.

In pandas its works then I use:
df.neuronal_data.apply(lambda x: x @ search_list) but that seems to be impossible in dask?
And is that even a good practice?! Should I save the data just pure matrix like? Without the ID? So that I can use transpose and the matmul function?

I am a newby in data science and big data. Hope someone can give me a bit advice. GhatGPT isnt a help atm 😦 And sorry for my super bad english.

gloomy hedge
#

Hey, quick question. From what I can find online, heapq.nsmallest runs in O(n * log k), where n is the size of the list and k is the number of smallest elements to return. I understand that it does this by heapifying the first k elements, then doing heappushpop for the rest (log k operation n times). However, wouldn't it be better to heapify the whole thing (O(n)), then do heappop k times to find the smallest elements (log n operation k times)? This would be O(n + k log n), which seems better than O(n * log k) since n > k. Why does Python choose the former implementation?

robust dagger
# gloomy hedge Hey, quick question. From what I can find online, `heapq.nsmallest` runs in O(n ...

https://github.com/python/cpython/blob/main/Lib/heapq.py has extensive comments about this. In particular it says:

Other algorithms were not used because they:

  1. Took much more auxiliary memory,
  2. Made multiple passes over the data.
  3. Made more comparisons in common cases (small k, large n, semi-random input).
    See the more detailed comparison of approach at:
    http://code.activestate.com/recipes/577573-compare-algorithms-for-heapqsmallest
    My guess is that the solution you suggest was rejected because of (1). The chosen solution makes it possible to find the k smallest elements without ever having all the values in memory (for example, if they're generated by an iterator).
#

Actually, the link in the source code confirms my suspicion: It explicitly considers your suggested algorithm but says it "is not space efficient".

haughty mountain
#

right, O(n + k log n) and O(n log k) differs in memory usage

#

O(n) vs O(k) extra usage

haughty mountain
#

but ultimately it's a trade-off

#

both solutions are good and make different sacrifices

keen hearth
#

In typical usage, k is probably pretty small compared to n.

haughty mountain
#

an interview question I asked actually touched upon that

#

the problem boils down to some preprocessing followed by getting the top K values

#

and I expect people to arrive at one of the two solutions here (maybe with some hints)

#

in C++ there is also std::partial_sort which does the right thing, though I never saw anyone jump to that in an interview

#

(granted, not a lot of people interviewing in C++)

#

I think I've only had one candidate completely nail it without any hints, and that candidate was just impressive to the extent that I had to pad with extra twists on the problem 😄

fiery cosmos
#

This looks like a problem that can be solved with a bottom up approach but I'm not sure how to go about it

SPOILER_826c1f1bcbb46e46c928c702cc72e0f0.png
robust dagger
# fiery cosmos This looks like a problem that can be solved with a bottom up approach but I'm n...

To do this bottom up, you would figure out, for each day n, the minimum cost strategy for days up to n. The cost of a strategy is the cost of whatever contract you most recently bought, plus the cost of whatever contracts you bought previously. That is, if you're on day n, then you want to consider: What's the cost if I bought a one-day plan yesterday? A one-year plan one year ago? A two-year plan two years ago? A five-year plan five years ago?

harsh blade
#

what is two sum algo used for? it was the first problem i tried solving but failed miserably lol sad anyway i wonder how they use it in real applications?

robust dagger
harsh blade
#

thank you alot

fiery cosmos
robust dagger
ripe kayak
#

Can someone help with my pandas dataframe project? I am trying to find all duplicates

#

I am trying to find duplicates by group

dusky trellis
#

group with an aggregate function of count then select those with count > 1

halcyon plankBOT
#

Hey @jagged void!

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

#

Hey @jagged void!

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

woven mirage
#

what are some good resources to learn algorithms and data structures?

agile sundial
#

clrs

woven mirage
#

@agile sundial https://en.wikipedia.org/wiki/Introduction_to_Algorithms ?

Introduction to Algorithms

Introduction to Algorithms is a book on computer programming by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The book has been widely used as the textbook for algorithms courses at many universities and is commonly cited as a reference for algorithms in published papers, with over 10,000 citations documented on C...

agile sundial
#

indeed

woven mirage
#

i'll take a look

#

thanks

late coral
#

will check out

brittle moat
#

hey guys, I solved the problem Given a roman numeral, convert it to an integer. ```python
def romanConversion(s):

complete_string = 0
roman_dictionary = \
{"I": 1, "V": 5,
"X": 10, "L": 50,
"C": 100, "D": 500,
"M": 1000}

for letter in s.upper():
    if letter in roman_dictionary.keys():
        complete_string += roman_dictionary[letter]

print(complete_string)

romanConversion("XXVII")``` What's a better way to solve it?

robust dagger
brittle moat
#

That’s true

brittle moat
robust dagger
#

You need to keep track of the most recent value you saw.

#

If the next value is larger than the previous one, then you should have subtracted.

haughty mountain
#

fwiw I prefer parsing roman numerals backwards

#

add if the next number is ≥ than the biggest seen so far, otherwise subtract

#

!e let's try

values = {"I": 1, "V": 5,
    "X": 10, "L": 50,
    "C": 100, "D": 500,
    "M": 1000}

s ="XIV"
biggest = 0
res = 0
for d in reversed(s):
  val = values[d]
  if val >= biggest:
    res += val
  else:
    res -= val
  biggest = max(biggest, val)

print(res)
halcyon plankBOT
#

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

14
dreamy comet
#

I wrote a program to calculate the slope of a line.

#

` rise = 0
run = 0

y1 = 3
y2 = 7

x1 = 2
x2 = 5

rise = y2 - y1
run = x2 - x1

slope = rise / run

print(slope)`
frank glade
#

Hello, could you please help me to solve the following exercise

fiery cosmos
#

No

ember mica
#

Hey Hi all

#

I am new to coding can someone help me out to learn how to code

fiery cosmos
#

That's not what this channel is for, if you want a basic introduction to python you can search for many tutorials online (preferably written documentation).
You can try the official tutorial https://docs.python.org/3/tutorial/

ember mica
#

thank you reffie

brittle moat
#

I can't get this code to work

# 
roman_numerals = {
    "I": 1,
    "V": 5,
    "X": 10,
    "L": 50,
    "C": 100,
    "D": 500,
    "M": 1000
}

class Solution:
    def int_to_Roman(self, num):

        roman_numerals_tuple = [(value, key) for value, key in roman_numerals.items()]
        roman_numerals_tuple.reverse() #reversing the order of the list, for divmod function


        roman_numeral = ""

        for (n, roman) in roman_numerals_tuple:
            (d, num) = divmod(num, n) # error on this line
            roman_numeral += roman * d

        return roman_numeral

S = Solution()
print(S.int_to_Roman(131))``` does anyone know how to fix it? /
haughty mountain
#

there isn't really any choice to be made, so no

halcyon plankBOT
#

@round valley :white_check_mark: Your 3.11 eval job has completed with return code 0.

MMCCXLII
round valley
# brittle moat ```py roman_numerals = { "I": 1, "V": 5, "X": 10, "L": 50, "...

!e

map = {1000: 'M', 900: 'CM', 500: 'D', 400: 'CD', 100: 'C', 90: 'XC', 50: 'L', 40: 'XL', 10: 'X', 9: 'IX', 5: 'V', 4: 'IV', 1: 'I'}
map2 = {v: k for k, v in map.items()}

def dec_to_roman(n):
    roman = []
    for r in map:
        x, y = divmod(n, r)
        roman.append(map[r] * x)
        n -= (r * x)
        if n <= 0:
            break
    return ''.join(roman)

def roman_to_dec(r):
    dec = 0
    while r:
        for k in map2:
            if r.startswith(k):
                dec += map2[k]
                r = r.removeprefix(k)
                break
        else:
            raise ValueError('Not valid Roman numeral.')
    return dec

print(dec_to_roman(2242))  # 'MMCCXLII'
print(roman_to_dec('MMCCXLII'))  # 2242
halcyon plankBOT
#

@round valley :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | MMCCXLII
002 | 2242
tulip bone
#

You can get a free sandwich on Thursday only if you buy a sandwich or a cup of soup
how can i translate this propositional logic?

#

like what could the propositions be here
p: You buy a sandwich
q: You buy a cup of coffee
r: You get a free sandwich on Thursday
or
p: You buy soup or sandwich
q: It is Thursday
r: You get a free sandwich

naive oak
#

i would have
you buy a sandwich
you buy a cup of soup
it is thursday
you get a free sandwich

real oriole
#

Has anyone here tried solving the cses.fi problem set in python. Is it doable with the 1 second time limit?

real oriole
#

I lost my account where I did most of the stuff in c++. It's been years and I have forgotten everything 🥲

#

Are there other platforms with the same cses questions?

#

:(

crude galleon
#

i am really struggling with time complexity

#

can someone help me

#

I understand the basic concept that x^n is worse than n^2 and that is worse than n etc

#

but i do not understand how this relates to actual numbers. of time relative to n

#

like here's an example:

#

n time
40 000 2 024 ms
80 000 6 085 ms
120 000 13 781 ms
160 000 23 079 ms
200 000 35 934 ms

#

I look at this and cant figure out if this is n, n^2 or something else. n is suppose to be linearly increasing, so something like 2-4-6-8 etc. In this case first one is 2k and second is 6k, then it's 13k. It does not appear to be a consistent linear increase. for n^2 it is suppose to be 2k, 4k,8k etc right? but this is 2k, 6k, 13k which is not quite right

#

but perhaps my understanding of linear is wrong

dusky trellis
#

n^2 is not linear

#

it's polynomial

#

2^n is exponential

vocal gorge
dusky trellis
#

that's a pretty graph but it implies negative execution time for n < 40000

#

that seems... unlikely

vocal gorge
#

but i do not understand how this relates to actual numbers
In theory, not at all, since the O-notation is about asymptotic behaviour, and at finite n other factors may dominate.
(though in practice, algorithms with better asymptotic complexity are in fact usually better.)

crude galleon
#

like another table is

300 000 000 545 ms
350 000 000 610 ms
400 000 000 740 ms
450 000 000 831 ms
500 000 000 900 ms

#

this seems like logn tho

#

because its so small increase

vocal gorge
#

900/545 is 1.65, 500/300 is 1.66, so this looks nearly perfectly linear to me.

dusky trellis
#

that is clearly linear

#

the previous times looked pretty polynomial (n^2) to me

crude galleon
#

yeah so basically I dont know where the problem lies but I cant figure this out

dusky trellis
#

what problem? what's to figure out?

crude galleon
#

problem that I look at second table and think its logn when its linear

dusky trellis
#

well, it could be log n. unlikely, but possible

#

you don't have a wide enough range of n's to be sure

#

both polynomial and exponential and logarithmic time can appear linear time if you zoom in enough

#

I don't know how to ask this without sounding like an a**hole, but didn't you cover this shit in HS math class?

outer rain
# crude galleon but i do not understand how this relates to actual numbers. of time relative to ...

This is not going to be a simple answer, so I won't explain what time complexity is. I will only explain why it's a bad idea to guess time complexity from runtime. This answer is not for a beginner and probably is not suitable for learning exercises.

According to my experience, time is not in a tight relationship with time complexity. If you know a time complexity of an algorithm and a general time it takes to handle a small query, you can use that to roughly approximate the time it will take the algorithm to run on a larger query. By "roughly" I mean you will be at most 10 times off (with good enough p-value). This does not work the other way around at all. By having just 5 points you will not be able to guess the time complexity. At least a few dozens (preferably hundreds) are required to make some assumptions.

Why? Because big-O only shows the largest term in value-time mapping. In reality it always comes with a constants you will need to guess. Even if you assume your time is a polynomial an^2 + bn + c this will require you to have at least 4 points to determine a, b, and c, but since they can vary significantly, those are absolutely useless, and you need to do actual analysis to find a, b, and c. Otherwise you are just eyeballing the big-O with no scientific reasoning.

And time will vary. The address space in your PC is randomized, which means sometimes the physical page layout will be better and your code will perform better. Sometimes your environment variables will be larger, the stack will be aligned better and will use cache more efficiently. Sometimes you will randomly shuffle a few pieces of code around, compiler will optimize it slightly differently, and branch predictor in the processor will be correct more often. This may lead to performance differences of up to 50%. This is much less noticeable in python of course, you effect still applies to some degree, especially the garbage collection/allocation overhead may vary significantly.

#

There is a wonderful talk at strange loop about it: "Performance Matters", and I can confirm that everything what is said there is true. Trust me, I've done a lot of optimization in my life and I know that modern processors don't make any sense.

crude galleon
#

so when all thats given to me is just n and time and asked to figure out the time complexity based on only those two things is, my best bet is just gut feeling

#

and some rough context based on how close numbers are to each other

outer rain
#

Pretty much. To be honest, I have no idea why would you even ask that question. If you have an algorithm, you can easily approximate it's time complexity. If you have it's actuall run time, you have a way, way more powerful tool than time complexity.

crude galleon
#

well above tables were mostly training questions which I was not confident in my answers so wanted to ask here to get some help

#

and there was no other context

#

just a table with time and n

dusky trellis
#

don't go with gut feel

outer rain
#

you can make a guess, you will never be sure

vocal gorge
#

Look at the ratios of times and the ratios of ns. For linear, the ratios should be roughly the same. For quadratic, the time ratio should be roughly the square of the n-ratio. For logarithmic, a multiplicative increase of n corresponds to an additive increase in time. For exponential, the opposite.

dusky trellis
#

because "gut feel" is your lizard brain at work and your lizard brain is not good at math

crude galleon
#

i see

#

on another question about time complexity. When there is two or more recursions the time complexity becomes someting like 2^n, so if there is only 1 recursion is it 1^n ?

#

or what is it exactly in that case

#

because 1^n is constant

#

as in its always 1, so it does not feel right to assume that

lament totem
outer rain
crude galleon
#

yeah i am guilty of going based off of memorization rather than context

lament totem
#

A cool example that my prof gave for time complexity was the following

i = N
while i > 0:
  i = i // 2
  j = i 
  while j > 0:
    j = j - 1
#

Which isn't O(N log N) like you would expect at first glance 🙃

crude galleon
#

yeah looking at that code makes me feel like i know nothing about time complexity 😦

#

like that feels like nested loop to me

#

so a n^2

outer rain
#

But my personal favourites come from number theory

#

for example a simple gcd fold with euclidean algorithm, like this:

a = [...]
g = 0
for x in a:
    g = gcd(g, x)

Is not just O(n log C), but O(n + log C). And I love this because there is so much complexity in this simple example. It's so, so deep and beautiful.

opal oriole
# outer rain This is not going to be a simple answer, so I won't explain what time complexity...

This is a "guess what comes next problem." Answering it involves inductive reasoning (statistics), which does not guarantee things. The best option here is to apply Occam's razor and pick the most simple curve that explains it (there are infinite valid answers otherwise), which is one of the simple curves like linear, quadratic, log, exp. Start with the most simple one. But without really having more points, it could easily be anything, and even then, we are dealing with probabilities, not guarantees. Given only those few points, you could give many different answers and argue that they are valid (this is why the "guess the next number," problems you may have seen are silly (they are more of a bias check than anything else)). @crude galleon

vocal gorge
#

also, pedant inside me wants to say it is in fact O(N log N), it's just not Θ(N log N)

lament totem
#

It's O(N), because it takes n/2 + n/4 + n/8 ... iterations

#

But this was more of a trick question when we had it on the exam

vocal gorge
#

I know it's Θ(N), the pedantry relates to the fact that e.g. any function that's O(n) is also O(n^2) and O(e^n) and infinity others, because O is an upper bound.

#

Most time people talk about O, they actually mean Θ - not just an upper bound, but a tight one, one that can't be improved.

crude galleon
#

when it talks about growth rate in this table what does it mean exactly

Skarmbild_2023-02-23_202724.jpg
#

like are those numbers suppose to represent t or t(n)

vocal gorge
#

I'm not sure what you're asking. For example, n^2 for n=8 is 64. It's just examples of some functions.

crude galleon
#

ah I see, I was reading the table wrong

#

its columns in relation to the first column

dusky trellis
#

lol

dusky trellis
#

t is dependent on n

vocal gorge
dusky trellis
#

well, at least my conclusion was correct 🙂

agile sundial
#

that doesn't count if you can't support it 😛

dusky trellis
#

there, now I appear smarter

vocal gorge
#

one can naively say it's O(n log n) in the same way one can naively say that || because the sum N//2 + N//4 + ... + 1 has ~log(N) terms with the highest being N//2, it's at most N log N|| - it's a correct upper bound, but it turns out it's not a tight one in this case.

opal oriole
crude galleon
#

so I am looking at this code

public void compute(int a[], int l) {
    if (l <= 1) {
        return;
    }
    compute(a, l - 1);

    int last = a[l - 1];
    int i = l - 2;

    while (i >= 0 && a[i] > last) {
        a[i + 1] = a[i];
        i--;
    }
    a[i + 1] = last;
}

and trying to figure out the time complexity for it . There is a single recursion so that is an O(n) and there is a simple while loop that check two conditions which is another O(n). Does it mean that this code has time complexity of O(n^2) ?

#

or am I totally wrong

agile sundial
#

you can't think "loop -> O(n)". stop thinking this, it's not correct

crude galleon
#

should I look at whats inside the parenthesis instead of the loop ?

agile sundial
#

well you need to look at both

#

your answer ||seems to be correct, but your reasoning is a bit shaky||

vocal gorge
#

ultimately, you need to count the number of operations, pretty much.

agile sundial
#

i actually like this code it's kinda clever

crude galleon
#

i know that the if statement is one and done thing so thats O(1), so is int last and int i

#

same applies to the things inside the while loop

#

last line of code seems to be O(1) too

agile sundial
crude galleon
#

i suck at this

snow anvil
#

The thing inside the while loop is O(1) * however many times it is triggered in while loop

crude galleon
outer rain
#

because I would start from here. It's hard to figure out how long something takes if you don't even know what it does

snow anvil
#

More importantly how it does what it does

crude galleon
#

hmm, I am actually not sure if I am being honest.

#

perhaps my issue is fundamental

#

like I know there is a recursion and a break point

outer rain
#

Not as fundamental as my brain damage, you will figure this out eventually 🙂

crude galleon
outer rain
#

Look at the code, follow it step by step, figure out what it does, estimate how many operations it takes

agile sundial
outer rain
crude galleon
#

my one issue is that inside the while loop

int last = a[l - 1];
    int i = l - 2;

    while (i >= 0 && a[i] > last) {

let's say l is 5. a[4] then i = 3. Which means inside the while loop a[3] > 4 will not be true

#

and this is an and statement

#

so this will be false

#

then nothing inside the while loop matters

#

then you would do a[3 + 1] = last which means last is now 4.

outer rain
crude galleon
#

so int last = a[l - 1]; is not the length of the array ?

agile sundial
#

it is the value in the array at l - 1

snow anvil
#

which language is that btw 💀

outer rain
#

Nope, why would it be the length? Consider a = [6, 2, 3, 5, 1, 4, 5, 7] and l = 4 or something, idk. The a[l - 1] is 5. You know how arrays work, don't you?

outer rain
crude galleon
#

java

outer rain
#

same thing

snow anvil
#

ah 2 I don't care to learn 💀

crude galleon
snow anvil
#

so I take it you are taking something like a discrete math course or algos and datastructures?

crude galleon
#

latter

#

we just began, some weeks ago

snow anvil
#

I'd recommend you familliarize yourself with the language first
it'll be hard to understand any of this if you don't know what the code actually does at any given point

#

write some code

#

maybe even do leetcode

crude galleon
#

yeah we have a project starting soon

#

I hope that will help me

snow anvil
#

I suggest you start sooner rather than later

#

just do some easy leetcode problems

#

your code will be slow

#

ask people why

crude galleon
#

i never heard leetcode so will check that out

snow anvil
#

if your solution is n^2 it won't submit I think

crude galleon
# crude galleon so I am looking at this code ``` public void compute(int a[], int l) { if ...

so i have been trying to understand this code. i don't know how close I am to truth but here goes nothing. it seems like this program compares a value in a specific index of an array with the value at one lower index. if the number with smaller index is larger than the other one then it replaces the value. Then you basically repeat this to compare the value at one lower index until the while loop becomes false. After that the value at index 0 becomes the value at index of "last" variable

#

I am not confident in my logic ngl

#

idk how the compute recursion comes into this playing field

agile sundial
#

not index 0, last is placed in the last location of i before the loop stopped

crude galleon
#

so this code basically turns an array into ascending right

#

from smallest number to highest

snow anvil
#

in other words it is a sorting algorithm if you are right

agile sundial
outer rain
#

👏👏 👏 👏 👏

agile sundial
crude galleon
#

?

snow anvil
#

(different sorting algorithms will obviously perform differently)

snow anvil
crude galleon
#

hmm, Its very hands on method so i believe it's definitely not one of the more complex algorithms like the one that uses binary tree

#

but i cant quite name which exactly

#

looking up in internet it seems to be insertion

agile sundial
#

it ends with "sort"

crude galleon
#

insertion

agile sundial
#

indeed

#

🎉

crude galleon
#

😄

#

it does feel good

#

but I still dont understand the point of that recursion

snow anvil
#

well if you just ran it for one item it would not work

agile sundial
snow anvil
#

you'd need at least another loop

crude galleon
snow anvil
#

in py sorting with recursion wouldn't work so well 😭

crude galleon
#

quick read up on the internet says, well basically what this code does. Just compare everything to one specific thing until everything is in right place

agile sundial
# crude galleon not really

ah that would explain it. essentially the idea in insertion sort is you incrementally build up the sorted array on the left side of the array by shuffling elements to the right if they're greater

crude galleon
#

which sounds like it would be really annoying algorithm to use if you have millions of number to go through

agile sundial
#

indeed, it's relatively slow compared to more advanced algorithms. but insertion sort is actually still pretty useful

snow anvil
#

it is easy to write but for that I prefer selections sort

crude galleon
#

so i know that due to the nature of arrays it's a O(1) to pick a random number in it

#

but for things like comparing the index value of an array with another index value

#

is that still O(1)

snow anvil
#

yuh for time complicity you always want to look at how many times the loops run

agile sundial
crude galleon
#

yeah element

snow anvil
#

recursion in this case being a sort of loop

icy oasis
#

hi everyone. does anyone have experience with linear programming using PuLP? :D

agile sundial
#

for ints you can assume it's O(1), but strings is O(len(the_string))

icy oasis
snow anvil
#

are u sure would the pc not just swap the memory adresses of the items or however the fuck that works?

#

my first solution was O(n^2) which is how I know it fails ;D

crude galleon
snow anvil
crude galleon
snow anvil
#

well yes it is but you are forgetting something very important

crude galleon
#

is it the recursion?

snow anvil
#

yes

#

what happens if the array isn't sorted yet after an iteration?

crude galleon
#

it only changes the element of the last index right

agile sundial
snow anvil
agile sundial
#

wdym "an iteration". of the while loop?

snow anvil
#

not sure can't read java

#

I know how the algorithm is supposed to work but I can't say anything about this implementation

#

since again I don't understand the syntax

#

@crude galleon have you looked at binary search yet?

crude galleon
#

yeah

#

its the one I am most familiar with

snow anvil
#

and you understand its time complexity?

crude galleon
#

binary search is logn right, cause when n increases you need only one more time to run it

snow anvil
#

it is logn that is correct I don't really understand what u mean by that explanation but I think it's nice to compare it to linear search to see the difference between logn and n

icy oasis
#

hi everyone. does anyone have experience with linear programming using PuLP?
i'm trying to implement a problem where the values in one time period are dependent on values in another but don't know how to model that using PuLP

shut breach
#

binary search halves the searchspace on each iteration, so doubling the input size only requires one more iteration

snow anvil
#

also if u know some basic linear algebra try to find a algorithm that does not need to multiply the matrix n times for matrix exponentiation

crude galleon
#

talking about binary trees a[i] = Arrays.binarySearch(n, i); this has no effect on time complexity right? i dont quite understand what this method does

snow anvil
#

well it probably does

#

depending on where it is being called

crude galleon
#

it is being called inside a normal iterative for loop

#

hmm actually

snow anvil
#

if there is a part of the function with higher time complexity than it it can be ignorted but it depends on the program

#

then that will probably n*log n

crude galleon
# 
public int[] compute(int[] n) {
    int[] a = new int[n.length];
    for(int i = 0; i < n.length; i ++) {
        a[i] = Arrays.binarySearch(n, i);
    }
    return a;
}
#

so the for loop is simple iterative function

#

so that's n

#

idk what binarysearch does but if it is using binary tree algorithm it would be log n right ?

#

and then you multiply these

snow anvil
#

ye

#

cuz the loop runs n times if you are telling the truth

#

and it will run this method n times

#

also it could be n*logm don't know what the method does specifically

crude galleon
#

hmm so I can not just say a loop is O(n) by looking at the for front of (). Thats just wrong way of thinking. But algorithms have specific always the case time complexity right ?

#

like a binary tree is always log n

agile sundial
#

how do you even do it in O(n^2)? i can't come up with a solution that would genuinely work in quadratic time

snow anvil
#

💀

agile sundial
#

that's not quadratic

snow anvil
#

don't worry abt it