#algos-and-data-structs

1 messages · Page 64 of 1

fallow agate
#

These patterns, you learnt from anywhere?

modern gulch
#

The planting problem above strikes me as a DP problem: it's not going to lend itself to some convenient solution other than brute force with optimization.

narrow mica
#

DP prolly the way to go
i.e. let ||dp[i][c] := min if you planted flower type c at i||

fallow agate
modern gulch
fallow agate
modern gulch
modern gulch
#

But besides that, take any popular web-scale company: there's many articles that'll talk about their architecture and evolution and design decisions. Reddit, Twitter, Facebook, Amazon, Google Search, etc have fascinating histories

haughty mountain
#

this seems like kinda textbook dp

#

let dp[i][j] be the smallest cost to plant the first i flowers, where the last planted flower was of type j

#

and you can express dp[i+1] in terms of dp[i]

#

the formula would be (in not quite python)
||dp[i+1][j] = min(dp[i][k] for k != j)||

west ocean
#

Ok

#

Is it alright if I draw it down?

opal oriole
#

Yes, that is even better.

west ocean
#

I’m allowed to send in images right?

opal oriole
#

Yeah.

west ocean
#

So let’s say this is our simple Binary tree

#

I want to insert 5

#

Each left child node must be less than the parent

#

While each right child must be greater than the parent

#

This is where the “binary search” of the binary search tree comes into play

#

Now to insert 5, we need to compare 5 with each node until we get to a leaf. If it’s less than the current node, it goes left, if it’s greater than the current node we go right

#

When we finally get to an leaf we append 5

opal oriole
#

Ok, what are the fundamental building blocks here? That is the first part to convert to code. Identify the objects involved in this process, they will need a representation in code.

#

You can highlight them in your English sentences.

#

(For more simple algorithms, it often revolves around one object)

west ocean
#

Ok

#

The first value, the one you want to insert is 5

#

The second value is the node you are comparing 5 to

opal oriole
#

Ok, so two keywords there, value and node.

#

These things are fundamental objects present in the problem, that we will need to operate on.

west ocean
#

Hmmm

opal oriole
#

So keep a list of the objects, and mark them as needing some representation in code, there are multiple options for this, but they both need some implementation.

west ocean
#

I could write the possible sudocode here

opal oriole
#

Yeah, but before that I just want to list things at an even more high level.

west ocean
#

Oh, ok

opal oriole
#

So we know what must show up in the code somewhere.

west ocean
#

Mhm

opal oriole
#

Now a little asterisk on that, sometimes some things are reperesented implicitly, so no directly in code, but either way make that list.

opal oriole
west ocean
#

To insert 5, compare node, go left if lesser, go right if greater, run until leaf node

opal oriole
#

So we can "go left" and "go right" (based on some conditions).

#

And those transition us from the current state to the next state (which is now the new current state).

west ocean
#

So If/else statement?

opal oriole
west ocean
#

Kk

opal oriole
#

So how is the "current state" represented? Which objects are used and how many? (from the list)

#

(Some objects are part of another)

#

The current state being the current place the algorithm is in / at at each step.

#

As in "state of being."

west ocean
#

“Current state” would be the first value of the comparable range of the branch to it’s leaf

opal oriole
#

Maybe this is what you meant, but let give another example. Say I have a house with 3 rooms, A, B, and C, and A <-> B <-> C is the layout, with "<->" meaning there is a door between them. If I start at A, and want to go to C, I can give a step by step instruction of start at A, go to B, go to C. My start state is "A," and I can represent my current state with just a single letter (the room name).

#

If I had in my object list "room," then each current state would be represented by one "room."

west ocean
#

Mmmm

#

So the current node would be the node that I’m comparing to

opal oriole
#

The important thing here is to think through time, where we have transitions between states through time, as the algorithm runs, and what is needed at each point in time.

west ocean
#

And after I compare the next value would be the new “current node”

opal oriole
west ocean
#

Ah, alright

opal oriole
#

Like moving from one room to another, the "current room" is updated to be what the "next room" was.

#

An algorithm runs through time, and so if we find out what is needed at each point in time to represent that point in time in code, and then what the transitions are (in the case of the binary tree, go left, and go right), and then when to do those transitions (the conditions), then we more or less have the solved problem.

west ocean
#

Ahhh

#

I think I got it

opal oriole
#

So what is the object list, can you write out for me?

#

To recap.

west ocean
#

The entire Binary tree?

#

Including 5?

opal oriole
#

The object list are the individual components, the binary tree is technically also in that list as it's the whole thing, but I meant from your English sentence describing the solution earlier, there were two other keywords, and they are what the binary tree is made of.

opal oriole
#

And also there is "value."

west ocean
#

Oh

opal oriole
#

The tree is made of nodes, which hold values.

#

So for object list: tree node value

#

They can be found in your own English description, so if you are unsure about how to code it, start by highlighting these.

#

Next, you can write down the relationship between these.

#

"A tree is made of nodes that hold values."

#

Still just writing English, not code yet.

west ocean
#

Gotcha!

opal oriole
#

So next, we have the object and their relationships, what are the actions / transitions between states?

#

(Not conditions, just the actions themselves)

west ocean
#

Greater than or less than?

opal oriole
#

That would be conditions.

west ocean
#

Oh

opal oriole
#

You wrote them before, "go left," "go right."

west ocean
#

Left or right

opal oriole
#

Ok, so now we have ```
Objects:
tree
node
value
Tree is made of nodes which hold values.
Transitions/actions/operations:
Go left.
Go right.

#

We are missing a bit on the actions.

#

When we get to the end, we need to actually insert the value.

#

The final action.

west ocean
#

Mhm

opal oriole
#

If you have a "final" or "unique" action or object, mark it as such.

#

Using your wording from before "append the node."

#

To "go left," "go right," "append node." (final action).

#

Next, identify the conditions under which the actions happens.

west ocean
#

So now greater than or less than?

opal oriole
#

Yes.

west ocean
#

Kk

opal oriole
#

And try using the word "if."

#

So still in English, can you describe it?

#

And the previous list of objects and actions.

#

Try to use all of them.

west ocean
#

If the value 5 is greater than the value of node then go right
If the value 5 is less than value of the node then how left
If there are no more nodes append 5

opal oriole
#

Ok, so this is already more refined the the original, getting closer to code too.

#

So now lets refine it more.

#

What exactly does it mean to "go right?"

#

And to answer this you can partially get there by asking the question how "node" should be represented to make that as easy as possible to implement.

west ocean
#

The value 5 compares itself to the right child node

opal oriole
#

What information do you need at each point in time to make the decisions?

#

And where does it come from?

#

Where is it stored?

opal oriole
#

Given our current description, where do we pull that from? Which objects have it?

#

The objects hold all our data, so we know it has to be in one of them.

#

(Or multiple)

opal oriole
#

And also "value."

#

Nodes hold values, so we know we are getting value from node.

#

So if you could define what is "inside" node, what would you like to be there?

#

We know value is in there.

#

Basically we need some way to fetch or compute the left and right children.

#

And so they need to be referenced somewhere in some way.

#

We can't pull them out of nothing.

#

Right now in the English description we are, because we have not given that detail yet, we just assume we have it somehow. Now we want to know how / where.

west ocean
#

How do we do that?

opal oriole
#

So there are multiple options, but the key thing here is that for every object involved, we need to be able have a reference to it somehow.

#

There are multiple ways to do this in code and I will give just one.

#

Are you fimiliar with classes in Python?

west ocean
#

Yes

opal oriole
#

Ok, what they let us do at the most basic level (and most important part) is bundle things together, this makes things concise and convenient as many variables are often used together in the same context.

#

(Passed around together, they are related)

#

Variables are a form of reference to an object / entity.

west ocean
#

Yep

opal oriole
#

So we know we need at least three references for our description. The value, the left child, and the right child. WIthout these we can't use our description.

#

We need them all at the same time.

#

When you need a bunch of things all the same time/place, a class can be a good tool to solve it.

#

Can you make a class with those three variables? What is the class name?

west ocean
#

I have to make one full class, right?

opal oriole
#

Yes.

west ocean
#

Tree

#

Would that work?

opal oriole
#

That would contain everything. Think about one point in time what you need. The description you gave before.

#

You need the value, the left child, and the right child.

#

And node.

west ocean
#

Value which is 5

opal oriole
#

So without a class, you could just have ```
value = 5
node = ???
left_child = ???
right_child = ???

#

You need all 4 at that point in time.

west ocean
#

Hmm

#

Node is 25

opal oriole
#

Ok, but how do we "fetch" these?

#

They are stored somewhere in some way.

#

For the value it's simple, we are given it and can just set it once.

#

