#algos-and-data-structs

1 messages Β· Page 117 of 1

gritty marsh
#

if you have c = 2

#

let me modify the graph

silk breach
#

so before n_0 cg(n) <= f(n)?

gritty marsh
#

all we care about is that after n_0, cg(n) >= f(n)

silk breach
#

ohhh got it

gritty marsh
#

if you look at the graph, you can see that it fluctuates

silk breach
#

yea yea

#

So what about when f(n) has a constant

#

like f(n) = 3n + 8

gritty marsh
#

okay, let's experiment on the graph

silk breach
#

wait nvm this book explains it pretty well

gritty marsh
#

do you still want me to experiment πŸ˜†

#

Let's set c = 1

#

so we have cg(n) = n^2

silk breach
#

sure lets experiment

gritty marsh
#

and f(n) = 3n + 8

silk breach
#

wait why are we taking g(n) as n^2?

gritty marsh
#

because why not

#

do you want g(n) to be n? I have no problem with that

silk breach
#

no no its fine

#

lets keep g(n) as n^2

silk breach
#

or do we take x_axis?

gritty marsh
#

x_axis

#

remember, the x axis represents n

#

the amount of input we are taking

silk breach
#

ohh got it

#

yeah

gritty marsh
#

here, n_0 is 5

silk breach
#

so we round up?

gritty marsh
#

technically it's 4.7, but I don't like fractional inputs πŸ˜†

silk breach
#

lmaoo i see

gritty marsh
#

okay, one last experiment

#

what if g(n) = n?

silk breach
#

then c = 4?

gritty marsh
#

no, not necessarily

silk breach
#

oh

gritty marsh
#

let's say c = 4

#

is there an n_0 that cg(n) >= f(n)?

#

obviously!

silk breach
#

Yes

gritty marsh
#

what you need to know @silk breach is that c just needs to be greater than 3

silk breach
#

Its 8 I put it in the graph

silk breach
gritty marsh
#

it doesn't matter if it's 3.1, 3.01, 3.001, 3.0001

#

why?

#

well let's take 1 billion as input

#

let's say c = 3.0001

#

what is 3.0001 * 1 billion?

silk breach
#

A lot

gritty marsh
#

can you calculate it for me, please?

silk breach
#

3,000,100,000?

gritty marsh
#

okay, now we go to f(n)

#

f(n) = 3n + 8, right?

#

what is 3 * 1 billion + 8?

silk breach
#

3,000,000,008

gritty marsh
#

you see?

silk breach
#

Ohhh yea

gritty marsh
#

as long as c > 3 (3 in this case is the leading coefficient of f(n)), there will always exist an n_0 such that cg(n) >= f(n) for all n >= n_0

silk breach
#

So what's the n_0 for this question

gritty marsh
#

uhhh you can calculate it using basic algebra

#

3.0001n = 3n + 8

#

solve for n

silk breach
#

Oh got it

#

Thanks a lot!

#

This was really helpful

gritty marsh
#

No problem πŸ˜‰

hollow star
#

francis be a smart boi

silk breach
#

@gritty marsh are you still here?

gritty marsh
#

Yes, but busy

silk breach
#

oh ok

fiery schooner
#

Guyss any best course for dsa?
I wanna start but i am so confused, so please help me!

trim fiber
gritty marsh
#

perhaps they meant Data Structures and Algorithms

trim fiber
#

😦

gritty marsh
#

πŸ˜†

trim fiber
subtle quiver
#

can someone help me with oop function?

mint jewel
#

!mute @arctic nebula 1d please reread our code of conduct

halcyon plankBOT
#

:incoming_envelope: :ok_hand: applied mute to @arctic nebula until 2021-05-12 10:27 (23 hours and 59 minutes).

mental parcel
#

!ask

#

Thought it was a tad, tldr just ask your question

runic lodge
#

New to python, want to learn data structs

empty trout
#

Is there any more efficient algos for sorting list of positive unique integers , than quick sort?

fiery cosmos
#

what is 0/0

empty trout
elder stone
#

Has anyone worked with PNGs with transparency images and edge detections? Seems like there is nothing on internet

fiery cosmos
autumn whale
empty trout
runic tinsel
#

i guess they are both linear

#

also counting is part of some radix implementations

rich bluff
#

I think

vocal gorge
sage quartz
#

can I get some help on Min Conflict Algorithm?

fallow canyon
#

Can anyone help me with this problem ?
https://www.hackerrank.com/challenges/find-second-maximum-number-in-a-list/problem

def runner(n, arr):
  if n < 1:
    print("Enter a value")
  elif len(arr) > n:
    print("There is more than {} no of scores".format(n))
  elif len(arr) < n:
    print("There is less than {} no of scores".format(n)) 
  else:
    print((sorted(set(arr))[-2]))
    
runner(3, [-10,0,10])

tried this code, all the test cases are getting passed in google colab but none of them are passing in the hackerrank IDE.. Please help

HackerRank
Find the Runner-Up Score! | HackerRank

For a given list of numbers, find the second largest number.

fathom quail
#

hey

#

is there record type in python

#

like in C ?

fiery cosmos
fiery schooner
spring jasper
#

You can use a tuple as a record, or a namedtuple

fickle harbor
#

is my answer to the question correct

#

im proving btw

lament oriole
#

depends what you mean by |, in python its the binary or operator but that doesnt seem reasonable in the context of the question

half lotus
#

| means divides

fickle harbor
#

I means divide

#

yes

lament oriole
#

fr? thats new to me lol we always used /

gritty python
#

yh

half lotus
#

It's different from division.

fickle harbor
#

its discrete kinda stuff

#

proofs and logic

#

in math foundation of comp sci

half lotus
#

If You use / it means you want to get the quotient. If you use |, you're just describing properties of two numbers.

lethal bridge
#

36 | 2 and 36 | 3 implies 36 | 19?

fickle harbor
#

wait mark so am i correct or wrong

half lotus
#

I haven't read it all yet. Got distracted answering the | question

fickle harbor
#

sorry lol

lethal bridge
#

Yes you are claiming that 36 | 2 and 36 | 3 implies 36 | 19?

fickle harbor
#

ig?

lethal bridge
#

So does it?

half lotus
#

Yeah, that proof looks solid to me.

fickle harbor
#

wait hold up so thats that

#

but i changed in my own words, is this correct

half lotus
#

Yeah it's not too complicated. You're just using the definition of | and some algebra.

fickle harbor
#

nvm i dont have it lol but yeah thats what i did so i should get most of the poinst or all ig

half lotus
#

You don't have what?

fickle harbor
#

my version of it but obv i did the same as this method so i am fine

#

but thanks alot

lethal bridge
#

@half lotus I don't see how it works at all >_>

half lotus
#

What was it again? If a | b and a | c, then a | (5b + 3c)?

lethal bridge
#

Oh wait

#

I'm reading the | notation in the wrong way

#

The proof seems ok then

half lotus
#

It's "a divides b"

#

meaning b Γ· a has no remainder

lethal bridge
#

I read it as a is divisible by b, which is the inverse

#

so I got it different

half lotus
#

Yeah I got tripped up by that before

eternal mulch
#

hey guys, how do i change the date format to May x, 2021?

#

ie. 2021-05-11 -> May 05, 2021

fiery cosmos
#

I am new to python can any one tell which string function can be used to find what is in a string at a specific index position

fiery cosmos
eternal mulch
#

how is that done?

#

ive seen people use datetime function on stack but i keep getting errors

fiery cosmos
halcyon plankBOT
#

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

001 | h
002 | y
003 | w
fiery cosmos
vocal gorge
fiery cosmos
#

what is epsilon rooBlank

vocal gorge
#

any real number >0

fiery cosmos
#

The bottom seems to be saying log(d(n)) grows the same as log(n)/log(log(n)) 02think (differing by a constant factor)

vocal gorge
#

The former means that it grows so slowly it grows slower than n to any positive power, if I'm not mistaken

fiery cosmos
#

oh, weird

vocal gorge
fiery cosmos
#

Just casually doing complex math on wordpress rooNumbers

#

but yeah, that tallies with what I was thinking wiki was saying

latex.png
#

which boils down to n^(1/log(log(n))) rooHmm vvBlank

#

curious

fiery schooner
#

Guyss anyone has practice list for list comprehensions

stable pilot
#

anyone here good at competitive

#

programming

#

i got a doubt

#

its in help-popcorn

manic violet
#

hey !!!! can anyone tell me where i can learn this python language easily ??

stable pilot
#

with time

manic violet
#

from where i have to start for it ??

burnt vigil
manic violet
#

can you suggest me some channels?

manic violet
burnt vigil
burnt vigil
#

