#algos-and-data-structs

1 messages Β· Page 27 of 1

snow anvil
# 
class Solution(object):
    def isIsomorphic(self, s, t):
        s_List = []
        t_List = []
        bool = 0
        for i in range(len(s)):
            a, b = s[i], t[i]
            for j in range(len(s)):
                c, d = s[j], t[j]
                if (a == c and not b == d) or (b == d and not a == c):
                    bool = 0
                    return bool
                else:
                    bool = 1
        return bool

this was me half a year ago

#

damn I haven't actually done any mediums yet πŸ’€

#

let me think about this one
I'm a slow person so it might take a bit

agile sundial
#

oh this is pretty straightforward

#

||sort, keep track of the max/min between right and left between adding or subtracting||

snow anvil
#

No spoilers

#

Thanks

agile sundial
#

well i haven't written it yet, but that should work

crude galleon
#

thanks for the help guys, while just a really tiny thing I think this whole struggle helped changing my perspective to be more correct

#

instead of being like "ah it's a for loop, must be O(n)"

snow anvil
#

oh this has a very easy mathematical solution I think

agile sundial
#

passed

#

it's just a medium...

snow anvil
#

I like this problem πŸ˜„
I'll try to get a good solution down
I had other things I still wanted to do today but this is more funny

agile sundial
#

wait till you find out about dp 😳

#

πŸ€”

dusky trellis
#

do I want to know what dp is?

haughty mountain
#

I wouldn't call it greedy

#

what choice is happening?

agile sundial
#

it's kinda just linear search πŸ€”

haughty mountain
#

you can just keep track of the min and max

#

the solution that sorts and sweeps is not greedy

#

there are no choices being made

#

the insight is that if I +k on value x I also want to +k on all values <= x

#

similar for -k on the other side

#

so you +k small values and -k large values

#

the only question is where the transition should be

#

and the solution tries all possibilities

#

doing greedy problems if you know there exists a greedy solution is pretty weird, the hard part is actually showing that some choice is always optimal

#

have you looked at some classical greedy problems and how you prove the correctness of the strategies?

#

if not then you might want to do that

agile sundial
haughty mountain
#

you tend to prove that given an optimal solution you can swap out steps to be greedy, while still being optimal

#

and after swapping out enough steps you have a greedy solution, still optimal

agile sundial
#

no lol

haughty mountain
#

the idea is basic

agile sundial
#

clrs calls it the "cut and paste" method

haughty mountain
#

say an optimal does steps
a, b, c, d, ...
what if you can make a greedy choice as a first step (let's make them uppercase letters) and still have a valid solution
A, b, c, d, ...
and what if you can show that this is not worse than the optimal solution

#

if you can show that you can repeat the process and make
A, B, c, d, ...
A, B, C, d, ...
and so on

#

and at the end you have replaced the whole optimal solution with a greedy one, and your solution never got worse by adding the greedy choices

#

so it's optimal

#

e.g. look at unweighted interval scheduling

#

replacing an interval by another valid interval that ends earlier can only make the solution better (or equally good), never worse

shut pasture
#

Anyone here to give a source code for creating a registration form from tkinter?

calm kindle
# shut pasture Anyone here to give a source code for creating a registration form from tkinter?

From ChatGPT import tkinter as tk

def register():
# Retrieve data from user inputs
username = username_entry.get()
password = password_entry.get()
email = email_entry.get()

# Print user inputs to console (for testing purposes)
print(f"Username: {username}")
print(f"Password: {password}")
print(f"Email: {email}")

# Clear input fields
username_entry.delete(0, tk.END)
password_entry.delete(0, tk.END)
email_entry.delete(0, tk.END)

Create a new tkinter window

window = tk.Tk()

Set window title

window.title("Registration Form")

Create label for username input

username_label = tk.Label(window, text="Username:")
username_label.pack()

Create entry field for username input

username_entry = tk.Entry(window)
username_entry.pack()

Create label for password input

password_label = tk.Label(window, text="Password:")
password_label.pack()

Create entry field for password input (set show='*' to hide characters)

password_entry = tk.Entry(window, show='*')
password_entry.pack()

Create label for email input

email_label = tk.Label(window, text="Email:")
email_label.pack()

Create entry field for email input

email_entry = tk.Entry(window)
email_entry.pack()

Create button to submit registration form

submit_button = tk.Button(window, text="Register", command=register)
submit_button.pack()

Run tkinter event loop

window.mainloop()

severe lance
naive oak
#

when implementing backtracking do you use a mutable object or pass around immutable ones/copies?

#

my intuition says the former but idk how it's usually implemented so

outer rain
#

I do the former

#

it usually faster, but not as convenient to use

#

the resulting structure is a similar to a linked-list and you have to traverse it... not nice, but doable

outer rain
#

like in bfs or like in dfs?

naive oak
#

dfs

outer rain
naive oak
#

mutable stack?

outer rain
# 
def dfs(v, path=[]):
    used[v] = True
    for u in graph[v]:
        if not used[u]:
            path.append(u)
            dfs(u)
            path.pop()
naive oak
#

ah gotcha

outer rain
#

Or, alternatively, you can have a back array and store parents in it.

def dfs(v):
    used[v] = True
    for u in graph[v]:
        if not used[u]:
            back[u] = v
            dfs(u)

And the path from start to u would be [..., back[back[u]], back[u], u]. You will have to traverse back as a linked list to extract it. It's a slightly more powerful method though because it gives you more information. Not just for one path, but for every single path you have traversed.

naive oak
#

backtracking is simpler than i thought

halcyon plankBOT
#

:incoming_envelope: :ok_hand: applied mute to @tiny nimbus until <t:1677240651:f> (10 minutes) (reason: duplicates rule: sent 4 duplicated messages in 10s).

The <@&831776746206265384> have been alerted for review.

haughty mountain
brave mortar
#

Any algorithm expert online?

#

I need some help with understanding a question

naive oak
#

just ask your question

#

it saves the delay of someone replying and then having to wait for you to send the question and then you have to wait for them to reply again

brave mortar
#

Yeah I can't post the question here

#

Otherwise I would have

#

Is it okay if I DM?

#

I don't need solution or anything. Just want to understand if I am interpreting it the right way

quaint perch
#

why is the excess space complexity of dynamic arrays Θ(n)
https://en.m.wikipedia.org/wiki/Dynamic_array

Dynamic array

In computer science, a dynamic array, growable array, resizable array, dynamic table, mutable array, or array list is a random access, variable-size list data structure that allows elements to be added or removed. It is supplied with standard libraries in many modern mainstream programming languages. Dynamic arrays overcome a limit of static arr...

quaint perch
outer rain
# quaint perch why is the excess space complexity of dynamic arrays Θ(n) https://en.m.wikipedia...

It's excess space is Θ(1) + (size - capacity) * sizeof(element). The Θ(1) part is a small pointer overhead, and variables to store size and capacity, and the rest is unallocated/deallocated elements. Since capacity is doubled once size becomes equal to it, the (size - capacity) is at most size - 1, which is Θ(n) worst case. So we've got Θ(1) + Θ(n - 1) * Θ(1) = Θ(n - 1) = Θ(n).

#

Or wait, I misunderstood

#

It's excess space is (size - capacity) * sizeof(element). The Θ(1) part is a small pointer overhead, and variables to store size and capacity, and the overhead is unallocated/deallocated elements. Since capacity is doubled once size becomes equal to it, the (size - capacity) is at most size - 1, which is Θ(n) worst case. So we've got Θ(n - 1) * Θ(1) = Θ(n - 1) = Θ(n).

quaint perch
#

thanks

robust dagger
#

I think it's an underappreciated point that you can actually make a trade-off between between space and time here. At one end, you grow the array by one item whenever you append and get O(1) space overhead but O(n) time complexity (because in the worst case, enlarging the array may require copying it); at the other end, you grow the array by a constant factor whenever you run out of space and get O(n) space overhead but O(1) amortized time complexity. But you can, in principle, grow an array of length n to an array of length f(n) for any f such that f(n) > n. For example, you could let f(n) = n + ceil(log n), or f(n) = n+ ceil(sqrt(n)), or lots of other things. These choices clearly give intermediate behavior, though I've never tried to work out exactly what their complexity is.

stiff willow
outer rain
quaint perch
stiff willow
#

bro im new to coding i dont understand

stiff willow
quaint perch
#

what don’t you understand exactly

outer rain
stiff willow
#

hmmm

#

ok

#

is the array soemthing to do with the ram ?

quaint perch
outer rain
#

well that's specific

#

hi

#

hmmm

#

apparently processor cache usage can affect python performance

import timeit
import random

N = 10 ** 7
p1 = list(range(N))
p2 = p1.copy()
random.shuffle(p2)

a = [random.randrange(10 ** 12) for _ in range(N)]

p1, p2, a = tuple(p1), tuple(p2), tuple(a)

# p1 is a cache-efficient sequence which does no memory jumps and makes prefetcher happy
# p2 is a nightmare for every modern processor

print(timeit.timeit("sum = 10 ** 12\nfor i in p1: sum += a[i]", globals=globals(), number=100))
print(timeit.timeit("sum = 10 ** 12\nfor i in p2: sum += a[i]", globals=globals(), number=100))
print(timeit.timeit("sum = 10 ** 12\nfor i in p1: sum += a[i]", globals=globals(), number=100))
print(timeit.timeit("sum = 10 ** 12\nfor i in p2: sum += a[i]", globals=globals(), number=100))
#

On my old laptop it outputs

59.48938252200014
444.5384246399999
68.39246315399987
459.9337272390003
#

Not sure how good my method is, but 7.5 times difference is absolutely enormous

#

Not as enormous as it would be in native code, but it's still a lot

empty trout
#

help me to write the fastest function that takes and array and index, and returning that array, but it moves element at given index to the start and at index + 1 to the end

#

I stopped at this variant, but it's still slow

def forward_transform(i: int, arr: list[int]):
    arr = arr[:]
    arr.insert(0, arr.pop(i))
    arr.append(arr.pop(i + 1))
    return arr
outer rain
# empty trout I stopped at this variant, but it's still slow ```py def forward_transform(i: i...

There is no way to make it significantly faster than this. You probably can make it around 1.5-2 times faster, but that's probably a python limit. Numpy will be orders of magnitude faster. Or you can try using other data structures for storing arr, like linked lists (but that's probably not what you want because or linear time random access) or randomized binary trees/AVL-trees/etc. Those are very hard to implement though compared to lists.

quaint perch
empty trout
empty trout
quaint perch
#

can i use collections.deque instead of asyncio.Queue or queue.Queue

#

what is the difference

astral osprey
outer rain
astral osprey
#

insert: O(n)
append: Append[1]

I think alot of the time may be contributed to the INSERT method, also what's the purpose of arr = arr[:] are you trying to create a copy? if so this may just make a reference?

outer rain
outer rain
#

You can't do this in better time complexity without using other data structures. Linked lists will do that in O(1), but they are pain to traverse and they cannot be persistent, so copying will still take O(n). Persistent trees do everything in O(log), but difficult to implement. Using numpy is probably 10-100 times improvement, same time complexity.

quaint perch
outer rain
#

Or not...

#

nevermind i'm super wrong

#

copying is the most expensive operation

#

my bad

#

Ok, if you don't need to copy do not copy. This is very slow as it turns out, at least for integer arrays

quaint perch
#

persistent vectors go brr

haughty mountain
#

in itself this will be an expensive operation to implement

#

(maybe you can do something with a tree that supports order statistics, but they are far from trivial)

naive oak
#

is there an easy way to iterate over all edges of a grid?

#

like i have a nxn grid and from each grid point i can go to the 8 other grid points surrounding it (except the boundary)

#

and i want to iterate over each pair of points

#

but if i just did it for every point i'd double count

outer rain
#

Kinda like you would do with array (iterate only if the second element of the pair is greater than the first one), except 2d

naive oak
#

ah ofc

#

why didn't i think of that

drifting kraken
#

hello! anyone suggest a roadmap and resources to learn data structures and algo in python

west vigil
#

Looking for help to write an algo to determine the validity of an expression

#

ive kind of understood a few concepts but no idea in implementation

robust dagger
#

What do you mean by "validity"?

west vigil
#

Like to check if parantheses are in the right place, and right stuff in front of operators etc.