But at each step, we need to retrieve node, left child, and right child, and this depends on how/where we stores the nodes.

#

This is the datastructure part of data structures and algorithms.

#

We know that we want to store them in a binary tree structure, but how?

west ocean
#

Node.left_child and node.right_child???

opal oriole
#

Yes, but why?

#

Or how do we get there?

#

The key is taking the objects the structure (tree) is made of (nodes), and their relationships and encoding that in code.

west ocean
#

How though?

opal oriole
#

So see how in your diagram you have nodes pointing to other points?

#

In other words you can get from one to another.

#

So if I have a node, I have a reference / way to compute a reference to the children.

#

The key here is "references."

#

Variables are references.

west ocean
#

So node.left_child would be the value of the left child?

opal oriole
#

And so if I have a reference to node, I would like to have a reference to left and right nodes.

#

And also I would like a referenece to the value of that node.

#

In other words, node contains references to value, left node, right node.

#

Data structures is all about how you can get one thing to another via references.

#

And then setup in a clever way to make it efficient.

west ocean
#

How could I translate it into python though?

opal oriole
#

So we have nodes, and they have those things in them.

#

When you have a container, you can use a class.

# 
class Node:
  def __init__(self, value, left_node, right_node):
    self.value = value
    self.left_node = left_node
    self.right_node = right_node
#

Now I can make Nodes.

#

And I can build a tree by setting up the references between them.

opal oriole
# west ocean 
# This is just the 25, no children yet.
root = Node(25, None, None)
# Add the children by making them and setting up the references, this is now a tree structure.
root.left_node = Node(15, None, None)
root.right_node = Node(30, None, None)
west ocean
#

I think I get what you’re saying

opal oriole
#

It's a tree because I can follow the references from the top node down to whatever child.

#

The structure is the reference scheme.

#

You can think of the 1D version with the rooms, each would have a reference to the next and previous room, forming a chain of rooms that I can traverse.

#

The varaibles link them together.

#

Variables can directly references simple values, like 5, but they can also reference something that references other things.

west ocean
#

Mhm

opal oriole
#

Using the method I gave, build the entire tree in your image manually like I was.

west ocean
#

So then from there I can start building my functions?

#

For left and right?

opal oriole
#

Yes, so, when you are given such a programming problem, they will often have built the tree for you.

#

But to make sure you get the structure first, try making the tree manually.

west ocean
#

Ok

#

Hold on

west ocean
violet notch
#

Hello team, I was wondering if you have any useful rules of thumb when using recursion in typical recursion, backtracking and dynamic programming problems. Thank you in advance:)

tight cedar
#

get the base case right first ig 🙂

quasi oracle
# violet notch Hello team, I was wondering if you have any useful rules of thumb when using rec...

Writing recursion is a lot like mathematical induction:

  1. You make it work for the base case.
  2. You assume that your function works for the recursive call, and with its result you show how you build the answer for the current call. For example, if you have a function f(n) which calls f(n-1), you write it by assuming f(n-1) works, and from its return value you create the return value for your current f(n).

Another rule of thumb is that at least in Python, everything you can solve with recursion you can also solve without recursion, and it's usually easier without. It's a nice exercise at least

haughty mountain
#

not always easier

#

but avoiding recursion in python for performance reasons if often a good idea

quasi oracle
regal spoke
# violet notch Hello team, I was wondering if you have any useful rules of thumb when using rec...

Something good to know about is that there is a trick to quickly convert a recursive DP solution to iterative ("bottom-up").

Say for example that you've coded this recursive solution for computing fibonacci numbers (mod 10^9 + 7 to keep them small).

import functools
MOD = 10**9 + 7

@functools.cache
def fibonacci(n):
  if n <= 1:
    return n
  return (fibonacci(n - 1) + fibonacci(n - 2)) % MOD

n = 10**5
print(n)
#

You can convert this to bottom-up DP simply by

#

!e

import functools
MOD = 10**9 + 7

@functools.cache
def fibonacci(n):
  if n <= 1:
    return n
  return (fibonacci(n - 1) + fibonacci(n - 2)) % MOD

n = 10**5
for i in range(n):
    fibonacci(i)
print(fibonacci(n))
halcyon plankBOT
regal spoke
#

I would definitely recommend to start out with a recursive solution, and then use the trick ^ to make it bottom up if recursion is too slow/you are hitting the recursion limit.

steady bone
#

in an http request , why is http requesting things from me?

regal spoke
violet notch
#

I am currently practicing for coding interviews in Python, while I do find the iterative solutions more intuitive I am doing my best to learn recursion in case it is asked from the interviewer. Would you consider solving everything iteratively a viable approach?

regal spoke
#

Only when you are thinking about implementing it is the iterative approach considered

#

Best idea is to just ask which one the interviewer prefers.

steady bone
#

what does -> mean
for example data ->

lean walrus
#

that is an arrow

hushed nova
fallow agate
#

Hi,
any good course for system design?

quasi oracle
stiff quartz
#

Because sometimes you have so much data that it doesn’t fit in the ram
Also the ram is reset when your computer reboots so you need to go through the hard drive eventually anyway

#

@fallow agate

fallow agate
#

currently i am learning system design.
what i am thinking is to start the ball rolling with implementing a server using flask framework.
& then whatever the concept i am going to read, suppose caching, i will integrate a simple nosql database named TinyDB into my project(i will make my application use this nosql data base for caching).

Next, suppose i read the concept of load balancing, then i create 2 more flask servers & will write small code in python to route the requests to different servers one after the other, using round robin algo.

this way, i not only learn theory but also practice practically.

Once i covered all system components like this one by one, finally i will start practising questions like how to design Instagram & how to design what's app etc.

Any corrections to my strategy/suggestions?
Does this help me to answer system interview questions?

steady bone
#

graphql Vs Realm which one you choosing and why?

fiery cosmos
#

(I know that there is better solution but I am interested to know what is wront with my code)

I am trying to solve this problem https://neetcode.io/problems/lru-cache

This is my code: https://pastecode.io/s/0h8m4saq

I do not understand how as a result I get [null,null,10,null,null,-1,10] instead of [null,null,10,null,null,20,-1]?

NeetCode

A better way to prepare for coding interviews.

quasi oracle
fiery cosmos
sacred kindle
#

looking for a hacker

jolly mortar
#

man the editorial solution for today's H is certainly something

wheat oriole
#

hi

regal spoke
#

My guess is that the original code even had scanf/printf, which was changed to cin/cout to be more readable

#

Note that there is no cin.tie or sync_with_stdio

#

They also use the wonderful #define int long long

quaint walrus
#

can anyone point me to a python markov chain implementation i could look at in on github

haughty mountain
lean walrus
#

I kinda like it

tepid blaze
#

anyone got a heuristic for multiple knapsack problem?

#

or some python code that i can look at

brisk stream
#

hi

proven gazelle
#

^_^

#

I just don’t understand like where the Normal Bible sort would stop if it isn’t normally stopping when no swaps are made

haughty mountain
lean walrus
#

each pass "bubbles" one number to the end/top
so after n-1 passes n-1 highest numbers are sorted at the end, that also means that the lowest number is at the beginning, so everything is sorted

floral nebula
#

the datastructures course from opencourseware has too much pre req in math

#

i cant find a good datastructures course work. i really want to get a solid understanding of DSA. i already know a rough overview of the whole area as i had a whole subject on it in the last semester but i feel like i still don't have a solid understanding on the topic than being familiar to some algorithms and topics.

#

how do i get good at DSA

hushed nova
#

@floral nebula if youre looking for a course, im currently doing stiver's dsa sheet, high recommend it

modern gulch
blissful cypress
floral nebula
#

my goal is to actually understand data structures in detail

brisk stream
# floral nebula i have already covered some topics and data structures like stacks queues linked...

that is because you're only watching videos/courses and solving easy puzzles

you could use https://cses.fi/problemset/ and work by topic, you can't learn 5 topics in a month, but you can learn a lot about one single topic in a month, depending on how much effort do you put on it,

the datastructures course from opencourseware has too much pre req in math

I dont know why you dislike this, basically dsa is worse than maths, if you dont like math dont even try dsa

#

basically dsa/cp is for people than like to break their heads trying to solve something with a crazy solution

#

if you think you are that type of person, then keep it up

brisk stream
#

i am not good either, but i like it, if you want we can practice together and share solutions for diff problems

floral nebula
floral nebula
vital ivy
vital ivy
floral nebula
brisk stream
vital ivy
real hatch
#

How can I connect my custom Python algorithmic trading bot to the MT5 platform via TeamViewer?

modern gulch
hybrid topaz
#

Guys i have question and i dont know where to ask, my question is can phyton work with realtime database?

