#algos-and-data-structs | Python | Page 92

fiery cosmos Nov 12, 2020, 6:31 PM

#

i knew it had to be a simple change

#

def solution(A, B):
    A.sort()
    B.sort()
    i = 0
    for a in A:
        while i < len(B) - 1 and B[i] < a:
            i += 1
        if a == B[i]:
            return a
    return -1

#

yep got it

#

open to any other suggestions however if u notice any

#

see this it works

#

also what will be the time complexity of your code?

#

the new while loop does work, is a while loop more effcient than an if?

#

hmm lemme check

#

while loop is log(n)

#

@desert cedar The problem is Given two sequences A, B find the smallest element that is found in both A and B. If not return -1

#

@fiery cosmos nope

desert cedar Nov 12, 2020, 6:33 PM

#

There is nothing to be counted then, so no counter should be used.

fiery cosmos Nov 12, 2020, 6:34 PM

#

from my quick google search the answer for a while loops complexity is log(n)

desert cedar Nov 12, 2020, 6:34 PM

#

While loops don't have a fixed complexity.

#

It depends on how you end the loop

fiery cosmos Nov 12, 2020, 6:35 PM

#

A.sort()
B.sort()
This part takes O(n log n)
------------------------------------------------
for a in A:
    while i < len(B) - 1 and B[i] < a:
        i += 1
    if a == B[i]:
    return a

How much does this part take?

#

wow this time complexity stuff can get a little confusing 2 secs

#

o(n2)?

desert cedar Nov 12, 2020, 6:36 PM

#

Why was the if changed to a while?

fiery cosmos Nov 12, 2020, 6:36 PM

#

@desert cedar to make it more efficient

#

O(n^2)??

#

no it is not to make it efficient, it is to make the code correct

mint jewel Nov 12, 2020, 6:37 PM

#

that is O(n**2)

fiery cosmos Nov 12, 2020, 6:37 PM

#

Well im guessing, i remember something like one loop is o(n), then another within it is o(n) again

mint jewel Nov 12, 2020, 6:37 PM

#

well, O(len(A)len(B))

fiery cosmos Nov 12, 2020, 6:37 PM

#

yes sorry o(n^2) is what i meant

#

Am I correct?

mint jewel Nov 12, 2020, 6:38 PM

#

yes

#

assuming both lists are n long

fiery cosmos Nov 12, 2020, 6:39 PM

#

nice

#

hmm

mint jewel Nov 12, 2020, 6:39 PM

#

since if B was fixed at 1k elements, it would be O(n)

fiery cosmos Nov 12, 2020, 6:39 PM

#

Im allowed to change 2 lines of the solution but im wondering if anything needs changed other than while loop that could improve it further

mint jewel Nov 12, 2020, 6:39 PM

#

you could do that in O(n) with sets I think

desert cedar Nov 12, 2020, 6:39 PM

#

Are you supposed to optimize it or just fix it?

fiery cosmos Nov 12, 2020, 6:40 PM

#

fix it but hopefully optimise it in the process as it will have extreme test cases run against it to test if it still holds up

#

as it works initially but bugs need to be fixed

#

I am thinking this is actually O(n) time complexity

#

the second while loop has some condition

#

and how can I be sure that it runs for every el in A?

mint jewel Nov 12, 2020, 6:41 PM

#

consider A of only positive numbers and B of only negative numbers.

#

B[i] < a will always hold

fiery cosmos Nov 12, 2020, 6:41 PM

#

there are some assumptions to be made i should make clear

#

what about the i < len(B) - 1 after first el in A?

#

1, 2, 3, 4

#

each element in the arrays is an int between 0 - 1,000,000,000

mint jewel Nov 12, 2020, 6:42 PM

#

oh, i does not get reset

#

that is probably a bug

fiery cosmos Nov 12, 2020, 6:42 PM

#

no it is not why would you need to reset i?

desert cedar Nov 12, 2020, 6:42 PM

#

It doens't need to reset, since it's sorted.

fiery cosmos Nov 12, 2020, 6:42 PM

#

since you can't find greater than first element of A

#

and you stop at the last element

mint jewel Nov 12, 2020, 6:43 PM

#

true

fiery cosmos Nov 12, 2020, 6:43 PM

#

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

after comparing with 1

[-1, -2, -3, -4]
              |
              i

i will stay there for rest of the code

#

so it is actually O(n) time

#

I cant believe I spent 50 minutes just to realise if should be while

#

this is like a technique called two pointer where you really write two loops

#

but the whole TC is O(n)

#

https://tenor.com/view/magic-shia-labeouf-snl-skit-fingers-gif-4860090

Tenor

mint jewel Nov 12, 2020, 6:45 PM

#

yeah, O(n) actually.

fiery cosmos Nov 12, 2020, 6:45 PM

#

why is while loop better than if loop for this?

mint jewel Nov 12, 2020, 6:45 PM

#

interesting

fiery cosmos Nov 12, 2020, 6:45 PM

#

does the while loop change it from o(n^2) to o(n)

#

?

desert cedar Nov 12, 2020, 6:45 PM

#

It's not better, the if just not the correct solution.

snow swift Nov 12, 2020, 6:45 PM

#

if loop?

fiery cosmos Nov 12, 2020, 6:45 PM

#

haha algorithms are interesting

mint jewel Nov 12, 2020, 6:45 PM

#

if is wrong

fiery cosmos Nov 12, 2020, 6:45 PM

#

sorry if statement

#

it works with an if statement though

#

🤔

desert cedar Nov 12, 2020, 6:45 PM

#

It doesn't for all inputs

fiery cosmos Nov 12, 2020, 6:46 PM

#

yeah so thats the problem

#

what inputs break it?

#

Id like to test it

#

uhh

desert cedar Nov 12, 2020, 6:46 PM

#

inputs where you have to search farther than 1 in b

mint jewel Nov 12, 2020, 6:46 PM

#

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

fiery cosmos Nov 12, 2020, 6:46 PM

#

yep

#

it breaks in this

#

you will be extinguished by the first loop

#

but you really have 6 as the answer

#

I just tried it with the while loop and that works, so im assuming im on the right track

#

nice quick test case :)

#

I am so bad at making testcases

#

any suggestions on test cases that could break the while loop?

#

I write a program for that 🥴

#

nope

#

a correct solution will not break

#

woop woop 😄

fiery cosmos Nov 12, 2020, 7:07 PM

#

If I split a string, how do I then reverse that split?

#

I know my question isnt well worded so I will show an example

mint jewel Nov 12, 2020, 7:08 PM

#

.split() is impossible, .split(sep) with sep.join

fiery cosmos Nov 12, 2020, 7:26 PM

#

Does anyone know how to make my code specifically remove entries with 'NULL' and not those with 'ANULLED'?

def solution(S):
    # write your code in Python 3.6
    S = S.split("\n")
    #Skip first row
    for i in S[1:]:
        #Only contains NULL not nill or ANNULLED
        if 'NULL' in i:
            S.remove(i)
    #Convert back to string with \n seperator
    str1 = "\n"
    return str1.join(S)

Example input:
'header,header\nANNUL,ANNULLED\nnull,NILL\nNULL,NULL'

Expected output:

ANNUL,ANNULLED
null,..)```

My output:
Removes ANNUL and ANNULLED

shy gate Nov 12, 2020, 8:14 PM

#

@fiery cosmos if 'NULL' in i: checks if the string contains NULL try if i == 'NULL': instead

fiery cosmos Nov 12, 2020, 8:16 PM

#

so i tried that

#

but it then breaks my other test cases and still does not fix my original test case

#

this is so annoying because I know youre right

shy gate Nov 12, 2020, 8:17 PM

#

i just realized this is *not #python-discussion. youre probably better off asking in a help channel

fiery cosmos Nov 12, 2020, 8:17 PM

#

ok np thx anyway dude

delicate trail Nov 12, 2020, 10:54 PM

#

can i ask for help for math in general not just python? im just stuck on this one exericice and i cant find teh answer, i only have 30min left to submit it or i get 0

agile sundial Nov 12, 2020, 10:57 PM

#

check the channel description

delicate trail Nov 12, 2020, 10:58 PM

#

well im bad with english its not my fmother language so i dont know if mathematical concepts counts as sequences

agile sundial Nov 12, 2020, 10:58 PM

#

the key part is as they relate to solving problems with Python

delicate trail Nov 12, 2020, 10:59 PM

#

ah then yes, i need to make a program from that

#

📎 unknown.png

agile sundial Nov 12, 2020, 10:59 PM

#

that doesn't look very python related

delicate trail Nov 12, 2020, 10:59 PM

#

that no but after i needt o make aprogram that will return the result of given n

#

but i first need to find the formula to that n which i cant find

agile sundial Nov 12, 2020, 11:03 PM

#

it's given, u_n+1 = 6u_n

frail sun Nov 12, 2020, 11:28 PM

#

Can someone help with creating Conways Game of Life? My code is nearly complete I'm just confused on this last bit. Please DM

oblique panther Nov 13, 2020, 1:05 AM

#

@frail sun you can get help in the server instead of over DMs

fiery cosmos Nov 13, 2020, 1:15 AM

#

can someone eli5 search engine services like elastic search and solr

#

do people have a server for their data and a server for their search engine?

#

how does the search engine server grab the data from the database, like a mongodb server for example

brave oak Nov 13, 2020, 1:17 AM

#

do people have a server for their data and a server for their search engine?
@fiery cosmos yes

fiery cosmos Nov 13, 2020, 1:18 AM

#

why dont people use the search engine thats built into things like mongodb

#

this is what i do so far

old thunder Nov 13, 2020, 1:24 AM

#

Anyone have a good solution to this: https://www.hackerrank.com/challenges/repeated-string/problem?h_l=interview&playlist_slugs[]=interview-preparation-kit&playlist_slugs[]=warmup

#

def repeatedString(s, n):
    if s == "a":
        return n
    
    if 'a' not in s:
        return 0
    
    string = s*(math.floor(n/len(s)))
    rem = s[:(n-(math.floor(n/len(s)) * len(s)))]
    
    a = 0
    
    for c in string:
        if c == 'a':
            a += 1
            
    for c in rem:
        if c == 'a':
            a += 1
  
    return a```

#

This seems to work, but gives a memory error with larger len(s) and n

brave oak Nov 13, 2020, 1:27 AM

#

how does the search engine server grab the data from the database, like a mongodb server for example
@fiery cosmos separate

#

sorry I got a call

#

why dont people use the search engine thats built into things like mongodb
@fiery cosmos efficiency

#

@old thunder post the question

#

and I’ll have a look

fiery cosmos Nov 13, 2020, 1:29 AM

#

@brave oak separate?

#

and why is

#

the built in one less efficient

brave oak Nov 13, 2020, 1:31 AM

#

@brave oak separate?
@fiery cosmos or rather

#

in some cases

#

you need to store two copies of the data

#

one on your normal database, and one on ES (this will probably be a subset)

#

but I understand there are ways to integrate ES with your database (Mongo is one case)

#

the built in one less efficient
@fiery cosmos hm

#

ES is quite a mature product

#

and lots of time has been spent tuning it for its specific usecase

#

searching.

old thunder Nov 13, 2020, 1:42 AM

#

@brave oak ```
Lilah has a string, s, of lowercase English letters that she repeated infinitely many times.

Given an integer, n, find and print the number of letter a's in the first n letters of Lilah's infinite string.

For example, if the string s='abcac` and n=10, the substring we consider is 'abcacabcac', the first 10 characters of her infinite string. There are 4 occurrences of 'a' in the substring.

brave oak Nov 13, 2020, 1:43 AM

#

ah, okay, I get it

#

let me read your code

#

@old thunder

#

you have this line string = s*(math.floor(n/len(s)))

#

can you explain your thought process?

old thunder Nov 13, 2020, 2:00 AM

#

Sorry, just saw this. Basically I was trying to get all of the characters that I could, without subdividing s

#

And then rem would be whatever is left, in order to make n characters

brave oak Nov 13, 2020, 2:02 AM

#

Sorry, just saw this. Basically I was trying to get all of the characters that I could, without subdividing s
@old thunder okay, so think about this

#

if n is big and s is small, what happens?

#

your idea is kind of correct

#

but the implementation is weird

#

it's solvable in two lines, btw

#

I don't really think I'm golfing but

#

yeah

fiery cosmos Nov 13, 2020, 2:10 AM

#

I succeeded learning some oop from making clear and nano programs

halcyon plankBOT Nov 13, 2020, 2:11 AM

#

Hey @fiery cosmos!

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

#

Hey @fiery cosmos!

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

#

Hey @fiery cosmos!

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

fiery cosmos Nov 13, 2020, 2:15 AM

#

https://paste.pythondiscord.com/hawoyuwaro.py
https://paste.pythondiscord.com/vaxulohori.py
https://paste.pythondiscord.com/ulazuderak.coffeescript

covert scaffold Nov 13, 2020, 2:49 AM

#

is it possible to define new pandas dataframes as part of a loop?

brave oak Nov 13, 2020, 2:49 AM

#

