#algos-and-data-structs

1 messages · Page 35 of 1

regal spoke
#

^ this is the definition of a leaf

stiff quartz
#

I agree, however, it doesn't seem to me that I'm doing something different

regal spoke
#

oh wait, ye ok

stiff quartz
#

Oh, maybe the problem is sum([final_costs[child] for child in copy_of_my_dag[node]])

#

I'm doing this sum way too many times

#

It doesn't really address the space complexity though

#

oh no it does, I don't need to have a copy of my dag

regal spoke
#

So your code is good

stiff quartz
#

Oh

regal spoke
#

It runs a tad bit slow, but that is to be expected since you are using dictionaries and sets everywhere

stiff quartz
#

What is PyPy under the hood

#

It compiles Python?

# 
Whereas CPython compiles Python to intermediate bytecode that is then interpreted by a virtual machine, PyPy uses just-in-time (JIT) compilation to translate Python code into machine-native assembly language.

I never understand anything when things like this are written

regal spoke
stiff quartz
#

I always thought JIT was not as good as compiling

#

If you do JIT you compile a lot of times?

#

If you compile it beforehands you don't lose as much time?

regal spoke
#

Ye it definitely isnt as good as compiling, but many times it is faster than not using a JIT

regal spoke
stiff quartz
regal spoke
#

It isn't like your orignal submission was wrong

stiff quartz
#

With a DFS?

#

Oh, with the bootstrap thing

#

Yeh, I saw it but I thought it might be interesting to learn how to do it iteratively

regal spoke
#

boostrap is a funny invention of mine, I find it very useful

#

You know how recursion uses a stack, right?

stiff quartz
#

Yep

#

first in first out

#

what you do is you make a stack object?

regal spoke
stiff quartz
#

Yeh I'm not sure I understand the code

#

I figured you had your own stack instead on relying on the one the recursive calls automatically make

#

So you store everything in an object?

haughty mountain
#

btw you can just do a print(*thing) to print space separated stuff

stiff quartz
haughty mountain
#

rather than the end hackery

#

that or a join

stiff quartz
#

damn clever

image.png
regal spoke
stiff quartz
#

Out of curiosity I've asked ChatGPT what it did

#

But didn't help too much

#

😆

regal spoke
#

Interesting, I've never tried asking chatgpt about it. Maybe you could try asking it to explain some code that uses bootstrap

#

!e

from types import GeneratorType
 
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        to = f(*args, **kwargs)
        while True:
            if type(to) is GeneratorType:
                stack.append(to)
                to = next(to)
            else:
                stack.pop()
                if not stack:
                    break
                to = stack[-1].send(to)
        return to
 
    return wrappedfunc

@bootstrap
def fib(n):
  if n <= 2:
    yield 1
  else:
    yield (yield fib(n - 1)) + (yield fib(n - 2))

print(fib(10))
halcyon plankBOT
#

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

55
stiff quartz
#

You can check the conversation I tried to have with it

#

But ngl, I do understand what you're trying to do

#

But not sure I understand each line of the bootstrap wrapper 😆

regal spoke
#

That is scarily accurate

#

The secret to understanding it is to know how generators work in Python

#

A function is a generator if it uses yield

#

You can interact with a generator by either using next or send.

#

send let's you send information back to the generator, so by using send the yield expression can have a return value

#

That is how something like this can make sense yield (yield fib(n - 1)) + (yield fib(n - 2))

stiff quartz
#

mmh

#

I understand yield and next

stiff quartz
regal spoke
stiff quartz
#

I'm trying to figure it out

#

oh the yield inside the generator

#

receives what the send sends?

regal spoke
stiff quartz
#

I hadn't understood previously

#

but that's pretty cool

regal spoke
#

!e

def adder():
  x = yield 0
  while 1:
    x += yield x

G = adder()
print(next(G))
print(G.send(5))
print(G.send(8))
halcyon plankBOT
#

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

001 | 0
002 | 5
003 | 13
stiff quartz
#

yep makes sense

#

I was gonna say i don't know when i would ever use that

#

but you obviously found a very interesting use case

haughty mountain
#

interesting/mildly cursed

haughty mountain
#

oh wait, it's more cursed than on first glance isn't it

regal spoke
haughty mountain
#

right, the first call does the while loop, everything else doesn't

#

makes sense

regal spoke
stiff quartz
#

So I tried doing the dfs thing

#

And I've been quite stupid

#

Cos my dfs function was recursive

regal spoke
stiff quartz
#

Yeh I wanted to try your idea because we didn't need like three objects holding the graph simultaneously (dag, reverse_dag and original_dag)

#

And no sets either

#

And the solution actually works perfectly on Python

regal spoke
stiff quartz
#

yeh for the remove i could've used an array of booleans to keep track right?

regal spoke
#

Well yes, but for the leaves approach you also need to keep a count of how many "live" parents a node has

stiff quartz
#

oh yes

#

i feel like it's defintely more of a brain teaser to go that way

regal spoke
#

I can see pros and cons for both methods

stiff quartz
#

Yeah the topological sort using dfs is a bit weird because you kind of launch dfs n times since there's no "initial root"

regal spoke
#

For example for identifying all strongly connected components

#

It might feel a bit weird, but it is also used in a ton of well known algorithms.

stiff quartz
# 
    for node in graph:
        # for each node in the graph, if it's not visited, run dfs on it
        if not visited[node]:
            dfs_stack.append(node)
            while dfs_stack:
                current_node = dfs_stack[-1]  # we don't pop yet, we only pop when everything "down" is visited
                if not visited[current_node]:
                    visited[current_node] = True
                    for neighbor in graph[current_node]:
                        if not visited[neighbor]:
                            dfs_stack.append(neighbor)
                else:
                    dfs_stack.pop()
                    stack.append(current_node)

Is that the right way to do topological sorting with dfs?

#

I feel like it's weird to not pop, add what's "dowstream", and only pop after

regal spoke
#

For the "pretraversal" I store the node index

#

And for the "posttraversal" I store the bit reversal of the node index

#

Like this

    for node in graph:
        # for each node in the graph, if it's not visited, run dfs on it
        if not visited[node]:
            dfs_stack.append(node)
            while dfs_stack:
                current_node = dfs_stack.pop()
                if current_node < 0: # Everything "down" has been visited
                    current_node = ~current_node
                    stack.append(current_node)
                elif not visited[current_node]:
                    visited[current_node] = True
                    dfs_stack.append(~current_node)
                    for neighbor in graph[current_node]:
                        if not visited[neighbor]:
                            dfs_stack.append(neighbor)
stiff quartz
#

I see

#

I didn't know about the bit reversal operator

#

you reverse the sign bit is that why you do if current_node < 0?

#

to know if it's pretraversal or posttraversal?

regal spoke
#

Bit reversal of x is exactly the same as -x - 1. So 0 is mapped to -1. And ~~x is x.

stiff quartz
#

oh yeah fair

regal spoke
#

!e

A = [2,6,7,8]
print(A[2])
A.reverse()
print(A[~2])
halcyon plankBOT
#

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

001 | 7
002 | 7
stiff quartz
#

!e

A = [2,6,7,8,9,10]
print(A[2])
A.reverse()
print(A[~2])
halcyon plankBOT
#

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

001 | 7
002 | 7
stiff quartz
#

ngl I'm a bit confused

regal spoke
#

All ~x is, is -x - 1

#

Which turns out to be really nice for indexing lists in reverse

stiff quartz
#

This was verified with my Python console but I can't wrap my mind around the mathematical proof behind it

#

I get that the first bit is probably the sign

regal spoke
stiff quartz
#

Oh

#

Well if you flip all the bits how can it become negative

regal spoke
#

Infinite 1s in binary is -1.

#

Infinite 0s in binary is 0.

#

!e

print(5 & -1)
halcyon plankBOT
#

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

5
regal spoke
#

The result of the bit AND between 5 and -1 is 5 since -1 is simply infinitely many 1s. In fact, the bit AND between any number and -1 is itself.

mortal rapids
#

hm

whole dune
regal spoke
#

Maybe I should have said there is no single sign bit

stiff quartz
whole dune
#

Except it's kind of implicit within two's complement

stiff quartz
#

But not sure I guess the link with why ~x is -x-1

#

Oh that's what it does?

image.png
regal spoke
stiff quartz
#

!e

print(2)
print(~2)

A = [2,6,7]
print(A[2])
A.reverse()
print(A[~2])
halcyon plankBOT
#

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

001 | 2
002 | -3
003 | 7
004 | 7
stiff quartz
#

fair fair

regal spoke
#

I'm not personally a big fan of using A[-1] to find the last element in A. I personally much rather use A[~0]. I think It is very nice and symmetrical to use A[0] to find the first element, and A[~0] to find the last element.

stiff quartz
#

!e

A = [2,6,7,8,9,10]
B = A[::-1]
print(A, B)
for k in range(len(A)):
    print(A[k])
    print(B[~k])
halcyon plankBOT
#

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

001 | [2, 6, 7, 8, 9, 10] [10, 9, 8, 7, 6, 2]
002 | 2
003 | 2
004 | 6
005 | 6
006 | 7
007 | 7
008 | 8
009 | 8
010 | 9
011 | 9
... (truncated - too many lines)