modern gulch
lean walrus
#

hello 👋
I implemented a Markov algorithms interpreter in python
pseudocode of it: #esoteric-python message

it works fine, but it is slow
I'm curious what data structures exist to solve this problem

#

most time is spent on iterating over rules and checking if they match or not

another point of concern is reallocating the entire string at each step even if only the small part of it has changed
I think the Rope DS can partially solve this problem [but it would mean that the built-in str in str would no longer be available]

#

all kinds of ideas (crazy or not) are welcome

haughty mountain
narrow mica
#

AC Automaton?
Should bump 1 iteration from O(len(rules)*len(before)*len(string)) down to O(len(before) + len(string)) but is complicated

haughty mountain
#

yeah aho corasick feels relevant

#

if replacement order doesn't matter it feels tempting to try to iterate over the string and shove stuff onto a stack, when a match is found you pop it and push the replacement

#

you might need some undo-ability in the string searching to make it really efficient though

lean walrus
narrow mica
#

in my head, there's also a possibility to have a rolling hash on the string and a range-update-point-query datastructure to reduce the if before in string from O(len(before) * len(string)) to O(len(string))
but len(before) isn't that big anyway as you said, dunno how much this affects things

lean walrus
#

since most time is spend on checking if rule match or not, it can be made faster by splitting work on several threads and then applying first found matched rule
but with gil it won't be faster

narrow mica
lean walrus
lean walrus
haughty mountain
#

trying to get rid of the linear cost string replacement is probably a good idea

lean walrus
narrow mica
haughty mountain
#

python string searching probably uses boyer moore or something

haughty mountain
narrow mica
#

then saw the opportunity to actually learn ACA
(which I definitely forgot by now)

haughty mountain
#

I had a groovy time

def magic(s) {
  def digits = s.findAll(/\d/)
  digits[0].toInteger()*10 + digits[-1].toInteger()
}

def part1(lines) {
  lines.sum { magic(it) }
}

def part2(lines) {
  lines.collect{
    it.replace("one", "o1e")
      .replace("two", "t2o")
      .replace("three", "t3e")
      .replace("four", "4")
      .replace("five", "5e")
      .replace("six", "6")
      .replace("seven", "7n")
      .replace("eight", "e8t")
      .replace("nine", "n9e")
  }.sum{ magic(it) }
}


def br = new BufferedReader(new InputStreamReader(System.in))
def lines = br.readLines()
println "Part 1: ${part1 lines}"
println "Part 2: ${part2 lines}"
lean walrus
halcyon plankBOT
#

Objects/stringlib/fastsearch.h lines 5 to 8

