algos-and-data-structs

[regal spoke]

I just copy paste from there, ye

[stiff quartz]

smart

[regal spoke]

https://codeforces.com/submissions/conqueror_of_tourist There is this guy

He is a crazy smart Python coder that sometimes switches to using c++, but most of the time uses Python

I usually supply him with Python implementations of data structures and stuff like that

[stiff quartz]

do all the "high elo" people of codeforces know each other

well not all but like

do you see each other around all the time

like a small circle kinda thing

[regal spoke]

There are a number of discord servers.

[stiff quartz]

Oh fairs, I usually just ask here (well rarely since i'm new to all this), didn't know there were dedicated ones

[regal spoke]

I'm mostly in the AC discord server

[stiff quartz]

i tried the two pointers approach with increasing sort instead of decreasing because i had an intuition it'd work but i'm banging my head about why it doesn't work on some test cases that i can't even access because they're not the simple ones. i evn wrote some myself but i'm correct on it argh

That kinda looks lik it'd work right?
merged_sorted_portals is a list of 4 integers (l, r, a, b), with the merging process i had done before but the mistak doesn't come from the merging process since it go time limit execution before on like test case 7

# sort portals by start point
merged_sorted_portals: list[list[int]] = sorted(stack_portals, key=lambda i: i[0])

# two-pointers approach to feed memoisation
memoisation: dict[int, int] = {}
left_pointer: int = 0
while left_pointer < len(merged_sorted_portals):
    right_pointer = left_pointer + 1
    while right_pointer < len(merged_sorted_portals):
        # can we get to the next portal
        if merged_sorted_portals[right_pointer-1][3] >= merged_sorted_portals[right_pointer][0]:
            right_pointer += 1
        else:
            break
    max_temp = 0
    for left_pointer_temp in range(left_pointer, right_pointer):
        max_temp = max(max_temp, merged_sorted_portals[left_pointer_temp][3])
    for left_pointer_temp in range(left_pointer, right_pointer):
        memoisation[merged_sorted_portals[left_pointer_temp][3]] = max_temp
    left_pointer = right_pointer

[regal spoke]

Oh sorting by i[0]?

I sort by i[3]

[stiff quartz]

Yep I changed around in the meantime

[stiff quartz]

I saw, but I wanted to investigate whther sorting by i[0] would work

and I kinda think it would

and it's O(n)

[regal spoke]

The fundamental reason why sorting by b works is that you know that the portal with maximum b cannot improve

[stiff quartz]

yeh i agree

[regal spoke]

Your code is as much O(n) as my code is. The sorting is still O(n log n).

[stiff quartz]

(oh yes mb)

I actually realize this would ve been very useful to simplify the last part of my code

but the error doesn't come from the fact that i didn't use that

oh no i think i understand (no actually that should never happen)

merged_sorted_portals[right_pointer-1][3] >= merged_sorted_portals[right_pointer][0]

this might be true but i'm also bigger than merged_sorted_portals[right_pointer][1]
in some instances

[regal spoke]

Speaking about the competitive discord servers. The original one was Competitive programming server by laggy. It was really big, but over the years it has kinda died out. The main problem with it is that it was filled with beginners asking very beginner questions.

To make a better server, a group of people created an invite only server called the AC discord server. The unwritten rule at the time was that you needed to be rated 1900 or above to join. I joined it roughly a year after its creation. Today it isnt invite only, instead we have a bot that checks your codeforces rating and only lets you join only if your rating is 1900 or above.

[stiff quartz]

oh shit i only participated in two contests and i'm 731 😆

[regal spoke]

Then some years later more people started to make their own competitive discord server. I think the biggest one out of those are errichto's server.

[regal spoke]

Actually that is just a fake rating to make beginners think that they are improving their rating

The internal rating of everyone starting is 1500, but you only see your true rating after like 5 contests.

[stiff quartz]

oh ok that's fair

i guess i'll get to see my real rating in a few weeks then

[regal spoke]

ye

[stiff quartz]

probably gonna stop trying to do div 2 i've been banging my head on this problem for too long

but it's pretty fun

been coding for a long time not even knowing what data structures were

ohhhhhhhhhhhhhhh i found my mistake

great

damn

TLE on test 8 now

💀

ok i just read your solution

so much easier damn

[summer fossil]

@stiff quartz @regal spoke u guys used python for competitive programing

[stiff quartz]

i mean yeh sure

could probably be easier in cpp but my ambition isn't really to be #1 on codeforces so i guess sticking to python is fine

[regal spoke]

yes

[stiff quartz]

https://codeforces.com/blog/entry/76507

unironically was just googling random stuff and found out that

[regal spoke]

There is one bad thing about my solution and that is that I'm using hashmaps. I could fairly easily hack my own submission

[stiff quartz]

didn't know such a legend was helping me

[stiff quartz]

mmh, what is the weakness of hashmaps here?

[summer fossil]

Legend!

[regal spoke]

Funny story about that is that the round got unrated afterwards. So when I woke up the next day after the competition my rating was gone.

[summer fossil]

Just spit some knowledge towards me

[regal spoke]

For Python there are two types of hacks. One case is abusing that the hash of integers is taken mod 2^61 - 1

!e

{i * (2**61 - 1) for i in range(10**5)}

[halcyon plank]

@regal spoke :warning: Your 3.11 eval job timed out or ran out of memory.

[No output]

[stiff quartz]

lmao

[regal spoke]

This wont work on codeforces since codeforces usually bounds the input to 10^9 or 10^18

[stiff quartz]

but if two integers have the same hash

it's "resolved" in the hash bucket right?

like we traverse the hash bucket to look for the right key?

[regal spoke]

Python hashmaps don't use buckets. Instead it tries to psudo randomly traverse to the next empty spot in a power of two sized array

[summer fossil]

u r also 7star coder on codechef

[stiff quartz]

Oh, I've beeen lied to

[regal spoke]

I think so, but I havent been on codechef in ages

Used to do the codechefs longs, and you got crazy amount of rating from that

[stiff quartz]

I thought it was an array of linked lists

[regal spoke]

Think of it as a power of 2 sized array where at least half of the spots are empty

When you try to place a new number x in the hashmap, then it tries to take spot x % size. If that spot is already occupied then it psudo randomly walks to some other index and checks if that is occupied. If that spot is occupied then it walks again, and again and again

The way to "attack" a hashmap is to fill in all the spots that x wants to use.

[stiff quartz]

oh because the hash of integers is taken mod 2^61 - 1, you don't know which of the spot is the right one?

[regal spoke]

For small integers the 2^61 - 1 thing wont matter

The hashes of integers >= 2^61 - 1 are modded by 2^61 - 1. So you can get tons of big integers with the same hash easily

That was the first type of attack I was talking about

[stiff quartz]

And if you "fill" all the spots that were supposed to be occupied

doesn't the dictionary just increase its size?

[regal spoke]

It doesn't have any fallback to increasing its size

It just runs super slowly if you fill in the spots of the random walk

!e

def dict_ddos(n):
    pow2 = 1
    while pow2 < 2 * n: pow2 *= 2

    # Fill up all spots that 0 wants to use
    A = [pow2]
    i = 1
    for _ in range(n // 2):
        A.append(i)
        i = (i * 5 + 1) % pow2

    # Spam 0s
    A += [0] * (n - len(A))
    return A

B = {}
for a in dict_ddos(10**5):
    B[a] = 1

[halcyon plank]

@regal spoke :warning: Your 3.11 eval job timed out or ran out of memory.

[No output]

[stiff quartz]

because you have to traverse all the places of the random walk?

to find your key/value pair?

[regal spoke]

Here the first half of A fills in the spots that 0 will travese in the psudo random walk

Then I try to put 0 into the hashmap 10^5 times. Each time it will have to do a 10^5 long walk to check if 0 is already in the hashmap or not

I could relatively easily make something like this that hacks my codeforces solution

[stiff quartz]

So it's sort of similar to finding 10^5 numbers that would end up in the same hash bucket? (for another language)

[regal spoke]

I would say it is different.

[regal spoke]

Hacking hashmaps in C++ definitely is of that kind. You come up with tons of integers that want to be placed in the same bucket.

https://codeforces.com/blog/entry/62393

[stiff quartz]

and here i thought hacking a solution meant you read the code of the person if you think they forgot an edge case

[regal spoke]

Hacking on codeforces can be anything that makes the program TLE or MLE or RTE

Hashhacks are kinda common

[stiff quartz]

That’s fair

Can you not just put thousands of lines of comments to obfuscate your code?

So that they don’t even know you use a hashmap?

[regal spoke]

Obfucation is against the rules of codeforces

[stiff quartz]

Ah

[regal spoke]

But you definitely can add some random crap to make your hashmaps effectively unhackable

C++ hashmaps can take in a custom hash function. So you can use that to protect yourself (that is what neal proposes to do in his blog)

Python hashmaps cannot be fixed as easily

After asking the PyPy developers about this issue, I was told to only use strings as keys in hashmaps, because those have been designed to not be hackable.

[stiff quartz]

So you could just convert your keys to strings of the integer there was right?

[regal spoke]

yes

[stiff quartz]

Interesting tho

Way above my head but interesting

[regal spoke]

Speaking about funny stories of hacks

Sorting integers in java used to be hackable. And it is still hackable on many websites since website are usually slow at updating their versions.

[static tapir]

hey guys just wanted to know if function are stored in heap memory or not?

[regal spoke]

Java used a kind of quicksort that could be easily abused to run in O(n^2).

Only in relatively recent versions did Java fix their sorting algorithm, I think they made it fall back to some O(n log n) algorithm if the quicksort runs too slow.

https://codeforces.com/blog/entry/102175

Going back to Python hashmaps. Another kinda bad thing about its design is that it can easily run in O(log n) even if the input data wasnt designed to be mallicious.

!e

n = 10**5
A = {}
for i in range(n):
  A[i] = 1

for _ in range(n):
  A[1 << 20] = 1

This for example runs in O(n log n) time ^

[halcyon plank]

@regal spoke :warning: Your 3.11 eval job has completed with return code 0.

[No output]

[regal spoke]

It isn't as crazy slow as the other hacks, but I think it should still be seen as a flaw with Pythons dictionary design

[stiff quartz]

i'm not sure i get why this runs in O(nlogn)?

[regal spoke]

The random walk essentially walks by multiplying by 5 (there is a little bit more to it, but it is mostly multiplying by 5)

1 << 20 wants the 0 spot, and when it cant get it, it walks by next_spot = (small number) + 5 * prev_spot

I've filled up all the spots between 0 to n

So it will have to multiply by 5 until it gets >= n to find an empty spot

[stiff quartz]

ohh

[regal spoke]

So each A[1 << 20] = 1 call will require log_5(n) steps

[stiff quartz]

wait why not 1 << 61

[regal spoke]

For big integers it mods them down by 2**61 - 1

but

For the walk in the power of 2 sized array, it mods by the size of the array

So the psudo random walk formula looks like this
next_spot = ((small number depending on intial value and number of steps taken) + 5 * prev_spot) % size

[stiff quartz]

oh

[regal spoke]

1 << 20 is big enough of a power of 2 that it is 0 mod size

1 << 60 would have worked too

But not 1 << 10

I guess 1 << 61 would have worked too, but for a different reason

It is a big integer (since it is larger than 2^61 - 1). So its hash will be modded by 2^61 - 1, making it 1

[stiff quartz]

yeh that'sw hat i was referring to

[stiff quartz]

here the size of the array is 2n right?

around that

so we just gotta make sure we have a number bigger than 2n?

[regal spoke]

I think it is the smallest power of 2 that is >= 2 n. Or something like that

[stiff quartz]

yeh fair

[regal spoke]

If we want numbers to overlap, yes

[stiff quartz]

the difference is kinda hard to see ngl

MemoryError on 10**10

A[1<<20] = 1 should be O(log(n)) right?

yeah

log_5(n)

[regal spoke]

ye it isn't a big deal

Unlike the O(n^2) hacks

[stiff quartz]

the java ones?

yeh i guess

[regal spoke]

No I meant the Python hashtable hacks

[stiff quartz]

oh with putting the numbers at all the places

it shoudl be walking

[regal spoke]

Yes

Also the first type of attack of sending multiples of 2^61 - 1

[stiff quartz]

This:

def create_dict(n) -> dict[int, int]:
    A = {}
    for i in range(n):
        A[1 + i * (2**61-1)] = 1
    return A

rip i'm doing something wrong

it's not the same hashes

id is the same as hash right in python?

actually maybe not

yeh mb

it was hash() not id()

[regal spoke]

CPython id I think is a pointer to where the integer is stored in memory

It is not the hash

[stiff quartz]

dang

super small dictionaries and you can see already

[regal spoke]

Just a warning. You could be seeing slowdowns just from using big integers

[stiff quartz]

yeh that's why i'm gonna compare with something similar but not spaced by 2**61-1

[regal spoke]

I would compare using i * (2**61 - 1) and i * 2**61

[stiff quartz]

smart

[regal spoke]

The first one will have hash 0, the second will have hash i, so all the hashes of i * 2**61 will be different

[stiff quartz]

something like that right?

damn the difference is huge

crystal clear

even for a dictionary of size two it literally takes almost twice as long

well i guess it's clearly linear time

which makes snse

you gotta do the whole walk

[regal spoke]

The amount of slow down is pretty high per bit of memory used.

[stiff quartz]

yeh those are dictionnaires of size 2 to 10

it's beautiful

i like it

[regal spoke]

Speaking about that. Back when Python added the 4300 limit for int to string, and string to int conversion, part of the argument was that you could make a yaml file that was super slow to load.

Turns out that per byte, it is significantly slower to load a hacked hashmap.

[stiff quartz]

You lost me there

[regal spoke]

Do you know about the 4300 limit?

[stiff quartz]

4300 limit?

oh you can't convert a large int?

to a string

wait what

str(4301) doesn't work?

[regal spoke]

!e

int('1' * 4301)

[halcyon plank]

@regal spoke :x: Your 3.11 eval job has completed with return code 1.

001 | Traceback (most recent call last):
002 |   File "/home/main.py", line 1, in <module>
003 |     int('1' * 4301)
004 | ValueError: Exceeds the limit (4300 digits) for integer string conversion: value has 4301 digits; use sys.set_int_max_str_digits() to increase the limit

[stiff quartz]

!e

print(str(4301))

oh ok

[halcyon plank]

@stiff quartz :white_check_mark: Your 3.11 eval job has completed with return code 0.

4301

[stiff quartz]

how the hell do you know every subtlety of Python

[regal spoke]

This limit is something that I'm personally very opposed to.

Maybe I'm just one of the few people using big integers in Python.

[stiff quartz]

Yeh I was gonna say, apart from competitive programming, i'm not sure people use numbers bigger than 10**4301

[regal spoke]

Math people could definitely use it.

[stiff quartz]

Well they wouldn't convert it from a string

They would straight up use the appropriate data type right?

[regal spoke]

I dont know what appropriate data type means to you

[stiff quartz]

I think Decimal

which allows you to integers with loads of bytes

[regal spoke]

Decimal is a fair bit of hassle to use

[stiff quartz]

I was using this i remember for some probability simulations

[regal spoke]

Ye that is the kind of think that I meant

[stiff quartz]

Although that was for precision after the decimal point

[regal spoke]

One more problem I have with decimal is that PyPy doesn't have an efficient decimal implementation. As someone that codes a lot for PyPy this is a pretty big issue

It is arguably more of an issue with PyPy than decimal, but it is still a drawback of using decimal

[regal spoke]

Speaking about Decimal, I recently looked into how efficient it is at multiplying big integers.

It is about 3 - 4 times slower than fast C++ implementations I could find for multiplying big integers

And it is about twice as fast as the fastest I'm able to mimic with pure Python code (no imports)

[stiff quartz]

In C++, how does it work if you want to multiply big integers

you have int

long

long long

but if you want "more"

what do you do?

[regal spoke]

You make a vector of them 😄

The hard thing is figuring out how to multiply vectors of digits.

[stiff quartz]

oh

can you not like have long long long?

😆

[regal spoke]

There is no long long long long long long

[stiff quartz]

damn that's a shame

[haughty mountain]

there are a few bigger types, but they are generally somewhat slow since they usually don't map to any existing integer sizes in hardware

[vocal gorge]

well, if you're not doing CP, you can use a bigint library like gmp.

maybe there's a C++-specific one; gmp is C
EDIT: ah, gmp has a c++ interface.

[regal spoke]

Ye gmp is definitely what you should use if you actually care about performance

[haughty mountain]

and I'm not sure if they are even standard, probably not

[stiff quartz]

Yeah i was asking for other stuff than CP

so it actually might be useful

[haughty mountain]

gmp is quite good, modulo potential license issues

[stiff quartz]

oh it's just for research so i'm sure it's fine

although i need to find out how to install a package in c++, my c++ experience is limited to doing easy leetcode problems 💀

[haughty mountain]

gmp is GPL licensed which might in some cases affect how you can licence your code, probably a good thing to be aware of

though it probably won't matter much for your usage of it

[stiff quartz]

good to know still i guess

gmp is for large floats too right? (looks like it https://gmplib.org/manual/C_002b_002b-Interface-Floats)

[haughty mountain]

iirc it being GPL is one reason python does not want to use it

[regal spoke]

Btw here is the big integer Python multiplication implementation algorithm that I was talking about https://paste.pythondiscord.com/RMVQ (It is my own implementation for benchmarking, so dont expect the commenting in the code to be great)
It is based on a paper that GMP authors released in 2007 of how to do fast big integer multiplication

It multiplies two huge integers without using the built in multiplication

It is pretty cool that you can make something this fast just in pure Python. The reason it is fast is because it uses built in big integer addition, subtraction, bitand, and bitshift.

But unfortunately it is about half as fast as decimal, and about 8 times slower than effiecent C++ implementations

[stiff quartz]

damn

[regal spoke]

It has the same speed as the built in multiplications when mutliplying integers with about 10^5 bits

At 1e6 bits it should be about 4 times faster than the built in multiplication.
At 1e7 bits it should be about 15 times faster than the built in multiplication.

At 1e8 bits it should be about 55 times faster than the built in multiplication.

[regal spoke]

Btw that int 4300 limit still have some weird quirks. You can get the 4300 error message even if the string isn't a valid integer.

!e

int('x' + 4301 * '1')

[halcyon plank]

@regal spoke :x: Your 3.11 eval job has completed with return code 1.

001 | Traceback (most recent call last):
002 |   File "/home/main.py", line 1, in <module>
003 |     int('x' + 4301 * '1')
004 | ValueError: invalid literal for int() with base 10: 'x111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

[regal spoke]

!e

int(4301 * '1' + 'x')

[halcyon plank]

@regal spoke :x: Your 3.11 eval job has completed with return code 1.

001 | Traceback (most recent call last):
002 |   File "/home/main.py", line 1, in <module>
003 |     int(4301 * '1' + 'x')
004 | ValueError: Exceeds the limit (4300 digits) for integer string conversion: value has 4301 digits; use sys.set_int_max_str_digits() to increase the limit

[regal spoke]

Leading 0s are counted as digits
!e

int(4301 * '0')

[halcyon plank]

@regal spoke :x: Your 3.11 eval job has completed with return code 1.

001 | Traceback (most recent call last):
002 |   File "/home/main.py", line 1, in <module>
003 |     int(4301 * '0')
004 | ValueError: Exceeds the limit (4300 digits) for integer string conversion: value has 4301 digits; use sys.set_int_max_str_digits() to increase the limit

[paper lotus]

Anyone here want to flex on me by opimizing my code that takes 10 minutes to run

[stiff quartz]

Damn

Well I guess you can increase the limit though with sys.set etc … so it should be fine?

[regal spoke]

Ye but that is also has its drawbacks. It is a bit of a pain to do. Different versions of Python will get RTE with it or without it.

The digit limit was backported, so even if you know the Python version you still dont know if you should have the limit in the code or not

[stiff quartz]

What is RTE sry?

[regal spoke]

Run time error

[stiff quartz]

Oh yeh ok

[regal spoke]

Here is another weird quirk with the limit

!e

import sys
sys.set_int_max_str_digits(1)

[halcyon plank]

@regal spoke :x: Your 3.11 eval job has completed with return code 1.

001 | Traceback (most recent call last):
002 |   File "/home/main.py", line 2, in <module>
003 |     sys.set_int_max_str_digits(1)
004 | ValueError: maxdigits must be 0 or larger than 640

[regal spoke]

This clearly says maxdigits needs to be larger than 640

but

!e

import sys
sys.set_int_max_str_digits(640)

[halcyon plank]

@regal spoke :warning: Your 3.11 eval job has completed with return code 0.

[No output]

[regal spoke]

640 is fine

[vocal gorge]

PR time 😛

[stiff quartz]

Well I mean they didnot say strictly larger than right?

😅

Although I’m not native so maybe ‘greater than’ implies ‘strictly greater than’?

[regal spoke]

nah I think this is just wrong

I've discussed things like this with people in the past

Appearently in french mathematics, it is common to view 0 as being both positive and negative

and for example a constant function as being both increasing and decreasing at the same time

Maybe in that kind of scenario larger than 640 could mean >= 640

[stiff quartz]

Well I’m French and yeah

[stiff quartz]

And in French we would assume >= unless explicitly stated ‘strictly’

But then idk

What the consensus is in English

[regal spoke]

Think almost everyone mean > when they say larger

[stiff quartz]

Yeh that’s down to conventions I guess they should’ve explicitly said larger or equal to 640

Now that I think about it

I either say "larger or equal than" or "strictly larger" in French, never do I really just say "larger than"

[regal spoke]

I think that is best solution if you dont want to be missunderstood

[shadow glen]

how do i make the bot await for a response by chat?

i'm planning to do it like when you blacklist a swearing and stuff

like when you blacklist the n word, the r word and any slur word

[regal spoke]

That sounds like a perfect question to ask in something like #async-and-concurrency or #discord-bots

[shadow glen]

yep, sorry wrong chat

i also need a way to unify two list of dicts while eliminate redundances

[fiery cosmos]

How would you say it in French that would give that impression?

[stiff quartz]

It sounds the same as greater than

Just down to conventions I guess

[regal spoke]

I would say that the biggest offender for misunderstanding in math is "A subset of B"

You'd think that this notation means that A is a strict subset of B ^

And that this means A is equal or a subset of B ^

But it is super common for both of these notations to mean the exact same thing. Both are read as "A subset of B".

[lean walrus]

In this case nonstrict case is implied, unless it is said explicitly that A is strict subset of B

Tbh, I've never seen the second symbol

[regal spoke]

How would you denote strict subsets?

[lean walrus]

With words 😄

[regal spoke]

I'm used to seeing this symbol

[lean walrus]

Lmao

Extremely weird

But i get the point

[naive oak]

it varies depending on the author

whether or not the first symbol denotes a subset or a proper subset

[lean walrus]

A possibility:
A c B; A ≠ B

[regal spoke]

Oh but that would be horrible for expressing things like

[lean walrus]

A c B c C c D
A ≠ B ≠ C ≠ D

Write one on top of another

Well, if we combine c and ≠ we would get your symbol

😄

[outer rain]

A ≠ B ≠ C ≠ D this is so cursed

neq is not transitive

(well, I suppose it is with the context above)

still cursed af

[crisp turtle]

What do you do when you are just... lost on a solo project?
I have no idea how and where to proceed.
I am building a gomoku AI based on a paper, which describes how to limit the search space if you look for specific patterns, but now that i implemented finding these, i have no idea what to do now.
How does my bot start the game? there obviously will be no patterns in the early (<6-7 turns)
how do i build an actual search three out of the current board state?

[modern gulch]

I dunno, maybe give us some details on the first problem you're blocked by? Sounds interesting. @crisp turtle

To your question: when stuck on anything, I take a break and think about it away from computer, maybe talk to something, or even just try to write it down or rubber duckie it

[crisp turtle]

this is a short summary generated by chatgpt, the actual page is a bit longer

Objective: TSS aims to identify sequences of moves that lead to a winning position, known as "threats." It focuses on finding and evaluating these threats to guide the game-playing strategy.

Threat Definition: A threat is typically defined as a specific pattern or sequence of moves that, if unopposed, will lead to a winning position for one player.

Search Space: TSS operates within a defined "threat space," which includes all possible threats that can be created by a player. It searches through this space to identify existing or potential threats.

Local Move Generation: Unlike conventional search techniques that may consider all possible moves, TSS often focuses on moves related to specific threats or areas of interest on the game board.

Efficiency: TSS is often used to make the search process more efficient by focusing on the most relevant parts of the game's state space. It may be combined with other search techniques to ensure comprehensive coverage.

Application: TSS can be used as part of a game-playing bot's strategy, helping it identify and respond to threats during the game. It may also be used in conjunction with other evaluation functions and strategies, especially in the early stages of a game when threats may not yet be present.

In summary, Threat Space Search is a targeted search technique that focuses on identifying and evaluating threats within a game. It provides a way to guide a game-playing bot's strategy by concentrating on the most relevant and potentially winning sequences of moves.```

i am more concerned what do i do when there are no threats present like in the early game

[crude galleon]

so I know that when you have a for loop that looks something like this

for(int i = 1; i < n.length; i *= 2) ```

the time complexity of the action is logarithmic ( because it takes half the time to reach the break point, am I right so far ?) 

my question is does that also apply to something like: += 2 or += 10 or *= 5

or is it logarithmic only when multiplying / dividing. In which case is it always logaritmic so long as the multiplied number is larger than 1 basically ?

[haughty mountain]

that particular loop won't even terminate

[crude galleon]

because there is no body ?

[haughty mountain]

because 0*2 == 2

[crude galleon]

ah my stupidity

what about now

[haughty mountain]

basically if you ask the question "how many times do I need to multiply with this to reach the limit" it's logarithmic

[crude galleon]

and what about the += X ?

[haughty mountain]

for your initial example i goes 1, 2, ..., 2^x

at what point does 2^x >= lim?
roughly x = log2(lim)

for your example now
0, X, 2X, 3X, ..., nX

nX = lim
n = lim/X

which is linear in lim

[crude galleon]

ah I see

makes sense when you put those like that

[haughty mountain]

it's basically just counting

this could be a fun practice exercise

for (int i = 1; i < n; i += i) { ... }

[crude galleon]

this is also logaritmic right ?

1 + 1 , 2 + 2 then 4 +4 etc

[haughty mountain]

nope

or wait

lol, that was not what I meant to write, oh well

yeah that would be the same as your first example

[crude galleon]

its a nice trick for a test question tho

if I went for the "there is no multiplication cant be logaritmic"

[haughty mountain]

I wanted to go for something like this

i = 1
j = 0
while j < n:
  j += i
  i += 2

[crude galleon]

hmm I am not sure with that. i constantly increases in size and J increases in size based on i. it feels like its still linear tho

[haughty mountain]

it's not linear

[crude galleon]

like j would be 0 -> 1 -> 4 - > 9

then continue

[haughty mountain]

right, what's that pattern?

[crude galleon]

its almost like x^2. Next step would 16

so not quite

9 instead of 8

16 instead of 18

[haughty mountain]

it is x^2

3*3 = 9
4*4 = 16
...

what does that mean for when we reach the limit?

[opal oriole]

https://www.desmos.com/calculator/yuiha3ute9

[crude galleon]

i am not sure what you mean by that question, it could be me english tho. its basically a O(n^2) so it takes quadratic steps relative to the data ?

[haughty mountain]

j goes like x^2

that means we reach the limit quite a bit quicker

x^2 = n
x = sqrt(n)

it would take O(sqrt(n)) steps

[opal oriole]

See the graph I posted.

@crude galleon

[regal spoke]

That graph have nothing to do with @haughty mountain i j example

[haughty mountain]

it has to do with the original question

[crude galleon]

how does sqrt(n) compare to O(log(n)) ?

[opal oriole]

It explains why those steps are taken, it was for the previous question, but same process.

[haughty mountain]

sqrt(n) grows faster

[regal spoke]

Logarithms grow really slowly. Really really slowly.

[haughty mountain]

notably it grows slower than any polynomial

[opal oriole]

https://www.desmos.com/calculator/ho2qsbwq5t Slightly updated version, maybe this helps a bit more.

[crude galleon]

but thats why logn O is good no ? so the steps grows really slowly relative to the data

[haughty mountain]

so evennsomething likw n^0.0000001 will grow slower than log(n) eventuallly

[haughty mountain]

scaling like log(n) is usually very good yeah

[opal oriole]

Often the best you could hope for. Generally, it will be fast then in practice, and even at large scales.

[crude galleon]

on that matter I actually wanted to ask. A LinkedList has worst case O(n) for accessing an element. An array list has O(1) but to add/remove for it has O(n). A HashTable without a lot of collusion has O(1) for most operations but when there is lots of collusion it goes towards O(n) I believe, (or was it O(n^2)). Meanwhile a TreeMap has LogN for all operations.

So my point is, in real life where you make applications or whatever. why would anyone use a datastructure other than TreeMap if LogN is so prefferable to everything else

assuming the data is very large

[regal spoke]

Here is an example where TreeMap is slow:

Suppose you want to use strings. Then a TreeMap would have to compare log(n) many strings each time you do add/remove. Comparing strings can be really expensive.

A hashtable would just use the hashes of the strings. So a hashtable wouldn't have to do those expensive string comparisions

[opal oriole]

No, because you can often avoid collisions even at larger scales. Databases use to care more about using log N stuff due to the access pattern on slower disks. They still have them, but often just going for O(1) lookups now. Which data structures to use have shifted over time due to changes in hardware.

[haughty mountain]

what operations do you need to be fast? it differs from case by case

there is no magical perfect data structure, it's all about tradeoffs

[opal oriole]

That being said, there are many different use cases, and not knowing that a TreeMap is a thing can prevent you from doing the best thing.

[haughty mountain]

know your options

have lots of tools in your toolbox

[opal oriole]

I'm just going off of the usual program case, but there are so many unusual cases, and who knows where you might end up / what you are working on.

[opal oriole]

For example, what if you are working on an old database? There are many.

[crude galleon]

i guess I am just confused because just with the time complexity tables and comparing each one to each other I keep hearing that why log(n) is great, while n is okay but imagine like you have 1 million data then that means 1 million steps.

and n ^2 is just getting really bad

etc

but i might lack a more nuanced understanding of data structures

to know when to pick one over other

[haughty mountain]

if you do an expensive operation rarely and a cheap one often you might win overall

it's all very dependent on the problem you're trying to tackle

[opal oriole]

Ultimately you want to time it, but generally, if big, the better complexity you want (e.g. log n).

What is "big?" Well, you learn that by just timing things on modern hardware. To get a feel for what it can handle, at what scale.

[haughty mountain]

which is why having broad knowledge is nice

[haughty mountain]

how big is big data? is a fun question 😛

[opal oriole]

BUT it also depends on the context, for example, you might be like "wow only a few thousands of microseconds!" But in a video game that might be slow.

Which is why there are generally modules that you time in seconds, milliseconds, microseconds, and sometimes nanoseconds, you just need to realize which is which.

[haughty mountain]

video games is a fun example actually, it's a case where "consistent and mediocre" can be better than "usually fast but very occasionally slow"

[opal oriole]

(Or even longer time units for long running batch things, e.g. running a machine learning algorithm for months)

[opal oriole]

When the bubble sort ends up actually being useful in some cases...

[regal spoke]

Remember that the time complexities do not tell you the entire picture. The could be huge constant factors hidden behind those O(1) and O(log n).

[haughty mountain]

I would say merge sort for that purpose 😛

[opal oriole]

Bubble sort wins out on small enough sizes due to the memory access pattern.

The goofy "bubbling" actually is good.

[haughty mountain]

tiny sizes yeah

[crude galleon]

so do you learn when to use which data structure with experience?

[haughty mountain]

though I think insertion sort is usually preferred

[regal spoke]

To some degree, yes

[opal oriole]

Yeah, except sometimes bubble beats even that, it gets really weird.

[haughty mountain]

to a big degree even

[opal oriole]

Small sizes are all about whatever the weird crazy modern hardware likes, and it's gotten really complex.

[regal spoke]

https://hal.science/hal-02070778v2/document here is a great example of where time complexities can "lie"

Integer multiplication in time O(n log n)
In terms of time complexity this is the best known algorithm for multiplying two integers. But in practice it is completely unusuable.

[haughty mountain]

knowing what to do comes down to

1. knowing your tools
2. knowing how to analyze and break down complex problems

[opal oriole]

One thing that kind of illustrates the point is that modern CPUs are like networked multiplayer games that predict things before they actually get confirmation from the server.

Because they are so fast that the distance between them and the main memory is basically like a multiplayer game.

[haughty mountain]

it's a lovely paper

[opal oriole]

(Which is why we even have gigabyte memory caches now, when do we get rid of the RAM I wonder...)

[haughty mountain]

RAM is for the big data

[opal oriole]

Becomes the new disk, in terms of speed.

[haughty mountain]

a few terabytes or more of ram 😋

[regal spoke]

Here is a really funny story about time complexity and games. https://news.ycombinator.com/item?id=26296339

kuroguro

How I cut GTA Online loading times by 70%

Hacker News · Feb 28, 2021, 7:38 PM

[opal oriole]

Yeah, this is a good example of the more classic, why you should pay attention to your time complexities.

[haughty mountain]

a.k.a. "wtf I hate C strings now"

[opal oriole]

The "why you should use pointer + length in a struct in C."

[haughty mountain]

or move to a language with a tad saner string type

[opal oriole]

• A string type at all.

[regal spoke]

The game GTA5 was known for having horrendously long loading times for online play. Someone called t0st figured out that the game loaded slowly cause of a stupid time complexity bug.

I think he got a relatively large bug bounty for finding this.

The crazy thing was that this bug existed in one of the most sold games ever, and somehow no one else had figured this out.

[haughty mountain]

what is a string? a miserable pile of characters

[haughty mountain]

a lot of people were very surprised by the C stdlib behavior

[opal oriole]

Makes games is hard, making GTA5 is crazy, and at some point you need to ship or run out of money.

[regal spoke]

It isn't like this was found on release of the game. This was found many many years after release

And it was not found by a rockstar employe

I would say this was really embarissing for rockstar

Rockstar has made crazy amounts of money from this game

[opal oriole]

Relative to leaving O(N^2) complexity to this day in Windows explorer resulting in not having directories with too many files, it's so so. They probably don't want to touch it anymore, like how Microsoft does not want to touch Windows (except by adding more on top, making it slower and more buggy over time).

[haughty mountain]

it's hurting the users more than them, I'm not surprised they wouldn't care

new shiny features sell better than better load times

it's not great, but it's what it is

[regal spoke]

They had loading times up to 6 min and didn't bother checking what it was doing

[opal oriole]

It apparently was not long enough for people to not buy the game.

But, recent research by some companies are showing that these stalls / waits, even if tiny, affect revenue a lot (e.g. Netflix's team looking into this) (because scale).

Convincing management will take time and more of those results.

[regal spoke]

After taking a minute to load the common resources used for both story and online modes (which is near on par with high-end PCs) GTA decides to max out a single core on my machine for four minutes and do nothing else.

Disk usage? None! Network usage? There’s a bit, but it drops basically to zero after a few seconds (apart from loading the rotating info banners). GPU usage? Zero. Memory usage? Completely flat…

What, is it mining crypto or something? I smell code. Really bad code.

[wispy topaz]

if anyone here is good with graphs/markov chains(?) can you please send me a dm. Im struggling very hard to create a path through a graph where each point has a cost to it, and then taking the least costly route. If you have experience with that kind of math let me know.

[blissful kiln]

hi

[coral salmon]

Someone tell me how 2 recursive calls in a recursive function work... For example, take TOH problem...

[outer rain]

Don't ask to ask, ask here

[crude galleon]

public int doMap(Map<Integer, Integer> map, int n(4) ) {
map.put(n, n);
if(n == 2) {
return map.get(n);
}
else {
return doMap(map, n - 1);
}
}

can someone explain to me why this is O(n logn) ?

My answer was O(n) because it seemed pretty linear. Because it goes like (4, 4) (3, 3) (2, 2). So if the initial n was 100 then it would just be linear increase in operations, no ?

[outer rain]

Looks O(n) to me...

Oh

Wait

Who the hell asked you this question?

It depends on how Map is implemented

If it a hash map, it would be O(n) (expected), if it is a tree map, O(n log n).

O(n^2) if flat map, (or O(n), depends on implementation, again)

[regal spoke]

Pretty sure this is a java question

But ye depends on what Map is being used

[outer rain]

In java, Map is an interface. It is not implemented

[regal spoke]

I'm not sure how tree map is implemented, but in theory it could be that tree map runs in O(n) time if you insert sorted data into it. (Similar to how Pythons sorted runs in O(n) for already sorted data)

[outer rain]

fair point (sounds like something very implementation defined, but very possible)

[outer rain]

in java se docs it says it uses Red-Black tree and I am pretty sure it is impossible in that case

[crude galleon]

the question does not explain whick kind of map it is

[regal spoke]

Then the answer is "It depends on the implementation"

[outer rain]

no you can, nevermind, I'm dumb

[crude galleon]

I have one quick question, in an algorithm like this

public static void beast(int n) {
if (n == 0)
return;
else {
beast(n / 2);
}
if (n % 2 > 0)
System.out.print(1);
else
System.out.print(0);
}

if the base condition is false and hence the recursion continues does the method reruns immediately, or does it continue into the ?

if (n % 2 > 0)
System.out.print(1);
else
System.out.print(0);

like if N is 666 would it print 1 ?

[outer rain]

it will first go into a recursive call, then print a digit

so if you call it, and it does not immediately return on the first recursion level, the digit it will print will be the last one

[crude galleon]

alright thanks

[outer rain]

(to be clear: recursive calls can also print digits)

[crude galleon]

you mean something like method(n-1) + method(n-2) etc ?

[outer rain]

not really

I'm just saying that if you give it a number like 6 as input, it will print 0 last (because 6 % 2 = 0 - this is done at recursion level 1), before that it will print 1 (because 3 % 2 = 1), and as first char it will print 1

[crude galleon]

ah gotcha, yeah this was an exercise question not something i wrote, but thats good to know

[astral edge]

da

hallo

do you know englis

guia

[slender kettle]

https://www.janestreet.com/puzzles/sum-of-squares-index/

Tackling this, || with a star and backtracking. However the 9^25 search space is huge and I can’t prune it enough. A* finds max score of 204, the solution is 205. Does anyone have any ideas? ||

[outer rain]

I would just dump it into ILP solver and call it a day. Using A* for this is a little weird though, what is your heuristic?

[haughty mountain]

and if A* gives the wrong answer either your heuristic is not admissable, or the shortest path is not the answer

[outer rain]

I think they mean that this is the closest A* got to the answer before timing out/OOM-ing. (at least that's what I would expect)

[haughty mountain]

I found a 205 by hand 😛

some of the choices are pretty forced

[outer rain]

Ah yes, the most obvious solution was in our hands the whole time

I remember there was a funny problem on some olympiad

you needed to give an example of a table of numbers from 1 to 4 (iirc) of size up to 10x10 such that there is no four equal numbers on the corners of a rectangle. So for 3 by 3 table:

1 2 3     1 3 1
2 3 1     2 3 2
1 2 3     1 3 1

First will work, the second won't

and some guy did it by hand for the 9x9 table

[haughty mountain]

axis aligned rectangle I hope?

if so

123412341
412341231
341234121
234123411
112233442
441122332
334411222
223344112
121234344

8x8 is easy to just make up with a regular pattern, then some playing around with the next outline

[outer rain]

yes

I am wrong however, it was numbers 1 to 3, not 1 to 4

my bad

[haughty mountain]

aww

I got to 12x12

123412341234
412341231234
341234121234
234123411234
112233442143
441122332143
334411222143
223344112143
121234344321
212143433412
343412124321
434321213412

maybe there is some easy construction to get arbitrarily large

[thorny ivy]

If a function with time-complexity Theta((log2(n))^3) takes 1 second to run for n=1000, how large n can the algorithm solve in one minute?

[agile sundial]

you can't determine that based on the information given

[thorny ivy]

Well it doesnt need to be exact. why is the information insufficient?

[narrow mica]

Time complexity ignores a lot of stuff. Hypothetically the time it takes to run your algorithm could be exactly a(log2(n))^3 + b seconds, then you have two unknowns with only one equation that is a(log2(1000))^3 + b = 1.

[thorny ivy]

i dont think there are any hidden time constants

i'd say we can assume the algorithm is "nice" and doesnt behave erratically

[narrow mica]

Well, one way to make an estimate would be to first assume that the exact time it takes is a(log2(n))^3, solve for a with your measurement, and then solve for a(log2(n))^3 = 60

[thorny ivy]

Thanks, i got some enormous number, which is to be expected 😁

[narrow mica]

I wouldn't bet on its accuracy though

[slender kettle]

Well it’s really just a priority queue based on current score and index in grid

[slender kettle]

205 will take a LONG time for my solver to find, if ever.

Z3 is definitely usable here, but i was hoping some homegrown solution would work.

[outer rain]

aside from coming up with a better heuristic, I don't think you have any options

wait, you only use score, just sum of all numbers as a key in the queue?

(well, I suppose there are not many options...)

[slender kettle]

https://topaz.github.io/paste/#XQAAAQDHCAAAAAAAAAARmknGRw8TogB3OyKDyLvjFZ1EywNdI4Abcedju6XWubxBLftTPf+L+VFmVCnVPvUom8eQm4IypT1jTF9gCJEqOJ5yUTiAB+Q3YHTmCLYEm+PjPVIrrhwUsD+sra6DClvS2KnZfWCUjYUxnBUOlBkVrzXMZ9cX80PjWHpUZlAxHl1exl1tq1ERJuC5CnXzJBFTNLri9bOIQf3tJJPC7Shxe+MuL9PJklrBdBCeAbn/59fhiSfEAZTod3H1eS6Byd3DS8F96we4bKbEYlLXX/Xk5LtHKwh+7zzg1bF+cytR5C8EXxBKWbGRfs7is3dGOQg3Wb2SetJoIz2uDafEgTUt31q7BifFLYq/f+TAnruvw/pBMv5bHBwmWxgWKwiRx3XF9PzlXUGgJ129BjX+Ct382YnVMqIekOchNvsX2TrhrzmSWg0YqBcUwuNEOHPvS9MofPwcEHllb+jPyWEBtzUo7mk0IwA8IH1Yp4XeAyhlNbAJvGXEKbB4yfj7eZMCVnTIpjJmI0seSE7mV/Scf2C/lqP1YX6e8UjaEwMdXxxj/aBZI6VEzNkVx7B9vfnFxEkqAPrVnZ5XDCwg3edzc6s2w2rZkCAYrkHnaO0hBvKqe/1FUCHSYdlGF4VfTTKpvJnXpC3Xh3X8iF95FmbPPyfTydr6HcR9OzyVS467MNfz+FYIBmHtzTVaoACs6RhvG8KUyVat4r64junZu8p1Rbu15Lf9DtHb9/KaEGAI/zg/t/UbA93DjxpawGzv0xZM4XGcw4uTJPKFPSmeuFNMvTaf7UTenytDv5GV+cNpcDs3QbYsvQY3rKnf7KrvrD0/16pR98T7o7srVSKs32aUS4WfChcN2JBkD+U+t/E+CrnUQtDwEd2bc8FFgN4P4GPqhK9YPAv+8NFlYwR8SXHjNeHNtfH5dVNIyRQJxpU//x6uAvHwLu6A4VxK/v8TYvdCkTW5t4gwXSQRUrOKSvO9bOcIgXTlIFcARIQlTkNSGVNNZoKuR1Se2O6XeWIku7SYtP/OlCep/DXxjQ==

Refer to this for the code

sorry for long link, its a topaz github paste

(C++ btw)

[outer rain]

I see

well that's more like a dijkstra, not really A*

[slender kettle]

sure, i guess you could say that.

[outer rain]

you can try adding a bit of random here and there

Like you always check numbers in the descending order

[slender kettle]

im just wondering if the intention for this sort of problem was path-finding or backtracking

[slender kettle]

good point, that could help

[outer rain]

You can try shuffling it sometimes and see what will it give

[outer rain]

It usually almost always is search and backtracking

It's how most constructive problems like this are solved

Literally sat, smt, ilp, and other solvers work exactly the same way

The way they choose the path, however, is what makes some solvers better than others

[slender kettle]

might not make a huge difference with the heuristic though

it'll still converge on the similar 204 answers

quickly

[outer rain]

well, hard to say without trying, but I agree, it probably won't give you much

[slender kettle]

Attempted it just now

Wish I knew what magic ILP solvers used to choose paths

And find these solutions in sub 1 second

More likely it’s just that they’re good at reducing search space per the constraints passed to them

[outer rain]

it's not too difficult btw, the branching and bounding algorithm is not too complicated (it requires LP algorithm though, but simplex method is also pretty simple conceptually)

implementing them well is super hard though

and, even just implementing, really

I tried wiring a dual simplex once, I spend two days, and then gave up because I couldn't debug it

and it was pretty much the simplest implementation, with no heuristics :)

I write sat solvers now, those are way more comfortable to work with haha

[haughty mountain]

I think the 9 column must be all nines

9*25 = 225

bottom right corner must be zero

225 - 9 = 216

div by 2, 4, 6, 8 loses you at least 4

216 - 4 = 212

if you miss all nines the best you can do is a digit sum of 9 less

212 - 9 = 203

and we know 204 solutions exist

so the 9 column must be all nines

now 6 of your squares are already fixed, which might be helpful

[glossy lintel]

how should i store data like images that i can recreate at a later time. I have a system where it uses json but it proves to be inefficient when i try to introduce it to bytes that are for pictures, files.... And so i need a way to store these as a file that i can then encrypt(cryptography library fernet) and then give the file to someone which that someone can decrypt it and basically decrypt the entire data stored and process it]

XML might come as a good option

[outer rain]

Why not store files as files?

[glossy lintel]

i wanna give to the user 1 file im working on a feature for a bot called snapshot which effictively stores messages and other contents and encrypted so the user doesn't know whats inside them

and these snapshots can be used to replicate a channel

from name, topic to permissions to messages.....

the problem is with messages(this is also more of data management and not a discord bot question so i figured to ask here)

[glossy lintel]

(i use fernet cryptography to encrypt it and its user is assigned with a special key so no worries as the admins cannot understand that much the file contents but the bot can)

[outer rain]

I don't understand anything. You might be better off asking in other channel though (like networking or security, they deal with that more often), this one is certainly not for this kind of questions.

[glossy lintel]

oh

[shut mauve]

How would I do something like this most efficiently?

1. pass list to function.
2. Return for each index individually
3. Assign values in respective order

def SearchMultipleImages(images):
    for i in images
        #do something
        return (i)

images = ['SearchNextBase.jpg', 'Deploy_Dragon', 'Deploy_Queen']
SearchNextBase, Deploy_dragon, DeployQueen = SearchMultipleImages(images)

I don't feel like making two lists, there should be a trick here somewhere right?

[narrow mica]

Generator functions I guess?

def search_multiple_images(images):
  for i in images:
    # do something ...
    yield i
images = ['SearchNextBase.jpg', 'Deploy_Dragon', 'Deploy_Queen']
new_images = search_multiple_images(images)
SearchNextBase = next(new_images)
Deploy_dragon = next(new_images)
DeployQueen = next(new_images)

[paper lotus]

Is task scheduler the best way to run a script every 10 days

[haughty walrus]

Hello ! I'm pretty new to python and I'm trying to use request library.
Here is my code :

import requests

x = requests.get('https://api.popcat.xyz/color/ffcc99')
x = x.text

print(x["hex"])

Here is the output of the api :

I'm trying to get a value by the key, like when using a dictionnary, but i do not succeed, can somebody help me please ?

[haughty mountain]

channel topic pls

[summer fossil]

#User function Template for python3
from collections import deque
import sys
sys.setrecursionlimit(10**8)
class Solution:
    def numIslands(self,grid):
        count = 0
        vis = [[0]*len(grid[0]) for _ in range(len(grid))]
        q = deque()
        
        def bfs(row,col):
            q.append((row,col))
            vis[row][col] = 1
            
            while q:
                row,col = q.popleft()
                # if grid[row][col]=='1' and not vis[row][col]:
                #     vis[row][col]=1
                #     q.append((row,col))
                for delrow in range(-1,2):
                    for delcol in range(-1,2):
                        neb_row = row+delrow
                        neb_col = col+delcol
                        if neb_row>=0 and neb_row<len(grid) and neb_col >=0 and neb_col<len(grid[0]) and grid[neb_row][neb_col]=='1' and not vis[neb_row][neb_col]:
                            vis[neb_row][neb_col]=1
                            q.append((neb_row,neb_col))
                            
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if not vis[row][col] and grid[row][col]=='1':
                    count+=1
                    bfs(row,col)
        return count```

https://practice.geeksforgeeks.org/problems/find-the-number-of-islands/1

My solution is not working

[haughty mountain]

I don't want to log in to check, but is their input actually strings?

If I give list of strings things seem to work for basic examples

[summer fossil]

It' seems to be string '0's (Water) and '1's(Land) and in video explantion of this problem they use "1"

Lol it's work i think it's string but i check it's type and it's work Thanks!

[summer fossil]

How can i call bfs here instead of 2for loops for neb_rows what change i need to make and where in code

[fiery cosmos]

you can omit maintaining a queue and recursively invoke bfs on neighbouring cells, with base case being - out of bounds, already visited 1 cell or a 0 cell. but you will still need 2 for loops though.

also uh that'd make it dfs rather than bfs

[haughty mountain]

Yeah, bfs and recursion really don't go together neatly

[regal spoke]

Even a dfs solution would have to have these two for loops for delrow in range(-1,2): for delcol in range(-1,2):

[ebon finch]

For the kmp algorithm, I’m struggling on fully grasping why you set len to lps[len-1] when creating your lps

[regal spoke]

So what that function is trying to calculate is known as the prefix function (It is defined here https://cp-algorithms.com/string/prefix-function.html , and is commonly denoted by pi)

The idea behind the algorithm is that greedily tries to match the suffix with the pattern.
An inefficient algorithm would just reset len to 0 when a match fails.
The trick to make an efficient algorithm is to reuse already calculated prefix function values to speed up the matching.
This is why when the greedily matching fails, it sets len to prefix_function(len - 1) instead of 0.
It could set len to 0, but that would be inefficient.

[summer fossil]

can't we call it like bfs(row+1,col) and so on... instead of for loops?

[regal spoke]

You could do something like that even with a bfs

#User function Template for python3
from collections import deque
import sys
class Solution:
    def numIslands(self,grid):
        count = 0
        vis = [[0]*len(grid[0]) for _ in range(len(grid))]
        q = deque()
        
        def bfs(row,col):
            q.append((row,col))
            while q:
                row,col = q.popleft()
                if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]) or not grid[row][col] or vis[neb_row][neb_col]:
                    continue
                vis[row][col] = 1
                q.append((row+1, col  ))
                q.append((row  , col+1))
                q.append((row-1, col  ))
                q.append((row  , col-1))
                q.append((row+1, col+1))
                q.append((row+1, col-1))
                q.append((row-1, col+1))
                q.append((row-1, col-1))
                            
                            
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if not vis[row][col] and grid[row][col]:
                    count+=1
                    bfs(row,col)
        return count

[summer fossil]

ohho i am trying to cal bfs function instead of appending in q

I understand why am i wrong Thanks!

[snow anvil]

Why would you make your life harder needlessly

[ashen forge]

Hey what would be the best way to represent a list of values

that is constantly being added onto

but has a max size

and old elements get removed, and newer ones shift

into its place

[agile sundial]

deque

[ashen forge]

oh okay ty

so popleft() and then append?

[agile sundial]

if you set a maxsize, it will automatically remove elements from the other side when you append

[ashen forge]

oh okay

ty

[marsh cradle]

i have a school projekt that i need some help with and the problem that i face is.I can't fulfill mine teacher time complexity standard. We have 5 files that we need to sort with quicksort_hybrid. This file are 10, 100, 1k, 10k 100k random files. I made quicksort and insertionsort correctly. But i do not know where is the problem.

https://godbolt.org/z/TevzoETxx

[haughty walrus]

can you tell me where i have to put it please ? I do not understand

[haughty mountain]

just #python-discussion would be fine for this kind of basic question

[haughty walrus]

okay thx !

[nova flare]

def sorting_with_merge(array):
    def merge(left, right):
        if len(left) == 0:
            return right

        if len(right) == 0:
            return left

        result = []
        index_left = index_right = 0

        while len(result) < len(left) + len(right):
            
            if left[index_left] <= right[index_right]:
                result.append(left[index_left])
                index_left += 1
            else:
                result.append(right[index_right])
                index_right += 1

            if index_right == len(right):
                result += left[index_left:]
                break

            if index_left == len(left):
                result += right[index_right:]
                break

        return result

    def merge_sort(array):
        if len(array) < 2:
            return array

        midpoint = len(array) // 2

        return merge(left=merge_sort(array[:midpoint]), right=merge_sort(array[midpoint:]))

    merge_sort(array)

this is a program for merge sort i found online, but for some reason it works much slower than insertion sort (upto 10x slower) for an array of size 10,000
is there a problem with the code?

[atomic bane]

!e

import time 
import random


def merge(left, right):
    if len(left) == 0:
        return right

    if len(right) == 0:
        return left

    result = []
    index_left = index_right = 0

    while len(result) < len(left) + len(right):
        
        if left[index_left] <= right[index_right]:
            result.append(left[index_left])
            index_left += 1
        else:
            result.append(right[index_right])
            index_right += 1

        if index_right == len(right):
            result += left[index_left:]
            break

        if index_left == len(left):
            result += right[index_right:]
            break

    return result
    

def merge_sort(array):
    if len(array) < 2:
        return array

    midpoint = len(array) // 2

    return merge(left=merge_sort(array[:midpoint]), right=merge_sort(array[midpoint:]))


def insertion_sort(array):
     for i in range(1, len(array)):
        key = array[i]
        j = i-1
        while j >= 0 and key < array[j]:
                array[j + 1] = array[j]
                j -= 1
        array[j + 1] = key


if __name__ == '__main__':
    test = random.sample(range(1, 20001), 10000)
    start = time.time()
    merge_sort(test)
    end = time.time()
    print(f'total elapsed time for merge sort: {end-start}')

    start = time.time()
    insertion_sort(test)
    end = time.time()
    print(f'total elapsed time for insertion sort: {end-start}')

[halcyon plank]

@atomic bane :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | total elapsed time for merge sort: 0.04455423355102539
002 | total elapsed time for insertion sort: 3.105802059173584

[nova flare]

Huh

[final matrix]

Hello! I know the basics of Python. Can you guys suggest me the resources to learn DSA for free?

[nova flare]

My array was also a random generated array but it perform 10x worse

[atomic bane]

Can you give me your line for generating your random number? And your code for insertion sort?

[nova flare]

See pins

[nova flare]

My array was

array = [random.randint(0,  10000) for _ in range(10000)]

[atomic bane]

Seems alright to me. Maybe your comparison inserstion sort code is incorrect?

[nova flare]

One sec I'm unable to paste it properly here

I'll send it

[atomic bane]

ok

[nova flare]

Is it okay if I DM you the website I got the code from?

I'm on phone rn and unable to paste the code

[atomic bane]

no worries

@nova flare I think the code is almost identical for insertion sort. Not sure why you are getting different results. You can try evaluating your script on the server when you are back on your desktop.

[nova flare]

Sure, I'll send a SS of the exact times that both take in a short while

insertion sort takes 7.8m ns, whereas merge sort takes 66m ns

i doubt that timer function is malfunctioning, but here it is anyway

def my_timer(orig_func):
    from time import perf_counter_ns

    def wrapper(*args, **kwargs):
        t1 = perf_counter_ns()
        result = orig_func(*args, **kwargs)
        total_time = perf_counter_ns() - t1
        print(f'{orig_func.__name__} sorted {array_length} items in: {total_time:,} ns ({total_time / 1e9} s)')
        return result

    return wrapper

in fact, insertion sort is performing unbelievably better than everything else (excluding built-in sort), in terms of both memory and time

[haughty mountain]

could you share the actual code?

and make sure you're not doing something silly like sorting a sorted list after a while

insertion sort will be hella fast on sorted data

[nova flare]

I dont believe so, I can send the file, but I dont think this server allows me to

i guess i could dm

[haughty mountain]

!paste

[halcyon plank]

Pasting large amounts of code

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

After pasting your code, save it by clicking the Paste! button in the bottom left, or by pressing CTRL + S. After doing that, you will be navigated to the new paste's page. Copy the URL and post it here so others can see it.

[nova flare]

oh

alright one min

https://paste.pythondiscord.com/3NSQ

thats the complete file, it has a bunch of other sorting functions too

[atomic bane]

Can you suggest what fenix said, can you move the insertion sort as the first sorting function?

[nova flare]

oh was that the reason

alright ill comment out all the other sorts as well

ahh yeah that was it, seems that since bubble sort function sorted it in place, insertion sort didnt really do anything lol

[atomic bane]

I think built in sort returns a new list, but your bubble sort is sorting it in place

yeah

[nova flare]

lmao yep that was the problem

now insertion sort took 13s

thank you both!

[haughty mountain]

so yeah, make a copy of the list before sorting

[nova flare]

array[::] makes a deepcopy right?

[haughty mountain]

it's not the first time someone has made this mistake in this channel 😛

just array[:] is enough

not deep copy

[nova flare]

ah yeah right right

[haughty mountain]

but a shallow copy

but it's enough for a this

[nova flare]

so bubble sorting it would give the same error since original array is also modified?

oh alright

ill try it

[haughty mountain]

some sorts run faster on specific inputs

e.g. insertion sort or python's internal sort on sorted input

something like merge sort or bubble sort would typically take roughly the same amount of time regardless

[nova flare]

oh that explains it all, good to know

thanks

[regal spoke]

Btw you can make your insertion sort many times faster with a smarter implementation. I'm not even sure I would call what you have insertion sort.

What you want to do is to start with an empty list A.

Then for every insert you want to binary search for the insert point, and then use A.insert(insert_point, x)

For the binary search you could either implement your own binary search or use insert_point = bisect.bisect_left(A, x)

[nova flare]

ooh sounds fun, I'll try implementing it when I'm free

I just copied that code from a website

[scenic abyss]

Thank you pinned message

[outer rain]

what would be faster about that?

Oh, you delegate shifting in insertion to CPython

I see

yeah, that would be way faster

[regal spoke]

Two things.

1. Number of comparisions per insert would be O(log n) instead of O(n)
2. Insert would be delagated to some fast C function, which runs really fast, especially compared to manually doing the insert in python code.

[brazen python]

Is index-lookup O(1) for list like it is for an array?

[atomic bane]

Yes, you can also have a look at https://wiki.python.org/moin/TimeComplexity for more documentation on time complexity

[fervent saddle]

It's like a wrapper around a dynamically resizing array. Like c++ std::vector.

Or Java ArrayList IIRC

[agile sundial]

yes it's basically an ArrayList<object> or a std::vector<PyObject *>

[brazen python]

Gonna bookmark this, thank you

[hard pivot]

You know how you can figure out the ways to count to N with increment sizes of 1 and 2 using n-1 + n-2. Then if increments are 1, 2 or 3 with n-1 + n-2 + n-3?(DP, staircase problem) Does this work for step sizes 1 to any number? And what if it was like random step sizes like 2, 9, 12

[narrow mica]

Well yeah it would, there's nothing stopping the idea from working
You're basically working backwards by thinking, "so if I'm on N, then I must've gotten here from N-2, N-9, or N-12."
And if the numbers don't make sense, say N-9 = -2, then that just means there's 0 ways for you to to have come from N-9

A minimal implementation could be something like

from functools import cache

@cache
def count_to(n, step_sizes):
  if n <= 0:
    return n == 0
  return sum([count_to(n-step, step_sizes) for step in step_sizes])```

[haughty mountain]

the forwards version is also very easy

!e

# e.g. fibonacci
step_sizes = [1, 2]
n_steps = 10

res = [1]
for i in range(n_steps):
  res.append(sum(res[-step] for step in step_sizes if step <= len(res)))

print(res)

[halcyon plank]

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

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

[haughty mountain]

and this doesn't have the drawback of the overhead and limitations of python recursion

[young vale]

what's the difference between strong induction and weak induction? I'm having a hard time identifying what to use 🥲

[hard pivot]

Makes sense, that's what i assumed but I could not find a single example to prove that it worked online lol

[jolly mortar]

in weak induction you only need P(k) to prove P(k+1), in strong you need P(1), P(2), ..., P(k) to prove P(k+1)

[regal spoke]

There isnt really a fundamental difference between the two.

The way I think of induction is like this:
You are given some formula/statement depending on a postive integer n, and your goal is to prove that the formula is correct.
Note that if the formula is wrong, then there has to be a smallest n for which the formula is incorrect.
In an "induction proof", you prove that such an n cannot exist.

[shadow glen]

okay guys is there any library that allows me to unify 2 lists while remove deundances?

i want to remove redundances

so i can do like:
list1 = [2,3,4]
list2 = [3,4,8]
list = unify(list1,list2)
then the result being
list = [2,3,4,8]

[regal spoke]

People usually do that using a set.

You could also try implementing a modified version of merge sort that removes any duplicates it finds

[shadow glen]

well, i tried set but it didn't worked

[shadow glen]

i also tried but in my character deleting function it bugs

so i'm searching a different solution

[regal spoke]

What exactly didnt work? The example you gave definitely works using set

!e

def unify(A, B):
  return list(set(A) | set(B))

list1 = [2,3,4]
list2 = [3,4,8]
unified_list = unify(list1,list2)
print(unified_list)

[halcyon plank]

@regal spoke :white_check_mark: Your 3.11 eval job has completed with return code 0.

[2, 3, 4, 8]

[shadow glen]

basically this:

[shadow glen]

oh that is much beetter

*better

[shadow glen]

File "c:\Users\User\Documents\GitHub\RP-Utilities\cogs\CharactersCog.py", line 204, in unify
return list(set(A) | set(B))
^^^^^^
TypeError: unhashable type: 'dict'

okay so since it's a dict type in a list

will i just need to remove set

?

or there is something else?

[regal spoke]

The elements of a set need to be a hashable type, like strings, integers or tuples.

[shadow glen]

yep, that's why i asked this question

cus like it's a list of dicts

both A and B

[regal spoke]

If you are ok with kinda slow running code, then try

!e

def unify(A, B):
  C = list(A)
  for b in B:
    if b not in C:
      C.append(b)
  return C

list1 = [2,3,4]
list2 = [3,4,8]
unified_list = unify(list1,list2)
print(unified_list)

[halcyon plank]

@regal spoke :white_check_mark: Your 3.11 eval job has completed with return code 0.

[2, 3, 4, 8]

[regal spoke]

The inoperator only makes use of ==, so the elements dont need to be hashable. But it might run kinda slow

[shadow glen]

and then we are back to the same problem:

in delete it should had appeared charA

when i type delete c

a strange kind of error

why it's not appearing?

before unify it appears like this:
[{'_id': ObjectId('64d7f1c83d613d9e0bf37c2e'), 'user_id': 1130268405333753857, 'name': 'charA', 'prompt_prefix': 'cA:', 'image_url': None}, {'_id': ObjectId('64d8cf2ef4a4c138dc2ce421'), 'user_id': 1130268405333753857, 'name': 'CharB', 'prompt_prefix': 'cB:', 'image_url': 'https://upload.wikimedia.org/wikipedia/en/3/3d/Senpai_wa_Otokonoko_volume_1.png'}]

but then after unify nothing appears

okay so now i noted what happened

yesh i fixed it

[shut mauve]

I'm trying to generate a multiple digit number out of a picture.
I have a dictionary with data about every single digit in the number already collected. Each value in the dictionary corresponds to the x pixel position of a digit. So the lowest '7' is the most left digit, the highest value '74' is the most right digit.

Looking at the picture it should generate: 12288.

How would I do this?

[shut mauve]

already done it myself if anyone wants to know how:

digit_positions = {'Enemy_Gold_5.png': {'number': 5, 'values': [7, 19]}, 'Enemy_Gold_6.png': {'number': 6, 'values': [33, 68]}, 'Enemy_Gold_7.png': {'number': 7, 'values': [80]}, 'Enemy_Gold_8.png': {'number': 8, 'values': [52]}}
digitssorted = []

digitssorted = [[i, data['number']] for key, data in digit_positions.items() for i in data['values']]
digitssorted.sort()
finalresult = ''.join(map(str, [num for _, num in digitssorted]))

print(int(finalresult))
    

[marble ingot]

I have a python dataclass that gets instantiated a few thousand times per second.

I need to make sure it's optimised. In an effort to accomplish that, most of its parameters are numpy c-types. I rely on this object so much, I'm wondering if python is even appropriate for defining it or if it would be most performant to make the data class in C. I also don't know what the additional difficulties will be with making C objects, if the performance would be worth it, or what the alternatives are.

Since I pass these objects around via queues a lot, if its faster to pack the data for the queue and unpack it after the queue, that's a consideration. (The only benefit would be if python's method of pickling the object is slower than me manually packing and unpacking it)

I need to learn better methods for benchmarking and I need to learn how to profile.

Something I just learned after getting some help in a #1035199133436354600 thread... Numpy can do packing and unpacking, and apparently it does it a lot faster than struct. Since I'm currently using struct for interfacing with USB devices, then converting the data to numpy types... just having numpy do it would be a significant improvement.

[livid holly]

Please, I need help understanding the bubble sort algorithm below especially the inner for loop and specifically what the character in the range function would mean:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

[marble ingot]

Looking at that code, you can think about it like this:

The comparison (only the last two lines) only uses the value j to address which elements are being compared (to swap them if they're out of order).

So what you're interested in is what the pattern of j is.

Copy the nested loops somewhere so you can just set n manually (without an array) and then in place of the comparison code, add a print statement to print j.

Just by looking at it, you should see it iterate over values of j like this:

first, i=0, so it'll run j from 0 to n-1 (sweeping over the array once).

then, i=1, so it'll run j from 0 to n-2 (sweeping over the array again, except one short)

and so on, until j gets called 0, 1, 2... 0, 1... 0... and then done.

[livid holly]

Thank you so much. I thought just would iterate from 0 to n - 1 since the last value and the second to the last value would get swapped anyway?

[summer badge]

hey how can i convert a balance to a numeric value to float it

because i tried to use a float dunder that i included but it didn't work

here are some code snippets:

    def __float__(self):
        if self.account_balance:
            return float(self.account_balance)
        else:
            return float(0)

def calculate_order_size(self, current_price):
        
        if not isinstance(self.balance, (int, float)):
            raise ValueError("Balance must be a numeric value")
        
        if not isinstance(self.max_loss_pct, float):
            raise TypeError("Max loss percentage must be a float")
        
        risk_amount = float(self.balance) * self.max_loss_pct
        stop_loss_price = current_price * (1 - self.stop_loss_pct)
        take_profit_price = current_price * (1 + self.take_profit_pct)
        
        order_size = risk_amount / (current_price - stop_loss_price)
        
        potential_profit = order_size * (take_profit_price - current_price)
        
        if potential_profit < risk_amount:
            order_size = risk_amount / (take_profit_price - current_price)
            
        return int(order_size)

Error:

Traceback (most recent call last):
  File "c:\Users\lenovo\Documents\ccdi.py", line 561, in <module>
    order_size=riskmg.calculate_order_size(current_price)
  File "c:\Users\lenovo\Documents\ccdi.py", line 215, in calculate_order_size
    raise ValueError("Balance must be a numeric value")
ValueError: Balance must be a numeric value

[regal spoke]

You could implement bubble sort like this

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

But if you think about it, you can for example see that after the first iteration of the outer loop, the maximum has bubble into the correct place in arr. This allows you to make a slightly more efficient implementation:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

[regal spoke]

What type is self.balance?

[summer badge]

what do you mean ?

[summer badge]

i mean it s not a int or a string the format of the balance object ain't compatible with float

[regal spoke]

You asked "hey how can i convert a balance to a numeric value to float it". So I was wondering what you meant by balance.

[summer badge]

it is like a bank balance

[summer badge]

but it is on a broker

[regal spoke]

Ye I get that it balance refers to a bank balance. But what type in Python are you using to represent the balance?

[summer badge]

i'm sorry i didn't understand your question

[livid holly]

Oh, I see now. Thank you very much. I 'd like to ask. Is there some tool I can use to help me track each iteration and what the output might be in each step? I would like to see what happens in each iteration and not only for this, but also for other sorting algorithms which I am trying to understand like selection sort.

[summer badge]

yes i understood now i think. I created a BalanceApp class

to represent balance

[regal spoke]

Oh ok, so your problem is that the function you are calling checks that your balance is isinstance(balance, (int, float)), but you want to use your own custom class for balance?

[summer badge]

i mean i have a BalanceApp class but i defined that the class is the balance object. And this object ain't compatible with the float

[regal spoke]

There are tons of videos of that on youtube. Some of the classics are https://www.youtube.com/watch?v=kPRA0W1kECg and https://www.youtube.com/watch?v=EdIKIf9mHk0&list=PLOmdoKois7_FK-ySGwHBkltzB11snW7KQ

[livid holly]

Thank you so much for this. I appreciate it. 🙏

[summer badge]

@regal spoke ?

[regal spoke]

I'm not sure I understand what you are saying

[summer badge]

Well, so I have a balance object that is the class itself that i want to float to give me my actual balance

do you need the BalanceApp code snippet

?

[regal spoke]

sure

[summer badge]

ok here is it

class BalanceApp(EWrapper, EClient):
    def __init__(self, ip_address, port_id, client_id):
        EClient.__init__(self, self)
        self.ip_address = ip_address
        self.port_id = port_id
        self.client_id = client_id
        self.account_balance = None

    def start(self):
        self.connect(self.ip_address, self.port_id, self.client_id)
        self.run()

    def nextValidId(self, orderId: int):
        super().nextValidId(orderId)
        self.nextorderId = orderId
        print('The next valid order id is: ', self.nextorderId)

    def accountSummary(self, reqId: int, account: str, tag: str, value: str, currency: str):
        super().accountSummary(reqId, account, tag, value, currency)
        if tag == 'TotalCashValue':
            self.account_balance = float(value)

    def __float__(self):
        if self.account_balance:
            return float(self.account_balance)
        else:
            return float(0)

    def error(self, reqId, errorCode, errorString):
        print(f"Error: {reqId} - {errorCode} - {errorString}")
        if errorCode == 2104:  # Market data farm connection is OK
            return

As you can see I used a float dunder in the BalanceApp

[regal spoke]

Okey, but just so you know. This check:

isinstance(balance, (int, float))

is a check if the type of balance is either int or float or a subclass of int or float.
It is not a check for if balance has a __float__ method.

[regal spoke]

So if you want to trick calculate_order_size that the balance is a float, then you will probably need to do something like this

BalanceApp(EWrapper, EClient, float):

!e

class fruit:
  pass

class banana(fruit):
  pass
b = banana()
print('Is b an int?', isinstance(b, int))

class int_banana(fruit, int):
  pass
ib = int_banana()
print('Is ib an int?', isinstance(ib, int))

[halcyon plank]

@regal spoke :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | Is b an int? False
002 | Is ib an int? True

[fiery cosmos]

Is it better for me to write solutions to DSA problems first on paper rather than on computer? That is what book Cracking the coding interview proposes.

[regal spoke]

If you are trying to write actual runnable code, then just do it on a computer.

[fiery cosmos]

Hmmm, I was wondering to do it on the paper initially because then I will think more rather than submit solution to Leetcode and wait for result or something like that

[summer badge]

Thank you so much ! Appreciate it

[summer badge]

so i should actually remove this error raise and the check right ?

but the thing is that now i get this:

Traceback (most recent call last):
  File "c:\Users\lenovo\Documents\ccdi.py", line 545, in <module>
    balance = BalanceApp(ip_address,port_id,client_id)
TypeError: float expected at most 1 argument, got 3

[regal spoke]

Coding runable code takes a lot more time and is more complicated than sketching things out with a pen and paper. That is why it can be good to start out with just pen and paper.

Then once you feel ready, go to the computer and try to implement your ideas.

[fiery cosmos]

If you would do something differently with regards to DSA problems solving in the case you would starting again, what would you do to become better at it?

[regal spoke]

I'm not sure I understand what you are asking for.

[fiery cosmos]

I am beginner in DSA problems solving and I am trying to not do mistake(s) that people do

I am trying to understand what people do not do to become better at DSA problems solving so I do not do same mistake(s)

[regal spoke]

There are two different goals here:

1. Learn how to solve problems
2. Get better at programming

To practice 1 you don't technically need computer, you just need a pen and paper and some problems.

But if 2. is your goal, then you are going to have to try implementing your solution in a computer.

[fiery cosmos]

Basically way forward is to solve as much as problems as possible

[summer badge]

@regal spoke can u tell me what to do plz

[regal spoke]

What you want to do is to use __new__ like this instead of __init__.

!e

class fruit:
  pass

class float_banana(fruit, float):
    def __new__(cls, a, b):
        self = float.__new__(cls, 0)
        self.a = a
        self.b = b
        return self

fb = float_banana('abc', 2)

print('Is fb an float?', isinstance(fb, float))

[halcyon plank]

@regal spoke :white_check_mark: Your 3.11 eval job has completed with return code 0.

Is fb an float? True

[summer badge]

so i should create or replace the __new__ by the __init__

[regal spoke]

You need to use __new__ instead of __init__

[summer badge]

In the balanceApp class

[regal spoke]

yes

[summer badge]

ok nice

[robust canyon]

How are sets structured? I think they're built on top of a dictionary/hashmap, or something like that. I don't understand something like checking for duplicates with a set, would that be O(n) worst case?

[regal spoke]

Both dictionaries and sets run in O(n) in worst case

It is relatively easy to come up with data that makes them run in O(n) too

Sets and dictionaries in Python store its elements in a power of 2 sized list which is roughly double the size of the number of elements currently stored in the set/dictionary. Depending on the hash, each element has a prefered spot in this list. If that spot is taken by some other element then it does a kind psuedo random walk to find its next prefered spot.

[robust canyon]

Is there anywhere that I can find documentation/more information on this? I'd love to read more about it

And thank you for the explanation, that makes a lot more sense

[regal spoke]

You can easily find the source code for it https://github.com/python/cpython/blob/bb86bf4c4eaa30b1f5192dab9f389ce0bb61114d/Objects/dictobject.c#L700-L720

But I don't know of a great write up on it.

[robust canyon]

Oh thanks, I completely forgot that cpython existed

[regal spoke]

Here is a fun script if you want to try to play around with triggering the worst case slowdown for dictionaries

!e

def dict_ddos(n):
    pow2 = 1
    while pow2 < 2 * n: pow2 *= 2

    # Fill up all spots that 0 wants to use
    A = [pow2]
    i = 1
    for _ in range(n // 2):
        A.append(i)
        i = (i * 5 + 1) % pow2

    # Spam 0s
    A += [0] * (n - len(A))
    return A

B = {}
for a in dict_ddos(10**5):
    B[a] = 1

[halcyon plank]

@regal spoke :warning: Your 3.11 eval job timed out or ran out of memory.

[No output]

[regal spoke]

There is also this script

[summer badge]

Well i tried to fix this issue but i couldn't
Here is the code snippet rn:

class BalanceApp(EWrapper, EClient, float):
    def __new__(self, ip_address, port_id, client_id):
        EClient.__init__(self, self)
        self.ip_address = ip_address
        self.port_id = port_id
        self.client_id = client_id
        self.account_balance = None

And the error:

Traceback (most recent call last):
  File "c:\Users\lenovo\Documents\ccdi.py", line 545, in <module>
    balance = BalanceApp(ip_address,port_id,client_id)
  File "c:\Users\lenovo\Documents\ccdi.py", line 160, in __new__
    EClient.__init__(self, self)
  File "C:\Users\lenovo\AppData\Local\Programs\Python\Python39\lib\site-packages\ibapi\client.py", line 48, in __init__
    self.reset()
TypeError: reset() missing 1 required positional argument: 'self'

[regal spoke]

!e

# Fill A with integers that all hash to 0
A = [i * (2**61 - 1) for i in range(10**5)]

B = {}
for a in A:
    B[a] = 1

[halcyon plank]

@regal spoke :warning: Your 3.11 eval job timed out or ran out of memory.

[No output]

[regal spoke]

Check my example here #algos-and-data-structs message

You need to create self by calling float.__new__(cls, 0)

[robust canyon]

So it's slowing down because python is having to find a way to hash thousands of 0's, i.e. trying to figure out a way to store 1000's of 0's as keys in the same dict?

[regal spoke]

The dict_ddos(n) first fills up all of the n/2 first spots that 0 wants to occupy in the internal power of 2 sized list. After doing this it will for example take ages to check if 0 is in the dict.

[regal spoke]

No. Python doesn't have a hard time to hash 0, the hash of 0 is just 0.

Maybe this makes it a little bit more clear to what is going on

!e

def dict_0ddos(n):
    pow2 = 1
    while pow2 < 2 * n: pow2 *= 2

    B = {}
    # Fill up the n first spots that 0 wants to use
    B[pow2] = 1
    i = 1
    for _ in range(n - 1):
        B[i] = 1
        i = (i * 5 + 1) % pow2
    return B

B = dict_0ddos(10**5)
for _ in range(10**5):
    # Checking if 0 is in B will take O(n) time
    0 in B

[halcyon plank]

@regal spoke :warning: Your 3.11 eval job timed out or ran out of memory.

[No output]

[sand vault]

!e

list = ((1,2,3,4),(1,2,3,4))
print(list[0][0])

[summer badge]

@regal spoke i tried ur example but it returns me this:

Traceback (most recent call last):
  File "c:\Users\lenovo\Documents\ccdi.py", line 550, in <module>
    balance = BalanceApp(ip_address,port_id,client_id)
TypeError: __init__() takes 1 positional argument but 4 were given

Here is a code snippet:

class BalanceApp(EWrapper, EClient, float):
    
    def __new__(cls, ip_address, port_id, client_id):
        instance = float.__new__(cls, 0.0)
        instance.ip_address = ip_address
        instance.port_id = port_id
        instance.client_id = client_id
        instance.account_balance = None
        return instance
    

    

    def start(self):
        self.connect(self.ip_address, self.port_id, self.client_id)
        self.run()

    def nextValidId(self, orderId: int):
        super().nextValidId(orderId)
        self.nextorderId = orderId
        print('The next valid order id is: ', self.nextorderId)

    def accountSummary(self, reqId: int, account: str, tag: str, value: str, currency: str):
        super().accountSummary(reqId, account, tag, value, currency)
        if tag == 'TotalCashValue':
            self.account_balance = float(value)

    def __float__(self):
        if self.account_balance:
            return float(self.account_balance)
        else:
            return (0)

print('Is balance a float?', isinstance(balance, float))

[regal spoke]

Okey, then try keeping __init__ as what it was, and make __new__ be just

    def __new__(cls, ip_address, port_id, client_id):
        return float.__new__(cls, 0.0)

!e

class fruit:
  def __init__(self):
      pass

class float_banana(fruit, float):
    def __init__(self, a, b):
        self.a = a
        self.b = b
    def __new__(cls, a, b):
        return float.__new__(cls, 0)

fb = float_banana('abc', 2)

print('Is fb an float?', isinstance(fb, float))

[halcyon plank]

@regal spoke :white_check_mark: Your 3.11 eval job has completed with return code 0.

Is fb an float? True

[regal spoke]

I'm not sure if this is the proper way to do it. But I think it will work

[summer badge]

ok i ll do it

[robust canyon]

Yeah that does I think, thanks

[summer badge]

same error 😦

[regal spoke]

Really?

I dont have your code so I cant test these things out

[summer badge]

do u want me to provide u the code by dm or e mail or something ?

[regal spoke]

You could dm if you want

[summer badge]

ok nice

[summer badge]

done

[regal spoke]

You should have done what I said here #algos-and-data-structs message

class BalanceApp(EWrapper, EClient, float):
   def __init__(self, ip_address, port_id, client_id):
       EClient.__init__(self, self)
       self.ip_address = ip_address
       self.port_id = port_id
       self.client_id = client_id
       self.account_balance = None
   
   def __new__(cls, ip_address, port_id, client_id):
       return float.__new__(cls, 0.0)

The code you sent me just had ```py
def new(cls):
return float.new(cls, 0.0)

Btw a better solution to all of this is to just remove the isinstance(self.balance, (int, float)) checks in the first place.

[fiery cosmos]

If I as input have digits, operators (+,-,*,/) and as much as possible paranthesis, in order to solve that math expression that I have as input, what kind of data structures and algorithms I can use? I wouldn't like to use eval

[narrow mica]

You first convert the original expression into a prefix or postfix expression, then evaluate that

[fiery cosmos]

Do I need to use any algorithm or data structure? Iirc, I saw somewhere that I need to use particular algorithm

[narrow mica]

I think you use stacks to store the numbers when you evaluate the pre/postfix expression
I don't think there's a particular name for the algorithm that converts the original expression

Search for infix calculator or something and you'll probably find some implementations

[fiery cosmos]

Thanks, will do that

[summer badge]

@regal spoke when i call balance.__new__() cls is = to what ?

[regal spoke]

You should never manually call balance.__new__

It is called automatically when you construct balance

#algos-and-data-structs message look at this example

[summer badge]

Ah ok thank u so much

[haughty mountain]

they probably mention the shunting yard algorithm

[fiery cosmos]

yup

I can recall name of algorithm

Implement an algorithm to determine if a string has all unique characters

This is my solution

string = "abcdagh"
my_dict = {}

def add_or_increment(dictionary, key):
    try:
        dictionary[key] += 1
        if  dictionary[key] == 2:
            return 1
    except KeyError:
        dictionary[key] = 1
        return 0
not_unique = 0
for element in string:
    if add_or_increment(my_dict, element) == 1:
        not_unique = 1
        break
if not_unique:
    print("String is not unique")
else:
    print("String is unique")

Can it be faster?

What if I can't use additional data structure? Is fastest way to loop through two loops, first loop is i = 0, second j = i + 1, then check if string[i]= string[j]?

[fiery cosmos]

Given two strings, write a method to decide if one is a permutation of the other

my_dict1 = {}
my_dict2 = {}

string1 = "abcd"
string2 = "dcba"

def add_or_increment(dictionary, key):
    try:
        dictionary[key] += 1
        if  dictionary[key] == 2:
            return 1
    except KeyError:
        dictionary[key] = 1
        return 0
    
for element in string1:
    add_or_increment(my_dict1, element)
for element in string2:
    add_or_increment(my_dict2, element)
is_permutation = 1
if len(my_dict1) != len(my_dict2):
    print("One string is not permutation of another")
else:
    for key in my_dict1:
        if my_dict1[key] != my_dict2[key]:
            is_permutation = 0
            break
    if is_permutation == 1:
        print("One string is permutation of another")
    else:
        print("One string is not permutation of another")

[regal spoke]

len(string) == len(set(string))

[regal spoke]

sorted(string1) == sorted(string2)

[fiery cosmos]

Hmm, then "abcd" and "gfdh" would be same because those strings have same length, no?

[regal spoke]

"Implement an algorithm to determine if a string has all unique characters"

I gave you a one linear to each of your problems

[fiery cosmos]

Rotate matrix: Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees.

I do not know how to present to myself how would this picture placed in the array look like. Like if there is one pixel how would array look like?

[lament totem]

@fiery cosmos

[fiery cosmos]

arr[0,0] is one bit, right? so arr[0,0], arr[0,1], arr[0,2], arr[0,3], arr[0,4], arr[1, 0], arr[1,1], arr[1,2], arr[1,3], ... , arr[3,3] would be one byte, right?

[regal spoke]

Probably you can just ignore that byte instruction. It is probably just trying to hint someone using C++ to use int.

[fiery cosmos]

So one byte would be just one point in array, like arr[0,0], or...?

Another question: There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away.

EXAMPLE

pale, ple -> true
pales, pale -> true
pale, bale -> true
pale, bike -> false

My solution

string1 = "pale"
string2 = "bake"
def add_or_increment(dictionary, key):
    try:
        dictionary[key] += 1
        if  dictionary[key] == 2:
            return 1
    except KeyError:
        dictionary[key] = 1
        return 0
    
for element in string1:
    add_or_increment(my_dict1, element)
for element in string2:
    add_or_increment(my_dict2, element)
is_one_away = 1
if abs(len(my_dict1) - len(my_dict2)) > 1:
    print("Strings are not one or zero edits away")
else:
    counter = 0
    for key in my_dict1:
        if my_dict1[key] != my_dict2[key]:
            counter += 1
            if counter == 2:
                break
    if counter > 1:
        print("Strings are not one or zero edits away")
    else:
        print("Strings are one or zero edits away")

Could it be faster?

[regal spoke]

I think you should just intepret the problem like this Rotate matrix: Given an image represented by an NxN matrix, write a method to rotate the image by 90 degrees.

Forget about that byte stuff

[fiery cosmos]

Yeah but I am confused how is one byte positioned in matrix, two bytes, three bytes..

I would like to know that 😄 lol

[regal spoke]

In languages like C++ the standard integer type is 32 bits = 4 byte

I think that is all they are trying to hint at

This wont matter for Python

[fiery cosmos]

Ah I see, so their one point is like one number in the array

[regal spoke]

Thats my best guess

But that problem formulation is kinda nonsense to begin with

[fiery cosmos]

Wdym?

[regal spoke]

"where each pixel in the image is 4 bytes"

This part

makes no sense

I can guess what they are trying to say

[fiery cosmos]

Hmm, also I am not sure how to rotate something 90 degrees

btw @regal spoke how do you propose to get better at DSA problem solving? i started to read book cracking the coding interview, I planned to combine Leetcode with that book

I mean from where to solve problems and learn particular tricks

[regal spoke]

I think your implementation here is wrong.The order of the characters matter for edit distance, but your solution here kinda ignores the order

[fiery cosmos]

Yeah I think you are right

Iirc I used dynamic programming for that in one NLP course

[regal spoke]

I'm a big fan of websites like https://codeforces.com/ or https://open.kattis.com/ or https://cses.fi/problemset/ or https://atcoder.jp/

[fiery cosmos]

Why those instead of LeetCode?

[regal spoke]

I do programming to challenge myself with difficult problems. LeetCode is usually too easy for my taste

[fiery cosmos]

Do you have idea how can I know where is correct index for particular byte after rotation for 90 degrees?

[regal spoke]

Forget about bytes.

Call them pixels or something

[fiery cosmos]

Okay, pixel

[regal spoke]

About the 90 degree rotation. Think about how you would rotate this by 90 degrees

Rotating it clockwise by 90 degrees would result in

2 1
4 3
6 5

[brazen python]

is there some accurate tool that can measure exactly how much memory an object consumes?

[fiery cosmos]

how would

[1 2 ]
[3 4]

be rotated for 90 degrees?

Is that

[3 1]
[4 2]?

[regal spoke]

yes

Btw just so you know, in Python you the standard way to represent a matrix is as a list of list

where the inner lists correspond to the rows of the matrix

[fiery cosmos]

like 2 x 3 would be a = [[[0,0],[0,1], [0,2]]], [[1, 0],[1,1],.., [1,3]], ...[[3,0],...[3,3]]] ?

[regal spoke]

what?

I said a list of lists

This would be

A = [[1,3,5], [2,4,6]]

[fiery cosmos]

I see

[haughty mountain]

it's how you usually end up representing it

one byte per color channel, RGBA or BGRA depending on endianness

not that what you are rotating matters much

[regal spoke]

Ye ok. But that is not relevant information for rotation

[haughty mountain]

yeah

[regal spoke]

!e

def print_matrix(A):
  for row in A:
    print(*row)
  print()

A = [[1,3,5], [2,4,6]]

print_matrix(A)
print_matrix([*zip(*A[::-1])])
print_matrix([*zip(*A)][::-1])

[halcyon plank]

@regal spoke :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | 1 3 5
002 | 2 4 6
003 | 
004 | 2 1
005 | 4 3
006 | 6 5
007 | 
008 | 5 6
009 | 3 4
010 | 1 2

[summer fossil]

https://practice.geeksforgeeks.org/problems/rotten-oranges2536/1```

class Solution:

    #Function to find minimum time required to rot all oranges. 
    def orangesRotting(self, grid):
        row = len(grid)
        col = len(grid[0])
        from collections import deque
        q = deque()
        vis = grid[::]
        
        for i in range(row):
            for j in range(col):
                if grid[i][j]==2:
                    q.append(((i,j),0))
                    vis[i][j] = 2
                else:
                    vis[i][j]=0
                    
         
        time = 0
        delrow = [-1,0,+1,0]
        delcol = [0,+1,0,-1]
        while q:
            a,t = q.popleft()
            r,c = a[0],a[1]
            time = max(time,t)
            for i in range(4):
                nrow = r + delrow[i]
                ncol = c + delcol[i]
                if nrow >=0 and nrow < row and ncol >= 0 and ncol < col and vis[nrow][ncol] !=2 and grid[nrow][ncol]==1:
                    print("Hola")
                    q.append(((nrow,ncol),t+1))
                    print(q)
                    vis[nrow][ncol]= 2
                    
        for i in range(row):
            for j in range(col):
                if vis[i][j]!=2 and grid[i][j]==1:
                    return -1
        return time```

[naive oak]

can you send the link not in a text box

[fiery cosmos]

If I understood you correctly, in order to rotate something for 90 degrees, I just need to A[::-1]) ?

btw, what is the meaning of using * there?

[summer fossil]

https://practice.geeksforgeeks.org/problems/rotten-oranges2536/1

[naive oak]

and what's the issue you're having?

[summer fossil]

if nrow >=0 and nrow < row and ncol >= 0 and ncol < col and vis[nrow][ncol] !=2 and grid[nrow][ncol]==1: this part

[naive oak]

what's wrong with it?

[summer fossil]

I think this part is not working i don;t know why?

[naive oak]

why do you think it isn't working

[summer fossil]

because print(q) and print("hola") is not printing

[naive oak]

what does the starting grid look like?

[summer fossil]

grid = {{0,1,2},{0,1,2},{2,1,1}}

-1 2
0 3
1 2
0 1
0 2
1 3
2 2
1 1
1 0
2 1
3 0
2 -1```nrow and ncol

[naive oak]

ah

[summer fossil]

why if condition is not working here

[naive oak]

vis = grid[::] is a shallow copy not a deepcopy

you'd need vis = [row[:] for row in grid]

[summer fossil]

so i need to use deepcopy here i think i solved a similar question with shallow copy

[summer fossil]

Shit bro It's work Thanks!

[regal spoke]

No. A[::-1] would just flip the matrix upside down which is not the same as rotating it by 90 deg

[fiery cosmos]

I see. Will try to think about how to rotate it to 90 degrees

[regal spoke]

My code does rotate the matrix by 90 degrees

[tawny prairie]

ooooooooohhhhhh

very intersting

[fiery cosmos]

You mean two times in a row A[::-1]) A[::-1]) will rotate it, or...? Also, I don't know why did you use * symbol

