you dont have that
#algos-and-data-structs
main bison
while i<n:
q.append(arr[i])
if len(q)%2!=0:
s+=sum(q)
if i==n-1:
i=j
j+=1
q = []
i+=1
here is your while loop
does this part scale with the size of array?
summer fossil
Nope it reset the array?
main bison
ccorrect, it does not. so lets not focus on that part
q.append(arr[i])
if len(q)%2!=0:
s+=sum(q)
then there are three lines of ccode left
does q.append(arr[i]) scale with the size of the array?
summer fossil
yeah!
main bison
is the work done important?
it might be right
so for now we can say it scales by adding another n
2n in total now
does s+=sum(q) scale?
summer fossil
nope!
main bison
q is the size of your array right?
main bison
so every iteration of n you have a for loop that takes alle the numbers in the array and sums it
summer fossil
yeah!
main bison
so when the array doubles, the amount of work that sum does also doubles
main bison
we only ccare about worst case
so the producct of the extra work inccreases by n
2n*n
summer fossil
Yeah!
main bison
and we dont ccare about the constants in big 0
all lines are acccounted for
time complexity is n**2 or n squared
summer fossil
that's why (n^2) complexity thanks for explanation!
main bison
my pleasure
outer rain
i got a question
Don't ask to ask
haughty mountain
time complexity is `n**2` or n squared
isn't is n³ for that code?
the loop itself loops over all i <= j < n
then there is also the sum
I think this would be equivalent code
s = 0
for j in range(n):
q = []
for i in range(j, n):
q.append(arr[i])
if len(q)%2 != 0:
s += sum(q)
where the n³-ness should be clear
haughty mountain
good case of "each loop doesn't just add a factor n‘
vocal gorge
yeah, I agree with O(n³) - it's O(n²) iterations of the loop, with every second iteration doing a sum that's O(n) on average.
mild cosmos
regal spoke
#algos-and-data-structs is probably not the right question to ask this in
worthy wadi
Damn meant async
summer fossil
Hello Can anyone help me
https://leetcode.com/problems/candy/
for test case [1,3,2,2,1]
regal spoke
Hello Can anyone help me
https://leetcode.com/problems/candy/
for test case [1,...
The answer for rating = [1,3,2,2,1] is 1+2+1+2+1 = 7 candies in total
cunning bison
How can I count occurrences of X in a linked list without accumulators or tail recursion?
agile sundial
a while loop
cunning bison
a while loop
That would use an accumulator tho
Something like
while l is not None:
if l == X:
count += 1
l = l.next()
how are you going to count without counting?
cunning bison
I have no clue
Heres the question
# Returns how many times x is found inside List135 xs (uses == to test equality)
# Function does NOT use tail-recursion or accumulators.
# [], 1 --> 0; [1], 1 --> 1; [1,2], 1 --> 1; [1,2,1], 1 --> 2; etc.
def count(xs, x):
return 0
List135 is a linked list
Where instead of being called next, the next element is called "rest" :) Now Im just complaining but what
I think it is actually a functional programming like were supposed to dump it into an array and use filter
Like
def count(xs, x):
l = []
while xs.first() is not None: # .first() is .get()
l.append(xs.first())
xs = xs.rest()
return len(list(filter(lambda y: y == x, l))))
Because that technically doesnt use tail recursion or an accumulator :) ah the joys
Lol now Im complaining more. This teacher gives us instructions on how to submit our assignment. You would think clicking on the link would allow you to just edit the url in the omni box... no my teacher created a fake link and instead redirected to a site that says "You must type in the URL yourself"
He does have a public facing anonymous file submission where you could in theory spam his inbox tho...
Okay last complaint -- we have this problem:
Here is his hint: use reduce, and string concatenation + in a lambda
He also for some reason heavily favors using reduce() to sum a list instead of the sum() function
He is a strange fellow indeed
haughty mountain
seems he really wants to teach functional programming using python 
agile sundial
they wouldn't let him use lisp
cunning bison
seems he really wants to teach functional programming using python <:pithink:652...
He also spent the first two weeks teaching memory management, having us manipulate lists in place
But why do all that. Then were gonna get CS grads who get glue_reverse and instead of "".join(string[::-1]) which IMO is very clear what it does theyre gonna have some lambda reduce nonsense that is completely unreadable
haughty mountain
He also spent the first two weeks teaching memory management, having us manipula...
which would be better taught in a lower level language like C
cunning bison
hence why reduce was removed from python std lib
cunning bison
which would be better taught in a lower level language like C
Yeah exactly. Im not sure how anyone else is passing this class
haughty mountain
(why that was moved and not filter is kinda beyond me)
cunning bison
According to guido it is no longer in the "standard library". Also Im not sure why because the most common use of reduce is sum() so it was moved but the most common use of filter is either counting which already exists, or any and all which were added in py3
Is map(F, list) actually slower than (F(x) for x in list)
agile sundial
the most common use of reduce is not sum 🤔
the most common use of filter is not counting
cunning bison
Guido disagrees
(related to filter) this has the huge advantage that the most common usages involve predicates that are comparisons, e.g. x==42, and defining a lambda for that just requires much more effort for the reader (plus the lambda is slower than the list comprehension)
haughty mountain
Which does remind me im excited for .sumprod() in [3.12](<https://docs.python.or...
and of course we can't call it what it is, a dot product 😔
timid spear
Hello I'm new here
modern gulch
and of course we can't call it what it is, a dot product 😔
Us data engineers are simple people.
haughty mountain
wait, is this meant to be a slow impl that's more accurate?
the github issue suggests as much, the python docs doesn't mention it
modern gulch
Huh, maybe a discussion in Python.org?
haughty mountain
cpython has a tendency to add some useful functionality with kinda questionable names
regal spoke
and of course we can't call it what it is, a dot product 😔
Clearly it should have been called .product
haughty mountain
the github issue suggests as much, the python docs doesn't mention it <:pithink:...
oh nvm
For float and mixed int/float inputs, the intermediate products and sums are computed with extended precision.
hopefully it won't be too much of a slowdown
like the pretty terrible slowdown of statistics.mean and the like
!d statistics.mean
halcyon plankBOT
haughty mountain
iirc it can be like an order of magnitude slower
regal spoke
hopefully it won't be too much of a slowdown
The main feature is that it uses FMA to calculate the multiplication with higher precision
static DoubleLength
dl_mul(double x, double y)
{
/* Algorithm 3.5. Error-free transformation of a product */
double z = x * y;
double zz = fma(x, y, -z);
return (DoubleLength) {z, zz};
}
other than also using quad precision
regal spoke
#ifdef NO_C99_FMA
static DoubleLength
dl_split(double x) {
// Dekker (5.5) and (5.6).
double t = x * 134217729.0; // Veltkamp constant = 2.0 ** 27 + 1
double hi = t - (t - x);
double lo = x - hi;
return (DoubleLength) {hi, lo};
}
static DoubleLength
dl_mul(double x, double y)
{
// Dekker (5.12) and mul12()
DoubleLength xx = dl_split(x);
DoubleLength yy = dl_split(y);
double p = xx.hi * yy.hi;
double q = xx.hi * yy.lo + xx.lo * yy.hi;
double z = p + q;
double zz = p - z + q + xx.lo * yy.lo;
return (DoubleLength) {z, zz};
}
#else
static DoubleLength
dl_mul(double x, double y)
{
/* Algorithm 3.5. Error-free transformation of a product */
double z = x * y;
double zz = fma(x, y, -z);
return (DoubleLength) {z, zz};
}
#endif
(or something mimicking it at least)
regal spoke
Tbh I dont really get why Python needs stuff like this
One thing in particular that I dislike about it is that the result can be dependent on which system you run it on
opal oriole
One thing in particular that I dislike about it is that the result can be depend...
That is the case for all floating point arithmetic.
regal spoke
That is the case for all floating point arithmetic.
Not for the basic operations
opal oriole
Not for the basic operations
It is. That's why deterministic lockstep is such a pain in game dev for multiplayer.
Some x86 processor won't give the same results as on ARM.
regal spoke
For basic stuff like addition/ subtraction/ multiplication?
opal oriole
Yeah.
haughty mountain
as in one is not standard compliant?
opal oriole
For x86, you can force it to all be the same with a processor flag, but it comes with a performance penalty.
haughty mountain
or odd extended precision stuff?
opal oriole
Used by physics engines for multiplayer though.
haughty mountain
err, excess precision
opal oriole
They are IEEE754 standard compliant. But IEEE754 is designed around precision and speed, not determinism.
regal spoke
They are IEEE754 standard compliant. But IEEE754 is designed around precision an...
What part of IEEE754 says that addition / subtraction / multiplcation is not deterministic?
opal oriole
What part of IEEE754 says that addition / subtraction / multiplcation is not det...
It's deterministic on the same machine, but not across machines (different systems).
Deterministic is not the best word for it.
They are just different.
haughty mountain
huh? aren't the operations defined to produce the closest representable value?
(ignoring fun excess precision stuff)
opal oriole
https://rapier.rs/ Physics engines will advertise the ability to enforce the compliance more strictly for stuff like this.
Optionally make Rapier cross-platform deterministic on all IEEE 754-2008 compliant 32- and 64-bits platforms.
"Determinism" is not exactly the right term here, but it's what everyone uses. It's just same across devices.
The details I don't exactly remember.
Some games even use fixed point because of this. Typically RTS games, for lockstep.
(e.g. Starcraft)
regal spoke
Are you talking about the stuff in https://en.wikipedia.org/wiki/C99#IEEE_754_floating-point_support ?
opal oriole
Are you talking about the stuff in https://en.wikipedia.org/wiki/C99#IEEE_754_fl...
It's not really a C problem, but C does add to the list of problems when trying to get cross-platform determinism.
EVAL_METHOD is one problem.
regal spoke
EVAL_METHOD is one problem.
Yes
But it should be 0 on all modern systems
I've had a lot of fun with EVAL_METHOD == 2 in the past. With it you can't assume anything about floating point calculations. It is horrible
For example, try comming up with an input that "hacks" this
#include <iostream>
#include <cmath>
using namespace std;
bool f() {
double x;
cin >> x;
double y = x + 1.0;
if (y >= 1.0)
return false;
pow(y, 2);
if (y < 1.0)
return false;
return y == 1.0;
}
int main() {
if (f())
cout << "HACKED\n";
else
cout << "Not hacked\n";
}
(it is possible, but only if EVAL_METHOD == 2)
One of the reasons that I like working with floating point numbers in Python is that they behave like you expect them to. You wouldnt be able to make a Python script with weird behaviour like this ^
opal oriole
There are some per-thread flags that seem to be different on x86/ARM.
And Visual C++ as usual does all the weird stuff.
I'm not exactly sure what the default settings for each is, but they are different and result in devs having to control these flags to get deterministic lockstep across different devices.
-ffp-model precise on clang seems to be the way to go for it, and /fp:precise on MSVC, plus -ffp-contract=off on clang.
Rounding, precision, exceptions, denormals flags.
Jolt physics engine wrote that it gives them about an 8% performance penalty, so not too bad.
And they test on x86/ARM.
Other than fixing the basic operations with those non-default flags, the compiler version and other things matter too. E.g. sin/cos/tan implementations.
So there is precision, rounding, exceptions, denormals, EVAL_METHOD, contraction, standard library implementations / versions / cross compiler differences of functions.
The default on most compilers is not the most strict.
I guess if you want to be really safe but slow in Python you could use the decimal package.
regal spoke
So there is precision, rounding, exceptions, denormals, EVAL_METHOD, contraction...
Btw code like this will totally break if EVAL_METHOD==2
#ifdef NO_C99_FMA
static DoubleLength
dl_split(double x) {
// Dekker (5.5) and (5.6).
double t = x * 134217729.0; // Veltkamp constant = 2.0 ** 27 + 1
double hi = t - (t - x);
double lo = x - hi;
return (DoubleLength) {hi, lo};
}
This code relies on double's working like one would expect them to
opal oriole
Btw code like this will totally break if `EVAL_METHOD==2`
```cpp
#ifdef NO_C99_F...
Yeah, this kind of code is really annoying if you need that "determinism."
A lot of stuff is written for speed though.
regal spoke
So are you claiming that this code is buggy?
opal oriole
So are you claiming that this code is buggy?
Not buggy, it's settings outside of its control / it has certain assumptions.
And those assumptions are fine, just not great for the goal of cross platform determinism for something like a networked game or reproducible code if you want the exact same results.
It can still be controlled by the user, so they can force it to behave the same.
But they have to be aware of it, and look up all the pitfalls.
Some are compile time settings, other runtime (per thread).
It usually does not come up, since most are not making deterministic lockstep games, nor trying to get exact reproducible results.
Or in the latter case, they make sure they have the same hardware and compiler / version, etc.
Rather than mess with flags.
regal spoke
But they have to be aware of it, and look up all the pitfalls.
This code would just straight up break if any of these pitfalls are actually a thing
opal oriole
This code would just straight up break if any of these pitfalls are actually a t...
Yeah, it would. It has several assumptions.
At least it checks FMA.
Side stepping these issues by using software floating or fixed point is what a lot of games do.
Interestingly, old arcade games used fixed point (no floating point hardware), and so they just work, which is why old fighting games just work for deterministic lockstep.
This means one can retroactively make old arcade games networked multiplayer (if they had multiple players). Without modifying their source code.
cobalt mirage
Hi
signal tinsel
hello?
fiery cosmos
guys i already ask this question in general but i didnt get a good answer
in leetcode is better runtime or memory
ill be following a neetcode roadmap
and the first problem is
duplicates elements
my code is
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
return len(set(nums)) != len(nums)
```
and his code is
```py
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
hashset = set()
for n in nums:
if n in hashset:
return True
hashset.add(n)
return False```
my code has good runtime but bad memory for some reason and his code is the otherwise
can you give me some tips?
what's more important, which code is better, what should i base it on
ocean glen
The question is along the these lines
You are bank. You are given notes, an array of size 8, where each entry denotes number of currency notes of denomination 5000, 1000, 500, 100, 50, 10, 5, 1, repectively.
You are also given withdraw_requests of size N. where withdraw_request[i] the amount i-th person requesting to withdraw from the bank.
- Return the maximum number of
withdraw_requestsyou can satisfy - Construct that optimal solution in an array of size N * 8
notes[i] <= 1500
N == 1000
The question is more vague... i think they are expecting an approximate algorithm not optimal
optimal seems exponential... since we need to construct the solution
does this problem sounds like something that reducilable to some well-known approximation algorithm problem?
haughty mountain
guys i already ask this question in general but i didnt get a good answer
in le...
this is a classic case of python being python
the former is faster because it's not relying on code written in python
the latter is similar to how you would build a set, but since it's written in python it's going to be slower
in a lower level lang things would look quite different
fiery cosmos
this is a classic case of python being python
would you do the same answer than mine?
haughty mountain
in python, probably
regal spoke
would you do the same answer than mine?
I'm a strong believer that simpler is better. I really prefer the return len(set(nums)) != len(nums) solution
haughty mountain
I wouldn't write that solution in say C++
in C++ your code will be comparatively fast as whatever is in the stdlib, do you have more freedoms there
valid widget
Hello, could someone please help in drawing out this binary tree and also please give some general advise on how to draw binary trees from this list format. I'm a high school student that just started out leetcode so im still tryna learn the ropes of basic DSA. Thanks!
narrow mica
From top(root) to bottom, there are 1, 2, 4, 8, ... nodes in each level
valid widget
so this?
haughty mountain
From top(root) to bottom, there are 1, 2, 4, 8, ... nodes in each level
that doesn't add up here
narrow mica
that doesn't add up here <:pithink:652247559909277706>
Well that's usually the case when you see a list... what does the question say?
haughty mountain
it almost makes sense as a dfs order with null as terminators
it just lacks two trailing nulls
but yeah, seeing the actual question would be helpful
it matches neither of the formats I would expect
and this is how broken things would be in the first interpretation
hmm, seems it's probably a BFS order
quite awkward
i.e.
regal spoke
i.e.
That is a natural generalization for how one would normally write down perfectly balanced binary trees
haughty mountain
I guess
regal spoke
For example heapq kind of uses this format
regal spoke
it almost makes sense as a dfs order with null as terminators
The issue with the dfs format is that it requires a very large number of nulls
haughty mountain
it is, but it's a much nicer embedding of a tree than this one
you can easily navigate around
regal spoke
Yepp, easily navigation is why the 2*i and 2*i+1 format is used in the first place
regal spoke
where the children are simply `2*i` and `2*i+1`
Btw heapq technically uses 0 indexing. So left node of node i has index 2*(i + 1) - 1 = 2*i + 1 and right node has index 2*(i + 1) + 1 - 1 = 2 * i + 2
The way I normally store a binary tree in my implementations is that I use a list A where A[i//2] gives the index of the left child of node i and A[i//2 + 1] gives the index of the right child or node i.
haughty mountain
huh?
or wdym
i//2 will squish stuff together, which is exactly what you don't want for the children
regal spoke
~~The way I normally store a binary tree in my implementations is that I use a l...
The way I normally store a binary tree in my implementations is that I use a list A where A[i*2] gives the index of the left child of node i and A[i*2 + 1] gives the index of the right child or node i.
One of the reasons I like this format is that the sibling of node A[i] is A[i ^ 1]. This can be super convinient
fiery cosmos
hi guys i just solved a medium problem in leetcode and I'm very happy because everything was written by me and the runtime and memory was pretty nice 😄
i will keep solving more problems
modern gulch
i will keep solving more problems
How long did it take you? Just curious
fiery cosmos
How long did it take you? Just curious
like 20 minutes, i have a whiteboard in my house, so its easier when you can write in the whiteboard and them pass that idea to code
polar jungle
Is there a data structure for building sequences from smaller sequences and avoiding repeated allocation? Would a linked list of non-linked lists be a good choice here (You concatenate all the lists together at the end of the computation)?
opal wadi
kind of a basic question, but what's the name for the type of enviroment where you run python cell by cell instead of all at once.
Sort of like jupyter notebook. I want to know so I can figure out how to do that on pycharm
vernal girder
Alr I’m wondering something
If we take 2 lines, such as y = x + 1 and y = x - 1, then make a shape from shading the area between the top and bottom lines in the range -1 <= x <= 1
Then, we make new areas given by similar rules, such as y = 2 and y = -2 in the same range as before
But you subtract all successive areas from the original area
Can you make a simple test to see if there is any of the original shape left at the end?
I don’t really need to how HOW MUCH is left after each subtraction, just if there remains PARTS OF THE ORIGINAL after all subtractions
Because if that sounds feasible, I’ve got a cool way to test if a set of lines is an opaque set of a given area (https://en.m.wikipedia.org/wiki/Opaque_set)
vernal girder
Ok I did it
The area is defined in the script in this format:
good_area = [((0.5, 0.5), (-0.5, 0.5)), ((-0.5, 0.5), (-0.5, -0.5)), ((-0.5, -0.5), (0.5, -0.5)), ((0.5, -0.5), (0.5, 0.5))]
This is graphed by the grey area in the left and right plots.
Then, the line segments are given. In this example, that would be:
segments = [((0.5, 0.25), (-0.5, -0.25)), ((-0.5, 0.25), (0.5, -0.25))]
If, in both the original and flipped versions, the grey area is completely filled out with its respective color, then the segments comprise an opaque set for the given area.
In this case, it does not, and you can see this by the remaining grey area.
I suppose what I need help with now is finding a more rigorous way to see if the grey area is filled with either red or blue. I think this way has a better big O notation than the one on wikipedia
clear eagle
where are you?
below the x axis
narrow mica
Is there a data structure for building sequences from smaller sequences and avoi...
wdym exactly?
regal spoke
Is there a data structure for building sequences from smaller sequences and avoi...
https://en.wikipedia.org/wiki/Rope_(data_structure) this is kinda like what you are talking about
C++ std::deque is also kinda similar
cobalt mirage
https://en.wikipedia.org/wiki/Rope_(data_structure) this is kinda like what you ...
rope?
haughty mountain
rope?
it's a pun on string
a rope (or cord) is a data structure that has a bunch of connected strings
cobalt mirage
🤔
serene karma
This is a bit of a general question but how do I continue to learn things? I am learning python and am using classes lists for and while loops etc. but I don't know what to learn next, in other languages as well I don't know what I don't know so where do I find that out?
kinda wierd question
narrow mica
Maybe DSA? That is, Data Structures and Algorithms
narrow mica
Well didn't you say you already know how to do that?
narrow mica
I know for loops and while loops
Well then you learned the loops already. I'm pretty sure there isn't some fancy 3rd type of loop
outer rain
This is a bit of a general question but how do I continue to learn things? I am ...
don't "learn" things, write stuff
narrow mica
I meant leetcode not stack
That's definitely one way to progress
outer rain
try doing something fun, programming for the sake of it
outer rain
like write a program which prints user's github activity to cli
or make flappy bird with pygame
or write a sudoku solver
narrow mica
code bullet stuff
Code bullet isn't really about game dev but AI (as is also indicated by their video titles)
serene karma
or write a sudoku solver
yea this though
outer rain
languages themselves are very big, but if I say "learn multiple inheritance" it will be super unhelpful, you need to see how it can be used first, so just try stuff out
you only need like 2% of the language to do a lot
serene karma
oh ok thanks this really answers my questions, I was kinda trying to complete languages but now it seems like that's not a thing
narrow mica
What you really want to learn are concepts which aren't specific to a language
outer rain
oh ok thanks this really answers my questions, I was kinda trying to complete la...
I would say that even if you want to learn the language, do something with this language instead
for example write your own language which translates to python
(or python bytecode if you are even deeper into it)
ok, maybe bad example because you will skip a lot
the opposite is better: write a translator from python to some other language
or analyze python in some other way
serene karma
ok thanks for all the help
summer fossil
well u can ask here! if anyone free they can reply u
summer fossil
Thanks I figured it out
Great Bro!
vernal girder
/// test ///
\\ test \\
how do i do the code format again lol
import random
import bisect
import heapq
# Generate random list
def generate_random_list(low_size, high_size, low_range, high_range):
list_size = random.randint(low_size, high_size)
random_values = [random.randint(low_range, high_range) for _ in range(list_size)]
return sorted(random_values)
# Generate uniform lists (for faster large generation)
def generate_uniform_list(num_values, start, end):
# Calculate the increment needed to achieve the specified number of values
increment = (end - start) / (num_values - 1)
# Generate the list of uniformly spaced values
uniform_list = [int(start + i * increment) for i in range(num_values)]
return uniform_list
num1 = generate_random_list(120000, 150000, -100000000, 100000000)
num2 = generate_uniform_list(50000000, -100300000, 100000300)
m = len(num1)
n = len(num2)
# Normal median
def median(list):
length = len(list)
med = 69
if length / 2 != length // 2:
med = list[length // 2]
else:
med = (list[(length // 2) - 1] + list[length // 2])/2
return med
# Quick median
def aug_median(list, count_mn):
length = len(list) + (count_mn[1] - count_mn[0])
med = 69
if length / 2 != length // 2:
med = list[length // 2]
else:
med = (list[(length // 2) - 1] + list[length // 2])/2
return med
# Normal version
print("Normal Version:")
combined_list = sorted(num1 + num2)
print(median(combined_list))
#"""
# This version
print("This Version:")
# Declarations
count_mn = [0, 0]
index_m = 0
index_n = 0
if m == 0: # Check if empty
print(median(num2))
elif n == 0: # Check if empty
print(median(num1))
else:
# Get the medians of each separately
med_1 = median(num1)
med_2 = median(num2)
# Swap if necessary
if med_1 < med_2:
med_1, med_2 = med_2, med_1
num1, num2 = num2, num1
m, n = n, m
# When the median of the first is larger
if med_1 > med_2:
# Get all indices
index_m = m//2 + 1
index_n = n//2 + 1
bi_index_m = bisect.bisect_left(num1, med_2) - 1
bi_index_n = bisect.bisect_left(num2, med_1)
# Make record of chops
count_mn[1] += m - index_m + n - bi_index_n
count_mn[0] += n - index_n + bi_index_m + 1
# Strike anything outside the indices
num1 = num1[bi_index_m + 1:(index_m)]
num2 = num2[-(index_n):bi_index_n]
# Sort remains
combined_list = list(heapq.merge(num1, num2))
# Send remains and record of chops
print(aug_median(combined_list, count_mn))
# When the medians are equal (immediate end)
else:
print(median(num1))
#"""
^ tryna do the leetcode problem: Median of Two Sorted Arrays
- The overall run time complexity should be O(log (m+n))
Don't know if i was able to do that, but its at least faster than the most basic way
haughty mountain
there is a nice and easy solution that scales with the range of inputs
but it's a bit worse than log(n+m)
shadow glen
what the elements in this list is considered?
[('echo', 'Hello World'), ('if', '2 < 3'), ('else', 'Change the new world')]
like, the () part?
warped iris
847. Shortest Path Visiting All Nodes
Here is the solution:
class Solution:
def shortestPathLength(self, graph: List[List[int]]) -> int:
n = len(graph)
visited = set()
q = deque()
for node in range(n):
q.append((node, 0, 1 << node))
visited.add((node, 1 << node))
reached = (1 << n) - 1
while q:
node, distance, mask = q.popleft()
if mask == reached:
return distance
for neighbor in graph[node]:
temp_mask = mask | (1 << neighbor)
if (neighbor, temp_mask) in visited:
continue
q.append((neighbor, distance+1, temp_mask))
visited.add((neighbor, temp_mask))
return -1
I have a question.
In this problem I think that there won't be ever a situation where we need to go trough the same path 2 times (I'm considering 0 -> 1 to be different than 1 -> 0), looking at the first example 0 -> 1 -> 0 -> 1 should not be ever necessary while 0 -> 1 -> 0 is a valid option, I though thebitmasking will prevent that, however while it will prevent 0 -> 1 -> 0 -> 1 it won't prevent 0 -> 1 -> 0 -> 2 -> 0 -> 1 (0 -> 1 path is taken two times). I know it's BFS solution and I'm showing DFS, however is there a possibility that this will occur (going through the same path two times) in BFS or it will always return before it happens, or maybe I'm wrong and there is some scenario where it's optimal to cross the same path multiple times?
I know that this solution wouldn't work if it would prevent going through the same path multiple time, since we could otherwise start only from one node not every node (q has every possible starting node)
So to clarify my question, will there ever be a situation before it returns an answer, that starting from node 0 it will explore the same path more than once like this 0 -> 1 -> 0 -> 2 -> 0 -> 1?
regal spoke
[847. Shortest Path Visiting All Nodes](https://leetcode.com/problems/shortest-p...
The standard way to deal with a traveling salesman problem is to think of it like there exists a weighted edge between any pair of nodes (the weight is equal to their distance between the two nodes in the original graph)
Then it is just a matter of finding the permutation that results in the lowest sum of weights. You can find this using DP with a bitmask in O(n^2 2^n) time
That way you dont have to think about whether or not you use the same edge multiple times or not
haughty mountain
like, the () part?
tuples?
warped iris
The standard way to deal with a traveling salesman problem is to think of it lik...
Thanks for the reply, I didn't even know that's a well know problem, I will dive deeper.
polar lodge
i literally just had a anagram problem smh
so easy to code but i forgot to use sort on the strings smh
vernal girder
Which has better time complexity for 2 sorted arrays num1 and num2?:
combined_list = list(heapq.merge(num1, num2))
combined_list = sorted(num1 + num2)
Seems like it should be heapq, but its doing worse in my benchmarks
polar lodge
Which has better time complexity for 2 sorted arrays num1 and num2?:
co...
ive never even used heapq 😟
polar lodge
i was in the middle of solving the easy anagram problem then the interviewer just cut me off and said they will lmk if they wanna proceed tomorrow smhh
regal spoke
Which has better time complexity for 2 sorted arrays num1 and num2?:
co...
Heapq merge is for combining tons of sorted lists
Also, sorted in Python uses a sorting algorithm called TIM sort, which runs in O(n) time if the data is already sorted / close to sorted
vernal girder
I see, so python sort is definitely best for two lists that are already themselves sorted
regal spoke
I see, so python sort is definitely best for two lists that are already themselv...
You could also try to manually code the merge in Python. That might be even faster.
vernal girder
tru
crisp mica
is it practical to make a data structure in python?
and not something like java or c++
vast onyx
@polar lodge Wow, not cool to just cut you off the interview. Was it a large company?
regal spoke
^ tryna do the leetcode problem: Median of Two Sorted Arrays
Median of two sorted arrays in O(log a + log b) time is pretty difficult to do. Here is a Python implementation I made for it
# Median of A[L:R]
# Assumes A is sorted
def find_median(A, L, R):
n = R - L
i = L + n//2
if n & 1:
return A[i]
else:
return A[i - 1], A[i]
# Median of A[L:R] + [x]
def find_median2(x, A, L, R):
B = sorted(A[L:R] + [x])
return find_median(B, 0, len(B))
# Median of A + B
# Assumes A and B are sorted
def solve(A, B):
# Median of A[LA:RA] + B[LB:RB]
# Assumes A and B are sorted
def median(LA, RA, LB, RB):
while True:
if RA <= LA:
return find_median(B, LB, RB)
if RB <= LB:
return find_median(A, LA, RA)
nB = RB - LB
midAL = (LA + RA - 1)//2
midAR = (LA + RA )//2
LA = max(midAL - nB, LA)
RA = min(midAR + nB + 1, RA)
nA = RA - LA
midBL = (LB + RB - 1)//2
midBR = (LB + RB )//2
LB = max(midBL - nA, LB)
RB = min(midBR + nA + 1, RB)
if LA + 1 == RA:
return find_median2(A[LA], B, LB, RB)
if LB + 1 == RB:
return find_median2(B[LB], A, LA, RA)
# Number of elements to remove from prefix and suffix
x = min(RA - LA, RB - LB)//2
midAL = A[(LA + RA - 1)//2]
midAR = A[(LA + RA )//2]
midBL = B[(LB + RB - 1)//2]
midBR = B[(LB + RB )//2]
if midAL < midBL:
LA += x
else:
LB += x
if midAR < midBR:
RB -= x
else:
RA -= x
return median(0, len(A), 0, len(B))
Maybe there is a simpler implementation out there, but this is what I felt was the most natural way to do it.
The idea behind my algorithm is that each iteration I remove x elements smaller than the median from A + B, and x elements larger than the median from A + B, where x is a number >= (len(A) + len(B)) / 6.
That way I keep the median of A + B the same while "removing" tons of elements from them.
vernal girder
Alr, made some formatting adjustments as well as the sliiightest bug fix that i hate took me so long
import random
import bisect
# Generate random list
def generate_random_list(low_size, high_size, low_range, high_range):
list_size = random.randint(low_size, high_size)
random_values = [random.randint(low_range, high_range) for _ in range(list_size)]
return sorted(random_values)
# Generate uniform list (for faster large generation)
def generate_uniform_list(num_values, start, end):
increment = (end - start) / (num_values - 1)
uniform_list = [int(start + i * increment) for i in range(num_values)]
return uniform_list
# To more easily test speeds, try using larger lists generated by generate_uniform_list()
NUM1 = generate_random_list(0, 1000, -10000000, 10000000)
NUM2 = generate_random_list(0, 1000, -10000000, 10000000)
M = len(NUM1)
N = len(NUM2)
# Normal median
def median(list):
length = len(list)
med = 69
if length % 2 != 0: med = list[length // 2]
else: med = (list[(length // 2) - 1] + list[length // 2])/2
return med
# Augmented median
def aug_median(list, count_mn):
length = len(list) + (count_mn[1] - count_mn[0])
med = 69
if length % 2 != 0: med = list[length // 2]
else: med = (list[(length // 2) - 1] + list[length // 2])/2
return med
# Normal version
def boring_version(num1, num2):
combined_list = sorted(num1 + num2)
return median(combined_list)
# My version
def my_version(num1, num2, m, n):
# Declarations
count_mn = [0, 0]
index_m, index_n = 0, 0
if m == 0: # Check if empty
return (median(num2))
elif n == 0: # Check if empty
return (median(num1))
else:
# Get the medians of each separately
med_1 = median(num1)
med_2 = median(num2)
# Swap if necessary
if med_1 < med_2:
med_1, med_2 = med_2, med_1
num1, num2 = num2, num1
m, n = n, m
# When the median of the first is larger
if med_1 > med_2:
# Get all indices
index_m = m//2 + 1
index_n = n//2 + 1
bi_index_m = bisect.bisect_left(num1, med_2)
bi_index_n = bisect.bisect_right(num2, med_1)
# Make record of chops
count_mn[1] += (m - index_m) + (n - bi_index_n)
count_mn[0] += (n - index_n) + (bi_index_m)
# Strike anything outside the indices
num1 = num1[bi_index_m:index_m]
num2 = num2[-index_n:bi_index_n]
# Sort remains
combined_list = sorted(num1 + num2)
# Send remains and record of chops
return (aug_median(combined_list, count_mn))
# When the medians are equal (immediate end)
else:
return (median(num1))
print("Normal Version:")
median_normal = boring_version(NUM1, NUM2)
print(median_normal)
print("My Version:")
median_fast = my_version(NUM1, NUM2, M, N)
print(median_fast)
mine finds the median of the arrays separately, removes all numbers outside of those two medians, but keeps count of the amount removed from each side
polar lodge
<@1005541208187228301> Wow, not cool to just cut you off the interview. Was it a...
yea to me to that means they def not interested in me smh and it was a senior recruiter who probably was a developer since he was asking technical questions
polar lodge
<@1005541208187228301> Wow, not cool to just cut you off the interview. Was it a...
but yea it wasnt the actual company they didnt tell me the company's name
regal spoke
mine finds the median of the arrays separately, removes all numbers outside of t...
But yours isnt logarithmic, right?
vernal girder
But yours isnt logarithmic, right?
not sure tbh
regal spoke
You have combined_list = sorted(num1 + num2), that definitely doesn't look logarithic to me
My code would run almost instantly even if A and B had size 10^9
vernal girder
yeah but that is with a fraction of the original list stes
*sets
num1 and num2 by that point have only the values between the medians of the original 2 sets
ive tested with large sets and its definitely faster than normal, near instant, dont know if its logarithmic tho
regal spoke
num1 and num2 by that point have only the values between the medians of the orig...
Okey but then your algorithm definitely isn't even close to be logarithmic
vernal girder
Yeah i wanted to start by cutting down the original sets, still have room to improve before just smashing the results together and doing the augmented median
vast onyx
but yea it wasnt the actual company they didnt tell me the company's name
Oh gotcha. Something else will come your way. How long have you been programming Python?
vernal girder
but like, for example,
pre cut lengths:
7076 and 9769
post cut lengths:
28 28
and its only sorting post cut
larger sets:
87857 and 78967
96 and 82
regal spoke
not sure tbh
Here is a benchmark to show the difference in speed between your solution (I'm guessing is either O(n) or O(n log n)) vs my solution (which is O(log n))
!e
import bisect
# Normal median
def median(list):
length = len(list)
med = 69
if length % 2 != 0: med = list[length // 2]
else: med = (list[(length // 2) - 1] + list[length // 2])/2
return med
# Augmented median
def aug_median(list, count_mn):
length = len(list) + (count_mn[1] - count_mn[0])
med = 69
if length % 2 != 0: med = list[length // 2]
else: med = (list[(length // 2) - 1] + list[length // 2])/2
return med
# My version
def my_version(num1, num2, m, n):
# Declarations
count_mn = [0, 0]
index_m, index_n = 0, 0
if m == 0: # Check if empty
return (median(num2))
elif n == 0: # Check if empty
return (median(num1))
else:
# Get the medians of each separately
med_1 = median(num1)
med_2 = median(num2)
# Swap if necessary
if med_1 < med_2:
med_1, med_2 = med_2, med_1
num1, num2 = num2, num1
m, n = n, m
# When the median of the first is larger
if med_1 > med_2:
# Get all indices
index_m = m//2 + 1
index_n = n//2 + 1
bi_index_m = bisect.bisect_left(num1, med_2)
bi_index_n = bisect.bisect_right(num2, med_1)
# Make record of chops
count_mn[1] += (m - index_m) + (n - bi_index_n)
count_mn[0] += (n - index_n) + (bi_index_m)
# Strike anything outside the indices
num1 = num1[bi_index_m:index_m]
num2 = num2[-index_n:bi_index_n]
# Sort remains
combined_list = sorted(num1 + num2)
# Send remains and record of chops
return (aug_median(combined_list, count_mn))
# When the medians are equal (immediate end)
else:
return (median(num1))
n = 2*10**5
A = [*range(n)]
B = [*range(n + 1, 2 * n)]
import timeit
print(timeit.timeit("my_version(A, B, len(A), len(B))", globals=locals(), number=100))
@regal spoke :white_check_mark: Your 3.11 eval job has completed with return code 0.
0.633063333996688
!e
# Median of A[L:R]
# Assumes A is sorted
def find_median(A, L, R):
n = R - L
i = L + n//2
if n & 1:
return A[i]
else:
return A[i - 1], A[i]
# Median of A[L:R] + [x]
def find_median2(x, A, L, R):
B = sorted(A[L:R] + [x])
return find_median(B, 0, len(B))
# Median of A + B
# Assumes A and B are sorted
def solve(A, B):
# Median of A[LA:RA] + B[LB:RB]
# Assumes A and B are sorted
def median(LA, RA, LB, RB):
while True:
if RA <= LA:
return find_median(B, LB, RB)
if RB <= LB:
return find_median(A, LA, RA)
nB = RB - LB
midAL = (LA + RA - 1)//2
midAR = (LA + RA )//2
LA = max(midAL - nB, LA)
RA = min(midAR + nB + 1, RA)
nA = RA - LA
midBL = (LB + RB - 1)//2
midBR = (LB + RB )//2
LB = max(midBL - nA, LB)
RB = min(midBR + nA + 1, RB)
if LA + 1 == RA:
return find_median2(A[LA], B, LB, RB)
if LB + 1 == RB:
return find_median2(B[LB], A, LA, RA)
# Number of elements to remove from prefix and suffix
x = min(RA - LA, RB - LB)//2
midAL = A[(LA + RA - 1)//2]
midAR = A[(LA + RA )//2]
midBL = B[(LB + RB - 1)//2]
midBR = B[(LB + RB )//2]
if midAL < midBL:
LA += x
else:
LB += x
if midAR < midBR:
RB -= x
else:
RA -= x
return median(0, len(A), 0, len(B))
n = 2*10**5
A = [*range(n)]
B = [*range(n + 1, 2 * n)]
import timeit
print(timeit.timeit("solve(A, B)", globals=locals(), number=100))
@regal spoke :white_check_mark: Your 3.11 eval job has completed with return code 0.
0.0036525960022117943
As you can see, there is a huge difference between running in logarithmic time vs linear time
That difference would only grow larger as n becomes bigger
vernal girder
ya im still working on what i want to do with the smaller lists, rn im mainly testing if cutting down to those lists is efficient enough
halcyon plankBOT
vernal girder
!e
import bisect
# Normal median
def median(list):
length = len(list)
med = 69
if length % 2 != 0: med = list[length // 2]
else: med = (list[(length // 2) - 1] + list[length // 2])/2
return med
# Augmented median
def aug_median(list, count_mn):
length = len(list) + (count_mn[1] - count_mn[0])
med = 69
if length % 2 != 0: med = list[length // 2]
else: med = (list[(length // 2) - 1] + list[length // 2])/2
return med
# My version
def my_version(num1, num2, m, n):
# Declarations
count_mn = [0, 0]
index_m, index_n = 0, 0
if m == 0: # Check if empty
return (median(num2))
elif n == 0: # Check if empty
return (median(num1))
else:
# Get the medians of each separately
med_1 = median(num1)
med_2 = median(num2)
# Swap if necessary
if med_1 < med_2:
med_1, med_2 = med_2, med_1
num1, num2 = num2, num1
m, n = n, m
# When the median of the first is larger
if med_1 > med_2:
# Get all indices
index_m = m//2 + 1
index_n = n//2 + 1
bi_index_m = bisect.bisect_left(num1, med_2)
bi_index_n = bisect.bisect_right(num2, med_1)
# Make record of chops
count_mn[1] += (m - index_m) + (n - bi_index_n)
count_mn[0] += (n - index_n) + (bi_index_m)
# Strike anything outside the indices
num1 = num1[bi_index_m:index_m]
num2 = num2[-index_n:bi_index_n]
# Sort remains
combined_list = sorted(num1 + num2)
# Send remains and record of chops
return (aug_median(combined_list, count_mn))
# When the medians are equal (immediate end)
else:
return (median(num1))
n = 2*10**9
A = [*range(n)]
B = [*range(n + 1, 2 * n)]
import timeit
print(timeit.timeit("my_version(A, B, len(A), len(B))", globals=locals(), number=100))
!e
import bisect
# Normal median
def median(list):
length = len(list)
med = 69
if length % 2 != 0: med = list[length // 2]
else: med = (list[(length // 2) - 1] + list[length // 2])/2
return med
# Augmented median
def aug_median(list, count_mn):
length = len(list) + (count_mn[1] - count_mn[0])
med = 69
if length % 2 != 0: med = list[length // 2]
else: med = (list[(length // 2) - 1] + list[length // 2])/2
return med
# My version
def my_version(num1, num2, m, n):
# Declarations
count_mn = [0, 0]
index_m, index_n = 0, 0
if m == 0: # Check if empty
return (median(num2))
elif n == 0: # Check if empty
return (median(num1))
else:
# Get the medians of each separately
med_1 = median(num1)
med_2 = median(num2)
# Swap if necessary
if med_1 < med_2:
med_1, med_2 = med_2, med_1
num1, num2 = num2, num1
m, n = n, m
# When the median of the first is larger
if med_1 > med_2:
# Get all indices
index_m = m//2 + 1
index_n = n//2 + 1
bi_index_m = bisect.bisect_left(num1, med_2)
bi_index_n = bisect.bisect_right(num2, med_1)
# Make record of chops
count_mn[1] += (m - index_m) + (n - bi_index_n)
count_mn[0] += (n - index_n) + (bi_index_m)
# Strike anything outside the indices
num1 = num1[bi_index_m:index_m]
num2 = num2[-index_n:bi_index_n]
# Sort remains
combined_list = sorted(num1 + num2)
# Send remains and record of chops
return (aug_median(combined_list, count_mn))
# When the medians are equal (immediate end)
else:
return (median(num1))
n = 2*10**7
A = [*range(n)]
B = [*range(n + 1, 2 * n)]
import timeit
print(timeit.timeit("my_version(A, B, len(A), len(B))", globals=locals(), number=100))
!e
import bisect
# Normal median
def median(list):
length = len(list)
med = 69
if length % 2 != 0: med = list[length // 2]
else: med = (list[(length // 2) - 1] + list[length // 2])/2
return med
# Augmented median
def aug_median(list, count_mn):
length = len(list) + (count_mn[1] - count_mn[0])
med = 69
if length % 2 != 0: med = list[length // 2]
else: med = (list[(length // 2) - 1] + list[length // 2])/2
return med
# My version
def my_version(num1, num2, m, n):
# Declarations
count_mn = [0, 0]
index_m, index_n = 0, 0
if m == 0: # Check if empty
return (median(num2))
elif n == 0: # Check if empty
return (median(num1))
else:
# Get the medians of each separately
med_1 = median(num1)
med_2 = median(num2)
# Swap if necessary
if med_1 < med_2:
med_1, med_2 = med_2, med_1
num1, num2 = num2, num1
m, n = n, m
# When the median of the first is larger
if med_1 > med_2:
# Get all indices
index_m = m//2 + 1
index_n = n//2 + 1
bi_index_m = bisect.bisect_left(num1, med_2)
bi_index_n = bisect.bisect_right(num2, med_1)
# Make record of chops
count_mn[1] += (m - index_m) + (n - bi_index_n)
count_mn[0] += (n - index_n) + (bi_index_m)
# Strike anything outside the indices
num1 = num1[bi_index_m:index_m]
num2 = num2[-index_n:bi_index_n]
# Sort remains
combined_list = sorted(num1 + num2)
# Send remains and record of chops
return (aug_median(combined_list, count_mn))
# When the medians are equal (immediate end)
else:
return (median(num1))
n = 2*10**6
A = [*range(n)]
B = [*range(n + 1, 2 * n)]
import timeit
print(timeit.timeit("my_version(A, B, len(A), len(B))", globals=locals(), number=100))
!e
import bisect
# Normal median
def median(list):
length = len(list)
med = 69
if length % 2 != 0: med = list[length // 2]
else: med = (list[(length // 2) - 1] + list[length // 2])/2
return med
# Augmented median
def aug_median(list, count_mn):
length = len(list) + (count_mn[1] - count_mn[0])
med = 69
if length % 2 != 0: med = list[length // 2]
else: med = (list[(length // 2) - 1] + list[length // 2])/2
return med
# My version
def my_version(num1, num2, m, n):
# Declarations
count_mn = [0, 0]
index_m, index_n = 0, 0
if m == 0: # Check if empty
return (median(num2))
elif n == 0: # Check if empty
return (median(num1))
else:
# Get the medians of each separately
med_1 = median(num1)
med_2 = median(num2)
# Swap if necessary
if med_1 < med_2:
med_1, med_2 = med_2, med_1
num1, num2 = num2, num1
m, n = n, m
# When the median of the first is larger
if med_1 > med_2:
# Get all indices
index_m = m//2 + 1
index_n = n//2 + 1
bi_index_m = bisect.bisect_left(num1, med_2)
bi_index_n = bisect.bisect_right(num2, med_1)
# Make record of chops
count_mn[1] += (m - index_m) + (n - bi_index_n)
count_mn[0] += (n - index_n) + (bi_index_m)
# Strike anything outside the indices
num1 = num1[bi_index_m:index_m]
num2 = num2[-index_n:bi_index_n]
# Sort remains
combined_list = sorted(num1 + num2)
# Send remains and record of chops
return (aug_median(combined_list, count_mn))
# When the medians are equal (immediate end)
else:
return (median(num1))
n = 2*10**4
A = [*range(n)]
B = [*range(n + 1, 2 * n)]
import timeit
print(timeit.timeit("my_version(A, B, len(A), len(B))", globals=locals(), number=100))
@vernal girder :white_check_mark: Your 3.11 eval job has completed with return code 0.
0.0549334449970047
!e
import bisect
# Normal median
def median(list):
length = len(list)
med = 69
if length % 2 != 0: med = list[length // 2]
else: med = (list[(length // 2) - 1] + list[length // 2])/2
return med
# Augmented median
def aug_median(list, count_mn):
length = len(list) + (count_mn[1] - count_mn[0])
med = 69
if length % 2 != 0: med = list[length // 2]
else: med = (list[(length // 2) - 1] + list[length // 2])/2
return med
# My version
def my_version(num1, num2, m, n):
# Declarations
count_mn = [0, 0]
index_m, index_n = 0, 0
if m == 0: # Check if empty
return (median(num2))
elif n == 0: # Check if empty
return (median(num1))
else:
# Get the medians of each separately
med_1 = median(num1)
med_2 = median(num2)
# Swap if necessary
if med_1 < med_2:
med_1, med_2 = med_2, med_1
num1, num2 = num2, num1
m, n = n, m
# When the median of the first is larger
if med_1 > med_2:
# Get all indices
index_m = m//2 + 1
index_n = n//2 + 1
bi_index_m = bisect.bisect_left(num1, med_2)
bi_index_n = bisect.bisect_right(num2, med_1)
# Make record of chops
count_mn[1] += (m - index_m) + (n - bi_index_n)
count_mn[0] += (n - index_n) + (bi_index_m)
# Strike anything outside the indices
num1 = num1[bi_index_m:index_m]
num2 = num2[-index_n:bi_index_n]
# Sort remains
combined_list = sorted(num1 + num2)
# Send remains and record of chops
return (aug_median(combined_list, count_mn))
# When the medians are equal (immediate end)
else:
return (median(num1))
n = 2*10**3
A = [*range(n)]
B = [*range(n + 1, 2 * n)]
import timeit
print(timeit.timeit("my_version(A, B, len(A), len(B))", globals=locals(), number=100))
@vernal girder :white_check_mark: Your 3.11 eval job has completed with return code 0.
0.004894115001661703
keen hearth
@vernal girder can you use #bot-commands if you need to evaluate a longer block of code multiple times. Btw, if you edit your code shortly after evaluating it, it will let you re-evaluate it without having to re-post the code.
vernal girder
Oh ya my b
warped iris
What's the time complexity of bit shifting for example 1 << 25694?
lean walrus
O(1)
haughty mountain
O(1)
only because the question is a bad one
1 << n is not O(1) in python
it's something like O(log(n))
lean walrus
it's something like O(log(n))
Im pretty sure it is O(n)
Because it requires n bits to be allocated, so it is O(n) time and memory
It is also equal to O(log(2^n)), which might be the thing that confused you
In C (and a lot of other langs) it is O(1) btw
agile sundial
because integer sizes are bounded
regal spoke
What's the time complexity of bit shifting for example `1 << 25694`?
1 << 25694 is just a large constant, so it is "O(1)"
regal spoke
Because it requires n bits to be allocated, so it is O(n) time and memory
It is O(n) if you count the number of bit operations. But normally with time complexity you consider log n sized operations (like adding two integers) to take O(1) time. In that sense the time complexity of 1 << n is O(n/log n). Sometimes you also see people write it as O(n/w), where w stands for the word size.
That w is the reason why data-structures like bitsets are so efficient.
So I wouldn't say 1 << n is O(n).
outer rain
I would absolutely say 1 << n is O(n) because considering word operations take O(1) and then saying the word size is O(log n) has funny consequences (hello transdichotomous model...). I am also fine with 1 << n is O(n/w) in word-ram model. However, I am pretty sure it is even funnier, because modern MMU operate on virtual memory, which is almost free to map to process memory and zero-out. So funnily enough, if you shift 1 by a large number and it causes memory allocation, it will be done either in O(n / B) where B is a page size (4096 bytes typically), at least as far as I know, it may even be O(1). And if it reuses existing memory it will get memset-ed to zero in O(n / B).
edit: assuming it does memset or other form page-by-page zeroing.
regal spoke
I would absolutely say `1 << n` is `O(n)` because considering word operations ta...
saying the word size is O(log n) that is essentially what everyone does all the time
s = 0
for i in range(n):
s += i
I think everyone would agree with my that this is O(n)
regal spoke
This is nlogn
Normally it is considered O(n)
Basically because we think of the word size as being O(log n)
lean walrus
I see, interesting point
outer rain
`saying the word size is O(log n)` that is essentially what everyone does all th...
ok, clarification: it does not matter most of the time. But then once you try to calculate the complexity of long arithmetic it becomes extremely annoying, so you usually count bit and word operations instead, which is exactly what we try to do in our case. I find saying that bit shift is O(n / log n) extremely unsual .
regal spoke
ok, clarification: it does not matter most of the time. But then once you try to...
The reason why I think it is good to say that bitshift is O(n / log n) or O(n / w) is that not all bit operations can neccessarily be sped up by a factor of w.
For example I know of some knapsack algorithms that only work with bits, but that cannot be sped up by a factor of w.
outer rain
would you say that binary multiplication of two n-bit numbers is O(n^2 / log n) though?
I mean, ok fair, you got a point. It's just that I find it weird saying that bitshift is O(n / log n) all of a sudden
I know that this is correct, but then you plug small numbers into it and it's not really how it scales...
again, technically correct
but unnatural
lean walrus
(btw there are better multiplication algos than O(n^2): https://en.wikipedia.org/wiki/Karatsuba_algorithm)
outer rain
I specified binary, idk if it sounded too ambiguous
lean walrus
oh, i cant read :(
narrow mica
I think karatsuba's works in arbitrary-based number systems aswell?
I'm reading "binary multiplication" as "multiplying in 2-based number system"
outer rain
yeah, looking back now, that's a bad wording from me
I meant like the same thing as with binary exponentiation
except you sum instead of multiply
narrow mica
Though for that matter, FFT works in O(n logn), but I think elteammate wasn't focusing on this part so I assumed they mean the simple algorithm
outer rain
yeah, the standard one
(FFT multiplication works in O(n log n log log n) btw, the recent crazy one with multidimentional fft is O(n log n) but I'm nitpicking now)
haughty mountain
Im pretty sure it is O(n)
oh right, it's n bits, so O(n)
haughty mountain
Normally it is considered O(n)
I'll happily say it's O(n) if your integer sizes are bounded by something sensible
haughty mountain
(FFT multiplication works in `O(n log n log log n)` btw, the recent crazy one wi...
n log n but yeah
@regal spoke has some insights into that approach 😛
narrow mica
Well the n logn one's constants are too big so the n logn loglogn one is used in practice
regal spoke
The thing that complicates the time complexity of big integer multiplication is if you should count multiplication of word size to take constant time or not.
If you assume that multiplication of log n bit numbers take O(1) time, then a straight forward FFT algorithm for big integer multiplication takes O(n) time.
This FFT approach is probably the most common fast big int multiplication out there
For example the decimal module in Python uses this approach.
outer rain
If you assume that multiplication of log n bit numbers take O(1) time, then a st...
(I told you things are weird if you assume this!)
outer rain
i want someone to explain to me args and *kwargs as a concept
ask in #1035199133436354600, this isn't really a channel for expaining language concepts...
next pecan
ok thanks
regal spoke
(I told you things are weird if you assume this!)
Yes definitely, but it also encaptures much better how fast algorithms actually run in practice. For example Karatsuba is normally said to have time complexity O(n^log_2(3)) \approx O(n^1.58).
But if you assume that multiplication of log n bit numbers take O(1) time, then Karatsuba has time complexity O((n/log n) ^ log_2(3))
So assuming constant time word size multiplication, FFT based big int mult takes O(n) and Karatsuba takes O((n/log n) ^ log_2(3)).
outer rain
True, but also when you are given numbers, those are usually in base 10 (=1e9), or base 2^32 or other radix which makes sense, which is usually about w or sqrt(w), so "in practice" it's still O(n log n) and O(n^1.58)
this is an interesting point though, we might just be talking about slightly different things on some deeper level🤔
(i still find reasoning about log-n operations being O(1) hurting my brain and need to use w instead lol)
regal spoke
Another reason why I think it makes sense to assume multiplication of log n bit numbers taking O(1) time is that in practice you wouldn't use a big int multiplication algorithm to do small multiplication
outer rain
multiplication - sure, bit shifting - uhm... idk
anyway, yeah, everything you say is correct, it's just me being annoying jerk👺
halcyon plankBOT
:incoming_envelope: :ok_hand: applied timeout to @lament portal until <t:1695144572:f> (10 minutes) (reason: duplicates spam - sent 4 duplicate messages).
The <@&831776746206265384> have been alerted for review.
lament portal
fiery cosmos
Another reason why I think it makes sense to assume multiplication of log n bit ...
hey my brother how are you! how are the coding doing!
slim galleon
shadow glen
how do i execute an asynchronous function outside an asynchronous function?
cus await don't work
agile sundial
you can't
shadow glen
you can't
how do i do it then
is there any library that do that?
allowing me to execute asycnhronous function outside?
dull lantern
allowing me to execute asycnhronous function outside?
the idea of async await is just an abstraction of callbacks The await keyword is permitted within the function body, enabling asynchronous, promise-based behavior to be written in a cleaner style and avoiding the need to explicitly configure promise chains.
the whole idea of an async function is it allows the await keyword
so you wont be able to use them anywhere
outer rain
dull lantern
allowing me to execute asycnhronous function outside?
async await is basically just letting you do this without indenting lol
you can also use .then
dull lantern
is there any library that do that?
all these or using await are basically equivalent if that makes more sense
outer rain
async await is basically just letting you do this without indenting lol
(it does not work that way in python though afaik)
but people at #async-and-concurrency know better, this is really not a chat for that
dull lantern
oh lol
I mean idr use python for async but I mean it seems exactly the same usage as js
shadow glen
I mean idr use python for async but I mean it seems exactly the same usage as js
well, works different, according to this error:
Traceback (most recent call last):
File "/home/runner/RP-Utilities-Beta/bot.py", line 9, in <module>
import server
File "/home/runner/RP-Utilities-Beta/server.py", line 23
await server_bot_synchrony()
^^^^^^^^^^^^^^^^^^^^^^^^^^^^
SyntaxError: 'await' outside function
nah you can do that in js either
thats what I mean its exactly the same implementation
u can just make an async function main that calls everything you want and you just put the awaits in there and then call the main function when you wanna run the program
dull lantern
well, works different, according to this error:
```
Traceback (most recent call ...
if ur trying to import something that uses async await so you dont want to use a run function you can just import the async functions and await them in your main program
shadow glen
oh, so the syntax is asyncio.run(main())
dull lantern
yeah but just to run the main program
Note: asyncio.run() should only be used once in a program and is intended as a convenient function to run asynchronous functions in a simple, single-threaded manner ```there are other interesting things depending on if youre trying to load data async def main(): async with asyncio.TaskGroup() as tg: task1 = tg.create_task(some_coro(...)) task2 = tg.create_task(another_coro(...)) print("Both tasks have completed now.")
but you can just check the docs https://docs.python.org/3/library/asyncio-task.html
shadow glen
Bot Connected!
Traceback (most recent call last):
File "/home/runner/RP-Utilities-Beta/bot.py", line 99, in <module>
asyncio.run(main())
File "/nix/store/xf54733x4chbawkh1qvy9i1i4mlscy1c-python3-3.10.11/lib/python3.10/asyncio/runners.py", line 44, in run
return loop.run_until_complete(main)
File "/nix/store/xf54733x4chbawkh1qvy9i1i4mlscy1c-python3-3.10.11/lib/python3.10/asyncio/base_events.py", line 649, in run_until_complete
return future.result()
File "/home/runner/RP-Utilities-Beta/bot.py", line 95, in main
await run_bot()
File "/home/runner/RP-Utilities-Beta/bot.py", line 91, in run_bot
Bot().run(bot_token.return_token())
File "/home/runner/RP-Utilities-Beta/.pythonlibs/lib/python3.10/site-packages/discord/client.py", line 862, in run
asyncio.run(runner())
File "/nix/store/xf54733x4chbawkh1qvy9i1i4mlscy1c-python3-3.10.11/lib/python3.10/asyncio/runners.py", line 33, in run
raise RuntimeError(
RuntimeError: asyncio.run() cannot be called from a running event loop
it says it cannot be called from a running event loop
why?
outer rain
ok honestly
it will probably be better if you learn asyncio more fundamentally
because writing asynchronous code is just as different as writing oop vs proceducal
it's very different and it is very hard to just randomly stumble into something working
shadow glen
!paste
halcyon plankBOT
shadow glen
thought how am i calling a loop from a running event?
https://paste.pythondiscord.com/MRLA
it's confuse
like, before the bot was working perfectly
but then when i try ti implement it for servering
not working
it seems that asynchronous make multitasks and await is a parameter to await the other function to work
this is the concept
the asynchronous function works together
but why it's not working
dull lantern
im remote work so I'm sorry I can't really help you now bc I got some requests I thought you were just fetching data but https://realpython.com/how-to-make-a-discord-bot-python/ this prolly will help, they explain async await and apply it for a bot
minor heath
can someone explain classes mainly stuff like the getter and setter methods?
halcyon escarp
Can someone help me with a topological sort question?
vernal girder
import random
import bisect
# Generate random list
def generate_random_list(low_size, high_size, low_range, high_range):
list_size = random.randint(low_size, high_size)
random_values = [random.randint(low_range, high_range) for _ in range(list_size)]
return sorted(random_values)
NUM1 = generate_random_list(50000, 100000, -10000000, 10000000)
NUM2 = generate_random_list(50000, 100000, -10000000, 10000000)
#n = 2*10**6
#NUM1 = [*range(n)]
#NUM2 = [*range(n + 1, 2 * n)]
M = len(NUM1)
N = len(NUM2)
# Normal median
def median(list):
length = len(list)
med = 69
if length % 2 != 0: med = list[length // 2]
else: med = (list[(length // 2) - 1] + list[length // 2])/2
return med
def augment(num1, num2, count_mn):
shift = count_mn[1] - count_mn[0]
if (shift) < 0:
for i in range(-shift):
if num1 and num2:
if num1[-1] > num2[-1]: num1.pop()
else: num2.pop()
elif num1: num1.pop()
elif num2: num2.pop()
elif (shift) > 0:
for i in range(shift):
if num1 and num2:
if num1[0] < num2[0]: num1.pop(0)
else: num2.pop(0)
elif num1: num1.pop(0)
elif num2: num2.pop(0)
else: return num1, num2
return num1, num2
def binary_sort(small, large):
for num in small:
index = bisect.bisect_left(large, num)
large.insert(index, num)
return large
def my_version(num1, num2, m, n):
while True:
if m == 0: return (median(num2))
elif n == 0: return (median(num1))
else:
count_mn = [0, 0]
index_m, index_n = 0, 0
med_1 = median(num1)
med_2 = median(num2)
# Swap if necessary
if med_1 < med_2:
med_1, med_2 = med_2, med_1
num1, num2 = num2, num1
m, n = n, m
# When the median of the first is larger
if med_1 > med_2:
# Get all indices
index_m = m//2 + 1
index_n = n//2 + 1
bi_index_m = bisect.bisect_left(num1, med_2)
bi_index_n = bisect.bisect_right(num2, med_1)
if bi_index_m == m//2 and m%2 == 0: bi_index_m -= 1
if bi_index_n == n//2 and n%2 == 0: bi_index_n += 1
# Make record of chops
count_mn[1] += (m - index_m) + (n - bi_index_n)
count_mn[0] += (n - index_n) + (bi_index_m)
# Strike anything outside the indices
num1 = num1[bi_index_m:index_m]
num2 = num2[-index_n:bi_index_n]
# Even the remains
num1, num2 = augment(num1, num2, count_mn)
m, n = len(num1), len(num2)
if m == 0: return (median(num2))
elif n == 0: return (median(num1))
elif num1[0] >= num2[-1]: return median(num2 + num1) # Check if lists can be appended to each other
elif num2[0] >= num1[-1]: return median(num1 + num2) # Check if lists can be appended to each other
elif m < 3 or n < 3: # Check if the minimum is reached
if m < n: return median(binary_sort(num1, num2))
else: return median(binary_sort(num2, num1))
else: return (median(num1))
# Normal version
def boring_version(num1, num2):
combined_list = sorted(num1 + num2)
return median(combined_list)
print("Normal Version:")
median_normal = boring_version(NUM1, NUM2)
print(median_normal)
print("My Version:")
median_fast = my_version(NUM1, NUM2, M, N)
print(median_fast)
import timeit
print(timeit.timeit("my_version(NUM1, NUM2, M, N)", globals=locals(), number=100))
^ here's what ive been working on with the median of two sorted lists leetcode problem
What I'm a bit confused on is when I use this to generate the lists:
#n = 2*10**6
#NUM1 = [*range(n)]
#NUM2 = [*range(n + 1, 2 * n)]
It sometimes returns and prints my value but doesn't quit the timer for a long time. Any reason why that is?
besides that, I wanna make the augment() function better, its probably unoptimal, I just wanted to get the idea working first
grizzled bough
is
arr = [0]*n
for i in range(n):
arr[i] = ...
faster than
arr = []
for i in range(n):
arr.append(...)
Does the speed leetcode gives u on submission have anything to do with it’s time complexity?
regal spoke
Does the speed leetcode gives u on submission have anything to do with it’s time...
Wdym "the speed leetcode gives u"
Are you talking about the time limit on leetcode?
vernal girder
When u submit, it tells you how fast ur code was
But that’s only somewhat related to it’s time complexity especially if it uses a lot of small sets right?
regal spoke
But that’s only somewhat related to it’s time complexity especially if it uses a...
If the tests are well made on leetcode, then time complexity should basically be the only thing that matters
vernal girder
Ok cool
regal spoke
```py
def my_version(num1, num2, m, n):
while True:
if m == 0: retur...
I think the time complexity of this is still O(n log n)
The task on leetcode is to make it run in O(log n)
vernal girder
Just wondering cuz this one beat 96% of users in speed but I didn’t really know if that mattered all that much for this one
vernal girder
I think the time complexity of this is still O(n log n)
I can’t benchmark it on here cuz of character limit lol
regal spoke
Your code is still crazy slow compared to what is possible / what is asked for in the problem statement
regal spoke
I can’t benchmark it on here cuz of character limit lol
Just run Python on your own computer.
barren coyote
Or a CodeSpace
They’re free
||exceptions apply eventually||
regal spoke
vernal girder
Your code is still crazy slow compared to what is possible / what is asked for i...
I mean my benchmarks were pretty good for 510^5 thru 110^6 range lol, usually around 0.015
regal spoke
"Usually get" is not what is important
Time complexity is about how fast your program runs in the worst case
vernal girder
Yeah I’m doing it a bunch and I’m not getting anything higher than that
I mean usually as in my worst time in a bunch, on average it’s like 0.005
regal spoke
Ye you've might have a somewhat decent solution for random test cases (it is still pretty slow compared to what is possible)
But your code is crazy slow in the worst case
So you have definitely not solved the task
vernal girder
Oh r u testing it?
I don’t know what the problem with that is, it’s returning the answer in a split second and then the time will keep going for like 10 seconds
regal spoke
Oh r u testing it?
I dont need to test it. Just from reading the code I can see how it works, and you have code like
def binary_sort(small, large):
for num in small:
index = bisect.bisect_left(large, num)
large.insert(index, num)
return large
This is increadibly slow compared to what is possible
vernal girder
I only use that for when one list is 2 long or less
regal spoke
Yes, and in that case your code runs really really slow
Suppose one array have length 10^9 and the other has length 2. Then you are currently doing around 2 * 10^9 operations by calling .insert twice
A good solution would only need to do like 100 operations
vernal girder
That’s not gonna happen
zenith tundra
If both lists are sorted, use heapq.merge. https://docs.python.org/3/library/heapq.html?highlight=heapq#heapq.merge
regal spoke
If both lists are sorted, use heapq.merge. https://docs.python.org/3/library/hea...
That wont work
The task is about finding the meadian of two lists in O(log n) time
vernal girder
It would weed out over half the larger list before that ever happened
regal spoke
That’s not gonna happen
What is not going to happen?
vernal girder
It wouldn’t do flat 10^9 size, it would weed it down a lot before it got there
regal spoke
What if nums1 = [0] and nums2 = [1,2,..., 10^9]
vernal girder
Then u didn’t read my code lol
First, that would just activate num1 + num2, but second even if it were [1] and [0, 2, etc.], the way it weeds stuff out, the majority of the large list is gonna be ignored by the time it gets there
It ain’t perfect, I already said it’s WIP. It was a test to implement a function where one list will be small. I already know insert is slow lol
regal spoke
Then u didn’t read my code lol
NUM1 = [0]
NUM2 = list(range(1, 3*10**5 + 1))
M = len(NUM1)
N = len(NUM2)
median_fast = my_version(NUM1, NUM2, M, N)
Try running this
I'm not sure if your code gets stuck in an infinite loop, or if it is just really slow
vernal girder
Yea thats what i was talking about earlier
try it with a print statement that returns the result of the function
you'll see the result prints almost instantly meaning the function ended, but the timer keeps going lol
vernal girder
wait actually i think that does bug it holdup
ah its getting caught in my fucky augment function
yeah see my augment function actually does suck, thats why i said i wanted to work on it lmao
regal spoke
NUM1 = [0]
NUM2 = list(range(1, 10**7 + 1))
import timeit
print(timeit.timeit("solve(NUM1, NUM2)", globals=locals(), number=1))
This takes 0.00001 s
NUM1 = [0]
NUM2 = list(range(1, 10**7 + 1))
M = len(NUM1)
N = len(NUM2)
import timeit
print(timeit.timeit("my_version(NUM1, NUM2, M, N)", globals=locals(), number=1))
This hasn't even finished for me yet. (Note that I only call your function once, so it doesn't matter that it modifies NUM1 and NUM2)
What you really should do is to think about how to entirely avoid anything that runs in O(n) time.
vernal girder
duh lmao
unless its on the final pass where a list will be within the same size range no matter the initial size
regal spoke
for x in range(1, 6):
NUM1 = [0]
NUM2 = list(range(1, x*10**5 + 1))
M = len(NUM1)
N = len(NUM2)
import timeit
print(timeit.timeit("my_version(NUM1[:], NUM2[:], M, N)", globals=locals(), number=1))
Outputs
0.1189719000030891
0.49390020000282675
3.2561825000011595
11.29144030000316
20.22324490000028
I have no clue what your time complexity is
These are some really funny looking numbers
vernal girder
yeah its the augment function, it sucks lmao
regal spoke
Btw there is a realatively simple test for if a number x is equal to the median, lower than the median or larger than the median
Just from doing a couple of binary searches
vernal girder
nah dont tell me thats cheating lmao
cobalt mirage
How do you approach questions like these?
Its bit harder for me to think about the median
i was thinking of doing binary search on both
like at the same time
regal spoke
The easiest is to think about what I said just above #algos-and-data-structs message
This will lead to a relatively simple O(log^2 n) solution
Which is not optimal, but still pretty good
cobalt mirage
Btw there is a realatively simple test for if a number x is equal to the median,...
is this log(m+n)
cobalt mirage
This will lead to a relatively simple O(log^2 n) solution
🤔
regal spoke
Think about it, if you have a test that can check if x is below, at, or above the median, then you can just binary search for the x that is equal to the median .
regal spoke
but how do you know the median
x is the median of A+B if half of the elements in A + B are smaller than the median (and half are larger)
You can count how many elements are smaller than x in A + B with two binary searches
regal spoke
but how do you know the median
A priori I don't know the median, but I can test if some x is the median or not
cobalt mirage
A priori I don't know the median, but I can test if some `x` is the median or no...
How
regal spoke
I just told you ^
cobalt mirage
How would you check if x is greater and smaller than half of A + B
in logn+m
🤔
@regal spoke nvm, I haven't tried the problem
brb
But I got another question
regal spoke
bisect.bisect_left(A, x) returns how many elements in A that are smaller than x
bisect.bisect_left(B, x) returns how many elements in B that are smaller than x
regal spoke
So the number of elements in A + B that are smaller than x is bisect.bisect_left(A, x) + bisect.bisect_left(B, x)
cobalt mirage
was this DP on tree/graph
regal spoke
was this DP on tree/graph
This was basically a test for if you knew an algorithm for finding the diameter of a tree
cobalt mirage
So the number of elements in `A + B` that are smaller than `x` is `bisect.bisect...
ima try the problem first and then ima come back
cobalt mirage
This was basically a test for if you knew an algorithm for finding the diameter ...
diameter of a tree? isnt that bottom up
oh i forgot you did bfs
regal spoke
Two bfs is the standard technique
cobalt mirage
How do you apply diameter of a tree on here
also what led you to that conclusion it is that
cobalt mirage
"Determine the longest distance between two ..." on a tree
But how do we know its a tree?
regal spoke
But how do we know its a tree?
"Is given by a tree"
cobalt mirage
what line
regal spoke
regal spoke
There is another thing that makes it obvious that this is a tree. The number of edges is n - 1
cobalt mirage
There is another thing that makes it obvious that this is a tree. The number of ...
How?
cobalt mirage
No I am saying how does that n-1 edges mean a tree?
regal spoke
A graph is a tree if number of edges is n - 1 and the graph is connected
In 99.999 % of cases, if the problem statement says "the number of edges is n - 1", then the problem is about trees
I would say like 90 % of graph problems are on trees. So just seeing
would make me guess that it is likely a tree problem
Btw speaking of the bfs algorithm for finding tree diameter. I'm not the only one that claims that it is the standard algorithm for tree diameter
cobalt mirage
Btw speaking of the bfs algorithm for finding tree diameter. I'm not the only on...
I learned it bottom up first time so I dont know if its standard
regal spoke
For example problem C in this tutorial https://codeforces.com/blog/entry/66639 starts with
The standard algorithm for finding the diameter of a tree is to find the farthest distance from node 1
, then find the farthest distance from that node.
cobalt mirage
For example problem C in this tutorial https://codeforces.com/blog/entry/66639 s...
I can't process how that works lol
regal spoke
Trees are weird sometimes
cobalt mirage
output = [0]
def dfs(node):
if not node:
return 0
left = dfs(node.left)
right = dfs(node.right)
output[0] = max(left + right, output[0])
return max(left, right) + 1
dfs(root)
return output[0]```do you also agree with this?
regal spoke
I think so
regal spoke
```py
output = [0]
def dfs(node):
if not node:
...
You could do this with a bfs too
cobalt mirage
You could do this with a bfs too
Yeah I am not sure how
I can't process it, i can learn how to
I just wanna make sure I understand this problem and what its asking
to make me think its diameter of a tree
cobalt mirage
In 99.999 % of cases, if the problem statement says "the number of edges is n - ...
so basically if its like a linkedlist its still counts as a tree in this def right
regal spoke
Not sure what you mean by linked list here
Trees are normally stored as an adjecency list
cobalt mirage
Nah
😹
I mean def of a linkedlist
not like the actual linkedlist
ima puill up a example
I am saying if the structure of that given adjcency looked like this
it would still be a tree right
regal spoke
With directed edges it would not be a tree
cobalt mirage
oh it has to be undirected
regal spoke
But if you have a rooted tree, then you could create the graph where all edges are directed away from the root. This is called https://en.wikipedia.org/wiki/Arborescence_(graph_theory)
cobalt mirage
But if you have a rooted tree, then you could create the graph where all edges a...
Oh are you trying to say that if your tree doesn't have a root, and its directed, is like a example given, it wouldn't be a tree
regal spoke
I would never call a graph with directed edges a tree
regal spoke
NOO
regal spoke
regal spoke
I'm gonna sleep soon
cobalt mirage
😭
poajene
can you send your bfs code 🙏
for that q
def do_bfs(graph, start=0):
n = len(graph)
found = [0] * n
bfs = [start]
found[start] = 1
for u in bfs:
for v in graph[u]:
if not found[v]:
found[v] = 1
bfs.append(v)
return bfs
def find_diameter(graph):
u = do_bfs(graph)[-1]
v = do_bfs(graph, u)[-1]
return u,v```is this called "double bfs"?
fiery cosmos
Is there anybody who wants to be learning buddy with doing DSA problems? I am beginner. Also will slowly learn about system design. What I mean by learning buddy is that we can support each other with problems, for example procrastination, also we can share knowledge, e.g. to share knowledge about some patterns behind solving DSA problems
How would you describe in one sentence post order, in order and pre order traversal?
Also, is there any good roadmap for getting better at DSA, what kind of problems to solve? Just solve LeetCode easy problems first?
urban kiln
so i have a list with n objects and now i want to convert this into a matrix (size = m * o where m*o = n)
is there some pythonic way of doing this, or do i just use a for loop?
haughty mountain
so i have a list with n objects and now i want to convert this into a matrix (si...
!e
a = [1, 2, 3, 4, 5, 6, 7, 8]
n = len(a)
m = 2
print([a[i:i+m] for i in range(0, n, m)])
@haughty mountain :white_check_mark: Your 3.11 eval job has completed with return code 0.
[[1, 2], [3, 4], [5, 6], [7, 8]]
there will be a function for this in 3.12
itertools.batched I think, which is a name I kinda hate
fiery cosmos
I am beginner into dsa, can anyone recommend some tutorial or something where to start from? i am confused
haughty mountain
the pins have some resources
fiery cosmos
okayy
cobalt mirage
A test needs to be prepared on the SAT platform with questions from different se skills to assess candidates. Given an array, skills, of size n, where skills[i] denotes the skill t of the ith question, select skills for the questions on the test. The skills should be grouped together as much as possible. The goal is to find the maximum length of a subsequence o skills such that there are no more than k unequal adjacent elements in the subsequence. Formally, find a subsequence of skills, call it x, of length m such that there are at most k in where x[i]!= x[i+1] for all 0 si<m.
Note: A subsequence of an array is obtained by deleting several elements of the array (po zero or all) without changing the order of the remaining elements. For example, [1, 3, 4], [3 subsequences of [1, 2, 3, 4] whereas [1, 5], [4, 3] are not.
Example
skills = [1, 1, 2, 3, 2, 1], k = 2.
The longest possible subsequence is x = [1, 1, 2, 2, 1]. There are only two indices where x[ x[2] and x[3] != x[4].
Return its length, 5.
Function Description
Complete the function findMaxLength in the editor below.
findMaxLength has the following parameter(3):
int skills[n]: the different skill types
int k: the maximum count of unequal adjacent elements
Returns
int: the maximum value of m
Constraints
•1≤n≤2*10^3
• 1sk≤n
·
1s skills[i]≤2*10^3```I am trying to do this problem with top down approach, but I cant apply any optimizations without it TLEing
I know you can do bottom up and apply few optimizations, but with states of index and current K, for top down, can anyone do it in top down with the constraints given
modern gulch
Also, is there any good roadmap for getting better at DSA, what kind of problems...
Besides doing problems: researching methods in depth. Like, don’t just do a leetcode problem and go to the next: go read about the algorithm and variations on the algorithm. Read other solutions and understand why they work. Etc. Serious thought.. extended thought… is how you get better at problem solving
fiery cosmos
I solved problem of transfering number to binary even I don't really know why it works
class Solution:
def decimal_to_binary(self, decimal):
if decimal == 0:
return 0
return decimal % 2 + (10 * self.decimal_to_binary(decimal // 2))
What makes it confusing for me is that function call is multiplied by 10, can somebody explains how recursion function in this example?
modern gulch
I solved problem of transfering number to binary even I don't really know why it...
What does the function return for decimal 1? Can you tell me why?
Or if you’d like a visual explanation: https://www.recursionvisualizer.com
fiery cosmos
It will not be 0 because it is 1 at start, so it will go at function call and 1 % 2 is 1 and then it will be 1 + ( 10 * 0) so it will be 1
modern gulch
Ok, now do the same for 2
Basically, it keeps taking the mod of the value until it gets to 0
It’d be a little easier to follow, perhaps, with divmod
modern gulch
You have to call the function
fiery cosmos
@modern gulch this part is confusing to me 10 * decimal_to_binary(decimal // 2)
like how is number multiplied with function call
this is graph that I got
fiery cosmos
Yes
modern gulch
That lowest level is the most significant bit, agree?
(The first digit)
So, they’re bastardizing the decimal system here: they’re using a decimal representation of a binary number: multiplying the lowest by 10
The result is a decimal integer whose string representation is the binary representation of the decimal input
Multiply by 10 is like a bit shift: it shifts the most significant bits left
fiery cosmos
I understand that in the last step it will be returned 0, to self.decimal_to_binary(decimal // 2) so then it will be 0 % 2 + (10 * 0)
But don't understand what is then done
hmm, I think I understand
modern gulch
I’d just start with 1,2,3,4… it makes sense but you kinda have to work it through
The multiply by 10 is somewhat weird because that’s a decimal hack. Should probably be constructing a string directly
fiery cosmos
I understand that in the last step it will be returned 0, to `self.decimal_to_bi...
So in the end 0 will be returned so it will be 0 % 2 + (10 * 0), then it will be 1 % 0 + (10 * 0), then it will be (2 % 2) + (10 * 1) which is 10, then it will be 5 % 2 = 1 + (10 * 10) so it is 101
Yeah I understand I just needed to understand how that returning functions and that in the call stack it is remembered what value is of decimal
cobalt mirage
```py
A test needs to be prepared on the SAT platform with questions from differ...
@regal spoke @haughty mountain any thoughts?
unreal summit
Hello everyone! I come with a plea of help. I'm trying class inheritance and overriding the init function like this:
class Base:
def __init__(self, value, printed):
self.value = value
self.printed = printed
def print_class(self):
print(f"{self.printed}: {self.value}")
class One(Base):
def __init__(self, value):
super(Base, self).__init__(value=value, printed="One")
class Two(Base):
def __init__(self, value):
super(Base, self).__init__(value=value, printed="Two")
The code is executed as follows:
one = One(1)
two = Two(2)
one.print_class()
two.print_class()
I'm getting the following error and I have no idea why: TypeError: object.__init__() takes exactly one argument (the instance to initialize)
fiery cosmos
Hello everyone! I come with a plea of help. I'm trying class inheritance and ove...
hi
super doesnt take arguments
remove the Base and self in the super
and it will work
unreal summit
and it will work
Thanks, I did that and it worked :/ used to work back in 3.6 haha guess that's something that didn't keep up
fiery cosmos
yeah :)
regal spoke
Hello everyone! I come with a plea of help. I'm trying class inheritance and ove...
Your bug is that you have super(Base, self), you can use either super() or super(One, self).
class One(Base):
def __init__(self, value):
super(One, self).__init__(value=value, printed="One")
It technically can take arguements. But it needs to be the right One 😄
fiery cosmos
It technically can take arguements. But it needs to be the right One 😄
what arguments can it take
regal spoke
what arguments can it take
See the code that I just posted
uncut sleet
regal spoke
does it take classes as arguments?
Yes. You can do either super() or super(my_class, self)
The idea is that all objects in Python have an ordered list called mro of all the classes that the object inherits from (either directly or indirect). Essentially whatsuper(my_class, self) does is that it returns the class that comes directly after my_class in self.mro.
In Python2 you had to use super(my_class, self), but starting from Python3 they added the sugar syntax super(). But you can still use the old super(my_class, self) syntax in Python3.
Here is a funny and wonky example that shows what I'm talking about
halcyon plankBOT
@regal spoke :white_check_mark: Your 3.11 eval job has completed with return code 0.
001 | C
002 | B
003 | A
!e
class A:
def draw(self):
print("A")
super().draw()
class B:
def draw(self):
print("B")
class C(A, B):
def draw(self):
print("C")
super().draw()
c = C()
c.draw()
@regal spoke :white_check_mark: Your 3.11 eval job has completed with return code 0.
001 | C
002 | A
003 | B
What is happening here is that c.mro is [C, A, B, object]. This means that the super().draw() in C calls A.draw(self) since A is the next class after C in self.mro. Then super().draw() in A calls B.draw(self) since B is the next class in self.mro after À.
So think of super() as the next class in line.
regal spoke
Hello everyone! I come with a plea of help. I'm trying class inheritance and ove...
Comming back to this.
The mro of one is [One, Base, object] and the mro of two is [Two, Base, object].
Calling super(Base, self).__init__ will call init for the next class in line, which is object. That is why the error message is TypeError: object.__init__() takes exactly one argument (the instance to initialize)
!e
class A:
def __init__(self):
super().__init__('One')
#super(A, self).__init__('One')
#object.__init__(self, 'One')
a = A()
@regal spoke :x: Your 3.11 eval job has completed with return code 1.
001 | Traceback (most recent call last):
002 | File "/home/main.py", line 6, in <module>
003 | a = A()
004 | ^^^
005 | File "/home/main.py", line 3, in __init__
006 | super().__init__('One')
007 | TypeError: object.__init__() takes exactly one argument (the instance to initialize)
!e
class A:
def __init__(self):
#super().__init__('One')
super(A, self).__init__('One')
#object.__init__(self, 'One')
a = A()
@regal spoke :x: Your 3.11 eval job has completed with return code 1.
001 | Traceback (most recent call last):
002 | File "/home/main.py", line 6, in <module>
003 | a = A()
004 | ^^^
005 | File "/home/main.py", line 4, in __init__
006 | super(A, self).__init__('One')
007 | TypeError: object.__init__() takes exactly one argument (the instance to initialize)
!e
class A:
def __init__(self):
#super().__init__('One')
#super(A, self).__init__('One')
object.__init__(self, 'One')
a = A()
@regal spoke :x: Your 3.11 eval job has completed with return code 1.
001 | Traceback (most recent call last):
002 | File "/home/main.py", line 6, in <module>
003 | a = A()
004 | ^^^
005 | File "/home/main.py", line 5, in __init__
006 | object.__init__(self, 'One')
007 | TypeError: object.__init__() takes exactly one argument (the instance to initialize)
thank you @regal spoke
paper lotus
How is ^VIX being calculated as having only a 0.0272 correlation with VIXCLSx
solemn moss
A connected undirected graph of size n (<= 2e5) is given. Need to find some simple path, that if we remove all its vertices (and their edges) from the graph we will get two graphs with equal sizes.
It's guaranteed that an answer exists.
Any ideas?
Examples:
(first line is n, m; next lines are m edges; output is the path)
3 2
3 1
2 1
1
7 7
1 2
2 3
4 2
2 5
4 5
6 7
7 2
1 2 4
equal sizes - that is? same amount of vertices?
solemn moss
equal sizes - that is? same amount of vertices?
ye
regal spoke
A connected undirected graph of size `n (<= 2e5)` is given. Need to find some si...
Is this a problem you came up with or is this an actual problem from somewhere?
solemn moss
Is this a problem you came up with or is this an actual problem from somewhere?
an actual problem
regal spoke
an actual problem
From where?
To me this looks like someone took a NP-hard problem and slapped a n <= 2e5 constraint on it
But atm I dont have any argument that it is NP-hard
solemn moss
From where?
algorithms course
actually we will have analysis anyways, so I don't really need the answer
regal spoke
regal spoke
A connected undirected graph of size `n (<= 2e5)` is given. Need to find some si...
Are you sure that this is the correct statement?
Also do the resulting two graphs need to be connected?
What is the limit on m?
The limit on n doesn't really matter, it is m that matters
If for example the problem was about trees and not general graphs. Then I could definitely belive there exists some linear solution
solemn moss
Maybe I understood it wrong.. I gonna send google translation
The mole is a small frail animal...
Translator's note
Not long ago, a family of moles decided to dig a new network of tunnels underground. The network plan, which has already been developed, consists of underground rooms and tunnels that connect them. Formally, a network plan is an undirected connected graph. Mole Mother wants to use the job as an opportunity to teach her two mole children how to properly dig a network of tunnels.
As an initial quick demonstration, the little mother is going to dig a few rooms and tunnels that form a simple path in the network plan graph. After that, she will divide the remaining rooms between her two children so that each child gets an equal number of rooms, otherwise they may get upset (you don't have to worry about tunnels, because they are much easier to dig). Children can work in any of their rooms in any order they want.
Since children have no experience in digging a network of tunnels, the little mother realized one problem: if there is a tunnel in the plan between a certain pair of rooms that belong to different children, then there is a risk of an accident while digging this tunnel.
Help the baby mother decide which path to use for the initial demonstration, and how to divide the remaining rooms equally so that there are no pairs of rooms assigned to different children connected by a tunnel. The initial path must contain at least one room and must not visit any room twice.
The first line contains two integers c and t (1≤c≤2e5, 0≤t≤2e5) — the number of rooms and tunnels in the plan.
Each of the next t lines contains two integers a and b (1 ≤ a, b ≤ c, a≠b) — the numbers of rooms connected by a tunnel.
The rooms are numbered from 1 to c. There is at most one tunnel between each pair of rooms. There is a path between any pair of rooms.
regal spoke
🤷♂️
"you don't have to worry about tunnels"
"then there is a risk of an accident while digging this tunnel"
I don't understand why it talks about "Children can work in any of their rooms in any order they want."
Is that relevant somehow?
outer rain
It might be just to tell that even though mother must dig in a simple path, children do not, so you don't have to worry about it (otherwise it would 100% be NP hard problem)
regal spoke
It honestly still sounds like an NP hard problem to me
outer rain
idk, I am not convinced
regal spoke
Or at very least not a problem with a linear solution
outer rain
I tried to reduced it to hamiltonian path, but it is always "either you find hamilton, or solve the problem for less vertices", I couldn't come up with a proper reduction... It may be NP-hard, I have no idea how to show it though. The equal number of vertices in the cut is a very weird constraint. I do agree that this doesn't seem linear, but I am not conviced in this either.
I am scared that it does not seem to be solvable with flows
regal spoke
Even if it was solvable by flows (which I kinda doubt) it wouldnt be linear
Well
I guess there are linear flows nowdays
outer rain
ik, ik, but that's a good polynomial to start
(also time complexity of O(n^6 m^2 log n) looks sick and no one can deny it 👺)
regal spoke
One idea I have is to create a spanning tree with a dfs, and then pick the diameter of that tree as the simple path
Not sure if that will always work out or not
But it works on some tiny graphs that I tried it on
solemn moss
Mhm.. it actually might work.. I got TL 5 for now but that's just some mistake in implementation i guess, will fix tomorow
vernal girder
import numpy as np
import matplotlib.pyplot as plt
# Define a list of line segments, each represented by a tuple of two points
good_area = [((0.5, 0.5), (-0.5, 0.5)), ((-0.5, 0.5), (-0.5, -0.5)), ((-0.5, -0.5), (0.5, -0.5)), ((0.5, -0.5), (0.5, 0.5))]
segments = [((-0.5, 0.5), (-0.2887, 0)), ((-0.5, -0.5), (-0.2887, 0)), ((0.5, -0.5), (0.2887, 0))]
def get_area_bounds(point1, point2):
m_values = np.array([-1, 1])
lower_b_values = []
upper_b_values = []
# Calculate the b values for each m
for m in m_values:
# Calculate the slope and intercept for the line y = mx + b
slope = m
lower_b_values.append(point1[1] - slope * point1[0])
upper_b_values.append(point2[1] - slope * point2[0])
return m_values, lower_b_values, upper_b_values
def flip(segments):
flipped_segments = []
for segment in segments:
flipped_segment = tuple([(point[1], point[0]) for point in segment])
flipped_segments.append(flipped_segment)
return flipped_segments
flipped_segments = flip(segments)
flipped_good_area = flip(good_area)
# Create two separate plots using subplots
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 6))
# Plot the original segments in the first plot
for i, good_line in enumerate(good_area):
m_values, lower_b_values, upper_b_values = get_area_bounds(good_line[0], good_line[1])
ax1.fill_between(m_values, lower_b_values, upper_b_values, color='gray', alpha=0.5, label=f'Shaded Region {i+1}')
for i, segment in enumerate(segments):
m_values, lower_b_values, upper_b_values = get_area_bounds(segment[0], segment[1])
ax1.fill_between(m_values, lower_b_values, upper_b_values, color='blue', alpha=0.5, label=f'Shaded Region {i+1}')
ax1.set_xlabel('m')
ax1.set_ylabel('b')
ax1.set_title('Original Segments')
ax1.grid(True)
# Plot the flipped segments in the second plot
for i, flipped_good_line in enumerate(flip(good_area)):
m_values, lower_b_values, upper_b_values = get_area_bounds(flipped_good_line[0], flipped_good_line[1])
ax2.fill_between(m_values, lower_b_values, upper_b_values, color='gray', alpha=0.5, label=f'Flipped Shaded Region {i+1}')
for i, flipped_segment in enumerate(flip(segments)):
m_values, lower_b_values, upper_b_values = get_area_bounds(flipped_segment[0], flipped_segment[1])
ax2.fill_between(m_values, lower_b_values, upper_b_values, color='red', alpha=0.5, label=f'Flipped Shaded Region {i+1}')
ax2.set_xlabel('m')
ax2.set_ylabel('b')
ax2.set_title('Flipped Segments')
ax2.grid(True)
plt.tight_layout()
plt.show()
Yo, wanna help me out here? Trying to find the area of the gray in each graph when not counting the blue or red areas covering it
regal spoke
Got no clue what this is about
vernal girder
the plotting is mainly just for visuals, mostly just wanting the number on its own
that would take a bit of explaining lol
this is an algorithm to test if a set of line segments is an opaque set of a polygon, id have to explain it in vc for any more details
vernal girder
Got no clue what this is about
heres the wikipedia article if ur curious:
green arch
hey guys I'm doing an assignment that pertains to linked lsits but the structures are very weird
like the lecture notes. So every node contains
a pointer and information about what is contained in the node
so like
Class Node
def __init__(self: data, pointer):
self.data = data
self.pointer = pointer ```coding in discord not an IDE so forgive the syntax if incorrect
how exactly does a pointer point to another node?
like do i assign each pointer as an integer?
Also, it seems to be that Null isn't a value that exists in python
and since 20 comes after 19. if I had pointer 19, do I compare the value of the integers in pointer to determine what is coming next?
sorry if noob question
I am new to DSA
Also, what happens if we are at the end of a linked list? would this indicate the list is over and there is no pointer?
so instead of a value it should be null, but then how does the previous item before that understand that it is the final value in the linked list if there is Null value of next pointer?
or would the logic indicate, that if there is an item behind it, and a null in front of it, then it is a final item?
vernal girder
Also, it seems to be that Null isn't a value that exists in python
I think python uses None instead of Null
dont know the rest tho lol
soft hawk
```py
import numpy as np
import matplotlib.pyplot as plt
# Define a list of lin...
what are you trying to do here?
vernal girder
what are you trying to do here?
If u run it, you'll see two plots. one has gray and blue, the other has grey and red. I am trying to find the total area of the gray sections in each graph which is not covered by blue or red
my goal is to do this without relying on the graphs; i dont need to be graphing it each time. One thing i want to use it for is neural network fitness, so finding the remaining gray area without needing to graph it would be very preferable
soft hawk
my goal is to do this without relying on the graphs; i dont need to be graphing ...
Cool, do you need any help with it?
vernal girder
Cool, do you need any help with it?
Id definitely appreciate it!
soft hawk
Id definitely appreciate it!
k, i'd like to help, is this the full file? #algos-and-data-structs message
vernal girder
k, i'd like to help, is this the full file? https://discord.com/channels/2676243...
yup. I have a revised version that gets rid of some unnecessary code, lemme grab it rq
vernal girder
import numpy as np
import matplotlib.pyplot as plt
M_VALUES = np.array([-1, 1])
# Define a list of line segments, each represented by a tuple of two points
good_area = [((0.5, 0.5), (-0.5, 0.5)), ((-0.5, 0.5), (-0.5, -0.5)), ((-0.5, -0.5), (0.5, -0.5)), ((0.5, -0.5), (0.5, 0.5))]
segments = [((-0.5, 0.5), (-0.2887, 0)), ((-0.5, -0.5), (-0.2887, 0)), ((0.5, -0.5), (0.2887, 0))]
def get_area_bounds(point1, point2):
lower_b_values = []
upper_b_values = []
# Calculate the b values for each m
for m in M_VALUES:
# Calculate the slope and intercept for the line y = mx + b
slope = m
lower_b_values.append(point1[1] - slope * point1[0])
upper_b_values.append(point2[1] - slope * point2[0])
return lower_b_values, upper_b_values
def flip(segments):
flipped_segments = []
for segment in segments:
flipped_segment = tuple([(point[1], point[0]) for point in segment])
flipped_segments.append(flipped_segment)
return flipped_segments
flipped_segments = flip(segments)
flipped_good_area = flip(good_area)
# Create two separate plots using subplots
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 6))
# Plot the original segments in the first plot
for i, good_line in enumerate(good_area):
lower_b_values, upper_b_values = get_area_bounds(good_line[0], good_line[1])
ax1.fill_between(M_VALUES, lower_b_values, upper_b_values, color='gray', alpha=0.5, label=f'Shaded Region {i+1}')
for i, segment in enumerate(segments):
lower_b_values, upper_b_values = get_area_bounds(segment[0], segment[1])
ax1.fill_between(M_VALUES, lower_b_values, upper_b_values, color='blue', alpha=0.5, label=f'Shaded Region {i+1}')
ax1.set_xlabel('m')
ax1.set_ylabel('b')
ax1.set_title('Original Segments')
ax1.grid(True)
# Plot the flipped segments in the second plot
for i, flipped_good_line in enumerate(flip(good_area)):
lower_b_values, upper_b_values = get_area_bounds(flipped_good_line[0], flipped_good_line[1])
ax2.fill_between(M_VALUES, lower_b_values, upper_b_values, color='gray', alpha=0.5, label=f'Flipped Shaded Region {i+1}')
for i, flipped_segment in enumerate(flip(segments)):
lower_b_values, upper_b_values = get_area_bounds(flipped_segment[0], flipped_segment[1])
ax2.fill_between(M_VALUES, lower_b_values, upper_b_values, color='red', alpha=0.5, label=f'Flipped Shaded Region {i+1}')
ax2.set_xlabel('m')
ax2.set_ylabel('b')
ax2.set_title('Flipped Segments')
ax2.grid(True)
plt.tight_layout()
plt.show()
k thanks
soft hawk
^ alr here it is. im good for vc too if u need anything
sure
vernal girder
vc0 or vc1?
soft hawk
1
vernal girder
👍🏻
soft hawk
it says i dont have permission
yeah i can hear you @vernal girder
wanna vc outside the server?
vernal girder
U give me a call 👌🏻
fiery cosmos
@fiery cosmos hi
fiery cosmos
<@456226577798135808> hi
hi man
narrow mica
so like
```py
Class Node
def __init__(self: data, pointer):
self.d...
Though there's no Null, there is None. So at the end, you can just have pointer be None.
Also, why self: data? self should just be a reference to itself, which is of class Node. I think you meant self, data, ...?
Thus you could have something like this
class Node
def __init__(self, data, next_node = None):
self.data = data
self.next_node = next_node
```To use this class, you can do something like
```py
head = Node('apple')
current = Node('orange')
head.next_node = current
Which isn't the easiest to use, so you can change it a bit, say for example
class Node
def __init__(self, data, prev_node = None):
self.data = data
self.next_node = None
if prev_node is not None:
prev_node.next_node = self
head = Node('apple')
current = Node('orange', head)
current = Node('lemon', current)
split sigil
!ban 1151689749124354048 trading spam
halcyon plankBOT
:incoming_envelope: :ok_hand: applied ban to @burnt frost permanently.
molten vigil
Is it possible to set datetime.datetime.now() precision to seconds?
haughty mountain
Is it possible to set `datetime.datetime.now()` precision to seconds?
something like
datetime.datetime.now().replace(microsecond=0)
thanks! :)
fiery cosmos
stuck in a simple data structures problem from hacker rank
i think you just need to post the problem, your try and what are you struggle in
fiery cosmos
i think you just need to post the problem, your try and what are you struggle in
I solved the problem just by rearranging the right side of assignment
Which was taking three lines
There were 7 variables on the right side
Could be some syntax problem idk
solemn moss
One idea I have is to create a spanning tree with a dfs, and then pick the diame...
That didn't really work.
But the starting idea is the same, thinking about it as a tree
Here is solution if you are interested https://pastebin.com/TwVEHXaT
regal spoke
That didn't really work.
But the starting idea is the same, thinking about it as...
Ye I realized that what I said wouldnt work. Earlier today I came up with this counter example
regal spoke
That didn't really work.
But the starting idea is the same, thinking about it as...
Do you have a proof of why this solution works?
Oh is it that a node with used = 0 can never be in contact with a node with used = 2?
solemn moss
Do you have a proof of why this solution works?
So, we are splitting graph with dfs into not visited (let's say A), current processing and already visited (let's say B).
We choose current processing as the path, and others two as the rooms for moles
Because |A| = 0 and |B| = n, and they are changing only by 1 in one time, they will sometimes be equal
And as you already wrote, used = 0 can't be in contact with used 2 (because they would be processed together then)
molten vigil
Is it possible to check if dataclass has an attribute without actually creating the object, purely by its type, and without setting default values to attributes? for example hasattr(Book, is_published), Book is a type not an object and I would like this to return True
regal spoke
So, we are splitting graph with dfs into not visited (let's say `A`), current pr...
Thats really cool
I've never seen this before
Hmm if you apply this recursively, you get a really cool path decomposition algorithm of a graph
A bit reminiscent of heavy light decomposition for trees
Do you know if this has a name?
next yarrow
someone pls help
You might be missing some "." s on line 61 and line 64
next yarrow
someone pls help
Also, make sure each if/elif/else statement returns the same type of information.
regal spoke
It really looks like the code on the right would return false for Wwm2. So that error message should be impossible
Did you forget to press submit?
next yarrow
dang yah i did forget the period. but now it is giving me this
The first part needs to be lowercase to get a True. You entered "Wmw2"
If any part of the string is not lowercase it will skip tje first two checks and return False
Actually, just reread that, I agree with pajenegod! It should return False, I misread the error
solemn moss
That code always returns True
because the methods aren't called
!e
print("TEST".islower)
if "TEST".islower:
print("lol")
@solemn moss :white_check_mark: Your 3.11 eval job has completed with return code 0.
001 | <built-in method islower of str object at 0x7f08fbceaa30>
002 | lol
solemn turret
hey, anyone know
solemn turret
anyone knos a good machine learning algorithm for a tyre degradation prediction model? the feature is you input the compound and the tyre lap and it should give the expected time
btw im getting this error ```py
import pandas as pd
from sklearn.tree import DecisionTreeClassifier
from sklearn.linear_model import LinearRegression
from sklearn.metrics import accuracy_score
import joblib
tyre_data = pd.read_csv("tyredeg.csv")
X = tyre_data.drop(columns=["LapTimeSeconds"])
y = tyre_data["LapTimeSeconds"]
model = LinearRegression
model.fit(X, y)
tyre_data
```AttributeError: 'DataFrame' object has no attribute '_validate_params'```The model instantiation doesn't look correct. Maybe try:
model = LinearRegression()
ohh yh, ur true
and how do i cap the value of X
so i cant make predictions of more X than 2
lyric walrus
dang yah i did forget the period. but now it is giving me this
What platform is this?
Algoexpert?
solemn turret
hey guys, which algorithm do you think it suits the most this model. it is a model which predicts the time in a specific circuit due to tyre degradation with inputs: compound, laps with tyre, laps in race
I have used linear regression and I wnat to test something else
solemn turret
The model instantiation doesn't look correct. Maybe try:
```
model = LinearRegr...
plesae help me
outer rain
So, we are splitting graph with dfs into not visited (let's say `A`), current pr...
This is a very cool idea. I like how it checks how spoiled you are in terms of algorithm knowledge lmao.
naive oak
can shunting yard be modified to be used for parsing implicit multiplication like 3(x+2)^2 being 3*((x+2)^2) or should i look into another parsing method?
haughty mountain
can shunting yard be modified to be used for parsing implicit multiplication lik...
I don't see why that wouldn't work
it's just another rule to add
haughty mountain
if you encounter a ( with a digit before it while parsing you should be able to just insert as you go
though I guess canonicalizing the expression beforehand is another option
naive oak
if you encounter a ( with a digit before it while parsing you should be able to ...
shunting yard usually doesn't keep track of previous tokens tho does it?
regal spoke
This is a very cool idea. I like how it checks how spoiled you are in terms of a...
Btw I found the problem. It's from nwerc 2020 https://open.kattis.com/problems/jointexcavation
haughty mountain
shunting yard usually doesn't keep track of previous tokens tho does it?
right, it's an easy extension you can allow
being able to check the previous token
sleek hearth
I need help with networkx on finding the shortest path that includes all nodes in a circular loop that may form in a path
I want the shortest_path function to treat graphs like the one above like this:
outer rain
I need help with networkx on finding the shortest path that includes all nodes i...
you want to create vertices while looking for a path? what?
sleek hearth
you want to create vertices while looking for a path? what?
I don't want nodes 5,6,7 to be omitted because 7 leads to 4 again.
outer rain
I don't want nodes 5,6,7 to be omitted because 7 leads to 4 again.
I still don't get it. Do you want to include every loop?
sleek hearth
I still don't get it. Do you want to include every loop?
Yeah, if the loop is caused by repetition of a node multiple times, like how 4 repeats twice in the above image
outer rain
wdym "the loop is caused by repetition of a node multiple times"?
sleek hearth
Like how 4,5,6,7 appear to be in a loop because 7 goes to 4. I should have mentioned that I am considering 1 and 8 as source and target nodes
outer rain
Like how 4,5,6,7 appear to be in a loop because 7 goes to 4. I should have menti...
still don't get it. Yeah, 4, 5, 6, 7 form a loop. Why do you want to include it in the path?
sleek hearth
Well in my code each node is a word, think of 4 like "you" and the digraph of all the 8 nodes as a sentence. You repeats twice in the sentence, so when I use shortest_path every word between the two instances of you is omitted
outer rain
I think the order will be ambigiuos no matter what
what if you have another cycle, like (4, 6). Where do you go first? (4, 5, 6, 7) or (4, 6)?
sleek hearth
what if you have another cycle, like (4, 6). Where do you go first? (4, 5, 6, 7)...
I am finding it hard to visualise that.. Could the code work if it searched for 2nd or 3rd shortest path instead?
outer rain
I am finding it hard to visualise that.. Could the code work if it searched for ...
It can, or it can not. If there is no cycles, there is only one path, for instance. If there are two loops, you 3rd path.
it's the path that visits every edge
but it does not guarantee the order of vertices
outer rain
what if you have another cycle, like (4, 6). Where do you go first? (4, 5, 6, 7)...
so it may give strange results in situations like this one
outer rain
that's not simple, and I am unsure if it is even in the networkx
the problem is that you don't understand your problem domain properly
the explanation you gave is ambigious
sleek hearth
If duplicates were allowed, shortest_path would get it done
outer rain
If duplicates were allowed, shortest_path would get it done
wdym?
sleek hearth
wdym?
Cause there wouldn't be loops then
My code has nothing to do with graphs, but I am not finding a function like shortest_path anywhere else
outer rain
My code has nothing to do with graphs, but I am not finding a function like shor...
you have a sentence, right? why can't you extract the order from it directly?
each word correspond to a vertex, the order of vertices form a path
outer rain
My code has nothing to do with graphs, but I am not finding a function like shor...
but I am not finding a function like shortest_path anywhere else
because you don't know what you are looking for. You need a more formal description of the problem to find the right algorithm.
sleek hearth
> but I am not finding a function like shortest_path anywhere else
because you ...
I know what I am looking for. I want a function like shortest_path that doesn't negate loops caused by multiple instances of a node. I don't know how to build a function to do that, and nobody else has built it because I am doing something new.
outer rain
I know what I am looking for. I want a function like shortest_path that doesn't ...
I think your problem can be solved with euler paths, but I still don't understand it well enough to say for sure.
sleek hearth
I think your problem can be solved with euler paths, but I still don't understan...
Should I explain my code to you?
outer rain
Have you already solved your problem? If you haven't, I won't understand what problem are you trying to solve in the first place 😦
haughty mountain
understanding the problem itself is probably more important at this stage
e.g. what should happen in the case mentioned above
sleek hearth
what do you expect from this graph
We should assign words to the nodes and the edges would be based on what word precedes and succedes what word
outer rain
"What are you trying are things which are hard"
Let me clarify what happens here: transition from sentence to a graph is lossy. If your nodes are unlabelled, you can build a path (1, 2, 3, 4, 2, 5, 6, 2, 7) or (1, 2, 5, 6, 2, 3, 4, 2, 7). What's two different paths.
sleek hearth
So if I take what(1) and hard(7) as source and target nodes, then how would I get a meaningful path including the loops made due to are(2) instead of just 'what are hard'
outer rain
So if I take what(1) and hard(7) as source and target nodes, then how would I g...
There are two paths (see prev message), do you want a specific one or just any?
sleek hearth
I don't understand. The shortest path would be (1,2,7) right?
outer rain
right
sleek hearth
Ok I think I understand.. 2 could go to 3(which gives the correct sentence) or 2 goes to 5(which gives half gibberish). That's alright. I just want to avoid the shortest path for now.
outer rain
Ok I think I understand.. 2 could go to 3(which gives the correct sentence) or 2...
Your problem has nothing to do with a shortest paths it seems to me
Please answer this: why can't you use the sentence to get the path? As I said, sentence -> graph is lossy. It is very simple to get the path (the unambiguous and real one!) from the sentence. Why can't you do this?
sleek hearth
I would have to explain my entire code and what I am trying to do here, I would answer if you have the time
outer rain
so that's just out of question, right? You are absolutely sure this is not possible?
sleek hearth
uhh what's not possible?
outer rain
Using the sentence to build the path
sleek hearth
The sentence is taken from the path.
outer rain
it is very weird if you can't do this btw
outer rain
The sentence is taken from the path.
ok, so you are given the graph, and no sentence?
sleek hearth
Initially I don't have both of those
I have a list of word pairs
I should tell you the entire code from the start
haughty mountain
fwiw this kinda screams markov chain
outer rain
(I don't see any)
sleek hearth
I need to go. Can I DM any of you later? @haughty mountain @outer rain
outer rain
I need to go. Can I DM any of you later? <@133944101929222144> <@284257720406638...
Please ping me in this channel instead
haughty mountain
(I don't see any)
generating sentences based on word transition probabilities
sleek hearth
generating sentences based on word transition probabilities
Yeah that's a better way to say it
outer rain
ah, like the most realistic sentence based on statistical data?
haughty mountain
not necessarily the most realistic
but somewhat realistic
markov chain text generators was all the rage many years back
(terrible compared to the language models of today if you want sensible text)
vernal girder
^ my program to test opaque sets is finished! time to build a neural network to generate good line segments
fiery cosmos
that sounds so cool :0
steel python
Hey 👋 Good morning y'all
craggy delta
Hey 👋 Good morning y'all
Hi
haughty mountain
https://paste.pythondiscord.com/3COA
what even is area supposed to be?
if I do no segments at all I see a printed area of 3
for what I assume is a unit square
vernal girder
the area is that of the gray bit on screen
the grey area is a graph of ranges of m (x axis) and b (y axis) for which the line y = mx + b passes through the unit square
haughty mountain
(fwiw, I can't really check the plots atm)
but getting an area of 3 for a unit square seems...interesting
vernal girder
but getting an area of 3 for a unit square seems...interesting
because it isnt measuring the area of a unit square
its kinda dense to explain, sorry about that lol
haughty mountain
the grey area is a graph of ranges of m (x axis) and b (y axis) for which the li...
for the case with no segments won't that be true for at least all m and -0.5≤b≤0.5
so infinite area