/* fast search/count implementation, based on a mix between boyer-
   moore and horspool, with a few more bells and whistles on the top.
   for some more background, see:
   https://web.archive.org/web/20201107074620/http://effbot.org/zone/stringlib.htm */```
`Objects/stringlib/stringlib_find_two_way_notes.txt` lines 19 to 22
```txt
The algorithm runs in O(len(needle) + len(haystack)) time and with
O(1) space. However, since there is a larger preprocessing cost than
simpler algorithms, this Two-Way algorithm is to be used only when the
needle and haystack lengths meet certain thresholds.```
haughty mountain
lean walrus
haughty mountain
#

do you have some decent test case?

haughty mountain
lean walrus
narrow mica
haughty mountain
# lean walrus

gives me flashbacks of
https://www.youtube.com/watch?v=8_npHZbe3qM

YouTube
suckerpinch
Generalized kerning is undecidable! But anagraphing is possible. (T...

This lecture is an addendum to my video about Anagraphs, which you should watch first (or only). I do two proofs by reduction: One that the "generalized kerning" problem is undecidable, and one that the "generalized anagraphing" problem is decidable. The first proof uses turing machines, and the second a fragment of linear logic. I try to explai...

▶ Play video
lean walrus
# narrow mica what is happening

that is how brainfuck is interpreted in markov algorithms :)
there are two "tapes": code and memory
to perform bf + operation you move a thingy from code tape to memory tape, and then perform increment there

lean walrus
narrow mica
haughty mountain
#

here is a cute rule set

rules = [
    ('0>0', '10>'),
    ('0>$', '<1$'),
    ('1<1', '<10'),
    ('^<1', '^0>'),
]

string = '^0>00000000$'
#

results

^0>00000000$
^10>0000000$
^110>000000$
^1110>00000$
^11110>0000$
^111110>000$
^1111110>00$
^11111110>0$
^111111110>$
^11111111<1$
^1111111<10$
^111111<100$
^11111<1000$
^1111<10000$
^111<100000$
^11<1000000$
^1<10000000$
^<100000000$
^0>00000000$
...
haughty mountain
#

so not the same replacement scheme you have

#

the proof in the video is a reduction from turing machines, i.e. basically implement turing machines with this rule replacement problem

#

!e another rule set and string

rules = [
  ('0|$', '1|$'),
  ('1|$', '|0$'),
  ('0|', '1>'),
  ('1|', '|0'),
  ('>0', '0>'),
  ('>1', '1>'),
  ('>$', '|$'),
]

string = '00000000|$'


for i in range(100):
  if string.endswith('|$'):
    print(string)
  for before, after in rules:
    if before in string: # profiling says that 99% of time is spent on this line
      string = string.replace(before, after, 1)
      break
  else:
    break
halcyon plankBOT
lean walrus
haughty mountain
# 
rules = [
  ('| ', ' |'),
  ('w ', ' w'),
  ('h ', ' h'),
  ('e ', ' e'),
  ('> ', ' > '),
]

string = "|wheee> "

|wheee>
|wheee >
|whee e>
|whe ee>
|wh eee>
|w heee>
| wheee>
|wheee>
|wheee >
|whee e>
|whe ee>
|wh eee>
|w heee>
| wheee>
|wheee>
|wheee >
|whee e>
|whe ee>
|wh eee>
|w heee>
| wheee>
|wheee>

lean walrus
#

sorting a string of a and b can be done in just one rule: ba -> ab

# 
Rules:
  0: ba -> ab

before: [6] >bababa<
after:  [6] >abbaba<
rule:   0: ba -> ab

before: [6] >abbaba<
after:  [6] >ababba<
rule:   0: ba -> ab

before: [6] >ababba<
after:  [6] >aabbba<
rule:   0: ba -> ab

before: [6] >aabbba<
after:  [6] >aabbab<
rule:   0: ba -> ab

before: [6] >aabbab<
after:  [6] >aababb<
rule:   0: ba -> ab

before: [6] >aababb<
after:  [6] >aaabbb<
rule:   0: ba -> ab

terminated: no matching rule
lean walrus
# haughty mountain ```py rules = [ ('| ', ' |'), ('w ', ' w'), ('h ', ' h'), ('e ', ' e'), ...

here is a challenge for you:
you are given a string of a and b
your goal is to reverse it:
aabb --> bbaa
abab --> baba
aaa --> aaa
etc

some other ideas if you are interested:

  • make a copy of a string
  • split a string into two strings of even and odd indices (s[::2] and s[1::2])
  • compute length of a string into unary system
  • compute length of a string into binary system
  • compute number of a and b separately
#

this is a binary counter:


s = State(
    '>0<',
    [
        Rule('0+', '1'),
        Rule('1+', '+0'),
        Rule('>+', '>1'),
        Rule('<', '+<'),
    ],
)
while True:
    s.step()
    input(s.string)
```  ```py
>0<
>0+<
>1<
>1+<
>+0<
>10<
>10+<
>11<
>11+<
>1+0<
>+00<
>100<
>100+<
>101<
>101+<
>10+0<
>110<
>110+<
>111<
>111+<
>11+0<
>1+00<
>+000<
>1000<
>1000+<
>1001<
...
haughty mountain
#

I can do a cheaty version which upper cases as well

rules = [
  ('aA', 'Aa'),
  ('bA', 'Ab'),
  ('bB', 'Bb'),
  ('aB', 'Ba'),
  ('a<', 'A<'),
  ('b<', 'B<'),
]

string = ">ababbaaa<"
lean walrus
#

there are actually two kinds of rules which were not refrected in my pseudocode: regular and terminating
if a terminating rule is matched, it halts the program completely, and the string you have is a result of your algorithm

haughty mountain
#

ah, termination was kinda my bigger concern

#

but if you can have terminating states that simplifies stuff

lean walrus
# 
string = '...' # current state, might be long (100+ or 1000+ chars), changes at each step
rules: list[tuple[str, str, bool]] = [...] # a couple hundred rules (both left and right side are pretty short - usually less than 10 chars), doesn't change
while True:
  for before, after, terminating in rules:
    if before in string: # profiling says that 99% of time is spent on this line
      string = string.replace(before, after, 1)
      if terminating:
        break@while # break 2 loops at once
      break # end the rule search, start again
  else:
    break # no rule matched - halt
print(string)
#

something like this

#

that gives you a possibility to give a result of bba for input abb
without terminating rules it would be switching between abb and bba forever

haughty mountain
#

yeah

lean walrus
#

sometimes terminating rules are denoted as foo ->. bar (note the point in ->.)

inner viper
#

hi

floral nebula
#

a deque is just a queue with insert at front and delete at last and only difference in algorithm is decrement of rear and head in those new operations??

lament glen
#

Hi, why it give syntax error when I declare an empty 2d array? data = [num_of_algs][] ^ SyntaxError: invalid syntax

narrow mica
lament glen
#

I recall previously I've been using this pretty often ...

narrow mica
#

do you want the result to be like this?

[
  [],
  [],
  [],
  ...   # num_of_algs many
]
lament glen
lament glen
#

exactly

narrow mica
lament glen
narrow mica
#

!e

l = [[]] * 5
print(l)
l[0].append(1)
print(l)
halcyon plankBOT
lament glen
vocal gorge
#

I recall previously I've been using this pretty often ...
in a different language, perhaps?

lament glen
#

Or, maybe I've beening useing "array = []" so I just took it for granted I could simply expand it to 2d array....

vocal gorge
#

in C/Java/etc the syntax would be along the lines of int data[10] (to declare a 10-element array data), and similarly data[10][20] for a 2d array.

#

in python, well, there's no arrays and no special syntax for them. there's just lists which behave like all other objects.

lament glen
#

for C there the bracket usually cannot be empty, as to Java I'm not that sure...

narrow mica
#

can't you do this?

int a[] = {1, 2, 3};
```or is this c++ only
lament glen
#

yes, btw can the compiler do c++ code in this channel?

narrow mica
haughty mountain
lean walrus
#

iirc in C you also can do int a[N][M] = {{1,2,3}, {4,5,6}, {7,8,9}};

#

and maybe int a[][] = {{1,2,3}, {4,5,6}, {7,8,9}};

narrow mica
lean walrus
#

just checked: x[][5] works but x[5][] does not

lament glen
lean walrus
#

yes

narrow mica
fiery cosmos
#

if programmer wanna represent tranditional POSIX file system which has files, folders and also possible symbolic links then which data structure should use? Graph or Tree ? I think without symbolic links Tree can be used because every file has only 1 unique path which prevents loops. When symbolic links involves i do not know i need to change tree based representation to graph or not

dusk ruin
#

reservoir sampling on wikipedia: https://en.wikipedia.org/wiki/Reservoir_sampling

Reservoir sampling is a family of randomized algorithms for choosing a simple random sample, without replacement, of k items from a population of unknown size n in a single pass over the items. The size of the population n is not known to the algorithm and is typically too large for all n items to fit into main memory. The population is revealed to the algorithm over time, and the algorithm cannot look back at previous items. At any point, the current state of the algorithm must permit extraction of a simple random sample without replacement of size k over the part of the population seen so far.

Why does it say that the population n is not known to the algorithm, but hten in the source code it is known?

(* S has items to sample, R will contain the result *)
ReservoirSample(S[1..n], R[1..k])
  // fill the reservoir array
  for i := 1 to k
      R[i] := S[i]
  end

  // replace elements with gradually decreasing probability
  for i := k+1 to n
    (* randomInteger(a, b) generates a uniform integer from the inclusive range {a, ..., b} *)
    j := randomInteger(1, i)
    if j <= k
        R[j] := S[i]
    end
  end
end
mint jewel
regal spoke
mint jewel
#

I preserved the 1 indexing

regal spoke
mint jewel
#

yea, that I just skipped

#

that part is not problematic in the pseudocode

regal spoke
#

Here is how I would describe the algorithm

num_samples_seen = 0
k = 100
R = []

def add_sample(s):
    global num_samples_seen
    num_samples_seen += 1
    if len(R) < k:
        R.append(s)
    else:
        j = random.randint(0, num_samples_seen - 1)
        if j < k:
            R[j] = s
#

!e

import random
num_samples_seen = 0
k = 10
R = []

def add_sample(s):
    global num_samples_seen
    num_samples_seen += 1
    if len(R) < k:
        R.append(s)
    else:
        j = random.randint(0, num_samples_seen - 1)
        if j < k:
            R[j] = s

n = 10**4
for _ in range(n):
    s = random.randint(1, 10**9)
    add_sample(s)
print(R)
halcyon plankBOT
regal spoke
#

Note how the algorithm has no knowledge of n (the number of samples it will be given)

#

add_sample simply just works with one sample at a time

#

It does however keep track of how many samples it has seen

last tangle
# 
print("Hello, world")
fiery cosmos
#

For this problem https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/description/

is this solution

class Solution:
    def findDisappearedNumbers(self, nums):        
        ans, seen = [], [False]*(len(nums)+1)
        for c in nums: seen[c] = True
        for i in range(1, len(nums)+1):
            if not seen[i]:
                ans.append(i)
        return ans

optimized version of this solution

class Solution:
    def findDisappearedNumbers(self, nums):
        s = set(nums)
        return [i for i in range(1, len(nums)+1) if i not in s]

because the boolean solution is only storing 1 byte of information while the hashset is storing 4 bytes?

stray fractal
fiery cosmos
stray fractal
#

3 things

  1. a boolean in python does not store 1 byte, it stores at least 12 or 24 bytes depending on the system
  2. first solution has a redundant operation
  3. "letting python do the work" is how things are mostly optimized, which happens in the 2nd solution
#

in conclusion the second one is theoretically faster

#

but it does seem like over large inputs the 2nd one gets slower

#

so it basically just depends on how large your input is

ivory bluff
#

Guys I am solving coding problems Can anybody help me here ?

fiery cosmos
stray fractal
#

ah i see

#

nvm

tight totem
#

Hii

#

I need code for breadth search function

#

My professor asked for it and idk wut exactly he need

tight totem
# 
from collections import deque

class Node:
    def __init__(self, state, parent=None):
        self.state = state
        self.parent = parent
        self.children = []
        
        if parent:
            parent.children.append(self)

def find(node, target_state):

    queue = deque([node])

    while queue:
        current_node = queue.popleft()
        if current_node.state == target_state:
            return current_node
        
        for child in current_node.children:
            queue.append(child)

    return None


root_node = Node("A")
B = Node("B", root_node)
C = Node("C", root_node)
D = Node("D", C)


result = find(root_node, "D")
if result:
    print(f"Node with state '{result.state}' found.")
else:
    print("Node not found.")```
#

Is this code explain breadth search correctly?

regal spoke
#

especially if someone gives it an evil designed sequence that makes set run in n^2

regal spoke
#

It is about using hash table vs not using hash table

lime quest
#

working on genetic algorithm to create timetable? Anyone willing to help

fiery cosmos
regal spoke
#

There is a lot more going on than what you might expect

#

While a boolean list is about as basic as it gets.

ripe oxide
mint jewel
jolly mortar
#

!cban 1276028320688898108 troll

halcyon plankBOT
#

:incoming_envelope: :ok_hand: applied ban to @rain copper permanently.

obtuse brook
#

Hello 👋 I am solving some past advent of code problems. For one of the problems, I need to count the number of literal characters in a string (I am not sure if the term "literal characters" is correct).
i.e. "\x27" -> 4 (\, x, 2 & 7)

Python processes this as "'" (apostrophe). Any ideas ?

narrow mica
obtuse brook
#

Yes

narrow mica
# obtuse brook Yes

I'm not sure what you mean exactly, cause if you use input() then it works perfectly?

>>> input()
\x27
'\\x27'
>>> len(input())
\x27
4
>>>
#

if you're storing \x27 as a string directly, you can add a r prefix so it doesn't turn into '

>>> '\x27'
"'"
>>> r'\x27'
'\\x27'
obtuse brook
obtuse brook
shadow glen
#

guys how do i make the comparation of the in t hing

#

i wanna compare it with strings

#

like a in "thing1, thing2, thing3"

shadow glen
#

guys, why my code is skipping lines?

#

it wasn't suppose to print stuff skipping lines

serene galleon
#

Why do i have this error ???

IMG_20241117_215239.jpg
quasi oracle
serene galleon
#

Yeah i don't have swichs

orchid violet
serene galleon
orchid violet
serene galleon
#

Just like a switch

orchid violet
serene galleon
#

Whats the difference ?

orchid violet
serene galleon
#

Ok thanks

hushed nova
#

this disjoint data struct just ate away my brain wtf yert

narrow mica
hushed nova
#

istg i was about to fall asleep

#

then looked at union by size, its somewhat understandable now

narrow mica
#

the really hard part comes if you try to prove the complexity

hushed nova
#

O(alpha(n)), he didnt explained it

#

ducky_sqlite basically said its near to constant time

narrow mica
hushed nova
#

i still havent done kruskal's yet, my brain cannot handle this much info for a day, so i have no idea how its gonna work with graphs

hushed nova
narrow mica
#

so check if nodes are connected => check if nodes are in the same group => fast with DSU

hushed nova
narrow mica
hushed nova
spice nacelle
#

I made an insertion sort algorithm and tested its performance and notice that everytime I ran the tests 2000 and 3000 elements were faster than 1000 elements. 1000 elements took 12 ms when 2000 took 4 ms and 3000 took 8ms. Why is that?
I used randomly generated array.

stiff quartz
#

Or use the Python timeit module

regal spoke
#

Basically, the first time you call sort, you do it on random data

#

which sorts the data used to benchmark

#

Then the rest of the benchmarks (after the first one) look weirdly fast

fiery cosmos
#

Given a list of lines which form a race track how would I color the inside of the track different from the outside of the track.

narrow mica
fiery cosmos
#

The colliders for a 2d race track are a list of lines. I want to know how i can color the outside of the track.

#

different from the inside

#

i guess i could make a 2d concave polygon from the lines and split that into a bunch of triangles then render thoes triangles as a track

narrow mica
#

the way you're describing it still doesn't make it clear

fiery cosmos
#

it is for a game

#

list of lines which are the colliders or edges of the race track

narrow mica
fiery cosmos
#

i don't want to color the lines i want to color the inside of the track.

#

the lines are just two points start and end

#

i know how to do it nevermind i asked

#

Triangle decomposition is what i needed

fiery cosmos
mint jewel
# fiery cosmos Can you explain?

Instead of doing [False]*len(nums), you'd much rather pack it bit by bit. This can be done by using a single int, and bit shifting. For example, to say that that 40 is found, you'd do
seen |= 1 << 40, and to check whether 25 has been found, you'd do
seen & (1 << 25)

haughty mountain
#

memory efficient yes

#

but toggling a bit might end up expensive for large bitsets, while with a proper bitset it's just O(1)

mint jewel
#

The big pain point is making the masks

#

1 << 1000 is not O(1), unfortunate

rare laurel
#

is 1 << n O(n/30) because base 2^30 digits?

haughty mountain
haughty mountain
regal spoke
#

I doubt it is faster

mint jewel
#

it is faster if it's a proper bitset, but yea, python ints don't work too well for this usecase

regal spoke
#

In Python u could store 63 bits in an int, and get true O(1) performance

regal spoke
#

The computer is kind of bad dealing with single bits in an efficient way

#

So for performance, counterintuitively 1 byte per bool is usually preferred

#

This is yet another reason for why c++ decision to make vector<bool> a bitset is stupid.

fringe bobcat
#

I am not able to identify error and even Google is not able see

num=[]
while True:
    input=input("enter number and 0 to exit")
    if input ==0:
        break
    num.append(int(input))
ordered=sorted(num)
ls=len(num) //2
median=ordered[ls]
print("gratest number is",max(num))
print("median is",{median})
    ```
#

What is error?

#

Ph error is variable sorry 😅

tight cedar
#

Don't use input as variable name

near grove
#

Does anyone know how I can turn these two arrays to a 3D array similar to the array at the bottom:

xe1 = np.array([["H", "F"], ["D", "F"], ["J", "I"]])

# [[[1,2], ["H", "F"]], [[3,4], [D", "F"]],[[5,6], ["J","I"]]] ```
narrow mica
#

second,

>>> np.stack((ex1, xe1), axis=1)
array([[['1', '2'],
        ['H', 'F']],

       [['3', '4'],
        ['D', 'F']],

       [['5', '6'],
        ['J', 'I']]], dtype='<U11')
regal spoke
# 
num = []
while True:
    x = int(input("enter number, 0 to exit"))
    if x == 0:
        break
    num.append(x)
num.sort()
ls = len(num)//2
median = ordered[ls]
print("greatest number is", num[-1])
print("median is", median)
half owl
#

does anyone know how i can implement a shortest path algo for a directed graph (like in the picture, but with self-arrows) with the following constraints:

  • without using a stack/queue/linked list
  • only with the option of using static arrays (implementing this in Java, couldnt find help online)
  • TC needs to be less than exponential TC
image.png
modern gulch
half owl
#

like in recursion

#

which is what im trying to do rn

modern gulch
#

With recursion, you'd need some memory structure to avoid infinite loops (ie; 3-4-3-4-3-4-...)?

#

And your problem statement says no stack/queue/list

regal spoke
#

But really, this sounds like they want you to use Floyd warshall

half owl
half owl
#

last semester i had i think the same problem and only managed to make it n^2 or something but with hash maps

#

or even n! cause idk if i managed

mint jewel
#

n! is better than exponential

regal spoke
mint jewel
#

also O(|V||E|) <= O(|V|^3)

half owl
regal spoke
#

Floyd is just 3 nested for loops, using a n x n matrix

#

I really think that is what they are trying to hint when they say you cannot use a stack/queue/linked list

mint jewel
#

yea, it does look likely

regal spoke
#

This is the entire algorithm

for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}
hushed nova
regal spoke
#