#

so far the only solution has been to write a parser in a binary tree but not sure how to implement

robust dagger
#

What are you trying to parse?

west vigil
#

a equation

#

can i dm?

robust dagger
#

No, I don't really do DMs.

#

This sounds like an exercise for a compilers course or something?

snow anvil
#

And how to use them

#

I had to do one of these this semester it's not hard especially in python

#

For the one I did we also had to evaluate the expression for if it's a valid string there is probably a easier way

spare jolt
#

Guys

#

How could I make an algorithm to trade crypto

#

I already used web3 to connect to a wallet and make transactions

snow anvil
# 
while True:
    if balance >= doge_coin_price:
        doge_coin.buy()
outer rain
finite dew
#

technical analysis is the equivalent of astrology in the finance.

#

I would personally look into market making, pairs trading, statistical arbitrage, basis risk premium harvesting

austere lodge
#

Is there any DSA test like AWS ones , I don't stick to a routine and learn but if there's a exam we can schedule and give I think it will help in preparing a lot more seriously

modest prairie
#

I need to create a function that will add the all the divisors of a number

#

I need help with it

#

@lusty crows

snow anvil
modest prairie
#

Yes

snow anvil
#

How fast O(n) fast enough? If so that is easy and you should try to think of it yourself

#

Other than that you could do prime factorisation which I think should be faster

#

Well not really just find the O(n) solution first

outer rain
#