Full output: https://paste.pythondiscord.com/ONE4T36QFGPUOINKQ6TZ3XLBYE

stiff quartz
#

soo 💀

#

thank you so much btw for your patience

#

and your help!

#

I defintely learned a lot

haughty mountain
#

twos complement

regal spoke
sage flame
#

in the solution ``` def numOfSubarrays(self, nums):
E,O,T = 0,0,0
sum1 = 0
for num in nums:
sum1 = (sum1+num)%2
if sum1:
T=T+1+E
else:
T+=O
if sum1:
O+=1
else:
E+=1
return T % (10 ** 9 + 7)

#

I don't get why we are doing if the sum is odd we add even counts and if summ is even we add odd counts

#

don't understand the reasoning behind it

sonic dagger
# sage flame don't understand the reasoning behind it

It's easier if you think about it recursively:
Let's call x1 x2 x3... xp your array
The sums of subarrays x1, x1+x2... are written s1 s2... sp
Assuming we already know the number of subarrays with odd sum until p-1 as T.
The new subarrays to check are x1 x2... xp, x2... xp,... Basically the xi:p.
sp = si + xi+1...p for all i.
Or xi+1...p = sp - si.

If sp is odd(sum1), the subarray i+1:p has an odd sum if and only if si is even. You add the number of even si to T.
If sp is even, that subarray i+1:p has an odd sum if and only if si is odd. You add the number of odd si to T.
In the case where sp is odd, you add one for the full array.

fiery cosmos
#

hi

stiff quartz
halcyon plankBOT
#

:incoming_envelope: :ok_hand: applied timeout to @halcyon anvil until <t:1691146349:f> (10 minutes) (reason: duplicates spam - sent 4 duplicate messages).

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

pale copper
#

hi, not exactly sure what channel to put this in but I thought this would be the most fitting. I'm working on a cryptology project that uses a Ceaser cipher model which means I have to shift letters by numbers and I thought using ASCII would work well for this but I'm having some trouble figuring out how to get the letters to their ASCII numbers. would appreciat help!

sonic dagger
pale copper
sonic dagger
#

It gives you the index of the substring(here a character for instance b) in the string you use it on

#

For instance "abc".index("b") returns 1

pale copper
#

oh ok

#

thank you!

regal spoke
#

!e

print(ord('S'))
print(chr(ord('S')))
halcyon plankBOT
#

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

001 | 83
002 | S
regal spoke
#

ord takes in a character and outputs its ascii value. chr does the opposite, it takes the ascii value and outputs the character it corresponds to

haughty mountain
#

in general unicode codepoint, not ascii value

scarlet jolt
#

@woven blaze
I knoweth not where to contact thee so this help channel might work.
#1137377803877228655 message
I tried: if event.type==pygame.K_ESCAPE and event.type==pygame.KEYDOWN:.
To conclude again: I want to stop the last time.sleep(1.0) run when the rabota becomes false because now it waits for the sleep that is already running to finish and executes its functions, while everything else stops, closes right away. And I want to use a specific hotkey rather than any, since we made hotkey to be working so I am going one step further because I can.

woven blaze
#

@scarlet jolt

scarlet jolt
brazen python
#

are there any books you guys would recommend for learning the foundamentals of algos and DS in Python (and other languages)?

scarlet jolt
tame bear
#

huh

#

why ping me?

scarlet jolt
#

You were on this problem a few minutes ago.

sonic dagger
brazen python
sonic dagger
#

I didn't buy it personally

brazen python
#

migh as well just look for the pdf online...

#

thnx anyways

#

that was fast, thanks

#

for some reason it dosent work in Italy

#

perhaps they restric the country? it says: This site can’t be reached with 'DNS_PROBE_FINISHED_NXDOMAIN'

woven blaze
#

oops

brazen python
#

I should try with a VPN

#

thanks tho

woven blaze
scarlet jolt
scarlet jolt
woven blaze
scarlet jolt
woven blaze
#

but i don't have it rn

scarlet jolt
woven blaze
#

did you try that what's the issue?

#

are you getting the keyevent now?

scarlet jolt
#

That is the issue! Man, what art thou tripping?! I literally repeat the same thing over and over again, as clear and as simple as it could be! It is not possible for me to say this any better! Ic thanke thee. It is better for us to leave, goodbye!

woven blaze
#

sorry i just forgot the context

scarlet jolt
# woven blaze sorry i just forgot the context

Ah. Well. I do not know. It is all linked there. And Discord is messed up, does not allow me to make a thread. For not to insult thee, here is the problem yet again.

import time
import pygame
from threading import Thread
Rabota=True
pygame.init()
window=pygame.display.set_mode((200,150))
def my_function():
 while Rabota:
  time.sleep(5.0)
  print("Every second.")
my_thread = Thread(target=my_function)
my_thread.start()
while Rabota:
 for event in pygame.event.get():
  if event.type==pygame.KEYDOWN:
   print("Hotkey.")
   Rabota=False
pygame.quit()
# PyGame is used somewhere else in the code, not important.
my_thread.join

I would like hotkey to be specific rather than any, and sleep of threading to break on when Boolean - Rabota turns to "False" rather than waiting to finish the thread it already started (the ongoing thread).

woven blaze
#

okay thanks give me a second will download pygame and try that out

scarlet jolt
woven blaze
#

no need will do that

scarlet jolt
#

I do not know, the hotkey does not work without a Screen, which I have but the code is not important, thou can probably make it.

#

Just needs a four more lines than I originaly provided. And I updated the code to include them. This is the lines that go into that code up above.

import pygame
pygame.init()
window=pygame.display.set_mode((200,150))
pygame.quit()
woven blaze
# 
import time
from threading import Thread, Event
import pygame

Rabota = True

pygame.init()

my_event = Event()


def my_function():
    my_event.clear()
    print("my event: ", my_event.is_set())
    while not my_event.is_set():
        time.sleep(1)
        print("Every second.")


my_thread = Thread(target=my_function)
my_thread.start()
window = pygame.display.set_mode((200, 150))
while Rabota:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:  # Usually wise to be able to close your program.
            print("riased quit event")
            my_event.set()
            raise SystemExit

        elif event.type == pygame.KEYDOWN:
            print("key down event")
            print(event.key)
            if event.key == 1073742050:
                print("got the vent")
                Rabota = False
                my_event.set()

pygame.quit()
# PyGame is used somewhere else in the code, not important.

try this i've tested working for me

#

@scarlet jolt

scarlet jolt
woven blaze
#

escape?

#

press and see what event you're getting
i thiink events are based on the ascii

scarlet jolt
#

Because nothing happens when I press any hotkey.

woven blaze
#

did you get "key down event" in log?

scarlet jolt
#

And where dost thou set Rabota to be False, is that not useful? No, I do not get that text Printed. Maybe I made it wrong.

woven blaze
#

yes we don't need that rabota if you want you can set it

#

can you send me screenshot of the log and keypress part ?

scarlet jolt
#

Thou (you) never use events variable?

woven blaze
#

yes i didn't just for testing i've added that

scarlet jolt
woven blaze
#

and that while part?

#

sorry key press part?

scarlet jolt
#

Nothing.

#

I have this:

while Rabota:
 for event in pygame.event.get():
  if event.type==pygame.QUIT:
   print("riased quit event")
   my_event.set()
   raise SystemExit
  if event.type==pygame.KEYDOWN:
   print("key down event")
   print(event.key)
   if event.key == 27:
      print("got the vent")
      my_event.set()
woven blaze
#

press it multiple times i think doesn't detect?

scarlet jolt
#

Works now.

#

And also, you had elif and I just if.

woven blaze
#

that's not required yours is also correct

woven blaze
scarlet jolt
#

"key down event
1073742050"

woven blaze
#

1073742050
add it in that if condition

scarlet jolt
#

It is weird and yes there are issues but I do not know how to say.

woven blaze
#

inplace of 27

woven blaze
scarlet jolt
#

I can not, it is complicated, the thing does not close.

#

Just stops printing. Why do we not use Rabota?

woven blaze
#

is it required?

scarlet jolt
#

And it does not break the loop, everything is the same but with another issue.

#

I use it as a loop, ikt is important.

#

I am going back to the beginning.

woven blaze
#

ooh yes i forgot you can set it to false after that keyevent
give me a second

#

Modified that please check

scarlet jolt
#

I removed everything, I need to make it again.

woven blaze
#

oops

scarlet jolt
#

How can it work for thee I do not udnerstand.

#

And that event thing you imported and used is confusing anyway.

woven blaze
#

Ooh but it's working for me
can you test just that part insted of directly integrating with existing code?

scarlet jolt
#

I do not know how to because Pycharm is extremely messy.

#

I will not attempt that.

#

Stupid software.

#

I can not believe how stupid it is.

#

I got thousands of files every time I oppen it and everything is hidden and weird.

woven blaze
#

No no pycharm is not messy it depends on the user

scarlet jolt
#

I tested and seems like it fixes the hotkey, it works, although seems not works always and instant, and seems like the other part where loop is supposed to break and sleeping not to work is the same, it still prints after.

#

No way, this is truly it, I give up. Ic thanke thee very much!

#

Nonsense this Python is! Cna not fix the simplex thing.

woven blaze
scarlet jolt
#

We tried. We can not make it.

#

What can we do? There is no way.

#

I said I spend days and weeks on this.

woven blaze
#

okay try something else

scarlet jolt
#

Yes, but not related to this. This is done, proven to be impossible.

#

Goodbye!

#

This is the last day I was patient with this bugged nonsense.

summer fossil
#

I don't know why it is not working

#

can u plz rewrite correct code for me

#

I am busy for some days nows i am starting again

regal spoke
#

Did you submit it to some website and got wrong answer?

#

Or like, why do you think it is wrong

summer fossil
rich apex
#

Is there anyway to optimize the selection sort just like in bubble sort where if there are no swaps done, then the array is sorted

regal spoke
rich apex
regal spoke
#

I think the only O(n^2) sorting algorithm that has some interesting algorithmic uses is insert sort

rich apex
#

How so?

regal spoke
#

Part of the reason for this is that the "expensive" insert step is in practice super cheap cause it just shifts stuff around in memory

rich apex
#

I think for an array you need to move all the elements to the right

#

I think it is expensive

#

in case of insertion sort

regal spoke
#

But moving stuff around in memory like that is one of the things that a computer has been optimized to do

rich apex
#

I see

regal spoke
#

Another nice thing about it is that you can access this super fast insert in Python just by doing .insert on a list

rich apex
#

Yeah cause of linked list right?

regal spoke
rich apex
regal spoke
#

It is still O(n) to do an insert

#

But it has a very small constant cost

rich apex
#

But the swap takes less time than insertion right?

regal spoke
rich apex
regal spoke
#

Or what do you mean by swap?

vocal gorge
#

swapping two elements takes constant time, unlike insertion, but it's not very valid to say that it means it's faster.

rich apex
regal spoke
#

One swap is definitely cheaper than an insert

#

But an insert is still remarkably cheap for what it is

rich apex
#

Maybe

#

I'm still new to all of this DSA thing

regal spoke
#

I've tried implementing and benchmarked tons of Python implementations of balanced binary trees that can be used to mantain sorted data

#

It turns out that data structures based on insert sort are simply faster, even when n becomes rather huge (like 1e7)

rich apex
regal spoke
#

They work in the same way as vector does in C++

rich apex
#

Looks like I have to revisit some basic concepts

regal spoke
#

Lists in Python allocate more memory than they intitally need, in order for .append to run quickly

#

And then when that memory becomes filled, it reallocates (again with some extra memory to make .append run quickly)

haughty mountain
vocal gorge
halcyon plankBOT
#

Objects/listobject.c lines 68 to 72

 * The growth pattern is:  0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
 * Note: new_allocated won't overflow because the largest possible value
 *       is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
 */
new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;```
vocal gorge
#

