algos-and-data-structs

[placid oasis]

they offer coding crash course

[old rover]

It’s in JavaScript tho

idk if that affects your decision

DS/algos are language agnostic yes I know

[winged vale]

You and two of your friends have just returned back home after visiting various countries. Now you would like to evenly split all the souvenirs that all three of you bought. Partition doesn't necessarily needs to be subarray.

Is this like multi dimensional knapsack?

[prime heath]

Can someone please help me with this problem? I could not even come up with a bruteforce solution. "Given an equation "x=y", for example, "111=12", you need to add pluses inside x to make the equation correct. In our example "111=12", we can add one plus "11+1=12" and the equation becomes correct. You need to find the minimum number of pluses to add to x to make the equation correct. If there is no answer print -1."

[trim fiber]

What have you tried, what results you got

[prime heath]

I have not been able to do anything so far

I can see there can be 2^(n-1) combinations with bruteforce approach

[trim fiber]

Okay, so start with something simple like "I assume that only one plus sign could solve my problem"
How this code will look like?

[prime heath]

hi, so it will be a single for loop to add two slices of x, like:

for i in range(len(x)-1):
    if int(x[:i+1]) + int(x[i+1:]) == int(y):
        return

[trim fiber]

It can be range(1, len(x) - 1) and rather x[:i] with x[i:]

!e

x = "hello world"
for i in range(1, len(x) - 1):
  print(x[:i], x[i:])

[halcyon plank]

@trim fiber :white_check_mark: Your eval job has completed with return code 0.

001 | h ello world
002 | he llo world
003 | hel lo world
004 | hell o world
005 | hello  world
006 | hello  world
007 | hello w orld
008 | hello wo rld
009 | hello wor ld

[trim fiber]

Woops, nope, len(x) without - 1 part

[prime heath]

yeah

[trim fiber]

!e

x = "1234"
for i in range(1, len(x)):
  print(" + ".join([x[:i], x[i:]]))

[halcyon plank]

@trim fiber :white_check_mark: Your eval job has completed with return code 0.

001 | 1 + 234
002 | 12 + 34
003 | 123 + 4

[trim fiber]

That's it

[prime heath]

yea I see

[trim fiber]

Okay, so it's first step when we are adding one + sign

Can you make a loop for case with two plus signs?

[fiery cosmos]

Isn't that just the brute force solution to keep trying more plusses

~2^n possibilities

[trim fiber]

Bruteforce solution is to try every possible case and pick best one (if it exists)

[fiery cosmos]

Yeah but 177 asked for something better

[trim fiber]

Right, I planned to show bruteforce solution firstly and then trying to upgrade the algorithm

[prime heath]

I could not do it in brute force either

[fiery cosmos]

I see

[prime heath]

!e

x = '1234'

for i in range(1, len(x)):
    for j in range(i+1, len(x)):
        print("+".join([x[:i], x[i:j], x[j:]]))

[halcyon plank]

@prime heath :white_check_mark: Your eval job has completed with return code 0.

001 | 1+2+34
002 | 1+23+4
003 | 12+3+4

[trim fiber]

!e

x = '123456789'

for i in range(1, len(x)):
    for j in range(i+1, len(x)):
        print("+".join([x[:i], x[i:j], x[j:]]))

[halcyon plank]

@trim fiber :white_check_mark: Your eval job has completed with return code 0.

001 | 1+2+3456789
002 | 1+23+456789
003 | 1+234+56789
004 | 1+2345+6789
005 | 1+23456+789
006 | 1+234567+89
007 | 1+2345678+9
008 | 12+3+456789
009 | 12+34+56789
010 | 12+345+6789
011 | 12+3456+789
... (truncated - too many lines)

Full output: https://paste.pythondiscord.com/ezikuyemel.txt?noredirect

[fiery cosmos]

Idk the full answer but I notice inserting a + always makes the number smaller (assuming no leading zeroes) so maybe you always want to add + to the side with the larger total

[prime heath]

what do you mean by "add + to the side with larger total"?

[fiery cosmos]

Like 111 is bigger than 12 so the 111 side needs to be smaller so it needs at least one +

[prime heath]

right. but I can only manipulate the left side anyway

[trim fiber]

As far as I understand you cannot add pluses on right side

[fiery cosmos]

Ohh, I missed that, sorry

I thought both sides

I should go to bed ignore my misleading advice

[prime heath]

that would be an interesting problem too though 😅

[prime heath]

so anyway how do i extend this?

[trim fiber]

Do you see the scheme how to upgrade it to add from 1 to len(x) - 1 plus signs?

I mean how to create a loop for it

[prime heath]

not yet

I mean without explicitly writing n-1 loops

[trim fiber]

It should be something like this

def put_plus_signs(string, how_many, index=1):
  if how_many == 1:
    for i in range(index, len(string)):
      print("+".join([string[:i], string[i:]]))
  else:
    pass  # some recursive call here

for how_many_plus_signs in range(1, len(string)):
  put_plus_signs(string, how_many_plus_signs)

[prime heath]

can't seem to figure out the recursion

[faint sentinel]

#min coin problem --->using recursive approach
#this program is giving me all the solutions available in all combinations
counter = 10000
memory = {} , #in dictionary , we will store the Amount as key , and the count of notes as value
def min_coin(Amount,coins_available,count):
    global counter
    if(Amount == 0):
        return count
    for i in coins_available:
       if Amount >= i:
            min_count =  min_coin(Amount - i,coins_available,count+1)
       if  min_count <= counter:
           counter = min_count

Amount = 2
coins_available = [1,2]
count = 0
min_coin(Amount,coins_available,count)
print(counter)

this is the problem of minimum number of coins required to make up an Amount , here in this code , i am not able to solve the problem of how to handle the case when the return type is None ,

please help

[mellow bronze]

You have a sequence of integers A1,A2,…,AN. You may perform any number of operations on this sequence (including zero). In one operation, you should choose a valid index i and decrease Ai by i. Can you make the sequence good using these operations?

Input:
The first line of the input contains a single integer T denoting the number of test cases.The description of T test cases follows.
The first line of each test case contains a single integer N.
The second line contains N space-separated integers A1,A2,…,AN.

Output:
For each test case, print a single line containing the string "YES" if it is possible to make the given sequence good or "NO" if it is impossible.

can anyone help me in solving this?

[keen hearth]

Hey. Am I missing something or does the question not define what a ‘good’ sequence is?

[mellow bronze]

basically a good sequence is when the sum of all its elements is 0

[faint sentinel]

can you answer my problem also

[keen hearth]

Can you think of a sequence that you could not make good?

For each index i, you have to be able to reduce the value at the index to zero by decreasing it by i some number of times.

Is there a way to quickly check if this is possible?

[keen hearth]

Hmm, I think you need to move counter inside the function. The function should surely return the minimum number of coins for the given amount?

[vocal gorge]

(note: they said the sum must be zero, I believe)

[keen hearth]

Ah, my mistake, I assumed the question said the numbers had to be non-negative.

[main flower]

I don't think I understand your problem. Couldn't you just calculate the sum of whole sequence and then just subtract 1s from element at index 1

So you'd end up at sum = 0

[agile sundial]

hm, that's what I thought too, and I think it would work

that would make it always possible for N>1

[main flower]

Yeah

[vocal gorge]

only if the original sum is >=0

[main flower]

Then just add 1s

[agile sundial]

oh right, they're not all positive

[vocal gorge]