this one is a pretty good course on youtube but if you want other similar one then just search for PYTHON COURSES on yt, and freecodecamp has good courses online

#

I dont recommend to watch long parts of it , watch short β€œpieces” it and learn slowly also make notes

manic violet
burnt vigil
paper yacht
#

whats the most common way used to print a Tree

austere sparrow
#

seriously though, I'd expect something like this

tree.png
#

(depending on what the tree represents)

paper yacht
#

i see

#

can i do that without involving any graphics at all

#

like plain text

austere sparrow
#

@paper yacht That's plain text. They're just using fancy ASCII characters to print out the lines

paper yacht
#

yeah sorry thats what i meant

#

i dont want to use those extra characters

#

coz it kinda gets complex just to print them out

austere sparrow
#

You can use |-+/\

#

Another slightly less conventional way is to use S-expresisons:

big-macros-class.png
#

basically, lots of parentheses

paper yacht
austere sparrow
#

but it depends on what kind of tree you want

paper yacht
#

a Binary Search Tree

#

with normal data like integers or strings

austere sparrow
#

then it's probably better to print it centered, otherwise it's awkward

unknown.png
paper yacht
#

but i have to do a lot of formatting right

austere sparrow
#

yep

paper yacht
#

thats sad

austere sparrow
#

doing it for arbitrary trees will be tricky, because you'd have to truncate very long strings etc.

paper yacht
#

yeah makes sense

austere sparrow
#

You could render an HTML table

#

that's a nice hack

paper yacht
#

i havent learnt yet how to render HTML but i can if its that good of a thing

#

its probably useful in a lot of areas apart from printing trees

#

hmm

#

thanks for the idea

austere sparrow
#

and then you can remove the borders πŸ™‚

paper yacht
#

WOW

#

clean

austere sparrow
#

yeah, you can merge table cells in HTML

paper yacht
#

alright

stable pecan
#

i have a printer for things similar to bsts -- the art data structure i implemented pretty prints

paper yacht
#

oh?

stable pecan
#

though it isn't centered, it just prints top to bottom

# 
In [27]: t = AdaptiveRadixTree()

In [28]: t['Python'] = 1; t['Python Discord'] = 1; t['Picnic'] = 1

In [29]: print(t)
''
╰─'P'
  β”œβ”€'icnic'
  ╰─'ython'
    ╰─' Discord'
paper yacht
#

better than just text tho

#

also do we ever remove nodes from BSTs?

brave matrix
#

where can i get help aa

stable pecan
#

yeah, but you have to maintain order when you delete nodes

paper yacht
mossy sedge
#

I dnt think that messages like this are allowed here

versed ravine
agile sundial
#

if only we could actually read it

coarse warren
#

lol

fervent saddle
#

Does anyone know if using list.clear on a list or deleting all of its reachable references so it will get garbage collected is O(1) in pypy?

fiery cosmos
#

memoryview shape casting is disappointing

#

it seems ideal at first for quickly passing binary data to constructors, except that you cant pass a sub view

#

i imagined it would be great for starmapping to ctors but nope

#

as usual in py, as you get lower, u get slower

fiery cosmos
#

oh you know what, i take that back. tolist also listifies the subarrays. its not ideal, but it gets the job done

#

definitely less than ideal if you have a very large amount of data though

stuck folio
#

Hope someone has time to help me :: Any idea how we can EXPAND, or STRETCH-out that polynomial graph? It's too narrow; would also like to see curved bottom (a bit below X-axis), any help appreciated :: https://i.imgur.com/g6Cbn02.png Thanks.

Imgur
#

Or point us where we might find assistance, thanks πŸ™‚

ivory yacht
#

Adjust your X/Y limits? You set specific ones on line 98-99, then read them back in and scale them up for some reason?

fiery cosmos
#

I need help deciphering a message can anyone help me?```
Key: Cipher Text:
⎑6 24 1⎀ ⎑654⎀
⎒13 16 10βŽ₯ ⎒694βŽ₯
⎣20 17 15⎦ ⎣878⎦

Reference Table:
a 0 | g 6 | m 12| s 18| y 24|
b 1 | h 7 | n 13| t 19| z 25|
c 2 | i 8 | o 14| u 20|
d 3 | j 9 | p 15| v 21|
e 4 | k 10| q 16| w 22|
f 5 | l 11| r 17| x 23|

grizzled schooner
fiery cosmos
#

No never heard what is it?

#

I heard it could also be an affine cipher but I don't know which @grizzled schooner

grizzled schooner
#

i doubt it's the affine cipher because affine has only 2 keys

fiery cosmos
#

oh ok

grizzled schooner
#

this looks like the hill cipher because of the matrices

fiery cosmos
#

How would I go about solving it there is no algorithm included?

grizzled schooner
#

err you basically multiply each number in the cipher text with all the numbers in a certain row of the key

#

i'm not that great at explaining math stuff, i recommend looking up an article on matrices

#

also not sure why the cipher text values are in the 600s?

fiery cosmos
#

I think there suppose to be separated...

grizzled schooner
#

what do you mean?

fiery cosmos
#

actually I got lost... is there any articles which can help me solve this cipher? @grizzled schooner

grizzled schooner
#

lol maybe the wikipedia page

fiery cosmos
#

ok so your steering towards the hill cipher alright

grizzled schooner
#

i'm not that familiar with cryptography but I don't know any other ciphers that invove matrices

agile sundial
#

looks like hill cipher

agile sundial
fiery cosmos
thorny cipher
#

have i sent 50 messages yet?

agile sundial
agile sundial
#

yeah, the plaintext

vocal olive
#

please help i am facing problem with level order traversal check channel #help-donut

royal solstice
#

what are some good tutorials i have to check on python i wanna start a project but don't know what project i don't have one in my mind and also im a newbie webdev soo anything i have to learn in that era

halcyon plankBOT
#

Hey @dusk flare!

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

dusk flare
hardy dawn
#

does anyone have best source to learn algorithm and data structure ?

trim fiber
random fern
#

hey guys i am stuck on a problem in python involving writing a code about loans but only using min and max functions

#

can anyone help?

hardy dawn
halcyon plankBOT
#

Hey @empty trout!

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

empty trout
wet dew
#

I wrote an app that takes an input from a separate class/module (only using this separate module to create a data structure similar to C/C++ dictionary.variable functionality). At the end of the app I pickle the file....and ideally would like to reload the app by feeding it the loaded pickle.

Unfortunately the pickled file has dependencies on the first module and the only way to load it is to rerun the first module (obviously not ideal). Any suggestions on how to get around this?

#

Outside of the obvious dont use the class for the C data structures functionality and just use pythons nested dictionary....so id have to reformat my code to dictionary['variable'] instead of dictionary.variable

valid harness
#

A person died during the time I posted this

wraith valve
#

like is the sequence supposed to repeat itself or something?

#

or am i supposed to use the "fibanacci" strategy of storing previous values

half lotus
#

Is it possible to find the shortest path in an unweighted cyclic graph using DFS?

#

Yes, it has cycles.

#

Every resource I read suggests BFS is the way to go

#

With DFS, the problem I run into is that it may first visit a longer path, and then all those nodes are marked as visited. Therefore, it will skip the nodes leading to the shorter path.

white imp
#

Has anybody solved PS2 on MIT OCW's CS 6.0002 pset? I'm trying to solve the weighted DFS problems and could use some help checking my solution for accuracy

limpid hornet
#

Just wanted some clarification

for a depth first search of this graph the
traversal order would be U,V,Y,X right

Because it cant traverse the nodes w and z?

unknown.png
vocal gorge
#

w isn't reachable from U (or any node at all other than itself, in fact), yeah.

agile sundial
#

is it reachable if you start at it?

vocal gorge
#

🀷

#

is an empty path a path

scarlet elm
scarlet elm
hexed raven
scarlet elm
#

2 ways u can shift shops

hexed raven
#

does going from shop 1 to shop 2 and coming back regarded as 1

scarlet elm
scarlet elm
scarlet elm
#

Which block u take

#

If u take any one block the other will make the 2nd way

#

All the items are different

scarlet elm
#

Did u understand the problem??

hexed raven
#

isn't our goal to shift all goods to shop 2

scarlet elm
scarlet elm
hexed raven
#

first take 2 goods weight 100, 100 each to shop 2
then come back to shop 1 with one good of 100,
then take good of 300 to shop 2
then again come back with 100 to shop 1
AND FINALLY take 100 , 100 to shop 2
isn't this the problem should be solved?
just wannna make things clear so I can work on it

scarlet elm
#

Yes the problem is solved but while u bring the 100 block for the 1st time u have 2 ways

#

Better index 1st 100 block with Id 1

#

And 2nd 100 block with id 2

#

While coming from shop 2 to shop 1 u have option to take block 100 having id 1

scarlet elm
#

While coming to shop 1 u may carry block 100 having id 2

scarlet elm
#

Did u got my explanation?

#

Or shall I arrange a voice channel?

hexed raven
oblique panther
#

!mute 826452894689656873

halcyon plankBOT
#

:incoming_envelope: :ok_hand: applied mute to @mystic steppe until 2021-05-14 15:48 (59 minutes and 59 seconds).

scarlet elm
#

Ok atleast help me the problem what u understood

#

I can follow up to my question

hexed raven
#

okay, I get it I will let u know when I am done

hexed raven
#

@scarlet elm you got some more inputs for this problem

scarlet elm
#

no mate only these

crystal forge
#

Can someone tell from where i can learn data structures and algorithms using python?

scarlet elm
#

jenny lectures

#

yt

crystal forge
#

They cover all the topics??

scarlet elm
#

yeah basics

trim fiber
wraith valve
agile sundial
#

i just waited like 30 seconds

#

what's your part 1?@wraith valve

wraith valve
#

oh i got part 1

#

cuz i just looped though and generated

#

cuz u only needed 2020 iterations

agile sundial
#

yeah, but if you did it efficiently you should be able to just brute force part 2 also

#

I can't see it since I'm not logged in, is it 3 million?

wraith valve
#

30 mil

agile sundial
#

ooh

#

show your part 1?

wraith valve
# 
fn main() {
    let result = input_parser::read_line_input(15, "numbers".to_string());
    let mut g = game::Game::new();

    match result {
        Some(value) => {
            let starting_nums = value[0].split(",");
            for i in starting_nums {
                let num: u32 = i.parse().unwrap();
                g.insert_starting_num(num);
            }
            let n = g.nth_number(2020);
            println!("Number is: {}", n);
        },
        None => {
            println!("Could not parse input");
        }
    }
}
# 
pub struct Game {
    last_nums: HashMap<u32, u32>, // number and turn last said
    last_last_nums: HashMap<u32, u32>, // number and turn last last said 
    last_said_num: u32,
    turn: u32,
}

impl Game {
    pub fn new() -> Self {
        Game {
            last_nums: HashMap::new(),
            last_last_nums: HashMap::new(),
            turn: 1,
            last_said_num: 0,
        }
    }

    pub fn insert_starting_num(&mut self, num: u32) {
        self.last_nums.insert(num, self.turn);
        self.last_said_num = num;
        self.turn += 1;
    }

    fn insert_num(&mut self, num: u32) {
        // essentially copy the values to last last if the value is already in last
        match self.last_nums.get(&num) {
            Some(val) => {
                self.last_last_nums.insert(num, *val);
            }
            None => {}
        }
        self.last_nums.insert(num, self.turn);
        self.last_said_num = num;
    }

    pub fn next_turn(&mut self) {
        // check last number spoken
        match self.last_last_nums.get(&self.last_said_num) {
            // has been said before
            Some(value) => {
                let diff = self.last_nums.get(&self.last_said_num).unwrap() - value;
                self.insert_num(diff);
            },
            // never said before
            None => {
                self.insert_num(0);
            }
        } 
        self.turn += 1;
    }

    pub fn nth_number(&mut self, n: u32) -> u32 {
        while self.turn <= n {
            self.next_turn();
        }
        self.last_said_num
    }
}
#

the missing module too

agile sundial
#

that's long

#

pastebin lol

wraith valve
#

didnt get zapped for pastebin yet lol

#

essentially what I do this this

pub fn nth_number(&mut self, n: u32) -> u32 {
        while self.turn <= n {
            self.next_turn();
        }
        self.last_said_num
    }
#

which is loop though till i hit the turn number

agile sundial
#

did you compile with optimization flags

wraith valve
#

nope

#

like the previous day or 2 which was the plug one

#

apparently the trick was using previous calculation

agile sundial
#

ngl, I'd just wait like a minute or two

wraith valve
#

but they did say in the beginning that each question should be 15 sec max

agile sundial
#

yeah, but who's counting

wraith valve
#

da faq

#

i compiled with release

#

and it was done in 3 secs

#

da faq

agile sundial
#

lol

#

right answer?

wraith valve
#

yeah

#

so confused but i will take it

agile sundial
#

lol, nice

grizzled schooner
#

this is not a help channel

agile sundial
#

this is not a modmail thread

grizzled schooner
#

πŸ˜”

wind maple
#

hi can anyone decipher this in the long format

# 
list(k for k,_ in itertools.groupby(k))```
spring jasper
#