which I note is actually quite slow growth (powers of 9/8), I think a common implementation in programming languages is to double in size each time.

haughty mountain
#

there has been plenty of arguments about what's the optimal factor

regal spoke
vocal gorge
#

hmm, this is for C++'s std::vector, right?

regal spoke
#

ye

vocal gorge
regal spoke
#

Btw another thing to note about insert sort. Suppose you are sorting up to 256 elements, then you can keep track of the sorted permutation using only 1 byte per element.

#

This can be used to further cut down the cost of the insert step in insert sort

regal spoke
outer rain
#

still double even if you only need one additional element or allocate as little as they need?

regal spoke
outer rain
#

ok, makes sense

regal spoke
#

But I'm not sure about c++

outer rain
#

It's just that I just realized that I have re-implement vector multiple times and upon resize I always (re)allocate max(capacity, new_size)

#

never though about it working in O(n^2)

regal spoke
#

realloc() works in mysterious ways

outer rain
#

Interesting

oak jewel
#

has anyone here solved programming problems from the euler project?

outer rain
#

I would expect resizes take long time only at the memory page boundaries though

#

(well, depends on the allocator implementation I suppose)

vocal gorge
#

That's just an ordinary linked list though, isn't it?

#

oh, you mean, like, have empty nodes at the end? I don't see why though; that just gets you extra memory usage without changing complexity

outer rain
#

Argh, linked list

#

the most overhyped and overused data structure ever

#

useful literally never

#

and still taught as if it is a holy grail of programming

vocal gorge
#

ehh, used sometimes in heavily modified forms

#

e.g. python's collections.deque

outer rain
#

it is used either:

  1. To ensure the memory location of an object does not change (why don't use std::deque's structure in that case though? Or even vector of pointers?)
  2. In hashmaps (or other structures) to store the information about element order
  3. When O(1) merge time is needed
  4. In concurrent data structures
  5. In low level (think OS development) fields where allocation is difficult
#

I don't know any other usecases

regal spoke
#

C++ std::deque is an interesting alternative to vector. It avoid reallocations by allocating its memory in blocks of like 16 elements each, and then having a lookup table for pointers to the blocks. Its time complexity is at least as good as vector for any operation.
No reallocations also means that pointers arent invalidated, unlike for pointers to elements in a vector.

outer rain
#

cyclical vector has better performance

regal spoke
outer rain
#

yes, but I you benchmark it against simple looped vector, the latter will crush it

regal spoke
#

Its real fail is that MSVC has a shit implementation of deque only allocating "blocks" of 1 element. So depending on your system you can have really bad performance

outer rain
#

that's even worse

regal spoke
#

Btw, many of the times I've seen people use std::deque it was used because its pointers dont get invalidated, and because its a double ended queue

outer rain
#

yeah people do that

#

it's technically more memory efficient than allocating memory for every object

#

but still less memory efficient than memory arenas thingy

regal spoke
#

I recall reading a proposal for a better "vector" in C++, but unfortunately I dont think that ever became a thing

outer rain
#

what would that be?

#

I mean, how they plan to improve vector?

regal spoke
#

Let me see if I can find it somewhere

outer rain
#

I don't see anything surprising about it

#

just an average "sqrt-decomposed" data structure

#

but seeing it in the context of deque implementation is interesting

summer fossil
#

Nope direct on gfg

regal spoke
summer fossil
# 
#User function Template for python3

from typing import List
from queue import Queue
class Solution:
    #Function to return Breadth First Traversal of given graph.
    def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
        visited = [False]*V
        bfs = [0]
        visited[0] = True
        for u in bfs:
            for v in adj[u]:
                if not visited[v]:
                    visited[v] = True
                    bfs.append(v)
        return bfs
```It's work
#

Well some website has different dfs article and some have different dfs I am confused!

regal spoke
#

BFS and DFS are two different things. The problem you linked and the code you posted is BFS

summer fossil
#

In my soln. I am also using queue for bfs

#

GFG Sucks but leetcode has no problem for calculating dfs/bfs of graph

regal spoke
brazen python
#

are there any examples of recursive generators that are used in BFS style instead of DFS?

#

and is it even possible to do the former with generator-functions?

regal spoke
#

I've never heard of anything like that before

brazen python
#

which is more eficcient, because if dont need all the nodes, but maybe just the first 5, the generator will stop there.

#

so I did this which is actually for a trie data structure, but it uses DFS instead of BFS

# TrieDict: TypeAlias = dict[str | bool, 'TrieDict' | str]

def extract_keywords_from_trie(trie: TrieDict) -> Iterator[str]:
    for key, val in trie.items():
        # if the key is true the value will be the keyword
        if key is True:
            yield val
        elif isinstance(val, dict):
            yield from extract_keywords_from_trie(trie=val)
#

but I'm trying to convert it to a BFS algorithm so it explores the nodes level by level

regal spoke
#

BFS doesn't use any recursion to begin with, so you can just yield whenever you append something to the queue

brazen python
#

I came up with these two solutions that seem to work

def extract_keywords_from_trie(trie: TrieDict) -> Iterator[str]:
    nodes = deque([trie])
    while nodes:

        current_node = nodes.popleft()
        for key, val in current_node.items():
            if key is True:
                yield val
            elif isinstance(val, dict):
                nodes.append(val)


def extract_keywords_from_trie_bfs(trie: TrieDict) -> Iterator[str]:
    next_level = []
    for key, val in trie.items():
        if key is True:
            yield val
        elif isinstance(val, dict):
            next_level.append(val)

    for node in next_level:
        yield from extract_keywords_from_trie(trie=node)
regal spoke
#

Another thing that I personally prefer is to BFS by just for looping over a list like this ```py
nodes = [trie]
for current_node in nodes:
for key, val in current_node.items():
if key is True:
yield val
elif isinstance(val, dict):
nodes.append(val)

#

You dont technically need any deque

brazen python
regal spoke
#

😄

brazen python
#

right

#

its not a syntax error, but still very bad practice

#

and the deque is the same as the list, its just more performant for popping the first element

regal spoke
lean walrus
brazen python
#

!e

lst = [1, 2]
for x in lst:
    lst.append(x)
halcyon plankBOT
#

@brazen python :warning: Your 3.11 eval job timed out or ran out of memory.

