#algos-and-data-structs

1 messages · Page 46 of 1

icy oasis
#

i'm trying to avoid having to write my own optimizer code because i imagine the pulp library is a million times faster lol

severe flicker
#

Is leetcode stats good for portofolio?

sonic rain
#

Given an unsorted array of integers(both positive and negative). Write a function to find the minimum positive integer that is missing in 𝑂(𝑛) time complexity.

min_pos_int(arr): return None

[3,9,2,−3,−5,1,9,6,4,8,72,5] return 7 [17,64,4,2,1,−3,76,−1,−5,16,13,9,10,18] return 3

#

how is O(n) even possible

vocal gorge
#

there's several possible tricks but one I like is ||just calculating the sum||

sonic rain
#

hmmm...... what do you mean by that

vocal gorge
#

(it's a bit arguable whether that's truly O(n) because it may be quite big)

#

ah, nevermind, I misread the task

outer rain
#

you can create a boolean array found of size n + 1 (same as the input size), iterate over the array, and every time you see an element 0 <= e < n + 1, set the element found[a] to true. Then find the first element in found which is false, and return it's index

#

this function is usually called MEX btw (minumum excluded or something)

sonic rain
#

Then find the first element in found which is false, and return it's index
wouldnt the worst case time complexity of that be O(n) as well

#

so altogether the function would be O(n^2)

vocal gorge
#

you don't do this for each element, you do it afterwards.

sonic rain
#

when you iterate through ur random array to create a boolean array thats O(n). checking which index is false is O(n). so although the function is O(n^2)?

#

oh wait

#

it would be O(2n)

#

sorry

#

brain shorted for a sec

#

@vocal gorge @outer rain thanks 🙏

stiff quartz
#

To solve this problem:
https://codeforces.com/problemset/problem/431/C

I did a "standard" dfs like so:

    n: int
    k: int
    d: int

    n, k, d = line_integers()

    # dfs with branch and bound
    @lru_cache(None)
    def dfs(sum_: int, has_d: bool) -> int:
        if sum_ == n:
            if has_d:
                return 1
        if sum_ > n:
            return 0

        s: int = 0
        if has_d:
            for m in range(1, k + 1):
                s += dfs(sum_ + m, True)
        else:
            for m in range(1, k + 1):
                s += dfs(sum_ + m, m >= d)

        return s

    ans: int = dfs(0, False)


    print(ans % 1000000007)