Wdym decipher

#

Thats pretty clear imo
It returns the unique elements in k in a list

agile sundial
#

it only dedupes adjacent elements

spring jasper
#

Yes correct my b, didnt think of that when testing

agile sundial
#

a bit annoying to use k as the loop variable as well, but whatever

#

actually, k is ok as the key, k as an iterable name is weird

spring jasper
#

Yea if this was a proper for loop k would be overwritten

civic current
# 
def checker(_token):
    r = get('https://api.eternal.com/login=nowl666')
    if 'good' in r.text:
        with open(good_path, 'a+') as f:
            f.write(f'{_token}\n')


if __name__ == '__main__':
    tokens = open(tokens_path, 'r').read().split("\n")
    for token in tokens:
        while True:
            if threading.active_count() <= 250:
                threading.Thread(target=checker, args=(token,)).start()
```how can i increase a speed i have file with 16k tokens
fiery schooner
#

Use recursion rather than for loop

#

Define a function to read and call it inside the loop again

fervent saddle
#

Python doesn’t optimize recursion

fiery schooner
#

Yeah but time complexity will decrease mostly.

agile sundial
#

how?

fervent saddle
#

Are you sure you need to repeatedly request the same web address?

#

Wouldn’t that just give the same thing each time?

agile sundial
#

that looks kinda malicious though ngl

#

and yeah, the while true inside the other loop doesn't make sense

keen hearth
civic current
summer moss
#

Hi, I'm testing some algorithms and I was thinking can I use my gpu for calculations to increase performance?

#

or can I increase use of my cpu during calculations.
Right now I'm running algorithm to find 100, 200, 300... 1000 words in 400'000 words. CPU use is ~15%, and it's been running for ~9 mins

vocal gorge
#

Depends on what kind of algorithm it is.

#

GPUs are good at very specific kinds of computation - stuff that's very parallelizable.

agile sundial
#

like processing graphics

wraith valve
#

make sure ur not being locked by GIL

#

like creating a bunch of python threads will use lots of mem but they wont run in parallel

brave oak
plush bramble
#

Hi iron man u dead

dapper sapphire
plush bramble
#

🀣 🀣 🀣

minor pumice
# agile sundial how?

Because recursion uses stack and stack is time expensive if you operate it on large data

agile sundial
#

he said time complexity

#

and he said recursion would be better

minor pumice
#

||recursion is never better||

#

Especially in competitive programming if you want to make something you would use recursion only if the data is small and to look fancy or use recursion because there is no other way

#

You can search on internet more about it, but I am sure most of the information you will find will be agains recursion even tho i use it :))

lean dome
#

The time complexity of a recursive and iterative solution will generally be the same, regardless of which one is faster

brave oak
brave oak
#

iteration and recursion are equivalent

#

it’s all about ease of expression

minor pumice
#

And I think this is where you are wrong

minor pumice
#

And that is a lot ...

lean dome
#

Even if we take that as fact, that's still the same time complexity.

minor pumice
#

Sure, I agree but you don’t want to know how many points I lost with recursion and got with iterative at competitions

lean dome
#

If one function is consistently 3x slower than another function regardless of the input, the two functions have the same time complexity.

minor pumice
#

Sure, I agree but maybe on some test cases it won’t work just because it is 3x slower

#

It happened to me ;-;

brave oak
#

the point is not absolute time taken, but time complexity

#

which was the original topic

minor pumice
#

Have you guys been to real competitions ?

brave oak
#

nobody is saying that an iterative solution might not be faster in some cases

#

and if you use recursion in a language which doesn’t have TCO

#

obviously you need to pay for it

#

πŸ₯΄

lean dome
#

Someone asserted that a recursive algorithm would have lower time complexity than an iterative one, which is how this whole conversation started. It won't. It will have the same time complexity.

lean dome
agile sundial
#

and of course, in "real competitions", often an iterative solution is much more complicated than a recursive one

minor pumice
#

sure, but often in real competitions iterative solutions gives more pointes than the recursvie one

#

and by real competitions i don't mean an insult

#

i mean some competitoins but not codeforces

#

in codeforces you only get AC or not, there are no intermediate scores

crystal kelp
#

Return the sum of the numbers in the array, except ignore sections of numbers starting with a 6 and extending to the next 9 (every 6 will be followed by at least one 9). Return 0 for no numbers.
summer_69([1, 3, 5]) --> 9
summer_69([4, 5, 6, 7, 8, 9]) --> 9
summer_69([2, 1, 6, 9, 11]) --> 14

#

can anybody help me with the logic of this example...please!!

#

def summer_69(arr):
total = 0
add = True
for num in arr:
while add:
if num != 6:
total += num
break
else:
add = False
while not add:
if num != 9:
break
else:
add = True
break
return total

#

here is the code

#

but i could not understand the second while loop

serene mango
#

Also, a recursive approach can be slower, even if the time complexity is same.

#

Magnitudes slower

#

A classic example is for generating n-th fibonacci number

#

@minor pumice

minor pumice
#

that is only related because it is exponential

#

lol

#

you can do the same exponential program iterativelly with a queue

#

and it's litarlly the same

#

i can do recursive dp and get a nice compleixty

serene mango
#

Yeah, But I was talking about speed on same time complexity.
And it's NOT literally the same. And definitely not for getting just an n-th fibonacci number if we take space into consideration

austere sparrow
#

well, it's not that bad πŸ™‚

unknown.png
#

3.5x difference

minor pumice
#

well that is huge

austere sparrow
#

Yeah, pretty big difference. But not magnitudes worse.

serene mango
#

Generate 40th

minor pumice
#

magnitudes worse won't ever be

minor pumice
#

2^40 time

#

operations i mean

serene mango
#

exactly but using iteration u can in microseconds

austere sparrow
minor pumice
#

you can do iterative in expo as well

#

and you can do recursive in O(n) as well

#

dude

#

depends on how you implement

serene mango
minor pumice
#

in this case yes

austere sparrow
#

The iterative is O(1) space complexity, the recursive is O(n) space complexity. Both are O(n) in time complexity.

vocal gorge
#

also, the complexity for recursively calculating fib(n) the naive way isn't 2^n, it's fib(n), which is around phi^n, where phi is the golden ratio

agile sundial
minor pumice
#

no

#

it is different

#

it surely is

austere sparrow
agile sundial
#

could you explain, i don't understand, for a dfs?

#

yeah, but that's just a constant isn't it

minor pumice
#

dfs is bad example

#

lol

serene mango
austere sparrow
vocal gorge
agile sundial
#

gotcha

minor pumice
#

i don't think you are right

agile sundial
austere sparrow
#

(look at my snippets)

agile sundial
#

right, but that's an entirely different approach, not simply converting between recursive to iterative. unless i'm confusing terms...

vocal gorge
# minor pumice false

how come?

fib(n) = fib(n-1) + fib(n-2)
recurrent equation for complexity:
T(n) = T(n-1) + T(n-2)
T(0) = T(1) = 1
This is the equation for fibonacci numbers themselves, hence
T(n) = fib(n)
- the complexities for naive fibonacci is, itself, the fibonacci sequence.
minor pumice
#

true

#

i am sorry

austere sparrow
#

Life ain't easy!

minor pumice
#

why is iterative log(n) lol

austere sparrow
vocal gorge
#

ah, the good old non-O(1) arithmetic

#

hyperfactorial, huh

#

how did you get that?

austere sparrow
#

wolframalpha πŸ˜›

#

not sure if that's correct

vocal gorge
#

like, from what equation?

minor pumice
austere sparrow
minor pumice
#

there will be ever be an error

vocal gorge
#

oh, lol, okay

#

computer science is all a lie

#

Computers aren't turing-complete because they have finite memory πŸ˜”

austere sparrow
vocal gorge
#

therefore, all space complexities are O(1)

serene mango
#

Can you please explain why iterative is logn space please?

minor pumice
#

it is log_10

#

lol

#

log means log_2

agile sundial
#

is that not log

minor pumice
vocal gorge
austere sparrow
austere sparrow
vocal gorge
minor pumice
minor pumice
vocal gorge
#

c++ doesn't have infinite-sized ints.

minor pumice
#

it is a table of logatirhms

agile sundial
#

only with bounded ints

serene mango
minor pumice
austere sparrow
vocal gorge
minor pumice
#

if the numbers are <= 2^128 we can

minor pumice
#

it's not log time

#

it is log_10 time

austere sparrow
#

O(log2(n)) is the same as O(log2(n) * constant)

minor pumice
#

ik but (ln(2)/ln(10)) is not a constant

#

lmao

austere sparrow
#

what...

vocal gorge
#

you sure about that

agile sundial
#

it is tho

minor pumice
#

it is a mathematical constant

austere sparrow
#

!e

import math
print(math.log(2)/math.log(10))
halcyon plankBOT
#

@austere sparrow :white_check_mark: Your eval job has completed with return code 0.

0.30102999566398114
agile sundial
#

what other constants are there

austere sparrow
#

And 2 is... biological?

agile sundial
#

spiritual

vocal gorge
#

O(2^n) != O(e^n), but O(2n) = O(e*n), and O(lg n) = O(ln n)

#

that's just, like, how logarithms work

minor pumice
austere sparrow
#

wait, no

minor pumice
#

and it is not true

#

we dont do so

agile sundial
#

can't you?

vocal gorge
#

wait, how?

minor pumice
#

we dont ahve logatithmic constants

agile sundial
#

some matrix thing?

minor pumice
#

sure

#

matrix chain

vocal gorge
#

numerically via calculating it using the formula? I tried that, but it very quickly hits double precision limits.

minor pumice
#

no

#

using matrix chain multipliucation

austere sparrow
serene mango
vocal gorge
#

that's what the formula I'm talking about is derived from, yes

minor pumice
#

and we can not have such constants

#

lol

austere sparrow
minor pumice
#

the same way i can say log_2 = log10000* (ln(2)/ln(100000))

vocal gorge
#

it's different with floats, which are finite-size (and, due to that, can't actually go to infinity)

minor pumice
#

and in cp the same

austere sparrow
minor pumice
#

but it is a sbunitar constant

#

such thing does not exist

vocal gorge
#

what's that? pithink

austere sparrow
#

I can't find that term anywhere

minor pumice
#

because there are no written rules

vocal gorge
#

ah yes, the unwritten rules of street CS

austere sparrow
#

so you just... invented your own O notation?

#

ok

minor pumice
#

the same way i can say 2^n = 3^n

austere sparrow
#

there's no such k that 2^n * k = 3^n

vocal gorge
#

And you'd be wrong, just like you are about log2(n) and log10(n) not being constant multiples of each other.

#

mathematics isn't exactly opinion-based

minor pumice
#

you can't

#

every where i have log2 i will write log1000000

#

than

vocal gorge
#

log2 isn't equal to log10

#

but O(log2(n)) is equal to O(log10(n))

#

for the same reasons that O(2x) = O(10x)

serene mango
minor pumice
#

2^n = 3^n
2^n = (6)^n / 2^n
2^(2*n) = (6)^n
(2^n)^2 = 6^n
2^n = sqrt(6)^n

#

that about this @austere sparrow

#

i started with 2^n = 3^n

#

and got here 2^n = sqrt(6)^n

#

i manipulated the wrong thing into something else

#

the same way it can be manipulated if you take a prove to infinity sqrt(6)=2

#

if we repeat the operations an infinite ammount of time

#

what do you think will be the

#

value

austere sparrow
#

@minor pumice Are you saying that log[a](n) = log[b](n) * ln[a]/ln[b] is wrong?

minor pumice
#

i perfecly agree that

#

i am saing that considerng ln[a]/ln[b] as a constant is wrong

#

even tho

#

mathematicaly

#

it is a constant

agile sundial
#

huh?

minor pumice
#

2^n = 3^n
2^n = (6)^n / 2^n
2^(2*n) = (6)^n
(2^n)^2 = 6^n
2^n = sqrt(6)^n
but what about this?

#

just take it to infinity and consider making this operation an infinite amount of time

#

i don't have that ammount of time now, but i will prove that by doing that an infinite ammount of time, it will converge

#

because it clearlly will

austere sparrow
minor pumice
#

2^n * 2^n = 2^(n+n)

#

2^n + 2^n = 2^(n+1)

agile sundial
#

no?

austere sparrow
#

wait, right, that part is right.

#

Wait. This doesn't prove that 2 = sqrt(6). You're assuming that 2^n = 3^n, which only holds for n = 0

minor pumice
#

sure

#

it does not prove

austere sparrow
#

so... what's your point?

minor pumice
#

but by doing this operations

#

like

#

look

#

i can do now

#

2^n = sqrt(12/2)^n
2^n = 2^(n/2) * sqrt(12)^n
sqrt(2)^n = sqrt(12)^n

#

and by doing these operation on and on

#

the values are getting closer and closer

#

and those will converge

serene mango
minor pumice
#

becase calculus

#

(a field of math)

serene mango
agile sundial
#

damn, thought it was botany

minor pumice
#

and i could just say than that 2^n = 3^n * C

minor pumice
#

i would take

#

the modulo

#

of the difference

#

of the terms

#

and it will converge into 0

#

because getting closer and closer with smaller and smaller steps

minor pumice
#

sure

#

i agree

#

but hey

#

it's a constant

#

and NO it is not a constant

#

we dont take imaginary numbars as constants

vocal gorge
#

Please do show it, then.

minor pumice
#

as i said i dont have the time to me, but be sure i will show it

serene mango
#

A constant is always a constant if you are talking about it in the same underlying field of numbers.

#

If you work in 2 different domains, such as one which is not an integral domain and other which is, a constant in one domain may not be a constant in other (it might not exist)

#

but here we are working in the same domain

austere sparrow
#

The definition of O notation (in CS sense, which is actually Big Theta in calculus) is:

f(x) = O(g(x)) means:
lim[x -> inf](f(x) / g(x)) = C,
    where C is a non-zero constant

Then it follows

Let f(x) = O(g(x)). Also suppose that K is a non-zero constant.

since f(x) = O(g(x)), then lim[x -> inf](f(x) / g(x)) = C, where C is a non-zero constant.

then, from basic calculus:
lim[x -> inf](f(x) / (g(x) * K)) = C / K
C / K is also a non-zero constant, so clearly then f(x) = O(g(x) * K).

Therefore, for any non-zero constant K, O(g(x)) is the same as O(g(x) * K).

I think this is a pretty straightforward proof. So unless you come up with a different definition of O notation...

minor pumice
#

ok, so how i see her e

#

we can take complex numbers as constants

#

i dont have a problem with that

#

i literally dont

#

i love when i have to make an n^2 code and i can prove it is n

#

it's genius

#

just take ln(-1) as a constant and make conversions

#

why not

#

@austere sparrow

#

Just found a nice demonstration of n!=(n-2)!

#

Assume n!=(n-2)!

#

Divide both sides by (n-2)!

#

n(n-1)=1

#

n^2-n-1=0

austere sparrow
#

have you thought of applying for Abel prize? lemon_pleased

vocal gorge
#

you seem to not realise what the O-notation even is.

minor pumice
#

I just want to show you that by assuming log2=log10 because of an irrational constant is wrong

minor pumice
#

Get the solution > 0, (1+sqrt(5))/2

vocal gorge
minor pumice
minor pumice
minor pumice
minor pumice
austere sparrow
#

Okay, what algorithm can you use to add two arbitrarily large integers, both b bits long, in less than O(log(n))? πŸ™‚

minor pumice
#

Arbitrarily large numbers not

#

But <=2^128 we can

vocal gorge
#

If you don't know the difference between O(f) == O(g) and f == g, that's on you 🀷

minor pumice
#

He literally said that a number in base 10 has log2 digits

#

Log2 of that number

agile sundial
#

in binary, yes

minor pumice
#

Times a constant but as you guys said does not matter

minor pumice
#

As specified

agile sundial
#

computers use binary

minor pumice
#

But we as humans can store a number as an array

#

And operate faster like so

agile sundial
#

and wasn't the original claim O(log2 N) anyway

minor pumice
#

It claimed b steps

agile sundial
#

actually, python does store numbers as an array, that's how it's able to get arbitrary size ints

minor pumice
#

And then why you say binary

#

It’s clearly log10

minor pumice
#

Literally b steps

empty trout
#

buble sort complexity it's O(n^2) or O(n*(n-1))?

jolly mortar
#

O(n*(n-1)) = O(n^2-n)
only the highest degree term is kept,
so O(n^2-n) = O(n^2)

faint gate
#

off topic question here, but are there any university professors specializing in mathematical modelling/statistics or economics here?

uncut talon
#

Assuming an instance of a class has references to other objects of that same type, as:

from dataclasses import dataclass
# please ignore syntax, I know it's wrong, it's just an example
@dataclass
class Node:
    value: int = None
    root: Node = None
    left: Node = None
    right: Node = None

But I can't exactly declare root, left, right type of Nodesince by the time I'm declaring it I've not declared the Node class (it's being built).
Does anyone have a good solution to use a typing approach to this problem?

fiery cosmos
#

@uncut talon That doesn't seem to fit the channel topic, but you could use a string instead (they're called forward references) left: 'None' = None

uncut talon
#

@fiery cosmos thanks, that works but seems like it's doing the same thing it'll do if I don't declare the types.
It still allows me to parse any non Node types. to left, root, right, I'd still have to explicitly check types.

fiery cosmos
#

@uncut talon Please ping me in a help channel if you want to continue, but the thing is that dataclass doesn't validate the type of arguments you pass in

serene mango
#

I think this is not the right channel for such topic.

hardy dawn
#

is learning algorithm a story and how to apply it is important ?

#

i found it so hard to apply when i write code

shut breach
#

a story?

flint kite
#

can someone help me explain this one

minor pumice
#

As I see you don’t really have to balance the tree

#

So you can just insert the new nodes lmao

spice gust
#

How would i describe what is happening here?

waxen thistle
#

checks if the value is empty ?

#

then again it is checking if all the values are empty simulatenously

spice gust
#

basically the Attributes are stored in one file

#

and the data is stored in a database

#

Thats how they are inserted

#

But how does it actually retrieve the data?

quick parcel
# spice gust

you could use:py if all(self.EmployeeNumber.get(), self....):

spice gust
waxen thistle
spice gust
#

Did this

spice gust
brave oak
eager hamlet
#

so my strategy for this

#

is to treat the deque as just 2 stacks together

#

and try and put the largest elements at the top and the lowest elements in the queue

# 
            if (stack.empty() || queue.empty() || deck.empty()) {
                if (stack.empty()) {
                cout << "pushStack" << endl;
                stack.push_back(op);
                } else if (queue.empty()) {
                    cout << "pushQueue" << endl;
                    queue.push(op);
                } else {
                    cout << "pushBack" << endl;
                    deck.push_back(op);
                }
            } else {
                if (op > stack.back()) {
                    cout << "pushStack" << endl;
                    stack.push_back(op);
                } else if (op > deck.front()) {
                    cout << "pushFront" << endl;
                    deck.push_front(op);
                } else if (op > deck.back()) {
                    cout << "pushBack" << endl;
                    deck.push_back(op);
                } else {
                    cout << "pushQueue" << endl;
                    queue.push(op);
                }
            }```here's my c++ code if it's relevant (yes ik this is a python discord,)
