algos-and-data-structs

[idle zephyr]

You are given a number N. You need to print the pattern for the given value of N.

For N = 2 the pattern will be 
2 2 1 1
2 1

For N = 3 the pattern will be 
3 3 3 2 2 2 1 1 1
3 3 2 2 1 1
3 2 1

Note: Instead of printing a new line print a "$" without quotes. After printing the total output, end of the line("$") is expected.```

Input: 2
Output:
2 2 1 1 $2 1 $```

My implementation, but somehow its wrong

def printPat(n):
    #Code here
    a = [str(x) for x in range(1,n+1)]
    b = n
    for i in range(1,n+1):
        for j in a:
            print(j*b,end=" ")
        b -=1
        print("",end="$")   

[fossil pagoda]

Loop running infinite times

[fossil pagoda]

  x=n
  for k in range(n):
        for i in range(n,0,-1):
            for j in range(x,0,-1):
                print(f"{i} ",end="")
        x-=1
        print("$",end="")   
n=int(input("Enter a number: "))
pat(n) ```

[fossil pagoda]

@idle zephyr

Sorry for trash soln

But will get it done

[mossy finch]

def printPat(n):
    #Code here
    x = ''.join([''.join([f"{i} "*j for i in range(n, 0, -1)])+"$" for j in range(n, 0, -1)])
    print(x)

here's a simple version

[mossy finch]

there's no need to use 3 loops

it can be done with a single or not even with a variable if u directly print the string without defining it in a variable

[mossy finch]

and the output will be nothing if n = 0

if you need it to print the "$" if n = 0

then, delete the +"$" and change the string of the first join function to '$', ''.join to '$'.join and the print function from print(x) to print(x, end='$')

it should print '$' if n = 0

and the responsible output for other numbers

[flint plinth]

Does anyone here know hot to build trading algos using Ict Concepts?

[glossy lintel]

its done

jesus

after forever

3 weeks of progress

i think implementing the doubley and circular linked list will be a bit easier

[fossil pagoda]

This is working

I didn’t know how to use .join

There might be a small mistake tho

It’s adding an extra space after repeated numbers but I think you can fix it

Time complexity wise it’s better

[severe notch]

can I ask leetcode problems related questions here?

[fossil pagoda]

Yes

[plush canyon]

can I ask why I'm encountering tensorflow warnings here???

I'll just leave it here since I'm about to take a sleep

I need some help at my coding. The problem I'm encountering is my code is having a hard time predicting my gestures, I'm thinking that this is the problem why (I might be wrong). Appreciate the help.
WARNING:tensorflow:No training configuration found in the save file, so the model was not compiled. Compile it manually.
I also make sure that I compile it at my coding
self.loaded_model_custom = load_model("Model/keras_model2.h5")
self.loaded_model_custom.compile(loss='categorical_crossentropy', optimizer=Adam(), metrics=['accuracy'])
self.loaded_model.compile(loss='categorical_crossentropy', optimizer=Adam(), metrics=['accuracy'])

[severe notch]

2095. Delete the Middle Node of a Linked List
So my approach was to use two pointers and move right whenever there is next node, and move left each second time (for that I used counter to count every odd turn)
To delete a node I just take left.next and make it left.next.next

class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        left = head
        right = head
        counter = 0
        while right.next:
            counter += 1
            if counter & 1 == 0:
                left = left.next
            right = right.
        left.next = left.next.next
        return head

However there seems to be a problem with this test case:
[1,3,4,7,1,2,6]

I got [1,3,4,7,2,6],
expected [1,3,4,1,2,6]

[severe notch]

I solved it by not moving left right was still on head

[fiery cosmos]

Hello ladies and gentlemen 🎩

[mossy finch]

well now yk

[mossy finch]

oh yeah, and the reson is you don't need the ' ' in the second join

ive edited it

[glossy lintel]

tbh im thinking for performance, we could go even further

i might reimplement the algorithm

with slight changes

[haughty mountain]

is that __reversed__ quadratic time?

[ebon finch]

This function is supposedly O(m^2n^2) complexity.
However I’m just getting O(m^2n). Note the dense_householderreflection has O(m) complexity

[haughty mountain]

you're doing n matrix multiplications, no?

[ebon finch]

At each iteration the matrix multiplication has time complexity m^2 and since you have n iterations it’ll have overall complexity of nm^2?

[haughty mountain]

matrix multiplication has time complexity m^2
does it?

naive matrix multiplication algo is O(n^3)

or I guess to be precise the naive algo for multiplying (N x M) * (M x K) is O(N M K)

it can be done a bit better with some algos, but we have no idea if doing it in quadratic time is even possible

[ebon finch]

Oh my bad matrix multiplication is O(n^3)

[opal oriole]

Nobody knows if N^2 is possible. Currently best theoretical is N^2.37188 IIRC. But in practice only N^3 is used and in some rare cases N^2.807 (Strassen's). Many algorithms that push this Big O even lower tend to not make sense for any real implementation as they don't take physics into account.

[haughty mountain]

yeah

Strassen is practically feasible for large enough matrices, but I think for most usual cases just hard optimized regular old matrix multiplication wins

i.e. BLAS/LAPACK/whatever

[opal oriole]

Strassens is actually only good for specific ranges of sizes. For large enough sizes in general it loses to the N^3. This is because information does not travel instantly (speed of light). And memory in reality has a physical location (and so it takes variable time to retrieve it (based on position)).

In theory math land all memory is the same. This is a huge disconnect from reality.

[agile sundial]

what is different in strassen's that makes this an issue compared to the naive algorithm?

[haughty mountain]

I wonder if you can do something silly to make the cache locality better for strassen

like hilbert curve ordering or whatever

[opal oriole]

Strassen's does a tradeoff that causes the physical setup to require more communication overhead, and that overhead scales.

There are some specific ranges / matrix sizes where due to physical constants / materials it actually is better.

[agile sundial]

whereas the naive algorithm lends itself to easy prefetching and other cache things i guess

[opal oriole]

Yes.

This is the reason it's especially more practical for reasonable matrix sizes.

The ones that push it even further in Big O tend to start having ridiculous requirements, like more memory than is physically possible in the observable universe.

The paper's authors like to make jokes about its practical applications in the paper.

[haughty mountain]

the O(n log n) integer multiplication has similar fun properties

though it could probably be made less bad

[opal oriole]

They both draw on the same tradeoff factors abused, it comes back to the faster multiplication.

[haughty mountain]

that paper was very much showing that it was possible

[opal oriole]

That was the start of all this absurd tradeoff stuff.

[haughty mountain]

is it that recent, surely not?

[opal oriole]

The faster multiplication has been broken very recently, 2019 I think? Not sure.

And also implies that one could get even better but at this point it's becoming a giant search problem (which can maybe be automated).

[haughty mountain]

yeah, it's quite recent

(and one of the reasons I remember that paper is that I remembered one of the authors as the creator of TeXmacs)

I'm more questioning that the absurd trade-off stuff is that recent, but maybe it is

I haven't followed developments that closely

[opal oriole]

From the latest one:

Need 2^(7.137398073×10³⁸) bit integers.

2^(1729^12)

[haughty mountain]

right, I know some of the constants here are kinda picked just for fun

so it's not quite that bad

but yeah, it's not practically useful

[opal oriole]

The interesting part is that physically this also does not work, since those numbers need to be stored, and that memory has a physical position, and so retrieving it takes variable time based on distance, you can't have all the memory in the same position.

And the numbers here are so large that it would not even fit in the universe if you used every atom to try to store them.

[glossy lintel]

yeh....

i needed to duplicate the linked list

[glossy lintel]

no worries tho, im improving the performance

on a 1 million linked list, it did about 1.83 seconds

on 1 million linked list with the previous implementation

it does way longer

imma test it on a 30k linked list length

19.83 seconds

for the previous implementation

whereas the other 0.044 seconds

(massive improvements)

i used batch traversing

on a 100 million linked list, it struggles

[candid rain]

Hi. I need to create a binary tree but I also need to keep information about type of the operation for each node.

Is it okay if I add new attribute to each node operation ?
Meaning that you can calulcate the data in node if you perform that operation with data from its childs.

[mossy finch]

well that's not a RULE you can use any data you need in it

the reason it is called a binary tree is

each node has atmost 2 child nodes

[candid rain]

Ye you're right. Im just asking if something like this could work.

[mossy finch]

well, anything is possible :)

[keen hearth]

Sure! You can add whatever additional attributes you want to each node.

[mighty flint]

Hello

I am working on a project to solve the missionnaries and cannibals proble using graphs

this is the main part of my code

from graph import Graph

'''
function to turn '33L' into digit so it'll work with the graph class
'''

indexes = []

def name_to_index(name):
    if name not in indexes:
        indexes.append(name)
    return indexes.index(name)

def render_name(name):
    return ''.join((str(n) for n in name[:2]))+['R','L'][name[2]]

def get_comb(n):
    if n==1:
        return []
    comb = []
    for i in range(n // 2 + 1):
        comb.append((i, n - i))
        if i != n - i:
            comb.append((n - i, i))
    return comb+get_comb(n-1)


def get_neigh(state, amount=3, capacity=2):
    neigh = []
    comb = get_comb(capacity)
    for c in comb:
        if state[0]>=c[0] and state[1]>=c[1]:
            neigh.append([-1, amount-(state[0]-c[0]), amount-(state[1]-c[1])])
    
    # Handle individual (round-trip)
    if state[2]==0:
        # ML
        if state[0]>=1:
            neigh.append([4, amount-(state[0]-1), amount-(state[1])])

        # CL
        if state[1]>=1:
            neigh.append([5, amount-(state[0]), amount-(state[1]-1)])

    result = []
    for n in neigh:
        if (n[1]>=n[2] or n[1]==0) and n[1]+n[2]>=0 and n[1] <= amount and n[2] <=amount  and (amount-n[1] >= amount-n[2] or amount-n[1]==0):
            modified_n = n + [int(not(state[2]))]
            result.append(modified_n)
    return result



def encode(state):
    return name_to_index(render_name(state))

graph = Graph()

def generate_graph(init, amount=3, capacity=2):
    if init==(amount,amount,0) or (init[1]>init[0] and init[0]!=0):
        return
    neigh = get_neigh(init, amount=amount, capacity=capacity)
    for n in neigh:
        if render_name(n[1:]) not in indexes:
            graph.add_edge(encode(init), encode(n[1:]), n[0])
            generate_graph(n[1:],amount=amount, capacity=capacity)

This works perfectly for a boat of capacity 2, but for some reason I don't get the minimal value correct for other capacities

get_comb is used to get all combinations possible for a number n, this allows me to know what are the possibilites to substract for each capacity

it's been multiple hours that I'm on it, still can't figure out why the value isn't correct for capacities > 2

[idle zephyr]

explain diff between these approch

def reverse_linearly_iter2(N):
    if N >= 1:
        print(N)
        reverse_linearly_iter2(N - 1)```
