#algos-and-data-structs

1 messages · Page 45 of 1

brazen python
#

and how do you know that you wont get a KeyError when you check descendants[child]?

haughty mountain
#

first off, do you see why the last equality I posted should be true?

#

if that's not clear nothing will make sense

#

the equality would be true for any node cur

brazen python
haughty mountain
#

not just more

#

but that that exact equality holds

brazen python
#

yep

haughty mountain
# brazen python yep

so if the parent knew the correct answer for its children the answer for the parent is easy to calculate, right?

#

so the key here is that we want to do the calculations in an order where the results for the children are calculated before the result of the parent

#

In any traversal through a (rooted) tree you will encounter the parent before any of its children

#

so if we look at that order in reverse, all children will come before the parent

#

makes sense?

frank pine
#

Need some urgent help:

Traceback (most recent call last):
File "/Volumes/Isaac's External Drive/neogapp/examples/gp/gp_example.py", line 30, in <module>
g = gp.GaussianProcess(X, Y, Sigma, cXstar=(xmin, xmax, nstar))
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/opt/homebrew/lib/python3.11/site-packages/gapp/gp.py", line 117, in init
if (xmin == None or xmax == None):
^^^^^^^^^^^^
ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()

haughty mountain
#

== for numpy arrays are overloaded to do elementwise comparison which is why it tells you about any/all

#

since it thinks it's not obvious what bool(array) means

frank pine
#

thanks a bunch bro! It worked!

#

Even for things that aren't numpy arrays?

#

@haughty mountain

haughty mountain
#

is for None checking is a good idea in general yes

frank pine
#

thanks

frank pine
#

Also: x1s = reshape(x1s, (nstar, nstar)) gave me TypeError: 'numpy.float64' object cannot be interpreted as an integer

#

Any idea?

lean walrus
#

i need some cache, but i dont know how it is called
i have two processes: client and server
client asks server to read some memory (real memory) and send it to client through socket

it works pretty fast if requested memory blocks are big, but for small memory regions it becomes awfully slow (because socket latencies are pretty much constant)
so i need the following cache:

  • when client needs data from server's memory, it actually requests bigger memory block (aligned to page size, for example)
  • cache stores (memaddr_start, length, data) somewhere
  • when client requests cached memory, it is quickly returned back from cache
  • cached values should be invalidated quickly (every several hundreds of milliseconds, for example)

i think i can implement it myself, but i have never done somwthing like this and im pretty sure there is an existing implementation somewhere

frank pine
lean walrus
outer rain
lean walrus
#

hmm, okay
thank you, i will implement it myself using existing implementations for inspiration

haughty mountain
#

you're kinda describing mmap

#

but idk if you can slot mmap into it somehow

#

and idk if you can do invalidation with mmap

#

also why invalidate rather than just doing some lru cache? you're worried about staleness?

lean walrus
#

python on both ends

#
  • windows
haughty mountain
#

🥴

#

I imagined something lower level

#

idk why

lean walrus
opal oriole
haughty mountain
#

presumably not

#

if network latency is a huge worry

lean walrus
haughty mountain
opal oriole
lean walrus
#

hmm

haughty mountain
#

yeah, on the same machine there are way better ways

opal oriole
lean walrus
#

can i share entire process memory to other process?

haughty mountain
opal oriole
#

Server client on same machine is silly.

haughty mountain
#

it depends

opal oriole
#

I see it a lot in web dev, sending data over sockets between processes (on the same machine, silly things like LSPs).

haughty mountain
#

if multi client it can make a lot of sense

opal oriole
#

Unless you also want to actually have it happen over the network too.

lean walrus
#

i have a extremely simple server in fragile unfriendly environment of the game, i dont want to affect the game process too much
client lives in another process, i can quickly restart it, i can use whatever libraries i want and i can attach GUI to it (which is very tricky to do in game because it already has GUI window)

lean walrus
haughty mountain
#

so you're writing a memory debugger basically

lean walrus
#

yeah

#

cheatengine-like thing

haughty mountain
#

¡rule 5 :V

lean walrus
#

it already works
game windows is on the right side, im doing things there
client output is in the console window in the left, you can see values change there

haughty mountain
#

fancy

opal oriole
#

Otherwise it can be a pain, since you need some registering system to make it easy to use (meta-programming baked for example).

lean walrus
#

game is not mine, im just researching it (and it is not violating their TOS (there is no TOS))

opal oriole
#

Oh, then I can't help you with that.

haughty mountain
#

I wonder if there is any python real time debugger

lean walrus
#

there is a bunch of global static variables that hold pointers to all dynamically allocated objects, so if i know the pointer, i can reach to object and all its members

haughty mountain
#

this is python you say? pithink

#

sounds a lot lower level

lean walrus
#

game is in delphi

#

im writing stuff in python (+ a little bit of C-API to spin up thread for CPython)

#

struct declaration looks like this (fully typechecker-friendly btw)

image.png
haughty mountain
#

and you want to monitor the delphi stuff only, right?

lean walrus
#

yeah, there is no point in monitoring cpython, because it is only running 100loc server

#

and i know exactly what is happening inside of it

#

game stuff is a lot more interesting

haughty mountain
#

couldn't you just attach gdb?

#

or whatever debugger

lean walrus
#

thats boring

haughty mountain
#