#

but that algorithm seems to WA

dapper sapphire
#

I'm doing search method for tree:

    def __search(self, current, value):
        print("current.value:", current.value)
        if value == current.value:
            return True
        elif value < current.value and current.left is not None:
            return self.__search(current.left, value)
        elif value > current.value and current.right is not None:
            return self.__search(current.right, value)
        return False

    def search(self, value):
        current = self.root
        return self.__search(current, value)

so if we did print(tree.search(1))
1 would return True
Then in the call stack 2 would return True that we received from 1
4 return True that we originally received from 1 and so on...?

drifting palm
#

is anyone good with algos ard here?

#

specifically uninformed and informed search

#

really need someone to guide me for an assignment

naive reef
#

"myfloat = 7.0
print"(myfloat)"
"myfloat = float(7)
print"(myfloat)" whats wrong

candid osprey
#

What's with the random quotes? Can you repost the correct code

#

!code

halcyon plankBOT
#

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.

pine lichen
#

hello, is it possible to create nested dict instantly like this?

given_key = "data.nest.nestagain"
sampledict = {}
sampledict[given_key] = "hello"

so far, this is what I found https://github.com/mewwts/addict , but it needs me to use it like this:

sampledict.data.nest.nestagain = "hello"  # I cannot use this since my key is an actual string from db
runic tinsel
#