```py
def reverse_linearly_iter2(N):
    if N >= 1:
        reverse_linearly_iter2(N - 1)
        print(N)

i feel like bottom one has extra step since after base case match it has to wind up also

[vocal gorge]

you might be interested in running this - the difference will be very visible. ||the prints will be in opposite orders||.

[remote anchor]

I think in first one the N will print first and then function call means recursion will happen
And in second one first function call will take place and then N will going to print

For example let's say N is 5
Then in first one N print first means 5 will print first and then function call happen which minus one from the N
So in this way it will print 5,4,3,2,1

But in second one function call happen first means N will decrease first so N is going to be the one if we subtract it again it will return nothing means that function call is finished and 1 is going to print which then return and 2 will print in this way it will print 1,2,3,4,5

I don't know I explain well or not but if you will say I will try to write it down on paper to help you in understanding

[idle zephyr]

that's the very obivous thing you'll notice but i wanna know their call stack behavior, is 2nd one have do one extra step

[outer rain]

it might have been, if "compiler" was doing tail recursion optimizations, but it doesn't

any relatively advanced compiler will optimize both of those functions into a loop, so there will be no difference whatsoever

python does not do that

afaik lua unwraps only the first form of tail recursion

LLVM optimizes both into the loop

[outer rain]

CPython*, I don't know about alternative python runtimes like PyPy or Cython

[hidden steeple]

Hello, relative python newb trying to get my head around low level data manipulation. Starting with the simplest first step I'm trying to xor a single byte in an array. I have a unit test:

def test_xor_byte():
    data = bytearray(b'00000000')
    data[0] = data[0] ^ 0x2a
    assert data == b'2a000000'

when I run it, I get:

E       AssertionError: assert bytearray(b'\x1a0000000') == b'2a000000'
E         At index 0 diff: 26 != 50
E         Use -v to get more diff

[hidden steeple]

it's not obviously an endianness or sign thing, and I'm a little baffled

[haughty mountain]

did you intend those to be 4 bytes of data?

[hidden steeple]

yes

[haughty mountain]

it's not

you want something like

b'\x00\x00\x00\x00'

[hidden steeple]

ok. what is it interpreting it as without those escapes?

[haughty mountain]

what you have now is 8 '0's where the 0 ends up being the ascii value for 0

48

!e

print(list(b'00000000'))
print(list(b'\x00\x00\x00\x00'))

[halcyon plank]

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

001 | [48, 48, 48, 48, 48, 48, 48, 48]
002 | [0, 0, 0, 0]

[hidden steeple]

ok, and I see it works with the correct escapes. but why was the second byte/char changing then? I'd expect byte 0 to be off (48 ^ 42 instead of 0 ^ 42 like I expected), but what's happening with byte 1?

[haughty mountain]

!e

print(hex(48 ^ 0x2a))

[halcyon plank]

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

0x1a

[haughty mountain]

checks out

[haughty mountain]

nothing happens with byte 1

[hidden steeple]

ah I see, it's formatting it according to the original literal, so it's comparing bytes to bytes but printing bytes vs chars

[haughty mountain]

right, it tries to print as much as possible as printable characters

it's a very string-like type

[hidden steeple]

thanks, that makes sense, I feel less crazy now

[fiery cosmos]

Hey, guys. Can someone help me with this perhaps simple issue:
I have an array that looks like the first image, when printed out, and has a shape of (13, 5, 40959).

I have another array that looks like the second image, but its shape is (13,5). However, I know for a fact it isn't, and when I do array[2][3].shape (for example), I do get the remaining dimension's size (1, 40959). The algorithm I have only works on arrays that have the latter's format; how do I get the first one to be like the second one?

[narrow mica]

why would you do that instead of just instantiate with the child class?
maybe some context?

[mint jewel]

You can override __new__, but the more common approach is indeed a factory method as you found.

[narrow mica]

I don't think I get it, so I guess just take lakmatiol's advice and use factory methods

[idle zephyr]

im just getting started in DSA and as always im getting bogged down by my own thoughts and completely surrounded by doubts,
like in recursion if a function isnt using call stack/backtracking or just doing top down recursion feels like im cheating and havent fully grapsed the concept

[mossy finch]

well recursion is a simple concept

you dont have to get things complicated

recursion has some conditions

[narrow mica]

why would top down recursion be cheating?
it's a very powerful tool yes, no reason that using it would be somehow cheating

[mossy finch]

1. the recursion loop should stop after a finite number of calls

2. the function should call itself atleast 1 time

3. the condition should be valid for the recursion to stop

wait, ig i got it wrong

[idle zephyr]

the problem is if their is some changes in problem i feel like concept isnt clear or i've missed something
i.e print N to 1 without using +

[mossy finch]

you didnt mean that right

i mean, about recursion

[idle zephyr]

maybe i need lot more practice and white board brain storming

[mossy finch]

well

[idle zephyr]

im relying on trial and error while writing code which isnt good

[mossy finch]

wdym print N to 1 without +?

[mossy finch]

getting errors is good so that you will know the ways to fix it

anything is not for bad

always be positive

[agile sundial]

why should I call itself at least once?

[mossy finch]

because if the recursion function doesnt call itself atleast once, it's not a recursive function

a recursive function may not call itself sometimes based on it's recursion condition

[agile sundial]

fib(n) is recursive, but fib(1) doesn't call itself

[mossy finch]

it does

it's not based on the parameters

it's about the condition

like

[agile sundial]

unless you have a different definition of "call". the definition of fib(n) does call itself, but the recursive call is not executed for fib(1)

[mossy finch]

def fib(n):
  return fib(n-1) if n == 1 else 0

assume this is the condition (it is false but possible)

it is a recursive function

so it's about the condition

rather than the parameter used

[mossy finch]

as i said, it's about the condition not the parameter

[agile sundial]

¯_(ツ)_/¯

[mossy finch]

¯_(ツ)_/¯

[whole flicker]

Is there somebody here that feels very confident with trees, specifically expression trees?

i need some help

[lilac cradle]

I thought a possibly silly way of approximating a sine for however far as you want with a finite term polynomial

[lilac cradle]

Just get a polynomial approximation for at least one ‘loop’ of the sine, then use the modulus of the input for it

maybe even just something like ‘x^3’

ill mess around in desmos for it in a sec

[outer rain]

you are a few steps away of reiventing taylor series 😊

[lilac cradle]

what i mean is not having to add more as you go

If you just mod it, and the ‘jump’ fits well (might need some tweaking to get it continuous) you should be able to use a simple one

since sine, cosine, and tangent are all periodic

[outer rain]

I mean, yeah, that's how you calculate sine with taylor series

[lilac cradle]

Isnt a taylor series an infinite polynomial?

[outer rain]

you mod it 2pi, then map to the [0, pi/2) segment, then calculate taylor on that segment

[idle zephyr]

is acceptable way or do i have use double for loop to signify rows and columns

for i in range(n + 1):
    remaining = n - (n - i * 2) - 1 # how many remaining space we need each side
    print(f"{' '*(n-i)}{'*'*remaining}{' '*(n-i)}")

pyramid pattern

[outer rain]

it is, but you can take a finite number of coefs

there are even a few ways to estimate the error if you only take the first few monomials

(https://en.wikipedia.org/wiki/Padé_approximant although the generalized Pade series might be a better way to do that)

[outer rain]

what's the problem?

[lilac cradle]

This probably wont work for any precise usage of sine in terms of its shape unless you use a more complex polynomial btw

im gonna just try x^3 since it has that ‘bend’

[idle zephyr]

their is isnt any problem, but in pattern printing is it necessary to use double for loop

[lilac cradle]

oh wait it doesnt on its own

i might be thinking of some third order polynomial

cause it doesnt have that sort of 'n' shape i remember

x^3 - x^2, that does it i think

its very lopsided tho

does desmos even have modulo actually

i might just have to write something using matplotlib :p

[outer rain]

here is the sine (blue), sine taylor (red) (first 8 monomials, up to x^17), and the absolute error times 10000000000 (purple)

it is a hella good approximation

it is also very stupid because you need to compute factorials and big powers, but I think it should land in the floating point limit anyway

[lilac cradle]

nice

oops did modulo in the wrong thing lmao

[outer rain]

lol

[lilac cradle]

interesting

oh right

[mossy finch]

well, as i said, there's no rule on how to use stuff but there are conditions, some patterns may need 2 or more loop but some will be done with just a single loop

[lilac cradle]

oh btw while im working on this i made a simple way of doing a triangle wave, figured i'd share it here
for a triangle wave of width t, it's (abs(((x + t2) % t) - t2)-(t4)) * 2
t2 and t4 are just t/2 and t/4, since it was annoying having to write that out each time
graphing it out seems to have a weird truncation at the top but im not sure if thats the plotting messing up or my function messing up

making t even seemed to remove it from the graph

heres what it looks like
it goes from -t/2 to t/2 kinda like a sine wave

[lilac cradle]

oh the truncation is just the sampling not being granular enough

doing 2.5 made that obvious

if i do 500 samples it resolves

ignore the x axis label; i divided the input range so as to make it smooth

[outer rain]

why it is necessary? 🤔

you can do whatever the heck you want

[lilac cradle]

wdym

also you dont need the spaces after the actual triangle chars

at least i dont think you do

yeah nah

also that makes me realize why my methods of making a triangle out of chars like that have been so difficult to get right
i've been tending to use str.rjust or smth like that but that only gets it to a specific length, not add length

[lilac cradle]

this is a bit weird, but you can do this py print(f"{'':>{n-i}}{('*'*remaining)}")

[lilac cradle]

it's because of how string formatting works

the :> is to pad the string (which is empty) with a right facing alignment to n-i chars using spaces(by default it uses spaces for padding)
you can also just have it go into the actual tri string

here's about as simple as it gets afaik

for i in range(1,n+1):
    r = (i*2)-1
    print(f"{('*'*r):>{r+(n-i)}}")

[haughty mountain]

!e for full terribleness, one-liner

n=6
print("\n".join(f"{('*'*(2*i + 1)):>{n + i}}" for i in range(n)))

[halcyon plank]

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

001 |      *
002 |     ***
003 |    *****
004 |   *******
005 |  *********
006 | ***********

[idle zephyr]

All Armstrong numbers in given range

def armstrong_number(inp_range):
    all_armstrong_numbers = []
    for n in range(10, inp_range + 1):
        power = 0
        copy_inp = n
        armstrong_number = 0
        # get number count which will be then used as power
        while copy_inp > 0:
            # remove last digit until it reduces to 0 or less
            copy_inp = copy_inp // 10
            power += 1
        copy_inp = n

        while copy_inp > 0:
            # get last digit of number apply power
            last_digit = copy_inp % 10
            armstrong_number = armstrong_number + last_digit**power

            # remove last digit
            copy_inp = copy_inp // 10

        if armstrong_number == n:
            all_armstrong_numbers.append(armstrong_number)
    return all_armstrong_numbers

[mystic grail]

def countFrequency(n: int,m: int, List):
    hash_table = [0] * n
    for num in arr:
        if num>n:
            continue
        else:
            hash_table[num] += 1
    return hash_table[:n+1]

[mystic grail]

You are given an array 'arr' of length 'n' containing integers within the range '1' to 'x'.

Your task is to count the frequency of all elements from 1 to n.

Note:
You do not need to print anything. Return a frequency array as an array in the function such that index 0 represents the frequency of 1, index 1 represents the frequency of 2, and so on.
Example:
Input: ‘n’ = 6 ‘x’ = 9 ‘arr’ = [1, 3, 1, 9, 2, 7]
Output: [2, 1, 1, 0, 0, 0]

Sorry for this long post, but, I'm stuck here

https://www.codingninjas.com/studio/problems/count-frequency-in-a-range_8365446?utm_source=striver&utm_medium=website&utm_campaign=a_zcoursetuf&leftPanelTabValue=PROBLEM

this is the question

I am using hashing concept to solve it but it is throwing me runtime error

[haughty mountain]

no need to use any hash based stuff here

just start with a list of x zeroes and increment stuff

[mossy finch]

well your method is almost right, but you should increment the value of the index num-1 because you're starting from the int 1 but the index value of it will be 0 and the second argument of it is not for nothing, you should use it too, it's the range it would check for, that mean, if the arr has a number that is out of range, the frequency of it will be 0, for example, if n is 5 and m is 4 and the arr has a value 5 or greater, then the frequency will be 0

here's the right way to do it

[mossy finch]

def countFrequency(n, m, arr):
    table = [0] * n
    for i in arr:
        if i > n or i > m:
            continue
        table[i-1] += 1
    return table

[fiery cosmos]

!e print("Hello")

[halcyon plank]

@fiery cosmos :white_check_mark: Your 3.12 eval job has completed with return code 0.

Hello

[fiery cosmos]

bruh no way their is an inbuilt python

[fiery cosmos]

from typing import List

def countFrequency(n: int, m: int, arr: List[int]) -> List[int]:
    hash_table = [0] * (n + 1)
    for num in arr:
        if num > n:
            continue
        else:
            hash_table[num] += 1
    return hash_table[:n + 1]

# Test the function
n = 6
x = 9
arr = [1, 3, 1, 9, 2, 7]
print(countFrequency(n, x, arr))  # Output: [2, 1, 1, 0, 0, 0]```