[No output]
brazen python
regal spoke
#

With deque you could also accidently fill up the memory by getting stuck in some infinite loop

lean walrus
#

!e ```py
l = [*range(10)]
for x in l:
print(x)
del l[0]
print(l)

halcyon plankBOT
#

@lean walrus :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | 0
002 | 2
003 | 4
004 | 6
005 | 8
006 | [5, 6, 7, 8, 9]
lean walrus
#

That's why it is bad

brazen python
#

I agree

regal spoke
#

Well I dont

brazen python
#

besides, in general you always want to avoid reading and writing at the same time

regal spoke
#

When you iterate over an list Python internally has an index that increments by 1 over and over

#

Thats all it is

lean walrus
#

for loops in python usually mean "do some stuff with every item of this collection"
Code like this is extremely obscure and hard to read, that's why i think it is bad

regal spoke
#

I agree that it is obscure

#

But it is a pretty useful feature

lean walrus
#

If you do write loop like this, consider leaving good explanation comment before it

regal spoke
#

As with anything obscure, if you want someone to be able to read your code and understand it, then it is bad

brazen python
#

lol

regal spoke
#

If you want something less obscure you could just manually do the indexing yourself

# 
    i = 0
    nodes = [trie]
    while i < len(nodes):    
        current_node = nodes[i]
        for key, val in current_node.items():
            if key is True:
                yield val
            elif isinstance(val, dict):
                nodes.append(val)
        i += 1
#

It is fundamentally the exact same thing

# 
Code that modifies a collection while iterating over that same collection can be tricky to get right. Instead, it is usually more straight-forward to loop over a copy of the collection or to create a new collection:
regal spoke
#

You cant just mix BFS and recursion like that

#

In a BFS, you need to do everything in parallell

#

As you've coded it now, you will start the 3rd layer before you are finished with the 2nd layer

brazen python
#

you can do both BFS and DFS, both iteratively, and also recursively

regal spoke
brazen python
#

aight if you say so 😂

regal spoke
#

This is an example of a graph where you'd get the wrong order

image.png
#

You would get to the node in the bottom left before reaching the node in the bottom right

#

Speaking about obscure code. A fun obscurity test is to show a Python code to chatgpt and ask it to translate it to C++.

#

However, it is less successful with something like this ```py
B = [0] * len(A)
for i in range(len(A)):
B[i] = A[-i]

haughty mountain
#

!e

from collections import deque
from typing import Iterator

TrieDict = dict

def extract_keywords_from_trie(trie: TrieDict) -> Iterator[str]:
    nodes = deque([trie])
    while nodes:
        current_node = nodes.popleft()
        for key, val in current_node.items():
            if key is True:
                yield val
            elif isinstance(val, dict):
                nodes.append(val)


def extract_keywords_from_trie_bfs(trie: TrieDict) -> Iterator[str]:
    next_level = []
    for key, val in trie.items():
        if key is True:
            yield val
        elif isinstance(val, dict):
            next_level.append(val)

    for node in next_level:
        yield from extract_keywords_from_trie(trie=node)

t = {
    'a': {
      True: 'a',
      'b': { True: 'ab' }
    },
    'c': {
      True: 'c',
      'd': { True: 'cd' }
    },
}

for x in extract_keywords_from_trie_bfs(t):
  print(x)
halcyon plankBOT
#

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

001 | a
002 | ab
003 | c
004 | cd
haughty mountain
#

a bfs order would start with a and b before getting to ab and cd

brazen python
#

the two functions are separate, its just a typo that one calls the other

#

so the first works

#

but the second ironically does the opposite

regal spoke
brazen python
steady hearth
#

im having a problem in which i can't reach a variable.
the variable is located at a function and i'm trying to reach it in a function that is inside of the parent function but cannot. any suggestions?

regal spoke
steady hearth
#

thanks

summer fossil
outer rain
#

I hate to say it, but you can ask chatgpt to translate it 😅

#

It is one thing it is relatively ok at

#

I'm sure it will understand basic java

#

But also I recommend you to try and understand java yourself

#

You don't have to know the language to understand it

fiery cosmos
#

haven't been here in a while

urban hill
#

Is there any good introductory course available for dsa in python? Im new to dsa and am looking to explore the field

robust needle
#

Hi, I'm doing a backtracking algorithm for the knight's tour problem. My current solution works, but I feel like there's ways to optimize it.

# 
def board_filled(n,board):
    for i in range(n):
        for j in range(n):
            if board[i][j] == 0:
                return False
    return True

def knights_tour(n):
    board = [[0 for i in range(n)] for j in range(n)]
    backtrack([(0,0)],1,n,board)
    for i in board:
         print(i)

def backtrack(sols:list,counter,n,board):
    possible_moves = [(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1)]
    prev_x,prev_y = sols[len(sols)-1]
    if board_filled(n,board):
        return sols
    if (prev_x) not in range(n) or (prev_y) not in range(n) or board[prev_x][prev_y] != 0:
        sols.pop()
        return False
    board[prev_x][prev_y] = counter
    for (x,y) in possible_moves:
                sols.append((x+prev_x,y+prev_y))
                if backtrack(sols,counter+1,n,board):
                    return True
    board[prev_x][prev_y] = 0
    sols.pop()
    return False

knights_tour(5)
#

mainly any ways to optimise the backtrack() function would be appreciated

haughty mountain
#

why?

#

or wait, you deal with that in the beginning of the call

robust needle
#

yeah i kill the function if the square it wants to go has been occupied

#

though maybe i could just not let it call it in the first place

haughty mountain
#

if so why do you need to check the board_filled like that?

robust needle
#

oh right

#

if counter = n*n it should work right? because the only way counter reaches that if it's successful

haughty mountain
#

something like that yeah

robust needle
#

i mainly just wanted to check the general structre

haughty mountain
#

might be + 1

robust needle
#

i'm a bit unsure on how a 'general backtracking' algorithm looks like

#

google search hasn't helped me much

haughty mountain
#

depending on your indexing with counter

robust needle
#

yeah but i mean like for any problem involving backtracking

#

right now i'm basically using this template i came up with

#

but i don't know if it's the best way to do it

#

because right now the only way my implementation works is because return attempt is evaulated as true

#

sorry it might be a bit of a loaded question

#

if you can direct me to any resources i'd be happy to just check them

haughty mountain
#

it's just this kind of pattern:

for all options:
  update state with option
  try to recurse
  if successful:
    return with success
  else:
    undo update
#

with the undoing of the update to avoid discarding all the prior work

robust needle
#

what does 'try to recurse' mean here?

haughty mountain
#

"does picking this option next work"

#

which usually is a recursive call to your function

robust needle
#

right but my problem is this

#

say one of the calls do work

#

it will return sucess, (with the solution)

#

but then that return is just basically...gone?

#

idk how to explain it properly

#

like if the succesful function returns success, it's meaningless since i need it's parent functions to pass that value to the initial function (the one that started the recursion)

#

and the only way i managed to do that is

sol =backtrack(solution + i):
if sol:
  return sol
#

so like if anytime one of the functions returns, say an array that passed all constraints

#

then the function that called it will 'pass it down'

haughty mountain
#

it's a bit awkward wrt data flow yes

robust needle
#

i guess i'll just stick with what i have since it seems to work

#

and you know what they say don't touch it if it works

haughty mountain
#

I like using closures for this, e.g. here is one that would output all solutions

def all_solutions(...):
  sols = []
  def backtrack(...):
    if this is solution:
      sols.append(...)
      return True
    for all valid options:
      update state
      backtrack(...)
      undo update
  backtrack(...)
  return sols
#

you could probably make a generator function work instead actually, which might be neat

robust needle
#

are both the backtrack calls the same? or are the arguements different?

#

i'm relatively new to python syntax so what does 'all' mean here?

haughty mountain
#

something like this with a generator

def backtrack(...):
  if this is solution:
    yield solution
    return
  for all valid options:
    update state
    yield from backtrack(...)
    undo update
haughty mountain
robust needle
#

oh okay lol

haughty mountain
robust needle
#

does puting a def inside another function definition mean that sols is accesbile to it?

#

like i don't need to pass sols as a function parameter?

#

but honestly thank you very much for clarifying this for me

#

this backtracking stuff is messing with my head

#

so tysm

haughty mountain
#

here is an example using generator functions to generate all solutions lazily, this finds partitions of a number, i.e. unique ways of adding up to some number

#

!e

def gen_partitions(n, max_allowed, picked):
  if n < 0:
    return
  if n == 0:
    yield picked
    return
  for i in range(1, max_allowed+1):
    picked.append(i)
    yield from gen_partitions(n - i, i, picked)
    picked.pop()

def partitions(n):
  return gen_partitions(n, n, [])

for p in partitions(5):
  print(p)
halcyon plankBOT
#

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

001 | [1, 1, 1, 1, 1]
002 | [2, 1, 1, 1]
003 | [2, 2, 1]
004 | [3, 1, 1]
005 | [3, 2]
006 | [4, 1]
007 | [5]
haughty mountain
#

and you could easily just pick the first solution from this and you wouldn't even compute the rest

#

you should be able to see the same patterns as before