you can write the literal

#

sampledict = {"data": {"nest" : {"nestagain" : "hello"}}}

#

or write a function that does it

pine lichen
#

right, I guess I'll need to do it myself with split and loops

#

thanks

hexed raven
#

If the weight are negative is this the right MST for above graph

mst.jpg
late dune
# 
class Node:
    def __init__(self, data):
        self.data = None
        self.next = None


class ClinkedList:
    def __init__(self):
        self.head = None
    
    
    def prepend(self,data):
        if self.head:
            self.head=Node(data)
            self.head.next=self.head
        else:
            new_node=Node(data)
            cur_node=self.head
            while cur_node.next!=self.head:
                cur_node=cur_node.next
            cur_node.next=new_node
            new_node.next=self.head
            self.head=new_node 
    
    
    def append(self,data):
        if not self.head:
            self.head=Node(data)
            self.head.next=self.head
        else:
            new_node=Node(data)
            cur_node=self.head
            while cur_node.next!=self.head:
                cur_node=cur_node.next
            cur_node.next=new_node
            new_node.next=self.head
    
    
    
    def printlist(self):
        cue =self.head
        while cue:
            print(cue.data)
            cue=cue.next
            if cue ==self.head:
                break
            
    
    
cclist = ClinkedList()
cclist.append("D")
cclist.append("C")
cclist.prepend("B")
cclist.prepend("A")
cclist.printlist()
#