[tough knot]

Greetings guys

Hope all are well. Quick question, can someone help me write a python function that takes a matrix that uses MSB (Most Significant Bit first) convention, and convert it to LSB?

So, given

a = [[1, 0, 0, 0],
     [0, 1, 0, 0],
     [0, 0, 0, 1],
     [0, 0, 1, 0]]

It would return

b = [[1, 0, 0, 0],
     [0, 0, 0, 1],
     [0, 0, 1, 0],
     [0, 1, 0, 0]]

a here is the CNOT operator. So, instead of taking 10 -> 11 (where 1 is the control bit), it would take 01 -> 11. You see how the order changed? I want to write a function that does this.

[cinder maple]

a=[1,2,5,4,6]
x=10
flag=0
for i in range(len(a)):
    if a[i]==x:
        flag=1
        break    
if flag==0:
    print("Not found")
else:
    print("Found")```

is there a better way to implement this?

like i want to refactor this code

[mossy finch]

@fiery cosmos it's easier, why are you complicating stuff? and it's been answered alrdy

[naive oak]

the entire loop is just the same as flag = x in a

[lean walrus]

if x in a: ... else: ...

[mystic grail]

whats wrong with this approach? it is not working

I guess, I need to make some changes in the condition

[mossy finch]

there's no variable named arr

it's edges ig

[mossy finch]

everything's fine but there's no variable named "arr" exists

it's probably edges

[mossy finch]

and the condition is not fully responsive to the output needed, you are not passing the second variable m in the function call for nothing

[mystic grail]

it still didn't work 😦

[mossy finch]

ah, lemme try that

[mystic grail]

https://www.codingninjas.com/studio/problems/count-frequency-in-a-range_8365446?utm_source=striver&utm_medium=website&utm_campaign=a_zcoursetuf&leftPanelTabValue=PROBLEM

[mossy finch]

ah mb

you see the last argument's type?

it's a list of list of int

means it's a 2d array

or a matrix

[mystic grail]

so what should I understand from that?

[mossy finch]

from typing import *

def countFrequency(n: int, m: int, edges: List[List[int]]):
    table = [0]*n
    for i in edges:
        if i <= n:
            table[i-1] += 1
    return table

this worked

as i said

it was edges

you might have did some mistake

but it worked

[mossy finch]

actually m had no use

[mossy finch]

and the edges is a normal list of int

[cosmic swallow]

trivia!! what does this tree spell out if we traverse post order from right to left?

cmon please just answer i need to prove my classmates wrong

[agile sundial]

[cosmic swallow]

please

is it clustering?

[cosmic swallow]

man please i need

[lean walrus]

it is

[mossy finch]

yep it is clustering

you can try traversing it with this code

class bst:
    def __init__(self, val = None, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right

tree = bst('g', 
           bst('n', bst('i', None, bst('r')), bst('e', bst('t'))),
           bst('s', bst('u', None, bst('l')), bst('c'))
           )

l = []

def trav(node):
    if node is not None:
        trav(node.right)
        trav(node.left)
        l.append(node.val)
trav(tree)
print(''.join(l))

this is just to test your tree

[cosmic swallow]

time to prove my people wrong

[cosmic swallow]

you dont even need to code it in just draw it out with brain

[mossy finch]

well, that's just to let him test that by himself

[mossy finch]

^

if u didnt read the last msg

seems like he's learning so that'd help him

ntg's wrng with that

[agile sundial]

looks like your terminal doesn't support displaying that character

[main bison]

ok, what other extensions do you have installed?

[fiery cosmos]

If I do it directly in the terminal, it works. But using vs code it looks like this...

[main bison]

just want to see all the extensions you have installed

[fiery cosmos]

of python, I only installed these

[fiery cosmos]

Ah, ok

[main bison]

no, all extensions you have installed please

[main bison]

disable code runner

restart and try again

[fiery cosmos]

what?! It worked. How did you know that was it? I would never find out.

[glossy remnant]

Anyone wanna join my java Minecraft server/SMP DM me

[main bison]

i saw it in the screenshot and i have seen this issue before

this is not default vscode, it is made by an extension

[main bison]

!ot

[halcyon plank]

Off-topic channel

#ot2-never-nester’s-nightmare

Please read our off-topic etiquette before participating in conversations.

[agile sundial]

(this is offtopic for #algos-and-data-structs )

[main bison]

yeah but our channel names are not easy to translate via click copy and paste. so we can let someone that uses google translate some slack

[fiery cosmos]

I understand, I need to pay more attention to these things, vs.code is good for everything. However, at the same time, this can happen, right? I didn't even know what the default was, since when I installed it I use extensions lol. Thank you very much

[main bison]

now you know, good luck! come back and ask us again if you need more help 😄

[fiery cosmos]

thanks

[fiery cosmos]

sorry

[main bison]

no worries, we told you to pick a help channel, and there are many topical channels in this server. they are hard to translate i get that.

[frail zinc]

def get_rkey_from_ddiff(ddiff_str):
    start_idx = ddiff_str.rfind('[')  # Search from the end of the string
    end_idx = ddiff_str.find(']', start_idx)  # Search for ']' starting from start_idx

    ret = ddiff_str[start_idx + 1:end_idx]

    ret = ret.replace('\\', '')
    ret = ret.replace("'", '')

    return ret


key_changed = "root['line_items'][0]['replacement_lineitem_ids'][0]"
key_changed = get_rkey_from_ddiff(key_changed)
print(key_changed)  # Output should be "replacement_lineitem_ids"

I need serious help. Been stuck on this for an hour. I am trying extract the replacement_lineitem_ids string and it's not working.

I figured it out

Lmfao

[agile sundial]

is key_changed a line of code? this seems very odd

[hardy adder]

wow

[frail zinc]

Yeah the line of code is something like for key_changed, obj_added in items_added

I used the DeepDiff library

[agile sundial]

it's giving you a line of code as a string?

[frail zinc]

I don’t understand your question but “root” was assigned to the key_changed variable

[frail zinc]

Oh I thought you were talking about the screenshot lmfao

[agile sundial]

I'm talking about your code

[frail zinc]

Oh no that’s from a test file

[agile sundial]

why are you trying to extract data from a line of code

[frail zinc]

Because when you use DeepDiff and you’re comparing dictionaries, it looks like that string

So you have to create a function that extracts strings from it

[agile sundial]

seriously? that's such a horrible output type. that surely is not the case

[frail zinc]

Yeah man. Check out their documentation

[agile sundial]

link it?

[frail zinc]

https://pypi.org/project/deepdiff/

[agile sundial]

I meant the documentation for the function you're using

[frail zinc]

https://zepworks.com/deepdiff/6.7.1/diff.html

[agile sundial]

wow, that's terrible. why are you using this

you can just write a function that does this in like 5 minutes, with a decent return type

[frail zinc]

Because the predecessor developer was using it

[agile sundial]

you can just stop using it for new things

[frail zinc]

I actually like the library aside from trying to extract the differences of data

[agile sundial]

isn't the entire point of deep diff to get the differences ?

[frail zinc]

Yes

[agile sundial]

so isn't that the only thing that matters?

[frail zinc]

But I will also need the keys as well as the values if I am sending PUT requests to different API endpoints

[agile sundial]

i don't see how that's relevant. the fact is that this library has an absolutely terrible interface, and the function it provides is easily emulated and improved

[frail zinc]

different items can also be added in a dictionary. So why would write different functions when there’s a library already available for me to use?

[agile sundial]

because the library is horrible

i also don't know what you mean by "different items can also be added in a dictionary"

[frail zinc]

Well relevant because it’s the foundation of how changed data gets updated

[agile sundial]

my point isn't to stop taking diffs of the data, it's just to stop using this library to do that

[frail zinc]

What do you precisely have in mind other than DeepDiff?

[agile sundial]

#algos-and-data-structs message do it yourself

[barren coyote]

Here's one: https://github.com/darbiadev/darbiadev-utilities/blob/main/src/darbia/utils/mappings.py#L9-L45
The SO link I got it from is in the docstring

[agile sundial]

wow, absolutely no info on what format the comparison results will be in 😩

[ripe flax]

Has anyone here taken the DSA course offered by front end masters

PrimeAgen teaches it

Also the course by Robert segwick on coursera- anyone have any thoughts on those??

[haughty mountain]

This doesn't recursively diff, does it?

[barren coyote]

No

[mystic grail]

sorry, I fell asleep at that time

and thanks a lot for helping, you are great 🙂

[mossy finch]

yw

[feral condor]

can someone help me figure out which sorting algorithm i came up with?

grab a value, drop it when you find a bigger one. once you hit the end of the list come back the same way but for smaller values each time. (additionally delete each sorted value from the algo)

[mint jewel]

I think this is coctail shaker sort if I understand it right, just storing the value out of place, rather than swapping it along until a better one comes along.

[feral condor]

let me take a look

[agile sundial]

yeah cocktail sort

[feral condor]

wohoo! thanks!

it is!

[glossy remnant]

Anyone wanna join my java Minecraft server/SMP DM me

[runic tinsel]

it's selection sort

or maybe you did mean actual bubbling

it kinda describes both equally well

show the code

[whole aurora]

it's not bubble sort?

the biggest item finds its way to the end each time

[haughty mountain]

if it started from the beginning every time it would be

cocktail sort goes alternating ways

bubbling up and down every other iteration

[feral condor]

it's the coctkail sort

[empty yarrow]

can anyone explain how the objects created by this know name when the parameter is not referenced in the function body of __init__?

[vocal gorge]

they don't. name is unused here.
EDIT: oh huh, I see. weird; i suspect the str constructor cheats somehow.

Specifically, it seems to be impossible to override the str constructor. Symbol.__init__ doesn't get used here, it just goes straight to str's.

It seems it's handled by str's __new__, and you need to override that to make a properly-behaving string subclass.

[mint jewel]

use collections.UserString

^@empty yarrow@vocal gorge

[empty yarrow]

thx

[fiery forge]

How can I optimise my code for speed?

queue = input()
room = []
new = ''
for item in queue:
room.append(item)
length = len(room)
if length % 2 == 0:
length -= 1
room.sort()
new += (room[(length//2)])
print(new)

[glossy remnant]

Anyone wanna join my java Minecraft server/SMP DM me

[narrow mica]

notice that it says single digits, that means that each item only has 10 possible values it can take
instead of storing each individual item in the room, keep a counts list where counts[n] == how many n's are in the room

[glossy lintel]

i'm trying to make a matrix that is n dimensions(ofc n is a integer that is above 1)

A 2D matrix is simple as nesting arrays, nothing too special

where it gets challenging both on how the user passes the arguments

is 3D and above

[vocal gorge]

the term is usually "n-dimensional array" (hence numpy's ndarray) or "tensor" (though the latter has math connotations). In general it's just a matter of having a 1d array of (n-1)-d arrays, though.

[glossy lintel]

mhm

tbh for 3D matrix i think of slicing it to 3 matrices that are 2 dimensional

for 4D, this is when it gets confusing

[vocal gorge]

a 2d array is just a bunch of same-size 1d arrays stacked along the second axis. a 3d array is just a bunch of same-shape 2d arrays stacked along the third axis. a 4d array is just a bunch of same-shape 3d arrays stacked along the fourth axis. and so on.

[glossy lintel]

mhm

[west birch]

is there something like Jaccard Similarity, but that can handle minor typo's like DamaruLevenstien ?
or i mean, i could write a jaccard that could handle the typo's using damarulevenstien - but i think that would kill its efficiency...
long story short, i have 2 lists of keywords, i want to see how similar they are, but one list is user input and could contain minor typos.
not sure, maybe im going about it the wrong way. i have a structure of data with keywords assigned to each.. trying to find best match based on the keywords input by the user, whilst being able to handle minor misstypes

[west birch]

to give some context, i was trying to come up with an efficient way to store and index a list of "lore Entries" {title, description, keywords}
in the end i came up with this, using a custom "ReferencedTrie" structure, (just a Trie where every end node holds a list of uuid's to "something")
using the keywords as the prefixes. this allows for fast indexing/retrieval of data based on the keyword that references it. and also allows for autocompletion of indexed keywords (or strings) --- but i cant work out how to effectively find "closest match" on a given list of user provided keywords when said keywords could contain minor misstypes. its a useful little structure, efficient as the complexity is based on the length of the strings. (can be memory intensive though, but also has the benefit of "compressing" common prefixes, english is full of them)

"preprocess_text" takes a sentence and stems it to extract potential keywords from a longer string. - it works but not well. need a better method.

[west birch]

best i can think is to do something like this, (from my ts version) but this feels like the wrong way, and does slow down Damerau (not enough to be an issue, but not sure about that)

[vocal gorge]

Is there a faster-than-n^2 algorithm for calculating the pareto frontier of a set of points?
Here's my current solution, which is nicely vectorized and readable but O(n^2):

def pareto_frontier(df: pd.DataFrame) -> list[int]:
    return [i for i, el in df.iterrows() if (el>=df).any(axis=1).all()]

[haughty mountain]

2d points?

if so sort in decreasing order of x and go through the points, if the y is the biggest one seen so far it's on the frontier

if I understand the constraint correctly

[keen hearth]

I'm not sure, but I found this blog post which has some ideas: https://maxhalford.github.io/blog/skyline-queries/

TIL there was a proposal to add an operator for this to SQL https://en.wikipedia.org/wiki/Skyline_operator

[empty hound]

I don't understand. How did the highlighted node go from 1 to 2?

[vocal gorge]

No, any number of dimensions. Interesting idea, though. I wonder if that generalizes.

One thing I note is that I think the pareto frontier is part of the convex hull, and a convex hull can be calculated in O(n log n), IIRC.

[vocal gorge]

oh, nice, it shows a nice iterative algorithm and by that keyword I found a paper (Tiakas 2015) with a bunch of more

the python implementation of the BNL algorithm is way slower than my naive-but-vectorized one, though 🥴

[whole flicker]

is there someone in here that is experienced with expression trees, i am really struggling with one final bug and I need some help

[steady osprey]

ohh... i needed help in a DSA question in c++. Could u help me out?

[whole flicker]

@steady osprey you know this is a python discord?

[steady osprey]

no.. they told me i could ask about other langs in other channels as many use different langs too

[whole flicker]

ay alr whats ur question?

[steady osprey]

it's based on Dota 2

too long.. should i dm u or send here?

[vocal gorge]

it becomes faster via numba, but my original solution benefits from numba even more and still wins

[whole flicker]

sure dm me

[keen hearth]

Take a look at the call stack on the right. The Inorder(1) call returned, because it reached the end of the function. When a function call returns, its frame is removed from the top of the stack.

[whole flicker]

https://discord.com/channels/267624335836053506/1218879790183092325
Is someone able to help me with this tree problem? I cannot seem to fix my bug

[glossy lintel]

~1 Million Bytes Used // Linked List
532 Bytes Used // Lazily Loaded Linked List(First Node Loaded)
104 Bytes Used // Python's Built In List

I ran some memory tests with

def verboseGenerator():
    yield 15e30000
    yield "39000000000"
    yield [*range(100)]
    yield {*range(5000)}

Here is the __sizeof__ function for SinglyNode

    def __sizeof__(self) -> int:
        dataValSize = self.data.__sizeof__()
        slotsSize = self.__slots__.__sizeof__()
        return dataValSize + slotsSize

And for SinglyLinkedList

    def __sizeof__(self) -> int:
        target = self.starting_node
        slotSize = self.__slots__.__sizeof__()
        seqSize = self.__sequence.__sizeof__()
        lengthSize = self.__nodes_length.__sizeof__()
        tailNodeSize = self.__ending_node.__sizeof__()
        pre_tailNodeSize = self.__pre_end_node.__sizeof__()
        currNodeSize = self.__current_node.__sizeof__()
        sizeSum = slotSize + seqSize + lengthSize + currNodeSize + pre_tailNodeSize + tailNodeSize
        for _ in range(self.__nodes_length):
            sizeSum += target.__sizeof__()
            target = target.point
        return sizeSum

There are 2 questions

• Is anything wrong with both of the functions?
• How can i optimise the memory of the linked list(im aware that python's built in list is made in C but i still wanna closely match the level)

[outer rain]

some __slots__ trickery maybe? https://stackoverflow.com/questions/472000/usage-of-slots

[glossy lintel]

i mean i already did that

[glossy lintel]

for the first question btw?

[outer rain]

I am a bit concerned about __slots__.__sizeof__

isn't it static?

[solar bone]

can we make 3d games using py?

[outer rain]

like, it takes space in SinglyLinkedList object, but not in instance

[outer rain]

I am sure you can, but #game-development seems to be a better place to ask this question

or just #python-discussion

[solar bone]

ok

[glossy lintel]

oh

ok then il remove it

Now looks like

1 Million Bytes Used
300 Bytes Used
104 Bytes Used

[fiery cosmos]

Anyone learning DSA with Python

[glossy lintel]

this channel is literally about that(well not for learning part but assume most of us do learn)

i do learn some stuff tho

[fiery cosmos]

Did u learn DSA with Python

[glossy lintel]

i learnt broadly

like not in python, but generally the theory

its nothing too complex(Linked lists, graphs, trees... etc)

and wasn't even focusing purely on it

[lunar jacinth]

hey all,

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        ans = []
        seen = set()

        def dfs(matrix, row, col, isUp):
            if row < len(matrix) and row >= 0 and col < len(matrix[0]) and col >= 0 and (row, col) not in seen:
                seen.add((row, col))
                ans.append(matrix[row][col])

                if isUp:
                    dfs(matrix, row-1,col,True)
                dfs(matrix, row, col + 1, False)  # Move right
                dfs(matrix, row + 1, col, False)  # Move down
                dfs(matrix, row, col - 1, False)  # Move left
                dfs(matrix, row - 1, col, True)   # Move up

        dfs(matrix, 0, 0, False)
        print(seen)
        return ans
``` Would anyone know why the only "True" is for moving up?