[regal spoke]

[*zip(*A)] is a classic Python trick for transposing a matrix. Which is almost the same as rotating the matrix by 90 degrrees, but it is not the same.

[hybrid umbra]

hello can anyone help me in a test please

please brother anyone

i am hanged

in my test

[fiery cosmos]

Which is almost the same as rotating the matrix by 90 degrrees, but it is not the same
Can you explain please?

[regal spoke]

https://stackoverflow.com/questions/10169919/python-matrix-transpose-and-zip

[fiery cosmos]

One Away

There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away.

EXAMPLE

pale, ple -> true
pales, pale -> true
pale, bale -> true
pale, bike -> false

input_string1 = "pale"
input_string2 = "ple"
string = ""
last_correct_index = 0
not_one_away = 1
counter = last_correct_index
len_of_second_index = len(input_string2)
if abs(len(input_string1) - len(input_string2)) >= 2:
    print("Strings are not one or zero edits away")
else:
    for index, element in enumerate(input_string1):
        if (index - last_correct_index) > 2:
            not_one_away = 0
            break
        if counter < len_of_second_index and (element == input_string2[counter]):
            last_correct_index = counter
            counter = last_correct_index + 1
        elif index < len_of_second_index and (element == input_string2[index]):
            last_correct_index = index
            counter = last_correct_index + 1 