circular linked list

#

output problem

grizzled schooner
#

what's the problem?

late dune
#

no output

#

idk what is the problem

calm knoll
#

Hi! I'm looking for help for a formal proof of a boolean expression, namely "(True ↔ x) ≑ x", as I keep getting stuck at ((x ∨ Β¬True) ∧ (Β¬x ∨ True)) - anyone that can help?

agile sundial
#

does that emoji mean or

jolly mortar
#

equivalent, I think

agile sundial
#

eh? isn't that =

jolly mortar
#

do truth tables count as formal proofs

# 
True | x | True <=> x
  1  | 0 |     0
  1  | 1 |     1
agile sundial
#

probably

jolly mortar
#

Either way

True <=> x
= (¬True ∧ ¬x) ∨ (True ∧ x)
= False ∨ x
= x
stable pecan
# 
In [17]: print(TruthTable('p and q', 'p or q', 'p then q', 'p iff q'))
β”Œβ”€β”€β”€β”¬β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚ p β”‚ q β”‚ p and q β”‚ p or q β”‚ p then q β”‚ p iff q β”‚
β”œβ”€β”€β”€β”Όβ”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€
β”‚ F β”‚ F β”‚    F    β”‚   F    β”‚    T     β”‚    T    β”‚
β”‚ F β”‚ T β”‚    F    β”‚   T    β”‚    T     β”‚    F    β”‚
β”‚ T β”‚ F β”‚    F    β”‚   T    β”‚    F     β”‚    F    β”‚
β”‚ T β”‚ T β”‚    T    β”‚   T    β”‚    T     β”‚    T    β”‚
β””β”€β”€β”€β”΄β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜
jolly mortar
agile sundial
#

flexin

jolly mortar
stable pecan
#

yes

jolly mortar
#

can it make me a smoothie

stable pecan
# 
In [18]: print(TruthTable('T iff x'))
β”Œβ”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚ x β”‚ T iff x β”‚
β”œβ”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€
β”‚ F β”‚    F    β”‚
β”‚ T β”‚    T    β”‚
β””β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜
jolly mortar
#

god it looks so neat

stable pecan
jolly mortar
#

ye i've seen

#

||starred too||

stable pecan
#

i'll take it!

agile sundial
#

⭐

pine brook
#

any good resources for learning nested loops in python ? , i really struggle with problems where i need to print patterns.

burnt vigil
# pine brook any good resources for learning nested loops in python ? , i really struggle wit...

https://note.nkmk.me/en/python-break-nested-loops/

Break out of nested loops in Python | note.nkmk.me

There are several ways to break out of nested loops (multiple loops) in Python.This article describes the following contents.How to write nested loops in Python Use else, continue Add a flag variable Avoid nested loops with itertools.product() Speed comparison See the following article for the basic...

burnt vigil
pine brook
#

aight ill check them out

#

thank you!

burnt vigil
hollow stone
#

Hello guys, making a task:

Some spherical balls are distributed in two-dimensional space. For each ball, the x-coordinates of the beginning and end of its horizontal diameter are given. Since space is two-dimensional, y-coordinates are irrelevant in this problem. Xstart is always less than xend. The arrow can be fired strictly vertically (along the y-axis) from different points on the x-axis. A ball with coordinates xstart and xend is destroyed by an arrow if it was fired from a position x such that xstart β©½ x β©½ xend. When the arrow is released, it flies through space for an infinite time (destroying all balls in the path). An array points are given, where points [i] = [xstart, xend]. Write a function that returns the minimum number of arrows you need to fire to destroy all the balls

Tested Cases
1.1 [[10,16],[2,8],[1,6],[7,12]] 2
1.2 [[1,2],[3,4],[5,6],[7,8]] 4
1.3 [[1,2],[2,3],[3,4],[4,5]] 2
1.4 [[1,2]] 1
1.5 [[2,3],[2,3]] 1
1.6 [[1,10],[2,11],[3,12],[4,13],[5,14]] 1

def balloons(matrix):
    peeks = {}
        
    for i in matrix:
        for key in i:
            peeks.update({key: 0})
    
    for i in matrix:
        for j in range(min(i), max(i)+1):
            if j in peeks:
                peeks[j] += 1
    
    return int(len(matrix) / max(peeks.values()))
    
balloons([[10,16],[2,8],[1,6],[7,12]])``` 

but I`m feeling that i missed smth.
Will be helpfull if u can help me with some tests and bugfixes
vocal gorge
#

Since space is two-dimensional, y-coordinates are irrelevant in this problem
what

#

I think they meant one-dimensional lol

hollow stone
#

no

#

x and Z

#

or

vocal gorge
#

The arrow can be fired strictly vertically (along the y-axis)

hollow stone
#

πŸ˜„

vocal gorge
#

ah, I see what they mean

#

y-coordinates are indeed irrelevant, but their reasoning for why is rather wrong πŸ˜…

hollow stone
#

its been translated from russian, so maybe some mistakes

#

if u need, i can explain idea of that code

vocal gorge
#

I don't think your algorithm works, because it only seems to care about ends of the ranges

hollow stone
#

but if arrow shoots between that ranges, we hit balloon

#

and subtask is make code than shows min arrows to hit all balloons

#

it means some balloons can overlap

#

and with 1 arrow we can hit unlimited balloons in X-axis

vocal gorge
#

consider, say, [[1,10],[2,11],[3,12],[4,13],[5,14]]. All of these can be hit with one arrow, launched anywhere between 5 and 10

hollow stone
#

but it shows 2?

vocal gorge
#

ah, your code does answer right on this one

hollow stone
#

yeah, 1

vocal gorge
#

ah, I see now

cursive beacon
#

i have my viva in 5 hours and they may ask questions on threading
can anybody suggest any docs / video abt threading which explains it real quick

vocal gorge
cursive beacon
hollow stone
austere valley
#

Guys Im stuck on the second part of this question:

Write a Python program to create three classes. First, Second and Third such that
Second is a child class of First and Third is a child of Second. Each class contains
its own instance variable names 'data'. Describe a way for a method in Third to access
and set First's version of 'Data' to a given value, without changing Second or Third's
version.

Can someone pls helpp??

hollow stone
cursive beacon
#

only english

hollow stone
#

https://habr.com/ru/post/149420/

Учимся ΠΏΠΈΡΠ°Ρ‚ΡŒ ΠΌΠ½ΠΎΠ³ΠΎΠΏΠΎΡ‚ΠΎΡ‡Π½Ρ‹Π΅ ΠΈ многопроцСссныС прилоТСния Π½Π° Python

Π­Ρ‚Π° ΡΡ‚Π°Ρ‚ΡŒΡ Π½Π΅ для ΠΌΠ°Ρ‚Ρ‘Ρ€Ρ‹Ρ… ΡƒΠΊΡ€ΠΎΡ‚ΠΈΡ‚Π΅Π»Π΅ΠΉ Python’а, для ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Ρ€Π°ΡΠΏΡƒΡ‚Π°Ρ‚ΡŒ этот ΠΊΠ»ΡƒΠ±ΠΎΠΊ Π·ΠΌΠ΅ΠΉ β€” дСтская Π·Π°Π±Π°Π²Π°, Π° скорСС повСрхностный ΠΎΠ±Π·ΠΎΡ€ ΠΌΠ½ΠΎΠ³ΠΎΠΏΠΎΡ‚ΠΎΡ‡Π½Ρ‹Ρ… возмоТностСй...

cursive beacon
#

wanna know why we use .join()

hollow stone
#

translate by google

vocal gorge
cursive beacon
#

why doesnt then it makes the code slow

hollow stone
#

thread can't make different things at time

#

step by step

cursive beacon
#

i ran the code without .join()
the time difference wasnt much
so whats the benefit?

hollow stone
#

as more threads, more steps