How does it pop out from the true. Is it because if it sees that (row,col) is in seen?

This is the question :

[mossy finch]

well seems like there's no need for the isUp parameter

the behavior is similar even without the isUp

[lunar jacinth]

Solution does not work if there is no if statement there

I think if it needs to go up again?

like lets say there are 4 rows, then it needs to go up twice right

[vocal gorge]

Think about a big matrix. First you move to the right wall, then the movement right stop working and you move down instead, similarly for the bottom wall... but then, once you start moving up, you need to continue doing so (rather than moving right as soon as you start being able to) until you are no longer able. That's what that if-statement and the parameter are for.

[lunar jacinth]

so if we have ```
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

then it would move right to 6,7, down to 11, and left 10?

[red quiver]

hi guys can u give me the name of the DSA ytb channel that was founded by two guys and when one of them passed away the other stopped posting videos

[sturdy mauve]

Farmer John has a permutation p of length N (2≤N≤105), containing each positive integer from 1 to N exactly once. However, Farmer Nhoj has broken into FJ's barn and disassembled p. To not be too cruel, FN has written some hints that will help FJ reconstruct p. While there is more than one element remaining in p, FN does the following:

Let the remaining elements of p be p′1,p′2,…,p′n,

If p′1>p′n, he writes down p′2 and removes p′1 from the permutation.
Otherwise, he writes down p′n−1 and removes p′n from the permutation.
At the end, Farmer Nhoj will have written down N−1 integers h1,h2,…,hN−1, in that order. Given h, Farmer John wants to enlist your help to reconstruct the lexicographically minimum p consistent with Farmer Nhoj's hints, or determine that Farmer Nhoj must have made a mistake. Recall that if you are given two permutations p and p′, p is lexicographically smaller than p′ if pi<p′i at the first position i where the two differ.

INPUT FORMAT (input arrives from the terminal / stdin):

Each input consists of T independent test cases (1≤T≤10). Each test case is described as follows:
The first line contains N.

The second line contains N−1 integers h1,h2,…,hN−1 (1≤hi≤N).

OUTPUT FORMAT (print output to the terminal / stdout):

Output T lines, one for each test case.
If there is a permutation p of 1…N consistent with h, output the lexicographically smallest such p. If no such p exists, output −1.

SAMPLE INPUT:

5
2
1
2
2
4
1 1 1
4
2 1 1
4
3 2 1
SAMPLE OUTPUT:

1 2
-1
-1
3 1 2 4
1 2 3 4
For the fourth test case, if p=[3,1,2,4] then FN will have written down h=[2,1,1].

p' = [3,1,2,4]
p_1' < p_n' -> h_1 = 2
p' = [3,1,2]
p_1' > p_n' -> h_2 = 1
p' = [1,2]
p_1' < p_n' -> h_3 = 1
p' = [1]
Note that the permutation p=[4,2,1,3] would also produce the same h, but [3,1,2,4] is lexiocgraphically smaller.

For the second test case, there is no p consistent with h; both p=[1,2] and p=[2,1] would produce h=[1], not h=[2].

Can anyone help with this problem?

[glossy remnant]

Anyone wanna join my java Minecraft server/SMP DM me

[agile sundial]

does it involve dsa ?

[haughty mountain]

dig straight ahead

[muted shoal]

!warn 1003291229901045832 Please respect the topic of the channel and do not advertise in the server as stated in our rules.

[halcyon plank]

:incoming_envelope: :ok_hand: applied warning to @glossy remnant.

[fiery cosmos]

@agile sundial hello

[fiery remnant]

Thoughts on dsa course by google?

Ping me if u reply pls.

https://techdevguide.withgoogle.com/paths/data-structures-and-algorithms/

[stone sinew]

Q. insertion sort, selection sort and
merge sort which is the most suitable sorting algorithm based on asymptotic running time:
I have a custom data structure, DS1, that organizes k items and
supports two operations:
DS1.get_at_index(j) takes constant time, and
DS1.set_at_index(j, x) takes Θ(k log k) time.
and task is to sort the items in DS1 in-place.

[stone sinew]

Would merge sort be the right aproach here

[raw lion]

hello fellas i need some more info in my program ,where some problem CANNOT RETRIEVE DATA FROM THE WEB

https://pastebin.com/0aK5hGjA this link

[lunar jacinth]

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:

        buckets = []
        freq_dict = {}
        ans =[]

        for i in range(len(nums) + 1):
            buckets.append([])

        for num in nums:
            if num not in freq_dict:
                freq_dict[num] = 1

            else:
                freq_dict[num] += 1

        for num, freq in freq_dict.items():
            buckets[freq].append(num)

        print(buckets)

        for num in range(len(nums), -1, -1):
            for num in buckets[num]:
                ans.append(num)
                if len(ans) == k:
                    return ans

``` is this O(n) time complexity?

[keen hearth]

Yea I think so. Benchmarking also seemed to confirm that (multiplying the length of nums by 10 roughly multiplied the running time by 10).

[nav] In [20]: %%timeit nums = random.choices(range(100), k=100)
          ...: f(nums, 10)
          ...:
18.4 µs ± 121 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

[nav] In [21]: %%timeit nums = random.choices(range(100), k=1000)
          ...: f(nums, 10)
177 µs ± 1.66 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

[nav] In [22]: %%timeit nums = random.choices(range(100), k=10000)
          ...: f(nums, 10)