?

hushed nova
#

floyd warshall

mint jewel
regal spoke
haughty mountain
#

Stirling's approximation says hi

Screenshot_20241120-135556.png
narrow mica
# hushed nova floyd warshall

floyd-warshall just keeps asking
is it better to go A->B directly, or introduce some midpoint C and go A->C->B
repeat enough times

haughty mountain
#

so it's worse than exponential

mint jewel
#

oh wait yea ,I misremembered

haughty mountain
mint jewel
#

it's better than n^n

narrow mica
#

n! = 1 * 2 * ... * k * (k+1) * (k+2) * ...
if you select any exponential k^n, n! starts growing faster and faster after n == k

hushed nova
#

cause we introduce 2 matrices one to keep record of paths, iirc

#

and other for shortest distance

modern gulch
#

I'm just not sure they'd ask a student to implement this given those instructions. But, I dunno.

thorn oriole
#

Hey guys, I've a list A of n natural numbers, and a K number, natural also

I want to return B, where B has n * k numbers, and it has to have all elements of A, multiplied by j, 1 <= j <= k

So something like this:

A = [2, 4, 6, 8]
k = 3
B = [
    2, 4, 6, // For 2
    4, 8, 12, // For 4
    6, 12, 18, // For 6
    8, 16, 24 // For 8
]
#

and B needs to be in order

#

I need to give a solution in O(nk log n), what I thought was, first creating a B' like this:

A = [2, 4, 6, 8]
k = 3
B = [
    [2, 4, 6], // For 2
    [4, 8, 12], // For 4
    [6, 12, 18], // For 6
    [8, 16, 24] // For 8
]

I know I've n lists of k elements in B, where each list is in order. Getting here costs n * k

#

I thought I could take advantage of knowing all these lists are in order, to do a Merge Sort, but I'm not sure if I'm in the complexity range

#

Btw, this isnt a python problem, it's more a theoretical problem, from a uni excercise.

hushed nova
#

If no constraints on spce i think you can use min heap

thorn oriole
#

what is spce

#

I can use min heap, yup

hushed nova
#

You take extra o(n) spce for heap

#

And to get B
while min_heap: i = heapq.heappop(min_heap) B.append(i)

#

Or rather you can use binary search on the go?

thorn oriole
#

hmm BST.inorder is O(1) and inserting in the binary tree is log n, right?

#

so I get nk log n?

#

oh that makes sense

hushed nova
#

nk log(nk)

thorn oriole
#

yeah right

#

hmmmm

#

so I cannot use that method

#

I think merge sort gives nk log n

hushed nova
#

Merge sort is nlogn

#

So it will be nk + nklog(n k)

#

It still be ny log(nk)

#

Cause total numbers will be n * k, i dont think you can escape that

haughty mountain
#

if k ≤ n then log(n k) = O(log n)

#

there are also approaches that are O(max(n k, max_value)) but that use O(max_value) memory

thorn oriole
#

RIP

#

my exam is this friday, and I'm cooked 😄

#

I also need to study for my calc exam

haughty mountain
#

isn't O(n k log n) easy with a min-heap?

#

you only ever need to keep n values in the heap

#

the smallest value from each group

thorn oriole
#

yeah, you insert elements n*k times

#

but the n inside the log, hmmmm idk

haughty mountain
haughty mountain
thorn oriole
#

I need to have n* k values

#

I have to return an array B with n * k values

haughty mountain
#

not in the heap at any one time

#