hollow stone
vocal gorge
#

join is how you wait for a thread to finish. Sometimes that's something you need to do, sometimes not.

hollow stone
#

i guess he means that he ran with threading and without and wanna make from Python - C++ by using multithreads

#

D

cursive beacon
# 
import threading
import time

def smth():
    print('qwerty')
    time.sleep(1)
    print('sleep done')
a = []
for i in range(10):
    t1 = threading.Thread(target=smth)
    t1.start()
    a.append(t1)
for i in a :
    i.join()
# smth()
# smth()
hollow stone
#

πŸ˜„

cursive beacon
#

is join needed over here?

hollow stone
#

i dont really think that u need threading at this such code

agile sundial
hollow stone
#

pfffff

cursive beacon
hollow stone
#

lel

agile sundial
#

it's possible to solve it better, without that issue lol

hollow stone
#

any ideas how?

cursive beacon
# 
import random
import threading

# dictionary which stores seat nos and names of people who got it
tickets = {
    'T01': '',
    'T02': '',
    'T03': '',
    'T04': '',
}

# Seats remaining to be alloted
remaining_seats = list(tickets)

# Function to randomly assign seats to people
def assign_ticket(dict, person, lock):
    lock.acquire()
    temp = random.choice(remaining_seats)
    dict[temp] = person.name
    remaining_seats.remove(temp)
    lock.release()

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

lock = threading.Lock()

p1 = Person('Alvin', 19)
p2 = Person('John', 20)
p3 = Person('Pal', 19)
p4 = Person('Rahul', 19)

# Threads to simulate multiple people booking simultaneously
t1 = threading.Thread(target=assign_ticket, args=(tickets, p1, lock))
t2 = threading.Thread(target=assign_ticket, args=(tickets, p2, lock))
t3 = threading.Thread(target=assign_ticket, args=(tickets, p3, lock))
t4 = threading.Thread(target=assign_ticket, args=(tickets, p4, lock))

t1.start()
t2.start()
t3.start()
t4.start()

t1.join()
t2.join()
t3.join()
t4.join()

# Display the assigned seats
for i in list(tickets):
    print(i, ':', tickets[i])
#

the question was: Write a python program to achieve thread synchronization using locks when multiple
passengers are booking the ticket simultaneously.

agile sundial
severe walrus
#

hello, I have an array of vectors ( 2d shape n, 3 ) and I want to get the length ( np.sqrt(x.dot(x)) ) of each one...

vocal gorge
severe walrus
#

it worked, noice

severe walrus
#

I got one more a bit complex ( maybe )
I have 2 arrays, different sizes, and I want to make an operation between them that would have a result of the shape of the first one, with a "stride" of the size of the second one ( both have size 3 on the second dimension )

#

have I explained it clearly?

#

oh, actually, the result will be the average ( or maybe some other operation )

#

of each result

#

or maybe a 2d array that I can operate on it afterwards

vocal gorge
severe walrus
#

sorry, I will go there thanks

vocal gorge
#