1.78 ms ± 5.45 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

[nav] In [23]: %%timeit nums = random.choices(range(100), k=100000)
          ...: f(nums, 10)
18.6 ms ± 108 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

[nav] In [24]: %%timeit nums = random.choices(range(100), k=1000000)
          ...: f(nums, 10)
214 ms ± 5.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

[honest rose]

@simple lance

[glossy remnant]

Anyone wanna join my java Minecraft server/SMP DM me

[simple lance]

?

[snow anvil]

@muted shoal this man right here

[muted shoal]

!ban 1003291229901045832 Promotion is against our rules and you are clearly not interested in following them.

[halcyon plank]

:incoming_envelope: :ok_hand: applied ban to @glossy remnant permanently.

[sullen ridge]

How can we calculate the frequency of given keywords in a large article (>10k words) in the most efficient way?

➡️ I'm thinking about trie data structure for efficient searching and sorting procedures.
also well suited for keyword searching.

[keen hearth]

I would extract the words with a regular expression, then count them with collections.Counter.

E.g. ```py
from collections import Counter
import re

WORD = re.compile(r"[a-zA-Z']+")

with open('article.txt') as file:
counts = Counter(WORD.findall(file.read()))

collections.Counter is a dictionary that is specialised for counting things. Every key has a default value of 0.

https://docs.python.org/3/library/collections.html#collections.Counter

[acoustic thunder]

Hello, I would need some help with a minimax algorithm, which is supposed to solve a cards game, I understand the idea but don't really know how to implement it in python, can anyone here help me out ?

[toxic hare]

https://media.discordapp.net/attachments/1218387166028365955/1219560446126850138/sort.gif

i animated my sorting algorithm :3

[haughty mountain]

have you looked at radix sort?

in a way it's a different generalization of counting/bucket sort

(and should be a lot more memory friendly)

[toxic hare]

yeah ive seen it i just havent gotten around to programming it yet

[quaint perch]

what software are you using

for that

[toxic hare]

pixel art studio Free

im drawing myself lols

[quaint perch]

ohh
using python right

[toxic hare]

https://media.discordapp.net/attachments/988398056699490348/1219662671444578354/pigicount.gif

i made a bigger animation

[toxic hare]

the sorting algorithm is on python yeah https://pypi.org/project/pigi/

[agile sundial]

really cool animation

[toxic hare]

tyy

[quaint perch]

so uh, i made a prng and its very bad (maybe bcos seed?)```py
def lfsr16(seed):
state = seed % (1 << 16)
while True:
shifted_bit = (state & 1<<1) ^ (state & 1<<0)
state >>= 1
if shifted_bit:
state += 1 << 15
yield state

def main():
rng = lfsr16(20000)
for i, n in enumerate(rng, 1):
if i > 100:
break
print(f'{n:05}', end=(' ' if i % 10 else '\n'))

if name == 'main':
main()
result
10000 05000 02500 01250 33393 49464 24732 12366 38951 52243
58889 62212 31106 48321 56928 28464 14232 07116 03558 34547
50041 57788 28894 47215 56375 60955 63245 64390 64963 65249
65392 32696 16348 08174 36855 51195 58365 61950 63743 64639
65087 65311 65423 65479 65507 65521 65528 32764 16382 40959
53247 59391 62463 63999 64767 65151 65343 65439 65487 65511
65523 65529 65532 32766 49151 57343 61439 63487 64511 65023
65279 65407 65471 65503 65519 65527 65531 65533 65534 65535
65535 65535 65535 65535 65535 65535 65535 65535 65535 65535
65535 65535 65535 65535 65535 65535 65535 65535 65535 65535

wait a min i think i made a mistake which is why

i forgot to shift the second bit back after extracting it

[fiery cosmos]

can you pop from a list and will it actually remove that element

[solemn moss]

del A[-1]
A.pop()

[agile sundial]

I'm not sure what you're asking. popping removes an element

[fiery cosmos]

ok ty

i just did an easy LC reasonably quickly and am happy with it but i can tell it has needless try/except blocks and the logic could be much cleaner:

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        word1_ind = [x for x in range(len(word1),-1,-1)]
        word2_ind = [x for x in range(len(word2),-1,-1)]
        outstring = ''
        longer = len(word1)-len(word2)
        if longer >= 0:
            while word1_ind:
                try:
                    outstring += word1[word1_ind.pop()]
                    outstring += word2[word2_ind.pop()]
                except IndexError:
                    try:
                        outstring += word1[word2_ind.pop()]
                    except IndexError:
                        pass
        elif longer < 0:
            while word2_ind:
                try:
                    outstring += word1[word1_ind.pop()]
                    outstring += word2[word2_ind.pop()]
                except IndexError:
                    try:
                        outstring += word2[word2_ind.pop()]
                    except IndexError:
                        pass
        return outstring

let me post the q description

You are given two strings word1 and word2. Merge the strings by adding letters in alternating order, starting with word1. If a string is longer than the other, append the additional letters onto the end of the merged string.

Return the merged string.

actually, if i could keep the precise logic and just write it in a way whereby the while statements obviate the need for the try blocks (e.g. they actually stop executing when the list is empty), that'd be excellent

[glossy lintel]

i kinda asked it again, but il say it anyway. Is this normal?

Traverse // 21.031161040998995
Batch Traverse // 0.02094146399940655 Seconds
Insertion // 20.154071191000185
Batch Insertion // 0.04759319299955678 Seconds
Deletion // 20.827346445999865
Batch Deletion // 0.017015639001328964 Seconds

for a 100k linked list with 30k (operations)

that is like 1000x diff

[haughty mountain]

20s sounds about right

[glossy lintel]

yes ik

but 0.02 seconds is a bit too suspiciously quick. There is just no way that it is legit

no compiled code, nor parallazation, nor anything. We are talking pure python

[fiery cosmos]

@haughty mountain what did you think of my LC solution

or any feedback would be appreciated

[glossy lintel]

!paste

[halcyon plank]

Pasting large amounts of code

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

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

[fiery cosmos]

@glossy lintel what are these numbers from

[glossy lintel]

from time testing

[fiery cosmos]

yeah no i got that. whats the data structure

[glossy lintel]

here is the code for traversing and batch traversing

[glossy lintel]

a singly linked list

https://paste.pythondiscord.com/F5NA

[haughty mountain]

I mean, it's 1 O(n) traversal with a slightly expensive operation vs 30k O(n) operations with a cheap operation

fwiw batched insertions/deletions could be equally well implemented for lists

[glossy lintel]

so its actually legit?

[haughty mountain]

I mean, it doesn't sound insanely far fetched

[glossy lintel]

oh

[haughty mountain]

like, consider ballpark estimations like this

it doesn't sound that weird

[glossy lintel]

il try to see what happens with 5 million nodes and 300k operations

[haughty mountain]

you'll not want to run that for the regular linked list...

my guesstimate would be like 10 hours

[glossy lintel]

jess

quite impressed i managed to optimise it like 1000x

[haughty mountain]

the batched one idk, 5 seconds?

[glossy lintel]

probably

[haughty mountain]

that kind of magnitude

[glossy lintel]

Batch Traverse // 0.2514129339997453 Seconds

ran batch traverse first

[haughty mountain]

that sounds less correct

I wouldn't expect the average time spent per node to go down

[glossy lintel]

yeh

[haughty mountain]

50x larger input, more operations to do

maybe double check your traversals are generated correctly, they are not near the front or something?

[glossy lintel]

i mean i iterate over 300k numbers where each have a diff of 6

like 5, 10, 15, 20, 25..... etc

[haughty mountain]

that's only 1.5M

what did you have before?

[glossy lintel]

wdym?

like iterations?

[haughty mountain]

diff of 5 like you showed would get up to like 300k*5

[glossy lintel]

yes

[haughty mountain]

so the rest of the list doesn't matter

[glossy lintel]

(it takes forever for traverse to complete)

[glossy lintel]

ig

[haughty mountain]

what were the numbers before?

for the smaller size

[glossy lintel]

^

[haughty mountain]

no, I mean the traversal pattern

every nth index for what n?

[agile sundial]

does batch insertion wait until you have accumulated enough elements for a full batch?

[haughty mountain]

I didn't re-read the code, but I'm assuming the batching does one traversal and does operations in one sweep

[fiery cosmos]

need help w LC 345

[glossy lintel]

exactly what it does

[glossy lintel]

u supply it with a pair of positions each corresponding to a node

[haughty mountain]

this matters a lot for estimating stuff, if only the first 1.5M are ever reaches, you effectively only do work on a 1.5M sized linked list

so my estimates become...off

!e

print('this much', 5/1.5, 'ish')

[halcyon plank]

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

this much 3.3333333333333335 ish

[fiery cosmos]

anyone wanna help me w leetcode 345 reverse vowels of a string

`Given a string s, reverse only all the vowels in the string and return it.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.`

i passed 479/480 test cases

i failed when they give me a gigantic string that i get "time limit exceeded"

[haughty mountain]

post code and people can say if you're doing something silly

without code we can't say more than your code probably being inefficient

[fiery cosmos]

dang i missed this. will post tomorrow

its O(n) runtime, there are no doubly nested loops or anything

[fiery cosmos]

@echo atlas

[echo atlas]

'''py
#---------------------------------------#

Implement Recursive selection sort here.

n: size of array - index is index of starting element

def recursive_selection_sort(data, data_len, index = 0):

# TODO-Remove pass and fill out the rest. 
#You may use additional user_defined functions if required.
pass
# Set the base case 
      
# Find the minimum index 
  
# Swap the data 
      
# Recursively calling selection sort function

'''

[fiery cosmos]

#---------------------------------------#      
# Implement Recursive selection sort here. 

# n: size of array - index is index of starting element
def recursive_selection_sort(data, data_len, index = 0): 
  
    # TODO-Remove pass and fill out the rest. 
    #You may use additional user_defined functions if required.
    pass
    # Set the base case 
          
    # Find the minimum index 
      
    # Swap the data 
          
    # Recursively calling selection sort function

hmm

why didnt it cover the spaces

ah