But the editorial suggests a dp solution (https://codeforces.com/blog/entry/12369, their solution coded up is https://codeforces.com/contest/431/submission/6676700). But I don't understand their dp solution.
this part:
Dp[n][0] = Dp[n-1][0] + ... + Dp[n-min(d-1,n)][0]
kinda makes sense but then when do we even "fill" the Dp[n-1] etc ... if we start with Dp[n][0] we will never do Dp[4][0] for example.

EDIT: or is the "n" they refer to actually an index idx defined in ``for idx in range(n)`?
EDIT2: are both solution equivalent since my cache is basically their dp?

#

unrelated, but is the term "branch and bound" the right one? I'm referring to if sum_ > n: return 0

#

or is it just a basic constraint check and therefore does not fall under the name of "branch and bound"

vocal gorge
#

Is there a library for... transforming discrete distributions, I guess? Rough example of what I'm talking about:

dist = uniform_range(0,10) # 0.1 probability each for elements in range(0,10)
dist2 = (dist*5 - 2).clip(20,30) # that's like doing max(20,min(30,x*5-2)) for each element in dist
# dist2 is then a distribution over 4 possible values with nonequal probabilities:
# {20: 0.5, 23: 0.1, 28: 0.1, 30: 0.3}

This isn't hard to implement from scratch (I've done this twice before, I think), but each time I feel like I'm reimplementing a wheel.

exotic bolt
#

anyone ever venture into information science?

regal spoke
#

What you have there is not branch and bound. Instead I would simply call your method DP

jaunty ridge
#

could someone explain why i'm getting this error

image.png
#

how can list index be out of range when for x in (whatever) goes through every element automatically lol

spring jasper
#

Because j is not the index of each element

#

Its the element itself

jaunty ridge
#

im stupid

#

i mixed up java, c and python

#

thanks man

spring jasper
#

👍

cyan sierra
#

I'm working on a pyqt5 browser and can't seem to load any form of captcha, here os the info I have...

js: unrecognized feature: 'cross-origin-isolated'

This is causing captcha to not load and only load as a string of random characters or more likely an ID, I really have 0 idea how to bypass or try to fix the issue to use the browser as my main browser.

cyan sierra
#

So... is there any fix at all?

subtle saffron
#

(this is copied from my reddit post to save time)

I'd like to learn encoders and machine learning but I don't know where to start.

I'm an intern for my last semester of college and the company asked me to make a machine learning model for a bunch of data with diffrent data types like strings, floats, bools in the shape of 0 and 1 and basically I didn't learn a thing from my college since we were online for a while and my course includes 2 out of 4 years of c++ for some reason etc anyway I cleaned the data and it's ready for use but now I know nothing about sklearn or any encoders, please give me some comprehensive but short ish resources to learn this, thank you in advance.

cloud knoll
# jaunty ridge thanks man

if you wanna use index, there are two ways to do that
for i in range(len(nums)):
i/ [i] are index and nums[i] it's the element

for i, v in enumerate(nums):
i index and v is a element or value, whatever you wanna call it

fervent light
#

would apprecaite any help

rich apex
#

How do you know what rotation to perform after inserting into a AVL Tree?

placid pier
#

how do i fix my code

summer stream
#

@pastel thorn check dm

forest heart
#

Whenever I need a linkedlist, should it always be Doubly?

cedar totem
#

depends whether you need backward references, so no, not always

forest heart
#

I see, and the only advantage with a doubly list, is that when doing backward references its O(1)?

cedar totem
#

yes, it allows you to iterate in the reverse direction, but if you want to count advantages, I would also add that since you can iterate in reverse, looking up an item by index/count would take less time in doubly linked-list
(eg: getting index 8 in list of length 10 takes 8 iterations, in doubly linked-list only 3)

#

and of course the tradeoff would be extra memory, and you need to maintain more references in insert/delete operations

forest heart
#

Awesome! Thanks I better understand 🫡

serene junco
#

i dont know which channel to post this error in

image.png
stiff quartz
#

I'm looking to understand how khan's algorithm is better compared to a naive BFS in the context of directed acyclic graphs with no weights

#

We could just do a BFS by adding in the initial queue all the vertices with no incoming edges

#

and adding the vertex we pop from that queue to a list we eventually return

#

Or maybe I'm getting something wrong:

Consider the following graph:
A -> B -> C
D -> C
E -> F

Is the topological order
A, D, E (all them interchangeable), B, F (these two interchangeable), C
or
A, D, E, (all them interchangeable) B, C, F (all them interchangeable)

Basically is C "3" (max of the number of edges to take to get to C) or "2" (min of the number of edges to take to get to C)

#

I think that's the second option, but that second option would be obtainable with a "basic" BFS

stray anvil
#

How I solved ?

The niceness of a pair (a, b) is the value you will get by subtracting their product from the difference of their squares. For example, the niceness of the pair (7, 4) is 5, because (7²-4²) - (74) is 5.
Find any pair of numbers with niceness 500, where both numbers have 4 digits. If you find a pair (a, b) then write the number (10000a)+b as the answer.

solemn moss
# stiff quartz Or maybe I'm getting something wrong: Consider the following graph: A -> B -> C...

Any order where for each vertex all incoming one are located before it
A should be before B, B and D should be before C, E should be before F

I didn't understood what the exact task is, but for example the longest path

If you do that with bfs on such graph (screenshot)
You will get in 2 from the 1, later you will get in 2 again from 3, and you will need to start from 2 again to update the answers everywhere after it, then one more time from 7

image.png
stiff quartz
#

2 has to come after 3 so bfs wouldn’t work I guess

#

Ok I understand

#

So in topological order, all vertices that could lead to i have to be before i

#

It’s not a matter of distance from the vertices that have no incoming edges

#

Is that right?

solemn moss
#

Ye, distance doesn't matter

stiff quartz
#

Ok i understand

#

That’s the subtlety

mystic fossil
#

Question - Bob has reviewed the external chaining policy, and he's designed a modification of it, which he calls "tree chaining". The idea is that rather than using a LinkedList for the chaining, he uses a BST instead. Alice comes over and sees the merits in the idea, but she cautions that the idea needs to be thought out carefully because it could have unexpected complications in implementation and unintended consequences in efficiency. Which of the following are plausible concerns that Alice might have?

  1. The requirements for keys in HashMaps do not match the requirements for data in a BST.
  2. BSTs only hold a singular data type, so it's non-trivial to store key-value pairs.
  3. The worst case performance (in terms of time complexity) is the same as before for searching.
  4. Performance may be worse when there are not many collisions.
  5. Performance may be worse in pathological cases with many collisions.
  6. Performance of resizing the table is asymptotically worse in the worst case.
  7. Alice's concerns are unfounded, and Bob is a genius for thinking of this idea!
agile sundial
#

definitely 7

mystic fossil
#

I feel the answer should be 1,2,4,5,6 but it is turning out to be incorrect 😦

mystic fossil
agile sundial
mystic fossil
#

for 1st option - Storing key-value pairs directly in BST nodes might not guarantee unique keys. However, Bob could potentially implement a custom node structure or use a separate data structure within the BST node to handle key uniqueness.
for 2nd option - Storing both key and value efficiently requires thoughtful design. Bob might need to create a custom node structure with separate fields for key and value
for 4th option - Using BSTs adds overhead compared to linked lists. For small chains with few collisions, the overhead might outweigh the benefits, leading to slower performance
for 5th option - While BSTs can handle collisions better than linked lists in some cases, pathological cases can still lead to unbalanced trees and O(n) search complexity, negating the benefits.
for 6th option - Resizing a hash table with tree chaining might involve rebuilding BST chains, potentially making it asymptotically slower (O(n log n)) than resizing with linked lists (O(n)) in the worst case

mystic fossil
agile sundial
#

that's cheating 😛

mystic fossil
#

I just wanted some help

agile sundial
#

i'm reading your answer

#

for number 1: what are the requirements for keys in a hash table?

mystic fossil
#

duplicate keys might get added

agile sundial
#

yeah i think 1 is correct, but the reasoning is different. a BST requires the keys to be comparable, while a hashmap only requires being able to check equality

mystic fossil
#

oh ok

#

I am a newbie actually.

mystic fossil
agile sundial
#

i think this question is a bit poorly worded. i think 2 is not really plausible, since as you mentioned we can just create a struct/class/whatever to store both key and value

#

it also doesn't really define "few" in 4. i'm tempted to say 4 is not plausible, if there's only 1 collision, the performance is the same

#

it also depends how the BST is implemented, actually

#

if you implement using nodes like a linked list, then there's no memory overhead. but if you use an array then there would be

mystic fossil
mystic fossil
agile sundial
#

for 5, the performance can never be worse, which i think is the key

#

the degenerate BST case is just a linked list, which can only be the same as a linked list

mystic fossil
#

but i think resizing in 6th would be worse

agile sundial
#

i think you're right for 6

mystic fossil
#

hmm so is the final answer 1, 5 and 6 according to you?

mystic fossil
#

even after removing the answers which you deem incorrect, it is still showing incorrect

agile sundial
#

why did you not include 3?

mystic fossil
#

i think the worst case performance remains the same in both scenarios

#

O(n)

agile sundial
#

hmm. i guess the question is just worded badly. i think it just wants "true or false". if true, select it

mystic fossil
#

actually these 7 options have tick box against them so I need to select all the options that apply 😦

agile sundial
#

right, select the true ones

mystic fossil
agile sundial
#

i think 3 too

mystic fossil
agile sundial
#

idk then

mystic fossil
#

ok buddy thanks 🙂

summer warren
#

can somebody help me with my python work 🙏 im not 100% sure where to put this

#

number = int(input("Enter an integer to see its powers: "))
amount = int(input("How many powers of " + str(number) + " do you want to see? "))
variable = 0
for i in range(amount + 1):
number = (number) ** (variable)
print(str(variable)+ ". " + str(number))
variable += 1

#

IS MY MATH WRONG OR SOMETHING bc variable never ends up adding up 😢

bronze bloom
#

,e 2 4 ```py
number = int(input("Enter an integer to see its powers: "))
amount = int(input("How many powers of " + str(number) + " do you want to see? "))
variable = 0
for i in range(amount + 1):
number = (number) ** (variable)
print(str(variable)+ ". " + str(number))
variable += 1

jolly mortar
#

you assign the result to the same name number

summer warren
#

i thought because i assigned it the same it would overwrite

jolly mortar
#

after the first iteration number becomes something ** 0 = 1 and then it stays 1 forever

jolly mortar
summer warren
#

ohh i see, i would have to assign it to another variable?? how would I make the code work?

jolly mortar
#

yes

summer warren
#

THANK YOU SO MUCH i should've done that earlier oops

#

🫧 🎊

lilac cradle
#

Is there a way to have fixed-width integers in base python?

#

i guess for the math aspect i could just implement a numeric class that does value & base-1 for every op

#

Is there a way to overload all the math operators for a class without having to make a decorator for them actually

lilac cradle
#

oh i checked in C, it's the same result

#

i thought python handled it differently

lavish fjord
lilac cradle
#

ill have to look at that

#

cause my implementation of int16 looks like this lmao

image.png
#

i honestly have no idea how to use the ABCs

lean walrus
#

i guess this is the best it can be

#

there is no more convenient way

#

you also might want to ask about it in #esoteric-python to get interesting answers

lavish fjord
#

Otherwise, just inherit from int and override what you need to

lilac cradle
vocal gorge
#

np.uint16 would also work

modern tartan
#

hello guys

#

i want to start python but is a prohlem

#

problem

#

can i use it as a freelancer and make a lot of money?

#

bcz some people that u cannot be an freelancer with python

restive bough
#

i need help

#

i keep getting an error on my mac im trying to install pandas into python and keep getting error

#

i did it correctly in my mac terminal

haughty mountain
#

topic pls

restive bough
haughty mountain
solemn moss
#

This is something like knapsack problem:
N (n <= 1e5) pairs of numbers l, r (l <= 1e13, 1.4 * l <= r <= 1e13) are given and a number s (s <= 1e13)
For each pair we can take some number x = 0 or l <= x <= r, then calculate the sum of these x values

We need to find out what is the maximum sum that is less or equal than s we can achieve and how much should we take in each pair to get it

Example

3 20
1 2
10 17
11 16

(first line is n and s, next n lines are l, r)

Answer

19
2 17 0

(first line is sum, second line is the value that we take for each segment)

To find only the answer sum value, we can do such algorithm:

segments = [(0, 0)] # stores segments with all the sums we can achieve
for i in range(n):
    new_segments = []
    l, r = A[i]
    for L, R in segments:
        new_segments.append((L, R))
        new_segments.append((L + l, R + r))
    # ...
    # Find a union of the segments in `new_segments`
    # ...
    segments = new_segments
# ...
# The answer sum can be found easily with binsearch now (or just with a loop)

It works fast enough because we have a constraint 1.4 * l <= r <= 1e13
It means that in one time we can't have more than log(1.4, 1e13) ~ 90 non-intersecting segments

But idk how to restore the answer (second line)

lilac cradle
#

anyone know an efficient sphere generation algorithm? i.e say i want to generate all the points on a sphere in a voxel grid (i.e like minecraft blocks)

#

i've tended to use the naive method of just iterating through a cube

#

and checking the distance

haughty mountain
#

I know of some well known algorithms for the 2d case, i.e. pixels on a circles

#

e.g. https://en.wikipedia.org/wiki/Bresenham's_line_algorithm which is for lines, but have variants like https://en.wikipedia.org/wiki/Midpoint_circle_algorithm

Bresenham's line algorithm

Bresenham's line algorithm is a line drawing algorithm that determines the points of an n-dimensional raster that should be selected in order to form a close approximation to a straight line between two points. It is commonly used to draw line primitives in a bitmap image (e.g. on a computer screen), as it uses only integer addition, subtraction...

Midpoint circle algorithm

In computer graphics, the midpoint circle algorithm is an algorithm used to determine the points needed for rasterizing a circle. It's a generalization of Bresenham's line algorithm. The algorithm can be further generalized to conic sections.

#

I'm not sure how easy these would be to generalize to 3d

lilac cradle
#

ik bresenham's

vocal gorge
# solemn moss This is something like knapsack problem: N (`n <= 1e5`) pairs of numbers l, r (`...

Somewhat confused: the goal is to find x_i such that forall i, either x_i=0 or l_i<=x_i<=r_i, and sum_i x_i should be as high as possible without exceeding a certain goal s? If so, I think that's linear programming, with some caveats like integer-only values and being allowed to use 0 always. Nevertheless, scipy's scipy.optimize.linprog can handle both of these constraints (integrality=3 does exactly this).

#

(of course, I have no idea how HiGHS actually works under the hood, so that's not really an answer to what algorithm to use 🥴)

solemn moss
outer rain
#

You can store for each non-intersecting segment in the DP how you got that segment

#

like if you have a segment [5, 12] and you want to know how can you get 10, you can trace back the evaluation of DP

#

so like, if, say, you got [5, 12] as a merge of segment [5, 8] you got from a previous iteration, and [7, 12] which you got as a sum of segment [5, 8] and item [2, 4], then you can store it with the segment itself, in some format, for instance, like ((5, 12), [((5, 8), None), ((5, 8), (2, 4))])

#

So when you are trying to restore the answer, look at the segment the answer lies in, trace back how you got it, then restore the segment you got it from, etc.

#

I know this is a bit confusing but its the best explanation I can give, I feel 😅

outer rain
#

It's going to be O(n^3) either way, you may lose like x4 performance at most

vocal gorge
#

the way that comes to my mind is

for z in range(-int(R), int(R)+1):
    ymax = int(math.sqrt(R**2-z**2))
    for y in range(-ymax, ymax+1):
        xmax = int(math.sqrt(R**2-y**2))
        yield from ((z,y,x) for x in range(-xmax,xmax+1))

(i may well have off-by-oned in many places.) but yeah, it's only a constant factor faster than any naive way.

#

actually, another answer to this is "I think skimage has a function for that" 😛

lilac cradle
#

kk

#

Good to know, thx

vocal gorge
sinful thorn
#

Anyone doing hackerrankone?

lilac cradle
#

also is there an algorithm for generating points on a face? (once again in a cubic grid) say i have the positions of the vertices

#

for a triangular face, that is, since for quadrilaterals and above there's ambiguity on how they're attached and you can also get some really fucky layouts that aren't possible to solve without curves or multiple faces

outer rain
lilac cradle
#

kk

outer rain
lilac cradle
#

it'd be handy, since i've been having people wanting me to make an OBJ-to-blueprint (for a game) program

#

btw is there any advantage to using a generator in a function? im not sure when i'd use them
the only time i've ever really done yielding is in my vector class code implementing __iter__()

#

im guessing for large amounts of data it's more efficient to use a generator since it can take it 'piece by piece'

#

if that's how it works

outer rain
#

Generators can be faster because they skip the whole "put elements into a list" step.

lilac cradle
#

kk

#

so here's a basic function that returns a set of points within a circle

def gen_circle_points(pos,rad):
    points = set()
    for y in range(-rad,rad):
        for x in range(-rad,rad):
            if (x**2 + y**2) <= (rad**2):
                points.add((x+pos[0],y+pos[1]))
    return points

might try doing it with a generator

#

oh yep that worked, i just removed the return statement and the set and did yield instead of points.add

#

only issue is it only works if you're going to iterate through it afaik, but in this case idk when you wouldn't want to do that

# 
def gen_circle_points(pos,rad):
    for y in range(-rad,rad):
        for x in range(-rad,rad):
            if (x**2 + y**2) <= rad**2:
                yield x+pos[0],y+pos[1]

much simpler

#

:D

#

its pretty fast too apparently, i ran it with a 100 radius circle and it didnt take long at all

lilac cradle
haughty mountain
#

of course, another option is to work scanline by scanline and solve a second degree equation to get the end points

#

(or even brensenham I guess)

#

and then you can say "draw a line at y from x=bleh to x=blah"

#

which might be a fast primitive

outer rain
wheat olive
lilac cradle
#

also wdym constant time?

wheat olive
wheat olive
#

since this is done in hardware

lilac cradle
#

ah well i guess yeah

outer rain
#

that's not constant time though, it's just faster

lilac cradle
#

if i actually needed the performance i would probably do something like that but that was just an example of the idea

#

i wonder if there's a way to kind of cut out some of the work by 'removing the corners' of the square or if that'd just make it worse

#

i mean really if you take that to its logical conclusion you could just keep removing corners until you get a circle (or an octagon, depending on how you do it)

outer rain
lilac cradle
#

lemme fiddle with that and see

wheat olive
outer rain
#

no, no it won't

#

using numpy doesn't magically improve time complexity

#

and it's not even "very close"

lilac cradle
#

this is all the code i used to do the circle render btw, very simple

from PIL import Image
#====#
w,h = 250,250
radius = 100
#====#
im = Image.new("RGB",(w,h),(255,255,255))
px = im.load()

def gen_circle_points(pos,rad):
    for y in range(-rad,rad):
        for x in range(-rad,rad):
            if (x**2 + y**2) <= rad**2:
                yield x+pos[0],y+pos[1]

points = gen_circle_points((w//2,h//2),radius)
for i in points:
    px[i]=(0,0,0)
im.save("circle_test.png")

it is, of course, less efficient to use px[pos] for a bunch of points rather than just putting it all into an array but i feel like for this it'd be weird to do that since i'm only filling some pixels

outer rain
lilac cradle
outer rain
#

nah, should be cheap

lilac cradle
#

ah, i avoided sqrt in mine in favor of doing a sort of distance2

outer rain
#

you only compute n*n square roots, not n*n*n

#

(n instread of n*n in 2d case)

lilac cradle
#

oh wait i was trying to break it down to see if i could render it as a square without the corners but

#

oh wait that is a sphere isnt it

outer rain
#

yeah

lilac cradle
#

yeah ok that explains it

#

i cut out the wrong part i guess :p

#

i was going to make a mockup of the 'cutting out the corners' bit in algodoo (too lazy to do it properly in an image editor) and, wow you really do not cut off that much space if you remove the corners

#

i can actually check the area using algodoo

#

circle is 1m radius, so the square is 2m on a side (and therefore an area of 4 m², so removing π m² from it gives ~0.858 m², so a ratio of 0.21 between the total area of the square and the area not in the circle, and this isn't even accounting for the fact that removing a corner would be an even smaller fraction of that area

image.png
#

so yeah i can see why it wouldn't be a super significant speed increase by doing it more elegantly

lilac cradle
#

the math is just (2r² - πr²)/2r²
im sure you could condense that down but whatever

dreamy galleon
#

hello

#

is there anyone can help me

humble spade
#

Yo how you guys doin?? I learned max pairwise and i'm trying to write a brute force solution for magic square matrix. It's nearly done but it keeps appending to the array. I will post the code if anyone is interested

humble spade
wind pasture
#

where do I go for a question about "return"?

vocal gorge
cobalt sedge
#

This is why I love programming. I got a very interesting question that i couldn't think of any idea. This is not a python code, instead it is a swift code. I would appreciate if someone can write me this in swift. Lets say I have the following struct and json data. Can We write a init(decode: Decoder) function to covert object with this condition? If the primaryKey for the selector exist, use the primaryKey value to look for the id for the option. If the primaryKey doesn't exist, then simply use the id.

Example, both the ids for the two options below would be ["1","2","3"]
My Struct

struct Selector: Decodable {
    let primaryKey: String?
    let id: String
    let text: String

    struct Option: Decodable {
        let id: String
        let text: String
    }
}

Json Data

[
    {
        "id": "123",
        "text": "text",
        "primaryKey": "month",
        "options": [
            {
                "text": "Hello",
                "month": "1"
            },
            {
                "text": "Hello2",
                "month": "2"
            },
            {
                "text": "Hello3",
                "month": "3"
            },
        ]
    },
    {
        "id": "222",
        "text": "text2",
        "options": [
            {
                "text": "Hello",
                "id": "1"
            },
            {
                "text": "Hello2",
                "id": "2"
            },
            {
                "text": "Hello3",
                "id": "3"
            },
        ]
    },
]
#

Currently I wrote sth like this, but I found that the optionJSON contain only the field I defined in the struct. In other words, the "month" doesn't exist

if let primaryKey = primaryKey {
                print(primaryKey)
                self.options = options.map { option in
                    var modifiedOption = option
                    if let optionData = try? JSONEncoder().encode(option),
                       let optionJSON = try? JSONSerialization.jsonObject(with: optionData, options: []) as? [String: Any],
                       let primaryKeyValue = optionJSON[primaryKey] as? String {
                        print(primaryKeyValue)
                        modifiedOption.id = primaryKeyValue
                    } else {
                        modifiedOption.id = ""
                    }
                    return modifiedOption
                }
            } else {
                self.options = options
            }
forest gorge
#

need some help with code of n^2 simulation, sorry if this is not the appropriate channel.

#

more precisely I am trying to implement 4th order runge-kutta, but facing some issues.

#

Can I ask here?

fiery cosmos
#

hi all, wondering why this leetcode solution doesn't work:

# 
class Solution:

    def twoSum(self, nums: List[int], target: int) -> List[int]:

        for i in range(len(nums)):

            for j in  range(len(nums)):
                
                if nums[i] + nums[j] == target:
                    return i,j
                
                else:
                    continue
solemn moss
fiery cosmos
#

ohhh

#

my second loop should thus be i+1

#

thanks

#

how do y'all solve leetcode problems, in IDE or in the web browser?

#

i don't like the browser because I cannot do print statements

fiery cosmos
#

why doesn't this palindrome number solution work:

# 
class Solution:

    def isPalindrome(self, x: int) -> bool:

        x_inverted = str(x)[::-1]
        
        x = str(x)

        flag = 'true'

        for i in range(len(x_inverted)):
            if x_inverted[i] != x[i]:
                flag = 'false'

        return flag
fiery cosmos
#

here's another solution

# 
class Solution:

    def isPalindrome(self, x: int) -> bool:

        xasstr = str(x)
        xrev = xasstr[::-1]

        print(xasstr,xrev)

        if xasstr == xrev:
            return 'true'
        
        else:
            return 'false'
#

how is this possibly not working

#

i'm verifying that they are not equivalent strings with my print

#

omg

#

its because in the problem description, they did not write True and False but true and false

#

ok

jovial gazelle
fiery cosmos
#

okay thanks. i've moved on to Longest Common Prefix

hot knoll
#

HELP ME

#

x = 27
y = 20

if x % 2 != 0:
if y < x:
z = 0
else:
z = 1
else:
if y < x:
z = 2
else:
z = 3

#

z=?

civic kraken
lean walrus
civic kraken
frozen ridge
#

Hello everyone, I'm not very good at coding, i need help to understand the algorithm of data structures and learn how to write the code line by line. Can anyone help me?

#

for example this question: Create a recursive function, not within any class scope, that accepts a ListADT and reverses its content.

steep kindle
#

is there any way to visualize an algo in a flowchart directly from source code?

fiery cosmos
#

i don't know of any flow chart but pythontutor is helpful and offers some visuals like the arrays and stuff. let me find it

#

separately i need some help w leetcode

#

specifically all the code i'm seeing begin as classes, so i guess i'd like to know how to write my own functions within the class (a method) and how to execute.

#

also what is this arrow thing:

# 
def isValid(self, s: str) -> bool:
#

->

#

also i have a solution i'd like to walk through w someone

#

to the easy question "valid parentheses"

# 
class Solution:

    def isValid(self, s: str) -> bool:

        stack = []
        mapping = {')': '(', '}': '{', ']': '['}

        for char in s:
            if char in mapping:  # Closing parenthesis
                # Check if stack is empty or if top of stack doesn't match current closing parenthesis
                if not stack or stack.pop() != mapping[char]:
                    return False
            else:  # Opening parenthesis
                stack.append(char)

        # Ensure the stack is empty at the end
        return not stack
#

specifically i'm wondering about if the dictionary lookups go both ways. reading this is seems to be the case that one could look up the proper parenthesis by querying the mapping dictionary with either a key or a value.. is this correct?

steep kindle
#

thanks @fiery cosmos

fiery cosmos
#

happy to help. hope it is doing that

fiery cosmos
#

okay, i've learned that the arrow -> indicates the expected return type from a function

narrow mica
exotic bolt
#

thoughts on haskell?

outer rain
oblique prairie
#

Hello I need a bit of help, the else argument is giving me a bit of a headace because it pops up as soon as I fix one else argument or so I thought I have.

`def init(self):
self.todos = []

def add_todo(self, todo):
self.todos.append(todo)

def delete_todo_by_index(self, index):
print('List is empty.')
if len(self.todos) ==0:
else: self.todos.remove(self.todos[index])

def delete_todo(self, todo):
print('List is empty')
if self.todos == []
else: self.todos.remove(todo)

def checked_todo(self, isChecked, todoCheck):
for todo in self.todos
if isChecked is True
print('(x)', todoCheck)
else
print('( )', todoCheck)
break`

#

I'm not sure what I'm doing wrong and I've looked online and tried different methods

#

here's a ss just to see how it's formated

tight cedar
#

you are doing if else statements wrong

oblique prairie
#

I get that

#

I don't know what I'm doing wrong though

#

like specifically

tight cedar
#

if [some_condition]:
code if condition is True
else:
code if condition is False

frozen ridge
#

does anyone know how to implement this? I have an idea but the code is not working with me

Screenshot_2023-12-23_at_23.02.54.png
#

This is my code
if num == 0:
raise ValueError("can't divide by 0")
current = self._first
prev = None
count_deleted = 0
while current:
if current.data % num == 0:
if prev:
prev._next = current.next
else:
self._first = current.next
count_deleted += 1
current = current.next
self._size -= count_deleted
return count_deleted

ionic locust
#

Hey guys so I'm making a queuing system. I need to find the estimated waiting time for each person in the queue. Apparently queuing theory is a real thing people study so just wondering how I should go about doing this and what topics will be relevant for me to read up on to find out how to get the estimated waiting time per person

soft parcel
#

(@me in replies)

modern gulch
# soft parcel I need help with BFS -_- I understand it from a graph theory perspective but get...

Wikipedia has a very nice pseudocode version that’s pretty simple, maybe take a look and ask any questions? https://en.m.wikipedia.org/wiki/Breadth-first_search

Breadth-first search

Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered ...

#

The idea is to push the children of each visited node into a queue, then visit the next node popped from the queue.

#

So, you push the root node 1 to initialize. You pop and visit node 1, then push children 2,3,4. Then pop (2) and push 5,6. Then pop (3) and so on.

narrow mica
languid thistle
#

hey people, what are some commendable ways to time arbitrary functions in python 3?

vocal gorge
#

well, the timeit builtin. personally I use the %timeit magic from ipython.

soft parcel
soft parcel
#

ill be back with questions 🫡

lilac cradle
#

collatz conjecture mapped to a hilbert curve

image.png
#

slightly bigger render

image.png
lilac cradle
#

and a much bigger render

image.png
#

dimmed by a factor of 1.6

haughty mountain
#

what are the values?

#

number of steps?

arctic crater
#

fastest algorithm

image.png
lilac cradle
#

Clamped between 0-255, hence the dimming

#

I used a histogram and manually found a good multiplier to keep it in range, basically

lean walrus
lean walrus
arctic crater
arctic crater
lean walrus
#

?

#

open(...).write(...) is the fastest way i can think of

#

not sure why you need hash table to print something

stiff quartz
#

Hi!

I'm currently doing this Leetcode problem: https://leetcode.com/problems/extra-characters-in-a-string/description/

My first instinct was to do that:

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:

        @lru_cache(None)
        def search(idx_start: int) -> int | float:
            if idx_start == len(s):
                return 0

            final_penalty = float('inf')
            for word in dictionary:
                if s[idx_start:].startswith(word):
                    final_penalty = min(
                        final_penalty,
                        search(idx_start + len(word))
                    )
            final_penalty = min(
                final_penalty,
                1 + search(idx_start + 1)
            )
            return final_penalty

        return search(0)

but it seems the solution is not that great (only beats 30% in space and time). Any idea what I should improve?

#

I don't fully understand the complexities of the editorial, I think my solution is O(len(s) * len(dictionary))

#

Maybe s[idx_start:].startswith(word) is not O(1) actually? but O(len(word))?

solemn moss
#

Also just recursion usually takes a lot of time and memory

stiff quartz
#

Fairs

stiff quartz
stiff quartz
#

So it’s pretty good

lilac cradle
#

it took a damn while to render (probably like 30s) but i didnt really care since i just had it going in the background

#

its quite simlpe

#

what it does is iterate through every coordinate, and for each one calculates the hilbert index, gets the amount of collatz steps for that, then dims,clamps and casts the value to int and then puts the value into the data array

# 
for y in range(res):
    if y&15 == 0:
        print(y,end="     \r")
    for x in range(res):
        index = xy2d(res,x,y)
        steps = int(clamp(0,collatz(index)/(1.6),255))
        data.append(steps)

im.putdata(data)
im.save("collatz_render.png")

the actual iteration part is this, the printing is just to give me an idea of how far along it is

#

i wrote it in like a few minutes

dapper saddle
#

hello I I have a kaggle general question. Kaglge discord is totally dead hope it's okay I ask here.

I submitted something on kaggle which was pretty much boilerplate code, I just wanted to see how the website works.

I have now created my own steps and even though I could not beat my boilerplate code I would like to submit it. Once I submitted it still showed my previous score.

Is there a way I can delete my submission.csv and use this one, does it run everything in my notebook and go with most recent submission, or does it just go with highest.

I have no idea how it works

haughty mountain
lilac cradle
#

lol

stiff quartz
#

Anyone could help explain why this codeforces submission https://codeforces.com/contest/1907/submission/239009018 is so much faster than this https://codeforces.com/contest/1907/submission/239009251. This is a really easy problem (https://codeforces.com/contest/1907/problem/B). The first solution is O(2n) and the second O(3n)* so i wouldn't have expected such a big difference in time. Am I missing something and the second might actually be quadratic or something?? I'm very confused!

* I had to use a list since append is O(1) and concatenating two strings is theoretically O(len(concatenated string)) so if i initialised ans: str = "" and did ans += char several times it would actually be quadratic.

outer rain
# stiff quartz Anyone could help explain why this codeforces submission https://codeforces.com/...

O(2n) = O(3n). Concatenating two strings is O(len(concatenated string)), and in your case if you concatenate char by char, it's O(1), so list vs str makes no difference complexity-wise. So unless I am missing something, I think the issue is simply that the second solution does more work. You append a lot in the second one, and append is a rather slow operation, compared to just access. Initializing tuples might also be an issue, since they require allocating memory every time, while simple strings like single letters are allocated once.

Have you tried submitting those with PyPy?

haughty mountain
#

just doing a bit more work in a tight loop could easily account for 2x

#

and it just seems the second one does a lot more work

stiff quartz
stiff quartz
outer rain
#

almost certainly

oblique oak
#

why did we take 1 from the index in the for loop? (this is a method in a linked list class)

def insert_at_pos(self, index, new_node):
    if index < 0 or index > self.length:
        raise IndexError("Index out of range")

    if index == 0:
        # Insert at the beginning
        self.insert_at_beginning(new_node)
    elif index == self.length:
        # Insert at the end
        self.insert_at_end(new_node)
    else:
        # Insert at the specified position
        current = self.head
        for i in range(index - 1):
            current = current.next
        new_node.next = current.next
        current.next = new_node
        self.length += 1
quiet light
#

Where should I ask my question regarding a Raspberry Pi with Micropython?

midnight cloak
#

hello guys i'm new here , i want a roadmap to learn dsa and have ability to solve leedcode prblems and thanks

narrow mica
midnight cloak
quiet light
lean walrus
hybrid umbra
#

can anyone help me in this qs.

Screenshot202023-12-2720at2010.png
fiery cosmos
#

i'm working on leetcode problem 26. Remove Duplicates from Sorted Array if anyone is around to help

#

nvm the site seems to be down

#

ok its back

fiery cosmos
#

i have a solution that i am not understanding if anyone is there

fiery cosmos
# 
class Solution:

    def isValid(self, s: str) -> bool:

        stack = []
        mapping = {')': '(', '}': '{', ']': '['}

        for char in s:
            if char in mapping:  # Closing parenthesis
                # Check if stack is empty or if top of stack doesn't match current closing parenthesis
                if not stack or stack.pop() != mapping[char]:
                    return False
            else:  # Opening parenthesis
                stack.append(char)

        # Ensure the stack is empty at the end
        return not stack
#

i'd like to talk through this solution, specifically i would like to know if the if char in mapping: line checks only keys in the mapping dict or also values

haughty mountain
#

if it checked values it would be super slow

fiery cosmos
#

does this return True by default?

#

i don't understand how it actually "answers" the question, where nowhere does it explicitly return True

#

yet when i run in leetcode it'll give true as an output

#

ugh i have to go as soon as @haughty mountain comes out of the woodworks. looking forward to working with you next time. i am aware of your expertise

#

any general advice you have for getting better at leetcode easy problems please drop here

haughty mountain
#

i.e. "is stack empty"

fiery cosmos
#

oh, and that is equivalent to true when stack is empty?

haughty mountain
#

bool([]) is False
bool(non_empty_list) is True

fiery cosmos
#

ok

#

ugh i don't get it

haughty mountain
#

this is stuff you really should have learned at some point, the truthiness of containers and whatnot pithink

fiery cosmos
#

agreed

#

well its good i'm working on this stuff now i suppose. leetcode is making me feel really dumb though

haughty mountain
#

do you know the simpler solution when you only have one kind of parens?

proper bramble
# fiery cosmos does this return `True` by default?

This is a matter of truthy and falsey values. Empty Sequences (dicts, lists, tuples, sets, and their subclasses like TypedDict, frozenset, namedtuple, etc), None, False, 0, 0.0, and empty strings all are equivalent to False for each respective data type.

haughty mountain
proper bramble
#

So when you say not foo, where foo is one of these things, then it evaluates to True

fiery cosmos
# 
#Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:

        dummy = ListNode(-1)
        current = dummy
        
        while list1 and list2:

            if list1.val <= list2.val:
                current.next = list1
                list1 = list1.next

            else:
                current.next = list2
                list2 = list2.next

            current = current.next
        
        # Append remaining elements if any
        if list1:
            current.next = list1
        elif list2:
            current.next = list2
        
        return dummy.next
haughty mountain
# fiery cosmos no

try figuring that problem out then, basically given a string of ( and ), is it balanced?

haughty mountain
#

it basically just does the thing, no real cleverness involved

#

the code for doing this with just two python lists is very similar

fiery cosmos
#

sorry my VScode seemingly just broke

#

i'm running a Python script in VSCode and nothing is happening

#

also, trying to launch IDLE is doing nothing

#

i'm reinstalling everything, should i do Python first or VSCode first?

fiery cosmos
#

reinstalled Python, running IDLE does nothing

fiery cosmos
#

ok i think i finally fixed it

#

not that i ever knew what was wrong

fiery cosmos
#

is there a better name for the count variable that'll make this make more sense to me:

# 
nums = [0,1,2,2,3,0,4,7]
val = 2

count = 0
# Loop through all the elements of the array
for i in range(len(nums)):
    if nums[i] != val:
        # If the element is not val
        nums[count] = nums[i]
        count += 1
        
print(count)
past mirage
fiery cosmos
#

for some reason, in the above solution having it named count really throws me. because its using a var named count to both count instances of elements nums which are not equal to val, but also using count as an index to reassign values within the array nums

#

the conflation of the two really confuses me

fiery cosmos
#

is there some other way i can think of count or a better variable name

near marsh
# 
[
  Media(
    (pk=123),
  ...stuff here...
    }),
  ),
];

what type of data type is this?

#

or how do i convert it into something python can read

haughty mountain
#

"how many values that are not val have I put in the array"

#

this is also the index if I want to put a new element

iron saffron
#

guys who can help me plz in some thing in python

coral flax
iron saffron
# coral flax Sure?

look i have microbit
its a card like arduino

I use opencv. When the camera opens, the system tells me to identify anything it sees. For example, if it sees the keyboard, it says it is a keyboard, like artificial intelligence. What did I do? I put two lines in the camera, a green line and a red line, and I said I am in the code. When a being called a human presses the red one, it says the word open. And when he touches the green line, he says “close,” and the command succeeds. Then I said, “When I touch the red line, it says open.” And when he says it, he sends a message to Com4, which has a microbit. And I said in the microbit code. When you receive the message, open, it draws a smiley face with its lights, and the same goes for the red color and when you receive the microbit. Message: Close. The microphone draws a house with its lights, an unsmiling face. Everything works, but when the camera turns on and I touch the red color that is supposed to be in the microphone, it draws the face.
The smiley, but do not draw it, although I see that the microbet is receiving a change through there is a yellow light in the back that tells me if there is a change or not.

oblique oak
#

hello

# 
class Node:
    def __init__(self,item):
        self.item = item
        self.next = None
class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0
    def insert_at_beginning(self, new_node):
        if self.length == 0:
            self.head = self.tail = new_node
            new_node.next = None         
        else:
            new_node.next = self.head
            self.head = new_node
        self.length += 1

    def insert_at_end(self, new_node):
        if self.length == 0:
            self.head = self.tail = new_node
            new_node.next = None
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.length += 1

    def insert_at_pos(self, index, new_node):
        if index< 0 or index> self.length:
            raise IndexError("Index out of range")
        elif index == 0:
            self.insert_at_beginning(new_node)
        elif index == self.length:
            self.insert_at_end(new_node)

        else:
            current = self.head
            for i in range(index-1):
                current = current.next
            new_node.next = current.next
            current.next = new_node
            self.length += 1

    def remove_from_first(self):
        if self.length == 0:
            raise "remove from empty list"
        elif self.length == 1:
            self.head = self.tail = None
        else:
            self.head = self.head.next
        self.length -= 1

    def remove_from_end(self):
        if self.length == 0:
            raise "remove from empty list"
        elif self.length == 1:
            self.head = self.tail = None 
        else:
            self.tail = None
        self.length -= 1
        
    
    def __str__(self):
        current = self.head
        lst = []
        while current is not None:
            lst.append(str(current.item))
            current = current.next
        return "[" + ", ".join(lst) + "]"
#

should I make my linked list doubly to become able to delete from the end with a constant time?

arctic crater
# 
class Solution:
    def decodeAtIndex(self, s: str, k: int) -> str:
        length_str = 0
        numbers_set = {str(x) for x in range(10)}

        # Get the amount of char it has (we used counter to save space)
        for char in s:
            if char in numbers_set:
                length_str *= int(char)  # If it is number than multiply it
            else:
                length_str += 1  # Else if letter just add 1

        for char in reversed(s):
            # The entire length of 3x leetleetcode (36 char) modulo (k % 36) is the index of it in the first line
            k %= length_str

            if k == 0 and char.isalpha():
                return char

            # The one line of text "leetleetcode" is 12 char and since 3 is the last number it will be
            # 3x in this case it will be 36 char, in this case we'll be turning it into one line so back to 12
            if char.isdigit():
                length_str //= int(char)  # If the char is number we can divide it can reduce the iteration
            else:
                length_str -= 1


e = Solution()

print(e.decodeAtIndex("leet2code3", 10))

Idk I am just that stupid but It hard to visualize, like the math on how to get it makes it looks vodoo to me

oblique oak
#

is this method implemented correctly?

    def remove_element(self,element):
        if self.length == 0:
            raise Exception("list is empty")
        elif self.length == 1:
            if self.head.item == element:
                self.head = self.tail = None
                self.length -= 1
            else:
                raise ValueError("element not found")
            
        if self.head.item == element:
            self.head = self.head.next
            return
        current = self.head.next
        prev = self.head
        while current.item != element:
            prev = current
            current = current.next
            if current == None:
                raise ValueError("element not found")
        
        prev.next = current.next
        self.length -= 1
fiery cosmos
# 
s = '{}'

mapping = {')': '(', '}': '{', ']': '['}

for i in range(len(s)-1):
    
    try:
        if s[0] != mapping[s[1]]:
    
            print(False)
            exit()

    except KeyError:
        print(False)
        exit()     
        
print(True)
#

this one properly validates a string of len 2 only containing a single set of parenthesis. it rejects incorrect matches or parenthesis occurring in the wrong order, eg '}{'

#

i took the mapping from the other solution

wise hull
#

Anyone herer

fiery cosmos
#

idk why they wrote in the closing parentheses as keys and the opening ones as values, i suppose to skip them and allow them to be a part of the stack in the original problem

fiery cosmos
wise hull
#

I am a newbie too

fiery cosmos
#

what you need

wise hull
#

I am lost, I am not able to decide if I should use python for learning data structure or c/c++

fiery cosmos
fiery cosmos
wise hull
#

Oh

#

Oh Yeah

snow anvil
fiery cosmos
# snow anvil just use a stack man

the primary leetcode problem i was trying to solve uses just that, this was a modified one to solve just a single set of parentheses which was suggested by another user

snow anvil
#

Idk why you'd only write it for one parentheses but sure

haughty mountain
#

e.g. (()(()))()

#

which is a simpler version of the version where you allow multiple kinds

fiery cosmos
#

ohh

#

hmm okay let me try

#

hmm getting KeyError

#

wait nope

#

doesn't work

#

okay this seems to work:

s = '()()()('


def validfindr(string):

    mapping = {')':'(','(':')'}

    for i in range(len(string)):
        if string[i-1] != mapping[string[i]]:
            return False
        
    return True

print(validfindr(s))
haughty mountain
#

!e does that even work for the example I gave?

s = '(()(()))()'


def validfindr(string):

    mapping = {')':'(','(':')'}

    for i in range(len(string)):
        if string[i-1] != mapping[string[i]]:
            return False
        
    return True

print(validfindr(s))
halcyon plankBOT
#

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

False
haughty mountain
#

no

#

it doesn't

#

it will even not work for (())

fiery cosmos
#

that should eval to False

#

the original leetcode problem, so long as an parentheses is not immediately followed by it's matching closing parenthesis, the string evals to false

#

let me get the link

#

hmm no that doesn't seem to be a requirement (what i mentioned above)

#

anyhow, how would you solve? in the case of parentheses string composed of all one type?

snow anvil
#

a stack

fiery cosmos
# 
s = '(()))'


def validfindr(string):

    stack = []
    mapping = {')':'('}

    for char in string:
        if char in mapping:
            if stack.pop() != mapping[char] or not stack:
                return False
        else:
            stack.append(char)
        
    return True

print(validfindr(s))
#

this one seems to work, but then i just built it looking at a solution 😭

#

i'm trying to visualize how it works

#

in the first char, the ( is not in mapping, because if char in mapping: is only looking at keys?

snow anvil
#

move on to another problem and keep thinking about this problem when u are going on a walk or whenever convenient

fiery cosmos
#

facts

#

hmm #35 Search Insert Position should be interesting

#

notably the runtime must be O(log(n)), therefore a recursive solution would work

#

i was trying to implement a binary search type paradigm, however, i get tripped up on trying to return the index of where the search term should occur in the case that the search term does not occur in the array

haughty mountain
snow anvil
#

sure its just easier imo

haughty mountain
#

than just keeping a variable for the depth?

snow anvil
#

sure less memory required makes sense ig

haughty mountain
#

the stack is basically an extension of the depth counter, but in the case where you need to care about paren types matching

haughty mountain
snow anvil
#

that is true I just find the stack easier intuitively

fiery cosmos
haughty mountain
#

maybe write the solution without the dict

#

to understand what the solution is about

fiery cosmos
#

i think i understand it

haughty mountain
#

!e

s = '(()(()))()'

def validfindr(string):
  depth = 0

  for c in string:
    if c == '(':
      depth += 1
    else:
      depth -= 1
      if depth < 0:
        return False

  return depth == 0

print(validfindr(s))
halcyon plankBOT
#

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

True
haughty mountain
#

this is the most basic thing

#

the multiple paren version is an extension of the same thing

haughty mountain
snow anvil
#

yes I know

fiery cosmos
#

i guess this makes sense. not straight away

#

i'm having trouble where i can study a solution enough and understand it, but developing my own solutions to the easy problems is a challenge

#

i think i've solved like 3 of them without looking up an answer. i usually can get on the right track but never quite get it, like the case where a binary search for problem 35 was the right approach, but i didn't know how to return the index of where the search term should occur, in the case it doesn't appear in the array

#

going to work on #35

#

whats the VSCode shortcut for block comment out?

#

cntl + /

#

so the way i am recursively implementing a binary search for the above problem, it will not work as i am breaking the array into smaller bits each time, and thus losing the original index information. any direction?

#

seems like if rather than giving the recursive call a slice of the original array, i could instead give it new indices, effectively passing it a new space to search

fiery cosmos
#

here is a solution:

def binsearch(array, tar):
    
    start, end = 0, len(array)-1

    while start <= end:
        
        mid = (start + end) // 2

        if array[mid] == tar:
            return mid

        elif array[mid] < tar:
            start = mid + 1

        else:
            end = mid - 1

    return start


print(binsearch([1,2,3,5,7,9], 8))
#

i tried to have chatgpt walk me through the approach without giving me code or pseudocode, but it doesn't listen

#

i stepped through it in my head and it seems to make sense, but dreaming it up on my own is another story

#

at least i can see now that there is a different variable returned, start, for the case when the search term does not occur in the array, rather than in the case where it does, which is mid

misty relic
dawn cliff
# 
def​ ​print_numbers_version_two​(upperLimit):
  number = 2

​  ​while​ number <= upperLimit:
​    print​(number)
​     
​    ​# Increase number by 2, which, by definition,​
​    ​# is the next even number:​
​    number += 2

How many steps are there in this algorithm? My textbook says 2.5N

#

But I just see 2N

haughty mountain
#

wdym by steps?

#

the loop runs roughly N/2 times

lean walrus
#

if you look close enough, you can see 5N steps

#

so counting steps doesnt make any sense

#

you should be interested in asymptotics (O(N) in this example) or iteration count (N/2 in this example)

dawn cliff
#

Idk if you guys are interested but he(textbook author) might have been talking about a different example

dawn cliff
lean walrus
#

so what is the problem?

#

it is neither 2N nor 2.5N

hollow spire
#

hi I'm currently learning wave function collapse how does this work? its pretty confusing

Screenshot_2023-12-29-07-38-16-43.jpg
austere sparrow
#

So I have a strange question...

#

What is the actual complexity of sleep sort? I'm assuming that the scheduler that dispatches the calls is not really O(N) in the number of tasks

stable pecan
#

why not

austere sparrow
# stable pecan why not

Well, suppose you just finished handling an event and you need to pick the next one. You need to choose the next timer, so you need to order them somehow

#

For example you use a BST, so every pick will be logarithmic

stable pecan
#

usually sorted on a heap

austere sparrow
#

yeah, so not an O(1) pop iirc?

stable pecan
#

O(1) pop, but not O(1) push

#

it's like log n push

#

i think

austere sparrow
#

Yeah, so while setting up the timers you'll be doing more than O(N)

stable pecan
#

suppose so

austere sparrow
#

maybe radix-sorted heap is not a thing and I'm a dummy

stable pecan
#

some languages might, dunno

#

python probably just uses the sort it already has implemented

#

maybe not, i think all heaps work the same

#

like, there are different kinds of heaps, but they all still sort in log n by moving down the tree

agile sundial
stable pecan
#

i dunno what a multi level feedback queue is

agile sundial
#

it's just a bunch of fifo queues with different priority for running

stable pecan
halcyon plankBOT
#

src/twisted/internet/base.py line 1051

def runUntilCurrent(self) -> None:```
`src/trio/_core/_run.py` line 248
```py
def next_deadline(self) -> float:```
`curio/timequeue.py` line 93
```py
def expired(self, deadline):```
stable pecan
halcyon plankBOT
#

Lib/asyncio/base_events.py line 1923

def _run_once(self):```
vocal gorge
#

https://en.wikipedia.org/wiki/Brain_Fuck_Scheduler gets away with a single queue i think

Brain Fuck Scheduler

The Brain Fuck Scheduler (BFS) is a process scheduler designed for the Linux kernel in August 2009 based on earliest eligible virtual deadline first scheduling (EEVDF), as an alternative to the Completely Fair Scheduler (CFS) and the O(1) scheduler. BFS was created by an experienced kernel programmer Con Kolivas.The objective of BFS, compared to...

agile sundial
#

cool

small gulch
#

Hello, Is there a package similar to dataclasses that allows you to use other types of data structures, such as Mappings, models with editable constructors?

#

The data entered could be similar to these.
mappings with undefined keys

{
    "34ba7bc2-329h-2352-2323-abj3a7c1": {
        "type": 1,
        "title": "..."
    },
    "12f2a8b1-a4b1-c6f1-bbc2-a8f5f4": {
        "type": 1,
        "title": "..."
    }
}

objects without key reference

{
    "media": [
        2,
        "https://the-web-url",
        null,
        {
            "title": "metadata: title"
        }
    ]
}
#

?

#

to create classes similar to dataclasses.

class MyObject:
    type: int
    title: str

class ObjectMapping(Mapping[str, MyObject]):
    ...

class Media:
    type: int
    url: str
    description: str | None
    metadata: dict
floral dew
#

hey everyone, i'm having trouble with this simple graph problem. my first thought was "oh, this is just asking if there exists a path from (1, 1) to (M, N) in the graph of cells, which is equivalent to asking if there exists a path from (M, N) to (1, 1)."

and since computing products are cooler than computing factors, i went with that second option and did a BFS in this initial solution.

getting TLE on the later test cases, i thought it must be a constant factor issue since i'm sure O(MN) is the lowest possible time complexity. but i couldn't figure it out, so i changed my graph a teeny bit, resulting in the second solution.

still TLE! i gave up - must be a "python too slow" issue, i thought. then i find this DFS python solution that passes on one judging website but not on another!

can you help me figure out where's the bottleneck in my two solutions, and why the third works? i appreciate any and all help, thank you!

regal spoke
# floral dew hey everyone, i'm having trouble with [this simple graph problem](https://dmoj.c...

You could try this BFS solution. This is how I would have solved that problem

n = int(input())
m = int(input())
A = [[int(x) for x in input().split()] for _ in range(n)]

BIG = 10**6 + 10
mapper = [[] for _ in range(BIG)]
for i in range(n):
  for j in range(m - (i == n - 1)): # Avoid (n-1,m-1)
    mapper[A[i][j]].append((i,j))

bfs = [(n - 1, m - 1)]
for i,j in bfs:
  prod = (i + 1) * (j + 1)
  bfs += mapper[prod]
  mapper[prod] *= 0 # Empty the list mapper[prod]

if mapper[A[0][0]]: # Has mapper[A[0][0]] not been seen?
  print('no')
else:
  print('yes')
#

To make it run fast, my solution is very basic and uses no hash tables. I kind of doubt that it is possible to make a Python solution that runs much faster than this.

#

Btw in your BFS solution, I think you should have visited.add(neighbor) when appending neighbor to dq. You should probably also empty ADJ[value] after iterating over it to avoid going through it multiple times:

    for neighbor in ADJ[value]:
        if neighbor not in visited:
            visited.add(neighbor)
            dq.append(neighbor)
    del ADJ[value]
#

My guess is that if you change to this then you will get AC ^

regal spoke
#

Played around optimizing my code some more

import sys
input = sys.stdin.buffer.readline

n = int(input())
m = int(input())

max_val = min(n * m + 1, 10**6)
A = [[min(int(x), max_val) for x in input().split()] for _ in range(n)]

BIG = max_val + 1
mapper = [[] for _ in range(BIG)]
for i in range(n):
  Ai = A[i]
  for j in range(m - (i == n - 1)): # Avoid (n-1,m-1)
    mapper[Ai[j]].append((i + 1) * (j + 1))

empty_list = []
bfs = [n * m]
for prod in bfs:
  bfs += mapper[prod]
  mapper[prod] = empty_list # Empty the list mapper[prod]

if mapper[A[0][0]]: # Has mapper[A[0][0]] not been seen?
  print('no')
else:
  print('yes')
#

It easily gets full score

#

TL is 2 s

small gulch
haughty mountain
small gulch
haughty mountain
#

this channel is more about the computer science side of things

haughty mountain
small gulch
quaint gorge
#

Hey guys, i tried to make a guessing game but gave up when i couldn't figure out how to stop a glitch.

# 
gameStatus = input("Hello, this is a guessing game. Type and enter start to play")
a = "start"
b = "Start"
min_value = 1

if gameStatus.lower() == a or gameStatus == b:
    max_value = int(input("Enter the maximum number that the game should use:"))
    average = int(input("Now enter the average number:"))

    while True:
        guess = int(input("Give it your best guess: "))

        if guess == average:
            print("You have guessed correctly and won the game!")
            break
        elif guess > average:
            max_value = min(max_value, guess - 1)
            print(max_value, guess - 1)
            print("You have guessed too high, the new guess ranges are from", min_value, "to", max_value)
        elif guess < average:
            min_value = max(min_value, guess + 1)
            print("You have guessed too low, the new guess ranges are from", min_value, "to", max_value)
        if guess < min_value or guess > max_value:
            print("You guessed out of the boundaries")
#

Chat GPT code ^

# 
#This code is a guessing game for practice.
gameStatus = input("Hello, this is a guessing game. Type and enter start to play")
a = "start"
b = "Start"
min = 1

if gameStatus == a or b:
   max = int(input("Enter the maximum number that the game should use:"))

average = int(input("Now enter the average number:"))
guess = 1
while average != guess:
    guess = int (input("Give it your best guess"))

    if guess == average:
        print("You have guessed correctly and won the game!")
    if guess > average:
        max = guess - 1
        print("You have guessed too high, the new guess ranges are from", min, "to", max)
    if guess < average:
        min = guess + 1
        print("You have guessed too low, the new guess ranges are from", min, "to", max)
    if guess < min:
        print("You guessed out of the boundaries")
    if guess > max:
        print("You guessed out of the boundaries")
#

My code ^

#

basically every time someone guesses a wrong answer that's too large or too small the code should narrow the gusses down. But i couldn't figure out how to stop the boundary from expanding if someone was to give a number outside of it.

#

chatgpt figured it out but i don't understand how

#

ik it has to do with the min and max function

leaden rivet
#

what is the best way to learn data structures and algo

#

as a complete beginner

snow anvil
wispy cipher
#

Hi , want to start leetcode but facing difficulties with run-time and on top of that my way of doing stuff is crude most of the time like I always try to use greedy approach which is not suitable for everything . Is there anyway I can improve on my DSA coding clean. Man I suffered alot when I did an interview just because of DSA 😦

dawn cliff
#

I was wondering if anyone could help explain to me why this is not O(N^2)

image.png
#

If X is the amount of elements in the inner arrays, doesn't the inner loop loop X times for N elements (inner arrays)?

dawn cliff
#

I'm going through it right now, the screenshot is from it

lean walrus
dawn cliff
#

Ohhh I get it now. Since N is the number of arrays, it is defintely O(N) then

lean walrus
#

wrong

#

if N is the number of arrays and K is the average length of arrays, then complexity is O(N K)

covert thorn
#

N represents how many numbers there are

haughty mountain
#

it's almost like the answer will depend on how you define your parameters 🫠

#

O(n²) is just wrong though ||unless you're making dumb parameter choices on purpose||

agile sundial
#

if we have all the dimensions the same size O(n^2) is correct for "let n = the size of a dimension"

dawn cliff
#

So it is O(N) because N is the total number of elements

haughty mountain
dawn cliff
haughty mountain
haughty mountain
#

I get what the textbook is trying to teach, but the phrasing is iffy to me

agile sundial
#

I agree

onyx olive
#

hello

gaunt mist
#

hi

#

@gaunt mist

harsh trail
#

im getting a recursion depth error in day 16 part 1

#

though it works just fine with test input

#

I have a function receives the current position and calculates a list with the next positions

#

and then i use those in a recursive function that i use to fill a dict

#

the stopping condition is met whenever that position has already been visited with the same direction

#

the error that i get is:

    if (nxt_pos[0] < h and nxt_pos[0] >= 0
        ^^^^^^^^^^^^^^
RecursionError: maximum recursion depth exceeded in comparison
#

and i find it weird, cause why would it point at comparison as the cause of the bug in the recursion?

random bison
#

im new to python and the reason i want to learn is thrtough data automation. Could someone help me and maybe even just show me down the rihgt path?

#

i have anoconda because i was told it is good for what i want to do

harsh trail
#

||```py
def fill_tiles(energized, grid, curr, dr):
if curr not in energized:
energized[curr] = [dr]
else:
found = False
for tmp_dr in energized[curr]:
if tmp_dr == dr:
found = True
break
if found:
return
else:
energized[curr].append(dr)

for nxt, nxt_dr in calc_nxt(curr, dr, grid):
    fill_tiles(energized, grid, nxt, nxt_dr)
#

calc_nxt returns an array of the next tiles to visit. It checks current tile, and depending on previous direction (dr) it can calculate it

#

the issue is basically the calc_nxt function is being called too many times

haughty mountain
#

your options are either to not writing it recursively (which is what I usually do) or raising the limit and hoping it's fine

haughty mountain
harsh trail
#

i cant believe it. It was fucking python limiting recursion

#

unbelievable

haughty mountain
# harsh trail ||```py def fill_tiles(energized, grid, curr, dr): if curr not in energized:...

untested, but this is how I would write it
||```py
def fill_tiles(grid, start_curr, start_dr):
stack = [(start_curr, start_dr)]
energized = collections.defaultdict()
while stack:
curr, dr = stack.pop()
if (curr, dr) in energized and dr in energized[dr]:
continue
energized[curr].append(dr)

stack.extend(
for nxt, nxt_dr in calc_nxt(curr, dr, grid):
  stack.append((nxt, nxt_dr))

return energized

#

roughly

harsh trail
#

ty mate

haughty mountain
#

trying to keep the core of your code

harsh trail
#

im super tired. going to sleep now

#

bye!

haughty mountain
# harsh trail unbelievable

and no it's not, python is quite bad at deep recursion and is notorious for putting a pretty low limit which you can easily run into doing a recursive dfs

quaint gorge
# 

def tri_recursion(k):
    if(k > 0):
        result = k + tri_recursion(k - 1)
        print(result)
    else:
        result = 0
    return result

print("\n\nRecursion Example Results")
tri_recursion(4)
#

Hey guys i'm having a hard time figuring out why this loops

#

there's no for loop but it still loops

errant hearth
#

because it calls itself

quaint gorge
#

How come it doesn't just calculate the recursion for the value "4"

quaint gorge
#

since there's only two instances where it calls itself in the code

#

shouldn't it only calculate the argument twice

errant hearth
#

When you input 4, it does:

- k=4
  - 4 > 0
    - result = 4 + tri(4 - 1) -> 4 + tri(3)
      - k = 3
        - 3 > 0
          - result = 3 + tri(3 - 1) -> 3 + tri(2)
            - k = 2
              - 2 > 0
                - result = 2 + tri(2 - 1) -> 2 + tri(1)
                  - k = 1
                    - 1 > 0
                      - result = 1 + tri(1 - 1) -> 1 + tri(0)
                        - k = 0
                          - 0 == 0
                            result = 0
                      - result = 1 + 0
                - result = 2 + 1 + 0
          - result = 3 + 2 + 1 + 0
    - result = 4 + 3 + 2 + 1 + 0
- result = 10```
quaint gorge
#

Fuck i might understand now...

#

But im gonna ask one more question

errant hearth
#

shoot

quaint gorge
#

How come it doesn't stop at the first calculation after "return result"

errant hearth
#

because it goes into the next iteration before reaching the return

quaint gorge
#

Ah i'm trying to understand but it's still confusing why

#

so k starts off as number 4 in this code

#

I'm imagining that k turns to 3....2...1 after each loop

#

but how does it know to do that

# 
 result = k + tri_recursion(k - 1)
        print(result)
#

Here all i can see is that there's a variable named result being assigned to an int expression

#

and then it's being printed

errant hearth
#

when assigning result, it includes a call to the current function

#

so it'll evaluate the function, then use the result to continue

quaint gorge
#

I get it

#

So after each iteration it returns the new value to the caller

#

and then since that if statement is there, it'll keep doing it until it's 0

quaint gorge
#

but if it's executed before that then i get it

#

nvm i'm still wrong

#

thank's though i'm going to keep rereading your explaination

errant hearth
muted wharf
#

@quaint gorge it would be nice if you google "what is recursion in programming" and get some more abstract explanation about the concept of recursion in computer science...

quaint gorge
#

I think i underestimated the topic because i was following w3schools lol

#

going to go watch some vids on it

muted wharf
#

although not resource efficient it is considered one of the most elegant ways to solve a problem and some problems can only be solved through recursion. but due to not being resource wise in terms of memory and stack it is generally avoided

errant hearth
muted wharf
#

@errant hearthTowers of Hanoi

quaint gorge
#

I get it now, love you both 🙏🏾@errant hearth @muted wharf

errant hearth
#

great job!

muted wharf
#

Glad we helped 👍

narrow mica
#

For the specific case of the Tower of Hanoi, there's actually an alternative method that uses binary to solve it

muted wharf
narrow mica
muted wharf
#

When I'm saying is the same for the CPU I mean in an abstract way. I mean the complexity. On a low level perspective it depends on the programming language and the compiler which I suspect most of the times is deferent than actual recursion yes

dapper saddle
#

Im running into a bit of an issue.

I have a bunch of categories and some of them correlate with each other but not all of the ones that do do not correlate with each other.

Whats a good way to visualize this.

There are 33 categories so its a bit of a mess with a heatmap.

For example A B and C correlate, D correlates with A and B but not C

shadow glen
#

okay so
how do i clone the contents of a string and list instead of treating them as objects?
i realize my code is copying them as object instead as their contents
as you can see:

# 
i: !roll
Initiator
command_pivot=['!roll']
i: (1d10+2)
simple command
main_command=[['!roll', '(1d10+2)']]
main command appender
i: !if
Initiator
command_pivot=['!if']
i: (!roll
Initiator
sub_command_pivot=['(!roll']
i: (1d20)
simple command
main_command=[['!if', '(1d20)'], ['!if', '(1d20)'], ['!if', '(1d20)']]
i: >
content
i: 10)
Ender
main command appender
i: !else
Initiator
command_pivot=['!else']
i: (!echo
Initiator
sub_command_pivot=['(!roll', '(!echo']
i: (Failure))
simple command
main_command=[['!else', '(Failure))'], ['!else', '(Failure))'], ['!else', '(Failure))'], ['!else', '(Failure))'], ['!else', '(Failure))']]
result: [['!else', '(Failure))'], ['!else', '(Failure))'], ['!else', '(Failure))'], ['!else', '(Failure))'], ['!else', '(Failure))']]
#

https://paste.pythondiscord.com/67NQ
it was suppose to be
[["!roll", "1d10+2"], ["!if", ["!roll", "1d20"], "> 10"], ["!else", ["!echo", "Failure"]]
that grabbing my from my args string

dawn cliff
# 
def intersectionOfTwoArraysHashTable(array1, array2):
  
  hashTable = {}
  intersection = []
  
  for num in array1:
    hashTable[num] = True
  
  for num in array2:
    if hashTable[num] == True:
      intersection.append(num)
  
  print(intersection)
  
  
intersectionOfTwoArraysHashTable([1, 2, 3, 4, 5], [0, 2, 4, 6, 8])

What is wrong with my hash table?

#

I keep getting a type error but I don't know how else I'm supposed to check for True in the second for loop

orchid violet
#

you probably only wanted an membership check

#

sorry to be pendantic here but, in python you're passing an list1, list2, not an array1 nor array2

dawn cliff
orchid violet
dawn cliff
#

I'm just trying to use a hash table for the first time and this is the problem I got

orchid violet
#

consider what happens if 0 does not exist in the dict for example

dawn cliff
#

even though I can use in I'm trying to use a hash table, so I guess a dictionary in python

#

well

#

I thought the for loop would just continue

orchid violet
#

you issue boils down to

#

!e ```py
example = {0: 1}

print(example[1])```

halcyon plankBOT
#

@orchid violet :x: Your 3.12 eval job has completed with return code 1.

001 | Traceback (most recent call last):
002 |   File "/home/main.py", line 3, in <module>
003 |     print(example[1])
004 |           ~~~~~~~^^^
005 | KeyError: 1
dawn cliff
#

wait really? I'm putting in the value?

orchid violet
#

1 does not exist as a key, so it raises an KeyError

dawn cliff
#

oh nvm

#

but an else statement wouldn't help

orchid violet
#

you can do something like

#

!e ```py
example = {0: 1}

print(1 in example)

halcyon plankBOT
#

@orchid violet :white_check_mark: Your 3.12 eval job has completed with return code 0.

False
orchid violet
#

does that make sense?

dawn cliff
#

yeah

#

I'm just trying to learn whatever is the standard way of using a hash table is I guess

orchid violet
#

are you coming from another language?

dawn cliff
#

I know some JS

#

but that's it

orchid violet
dawn cliff
#

i'll try sure

orchid violet
#

a membership check is basically just does x exist in the container?

dawn cliff
#

I'm stuck on how to use a hash table though with this

#

I can get this function to work with in

#

but that's not using a hash table

orchid violet
#

yes it is

dawn cliff
#

oh

orchid violet
#

because an in lookup uses the dictionary (hashtable) to do the lookup in constant time

#

you could also use uh

#

!d dict.get

halcyon plankBOT
#
dict.get 

get(key[, default])```
Return the value for *key* if *key* is in the dictionary, else *default*. If *default* is not given, it defaults to `None`, so that this method never raises a [`KeyError`](https://docs.python.org/3/library/exceptions.html#KeyError).
dawn cliff
# 
def intersectionOfTwoArraysHashTable(array1, array2):
  
  intersection = []

  for num in array2:
    if num in array1:
      intersection.append(num)
  
  print(intersection)
  
  
intersectionOfTwoArraysHashTable([1, 2, 3, 4, 5], [0, 2, 4, 6, 8])
#

so that is using a hash table?

#

oh

#

ok

#

so here is my thing, the solution was in javascript and so I've been trying to implement it in python

#

and I guess I just have to learn how python works lol

orchid violet
#

yep

#

python and javascript are different languages

dawn cliff
#

this was the textbook's solution:

     ​function​ getIntersection(array1, array2) {
​       ​let​ intersection = [];
​       ​let​ hashTable = {};
​     
​       ​for​(​let​ i = 0; i < array1.length; i++) {
​         hashTable[array1[i]] = ​true​;
​       }
​     
​       ​for​(​let​ j = 0; j < array2.length; j++) {
​         ​if​(hashTable[array2[j]]) {
​           intersection.push(array2[j]);
​         }
​       }
​     
​       ​return​ intersection;
​     }
#

so I was trying to declare a hash table variable in my python earlier but I guess I didn't even need to declare any sort of hash table

orchid violet
# 
def intersectionOfTwoArraysHashTable(array1, array2):
    hashTable = {}
    intersection = []

    for num in array1:
        hashTable[num] = True

    for num in array2:
        if num in hashTable:
            intersection.append(num)

    return intersection


print(intersectionOfTwoArraysHashTable([1, 2, 3, 4, 5], [0, 2, 4, 6, 8]))
dawn cliff
#

but what is the point of the dictionary in there? it's not being used

orchid violet
#

here

#

but you're not actually using it, no

dawn cliff
#

But in my final solution I didn't even use a dictionary

orchid violet
#

yeah you don't need one

dawn cliff
#

so all I did was use in to look within a list for membership?

orchid violet
#

i would use a set here honestly

dawn cliff
#

like literally I'm just trying to use a hash table in python. that's all i'm trying to do

orchid violet
#

this is roughly how i'd done it ```py
def KRRT_impl(list1, list2):
temp1 = set(list1)
temp2 = set(list2)
return list(temp1.intersection(temp2))

#

sets use a hashtable under the hood of sorts

dawn cliff
#

ok yes that makes sense but I'm taking a DSA class so I'm trying to do it without too many built in methods ya know

orchid violet
#

what does this do?

# 
​         ​if​(hashTable[array2[j]]) {
​           intersection.push(array2[j]);
#

i dont know any js

dawn cliff
#

it checks if the value in array2 at index j is not null I think and then pushes it to intersection

#

idk though exactly if its checking if its null or not

orchid violet
#

so

# 
        if num in hashTable:
            intersection.append(num)
``` essentially what this is doing?
#

actually no

#

in a way yes

#

in python, it just checks if the number exists in the hash table

#

if it does, "push"it to the intersection list

dawn cliff
# 
def intersectionOfTwoArraysHashTable(array1, array2):
  
  intersection = []
  mySet = set(array1)

  for num in array2:
    if num in mySet:
      intersection.append(num)
  
  print(intersection)
  
  
intersectionOfTwoArraysHashTable([1, 2, 3, 4, 5], [0, 2, 4, 6, 8])

So is this better

dark tendon
#

idk if this works, but is this also valid?

def f(a, b):
  return [x for x in set(a) if x in set(b)
#

basically what u did, but in one line

#

and u can do the set() on array2 too

narrow mica
# 
def f(a, b):
  return list(set(a) & set(b))
haughty mountain
#

otherwise you're re-making the set for every element

raw zealot
#

does the iterative and recursive form of an algorithm always have same time complexity ? idts

hollow walrus
#

who wants to practice matplotlib with me?

shut breach
dawn cliff
#

I cannot figure out why my code is wrong. I'm supposed to be getting f but I'm getting None.

# Write a function that accepts a string that contains all the letters of the alphabet
# except one and returns the missing letter. For example, the string, "the quick brown
# box jumps over a lazy dog" contains all the letters of the alphabet except the letter,
# "f". The function should have a time complexity of O(N).

def myFunction(my_string):
  
  dictionary = {}
  alphabet = "abcdefghijklmnopqrstuvwxyz"
  
  for character in alphabet:
    dictionary[character] = True
  
  for character in my_string:
    if not dictionary.get(character, False):
      return character
  
  #missing alphabet character = f  
  
print(myFunction('thequickbrownboxjumpsoveralazydog'))
#

btw the purpose of this exercise is to practice hash tables

coral void
#

A set would be the more-natural choice here. Sets are for testing membership / whereas, dictionaries are for doing key-->value lookups. The tip-off: You store the same value [True] for every [a..z] key; if every key returns the same answer, it's a major clue that you're only interested in the presence or absence of a key—and that spells “set.”

#

set(string.ascii_lowercase) - set('thequickbrownboxjumpsoveralazydog') #==> {'f'}

coral void
#

Some style-notes: Instead of typing the 26 letters of the alphabet, my above solution used ‘string.ascii_lowercase’ (the digits, uppercase-letters, etc. are also available—see: https://docs.python.org/3/library/string.html#module-string ). Using Python-provided initialized strings avoids the risk of introducing a hard-to-spot bug caused by a typo. The rule is: “Let the machine do the dirty-work.”

Also: If you're going to be comparing different messages against a set or dictionary whose contents does not change, then, you want to load that set only once—you should not be pointlessly reloading the dictionary here with the same info every time you test a new message's text.

And finally: As for your program's use of double-negatives—namely, using “if not False that the letter is not in the dictionary” to trigger the return—all I can say is:
Not bad it's not,
because double-negatives are burdensome to decipher.
There's no need for a double-negative here,
because Python lets you say exactly what you mean:
if k in d: print('Eureka!')
or, conversely,
if k not in d: print('Key not here; have you checked under the bed?')

Python documentation
string — Common string operations

Source code: Lib/string.py String constants: The constants defined in this module are: Custom String Formatting: The built-in string class provides the ability to do complex variable substitutions ...

stray fractal
#

how would i find the longest common substring between a string and an individual string from a list of strings efficiently

stray fractal
# 
def longest_sub_ss(s: str, t: str, z: int = 0):
    # Wikipedia-based
    L = {}
    ret = set()
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                L[i, j] = Lij = L.get((i - 1, j - 1), 0) + 1
                if Lij > z:
                    z = Lij
                    ret = {(i, j)}
                elif Lij == z:
                    ret.add((i, j))
    return z, ret

def longest_sub_sl(s: str, l: list[str]):
    most_len = 0
    most_len_set = set()
    for i, t in enumerate(l):
        t_len, t_set = longest_sub_ss(s, t, most_len)
        if not t_set:
            continue
        t_set = {(y, i) for y in t_set}
        if t_len > most_len:
            most_len = t_len
            most_len_set = t_set
        elif t_len == most_len:
            most_len_set |= t_set
    return most_len, most_len_set
``` here's some basic code and i'm not sure if there's a better algorithm
coral void
narrow mica
stray fractal
haughty mountain
#

rather than the O(nm) you have

#

any more info about the input like string sizes?

stray fractal
#

i think 100 characters maximum?

#

probably applied on a list with a length of up to 1024

haughty mountain
#

and the one string is similar in size with the ones in the list?

stray fractal
#

yep

haughty mountain
#

so, suffix automatons might be an interesting thing

#

they are apparently less annoying than suffix trees

#

linking to the section applying it for LCS
https://cp-algorithms.com/string/suffix-automaton.html#longest-common-substring-of-two-strings

Suffix Automaton - Algorithms for Competitive Programming

The goal of this project is to translate the wonderful resource http://e-maxx.ru/algo which provides descriptions of many algorithms and data structures especially popular in field of competitive programming. Moreover we want to improve the collected knowledge by extending the articles and adding new articles to the collection.

#

seems it would be enough to build the automaton for the one string, and you can re-use it for every subproblem

coral void
# stray fractal doesn't this get the common for *all* strings inside the list

If the goal is speedy execution in Python, I suspect that none of the classical results on the analysis of algorithms
will be directly applicable to the programs that you transliterate from C (& the like) into C-Python. In C-Python [without a JIT specializer], looping is slow. The way to gain speed is to delegate as much of the work as possible to those modules that are written in C—even when this involves oddly indirect and convoluted paths, because reducing the overall
execution-time is the goal.

delicate lion
#

Is there a python library for lattice data structure with ordering and meet and join operators?

fiery cosmos
#

what is the best way to store an arbitrary amount of data, given that i want it to occur in what could be easily converted to a single column of a spreadsheet

#

nvm, i think i want to run sentiment analysis first and then drop that value into a csv in a specific col

vivid lynx
#

i wanna check is like a certain string is part of string in a loop but not the whole string just the first six charecters i cant figure out how to match patterns like that without regex

slate hedge
#

I am intending to run a backtracking algorithm for a game and store the states in a data struct, where each element stores the current state of the game, how many steps it took to get to this state from the starting position and the best predecessor state

#

Now, since the backtracking algorithm will repeatedly come across already seen states, I need to be able to update the struct if the predecessor state has improved (in specific: if it took less steps to get to the same state, update the predecessor)

#

however then I'd also have to update all states emerging from that updated state by changing their distances to the start position as well, which is where I'm currently a bit stuck

#

a sample of how this could look like:

#

The uppermost node would be the root in this case, its distance to itself is 0

#

now if add an edge to this graph (red)

#

the distances for the red-circled elements would decrease

#

but if my graph/struct contains millions of nodes and I continuously add edges, changing the distances for entire parts of the graph will likely be too slow

fiery cosmos
#

!e

halcyon plankBOT
#
Missing required argument

code

#
Command Help

!eval [python_version] <code, ...>
Can also use: e

Run Python code and get the results.

This command supports multiple lines of code, including formatted code blocks. Code can be re-evaluated by editing the original message within 10 seconds and clicking the reaction that subsequently appears.

The starting working directory /home, is a writeable temporary file system. Files created, excluding names with leading underscores, will be uploaded in the response.

If multiple codeblocks are in a message, all of them will be joined and evaluated, ignoring the text outside them.

Currently only 3.12 version is supported.

We've done our best to make this sandboxed, but do let us know if you manage to find an issue with it!

hollow ravine
#

So my next semester is going to my introduction to algorithms is there anything you guys recommend to learn so when they show up I'll be more pre-pare. (Context, I basically know nothing about algorithms expect binary search)

keen hearth
#

Khan Academy is pretty good for that.

#

But prioritise the material of your actual algorithms course.

outer rain
#

instead of having the actual distance in each node, store how much the distance in the node is different from the distance in the parent node

#

and by "parent node" I mean any parent node of the node, any is fine

#

and then to get the distance from the node, you go up the predecessors of that node and sum up the differences

#

That way updating the distance is O(1), and getting the distance is O(depth), which is likely to be small in your case

#

but if it is not, you can look up "Heavy-Light decomposition", it's a pretty complex data structure which will get you to O(log n) update and O(log^2 n) get

stray fractal
#

i got like 2x slower when i benchmarked it

outer rain
stray fractal
#

i think it's all the C to python object conversions

outer rain
#

even so, conversion is linear, the algorithm is not, it shouldn't that that long

stray fractal
#

yeah apparently too many C to python object conversions
i'll try to make a better one when i have time to

narrow mica
# slate hedge however then I'd also have to update all states emerging from that updated state...

Lazy propagation? The idea is to update distance only when you need it
Let's call the node you circled red n
When you add the red edge, the distance got better, so you want to update n and all nodes below it
Here's the trick: Only update n and its direct children (for now)
Update the distance of n, and update a .tag attribute of n's direct children. Don't do anything to anything below that
The .tag will function like an unresolved update
Later, once you traverse to a node m, use the .tag to update m's distance, then update the .tag of m's children

slate hedge
narrow mica
slate hedge
#

maybe let's consider some sample, then it'll probably get clearer for me

image.png
#

e.g. if I add the following edge now:

#

then the node with distance 4 would update to distance 2

#

and as you mentioned its direct child would update from dist 5 to dist 3

#

now if I select the node at the bottom and ask for its distance, how would be prop. work?

narrow mica
narrow mica
# slate hedge

Actually, I've been building on the assumption that once you determine the red edge is better, the predecessor should switch and the 3-4 edge should be removed?

slate hedge
#

yeah, it'll reduce the storage amount, but doesn't speed up the distance determination

#

if I want to know the distance of the node which currently has dist 6, I'd go backwards until the "newest change" is reached

#

however my issue is that I can't know what's the newest change

#

for instance I'd store the best predecessor:

image.png
#

as an arrow symbolized here

#

if I add an edge

#

the predecessor of 5 updates

#

because it found a better one

#

so now the distance of that 5-node becomes 3

#

however I won't yet update all of the lower nodes of the changed node

#

now if I want to know the distance of the node with value 3

#

I'd walk backwards regarding the best predecessors

#

to determine the distance

#

the basic way would be to walk back to the root

#

and update all nodes on the way to the root

#

(I added another node on the bottom for clarity)

image.png
#

walked back to the root and now since I know the distance, I can update all of the circled nodes

#

however there is a problem with this approach

#

because if I don't update the children until I ask for the distance

#

then adding a new edge may change the predecessor falsely!

#

like this

#

so now I added an edge

#

but because the predecessor (6) was not yet updated

#

it thinks the connection to the left must be the best

#

but that isn't always the case

narrow mica
# 
class Node:
    parent: Node
    distance: int
    children: list[Node]
    tag: int = float('inf')

    def resolve(self):
        if self.tag is not None:
            self.distance = self.tag + 1
            self.propagate()
            self.tag = None
        
    def propagate(self):
        for child in self.children:
            child.tag = self.distance
            

def get_dist(node: Node):
    stack = [node]
    while stack[-1].parent is not None:
        stack.push(node.parent)
    for n in stack[::-1]:
        n.resolve()
    return node.distance
```I was thinking something like this
#

The downside is that get_dist is now O(depth), and the upside is that updating is O(1)

slate hedge
#

yea that's not desirable for my case, sry

narrow mica
#

Hmm

#

What compexity do you need?

slate hedge
#

preferrably get_dist is O(1) and update is less than O(depth)

#

the nodes would somehow need to know which state they're in in order to tell whether they're up to date

#

hm maybe it's just best to update all of the children

narrow mica
slate hedge
#

me neither, it'd certainly be a data struc I don't yet know, or at least some graph with grouping properties

slate hedge
#

just get_dist needs to be O(1)

#

and update shall make minimal use of the graph

narrow mica
#

The only thing that comes to mind right now is something like heavy-light decomposition, which will knock both complexities down to log level

slate hedge
#

I'll experiment a bit more, thx for the suggestions :)

narrow mica
haughty mountain
#

@narrow mica @slate hedge
just to check I understood the problem, it's conceptually trying to keep a shortest path tree up to date during edge additions?

Shortest-path tree

In mathematics and computer science, a shortest-path tree rooted at a vertex v of a connected, undirected graph G is a spanning tree T of G, such that the path distance from root v to any other vertex u in T is the shortest path distance from v to u in G.
In connected graphs where shortest paths are well-defined (i.e. where there are no negative...

narrow mica
haughty mountain
#

adding an edge will make a tree not a tree

narrow mica
#

Well it's not only adding, they'll remove the old edge connected to the parent if that new one is added

haughty mountain
#

in my head there is the shortest path tree, and there is an underlying graph it's the shortest path tree to

#

and you add edges to the underlying graph

narrow mica
#

No it's just a tree

#

The red edge is them attempting to reduce the distance from a node n to the root, and if successful, n will swap its predecessor

haughty mountain
#

is the end result not just wanting to know the shortest distance from the root to nodes?

#

for the current graph

narrow mica
#

Actually wait

#

I think they just want the depth of each node?
Because if it's just a tree the distance is just the depth

#

And I guess the problem is, in order for them to determine whether the original or the red edge is better, they need to know the depth at the moment
So they can't do offline updates

haughty mountain
#

I'm saying that in my head you're adding this red edge to some underlying graph, which might cause the shortest path tree (or I guess just shortest path info in general) to update

narrow mica
#

Wait I think I get what you mean
I don't think OP said something about it though

haughty mountain
#

I'm trying to see the x behind the y 😅

#

if this is the case the real problem seems more like a dynamic shortest path problem

#

as I add edges, track the shortest paths

narrow mica
#

Well this is the original quote

I am intending to run a backtracking algorithm for a game and store the states in a data struct, where each element stores the current state of the game, how many steps it took to get to this state from the starting position and the best predecessor state

Now, since the backtracking algorithm will repeatedly come across already seen states, I need to be able to update the struct if the predecessor state has improved (in specific: if it took less steps to get to the same state, update the predecessor)

haughty mountain
#

but if the thing I think I see is actually what's going on and this is really a dynamic shortest path problem in disguise, then there are things like
https://en.wikipedia.org/wiki/D*

D*

D* (pronounced "D star") is any one of the following three related incremental search algorithms:

The original D*, by Anthony Stentz, is an informed incremental search algorithm.
Focused D* is an informed incremental heuristic search algorithm by Anthony Stentz that combines ideas of A* and the original D*. Focused D* resulted from a further de...

fiery cosmos
#

which bot is used for running code in this server

#

eg the one we invoke with !e

solemn moss
#

@halcyon plank

#

You could see it by just running something :p

haughty mountain
#

!source

halcyon plankBOT
honest remnant
#

guys help, I am sort of new to python, I am wondering how I can sort a list of dictionaries by a value of the dictionaries??
please help!!!

brazen python
haughty mountain
#

or look at any docs for the sorting functions that will tell you that you can specify a key to sort by

stray fractal
#

is there a better way to get the length of the fractional part of a fractions.Fraction() than this ```py
def ndec_places(x):
assert isinstance(x, Fraction)
y = x
j = 0
seen = set()
while y := y % 1:
if y in seen:
# cycled; infinite places
return math.inf
seen.add(y)
j += 1
y *= 10
return j

jolly mortar
#

check the prime factorizations of numerator and denominator

#

if any factor other than 2 or 5 is leftover then its inf

stray fractal
#

yeah but i also need to get the length

#

it seems more efficient to just add to a set and check for that while getting the length

keen hearth
#

But your approach seems alright I guess ¯_(ツ)_/¯

keen hearth
# 
def decimal_places(fraction):
    twos = prime_exp(fraction.denominator, 2)
    fives = prime_exp(fraction.denominator, 5)
    if 2**twos * 5**fives == fraction.denominator:
        return max(twos, fives)
    else:
        return math.inf

def prime_exp(number, prime):
    exp = 0
    while number % prime == 0:
        exp += 1
        number //= prime
    return exp
jolly mortar
keen hearth
#

Not sure about that actually.

jolly mortar
#

oh it does

stray fractal
#

there should be a better way to do the twos loop right

keen hearth
stray fractal
#

hmm

#

yeah maybe

keen hearth
#

Oh yeah there is a trick to calculate the zeros at the end of a binary number right.

stray fractal
#

yeah the one-liner wins

stray fractal
keen hearth
#

Small world lol

maiden whale
#

Hi guys !!
I need a little help in or-tools.
I am using this code but not sure how to allow multiple depots or different start and end location for each vechicle?

https://hastebin.com/share/gacozokeke.python

Hastebin

Hastebin is a free web-based pastebin service for storing and sharing text and code snippets with anyone. Get started now.

somber mango
#

hi guys

#

really quick q

#

i have a string '20220101'

#

is it possible to use datetime module to convert it into a datetime object "year-month-day"

#

?

vocal gorge
#

sure, use strptime with the right format specifier

maiden whale
#

date_object = datetime.strptime(date_string, '%Y%m%d')

#

Use chatgpt for this bro

somber mango
#

right,thanks guys

maiden whale
#

Now answer my question 😄

topaz otter
# 
def solution(number):
    arr = []

    if number == -1:
        return
    
    for num in range(1, number):
        if num % 3 and num % 5 == 0:
            print(f'{num}: 3 and 5')
            #arr.append(num)
        if num % 3 == 0:
            print(f'{num}: 3')
            #arr.append(num)
        if num % 5 == 0:
            print(f'{num}: 5')
            #arr.append(num)

    return arr

print(solution(10))
#

why does the first line get executed here? I know swapping the other 2 ifs to elifs gives the results I'm looking for. Just wondering why does the first if statement execute for the number 5?

#

oh wait nvm I think i see

#

lol oops

#

I'm not checking the first one to anything

storm yoke
#

Hello i have the following code about data with density in the earths core.
def premfunc(r):
R = 6371
x = r/R
if 0<=r<=1221.5: #inner core
rho_x = 13.0885-8.8381 x**2
elif 1221.5<r<=3480: #outer core
rho_x = 12.5815 - 1.2638x - 3.6426x**2 - 5.5281 x3
elif 3480<r<=5701: # Lower mantle
rho_x = 7.9565 - 6.4761x + 5.5283x2 - 3.0807x**3
elif 5701<r<=5771: # transition zone 1
rho_x= 5.3197 - 1.4836x
elif 5771<r<=5971: #transition zone 2
rho_x= 11.2494 - 8.0298* x
elif 5971<r<=6151: #transition zone 3
rho_x= 7.1089 - 3.8045x
elif 6151<r<=6291: #Low velocity zone
rho_x= 2.6910 + 0.6924x
elif 6291<r<=6346.6: #LID
rho_x= 2.6910 + 0.6924*x
elif 6346.6<r<=6356: #Lower Crust
rho_x=2.9
elif 6356<r<=6368: #Upper Crust
rho_x=2.6
elif 6368<r<=6371: #Ocean
rho_x=1.020
else:
rho_x = 0
rho_x = rho_x *1000
return rho_x

In this code r= the radius of the earth and R=the maximum radius or the radius of the earth with x being the density.
Now the exercise is to have the average density of each zone in the earths crust/mantle etc with numpy, i used np.average to get the average density of the whole earth. So the question is: How do i make a code for calculating the average density of each zone?

Thank you

# 
    R = 6371
    x = r/R
    if 0<=r<=1221.5: #inner core
        rho_x = 13.0885-8.8381 *x**2
    elif 1221.5<r<=3480: #outer core
        rho_x = 12.5815 - 1.2638*x - 3.6426*x**2 - 5.5281* x**3
    elif 3480<r<=5701: # Lower mantle
        rho_x = 7.9565 - 6.4761*x + 5.5283*x**2 - 3.0807*x**3
    elif 5701<r<=5771: # transition zone 1
        rho_x= 5.3197 - 1.4836*x
    elif 5771<r<=5971: #transition zone 2
        rho_x= 11.2494 - 8.0298* x
    elif 5971<r<=6151: #transition zone 3
        rho_x= 7.1089 - 3.8045*x
    elif 6151<r<=6291: #Low velocity zone
        rho_x= 2.6910 + 0.6924*x
    elif 6291<r<=6346.6: #LID
        rho_x= 2.6910 + 0.6924*x
    elif 6346.6<r<=6356: #Lower Crust
        rho_x=2.9
    elif 6356<r<=6368: #Upper Crust
        rho_x=2.6
    elif 6368<r<=6371: #Ocean
        rho_x=1.020
    else:
        rho_x = 0
    rho_x = rho_x *1000
    return rho_x
languid moss
#

jesus fucking christ 💀

dawn cliff
dawn cliff
native cliff
#

am not getting how to improve performance of my codes

def climbingLeaderboard(ranked, player):
    # Write your code here
    returnrank = []
    highestscore = 0

    for p in player:
        prank = 1
        for i in range(len(ranked)):
            cscore = ranked[i]
            if ranked[i-1] == cscore:
                continue
            if cscore > p:
                prank += 1
        returnrank.append(prank)
        
    return returnrank

in this one i have to implement 'dense ranking'

image.png
narrow mica
native cliff
narrow mica
keen hearth
#

Or are the parameters of the problem such that ranked is much larger than player, and you have to find a solution that's less than O(n) with respect to the length of ranked?

floral heart
#

Does anyone have any idea ab camera model and projection matrices ?

karmic locust
#

Hey guys I need some help

Is there anyway to take linux system calls and turn them into stack traces

olive badge
#

i cannot understand this solution

#

You are given an array a of n integers. Count the number of pairs of indices (i,j) such that i<j and a_j−a_i=j−i.

#

basically the idea in an array is check if
nums[i] - nums[j] == i - j

#

obviously something like

n = 6
arr = [3 5 1 4 6 6]
total = 0
for i in range(len(arr)):
    for j in range(i + 1, len(arr)):
         if arr[i] - arr[j] == i - j:total += 1

basically that would be the easiest way

#

but the problem is you need to check larger inputs

#

so the real solution is

# 
nums = [3, 5, 1, 4, 6, 6]
hashmap = {}

for i in range(len(nums)):
    diff = nums[i] - i
    if diff in hashmap:
        hashmap[diff] += 1
    else:
        hashmap[diff] = 1

print(sum([n * (n-1) // 2 for n in hashmap.values()]))
#

i was researching a bit so i found
n * (n-1) // 2 is for count the number of unordered pairs of different values

for example
{a,b,c} = {a, b}, {a, c}, {b, c}

#

but i dont understand why would you store the diff

#

and how are you getting the solution by doing this

#

this is a simple code i dont know how i cannot understand it

narrow mica
# olive badge and how are you getting the solution by doing this

Rearrange your original equation

a_j - a_i = j - i
a_j - j = a_i - i # <-- on each side is the difference between some index k and the value a_k
```So you can instead count how many indices `k` satisfies `a_k - k = d` for some arbitrary `d`. 
Say there are `5` indices, `u, v, w, x, y`, satisfying `a_k - k = 1`. Choosing any 2 of the 5 indices from here will give you a pair of indices that satisfies the original equation. Thus, these 5 numbers will add to the answer the number of ways you can uniquely choose 2 items from a set of 5.
narrow mica
olive badge
#

thanks buddy I will analyze it

native cliff
native cliff
oblique oak
#

is this doubly linked list method correct?

code.png
jovial gazelle
#

https://leetcode.com/problems/domino-and-tromino-tiling/description

Can someone plz hold my hand and tell me it's okay to think that this sentence is totally meaningless

Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.

LeetCode
Domino and Tromino Tiling - LeetCode

Can you solve this real interview question? Domino and Tromino Tiling - You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes.

[https://assets.leetcode.com/uploads/2021/07/15/lc-domino.jpg]

Given an integer n, return the number of ways to tile an 2 x n board. Since the answer may be very large, retu...

#

What does 4-dirextionally adjacent mean in a 2xn board ?

#

Is cell=square ?

austere folio
#

Hi, anyone would know how to translate "sketch data structure" in French or any other latin language? I fail to find translations for this?

jovial gazelle
jovial gazelle
austere folio
deep jetty
#

Hey, so I have a weighted graph of connections. I'm using a dijkstra algorithm to find the shortest path between 2 nodes.
But what if I don't know the weight of some connections?
Let's say that the shortest path (weight-wise) between A and B would be A->C->D->B but in terms of jumps it would be A->C (we dont know the weight of A-C connection). So my program should return A->C in this case

#

and then if in any time we would discover the weight of A-C it would update it's path

#

how can i make dijkstra work like this?

cedar zenith
#

guys

#

i'm a senior year highschool graduate

#

bout to take a degree in cs

#

i've got like a 4 months time for that

#

so

#

should i

#

start studying

#

data structures and algorithms

#

rn

stoic belfry
#

Hi All, is there any book of O’reilly on algorithms and data structures (written in python)? Please let me know

mystic grail
cedar totem
keen beacon
#

Hello everyone (and happy new year!). I have completed a couple python courses online, and i am now trying to practice on Codewars and Leetcode. However i am kinda reaching a plateau (especially on Leetcode) because of new data structures and/or algorithms i don't know at all (e.g. binary search, two pointers, linked lists, trees etc).

My request is kinda simple: can you please recommend some (free, if possible) resources that cover these? I did find so many online/on youtube, but they weren't great/comprehensive enough.

Thanks !

cedar zenith
lilac cradle
#

what do you guys think of this bresenham circle implementation? to be honest i dont remember the specifics of why the algorithm works, i just found it in my old code and spruced it up

def bresenham_circle(pos,radius):
    x2,y2 = pos
    switch = 3-(2*radius)
    x,y = 0,int(radius)
    while x <= y:
        yield from [
            (x+x2,-y+y2),
            (y+x2,-x+y2),
            (y+x2,x+y2),
            (x+x2,y+y2),
            (-x+x2,y+y2),        
            (-y+x2,x+y2),
            (-y+x2,-x+y2),
            (-x+x2,-y+y2)
        ]
        if switch < 0:
            switch = switch+(4*x)+6
        else:
            switch = switch+(4*(x-y))+10
            y-=1
        x+=1
#

before i was adding all the points to a set but i think using a generator expression works better

#

unless it'd be faster to do individual yield statements, idk

haughty mountain
lilac cradle
#

kk