is it possible to define new pandas dataframes as part of a loop?
@covert scaffold yes. but why? (#data-science-and-ml probably more appropriate)

covert scaffold Nov 13, 2020, 2:50 AM

#

Aren't loops algorithms ? I figured it would fit here

#

I'm like clueless

brave oak Nov 13, 2020, 2:51 AM

#

how about

#

tell us what you wanna do

#

Aren't loops algorithms ? I figured it would fit here
@covert scaffold loops are part of algorithms, but the approach to solving problems with pandas can differ quite significantly from what you would do with less complex data structures

#

and pandas is a DS-specific tool, so

covert scaffold Nov 13, 2020, 2:52 AM

#

Ah that makes sense

brave oak Nov 13, 2020, 2:52 AM

#

you're more likely to get someone who knows how to solve the problem in the best way for pandas there

covert scaffold Nov 13, 2020, 2:52 AM

#

I will keep all my pandas related questions over there

oblique panther Nov 13, 2020, 2:53 AM

#

@covert scaffold loops are used in algorithms in the sense that they're a building block of programs. Though this channel is mostly about classical algorithms like efficient sorts, graph traversal, etc.

brave oak Nov 13, 2020, 2:53 AM

#

anyway, yeah, just post your question there and we can help you out

covert scaffold Nov 13, 2020, 2:55 AM

#

Thank you, I was just trying to assess whether its possible to create them within the loop or if I should just look for a workaround

#

I'm unwilling to post questions I haven't tried to solve by myself first

#

back to failing at coding 👀

brave oak Nov 13, 2020, 2:57 AM

#

sure, atb!

oblique panther Nov 13, 2020, 2:57 AM

#

atb?

brave oak Nov 13, 2020, 3:00 AM

#

all the best

agile sundial Nov 13, 2020, 3:01 AM

#

adenosine tri bhosphate

eager hamlet Nov 13, 2020, 6:07 AM

#

ok so i'm no expert in cryptography
but i was looking at rsa-2048 in https://en.wikipedia.org/wiki/RSA_numbers#RSA-250
and they said that it hasn't been factored yet
but if it is then how the frick did they find it in the first place (ping 2 reply thx)

flat sorrel Nov 13, 2020, 7:37 AM

#

The organizers have the prime factors and used them to create the number, but the participants don't have it

#

The challenge is for the participants to compute said factors

#

@eager hamlet

pallid phoenix Nov 13, 2020, 12:15 PM

#

Hello!, si i have a 2D list, every list in the list(there are X*X-1 lists in the list), is a list of 53 values, each value are SA/A/NAD/D and SD, except for the last value, being an email adress, i want to find how many SA/A/NAD/SD there is in total for each email adress so say we take 4 lists, 3 of them have email adress algo@gmail.com, and in the first value for all 3 of its lists it has SA, i want to save 3 to say a list with the name of the column, and then move o nto the next value a bit hard to explain but i've been stuck on making the algorithm for a while now and i would appreciate any help

#

TLDR 2Dlist, list has say 90Lists, these lists have 53 values, for the unique values in spot 53, i want to count all the values in the previous spots for each column, columns SA/A/NAD/D and SDcan have values

twin edge Nov 13, 2020, 1:09 PM

#

Use Counter data structure

pallid phoenix Nov 13, 2020, 1:11 PM

#

ooh thank you!, didn't even know it existed so ill go check it out

vagrant condor Nov 13, 2020, 3:24 PM

#

!code

halcyon plankBOT Nov 13, 2020, 3:24 PM

#

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.

vagrant condor Nov 13, 2020, 3:29 PM

#

hey! i'm a bit lost here.
ive got the result of a http links and what i have to do its to update those new links into my previous link.
For that i know that i must use a .get() function.
and i know also that

n = (u.get("href"))

is a dictionary. now when i try to update to the previous link

n[url] = n.get(url,0) + 1

i got traceback because url is a string.
this is my entire code

import urllib.request, urllib.parse, urllib.error
from bs4 import BeautifulSoup
import ssl
# Ignore SSL certificate errors
ctx = ssl.create_default_context()
ctx.check_hostname = False
ctx.verify_mode = ssl.CERT_NONE

url = input('Enter - ')
s = input("Enter position: ")
m = input("Enter count: ")

m = int(m)
while m > 0:
    html = urllib.request.urlopen(url).read()
    soup = BeautifulSoup(html, 'html.parser')
    tags = soup("a")
    m = m - 1
    u = tags[18]
    n = (u.get("href"))
    print(n)
    n[url] = n.get(url,0) + 1
    print(url)

#

what im doing wrong?

#

any help or advice please. thanks in advance 😄

pallid phoenix Nov 13, 2020, 6:28 PM

#

maybe its because you are adding a string and an int together? if you try n.get(url,0) + str(1)? or n.get(url,0) +"1", or maybe convert the number part of the url to int, add 1, and append it back as a string? @vagrant condor

vagrant condor Nov 13, 2020, 6:33 PM

#

My n is a string maybe that’s why I have a traceback

#

I think if I try to index the tags it would be easier

eager hamlet Nov 13, 2020, 7:24 PM

#

http://www.usaco.org/index.php?page=viewproblem2&cpid=643
ok so im doing a greedy method

#

so i first made a sliding window and (without considering the second part) just stuffed as many diamonds as possible in one case

#

then i removed those diamonds and did another

#

the thing is it fails for some test cases

#

any help?

#

(my code is in java so idek if i should ask here)

#

(ping if you wanna help plz)

eager hamlet Nov 13, 2020, 7:42 PM

#

turns out greedy dooesn't work frick

torpid rivet Nov 14, 2020, 2:44 AM

#

how do i enter in the info in this ?

📎 Screen_Shot_2020-11-13_at_9.39.32_PM.png

eager hamlet Nov 14, 2020, 3:29 AM

#

wait what

#

@torpid rivet you just type them into the console

#

and @clever orbit what have you tried so far?

pseudo pilot Nov 14, 2020, 5:19 AM

#

Given a set of distinct integers, A, return all possible subsets.

NOTE:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
Also, the subsets should be sorted in ascending ( lexicographic ) order.
The list is not necessarily sorted.

can anyone tell me the approach for this using recursion/backtracking?

eager hamlet Nov 14, 2020, 5:43 AM

#

@pseudo pilot what are the points?
bc this should be like exponential time

pseudo pilot Nov 14, 2020, 5:45 AM

#

i was able to solve it, but thanks anyways

eager hamlet Nov 14, 2020, 5:46 AM

#

oh ok

#

well, given a list of numbers, i have to find the sum of a distance between a number and every other number

#

like [1, 2, 3, 4]

#

for 1, it'd be (2 - 1) + (3 - 1) + (4 - 1) = 6

#

and p much the same thing for 2, 3, and 4

#

is it possible to do this with O(n)

#

precomputation for each element?

wraith valve Nov 14, 2020, 5:51 AM

#

this depends on ur assumptions

#

if u compute each difference before u decide to run ur function

#

ur gonna get ur linear

#

but if u compute ur difference in ur function thats gonna be quadratic

#

i think if u memonize u will prob get slightly better runtime than quadratic

forest sand Nov 14, 2020, 6:07 AM

#

Guys, I need help

#

I have created a stock price predictor algorithm that predicts the data with 97% accuracy

#

However, it fetches an year old data. How can I make it so that it gets the latest data? cuz the predictions are worthless if they are one year old

brave oak Nov 14, 2020, 6:14 AM

#

well, given a list of numbers, i have to find the sum of a distance between a number and every other number
@eager hamlet why?

fiery cosmos Nov 14, 2020, 7:00 AM

#

there is a O(2^n) brute force solution for generating every subset

next swallow Nov 14, 2020, 8:13 AM

#

Hi everybody. I got a minor problem of extracting list's element. (X X )
I would like to ask how I can remove string from the list if the substring contains non-targeted str？

For example, there is a list.
list = ["aabb","baza","babab","acba","aabbd"]

I want to screen out any string in the list that contains character that is not a or not b and then remove the corresponding string.

So the output will be
list = ["aabb","babab"]
when printed out

How can I use the loop to approach to the output？ please help :$

stable pecan Nov 14, 2020, 8:33 AM

#

In [1]: s = set("abc")

In [2]: s
Out[2]: {'a', 'b', 'c'}

In [3]: s.difference_update("ab")

In [4]: s
Out[4]: {'c'}

In [5]: s = set("a")

In [6]: s.difference_update("ab")

In [7]: s
Out[7]: set()

maybe this will give you an idea

sudden phoenix Nov 14, 2020, 9:11 AM

#

hello

#

Is there any interactive page for algorithms

#

where I can create them using block

eager cairn Nov 14, 2020, 9:49 AM

#

happy diwali to indians
🪔

next swallow Nov 14, 2020, 10:03 AM

#

Thanks @@stable pecan (_ _ )
However, I have no idea on it
As I am not allowed to split the element in the list
The example I given here is just the simplified ver. So
I would like to ask for the code input

#

(＿＿ )

stable pecan Nov 14, 2020, 10:17 AM

#

In [4]: my_list = ["aabb","baza","babab","acba","aabbd"]

In [5]: [set(string).difference("ab") for string in my_list]
Out[5]: [set(), {'z'}, set(), {'c'}, {'d'}]

next swallow Nov 14, 2020, 3:20 PM

#

This is my last solution. Thanks for the brainstorm ( ^ ^ )

📎 Screenshot_20201114-232012_Chrome.jpg

fast arch Nov 14, 2020, 3:39 PM

#

What's the difference between arrays & Stack?

eager hamlet Nov 14, 2020, 4:38 PM

#

well clearly the list index is out of range i mean

clever orbit Nov 14, 2020, 5:38 PM

#

well clearly the list index is out of range i mean
@eager hamlet why

eager hamlet Nov 14, 2020, 6:11 PM

#

do some debug prints, see why it's like that

clever orbit Nov 14, 2020, 6:28 PM

#

do some debug prints, see why it's like that
@eager hamlet well i think when i = 0 -> i - 1 = - 1

eager hamlet Nov 14, 2020, 9:17 PM

#

i mean why are you telling me lol
just go with it and see what happens

#

try and fiddle around with the loops, there's probably some dumb off-by-one error

clever orbit Nov 14, 2020, 11:04 PM

#

and I don't understand why still out of range

fiery cosmos Nov 14, 2020, 11:23 PM

#

is there a faster algorithm that finds strings between 2 special strings and adds them to a list? my algo:

def FindBetween(string,a,b,once=False):
    string = str(string)
    i = 0
    start = 0
    end = 0
    active = 0
    found = []
    while i <= len(string): 
        if string[i:i+len(a)] == a and active == 0:
            i += len(a)
            start = i
            active = 1
        if string[i:i+len(b)] == b and active == 1:
            end = i
            found.append(string[start:end])
            active = 0
            if once == True:
                break 
        i += 1
    return found

example:

fruits = "apple lemon orange    apple banana orange    apple pineapple orange"
FindBetween(fruits, "apple", "orange")
[" lemon ", " banana ", " pineapple "]

eager hamlet Nov 15, 2020, 1:18 AM

#

probably one of -1's or array indexes that makes everything go wonky
and maybe name your variables better names lol
no one can tell what you mean by c or h

forest sand Nov 15, 2020, 4:06 AM

#

Hey guys! anyone up?

#

I mean is anyone online?

hollow stratus Nov 15, 2020, 5:04 AM

#

Anyone here good with proving correctness in algorithms?

languid vector Nov 15, 2020, 6:32 AM

#

@fiery cosmos why didn't use Regex?

wet blade Nov 15, 2020, 7:10 AM

#

Can anyone help in finding optimized form of below code it is giving TLE, finding length of LIS of list ```py
def lengthOfLIS(nums):
tails = [0] * len(nums)
size = 0
for x in nums:
i, j = 0, size
while i != j:
m = int((i + j) / 2)
if tails[m] < x:
i = m + 1
else:
j = m
tails[i] = x
size = max(i + 1, size)
return size

n,q,s = map(int,input().split())
arr = [int(a) for a in input().split()]
last = 0
while(q):
l,r = map(int,input().split())
l = (l+slast-1)%n+1
r = (r+slast-1)%n+1
if l>r:
t = l
l = r
r = t
temp = arr[l-1:r]
last = lengthOfLIS(temp)
print(last)
q-=1 ```

#

for complete outlook of problem https://www.codechef.com/NOV20B/problems/UNSQUERS

fiery cosmos Nov 15, 2020, 8:51 AM

#

probably one of -1's or array indexes that makes everything go wonky
and maybe name your variables better names lol
no one can tell what you mean by c or h
@eager hamlet even I forgot my own code. only know it when Im coding at the moment. someone in another server said this is faster:

import re


def find_between(string, start, end):
    pattern = re.compile(f"{start}(.+?){end}")
    return pattern.findall(string)

rocky shore Nov 15, 2020, 8:51 AM

#

can someone guide me how to solve a problem?

fiery cosmos Nov 15, 2020, 8:51 AM

#

what probelm?

rocky shore Nov 15, 2020, 8:52 AM

#

i have a problem you have to sign a message with the number of letters that contains the message including the sign with words

fiery cosmos Nov 15, 2020, 8:53 AM

#

wdym by sign a message?

rocky shore Nov 15, 2020, 8:55 AM

#

like at the end of your message you add a string like this message contains n times lettre_k,....

#

but you need to take into account what you are adding

fiery cosmos Nov 15, 2020, 8:56 AM

#

what are you trying to find with your algorithm?

halcyon plankBOT Nov 15, 2020, 8:57 AM

#

Hey @rocky shore!

Uh-oh! It looks like your message got zapped by our spam filter. We currently don't allow .txt attachments, so here are some tips to help you travel safely:

• If you attempted to send a message longer than 2000 characters, try shortening your message to fit within the character limit or use a pasting service (see below)

• If you tried to show someone your code, you can use codeblocks
(run !code-blocks in #bot-commands for more information) or use a pasting service like:

https://paste.pythondiscord.com

rocky shore Nov 15, 2020, 8:58 AM

#

@fiery cosmos i am trying to get a verification in the way that this signature matches the number of letters

#

or char

fiery cosmos Nov 15, 2020, 8:58 AM

#

have code?

halcyon plankBOT Nov 15, 2020, 8:58 AM

#

Hey @rocky shore!

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

rocky shore Nov 15, 2020, 8:59 AM

#

yes

fiery cosmos Nov 15, 2020, 8:59 AM

#

what do you mean by signature?

rocky shore Nov 15, 2020, 9:00 AM

#

https://paste.pythondiscord.com/ibivudihob.py

#

like a postscript

#

postdata: os animamos a comprobar que: en este mensaje aparece cuatrocientas treinta ycuatro veces la letra a, veinte veces la letra b, doscientas cuatro veces la letra c, ciento dosveces la letra d, quinientas setenta y tres veces la letra e, veintisiete veces la letra f,veintitrés veces la letra g, dieciséis veces la letra h, ciento ochenta y tres veces la letra i,veintiséis veces la letra j, tres veces la letra k, ciento ochenta y seis veces la letra l, cientocinco veces la letra m, doscientas treinta y ocho veces la letra n, cinco veces la letra ñ,doscientas doce veces la letra o, cincuenta y nueve veces la letra p, treinta y una veces laletra q, doscientas cuarenta y siete veces la letra r, doscientas cincuenta y una veces laletra s, doscientas veintiuna veces la letra t, ciento trece veces la letra u, sesenta y sieteveces la letra v, una vez la letra w, seis veces la letra x, veintisiete veces la letra y, y onceveces la letra z

fiery cosmos Nov 15, 2020, 9:02 AM

#

is there a specific snippet of code you need help on or is it the whole thing?

rocky shore Nov 15, 2020, 9:02 AM

#

no i have to code an algo to find a signature that is valid

#

for any given message

fiery cosmos Nov 15, 2020, 9:06 AM

#

where is the signature located?

rocky shore Nov 15, 2020, 9:06 AM

#

def firmar_mensaje(mensaje, conteo)

#

it gives u the signature for the message but you have to somehow take into account the signature so that message + signature contains the number of letters that the signature specifies

fiery cosmos Nov 15, 2020, 9:10 AM

#

so all you need to do is find out if both the message string and the signature string are the same size?

rocky shore Nov 15, 2020, 9:10 AM

#

if it contains the same nmber of letters

#

the signature is of the form "this mesagge contains four houndred times the letter e , etc"

#

take this msg: Buenas tardes

#

output: Buenas tardes; en este mensaje aparece dos veces la letra e

#

but the message contines more than two time the letter e

#

ill translate

#

Good morning; in this message the letter e appears two times

cobalt sedge Nov 15, 2020, 9:15 AM

#

📎 Screenshot_2020-11-15_at_17.15.15.png

#

Could anyone help me with this? I am pretty confused with this question...

I was thinking like Bob will refill the water when he reaches the oasis... and the volume of water will equal to the distance between the current oasis and the next oasis

fiery cosmos Nov 15, 2020, 9:17 AM

#

@rocky shore

import re
def find_between(string, start, end):
    pattern = re.compile(f"{start}(.+?){end}")
    return len(pattern.findall(string))

this function finds the number of times a string was found between 2 special strings. is this what you wanted?

#

I dont think I can be of help much because I lack Spanish skills. maybe someone who speaks the language here will help you?

rocky shore Nov 15, 2020, 9:19 AM

#

ok thx

worthy breach Nov 15, 2020, 11:14 AM

#

hello im trying to write a recursive function that can take a number and return 1 if the sum of digits is even and 0 otherwise...

#

i managed to write a function that can get the sum recursively but i dont know how to check if the answer is even before using a return statement

#

im implementing the function in c but any help even if in python would be appreciated

#

int even_sum(int num)
{
    int sum,dig;
    if (num == 0)
        return 0;
        
    
        
    dig = num % 10;

    sum = dig + even_sum(num / 10);

    return sum;
}```

fiery cosmos Nov 15, 2020, 1:25 PM

#

def sum(n):
  if n < 10:
    return n
  return n % 10 + sum(n//10)

def check(n):
  if sum(n) % 2 == 0:
    return 1
  return 0

worthy breach Nov 15, 2020, 2:32 PM

#

sorry i probably should have mentioned it should be one function @fiery cosmos

#

thank you for the answer btw!

fiery cosmos Nov 15, 2020, 2:37 PM

#

oh I see

#

then

#

def sum_and_check(s, n):
  if n == 0:
    if s % 2 == 0:
      return 1
    return 0
  return sum_and_check(s + n % 10, n//10)

worthy breach Nov 15, 2020, 2:46 PM

#

o i see!

#

very nice

#

thanks for the help

#

im assuming u first call s as 0 right?

fiery cosmos Nov 15, 2020, 2:53 PM

#

yep :)

worthy breach Nov 15, 2020, 2:54 PM

#

awesome, never thought of taking advantage of using another parameter

#

could come in handy often

#

i dont know if the person checking my homework might appreciate it but i do XD

fiery cosmos Nov 15, 2020, 3:14 PM

#

just code more

#

you will get to know more shortcuts

tender crest Nov 15, 2020, 4:17 PM

#

I'm storing a NxN matrix in a file (2D list) and I need a way to rotate it by 90 degrees, i.e.:
from:

you'd get:

This could be easy if I just loaded the list into a python list and did something like: list(zip(*reversed(lst)))
Problem is that this 2D list is way too big to load it whole into memory so that's not possible.

The way I'm storing this list is basically in "blocks" in which the matrix is flat, each block containing certain amount of data (let's call this amount b), so basically for the example above, with block size of 2 the stored list would look like this: [1, 2], [3, 4], [5, 6], [7, 8], [9, 0], [0, 0], [1, 1], [1, 1]

I need some meaningful way to rotate this list without loading too many blocks into memory.
The storing works in a way where the amount of data each block can contain (b) is known and n (size of matrix) is also known and it will always be a multiple of b

I figured I could just go through these elements, get the block they're in, read it, get the element from that block, store it and get the block in which the corresponding element number (after rotation) would be. Then just swap those and write them back. Problem is that this would make way too many calls to write and read (2xN^2) calls to read and another (2xN^2) for write, which would be way too slow. Is there a more meaningful way to do this than just going through every element, finding the rotate pos and swapping it directly?

clever orbit Nov 15, 2020, 5:51 PM

#

my sorting doesn't work

fiery cosmos Nov 15, 2020, 5:52 PM

#

do you need to implement a sorting algorithm on your own?

clever orbit Nov 15, 2020, 5:53 PM

#

do you need to implement a sorting algorithm on your own?
@fiery cosmos yes

#

it gives
A.sort(key=lambda k: k[0]) TypeError: 'int' object is not subscriptable

fiery cosmos Nov 15, 2020, 5:54 PM

#

your count of inversions is too slow

#

n goes up to 10^6

#

also you need to sort a and b combined

clever orbit Nov 15, 2020, 5:55 PM

#

i think i need total run time O(n lo n)

#

also you need to sort a and b combined
@fiery cosmos how please ?

fiery cosmos Nov 15, 2020, 5:56 PM

#

so

c = [[fi, se] for fi, se in zip(a, b)]
c.sort()    # by default it is sorted based on first element

clever orbit Nov 15, 2020, 5:56 PM

#

geeks4geeks sort code also gives the same error

📎 unknown.png

fiery cosmos Nov 15, 2020, 5:57 PM

#

yeah they assumed arr is list of pairs

#

but in your code a is list of integers not list of pairs

azure nymph Nov 15, 2020, 6:11 PM

#

can I ask scripting question to read data from a csv file here?

fiery cosmos Nov 15, 2020, 6:16 PM

#

there is csv module for that

#

https://realpython.com/python-csv/

Reading and Writing CSV Files in Python – Real Python

Learn how to read, process, and parse CSV from text files using Python. You'll see how CSV files work, learn the all-important "csv" library built into Python, and see how CSV parsing works using the "pandas" library.

#

@azure nymph

azure nymph Nov 15, 2020, 6:39 PM

#

@fiery cosmos thank you

#

I did not clariffied my question, I wanted to use regex to search for certain passwords in a csv file using python script. I got it to work but my regex is not matching the right characters.

fiery cosmos Nov 15, 2020, 6:58 PM

#

So i want to look for a item in inventory with this code for thing in users[str(user.id)]["inv"]: n = thing["item"] a = thing["amount"]
but i want it to only look for the item fishingrod. how can i do that?
right now it scans al the items but i want to make it so it only looks for fishing rod and the ammount of fishingrods a person has

{"728265216453771274": {"wallet": 12839.0, "bank": 0, "inv": [{"item": "apple", "amount": 1}, {"item": "fishingrod", "amount": 0}]}

#

idk if i put this here

clever orbit Nov 15, 2020, 8:26 PM

#

so

c = [[fi, se] for fi, se in zip(a, b)]
c.sort()    # by default it is sorted based on first element

@fiery cosmos thx so the sorting i did isn't needed ?

shrewd cradle Nov 15, 2020, 8:49 PM

#

What's a good data structure in Python for one-to-one mappings?

#

Kinda like a dictionary but all the values are also unique and I want to get the key using the value

#

The keys and values are guaranteed hashable

#

I guess Enum does the job but I'm not sure how efficient it may be fore large datasets

stable pecan Nov 15, 2020, 8:58 PM

#

might be best to make your own class for this

stable pecan Nov 15, 2020, 9:13 PM

#

class OneToOne:
    def __init__(self, **kwargs):
        self._keys_to_values = {}
        self._values_to_keys = {}

        self.update(kwargs)

    def update(self, other):
        for key, value in other.items():
            self[key] = value

    def __setitem__(self, key, value):
        keys = self._keys_to_values
        values = self._values_to_keys

        if value in values:
            raise ValueError(f"{values[value]} already mapped to {value}")

        try:
            values.pop(self[key])
        except KeyError:
            pass
        keys[key] = value
        values[value] = key

    def __delitem__(self, key):
        keys = self._keys_to_values
        values = self._values_to_keys

        values.pop(keys.pop(key))

    def __getitem__(self, key):
        return self._keys_to_values[key]

    def __repr__(self):
        return repr(self._keys_to_values)

    def getkey(self, value):
        return self._values_to_keys[value]

something like this

#

@shrewd cradle

shrewd cradle Nov 15, 2020, 9:17 PM

#

Ah thanks! Lemme try to understand this...

stable pecan Nov 15, 2020, 9:18 PM

#

the __setitem__, __delitem__, __getitem__ dunder methods allow you to access it like a dictionary

#

In [2]: o = OneToOne()

In [3]: o[1] = 2

In [4]: o[3] = 2
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-4-67a184e225d8> in <module>
----> 1 o[3] = 2

~\Documents\Python\sacks\bijection.py in __setitem__(self, key, value)
     15
     16         if value in values:
---> 17             raise ValueError(f"{values[value]} already mapped to {value}")
     18
     19         try:

ValueError: 1 already mapped to 2

In [5]: del o[1]

In [6]: o[3] = 2

In [7]: o._keys_to_values
Out[7]: {3: 2}

In [8]: o._values_to_keys
Out[8]: {2: 3}

#

well, that's just playing around with it --- i don't guarantee no bugs

shrewd cradle Nov 15, 2020, 9:20 PM

#

I get the general idea 😄

zenith creek Nov 15, 2020, 9:45 PM

#

trying to get some help on a topic - do I post here or do I just grab a help channel and start posting there??

latent cradle Nov 17, 2020, 1:54 AM

#

Hey guys, I have a question with linked lists. Can someone help me in #help-pancakes?

fresh arch Nov 17, 2020, 2:16 AM

#

anyone have a good video walkthrough in python of kahns algorithm, or anything else? I'm trying to work on a problem to return the earliest completion times of each task (node). currently reviewing: https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/ but wanted to see other resources.

cobalt sedge Nov 17, 2020, 2:23 AM

#

Can anyone help me with this?

All I can think of is a more than O(n^2) method...

My idea is to put v in a max heap, and for any time that Bob does not have enough water to proceed, extract max until he has enough water to proceed but it seems that it takes O(n^2logn) time to do it

📎 Screenshot_2020-11-17_at_10.21.16.png

#

And the most thing that disappointed me is that i only got 3 more days to do it and 4 more questions need to be solved. I've tried to use chegg but it seems to have lots of fake answer... fml

sweet cipher Nov 17, 2020, 1:27 PM

#

Why default dict takes a callable , it's very easy Directly assign a default value?

mint jewel Nov 17, 2020, 1:28 PM

#

consider having a defaultdict of lists

#

a = []
k = defaultdict(a)
k[3].append(4)
print(a)

#

a would be [4] in this case

#

which is very often not what you want

sweet cipher Nov 17, 2020, 1:44 PM

#

May be for instantiation of lists or any data type for functions as well

oblique panther Nov 17, 2020, 3:50 PM

#

@mint jewel I don't think that would work because it would be calling __call__ on the list instance, yes?

#

it would have to be defaultdict(list) to get a new list each time, or defaultdict(lambda: a) to get a reference to a every time

mint jewel Nov 17, 2020, 3:58 PM

#

as I understood his question, he was asking why does defaultdict need a function, so this was an example if it were to just take a value

stable pecan Nov 17, 2020, 4:06 PM

#

also you can just use k.setdefault for that behavior

sweet forge Nov 18, 2020, 2:09 AM

#

Hello?

oblique panther Nov 18, 2020, 2:21 AM

#

@sweet forge hi

sweet forge Nov 18, 2020, 2:22 AM

#

thanks for responding

#

I was told to come here by member

#

I am currently live on the help-copper forum

oblique panther Nov 18, 2020, 2:22 AM

#

Were you going to ask a question? You can always just ask and people who are here can take a stab at it.

sweet forge Nov 18, 2020, 2:23 AM

#

its not more of a question more can you explain it potentially?

oblique panther Nov 18, 2020, 2:23 AM

#

I can try. I'm semi-afk

sweet forge Nov 18, 2020, 2:24 AM

#

hi any help is appreciated thanks

#

think it isnt live any more Ill post it here

oblique panther Nov 18, 2020, 2:25 AM

#

If you're sure you're done with that channel, remember to !close it

sweet forge Nov 18, 2020, 2:26 AM

#

the issue is struggling to understand this piecewise linear fit code https://paste.pythondiscord.com/yisowirelu.properties

#

yeah Ill do that now

#

no worries

chrome needle Nov 18, 2020, 4:08 AM

#

hey guys, someone could help me to create this data interpreter?

I have one matrix of 7 columns and 6 lines (7x6)
and each one has a matrix of 1000 x 1000 inside.

the total matrix is 7000 x 6000 (42.000.000 possibilities)

how can i translate the 'local coordinates' to the 'global coordinates' ?

it's not some data science basic question, the root of this is very simple, imagine a huge retangular grid of 7 x 6 with 1000 x 1000 matrix inside each segment

#

when I select the "major element (one of the 42 parent elements)" i want to be able to return 2 lists of 2 objects

[global_x, global_y], [local_x, local_y]

#

📎 unknown.png

chrome needle Nov 18, 2020, 7:20 AM

#

solved 😄

vagrant condor Nov 18, 2020, 2:36 PM

#

hey guys

#

im having a trouble with the .get() function

#

!code

halcyon plankBOT Nov 18, 2020, 2:36 PM

#

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.

vagrant condor Nov 18, 2020, 2:38 PM

#

u = tags[s]
    url1 = u.get(url)

i just want to use the .get() to update my new link that i found.
i know that inside the .get() i must use the previous url so the variable stores
when i print url1 i recive None in my output.

#

really i have been struggeling with this issue for days

vagrant condor Nov 18, 2020, 3:27 PM

#

😫

trim fiber Nov 18, 2020, 3:46 PM

#

@vagrant condor what is u? Is it a dict or what?

burnt hamlet Nov 18, 2020, 4:25 PM

#

I wrote about a custom data binning type I used for implementing some statistical tests if folk are interested https://blog.matthewbarber.io/python/datasci/2020/11/18/bins/

Honno's Blog

Simplify data binning with a custom dict

Personal blog of Matthew Barber.

sweet forge Nov 18, 2020, 6:39 PM

#

Hello was wondering if anyone could help me with this code error just trying to get it to run but it says
IndentationError: unindent does not match any outer indentation level

#

line 18

fiery cosmos Nov 18, 2020, 6:40 PM

#

can you share your code?

sweet forge Nov 18, 2020, 6:40 PM

#

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

fiery cosmos Nov 18, 2020, 6:41 PM

#

I'll peek into it

sweet forge Nov 18, 2020, 6:41 PM

#

sorry line 14

#

thanks

fiery cosmos Nov 18, 2020, 6:41 PM

#

I'll peek into it

sweet forge Nov 18, 2020, 6:42 PM

#

really appreciate it those returns are ment to be outside the loop aswell sorry

fiery cosmos Nov 18, 2020, 6:42 PM

#

it is running fine on my machine 🤔

#

It doesn't produce any output tho

sweet forge Nov 18, 2020, 6:43 PM

#

may thats it how do I get an output is that the print function

#

maybe

fiery cosmos Nov 18, 2020, 6:44 PM

#

are you trying this on a Jupyter Notebook?

#

can you show the screenshot of the error

sweet forge Nov 18, 2020, 6:44 PM

#

nah Repl.it

#

yeah ill do that give me a sec

#

sorry thats it there

📎 unknown.png

fiery cosmos Nov 18, 2020, 6:59 PM

#

remove that 4 space above return

sweet forge Nov 18, 2020, 7:07 PM

#

sayin this now

📎 unknown.png

#

synatxerror

foggy drift Nov 18, 2020, 7:29 PM

#

I would help

#

But I'm a beginner

#

😩

sweet forge Nov 18, 2020, 7:30 PM

#

so am I lol

fiery cosmos Nov 18, 2020, 7:31 PM

#

now give 2 spaces before return

sweet forge Nov 18, 2020, 7:31 PM

#

actually go that sorted

#

sorry

#

saying this

#

📎 unknown.png

fiery cosmos Nov 18, 2020, 7:32 PM

#

yeah you are not indenting line 17

sweet forge Nov 18, 2020, 7:32 PM

#

sorry my coding skills aint the best what does that mean lol

fiery cosmos Nov 18, 2020, 7:33 PM

#

like you need to add spaces for that return statement

#

add 2 spaces on line 17

#

like this

def function():
  ....
  ....
  return ...

#

see how return is inside the function

sweet forge Nov 18, 2020, 7:34 PM

#

aww ok is mine outside I guess then

#

aww ok is mine outside I guess then

fiery cosmos Nov 18, 2020, 7:35 PM

#

yeah

sweet forge Nov 18, 2020, 7:35 PM

#

ill try that and get back to ye

#

having this problem now

📎 unknown.png

rocky shore Nov 18, 2020, 8:10 PM

#

how to a *?

#

a star

#

anyone can help?

crystal birch Nov 18, 2020, 9:58 PM

#

hello people.. I had a need.

#

I want to initialise a list of a givent size

#

if 4 : mylist = (0, 0, 0, 0)

#

if 5 : mylist = (0, 0, 0, 0, 0)

#

someone knows how to do that without an iteratioN ?

#

gotcha

#

a = (0,) * 15

a
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

agile sundial Nov 18, 2020, 10:08 PM

#

that's not a list btw, that's a tuple

crystal birch Nov 18, 2020, 10:18 PM

#

and you are right.. () tuple [] list

lunar jacinth Nov 18, 2020, 11:54 PM

#

class Node(object):

    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None


class BinarySearchTree():

    def __init__(self, root: Node):
        self.root = root

    def insert(self, node: Node):
        current = self.root
        while current.data is not None:
            if node.data < current.data:
                current = current.left
            else:
                current = current.right
        current = node

#

can someone tell me whats wrong with this code please?

#

I'm trying to make a binary search tree

#

i have to use isnert there somewhere?

#

like would it be insert(current.left)?

somber kiln Nov 19, 2020, 1:02 AM

#

I have a ReDoS report from dlint but I suspect it's a false-positive, could anyone confirm?
The regex: ^POLYGON ?$\([0-9 .]+$(, ?$[0-9 .]+$)*\)$
(also #help-falafel)

#

there are two identical groups in there but I don't see how it could be DoS
(is ^POLYGON ?$group(, ?group)*$$)

minor chasm Nov 19, 2020, 6:00 AM

#

i have to use isnert there somewhere?
@lunar jacinth what u mean by insert there somewhere ??

#

like use that method ?

buoyant pine Nov 19, 2020, 8:47 AM

#

hey

twin edge Nov 19, 2020, 11:11 AM

#

What bs tree should I choose for rope data structure?

fiery cosmos Nov 19, 2020, 11:18 AM

#

hi

fleet plume Nov 19, 2020, 9:44 PM

#

class Node(object):

    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None


class BinarySearchTree():

    def __init__(self, root: Node):
        self.root = root

    def insert(self, node: Node):
        current = self.root
        while current.data is not None:
            if node.data < current.data:
                current = current.left
            else:
                current = current.right
        current = node

@lunar jacinth Your while loop condition should be while current is not None: or while current: because we insert at leaf nodes, leaf nodes are denoted by None. Also, you need two node pointers, current and parent_of_current to enable you to insert a new node in correct location. BST = Node or Leaf where Node is Node, Leaf is None

ruby pumice Nov 20, 2020, 10:24 AM

#

hi , please it there any ressource to learn the binary tree I got stuck with it can't understand it very well ?

solid rune Nov 20, 2020, 11:13 AM

#

foggy drift I would help

are u ?

foggy drift Nov 20, 2020, 11:17 AM

#

Yee

raw bridge Nov 20, 2020, 1:58 PM

#

can someone explain how merge sort works? just the process, i didnt understand from geeksforgeeks

agile sundial Nov 20, 2020, 2:01 PM

#

which part?

raw bridge Nov 20, 2020, 2:15 PM

#

oof sorry for late reply, ik that it divides it and then merges, but what does it do after it has reached the part where it cant split anymore

agile sundial Nov 20, 2020, 2:18 PM

#

if you can't split anymore, then your section has one element

#

a list of one element is always sorted

raw bridge Nov 20, 2020, 2:18 PM

#

yeah, then how do we get a sorted list when we merge

#

i mean, when it merges, how does it take care of the order

agile sundial Nov 20, 2020, 2:19 PM

#

i mean

#

try coming up with something that can do that

raw bridge Nov 20, 2020, 2:20 PM

#

does it compares the other parts which have been splitted and are at the point of having just one element ?

#

and then keeps the order based on the comparison

#

smaller number first

agile sundial Nov 20, 2020, 2:20 PM

#

pretty much

raw bridge Nov 20, 2020, 2:21 PM

#

ah i see, i thought this was done without comparing

#

thanks

fiery cosmos Nov 20, 2020, 4:30 PM

#

the order is taken care when you merge
merge takes 2 sorted lists and merges them

night socket Nov 20, 2020, 4:41 PM

#

📎 unknown.png

#

>>> def cvi(c, n, x):
...     divisor = 0
...     dividendo = 0
...     for i in range(len(x)):
...         for j in range(len(x[i])):
...             dividendo += c[i] * n[i] * x[i][j]
...             divisor += c[j] * n[j]
...     return dividendo / divisor
... 
>>> a
[1, 2, 3]
>>> b
[2, 3, 4]
>>> x
[[1, 2, 3], [2, 3, 4]]
>>> cvi(a,b,x)
1.65
>>>

#

is this alg right for the above formula?

#

i have the understandig that the formula would be like this code i sent

#

my friend says is something like {

n = 3
c = 5

CVI = ( x11+x21+x31 + x12+x22+x32 + x13+x23+x33 + x14+x24+x34 + x15+x25+x35) / (n1+n2+n3+n4+n5)

#

now we are in doubt

#

can someone light our issue?

fiery cosmos Nov 20, 2020, 4:51 PM

#

@night socket why are c, n lists?

night socket Nov 20, 2020, 4:53 PM

#

i suposed theyre lists

#

because the formula uses a sum

#

of elements

#

dont it?

fiery cosmos Nov 20, 2020, 4:53 PM

#

no according to the formula c,n are constants

night socket Nov 20, 2020, 4:53 PM

#

i may be wrong

fiery cosmos Nov 20, 2020, 4:54 PM

#

you know when you write a summation in math you normally iterate only indices from start to end

night socket Nov 20, 2020, 4:55 PM

#

from 1 to c

#

so the second is right?

fiery cosmos Nov 20, 2020, 4:56 PM

#

def cvi(c, n, x):
    divisor = 0
    dividendo = 0
    for j in range(c):
      for i in range(n):
          dividendo += x[i][j]
      divisor += n[j]
    return dividendo / divisor

#

yeah the second one is right

#

also note the changes to the code

#

divisor should be not indented to second for loop

#

because you will be adding n[j] i times

night socket Nov 20, 2020, 4:57 PM

#

i see

#

thank you

fiery cosmos Nov 20, 2020, 4:57 PM

#

ping me if you got any more issues

#

or the implementation is wrong

night socket Nov 20, 2020, 4:57 PM

#

ty

#

i will

halcyon rain Nov 20, 2020, 6:10 PM

#

hi

#

i am stuck with my home work problem on algorithm

#

can someone help me

#

📎 Screen_Shot_2020-11-20_at_1.09.57_PM.png

#

i tried googling and youtube.. still

fiery cosmos Nov 20, 2020, 6:15 PM

#

17 is easy

#

you just need to code a function called hash and send 'boneyhun' into it

#

the code would look like this

#

def hash(s):
  n = len(s)
  hashed_result = 0
  for i in range(n):
    hashed_result += (128 ** (n - i - 1)) * ord(s[i])
  return hashed_result

#

and 18 seems like you return 7 for every integer

#

so whatever you hash it gets chained into a list

#

so searching would take O(n)

#

illustration

[7] => [1, 34, 43,4, 3,123, 454,5]

#

@halcyon rain do you understand?

halcyon rain Nov 20, 2020, 6:33 PM

#

i just tried to code that function

#

understood very well

#

thanks a lot

halcyon rain Nov 20, 2020, 8:32 PM

#

📎 Screen_Shot_2020-11-20_at_1.14.13_PM.png

#

22 is key staple

#

23 .. yes

#

20 and 21 i have no idea

#

reply only when anyone is free, no hurries. thanks again

#

also pls check my answers for 22 and 23

tropic oxide Nov 20, 2020, 8:42 PM

#

so for an assignment i got a massive JSON with every game on steam in april 2019

#

and i don't necessarily need to

#

but i'm trying to make every game into an actual object

#

and this is the basic thing i've got

📎 unknown.png

#

but i want the objects to be named after their appId+g ultimately

#

and this is probably not the best place to putthis

#

but i don't understand how to generate a lot of objects

#

or is that just a bad idea

fiery cosmos Nov 20, 2020, 10:14 PM

#

Whats heap sort

#

Could i send my sort code

agile sundial Nov 20, 2020, 10:18 PM

#

sure

#

heap sort involves creating a min/max heap and popping elements off the root

fiery cosmos Nov 20, 2020, 10:43 PM

#

what max heap mainly about

agile sundial Nov 20, 2020, 10:44 PM

#

it's a smart way to store data

fiery cosmos Nov 20, 2020, 10:47 PM

#

no the max word

agile sundial Nov 20, 2020, 10:47 PM

#

the max element is at the root

fiery cosmos Nov 20, 2020, 11:49 PM

#

Aha

hoary scarab Nov 21, 2020, 12:55 AM

#

I'm having a little trouble with wording
I am trying to look up an algorithm for picking an element from an array but some elements are harder to get than other elements
Like in games that has a [Normal, Rare, Super] type of system... What to google?

vernal venture Nov 21, 2020, 1:01 AM

#

hoary scarab I'm having a little trouble with wording I am trying to look up an algorithm for...

What do you mean 'harder to get'? Is this some sort of loot reward ?

hoary scarab Nov 21, 2020, 1:02 AM

#

Just like a percentage of the chances to acquire that item.
For example:

Name      | Rarity
-------------------
Bulbasaur | 1
Ivysaur   | 1
Venesaur  | 0.5
Charizard | 0.25

vernal venture Nov 21, 2020, 1:03 AM

#

https://pynative.com/python-weighted-random-choices-with-probability/

vernal venture Nov 21, 2020, 1:06 AM

#

hoary scarab Just like a percentage of the chances to acquire that item. For example: ``` Nam...

Is that what you are looking for?

hoary scarab Nov 21, 2020, 1:08 AM

#

vernal venture Is that what you are looking for?

Yep! Thank you! 😁

fast walrus Nov 21, 2020, 8:42 AM

#

Has anyone tried interviewespresso.com for algorithms and data structure interview prep? How is the material covered? Good enough for the interview readiness?

fiery cosmos Nov 21, 2020, 8:57 AM

#

can someone help me with this: https://softwareengineering.stackexchange.com/questions/419197/how-do-i-make-items-disappear-based-on-the-size-of-its-members

Software Engineering Stack Exchange

How do I make items disappear based on the size of it's members?

Consider a list of items (take a list of voice channels) where each item has these attributes

System::vc: List of voice channels.
System::on_join(member, before, after): On the event when a member...

sly lotus Nov 21, 2020, 2:51 PM

#

anyone know how to type a search algorithm on students interests then group them based on their interests

raw bridge Nov 21, 2020, 4:37 PM

#

you should make b a copy of a

#

b = a.copy()

#

other wise your code will take effect on both the lists

kindred ermine Nov 22, 2020, 3:11 AM

#

How can i solve this probelm?

📎 17.png

kindred imp Nov 22, 2020, 5:45 AM

#

i'm trying to traverse a data structure

#

wondering if there's a neater way of doing this

#

i can't access the help channels for some reason

agile sundial Nov 22, 2020, 5:45 AM

#

you have a cooldown, which means you have one open already

kindred imp Nov 22, 2020, 5:46 AM

#

def traverse_tree(root_node,dict_pairs):
    if root_node not in dict_pairs.keys():
        return f"{root_node}"
    elif len(dict_pairs[root_node]) == 1:
        return f"{root_node}({traverse_tree(dict_pairs[root_node][0],dict_pairs)})"
    elif len(dict_pairs[root_node]) == 2:
        if dict_pairs[root_node][0] < dict_pairs[root_node][1]:
            return f"{root_node}({traverse_tree(dict_pairs[root_node][0],dict_pairs)})({traverse_tree(dict_pairs[root_node][1],dict_pairs)})"
        else: 
            return f"{root_node}({traverse_tree(dict_pairs[root_node][1],dict_pairs)})({traverse_tree(dict_pairs[root_node][0],dict_pairs)})"```

kindred imp Nov 22, 2020, 5:46 AM

#

agile sundial you have a cooldown, which means you have one open already

I havent used the channel for multiple days

#

there

#

s a problem

agile sundial Nov 22, 2020, 5:46 AM

#

hm, let me ask about it

#

although, this channel is a pretty good place to ask

kindred imp Nov 22, 2020, 5:47 AM

#

I am trying to build an s-expression to represent a tree

#

turn this (B,D) (D,E) (A,B) (C,F) (E,G) (A,C)
into
(A(B(D(E(G))))(C(F)))

#

so my cleaned nodes then returns this ```return f"({traverse_tree(list_root_nodes[0],dict_pairs)})"

#

starts with the very top node and builds out the expression

#

it works, but i was just wondering if there's nicer way

fiery cosmos Nov 22, 2020, 5:49 AM

#

The tuple represents the connections?

kindred imp Nov 22, 2020, 5:50 AM

#

this is the complete code i have written

fiery cosmos Nov 22, 2020, 5:51 AM

#

no I mean (B, D) does it mean B is connected to D?

#

and A is always the root?

kindred imp Nov 22, 2020, 5:51 AM

#

yes

#

i have a code lenth limit

#

sorry, let me remove some chsrs

halcyon plankBOT Nov 22, 2020, 5:52 AM

#

Hey @kindred imp!

Uh-oh! It looks like your message got zapped by our spam filter. We currently don't allow .txt attachments, so here are some tips to help you travel safely:

• If you attempted to send a message longer than 2000 characters, try shortening your message to fit within the character limit or use a pasting service (see below)

• If you tried to show someone your code, you can use codeblocks
(run !code-blocks in #bot-commands for more information) or use a pasting service like:

https://paste.pythondiscord.com

#

Hey @kindred imp!

Uh-oh! It looks like your message got zapped by our spam filter. We currently don't allow .txt attachments, so here are some tips to help you travel safely:

• If you attempted to send a message longer than 2000 characters, try shortening your message to fit within the character limit or use a pasting service (see below)

• If you tried to show someone your code, you can use codeblocks
(run !code-blocks in #bot-commands for more information) or use a pasting service like:

https://paste.pythondiscord.com

kindred imp Nov 22, 2020, 5:54 AM

#

def sExpression(nodes):
    # Write your code here
    list_root_nodes, list_parent_nodes, list_child_nodes = [], [], []
    dict_pairs, dict_parent_nodes, dict_child_nodes = {}, {}, {}
    max_children = 2
    max_child_nodes = 1
    
    # error codes
    error_codes = {"E1": "More than 2 children",
        "E2": "Duplicate Edges",
        "E3": "Cycle present (node is direct descendant of more than one node)",
        "E4": "Multiple roots",
        "E5": "Any other error"}
        
    # create a list of unique nodes
    unique_nodes = [(node[1], node[-2]) for node in pd.unique(nodes.split())]
  
    # Populate the node dictionaries
    for n, node in enumerate(unique_nodes):
        list_parent_nodes.append(node[0])
        list_child_nodes.append(node[1])
        
        # count parent nodes
        if node[0] not in dict_parent_nodes:
            dict_parent_nodes[node[0]] = 1
        else:
            dict_parent_nodes[node[0]] += 1
            
        # count child nodes
        if node[1] not in dict_child_nodes:
            dict_child_nodes[node[1]] = 1 
        else:
            dict_child_nodes[node[1]] += 1
        
        # create the pairs dictionary
        if node[0] in dict_pairs.keys():
            dict_pairs[node[0]].append(node[1]) # append the child node
        else:
            dict_pairs[node[0]] = [node[1]] # parent = chiild```

#

    # build a list of root nodes
    list_root_nodes = [node[0] for node in pd.unique(list_parent_nodes) if node not in list_child_nodes]
    
    # store the length as I check this more than once
    len_root_nodes = len(list_root_nodes)
    
    #check for errors
    if any([True for k, val in dict_parent_nodes.items() if val > max_children]):
        return "E1" # error_codes["E1"]
    if len(nodes.split()) > len(unique_nodes):
        return "E2" # error_codes["E2"]
    if any([True for k, val in dict_child_nodes.items() if val > max_child_nodes]) or len_root_nodes == 0:
        return "E3" # error_codes.keys["E3"]
    if len_root_nodes > 1:
        return "E4" # error_codes["E4"]
    
    # recurse through the tree and return the lexicographically smallest way oxpressing the tree
    return f"({traverse_tree(list_root_nodes[0],dict_pairs)})"```

#

thats the full function

#

which calls traverse_tree

fiery cosmos Nov 22, 2020, 5:54 AM

#

how is the input taken

kindred imp Nov 22, 2020, 5:54 AM

#

(B,D) (D,E) (A,B) (C,F) (E,G) (A,C)

#

thats theinput

fiery cosmos Nov 22, 2020, 5:55 AM

#

okay tuples with spaces

kindred imp Nov 22, 2020, 5:55 AM

#

this is th eoutput
(A(B(D(E(G))))(C(F)))

#

the whole thing works, just wondering i can make the traverse_tree clener

fiery cosmos Nov 22, 2020, 6:01 AM

#

hmm I made the code 16 lines tell me if it is understandable

from collections import defaultdict

edges = input().split()
tree = defaultdict(lambda : [])

for edge in edges:
    tree[edge[1]].append(edge[3])

def dfs(root):
    rep = "(" + root
    for child in tree[root]:
        rep += dfs(child)
    rep += ")"
    return rep

print(dfs("A"))

#

@kindred imp is this understandable?

#

I didnt write comments to make it more clear

#

you need to know 2 things

How to traverse the tree - Here dfs should be used
How to store the tree efficiently - This is done by popular adjacency list
both are easy to learn

kindred imp Nov 22, 2020, 6:16 AM

#

Thx

kindred imp Nov 22, 2020, 6:38 AM

#

@fiery cosmos Taj KS that’s really helpful

craggy ermine Nov 22, 2020, 7:31 AM

#

Hey, I have more of a math problem than a python one, but I'm trying to figure out if my issue is worth trying to solve in numpy rather than pure python:

I have an object that gives me values based on input. It's effectively a kind of transformation where if I give it (10, 12, 1, 3), it might give me (1, 4, 0.3, 0.003). The real meaning of these numbers is a bit complex (involving chemistry), but the issue is that when one number gets very close to zero (and they can not be negative), the solver starts to freak out and give errors because part of the calculations involve logarithms of the input. I need to be able to either be able to handle logarithms (some way of representing infinity or zero) or deal with exploding numbers. I know numpy can handle -inf, but the solver I'm using is SciPy's LM-BFGS, and I don't know how it will handle this.

My question is: Will numpy -inf terms be handle-able in scipy solvers, and does anyone have any suggestions for me to try for alternative methods of handling complex iterative solutions?

#

My field is membrane chemical engineering, so I'm solving concentration profiles of multicomponent mixtures

tulip plinth Nov 22, 2020, 8:15 AM

#

Hey would u guys say learning data structures and algorithms is important for being a data scientist

craggy ermine Nov 22, 2020, 8:43 AM

#

yes...

#

@tulip plinth

tulip plinth Nov 22, 2020, 8:45 AM

#

Um should I go in depth or just understanding the basics is enough ??

#

Like I know how to create a linked list and how it works

#

Should I learn more about it ?

craggy ermine Nov 22, 2020, 9:00 AM

#

It really just depends on what you're doing

tulip plinth Nov 22, 2020, 9:14 AM

#

Well tbh when I’ve been doing project related to ML or DL

#

I haven’t used data structures that much

#

ppl are like even thou u don’t use it just learn the basics of it

#

Wat do u think ??

fiery cosmos Nov 22, 2020, 9:19 AM

#

you will learn those in university, but a start now won't hurt

tulip plinth Nov 22, 2020, 9:49 AM

#

well I’m in uni but not a cs student that’s why

fiery cosmos Nov 22, 2020, 10:23 AM

#

then you need to understand the basics

#

it may or may not come along in your ML or AI part

unique minnow Nov 22, 2020, 10:50 AM

#

any good resources for DSA for a beginner ?

fiery cosmos Nov 22, 2020, 11:57 AM

#

Im using import socket to create a sever on python , I got the code from a youtube video and im trying to run it on my cmd. What I dont understand is I use a certain port number and I got the error sock.bind(('0.0.0.0', 10000))OSError: [WinError 10048] Only one usage of each socket address (protocol/network address/port) is normally permitted . Also when I connect to a sever and I try to do telnet , I seem to be stuck in a infinite loop. Then I close the cmd , does this leave the server unclosed or something ? Could someone try explain to me what im doing wrong

pseudo fog Nov 22, 2020, 2:00 PM

#

fiery cosmos Im using `import socket` to create a sever on python , I got the code from a you...

Yes the socket remains open for some time even after the process using the socket is over (it's a feature called time wait)

#

It will be free after some time, but you can search for how to reduce the wait time

fiery cosmos Nov 22, 2020, 2:04 PM

#

@pseudo fog how do stop or reduce the wait time ?

pseudo fog Nov 22, 2020, 2:16 PM

#

https://stackoverflow.com/questions/8688949/how-to-close-tcp-and-udp-ports-via-windows-command-line or https://stackoverflow.com/questions/337115/setting-time-wait-tcp

Stack Overflow

How to close TCP and UDP ports via windows command line

Does somebody knows how to close a TCP or UDP socket for a single connection via windows command line?

Googling about this, I saw some people asking the same thing. But the answers looked like a m...

Stack Overflow

Setting TIME_WAIT TCP

We're trying to tune an application that accepts messages via TCP and also uses TCP for some of its internal messaging. While load testing, we noticed that response time degrades significantly (an...

fiery cosmos Nov 22, 2020, 2:28 PM

#

@pseudo fog I tried ,but got this error . What am I doing wrong ?

📎 unknown.png

pseudo fog Nov 22, 2020, 2:30 PM

#

fiery cosmos <@!358287253623013377> I tried ,but got this error . What am I doing wrong ?

You have to write PID of the process which is using the port instead of [PID of the port 8080 got from previous command]

#

like if PID is 13201 then you have to write taskkill /f /im 13201

fiery cosmos Nov 22, 2020, 2:32 PM

#

taskkill /f /im 8080[PID of the port 8080 got from previous command]

#

like this ?

frigid cypress Nov 22, 2020, 2:32 PM

#

Hi guys. I was wondering if anyone could give me a pointer on how to keep track of objects. I assign the objects like

for index, row in sdf.iterrows():
    tmp = station(row[3],row[6],row[7],row[4])
                  #ID , #Long, #Lat, #Numer
    listOfStations.append(tmp)

When adding values to the objects later on, I run this stupid thing... ^^

# sId and eId passed from func
for s in listOfStations:
        if s.getId() == sId:
            s.updateChange(-1)
            sId=False
        if s.getId() == eId:
            s.updateChange(1)
            eId=False
        if not sId and not eId:
            break

So I guess that alot of stuff can be done to optimalize the code, but my question is if i can do a lookup on object id? I guess i could do a dict like {'Id':Obj1,'Id2':Ob2.... }
But how do do this most effective?

fiery cosmos Nov 22, 2020, 2:33 PM

#

@pseudo fog If I want to kill 8080 , what should I enter ?

pseudo fog Nov 22, 2020, 2:33 PM

#

fiery cosmos <@!358287253623013377> If I want to kill 8080 , what should I enter ?

nope, you have to kill the process which is using that port (i.e. 8080)

fiery cosmos Nov 22, 2020, 2:34 PM

#

pseudo fog nope, you have to kill the process which is using that port (i.e. 8080)

What do I type to do that ?

pseudo fog Nov 22, 2020, 2:35 PM

#

first use netstat -ano | findstr :8080 command

fiery cosmos Nov 22, 2020, 2:35 PM

#

okay done and nothing returned

pseudo fog Nov 22, 2020, 2:36 PM

#

Then your port 8080 is already free

#

📎 unknown.png

fiery cosmos Nov 22, 2020, 2:37 PM

#

okay bare with me , I run my program and im still getting the same error

#

Will I show you my program ?

pseudo fog Nov 22, 2020, 2:38 PM

#

Yes please

fiery cosmos Nov 22, 2020, 2:49 PM

#

@pseudo fog any idea ?

pseudo fog Nov 22, 2020, 2:56 PM

#

According to the error you previously stated, it's port not free only

#

try after changing port in the code

fiery cosmos Nov 22, 2020, 2:58 PM

#

@pseudo fog Sorry what do I change ?

lean glade Nov 22, 2020, 2:59 PM

#

I made this quicksort function (just learning, so it's not the best at all), and I made this swaps variable for to know how many swaps have been done, but Im pretty sure I did it wrong, because it's giving me insane numbers. def quickSort(k,swaps=0): n=len(k) if n==1 or n==0: return k,swaps pivot=k[-1] i=0 for j in range(n-1): if k[j]<pivot: k[j],k[i]=k[i],k[j] i+=1 swaps+=1 k[i],k[-1]=k[-1],k[i] swaps+=1 k[:i],swap=quickSort(k[:i],swaps=swaps) swaps+=swap k[i:],swap=quickSort(k[i:],swaps=swaps) swaps+=swap return (k,swaps)

#

For a list of 100 shuffled numbers, it said it did 16412864521840461437626774873808948705 swaps, and I'm pretty sure that's wrong

agile sundial Nov 22, 2020, 3:00 PM

#

yeah that's wrong

lean glade Nov 22, 2020, 3:18 PM

#

How can I fix it?

#

Oh nevermind, I think that taking out the swaps=swaps keyword when I did the recursion fixed it

pliant crane Nov 23, 2020, 4:19 AM

#

<@&267629731250176001> i am supressed in every voice channel is this normal

#

or am i being heavily trolled by someone

torpid crown Nov 23, 2020, 4:20 AM

#

We have created a voice verification system to increase quality of messages sent and too keep trolls out of voice. See #voice-verification for more info.

pure terrace Nov 23, 2020, 11:46 AM

#

Hello I want to prevent users from entering level command before nick command. I'm using the following code to do that: https://mystb.in/WorseAugHack.python, but apparently if conditional doesn't work as expected because else statement doesn't get triggered when I type level command before nick. Ty in advance, any help is very welcome.

fiery cosmos Nov 23, 2020, 12:02 PM

#

lean glade I made this quicksort function (just learning, so it's not the best at all), and...

I am 1 day late for this, but I really like this

#

So ill answer it in a different way

#

def quick_sort(arr):
  if arr == []:
    return []
  mid = arr.pop()
  big, small = [], []
  for i in arr:
    if i > mid: big.append(i)
    else: small.append(i)
  return quick_sort(small) + [mid] + quick_sort(big)

lean glade Nov 23, 2020, 12:06 PM

#

Oh that's waay nicer and more understandable than what I was doing

fiery cosmos Nov 23, 2020, 12:06 PM

#

thanks man

lean glade Nov 23, 2020, 12:06 PM

#

Thanks!

fiery cosmos Nov 23, 2020, 12:07 PM

#

side note: find the worst case complexity

#

I actually learned it form Derrick Sherrill

fiery cosmos Nov 23, 2020, 12:07 PM

#

fiery cosmos side note: find the worst case complexity

hmmmmmmm

lean glade Nov 23, 2020, 12:07 PM

#

Who is he?

lean glade Nov 23, 2020, 12:07 PM

#

fiery cosmos side note: find the worst case complexity

Yeah I know this could be optimized, but its a good startup

lean glade Nov 23, 2020, 12:17 PM

#

lean glade Who is he?

I checked in google and now I know :)

fiery cosmos Nov 23, 2020, 1:02 PM

#

def heapify(arr, n, i):
    largest = i  # largest value
    l = 2 * i + 1  # left
    r = 2 * i + 2  # right
    # if left child exists
    if l < n and arr[i] < arr[l]:
        largest = l
    # if right child exits
    if r < n and arr[largest] < arr[r]:
        largest = r
    # root
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # swap
        # root.
        heapify(arr, n, largest)


# sort
def heapSort(arr):
    n = len(arr)
    # maxheap
    for i in range(n, -1, -1):
        heapify(arr, n, i)
    # element extraction
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # swap
        heapify(arr, i, 0)


# main
n = int(input())

arr = input().split()  # [2, 5, 3, 8, 6, 5, 4, 7]

heapSort(arr)
map(float , arr)
for i in range(n):
    print(arr[i])

#

here is my code

sweet cipher Nov 23, 2020, 1:02 PM

#

Why isn't bool an iterable it would be very helpful in cases with any(...) syntax? Will python core-devs make booleans an iterable objects, just out of curoisty asking

fiery cosmos Nov 23, 2020, 1:03 PM

#

i want to get mean of evrey iteration of the array

fiery cosmos Nov 23, 2020, 1:04 PM

#

sweet cipher Why isn't bool an iterable it would be very helpful in cases with any(...) synta...

might ask in python general

sweet cipher Nov 23, 2020, 1:04 PM

#

They didn't answer so here i tried

#

Nope

fiery cosmos Nov 23, 2020, 1:05 PM

#

sweet cipher Why isn't bool an iterable it would be very helpful in cases with any(...) synta...

i don't understand what ur trying to say.

sweet cipher Nov 23, 2020, 1:05 PM

#

Why boolean objects are not iterable I mean

fiery cosmos Nov 23, 2020, 1:06 PM

#

why shoud be

sweet cipher Nov 23, 2020, 1:06 PM

#

For optimization purposes

fiery cosmos Nov 23, 2020, 1:06 PM

#

so ur like

#

for i in range(True):

#

that just doesn't make sense

#

idk

#

then its abtually a list

#

not boolean

#

and list are iterable

#

ye, thats what he was asking for

#

sort of

#

To make Booleans iterable

#

hmm

snow swift Nov 23, 2020, 2:20 PM

#

uh how would iterating over a bool work

#

how do you iterate over a single value

#

@sweet cipher

flat sorrel Nov 23, 2020, 2:21 PM

#

It appears that they have gotten their question answered if you look at their* chat history

agile sundial Nov 23, 2020, 2:52 PM

#

it still makes no sense

lean forge Nov 23, 2020, 4:04 PM

#

hi

hot bobcat Nov 23, 2020, 4:46 PM

#

fiery cosmos ``` def quick_sort(arr): if arr == []: return [] mid = arr.pop() big, ...

this is actually not good as a normal quicksort since you are not using inplace sorting

#

you are creating new arrays each iteration making it more complex in space

hot bobcat Nov 23, 2020, 4:48 PM

#

sweet cipher Why isn't bool an iterable it would be very helpful in cases with any(...) synta...

why should any variable be iterable, this is like stating that an integer should be an iterable, it does not make sense at all

eager hamlet Nov 23, 2020, 7:02 PM

#

http://www.usaco.org/index.php?page=viewproblem2&cpid=739
so i'm trying to do this problem but i can't even understand it
if we just have pos 2 and 4, these are the genomes
spotty: AC, AT, GC
plain: CC, GT, GT
how in frick does the logic in the problem hold
(ping 2 reply thx)

fiery cosmos Nov 23, 2020, 9:03 PM

#

how can I make a key function that I can pass into the sort function? i have a list of tuples that i wanna sort and the key is the sum of the elements in the tuple

#

# tried smth like this but i m stuck
def suma(tuplu):
    return tuplu[0] + tuplu[1] + tuplu[2]

sortare = suma()

tupluri = sorted(tupluri, key=sortare)

topaz pulsar Nov 23, 2020, 9:06 PM

#

@fiery cosmos you can just use key=sum, but for your own custom functions you would pass it as key=suma in your case

fiery cosmos Nov 23, 2020, 9:06 PM

#

it wants me to put a parameter

topaz pulsar Nov 23, 2020, 9:07 PM

#

it just passes each item to the key function and sorts by the value that it returns

fiery cosmos Nov 23, 2020, 9:07 PM

#

should i delete tuplu

#

from the function parameter?

topaz pulsar Nov 23, 2020, 9:07 PM

#

don't try to call it wiht (), just pass the function name like in my example

fiery cosmos Nov 23, 2020, 9:07 PM

#

without sortare?

#

huh, it worked

#

what s the philosophy behind this

topaz pulsar Nov 23, 2020, 9:08 PM

#

you don't need it, no, you can use it but sum would also work

#

like I said, if you pass a key argument, you can think of it instead of comparing items as if item1 < item2: ... it does if key(item1) < key(item2): ...

fiery cosmos Nov 23, 2020, 9:09 PM

#

so the parameter will be automatically the element from the list

topaz pulsar Nov 23, 2020, 9:09 PM

#

yep

fiery cosmos Nov 23, 2020, 9:10 PM

#

I got confused because I saw examples that passed a function through a variable

#

but that function was a lot of nested functions actually

#

that was doin' a lotta things once

#

def cheie_cmmdc(t):
    def cmmdc(element):
        while t != element:
            if t > element:
                t -= element
            else:
                element -= t
    
        return t

    def cmmdc_aux(element):
        return cmmdc(t, element)

L = [20,18,46,100,90,35,8,11]
t = 4
sortare = cheie_cmmdc(t)
L = sorted(L, key=sortare)
print(L)
``` smth like that

topaz pulsar Nov 23, 2020, 9:11 PM

#

afaik, key can be any callable that requires one positional argument (and optionally uses default arguments)

#

that works because cheie_cmmdc(t) returns another function so sortare is still callable

#

actually it doesn't in that case, there is on return inside the outer function so i'm not sure how that works

fiery cosmos Nov 23, 2020, 9:16 PM

#

hmmm

#

thank you

lean glade Nov 23, 2020, 9:51 PM

#

Well, it seems that my attempt at implementing an iterative quick sort was a complete and utter failure.

#

100x slower than the recursive one I implemented

#

lol

#

Might as well die

eager hamlet Nov 24, 2020, 1:29 AM

#

http://www.usaco.org/index.php?page=viewproblem2&cpid=692
ok uh

#

with open('cowcode.in') as read:
    theString, charNum = [i for i in read.readline().split()]
    charNum = int(charNum)


def findChar(position: int, findIn: str) -> str:
    if position <= len(findIn):
        return findIn[position - 1]

    currTwoPower = 0  # this will be how many times we'll have to apply it (given that the original string's there alr)
    while True:
        currTwoPower += 1
        if position <= 2 ** currTwoPower * len(findIn):
            break
    lowerBound = len(findIn) * 2 ** (currTwoPower - 1)

    if position == lowerBound + 1:
        return findChar(lowerBound, findIn)  # bc of the rotation
    return findChar(position - lowerBound - 1, findIn)


with open('cowcode.out', 'w') as written:
    answer = findChar(charNum, theString)
    print(answer)
    written.write(str(answer) + '\n')

#

this works

#

but i have no idea why (i wrote it like 4 months ago)

#

programmer pain

#

does anyone know why? (ping 2 reply plz)

lunar jacinth Nov 24, 2020, 1:56 AM

#

hey guys, im trying to make an undirected graph(ADT) using linkedlists

#

and i was just wondering if i could get some help with my add_vertex function?

#



class Node:

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


class LinkedList:

    def __init__(self):
        self.head = None

    def append(self,data):
        if not self.head:
            self.head = Node(data)
            return None
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = Node(data)


class Vertex:

    def __init__(self, id):
        self.id = id
        self.neighbors = LinkedList()

    def add_neighbor(self, neighbor, weight=0):
        self.neighbors.append({neighbor: weight})

    def get_connections(self):
        return self.neighbors.keys()

    def get_id(self):
        return self.id

    def __str__(self):
        lst = []
        for x in self.nieghbors:
            lst.append(x.id)
        return "vertex ID: " + str(self.id) + "is neighbor of " + str(lst)


class Graph:

    def __init__(self):
        self.vertList = {}
        self.vertices = 0

    def add_vertex(self, val):
        self.vertices += 1
        newV = Vertex(val)
        self.vertList[key] = newV
        return newV

#

if someone does help , can you just @ me?

atomic mulch Nov 24, 2020, 2:46 AM

#

why does everyone shit on java

dense ibex Nov 24, 2020, 2:47 AM

#

i feel that there are more appealing languages

stable pecan Nov 24, 2020, 2:55 AM

#

either way it's offtopic here

dense ibex Nov 24, 2020, 2:56 AM

#

true

lunar jacinth Nov 24, 2020, 4:21 AM

#

i still need help on adding edges haha

#

if anyone could

lethal swallow Nov 24, 2020, 9:16 AM

#

I have implement some sorting methods in python, namely selection sort, quicksort, insertion sort, bubblesort and mergesort, and when I time them, quicksort turns out to be the slowest

#

but, it is supposed to be the fastest right?

#

https://paste.pythondiscord.com/vujokaqaxi.py

#

this is my code

#

What have I done wrong?

lethal swallow Nov 24, 2020, 9:42 AM

#

Please ping me if you find the solution

hoary finch Nov 24, 2020, 10:16 AM

#

i haven't looked at your code yet but maybe try a larger sample size of numbers

fiery cosmos Nov 24, 2020, 10:30 AM

#

@lethal swallow

for i in left + right:
    if i < chosen:
        sorted_list.insert(0, i)
        chosen_idx += 1
    else:
        sorted_list.append(i)

#

the sorted_list.insert(0, i) takes O(n) worst time

lethal swallow Nov 24, 2020, 10:31 AM

#

oh... so I just insert it at a random position before (or after) the chosen number?

fiery cosmos Nov 24, 2020, 10:31 AM

#

wait hold up I may be wrong

#

ah yes so you are iterating twice

#

the for loop takes O(n) time and the insert takes O(n) again

#

so worst case you do O(n^2) work

lethal swallow Nov 24, 2020, 10:35 AM

#

oh... so how do I fix that?

#

Can I fix that?

fiery cosmos Nov 24, 2020, 10:35 AM

#

https://www.cc.gatech.edu/classes/cs3158_98_fall/quicksort.html
see this for pseduocode

#

yes you can

#

idk how to implement it rn but the partition should take O(n) time

#

then it will result in O(n log n)

lethal swallow Nov 24, 2020, 10:37 AM

#

wait I didn't see the solution yet, because I want to try to fix it my self. So will it be better if I write sorted_list = [i] + sorted_list?

#

it still takes the most time

#

here are the results:

Time taken for the inbuilt sorted() method (1000 rounds): 0.00034409999999999996
Time taken for the selection_sort() method (1000 rounds): 0.006560099999999999
Time taken for the   quicksort()    method (1000 rounds): 0.021209599999999995
Time taken for the  insertionsort() method (1000 rounds): 0.0047648
Time taken for the  bubblesort()    method (1000 rounds): 0.0010583999999999871
Time taken for the   mergesort()    method (1000 rounds): 0.012199299999999996
                     Results:                     
inbuilt_sort()  : [0, 4, 6, 6, 34, 39, 43, 49, 57, 59, 63, 78, 84]
selection_sort(): [0, 4, 6, 6, 34, 39, 43, 49, 57, 59, 63, 78, 84]
quicksort()     : [0, 4, 6, 6, 34, 39, 43, 49, 57, 59, 63, 78, 84]
insertionsort() : [0, 4, 6, 6, 34, 39, 43, 49, 57, 59, 63, 78, 84]
bubblesort()    : [0, 4, 6, 6, 34, 39, 43, 49, 57, 59, 63, 78, 84]
mergesort()     : [0, 4, 6, 6, 34, 39, 43, 49, 57, 59, 63, 78, 84]

#

should I try a larger list like how poke suggested?

#

(sorry for the ping)

fiery cosmos Nov 24, 2020, 10:39 AM

#

okay what you can do is have two separate arrays for left and right

#

fill those in one loop

#

and then do your usual algo

lethal swallow Nov 24, 2020, 10:40 AM

#

hmmmmm ok let me try that

hoary finch Nov 24, 2020, 10:40 AM

#

it's fine, but yeah i think you should try a larger list if you haven't already because quicksort does a lot more computation per iteration than something like bubblesort, so bubblesort is faster for smaller lists

fiery cosmos Nov 24, 2020, 10:41 AM

#

moving less than pivot to left and greater to right

#

and then calling quick sort on left and right

#

shall I code a stub if you want?

#

(if you are unclear with what I said)

lethal swallow Nov 24, 2020, 10:43 AM

#

https://paste.pythondiscord.com/amafeyedas.properties this is the result now (idk why the syntax highlighting is wrong) but it still takes a lot of time

lethal swallow Nov 24, 2020, 10:45 AM

#

hoary finch it's fine, but yeah i think you should try a larger list if you haven't already ...

In a list of 200 numbers, bubble sort is the fastest and quicksort is the second fastest:

Time taken for the inbuilt sorted() method (1000 rounds): 0.006825499999999998
Time taken for the selection_sort() method (1000 rounds): 0.5805222
Time taken for the   quicksort()    method (1000 rounds): 0.3959051
Time taken for the  insertionsort() method (1000 rounds): 1.3347014000000001
Time taken for the  bubblesort()    method (1000 rounds): 0.013528400000000218
Time taken for the   mergesort()    method (1000 rounds): 0.22213100000000008

hoary finch Nov 24, 2020, 10:47 AM

#

do 100 cycles of 10000 if it doesn't take too long

#

see if there's a difference

lethal swallow Nov 24, 2020, 10:47 AM

#

2,000 numbers took 7 s

fiery cosmos Nov 24, 2020, 10:48 AM

#

def quicksort(lst=target):
    if len(lst) in [0, 1]:
        return lst
    list_to_sort = copy(lst)
    rand = randint(0, len(list_to_sort) - 1)
    chosen = list_to_sort(rand)
    # this is the change I was mentioning
    #-----------------------------------------------
    left = right = []
    for i in range(len(list_to_sort)):
        if i != rand:
            if list_to_sort[i] < chosen:
                left.append(list_to_sort[i])
            else:
                right.append(list_to_sort[i])
    #-------------------------------------------------
    return quicksort(left) + [chosen] + quicksort(right)

lethal swallow Nov 24, 2020, 10:48 AM

#

100 cycles of 10,000 will take 3500 seconds

hoary finch Nov 24, 2020, 10:48 AM

#

how fast are they for 2000

lethal swallow Nov 24, 2020, 10:48 AM

#

its still running

#

aah I stopped it

#

😦

fiery cosmos Nov 24, 2020, 10:49 AM

#

this is O(n)

#

your code is still O(n^2)

lethal swallow Nov 24, 2020, 10:50 AM

#

fiery cosmos ```py def quicksort(lst=target): if len(lst) in [0, 1]: return lst ...

Isn't that what I did?

fiery cosmos Nov 24, 2020, 10:50 AM

#

no

lethal swallow Nov 24, 2020, 10:50 AM

#

oh wait

#

one second

flat sorrel Nov 24, 2020, 10:50 AM

#

You are assigning both left and right to the same list instance, that probably causes some problems

fiery cosmos Nov 24, 2020, 10:50 AM

#

you are still doing unnecessary work

#

which will lead to O(n^2) making it slow

lethal swallow Nov 24, 2020, 10:52 AM

#

def quicksort(lst=target):
    if len(lst) in [0, 1]:
        return lst

    list_to_sort = copy(lst)
    rand = randint(0, len(list_to_sort) - 1)
    left, chosen, right = list_to_sort[:rand], list_to_sort[rand], list_to_sort[rand + 1:]

    sort_left = []
    sort_right = []
    for i in left + right:
        if i < chosen:
            sort_left.append(i)
        else:
            sort_right.append(i)

    return quicksort(sort_left) + [chosen] + quicksort(sort_right)
```is this better?

fiery cosmos Nov 24, 2020, 10:53 AM

#

yes

flat sorrel Nov 24, 2020, 10:53 AM

#

Is there a good reason why are you using a random integer to split the list?

lethal swallow Nov 24, 2020, 10:53 AM

#

No

fiery cosmos Nov 24, 2020, 10:54 AM

#

many ways to choose pivot element

lethal swallow Nov 24, 2020, 10:54 AM

#

Where I read it said that you should pick a random pivot point

fiery cosmos Nov 24, 2020, 10:54 AM

#

random is one

lethal swallow Nov 24, 2020, 10:54 AM

#

Wait but the best case is when the pivot point is somewhere in the middle right?

fiery cosmos Nov 24, 2020, 10:55 AM

#

idk no matter what pivot is, you still need to scan the other things beside the pivot

#

the best case is n log n

flat sorrel Nov 24, 2020, 10:57 AM

#

I guess random is good enough

#

I think copying lst is unnecessary

fiery cosmos Nov 24, 2020, 10:58 AM

#

well there are testcases that can break the normal quicksorts

#

yeah quicksort is inplace

#

you can even remove those left and right arrays

#

and do swappings

lethal swallow Nov 24, 2020, 11:00 AM

#

flat sorrel I think copying `lst` is unnecessary

Not much difference

lethal swallow Nov 24, 2020, 11:00 AM

#

fiery cosmos and do swappings

What do you mean?

fiery cosmos Nov 24, 2020, 11:02 AM

#

uhh as I said, idk the implementation but you can checkout other codes in online for optimizations

onyx mist Nov 24, 2020, 12:48 PM

#

Hey guys. I am working with a pandas DataFrame like this and am looking to create a nested dictionary keyed by 'id' with values being dictionaries with keys and values for 'capacity' and 'level' for only the ids where is_customer is True. Anyone know how to do this?

📎 DataFrame.png

lean glade Nov 24, 2020, 1:35 PM

#

Hey @lethal swallow, here you have the same quicksort function you wrote, but I got rid of the unnecessary parts, probably making it faster: ```def quicksort(lst=target):
if len(lst) in [0, 1]:
return lst

rand = randint(0, len(lst) - 1)
left, chosen, right = [], lst.pop(rand), []

for i in lst:
    if i < chosen:
        left.append(i)
    else:
        right.append(i)

return quicksort(left) + [chosen] + quicksort(right)```

#

If you check google you'll find faster quicksorts anyway

raw bridge Nov 24, 2020, 1:38 PM

#

def Quicksort(arr: list):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2-1]
    lhs = [i for i in arr if i < pivot]
    rhs = [i for i in arr if i > pivot]
    eq = [i for i in arr if i == pivot]

    return Quicksort(lhs) + eq + Quicksort(rhs)
``` ![UwU](https://cdn.discordapp.com/emojis/624350494072242206.webp?size=128 "UwU")

lean glade Nov 24, 2020, 1:39 PM

#

^better

raw bridge Nov 24, 2020, 1:39 PM

#

its basically a shorter version of what you did

lean glade Nov 24, 2020, 1:39 PM

#

From what I read list comprehensions are faster

raw bridge Nov 24, 2020, 1:39 PM

#

yeah maybe

#

i like them a lot KoishiDerp

lean glade Nov 24, 2020, 1:40 PM

#

One of the best features of python I think

#

From what I checked, the list comprehension one was faster than the other two in the worst case scenario, and the original one was slower than the other two in the normal scenarios

agile sundial Nov 24, 2020, 1:57 PM

#

the list comprehension version loops over the list 3 times, while the not list comp version only loops over the list one time

raw bridge Nov 24, 2020, 1:58 PM

#

ye true

agile sundial Nov 24, 2020, 1:58 PM

#

per recursion

raw bridge Nov 24, 2020, 1:58 PM

#

so slower i guess

lethal swallow Nov 24, 2020, 2:42 PM

#

raw bridge ```py def Quicksort(arr: list): if len(arr) <= 1: return arr piv...

Hey that's actually much much much faster!

#

wait

#

nevermind its slower

raw bridge Nov 24, 2020, 2:42 PM

#

ye its fast, i learned that method from eivl

lethal swallow Nov 24, 2020, 2:43 PM

#

no wait its faster!

agile sundial Nov 24, 2020, 2:43 PM

#

how is that faster

lethal swallow Nov 24, 2020, 2:43 PM

#

¯_(ツ)_/¯

raw bridge Nov 24, 2020, 2:43 PM

#

idk about fast

#

it just seems easy to me so i use it

agile sundial Nov 24, 2020, 2:44 PM

#

wait you actually use this algo to sort things?

lethal swallow Nov 24, 2020, 2:44 PM

#

Yes

#

its called quicksort

raw bridge Nov 24, 2020, 2:44 PM

#

agile sundial wait you actually use this algo to sort things?

no lol

agile sundial Nov 24, 2020, 2:44 PM

#

... not the algo in general, i mean the one he wrote

raw bridge Nov 24, 2020, 2:44 PM

#

haha

#

why would i use it if theres a built in method

agile sundial Nov 24, 2020, 2:45 PM

#

you said "so i use it"

raw bridge Nov 24, 2020, 2:45 PM

#

eh my bad, didnt mean it that way though

agile sundial Nov 24, 2020, 2:48 PM

#

¯_(ツ)_/¯

lethal swallow Nov 24, 2020, 2:48 PM

#

I think it is faster becase vinam chose the approximate midpoint as the pivot

#

while I am choosing a random number

agile sundial Nov 24, 2020, 2:49 PM

#

well, they should be about the same

toxic grotto Nov 24, 2020, 2:52 PM

#

hlo

#

i am a new one

#

plz some one clearmy dout

#

what are gethut and there uses

agile sundial Nov 24, 2020, 2:54 PM

#

github?

lethal swallow Nov 24, 2020, 2:54 PM

#

@toxic grotto why don't you ask in #tools-and-devops?

toxic grotto Nov 24, 2020, 2:55 PM

#

ok sir

lethal swallow Nov 24, 2020, 2:55 PM

#

I think that is a more appropriate place. Also, it is github, not gethut

#

!e

from time import perf_counter
from random import randint

target = [randint(0, 100) for _ in range(2000)]


def vinam_quicksort(arr: list):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2-1]
    lhs = [i for i in arr if i < pivot]
    rhs = [i for i in arr if i > pivot]
    eq = [i for i in arr if i == pivot]

    return vinam_quicksort(lhs) + eq + vinam_quicksort(rhs)


def chococookies_quicksort(lst=target):
    if len(lst) in [0, 1]:
        return lst

    rand = randint(0, len(lst) - 1)
    left, chosen, right = [], lst.pop(rand), []

    for i in lst:
        if i < chosen:
            left.append(i)
        else:
            right.append(i)

    return chococookies_quicksort(left) + [chosen] + chococookies_quicksort(right)


for func in (vinam_quicksort, chococookies_quicksort):
    strt = perf_counter()
    func(target)
    print(f"Time taken for {func.__name__}: {perf_counter() - strt}")

halcyon plankBOT Nov 24, 2020, 2:55 PM

#

You are not allowed to use that command here. Please use the #bot-commands channel instead.

lethal swallow Nov 24, 2020, 2:55 PM

#

aw man

lethal swallow Nov 24, 2020, 2:55 PM

#

agile sundial how is that faster

#bot-commands message

#

look here

raw bridge Nov 24, 2020, 3:47 PM

#

ye, the main reason seems to be the list comp, it is faster than normal for loops

#

like for 200k length list the difference is already 2 seconds

#

📎 unknown.png

#

📎 unknown.png

median ridge Nov 24, 2020, 6:32 PM

#

@raw bridge just to get a comparison, could you time the standard timsort (sort()) as well?

#

doubt it will be any different to the best quicksort implementation tho, as timsort is only faster on "real" data, not scientific data

agile sundial Nov 24, 2020, 6:41 PM

#

compared to python, sort() should be much much faster

#

it's implemented in C

final lodge Nov 24, 2020, 9:08 PM

#

Hello Earthlings, I am reading a book on algorithms and I would like to practice it in python. The problem is python doesn't have many data structure build in like linked list etc. It's getting tiresome to implement the data structure everytime I need it, is their any module in python which contains all common data structure

agile sundial Nov 24, 2020, 9:10 PM

#

why don't you save the implementations

final lodge Nov 24, 2020, 9:14 PM

#

yeah i could do that, but I don't think I have written an elegant code, it only works as proof of concept for me but I think I would be much better off borrowing a module.

agile sundial Nov 24, 2020, 9:15 PM

#

generally there are, which ones are you looking for?

final lodge Nov 24, 2020, 9:16 PM

#

linked list, double linked list, binary tress. Basically I am reading Ullman Algo book and would like to solve the end of the chapter problem using python

agile sundial Nov 24, 2020, 9:20 PM

#

hm

#

there is llist, and there's also deque

final lodge Nov 24, 2020, 9:29 PM

#

from what I read llist does the job, but it only has single and double linked list functionality, so do I have to download all other data structure separetely. I thought all common data structure would be available at single place?

eager hamlet Nov 25, 2020, 12:44 AM

#

so i have n (n < 1000) lists, each of max length 9
like [2, 20, 22, 47, 7, 32, 23, 8, 48] [36, 0, 39, 42, 18, 26, 27, 31, 25] ...and i have to choose at most 1 element from each list so that the result is as long as possible and is strictly increasing- would this require dp? (ping 2 reply thx)

#

my algo so far does use it

#

it's where dp[i] returns the length of the sequence and the last number in the list

brave oak Nov 25, 2020, 4:28 AM

#

say you have a list of origin and destination nodes and an approximate cost to travel between them

#

is there an algorithm which generates a graph based on that?

fiery cosmos Nov 25, 2020, 4:30 AM

#

you need more info

brave oak Nov 25, 2020, 4:30 AM

#

okay, more like

fiery cosmos Nov 25, 2020, 4:30 AM

#

I can just construct a graph with src and des and add an edge cost

brave oak Nov 25, 2020, 4:31 AM

#

there exists a connected graph which I can't see

#

which represents a transport network

#

so the cost of a path is the time taken to get between two points

brave oak Nov 25, 2020, 4:33 AM

#

brave oak say you have a list of origin and destination nodes and an approximate cost to t...

I want to approximately reconstruct the original graph based on that

#

like I'm not really sure where to start

fiery cosmos Nov 25, 2020, 4:33 AM

#

so based on many graphs that are possible you need to construct one which is as close as possible to the original one

#

but there are exponential many graphs 🤔

brave oak Nov 25, 2020, 4:34 AM

#

fiery cosmos so based on many graphs that are possible you need to construct one which is as ...

a reasonably good guess

#

would be sufficient

#

like

#

okay, for example, if I have two nodes A and B which each have a set of, say, 10 closest nodes, and the intersection of these sets contains 5 nodes

#

it's a good guess that those 5 nodes are "between" A and B on the network

#

similarly, if choose two random nodes from the 10 closest nodes to A and they have no common close nodes, that suggests that they are on opposite sides of A

#

that's kind of the logic

#

but I'm looking for an algorithm that captures this intuition...?

#

because I don't want to piece together the graph manually

fiery cosmos Nov 25, 2020, 4:37 AM

#

I have not heard (until now) any algo that does this

brave oak Nov 25, 2020, 4:37 AM

#

or, another way of looking at the problem

fiery cosmos Nov 25, 2020, 4:37 AM

#

nor have I come across this question 🙂

brave oak Nov 25, 2020, 4:37 AM

#

say I have "pieces" of a graph (basically subgraphs)

#

hm, actually, never mind, that's trivial

brave oak Nov 25, 2020, 4:38 AM

#

fiery cosmos I have not heard (until now) any algo that does this

it's okay, thanks for your help!

#

maybe I'm going about it the wrong way

fiery cosmos Nov 25, 2020, 4:38 AM

#

brave oak say I have "pieces" of a graph (basically subgraphs)

if it were this you can generate 2^n subsets with each pieces and their connection and check?

brave oak Nov 25, 2020, 4:39 AM

#

fiery cosmos if it were this you can generate 2^n subsets with each pieces and their connecti...

yeah, but that's not the problem and I think it would be wrong to transform it in that way

fiery cosmos Nov 25, 2020, 4:39 AM

#

hmm ok

lunar jacinth Nov 25, 2020, 4:48 AM

#

can someone help me with undirected graphs?

#

i have a few methods written but im not sure how to get the end result i want

#

https://paste.pythondiscord.com/uhiredewoh.http

#

this is my code right now

#

📎 a7c93738527dbd389290426ef67eebf7.png

#

im trying to create this somehow...

fiery cosmos Nov 25, 2020, 4:55 AM

#

you need to make a matrix of some large size or give the number of nodes as an argument and build a size x size matrix

#

then when adding an edge between node u and v you make matrix[u][v] = 1 and matrix[v][u] = 1

lunar jacinth Nov 25, 2020, 4:58 AM

#

fiery cosmos then when adding an edge between node u and v you make `matrix[u][v] = 1 and mat...

does this happen in the main function?

#

so everything i have right now is decent? do i need a str function?

fiery cosmos Nov 25, 2020, 5:10 AM

#

im trying to write to a text file, after reading it. Adding 1 to the content and rewriting to it. I get this error

TypeError: must be str, not int

#

what should I do

ionic pasture Nov 25, 2020, 5:19 AM

#

so change N

fiery cosmos Nov 25, 2020, 5:19 AM

#

i did

ionic pasture Nov 25, 2020, 5:19 AM

#

nah wait

fiery cosmos Nov 25, 2020, 5:19 AM

#

and i get this

#

📎 unknown.png

ionic pasture Nov 25, 2020, 5:20 AM

#

n = str(c1.read(1))

#

look

#

what is n equal too

fiery cosmos Nov 25, 2020, 5:20 AM

#

    if f1 in file:
      with open (f"{key}.txt", "r") as c1:
        n = str(c1.read(1))
        c1.close()
        with open (f"{key}.txt", "w") as c2:
          var1 = n + 1
          var2 = str(var1)
          c2.write(str(var2))
          c2.close()

#

mind adding it to this?

ionic pasture Nov 25, 2020, 5:21 AM

#

it’s on ur 3rd line

#

remove str

fiery cosmos Nov 25, 2020, 5:21 AM

#

📎 unknown.png

ionic pasture Nov 25, 2020, 5:21 AM

#

if f1 in file:
with open (f"{key}.txt", "r") as c1:
n = c1.read(1)
c1.close()
with open (f"{key}.txt", "w") as c2:
var1 = n + 1
var2 = str(var1)
c2.write(str(var2))
c2.close()

#

like this

fiery cosmos Nov 25, 2020, 5:21 AM

#

still get the same issue

ionic pasture Nov 25, 2020, 5:22 AM

#

what is n equal too

#

can u

#

wait

fiery cosmos Nov 25, 2020, 5:22 AM

#

os.chdir("/var/www/html/.conc/")
    file = os.listdir()
    f1 = f"{key}.txt"
    if f1 in file:
      with open (f"{key}.txt", "r") as c1:
        n = (c1.read(1))
        c1.close()
        with open (f"{key}.txt", "w") as c2:
          var1 = n + 1
          var2 = str(var1)
          c2.write(str(var2))
          c2.close()

#

thats more of the code

ionic pasture Nov 25, 2020, 5:22 AM

#

if f1 in file:
with open (f"{key}.txt", "r") as c1:
n = c1.read(1)
print (n)
c1.close()
with open (f"{key}.txt", "w") as c2:
var1 = n + 1
var2 = str(var1)
c2.write(str(var2))
c2.close()

#

wait

#

hello

fiery cosmos Nov 25, 2020, 5:23 AM

#

yes

ionic pasture Nov 25, 2020, 5:23 AM

#

wait no

#

can u

#

just after

#

n = c1.read(1)

#

add this line :
print (type(n))

fiery cosmos Nov 25, 2020, 5:25 AM

#

📎 unknown.png

#

retruns as a string

ionic pasture Nov 25, 2020, 5:25 AM

#

got it

#

and

fiery cosmos Nov 25, 2020, 5:25 AM

#

should i make it a int?

ionic pasture Nov 25, 2020, 5:25 AM

#

now change « print(type(n)) » to « print (n) »

fiery cosmos Nov 25, 2020, 5:26 AM

#

📎 unknown.png

ionic pasture Nov 25, 2020, 5:26 AM

#

what do u get

#

did it print the value of n

fiery cosmos Nov 25, 2020, 5:27 AM

#

no

ionic pasture Nov 25, 2020, 5:27 AM

#

what

#

ok

#

k so try putting int

#

to the 3rd line

#

n = int(c1.read(1))

fiery cosmos Nov 25, 2020, 5:28 AM

#

📎 unknown.png

ionic pasture Nov 25, 2020, 5:28 AM

#

like do u know what u are taking

fiery cosmos Nov 25, 2020, 5:28 AM

#

i get this erro rnow

flat sorrel Nov 25, 2020, 5:28 AM

#

brave oak say you have a list of origin and destination nodes and an approximate cost to t...

I would try a physics based approach. Initially, put the nodes randomly in some N-dimensional space, then in each iteration, the nodes apply forces on one another based on the known distances (if a node is closer than it should be, push it away, etc.). Sum up all of the force vectors for the entire set before applying them together. At the end of X iterations, calculate the distance between each node pair to get a dense distance matrix.

ionic pasture Nov 25, 2020, 5:28 AM

#

do u know what c1.reaad(1) is ?

fiery cosmos Nov 25, 2020, 5:28 AM

#

yes

ionic pasture Nov 25, 2020, 5:28 AM

#

what is it

#

an int ?

fiery cosmos Nov 25, 2020, 5:28 AM

#

yes

#

it is an int

ionic pasture Nov 25, 2020, 5:28 AM

#

then why it isnt

#

putting it as int

fiery cosmos Nov 25, 2020, 5:29 AM

#

im not sure

#

'

📎 unknown.png

#

it has the value of 1

#

@ionic pasture i got it to work

#

thanks

ionic pasture Nov 25, 2020, 5:30 AM

#

how

#

what did u do

fiery cosmos Nov 25, 2020, 5:30 AM

#

i changed the variable type like u said

#

and changed the file to a diffrnet number

ionic pasture Nov 25, 2020, 5:31 AM

#

well if it returned a literal base 10 error

#

that means it wasnt an int

fiery cosmos Nov 25, 2020, 5:31 AM

#

ohhh

brave oak Nov 25, 2020, 5:31 AM

#

flat sorrel I would try a physics based approach. Initially, put the nodes randomly in some ...

hm

ionic pasture Nov 25, 2020, 5:31 AM

#

it was a character else than a number

brave oak Nov 25, 2020, 5:31 AM

#

but how does that help me construct the graph?

fiery cosmos Nov 25, 2020, 5:31 AM

#

imean i had it set it to 0

#

is 0 an int?

ionic pasture Nov 25, 2020, 5:31 AM

#

yes

#

well yes

fiery cosmos Nov 25, 2020, 5:31 AM

#

then it should of

#

but idk

#

but ty

ionic pasture Nov 25, 2020, 5:31 AM

#

weird

fiery cosmos Nov 25, 2020, 5:32 AM

#

i got it to work

ionic pasture Nov 25, 2020, 5:32 AM

#

maybe there is something else in the code linked to that

#

and that caused to not work