just use ` 3 times

[fiery cosmos]

class Solution:
    def reverseVowels(self, s: str) -> str:

        rev = []
        vowels = 'aeiouAEIOU'
        tochange = []

        for i in range(len(s)):
            if s[i] in vowels:
                tochange.append(i)
                rev.append(s[i])

        ret_s = ""

        for i in range(len(s)):
            if i in tochange:
                ret_s += rev.pop()
            else:
                ret_s += s[i]
        
        if len(s) == 2 and s[0] in vowels and s[1] not in vowels:
            return s

        else:
            return ret_s

Given a string s, reverse only all the vowels in the string and return it.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.

[haughty mountain]

quadratic time

[fiery cosmos]

how

[haughty mountain]

one operation you assume is O(1) is not O(1)

[fiery cosmos]

pop()?

[haughty mountain]

that's fine

[fiery cosmos]

🤔

oh

the if x in n statements

[haughty mountain]

one particular one

[fiery cosmos]

hm

well one looks through a string and the other through a list, so i would think that's the key

to the answer

[haughty mountain]

both of those are linear time in the length of the thing, but which one matters?

[fiery cosmos]

tochange matters as the size of the input grows

[haughty mountain]

right

[fiery cosmos]

interesting! i love the way you teach by slowly allowing one to get to the answer "themselves." very helpful and effective. my new approach for this problem was looking at having pointers at the beginning and end of the string but i haven't fully fleshed it out yet

i'll share when i have a new approach. may be awhile as i am also learning R

[haughty mountain]

just using a set here would work fine

[fiery cosmos]

to store all the letters to be changed?

[haughty mountain]

- tochange = []
+ tochange = set()

- tochange.append(i)
+ tochange.add(i)

[fiery cosmos]

i see. i'll give it a go! how did you do change syntax

[haughty mountain]

```diff
+ stuff
- other stuff
```

[fiery cosmos]

and why does set work better?

[haughty mountain]

you really should know this

what is a set?

what is used for its implementation?

[fiery cosmos]

a collection of distinct elements

[haughty mountain]

and for this?

[fiery cosmos]

to implement a pythonic set? i'd have to look into the docs

[haughty mountain]

it's basically the same as a dict

which is what?

[fiery cosmos]

hash table

[haughty mountain]

ok, can you answer this now?

[fiery cosmos]

it stores the number of each vowel that need replacing?

rather than many of them repeated multiple times throughout a giant list

[haughty mountain]

no, just a basic property of hash tables

[fiery cosmos]

oh its mapping which vowel is replaced with with other vowel

[haughty mountain]

no

checking if a key is in a hash table is O(1)

[fiery cosmos]

isn't it looking if a value is there is O(1) given the key?

i'm thinking location in the map is key and information is value e.g. like a dictionary key:value pair

[haughty mountain]

think about set like a dict without values

[fiery cosmos]

so it's O(1) because it goes and looks at a specific location given the inherent information in the key itself (the int)

?

i'm struggling to understand the solution now. i thought i had to store the vowels to be changed in a list or string so that the return vowels would be in the proper order

perhaps i just need to learn more about sets

considering i dreampt up a workable solution in which one minor change made it proper

oh i see what's going on

tochange was just a collection of all non vowels that had been encountered. i wasn't building my return string from there but from rev[]

or from the original string itself

[haughty mountain]

it's just storing indices, no?

[exotic parrot]

Hi! I have an assignment for college, where me and my team have to make a vehicle that will basically collect points scattered on a grid, I'm doing the programming part and as of now I've created an algorithm, but the assigment states that the algorithm has to calculate the shortest possible route for collecting the points? Can someone help me a bit?

[fiery cosmos]

sounds like travelling salesman?

https://www.routific.com/blog/travelling-salesman-problem

[agile sundial]

do you need to return back to the starting point?

[exotic parrot]

yeah

[agile sundial]

then yeah, that's TSP

[fiery cosmos]

read up on TSP problem statement and algos associated with solving it

[exotic parrot]

ohhh I see, what I did was basically a broke version of A*, with G_cost and H_cost... but I wasn't sure if it would give the most efficient route

[exotic parrot]

thanks for the link

[fiery cosmos]

np that was just a quick google, wikipedia probably more useful tbh

[exotic parrot]

I've searched everywhere for smg similar

idk how but almost every source told me A* or Dijkstra

[fiery cosmos]

depends on if you want exacting or heuristic

there are many algos to do it

[exotic parrot]

is Brute force a good idea for 6 destinations?

[agile sundial]

definitely

[fiery cosmos]

https://en.wikipedia.org/wiki/Travelling_salesman_problem#Heuristic_and_approximation_algorithms

[agile sundial]

6 you can probably do in your head, lol

[fiery cosmos]

probably? depends on the time complexity

[thin umbra]

hello

[exotic parrot]

it's exponential, I think

[agile sundial]

not really. 6 is tiny, even for a 2^n algo like tsp is

[thin umbra]

can anyone help me why this happen? print statement is correct answer but returns wrong

[fiery cosmos]

which problem is this

looks like LC

[exotic parrot]

alright, I'll give it a go than, thanks guys

[thin umbra]

yes problem 88

cnnot believe i can get error in this

[fiery cosmos]

agreed. wanted to get them thinking about how they'd know the answer

[fiery cosmos]

i haven't done this one yet myself

wait a min

[thin umbra]

easy qurstion and i make dumb mistake

i can not find my mistake after thinking so much

[fiery cosmos]

take a break

[thin umbra]

i just strted 😭

[fiery cosmos]

i can't help as i'm working on R rn but maybe someone else will weigh in

[thin umbra]

question 2 in day

[thin umbra]

ookay

[exotic parrot]

can I put my code somewhere for someone to look into? I think I basically did the Greedy version and don't want to do extra work lol

I can also try to explain what it does

basically, initial coordinates, coordinates of the points, coordinates of the walls, are given beforehand, so we have to put them in as inputs

my algorithm measures all distances between the initial position and all points using the Heuristic method, the point that returns the lowest value is chosen as 'destination', the algorithm then checks all available grid points where the car can move to, using G_cost and H_cost the algorithm then choses a grid point which would lead the car closer to the destination point, the same process is repeated until the car reaches the point, in that case the algorithm start from the beginning, scanning for closest point, checking for best tiles,.... until all points have been eaten/removed, then it does the same thing but for it's intial position to get back

[exotic parrot]

I have a slight problem

the grid will look somewhat like this

I can calculate the weights using the Heuristic method and then look at the permutation which gives the lower value, but how will the programm know how to move along the neutral interesections?

[exotic parrot]

If anyone knows how to solve this pls DM me

I'll answer tmrw

[valid egret]

hi does anyone know how to properly read from stdin

ive been doing competative programing for a while in java

and im used to using Scanner.next or .nextLine ect

is there anything similar in python

[modern gulch]

Better question for general #python-discussion , ask over there. There’s a few answers depending on whether you actually want to capture the stdin stream or just a bit of user input()

[fiery cosmos]

can someone pls offer a generic strategy for LC 392 "is subsequence", i'd like to do the coding myself but need a push in the right direction

its listed under the "two pointers" section so i have a hint

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

[agile sundial]

what have you tried so far?

[fiery cosmos]

my strat is essentially use nested loop to check all letters in t for each letter in s and store the index of j when i see that the letter in s exists there, then at the end make sure that all indices exist in increasing order (ensuring left-to-rightedness of the substring)

i need to rework my approach and logic to each problem, what's happening is that i write a solution that'll pass say 15/20 test cases then add in logic as necessary to finish out the rest, that's obv not optimal / means im not considering all possible input cases

[haughty mountain]

"two pointers" is a bit of a stretch

[agile sundial]

you use 2 pointers, i guess 😩

[haughty mountain]

labeling this as just a greedy algo would make much more sense

[fiery cosmos]

i'm all ears for suggestion without giving away too much

i wonder if yield/generator here would be good

[haughty mountain]

idk how much I can hint without just giving stuff away entirely

there is a very simple O(n) solution

[fiery cosmos]

i looked in CLRS but that was LCS not substring

and im sure way overengineered

if there is a way to use yield here i'd like to do that since i never learned it

er

[haughty mountain]

the problem is subsequence, no?

[fiery cosmos]

i've never used it in practice

yes

[haughty mountain]

substring tends to mean everything's adjacent too

can you describe what it means for s to be a subsequence of t?

[fiery cosmos]

it means that the chars in s can be found in the same order by reading through t

while skipping zero, one, or more t chars

[haughty mountain]

what about just implementing exactly that?

[fiery cosmos]

im suddenly thinking pop()

[haughty mountain]

when iterating through the chars of t I need to see s[0], later s[1], later s[2], ...

[fiery cosmos]

ok let me try

[haughty mountain]

the way I would implement it would actually use it, but just more of a convenience

spoiler tags with code works, right?
||```py
def f(s, t):
chars = list(s)[::-1]
for c in t:
if chars and chars[-1] == c:
chars.pop()
return len(chars) == 0

good, it does

[agile sundial]

that's an interesting way to do it

[fiery cosmos]

ok the only bit i don't get is the and chars[-1] == c:

is that shorthand for look at the last char in chars

yeah thats gotta be the case

alright thanks as always

a bit frustrating that i can't go from the logic to the code very efficiently but maybe i'll get there

[haughty mountain]

I could index stuff, but that's kinda meh

[agile sundial]

ya

[fiery cosmos]

slice is reserved in python?

[agile sundial]

built in function

[fiery cosmos]

alright this is weird, i'm getting a very close answer but the incorrect one

for max avg subarray

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.

passed 97/127 cases with this code:

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:

        if len(nums) == 1:
            return nums[0]

        max_av = 0
        for i in range(len(nums)-k):
            addends = sum(nums[i:i+k])/k
            #print(len(nums[i:i+k]))
            if addends > max_av:
                max_av = addends
            
        return max_av

[vocal gorge]

can be done faster via a sliding window approach. Like, calculate the sum instead of the average. To shift the window from i:i+k to i+1:i+k+1, subtract nums[i] and add nums[i+k].

as for why your solution fails - ||what if the max average is negative||?

[fiery cosmos]

i was trying to implement a sliding window approach with this

[vocal gorge]

well, you are sliding a window indeed, it's just that the point of that approach is that you can save compute by not adding up all the elements of the window each time - you can just take into account the element that just left the window and the element that just entered it.

[keen hearth]

Unless I'm mistaken I think the range should be: ||range(len(nums) - k + 1)||

Try doing a couple of small examples by hand to check that.

Although it might end up being easier if you can avoid using indices at all.