(also, no, don't quite get what you want to do)

fervent saddle
#

I have a list of ints which all start at 0, and they’re randomly incremented by 1. They can also randomly be reset to 0 all at once. Is there a way to reset all of them to 0 in O(1) time? As in not actually going through the list and setting them to 0, but doing something which effectively achieves the same effect

austere sparrow
fervent saddle
#

Yeah, that might work, that seems like a good idea

lean dome
#

They would all store the last time (in nanoseconds, perhaps?) when they were last incremented.
There's no reason to store a time, just a counter. Every time you reset, increment the "number of resets" counter, and every time you read a value, check whether the stored copy of the counter matches the current value of the counter.

#

that's using the counter as a generation id.

#

and then you just ignore values that were last incremented in a previous generation, and treat them as 0 instead.

halcyon plankBOT
#

Hey @analog pagoda!

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

analog pagoda
#

Hey I'm coding a small physics engine in micropython, however I get an error saying 'bool' object isnt subscriptable

lean dome
#

!e That's what you'd get if you tried to do True[0]:

True[0]
halcyon plankBOT
#

@lean dome :x: Your eval job has completed with return code 1.

001 | <string>:1: SyntaxWarning: 'bool' object is not subscriptable; perhaps you missed a comma?
002 | Traceback (most recent call last):
003 |   File "<string>", line 1, in <module>
004 | TypeError: 'bool' object is not subscriptable
lean dome
#

you've got a [] being applied to the wrong type of object.

analog pagoda
#

Could you take a look at this code, specifically

 def scatter(self, particles, nparticles):
        where = self.intersection(particles, nparticles)
        if where[0] and particles[where[1]].isscatter:
            # avoid multiple scatters at same moment
            particles[where[1]].isscatter = False
            self.isscatter = False

            # Total and Difference Mass to Simplify Calculation
            totalmass = self.mass + particles[where[1]].mass
            massdiff = self.mass - particles[where[1]].mass

            # store velocity variable to avoid error caused by sequential calculation

            tempvelocity = [self.velocity[0], self.velocity[1]]

            self.velocity[0] = (massdiff * self.velocity[0] + 2 * particles[where[1]].mass *
                                particles[where[1]].velocity[0]) / totalmass
            self.velocity[1] = (massdiff * self.velocity[1] + 2 * particles[where[1]].mass *
                                particles[where[1]].velocity[1]) / totalmass
            particles[where[1]].velocity[0] = (-massdiff * tempvelocity[0] + 2 * self.mass * tempvelocity[
                0]) / totalmass
            particles[where[1]].velocity[1] = (-massdiff * tempvelocity[1] + 2 * self.mass * tempvelocity[
                1]) / totalmass


Nparticles = 2
rangeparticles = range(Nparticles)
mainparticles = []
mainparticles += [particle([64,0],30,[-1,0],0)]
mainparticles += [particle([64,0],30,[1,0],1)]

while True:
    for i in rangeparticles:
        mainparticles[1].clear()

    for i in rangeparticles:
        mainparticles[i].update()

    for i in rangeparticles:
        mainparticles[i].scatter(mainparticles,Nparticles)

    for i in rangeparticles:
        mainparticles[i].isscatter = True
        mainparticles[i].move()
lean dome
# 
        where = self.intersection(particles, nparticles)
        if where[0] and particles[where[1]].isscatter:

That's buggy.

#

self.intersection can return False, and if it does then you subscript False[0]

#

Maybe you meant return [False] instead of return False in intersection

analog pagoda
# 

    def intersection(self, particles, nparticles):
        for i in range(nparticles):
            if i != self.index:
                x = self.position[0] - particles[i].position[0]
                y = self.position[1] - particles[i].position[1]
                if x ** 2 + y ** 2 < 1:
                    return [True, i]
                else:
                    return [False]
lean dome
#

also - that only ever looks at the first or second particle

#

if self.index == 0, then it looks at the second particle, otherwise it looks at the first.

#

I think you meant to do:

    def intersection(self, particles, nparticles):
        for i in range(nparticles):
            if i != self.index:
                x = self.position[0] - particles[i].position[0]
                y = self.position[1] - particles[i].position[1]
                if x ** 2 + y ** 2 < 1:
                    return [True, i]
        return [False]
#

so that the False case is only hit after iterating over all possible particles.

analog pagoda
#

Oh okay, that makes more sense! I'm trying to port a simple physics engine into micropython, the code im trying to port is from a video on youtube, the uploader lost the original files

#

Aside from creating basic particles and moving them, now im trying to implement his collison detection

analog pagoda
lean dome
fervent saddle
#

Thank you, that was the first thing I thought of following the idea. But still I was thinking about how long it would work if you were using nanoseconds. Even if you weren’t using python, even if you were in C or something with limited numeric sizes, it would still work for centuries if you used an 8 byte number

#

So that’s cool. This was a good idea for this. This is a really helpful discord server

lean dome
#

the reason not to use nanoseconds isn't that it'll overflow, it's that getting the current time is a relatively slow operation, and all you need is a value that changes over time without repeating, so there's no reason to pay the cost of getting the time.

austere sparrow
fervent saddle
#

Yeah it seems like that would still be a better idea.

analog pagoda
tender fulcrum
#

Create a function called append_size that has one parameter named lst.

The function should append the size of lst (inclusive) to the end of lst. The function should then return this new list.

For example, if lst was [23, 42, 108], the function should return [23, 42, 108, 3] because the size of lst was originally 3.

#

Here's my code

#

#Write your function here
def append_size(lst):
counter = 0

for x in range(len(lst)):
counter += 1

print(lst.append(counter))

#Uncomment the line below when your function is done
print(append_size([23, 42, 108]))

#

but why doesn't this approach work? It prints out:
None
None

agile sundial
#

append doesn't return a new list it returns None

#

your function also doesn't return anything

tender fulcrum
#

ahhh

empty trout
#

How hash-tables works, and why 3 in {1,2,3,4} works by O(1)?

agile sundial
#

magic they work by hashing (hence the name) the value, and using the hash value as an index in an array

#

since it only checks one spot, it's O(1)

shut breach
#

objects get a unique* key through the hash function, so the table knows exactly where to look for it
*mostly

fervent saddle
#

!e ```py
def string_hash(s):
return sum(map(ord, s))

def add_hash_set_string(hash_set, s):
hash_set[string_hash(s) % len(hash_set)].append(s)

def check_hash_set_string(hash_set, s):
return s in hash_set[string_hash(s) % len(hash_set)]

hash_set_size = 50
hash_set = [[] for _ in range(hash_set_size)]
test_strings = ("first", "second", "third", "fourth", "fifth")

for ind in range(0, len(test_strings), 2):
add_hash_set_string(hash_set, test_strings[ind])

for s in test_strings:
print(s, check_hash_set_string(hash_set, s))```

halcyon plankBOT
#

@fervent saddle :white_check_mark: Your eval job has completed with return code 0.

001 | first True
002 | second False
003 | third True
004 | fourth False
005 | fifth True
fervent saddle
#

That’s the really basic idea of it

#

There are a lot of different ways to deal with if multiple hash values go to the same index. That way is closed addressing, where each index in the hash table is another data structure, in that case another list

#

There’s also open addressing where it’s just stored in a different place in the hash table array itself

#

It can be a lot more complex than that, involving things that are way over my head, but that’s some of the basic ideas involved

#

In python, objects have __hash__ dunder methods which are used to get their hash values

#

And if they don’t have a __hash__ method then it uses their memory address

tender fulcrum
#

Write a function named append_sum that has one parameter β€” a list named named lst.

The function should add the last two elements of lst together and append the result to lst. It should do this process three times and then return lst.

For example, if lst started as [1, 1, 2], the final result should be [1, 1, 2, 3, 5, 8].

#Write your function here
def append_sum(lst):
for x in range(len(lst)):

update = lst[-1] + lst[-2]

lst.append(update)

return lst
print(append_sum([2,5]))

with 2,5 as my input it stops at 12, but it should be 2 , 5 , 7, 12, 19

runic tinsel
#

because you don;t do it three times

#

you do length of list instead

#

so it needs to be three for you to do three, and it's not necessarily three

#

e.g. 2,5 is 2 and not 3

wide lake
#

Hey guys, Is there any too to convert python code to java?

trim fiber
#

However I don't know the easy way to convert one language to another one

weak coral
#

Can someone help me with this

wide lake
trim fiber
gaunt beacon
#

https://www.codewars.com/kata/5ed7625f548425001205e290
hi, having hard time solving this Typing challenge and can't progress.
Maybe because it's hard to debug locally or can't imagine using recursion for these 'Type things/objects?', which is a must to solve those nested Types probably.
Also Typing module seems to be changed between python versions, which adds to confusion maybe.

Basically you have to return type itself from args. Like:

to_type_hint((1, "2", 3, 4.0)) => Tuple[Union[int, str, float], ...]
to_type_hint(([1, 2], [])) => Tuple[List[int], list]```

I can check basic types with type(arg), but can't see even with intense googling how to solve it fully. 
Thanks for tips.
Codewars
Hint a Type

Task
In Python 3.5 a new module called typing was introduced which provides type hints. In this kata you will need to implement to_type_hint which needs to return (a best match of) such a type hi...

jagged escarp
#

Hi, I've a bug and I would like some indication about what's the issue.

import fs
from zipfile import ZipFile

# source zip in OSFS
src_zip = "/home/andrea/nmr/hsqc.topspin.zip"
# instantiate in-memory ephemeral FS
mem_fs = fs.open_fs('mem://')
with mem_fs:
    # open zip as ZipFS, copy content of zip in mem_FS
    with ZipFS(src_zip) as zip_fs:
        fs.copy.copy_fs(zip_fs,mem_fs)
        # how do I point at files?
        os.listdir('mem://')

output:

----------------------------------
FileNotFoundError                         Traceback (most recent call last)
<ipython-input-35-b5cb46aef5ec> in <module>
     11         fs.copy.copy_fs(zip_fs,mem_fs)
     12         # how do I point at files?
---> 13         os.listdir('mem://')
     14 
     15 

FileNotFoundError: [Errno 2] No such file or directory: 'mem://'

How can I access to the PATH of the files in mem_fs?

jagged escarp
#

context: I've got an ugly external library that accepts the path of a folder where it expects to find some files. The folder is the unzipped file in the mem_fs

serene mango
#

How do I adjust Floyd's cycle detection for multiple duplicates? Here is what I thought.:

I think when having multiple duplicates, we would have more than one cycle. So my first step would be to adjust it so it finds multiple cycles.
Suppose somehow we are able to detect mutiple cycles, so for each cycle we would need two pointers ( I think) to find the entry point.
So we would have something like :

---------o ``` with `o` as the cycle and `------` as the part from where we start the pointers. 

In case of multiple cycles , we would have multiple `-------o`, so I just need to FIND the first `-` from my `------o` , which would just be the number NOT in `------o` which I have already visited. HOW DO I FIND THIS optimally?  - `(1)`

Now I need to find entry points of the cycle, so that is guaranteed by number of steps required to get from index 0 (or my first `-`), to the starting points mod length of cycle  = no. of steps it takes from the meeting point of the two pointers in the cycle up to the entry point of the cycle and hence we have a duplicate.

Is this approach feasible?  And if it  is then how do I find `(1)`
somber nova
#

How would you guys go about finding the least lines that will pass through all points on a 2D matrix?

#

are there any resources on the topic?

serene mango
somber nova
#

@serene mango It might be super simple, but my head is super fried

#

I want to begin with just solving that

#

Later I will add constraints as parameters

#

Imma check that out, thanks @serene mango

serene mango
somber nova
#

Awesome, thanks @serene mango

serene mango
#

No problem :)) pyllow

minor pumice
somber nova
#

@minor pumice Input are points like (1,2), (2,4),(5,5).... and I want to find the minimum number of lines that will pass through all those points

minor pumice
minor pumice
somber nova
#

That can be a parameter but right now no, I don't want that

#

I want to start by just solving it

minor pumice
#

like we can put (1,1) and (2,2) on the same line?

somber nova
#

Yeah, that's the point

minor pumice
#

what is the compleixty you want?

#

n^2 is ok?

#

i dont think you even can better but maybe i am wrong

somber nova
#

Yep, that's great

minor pumice
#

ok so

#

you want

#

to see at every point the maximum number of coliniar points

#

and if you have 2 points with coordinates (x1,y1) and (x2,y2) do you know how to see if they are colliniar? (it is a math formula)

#

wait sry

#

2 points are coliniar no matter what

#

lol

#

ok so

#

you will want to see the maximum number of colliniar points

#

we can do this by the angle the points joined with the (0, 0) form

#

agree?

#

like if 2 points have the same angle with Ox they will be on the same line

somber nova
#

Makes sense, yeah

minor pumice
#

and you can map the points but will have a log(n)

somber nova
#

So you say i use the (0,0) as a comparison point for all the other points

minor pumice
#

if N and M are small you can use a trick

minor pumice
#

you cont want to see the points in a matrix

austere sparrow
# gaunt beacon https://www.codewars.com/kata/5ed7625f548425001205e290 hi, having hard time solv...

!e
typing's API is indeed a bit hard, but for this you just need to subscript the types, right?

import typing

def get_list_type(xs):  # doesn't support nested structures!
    if xs == []:
        return typing.List
    else:
        types = set(map(type, xs))
        if len(types) == 1:
            return typing.List[types.pop()]
        else:
            return typing.List[typing.Union[(*types,)]]

print(get_list_type([]))
print(get_list_type([1, 2, 3]))
print(get_list_type([1, 2, "foo"]))
halcyon plankBOT
#

@austere sparrow :white_check_mark: Your eval job has completed with return code 0.

001 | typing.List
002 | typing.List[int]
003 | typing.List[typing.Union[str, int]]
minor pumice
#

you want to see them from a geometrical point of view

#

it's easier

#

so

#

just consider (0,0) as the point of reference

somber nova
#

Okay cool

minor pumice
#

do you know how to sort the points with the angle formed with Ox?

somber nova
#

Yeah, I can do that

minor pumice
#

ok

#

if you have the points sorted you will want to make the folowing procces until there are no points left

#

in the worst case you will do points/2

#

times

#

and every time

#

wait