you know that the minimum is one of the values among the smallest values in each group

#

so you can make use of things being sorted

thorn oriole
#

I dont understand

#

Like, what you are trying to say sad

#

I need to return B, which has to have n * k elements

#

if I use a heap to order, then I need a heap of n * k elements

haughty mountain
#

if you have n lists of length k that you know are sorted, how many elements could possibly be the smallest?

thorn oriole
#

I've n lists of lenght k that are sorted, but I might have repeated lists for example?

#

also, A isnt in order

#

and I dont need to return the smallest number, I need to return the FULL list, in order

haughty mountain
half owl
#

like they shouldve given simple code, simple execution and simple examples

thorn oriole
#

but I dont have to return the smallest number

haughty mountain
# thorn oriole n

cool, now remove that element and replace it with the next one in the same list

#

how many elements can now be the 2nd smallest?

#

it's again n

thorn oriole
#

n-1

haughty mountain
#

keep doing this

#

no

#

it's still n

thorn oriole
#

yeah n

#

mb

haughty mountain
#

the heap has size ≤n at all times

#

i.e. at most n elements could be the minimum at any point, those are the ones you need to consider when finding the minimum

thorn oriole
#

Sorry I just dont get how you can return a list of lenght k * n without adding k * n elements to the heap. I'll continue with the next excercise.

#

Thanks btw

lean walrus
#

you can put k*n references to the same object into a list

thorn oriole
#

no worries, dont want to lose more of you time

#

thanks again

haughty mountain
#

but not at the same time

#

@thorn oriole sketch of how it would work

n=2, k=3

a = [4, 8, 12]
b = [3, 6, 9]

result = []
heap = [3, 4]
a = [4, 8, 12]
b = [3, 6, 9]

result = [3]
heap = [4, 6]
a = [4, 8, 12]
b = [6, 9]

result = [3, 4]
heap = [6, 8]
a = [8, 12]
b = [6, 9]

result = [3, 4, 6]
heap = [8, 9]
a = [8, 12]
b = [9]

...
serene galleon
#

How to do method overloading ?

stiff quartz
#

Did they make two entries because pop returns the element and delete calls the garbage collector?

quasi oracle
#

Oh pop intermediate

#

Probably list.pop(i) vs del list[i]

#

No functional difference

regal spoke
#

Some of these tables look wrong in general

image.png
#

if n = 2 then you should get same time complexity on both rows

#

But you dont

regal spoke
#

I would assume that just like append, pop also has to deal with amortization

#

Unless you never want the memory usage of a list to shrink

haughty mountain
#

it should be min in both I think

narrow mica
regal spoke
#

So it hould say something like O((n - 1) * l^2)

cold lodge
#

Hello chat

#

Im just about to start training my transformer based model, any useful tips before i run this nonstop for a while?

haughty mountain
#

I think average case is (n-1) O(min(lens))

#

also "average"

#

maybe average on random input

regal spoke
haughty mountain
#

ah right, python can't really optimize for this

#

I guess it's worse yeah

regal spoke
#

Someone should probably just remove that multiple intersection row from the table

haughty mountain
#

yeah

regal spoke
#

It tricks you into thinking that python has some special optimization for multiple intersections

#

While in fact it just runs pairwise intersection over and over

stiff quartz
#

Like you can free the memory without having to copy your array somewhere else?

#

But when you append, if the memory you’re « requesting » when it grows is not free, then you have to copy everything

haughty mountain
#

I think you can't really free part of some allocated memory

stiff quartz
stiff quartz
haughty mountain
#

official wiki of sorts

#

but I'm not surprised there are errors

#

I would assume they would do a realloc to shrink memory

#

which more than likely just keeps the same pointer

narrow mica
cold lodge
#

sry

north cosmos
#

For this question:

    You've decided to take the ultimate course: MATH131. However, that course has some requirements - you have to take MATH120, MATH121, and MATH122 first! But each of those have their own requirements:

        MATH131 requires MATH120, MATH121, MATH122
        MATH122 requires MATH111, MATH112
        MATH121 requires MATH111
        MATH120 requires MATH110, MATH111
        MATH112 requires MATH110
        MATH111 requires MATH110
        MATH110 has no requirements

    What order should you take these courses in?

How would you guys go about it?
This was my code, and let me know where I can improve it.
https://mystb.in/14eabcb146f111696d

Output = ['MATH110', 'MATH112', 'MATH111', 'MATH122', 'MATH121', 'MATH120', 'MATH131']

#The order matters
vocal gorge
halcyon plankBOT
#
graphlib.TopologicalSorter 

class graphlib.TopologicalSorter(graph=None)```
Provides functionality to topologically sort a graph of [hashable](https://docs.python.org/3/glossary.html#term-hashable) nodes.

A topological order is a linear ordering of the vertices in a graph such that for every directed edge u \-\> v from vertex u to vertex v, vertex u comes before vertex v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this example, a topological ordering is just a valid sequence for the tasks. A complete topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph.
north cosmos
#

ooh

#

didnot know about it lol

narrow mica
# halcyon plank

and again for some reason this stdlib exists solely for this class

#

and honestly a topo sort isn't hard to implement anyways

summer fossil
# 
class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
            freqs = [0] * 3
            n = len(s)
            
            for c in s:
                freqs[ord(c) - ord('a')] += 1
            
            i = 0
            j = 0
            if freqs[0] < k or freqs[1] < k or freqs[2] < k:
                return -1
            
            for j in range(n):
                freqs[ord(s[j]) - ord('a')] -= 1
                
                if freqs[0] < k or freqs[1] < k or freqs[2] < k:
                    freqs[ord(s[i]) - ord('a')] += 1
                    i += 1

            return n - (j - i + 1)```
# 
Input: s = "aabaaaacaabc", k = 2
Output: 8```
#

can anyone explain how it works?

#

is j==n? use for loop here for j in range(n): working of j here?

regal spoke
#

range(n) is 0,1,..., n-1

regal spoke
summer fossil
#

oh yeah so j has no role? Return i

#

so how i works here? How i is the soln like valid

odd skiff
#

How to send formatted code in this chat?

#

Could someone explain me the code implemented here..
Background : Its a code for finding the longest length of a sub-array in which its values sum to value k below is the code

def longest_subarray_with_sum_k(array, array_length, target_sum):
    # Dictionary to store prefix sums and their first occurrences
    prefix_sum_indices = {}

    # Initialize variables
    prefix_sum = 0
    longest_subarray_length = 0

    for index in range(array_length):
        # Update the prefix sum
        prefix_sum += array[index]

        # If the prefix sum itself equals the target, update the length
        if prefix_sum == target_sum:
            longest_subarray_length = max(longest_subarray_length, index + 1)

        # Check if the difference (prefix_sum - target_sum) exists in the hashmap
        difference = prefix_sum - target_sum
        if difference in prefix_sum_indices:
            # Calculate the subarray length
            subarray_length = index - prefix_sum_indices[difference]
            longest_subarray_length = max(longest_subarray_length, subarray_length)

        # Store the first occurrence of the prefix sum in the hashmap
        if prefix_sum not in prefix_sum_indices:
            prefix_sum_indices[prefix_sum] = index

    return longest_subarray_length


# Example usage
n = 7
k = 3
a = [1, 2, 3, 1, 1, 1, 1]
result = longest_subarray_with_sum_k(a, n, k)
print("Length of the longest subarray with sum =", k, "is", result)```
summer fossil
#

using 3 back tick ```

#

backtick

odd skiff
#

Here are my question... I am getting fuzzy in these two sections specially...


 # Check if the difference (prefix_sum - target_sum) exists in the hashmap
        difference = prefix_sum - target_sum
        if difference in prefix_sum_indices:
            # Calculate the subarray length
            subarray_length = index - prefix_sum_indices[difference]
            longest_subarray_length = max(longest_subarray_length, subarray_length)

        # Store the first occurrence of the prefix sum in the hashmap
        if prefix_sum not in prefix_sum_indices:
            prefix_sum_indices[prefix_sum] = index
summer fossil
odd skiff
#

I dont know Hindi..

#

Do you anyone around here who knows Tamil?

#

Its another south indian language

summer fossil
#

i dont know but wait so many xpert peeps here

regal spoke
#

Technically it is return i - int(n<=0)

upper crypt
#

Hi ! I have a question regarding the del method.
I've stumble onto a bug (sys.meta_path is None, Python is likely shutting down) and a bit of reading convinced me that I had the wrong understanding of how it works. It appears not to act as a destructor, or mainly that it may be called after the environment starts to tear down and that's what causes my issue, and it's globally a bad idea to use them.
However, I do need some of my objects to act when destroyed, how can I do that please ? 😄

regal spoke
upper crypt
#

Okay, thanks 😄

summer fossil
near grove
#

I have a numpy array like this: np.array(["1546", "234", "123414", "342", "9120831"]), and I want a new array instead with each strings lenght as a value. To this instead: np.array([4, 3, 6, 3, 7])

#

np.array(["1546", "234", "123414", "342", "9120831"]) # To this -> np.array([4, 3, 6, 3, 7]) Which is a new array of each strings length instead.

jolly mortar
#

apparently np.char.str_len(arr) exists

narrow mica
#

!rule 9

halcyon plankBOT
#
Rules

9. Do not offer or ask for paid work of any kind.

lean walrus
#

!d numpy.char.str_len

halcyon plankBOT
#
numpy.char.str\_len 

char.str_len(x, /, out=None, *, where=True, casting='same_kind', order='K', dtype=None, subok=True[, signature]) = <ufunc 'str_len'>```
Returns the length of each element. For byte strings, this is the number of bytes, while, for Unicode strings, it is the number of Unicode code points.
brisk stream
#