(it's scriptable in python)

lean walrus
#

i want to implement it myself
and it can be a foundation for things that manipulate game state (for example, game modifications)

#

how can i implement socket-like messaging using shared memory?
the only functionality i need is: ```py
def read(addr: int, size: int) -> bytes: ...
def write(addr: int, data: bytes) -> None: ...

def check(addr: int) -> bool: ... # check if readable


right now i am sending packets like `\1 addr size` to read, `\2 addr datadatadata...` to write and `\3 addr` to check if addr is readable

what should i do with shared memory to achieve similar functionality?
#

another advantage of sockets vs sharedmemory is that they dont depend on bitness of process
game is 32-bit only, but i can talk to it from 64-bit process
i dont think this is easily possible with shared memory

haughty mountain
#

I feel just adding some dumb caching layer on the client side makes sense

#

like a layer that translates a "read n bytes at this address" to "fetch a bunch of N sizes blocks" and then gives you the data you asked for

#

should be a thin enough layer to write

lean walrus
#

write is trickier

haughty mountain
#

in what sense?

#

you want to batch writes?

lean walrus
#

flushing read-caches is pretty easy - just forget about them
flushing write-caches can break game's state:

  • imagine we cached one page for writes
  • write to some place A (this is written to cache, not to game's memory)
  • at this time game writes to B in its own memory
  • flush write cache by just writing cached page into game memory
  • now game's write to B is discarded, and game is left in inconsistent state
haughty mountain
#

why not keep it simple and keep the cache read only?

lean walrus
#

this can happen easily if two objects are allocated near each other: we change A, game changes B

lean walrus
haughty mountain
#

if write latency is an issue. you can bundle a bunch of writes and send them all at once for the server to execute

#

and you probably want to invalidate the relevant parts of cache

lean walrus
#

i can cache page and keep track of bytes that were changed
then send changed page and list of changed bytes (or bitbytemask of changed bytes)

haughty mountain
#

I imagine

------->
  read pls
<-------
   ok, have data
------->
  here, some writes to execute
<-------
   ok, done writing

now invalidate the cached chunks that intersect with your writes
#

or ignore the invalidation and just accept that your cache is stale for a bit

#

but that feels potentially racy

lean walrus
#

another a bit unrelated question:
is it possible to "freeze" game thread for several microseconds while i am doing all reading/writing stuff?
i dont think this is necessary in most cases, but in some very hot places can be helpful

haughty mountain
#

surely yes, debuggers do that

#

as to how, that's a separate question 😛

#

on linux I would look if just suspending the process does what you need

lean walrus
#

is thread considered an another process on linux?

#

i heard something like that

#

enumerating all threads seems to be harder, but i remember that game stores their handles somewhere, so i can grab handles there

haughty mountain
#

so that if you suspend that process all threads are suspended

#

but I don't really know

lean walrus
haughty mountain
#

ah, your thing runs as part of the game process, huh?

lean walrus
#

"server" thing runs in thread in the game process, yes

#

in order to read its memory

haughty mountain
#

yeah, you might want to be more fine grained then

lean walrus
#

good thing is that game uses only couple of threads and very rarely spawns new ones, so manually getting thread handles from some obscure game storage should not be very complicated

#

most of the time there is only thread that does game logic + draws gui (if we ignore music + sound threads)

haughty mountain
#

there should be apis to get all threads for a process

lean walrus
#

i found winapi that extracts this info from process snapshot, i dont think this is a good idea

#

hmm, what would happen if i kill random thread? 🤔

#

sound just disappeared

#

and it fixed a bug

#

it worked for a moment and then crashed

image.png
#

no, it hanged
my thingy still works

haughty mountain
#

not overly surprising if you're killing threads

lean walrus
#

now it crahed completely, i wasnt doing anything

#

funny

haughty mountain
#

suspending hopefully behaves more nicely

lean walrus
#

it is, game hangs if i suspend crucial thread and unhangs when i unsuspend the thread
no crashes

fiery cosmos
#

VfxvGYo3N8o-U0vTPLDxAq2PE-mPvvNqZjK5NAMn3iduohl-Te3TPLSIXidajTOQrDwz_YG_H0WpCwbSF-9Ky9wM6si4EJ5Tc5LK41sJaeuc8gyeOklol9TllUG9HlM2W4NZV03xe7bnnD8NuCXCuVwpwbAeoVH1dIx4o7GdHdSQvUxHvL3LDTww8PV04FTmfUtqJP-au0dFHIYxzJtoSGOEtmRtjtKEp7d5a8aUdqsKrfidxJUs21yRnhfVmHh40Zz8E7602zv9ZYx-2xs=
You think what is this?

haughty mountain
#

some binary data encoded in base64

fiery cosmos
#

all codes this

#

@haughty mountain Is it possible to write code that will decode the url?

haughty mountain
olive badge
#

one question

#

why nobody use codewars?

#

i mean there are a lot videos about leetcode in youtube, same with codeforces
but if you want to see someone solving hard problems in codewars you wont find
codewars hard problems are actually pretty hard haha
i dont know someone who have solve katas 2 or 1
i just want to know what do you think about it

haughty mountain
#

people use it

#

it's not that rare for people in this server to recommend it

#

(I did solve a 2 kata, but katas 1-2 are usually more annoying than really hard)

fiery cosmos
#

I am late with respond, was solving some other problems, but this is better (not my) solution (I guess it is correct)

  def findLength(self, str1, k):
    window_start, max_length, max_repeat_letter_count = 0, 0, 0
    frequency_map = {}
    for window_end in range(len(str1)):
        right_char = str1[window_end]
        if right_char not in frequency_map:
            frequency_map[right_char] = 0
        frequency_map[right_char] += 1
        max_repeat_letter_count = max(
        max_repeat_letter_count, frequency_map[right_char])
        if (window_end - window_start + 1 - max_repeat_letter_count) > k:
            left_char = str1[window_start]
            frequency_map[left_char] -= 1
            window_start += 1

        max_length = max(max_length, window_end - window_start + 1)
    return max_length
#

For this problem

Given an array containing 0s and 1s, if you are allowed to replace no more than ‘k’ 0s with 1s, find the length of the longest contiguous subarray having all 1s.

Example 1:

Input: Array=[0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1], k=2
Output: 6
Explanation: Replace the '0' at index 5 and 8 to have the longest contiguous subarray of 1s having length 6.

Example 2:

Input: Array=[0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1], k=3
Output: 9
Explanation: Replace the '0' at index 6, 9, and 10 to have the longest contiguous subarray of 1s having length 9.

There is also interesting solution:

  def findLength(self, arr, k):
    n = len(arr)
    max_length = 0
    window_start = 0
    num_of_zeros = 0
    for i in range(n):
        if arr[i] == 0:
            num_of_zeros += 1
        if (i - window_start - num_of_zeros + 1) > k:
            if arr[window_start] == 0:
                num_of_zeros -= 1
            window_start += 1
        max_length = max(max_length, i - window_start + 1)
    return max_length
haughty mountain
haughty mountain
#

i.e.

  • I saw 4 character repeats in a window of <=6
  • so I need 5 character repeats in a window of <=7 to beat it
#

the monotonicity means you only need to keep track of the max number of repeats repeats you've seen in a window overall

#

rather than the number of repeats in a sliding window

stiff quartz
#

I'm solving this problem:
https://codeforces.com/contest/356/problem/A

I'm trying to use a segment tree. My Python code would be this one (skip the snippets before if name == main):
https://codeforces.com/contest/356/submission/233010602https://codeforces.com/contest/356/submission/233010602

The solution is inspired from someone's solution https://codeforces.com/blog/entry/22616?#comment-332438 because I couldn't solve it on my own (and I wanted to train my segment trees skills).

I'm however confused as to the update part. I fully understand how to query stuff when the tree is done. I drew the whole binary tree to make sure I understand what's happening with the first example of the examples provided in the problem

image.png
#

I understand that
We update everyone except x[fight_number] - 1 because we don't want to update the winner of the fight as being "conquered by" themselves. hence the two calls

#

But then the partiy checks are a bit obscure to me, I understand that we go to the parents with >>=1 but other than that I'm a bit lost

#

I'd imagine:
if right & 1:
# if right is odd, it means it is a right child
right -= 1
is because right is excluded and we still want to update the [left; midpoint] range?

#

The only thing I understand in the update function is:

            left += self.num_knights
            right += self.num_knights

which is basically to go to the leaves (e.g. if fights are from knight 1 (index 0) to knight 4 (index 3)), we need to look at leaves which are at position 4 to 7 in the array

but why do we care so much about left and right being right children?

EDIT: I actually think I understood.
If left is odd, it's a right child of its parent node. We update it (because [left, right)) and then we will not go further up for the query so we can go "to the left child of the next parent node" by doing left += 1
If right is odd, it's a right child of its parent node. We don't update it (because [left, right)) but we update right - 1 since left < right and since we won't go "further up" it's fine to leave right at (right - 1) // 2 because the parent will be excluded too

dreamy gate
#

guys i got a powerpoint code and i wanna put it in powerpoint but how do i do it

fiery cosmos
#

is it possible to increment a value of a tuple that occurs as part of a value of a dictionary

#

eg:
key: (value, desc)
to increment value here

lean walrus
#

you cant change tuples or integers

#

so the only option is to replace tuple completely with new one

fiery cosmos
#

hmm

#

i'm trying to keep track of occurences of a name as i parse a file, but also store the number of times it occurs and a description

#

i wonder what the best ds is for this

#

doesn't super work with dict

#

i was just building giant lists but that's super inefficient

honest bramble
#

Why not do the occurrence and it’s description as a tuple for the key and increment the value

loud trail
#

is there something in the python standard library that can perform efficient binary searches on sorted lists? or do i need to write that myself?

#

i'm familiar with heapq but i don't see a binary search routine built in for it

solemn moss
#

!d bisect

halcyon plankBOT
#
bisect

Source code: Lib/bisect.py

This module provides support for maintaining a list in sorted order without having to sort the list after each insertion. For long lists of items with expensive comparison operations, this can be an improvement over linear searches or frequent resorting.

The module is called bisect because it uses a basic bisection algorithm to do its work. Unlike other bisection tools that search for a specific value, the functions in this module are designed to locate an insertion point. Accordingly, the functions never call an __eq__() method to determine whether a value has been found. Instead, the functions only call the __lt__() method and will return an insertion point between values in an array.

loud trail
#

aha, that's the one. thanks!

#

out of curiosity, is there no equivalently efficient search algorithm for the binary tree data structure in heapq?

solemn moss
#

idk 🤷‍♂️

loud trail
#

fair enough. in any case, my actual problem is that i have a list of pairs [(a1, a2), (b1, b2), ...] and i want something like this:

items: list[tuple[int, int]]
max(filter(lambda item: item[0] < k, items), key=lambda item: item[1])
#

in my actual code i could just write that as-is and i don't think it'd be a serious performance bottleneck. but i was interested in whether there might be some algorithmically-interesting way to do that, with better (theoretical) performance when running in a hot loop on lists of several thousand pairs.

solemn moss
#

I don't think that's possible without some extra datastructures

With binsearch we can only get that the value is one of the values from 0 to pos (the filter part)
But we can't get the max with it

#

But with anything that can search maximum on that segment - Segment Tree, Spare Table, etc.. sure

loud trail
#

my thinking was that i want the "biggest thing in xs before x", but yeah i don't think that works with two different filter criteria

agile sundial
#

a heap doesn't give you any guarantees about the order except the min/max is the first. so there's no way to search a heap

loud trail
#

i see

haughty mountain
#

I see I'm late to the party

#

thanks discord

loud trail
#

always good to get confirmation!

fiery cosmos
#

hii

daring heart
vagrant anchor
#

Can I calculate the weighted average of the percentages?

naive oak
#

in what context?

quick yarrow
#

is there an easy way to "deepcopy" all the member variables of a variable except 1
something like:

best_model = copy.deepcopy(model, exclude="erb")  # Here i want to copy all member variables in `model` to `best_model` except `model.erb`, which i do not care what value it gets (it can be `None` for example)

motivation: coping the erb member variable is plenty costly (1/3 of total runtime for my program) and is useless in my case

PS if there is a better channel for me to ask this question let me know

vocal gorge
#

!e yeah, that seems to work:

import copy
class A:
    def __init__(self, a, b=None):
        self.a = a
        self.b = b
    # see https://docs.python.org/3/library/pickle.html#handling-stateful-objects
    def __getstate__(self):
        x = self.__dict__.copy()
        del x["b"]
        return x
    def __setstate__(self, state):
        self.__dict__.update({"b": None} | state)

print(copy.deepcopy(A(5, 10)).b)
halcyon plankBOT
#

@vocal gorge :white_check_mark: Your 3.12 eval job has completed with return code 0.

None
quick yarrow
vocal gorge
quick yarrow
vocal gorge
quick yarrow
vocal gorge
#

Then it depends on the class, I guess, but if there's no "external state" (so to say) that you need to maintain, you can do something slightly evil like

def deepcopy(self):
    dct = self.__dict__.copy()
    del dct["erb"]
    # we avoid the normal init. I *think* unpickling does something like this too?
    other = type(self).__new__(type(self))
    other.__dict__ = copy.deepcopy(dct)
    other.erb = None
    return other
quick yarrow
#

is there a way to perhaps create an empty instance of class (without running __init__())

vocal gorge
#

That's the __new__ call here.

solemn moss
#

A string of size n <= 2e5 and q <= 2e5 requests of two types are given:
1 p c -> change character on position p to c
2 l r -> print out minimal period of the substring s[l...r] (inclusive)

period of string is such k, that s[0...k] repeated some times equals to s

How to solve this faster than O(q*logn*d)? (d is the number of divisors, smth like n^(1/3))

This asymptotic is segment tree + hashes
We will store string hash in the tree, for each request we will iterate over all divisors of r-l and check if it is a period

#

From what I know segtree and hashes are correct, but there is a way to not check all the divisors of r-l

silver depot
quick yarrow
quick yarrow
#

in my program i have a big circular buffer

import collections
...
self.buffer = collections.deque(maxlen=1_000_000)

which i am sampling many times in the runtime

return random.sample(self.buffer, 256)

so much so, that it takes <60% of my total program runtime sampling the buffer, is there a way to change the memory layout of the buffer
as far as i can tell, it uses a list data structure for the deque by default, by reserve engineering the memory accesses of it, is there a way for the degue to be allocated using a std::array type structure?

Thanks! (PS if you need clarifications on my requirements be sure to ask)

agile sundial
#

it's not possible in python. yes, deque is a linked list. the things you could do would be implement your own queue or see if you really need to append and pop on the left

stray fractal
quick yarrow
#

it is the traversing of the buffer takes a lot of time, which can not be fixed with a custom sample function

agile sundial
#

deque indexing is slow in the center due to being a linked list. if you're just appending to the right that should just be a list

quick yarrow
agile sundial
#

can you elaborate on that? what properties do you need specifically

quick yarrow
agile sundial
#

ok so just a normal queue with a max size

#

there exists queue.Queue but I don't know how it's implemented and I don't know if it supports indexing

#

you might have to just implement your own, sadly 😔

quick yarrow
#

queue.Queue also uses the same memlayout, i probably will end up writing my own in C++

agile sundial
#

unfortunate

#

you can implement it as a subclass of OrderedDict probably

#

or a class with an ordereddict inside

#

it'd be a lot more expensive memory wise, but the lookups wouldn't be too bad

old rover
# 
class Solution(object):
    def isAnagram(self, s, t):

        return sorted(s) == sorted(t) 

        if len(s) != len(t):
            return False #if length of s is not equal to length of t, it's not an anagram.
        countS, countT = {}, {}
        
        for i in range(len(s)): #iterate through the range of the length of s.
            countS[s[i]] = 1 + countS.get(s[i],0) #counts amount of times each character is in s.
            countT[t[i]] = 1 + countT.get(t[i],0) #counts amount of times each character is in t.
        
        for c in countS:
            if countS[c] != countT.get(c,0): #checks if counts are equal.
                return False
        
        return True
            
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
solution_instance = Solution()
s = ["cat"]
t = ["tac"]
result = solution_instance.isAnagram(s,t)
print(result)
#

my ds algos era has returned

#

but why does this return False

#

aren't they clearly anagrams?

#

cat and tac?

#

or is it because i'm being dumb

#

oh i know

#

it is because i passed in lists

#

not strings

haughty nimbus
#

how to make a hash-statement

fiery cosmos
#

silly quesiton, but CLRS doesn't discuss the towers of hanoi. why would that be? I thought it was a super standard topic

haughty mountain
#

presumably they expect you to know what it is, and they focus on how to analyze recursion and specific recursive algos

#

hanoi is mostly just a simple example to teach basic recursion

old rover
simple silo
#

hey buds i really need someone to explain me this code and how this works

def findxor(n):
    if n%4==0:
        return  n
    elif n%4==1:
        return 1
    elif n%4==2:
        return  n+1
    elif n%4==3:
        return 0
for _ in range(int(input())):
    a,b=map(int,input().split())
    num=findxor(a-1)-findxor(b)
    print("Even" if num%2==0 else "Odd")
#

this is a code to a problem that needs you to xor a range of numbers ex: 2,6 = 2^3^4^5^6 and check if the ans is odd or even

#

this is my approach and it doesnt work with a huge input

for i in range(int(input())):
    a,b = map(int,input().split())
    ans=0
    for j in range(a,b+1):
        ans = ans^j
    if ans%2==0:
        print("Even")
    else:print("Odd")
#

ping me is somebody responds pithink

fiery cosmos
# haughty mountain does CLRS even try to teach "what is recursion?"

they define it and explain it in detail as part of divide and conquer approaches. they do assume that you have seen recursion at least in coding, but they explain it enough from scratch that I am a bit surprised they didn't discuss hanoi. for example, they cover fibonacci from scratch

fiery cosmos
haughty mountain
#

There is the naive exponential approach, O(n) versions and O(log n) versions

fiery cosmos
#

you can find entire books dedicated to the topic

haughty mountain
#

not for the usual 3 peg example at least

#

in that case there is only one option if you want to follow the optimal path

agile sundial
haughty mountain
#

for fibonacci the approaches span several different topics, which is very useful for a textbook

recursion, memoization, dp, exponentiation by squaring on matrices

#

probably more

fiery cosmos
# haughty mountain no there isn't?

well, there is the fact that there are many interesting variations, too. but there are different algorithms for solving the original problem too. there are recursive and iterative methods with several variations

haughty mountain
#

the numbers also pop up in analysis of other algorithms

haughty mountain
fiery cosmos
fiery cosmos
# haughty mountain but all are the same complexity-wise

yes, but the algorithms are different, with different tradeoffs. I think it's an interesting case study that has produced a lot of research, at least from the kind of publications you can find on it. maybe it's just not such a good or central one for a textbook, more of a specialized problem

agile sundial
#

ok but this book..

agile sundial
fiery cosmos
#

I have read parts of it

agile sundial
#

sure ¯_(ツ)_/¯

haughty mountain
#

that doesn't mean it's that interesting and multifaced from a cs point of view

fiery cosmos
# agile sundial sure ¯\_(ツ)_/¯

I really struggle to see how a book having attractive figures and photos detracts from its mathematical interest. look at any book by raymond smullyan with its nice illustrations

#

I stumbled upon a binary solution while working on it and I found it interesting, at least

haughty mountain
#

it has neat mathematical properities, but that doesn't necessarily translate to much in terms of cs topics

fiery cosmos
devout kestrel
# 
"""Grouping bits by chunks in O(n)"""


def get_binstr(s: str) -> str:
    """Bit string representation of Unicode string"""
    return "".join(bin(byte)[2:].zfill(8) for byte in bytes([ord(c) for c in s]))


def group_bits(binstr: str, chunk_size: int) -> str:
    """Returns bitstring representation with each bit moved to form evenly chunks"""
    bitlst = list(binstr)
    j = -1  # sub index
    for i in range(len(bitlst) - 1):
        if bitlst[i] != bitlst[i + 1]:
            if j == -1 or (j + 1) % chunk_size == 0:
                j = i
                continue
            bitlst[j + 1], bitlst[i + 1] = bitlst[i + 1], bitlst[j + 1]
            j += 1
    return "".join(bitlst)


# TODO
# def reconstruct_bits(binstr:str, chunk_size:int) -> str:
#

if __name__ == "__main__":
    size = int(input("\nInsert chunk size >>").strip())
    inp_str = input("\nInput string >>").strip()

    BIN_STR = get_binstr(inp_str)
    print(f"\noriginal bitstring: {BIN_STR}")
    print(f"\nnew: {group_bits(BIN_STR, size)}\n")

Is anyone able to reverse this bit conversion?

verbal ether
#

`salutationsDict = {'de':'Keine Angabe', 'de':'Frau', 'de':'Mann', 'en':'not specified', 'en':'mrs', 'en':'mr'}

germanList = []
englishList = []

for k,v in salutationsDict.items():
if k == 'de':
germanList.append(v)
else:
englishList = [k]

print(germanList)`

Hello guys,
I loop over the key and the value of a dictionary. Then I would like to put all the keys that have 'de' into a list and output it. However, only the last value is always output.

tight cedar
#

I want to ask how can you compute n(n-1) / 2 % 10^9 + 7 for some large integer n.
What if n is less than 10^9 + 7 but the result of n(n-1) is larger than a 32 bit integer? The modular multiplication ((a % m) * (b % m)) % m basically did nothing in shrinking the number here?
Also, I am not very sure how do you do a modular division for the /2 part

jolly mortar
#

could just check which of n or n-1 is even and halve that

tight cedar
#

Oh right but the main part is the multiplication

#

for some n like 10^9 + 6?

lean walrus
#

there is no such thing as 32bit int in python
integers have dynamic arbitrary large size, so you never get any kind of overflow

#

if you want to simulate C behaviour, then you have to do %2**32 or something like that after every operation
(optionally you can create class that does it for you)

tight cedar
#

I know about the python integers thing but how about ppl doing this in c? Basically I want to know whether the only way to solve this is using longer integers

opal oriole
#

If it's even bigger you need a BigInt type.

verbal ether
#

Anyone have a Idea?

verbal ether
solemn moss
narrow mica
# tight cedar I want to ask how can you compute n(n-1) / 2 % 10^9 + 7 for some large integer n...

In general, when you do some division a / b mod m and both a and b get very big so you want to mod first, you instead replace it with an equivalent multiplication a * c mod m.

Here, c is the "modular multiplicative inverse" of b with respect to the modulus m. It satisfies bc = 1 mod m.

To find c, you can use the extended euclidean algorithm. If m is a prime (like 10^9+7, 10^9+9, 998244353, etc.), then you can just use c = pow(b, m-2, m) (by Fermat's little theorem)

exotic bolt
#

Any Python library for diagramming nodes, naming the nodes, and naming their links?

#

Is networkx the most popular graph library?

haughty mountain
#

probably

#

(I never really used it though, I've always just written my own stuff)

exotic bolt
#

thanks for the answer!

#

different question: does anyone know if UML is enough to define SysML, at least, systems, interfaces, and processes?

latent wraith
#

hi guy i m new in ml can you just me difference between weights,parameter and hyperp... in simple words it making me more confuse on internet...

haughty mountain
twin jasper
#

hello guys, so i was trying to apply kruskal algorithm to find the minimum spanning tree, but im not sure if i understand whats a spanning tree well, anyway i did it by hand than tried to apply into code. I had this initial graph and result.
So is the second image truly a spanning tree?
Obs.: i didn't add the weight because i'm in doubt more about the spanning tree concept itself than the algorithm

graphoriginal.jpeg graph_result.jpeg
haughty mountain
#

so yes the right thing is a spanning tree

twin jasper
fiery cosmos
#

Hello, i'm doing currently bubble sort on multiprocessing and im curious is there better way to merge arrays. So it looks like this im opening a n of proccesses and it returns array of n sorted arrays (n is num of processes) and i have to merge them

#

this is my solution

# 
    merged_list = []
    left = 0
    right = 0

    while left < len(res) and right < len(l2):
        if res[left] < l2[right]:
            merged_list.append(res[left])
            left += 1
        else:
            merged_list.append(l2[right])
            right += 1

    merged_list.extend(res[left:])
    merged_list.extend(l2[right:])

    return merged_list


def merge_arrays(results):
    while len(results) > 1:
        res1 = results.pop(0)
        res2 = results.pop(0)
        merged = merge_func(res1, res2)
        results.append(merged)
    return results[0]```
#

also tried this but its not working well on big arrays

# 
def merge_sorted_arrays(arrays):
    result = []
    pointers = [0] * len(arrays)

    while True:
        min_val = float('inf')
        min_idx = -1

        for i, array in enumerate(arrays):
            if pointers[i] < len(array) and array[pointers[i]] < min_val:
                min_val = array[pointers[i]]
                min_idx = i

        if min_idx == -1:
            break

        result.append(min_val)
        pointers[min_idx] += 1

    return result```
#

my teacher said i should optimize it and said smth about merge sort but only merge part but i think the first algo is a some way of merging from merge sort

serene karma
#

I'm learning hashmaps for the first time and I'm running into an issue with this anagram checker. If the two strings are cacc and acca then it reads true. This means I need to remove a value from the hashmap after I check it. del prevValues[ord(t[i])] however it deletes every instance of that value

#

which results in this

#

prevValues.pop(ord(t[i]), i) it looks like pop does the same or I am analyzing the issue wrong

#

I am so close

haughty mountain
#

but you could instead have a key that maps to an integer where you keep the count

serene karma
#

to be honest I don't understand hashmaps at all I think I need to get the neetcode course

haughty mountain
#

how deeply do you need to understand it?

#

at high level it's just a mapping, it maps keys to values

serene karma
haughty mountain
#

it you just need to know roughly what it does that's pretty easy

#

if you want to dig into the details of exactly how hash tables work it gets more complicated

serene karma
#

ok I think it's best I gain a deeper understanding just to be thorough

dawn sky
#

Hi guys, can anyone help me with this? I don't want to have a space after the 6.

Bildschirmfoto_2023-11-23_um_12.40.32.png
lean walrus
#

use f-strings to do that

#

!f-string

halcyon plankBOT
#
Format-strings

Creating a Python string with your variables using the + operator can be difficult to write and read. F-strings (format-strings) make it easy to insert values into a string. If you put an f in front of the first quote, you can then put Python expressions between curly braces in the string.

>>> snake = "pythons"
>>> number = 21
>>> f"There are {number * 2} {snake} on the plane."
"There are 42 pythons on the plane."

Note that even when you include an expression that isn't a string, like number * 2, Python will convert it to a string for you.

shadow oyster
#

def func_a():
if a:
if b:
print(yes)

def func_b():
if a and b:
print(yes)

It seems like func_a is the same as func b but func_b looks better. However, for debugging purposes in my particular case, having nested ifs makes it easier to follow the code. Would it look bad to keep the nested ifs? does it hurt code maintainability?

lean walrus
#

func_b indeed looks better, but func_a is not that bad either

#

i dont think making nested ifs is bad (if you nest them 2-3 times)
nesting them 10 times is of course unreadable, and in this case you should prefer func_b approach

outer rain
#

and if you think a is complex enough to be separate from b, then separate it with a variable. That way you can both "comment" on the meaning of the condition with a variable name, and simplify the debugging by allowing to see the intermediate result

def func_c():
    safe_to_access = 0 <= i < n and 0 <= j < m
    if safe_to_access and board[i][j] = '.':
        ...

but you can do whatever, strongly preferring one is nitpicking imo

shadow oyster
#

Thank you guys. Yeah, in some cases it is complex enough (a is a recursive function that may call itself n times).

haughty mountain
olive badge
#

codefroces blog's looks pretty similar to reddit lol

olive badge
#

!e

a = "fiery"
b = "stickie"
c = "fenix"


print("CASE 1", a,b)
print("CASE 2 "+a+c)```
halcyon plankBOT
#

@olive badge :white_check_mark: Your 3.12 eval job has completed with return code 0.

001 | CASE 1 fiery stickie
002 | CASE 2 fieryfenix
regal spoke
#

If your issue is that a and b are complicated expressions and not nice to have as a one liner, then try moving some of that logic to before the first if statement.

modern gulch
acoustic mason
#

I wanted to access data from this dictionary

students_dict = {
"Student1": "ID001",
"Student2": "ID002",
"Student3": "ID003",
"Student4": "ID004",
"Student5": "ID005",
"Student6": "ID006",
"Student7": "ID007"
} how can I do that?

olive badge
#

the student part or the ID00X part

#

btw this channel is for dsa

haughty mountain
#

I've had to unnest a jungle of 3-4 level if-elses to even understand what logic a coworker tried to write

dapper saddle
#

are you supposed to use imported modules on leetcode?

I'm running into an issue where my result is different than leetcodes for the output, when I do research one of the solutions is using

from collections import Counter

something feels off about using a module to problem solve.

naive oak
#

stdlib libraries are usually fine since they're built into python

#

Counter isn't very hard to implement by hand anyways so it's not that big of an advantage

dapper saddle
#

Thank you

old rover
# 
from collections import defaultdict 

class Solution(object):
    def groupAnagrams(self, strs):
        res = defaultdict(list) #mapping count to list of anagrams
        
        for s in strs:
            count = [0] * 26 # a-z
            
            for c in s:
                count[ord(c) - ord("a")] += 1
                
            res[tuple(count)].append(s)
             
        return res.values()
            
        
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
solution_instance = Solution()
strs = ["eat","tea","tan"]
result = solution_instance.groupAnagrams(strs)
print(result)
#

this is going to be a dumb question but

# 
            res[tuple(count)].append(s)
#

is this where the code matches the strings to the count?

serene karma
#

what does this error mean?

image.png
shadow cosmos
# serene karma

len(prevNums) - 1 is 2 which is out of the bounds of the prevNums array

serene karma
#

literally how

#

by defintion it should be the max index

shadow cosmos
#

Id try printing out prevNums before/after the for loops and see how it changes

serene karma
#

for whatever reason leetcode doesn't allow that

shadow cosmos
#

Oh actually it might have some error bc you’re trying to store an int as the name of the key which I don’t think can work for dictionaries

#

I’m not sure what nums you’re inputting

haughty mountain
serene karma
#

table maybe? no idea how this thing works but I am trying to use it

#

cracking the coding interview is coming soon hopefully that will explain it a bit better, at least provide more direction

#

I'm sure it will go into more depth than I can understand though

#

oh I am a dumbass this isn't a prevNums[0-7] the indicies are exactly the nums

outer creek
#

What is the best data video to learn easily

fiery cosmos
#

can i ask questions here on ADT's?

fiery cosmos
fiery cosmos
fiery cosmos
#

Yes

#

I wrote the linked implemenation

#

i want a array too now

#

and what kind of help do you need?

#

the most basic thing you need to do is decide if this is a static or a dynamic array

#

what would be the difference?

#

Is one hardcoded and one isn't or?

#

I have like a testcode that i need to write it on if that helps?

#

it needs to be a response to it in away

fiery cosmos
#

static array has a fixed number of indices, dynamic array can be expanded or shortened

fiery cosmos
fiery cosmos
# fiery cosmos yes, you can show it to me

if name == "main":
s = MyStack()
print(s.isEmpty())
print(s.getTop()[1])
print(s.pop()[1])
print(s.push(2))
print(s.push(4))
print(s.isEmpty())
print(s.pop()[0])
s.push(5)
print(s.save())

s.load(['a','b','c'])
print(s.save())
print(s.pop()[0])
print(s.save())
print(s.getTop()[0])
print(s.save())
#

thats it

#

would you like to see my code for the linked part?

#

ok, but they want you to implement a stack, not an array

fiery cosmos
#

an array stack

fiery cosmos
#

yeah

fiery cosmos
fiery cosmos
fiery cosmos
#

so what do ido?

#

all you need to do is put the list inside a class and define push with append, pop with remove last item, top with return last item, and is empty with return len(l) == 0

#

however, I am not sure what they mean by getTop()[1] instad of just getTop(), and I don't know what they mean by save()

#

do you have more instructions for it?

# 
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class MyStack:
    def __init__(self):
        self.top = None

    def isEmpty(self):
        return not self.top

    def getTop(self):
        if self.isEmpty():
            return None, False
        else:
            return self.top.data, True

    def pop(self):
        if self.isEmpty():
            return None, False
        else:
            data = self.top.data
            self.top = self.top.next
            return data, True

    def push(self, value):
        new_node = Node(value)
        new_node.next = self.top
        self.top = new_node
        return True

    def save(self):
        stack_data = []
        current = self.top
        while current:
            stack_data.append(current.data)
            current = current.next
        return list(reversed(stack_data))

    def load(self, stack_data):
        self.top = None
        for value in stack_data:
            self.push(value)
#

this is my code for linked

fiery cosmos
#

save returns everything

fiery cosmos
# fiery cosmos save returns everything

ok makes sense. sorry I don't have more time right now, but it's very simple. just create a class. initialize with self.stack = [] and then pop returns a tuple like (True, item) by accessing the last item in the stack, or if the length of the list is 0, it gives you (False, None)

#

push appends to the list, etc.

#

can't i reuse my code?

#

and change the names

fiery cosmos
#

define them differently

#

would you mind continiuing this when have free time?

#

sometime this week or so

fiery cosmos
fiery cosmos
#

try to do it, it's not too hard, I think you can do it

#

i will try and let you know bro

#

thank you

olive badge
#

hey guys do you think atcoder begginer contest are actually for begginers?

quartz yoke
#

Hi, I dont currently really know where to put my question. Is here anyone who uses and builds actionaz automation scripting program? I have a little puzzle to build, can´t figure, how to build 2 script working parralel.

olive badge
exotic bolt
#

any interesting theoretical treatments of the subject of discoverability?

serene karma
# 
    def majorityElement(self, nums):
        numsTable = {}
        for i in range(len(nums)):
            numsTable[nums[i]] = 1
        for i in range(len(nums)):
            numsTable[nums[i]] += 1
        return max(numsTable, key=numsTable.get)``` Is this O(n) or O(n^2)
agile sundial
#

the former

serene karma
#

oh ok is there a way to avoid two for loops here?

image.png
#

just doing += 1 does not work and I am having a hard time checking for nil

snow anvil
agile sundial
coral coral
halcyon plankBOT
#

usr/gen_init_cpio.c lines 173 to 174

3,			/* major */
1,			/* minor */```
coral coral
#

it seems to use that same major/minor on all entries, it also seems to start the inode at like 700, just kinda does weird thigns

median meadow
#

That is the beauty of programming, nothing makes sense, while making all the sense in the world, programmatically.

median meadow
haughty mountain
manic kite
#

In the n stairs problem, the solution can be obtained by the fibonacci sequence, which is an application of the addition principle? If so how to prove that the 2 sets (combinations of (n-1) and combinations of (n-2)) are disjoint.

serene karma
#

I have very little idea what any of this means what should I do to better understand it?

IMG_2626.jpg
old rover
#

implementing it

#

and i know data structures and algos are language agnostic

#

but i am reading a book in python

#

i believe CTCI is in java

serene karma
#

it is

#

I have solved 2-3 problems using a hashtable on my own and 3 more after looking at the solution

#

so I can sorta use it, are you not supposed to use integers as keys?

old rover
#

are you talking about your majority element code

serene karma
#

no I'm talking about hashtables

#

oh yea

#

maybe?

#

oh yes that and another similar problem that I solved today

old rover
#

so integers work

#

pub will probably correct me if i'm wrong

snow anvil
#

And don't use the built in

serene karma
old rover
slender sandal
#

Python dictionaries are a kind of a hash table where the hashes of the keys are used, so the keys must be hashable

#

Any key will do as long as it is hashable

#

Even keys of mutable types

serene karma
#

ok thanks

haughty mountain
# serene karma I have very little idea what any of this means what should I do to better unders...

tl;dr: one of the simplest types of hash table is:

to add an element x to the hash table

  • compute hash(x) to get an integer h
  • use h to pick a bucket to put this element in
  • put x in that bucket

to check if an element x is in the hash table

  • compute hash(x) to get an integer h
  • use h to find the bucket this element must be in
  • look at the elements in the bucket to see if there is any equal to x
    • if there is, the element is right there, answer is true
    • if there isn't, the element is not in the table, answer is false
old rover
# 
class Solution(object):
    def replaceElements(self, arr):
        rightMax = -1
        
        for i in range(len(arr)-1,-1,-1):
            newMax = max(rightMax, arr[i])
            arr[i] = rightMax
            rightMax = newMax
        return arr
            
        """
        :type arr: List[int]
        :rtype: List[int]
        """
        ```
#

this problem is making me bug out

#

maybe i'm just tired

#

i just don't understand the point of iterating through the list backwards

lament totem
#

It's a recursive pattern @old rover . The maximum element to the right of some position is the maximum between the element on the right, and the maximum of all the elements to the right of that position.

#

So by going backwards you only have to go through the list once

#

Because you use the result of each position to find the result of the next position to the left

old rover
#

i am way too tired for this ig

#

i will come back to it tomorrow

old rover
modern gulch
old rover
floral dew
#

hey guys, quick performance problem. i'm learning dynamic programming and wanted some easy practice. the problem i picked: https://cses.fi/problemset/task/1633/

i solved it in linear time and even optimized to constant space (https://paste.pythondiscord.com/ZFZQ), but i get TLE starting from the case n = 654321. i came across this sol, linear time and linear space, and it passes the problem, running ~4-5x faster at n = 1 mil:```py
dp = [1]
for i in range(int(input())):
dp.append(sum(dp[-6:]) % (10**9 + 7))
print(dp[-1])

our logic seems equivalent. where's my bottleneck? thank you for the help!
runic tinsel
#

i can't profile it accurately by sight, but i'm sure it's just from having that much less things to do, not because there's a particular part in your code that secretly takes ages

haughty mountain
#

it might actually just be cpython being too slow

haughty mountain
#

this seems to be fine runtime-wise

combos_n = [0] * 7
combos_n[0] = 1

for i in range(1, n + 1):
    curr = i % 7
    combos_n[curr] = 0
    combos_n[curr] = sum(combos_n) % MODULUS

print(combos_n[n % 7])
#

sum is written in C

#

so this is a case of pure python code just being too slow

old rover
#

how do i come up with brute force solutions faster?

#

i know you’re supposed to do brute force and then optimize

old rover
#

actually

#

i was able to say the brute force algorithm in my head before i tried to implement it in code yesterday

haughty mountain
#

with experience you can just figure out the optimal solution immediately in some cases

#

sometimes if you have no clue what to do brute force + optimization might be a good idea, but sometimes it's not feasible to just incrementally improve a naive solution

old rover
#

i have a problem with translating what’s in my head to code

#

maybe it’s a sign to brush up on the fundamentals

haughty mountain
#

the boring answer is just practice

old rover
#

yes

haughty mountain
#

pick some simpleish problem, figure out solution and implement in code

#

rinse and repeat

old rover
#

yep

#

i think i’m getting better

old rover
#

where are the discord backticks on mobile?

#

so i can type code from my phone

#

oh ok

# 
class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        for i in range(len(arr)):
            max_value = -1
            for j in range(i+1, len(arr)):
                max_value = max(max_value, arr[j])
            arr[i] = max_value
        return arr
#

so i did this for this problem

#

it timed out lol

old rover
#

probably due to time complexity reasons

summer fossil
#

||py class Solution: def replaceElements(self, arr: List[int]) -> List[int]: n = len(arr) nums = [-1]*n ans=-1 for i in range(n-1,-1,-1): nums[i] = ans ans = max(arr[i],ans) # print(nums) return nums||

old rover
jolly mortar
old rover
old rover
fiery cosmos
#

Hello is there any algorithm for merging a n of sorted sub arrays ?

#

i only did this one but i want to know if there any way of optimize this code or do i can do it better

#

arrays is a list of sorted sublists

# 
def merge_sorted_arrays(arrays):
    if not arrays:
        return []
    
    merged_list = arrays.pop(0)
    
    while len(arrays) > 0:
        l2 = arrays.pop(0)

        merged = []
        left, right = 0, 0

        while left < len(merged_list) and right < len(l2):
            if merged_list[left] < l2[right]:
                merged.append(merged_list[left])
                left += 1
            else:
                merged.append(l2[right])
                right += 1
        merged.extend(merged_list[left:])
        merged.extend(l2[right:])

        merged_list = merged

    return merged_list
modern gulch
fiery cosmos
modern gulch
fiery cosmos
#

yup

modern gulch
#

So taking the first element is taking the min.

#

Then you just need to sort the first elements /take the min of the first elements

fiery cosmos
#

so how can i take min from all lists in same iteration ?

modern gulch
#

There are many ways. You could sort the lists by the head value. You could pop the first values and sort. You could take the min of the first values.

fiery cosmos
# modern gulch There are many ways. You could sort the lists by the head value. You could pop t...

Okay i get the idea, so i will take the min of first elements in all lists then pop this element from for example first sublist and after this ill again take min from all list but now on 0 index there will be a 2nd element from this 1st list ?
[0,5,7] , [2,6,1], [8,10,12] -> min val 0
[5,7] , [2,6,1],[8,10,12] -> min val 2
and do it until all lists are empty or there is one list left, and if there is one list left just add all elements into this merged_list

fiery cosmos
# 
l = [[1, 3, 5], [2, 4, 6], [0, 7, 8]]

merged_list = []

while True:
    min_val = float('inf')
    list_idx = -1

    for i in range(len(l)):
        if l[i] and l[i][0] < min_val:
            min_val = l[i][0]
            list_idx = i

    if list_idx != -1:
        merged_list.append(min_val)
        l[list_idx].pop(0)
    else:
        break

print(merged_list)
modern gulch
fiery cosmos
#

how it would like on large datasets like 100000 divided into 8 sublists

modern gulch
#

Complexity analysis is an exercise left to the reader 🙂

fiery cosmos
#

I'm doing multiprocessing project for py lessons when im testing bubble sort with multiprocessing so im splitting a lists into number of processes after bubble sort on every list this im getting exacly a list of number of processes sorted sublists it can be like 100000 elements divided into sublists just in case it will change something in approach 🙂

fiery cosmos
#

can someone tell what i did wrong

Screenshot_2023-11-27_at_18.35.15.png
old rover
fiery cosmos
#

also if you can't tell i am trying to create a atom in python

old rover
#

i'm looking at some code for containsDuplicate

#

and i noticed that i is 0

#

but i'm confused as to how?

#

i also noticed it stays as 0 throughout

fiery cosmos
#

me to i am confused as well

old rover
#

maybe i'm just having a brainfart lol

fiery cosmos
#

idk waht to do next

old rover
#

actually i think it's intentionally placed at 0

#

so then j goes through the rest of the list

fiery cosmos
#

im new to python this is my 5th project actualy

old rover
#

that's good

fiery cosmos
#

i know i started python due to depression and anxiety

#

how old are you damain

old rover
#

currently in college

#

lol

fiery cosmos
#

oh i am 11 years old

#

or 12 somthing

#

idk

#

lol

old rover
# 
class Solution(object):
  def containsDuplicate(self, nums):
    n = len(nums)
    for i in range(n-1):
      print(i)
      for j in range(i+1, n):
        print(j)
        if nums[i] == nums[j]:
          return True
    return False

solution_instance = Solution()
nums = [99, 100]
result = solution_instance.containsDuplicate(nums)
#

ok so i think i understand this now

fiery cosmos
#

thanks man

#

your great

old rover
#

while moving j forwards

fiery cosmos
#

peace out

valid kindle
#

guys i need help with designing an algorithm with the least possible complexity
i tried but i always get O(n^2), i cant get to O(n)
it wants me do encryp a message as follow:
for each number its value is added to next bigger number that follows its location
if there's no such number, keep that number without a change
example:
[7, 4, 5, 10, 2, 1, 7, 8, 2] result is [17, 9, 15, 10, 9, 8, 15, 8, 2]

# 
function encode_message(input_numbers):
    n = length(input_numbers)
    result = new array of size n

    for i from 1 to n:
        current_number = input_numbers[i-1]

        # Initialize next_index to the index after i
        next_index = i + 1
        
        # Find the next bigger number
        while next_index <= n and input_numbers[next_index-1] <= current_number:
            next_index = next_index + 1

        # Check if a next bigger number is found
        if next_index <= n:
            result[i-1] = current_number + input_numbers[next_index-1]
        else:
            result[i-1] = current_number

    return result

that's my pseudocode for the algo but isnt that brute-force that's why i get O(n^2) ? if so then what should i do :(

drifting hare
#

my intuition says to go in reverse and use a stack

valid kindle
drifting hare
#

it's basically a linked list where you can either append or consume the end node

valid kindle
drifting hare
#

oh just use a deque

#

so from collections import deque

#

create a deque with stack = deque()

#

you can then do either stack.append() or stack.pop()

haughty mountain
valid kindle
#

can i send you the question in dms if that's okay?

haughty mountain
#

i.e. keep a stack as you go, as soon as you find something bigger than the thing on top of the stack, pop from the stack and process that element

drifting hare
#

uhh sure dm me

valid kindle
#

i understand what a stack is but i never typed pseudocode with it so idk how to do it

haughty mountain
# 
# add 2 to stack, go to next
2, 1, 3, 1
^
stack = []

# 1 is smaller, just add to stack and go to next
2, 1, 3, 1
   ^
stack = [2]

# 3 is bigger than 1, pop and handle
2, 1, 3, 1
      ^
stack = [2, 1]

# 3 is bigger than 2, pop and handle
2, 4, 3, 1
      ^
stack = [2]

# add 3 to stack and go to next
5, 4, 3, 1
      ^
stack = []

# 1 not bigger than 3, add to stack, advance
5, 4, 3, 1
         ^
stack = [3]

# done
5, 4, 3, 1
            ^
stack = [3, 1]
haughty mountain
#

and you can kinda handwave the unimportant details

valid kindle
#

i see thank you for that great explanation
will try to do pseudocode with that

valid kindle
modern gulch
tame idol
haughty mountain
#

oh you mean the stack

#

the stack we maintain will always have items in decreasing order, which is the key to do this efficiently

#

in particular, the stack contains all the elements that haven't seen a larger element yet

#

so as soon as you get something larger you can start pairing it up with the elements it's the next largest elements for

#

Also it should be noted that my example was cheating a tad, I did not store enough info to know what number to modify

#

but if you store the index as well you have this info, so easy to fix

#

I just wanted to keep the example simple

uncut roost
#

Hey guys,
I'm not quite sure if this is the right group to ask this but I am in need of a Python coder that is experienced in trading bots/ algorithmic trading. Please send me a DM if you'd like to discuss a potential job.

old rover
floral dew
#

@runic tinsel thank you for the thoughts too!

serene karma
#

how do you do [:] for dictionaries?

lean walrus
coral coral
supple gull
#

test

#

@fierce moat

craggy rose
#

Hello, I'm trying to solve this problem on LeetCode however I'm getting RTE. Would appreciate any help

image.png
# 
public:
    bool search(vector<int>& nums, int target) {
        int low = 0;
        int high = nums.size()-1;
        while(low<=high){
            int mid = low + (high-low)/2;

            if(nums[mid]==target)
                return true;
            
            if(nums[low] == nums[mid] && nums[mid] == nums[high]){
                low++; high--;
            }

            //check if left half is sorted
            if(nums[low]<=nums[mid]){
                if(nums[low]<=target && target<nums[mid])
                    high = mid-1;
                else
                    low = mid+1;
            } else { //check if right half is sorted
                if(nums[mid]<target && target<=nums[high])
                    low = mid+1;
                else
                    high = mid-1;
            }
        }

        return false;
    }
};```
old rover
# 
class Solution(object):
    def containsDuplicate(self, nums):
        n = len(nums)
        for i in range(n):
            print(i)
            for j in range(i+1, n):
                print(j)
                if nums[i] == nums[j]:
                    return True
        return False
# 
class Solution(object):
  def containsDuplicate(self, nums):
    n = len(nums)
    for i in range(n-1):
      print(i)
      for j in range(i+1, n):
        print(j)
        if nums[i] == nums[j]:
          return True
    return False

solution_instance = Solution()
nums = [99, 100]
result = solution_instance.containsDuplicate(nums)
print(result)
#

hmm

#

why the -1

modern gulch
#

Once you reach the last element, there’s nothing to compare it to. You’re comparing the i th element to the elements from i+1 to n (the j loop)… so the very last check is i=n-2 and j=n-1

old rover
#

i think i need to brush up on my fundamentals

#

this is not doing me any good

#

back to automating the boring stuff i go lol

modern gulch
old rover
#

hm

#

i look at the fundamentals and i think i get them but i see a leetcode easy and i'm stumped

modern gulch
#

Learn to add print statements and inspect the variables, that’s the biggest problem most new engineers have: they stare at the code to understand it

old rover
#

yeah

#

that and using a debugger

modern gulch
#

I rarely use a debugger. A few print statements usually are enough

#

But a debugger is good too

old rover
#

there is also python tutor which is a code visualizer

#

not sure why it's called that and not python visualizer but yeah

modern gulch
#

In this case, i recognize the general pattern: you have one loop over i, then a loop over j. Since you’re comparing the element at i to the elements at j, there’s no reason to check the last element

old rover
#

it's so frustrating

#

it's like having a sentence in your head but being unable to speak it

modern gulch
old rover
#

but i feel like a part of it is memorization

modern gulch
old rover
#

i just solved a leetcode easy on my own

#

well

#

technically it was a similar question to contains sum 1

#

it was contains sum 2

#

https://leetcode.com/problems/contains-duplicate-ii/

LeetCode
Contains Duplicate II - LeetCode

Can you solve this real interview question? Contains Duplicate II - Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: t...

# 
class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        n = len(nums)
        for i in range(n-1):
            for j in range(i+1, n):
                if nums[i] == nums[j]:
                    if abs(i-j) <= k:
                        return True
        return False
                   
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
#

i wrote the psuedocode in my notebook

modern gulch
old rover
old rover
# 
class Solution(object):
    def minimumOperations(self, nums):
        n = len(nums)
        for idx, num in enumerate(nums):
            if nums[idx] == 0:
                nums.pop(idx)
        min_number = min(nums)
#

this unfortunately is all i was able to come up with

#

identifying the minimum number

#

all i did was identify the number that's greater than zero

#

in the list

haughty mountain
old rover
haughty mountain
#

why would you want bruteforce if you can see a better solution? pithink

old rover
#

well

haughty mountain
#

(a better solution that is also easier)

old rover
#

i thought it would be a good practice to come up with brute force solutions firsst

#

and then optimize from there

haughty mountain
#

the brute force here is just...annoying

old rover
#

but i think doing it would help me learn

haughty mountain
#

you're probably better off doing it on a task where you don't know a better way

old rover
#

ugh

#

i write out the steps, i know them in my head

#

but i can't put them to code

agile sundial
#

try using pseudocode first, that might help

agile sundial
haughty mountain
#

subtract min of array
remove zeroes

over and over and over

#

that is the brute-force

#

O(n² + suffering)

#

though maybe suffering is constant

#

(in my defense I didn't set out to make that joke, it just happened)

old rover
#
  1. find the minimum value in the list by removing all zeroes and getting the minimum number from there
  2. iterate through the list
  3. subtract the minimum value from each number in the list
  4. increase the countOperations by 1 for each time a number in the list is zero
  5. update the minimum value
  6. return the countOperations
#

and from what i can see

#

it seems like the code from what i did above does finds the minimum the first pass

lilac mulch
#

Hello everyone

#

I had a problem with my python

#

Take a look of it

#

When i run the code it doesn't work

#

Like the same i saw

lean walrus
lilac mulch
#

Oh ok i will try

lean walrus
#

btw it literally said you that

image.png
lilac mulch
#

Thank dude @lean walrus

serene karma
#

how many easy problems should it take you to be able to solve a medium problem

modern gulch
serene karma
#

K most common element in list

#

List is all internet

#

So like if k is 3 the top 3 most common

#

No idea how to only use K numbers

modern gulch
#

I assume you want problem solving advice, not a solution: try to reframe the question as something non coding. How would you do this with a room full of numbered blocks?

#

Don’t try to be clever in the first pass, just come up with a brute force or naive solution.

serene karma
#

ok thanks 🙂

#

if you just add numbers to a hashtable without using a hashcode is it even a hashtable?

#

I don't know if that makes sense

jolly mortar
#

do you mean treat the numbers themselves as their hashcode

#

if so then thats already almost the case in python, ints hash to themselves

wide marlin
#

i'd like to get into DSA
what books should I look for? if there's one with a gentle introduction i'd love to read it
nvm there's some on the pinned

old cape
# 
    ref = arr[0]
    i=0
    while i<len(arr):
        if arr[i]!=ref:
            return False
        i+=1
    return True        
print(all_equal([1,0,0,0,0]))
            ```
#

line 8 seems to be the issue. it is something to do with the return keyword, if i just print "True", it seems to be working fine

jolly mortar
#

whats wrong with it?

old cape
solemn moss
#

!e it doesn't?

def all_equal(arr):
   ref = arr[0]
   i=0
   while i<len(arr):
       if arr[i]!=ref:
           return False
       i+=1
   return True        
print(all_equal([1,0,0,0,0]))
halcyon plankBOT
#

@solemn moss :white_check_mark: Your 3.12 eval job has completed with return code 0.

False
jolly mortar
#

you dont handle the case of arr being empty

long temple
#

hi

tacit yoke
#

Does anyone know the difference of a condition and a conditional? Have an exam and need help asap

real gull
#

i need a bit of help and dont know where to go

#

tensorflow text isnt installing

real gull
#

nvm

#

tensorflow was outdated

real gull
#

ah fuck thought it downloaded

#

this mf

snow anvil
old rover
# 
class Solution(object):
    def groupAnagrams(self, strs):
        charCounter = {}
        for s in strs:
            for c in s:
                charCounter[c] = 1 + charCounter.get(c, 0)
        print(charCounter)
    
    
    """
    input: strs = ["eat","tea","tan","ate","nat","bat"]
    output: [["bat"],["nat","tan"],["ate","eat","tea"]]
    1. start with a blank dictionary
    2. iterate through the list
    3. count each character that appears through the list
    4. if the character count is the same, append the strings together in a list
    5. return the strings
    
    """

       
        
    """
    :type strs: List[str]
    :rtype: List[List[str]]
    """
#

so this is weird

#

i'm getting {u'a': 6, u'b': 1, u'e': 3, u't': 6, u'n': 2}

#

what is u'?

#

unicode?

old rover
#

i can't for the life of me do this

modern gulch
old rover
#

ooh

modern gulch
#

But, what version of python are you using?

old rover
#

dude

#

i'm an idiot

#

i've been using python

#

THE WHOLE TIME

#

smhhhh

modern gulch
#

You should be

old rover
#

no not python3

#

python

#

smh smh smh

#

is that why???

modern gulch
#

Oh, python2?

old rover
#

i think so

#

i didn't realize

#

smh

#

attention to detail much

#

lolll

modern gulch
#

Oh, "python" in Leetcode is 2.7.18

#

Make sure you pick Python3

old rover
#

whoopsie

modern gulch
#

That's just terrible ergonomics by leetcode. They should at least label "python" as Python2

old rover
#

yeah i didn't realize

naive oak
#

!e

from itertools import groupby
def all_equal(seq):
    g = groupby(seq)
    return next(g, True) and not next(g, False)
for item in [[], [1], [1, 2], [1, 1], [1, 2, 1]]:
    print(f'all_equal({item}) = {all_equal(item)}')
halcyon plankBOT
#

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

001 | all_equal([]) = True
002 | all_equal([1]) = True
003 | all_equal([1, 2]) = False
004 | all_equal([1, 1]) = True
005 | all_equal([1, 2, 1]) = False
haughty mountain
#

len(set(seq)) <= 1 is quite tempting

buoyant nexus
#

yo can somoee explain to me the usage of array in numpy library

naive oak
haughty mountain
#

this one is kinda neat

not any(x != y for x, y in pairwise(seq))
#

or I guess all(x == y ...)

#

though the first reads better to me

#

(and no-one mention ||nan|| pls)

lean walrus
#

i would argue that [nan, nan] contains two different values (even if nan is nan)

old rover
# 
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        numberCounter = {}
        for n in nums:
            numberCounter[n] = 1 + numberCounter.get(n, 0)
        for key, value in numberCounter.items():
            if value >= 2:
                return True
        return False
                
            
        
        ```
#

@modern gulch i wrote my own solution to contains duplicate pithink

#

by throwing a dictionary at it

#

is that considered brute force?

modern gulch
#

I don't know if I'd use the term brute force, but this is inefficient because: you keep going after you get your first duplicate.

agile sundial
#

brute force would just be the O(n^2) solution

old rover
#

ohhh

#

ok

modern gulch
# old rover ok

But, you're just starting out, and this is a fine first pass at the problem.

old rover
modern gulch
#

And there's other problems where you'd need something like this pattern. Yah, feel good about it.

#

But, consider how you could be more efficient by stopping as soon as you hit a duplicate.

old rover
modern gulch
modern gulch
#

But, ignore that...

#

In your solution: Why are you keeping a count?

old rover
#

my bad

agile sundial
#

why use a dictionary if you can return true as soon as the count gets to 2?

old rover
# 
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        numberCounter = {}
        for n in nums:
            numberCounter[n] = 1 + numberCounter.get(n, 0)
        return True if numberCounter[n] >= 2 else False
#

but that fails [0,4,5,0,3,6]

#

hmmmm

#

i don't know why that fails

#

actually

#

i might

#

what if it's seeing a value that's not actually greater than 2

agile sundial
#

you're only checking the occurrences of the last element in nums

#

the value of n after the loop ends is the last element in the list

old rover
#

uhhh

old rover
agile sundial
#

you want to check the occurrences of every element, not just the last number in the list

old rover
#

i don't get it

agile sundial
#

your last line isn't indented

old rover
#

hmmm

#

now it fails [1,2,3,1]

modern gulch
old rover
agile sundial
old rover
#

idk then

agile sundial
#

maybe you would instruct them to look backwards from where they are and see if they find the word again

#

that way they only have to remember one word at a time

old rover
#

i've seen this iterating backwards through an array solution before

modern gulch
#

forget about code, python, etc.

old rover
modern gulch
#

There's a line of people. And paper and pen.

old rover
#

my bad

modern gulch
# old rover hmmm line of people then

The point is; the 5th grader needs to visit each person. And stop as soon as they get to the first duplicate. They have a bad memory, so must use their notebook and pen.

#

Explain the algorithm. Then, implement in Python.

old rover
#

sorry for all the questions

modern gulch
#

Yes eventually, but first step is to ignore code/data structures and just envision; what would you tell a 5th grader?

hazy garden
# 
with open("input.txt", "r") as f:
    lines = f.readlines()
def word_to_num(line):
    replacements = {
        "twone": "21", "oneight": "18", "eightwo": "82", "threeight": "38", "eighthree": "83", "fiveight": "58", "sevenine": "79", "nineight": "98", "one": "1", "two": "2", "three": "3", "four": "4", "five": "5", "six": "6", "seven": "7", "eight": "8", "nine": "9"
    }
    for word, num in replacements.items():
        line = line.replace(word, num)
    return line
num_list = []
for line in lines:
    modified_line = word_to_num(line)
    counter = 0
    indexed = 0
    first_digit = 0
    second_digit = 0
    for ch in modified_line:
        if ch.isdigit():
            counter += 1
            indexed = modified_line.index(ch)
            first_digit = int(ch)
            break
    for i in range(len(modified_line)-1, indexed, -1):
        if modified_line[i].isdigit():
            counter+=1
            second_digit = int(modified_line[i])
            break
    if counter == 1:
        second_digit = first_digit
    num = first_digit * 10 + second_digit
    num_list.append(num)
print(sum(num_list))
hazy garden
agile sundial
modern gulch
agile sundial
haughty mountain
#

(join the cult)

old rover
# 
class Node:
  def __init__(self, value):
    self.value = value
    self.next = None
    #we create a class that creates a Node


class LinkedList:
  def __init__(self, value):
    new_node = Node(value)
    self.head = new_node
    self.tail = new_node
    self.length = 1
    #create a new node.
  
  def print_list(self):
    temp = self.head()
    while temp is not None:
      print(temp.value)
      temp = temp.next
  
  def append(self, value):
    new_node = Node(value) #created a node
    if self.head is None: #tested to see if the list is empty 
      self.head = new_node
      self.tail = new_node
    else: #otherwise do this
      self.tail.next = new_node
      self.tail = new_node
    self.length += 1
    return True
    #create a node
    #add it to the end.
 
my_linked_list = LinkedList(1)
my_linked_list.append(2)

my_linked_list.print_list()
```---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-7-e6aa84657e66> in <cell line: 38>()
     36 my_linked_list.append(2)
     37 
---> 38 my_linked_list.print_list()

<ipython-input-7-e6aa84657e66> in print_list(self)
     15 
     16   def print_list(self):
---> 17     temp = self.head()
     18     while temp is not None:
     19       print(temp.value)

TypeError: 'Node' object is not callable
#

what am i missing here?

#

there's a typo somewhere

#

is it indentation?

#

a type error usually indicates me trying to use an argument that's not compatible with a certain type

#

dude

#

i'm an idiot

#

there's no parentheses after self.head() in the print_list function

#

smhhhh

#

at least i caught the damn error

brazen cedar
#

hi does anyone know about LZ77

lilac cradle
#

is there an efficient way to convert rows to columns? say you have a list of list where each sublist is a row, so like say l = [a,b,c,d,e...] where a,b,c,etc are all sublists

is simply iterating through and making a column like [a[x],b[x],c[x],d[x],e[x]] the fastest way, or is there some other way to do it

modern gulch
halcyon plankBOT
#
zip 

zip(*iterables, strict=False)```
Iterate over several iterables in parallel, producing tuples with an item from each one.

Example:

```py
>>> for item in zip([1, 2, 3], ['sugar', 'spice', 'everything nice']):
...     print(item)
...
(1, 'sugar')
(2, 'spice')
(3, 'everything nice')
```...
Similar names: 2to3fixer.zip
tawny path
#

Hello, Iam trying to learn QuickSort (just to get a bit ahead from the bubble sort that we are taught at school) and I am stuck on a few details.

I copied the code to experiment with from GeekForGeeks. The code works great, fast and with no functional problems. Problem is, that I am getting stuck in the logic behind it. I have looked at it from YouTube tutorials, explanations and I get the jist of it, but I can't make out how it actually does the sequence of operations.

This is the array sample I used to test it.
[1, 7, 4, 1, 10, 9, 21]

Code I am using: https://www.geeksforgeeks.org/python-program-for-quicksort/

GeeksforGeeks
Python Program for QuickSort - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

modern gulch
tawny path
#

well, for one, I understand that QuickSort is a variation of MergeSort (which I don't know how to do), that splits the arrays into 2 with each sequence, working in smaller groups so it can work faster.

#

I could be completely wrong but that's what I know (and that it is 100s of times faster than Bubble Sort if the array is not sorted or nearly sorted beforehand)

#

as for what I am stuck in, I am trying to make a table of how the values change with each iteration. My problem is that I don't really get how it does the itteration.

agile sundial
#

quicksort works pretty differently from mergesort, but they're both divide and conquer algorithms

#

the interesting part is in the pivot function

modern gulch
#

Hmm? Im wondering about bringing 5th graders into this again

#

Ok, I’ll try: let’s say you had a bunch of kids in a class and want to sort by height. The only thing you can do is divide them into two groups. So you pick a kid and put everyone shorter than the kid in the left group, and taller than the kid in the right group.

#

Then, for the left group, you do the same thing, shorter and taller group. You keep breaking them into smaller groups until you reach 1 kid in each group, at which point, you’re sorted.

agile sundial
#

i think that's cheating tbh. a 5th grader isn't sorting, they're just an element

tawny path
#

I do (kinda) get how divide and conquer algorithms work. What I am confused is the order that it does the operations because I cannot seem to match it in my table

modern gulch
#

Fine. My fifth grader who is doing the sorting has a terrible memory and can only compare one kid at a time against a reference kid.

agile sundial
modern gulch
tawny path
#

(I feel like it's a good time to curse my limited vocabulary).

I mean how it goes through the array in this piece of code:

def quickSort(array, low, high):
    if low < high:
 
        # Find pivot element such that
        # element smaller than pivot are on the left
        # element greater than pivot are on the right
        pi = partition(array, low, high)
 
        # Recursive call on the left of pivot
        quickSort(array, low, pi - 1)
 
        # Recursive call on the right of pivot
        quickSort(array, pi + 1, high)```
#

the whole code is in the link

#

I haven't really touched self nested (is that the term?) functions so I get confused in how it works

modern gulch
#

You mean ‘recursive’ functions?

tawny path
#

yes, that

modern gulch
#

Oh. Think of my example for a moment:

#

But I’ll describe it recursively:

#

You pick a kid and find everyone shorter, and put them in the left group. Then, you go to the left group, and pick another kid and pivot them into a left and right group. Then you go to the left group (that you just created), and pick a kid and pivot again. You keep pivoting the left groups until the group has only one kid. Then, you go back and deal with the last right group

agile sundial
modern gulch
#

Tbh, maybe fib would be a better example to learn recursive…

#

That site is pretty neat and helps you visualize recursive Python functions

tawny path
#

thanks, I will check it out and check out a few more sources. I am still fairly a beginner, despite how fast I progress

#

I think I finally get it (somewhat). With practice will make perfect. Thanks again guys!

exotic bolt
#

is there a formalization of the idea of software ecology, or software as a complex system? comp sci wise

heady sentinel
#

Can anyone pls help me convert this piece of C code to python accurately? I am having some problems.

#include <stdio.h>
#include <math.h>

int main() {
    int t, b, a, y,z;
    scanf("%d", &t);
    while(t) {
        scanf("%d", &b);
        y = sqrt(b);
        z = cbrt(b);
        a =  y + z - (int)(sqrt(z));
        printf("%d\n", a);
        t--;
    }
}
vocal gorge
#

What's your current attempt? Offhand, scanf might be annoying to reimplement if you want exact equivalence of action, because Python mostly takes input by line.
EDIT: this person has now made a help channel

heady sentinel
#

I have no problem with I/O but there's some rounding(converting to int) errors happening in python. Output sometimes increases or decreases by 1.

#

I have tried converting everything to int in python but that does not help.

#

Here is my current attempt.

import math

for _ in range(int(input())):
    b = int(input())
    y = int(math.sqrt(b))
    z = int(math.pow(b, (1/3))) 
    a = y + z - int(math.sqrt(z))
    print(int(a))
#

This problem from code forces 1619B. Test case:

10
1
25
1000000000
999999999
500000000
vocal gorge
#

C's cbrt presumably is equivalent to the latter.

heady sentinel
#

I have used numpy.cbrt too it's the same

vocal gorge
heady sentinel
#

Sry, I cant use numpy and code forces uses python 3.8

#

Is there any alt to math.cbrt?

slender sandal
#

You can try using round instead of int in z = int(math.pow(b, 1 / 3))

vocal gorge
# heady sentinel Is there any alt to math.cbrt?

!e You're kind of in trouble, then. You could try a simple fix, like applying one iteration of Newton's method to the inaccurate cuberoot:

def cbrt(x):
    y = x ** (1 / 3)
    y -= y / 3 - x / (3 * y**2)
    return y
print(1000000000**(1/3), cbrt(1000000000))
halcyon plankBOT
#

@vocal gorge :white_check_mark: Your 3.12 eval job has completed with return code 0.

999.9999999999997 1000.0
vocal gorge
#

but no guarantees it'd actually work

vocal gorge
slender sandal
#

No idea if they rely on flooring when it matters

regal spoke
vocal gorge
#

ah, good point. implementing an accurate icbrt(x: int) -> int is much easier than a float one (pretty much do y = int(x**(1/3)) and then try it and y+1 for the outcome)

regal spoke
#

hmm

regal spoke
#

Just tested it, and as long as you don't use crazy large numbers (> 2**64), then you wont need -1. I think the reason why it works is that the floating point representation of 1/3 is just slightly less than 1/3

#

!e

import math
x = 259254712487743
y1 = int(x**(1/3))
y2 = int(x**math.nextafter(1/3, 1))

print(y1, y2)
halcyon plankBOT
#

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

63763 63763
regal spoke
#

Hmm on my computer locally this results in 63763 63764

#

This is the scary thing about using floating point numbers.

shadow glen
#

okay so, i realie that i'm instantiating my class wrongly:

    async def _character(self, ctx):
        embed = discord.Embed(
            description=await Help(ctx.guild).character
        )
        await ctx.send(embed)
#

what is the correct way?

[2023-12-03 15:57:59] [ERROR   ] discord.app_commands.tree: Ignoring exception in command 'math'
Traceback (most recent call last):
  File "C:\Users\User\AppData\Local\Programs\Python\Python311\Lib\site-packages\discord\app_commands\commands.py", line 827, in _do_call
    return await self._callback(self.binding, interaction, **params)  # type: ignore
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "C:\Users\User\Documents\GitHub\RP-Utilities\cogs\MathCog.py", line 44, in math_slash
    description= await Help(interaction.guild).math
                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "C:\Users\User\Documents\GitHub\RP-Utilities\help.py", line 32, in math
    prefix = await self.get_prefix()
             ^^^^^^^^^^^^^^^^^^^^^^^
  File "C:\Users\User\Documents\GitHub\RP-Utilities\help.py", line 10, in get_prefix
    prefix = self.database.get_prefix(self.guild_id)
             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
TypeError: Database.get_prefix() takes 1 positional argument but 2 were given

The above exception was the direct cause of the following exception:

Traceback (most recent call last):
  File "C:\Users\User\AppData\Local\Programs\Python\Python311\Lib\site-packages\discord\app_commands\tree.py", line 1248, in _call
    await command._invoke_with_namespace(interaction, namespace)
  File "C:\Users\User\AppData\Local\Programs\Python\Python311\Lib\site-packages\discord\app_commands\commands.py", line 853, in _invoke_with_namespace
    return await self._do_call(interaction, transformed_values)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "C:\Users\User\AppData\Local\Programs\Python\Python311\Lib\site-packages\discord\app_commands\commands.py", line 842, in _do_call
    raise CommandInvokeError(self, e) from e
discord.app_commands.errors.CommandInvokeError: Command 'math' raised an exception: TypeError: Database.get_prefix() takes 1 positional argument but 2 were given
#

like, it seems my program detected self as a parameter to be filled

#

i don't know how i was suppose to instantiate to make it function properly without asking the "self"

ember osprey
#

i'm not sure if this should go here, but i'll give it a shot: i'm using the noise library to generate noise for my game and it sometimes produces strange results like you see here. here is my code to generate the noise (x and y are looped through and WORLD_SEED is set to random.randint(1, 1000)):

filled_value = max(0, (noise.pnoise2(x / 10, y / 10,
                                                 octaves=2,
                                                 persistence=0.8,
                                                 lacunarity=2.0,
                                                 base=WORLD_SEED) + 1))

Any ideas how to... make it look right?

Screen_Shot_2023-12-03_at_11.17.01_PM.png
#

(i'm looking for less uniform/repeaty and more random results, like caves)

#

(it works sometimes but every now and then when I run it it gives stuff like this)

vocal gorge
#

Huh, weird, I can replicate this. The issue seems to be with the first octave of the noise for base=512 or base=1024 and probably some others.

#

Actually, all the octaves really.

#

This is probably some feature of perlin noise that I don't know enough about; maybe try the other functions from this package and see if they're less prone to periodicity.

frail jetty
#

Hi

#

I need a function that makes a matrix have 1 in a spiral shape

runic tinsel
#

@frail jetty```py
def s(n):
a = [[1],[0]]
for l in range(2, n+2):
a = [(1,)*l , *zip(*reversed(a)) , (0,)*l]

return a

for a in s(8): print(a)

lean walrus
#

!e ```py
def s(n):
a = [[1],[0]]
for l in range(2, n+2):
a = [(1,)*l , *zip(*reversed(a)) , (0,)*l]

return a

for a in s(8): print(a)

halcyon plankBOT
#

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

001 | (1, 1, 1, 1, 1, 1, 1, 1, 1)
002 | (0, 0, 0, 0, 0, 0, 0, 0, 1)
003 | (0, 1, 1, 1, 1, 1, 1, 0, 1)
004 | (0, 1, 0, 0, 0, 0, 1, 0, 1)
005 | (0, 1, 0, 1, 1, 0, 1, 0, 1)
006 | (0, 1, 0, 1, 0, 0, 1, 0, 1)
007 | (0, 1, 0, 1, 1, 1, 1, 0, 1)
008 | (0, 1, 0, 0, 0, 0, 0, 0, 1)
009 | (0, 1, 1, 1, 1, 1, 1, 1, 1)
010 | (0, 0, 0, 0, 0, 0, 0, 0, 0)
loud jay
#

what is the best way to learn algorithms and data structures? as well as problem solving?

cyan dagger
pale cosmos
loud jay
coral grove
#

I want to evaluate the effectiveness of a text classification algorithm in terms of how many mistakes it did, anyone has experience knows where to look? I want to know on average how many mistakes it will make in an n sample

urban kiln
exotic bolt
#

is there some sort of approach to software programming where software is programmed modularly, so that different parts of the code can be ran individually without needing to run the entire program? is this possible in python?

narrow mica
exotic bolt
narrow mica
exotic bolt
pale cosmos
modern gulch
pale cosmos
#

He may be asking how to use the library twilio

modern gulch
#

Yah, I just wasn’t sure if they’re asking about how to import, if they’re getting an import running, did they write some code and it’s failing, etc. but either way, would probably be guided in pydis a little faster

lilac scaffold
#

Hey there. Do you have any suggestions for speeding up Python code? I was looking into Numba, but it doesn't work well in many cases.

haughty mountain
modern gulch
lilac cradle
#

is there a specific term for iterating through a grid?

#

like going through each row

lean walrus
#

"iteration over rows"

#

i dont think it should be more specific than that

lilac cradle
dawn cosmos
#

So I have this problem

BC02264C-BF25-4C33-952D-643FC37D2CF5.jpg
#

And I think I know that I need to reduce it from Vertex Cover as that’s probably the closest thing to this

#

I’m just having trouble figuring out how to set it up as VC

#

Would I want students as edges or students as vertices?

#

It would have to be students as vertices right

#

Cause in VC not every vertex is used and if I need every course to be present that wouldn’t work

final palm
#

can someone check this pls before i send to my tutor

image.png image.png image.png image.png
haughty mountain
#

pick an appropriate channel pls

haughty mountain
#

that seems very close to the description of the problem

#

(or equivalently, hitting set)

#

VC is a special case of SC, but I suspect SC will serve you better

exotic bolt
#

are there any language-independent approaches to designing algorithms? so that implementation in a particular language is a final step

agile sundial
#

pseudocode

covert ember
#

but the "standard" algorithms are pretty much implemented the same with minor details making the differnce

copper holly
#

Guys, this is my personal reference of how to use decorators or what can be done with them, any suggestions to add or corrections of misunderstandings? https://paste.pythondiscord.com/EOWA

copper holly
#

I g the class method implementation is incomplete, it fails if it is called without an instance

copper holly
# 
def _classmethod(f):
    def mod_f(*args, **kwargs):
        f_name = f.__name__
        if args and getattr(type(args[0]), f_name, None) is mod_f:
            self = args[0]
            args = args[1:]
            return f(type(self), *args, **kwargs)
        else:
            cls = getattr(importlib.import_module(f.__module__), f.__qualname__.rsplit(".", maxsplit=1)[0])
            return f(cls, *args, **kwargs)
    return mod_f```
#

This works for all cases I tested

#

Anyone wants to vet it? 👀

fiery cosmos
#

Hello, I am new here; please help me in my DSA learning journey!

cobalt parcel
#

Hey after implementing Binary Heaps in form of trees and arrays
we found arrays are better in all operations
in term of time complexity
is this correct?
why is it?

outer rain
# exotic bolt are there any language-independent approaches to designing algorithms? so that i...

Pretty much every algorithm is designed to be language agnostic. Instead, we say an algorithm runs on a certain "abstract machine" with a certain "model of computation", for instance: turing machine, RAM machine, external memory machine, etc., and then knowing the properties of that machine, we construct a program using operations that machine can perform. Most single-threaded algorthims are designed for RAM machines, which is basically any cpu, which exists at the moment (ignore multiple cores for a sec), and you can implement basically any algorithm, in any language, which allows writing code for RAM machines. So, for instance, you can implement a heap as it is in Python, or C, or Java, or even Haskell, but you will find it difficult to implement in say, CUDA, a language for programming GPUs, which works on a different device which uses a different model of computation. All that is to say, in some sense, algorithms exist in a plane different from a plane languages exist in.

outer rain
outer rain
# cobalt parcel Hey after implementing Binary Heaps in form of trees and arrays we found arrays ...

The time complexity is the same. It is basically impossible to know the time complexity from the experiment though, because of how complex measuring time is. Both are O(n) build, O(1) max, and O(log n) insert & pop. You get that from a theoretical analysis of the algorithm, not from an experiment (although you can refer to an experimental result, saying "the algorithm performs that good on our experimental data", you just can't conclude the complexity from that. The opposite is also somewhat true: you can only estimate the time it would take the algorithm to execute based on time complexity, but not measure time directly in a lot of cases).

cobalt parcel
#

yeah we are not trying to prove anything, we just found out that the array version takes less time in all operations

outer rain
#

The reason why array implementation is faster, is because not all implementations are created equal. Some are faster, and some are not. What language did you use?

cobalt parcel
#

and wonder if its supposed to be like that

#

or we messed up

cobalt parcel
outer rain
#

it is supposed to be like that

#

Well, I can't know the exact reason why, but I if I had to guess:
0. initializing tree nodes requires memory allocation, which an expensive operation, compared to pushing to an array

  1. Recursive function calls take more time than simple loops, so traversing a tree is slower than iterating over the array
  2. Memory layout of the array is better than the tree layout in memory, so it is easier for hardware to work with (although it is very difficult to estimate the effect of that in python, it is definitely present)
  3. The code python executes is simply more complex, since it requires accessing class fields

I would guess that tree-based implementation is anywhere from 3 to 8 times slower than the array one, but this is just a wild guess, you have to measure it

#

If you used pypy, then it is also possible that pypy optimized the simple array-based code significantly better than the plain python one, but I don't know pypy enough to reason much about that

cobalt parcel
#

hmm interesting

cobalt parcel
#

@outer rain also is timeit and lambda function the correct way to measure execution time? because Ive seen it get weird with bumps

#

like in this case

image.png
#

the graph on the right is supposed to be logn

#

sometimes it does look like logn sometimes it has these weird bumps when I run the function multiple times

outer rain
# cobalt parcel <@284257720406638594> also is timeit and lambda function the correct way to meas...

that should be fine, but you say "sometimes" you get those bumps?

Check your environment. Make sure the data is randomly distributed in the way you want, and check that CPU load is as similar as possible between the runs. Also it might be just that your implementations actually works like this. It may be just me witch hunting (most likely, yes), but could it be that the performance with sizes close to the power of two behave slower?.. I am probably wrong, because I have no idea how can you even make it that way with binomial heap, but it might be worth checking. And, of course, make sure your implementation is correct, before benchmarking it.

Unfortunately measuring time is a whole science of it's own, so it make take a long time to explain why the time behaves like that.

cobalt parcel
#

this is with timeit ```py
heap1.createBinomialHeap(list[len(list)//2:])
heap2 = BinomialHeap()
heap2.createBinomialHeap(list[:len(list)//2])
execution_times.append(timeit.timeit(
lambda: heap1.mergeHeap(heap2), number=1))

image.png
exotic bolt
#

thanks for the answer btw

cobalt parcel
#

@outer rain sometimes it gives me this which does kinda look like logn

image.png
outer rain
#

You are trying to measure times of orders of microseconds, which is way too small for a single iteration

#

unfortunately, I am not sure how to easily measure union at all, since it takes way less time to complete compared to the setup required for it 🤔

outer rain
exotic bolt
#

noted ty!

cobalt parcel
#

I just followed some tutorial on how to measure a function

outer rain
#

I don't know much about it either, unfortunately

slender sandal
halcyon plankBOT
#
timeit.timeit 

timeit.timeit(stmt='pass', setup='pass', timer=<default timer>, number=1000000, globals=None)```
Create a [`Timer`](https://docs.python.org/3/library/timeit.html#timeit.Timer) instance with the given statement, *setup* code and *timer* function and run its [`timeit()`](https://docs.python.org/3/library/timeit.html#timeit.Timer.timeit) method with *number* executions. The optional *globals* argument specifies a namespace in which to execute the code.

Changed in version 3.5: The optional *globals* parameter was added.
slender sandal
#

It just runs stmt number number of times using globals as the global namespace. setup is run once beforehand, timer is time.perf_counter by default. The return value is the sum of the timer measurements

#

E.g. with stmt="time.sleep(1)", setup="import time", number=10, the return value is approximately 10

cobalt parcel
#

It runs the stmt code 1 million times by default and return the minimum

slender sandal
#

No

# 
Python 3.12.1 (tags/v3.12.1:2305ca5, Dec  7 2023, 22:03:25) [MSC v.1937 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> from timeit import timeit
>>> timeit(stmt="time.sleep(1)", setup="import time", number=10)
10.013792699901387
>>>
#

Congratulations, Python 3.12.1 is out now

unique needle
#

Hi, I hope I choosed the right channel for this, but I have a machine that decorate a gingerbreads, Now I have a algorythm to detect the contours of the gingerbread. Do you have some ideas on how to do some filling patterns? Like some fancy decorating with the machine? (What algorythm to use to create the patterns specificly). Thanks a lot for answer!

fiery remnant
#

Suggest me a playlist for dsa in python

hoary sun
#

hello people

#

so i was trying to make a graph with connections between nodes within a certain radius of one another. i used the sampling based rrt algorithm for sampling nodes

#

i modified the code i found in an online repo

image.png
#

and used dijikstra's algorithm to find the path between two nodes

#

i dont think the path that the algorithm found was the most optimal(i may be wrong here) can you guys tell me what could be the reason for that?

#

idk if i should link my code here so please let me know if you want it

prisma forum
#

is there any common discussion group here in this server?

tender peak
#

yoo wassup

#

I just wanna to make my basic python code run in a window screen using Pygame
How can I do it

cedar totem
icy oasis
#

i think this is the correct space to ask this but apologies if not.
is the pulp library able to handle objective functions where the decision variables undergo some transformation and the result is what's optimized?
specifically if the decision variables are put into a vector and multiplied by a matrix.