halcyon plankBOT
#
Sequence slicing

Slicing is a way of accessing a part of a sequence by specifying a start, stop, and step. As with normal indexing, negative numbers can be used to count backwards.

Examples

>>> letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
>>> letters[2:]  # from element 2 to the end
['c', 'd', 'e', 'f', 'g']
>>> letters[:4]  # up to element 4
['a', 'b', 'c', 'd']
>>> letters[3:5]  # elements 3 and 4 -- the right bound is not included
['d', 'e']
>>> letters[2:-1:2]  # Every other element between 2 and the last
['c', 'e']
>>> letters[::-1]  # The whole list in reverse
['g', 'f', 'e', 'd', 'c', 'b', 'a']
>>> words = "Hello world!"
>>> words[2:7]  # Strings are also sequences
"llo w"
wooden belfry
#

Hello, I have written some code to sample m number of pauli strings (without replacement). But its super inefficient.

#Inefficient implementation (Possibly make it better?, ok for proof of concept?)
def create_random_pauli_strings(num_qubits, num_basis, seed):
    pauli_chars = ["I", "X", "Y", "Z"]
    all_pauli_strings = list(product(*([pauli_chars] * num_qubits)))
    all_pauli_strings.remove(tuple(["I"] * num_qubits)) #Remove identity
    
    random.seed(seed)
    random_pauli_strings = random.sample(all_pauli_strings, k=num_basis)

    random_pauli_strings = list(map(lambda x : "".join(x), random_pauli_strings))
    
    return random_pauli_strings

Right now I am expanding every single possible cartesian product of I,X,Y, and Z and sampling them. For instance if num_qubits is 2, all_pauli_strings will expand to [IX, IY, IZ, XX, XY, XZ, ...] (the length of the list will be 15). Then lets say m is 3, so I will sample XX, YY, and ZI (you cannot repeat any of the strings).

This code is particullary bad beause the length of all_pauli_stings will expand exponentially, the length will be in fact 2 ** (2 * num_qubits) - 1

Any ideas of how I can achieve this without having a gigantic list?

vocal gorge
#

Anyway, seems that you want to sample some random elements from a cartesian product. That's definitely possible, because you can enumerate a cartesian product in an intuitive way:

let's say we consider product("ab", repeat=2)

n element
0 aa
1 ab
2 ba
3 bb

This is just n written in base-2, with 0 replaced by a and 1 by b.

Whereas if you have product("abc", repeat=2), that'd be like writing the number in base-3 and replacing 012 with abc respectively.
#

So just generate num_basis integers from 1 to 2**num_qubits - 1 inclusive, and transform them into the actual elements this way.

wooden belfry
#

But there's actually 4 elements

#

I, X, Y and Z

vocal gorge
#

base-4, then.

wooden belfry
#

Yep

#

Oh I see what ur saying

#

That is a def a much clever way of doing it

#

So num qubits is just gonna detemine length of my bitstring

#

Or I guess 4base string

#

Thank you @vocal gorge !

vocal gorge
# wooden belfry So num qubits is just gonna detemine length of my bitstring

Yeah, something like:

def product_nth(iterables, n: int):
    "Returns the nth element of product(*iterables)"
    res = []
    for i in range(len(iterables) - 1, -1, -1):
        n, mod = divmod(n, len(iterables[i]))
        res.append(iterables[i][mod])
    return tuple(res[::-1])

def create_random_pauli_strings(num_qubits, num_basis, seed):
    pauli_chars = ("I", "X", "Y", "Z")
    random.seed(seed)
    random_ns = random.sample(range(1, 4**num_qubits), k=num_basis)
    return [product_nth([pauli_chars] * num_qubits, n) for n in random_ns]
#

(This approach might also be vectorizable with numpy, if more performance is desired.)

jovial briar
#

cool

haughty mountain
#

~1s for generating 100M nucleotides

vocal gorge
#

that makes it much more problematic. Could use an approach like in my python version though, just vectorized. Would be fast-ish.

regal spoke
wooden belfry
#

Yes, because in my case the II.. string is invalid

#

I shouldvw mentioned that

regal spoke
wooden belfry
#

The idea is that in theory it should be efficient

#

In practice not really because we are prolly not gonna use anything more than 3 or 4

#

But the idea of converting it into base 4 should work

regal spoke
#

3 or 4 what?

wooden belfry
wooden belfry
regal spoke
#

What about just sampling a random 5qbit string and cutting it down to 4 qbits?

wooden belfry
#

But in theory it should be efficient for any number of qubits :)

#

Even 10 is an insane number of strings

regal spoke
#

10 is not that insane

#

but 5 is more reasonable

wooden belfry
#

It's still an exponential algorithm is what I'm trying to say

regal spoke
wooden belfry
#

? How so

regal spoke
#

for a random 22 long qbit string, I would sample five random 5 long qbit strings

#

remove the last 3 qbits from the last sample

#

and concatenate them

wooden belfry
#

Not sure if I follow, I still think that the solution confuses reptile stated is the best

#

It's essentially constant time

#

Or actually linear

regal spoke
#

Every approach will be linear

#

However, I'm not sure what will be the bottleneck

haughty mountain
#

!e I have a really terrible numpy thing

import numpy as np
import random

n = 10
k = 8

r = np.array(random.sample(range(1, 4**n), k), dtype=int)

n_range = np.arange(n, dtype=int).reshape((n, 1))
indices = r >> 2*n_range & 3
elements = np.frombuffer(b'IXYX', dtype=np.uint8)
ascii_arr = np.take(elements, indices)
res = np.frombuffer(ascii_arr.tobytes(), dtype=np.dtype(f'S{n}'))
print(res)
halcyon plankBOT
#

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

001 | [b'XXXXIYXYYI' b'XYIXXXXIXI' b'XXIYYXXXYX' b'IIXIYYIXYX' b'YIYIYXXXYX'
002 |  b'XXXYXYIXII' b'YXYXYXYIIX' b'XIIIYIXXIY']
vocal gorge
#