guys one question

#

in bfs, you always have to have a initial node

#

and an reach node, or this last is not necessary

narrow mica
brisk stream
narrow mica
#

or initial nodes
depends on what you're doing

vale gulch
#

Chat

#

Does json files go up to infinite numbers?

orchid violet
wheat fulcrum
#

do you know how to fix

#

File "<console>", line 1
import os
^
SyntaxError: multiple statements found while compiling a single statement
File "<console>", line 1
import os
^
SyntaxError: multiple statements found while compiling a single statement

vale gulch
#

I can give it an infinite value?

orchid violet
narrow mica
#

but the python json does have some special functions to read them anyways

odd skiff
#

Looking for buddies for daily learning or connecting..

vale gulch
#

Ok

outer rain
#

is there a fast, branchless way of getting any 3d vector non-collinear to the given non-zero vector?

toxic hare
raven dagger
#

my parser broke

main berry
#
  1. Custom Sorting Algorithm
    ● Objective: Write a program to sort a list of integers using a custom sorting algorithm,
    such as bubble sort or selection sort.
    ● Requirements:
    ○ Accept a list of integers from the user and provide options to sort it in ascending
    or descending order.
    ○ Implement the sorting algorithm manually (no built-in sort() function).
    ○ Display the sorted list along with the number of comparisons or swaps made
    during the sorting process.
    ○ Bonus: Implement both bubble sort and selection sort, allowing the user to
    choose the algorithm they want to use.

● Skills Practiced: Loops, conditionals, algorithm design, and understanding of sorting
mechanics.

someone can help to create it? and can tell what this assignment exactly need?

#

what is bubble sort or selecion sort i mean?

toxic hare
#

bubble sort and selection sort are algorithms that achieve this

regal spoke
#

Maybe something like (a,b,c) -> (b,c,2*a)

outer rain
#

pretty sure it can't be continious in general because something-something hairy ball theorem

Hairy ball theorem

The hairy ball theorem of algebraic topology (sometimes called the hedgehog theorem in Europe) states that there is no nonvanishing continuous tangent vector field on even-dimensional n-spheres. For the ordinary sphere, or 2‑sphere, if f is a continuous function that assigns a vector in ℝ3 to every point p on a sphere such that f(p) is always ta...

jolly mortar
#

u = v/abs(v); out = (u == i^)*j^ + (u != i^)*i^?

outer rain
# jolly mortar `u = v/abs(v); out = (u == i^)*j^ + (u != i^)*i^`?

that works ig but you might as well have an if at that point. It's not pretty, but this is even worse, especially considering that by u == i^ here you actually mean something like abs(u.x) - 1 > -eps.

It would be nice if there was just a weird function which would do that.

jolly mortar
#

agreed

regal spoke
haughty mountain
#

actually, can't you just pick some perpendicular vector pithink

#

e.g. (y - z, z - x, x - y)

outer rain
#

In general, to find the perpendicular vector you take the cross product of your vector with any non-collinear vector and... well guess what

narrow mica
outer rain
#

well, ok, now it's curiosity more than anything

#

because as it has already been said, just take a random unit vector

jolly mortar
#

slightly funny that a matrix mult that does that exists in 2d and even 4d but not 3d

outer rain
#

yeah, hairy ball theorem again

#

unfortunate

outer rain
#

I think (1, y + floor(abs(x)), z) works for normalized vectors because when abs(x) != 1 it's (1, y, z) which is not collinear, and if abs(x) = 1 it's (1, y + 1, z) which is (1, 1, 0) and it's collinear to (+-1, 0, 0)

#

although (1, y + floor(abs(x + x)), z) should have better floating point robustness if my math in correct

half owl
#

why didnt they just add that legals is of max length 8? it's very misleading

image.png image.png
#

they shouldve added ? to the other areas

haughty mountain
#

it can be whatever length (≤ len(V))

pallid dock
#

Henlo guis

#

Can u guys tell me ur best way to use classes

#

Like pro guy

lean walrus
#

use when it makes sense

#

don't use when it doesn't

pallid dock
#

Ohk

#

How would I know that it can be with it

lean walrus
#

practice

half owl
#

how is this O(n) and not O(n^2)?

image.png image.png
#

inserting to an array should be O(1) since we keep track of the array's length (not the max array capacity)

#

so inserting to arr of size n should be n+1 operations to build and fill the new arr

#

oh i understand

haughty mountain
half owl
haughty mountain
#

where did anything say legals is a stack?

#

it's a separate slide with a completely separate example

half owl
haughty mountain
#

it's not?

half owl
#

oh nvm

#

i didnt copy the correct slide

#

but yk

#

it's still misleading

haughty mountain
#

what is misleading?

half owl
haughty mountain
half owl
# haughty mountain what is misleading?

calling an array an array, drawing only 2 out of 8 elements in memory of it (other arrays were drawn with the entirety of their elements in the example), and then the next slide saying that small array is a stack

#

of size 8

half owl
#

or lecture slides

haughty mountain
#

or you haven't shared whatever slide says that

half owl
haughty mountain
half owl
#

i think there's a mistake here, because the $a_{i+1}$ Node might not exist (=be equal to null), so in the 2nd line: A.next<-A.next.next would be like doing A.next<-null.next, which is undefined, since null doesnt have any fields like next stored in memory

half owl
haughty mountain
#

it doesn't need to be

half owl
#

theyre allocated and vacant "?"

half owl
#

also why it is an array thats also a stack of the same size as the others

image.png
haughty mountain
#

oh, they do use a stack, but I don't get your complaint

#

the stack ADT is not a fixed size thing

half owl
half owl
#

but thats okay

half owl
half owl
haughty mountain
#

it's assuming you're not at the end, yes

#

depending on how the function is used it might be a fine function

half owl
#

what am i not understanding? why is amort(Pop) both 1 time units, and 0 time units (not possible)

image.png
regal spoke
#

since before any pop comes a push

#

So "amortized" you could say pop has 0 cost by doubling the cost of push

brazen magnet
# 
return sum(1 for passenger in details if int(passenger[11:13]) > 60)

i feel like this probably isn't a great way of doing this

#

is the sum(1) thing idiomatic for python?

regal spoke
regal spoke
#

If you want your code to be easier to understand, a good alternative might be to create a list and do len on it.

fiery cosmos
#

what are cut vertices or articulation points?

fiery cosmos
#

How can I find them?

half owl
#

@regal spoke have u uses clrs book and how good it is? I wonder if their explanations would be better than our lecture slides

regal spoke
#

But they are not incorrect

regal spoke
#

Think of it more like this: for the time complexity analysis, it doesn't matter if you assume pop takes time or not

#

Since the time of doing pops will always be dominated by the time it takes to do the pushes

regal spoke
half owl
mortal dagger
#

Does learning DSA in python is beneficial or not

stiff quartz
#

Worth noting I also get TLE in C++ so it's probably that we can't use Edmonds-Karp for that problem?

stiff quartz
#

Ah so, using a stack instead of a queue (so not using edmonds-karp) works

#

even though it's supposedly O(Ef) which is a lot worse than O(E²V)

stiff quartz
regal spoke
#

The trick is to keep track of a forward capacity and a backwards capacity for each edge

#

When you push x flow through an edge, you decrease the forward capacity by x and increase the backwards capacity by x

#

About the time complexity. Flow algorithms almost always run magnitudes faster than what you'd expect from looking at their time complexity

#

However, on websites that allow users to add hacks, probably someone has submitted a worst case for all of the popular flow algorithms

#

Your BFS is kind of bugged. You will try to go back to the source node since its parent is -1

stiff quartz
stiff quartz
#

If I understand correctly it is O(E*max_flow)

#