||```py
window = collections.deque(maxsize=k)
window_sum = 0
for num in nums:
...

[fiery cosmos]

i had been tinkering with that solution, yeah. given that range is up to and not including final term

[keen hearth]

I always end up with off-by-one errors when I try to calculate indices/bounds. I used to be better at reasoning about these things than I am now. But I also make fewer mistakes now because I've learned to find ways to avoid doing things that I find hard 😄

[haughty mountain]

why do hard thing when easy thing does the job?

[keen hearth]

So did that solve the issue?

[fiery cosmos]

i don't think so, let me go back

[haughty mountain]

the original code is quadratic anyway

[keen hearth]

Yeah, so it probably will TLE on the harder inputs. But they said at the moment it is producing incorrect output in some cases.

[fiery cosmos]

no it passes 115/127 test cases

[keen hearth]

That's a slight improvement I think? 😄

[fiery cosmos]

well, this is what i was discussing earlier, let me link to that msg

[keen hearth]

In what way is it failing the remaining cases? Do you have an example failing case?

[fiery cosmos]

#algos-and-data-structs message

[keen hearth]

I'm most interested in knowing whether it's failing due to logic errors or inefficiency.

[fiery cosmos]

it fails when nums = [8860,-853,6534,4477,-4589,8646,-6155,-5577,-1656,-5779,-2619,-8604,-1358,-8009,4983,7063,3104,-1560,4080,2763,5616,-2375,2848,1394,-7173,-5225,-8244,-809,8025,-4072,-4391,-9579,1407,6700,2421,-6685,5481,-1732,-8892,-6645,3077,3287,-4149,8701,-4393,-9070,-1777,2237,-3253,-506,-4931,-7366,-8132,5406,-6300,-275,-1908,67,3569,1433,-7262,-437,8303,4498,-379,3054,-6285,4203,6908,4433,3077,2288,9733,-8067,3007,9725,9669,1362,-2561,-4225,5442,-9006,-429,160,-9234,-4444,3586,-5711,-9506,-79,-4418,-4348,-5891]
and k = 93

[haughty mountain]

fwiw, you can just find the max sum of k consequtive elements and divide by k at the end

[fiery cosmos]

and its failed logic

[keen hearth]

Ah

[fiery cosmos]

failing in the negative case as confused described earlier

lms

[haughty mountain]

sso k == n

[fiery cosmos]

i didn't check that, but it seems to be failing bc of my if addends > max_sum: logic

[haughty mountain]

wait, why are you defaulting max_av to 0?

[fiery cosmos]

🤷🏻‍♂️

no i don't have a max_av

heres my code

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:

        if len(nums) == 1:
            return nums[0]

        max_sum = 0

        for i in range(len(nums)-k+1):
            addends = sum(nums[i:i+k])
            #print(len(nums[i:i+k]))
            if addends > max_sum:
                max_sum = addends
            
        return max_sum / k

[haughty mountain]

same question but max_sum

[fiery cosmos]

right

idk i felt i needed that to exist and didn't know what a good default would be

[haughty mountain]

that's a bad default

[fiery cosmos]

so just set it equal to addends to begin

[haughty mountain]

e.g. you completely fail on [-1], k=1

[keen hearth]

Ah right yeah I totally missed that.

If you're finding a maximum (from a sequence of floats) you want to start with a default of -math.inf.

Do you understand why? @fiery cosmos

[haughty mountain]

let max_sum = -10**18 or something similarly small

[haughty mountain]

while correct in python, that feels so disgusting 🥴

(in this int case, I mean)

[fiery cosmos]

idk if you can import packages in LC

[keen hearth]

Right yeah 😄

[keen hearth]

I think a number of packages are pre-imported for you including math.

[haughty mountain]

or just use something small enough

based on the constraints

[fiery cosmos]

ok now i'm exceeding time limit, meaning i'll need to use the sliding window approach outlined by @vocal gorge

[keen hearth]

You can also do float('-inf')

[fiery cosmos]

in other words, i have to do the one in one out method of compute

one of the test cases is a gigantic array and k = 14538

so.. deque?

[keen hearth]

Yeah give it a go

[fiery cosmos]

not sure how to work in the deque with the loop which is looping over nums

[vocal gorge]

for what? you don't need to store the elements of the window

the idea is that if you have a list [1,2,3,4,5,6,7], and you know the first 5 elements sum to 15, then the next window position sums to 15 + 5 - 1 = 19

[fiery cosmos]

15 + 6 - 1

[haughty mountain]

the risk of off-by-one errors is non-zero 😛

max_sum = -10**18
s = sum(seq[:k-1])
for i in range(n - k + 1):
  s += seq[i + k - 1]
  max_sum = max(max_sum, s)
  s -= seq[i]

actually, maybe there is a nicer phrasing...

[fiery cosmos]

do you ever do leetcode

[haughty mountain]

not really

[haughty mountain]

max_sum = s = sum(seq[:k])
for i in range(n - k):
  s += seq[i + k]
  s -= seq[i]
  max_sum = max(max_sum, s)

all the ones melt away

[fiery cosmos]

is this real life

what's going on w the double assignment operator

nvm

[keen hearth]

I would fill the deque up with the first k numbers, giving you your first window, then for each number after that pop a number off the left end of the deque and append the new number to the right end of the deque.

When you pop a number, subtract it from your running total. When you append a number, add it to your running total.

[haughty mountain]

that is the nice way to do it generically, yeah

iterator, some islice, go to town

[fiery cosmos]

i definitely need to learn deque, yeah

[fiery cosmos]

looks like deques can consist of any iterable

so strings, lists, what else

Once a bounded length deque is full, when new items are added, a corresponding number of items are discarded from the opposite end.

that's cool

[lean walrus]

deques are not restricted to iterables
they can contain anything, for example integers

[fiery cosmos]

yeah i suppose the deque itself is its own structure, therefore there is no need for the items to be contained within say, a string, a list

[tepid blaze]

anyone know what this kind of problem is called:

i have a list of elements
0: 1,2,3
1: 2,3
2: 3
what is the minimum amount of groups that they can be put in

[narrow mica]

well what's a group?

[keen hearth]

That would be a combinatorics problem. But the answer depends on what the constraints are on how the elements can be grouped, and what makes two groups different (for example, do you care about the order within the group).

[opal agate]

is there any algorithm that I can use as an inspiration for designing my own algorithm to maximize the positive number of given arra when transforming into desired array lengthy? For example if input array is [2, -5, 2, 4, 6] and desired length\ is 3, then output should be [3, 1 (-5+2+4), 6]. Another example is [-10, 5, -10, -2, 10] into array of 3 length should be any output that doesn't erase possible 1 positive. The number have to be next to each other to be added

[nimble sedge]

Currently trying to make a simple algebra solver. Finally got it to put everything inside of a tree by tokenizing the equation provided by the user, parsing it, converting it to Reverse Polish Notation form and then to tree form.

Now my problem is solving a simple equation such as 2x+2=5 (the one seen in the picture in tree form). As a person I can easily see where the x is located and know I need to start isolating it. So as a person, first I would subtract two from both sides, then divide both sides by two, but how would I implement this logic into my algorithm? Especially when both sides include x. Would I just choose an arbitrary side to start solving for? This seems to get a lot more complex to implement especially when there is multiple x's on both sides and includes factoring.

If anyone has any advice on how i’d go about solving this issue, it would be very appreciated. Thanks in advance.

https://media.discordapp.net/attachments/495064710278938662/1220634118845628416/image.png?ex=660fa71c&is=65fd321c&hm=a2f9d051c488167f8df20548ac1a9678cb8ceacc859f7113681a0db473994a89&=&format=webp&quality=lossless&width=1922&height=814

[tepid blaze]

I want to return the minimum number of bins and the solution the elements can be placed in

in this case the solution to the problem would be

above test case is probable a bad one
for the solution to this test case

0: 1,2,3
1: 0,
2: 0, 3
3: 0, 2

the solution would be
[[0],[1,2],[3]] n=4

on further research found that this is called a bin packing problem

[vocal gorge]

You could look at sympy's source code for inspiration. I'd start by finding all symbols in the expression - if there's more than two different symbols, then the result won't be numeric, and if a symbol is on both sides (e.g. x + 5 = 2x), it should be collected on one side.

[nimble sedge]

I see, thank you for the help!

[hushed mist]

Do you have more detailed description?

[opal agate]

the output just need to maximize the possible positive number when transforming the array into k length by combing adjacent number. For example, ([1, 2, -5, 4, 3], 3) should have 3 possible positive number by [1, 2, 2] with (-5+4+3). That way it maximize possible positive number. It can also be, [1, 1, 3] which middle 1 is the result of (2 -5 +4) . The algorithm shouldn't care about how big of the number is as long as it is possible to create a positive number. In tern of ([-1, -2, -3, -4, 5, 6], 3) the output should be [-10, 5, 6] by (-1-2-3-4) or [-6, 1, 6] with -6 resulted by (-1-2-3) and middle 1 resulted by (-4+5).

[agile sundial]

it just seems you like do sliding window

what do you mean by "maximizethe possible positive number"? do you want to maximize the count of positive numbers? or maximize the sum?

[opal agate]

count. The algorithm shouldn't care about how big of the number is as long as it is possible to create a positive number. as long as it an array with possible maximum positive numbers i.n k length of array

[hushed mist]

@opal agate are you just adding together items in one group or can do multiple additions spread out over the array?
Is this a legal transformation? [5, -1, 5, -1, 5, -10, 20] -> [4, 4, 5, 10]

[opal agate]

where k = 4? the legal transformation would be [5, 4, 4, 10] or [4, 5, 4, 10]. either work

[hushed mist]

or [5, 3, 5, 10] ... i would try to brute force to start with, how did you come up with this problem?

[opal agate]

part of my school exercise

I'm struck at that part.

[hushed mist]

Say the starting list has N elements [a0, a1, ..., a(N-1)], N> 3. And you should get a list of 3 elements, that means you need to "place" N-3 +:s between soe of the elements in the original list

There are N-1 positions to place + signs.

itertools.combinations(range(N-1), N-3) will you give combinations of 3 indices, place + at these locations, calculate the result and record the count of positive integers in your list.

[vocal gorge]

considering all possible positions is probably way too inefficient... though on second thought comb(n-1, n-3) is comb(n-1, 2), so that's only O(n^2), not horrible

[hushed mist]

yes it depends on the numbers what method is more efficient here

The problem is, which plus signs should be kept, and which should not.

[1, 2, -5, 4, 3]
   +  +   +  +

It might be possible to do some smart filtering or test some interesting combinations before crunching.

[opal agate]

yeah. brute forcing way is too inefficient if the arr is large. I come up with another brute forcing way but it would be Exponentiation in worst case.

[vocal gorge]

how big can n and k be?

[opal agate]

n limit is not given.0 < k <= n.

[hushed mist]

I don't immediately see how to other than brute force ..

[opal agate]

Would it be possible to alter Kadence’s Algorithm for my output?

[hushed mist]

No idea what that is

[orchid pebble]

"Draw the corresponding heap resulting from the interpretation of the following array below!" Would that be right?

[mint jewel]

seems right, but I would write the numbers in the heap as well.

[orchid pebble]

Can you also take a look at that? We're not that sure: https://discord.com/channels/267624335836053506/1221191070294216774

[tall iris]

This is a python script of a Discord Bot I developed for my users, basically I am working on a Automation project on discord my ultimate goal is to develop discord bot which helps my client to perform auto operations like Auto Posting/Auto Comment ... without getting banned or suspend by discord , Insha-Allah soon this project will be completed I want your feed back guys related to this short video about code. Thanks

[lean walrus]

!rule tos

[halcyon plank]

Rules

5. Do not provide or request help on projects that may violate terms of service, or that may be deemed inappropriate, malicious, or illegal.

[gray sorrel]

Does anyone know an easy way to make a class diagram (an image) based on a python file with some classes, that contain arguments, methods and linked to each others ?

[barren void]

So I have a project where I want to compare A* algorithm with Dijkstra. Basically checking out how much the heuristic function helps with the effectivness of the algorithm. Problem being I have to generate a sample size large enough to see the difference. I wondered whether I could theoritecally make a 2D plane and just add notes randomly and have the heuristic of A* be calculated by euclidian distance. Problem being im not too sure as to how to make a heuristic function equal to the weight of the nodes so that it has the same accuracy but added speed. How do I scale these two things?

[vocal gorge]

If you use a grid, euclidean distance will, IIRC, be a provably optimal heuristic. E.g. here's A* vs dijkstra on a random grid.

[barren void]

yes correct, but the problem how is this applicable to a weighted graph where the paths are not the same. Because A*s effectivness is determined f(x) = h(x) + g(x), same goes for Dijkstra but without the g(x) (where h is the weight of the nodes). Does this not mean that g is always equal to 1 as it is a grid?

Or lets say if I understand correctly, if I only want to know the added effectivness from the heuristic It does not matter whether the graph is weighted or not?

[barren void]

And are these two paths exactly the same in terms of shortness?

[vocal gorge]

Yeah; for manhattan distance there's usually a ton of shortest paths between two given points.

[barren void]

Also what would happen if I overvalued the heuristic function, would it be faster but the path would compute out to be longer?

[vocal gorge]

That's true, yeah. You could use a slightly more advanced model where the walls are permeable but cost more than an empty tile to move through, though in this case you won't have a monotone heuristic (only an admissible one).

[vocal gorge]

actually I'm not sure about this last claim... it seems to me that if you use h(x) = manhattan distance from x to the goal, then it never overestimates the distance (nonempty tiles will cause the real distance to be higher) and also h(x)<=h(y)+d(x,y) for adjacent tiles x,y (because d(x,y)>=1), so it's monotone.

[barren void]

So if I use the correct heuristic, an admissable one in this case A* is supposed to have, It does not matter whether it’s a more complex structure or not, I would still be efficiently able to show the effectiveness that the heuristic adds?

[vocal gorge]

It seems to me like it should have an effect, yeah. Try it - if it turns out A* has no benefit over Dijkstra for your samples, that's in itself an interesting result.

[barren void]

Wait i’m confused a bit sorry, try it out for what, more complex or just a grid?

[vocal gorge]

I'm not sure how you'd find an admissible heuristic for something more complex like a random graph.

[barren void]

That’s the problem, so if I want to show the effectiveness consistently it’s only really possible on grids as I genuinely don’t know how I would be able to make an algorithm which generates random graphs whilst also for me to be able to create an admissible heuristic

[vocal gorge]

Yeah, that sounds right. The idea of A* is to use information about the structure of the environment to search in the right direction and so visit fewer nodes than Dijkstra, so for cases like arbitrary graphs where there's no such structure, you can't use it.

[keen hearth]

You generally construct an admissible heuristic (it also need to be consistent btw for graph search) by relaxing some of the constraints of the problem. E.g. for finding a path on a grid maze, the Manhattan distance heuristic is solving the easier problem of: "get from point A to point B, but you're allowed to walk through walls".

So yeah for a random graph, there isn't really any structure you can take advantage of, unless you do some kind of pre-processing on the entire graph to learn a bit about its structure beforehand. If you're going to be performing multiple searches on the same graph that might be beneficial, but if you're only performing one search then what's the point as you then have to visit every node anyway.

[keen hearth]

There are actually a couple of other ways to construct heuristics, aside from constraint relaxation, btw:

• You can use pattern databases, which are essentially big tables that store optimal solutions to sub-problems (problems that only deal with a subset of the state of the problem). Although this requires the problem to have some structure that can be analysed (i.e. not just atomic state nodes).
• You can choose a set of landmark nodes and estimate the cost of getting from a node to the goal as the minimum cost of getting to the node through a landmark node (by pre-computing the cost of getting to/from every node from each landmark). The heuristic this produces is not admissible though, but there is a related approach using landmarks that does give you an admissible heuristic.
  But both of these approaches are the kind that require you do some pre-computation on the entire graph.

[stiff quartz]

Currently doing 3sum problem on Leetcode (https://leetcode.com/problems/3sum). Could someone give me a hint why this O(n^2) solution does not pass (Time Limit)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n: int = len(nums)
        
        missing_map: dict[int, list[list[int]]] = defaultdict(list)
        for i in range(n):
            for j in range(i+1, n):
                missing_map[-nums[i]-nums[j]].append([i, j])

        already: set[tuple[int, int, int]] = set()
        for k in range(n):
            for i, j in missing_map[nums[k]]:
                if k != i and k != j:
                    to_app: list[int] = [nums[i], nums[j], nums[k]]
                    hash_: tuple[int, int, int] = tuple(sorted(to_app))
                    already.add(hash_)
            del missing_map[nums[k]]

        return list(map(lambda x: list(x), already))

But this O(n^2) sol does (no hashmap, we sort and use a two pointer approach)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        
        n: int = len(nums)

        ans: list[list[int]] = []
        for k in range(n):
            if k == 0 or nums[k-1] != nums[k]:
                l, r = k+1, n-1
                while l < r:
                    three_sum = nums[k] + nums[l] + nums[r]
                    if three_sum == 0:
                        ans.append([nums[k], nums[l], nums[r]])
                        while l < r and nums[l] == nums[l+1]:
                            l += 1
                        l += 1
                    elif three_sum < 0:
                        while l < r and nums[l] == nums[l+1]:
                            l += 1
                        l += 1
                    else:
                        while l < r and nums[r] == nums[r-1]:
                            r -= 1
                        r -= 1           
        return ans

Is the hashing adding that much time to my first solution?

(and the sorting of three elements)

[quick cairn]

Is A* a greedy algorithm

[haughty mountain]

in a sense

[keen hearth]

I think the two pointer approach cuts down quite a lot on the number of triples that are considered, especially if you are able to skip over duplicates.

Btw @barren void, I recommend reading the chapter on searching of this book, if you can get a hold of a copy of it: https://aima.cs.berkeley.edu/ (Check your university library if you're at one.) There's lots of content in the chapter about implementing A* search and about designing and evaluating heuristic functions.
This website is also has a really nice explanation of A* search: https://www.redblobgames.com/pathfinding/a-star/introduction.html

[stiff quartz]

Fair point

First time I had a Time Limit Execution on a solution that had the same complexity than the answer

So I was puzzled

but I guess it makes sense since the two pointers skips all those duplicates

[keen hearth]

Yeah, there's also quite a large variance of runtimes for this problem if you look at the histogram, and it's pretty multi-modal.

The hash table approach might just about be fast enough if you can cut down on duplicates.

[stiff quartz]

What do you mean by multi-modal sorry?

[keen hearth]

Like, has more than one bump

So like, different approaches have a significant effect on the runtime, even among the ones that are fast enough to pass the tests (the differences are not just due to random variation).

Probably explains it better: https://en.wikipedia.org/wiki/Multimodal_distribution

[stiff quartz]

Oh I see

thx!

[keen hearth]

When I originally submitted, my solution was in the cluster all the way on the right.

If you click on the histogram, you can actually see example solutions with different runtimes.

[quick cairn]

I was asked this on an exam and got this wrong by saying it is. My rationale was that it picks the best option based on its heuristic function

[haughty mountain]

it's a bit of a stretch calling it greedy

you could phrase it some kind of greedy choice, but it feels kinda iffy

[keen hearth]

I would assume by greedy they mean it doesn't backtrack, but A* search does backtrack (unless you have a perfect heuristic function).

But then again it's greedy in terms of choosing which node on the frontier to expand next so 🤷‍♂️

Usually when you talk about A* search and greedy search in the same context, you're contrasting them with each other, like here: https://www.redblobgames.com/pathfinding/a-star/introduction.html#astar

[opal oriole]

What makes an algorithm "greedy" is not actually super well defined as it is commonly used (what is "local"?), so it can be debated. You can even find contradictions on places like Wikipedia on whether and algorithm is greedy or not because the authors of the different articles had differing opinions on what makes something a greedy algorithm (e.g. says it's greedy -> links to greedy algorithm article -> definition on that article contradicts it).

There are even some papers IIRC on trying to define it.

Whether something is DP is actually well defined though.

(e.g. Dijkstra's is often presented as greedy, and it might be depending on how you feel about it, but it's DP by definition (so in a sense it's more DP than it's greedy))

(This is also an educational issue, since it's not covered as a DP algorithm (so it being greedy but not DP is kind of mass misinformation): https://www.infona.pl/resource/bwmeta1.element.baztech-article-BAT5-0013-0005/tab/summary )

[valid holly]

Ok does anyone know about Leb128 and hashing?

https://mystb.in/HarmonyBernardSage

why is this happening...

the game technically does 00 byte fills

but somehow only when calculating as FF fills the hash matches on that image data I sent

tbf I don't think Leb128 is important here

that calculate_hash python function is originally converted from

uint calculate_hash(char * data, int len) {
  uint hash;
  uint chunks;
  uint chunk;
  uint v1;
  uint v2;
  uint v3;

  hash = 2166136261;
  if (len >= 0 && (len & 0xFFFFFFFC) != 0) {
    chunks = (((len & 0xFFFFFFFC) - 1) >> 2) + 1;
    do {
      chunk = * data;
      data += 4;
      hash = 16777619 * (hash ^ chunk);
      --chunks;
    }
    while (chunks);
  }
  v1 = 0;
  switch (len & 3) {
  case 1:
    return 16777619 * (hash * (v1 | * data));
  case 2:
    v3 = * data++;
    v1 = (v3 | v1) << 8;
    return 16777619 * (hash ^ (v1 | * data));
  case 3:
    v2 = * data++;
    v1 = v2 << 8;
    v3 = * data++;
    v1 = (v3 | v1) << 8;
    return 16777619 * (hash ^ (v1 | * data));
  }
  return hash;
}```