np.array(random.sample can be a np.random.randint with replace=False

#

now, what is happening here... oh, I get it. yeah, that's about what I had in mind for vectorization.

haughty mountain
#

it's a bit awkward

vocal gorge
#

is np.take(elements, indices) different from elements[indices]?

haughty mountain
#

and I think you can't get away from using int with this approach

#

err, good question

#

it's probably the same in this case

regal spoke
#

Btw I suspect the bottleneck might be the random.sample

haughty mountain
#

using the numpy version will be a lot quicker probably

#

though I suspect this is very premature optimization unless we expect to want to pick tons of elements

#

just doing the sane pure python version from earlier seems like a sane choice

#

also, if k is much smaller than 4**n rejection sampling could be a very good and simple option

#

!e something like this

import random

def random_pauli_str(n):
  return ''.join(random.choice('IXYX') for _ in range(n))

n = 10
k = 8

res = set()
while len(res) < k:
  s = random_pauli_str(n)
  if s != 'I'*n:
    res.add(s)

print(res)
halcyon plankBOT
#

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

{'IYIXYXYXYX', 'XXYYYXYXYI', 'YXIXIYXYYX', 'IYXXYIIXXX', 'IXXXXIXIIX', 'XIYIYYXXXY', 'XXXIXXYXII', 'YXXYIYXYXX'}
haughty mountain
#

hey, first try without test running

#

idk if this is really rejection sampling, but it feels a bit like it

vocal gorge
#

you forgot s not in res

haughty mountain
#

not needed

vocal gorge
#

oh, right

haughty mountain
#

I was about to write it before I realized it was a bit silly of a check when we have a set anyway

regal spoke
#

Could even add 1*n to set at the start and remove it at the end

#

and do <= in the while

haughty mountain
#

yeah, it's another option

regal spoke
#

@wooden belfry Do you actually want the sampling without replacement?

haughty mountain
#

from what was said earlier, yes

haughty mountain
regal spoke
#

Usually sampling without replacement just complicates things mathematically

wooden belfry
#

Yes I need to sample without replacement

#

No duplicates essentially

regal spoke
haughty mountain
lilac moat
#

Hi

odd mesa
#

Hi everyone, I'm currently working with opencv for computer vision and my problem is that I'd like to dilate or erode random parts of an image but not the entire image itself. Does someone know how it is possible to do that ? I'd greatly appreciate your help 🙂

mild dove
#

Hi, just for curiosity, when I'm coding an algorithm with multiple index and need to increment or decrement at the end or beginning of the code (pointer++ or i = start +1 in the code), is there any trick to remember, without iterate the code in my head or memorize the entire algorithm? sorry java code public static int[] quickSortRec(int start, int end, int[] list) { if(start < end) { int pivot = list[start]; int pointer = start; for (int i = start + 1; i <= end; i++) { if (list[i] < pivot) { pointer++; swap(pointer, i, list); } } swap(pointer, start, list); quickSortRec(start, pointer - 1, list); quickSortRec(pointer + 1, end, list); return list; } return list; }

haughty mountain
#

it's less memorizing and more understanding the algo

naive oak
#

I usually visualize an arbitrary array in my head with arrows as pointers

regal spoke
# mild dove Hi, just for curiosity, when I'm coding an algorithm with multiple index and nee...

I think what you have there is basically as good as it will get. It gets a bit tricky no matter how you code it.

My personal preference would be to code it like this.

int pivot = list[start];
++start; // ignore the pivot element for now
int j = start;
for (int i = start; i < end; ++i) {
    if (list[i] < pivot) {
        swap(i, j, list);
        ++j;
    }
}
swap(start - 1, j - 1, list); // place pivot at j - 1 (in the middle)
quickSortRec(start - 1, j - 1, list);
quickSortRec(j, end, list);
#

The reason I prefer coding quicksort like this is that the for loop part of the code becomes really nice, short and simple.
Also, I changed the code to use [start, end) instead of [start, end].

regal spoke
#

is there any trick to remember, without iterate the code in my head or memorize the entire algorithm?
When I implement an algorithm I try to break it down into steps. I view the quicksort as having 3 steps

  1. Choosing the pivot
int pivot = list[start];
++start; // ignore the pivot element for now
  1. Create the partitioning.
    Places everything < the pivot to the left, and everything >= the pivot to the right.
    The variable j marks the index to the first element >= pivot. If there is no element >= pivot, then j = end.
int j = start;
for (int i = start; i < end; ++i) {
    if (list[i] < pivot) {
        swap(i, j, list);
        ++j;
    }
}
  1. Place the pivot in the middle and recursively sort the two partitions
swap(start - 1, j - 1, list); // place pivot at j - 1 (in the middle)
quickSortRec(start - 1, j - 1, list);
quickSortRec(j, end, list);
#

One really nice thing about doing it like this is that step 2 doesn't depend on how you picked your pivot. Step 2 would look exactly the same if for example you picked the last element to be the pivot.

mild dove
#

yeah like I try to divide the code in steps and also visualize the array to check the corner cases, but my brain is not good to do that without errors, I need to review the code to check these cases and run the tests to validate 😢

regal spoke
regal spoke
#

Step 3 has a slightly awkward edge case (which happens if all elements were bigger than the pivot). In that case the pivot happens to get swapped with itself. But importantly that doesn't matter for the correctness of step 1 and 2

mild dove
#

hmm, okay I will try to think about that, to quick sort is just one case, but sometimess it is really dificult to visualize the algorithm. I thought maybe I can test a case with 1 element and 2 elements in my brain to simplify the validation 🤔, or try to code the algorithm and consider the corners at the end. idk

turbid valve
#

N

#

I

#

G

river vector
# 
    1. eg, business hours for a store are 9 AM to 12 PM on Monday
        1. we only have 2 observations for this store on a particular date (Monday) in our data at 10:14 AM and 11:15 AM
        2. we need to fill the entire business hours interval with uptime and downtime from these 2 observations based on some sane interpolation logic```
#

what would be best way to solve this
i can assume the store is active in it's active hours unless one entry says inactive

#

just looking for another pair of eyes

fiery cosmos
#

has anyone ever done a question called pow(x ,n) on leetcode its question 50 on it?

regal spoke
#

or use math.pow

cinder bronze
#

Can someone help me with a hangman problem

#

Can someone suggest what type of algorithms I can use to solve it

vocal gorge
#

You could get a decent-ish solver by just trying the most common letter among the possible guesses each time.

outer rain
haughty mountain
oak jewel
#

All the problem statements are given in the screenshots can anyone help me improve my code(im returning correct outputs only for a few cases, others are failing)

Screenshot_2023-08-11_002200.png Screenshot_2023-08-11_002253.png Screenshot_2023-08-11_002537.png
#

The argument to the function "sum_of_intervals" is an array of arrays FYI

manic urchin
#

Hi, I was recommended to use
base64.b64encode(os.urandom(32))[:8]
question is, isn't this the same thing?
base64.b64encode(os.urandom(6))
if run time was a factor, wouldn't the ladder code be better?

deep snow
#

hello, question, I found this website its like, an algorithm a day, and Im on one called Kadane's Algorithm, and it seems to be an algorithm for getting the sum of the array? why do that when you can just sum()?

# 
def solution(nums):
    start_time = time.time()
    maxCurrent = nums[0]
    maxGlobal = nums[0]
    for i,val in enumerate(nums):
        if i == 0:
            pass
        else:
            maxCurrent = max(val, maxCurrent + val)
            if maxCurrent > maxGlobal:
                maxGlobal = maxCurrent
        
    print ("My program took", time.time() - start_time, "to run")
    return maxGlobal

Thats the code for it and I dont quite understand what the benefit of something like this would be

snow anvil
deep snow
summer fossil
deep snow
#

so going through a list and doing sum += currentlistnum is o(n^2)?

summer fossil
#

U use only one for loop and iterate for n elements

deep snow
#

right, so why you kadane algorithm if just sum(list) does the same thing and even got me faster results

summer fossil
#

like [1,2,-4,-3]
sum of list is not working here

snow anvil
#

Sum(list) gives you the sum of the entire array not the subarray

summer fossil
deep snow
#

right which gives the same answer anyway?

snow anvil
#

No

summer fossil
#

and sum of array is not the right answer always

snow anvil
#

Did you read the website you sent?

summer fossil
deep snow
#

I did but I guess I dont understand it

#

in the end it seems like he's still just adding together every number in the array

snow anvil
#

Numbers that are after each other

#

Subarrays

deep snow
#

yeah idk im completely lost as to what the goal is

snow anvil
#

To find the subarray with the highest sum

#

Or the sum itself

deep snow
#

so the only time it wouldnt just return the sum of the full array is if the end numbers are negative?

#

like [2,4,2,-2,-5]

#

it would just return 8

snow anvil
#

What about [1,2,-3,4] what is the largest subarray sum here

deep snow
#

4

snow anvil
#

Yes

#

👍

deep snow
#

1 + 2 + -3 + 4

#

sum of the list

snow anvil
#

No

#

Okay

deep snow
#

xD

#

you see where im confused now xD?

snow anvil
#

[1,2,-3,5]

deep snow
#

5

snow anvil
#

Lol sure but you are doing it wrong [2,2,-3,5]

#

What is it for this one

deep snow
#

6

snow anvil
#

Nope it's 5

#

Subarrays are [2] or [2,2] or [5] or [-3,5]

#

Does that make it more clear?

deep snow
#

not at all

#

why cant it be [2,2,-3]

#

or [2,2,5]

snow anvil
#

That's one aswell

deep snow
#

so 9 is the maximum

snow anvil
#

Whoops sorry I'm not helpful rn

#

You have the right idea I was spewing nonsense let me give you a better example

#

[1,2,-4,5]

deep snow
#

using his code

snow anvil
#

I am a bit sleep deprived I apologize

deep snow
#

you're fine

#

im a bit stupid so xD

deep snow
snow anvil
#

Cuz it's not contiguous

#

5 follows -4 and not 2

#

So to include 5 you have to either have it by itself or include numbers previous to it

#

So in this case the max subarray is just [5]

deep snow
#

so in a case like, [1, 2, 3, -1, 7]

#

is it 7?

snow anvil
#

Well yes but that one is not very interesting imo

#

Nvm u right

deep snow
#

well i cant tihnk of anything else cuz I still dont see why sometimes it seems like its just the sum of the full array and sometimes not

snow anvil
#

Same concept

deep snow
#

[2, 1, -2, 3, 2]

#

in this one why isnt it 5

snow anvil
#

Cuz 2 + 1 - 2 > 0

deep snow
#

yeah idk im too stupid for this I guess, I appreciate you trying to help but I dont think ill be able to understand this

snow anvil
#

Its 6 - 1 + 7

deep snow
#

yeah see its the full sum

#

idk

#

i cant

snow anvil
deep snow
#

no you're fine

#

I just genuinely cant see the difference between these arrays

snow anvil
#

It's the full sum because the negative number is less or equal to the sum previous to it

deep snow
#

ouhhh

snow anvil
#

So here [1,2,-4,5] you have 1 +2 - 4 < 0

#

So you have to start a new subarray

deep snow
#

so if at any point when making a subarray it goes negative

#

you start a new one

#

disregarding the number that made it go negative

#

1,2,-4,5

1+2+-4 is -1, so since -4 made it go negative the max subarray so far is 3

snow anvil
#

Well I think you initial misunderstanding was with how these tubarrays worked

deep snow
#

then start the next one after the disregarded number

snow anvil
#

I was using that examples more to illustrate why the sum of full array doesn't work and to make you think more about the subarray

#

But you understand those now right?

deep snow
#

maybe

#

im not sure if I actually do or not xD

snow anvil
#

Try to read about the algorithm again and see if you understand why it is useful if u have any questions feel free to ask

deep snow
#

im gonna go sleep I have work in the morning

#

but yeah ill ping you if anything tomorrow if I understand it further or not

snow anvil
#

Feel free to but I hope other people answer because I think my explanations are kinda shit

haughty mountain
#

basically if you know the max subarray that ends at n-1 what is the maximum subarray that ends at n?

#

you have two options, you could either add the number at n (so + value[n] to the previous max), or you could decide to start a new subarray (which would give you a sum of 0)

#

those are the only two choices, so pick the best one

#

which ends up as "if adding value[n] makes things go negative, just pick the empty subarray from this point"

haughty mountain
#

just saying that doesn't explain why it works

#

ah, from the later discussion I got the impression that the confusion was about how it works

#

never mind then

#

and a good example for why just taking the sum isn't optimal would be something like

1 -1000 2
#

picking -1000 at all would be terrible

summer fossil
#

Need help can anyone provide me soln.

#

I think gfg is not good for beginners!

random plaza
#

Have you tried to find an appropriat algorithm?

regal spoke
#

It is even possible to solve this by counting the number of connected components

haughty mountain
#

i.e. "is this a forest?"

regal spoke
haughty mountain
#

(but yeah, the even more obvious solution is to do a bunch of traversals and seeing if you hit yourself)

#

ah

#

yeah that works

lament totem
#

@blissful kiln ask the egg question here

jade scaffold
#

Yo I am trying to create a custom hashing(encrypting) method for password encryption which we can also ecrypt

#

using a custom wordlist

#

like

#

a means 0n%

whole dune
blissful kiln
#

not sure if this is the wrong place for this sort of thing, but I'll give it a go anyhow! how do I think through this problem, what sort of tools do I need to pick up in order to get better at solving them?
The Empire State Building is 102 stories high. A man wanted to know the highest floor from which he could drop an egg without the egg breaking. He proposed to drop an egg from the top floor. If it broke, he would go down a floor, and try it again. He would do this until the egg did not break. At worst, this method requires 102 eggs. Implement a method that at worst uses seven eggs.

jade scaffold
modern gulch
modern gulch
#

Which floor would you go to first - that would definitely reduce the number of floors you’d have to search the most?

blissful kiln
modern gulch
#

So what floor would you start on?

#

(Trust me, I’ll answer your q)

blissful kiln
modern gulch
#

Great, so how many floors are left? 50ish, right? So now, what floor do you check next?

#

Do this a few times and see what happens when you get to 7 searches

blissful kiln
summer fossil
#

It's binary search problem?

blissful kiln
#

with a constraint on the amount of egtgs.

modern gulch
#

(Or 7th check)

summer fossil
fiery cosmos
#

hi need help with leetcode roman numerals,

blissful kiln
#

so if the egg doesn't break at floor 12, but does at 13.

#

if we're searchin 102 floors, and we divide by 2 for each floor it breaks, we end up at 12, that's fine.

#

assume that our highest floow is now 11.

fiery cosmos
#

not sure how to show the difference for 4s and 9s in py

image.png
blissful kiln
#

we arrive at 6, where it doesn't break, and know that it's between 6-12.

#

how do we think of that range of 6 numbers, with three eggs left?

#

(51, 25, 12, 6, x, x, x)

#

to arrive at 11

#

sorry if I'm not making sense, let me know if I am.

modern gulch
#

51 - 25 - 12 - 6 - 3 - 2 - 1, 7 eggs, right?

blissful kiln
#

sure

modern gulch
#

Or, in your example.

agile sundial
#

why'd they have to use eggs though... just start on the first floor 😭 it's going to break

blissful kiln
#

@agile sundial let's assume we're using your skull instead

modern gulch
#

51-25-12-6-9-10-11 or 6-9-11-x depending on how your rounding

blissful kiln
#

how are you getting from 6-9-10?

modern gulch
#

After 6, you know it’s 7-11, so split it (9) and check

#

Then it’s above 9, so you know it’s 10 or 11

blissful kiln
#

hmm, is this repeatable the other way around?

#

say we have 99

modern gulch
#

At this point, I’d write a little code and test it

blissful kiln
#

I just want to think it through, because I don't think it follows in the same way

#

so say we have 99, I'd approach it by dividing i.e., 102 - 51

#

at this point it doesn't break, (99 is our reference)

#

so I'm thinking I'd add 51 + (51 / 2)

#

which is 76.5, still too low

#

adding 76.5 + (76.5 / 2) > 102, so maybe just 76.5 + (51 / 2) which is 88

#

still too low here.

#

we arrive at 101 in the next iteration

#

there's a range of 11, 100 - 89.

#

we have two @agile sundial skulls left

#

so the increment isn't good enough

modern gulch
#

51 - 76 - 89 - 96 - 99

#

That’s divide remainder by 2 and add (or sub) to last floor

#

I guess you have a math error going from 88 to 101

#

You should’ve gone 88 to 95 or 96 (depending on rounding)

blissful kiln
#

I wonder how well this will work but I'll try to code it today or tomorrow.

blissful kiln
#

is there anything that you're still concerned about when looking at this problem?

modern gulch
#

No, seems straightforward. Write yourself a test case that tries each scenario and tells you how many tries it took.

#

Writing test cases first is a very good practice.

outer rain
#

the goal is to minimize eggs, not attempts

#

wait, one egg

#

whatever, I'm dumb

#

You need one egg

modern gulch
outer rain
#

bruh

celest locust
#

Hello there anyone knows about boyer moore voting algorithm for knowing the majority problem? If so I have been finding the concept of counter incrementing and decrementing and the candidate switching until a majority element appears not intuitive . I know that a majority element exists at least n/2 + 1 and is larger than the remaining elements but can't fathom behind the intuition of counter . Does anyone here know a rigorous proof for that algorithm?

snow anvil
# outer rain You need **one** egg

Unless I am reading the question wrong or we are assuming the eggs work like actual eggs I think you need binary search since he's looking for the highest floor

outer rain
#

no

#

try floor one. If it failed you found the floor. Otherwise take the egg you just used (it did not break, you can reuse it), and try floor two

#

repeat until it breaks

outer rain
#

The proof for it is beatiful

snow anvil
#

Sure if they work like real eggs otherwise this is just a linear sesrch

#

If it's floor 102 your worst case is still 102 floors

outer rain
# celest locust Hello there anyone knows about boyer moore voting algorithm for knowing the majo...

Every element can either decrement or increment the counter. For every decrement, there must be some other element, which incremented a counter, and it must be not equal to the one decrementing, by construction of the algorithm. Imagine now that we split operations (and corresponding sequence elements) in decrement-increment pairs, leaving some last increments without a pair (possibly none). Notice how those last increments are corresponding to the same element. Consider the majority element. Elements in the pair must be different. How much pairs can there possibly be? Well, at most n/2, obviously. But, the majority element appears more than n/2 times! This means that the last increments must be caused by that majority element. Therefore, this element is the last element counter is being incremented for.

P.S. I rewrote this like 5 times lol.

outer rain
#

we don't care about floors

#

we must minimize eggs

snow anvil
#

Your method still uses 102 skulls at worst

#

Nvm

#

U right

#

Disregard me

#

Since this doesn't take place in reality the structural integrity of the shell does not matter

modern gulch
# outer rain we must minimize eggs

To be fair, the specification didn’t say which was to minimized, only that it must not exceed 7 eggs. Nor the properties of a egg after repeated drops. Third, the common sense answer is: 0, since any chicken egg will break from even a first floor drop.

#

But perhaps we’re talking faberge eggs ?

blissful kiln
outer rain
blissful kiln
haughty mountain
#

minimize the number of tested floors using k eggs is an interesting enough problem

#

if k=1 you can only linear search small to large

#

if k is large enough, I think k >= log2(n_floors), you can binary search

#

what about the cases between?

#

the classical problem is with k=2 iirc

#

which can be solved checking only O(||sqrt(n)||) floors

#

and it generalizes pretty neatly with some math

fallen vale
#

Algorithm n data structure is very difficult

blissful kiln
haughty mountain
#

the question to look at is, given that you have 2 eggs and n tries, how many floors can you cover?

#

I guess let f(n, k) be the floors you can cover with n tries and k eggs

#

f(n, 1) = n

#

because you can only linear search from below

#

f(0, k) = 0

#

so what is f(n, 2)?

#

you do some test and the outcome is that you spent a test and may or may not have broken an egg, and you have covered one floor

#

f(n, 2) = f(n-1, 1) + f(n-1, 2) + 1

#

this is the relevant recurrence for k=2

blissful kiln
#

oh I see what you mean - I thInk for the example I illustrated, and not the leetcode problem, that we have 7 eggs, i.e., 7 tries, across 102 floors which using this notation would be f(7, 1) I guess.

#

or f(7, 7) would be more accurate probably, as once an egg breaks we can't reconstruct it

blissful kiln
#

context: The Empire State Building is 102 stories high. A man wanted to know the highest floor from which he could drop an egg without the egg breaking. He proposed to drop an egg from the top floor. If it broke, he would go down a floor, and try it again. He would do this until the egg did not break. At worst, this method requires 102 eggs. Implement a method that at worst uses seven eggs.

#

still with me @haughty mountain?

haughty mountain
#

I think the recurrence is missing a +1 actually

haughty mountain
# haughty mountain f(n, 2) = f(n-1, 1) + f(n-1, 2) + 1

and solving it is fairly straightforward
||expand recursively to get||
||f(n, 2) = f(n-1, 1) + 1 + f(n-2, 1) + 1 + ... + f(1, 1) + 1 + f(0, 1) + 1 + f(0, 2)||
||f(n, 2) = n + n-1 + ... + 1 + 0||
||f(n, 2) = n*(n+1)/2||

#

I realized when actually solving it the answer was off 😛

#

the intuitive logic is ||that if you have 10 tries you can try floor 10 first, if the egg breaks you have enough tries to search through floors 1-9, if the egg does not break you know floor 10 is ok and you're in the same situation with 1 less try||

#

so you can now try floor ||10+9||

#

||and again you have enough eggs to cover floors 11-18, ...||

blissful kiln
#

you're so much better than I am at thinking through algorithms, golly

#

any books you'd highly recommend?

haughty mountain
#

I haven't really learned through books much for cs

blissful kiln
#

gotta take that genius IQ and make some chatbots with it.

haughty mountain
#

the 7 egg, 102 case in particular is part of one of the easier edge cases

blissful kiln
#

nods

haughty mountain
#

if the number of eggs ≥ number of tries things boil down to just binary search

#

with 7 eggs you can for sure do it in 7 tries

#

I think it ends up that you can cover 2^7-1 = 127 in that case (didn't really derive this, but it feels correct, 2^0 - 1 = 0 and whatnot)

blissful kiln
#

almost seems trivial, yeah.

haughty mountain
#

well, it's the easier case for sure

blissful kiln
#

totally. I'll try for a solution in the afternoon.

haughty mountain
#

other than the trivial 1 egg case

blissful kiln
#

if you don't read books for cs, I'm guessing you have a math/combinatorics/logic background? or how else do you find yourself learning if not through books?

#

unless you pop into lectures or you're YouTube heavy.

haughty mountain
#

I do have a bunch of math background, but learning cs has mostly been doing programming contests and researching stuff I ended up needing to learn

blissful kiln
#

oh interesting

haughty mountain
#

which could be as simple as reading a wiki article or whatever, but sometimes might require digging into papers as well

blissful kiln
#

I suppose if your math is robust, everything else is relatively easy.

haughty mountain
#

the problem solving you train when studying math/physics/whatever translates fairly well to cs

#

and some math has direct applicability as well

blissful kiln
#

ty for your time btw

outer rain
haughty mountain
#

and I guess n would be the number of floors in your question?

haughty mountain
#

which is correct if you assume you need to end up at ground level afterwards

#

if not then it's n*(n+1) - n

#

or just n^2

stiff quartz
#

Hi, if someone did problem D of Codeforces yesterday, why is this code too slow for problem D of Round 892 Problem D (https://codeforces.com/contest/1859/problem/D). I'm using memoisation to not compute twice the maximum distance from the same xi, and make sure i track the last_portal used to not try and use portals that would lead to a smaller end point, but it's still too long, i'm not even sure what the complexity of my algo is (it would be O(q+n_portals^2), right? But because of the multiple break statements it should be less than that on average)

def get_as_far_as_possible(xi: int, last_portal_idx: int) -> int:
    if xi in memoisation:
        return memoisation[xi]
    else:
        for portal_idx, portal in enumerate(portals):
            if portal[0] <= xi <= portal[1] and portal[3] > xi:
                xi = portal[3]
                xi = get_as_far_as_possible(xi, portal_idx)
                break
            if portal_idx > last_portal_idx:
                break
        memoisation[xi] = xi
        return xi
 
 
if __name__ == "__main__":
    n_tests: int = int_input()
 
    for _ in range(n_tests):
        memoisation: dict[int, int] = {}
 
        n_portals: int = int_input()
        portals: list[list[int]] = []
        for _ in range(n_portals):
            portals.append(line_integers())
        q: int = int_input()  # len(x)
        x: list[int] = line_integers()
 
        portals = sorted(portals, key=lambda i: i[3], reverse=True)
 
        result = []
        for start_position in x:
            result.append(get_as_far_as_possible(start_position, n_portals))
 
        print(*result)
Codeforces
Codeforces
#

And I tried to understand the tutorial but I'm not sure I understood what they meant with scanline (I know what the scanline algo is, I just don't understand how you can apply it here)

#

And I'm not very good at reading c++ which they wrote their solution is so i'm a bit confused now

#

been trying to figure out this stuff for an hour or two and i'm dying

#

I figured I could do something like scanning all the portals for all positions (so basically computing the answer for all positions decreasing from 10^9 to 1) to not have any quadratic term (but it would O(n_positions*n_portals)) but there are so many more positions that it doesn't seem worth it

stiff quartz
#

I merged useless portals like this:

        # merge portals
        portals = sorted(portals, key=lambda i: i[2])
        stack_portals: list[list[int]] = [portals[0]]
        for portal in portals[1:]:
            if portal[2] <= stack_portals[-1][3]:
                stack_portals[-1][0] = min(stack_portals[-1][0], portal[0])
                stack_portals[-1][1] = max(stack_portals[-1][1], portal[1])
                stack_portals[-1][3] = max(stack_portals[-1][3], portal[3])
            else:
                stack_portals.append(portal)

but it's still too slow lemon_angrysad

#

i get further in the tests though

regal spoke
#

If a point isn't in the range of any portal than it will take O(n) time

stiff quartz
#

Sure there are loads of queries but most will be in the range of at least a portal

regal spoke
stiff quartz
#

so should i make a set containing all the positions that are not in the range of a portal beforehands?

#

that seems kinda bad of a fix

#

especially since there are so many positions

#

iterating over them is even worse than iterating through all the portals

regal spoke
#

Btw I'm not sure I follow your solution idea from reading the code. Are you trying to go for a greedy approach?

stiff quartz
#

yep! I think that's the right idea, for each point, you try to go to the rightmost part of any portal you can take. But you sort the portals before hands based on that rightmost part (decreasing order) so that the first one "you can take" ends up being the one sending you the furthest

#

and since the portals have "continuous ranges" it's pointless to go left at any point

#

so i just always go at the rightmost part of the portal

regal spoke
#

One thing you could do is to add the queries as intervals with l = a = b = r = x_i.

regal spoke
#

But that is not what your code is doing thonkey

stiff quartz
stiff quartz
#

What I do is I've sorted it based on the rightmost part

#

And then I iterate through all the portals

#

And the first one I can take

#

will bring me to the rightmost part i can get to

#

and then i call again the same function

#

since i might have unlocked "new portals"

#

but I think that's where the memoisation should help a lot

#

however it's still like O(n²)

#

which is surely enough too much

stiff quartz
regal spoke
stiff quartz
regal spoke
#

The way I would solve this problem is that I would figure out the maximum coordinate you can reach if you start at b and use 0 or more teleports

regal spoke
stiff quartz
regal spoke
#

Starting from the portal with the largest value of b

stiff quartz
#

I'd have to sort my list in increasing rightmost-part-of-portals, the right pointer going up everytime i unlock a new portal from a fixed position, updating my array memoisation along the way and whenever i can't get to the next portal, i move both the left and the right pointer to the next (unattainable) portal, achieving O(n)?

regal spoke
#

Instead of increasing

stiff quartz
#

Yeh that's what i was doing until now (without the two pointers), but with decreasing b order, I'm struggling to see how I could use two pointers

regal spoke
stiff quartz
#

damn

regal spoke
#

The reason that my submission is kinda slow is that sorted is really slow in Python for sorting non-interger lists

stiff quartz
#

i was trying to code one and i have an infinite loop somewhere

#

(im trying to see if what i tried to code works before checking your solution)

regal spoke
#

This is currently the shortest solution to this problem on codeforces.

stiff quartz
#

wdym codegolfed?

#

btw thx for the help appreciate it

regal spoke
# stiff quartz wdym codegolfed?

I just rewrote the code to be more compact and use fewer lines of code.
If you sort under "status" by AC submission to the problem ordered by "solution size", then my solution is first.

stiff quartz
#

that's something I hope I can have fun doing in a few decades 💀

#

so far from doing this, just trying to get AC and understanding first 😆

#

i've noticed literally no one uses python in the first 200 people

#

it's probably why no one has short solutions i guess

regal spoke
#

Btw I'm not saying that I actually codegolfed it. It is just that my solution is short and simple.

#

I even left in a comment in the code

stiff quartz
#

yeah yeah course

regal spoke
#

I dont think my solution would be all that much longer in C++.

stiff quartz
#

ngl i don't understand why the tutorial talks about multiset and all that stuff

#

when your solution is apparently way easier to understand

#

although i'm still trying to make my two-pointer approach work

regal spoke
#

I havent read the tutorial

#

Lets see

stiff quartz
#

there are two tutorials, a video of a guy explaining he did coordinate compression and used priority queues and it was all c++ so i was lost

#

and the written one was talking about multiset, which is a dsa i didn't really know so i was a bit lost when trying to understand the code

regal spoke
#

It is a sorted data structure

#

Python doesnt have anything like that built in

stiff quartz
#

I think i found that there was a library in python that had it, but it's probably not built in so i don't think i can use it on codeforces

regal spoke
#

It is my own implementation

stiff quartz
#

oh dang

#

that's a lot of prep but i guess it might be very useful - although you need to know them all by heart i guess

#

so you basically copy the class definition when you need a new datastructure?