The O(sqrt(n)) is not much harder. Precalculation with Eratosthenes sieve is at most O(sqrt(n)/log(n)) improvement per number and generally does not worth it for a set of unrelated numbers in a large range. Eratosthenes sieve can also factorize numbers in range [l, r] in O(sqrt(r) + (r - l)) (perhaps also times log log r, I don't remember if linear sieve can do that). Better algorithms get very, very complex. But if you have a quantum computer laying around, there is a fairly simple Shor's algorithm. Seriously, just google how to get divisors of the number, or how to generalize the sieve, there are a lot of good explanations out there.

snow anvil
#

I think it'd be best for them to find an algorithm that works by themselves and then to google for better ones

outer rain
#

Fair, it's kinda straight forward to implement an O(n) and then come up with O(sqrt(n)) optimization.

snow anvil
#

@modest prairie can you think of a solution that requires only one for loop over the range from 1 or 2 to your_number?

modest prairie
#

I’m not quite sure

snow anvil
#

Is there any operator in python that could help you find if any given number is a factor? If so which one?

modest prairie
#

Modulo?

snow anvil
fiery cosmos
#

Coalesced hashing

#

anyone heard of this?

halcyon plankBOT
#

Hey @trim charm!

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

trim charm
#

Hy,is there anyone who knows deep learning better?
I need to implement a multi-layered classifier where weights of each layer is calculated greedily using
layer-wise pretraining with the help of auto-encoders on STL-10 dataset. And I have to train a classifier having
[1024,1200,728,512,128], structure (excluding input and output layers) for classification task on the test set.(I dont have to use tenserflow for this problem)

Im getting an error saying RuntimeError: mat1 and mat2 shapes cannot be multiplied (32x12288 and 27648x1200) in training the autoencoder for each layer the code which I written for it is:
https://paste.pythondiscord.com/tevijomine

earnest mauve
#

what are the best resources someone can use to learn OOP concept in python from scratch?

slender sandal
#

Corey Schafer's OOP playlist on YouTube or Real Python's OOP course

frank glade
#

Could you please help me with the following exercise?
I don't have a clear idea to solve it

earnest mauve
quaint perch
haughty mountain
agile sundial
#

i don't get what they mean by the merge-sort hint

#

i think what you want to do is ||do prefix sum with b. then you can find when a particular a_i runs out, which you can do with binary search||

outer rain
#

There is also a solution there so be careful and don't click the link with editorial until you solve the problem for sure πŸ™‚

slim galleon
#

Can anyone suggest material for ds and algo for interview, preferred languages are python and c++

grim matrix
naive oak
#

geeksforgeeks is not good

limpid sand
#

I'm trying to fit a CubicSpline to some data for extrapolation

I have a lot of data in an ndarray and then one point I want the data to extrapolate towards.

[minima, ...a large gap..., ...a lot of other data]

However when my CubicSpline hits the other data section I see a jump above the data.

Is there a better way to extrapolate smoothly from the minima to the first point in the data array?

#

Let's say I have y-values like this:

[
  0, # minima
  10.5,
  10.51,
  10.53,
  10.58,
  10.59,
  ...
]

My CubicSpline extrapolates to look like:

[
 0,
 10.9,
 10.7,
 10.51,
 10.53,
 10.58
]
#

I would much rather it extrapolated like this:

[
 0,
 9.8,
 9.99,
 10.35,
 10.51,
 10.53
]
vocal gorge
#

I don't really get this - isn't spline interpolation guaranteed to pass through each of the data points?

#

(oh, or are you fitting a single spline to the entire dataset?)

limpid sand
#

Yea, it's a merged spline

# 
    # Define the range of parameter t
    t = np.linspace(0, 1, num_points)

    # Evaluate the curves at each value of t
    x = bz_x(t)
    y = bz_y(t)
    z = bz_z(t)

    # Combine the x, y, and z values into a single array of points
    interpolated_points = np.column_stack((x, y, z))
vocal gorge
#

How are you determining the parameters for the three curves, though?

limpid sand
# 
def extend_to_bottom(
    points: Cloud, minima: Point, maxima: Point, num_points: int = 20
) -> Cloud:

    minima = points[0].copy()
    minima[2] = -10

    sampled_points = points[:: int(len(points) / num_points)]

    # Split the data into separate arrays for each dimension
    x_vals = sampled_points[:, 0]
    y_vals = sampled_points[:, 1]
    z_vals = sampled_points[:, 2]

    # Insert the points at the beginning and end of the array
    x_vals = np.insert(x_vals, 0, minima[0])
    y_vals = np.insert(y_vals, 0, minima[1])
    z_vals = np.insert(z_vals, 0, minima[2])
    x_vals = np.insert(x_vals, len(x_vals) - 1, maxima[0])
    y_vals = np.insert(y_vals, len(y_vals) - 1, maxima[1])
    z_vals = np.insert(z_vals, len(z_vals) - 1, maxima[2])

    # return np.column_stack((x_vals, y_vals, z_vals))

    indices = range(len(x_vals))

    # Create separate curves for each dimension
    bz_x = CubicSpline(indices, x_vals, extrapolate=True)
    bz_y = CubicSpline(indices, y_vals, extrapolate=True)
    bz_z = CubicSpline(indices, z_vals, extrapolate=True)

    # Define the range of parameter t
    t = np.linspace(0, 1, num_points)

    # Evaluate the curves at each value of t
    x = bz_x(t)
    y = bz_y(t)
    z = bz_z(t)

    # Combine the x, y, and z values into a single array of points
    interpolated_points = np.column_stack((x, y, z))

    return interpolated_points
#

Sorry for code spam

#

Points are sorted distance from the maxima, farthest first

#

Also points are guaranteed to be in the same general direction (directional slice when looking from above)

vocal gorge
#

Huh, it looks a bit weird to me that you're passing indices, which go from 0 to len(x_vals), to CubicSpline as the x-points, but then evaluating the spline at the linspace from 0 to 1 (rather than to len(x_vals)). Isn't that only the first small part of the spline?

limpid sand
#

0..len(x_vals) gives me the entire spline

#

I just want to extrapolate to fill my missing pieces between the minima and the first datapoint

#

If I actually fill the entire spline, most of it looks matching and correct, except for the jump at the end of the data

#

The jump is suddenly vertically upwards

#

Strange πŸ€” have been banging my head on it for a while

vocal gorge
limpid sand
#

10 points into the dataset

#

In general it's far too sharp a drop anwyay

#

Perhaps you know of a better spline method?

#

I guess I can try to drop the first data point by x, and then the next by n/2 and the next by n/4

#

Mayb that'll help the spine align

#

But it's a shame to lose that directional (horizontal) data

vocal gorge
#

If the splines are meant to be closed curves, maybe extrapolate="periodic" would be a good choice?

fallen sequoia
#

is there a way to put a default except on all my functions?

vocal gorge
#

sounds like you want to override sys.excepthook or something. Why, though?

fallen sequoia
#

But i don't want to write a try except block in 500 functons

vocal gorge
#

Well, presumably your program only has one entry point - wrap it in a try-except.

#

(Also, don't just discard the error and ask the user to try again, at least dump the full error and traceback into the log.)

fallen sequoia
fallen sequoia
agile sundial
#

just bubble the except up to the entry point like reptile said

lean junco
#

what kind of questions should i expect from startup interview, as a fresher?
CAN they ask me DSA?

snow anvil
#

They can ask you whatever they want lol

lean junco
haughty mountain
#

what are they even doing?

#

can some sets of functions be parametrized and collapsed into one?

final comet
#

is pytourch good for q-learning?

agile sundial
haughty mountain
#

I think prefix sums is the intended solution

agile sundial
#

my only lead is that with prefix sum, the array is sorted, and it's also sorted in mergesort

slim galleon
#

whats this? a book

quaint perch
slim galleon
#

yup

#

πŸ‘

haughty mountain
kindred gazelle
#

hi! i wanna able to trace multipy prices from shopping sites, which way should i follow?

gritty oyster
#

why this one is invalid binary search tree? πŸ₯Ή I'm missing some rule

image.png
agile sundial
#

all nodes to the left of a node must be less than or equal to the node

blissful ginkgo
#

I need help with finding the right wording so I can research it better - I'm trying to figure out if one numpy 2d array (all bools) can "fit" into another, bigger numpy 2d array - smaller array will have True in some positions and I need to find if there is any place in the bigger array with that same shape but with False. I hope that's clear πŸ™‚

outer rain
blissful ginkgo
# outer rain > bigger array with that same shape Can you clarify that?

I can try: if bigger array is np.zeros((5, 12), dtype=bool), that's 5x12 of False...and if smaller array is something like:

        [
            [1, 1, 1, 1, 0],
            [0, 0, 1, 0, 0],
            [0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0],
        ],
        dtype=bool,

we know that it can fit because this shape (where 1s are) can be placed in bigger array.
If bigger array is all 1s, than nothing can fit.

#

What I'm wondering if is there a name for this, because if there is I'm guessing there's a numpy function that checks it, or if I have to write it myself from scratch

outer rain
#

I see. I guess you can call it "multidimensional boolean convolution", but I don't think function to do this exists in numpy. It's not hard to write it yourself though!

You can check if two "one shapes" in a and b (of equal size) will intersect with simple np.any(a & b). So you can iterate over the offset of one array position and apply that check for the intersection:

n, m = a.shape()
h, w = b.shape()
c = np.array((h - n + 1, w - n + 1), dtype=bool)
for i in range(h - n + 1):  # if i = h - n + 1 then a won't fit into b[...] because b is too small
  for j in range(w - m + 1):
    c[i][j] = np.any(a & b[i:i + n, j:j + m])

This may not be the most accurate implementation, I have not checked it, so don't blindly copy and paste

#

There is a significantly faster way to do that (for very large inputs), but way more complex (using multidimensional FFT), but I think the solution above will suffice.

blissful ginkgo
#

Thank you very much. Let me try and understand it πŸ™‚ and test on few examples.

blissful ginkgo
#

I don't think this works. First error was something about numpy and TypeError (had to use npzeros with dtype=int for c), but even with that I don't think that shape can be used to solve this.
Consider:

1 0 1 0 0
0 0 0 0 0
0 0 0 0 0```
this would have shape of 2, 3, but it's more complicated than that
flat sorrel
# blissful ginkgo I don't think this works. First error was something about numpy and TypeError (h...

!e

import numpy as np
from scipy import signal

def contains(large, small):
    k1 = large
    k2 = small[::-1, ::-1]  # Need to flip the kernel as we are doing correlation, not convolution

    convolved = signal.convolve2d(k1, k2, mode='same')
    print('Convolved:\n', convolved)
    print('Target:', k2.sum())
    return (convolved == k2.sum()).any()

arr1 = np.array([
    [1, 1, 1, 0, 0],
    [1, 0, 1, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
])
arr2 = np.array([
    [1, 1, 1],
    [1, 0, 1],
    [0, 0, 0],
])
arr3 = np.array([
    [1, 1, 1],
    [1, 1, 1],
    [0, 0, 0],
])
arr4 = np.array([
    [1, 0, 1],
    [1, 1, 1],
    [0, 0, 0],
])

print(contains(arr1, arr2))
print(contains(arr1, arr3))
print(contains(arr1, arr4))
halcyon plankBOT
#

@flat sorrel :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | Convolved:
002 |  [[1 2 1 1 0]
003 |  [2 5 2 2 0]
004 |  [1 2 1 1 0]
005 |  [0 0 0 0 0]
006 |  [0 0 0 0 0]]
007 | Target: 5
008 | True
009 | Convolved:
010 |  [[2 3 2 1 0]
011 |  [3 5 3 2 0]
... (truncated - too many lines)

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

flat sorrel
#

but it uses scipy to perform the convolution

#

replace k2.sum() with (k2 * k2).sum() to extend it to test whether two integer arrays exactly match

blissful ginkgo
#

@flat sorrel I'm sorry but I have no idea what this is...what's with 2s and 3s and 5s? All I need is if smaller can fit in larger in any position (if there's a the same "shape" (but not just h*w, but the real shape) in larger 2d array with "False", so that the smaller 2d array (which has True in those same positions))

flat sorrel
#

the integer values are the result of the convolution as k2 is being slided over k1

#

when k2 exactly overlaps a patch in k1, the corresponding result is (k2 * k2).sum()

#

e.g. when they don't match, the correlation between a patch in large and small gives

[[1, 0, 1],          [[1, 0, 1],               ([[1 * 1, 0 * 0, 1 * 1],
 [1, 1, 1],    *      [1, 0, 1],        =        [1 * 1, 1 * 0, 1 * 1],             = 4 != 5
 [0, 0, 0]]           [0, 0, 0]]                 [0 * 0, 0 * 0, 0 * 0]]).sum()

but when they match, the correlation is evaluated as

[[1, 0, 1],          [[1, 0, 1],               ([[1 * 1, 0 * 0, 1 * 1],
 [1, 1, 1],    *      [1, 1, 1],        =        [1 * 1, 1 * 1, 1 * 1],             = 5 == 5
 [0, 0, 0]]           [0, 0, 0]]                 [0 * 0, 0 * 0, 0 * 0]]).sum()
flat sorrel
blissful ginkgo
haughty mountain
#

since you want the pattern to align with the gaps (0), not the filled in cells (1)

#

!e

import numpy as np
from scipy import signal

def contains(large, small):
    k1 = 1 - large
    k2 = small[::-1, ::-1]  # Need to flip the kernel as we are doing correlation, not convolution

    convolved = signal.convolve2d(k1, k2, mode='valid')
    print('Convolved:\n', convolved)
    print('Target:', k2.sum())
    return (convolved == k2.sum()).any()

arr1 = np.array([
    [1, 1, 1, 0, 0],
    [1, 0, 1, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
])
arr2 = np.array([
    [1, 1, 1],
    [1, 0, 1],
    [0, 0, 0],
])
arr3 = np.array([
    [1, 1, 1],
    [1, 1, 1],
    [0, 0, 0],
])
arr4 = np.array([
    [1, 0, 1],
    [1, 1, 1],
    [0, 0, 0],
])

print(contains(arr1, arr2))
print(contains(arr1, arr3))
print(contains(arr1, arr4))
halcyon plankBOT
#

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

001 | Convolved:
002 |  [[0 3 3]
003 |  [3 4 4]
004 |  [5 5 5]]
005 | Target: 5
006 | True
007 | Convolved:
008 |  [[1 3 4]
009 |  [4 5 5]
010 |  [6 6 6]]
011 | Target: 6
... (truncated - too many lines)

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

haughty mountain
#

!e let's try a more interesting input

import numpy as np
from scipy import signal

def contains(large, small):
    k1 = 1 - large
    k2 = small[::-1, ::-1]  # Need to flip the kernel as we are doing correlation, not convolution

    convolved = signal.convolve2d(k1, k2, mode='valid')
    print('Convolved:\n', convolved)
    print('Target:', k2.sum())
    return (convolved == k2.sum()).any()

arr1 = np.array([
    [1, 0, 1, 1],
    [1, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
])
arr2 = np.array([
    [1, 0],
    [1, 1],
    [0, 1],
])

print(contains(arr1, arr2))
halcyon plankBOT
#

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

001 | Convolved:
002 |  [[1 4 2]
003 |  [1 3 3]
004 |  [3 3 4]]
005 | Target: 4
006 | True
haughty mountain
#

so there are two places where the smaller shape could be placed

# 
i.e.
    1 X 1 1
    1 X X 0
    1 1 X 1
    0 0 0 0
    0 0 0 0

    1 0 1 1
    1 0 0 0
    1 1 X 1
    0 0 X X
    0 0 0 X
vocal gorge
#

Need to flip the kernel as we are doing correlation, not convolution

Why not use correlate2d then?

haughty mountain
#

you probably could, I didn't write that code

vocal gorge
#

ah

haughty mountain
#

in any case the 4s correspond where the top right of the smaller matrix can be placed

#

it's a 4 because all 4 1s got matched with 1s

vocal gorge
haughty mountain
#

I should be careful about writing invert and matrix in the same sentence when I mean bit inverse πŸ˜…

flat sorrel
#

but yeah I think swapping 1s and 0s would solve your problem in that case

#

!e

import numpy as np
from scipy import signal

def contains(large, small):
    k1 = 1 - large
    k2 = small

    correlated = signal.correlate2d(k1, k2, mode='valid')
    target = (k2 * k2).sum()
    print('Correlated:\n', correlated)
    print('Target:', target)
    return (correlated == target).any()

arr1 = np.array([
    [1, 0, 1, 1],
    [1, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
])
arr2 = np.array([
    [1, 0],
    [1, 1],
    [0, 1],
])

print(contains(arr1, arr2))
halcyon plankBOT
#

@flat sorrel :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | Correlated:
002 |  [[1 4 2]
003 |  [1 3 3]
004 |  [3 3 4]]
005 | Target: 4
006 | True
haughty mountain
#

and yeah, I didn't mention it but I switched the mode to 'valid'

#

so that we only get sums for when the smaller array actually fits

#

not that it matters for the result, it just felt like the right thing to do πŸ˜›

flat sorrel
#

yeah I agree that would be better

blissful ginkgo
#

Thank you all, I'm not sure I'd be able to do it πŸ™‚

flat sorrel
#

Glad to help!

jaunty oxide
#

from math import floor, log2

def count(n):
layers = 0
for i in range(1, n+1):
layers += floor(log2(i))
return layers

#

Any ideas how I can make this code faster?

#

Task is to calculate how many swaps for an array of 1 to n to maxheap

vocal gorge
#

to start with, floor(log2(i)) is something like i.bit_length()-1, I think

#

so check if the bit_length way is faster, but probably it's not much so.

maiden garden
#

Hello there,
I'm new here, i want to learn programming and i'm at very early stage of this
I have a pb rn when i want to check on what conda's version i'm in on the IDLE shell

image.png
quaint perch
maiden garden
#

Oh sorry, thx nonetheless

meager bane
#

what is creating None here?

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        for count, i in enumerate(nums):
            if i == target:
                return count
            if target < i:
                return (count - 1)

TypeError: None is not valid value for the expected return type integer
    raise TypeError(str(ret) + " is not valid value for the expected return type integer");
Line 35 in _driver (Solution.py)
    _driver()
Line 42 in <module> (Solution.py)
During handling of the above exception, another exception occurred:
TypeError: '<' not supported between instances of 'int' and 'NoneType'
Line 12 in _serialize_int (./python3/__serializer__.py)
Line 61 in _serialize (./python3/__serializer__.py)
    out = ser._serialize(ret, 'int```
outer rain
outer rain
# jaunty oxide from math import floor, log2 def count(n): layers = 0 for i in range(1...

Bit width always acts in a predictable way. There is one number with width of 1 (0b1), two with width of 2 (0b10, 0b11), four with width of 3 (0b100, 0b101, 0b110, 0b111), etc., 2^k of width k - 1. Therefore numbers are split into groups by their width and all you have to do is for each group in your range [1, n] sum up the size of that group times it's bit width minus one. This can be done in O(log n). Kinda like that, except there will be some +1/-1 here and there. I am not going to think hard about that, nor spoonfeed you. Think of that as a very rough pseudocode:

def count(n):
  i = 1
  layers = 0
  while 2 ** i < n:
    layers += i * 2 ** i  # group [2 ** i, 2 ** (i + 1)), 2 ** i numbers in total of width i
    i += 1
  layers += i * (n - 2 ** i)  # a final group, a subset of [2 ** i, 2 ** (i + 1)) bounded by n
  return layers

You can also precalculate the sum in while loop for, say, i = 0..30 and just look up the initial layers sum by using index n.bit_length(). That way this function will work in O(1).

snow anvil
meager bane
#

why is count at None?

mild dove
#

Hi, just for curiosity, have anyone implemented bloom filter with insert and delete? or is there a good way to implement bloom filter like to avoid go to cache/database when we have delete/update?

upbeat compass
#

Hi,

Below is the program for counting the factor of given N.

    def solve(self, A):
        factors = []
        cnt = 0
        for i in range(1, int(A**0.5)+1):
            fact = A / i
            if A % i == 0:
                cnt+=1
                if i != A//i:
                    cnt += 1
        return cnt

works fine with below inputs,

func(5)
func(10)
func(12)
func(6)

but, If I don't include the 2nd if condition, it was failing in below input.

func(637759701)

Can anyone explain me the need of the 2nd condition ?

naive oak
#

the second condition checks if the factor is the square root of the number

#

and if it isn't then it adds one

#

since you're only counting up to the sqrt

somber hatch
#

What's a priority Queue?

jolly mortar
#

in a normal queue you can only add things to the end, in a priority queue you can insert a new element at some particular position based on some priority you assign each element

#

and whenever you pop from the front, you always get the highest priority element

agile sundial
#

you don't really insert it into a particular position based on priority. you just insert it

jolly mortar
#

well sure

#

assuming its a heap itll shift things around till it gets in a particular position

agile sundial
#

yeah but you don't know anything about its position unless it's the max, assuming a max heap

upbeat compass
naive oak
outer rain
# meager bane can you explain why? In order for it to reach target > i condition, the count is...

Run your code in your head if nums = [0, 0, 0, 0, 0] and target = 3. i is always 0, target is always 3. Both if conditions will fail and each iteration nothing will be returned, there for None will be returned. Even if that example is not allowed by problem constraints, a similar situation where target > i always is the only way to return None.

Do you know that enumerate yields pairs of index, value and not value, index by the way?

quaint perch
#

wait wdym by avoiding going to cache or database

outer rain
#

I think if they need bloom filters sets won't suffice

snow anvil
outer rain
# mild dove Hi, just for curiosity, have anyone implemented bloom filter with insert and del...

I don't think deleting from bloom filter is possible, but workarounds exist. You can have a second bloom filter with deleted elements. If you need to check if the element is in filter, ask if it's in the first filter and not in the second. But then you won't be able to insert elements back... unless you have a third bloom filter for inserting elements deleted once, but then you won't be able to delete elements inserted twice, etc. Are you sure you can't use simple bitsets? They will work ok-ish with autoincremented ids.

mild dove
# outer rain I don't think deleting from bloom filter is possible, but workarounds exist. You...

I can use set or bitset but it is not memory scalable efficient like bloom filter. but I'm thinking now, for example LSM-tree it will create a key: tombstone to the deleted data (after SSTable merge probably it will update the data removing the tomb). so I guess if we just ignore deleted it will be okay (false positive is acceptable). after sometime need to rebuild the bloomfilter to remove the tombstones.

blissful ginkgo
#

I have 2 numpy 2d arrays:

[[1 1 0 0 0]
 [1 1 1 1 0]
 [1 1 0 0 0]]

and

[[1 1]
 [0 1]
 [1 1]]

I want to "combine" them by putting the small array "over" the big to the only available location ("shape" of 1s in small array fits the "shape" of 0s in big), so that it looks like this:

[[1 1 0 1 1]
 [1 1 1 1 1]
 [1 1 0 1 1]]

My current code, where fits is Tuple[bool, (tuple)] and tuple is the starting coordinate where piece will fit:

big_array[
    fits[1][0] : fits[1][0] + small_array.shape[0],
    fits[1][1] : fits[1][1] + small_array.shape[1],
] = small_array

produces this:

[[1 1 0 1 1]
 [1 1 1>0<1]  # note the 0 from the second array
 [1 1 0 1 1]]

so I need to add a condition that only those values which have 1 in small array are the ones that apply the update. How? πŸ™‚

mint phoenix
#

omago

plain marten
#

Can anyone help me with my homework? im 10 hours deep, and got nothing to show for it. Besides it is a problem much like minimum spanning trees. But not really hmmm

outer rain
blissful ginkgo
agile sundial
hidden yacht
snow anvil
#

This is too general of a question. Which part of bfs do you have trouble with?

fiery cosmos
# plain marten

why do i feel like this is not the complete question, pardon me if i am wrong.

pine axle
#

In numpy can you broadcast arrays of shapes: (100, 200, 3) and (100, 200)?

#

I thought you could but my code doesn't seem to like it

vocal gorge
#

arrays with different numbers of dimensions are usually not compatible. add a 1-sized third axis to the second array (arr2[..., None], say) and they'll be compatible.

naive oak
#

in this case it's not broadcastable since it matches 3 with 200

robust dagger
naive oak
#

it always adds to the left doesn't it

#

!e

import numpy as np
a = np.zeros((5, 6, 7, 8))
b = np.zeros((6, 1, 8))
print((a+b).shape)
halcyon plankBOT
#

@naive oak :white_check_mark: Your 3.11 eval job has completed with return code 0.

(5, 6, 7, 8)
swift breach
robust dagger
naive oak
#

yeah

#

I was disagreeing with the point that usually different dimensions can't be broadcasted together

#

for this specific case you need to insert a new axis yourself since you want it to the right

keen skiff
# 
    def populate_kids(self, arr, used_Indices):
        for child in self.children:
            child.get_all_jumps(arr, used_Indices)

        for child in self.children:
            for a in child.children:
                a.get_all_jumps(arr, used_Indices)

        for child in self.children:
            for a in child.children:
                for b in a.children:
                    b.get_all_jumps(arr, used_Indices)

        for child in self.children:
            for a in child.children:
                for b in a.children:
                    for c in b.children:
                        c.get_all_jumps(arr, used_Indices)
#

Is there a way to make this automatic

#

it's clearly following a pattern

agile sundial
#

recursion

keen skiff
#

I tried

robust dagger
# keen skiff I tried

It looks like you need

def populate_kids(self, arr, used_Indices):
    for child in self.children:
        child.get_all_jumps(arr, used_Indices)
        child.populate_kids(arr, used_Indices)

Or something like that.

keen skiff
#

@robust dagger tried that doesn't work

robust dagger
#

Possibly

def populate_kids(self, arr, used_Indices):
    self.get_all_jumps(arr, used_Indices)
    for child in self.children:
        child.populate_kids(arr, used_Indices)

then?

keen skiff
#

hmm let me give it a shot

robust dagger
#

If it doesn't work, can you say how it fails?

keen skiff
#

nah it doesnt work
Get_all_jumps is supposed to populate itself with kids

robust dagger
#

I think you're going to have to post more of your code for anyone to understand how it's failing.

keen skiff
#

Im trying to populate a Tree data structure

#

but I want to populate first lvl 0 then lvl 1 then lvl 2

#

your code populates 0123 0123 0123 0123 0123

#

not 000 111 222 333

#

you get it ?

robust dagger
#

"Populate" is ambiguous. I don't know what you mean by that.

#

When is .children set?

keen skiff
#

It's a tree that adds childern that are also Tree structure

robust dagger
#

Can you post your code?

keen skiff
#

yes sure

# 
class Tree:
    def __init__(self, data):
        self.parent = None
        self.children = []
        self.data = data
        self.distance = 0

    def add_child(self, child):
        child.parent = self
        self.children.append(child)

    def get_all_jumps(self, array, used_Indices):
        valuesUsed = []
        # Small Jumps
        if (self.data + 1 < len(array)) and not(self.data + 1 in used_Indices):
            valuesUsed.append(self.data + 1)
            self.add_child(Tree(self.data + 1))
        if (self.data - 1 > 0) and not(self.data - 1 in used_Indices):
            valuesUsed.append(self.data - 1)
            self.add_child(Tree(self.data - 1))

        # Big Jumps
        for j, e in enumerate(array):
            if j == self.data:
                continue
            if (array[j] == array[self.data]) and not(j in used_Indices):
                valuesUsed.append(j)
                self.add_child(Tree(j))

        for value in valuesUsed:
            used_Indices.append(value)

        if self.parent is None:
            print(self.data)
        else:
            print(self.data, " Parent:", self.parent.data)

    def populate_kids(self, arr, used_Indices):
        self.get_all_jumps(arr, used_Indices)
        for child in self.children:
            child.populate_kids(arr, used_Indices)

    def getDistanceToFirst(self, dist):
        if self.parent is not None:
            dist += 1
            self.parent.getDistanceToFirst(dist)
        else:
            self.distance = dist
            return dist


class Solution(object):
    def minJumps(self, arr):
        dist = 0
        used_Indices = [0]
        root = Tree(0)
        root.get_all_jumps(arr, used_Indices)
        root.populate_kids(arr, used_Indices)
        return root.distance
#

Too long

robust dagger
#

What is .data supposed to represent? It's some kind of index, but I don't understand why you want to track it.

keen skiff
#

yes it's index

#

I need to know the index because I need to know what's the distance from first element to last element

robust dagger
#

What's the actual problem you're trying to solve?

keen skiff
#

first element has index 0 and last has index array.length -1

keen skiff
robust dagger
#

Are you familiar with dynamic programming?

keen skiff
#

kinda but not really

robust dagger
#

This is a dynamic programming problem.

#

Because of the goal of the problem, you do not need to keep an explicit tree.

#

BFS is not the same thing as dynamic programming in general.

#

Yes.

#

It can most certainly be thought of as dynamic programming.

#

You can also think of it as BFS. It works out to be the same thing.

#

In this particular case, yes.

#

Thinking of it as dynamic programming offers some opportunities for improving the underlying algorithm.

#

You can use heuristic functions as in the A* algorithm and you can work from both ends.

#

You can't do that with plain BFS.

#

Regardless, the first thing to do is get working code.

keen skiff
# 
def populate_kids(self, arr, used_Indices):
    for a in self.children:
        a.get_all_jumps(arr, used_Indices)

    for a in self.children:
        for b in a.children:
            b.get_all_jumps(arr, used_Indices)

    for a in self.children:
        for b in a.children:
            for c in b.children:
                c.get_all_jumps(arr, used_Indices)

    for a in self.children:
        for b in a.children:
            for c in b.children:
                for d in c.children:
                    d.get_all_jumps(arr, used_Indices)
#

ok but regardless

#

this should have an automatic way of generating

#

so what is it

robust dagger
#

Are you familiar with breadth first search?

#

That's the most elementary way to solve this problem.

#

If you're not, then you should look that up. It will solve your populate_kids problem.

keen skiff
#

ye but now I kinda wanna know how do you make a recurssive function like that one

robust dagger
#

That's the easiest way to do BFS.

keen skiff
#

I'm keeping track of which nodes I processed

robust dagger
#

Doesn't look like it.

keen skiff
#

the function has the parameter "used_indices"

robust dagger
#

Yes, why does that matter?

#

Actually, hold on.

#

I think I know your problem.

#

You're using the same class to represent the tree and paths through the tree.

#

I think you would have a much easier time if you made those two distinct.

keen skiff
#

am I not supposed to

robust dagger
#

It's a choice you can make.

keen skiff
#

if I made a layer class and a tree class ?

robust dagger
#

The allowable moves aren't really a tree. They're really a graph.

south wren
#

Is there a way to check a class value without inheritance? E.g. Parent.value = 1, child.value will return 1 if not defined, can I check specifically if it's not defined on the child?

robust dagger
south wren
#

On the class itself, not an instance

robust dagger
#

Look at the class's __dict__.

south wren
#

oh right you can do that

robust dagger
#

(You should probably not do this, by the way.)

keen skiff
#

can you guys pls upvote this post ❀️

robust dagger
#

(At least not if you can help it. But I've run across cases where you can't...)

south wren
#

Yeah, it's not ideal but the way we have things structured it's better this than the alternative

robust dagger
#

Yeah, I've been there. Good luck!

south wren
#

Haha, thanks. Multiprocessing is a biatch

keen skiff
#

@robust dagger you were right

#

maybe there's no way to do that recursively

#

and you even mentioned BFS a couple of times but I thought I had to completely redesign my code if I implemented that

#

@cobalt mirage what is DFS

#

imma google that thank you

shut breach
#

@tepid basin your help channel closed, but I think that would be log(log(n))

haughty mountain
#

2^(2^x) >= n

fiery cosmos
# 
import pygame
import os
import sys
from dataclasses import dataclass
import random
from abc import ABC

is this normal to import this many stuff

naive marten
#

Yes.

fiery cosmos
#

lol okay

#

thx

robust dagger
fiery cosmos
#

below average πŸ’€

#

im just at 94th line of code

robust dagger
#

Oh, well, for short things it's probably about average.

fiery cosmos
#

lmao

# 
import pygame
import os
import sys
from dataclasses import dataclass
import random
from abc import ABC

dir_path = os.getcwd()

pygame.init()


# pygame objects
screen = pygame.display.set_mode((600, 600))
clock = pygame.time.Clock()

# colours
black = (0, 0, 0)
gret = (128, 128, 128)
white = (255, 255, 255)

red = (255, 0, 0)
green = (0, 255, 0)
blue = (0, 0, 255)

@dataclass
class GameObject:
    colour: tuple
    pos: pygame.Rect
    speed: int

class Player(GameObject):
    def move(self, up=False, down=False, left=False, right=False):
        
        if up:
            self.pos.top -= self.speed

        if down:
            self.pos.top += self.speed

        if right:
            self.pos.right += self.speed

        if left:
            self.pos.right -= self.speed

        if self.pos.top < 0:
            self.pos.top = 0

        if self.pos.bottom > screen.get_height():
            self.pos.bottom = screen.get_height()

        if self.pos.left < 0:
            self.pos.left = 0

        if self.pos.right > screen.get_width():
            self.pos.right = screen.get_width()
            


# class Obstacle(GameObject):

#     def move(self, movable):
#         if movable:
#             self.pos.move(random.randint(1, self.speed))



# define and intialise player at centre
size = 100
player_x = screen.get_width() / 2 - size
player_y = screen.get_height() / 2 - size

player = Player(black, pygame.Rect(player_x, player_y, size, size), 10)


screen.fill(white)

while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            sys.exit()
        
    screen.fill(white, player.pos)

    keys = pygame.key.get_pressed()

    player.move(keys[pygame.K_UP], keys[pygame.K_DOWN], keys[pygame.K_LEFT], keys[pygame.K_RIGHT])
    
    pygame.draw.rect(screen, player.colour, player.pos)

    pygame.display.update()
    
    clock.tick(60)
#

idk might be a little bit bloated

robust dagger
#

Doesn't look like it to me.

fiery cosmos
agile sundial
#

probably has a lot of lines because you put a bunch of blank lines everywhere lol

robust dagger
#

When you try to express all the logic you want in a real game, you'll find that it grows a lot. It's going to be way bigger in the end.

fiery cosmos
fiery cosmos
robust dagger
#

My advice would be, if you like games, then try to make a real game.

#

Like, one with title screens, levels (if it's that kind of game), cut scenes, etc.

fiery cosmos
#

i will, that'd be a long way to go

fiery cosmos
robust dagger
#

Don't worry about art (unless you want to). You can just put in stick figures.

fiery cosmos
#

dw im just doing this because of school needing us to

robust dagger
# fiery cosmos wtf

It's a question of how ambitious you are. You could make something really simple. Maybe that's all you're interested in doing for the moment, and that's fine.

snow anvil
#

what does this have to do with algos and data structures?

fiery cosmos
#

imports

robust dagger
fiery cosmos
south wren
#

tbh depending on the language/library transitioning between scenes/menus/screens gracefully in a game is almost harder than coding the actual game

fiery cosmos
#

imma not do a story, just straight up a simple game

snow anvil
#

just please go to the appropriate channel
don't gum up this one with stuff that has nothing to do with the title

snow anvil
#

for my daily problem I used O(n) time but binary search can lead to O(log n) can someone explain how to apply binary search to this problem

#

I am clueless rn

# 
def findKthPositive(arr, k):
    prev = 0
    count = 0
    for i, num in enumerate(arr):
        if num != prev + 1:
            if count + (num - prev - 1) >= k:
                return prev + k - count
            count += num - prev - 1
        prev = num
        if i == len(arr) - 1:
            return arr[(len(arr) - 1)] + k - count

this was my approach

#

not exactly the greatest

#

nvm after some thinking I think I got it

tepid basin
tepid basin
#

i get your english explanation, but im not following the math term

haughty mountain
#

squaring x over and over goes like x, x^2, x^4, x^8, x^16, ...

#

i.e. x^(2^n)

tranquil junco
#

hey there,
Can you help me extract the payload from these xbee frames?
b'~\x00\x0e\x90\x00\x13\xa2\x00A\xe1%#\xff\xfe\xc1on\xb5' --> on
b'~\x00\x0f\x90\x00\x13\xa2\x00A\xe1%#\xff\xfe\xc1offW' --> off
b'~\x00\x0e\x90\x00\x13\xa2\x00A\xe1%#\xff\xfe\xc150-' --> 50

haughty mountain
# 
   b'~\x00\x0e\x90\x00\x13\xa2\x00A\xe1%#\xff\xfe\xc150-'
    / -------- ---------------------------------------- \
start size (14)         data (14 bytes)                 checksum
#

I have no clue about the format of the data itself

#

though clearly on/off/50 are in there

#

as the last thing before the checksum

tranquil junco
#

yes yes, that is what I put there.
Okay, But how can I index this byte array? Should I use smth like unpack or decode?

#

.decode('ascii') or .decode('utf-8') gives me unicode error

haughty mountain
#

why would you want it as a string?

#

it's binary data

#

so bytes is a reasonable thing to work with

#

and you can just index into it

#

slices give you new bytes objects, indexing normally gives you an int

tranquil junco
#

but how can I get the message out of it?

haughty mountain
#

what's the format?

tranquil junco
#

how do you mean?

#

sorry, I am little bit outside of my confortzone πŸ™‚

haughty mountain
#

I linked the format for a frame with the size and whatnot, but I have no clue what the data itself means

#

b'\x90\x00\x13\xa2\x00A\xe1%#\xff\xfe\xc150' this is the actual data in the message (for the 50 one)

#

I can see some parts in it, but I have no clue what the overall message before the 50 means

#

you would need to find some api reference to tell you what it actually means

tranquil junco
haughty mountain
#

and when you know the format you can write some code to parse it

tranquil junco
#

this is the format, so for a dirty job, a the first 4 bythes can be ignored.

haughty mountain
#

I mean, parsing the frame itself is simple enough

#

but what about the data inside it?

tranquil junco
haughty mountain
#

if you just want a pretty broken and hacky way, just check the end of the string, ignoring the last character

#

but this will easily break for frame data different to this

tranquil junco
#

I know, I am just creating a poc, right now.

haughty mountain
#

0x90 looks like "receive packet"

tranquil junco
#

yup, but how is that makes it easyer to extract the on/off/50?

haughty mountain
#

do you want to parse the packet or not?

tranquil junco
#

yes I do πŸ™‚

haughty mountain
#

a super hacky thing is s[:-1].endswith(b'50') or similar

tranquil junco
#

Don't meant to be rude

haughty mountain
#

if you want to parse the packed properly you need to figure out what the data means

#

if you just want something hacky you can do the hacky thing that's likely to break

tranquil junco
#

okay, I think I ned to do a little bit more research.

#

thanks.

haughty mountain
#

have you looked whether there are any libraries for this?

#

or do you want to do it yourself from the raw data?

tranquil junco
#

there is xbee.decode, but that is only avaible on xbee deviceces. I am tring to process this data on a rp2040.

haughty mountain
#

relevant part of the user guide

image.png
#

annoyingly the docs aren't exactly linkable...

tranquil junco
haughty mountain
#

this thing has the actual descriptions of the frame formats

tranquil junco
#

thank you for pointing me to the right direction

shut breach
# tepid basin how did you get this?

first thing to notice is that each call is just constant + the recursive call, so we can reduce the question to how many function calls are required
next thing is that n is reduced each time by taking the square root, so the question becomes how many times can we take square root of n before reaching the base case
that sequence in reverse is squaring n repeatedly, and as algmyr showed, the ith term can be written explicitly as a_i = x^(2^i)
rearrange to get log(a_i) = 2^i and again to get log(log(a_i)) = i

haughty mountain
#

!e there probably are a lot nicer tools for this, but...

import struct

def parse_receive_frame(s: bytes):
  start_delim, size = struct.unpack('>BH', s[:3])
  data = s[3:3+size]
  checksum = s[3+size]

  print(f'{size = }')
  print(f'{checksum = }')

  assert data[0] == 0x90
  header_fmt = '>BQHB'
  header_size = struct.calcsize(header_fmt)
  frame_type, source_addr_64, source_addr_16, recv_opts = struct.unpack(header_fmt, data[:header_size])
  
  print(f'{hex(frame_type) = }')
  print(f'{source_addr_64 = }')
  print(f'{source_addr_16 = }')
  print(f'{recv_opts = }')

  recieved_data = data[header_size:]
  print(f'{recieved_data = }')

s = b'~\x00\x0e\x90\x00\x13\xa2\x00A\xe1%#\xff\xfe\xc150-'
parse_receive_frame(s)
halcyon plankBOT
#

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

001 | size = 14
002 | checksum = 45
003 | hex(frame_type) = '0x90'
004 | source_addr_64 = 5526146546476323
005 | source_addr_16 = 65534
006 | recv_opts = 193
007 | recieved_data = b'50'
haughty mountain
#

@tranquil junco this

#

struct is annoying in that it can only read fixed size stuff

#

I imagine there are a lot nicer binary parsing libraries

#

but this should get the point across

#

it's just using the information given in the user guide

swift breach
#

you can use unpack_from and a starting offset to not slice bytes repeatedly

fiery cosmos
# snow anvil ```py def findKthPositive(arr, k): prev = 0 count = 0 for i, num in ...

you can observe that to get the number of missing numbers at a given index of the array ,say 'i' would be arr[i] - i - 1. So u do a binary search to find the index where the no of missing numbers is equal to k. The index + k gives u the kth missing value.

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        return k + bisect_left(range(len(arr)), 0, key=lambda i:(-1, 1)[arr[i] - i - 1>=k])

you can refer to the solutions posted in the solution tab for getting a better understanding.

boreal schooner
#

Hey guys, say I have the following array:

[
  {'field': FIELD_1, 'value': {NESTED_KEY_1: NESTED_VALUE_1}},
  {'field': FIELD_2, 'value': {NESTED_KEY_2: NESTED_VALUE_2}},
  {'field': FIELD_1, 'value': {NESTED_KEY_3: NESTED_VALUE_3}},
  {'field': FIELD_3, 'value': {NESTED_KEY_4: NESTED_VALUE_4}},
]

But I want it to become like this:

[
  {'field': FIELD_1, 'value': {NESTED_KEY_1: NESTED_VALUE_1, NESTED_KEY_3: NESTED_VALUE_3}},
  {'field': FIELD_2, 'value': {NESTED_KEY_2: NESTED_VALUE_2}},
  {'field': FIELD_3, 'value': {NESTED_KEY_4: NESTED_VALUE_4}},
]

What would be the most performatic way to do so?

upper hearth
#

I want to get started with data structures and algorithms. How to get started

haughty mountain
#

imo the saner thing to want at the end is a dict instead

#

dict mapping field to dict of values

#

i.e.

joined_dict = {}
for your_dict in your_list_of_dict:
  field = your_dict['field']
  value = your_dict['value']
  if field not in joined_dict:
    joined_dict[field] = {}
  joined_dict[field] |= value
fiery cosmos
crude pike
#

Hi, could I know what is the base class of python?

#

like in objective c it was NS-Object

#

basically everything at its foundation was NS-object

#

is there something like object that is the base class that all python rest on?

lament totem
#

object

#

@crude pike

crude pike
#

@lament totem are integers and str also using object as their base?

lament totem
#

Sometimes people explicitly write

class MyClass(object):
    pass
lament totem
crude pike
#

i know in javascript numbers are actually primitives and do not follow the javscript's base class

lament totem
#

Well ints and strings are classes

#

But they are a bit different from other/custom classes because they are used a lot, so they are optimized a bit more.

#

It's for example not completely straight-forward to inherit from them

crude pike
#

for type annotations if I want the class to be flexible can I just use object??

lament totem
#

You would use Any iirc

crude pike
#

wait there's a annotation called "Any"

lament totem
#

yes

crude pike
#

thx!

lament totem
#

from typing import Any

flat sorrel
#

Note that Any differs from object in that Any is much more permissive (you can assign a value with Any type to any variable, but you can only assign a value with object type to a variable that has object or Any type)

crude pike
#

@flat sorrel do you have examples of any data type that is not based on object?

flat sorrel
#

!e

print(isinstance(None, object))

class MyMetaclass(type):
    pass

class MyClass(metaclass=MyMetaclass):
    pass

my_obj = MyClass()
print(isinstance(my_obj, object))
halcyon plankBOT
#

@flat sorrel :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | True
002 | True
flat sorrel
#

However, the converse is not true (an object is not everything else) - in fact, object is not a subclass of any other class, hence the assignment rules

crude pike
#

hi why is ColumnEnum not defined in the last statement?

# 
from typing import List


class Constants:
    class ColumnEnum(str, Enum):
        resale_price = "resale_price"

    LABEL_COLUMN_NAME = ColumnEnum.resale_price.value```
flat sorrel
#

!e

from enum import Enum
from typing import List


class Constants:
    class ColumnEnum(str, Enum):
        resale_price = "resale_price"

    LABEL_COLUMN_NAME = ColumnEnum.resale_price.value

print(Constants.LABEL_COLUMN_NAME)
halcyon plankBOT
#

@flat sorrel :white_check_mark: Your 3.11 eval job has completed with return code 0.

resale_price
flat sorrel
crude pike
#

weird only works when i move the ColumnEnum outside of Constants

#

is it because I am calling this the LABEL_COLUMN_NAME from another file?

blissful ginkgo
#

So I'm still struggling with that Katamino solver I bothered you the other day...I don't understand this:

                   [1, 1],
                   [1, 1]])

mask = pentamino == 1
to_place = 1

board = array([[ True,  True,  True],
               [ True,  True,  True],
               [ True, False,  True],
               [False, False,  True],
               [False, False,  True]])

pos = array([2, 0])

board[
    pos[0] : pos[0] + pentamino.shape[0], pos[1] : pos[1] + pentamino.shape[1]
] = np.where(
    mask,
    to_place,
    np.where(
        np.logical_not(mask),
        board[
            pos[0] : pos[0] + pentamino.shape[0],
            pos[1] : pos[1] + pentamino.shape[1],
        ],
        0,
    ),
)

---

board = array([[ True,  True,  True],
               [ True,  True,  True],
       -----> ?[False,  True,  True],
               [ True,  True,  True],
               [ True,  True,  True]])

Why does this cell flip? How do I place this piece on its location without flipping this cell?

haughty mountain
#

!e

from numpy import array
import numpy as np

pentamino = array([[0, 1],
                   [1, 1],
                   [1, 1]])

mask = pentamino == 1
to_place = 1

board = array([[ True,  True,  True],
               [ True,  True,  True],
               [ True, False,  True],
               [False, False,  True],
               [False, False,  True]])

pos = array([2, 0])

board[
    pos[0] : pos[0] + pentamino.shape[0], pos[1] : pos[1] + pentamino.shape[1]
] = np.where(
    mask,
    to_place,
    np.where(
        np.logical_not(mask),
        board[
            pos[0] : pos[0] + pentamino.shape[0],
            pos[1] : pos[1] + pentamino.shape[1],
        ],
        0,
    ),
)

print(board)
halcyon plankBOT
#

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

001 | [[ True  True  True]
002 |  [ True  True  True]
003 |  [ True  True  True]
004 |  [ True  True  True]
005 |  [ True  True  True]]
haughty mountain
#

looks like it works, no?

blissful ginkgo
#

Hm...I'm getting something else in debugger, let me check again

haughty mountain
#

also, why not just do

board[
    pos[0] : pos[0] + pentamino.shape[0], pos[1] : pos[1] + pentamino.shape[1]
] |= pentamino
#

and it' might be neater to just work with 1/0 rather than True/False

#

!e so it boils down to something like

import numpy as np

pentamino = np.array([[0, 1],
                      [1, 1],
                      [1, 1]])

board = np.array([[1, 1, 1],
                  [1, 1, 1],
                  [1, 0, 1],
                  [0, 0, 1],
                  [0, 0, 1]])

y, x = [2, 0]
height, width = pentamino.shape

board[y:y + height, x:x + width] |= pentamino

print(board)
halcyon plankBOT
#

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

001 | [[1 1 1]
002 |  [1 1 1]
003 |  [1 1 1]
004 |  [1 1 1]
005 |  [1 1 1]]
haughty mountain
#

+= might also be an interesting alternative to |=

#

they should be equivalent if you only place things in valid ways

blissful ginkgo
#

I'll try your advice, I'm just slow and have to go 1 by 1 πŸ™‚

haughty mountain
#

but if you mess up you get numbers larger than 1, which might be a good way to catch some bugs

blissful ginkgo
#

I moved True/False to 1/0, swapped my logic with |= you suggested and it solved 5x3 board! πŸ™‚ I'm running it with 5x12 now, it seems it will take a while (I hope I don't have an endless loop somewhere)

outer rain
# blissful ginkgo I moved True/False to 1/0, swapped my logic with `|=` you suggested and it solve...

If you simply iterate though every single combination of positions of pieces (even with some pruning), at 50 tiles board with 10 pieces it may take up to 50^10 = a lot of combinations (even if your pruning is good enough to reduce 50 tiles to 5 on average, 5^10 is still a lot, and with 100 tiles and 20 pieces it begins to be about as much). If I was you I would have just used sat solvers from the beginning (google "sat-solvers", "eight queen problem and sudoku using sat solvers", and "pycosat" if you want to learn more). But I have to say that using them will turn your program into pure magic.

And I am also pretty sure that this is the only option that solves katamino fast, because katamino is "stronger" than rectangle packing problem, which is NP-complete.

blissful ginkgo
#

Good info, thanks. I have some logic in my solver where after I place a pentamino I check if there's "an island" with less than 5 cells, and if there is, I don't go down that path. I hope that it will make it good enough to solve in "reasonable" amount of time.
Funny story, my partner solved it in 20 minutes by hand without any prior knowledge πŸ™‚

naive oak
#

how do you guys usually learn a new algorithm? do you implement it first and then try and understand it or understand it and then implement?

flint river
#

would it be possible to create a decorator which has the exact same function as the @ static method and @classmethod?

agile sundial
unborn sundial
unborn sundial
naive oak
agile sundial
#

pretty much, yeah

naive oak
somber breach
#

arr=[8,10,17,1,3,4]
def pivotofarr(arr):
start=0
end=len(arr)-1
while (start<end):
mid=(start+end)//2
if (arr[mid]>=arr[0]):start=mid+1
elif (arr[mid]<=arr[0]):end=mid
return(start)
pivotofarr(arr)

why do we use start<end here and why not start<=end as in binary search any help? thanks in advanceπŸ˜‡
blissful ginkgo
fiery cosmos
fiery cosmos
# somber breach arr=[8,10,17,1,3,4] def pivotofarr(arr): start=0 end=len(arr)-1 whil...

Using start <= end as the condition for a binary search while loop can cause an infinite loop if the update statements for start and end don't guarantee that the search space is reduced on each iteration. It's recommended to use a condition such as start < end, along with appropriate update statements, to ensure that the loop will eventually terminate.
In this case, the update statements would be adjusted to ensure that mid is not included in the next search space, such as start = mid + 1 and end = mid - 1. This condition and update scheme ensure that the loop will eventually terminate, either by finding the target element or exhausting the search space.

somber breach
#

Thank you so much for the help , really appreciate you man 😊

magic holly
#

guys explain me please,if in python everything is an object and every object is an instance of class ,then does python have a basis class where any object is an instance of that class ,but the basis class is not an instance of any different class or this instance class sequence goes to infinity?

agile sundial
#

everything is an subclass of object

dusky trellis
#

even classes are themselves objects

#

of class type (which are also subclasses of object)

agile sundial
#

classes are instances of type, which is also an instance of type

dusky trellis
#

so classes in python can be recursive!

#

fun times

magic holly
#

is type instance of object class?

agile sundial
#

yep

dusky trellis
#

the type class is a subclass of object class

magic holly
#

then type is instance of both object and type?

agile sundial
#

yep

dusky trellis
#

a particular type (i.e. as setup by a class declaration) is an instance of type class. and thus also an instance of object class. Thus, the type class which is itself a class, is also an instance of type and thus an instance of object.

#

iow, type is both a subclass of object and and instance of type and of object. it's recursive!

magic holly
#

so as i understood ,object is the basis class which is not an instance of any other class?

dusky trellis
#

object is a class, thus an instance of type

#

(and thus, also an instance of object)

magic holly
#

it is interesting to see how this recursion work in practice

#

thank you for explanation

dusky trellis
#

well, be aware, I was using the term "recursive" in a poetic sense

#

technically, in programming, recursion is used to describe flow control, rather than data referencing itself

#

(though that's not exactly uncommon either, now that I think about it)

#

that seems likely

lean walrus
#

Because why not? 0x02 is the same as 2 and 0b10.
Hex is usually more convenient than decimal and sometimes more convenient that binary

dusky trellis
vocal gorge
#

this looks slightly weird tbh, since it's equivalent to currentFont.attribute = currentFont.attribute if currentFont.attribute else 0x02, so it only sets boldness if no other attribute is set

#

I'd have expected to see a bitwise OR, | 0x02

lean walrus
dusky trellis
#

looks like something that should be reserved for rare instances

dusky trellis
haughty mountain
#

because people like to nibble on nibbles

#

it's a bit suspicious to do logical or there

#

if you use bitflags that should be a bitwise or

#

currently the behavior is "only make bold if text is unstyled"

halcyon plankBOT
hexed pendant
lean walrus
night minnow
#

hey, any advice on where can I get started with dsa?

shut breach
night minnow
somber pilot
#

I am pretty sure that it is a stupid mistake but I am going crazy over it. Can someone help me.

def text_to_immage_array(text, rx, cx): 
    array = [[0]*cx]*rx
    i = 0

    for c in range(cx):
        for r in range(rx):
            try:
                array[c][r] = text[i]

            except:
                array[c][r] = 0
            
            i += 1

    print(array)

    return array

x1 = "100010000101001100001100101001000000000011000000010011010111101001010010001100000100000000000100000000000101"

image_encode(x1, 12, 12)

Output:

Array = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

It doesn't change the array.
However

...
try:
  array[c][r] = text[i]
  print(array[c][r])
...

When I do this. It prints what it is supposed to.

Please help I am going mental.

jolly mortar
#

currently all rows are references to the same list oject

somber pilot
jolly mortar
#

also having a bare except is considered a bad idea, you should specify which error that except block is meant to handle

#

eg except IndexError:

somber pilot
#

I found it easier to add 0s to text

snow anvil
#

for https://leetcode.com/problems/koko-eating-bananas/description/

my solution is not quite correct any help would be appreciated

def minEatingSpeed(piles, h):
    if len(piles) >= h:
        return max(piles)
    piles = sorted(piles, reverse=True)
    k = max(piles)
    high = max(piles)
    low = max(piles)//2
    count_hrs = h
    while count_hrs != 0:
        if count_hrs > 0:
            high = k + 1
            k = (high - low)//2
        else:
            low = k - 1
            k = (high + low)//2
        print('k = ', k)
        if k == 1:
            return k
        count_hrs = h
        for pile in piles:
            #time_to_eat = -(pile//-k)
            count_hrs -= -(pile//-k)
        print('alloted_time - time_taken_to_eat = ', count_hrs) 
   return k
LeetCode
LeetCode - The World's Leading Online Programming Learning Platform

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

#

I also did a hacky linear search in the range from low to high at the end but that predictably exceeds the time limit

# 
    for k in range(low, high):
        hours = h
        for pile in piles:
            hours -= -(pile//-k)
        if hours == 0:
            return k

this is what I added at the end to make it spit out the correct results but it's just too slow

fiery cosmos
snow anvil
#

well at least even with fixed code this is too slow

lunar jacinth
#

best algo book that helps with interviews?

haughty mountain
#

for your own sanity, make a function hours_needed(piles, k) that returns the number of hours needed at speed k

#

and then write a nicer binary search

#

e.g.

# binary search in k,
# keep l as not possible, r as possible
l = 0
r = max(piles)

while r - l > 1:
  mid = (r - l)//2
  if hours_needed(piles, mid) <= h:
    r = mid  # possible
  else:
    l = mid  # not possible

# answer is `r`, the smallest k that is posssible
bronze junco
#

Any rules to make a question? I'm a newbie. Or can I just ask...?

haughty mountain
#

generally just ask, if it's a general python question you can ask in #python-discussion, the channels in this section are more specialized

bronze junco
#

Oh okay. Then. It's about Algorithm. But I guess it's bigger question so. I will head to #1035199133436354600 thank you!

haughty mountain
#

and no messy +1 or -1 that pops up in most people's implementation

lyric burrow
#

hey, i've been trying to solve this problem called Roman to Integer https://leetcode.com/problems/roman-to-integer/
and here's what i came up with until now:

class Solution:
    def romanToInt(self, s: str) -> int:
        sum = 0
        
        translate = {
            'I' : 1,
            'V' : 5,
            'X' : 10,
            'L' : 50,
            'C' : 100,
            'D' : 500,
            'M' : 1000
            }
        for idx, ele in enumerate(s):
            if translate[s[idx+1]]>translate[ele]:
                sum+=translate[s[idx+1]]-translate[ele]
                if s[idx+1] is s[-1]:
                    break
            else:
                sum+=translate[ele]

        return sum

it gives me a runtime error saying String Index Out of Range:

    if translate[s[idx+1]]>translate[ele]:
Line 15 in romanToInt (Solution.py)
    ret = Solution().romanToInt(param_1)
Line 47 in _driver (Solution.py)
    _driver()
Line 58 in <module> (Solution.py)```
LeetCode
LeetCode - The World's Leading Online Programming Learning Platform

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

haughty mountain
bronze junco
#

thank you very much 😊

haughty mountain
keen hearth
haughty mountain
#

fwiw, doing the conversion in reversed order is more convenient imo

restive harbor
#

Hi guys ! I would like to know whether there exists a built-in function that calculates the product of each element of a list of int please πŸ˜„

keen hearth
tranquil junco
#

hey-hey! πŸ™‚
I am facing terrible issue/challenge.
I collecting data from digital input. I don't know precisely when it starts, or when it ends, So the result looks like this:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

The samleing freq is approximetly 6-7 faster then the input data so the output should be this : 01010101010010101010
it is manchester coded but that part is not important. the end end result is this 111110000
My question is how to clear it up? If I remove the duplication i can lose a bit where same bits are follows eachother, so that is not an option.

restive harbor
keen hearth
#

I'm sure there's a proper signal processing way to do it, but perhaps you could break it into groups of consecutive 0s/1s then divide the length of each group by 6 and round.

tranquil junco
#

My idea is to breakit up by signal changes.
create like a list...
1: 6
0:7
1: 14
then loop through again, and append an array based on that.
if the lenght is lover then 12 then it is a 1/0
if it is higher than than it is two 1/0

keen hearth
#

So for each consecutive group of bits, you just need to decide between whether that group represents 1 or 2 bits.

tranquil junco
keen hearth
#

!e ```py
from itertools import groupby

def process(bits):
for key, group in groupby(bits):
n = 1 if len(list(group)) < 9 else 2
for _ in range(n):
yield key

bits = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

print(list(process(bits)))

halcyon plankBOT
#

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

[0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0]
keen hearth
#

Not the most elegant but Β―_(ツ)_/Β―

tranquil junco
#

wow.

#

nice

#

thank you! πŸ™‚

#

it is sofistacated by my standards πŸ™‚

#

the issue is that there is no groupby in micropython. But I can write that with no issue

keen hearth
crude galleon
#

hello, I got a question about data structures. So i am trying to solve a problem in java where I have a large csv file with dates and values. the idea is to do various operations based on the start-end date input of the user. stuff like taking the average of values between the inputted start-end date.

now it seemed like TreeMap made sense for purposes of reading the file as I can turn the dates into keys, and everything else into values but I was curious how should I make my TreeMap. The lines in the file look like this "1946-01-02;13:00:00;-0.2;G" and I am using the ; as the separator

I just dont know if If I should do TreeMap<Integer,Integer> or something else

agile sundial
#

you could parse the time into a timestamp

crude galleon
#

for what purposes ?

#

never worked with timestamps so i dont know much about what i can do with it

iron vector
#

Hello,

I recently did Recursion in Python, I was then tasked to write a script using a recursive function for: Fibonacci Sequence.

My Implementation was:

`def get_fib(position, a=1, b=1):
if position <= 2:
return b

else:
    z = a
    a = b
    b = z + b

    output = get_fib(position - 1, a=a, b=b)
    return output`

But the implementation I studied later was:

def fibonacci_recursive(n): if n <= 1: return n else: return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

A little short yes, but I think slows down a lot when generating a big sequence, for which devs use Memoization to make it very efficient.

Is my approach wrong ? what will the time complexity be of my approach ?
As per my approach it generates the sequence near instantly upon running the script, although I do run into recursion error, when generating a sequence over N =1000.

Kindly guide me πŸ™‚

snow anvil
lament totem
agile sundial
#

it's actually worse, the time complexity is fib(n)

lament totem
#

hmm

#

Well anyways it's bad πŸ˜›

lament totem
#

If you just care about readability then you pick the 2nd algorithm you show. And yours is more of an iterative-ish approach

iron vector
#

I think to get the best readability & time complexity, I should go for:

  • from functools import lru_cache

set lru_cache as the decorator over the second approach.

iron vector
iron vector
agile sundial
iron vector
# agile sundial do you know what time complexity is?

Yes I have been learning about it,

O(n) -> is for Linear, but I didn't get what you meant by fib(n) and which is actually worse ?

As per what I have studied and @lament totem has said the second approach without Memoization is worse.

agile sundial
#

well fib(n) is the nth fibonnaci number

snow anvil
#

do you mind not posting in the wrong channel all the time

#

no

twin void
#

Hello guys, i need help with an algo, is there anyone who would be willing to help personally

#

I have two different tables in a db. The first table contains a data which has a latitude and longtitude. I then have a census_block_group as the second table. I need to query for where the latitude and longtitude in the first table appears in the census_block_group table and then join that value with the data in the first table and write to another table. Right now, the issue i'm having is how to look for situations where the latitude and longtitude in the first table corresponds to the latitude and longtitude in the second table.

There might not be an option for specificity(an exact match) between the lat and long of both tables but at least they shouldn't be far off. Chatgpt suggested i use a tolerance level which can be gotten by subtracting the latitude of one table with another table and if that is within my tolerance value range, then i would do the same for the longtitude. The issue is, how can i calculate the tolerance value when making the query as i have to retrieve it with sqlite queries. What would be your advice on implementing an algo to do this

naive oak
twin void
#

Anyone willing to help with an algo

robust dagger
twin void
fiery cosmos
# 
class Single:
    def __init__(self,
                 window: pygame.Surface,
                 background_colour: pygame.Color = colour.black,
                 player_colour: pygame.Color = colour.white,

                 # colours
                 enemy_colour: pygame.Color = colour.red,
                 enemy_num: int = 10,

                
                 # difficulty
                 size: int = 20,
 
                 player_speed: int = 10,
                 min_speed: int = 5,
                 max_speed: int = 10,
 
 
                 # appearances
                 player_trail: int = 50,
                 trail_fade = 0.1
        
                 ) -> None:
        
        self.window = window
        self.background_colour = background_colour
        self.player_colour = player_colour
        
        self.enemy_colour = enemy_colour
        self.enemy_num = enemy_num
        
        self.size = size
        
        self.player_speed = player_speed
        self.min_speed = min_speed
        self.max_speed = max_speed

        self.player_trail = player_trail
        self.trail_fade = trail_fade
#

am i doing it the right way or is there a more efficient way?

lean walrus
#

you can use @dataclass

#

!d dataclasses.dataclass

halcyon plankBOT
#
dataclasses.dataclass 

@dataclasses.dataclass(*, init=True, repr=True, eq=True, order=False, unsafe_hash=False, frozen=False, match_args=True, kw_only=False, slots=False, weakref_slot=False)```
This function is a [decorator](https://docs.python.org/3/glossary.html#term-decorator) that is used to add generated [special method](https://docs.python.org/3/glossary.html#term-special-method)s to classes, as described below.

The [`dataclass()`](https://docs.python.org/3/library/dataclasses.html#dataclasses.dataclass "dataclasses.dataclass") decorator examines the class to find `field`s. A `field` is defined as a class variable that has a [type annotation](https://docs.python.org/3/glossary.html#term-variable-annotation). With two exceptions described below, nothing in [`dataclass()`](https://docs.python.org/3/library/dataclasses.html#dataclasses.dataclass "dataclasses.dataclass") examines the type specified in the variable annotation.

The order of the fields in all of the generated methods is the order in which they appear in the class definition.
vocal gorge
#

What would be a good way to evaluate this without exceeding 64-bit float limits? Ξ± and Ξ² will be small (-1 or +1, maybe) but not necessarily floats (so these aren't factorials, and so can't be computed as ints), and m can be up to e.g. 1000.

#

the output can be assumed to be small, but none of the parts of this are

#

oh, I can probably compute the log of this expression, because scipy provides gammaln

#

or alternatively, this seems to be two Pochhammer symbols

#

yeah, it's equivalent to poch(m,Ξ±+1)/poch(m+Ξ²+1,Ξ±+1), and this seems to be computable for m=1000, great.

#

correction: poch(m+1,Ξ±)/poch(m+Ξ²+1,Ξ±), I can totally count

fiery cosmos
#

such as pygame.Color

#

i tried and it doesn't allow it

lean walrus
fiery cosmos
#

but if this layout is practical, im not doing anything wrong ig

lean walrus
#

Dataclasses do allow any parameters

fiery cosmos
#

they dont... that's why i do it this way

lean walrus
#

What error message do you see?

fiery cosmos
#

forgot but its mutable parameters lemme dive into my search history

#

ah there
mutable default <class 'pygame.color.Color'> for field background_colour is not allowed

lean walrus
vocal gorge
#

you do it like = field(default_factory = lambda: Color(whatever)), or see dataclasses docs

fiery cosmos
#

ohno

#

nvm im not changing it takes too much time

fiery cosmos
#

okay im changing it dammit

iron vector
#

Can anyone here recommend me a good source to learn about recursion ?

fiery cosmos
#

why people use recursion fr

#

its confusing

crude galleon
#

is O(nlogn + d * h) bad ?

#

(d * h), where d is the number of days between dateFrom and dateTo (inclusive), and h is the maximum number of hourly measurements for any given day.

iron vector
snow anvil
#

Recursion is not my preferred method to use because of the depth limit

snow anvil
#

And we can't know if it's bad because we don't know the problem you are trying to solve

outer rain
snow anvil
snow anvil
outer rain
# iron vector Can anyone here recommend me a good source to learn about recursion ?

I can't really recommend a source, but I can recommend a perfect way to master it after you get the gist: try drawing fractals with turtle module. It's very easy to learn and you will visually see the results almost instantly. Start with a simple ones: like a put a square into a square into a square ... Then try Sierpinski triangle, then something even more advanced like Pythagoras tree, etc. It's very satisfying!

outer rain
outer rain
# crude galleon hello, I got a question about data structures. So i am trying to solve a problem...

is O(nlogn + d * h) bad ?
You are referring to this, right? Is my understanding correct: you want to perform range requests based on a date. The data fits into RAM, performance matters a lot, O(n) per request is too much. Is O(sqrt(n)) per request ok or is O(log n) required? Does data change between requests? And what kind of range requests exactly? You mentioned average of values, which is equivalent to sum on range + count on range, anything else? What timespan you are working with? Decades/Years/Months/Weeks? What's the dataset size approximately?

haughty mountain
#

for static data you can make queries O(log n) easily

#

prefix sum + binary search to get sum/average in a range

austere sparrow
#

What are some data structures/algorithms commonly used in text editors? Not just plain text editors, but perhaps also "rich" editors like Word

agile sundial
#

πŸͺ’ ||(rope)||

agile sundial
#

rope is actually a thing, though

austere sparrow
#

Yeah rope sounds like a useful thing as well

austere sparrow
agile sundial
#

This makes the gap buffer a simpler alternative to the rope for use in text editors[1] such as Emacs.[2]
huh, never heard of it before, seems interesting

agile sundial
#

i should make a markdown editor for my blog πŸ€”

#

and then write a blog post about it

austere sparrow
# agile sundial no u πŸ˜›

well, that's actually a serious comment πŸ™‚

  • Rust uses a dynamic array storing UTF-8 data for &str and String, then there's also OsStr[ing], CStr[ing]; then there are persistent data structures where you can technically store chars... or small arrays of chars...
  • Haskell is notorious for the number of string types it has
  • Python has a bit of an unusual string encoding which allows for O(1) access and decent memory efficiency for ASCII-only strings
  • JavaScript IIRC stores UTF-16 codepoints
opal oriole
#

Gap buffer is probably the way to go. Rope is more complicated with not really any gain it seems (IIRC Emacs is gap, and Vim is rope (I don't notice a difference)).

agile sundial
opal oriole
#

string is not dynamic, just pointer and length.

#

string builder lets you actually append to it and all that, it can be cast to a string.

#

This seems to be what most (compiled / fast / low level ("systems programming languages")) languages are converging to (C++, Rust, Zig, Odin, etc)

austere sparrow
#

Well, in Rust a String is mutable

opal oriole
#

Yes, Rust has different names.

#

&str is string.

bronze hillBOT
#
Command not found

Command "str" is not found

opal oriole
#

The others are for dealing with foreign (C) functions and the OS stuff.

#

And some other loose ends.

austere sparrow
opal oriole
#

The reason for this split is for ownership reasons and such.

#

And they are just two different things (static vs dynamic).

agile sundial
#

and πŸ„ strings πŸ₯Ί

opal oriole
#

(Having them be the same thing like in C++ in the past has caused issues, including bringing chrome (or was it firefox?) to a grinding halt because each time you type into the search bar it did a ton of copies and reallocation of the strings and stuff (no clear separation of string and string builder))

austere sparrow
#

I suppose the Python equivalent would be keeping a list of str chunks and then "".joining them

opal oriole
#

I don't think Python cares about this problem. For a long time it was assumed that just having a single dynamic string type was fine.

#

And now many languages are stuck with it and/or don't care.

austere sparrow
#

you mean a mutable string?

opal oriole
#

Separation into two solves multiple problems at once. Which is why newer languages like Rust are doing it. Making use of hindsight.

#

(The concept has also been back-ported to languages like C, where new projects have two string types (or more for stuff like UTF-16) (well actually they have already been doing this for a long time, especially when they could not afford to have every string be dynamic, it (and many other concepts) went away for a while when computational power and memory suddenly exploded)))

crude galleon
# outer rain > is O(nlogn + d * h) bad ? You are referring to this, right? Is my understandin...

I have a range of data starting from 1950 or something and ends around 2020. A majority of that time frame is also based on 24 hours. So like there is 24 instance of 2020-10-10 starting from 00:00 to 23:00. I am suppose to choose a start date and end date which can range between whatever, and do operations like take average of temperature of each day, calculate how many of the days are missing how many instances (like 1950-10-10 has only 3 instance of reappearing) etc. those kind of operations

haughty mountain
#

but if you have specific operations that you want to be fast you can typically do better

crude galleon
#

This is a very static program. So only 3 different operations I need to do

outer rain
#

all of these can be answered in O(log n) using binary search on datetime array and prefix sums on the data array

haughty mountain
#

yeah, that

#

I mentioned it earlier

#

any sum-like query can be done with prefix sums at the cost of the initial O(n) set-up

outer rain
#

Actually 70 years is not that may hours so you can even omit binary search

haughty mountain
#

you want to store in some array with hour resolution?

#

I guess that works with prefix sums, yeah

crude galleon
#

Well there is a bit more to data. It’s Date;hour;temperature;approval/disapproval letter

#

I used a multivalueMap

#

Dates for key. Everything else is value

haughty mountain
#

(date, hour) is the key, no?

crude galleon
#

Hours are also in the value

#

Only date is key

haughty mountain
#

why?

#

you can just make date and hour into a timestamp or whatever

outer rain
crude galleon
#

I can post my code if you guys don’t mind reviewing it. It’s a short class

#

Only 4 methods

halcyon plankBOT
#

Hey @crude galleon!

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

crude galleon
#

this is the code in java

outer rain
#

You store time in some extremely overcomplicated way

#

you can count amount of days between the date and 1 jan 1950, multiply it by 24 and add the hours. This gives you a single integer

#

Then just put your entries into array by index of that integer

#

this may even take less memory

haughty mountain
#

if the data is somewhat dense it might, yeah

#

if the data is sparse it's not too bad anyway

#

it's ~600k hours in 70 years

#

also, I would really recommend parsing the data once rather than re-parsing during queries

#

what I would probably do is to have some class for the value which can hold date, hour, temperature, approval

#

and then put them into an array according to (date, hour) converted to time like @outer rain described

#

then you can do the prefix sum precomputations on top of that to be able to answer queries quickly

#

actually, maybe don't store the values in an array like that pithink

#

you only need to store the prefix sums of specific values in such arrays

#

!e prefix sum example

# (time, value) pairs.
data = [
    (5,  5),
    (10, 7),
    (12, 5),
    (13, 12),
    (17, 8),
    (40, 10),
    (55, 17),
]

max_time = max(d[0] for d in data)

# Build prefix sum array.
prefix_sum = [0]*(max_time + 2)
for d in data:
  prefix_sum[d[0]] = d[1]
for i in range(1, len(prefix_sum)):
  prefix_sum[i] += prefix_sum[i-1]

def query_sum(prefix_sum, l, r):
  """Sum in range [l, r)."""
  return prefix_sum[r] - prefix_sum[l]

print(f'sum of range [11, 20) is {query_sum(prefix_sum, 11, 20)}')
halcyon plankBOT
#

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

sum of range [11, 20) is 25
fiery cosmos
#

Hi guys, I have created a chatbot and I am working on it, already created datasheet of 20k+ sentences, now i need to work on algorithm, if someone is interested in working with me, can dm me

5.png
haughty mountain
#

this is not a bulletin board for work

green temple
#

Can anyone suggest me best dsa course with python implementation. I can only find good courses with c++ and java. Someone please help me find a good course for python DSA.

haughty mountain
vocal gorge
outer rain
vocal gorge
#

oh, I misread, I thought you said O(n) precalc, like e.g. prefix sums

outer rain
#

Yes, with O(n) precalc the reversibility is mandatory I think. You would probably be able to sort in O(n) otherwise or something

wraith siren
#

Why is python -m timeit -s "xs = 'a' * 50 " "len(set(xs)) == 1" so much faster than python -m timeit -s "xs = 'a' * 50; x=xs[0]" "all(x == c for c in xs)" ( 679 nsec per loop vs 2.99 usec per loop)?
Does set run C underneath?

outer rain
#

len(set(xs)) == 1 is O(1) python operations, all(x == c for c in xs) is O(n) python operations

haughty mountain
outer rain
#

to be even clearer T1(n) = O(1) + n * C_hash_map_const vs T2(n) = O(1) + n * py_comparasion_and_generator_const, but C's const is an order smaller

wraith siren
#

Thanks for the confirmation!

crude galleon
haughty mountain
#

If I change the date span, would the number of operations change?

#

If I change the number of elements in the data structure, would the number of operations change?

crude galleon
#

Hmm, changing the date span would just add extra iterations to the code

#

on average temperatures I also iterate over each hours in a given day so I can calculate the sum of average then divide it accordingly

#

so i iterate over each day + each hour

haughty mountain
#

Trying to give a tight bound for your approach is pretty awkward. And the worst case kinda sucks. I think the worst case is ||O(number_of_days_in_range + number_of_data_points)||

#

(which kinda sucks compared to how quick you can make it with some precomputations)

crude galleon
#

yeah, tbh I did went into this endeavor without a whole lot of knowledge so it was kinda brute forcing my way to a solution

#

there is much to improve and learn

#

when I started in the beginning it seemed like a good decision to go for a map. maybe I could have go for a binary tree

#

but i was not sure how binary tree would look like for it

#

like would the binary tree nodes depend on the dates?

#

and then same date can appear several times so would that work with a binary tree? like as an example there is 2020-10-10 13:00 and 2020-10-10 19:00

haughty mountain
#

see the discussion from before, you can easily combine the date and the hour into one timestamp

#

and then you have a unique key

crude galleon
#

but would that not count way more keys ?

#

this is not the exact case but assuming each hour of the day has a measurement of tempretare that's basically 23 extra keys for each date ?

#

but perhaps more keys is not the problem ?

haughty mountain
#

it's only a problem because of how you've implemented your methods

#

they scale with the date range

#

it doesn't have to

#

(but yes, there aren't a huge number of keys either)

#

but doing O(number of hours in range) work would be a lot per query

#

as discussed before, using a prefix sum you can get the queries down to O(1)

#

at the cost of some space and some work at the beginning

crude galleon
#

I will check out what prefix sum is

#

and learn it

haughty mountain
#

I gave an example earlier

haughty mountain
#

the idea is very simple, for some data like [1, 2, 3, 4] you compute the sum of prefixes

so sum of [], sum of [1], sum of [1, 2], ...

#

and you get [0, 1, 3, 6, 10] for my that data

#

now by computing differences you can get the sum for subarrays

#

e.g. the sum of the range [2, 3] would be computed like [1, 2, 3] - [1]

#

both of those prefix sums we already have computed

[0, 1, 3, 6, 10]
    ^     ^
#

so the sum over the index range [1, 3) is prefix_sum[3] - prefix_sum[1]

#

in general the sum of values over the index range [l, r) is prefix_sum[r] - prefix_sum[l]

crude galleon
#

would this work even for things like Β΄boolean operations. in this program every value includes the character G or Y which determine approved/not approved. And one of the methods is calculating the percentage of G between a start date and end date

#

can i calculate that with prefix sum

haughty mountain
#

you can have a prefix sum for the number of Gs

#

assuming it can only be G or Y

#

since you can get the number of Ys as just whatever number of elements that were not Y

crude galleon
#

hmm, it will take some time for me to truly wrap my head around prefix sum but it sounds interesting

molten osprey
#

Hello

#

I've got a slight problem, it should be an easy fix

#

I have an error

ValueError: Data must be 1-dimensional

on this line

delta2 = (y2 - y1) * y2 * (1 - y2)```

The values of y1 are 
```python
952     0.469231
786     0.376923
414     0.438462
251     0.500000
69      0.376923
          ...   
1095    0.530769
1130    0.407692
1294    0.500000
860     0.407692
1126    0.346154

and y2 are

[[0.60591672]
 [0.61176466]
 [0.60348066]
 [0.60421058]
 [0.60590897]]
#

I understand y1 is two columns but I've tried isolating only the second column but I need a way of making sure both are the same format

#

let me know if anyone has any solutoins

haughty mountain
#

if you know red and yellow, can you find what blue is?

molten osprey
#

no because there is no yellow for the blue part?

#

I've got a slight mistake in my problem, the real value of y2 is this

halcyon plankBOT
#

Hey @molten osprey!

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

molten osprey
#

y1 and y2 are the same size, I didnt paste all of y2 in because its too long

#

y1 and y2 are both 580 long

haughty mountain
#

why does y1 even have two columns?

molten osprey
#

I used pandas dataframe

#

it automatically gave it an index

#

I tried to do this

#

y1[:, 1])

#

this gets rid of the first column

#

it then gave me this error ```KeyError: 'key of type tuple not found and not a MultiIndex'

#

@haughty mountain I have another solution ```python
y1_list = []

for col in y1:
    y1_value = []
    y1_value.append(col)
    y1_list.append(y1_value)
print(y1_list)
haughty mountain
molten osprey
#

I read the data from this file for y1

#

this is where y1 comes from

haughty mountain
molten osprey
#

I wrote to this file using pandas, I didnt want a index but when I wrote to it I looked and it had an index

#

now itll be too long to change it

haughty mountain
#

can't you just re-write the file and tell pandas not to add an index?

molten osprey
#

this is where I write it

# 
    # writing the dataframe to csv file
    standardised_df.to_csv("standardised_data.csv")
#

standardised_df.to_csv("standardised_data.csv", index=False)

#

that should work right?

haughty mountain
#

yes

molten osprey
#

Im sorry I tried this its too long the I have change a lot of my other code that uses certain columns etc

#

there must be a way to do in the code

#

@haughty mountain

haughty mountain
#

so you want to hack around bad data in your code just to avoid fixing the actual source of the data...

molten osprey
#

your right I should remove it, but the process involves a lot of backtracking

haughty mountain
#

granted, it seems that pandas will always have some index

#

so maybe what you really want is how to just get a specific column out of a pandas dataframe

molten osprey
#

thats what I tried to do

#

I get this error

#

AttributeError: 'Series' object has no attribute 'columns'

#

@haughty mountain

#

give me 5 min ill be back sorry

haughty mountain
#

series doesn't have columns

#

it only has one column, and an index

molten osprey
#

I see

haughty mountain
#

I never use pandas, but it's easy enough to search around to find stuff

In [8]: s = pd.Series({'a': 'A', 'b': 'B'})

In [9]: s.values
Out[9]: array(['A', 'B'], dtype=object)

In [10]: s.index
Out[10]: Index(['a', 'b'], dtype='object')
#

to_numpy() is another way to get the values

molten osprey
#

ah so I can do .values

#

now I need to make sure y1 and y2 are the same format

#

this is my code

#

delta2 = (y2 - y1.values) * y2 * (1 - y2)

#

y1 looks like this ```[0.46923077 0.37692308 0.43846154 0.5 0.37692308 0.59230769
0.53076923 0.34615385 0.59230769 0.40769231 0.46923077 0.43846154
0.62307692 0.5 0.37692308 0.53076923 0.71538462 0.5
0.43846154 0.56153846 0.53076923 0.46923077 0.56153846 0.53076923
0.80769231 0.46923077 0.5 0.56153846 0.37692308 0.40769231
0.46923077 0.34615385 0.43846154 0.46923077 0.34615385 0.5

#

and y2 looks like

# 
 [0.53518651]
 [0.53570278]
 [0.53551548]
 [0.53485952]
  .......

 [0.53465815]
 [0.53597329]
#

since Im trying to multiply them

haughty mountain
#

how do you even end up with those sizes?

molten osprey
#

Ill show you where y2 is made

# 
    # multiply input by first set of weights
    z1 = np.dot(x1, w1)
    # apply activation function (e.g. sigmoid)
    a1 = 1 / (1 + np.exp(-z1))
    # multiply hidden layer by second set of weights
    z2 = np.dot(a1, w2)
    # apply activation function to get output
    y2 = 1 / (1 + np.exp(-z2))
haughty mountain
#

so you're working with a matrix and a vector

#

just transpose them to be the same?

#

but I have no clue at all how you would get something with size 5

molten osprey
#

honestly neither

#

how would I go about transposing them, there two completely different sizes

meager bane
#

does anyone have any idea of how to solve this IF it were generalized to longest common string

#

ie not necessarily prefix

#

it seems much much much harder that way

#

any idea?

#

well i mean its doable but very messey and long run time

#

I was thinking cylcing through all combinations before finally choosing the max. It would have horrific run time

#

basically is there an "elegant" solution that someone can think of

haughty mountain
molten osprey
# 
(580, 1) shape of y2
(580,)  shape of y1
haughty mountain
#

ok, how tf do you get a 5?

molten osprey
#

waittt I've confused it

#

that error

#

it came from this line

#

delta1 = np.dot(delta2, w2.T) * a1 * (1 - a1)