But I really don’t like the example of that worst case scenario / hack on Wikipedia

#

I don’t know if I’m clear

regal spoke
#

Codeforces comments are usually the best way to find stuff like this

stiff quartz
stiff quartz
#

Just to make sure

#

On this page, the integer flow example

#

https://en.m.wikipedia.org/wiki/Ford–Fulkerson_algorithm

Ford–Fulkerson algorithm

The Ford–Fulkerson method or Ford–Fulkerson algorithm (FFA) is a greedy algorithm that computes the maximum flow in a flow network. It is sometimes called a "method" instead of an "algorithm" as the approach to finding augmenting paths in a residual graph is not fully specified or it is specified in several implementations with different running...

#

Says it would take 2000 steps

#

To finish with dfs

#

Am I correct in saying that would never happen if you were to code it?

#

Or am I just misunderstanding something?

regal spoke
#

I think it could happen

#

Depends on the order of the adjecency list

stiff quartz
#

They claim you do ABCD (which is fair)

#

Then augmenting path ACBD

#

but like you’d go for ABD

#

Because no way the iterable neighbours(A) changed its order

regal spoke
#

A's adjecency list is [B,C]

stiff quartz
#

Why is D there

#

Capacity 0?

regal spoke
#

B's adjecency list is [C,D,A]

#

C's adjecency list is [B,D,A]

regal spoke
regal spoke
#

What edges the graph contains dont change depending on the capacities

#

At this point ^ A,C,B,D is an augmenting path

stiff quartz
#

Yes that I understand

#

However I don’t understand why in the first iteration the first path we found with our dfs was ABCD

#

so clearly in the second iteration the first augmenting path should be ABD?

#

But I’m not sure I understand your adjacency lists

stiff quartz
regal spoke
#

oh ops

stiff quartz
#

Since initially there is no way to push flow from A to D « directly » nor is there a way to push flow from D to A

regal spoke
#

A and D arent connected

stiff quartz
#

Ah okok

#

Yes

#

Starting from there, A’s adjacency list is [B,C]

regal spoke
stiff quartz
#

If we use dfs the first augmenting path we find will be A C B D and the second one will be A C D

regal spoke
#

Maybe this isn't a good example

stiff quartz
#

like there is no way

#

We alternate

#

A B and then A C

#

I know Wikipedia is usually not the greatest place for those examples but they seemed very convinced of their counter example

regal spoke
#

I think that "worst case" on wiki doesn't work for a fixed adjecency list

stiff quartz
#

Is it worst case if we take a random neighbor

#

And we are really really really unlucky

#

Which I guess from a theoretical point of view is enough to say that’s the worst case

regal spoke
#

You know, just do dinics if you want to avoid this kind of worst case

stiff quartz
#

But like if I were tasked to hack someone’s solution with a fixed adjacency list I really don’t see how I can attain this O(E*max_flow)

stiff quartz
#

It’s probably not useful to try and build that counter example but still it bothers me

regal spoke
#

I think the point of the wiki article is just that if a bad actor could chose what dfs you do

#

Then the algorithm could become crazily slow

stiff quartz
#

And so my question is can your algo become crazily slow if the bad actor can just craft a shitty output

#

Basically like a Codeforces hack

#

But it might not be that easy to build

regal spoke
#

In the case of a BFS, the answer is no

stiff quartz
#

Oh yes I was talking about a DFS

regal spoke
#

In the case of a DFS, I'm not sure

stiff quartz
#

I read the proof that BFS is VE^2 (Edmonds Karp thing)

regal spoke
#

There probably is some killer out there

stiff quartz
#

And then I saw dinic but didn’t look at it yet

regal spoke
#

Dinics is basically same as edmonds karp

#

But it is able to reuse the BFS to find multiple augmenting paths

stiff quartz
#

Yeah but I kinda wanted to solidify those two first

#

The dfs and the bfs ones

regal spoke
#

The dfs in dinics is essentially a bfs

#

It is a very unusual kind of dfs

stiff quartz
#

Anecdotally, on the cses I think they expected dinics because I copy pasted a template to try it and it passed

#

And the Edmonds Karp one didn’t pass (fair enough seeing the constraints)

#

But the dfs did which seems crazy to me (and currently the fastest Python solution uses it)

regal spoke
#

What about this example

image.png
stiff quartz
#

Ah

regal spoke
#

The idea is that the dfs is tricked into going into the loop before trying C

stiff quartz
#

Yes

#

That would definitely break it

#

I guess you would have to call B C

#

Coz the dfs goes to C first

stiff quartz
#

It would break so many solutions

stiff quartz
#

Since A was marked as visited?

regal spoke
stiff quartz
#

Well in my case where I had parent[source] set to -1 by accident

#

That would work

stiff quartz
regal spoke
#

BFS != DFS

stiff quartz
#

Yes I know I know but

#

In my DFS

#

I could very well say

#

Im adding to the stack only

#

If parent[neighbour] != -1

#

To avoid that loop

#

This blog mentions a hack to the normal dfs ford fulkerson but I’m a bit confused

stiff quartz
#

that failed miserably

regal spoke
#

Just do dinica

stiff quartz
#

I'm not trying to pass the cses problem

regal spoke
#

Its easy and runs reasonably fast

stiff quartz
#

I'm trying to hack my solution that passed despite it being O(E*f)

regal spoke
#

Btw all of these flow algorithms are technically O(E * f)

stiff quartz
#

I'm pretty sure Edmonds-Karp can actually be bound by E²V

regal spoke
#

You can prove that the augmenting paths become longer and longer

#

That's the case with both dinics and Edmonds-karp

#

But the E*f bound still holds

stiff quartz
#

I think their proof disregards that bound I might have misunderstood though

stiff quartz
#

and then they prove this claim (and I went through it and was convinced)

regal spoke
stiff quartz
#

This O(VE²) is just a better bound if f is big is what I meant.
And in the case of Edmonds-Karp they prove there are at most E*V/2 augmentations.

regal spoke
#

Since an augmentation costs O(E) time, and there can be at most f augmentations

#

Edmonds-karp use of BFS also makes it so there is an order to which it finds its augmenting paths

#

This lets you show another bound on the number of augmentations that it will do

stiff quartz
regal spoke
stiff quartz
#

Well yes f being the max flow if f is big I meant the capacities will necessarily be big (since V and E are quite small in the problem)

regal spoke
#

A common case is all capacities = 1

#

Then you can derive another bound

stiff quartz
#

Yes but they derive the other bound without assuming the capacities are all 1

#

if I'm not mistaken

regal spoke
#

yes

stiff quartz
#

So there has to be an example where (for small V and E, and big capacities) BFS works and DFS times out crazy

#

and this would definitely hack my cses solution since I use the DFS which is not bound by VE² but only bound by E*f and the capacities can go up to 10^9

#

I really expected creating billions of random small graphs with big capacities would allow me to find that counter example but no 😦

narrow mica
stiff quartz
#

yes we are

#

this ff is dfs and passes (0.05s on test 20)

narrow mica
#

blank

regal spoke
#

Looks blank to me too

stiff quartz
#

ah hum i don't know how to share cses results

#

sorry, found the button

regal spoke
stiff quartz
narrow mica
regal spoke
#

You know, max flow can be solved in O(n log ^ 10 n) (not sure of the exact number of logs, its something like 10 logs).
I think of it like max flow algorithms are usually really fast, but there are tricky edge cases where they run slow.
The people that did the O(n log ^ 10 n) algorithm was able to rule out all of those edge cases.

stiff quartz
#

Those are the crazy edge cases I was looking for 😭

#

There has to be someone that hacked ff before

#

I'll probably just ask if they remember on a blog on codeforces

#

I initially thought it would be easy to come up with

#

how mistaken was i

stiff quartz
regal spoke
#

Actually I have an idea

#

Maybe you can show that the DFS version isn't really O(E * f)

#

My idea is to duplicate the edges enough times

#

To where a BFS would take the same path as a DFS

#

We know that the BFS doesn't take O(E * f)

#

So maybe the DFS also cannot take O(E * f)

#

There could still be some case where the DFS is horribly slow, but at least it will be polynomial in the number of edges

stiff quartz
# regal spoke So maybe the DFS also cannot take O(E * f)

I feel like if you managed to prove that you could almost publish it, all sources I've seen so far all say FF with DFS is O(Ef) and that's why we like BFS in max flow because we have a bound that doesn't depend on the capacities (or at least that's how it was presented to me when I was in uni)

regal spoke
#

I asked some other people about this on another server

#

None of them have a clue about how to construct an E * f worst case in the DFS one

regal spoke
#

@stiff quartz Update.

image.png
#

This is a recursive construction that adds two new nodes every time

#

It takes O(2^n) time