(and yes, that's the spoiler 😛 )

[agile sundial]

you have to decrease

[vocal gorge]

adding isn't mentioned as an operation

[main flower]

Hmmm

So

if sum >= 0 It's yes, else no

[fiery cosmos]

I need to gen valid random amazon urls (dont ask), how to?

@trim flume

[muted yoke]

omg

[agile sundial]

but why

[fiery cosmos]

I said dont ask for what lol

[muted yoke]

why are my friends telling people about my insecurities?

wrong group

[latent cradle]

Two quick questions.

What could possible go wrong with this? sys.setrecursionlimit(10000)

And what's the most efficient way to implement something like wang tiles?

Sorry that's a really broad question. I'm really bad with data structures and algos.

[spring jasper]

If you cant fit your recursive solution in the default limit of 1000 youre probably doing something wrong

[fiery cosmos]

audioop is such an odd hidden gem

the methods in it can operate on any object that implements the buffer protocol, and the implementations of the functions in it are very fast as far as builtins go

and many have applications outside of audio

like audioop.getsample lets you look up an 8, 16, 24 or 32 bit integer from a bytes like object without requiring a memoryview cast to the desired size

and lin2lin lets you take a buffer and upcast/downcast it between 1/2/3/4 byte width ints

well not cast, convert.

they are by far the fastest functions built in to the interpreter for processing integer data

[rose sable]

guysss

[frail veldt]

def get_excluded_guilds(user_guilds: list, bot_guilds: list):
    excluded = []
    for guild in bot_guilds:
        if guild['id'] in map(lambda i: i['id'], user_guilds) and (guild['permissions'] & 0x8 == 0x8):
            excluded.append(guild)
            return excluded

why ot pass only one item

of an array

[agile sundial]

you return as soon as you append one thing, so the list will only have one item

[nocturne linden]

are you tho? I'm sure you've run Dynamic Programming algorithms with much greater depth than 1000

[agile sundial]

1000 is a lot

[spring jasper]

Naive recursive solutions sure

[onyx root]

you will crash Python

[latent cradle]

Got it

I tested it, that is indeed correct.

[keen hearth]

Yep 😄 Often the only solution really is to re-write your code to be iterative.

[tranquil barn]

#☕help-coffee message

I just want to be pointed in a right direction with this problem

[sullen adder]

i think you could check out euler's theorum?

https://math.stackexchange.com/questions/1546417/find-the-last-digits-of-a-number-raised-to-a-large-exponent

[tranquil barn]

Oh I solved that problem, tho I do need a bit of help in understanding this question https://codeforces.com/problemset/problem/82/A

Does this mean that the names will be increasing exponentially?

I really don't understand the sequence

@sullen adder

[sullen adder]

not exponentially

rather in multiples of two it seems

at first there are 5 people
at the end of the second cycle there would be 10
the third would have 20 people
the fourth would have 40 and so forth

all the names will be grouped together though

@tranquil barn

[tranquil barn]

Oh

okay so is the list something like [1,2,3,4,1,1,2,2,3,3,4,4,1,1,1,1,2,2,2,2]

@sullen adder

[sullen adder]

yep, that's it!

@tranquil barn

i should really remember to use the reply function

[tranquil barn]

Yeah same lol same. but thank you! ❤️

[sullen adder]

no problem, i hope you have fun with these challenges!!

[slow whale]

Any one beginners here who can be my partner in learning algo?

[iron ridge]

I´m lost. How can I separate in digits a list with more than one compose number. I mean, I have this list created from a input number:

inputuser 13
listaglobal = list(range(n+1))

#and I get listaglobal = [0,1,2,3,4,5,6,7,8,9,10,11,12,13]

Now I need to transform to this:

With

aux1 = [int(i) for i in str(n)] 

I have got

But I need to change all the list in digits.
I¨m breaking my head 😆

More plain? I can´t

Thanks you so much, I´m going to read it for understand correctly.

[cedar hornet]

Hi everyone, just wondering, does anyone knows some clue about the history of insertion sort or the origin of its popularity ? Couldn't really find the source of information for those, so I thought of asking you all. Thanks 🙂

[pure terrace]

Hello what should be the correct order to return a variable and break a for loop

for doc in document:
   return doc
   break

Or the other way around

[agile sundial]

think about what happens in each situation

[vocal gorge]

The answer is ||this question doesn't really make any sense, because return ends the function entirely - you don't need to "clean up" by stopping loops after that, or anything.||

[latent cradle]

Is the loop in a function?

[flint kite]

So why do I get the error?

[spring jasper]

Depends on where the repl is running from

You need to start the repl from the save dir as the files

Or cd into it after you start it

[flint kite]

we did that

still occurs @spring jasper

[spring jasper]

If you do %pwd it shows the proper directory?

[misty plume]

hello, so I have this task, the problem asks me to create a graph, 6 is the number of nodes, and the following numbers, are node types based on the int that the user writes
so later on it gets the nodes with the same int together to do operations with it

input should look like this

6
0 0 0 1 1 1
6 would be the number of ints I want, and then they would have to be spaced like that

[crisp fog]

Can someone send me some link to code where is implemented how to make from bdd robdd (my boolean function is represented as a vector, so just ones and zeros) ?

[hard wadi]

I am trying to make an algorithm that solves multi-choice math related questions
This algorithm brute forces through a lot of various series of math operations and compare the result with answers.
If it ever gets closer to an answer then a certain threshold, we say that that's a possible answer.

But it gets real complex, real fast before it can reach the answers most of the time.
I need to find ways to tone down that complexity if i want this algorithm to figure out more than just some simple questions.

What do you guys think?
How can the complexity be decreased?

I also need control over what operation or value gets included in the guess
And how many times it can occur.

[covert prairie]

!rule 5

[halcyon plank]

Rules

5. Do not provide or request help on projects that may break laws, breach terms of services, be considered malicious or inappropriate. Do not help with ongoing exams. Do not provide or request solutions for graded assignments, although general guidance is okay.

[hard wadi]

@covert prairie i don't think this is illegal in any way

[covert prairie]

Read the rule in its entirety.

[hard wadi]

read my text again

[covert prairie]

Nice edit 🙂

[waxen iron]

what is this software ?

[hard wadi]

I am trying to come up with an algorithm, thats all

[covert prairie]

The cat is out of the bag though, sorry I can't help you.

[hard wadi]

i believe in a world with a great education system where they don't force you to learn useless stuff that you forget in 6 months after learning
i study computer engineering and all that they teach us should've been algorithms and data structures
physics should've been an elective, not the advanced cs lectures

i think university degrees will soon be absolete

[keen hearth]

I think you'd be missing out on a lot if you just did algorithms. That wouldn't be a very broad CS education.

[hard wadi]

the lectures could force dependencies, if you wanna learn ML, you have to get calculus, linear algebra for example

if you wanna go full web dev, maybe they better not teach you calculus

you could say, knowing some extra stuff might come in handy one day an all
but is it worth the effort and time really?

[hard wadi]

i am saying, make math/physics related lectures elective
and force some more cs related lectures
or better, make the education shorter

[keen hearth]

Maybe. I don't know to what extent the math requirements are a barrier to potentially good developers entering the field.

[keen hearth]

Actually, I think they are planning to introduce 2-year degree programs in the UK.

[hard wadi]

I'd like to think highschool math should be sufficient

[keen hearth]

I mean, I think a reason for the maths and physics is that it teaches model-building and problem-solving, as well as constructing logical arguments.

Computer science is really an academic off-shoot of mathematics, but CS degrees are often treated as if they are software engineering degrees.

[ripe wolf]

maybe if you pay attention in your class you'll find out!

if you cannot create an algorithm that isn't brute force then you will need to pay attention in class

[hard wadi]

Whatever information that those lectures they give us that stays with us more than 3 years is not unnecessary imo.

I couldn't argue with most of math as i also spend some time in gamedev and computer graphics, and a little ML. But i don't think i will ever need whats shown in physics II

@ripe wolf half of those questions should be solvable with about 4 to 6 givens and 5-6 types of operations

[ripe wolf]

if you pay attention in class you will create a better bot

so regardless just pay attention in class

[hard wadi]

if my brute force spans the solution, i should be able to at least get it down to 2 possible answers

[ripe wolf]

just pay attention

[hard wadi]

@ripe wolf its about physics

[ripe wolf]

if you pay attention to physics you will learn about physics

then you can apply that knowledge and make a better algorithm regarding physics

it's a real world skill since you will need to learn about things and then program it in if you become a dev

[hard wadi]

i think i know where you are getting at but in case not, let me make this a little bit more clear:
i am looking to create an algorithm that doesn't know about anything related to type of the question

treating the question like a blackbox

[ripe wolf]

it's impossible no matter what you do

[hard wadi]

thats a nice point, but they don't force you to solve 25 questions in 80 mins in real life scenario no?

[ripe wolf]

you will have deadlines

they force you to solve 25 questions in 80 minutes to demonstrate understanding

if you do not understand what you are coding and a senior developer reviews your code and it doesnt make sense

it will be a very awkward conversation

it will also generate many future headaches

while your thinking of automating something is correct, you need to understand what you're automating very well

if you understood physics really really really well then you would be able to create a bot that can do that due to your knowledge

however, if you knew it to that level you would not worry about that test

[hard wadi]

I believe i have a different mindset than you,
I do not like spending efforts on something that i am convinced that its very likely to be useless and not interesting.
You have no trouble soldiering through it.
@ripe wolf

[ripe wolf]

i have adhd, im pretty sure i feel the same way as you

im just telling you that it'll be useful later on

[hard wadi]

Everything is an experience afterall right?

[ripe wolf]

yes, just work through it

especially if you don't have adhd, sometimes i wish i had the self control to do what i told u to do

[hard wadi]

Eitherway, i will give this a few days. It's a nice project afterall

[ancient pier]

I'm having problem with a way to append list of 2 vars in a bigger list like basically right now I'm using lambda and map in following sense -
n,*k = map(int,input().split())
segments = list(map(lambda x: Segment(x[0], x[1]), zip(k[::2], k[1::2]))) and using Segment as anonymous function imported from collections from
collections import namedtuple
Segment = namedtuple('Segment', 'start end') to get output as [Segment(start=1, end=3), Segment(start=2, end=5), Segment(start=3, end=5), Segment(start=2, end=6)] and i think there should be more efficient way to do this by maybe using list comprehension can anyone help me out?

[normal axle]

So I'm trying to implement Eller's algorithm for maze generation, but one problem I come across is a logical one and it looks like this

1 2 3 4 Put random numbers
1>1>1>1 Randomly connect
-- ---  Randomly put walls under
5 1 6 1 Fill empty with new numbers
5>5>5>5 Randomly connect
- -----  Randomly put walls under
5555555 Last line has no vertical walls

Result:
__________
*********|
|_*_____*|
|********|
|_*______|
|*********
__________

This algorithm is supposed to generate perfect mazes but there is clearly a loop so I surely misunderstood some part of it but can't figure it out
Source: https://weblog.jamisbuck.org/2010/12/29/maze-generation-eller-s-algorithm

[crude flare]

hello, can anyone help me to solvethis: using only while read input from the keyboard until it equals "mergem". Once this condition is met, exit the block and then display the "end" message.

[vestal umbra]

while True:
  if input() == "mergem":
    break

print("end")

not sure if that's what you wanted, that's how I understood the question at least.. hehe

[crude flare]

i make it in this mode 😄 py y = 'mergem' while True : a = input("Introduceti ce doriti: ") if a == y: break print("sfarsit")

[wispy locust]

!code

[halcyon plank]

Here's how to format Python code on Discord:

```py
print('Hello world!')
```

These are backticks, not quotes. Check this out if you can't find the backtick key.

[crude flare]

y = 2
while True :
    a = int(input("Introduceti ce doriti: "))
    if a > y:
        for i in range(1, a + 1, 1):
            s += i
            print("sum is : ", s)
    break
``` any ideea how can i make the output to be only the final sum?

[frozen valley]

Put the print statement outside of the for loop

Just unindent that line once

[gilded tapir]

Folks I am looking for an sorted dictionary data structure in python similar to (pqdict)[https://pypi.org/project/pqdict/] or (sorteddict)[http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html] but i expect a lot of my elements to have the same value so when I pop() the dict for the item with max value, I want to get all the items with max value returned to me, and the option to delete one of those values before I move on. Any pointers or does it seem like I have to implement this myself?

[prime heath]

In quicksort, how can we tell that Hoare's partitioning scheme does only n/6 swaps on average on a random array?

[ocean hazel]

Is adding to a numpy array using += any faster than iterating over a normal list and using += for every element

[agile sundial]

yeah

just test it for yourself

[ocean hazel]

Is it still O(n)?

[prime heath]

numpy vectorizes the operation. the elements in a numpy array are incremented in batches, while with a for loop on a python list they are incremented one-by-one

[agile sundial]

and the more work you do in C, the faster it will be

hey, that rhymes

[gray swan]

~

[dapper sapphire]

So pythons variable scope is equivalent to javascript's var
Below is a Node.js code:

var i = -10
let j = -10

for(var i = 0; i < 2; i++)
    console.log("for loop - i(var):", i)

for(let j = 0; j < 2; j++)
    console.log("for loop - j(let):", j)


console.log("\n\ni(var):", i)
console.log("j(let):", j)

output
for loop - i(var): 0
for loop - i(var): 1
for loop - j(let): 0
for loop - j(let): 1


i(var): 2
j(let): -10

---

Below is a python code:

i = -10

for i in range(2):
    print("for loop -", i)

print(f"\n{i}")

output
for loop - 0
for loop - 1

1

[old rover]

ok?

[dapper sapphire]

Just some observation

And wanted to know what other people thought of it.

[fading sky]

The question on leetcode:
Given an integer array **nums** sorted in ascending order, return an array of the squares of each number sorted in ascending order.
Here are 2 functions that do the same thing:

def func1(nums):
  return sorted([x*x for x in nums])

def func2(nums):
  for i in range(len(nums)):
    nums[i] = nums[i]**2
  return sorted(nums)

However, leetcode says that func1 is faster than func2, and I timed both the functions 10 times, and 8/10 times func1 was faster than func2. But why, they're both exactly the same things?

[cold cloak]

I think it has got to do something with time complexity. While traversing through a list it takes O(n) i.e (linear time) to complete. But according to this , func1 and func2 should both run in linear time. Moreover, you have used the len() in func2 which takes O(1) i.e (constant time)...whereas func1 is more simpler. I dont know if this is right, pls correct me if i'm wrong.

[prime heath]

Func2 is inplace. Func1 creates a new list. That might have something to do with taking more time

[pine vapor]

Hey guys...

[fading sky]

bigO notation gives the general sense of time & space complexity, it doesn't tell us the actual time that would be used, ofcourse you can calculate the speed of a code if the bigO for that code is given but that would only be the average of the normal distribution for that piece of code. Atleast that's what I've been told

[cold cloak]

Oh, alright.

[fading sky]

umm, but I said func1 is faster than func2, you're saying the opposite???

[prime heath]

Oh right. Sorry I misread

Maybe list comprehension is faster than for loop, but thats just me guessing

[fading sky]

hmm, could be

[fading sky]

yes, i just googled this and this is true, thanks

[pine vapor]

Maybe...

for both the cases sorted() is same
But
In func1... x the only variable so processor need to process only on that variable...

Whereas In func2... Processor fast need to process the value of i then it will compute the nums[i]...
And it goes throughout the list.

First**

[fading sky]

yup, all of these factors decrease the speed of func2

[pine vapor]

Yeah...

Guys can anybody tell me about LAPLACE TRANSFORM..??

[prime heath]

I also just googled it haha

[vocal gorge]

Like, in general? I've encountered it in control theory, say. It's very similar to the fourier transform, but happens to be useful less often.

Or do you want to know how to calculate it numerically, or something?

[lean dome]

More accurately, Python simply doesn't have a block scope. The local variables of a function is the smallest scope in Python.

[pine vapor]

No no... I wanna know ... What does that mean...

What does LT. of a function represent??...

I kno how to calculate...
But don't know want LT actually is...

[vocal gorge]

Well, just like the fourier transform is kinda like the decomposition of a function into waves with different frequences, the laplace transform is kinda like the decomposition of a function into exponents decaying on different rates. One could say that's why it comes up when studying the response of a dynamical system to an impulse.

Not sure there's a deeper understanding to be had than that.

[pine vapor]

Something like transforming a function to wave (like sine function)

[fiery cosmos]

what's a good algorithm for generating all strings of length n that contain more a's than b's?

[vocal gorge]

Loop over the number of a's from half the string length to it, and generate all the possible strings with that number for each number

There'd just be something like NChooseK such strings for k a's from n.

[fiery cosmos]

how do you generate all such strings? is there a function in python that does it?

[vocal gorge]

you can generate all the ways to choose k indexes from n with itertools.combinations and for each, put as on these positions, bs on all other positions.

[runic tinsel]

are there other letters too?

[fiery cosmos]

only a and b

[runic tinsel]

You can also generate letter by letter, recursively

And also make all sorted ones and permute

and i don;t know which is worst and which is best out of three

2nd probably worst

[fiery cosmos]

i don't know how to write the code lol

[runic tinsel]

def makestrings(total_left, b_allowed):
  if not total_left:
     return ['']
  if b_allowed:
     result = []
     for s in makestrings(total_left - 1, b_allowed - 1):
        result.append('b' + s)
     for s in makestrings(total_left - 1, b_allowed):
        result.append('a' + s)
     return result
  return ['a' * total_left]
def strings(n):
  return makestrings(n, (n-1)//2)

that must be the worst one because it's recursive

and i made it even worse by avoiding generators

[fiery cosmos]

oh my gosh, thank you so much

you're the best person ever

[runic tinsel]

in this moment i am euphoric

[split dawn]

I am working on this piece of code for the past 3 hours and I am still not able to figure out what the issue is here.

1. Write a function to calculate the tip for a hostess given the amount and tip percentage

    def tip_calculator(amount, percentage):

and here is my code

def tip_calculator(amount, percentage):
if percentage >= 0 and percentage >= 100:
return amount + (amount * percentage)
else:
return -1

and this is the output that I am getting

Process finished with exit code 0

[jolly mortar]

log n

[brave oak]

write down a series of numbers in increasing order along with the number of operations needed

and check the pattern 😉

[fiery cosmos]

how do i restrict which of something can be related to another

[brave oak]

😉

okay

consider this.

I'm assuming

verb comes first

so

you have a set of verbs

choose one from those verbs randomly

next

you have some sort of data structure

that can relate one object to another

in this case, a verb to a set of nouns

think about htat

[fiery cosmos]

ok

sorry about that

[marble obsidian]

hello, i want to make a question with multiple answer (if i write 'a' the algorithm write Exemple)

if someone know how it work that could be nice i'm beginning with python

[trim fiber]

You need to check that x variable is "a" string so

if x == "a":
  pass

[split dawn]

^^^

[trim fiber]

!code

[halcyon plank]

Here's how to format Python code on Discord:

```py
print('Hello world!')
```

These are backticks, not quotes. Check this out if you can't find the backtick key.

[trim fiber]

Your indentation is wrong, it should be

def tip_calculator(amount, percentage):
    if percentage >= 0 and percentage >= 100:
        return amount + (amount * percentage)
    else:
        return -1
print(tip_calculator(10, 2))

As you can see there are no spaces (or no tab) before print

Okay, there is problem with percentage variable, you can use 0 <= percentage <= 100 notation

!e

def tip_calculator(amount, percentage):
    if 0 <= percentage <= 100:
        percentage = percentage / 100.0  # convert from 0-100 to 0.0-1.0
        return amount + (amount * percentage)
    else:
        return -1
print(tip_calculator(10, 2))

[halcyon plank]

@trim fiber :white_check_mark: Your eval job has completed with return code 0.

10.2

[trim fiber]

@split dawn

[split dawn]

Ah Gotcha! thanks so much!

[trim fiber]

🎉

[marble obsidian]

thanks

[tranquil barn]

https://www.codewars.com/kata/541af676b589989aed0009e7/train/python

Can someone provide me with a bit of a direction with this problem?

[vocal gorge]

This is a dynamical programming task of sorts, though it has a bit of a nonobvious twist. If you try to find out the number of ways to give out n money knowing the numbers for all lower n, you'll fail. But what you can do, is to calculate count_change(money, coins) if you know count_change(n, coins[:-1]) for all n<=money.

So essentially, start by calculating the number of ways (for all amounts of money up to money) for only the first coin, then add in the second, and so on.

If a word starts with h, the first element of the tuple will be False, True otherwise. Comparing tuples compares their corresponding elements in order. So as words starting with h get a False as first element, they will compare lower than any word not starting from h.

[open orchid]

oo okayy I get it. I just needed to know the false part. thanks!

[dusk anchor]

Hello
I recently tried to make a function that generates half pyramids.
So for example:
If the length input is 3:
The output will be:
***
****
*****
******
So i am actually really happy that i thought of this alg:

lines = [1, 2, 3 , 4]
counter = 0

character = '*'
for line in lines:
    if line == 1:
      print(character * triangle_length)
else:
     counter = triangle_length + line - 1
     print(character * counter)

So actually the equation is the following:
x = length + (line - 1)
What do you guys think on that??

[vocal gorge]

you can get rid of an explicit lines list and use a range instead. Is the last line really different enough to warrant an else of its own? I'd probably do something like:

for count in range(length,length+4):
    print("*"*count)

[dusk anchor]

Yeah thats a good solution and to be honest i did thought of that. I just wanted to keep things analysed for my friends to understand that and also for newbies. However what do you think about the alg.

[frigid tulip]

which help chat is best to help with an api that im using

[spring jasper]

The help channels? #❓｜how-to-get-help

[frigid tulip]

bruh i completely forgot about those, tysm

[fading sky]

I'm having a problem with running my code on leetcode. Here's the question

here;s my sol for it:

def shift(arr):
    initial_length = len(arr)
    i, count = 0, 0
    n_0 = arr.count(0)
    while (i<initial_length):
        if 0 in arr[count:]:
            index = arr.index(0,count)
            arr.insert(index, 0)
            count = index + 2
        else:
            break
        i += 1
    arr = arr[:len(arr) - n_0]

This solution seems to work fine in jupyter notebook, but not on leetcode

this is what leetcode has to say

but the exact same gives the correct output in jupyter notebook, I'm just returning arr here so that I can check it.

[agile sundial]

what's the question?

surely you have more than the expected input and output

@fading sky

[fading sky]

oops sorry, i pasted the wrong image for the question, one moment plz

[flint kite]

"ModuleNotFoundError: No module named 'PQHeap'" why does this occur?

[serene oracle]

@fading sky I think you can simplify this quite a bit...

count = 0
start_zeroes = arr.count(0)
while 0 in arr[count:]:
    .....
return arr[:len(arr) - start_zeroes]

[serene oracle]

are you trying to import a module called PQHeap? that error means python can't find that module anywhere it knows to look for it.

[tiny river]

Is there any builtin module in python to convert hex strings to the list of int values? Like

flag='2e313f2702184c5a0b1e321205550e03261b094d5c171f56011904'
from textwrap import wrap
fconv = [int(x, 16) for x in wrap(flag, 2)]
#[46, 49, 63, 39, 2, 24, 76, 90, 11, 30, 50, 18, 5, 85, 14, 3, 38, 27, 9, 77, 92, 23, 31, 86, 1, 25, 4]

[mint jewel]

@tiny river bytes.fromhex

[tiny river]

Oh, you are right, list(bytearray.fromhex()) would be the exact equivalent, thank you

[fiery cosmos]

from time import time

n = 5 * 10**3

def measure_dict_speed(t):
    l = [t() for i in range(2*n + 1)]
    d = {l[i]: i for i in range(2*n + 1)}
    print('start')
    start = time()
    d[l[n]]
    end = time()
    print(end - start)

class a:
        def __hash__(self):
            return 0

measure_dict_speed(a)

time measured is 0.0

why is the lookup so fast?

if the hash is always 0, shouldn't it have to iterate through all the elements of one hashtable bucket?

[mint jewel]

it still won't take a time long enough to show up on time

use perf_counter instead

[fiery cosmos]

thanks, now the results are actually interesting

from time import perf_counter as time

n = 5 * 10**3

def measure_dict_speed(t):
    print(t)
    l = [t(i) for i in range(2*n + 1)]
    d = {l[i]: i for i in range(2*n + 1)}
    print('start')
    start = time()
    d[l[n]]
    end = time()
    print(end - start)

class a:
    def __init__(self, i):
        pass
    
    def __hash__(self):
        return 0

measure_dict_speed(a)
measure_dict_speed((lambda x: x))

yields

<class '__main__.a'>
start
0.0001002999999999421
<function <lambda> at 0x03C7F7C8>
start
1.4999999999876223e-06```

[fading sky]

nahh, we can do it without the start_zeroes, :

def shift():
    initial_length = len(arr)
    i, count = 0, 0
    while True:
        if 0 in arr[count:]:
            index = arr.index(0,count)
            arr.insert(index, 0)
            count = index + 2
        else:
            break
        i += 1
    arr = arr[:initial_length]

But this doesnt solve the problem, leetcode still says the same thing

[mint jewel]

yeah, it's measurable

[fiery cosmos]

should be O(n) right?

[mint jewel]

yup

[fiery cosmos]

def flatten_list(l):
    return [j for i in l for j in i]

def double_zeroes(arr):
    return flatten_list([([e, e] if e == 0 else [e]) for e in arr])```
this is probably horribly inefficient though

oh it's supposed to be in-place?

oops

[fiery cosmos]

using

n = 5 * 10**4```

I get

<class '__main__.a'>
start
0.0021157000000187054
<function <lambda> at 0x03D1F7C8>
start
2.500000022109816e-06```

so yeah, the access time of the all-in-one-bucket class is multiplied by 20 and the access time of the all-in-seperate-bucket integers is multiplied only by 2

interestingly enough it's not constant

so a bigger dict takes longer to access even if the distribution is optimal if I'm reading this correctly

[serene oracle]

you aren't using i for anything... and using while 1: ..... if <cond>: ..... else: break is very kludgy.... why not just do while <cond>: ...... Either start_zeroes or initial_length, take your pick.

[rose depot]

hi

[fading sky]

yeah I realized that and edited the code to:

def shift(arr):
    count = 0
    while True:
        if 0 in arr[count:]:
            index = arr.index(0,count)
            arr.insert(index, 0)
            arr.pop()
            count = index + 2
        else:
            break

[serene oracle]

but the loop 😭 .... im not sure if that is still O(n), does arr.index need to scan the whole list?

[vocal gorge]

this looks O(n^2) to me, because of index and insert

[fading sky]

what?? hoe can operations performed on object increase the time complexity.? I thought time complexity doesn't consider that.

[fading sky]

no, not the whole list, it scans from the index count since that's the parameter I'm passing into it.

[keen hearth]

Well because those are not constant-time operations. E.g. the running time of x.index(y) depends on the size of the list being indexed.

[agile sundial]

python is a bit tricky since it tends to hide many things from the programmer. things like in and max actually take O(n), but they look very simple

[fading sky]

ohh, interesting.

[serene oracle]

@fading sky think about how you would do it if you had to do it by hand. How could you find the max of an arbitrary list without looking at every element?

[fading sky]

i would sort the list & then pick the last element of the list.

[serene oracle]

actually that's worse.... you would be better off just scanning down the whole list and and taking the largest element you find

[jovial tartan]

what would be the best way to search for specifically formatted substrings in a string and replace them based on the text?

e.g. "i dont know #word#" where i would search for #word# and then replace it with something else

we already have what #word# is replaced with, the string searching part we dont know

[keen hearth]

@jovial tartan Are you familiar with the re module?

[jovial tartan]

yeah but regex is pretty slow right

it's exponential time because it backtracks

[lean dome]

That depends on the pattern you use. There's no backtracking needed for a pattern like #([^#]*)#

[dreamy aurora]

hey guys, I'm using breadth first search and I'm trying to find the shortest distance from the top-left of a matrix to the bottom right. I start by assigning a coordinate to each number, then:

• Starting from the top left, I add its neighbors to the queue
• I check if the coordinates of the neighbors equals the end, if not, I pop it from the queue, and add the neighbors of the point.
  and this repeats, until the bottom right coordinate is reached.

But I don't know how I can find the shortest path:

[
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0]
]

I'm really fried on this.

[agile sundial]

bfs will find the shortest path simply because of how it is

the first path you find to the bottom right corner will be the shortest path

[astral sundial]

How can i print all my return?

class Calcs:
    def __init__(self):
        self.ALL_FILES = []
        self.PATH = '..\Jonque'
        self.PY_FILES = []

        self.percentage()

    def percentage(self):
        for root, dirs, files in os.walk(self.PATH):
            for file in files:
                if not file.endswith('.'):
                    self.ALL_FILES.append(os.path.join(file))

        for root, dirs, files in os.walk(self.PATH):
            for file in files:
                if not file.endswith('.'):
                    if file.endswith(".py"):
                        self.PY_FILES.append(os.path.join(file))

        NB_PY_FILES = len(self.PY_FILES)
        NB_FILES = len(self.ALL_FILES)

        PY_PERCENTAGE = NB_PY_FILES*NB_FILES/100

        return NB_PY_FILES, NB_FILES, PY_PERCENTAGE


if __name__ == '__main__':
    # * Test function percentage
    t = Calcs().percentage
    print(t[0])

[dapper sapphire]

Just replace print(t[0]) with print(t)

[dreamy aurora]

sure, but how do I keep track of the shortest path?
For each of the nodes, I track the neighbors RIGHT and BELOW of it. I'm left with an array of checked coordinates which isn't the shortest path.

[agile sundial]

maintain a dictionary of "parents"

[astral sundial]

It return that: <bound method Calcs.percentage of <__main__.Calcs object at 0x000002C205B7E400>>

:/

[agile sundial]

that holds the node that you were at previously

[dapper sapphire]

Add parenthesis after percentage so this t = Calcs().percentage becomes => t = Calcs().percentage()

[astral sundial]

Thx it work ;)

[dapper sapphire]

So in a tree data structure, are insert, search, tree traversal(preorder, inorder, postorder), height and delete the most common methods?

[astral sundial]

Yes i think so

Hello again lol, when i insert all my files of my main dir in my list i get some file like this 30ebaa67ceab1b10272337e894530a1624c098
How can i insert all files without files like this?

My code:

        for root, dirs, files in os.walk(self.PATH):
            for file in files:
                if not file.endswith('.'):
                    self.ALL_FILES.append(os.path.join(file))

[dapper sapphire]

What are some other tree structures that are good to know?
So you dont wanna append files that look like this 30ebaa67ceab1b10272337e894530a1624c098?

[astral sundial]

I don't know :/ Sorry.
Yes exactly .

[dapper sapphire]

I guess maybe one thing you could do is check the file type of this file. If rest of the files you want dont have this file type then you could make a conditional on this file type and not append it.

[astral sundial]

Yes but i don't know how to get it :(

I think to get type i can do:

t = var
print(type(v))

[dapper sapphire]

Yeah, but that would only show you the data type for variables and classes. It wont show you the file type.

[astral sundial]

Oh... How can i do that so?

[dapper sapphire]

Does this file have an extension at the end?

something like .txt .ddb?

[astral sundial]

No extensions it only return that: 31dabc9597401f70b5e4167e3e361ae2b26f69

[dapper sapphire]

ok then I guess you would have to look at the mime type of each file

Maybe give this a look https://stackoverflow.com/questions/16872139/how-can-i-get-a-file-extension-from-a-filetype

[astral sundial]

I know, i need to exclude git folder but how?

Any idea maybe?

[dapper sapphire]

If all of your other files have an extension, but this is the only file that doesnt have an extension, then you can exclude files that dont have an extension.

But if it's a mix then checkout that stack overflow link and look at mimetype and python-magic modules.

[astral sundial]

So i fix it thx very much :)

[dapper sapphire]

How did you fix it?

[astral sundial]

Like this:

class Calcs:
    def __init__(self):
        self.ALL_FILES = []
        self.HTML_FILES = []
        self.PATH = '..\Jonque'
        self.PY_FILES = []
        self.SASS_FILES = []
        self.EXCLUDE = ['.git']

        self.percentage()

    def percentage(self):
        """
        Generate percentage of file with specific extensions.

        Returns:
            [int]: This is percentage for each files extensions.
        """
        for root, dirs, files in os.walk(self.PATH):
            dirs[:] = [d for d in dirs if d not in self.EXCLUDE]
            for file in dirs:
                self.ALL_FILES.append(os.path.join(file))

[dapper sapphire]

Yeah that would work if you want to exclude everything inside .git directory

[astral sundial]

Yeah ;)

[fiery cosmos]

I am looking for someone who can help me with an algorithm. Can someone please help me?

[dapper sapphire]

Post your question and if someone can they will.

[fiery cosmos]

I need to create an algorithm that decrypts an encrypted password. For example i can have print(encrypt("pineapple"))so that it encrypts pineapple and the encrypting algorithm also puts and x in the end of the word which is password = password + 'x', and the password is generated by print(encrypt(password))where the password would be "pineapple" like in the beginning. I need to create an algorithm which sees that encrypted password, sees if it has an x, removes it, which i think will be in a loop and then password = password - x , and then reverses the encrypted password so it decrypts it. The password encrypting algorithm is made by reversing the first two digits. Pineapple would be nepipaple. Where do i start???

[urban tulip]

def cuttingCakes(number_of_cakes: int, number_of_people: int) -> int:
    '''
    Need to deliver n cakes to m people with constraints below:
    . each cut divides a cake into 2 parts (equal or not equal)
    . each person get an equal amount of cakes and that all of cakes should be delivered

    how to do it with minimal cuts?

    e.g
    3 cakes, 3 people --> needs 0 cuts (1 cake/ 1 person)
    6 cakes, 3 people --> needs 0 cuts (2 cakes/1 person)
    3 cakes, 6 people --> needs 3 cuts (0.5 cake/1 person)
    3 cakes, 5 people --> needs 4 cuts (0.6 cake/1 person)

    '''
    minimal_cuts = 0

    if number_of_cakes == number_of_people or number_of_cakes == 0 or number_of_people == 0:
        pass

    elif number_of_cakes > number_of_people:
        minimal_cuts += cuttingCakes(number_of_cakes % number_of_people, number_of_people)

    else: 
        minimal_cuts += number_of_cakes
        number_of_people = number_of_people - number_of_cakes
        minimal_cuts += cuttingCakes(number_of_cakes, number_of_people)

    return minimal_cuts

if __name__ == "__main__":
    print(cuttingCakes(3, 5)) 

could you have a look at my script? i'm not sure if this algorithm always works.

[dapper sapphire]

The password encrypting algorithm is made by reversing the first two digits. Can you clarify "reversing the first two digits" because this doesnt make sense Pineapple would be nepipaple.

[dapper sapphire]

When does it fail?

[fiery cosmos]

`def isEven(number):
return number % 2 == 0

def getEvenLetters(password):
evenLetters = []
for i in range(0, len(password)):
if isEven(i):
evenLetters.append(password[i])
return evenLetters

def getOddLetters(password):
oddLetters = []
for i in range(0, len(password)):
if not isEven(i):
oddLetters.append(password[i])
return oddLetters

def encrypt(password):
encrypted = []
if not isEven(len(password)):
password = password + 'x'
evenLetters = getEvenLetters(password)
oddLetters = getOddLetters(password)
for i in range(int(len(password) / 2)):
encrypted.append(oddLetters[i])
encrypted.append(evenLetters[i])
return encrypted`

This is the encrypting code. Can't describe it better than the evidence.

[urban tulip]

I did some test cases, it returned correct result. but i'm not sure if it always works with all cases

[mossy forge]

hey could someone help with a minor problem?

[urban tulip]

ask your question, do not ask to ask 👀

[turbid wharf]

i'm currently working on how to estimate PI with metropolis algorithm (MCMC)
unfortunately i don't where to start and how to proceed
any help would be appreciated

[south yacht]

so I have a data struct of X,Y pairs of Points. I need to convert the X,Y values to "screen space"....how to do this?

I'm not familiar with the math needed to construct this algo

which why I need assistance. 🙂

[main flower]

wdym by screen space

[dreamy aurora]

has anyone used breadth first search and tracked the nodes which they have visited for the shortest path?

i'm stuck on how to do that.

[main flower]

wdym? Where are you stuck

[dreamy aurora]

so, I'll give you an example. I have a matrix:

1 0 0 0
0 0 0 0
0 0 0 1

(starting from top-left, ending at bottom-right). Using BFS add each neighbor to the queue until the bottom right is reached.

But I simply don't know how I can get the shortest distance from this

e.g. the actual path

I understand each time I go through a node's neighbors, I can add to a step counter to find the length of the shortest path, but I would actually like to know the coordinates of each point in the shortest path.

[south yacht]

@main flower By "screen space" I mean something like a 640x480 canvas... For instance if I have a Point with X,Y values of (-1088, 340) how to translate that to the 640x480 space?

[stiff schooner]

I am going to have an interview next Tuesday where I'll have to do some coding exercises in Python. What are some basic things to know? Like I know I am probably fine to use python's inbuilt sort as being O(n log n), but for example if I have a sorted list given what should I use to search it in O(log n)?

[agile sundial]

python has the inbuilt bisect module

[stiff schooner]

ah yeah that was that answer 😄

ok but that is a module I have to load?

[agile sundial]

import, yeah

[stiff schooner]

interview is on coderpad.io - can I load modules there?

[agile sundial]

never heard of it ¯_(ツ)_/¯

if you can run python code you should be able to import modules

i wouldn't worry about the environment not letting you import things. i would expect the interviewer to not let you, if they are testing you explicitly on binary search

[stiff schooner]

ok yeah maybe good to know how to quickly implement it from scratch anyways 😅

[agile sundial]

it's preeetty simple as far as algorithms go

[stiff schooner]

yeah I am still a bit of a newbie, but should be doable

[sage coral]

So for context: took this from a tech with tim video open_set is a priority queue, and g and f score are just dictionaries of scores. This is for an A* alorithm.

How does the f_score get updated in the open_set when it's changed? Aside from the first time where its added.

[cunning palm]

frineds help me

[austere sparrow]

@cunning palm Don't use random channels for running !e, we have #bot-commands

[vocal gorge]

IIRC you don't update the scores for nodes in open_set. Every node gets to be in the open_set exactly once - it gets added to it when a neighbouring node gets processed, then removed by getting processed.

It's the g_score and f_score mappings that get updated repeatedly.

[sage coral]

but then when you find a shorter path, how does it reorder correctly?

because with every iteration it needs to find the minimum node

[azure inlet]

The f-score is accounted for when it's added to the open set, which as you say is a priority queue, with the f-score being the priority metric.

After that, it's no longer needed.

[vocal gorge]

The heap gets reordered each time a new node gets added to it, if that's what you mean ^

[azure inlet]

What you can rely on is that when you pop something from the open set, it'll be the value with the lowest f-score.

[sage coral]

ah ok I think thats what was causing me confusion

[azure inlet]

That's what distinguishes a priority queue from a regular queue.

[sage coral]

that makes more sense. I should probably read up a bit on that stuff 😅

[dapper sapphire]

You can use your encrypted algorithm again to decrypt it.
The only problem is that it will work fine if the length of the string is odd.
Because your encrypted string is always even length. One way you could fix that could be it add two xx so that way you can get an odd length and get rid off the xx afterward. And you would have to modify your for loop:

    for i in range(int(len(password) / 2)):
        encrypted.append(oddLetters[i])
        encrypted.append(evenLetters[i])

[green orchid]

do anybody get what dies this do

def Mysterious_Function(n):
    if n > 350:
        return n - 47
    else:
        return Mysterious_Function(Mysterious_Function(n + 48))


n = int(input("Please enter a number : "))

Mysterious_Function(n)

[gaunt forge]

I am going to have an interview next Tuesday where I'll have to do some coding exercises in Python. What are some basic things to know? Like I know I am probably fine to use python's inbuilt sort as being O(n log n), but for example if I have a sorted list given what should I use to search it in O(log n)?
@stiff schooner do you mean search it or confirm that its sorted?

Binary search is log n, but confirming a list is sorted is n

[trim fiber]

[green orchid]

ahahhahah xD @trim fiber what does this code do xDDD

[trim fiber]

In first few lines you have function declaration, next in line n = int(input("Please enter a number : ")) program asks user for a number and then executes Mysterious_Function on given number n

[boreal pelican]

guys

when a key in a dict has 2 valeus defined to it how can i access the second one

[trim fiber]

!e

mydict = {
  "a": 0,
  "b": 1,
}
print(mydict["b"])

[halcyon plank]

@trim fiber :white_check_mark: Your eval job has completed with return code 0.

1

[boreal pelican]

bro

if both of the numbers were assigned to a

how can i take the second one

[gaunt forge]

You have a list assigned to the key?

[trim fiber]

Show some code, I don't know what are you talking of

[green orchid]

ok whats the problem i dont get it

[boreal pelican]

sec

[trim fiber]

What exactly?

[green orchid]

the else part when i do enter any number always gets me a 304

[green orchid]

..

[trim fiber]

!e

def Mysterious_Function(n):
  if n > 350:
    return n - 47
  else:
    return Mysterious_Function(Mysterious_Function(n + 48))

for i in [100, 200, 300, 400, 500]:
  print(f"i = {i}", Mysterious_Function(i))

[halcyon plank]

@trim fiber :white_check_mark: Your eval job has completed with return code 0.

001 | i = 100 304
002 | i = 200 304
003 | i = 300 304
004 | i = 400 353
005 | i = 500 453

[trim fiber]

!e

def Mysterious_Function(n):
  if n > 350:
    return n - 47
  else:
    return Mysterious_Function(Mysterious_Function(n + 48))

print(all(Mysterious_Function(i) == 304 for i in range(350)))

[halcyon plank]

@trim fiber :white_check_mark: Your eval job has completed with return code 0.

True

[trim fiber]

Nice but it's hard to proof it today for me because it's almost 11 PM

[zinc grail]

https://switowski.com/blog/type-vs-isinstance

[lean dome]

!e type(foo) and foo.__class__ should usually be the same thing, but technically a class can override what __class__ returns - by doing something crazy like:

class A:
    def __getattribute__(self, name):
        if name == "__class__":
            return str
        return getattr(super(), name)

a = A()
print(type(a))
print(a.__class__)

[halcyon plank]

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

001 | <class '__main__.A'>
002 | <class 'str'>

[fiery cosmos]

holy shit the lies

[lean dome]

yeah, uh, don't do that.

[wet fiber]

Hi

[dapper sapphire]

I did rangeSumBST the following way:

    def __rangeSumBST_llist(self, current, low, high, llist):
        if current is None:
            return 0
        if current is not None:
            self.__rangeSumBST_llist(current.left, low, high, llist)
            self.__rangeSumBST_llist(current.right, low, high, llist)
            if current.value >= low and current.value <= high:
                llist.append(current.value)

    def rangeSumBST_llist(self, low, high) -> int:
        current = self.root
        sum_all = 0
        llist = []
        self.__rangeSumBST_llist(current, low, high, llist)
        for element in llist:
            sum_all = sum_all + element
        return(sum_all)

I knew while implementing that this is not the ideal way because we have to iterate over the numbers again in the while loop to calculate the sum.

And then I came across a solution like the following:

    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        if not root:
            return 0
        sum = 0
        if root.val > L:
            sum += self.rangeSumBST(root.left, L, R)
        if root.val < R:
            sum += self.rangeSumBST(root.right, L, R)
        if L <= root.val <= R:
            sum += root.val     
        return sum

I just cant seem to get my head around when we do the comparison of the current node's value with the low, we traverse to the left of the tree:

        if root.val > L:
            sum += self.rangeSumBST(root.left, L, R)

[agile sundial]

what's range sum bst

[dapper sapphire]

@agile sundial
We would have a tree and we get a range, low and high. And we calculate the sum between the range:

# Example:
#          10
#        /    \
#       5      15
#      / \       \
#     3   7       18 
# 
# Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
# Output: 32

[agile sundial]

gotcha

[dapper sapphire]

It's a leetcode question.
https://leetcode.com/problems/range-sum-of-bst/

[agile sundial]

are you familiar with binary search trees?

[dapper sapphire]

I understand the insertion which makes complete sense:
If value_we_are_inserting is less than current_node_value then traverse to the left
If value_we_are_inserting is greater than current_node_value then traverse the right.

Yeah, I can create insert, height, search, traversal(pre, post, inorder) methods for a tree.

[agile sundial]

right, but what about the structure

you know that the values of the nodes to the left of the root are..

[dapper sapphire]

smaller

[agile sundial]

and the nodes to the right are..

[dapper sapphire]

bigger.

[agile sundial]

so knowing that, can you figure out why they did what they did in that solution @dapper sapphire

[dapper sapphire]

Yeah actually I see what's happening I just changed the order of the comparison to how I usually create the insert method.
I changed root.val > L to L < root.val. It's the same thing, but just that small switch helped me understand

Thanks!!

[agile sundial]

🎉

[dapper sapphire]

    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        if not root:
            return 0
        sum = 0
        if root.val > L:
            sum += self.rangeSumBST(root.left, L, R)
        if root.val < R:
            sum += self.rangeSumBST(root.right, L, R)
        if L <= root.val <= R:
            sum += root.val     
        return sum

So I simplified the above, but the above is definitely more optimized because we dont visit nodes that are greater then R and less then L:

    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        if not root:
            return 0
        sum = 0
        sum += self.rangeSumBST(root.left, L, R)
        sum += self.rangeSumBST(root.right, L, R)
        if L <= root.val <= R:
            sum += root.val     
        return sum

[signal knot]

What's an example of O(n^2) space complexity?

[agile sundial]

an adjacency matrix

[zinc grail]

anyone want to optimize a function?

[signal knot]

How does O(M*N) differ from O(N^2)

[zinc grail]

different letters

[lean dome]

If M=N they're the same. If M>N, then O(M*N) would be worse than O(N^2). If M<N then O(M*N) would be better than O(N^2).

[signal knot]

Thank you!

[fiery cosmos]

technically if M<N then an O(M*N) algorithm is also in O(N^2) since big Oh is an upper bound

But O(M*N) is indeed "better"

[fiery cosmos]

Is it possible to convert a two dimensional matrix to a single number without loosing information, in order to use it as an input for a genetic algorithm ?

[trim fiber]

Depends. For example if you have fixed 2x2 matrix with 0s and 1s you can transform it by using the following algorithm

              +---+
              | a |
+---+---+     +---+                                                     +-------+-------+
| a | b |     | b |                                                     | n & 1 | n & 2 |
+---+---+  => +---+ => (d << 3) | (c << 2) | (b << 1) | (a << 0) = n => +-------+-------+
| c | d |     | c |                                                     | n & 4 | n & 8 |
+---+---+     +---+                                                     +-------+-------+
              | d |
              +---+

[fiery cosmos]

wow

I did not understand a single thing in this algorithm lol

is there somewhere I could research that ? Does it have a name ?

[trim fiber]

In this case the 2x2 matrix is changed into 4-elements vector and each binary vector can be represented as an unsigned number

Maybe others will have better ideas

[fiery cosmos]

hum

okay

Is it how people that do ML with genetic algorithm give matrixes to their models ?

[trim fiber]

Idk

[fiery cosmos]

alright thanks

[potent yarrow]

need help in binary tree expressions should && be the root node? for question #2

[potent yarrow]

Did I do it correctly?

noicee

[solar timber]

Can I ask dynamic programming questions here?

[spring jasper]

Yes

[solar timber]

If it's difficult to understand from the screenshot:

There are different piles of cookies.

You need to chose a number 'p', and it will remove 'p' number of cookies from each pile... If a pile has less than 'p' cookies, no cookies are removed.

You keep selecting a value for 'p' until all cookies are finsihed. And we should finish all the cookies, in the least number of movies possible

EXAMPLE
1, 10, 17, 34, 43, 46 (These are the piles of cookies)

We take 'p' as 34
Piles(1, 10, 17) remain unaffected since they have less than 34 cookies
34 - 34 = 0 {So this piles is eliminated}
43 - 34 = 9
46 - 34 = 12

New piles = 1, 9, 10, 12, 17

We take 'p' as 9
Pile(1) remain unaffected
9 - 9 = 0
10 - 9 = 1
12 - 9 = 3
17 - 9 = 8

New piles = 1, 3, 8 {No point in writing 3 and 8 again}

We take 'p' as 8 {8 pile eliminated, all other remain same}
p = 3 {3 pile eliminated, 1 pile remains same}
p = 1 {1 pile eliminated}

ALL PILES ELIMINATED

[solar timber]

Please refer to the table for more examples

[pseudo hornet]

Problem Link :- https://codeforces.com/problemset/problem/1353/B - (B. Two Arrays And Swaps)

The test case which dosen't match to the problem statemment:-
    5 3
    1 2 3 4 5
    10 9 10 10 9

Answer of the test case:-
    39

expected answer:-
    30

The problem I found:-
    Why they took 5 elements instead of 3 cause the k-th value is 3 so they should take 3 elements
    And also why they took 3 and 5 they should take 9 and 9 cause we are here finding the maximum sum of an array

Pls try to help me to understand this problem...

[fiery cosmos]

Are there any free alternatives to algoexpert.io? I've really enjoyed somewhat competitive programming and I didn't really listen during my Algo & DS module in university, I was wondering if there are any free sites that let me practice code with challenges (such as hacker rank) but I want to gain some new Algo & DS knowledge.

[vocal gorge]

https://codeforces.com/ is the most DSA-focused practice site I know

[fiery cosmos]

thx

[main flower]

What's wrong with that test case? In the example input/output the answer to that test case is 39 cuz a can be 10, 10, 10, 4, 5

[dreamy aurora]

hey guys, if I wanted to find the shortest path in a maze, given that I can break any wall, can I use DFS for this?

[vocal gorge]

Any one wall on a path, or is it just that breaking a wall costs some time?

[dreamy aurora]

any singular wall on the path

I was thinking to find every single path to the endpoint and then just choosing the one with the least amount of walls, but I think that isn't the most optimized solution (plus I don't really know how to do it)

[vocal gorge]

I believe you need to consider two kinds of paths: without walls broken and with one. Just like normally in BFS you have an array of "distance to this tile along the shortest path", here you'll have two arrays, one for each kind of path.

And the update rule for normal tiles will be just "minimal of the neighbour distances + 1" (like normally in BFS), but for the wall-breaking array it'll be the minimum of:

1. The minimum of the neighbour distances for wall-breaking paths
2. If the tile is a wall, the minimum of the non-wall-breaking neighbour distances + 1.

I think this approach will result in properly considering all the paths.

(worst case scenario, I'm missing some reason why this can't be done via BFS at all and you'll have to use Dijksta/A*)

[dreamy aurora]

I see, so I can make a BFS for the maze without breaking any walls, and then make a BFS for the maze breaking one wall.

However I can't think of which wall I decide to break. Could I do this?
walls = []

• Beginning from the start point, check if the node is a wall.
• Add the wall to the walls I've already broken walls.append(wall coordinates)
• Find the shortest distance to the endpoint, given a broken wall.

Then repeating this until I have broken each wall once in all my runs? Then comparing shortest distances?

[vocal gorge]

You don't need to keep track of what wall is broken. Just do it like normally - calculate the distances, then backtrack from the target.

Like, you know the the path ends at the target. The second-to-last tile is the one from the target's neighbours with the lowest distance, the third-to-last one is the one from the second-to-last one's neighbours with the lowest distance, and so on.

[dreamy aurora]

That's the issue I have with BFS, I don't understand how to backtrack / keep track of nodes

[dreamy aurora]

e.g. say we had:

X 1 2 Y
3 4 5 6

and we want to get from X -> Y, and we can move up or down, we would add 1 then 3 to the queue, 2 then 4, Y then 5.
We have reached the destination but I don't see how we can get the nodes that we visited in order to get to Y?

well I guess I can do this problem without taking into account the order that we reach the destination, or the walls broken as you said.

but it's still something I can't get my head around.

[vocal gorge]

After you finish, you get an array of distances that'd look like this:

0 1 2 3
1 2 ? ?

where the two ?s didn't get visited because the search found Y first.

So what you do after that is backtrack from Y to X:

1. Start from Y.
2. Search the neighbours for the node with the lowest distance.
3. That's the next node (in the backtrack from Y to X).
4. Repeat until you get to X.

[dreamy aurora]

oh - I see!! I need to save that 🙂
so, you're essentially running DFS 2x? Once to find Y then to backtrack?

[vocal gorge]

would be something like:

def reconstruct_path(start,end,distances):
    path = [end]
    while True:
        cur = path[-1]
        next_node = min(neighbours(cur), key = lambda node: distances[node])
        path.append(next_node)
        if next_node == start:
            return path[::-1]

to reconstruct the path.

[fluid matrix]

can someone help me

its a discord bot

when i press

"run" it runs

for like

a millisecond

then stops

it does even say

"logged in as yadaydaday"

ya know

dm me with solution please

[dreamy aurora]

the on_message and its decorator should probably not be nested in on_ready

[fluid matrix]

OH

wait lemme try

still doing the same thing

[vocal gorge]

Another solution is to maintain a dictionary came_from mapping a node to, well, the node the currently known best path visited it from.

[fluid matrix]

what

[vocal gorge]

Nah, notice that the complexity of the reconstruction is linear with the length of the path - it doesn't scan all the cells, just a bit around the path.

[dreamy aurora]

i see, and the data structure of this "array of distances" will have to match the input?
Let's say for our input:

[[X, 1, 2, Y],
[3, 4, 5, 6]]

our array of distances will look like this?

[[0, 1, 2, 3],
[1, 2, ?, ?]

[vocal gorge]

It doesn't necessarily have to be an array, just some mapping that takes a tile and gives you the distance to it.

[dreamy aurora]

the folks at #discord-bots will most likely know how to help you with that 🙂

[fluid matrix]

yesyes

[dreamy aurora]

okay, I see. Thanks so much for the explanation, I couldn't get my head around how to actually find/reconstruct the shortest path!

So just to go back to the "wall" thing - why can I go about this without keeping track of which wall is broken? Can I just find normal BFS then add 1 to any points in my "array of distances" which have a wall?

[solar timber]

Someone please help

[vocal gorge]

I believe you need to do BFS to find the shortest paths without breaking walls, then do BFS again with slighly different rules for the wall-breaking.

Basically, for the second round, you'll be considering both the new (with wall breaking) distances and the old ones (without) when updating a distance

[solar timber]

Should I again send the screenshot?

[dreamy aurora]

my idea was to do BFS a lot of times, breaking one wall each then backtracking and comparing the distances (based on which wall is broken). Taking the minimum distance will give me the most optimal wall to break - but I think that it may be too much

[solar timber]

There are different piles of cookies.

You need to chose a number 'p', and it will remove 'p' number of cookies from each pile... If a pile has less than 'p' cookies, no cookies are removed.

You keep selecting a value for 'p' until all cookies are finsihed. And we should finish all the cookies, in the least number of movies possible

[dreamy aurora]

because I'm essentially running BFS for however many walls there are - then backtracking - surely that gets pretty slow.

[solar timber]

EXAMPLE
1, 10, 17, 34, 43, 46 (These are the piles of cookies)

We take 'p' as 34
Piles(1, 10, 17) remain unaffected since they have less than 34 cookies
34 - 34 = 0 {So this piles is eliminated}
43 - 34 = 9
46 - 34 = 12

New piles = 1, 9, 10, 12, 17

We take 'p' as 9
Pile(1) remain unaffected
9 - 9 = 0
10 - 9 = 1
12 - 9 = 3
17 - 9 = 8

New piles = 1, 3, 8 {No point in writing 3 and 8 again}

We take 'p' as 8 {8 pile eliminated, all other remain same}
p = 3 {3 pile eliminated, 1 pile remains same}
p = 1 {1 pile eliminated}

ALL PILES ELIMINATED

[vocal gorge]

@dreamy aurora I think you just need something like this for the second round:

# distance1 - shortest distances without breaking walls, already calculated
# distance2 - shortest distances with breaking walls, being calculated

# to calculate the distance2 for a tile:
neighbours = get_neighbours(tile):
d1 = distance1[tile]
d2 = distance2[tile]
for neighbour in neighbours:
    if visited[neighbour]:
        continue
    distance2[neighbour] = min(distance2[neighbour], d2+1)
    # and if the neighbour is a wall, there's another option:
    if is_wall[neighbour]:
        distance2[neighbour] = min(distance2[neighbour], d1+1)
    to_visit.append(neighbour)
visited[tile] = True

very roughly

basically, instead of just updating using the current array of distances, you also update walls using the wallless one

[dreamy aurora]

alright - thanks very much for the help I really appreciate it. I'm gonna save what we discussed and give it a go soon, and I'll come back with what I devised. Thank you!! 🙂

[hexed raven]

for solving the 15 puzzle i am using the A* algorithm but my code doesn't give any output instead runs in a loop unless i terminate it

['R', 'L', 'R', 'L', 'R', 'L', 'R', 'L', 'R', 'L', 'R', 'L', 'R', 'L', 'R', 'L', '
R', 'L', 'R', 'L', 'R', 'L', 'R', 'L', 'R', 'L', 'R', 'L', 'R', 'L', 'R', 'L', 'R']

A* algo I used ⏬
BY using A* algorithm i.e F(n) = G(n) + H(n)
G(n) = distance form initial state to goal state
H(n) = number of misplaced tiles by comparing the current state and the goal state.

anyone here guys....

[solar timber]

Someone pls help🙏

[shell bobcat]

The first move always seems to be to the highest number such that a stack with a larger number of cookies is reduced to the same value as a stack with a smaller number of cookies

Perhaps you can trace through and figure something out from there, I'd look into recursion and what the different possible cases would be

[solar timber]

But That's not true for the third case

[shell bobcat]

well shit

nvm then lmao

where does the link lead?

[solar timber]

Idk, I got this from a friend

He wanted me to help him, but I can't figure it on my own lmao

[shell bobcat]

yeah lmao

One thing I see that might help is that correct answer should never be the largest pile

I feel like that link would provide more information about the problem, with the name of the algorithm or something it might be googleable

[solar timber]

Yeah, and also that 'p' is always equal to number of cookies in a pile

And they have mentioned that Greedy algorithms are not the best way, so maybe we need to do something which also takes the future moves into account

Bcs it's always not possible that 2 piles end up with the same number of cookies

[shell bobcat]

actually

Given that there are relatively few piles, order doesn't matter, and the only options eliminate at least one pile

It might not be too unreasonable to iterate through all possibilities and check

[solar timber]

The last example in the table is quite large

[shell bobcat]

That seems to be worst case scenario though

[solar timber]

But there are many options which eliminate one pile

[shell bobcat]

And even then there's only one other possibility

[solar timber]

And in some examples, we pick the middle-ish term, but in others we don't

[sage coral]

So I've got an A* Algorithm. Currently at the most it will explore like 200k nodes. My problem is this takes like 5-8 seconds. I need to have lots of these running at once and ideally the most it should be is 1-2 seconds. Any advice on how to cut down the time?

[shell bobcat]

Can you convert it to c++

[sage coral]

probably not.. its for a python class

[shell bobcat]

hm

[sage coral]

also I dont know c++ 😅

[shell bobcat]

fair

Depends on your code I guess

[sage coral]

should I paste it here?

https://paste.pythondiscord.com/molujafiti.rb

[shell bobcat]

What if it's the move such that it maximizes the total number subtracted from the piles in a single turn?

that's a greedy algorithm but it might work here

[solar timber]

Yeah, it might

I think that's it

[shell bobcat]

this is actually fascinating lmao

[solar timber]

I'll try it later and will let you know

doing hw rn 😦

School gives so much hw 😦

[shell bobcat]

nvm it literally says that doesn't work lmao

[solar timber]

Lol, just read that

We do know that we must eliminate one pile every move

[shell bobcat]

oh god nvm

it's trivial lmao

"It suffices to examine only strictly descending move sequences"

[solar timber]

So, p = no. of cookies in one pile

In every example, except the 4th one, the first value of 'p' is the middlish term

@shell bobcat

[shell bobcat]

I think I have a solution

but I'm bad at recursion

testing it rn

[solar timber]

oh okay

[shell bobcat]

hm

so it works

but it's slow

[solar timber]

atleast it works

could you send the code?

[solar timber]

how slow?

[shell bobcat]

I did some optimizations

2-3s on my machine on the 2nd to last problem

https://paste.pythondiscord.com/fazelesupa.properties

I haven't tried the last one

the last one is < 10 seconds

on my machine anyway

It's not terribly slow but if the problems tested are much larger than the ones in the examples it will be lol

[solar timber]

oh wow

I can see why it's lengthy

It must be testing a lot of combinations

Thank you so muchh!!

[split dawn]

player_1 = input("Rock", "Paper", "Scissors")
player_2 = input("Rock", "Paper", "Scissors")
if player_1 != "Rock" and player_1 != "Paper" and player_1 !=
"Scissors" and player_2 != "Rock" and player_2 != "Paper" and player_2 !=
"Scissors":
return -1
else:
print("Error")

No matter what I do, I keep getting this error 😦

Write a program to play rock-paper-scissors. Your function will receive two inputs from player_1 & player_2 . If the inputs are anything other than ‘rock’, ‘paper’ or ‘scissor’ print “Error” (optional) and return -1 .

[sage coral]

you need to indent that last line

[sage coral]

and dedent the else
like this:

player_1 = input("Rock", "Paper", "Scissors")
player_2 = input("Rock", "Paper", "Scissors")
if player_1 != "Rock" and player_1 != "Paper" and player_1 != \
"Scissors" and player_2 != "Rock" and player_2 != "Paper" and player_2 != \
"Scissors":
    return -1
else:
  print("Error")

[split dawn]

Thank you!!

[sage coral]

np, but in the future you should put this in a general help channel - this is for algos and such

[split dawn]

Gotcha! thanks

[dapper sapphire]

Try putting it in data science and ai channel. People in that channel would be more familiar to pandas.

[bronze pine]

ah ok

[shell bobcat]

Sorry if this is the wrong channel, but I'm trying to turn the following code into a list comprehension:

for i in inp:
    if i > toSubtract:
        tempList.append(i - toSubtract)
    if i < toSubtract:
        tempList.append(i)
``` I have the following comprehension
```py
tempList = [i - toSubtract if i > toSubtract else i if i < toSubtract for i in inp]

but there is a syntax error at for i in inp], any ideas? I think it may be the lack of a default value when i == toSubtract, but I don't want anything added to the list in that case

[agile sundial]

you're probably better off keeping it a loop like you have

a list comp, while doable, will be less readable

if you really want a list comp I can show you how but it's really not worth it

also it errors because ternaries only have if and else

[shell bobcat]

Can I see how I would do it just so I know? I've never really used list comprehensions before and I'm curious

[solar timber]

templist = [i - toSubtract  for i in inp if i >  toSubtract]

[solar timber]

I don't know how to implement else in list comprehension

[agile sundial]

that's not equivalent

[shell bobcat]

The problem is you do kinda need both lmao

[solar timber]

Yeah ik 😅

[solar timber]

templist = [i - toSubtract if i > toSubtract else i for i in inp]

I'm on my phone rn, so can't test it 😅

[inland sage]

anyone here do algo trading?

[shell bobcat]

that's not equivalent because if i == toSubtract then i gets added to the list 😦

[solar timber]

templist = [i - toSubtract if i >= toSubtract else i for i in inp]

[lean dome]

templist = [i - toSubtract if i > toSubtract else i for i in inp if i != toSubtract] 

[shell bobcat]

then it just adds i - toSubtract if i == toSubtract tho

[shell bobcat]

You're a genius

thank you

[solar timber]

templist = [i - toSubtract if i > toSubtract else i if i < toSubtract for i in inp] 

[meager jetty]

Cookies ... interesting ... is there a way better than a brute force approach ?

[inland sage]

im gonna take that as a no

[solar timber]

If there is, we haven't found any

[meager jetty]

if u chose the smallest number all the time, it seems to conduct to the longest path ....

[solar timber]

Though, we've noticed a few things:
The value of p is always equal to the number of cookies in a pile, so it eliminates atleast one pile every time

We try to take a value of p such that 2 piles end up with the same number of cookies

[solar timber]

But that's not always possible

[meager jetty]

in exemple 1 removing 4 create other piles that already exist

ex1 is a triangle

[solar timber]

Almost always, the value of p is the middle-ish the middle term
Exception: 4th example

[meager jetty]

ex is fib.

so maybe finding all prime factors and try to remove the number that has the most in commun ?

[shell bobcat]

I've been working on brute force, you can get it pretty fast but past input length 11 or so it'll be slow in python

[meager jetty]

the last one is the same has the 1. it is a bigger trriangle with commun spacing

[solar timber]

But brute force beats the purpose of dynamic programming

[shell bobcat]

maybe with a stronger computer and c++ it can be reasonable to 12-13 ish

actually my desktop and c++ should be be able to handle size 13 fairly easily

[shell bobcat]

very fair

[solar timber]

Triangle?

[meager jetty]

or serie

it is a serie of 1 2 4 8 16 ...

instead of a serie of 1 2 3 4 ....

[shell bobcat]

correct

it appears to be the worst case scenario

[meager jetty]

so starting in the middle will create subserie equal .. I guess

[solar timber]

Prime numbers

[solar timber]

Yeah

@shell bobcat @meager jetty

[shell bobcat]

Hm

Idk if prime factorization will work

[solar timber]

Hmmm....

[runic tinsel]

in the screenshot there's a link

just find out what it says

there https://arxiv.org/pdf/1309.5985.pdf

oh, they don't know either

☹️

that's not the same problem btw, they are allowed to eat any number from any subset, not just an entire jar from all

nevermind then

[solar timber]

Please DM me if you figure anything out! Thanks!

[shell bobcat]

Alright so it appears this is an unsolved problem in mathematics lol

So my solution is probably the best you're going to get barring any optimizations

[runic tinsel]

the unsolved one wouldn't let you bruteforce that easily

this one is more constraned

[shell bobcat]

very true

[agile sundial]

they probably meant unsolved in polynomial time?

surely you could bruteforce whatever you wanted in exponential or worse

[shell bobcat]

either are unsolved as far as I'm aware, though that could just be because nobody bothered to look into the simplistic one

Right, it's unsolved without brute forcing

[runic tinsel]

what I mean is here you have n choices, so you can search

[shell bobcat]

you can reduce the search space but at some point you'll have to brute force

[runic tinsel]

cache = {}

def solve(arr):
   if not arr: return 0
   if arr not in cache:
     cache[arr] = 1 + min(solve(tuple(a-j if a>j else a for a in arr if a != j)) for j in arr)
   return cache[arr]     

just the obvious

it doesn't do "large to small" but they say in the task it doesn't actually matter , so maybe they are right and it doesn't

[solar timber]

Lol thanks for your help!

Btw, is there any site which holds competitions on dynamic programming?

[shell bobcat]

Didn't think about using a cache, that's way faster

I wonder how fast you could get it in c++ tbh

[vocal gorge]

codeforces holds competitions, and it's a rather DSA-focused site.

[solar timber]

Okayy, thanks!

[halcyon plank]

:incoming_envelope: :ok_hand: applied mute to @limber fog until 2021-04-27 06:50 (9 minutes and 59 seconds) (reason: links rule: sent 11 links in 10s).

[split sigil]

!unmute 205094367323488256

[halcyon plank]

:incoming_envelope: :ok_hand: pardoned infraction mute for @limber fog.

[limber fog]

sorry

[split sigil]

!paste you can use this

[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.pydis.com/

After pasting your code, save it by clicking the floppy disk icon in the top right, or by typing ctrl + S. After doing that, the URL should change. Copy the URL and post it here so others can see it.

[limber fog]

https://paste.pythondiscord.com/xoyicazice.rust help me pls

[limber fog]

like iwant to make all the link into one line

[stiff schooner]

I got a kinda simple question on hashtables I think... for some coding problems you don't need both key and value, so how do I best simplify it?

just basically have the keys be the values?

[fiery cosmos]

You could use a set

[stiff schooner]

is that called a hashset then?

[fiery cosmos]

Well, I guess that depends on the language. In Java they're called HashSet's yes. In Python it's just Set. But the underlying implementation is the same (using hashes and bucket for storing information)

[stiff schooner]

in Python^^

so wait how do I find stuff in O(1) time in a set?

[fiery cosmos]

value in set

[stiff schooner]

and that is O(1)? 😮

[fiery cosmos]

yeah

https://wiki.python.org/moin/TimeComplexity

[stiff schooner]

but also sets are unchangeable if I understand it right? So that I couldn't really build on the fly as I iterate through something right?

[fiery cosmos]

No they aren't immutable as far as I'm aware. Tuples are, but set's are not

!e

unique_nums = set()
unique_nums.add(1)
unique_nums.add(2)
unique_nums.add(3)
unique_nums.add(1)
print(unique_nums)

[halcyon plank]

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

{1, 2, 3}

[stiff schooner]

oh nice

ok one more set question... the time complexity thing says worst case is O(n) - how do the access cases differ for sets and is it something I need to worry about?

like is it O(n) for stuff that is not in the set?

[fiery cosmos]

no you don't have to worry about it

[stiff schooner]

great, thanks a lot!

[jolly mortar]

the worst case is O(n) due to hash collisions

when all the items in the set hash to the same value

in practice that is pretty much impossible

[limber fog]

can anyone helpme https://paste.pythondiscord.com/xoyicazice.rust for this case?

[vocal gorge]

as hahastinkypoop said ^, this isn't a problem in practice. As an example, you can create such a worst case manually:

class Collider:
    def __hash__(self): return 0 # always the same hash
    def __eq__(self,other): return False # not equal to anything

# make a set of these, and you'll see that all the operations are O(n)

[stone steeple]

Hey, anyone here know how to use odeint from scipy? I'm having a problem of setting up my derivative function that I need to feed into odeint

maybe someone else's perspective on the problem would be great

nvm I think i've done it

[hoary bronze]

treebased multimap /set
treebased map / set
hashbased multimap /set
hasbased map / set
Can anyone give me a source about this topics , im searching but i couldnt find anything that is fit to me

[tiny river]

f = open('output.txt', 'r')
ff = f.read().split('\n')
ff = hash( frozenset( [ bytearray.fromhex(x) for x in ff ] ) )

TypeError: unhashable type: 'bytearray'

Edit: Just converted it to a str and did bytearray right before usage, nvmnd.

[vocal gorge]

bytearray is the mutable version of bytes, yeah.

[tawdry ibex]

#web-development message (cross channel posting because it may fit here but i dont want to spam the information which was allready posted)

[tawdry ibex]

anyone know why xmltodict is unable to parse my xml
xmld = xmltodict.parse(xml)
xml is a string containing the xml data

but then when i wrap the xml variable to make it a bytes value

it C:\Users\walke\OneDrive\Desktop\trash nation states bot>py bot.py Traceback (most recent call last): File "C:\Users\walke\OneDrive\Desktop\trash nation states bot\bot.py", line 24, in <module> print(NS.getIssues('password','walksanator','user agent')) File "C:\Users\walke\OneDrive\Desktop\trash nation states bot\bot.py", line 20, in getIssues xmld = xmltodict.parse(bytes(xml, 'UTF-8')) TypeError: encoding without a string argument

why

it expects a string, but when i give it a string it wants a byte

[half sluice]

Finally im unbanned

Xd

[tawdry ibex]

and you are about to be banned again for channel misuse

[half sluice]

Lol nah

Oof i thought this is off topic

Sorry

[tawdry ibex]

i was about to say it is #python-discussion but that exist

[analog gull]

hey guys i have a question

about counting the number of times a statement is counted inside a loop statement

[misty light]

ok

what have you tried so far? @analog gull

[analog gull]

i have tried counting manually through trial and error, also i have been trying to use the summation formula @misty light

[misty light]

I think i need an example. I cant quite visualise your problem

[analog gull]

a= 2
b=20
count=0
countmult=0
for i in range(a, b):
    for j in range(2,4):
        count+=1
        if((j*i)%2==0):
            print(i,j)
            countmult+=1
print(f"if statement: {count}")
print(countmult) ```

i just dont know how to make a math formula out of that

[slender lava]

Hi guys I have a question here from my cs class I tould greatly appriciate it if anyone would be able to solve this using python or give some insight on were to start https://stackoverflow.com/questions/67289033/i-have-to-write-a-program-that-takes-a-sequence-of-integers-and-find-all-primed?noredirect=1#comment118937874_67289033

[ornate thistle]

For starters, may be you could try a double sum and a Dirac/Kronecker delta for the conditional part. I think it will suffice

[hoary bronze]

?

[tawdry ibex]

is there a fast way to get all keys with a ceartain value (i want to see how many have the same value for a voting system)

using tinydb because i dont care about data loss

[vocal gorge]

Not unless you've been maintaining a dict mapping from values to all keys with that value.

Of course, you can build such a dict in O(n).

[tawdry ibex]

oof so just search the dictionary and get all values

[vocal gorge]

Yup.

[tawdry ibex]

a perfectly legal way to loop over each data base and get the most common number py for f in DB.all(): votes = {} for k, v in f.items(): if int(v) <= 6: try: votes[str(v)] = int(votes[str(v)]) + 1 except Exception as e: votes[str(v)] = 1 print(votes) win = [0,0] for k, v in votes.items(): if int(v) > win[1]: win = [int(k), int(v)] print(win) NSA.submitIssue(f['id'], win[0]) time.sleep(1)

[vocal gorge]

I don't like except Exception. Nor, for that matter, unnecessatily casting votes[str(v)] to int.

[tawdry ibex]

in the db it is "2" would be a vote for 2

so it would be string 2

[vocal gorge]

But it's not the database one you're converting 😛

[tawdry ibex]

so no need to do it for indexing
but to tally votes and compare have to cast them

(also how do i delete a db entry)

or i could just wipe the db since all information should be there when it gets wipes and all necisarry commands executed

all it does is tally up 12h votes

[vocal gorge]

(converted to int32 when creating the array because I am using numba because numba go brrr
...why not np.bool though? 4 times less memory 😛 And yes, numba is dope.
Anyways the trivial bit I'm getting at is I need to add a value in every row at column 0 that is above zero.
not sure what you mean here, tbh

[lavish flint]

Hey data structures and algos gang, back again with an issue with some code that I'm running. This feels rather trivial but the results are yielding what I expect so I'm putting my code here to see if you might have some ideas.

I am looking over a huge numpy array with 3 columns. Column 0 starts with only 0's, this is the column that my results are returned in. Column 1 and column 2 are filled with 0's and 1's to indicate the true and false conditions (converted to int32 when creating the array because I am using numba because numba go brrr and I have like 3 million records and don't want to wait for this to run in future iterations because I might test like 80 different parameters in this analysis and without numba it takes like 4 minutes). Anyways the trivial bit I'm getting at is I need to add a value in every row at column 0 that is above zero. This will be a duplicated index of sorts, and I will simply be iterating the index after each row if the value is column 1 is 0. So, I figure my code would trivially be the following:

@njit
def loop(nparr,index_start=1):
     for i in range(nparr.shape[0]):
          #start the loop by declaring the first row's first value to be the index_start value, which is currently 1
          nparr[i,0]=index_start

          #if the second value of the first row is a 0, then we need to increment index_start by 1, which means the next row will be assigned 2 (means we found a new element in the pattern)
          if nparr[i,1]==0:
              index_start=index_start+1

#now outside of the definition of our function loop()
#convert the pandas dataframe to int32, then convert to numpy, pass to function loop()
output_frame=loop(input_df.astype('int32').to_numpy(dtype=int32)#is this the step that I am messing up?

[tawdry ibex]

you failed to use apy code=boxed

you need to box your code

failed

[lavish flint]

fml

[vocal gorge]

!code

[lavish flint]

I did it last time

[halcyon plank]

Here's how to format Python code on Discord:

```py
print('Hello world!')
```

These are backticks, not quotes. Check this out if you can't find the backtick key.

[lavish flint]

forgot how

[tawdry ibex]

use ```

[vocal gorge]

And no, I don't think I get what's your goal still.

[lavish flint]

im dying lmao it has been a long day

[vocal gorge]

WDYM by "add a value in each row"?

[lavish flint]

I mean replace the value in place 0 with the value if index_start

[vocal gorge]

uhh

[lavish flint]

IT ISNT WORKING

so trivial

[vocal gorge]

so just set the first column to 1 where the second column is 1?

[lavish flint]

and then increment

the increment is what is not working

[vocal gorge]

increment what?

[lavish flint]

index_start

by 1

if nparr[i,1]==0:
              index_start=index_start+1

For whatever reason on my work machine isnt working

[vocal gorge]

so you want the first column to basically count the number of 1s in the second column up to this point?

like

0 0
1 1
1 0
2 1
2 0
3 1
...

?

[lavish flint]

except it starts at 1

[vocal gorge]

tbh that can be done with just numpy

[lavish flint]

1 0
2 1
2 0
3 1
3 0
4 1

[vocal gorge]

it's just the cumulative sum of the second column

np.cumsum

[lavish flint]

this is why

I bought some math books

because I literally knew the pattern I was looking for, but I missed that super trivial thing

[vocal gorge]

nparr[:,0] = 1 + np.cumsum(nparr[:,1]) or something like that

[lavish flint]

the data that I am working with is Flight data, and I am building ordered pairs, so I wasnt even thinking about the 1's and 0s

thanks for your fresh eyes, I appreciate you

[vocal gorge]

as for why your function doesn't work, hmm

[lavish flint]

I blame numba

[vocal gorge]

lemme see..

huh, weird indeed

actually

wait, you're incrementing when you get a 0

not when you get a 1

is that right?

[lavish flint]

yes

when df[i,1]==0

increment

(i call df nparr)

[vocal gorge]

It seems to work fine for me.

#example data:
arr = np.zeros((10,2),dtype=np.int32)
arr[:,1] = np.random.randint(0,2,10)

arr2 = arr.copy()
loop(arr2)

print(np.concatenate([arr,arr2],axis=1))

[[0 1 1 1]
 [0 0 1 0]
 [0 0 2 0]
 [0 1 3 1]
 [0 0 3 0]
 [0 0 4 0]
 [0 1 5 1]
 [0 1 5 1]
 [0 1 5 1]
 [0 0 5 0]]

first 2 columns is original, second 2 columns is the result

[lavish flint]

I see, thank you again! I will compare our discussion with my code and if I figure out what I was doing wrong in a reasonable amount of time I will let you know

[vocal gorge]

@lavish flint had to play with cumsum for a while to get it right - because a 0 in the current row only gets counted since the next row, you need to shift the cumsum by 1. This gets me the same results as your numba function:

def numpy_sol(arr,start_index=1):
    arr[0,0] = start_index
    arr[1:,0] = start_index + np.cumsum(1-arr[:-1,1])

But it is slower than the numba one for N=1 million elements, interestingly:

%timeit loop(arr1)
%timeit numpy_sol(arr2)
# 985 µs ± 50.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
# 8.66 ms ± 136 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

And for 10 million, too:

N = 10**7    
arr = np.zeros((N,2),dtype=np.int32)
arr[:,1] = np.random.randint(0,2,N)
arr1 = arr.copy()
arr2 = arr.copy()
%timeit loop(arr1)
%timeit numpy_sol(arr2)
#9.76 ms ± 376 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
#85.5 ms ± 567 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

so yeah, this is a situation when a manual loop in numba is faster than a numpy-vectorized solution, cool.

[lavish flint]

wow thanks for expanding on that, I was about to try inverting my 0's to 1's and playing with the iteration condition a bit to see where that got me

and yeah, Numba seems to be used a lot for my analytics .. it really is great

[vocal gorge]

oh wait, just realised I borked my timeits, actually

I can't call the function on the same array because it modifies it, hold on

...but the results are the same if I do it right, so nevermind.

[lavish flint]

it totally works, thank you

again, because I keep imagining this data as the literal elements, not the abstract 0s and 1s, I totally missed that cumsum() is what I am building.. not some funky index based on if logic

[solar timber]

I'm a highschooler, and am not interested in DSA, but I love to solve dynamic programming questions. I've tried finding sites which offer dynamic programming questions, but all of them focus on DSA. Is there any site which has a good question bank of dynamic programming questions?

[fiery cosmos]

You should really take your time and understand how some of the data structures and algorithms behave. DSA is a fundemental part of programming and choosing the right algorithm / DSA can be the difference of a function taking minutes if not hours to complete instead of seconds

[white dagger]

Is there a way to differentiate between the first nibble of this two bytes objects at index position 2:

bytes_good = b'\x00\x00\x0c\xc2\xfd\x87\xa4\xad\x7f\x89^\x03\\\r%\xf3\xc0\x9b\x04\xc5'
bytes_good[0] & b'\xF0'[0] == 0:
>>> True # this is correct because there is a '0' as first nibble at index 2

bytes_wrong = b'\x00\x00\nzO\x9fLX\xa7\x89\x11k\xa4R\xce\xb3\xb6\x94M*'
bytes_wrong[0] & b'\xF0'[0] == 0:
>>> True # This should be False because there is a 'n' as first nibble at index 2!

[white dagger]

I just found out that converting them to hex notation they will both give me the same number of leading zeros 🙂 So, that is what I was looking for

[rain iron]

https://github.com/OmidNejadabbasi/Quine_McCluskey

[golden plank]

what algorithm should I use to calculate country vertices?
I have a white-black world map image with all countries borders on it and I want a list of all countries and their shapes (vertices) as output, and then calculate the visual center of each country using polylabel

a map like this https://d2gg9evh47fn9z.cloudfront.net/800px_COLOURBOX2114891.jpg

[lean dome]

You can get the high nibble of a byte with (bytes_good[2] & 0xf0) >> 4, or get the low nibble with bytes_good[2] & 0x0f

[white dagger]

@lean dome Does the way I interpret the high and low depends on the endianess of my CPU?

[random sage]

hi guys, i have engineering background + experience with python coding, but I struggle with solving leetcode questions. I had a few live coding interviews that need me to solve leetcode questions... but I really struggle alot even after I watch youtube videos, what would be a better way to kick start on learning algo and data struct?

[lean dome]

No, endianness is about the order in which bytes appear in some larger thing. Endianness doesn't affect anything within a single byte.

[old rover]

endianness?

is that a made-up word

no it's not

[white dagger]

@lean dome thanks!

[halcyon plank]

Hey @tawdry ibex!

It looks like you tried to attach a Python file - please use a code-pasting service such as https://paste.pythondiscord.com

[tawdry ibex]

you do know discord will now embed a code box right

i just finished re-factoring my api library (right refactoring is the right word for changing namespaces and class names and stuff like that while fixing bugs that came from changing name spaces)
https://paste.pythondiscord.com/ihozegirat.py

i organised it into

(these are all sub classes of api which is what you use to acess the entire api)

state variables that are mainly for internal use
functions all the functions go here for easy storage
vars either custom variable classes or variables that should be used with the api

exceptions you know what these are

[agile sundial]

is this dsa related?

[limber fog]

can dict have more than 1 values?
like

{'keys': [['subkey'], ['apple'], ['mango'], ['yogurt']]}

into this?

{'keys': ['subkey'], [['apple'], ['mango'], ['yogurt']]}

bcuz i need for more column on pandas

[tawdry ibex]

what is dsa this is a api wrapper/lib for the NationStates api
https://www.nationstates.net/pages/api.htm

[old rover]

dsa is data structures/algos

[old rover]

a key can map to multiple values

[tawdry ibex]

well it mean it technically contains a data struct
(api.vars.Issue())
and it could be considered a algorithym since it does some baisic processing on some of the information it recieves

oh god i clearly missed some bugs

just tried to query the api and got 3 errors
they are fixed now luckily

[lean junco]

why np.sum(np.square(matrix)) giving different answer from np.linalg.norm(matrix)??????

[mossy whale]

Hello there, I am creating a small app where there are multiple products for a user to choose from and the user will go through a series of questions and is eventually suggested a product based on the questions. I looked online for similar ideas but almost all of them require some kind of recommendation engines. I dont want to involve ml for such a small app. I was wondering if I could create some kind of a categorising system and rating based system. Basically if a user answers a series of questions positively in one category then suggest product of that category. But I am stuck - if a users all the answers in all the categories neutrally then how do I suggest a product ??
Basically I am trying to achieve a small suggestion system where one can answer a bunch of questions and get suggested appropriately. Any ideas ? Any simple algos ?
A very basic example would be a personality test.

[spring jasper]

1 key 1 value, the nature of that value may vary tho, you could have a key map to a list with a bajillion elements

You cant have

{key: value1, key: value2} 

the second value will overwrite the first one

And obviously you cant have ```
{key: val1, val2, ...}

[slate bear]

how can i import the numbers from a txt file in python? the numbers don't have to be read as a string

[agile sundial]

are you familiar with opening files?

[slate bear]

yes i do f = open('filename.txt', 'r')

[agile sundial]

right

[slate bear]

ok

how can i continue

[agile sundial]

so read the lines using that

[slate bear]

yes but when i do it the function reads my numbers as string and not as integers

i have done it like this

Python program for implementation of Bubble Sort

def bubbleSort(arr):
n = len(arr)

# Traverse through all array elements
for i in range(n-1):
# range(n) also work but outer loop will repeat one time more than needed.

    # Last i elements are already in place
    for j in range(0, n-i-1):

        # traverse the array from 0 to n-i-1
        # Swap if the element found is greater
        # than the next element
        if arr[j] > arr[j+1] :
            arr[j], arr[j+1] = arr[j+1], arr[j]

Driver code to test above

f = open('numbersbubblesort.txt','r')
myList = []
for line in f:
myList.append(line.strip())

bubbleSort(arr)

print ("Sorted array is:")
for i in range(len(arr)):
print ("%d" %arr[i]),

[agile sundial]

yeah, so convert them to ints

[slate bear]

myList.append(line.strip()) do i have to change something here?

[agile sundial]

yeah

use intthere

this is for some class?

[slate bear]

What do you mean?

[slate bear]

Like MyList.append(int.strip(line))

?

[agile sundial]

no

!d int

[halcyon plank]

int

class int([x])``````py

class int(x, base=10)```
Return an integer object constructed from a number or string *x*, or return `0` if no arguments are given. If *x* defines [`__int__()`](https://docs.python.org/3/reference/datamodel.html#object.__int__ "object.__int__"), `int(x)` returns `x.__int__()`. If *x* defines [`__index__()`](https://docs.python.org/3/reference/datamodel.html#object.__index__ "object.__index__"), it returns `x.__index__()`. If *x* defines [`__trunc__()`](https://docs.python.org/3/reference/datamodel.html#object.__trunc__ "object.__trunc__"), it returns `x.__trunc__()`. For floating point numbers, this truncates towards zero.

[agile sundial]

this work, is it for class?

[slate bear]

yes

[agile sundial]

see that embed above

[slate bear]

yes but why do we insert a class for the int(x)?

i don't know very well how to work with classes

[agile sundial]

it converts the string to an int

[dark egret]

x='10' # 10 as a string
x=int(x) # 10 as an int

[white pelican]

Hey, I'm a little new here. How do I start on data structures and algorithms?

[dark egret]

https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844
this is a really good book (computer science textbook) if you are completely new to algorithms
you can also start doing easy leetcode problems if you already have some knowledge of algorithms and programming

[white pelican]

Thank you kind sir/ma'am 🙂

[agile sundial]

it's also takes a very mathematical approach. if that's not for you there are a few other things you could try

the pins have some nice resources

[limber fog]

@spring jasper but the second keys have no value

[limber fog]

yeah thats really what i want

because i need to make ddataframe and for more column

[fiery cosmos]

does anyone reconmend like any college books or books online to study python? my main goal is to write algos for trading currencies. Otherwise, I'm looking for an experienced programmer who knows the coding side of things to write an algo with me as I learn. On my end I am putting down knowledge and the ideas that needed to be put into code form

knowledge as in theories, principles, price, volume, liquidity, other such factors.

getting live market place data in code as well that will be covered

[half lotus]

!resources we have some learning material here

[halcyon plank]

Resources

The Resources page on our website contains a list of hand-selected learning resources that we regularly recommend to both beginners and experts.

https://pythondiscord.com/pages/resources

[fiery cosmos]

@half lotus Appreciate it!