if not_one_away == 1:
    print("Strings are one or zero edits distance")
else:
    print("Strings are not one or zero edits distance")

Is this correct solution?

I get correct output for my inputs

[lean walrus]

That's cool.
There is one problem: rows are tuples, so you cant modify them.
Fixed code: [*map(list,zip(*A))]

[fiery cosmos]

String Rotation

Assume you have a method IsSubstring which checks if one word is a substring of another. Given two strings, s1 and s2 , write code to check if s2 is a rotation of s1 using only one call to isSubstring (e.g., "waterbottle" is rotation of "erbottlewat")

Interesting problem. Didn't know how to solve it without looking at solution.

[naive oak]

is it ||check if s1 is in s2+s2||?

[fiery cosmos]

In the solution is reversed but I think that would also work

[spring jasper]

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
some solutions make a pointer at index 2 and then check pointer - 2 and pointer -1

but the constraints say > 1 <= nums.length <= 3 * 104

so why do those solutions pass when len(nums) == 1

the return value would be 2

and from the spec we see this

int k = removeDuplicates(nums); // Calls your implementation
assert k == expectedNums.length;

how is expectedNums.length for an array like [1] equal to 2

is this a missing test case

[tiny crest]

Can anybody help me with linked list? next week I got midterm exam

[regal spoke]

The way I would have coded something like this would not do any work at all of len(nums) == 1. Because of that I wouldn't index out of bounds

[tiny crest]

I'm struggling with pointers

[spring jasper]

Sure but how does a solution like this one pass
https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/solutions/3861369/3-line-easy-to-understand-code-beats-86-in-runtime-99-31-in-memory-very-easy-to-understand/

It shouldnt

[regal spoke]

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        ans=2
        for i in range(2,len(nums)):
            if nums[i]!=nums[ans-2]:nums[ans]=nums[i];ans+=1
        return ans
``` the for loop here only runs if len(nums) >= 3

Otherwise the range is empty

[spring jasper]

So the return is 2

[regal spoke]

yes