[stray fractal]

how would i implement an intersection between 2 ranges, especially with different step values

[solemn moss]

If there is a negative step, you can just reverse that range and get positive one

If you know a start and the end, the result will be
range(start, end + 1, lcm(step1, step2))

If we have two segments [a, b], [c, d]
Their intersection is [max(a, c), min(c, d)]

So now we need to find first element from the ranges and the last one on this segment

I think for that we can look on the segment with smallest start, let it be a here
We need to find first such value a + lcm(step1, step2) * k that is >= max(a, c)
k is something like (max(a, c) - a) / lcm(step1, step2) rounded up

[stray fractal]

what if the range can be infinite

[solemn moss]

What values are in a range(-inf, inf, 5)?

[stray fractal]

it can't have both endpoints infinite though

[solemn moss]

Well, than the segments intersection part is the same
And for searching first/last element I don't see something else than just placing if on all cases with inf

1. min(a, c) is not -inf,
2. min(a, c) is -inf, max(a, c) is not -inf
3. both are -inf

[glossy lintel]

how should i represent a tree as string that has multiple children(no constant count of children)

one idea could be

<1> <= <2, 5>, <3>, <4, 7> =>

(im confused on how to do so)

[narrow mica]

you could just

root
  - 1
    - 2
      - 5
    - 3
    - 4
      - 7

looks ugly but what I'm trying to say is, folders & files are in fact a tree structure with varying number of children
so you could just use how you'd represent a folder hierarchy to represent a tree

[glossy lintel]

so best could be

1
├── 2
│   └── 'A'
└── 4
    └── 'C'

[glossy lintel]

or even

1
|- 2
|  |- 'A'
|
|- 4
   |- 'C'

[opal oriole]

You can use a standard format (JSON/XML). Or if you want something really simple, something like: 1 (2 5) 3 (4 7) (Note that this is effectively Lisp minus the outer parens).

[stray fractal]

using that to get the first element doesn't work well
i've found posts on stack exchange but i can't seem to understand how they work
there's one that works for integers but not decimals which i plan to support

[coral sierra]

Which framework should I use as a beginner. I prefer the one which reveals most of the low level concepts while still being continually maintained.

[narrow mica]

write the ranges as

A, A+s, A+2s, A+3s, ...
B, B+t, B+2t, B+3t, ...
```you're trying to find the (first) common element(s) between the two
in other words, you're trying to find the integers `n, m` such that

A + sn = B + tm
=> sn - tm = B - A // rearrange
```where s, t, B, A are known values
again in other words, you're trying to find the integer solutions to an equation - a diophantine equation
to do so use extgcd, which allows you to find the integer solutions to the equation

ax + by = gcd(a, b)
```you can multiply both sides by `k = (B - A)/gcd(s, t)` to get back to your original equation

[stray fractal]

how "multiply both sides"?

so if i multiply any of n/m by k and add it to their respective equation, i get the first term?

oh

it sort of works but only for integers

[narrow mica]

k = (B - A)/gcd(s, t)

an + bm   = gcd(s, t)
kan + kbm = k * gcd(s, t)
          = B - A

(ka)n + (kb)m = B - A
(s)n  + (t)m  = B - A

[narrow mica]

why do you think that?

[stray fractal]

the egcd() function i have returns huge numbers for non-integers

[narrow mica]

oh wait I see

lemme think

[narrow mica]

on a slight tangent, but how are you planning to deal with float imprecisions?

[stray fractal]

i don't deal with it

[stray fractal]

one workaround i found was using .as_integer_ratio() and dividing by the denominator from it

though it's not producing the correct results yet it's producing small ones

[narrow mica]

one idea is, if you had

(a/b)x + (c/d)y = (e/f)
```where `a-f` are integers, then you can multiply by `bdf` to get back an equation with only integer coefficients
and since technically all floats are rational, you can do this

[stray fractal]

it's still producing wrong results

# s = 1
# t = 0.3
# A = 2.3
# B = 5.6
(s_n, s_d), (t_n, t_d) = s.as_integer_ratio(), t.as_integer_ratio()
C = B - A
C_n, C_d = C.as_integer_ratio()
p = lcm(s_d, t_d, C_d)
s_n2 = s_n * (p // s_d)
t_n2 = t_n * (p // t_d)
C_n2 = C_n * (p // C_d)
g, n, m = egcd(s_n2, t_n2)
k = C_n2 / (g * p)
t = A + n * k / p
t2 = B + m * k / p
assert t == t2 # failed
# t ≈ 1.805
# t2 ≈ 7.25

actually wait lemme check if they intersect

they do

[narrow mica]

so... it works?

[stray fractal]

nope

26.3 is the expected value for both t and t2

[haughty mountain]

why are you trying to mix gcd with floats...

that will just not work

[stray fractal]

how would i get the first element of an arithmetic sequence with floating points then

or any other decimal data type

[narrow mica]

the gist is they're trying to make a custom range that would support float values and maybe inf on one side; right now they're trying to implement a range intersection type of deal

[haughty mountain]

inf on one side will wreak havoc with floats 🥴

if you had said fractions then sure that could work, floats no

tbh, I would probably just model float ranges as regular ranges + some arithmetic

[stray fractal]

floats are fractions sorta